pith. sign in

arxiv: 2402.17604 · v3 · pith:GHZSMG2Jnew · submitted 2024-02-27 · 💻 cs.LO · cs.FL· math.AC

Equivariant ideals of polynomials

Arka Ghosh , S{\l}awomir Lasota This is my paper

Pith reviewed 2026-05-24 03:41 UTC · model grok-4.3

classification 💻 cs.LO cs.FLmath.AC
keywords equivariant idealspolynomial idealsHilbert basis theoremBuchberger algorithmlogical structuresGröbner basesinfinite variablesregister automata
0
0 comments X

The pith

A countable structure A makes every equivariant polynomial ideal finitely generated exactly when it satisfies a specific condition on embeddings.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper gives a necessary and sufficient condition on a countable logical structure A such that every polynomial ideal invariant under variable renaming by embeddings of A into itself must be finitely generated. This extends the classical Hilbert basis theorem to rings with infinitely many variables. When the condition holds, the paper supplies an algorithm that extends Buchberger's method to produce a Gröbner basis and thereby decide ideal membership. The results apply directly to computation over infinite data domains arising in automata and nets.

Core claim

There is a sufficient and necessary condition on the countable logical structure A that guarantees every equivariant polynomial ideal is finitely generated; an extension of Buchberger's algorithm then computes a Gröbner basis and decides membership.

What carries the argument

equivariant ideal: a polynomial ideal closed under the renaming action induced by all embeddings of the structure A into itself

If this is right

  • The membership problem for any equivariant ideal becomes decidable.
  • A Gröbner basis can be computed for any given equivariant ideal.
  • Finite bases exist for the ideals that arise in register automata, Petri nets with data, and orbit-finitely generated vector spaces.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same condition on A would immediately yield algorithms for ideal membership in any algebraic structure whose variables are drawn from A.
  • Analogous finite-generation theorems could be sought for modules or other rings equipped with the same embedding action.

Load-bearing premise

The finite-generation property of ideals depends only on properties of the structure A and not on the particular choice of polynomials inside the ideal.

What would settle it

Exhibit a concrete countable structure A that meets the stated condition yet possesses at least one equivariant ideal requiring infinitely many generators, or conversely a structure that fails the condition but has all its equivariant ideals finitely generated.

Figures

Figures reproduced from arXiv: 2402.17604 by Arka Ghosh, S{\l}awomir Lasota.

Figure 1
Figure 1. Figure 1: 5 ∈ Age(Q × Q). Its elements are depicted by edges. relation symbols is the disjoint union of sets of relation symbols of A and A′ . For each -ary relation of A, the relation in A ⊗ A′ relates those -tuples ( (1, ′ 1 ), . . . , ( , ′ [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

We study existence and computability of finite bases for ideals of polynomials over infinitely many variables. In our setting, variables come from a countable logical structure A, and embeddings from A to A act on polynomials by renaming variables. First, we give a sufficient and necessary condition for A to guarantee the following generalisation of Hilbert's Basis Theorem: every polynomial ideal which is equivariant, i.e. invariant under renaming of variables, is finitely generated. Second, we develop an extension of classical Buchberger's algorithm to compute a Gr\"obner basis of a given equivariant ideal. This implies decidability of the membership problem for equivariant ideals. Finally, we sketch upon various applications of these results to register automata, Petri nets with data, orbit-finitely generated vector spaces, and orbit-finite systems of linear equations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper studies polynomial ideals over countably infinitely many variables indexed by a countable logical structure A, with embeddings A→A acting by variable renaming to produce equivariant ideals (closed under the action). It claims a necessary and sufficient condition on A guaranteeing that every such equivariant ideal is finitely generated (a generalization of Hilbert's basis theorem), develops a terminating extension of Buchberger's algorithm to compute Gröbner bases for equivariant ideals, and derives decidability of the membership problem. Applications to register automata, Petri nets with data, orbit-finite vector spaces, and linear equations are sketched.

Significance. If the condition on A is correctly identified and the algorithm is shown to terminate and be correct, the results would provide a useful algebraic tool for handling symmetry in infinite-state systems, with direct implications for decidability in automata and verification. The explicit algorithm and the necessity direction (via counterexample when the condition fails) are strengths.

major comments (2)
  1. [§3] §3 (or wherever the main theorem is stated): the necessity direction requires an explicit construction of a non-finitely-generated equivariant ideal when the condition on A fails; the manuscript must verify that this ideal is indeed closed under the embedding action and that the failure is not an artifact of the coefficient ring choice.
  2. [§4] Algorithm in §4: termination of the extended Buchberger procedure relies on a well-quasi-order or Noetherian property induced by the condition on A; the proof must explicitly reduce to the classical case or exhibit the new well-founded measure, as the monoid action may introduce additional orbits.
minor comments (3)
  1. [Abstract / §1] The abstract claims both sufficiency and necessity but does not name the condition; the introduction should state the condition explicitly (e.g., 'A has the finite-orbit property' or whatever the precise formulation is) before the theorem.
  2. [§2] Notation for the monoid of embeddings and the induced action on the polynomial ring should be fixed early and used consistently; currently the variable-renaming map is described informally.
  3. [§5] Applications section sketches connections to register automata and Petri nets but does not contain a formal reduction or theorem statement; either add a precise corollary or move the sketches to a separate discussion.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and for identifying two points where the manuscript would benefit from additional explicit detail. Both comments concern the necessity proof and the termination argument; we will strengthen the exposition in the revised version without altering the main theorems.

read point-by-point responses

  1. Referee: [§3] §3 (or wherever the main theorem is stated): the necessity direction requires an explicit construction of a non-finitely-generated equivariant ideal when the condition on A fails; the manuscript must verify that this ideal is indeed closed under the embedding action and that the failure is not an artifact of the coefficient ring choice.

    Authors: We agree that an explicit counterexample strengthens the necessity claim. In the revision we will insert a concrete construction (a specific equivariant ideal generated by monomials whose supports violate the condition on A) together with a direct verification that it is closed under all embeddings A→A and that it remains non-finitely generated over any Noetherian coefficient ring (in particular over ℚ). revision: yes

  2. Referee: [§4] Algorithm in §4: termination of the extended Buchberger procedure relies on a well-quasi-order or Noetherian property induced by the condition on A; the proof must explicitly reduce to the classical case or exhibit the new well-founded measure, as the monoid action may introduce additional orbits.

    Authors: We will expand the termination argument in §4 by exhibiting an explicit well-founded measure on the set of equivariant Gröbner bases that is compatible with the monoid action. The measure is obtained by lifting the classical Dickson’s lemma via the Noetherian property guaranteed by the condition on A; we will also include a short reduction showing that, when the action is trivial, the new measure coincides with the classical one. revision: yes

Circularity Check

0 steps flagged

No circularity: theorem and algorithm are independently derived

full rationale

The paper states a necessary and sufficient condition on the structure A guaranteeing finite generation of equivariant ideals, followed by an extension of Buchberger's algorithm. No equations, fitted parameters, or self-citations are visible in the abstract or described claims that would reduce the finite-generation result or the algorithm termination to a definitional tautology or prior self-referential input. The derivation is presented as a standard mathematical generalization of Hilbert's basis theorem with explicit computability consequences, self-contained against external benchmarks such as classical Gröbner basis theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The setup rests on the definition of equivariance via embeddings of a countable logical structure A; no free parameters, invented entities, or additional axioms are visible from the abstract.

axioms (1)
  • domain assumption Variables are indexed by elements of a countable logical structure A and embeddings A → A act on polynomials by renaming variables.
    Stated in the first sentence of the abstract as the setting in which equivariance is defined.

pith-pipeline@v0.9.0 · 5665 in / 1228 out tokens · 33232 ms · 2026-05-24T03:41:08.692370+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages · 1 internal anchor

  1. [1]

    Matthias Aschenbrenner and Christopher Hillar. 2007. F inite generation of sym- metric ideals. Trans. Amer. Math. Soc. 359.11 (2007), 5171–5192

    work page 2007

  2. [2]

    Matthias Aschenbrenner and Christopher J. Hillar. 2008 . An algorithm for find- ing symmetric Grobner bases in infinite dimensional rings. In Proc. ISSAC. ACM, 117–124

    work page 2008

  3. [3]

    Michael Benedikt, Timothy Duff, Aditya Sharad, and James Worrell. 2017. Poly- nomial automata: Zeroness and applications. In Proc. LICS 2017. IEEE Computer Society, 1–12

    work page 2017

  4. [4]

    Mikołaj Bojańczyk. 2019. Slightly Infinite Sets. (2019) . https://www.mimuw.edu.pl/~bojan/paper/atom-book

    work page 2019

  5. [5]

    Mikolaj Bojanczyk, Bartek Klin, and Slawomir Lasota. 20 14. Automata theory in nominal sets. Log. Methods Comput. Sci. 10, 3 (2014)

    work page 2014

  6. [6]

    Mikołaj Bojańczyk, Bartek Klin, and Joshua Moerman. 202 1. Orbit-Finite- Dimensional Vector Spaces and Weighted Register Automata. In Proc. LICS . IEEE, 1–13

    work page

  7. [7]

    Brouwer and Jan Draisma

    Andries E. Brouwer and Jan Draisma. 2011. Equivariant Gr öbner Bases and The Gaussian Two-factor Model. Math. Comp. 80, 274 (2011), 1123–1133

    work page 2011

  8. [8]

    Buchberger and F

    B. Buchberger and F. Winkler (Eds.). 1998. Gröbner Bases and Applications. Cam- bridge University

    work page 1998

  9. [9]

    Peter J. Cameron. 1990. Oligomorphic Permutation Groups . Cambridge Univer- sity Press

    work page 1990

  10. [10]

    Daniel E. Cohen. 1967. On the Laws of a Metabelian Variet y. Journal of Algebra 5 (1967), 267–273

    work page 1967

  11. [11]

    Daniel E. Cohen. 1987. Closure Relations, Buchberger’ s Algorithm, and Poly- nomials in Infinitely Many Variables. In Computation Theory and Logic (Lecture Notes in Computer Science, Vol. 270) . Springer, 78–87

    work page 1987

  12. [12]

    Cox, John Little, and Donal O’Shea

    David A. Cox, John Little, and Donal O’Shea. 2015. Ideals, Varieties, and Algo- rithm. Springer

    work page 2015

  13. [13]

    Reinhard Diestel. 2017. Graph Theory

    work page 2017

  14. [14]

    Phillip Emmott. 1987. Some decision problems in group theory and ring theory . Ph. D. Dissertation. Queen Mary College, University of Lond on

    work page 1987

  15. [15]

    Arka Ghosh, Piotr Hofman, and Slawomir Lasota. 2022. So lvability of orbit- finite systems of linear equations. In Proc. LICS’22 . ACM, 11:1–11:13

    work page 2022

  16. [16]

    Arka Ghosh and Sławomir Lasota. 2024. Equivariant idea ls of polynomials. arXiv:2402.17604 [cs.LO]

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  17. [17]

    G. Higman. 1952. Ordering by divisibility in abstract a lgebras. Proc. London Math. Soc. 3 (1952), 326–336. Issue 2

    work page 1952

  18. [18]

    Hillar, Robert Krone, and Anton Leykin

    Christopher J. Hillar, Robert Krone, and Anton Leykin. 2018. Equivariant Gröb- ner bases. Advanced Studies in Pure Mathematics 77 (2018), 129–154

    work page 2018

  19. [19]

    Hillar and Seth Sullivant

    Christopher J. Hillar and Seth Sullivant. 2012. Finite Gröbner bases in infinite dimensional polynomial rings and applications. Advances in Mathematics 229, 1 (2012), 1–25

    work page 2012

  20. [20]

    Wilfrid Hodges. 1997. A shorter model theory . Cambridge University Press

    work page 1997

  21. [21]

    Kriz and J

    I. Kriz and J. Sgall. 1991. Well-quasi-ordering depend s on labels. Acta Scientar- ium Mathematicarum 55 (1991), 55–69

    work page 1991

  22. [22]

    Slawomir Lasota. 2016. Decidability Border for Petri N ets with Data: WQO Di- chotomy Conjecture. In Proc. Petri Nets 2016 (Lecture Notes in Computer Science, Vol. 9698). Springer, 20–36

    work page 2016

  23. [23]

    Ranko Lazic, Thomas Christopher Newcomb, Joël Ouaknin e, A. W. Roscoe, and James Worrell. 2007. Nets with Tokens Which Carry Data. In Proc. ICATPN 2007 (Lecture Notes in Computer Science, Vol. 4546) . Springer, 301–320

    work page 2007

  24. [24]

    Mayr and Albert R

    Ernst W. Mayr and Albert R. Meyer. 1982. The Complexity o f the Word Problems for Commutative Semigroups and Polynomial Ideals. Advances in Mathematics 46 (1982), 305–329

    work page 1982

  25. [25]

    C. St. J. A. Nash-Williams. 1965. On well-quasi-orderi ng transfinite sequences. Mathematical Proceedings of the Cambridge Philosophical So ciety 61 (1965), 33–

    work page 1965

  26. [26]

    Maurice Pouzet. 2020. Well quasi ordering and embeddab ility of relational struc- tures. In Proc. ALGOS 2020 . https://hal.science/hal-02918958/document

    work page 2020

  27. [27]

    Jitka Stríbrná. 1997. Decidability of strong bisimula tion of Basic Parallel Pro- cesses using Hilbert’s basis theorem. In Proc. Infinity 1997 (Electronic Notes in Theoretical Computer Science, Vol. 9) , Faron Moller (Ed.). Elsevier, 44. Equivariant ideals of polynomials A PROOFS FOR SECTION 2 (PRELIMINARIES) L/e.sc/m.sc/m.sc/a.sc 7.Every ordinal (seen as ...

    work page 1997

  28. [28]

    Define /u1D461∈ /u1D43C/u1D460as (/u1D461/u1D44E 1 , /u1D461/u1D44E 2)=          (/u1D45D/u1D44E 1, /u1D45D/u1D44E

    ∈/u1D447and /u1D457/u1D44E∈ E/m.sc/b.scB such that /u1D457/u1D44E◦ /u1D45D/u1D44E 1 = /u1D462/u1D44E 1 and /u1D457/u1D44E◦ /u1D45D/u1D44E 2 = /u1D462/u1D44E 2 . Define /u1D461∈ /u1D43C/u1D460as (/u1D461/u1D44E 1 , /u1D461/u1D44E 2)=          (/u1D45D/u1D44E 1, /u1D45D/u1D44E

    work page

  29. [29]

    We finish the proof by showing that there exists /u1D704∈ E/m.sc/b.scA⊗B such that /u1D704◦ /u1D453/u1D460,/u1D461 1 = /u1D4621 and /u1D704◦ /u1D453/u1D460,/u1D461 2 = /u1D4622

    when /u1D44E∈ /u1D4601(/u1D44B)∩/u1D4602(/u1D44B) (Id/u1D44C,Id∅) when /u1D44E∈ /u1D4601(/u1D44B)\/u1D4602(/u1D44B) (Id∅,Id/u1D44C) when /u1D44E∈ /u1D4602(/u1D44B)\/u1D4601(/u1D44B). We finish the proof by showing that there exists /u1D704∈ E/m.sc/b.scA⊗B such that /u1D704◦ /u1D453/u1D460,/u1D461 1 = /u1D4621 and /u1D704◦ /u1D453/u1D460,/u1D461 2 = /u1D462...

    work page