Proceedings of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6826(e) ISSN 0002-9939(p)

The complete generating function for Gessel walks is algebraic

Author(s): Alin Bostan; 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
Posted: May 14, 2010
MathSciNet review: 2653931
Retrieve article in: 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 denotes the number of Gessel walks of length 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:

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, http://www.risc.jku.at/people/mkauers/gessel/.
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 http://arxiv.org/abs/0810.4387, 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 -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:// arxiv.org/abs/0807.3202, 2008.
22.: M. van der Put, Grothendieck's conjecture for the Risch equation , 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.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|