Couper les alphabets en quatre

Quelques commentaires sur l’oeuvre mathématique de

Gian-Carlo Rota

Alain Lascoux CNRS, Institut Gaspard Monge, Université de Marne-la-Vallée 77454 Marne-la-Vallée Cedex, France Alain.Lascoux@univ-mlv.fr

Abstract

We stress the importance of addition (of alphabets) in the mathematical work of Gian-Carlo Rota, in particular for what concerns his ”Finite Operator Calculus”.

J’ai rencontré Gian-Carlo en 1976 en débarquant au MIT à la recherche d’interlocuteurs. Travaillant étroitement avec Marcel-Paul Schützenberger qui était un de ses grands amis, je n’avais pas besoin d’autre introduction! De plus, les quelques dollars que j’avais en poche me cantonnaient aux restaurants dits “fasts”, ce que le sens de l’hospitalité de Gian-Carlo pouvait difficilement accepter. J’eus donc l’honneur de figurer à plusieurs reprises sur sa note de frais professionnels. C’était encore l’époque où les inspecteurs des impôts acceptaient d’encourager le développement de la combinatoire. Ce n’est plus le cas de nos jours où cette dernière a accédé à la reconnaissance officielle du Séminaire Bourbaki. Je tiens à préciser toutefois que le repas était prolongé par de longues discussions sur les mérites comparés de différentes structures algébriques, Gian-Carlo me demandant de lui répéter une fois encore les axiomes des λ-anneaux qu’il notait dans ses cahiers avec un nouvel exemple de leur usage.

Gian-Carlo se présentait comme l’épigraphiste des richesses de la littérature mathématique passée et l’avocat de la recherche des structures qui permettent de les intégrer aux courants actuels.

Par exemple, le principe d’inclusion-exclusion conduit à l’étude des ensembles ordonnés, et à leur fonction de Moebius. La théorie des invariants mène au calcul ombral, le calcul différentiel a sa contrepartie discrète, etc.

Mais il ne suffit pas de dégager les structures algébriques pour qu’elles existent, il faut encore les commercialiser. Et pour cela, montrer que l’investissement que représente leur apprentissage est récompensé par l’éclairage nouveau apporté à différents domaines classiques, la mise en relation de notions disjointes jusque là, et l’apport de nouveaux objets - car on ne peut toujours moudre le même grain, il faut semer!

Calcul ombral [13], fonction de Moebius [14], algèbres de Hopf [19], de Baxter [16], etc. peuvent de fait se résumer chacun(e)s en deux mots.

Par exemple, le calcul ombral est l’art de lever les indices et d’abaisser les exposants, l’inversion de Moebius est l’inversion des matrices triangulaires de diagonale 1, …, 1, etc.

Mais ces notions sont plus sophistiquées qu’il n’y paraît. Comment calculer sur des ensembles ordonnés quand on ne peut les représenter et expérimenter sur eux dès qu’ils sont quelque peu volumineux? Même dans le cas d’un objet aussi classique que le groupe symétrique, si l’on peut donner sa fonction de Moebius (relative à l’ordre de Bruhat), on ne sait dire que peu de choses sur ses intervalles ( i.e. les ensembles [x, y] := {z : x ≤ z ≤ y}). Par exemple, on conjecture que les polynômes de Kazhdan-Lusztig P_{x,y} pour le groupe symétrique ne dépendent que de la classe d’isomorphisme de l’intervalle [x, y], mais en général on ne sait pas calculer ce polynôme, quoique ce soit le premier niveau de la description des intervalles.

Quand à lever des indices, rien ne nous en empêche, mais bien entendu on veut le faire sans perte d’information.

Il est clair que dans une identité linéaire en des indéterminées a_{i}, i = 1, 2 …, on peut remplacer sans dommage chaque a_{i} par a^{i}, en supposant que a est une indéterminée ou un élément transcendant sur l’espace de base. Mais pourquoi dans les relations de straightening si chères à Rota [21] entre les mineurs d’une matrice peut-on se restreindre à une matrice de Vandermonde

[\begin{matrix}a^{1} & a^{2} & a^{3} & ⋯ \\ b^{1} & b^{2} & b^{3} & ⋯ \\ · & · & · & ⋯ \end{matrix} ]

au lieu d’avoir à prendre une matrice générique

[\begin{matrix}a_{1} & a_{2} & a_{3} & ⋯ \\ b_{1} & b_{2} & b_{3} & ⋯ \\ · & · & · & ⋯ \end{matrix} ] ?

Les règles du calcul ombral sont simples, mais définir précisément leur domaine de validité est beaucoup moins élémentaire et pose un problème de “fondations”, cf. [23]. J’aborderai donc ce problème sous l’angle le plus simple que je connaisse, celui de l’addition.

Addition de quoi? Addition d’alphabets, i.e. union disjointe d’ensembles d’indéterminées :

(𝔸 = {a} , 𝔹 = {b}) ↦ 𝔸 + 𝔹 := {a} ∪ {b} .

Ne considérons pour le moment que des ensembles finis. En prenant une indéterminée supplémentaire z, on peut écrire des fonctions génératrices

λ_{z}(𝔸) := ∏_{a∈𝔸}(1 + za) , σ_{z}(𝔸) := ∏_{a∈𝔸} \frac{1}{1 − za}.  (1)

dont le développement définit les fonctions complètes S^{i}(𝔸) et élémentaires Λ^{i}(𝔸)

λ_{z}(𝔸) = ∑ z^{i} Λ^{i}(𝔸) , σ(𝔸) = ∑ z^{i} S^{i}(𝔸) .  (2)

L’addition des alphabets implique donc le produit des fonctions génératrices

λ_{z}(𝔸 + 𝔹) = λ_{z}(𝔸) λ_{z}(𝔹) , σ_{z}(𝔸 + 𝔹) = σ_{z}(𝔸) σ_{z}(𝔹) .  (3)

On a besoin aussi des sommes de puissance ψ_{i}:

ψ_{i}(𝔸) = ∑_{a∈𝔸}a^{i} , ∑_{i=1}^{∞} ψ_{i}(𝔸)\frac{z^{i}}{i} = log(σ_{z}(𝔸)) .  (4)

Mais quand on sait additionner, on sait aussi multiplier par un entier positif

𝔸 = {a} → 2𝔸 := {a′} ∪ {a′′} , 3𝔸 := {a′} ∪ {a′′} ∪ {a′′′} …

c’est-à-dire doubler, tripler chaque lettre (et oublier les diacritiques à l’étape finale):

λ_{z}(2𝔸) = λ_{z}(𝔸)^{2} , λ_{z}(3𝔸) = λ_{z}(𝔸)^{3} …

On n’a pas besoin de plus d’outils pour inverser les séries formelles f(z) = z + f_{1}z^{2} + f_{2}z^{3} + ⋯, c’est-à-dire trouver g(z) = z + g_{1}z^{2} + g_{2}z^{3} + ⋯ telle que

f(g(z)) = z & g(f(z)) = z .

C’est un problème que l’on sait résoudre depuis Lagrange, en calculant les dérivées successives des puissances de f, c’est-à-dire à l’aide d’opérations qui s’expriment aisément en termes d’alphabets. Si l’on décide d’écrire f sous la forme f = zσ_{−z}(𝔸), alors on trouve que les puissances de g sont

g^{k}(z) = k z^{k} ∑ \frac{z^{i}}{i + k} Λ^{i}((i + k)𝔸) ,  (5)

et donc ne réclament que la multiplication des alphabets par des entiers si k ∈ ℤ (on peut en fait prendre k ∈ ℂ; le cas limite k = 0 donne le logarithme de g).

La théorie des fonctions symétriques fournit, pour tout choix de couples de bases adjointes par rapport au produit scalaire naturel, un développement des Λ^{i}((i+k)𝔸) en fonction des coefficients de f ou 1/f. Ces développements apparaissent dans la littérature classique, obtenus par les nombreux mathématiciens qui ont voulu donner leur interprétation de l’inversion de Lagrange, en dernier lieu dans la thèse de Vincent Prosper qui en propose l’implémentation [9, 10]. En d’autres termes, la notation condensée Λ^{i}((i+k)𝔸) contient les formules suivantes (nous rejetons en annexe les propriétés requises des fonctions symétriques) :

\begin{aligned}Λ^{i}((i + k)𝔸) & = & (−1)^{i} ∑_{|J|=i} ψ_{J}(−(i + k))S^{J}(𝔸) & (a) \\ & = & ∑_{|J|=i} ψ_{J}(i + k)Λ^{J}(𝔸) & (b) \\ & = & ∑_{|J|=i} S_{J}(i + k)S_{J^{∼}}(𝔸) & (c) \\ & = & ∑_{|J|=i} Λ^{J}(i + k)ψ_{J}(𝔸) & (d) \\ & = & (−1)^{i} ∑_{|J|=i} \frac{(−i−k)^{ℓ(J)}}{m_{1}!m_{2}!···} (\frac{ψ_{1}}{1} )^{m_{1}}(\frac{ψ_{2}}{2} )^{m_{2}}(\frac{ψ_{3}}{3} )^{m_{3}} ⋯ & (e) \end{aligned} (6)

sont les développements possibles dans la base des produits de fonctions complètes S^{J}, des produits de fonctions élémentaires Λ^{J}, des fonctions de Schur S_{J}, des fonctions monomiales ψ_{J}, des produits de sommes de puissance ψ^{J}, en notant dans (6e) les partitions sous forme exponentielle : J = 1^{m_{1}}2^{m_{2}} · · ·.

Soulignons encore une fois que chacun de ces développements résulte d’une explicitation de l’opération 𝔸 → k 𝔸 à l’aide de (1),...,(4).

Revenons aux travaux de Gian-Carlo. Je dis que l’article fondamental ”Finite Operator Calculus” [R1] repose essentiellement sur l’inversion de Lagrange, et donc en fin de compte, sur la multiplication des alphabets par des entiers.

De quoi s’agit-il? On veut déformer la dérivée

D := \frac{d}{dx} → Q = D + a_{1}D^{2} + a_{2}D^{2} + ⋯

tout en préservant des propriétés telles que l’existence d’une base {x^{n}} : Dx^{n} = nx^{n−1}, celle d’un développement de Taylor, etc. , i.e. les outils de l’analyse classique en une variable.

Introduisons un alphabet 𝔸 (dont on ne cherchera pas à expliciter les éléments !) pour écrire

Q = D σ_{−D}(𝔸) = D − S^{1}(𝔸)D^{2} + S^{2}(𝔸)D^{2} − S^{3}(𝔸)D^{3} + ⋯  (7)

On cherche des polynômes P_{n}, n = 1, 2 …, P_{0} := 1, tels que

Q(P_{n}) = nP_{n−1} & P_{n}(0) = 0 , n ≥ 1 .  (8)

Le théorème de Rota ([17], th. 4), est

P_{n} = x λ_{D}(n𝔸) x^{n−1} , n ≥ 1 .  (9)

Preuve. Notant f′ la dérivée en x d’une fonction f(x), on a f(D)x = x f(D)+ f′(D). Prenant f telle que f(D) = λ_{D}(−𝔸), on a Q = D f = f D et

Q P_{n} = f DP_{n} = f Dxf^{−n} x^{n−1}
= f f^{−n} x^{n−1} + fx Df^{−n}x^{n−1} = f^{−n+1} xx^{n−2} + fxf^{−n}Dx^{n−1}

= (1−n)f′ f^{−n} x^{n−2} +xf^{−n+1}x^{n−2} +xf′ f^{−n} (n−1)x^{n−2} +xf^{−n+1}(n−1)x^{n−2}

= n P_{n−1}

Le théorème de Rota a de multiples corollaires qui sont les propriétés de l’analyse classique que l’on voulait déformer :

• existence d’un noyau reproducteur

∑ \frac{P_{n}(y)}{n!} Q^{n}(f(x)) = f(x + y) ,  (10)

• d’une formule de Cauchy

∑ \frac{P_{n}(y)}{n!} x^{n}σ_{−x}(n𝔸) = exp(xy) ,  (11)

• d’une propriété de “binomialité”

P_{n}(x + y) = ∑ \binom{n}{i}P_{i}(x)P_{n−i}(y) .  (12)

Ces formules peuvent s’interpréter comme résultant du remplacement de l’exponentielle classique par ∑ x^{n}P_{n}(x)/n!. Elles peuvent apparaıtre beaucoup plus surprenantes une fois spécialisées.

Prenons par exemple Q = D(1 − D), i.e. 𝔸 est tel que S^{1}(𝔸) = 1, S^{i}(𝔸) = 0, i > 1. Alors Λ^{i}(n𝔸) = \binom{n+i−1}{i},

P_{n} = ∑ \frac{(n − i) ⋯ (n + i − 1)}{i!} x^{n−i} ,  (13)

et la formule de Cauchy donne le développement de l’exponentielle

exp(xy) = ∑ \frac{P_{n}(y)}{n!} x^{n} (1 − x)^{n}  (14)

utilisé par Schur [24] pour calculer sin(πx).

Les polynômes d’Abel apparaissent pour

Q = D + aD^{2}/1! + a^{2}D^{3}/2! + ⋯,

i.e. pour Q tel que Q(f(x)) = \frac{d}{dx}f(x + a).

L’ “alphabet d’Abel” correspondant est tel que S^{i}(𝔸) = (−a)^{i}/i!, Λ^{i}(n𝔸) = S^{i}(n𝔸) = (−na)^{i}/i!, et donc alors

P_{n}(x) = x (x − na)^{n−1} .  (15)

Dans ce cas, ce sont en fait les sommes de puissances qui sont les plus simples, car l’on a :

ψ_{1}(n𝔸) = −na & ψ_{i}(n𝔸) = 0 , i > 1 .

On peut noter que les dimensions dim(J), J partition, des représentations du groupe symétrique sont données par la spécialisation S^{i}(𝔸) = 1/i!. On peut donc calculer les déterminants en les S^{i}(n𝔸) en terme de ces dimensions (qui ont différentes interprétations combinatoires). Ainsi a-t-on pour les fonctions de Schur en les multiples entiers de l’alphabet d’Abel, pour J = [j_{1}, …, j_{n}], 0 ≤ j_{1} ≤≤ ⋯ ≤ j_{n} :

S_{J}(n𝔸) = \frac{(−a n)^{|J|}}{|J|!} dim(J) = (−a n)^{|J|} det |\frac{1}{(j_{i} + k − i)!}|_{1≤i,k≤n} .

Dernier exemple de déformation de la dérivée, conduisant aux nombres de Bernoulli:

Q = D\frac{D}{exp(D) − 1} = D (1 − \frac{1}{2}D + \frac{B_{2}}{2!} D^{2} + \frac{B_{4}}{4!} D^{4} + ⋯)  (16)

On a donc

S^{i}(𝔸) = B_{i}/i! & Λ^{i}(𝔸) = (−1)^{i}/(i + 1)! , i ≥ 0 .

Les fonctions élémentaires sont les mêmes que pour Abel (et a = 1), à un décalage d’indice près, qui a des conséquences que le corps médical dénomme drastiques:

P_{n}(x) = x (\frac{exp(D) − 1}{D})^{n} x^{n−1} = x(1 + D/2! + D^{2}/3! + ⋯)^{n} x^{n−1} . (17)

D’avoir des notations compactes pour désigner les coefficients des puissances d’une série facilite grandement les calculs. Mais de plus, que ces notations utilisent le formalisme des alphabets et des fonctions symétriques permet, à partir d’une identité, d’en engendrer de multiples autres en puisant dans tout bon formulaire de fonctions symétriques [7] ou [8].

Ainsi, dans le cas présent de l’alphabet de Bernoulli, l’identité \frac{d}{dx} exp(x) = exp(x) implique que ψ_{i}(𝔸) = −S^{i}(A) ∀i > 1, et donc les relations de Newton entre fonctions complètes S^{i} et sommes de puissances ψ_{k}

nS^{n} = ψ_{1}S^{n−1} + ψ_{2}S^{n−2} + ⋯ ψ_{n}S^{0}

fournissent la récurrence suivante sur les nombres de Bernoulli (dont Gessel me signale qu’elle est classique)

−(n + 1)S^{n}(𝔸) = \frac{−n − 1}{n!}B_{n} = S_{2}(𝔸)S_{n−2}(𝔸) + S_{4}(𝔸)S_{n−4}(𝔸) + ⋯ + S_{n−2}(𝔸)S_{2}(𝔸) . (18)

On pourra comparer l’algorithme sous-jacent à celui de Mademoiselle Augusta Ada, comtesse de Lovelace,

\frac{2x − 1}{2(2x + 1)} = B_{2} \frac{2x}{2!} + B_{4} \frac{2x(2x − 1)(2x − 2)}{4!} + B_{6} \frac{2x ⋯ (2x − 4)}{6!} + ⋯ (19)

Pour clore le chapitre des nombres de Bernoulli, on me permettra de les exprimer en terme de polynômes de Schubert [6] Y_{v} spécialisés en x_{1} = x_{2} = ⋯ = 1. On a ainsi

(−1)^{n−1}B_{2n} = \frac{Y_{[2,(3,0)^{n−1}]}}{2^{n}(n − 1)!(2^{2n} − 1)} = \frac{n Y_{[1,(2,0)^{n−1}]}}{2^{2n}(2^{2n} − 1)}  (20)

B_{12} = Y_{[2,3,0,3,0,3,0,3,0,3]} \frac{1}{31449600} = Y_{[1,2,0,2,0,2,0,2,0,2]} \frac{1}{1397760} .

Mais l’on peut réduire les déterminants exprimant les polynômes de Schubert précédents, et finalement on obtient les nombres de Bernoulli comme mineurs de la matrice de Pascal |\binom{i}{2j−i}|, aux facteurs 2 × (2^{2n} − 1) près. Par exemple, pour n = 6, le produit de B_{12} = −\frac{691}{2730} par l’entier 2 × (2^{2n} − 1) (= 8190), est égal au déterminant (=2073) de la matrice suivante (écrivant ‘·‘ pour ‘0‘, la matrice de Pascal décalée dont elle est extraite figurant à droite) :

[\begin{matrix}1 & 1 & · & · & · & · \\ · & 1 & 1 & · & · & · \\ · & · & 3 & 1 & · & · \\ · & · & 1 & 6 & 1 & · \\ · & · & · & 5 & 10 & 1 \\ · & · & · & 1 & 15 & 15 \end{matrix}] ← [\begin{matrix}1 & 1 & · & · & · & · & · & · & · & · \\ · & 1 & 2 & 1 & · & · & · & · & · & · \\ · & · & 1 & 3 & 3 & 1 & · & · & · & · \\ · & · & · & 1 & 4 & 6 & 4 & 1 & · & · \\ · & · & · & · & 1 & 5 & 10 & 10 & 5 & 1 \\ · & · & · & · & · & 1 & 6 & 15 & 20 & 15 \end{matrix}]

Les combinatoristes ne peuvent se lasser de répéter qu’ils ont pratiqué le q-calcul avant que les spécialistes des groupes quantiques ne s’en emparent.

Ils disposent ainsi d’une q-dérivée D_{q} : f ↦ \frac{f(qx)−f(x)}{qx−x}. A l’instar du cas précédent, on peut la déformer :

D_{q} ↦ Q = D_{q}σ_{−D_{q}}(𝔸) = D_{q} − S^{1}(𝔸)D_{q}^{2} + S^{2}(𝔸)D_{q}^{2} − S^{3}(𝔸)D_{q}^{3} + ⋯ (21)

Comme D_{q}(x^{n}) = [n] x^{n−1}, avec [n] := 1 + q + ⋯ + q^{n−1}, on est amené à chercher des polynômes P_{n}^{q} tels que

Q(P_{n}^{q}) = [n]P_{n−1}^{q} & P_{n}^{q}(0) = 0 , n ≥ 1 .  (22)

Il faut en fait remplacer la relation P_{n} = xλ_{D}(n𝔸)x^{n−1} par une équivalente pour pouvoir la q-ifier, et l’on trouve

P_{n}^{q} = (1 + ∑(n − |J|)\frac{(n − 1) ⋯ (n − ℓ(J) + 1)}{∏ m_{i}!}Λ^{J}(𝔸) D_{q}^{|J|}) x^{n} , (23)

somme sur toutes les partitions J ≠ 0, J = 1^{m_{1}}2^{m_{2}}3^{m_{3}} ⋯, ℓ(J) = m_{1} +m_{2} + ⋯, |J| = m_{1} + 2m_{2} + 3m_{3} + ⋯, et Λ^{J} := (Λ^{1})^{m_{1}}(Λ^{2})^{m_{2}}(Λ^{3})^{m_{3}} · · ·.

Les q-entiers n’apparaissent donc que dans l’action de D_{q} et pas dans les coefficients des puissances de D_{q}. Comme on obtient P_{n}^{q} à partir de x^{n} et pas de x^{n−1}, la formule (23) ne découle pas instantanément de (9). Pour des extensions du calcul ombral, voir [12].

Il me faut maintenant justifier que l’addition ou la multiplication par les entiers ne couvre pas toutes les mathématiques. Il est nécessaire en effet de faire appel à la multiplication par les rationnels, ou même les nombres complexes.

En d’autres termes, on a rencontré le doublement des alphabets 𝔸 = {a} ↦ 2𝔸 := {a′} ∪ {a′′}, mais on réclame l’opération inverse :

𝔸 ↦ \frac{1}{2}𝔸 = 𝔹 , 𝔹 = \{b\} ↦ \{b′\} ∪ \{b′′\} = 𝔸 .

Si l’on veut bien voir qu’au niveau des sommes de puissance :

ψ_{i}(2𝔸) = ∑(a′)^{i} + ∑(a′′)^{i} = 2ψ_{i}(𝔸) ,

on comprend que B = k 𝔸, k ∈ ℂ puisse être formellement défini par

ψ_{i}(𝔹) := k ψ_{i}(𝔸) , i ≥ 1 .  (24)

Mais il est plus éclairant de constater que tout polynôme peut jouer le rôle d’alphabet, c’est-à-dire que les ψ_{i} sont des opérateurs sur l’anneau des polynômes ( α ∈ ℂ, u monôme):

P = ∑_{α,u} α u ⇒ ψ_{i}(P) = ∑_{α,u} α u^{i} .  (25)

L’anneau des polynômes symétriques 𝔖ym ayant pour générateurs les ψ_{i}, i = 1, 2, …, les formules (25) font de tout polynôme symétrique un opérateur sur l’anneau des polynômes. Ansi, les fonctions génératrices des opérateurs Λ^{i} et S^{i} sont

P = ∑_{α,u} α u ↦ λ_{z}(P) = ∏(1 + zu)^{α} ,  (26)

P = ∑_{α,u} α u ↦ σ_{z}(P) = ∏(1 − zu)^{−α} .  (27)

Chacune des formules (25) (26), (27), au choix, caractérise la structure de λ-annneau de l’anneau des polynômes. Grothendieck avait choisi les lambda opérations, c’est-à-dire les puissances extérieures Λ^{i} sur les classes de fibrés vectoriels, les S^{i} étant les puissances symétriques. Les topologues algébristes préfèrent quant à eux les opérations d’Adams ψ_{i} (voir en annexe quelques remarques sur les λ-anneaux).

Remarquons le rôle différent joué par les constantes α et les monômes u:

\begin{cases}ψ_{i}(α) = α , & S^{i}(α) = \binom{α+i−1}{i} , & Λ^{i}(α) = \binom{α}{i} \\ ψ_{i}(u) = u^{i} , & S^{i}(u) = u^{i} , & Λ^{i}(u) = 0, i > 1, & Λ^{1}(u) = u \end{cases}  (28)

Un système de calcul formel ne peut distinguer, sans aide, des coefficients indéterminés α de variables u. Il est plus correct de caractériser les “monômes” comme les élements de rang 1 (i.e. les x ≠ 0 tels que Λ^{i}(x) = 0 ∀i > 1), et les “constantes” α comme les élements invariants par les ψ_{i} (Rota [17] disait plutôt élément de type binomial).

Il est approprié de ne pas se cantonner aux polynômes, mais de prendre plutôt des fonctions rationnelles, ou des séries formelles, en gardant comme définition

ψ_{i} (\frac{∑ αu}{∑ βv}) = \frac{∑ αu^{i}}{∑ βv^{i}} ,  (29)

les sommations étant finies ou non.

Avec un peu de précaution, on peut aussi utiliser des ”monômes de Laurent” d’exposants dans ℤ au lieu de ℕ.

Si q est de rang 1, on peut maintenant écrire \frac{1}{1−q} = 1 + q + q^{2} + ⋯, c’est-à-dire \frac{1}{1−q} est l’alphabet infini \{1, q, q^{2}, … \} et ψ_{i}(\frac{1}{1−q}) = \frac{1}{1−q^{i}}, i ≥ 1. Incidemment, Cauchy nous apprend que :

S_{i}(1/(1 − q)) = 1/(1 − q) ⋯ (1 − q^{i})  (30)

et donc

σ_{x}(1/(1 − q)) = ∑ x^{i}/(1 − q) ⋯ (1 − q^{i})  (31)

est la q-exponentielle, l’égalité 1/1 − q = 1 + q + q^{2} + ⋯ se traduisant par la factorisation

σ_{x}(1/1 − q) = ∏_{i=1}^{∞} 1/(1 − xq^{i})  (32)

qui fait de la q-exponentielle un objet souvent plus simple à manipuler que l’exponentielle proprement dite [18].

En combinant des éléments de type différent d’un λ-anneau, on code par le signe “+” des développements très variés. Soit par exemple x de type binomial, q de rang 1 et y tel que y(1 − q) soit de rang 1. On définit les q-polynômes de Charlier par :

Ch_{n}(x) := n! Λ^{n}(x − y) .  (33)

Pour avoir leur expression explicite, il est préférable d’introduire z := y(1−q). On alors

Λ^{n}(x − \frac{z}{1 − q}) = ∑ Λ^{n−i}(x)Λ^{i}(\frac{−z}{1 − q}) = ∑ Λ^{n−i}(x)(−z)^{i}S^{i}(\frac{1}{1 − q})

Ch_{n}(x) = n! ∑ \frac{x ⋯ (x − n + i + 1)}{(n − i)!} \frac{(−y)^{i}(1 − q)^{i}}{(1 − q) ⋯ (1 − q^{i})} ,  (34)

en combinant (3), (28), (30). Pour y = 1, q → 1, on retrouve bien les polynômes classiques (Rota [13], p.64).

Nous pouvons maintenant revenir au calcul ombral, en ayant présent à l’esprit qu’il y a plusieurs relèvements possibles pour a_{i}:

a_{i} ↦ S_{i}(𝔸) , a_{i} ↦ ψ_{i}(𝔸) , a_{i} ↦ i!S_{i}(𝔸) , …

C’est là où il faut faire preuve de discernement, et/ou disposer d’un outil qui permette l’expérimentation comme ACE [1] et sa librairie SFA [10] consacrée aux λ-anneaux.

Prenons par exemple l’identité

exp(bx) = ∑ \frac{b(ak + b)^{k−1}}{k!} (x exp(−ax))^{k} ,  (35)

que Riordan [11] donne comme application de l’inversion de Lagrange. Comment l’interpréter dans un λ-anneau ? On peut introduire deux alphabets 𝔸, 𝔹, remplacer exp(ax) par σ_{x}(𝔸), exp(bx) par σ_{x}(𝔹) et chercher les coefficients c_{k} du développment

σ_{x}(𝔹) = ∑ c_{k}(\frac{x}{σ_{x}(𝔸)})^{k} = ∑ c_{k}x^{k} λ_{−x}(k𝔸) .  (36)

Les premiers termes sont

1 + xS^{1}(𝔹) + x^{2}S^{2}(𝔹) + ⋯ = 1 + xS^{1}(𝔹)λ_{−x}(𝔸) + x^{2}(S^{2}(𝔹) + S^{1}(𝔹)S^{1}(𝔸))

λ_{−x}(2𝔸)+x^{3}(S^{3}(𝔹)+2S^{2}(𝔹)S^{1}(𝔸)+2S^{1}(𝔹)S^{2}(𝔸)+S^{1}(𝔹)S_{11}(𝔸))λ_{−x}(3𝔸)+⋯

On voit que les c_{k} sont linéaires en les S_{i}(𝔹) ce qui permet de se retreindre à un alphabet 𝔹 := b de cardinal 1. Par homogénéité, on peut même poser b = 1. On veut donc résoudre

\frac{1}{1 − x} = ∑ c_{k}x^{k} λ_{−x}(k𝔸)

i.e.

1 = (1 − x) ∑ c_{k}x^{k} λ_{−x}(k𝔸) = ∑ c_{k}x^{k} λ_{−x}(k𝔸 + 1)

système dont la solution combine addition et multiplication par un entier:

c_{k} = \frac{1}{k}S^{k−1}(k𝔸 + 2) , k ≥ 1 .  (37)

Par exemple, c_{3} = \frac{1}{3}S_{2}(2𝔸+2) = 2S^{2}(𝔸)+S_{11}(𝔸)+2S^{1}(𝔸)+1 et, en revenant à une expression homogène de degré 3

c_{3} = 2S^{2}(𝔸)S^{1}(𝔹) + S_{11}(𝔸)S^{1}(𝔹) + 2S^{1}(𝔸)S^{2}(𝔹) + S^{3}(𝔹) .

L’identité de Riordan se retrouve dans la spécialisation S^{i}(𝔸) = a^{i}/i!, S^{i}(𝔹) = b^{i}/i!, car alors :

c_{3} ↦ 2\frac{a^{2}}{2} \frac{b}{1} + \frac{a^{2}}{2} \frac{b}{1} + 2\frac{a}{1} \frac{b^{2}}{2} + \frac{b^{3}}{3!} = \frac{b(3a + b)^{2}}{3!} .

On peut méditer sur le fait que la généralisation de l’identité de Riordan se prouve en remplaçant exp(−bx) par 1 − bx, ombre qui paraît bien chétive pour abriter l’exponentielle, qu’elle repose sur le seul usage de la formule (25) et qu’elle fait surgir de nihilo l’entier 2 .

Nous pourrions multiplier les exemples classiques qui se décodent en multiples entiers d’alphabets (voir en particulier l’article de Brenti [2]). Les quarts d’alphabets promis par le titre de cet exposé se rencontrent plus difficilement dans la nature et je terminerai sur un seul exemple, celui des polynômes de Jack J_{k}^{α} indicés par les partitions de longueur 1 [8]. En effet leur fonction génératrice est :

∑ \frac{z^{k}}{a^{k}k!}J_{k}^{α}(x_{1}, …, x_{n}) = ∏(1 − zx_{i})^{− \frac{1}{α}} = σ_{z}(\frac{1}{α}X) ,  (38)

la dernière écriture supposant que les x_{i} soient des éléments de rang 1 de somme X. Un exemple de calculs utilisant les techniques de λ-anneaux pour produire des identités liées aux polynômes de Jack se trouve dans [5].

Quand les λ-anneaux seront enseignés dans les lycées et collèges, je n’aurai pas de mal à allonger la liste d’exemples.

Formule de Cauchy

L’espace des fonctions symétriques 𝔖ym en des indéterminées x_{1}, …, x_{n} est étudié depuis fort longtemps. Newton a montré que cet espace est un espace de polynômes en les variables Λ^{1}, …, Λ^{n}, ou ψ_{1}, …, ψ_{n}. La majorité des problèmes classiques se réduisaient à des changements de base de 𝔖ym (en tant qu’espace vectoriel).

A la suite de Kostka, on a compris qu’il existait un produit scalaire canonique, pour lequel les fonctions de Schur sont une base orthonormée, les sommes de puissance, une base orthogonale, les fonctions monomiales, la base adjointe des produits de fonctions complètes, etc. Tous ces énoncés se résument en l’existence d’un noyau de Cauchy

K(X, Y) := ∏_{i,j} \frac{1}{1 − x_{i}y_{j}}

(introduisant un deuxième ensemble d’indéterminées y_{1}, …, y_{n} que l’on peut supposer de même cardinal). Ce noyau définit le produit scalaire, en ce sens que tout développement “séparant les variables”

K(X, Y) = ∑ U_{J}(X)V_{J}(Y)

fournit un couple de bases adjointes {U_{J}}, {V_{J}} de 𝔖ym relativement à ce produit scalaire.

Les développements

K(X, Y) = ∏_{i} ∑_{k} y_{i}^{k}S^{k}(X) & K(X, Y) = ∏_{i,j} (1 + x_{i}y_{j} + (x_{i}y_{j})^{2} + ⋯)

montrent que la base monomiale est adjointe de la base des produits de fonctions complètes, et que la base des sommes de puissance est orthogonale. La diagonalisation de K(X, Y) dans la base des fonctions de Schur est moins immédiate. On la déduit du théorème de Binet-Cauchy exprimant les mineurs d’un produit de deux matrices en fonction de ceux de chacune d’entre elles (cf. [8]), la matrice [\frac{1}{1−x_{i}y_{j}} ] factorisant en deux matrices de Vandermonde.

Ces trois développements, combinés à l’involution X ↦ −X et la symétrie X ↔ Y donnent par spécialisation de Y en l’entier i + k les formules (6a), …, (6e).

Déformant le noyau de Cauchy en introduisant un ou deux paramètres, on peut ainsi généraliser les fonctions de Schur en les polynômes de Hall-Littlewood ou les polynômes de Macdonald. Cependant ces polynômes forment une base orthonormée et non orthogonale, ce qui nécessite d’introduire des conditions supplémentaires pour les caractériser (contrairement aux fonctions de Schur qui sont la seule base orthonormale de 𝔖ym sur ℤ).

λ-anneaux

Les λ-anneaux sont des anneaux munis d’opérateurs λ^{i}, i ∈ ℕ, satisfaisant trois axiomes exprimant leur compatibilité avec les opérations de l’anneau (cf. [4]) : l’addition : λ^{i}(x + y), la multiplication λ^{i}(xy), le troisième axiome énonçant une propriété d’universalité de la composition x ↦ λ^{i}(λ^{j}(x)) (que les combinatoristes ont appelée plethysm(e).

Au lieu de prendre les λ^{i}, on peut utiliser les S^{i} définis par S^{i}(x) := (−1)^{i} λ^{i}(−x), ou les ψ_{k} définis par la fonction génératrice (4) (en remplaçant A par x).

Pour ce qui est des calculs explicites, notre connaissance du plethysme est à l’heure actuelle trop sommaire pour que l’on puisse en faire grand usage. Il ne reste que l’addition (c’est un avatar de la formule de Chu-Vandermonde)

S^{k}(x + y) = ∑_{i+j=k} S^{i}(x)S^{j}(y)

et la multiplication, qui est explicitée par la formule de Cauchy

S^{k}(xy) = ∑_{J:|J|=k} S_{J}(x)S_{J}(y)

(en définissant les S_{J}(x) comme des déterminants en les S^{j}(x)).

On peut donc dire que la formule de Cauchy engendre la majorité des identités en théorie des λ-anneaux, tout comme en théorie classique des fonctions symétriques.

Nous nous sommes restreints à l’anneau des polynômes, ce qui rend l’axiomatique plus simple. Les objets de base sont en effet les monômes u et les scalaires α (ici, les éléments de ℂ). Les trois axiomes se condensent alors en les formules (25), pour k > 0,

ψ_{k} (∑ α u) = ∑ α u^{k} .

Par contre, dans un λ-anneau général, on aura d’autres éléments que les “polynômes”.

Polynômes de Schubert

Ces polynômes généralisent les fonctions de Schur et constituent une base linéaire de l’anneau des polynômes en x_{1}, x_{2}, …, stable par différences divisées. Leur combinatoire fait appel aux permutations, plutôt qu’aux partitions.

Pour tout i on définit à la suite de Newton la i-ème différence divisée ∂_{i} comme l’opérateur (noté à droite)

f ∂_{i} = \frac{f(… x_{i}, x_{i+1} …) − f(… x_{i+1}, x_{i} …)}{x_{i} − x_{i+1}}

Pour tout k, tout ν := [ν_{1}, …, ν_{k}], ν_{1} ≥ ⋯ ≥ ν_{k} ≥ 0, on pose

Y_{ν} := x^{ν}

et l’on définit récursivement les polynômes de Schubert par

Y_{J} ∂_{i} = Y_{[... ,j_{i+1},j_{i}−1,...]} si j_{i} > j_{i+1}  (39)

(comme ∂_{i}^{2} = 0, on a nécessairement Y_{J} ∂_{i} = 0 si j_{i} ≤ j_{i+1}). En d’autres termes les polynômes de Schubert sont toutes les images par itération de différences divisées des monômes dominants.

Lorsque J est du type j_{1} ≤ j_{2} ≤ ⋯ ≤ j_{n}, j_{n+1} = 0 = j_{n+2} = ⋯, alors Y_{J} est égal à la fonction de Schur d’indice [j_{1}, …, j_{n}] en les variables x_{1}, …, x_{n}. Les déterminants binomiaux s’obtiennent à partir des fonctions de Schur, en utilisant répétivement la règle (39).

Ainsi

Y_{2345} ⟶^{∂_{4}∂_{5}} Y_{234003} ⟶^{∂_{3}} Y_{230303}

Y_{1234} ⟶^{∂_{4}∂_{5}} Y_{123002} ⟶^{∂_{3}} Y_{120202}

Les techniques de différences divisées remplacent ainsi les manipulations de déterminants, et fournissent des identités sur les déterminants binomiaux qui sont des spécialisations x_{i} = 1, i = 1, 2, … de polynômes de Schubert, en particulier pour ceux exprimant les nombres de Bernoulli. Gessel et Viennot [3] utilisent quant à eux une combinatoire de chemins pour étudier ces déterminants.

Comme pour les fonctions symétriques, la théorie peut se condenser en l’existence d’un noyau de Cauchy

K_{n}(X, Y) := ∏_{i,j: i+j≤n}(x_{i} − y_{j})

qui généralise en fait le résultant ∏_{i,j}(x_{i} − y_{j}) (lequel est diagonal dans la base Schur).

Notons qu’il est équivalent de considérer ∏_{i,j}(x_{i}−y_{j}) ou ∏_{i,j} 1/(1−x_{i}y_{j}). Par contre, la fonction ∏_{i,j: i+j≤n} 1/(1 − x_{i}y_{j}) fait intervenir les polynômes clefs (associés aux différences divisées isobares) et non les polynômes de Schubert.

References

[1] ACE, S. Veigneau. an Algebraic Environment for the Computer algebra

   system MAPLE, http://phalanstere.univ-mlv.fr/∼ace (1998).

[2] F. Brenti. A class of q-symmetric functions arsing from plethysm, prépublication (1999).

[3] I. Gessel, X. Viennot, Binomial determinants, paths and hook length formulae, Advances in M. 58 (1985) 300–321.

[4] D. Knutson. λ-rings and the representation theory of the symmetric group, Lecture Notes in Mathematics 308, Springer (1973).

[5] A. Lascoux, M. Lassalle. Une identité remarquable en théorie des partitions, Math. Annal. à paraître

[6] A. Lascoux & M.P. Schützenberger. Polynômes de Schubert, Comptes Rendus 294 (1982) 447.

[7] A. Lascoux & M. P. Schützenberger. Formulaire raisonné de fonctions symétriques, Université Paris 7 (1985).

[8] I.G. Macdonald. Symmetric functions and Hall polynomials, Clarendon Press, second edition, Oxford, 1995.

[9] V. Prosper. Combinatoire des polynômes multivariés, thèse, Université de Marne la Vallée (1999)

   http://schubert.univ-mlv.fr/∼vince/vpthesis.html

[10] V. Prosper. SFA, a package on symmetric functions ... for Maple, J. of Symb. Comp. 29 (2000) 83–94.

[11] J. Riordan. Combinatorial identities, Wiley (1968).

[12] S. Roman. More on the umbral calculus, with emphasis on the q-umbral calculus J. Math. Anal. Appl. 107 (1985) 222–254.

[13] Gian-Carlo Rota. Finite Operator Calculus, Academic Press (1975).

[14] Gian-Carlo Rota. Foundations I. Theory of Moebius functions, Zeit. für Wahr. 2 (1964) 340–368.

[15] Gian-Carlo Rota. The number of partitions of a set, Am. Math. M. 71 (1964) 498–504.

[16] Gian-Carlo Rota. Baxter algebras and combinatorial identities I,II, Bull. A.M.S. 75 (1969) 325–334.

[17] R. Mullin, G-C Rota. Foundations III. Theory of binomial enumeration, Graph Theory and its Applications, B.Harris ed., Academic Press (1970) 167-213.

[18] J. Goldman, G-C Rota. Foundations IV. Finite vector spaces and Eulerian generating functions, Studies in Appl. Math. 49 (1970) 239–258.

[19] Gian-Carlo Rota. Hopf Algebra methods in combinatorics, Colloques internationaux C.N.R.S, Orsay (1976) 363–365.

[20] S.A. Joni, G-C Rota. Coalgebras and bialgebras in combinatorics, Stud. in Appl. Math. 61 (1979) 93-139.

[21] J.P. Kung, G-C Rota. The invariant theory of binary forms, Bull. AMS 10 (1984) 27–85.

[22] W.Y.C. Chen, G-C Rota. q-analogs of the inclusion-exclusion principle and permutations with restricted position, Discr. Math. 104 (1992) 7–22.

[23] G-C Rota. Report on the present state of combinatorics, Discr. Math. 153 (1996) 289–303.

[24] I. Schur. Bermerkungen sur Theorie der beschränkten Bilinearformen ... , Journal für die reine ... 140 (1911) 1–28.