Accueil du site > Actualité de la recherche > Actualités scientifiques




Recherchez sur ce site


La conjecture de Gessel en combinatoire énumérative

6 mars 2016

La conjecture de Gessel a une place à part dans la zoologie des formules closes combinatoires. Retour sur la théorie générale des marches dans des cônes et l’histoire de cette conjecture, occasion d’un duel entre homme et machine !

Cette note a plusieurs ambitions : montrer d’abord que la conjecture de Gessel est singulière dans la zoologie des formules closes combinatoires ; esquisser aussi la théorie générale des marches dans des cônes, dont il s’agit là d’un cas particulier ; enfin retracer l’histoire de cette conjecture, qui a mis en concurrence plusieurs approches, et notamment un avatar du duel entre homme et machine. On pourra consulter [3] pour une version longue de cette note.

Une conjecture aux multiples facettes

Dans le réseau \mathbb Z^2, combien compte-t-on de chemins de longueur n empruntant les pas Nord, Sud, Est et Ouest, partant et revenant en l’origine, tout en restant dans le cône \{(i,j)\in\mathbb Z^2: j\geq 0,i+j\geq 0\} (voir Figures 1 et 2) ?

Si n est impair, il n’y en a pas, assurément ! En effet, la somme i+j des coordonnées d’un chemin possède la même parité que sa longueur. Lorsque n=2m est pair, le combinatoricien américain Ira Gessel conjecture en 2000 la formule


16^{m} \frac{(5/6)_{m} (1/2)_{m}}{(2)_{m} (5/3)_{m}}, \quad (1)

(a)_{m}=a(a+1)\cdots (a+m-1) désigne la factorielle croissante. Que l’on énumère exhaustivement ces excursions ou que l’on applique la formule (1), on aboutit aux nombres

1, 2, 11, 85, 782, 8004, 88044,...

pour les petites valeurs de m. En 2000 cette suite est inconnue, même dans la gigantesque encyclopédie en ligne des suites de nombres entiers.

Cette conjecture a tout pour plaire ! D’abord elle est simple à formuler. Ensuite, elle concerne un objet simple (la marche dite simple, avec déplacements aux points cardinaux). D’autre part, derrière le cas particulier de Gessel se dressent tous les modèles de marches dans un quart de plan (notre modèle en est un, après transformation linéaire des coordonnées comme sur la Figure 2), populaires en combinatoire, par le fait qu’ils sont en bijection avec de nombreux objets (tableaux de Young, arbres, permutations). Enfin, on peut avoir sur la marche (aléatoire) simple de multiples points de vue, venant des probabilités, de la combinatoire, de la théorie des représentations, du calcul formel, fournissant autant d’angles d’attaques possibles.

gessel

FIGURE 1. À gauche : une excursion de longueur 10 dans le plan qui ne reste pas dans le domaine ; à droite, l’une des 85 excursions de longueur 8 de Gessel.

steps gessel

FIGURE 2. La marche de Gessel peut indifféremment être vue comme une marche dans le cône d’ouverture 3\pi/4 ou dans le quart de plan.

Combinatoire vs. calcul formel

À l’attaque donc ! Mireille Bousquet-Mélou et Marni Mishna développent une approche pionnière et systématique [5] pour les marches dans un quart de plan. L’idée principale est d’exploiter une équation fonctionnelle (dite à noyau) pour la série génératrice


Q(x,y;t) = \sum_{i,j,n\geq 0}q(i,j;n) x^{i}y^{j}t^{n} 
\quad (2)

des nombres q(i,j;n) définis comme le nombre de chemins de \mathbb N^2 longs de n pas, ralliant (0,0) à (i,j), et d’appliquer un raffinement algébrique du principe de réflexion (concept bien connu et fructueux en probabilités comme en combinatoire). Dans le cas de Gessel, le noyau vaut


xy+\frac{1}{xy}+x+\frac{1}{x}-\frac{1}{t}. 
\quad (3)

La partie polynomiale en x et y inventorie les sauts, voir à droite sur la Figure 2, tandis que la variable t mesure la longueur. Le modèle de Gessel échappe pourtant à la théorie de [5], pour des raisons mystérieuses.

Parallèlement, la communauté du calcul formel s’est emparée du problème. Il est facile de générer des termes (on peut toujours compter), et de ce fait d’obtenir des développements en série tronqués. On voudrait alors appliquer une procédure du type "deviner et prouver", mais pour Gessel les calculs dépassent la capacité des ordinateurs. C’est finalement une variation subtile de cette approche qui en 2009 donne le jour à la première démonstration, et la conjecture devient le théorème de Kauers, Koutschan et Zeilberger [6].

Au cours de la preuve les auteurs manipulent une récurrence linéaire qui, reproduite sur du papier, noircirait environ 250 pages ! Croyant une preuve courte et purement mathématique hors de portée, Doron Zeilberger promet 100 dollars US à quiconque prouverait la formule hypergéométrique (1) sans ordinateur et en moins de cinq pages [6].

La décennie qui sépare l’énoncé et la preuve de cette formule a été témoin de recherches fournies : on peut mentionner un deuxième tour de force algorithmique [1], démontrant que la fonction (2) de trois variables est algébrique (cette structure simple fut incontestablement une surprise dans notre communauté) ; on pense encore à une approche analytique, consistant à réduire l’équation fonctionnelle à un problème frontière de type Riemann-Hilbert, partant de quoi des formules intégrales complexes de (2) sont prouvées [7].

Humain, trop humain

La preuve humaine présentée dans [2] prend résolument le parti de l’analyse complexe, et utilise le noyau (3) de l’équation fonctionnelle pour sa structure complexe, celle d’une surface de Riemann de genre 1 :


\{(x,y)\in{\bf C}^2 :xy+\frac{1}{xy}+x+\frac{1}{x}-\frac{1}{t}=0\}.

La théorie des fonctions elliptiques et sa myriade d’identités jettent alors une lumière particulière sur ce modèle, et permettent in fine de le résoudre. Cette démonstration [2] présente l’avantage de traiter le modèle de Gessel comme un autre (pour une fois !).

C’est finalement Mireille Bousquet-Mélou qui l’année dernière [4] répond positivement à Zeilberger (l’article certes comporte plus de 5 pages, mais l’argument - qui marie une compréhension profonde d’une large classe d’équations fonctionnelles à variables catalytiques à une inventivité de chaque ligne, toute spécifique au modèle de Gessel - s’y conforme).

Nouveaux modèles

La communauté combinatoire déjà se tourne vers de nouveaux modèles de marches, avec des grands sauts et en dimension supérieure. Les écueils sont nombreux : pratiques (plus de 11 millions de modèles à petits sauts en dimension 3), techniques (l’analyse complexe, si utile, n’est plus applicable en dimension >2), etc. Nombreux sans doute, mais moins que nos motivations !

Références :

[1] A. Bostan and M. Kauers : The complete generating function for Gessel walks is algebraic. Proc. Amer. Math. Soc. 138 3063-3078 (2010)

[2] A. Bostan, I. Kurkova and K. Raschel : A human proof of Gessel’s lattice path conjecture. Preprint arXiv : 1309.1023 1-28 (2013). A paraître dans Trans. Amer. Math. Soc.

[3] A. Bostan and K. Raschel : Compter les excursions sur un échiquier. Pour la Science 449 40-46 (mars 2015)

[4] M. Bousquet-Mélou : An elementary solution of Gessel’s walks in the quadrant. Preprint arXiv : 1503.08573 1-14 (2015).

[5] M. Bousquet-Mélou and M. Mishna : Walks with small steps in the quarter plane. Contemp. Math. 520 1-40 (2010)

[6] M. Kauers, C. Koutschan and D. Zeilberger : Proof of Ira Gessel’s lattice path conjecture. P. Natl. Acad. Sci. USA 106 11502-11505 (2009)

[7] I. Kurkova and K. Raschel : Explicit expression for the generating function counting Gessel’s walks. Adv. in Appl. Math. 47 414-433 (2011)

Contact : Kilian Raschel | LMPT | UMR 7350 | Pacific Institute for the Mathematical Sciences, 4176-2207 Main Mall, Vancouver, Canada |