An elementary solution of Gessel's walks in the quadrant
arXiv:1503.08573 · doi:10.1016/j.aim.2016.08.038
Abstract
Around 2000, Ira Gessel conjectured that the number of lattice walks in the quadrant N^2, starting and ending at the origin (0,0) and taking their steps in {E,NE,W,SW} had a simple hypergeometric form. In the following decade, this problem was recast in the systematic study of walks with small steps (that is,steps in {-1,0,1}^2) confined to the quadrant. The generating functions of such walks are archetypal solutions of partial discrete differential equations.A complete classification of quadrant walks according to the nature of their generating function(algebraic, D-finite or not) is now available, but Gessel'swalks remained mysterious because they were the only model among the 23D-finite ones that had not been given an elementarysolution. Instead, Gessel's conjecture was first proved usingan inventive computer algebra approach in 2008. A year later, the associated three-variate generating function was proved to be algebraic by a computer algebra tour de force. This was re-proved recently using elaborate complex analysis machinery. We give here an elementary and constructive proof. Our approach also solves other quadrant models (with multiple steps) recently proved to be algebraic via computer algebra.
arXiv commentin Advances in Mathematics, Elsevier, 2017
References in corpus (14)
- Two Non-holonomic Lattice Walks in the Quarter Plane
- Walks confined in a quadrant are not always D-finite
- Proof of Ira Gessel's Lattice Path Conjecture
- Counting colored planar maps: algebraicity results
- Singularity analysis via the iterated kernel method
- On the functions counting walks with small steps in the quarter plane
- On 3-dimensional lattice walks confined to the positive octant
- Random Walks in Cones: the Case of Nonzero Drift
- About a possible analytic approach for walks in the quarter plane with arbitrary big jumps
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- A human proof of Gessel's lattice path conjecture
- On the exit time from a cone for Brownian motion with drift
- On a conjecture of Ira Gessel
- Towards a human proof of Gessel's conjecture
Cited by in corpus (8)
- Counting quadrant walks via Tutte's invariant method
- Square lattice walks avoiding a quadrant
- Counting quadrant walks via Tutte's invariant method (extended abstract)
- Winding of simple walks on the square lattice
- Enumeration of three-quadrant walks via invariants: some diagonally symmetric models
- Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
- Walks obeying two-step rules on the square lattice: full, half and quarter planes
- Engines of Parsimony: Part II; Performance Trade-offs for Communicating Reversible Computers