Numerical Semigroups and Delta Sets

In this post I want to outline my main research project, which involves non-unique factorization in numerical semigroups. I’m going to define semigroups and numerical semigroups; explain what non-unique factorization means; define the invariant I study, called the delta set; and talk about some of the specific questions I’m interested in.

Semigroups

A semigroup is a set $S$ with one associative operation. This really just means we have a set of things, and some way of combining any two of them to get another. Semigroups generalize the more common idea of a group, which has an identity and inverses in addition to the associative operation. Every group is also a semigroup, but not every semigroup is a group.¹

The simplest example of a semigroup is the natural numbers $\mathbb{N}$, with the operation of addition: we can add any two natural numbers together, but without negative numbers we don’t have any way to subtract, which would be an inverse. This is the free semigroup on one generator, which means we can get every element by starting with $1$ and adding it to itself some number of times.

Other examples of semigroups are:

• $\mathbb{N}^n, +$: ordered $n$-tuplets of natural numbers.
• $\mathbb{N}, \times$: the natural numbers using multiplication as the operation. This has infinitely many generators, since we need to start with every prime number to get every possible natural number.
• String Concatenation: we can take our set to be the set of all strings of English letters, and we combine two strings by just sticking the second one after the first.
• Block Monoids are semigroups whose elements are lists of group elements that mulitiply out to zero under the operation of concatenation.

Numerical semigroups, which are the main object I study, are formally defined as sub-semigroups of the natural numbers but that phrase doesn’t actually explain a lot if you’re not already familiar with the field. However, I can explain what they actually are them much less technically and more simply.

Numerical Semigroups

We can define the numerical semigroup generated by $a_1, \dots, a_k$ to be the set of integers \[ \langle a_1, \dots, a_k \rangle = {n_1 a_1 + \dots + n_k a_k : n_i \in \mathbb{Z}_{\geq 0} }. \] In other words, our semigroup is the set of all the numbers you can get by adding up the generators some number of times, but without allowing subtraction.

I like to think about the Chicken McNugget semigroup to explain this. When I was a kid, at McDonald’s you could get a 4-piece, 6-piece, or 9-piece order of Chicken McNuggets.² And then we can ask: which numbers of nuggets is it possible to order?

You certainly can’t order one, two, or three nuggets. You can order four, but not five. You can order six, but not seven. You can get eight by ordering two 4-pieces, nine by ordering one 9-piece, and ten by ordering a 4-piece and a 6-piece. There’s no way to order exactly eleven nuggets, and it turns out we can get any number of nuggets past that exactly. (This makes eleven the Frobenius number for this semigroup). We can summarize all this in the table below:

\[ \begin{array}{cc} 1 & \text{not possible} \\\
2 & \text{not possible} \\\
3 & \text{not possible} \\\
4 & = 1 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 \\\
5 & \text{not possible} \\\
6 & = 0 \cdot 4 + 1 \cdot 6 + 0 \cdot 9 \\\
7 & \text{not possible} \\\
8 & = 2 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 \\\
9 & = 0 \cdot 4 + 0 \cdot 6 + 1 \cdot 9 \\\
10 & = 1 \cdot 4 + 1 \cdot 6 + 0 \cdot 9 \\\
11 & \text{not possible} \\\
12 & = 3 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 \\\
& = 0 \cdot 4 + 2 \cdot 6 + 0 \cdot 9 \\\
13 & = 1 \cdot 4 + 0 \cdot 6 + 1 \cdot 9 \end{array} \]

Looking at this table you might notice something else: there are two rows for the number 12, because we can order 12 nuggets in two different ways: we can order three 4-piece orders, or two 6-piece orders. We call each of these ways of ordering twelve nuggets a factorization of 12 with respect to the generators $4,6,9$. And not only do we have two different factorizations of 12; they actually have different numbers of factors!

If we look at larger numbers, the variety in factorizations becomes far greater. Consider this table of ways to factor 36: \[ \begin{array}{cc} \text{factorization} & \text{length} \\\
9 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 & 9 \\\
6 \cdot 4 + 2 \cdot 6 + 0 \cdot 9 & 8 \\\
3 \cdot 4 + 4 \cdot 6 + 0 \cdot 9 & 7 \\\
3 \cdot 4 + 1 \cdot 6 + 2 \cdot 9 & 6 \\\
0 \cdot 4 + 6 \cdot 6 + 0 \cdot 9 & 6 \\\
0 \cdot 4 + 3 \cdot 6 + 2 \cdot 9 & 5 \\\
0 \cdot 4 + 0 \cdot 6 + 4 \cdot 9 & 4 \end{array} \] We have seven distinct ways we can factor 12. The shortest has four factors and the longest has nine; every length in between is represented.

From here we can ask a number of questions. How many ways can we order a given number of chicken nuggets? How many different lengths can these factorizations have? What patterns can we find?

All this is very different from what we’re used to. When we factor integers into prime numbers, the Fundamental Theorem of Arithmetic tells us that there is a unique way to do this. We generally learn this in grade school, and so from a very young age we’re used to having only one way to factor things. But this unique factorization property isn’t universal, and it doesn’t apply here.

Numerical semigroups essentially never have unique factorization. But we want to find ways to measure how not-unique their factorization is.

The Delta Set

In my research I study something called the delta set of a semigroup. The delta set is a way of measuring how complicated the relationships among different factorizations can get.

For an element $x$ in a semigroup, we can look at all the factorizations of $x$, and then we can look at all the possible lengths of these factorizations. (In our example above, we had $\mathbf{L}(36) = \{4,5,6,7,8,9\}$; we don’t repeat the $6$ because we only care about which lengths are possible, and not how many times they occur). Then we can ask a bunch of questions about these sets of lengths.

A simple thing to compute is the elasticity of an element, which is just the ratio of the longest factorization to the shortest, and tells you how much the lengths can vary. (The elasticity of $36$ is $9/4$). A good exercise is to convince yourself that the largest elasticity of any element in a semigroup is the ratio of the largest generator to the smallest generator. (And thus that $36$ has the maximum possible elasticity for $\langle 4, 6, 9 \rangle$).

The delta set is a bit more complicated. The delta set of $x$ is the set of successive differences in lengths. So instead of looking at the shortest and longest factorizations, we look at all of them, and see what sort of gaps show up. (For our example, the delta set is just $\Delta(36) = \{1\}$, since there’s a factorization of each length between $4$ and $9$. If the set of lengths were $\{3,5,8,15\}$ then the delta set would be $\{2,3,7\}$).

We want to understand the whole semigroup, not just individual elements. So we often want to talk about the delta set of an entire semigroup, which is just the union of the delta sets of all the elements. So $\Delta(S)$ tells us what kind of gaps can appear in any set of lengths for any element of the semigroup. It turns out that for the Chicken McNugget semigroup $S = \langle 4,6,9 \rangle$, the delta set is just $\Delta(S) = \{1\}$. This means that the delta set of any element is just $\{1\}$, and thus that every set of lengths is a set of consecutive integers $\{n,n+1, \dots, n+k \}$.

What Do We Know?

Delta sets can be a little tricky to compute. It’s fairly easy to show a number is in the delta set of a semigroup: find an element, calculate all the factorization lengths, and see that you have a gap of the desired size. But to show that a number is not in the delta set of the semigroup, you have to show that it isn’t in the delta set of any element, which is much trickier.

However, there are a few things we do know.

• The smallest element of the delta set is the greatest common divisor of the other elements of the delta set. This means that $\{2,3\}$ can’t be the delta set of any semigroup, since $2$ isn’t the GCD of $2$ and $3$.

• If $S = \langle a, b \rangle$ is generated by exactly two elements, then $\Delta(S) = \{b - a\}$. More generally, if $S = \langle a, a+d, a+2d, \dots, a+kd \rangle$ then $\Delta(S) = \{d\}$. (We call such semigroups “arithmetic semigroups” since their generating set is an arithmetic progression).

• For any numerical semigroup $S$, there is a finite collection of (computable) elements called the Betti elements, and the maximum element of the delta set of $S$ is in the delta set of at least one of the Betti elements.

• Finally and most importantly, the delta set is eventually periodic. This means that if you check the delta sets for a (possibly large but known) number of elements of the semigroup, you will see everything you can possibly see. This makes it possible to compute the delta set of any given semigroup and know you haven’t left anything out. ³

But this is nearly everything that we really know about delta sets. There are a lot of open questions left, which primarily fall into two categories:

1. For some nice category of semigroup, compute the delta set. We’ve already seen this question answered for semigroups generated by arithmetic sequences; we also have complete or partial answers for semigroups generated by generalized arithmetic sequences, geometric sequences, and compound sequences.

2. The realization problem: given a set of natural numbers, is it the delta set of some numerical semigroup? We don’t actually know a lot about this. About the only thing that we know can’t happen is a minimum element that isn’t the GCD of the set. But to show that something can happen, about all we can do is find a specific semigroup that has that delta set. There’s a lot of room to explore here.

Non-Minimal Generating Sets

In my research I introduce one more complication. Earlier we talked about the Chicken McNugget semigroup, of all the ways we can build orders out of 4, 6, or 9 chicken nuggets. But McDonald’s also offers a 20 piece order of chicken nuggets. ⁴

From a purely algebraic perspective, this doesn’t change anything. Anything we can get with 20 piece orders, we can get with a combination of 4 and 6 pieces, so we have the same set and the same operation, and thus the same semigroup. (We say that 20 isn’t “irreducible” because we can factor it into other simpler elements). So in this sense, nothing should change.

But the set of factorizations does change. If we replicate our earlier table of factorizations of 36 but now allow $20$ as a factor, we get \[ \begin{array}{cc} \text{factorization} & \text{length} \\\
9 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 + 0 \cdot 20 & 9 \\\
6 \cdot 4 + 2 \cdot 6 + 0 \cdot 9 + 0 \cdot 20 & 8 \\\
3 \cdot 4 + 4 \cdot 6 + 0 \cdot 9 + 0 \cdot 20 & 7 \\\
3 \cdot 4 + 1 \cdot 6 + 2 \cdot 9 + 0 \cdot 20 & 6 \\\
0 \cdot 4 + 6 \cdot 6 + 0 \cdot 9 + 0 \cdot 20 & 6 \\\
0 \cdot 4 + 3 \cdot 6 + 2 \cdot 9 + 0 \cdot 20 & 5 \\\
\color{blue}{4 \cdot 4 + 0 \cdot 6 + 0 \cdot 9 + 1 \cdot 20} & \color{blue}{5} \\\
0 \cdot 4 + 0 \cdot 6 + 4 \cdot 9 + 0 \cdot 20 & 4 \\\
\color{blue}{1 \cdot 4 + 2 \cdot 6 + 0 \cdot 9 + 1 \cdot 20 } & \color{blue}{4} \end{array} \] The extra generator gives us the two additional factorizations in blue.

Now every question we asked about factorizations in numerical semigroups, we can ask again for factorizations with respect to our non-minimal generating set. For instance, we can ask for the delta set with respect to our generating set. For 36 above, we see that the delta set is still 1, just as it was before; nothing has changed.

But let’s look instead at the element 20. With our old generating set of $4,6,9$, we can only get 20 nuggets in two ways. But with our non-minimal generating set, we have three different ways to order 20 nuggets: $20 = 5 \cdot 4 = 2 \cdot 4 + 2 \cdot 6 = 1 \cdot 20$. These three “factorizations” have lengths 5, 4, and 1, and a little experimentation will convince you that they’re the only possible factorizations. Therefore our set of lengths is $\mathbf{L}(20) = \{1,4,5\}$ and the delta set is $\Delta(20) = \{1,3\}$.

This is a big change! With the original, minimal generating set, the delta set of the entire semigroup was ${1}$. There was no element with a length gap larger than 1. But by adding a new generator in, we can get an element whose delta set is ${1,3}$. And a little experimentation shows us that \[ 26 = 5 \cdot 4 + 1 \cdot 6 = 2 \cdot 4 + 3 \cdot 6 = 2 \cdot 4 + 2 \cdot 9 = 1 \cdot 6 + 1 \cdot 20 \] and thus $\mathbf{L}(26) = \{2,4,5,6\}$ and $\Delta(26) = \{1,2\}$. So the delta set for the entire semigroup is $\{1,2,3\}$.⁵ We’ve gotten a different delta set for the exact same semigroup, but using a different set of generators.

This raises a number of questions for us to study. We can start with our previous two questions: given a semigroup (and a non-minimal set of generators), what is the delta set? And given a set, is it the delta set of some semigroup and non-minimal generating set? But we also have a new question: what happens to the delta set of a semigroup as we continually add things to the generating set? Can we make the delta set bigger? Can we make it smaller? What ways of adding generators produce interesting patterns?

There’s a lot of fertile ground here. A few questions have been answered already, in a paper I cowrote with Scott Chapman, Rolf Hoyer, and Nathan Kaplan in 2010. For instance, it is always possible to force the delta set to be $\{1\}$ by adding more elements to the generating set. A couple other groups have done some work since then, but as far as I know, nothing else has been published.

But hopefully I’ve convinced you that there are quite a few interesting and unanswered questions in this field. Many of the answers should be accessible with a bit of work, and I hope to be able to provide some of them soon.

Have a question about numerical semigroups? Factorization theory? My research? Tweet me @ProfJayDaigle or leave a comment below.