On the computation of the Galois group of linear difference equations

Feng, Ruyong

doi:10.1090/mcom/3232

On the computation of the Galois group of linear difference equations
HTML articles powered by AMS MathViewer

by Ruyong Feng PDF

Math. Comp. 87 (2018), 941-965 Request permission

Abstract:

We present an algorithm that determines the Galois group of linear difference equations with rational function coefficients.

References

Thomas Becker and Volker Weispfenning, Gröbner bases, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. A computational approach to commutative algebra; In cooperation with Heinz Kredel. MR 1213453, DOI 10.1007/978-1-4612-0913-3
M. A. Barkatou, T. Cluzeau, L. Di Vizio and J. A. Weil, Computing the Lie algebra of the differential Galois group of a linear differential system, ISSAC’16 (2016), 63-70.
Elie Compoint and Michael F. Singer, Computing Galois groups of completely reducible differential equations, J. Symbolic Comput. 28 (1999), no. 4-5, 473–494. Differential algebra and differential equations. MR 1731934, DOI 10.1006/jsco.1999.0311
Thomas Cluzeau and Mark van Hoeij, Computing hypergeometric solutions of linear recurrence equations, Appl. Algebra Engrg. Comm. Comput. 17 (2006), no. 2, 83–115. MR 2233774, DOI 10.1007/s00200-005-0192-x
David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. An introduction to computational algebraic geometry and commutative algebra. MR 1417938
Harm Derksen, Emmanuel Jeandel, and Pascal Koiran, Quantum automata and algebraic groups, J. Symbolic Comput. 39 (2005), no. 3-4, 357–371. MR 2168287, DOI 10.1016/j.jsc.2004.11.008
Thomas Dreyfus and Julien Roques, Galois groups of difference equations of order two on elliptic curves, SIGMA Symmetry Integrability Geom. Methods Appl. 11 (2015), Paper 003, 23. MR 3313679, DOI 10.3842/SIGMA.2015.003
David Eisenbud, Craig Huneke, and Wolmer Vasconcelos, Direct methods for primary decomposition, Invent. Math. 110 (1992), no. 2, 207–235. MR 1185582, DOI 10.1007/BF01231331
Ruyong Feng, Hrushovski’s algorithm for computing the Galois group of a linear differential equation, Adv. in Appl. Math. 65 (2015), 1–37. MR 3320755, DOI 10.1016/j.aam.2015.01.001
Patrizia Gianni, Barry Trager, and Gail Zacharias, Gröbner bases and primary decomposition of polynomial ideals, J. Symbolic Comput. 6 (1988), no. 2-3, 149–167. Computational aspects of commutative algebra. MR 988410, DOI 10.1016/S0747-7171(88)80040-3
Peter A. Hendriks, An algorithm for computing a standard form for second-order linear $q$-difference equations, J. Pure Appl. Algebra 117/118 (1997), 331–352. Algorithms for algebra (Eindhoven, 1996). MR 1457845, DOI 10.1016/S0022-4049(97)00017-0
Peter A. Hendriks, An algorithm determining the difference Galois group of second order linear difference equations, J. Symbolic Comput. 26 (1998), no. 4, 445–461. MR 1646675, DOI 10.1006/jsco.1998.0223
James E. Humphreys, Linear algebraic groups, Graduate Texts in Mathematics, No. 21, Springer-Verlag, New York-Heidelberg, 1975. MR 0396773
Ehud Hrushovski, Computing the Galois group of a linear differential equation, Differential Galois theory (Będlewo, 2001) Banach Center Publ., vol. 58, Polish Acad. Sci. Inst. Math., Warsaw, 2002, pp. 97–138. MR 1972449, DOI 10.4064/bc58-0-9
Deepak Kapur, Yao Sun, and Dingkang Wang, An efficient method for computing comprehensive Gröbner bases, J. Symbolic Comput. 52 (2013), 124–142. MR 3018131, DOI 10.1016/j.jsc.2012.05.015
Manuel Kauers and Burkhard Zimmermann, Computing the algebraic relations of $C$-finite sequences and multisequences, J. Symbolic Comput. 43 (2008), no. 11, 787–803. MR 2432957, DOI 10.1016/j.jsc.2008.03.002
Jerald J. Kovacic, An algorithm for solving second order linear homogeneous differential equations, J. Symbolic Comput. 2 (1986), no. 1, 3–43. MR 839134, DOI 10.1016/S0747-7171(86)80010-4
Andy R. Magid, Finite generation of class groups of rings of invariants, Proc. Amer. Math. Soc. 60 (1976), 45–48 (1977). MR 427306, DOI 10.1090/S0002-9939-1976-0427306-0
Annette Maier, A difference version of Nori’s theorem, Math. Ann. 359 (2014), no. 3-4, 759–784. MR 3231015, DOI 10.1007/s00208-014-1012-z
Marko Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Comput. 14 (1992), no. 2-3, 243–264. MR 1187234, DOI 10.1016/0747-7171(92)90038-6
Antonio Montes and Michael Wibmer, Gröbner bases for polynomial systems with parameters, J. Symbolic Comput. 45 (2010), no. 12, 1391–1425. MR 2733386, DOI 10.1016/j.jsc.2010.06.017
Rettstadt, D. On the computation of the differential Galois group, Ph.D. thesis, RWTH Aachen University, 2014.
J. Roques, On the algebraic relations between Mahler functions, 2015, https://www-fourier.ujf-grenoble.fr/˜jroques/mahler.pdf.
Julien Roques, Galois groups of the basic hypergeometric equations, Pacific J. Math. 235 (2008), no. 2, 303–322. MR 2386226, DOI 10.2140/pjm.2008.235.303
Maxwell Rosenlicht, Toroidal algebraic groups, Proc. Amer. Math. Soc. 12 (1961), 984–988. MR 133328, DOI 10.1090/S0002-9939-1961-0133328-9
A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273–313. MR 349648, DOI 10.1090/S0002-9947-1974-0349648-2
Michael F. Singer and Felix Ulmer, Galois groups of second and third order linear differential equations, J. Symbolic Comput. 16 (1993), no. 1, 9–36. MR 1237348, DOI 10.1006/jsco.1993.1032
Michael F. Singer, Algebraic relations among solutions of linear differential equations, Trans. Amer. Math. Soc. 295 (1986), no. 2, 753–763. MR 833707, DOI 10.1090/S0002-9947-1986-0833707-X
M. F. Singer Algebraic and Algorithmic Aspects of Difference Equations, Lecture notes at CIMPA conference in Santa Marta Columbia, 2012.
A. Suzuki and Y. Sato, A simple algorithm to compute comprehensive Gröbner bases, ISSAC 2006 (2006), 326-331.
Marius van der Put and Michael F. Singer, Galois theory of difference equations, Lecture Notes in Mathematics, vol. 1666, Springer-Verlag, Berlin, 1997. MR 1480919, DOI 10.1007/BFb0096118
Volker Weispfenning, Comprehensive Gröbner bases, J. Symbolic Comput. 14 (1992), no. 1, 1–29. MR 1177987, DOI 10.1016/0747-7171(92)90023-W