Proof of Ira Gessel's Lattice Path Conjecture

By Manuel Kauers, Christoph Koutschan, and Doron Zeilberger

.pdf     LaTeX source
[Appeared in Proc Natl Acad Sci USA 106(28):11502-11505 (2009)]

First Written: June 25, 2008. This Version: Nov. 12, 2008.

Last update of this webpage: May 12, 2015.

In a recent article, Manuel Kauers and I tried very hard to prove Ira Gessel's notorious conjecture, that has been circulating in combinatorial enumeration circles for the last seven years, about the number of ways of walking, in the "Manhattan lattice" (2D square-lattice), 2n steps, from the origin back to the origin, using unit steps in the four fundamental directions (north, south, east, and west), all the while staying in x+y ≥ 0, y ≥ 0. Ira Gessel conjectured that it is given by the beautiful expression
[16n (5/6)n (1/2)n]/[(5/3)n (2)n]   , where   (a)n=a(a+1)...(a+n-1)   .
We failed, becuase our computers ran out of memory, even though we felt that a sufficiently large computer would yield to our approach. But then came along the brilliant Christoph Koutschan, and joined the effort, and together with Manuel, was able to complete the task, still using our ideas, but adding to them some very good ones of his own, and this lead to the final solution.

Added Dec. 3, 2009: Read Christoph Koutschan and Manuel Kauers's How Many Roads...? (in German) (p. 17)
Added Dec. 5, 2008: I will talk about this work in an invited talk, entitled "Guesseling" at the Fourth International Conference on Combinatorial Mathematics and Combinatorial Computing. Read the abstract of my talk, and (added Jan. 24, 2009) watch the movie.
Added Nov. 12, 2008: Since we first posted this article, there were two exciting new developments. The first one is the announcement, by Manuel Kauers and Alin Bostan, that the full counting function, F(t;x,y) is in fact algebraic (in all three t,x,y), and consequently holonomic in all three variables. In order to accomplish this feat the used the result implied by the present article that F(t;0,0) is holonomic, plus some new brilliant ideas. They are currently preparing this fascinating article.
The other development is a lovely article by Mireille Bousquet-Mélou and Marni Mishna that presents a systematic approach to counting all classes of walks with steps taken from any subset of the set {E,W,N,S,NE,NW,SE,SW}, that can handle all cases EXCEPT one, the present case of Gessel walks. So Gessel walks are really special, they are "one in a million" (well, even better, "one in a hundred million" (alas, in base 2)).
Added July 3, 2008: Of course the scope of our method is much larger, and should be usable for many other families of walks, except that one should not expect such "nice" answers. Even staying within the Gessel walks, but looking at the number of walks for points terminating at other points (near the origin), Marko Petkovskek and Herb Wilf found analogous conjectures, and Christoph Koutshan's amazing program found the proving operator for one of them (F(2n+1,1,0)). [addition (Nov. 11, 2008) to this addition: Christoph's program can also do all the other conjectures of Petkovsek and Wilf, including finding a recurrence for f(n;2,0), refuting their conjecture that there is no such recurrence.]
Added Sept. 7, 2013: To my great disappointment, humankind met the challenge of having a computer-free proof (at least in principle). See the (humanly-) beautiful article by Alin Bostan, Irina Kurkova, Kilian Raschel. While they exceeded the required length stipulated in the prize offer, I will nevertheless express my admiration by donating \$100 in their honor, to the OEIS foundation.
Added May 12, 2015: I apparently forgot my promise to donate to the OEIS in their honor, but meanwhile Mireille Bousquet-Mélou came even closer, and I donated \$100 dollars in her honor. It is hereby also in honor of Bostan, Kurkova, and Raschel. Mireille was probably inspired by a beautiful "popular" article by Alin Bostan and Kilian Raschel, entitled "Compter les excursions sur un échiquier", published in Pour La Science #449, 40-46 (2015).