The complete generating function for Gessel walks is algebraic

Bostan, Alin; Kauers, Manuel

doi:10.1090/S0002-9939-2010-10398-2

The complete generating function for Gessel walks is algebraic
HTML articles powered by AMS MathViewer

by Alin Bostan and Manuel Kauers; \\with an appendix by Mark van Hoeij PDF

Proc. Amer. Math. Soc. 138 (2010), 3063-3078 Request permission

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

Bernhard Beckermann and George 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, DOI 10.1137/S0895479892230031
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
Alin Bostan, Philippe Flajolet, Bruno Salvy, and Éric Schost, Fast computation of special resultants, J. Symbolic Comput. 41 (2006), no. 1, 1–29. MR 2194883, DOI 10.1016/j.jsc.2005.07.001
A. Bostan and M. Kauers, The complete generating function for Gessel walks is algebraic — supplementary material, http://www.risc.jku.at/people/mkauers/gessel/.
A. Bostan and M. Kauers, Automatic classification of restricted lattice walks, Proceedings of FPSAC’09, 2009, pp. 201–215.
Mireille Bousquet-Mélou, Walks in the quarter plane: Kreweras’ algebraic model, Ann. Appl. Probab. 15 (2005), no. 2, 1451–1491. MR 2134111, DOI 10.1214/105051605000000052
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.
Mireille Bousquet-Mélou and Marko Petkovšek, Walks confined in a quadrant are not always D-finite, Theoret. Comput. Sci. 307 (2003), no. 2, 257–276. Random generation of combinatorial objects and bijective combinatorics. MR 2022578, DOI 10.1016/S0304-3975(03)00219-6
F. Chyzak, Fonctions holonomes en calcul formel, Ph.D. thesis, École polytechnique, 1998.
Bernard Dwork, Differential operators with nilpotent $p$-curvature, Amer. J. Math. 112 (1990), no. 5, 749–786. MR 1073008, DOI 10.2307/2374806
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Ira M. Gessel, A probabilistic method for lattice path enumeration, J. Statist. Plann. Inference 14 (1986), no. 1, 49–58. MR 845914, DOI 10.1016/0378-3758(86)90009-1
D. Yu. Grigor′ev, Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Comput. 10 (1990), no. 1, 7–37. MR 1081258, DOI 10.1016/S0747-7171(08)80034-X
Manuel Kauers, Christoph Koutschan, and Doron Zeilberger, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA 106 (2009), no. 28, 11502–11505. MR 2538821, DOI 10.1073/pnas.0901678106
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
C. Koutschan, Advanced applications of the holonomic systems approach, Ph.D. thesis, RISC-Linz, 2009.
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.
C. Mallinger, Algorithmic manipulations and transformations of univariate holonomic functions and sequences, Master’s thesis, RISC-Linz, August 1996.
John McDonald, Fiber polytopes and fractional power series, J. Pure Appl. Algebra 104 (1995), no. 2, 213–233. MR 1360177, DOI 10.1016/0022-4049(94)00129-5
Marni Mishna and Andrew Rechnitzer, Two non-holonomic lattice walks in the quarter plane, Theoret. Comput. Sci. 410 (2009), no. 38-40, 3616–3630. MR 2553316, DOI 10.1016/j.tcs.2009.04.008
M. Petkovšek and H. Wilf, On a conjecture of Ira Gessel, preprint, available on line at http:// arxiv.org/abs/0807.3202, 2008.
Marius 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, DOI 10.1016/S0019-3577(01)80009-4
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.
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.