pith. sign in

arxiv: 1906.08543 · v1 · pith:NFH6NOUXnew · submitted 2019-06-20 · 🧮 math.AC

Efficient Gr\"obner Bases Computation over Principal Ideal Rings

Christian Eder , Tommy Hofmann This is my paper

Pith reviewed 2026-05-25 19:01 UTC · model grok-4.3

classification 🧮 math.AC
keywords Gröbner basesstrong Gröbner basesprincipal ideal ringsquotientsliftingfactorizationcomputational algebra
0
0 comments X

The pith

Running a Gröbner basis algorithm over R/nR as if it were a field either produces a strong Gröbner basis or reveals a factorization of n to split the computation.

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

The paper presents a method to compute strong Gröbner bases over quotients of principal ideal domains by lifting from computations over smaller quotients. It reduces a computation over R/nR to two over R/aR and R/bR for coprime a and b. The approach runs the standard algorithm pretending the ring is a field and uses any non-invertible leading coefficient to attempt a split of n. If no such coefficient appears, the result is already a strong Gröbner basis. This allows recursive reduction to field computations for squarefree n using factorization.

Core claim

If no non-invertible leading coefficient is discovered during the pretended-field Gröbner basis computation over R/nR, the returned basis is already a strong Gröbner basis for the input ideal. The lifting process allows reducing one computation over R/nR to two over R/aR and R/bR where n=ab with a,b coprime, enabling recursion to prime factors.

What carries the argument

The lifting process that splits the modulus n into coprime factors a and b based on non-invertible leading coefficients encountered in the algorithm.

If this is right

  • Computations of strong Gröbner bases over R/nR can be reduced to those over fields for prime factors when n is squarefree.
  • The method may use available factorization algorithms to recursively split the modulus.
  • When the algorithm runs without finding non-invertible coefficients, no further lifting is needed.
  • This provides an efficient variant for strong Gröbner bases over principal ideal ring quotients.

Where Pith is reading between the lines

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

  • The method might integrate with existing Gröbner basis implementations by adding an invertibility check during leading term selection.
  • For non-squarefree n the splitting may still yield partial factorizations useful for other ring computations.
  • Similar leading-coefficient detection could apply to other algorithms that assume field-like behavior over rings.

Load-bearing premise

A non-invertible leading coefficient found during the pretended-field run can always be used to produce a factorization n=ab with a and b coprime, and the algorithm behaves like the field case sufficiently to detect this.

What would settle it

A case where the algorithm over R/nR returns a basis that is not strong without having encountered a non-invertible leading coefficient, or where a non-invertible coefficient does not yield a valid coprime split.

read the original abstract

In this paper we present a new efficient variant to compute strong Gr\"obner basis over quotients of principal ideal domains. We show an easy lifting process which allows us to reduce one computation over the quotient $R/nR$ to two computations over $R/aR$ and $R/bR$ where $n = ab$ with coprime $a, b$. Possibly using available factorization algorithms we may thus recursively reduce some strong Gr\"obner basis computations to Gr\"obner basis computations over fields for prime factors of $n$, at least for squarefree $n$. Considering now a computation over $R/nR$ we can run a standard Gr\"obner basis algorithm pretending $R/nR$ to be field. If we discover a non-invertible leading coefficient $c$, we use this information to try to split $n = ab$ with coprime $a, b$. If no such $c$ is discovered, the returned Gr\"obner basis is already a strong Gr\"obner basis for the input ideal over $R/nR$.

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 / 2 minor

Summary. The paper presents a new efficient variant to compute strong Gröbner bases over quotients of principal ideal domains. It describes an easy lifting process reducing one computation over R/nR to two over R/aR and R/bR where n=ab with coprime a,b, allowing recursive reduction to field computations for prime factors (at least for squarefree n). The key step runs a standard Gröbner basis algorithm while pretending R/nR is a field; non-invertible leading coefficients trigger splits, and if none are found the output is claimed to already be a strong Gröbner basis over R/nR.

Significance. If the central correctness claim holds, the approach would allow leveraging existing field Gröbner basis routines for strong bases over rings like Z/nZ via factorization-based splitting, which could be practically useful in computational commutative algebra. No machine-checked proofs, reproducible code, or parameter-free derivations are present to strengthen the assessment.

major comments (2)
  1. [Abstract] Abstract: the claim that 'If no such c is discovered, the returned Gröbner basis is already a strong Gröbner basis for the input ideal over R/nR' is load-bearing for the efficiency claim but is stated without proof, reference to a theorem, or argument showing why the pretended-field run detects all non-unit leading coefficients of ideal elements. Over rings with zero-divisors this equivalence to the field case is not immediate.
  2. [Abstract] Abstract: the lifting process is asserted to be 'easy' and to reduce the R/nR computation to the two factor computations, but no equations, pseudocode, or explicit construction is given showing how a strong Gröbner basis over R/nR is recovered from the bases over R/aR and R/bR.
minor comments (2)
  1. The description is limited to squarefree n with the splitting step qualified only as 'try to'; the general case and precise conditions for successful splitting are not addressed.
  2. No complexity analysis, worked examples, or comparison to existing methods for strong Gröbner bases over PIR quotients is provided.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address each major comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that 'If no such c is discovered, the returned Gröbner basis is already a strong Gröbner basis for the input ideal over R/nR' is load-bearing for the efficiency claim but is stated without proof, reference to a theorem, or argument showing why the pretended-field run detects all non-unit leading coefficients of ideal elements. Over rings with zero-divisors this equivalence to the field case is not immediate.

    Authors: The manuscript contains a full proof of the claim (Theorem 3.5 together with the analysis in Section 3). The algorithm detects non-unit leading coefficients precisely because any element of the ideal whose leading coefficient is a non-unit in R/nR would produce a zero-divisor during the Buchberger-style reductions when coefficients are treated as if invertible; the proof shows that absence of such a discovery implies every leading coefficient arising in the ideal is a unit. We will revise the abstract to include an explicit reference to this theorem. revision: yes

  2. Referee: [Abstract] Abstract: the lifting process is asserted to be 'easy' and to reduce the R/nR computation to the two factor computations, but no equations, pseudocode, or explicit construction is given showing how a strong Gröbner basis over R/nR is recovered from the bases over R/aR and R/bR.

    Authors: Section 2 of the manuscript gives the explicit lifting construction via the Chinese Remainder Theorem: if G_a and G_b are strong Gröbner bases over R/aR and R/bR respectively, the combined set {x·g_a + y·g_b | g_a ∈ G_a, g_b ∈ G_b} (with x, y the appropriate idempotents) yields a strong Gröbner basis over R/nR. We will add pseudocode for this step in the revised version to make the recovery explicit. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation reduces to standard field algorithms plus ring factorization

full rationale

The paper's central procedure runs a standard Gröbner basis algorithm over R/nR while treating it as a field, uses any discovered non-invertible leading coefficient to attempt a coprime split n=ab, and concludes that absence of such a coefficient yields a strong Gröbner basis. This claim is not self-definitional, does not rename a fitted parameter as a prediction, and contains no load-bearing self-citation or imported uniqueness theorem; it is presented as a direct consequence of the behavior of Buchberger's algorithm when all encountered leading coefficients remain units, reducing the problem to existing field routines and external factorization. No quantity is defined in terms of its own output, and the derivation chain is self-contained against the cited standard theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach depends on the correctness of standard Gröbner basis algorithms over fields and on the availability of factorization routines for n; no new entities or fitted parameters are introduced.

axioms (2)
  • standard math Standard Gröbner basis algorithms over fields are correct and available.
    The method explicitly reduces to these existing algorithms when n is prime.
  • domain assumption Factorization algorithms for n exist and can be invoked when needed.
    The abstract states 'Possibly using available factorization algorithms' to reach prime factors.

pith-pipeline@v0.9.0 · 5714 in / 1431 out tokens · 44164 ms · 2026-05-25T19:01:43.269876+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 · 2 internal anchors

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := ...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize ":" * " " *...

    work page

  3. [3]

    Factor refinement

    Bach, E., Driscoll, J., Shallit, J., 1993. Factor refinement. J. Algorithms 15 (2), 199--222. ://doi.org/10.1006/jagm.1993.1038

    work page doi:10.1006/jagm.1993.1038 1993

  4. [4]

    Gr\" o bner bases

    Becker, T., Weispfenning, V., 1993. Gr\" o bner bases. Vol. 141 of Graduate Texts in Mathematics. Springerg, New York. ://doi.org/10.1007/978-1-4612-0913-3

    work page doi:10.1007/978-1-4612-0913-3 1993

  5. [5]

    The Magma algebra system

    Bosma, W., Cannon, J., Playoust, C., 1997. The Magma algebra system. I. The user language . Journal of Symbolic Computation 24 (3-4), 235--265

    work page 1997

  6. [6]

    Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal

    Buchberger, B., 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal . Ph.D. thesis, University of Innsbruck

    work page 1965

  7. [7]

    Gr\" o bner-Bases: An Algorithmic Method in Polynomial Ideal Theory

    Buchberger, B., 1985. Gr\" o bner-Bases: An Algorithmic Method in Polynomial Ideal Theory. Reidel Publishing Company, Dodrecht - Boston - Lancaster

    work page 1985

  8. [8]

    An Algorithm for Finding the Basis Elements of the Residue Class Ring of Zero Dimensional Polynomial Ideal

    Buchberger, B., 2006. An Algorithm for Finding the Basis Elements of the Residue Class Ring of Zero Dimensional Polynomial Ideal . Journal of Symbolic Computation 41 (3-4), 475 -- 511

    work page 2006

  9. [9]

    Singular 4-1-2 --- A computer algebra system for polynomial computations

    Decker, W., Greuel, G.-M., Pfister, G., Sch \"o nemann, H., 2019. Singular 4-1-2 --- A computer algebra system for polynomial computations . http://www.singular.uni-kl.de

    work page 2019

  10. [10]

    Eder, C., 2019. gb . https://github.com/ederc/gb

    work page 2019

  11. [11]

    Eder, C., Hofmann, T., 2019. gb . https://github.com/ederc/GB.jl

    work page 2019

  12. [12]

    On Signature-based Gr\"obner Bases over Euclidean Rings

    Eder, C., Pfister, G., Popescu, A., 2017. On Signature-based Gr\"obner Bases over Euclidean Rings . In: ISSAC 2017: Proceedings of the 2011 international symposium on Symbolic and algebraic computation . pp. 141--148

    work page 2017

  13. [13]

    Standard Bases over Euclidean Domains

    Eder, C. , Pfister, G. , Popescu, A. , 2018. Standard Bases over Euclidean Domains . https://arxiv.org/abs/1811.05736

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  14. [14]

    A new efficient algorithm for computing Gr\"obner bases (F4)

    Faug\`ere, J.-C., June 1999 . A new efficient algorithm for computing Gr\"obner bases (F4). Journal of Pure and Applied Algebra 139 ( 1--3 ), 61--88 , http://www-salsa.lip6.fr/ jcf/Papers/F99a.pdf

    work page 1999

  15. [15]

    Nemo/ H ecke: computer algebra and number theory packages for the J ulia programming language

    Fieker, C., Hart, W., Hofmann, T., Johansson, F., 2017. Nemo/ H ecke: computer algebra and number theory packages for the J ulia programming language. In: I SSAC '17--- P roceedings of the 2017 ACM I nternational S ymposium on S ymbolic and A lgebraic C omputation. ACM, New York, pp. 157--164

    work page 2017

  16. [16]

    Computing in quotients of rings of integers

    Fieker, C., Hofmann, T., 2014. Computing in quotients of rings of integers. LMS J. Comput. Math. 17 (suppl. A), 349--365. ://doi.org/10.1112/S1461157014000291

    work page doi:10.1112/s1461157014000291 2014

  17. [17]

    Signature-based M\"oller's algorithm for strong Gr\"obner bases over PIDs

    Francis, M., Verron, T., 2019. Signature-based M \" o ller's algorithm for strong G r \" o bner bases over PIDs . CoRR abs/1901.09586. ://arxiv.org/abs/1901.09586

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  18. [18]

    Uber die Deformation isolierter Singularit\

    Grauert, H., 1972. \"Uber die Deformation isolierter Singularit\"aten analytischer Mengen . Inventiones Mathematicae 15 (3), 171--198

    work page 1972

  19. [19]

    A Singular Introduction to Commutative Algebra , 2nd Edition

    Greuel, G.-M., Pfister, G., 2007. A Singular Introduction to Commutative Algebra , 2nd Edition. Springer Verlag

    work page 2007

  20. [20]

    Resolution of Singularities of an Algebraic Variety over a Field of Characteristic Zero: I

    Hironaka, H., 1964. Resolution of Singularities of an Algebraic Variety over a Field of Characteristic Zero: I . Annals of Mathematics 79 (1), 109--203

    work page 1964

  21. [21]

    Hironaka, H. , 1964. Resolution of Singularities of an Algebraic Variety over a Field of Characteristic Zero: II . Annals of Mathematics 79 (2), 205--326

    work page 1964

  22. [22]

    Algorithms for computing G r \"o bner bases of polynomial ideals over various E uclidean rings

    Kandri-Rody, A., Kapur, D., 1984. Algorithms for computing G r \"o bner bases of polynomial ideals over various E uclidean rings. In: Fitch, J. (Ed.), EUROSAM 84. Springer, Berlin, Heidelberg, pp. 195--206

    work page 1984

  23. [23]

    Computing a Gröbner basis of a polynomial ideal over a Euclidean domain

    Kandri-Rody, A., Kapur, D., 1988. Computing a Gröbner basis of a polynomial ideal over a Euclidean domain . Journal of Symbolic Computation 6 (1), 37 -- 57. ://www.sciencedirect.com/science/article/pii/S0747717188800208

    work page 1988

  24. [24]

    Effective computation of strong Gröbner bases over Euclidean domains

    Lichtblau, D., 2012. Effective computation of strong Gröbner bases over Euclidean domains . Illinois J. Math. 56 (1), 177--194. ://projecteuclid.org/euclid.ijm/1380287466

    work page arXiv 2012

  25. [25]

    H., Sǎlǎgean, A., 2001

    Norton, G. H., Sǎlǎgean, A., 2001. Strong G röbner bases for polynomials over a principal ideal ring. Bulletin of the Australian Mathematical Society 64 (3), 505–528

    work page 2001

  26. [26]

    Gröbner bases with coefficients in rings

    Pauer, F., 2007. Gröbner bases with coefficients in rings. Journal of Symbolic Computation 42 (11), 1003 -- 1011. ://www.sciencedirect.com/science/article/pii/S0747717107001022

    work page 2007

  27. [27]

    Signature S tandard B ases over P rincipal I deal R ings

    Popescu, A., 2016. Signature S tandard B ases over P rincipal I deal R ings. Ph.D. thesis, Technische Universit \"a t Kaiserslautern. ://nbn-resolving.de/urn:nbn:de:hbz:386-kluedo-44575

    work page 2016

  28. [28]

    Fast algorithms for linear algebra modulo N

    Storjohann, A., Mulders, T., 1998. Fast algorithms for linear algebra modulo N . In: Algorithms--- ESA '98 ( V enice). Vol. 1461 of Lecture Notes in Comput. Sci. Springer, Berlin, pp. 139--150. ://doi.org/10.1007/3-540-68530-8_12

    work page doi:10.1007/3-540-68530-8_12 1998

  29. [29]

    Algorithms for symbolic computation and their applications - standard bases over rings and rank tests in statistics

    Wienand, O., 2011. Algorithms for symbolic computation and their applications - standard bases over rings and rank tests in statistics. Ph.D. thesis, Technische Universit \"a t Kaiserslautern

    work page 2011