MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

arXiv:1701.08555v1 [] 30 Jan 2017

REBECCA CONAWAY, FELIX GOTTI, JESSE HORTON, CHRISTOPHER O’NEILL,
ROBERTO PELAYO, MESA WILLIAMS, AND BRIAN WISSMAN
Abstract. A numerical monoid is an additive submonoid of the non-negative integers. Given a numerical monoid S, consider the family of “shifted” monoids Mn
obtained by adding n to each generator of S. In this paper, we examine minimal
relations among the generators of Mn when n is sufficiently large, culminating in a
description that is periodic in the shift parameter n. We explore several applications
to computation, combinatorial commutative algebra, and factorization theory.

1. Introduction
A minimal presentation of a numerical monoid M (that is, an additive submonoid
of the natural numbers) encapsulates the minimal relations among generators of M .
Such minimal presentations arise in the study of toric ideals, where they correspond
to minimal generating sets for kernels of monomial maps [7], and algebraic statistics,
where they correspond to Markov bases [9]. Additionally, many arithmetic invariants
of interest in combinatorial commutative algebra and factorization theory can be easily recovered (both theoretically and computationally) from a minimal presentation,
making them a particularly useful tool in computational algebra [10, 14].
In this paper, we examine families of numerical monoids obtained by “shifting” a
chosen generating set. In particular, given positive integers r1 < · · · < rk , consider
numerical monoids of the form
Mn = hn, n + r1 , . . . , n + rk i,
indexed by a shift parameter n. Our main result is Theorem 4.9, which describes how
minimal presentations of Mn vary with large n. More specifically, we give an explicit
bijection between the minimal presentations of Mn and those of Mn+rk when n > rk2 .
Following Theorem 4.9, we characterize the behavior of several arithmetic invariants determined by minimal presentations (e.g. Betti numbers and catenary degree),
resulting in periodic or periodic-linear descriptions in each case. Some of these characterizations are new, while others strengthen existing results in the literature [6, 15].
Our approach unifies these results (old and new) as consequences of a deeper structural
phenomenon that occurs among the minimal relations of Mn for large n, and improves
each lower bound on n that was previously given; see Remark 5.4 for a thorough
discussion of the benefits of our approach and resulting improvements.
Date: March 9, 2018.
1

2

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

One of the primary consequences of Theorem 4.9 lies in the realm of computation.
While minimal presentations (and many of the arithmetic invariants they determine)
are generally more difficult to compute for monoids with large generators, our results
give a way to more efficiently perform these computations in some cases by instead
computing a minimal presentation for a numerical monoid with smaller generators in
the same shifted family. We discuss the specifics in Remark 5.1, including a forthcoming
implementation in the popular GAP package numericalsgps [8].
2. Background
In this section, we provide the necessary definitions related to the factorization theory
of numerical monoids. In what follows, let N denote the set of non-negative integers.
Definition 2.1. A numerical monoid M is an additive submonoid of N. When we write
M = hm1 , . . . , mt i, we assume m1 < · · · < mt , and the chosen generators m1 , . . . , mt
are called irreducible elements or atoms. We say M is primitive if gcd(m1 , . . . , mt ) = 1.
Definition 2.2. Fix a numerical monoid M = hm1 , . . . , mt i and a ∈ M . A factorization of a is an expression
a = z1 m1 + · · · + zt mt
of a as a sum of irreducible elements of M , which we often represent with the tuple
z = (z1 , . . . , zt ) ∈ Nt . The length of a factorization z of a is the total number
|z| = z1 + · · · + zt
of irreducible elements appearing in z, and the support of z is the set
supp(z) = {mi : zi > 0}
of distinct irreducible elements appearing in z.
Definition 2.3. Fix a numerical monoid M = hm1 , . . . , mt i and a ∈ M . The factorization homomorphism of M is the map π : Nt → M given by
π(z1 , . . . , zt ) = z1 m1 + · · · + zt mt .
The set of factorizations of a is the set
ZM (a) = π −1 (a) = {z ∈ Nt : π(z) = a} ⊂ Nt .
When there can be no confusion, we often omit the subscript and simply write Z(a).
We conclude this section with Theorem 2.4, which appeared as [1, Theorem 4.3]
for minimally generated, primitive numerical monoids. The statement below follows
immediately from the proof of the original statement given in [1].

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

3

Theorem 2.4. Fix m1 < · · · < mt , and suppose M = hm1 , . . . , mt i is not necessarily
primitive or minimally generated by m1 , . . . , mt . The function m : M → N sending
each a ∈ M to its smallest factorization length satisfies
m(a + mt ) = m(a) + 1
for all a > mt−1 mt .
Notation. Through the remainder of this paper, fix r1 < · · · < rk and n ∈ N, and let
S = hr1 , . . . , rk i

and

Mn = hn, n + r1 , . . . , n + rk i

denote additive submonoids of N. Unless otherwise stated, we assume Mn is primitive
and minimally generated as written, but we do not make either assumption for S.
Note that choosing n as the first generator of Mn ensures that every numerical monoid
falls into exactly one shifted family.
3. Sufficiently shifted numerical monoids
In this section, we give the Theorem 3.4 and Corollary 3.5, which identify the core
obstruction to Theorem 4.9 for small n (in the sense of Remark 4.10). This result comes
in the form of a description of the factorizations of Betti elements (Definition 3.1),
whose factorizations encapsulate the minimal relations among atoms.
Definition 3.1. Fix a numerical monoid M and a ∈ M . The factorization graph of a,
denoted ∇a , has vertex set Z(a), and two vertices z, z 0 ∈ Z(a) are connected by an edge
whenever they have at least one irreducible in common. We say a is a Betti element
of M if its factorization graph ∇a is disconnected, and write Betti(M ) for the set of
Betti elements of M .
Example 3.2. The Betti elements of M = h6, 9, 20i are 18 and 60, since
Z(18) = {(3, 0, 0), (0, 2, 0)} and
Z(60) = {(10, 0, 0), (7, 2, 0), (4, 4, 0), (1, 6, 0), (0, 0, 3)}
both yield disconnected factorization graphs. Here, the factorizations of 18 represent
the minimal relation between 6 and 9, namely that in any factorization of an element
a ∈ M , one can replace three copies of 6 with two copies of 9 to yield a new factorization
of a. Similarly, 60 is the first element that can be factored using all three irreducibles,
and thus gives the minimal ways to exchange copies of 20 for copies of 6 and 9.
In contrast, the element 126 ∈ M is not a Betti element of M , even though
(1, 0, 6), (0, 14, 0) ∈ Z(126) have no irreducibles in common. Indeed, this relation can
be obtained by twice exchanging three 20’s for ten 6’s, yielding (21, 0, 0), and then
repeatedly exchanging three 6’s for two 9’s until (0, 14, 0) is obtained. This is represented by a path through the factorization graph ∇126 connecting (1, 0, 6) to (0, 14, 0)
that passes through 9 vertices, including (21, 0, 0).

4

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

Before stating and proving Theorem 3.4 and Corollary 3.5, we prove Lemma 3.3,
which identifies the locations in the proof of Theorem 3.4 that require n to be sufficiently
large. Note that Theorem 3.4 is the source of the bound given in nearly every “eventual
behavior” result in this paper; see Remark 4.10 for more detail.
Lemma 3.3. Fix a ∈ S and s = (s1 , . . . , sk ) ∈ Z(a).
(a) If |s| ≥ rk and sk = 0, then there is a shorter factorization s0 ∈ Z(a) with s0k > 0.
(b) If a > rk−1 rk and s has minimum factorization length, then sk > 0.
(c) If a > rk2 , then |s| ≥ rk .
Proof. [1, Lemma 4.1] and Theorem 2.4.



Theorem 3.4. Suppose n > rk2 , and let z and z 0 be factorizations of a Betti element
β ∈ Mn in different connected components of ∇β . If |z| > |z 0 |, then z0 > 0 and zk0 > 0.
Proof. We begin by observing that
β − |z|n = z0 n +

k
X

zi (n + ri ) − |z|n =

i=1

k
X

zi ri ,

i=1

which yields an explicit bijection between the factorizations of β ∈ Mn of length ` and
the factorizations of β − `n ∈ S of length at most `. Let s = (z1 , . . . , zk ) ∈ ZS (β − |z|n)
and s0 = (z10 , . . . , zk0 ) ∈ ZS (β − |z 0 |n) denote the factorizations in S corresponding to z
and z 0 , respectively. Notice that since |z| > |z 0 |, we have
β − |z 0 |n ≥ n + β − |z|n ≥ n > rk2 ,
so |s0 | ≥ rk by Lemma 3.3(c).
Next, we claim some factorization in the same connected component of ∇β as z 0 has
positive last component. Certainly if zk0 > 0 the claim is proved. Otherwise, since
β − |z 0 |n ≥ rk−1 rk , applying Lemma 3.3(b) produces a factorization s00 ∈ ZS (β − |z 0 |n)
with s00k > 0 obtained from s0 by replacing all but one atom with a minimum length
factorization. The corresponding factorization z 00 = (|z 0 | − |s00 |, s001 , . . . , s00k ) ∈ Z(β) of β
under the above bijection is connected to z 0 in ∇β and has z000 > 0 and zk00 > 0.
Now, since z and z 0 lie in different connected components of ∇β , the above claim
implies zk = 0. This means |s| ≤ rk , since otherwise Lemma 3.3(a) would produce a
factorization connected to z in ∇β with positive last coordinate. As such,
|z| > |z 0 | ≥ |s0 | ≥ rk ≥ |s|,
which yields z0 = |z|−|s| > 0. Lastly, we conclude zk0 > 0, as otherwise the factorization
z 00 constructed above would be connected to both z and z 0 in ∇β since it has positive
first coordinate.

Corollary 3.5. Suppose n > rk2 and that Mn is primitive, and let d = gcd(r1 , . . . , rk ).
Any two factorizations z, z 0 ∈ Z(β) of a Betti element β ∈ Betti(Mn ) lying in different
connected components of ∇β satisfy |z| − |z 0 | ∈ {0, d}.

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

5

Proof. By [2, Proposition 2.9], |z| − |z 0 | ∈ dZ, so suppose by way of contradiction that
|z| − |z 0 | ≥ 2d. Since β − |z 0 |n − n ∈ S, there exists a factorization z 00 ∈ Z(β) with
|z 00 | = |z 0 | + d. By Theorem 3.4, both z000 and zk00 must be positive, meaning z and z 0
are both connected to z 00 in ∇β .

4. Minimal presentations
Let πn : Nk+1 → Mn denote the factorization homomorphism of Mn , that is,
πn (z) = z0 n +

k
X

zi (n + ri ),

i=1

and let ker πn denote the equivalence relation on Nk+1 given by (z, z 0 ) ∈ ker πn whenever
πn (z) = πn (z 0 ), (that is, when z and z 0 are factorizations for the same element in Mn ).
The equivalence relation ker πn is a congruence since it is also closed under translation,
that is, (z + u, z 0 + u) ∈ ker πn whenever (z, z 0 ) ∈ ker πn and u ∈ Nk+1 .
Definition 4.1. Fix a numerical monoid M = hm1 , . . . , mt i and let π : Nt → M denote
the factorization homomorphism of M . A presentation for M is a set of relations
ρ ⊂ ker π such that ker π is the unique minimal (w.r.t. containment) congruence on Nt
containing ρ. Equivalently, this is true if between any two factorizations (z, z 0 ) ∈ ker π,
there exists a chain a0 , a1 , . . . , ar with a0 = z, ar = z 0 , and
(ai−1 , ai ) = (bi , b0i ) + (ui , ui ) ∈ ker π
for some (bi , b0i ) ∈ ρ and ui ∈ Nt for each i ≤ r. We say ρ is minimal if it is minimal
with respect to containment among all presentations of M .
Minimal presentations are one of the fundamental tools with which to study the
factorization structure of finitely generated monoids. Each minimal presentation of a
monoid M can be viewed as a particular choice of minimal relations that are sufficient for relating any two factorizations of the elements of M . For a more thorough
introduction, we refer the reader to [13, Chapter 9] and [14, Chapter 7].
Example 4.2. The minimal presentations of M = h6, 9, 20i from Example 3.2 are
{((3, 0, 0), (0, 2, 0)), ((10, 0, 0), (0, 0, 3))}, {((3, 0, 0), (0, 2, 0)), ((7, 2, 0), (0, 0, 3))},
{((3, 0, 0), (0, 2, 0)), (( 4, 4, 0), (0, 0, 3))}, {((3, 0, 0), (0, 2, 0)), ((1, 6, 0), (0, 0, 3))},
each of which has exactly one relation for each Betti element. As per the discussion in
Example 3.2, each minimal presentation provides enough relations among the minimal
generators of M to relate any two factorizations of elements of M .

6

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

Example 4.3. Let S = h6, 9, 20i, and consider the following minimal presentations.
M450 : (( 0, 0, 8, 0), (3, 2, 0, 3)), (( 0, 1, 6, 0), (4, 0, 0, 3)), (( 0, 3, 0, 0), (1, 0, 2, 0)),
((20, 5, 0, 0), (0, 0, 0, 24)), ((25, 1, 0, 0), (0, 0, 4, 21)), ((26, 0, 0, 0), (0, 2, 2, 21))
M470 : (( 0, 0, 8, 0), (3, 2, 0, 3)), (( 0, 1, 6, 0), (4, 0, 0, 3)), (( 0, 3, 0, 0), (1, 0, 2, 0)),
((21, 5, 0, 0), (0, 0, 0, 25)), ((26, 1, 0, 0), (0, 0, 4, 22)), ((27, 0, 0, 0), (0, 2, 2, 22))
M490 : (( 0, 0, 8, 0), (3, 2, 0, 3)), (( 0, 1, 6, 0), (4, 0, 0, 3)), (( 0, 3, 0, 0), (1, 0, 2, 0)),
((22, 5, 0, 0), (0, 0, 0, 26)), ((27, 1, 0, 0), (0, 0, 4, 23)), ((28, 0, 0, 0), (0, 2, 2, 23))

Each first-row relation (z, z 0 ) satisfies |z| = |z 0 |, and each second-row relation (z, z 0 )
satisfies |z| = |z 0 | + 1, z0 > 0 and z30 > 0. Theorem 3.4 ensures that every relation
above satisfies one of these two criteria.
Theorem 4.9 characterizes the relationship between successive minimal presentations. In particular, the same equal-length relations appear in all three given minimal
presentations, and each remaining relation for Mn+20 is obtained from a relation for
Mn by adding (e0 , ek ).
Proposition 4.4 defines the map Φn used to construct the bijection between minimal
presentations in Theorem 4.9, and Proposition 4.6 gives several key properties of Φn .
In particular, it is shown that Φn preserves symmetric and translation closure, and
preserves monotone chain connectivity (Definition 4.5).
Proposition 4.4. The map Φn : ker πn → ker πn+rk

 (z + `e0 , z 0 + `ek )
0
(z + `ek , z 0 + `e0 )
Φn (z, z ) =

(z, z 0 )

given by
if
if
if

|z| > |z 0 |
|z| < |z 0 |
|z| = |z 0 |

for (z, z 0 ) ∈ ker πn and ` = |z| − |z 0 | is well defined.
Proof. Fix (z, z 0 ) ∈ ker πn with z = (z0 , . . . , zk ) and z 0 = (z00 , . . . , zk0 ). By symmetry, we
can assume that ` = |z| − |z 0 | ≥ 0. Now, we simply use πn (z) = πn (z 0 ) to verify that
πn+rk (z + de0 ) = (|z| + `)(n + rk ) +

k
X

zi ri = (|z 0 | + 2`)(n + rk ) − `n +

i=1

= (|z 0 | + `)(n + rk ) + `rk +

k
X

zi0 ri

i=1
k
X

zi0 ri = πn+rk (z 0 + `ek ),

i=1

as desired.



Definition 4.5. A chain z = a0 , a1 , . . . , ar = z 0 between factorizations z, z 0 in a numerical monoid is monotone if |a0 |, |a1 |, . . . , |ar | is a monotone sequence.
Proposition 4.6. Fix n, ρ ⊂ ker πn , and (z, z 0 ) ∈ ρ, and let (w, w0 ) = Φn (z, z 0 ).
(a) The map Φn is injective.
(b) The map Φn preserves length differences: |z| − |z 0 | = |w| − |w0 |.

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

7

(c) The map Φn preserves the reflexive, symmetric, and translation closure operations:
if ρ is reflexive, symmetric, or closed under translation, then so is Φn (ρ).
(d) The map Φn preserves monotone chain connectivity: if ρ is translation-closed and
there exists a monotone ρ-chain from z to z 0 , then there exists a monotone Φn (ρ)chain from w to w0 .
Proof. It is easy to check that |z| − |z 0 | = |w| − |w0 |, from which injectivity follows.
Both Φ(z, z) = (z, z) and Φ(z 0 , z) = (w0 , w) follow directly from definitions as well.
Next, fixing u ∈ Nk+1 and assuming by symmetry that ` = |z| − |z 0 | ≥ 0, we have
Φn (z+u, z 0 +u) = (z+u+`e0 , z 0 +u+`ek ) = (z+`e0 , z 0 +`ek )+(u, u) = Φn (z, z 0 )+Φn (u, u).
It remains to prove the final claim.
Suppose ρ is translation-closed and there is a monotone decreasing ρ-chain from z
to z 0 . By induction on chain length, we can assume there is a single intermediate
factorization z 00 . Letting ` = |z| − |z 00 | ≥ 0 and `0 = |z 00 | − |z 0 | ≥ 0, we have
Φn (z + `0 e0 , z 00 + `0 e0 ) = (z + (` + `0 )e0 , z 00 + `0 e0 + `ek )
and
Φn (z 00 + `ek , z 0 + `ek ) = (z 00 + `ek + `0 e0 , z 0 + (` + `0 )ek )
which form a monotone decreasing Φn (ρ)-chain from w to w0 .



The main obstruction to Theorem 4.9 for arbitrary n is that Φn needs only preserve connectivity by monotone chains. Proposition 4.8 ensures that for n sufficiently
large, any pair of factorizations (z, z 0 ) ∈ ker πn is connected by a monotone chain, and
Example 4.7 demonstrates why this can fail for small n.
Example 4.7. Let S = h3, 14i. The element 1078 ∈ M74 has factorization set
ZM74 (1078) = {(0, 14, 0), (11, 0, 3), (0, 6, 7)}.
Notice that the only chains between (0, 14, 0) and (11, 0, 3) are a monotone chain directly between them and a non-monotone chain through (0, 6, 7). Since both relations
in the non-monotone chain are translations, no minimal presentation of M74 contains
the relation ((0, 14, 0), (11, 0, 3)). On the other hand, we have
ZM88 (1274) = {(0, 14, 0), (11, 0, 3)},
so every minimal presentation of M88 contains the relation ((0, 14, 0), (11, 0, 3)).
Proposition 4.8. Fix n > rk2 and a minimal presentation ρ ⊆ ker πn . There exists a
monotone ρ-chain between any (z, z 0 ) ∈ ker πn .
Proof. Without loss of generality, assume gcd(z, z 0 ) = 0. By way of contradiction,
assume there is no monotone ρ-chain from z to z 0 . Since Cong(ρ) = ker πn , there exists
a chain z = a0 , a1 , . . . , ar = z 0 of factorizations such that for each i < r, we have
(ai , ai+1 ) = (bi , b0i ) + (ui , ui ),

(bi , b0i ) ∈ ρ, ui ∈ Nk+1 ,

8

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

where bi and b0i occur in distinct connected components of the graph ∇β of β = πn (bi ).
By Corollary 3.5, we have |ai | − |ai−1 | ∈ {−1, 0, 1} for each i ≤ r. As such, the
sequence |a0 |, |a1 |, . . . , |ar | of factorization lengths has non-sequential repeated values.
Without loss of generality, we can replace z 0 with the factorization whose length is
the first non-sequential repeated value in this sequence, and replace z with the last
factorization before z 0 with |z| = |z 0 |. As such, |a0 | = |ar | = |a1 | = |ar−1 |, and
|ai | = |ai−1 | whenever 1 < i < r.
First, suppose |a1 | = |a0 | + 1. Applying Theorem 3.4 to the pairs (b1 , b01 ) and (br , b0r ),
we see that zk > 0 and zk0 > 0, which contradict the assumption that gcd(z, z 0 ) = 0.
Likewise, if |a1 | = |a0 | − 1, then Theorem 3.4 implies that z0 > 0 and z00 > 0, which
again contradict the assumption that gcd(z, z 0 ) = 0. This completes the proof.

Together, Propositions 4.6 and 4.8 yield Theorem 4.9, the main result of this section.
Theorem 4.9. For any n > rk2 , the image of any minimal presentation ρ of Mn under
the map Φn : ker πn → ker πn+rk is a minimal presentation of Mn+rk . In particular,
Φn induces a one-to-one correspondence between the minimal presentations of Mn and
the minimal presentations of Mn+rk .
Proof. We begin by showing that any minimal presentation ρ ⊂ ker πn of Mn satisfies
Cong(Φn (ρ)) = ker πn+rk ,
that is, the image of ρ under Φn is a presentation for Mn+rk . Fix (w, w0 ) ∈ ker πn+rk ,
and let m = πn+rk (w). By Proposition 4.8, there exists a monotone chain from w to
w0 , which we can assume is monotone decreasing by Proposition 4.6(c). We can also
assume each step in this chain has the form (b, b0 ) + (u, u) for some u ∈ Nk+1 and
b, b0 ∈ Z(β) lying in different connected components of ∇β . By Proposition 4.6(c), it
suffices to prove each (b, b0 ) lies in the image of Φn , so it is enough to assume w and w0
lie in different connected components of ∇m .
First, if |w| = |w0 |, then Φn (w, w0 ) = (w, w0 ) by Proposition 4.4. Otherwise, Corollary 3.5 implies |w| = |w0 | + d, where d = gcd(r1 , . . . , rk ), and w0 , wk0 ≥ d follows from
the proof of Theorem 3.4. This means Φn (w − de0 , w0 − dek ) = (w, w0 ), which proves
Φn (ρ) generates ker πn+rk .
Now, by Propositions 4.6(d) and 4.8, factorizations z, z 0 ∈ ZMn (β) lie in distinct
connected components of ∇β if and only if (w, w0 ) = Φn (z, z 0 ) lie in different connected
components of the factorization graph of πn+rk (w), so the image Φn (ρ) is indeed minimal as a presentation of Mn+rk . Additionally, the above argument implies that any
minimal presentation ρ0 of Mn+rk is contained in the image of Φn , so its preimage
0
Φ−1

n (ρ ) is a minimal presentation for Mn . This completes the proof.
Remark 4.10. Resuming notation from Theorem 4.9, the bound n > rk2 first appears
in Theorem 3.4, and this is the only result explicitly using the bound. In particular,
each subsequent result requiring n > rk2 (including Corollary 3.5, Proposition 4.8,

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

9

Theorem 4.9, Corollary 4.12, and several results in Section 5) only uses this bound to
(possibly indirectly) apply Theorem 3.4. As such, any improvement on the bound in
Theorem 3.4 immediately improves Theorem 4.9.
Example 4.11. For fixed S and n sufficiently large, the size of a minimal presentation
for Mn need not be fixed within a given rk -period. For example, if S = h6, 9, 20i, the
size of a minimal presentation of Mn ranges from 4 (for n = 420) to 8 (for n = 417).
We conclude the section with Corollary 4.12, which uses Proposition 4.8 to characterize the minimal relations for Mn whose factorizations have equal length.
Corollary 4.12. Fix n > rk2 and a minimal presentation ρ ⊂ ker πn for Mn . Then
τ = {((z1 , . . . , zk ), (z10 , . . . , zk0 )) : (z, z 0 ) ∈ ρ and |z| = |z 0 |} ⊂ Nk × Nk
is a presentation for S.
Proof. Fix s, s0 ∈ ZS (s) with |s| ≤ |s0 |. Let π : Nk → S denote the factorization
homomorphism of S, and let z = (|s0 | − |s|, s1 , . . . , sk ) and z 0 = (0, s01 , . . . , s0k ). Then
(z, z 0 ) ∈ ker πn , so by Proposition 4.8 there exists a monotone ρ-chain from z to z 0 , but
since |z| = |z 0 |, each factorization a in the chain must have length |z| as well. As such,
πn (a) = |z|n +

k
X

ai ri = |z|n + π(a1 , . . . , ak )

i=1

for each a in the chain, thus producing a τ -chain from s to s0 .



Example 4.13. Resuming notation from Corollary 4.12, the presentation τ for S need
not be minimal. Indeed, if S = h6, 9, 20i, then the minimal presentation ρ of M450
given in Example 4.3 contains three equal-length relations, yielding the presentation
τ = {((0, 8, 0), (2, 0, 3)), ((1, 6, 0), (0, 0, 3)), ((3, 0, 0), (0, 2, 0))}
for S. The first of the above relations is redundant, as the latter two form a minimal
presentation τ 0 for S. However, the only τ 0 -chain between (0, 8, 0) and (2, 0, 3) is nonmonotone, which is why ρ must also contain the relation ((0, 0, 8, 0), (3, 2, 0, 3)).
5. Applications to factorization invariants
In this section, we explore several consequences of the results in Sections 3 and 4. We
begin with Remark 5.1, which discusses computational applications of Theorem 4.9,
and Corollary 5.2, which improves a recent result from commutative algebra (see Remark 5.3 for more on this connection). Next, we characterize the behavior of several
arithmetical invariants of non-unique factorization over Mn for large n. The survey
article [12] gives an overview of several of the invariants discussed here.

10

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

n
50
200
400
1000
5000
10000

Mn
h50, 56, 59, 70i
h200, 206, 209, 220i
h400, 406, 409, 420i
h1000, 1006, 1009, 1020i
h5000, 5006, 5009, 5020i
h10000, 10006, 10009, 10020i

GAP Runtime [8] Remark 5.1
1 ms
1 ms
40 ms
40 ms
210 ms
210 ms
3 sec
210 ms
18 min
210 ms
4.2 hr
210 ms

Table 1. Runtime comparison for computing a minimal presentation for
numerical monoids Mn with S = h6, 9, 20i. All computations performed
using GAP and the package numericalsgps [8].

Remark 5.1. Minimal presentations are used frequently in computer software package
implementations, since many quantities of interest can then be quickly computed [10].
Additionally, minimal presentations have particular significance in commutative algebra; see Remark 5.3. Most existing algorithms to compute a minimal presentation of a
given numerical monoid use Gröbner basis techniques, which become computationally
infeasible as the number and size of the generators grow large [7].
Theorem 4.9 yields a method of reducing this complexity in certain cases. In particular, if the generators of M = hn1 , . . . , nk i satisfy n1 > (nk − n1 )2 , then a minimal
presentation for M can be computed by first computing a minimal presentation for
M 0 = hn1 − R, . . . , nk − Ri, where R is some appropriately chosen multiple of nk − n1 ,
and then successively applying the map Φ∗ from Proposition 4.4 until a minimal presentation for M is obtained. In cases where the generators of M 0 are significantly smaller
than those of M , the resulting computation is much faster than directly computing a
minimal presentation for M .
Table 1 gives a sample of the improved runtimes that result from using Theorem 4.9.
All runtimes were obtained in the computer algebra system GAP and the numericalsgps
package, a standard setting for numerical semigroup computations. An improved implementation of the function MinimalPresentationOfNumericalSemigroup that utilizes
Theorem 4.9 is currently in development, and will be available with the next major
release of the numericalsgps package.
As a corollary of Theorem 4.9, we obtain an improved bound for a result conjectured
by Herzog and Srinivasan and later proved by Vu in [15].
Corollary 5.2. The function n 7→ | Betti(Mn )| is rk -periodic for n > rk2 .
Proof. Given any minimal presentation ρ for Mn , the set Betti(Mn ) consists of precisely
the elements with factorizations appearing in ρ. Now, Theorem 3.4 and Corollary 3.5
imply that each relation in ρ involving factorizations of different lengths produces a
distinct Betti element, since the corresponding Betti element β must have exactly two

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

11

connected components in ∇β . Thus, Proposition 4.4 implies Φn induces a well-defined
map Betti(Mn ) → Betti(Mn+rk ), and Theorem 4.9 ensures this map is a bijection. 
Remark 5.3. The elements of a minimal presentation of a numerical monoid M correspond to binomial generators of the defining toric ideal I of M . In fact, each minimal
presentation corresponds to a minimal binomial generating set for I. It is in this setting
that Vu approached Corollary 5.2 in [15], where the Betti elements of M correspond
to Betti numbers of I in homological degree 1.
Remark 5.4. Corollary 5.2, as well as some results in Sections 3 and 4, appears in [15]
using the language of Remark 5.3. However, our approach has several advantages.
(a) Our approach is purely combinatorial; shedding the dependence on commutative
algebra makes the results available to a broader mathematical audience, and better
isolates the core structural changes (i.e. the existence of monotone chains and
Theorem 3.4) that occur once n is large enough.
(b) Our bound n > rk2 is lower than each of those previously given, which is crucial for
effective use in computation in Remark 5.1. Additionally, great care was taken to
ease future improvements on our bound, as discussed in Remark 4.10.
(c) Several results in this section, such as Corollary 5.9, do not follow as directly from
statements in [15] as they do from Theorem 4.9. Indeed, much of the theory developed in Section 4 would have been necessary for a specialized proof of Corollary 5.9,
and such specialization would have obscured the underlying connection to the other
consequences of Theorem 4.9 presented here.
Remark 5.5. As a consequence of Theorem 4.9 and Corollary 4.12, the elements of
Betti(Mn ) fall into two distinct categories: those with minimal relations of equal length,
and those with minimal relations of different length. Upon successive applications of
Φn , those Betti elements in the former category increase linearly with n (with slope
given by factorization length, preserved under Φn ), and those Betti elements in the
latter category increase quadratically with n. The plot in Figure 1 exhibits a graphical
representation, which makes the distinction more explicit.
Theorem 4.9 can also be applied to characterize arithmetic invariants of non-unique
factorization for sufficiently large n. We begin with the delta set invariant.
Definition 5.6. Fix a numerical monoid M ⊂ N, and fix a ∈ M . Writing
L(a) = {`1 < · · · < `r }
for the set of distinct factorization lengths of a, the delta set of a is the set
∆(a) = {`i − `i−1 : 2 ≤ i ≤ r}
of successive differences
of factorization lengths of a. Lastly, the delta set of M is the
S
union ∆(M ) = a∈M ∆(a) of the delta sets of its elements.

12

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

4000
3000
2000
1000
0

50

100

150

200

250

Figure 1. A plot depicting the Betti elements of Mn for S = h6, 9, 20i
and n ≤ 250. Each point (n, b) indicates b ∈ Betti(Mn ).
As a consequence of Corollary 3.5, we obtain Corollary 5.7, which offers an improved
bound over [6, Theorem 2.2].
Corollary 5.7 ([6, Theorem 2.2]). If n > rk2 , then
∆(Mn ) = {d},
where d = gcd(r1 , . . . , rk ).
Proof. An elementary number theory argument implies d = min ∆(Mn ). Additionally,
max ∆(Mn ) occurs in the delta set of a Betti element of Mn by [4, Theorem 2.5], so
max ∆(Mn ) = d by Corollary 3.5.

Next, we examine the family of catenary degree invariants. An introduction to the
catenary degree is provided in [12, Section 5], and an extensive overview of numerous
catenary degree variations can be found in [11].
Definition 5.8. Fix a numerical monoid M = hm1 , . . . , mt i and an element a ∈ M .
For z, z 0 ∈ Z(a), the greatest common divisor of z and z 0 is given by
gcd(z, z 0 ) = (min(z1 , z10 ), . . . , min(zt , zt0 )) ∈ Nt ,
and the distance between z and z 0 is given by
d(z, z 0 ) = max(|z − gcd(z, z 0 )|, |z 0 − gcd(z, z 0 )|).
For z, z 0 ∈ Z(a) and N ≥ 1, an N -chain from z to z 0 is a sequence w0 , . . . , wr ∈ Z(a)
of factorizations of a such that w0 = z, wr = z 0 , and d(wi−1 , wi ) ≤ N for all i ≤ r.
(a) The catenary degree of a, denoted c(a), is the smallest N ∈ N such that there exists
an N -chain between any two factorizations of a.
(b) The monotone catenary degree of a, denoted cmon (a), is the smallest N ∈ N such
that there exists a monotone N -chain (i.e. an N -chain whose factorization lengths
form a monotone sequence) between any two factorizations of a.

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

13

15

10

5

0

50

100

150

200

250

Figure 2. A plot depicting c(Mn ) for S = h6, 9, 20i and n ≤ 250.
(c) The equal catenary degree of a, denoted ceq (a), is the smallest N ∈ N such that
there exists an equal N -chain (i.e. an N -chain whose factorization lengths are all
identical) between any two equal-length factorizations of a.
For each invariant above, define c∗ (M ) = supa∈M c∗ (a).
Corollary 5.9. The function n 7→ c(Mn ) is eventually quasilinear. In particular,
if n > rk2 and Mn is primitive, then
c(Mn+rk ) = c(Mn ) + d
for d = gcd(r1 , . . . , rk ).
Proof. Let ρ1 , . . . , ρm denote all minimal presentations of Mn , and let
µi = max{|z|, |z 0 | : (z, z 0 ) ∈ ρi }.
By [5, Theorem 4], the catenary degree of Mn equals
c(Mn ) = min{µi : 1 ≤ i ≤ m}.
By Theorem 4.9, each ρi satisfies µ(Φn (ρi )) = µ(ρi ) + d, which implies the claim.



Corollary 5.10. For n > rk2 , we have cmon (Mn ) = ceq (Mn ) = c(Mn ). In particular,
cmon (Mn ) and ceq (Mn ) are both eventually quasilinear with period rk as functions of n.
Proof. Definition 5.8 implies c(Mn ) ≤ ceq (Mn ) ≤ cmon (Mn ) for each n, so it suffices to
prove cmon (Mn ) = c(Mn ). Now apply Proposition 4.8 and Corollary 5.9.

Remark 5.11. Included in Figure 2 is a graphical representation of the quasilinear
behavior described in Corollaries 5.9 and 5.10.
We conclude with Example 5.13 demonstrating why a characterization of the eventual behavior of the tame degree (Definition 5.12) does not follow directly from Theorem 4.9. As such, a solution to Problem 5.14 will likely require a characterization of
the primitive elements of Mn for sufficiently large n; see [3].

14

CONWAY, GOTTI, HORTON, O’NEILL, PELAYO, WILLIAMS, AND WISSMAN

Definition 5.12. Resume notation from Definition 5.8. The tame degree of a ∈ M ,
denoted t(a), is the smallest N ∈ N such that for each z ∈ Z(a) and each i ≤ t with
a − mi ∈ M , there exists z 0 ∈ Z(a) such that zi0 > 0 and d(z, z 0 ) ≤ N .
Example 5.13. Unlike the catenary degree, the tame degree of a numerical monoid
need not be achieved at a Betti element, even for n > rk2 . As such, Theorem 4.9 does
not allow us to immediately characterize the eventual behavior of the tame degree.
Indeed, for S = h6, 9, 20i and n = 401, we have c(Mn ) = 23 and t(10869) = 27.
In contrast, the monotone and equal catenary degrees also need not occur at a Betti
element in general (see [11]), but Corollary 5.10 ensures they do for n > rk2 .
Problem 5.14. Characterize the tame degree of Mn for n sufficiently large.
6. Acknowledgements
Much of this work was completed during the Pacific Undergraduate Research Experience in Mathematics (PURE Math), funded by National Science Foundation grants
DMS-1035147 and DMS-1045082 and a supplementary grant from the National Security Agency. The authors would like to thank Scott Chapman for giving the initial
motivation to start this work and for his helpful comments.
References
[1] T. Barron, C. O’Neill, and R. Pelayo, On the set of elasticities in numerical monoids, to appear,
Semigroup Forum. Available at arXiv: math.CO/1409.3425.
[2] C. Bowles, S. Chapman, N. Kaplan, D. Reiser, On delta sets of numerical monoids, J. Algebra
Appl. 5 (2006) 1–24.
[3] S. Chapman, P. Garcı́a-Sánchez, and D. Llena, The catenary and tame degree of numerical
semigroups, Forum Math. 21 (2009) 117-129.
[4] S. Chapman, P. Garcı́a-Sánchez, D. Llena, A. Malyshev, and D. Steinberg, On the Delta set and
the Betti elements of a BF-monoid, Arab J. Math 1 (2012), 53–61.
[5] S. Chapman, P. Garcı́a-Sánchez, D. Llena, V. Ponomarenko, J. Rosales, The catenary and tame
degree in finitely generated commutative cancellative monoids, Manuscripta Math. 120 (2006), no.
3, 253–264.
[6] S. Chapman, N. Kaplan, T. Lemburg, A. Niles, and C. Zlogar, Shifts of generators and delta sets
of numerical monoids, Internat. J. Algebra Comput. 24 (2014), no. 5, 655–669.
[7] D. Cox, J. Little, and D. O’Shea, Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra, 4th edition, Undergraduate Texts in
Mathematics, Springer, Cham, 2015.
[8] M. Delgado, P. Garcı́a-Sánchez, J. Morais, NumericalSgps, A package for numerical semigroups, Version 0.980 dev (2013), (GAP package), http://www.fc.up.pt/cmup/mdelgado/
numericalsgps/.
[9] P. Diaconis and B. Sturmfels, Algebraic algorithms for sampling from conditional distributions,
Ann. Statist. 26 (1998), no. 1, 363–397.
[10] P. Garcı́a-Sánchez, An overview of the computational aspects of nonunique factorization invariants, preprint. Available at arXiv: /1504.07424

MINIMAL PRESENTATIONS OF SHIFTED NUMERICAL MONOIDS

15

[11] P. Garcı́a-Sánchez, I. Ojeda, R. Sánchez, and A. Navarro, Factorization invariants in half-factorial
affine semigroups, Internat. J. Algebra Comput. 23 (2013), no. 1, 111–122.
[12] C. O’Neill and R. Pelayo, Factorization invariants in numerical monoids, to appear, Contemp.
Math. Available at arXiv: /1508.00128.
[13] J.C. Rosales and P.A. Garcı́a-Sánchez, Finitely generated commutative monoids, Nova Science
Publishers, Inc., Commack, NY, 1999. xiv+185 pp. ISBN: 1-56072-670-9.
[14] J. Rosales and P. Garcı́a-Sánchez, Numerical semigroups, Developments in Mathematics, Vol. 20,
Springer-Verlag, New York, 2009.
[15] T. Vu, Periodicity of Betti numbers of monomial curves, Journal of Algebra 418 (2014) 66–90.
Monmouth University, West Long Branch, NJ 07764
E-mail address: s0969183@monmouth.edu
Mathematics Department, UC Berkeley, Berkeley, CA 94720
E-mail address: felixgotti@berkeley.edu
University of Arkansas, Fayetteville, AR 72701
E-mail address: jphorton@uark.edu
Mathematics Department, Texas A&M University, College Station, TX 77843
E-mail address: coneill@math.tamu.edu
Mathematics Department, University of Hawai‘i at Hilo, Hilo, HI 96720
E-mail address: robertop@hawaii.edu
Lee University, Cleveland, TN 37311
E-mail address: mprach00@leeu.edu
Mathematics Department, University of Hawai‘i at Hilo, Hilo, HI 96720
E-mail address: wissman@hawaii.edu

