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:
Keywords: Random walks in the quarter plane, Difference Galois theory, Elliptic functions, Transcendence, Algebraicity
Thomas Dreyfus 1; Kilian Raschel 2
CC-BY-ND 4.0
@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{c}on. Alg\`ebre et th\'eorie des nombres},
pages = {41--80},
publisher = {Presses universitaires de Franche-Comt\'e},
number = {1},
year = {2019},
doi = {10.5802/pmb.29},
language = {en},
url = {https://pmb.centre-mersenne.org/articles/10.5802/pmb.29/}
}
TY - JOUR AU - Thomas Dreyfus AU - Kilian Raschel TI - Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks JO - Publications mathématiques de Besançon. Algèbre et théorie des nombres PY - 2019 SP - 41 EP - 80 IS - 1 PB - Presses universitaires de Franche-Comté UR - https://pmb.centre-mersenne.org/articles/10.5802/pmb.29/ DO - 10.5802/pmb.29 LA - en ID - PMB_2019___1_41_0 ER -
%0 Journal Article %A Thomas Dreyfus %A Kilian Raschel %T Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks %J Publications mathématiques de Besançon. Algèbre et théorie des nombres %D 2019 %P 41-80 %N 1 %I Presses universitaires de Franche-Comté %U https://pmb.centre-mersenne.org/articles/10.5802/pmb.29/ %R 10.5802/pmb.29 %G en %F PMB_2019___1_41_0
Thomas Dreyfus; Kilian Raschel. Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks. Publications mathématiques de Besançon. Algèbre et théorie des nombres, no. 1 (2019), pp. 41-80. doi : 10.5802/pmb.29. https://pmb.centre-mersenne.org/articles/10.5802/pmb.29/
[1] Counting quadrant walks via Tutte’s invariant method (2017) (https://arxiv.org/abs/1708.08215)
[2] On 3-dimensional lattice walks confined to the positive octant, Ann. Comb., Volume 20 (2016) no. 4, pp. 661-704 | DOI | MR | Zbl
[3] The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., Volume 138 (2010) no. 9, pp. 3063-3078 (With an appendix by Mark van Hoeij) | DOI | MR | Zbl
[4] Non-D-finite excursions in the quarter plane, J. Comb. Theory, Ser. A, Volume 121 (2014), pp. 45-63 | DOI | MR | Zbl
[5] Walks with small steps in the quarter plane, Algorithmic probability and combinatorics (Contemporary Mathematics), Volume 520, American Mathematical Society, 2010, pp. 1-39 | DOI | MR | Zbl
[6] Linear recurrences with constant coefficients: the multivariate case, Discrete Math., Volume 225 (2000) no. 1-3, pp. 51-75 Formal power series and algebraic combinatorics (Toronto, ON, 1998) | DOI | MR | Zbl
[7] Random walks in cones, Ann. Probab., Volume 43 (2015) no. 3, pp. 992-1044 | DOI | MR | Zbl
[8] Hypertranscendance of solutions of Mahler equations, J. Eur. Math. Soc., Volume 20 (2018) no. 9, pp. 2209-2238
[9] Walks in the quarter plane, genus zero case (2017) (https://arxiv.org/abs/1710.02848)
[10] On the nature of the generating series of walks in the quarter plane, Invent. Math., Volume 213 (2018) no. 1, pp. 139-203
[11] Galois groups of difference equations of order two on elliptic curves, SIGMA, Symmetry Integrability Geom. Methods Appl., Volume 11 (2015), 003, 23 pages | DOI | MR | Zbl
[12] Infinite orders and non-D-finite property of 3-dimensional lattice walks, Electron. J. Comb., Volume 23 (2016) no. 3, 3.38, 15 pages | MR | Zbl
[13] Discrete integrable systems. QRT maps and elliptic surfaces, Springer Monographs in Mathematics, Springer, 2010, xxii+627 pages | DOI | MR | Zbl
[14] Random walks in the quarter-plane. Algebraic methods, boundary value problems and applications, Applications of Mathematics, 40, Springer, 1999, xvi+156 pages | DOI | MR | Zbl
[15] On the holonomy or algebraicity of generating functions counting lattice walks in the quarter-plane, Markov Process. Relat. Fields, Volume 16 (2010) no. 3, pp. 485-496 | MR | Zbl
[16] Random walks in the quarter-plane with zero drift: an explicit criterion for the finiteness of the associated group, Markov Process. Relat. Fields, Volume 17 (2011) no. 4, pp. 619-636 | MR | Zbl
[17] Galoisian approach to differential transcendence, Galois theories of linear difference equations: an introduction (Mathematical Surveys and Monographs), Volume 211, American Mathematical Society, 2016, pp. 43-102 | MR | Zbl
[18] Differential Galois theory of linear difference equations, Math. Ann., Volume 342 (2008) no. 2, pp. 333-377 | DOI | MR | Zbl
[19] Walks in the quarter plane with multiple steps, Proceedings of FPSAC 2015 (Discrete Math. Theor. Comput. Sci. Proc.) (2015), pp. 25-36 | MR | Zbl
[20] On the functions counting walks with small steps in the quarter plane, Publ. Math., Inst. Hautes Étud. Sci., Volume 116 (2012), pp. 69-114 | DOI | MR
[21] New steps in walks with small steps in the quarter plane: series expressions for the generating functions, Ann. Comb., Volume 19 (2015) no. 3, pp. 461-511 | DOI | MR | Zbl
[22] Singularity analysis via the iterated kernel method, Comb. Probab. Comput., Volume 23 (2014) no. 5, pp. 861-888 | DOI | MR | Zbl
[23] Classifying lattice walks restricted to the quarter plane, J. Comb. Theory, Ser. A, Volume 116 (2009) no. 2, pp. 460-477 | DOI | MR
[24] Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., Volume 410 (2009) no. 38-40, pp. 3616-3630 | DOI | MR | Zbl
[25] Counting walks in a quadrant: a unified approach via boundary value problems, J. Eur. Math. Soc., Volume 14 (2012) no. 3, pp. 749-777 | DOI | MR | Zbl
[26] 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 Mathematical Library, Cambridge University Press, 1996, vi+608 pages | DOI | MR | Zbl
Cited by Sources: