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)

 
 

 

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?)

  • [1] Milton Abramowitz and Irene A. Stegun (eds.), Handbook of mathematical functions with formulas, graphs, and mathematical tables, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York; National Bureau of Standards, Washington, DC, 1984. Reprint of the 1972 edition; Selected Government Publications. MR 757537 (85j:00005a)
  • [2] Didier Arquès, Dénombrements de chemins dans $ {\bf R}^2$ soumis à contraintes, RAIRO Inform. Théor. Appl. 20 (1986), no. 4, 473-482 (French, with English summary). MR 880848 (88d:68085)
  • [3] Arvind Ayyer, Towards a human proof of Gessel's conjecture, J. Integer Seq. 12 (2009), no. 4, Article 09.4.2, 15. MR 2511220 (2010h:05020)
  • [4] Alin Bostan and Manuel Kauers, The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc. 138 (2010), no. 9, 3063-3078. With an appendix by Mark van Hoeij. MR 2653931 (2011j:05015), https://doi.org/10.1090/S0002-9939-2010-10398-2
  • [5] M. Bousquet-Mélou, Walks in the quarter plane: A functional equation approach, Proceedings of the Fourteenth International Conference on Formal Power Series and Algebraic Combinatorics, Melbourne, Australia (2002)
  • [6] Mireille Bousquet-Mélou, Walks in the quarter plane: Kreweras' algebraic model, Ann. Appl. Probab. 15 (2005), no. 2, 1451-1491. MR 2134111 (2006c:05013), https://doi.org/10.1214/105051605000000052
  • [7] Mireille Bousquet-Mélou and Marni Mishna, Walks with small steps in the quarter plane, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, 2010, pp. 1-39. MR 2681853 (2011k:05225), https://doi.org/10.1090/conm/520/10252
  • [8] Mireille Bousquet-Mélou and Marko Petkovšek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (2000), no. 1-3, 51-75. Formal power series and algebraic combinatorics (Toronto, ON, 1998). MR 1798324 (2002a:05005), https://doi.org/10.1016/S0012-365X(00)00147-3
  • [9] 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 (2004k:05010), https://doi.org/10.1016/S0304-3975(03)00219-6
  • [10] Guy Fayolle, Roudolf Iasnogorodski, and Vadim Malyshev, Random walks in the quarter-plane, Applications of Mathematics (New York), vol. 40, Springer-Verlag, Berlin, 1999. Algebraic methods, boundary value problems and applications. MR 1691900 (2000g:60002)
  • [11] G. Fayolle and K. Raschel, On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Related Fields 16 (2010), no. 3, 485-496. MR 2759770 (2012d:05035)
  • [12] Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235 (2010h:05005)
  • [13] L. Flatto and S. Hahn, Two parallel queues created by arrivals with two demands. I, SIAM J. Appl. Math. 44 (1984), no. 5, 1041-1053. MR 759714 (86e:60079a), https://doi.org/10.1137/0144074
  • [14] Leopold Flatto, Two parallel queues created by arrivals with two demands. II, SIAM J. Appl. Math. 45 (1985), no. 5, 861-878. MR 804012 (86m:60227), https://doi.org/10.1137/0145052
  • [15] I. Gessel, Personal communication. (2013)
  • [16] Dominique Gouyou-Beauchamps, Chemins sous-diagonaux et tableaux de Young, Combinatoire énumérative (Montreal, Que., 1985/Quebec, Que., 1985), Lecture Notes in Math., vol. 1234, Springer, Berlin, 1986, pp. 112-125 (French, with English summary). MR 927762 (89d:05005), https://doi.org/10.1007/BFb0072513
  • [17] Richard K. Guy, C. Krattenthaler, and Bruce E. Sagan, Lattice paths, reflections, & dimension-changing bijections, Ars Combin. 34 (1992), 3-15. MR 1206544 (93i:05008)
  • [18] Gareth A. Jones and David Singerman, Complex functions, Cambridge University Press, Cambridge, 1987. An algebraic and geometric viewpoint. MR 890746 (89b:30001)
  • [19] 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 (2011b:05015), https://doi.org/10.1073/pnas.0901678106
  • [20] Manuel Kauers and Doron Zeilberger, The quasi-holonomic ansatz and restricted lattice walks, J. Difference Equ. Appl. 14 (2008), no. 10-11, 1119-1126. MR 2447188 (2009m:05007), https://doi.org/10.1080/10236190802332084
  • [21] 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 5-105 (1965)
  • [22] Irina Kurkova and Kilian Raschel, Explicit expression for the generating function counting Gessel's walks, Adv. in Appl. Math. 47 (2011), no. 3, 414-433. MR 2822196 (2012h:05021), https://doi.org/10.1016/j.aam.2010.11.004
  • [23] Irina Kurkova and Kilian Raschel, On the functions counting walks with small steps in the quarter plane, Publ. Math. Inst. Hautes Études Sci. 116 (2012), 69-114. MR 3090255, https://doi.org/10.1007/s10240-012-0045-7
  • [24] I. Kurkova and K. Raschel, New Steps in Walks with Small Steps in the Quarter Plane: Series Expressions for the Generating Functions, Ann. Comb. 19 (2015), no. 3, 461-511. MR 3395491, https://doi.org/10.1007/s00026-015-0279-4
  • [25] L. Lipshitz, $ D$-finite power series, J. Algebra 122 (1989), no. 2, 353-373. MR 999079 (90g:13032), https://doi.org/10.1016/0021-8693(89)90222-6
  • [26] V. A. Malyshev, Random walks. The Wiener-Hopf equation in a quadrant of the plane. Galois automorphisms, Izdat. Moskov. Univ., Moscow, 1970 (Russian). MR 0428464 (55 #1485)
  • [27] V. A. Malyshev, Positive random walks and Galois theory, Uspehi Mat. Nauk 26 (1971), no. 1(157), 227-228 (Russian). MR 0293729 (45 #2804)
  • [28] V. A. Malyshev, An analytic method in the theory of two-dimensional positive random walks, Sibirsk. Mat. Ž. 13 (1972), 1314-1329, 1421 (Russian). MR 0336823 (49 #1596)
  • [29] M. Mishna, Classifying lattice walks restricted to the quarter plane, Proceedings of the Nineteenth International Conference on Formal Power Series and Algebraic Combinatorics, Tianjin, China (2007)
  • [30] Marni Mishna, Classifying lattice walks restricted to the quarter plane, J. Combin. Theory Ser. A 116 (2009), no. 2, 460-477. MR 2475028 (2009j:05009), https://doi.org/10.1016/j.jcta.2008.06.011
  • [31] Émile Picard, Sur les périodes des intégrales doubles et sur une classe d'équations différentielles linéaires, Ann. Sci. École Norm. Sup. (3) 50 (1933), 393-395 (French). MR 1509336
  • [32] Georg Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Math. Ann. 84 (1921), no. 1-2, 149-160 (German). MR 1512028, https://doi.org/10.1007/BF01458701
  • [33] M. Petkovšek and H. Wilf, On a conjecture of Ira Gessel, Preprint, arXiv:0807.3202 (2008).
  • [34] Kilian Raschel, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc. (JEMS) 14 (2012), no. 3, 749-777. MR 2911883, https://doi.org/10.4171/JEMS/317
  • [35] N. Roytvarf and Y. Yomdin, Analytic continuation of Cauchy-type integrals, Funct. Differ. Equ. 12 (2005), no. 3-4, 375-388. MR 2137518 (2006h:30028)
  • [36] Ping Sun, Proof of two conjectures of Petkovšek and Wilf on Gessel walks, Discrete Math. 312 (2012), no. 24, 3649-3655. MR 2979494, https://doi.org/10.1016/j.disc.2012.09.003
  • [37] R. Vidūnas, Transformations of algebraic Gauss hypergeometric functions, Preprint, arXiv:0807.4808 (2008).
  • [38] Raimundas Vidūnas, Algebraic transformations of Gauss hypergeometric functions, Funkcial. Ekvac. 52 (2009), no. 2, 139-180. MR 2547100 (2010i:33012), https://doi.org/10.1619/fesi.52.139
  • [39] E. T. Whittaker and G. N. Watson, A course of modern analysis, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1996. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions; Reprint of the fourth (1927) edition. MR 1424469 (97k:01072)

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

American Mathematical Society