A human proof of Gessel’s lattice path conjecture

Bostan, A.; Kurkova, I.; Raschel, K.

doi:10.1090/tran/6804

A human proof of Gessel’s lattice path conjecture
HTML articles powered by AMS MathViewer

by A. Bostan, I. Kurkova and K. Raschel PDF

Trans. Amer. Math. Soc. 369 (2017), 1365-1393 Request permission

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

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; John Wiley & Sons, Inc., New York, 1984. Reprint of the 1972 edition; Selected Government Publications. MR 757537
Didier Arquès, Dénombrements de chemins dans $\textbf {R}^2$ soumis à contraintes, RAIRO Inform. Théor. Appl. 20 (1986), no. 4, 473–482 (French, with English summary). MR 880848
Arvind Ayyer, Towards a human proof of Gessel’s conjecture, J. Integer Seq. 12 (2009), no. 4, Article 09.4.2, 15. MR 2511220
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, DOI 10.1090/S0002-9939-2010-10398-2
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)
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
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, DOI 10.1090/conm/520/10252
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, DOI 10.1016/S0012-365X(00)00147-3
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
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, DOI 10.1007/978-3-642-60001-2
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
Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
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, DOI 10.1137/0144074
Leopold Flatto, Two parallel queues created by arrivals with two demands. II, SIAM J. Appl. Math. 45 (1985), no. 5, 861–878. MR 804012, DOI 10.1137/0145052
I. Gessel, Personal communication. (2013)
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, DOI 10.1007/BFb0072513
Richard K. Guy, C. Krattenthaler, and Bruce E. Sagan, Lattice paths, reflections, & dimension-changing bijections, Ars Combin. 34 (1992), 3–15. MR 1206544
Gareth A. Jones and David Singerman, Complex functions, Cambridge University Press, Cambridge, 1987. An algebraic and geometric viewpoint. MR 890746, DOI 10.1017/CBO9781139171915
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
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, DOI 10.1080/10236190802332084
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)
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, DOI 10.1016/j.aam.2010.11.004
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, DOI 10.1007/s10240-012-0045-7
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, DOI 10.1007/s00026-015-0279-4
L. Lipshitz, $D$-finite power series, J. Algebra 122 (1989), no. 2, 353–373. MR 999079, DOI 10.1016/0021-8693(89)90222-6
V. A. Malyshev, Sluchaĭ nye bluzhdaniya Uravneniya. Vinera-Khopfa v chetverti ploskosti. Avtomorfizmy Galua, Izdat. Moskov. Univ., Moscow, 1970 (Russian). MR 0428464
V. A. Malyšev, Positive random walks and Galois theory, Uspehi Mat. Nauk 26 (1971), no. 1(157), 227–228 (Russian). MR 0293729
V. A. Malyšev, An analytic method in the theory of two-dimensional positive random walks, Sibirsk. Mat. Ž. 13 (1972), 1314–1329, 1421 (Russian). MR 0336823
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)
Marni Mishna, Classifying lattice walks restricted to the quarter plane, J. Combin. Theory Ser. A 116 (2009), no. 2, 460–477. MR 2475028, DOI 10.1016/j.jcta.2008.06.011
É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
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, DOI 10.1007/BF01458701
M. Petkovšek and H. Wilf, On a conjecture of Ira Gessel, Preprint, arXiv:0807.3202 (2008).
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, DOI 10.4171/JEMS/317
N. Roytvarf and Y. Yomdin, Analytic continuation of Cauchy-type integrals, Funct. Differ. Equ. 12 (2005), no. 3-4, 375–388. MR 2137518
Ping Sun, Proof of two conjectures of Petkovšek and Wilf on Gessel walks, Discrete Math. 312 (2012), no. 24, 3649–3655. MR 2979494, DOI 10.1016/j.disc.2012.09.003
R. Vidūnas, Transformations of algebraic Gauss hypergeometric functions, Preprint, arXiv:0807.4808 (2008).
Raimundas Vidūnas, Algebraic transformations of Gauss hypergeometric functions, Funkcial. Ekvac. 52 (2009), no. 2, 139–180. MR 2547100, DOI 10.1619/fesi.52.139
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, DOI 10.1017/CBO9780511608759