# Proof of Ira Gessel's lattice path conjecture

## Abstract

We present a computer-aided, yet fully rigorous, proof of Ira Gessel's tantalizingly simply stated conjecture that the number of ways of walking 2

*n*steps in the region*x*+*y*≥ 0,*y*≥ 0 of the square lattice with unit steps in the east, west, north, and south directions, that start and end at the origin, equals ${16}^{n}\frac{{(5/6)}_{n}{(1/2)}_{n}}{{(5/3)}_{n}{(2)}_{n}}$.### Sign up for PNAS alerts.

Get alerts for new articles, or get an alert when an article is cited.

There is a certain family of lattice walks, let us call them the Gessel walks, whose counting function has already been puzzling the combinatorialists for several years. Gessel walks (that are trivially equivalent to the walks described in the abstract) are walks in the lattice ℤWe would call this power series holonomic (with respect to

^{2}that stay entirely in the first quadrant (namely, they are walks in ℕ^{2}) and that only consist of steps chosen from*G*:= {←,→,↙,↗}. If*f*(*n*;*i*,*j*) denotes the number of Gessel walks with exactly*n*steps starting at the origin (0,0) and ending at the point (*i*,*j*), then the counting function is the multivariate power series*t*) if it satisfies an ordinary linear differential equation (with respect to*t*) with polynomial coefficients in*t*,*x*,*y*. This, a priori, may or may not be the case.For example, the Kreweras walks are defined just like the Gessel walks, but with the steps chosen from {←,↓,↗} instead of from

*G*. It is a classical result (1) that their counting function is holonomic. In contrast, Bousquet-Mélou and Petkovšek showed that the counting function for certain Knight walks is not holonomic (2). Mishna (3) provides a systematic study of all the possible walks in the quarter plane with steps chosen from any step set*S*⊆ {←,↖,↑,↗,→,↘,↓,↙} with |*S*| = 3. She shows that the counting functions for the step sets {↗,↘,↖} and {↗,↘,↑} (and some others that are equivalent to those by symmetry) are not holonomic while all others are holonomic.For the number of walks returning to the origin, there is sometimes a nice closed form representation, even if there is no such representation for the number of walks to an arbitrary point ((4; A006335) and

*i*,*j*). For instance, if*k*(*n*;*i*,*j*) denotes the number of Kreweras walks of length*n*from (0,0) to (*i*,*j*), then (1)*k*(*n*;0,0) = 0 if*n*is not a multiple of 3.Gessel (personal communication, 2001) observed that a similar representation seems to exist for the number

*f*(*n*;0,0) of Gessel walks returning to the origin (4; A135404). He conjectured the following closed form representation.**Theorem.**

*Let f*(

*n*;

*i*,

*j*)

*denote the number of Gessel walks going in n steps from*(0,0)

*to*(

*i*,

*j*).

*Then f*(

*n*;0,0) = 0

*if n is odd and*

*where*(

*a*)

_{n}:=

*a*(

*a*+ 1)⋯(

*a*+

*n*− 1)

*denotes the Pochhammer symbol*.

The purpose of the present article is to describe, to human beings, the proof of this theorem. The proof is accomplished by computing a homogeneous linear recurrence in

*n*for*f*(*n*;0,0). Then the statement follows directly by verifying that the right-hand side satisfies the same recurrence and that the initial values match. Our recurrence has order 32, polynomial coefficients of degree 172, and involves integers with up to 385 decimal digits. Because this is somewhat too much to be printed here (it would cover ≈250 pages), we provide it electronically at http://www.math.rutgers.edu/˜zeilberg/tokhniot/Guessel2 which has the recurrence as a Maple procedure whose output being 0 proves Gessel's conjecture (once the first 32 initial values are checked, but this has already been done by Gessel himself, when he formulated his conjecture).As variations of Gessel's conjecture, Petkovšek and Wilf (5) have conjectured simple recurrence equations for

*f*(*n*;0,1) and*f*(*n*;1,0) and some others. We were able to prove these conjectures as well, by computing recurrence equations for the respective sequences in the same way as we computed our recurrence equation for*f*(*n*;0,0). We have also found a recurrence for*f*(*n*;2,0), for which Petkovšek and Wilf had conjectured that no recurrence exists.Our result implies that

*F*(*t*;0,0) is holonomic with respect to*t*, but has no immediate implications concerning the holonomy of*F*(*t*;*x*,*y*) for general*x*and*y*.## The Quasi-Holonomic Ansatz

### Annihilating Operators.

Let Those operators belong to a noncommutative polynomial algebra ℚ[

*S*_{n},*S*_{i},*S*_{j}be the shift operators, acting on*f*(*n*;*i*,*j*) in the natural way, e.g.,*S*_{n}*f*(*n*;*i*,*j*) =*f*(*n*+ 1;*i*,*j*). An annihilating operator of*f*(*n*;*i*,*j*) is an operator*R*with*n*,*i*,*j*][*S*_{n},*S*_{i},*S*_{j}], and together they form a left ideal in that algebra, called the*annihilator*of*f*(*n*;*i*,*j*). Later, when it turns out to be computationally more convenient, we will view operators also as elements of the algebra ℚ[*n*,*i*,*j*][*S*_{n},*S*_{i},*S*_{j}], which is hardly more than a technical difference. Note that for sake of simplicity we do not use the cumbersome notation for Ore extensions but refer to the operator algebra with the above somewhat sloppy notation.Our goal is to find an annihilating operator for Gessel's

*f*(*n*;*i*,*j*) that implies the conjecture. For example, it would be sufficient to know an annihilating operator*R*(*n*,*i*,*j*,*S*_{n}) free of the shifts*S*_{i}and*S*_{j}, because then*R*(*n*,0,0,*S*_{n}) would be an annihilating operator for*f*(*n*;0,0).For this reasoning to apply, we could actually be less restrictive and allow also shifts in annihilates

*i*and*j*to occur in*R*, as long as they disappear when*i*and*j*are set to zero. Our goal, therefore, is to find operators*P*,*Q*_{1},*Q*_{2}such that*f*(*n*;*i*,*j*). This is the*quasi-holonomic ansatz*(7).### Discovering Annihilating Operators.

We search for annihilating operators by making, for some fixed with undetermined coefficients which, when equated to zero for any specific choice of

*d*, an ansatz*c*_{e1,…,e6}. Applying this “operator template” to*f*(*n*;*i*,*j*) gives*n*,*i*,*j*yields a linear constraint for the undetermined coefficients. (The*f*(*n*;*i*,*j*) can be computed efficiently for any given*n*,*i*,*j*∈ ℤ.)By taking several different

*n*,*i*,*j*we obtain a linear system of equations. If that system has no solution, then there is definitely no annihilating operator matching the template. If there are solutions, then these are candidates for annihilating operators.We can clearly restrict the search to quasi-holonomic operators by leaving out unwanted terms in the ansatz for

*R*.### Verifying Conjectured Annihilating Operators.

An algorithm was given in ref. 7 for deciding whether some given operator

*R*∈ ℚ[*n*,*i*,*j*][*S*_{n},*S*_{i},*S*_{j}] annihilates*f*(*n*;*i*,*j*) or not. We repeat this algorithm for the sake of self-containedness.First, note that the step set {←, →, ↗, ↙} gives readily rise to the recurrence(certainly annihilates

*n*≥ 0,*i*,*j*∈ ℤ), and therefore the “trivial operator”*f*(*n*;*i*,*j*). Instead of checking that*R*annihilates*f*(*n*;*i*,*j*), we will check that*TR*annihilates*f*(*n*;*i*,*j*). By the following lemma, this is sufficient.**Lemma.**

*Suppose that an operator R is such that*

*Then it can be checked whether Rf*(

*n*;

*i*,

*j*) = 0.

**Proof:**(

*TR*)

*f*(

*n*;

*i*,

*j*) = 0 implies that

*T*annihilates

*Rf*(

*n*;

*i*,

*j*), i.e.,

*Rf*(

*n*;

*i*,

*j*) also satisfies the above recurrence. Therefore, to show that

*Rf*(

*n*;

*i*,

*j*) = 0 entirely, it suffices to show that

*Rf*(

*n*;

*i*,

*j*) = 0 for

*n*= 0 and all

*i*and

*j*. If

*r*

_{n}bounds the degree of

*S*

_{n}in

*R*, then it suffices to verify

*Rf*(

*n*;

*i*,

*j*) = 0 for

*n*= 0 and 0 ≤

*i*,

*j*≤

*r*

_{n}, because we clearly have

*f*(

*n*;

*i*,

*j*) = 0 for

*i*>

*n*or

*j*>

*n*. This leaves us with checking finitely many values, which can be done.

By the lemma, to check If

*Rf*(*n*;*i*,*j*) = 0, it suffices to be able to check (*TR*)*f*(*n*;*i*,*j*) = 0. For checking the latter, compute operators*U*,*V*with*TR*=*UT*+*V*by division with remainder. Then*V*is the zero operator, then we are done, otherwise we proceed recursively to show that*Vf*(*n*;*i*,*j*) = 0 (compute*U*′,*V*′ with*TV*=*U*′*T*+*V*′, observe that (*TV*)*f*(*n*;*i*,*j*) = 0 iff*V*′*f*(*n*;*i*,*j*) = 0, and so on.) As*T*has constant coefficients and, for any*d*> 0, the commutation rules in ℚ[*n*,*i*,*j*][*S*_{n},*S*_{i},*S*_{j}] are such that*S*_{i}*n*^{d}=*n*^{d}*S*_{i},*S*_{j}*n*^{d}=*n*^{d}*S*_{j}and*S*_{n}*n*^{d}=*n*^{d}*S*_{n}+O (*n*^{d−1}) (and similarly for*i*and*j*in place of*n*), it follows that the degree of*V*with respect to*n*,*i*,*j*will be strictly smaller than the degree of*R*with respect to these variables. Therefore, the recursion must eventually come to an end.### Nice Idea, but….

At this point, we know that all we need for proving the conjecture is a quasi-holonomic annihilating operator for

*f*(*n*;*i*,*j*). We know how to search for such operators, and once empirically discovered, we know how to verify them.Unfortunately, it turned out that if a quasi-holonomic annihilating operator for

*f*(*n*;*i*,*j*) exists at all, then it must be quite large. It was shown (7) that there is no such operator of order up to 8 in either direction with polynomial coefficients of total degree at most 6. Increasing the bounds on order and degree further might, of course, help, but this is beyond our current computing capabilities. (For the above assertion, a dense linear system with several thousand variables and equations had to be solved exactly.)## A Takayama-Style Approach

By making an ansatz, we could not find a quasi-holonomic annihilating operator, but we could find (and verify) plenty of other operators, will again be an annihilating operator. This just rephrases the fact that all annihilating operators form a left ideal in the corresponding algebra. Our next step is to find a quasi-holonomic combination of the operators

*R*_{1},*R*_{2},*R*_{3},… that were not of the quasi-holonomic type. Once it has been verified that these*R*_{i}are indeed annihilating operators, we may of course freely choose any operators*P*_{1},*P*_{2},*P*_{3},…, and the combined operator*R*_{1},*R*_{2},*R*_{3},… that were found (and verified) by the method of the previous section.### Takayama's Algorithm.

Assume we want to find a recurrence for the sumIn his “holonomic systems approach” (8) D.Z. proposes to search for an annihilating operator Summing over

*R*of*f*(*n*,*k*) of the form*k*shows (in case of natural boundaries that we will assume in the following) that*P*(*n*,*S*_{n}) annihilates the sum. Starting with the annihilator of the summand*f*(*n*,*k*) in*A*= ℚ(*k*,*n*)[*S*_{n},*S*_{k}], i.e., Ann_{A}*f*⊆*A*, one computes an*R*(*n*,*S*_{n},*S*_{k}) ∈ Ann_{A}*f*free of*k*(e.g., by elimination via Gröbner bases). Any such*R*can be brought to the above form.Almkvist and Zeilberger (9) observed that in the above setting the constraint for

*Q*can be released: The whole proof would go through in the same way if additionally*Q*depends on*k*. This fact is exploited in Takayama's algorithm (10, 11) which originally was formulated only in the context of the Weyl algebra. Chyzak and Salvy (12) extended the algorithm to more general Ore algebras and proposed some improvements (including the shift case that we are dealing with). We follow their version of the algorithm. The idea in short is the following: while in the algorithm above, first*k*was eliminated and then the part (*S*_{k}− 1)*Q*was removed (which corresponds to dividing out the right ideal (*S*_{k}− 1)*A*), the order is now reversed. In Takayama's algorithm we first reduce modulo (*S*_{k}− 1)*A*and then perform the elimination of*k*. The algorithm usually leads to shorter recurrences since we allow more freedom for*Q*. Second, the elimination is in general much faster since we got rid of*Q*from the very beginning. Note that*Q*is not computed at all so we have to assure natural boundaries a priori.There is one technical complication in this approach. The fact that we are computing in a noncommutative algebra restricts us in the computations after having divided out the right ideal (

*S*_{k}− 1)*A*. In particular, we are no longer allowed to multiply by*k*from the left. We can easily convince ourselves that otherwise we would get wrong results: Assume we have written an operator already in the form*P*+ (*S*_{k}− 1)*Q*. Multiplying it by*k*and then reducing it by (*S*_{k}− 1)*A*leads to*kP*−*Q*since we have to rewrite*k*(*S*_{k}− 1) as (*S*_{k}− 1)(*k*− 1) − 1. Because*k*does not commute with*S*_{k}− 1 we get the additional term −*Q*in the result which we lose if we first remove (*S*_{k}− 1)*Q*and then multiply by*k*.In order to find a where for some

*k*-free operator one needs an elimination procedure that takes this complication properly into account. Let*R*_{1},…,*R*_{m}∈*A*be the operators that generate Ann_{A}*f*, and let*R*′_{1},…,*R*′_{m}∈ ℚ(*k*,*n*)[*S*_{n}] be the corresponding reductions modulo (*S*_{k}− 1)*A*. For 1 ≤*i*≤*m*we can write*R*_{i,j}∈*A*′ := ℚ(*n*)[*S*_{n}]. Elimination of*k*now amounts to finding a linear combination*P*_{1},…,*P*_{m}∈*A*′. The vector on the right-hand side corresponds to the desired*k*-free operator. In general, this will not work yet since we can not expect to succeed in the elimination without multiplying by*k*at all. Hence, we also have to include multiples of the*R*_{i}by powers of*k*. More algebraically speaking, the computations take place in an*A*′-module*M*that is generated by the above vectors plus the vectors corresponding to the elements*k*^{j}*R*_{i}mod (*S*_{k}− 1)*A*,1 ≤*i*≤*m*,*j*= 1,2,… . The elimination is achieved by computing a Gröbner basis of this module. Note that*P*∈*M*if and only if there exists a*Q*∈*A*such that*P*+ (*S*_{k}− 1)*Q*∈ Ann_{A}*f*. For practical purposes we have to truncate the module*M*by considering only elements with a finite number*d*of components, i.e., which have zeros in all positions greater than*d*. The most natural choice for*d*is the highest power*k*^{d}that appears in*R*_{1},…,*R*_{m}. But we are not guaranteed that for any*P*,*Q*∈*A*with*P*+ (*S*_{k}− 1)*Q*∈ Ann_{A}*f*the operator*P*is an element of the truncated module. In the unlucky case that no*k*-free operator was found, the bound*d*has to be increased. The algorithm works similar in the case of multiple sums where we want to eliminate several variables*k*_{1},…,*k*_{r}.### Proof of Gessel's Conjecture.

Now back to Gessel's conjecture: Recall that we were looking for a quasi-holonomic operatorwhere we are mainly interested in

*P*, because*Q*_{1}and*Q*_{2}vanish anyway when we set*i*and*j*to 0. This task is very similar to the setting in the previous section, and with slight modifications we can apply Takayama's algorithm to solve it. The only difference is that now*i*and*j*play the role of*S*_{k}− 1, and instead of*k*, we want to eliminate the operators*S*_{i}and*S*_{j}. Consequently we have to consider the ℚ(*n*)[*S*_{n}]-module which is generated by {*S*_{i}^{e1}*S*_{j}^{e2}|*e*_{1},*e*_{2}= 0,1,… }.For our concrete application, we started with a set of 16 annihilating operators for

*f*(*n*;*i*,*j*). These operators were found by the ansatz described in*Discovering Annihilating Operators*and verified as proposed in*Verifying Conjectured Annihilating Operators*. The maximal degree with respect to*S*_{i}as well as the maximal degree with respect to*S*_{j}is 4. Some of the operators had a degree less than 4 in*S*_{i}or*S*_{j}, hence, we had to add their corresponding multiples to the set of annihilating operators (which after this step consisted of 24 elements). Next, we performed the substitution*i*= 0 and*j*= 0. Finally, the elimination of*S*_{i}and*S*_{j}using a Mathematica package for noncommutative Gröbner bases computations written by C.K. took about 30 h and resulted in an operator*P*(*n*,*S*_{n}) of order 32 and polynomial coefficients of degree 172 in*n*. (This is the operator posted on our web site.)As already pointed out, Takayama's algorithm does not deliver

*Q*_{1}and*Q*_{2}. However, in principle the full certificate*R*(*n*,*i*,*j*,*S*_{n},*S*_{i},*S*_{j}) can be computed by doing some book-keeping during the run of the algorithm. But in the case of Gessel's conjecture this extra cost would make our computations not feasible with current computers (we would have to wait for a few, or perhaps even many, more Moore-doublings). We want to emphasize that, nevertheless, the proof is*completely rigorous*.To cite a simple (commutative) analogy, Euclid devised, more than 2,300 years ago, an algorithm to find the greatest common divisor of two integers. Later mathematicians extended it to the generalized Euclidean algorithm that inputs integers

*m*and*n*and outputs not only*d*, the greatest common divisor of*m*and*n*, but also two other integers*a*and*b*such that*am*+*bn*=*d*. Just because our computers are not fast or big enough to actually find these two other integers*a*and*b*does not detract from the correctness of the output*d*of the original Euclidean algorithm, and their existence is implied by it.## Conclusion

Computer-aided proofs have come a long way since the hostile reception of the Appel–Haken landmark proof of the Four-Color Conjecture. Even as recently as 1998, Hales' breakthrough computer-aided proof of Kepler's conjecture was met with skepticism, but it did get published, with some reservations, in the prestigious journal

*Annals of Mathematics.*Both the Appel–Haken and Hales theorems are examples of extremely simply stated statements, whose proofs have defied, so far, human attempts. Although Ira Gessel's conjecture has neither the longevity nor the notoriety of the above theorems, it does belong to that genre, and we believe that it is very possible that a short human proof does not exist. Unfortunately, formally proving this last meta-conjecture would probably be much more difficult than proving Gessel's conjecture, since proving realistic lower bounds is a notoriously difficult task. So, we have to resort to empirical sociological testing, using the ingrained greed of human mathematicians. To that end, D.Z. offers a prize of one hundred (100) US dollars for a short, self-contained, human-generated (and computer-free) proof of Gessel's conjecture, not to exceed five standard pages typed in standard font. The longer that prize would remain unclaimed, the more (empirical) evidence we would have that a proof of Gessel's conjecture is indeed beyond the scope of humankind.### Note.

Meanwhile Bostan and Kauers have shown that the general series

*F*(*t*;*x*,*y*) is in fact algebraic, and thus, in particular, holonomic. Their proof uses as a prerequisite the holonomy of*F*(*t*;0,0) proven below, in addition to computer algebra techniques, which are different from those used below for establishing the holonomy of*F*(*t*;0,0) (a brief discussion of their work is available at http://www-lipn.univ-paris13.fr/actualites/post/The-full-counting-function-of-Gessel-walks-is-algebraic). Shortly after that, Bousquet-Melou and Mishna (6) announced a complete classification of all of the 256 step sets. With a uniform technique they are able to determine the nature of all step sets, with one single but remarkable exception: Gessel's. This fact reveals evidence that the problem of enumerating Gessel walks is*sui generis*within the class of lattice path problems and hence deserves special attention.## Acknowledgments.

M.K. and C.K. were supported in part by the Austrian Fonds zur Wissenschaftlichen Förderung Grants P19462-N18 and P20162-N18. D.Z. was supported in part by the National Science Foundation.

## References

1

G Kreweras, Sur une classe de problmes lis au treillis des partitions d'entiers.

*Cah BURO***6**, 5–105 (1965).2

M Bousquet-Mélou, M Petkovšek, Linear recurrences with constant coefficients: the multivariate case.

*Discr Math***225**, 51–75 (2000).3

M Mishna, Classifying lattice walks restricted to the quarter plane.

*Proceedings of the Nineteenth International Conference on Formal Power Series and Algebraic Combinatorics*, (FPSAC), Tianjin, China, arXiv:math/0611651v1. (2007).4

NJA Sloane

*The On-Line Encyclopedia of Integer Sequences*, http://research.att.com/~njas/sequences/.5

M Petkovšek, HS Wilf, On a conjecture of Gessel., arXiv:0807.3203[math.CO]. (2008).

6

M Bousquet-Mélou, M Mishna, Walks with small steps in the quarter plane., arXiv:0810.4387 [math.CO]. (2008).

7

M Kauers, D Zeilberger, The quasi-holonomic ansatz and restricted lattice walks.

*J Differ Equations Appl***14**, 1119–1126 (2008).8

D Zeilberger, A holonomic systems approach to special function identities.

*J Comput Appl Math***32**, 321–368 (1990).9

G Almkvist, D Zeilberger, The method of differentiating under the integral sign.

*J Symb Comput***11**, 571–591 (1990).10

N Takayama, An algorithm of constructing the integral of a module.

*Proceedings of ISSAC'90*, pp. 206–211 (1990).11

N Takayama, Grbner basis, integration and transcendental functions.

*Proceedings of ISSAC'90*, pp. 152–156 (1990).12

F Chyzak, B Salvy, Non-commutative elimination in Ore algebras proves multivariate identities.

*J Symb Comput***26**, 187–227 (1998).## Information & Authors

### Information

#### Published in

#### Classifications

#### Copyright

© 2009.

#### Submission history

**Received**: June 25, 2008

**Published online**: July 14, 2009

**Published in issue**: July 14, 2009

#### Keywords

#### Acknowledgments

M.K. and C.K. were supported in part by the Austrian Fonds zur Wissenschaftlichen Förderung Grants P19462-N18 and P20162-N18. D.Z. was supported in part by the National Science Foundation.

### Authors

#### Competing Interests

The authors declare no conflict of interest.

## Metrics & Citations

### Metrics

#### Citation statements

#### Altmetrics

### Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

#### Cited by

Loading...

## View Options

### View options

#### PDF format

Download this article as a PDF file

DOWNLOAD PDF### Get Access

#### Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Personal login Institutional Login#### Recommend to a librarian

Recommend PNAS to a Librarian#### Purchase options

Purchase this article to get full access to it.