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 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 and are associated to the ending point of the path, the variable encodes its length. In this paper, we prove that in the unweighted case, satisfies an algebraic differential relation with respect to if and only if it satisfies an algebraic differential relation with respect (resp. ). Combined with [2, 3, 4, 9, 11], we are able to characterize the -differential transcendence of the models of walks listed by Bousquet-Mélou and Mishna.
Accepté le :
Accepté après révision le :
Publié le :
Mots clés : Random walks, Difference Galois theory, Transcendence, Valued differential fields.
Thomas Dreyfus 1 ; Charlotte Hardouin 2
CC-BY-NC-ND 4.0
@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, Tome 13 (2021) no. 2, pp. 39-92. doi : 10.5802/cml.77. https://cml.centre-mersenne.org/articles/10.5802/cml.77/
[1] Asymptotic differential algebra and model theory of transseries, Annals of Mathematics Studies, 195, Princeton University Press, Princeton, NJ, 2017, xxi+849 pages
[2] Counting quadrant walks via Tutte’s invariant method, Discrete Mathematics & Theoretical Computer Science (2020)
[3] The complete generating function for Gessel walks is algebraic, Proc. Amer. Math. Soc., Volume 138 (2010) no. 9, pp. 3063-3078
[4] 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] Difference algebra, Interscience Publishers John Wiley & Sons, New York-London-Sydeny, 1965
[6] Descent for differential Galois theory of difference equations: confluence and -dependence, Pacific J. Math., Volume 256 (2012) no. 1, pp. 79-104 | DOI | MR
[7] On -summation and confluence, Ann. Inst. Fourier, Volume 59 (2009) no. 1, pp. 347-392
[8] Differential algebraic generating series of weighted walks in the quarter plane, arXiv preprint arXiv:2104.05505 (2021)
[9] On the nature of the generating series of walks in the quarter plane, Inventiones mathematicae, Volume 213 (2018) no. 1, pp. 139-203
[10] On the kernel curves associated with walks in the quarter plane, Transient Transcendence in Transylvania International Conference (2019), pp. 61-89
[11] Walks in the quarter plane: Genus zero case, Journal of Combinatorial Theory, Series A, Volume 174 (2020), p. 105251
[12] Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks, Publications Mathématiques de Besançon (2019) no. 1, pp. 41-80
[13] Discrete Integrable Systems: Qrt Maps and Elliptic Surfaces, Springer Monographs in Mathematics, 304, Springer-Verlag, New York, 2010
[14] 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] 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] Rigid analytic geometry and its applications, Progress in Mathematics, 218, Birkhäuser Boston, Inc., Boston, MA, 2004, xii+296 pages
[17] Differential Galois theory of linear difference equations, Math. Ann., Volume 342 (2008) no. 2, pp. 333-377
[18] On differentially algebraic generating series for walks in the quarter plane, Selecta Mathematica, Volume 27 (2021) no. 5, pp. 1-49
[19] Elliptic curves. With appendices by Otto Forster, Ruth Lawrence, and Stefan Theisen, 111, New York, NY: Springer, 2004, xxi + 487 pages
[20] Walks in the quarter plane with multiple steps, Proceedings of FPSAC 2015 (Discrete Math. Theor. Comput. Sci. Proc.) (2015), pp. 25-36
[21] 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] Differential algebra & algebraic groups, 54, Academic press, 1973
[23] 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] Complex analysis, 103, Springer Science & Business Media, 2013
[25] The universality of formal power series fields, Bull. Am. Math. Soc., Volume 45 (1939), pp. 888-890
[26] Singularity analysis via the iterated kernel method, Combin. Probab. Comput., Volume 23 (2014) no. 5, pp. 861-888 | DOI | MR
[27] Two non-holonomic lattice walks in the quarter plane, Theoret. Comput. Sci., Volume 410 (2009) no. 38-40, pp. 3616-3630 | DOI | MR
[28] 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] -Galois theory of linear difference equations, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 3962-4018
[30] Analytic theory of elliptic functions over local fields, Vandenhoeck u. Ruprecht, 1970 no. 1
[31] Systèmes aux -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] Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, 151, Springer-Verlag, New York, 1994
[33] 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] Galois theory of difference equations, Lecture Notes in Mathematics, 1666, Springer-Verlag, Berlin, 1997, viii+180 pages
[36] A course of modern analysis, Mineola, NY: Dover Publications, 2020, 613 pages
Cité par Sources :