pith. sign in

arxiv: 2601.05026 · v3 · submitted 2026-01-08 · 💻 cs.SC · cs.DS

A data structure for monomial ideals with applications to signature Gr\"obner bases

Pierre Lairez , Rafael Mohr , Th\'eo Ternier This is my paper

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

classification 💻 cs.SC cs.DS
keywords monomial idealsdata structuresMDDssignature Gröbner basesmembership testsdirected acyclic graphsalgebraic solving
0
0 comments X

The pith

Monomial divisibility diagrams replace list representations to accelerate membership tests during signature Gröbner basis computations.

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

The paper introduces monomial divisibility diagrams as a data structure for monomial ideals that supports fast membership tests and generator insertion. The structure is built from a canonical tree by maximally sharing equal subtrees, which produces a compact directed acyclic graph. The authors derive complexity bounds for the core operations and measure diagram sizes on practical examples. When plugged into the signature Gröbner basis routine of AlgebraicSolving.jl, the diagrams replace lists of generators with divmasks and produce substantial reductions in overall running time.

Core claim

Monomial divisibility diagrams arise from a canonical tree representation of monomial ideals in which identical subtrees are maximally shared to form a directed acyclic graph; this structure supports efficient insertion of generators and rapid membership tests, and its adoption in signature Gröbner basis software replaces list-of-generators representations to achieve substantial speed-ups.

What carries the argument

Monomial divisibility diagrams (MDDs): a directed acyclic graph obtained by maximal sharing of subtrees in a canonical tree representation of the monomial ideal, used to accelerate membership testing.

If this is right

  • Membership queries in monomial ideals execute more rapidly than with generator lists and divmasks.
  • Reductions to zero are detected earlier during signature Gröbner basis construction.
  • Overall runtime of the signature Gröbner basis algorithm decreases in the AlgebraicSolving.jl implementation.
  • The data structure scales to the monomial ideals that appear in practical polynomial system solving.

Where Pith is reading between the lines

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

  • The same shared-subtree DAG technique could be adapted to speed up monomial operations in other symbolic algorithms beyond Gröbner bases.
  • If diagram sizes remain controlled across a wider range of inputs, MDDs may become a default representation for monomial ideals in computer algebra libraries.
  • The canonical sharing mechanism offers a template for compact encodings of other divisibility or partial-order structures arising in algebra.

Load-bearing premise

The empirical size of MDDs stays manageable and the cost of maintaining the DAG does not offset the membership gains for the monomial ideals arising in signature Gröbner basis computations.

What would settle it

A benchmark algebraic computation in which the MDD representation grows larger than the corresponding list with divmasks or in which diagram maintenance dominates runtime, eliminating the observed speed-up.

Figures

Figures reproduced from arXiv: 2601.05026 by Pierre Lairez, Rafael Mohr, Th\'eo Ternier.

Figure 1
Figure 1. Figure 1: Two trees representing the monomial ideal ⟨𝑥 𝑦𝑧, 𝑥2 , 𝑥 𝑦2 ⟩. The first level correspond the variable 𝑧, the second to 𝑦, and the last to 𝑥. The left tree is not an ideal tree because ⟨𝑥 2 , 𝑥 𝑦2 ⟩ is not included in ⟨𝑥 𝑦⟩. The right tree is an ideal tree. Note the extra path corresponding to the monomial 𝑧𝑥2 . 2.2 Ideal trees Given a set T, let ℕ ⇀ T be the set of partial functions from ℕ to T with finite… view at source ↗
Figure 2
Figure 2. Figure 2: Insertion of a monomial 𝛼 = 𝑥 ·𝛼 ′ in an ideal tree 𝑡 with dom(𝑡) = {𝑎, 𝑏, 𝑐 }, with 𝑎 < 𝑏 < 𝑐. Pruning of redundant subtrees after insertion is not shown. Algorithm 2 Insertion in an ideal tree. input 𝛼 ∈ ℕ 𝑛 output the ideal tree representing ⟨𝛼⟩ 1 def singleton(𝛼): 2 if len(𝛼) = 0: return {} 3 𝑥 · 𝛼 ′ ← 𝛼 4 𝑡 ← {𝑥 ↦→ singleton(𝛼 ′ )} 5 return 𝑡 input an ideal tree 𝑡 (or ∅), and 𝛼 ∈ ℕ 𝑛 output the ideal … view at source ↗
Figure 3
Figure 3. Figure 3: The ideal tree of the monomial ideal generated in ℕ 5 by the leading monomials of the 55 elements of the Gröbner basis of five generic equations of degree 3, 3, 3, 3, and 2. 0 2 4 6 8 10 0 0 1 3 4 5 0 0 0 0 0 0 0 0 0 1 2 3 4 1 3 4 0 0 0 0 1 2 3 1 2 3 2 3 2 1 0 1 2 1 2 1 2 ⟂ 1 1 1 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The monomial divisibility diagram of the ideal tree of [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Size of the ideal tree and of the MDD across benchmark families. Each pair of points corresponds to a monomial ideal. The abscissa of a point is the size of the list of generators, in machine words, that is, the number of generators times the number of variables. The ordinate of the lower point of a pair is the size, in machine words, of the MDD in sequential form, that is, twice the number of edges plus t… view at source ↗
Figure 6
Figure 6. Figure 6: Monomial divisibility diagram of the monomial ideal in ℕ 14 generated by the leading monomials of a Gröbner basis of eco-14. The ideal is minimally generated by 2852 monomials. The MDD has 173 nodes [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
read the original abstract

We introduce monomial divisibility diagrams (MDDs), a data structure for monomial ideals that supports insertion of new generators and fast membership tests. MDDs stem from a canonical tree representation by maximally sharing equal subtrees, yielding a directed acyclic graph. We establish basic complexity bounds for membership and insertion, and study empirically the size of MDDs. As an application, we integrate MDDs into the signature Gr\"obner basis implementation of the Julia package AlgebraicSolving.jl. Membership tests in monomial ideals are used to detect some reductions to zero, and the use of MDDs leads to substantial speed-ups compared to the existing representation by lists of generators with divmasks.

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 introduces monomial divisibility diagrams (MDDs), a DAG data structure for monomial ideals obtained from a canonical tree representation with maximal subtree sharing. It establishes basic worst-case complexity bounds for insertion and membership testing, empirically measures MDD node counts on ideals generated during signature Gröbner basis runs, and integrates MDDs into the signature Gröbner basis implementation of AlgebraicSolving.jl, reporting substantial speed-ups over the prior list-of-generators-plus-divmasks representation for detecting zero reductions.

Significance. If the empirical speed-ups hold and MDD sizes remain manageable, the structure offers a practical improvement for monomial ideal operations inside signature-based Gröbner basis algorithms. The combination of explicit complexity bounds with concrete timing comparisons against an independent baseline in a publicly available Julia package is a clear strength.

major comments (2)
  1. [empirical evaluation] Empirical evaluation section: the manuscript states that MDD node counts and timing comparisons were measured on ideals arising in signature Gröbner basis computations, yet provides neither the raw data tables nor the precise list of benchmark ideals (number of generators, degrees, or ring dimensions). This information is load-bearing for the central performance claim.
  2. [complexity analysis] Complexity analysis section: the basic worst-case bounds for MDD insertion and membership are asserted, but the proofs are not supplied in sufficient detail to verify the claimed asymptotic behavior independent of the empirical results.
minor comments (2)
  1. [abstract] The abstract refers to 'basic complexity bounds' without stating them explicitly; a one-sentence summary of the bounds would improve readability.
  2. Notation for the MDD construction (canonical tree to DAG sharing) is introduced without a small worked example; adding one would clarify the maximal-sharing step.

Simulated Author's Rebuttal

2 responses · 0 unresolved

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

read point-by-point responses

  1. Referee: Empirical evaluation section: the manuscript states that MDD node counts and timing comparisons were measured on ideals arising in signature Gröbner basis computations, yet provides neither the raw data tables nor the precise list of benchmark ideals (number of generators, degrees, or ring dimensions). This information is load-bearing for the central performance claim.

    Authors: We agree that the empirical section would benefit from greater reproducibility. In the revised manuscript we will add an explicit table (or subsection) enumerating the benchmark ideals, reporting for each the number of variables, the degrees of the generators, the number of generators, and the source of the ideal (e.g., the specific signature Gröbner basis run). We will also deposit the raw timing and node-count data in a public repository and cite it from the paper. revision: yes

  2. Referee: Complexity analysis section: the basic worst-case bounds for MDD insertion and membership are asserted, but the proofs are not supplied in sufficient detail to verify the claimed asymptotic behavior independent of the empirical results.

    Authors: We acknowledge that the current presentation of the complexity arguments is concise. In the revision we will expand the relevant section to include complete, self-contained proofs of the stated worst-case bounds (linear in the number of generators for insertion and linear in the degree for membership), with all steps spelled out and independent of the experimental data. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper defines MDDs directly via canonical tree representation of monomial divisibility with subtree sharing to form a DAG. It supplies explicit worst-case complexity bounds for insertion and membership tests, plus empirical node-count measurements on ideals arising in signature Gröbner basis runs. Integration into AlgebraicSolving.jl is evaluated by direct timing comparison against the independent list-plus-divmask baseline. No equation reduces a claimed result to a fitted parameter, self-citation, or renamed input; the central claims rest on the explicit construction and external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The contribution rests on standard algebraic properties of monomial divisibility together with the algorithmic construction of the shared DAG; no numerical parameters are fitted and the only invented entity is the MDD itself.

axioms (1)
  • domain assumption Monomial divisibility forms a partial order on the monoid of monomials
    Invoked implicitly when defining membership tests and the tree representation of generators.
invented entities (1)
  • Monomial divisibility diagram (MDD) no independent evidence
    purpose: Compact DAG representation of a monomial ideal obtained by maximal sharing of equal subtrees
    The MDD is the central new artifact introduced to replace list-based storage.

pith-pipeline@v0.9.0 · 5412 in / 1252 out tokens · 84916 ms · 2026-05-16T16:25:10.003727+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

24 extracted references · 24 canonical work pages · 2 internal anchors

  1. [1]

    Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. 2021. Examples for msolve. https://msolve.lip6.fr/examples/index.html

    work page 2021

  2. [2]

    Jérémy Berthomieu, Christian Eder, and Mohab Safey El Din. 2021. Msolve: a library for solving polynomial systems. In Proc. ISSAC 2021 . ACM, (2021), 51–58. doi: 10/gk8549. 1The modified version of AlgebraicSolving.jl is available at https://gitlab.inria.fr/math exp/algebraicsolving.jl (branch withmdd, to be merged upstream in a near future). The Julia im...

    work page 2021

  3. [3]

    Cox, John Little, and Donal O’Shea

    David A. Cox, John Little, and Donal O’Shea. 2015.Ideals, Varieties, and Algo- rithms. (4th ed.). Undergraduate Texts in Mathematics. Springer. doi: 10/hzv6

    work page 2015

  4. [4]

    Christian Eder and Jean-Charles Faugère. 2017. A survey on signature-based algorithms for computing Gröbner bases. J. Symb. Comput., 80, 3, (2017), 719–

    work page 2017

  5. [5]

    Christian Eder and Bjarke Hammersholt Roune. 2013. Signature rewriting in Gröbner basis computation. In Proc. ISSAC 2013. ACM, (2013), 331–338. isbn: 978-1-4503-2059-7. doi: 10/ggkppx

    work page 2013

  6. [6]

    Jean-Charles Faugère. 1999. A new efficient algorithm for computing Gröbner bases (𝐹4 ). J. Pure Appl. Algebra, 139, 1-3, 61–88. doi: 10/bpq5dx

    work page 1999

  7. [7]

    Jean-Charles Faugère. 2002. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proc. ISSAC 2002. ACM, (2002), 75–83. doi: 10/bd4nnq

    work page 2002

  8. [8]

    Jean-Christophe Filliâtre and Sylvain Conchon. 2006. Type-safe modular hash- consing. In Proc. ML 2006. ACM, (2006), 12–19. isbn: 978-1-59593-483-3. doi: 10/bbfkc4

    work page 2006

  9. [9]

    Shuhong Gao, Frank Volny, and Mingsheng Wang. 2016. A new framework for computing Gröbner bases. Math. Comp., 85, 297, (2016), 449–465. doi: 10/f7t889

    work page 2016

  10. [10]

    Shuhong Gao and Mingfu Zhu. 2008. Computing irreducible decomposition of monomial ideals. Version 1. (2008). arXiv: 0811.3425. Pre-published

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  11. [11]

    Gerdt and Yuri A

    Vladimir P. Gerdt and Yuri A. Blinkov. 2005. Janet-like monomial division. In Proc. CASC 2005. Victor G. Ganzha, Ernst W. Mayr, and Evgenii V. Vorozhtsov, (Eds.) Springer, 174–183. isbn: 978-3-540-32070-8. doi: 10/brp4sg

    work page 2005

  12. [12]

    Gerdt, Yuri A

    Vladimir P. Gerdt, Yuri A. Blinkov, and Denis A. Yanovich. 2001. Construction of Janet bases I. Monomial bases. InProc. CASC 2001. Victor G. Ganzha, Ernst W. Mayr, and Evgenii V. Vorozhtsov, (Eds.) Springer, 233–247. isbn: 978-3-642- 56666-0. doi: 10/c8c3p3

    work page 2001

  13. [13]

    Eiichi Goto. 1974. Monocopy and Associative Algorithms in Extended LISP. Technical Report TR-74-03. University of Toyko

    work page 1974

  14. [14]

    Mark L. Green. 1998. Generic initial ideals. In Six Lectures on Commutative Algebra. Progress in Mathematics. J. Elias, J. M. Giral, R. M. Miró-Roig, and S. Zarzuela, (Eds.) Birkhäuser, 119–186. isbn: 978-3-0346-0329-4. doi: 10/c7xfx4

    work page 1998

  15. [15]

    Amir Hashemi, Matthias Orth, and Werner M. Seiler. 2022. Complementary decompositions of monomial ideals and involutive bases. Appl. Algebra Eng. Commun. Comput., 33, 6, (2022), 791–821. doi: 10/hbdj7h

    work page 2022

  16. [16]

    Amir Hashemi, Matthias Orth, and Werner M. Seiler. 2023. Recursive structures in involutive bases theory. J. Symb. Comput., 118, (2023), 32–68. doi: 10/hbdj7j

    work page 2023

  17. [17]

    Donald E. Knuth. 2011. The Art of Computer Programming . Vol. 4A. Addison- Wesley

    work page 2011

  18. [18]

    Pierre Lairez. 2024. Axioms for a theory of signature bases. J. Symb. Comput., 123, (2024), 102275. doi: 10/k99k

    work page 2024

  19. [19]

    Peter N. Malkin. 2007. Computing Markov Bases, Gröbner Bases, and Extreme Rays. Université catholique de Louvain

    work page 2007

  20. [20]

    Alexander Milowski

    R. Alexander Milowski. 2004. Computing irredundant irreducible decomposi- tions of large scale monomial ideals. In Proc. ISSAC 2004. ACM, (2004), 235–242. doi: 10/b87wt6

    work page 2004

  21. [21]

    Guillermo Moreno-Socías. 2003. Degrevlex Gröbner bases of generic complete intersections. J. Pure Appl. Algebra, 180, 3, (2003), 263–283. doi: 10/fvbj64

    work page 2003

  22. [22]

    Bjarke Hammersholt Roune. 2009. The Slice Algorithm for irreducible decom- position of monomial ideals. J. Symb. Comput. , 44, 4, (2009), 358–381. doi: 10/fpqfwv

    work page 2009

  23. [23]

    Bjarke Hammersholt Roune and Michael Stillman. 2012. Practical Gröbner basis computation. In Proc. ISSAC 2012. ACM, (2012), 203–210. doi: 10/ggkpqd

    work page 2012

  24. [24]

    Bjarke Hammersholt Roune and Michael Stillman. 2012. Practical Groebner basis computation. (2012). arXiv: 1206.6940. http://arxiv.org/abs/1206.6940

    work page internal anchor Pith review Pith/arXiv arXiv 2012