An upper bound and finiteness criteria for the Galois group of weighted walks with rational coefficients in the quarter plane

Jiang, Ruichao; Tavakoli, Javad; Zhao, Yiqiang

Comptes Rendus. Mathématique, Tome 359 (2021) no. 5, pp. 563-576.

En utilisant le théorème de Mazur sur les torsions de courbes elliptiques, on obtient un majorant 24 pour l’ordre du groupe fini de Galois $\mathscr{H}$ associé aux marches pondérées dans le quart de plan ${\mathbb{Z}}_{+}^2$. Le critère explicite pour que $\mathscr{H}$ soit d’ordre 4 ou 6 est obtenu par un simple argument géométrique. En utilisant des polynômes de division, un critère récursif pour $\mathscr{H}$ d’ordre $4m$ ou $4m+2$ est également obtenu. Comme corollaire, un critère explicite pour que $\mathscr{H}$ soit d’ordre 8 est donné et est beaucoup plus simple que la méthode existante.

Using Mazur’s theorem on torsions of elliptic curves, an upper bound 24 for the order of the finite Galois group $\mathscr{H}$ associated with weighted walks in the quarter plane ${\mathbb{Z}}_{+}^2$ is obtained. The explicit criterion for $\mathscr{H}$ to have order 4 or 6 is rederived by simple geometric arguments. Using division polynomials, a recursive criterion for $\mathscr{H}$ to have order $4m$ or $4m+2$ is also obtained. As a corollary, an explicit criterion for $\mathscr{H}$ to have order 8 is given through a method simpler than the existing one.

[1] Billing, Gunnar; Mahler, Kurt On exceptional points on cubic curves, J. Lond. Math. Soc., Volume s1-15 (1940) no. 1, pp. 32-43 | DOI | MR | Zbl

[2] Bousquet-Mélou, Mireille; Mishna, Marni Walks with small steps in the quarter plane, Algorithmic probability and combinatorics (Contemporary Mathematics), Volume 520, American Mathematical Society, 2010, pp. 1-40 | DOI | MR | Zbl

[3] Dreyfus, Thomas; Raschel, Kilian Differential transcendence & algebraicity criteria for the series counting weighted quadrant walks, Publ. Math. Besançon, Algèbre Théorie Nombres, Volume 1 (2019), pp. 41-80 | Numdam | Zbl

[4] Duistermaat, Johannes J. Discrete integrable systems. QRT maps and elliptic surfaces, Springer Monographs in Mathematics, Springer, 2010 | Zbl

[5] Fayolle, Guy; Iasnogorodski, Roudolf Random walks in the quarter-plane: Advances in explicit criterions for the finiteness of the associated group in the genus 1 case, Markov Process. Relat. Fields, Volume 21 (2015) no. 4, pp. 1005-1032 | MR

[6] Fayolle, Guy; Iasnogorodski, Roudolf; Malyshev, Vadim Random walks in the quarter plane, Probability Theory and Stochastic Modelling, 40, Springer, 2017 | MR | Zbl

[7] Fayolle, Guy; Raschel, Kilian 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

[8] Fayolle, Guy; Raschel, Kilian 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

[9] Flatto, Leopold Two parallel queues created by arrivals with two demands. II, SIAM J. Appl. Math., Volume 45 (1985) no. 5, pp. 861-878 | DOI | MR | Zbl

[10] Flatto, Leopold; Hahn, S. Two parallel queues created by arrivals with two demands. I, SIAM J. Appl. Math., Volume 44 (1984) no. 5, pp. 1041-1053 | DOI | MR | Zbl

[11] Hopf, H. Vektorfelder in n-dimensionalen Mannifaltigkeiten, Math. Ann., Volume 96 (1927) no. 1, pp. 225-249 | DOI

[12] Kauers, Manuel; Yatchak, Rika Walks in the quarter plane with multiple steps, Proceedings of FPSAC (Discrete Mathematics & Theoretical Computer Science), The Association DMTCS (2015), pp. 25-36 | Zbl

[13] Kurkova, Irina; Raschel, Kilian Explicit expression for the generating function counting Gessel’s walks, Adv. Appl. Math., Volume 47 (2011) no. 3, pp. 414-433 | DOI | MR | Zbl

[14] Malyshev, Vadim Positive random walks and Galois theory, Usp. Mat. Nauk, Volume 1 (1971), pp. 227-228 | MR

[15] Mazur, Barry Modular curves and the Eisenstein ideal, Publ. Math., Inst. Hautes Étud. Sci., Volume 47 (1977), pp. 33-186 | DOI | Numdam | Zbl

[16] Mazur, Barry Rational isogenies of prime degree, Invent. Math., Volume 44 (1978), p. 129 | DOI

[17] Mazur, Barry; Tate, John T. Points of order 13 on elliptic curves, Invent. Math., Volume 22 (1973) no. 1, pp. 41-49 | DOI | MR | Zbl

[18] Silverman, Joseph H. The arithmetic of elliptic curves, Graduate Texts in Mathematics, 106, Springer, 2009 | MR | Zbl

[19] Silverman, Joseph H.; Tate, John T. Rational points on elliptic curves, Undergraduate Texts in Mathematics, Springer, 2015 | Zbl