Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

A human proof of Gessel's lattice path conjecture


Authors: A. Bostan, I. Kurkova and K. Raschel
Journal: Trans. Amer. Math. Soc. 369 (2017), 1365-1393
MSC (2010): Primary 05A15; Secondary 30F10, 30D05
DOI: https://doi.org/10.1090/tran/6804
Published electronically: April 14, 2016
MathSciNet review: 3572277
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Gessel walks are lattice paths confined to the quarter plane that start at the origin and consist of unit steps going either West, East, South-West or North-East. In 2001, Ira Gessel conjectured a nice closed-form expression for the number of Gessel walks ending at the origin. In 2008, Kauers, Koutschan and Zeilberger gave a computer-aided proof of this conjecture. The same year, Bostan and Kauers showed, again using computer algebra tools, that the complete generating function of Gessel walks is algebraic. In this article we propose the first ``human proofs'' of these results. They are derived from a new expression for the generating function of Gessel walks in terms of Weierstrass zeta functions.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05A15, 30F10, 30D05

Retrieve articles in all journals with MSC (2010): 05A15, 30F10, 30D05


Additional Information

A. Bostan
Affiliation: INRIA Saclay Île-de-France, Bâtiment Alan Turing, 1 rue Honoré d’Estienne d’Orves, 91120 Palaiseau, France
Email: Alin.Bostan@inria.fr

I. Kurkova
Affiliation: Laboratoire de Probabilités et Modèles Aléatoires, Université Pierre et Marie Curie, 4 Place Jussieu, 75252 Paris Cedex 05, France
Email: Irina.Kourkova@upmc.fr

K. Raschel
Affiliation: CNRS & Fédération de recherche Denis Poisson & Laboratoire de Mathématiques et Physique Théorique, Université de Tours, Parc de Grandmont, 37200 Tours, France
Email: Kilian.Raschel@lmpt.univ-tours.fr

DOI: https://doi.org/10.1090/tran/6804
Keywords: Enumerative combinatorics, lattice paths, Gessel walks, generating functions, algebraic functions, elliptic functions
Received by editor(s): March 25, 2014
Received by editor(s) in revised form: February 12, 2015
Published electronically: April 14, 2016
Article copyright: © Copyright 2016 American Mathematical Society