Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



The complete generating function for Gessel walks is algebraic

Authors: Alin Bostan and Manuel Kauers; with an appendix by Mark van Hoeij
Journal: Proc. Amer. Math. Soc. 138 (2010), 3063-3078
MSC (2010): Primary 05A15, 14N10, 33F10, 68W30; Secondary 33C05, 97N80
Published electronically: May 14, 2010
MathSciNet review: 2653931
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Gessel walks are lattice walks in the quarter-plane $ \mathbb{N}^2$ which start at the origin  $ (0,0)\in\mathbb{N}^2$ and consist only of steps chosen from the set $ \{\leftarrow, \swarrow, \nearrow, \rightarrow\}$. We prove that if $ g(n;i,j)$ denotes the number of Gessel walks of length $ n$ which end at the point  $ (i,j)\in\mathbb{N}^2$, then the trivariate generating series

$ \displaystyle{G(t;x,y)=\sum_{n,i,j\geq 0} g(n;i,j)x^i y^j t^n}$ is an algebraic function.

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

  • 1. B. Beckermann and G. Labahn, A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl. 15 (1994), no. 3, 804-823. MR 1282696 (95f:65030)
  • 2. W. Bosma, J. Cannon, and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235-265. MR 1484478
  • 3. A. Bostan, P. Flajolet, B. Salvy, and E. Schost, Fast computation of special resultants, J. Symbolic Comput. 41 (2006), no. 1, 1-29. MR 2194883 (2006h:65005)
  • 4. A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic -- supplementary material,
  • 5. A. Bostan and M. Kauers, Automatic classification of restricted lattice walks, Proceedings of FPSAC'09, 2009, pp. 201-215.
  • 6. M. Bousquet-Mélou, Walks in the quarter plane: Kreweras' algebraic model, Ann. Appl. Probab. 15 (2005), no. 2, 1451-1491. MR 2134111 (2006c:05013)
  • 7. M. Bousquet-Mélou and M. Mishna, Walks with small steps in the quarter plane, preprint, to appear in ``Algorithmic Probability and Combinatorics'', special volume of the Contemporary Mathematics series of the Amer. Math. Soc., available at, 2008.
  • 8. M. Bousquet-Mélou and M. Petkovšek, Walks confined in a quadrant are not always D-finite, Theoret. Comput. Sci. 307 (2003), no. 2, 257-276. MR 2022578 (2004k:05010)
  • 9. F. Chyzak, Fonctions holonomes en calcul formel, Ph.D. thesis, École polytechnique, 1998.
  • 10. B. Dwork, Differential operators with nilpotent $ p$-curvature, Amer. J. Math. 112 (1990), no. 5, 749-786. MR 1073008 (91m:12008)
  • 11. J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge Univ. Press, 1999. MR 1689167 (2000j:68205)
  • 12. I. Gessel, A probabilistic method for lattice path enumeration, J. Stat. Plan. Infer. 14 (1986), 49-58. MR 845914 (87h:05017)
  • 13. D. Grigoriev, Complexity of factoring and GCD calculating of ordinary linear differential operators, J. Symbolic Comput. 10 (1990), no. 1, 7-37. MR 1081258 (92g:12012)
  • 14. M. Kauers, C. Koutschan, and D. Zeilberger, Proof of Ira Gessel's lattice path conjecture, Proc. Natl. Acad. Sci. USA 106 (2009), no. 28, 11502-11505. MR 2538821
  • 15. D. E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley, 1969. MR 0378456 (51:14624)
  • 16. C. Koutschan, Advanced applications of the holonomic systems approach, Ph.D. thesis, RISC-Linz, 2009.
  • 17. G. Kreweras, Sur une classe de problèmes de dénombrement liés au treillis des partitions des entiers, Cahiers du B.U.R.O. 6 (1965), 5-105.
  • 18. C. Mallinger, Algorithmic manipulations and transformations of univariate holonomic functions and sequences, Master's thesis, RISC-Linz, August 1996.
  • 19. J. McDonald, Fiber polytopes and fractional power series, J. Pure Appl. Algebra 104 (1995), 213-233. MR 1360177 (97a:52020)
  • 20. M. Mishna and A. Rechnitzer, Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci. 410 (2009), no. 38-40, 3616-3630. MR 2553316
  • 21. M. Petkovšek and H. Wilf, On a conjecture of Ira Gessel, preprint, available on line at http://, 2008.
  • 22. M. van der Put, Grothendieck's conjecture for the Risch equation $ y'=ay+b$, Indag. Math. (N.S.) 12 (2001), no. 1, 113-124. MR 1908143 (2003h:12011)
  • 23. B. Salvy and P. Zimmermann, Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM T. Math. Software 20 (1994), no. 2, 163-177.
  • 24. H. A. Schwarz, Über diejenigen Fälle, in welchen die Gaußische hypergeometrische Reihe einer algebraische Funktion ihres vierten Elementes darstellt, J. Reine Angew. Math. 75 (1873), 292-335.

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05A15, 14N10, 33F10, 68W30, 33C05, 97N80

Retrieve articles in all journals with MSC (2010): 05A15, 14N10, 33F10, 68W30, 33C05, 97N80

Additional Information

Alin Bostan
Affiliation: Algorithms Project, INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquencourt-B.P. 105, 78153 Le Chesnay Cedex, France

Manuel Kauers
Affiliation: RISC, Johannes Kepler University, Altenbergerstrasse 69, A-4040 Linz, Austria

Mark van Hoeij
Affiliation: Department of Mathematics, Florida State University, Tallahassee, Florida 32306

Received by editor(s): September 26, 2009
Published electronically: May 14, 2010
Additional Notes: The first author was partially supported by the Microsoft Research-INRIA Joint Centre
The second author was partially supported by Austrian Science Fund (FWF) grant no. P19462-N18.
Communicated by: Jim Haglund
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society