Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

On the computation of the Galois group of linear difference equations


Author: Ruyong Feng
Journal: Math. Comp. 87 (2018), 941-965
MSC (2010): Primary 39A06, 12H10, 68W30
DOI: https://doi.org/10.1090/mcom/3232
Published electronically: June 27, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)

  • [1] Thomas Becker and Volker Weispfenning, Gröbner Bases: A Computational Approach to Commutative Algebra, Graduate Texts in Mathematics, vol. 141, Springer-Verlag, New York, 1993. MR 1213453
  • [2] 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.
  • [3] Elie Compoint and Michael F. Singer, Computing Galois groups of completely reducible differential equations, J. Symbolic Comput. 28 (1999), no. 4-5, 473-494. MR 1731934, https://doi.org/10.1006/jsco.1999.0311
  • [4] 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, https://doi.org/10.1007/s00200-005-0192-x
  • [5] David Cox, John Little, and Donal O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. MR 1417938
  • [6] Harm Derksen, Emmanuel Jeandel, and Pascal Koiran, Quantum automata and algebraic groups, J. Symbolic Comput. 39 (2005), no. 3-4, 357-371. MR 2168287, https://doi.org/10.1016/j.jsc.2004.11.008
  • [7] 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, https://doi.org/10.3842/SIGMA.2015.003
  • [8] David Eisenbud, Craig Huneke, and Wolmer Vasconcelos, Direct methods for primary decomposition, Invent. Math. 110 (1992), no. 2, 207-235. MR 1185582, https://doi.org/10.1007/BF01231331
  • [9] 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, https://doi.org/10.1016/j.aam.2015.01.001
  • [10] 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. MR 988410, https://doi.org/10.1016/S0747-7171(88)80040-3
  • [11] 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. MR 1457845, https://doi.org/10.1016/S0022-4049(97)00017-0
  • [12] 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, https://doi.org/10.1006/jsco.1998.0223
  • [13] James E. Humphreys, Linear Algebraic Groups, Springer-Verlag, New York-Heidelberg, 1975. Graduate Texts in Mathematics, No. 21. MR 0396773
  • [14] Ehud Hrushovski, Computing the Galois group of a linear differential equation, Differential Galois theory (Bedlewo, 2001) Banach Center Publ., vol. 58, Polish Acad. Sci., Warsaw, 2002, pp. 97-138. MR 1972449, https://doi.org/10.4064/bc58-0-9
  • [15] 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, https://doi.org/10.1016/j.jsc.2012.05.015
  • [16] 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, https://doi.org/10.1016/j.jsc.2008.03.002
  • [17] Jerald J. Kovacic, An algorithm for solving second order linear homogeneous differential equations, J. Symbolic Comput. 2 (1986), no. 1, 3-43. MR 839134, https://doi.org/10.1016/S0747-7171(86)80010-4
  • [18] Andy R. Magid, Finite generation of class groups of rings of invariants, Proc. Amer. Math. Soc. 60 (1976), 45-48 (1977). MR 0427306
  • [19] Annette Maier, A difference version of Nori's theorem, Math. Ann. 359 (2014), no. 3-4, 759-784. MR 3231015, https://doi.org/10.1007/s00208-014-1012-z
  • [20] Marko Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symbolic Comput. 14 (1992), no. 2-3, 243-264. MR 1187234, https://doi.org/10.1016/0747-7171(92)90038-6
  • [21] Antonio Montes and Michael Wibmer, Gröbner bases for polynomial systems with parameters, J. Symbolic Comput. 45 (2010), no. 12, 1391-1425. MR 2733386, https://doi.org/10.1016/j.jsc.2010.06.017
  • [22] Rettstadt, D. On the computation of the differential Galois group, Ph.D. thesis, RWTH Aachen University, 2014.
  • [23] J. Roques, On the algebraic relations between Mahler functions, 2015, https://www-fourier.ujf-grenoble.fr/˜jroques/mahler.pdf.
  • [24] Julien Roques, Galois groups of the basic hypergeometric equations, Pacific J. Math. 235 (2008), no. 2, 303-322. MR 2386226, https://doi.org/10.2140/pjm.2008.235.303
  • [25] Maxwell Rosenlicht, Toroidal algebraic groups, Proc. Amer. Math. Soc. 12 (1961), 984-988. MR 0133328
  • [26] A. Seidenberg, Constructions in algebra, Trans. Amer. Math. Soc. 197 (1974), 273-313. MR 0349648
  • [27] 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, https://doi.org/10.1006/jsco.1993.1032
  • [28] Michael F. Singer, Algebraic relations among solutions of linear differential equations, Trans. Amer. Math. Soc. 295 (1986), no. 2, 753-763. MR 833707, https://doi.org/10.2307/2000062
  • [29] M. F. Singer Algebraic and Algorithmic Aspects of Difference Equations, Lecture notes at CIMPA conference in Santa Marta Columbia, 2012.
  • [30] A. Suzuki and Y. Sato, A simple algorithm to compute comprehensive Gröbner bases, ISSAC 2006 (2006), 326-331.
  • [31] 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
  • [32] Volker Weispfenning, Comprehensive Gröbner bases, J. Symbolic Comput. 14 (1992), no. 1, 1-29. MR 1177987, https://doi.org/10.1016/0747-7171(92)90023-W

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 39A06, 12H10, 68W30

Retrieve articles in all journals with MSC (2010): 39A06, 12H10, 68W30


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
Email: ryfeng@amss.ac.cn

DOI: https://doi.org/10.1090/mcom/3232
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)
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society