CHOMP ON NUMERICAL SEMIGROUPS
IGNACIO GARCÍA-MARCO AND KOLJA KNAUER

arXiv:1705.11034v2 [math.CO] 13 Mar 2018

A BSTRACT. We consider the two-player game chomp on posets associated to numerical semigroups and show that the analysis of strategies for chomp is strongly related to classical properties
of semigroups. We characterize which player has a winning-strategy for symmetric semigroups,
semigroups of maximal embedding dimension and several families of numerical semigroups generated by arithmetic sequences. Furthermore, we show that which player wins on a given numerical
semigroup is a decidable question. Finally, we extend several of our results to the more general
setting of subsemigroups of N × T , where T is a finite abelian group.

1. I NTRODUCTION
Let P be a partially ordered set with a global minimum 0. In the game of chomp on P (also
known as poset game), two players A and B alternatingly pick an element of P . Whoever is
forced to pick 0 loses the game. A move consists of picking an element x ∈ P and removing its
up-set, that is, all the elements that are larger or equal to x. The type of questions one wants to
answer is: for a given P , has either of the players a winning strategy? And, if yes, can a strategy
be devised explicitly? A crucial, easy, and well-known observation with respect to these questions
is the following one.
Remark 1.1. If P has a global maximum 1 and 1 6= 0 (that is, P 6= {0}), then player A has
a winning strategy. This can be proved with an easy strategy stealing argument. Indeed, if A
starting with 1 cannot be extended to a winning strategy, there is a devastating reply x ∈ P . But
in this case, A wins starting with x.
One of the most well-known and probably oldest games that is an instance of chomp is Nim [3],
where P consists of a disjoint union of chains plus a global minimum. The first formulation in
terms of posets is due to Schuh [24], where the poset is that of all divisors of a fixed number N ,
with x below y when y|x. A popular special case of this is the chocolate-bar-game introduced by
Gale [12]. The a × b-chocolate-bar-game coincides with chomp on P := {(n, m) | 0 ≤ n < a,
0 ≤ m < b} partially ordered by (n, m) ≤ (n0 , m0 ) if and only if n ≤ n0 and m ≤ m0 . Since
(P, ≤) has (a − 1, b − 1) as global maximum, the strategy stealing argument of Remark 1.1 yields
that player A has a winning strategy for chomp on P . Explicit strategies for player A are known
only in very particular cases including when a = b or a ≤ 2. The problem remains open even
in the 3 × b case. There is a rich body of research on chomp with respect to different classes of
posets. For more information on the game and its history, we refer to [4, 10].
In this work, we investigate chomp on a family of posets arising from additive semigroups
of natural numbers instead of their multiplication as in Schuh’s game. More precisely, let S =
ha1 , . . . , an i denote the semigroup generated by positive integers a1 , . . . , an , that is,
S = ha1 , . . . , an i = {x1 a1 + · · · + xn an | x1 , . . . , xn ∈ N}.
The semigroup S induces on itself a poset structure (S, ≤S ) whose partial order ≤S is defined by
x ≤S y ⇐⇒ y − x ∈ S.
This poset structure on S has been considered in [11, 15] to study algebraic properties of its
corresponding semigroup algebra, and in [5, 6, 7] to study its Möbius function. We observe that
Key words and phrases. Numerical semigroup, Apéry set, Frobenius number, Cohen-Macaulay type, Chomp,
poset game.
1

2

I. GARCÍA-MARCO AND K. KNAUER

there is no loss of generality in assuming that a1 , . . . , an are relatively prime. Indeed, setting
d := gcd(a1 , . . . , an ) and S 0 := ha1 /d, . . . , an /di, then (S, ≤S ) and (S 0 , ≤S 0 ) are isomorphic
posets. From now on we will assume that S is a numerical semigroup, that is, it is generated by
relatively prime integers.
One of the peculiarities of chomp on posets coming from numerical semigroups is that after
player A’s first move, the remaining poset is finite (see Remark 2.3). In particular, this implies
that every game is finite and either A or B has a winning strategy.
Results and structure of the paper: In Section 2 we introduce some elements of the theory of
numerical semigroups. In particular, we relate the Apéry sets to the first moves of chomp and
show that B has a winning strategy in all symmetric semigroups (Theorem 2.4). Section 3 is
devoted to numerical semigroups of maximal embedding dimension. We characterize those semigroups in the class for which A has a winning strategy (Theorem 3.4) and describe an explicit
winning strategy. In Section 4 we discuss numerical semigroups that are generated by generalized arithmetic sequences. We characterize, when the smallest generator is a winning move for
A (Proposition 4.2) and classify those semigroups in the class, that have three generators and admit a winning strategy for A (Theorem 4.4). In Section 5 we consider semigroups generated by
intervals. We characterize when A has a winning strategy for S = ha, a + 1, . . . , 2a − 3i with
a ≥ 4 (Proposition 5.4) and S = h3k, 3k + 1, . . . , 4ki with k odd (Proposition 5.1). In Section 6
we show, that if A has a winning strategy on S, then the smallest winning first move is bounded
by a function of the number of gaps and the Frobenius number of S (Theorem 6.5). In particular,
which player wins on a given semigroup is a decidable question. Finally, in Section 7, we investigate to what extent the game of chomp can be generalized to other algebraically defined posets.
In particular, we extend the decidability result (Theorem 7.10) as well as the result on symmetric
semigroups (Theorem 7.9) to the more general setting of numerical semigroups with torsion, that
is, subsemigroups of N × T , where T is a finite abelian group. We conclude the paper with some
questions in Section 8.
2. S YMMETRIC NUMERICAL SEMIGROUPS
One of the most studied families of numerical semigroups is the family of symmetric numerical semigroups. This family contains the family of complete intersection semigroups and is an
important subfamily of irreducible semigroups (see, for example, [20, 21]). Symmetric numerical
semigroups turn out to be also interesting in the study of affine monomial curves; in particular,
Kunz [15] proved that a numerical semigroup S is symmetric if and only if its corresponding
one-dimensional semigroup algebra K[S] = K[ts | s ∈ S] is Gorenstein.
The goal of this short section is to prove that whenever S is symmetric, then player B has a
winning strategy. One of the key points to obtain this result will be Remark 1.1.
We will now recall some basic results and definitions about numerical semigroups, for a detailed
exposition on this topic we refer the reader to [19, 22]. For a numerical semigroup S, the Frobenius
number g = g(S) is the largest integer not in S. The semigroup S is symmetric if
S ∪ (g − S) = Z,
where g − S = {g − s | s ∈ S}. In other words, S is symmetric if and only if for every x ∈ Z
either x ∈ S or g − x ∈ S.
For a semigroup S we set PF = {x ∈
/ S | x + s ∈ S for all s ∈ S \ {0}}. The elements of PF
are usually called pseudo-Frobenius numbers and the number of elements of PF is called the type
of S and denoted by type(S) (it coincides with the Cohen-Macaulay type of the corresponding
semigroup algebra K[ts | s ∈ S], where K is any field). We notice that g is always a pseudoFrobenius number. Moreover, by [11, Proposition 2] S is symmetric if and only if PF = {g}, or
equivalently, when the type of S is 1.

CHOMP ON NUMERICAL SEMIGROUPS

3

Given a ∈ S, the Apéry set of S with respect to a is defined as
Ap(S, a) = {s ∈ S | s − a ∈
/ S}.
This set, which is a complete set of residues modulo a, contains relevant information about the
semigroup. The following result illustrates how to obtain the set of pseudo-Frobenius numbers
from an Apéry set.
Proposition 2.1. [11, Proposition 7] Let S be a numerical semigroup and a ∈ S. Then, the
following conditions are equivalent for any x ∈ Z:
• x is a pseudo-Frobenius number of S, and
• x + a is a maximal element of Ap(S, a) with respect to the partial order ≤S .
In particular, the following corollary holds.
Corollary 2.2. Let S be a numerical semigroup and a ∈ S. The number of maximal elements of
Ap(S, a) with respect to ≤S does not depend on the a ∈ S chosen and coincides with type(S).
Going back to chomp, the following remark will be essential in the sequel and establishes a nice
connection between chomp and the theory of numerical semigroups.
Remark 2.3. Whenever player A’s first move is a ∈ S, then the remaining poset is exactly
Ap(S, a).
This remark together with Corollary 2.2 and Remark 1.1 yields the following.
Theorem 2.4. If S is a symmetric numerical semigroup, then player B has a winning strategy for
chomp on S.
Proof. No matter the first move of A, the remaining poset has a global maximum because type(S) =
1. Hence, Remark 1.1 yields the result.

We observe that the proof of Theorem 2.4 is not constructive. The task of determining a winning
strategy for B in this context seems a very difficult task. Indeed, we will argue now that it is at
least as difficult as providing a winning strategy for A in the a × b-chocolate-bar-game, which,
as mentioned in the introduction, remains an unsolved problem even for a = 3. Namely, if S
is symmetric, to describe a winning strategy for B, one has to exhibit a good answer for B for
every first move of A. It is well known (and easy to check) that every two-generated numerical
semigroup is symmetric. Let us consider S = ha, bi with a, b relatively prime and assume that A
starts picking ac with 1 ≤ c ≤ b. The remaining poset is
Ap(S, ac) = {λa + µb | 0 ≤ λ < c, 0 ≤ µ < a},
and, for every 0 ≤ λ, λ0 < c, 0 ≤ µ, µ0 < a, we have that λa + µc ≤S λ0 a + µ0 c if and only if
λ ≤ λ0 , µ ≤ µ0 . Hence, the remaining poset is isomorphic to the a × c chocolate bar. Therefore,
providing an explicit winning strategy for B in this poset is equivalent to finding winning strategies
for A in chomp on the a × c chocolate bar for every 1 ≤ c ≤ b.
3. N UMERICAL SEMIGROUPS OF MAXIMAL EMBEDDING DIMENSION
Given a numerical semigroup S, its smallest nonzero element is usually called its multiplicity
and denoted by m(S). It turns out that every numerical semigroup has a unique minimal generating set, the size of this set is the embedding dimension of S and is denoted by e(S). It is easy
to prove that m(S) ≥ e(S). Whenever m(S) = e(S) we say that S has maximal embedding
dimension. In this section we study chomp on posets coming from numerical semigroups with
maximal embedding dimension.
These semigroups have been studied by several authors, see, for instance, [1, 23]. There exist
several characterizations for this family of semigroups, in particular we use the following ones,
which can be found or easily deduced from the ones in [22, Chapter 2].

4

I. GARCÍA-MARCO AND K. KNAUER

Proposition 3.1. Let S be a numerical semigroup and let a1 < · · · < an be its unique minimal
system of generators. Then the following properties are equivalent.
(a) S has maximal embedding dimension,
(b) Ap(S, a1 ) = {0, a2 , . . . , an },
(c) type(S) = a1 − 1,
(d) x + y − a1 ∈ S for all x, y ∈ S \ {0},
(e) every element b ∈ S \ {0} can be uniquely written as b = λa1 + ai with λ ∈ N and
i ∈ {1, . . . , n}.
For this family of posets we do not only characterize which player has a winning a strategy but
also we provide an explicit winning strategy in each case.
We start with a result about Apéry sets that we will need in the sequel. For every numerical
semigroup, whenever a, b ∈ S and a ≤S b, it is easy to check that Ap(S, a) ⊂ Ap(S, b). The
following result furthermore describes the difference between these two sets.
Proposition 3.2. [9, Lemma 2] Let S be a numerical semigroup and a, b ∈ S such that a ≤S b.
Then,
Ap(S, b) = Ap(S, a) ∪ (a + Ap(S, b − a)),
and it is a disjoint union.
In particular, from this result and Proposition 3.1.(b) one easily derives the following result.
Lemma 3.3. Let S = ha1 , . . . , am i be a maximal embedding dimension numerical semigroup with
multiplicity m = a1 . Then,
Ap(S, λm) = {µm, µm + ai | 0 ≤ m < λ, 2 ≤ i ≤ m};
and the set of maximal elements of Ap(S, λm) with respect to ≤S is {(λ − 1)m + ai | 2 ≤ i ≤ m}.
Now, we can proceed with the proof of the main result of this section.
Theorem 3.4. Let S be a maximal embedding dimension numerical semigroup with multiplicity
m. Player A has a winning strategy for chomp on S if and only if m is odd.
Proof. Let m = a1 < a2 < · · · < am be the minimal set of generators of S.
(⇐) If m is odd and player A picks m, then the remaining poset is Ap(S, m) = {0, a2 , . . . , am }
which has 0 as minimum and m − 1 non-comparable (with respect to ≤S ) maximal elements (see
Figure 1). Since m − 1 is even, it is easy to see that player B loses this game.
a2

a3

...

am

0

F IGURE 1. The poset Ap(S, m).
(⇒) To prove this implication we divide S into layers {Sλ }λ∈N , being S0 := {0} and Sλ =
{(λ − 1)m + ai , | 1 ≤ i ≤ m} for λ ≥ 1. By Lemma 3.3 we have that Ap(S, λm) = (∪µ≤λ Sµ ) \
{λm} and has exactly m − 1 maximal elements, namely those of Sλ \ {λm}.
To prove that B has a winning strategy, we show that whenever A’s first move is an element of
Sλ , then B has an answer in Sλ so that:
(a) the remaining poset P satisfies that ∪µ<λ Sµ ⊆ P ( ∪µ≤λ Sµ , and
(b) A is eventually forced to pick an element from a layer Sµ with µ < λ.

CHOMP ON NUMERICAL SEMIGROUPS

5

We separate two cases. If A picks x = λm, then the remaining poset is exactly Ap(S, λm).
This poset has m − 1 maximal elements which are exactly the elements of Sλ \ {λm}. Since m − 1
is odd, B can force A to pick an element of a layer µ < λ by just choosing elements from Sλ . If
A picks x = (λ − 1)m + ai with i ≥ 2, then λa1 ∈ Ap(S, x). Now B picks λa1 and the remaining
poset is exactly Ap(S, λm) \ {x}. This poset has m − 2 elements of Sλ and they are all maximal.
Since m − 2 is even, B can force A to pick an element of a layer µ < λ. Iterating this strategy
yields a winning strategy for B.

As we mentioned before, this result does not only characterize who has a winning strategy but
also provides explicit winning strategies.
4. N UMERICAL SEMIGROUPS GENERATED BY GENERALIZED ARITHMETIC SEQUENCES
A generalized arithmetic sequence is set of positive integers of the form a < ha + d < · · · <
ha + kd for some a, d, k, h ∈ Z+ . Since such a sequence generates a numerical semigroup if and
only if gcd{a, d} = 1, from now on we assume that this is the case. Several authors have studied
semigroups generated by generalized arithmetic sequences (see, for example [8, 17, 25]) as well
as their relation with monomial curves (see, for example, [2, 26]). This section concerns chomp
on semigroups generated by a generalized arithmetic sequence of positive integers. The main
result of this section is Theorem 4.4, where we characterize which player has a winning strategy
for chomp on S when k = 2.
A first easy observation is that {a, ha + d, . . . , ha + kd} minimally generates S if and only if
k < a; otherwise S = ha, ha + d, . . . , a(h + d) − di. Thus, from now on we assume that k < a.
We observe that a semigroup S generated by a generalized arithmetic sequence is of maximal
embedding dimension if and only if k = a − 1. Hence, when k = a − 1, Theorem 3.4 applies here
to conclude that A has a winning strategy if and only if a is odd.
We are now going to characterize when a is a winning first move for A in the chomp game;
for this purpose we study Ap(S, a). Although the description of Ap(S, a) is due to Selmer [25]
(see also [17]), here we include a slightly refined version of his result where we also describe the
ordering ≤S on Ap(S, a).
Proposition 4.1. Let S = ha, ha+d, . . . , ha+kdi with a, k, d, h ∈ Z+ , k < a and gcd{a, d} = 1.
Then,
 

i
Ap(S, a) =
ha + id | 0 ≤ i < a .
k
Moreover, if we take t ≡ (a − 1) mod k, t ∈ {1, . . . , k}, denote xj,` := j(ha + kd) − kd + `d for
j, ` ∈ N, and set

if j = 0,  
 {x0,k }
,
{xj,` | 1 ≤ ` ≤ k} if 1 ≤ j < a−1
Aj :=
k

a−1
{xj,` | 1 ≤ ` ≤ t} if j = k ;
 
then we have that Ap(S, a) is the disjoint union of Aj with 0 ≤ j ≤ a−1
. In addition, if
k
xj,` ∈ Aj , xj 0 ,`0 ∈ Aj 0 ; then,
xj,` <S xj 0 ,`0 ⇐⇒ j < j 0 and ` ≥ `0 .
In particular, from
 Proposition 4.1 one gets that the set of maximal elements of Ap(S, a) is
Aj with j = a−1
. According to Corollary 2.2, this gives that type(S) = t being t ≡ a −
k
1 (mod k) and t ∈ {1, . . . , k}. In particular, S is symmetric if and only if a ≡ 2 (mod k) or,
equivalently, if a − 2 is a multiple of k (this result was already known, see Estrada and López [8],
and Matthews [17]). Moreover, if k is even, then type(S) is even if and only if a is odd.
The following result characterizes when a is a winning first move for chomp on a numerical
semigroup generated by a generalized arithmetic sequence.

6

I. GARCÍA-MARCO AND K. KNAUER

51

53

32

13

34

15

36

17

38

19

0

F IGURE 2. The poset Ap(S, 11) with S = h11, 13, 15, 17, 19i.
Proposition 4.2. Let S = ha, ha + d, . . . , ha + kdi be a numerical semigroup. Then, a ∈ S is a
winning first move in the chomp game on (S, ≤S ) if and only if a is odd and k is even.
To prove this result, we will use Proposition 4.1, together with the following Lemma (which is
an improvement of [10, Fact 1.5]):
Lemma 4.3. Let P be a finite poset with a minimum element 0 and let ϕ : P → P be such that
(a) ϕ ◦ ϕ = idP (that is, ϕ is an involution),
(b) if x ≤ ϕ(x), then x = ϕ(x),
(c) if x ≤ y, then ϕ(x) ≤ ϕ(y) or x ≤ ϕ(y), and
(d) the set F := {x ∈ P | ϕ(x) = x} of fixed points of ϕ is a down-set of P (that is, F is a
subset of P such that if x ∈ F and y ≤ x ⇒ y ∈ F ).
Then, A has a winning strategy on P if and only if A has a winning strategy on F .
Proof. Assume that player A has a winning strategy on F and let us exhibit a winning strategy on
P . Player A starts by picking a winning move in F . Now, whenever B picks x ∈ P , we separate
two cases.
Case x ∈ F . A replies in F following his winning strategy on F .
Case x ∈
/ F . A replies ϕ(x) ∈
/ F.
We claim that this gives a strategy for A. Indeed, since F is a down-set, picking an element
x∈
/ F at any stage of the game does not alter the remaining elements of F . Moreover, conditions
(a), (b) and (c) justify that at any state of the game, whenever B picks an element x ∈
/ F , the
element ϕ(x) is in the remaining poset and, hence, it can be removed by A in the following move.
Since the poset is finite, player B cannot pick elements not belonging to F forever and thus, will
be forced to play in F . Eventually B will be forced to take the minimum because A has a winning
strategy on F .
If A does not have a winning strategy on P , then B has one (because P is finite). A similar
argument to the previous one gives a winning strategy for B, completing the proof.

of Proposition 4.2. By assuming that A picks a, we have that the resulting poset is (Ap(S, a), ≤S ).
If k is odd, then for B to pick ha + kd is a winning move since the resulting poset is P =
{0} ∪ {ha + d, . . . , ha + (k − 1)d} and P \ {0} is an antichain (a set of pairwise incomparable
elements) with an even number of elements (see Figure 3).
Suppose now that k is even. Following the notation of Proposition 4.1, we first assume that
a is odd, that is, t is even, and consider the involution ϕ : Ap(S, a) → Ap(S, a) defined as
ϕ(xj,` ) = xj,`0 , with

if j = 0,
 k
0
` + 1 if ` is odd,
` =

` − 1 if ` is even.

CHOMP ON NUMERICAL SEMIGROUPS

ha + d

ha + 2d

7

ha + (k − 2)d ha + (k − 1)d

0

F IGURE 3. An even antichain with k − 2 elements and a global minimum.
A simple argument yields that conditions (a), (b) and (c) in Lemma 4.3 are satisfied and that the
only fixed point of ϕ is 0 (see Figure 4). Thus, a direct application of Lemma 4.3 yields that A
has a winning strategy.
ϕ
xs,1

x1,1

ϕ
xs,2

xs,t−1 xs,t

ϕ

ϕ

ϕ

ϕ
x1,2

x1,k
ϕ(0) = 0

F IGURE 4. Involution ϕ : Ap(S, a) → Ap(S, a) in the proof of Proposition 4.2
(with s := d a−1
e, a odd and k even).
k
 
If a is even, that is, t is odd, we are going to show that y = xs,t with s = a−1
is a winning
k
move for B. Indeed, the same involution ϕ as before defined in Ap(S, a) \ {y} proves that B has
a winning strategy in this poset. This proves the result.

As a consequence of this result, one can completely determine who wins chomp on S when S
is generated by a generalized arithmetic sequence of three elements.
Theorem 4.4. Let h, a, d ∈ Z+ with a, d relatively prime integers and consider S := ha, ha +
d, ha + 2di. Player A has a winning strategy for chomp on S if and only if a is odd.
Proof. We set t := type(S). By Proposition 4.1, we have that t ∈ {1, 2} and t ≡ a − 1 (mod 2).
Hence, S is symmetric if and only if a is even and, in this case, B has a winning strategy by
Theorem 2.4. Whenever a is odd, then Proposition 4.2 yields that a is a winning first move for
player A.

For three-generated numerical semigroups generated by a generalized arithmetic sequence we
have proved that either the multiplicity of the semigroup is a winning first move for A, or B has a
winning strategy. This is no longer the case for general three-generated numerical semigroups. for
instance, an exhaustive computer aided search shows that for S = h6, 7, 11i, the smallest winning
first move for A is 25, and for S = h6, 7, 16i the smallest winning first move for A is 20. It would
be interesting to characterize which player has a winning strategy when S is three generated.

8

I. GARCÍA-MARCO AND K. KNAUER

5. N UMERICAL SEMIGROUPS GENERATED BY AN INTERVAL
In this section we are going to study chomp on numerical semigroups generated by an interval
of positive integers, that is, when S = ha, . . . , a + ki for some a, k ∈ Z+ . These semigroups
were studied in detail in [14] and form a subfamily of those generated by a generalized arithmetic
sequence. Hence, the results obtained in the previous section are also valid in this context. That
is, a is a winning first move for A in S = ha, . . . , a + ki if and only if a is odd and k is even
(Proposition 4.2) and A wins in S = ha, a + 1, a + 2i if and only if a is odd (Theorem 4.4).
Moreover, S = ha, . . . , 2a − 1i is of maximal embedding dimension, thereby, in this case A has a
winning strategy if and only if a is odd (Theorem 3.4). Finally, the semigroups such that a − 2 is
a multiple of k, such as S = ha, . . . , 2a − 2i and S = ha, a + 1i, are symmetric and therefore B
has a winning strategy (Theorem 2.4).
In this section we will extend this list of results to two infinite families. Furthermore, we have
implemented an algorithm that receives as input a numerical semigroup S given by its generators
and a positive integer x, and tests if player A has a winning strategy with a first move less or equal
than x. Our implementation consists of an exhaustive brute force implementation that checks
for all y ∈ S, y ≤ x if player A has a winning strategy starting with y (we recall that after
the first move, the remaining poset is finite). Due to the large number of cases to consider, our
naive implementation can only handle instances where x is small in a reasonable time. However,
the computer search is used for solving one case of Proposition 5.4. Moreover, our experiments
provide computational evidence for what in in our opinion would be the next feasible questions to
attack, concerning chomp on numerical semigroups.
The following result shows that, in semigroups of the form S = h3k, 3k + 1, . . . , 4ki for k
odd, playing 3k + 1, the second generator, is a winning first move for A. Note that 3k, the first
generator, is not a winning move by Proposition 4.2. One member of this family after A picked
3k + 1 is displayed in Figure 5.
60
45

57

37

30

15

17

58

59

38

39

18

19

40

20

0

F IGURE 5. Ap(S, 16) for S = h15, 16, 17, 18, 19, 20i.
Proposition 5.1. Let k ≥ 3 and S = h3k, 3k + 1, . . . , 4ki. If k is odd, then 3k + 1 ∈ S is a
winning first move in the chomp game on (S, ≤S ).
We are going to prove this proposition by means of Lemma 4.3 together with the following
technical lemmas.
Lemma 5.2. Let S = h3k, 3k + 1, . . . , 4ki. Then,
Ap(S, 3k + 1) = {0, 3k, 6k, 9k} ∪ {3k + i, 7k + i, 11k + i | 2 ≤ i ≤ k}.
As a consequence, type(S) = k − 1.

CHOMP ON NUMERICAL SEMIGROUPS

9

Proof. We begin by observing that S = {3k, . . . , 4k} ∪ {6k, . . . , 8k} ∪ {x ∈ N | x ≥ 9k}. Let
A := {0, 3k, 6k, 9k} ∪ {3k + i, 7k + i, 11k + i | 2 ≤ i ≤ k}. Since A ⊂ S and has 3k + 1 elements,
to prove that A = Ap(S, 3k + 1) it suffices to observe that x − (3k + 1) ∈
/ S for all x ∈ A. The
set of maximal elements of A with respect to ≤S is {11k + i | 2 ≤ i ≤ k}. Thus, by Corollary 2.2
we have that type(S) = k − 1.

Lemma 5.3. Player B has a winning strategy in the poset (P, ≤) with P = {0} ∪ {xi,j | 1 ≤
i, j ≤ 3} and relations induced by
0 ≤ x1,j ,
for j = 1, 2, 3,
xi,j ≤ xi+1,j , for i = 1, 2,
j = 1, 2, 3,
xi,3 ≤ xi+1,2 , for i = 1, 2,
x3,1 ≤ x3,3 .
Proof. We will exhibit a winning answer for any first move of A in this poset (see Figure 6).
x3,3
x3,1

x3,2

x2,1

x2,2

x2,3

x1,1

x1,2

x1,3

0

F IGURE 6. The poset of Lemma 5.3.
• If A picks x1,1 , then B picks x3,2 and vice versa.
• If A picks x2,1 , then B picks x1,3 and vice versa.
• If A picks x3,1 , then B can either pick x1,2 or x2,3 and vice versa.
• If A picks x2,2 , then B picks x3,3 and vice versa.
Hence, B has a winning strategy.



of Proposition 5.1. Assume that k is odd. We consider ϕ defined as (see Figure 7).

for x ∈ {0, 3k, 6k, 9k, 4k − 1, 4k, 8k − 1, 8k, 12k − 1, 12k},
 x,
x + 1, for x ∈ {3k + i, 7k + i, 10k + i | 2 ≤ i ≤ k − 3, i even},
ϕ(x) =

x − 1, for x ∈ {3k + i, 7k + i, 10k + i | 3 ≤ i ≤ k − 2, i odd}.
With Lemma 5.2 it is easy to see that ϕ is an involution of Ap(S, 3k + 1). This involution satisfies
the hypotheses of Lemma 4.3. Hence, 3k + 1 is a winning move for A if and only if there is a
winning strategy for the second player in the poset (F, ≤S ), where F is the set of fixed points of
ϕ. But, F = {0, 3k, 6k, 9k, 4k − 1, 4k, 8k − 1, 8k, 12k − 1, 12k} and (F, ≤S ) is isomorphic to the
poset of Lemma 5.3. Thus, 3k + 1 is a winning move for player A.

As stated in the beginning of the section we know the behavior of chomp on S = ha, . . . , 2a−1i
and S = ha, . . . , 2a − 2i. The following result characterizes when A has a winning strategy for
chomp on S = ha, . . . , 2a − 3i.
Proposition 5.4. Let S = ha, a + 1, . . . , 2a − 3i with a ≥ 4. Player A has a winning strategy for
chomp on S if and only if a is odd or a = 6.

10

I. GARCÍA-MARCO AND K. KNAUER

ϕ

12k

ϕ
12k − 1

11k + 2

9k

ϕ

ϕ
8k − 1

7k + 2

6k

ϕ

ϕ
4k − 1

3k + 2

3k

8k

4k

0

F IGURE 7. Involution of Proposition 5.1.
Proof. If a is odd, we are under the hypotheses of Proposition 4.2 and a is a winning move for A.
If a = 4, then S = h4, 5i is symmetric and B has a winning strategy. For a = 6, an exhaustive
computer aided search shows that 36 is a winning first move for A, see Table 1.
From now on we assume that a is even and a ≥ 8 and we are going to describe a winning
strategy for B. First, we observe that for all x ∈ Z+ we have that x ∈ S ⇐⇒ x ≥ a and
x∈
/ {2a − 2, 2a − 1}. We partition S into intervals Si := [a + i(2a + 1), 3a + i(2a + 1)] ∩ S for
all i ∈ N and we denote by (i, x) the element a + i(2a + 1) + x ∈ Si for all x ∈ {0, . . . , 2a} (see
Figure 8).

(0, a)

(0, a + 1)

(0, 0)

(0, 1)

S0

(0, 2a)

(0, 2a − 3)

(0, 2a − 2)

(0, a − 3)

Si , i ≥ 1

(i, a)

(i, 0)

(i, a + 1)

(i, 1)

(0, 2a − 1)

(i, 2a − 3)

(i, a − 3)

(i, 2a)

(i, 2a − 2) (i, 2a − 1)

(i, a − 2)

(i, a − 1)

F IGURE 8. S0 and Si for i ≥ 1.
We are going to exhibit a winning strategy for B that respects the following rules.
(a) A is always forced to be the first to pick an element in Si for all i (and will be finally forced
to pick 0 ∈ S).
(b) After A picks the first element in Si , B answers with an element in Si and the remaining
poset P has at most one element in ∪j>i Sj .
(c) B avoids that after his move, the remaining poset P satisfies that (i, 0), . . . , (i, a − 4) ∈
/P
and (i, a − 3) ∈ P for every i.

CHOMP ON NUMERICAL SEMIGROUPS

11

Assume that A picks an element for the first time in Si for some i.
(1) If A picks (i, 0), then B answers (i, x) for any x ∈ {2, . . . , a − 2}; and vice versa. All
these moves leave the remaining poset
[
P = {0} ∪
Sj ∪ {(i, y) | 1 ≤ y ≤ a − 1, y 6= x}.
j<i

Hence, P ∩ Si is just an antichain of a − 2 elements; since a − 2 is even, B can easily
satisfy (a). Moreover, in order to satisfy (c), in the next move player B can pick (i, a − 3)
if it had not been removed before.
(2) If A picks (i, a − 1), then B answers (i, 2). These moves leave the remaining poset
[
P = {0} ∪
Sj ∪ {(i, y) | 0 ≤ y ≤ a + 1, y ∈
/ {2, a − 1}}.
j<i

Hence, P ∩ Si is the poset of Figure 9. Since a − 4 is even, B can easily force A to be
the first to pick an element from Sj for some j < i. Moreover, player B can always assure
condition (c) in his winning strategy; indeed, since a ≥ 8, player B can pick (i, a − 3)
after the first time that A picks (i, y) for some y ∈ {3, . . . , a − 4, a − 2}.
(i, a)

(i, 0)

(i, a + 1)

(i, 1)

(i, 3)

(i, a − 2)

F IGURE 9. P ∩ Si in case (2).
(3) If A picks (i, 1), then B answers (i, 2a) and vice versa. These moves leave the remaining
poset
[
P = {0} ∪
Sj ∪ {(i, y) | y ∈ {0, 2, 3, . . . , a − 1, a, 2a − 1}}.
j<i

Hence, P ∩ Si is the poset of Figure 10. Again B can easily satisfy (a) and (c).
(i, 2a − 1)

(i, a)

(i, 0)

(i, 2)

(i, a − 2)

(i, a − 1)

F IGURE 10. P ∩ Si in case (3).
(4) If A picks (i, a), then B answers (i, x) for any x ∈ {a + 2, . . . , 2a − 2} and vice versa.
These moves leave the remaining poset
[
P = {0} ∪
Sj ∪ (Si \ {(i, a), (i, 2a), (i, x)}.
j<i

Hence, P ∩ Si is the poset of Figure 11. We are now providing a strategy for B satisfying
(a) and (c). We divide the elements of P ∩ Si into two sets, L1 := {(i, y) ∈ P ∩ Si | y ≤
a − 1} and L2 := {(i, y) ∈ P ∩ Si | y ≥ a}. We observe that both L1 and L2 are of even
size. If A picks an element from L2 , then so does B. If A picks an element from L1 , then

12

I. GARCÍA-MARCO AND K. KNAUER

B picks an element from L1 such that after the two moves, every element of L2 is removed
(this can always be achieved by either picking (i, 1) or (i, 3)).
The second time that A picks an element from L1 , B picks (i, a − 3) if it has not been
removed, yet. This assures (c).
(i, a + 1)

(i, 0)

(i, a + 3)

(i, 1)

(i, 2)

(i, 2a − 3)

(i, 2a − 2) (i, 2a − 1)

(i, a − 3)

(i, 3)

(i, a − 2)

(i, a − 1)

F IGURE 11. P ∩ Si in case (4) for x = a + 2.
(5) If A picks (i, a + 1), then B answers (i, a + 3) and vice versa. These moves leave the
remaining poset
[
P = {0} ∪
Sj ∪ (Si \ {(i, a + 1), (i, a + 3)}.
j<i

Hence, P ∩ Si is the poset of Figure 12. Let us see how B can force (a) and (c). If A picks
(i, 1) then B answers (i, 2a) and vice versa; this leaves the poset in the same situation of
case (3). If A picks (i, 0); then B can pick (i, y) for any y ∈ {2, . . . , a − 1} and vice versa;
in this case the poset is left as in case (1). If A picks (i, a); then B can pick (i, y) for any
y ∈ {a + 2, a + 4, . . . , 2a − 1} and vice versa; in this case the poset is left similar to case
(4) but with 2 elements less in L2 , the strategy for B described in (4) also works here.
(i, 2a)

(i, a + 4)

(i, a + 2)

(i, a)

(i, 0)

(i, 1)

(i, 2)

(i, 3)

(i, 4)

(i, 2a − 1)

(i, a − 1)

F IGURE 12. P ∩ Si in case (5).
(6) If A picks (i, 2a − 1), then we take λ as the minimum value such that (i + 1, λ) is in the
current poset. We separate two cases:
(6.1) If λ does not exist or λ ≥ a − 2, then B picks (i, a) and the remaining poset is
[
P = {0} ∪
Sj ∪ (Si \ {(i, a), (i, 2a − 1), (i, 2a)}.
j<i

Hence, P ∩ Si is the poset of Figure 13. In this case, the same strategy as in (4) works
here to guarantee (a) and (c).
(6.2) If λ < a − 2, then λ < a − 3 by condition (c) and B can answer (i, a + λ + 2) because
a + λ + 2 < 2a − 1; the remaining poset is
[
P = {0} ∪
Sj ∪ (Si \ {(i, a + λ + 2), (i, 2a − 1)} ∪ {(i + 1, λ)}.
j<i
0

Hence, P := P ∩ (Si ∪ Si+1 ) is the poset of Figure 14. We partition P 0 into three
sets; L1 := {(i, y) ∈ P 0 | 0 ≤ y ≤ a − 1}, L2 := {(i, y) ∈ P 0 | a ≤ y ≤ 2a − 2} and

CHOMP ON NUMERICAL SEMIGROUPS

(i, a + 1)

(i, 0)

(i, 1)

13

(i, 2a − 2)

(i, a + 2)

(i, 2)

(i, a − 1)

(i, 4)

F IGURE 13. P ∩ Si in case (6.1).
L3 := {(i, 2a), (i + 1, λ)}. Each of these three sets has an even number of elements
and whenever A picks an element from Li , then B can pick an element from Li such
that ∪j>i Lj is completely removed. The only exception to this is if A picks (i, a − 1),
but in this case B can pick (i, 2) and we are in case (2).
(i, 2a)

(i, a)

(i, 0)

(i + 1, λ)

(i, a + 1)

(i, 1)

(i, a + λ + 1)

(i, λ + 1) (i, λ + 2)

(i, a + λ + 3)

(i, λ + 3)

(i, 2a − 2)

(i, a − 2)

(i, a − 1)

F IGURE 14. P ∩ (Si ∪ Si+1 ) in case (6.2).
Thus, player B has a winning strategy on (S, ≤S ) when S = ha, . . . , 2a − 3i with a even and
a ≥ 8 and the proof is finished.

Condition (c) in the proof of Proposition 5.4 might seem artificial but it is crucial for the proof.
Indeed, if (i, 0), . . . , (i, a − 4) ∈
/ P , (i, a − 3) ∈ P and none of the players has picked an element
from Sj for all j < i; then (i − 1, 2a − 1) ∈ Si−1 is a winning move. In the proof, when we
consider a even and a ≥ 8, the only place where we use that a ≥ 8 is to assure in case (2) that
the winning strategy can respect condition (c). When a = 6 (and S = h6, 7, 8, 9i) this cannot be
guaranteed.
Remark 5.5. We illustrate in Table 1 which player has a winning strategy for interval generated
semigroups with small multiplicity. The notation B means that player B has a winning strategy
because
• S is symmetric (Theorem 2.4),
• S is of maximal embedding dimension and a even (Theorem 3.4), or
• k = a − 3 and a ≥ 8 is even (Proposition 5.4).
The notation Aj means that A has a winning strategy whose first move is j, because
• a odd and k is even (Proposition 4.2); the subcases a is odd and k = a − 1 are also
justified by Theorem 3.4,
• a = 3k and k odd (Proposition 5.1), or
• k = a − 3 and a is either odd or a = 6 (Proposition 5.4).
The notation B≤i means that an exhaustive computer search as mentioned in the beginning of
the section shows that B wins if A’s first move is ≤ i.
A particular property of the semigroups considered in Proposition 5.4 on which B wins, is that
they have type 2 and k is odd. Computational experiments suggest that when type(S) = 2 and
k odd, then B has a winning strategy in most cases, see Table 1. However, examples where this

14

I. GARCÍA-MARCO AND K. KNAUER
a\k
2
3
4
5
6
7
8
9
10
11
12
13
14

1
B
B
B
B
B
B
B
B
B
B
B
B
B

2

3

4

A3
B
A5
B
A7
B
A9
B
A11
B
A13
B

B
B
A36
B≤49
B
A10
B≤40
B
B≤43
B≤39
B

A5
B
A7
B≤43
A9
B
A11
B≤50
A13
B

5

B
B
B
B≤41
B≤40
B≤42
B
B≤46
B≤42

6

A7
B
A9
B≤47
A11
B≤44
A13
B

7

B
B
B
B≤43
B≤36
B≤37
B≤42

8

A9
B
A11
B≤50
A13
B≤49

9

B
B
B
B≤37
B≤40

10

11

12

13

A11
B
A13
B≤50

B
B
B

A13
B

B

TABLE 1. Winner of chomp on S = ha, . . . , a + ki for small values of a (see
Remark 5.5).

is not the case are given by S = h6, 7, 8, 9i and h9, 10, 11, 12i, where in the latter A wins playing
10, by Proposition 5.1. It would be interesting to completely characterize the cases where A has a
winning strategy in this setting.
Another observation coming from our results on S = ha, . . . , 2a − ci for 1 ≤ c ≤ 3 is that
for interval generated semigroups for which a + k is close to 2a, player A seems to win only in
the case guaranteed by Proposition 4.2, that is, a odd and k even. We formulate this suspicion as
Conjecture 8.1 in the last section.
6. A BOUND FOR THE FIRST MOVE OF A WINNING STRATEGY FOR A
The goal of this section is to prove that for any numerical semigroup S, there is a value ∆
depending only on the Frobenius number and the number of gaps of S such that if A has a winning
strategy, then A has a winning strategy with a first move ≤ ∆. The dependence is exponential in
the Frobenius number of the semigroup g(S) and doubly exponential in the number of gaps of the
semigroup, which we denote by n(S). We recall that the set of gaps of a numerical semigroup is
the finite set N (S) = N \ S = {x ∈ N | x ∈
/ S}.
The proof exploits the “local" behavior of the poset, in the sense that every down-set P 0 ( S
can be encoded by a pair (x, C), where x ∈ S and C ⊂ N (S). Indeed, all proper down-sets
P 0 ( S are finite and if we take x as the minimum integer in S \ P 0 , then we claim that P 0 satisfies
that
([0, x − 1] ∩ S) ⊆ P 0 ⊆ ([0, x − 1] ∪ (x + N (S))) ∩ S,
where x + N (S) := {x + n | n ∈ N (S)}. Since the inclusions ([0, x − 1] ∩ S) ⊆ P 0 ⊆ S are
trivial, let us prove that P 0 ⊆ ([0, x − 1] ∪ (x + N (S))). For this purpose, we take y ∈ P 0 such
that y ≥ x. Since P 0 is a down-set and x ∈
/ P 0 , we have x 6≤S y. Hence, y − x ∈ N (S) and the
claim is proved.
Thus, one can choose C ⊆ N (S) in such a way that P 0 = ([0, x − 1] ∩ S) ∪ (x + C). We
will denote this by P 0 ≡ (x, C). It is evident that the down-sets of (S, ≤S ) are in bijection
with the possible states of the chomp game, hence we encode the state of a game by elements of
S × P(N (S)), where P(N (S)) denotes the power set of N (S).
Let us illustrate this way of encoding the states of the chomp game with an example.
Example 6.1. Let S = h3, 5i, then the set of gaps of this semigroup is N (S) = {1, 2, 4, 7}.
Assume now that the first player picks 8 ∈ S, then the remaining poset is P1 := S \ (8 + S) =
Ap(S, 8) = {0, 3, 5, 6, 9, 10, 15}. We observe that [0, 7] ∪ (7 + N (S)) = [0, 7] ∪ {9, 10, 12, 15}
and, thus, P1 = ([0, 7] ∪ (8 + N (S))) ∩ S ≡ (8, N (S)).
If now player B picks 9, then the remaining poset is P2 := P1 \ (9 + S) = {0, 3, 5, 6, 10}. The
smallest element already picked is x = 8 and P2 = ([0, 7] ∪ (8 + {2})) ∩ S ≡ (8, {2}).

CHOMP ON NUMERICAL SEMIGROUPS

15

Assume that at some point of the game, the remaining poset is P ≡ (x, C) with x ∈ S and
C ⊆ N (S), and the player to play picks x0 ∈ P . The following lemma explains how the resulting
poset P 0 := P \ (x0 + S) is encoded.
Lemma 6.2. Let (S, ≤S ) be a numerical semigroup poset, P ≡ (x, C) ( S a down-set, and
x0 ∈ P . Then, P \ (x0 + S) is encoded by (x00 , D), where
(a) x00 = min{x, x0 },
(b) if x < x0 , then D ( C,
(c) if g(S) < x0 < x − g(S), then (z, D) = (x0 , N (S)).
Proof. By definition x00 is the smallest integer in S \ P , and equals min{x, x0 }. If x < x0 , then
P 0 = (x, C) \ (x0 + S) = (x, D) with D ⊆ C. Since x0 ∈ C \ D, then D ( C. To prove (c)
we observe that x0 < x, then by (a) we have that P = (x0 , D) for some d ⊂ N (S). To prove that
D = N (S) it suffices to verify that x0 + z ∈ P 0 for all z ∈ N (S). Indeed, since g(S) < x0 + z ≤
x0 + g(S) < x00 , then x0 + z ∈ P . Moreover x0 + z ∈
/ x0 + S, so x0 + z ∈ P \ (x0 + S) = P 0 and
(c) is proved.

The following technical lemma, whose proof is straightforward, will be useful in the proof of
the main result of this section.
Lemma 6.3. Let (S, ≤S ) be a numerical semigroup poset and take C ⊆ N (S) and x, x0 , y, y 0 >
g(S) such that y 0 − y = x0 − x. We set P ≡ (x, C) and Q ≡ (y, C). If x0 ∈ P and P \ (x0 + S) ≡
(min{x, x0 }, D), then:
• y 0 ∈ Q,
• Q \ (y 0 + S) ≡ (min{y, y 0 }, D).
Let us illustrate this result with an example.
Example 6.4. Consider again S = h3, 5i. We saw that if we take x = 8, x0 = 9 and C = N (S) =
{1, 2, 4, 7}, then (x, C) \ (x0 + S) = (x, {2}). Setting y = 8 + λ, y 0 = 9 + λ for some λ ∈ Z+ , it
is easy to see that (y, C) \ (y 0 + S) = (y, {2}).
Now we can proceed with the main result of this section.
Theorem 6.5. If A has a winning strategy for chomp on S, then A has a winning strategy with
n
first move less than 2g2 , where g = g(S) and n = n(S).
n

Proof. Denote ∆ := 2g2 and suppose that A has no winning strategy with first move less than ∆.
We will prove that A has no winning strategy.
For every x ∈ S we define the set Wx ⊆ P(N (S)) as follows: C ∈ Wx if and only if the first
player has a winning strategy on the chomp game on the poset (x, C). The elements C ∈ Wx can
be inductively characterized as follows: C ∈ Wx if and only if there exists y ∈ (x, C) such that if
(x, C) \ (y + S) = (z, D), then D ∈
/ Wz . Another interesting property of the sets Wx is that, if
x > g, then x is a winning first move for chomp on S if and only if N (S) ∈
/ Wx . In particular,
since A has no winning strategy with first move less than ∆, we have that N (S) ∈ Wx for all
g < x ≤ ∆.
The result is a direct consequence of the following claims.
Claim 1: Let x, y ∈ S : g < x < y ≤ ∆ and k ∈ Z+ such that Wx+i = Wy+i for all 0 ≤ i < k.
Then, z ∈ S is not a winning first move for player A for all z < y + k.
Proof of Claim 1. Assume there exists a winning first move z < y + k, and take z the minimum
possible. We observe that g < x < y ≤ ∆ ≤ z < y + k and that N (S) ∈
/ Wz = Wy+(z−y) with
z − y < k. Hence, Wy+(z−y) = Wx+(z−y) and N (S) ∈
/ Wx+(z−y) . This implies that x + z − y is a
winning first move but x + z − y < z, a contradiction.
Claim 2: There exist x, y ∈ S : g < x < y ≤ ∆ such that Wx+i = Wy+i for all 0 ≤ i < g
Proof of Claim 2. Since the power set of N (S) has 2n elements and N (S) ∈ Wx for all x : g <
n
x ≤ ∆; there are 22 −1 possible sets Wx for each x : g < x ≤ ∆. As a consequence, there are

16

I. GARCÍA-MARCO AND K. KNAUER
n

µ := 2(2 −1)g possible combinations of sets (Wx , Wx+1 , . . . , Wx+g−1 ) for all x : g < x ≤ ∆ − g.
Since µ < ∆ − 2g, there exist x, y : g < x < y ≤ ∆ − g such that (Wx , Wx+1 , . . . , Wx+g−1 ) =
(Wy , Wy+1 , . . . , Wy+g−1 ).
Claim 3: Take x, y as in Claim 2, then Wx+i = Wy+i for all i ∈ N.
Proof of Claim 3. By contradiction, we take k as the minimum value such that Wx+k 6= Wy+k . By
Claim 2 we have that k ≥ g.
Now, take C as an element in the symmetric difference of Wx+k and Wy+k with the minimum
number of elements. Assume without loss of generality that C ∈ Wx+k (and C ∈
/ Wy+k ).
Since C ∈ Wx+k , there is a winning move in the poset (x + k, C). Let x0 be this winning move.
We are going to prove that y 0 := x0 − x + y is a winning move for (y + k, C); this would be a
contradiction because C ∈
/ Wy+k and, hence, there is no winning move in this poset. We denote
0
(x + k, C) \ (x + S) ≡ (x00 , D); we have that
(i) x00 = min{x, x0 }, by Lemma 6.2.(a),
(ii) D ∈
/ Wx00 , because x0 is a winning answer in (x + k, C), and
0
(iii) x ≥ x + k − g (otherwise, by Lemma 6.2.(c), x00 = x0 and D = N (S) ∈
/ Wx0 , which
0
means that x is a winning first move; a contradiction to Claim 1).
We set y 00 := x00 − x + y, by Lemma 6.3 we have that (y + k, C) \ (y 0 + S) = (y 00 , D). To
prove that y 0 = x0 − x + y is a winning move for (y + k, C) is equivalent to see that D ∈
/ Wy00 .
We separate two cases:
(1) x0 > x + k: We have that x00 = x + k and D ( C by Lemma 6.2.(b); hence (y 00 , D) =
(y + k, D). Since D ( C and D ∈
/ Wx+k , we get that D ∈
/ Wy+k = Wy00 .
(2) x0 < x + k: We have that x00 = x0 . By (iii) we have that x ≤ x + k − g ≤ x0 < x + k, then
Wx0 = Wx+(x0 −x) = Wy+(x0 −x) = Wy+(y0 −y) = Wy0 and D ∈
/ Wy0 = Wy00 .
This proves Claim 3. Claims 1 and 3 conclude the proof.

Apart from this bound being probably far from optimal, its theoretic use is to prove the decidability of the problem of determining which player has a winning strategy. Indeed, this result
yields a (non-efficient) algorithm for this problem: it suffices to try all possible games with a first
move ≤ ∆ to decide if player A has a winning strategy. It would be nice to have better bounds on
a first move for A which uses in a deeper way the semigroup structure of the poset.
Indeed, it is worth pointing out that the proof only exploits the local behavior of the poset and,
hence, such a result can be obtained for infinite posets with similar behavior. This is the purpose
of the following section.
7. N UMERICAL SEMIGROUPS WITH TORSION
The goal of this section is to extend Theorem 2.4 and Theorem 6.5 to more general families of
posets with a semigroup structure. We start from a high point of view and consider subsemigroups
of N × T where T is any finite monoid. The main result of this section is that the above-mentioned
theorems generalize naturally to this setting if and only if T is a finite abelian group. Semigroups
of this kind, which we call numerical semigroups with torsion, have been considered in the literature by several authors due to their connections with one dimensional lattice ideals (see, for
example, [16, 18]). Whenever S is a numerical semigroup with torsion that additionally has no
inverses, it carries a natural poset structure (S, ≤S ) induced by x ≤S y ⇔ y − x ∈ S. Moreover, for every x, y ∈ S the upper sets x + S and y + S are isomorphic with via the addition
of y − x ∈ Z × T . Since the addition in Z × T is commutative this implies that (S, ≤S ) is
auto-equivalent in the sense of [5, Section 5].
In order to extend Theorem 2.4 and Theorem 6.5 let us first highlight the main ingredients of
their proofs. We observe that Theorem 2.4 relies on the following property of semigroup posets:
whatever player A’s first move is, the remaining poset is finite (Remark 2.3) and its number of
maximal elements does not depend on the first move (Corollary 2.2). Moreover, this number is

CHOMP ON NUMERICAL SEMIGROUPS

17

exactly 1 if and only if the corresponding numerical semigroup is symmetric. Similarly, Theorem 6.5 builds on the local behavior of numerical semigroup posets. Hence, whenever a family of
posets has this behavior, we obtain analogue versions of Theorems 2.4 and 6.5.
In order to see how far we can go with respect to the structural restrictions on T while still
ensuring a generalization of our results, we start by studying submonoids of (N × T, ·), where N is
considered as an additive monoid and (T, ·) is a finite monoid. In order to avoid cases, we assume
that our numerical semigroups with torsion are infinite, that is, not all their elements have a zero
in the first coordinate.
Even if we will not make explicit use of it later, we begin by studying which such monoids
are finitely generated as a result of independent interest. For this we restrict the notion of finitely
generated in the following sense: Let T be a finite monoid with neutral element e and let (S, ·)
be a submonoid of N × T . We set St := S ∩ (N × {t}) for all t ∈ T . We say that S is nicely
generated if there exists a finite set F ⊂ S such that S = F · Se . Since Se is isomorphic to
a subsemigroup of N, there exist a1 , . . . , an ∈ N such that Se = h(a1 , e), . . . , (an , e)i. Thus, S
being nicely generated means that every y ∈ S can be written as y = x · (b, e) with x ∈ F and
b ∈ ha1 , . . . , an i. In particular, nicely generated implies finitely generated.
Example 7.1. Consider (T, ·) the monoid with T = {0, 1, 2} and i · j := min{i + j, 2} for all
i, j ∈ {0, 1, 2}. Then S = h(3, 0), (2, 1), (3, 2)i is nicely generated, indeed, Se = h(3, 0)i and
S = F · Se with F = {(0, 0), (2, 1), (3, 2), (4, 2), (8, 2)}
Proposition 7.2. Let T be a finite monoid with neutral element e and let (S, ·) be a submonoid of
N × T . We have that S is nicely generated if and only if (a, e) ∈ S for some a > 0.
Proof. The first direction is trivial. If S does not contain an element of the form (a, e) with a > 0,
then S = F · Se = F is finite, contradicting our general assumption that S is infinite.
Conversely, we take a1 , . . . , an ∈ N such that Se = h(a1 , e), . . . , (an , e)i. If we set d :=
gcd{a1 , . . . , an }, then there exists g ∈ Z+ such that for all b > g, (b, e) ∈ Se if and only if d
divides b.
For every t ∈ T , j ∈ {0, . . . , d − 1} we denote St,j := {(x, t) ∈ St | x ≡ j (mod d)} and,
whenever St,j is not empty, we set rt,j := min{x ∈ N | (x, t) ∈ St,j }. We conclude that there is
only a finite number of elements in S that cannot be expressed as (rt,j , t) · (s, e) with (s, e) ∈ Se ;
this proves the result.

As a consequence of Proposition 7.2 we get that if T is a finite group, then S is always finitely
generated.
Corollary 7.3. Let T be a finite group with neutral element e and let (S, ·) be a submonoid of
N × T . Then S is nicely generated.
Proof. By Proposition 7.2, if there exists a > 0 such that (a, e) ∈ S, then we are done. Otherwise,
we are going to see that S ⊂ {0} × T and, hence, it is finite. By contradiction, assume that there
exists (b, t) ∈ S with b > 0; if we multiply (b, t) with itself k times, with k the order of t ∈ T , we
get that (kb, e) ∈ S and kb > 0, a contradiction.

From now on, we assume without loss of generality that St 6= ∅ for all t ∈ T ; otherwise
one could find another monoid T 0 ( T such that S ⊆ N × T 0 . For example for T = Z/6Z
the cyclic group with 6 elements, the semigroup S = h(7, 2), (4, 4)i ⊂ N × T satisfies that
S1 = S3 = S5 = ∅; hence taking T 0 := 2Z/6Z = {0, 2, 4} we have that S ⊂ N × T 0 .
In general, the complement of x · S := {x · s | s ∈ S} in S is not finite. For instance, if we
take x = (2, 1) in Example 7.1, then h(3, 0)i is an infinite subset of S \ (x · S). Proposition 7.5
provides a sufficient condition so that the complement of x · S := {x · s | s ∈ S} in S is finite
for all x ∈ S. Since the set S \ (x · S) is a natural generalization of the Apéry set for numerical
semigroups, we will usually denote it by Ap(S, x). The condition that Ap(S, x) is finite for every

18

I. GARCÍA-MARCO AND K. KNAUER

x is equivalent to saying that when playing chomp on S, after one move the remaining poset is
finite. Before stating the result we recall a well known result.
Proposition 7.4. Let T be a monoid. Then, T is a group if and only if for all t1 , t2 ∈ T there exists
an u ∈ T such that t1 · u = t2 .
Proposition 7.5. Let (T, ·) be a finite monoid and let S be a submonoid of N × T . We have that
T is a group if and only if Ap(S, x) is finite for all x ∈ S and S is nicely generated.
Proof. For the first direction let T be a group. By Corollary 7.3 we have that S is nicely generated.
Hence, there exists an element (a, e) ∈ S with a > 0. We write Se = h(a1 , e), . . . , (an , e)i for
some a1 , . . . , an ∈ Z+ . If we set d := gcd{a1 , . . . , an }, then:
(1) if (b, e) ∈ Se , then b is a multiple of d, and
(2) there exists g ∈ Z+ such that for all b > g, (b, e) ∈ Se if and only if b is a multiple of d.
For every (b1 , t), (b2 , t) ∈ S we claim that:
(3) b1 − b2 is a multiple of d;
indeed, there exists a c ∈ N such that (c, t−1 ) ∈ T , then (b1 + c, e), (b2 + c, e) ∈ Se and (3) follows
from (1).
Take now x = (b, t) ∈ S. We observe that Ap(S, x) = ∪s∈T (Ss \ (x · S)) and we are going to
prove that Ss \ (x · S) is finite for all s ∈ T . More precisely, if we take x0 = (c, t0 ) ∈ S so that
t · t0 = s, we are proving that (a, s) ∈ x · S for all a > b + c + g. Indeed, since x · x0 = (b + c, s),
then a − b − c is a multiple of d by (3); and, since a − b − c > g, then (a − b − c, e) ∈ Se by (2).
Thus, we can write (a, s) = x · x0 · (a − b − c, e) ∈ x · x0 · Se ⊂ x · S, and the result follows.
We prove the second direction by contradiction. Assume that T is not a group. Since S is
nicely generated by Proposition 7.2 there exists a > 0 such that (a, e) ∈ S. First, we observe that
St is infinite for all t ∈ T . Indeed, for all t ∈ T , if we take b ∈ N such that (b, t) ∈ St , then
(b + λa, t) ∈ St for all λ ∈ N. Since T is not a group, by Proposition 7.4, there exist t1 , t2 such
that t1 · u 6= t2 for all u ∈ T . Then, for all x ∈ St1 we have that St2 ⊂ Ap(S, x) and, thus, it is
infinite.

The following example illustrates why the hypothesis of being nicely generated cannot be
removed. Consider (T, ·) the monoid with T = {0, . . . , n} and i · j := min{i + j, n} for
all i, j ∈ {0, . . . , n}. Clearly, T is not a group but the monoid S ⊂ N × T with elements
{(i, i) | 0 ≤ i < n} ∪ {(i, n) | i ∈ N} satisfies that for all x ∈ S, the set Ap(x, S) is finite. While S
is finitely generated, it does not contain any (a, 0) with a > 0 and therefore is not nicely generated
by Proposition 7.2.
Motivated by Proposition 7.5, from now on we will consider submonoids S of N × T , where T
is a finite group. It is worth pointing out that such a monoid is embeddable in the group Z × T .
We are first proving that in this context one can extend the definition of Frobenius number.
Proposition 7.6. Let (T, ·) be a finite group and S a submonoid of N × T . Denote by ZS the
smallest subgroup of Z × T containing S. There exists g(S) ∈ Z such that for all (a, t) ∈ ZS if
a > g(S), then (a, t) ∈ S.
Proof. We take G the smallest subgroup of Z × {e} containing Se . Since G ⊂ Z × {e}, it is
cyclic with generator (d, e) for some d ∈ N. If d = 0, then S = G = {0} × T and the result
follows. Assume that d > 0, then there exists ge ∈ N such that for all (a, e) ∈ G with a > ge ,
we have that (a, e) ∈ S. For all t ∈ T we take mt := min{a ∈ N | (a, t) ∈ St }. We claim
that g(S) := ge + max{mt | t ∈ T } satisfies the desired property. Consider (c, t) ∈ ZS with
c > g(S). We have that (mt , t) ∈ S and then (c, t) · (mt , t)−1 = (c − mt , e) ∈ ZS. Moreover,
since c − mt > ge , we have that (c − mt , e) ∈ S. Thus, (c, t) = (mt , t) · (c − mt , e) ∈ S.

Let us illustrate this result with an example.

CHOMP ON NUMERICAL SEMIGROUPS

19

Example 7.7. Let T = S3 be the symmetric group on 3 elements and consider the monoid S =
h(3, id), (2, (12)), (4, (123))i ⊂ N × S3 . Since the set {(12), (123)} generates S3 , we have St 6= ∅
for all t ∈ S3 . Moreover, the equality (2, (12)) · (2, (12)) · (3, id)−1 = (1, id) ∈ ZS yields that
ZS = Z × S3 . Since (3, id), (4, id) ∈ S there exists g(S) ∈ Z+ such that for all (a, σ) ∈ Z × S3
with a > g(S), we have a ∈ S. More precisely, we have that (2, (12)), (4, (123)), (6, (23)),
(6, (13)), (8, (132)) ∈ S and that Sid = h(3, id), (4, id)i, thus Proposition 7.6 holds with g(S) =
13.
We define the set of gaps of the semigroup S as N (S) := ZS ∩ (N × T ) \ S. Proposition 7.6
implies that this set is always finite.
To play chomp on S, we need that (S, ≤S ) has a poset structure with a global minimum. The
role of the minimum will be played by (0, e) ∈ S, the neutral element. We consider the binary
relation r1 ≤S r2 ⇔ r2 · r1−1 ∈ S. A necessary and sufficient condition for ≤S to be an order is
that
(1)

(0, t) ∈ S ⇐⇒ t = e.

Indeed, ≤S is reflexive (because S has a neutral element), transitive (because S is closed under ·)
and property (1) implies antisymmetry. A monoid satisfying property (1) will be called an ordered
monoid.
In order to extend Theorem 2.4 we also need that the number of maximal elements of the
remaining poset is invariant under the choice of the first move. We will see that this is always the
case if and only if T is commutative, that is, if S is a numerical semigroup with torsion.
Proposition 7.8. Let T be a finite group. The number of maximal elements of Ap(S, x) is invariant
under the choice of x for every ordered monoid (S, ≤S ) with S ⊂ N × T if and only if T is
commutative.
Proof. (⇐) We assume that T is commutative. To prove the result it suffices to establish a bijection
between the set of maximal gaps of S with respect to ≤S and the set of maximal elements of
Ap(S, x). In fact, it is straightforward to check that the map sending σ : N (S) −→ Ap(S, x)
defined as y 7→ x · y is a bijection.
(⇒) Suppose that T is not commutative. We are going to exhibit an ordered monoid (S, ≤S )
with S ⊂ N×T and two elements x, y ∈ S such that the number of maximal elements of Ap(S, x)
and Ap(S, y) with respect to ≤S is not the same. We take s, t ∈ T such that s · t 6= t · s and we set

S := {(i, s) | i ≥ 1} ∪ {(i, s · t) | i ≥ 3} ∪ ∪u∈{s,s·t}
{(i, u) | i ≥ 2} ∪ {(0, e)}
/
We observe that S is a semigroup, the only potential problem would be if (1, s) · (1, s) =
(2, s · t) ∈
/ S, but this is not possible because s2 6= s · t. Now we choose x := (2, e) and
y := (1, s). We are going to prove that Ap(S, x) has more maximal elements than Ap(S, y).
Indeed, this is a consequence of the following facts:
(a) Ap(S, x) = {(0, e), (3, e), (1, s), (2, s), (3, s · t), (4, s · t)} ∪ {(2, u), (3, u) | u ∈
/ {s, s ·
t, e}},
(b) every element of
{(4, s · t)} ∪ {(3, u) | u ∈
/ {s, t}} ⊂ Ap(S, x),
is a maximal with respect to ≤S ,
(c) Ap(S, y) = {(2, u) | u ∈
/ {s2 , s · t}} ∪ {3, s2 · t} ∪ {(0, e)}, and, hence, it has size |T |, and
2
−1
(d) (0, e) and (2, s · t · s ) belong to Ap(S, y) and are not maximal in this set with respect
to ≤S ; thus Ap(S, y) has at most |T | − 2 maximal elements.
If we prove facts (a)-(d), we conclude that Ap(S, x) has at least |T | − 1 maximal elements
meanwhile Ap(S, y) has at most |T | − 2; and the result follows. Since (a) is easy to check, we
start by proving (b). We denote by Mx the set of maximal elements of Ap(S, x) with respect to
≤S . We first observe that (4, s · t) ∈ Mx . An element (3, u) ∈ Ap(S, x) if and only if u 6= s;

20

I. GARCÍA-MARCO AND K. KNAUER

moreover it belongs to Mx if and only if (3, u) 6≤S (4, s·t) or, equivalently, if (1, s·t·u−1 ) 6= (1, s);
this happens if and only if u 6= t.
To prove (c) one just needs to verify that (i, u) ∈ y · S for all u ≥ 4, that (3, u) ∈ y · S if and
only if u 6= s2 · t, and that (2, u) ∈ y · S if and only if u = s2 .
Clearly, (0, e) is not maximal in Ap(S, y). Concerning (2, s2 ·t·s−1 ), we observe that s2 ·t·s−1 6=
s2 because t 6= s and that s2 · t · s−1 6= s · t because s · t 6= t · s; hence (2, s2 · t · s−1 ) ∈ Ap(S, y).
Finally, (2, s2 · t · s−1 ) ≤S (3, s2 · t) because (1, s) ∈ T . This proves (d) and we are done.

In order to generalize Theorem 2.4, we first extend the definition of symmetric semigroup to
numerical semigroups with torsion. Let S be a numerical semigroup with torsion (since S is
abelian we will use the additive notation for the operation on S). We say that S is symmetric if
and only if there exists an x ∈ N (S) such that:
y ∈ N (S) ⇐⇒ x − y ∈ S.
We observe that the role of x in this definition can only be played for a maximal element in N (S);
indeed, S is symmetric if and only if the set of gaps of S has a maximum. Following the lines of
the proof of Proposition 7.8, we have that this is equivalent to Ap(S, z) having a global maximum
with respect to ≤S for all z ∈ S. Thus, from Propositions 7.5 and 7.8, we conclude the following
result:
Theorem 7.9. Let T be a finite commutative group and let (S, ≤S ) be an ordered numerical
semigroup with torsion. If S is symmetric, then player B has a winning strategy for chomp on S.
Furthermore, we can extend the proof of Theorem 6.5 to prove the following result:
Theorem 7.10. Let S ⊂ N × T be an ordered numerical semigroup with torsion. If A has
a winning strategy for chomp on S, then A has a winning strategy with first move (a, x) with
n
a ≤ 2gt2 , where g = max{a ∈ Z | (a, x) ∈ N (S)}, n = |N (S)| and t = |T |.
8. C ONCLUDING REMARKS
We have combined the combinatorial game of chomp with the more algebraically structured
posets coming from numerical semigroups. Some concepts in semigroups found a corresponding interpretation as strategies in chomp. While we have found strategies on several classes of
semigroups, it is clear, that the problem in general is quite complicated and for many (seemingly
restricted) classes, we could not provide a complete characterization for when A wins. We believe
that the possibly easiest next case to attack would be to get more results on semigroups, that are
generated by an interval. As mentioned at the end of Section 5 a first task could be to completely
characterize the generated semigroups of type 2 and with k odd, where A has a winning strategy.
Another problem pointed out at the end of Section 5 can be formulated as follows:
Conjecture 8.1. For every c there exists an ac , such that for all a ≥ ac player A has a winning
strategy for chomp on S = ha, a + 1, . . . , 2a − ci if and only if a and c are odd.
The results of Sections 3 and 5 show that the statement of the conjecture is true for 1 ≤ c ≤ 3,
with the a1 , a2 , a3 being 2, 3, 7, respectively. Moreover, the results from Section 4 show that if a
and c are odd, then A has a winning strategy, so indeed only one direction remains open. Similarly,
one can wonder whether for every k there exists an ak , such that for all a ≥ ak the winner of chomp
on S = ha, a + 1, . . . , a + ki is determined by the parities of a and k. We know this to be true for
1 ≤ k ≤ 2 by the results from Section 5.
We have shown, that the outcome of chomp on a given S is decidable, by giving a huge upper
bound for the smallest winning first move of A. Can this bound be improved? What is the
computational complexity of deciding the outcome of S?
In the last section, we studied under which circumstances our results on numerical semigroups
can be generalized in a straight-forward way to other posets coming from infinite monoids. It

CHOMP ON NUMERICAL SEMIGROUPS

21

would be interesting to further broaden this class of posets, to those defined in terms of wider
classes of monoids or satisfying some local symmetry conditions, such as the auto-equivalent
posets defined in [5]. This will be the subject of a forthcoming paper [13].

Acknowledgements. K.K. has been supported by ANR project ANR-16-CE40-0009-01: Graphes,
Algorithmes et TOpologie. I. G. has been supported by Ministerio de Economía y Competitividad,
Spain (MTM2016-78881-P).
The authors want to thank the anonymous referees for their comments and suggestions that
helped to improve this manuscript.

R EFERENCES
[1] V. Barucci, D. E. Dobbs, and M. Fontana. Maximality properties in numerical semigroups and applications to
one-dimensional analytically irreducible local domains. Mem. Amer. Math. Soc., 125(598):x+78, 1997.
[2] I. Bermejo, E. García-Llorente, and I. García-Marco. Algebraic invariants of projective monomial curves associated to generalized arithmetic sequences. J. Symbolic Comput., 81:1–19, 2017.
[3] C. L. Bouton. Nim, a game with a complete mathematical theory. Ann. of Math. (2), 3(1-4):35–39, 1901/02.
[4] A. E. Brouwer. The game of chomp. https://www.win.tue.nl/∼aeb/games/chomp.html.
[5] J. Chappelon, I. García-Marco, L. P. Montejano, and J. L. Ramírez Alfonsín. Möbius function of semigroup
posets through Hilbert series. J. Combin. Theory Ser. A, 136:238–251, 2015.
[6] J. Chappelon and J. L. Ramírez Alfonsín. On the Möbius function of the locally finite poset associated with a
numerical semigroup. Semigroup Forum, 87(2):313–330, 2013.
[7] J. A. Deddens. A combinatorial identity involving relatively prime integers. J. Combin. Theory Ser. A, 26(2):189–
192, 1979.
[8] M. Estrada and A. López. A note on symmetric semigroups and almost arithmetic sequences. Comm. Algebra,
22(10):3903–3905, 1994.
[9] J. I. Farrán, P. A. García-Sánchez, B. A. Heredia, and M. J. Leamer. The second feng–rao number for codes
coming from telescopic semigroups. Designs, Codes and Cryptography, Oct 2017.
[10] S. A. Fenner and J. Rogers. Combinatorial game complexity: an introduction with poset games. Bull. Eur. Assoc.
Theor. Comput. Sci. EATCS, (116):42–75, 2015.
[11] R. Fröberg, C. Gottlieb, and R. Häggkvist. On numerical semigroups. Semigroup Forum, 35(1):63–83, 1987.
[12] D. Gale. A curious Nim-type game. Amer. Math. Monthly, 81:876–879, 1974.
[13] I. García-Marco and K. Knauer. Cayley posets. (in preparation).
[14] P. A. García-Sánchez and J. C. Rosales. Numerical semigroups generated by intervals. Pacific J. Math.,
191(1):75–83, 1999.
[15] E. Kunz. The value-semigroup of a one-dimensional Gorenstein ring. Proc. Amer. Math. Soc., 25:748–751,
1970.
[16] H. H. López and R. H. Villarreal. Computing the degree of a lattice ideal of dimension one. J. Symbolic Comput.,
65:15–28, 2014.
[17] G. L. Matthews. On numerical semigroups generated by generalized arithmetic sequences. Comm. Algebra,
32(9):3459–3469, 2004.
[18] M. Morales and A. Thoma. Complete intersection lattice ideals. J. Algebra, 284(2):755–770, 2005.
[19] J. L. Ramírez Alfonsín. The Diophantine Frobenius problem, volume 30 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2005.
[20] J. L. Ramírez Alfonsín and Ø. J. Rø dseth. Numerical semigroups: Apéry sets and Hilbert series. Semigroup
Forum, 79(2):323–340, 2009.
[21] J. C. Rosales. On symmetric numerical semigroups. J. Algebra, 182(2):422–434, 1996.
[22] J. C. Rosales and P. A. García-Sánchez. Numerical semigroups, volume 20 of Developments in Mathematics.
Springer, New York, 2009.
[23] J.C. Rosales, P. A García-Sánchez, J. I. García-García, and M. B. Branco. Numerical semigroups with maximal
embedding dimension. Int. J. Commut. Rings, 2(1):47–53, 2003.
[24] F. Schuh. Spel van delers (the game of divisors). Nieuw Tijdschrift voor Wiskunde, 39:299–304, 1952.
[25] E. S. Selmer. On the linear Diophantine problem of Frobenius. J. Reine Angew. Math., 293/294:1–17, 1977.
[26] L. Sharifan and R. Zaare-Nahandi. Minimal free resolution of the associated graded ring of monomial curves of
generalized arithmetic sequences. J. Pure Appl. Algebra, 213(3):360–369, 2009.

22

I. GARCÍA-MARCO AND K. KNAUER

FACULTAD DE C IENCIAS , U NIVERSIDAD DE L A L AGUNA . 38200 L A L AGUNA , S PAIN .
E-mail address: iggarcia@ull.es
A IX M ARSEILLE U NIV, U NIVERSITÉ DE T OULON , CNRS, LIS, M ARSEILLE , F RANCE .
E-mail address: kolja.knauer@lis-lab.fr

