arXiv:1708.09527v1 [] 31 Aug 2017

APÉRY SETS OF SHIFTED NUMERICAL MONOIDS
CHRISTOPHER O’NEILL AND ROBERTO PELAYO
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 characterize the Apéry
set of Mn in terms of the Apéry set of the base monoid S when n is sufficiently large.
We give a highly efficient algorithm for computing the Apéry set of Mn in this case,
and prove that several numerical monoid invariants, such as the genus and Frobenius
number, are eventually quasipolynomial as a function of n.

1. Introduction
The factorization theory of numerical monoids – co-finite, additive submonoids of the
non-negative integers – has enjoyed much recent attention; in particular, invariants such
as the minimum factorization length, delta set, and ω-primality have been studied in
much detail [8]. These measures of non-unique factorization for individual elements in
a numerical monoid all exhibit a common feature: eventual quasipolynomial behavior.
In many cases, this eventual behavior is periodic (i.e. quasiconstant) or quasilinear,
and this pattern always holds after some initial “noise” for small monoid elements.
In this paper, we describe quasipolynomial behavior of certain numerical monoid
invariants over parameterized monoid families. Unlike previous papers, which studied
how factorization invariants change element-by-element (e.g., minimum factorization
length [1]), we investigate how a monoid’s properties change as the generators vary by
a shift parameter. More specifically, we study “shifted” numerical monoids of the form
Mn = hn, n + r1 , . . . , n + rk i
for r1 < · · · < rk , and find explicit relationships between the Frobenius number, genus,
type, and other properties of Mn and Mn+rk when n > rk2 . As with the previous
element-wise investigations of invariant values, our monoid-wise analysis reveals eventual quasipolynomial behavior, this time with respect to the shift parameter n.
The main result of this paper is Theorem 3.3, which characterizes the Apéry set of Mn
(Definition 2.2) for large n in terms of the Apéry set of the monoid S = hr1 , . . . , rk i
at the base of the shifted family. Apéry sets are non-minimal generating sets that
concisely encapsulate much of the underlying monoid structure, and many properties
of interest can be recovered directly and efficiently from the Apéry set, making it a
Date: September 1, 2017.
1

2

CHRISTOPHER O’NEILL AND ROBERTO PELAYO

sort of “one stop shop” for computation. We utilize these connections in Section 4 to
derive relationships between properties of Mn and Mn+rk when n is sufficiently large.
One of the main consequences of our results pertains to computation. Under our
definition of Mn above, every numerical monoid is a member of some shifted family of
numerical monoids. While Apéry sets of numerical monoids (and many of the properties derived from them) are generally more difficult to compute when the minimal
generators are large, our results give a way to more efficiently perform these computations by instead computing them for the numerical monoid S, which has both smaller
and fewer generators than Mn . In fact, one surprising artifact of the algorithm described in Remark 3.5 is that, in a shifted family {Mn } of numerical monoids, the
computation of the Apéry set of Mn for n > rk2 is typically significantly faster than for
Mn with n ≤ rk2 , even though the former has larger generators. We discuss this and
futher computational consequences in Remark 4.11, including implementation of our
algorithm in the popular GAP package numericalsgps [5].
2. Background
In this section, we recall several definitions and results used in this paper. For more
background on numerical monoids, we direct the reader to [9].
Definition 2.1. A numerical monoid M is an additive submonoid of Z≥0 . When
we write M = hn1 , . . . , nk i, we assume n1 < · · · < nk . We say M is primitive if
gcd(n1 , . . . , nk ) = 1. A factorization of an element a ∈ M is an expression
a = z1 n1 + · · · + zk nk
of a as a sum of generators of M, which we often represent with the integer tuple
~z = (z1 , . . . , zk ) ∈ Zk≥0 . The length of a factorization ~z of a is the number
|~z | = z1 + · · · + zk
of generators appearing in z. The set of factorizations of a is denoted ZM (a) ⊂ Zk≥0 ,
and the set of factorization lengths is denoted LM (a) ⊂ Z≥0 .
Definition 2.2. Let M be a numerical monoid. Define the Apéry set of x ∈ M as
Ap(M, x) = {m ∈ M : m − x ∈ Z \ M}
and the Apéry set of M as Ap(M) = Ap(M; n1 ), where n1 is the smallest nonzero
element of M. Note that under this definition, |Ap(M; x)| = x/ gcd(M).
Theorem 2.3 appeared in [1] for primitive, minimally generated numerical monoids,
and in [3] for general numerical monoids. We state the latter version here.
Theorem 2.3 ([1, 3]). Suppose M = hn1 , . . . , nk i is a numerical monoid. The function
m : M → Z≥0 sending each a ∈ M to its shortest factorization length satisfies
m(a + nk ) = m(a) + 1
for all a > nk−1 nk .

APÉRY SETS OF SHIFTED NUMERICAL MONOIDS

3

Notation. Through the remainder of this paper, r1 < · · · < rk and n are non-negative
integers, g = gcd(r1 , . . . , rk ), and
S = hr1 , . . . , rk i

and

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

denote additive submonoids of Z≥0 . Unless otherwise stated, we assume n > rk and
gcd(n, g) = 1 so Mn is primitive and minimally generated as written, but we do not
make any such assumptions on S. Note that choosing n as the first generator of Mn
ensures that every numerical monoid falls into exactly one shifted family.
3. Apéry sets of shifted numerical monoids
The main results in this section are Theorem 3.3, which expresses Ap(Mn ) in terms
of Ap(S; n) for n sufficiently large, and Proposition 3.4, which characterizes Ap(S; n)
for large n in terms of Z≥0 \ S. In addition to the numerous consequences in Section 4,
these two results yield an algorithm to compute Ap(Mn ) for large n; see Remark 3.5.
Lemma 3.1 ([3, Theorem 3.4]). Suppose n > rk2 . If ~a and ~b are factorizations of an
element m ∈ Mn with |~a| < |~b|, then b0 > 0.
Remark 3.2. Lemma 3.1 was also proven in [12] and subsequently improved in [7],
both with strictly higher bounds on the starting value of n. The latter source proved
that such numerical monoids are homogeneous, meaning every element of the Apéry
set has a unique factorization length. This property appears as part of Theorem 3.3
along with a characterization of the unique length in terms of S.
Theorem 3.3. If n ∈ S satisfies n > rk2 , then
Ap(Mn ; n) = {i + mS (i) · n | i ∈ Ap(S; gn)}
where g = gcd(S) and mS denotes min factorization length in S. Moreover, we have
LMn (i + mS (i) · n) = {mS (i)}
for each i ∈ Ap(S; gn).
Proof. Let A = {i + mS (i) · n | i ∈ Ap(S; gn)}. Each element of Ap(S; gn) is distinct
modulo n, since each element of {i/g | i ∈ Ap(S; gn)} is distinct modulo n and
gcd(n, g) = 1. As such, each element of A is distinct modulo n, since
i + mS (i) · n ≡ i mod n
for i ∈ Ap(S; gn). This implies |A| = n, so it suffices to show A ⊆ Ap(Mn ; n).
Fix i ∈ Ap(S; gn), and let a = i + mS (i) · n. If ~s ∈ ZS (i) has minimal length, then
a = i + mS (i) · n =

k
X
i=1

si ri + |~s| · n =

k
X
i=1

si (n + ri ),

4

CHRISTOPHER O’NEILL AND ROBERTO PELAYO

meaning a ∈ S. In this way, each minimal length factorization ~s for i ∈ S corresponds
to a factorization of a ∈ Mn with first component zero. More generally, for each ℓ ≥ 0,
there is a natural bijection
{~z ∈ ZMn (a) : |~z| = ℓ} −→ {~s ∈ ZS (a − ℓn) : |~s| ≤ ℓ}
(z0 , z1 , . . . , zk ) 7−→ (z1 , . . . , zk )
between the factorizations of a ∈ Mn of length ℓ and the factorizations of a − ℓn ∈ S
of length at most ℓ, obtained by writing
a = z0 n +

k
X
i=1

zi (n + ri ) = ℓn +

k
X

zi ri

i=1

and subsequently solving for a − ℓn.
Now, since a − mS (i) · n = i ∈ Ap(S; gn), whenever ℓ > mS (i) we have
a − ℓn = (a − mS (i) · n) − (ℓ − mS (i))n = i − (ℓ − mS (i))n ∈
/ S,
so a has no factorizations in Mn of length ℓ. Moreover, a can’t have any factorizations
in Mn with length strictly less than mS (i) since Lemma 3.1 would force every factorization of length mS (i) to have nonzero first coordinate. Putting these together, we see
LMn (a) = {mS (i)}, meaning every factorization of a in Mn has first coordinate zero.
As such, we conclude a ∈ Ap(Mn ; n).

Proposition 3.4. If n ∈ S and n > F (S), then Ap(S; n) = {a0 , . . . , an−1 }, where

gi
if i ∈ S
ai =
gi + n if i ∈
/S
and g = gcd(S). In particular, this holds whenever n > rk2 as in Theorem 3.3.
Proof. Clearly ai ∈ Ap(S; n) for each i ≤ n − 1. Moreover, the values a0 , . . . , an−1 are
distinct modulo n, so the claimed equality holds.

Remark 3.5. Theorem 3.3 and Proposition 3.4 yield an algorithm to compute the
Apéry set of numerical monoids M = hn1 , . . . , nk i that are sufficiently shifted (that is,
if n1 > (nk − n1 )2 ) by first computing the Apéry set for S = hni − n1 : 2 ≤ i ≤ ki.
Table 1 compares the runtime of this algorithm to the one currently implemented in
the GAP package numericalsgps [5]. The strict decrease in runtime halfway down the
last column corresponds to values of n where n > rk2 = 202 = 400, so we may use
Proposition 3.4 to express Ap(S; gn) directly in terms of the gaps of S. This avoids
performing extra modular arithmetic computations for each Apéry set element, as is
normally required to compute Ap(S; gn) from Ap(S).
An implementation will appear in the next release of the numericalsgps package,
and will not require any special function calls. In particular, computing the Apéry set
of a monoid M that is sufficiently shifted will automatically use the improved Apéry
set algorithm, and resort to the existing algorithm in all other cases.

APÉRY SETS OF SHIFTED NUMERICAL MONOIDS

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 [5]
1 ms
30 ms
170 ms
3 sec
17 min
3.6 hr

5

Remark 3.5
1 ms
30 ms
170 ms
1 ms
1 ms
1 ms

Table 1. Runtime comparison for computing Apéry sets of the numerical monoids Mn with S = h6, 9, 20i. All computations performed using
GAP and the package numericalsgps [5].
4. Applications
As Apéry sets can be used to easily compute other numerical monoid invariants, the
results of Section 3 can be applied to provide quick computations of and structural
results for the Frobenius number, genus (Definition 4.2), and type (Definition 4.8) of
Mn for n sufficiently large. In particular, we show that each of these are eventually
quasipolynomial functions of n (Corollaries 4.4, 4.3, and 4.10, respectively).
Definition 4.1. A function f : Z → R is an r-quasipolynomial of degree d if
f (n) = ad (n)nd + · · · + a1 (n)n + a0 (n)
for periodic functions a0 , . . . , ad , whose periods all divide r, with ad not identically 0.
Definition 4.2. Suppose S is a numerical monoid with gcd(S) = 1. The genus of
S is the number g(S) = |Z≥0 \ S| of positive integers that lie outside of S. The
largest integer F (S) = max(Z≥0 \ S) outside of S is the Frobenius number of S. For a
non-primitive monoid T = gS with g ≥ 1, define g(T ) = g · g(S) and F (T ) = g · F (S).
Corollary 4.3. For n > rk2 , the function n 7→ g(Mn ) is rk -quasiquadratic in n.
Proof. By counting the elements of Z≥0 \ Mn modulo n, we can write
X jak
g(Mn ) =
n
a∈Ap(Mn ;n)

Applying Theorem 3.3 and Proposition 3.4, a simple calculation shows that
X
X i
+
mS (i)
g(Mn ) =
n
i∈Ap(S;gn)
i∈Ap(S;gn)

n−1 
X
X
X
gi
mS (gi) +
mS (gi + gn).
=
+ g · g(S) +
n
i≥0
i=0
i<n
gi∈S

gi∈S
/

6

CHRISTOPHER O’NEILL AND ROBERTO PELAYO

Each of the four terms in the above expression is eventually quasipolynomial in n.
Indeed, the first term is g-quasilinear in n, the second term is independent of n, and
Theorem 2.3 implies the third and fourth terms are eventually rk -quasiquadratic and
rk -quasilinear in n, respectively. This completes the proof.

Corollary 4.4 is known in more general contexts [10, 11]. The proof given here yields a
fast algorithm for computing the Frobenius number of Mn for n > rk2 ; see Remark 4.11.
Corollary 4.4. For n > rk2 , the function n → F (Mn ) is rk -quasiquadratic in n.
Proof. Let a denote the element of Ap(S; gn) for which mS (−) is maximal. Theorem 3.3
and Proposition 3.4 imply
F (Mn ) = max(Ap(Mn ; n)) − n = a − n + mS (a) · n.
Theorem 2.3 and Proposition 3.4 together imply a + rk is the element of Ap(S; gn + rk )
for which mS (−) is maximal, and quasilinearity of mS (−) completes the proof.

Remark 4.5. Wilf’s conjecture [13], a famously open problem in the numerical monoids
literature, states that for any primitive numerical monoid S = hr1 , . . . , rk i,
F (S) + 1 ≤ k(F (S) − g(S))
To date, Wilf’s conjecture has only been proven in a handful of special cases, and
remains open in general. Corollary 4.7 adds monoids of the form Mn for n > rk2 to the
list of special cases in which Wilf’s conjecture is known to hold.
Definition 4.6 ([4]). The Wilf number W (S) of a numerical monoid S with embedding
dimension k is given by
W (S) = k(F (S) − g(S)) − (F (S) + 1).
Corollary 4.7. For n > rk2 , the function n 7→ W (Mn ) is rk -quasiquadratic in n.
In particular, Mn satisfies Wilf ’s conjecture for n > rk2 .
Proof. Apply Corollaries 4.3 and 4.4, and note that the quadratic coefficients of the
maps n 7→ F (Mn ) and n 7→ g(Mn ) are constants g/rk and g/2rk , respectively.

We next examine the pseudo-Frobenius numbers of Mn .
Definition 4.8. An integer m ≥ 0 is a pseudo-Frobenius number of a numerical monoid
S if m ∈
/ S but m + n ∈ S for all positive n ∈ S. Denote by P F (S) the set of pseudoFrobenius numbers of S, and by t(S) = |P F (Mn )| the type of S.
Theorem 4.9. Given n ∈ Z≥0 , let Pn denote the set
Pn = {i ∈ Ap(S; gn) : a ≡ i mod n for some a ∈ P F (Mn )}.
For n > rk2 , the map Pn → Pn+rk given by

i
if i ≤ gn
i 7→
i + rk if i > gn

APÉRY SETS OF SHIFTED NUMERICAL MONOIDS

7

is a bijection. In particular, there is a bijection P F (Mn ) → P F (Mn+rk ).
Proof. Fix i ∈ Ap(S; gn) and write a = i + mS (i)n ∈ Ap(Mn ; n). First, if i ≤ gn,
then i ∈ Ap(S; gn + grk ) by Proposition 3.4, so by Theorem 3.3,
a′ = i + mS (i)(n + rk ) = a + mS (i)rk ∈ Ap(Mn+rk ; n + rk ).
Notice that if a + rj ∈ Mn , then the bijection in the proof of Theorem 3.3 implies a + rj
has a factorization of length mS (i) in Mn . As such, for each j we have a′ + rj ∈ Mn+rk
if and only if a + rj ∈ Mn . On the other hand, if i > gn, then i + rk ∈ Ap(S; gn + grk )
by Proposition 3.4, so by Theorem 3.3,
a′ = i + rk + mS (i + rk )(n + rk ) = a + (n + rk ) + (mS (i) + 1)rk ∈ Ap(Mn+rk ; n + rk ).
Once again, a′ + rj ∈ Mn+rk if and only if a + rj ∈ Mn for each j, thus proving the
first claim. The second claim is obtained using the composition
P F (Mn ) −→ Pn −→ Pn+rk −→ P F (Mn+rk )
of the above map with two bijections obtained via reduction modulo n.



Corollary 4.10. The function n 7→ t(Mn ) is eventually rk -periodic. In particular,
Mn is (pseudo)symmetric if and only if Mn+rk is (pseudo)symmetric.
Proof. Apply Theorem 4.9 and [9, Corollaries 3.11 and 3.16].



Remark 4.11. Each of the quantities and properties discussed in this section are
usually computed for a general numerical monoid M by first computing an Apéry set.
Indeed, computing each of these quantities for the monoids in Table 1 takes only
slightly longer than the corresponding Apéry set runtime. As such, computing these
values using the algorithm discussed in Remark 3.5 is also significantly faster for n > rk2 .
References
[1] T. Barron, C. O’Neill, and R. Pelayo, On the set of elasticities in numerical monoids,
Semigroup Forum 94 (2017), no. 1, 37–50.
[2] T. Barron, C. O’Neill, and R. Pelayo, On dymamic algorithms for factorization invariants
in numerical monoids, Mathematics of Computation 86 (2017), 2429–2447.
[3] R. Conaway, F. Gotti, J. Horton, C. O’Neill, R. Pelayo, M. Williams, and B. Wissman, Minimal presentations of shifted numerical monoids, preprint. Available at
arXiv:/1701.08555.
[4] M. Delgado, On a question of Eliahou and a conjecture of Wilf, to appear, Mathematische
Zeitschrift. Available at arXiv:math.CO/1608.01353
[5] 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/.
[6] J. Garcı́a-Garcı́a, M. Moreno-Frı́as, and A. Vigneron-Tenorio, Computation of Delta sets
of numerical monoids, Monatshefte für Mathematik 178 (3) 457–472.
[7] R. Jafari and Z. Armengou, Homogeneous numerical semigroups, preprint. Available at
arXiv:/1603.01078.

8

CHRISTOPHER O’NEILL AND ROBERTO PELAYO

[8] C. O’Neill and R. Pelayo, Factorization invariants in numerical monoids, Contemporary
Mathematics 685 (2017), 231–349.
[9] J. Rosales and P. Garcı́a-Sánchez, Numerical semigroups, Developments in Mathematics,
Vol. 20, Springer-Verlag, New York, 2009.
[10] B. Roune and K. Woods, The parametric Frobenius problem, Electron. J. Combin. 22
(2015), no. 2, Research Paper #P2.36.
[11] B. Shen, The parametric Frobenius problem and parametric exclusion, preprint. Available
at arXiv:math.CO/1510.01349.
[12] T. Vu, Periodicity of Betti numbers of monomial curves, Journal of Algebra 418 (2014)
66–90.
[13] H. Wilf, A circle-of-lights algorithm for the “money-changing problem”,
Amer. Math. Monthly 85 (1978), no. 7, 562–565.
Mathematics Department, University of California Davis, Davis, CA 95616
E-mail address: coneill@math.ucdavis.edu
Mathematics Department, University of Hawai‘i at Hilo, Hilo, HI 96720
E-mail address: robertop@hawaii.edu

