A Sequence of Quasipolynomials Arising from Random Numerical Semigroups

Calvin Leng Department of Mathematics University of California Davis Davis, CA 95616 USA

                  calleng@ucdavis.edu

Christopher O’Neill Department of Mathematics and Statistics San Diego State University San Diego, CA 92182 USA

                   cdoneill@sdsu.edu

Abstract

A numerical semigroup is a cofinite subset of the non-negative integers that is closed under addition. For a randomly generated numerical semigroup, the expected number of minimum generators can be expressed in terms of a doubly-indexed sequence of integers, denoted h_{n,i}, that count generating sets with certain properties. We prove a recurrence that implies the sequence h_{n,i} is eventually quasipolynomial when the second parameter is fixed.

1 Introduction

A numerical semigroup is an additive subsemigroup of ℤ_{≥0} with finite complement. The semigroup generated by a set A = {a_{1}, a_{2}, …, a_{k}} is the smallest additive subsemigroup of ℤ_{≥0} containing A, namely

S = ⟨A⟩ = ⟨a_{1}, …, a_{k}⟩ = {a_{1}x_{1} + ⋯ + a_{k}x_{k} : x_{i} ∈ ℤ_{≥0}}.

A generating set A is minimal if for all x ∈ A, we have ⟨A⟩ ≠ ⟨A \ {x}⟩. Every additive subsemigroup S ⊂ ℤ_{≥0} has a unique minimal generating set, and the embedding dimension of S, denoted e(S), is the size of its minimal generating set (see [3] for a thorough introduction).

The authors of [2] introduce a model for randomly selecting a subsemigroup of ℤ_{≥0} that is similar to the Erdős-Renyi model for random graphs. Their model takes two inputs M ∈ ℤ_{≥1} and p ∈ [0, 1], and randomly selects a generating set A that includes each integer n = 1, 2, …, M with independent probability p. Note that it is possible for a semigroup produced by this model to lack the “finite complement” property, but [2, Theorem 5] implies that asymptotically this happens with probability 0. This justifies the use of the term random numerical semigroup model.

As an example, if M = 40 and p = 0.1, then one possible set is A = {6, 9, 18, 20, 32} (this is not unreasonable, as on average one would expect 4 generators to be selected). However, only 3 elements of A are minimal generators, since 18 = 9 + 9 and 32 = 20 + 6 + 6. As such, the resulting semigroup S = ⟨A⟩ = ⟨6, 9, 20⟩ has embedding dimension 3.

One of the main results in [2] is that the expected number of minimal generators of a numerical semigroup S sampled with the above model can be expressed as

𝔼[e(S)] = ∑_{n=1}^{M} p(1 − p)^{⌊n/2⌋} (h_{n,0} + h_{n,1}p + h_{n,2}p^{2} + ⋯) ,

where h_{n,i} equals the number of sets A ⊂ [1, n/2) ∩ ℤ with |A| = i that minimally generate an additive subsemigroup of ℤ_{≥0} not containing n. Of interest is the asymptotic behavior of 𝔼[e(S)] for fixed p as M → ∞. Although this is currently out of reach, 𝔼[e(S)] can be approximated for fixed M using the above formula, so long as h_{n,i} is known for n ≤ M.

n = 68: 1, 29, 249, 888, 1705, 2014, 1599, 888, 347, 91, 14, 1
n = 69: 1, 31, 301, 1181, 2414, 2939, 2365, 1335, 535, 147, 25, 2
n = 70: 1, 28, 248, 1012, 2218, 2873, 2431, 1414, 569, 155, 26, 2
n = 71: 1, 34, 359, 1577, 3615, 4945, 4481, 2878, 1348, 453, 105, 15, 1
n = 72: 1, 25, 222, 893, 1923, 2498, 2138, 1267, 526, 147, 25, 2
n = 73: 1, 35, 383, 1764, 4252, 6139, 5883, 4008, 2004, 725, 181, 28, 2
n = 74: 1, 34, 337, 1456, 3361, 4694, 4365, 2853, 1345, 453, 105, 15, 1
n = 75: 1, 32, 346, 1582, 3810, 5567, 5428, 3758, 1888, 684, 172, 27, 2
n = 76: 1, 33, 334, 1448, 3413, 5005, 4992, 3559, 1863, 705, 181, 28, 2

Figure 1: Values of h_{n,i} for n = 68 through n = 76.

The doubly-indexed sequence h_{n,i} is awaiting approval on OEIS as \underline{A319608}, computed for n ≤ 90. The sequence can also be viewed at the following URL:

   https://gist.github.com/coneill-math/c2f12c94c7ee12ac7652096329417b7d

Figure 1 contains the values of h_{n,i} for n = 68, …, 76, where each row is comprised of h_{n,0}, h_{n,1}, …, h_{n,d_{n}} from left to right. The following facts about the sequence h_{n,i} are known:

• h_{n,i} is nonzero if and only if n ≥ 1 and 0 ≤ i ≤ d_{n} = ⌊n/2⌋ − ⌊n/3⌋;

• h_{n,0} = 1;

• h_{n,1} = ⌊(n + 1)/2⌋ − τ(n), where τ(n) denotes the number of divisors of n; and

• The sum of the n^{th} row equals the number of irreducible numerical semigroups with Frobenius number n [1, 4], which appears in OEIS as \underline{A158206} [5].

Currently, computing the values of h_{n,i} for large n is time-intensive; the fastest known algorithm computes the n^{th} row by first computing the set of irreducible numerical semigroups with Frobenius number n and utilizing the last bullet point above [4]. This computation takes 3 days for n = 89 on the authors’ machines. The more values of h_{n,i} that are known, the more accurately 𝔼[e(S)] can be approximated. Due to the limited known values of h_{n,i}, approximations computed with the currently known values still differ drastically from those obtained from experimental data; see [2, Table 2] for several sample estimates.

In this paper, we examine the combinatorics of the sequence h_{n,i}. Our main result is Corollary 2, which follows from the following recurrence and states that for fixed k the sequence h_{n,d_{n}−k} coincides with a polynomial in n ≫ 0 whose coefficients are 6-periodic functions of n.

Theorem 1. Fix k ∈ ℤ_{≥0}, b ∈ {0, 1, 2}, and m > 24k + 12 − 8b with m ≡ b (mod 3). The recurrence

h_{n,d_{n}−k} = ∑_{l=0}^{k} h_{m,d_{m}−l}\binom{d_{n} − d_{m}}{k − l}

holds for all n ≥ m satisfying n ≡ b (mod 3).

A quasipolynomial is a function q : ℤ → ℤ such that

q(x) = c_{0}(x) + c_{1}(x)x + c_{2}(x)x^{2} + ⋯ + c_{d}(x)x^{d}

where each c_{i}(x) is a periodic function. The degree of q, denoted deg q, is the largest integer d for which c_{d} is not identically 0, and the period of q is the smallest integer p such that c_{i}(x + p) = c_{i}(x) for every x and i.

Corollary 2. For fixed k, the function n ↦ h_{n,d_{n}−k} coincides with a quasipolynomial

c_{k}(n)n^{k} + ⋯ + c_{1}(n)n + c_{0}(n)

with degree k, period 6, and leading coefficient

c_{k}(n) = \begin{cases}\frac{2}{k!6^{k}} , & if n ≡ 0, 1 (mod 3); \\ \frac{1}{k!6^{k}} , & if n ≡ 2 (mod 3), \end{cases}

for all n > 24k + 12 − 8b, where b ∈ {0, 1, 2} with n ≡ b (mod 3).

In the development of the proof of Theorem 1, we obtain an algorithm for computing the values h_{n,i} appearing in Corollary 2 (Algorithm 19). Our algorithm has obtained h_{n,i} values that were previously unknown. With the improved algorithm and Theorem 1, explicit quasipolynomials have been provided for h_{n,d_{n}−k} for each k ≤ 7 (see Figure 2 for the quasipolynomials up to k = 4). Computing the quasipolynomial coefficients of h_{n,d_{n}−7} requires computing the value of e.g., h_{183,d_{183}−7} = h_{183,23} = 6423209, a task that would have been impossible with existing methods.

2 Setup

Unless otherwise stated, throughout the rest of the paper assume n ∈ ℤ_{≥1} and b_{n} ∈ {0, 1, 2} with n ≡ b_{n} (mod 3). Let

X_{n} = (\frac{n}{3}, \frac{n}{2}) ∩ ℤ.

Definition 3. Fix a set A ⊂ ℤ_{≥1}. We say A works for n ∈ ℤ_{≥1} if

(i) n ∉ ⟨A⟩,

(ii) x < n/2 for all x ∈ A, and

(iii) A minimally generates an additive subsemigroup of ℤ_{≥0}.

In particular, h_{n,i} equals the number of sets A with |A| = i that work for n.

To motivate the next several definitions, recall from Figure 2 that for n ≥ 13,

h_{n,d_{n}} = \begin{cases}2, & if n ≡ 0, 1 (mod 3); \\ 1, & if n ≡ 2 (mod 3). \end{cases}  (1)

The set X_{n} works for n and |X_{n}| = d_{n}. Let E_{0,n} and E_{1,n} denote the remaining working sets for n of size d_{n} when b_{n} = 0 and b_{n} = 1, respectively. The key observation is that for all n,

X_{n} − ⌊\frac{n}{3}⌋ = \{1, 2, …, d_{n}\},
E_{0,n} − ⌊\frac{n}{3}⌋ = \{−1, 1, 3, 4, …, d_{n}\}, and
E_{1,n} − ⌊\frac{n}{3}⌋ = \{0, 2, 3, …, d_{n}\}.

Since X_{n} contains every integer in the interval (n/3, n/2), any other elements in a set counted by h_{n,−} must lie in {1, 2, …, ⌊n/3⌋}. Thus we thought of ⌊n/3⌋ as a sort of cutoff point. From this, it felt natural to express sets in terms of how offset the elements are from ⌊n/3⌋. This motivates the following.

h_{n,d_{n}} = \begin{cases}2, & if n ≡ 0 (mod 6) and n ≥ 18; \\ 2, & if n ≡ 1 (mod 6) and n ≥ 7; \\ 1, & if n ≡ 2 (mod 6) and n ≥ 2; \\ 2, & if n ≡ 3 (mod 6) and n ≥ 15; \\ 2, & if n ≡ 4 (mod 6) and n ≥ 10; \\ 1, & if n ≡ 5 (mod 6) and n ≥ 5. \end{cases}

h_{n,d_{n}−1} = \begin{cases}\frac{1}{3}(n + 3), & if n ≡ 0 (mod 6) and n ≥ 42; \\ \frac{1}{3}(n + 11), & if n ≡ 1 (mod 6) and n ≥ 31; \\ \frac{1}{6}(n + 16), & if n ≡ 2 (mod 6) and n ≥ 26; \\ \frac{1}{3}(n + 6), & if n ≡ 3 (mod 6) and n ≥ 39; \\ \frac{1}{3}(n + 8), & if n ≡ 4 (mod 6) and n ≥ 34; \\ \frac{1}{6}(n + 19), & if n ≡ 5 (mod 6) and n ≥ 23. \end{cases}

h_{n,d_{n}−2} = \begin{cases}\frac{1}{36}(n^{2} + 108), & if n ≡ 0 (mod 6) and n ≥ 66; \\ \frac{1}{36}(n^{2} + 16n + 19), & if n ≡ 1 (mod 6) and n ≥ 55; \\ \frac{1}{72}(n^{2} + 26n + 160), & if n ≡ 2 (mod 6) and n ≥ 50; \\ \frac{1}{36}(n^{2} + 6n + 117), & if n ≡ 3 (mod 6) and n ≥ 63; \\ \frac{1}{36}(n^{2} + 10n − 20), & if n ≡ 4 (mod 6) and n ≥ 58; \\ \frac{1}{72}(n^{2} + 32n + 247), & if n ≡ 5 (mod 6) and n ≥ 47. \end{cases}

h_{n,d_{n}−3} = \begin{cases}\frac{1}{648}(n^{3} − 9n^{2} + 342n − 3240), & if n ≡ 0 (mod 6) and n ≥ 90; \\ \frac{1}{648}(n^{3} + 15n^{2} − 69n + 5885), & if n ≡ 1 (mod 6) and n ≥ 79; \\ \frac{1}{1296}(n^{3} + 30n^{2} + 264n − 1952), & if n ≡ 2 (mod 6) and n ≥ 74; \\ \frac{1}{648}(n^{3} + 315n − 2268), & if n ≡ 3 (mod 6) and n ≥ 87; \\ \frac{1}{648}(n^{3} + 6n^{2} − 132n + 6200), & if n ≡ 4 (mod 6) and n ≥ 82; \\ \frac{1}{1296}(n^{3} + 39n^{2} + 471n − 863), & if n ≡ 5 (mod 6) and n ≥ 71. \end{cases}

h_{n,d_{n}−4} = \begin{cases}\frac{1}{15552}(n^{4} − 24n^{3} + 828n^{2} − 17280n + 419904), & if n ≡ 0 (mod 6) and n ≥ 114; \\ \frac{1}{15552}(n^{4} + 8n^{3} − 282n^{2} + 24728n + 413225), & if n ≡ 1 (mod 6) and n ≥ 103; \\ \frac{1}{31104}(n^{4} + 28n^{3} + 204n^{2} − 10256n + 454912), & if n ≡ 2 (mod 6) and n ≥ 98; \\ \frac{1}{15552}(n^{4} − 12n^{3} + 666n^{2} − 12852n + 374949), & if n ≡ 3 (mod 6) and n ≥ 111; \\ \frac{1}{15552}(n^{4} − 4n^{3} − 300n^{2} + 26528n − 490112), & if n ≡ 4 (mod 6) and n ≥ 106; \\ \frac{1}{31104}(n^{4} + 40n^{3} + 510n^{2} − 8168n + 426817), & if n ≡ 5 (mod 6) and n ≥ 95. \end{cases}

Figure 2: Quasipolynomial expressions for h_{n,d_{n}−k} with k = 0, 1, …, 4.

Definition 4. The offset form of a set A = {x_{1}, x_{2}, …, x_{k}} ⊂ ℤ_{≥1} is the set

A_{(n)} = A − ⌊n/3⌋ = {x_{1} − ⌊n/3⌋ , x_{2} − ⌊n/3⌋ , …, x_{k} − ⌊n/3⌋}.

After expressing the sets we computed in offset form, we noticed that we could go one step further. We noticed that if we instead expressed sets in terms of how different they are from X_{n} and then take the offset form of the result, the expressions would be equal. This motivates the following.

Definition 5. A set I ⊆ ℤ is an inserting set for n ∈ ℤ_{≥1} if

I_{(n)} ⊆ {− ⌊n/3⌋ , …, −1, 0},

and a set R ⊆ ℤ is a removing set for n if

R_{(n)} ⊆ {1, 2, …, d_{n}}.

An RI-pair for n is a pair (R, I) of a removing set R and an inserting set I.

There is a natural bijection between RI-pairs for n and the power set of {1, 2, …, d_{n}} given by the map

φ_{n}(R, I) = (X_{n} \ R) ∪ I.

The inverse map is given by

A ↦ (X_{n} \ A, A \ X_{n}).

Since φ_{n} gives a bijection between the two objects, we say the set corresponding to an RI-pair (R, I) is the set φ_{n}(R, I), and vice-versa.

Theorem 1 follows from the fact that for fixed k and large n, every RI-pair (R, I) corresponding to a working set for n of size d_{n} − k satisfies I_{(n)} ⊆ {p_{n}(k), …, −1, 0}, where

p_{n}(k) = b_{n} − 2k − 1

only depends on n modulo 3 (Theorem 15). As a consequence, the restrictions on removal sets corresponding to a given insertion set are independent of the size of n in this case.

Example 6. If n = 11 and k = 1, then h_{n,d_{n}−k} = h_{11,1} = 4 and X_{n} = {4, 5}. The sets A with |A| = 1 that work for 11 are

\begin{matrix}A = \{2\} = (X_{n} \ \{4, 5\}) ∪ \{2\}, & A = \{4\} = (X_{n} \ \{5\}) ∪ \{\}, \\ A = \{3\} = (X_{n} \ \{4, 5\}) ∪ \{3\}, and & A = \{5\} = (X_{n} \ \{4\}) ∪ \{\}. \end{matrix}

Theorem 11 classifies the possible RI-pairs that correspond to working sets for large n.

3 Strongly bounded sets

We begin by classifying the working sets for n that are strongly n-bounded (Definition 7). As it turns out, for k fixed and large n, every working set for n with size d_{n} − k is strongly n-bounded (Theorem 16). Note that any strongly n-bounded set automatically satisfies parts (ii) and (iii) of Definition 3.

In what follows, we utilize the notation mB = {mb : b ∈ B} for B ⊂ ℚ and m ∈ ℚ.

Definition 7. We say a set A ⊂ ℤ_{≥1} is strongly n-bounded if A ⊂ (n/4, n/2).

Proposition 8. A strongly n-bounded set A works for n if and only if b_{n} ∉ 3A_{(n)}.

Proof. Any strongly n-bounded set automatically satisfies part (ii) and (iii) of Definition 3 since x + y > \frac{n}{2} > z for any x, y, z ∈ A. As such, A works for n if and only if n ∉ ⟨A⟩. Moreover, since A is strongly n-bounded, we have x < n < y for any x ∈ 2A and y ∈ 4A, so n ∈ ⟨A⟩ if and only if n ∈ 3A. The claim now follows from the fact that n = 3 ⌊n/3⌋+b_{n}.

Definition 9. An RI-pair (R, I) is compatible for n (or, equivalently, R is compatible with I) if the corresponding set A satisfies b_{n} ∉ 3A_{(n)}. The removal degree of an inserting set I, denoted r(I), is given by

r(I) = min{|R| : (R, I) is compatible}

and the removal degree of an integer α ≤ 0 is given by r(α) = r({α}).

Remark 10. Note that Proposition 8 does not imply that an RI-pair (R, I) compatible for n corresponds to a set A that works for n, as A need not be strongly n-bounded in general.

Theorem 11 classifies the RI-pairs compatible for n in terms of I_{(n)} and R_{(n)} by examining the different ways for three integers to sum to b_{n} ∈ {0, 1, 2}.

Theorem 11. If A is a set and (R, I) is the corresponding RI-pair, then b_{n} ∉ 3A_{(n)} if and only if for all α ∈ I_{(n)}, the following hold:

(i) b_{n} − 2α ∈ R_{(n)};

(ii) (b_{n} − α)/2 ∈ R_{(n)} if α ≡ b_{n} (mod 2);

(iii) b_{n} − α − β ∈ R_{(n)} for all β ∈ I_{(n)} with β ≠ α; and

(iv) y ∈ R_{(n)} or b_{n} − α − y ∈ R_{(n)} for all y satisfying 1 ≤ y < b_{n} − α − y.

Proof. If any of (i)-(iv) is violated for some α ∈ I_{(n)}, then it is easy to check that b_{n} ∈ 3A_{(n)}. Conversely, suppose b_{n} ∈ 3A_{(n)}, meaning α + y + z = b_{n} for some α, y, z ∈ 3A_{(n)} with α ≤ y ≤ z. Since b_{n} ∈ {0, 1, 2}, we must have α ≤ 0 and thus α ∈ I_{(n)}. Let S = {α, y, z}. If every element of S is nonpositive, then α = y = z = b_{n} = 0 so (i) fails to hold and we are done. As such, at most 2 elements of S are nonpositive, so z > 0. Similarly, if |S| = 1, then α = y = z = b_{n} = 0 so (i) fails to hold and we are done. This leaves four distinct cases:

• |S| = 2 and y ≤ 0, in which case y = α and (i) fails to hold;

• |S| = 2 and y > 0, in which case y = z and (ii) fails to hold;

• |S| = 3 and y ≤ 0, in which case α ≠ y and (iii) fails to hold; or

• |S| = 3 and y > 0, in which case y ≠ z and (iv) fails to hold.

This completes the proof.

Remark 12. Given an inserting set I, Theorem 11 provides a systematic way to construct a removing set R such that the set A corresponding to (R, I) satisfies b_{n} ∉ 3A_{(n)}. Most applications of Theorem 11 will involve starting with a set R = ∅ and systematically putting elements into R; see Example 20. Moreover, Theorem 11 yields a better-than-brute-force method of computing h_{n,d_{n}−k} for large n; see Algorithm 19.

Lemma 13. We have

r(α) = 1 + ⌈\frac{b_{n} − α − 1}{2}⌉

for any integer α ≤ 0.

Proof. Fix α ≤ 0, let I = {α}, and suppose R is a removing set that is minimal among all removing sets compatible with I. We will apply Theorem 11, noting that for fixed α, parts (i)-(iv) each require distinct elements to lie in R_{(n)}. Theorem 11(i) requires 1 element to lie in R, and Theorem 11(iv) forces ⌊(b_{n} − α − 1)/2⌋ additional elements to lie in R. Since |I| = 1, Theorem 11(iii) is vacuously satisfied. This leaves Theorem 11(ii), which only requires an additional element to lie in R if α ≡ b_{n} (mod 2). This completes the proof.

Lemma 14. If A ⊂ ℤ_{≥1} corresponds to an RI-pair (R, I) that is compatible for n, then

|A| ≤ d_{n} + 1 − r(m),

where m = min I_{(n)}.

Proof. Let m = min I_{(n)}, and apply Theorem 11 to α = m. Following the proof of Lemma 13, Theorem 11(i), (ii), and (iv) require r(m) elements to lie in R, and Theorem 11(iii) requires R to contain an additional |I| − 1 elements. We conclude

|A| = d_{n} + |I| − |R| ≤ d_{n} + |I| − r(m) − |I| + 1 = d_{n} + 1 − r(m),

as desired.

Theorem 15. Fix k ∈ ℤ_{≥0}, and suppose A ⊂ ℤ_{≥1} corresponds to an RI-pair (R, I) that is compatible for n. If |A| ≥ d_{n} − k, then

I_{(n)} ⊂ {p_{n}(k), p_{n}(k) + 1, …, −1, 0}.

Proof. Let m = min I_{(n)}. By Lemma 14, we have

d_{n} − k ≤ |A| ≤ d_{n} + 1 − r(m),

meaning k ≥ r(m) − 1. Applying Lemma 13, we obtain

k ≥ 1 + ⌈\frac{b_{n} − m − 1}{2}⌉ − 1 ≥ \frac{b_{n} − m − 1}{2}

which can then be rearranged to yield m ≥ b_{n} − 2k − 1 = p_{n}(k).

Theorem 16. If n > 24k + 12 − 8b_{n}, then every set A with |A| = d_{n} − k that works for n is strongly n-bounded.

Proof. Fix a set A with |A| = d_{n} − k that works for n. Theorem 15 implies

min A − p_{n}(k) ≥ ⌊\frac{n}{3}⌋ = \frac{n − b_{n}}{3} = \frac{\frac{1}{4}n − b_{n}}{3} + \frac{n}{4} > \frac{6k + 3 − 3b_{n}}{3} + \frac{n}{4} = 2k + 1 − b_{n} + \frac{n}{4}

meaning A is strongly n-bounded.

4 Proof of Theorem 1

We now have enough machinery to prove Theorem 1 and Corollary 2.

Proof of Theorem 1. Fix n, m ∈ ℤ satisfying n ≡ m (mod 3) and n ≥ m > 24k + 12 − 8b_{n}. Let S_{k} denote the set of k-subsets of {d_{m} + 1, d_{m} + 2, …, d_{n}}. We will prove the claim combinatorially by constructing a bijection between

A := {A : A works for n and |A| = d_{n} − k}

and

B := ⋃_{l=0}^{k} ({A : A works for m and |A| = d_{m} − l} × S_{k−l}).

Fix A ∈ A, and let (R, I) denote the corresponding RI-pair. Write R = R_{1} ∪ R_{2} with

(R_{1})_{(n)} = {α ∈ R_{(n)} : 1 ≤ α ≤ d_{m}} and
(R_{2})_{(n)} = {α ∈ R_{(n)} : d_{m} + 1 ≤ α ≤ d_{n}},

and define f : A → B by

f(A) = (φ_{m}(R_{1}, I), (R_{2})_{(n)}).

We first show f is well-defined. Let l = |R_{1}| − |I|. It is clear that (R_{2})_{(n)} ∈ S_{k−l}, and (R_{1}, I) is an RI-pair for m, so it remains to show that (R_{1}, I) is compatible for m. By Theorem 16, A is strongly n-bounded, so Theorem 15 implies min I_{(n)} ≥ p_{n}(k) = p_{m}(k). The key observation is that the criteria in Theorem 11(i)-(iv) only involve I_{(n)} and R_{(n)}, so tracing through each part, the fact that (R, I) is compatible for n implies (R_{1}, I) is compatible for m. Hence, f is well-defined.

To prove f is a bijection, we observe that basic set-theoretic arguments verify the map

((R_{1}, I), R_{2}) ↦ (R_{1} ∪ R_{2}, I),

is the inverse function of f, thereby completing the proof.

Proof of Corollary 2. Fix k ≥ 0 and b ∈ {0, 1, 2}, and let

m = min{x > 24k + 12 − 8b : x ≡ b (mod 3)}.

For any n ≥ m satisfying n ≡ b (mod 3), we obtain the expression

h_{n,d_{n}−k} = h_{m,d_{m}−k}\binom{d_{n} − d_{m}}{0} + h_{m,d_{m}−k+1}\binom{d_{n} − d_{m}}{1} + ⋯ + h_{m,d_{m}} \binom{d_{n} − d_{m}}{k} (2)

from Theorem 1, wherein each binomial coefficient is a polynomial in d_{n} of degree at most k. Since d_{n} is a quasilinear function of n with period 6, we conclude h_{n,d_{n}−k} is a quasipolynomial in n of degree k and period 6.

It remains to verify the leading coefficient of h_{n,d_{n}−k} has the desired form. The highest degree term in (2) is

h_{m,d_{m}} \binom{d_{n} − d_{m}}{k} = h_{m,d_{m}} \frac{(d_{n} − d_{m}) · (d_{n} − d_{m} − 1) ⋯ (d_{n} − d_{m} − k)}{k!}.

Combined with the fact that d_{n} has constant leading coefficient 1/6, we obtain the leading coefficient h_{m,d_{m}}/k!6^{k}, and the claim now follows from examination of Figure 2.

Example 17. For fixed k ≥ 1, the proof of Corollary 2 provides a slightly optimized method of computing the eventual quasipolynomial form of h_{n,d_{n}−k}. For example, let k = 3 and b = 0. In this case, m = 87, and consulting \underline{A319608} we see

h_{87,d_{87}−0} = 2,  h_{87,d_{87}−1} = 31,  h_{87,d_{87}−2} = 228,  and  h_{87,d_{87}−3} = 1055.

From here, we obtain

h_{n,d_{n}−3} = 2 · \binom{d_{n} − d_{87}}{3} + 31 · \binom{d_{n} − d_{87}}{2}

+ 228 · \binom{d_{n} − d_{87}}{1} + 1055 · \binom{d_{n} − d_{87}}{0}

for all n ≡ 0 (mod 3) such that n ≥ 87. Expanding binomial coefficients yields

h_{n,d_{n}−3} = \frac{1}{6}(2d_{n}^{3} + 3d_{n}^{2} + 19d_{n} − 12),

and substituting

d_{n} = ⌊\frac{n − 1}{2}⌋ − ⌊\frac{n}{3}⌋ = \begin{cases}\frac{1}{6}n − 1, & if n ≡ 0 (mod 6); \\ \frac{1}{6}n − \frac{1}{2}, & if n ≡ 3 (mod 6). \end{cases}

into the expression for h_{n,d_{n}−3}, we arrive at

h_{n,d_{n}−3} = \begin{cases}\frac{1}{648}(n^{3} − 9n^{2} + 342n − 3240), & if n ≡ 0 (mod 6), n ≥ 87; \\ \frac{1}{648}(n^{3} + 315n − 2268), & if n ≡ 3 (mod 6), n ≥ 90. \end{cases}

Repeating this process for b = 1, 2 yields the function given in Figure 2.

Remark 18. It is interesting to note that the eventual quasipolynomial form of h_{n,d_{n}−3} would not be impossible to compute using the “standard” method of finding polynomial coefficients. Indeed, the values of h_{n,i} have only been successfully computed for n ≤ 90, and since the quasipolynomial behavior of h_{n,d_{n}−3} only holds for n ≥ 87, the standard methods of finding the coefficients of a cubic require knowing h_{87,d_{87}−3}, h_{90,d_{90}−3}, …, most of which have yet to be computed. The above method, on the other hand, only relies on h_{87,d_{87}−i} for 0 ≤ i ≤ 3.

Algorithm 19. The theory developed in Section 3 yields an algorithm to compute h_{m,d_{m}−k} for m > 24k + 12 − 8b_{m}. In particular, for each possible inserting set I ⊂ {p_{m}(k), …, −1, 0} for m, Theorem 11 determines precisely which removal sets R are compatible with I. Example 20 demonstrates the main idea of the algorithm.

The authors used a C++ implementation, now posted on Github at the following URL,

              https://github.com/calvinleng97/rnsg-qp-coeffs ,

to compute the quasipolynomial functions in Corollary 2 up to k = 7, the last of which took 6 hours to complete.

Example 20. Suppose n = 60, and consider the insertion set I = {17, 18}. Theorem 11 provides a systematic method of constructing all removal sets R that are compatible with I. Since min I > n/4, the resulting set will be strongly n-bounded. This ensures the resulting sets A corresponding to (R, I) will work for n.

We check every item of Theorem 11 with every element α ∈ I_{(n)} to construct R_{(n)}. We first compute the offset form

I_{(n)} = {−3, −2}

and initialize R_{(n)} = ∅. Note that b_{n} = 0 since 60 ≡ 0 (mod 3). We begin by applying Theorem 11(i)-(iii) to each α ∈ I_{(n)}, since Theorem 11(iv) requires additional decisions.

For α = −2, we see that 1, 4, 5 ∈ R_{(n)}, and for α = −3, we must have R_{(n)} = {1, 4, 5, 6}. Lastly, we deal with Theorem 11(iv), which is vacuously satisfied for α = −2, and for α = −3 implies either 1 ∈ R_{(n)} or 2 ∈ R_{(n)}, the first of which is already required from above. As such, R_{(n)} = {1, 4, 5, 6} yields a removal R = {21, 24, 25, 26} that is compatible with I. Moreover, any removal set R′ ⊃ R is also compatible with I.

5 Future work

Although the quasipolynomials in Corollary 2 only hold for n sufficiently large, the machinery developed in Section 3 describes the sets counted by h_{n,d_{n}−k} and the relations between them as n varies. For n just below the start of quasipolynomial behavior, computations indicate the sets counted by h_{n,d_{n}−k} are simply those predicted by Theorem 11 that still minimally generate an additive subsemigroup of ℤ_{≥0}. A better understanding of this phenomenon could allow Algorithm 19 to be extended to all n ≥ 1, rather than just sufficiently large n.

Problem 21. Characterize the sets counted by h_{n,d_{n}−k} for all n in terms of those counted by h_{n,d_{n}−k} for n sufficiently large.

Algorithm 19 has the potential to be parallelized (with different threads handling different insertion sets), but the current implementation does not take advantage of this fact. Doing so would likely extend the current limits of computation, which would be especially useful if Problem 21 has a positive answer.

Problem 22. Write a parallelized implementation of Algorithm 19.

References

[1] J. Backelin, On the number of semigroups of natural numbers, Math. Scand. 66 (1990), 197–215.

[2] J. De Loera, C. O’Neill, and D. Wilbourne, Random numerical semigroups and a simplicial complex of irreducible semigroups, preprint, 2017, https://arxiv.org/abs/1710.

   00979.

[3] J. Rosales and P. García-Sánchez, Numerical Semigroups, Developments in Mathematics, Vol. 20, Springer-Verlag, 2009.

[4] J. Rosales, P. García-Sánchez, J. García-García, J. Jiménez Madrid, Fundamental gaps in numerical semigroups, J. Pure Appl. Algebra 189 (2004), 301–313.

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.

2010 Mathematics Subject Classification: Primary 20M14; Secondary 05E40. Keywords: numerical semigroup, quasipolynomial.

(Concerned with sequences \underline{A158206} and \underline{A319608}.)

Received October 9 2018; revised version received August 7 2019. Published in Journal of Integer Sequences, August 24 2019.

Return to Journal of Integer Sequences home page.