Computability of Equivariant Gröbner bases
Arka Ghosh, Aliaume Lopez · 2025
Read Computability of Equivariant Gröbner bases by Arka Ghosh, Aliaume Lopez (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08990.txt.
Introduction
Arka Ghosh and Aliaume Lopez published this algebra paper in 2025. Gröbner bases are the workhorse tool for computing with polynomial ideals. The paper asks whether they can still be computed when the polynomial ring has infinitely many variables but a group of symmetries keeps things under control. An ideal that respects those symmetries is called equivariant.
The authors show that when every equivariant ideal is finitely generated, a property tied to Hilbert's basis theorem, Gröbner bases for such ideals are computable. It follows that testing whether a polynomial belongs to an equivariant ideal is decidable in that setting. They also give a condition under which membership becomes undecidable. That condition covers most of the common examples that lack the finite generation property. The paper thus draws a sharp line between the computable and uncomputable cases.
Catalog record
| CREATOR | Arka Ghosh, Aliaume Lopez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-08990
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computability of Equivariant Gröbner bases Arka Ghosh, Aliaume Lopez Abstract Let 𝕂 \mathbb{K} be a field, 𝒳 \mathcal{X} be an infinite set (of indeterminates), and 𝒢 \mathcal{G} be a group acting on 𝒳 \mathcal{X} . An ideal in the polynomial ring 𝕂 [ 𝒳 ] \mathbb{K}[\mathcal{X}] is called equivariant if it is invariant under the action of 𝒢 \mathcal{G} . We show Gröbner bases for equivariant ideals are computable are hence the equivariant ideal membership is decidable when 𝒢 \mathcal{G} and 𝒳 \mathcal{X} satisfies the Hilbert’s basis property, that is, when every equivariant ideal in 𝕂 [ 𝒳 ] \mathbb{K}[\mathcal{X}] is finitely generated. Moreover, we give a sufficient condition for the undecidability of the equivariant ideal membership problem. This condition is satisfied by the most common examples not satisfying the Hilbert’s basis property. Keywords: equivariant ideal, Hilbert basis, ideal membership problem, orbit finite, oligomorphic, well-quasi-ordering Repository: https://github.com/AliaumeL/AtomicHilbert This document uses knowledge : notion points to its definition . 1 Introduction For a field \mathbb{K} and a non-empty set \mathcal{X} of indeterminates, we use \mathbb{K}[\mathcal{X}] to denote the ring of polynomials with coefficients from \mathbb{K} and indeterminates/variables from \mathcal{X} . A fundamental result in commutative algebra is Hilbert’s basis theorem , stating that when \mathcal{X} is finite, every ideal in \mathbb{K}[\mathcal{X}] is finitely generated [ 26 ] , where an ideal is a non-empty subset of \mathbb{K}[\mathcal{X}] that is closed under addition and multiplication by elements of \mathbb{K}[\mathcal{X}] . This property can be rephrased as the fact that the set of polynomials \mathbb{K}[\mathcal{X}] is Noetherian . Hilbert’s basis theorem extends to the case where \mathbb{K} is a ring that is itself Noetherian [ 35 , Theorem 4.1] . A Gröbner basis is a specific kind of generating set of a polynomial ideal which allows easy checking of membership of a given polynomial in that ideal. Gröbner bases were introduced by Buchberger who showed when \mathcal{X} is finite, every ideal in \mathbb{K}[\mathcal{X}] has a finite Gröbner basis and that, for a given a set of polynomials in \mathbb{K}[\mathcal{X}] , one can compute a finite Gröbner basis of the ideal generated by them via the so-called Buchberger algorithm [ 11 ] . The existence and computability of Gröbner bases implies the decidability of the ideal membership problem : given a polynomial f and set of polynomial H , decide whether f is in the ideal generated by H . The theory of Gröbner bases has applications in very diverse areas of computer science, including integer programming [ 51 ] , algebraic proof systems [ 31 ] , geometric reasoning [ 13 ] , fixed parameter tractability [ 2 ] , program analysis [ 49 ] and constraint satisfaction problems [ 41 ] . In automata theory it has been used for deciding zeroness of polynomial automata [ 6 ] , reachability in symmetric Petri nets [ 42 ] , equivalence for string-to-string transducers [ 29 ] and equivalence of polynomial differential equations [ 12 ] . There has been a growing interest in the last few years for computational models that are manipulating infinite data structures in a finite way, for instance an automaton reading words on the infinite alphabet \mathbb{N} , while maintaining a finite number of states. While this idea can be traced back to the 90s with the notion of register automata [ 30 ] , it has been revived in with the development of the theory of orbit finite sets . In this setting, one would like to consider an infinite set of variables \mathcal{X} . As an example, let us consider the set \mathcal{X} of variables x_{i} for i\in\mathbb{N} , and the ideal \mathcal{Z} generated by the set \{x_{i}\mid i\in\mathbb{N}\} . It is clear that \mathcal{Z} is not finitely generated, and we conclude that the Hilbert’s basis theorem (and a fortiori, the Gröbner basis theory) does not extend to the case of infinite sets of indeterminates. However, in the applications mentionned above, the infinite set of variables (data) comes with an extra structure: the behaviour of the considered systems are invariant under the action of a group \mathcal{G} on \mathcal{X} . The action of this \mathcal{G} on \mathcal{X} naturally induces an action on \mathbb{K}[\mathcal{X}] , by renaming the variables. The typical example is the group of all permutations of \mathcal{X} , which corresponds to seeing \mathcal{X} as a set of indistinguishable names: one is not interested in the ideal \mathcal{Z} generated by the set \{x_{i}\mid i\in\mathbb{N}\} , but rather in the equivariant ideal generated by the set \{x_{i}\mid i\in\mathbb{N}\} , which is the smallest ideal that contains it and is invariant under the action of \mathcal{G} . In this case, this ideal is finitely generated by a single indeterminate, e.g. x_{1} . Please note that equivariance does not imply finite generation in general: for instance, the ideal \mathcal{Z} is not finitely generated as an equivariant ideal with respect to the trivial group. 1.1 Related Research The above-mentioned results were rediscovered in [ 3 , 4 , 27 ] . In [ 28 ] these results were used to prove the Independent Set Conjecture in algebraic statistics. In [ 28 ] , the authors also showed that one can even take a submonoid \mathcal{M} of \textsc{Inc}_{<} and prove existence and computability of finite Gröbner basis assuming that \mathrel{{\color[rgb]{0.1914,0.2422,0.2813}\sqsubseteq^{\mathrm{div}}_{\mathcal{M}}}} is a well-partial-order. These results were significantly generalised in [ 21 ] , which gives a necessary and a sufficient condition on the actions \mathcal{G}\curvearrowright\mathcal{X} for the Equivariant Hilbert basis property to hold [ 21 , Theorems 11 and 12, Lemma 13] . The necessary and sufficient conditions are equivalent up to a well-known conjecture by Pouzet [ 46 , Problems 12] . But to obtain decision procedures, one still lacks a generalisation of Buchberger’s algorithm to the equivariant case, except under artificial extra assumptions [ 21 , Section 6] . Overall, a general understanding of the decidability of the equivariant ideal membership problem is still missing, and a fortiori , a generalisation of Buchberger’s algorithm to the equivariant case is still an open problem. Our results are part of a larger research direction that aims at establishing an algorithmic theory of computation with orbit-finite sets. For instance, [ 43 ] studies equivariant subspaces of vector spaces generated by orbit-finite sets, [ 20 , 36 ] study solvability of orbit-finite systems of linear equations and inequalities, and [ 43 , 20 , 47 ] study duals of vector spaces generated by orbit-finite sets. 1.2 Contributions. In this paper, we bridge the gap between the theoretical understanding of the equivariant Hilbert basis property [ 21 , Property 4] , and the computational aspects of equivariant ideals , by showing that under mild assumptions on the group action, one can compute an equivariant Gröbner basis of an equivariant ideal , hence, that one can decide the equivariant ideal membership problem . In order to compute such sets, we will need to introduce some classical computability assumptions on the group action \mathcal{G}\curvearrowright\mathcal{X} , and on the set of indeterminates \mathcal{X} . These will be defined in Section 2 , but informally, we assume that one can compute representatives of the orbits of elements under the action of \mathcal{G} (this is called effective