×

A human proof of Gessel’s lattice path conjecture. (English) Zbl 1350.05006

Summary: 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, I. Gessel conjectured a nice closed-form expression for the number of Gessel walks ending at the origin. M. Kauers et al. [Proc. Natl. Acad. Sci. USA 106, No. 28, 11502–11505 (2009; Zbl 1203.05010)] gave a computer-aided proof of this conjecture. The same year, A. Bostan et al. [Proc. Am. Math. Soc. 138, No. 9, 3063–3078 (2010; Zbl 1206.05013)] 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.

MSC:

05A15 Exact enumeration problems, generating functions
30F10 Compact Riemann surfaces and uniformization
30D05 Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Handbook of mathematical functions with formulas, graphs, and mathematical tables, A Wiley-Interscience Publication, xiv+1046 pp. (1984), John Wiley & Sons, Inc., New York; National Bureau of Standards, Washington, DC · Zbl 0643.33001
[2] Arqu{\`“e}s, Didier, D\'”enombrements de chemins dans \({\bf R}^2\) soumis \`“a contraintes, RAIRO Inform. Th\'”eor. Appl., 20, 4, 473-482 (1986) · Zbl 0613.05008
[3] Ayyer, Arvind, Towards a human proof of Gessel’s conjecture, J. Integer Seq., 12, 4, Article 09.4.2, 15 pp. (2009) · Zbl 1165.05304
[4] Bostan, Alin; Kauers, Manuel, The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc., 138, 9, 3063-3078 (2010) · Zbl 1206.05013 · doi:10.1090/S0002-9939-2010-10398-2
[5] BM02 M. Bousquet-M\'elou, 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] Bousquet-M{\'e}lou, Mireille, Walks in the quarter plane: Kreweras’ algebraic model, Ann. Appl. Probab., 15, 2, 1451-1491 (2005) · Zbl 1064.05010 · doi:10.1214/105051605000000052
[7] Bousquet-M{\'e}lou, Mireille; Mishna, Marni, Walks with small steps in the quarter plane. Algorithmic probability and combinatorics, Contemp. Math. 520, 1-39 (2010), Amer. Math. Soc., Providence, RI · Zbl 1209.05008 · doi:10.1090/conm/520/10252
[8] Bousquet-M{\'e}lou, Mireille; Petkov{\v{s}}ek, Marko, Linear recurrences with constant coefficients: the multivariate case, Discrete Math., 225, 1-3, 51-75 (2000) · Zbl 0963.05005 · doi:10.1016/S0012-365X(00)00147-3
[9] Bousquet-M{\'e}lou, Mireille; Petkov{\v{s}}ek, Marko, Walks confined in a quadrant are not always D-finite, Theoret. Comput. Sci., 307, 2, 257-276 (2003) · Zbl 1070.68112 · doi:10.1016/S0304-3975(03)00219-6
[10] Fayolle, Guy; Iasnogorodski, Roudolf; Malyshev, Vadim, Random walks in the quarter-plane, Applications of Mathematics (New York) 40, xvi+156 pp. (1999), Springer-Verlag, Berlin · Zbl 0932.60002 · doi:10.1007/978-3-642-60001-2
[11] Fayolle, G.; Raschel, K., On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Related Fields, 16, 3, 485-496 (2010) · Zbl 1284.05018
[12] Flajolet, Philippe; Sedgewick, Robert, Analytic combinatorics, xiv+810 pp. (2009), Cambridge University Press, Cambridge · Zbl 1165.05001 · doi:10.1017/CBO9780511801655
[13] Flatto, L.; Hahn, S., Two parallel queues created by arrivals with two demands. I, SIAM J. Appl. Math., 44, 5, 1041-1053 (1984) · Zbl 0554.90041 · doi:10.1137/0144074
[14] Flatto, Leopold, Two parallel queues created by arrivals with two demands. II, SIAM J. Appl. Math., 45, 5, 861-878 (1985) · Zbl 0579.90033 · doi:10.1137/0145052
[15] Gessel13 I. Gessel, Personal communication. (2013)
[16] Gouyou-Beauchamps, Dominique, Chemins sous-diagonaux et tableaux de Young. Combinatoire \'enum\'erative (Montreal, Que., 1985/Quebec, Que., 1985), Lecture Notes in Math. 1234, 112-125 (1986), Springer, Berlin · Zbl 0611.05003 · doi:10.1007/BFb0072513
[17] Guy, Richard K.; Krattenthaler, C.; Sagan, Bruce E., Lattice paths, reflections, & dimension-changing bijections, Ars Combin., 34, 3-15 (1992) · Zbl 0770.05003
[18] Jones, Gareth A.; Singerman, David, Complex functions, xiv+342 pp. (1987), Cambridge University Press, Cambridge · Zbl 0608.30001 · doi:10.1017/CBO9781139171915
[19] Kauers, Manuel; Koutschan, Christoph; Zeilberger, Doron, Proof of Ira Gessel’s lattice path conjecture, Proc. Natl. Acad. Sci. USA, 106, 28, 11502-11505 (2009) · Zbl 1203.05010 · doi:10.1073/pnas.0901678106
[20] Kauers, Manuel; Zeilberger, Doron, The quasi-holonomic ansatz and restricted lattice walks, J. Difference Equ. Appl., 14, 10-11, 1119-1126 (2008) · Zbl 1193.05014 · doi:10.1080/10236190802332084
[21] Kreweras G. Kreweras, Sur une classe de probl\`“emes de d\'”enombrement li\'es au treillis des partitions des entiers, Cahiers du B.U.R.O. 6 5-105 (1965)
[22] Kurkova, Irina; Raschel, Kilian, Explicit expression for the generating function counting Gessel’s walks, Adv. in Appl. Math., 47, 3, 414-433 (2011) · Zbl 1234.05027 · doi:10.1016/j.aam.2010.11.004
[23] Kurkova, Irina; Raschel, Kilian, On the functions counting walks with small steps in the quarter plane, Publ. Math. Inst. Hautes \'Etudes Sci., 116, 69-114 (2012) · Zbl 1255.05012 · doi:10.1007/s10240-012-0045-7
[24] Kurkova, I.; Raschel, K., New Steps in Walks with Small Steps in the Quarter Plane: Series Expressions for the Generating Functions, Ann. Comb., 19, 3, 461-511 (2015) · Zbl 1326.05010 · doi:10.1007/s00026-015-0279-4
[25] Lipshitz, L., \(D\)-finite power series, J. Algebra, 122, 2, 353-373 (1989) · Zbl 0695.12018 · doi:10.1016/0021-8693(89)90222-6
[26] Malyshev, V. A., Random walks. The Wiener-Hopf equation in a quadrant of the plane. Galois automorphisms, 201 pp. (1970), Izdat. Moskov. Univ., Moscow
[27] Malyshev, V. A., Positive random walks and Galois theory, Uspehi Mat. Nauk, 26, 1(157), 227-228 (1971) · Zbl 0254.60043
[28] Malyshev, V. A., An analytic method in the theory of two-dimensional positive random walks, Sibirsk. Mat. \v Z., 13, 1314-1329, 1421 (1972) · Zbl 0287.60072
[29] MM07 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] Mishna, Marni, Classifying lattice walks restricted to the quarter plane, J. Combin. Theory Ser. A, 116, 2, 460-477 (2009) · Zbl 1183.05004 · doi:10.1016/j.jcta.2008.06.011
[31] Picard, {\'E}mile, Sur les p\'eriodes des int\'egrales doubles et sur une classe d’\'equations diff\'erentielles lin\'eaires, Ann. Sci. \'Ecole Norm. Sup. (3), 50, 393-395 (1933) · Zbl 0008.15801
[32] P{\'o}lya, Georg, \"Uber eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Stra\ss ennetz, Math. Ann., 84, 1-2, 149-160 (1921) · JFM 48.0603.01 · doi:10.1007/BF01458701
[33] PW M. Petkovsek and H. Wilf, On a conjecture of Ira Gessel, Preprint, http://arxiv.org/abs/0807.3202arXiv:0807.3202 (2008).
[34] Raschel, Kilian, Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc. (JEMS), 14, 3, 749-777 (2012) · Zbl 1238.05014 · doi:10.4171/JEMS/317
[35] Roytvarf, N.; Yomdin, Y., Analytic continuation of Cauchy-type integrals, Funct. Differ. Equ., 12, 3-4, 375-388 (2005) · Zbl 1072.30029
[36] Sun, Ping, Proof of two conjectures of Petkov\v sek and Wilf on Gessel walks, Discrete Math., 312, 24, 3649-3655 (2012) · Zbl 1254.05021 · doi:10.1016/j.disc.2012.09.003
[37] Vidunas08 R. Vid\=unas, Transformations of algebraic Gauss hypergeometric functions, Preprint, http://arxiv.org/abs/0807.4808arXiv:0807.4808 (2008).
[38] Vid{\=u}nas, Raimundas, Algebraic transformations of Gauss hypergeometric functions, Funkcial. Ekvac., 52, 2, 139-180 (2009) · Zbl 1176.33005 · doi:10.1619/fesi.52.139
[39] Whittaker, E. T.; Watson, G. N., A course of modern analysis, Cambridge Mathematical Library, vi+608 pp. (1996), Cambridge University Press, Cambridge · Zbl 0951.30002 · doi:10.1017/CBO9780511608759
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.