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
Additional Information
- Ruyong Feng
- Affiliation: KLMM, Academy of Mathematics and Systems Science, Chinese Academy of Sciences and UCAS, Chinese Academy of Sciences, Beijing 100190, People’s Republic of China
- MR Author ID: 756535
- Email: ryfeng@amss.ac.cn
- Received by editor(s): June 2, 2015
- Received by editor(s) in revised form: September 2, 2016, and September 20, 2016
- Published electronically: June 27, 2017
- Additional Notes: This work was partially supported by a National Key Basic Research Project of China (2011CB302400) and by a grant from NSFC (11371143)
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 941-965
- MSC (2010): Primary 39A06, 12H10, 68W30
- DOI: https://doi.org/10.1090/mcom/3232
- MathSciNet review: 3739224