On differentially algebraic generating series for walks in the quarter plane. (English) Zbl 1476.05013
Summary: We refine necessary and sufficient conditions for the generating series of a weighted model of a quarter plane walk to be differentially algebraic. In addition, we give algorithms based on the theory of Mordell-Weil lattices, that, for each weighted model, yield polynomial conditions on the weights determining this property of the associated generating series.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 60G50 | Sums of independent random variables; random walks |
| 11G05 | Elliptic curves over global fields |
| 30D05 | Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable |
| 39A06 | Linear difference equations |
Keywords:
lattice walks; Mordell-Weil lattices; Kodaira-Néron model; random walks; generating functions; difference Galois theory; elliptic functions; transcendence; Néron-Tate heightReferences:
| [1] | Bostan, A.; Bousquet-Mélou, M.; Kauers, M.; Melczer, S., On 3-dimensional lattice walks confined to the positive octant, Ann. Comb., 20, 4, 661-704 (2016) · Zbl 1354.05006 · doi:10.1007/s00026-016-0328-7 |
| [2] | Bernardi, O., Bousquet-Mélou, M., Raschel, K.: Counting quadrant walks via Tutte’s invariant method, An extended abstract to appear In: Proceedings of FPSAC 2016, Discrete Math. Theor. Comput. Sci. Proc., arXiv:1511.04298 (2015) · Zbl 1440.05019 |
| [3] | Bernardi, O., Bousquet-Mélou, M., Raschel, K.: Counting quadrant walks via Tutte’s invariant method. Preprint arXiv:1708.08215 (2017) · Zbl 1440.05019 |
| [4] | Bostan, A., Chen, S., Chyzak, F., Li, Z.: Complexity of creative telescoping for bivariate rational functions. In: ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, pp. 203-210 (2010) · Zbl 1321.68524 |
| [5] | Bostan, A.; Chyzac, F.; Jiménez-Pastor, A.; Lairez, P., The Sage Package comb_walks for walks in the quarter plane, ACM Commun. Comput. Algebra, 54, 2, 30-37 (2020) · Zbl 1499.68417 · doi:10.1145/3427218.3427220 |
| [6] | Banderier, C., Flajolet, P.: Basic analytic combinatorics of directed lattice paths, vol. 281, Selected papers in honour of Maurice Nivat, pp. 37-80 (2002) · Zbl 0996.68126 |
| [7] | Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane, Algorithmic probability and combinatorics, Contemp. Math., vol. 520, Amer. Math. Soc., Providence, RI, pp. 1-39 (2010) · Zbl 1209.05008 |
| [8] | Bostan, A.; Raschel, K.; Salvy, B., Non-D-finite excursions in the quarter plane, J. Comb. Theory Ser. A, 121, 45-63 (2014) · Zbl 1279.05003 · doi:10.1016/j.jcta.2013.09.005 |
| [9] | Bostan, A.; van Hoeij, M.; Kauers, M., The complete generating function for Gessel walks is algebraic, Proc. Am. Math. Soc., 138, 9, 3063-3078 (2010) · Zbl 1206.05013 · doi:10.1090/S0002-9939-2010-10398-2 |
| [10] | Chevalley, C.: Introduction to the theory of algebraic functions of one variable, Mathematical Surveys. American Mathematical Society, Providence, R.I, No. VI (1963) |
| [11] | Courtiel, J.; Melczer, S.; Mishna, M.; Raschel, K., Weighted lattice walks and universality classes, J. Comb. Theory Ser. A, 152, 255-302 (2017) · Zbl 1369.05011 · doi:10.1016/j.jcta.2017.06.008 |
| [12] | Chen, S.; Singer, MF, Residues and telescopers for bivariate rational functions, Adv. Appl. Math., 49, 2, 111-133 (2012) · Zbl 1248.33042 · doi:10.1016/j.aam.2012.04.003 |
| [13] | Dreyfus, T.: Differential algebraic generating series of weighted walks in the quarter plane, arXiv:2104.05505 (2021) |
| [14] | Dreyfus, T., Hardouin, C.: Length derivative of the generating series of walks confined in the quarter plane, arXiv:1902.10558 (2019) |
| [15] | Dreyfus, T., Hardouin, C., Roques, J., Singer, M.F.: On the nature of the generating series of walks in the quarter plane. Inventiones mathematicae 139-203 (2018) · Zbl 1392.05007 |
| [16] | Dreyfus, T., Hardouin, C., Roques, J., Singer, M.F.: Walks on the quarter plane, genus zero case, to appear in Journal of Combinatorial Theory A (2019) · Zbl 1439.05015 |
| [17] | Dreyfus, T., Hardouin, C., Roques, J., Singer, M.F.: On the kernel curves associated with walks in the quarter plane, preprint, arXiv:2004.01035 (2020) · Zbl 1439.05015 |
| [18] | Dreyfus, T., Raschel, K.: Differential transcendence and algebraicity criteria for the series counting weighted quadrant walks. Publications mathematiques de Besancon no. 1, 41-80 (2019) · Zbl 1468.12004 |
| [19] | Duistermaat, J., Discrete Integrable Systems: QRT Maps and Elliptic Surfaces, Springer Monographs in Mathematics (2010), New York: Springer, New York · Zbl 1219.14001 · doi:10.1007/978-0-387-72923-7 |
| [20] | Fayolle, G., Iasnogorodski, R., Malyshev, V.: Random walks in the quarter plane. Algebraic methods, boundary value problems, applications to queueing systems and analytic combinatorics. 2nd edition, previously published with the subtitle Algebraic methods, boundary value problems and applications., vol. 40, Cham: Springer (2017) (English) · Zbl 1386.60004 |
| [21] | Hardouin, C., Singer, M.F.: Maple code for the examples linked to On differentially algebraic generating series for walks in the quarter plane, https://singer.math.ncsu.edu/ms_papers2.html (2020) |
| [22] | Hartshorne, R., Algebraic Geometry, Graduate Texts in Mathematics (1977), New York: Springer, New York · Zbl 0367.14001 · doi:10.1007/978-1-4757-3849-0 |
| [23] | Humphreys, K., A history and a survey of lattice path enumeration, J. Stat. Plan. Inference, 140, 8, 2237-2254 (2010) · Zbl 1204.05015 · doi:10.1016/j.jspi.2010.01.020 |
| [24] | Ishizaki, K., Hypertranscendency of meromorphic solutions of a linear functional equation, Aequationes Math., 56, 3, 271-283 (1998) · Zbl 0932.39020 · doi:10.1007/s000100050062 |
| [25] | Jiang, R., Tavakoli, J., Zhao, Y.: An upper bound and criteria for the galois groupof weighted walks with rational coefficients in thequarter plane, arXiv:2008.11101 (2017) |
| [26] | Kodaira, K., On the structure of compact complex analytic surfaces. I, Am. J. Math., 86, 751-798 (1964) · Zbl 0137.17501 · doi:10.2307/2373157 |
| [27] | Kodaira, K., On the structure of compact complex analytic surfaces II, Am. J. Math., 88, 682-721 (1966) · Zbl 0193.37701 · doi:10.2307/2373150 |
| [28] | Kurkova, I.; Raschel, K., On the functions counting walks with small steps in the quarter plane, Publ. Math. Inst. Hautes Études Sci., 116, 69-114 (2012) · Zbl 1255.05012 · doi:10.1007/s10240-012-0045-7 |
| [29] | Kauers, M., Yatchak, R.: 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, pp. 25-36 (2015) · Zbl 1335.05012 |
| [30] | Lang, S.: Algebra, 2nd edn. Addison-Wesley Publishing Company, Advanced Book Program (1984) · Zbl 0712.00001 |
| [31] | Melczer, S.; Mishna, M., Singularity analysis via the iterated kernel method, Comb. Probab. Comput., 23, 5, 861-888 (2014) · Zbl 1298.05026 · doi:10.1017/S0963548314000145 |
| [32] | Mishna, M.; Rechnitzer, A., Two non-holonomic lattice walks in the quarter plane, Theor. Comput. Sci., 410, 38-40, 3616-3630 (2009) · Zbl 1228.05038 · doi:10.1016/j.tcs.2009.04.008 |
| [33] | Néron, A.: Modèles minimaux des variétés abéliennes sur les corps locaux et globaux. Inst. Hautes Études Sci. Publ. Math. no. 21, 128 (1964) · Zbl 0132.41403 |
| [34] | Oguiso, K.; Shioda, T., The Mordell-Weil lattice of a rational elliptic surface, Comment. Math. Univ. St. Paul., 40, 1, 83-99 (1991) · Zbl 0757.14011 |
| [35] | Shafarevich, I.R.: Basic algebraic geometry. 1: Varieties in projective space. Transl. from the Russian by Miles Reid. 3rd ed., 3rd ed. ed., Berlin: Springer (2013) · Zbl 1273.14004 |
| [36] | Shioda, T., On the Mordell-Weil lattices, Comment. Math. Univ. St. Paul., 39, 2, 211-240 (1990) · Zbl 0725.14017 |
| [37] | Silverman, JH, Advanced Topics in the Arithmetic of Elliptic Curves, Graduate Texts in Mathematics (1994), New York: Springer, New York · Zbl 0911.14015 · doi:10.1007/978-1-4612-0851-8 |
| [38] | Schütt, M., Shioda, T.: Elliptic surfaces, Algebraic geometry in East Asia-Seoul, : Adv. Stud. Pure Math., vol. 60, Math. Soc. Japan, Tokyo 2010, 51-160 (2008) · Zbl 1216.14036 |
| [39] | Schütt, M., Shioda, T.: Mordell-Weil lattices, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 70, Springer, Singapore (2019) · Zbl 1433.14002 |
| [40] | Tate, J.: Algorithm for determining the type of a singular fiber in an elliptic pencil, Modular functions of one variable, IV (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972), pp. 33-52. Lecture Notes in Math., Vol. 476. (1975) · Zbl 1214.14020 |
| [41] | Tsuda, T., Integrable mappings via rational elliptic surfaces, J. Phys. A, 37, 7, 2721-2730 (2004) · Zbl 1060.14051 · doi:10.1088/0305-4470/37/7/014 |
| [42] | Wilf, HS; Zeilberger, D., Rational functions certify combinatorial identities, J. Am. Math. Soc., 3, 1, 147-158 (1990) · Zbl 0695.05004 · doi:10.1090/S0894-0347-1990-1007910-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
