betaFeedback

WorksComputer Science

Burnside Problems for Matrix Semigroup Quotients with Applications to Border Complexity

Abstract

The Burnside theorem for matrix semigroups states that a finitely generated matrix semigroup is finite whenever each element has only finitely many distinct powers. We study analogous finiteness questions for quotients of matrix semigroups by congruences, which need not themselves admit faithful finite-dimensional matrix representations. We show three finiteness criteria based on uniform bounds on the quotient images of (rank-)stable subsemigroups and groups in the Zariski closure. Our proofs use exterior algebra and the Ramsey theorem to develop variations of Simon's factorisation forest to matrix semigroups modulo congruences. We also present applications of our results to border complexity. One such involves separating homogeneous algebraic branching programs of fixed width and degree from its Zariski closure.

AI Use: Discussions with GPT-6 Astra suggested the explicit polynomial used to separate homogeneous algebraic branching programs (ABPs) of fixed width and degree from the Zariski closure of this class. This polynomial was found after the matrix encoding of polynomials through translations of universal ABPs and our previously established variants of Burnside Theorems for semigroup congruences were given to the model. The proofs of Theorem 2 and Corollary 1 were developed through an interaction with GPT-6. We also used GPT-6 to help develop several examples.

Funding: Shirmohammadi is supported by the ERC Synergy grant Project 101224640 (VePaSS). Worrell is supported by EPSRC Fellowship EP/X033813/1. Guttenberg is supported by the ERC Consolidator grant Polaris 101231447.

Introduction

In 1902, Burnside asked whether a finitely generated group is necessarily finite if every element has finite order, that is, if some positive power of each element equals the identity. Novikov and Adian showed in 1968 that the answer is negative even when the orders of all elements are bounded by a common constant [1]. By contrast, Schur proved that the answer is positive for groups of invertible matrices over the complex numbers [2]. Kaplansky generalised Schur’s result from the complex numbers to arbitrary fields (see [3]). McNaughton and Zalcstein further extended this conclusion to matrix semigroups over arbitrary fields [4]. They proved that a finitely generated matrix semigroup is finite whenever each element is torsion, meaning that its powers take only finitely many distinct values. Among other things, this shows that infiniteness of finitely generated matrix semigroups is semi-decidable (a witness of infiniteness is a matrix of infinite order) and hence finiteness of finitely generated matrix semigroups is decidable.

The positive answer to the Burnside problem for matrix groups generalises to quotients of matrix groups by Zariski closed normal subgroups, since such quotients can be embedded in matrix groups in higher ambient dimension. This finiteness result is a key ingredient in the first proposed algorithm for computing the Zariski closure of a finitely generated matrix group [5], resolving an open problem in quantum computation. In subsequent joint work, again relying on such a Burnside finiteness theorem, we obtained an elementary algorithm for computing this closure [6].

In this paper, we study Burnside-type questions for quotients of matrix semigroups. Our approach is based on congruences, that is, equivalence relations of matrix semigroups that are compatible with matrix multiplication. Given a finite set XX of rational matrices and a congruence ∼\sim on the semigroup ⟨X⟩\langle X\rangle they generate, we ask for sufficient conditions that

  • the quotient ⟨X⟩/∼\langle X\rangle/\sim be finite, and

  • there be a uniform bound on the length of the shortest product of generators from XX representing each equivalence class.

The classical results on the Burnside problem for matrix semigroups do not apply here, since the quotient need not admit a faithful finite-dimensional representation in a monoid of matrices with entries in a field.1 We establish three quantitative finiteness criteria for such quotients and present two applications to border complexity.

Border complexity, also known as approximate complexity, studies polynomials and tensors obtained as limits of parametrised families of bounded complexity. The distinction between exact and approximate computability is central to geometric complexity theory, where questions about computational power are expressed through polynomial and tensor orbit closures [7, 8, 9]. This distinction is already visible in small-width algebraic branching programs, as approximation can increase the expressive power in these models [10]. Our two applications study these distinctions through semigroup congruences:

  1. First, for homogeneous algebraic branching programs, we separate the class of polynomials computable by algebraic branching programs of fixed width and degree from its Zariski closure.

  1. Second, we construct a finitely generated matrix monoid under whose action the orbit closure of the permanent is not contained in that of the determinant. Curiously, under the congruence of mutual reducibility, the orbit closure of the determinant has a finite quotient whereas that of the permanent is not finite.

Both of these applications use the fact that a finitely generated matrix semigroup can have a finite quotient under a congruence, while its Zariski closure has infinitely many classes under the same congruence. These applications connect semigroup theory with border complexity and provide a new toolkit for studying a broader range of algebraic computational models.

The central tool in our proof is the notion of factorisation forest for matrix semigroups, which we developed in recent works [11, 12]. The original notion of factorization forest for semigroups was introduced by Imre Simon [13] and was later used in [14] to give an algorithm for deciding finiteness of matrix semigroups with entries in the tropical semiring. The notion has become central in the algebraic theory of formal languages (see, for example, [15, 16]) and has played a significant role in the resolution of a number of open problems (e.g., the proof of Courcelle’s conjecture that for a class of graphs of bounded treewidth a property is MSO-definable if and only if it is recognisable by a tree automaton [17]). In particular, factorisation forests provide a means to translate results on groups to the setting of semigroups. Our variants generalise Simon’s factorisation from finite semigroups to (infinite) matrix semigroups [11] and matrix semigroup quotients. In our factorisation trees, the role of idempotent elements in the classical version is replaced by (rank-)stable matrices and generalisations. We recently used one of these variants in the context of finite matrix semigroups, to give a polynomial-space algorithm for the finiteness problem for finitely generated matrix semigroups, improving a previous NExp-upper bound. This was a corollary of our polynomial bit-size bound on matrix entries in finite monoids [12].

Our Contribution

In this section we state our main technical contributions, which concern congruences on finitely generated semigroups ⟨X⟩\langle X\rangle. Each result assumes a uniform bound NN on the number of equivalence classes of a certain family of group-like sub-semigroups, and infers a bound on the number of classes of the ambient semigroup. The bound depends on NN and the ambient dimension dd, with the first result additionally depending on the cardinality of the set XX of generators. There are three variants, according to the kind of sub-semigroups on which the uniform bound is applied. Theorem 3 considers subgroups of ⟨X⟩\langle X\rangle, Theorem 1 considers stable sub-semigroups of ⟨X⟩\langle X\rangle (that is, sub-semigroups in which all matrices share the same kernel and the same image that moreover have intersection zero), finally Theorem 2 considers rank-stable sub-semigroups of ⟨X⟩\langle X\rangle, that is, sub-semigroups in which all matrices have the same rank. Every subgroup of a matrix semigroup is a stable sub-semigroup and a stable semigroup of rank rr is isomorphic to a sub-semigroup of the general linear group in dimension rr. We state a Burnside theorem for quotients of matrix semigroups by closed congruences in Corollary 1.

For positive integers N,d,mN,d,m, define

Fd(N,m):=[m(N+1)2](2d+3+1)dd−1F_d(N,m) := \left[m(N+1)^2\right]^{(2^{d+3}+1)d^{d-1}}

This yields the asymptotic bound (m(N+1))2O(d2)(m(N+1))^{2^{O(d^2)}}, which is polynomial in mm and NN for fixed dd.

Theorem 1. Let X⊆Mat⁡d(Q)X \subseteq\operatorname{Mat}_d(\mathbb{Q}) be finite, and ∼\sim be a congruence on ⟨X⟩\langle X\rangle. Then ⟨X⟩/∼\langle X\rangle/\sim is finite if and only if there is an N≥1N \ge1 such that ∣S/∼∣≤N|S/\sim| \le N for every stable subsemigroup S≤⟨X⟩S \le\langle X\rangle. The cardinality and the diameter of the quotient are at most Fd(N,∣X∣)F_d(N,|X|).

:::`

We say that a congruence ∼\sim defined on ⟨X⟩\langle X\rangle is relatively Zariski closed in ⟨X⟩×⟨X⟩\langle X\rangle\times\langle X\rangle when there exists a Zariski-closed set R⊆Mat⁡d(Q)×Mat⁡d(Q)R \subseteq\operatorname{Mat}_{d}(\mathbb{Q}) \times\operatorname{Mat}_{d}(\mathbb{Q}) such that, for all a,b∈⟨X⟩a,b \in\langle X\rangle, a∼ba \sim b if and only if (a,b)∈R(a,b) \in R. The following finiteness result for torsion quotients follows from Theorem 1. This gives a Burnside theorem for quotients of matrix semigroups by closed congruences.

Corollary 1. Let X⊂Mat⁡d(Q)X \subset\operatorname{Mat}_{d}(\mathbb{Q}) be finite, and ∼\sim be a congruence on ⟨X⟩\langle X\rangle. Suppose that the relation ∼\sim is relatively Zariski closed in ⟨X⟩×⟨X⟩\langle X\rangle\times\langle X\rangle. If ⟨X⟩/∼\langle X\rangle/\sim is torsion, then it is finite.

For positive integers N,dN,d, define

Gd(N):=(N+1)(H+1)d−1≤min⁡{2O(d2N),(N+1)2O(d)}.G_{d}(N) := (N+1)(H+1)^{d}-1 \le\min\left\{2^{O(d^{2}N)}, (N+1)^{2^{O(d)}}\right\}.

where

H:=(N+D2+1D2)andD:=(d⌊d/2⌋).H := \binom{N+D^{2}+1}{D^{2}} \qquad\text{and} \qquad D := \binom{d}{\lfloor d/2\rfloor}.

Theorem 2. Let X⊆Mat⁡d(Q)X \subseteq\operatorname{Mat}_{d}(\mathbb{Q}) be finite and ∼\sim be a congruence on ⟨X⟩\langle X\rangle. Then ⟨X⟩/∼\langle X\rangle/\sim is finite if and only if there is an N≥1N \ge1 such that ∣S/∼∣≤N|S/\sim| \le N for every rank-stable subsemigroup S≤⟨X⟩S \le\langle X\rangle. The diameter of the quotient is at most Gd(N)G_{d}(N).

The uniform boundedness assumption in Theorem 2 is stronger than in Theorem 1, since it applies to all rank-stable semigroups, not just stable semigroups. Correspondingly, the theorem yields a better bound on the diameter of ⟨X⟩/∼\langle X\rangle/\sim: while the bound in Theorem 1 is doubly exponential in d2d^{2} and depends on the number ∣X∣|X| of generators, the bound in Theorem 2 is doubly exponential only in dd and is independent of the number of generators.

The next result, Theorem 3, obtains a diameter bound on ⟨X⟩/∼\langle X\rangle/\sim that is only singly exponential in dd, but assumes that the congruence ∼\sim is defined on the Zariski closure of ⟨X⟩\langle X\rangle, with a uniform bound on the number of classes of this closure met by each subgroup.

Theorem 3. Let X⊆Mat⁡d(Q)X \subseteq\operatorname{Mat}_{d}(\mathbb{Q}) be finite and ∼\sim be a congruence on ⟨X⟩\langle X\rangle. Assume that there exists N≥1N \ge1 such that ∣G/∼∣≤N|G/\sim| \le N for every group G≤⟨X⟩G \le\langle X\rangle. Then ⟨X⟩/∼\langle X\rangle/\sim is finite and has diameter at most 22d(d+3)Nd2^{2d(d+3)}N^{d}.

We now apply the viewpoint of matrix semigroup congruences and quotients to questions in border complexity, focusing on two lines of applications. In each application, we construct a finitely generated matrix semigroup and a congruence on its Zariski closure. We show that any group in the closure lies in a single congruence class, so Theorem 3 applies and gives a finite quotient of the generated semigroup. We then show that the closure has infinitely many classes, and relate this distinction or the congruence classes to the polynomial families (or their orbits) under study.

Separation of homogeneous (commutative) ABPs and their closures. Let w≥2w \ge2 and d≥3d \ge3. Recall that a homogeneous algebraic branching program (ABP) of width at most ww and degree dd computes a polynomial through matrix multiplication, that is,

f(x)=L1(x)⋯Ld(x),f(\boldsymbol{x}) = L_{1}(\boldsymbol{x}) \cdots L_{d}(\boldsymbol{x}),

where L1L_{1} is a 1×w1 \times w matrix, LdL_{d} is a w×1w \times1 matrix, and the remaining matrices are w×ww \times w. The entries of the matrices LiL_{i} are homogeneous linear forms in the input variables x=(x1,…,xm)\boldsymbol{x}=(x_{1},\ldots,x_{m}), with coefficients in Q\mathbb{Q}. ABPs and their border complexity have been studied in recent years [10, 18, 19, 20].

Homogeneous models and their connections with algebraic geometry have also received recent attention [21, 22]. In our constructions, we keep both the width ww and the degree dd fixed and use homogeneous linear forms as used in [22].

Write Q‾[x]d\overline{\mathbb{Q}}[x]_d for the vector space of homogeneous degree-dd polynomials in the variables xx, with coefficients in Q‾\overline{\mathbb{Q}}. Denote by Aw,d\mathcal{A}_{w,d} the set of polynomials Q‾[x]d\overline{\mathbb{Q}}[x]_d computed by the ABPs defined above. As usual, viewing each polynomial as its vector of coefficients, we take the Zariski closure of the set Aw,d\mathcal{A}_{w,d} of polynomials in the vector space of homogeneous degree-dd polynomials over Q‾\overline{\mathbb{Q}}; we denote this closure by A‾w,d\overline{\mathcal{A}}_{w,d}.

Below, we prove the separation of Aw,d\mathcal{A}_{w,d} and its closure through a semigroup congruence. Roughly speaking, we use translation of the degree-dd and width-ww universal ABP to encode polynomials (in Aw,d\mathcal{A}_{w,d}) in a finitely generated matrix semigroup. We construct a congruence on its closure whose zero class consists exactly of the encodings of polynomials in Aw,d\mathcal{A}_{w,d}. We give an explicit polynomial Fw,dF_{w,d} with integer coefficients whose encoding is not congruent with zero, implying that Fw,d∈A‾w,d∖Aw,dF_{w,d} \in\overline{\mathcal{A}}_{w,d} \setminus\mathcal{A}_{w,d}.

Theorem 4. Let w≥2w \ge2 and d≥3d \ge3 and m≥2w+7m \ge2w+7. The class Aw,d\mathcal{A}_{w,d} of width-ww degree-dd homogenous ABPs is separated from A‾w,d\overline{\mathcal{A}}_{w,d}.

Separation of Det⁡n\operatorname{Det}_n from Perm⁡n\operatorname{Perm}_n under a subclass of reductions

Let n≥3n \ge3. Consider the matrix [xi,j]1≤i,j≤n[x_{i,j}]_{1\le i,j\le n} whose entries are the formal variables xi,jx_{i,j}, and X:=(x1,1,…,xn,n)X := (x_{1,1},\ldots,x_{n,n}) be the vector of these n2n^2 variables. We denote by Det⁡n\operatorname{Det}_n and Perm⁡n\operatorname{Perm}_n the determinant and permanent polynomials, respectively, defined by

Det⁡n(X):=∑σ∈Snsgn⁡(σ)∏i=1nxi,σ(i)andPerm⁡n(X):=∑σ∈Sn∏i=1nxi,σ(i),\operatorname{Det}_n(X) := \sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^{n}x_{i,\sigma(i)} \quad\text{and}\quad \operatorname{Perm}_n(X) := \sum_{\sigma\in S_n}\prod_{i=1}^{n}x_{i,\sigma(i)},

where SnS_n is the set of permutations of {1,…,n}\{1,\ldots,n\} and sgn⁡(σ)\operatorname{sgn}(\sigma) denotes the sign of σ\sigma.

Below, we use the standard action of Mat⁡n2(Q‾)\operatorname{Mat}_{n^2}(\overline{\mathbb{Q}}) on the polynomial ring Q‾[X]\overline{\mathbb{Q}}[X], defined by

(h◃L)(x):=h(xL),(h \triangleleft L)(x) := h(xL),

where L∈Mat⁡n2(Q‾)L \in\operatorname{Mat}_{n^2}(\overline{\mathbb{Q}}) and h∈Q‾[X]h \in\overline{\mathbb{Q}}[X]. This is the action of linear substitutions in the n2n^2 variables; as defined in [8 Section 3.2].

We construct a finitely generated monoid ⟨Yn⟩≤Mat⁡n2(Q‾)\langle Y_n\rangle\le\operatorname{Mat}_{n^2}(\overline{\mathbb{Q}}) such that

References

  1. [1]Petr S Novikov and Sergei I Adjan. Infinite periodic groups. i. Mathematics of the USSR-Izvestiya, 2(1):209–236, 1968.
  2. [2]Issai Schur. Über gruppen periodischer linearer substitutionen. Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften, pages 619–627, 1911.
  3. [3]Irving Kaplansky. Fields and Rings. Chicago Lectures in Mathematics. University of Chicago Press, 2nd edition, 1972.
  4. [4]Robert McNaughton and Yechzekel Zalcstein. The burnside problem for semigroups. Journal of Algebra, 34(2):292–299, 1975.DOI
  5. [5]Harm Derksen, Emmanuel Jeandel, and Pascal Koiran. Quantum automata and algebraic groups. Journal of Symbolic Computation, 39:357–371, 2005.
  6. [6]Klara Nosan, Amaury Pouly, Sylvain Schmitz, Mahsa Shirmohammadi, and James Worrell. On the computation of the zariski closure of finitely generated groups of matrices. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pages 129–138, 2022.DOI
  7. [7]Ketan D Mulmuley and Milind Sohoni. Geometric complexity theory i: An approach to the p vs. np and related problems. SIAM Journal on Computing, 31(2):496–526, 2001.DOI
  8. [8]Markus Bläser and Christian Ikenmeyer. Introduction to geometric complexity theory. Theory of Computing Library, Graduate Surveys, 10:1–166, 2025.
  9. [9]Pranjal Dutta and Bhargav Thankey. On the border complexity of sums of rofs. In International Computing and Combinatorics Conference, pages 451–464. Springer, 2026.DOI
  10. [10]Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On algebraic branching programs of small width. Journal of the ACM (JACM), 65(5):1–29, 2018.
  11. [11]Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, and James Worrell. Algebraic closure of matrix sets recognized by 1-vass. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5211–5240. SIAM, 2026.
  12. [12]Rida Ait El Manssour, Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, and James Worrell. Revisiting finiteness of matrix monoids. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), volume 374 of Leibniz International Proceedings in Informatics (LIPIcs), pages 158:1–158:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2026.
  13. [13]Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65–94, 1990.DOI
  14. [14]Imre Simon. On semigroups of matrices over the tropical semiring. RAIRO - Theoretical Informatics and Applications, 28(3-4):277–294, 1994.DOI
  15. [15]Mikołaj Bojańczyk. Factorization forests. In International Conference on Developments in Language Theory, pages 1–17. Springer, 2009.DOI
  16. [16]Thomas Colcombet. The factorisation forest theorem. In Jean-Éric Pin, editor, Handbook of Automata Theory, pages 653–693. European Mathematical Society Publishing House, Zürich, Switzerland, 2021.DOI
  17. [17]Mikolaj Bojanczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS ’16, New York, NY, USA, July 5-8, 2016, pages 407–416. ACM, 2016.
  18. [18]Eric Allender and Fengming Wang. On the power of algebraic branching programs of width two. Computational Complexity, 25(1):217–253, 2016.
  19. [19]Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic branching programs, border complexity, and tangent spaces. In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1–21:24. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2003.04834
  20. [20]Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the power of border width-2 ABPs over fields of characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.
  21. [21]Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov. Degree-restricted strength decompositions and algebraic branching programs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022), volume 250 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.DOI
  22. [22]Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Homogeneous algebraic complexity theory and algebraic formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), volume 287 of Leibniz International Proceedings in Informatics (LIPIcs), pages 43:1–43:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.DOI
  23. [23]David A. Cox, John Little, and Donal O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer, 4 edition, 2015.
  24. [24]James E Humphreys. Linear algebraic groups, volume 21. Springer, New York, 1975.DOI
  25. [25]Issai Schur. Über gruppen linearer substitutionen mit koeffizienten aus einem algebraischen zahlkörper. Mathematische Annalen, 71(3):355–367, 1911.
  26. [26]Francesco Galuppi and Mima Stanojkovski. Toric varieties from cyclic matrix semigroups. arXiv preprint arXiv:2002.02713, 2020.DOI
  27. [27]Derek John Scott Robinson. A Course in the Theory of Groups, volume 2. Springer, 1982.
  28. [28]Michel Brion. On extensions of algebraic groups with finite quotient. Pacific J. Math, 279(1-2):135–153, 2015.arxiv.org/abs/1503.06564
  29. [29]E Breuillard. An exposition of jordan’s original proof of his theorem on finite subgroups of.
  30. [30]Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463–470, 1935.
  31. [31]Reinhard Diestel. Graph theory, electronic editions 2005, 2000.

Paper details

vlnc:W_6qcdj66t
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents