Length derivative of the generating function of walks confined in the quarter plane

Thomas Dreyfus; Charlotte Hardouin

doi:10.5802/cml.77

Thomas Dreyfus ¹; Charlotte Hardouin ²

¹ Institut de Recherche Mathématique Avancée UMR 7501, Université de Strasbourg et CNRS, 7 rue René Descartes, 67084 Strasbourg, France
² Université Paul Sabatier - Institut de Mathématiques de Toulouse, 118 route de Narbonne, 31062 Toulouse, France

Confluentes Mathematici, Volume 13 (2021) no. 2, pp. 39-92.

Abstract

In the present paper, we use difference Galois theory to study the nature of the generating function counting walks with small steps in the quarter plane. These series are trivariate formal power series $Q (x, y, t)$ that count the number of walks confined in the first quadrant of the plane with a fixed set of admissible steps, called the model of the walk. While the variables $x$ and $y$ are associated to the ending point of the path, the variable $t$ encodes its length. In this paper, we prove that in the unweighted case, $Q (x, y, t)$ satisfies an algebraic differential relation with respect to $t$ if and only if it satisfies an algebraic differential relation with respect $x$ (resp. $y$ ). Combined with [2, 3, 4, 9, 11], we are able to characterize the $t$ -differential transcendence of the $79$ models of walks listed by Bousquet-Mélou and Mishna.

Received: 2020-07-12
Accepted: 2022-01-13
Revised after acceptance: 2022-03-01
Published online: 2022-03-21

DOI: 10.5802/cml.77

Classification: 05A15, 30D05, 39A06
Keywords: Random walks, Difference Galois theory, Transcendence, Valued differential fields.

Author's affiliations:

Thomas Dreyfus ¹; Charlotte Hardouin ²

¹ Institut de Recherche Mathématique Avancée UMR 7501, Université de Strasbourg et CNRS, 7 rue René Descartes, 67084 Strasbourg, France
² Université Paul Sabatier - Institut de Mathématiques de Toulouse, 118 route de Narbonne, 31062 Toulouse, France

License:

CC-BY-NC-ND 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{CML_2021__13_2_39_0,
     author = {Thomas Dreyfus and Charlotte Hardouin},
     title = {Length derivative of the generating function of walks confined in the quarter plane},
     journal = {Confluentes Mathematici},
     pages = {39--92},
     publisher = {Institut Camille Jordan},
     volume = {13},
     number = {2},
     year = {2021},
     doi = {10.5802/cml.77},
     language = {en},
     url = {https://cml.centre-mersenne.org/articles/10.5802/cml.77/}
}

TY  - JOUR
AU  - Thomas Dreyfus
AU  - Charlotte Hardouin
TI  - Length derivative of the generating function of walks confined in the quarter plane
JO  - Confluentes Mathematici
PY  - 2021
SP  - 39
EP  - 92
VL  - 13
IS  - 2
PB  - Institut Camille Jordan
UR  - https://cml.centre-mersenne.org/articles/10.5802/cml.77/
DO  - 10.5802/cml.77
LA  - en
ID  - CML_2021__13_2_39_0
ER  -

%0 Journal Article
%A Thomas Dreyfus
%A Charlotte Hardouin
%T Length derivative of the generating function of walks confined in the quarter plane
%J Confluentes Mathematici
%D 2021
%P 39-92
%V 13
%N 2
%I Institut Camille Jordan
%U https://cml.centre-mersenne.org/articles/10.5802/cml.77/
%R 10.5802/cml.77
%G en
%F CML_2021__13_2_39_0

Thomas Dreyfus; Charlotte Hardouin. Length derivative of the generating function of walks confined in the quarter plane. Confluentes Mathematici, Volume 13 (2021) no. 2, pp. 39-92. doi : 10.5802/cml.77. https://cml.centre-mersenne.org/articles/10.5802/cml.77/

References
Cited by

[1] Matthias Aschenbrenner; Lou van den Dries; Joris van der Hoeven Asymptotic differential algebra and model theory of transseries, Annals of Mathematics Studies, 195, Princeton University Press, Princeton, NJ, 2017, xxi+849 pages

[2] Olivier Bernardi; Mireille Bousquet-Mélou; Kilian Raschel Counting quadrant walks via Tutte’s invariant method, Discrete Mathematics & Theoretical Computer Science (2020)

[3] Alin Bostan; Mark van Hoeij; Manuel Kauers The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc., Volume 138 (2010) no. 9, pp. 3063-3078

[4] Mireille Bousquet-Mélou; Marni Mishna Walks with small steps in the quarter plane, Algorithmic probability and combinatorics (Contemp. Math.), Volume 520, Amer. Math. Soc., Providence, RI, 2010, pp. 1-39

[5] Richard M. Cohn Difference algebra, Interscience Publishers John Wiley & Sons, New York-London-Sydeny, 1965

[6] Lucia Di Vizio; Charlotte Hardouin Descent for differential Galois theory of difference equations: confluence and $q$ -dependence, Pacific J. Math., Volume 256 (2012) no. 1, pp. 79-104 | DOI | MR

[7] Lucia Di Vizio; Changgui Zhang On $q$ -summation and confluence, Ann. Inst. Fourier, Volume 59 (2009) no. 1, pp. 347-392

[8] Thomas Dreyfus Differential algebraic generating series of weighted walks in the quarter plane, arXiv preprint arXiv:2104.05505 (2021)

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

[10] Thomas Dreyfus; Charlotte Hardouin; Julien Roques; Michael F Singer On the kernel curves associated with walks in the quarter plane, Transient Transcendence in Transylvania International Conference (2019), pp. 61-89

[11] Thomas Dreyfus; Charlotte Hardouin; Julien Roques; Michael F Singer Walks in the quarter plane: Genus zero case, Journal of Combinatorial Theory, Series A, Volume 174 (2020), p. 105251

[12] Thomas Dreyfus; Kilian Raschel Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks, Publications Mathématiques de Besançon (2019) no. 1, pp. 41-80

[13] J. Duistermaat Discrete Integrable Systems: Qrt Maps and Elliptic Surfaces, Springer Monographs in Mathematics, 304, Springer-Verlag, New York, 2010

[14] Guy Fayolle; Roudolf Iasnogorodski; Vadim Malyshev Random walks in the quarter-plane, Applications of Mathematics (New York), 40, Springer-Verlag, Berlin, 1999, xvi+156 pages (Algebraic methods, boundary value problems and applications) | DOI | MR

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

[16] Jean Fresnel; Marius van der Put Rigid analytic geometry and its applications, Progress in Mathematics, 218, Birkhäuser Boston, Inc., Boston, MA, 2004, xii+296 pages

[17] Charlotte Hardouin; Michael F. Singer Differential Galois theory of linear difference equations, Math. Ann., Volume 342 (2008) no. 2, pp. 333-377

[18] Charlotte Hardouin; Michael F Singer On differentially algebraic generating series for walks in the quarter plane, Selecta Mathematica, Volume 27 (2021) no. 5, pp. 1-49

[19] Dale Husemöller Elliptic curves. With appendices by Otto Forster, Ruth Lawrence, and Stefan Theisen, 111, New York, NY: Springer, 2004, xxi + 487 pages

[20] Manuel Kauers; Rika Yatchak Walks in the quarter plane with multiple steps, Proceedings of FPSAC 2015 (Discrete Math. Theor. Comput. Sci. Proc.) (2015), pp. 25-36

[21] E. R. Kolchin Algebraic groups and algebraic dependence, Amer. J. Math., Volume 90 (1968), pp. 1151-1164 https://doi-org.prox.lib.ncsu.edu/10.2307/2373294 | DOI | MR

[22] Ellis Robert Kolchin Differential algebra & algebraic groups, 54, Academic press, 1973

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

[24] Serge Lang Complex analysis, 103, Springer Science & Business Media, 2013

[25] Saunders MacLane The universality of formal power series fields, Bull. Am. Math. Soc., Volume 45 (1939), pp. 888-890

[26] Stephen Melczer; Marni Mishna Singularity analysis via the iterated kernel method, Combin. Probab. Comput., Volume 23 (2014) no. 5, pp. 861-888 | DOI | MR

[27] Marni Mishna; Andrew Rechnitzer Two non-holonomic lattice walks in the quarter plane, Theoret. Comput. Sci., Volume 410 (2009) no. 38-40, pp. 3616-3630 | DOI | MR

[28] Alexandre Ostrowski Sur les relations algébriques entre les intégrales indéfinies, Acta Math., Volume 78 (1946), pp. 315-318 https://doi-org.prox.lib.ncsu.edu/10.1007/BF02421605 | DOI | MR

[29] Alexey Ovchinnikov; Michael Wibmer $σ$ -Galois theory of linear difference equations, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 3962-4018

[30] Peter Roquette Analytic theory of elliptic functions over local fields, Vandenhoeck u. Ruprecht, 1970 no. 1

[31] Jacques Sauloy Systèmes aux $q$ -différences singuliers réguliers: classification, matrice de connexion et monodromie, Ann. Inst. Fourier (Grenoble), Volume 50 (2000) no. 4, pp. 1021-1071 | MR

[32] Joseph H. Silverman Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, 151, Springer-Verlag, New York, 1994

[33] Joseph H Silverman The arithmetic of elliptic curves, 106, Springer Science & Business Media, 2009

[34] Snowbird lectures in algebraic geometry. Proceedings of an AMS-IMS-SIAM joint summer research conference on algebraic geometry: Presentations by young researchers, Snowbird, UT, USA, July 4–8, 2004 (Ravi Vakil, ed.), 388, Providence, RI: American Mathematical Society (AMS), 2005

[35] Marius van der Put; Michael F. Singer Galois theory of difference equations, Lecture Notes in Mathematics, 1666, Springer-Verlag, Berlin, 1997, viii+180 pages

[36] E. T. Whittaker; G. N. Watson A course of modern analysis, Mineola, NY: Dover Publications, 2020, 613 pages

Cited by Sources: