Degree bound for toric envelope of a linear algebraic group

Amzallag, Eli; Minchenko, Andrei; Pogudin, Gleb

doi:10.1090/mcom/3695

Degree bound for toric envelope of a linear algebraic group
HTML articles powered by AMS MathViewer

by Eli Amzallag, Andrei Minchenko and Gleb Pogudin HTML | PDF

Math. Comp. 91 (2022), 1501-1519 Request permission

Abstract:

Algorithms working with linear algebraic groups often represent them via defining polynomial equations. One can always choose defining equations for an algebraic group to be of degree at most the degree of the group as an algebraic variety. However, the degree of a linear algebraic group $G \subset \operatorname {GL}_n(C)$ can be arbitrarily large even for $n = 1$. One of the key ingredients of Hrushovski’s algorithm for computing the Galois group of a linear differential equation was an idea to “approximate” every algebraic subgroup of $\operatorname {GL}_n(C)$ by a “similar” group so that the degree of the latter is bounded uniformly in $n$. Making this uniform bound computationally feasible is crucial for making the algorithm practical.

In this paper, we derive a single-exponential degree bound for such an approximation (we call it a toric envelope), which is qualitatively optimal. As an application, we improve the quintuply exponential bound due to Feng for the first step of Hrushovski’s algorithm to a single-exponential bound. For the cases $n = 2, 3$ often arising in practice, we further refine our general bound.

References

Moulay Barkatou, Thomas Cluzeau, Jacques-Arthur Weil, and Lucia Di Vizio, Computing the Lie algebra of the differential Galois group of a linear differential system, Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2016, pp. 63–70. MR 3565698, DOI 10.1145/2930889.2930932
Frits Beukers, Differential Galois theory, From number theory to physics (Les Houches, 1989) Springer, Berlin, 1992, pp. 413–439. MR 1221107
Armand Borel, Linear algebraic groups, 2nd ed., Springer-Verlag, New York, 1991., DOI 10.1007/978-1-4612-0941-6
Michel Brion, Groupe de Picard et nombres caractéristiques des variétés sphériques, Duke Math. J. 58 (1989), no. 2, 397–424.
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
Charles W. Curtis and Irving Reiner, Representation theory of finite groups and associative algebras, Pure and Applied Mathematics, Vol. XI, Interscience Publishers (a division of John Wiley & Sons, Inc.), New York-London, 1962. MR 0144979
Willem Adriaan de Graaf, Computation with linear algebraic groups, Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2017. MR 3675415, DOI 10.1201/9781315120140
Harm Derksen, Computation of invariants for reductive groups, Adv. Math. 141 (1999), no. 2, 366–384., DOI 10.1006/aima.1998.1787
Harm Derksen, Polynomial bounds for rings of invariants, Proc. Am. Math. Soc. 129 (2001), 955–963., DOI 10.1090/S0002-9939-00-05698-7
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
Julia Hartmann, On the inverse problem in differential Galois theory, J. Reine Angew. Math. 586 (2005), 21–44. MR 2180599, DOI 10.1515/crll.2005.2005.586.21
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 0463157, DOI 10.1007/978-1-4757-3849-0
Joos Heintz, Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci. 24 (1983), no. 3, 239–277. MR 716823, DOI 10.1016/0304-3975(83)90002-6
Gerhard P. Hochschild, Basic theory of algebraic groups and Lie algebras, Graduate Texts in Mathematics, vol. 75, Springer-Verlag, New York-Berlin, 1981. MR 620024, DOI 10.1007/978-1-4613-8114-3
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
Nathan Jacobson, Lie algebras, Dover Publications, Inc., New York, 1979. Republication of the 1962 original. MR 559927
Gabriela Jeronimo and Juan Sabia, Effective equidimensional decomposition of affine varieties, J. Pure Appl. Algebra 169 (2002), no. 2-3, 229–248. MR 1897345, DOI 10.1016/S0022-4049(01)00083-4
M. Camille Jordan, Mémoire sur les équations différentielles linéaires à intégrale algébrique, J. Reine Angew. Math. 84 (1878), 89–215. MR 1581645, DOI 10.1515/crelle-1878-18788408
B. Ya. Kazarnovskiĭ, Newton polyhedra and Bezout’s formula for matrix functions of finite-dimensional representations, Funktsional. Anal. i Prilozhen. 21 (1987), no. 4, 73–74 (Russian). MR 925078
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
G. A. Miller, H. F. Blichfeldt, and L. E. Dickson, Theory and applications of finite groups, Dover Publications, Inc., New York, 1961. MR 0123600
Andrey Minchenko, Alexey Ovchinnikov, and Michael F. Singer, Unipotent differential algebraic groups as parameterized differential Galois groups, J. Inst. Math. Jussieu 13 (2014), no. 4, 671–700. MR 3249687, DOI 10.1017/S1474748013000200
Andrey Minchenko, Alexey Ovchinnikov, and Michael F. Singer, Reductive linear differential algebraic groups and the Galois groups of parameterized linear differential equations, Int. Math. Res. Not. IMRN 7 (2015), 1733–1793. MR 3335233, DOI 10.1093/imrn/rnt344
C. Mitschi and M. F. Singer, Connected linear groups as differential Galois groups, J. Algebra 184 (1996), no. 1, 333–361. MR 1402584, DOI 10.1006/jabr.1996.0263
Alexey Bolsinov, Juan J. Morales-Ruiz, and Nguyen Tien Zung, Geometry and dynamics of integrable systems, Advanced Courses in Mathematics. CRM Barcelona, Birkhäuser/Springer, Cham, 2016. Lecture notes from the advanced course held at the Centre de Recerca Matemàtica (CRM), Barcelona, September 2013; Edited by Vladimir Matveev and Eva Miranda. MR 3470212, DOI 10.1007/978-3-319-33503-2
Morris Newman, Integral matrices, Pure and Applied Mathematics, Vol. 45, Academic Press, New York-London, 1972. MR 0340283
A. L. Onishchik and È. B. Vinberg, Lie groups and algebraic groups, Springer Series in Soviet Mathematics, Springer-Verlag, Berlin, 1990. Translated from the Russian and with a preface by D. A. Leites. MR 1064110, DOI 10.1007/978-3-642-74334-4
Daniel Rettstadt, On the computation of the differential Galois group, Ph.D. Thesis, RWTH Aachen University, 2014. Available at http://publications.rwth-aachen.de/record/444974/files/5181.pdf.
Javier Carrasco Serrano, Finite subgroups of $\sl (2, \mathbb {C})$ and $\sl (3, \mathbb {C})$, Ph.D. Thesis, The University of Warwick, 2014. Available at https://homepages.warwick.ac.uk/~masda/McKay/Carrasco_Project.pdf.
Michael F. Singer, Moduli of linear differential equations on the Riemann sphere with fixed Galois groups, Pacific J. Math. 160 (1993), no. 2, 343–395. MR 1233356, DOI 10.2140/pjm.1993.160.343
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
Mengxiao Sun, A new bound on Hrushovski’s algorithm for computing the Galois group of a linear differential equation, Comm. Algebra 47 (2019), no. 9, 3553–3566. MR 3969464, DOI 10.1080/00927872.2019.1567750
Ken-Ichi Tahara, On the finite subgroups of $\mathrm {GL} (3,\mathbb {Z})$, Nagoya Math. J. 41 (1971), 169–209., DOI 10.1017/S002776300001415X
Carol Tretkoff and Marvin Tretkoff, Solution of the inverse problem of differential Galois theory in the classical case, Amer. J. Math. 101 (1979), no. 6, 1327–1332. MR 548884, DOI 10.2307/2374143
Joris van der Hoeven, Around the numeric-symbolic computation of differential Galois groups, J. Symbolic Comput. 42 (2007), no. 1-2, 236–264. MR 2284295, DOI 10.1016/j.jsc.2006.03.007
Marius van der Put and Michael F. Singer, Galois theory of linear differential equations, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 328, Springer-Verlag, Berlin, 2003. MR 1960772, DOI 10.1007/978-3-642-55750-7
Mark van Hoeij and Jacques-Arthur Weil, An algorithm for computing invariants of differential Galois groups, J. Pure Appl. Algebra 117/118 (1997), 353–379. Algorithms for algebra (Eindhoven, 1996). MR 1457846, DOI 10.1016/S0022-4049(97)00018-2
E. P. Vdovin, Maximal orders of abelian subgroups in finite Chevalley groups, Mat. Zametki 69 (2001), no. 4, 524–549 (Russian, with Russian summary); English transl., Math. Notes 69 (2001), no. 3-4, 475–498. MR 1845994, DOI 10.1023/A:1010256129959
B. A. F. Wehrfritz, Infinite linear groups, Queen Mary College Mathematical Notes, Queen Mary College, Department of Pure Mathematics, London, 1969. MR 837425
Stephen S.-T. Yau and Yung Yu, Gorenstein quotient singularities in dimension three, Mem. Amer. Math. Soc. 105 (1993), no. 505, viii+88. MR 1169227, DOI 10.1090/memo/0505