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.
Additional Information
- Alin Bostan
- Affiliation: Algorithms Project, INRIA Paris-Rocquencourt, Domaine de Voluceau, Rocquencourt-B.P. 105, 78153 Le Chesnay Cedex, France
- MR Author ID: 725685
- Email: Alin.Bostan@inria.fr
- Manuel Kauers
- Affiliation: RISC, Johannes Kepler University, Altenbergerstrasse 69, A-4040 Linz, Austria
- Email: mkauers@risc.uni-linz.ac.at
- Mark van Hoeij
- Affiliation: Department of Mathematics, Florida State University, Tallahassee, Florida 32306
- Email: hoeij@math.fsu.edu
- 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
- © Copyright 2010 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 138 (2010), 3063-3078
- MSC (2010): Primary 05A15, 14N10, 33F10, 68W30; Secondary 33C05, 97N80
- DOI: https://doi.org/10.1090/S0002-9939-2010-10398-2
- MathSciNet review: 2653931