Nombre de surjections linéaires

Bonjour,
Un résultat plus général figure dans la proposition 3.1 de l'article de D. Laksov & A. Thorup (Counting matrices with coordinates in finite fields and of fixed rank) https://www.mscand.dk/article/view/12477

Finalement, je crois que ceci est mieux :
On compte ne nombre de noyaux possibles de nos surjections linéaires (1) et pour chaque noyau possible on prend un supplémentaire $S$ et on compte le nombre d'isomorphismes $S\to F$ (2). Le résultat est (1) $\times$ (2). Pour ça on a d'abord besoin de calculer le nombre de familles libres d'un cardinal donné dans un K-ev de dimension donnée puis le nombre d'injections d'une K-ev de dimension finie dans un autre. Avec ces dénombrements préliminaires, on peut calculer (1) et (2).
Mais peut-être que c'est fait dans le document donné par Claude. En tout cas, c'est un problème intéressant !

$\newcommand\dBinom[2]{\displaystyle\genfrac{[}{]}{0pt}{}{#1}{#2}}$En fait, ma méthode permet de dénombrer les applications $E\to F$ de rang $r$ pour n'importe quel $r$ (en comptant les injections $S\to F$ au lieu des isomorphismes). J'ai fait les calculs, on obtient $\dfrac{Q_{n-r}(q^n)}{Q_{n-r}(q^{n-r})} Q_r(q^m) = \dfrac{Q_{r}(q^n)Q_r(q^m)}{Q_{r}(q^{r})} $ comme dans le papier. Il faut démontrer au passage la formule $\dBinom{n}{r}_q = \dBinom{n}{n-r}_q$ du $q$-coefficient binomial $\dBinom{n}{r}_q = \dfrac{Q_{r}(q^n)}{Q_{r}(q^{r})}$ qui doit lui valoir en partie son nom.

claude quitté a écrit:

Histoire de participer j'ai fait $m=1$, ce qui donne $q^n-1$ formes linéaires surjectives $K^n \twoheadrightarrow K$. Pas mal, non ?

Oui, oh c'est juste le nombre de formes linéaires non nulles. 8-)(:P)

Pour les surjections ($r=m$) on tombe sur la formule plus simple $Q_m(q^n)$, comme tu l'as dis Claude. C'est égal au nombre d'injection dans l'autre sens $F\hookrightarrow E$, donc il y avait forcément une bonne raison à ça, mais je ne l'ai pas trouvée. C'est toi qui me l'a donnée avec la transposée, donc merci.

$\newcommand \Binom[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}\def\F{\mathbb F}$Rietveld & Calli
En guise de modeste cadeau pour le travail de Calli : le polynôme $\Binom{n}{d}_q$ pour $n=7$ et $0 \le d \le n$. La colonne de gauche, c'est $d$, ensuite le $q$-polynôme binomial en question et enfin le coefficient binomial $\binom{n}{d}$ habituel que l'on obtient en faisant $q = 1$ dans $\Binom{n}{d}_q$.

[color=#000000]0 1                                                                                               1
1 q^6 + q^5 + q^4 + q^3 + q^2 + q + 1                                                             7
2 q^10 + q^9 + 2*q^8 + 2*q^7 + 3*q^6 + 3*q^5 + 3*q^4 + 2*q^3 + 2*q^2 + q + 1                      21
3 q^12 + q^11 + 2*q^10 + 3*q^9 + 4*q^8 + 4*q^7 + 5*q^6 + 4*q^5 + 4*q^4 + 3*q^3 + 2*q^2 + q + 1    35
4 q^12 + q^11 + 2*q^10 + 3*q^9 + 4*q^8 + 4*q^7 + 5*q^6 + 4*q^5 + 4*q^4 + 3*q^3 + 2*q^2 + q + 1    35
5 q^10 + q^9 + 2*q^8 + 2*q^7 + 3*q^6 + 3*q^5 + 3*q^4 + 2*q^3 + 2*q^2 + q + 1                      21
6 q^6 + q^5 + q^4 + q^3 + q^2 + q + 1                                                             7
7 1                                                                                               1
[/color]

J'attache la définition de $\Binom{n}{d}_q$ en fonction de la $q$-factorielle. Il faut juste se convaincre que le quotient est un polynôme en $q$.

Je crois me souvenir de l'existence d'un fil (il y a un certain temps) où l'on essayait de compter le nombre de points sur $\F_q$ d'une variété torique : il me semble que c'est un polynôme en $q$.

Salut Flip Flop
Ok, pour le titre $q$-polynôme(s). Je ne sais plus ce que l'on avait fabriqué dans ce fil. Je me souviens juste que j'étais largué concernant vos posts (toi et Lupulus) où il était question de drapeaux.

Mode en aparté (sorry Rietveld)
J'ai vu que tu lisais SGA1 en planquette. De mon côté, histoire d'apprendre un peu de maths, j'ai essayé de comprendre ce qu'était une variété de Schubert. Ma ma mia. Et figure toi que le Dan Laksov du papier que j'ai pointé ici, c'est le fameux Dan Laksov (avec Kleiman) du Schubert Calculus http://people.reed.edu/~davidp/pcmi/laksov.pdf

Et visiblement Dan Laksov & Anders Thorup (les auteurs du papier pointé ici) sont peut-être nés avec du Schubert dans leur berceau, cf http://web.math.ku.dk/~thorup/temp/flagat.pdf. Pourquoi c'est toujours les mêmes qui font avancer la science ?
Fin du mode en aparté.

$\newcommand\Binomq[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}$Ces $q$-coefficients binomiaux et $q$-factorielles sont assez riches, dis donc ! Déjà, $[n]_q$ est égal au nombre de droites de $K^n$. Ensuite, en regardant le fil mentionné "$q$-polynômes" et l'autre fil "Diagonalisation projective souhaitée" vers lequel le premier pointe, j'ai appris que la $q$-factorielle $[n]_q!$ est égale au nombre de drapeaux maximaux de $K^n$ (i.e. aux $\{0\}=F_0\subset F_1\subset \dots\subset F_n = K^n$ avec $\dim F_k = k$) et que le $q$-coefficient multinomial $\frac{[n]_q!}{[\gamma_1]_q!\cdots [\gamma_r]_q! }$ avec $\gamma_1+\cdots +\gamma_r=n$ est égal au nombre de drapeaux $\{0\}=F_0\subset F_1\subset \dots\subset F_r = K^n$ avec $\dim F_k = \gamma_1 +\cdots +\gamma_k$.

Et on peut s'amuser à trouver ou retrouver des identités sur les $\Binomq{n}r$ par méthode combinatoire.

• Par exemple, si on se donne une forme quadratique non dégénérée sur $K^n$, on a, pour tout sev $V$, $\dim V+\dim V^\perp = n$ et $(V^\perp)^\perp =V$. Donc $V\mapsto V^\perp$ est une bijection entre les sev de dimension $r$ les sev de dimension $n-r$, ce qui redonne $\Binomq{n}r = \Binomq{n}{n-r}$.
• Ensuite, les familles de $K^m$ de longueur $n+1$ de rang $r+1$ peuvent être séparées en deux groupes : celles dont les $n$ premier vecteurs sont de rang $r$ et celles dont les $n$ premiers vecteurs sont de rang $r+1$. Cela donne $$\Binomq{n+1}{r+1} Q_{r+1}(q^m) = \Binomq{n}{r} Q_r(q^m) (q^m-q^r) + \Binomq{n}{r+1} Q_{r+1}(q^m)\, q^{r+1}$$ donc $$\Binomq{n+1}{r+1} = \Binomq{n}{r} + \Binomq{n}{r+1} q^{r+1}.$$
• Enfin, le nombre d'applications linéaires $K^n\to K^m$ est égal à la somme sur $r$ du nombre d'applications linéaires de rang $r$, donc $ \sum\limits_{r=0}^n \Binomq{n}r Q_r(q^m) = q^{nm}$. Puisque c'est vrai pour tout $m\in\Bbb N$, on a $$ \sum_{r=0}^n \Binomq{n}r Q_r(X) = X^n .$$ En évaluant en $x=0$, on trouve pour $n\in\Bbb N^*$ l'identité $$\sum_{r=0}^n \Binomq{n}r (-1)^r q^{\textstyle \binom{r}2}=0$$ qui est un cas particulier de la proposition 1.4 du papier fourni par Claude.
  Quand $q=1$, on retrouve le cas particulier de la formule du binôme $ \sum\limits_{r=0}^n \binom{n}r (X-1)^r = X^n$. Ça me fait me demander : existe-t-il un analogue de la formule du binôme pour les $q$-coefficients binomiaux ? J'ai essayé de regarder $\sum\limits_{r=0}^n \Binomq{n}r Q_r(X) Q_{n-r}(Y)$ pour $n=2$ mais je n'ai rien obtenu de satisfaisant.

$\newcommand \Binom[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}\def\F{\mathbb F}$Calli. Je vois que tu t'amuses bien avec les $q$-polynômes.

$\bullet$ Je réponds à ton AVANT dernier post : $\Binom{n}{r}_q$ est un polynôme en $q$. Je n'ai pas d'argument personnel si bien que je pompe sur les autres. Par exemple sur toi. Bien joué ; sauf qu'à un moment donné, tu ne peux pas dire que $\Binom{n}{r}_q$ est entier lorsque $q$ est entier au prétexte que c'est le nombre de ....etc.. Il faut limiter $q$ à $q$ puissance d'un premier. Mais cela marche quand même donc encore deux magnifiques cadeaux (cf plus loin).

Voilà comment procèdent Berndt, Evans & Williams au début de leur ouvrage ``Gauss and Jacobi Sums''. Ils définissent (page 18) une fraction rationnelle en $q$, pour $0 \le r \le n$ :
$$
\Binom{n}{r}_q = {(q^n - 1) (q^{n-1} - 1) \cdots (q^{n-r+1} - 1) \over (q-1) (q^2 - 1) \cdots (q^r - 1)}
$$Et via un petit calcul (je zappe) montrent les deux relations de récurrence (une suffit à nos besoins)
$$
\Binom{n}{r}_q = \Binom{n-1}{r-1}_q + q^r \Binom{n-1}{r}_q = \Binom{n-1}{r}_q + q^{n-r} \Binom{n-1}{r-1}_q
$$Par récurrence sur $n$, on en déduit que $\Binom{n}{r}_q$ est un polynôme en $q$ avec le bonus suivant : il est unitaire de degré $r(n-r)$ et à coefficients entiers $\ge 0$. En fait, je crois que TOUS ses coefficients, du degré $0$ au degré $r(n-r)$, sont des entiers $\ge 1$.

$\bullet$ Formule du binôme. Je ne sais pas si ce qui suit répond à la question de ton dernier post. J'ai vu cela à la première page de https://arxiv.org/pdf/math/0407093.pdf. C'est dû à Schüterzenberger dit Henry Cohn. En non commutatif, on considère 3 variables $x,y,q$ :
$$
xq = qx, \quad yq = qy, \qquad yx = qxy \qquad\qquad \text{alors}\qquad (x + y)^n = \sum_{r=0}^n \Binom{n}{r}_q x^r y^{n-r}
$$Je trouve que c'est joli car cela montre pas mal de choses. Et quand on fait $q = 1$ ...etc.. Il y a bien sûr un problème d'oeuf(s) et de poule(s).

$\bullet$ Cadeau I. Via les parties $S$ de cardinal $r$ de $\{1..n\}$ en notant $\min = 1 + 2 + \cdots + r = \binom{r+1}{2}$ le minimum des sommes des éléments de $S$
$$
\Binom{n}{r}_q = \sum_{S \subset \{1..n\} \atop \#S = r} q^{\ \sum\limits_{s \in S} s - \min}
$$Et quand on fait $q = 1$ ...etc...

[color=#000000]> n := 9 ; 
> r := 4 ;
> G := qBinomial(n,r) ;
> G ;
q^20 + q^19 + 2*q^18 + 3*q^17 + 5*q^16 + 6*q^15 + 8*q^14 + 9*q^13 + 11*q^12 + 11*q^11 + 12*q^10 + 11*q^9 + 
    11*q^8 + 9*q^7 + 8*q^6 + 6*q^5 + 5*q^4 + 3*q^3 + 2*q^2 + q + 1
> 
> B := Subsets({1..n},r) ;
> min := Binomial(r+1,2) ;
> F := &+[q^(&+S - min) : S in B] ;
> F ;
q^20 + q^19 + 2*q^18 + 3*q^17 + 5*q^16 + 6*q^15 + 8*q^14 + 9*q^13 + 11*q^12 + 11*q^11 + 12*q^10 + 11*q^9 + 
    11*q^8 + 9*q^7 + 8*q^6 + 6*q^5 + 5*q^4 + 3*q^3 + 2*q^2 + q + 1
> F eq G ;
true
[/color]

$\bullet$ Cadeau II. C'est lié au cadeau I. Histoire de faire savant, on parle de quantum-interprétation. Cela vient de https://arxiv.org/abs/1601.06110, lemme 2.1 page 5. Le lien est dans la preuve (j'attache un morceau). Pas eu le temps de réfléchir (à la retraite, on n'a pas le temps ...etc...)
$$
\Binom{n}{r}_q = \sum_{\lambda \subset (n-r)^r} q^{|\lambda|}
$$La somme porte sur les partitions $\lambda = (\lambda_1 \ge \lambda_2 \ge \cdots)$ qui sont les suites décroissantes d'entiers nulles à partir d'un certain rang. Et ici limitées par le rectangle $(n-r) \times r$, cf le papier pour cette contrainte. Et $|\lambda|$, c'est par définition $\sum_i \lambda_i$.

[color=#000000]> IsInsideRectangle := func < lambda, n, r | #lambda le n-r  and #TransposePartition(lambda) le r > ;
> 
> P := &cat [[lambda : lambda in Partitions(d) | IsInsideRectangle(lambda,n,r)] : d in [0..r*(n-r)]] ;
> #P ;
126
> lambda := Random(P) ;
> lambda ;
[ 4, 4, 3, 2, 1 ]
> Weight(lambda) ;
14
> 
> H := &+[q^Weight(lambda) : lambda in P] ;
> H ;
q^20 + q^19 + 2*q^18 + 3*q^17 + 5*q^16 + 6*q^15 + 8*q^14 + 9*q^13 + 11*q^12 + 11*q^11 + 12*q^10 + 11*q^9 + 
    11*q^8 + 9*q^7 + 8*q^6 + 6*q^5 + 5*q^4 + 3*q^3 + 2*q^2 + q + 1
> H eq G ;
true
[/color]

$\bullet$ Ca, c'est juste pour moi, pour ne pas oublier comment on détermine le $q$-polynôme d'une variété torique $X$, via les faces des cônes d'un fan de $X$. La valeur en $q$ de ce polynôme représente le nombre de points de $X$ sur $\F_q$

[color=#000000]qPolynomial := function(X)
  // X est une variété torique
  n := Dimension(X) ;
  xCones := AllCones(Fan(X)) ;
  // xCones = [[cônes de dim 0], [cônes de dim 1], ..., [cônes de dim n]]
  // N(d) = nombre de cônes de dimension d
  N := map < [0..n] -> Z | d :-> #xCones[d+1] > ;
  return &+[N(d)*(q-1)^(n-d) : d in [0..n]] ;
end function ;
[/color]

$\newcommand\Binomq[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}$Merci Claude.

claude quitté a écrit:

Bien joué ; sauf qu'à un moment donné, tu ne peux pas dire que $\Binomq{n}{r}$ est entier lorsque $q$ est entier au prétexte que c'est le nombre de ....etc.. Il faut limiter $q$ à $q$ puissance d'un premier.

C'est exact. Heureusement, ce n'est pas bien grave.

La formule de Schüterzenberger répond très bien à ma question. Mais un binôme non commutatif, ça je ne m'y attendais pas ! En général, ce genre de formule ne marche que dans les anneaux commutatifs.

Très astucieux, le passage du cadeau I au cadeau II.

$\newcommand\Binomq[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}$Mais Claude, tu viens de me donner sans le savoir mon binôme commutatif ! (:D En m'inspirant du $q$-binôme négatif $\prod\limits_{i=0}^n \frac1{1 - q^ i X} = \sum\limits_{r =0}^\infty \Binomq{n+r}{r} X^r$ et de la formule déjà établie $\sum\limits_{r=0}^n \Binomq{n}r (-1)^r q^{\textstyle \binom{r}2}=0$, j'ai trouvé que $$\fbox{${\displaystyle\sum_{r=0}^n \Binomq{n}r q^{\textstyle \binom{r}2} X^r Y^{n-r} = \prod_{i=0}^{n-1} (q^ i X+Y)}$}.$$
Pour le prouver, on utilise l'identité $\Binomq{n+1}{r+1} = \Binomq{n}{r} + \Binomq{n}{r+1} q^{r+1}$ : $$\begin{eqnarray*}
\sum_{r=0}^{n+1} \Binomq{n+1}r q^{\textstyle \binom{r}2} X^r Y^{n+1-r} &=& \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r+1}2} X^{r+1} Y^{n-r} + \sum_{r=0}^{n} \Binomq{n}r q^r q^{\textstyle \binom{r}2} X^r Y^{n+1-r}\\
&=& X \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r} + Y \sum_{r=0}^{n} \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r} \\
&=& (X+Y) \sum_{r=0}^n \Binomq{n}r q^{\textstyle \binom{r}2} (qX)^r Y^{n-r}
\end{eqnarray*}$$
Le nom de "formule du binôme" n'est pas volé puisqu'on retombe bien sur le binôme classique quand $q=1$. Cas particuliers : (1) en évaluant $(X,Y)$ en $(-1,1)$ on retombe sur $\sum\limits_{r=0}^n \Binomq{n}r (-1)^r q^{\textstyle \binom{r}2}=0$ et (2) en évaluant $X$ en $1$ on a $\sum_{r=0}^n \Binomq{n}r \, q^{\textstyle \binom{r}2} Y^{n-r} = (-1)^n Q_n(-Y)$ puis $$\sum_{r=0}^n \Binomq{n}r q^{\textstyle \binom{r}2} (-1)^r X^{n-r} = Q_n(X).$$ Donc on a une expression de $Q_n(X)$ en fonction des $X^r$ et aussi une expression de $X^n$ en fonction des $Q_r(X)$ (cf. http://www.les-mathematiques.net/phorum/read.php?3,2042316,2043408#msg-2043408). La formule de $Q_n(X)$ que je viens d'écrire est aussi dans le premier article joint, mais elle y est prouvée différemment.

Calli
J'en suis à ton avant dernier post (binôme commutatif). Bien sûr, dans ta première ligne, ``en s'inspirant'' ne veut pas dire ``en utilisant'' : ton post est self-contained ! Une remarque : en faisant $Y = 1$ dans ton encadré, je vois mieux le lien entre la formule que j'ai donnée et la tienne. Encore bien joué mais je ne sais plus où donner de la tête.

Autre chose : le cadeau I, dans mon post http://www.les-mathematiques.net/phorum/read.php?3,2042316,2043574#msg-2043574, qui venait de https://arxiv.org/pdf/1601.06110.pdf, cela m'a rappelé quelque chose que j'avais fait dans le fil $q$-polynômes. A voir plus tard. En attendant, j'attache de nouveau un extrait de l'article ``quantum'', en plein milieu de la preuve (la référence [Stal12], c'est Stanley, Enumerative Combinatorics). Bref, cela explose dans tous les sens dans ma pauvre tête (bis).

PS : en ce qui concerne la cure, j'ai également réservé une place pour toi.