NUMERICAL SEMIGROUPS II:
PSEUDO-SYMMETRIC AA-SEMIGROUPS

arXiv:1601.07337v1 [] 27 Jan 2016

IGNACIO GARCÍA-MARCO *, JORGE L. RAMÍREZ ALFONSÍN, AND ØYSTEIN J. RØDSETH
A BSTRACT. This paper is a continuation of the paper “Numerical Semigroups: Apéry Sets and
Hilbert Series" [4]. We consider the general numerical AA-semigroup, i.e., semigroups consisting of all non-negative integer linear combinations of relatively prime positive integers of the form
a, a+d, a+2d, . . . , a+kd, c. We first prove that, in contrast to arbitrary numerical semigroups, there
exists an upper bound for the type of AA-semigroups that only depends on the number of generators of the semigroup. We then present two characterizations of pseudo-symmetric AA-semigroups.
The first one leads to a polynomial time algorithm to decide whether an AA-semigroup is pseudosymmetric. The second one gives a method to construct pseudo-symmetric AA-semigroups and
provides explicit families of pseudo-symmetric semigroups with arbitrarily large number of generators.

1. I NTRODUCTION
This paper is a continuation of the paper [4]. For a numerical semigroup S, we recall that the
Frobenius number g = g(S) is the largest integer not in S, and the genus N = N (S) is the
number of non-negative integers not in S. The semigroup S is symmetric if
S ∪ (g − S) = Z,

where g − S = {g − s | s ∈ S}. The semigroup is pseudo-symmetric if the Frobenius number g
is even and
(1)

S ∪ (g − S) = Z \ {g/2}.

It is well known that S is symmetric if and only if g = 2N − 1. Similarly, it is also known that S
is pseudo-symmetric if and only if
(2)

g = 2N − 2.

We include an easy proof of this result in Section 2 (Lemma 2.2).
Set ∆ = 2N − 1 − g. Then S is symmetric if and only if ∆ = 0, and pseudo-symmetric if
and only if ∆ = 1. The numerical semigroup S is irreducible if it is not the intersection of two
strictly larger numerical semigroups. It now follows from [1, 2, 6] that S is irreducible if and only
if ∆ ≤ 1.
For a semigroup S we set S 0 = {x ∈
/ S | x + s ∈ S for all s ∈ S}. The elements of S 0 are
usually called pseudo-Frobenius numbers and the number of elements of S 0 is called the type of S
and denoted by type(S). We notice that g is always a pseudo-Frobenius number. Moreover, by [2,
Proposition 2] S is symmetric if and only if S 0 = {g}, or equivalently, if the type of S is 1. Also,
S is pseudo-symmetric if and only if S 0 = {g, g/2}, which implies that every pseudo-symmetric
semigroup has type 2.
The Apéry set of S with respect to m ∈ S is defined as
Ap(S; m) = {s ∈ S | s − m ∈
/ S}.

2010 Mathematics Subject Classification. 05A15, 13P10, 20M14.
Key words and phrases. Numerical semigroup, Apéry set, Frobenius number, Cohen-Macaulay type, genus,
pseudo-symmetry.
* Corresponding Author: Phone: +33-624564368. Email: ignacio.garcia-marco@ens-lyon.fr, iggarcia@ull.es
The first author was supported by the Ministerio de Economía y Competitividad, Spain (MTM2013-40775-P).
1

2

I. GARCÍA-MARCO, J.L. RAMÍREZ ALFONSÍN, AND Ø. J. RØDSETH

An Apéry set of a semigroup S is very difficult to determine in general. This set contains many
relevant information about the semigroup. As we shall point out, in Section 2, all the above
mentioned parameters related to S can be expressed in terms of an Apéry set.
In this paper we focus our attention on numerical AA-semigroup consisting of all non-negative
integer linear combinations of relatively prime positive integers a, a + d, a + 2d, . . . , a + kd, c,
where also a, d, k, c are positive integers. In [5], Rødseth presented “semi-explicit" formulas for
Ap(S; a), g(S) and N (S) when S is an AA-semigroup.
This self-contained paper is organized as follows. In next section, we review some basic results
on Apéry sets and the type of numerical semigroups. We also present a useful characterization on
the pseudo-symmetry of semigroups (Lemma 2.2).
In Section 3, after recalling some basic notions and results on AA-semigroup given in [5]
needed for the rest of the paper, we prove that the type of an AA-semigroup is at most 2k (Theorem 3.1). Since every three generated numerical semigroup is an AA-semigroup (with k = 1),
then Theorem 3.1 generalizes a result due to Fröberg, Gottlieb and Häggkvist [2, Theorem 11]
stating that a 3 generated numerical semigroup has type at most 2.
In Section 4, we present two characterizations for pseudo-symmetric AA-semigroups. The first
one (Theorem 4.5) provides a criterion to decide when an AA-semigroup is irreducible. As a
consequence of this result and [4, Theorem 6], we obtain a polynomial time algorithm to decide
whether an AA-semigroup is pseudo-symmetric. Also, by combining the characterization of symmetric AA-semigroups given in [4, Theorem 5] together with Theorem 4.5 we obtain a complete
characterization of irreducible AA-semigroups. The second characterization of pseudo-symmetric
AA-semigroups (Theorem 4.9) shows how to construct any pseudo-symmetric AA-semigroup.
In particular, it provides explicit families of pseudo-symmetric semigroups with arbitrarily large
number of generators. These results extend those given by Rosales and García-Sanchez in [7] who
characterized three generated pseudo-symmetric numerical semigroups.
2. T HE A PÉRY SET AND THE TYPE OF A NUMERICAL SEMIGROUP
Apéry sets are in general very difficult to describe and calculate. Nevertheless, in the few cases
where one knows explicitly this set, it provides a lot of interesting information about the numerical
semigroup. In this section we recall some nice properties of the Apéry set and use them to prove
some new results, all these properties will be useful in the sequel.
Firstly, it is well known that the Frobenius number of S can be computed as
(3)

g(S) = max Ap(S; m) − m,

and also
(4)

N (S) =

1
m

X
w∈Ap(S;m)

1
w − (m − 1),
2

(a result essentially due to Selmer [8]).
Let a1 , . . . , an be relatively prime positive integers, and let e be a positive integer prime to a1 .
Put S e = ha1 , ea2 , . . . , ean i. By [4, Section 2], we have that the map N −→ N; x 7→ ex induces a
bijection Ap(S; a1 ) −→ Ap(S e ; a1 ) and, hence,
(5)

eAp(S; m) = Ap(S e ; m).

From this equality, it was deduced in [4, (9) and (10)] that
g(S e ) = eg(S) + a1 (e − 1),

1
N (S e ) = eN (S) + (a1 − 1)(e − 1),
2

and so,
(6) ∆(S e ) = 2eN (S) + a1 (e − 1) − 1 − eg(S) − a1 (e − 1) = 2eN (S) − eg(S) − e = e∆(S).

NUMERICAL SEMIGROUPS II: PSEUDO-SYMMETRIC AA-SEMIGROUPS

3

Thus if S e is symmetric for some admissible e, then S e is symmetric for all admissible numbers
e. Moreover, we have that S is pseudo-symmetric if and only if ∆(S e ) = e. In particular, if S e is
pseudo-symmetric, then e = 1. Therefore, if S = ha, a + d, . . . , a + kd, ci, it is no restriction to
assume gcd(a, d) = 1 when studying pseudo-symmetry.
One can also determine the set S 0 of pseudo-Frobenius numbers in terms of the Apéry set.
Indeed, if we consider ≤S the partial order in Z given by x ≤S y ⇐⇒ y − x ∈ S, then, by [2,
Proposition 7], s ∈ S is a maximal element in Ap(S; m) with respect to ≤S if and only if s − m
is a pseudo-Frobenius number of S. From this result and (5) we directly deduce the following.
Proposition 2.1. type(S) = type(S e ).
We now present a helpful characterization of pseudo-symmetric semigroups.
Lemma 2.2. Let S be a numerical semigroup. The following conditions are equivalent:

(a) S is pseudo-symmetric
(b) If we write w(i) for the unique w ∈ Ap(S; m) satisfying w ≡ i (mod m), we have that
(
m if i ≡ 0 (mod m),
w(g/2 + i) + w(g/2 − i) = w(g) +
0 otherwise.
(c) g(S) = 2N (S) − 2.

Proof. [(a) =⇒ (b)] For all i, it is clear that w(g/2+i)+w(g/2−i) ≡ w(g) (mod m), so w(g/2+
i) +w(g/2−i)−w(g) = λi m for some λi ∈ Z. We observe that w(g) = g(S)+m, which implies
that λi ≥ 0, otherwise g ∈ S. Moreover, if λi > 0, we get that (w(g/2 − i) − m) + (w(g/2 + i) −
λi m) = g(S). From this equality we derive that w(g/2 − i) − m, w(g/2 + i) − λi m ∈
/ S ∪ (g − S).
Since S is pseudo-symmetric, we obtain that g/2 = w(g/2 − i) − m = w(g/2 + i) − λi m, so
λi = 1 and i ≡ 0 ( mod m).
[(b) =⇒ (a)] Take s ∈
/ S ∪ (g − S). Since s ∈
/ S, there exists i0 such that w(g/2 − i0 ) = s + µm
+
with µ ∈ Z . If i0 6≡ 0 (mod m), then s + µm + w(g/2 − i0 ) = w(g) = g + m and we get that
s ∈ g − S, a contradiction. If i0 ≡ 0 (mod m), then 2s + 2µm = 2w(g/2) = w(g) + m = g + 2m.
Hence µ = 1 and s + µm = g/2 + m, from where we finally obtain that s = g/2.
[(b) =⇒ (c)] Notice that g + m = w(g). Summing over a complete system of residues i (mod
m) and using formula (4), we get
1 X
(w(g/2 + i) + w(g/2 − i)) − m − 1
m i
1 X
=
w(g) − m = g.
m i

2N − 2 =

[(c) =⇒ (b)] We find that
m−1
1 X
g = 2N − 2 =
(w(g/2 + i) + w(g/2 − i)) − m − 1
m i=0

=

m−1
X
1 X
(w(g) + ci m) − m − 1 = g +
ci − 1,
m i=0
i

for integers ci ≥ 0. Thus, ci = 0 with the exception of one value of i mod m for which ci = 1.
Since ci = cj whenever i + j = m, we deduce that c0 = 1 and thus (b) holds.


4

I. GARCÍA-MARCO, J.L. RAMÍREZ ALFONSÍN, AND Ø. J. RØDSETH

3. T HE TYPE OF ALMOST ARITHMETIC PROGRESSIONS
Let us quickly recall some notions and results given in [5] needed in the rest of the paper.
Assume that gcd(a, d) = 1, let s−1 = a and set s0 the only integer such that
ds0 ≡ c (mod s−1 ),

0 ≤ s0 < s−1 .

If s0 = 0 we set m = −1. Otherwise, we use the Euclidean algorithm with negative division
remainders,
s−1 = q1 s0 − s1 ,
s0 = q 2 s1 − s2 ,
s1 = q 3 s2 − s3 ,
...
sm−2 = qm sm−1 − sm ,
sm−1 = qm+1 sm ,

0 ≤ s1 < s0 ;
0 ≤ s2 < s1 ;
0 ≤ s3 < s2 ;
0 ≤ sm < sm−1 ;
0 = sm+1 < sm .

We have sm = gcd(a, c). We define integers Pi by P−1 = 0, P0 = 1, and (if m ≥ 0),
Then, by induction on i,

Pi+1 = qi+1 Pi − Pi−1 ,

si Pi+1 − si+1 Pi = a,

i = 0, . . . , m.

i = −1, 0 . . . , m,

and
0 = P−1 < 1 = P0 < · · · < Pm+1 =

a
.
sm

In addition we have,
(7)

dsi ≡ cPi

(mod a),

i = −1, . . . , m + 1.

Putting
Ri =

1
((a + kd)si − kcPi ) ,
a

1
we see that all the Ri are integers. Moreover, we have R−1 = a + kd, R0 = ((a + kd)s0 − kc),
a
and
Ri+1 = qi+1 Ri − Ri−1 , i = 0, . . . , m.
Furthermore,
c
−
= Rm+1 < Rm < · · · < R0 < R−1 = a + kd,
sm
so there is a unique integer v such that
Rv+1 ≤ 0 < Rv .

For each i, let τ (i) be the smallest integer for which there exist non-negative integers x, y such
that
(8)

τ (i) = (a + kd)x + kcy,

dx + cy ≡ i

(mod a).

If there are more than one such pair x, y for some i, choose the one with y minimal. This gives
us a unique set L of pairs of nonnegative integers, with |L| = a. The set L consists of all lattice
points in a closed L-shaped region in the x, y-plane. Sometimes the L-shape degenerates to a
rectangle or an interval. Rødseth [5] proved that L = A ∪ B, where
A = {(x, y) | 0 ≤ x ≤ sv − 1,
0 ≤ y ≤ Pv+1 − Pv − 1}
B = {(x, y) | 0 ≤ x ≤ sv − sv+1 − 1, Pv+1 − Pv ≤ y ≤ Pv+1 − 1}.

Moreover, Rødseth showed that if we consider the map

NUMERICAL SEMIGROUPS II: PSEUDO-SYMMETRIC AA-SEMIGROUPS

5

ϕ : Z2 → Z
lxm
(x, y) 7→
a + xd + yc,
k
then Ap(S; a) = ϕ(L).

(9)

Combining (9) and (3), Rødseth easily deduced that
(10)

g(S) = max{ϕ(sv − 1, Pv+1 − Pv − 1), ϕ(sv − sv+1 − 1, Pv+1 − 1)} − a.

Fröberg, Gottlieb and Häggkvist proved in [2, Theorem 11] that every three generated numerical
semigroup has type at most 2. In the same paper the authors include an observation due to J.
Backelin showing that there is no upper bound on the type of ha1 , . . . , at i only in terms of t for
t ≥ 4. Indeed, he provided a family (Sn )n∈N of 4 generated numerical semigroups whose type
is 2n + 3. In this section we consider AA-semigroups, i.e., numerical semigroups of the form
S = ha, a + d, . . . , a + kd, ci, where a, d, k, c are positive integers. These semigroups generalize
three generated semigroups. We prove that the type of AA-semigroups is bounded in terms of the
number of generators of the semigroup.
Theorem 3.1. Let S be an AA-semigroup, then type(S) ≤ 2k.
By Proposition 2.1, it suffices to prove this result when gcd(a, d) = 1.
Proof of Theorem 3.1. It suffices to observe that for all (x, y) ∈ Z2 , ϕ(x + k, y) − ϕ(x, y) =
a + kd ∈ S and that ϕ(x, y + 1) − ϕ(x, y) = c ∈ S. The rectangular grid shape of A shows
that in ϕ(A) there are at most k maximal elements of Ap(S; a) with respect of ≤S . The same
argument works for B. So, there are at most 2k maximal elements in Ap(S; a) with respect to ≤S
and, hence, type(S) ≤ 2k.
2
The bound provided in Theorem 3.1 is sharp. Indeed, consider the following
Example 3.2. For all k ≥ 1 we consider the AA-semigroup Sk = ha, . . . , a + kd, ci with a :=
3k + 2, d := 1 and c := 5k + 3. We observe that s0 = 2k + 1. The equality a = 2s0 − k yields that
s1 = k and P1 = 2. Since R1 = −2k ≤ 0 < k + 1 = R0 , we get that v = 0. A direct application
of (9) gives that Ap(S; a) = ϕ(L), where L is the set of Figure 1.

1
0

1

k k+1

2k

F IGURE 1. L-shape in bijection with Ap(Sk ; a)
Then,
Ap(S; a) = {0, a, a + 1, . . . , a + k, 2a + k + 1, . . . , 2a + 2k, c, c + a + 1, . . . , c + a + k}

Hence, the maximal elements of Ap(S; a) with respect to ≤S are {2a+k +i, c+a+i | 1 ≤ i ≤ k}
(see Figure 2) and type(S) = 2k.
4. P SEUDO - SYMMETRIC ALMOST ARITHMETIC SEMIGROUPS
The goal of this section is to characterize pseudo-symmetry for AA-semigroups. When S is
a three generated numerical semigroup, Rosales and García-Sánchez gave a characterization of
pseudo-symmetry in [7]. They proved that if S is a three generated numerical semigroup then S

6

I. GARCÍA-MARCO, J.L. RAMÍREZ ALFONSÍN, AND Ø. J. RØDSETH

1
0

1

k k+1

2k

F IGURE 2. Points corresponding to maximal elements of Ap(Sk ; a)
is pseudo-symmetric if and only S = hc(b − 1) + 1, (c − 1)a + 1, b(a − 1) + 1i with gcd(c(b −
1) + 1, (c − 1)a + 1) = 1.

Here, we only consider the case when S is an AA-semigroup generated by at least 4 elements,
i.e., when k ≥ 2. However, one could easily extend our proof for three generated semigroups and
recover the result of Rosales and García-Sánchez.
As mentioned in Section 2, if gcd(a, d) 6= 1, then S is not pseudo-symmetric, so from now on
we suppose that a and d are relatively prime. The idea of our proof is to apply the description of
Ap(S; a) in terms of the set L and the map ϕ given in (9) together with the characterization of
pseudo-symmetry given in Lemma 2.2 (b).
In the forthcoming we denote by (x0 , y0 ) the element of L such that ϕ(x0 , y0 ) = g(S) + a.
By (10) it follows that
(x0 , y0 ) = (sv − sv+1 − 1, Pv+1 − 1) or (sv − 1, Pv+1 − Pv − 1).
Before stating and proving the main results we need the following three lemmas. The proof of
the first one is a straightforward checking (we leave it to the reader).
Lemma 4.1. Let S be an AA-semigroup.
If (x0 , y0 ) = (sv − sv+1 − 1, Pv+1 − 1), then

(a1) ϕ(x, y) + ϕ(x0 − x, y0 − y) ≡ ϕ(x0 , y0 ) (mod a) for 0 ≤ x ≤ x0 , 0, ≤ y ≤ y0 .
(a2) ϕ(x, y) + ϕ(x0 + sv − x, y0 − Pv − y) ≡ ϕ(x0 , y0 ) (mod a) for x0 < x ≤ sv − 1,
0 ≤ y ≤ y0 − Pv .

If (x0 , y0 ) = (sv − 1, Pv+1 − Pv − 1), then

(b1) ϕ(x, y) + ϕ(x0 − x, y0 − y) ≡ ϕ(x0 , y0 ) (mod a) for 0 ≤ x ≤ x0 , 0, ≤ y ≤ y0 .
(b2) ϕ(x, y) + ϕ(x0 − sv+1 − x, y0 + Pv+1 − y) ≡ ϕ(x0 , y0 ) (mod a) for 0 ≤ x ≤ x0 − sv+1 ,
y0 < y ≤ y0 + Pv+1 .
Remark 4.2. Let S be a pseudo-symmetric AA-semigroup and let us denote by (x1 , y1 ) the element in L such that ϕ(x1 , y1 ) = (g(S)/2) + a. Then,
(a) 2ϕ(x1 , y1 ) = g(S) + 2a = ϕ(x0 , y0 ) + a, and
(b) if 2ϕ(x1 , y1 ) = ϕ(x0 , y 0 ) + ϕ(x00 , y 00 ) with (x0 , y 0 ), (x00 , y 00 ) ∈ L, then x1 = x0 = x00 and
y1 = y 0 = y 00 (this is a consequence of Lemma 2.2(b)).
Lemma 4.3. Let S be a pseudo-symmetric AA-semigroup. Then,
(a) either y1 = 0 or (x1 , y1 + 1) ∈
/ L,
(b) either x1 < k or (x1 + k, y1 ) ∈
/ L, and
(c) either x1 = 0, (x1 + 1, y1 ) ∈
/ L or x1 ≡ 1 (mod k).

Proof. If (a) does not hold, then 2ϕ(x1 , y1 ) = ϕ(x1 , y1 − 1) + ϕ(x1 , y1 + 1), but this contradicts
Remark 4.2(b). Similarly, if (b) does not hold, then 2ϕ(x1 , y1 ) = ϕ(x1 − k, y1 ) + ϕ(x1 + k, y1 ),
a contradiction. Finally, if (c) does not hold, then ϕ(x1 , y1 ) = ϕ(x1 − 1, y1 ) + d and ϕ(x1 , y1 ) ≤
ϕ(x1 + 1, y1 ) − d. Hence, ϕ(x0 , y0 ) + a = 2ϕ(x1 , y1 ) ≤ ϕ(x1 − 1, y1 ) + ϕ(x1 + 1, y1 ) = ϕ(x0 , y0 ),
which is again a contradiction.


NUMERICAL SEMIGROUPS II: PSEUDO-SYMMETRIC AA-SEMIGROUPS

7

Lemma 4.4. Let S be a pseudo-symmetric AA-semigroup such that (x0 , y0 ) 6= (2, 0). Then, either
x0 = 0 or x0 ≡ 1 (mod k). In particular, this implies that
ϕ(x0 , y0 ) = ϕ(x0 − x, y0 − y) + ϕ(x, y)
for all 0 ≤ x ≤ x0 , 0 ≤ y ≤ y0 .
Proof. Firstly we observe that S cannot be a two generated semigroup, otherwise it would be
symmetric. By contradiction, assume that x0 > 0 and that x0 6≡ 1 (mod k). Then, ϕ(x0 , y0 ) =
ϕ(x0 − 1, y0 ) + d. We claim that d ∈
/ S. Indeed, if d ∈ S, then S = ha, ci, a contradiction.
Therefore, x1 = x0 − 1 and y1 = y0 . The equality 2ϕ(x1 , y1 ) = ϕ(x0 , y0 ) + a yields ϕ(x1 , y1 ) =
a + d. Hence we have that either (x1 , y1 ) = (1, 0) or (x1 , y1 ) = (0, λ) for some λ > 0. Then,
(x0 , y0 ) = (2, 0) or x0 = 1, a contradiction. The reader can easily verify the second part of the
result.

We may now proceed with our first characterization.
Theorem 4.5. Let S = ha, a + d, . . . , a + kd, ci with a, d, c ∈ Z+ and k ≥ 2. Then, S is
pseudo-symmetric if and only if gcd(a, d) = 1 and one of the following statements holds:
(a) S = h3, 3 + d, 3 + 2di
(b) a(c − 1) = 2(c + d) with c odd,
(c) sv ≡ 3 (mod k), sv+1 = 1, Pv+1 = Pv + 1 and Rv = 3,
(d) sv ≡ 1 (mod k), sv+1 = 2k − 1, Pv+1 = Pv + 1 and Rv = 1,
(e) s0 ≡ 2 (mod k), s0 = s1 + 1 and R1 = 1 − 2k, or
(f) s0 ≡ 2 (mod k), s0 = s1 + 3 and R1 = −1.
Proof. (⇒) As we mentioned in Section 2, gcd(a, d) = 1 is a necessary condition for S to be
pseudo-symmetric.
We first consider (x0 , y0 ) = (2, 0). We observe that (x1 , y1 ) = (1, 0). Otherwise ϕ(x0 , y0 ) −
ϕ(1, 0) = d ∈ S by Lemma 2.2, and then S = ha, ci, which is symmetric, a contradiction. If
a = 3, then Ap(S; 3) = {0, 3+d, 3+2d} and S = h3, 3+d, 3+2di, getting (a). Assume now that
a > 3. We have that (1, 1) ∈
/ L, otherwise ϕ(x0 , y0 ) − ϕ(1, 1) = d − c ∈ S, but this implies that
S = ha, ci, a contradiction. Then, the L-shape is L = {(1, 0), (2, 0)}∪{(0, λ) | 0 ≤ λ ≤ Pv+1 −1}.
From here we deduce that sv = 3, sv+1 = 2, a = Pv + 3 = Pv+1 + 2. Moreover, the equality
ϕ(0, i) + ϕ(0, Pv+1 − i) = ϕ(2, 0) for all i ∈ {1, . . . , Pv } yields that (a − 2)c = Pv+1 c = a + 2d
or, equivalently, that a(c − 1) = 2(c + d). To get (b) it only remains to prove that c is odd. We
proceed by contradiction. Assume that c is even, then the equality a(c − 1) = 2(c + d) proves that
a is also even. Since g(S) = 2d, then S = ha, a + d, ci. Hence, if we set S 0 = ha/2, a + d, c/2i,
then by (6) we get that ∆(S) = 2∆(S 0 ) 6= 1, and S is not pseudo-symmetric.
From now on, we assume that (x0 , y0 ) 6= (2, 0), then by Lemma 4.4 it follows that either
x0 = 0 or x0 ≡ 1 (mod k). We split the proof in two cases according to the value of g(S) given
by equation (10).
Case I: g(S) = ϕ(sv − sv+1 − 1, Pv+1 − 1) − a. If sv+1 = 0, then we observe that the L-shape
degenerates to a rectangle and, by the second part of Lemma 4.4, we obtain that S is symmetric
(we could also have obtained that S is symmetric by applying [4, Theorem 5]). If sv+1 > 0, then
by Lemma 4.1 we have that x1 = (2sv − sv+1 − 1)/2 and y1 = (Pv+1 − Pv − 1)/2. Moreover, by
Lemma 4.3 (a) we have that y1 = 0 and, hence, Pv+1 − Pv = 1. Moreover, by Lemma 4.3 (b) we
also have that (x1 + k, y1 ) ∈
/ L and, hence, x1 + k ≥ sv , which implies that sv+1 ≤ 2k − 1.
Since x1 > 0 then, by Lemma 4.3 (c), we have two subcases.
Subcase 1: If (x1 + 1, 0) ∈
/ L or, equivalently, sv+1 = 1. According to Lemma 4.4 we have
that either x0 = 0 or x0 ≡ 1 (mod k). If x0 = 0, then x1 = 1 and the identity 2ϕ(x1 , y1 ) =
ϕ(x0 , y0 ) + a implies that Pv c = a + 2d. However, this is not possible because 0 < Rv =
1
[(a + kd)sv − kcPv ] = 2 − k ≤ 0. If x0 ≡ 1 (mod k). Since k ≥ 2, we observe that
a

8

I. GARCÍA-MARCO, J.L. RAMÍREZ ALFONSÍN, AND Ø. J. RØDSETH

dx0 /ke = d(x0 + 1)/ke = (x0 − 1 + k)/k . Thus the identity 2ϕ(x1 , y1 ) = ϕ(x0 , y0 ) + a yields

x0 − 1
sv − 3
a + (x0 + 2)d =
a + dsv .
k
k
From here we directly deduce that Rv = a1 [(a + kd)sv − kcPv ] = 3 and we obtain (c).
Subcase 2: If x1 ≡ 1 (mod k). According to Lemma 4.4 we have that either x0 = 0 or
x0 ≡ 1 (mod k). If x0 = 0, then x1 = λk + 1 and (x1 + k, 0) ∈
/ L and thus λ = 0. This implies
that the Apéry set has Pv +2 = a elements and that Pv c = 2(a+d)−a and thus (a−2)c = a+2d.
However, the fact that Rv > 0 implies that (a + kd)sv − kcPv > 0, but this can only happen if
2a + 2kd − kc(a − 2) = 2a + 2kd − k(a + 2d) > 0, but this implies k = 1, a contradiction. If
x0 ≡ 1 (mod k), then we get that x0 = sv −2k and x1 = sv −k. Moreover, Pv c = a(sv −1)/k+dsv
and, hence, kcPv = (a + kd)sv − a. This implies that Rv = 1 and we obtain (d).
Case II: g(S) = ϕ(sv − 1, Pv+1 − Pv − 1) − a. Firstly, we shall prove that
(i) v = 0
(ii) s0 ≡ 2 (mod k)
(iii) s0 − s1 ∈ {1, 3}
Since x0 6= 0, by Lemma 4.4, we have that x0 ≡ 1 (mod k) and that g(S) + a = ϕ(x, y) +
ϕ(x0 − x, y0 − y) for all 0 ≤ x ≤ x0 and 0 ≤ y ≤ y0 . Then, by Lemma 4.1, x1 = (x0 − sv+1 )/2,
y1 = (y0 + Pv+1 )/2 and by Lemma 4.3 we get also that y1 = Pv+1 − 1 and that Pv = 1 yielding
to v = 0.
We observe that (d) is equivalent to prove that x1 = 0 or x1 = 1. By Lemma 4.3 we have
that x1 = 0 or x1 ≡ 1 (mod k). Nevertheless, also by Lemma 4.3 we obtain that x1 < k, so we
conclude that x1 ∈ {0, 1}.
Firstly we assume that s0 − s1 = 1, then we have that a = q1 s0 − s1 = (q1 − 1)s0 + 1.
Since v = 0, we have that R1 = q1 R0 − (a + kd) ≤ 0 and, hence, a + kd = q1 R0 + λ
for some λ ≥ 0. Moreover, aR0 = (a + kd)s0 − kcP0 = (q1 R0 + λ)s0 − kc, so we deduce
that kc = (R0 + λ)(s0 − 1) + λ. We observe that x1 = 0, y1 = y0 + 1. Then the equality
2ϕ(x1 , y1 ) = ϕ(x0 , y0 ) + a yields q1 c = ( s0k−2 + 2)a + (s0 − 1)d, which implies that kq1 c =
(s0 − 1)(a + kd) + (2k − 1)a. Then q1 (λs0 + s0 R0 − R0 ) = (s0 − 1)(q1 R0 + λ) + (2k − 1)a and
we derive that λa = (2k − 1)a. Therefore, λ = 2k − 1 and thus obtaining (e).
For s0 − s1 = 3, then we have that a = q1 s0 − s1 = (q1 − 1)s0 + 3.
Since v = 0, we have that R1 = q1 R0 − (a + kd) ≤ 0 and, hence, a + kd = q1 R0 + λ for
some λ ≥ 0. Moreover, aR0 = (a + kd)s0 − kcP0 = (q1 R0 + λ)s0 − kc, so we deduce that
kc = (R0 + λ)(s0 − 3) + 3λ. We observe that x1 = 1, y1 = y0 + 1. Then the equality 2ϕ(x1 , y1 ) =
ϕ(x0 , y0 ) + a yields q1 c = ( s0k−2 )a + (s0 − 3)d, which implies that kq1 c = (s0 − 3)(a + kd) + a.
Then q1 (λs0 + s0 R0 − 3R0 ) = (s0 − 3)(q1 R0 + λ) + a and we derive that λa = a. Thus, λ = 1
and we conclude (f).
(⇐) In (a) it is clear that Ap(S, 3) = {0, 3 + d, 3 + 2d} and that S is pseudo-symmetric. In (b),
the equality c−1
a = c + d yields that s0 = a − 1, then si = a − 1 − i, Pi = i + 1 and qi = 2 for
2
all i. We also observe that Ra−4 > 0, indeed,
(11)

Pv c =

Ra−4 = (3(a + kd) − kc(a − 3))/a = 3 + (3d − (a − 3)c)k/a
= 3 + (3d − a − 2d + c)k/a
= 3 − k + k(d + c)/a
= 3 + k(c + 1)/2 > 0,
and that Ra−3 = (2(a + kd) − kc(a − 2))/a = (2(a + kd) − k(a + 2d))/a = 2 − k ≤ 0. Then
v = a − 4, the L-shape corresponds to the one in Figure 3 and it is straightforward to check that
S is pseudo-symmetric.
Both in (c) and (d) we have that (x0 , y0 ) = (sv − sv+1 − 1, Pv+1 − 1) and it is easy to check
that S satisfies Lemma 2.2 (b) and, hence, it is pseudo-symmetric. For (e) and (f) we observe that

NUMERICAL SEMIGROUPS II: PSEUDO-SYMMETRIC AA-SEMIGROUPS

9

a−3
a−4
...
1
0

1

2

F IGURE 3. L-shape in Theorem 4.5(b)
v = 0, we obtain that (x0 , y0 ) = (s0 − 1, P1 − 2) and, again, it is easy to check that S satisfies
Lemma 2.2 (b) and, hence, S is pseudo-symmetric.

From Theorem 4.5 we deduce that the decision problem that receives as input a, k, d, c and
asks if the corresponding AA-semigroup S is pseudo-symmetric is solvable in polynomial time.
Indeed, Theorem 4.5 yields an algorithm for determining whether an AA-semigroup is pseudosymmetric that relies on the computation of some values of si , Ri , Pi and, in [4, Theorem 6], the
authors proposed a polynomial time method to compute these values. As we mentioned in the introduction, a semigroup is irreducible if and only if it is either symmetric or pseudo-symmetric. In
[4], it is proved that one can check in polynomial time whether an AA-semigroup S is symmetric.
Hence, we directly derive the following.
Corollary 4.6. Given a, k, d, c ∈ Z+ , the decision problem: "is the AA-semigroup S = ha, a +
d, . . . , a + kd, ci irreducible?", is solvable in polynomial time.
Our second characterization gives a method to construct any pseudo-symmetric AA-semigroup.
We first need the following
Lemma 4.7. If Pj+1 − Pj = 1 for some j in the interval −1 ≤ j ≤ m, then
qi+1 = 2 for

i = 0, 1, . . . , j,

and
Pi = i + 1

for i = −1, 0 . . . , j + 1.

Proof. We have
Pi+1 = qi+1 Pi − Pi−1 ≥ 2Pi − Pi ,

so that Pi+1 − Pi ≥ Pi − Pi−1 for all i. Hence

1 = Pj+1 − Pj ≥ Pj − Pj−1 ≥ · · · ≥ P0 − P−1 = 1,
and the lemma follows.



Remark 4.8. The condition sv+1 = 1 is equivalent to v + 1 = m and sm = gcd(a, c) = 1. Then,
by Lemma 4.7, Theorem 4.5 (a) is equivalent to gcd(a, c) = 1, sm−1 ≡ 3 (mod k), Pm+1 = m + 2
and Rm−1 = 3.
Theorem 4.9. Let S = ha, a + d, . . . , a + kd, ci with a, d, c ∈ Z+ and k ≥ 2. Then, S is
pseudo-symmetric if and only if gcd(a, d) = 1 and one of the following conditions holds:
(a) S = h3, 3 + d, 3 + 2di
(b) a(c − 1) = 2(c + d) with c odd,
(c.1) a ≡ 1 or 5 (mod 6), c(a − 3) = 6d, and a ≤ 2kd + 3,

10

I. GARCÍA-MARCO, J.L. RAMÍREZ ALFONSÍN, AND Ø. J. RØDSETH

(c.2) there exist λ, µ ≥ 1 and m ≥ 1 such that

a = (2 + λk)(m + 1) + 1, c + (2 + λk)d = µa,
cm − 3d
and a + kd =
,
λ
(d) there exist λ ≥ 2, µ ≥ 1 and v ≥ 0 such that

a = (v + 1)(2 + (λ − 2)k) + (λk + 1), c + (2 + (λ − 2)k)d = µa,
c(v + 1) − d
,
and a + kd =
λ
(e) there exist q1 ≥ 2, R0 ≡ 2 (mod k) and s0 ≡ 2 (mod k) such that

a = (q1 − 1)s0 + 1, a + kd = q1 R0 + 2k − 1 and kc = (R0 + 2k − 1)(s0 − 1) + 2k − 1,
(f) there exist q1 ≥ 2, R0 ≡ 2 (mod k) and s0 ≡ 2 (mod k), s0 6= 2 such that

a = (q1 − 1)s0 + 3, a + kd = q1 R0 + 1 and kc = (R0 + 1)(s0 − 3) + 3.

Proof. Conditions (a) and (b) are equal to Theorem 4.5(a) and (b), respectively. We first start
proving that the condition in Theorem 4.5 (c) is equivalent to either (c.1) or (c.2). In Theorem 4.5
(c) we have Rv = 3 or, equivalently, 3a = (a + kd)sv − kcPv , sv+1 = 1 and Pv+1 = Pv + 1, so
from the inequality Rv+1 ≤ 0 we obtain that
(12) (a + kd)sv+1 − kcPv+1 = a + kd − kc − kcPv = a − 2kd − kc − (sv − 3)(a + kd) ≤ 0.

Since sv > sv+1 = 1 and sv ≡ 3 (mod k), then (12) holds if and only if sv > 3, or sv = 3 and
a − 2kd − kc ≤ 0.
Assume first that sv = 3, then a = sv Pv+1 − sv+1 Pv = 2Pv + 3. Moreover, Rv = 3 implies
that 3d = cPv , so we get that 6d = c(a − 3). We claim that a is not multiple of 3. Otherwise,
since a is odd, then a − 3 is multiple of 6 and we get that c divides d implying that S = ha, ci,
which is symmetric, a contradiction. Inequality (12) and the equality 6d = c(a − 3) imply now
that a ≤ 2kd + 3, getting (c.1).
When sv > 3, then sv = 3 + λk for some λ ≥ 1. By Remark 4.8, we get that v = m − 1 and that
Pm = Pm−1 + 1. By Lemma 4.7 we get that qi = 2 for all i and, since, sm = 1, sm−1 = 3 + λk,
we get that sm−i = 1 + i(2 + λk) for all i. In particular, a = s−1 = (2 + λk)(m + 1) + 1 and
s0 = a − (2 + λk). From the condition ds0 ≡ c (mod a) we deduce that there exists µ ≥ 1 such
that µa = c + d(2 + λk). Finally, Rm−1 = 3 implies that a + kd = (cm − 3d)/λ, getting (c.2).
Conversely, if (c.1) holds, then the equality 6d = c(a − 3) yields that 6d ≡ −3c (mod a) and
a is not a multiple of 3, so d(a − 2) ≡ c (mod a) and we get that s0 = a − 2. From here we
easily derive that qi = 2, si = a − 2(i + 1) and Pi = i + 1 for all i and m = (a − 3)/2. From
these values we easily get that Rm−1 = 3 and by Remark 4.8 we obtain that we are under the
conditions of Theorem 4.5 (c). If (c.2) holds, then s0 is the only integer in 0 ≤ s0 ≤ a − 1 such
that ds0 ≡ c (mod a), which is s0 = a − (2 + λk) = (2 + λk)m + 1. Thus, the equalities
si = qi+2 si+1 − si+2 with 0 ≤ si+2 < si+1 for all i ≤ m − 1 yield that si = (2 + λk)(m − i) + 1
for all i ∈ {−1, . . . , m} and qi = 2 for all i. Hence, Pm+1 = m + 2 and sm−1 = 3 + λk. We also
easily get that Rm−1 = 3, so by Remark 4.8 we also recover the conditions of Theorem 4.5 (c).
The proof that (d) is equivalent to Theorem 4.5 (d) is analogue (but easier) to the previous one,
with the only differences that the role of m is played by v + 1 and that Rv = 1 directly implies
that Rv+1 ≤ 0, so we do not need to impose the condition Rv+1 ≤ 0.
Let us prove that conditions in Theorem 4.5 (e) are equivalent to (e). Firstly, the fact that
s1 = s0 − 1 implies that a = (q1 − 1)s0 + 1. We observe that P1 = q1 and the condition
R1 = 1 − 2k implies that R1 = q1 R0 − R−1 = q1 R0 − (a + kd) = 1 − 2k. Finally the equality
aR0 = (a + kd)s0 − kc yields that kc = (R0 + 2k − 1)(s0 − 1) + 2k − 1. If we take residues
modulo k in this equality we conclude that R0 ≡ 2 (mod k). The converse is straightforward.
The proof that (f) is equivalent to Theorem 4.5 (f) is analogue to one above.


NUMERICAL SEMIGROUPS II: PSEUDO-SYMMETRIC AA-SEMIGROUPS

11

R EFERENCES
[1] V. Barucci, D. E. Dobbs, M. Fontana, Maximality properties in numerical semigroups and applications to onedimensional analytically irreducible local domains, Memoirs Amr. Math. Soc, 125(598) (1997)
[2] R. Fröberg, C. Gottlieb, R. Häggkvist, On numerical semigroups, Semigroup Forum 35, 63–83 (1987)
[3] G. L. Matthews, On semigroups generated by generalized arithmetic sequences, Comm. Algebra 32 (9) (2004),
3459–3469.
[4] J. L. Ramírez Alfonsín, Ø. J. Rødseth, Numerical semigroups: Apéry sets and Hilbert series, Semigroup Forum
79, 323-340 (2009).
[5] Ø. J. Rødseth, On a linear diophantine problem of Frobenius II, J. Reine Angew. Math. 307/308, 431–440 (1979)
[6] J. C. Rosales, M. B. Branco, Irreducible numerical semigroups, Pacific J. Math. 200(1), 131–143 (2003)
[7] J. C. Rosales, P. A. García-Sánchez, Pseudo-symmetric numerical semigroups with three generators, J. Algebra
291, 46–54 (2005)
[8] E. S. Selmer, On the linear diophantine problem of Frobenius, J. Reine Angew. Math. 293/294 (1977), 1–17.
LIP, ENS LYON - CNRS -UCBL - INRIA, U NIVERSITÉ DE LYON UMR 5668, LYON , F RANCE
E-mail address: ignacio.garcia-marco@ens-lyon.fr, iggarcia@ull.es
U NIVERSITÉ DE M ONTPELLIER , I NSTITUT M ONTPELLIÉRAIN A LEXANDER G ROTHENDIECK , C ASE C OUR 051, P LACE E UGÈNE BATAILLON , 34095 M ONTPELLIER C EDEX 05, F RANCE
E-mail address: jramrez@univ-montp2.fr

RIER

D EPARTMENT OF M ATHEMATICS , U NIVERSITY OF B ERGEN , J OHS . B RUNSGT. 12, N-5008 B ERGEN , N OR WAY

E-mail address: rodseth@math.uib.no

