.pdf
LaTeX source
[Appeared in Proc Natl Acad Sci USA 106(28):1150211505 (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 squarelattice), 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
[16^{n} (5/6)_{n} (1/2)_{n}]/[(5/3)_{n} (2)_{n}] ,
where (a)_{n}=a(a+1)...(a+n1) .
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 BousquetMé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 computerfree 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 BousquetMé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, 4046 (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 P_{0}(n), then we would have to check the first max(32,32+K) initial values.
Fortunately, when Maple factors P_{0}(n) you only get factors of the form (an+b), with
a and b positive integers, as well as other higherdegree factors. So
K=infinity, and 32 initial values suffice. Here is the Maple file,
GuesselP0,
that factors the leading coeff. P_{0}(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 order32, degree172,
linearrecurrencewithpolynomialcoefficients
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
leftmultiplied it by a random monstrous order30 operator with
gigantic coefficients, and pretented that it came out
from our
noncommutative 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
Doron Zeilberger's Home Page