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

Dreyfus, Thomas; Hardouin, Charlotte

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

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.

Classification : 05A15, 30D05, 39A06
Mots clés : Random walks, Difference Galois theory, Transcendence, Valued differential fields.

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

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

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

[4] Bousquet-Mélou, Mireille; Mishna, Marni 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] Cohn, Richard M. Difference algebra, Interscience Publishers John Wiley & Sons, New York-London-Sydeny, 1965

[6] Di Vizio, Lucia; Hardouin, Charlotte 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] Di Vizio, Lucia; Zhang, Changgui On $q$-summation and confluence, Ann. Inst. Fourier, Volume 59 (2009) no. 1, pp. 347-392

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

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

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

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

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

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

[14] Fayolle, Guy; Iasnogorodski, Roudolf; Malyshev, Vadim 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] Fayolle, Guy; Raschel, Kilian 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] Fresnel, Jean; van der Put, Marius Rigid analytic geometry and its applications, Progress in Mathematics, 218, Birkhäuser Boston, Inc., Boston, MA, 2004, xii+296 pages

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

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

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

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

[21] Kolchin, E. R. 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] Kolchin, Ellis Robert Differential algebra & algebraic groups, 54, Academic press, 1973

[23] Kurkova, Irina; Raschel, Kilian 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] Lang, Serge Complex analysis, 103, Springer Science & Business Media, 2013

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

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

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

[28] Ostrowski, Alexandre 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] Ovchinnikov, Alexey; Wibmer, Michael $\sigma$-Galois theory of linear difference equations, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 3962-4018

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

[31] Sauloy, Jacques 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] Silverman, Joseph H. Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, 151, Springer-Verlag, New York, 1994

[33] Silverman, Joseph H 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 (Vakil, Ravi, ed.), 388, Providence, RI: American Mathematical Society (AMS), 2005

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

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