Beyond F5 and GVW: The Proper-Cover Algorithm for Fast Ideal Basis Computation

Sheng-Ming Ma; Yi Liu; Zheng-Lin Jiao

REVIEW 2 major objections 4 minor 16 references

Beyond F5 and GVW: The Proper-Cover Algorithm for Fast Ideal Basis Computation

T0 review · 2 major / 4 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A signature-cover algorithm for zero-dimensional ideals terminates with a proper basis that beats F5 under every order and speeds up GVW under lex.

desk verdict Solid algorithmic merge of GVW covers with proper bases; the singular-S-pair gap in Lemma 4.3 is real but narrow, and the Maple numbers still make the paper worth a referee. read the letter →

arxiv 2607.09163 v1 pith:IX2P55P7 submitted 2026-07-10 cs.SC

Sheng-Ming Ma , Yi Liu , Zheng-Lin Jiao This is my paper · ORCID

classification cs.SC MSC 13P1068W30

keywords Gröbnerbasessignaturealgorithmsproperbasiszero-dimensionalidealscovercriterionlexicographicordereliminantPIDcoefficients

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Computing Gröbner bases is expensive, especially under lexicographic order. This paper takes the proper-basis idea of treating one variable as a parameter over a principal ideal domain and grafts onto it the signature-cover machinery of modern signature algorithms. The resulting Proper-Cover algorithm runs in two phases: a first pass that produces a pre-basis and a pre-eliminant together with a set of multipliers, then a hungry-refinement pass that recovers the exact powers of the remaining irreducible factors of the eliminant. The authors prove that the algorithm always terminates on zero-dimensional ideals and that the modular pieces it returns satisfy the leading-term ideal condition required of a proper basis. Benchmarks on Cyclic, Katsura and random systems show that the method finishes more instances than F5 under every tested monomial order and is markedly faster than GVW under pure lexicographic order. The practical payoff is a new route to bases of zero-dimensional ideals that can be converted, if desired, into classical Gröbner bases over the ground field.

What carries the argument

The generalized cover and regular reduction of semi-S-pairs over the PID K[x1]: every classical S-pair admits a representation, via these operations, in terms of the local pre-basis and pre-eliminants already computed, which is what lets the algorithm recover exact powers of eliminant factors without re-examining the whole ideal.

What would settle it

Run the algorithm on a concrete zero-dimensional ideal whose classical Gröbner basis and eliminant are already known (for example a small Cyclic or Katsura system under lex) and check whether the returned modular bases generate exactly the same leading-term ideal as the projected ideal; any mismatch falsifies the main theorem.

Watch

Extended reading notes

Core claim

For every zero-dimensional ideal I in K[x1][x̃] the Proper-Cover algorithm terminates and returns pairwise-coprime factors qj of the eliminant together with modular bases Bqj such that the leading-term ideal of the projected ideal equals the leading-term ideal of Bqj; the union of those modular bases with the qj themselves is therefore a proper basis of I.

Load-bearing premise

The proof assumes that every standard S-pair can be rewritten, through the generalized cover and regular reduction of semi-S-pairs, purely in terms of the first-stage local basis; if that rewriting fails for singular pairs or awkward multipliers, the modular-basis equalities no longer hold.

Editorial extensions

If this is right

A proper basis of a zero-dimensional ideal can be obtained without computing a full field Gröbner basis first, then converted to a classical Gröbner basis by standard change-of-order techniques if needed.
Under pure lexicographic order the method is expected to finish many instances that currently time out for both F5 and GVW.
The same cover-and-hungry-refinement pattern can be reused for other signature-based algorithms that work over principal ideal rings.
Compatible-factor bookkeeping gives an explicit factorization of the eliminant as a by-product of the basis computation.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the first phase already records all non-constant multipliers, later refinement only needs to re-run the signature engine for the remaining prime-power factors, suggesting a natural parallel or incremental implementation.
The same semi-S-pair representation may extend the method to positive-dimensional ideals once a suitable notion of eliminant ideal is supplied.
If the cover criterion continues to discard most pairs under plex, the algorithm could become a practical default for radical membership and primary decomposition pipelines that currently rely on F5-style lex Gröbner bases.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real news is a working two-phase algorithm that lifts GVW-style signature covers and semi-S-pairs to K[x1][x̃], then recovers exact powers of the eliminant via “compatible factors” and hungry refinement. That is new; it is not just a re-packaging of F5/GVW or of the authors’ earlier proper-basis papers. The termination argument is standard Noetherian, the modular-basis equality is proved once the representation lemmas are granted, and the Maple timings (especially under plex) are the first concrete evidence I have seen that a proper-basis method can beat both F5 and GVW on the hard order.

What they do well: the definitions of proper/hungry cover, least multiplier, and semi-S-pair are clean; Algorithms 1–3 are readable; and the experimental table is honest about timeouts. The claim that Proper-Cover dominates F5 across orders and often wins under lex is supported by the numbers they give.

The soft spot the stress-test flags is real but limited. Lemma 4.3 carefully builds the S-pair representation for non-singular and covered cases, then waves at singular pairs with “it is easy to see.” That sentence is the weakest link: if a singular configuration under PID multipliers fails to reduce to the local pre-basis, the inductive step of Lemma 4.5 and therefore Props. 4.6–4.7 lose their footing. I do not think the whole edifice collapses—singular pairs are already handled by signature cancellation in the classical theory—but the paper should either expand the argument or cite a reduction that covers the PID case. Everything else (compatible-factor extraction, hungry refinement, exact-power recovery) sits on top of that one step.

No code, no independent reimplementation, and several cells are pure timeouts; those are ordinary conference-paper limitations, not fatal ones. Citations are appropriate; self-cites to the proper-basis arXivs are necessary background, not circular.

This is for people who actually implement elimination or signature Gröbner bases. A serious referee in computational algebra will want the singular case written out and preferably a public Maple or Singular worksheet, but the paper already clears the bar for peer review. I would send it out.

Referee Report

2 major / 4 minor

Summary. The paper proposes the Proper-Cover algorithm for computing proper bases of zero-dimensional ideals I ⊂ K[x1][x̃]. It generalizes signatures, POT order, covers, regular reductions and S-pairs from the field setting of F5/GVW to coefficients in the PID K[x1], introduces semi-S-pairs, proper/hungry covers and reductions, and a two-phase procedure (ProperCoverReduction followed by HungryRefinement with compatible-factor extraction). Theorem 1.1 / Theorem 4.8 asserts termination and that the output pairs (qj, Bqj) satisfy χ = ∏ qj together with the modular leading-term equality ⟨LT(πqj(I))⟩ = ⟨LT(Bqj)⟩, so that the assembled set is a proper basis. Maple timings on Cyclic, Katsura and seven random systems are reported to claim superiority over F5 under all orders and over GVW under plex.

Significance. If the correctness chain holds, the work supplies a genuine new algorithmic framework that imports modern signature-cover techniques into the proper-basis setting of Ma, offering a practical route to modular bases and eliminants that is especially attractive for lexicographic order. The explicit two-phase design, the compatible-factor construction, and the PID-level generalizations of cover and reduction are concrete contributions that could be adopted by computer-algebra systems. The experimental section, while limited to unoptimized Maple, already shows that the method solves instances on which F5 times out and frequently beats GVW under plex, giving empirical weight to the claim of a useful alternative.

major comments (2)

Lemma 4.3 is the load-bearing representation that lets every ordinary S-pair (including singular ones) be rewritten via covers and regular reductions of semi-S-pairs by the local pre-basis. The argument carefully constructs identity (9) for non-singular and covered cases, then simply asserts “It is easy to see that when the S-pair is singular this conclusion also holds.” No separate reduction, signature comparison, or reference is supplied. Because singular S-pairs are precisely those for which sig(SSS) ≺POT max{λf tf sig(f), λg tg sig(g)}, the local-basis reduction that produces (9) is not automatic. If the identity fails for any singular configuration that arises under the PID multipliers of Algorithms 1–2, the inductive step of Lemma 4.5 collapses and both the modular-basis equality of Proposition 4.7 and the exact-power claim of Proposition 4.6 become unsupported. A complete case ana
Table 1 and the abstract claim that Proper-Cover “delivers clear speedups over GVW for lexicographic (plex) order.” The table itself shows the opposite on Random-6 (PC 310 s vs GVW 80 s) and comparable or worse behaviour on several other plex entries once timeouts are excluded. The experimental claim therefore overstates the evidence and should be qualified to the systems and orders for which the advantage is actually observed.

minor comments (4)

Typographical errors: “momomial” (p. 1), “V olny” (ref. [14]), “GP” vs “Gp” inconsistency in Algorithm 2 line 22, and the future arXiv date “10 Jul 2026”.
Section 5 gives no implementation details for the F5 and GVW baselines (signature selection strategy, pair-set data structures, reduction heuristics). Without them the Maple timings are hard to interpret or reproduce.
The passage from a proper basis to a classical Gröbner basis is only referenced to Adams–Loustaunau; a short self-contained statement of the conversion would help readers who do not have that monograph at hand.
Definition 2.3 leaves the singular case without a semi-S-pair; a one-sentence remark on how the algorithm nevertheless processes such pairs would improve clarity.

Circularity Check

1 steps flagged · score 2.0 of 10

Minor self-citation of a supporting algebraic lemma from the authors' prior proper-basis paper; the new cover/reduction lemmas and main correctness chain are independently derived.

self citation load bearing [Lemma 4.4 (used inside proof of Lemma 4.5)]
"This is Lemma 3.11 of [15]."

The algebraic identity that expresses a leading-term cancellation as a linear combination of S-polynomials is not re-proved; it is imported from the first author's prior proper-basis paper and then used load-bearingly to construct the multiplier-coprime representation (12)–(13) that underpins both the modular-basis equality and the exact-power recovery. The rest of the correctness chain does not collapse to this citation.

full rationale

The paper defines a new two-phase signature algorithm (ProperCoverReduction + HungryRefinement) that generalizes GVW-style covers and semi-S-pairs to the PID coefficient ring K[x1], then proves termination and that the output pairs satisfy the modular-basis condition of a proper basis (Thm. 1.1 / 4.8). The bulk of the derivation (Defs. 2.2–2.7, Lemmas 4.2–4.3 and 4.5, Props. 4.6–4.7) is self-contained algebraic reasoning about signatures, regular reductions and compatible factors; it does not reduce by construction to the input definitions. The only self-citation that is load-bearing for a technical step is the importation of a cancellation lemma (Lemma 4.4 = Lemma 3.11 of the first author's earlier arXiv:2101.03482). That lemma is a standard fact about S-polynomials when leading monomials cancel and is used inside the inductive construction of representation (12); it does not force the main claim or close a definitional loop. There are no fitted parameters, no uniqueness theorems imported to forbid alternatives, no ansatz smuggled via citation, and no renaming of known empirical patterns. Benchmarks are independent runtime comparisons. The proof gap noted by the skeptic (singular S-pairs in Lemma 4.3) is a correctness risk, not circularity. Hence only a minor self-citation penalty is warranted.

Assumptions & free parameters 0 free parameters · 4 assumptions · 3 invented entities

The work sits inside classical commutative algebra and signature-based Gröbner theory. No free parameters are fitted. Background axioms are standard (Noetherian rings, POT order, zero-dimensionality, PID property of K[x1]). Invented entities are definitional constructs of the algorithm rather than physical postulates; they have no independent empirical handle outside the paper’s own correctness claims.

assumptions (4)

standard math K[x1] is a PID and K[x1][x̃] is Noetherian; monomial orders are well-orders.
Used throughout for existence of gcds/lcms, termination of reductions, and principal eliminants (Sections 2 and 4).
domain assumption Input ideal I is zero-dimensional, so I ∩ K[x1] is principal and nonzero.
Stated in Theorem 1.1 and Definition 2.1; required for the eliminant χ and modular bases to be well-defined.
domain assumption POT order and signature-based cover criteria behave as in the classical F5/GVW setting once coefficients are taken in a PID.
Assumed when generalizing Definitions 2.2–2.7 and when claiming that local bases below a signature reduce syzygies (Section 4 opening paragraphs).
ad hoc to paper Every S-pair (including singular ones) admits a representation via covers and regular reductions of semi-S-pairs by the local pre-basis (Lemma 4.3).
Load-bearing technical lemma introduced in this paper; subsequent exact-power and modular-basis arguments depend on it.

invented entities (3)

Compatible factor χ0,c / χp,c
purpose: Extracts the part of a pre-eliminant whose irreducible factors never divide recorded multipliers, guaranteeing it divides the true eliminant.
Definition 3.1; used in Algorithm 3 and Lemma 4.5. Purely algorithmic; no external falsifiable prediction.
Hungry cover / hungry reduction with respect to an irreducible p
purpose: Restricts multipliers to be coprime to a chosen p so that exact multiplicity of p in the eliminant can be recovered.
Definitions 2.4 and 2.7; Algorithm 2. Definitional device of the two-phase design.
Semi-S-pair
purpose: Allows the algorithm to process only one side of an S-pair when signatures do not cancel, enabling cover pruning over a PID.
Definition 2.3; central to Algorithms 1–2 and Lemma 4.3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Beyond F5 and GVW: The Proper-Cover Algorithm for Fast Ideal Basis Computation." pith.science (2026). https://pith.science/paper/IX2P55P7

@misc{pith2026260709163,
  author       = {Pith},
  title        = {Pith review of: Beyond F5 and GVW: The Proper-Cover Algorithm for Fast Ideal Basis Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IX2P55P7}},
  note         = {Machine review of arXiv:2607.09163}
}

read the original abstract

Gr\"obner basis computation incurs heavy computational overhead, especially under lexicographic order. F5 and its GVW variant dominate efficient field-based Gr\"obner basis solving. The proper basis algorithm offers a parameterized ideal computation framework without leveraging modern signature-based optimizations. This work presents the Proper-Cover algorithm for zero-dimensional polynomial ideals by combining GVW's cover optimization over signature with the proper basis theory. We generalize signature, cover, POT ordering, reduction and S-pair concepts to parameterized coefficients, design a two-phase algorithm with compatible factor construction and hungry refinement, and rigorously prove termination and output correctness. Accordingly, we propose a new framework for the efficient computation of polynomial ideal bases. Benchmark results show that Proper-Cover surpasses F5 under all monomial orderings and delivers clear speedups over GVW for lexicographic (plex) order.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 3 canonical work pages

[1]

W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, Providence, RI, 1994

1994
[2]

Arri and J

A. Arri and J. Perry, The F5 criterion revised,Journal of Symbolic Computation, 46 (2011), no. 9, 1017–1029. doi:10.1016/j.jsc.2011.05.004

work page doi:10.1016/j.jsc.2011.05.004 2011
[3]

Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero-dimensional polynomial ideal, Journal of Symbolic Computation, 41 (2006), no

B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero-dimensional polynomial ideal, Journal of Symbolic Computation, 41 (2006), no. 3–4, 475–511

2006
[4]

D. Cox, J. Little, and D. O’Shea,Ideals, Varieties, and Algorithms, 4th ed., Springer, Cham, 2015

2015
[5]

Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra, 139 (1999), 61–88

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra, 139 (1999), 61–88

1999
[6]

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. doi:10.1145/780506.780516

doi:10.1145/780506.780516 2002
[7]

Eder and T

C. Eder and T. Hofmann, Efficient Gröbner bases computation over principal ideal rings, Journal of Symbolic Computation, 103 (2021), 1–13

2021
[8]

Eder and J.-C

C. Eder and J.-C. Faugère, A survey on signature-based algorithms for com- puting Gröbner bases, Journal of Symbolic Computation , 80 (2017), 719–784. doi:10.1016/j.jsc.2016.07.031

work page doi:10.1016/j.jsc.2016.07.031 2017

Show all 16 references

[9]

Eder and J

C. Eder and J. Perry, F5C: a variant of Faugère’s F5 algorithm with reduced Gröbner bases, Journal of Symbolic Computation, 45 (2010), 1442–1458

2010
[10]

Francis and T

M. Francis and T. Verron, A signature-based algorithm for computing Gröbner bases over principal ideal domains, Mathematics in Computer Science , 14 (2020), 515–530. doi:10.1007/s11786-019-00432-5

2020 doi
[11]

Faugère, P

J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, 16 (1993), 329– 344

1993
[12]

Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, 13 (1992), no

D. Lazard, Solving zero-dimensional algebraic systems, Journal of Symbolic Computation, 13 (1992), no. 2, 117–131

1992
[13]

von zur Gathen and J

J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge Univer- sity Press, Cambridge, 2013

2013
[14]

S. Gao, F. V olny IV , and M. Wang, A new framework for computing Gröbner bases, Mathematics of Computation, 85 (2016), 449–465. 14

2016
[16]

Ma, A new type of bases for zero-dimensional ideals, arXiv:2101.03482v1, 2021

S.-M. Ma, A new type of bases for zero-dimensional ideals, arXiv:2101.03482v1, 2021

2021 arXiv
[17]

H. M. Möller, On the construction of Gröbner bases using syzygies, Journal of Symbolic Computation, 6 (1988), 345–359. 15

1988

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.

[1] [1]

W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, Providence, RI, 1994

1994

[2] [2]

Arri and J

A. Arri and J. Perry, The F5 criterion revised,Journal of Symbolic Computation, 46 (2011), no. 9, 1017–1029. doi:10.1016/j.jsc.2011.05.004

work page doi:10.1016/j.jsc.2011.05.004 2011

[3] [3]

Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero-dimensional polynomial ideal, Journal of Symbolic Computation, 41 (2006), no

B. Buchberger, An algorithm for finding the basis elements of the residue class ring of a zero-dimensional polynomial ideal, Journal of Symbolic Computation, 41 (2006), no. 3–4, 475–511

2006

[4] [4]

D. Cox, J. Little, and D. O’Shea,Ideals, Varieties, and Algorithms, 4th ed., Springer, Cham, 2015

2015

[5] [5]

Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra, 139 (1999), 61–88

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases (F4), Journal of Pure and Applied Algebra, 139 (1999), 61–88

1999

[6] [6]

J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5), in Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. doi:10.1145/780506.780516

doi:10.1145/780506.780516 2002

[7] [7]

Eder and T

C. Eder and T. Hofmann, Efficient Gröbner bases computation over principal ideal rings, Journal of Symbolic Computation, 103 (2021), 1–13

2021

[8] [8]

Eder and J.-C

C. Eder and J.-C. Faugère, A survey on signature-based algorithms for com- puting Gröbner bases, Journal of Symbolic Computation , 80 (2017), 719–784. doi:10.1016/j.jsc.2016.07.031

work page doi:10.1016/j.jsc.2016.07.031 2017