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).

# Very Important

This article is accompanied by the following Maple and Mathematica files. [More accurately, the article is a human commentary on the much more important computer files below].
• The Maple file Guessel1 that has the annihilating operator described in the paper, and the input to the checking procedure, bdok(n), is numeric n, and that verifies that Gessel's expression does indeed satisfy it numerically for n from 0 to 205. Note that this is already a rigorous proof, since the calculation boils down to proving that a certain polynomial of degree ≤ 205 is identically zero. To use it, download it into a directory, and type (in Linux)
maple -q < Guessel1
and you should get the following output
• The Maple file Guessel2 that has the annihilating operator described in the paper, and the checking procedure, bdok1(n); now takes symbolic input. It verifies, this time symbolically, that Gessel's expression does indeed satisfy it (for symbolic n, and hence, in particular for all integer n). To run it, download it into a directory, and type
maple -q < Guessel2
and you should get the following output.
• There is still one minor technicality. The homog. linear recurrence equation, of order 32, may, a priori, be "singular", i.e. have positive integer roots. In that case, we would have to check more than the first 32 initial values. If K is the largest positive integer root of the coeff. of f(n+32) in the recurrence equation, let's call it P0(n), then we would have to check the first max(32,32+K) initial values. Fortunately, when Maple factors P0(n) you only get factors of the form (an+b), with a and b positive integers, as well as other higher-degree factors. So K=-infinity, and 32 initial values suffice. Here is the Maple file, GuesselP0, that factors the leading coeff. P0(n). To run it, download it into a directory, and type
maple -q < GuesselP0
and you should get the following output.
• But how did we come up with this order-32, degree-172, linear-recurrence-with-polynomial-coefficients annihilating operator Monster? We could have easily cheated and cooked it up by taking the minimal operator of order 2, satisfied by the conjectured expression, and left-multiplied it by a random monstrous order-30 operator with gigantic coefficients, and pretented that it came out from our non-commutative Groebner bases program. For those who have any suspicion, here is Christoph Koutschan's Mathematica Notebook, that describes all the needed steps, and that would enable the skeptic (and patient!) reader to check all the steps.
• Finally, the set of 16 annihilating operators that formed the basis for the elimination described in the article is given right here.
Doron Zeilberger's List of Papers