On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
Authors: 
Klara Nosan, Amaury Pouly, 
Sylvain Schmitz, Mahsa Shirmohammadi, James WorrellAuthors Info & Claims
Pages 129 - 138
Abstract
We investigate the complexity of computing the Zariski closure of a finitely generated group of matrices. The Zariski closure was previously shown to be computable by Derksen, Jeandel, and Koiran, but the termination argument for their algorithm appears not to yield any complexity bound. In this paper we follow a different approach and obtain a bound on the degree of the polynomials that define the closure. Our bound shows that the closure can be computed in elementary time. We also obtain upper bounds on the length of chains of linear algebraic groups.
References
[1]
E. Amzallag. 2018. Galois groups of differential equations and representing algebraic sets. Ph.D. Dissertation. CUNY Academic Works. https://academicworks.cuny.edu/gc_etds/2860
[2]
E. Amzallag, A. Minchenko, and G. Pogudin. 2021. Degree bound for toric envelope of a linear algebraic group. arXiv:1809.06489 [math.AG]
[3]
M. Aschenbrenner. 2004. Ideal membership in polynomial rings over the integers. J. Amer. Math. Soc. 17 (2004), 407--441. https://doi.org/10.1090/S0894-0347-04-00451--5
[4]
T. Becker and V. Weispfenning. 1993. Gröbner Bases. Graduate Texts in Mathematics, Vol. 141. Springer. https://doi.org/10.1007/978--1--4612-0913--3
[5]
V. Blondel and V. Canterini. 2001. Undecidable problems for probabilistic automata of fixed dimension. Theory Comput. Syst. 36 (2001), 231--245. https://doi.org/10.1007/s00224-003--1061--2
[6]
V.D. Blondel, E. Jeandel, P. Koiran, and N. Portier. 2005. Decidable and undecidable problems about quantum automata. SIAM J. Comput. 34, 6 (2005), 1464--1473. https://doi.org/10.1137/S0097539703425861
[7]
A. Borel. 1966. Linear algebraic groups. In Algebraic Groups and Discontinuous Subgroups, A. Borel and G. D. Mostow (Eds.). Proc. Symposia Pure Math., Vol. 9. 3--19. https://doi.org/10.1090/pspum/009
[8]
A. R. Bradley and Z. Manna. 2007. Invariant generation. Springer, Chapter 12, 311--346. https://doi.org/10.1007/978--3--540--74113--8_12
[9]
G. Bumpus, C. Haase, S. Kiefer, P.-I. Stoienescu, and J. Tanner. 2020. On the size of finite rational matrix semigroups. In Proc. ICALP 2020 (LIPIcs, Vol. 168). 115:1--115:13. https://doi.org/10.4230/LIPIcs.ICALP.2020.115
[10]
J. Cai, R. J. Lipton, and Y. Zalcstein. 2000. The complexity of the A B C problem. SIAM J. Comput. 29, 6 (2000), 1878--1888.
[11]
W. A. de Graaf. 2017. Computation with Linear Algebraic Groups. CRC Press.
[12]
H. Derksen, E. Jeandel, and P. Koiran. 2005. Quantum automata and algebraic groups. J. Symb. Comput. 39, 3--4 (2005), 357--371. https://doi.org/10.1016/j.jsc.2004.11.008
[13]
T. W. Dubé. 1990. The Structure of polynomial ideals and Gröbner bases. SIAM J. Comput. 19, 4 (1990), 750--773. https://doi.org/10.1137/0219053
[14]
R. Feng. 2015. Hrushovski's Algorithm for computing the Galois group of a linear differential equation. Adv. Appl. Math. 65 (2015), 1--37. https://doi.org/10.1016/j.aam.2015.01.001
[15]
S. Friedland. 1997. The maximal orders of finite subgroups in GL?? (Q). Proc. Am. Math. Soc. 125, 12 (1997), 3519--3526. https://doi.org/10.1090/S0002--9939--97-04283--4
[16]
G. Gallo and B. Mishra. 1994. A solution to Kronecker's Problem. Appl. Algebra Eng. Commun. 5 (1994), 343--370. https://doi.org/10.1007/BF01188747
[17]
R. M. Guralnick and M. Lorenz. 2006. Orders of finite groups of matrices. In Groups, Rings and Algebras. Contemp. Math., Vol. 420. AMS, 141--161. https://doi.org/10.1090/conm/420/07974
[18]
E. Hrushovski. 2002. Computing the Galois group of a linear differential equation. Banach Center Publications 58, 1 (2002), 97--138. https://doi.org/10.4064/bc58-0--9
[19]
E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell. 2018. Polynomial invariants for affine programs. In Proc. LICS 2018. ACM, 530--539. https://doi.org/10.1145/3209108.3209142
[20]
J. E. Humphreys. 1975. Linear Algebraic Groups. Graduate Texts in Mathematics, Vol. 21. Springer. https://doi.org/10.1007/978--1--4684--9443--3
[21]
M. Karr. 1976. Affine relationships among variables of a program. Acta Inf. 6 (1976), 133--151. https://doi.org/10.1007/BF00268497
[22]
J. Kuzmanovich and A. Pavlichenkov. 2002. Finite groups of matrices whose entries are integers. Am. Math. Mon. 109, 2 (2002), 173--186. https://doi.org/10.1080/00029890.2002.11919850
[23]
C. C. MacDuffee. 1933. The Theory of Matrices. Ergebnisse der Mathematik und Ihrer Grenzgebiete, Vol. 5. Springer. https://doi.org/10.1007/978--3--642--99234--6
[24]
D. W. Masser. 1988. Linear relations on algebraic groups. In New Advances in Transcendence Theory. Cambridge University Press, 248--262. https://doi.org/10.1017/CBO9780511897184.016
[25]
K. A. Mikhailova. 1966. The occurrence problem for direct products of groups. Mat. Sb. (N.S.) 70(112), 2 (1966), 241--251. http://mi.mathnet.ru/eng/msb4223
[26]
C. F. Miller. 1972. On Group-Theoretic Decision Problems and Their Classification. Annals of Mathematics Studies, Vol. 68. Princeton University Press. https://doi.org/10.1515/9781400881789
[27]
G. Moreno Socias. 1992. Length of polynomial ascending chains and primitive recursiveness. Math. Scand. 71 (1992), 181--205. https://doi.org/10.7146/math.scand.a-12421
[28]
D. W. Morris. 2001. Introduction to Arithmetic Groups. arXiv:math/0106063 [math.DG]
[29]
M. Müller-Olm and H. Seidl. 2004. A note on Karr's Algorithm. In Proc. ICALP 2004 (Lect. Notes Comput. Sci., Vol. 3142). Springer, 1016--1028. https://doi.org/10.1007/978--3--540--27836--8_85
[30]
M. Newman. 1972. Integral Matrices. Pure and Applied Mathematics, Vol. 45. Academic Press.
[31]
K. Nosan. 2020. On the complexity of computing the algebraic closure of a finitely generated matrix semigroup. Internship Report. École Polytechnique. https://www.irif.fr/~nosan/Reports/M1report.pdf
[32]
D. Novikov and S. Yakovenko. 1999. Trajectories of polynomial vector fields and ascending chains of polynomial ideals. Ann. Inst. Fourier 49, 2 (1999), 563--609. https://doi.org/10.5802/aif.1683
[33]
A. Paz. 1971. Introduction to Probabilistic Automata. Academic Press, Inc.
[34]
J. Renegar. 1992. On the computational complexity and geometry of the firstorder theory of the reals. I, II, and III. J. Symb. Comput. 13, 3 (1992), 255--352. https://doi.org/10.1016/S0747--7171(10)80003--3
[35]
A. Seidenberg. 1972. Constructive proof of Hilbert's Theorem on ascending chains. Trans. Amer. Math. Soc. 174 (1972), 305--312. https://doi.org/10.1090/S0002--9947--1972-0314829--9
[36]
Á. Seress. 2003. Permutation Group Algorithms. Cambridge Tracts in Mathematics, Vol. 152. Cambridge University Press. https://doi.org/10.1017/CBO9780511546549
[37]
M. Sun. 2019. A new bound on Hrushovski's Algorithm for computing the Galois group of a linear differential equation. Commun. Algebra 47, 9 (2019), 3553--3566. https://doi.org/10.1080/00927872.2019.1567750
[38]
B. Weisfeiler. 1985. Post-classification version of Jordan's Theorem on finite linear groups. Proc. Natl. Acad. Sci. U.S.A. 81 (1985), 5278--5279. https://doi.org/10.1073/pnas.81.16.5278
Index Terms
- On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
Recommendations
Constructing algebraic groups from their Lie algebras
A connected algebraic group in characteristic 0 is uniquely determined by its Lie algebra. In this paper algorithms are given for constructing an algebraic group in characteristic 0, given its Lie algebra. In particular, this leads to an algorithm for ...
The Zariski topology on the spectrum of prime L-submodules
Let R be a commutative ring with identity and let M be an R-module. We topologize L − Spec(M), the collection of all prime L-submodules of M, analogous to that for FSpec(R), the spectrum of fuzzy prime ideals of R, and investigate the properties of this ...
Induced Topologies on the Poset of Finitely Generated Saturated Sets
AbstractIn [R. Heckmann, K. Keimel, Quasicontinuous Domains and the Smyth Powerdomain, Electronic Notes in Theoretical Computer Science 298 (2013), 215–232], Heckmann and Keimel proved that a dcpo P is quasicontinuous iff the poset Fin P of nonempty ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
547 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 05 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
ISSAC '22
Sponsor:
ISSAC '22: International Symposium on Symbolic and Algebraic Computation
July 4 - 7, 2022
Villeneuve-d'Ascq, France
Acceptance Rates
Overall Acceptance Rate 395 of 838 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 104Total Downloads
- Downloads (Last 12 months)30
- Downloads (Last 6 weeks)3
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in