Over fields and Noetherian rings, Hilbert's basis theorem guarantees that every finitely generated ideal has a finite Gröbner basis, so completion of a finite set of polynomial relations always terminates. Bokut, Chen, and Mo extended Gröbner–Shirshov basis theory to semirings and commutative semirings via algebraization, and showed that this finiteness foundation collapses: a congruence on the polynomial semiring N[x]\mathbb{N}[x] generated by the single relation x+1=xx+1=x has an infinite reduced Gröbner–Shirshov basis (their Example 5.9), and N[x]\mathbb{N}[x] is not Noetherian (their Corollary 5.10). These results leave open the question of characterizing the commutative semirings for which finite reduced Gröbner–Shirshov bases — and with them the termination of Shirshov completion upon reaching such a basis — can be restored.

Background

A semiring is an algebraic structure with addition and multiplication satisfying the usual ring axioms except that additive inverses need not exist; standard examples are the natural numbers N\mathbb{N}, the Boolean semiring {0,1}\{0,1\}, and the tropical (additively idempotent) semirings used in tropical geometry. Because subtraction is unavailable, quotients of a semiring are described by congruences — equivalence relations compatible with both operations — rather than by ideals. A Gröbner–Shirshov basis is a special generating set of an ideal that supports rewriting of every element into a unique normal form; in commutative polynomial rings over fields it coincides with the classical notion of a Gröbner basis, and the general theory goes back to Shirshov's composition lemma and Bergman's diamond lemma for associative algebras, which state that if all 'compositions' (overlap and multiples of rewriting rules, the analogues of S-polynomials) reduce to a common normal form, the rewriting system is confluent and the irreducible elements form a linear basis. Fixing a monomial order, every ideal has a unique reduced Gröbner–Shirshov basis, and completion is the process that keeps adding the non-trivial compositions until this basis is reached. Over a Noetherian commutative ring, Hilbert's basis theorem makes every such reduced basis finite, so completion terminates and membership in finitely generated ideals is decidable.

Bokut, Chen, and Mo developed Gröbner–Shirshov basis theory for semirings and commutative semirings by algebraization: a semiring presentation Rig[X∣S]\mathrm{Rig}[X|S] is embedded into a polynomial algebra kRig[X∣S]k\mathrm{Rig}[X|S] over a field, where compositions and normal forms can be computed, and finitely presented semiring quotients such as N[x]/(x=1+x+x2)\mathbb{N}[x]/(x=1+x+x^2) and N[x]/(x=1+x2)\mathbb{N}[x]/(x=1+x^2) are given explicit finite normal forms (recovering results of Blass and of Fiore–Leinster). The algorithmic theory works, but they exhibited a fundamental finiteness failure in the commutative setting: for the congruence on N[x]\mathbb{N}[x] generated by the single relation x+1=xx+1=x, the reduced Gröbner–Shirshov basis in the algebraization is the infinite set {xn+1=xn:n≥1}\{x^n+1=x^n:n\geq 1\} (Example 5.9), from which they built a strictly increasing infinite chain of finitely generated congruences ρ1⊊ρ2⊊⋯\rho_1\subsetneq\rho_2\subsetneq\cdots and concluded that N[x]\mathbb{N}[x] is not Noetherian (Corollary 5.10) — where a semiring is called Noetherian if every congruence on it is finitely generated, equivalently if there is no infinite strictly ascending chain of congruences — even though the base semiring N\mathbb{N} itself is Noetherian (Corollary 5.8). Thus the mechanism that makes Gröbner bases decisive over Noetherian rings — termination of completion via finite reduced bases — is genuinely absent over semirings.

Problem Statement

Characterize the commutative semirings SS with the property that, for every number of variables n≥1n\geq 1 and every monomial order on S[x1,…,xn]S[x_1,\dots,x_n], every congruence on the polynomial semiring S[x1,…,xn]S[x_1,\dots,x_n] generated by finitely many polynomial relations admits a finite reduced Gröbner–Shirshov basis in the sense of Bokut–Chen–Mo, i.e. computed in the algebraization kS[x1,…,xn]kS[x_1,\dots,x_n] over a field kk (whose monomials are the elements of S[x1,…,xn]S[x_1,\dots,x_n]; for the free semiring S=NS=\mathbb{N} this is the source's semiring algebra kRig[x1,…,xn]k\mathrm{Rig}[x_1,\dots,x_n], for which the reduced basis of an ideal exists and is unique once the monomial order is fixed, their Theorems 3.5 and 4.4). Here a monomial order on S[x1,…,xn]S[x_1,\dots,x_n] is read in the source's sense: a well-ordering of the monomials (the elements of S[x1,…,xn]S[x_1,\dots,x_n]) compatible with substitution into ⋆\star-monomials. Since such an order is translation-invariant under addition, no monomial order exists when SS contains a nonzero additively invertible element (any field or nonzero commutative ring, for example); for such SS the quantifier over monomial orders is empty, the property holds vacuously, and the substantive part of the characterization concerns the semirings in which no nonzero element is additively invertible. The characterization is for all commutative semirings SS; the natural classes S=NS=\mathbb{N}, the Boolean semiring, and tropical or additively idempotent semirings are illustrative instances of it. The source fixes kk as part of the framework, and the question includes whether the resulting classification depends on the choice of kk. Determine which structural hypotheses on SS restore finite reduced bases — and hence completion that terminates upon reaching the reduced basis, as Hilbert's basis theorem provides over Noetherian rings — and which semirings fail as in the source paper's Example 5.9, where the single relation x+1=xx+1=x over N[x]\mathbb{N}[x] already forces the infinite reduced basis {xn+1=xn:n≥1}\{x^n+1=x^n:n\geq 1\} (with the ordering of their Theorem 5.1) and non-Noetherianity of N[x]\mathbb{N}[x].

References

  1. L. A. Bokut, Yuqun Chen, Qiuhui Mo, Gröbner–Shirshov bases for semirings, Journal of Algebra 385 (2013) 47–63. DOI: 10.1016/j.jalgebra.2013.03.013; arXiv:1208.0538. https://doi.org/10.1016/j.jalgebra.2013.03.013
  2. L. A. Bokut, Yuqun Chen, Gröbner–Shirshov bases and their calculation, Bulletin of Mathematical Sciences 4 (2014) 325–395. DOI: 10.1007/s13373-014-0054-6; arXiv:1303.5366. https://doi.org/10.1007/s13373-014-0054-6
  3. George M. Bergman, The diamond lemma for ring theory, Advances in Mathematics 29 (1978) 178–218. DOI: 10.1016/0001-8708(78)90010-5. https://doi.org/10.1016/0001-8708(78)90010-5
  4. Diane Maclagan, Felipe Rincón, Tropical ideals, Compositio Mathematica 154 (2018), no. 3, 640–670. DOI: 10.1112/s0010437x17008004; arXiv:1609.03838. https://doi.org/10.1112/s0010437x17008004
  5. Miroslav Korbelář, Günter Landsmann, One-generated semirings and additive divisibility, Journal of Algebra and Its Applications 16 (2017), Article 1750038. DOI: 10.1142/S0219498817500384. https://doi.org/10.1142/S0219498817500384
  6. B. Ya. Kazarnovskiĭ, A. G. Khovanskiĭ, Tropical noetherity and Gröbner bases, St. Petersburg Mathematical Journal 26 (2015) 797–811. DOI: 10.1090/spmj/1359. https://doi.org/10.1090/spmj/1359
  7. Andrew J. Chan, Diane Maclagan, Gröbner bases over fields with valuations, Mathematics of Computation 88 (2019) 467–483. DOI: 10.1090/mcom/3321. https://doi.org/10.1090/mcom/3321
  8. Yatma Diop, Laila Mesmoudi, Djiby Sow, Semi-ring Based Gröbner–Shirshov Bases over a Noetherian Valuation Ring, in: Associative and Non-Associative Algebras and Applications, Springer Proceedings in Mathematics & Statistics (2020), pp. 183–198. DOI: 10.1007/978-3-030-35256-1_11. https://doi.org/10.1007/978-3-030-35256-1_11
  9. Soda Diop, Guy Stonn Wamba, Djiby Sow, Gröbner-Shirshov basis for monomials semiring over D-A rings, JP Journal of Algebra, Number Theory and Applications 61 (2023) 53–100. DOI: 10.17654/0972555523011. https://doi.org/10.17654/0972555523011
  10. Xiaohui Niu, Wenxi Li, Zhongzhi Wang, On Grobner-Shirshov bases for Markov semirings, arXiv:2401.05731 (2024). https://arxiv.org/abs/2401.05731
  11. Wenxi Li, Zhongzhi Wang, On propositional logic semirings, arXiv:2401.09043 (2024). https://arxiv.org/abs/2401.09043
  12. Youren Hu, Xiao-Shan Gao, Tropical differential Gröbner bases, Mathematics in Computer Science 15 (2021) 255–269. DOI: 10.1007/s11786-020-00481-1; arXiv:1904.02275. https://doi.org/10.1007/s11786-020-00481-1