pith. sign in

arxiv: 2503.14664 · v4 · submitted 2025-03-18 · 🧮 math.CO · cs.DM· math.AC

Exploring the unleaved tree of numerical semigroups up to a given genus

Maria Bras-Amor\'os This is my paper

Pith reviewed 2026-05-22 23:23 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.AC
keywords numerical semigroupsgenusunleaved treeenumerationgcd encodingshrinkinggeneratorscombinatorial enumeration
0
0 comments X

The pith

A gcd-shrinking encoding lets the unleaved tree of numerical semigroups be traversed to count all examples of any given genus.

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

The paper develops an algorithm that traverses an unleaved tree of numerical semigroups by encoding each semigroup through the gcd of its left elements and the shrinking of the semigroup they generate. Transition rules move from a parent semigroup or a predecessor sibling to the next one while determining right and strong generators directly from the encoding. This produces the exact counts n_76 = 29028294421710227 and n_77 = 47008818196495180. A reader cares because the method turns an otherwise intractable enumeration into a feasible computation for large genera.

Core claim

By representing each numerical semigroup in the unleaved tree via its gcd-shrinking encoding and defining parent-to-child and sibling-to-sibling transition rules, the algorithm enumerates every semigroup of a target genus exactly once, yielding the values n_76=29028294421710227 and n_77=47008818196495180.

What carries the argument

The gcd-shrinking encoding of a numerical semigroup, which stores the gcd of its left elements together with the semigroup generated by those elements divided by the gcd.

If this is right

  • Right generators and strong generators of any semigroup can be recovered directly from its gcd and shrinking values.
  • The traversal never processes leaves at depths below the target genus.
  • Exact counts become available for all genera through 77.
  • The same encoding supports both exploration and pure counting of the semigroups.

Where Pith is reading between the lines

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

  • The same traversal could be continued to genus 78 or higher given enough computing resources.
  • Growth-rate patterns in the sequence n_g might become visible once more terms are computed this way.
  • Comparable tree encodings could be tried for other graded combinatorial families such as integer partitions or plane trees.

Load-bearing premise

The gcd-shrinking encoding and the parent and sibling transition rules together represent every numerical semigroup exactly once with no omissions or duplicates.

What would settle it

Run the algorithm on genus 10, where the count is independently known to be 42, and check whether the output matches 42.

read the original abstract

We present a new algorithm to explore or count the numerical semigroups of a given genus which uses the unleaved version of the tree of numerical semigroups. In the unleaved tree there are no leaves rather than the ones at depth equal to the genus in consideration. For exploring the unleaved tree we present a new encoding system of a numerical semigroup given by the gcd of its left elements and its shrinking, that is, the semigroup generated by its left elements divided by their gcd. We show a method to determine the right generators and strong generators of a semigroup by means of the gcd and the shrinking encoding, as well as a method to encode a semigroup from the encoding of its parent or of its predecessor sibling. With the new algorithm we obtained $n_{76}=29028294421710227$ and $n_{77}=47008818196495180$.

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 manuscript presents a new algorithm for counting numerical semigroups of a prescribed genus that traverses an unleaved version of the standard tree of numerical semigroups. The algorithm relies on a gcd-shrinking encoding of each semigroup together with explicit rules for recovering right/strong generators and for producing the encodings of children and sibling successors. Using this procedure the authors compute the previously unknown values n_76 = 29028294421710227 and n_77 = 47008818196495180.

Significance. If the gcd-shrinking encoding together with the parent-to-child and sibling-to-sibling transitions is bijective, the work supplies the first explicit counts beyond genus 75 and demonstrates a practical method for exploring the tree at depths that were previously inaccessible. The encoding itself may also be of independent interest for other enumeration problems on numerical semigroups.

major comments (2)
  1. The central claim that the reported values of n_76 and n_77 are exact rests on the assertion that the gcd-shrinking encoding plus the transition rules produce each numerical semigroup of genus g exactly once. The manuscript describes how to recover generators from an encoding and how to generate child and sibling encodings, but supplies neither an inductive argument establishing bijectivity nor an exhaustive verification against the known sequence up to genus 75. Without one of these, an undetected omission or duplication at any depth would propagate directly to the headline counts.
  2. No cross-checks, error bounds, or sample computations for small genera (e.g., explicit enumeration up to genus 20 or 30) are provided to confirm that the new encoding reproduces the already tabulated values of n_g. Such a sanity check is load-bearing for any computational claim of this magnitude.
minor comments (2)
  1. The abstract and introduction would benefit from a short table or paragraph listing the previously known values of n_g up to genus 75 so that readers can immediately see the extension achieved.
  2. Notation for the gcd and shrinking operations is introduced informally; a single displayed definition with consistent symbols would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed report and for highlighting the need for explicit verification of the algorithm's correctness. We address each major comment below and will revise the manuscript to incorporate the requested additions.

read point-by-point responses

  1. Referee: The central claim that the reported values of n_76 and n_77 are exact rests on the assertion that the gcd-shrinking encoding plus the transition rules produce each numerical semigroup of genus g exactly once. The manuscript describes how to recover generators from an encoding and how to generate child and sibling encodings, but supplies neither an inductive argument establishing bijectivity nor an exhaustive verification against the known sequence up to genus 75. Without one of these, an undetected omission or duplication at any depth would propagate directly to the headline counts.

    Authors: We agree that an explicit inductive proof of bijectivity is required to rigorously support the exactness of the computed values. The transition rules are constructed to mirror the standard parent-child and sibling relations in the unleaved tree while preserving uniqueness via the gcd-shrinking representation, but the manuscript does not contain a formal inductive argument. In the revised version we will add a dedicated section providing such an inductive proof that every numerical semigroup of genus g is generated exactly once. revision: yes

  2. Referee: No cross-checks, error bounds, or sample computations for small genera (e.g., explicit enumeration up to genus 20 or 30) are provided to confirm that the new encoding reproduces the already tabulated values of n_g. Such a sanity check is load-bearing for any computational claim of this magnitude.

    Authors: We acknowledge the absence of explicit small-genus verification in the current manuscript. We will add a new subsection that recomputes the known sequence n_g for all g ≤ 30 using the gcd-shrinking algorithm and tabulates the results against the established values, thereby confirming agreement before proceeding to the larger genera. revision: yes

Circularity Check

0 steps flagged

No circularity detected; counts are direct algorithmic outputs

full rationale

The paper introduces a gcd-shrinking encoding and parent/sibling transition rules for traversing the unleaved tree, then reports the resulting enumeration values n_76 and n_77. No equations, definitions, or self-citations in the provided text reduce these counts to fitted parameters, renamed inputs, or self-referential quantities by construction. The bijectivity of the encoding is presented as a methodological claim whose verification lies outside the derivation itself; the reported numbers are computed outputs rather than tautological restatements of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 2 invented entities

The central claim rests on standard domain assumptions about the tree organization of numerical semigroups and introduces two new algorithmic constructs without free parameters or external validation.

axioms (1)
  • domain assumption Numerical semigroups admit a tree structure in which each semigroup has well-defined children obtained by adding minimal generators.
    Invoked by the description of the unleaved tree and parent-to-child encoding transitions.
invented entities (2)
  • unleaved tree no independent evidence
    purpose: Tree of numerical semigroups containing no leaves except at the target genus depth.
    New structural device introduced to support the enumeration algorithm.
  • gcd-shrinking encoding no independent evidence
    purpose: Representation of a numerical semigroup by the gcd of its left elements and the shrunk semigroup they generate.
    New encoding used to recover generators and to perform parent/sibling transitions.

pith-pipeline@v0.9.0 · 5680 in / 1295 out tokens · 109260 ms · 2026-05-22T23:23:06.984457+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Bras-Amor´ os

    M. Bras-Amor´ os. Acute semigroups, the order bound on the minimum distance, and the Feng-Rao improvements. IEEE Trans. Inform. Theory , 50(6):1282–1289, 2004

    work page 2004

  2. [2]

    Bras-Amor´ os

    M. Bras-Amor´ os. A note on numerical semigroups. IEEE Trans. Inform. Theory, 53(2):821–823, 2007

    work page 2007

  3. [3]

    Bras-Amor´ os

    M. Bras-Amor´ os. On numerical semigroups and their applications to algebraic geometry codes, in Thematic Seminar ”Algebraic Geometry, Coding and Comput- ing”, Universidad de Valladolid en Segovia. http://www.singacom.uva.es/oldsite/ seminarios/WorkshopSG/workshop2/Bras_SG_2007.pdf, 2007

    work page 2007

  4. [4]

    Bras-Amor´ os

    M. Bras-Amor´ os. Fibonacci-like behavior of the number of numerical semigroups of a given genus. Semigroup Forum, 76(2):379–384, 2008

    work page 2008

  5. [5]

    Bras-Amor´ os

    M. Bras-Amor´ os. Bounds on the number of numerical semigroups of a given genus. J. Pure Appl. Algebra , 213(6):997–1001, 2009

    work page 2009

  6. [6]

    Bras-Amor´ os

    M. Bras-Amor´ os. On the seeds and the great-grandchildren of a numerical semi- group. Math. Comp., 93(345):411–441, 2024

    work page 2024

  7. [7]

    Bras-Amor´ os and S

    M. Bras-Amor´ os and S. Bulygin. Towards a better understanding of the semigroup tree. Semigroup Forum, 79(3):561–574, 2009

    work page 2009

  8. [8]

    Bras-Amor´ os and J

    M. Bras-Amor´ os and J. Fern´ andez-Gonz´ alez. Computation of numerical semi- groups by means of seeds. Math. Comp., 87(313):2539–2550, 2018

    work page 2018

  9. [9]

    Bras-Amor´ os and J

    M. Bras-Amor´ os and J. Fern´ andez-Gonz´ alez. The right-generators descendant of a numerical semigroup. Math. Comp., 89(324):2017–2030, 2020. 14

    work page 2017

  10. [10]

    Bras-Amor´ os and M Rosas-Ribeiro

    M. Bras-Amor´ os and M Rosas-Ribeiro. Rarity of the infinite chains in the tree of numerical semigroups. Submitted (https://arxiv.org/abs/2401.18060), 2024

    work page arXiv 2024

  11. [11]

    M. Delgado. Trimming the numerical semigroups tree to probe Wilf’s conjecture to higher genus. arXiv:1910.12377, 2019

    work page arXiv 1910

  12. [12]

    Delgado, S

    M. Delgado, S. Eliahou, and J. Fromentin. A verification of Wilf’s conjecture up to genus 100. J. Algebra, 664:150–163, 2025

    work page 2025

  13. [13]

    Fromentin and F

    J. Fromentin and F. Hivert. Exploring the tree of numerical semigroups. Math. Comp., 85(301):2553–2568, 2016

    work page 2016

  14. [14]

    Kirfel and R

    C. Kirfel and R. Pellikaan. The minimum distance of codes in an array coming from telescopic semigroups. IEEE Trans. Inform. Theory, 41(6, part 1):1720–1732,

    work page

  15. [15]

    Special issue on algebraic geometry codes

    work page

  16. [16]

    Medeiros

    N. Medeiros. Numerical semigroups. https://web.archive.org/web/20150911134119/ http://w3.impa.br/~nivaldo/algebra/semigroups/index.html

    work page arXiv

  17. [17]

    J. C. Rosales. Numerical semigroups with multiplicity three and four. Semigroup Forum, 71(2):323–331, 2005

    work page 2005

  18. [18]

    J. C. Rosales. Families of numerical semigroups closed under finite intersections and for the frobenius number. Houston Journal of Mathematics , 2008

    work page 2008

  19. [19]

    J. C. Rosales, P. A. Garc´ ıa-S´ anchez, J. I. Garc´ ıa-Garc´ ıa, and J. A. Jim´ enez Madrid. The oversemigroups of a numerical semigroup. Semigroup Forum, 67(1):145–158, 2003

    work page 2003

  20. [20]

    J. C. Rosales, P. A. Garc´ ıa-S´ anchez, J. I. Garc´ ıa-Garc´ ıa, and J. A. Jim´ enez Madrid. Fundamental gaps in numerical semigroups. J. Pure Appl. Algebra , 189(1-3):301– 313, 2004

    work page 2004

  21. [21]

    N. J. A. Sloane. The on-line encyclopedia of integer sequences (A007323). https: //oeis.org/A007323

    work page

  22. [22]

    A. Zhai. Fibonacci-like growth of numerical semigroups of a given genus.Semigroup Forum, 86(3):634–662, 2013. 15

    work page 2013