the numerical semigroup tree

A numerical semigroup is a cofinite submonoid of the natural numbers¹ under addition. The set of numerical semigroups can be arranged into a rooted tree $\mathcal{T}$, where the vertices of depth $g$ are exactly the numerical semigroups of genus $g$. This tree was first described by Rosales in their 1991 thesis Semigrupos numéricos. We explain how $\mathcal{T}$ can be used to enumerate numerical semigroups by genus, and also discuss some interesting applications.

constructing the tree

Here's how to construct the tree: Make a directed graph with numerical semigroups as vertices, and add the edge $S \rightarrow T$ if and only if $S = T\cup \{F(T)\}$. We'll call this graph $\mathcal{T}$.

We do have to show $\mathcal{T}$ is actually a rooted tree. To do so, we need to establish that for every numerical semigroup $S$, there is a unique (directed) path from $\mathbb{N}$ to $S$. (Note that $\mathbb{N}$ is the only candidate for the root, since it has no incoming edges.) The idea is that you can add $F(S)$ to $S$ to get another numerical semigroup that is one step closer to $\mathbb{N}$.

Lemma. Let $S$ be a numerical semigroup. Then $S \cup \{F(S)\}$ is a numerical semigroup.

Proof. The set $S \cup \{F(S)\}$ is clearly cofinite and contains zero. To show that $S \cup \{F(S)\}$ is closed under addition, it suffices to note that for all nonzero $s \in S$, we have $s + F(S) \in S$ by definition of $F(S)$. So $S \cup \{F(S)\}$ is a numerical semigroup. $\blacksquare$

If we rinse and repeat the "add the Frobenius number" process, we eventually fill in all the gaps of $S$. This means we have a path to $\mathbb{N}$, which clearly has length $g$. It's also obvious that this path is unique, since any numerical semigroup has exactly one incoming edge. We sum up all of this in the following proposition:

Proposition. Let $\mathcal{T}$ be the directed graph whose vertices are numerical semigroups, which has the edge $S \rightarrow T$ if and only if $S = T\cup \{F(T)\}$. Then $\mathcal{T}$ is a rooted tree with root vertex $\mathbb{N}$. Furthermore, the set of vertices of $\mathcal{T}$ with depth $g$ is exactly the set of numerical semigroups with genus $g$.

For the rest of the post, we'll call this tree $\mathcal{T}$ the numerical semigroup tree.

what do the children look like?

In establishing the fact that $\mathcal{T}$ is indeed a rooted tree, we showed that every numerical semigroup has exactly one parent. In particular, we know that we move up the tree by adding in the Frobenius number. But a numerical semigroup may have multiple children, and understanding what these children look like is the key to using $\mathcal{T}$ to enumerate numerical semigroups. It turns out that we move down the tree by removing minimal generators that are larger than the Frobenius number.

Lemma. Let $T$ be a numerical semigroup, and let $S = T \cup \{F(T)\}$. Then $F(T)$ is a minimal generator of $S$.

Proof. It is clear that $F(T)$ is not a sum of two nonzero elements of $T$, so it also cannot be a sum of two nonzero elements of $S$. But $F(T) \in S$, so it must be a minimal generator of $S$. $\blacksquare$

Lemma. Let $S$ be a numerical semigroup, and let $s\in S$ be a minimal generator greater than $F(S)$. Then $S \setminus \{s\}$ is a numerical semigroup with Frobenius number $s$.

Proof. It is obvious that $0 \in S \setminus \{s\}$, and that $S \setminus \{s\}$ is cofinite. Let $a, b \in S \setminus \{s\}$. It is obvious that $a+b \in S \setminus \{s\}$ if either $a$ or $b$ is zero, so suppose they are both nonzero. Since these are also elements of $S$, we have that $a+b \in S$. But $s$ is a minimal generator of $S$, so it is not the sum of two nonzero elements of $S$; that is, $a+b \neq s$. Therefore, $S \setminus \{s\}$ is closed under addition. So $S \setminus \{s\}$ is a numerical semigroup. Since $s$ is greater than $F(S)$, we know that $S$ contains all natural numbers greater than $s$, and we conclude that $S \setminus \{s\}$ has Frobenius number $s$. $\blacksquare$

Together, these lemmas say that the direct children of a numerical semigroup $S$ are exactly the numerical semigroups that can be obtained by removing a minimal generator greater than $F(S)$.² So if you know all the numerical semigroups of genus $g$ (i.e., those with depth $g$), you can compute all the numerical semigroups of genus $g+1$.

This makes it relatively simple to compute all the numerical semigroups of genus $g$ by doing a breadth-first search, and in 2008, Bras-Amorós ran such a search of the tree up to genus 50. A more recent paper by Fromentin and Hivert uses a depth-first search and other optimizations to compute the numerical semigroups up to genus 67. But you do eventually run into computational limits, because the number of numerical semigroups grows exponentially with genus.

related cool results

The numerical semigroup tree has been used to do some pretty cool things.

As we mentioned, the tree is generally useful for computing numerical semigroups, so related algorithms have been used to collect data related to outstanding conjectures. For example, the paper by Fromentin and Hivert mentioned above confirms Wilf's conjecture up to genus 60, a major conjecture in numerical semigroup theory. Later that year, Delgado, Eliahou, and Fromentin verified Wilf's conjecture up to genus 100. To support these efforts, there continue to be advances in the computational efficiency through approaches like the method of seeds by Bras-Amorós and Fernández-González and the Bras-Amorós' unleaved tree method.

Also, the fact that the tree organizes numerical semigroups at all means that it can act a framework to study numerical semigroups with respect to different invariants. For example, García-Sánchez, Marín-Aragón, and Robles-Pérez studied numerical semigroups of small multiplicity via the numerical semigroup tree in 2018, counting numerical semigroups of fixed multiplicity and genus. In 2025, Chappelon, Ramírez Alfonsín, and Stamate used the tree to count numerical semigroups of a given genus and type (another numerical semigroup invariant). In both cases, the authors considered the number of numerical semigroups with respect to some invariant as a function of the genus.

One last cool result: Earlier, I offhandedly mentioned that the number of numerical semigroups grows exponentially with genus, but this is a nontrivial result proven by Zhai in 2011. Before this result, it was unproven whether the number of numerical semigroups of genus $g$ increased with $g$ at all, though it seemed true on a heuristic level. Using the numerical semigrouup tree, Zhai proved that the number of numerical semigroups exhibits Fibonacci-like growth, confirming a conjecture of Bras-Amorós.

appendix

Here's a refresher of some definitions. If you've seen numerical semigroups before, you can skip to the end for a table of notation.

A numerical semigroup is a cofinite submonoid of the natural numbers under addition, which is a lot of word salad to say the following:

Definition (Numerical semigroup). Let $S \subseteq \mathbb{N}$. We say that $S$ is a numerical semigroup if

1. The complement $\mathbb{N} \setminus S$ is finite,
2. The set $S$ is closed under addition; that is, $x, y\in S$ implies $x+y \in S$, and
3. The element $0 \in S$.

We have some special names for a elements with respect to a numerical semigroup $S$. The smallest nonzero element of $S$ is called the multiplicity, denoted $m(S)$. The elements of $\mathbb{N} \setminus S$ are called gaps, the greatest of which is called the Frobenius number, denoted $F(S)$. The number of gaps is called the genus, denoted $g(S)$.

We can generate numerical semigroups similarly to how we generate vector spaces. The numerical semigroup generated by the positive integers $x_{1}, \dots, x_n$, denoted $\langle x_{1},\dots, x_n\rangle$, is the set of nonnegative linear combinations of the $x_i$'s; that is,

The $x_{i}$'s are called generators. Every numerical semigroup $S$ has a set of minimal generators, which is the unique set of generators $X$ with the property that no proper subset of $X$ generates $S$. The relevant piece of theory for us is the following: if we write $S^{*}= S\setminus \{0\}$, the set of minimal generators of $S$ is

That is, the minimal generators are the nonzero elements of $S$ that are not the sum of two nonzero elements of $S$.

This is enough theory to get you through the post, but if you want more information, I would recommend the wonderful monograph Numerical Semigroups by J.C. Rosales and P.A. García-Sánchez.

Table of Notation

In the following, $S$ is a numerical semigroup.