Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks
Publications Mathématiques de Besançon no. 1  (2019), p. 41-80

We consider weighted small step walks in the positive quadrant, and provide algebraicity and differential transcendence results for the underlying generating functions: we prove that depending on the probabilities of allowed steps, certain of the generating functions are algebraic over the field of rational functions, while some others do not satisfy any algebraic differential equation with rational function coefficients. Our techniques involve differential Galois theory for difference equations as well as complex analysis (Weierstrass parameterization of elliptic curves). We also extend to the weighted case many key intermediate results, as a theorem of analytic continuation of the generating functions.

Nous considérons des marches à petits pas avec poids dans le quadrant positif, et nous fournissons des résultats d’algébricité et de transcendance différentielle pour les fonctions génératrices sous-jacentes  : nous prouvons que, selon les probabilités des pas permis, certaines fonctions génératrices sont algébriques sur le corps des fonctions rationnelles, alors que d’autres ne satisfont aucune équation différentielle algébrique. Nos techniques utilisent la théorie de Galois différentielle des équations aux différences ainsi que l’analyse complexe (notamment la paramétrisation de Weierstrass des courbes elliptiques). Nous étendons aussi au cas pondéré plusieurs résultats intermédiaires clé, comme un théorème de prolongement analytique des fonctions génératrices.

Published online : 2019-10-15
Classification:  05A15,  30D05,  39A06
Keywords: Random walks in the quarter plane, Difference Galois theory, Elliptic functions, Transcendence, Algebraicity
@article{PMB_2019___1_41_0,
author = {Thomas Dreyfus and Kilian Raschel},
title = {Differential transcendence \& algebraicity criteria for the series counting weighted quadrant walks},
journal = {Publications Math\'ematiques de Besan\c con},
publisher = {Presses universitaires de Franche-Comt\'e},
number = {1},
year = {2019},
pages = {41-80},
language = {en},
url = {https://pmb.centre-mersenne.org/item/PMB_2019___1_41_0}
}

Dreyfus, Thomas; Raschel, Kilian. Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks. Publications Mathématiques de Besançon, no. 1 (2019), pp. 41-80. pmb.centre-mersenne.org/item/PMB_2019___1_41_0/

[1] Olivier Bernardi; Mireille Bousquet-Mélou; Kilian Raschel Counting quadrant walks via Tutte’s invariant method (2017) (https://arxiv.org/abs/1708.08215)

[2] Alin Bostan; Mireille Bousquet-Mélou; Manuel Kauers; Stephen Melczer On 3-dimensional lattice walks confined to the positive octant, Ann. Comb., Tome 20 (2016) no. 4, pp. 661-704 | Article | MR 3572381 | Zbl 1354.05006

[3] Alin Bostan; Manuel Kauers The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., Tome 138 (2010) no. 9, pp. 3063-3078 (With an appendix by Mark van Hoeij) | Article | MR 2653931 | Zbl 1206.05013

[4] Alin Bostan; Kilian Raschel; Bruno Salvy Non-D-finite excursions in the quarter plane, J. Comb. Theory, Ser. A, Tome 121 (2014), pp. 45-63 | Article | MR 3115331 | Zbl 1279.05003

[5] Mireille Bousquet-Mélou; Marni Mishna Walks with small steps in the quarter plane, Algorithmic probability and combinatorics, American Mathematical Society (Contemporary Mathematics) Tome 520 (2010), pp. 1-39 | Article | MR 2681853 | Zbl 1209.05008

[6] Mireille Bousquet-Mélou; Marko Petkovšek Linear recurrences with constant coefficients: the multivariate case, Discrete Math., Tome 225 (2000) no. 1-3, pp. 51-75 (Formal power series and algebraic combinatorics (Toronto, ON, 1998)) | Article | MR 1798324 | Zbl 0963.05005

[7] Denis Denisov; Vitali Wachtel Random walks in cones, Ann. Probab., Tome 43 (2015) no. 3, pp. 992-1044 | Article | MR 3342657 | Zbl 1332.60066

[8] Thomas Dreyfus; Charlotte Hardouin; Julien Roques Hypertranscendance of solutions of Mahler equations, J. Eur. Math. Soc., Tome 20 (2018) no. 9, pp. 2209-2238

[9] Thomas Dreyfus; Charlotte Hardouin; Julien Roques; Michael F. Singer Walks in the quarter plane, genus zero case (2017) (https://arxiv.org/abs/1710.02848)

[10] Thomas Dreyfus; Charlotte Hardouin; Julien Roques; Michael F. Singer On the nature of the generating series of walks in the quarter plane, Invent. Math., Tome 213 (2018) no. 1, pp. 139-203

[11] Thomas Dreyfus; Julien Roques Galois groups of difference equations of order two on elliptic curves, SIGMA, Symmetry Integrability Geom. Methods Appl., Tome 11 (2015), 003, 23 pages | Article | MR 3313679 | Zbl 1311.39002

[12] Daniel K. Du; Qing-Hu Hou; Rong-Hua Wang Infinite orders and non-D-finite property of 3-dimensional lattice walks, Electron. J. Comb., Tome 23 (2016) no. 3, 3.38, 15 pages | MR 3558075 | Zbl 1344.05013

[13] Johannes Duistermaat Discrete integrable systems. QRT maps and elliptic surfaces, Springer, Springer Monographs in Mathematics (2010), xxii+627 pages | Article | MR 2683025 | Zbl 1219.14001

[14] Guy Fayolle; Roudolf Iasnogorodski; Vadim Malyshev Random walks in the quarter-plane. Algebraic methods, boundary value problems and applications, Springer, Applications of Mathematics, Tome 40 (1999), xvi+156 pages | Article | MR 1691900 | Zbl 0932.60002

[15] Guy Fayolle; Kilian Raschel On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Relat. Fields, Tome 16 (2010) no. 3, pp. 485-496 | MR 2759770 | Zbl 1284.05018

[16] Guy Fayolle; Kilian Raschel Random walks in the quarter-plane with zero drift: an explicit criterion for the finiteness of the associated group, Markov Process. Relat. Fields, Tome 17 (2011) no. 4, pp. 619-636 | MR 2918123 | Zbl 1263.60039

[17] Charlotte Hardouin Galoisian approach to differential transcendence, Galois theories of linear difference equations: an introduction, American Mathematical Society (Mathematical Surveys and Monographs) Tome 211 (2016), pp. 43-102 | MR 3497726 | Zbl 1347.39001

[18] Charlotte Hardouin; Michael F. Singer Differential Galois theory of linear difference equations, Math. Ann., Tome 342 (2008) no. 2, pp. 333-377 | Article | MR 2425146 | Zbl 1163.12002

[19] Manuel Kauers; Rika Yatchak Walks in the quarter plane with multiple steps, Proceedings of FPSAC 2015, Assoc. Discrete Math. Theor. Comput. Sci., Nancy (Discrete Math. Theor. Comput. Sci. Proc.) (2015), pp. 25-36 | MR 3470849 | Zbl 1335.05012

[20] Irina Kurkova; Kilian Raschel On the functions counting walks with small steps in the quarter plane, Publ. Math., Inst. Hautes Étud. Sci., Tome 116 (2012), pp. 69-114 | Article | MR 3090255

[21] Irina Kurkova; Kilian Raschel New steps in walks with small steps in the quarter plane: series expressions for the generating functions, Ann. Comb., Tome 19 (2015) no. 3, pp. 461-511 | Article | MR 3395491 | Zbl 1326.05010

[22] Stephen Melczer; Marni Mishna Singularity analysis via the iterated kernel method, Comb. Probab. Comput., Tome 23 (2014) no. 5, pp. 861-888 | Article | MR 3249228 | Zbl 1298.05026

[23] Marni Mishna Classifying lattice walks restricted to the quarter plane, J. Comb. Theory, Ser. A, Tome 116 (2009) no. 2, pp. 460-477 | Article | MR 2475028

[24] Marni Mishna; Andrew Rechnitzer Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., Tome 410 (2009) no. 38-40, pp. 3616-3630 | Article | MR 2553316 | Zbl 1228.05038

[25] Kilian Raschel Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc., Tome 14 (2012) no. 3, pp. 749-777 | Article | MR 2911883 | Zbl 1238.05014

[26] Edmund Whittaker; George Watson A course of modern analysis. An introduction to the general theory of infinite processes and of analytic functions; with an account of the principal transcendental functions, Cambridge University Press, Cambridge Mathematical Library (1996), vi+608 pages | Article | MR 1424469 | Zbl 0951.30002