NUMERICAL SEMIGROUPS&KUNZ POLYTOPESOSAKA UNIVERSITY
AUGUST 2018

Introduction

Elie Alhajjar

United States Military Academy

Introduction
Question:
In how many ways can we remove g positive integers from ℕ0 so that the remaining set isadditively closed?

Elie Alhajjar

United States Military Academy

Introduction
Question:
In how many ways can we remove g positive integers from ℕ0 so that the remaining set isadditively closed?

Answer:I don’t know!

Elie Alhajjar

United States Military Academy

Introduction• A numerical semigroup is an additive sub-monoid of ℕ0 = {0,1,2,3,…} whose
complement is finite.

Elie Alhajjar

United States Military Academy

Introduction• A numerical semigroup is an additive sub-monoid of ℕ0 = {0,1,2,3,…} whose
complement is finite.
• The genus of S is the number of gaps, i.e. the cardinality of its complement.

Elie Alhajjar

United States Military Academy

Introduction• A numerical semigroup is an additive sub-monoid of ℕ0 = {0,1,2,3,…} whose
complement is finite.
• The genus of S is the number of gaps, i.e. the cardinality of its complement.
• The multiplicity of S is the smallest nonzero element in S.

Elie Alhajjar

United States Military Academy

Introduction• A numerical semigroup is an additive sub-monoid of ℕ0 = {0,1,2,3,…} whose
complement is finite.
• The genus of S is the number of gaps, i.e. the cardinality of its complement.
• The multiplicity of S is the smallest nonzero element in S.
• The embedding dimension of S is the size of its minimal generating set.

Elie Alhajjar

United States Military Academy

Introduction• A numerical semigroup is an additive sub-monoid of ℕ0 = {0,1,2,3,…} whose
complement is finite.
• The genus of S is the number of gaps, i.e. the cardinality of its complement.
• The multiplicity of S is the smallest nonzero element in S.
• The embedding dimension of S is the size of its minimal generating set.
• The Frobenius number of S is the largest number NOT in S.

Elie Alhajjar

United States Military Academy

Example

Elie Alhajjar

United States Military Academy

ExampleS = {0,3,6,8,9,11,12,14,15,16,…}= ℕ0 \ {1,2,4,5,7,10,13}= < 3,8 >Elie Alhajjar

United States Military Academy

ExampleS = {0,3,6,8,9,11,12,14,15,16,…}= ℕ0 \ {1,2,4,5,7,10,13}= < 3,8 >g(S) = 7

Elie Alhajjar

United States Military Academy

ExampleS = {0,3,6,8,9,11,12,14,15,16,…}= ℕ0 \ {1,2,4,5,7,10,13}= < 3,8 >g(S) = 7m(S) = 3

Elie Alhajjar

United States Military Academy

ExampleS = {0,3,6,8,9,11,12,14,15,16,…}= ℕ0 \ {1,2,4,5,7,10,13}= < 3,8 >g(S) = 7m(S) = 3
F(S) = 13

Elie Alhajjar

United States Military Academy

ExampleS = {0,3,6,8,9,11,12,14,15,16,…}= ℕ0 \ {1,2,4,5,7,10,13}= < 3,8 >g(S) = 7m(S) = 3
F(S) = 13e(S) = 2

Elie Alhajjar

United States Military Academy

Applications

Elie Alhajjar

United States Military Academy

Applications• Diophantine Equations:Nonnegative integer solutions to equations of the form a1x1 + … + anxn = b, where
a1,…,an and b are natural numbers with gcd (a1,…,an) = 1

Elie Alhajjar

United States Military Academy

Applications• Diophantine Equations:Nonnegative integer solutions to equations of the form a1x1 + … + anxn = b, where
a1,…,an and b are natural numbers with gcd (a1,…,an) = 1• Commutative Algebra:
Families of numerical semigroups yielding complete intersection and thus Gorensteinsemigroup rings of the form K[ta : a in S ]Elie Alhajjar

United States Military Academy

Applications• Diophantine Equations:Nonnegative integer solutions to equations of the form a1x1 + … + anxn = b, where
a1,…,an and b are natural numbers with gcd (a1,…,an) = 1• Commutative Algebra:
Families of numerical semigroups yielding complete intersection and thus Gorensteinsemigroup rings of the form K[ta : a in S ]• Algebraic Geometry:
The local intersection multiplicities of formal power series form a numerical semigroup
under some conditions

Elie Alhajjar

United States Military Academy

Applications• Algebraic Codes:
Classification of Weierstrass numerical semigroups in coding theory and cryptography

Elie Alhajjar

United States Military Academy

Applications• Algebraic Codes:
Classification of Weierstrass numerical semigroups in coding theory and cryptography• Moreover:
Factorization of monoids
Singularities of plane algebraic curves
One-dimensional analytically irreducible local domainsetc…

Elie Alhajjar

United States Military Academy

The Problem

Elie Alhajjar

United States Military Academy

The Problem
Combinatorial Question:
In how many ways can we remove g positive integers from ℕ0 so that the remaining set isadditively closed?

Elie Alhajjar

United States Military Academy

The Problem
Combinatorial Question:
In how many ways can we remove g positive integers from ℕ0 so that the remaining set isadditively closed?
Equivalently:
What is the number N(g) of numerical semigroups with genus g?

Elie Alhajjar

United States Military Academy

Tree StructureElie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure

Elie Alhajjar

United States Military Academy

Tree Structure
N(0) = 1

N(1) = 1

N(2) = 2

N(3) = 4

N(4) = 7

Elie Alhajjar

United States Military Academy

Numerical Computation

Elie Alhajjar

United States Military Academy

Numerical Computation• N(10) = 204• N(20) = 37,396• N(30) = 5,646,773• N(40) = 774,614,284• N(50) = 101,090,300,128• N(67) = 377,866,907,506,273

Elie Alhajjar

United States Military Academy

Bounds

Elie Alhajjar

United States Military Academy

Bounds• Bras Amoros `08:
1N(g) ≤𝑔𝑔+1

Elie Alhajjar

2𝑔𝑔
𝑔𝑔

United States Military Academy

Bounds• Bras Amoros `08:
1N(g) ≤𝑔𝑔+12𝑔𝑔
𝑔𝑔• Bras Amoros `08, Elizalde `10:
Fg+2 – 1 ≤ N(g) ≤ 1 + 3.2g-3

Elie Alhajjar

United States Military Academy

Asymptotical Behavior

Elie Alhajjar

United States Military Academy

Asymptotical Behavior• Conjecture (Bras-Amoros `08):
𝑁𝑁 𝑔𝑔−1 +𝑁𝑁(𝑔𝑔−2)=1𝑁𝑁(𝑔𝑔)𝑔𝑔→∞

1) lim

𝑁𝑁 𝑔𝑔= φ, the golden ratio.
𝑔𝑔→∞ 𝑁𝑁(𝑔𝑔−1)2) limElie Alhajjar

United States Military Academy

Asymptotical Behavior• Conjecture (Bras-Amoros `08):
𝑁𝑁 𝑔𝑔−1 +𝑁𝑁(𝑔𝑔−2)=1𝑁𝑁(𝑔𝑔)𝑔𝑔→∞

1) lim

𝑁𝑁 𝑔𝑔= φ, the golden ratio.
𝑔𝑔→∞ 𝑁𝑁(𝑔𝑔−1)2) lim• Theorem (Zhai `13):
𝑁𝑁 𝑔𝑔
𝑔𝑔→∞ 𝜑𝜑𝑔𝑔

lim

Elie Alhajjar= K for some constant K,United States Military Academy

Asymptotical Behavior• Conjecture (Bras-Amoros `08):
𝑁𝑁 𝑔𝑔−1 +𝑁𝑁(𝑔𝑔−2)=1
𝑁𝑁(𝑔𝑔)
𝑔𝑔→∞1) lim

𝑁𝑁 𝑔𝑔= φ, the golden ratio.
𝑔𝑔→∞ 𝑁𝑁(𝑔𝑔−1)2) lim• Theorem (Zhai `13):
𝑁𝑁 𝑔𝑔
𝑔𝑔→∞ 𝜑𝜑𝑔𝑔

lim

Elie Alhajjar= K for some constant K, hence 1) and 2) hold.

United States Military Academy

Nonetheless…

Elie Alhajjar

United States Military Academy

Nonetheless…
• Strong Genus Conjecture:
N(g) ≥ N(g – 1) + N(g – 2) for all g ≥ 2

Elie Alhajjar

United States Military Academy

Nonetheless…
• Strong Genus Conjecture:
N(g) ≥ N(g – 1) + N(g – 2) for all g ≥ 2• Weak Genus Conjecture:
N(g) ≥ N(g – 1) for all g ≥ 1

Elie Alhajjar

United States Military Academy

Apéry Sets

Elie Alhajjar

United States Military Academy

Apéry Sets
• Let S be a numerical semigroup with multiplicity m. The Apéry set of S with respect tom is defined as
Ap(S,m) = {0, w(1), w(2),…, w(m-1)},
where w(i) = ki m + i is the smallest element in S that is congruent to i mod m.

Elie Alhajjar

United States Military AcademyApéry Sets
• Let S be a numerical semigroup with multiplicity m. The Apéry set of S with respect tom is defined as
Ap(S,m) = {0, w(1), w(2),…, w(m-1)},
where w(i) = ki m + i is the smallest element in S that is congruent to i mod m.
• Theorem (Selmer `77):1) g(S) = k1 + k2 + … + km-1

Elie Alhajjar

United States Military Academy

Apéry Sets
• Let S be a numerical semigroup with multiplicity m. The Apéry set of S with respect tom is defined as
Ap(S,m) = {0, w(1), w(2),…, w(m-1)},
where w(i) = ki m + i is the smallest element in S that is congruent to i mod m.
• Theorem (Selmer `77):1) g(S) = k1 + k2 + … + km-12) F(S) = max [Ap(S,m)] – mElie Alhajjar

United States Military Academy

From N(g) to N(m,g)

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g)• Let N(m,g) be the number of numerical semigroups with genus g and multiplicity m.

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g)• Let N(m,g) be the number of numerical semigroups with genus g and multiplicity m.
Clearly, N(g) = N(1,g) + N(2,g) + … + N(g,g) + N(g+1,g).

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g)• Let N(m,g) be the number of numerical semigroups with genus g and multiplicity m.
Clearly, N(g) = N(1,g) + N(2,g) + … + N(g,g) + N(g+1,g).
• Theorem (Kunz `87, Rosales et al. `02):
There is a one-to-one correspondence between the set of numerical semigroups of genus
g and multiplicity m and the integer points satisfying the following conditions:xi ≥ 1,xi + xi – xi+j ≥ 0xi + xi – xi+j-m ≥ -1

Elie Alhajjar

for all i = 1,2,…,m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≤ m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≥ m + 1

United States Military Academy

From N(g) to N(m,g)• Let N(m,g) be the number of numerical semigroups with genus g and multiplicity m.
Clearly, N(g) = N(1,g) + N(2,g) + … + N(g,g) + N(g+1,g).
• Theorem (Kunz `87, Rosales et al. `02):
There is a one-to-one correspondence between the set of numerical semigroups of genus
g and multiplicity m and the integer points satisfying the following conditions:xi ≥ 1,xi + xi – xi+j ≥ 0
xi + xi – xi+j-m ≥ -1
x1 + … + xm-1 = g

Elie Alhajjar

for all i = 1,2,…,m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≤ m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≥ m + 1

United States Military Academy

From N(g) to N(m,g) to MED(m,g)

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g) to MED(m,g)• Let MED(m,g) be the number of maximal embedding dimension numerical semigroups
with genus g and multiplicity m, i.e. e(S) = m(S).

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g) to MED(m,g)• Let MED(m,g) be the number of maximal embedding dimension numerical semigroups
with genus g and multiplicity m, i.e. e(S) = m(S).
Clearly, MED(g) = MED(1,g) + MED(2,g) + … + MED(g,g) + MED(g+1,g).

Elie Alhajjar

United States Military Academy

From N(g) to N(m,g) to MED(m,g)• Let MED(m,g) be the number of maximal embedding dimension numerical semigroups
with genus g and multiplicity m, i.e. e(S) = m(S).
Clearly, MED(g) = MED(1,g) + MED(2,g) + … + MED(g,g) + MED(g+1,g).
• Theorem (Kunz `87, Rosales et al. `02):
There is a one-to-one correspondence between the set of maximal embedding dimension
numerical semigroups of genus g and multiplicity m and the integer points satisfying thefollowing conditions:xi ≥ 1,xi + xi – xi+j ≥ 1xi + xi – xi+j-m ≥ 0
x1 + … + xm-1 = g

Elie Alhajjar

for all i = 1,2,…,m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≤ m – 1
for all 1 ≤ i ≤ j ≤ m – 1 & i + j ≥ m + 1

United States Military Academy

Polyhedral Structure

Elie Alhajjar

United States Military Academy

Polyhedral Structure• Let PN be the polytope corresponding to N(m,g) and PMED the polytope corresponding toMED(m,g). Define P to be the polytope satisfying the same inequalities with 0 on theright hand side.

Elie Alhajjar

United States Military Academy

Polyhedral Structure• Let PN be the polytope corresponding to N(m,g) and PMED the polytope corresponding toMED(m,g). Define P to be the polytope satisfying the same inequalities with 0 on theright hand side.
• Clearly, PMED ⊆ P ⊆ PN and they all are (m – 2)-dimensional.

Elie Alhajjar

United States Military Academy

Polyhedral Structure• Let PN be the polytope corresponding to N(m,g) and PMED the polytope corresponding toMED(m,g). Define P to be the polytope satisfying the same inequalities with 0 on theright hand side.
• Clearly, PMED ⊆ P ⊆ PN and they all are (m – 2)-dimensional.

• Embedding the last equation into the previous inequalities, we can write these polytopes
in the form A.x ≥ b(g) where A is a matrix with integer entries and b is a vector whose
coordinates are linear functions in terms of g. We mention some of the properties of PN:

Elie Alhajjar

United States Military Academy

Polyhedral Structure1) The matrix A has

Elie Alhajjar

𝑚𝑚2 −12rows.

United States Military Academy

Polyhedral Structure1) The matrix A has

𝑚𝑚2 −12rows.

2) The coordinates of b(g) belong to the set {0,1,-1,g,-g+1,-g-1,-2g-1}.

Elie Alhajjar

United States Military Academy

Polyhedral Structure1) The matrix A has

𝑚𝑚2 −12rows.

2) The coordinates of b(g) belong to the set {0,1,-1,g,-g+1,-g-1,-2g-1}.
3) For g ≥ (m – 1)2, the polytope P “stabilizes”, i.e. φ(m) inequalities become redundant.

Elie Alhajjar

United States Military Academy

The Case m = 4

Elie Alhajjar

United States Military Academy

The Case m = 4

Elie Alhajjar

United States Military Academy

Combinatorial Structure

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Let p(g) be the number of integer points in P.
Since PMED ⊆ P ⊆ PN , it follows that MED(m,g) ≤ p(g) ≤ N(m,g)

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Let p(g) be the number of integer points in P.
Since PMED ⊆ P ⊆ PN , it follows that MED(m,g) ≤ p(g) ≤ N(m,g)• Theorem (Kaplan `12):
For fixed m, N(m,g) agrees eventually with a quasipolynomial in g of degree m – 2, withperiod depending on m. The same holds for MED(m,g).

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Let p(g) be the number of integer points in P.
Since PMED ⊆ P ⊆ PN , it follows that MED(m,g) ≤ p(g) ≤ N(m,g)• Theorem (Kaplan `12):
For fixed m, N(m,g) agrees eventually with a quasipolynomial in g of degree m – 2, withperiod depending on m. The same holds for MED(m,g).
• Theorem (Blanco et al. `11):
For fixed m, N(m,g) and MED(m,g) can be computed in polynomial time.
Consequently, the same holds for N(g) and MED(g).

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Theorem:
𝑁𝑁 𝑚𝑚, 𝑔𝑔
𝑀𝑀𝑀𝑀𝑀𝑀 𝑚𝑚, 𝑔𝑔
lim
= lim
= 𝑉𝑉𝑉𝑉𝑉𝑉 𝑃𝑃 .
𝑔𝑔→∞ 𝑔𝑔𝑚𝑚−2𝑔𝑔→∞
𝑔𝑔𝑚𝑚−2

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Theorem:
𝑁𝑁 𝑚𝑚, 𝑔𝑔
𝑀𝑀𝑀𝑀𝑀𝑀 𝑚𝑚, 𝑔𝑔
lim
= lim
= 𝑉𝑉𝑉𝑉𝑉𝑉 𝑃𝑃 .
𝑔𝑔→∞ 𝑔𝑔𝑚𝑚−2𝑔𝑔→∞𝑔𝑔𝑚𝑚−2• For small values of m, the volume of P is computed:
1 1
1
71
1,633
12,256,093,,,,,,…
3 12 135 81,648 36,288,000 3,923,023,104,000

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Theorem:
N(m,g) ≤ MED(m,g + m – 1) for all g ≥ 0 and m ≥ 2.

Elie Alhajjar

United States Military Academy

Combinatorial Structure• Theorem:
N(m,g) ≤ MED(m,g + m – 1) for all g ≥ 0 and m ≥ 2.

Equality holds when m is prime and g >Elie Alhajjar(𝑚𝑚−1)(𝑚𝑚−2).
2

United States Military Academy

The Case m = 4 (continued)

Elie Alhajjar

United States Military Academy

The Case m = 4 (continued)

N(4,g) =Elie Alhajjar

𝑔𝑔2𝑔𝑔+122𝑔𝑔2𝑔𝑔
7+ −12212𝑔𝑔2
𝑔𝑔
1+ −
122
32𝑔𝑔
𝑔𝑔
1+ −
122
4United States Military Academy

The Case m = 4 (continued)

N(4,g) =Elie Alhajjar

𝑔𝑔2
𝑔𝑔+122𝑔𝑔2
𝑔𝑔
7+ −
122
12𝑔𝑔2
𝑔𝑔
1+ −
122
32𝑔𝑔
𝑔𝑔
1+ −
122
4MED(4,g) =𝑔𝑔2
12𝑔𝑔2
1−1212𝑔𝑔2
1−1232𝑔𝑔
1+
124United States Military Academy

The Case m = 4 (continued)

N(4,g) =Elie Alhajjar

𝑔𝑔2
𝑔𝑔+
1222𝑔𝑔
𝑔𝑔
7+ −
122
122𝑔𝑔
𝑔𝑔
1+ −
1223𝑔𝑔2
𝑔𝑔
1+ −122
4MED(4,g) =

𝑔𝑔2
12𝑔𝑔2
1−
12122
𝑔𝑔
1−
123
𝑔𝑔2
1+
124p(g) =

𝑔𝑔2
5𝑔𝑔
+ +1
1212𝑔𝑔2
𝑔𝑔
1+ −121262𝑔𝑔
5𝑔𝑔
1+ −121262
𝑔𝑔
𝑔𝑔
+
12122
𝑔𝑔
𝑔𝑔
1+ +
12122
𝑔𝑔2
5𝑔𝑔
1+ +
12122
𝑔𝑔2
𝑔𝑔
2+ −
121232𝑔𝑔
5𝑔𝑔
1+ +12123United States Military Academy

Special Results

Elie Alhajjar

United States Military Academy

Special Results• N(4,g) = number of partitions of g + 6 into 3 parts such that the ith part is greater than i

Elie Alhajjar

United States Military Academy

Special Results• N(4,g) = number of partitions of g + 6 into 3 parts such that the ith part is greater than i• MED(4,g) = number of partitions of g + 3 into 3 distinct parts.

Elie Alhajjar

United States Military Academy

Future Directions

Elie Alhajjar

United States Military Academy

Future Directions• Strong & Weak Genus Conjectures:N(g) ≥ N(g – 1) + N(g – 2) for all g ≥ 2 & N(g) ≥ N(g – 1) for all g ≥ 1

Elie Alhajjar

United States Military Academy

Future Directions• Strong & Weak Genus Conjectures:
N(g) ≥ N(g – 1) + N(g – 2) for all g ≥ 2 & N(g) ≥ N(g – 1) for all g ≥ 1• Nondecreasing Sequences:N(m,g) ≥ N(m,g – 1) & MED(m,g) ≥ MED(m,g – 1) for all m ≥ 2Elie Alhajjar

United States Military Academy

Future Directions• Strong & Weak Genus Conjectures:
N(g) ≥ N(g – 1) + N(g – 2) for all g ≥ 2 & N(g) ≥ N(g – 1) for all g ≥ 1• Nondecreasing Sequences:N(m,g) ≥ N(m,g – 1) & MED(m,g) ≥ MED(m,g – 1) for all m ≥ 2• Other types of numerical semigroups:
One can define symmetric, pseudo-symmetric, Arf, irreducible, saturated, etc…
numerical semigroups and ask the same questions!!
What properties does a ‘generic’ numerical semigroup have, for large g???

Elie Alhajjar

United States Military Academy

Future Directions

Elie Alhajjar

United States Military Academy