arXiv:1706.09765v1 [math.NT] 29 Jun 2017

Numerical Semigroups and Codes
Maria Bras-Amorós
Chapter 5 of Algebraic Geometry Modeling in Information Theory,
E. Martinez-Moro (ed.), World Scientific, 2013.

Abstract
A numerical semigroup is a subset of N containing 0, closed under addition and with finite complement in N. An important example of numerical
semigroup is given by the Weierstrass semigroup at one point of a curve.
In the theory of algebraic geometry codes, Weierstrass semigroups are crucial for defining bounds on the minimum distance as well as for defining
improvements on the dimension of codes. We present these applications
and some theoretical problems related to classification, characterization
and counting of numerical semigroups.

Contents
1 Numerical semigroups
3
1.1 Paradigmatic example: Weierstrass semigroups on algebraic curves 3
1.1.1 Algebraic curves . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2 Weierstrass semigroup . . . . . . . . . . . . . . . . . . . .
4
1.1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2 Basic notions and problems . . . . . . . . . . . . . . . . . . . . .
7
1.2.1 Genus, conductor, gaps, non-gaps, enumeration . . . . .
7
1.2.2 Generators, Apéry set . . . . . . . . . . . . . . . . . . . .
7
1.2.3 Frobenius’ coin exchange problem . . . . . . . . . . . . .
8
1.2.4 Hurwitz question . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.5 Wilf conjecture . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3.1 Symmetric and pseudo-symmetric numerical semigroups
9
1.3.2 Arf numerical semigroups . . . . . . . . . . . . . . . . . . 10
1.3.3 Numerical semigroups generated by an interval . . . . . 12
1.3.4 Acute numerical semigroups . . . . . . . . . . . . . . . . 13
1.4 Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.1 Homomorphisms of semigroups . . . . . . . . . . . . . . 16
1.4.2 The ⊕ operation, the ν sequence, and the τ sequence . . 16
1.4.3 Characterization of a numerical semigroup by ⊕ . . . . . 19
1.4.4 Characterization of a numerical semigroup by ν . . . . . 19
1

1.4.5 Characterization of a numerical semigroup by τ . . . . .
Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22
23

2 Numerical semigroups and codes
2.1 One-point codes and their decoding . . . . . . . . . . . . . . . .
2.1.1 One-point codes . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Decoding one-point codes . . . . . . . . . . . . . . . . . .
2.2 The ν sequence, classical codes, and Feng-Rao improved codes .
2.2.1 The ν sequence and the minimum distance of classical
codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 On the order bound on the minimum distance . . . . . .
2.2.3 The ν sequence and Feng-Rao improved codes . . . . . .
2.2.4 On the improvement of the Feng-Rao improved codes .
2.3 Generic errors and the τ sequence . . . . . . . . . . . . . . . . .
2.3.1 Generic errors . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.2 Conditions for correcting generic errors . . . . . . . . . .
2.3.3 Comparison of improved codes and classical codes correcting generic errors . . . . . . . . . . . . . . . . . . . . .
2.3.4 Comparison of improved codes correcting generic errors
and Feng–Rao improved codes . . . . . . . . . . . . . . .

26
26
26
27
29

1.5

29
30
36
36
37
37
39
39
41

Introduction
Numerical semigroups are probably one of the most simple mathematical objects. However they are involved in very hard (and some very old) problems.
They can also be found in several applied fields such as error-correcting codes,
cryptography, or combinatorial structures for privacy applications.
In the present chapter we present numerical semigroups with some of the
related classical problems and we explore their importance in the field of algebraicgeometry codes.
The material is divided into two parts. In the first part we give a brief introduction to Weierstrass semigroups as the paradigmatic example of numerical
semigroups, we present some classical problems related to general numerical
semigroups, we deal with some problems on classification and characterization
of numerical semigroups which have an application to coding theory, and we
finally present a conjecture on counting numerical semigroups by their genus.
In the second part we present one-point algebraic-geometry codes and we
focus on the applications that numerical semigroups have for defining bounds
on the minimum distance as well as for defining improvements on the dimension of these codes. Based on the decoding algorithm for one-point codes one
can deduce sufficient conditions for decoding, and from these conditions one
can define minimal sets of parity checks (and so codes with improved correction capability) either for correcting any kind of error or at least for guaranteeing the correction of the so-called generic errors. The decoding conditions are

2

related to the associated Weierstrass semigroups and so the improvements can
be defined in terms of semigroups.

1 Numerical semigroups
1.1 Paradigmatic example: Weierstrass semigroups on algebraic
curves
1.1.1 Algebraic curves
Consider a field K and a bivariate polynomial f (x, y) ∈ K[x, y]. If K̄ is the
algebraic closure of K, the (plane) affine curve associated to f is the set of points
in K̄ 2 at which f vanishes. Now given a homogeneous polynomial F (X, Y, Z) ∈
K[X, Y, Z] the (plane) projective curve associated to F is the set of points in
P2 (K̄) at which F vanishes. We use the notation XF to denote it.
From the affine curve defined by the polynomial f (x, y) of degree d we can
obtain a projective curve defined by the homogenization of f , that is, f ∗ (X, Y, Z) =
Y
Z df ( X
Z , Z ). Conversely, a projective curve defined by a homogeneous polynomial F (X, Y, Z) defines three affine curves with dehomogenized polynomials
F (x, y, 1), F (1, u, v), F (w, 1, z). The points (a, b) ∈ K̄ 2 of the affine curve defined by f (x, y) correspond to the points (a : b : 1) ∈ P2 (K̄) of Xf ∗ . Conversely,
the points (X : Y : Z) with Z 6= 0 (resp. X 6= 0, Y 6= 0) of a projective
curve XF correspond to the points of the affine curve defined by F (x, y, 1)
(resp. F (1, u, v), F (w, 1, z)) and so they are called affine points of F (x, y, 1).
The points with Z = 0 are said to be at infinity.
In the case K = Fq , any point of XF is in P2 (Fqm ) for some m. If L/K is
a field extension we define the L-rational points of X as the points in the set
XF (L) = XF ∩ L2 .
We will assume that F is irreducible in any field extension of K (i.e. absolutely irreducible). Otherwise the curve is a proper union of two curves.
If two polynomials in K(X, Y, Z) differ by a multiple of F , when evaluating them at a point of XF we obtain the same value. Thus it makes sense to
consider K(X, Y, Z)/(F ). Since F is irreducible, K(X, Y, Z)/(F ) is an integral
domain and we can construct its field of fractions QF . For evaluating one such
fraction at a projective point we want the result not to depend on the representative of the projective point. Hence, we require the numerator and the denominator to have one representative each, which is a homogeneous polynomial
and both having the same degree. The function field of XF , denoted K(XF ),
is the set of elements of QF admitting one such representation. Its elements
are the rational functions of XF . We say that a rational function f ∈ K(XF ) is
G(X,Y,Z)
regular in a point P if there exists a representation of it as a fraction H(X,Y,Z)
G(P )
with H(P ) 6= 0. In this case we define f (P ) = H(P
) . The ring of all rational
functions regular in P is denoted OP . Again it is an integral domain and this
time its field of fractions is K(XF ).

3

Let P ∈ XF be a point. If all the partial derivatives FX , FY , FZ vanish at
P then P is said to be a singular point. Otherwise it is said to be a simple point.
Curves without singular points are called non-singular, regular or smooth curves.
From now on we will assume that F is absolutely irreducible and that XF
is smooth.
The genus of a smooth plane curve XF may be defined as
g=

(deg(F ) − 1)(deg(F ) − 2)
.
2

For general curves the genus is defined using differentials on a curve which is
out of the purposes of this survey.
1.1.2 Weierstrass semigroup
Theorem 1. Consider a point P in the projective curve XF . There exists t ∈ OP such
that for any non-zero f ∈ K(XF ) there exists a unique integer vP (f ) with
f = tvP (f ) u
for some u ∈ OP with u(P ) 6= 0. The value vP (f ) depends only on XF , P .
If G(X, Y, Z) and H(X, Y, Z) are two homogeneous polynomials of degree 1 such
that G(P ) = 0, H(P ) 6= 0, and G is not a constant multiple of FX (P )X +FY (P )Y +
G(X,Y,Z)
.
FZ (P )Z, then we can take t to be the class in OP of H(X,Y,Z)
An element such as t is called a local parameter. If there is no confusion we
G(X,Y,Z)
will write H(X,Y,Z)
for its class in OP . The value vP (f ) is called the valuation of
f at P . The point P is said to be a zero of multiplicity m if vP (f ) = m > 0 and a
pole of multiplicity −m if vP (f ) = m < 0. The valuation satisfies that vP (f ) > 0
if and only if f ∈ OP and that in this case vP (f ) > 0 if and only if f (P ) = 0.
Lemma 2.

1. vP (f ) = ∞ if and only if f = 0

2. vP (λf ) = vP (f ) for all non-zero λ ∈ K
3. vP (f g) = vP (f ) + vP (g)
4. vP (f + g) > min{vP (f ), vP (g)} and equality holds if vP (f ) 6= vP (g)
5. If vP (f ) = vP (g) > 0 then there exists λ ∈ K such that vP (f − λg) > vP (f ).
Let L(mP ) be the set of rational functions having only poles at P and with
pole order at most m. It is a K-vector space and so we can define l(mP )=
dimK (L(mP )). One can prove that l(mP ) is either l((m−1)P ) or l((m−1)P )+1.
There exists a rational function f ∈ K(XF ) having only one pole at P with
vP (f ) = −m if
S and only if l(mP ) = l((m − 1)P ) + 1.
Let A = m>0 L(mP ), that is, A is the ring of rational functions having
poles only at P . Define Λ = {−vP (f ) : f ∈ A \ {0}}. It is obvious that Λ ⊆ N0 ,
where N0 denotes the set of all non-negative integers.
4

Lemma 3. The set Λ ⊆ N0 satisfies
1. 0 ∈ Λ
2. m + m′ ∈ Λ whenever m, m′ ∈ Λ
3. N0 \ Λ has a finite number of elements
Proof.

1. Constant functions f = a have no poles and satisfy vP (a) = 0 for
all P ∈ XF . Hence, 0 ∈ Λ.

2. If m, m′ ∈ Λ then there exist f, g ∈ A with vP (f ) = −m, vP (g) = −m′ .
Now, by Lemma 2, vP (f g) = −(m + m′ ) and so m + m′ ∈ Λ.
3. The well-known Riemann-Roch theorem implies that l(mP ) = m + 1 − g
if m > 2g − 1. On one hand this means that m ∈ Λ for all m > 2g, and on
the other hand, this means that l(mP ) = l((m − 1)P ) only for g different
values of m. So, the number of elements in N0 which are not in Λ is equal
to the genus.
The three properties of a subset of N0 in the previous lemma will constitute
the definition of a numerical semigroup. The particular numerical semigroup of
the lemma is called the Weierstrass semigroup at P and the elements in N0 \ Λ
are called the Weierstrass gaps.
1.1.3 Examples
Example 4 (Hermitian curve). Let q be a prime power. The Hermitian curve Hq
over Fq2 is defined by the affine equation xq+1 = y q + y and homogeneous equation
X q+1 − Y q Z − Y Z q = 0. It is easy to see that its partial derivatives are FX = X q ,
FY = −Z q , FZ = −Y q and so there is no projective point at which Hq is singular.
The point P∞ = (0 : 1 : 0) is the unique point of Hq at infinity.
We have FX (P∞ )X + FY (P∞ )Y + FZ (P∞ )Z = −Z and so t = X
Y is a local
Y
X
parameter at P∞ . The rational functions Z and Z are regular everywhere except
at P∞ . So, they belong to ∪m>0 L(mP
the homogeneous
q∞ ). One can derive from
q
equation of the curve that tq+1 = YZ + YZ . So, vP∞ ( YZ + YZ ) = q + 1. By
Lemma 2 one can deduce that vP∞ ( YZ ) = q + 1 and so vP∞ ( YZ ) = −(q + 1). On the
q+1
q
other hand, since X
= YZ + YZ , we have (q + 1)vP∞ ( X
Z
Z ) = −q(q + 1). So,
)
=
−q.
vP∞ ( X
Z
We have seen that q, q + 1 ∈ Λ. In this case Λ contains what we will call later the
= g elements.
semigroup generated by q, q + 1 whose complement in N0 has q(q−1)
2
Since we know that the complement of Λ in N0 also has g elements, this means that
both semigroups are the same.
For further details on the Hermitian curve see [66, 35].

5

Example 5 (Klein quartic). The Klein quartic over Fq is defined by the affine equation x3 y + y 3 + x = 0. We shall see that if gcd(q, 7) = 1 then K is smooth. Its defining
homogeneous polynomial is F = X 3 Y + Y 3 Z + Z 3 X and its partial derivatives are
FX = 3X 2 Y + Z 3 , FY = 3Y 2 Z + X 3 , FZ = 3Z 2 X + Y 3 . If the characteristic of Fq2
is 3 then FX = FY = FZ = 0 implies X 3 = Y 3 = Z 3 = 0 and so X = Y = Z = 0.
Hence there is no projective point P = (X : Y : Z) at which K is singular. Otherwise, if the characteristic of Fq2 is different than 3 then FX = FY = FZ = 0 implies
X 3 Y = −3Y 3 Z and Z 3 X = −3X 3 Y = 9Y 3 Z. Now the equation of the curve
translates to −3Y 3 Z + Y 3 Z + 9Y 3 Z = 7Y 3 Z = 0. By hypothesis gcd(q, 7) = 1
and so either Y = 0 or Z = 0. In the first case, FY = 0 implies X = 0 and FX = 0
implies Z = 0, a contradiction, and in the second case, FY = 0 implies X = 0 and
FZ = 0 implies Y = 0, another contradiction.
Let P0 = (0 : 0 : 1). One can easily check that P0 ∈ K. We have FX (P0 )X +
FY (P0 )Y +FZ (P0 )Z = X and so t = YZ is a local parameter at P0 . From the equation
3 Z
3
of the curve we get X
+ Y + YZ X
Y
Y = 0. So, at least one of the next equalities
holds
Z
• 3vP0 ( X
Y ) = vP0 ( Y )
Z
X
• 3vP0 ( X
Y ) = 3vP0 ( Y ) + vP0 ( Y )

• vP0 ( YZ ) = 3vP0 ( YZ ) + vP0 ( X
Y )
Since t = YZ is a local parameter at P0 , vP0 ( YZ ) = −1. Now, since vP0 ( X
Y ) is an
integer, only the third equality is possible, which leads to the conclusion that vP0 ( X
Y )=
3 Y

Y 3
X
2. Similarly, X
+
=
0
gives
that
at
least
one
of
the
next
equalities
+
Z
Z
Z
Z
holds
Y
Y
• 3vP0 ( X
Z ) + vP0 ( Z ) = 3vP0 ( Z )
Y
X
• 3vP0 ( X
Z ) + vP0 ( Z ) = vP0 ( Z )

• 3vP0 ( YZ ) = vP0 ( X
Z)
Again only the third equality is possible and this leads to vP0 ( X
Z ) = 3.
i j
Z
Now we consider the rational functions fij = YX i+j
. We have already seen that
vP0 (fij ) = −2i − 3j and we want to see under which conditions fij ∈ ∪m>0 L(mP0 ).
This is equivalent to see when it has no poles rather than P0 . The poles of fij may only
be at points with X = 0 and so only at P0 and P1 = (0 : 1 : 0). Using the symmetries
Z
Y
) = −1, vP1 ( X
) = 2. So, vP1 (fij ) = −i + 2j. Then
of the curve we get vP1 ( X
fij ∈ ∪m>0 L(mP0 ) if and only if −i + 2j > 0. We get that Λ contains {2i + 3j :
i, j > 0, 2j > i} = {0, 3, 5, 6, 7, 8, . . . }. This has 3 gaps which is exactly the genus of
K. So,
Λ = {0, 3, 5, 6, 7, 8, 9, 10, . . .}.
It is left as an exercise to prove that all this can be generalized to the curve Km with
defining polynomial F = X m Y + Y m Z + Z m X, provided that gcd(1, m2 − m + 1) =
1. In this case vP0 (fij ) = −(m − 1)i − mj and fij ∈ ∪m>0 L(mP0 ) if and only if
6

−i + (m − 1)j > 0. Since (m − 1)i + mj = (m − 1)i′ + mj ′ for some (i′ , j ′ ) 6= (i, j)
if and only if i > m or j > m − 1 we deduce that
{−vP0 (fij ) : fij ∈ ∪m>0 L(mP0 )} = {(m−1)i+mj : (i, j) 6= (1, 0), (2, 0), . . . , (m−1, 0)}.
This set has exactly m(m−1)
gaps which is the genus of Km . So it is exactly the
2
Weierstrass semigroup at P0 . For further details on the Klein quartic we refer the
reader to [56, 35].

1.2 Basic notions and problems
A numerical semigroup is a subset Λ of N0 containing 0, closed under summation and with finite complement in N0 . A general reference on numerical semigroups is [59].
1.2.1 Genus, conductor, gaps, non-gaps, enumeration
For a numerical semigroup Λ define the genus of Λ as the number g = #(N0 \Λ)
and the conductor of Λ as the unique integer c ∈ Λ such that c − 1 6∈ Λ and
c + N0 ⊆ Λ. The elements in Λ are called the non-gaps of Λ while the elements
in N0 \ Λ are called the gaps of Λ. The enumeration of Λ is the unique increasing
bijective map λ : N0 −→ Λ. We will use λi for λ(i).
Lemma 6. Let Λ be a numerical semigroup with conductor c, genus g, and enumeration λ. The following are equivalent.
(i) λi > c
(ii) i > c − g
(iii) λi = g + i
Proof. First of all notice that if g(i) is the number of gaps smaller than λi , then
λi = g(i)+ i. To see that (i) and (iii) are equivalent notice that λi > c ⇐⇒ g(i) =
g ⇐⇒ g(i) + i = g + i ⇐⇒ λi = g + i. Now, from this equivalence we deduce
that c = λc−g . Since λ is increasing we deduce that λi > c = λc−g if and only if
i > c − g.
1.2.2 Generators, Apéry set
The generators of a numerical semigroup are those non-gaps which can not be
obtained as a sum of two smaller non-gaps. If a1 , . . . , al are the generators
of a semigroup Λ then Λ = {n1 a1 + · · · + nl al : n1 , . . . , nl ∈ N0 } and so
a1 , . . . , al are necessarily coprime. If a1 , . . . , al are coprime, we call {n1 a1 +
· · · + nl al : n1 , . . . , nl ∈ N0 } the semigroup generated by a1 , . . . , al and denote it
by ha1 , . . . , al i.
The non-gap λ1 is always a generator. If for each integer i from 0 to λ1 − 1
we consider wi to be the smallest non-gap in Λ that is congruent to i modulo λ1 , then each non-gap of Λ can be expressed as wi + kλ1 for some i ∈
7

{0, . . . , λ1 − 1} and some k ∈ N0 . So, the generators different from λ1 must
be in {w1 , . . . , wλ1 −1 } and this implies that there is always a finite number of
generators. The set {w0 , w1 , . . . , wλ1 −1 } is called the Apéry set of Λ and denoted
Ap(Λ). It is easy to check that it equals {l ∈ Λ : l − λ1 6∈ Λ}. References related
to the Apéry set are [1, 25, 60, 62, 43].
1.2.3 Frobenius’ coin exchange problem
Frobenius suggested the problem to determine the largest monetary amount
that can not be obtained using only coins of specified denominations. A lot
of information on the Frobenius’ problem can be found in Ramı́rez Alfonsı́n’s
book [57].
If the different denominations are coprime then the set of amounts that can
be obtained form a numerical semigroup and the question is equivalent to determining the largest gap. This is why the largest gap of a numerical semigroup
is called the Frobenius number of the numerical semigroup.
If the number of denominations is two and the values of the coins are a, b
with a, b coprime, then Sylvester’s formula [69] gives that the Frobenius number is
ab − a − b.
However, when the number of denominations is larger, there is no closed
polynomial form as can be derived from the next result due to Curtis [18].
Theorem 7. There is no finite set of polynomials {f1 , . . . , fn } such that for each choice
of a, b, c ∈ N, there is some i such that the Frobenius number of a, b, c is fi (a, b, c).
1.2.4 Hurwitz question
It is usually attributed to Hurwitz the problem of determining whether there
exist non-Weierstrass numerical semigroups, to which Buchweitz gave a positive answer, and the problem of characterizing Weierstrass semigroups. For
these questions we refer the reader to [71, 38, 41] and all the citations therein.
A related problem is bounding the number of rational points of a curve
using Weierstrass semigroups. One can find some bounds in [68, 42, 30]
1.2.5 Wilf conjecture
The Wilf conjecture ([73, 19]) states that the number e of generators of a numerical semigroup of genus g and conductor c satisfies
e>

c
.
c−g

It is easy to check it when the numerical semigroup is symmetric, that is, when
c = 2g. In [19] the inequality is proved for many other cases. In [8] it was
proved by brute approach that any numerical semigroup of genus at most 50
also satisfies the conjecture.
8

1.3 Classification
1.3.1 Symmetric and pseudo-symmetric numerical semigroups
Definition 8. A numerical semigroup Λ with genus g and conductor c is said to be
symmetric if c = 2g.
Symmetric numerical semigroups have been widely studied. For instance
in [39, 35, 16, 12].
Example 9. Semigroups generated by two integers are the semigroups of the form
Λ = {ma + nb : a, b ∈ N0 }
for some integers a and b. For Λ having finite complement in N0 it is necessary that
a and b are coprime integers. Semigroups generated by two coprime integers are symmetric [39, 35].
Geil introduces in [29] the norm-trace curve over Fqr defined by the affine equation
r
r−1
r−2
x(q −1)/(q−1) = y q
+ yq
+ ···+ y
where q is a prime power. It has a single rational point at infinity and the Weierstrass
semigroup at the rational point at infinity is generated by the two coprime integers
(q r − 1)/(q − 1) and q r−1 . So, it is an example of a symmetric numerical semigroup.
Properties on semigroups generated by two coprime integers can be found in [39].
For instance, the semigroup generated by a and b, has conductor equal to (a−1)(b−1),
and any element l ∈ Λ can be written uniquely as l = ma + nb with m, n integers
such that 0 6 m < b.
From the results in [35, Section 3.2] one can get, for any numerical semigroup Λ
generated by two integers, the equation of a curve having a point whose Weierstrass
semigroup is Λ.
Let us state now a lemma related to symmetric numerical semigroups.
Lemma 10. A numerical semigroup Λ with conductor c is symmetric if and only if
for any non-negative integer i, if i is a gap, then c − 1 − i is a non-gap.
The proof can be found in [39, Remark 4.2] and [35, Proposition 5.7]. It follows by counting the number of gaps and non-gaps smaller than the conductor
and the fact that if i is a non-gap then c − 1 − i must be a gap because otherwise
c − 1 would also be a non-gap.
Definition 11. A numerical semigroup Λ with genus g and conductor c is said to be
pseudo-symmetric if c = 2g − 1.
Notice that a symmetric numerical semigroup can not be pseudo-symmetric.
Next lemma as well as its proof is analogous to Lemma 10.
Lemma 12. A numerical semigroup Λ with odd conductor c is pseudo-symmetric if
and only if for any non-negative integer i different from (c − 1)/2, if i is a gap, then
c − 1 − i is a non-gap.
9

Example 13. The Weierstrass semigroup at P0 of the Klein quartic of Example 5 is
Λ = {0, 3} ∪ {i ∈ N0 : i > 5}. In this case c = 5 and the only gaps different from
(c − 1)/2 are l = 1 and l = 4. In both cases we have c − 1 − l ∈ Λ. This proves that
Λ is pseudo-symmetric.
In [58] the authors prove that the set of irreducible semigroups, that is, the
semigroups that can not be expressed as a proper intersection of two numerical
semigroups, is the union of the set of symmetric semigroups and the set of
pseudo-symmetric semigroups.
1.3.2 Arf numerical semigroups
Definition 14. A numerical semigroup Λ with enumeration λ is called an Arf numerical semigroup if λi + λj − λk ∈ Λ for every i, j, k ∈ N0 with i > j > k
[17].
For further work on Arf numerical semigroups and generalizations we refer
the reader to [2, 61, 13, 46]. For results on Arf semigroups related to coding
theory, see [4, 17].
Example 15. It is easy to check that the Weierstrass semigroup in Example 5 is Arf.
Let us state now two results on Arf numerical semigroups that will be used
later.
Lemma 16. Suppose Λ is Arf. If i, i + j ∈ Λ for some i, j ∈ N0 , then i + kj ∈ Λ for
all k ∈ N0 . Consequently, if Λ is Arf and i, i + 1 ∈ Λ, then i > c.
Proof. Let us prove this by induction on k. It is obvious for k = 0 and k = 1. If
k > 0 and i, i + j, i + kj ∈ Λ then (i + j) + (i + kj) − i = i + (k + 1)j ∈ Λ.
Consequently, Arf semigroups are sparse semigroups [46], that is, there are
no two non-gaps in a row smaller than the conductor.
Let us give the definition of inductive numerical semigroups. They are an
example of Arf numerical semigroups.
Definition 17. A sequence (Hn ) of numerical semigroups is called inductive if there
exist sequences (an ) and (bn ) of positive integers such that H1 = N0 and for n > 1,
Hn = an Hn−1 ∪ {m ∈ N0 : m > an bn−1 }. A numerical semigroup is called
inductive if it is a member of an inductive sequence [55, Definition 2.13].
One can see that inductive numerical semigroups are Arf [17].
Example 18. Pellikaan, Stichtenoth and Torres proved in [54] that the numerical
semigroups for the codes over Fq2 associated to the second tower of Garcia-Stichtenoth
attaining the Drinfeld-Vlăduţ bound [27] are given recursively by Λ1 = N0 and, for
m > 0,
Λm = q · Λm−1 ∪ {i ∈ N0 : i > q m − q ⌊(m+1)/2⌋ }.
They are examples of inductive numerical semigroups and hence, examples of Arf numerical semigroups.
10

Example 19. Hyperelliptic numerical semigroups. These are the numerical semigroups generated by 2 and an odd integer. They are of the form
Λ = {0, 2, 4, . . . , 2k − 2, 2k, 2k + 1, 2k + 2, 2k + 3, . . . }
for some positive integer k.
The next lemma is proved in [17].
Lemma 20. The only Arf symmetric semigroups are hyperelliptic semigroups.
In order to show which are the only Arf pseudo-symmetric semigroups we
need the Apéry set that was previously defined.
Lemma 21. Let Λ be a pseudo-symmetric numerical semigroup. For any l ∈ Ap(Λ)
different from λ1 + (c − 1)/2, λ1 + c − 1 − l ∈ Ap(Λ).
Proof. Let us prove first that λ1 + c − 1 − l ∈ Λ. Since l ∈ Ap(Λ), l − λ1 6∈ Λ and it
is different from (c−1)/2 by hypothesis. Thus λ1 +c−1−l = c−1−(l−λ1 ) ∈ Λ
because Λ is pseudo-symmetric.
Now, λ1 + c − 1 − l − λ1 = c − 1 − l 6∈ Λ because otherwise c − 1 ∈ Λ. So
λ1 + c − 1 − l must belong to Ap(Λ).
Lemma 22. The only Arf pseudo-symmetric semigroups are {0, 3, 4, 5, 6, . . . } and
{0, 3, 5, 6, 7, . . . } (corresponding to the Klein quartic).
Proof. Let Λ be an Arf pseudo-symmetric numerical semigroup. Let us show
first that Ap(Λ) = {0, λ1 + (c − 1)/2, λ1 + c − 1}. The inclusion ⊇ is obvious.
In order to prove the opposite inclusion suppose l ∈ Ap(Λ), l 6∈ {0, λ1 + (c −
1)/2, λ1 + c − 1}. By Lemma 21, λ1 + c − 1 − l ∈ Λ and since l 6= λ1 + c − 1,
λ1 + c − 1 − l > λ1 . On the other hand, if l 6= 0 then l > λ1 . Now, by the Arf
condition, λ1 + c − 1 − l + l − λ1 = c − 1 ∈ Λ, which is a contradiction.
Now, if #Ap(Λ) = 1 then λ1 = 1 and Λ = N0 . But N0 is not pseudosymmetric.
If #Ap(Λ) = 2 then λ1 = 2. But then Λ must be hyperelliptic and so Λ is not
pseudo-symmetric.
So #Ap(Λ) must be 3. This implies that λ1 = 3 and that 1 and 2 are gaps. If
1 = (c−1)/2 then c = 3 and this gives Λ = {0, 3, 4, 5, 6, . . . }. Else if 2 = (c−1)/2
then c = 5 and this gives Λ = {0, 3, 5, 6, 7, . . . }. Finally, if 1 6= (c − 1)/2 and
2 6= (c − 1)/2, since Λ is pseudo-symmetric, c − 2, c − 3 ∈ Λ. But this contradicts
Lemma 16.
The next two lemmas are two characterizations of Arf numerical semigroups.
The first one is proved in [17, Proposition 1].
Lemma 23. The numerical semigroup Λ with enumeration λ is Arf if and only if for
every two positive integers i, j with i > j, 2λi − λj ∈ Λ.
Lemma 24. The numerical semigroup Λ is Arf if and only if for any l ∈ Λ, the set
S(l) = {l′ − l : l′ ∈ Λ, l′ > l} is a numerical semigroup.
11

Proof. Suppose Λ is Arf. Then 0 ∈ S(l) and if m1 = l′ − l, m2 = l′′ − l with
l′ , l′′ ∈ Λ and l′ > l, l′′ > l, then m1 + m2 = l′ + l′′ − l − l. Since Λ is Arf,
l′ + l′′ − l ∈ Λ and it is larger than or equal to l. Thus, m1 + m2 ∈ S(l). The
finiteness of the complement of S(l) is a consequence of the finiteness of the
complement of Λ.
On the other hand, if Λ is such that S(l) is a numerical semigroup for any
l ∈ Λ then, if λi > λj > λk are in Λ, we will have λi − λk ∈ S(λk ), λj − λk ∈
S(λk ), λi + λj − λk − λk ∈ S(λk ) and therefore λi + λj − λk ∈ Λ.
1.3.3 Numerical semigroups generated by an interval
A numerical semigroup Λ is generated by an interval {i, i + 1, . . . , j} with i, j ∈
N0 , i 6 j if
Λ = {ni i + ni+1 (i + 1) + · · · + nj j : ni , ni+1 , . . . , nj ∈ N0 }.
A study of semigroups generated by intervals was carried out by Garcı́aSánchez and Rosales in [28].
Example 25. The Weierstrass semigroup at the rational point at infinity of the Hermitian curve (Example 4) is generated by q and q + 1. So, it is an example of numerical
semigroup generated by an interval.
Lemma 26. The semigroup Λ{i,...,j} generated by the interval {i, i+1, . . . , j} satisfies
[
Λ{i,...,j} =
{ki, ki + 1, ki + 2, . . . , kj}.
k>0

This lemma is a reformulation of [28, Lemma 1]. In the same reference we
can find the next result [28, Theorem 6].
Lemma 27. Λ{i,...,j} is symmetric if and only if i ≡ 2 mod j − i.
Lemma 28. The only numerical semigroups which are generated by an interval and
Arf, are the semigroups which are equal to {0} ∪ {i ∈ N0 : i > c} for some nonnegative integer c.
Proof. It is a consequence of Lemma 16 and Lemma 26.
Lemma 29. The unique numerical semigroup which is pseudo-symmetric and generated by an interval is {0, 3, 4, 5, 6, . . . }.
Proof. By Lemma 26, for the non-trivial semigroup Λ{i,...,j} generated by the
interval {i, . . . , j}, the intervals of gaps between λ0 and the conductor satisfy
that the length of each interval is equal to the length of the previous interval
minus j − i. On the other hand, the intervals of non-gaps between 1 and c − 1
satisfy that the length of each interval is equal to the length of the previous
interval plus j − i.
Now, by Lemma 12, (c − 1)/2 must be the first gap or the last gap of an
interval of gaps. Suppose that it is the first gap of an interval of n gaps. If it is
12

equal to 1 then c = 3 and Λ = {0, 3, 4, 5, 6, . . . }. Otherwise (c−1)/2 > λ1 . Then,
if Λ is pseudo-symmetric, the previous interval of non-gaps has length n − 1.
Since Λ is generated by an interval, the first interval of non-gaps after (c − 1)/2
must have length n − 1 + j − i and since Λ is pseudo-symmetric the interval
of gaps before (c − 1)/2 must have the same length. But since Λ is generated
by an interval, the interval of gaps previous to (c − 1)/2 must have length
n + j − i. This is a contradiction. The same argument proves that (c − 1)/2 can
not be the last gap of an interval of gaps. So, the only possibility for a pseudosymmetric semigroup generated by an interval is when (c − 1)/2 = 1, that is,
when Λ = {0, 3, 4, 5, 6, . . . }.
1.3.4 Acute numerical semigroups
Definition 30. We say that a numerical semigroup is ordinary if it is equal to
{0} ∪ {i ∈ N0 : i > c}
for some non-negative integer c.
Almost all rational points on a curve of genus g over an algebraically closed
field have Weierstrass semigroup of the form {0} ∪ {i ∈ N0 : i > g + 1}.
Such points are said to be ordinary. This is why we call these numerical semigroups ordinary [32, 21, 67]. Caution must be taken when the characteristic of
the ground field is p > 0, since there exist curves with infinitely many nonordinary points [68].
Notice that N0 is an ordinary numerical semigroup. It will be called the
trivial numerical semigroup.
Definition 31. Let Λ be a numerical semigroup different from N0 with enumeration
λ, genus g and conductor c. The element λλ−1 (c)−1 will be called the dominant of the
semigroup and will be denoted d. For each i ∈ N0 let g(i) be the number of gaps which
are smaller than λi . In particular, g(λ−1 (c)) = g and g(λ−1 (d)) = g ′ < g. If i is
the smallest integer for which g(i) = g ′ then λi is called the subconductor of Λ and
denoted c′ .
Remark 32. Notice that if c′ > 0, then c′ − 1 6∈ Λ. Otherwise we would have
g(λ−1 (c′ − 1)) = g(λ−1 (c′ )) and c′ − 1 < c′ . Notice also that all integers between c′
and d are in Λ because otherwise g(λ−1 (c′ )) < g ′ .
Remark 33. For a numerical semigroup Λ different from N0 the following are equivalent:
(i) Λ is ordinary,
(ii) the dominant of Λ is 0,
(iii) the subconductor of Λ is 0.
Indeed, (i)⇐⇒(ii) and (ii)=⇒(iii) are obvious. Now, suppose (iii) is satisfied. If
the dominant is larger than or equal to 1 it means that 1 is in Λ and so Λ = N0 a
contradiction.
13

Definition 34. If Λ is a non-ordinary numerical semigroup with enumeration λ and
with subconductor λi then the element λi−1 will be called the subdominant and denoted d′ .
It is well defined because of Remark 33.
Definition 35. A numerical semigroup Λ is said to be acute if Λ is ordinary or if
Λ is non-ordinary and its conductor c, its subconductor c′ , its dominant d and its
subdominant d′ satisfy c − d 6 c′ − d′ .
Roughly speaking, a numerical semigroup is acute if the last interval of
gaps before the conductor is smaller than the previous interval of gaps.
Example 36. For the Hermitian curve over F16 the Weierstrass semigroup at the
unique point at infinity is
{0, 4, 5, 8, 9, 10} ∪ {i ∈ N0 : i > 12}.
In this case c = 12, d = 10, c′ = 8 and d′ = 5 and it is easy to check that it is an acute
numerical semigroup.
Example 37. For the Weierstrass semigroup at the rational point P0 of the Klein
quartic in Example 5 we have c = 5, d = c′ = 3 and d′ = 0. So, it is an example of a
non-ordinary acute numerical semigroup.
Lemma 38. Let Λ be a numerical semigroup.
1. If Λ is symmetric then it is acute.
2. If Λ is pseudo-symmetric then it is acute.
3. If Λ is Arf then it is acute.
4. If Λ is generated by an interval then it is acute.
Proof. If Λ is ordinary then it is obvious. Let us suppose that Λ is a nonordinary semigroup with genus g, conductor c, subconductor c′ , dominant d
and subdominant d′ .
1. Suppose that Λ is symmetric. We know by Lemma 10 that a numerical
semigroup Λ is symmetric if and only if for any non-negative integer i, if
i is a gap, then c − 1 − i ∈ Λ. If moreover it is not ordinary, then 1 is a gap.
So, c − 2 ∈ Λ and it is precisely the dominant. Hence, c − d = 2. Since
c′ − 1 is a gap, c′ − d′ > 2 = c − d and so Λ is acute.
2. Suppose that Λ is pseudo-symmetric. If 1 = (c − 1)/2 then c = 3 and
Λ = {0, 3, 4, 5, 6, . . . } which is ordinary. Else if 1 6= (c − 1)/2 then the
proof is equivalent to the one for symmetric semigroups.
3. Suppose Λ is Arf. Since d > c′ > d′ , then d + c′ − d′ is in Λ and it is
strictly larger than the dominant d. Hence it is larger than or equal to c.
So, d + c′ − d′ > c and Λ is acute.
14

Numerical semigroups

Acute

Irreducible

Arf

Symmetric

Pseudo-sym

Λ{i,...,j}

EX: Klein quartic.

EX: Hermitian c.
Norm-Trace c.

EX: Klein quartic.

EX: Hermitian c.

Gar-Sti tower

Hyperelliptic Ordinary Λ{i,..., (k+1)i−2
}
k
Klein q.
{0, 3, 4, . . . }

Campillo, Farran,

Garcı́a-Sánchez,
Rosales

Munuera

{0, 3, 4, . . . }

Trivial: N0

Figure 1: Diagram of semigroup classes and inclusions.
4. Suppose that Λ is generated by the interval {i, i + 1, . . . , j}. Then, by
Lemma 26, there exists k such that c = ki, c′ = (k − 1)i, d = (k − 1)j and
d′ = (k − 2)j. So, c − d = k(i − j) + j while c′ − d′ = k(i − j) − i + 2j.
Hence, Λ is acute.

In Figure 1 we summarize all the relations we have proved between acute
semigroups, symmetric and pseudo-symmetric semigroups, Arf semigroups
and semigroups generated by an interval.
Remark 39. There exist numerical semigroups which are not acute. For instance,
Λ = {0, 6, 8, 9} ∪ {i ∈ N0 : i > 12}.
In this case, c = 12, d = 9, c′ = 8 and d′ = 6.
On the other hand there exist numerical semigroups which are acute and which are
not symmetric, pseudo-symmetric, Arf or interval-generated. For example,
Λ = {0, 10, 11} ∪ {i ∈ N0 : i > 15}.
In this case, c = 15, d = 11, c′ = 10 and d′ = 0.
15

1.4 Characterization
1.4.1 Homomorphisms of semigroups
Homomorphisms of numerical semigroups, that is, maps f between numerical semigroups such that f (a + b) = f (a) + f (b), are exactly the scale maps f (a) = ka
for all a, for some constant k > 0. Indeed, if f is a homomorphism then f (a)
a
is constant since f (ab) = a · f (b) = b · f (a). Furthermore, the unique surjective homomorphism is the identity. Indeed, for a semigroup Λ, the set kΛ is a
numerical semigroup only if k = 1.
1.4.2 The ⊕ operation, the ν sequence, and the τ sequence
Next we define three important objects describing the addition behavior of a
numerical semigroup.
Definition 40. The operation ⊕Λ : N0 × N0 → N0 associated to the numerical
semigroup Λ (with enumeration λ) is defined as
i ⊕Λ j = λ−1 (λi + λj )
for any i, j ∈ N0 . Equivalently,
λi + λj = λi⊕Λ j .
The subindex referring to the semigroup may be ommitted if the semigroup
is clear by the context. The operation ⊕ is obviously commutative, associative,
and has 0 as identity element. However there is in general no inverse element.
Also, the operation ⊕ is compatible with the natural order of N0 . That is, if
a < b then a ⊕ c < b ⊕ c and c ⊕ a < c ⊕ b for any c ∈ N0 .
Example 41. For the numerical semigroup Λ = {0, 4, 5, 8, 9, 10, 12, 13, 14, . . .} the
first values of ⊕ are given in the next table:
⊕
0
1
2
3
4
5
6
7
..
.

0 1 2
0 1 2
1 3 4
2 4 5
3 6 7
4 7 8
5 8 9
6 10 11
7 11 12
.. ..
..
. .
.

3
3
6
7
10
11
12
14
15
..
.

4
4
7
8
11
12
13
15
16
..
.

5
5
8
9
12
13
14
16
17
..
.

6
6
10
11
14
15
16
18
19
..
.

7
7
11
12
15
16
17
19
20
..
.

...
...
...
...
...
...
...
...
...
..
.

Definition 42. The partial ordering 4Λ on N0 associated to the numerical semigroup
Λ is defined as follows:
i 4Λ j if and only if λj − λi ∈ Λ.
16

Equivalently
i 4Λ j if and only if there exists k with i ⊕Λ k = j.
As before, if Λ is clear by the context then the subindex may be ommitted.
Definition 43. Given a numerical semigroup Λ, the set Ni is defined by
Ni = {j ∈ N0 : j 4Λ i} = {j ∈ N0 : λi − λj ∈ Λ}.
The sequence νi is defined by νi = #Ni .
Example 44. The ν sequence of the trivial semigroup Λ = N0 is 1, 2, 3, 4, . . . .
Next lemma states the relationship between ⊕ and the ν sequence of a numerical semigroup. Its proof is obvious.
Lemma 45. Let Λ be a numerical semigroup and ν the corresponding ν sequence. For
all i ∈ N0 ,
νi = #{(j, k) ∈ N20 : j ⊕ k = i}.
Example 46. If we are given the table in Example 41 we can deduce ν7 by counting the
number of occurrences of 7 inside the table. This is exactly 6. Thus, ν7 = 6. Repeating
the same process for all νi with i < 7 we get ν0 = 1, ν1 = 2, ν2 = 2, ν3 = 3, ν4 = 4,
ν5 = 3, ν6 = 4.
This lemma implies that any finite set in the sequence ν can be determined
by a finite set of ⊕ values. Indeed, to compute νi it is enough to know {j ⊕ k :
0 6 j, k 6 i}.
Definition 47. Given a numerical semigroup Λ define its τ sequence by
τi = max{j ∈ N0 : exists k with j 6 k 6 i and j ⊕Λ k = i}.
Notice that τi is the largest element j in Ni with λj 6 λi /2. In particular, if
λi /2 ∈ Λ then τi = λ−1 (λi /2). Notice also that τi is 0 if and only if λi is either 0
or a generator of Λ.
Example 48. In Table 1 we show the ν sequence and the τ sequence of the numerical
semigroups generated by 4, 5 and generated by 6, 7, 8, 17.
One difference between the τ sequence and the ν sequence is that, while
in the ν sequence not all non-negative integers need to appear, in the τ sequence all of them appear. Notice for instance that 7 does not appear in the ν
sequence of the numerical semigroup generated by 4 and 5 nor the numerical
semigroup generated by 6, 7, 8, 17. The reason for which any non negative integer j appears in the τ sequence is that if λi = 2λj then τi = j. Furthermore,
the smallest i for which τi = j corresponds to λi = 2λj .

17

(a) < 4, 5 >

i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
.

λi
0
4
5
8
9
10
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
..
.

(b) < 6, 7, 8, 17 >

νi τi
1 0
2 0
2 0
3 1
4 1
3 2
4 1
6 2
6 2
4 2
5 3
8 3
9 4
8 4
9 5
10 4
12 5
12 5
13 6
14 6
15 7
16 7
17 8
18 8
..
..
.
.

i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
..
.

λi
0
6
7
8
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
..
.

νi τi
1 0
2 0
2 0
2 0
3 1
4 1
5 2
4 2
3 3
2 0
4 1
6 2
8 3
8 3
8 3
8 3
9 4
10 4
11 5
12 5
13 6
14 6
15 7
16 7
..
..
.
.

Table 1: ν and τ sequences of the numerical semigroups generated by 4, 5 and
by 6, 7, 8, 17

18

1.4.3 Characterization of a numerical semigroup by ⊕
The next result was proved in [6, 7].
Lemma 49. The ⊕ operation uniquely determines a semigroup.
Proof. Suppose that two semigroups Λ = {λ0 < λ1 < . . . } and Λ′ = {λ′0 <
λ′1 < . . . } have the same associated operation ⊕. Define the map f (λi ) = λ′i . It
is obviously surjective and it is a homomorphism since f (λi + λj ) = f (λi⊕j ) =
λ′i⊕j = λ′i + λ′j = f (λi ) + f (λj ). So, Λ = Λ′ .
Conversely to Lemma 49 we next prove that any finite set of ⊕ values is
shared by an infinite number of semigroups. This was proved in [7].
Lemma 50. Let a, b be positive integers. Let Λ be a numerical semigroup with enumeration λ and let d be an integer with d > 2. Define the numerical semigroup
Λ′ = dΛ ∪ {i ∈ N : i > dλa⊕b }. Then i ⊕Λ′ j = i ⊕Λ j for all i 6 a and all j 6 b,
and Λ′ 6= Λ.
Proof. It is obious that Λ′ 6= Λ. Let λ′ be the enumeration of Λ′ . For all k 6 a ⊕Λ
b, λ′k = dλk . In particular, if i 6 a and j 6 b then λ′i = dλi and λ′j = dλj . Hence,
λ′i⊕Λ′ j = λ′i +λ′j = dλi +dλj = dλi⊕Λ j = λ′i⊕Λ j . This implies i⊕Λ′ j = i⊕Λ j.
By varying d in Lemma 50, we can see that although the values (i ⊕ j)06i,j
of a numerical semigroup uniquely determine it, any subset (i ⊕ j)06i6a,06j6b
is exactly the corresponding subset of infinitely many numerical semigroups.
1.4.4 Characterization of a numerical semigroup by ν
We will use the following result on the values νi . It can be found in [39, Theorem 3.8.].
Lemma 51. Let Λ be a numerical semigroup with genus g, conductor c and enumeration λ. Let g(i) be the number of gaps smaller than λi and let
D(i) = {l ∈ N0 \ Λ : λi − l ∈ N0 \ Λ}.
Then, for all i ∈ N0 ,
νi = i − g(i) + #D(i) + 1.
In particular, for all i > 2c − g − 1 (or equivalently, for all i such that λi > 2c − 1),
νi = i − g + 1.
Proof. The number of gaps smaller than λi is g(i) but it is also #D(i) + #{l ∈
N0 \ Λ : λi − l ∈ Λ}, so,
g(i) = #D(i) + #{l ∈ N0 \ Λ : λi − l ∈ Λ}.

(1)

On the other hand, the number of non-gaps which are at most λi is i + 1 but it
is also νi + #{l ∈ Λ : λi − l ∈ N0 \ Λ} = νi + #{l ∈ N0 \ Λ : λi − l ∈ Λ}. So,
i + 1 = νi + #{l ∈ N0 \ Λ : λi − l ∈ Λ}.
19

(2)

From equalities 1 and 2 we get
g(i) − #D(i) = i + 1 − νi
which leads to the desired result.
The next lemma shows that if a numerical semigroup is non-trivial then
there exists at least one value k such that νk = νk+1 .
Lemma 52. Suppose Λ 6= N0 and suppose that c and g are the conductor and the
genus of Λ. Let k = 2c − g − 2. Then νk = νk+1 .
Proof. Since Λ 6= N0 , c > 2 and so 2c − 2 > c. This implies k = λ−1 (2c − 2)
and g(k) = g. By Lemma 51, νk = k − g + #D(k) + 1. But D(k) = {c − 1}. So,
νk = k − g + 2. On the other hand, g(k + 1) = g and D(k + 1) = ∅. By Lemma 51
again, νk+1 = k − g + 2 = νk .
Lemma 53. The trivial semigroup is the unique numerical semigroup with ν sequence
equal to 1, 2, 3, 4, 5, . . . .
Proof. As a consequence of Lemma 52 for any other numerical semigroup there
is a value in the ν sequence that appears at least three times.
The next result was proved in [5, 6].
Theorem 54. The ν sequence of a numerical semigroup determines it.
Proof. If Λ = N0 then, by Lemma 53, its ν sequence is unique.
Suppose that Λ 6= N0 . Then we can determine the genus and the conductor
from the ν sequence. Indeed, let k = 2c − g − 2. In the following we will show
how to determine k without the knowledge of c and g. By Lemma 52 it holds
that νk = νk+1 = k − g + 2 and by Lemma 51 νi = i − g + 1 for all i > k, which
means that νi+1 = νi + 1 for all i > k. So,
k = max{i : νi = νi+1 }.
We can now determine the genus as
g = k + 2 − νk
and the conductor as

k+g+2
.
2
At this point we know that {0} ∈ Λ and {i ∈ N0 : i > c} ⊆ Λ and, furthermore,
{1, c − 1} ⊆ N0 \ Λ. It remains to determine for all i ∈ {2, . . . , c − 2} whether
i ∈ Λ. Let us assume i ∈ {2, . . . , c − 2}.
On one hand, c − 1 + i − g > c − g and so λc−1+i−g > c. This means that
g(c − 1 + i − g) = g and hence
c=

νc−1+i−g = c − 1 + i − g − g + #D(c − 1 + i − g) + 1.
20

(3)

On the other hand, if we define D̃(i) to be
D̃(i) = {l ∈ N0 \ Λ : c − 1 + i − l ∈ N0 \ Λ, i < l < c − 1}
then
D(c − 1 + i − g) =



D̃(i) ∪ {c − 1, i}
D̃(i)

if i ∈ N0 \ Λ
otherwise.

(4)

So, from (3) and (4),
i is a non-gap ⇐⇒ νc−1+i−g = c + i − 2g + #D̃(i).
This gives an inductive procedure to decide whether i belongs to Λ decreasingly from i = c − 2 to i = 2.
Remark 55. From the proof of Theorem 54 we see that a semigroup can be determined
by k = max{i : νi = νi+1 } and the values νi for i ∈ {c − g + 1, . . . , 2c − g − 3}.
Remark 56. Lemma 49 is a consequence of Lemma 45 and Theorem 54.
Conversely to Theorem 54 we next prove that any finite set of ν values is
shared by an infinite number of semigroups. This was proved in [7]. Thus,
the construction just given to determine a numerical semigroup from its ν sequence can only be performed if we know the behavior of the infinitely many
values in the ν sequence.
Lemma 57. Let k be a positive integer. Let Λ be a numerical semigroup with enumeration λ and let d be an integer with d > 2. Define the semigroup Λ′ = dΛ ∪ {i ∈ N :
′
i > dλk } and let ν Λ and ν Λ be the ν sequence corresponding to Λ and Λ′ respectively.
′
Then νiΛ = νiΛ for all i 6 k and Λ′ 6= Λ.
Proof. It is obvious that Λ′ 6= Λ. Let λ′ be the enumeration of Λ′ . For all i 6 k,
λ′i = dλi . In particular, if j 6 i 6 k, then λ′i − λ′j = d(λi − λj ) ∈ Λ′ ⇐⇒ λi − λj ∈
′
Λ. Hence, νiΛ = νiΛ .
As a consequence of Lemma 57, although the sequence ν of a numerical
semigroup uniquely determines it, any subset (νi )06i6k−1 is exactly the set of
the first k values of the ν sequence of infinitely many semigroups. In fact, by
varying d among the positive integers, we get an infinite set of semigroups, all
of them sharing the first k values in the ν sequence.
It would be interesting to find which sequences of positive integers correspond to the sequence ν of a numerical semigroup. By now, only some necessary conditions can be stated, for instance,
• ν0 = 1,
• ν1 = 2,
• νi 6 i + 1 for all i ∈ N0 ,
• there exists k such that νi+1 = νi + 1 for all i > k,
21

1.4.5 Characterization of a numerical semigroup by τ
In this section we show that a numerical semigroup is determined by its τ
sequence. This was proved in [10].
Lemma 58. Let Λ be a numerical semigroup with enumeration λ, conductor c > 2,
genus g, and dominant d. Then
1. τ(2c−g−2)+2i = τ(2c−g−2)+2i+1 = (c − g − 1) + i for all i > 0
2. At least one of the following statements holds
• τ(2c−g−2)−1 = c − g − 1
• τ(2c−g−2)−2 = c − g − 1
Proof.

1. If i > 1 then λ(2c−g−2)+2i = 2c − 2 + 2i and λ(2c−g−2)+2i /2 =
c − 1 + i ∈ Λ. So τ(2c−g−2)+2i = λ−1 (c − 1 + i) = c − 1 + i − g. On the
other hand, λ(2c−g−2)+2i+1 = 2c − 2 + 2i + 1 = (c − 1 + i) + (c − 1 + i + 1)
and so τ(2c−g−2)+2i+1 = λ−1 (c − 1 + i) = c − 1 + i − g.
If i = 0 then λ(2c−g−2)+2i = λ2c−g−2 and since c > 2 this is equal to 2c − 2.
Now λ2c−g−2 /2 = c − 1 and the largest non-gap which is at most c − 1 is
d. On the other hand, λ2c−g−2 − d = 2c − 2 − d > c because c > d + 2.
Consequently λ2c−g−2 −d ∈ Λ and τ2c−g−2 = λ−1 (d) = c−g−1. Similarly,
the largest non-gap which is at most λ2c−g−1 /2 is d and λ2c−g−1 − d =
2c − 1 − d ∈ Λ. So, τ2c−g−1 = c − g − 1.

2. If c = 3 then g = 2 and λ(2c−g−2)−2 = λ0 and τ(2c−g−2)−2 = 0 = c −
g − 1. Assume c > 4. If d = c − 2 then λ(2c−g−2)−2 = 2c − 4 = 2d,
so τ(2c−g−2)−2 = λ−1 (d) = c − g − 1. If d = c − 3 then λ(2c−g−2)−1 =
2c − 3 = d + c, so τ(2c−g−2)−1 = λ−1 (d) = c − g − 1. Suppose now
d 6 c − 4. In this case λ(2c−g−2)−2 /2 = c − 2, which is between d and c,
and λ(2c−g−2)−2 − d = 2c − 4 − d > c. So λ(2c−g−2)−2 − d ∈ Λ. This makes
τ(2c−g−2)−2 = λ−1 (d) = c − g − 1.
Lemma 59. The trivial semigroup is the unique numerical semigroup with τ sequence
equal to 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, . . ..
Proof. It is enough to check that for any other numerical semigroup there is a
value in the τ sequence that appears at least three times. If c = 2 then τ0 = τ1 =
τ2 = 0. If c > 2, by Lemma 58, τ2c−g−2 = τ2c−g−1 and they are equal to at least
one of τ2c−g−3 and τ2c−g−4 .
Theorem 60. The τ sequence of a numerical semigroup determines it.
Proof. Let k be the minimum integer such that τk+2i = τk+2i+1 and τk+2i+2 =
τk+2i+1 + 1 for all i ∈ N0 . If k = 0, by Lemma 59, Λ = N0 . Assume k > 0.

22

By Lemma 58, if c > 2, k = 2c − g − 2 and τk = c − g − 1. So,

c = k − τk + 1
g = k − 2τk
This result can be extended to the case c = 2 since in this case c = 2, g = 1,
k = 1 and τk = 0.
This determines λi = i + g for all i > c − g. Now we can determine λc−g−1 ,
λc−g−2 , and so on using that the smallest j for which τj = i corresponds to
λj = 2λi . That is, λi = 21 min{λj : τj = i}.
We have just seen that any numerical semigroup is uniquely determined by
its τ sequence. The next lemma shows that no finite subset of τ can determine
the numerical semigroup. This result is analogous to [7, Proposition 2.2.]. In
this case it refers to the ν sequence instead of the τ sequence.
Lemma 61. Let r be a positive integer. Let Λ be a numerical semigroup with enumeration λ and let m be an integer with m > 2. Define the semigroup Λ′ = mΛ ∪ {i ∈
′
N0 : i > mλr } and let τ Λ and τ Λ be the τ sequence corresponding to Λ and Λ′
′
respectively. Then τiΛ = τiΛ for all i 6 r and Λ′ 6= Λ.
Proof. It is obvious that Λ′ 6= Λ. Let λ′ be the enumeration of Λ′ . For all i 6 r,
λ′i = mλi . In particular, if j 6 i 6 r, then it exists k with j 6 k 6 i and
λj + λk = λi if and only if it exists k with j 6 k 6 i and λ′j + λ′k = λ′i . Hence,
′
by the definition of the τ sequence, τiΛ = τiΛ .
As a consequence of Lemma 61, although the sequence τ of a numerical
semigroup uniquely determines it, any subset (τi )06i6r−1 is exactly the set of
the first r values of the τ sequence of infinitely many semigroups. In fact, by
varying m among the positive integers, we get an infinite set of semigroups, all
of them sharing the first r values in the τ sequence.

1.5 Counting
We are interested on the number ng of numerical semigoups of genus g. It is
obvious that n0 = 1 since N0 is the unique numerical semigroup of genus 0. On
the other hand, if 1 is in a numerical semigroup, then any non-negative integer
must belong also to the numerical semigroup, because any non-negative integer is a finite sum of 1’s. Thus, the unique numerical semigroup with genus
1 is {0} ∪ {i ∈ N0 : i > 2} and n1 = 1. In [40] all terms of the sequence ng
are computed up to genus 37 and the terms of genus up to 50 are computed
in [8]. Recently we computed n51 = 164253200784 and n52 = 266815155103. It
is conjectured in [8] that the sequence given by the numbers ng of numerical
semigroups of genus g asymptotically behaves like the Fibonacci numbers and
so it increases by a portion of the golden ratio. More precisely, it is conjectured
ng
n
+n
= φ,
that (1) ng > ng−1 + ng−2 , (2) limg→∞ g−1ng g−2 = 1, (3) limg→∞ ng−1
where φ =

√
1+ 5
2

is the golden ratio. Notice that (2) and (3) are equivalent.
23

ng−1 +ng−2
ng
✻

1

✉
✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉
✉
✉

✲

0

g

52

Figure 2: Behavior of the quotient
spond to the values in Table 2.

ng−1 +ng−2
.
ng

The values in this graphic corre-

ng
ng−1
✻

✉

✉
✉
✉

φ

✉
✉

✉

✉

✉

✉
✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✉

✲

0

g

52

Figure 3: Behavior of the quotient
to the values in Table 2.

ng
ng−1 .

The values in this graphic correspond

By now, only some bounds are known for ng which become very poor when g
approaches infinity [9, 20]. Other contributions related to this sequence can be
found in [40, 41, 65, 44, 12, 11, 74, 37, 3].
In Table 2 there are the results obtained for all numerical semigroups with
genus up to 52. For each genus we wrote the number of numerical semigroups
of the given genus, the Fibonacci-like-estimated value given by the sum of the
number of semigroups of the two previous genus, the value of the quotient
ng−1 +ng−2
ng
, and the value of the quotient ng−1
. In Figure 2 and Figure 3 we
ng
depicted the behavior of these quotients. From these graphics one can predict
ng
n
+n
approaches
that g−1ng g−2 approaches 1 as g approaches infinity whereas ng−1
the golden ratio as g approaches infinity.
The number ng is usually studied by means of the tree rooted at the semi-

24

g
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

ng
1
1
2
4
7
12
23
39
67
118
204
343
592
1001
1693
2857
4806
8045
13467
22464
37396
62194
103246
170963
282828
467224
770832
1270267
2091030
3437839
5646773
9266788
15195070
24896206
40761087
66687201
109032500
178158289
290939807
474851445
774614284
1262992840
2058356522
3353191846
5460401576
8888486816
14463633648
23527845502
38260496374
62200036752
101090300128
164253200784
266815155103

ng−1 + ng−2

ng−1 +ng−2
ng

ng
ng−1

2
3
6
11
19
35
62
106
185
322
547
935
1593
2694
4550
7663
12851
21512
35931
59860
99590
165440
274209
453791
750052
1238056
2041099
3361297
5528869
9084612
14913561
24461858
40091276
65657293
107448288
175719701
287190789
469098096
765791252
1249465729
2037607124
3321349362
5411548368
8813593422
14348888392
23352120464
37991479150
61788341876
100460533126
163290336880
265343500912

1
0.75
0.857143
0.916667
0.826087
0.897436
0.925373
0.898305
0.906863
0.938776
0.923986
0.934066
0.940933
0.942947
0.946733
0.952517
0.954259
0.957621
0.960825
0.962472
0.964589
0.967695
0.969526
0.971249
0.973042
0.974642
0.976121
0.977735
0.979120
0.980341
0.981474
0.982554
0.983567
0.984556
0.985470
0.986312
0.987114
0.987884
0.988610
0.989290
0.989919
0.990504
0.991053
0.991574
0.992067
0.992531
0.992969
0.993381
0.993770
0.994138
0.994484

1
2
2
1.75
1.71429
1.91667
1.69565
1.71795
1.76119
1.72881
1.68137
1.72595
1.69088
1.69131
1.68754
1.68218
1.67395
1.67396
1.66808
1.66471
1.66312
1.66006
1.65588
1.65432
1.65197
1.64981
1.64792
1.64613
1.64409
1.64254
1.64108
1.63973
1.63844
1.63724
1.63605
1.63498
1.63399
1.63304
1.63213
1.63128
1.63048
1.62975
1.62906
1.62842
1.62781
1.62723
1.62669
1.62618
1.62570
1.62525
1.62482
1.62441

Table 2: Computational results on the number of numerical semigroups up to
25
genus 52.

<1>

< 2, 3 >

< 2, 7 >

< 2, 9 >
..
.

< 2, 5 >

< 3, 4, 5 >

< 3, 4 >

< 3, 5, 7 > < 4, 5, 6, 7 >

< 3, 5 > < 3, 7, 8 > < 4, 5, 6 > < 4, 5, 7 > < 4, 6, 7, 9 > < 5, 6, 7, 8, 9 >
..
.

..
.

..
.

..
.

..
.

..
.

Figure 4: Recursive construction of numerical semigroups of genus g from numerical semigroups of genus g − 1. Generators larger than the conductor are
written in bold face.
group N0 and for which the children of a semigroup are the semigroups obtained by taking out one by one its generators larger than or equal to its conductor [8, 9, 11, 20]. This tree was previously used in [64, 63]. It is illustrated in
Figure 4. It contains all semigroups exactly once and the semigroups at depth
g have genus g. So, ng is the number of nodes of the tree at depth g. Some
alternatives for counting semigroups of a given genus without using this tree
have been considered in [12, 3, 74].

2 Numerical semigroups and codes
2.1 One-point codes and their decoding
2.1.1 One-point codes
Linear codes A linear code C of length n over the alphabet Fq is a vector subspace of Fnq . Its elements are called code words. The dimension k of the code is
the dimension of C as a subspace of Fnq . The dual code of C is C ⊥ = {v ∈ Fnq :
v · c = 0 for all c ∈ C}. It is a linear code with the same length as C and with
dimension n − k.
The Hamming distance between two vectors of the same length is the number
of positions in which they do not agree. The weight of a vector is the number
of its non-zero components or, equivalently, its Hamming distance to the zero
vector. The minimum distance d of a linear code C is the minimum Hamming
distance between two code words in C. Equivalently, it is the minimum weight
of all code words in C. The correction capability of a code is the maximum num26

ber of errors that can be added to any code word, with the code word being still
uniquelly identifiable. The correction capability of a linear code with minimum
distance d is ⌊ d−1
2 ⌋.
One-point codes Let P be a rational point of the algebraic smooth curve XF
defined over Fq with Weierstrass
semigroup Λ. Suppose that the enumeration
S
of Λ is λ. Recall that A = m>0 L(mP ) is the ring of rational functions having
poles only at P . We will say that the order of f ∈ A\{0} is s if vP (f ) = −λs . The
order of 0 is considered to be either −1 [52] or −∞ [35]. In the present work we
will consider the order of 0 to be −1 although both would be fine. We denote
the order of f by ρ(f ).
One can find an infinite basis z0 , z1 , . . . , zi , . . . of A such that vP (zi ) = −λi
or, equivalently, ρ(zi ) = i. Consider a set of rational points P1 , . . . , Pn different
from P and the map ϕ : A −→ Fq n defined by ϕ(f ) = (f (P1 ), . . . , f (Pn )). To
each finite subset W ⊆ N0 we associate the one-point code
CW =< ϕ(zi ) : i ∈ W >⊥ =< (zi (P1 ), . . . , zi (Pn )) : i ∈ W >⊥ .
We say that W is the set of parity checks of CW . The one-point codes for which
W = {0, 1, . . . , m} are called classical one-point codes. In this case we write Cm
for CW .
2.1.2 Decoding one-point codes
This section presents a sketch of a decoding algorithm for CW . The aim is to
justify the conditions guaranteeing correction of errors. Suppose that a code
word c ∈ CW is sent and that an error e is added to it so that the received word
is u = c + e. We will use t for the number of non-zero positions in e.
Definition 62. A polynomial f is an error-locator of an error vector e if and only if
f (Pi ) = 0 whenever ei 6= 0. The footprint of e is the set
∆e = N0 \ {ρ(f ) : f is an error-locator}.
It is well known that #∆e = t and that ∆e is 4-closed. That is, if i 4 j
and j ∈ ∆e then i ∈ ∆e . If for each minimal element in N0 \ ∆e with respect
to 4 we can find an error-locator with that order then localization of errors is
guaranteed.
Definition 63. Define the syndrome of orders i, j as
sij =

n
X

zi (Pl )zj (Pl )el .

l=1

′

′

rr
The syndrome matrix S rr is the (r + 1) × (r′ + 1) matrix with Sij
= sij for
′
0 6 i 6 r and 0 6 j 6 r .

27

′

′

The matrix S r r is the matrix S r r , transposed. By Lemma 2, if i ⊕ j = k
then
Pn there exist a0 , . . . , ak such that zi zj = ak zk + · · · + a0 z0 . Define sk =
l=1 zk (Pl )el . Then
sij = ak sk + · · · + a0 s0 .
(5)
The syndromes depend on e which is initially unknown. So, in general, sij
and sk are unknown. For a polynomial f = zr + ar−1 zr−1 + · · · + a0 z0 , being an
′
error locator means that (a0 , . . . , ar )S rr = 0 for all r′ > 0.1 Conversely, there
′
exists M such that if (a0 , . . . , ar )S rr = 0 for all r′ with r ⊕ r′ 6 M then f is an
2
error locator.
′
Hence, we look for pairs (r, r′ ) with r⊕r′ large enough such that (x0 , . . . , xr−1 , 1)S rr =
0 has a non-zero solution (and indeed we look for this solution). Notice that if
′
′′
(x0 , . . . , xr−1 , 1)S rr = 0 has a non-zero solution then so does (x0 , . . . , xr−1 , 1)S rr
′′
′
for all r < r .
The first difficulty is that only a few syndromes are known. This is overcome by using a majority voting procedure.
We proceed iteratively, considering the non-gaps of Λ by increasing order.
Suppose that all syndromes sij are known for i⊕j < k and we want to compute
the syndromes sij with i ⊕ j = k. By equation 5 this is equivalent to finding
sk . If k ∈ WP
then the computation
can be done
the definition
P
P by just using P
of CW : sk = nl=1 zk (Pl )el = nl=1 zk (Pl )ul − nl=1 zk (Pl )cl = nl=1 zk (Pl )ul .
Otherwise we establish a voting procedure to determine sk
In the voting procedure the voters are the elements i 4 k for which (x0 , . . . , xi−1 , 1)S i,k⊖i−1 =
0 and (y0 , . . . , yk⊖i−1 , 1)S k⊖i,i−1 = 0 have non-zero solutions. We consider the
value
s̃i,k⊖i = (s0,(k⊖i) , . . . , si−1,(k⊖i) ) · (x0 , . . . , xi−1 ) = (si,0 , . . . , si,(k⊖i)−1 ) · (y0 , . . . , y(k⊖i)−1 ). 3

as a candidate for si,k⊖i . Notice that if si,k⊖i = s̃i,k⊖i then (x0 , . . . , xi−1 , 1)S i,k⊖i =
0 and (y0 , . . . , yk⊖i−1 , 1)S k⊖i,i = 0. Otherwise, if si,k⊖i 6= s̃i,k⊖i then there exist
no error-locators of order i and no error-locators of order k ⊖ i. Since s̃i,k⊖i is a
candidate for si,k⊖i , the associated candidate s̃k for sk will be derived from the
equation s̃i,k⊖i = ak s̃k + ak−1 sk−1 + · · · + a0 s0 , where a0 , . . . , ak are such that
s̃
−a
s
−···−a0 s0
zi zk⊖i = ak zk + · · · + a0 z0 . That is, s̃k = i,k⊖i k−1akk−1
.
Lemma 64.
with sk .

• If i ∈ Nk and i, k ⊖ i 6∈ ∆e then i is a voter and its vote coincides

Pr
P
P
P
Pr
Pn
1
rr ′
. . , ri=0 ai sir ′ ) P
= ( ri=0 ai n
k=1 zi (Pk )z0 (Pk )ek , . . . ,
i=0 ai
k=1 zi (Pk )zr ′ (Pk )ek ) =
P (a0 , . . . , ar )SPr = ( i=0 ai si0 , .P
n
r
(Pn
z
(P
)e
a
z
(P
),
.
.
.
,
z
′
(P
)e
a
z
(P
))
=
k k
k k
k
k=1 0
i=0 i i Pk
k=1 r
i=0 i i
n
( n
k=1 z0 (Pk )ek f (Pk ), . . . ,
k=1 zr ′ (Pk )ek f (Pk )) = (0, . . . , 0)
2 An explanation for this can be found in [56, 35, 14].
3
If (x0 , . . . , xi−1 , 1)S i,j−1
=
0 and (y0 , . . . , yj−1 , 1)S j,i−1
=
0 then
(s0,j , . . . , si−1,j ) · (x0 , . . . , xi−1 )
=
(si,0 , . . . , si,j−1 ) · (y0 , . . . , yj−1 ). Indeed,
(x0 , . . . , xi−1 , 1)S i,j−1 = 0 implies that (si,0 , . . . , si,j−1 ) = −(x0 , . . . , xi−1 )S i−1,j−1 and
similarly, (y0 , . . . , yj−1 , 1)S j,i−1 = 0 implies that (s0,j , . . . , si−1,j ) = −(y0 , . . . , yj−1 )S j−1,i−1 .
Now, (s0,j , . . . , si−1,j ) · (x0 , . . . , xi−1 ) = −(y0 , . . . , yj−1 )S j−1,i−1 · (x0 , . . . , xi−1 ) =
−(y0 , . . . , yj−1 )S j−1,i−1 (x0 , . . . , xi−1 )T
= −(x0 , . . . , xi−1 )S i−1,j−1 (y0 , . . . , yj−1 )T
=
−(x0 , . . . , xi−1 )S i−1,j−1 · (y0 , . . . , yj−1 ) = (si,0 , . . . , si,j−1 ) · (y0 , . . . , yj−1 )

28

• If a voter i votes for a wrong cadidate for sk then i, k ⊖ i ∈ ∆e .
• If νk > 2#(Nk ∩ ∆e ) then a majority of voters vote for the right value sk .
Proof. The first two items are deduced from what has been said before. Consider the sets A = {i ∈ Nk : i, k ⊖ i ∈ ∆e }, B = {i ∈ Nk : i ∈ ∆e , k ⊖ i 6∈ ∆e },
C = {i ∈ Nk : i 6∈ ∆e , k ⊖ i ∈ ∆e }, D = {i ∈ Nk : i, k ⊖ i 6∈ ∆e }. By the previous
items, the wrong votes are at most #A while the right votes are at least #D.
Obviously, νk = #A + #B + #C + #D, #(Nk ∩ ∆e ) = #A + #B = #A + #C.
So, the difference between the right and the wrong votes is at least #D − #A =
νk − 2#A − #B − #C = νk − 2#(Nk ∩ ∆e ) > 0.
The conclusion of this section is the next theorem.
Theorem 65. If νi > 2#(Ni ∩ ∆e ) for all i 6∈ W then e is correctable by CW .

2.2 The ν sequence, classical codes, and Feng-Rao improved
codes
From the equality #∆e = t we deduce the next lemma.
Lemma 66. If the number t of errors in e satisfies t 6 ⌊ νi2−1 ⌋, then νi > 2#(Ni ∩∆e ).
2.2.1 The ν sequence and the minimum distance of classical codes
Theorem 65 and Lemma 66 can be used in order to get an estimate of the minimum distance of a one-point code. The next definition arises from [23, 35, 39].
Definition 67. The order bound on the minimum distance of the classical code CW ,
with W = {0, . . . , m} is
dORD (Cm ) = min{νi : i > m}.
The order bound is also referred to as the Feng-Rao bound. The order bound
is proved to be a lower bound on the minimum distance for classical codes
[23, 35, 39].
Lemma 68. d(Cm ) > dORD (Cm ).
From Lemma 51 we deduce that νi+1 6 νi+2 and so dORD (Ci ) = νi+1 for all
i > 2c − g − 2.
A refined version of the order bound is
1 ,...,Pn
(Cm ) = min{νi : i > m, Ci 6= Ci+1 }.
dP
ORD
1 ,...,Pn
depends
While dORD only depends on the Weierstrass semigroup, dP
ORD
also on the points P1 , . . . , Pn . Since our point of view is that of numerical semigroups we will concentrate on dORD .
Generalized Hamming weights are a generalization of the minimum distance of a code with many applications to coding theory but also to other fields

29

such as cryptography. For the generalized Hamming weights of one-point
codes there is a generalization of the order bound based also on the associated Weierstrass semigroups. We will not discuss this topic here but the reader
interested in it can see [34, 22].
2.2.2 On the order bound on the minimum distance
In this section we will find a formula for the smallest m for which dORD (Ci ) =
νi+1 for all i > m, for the case of acute semigroups. At the end we will use
Munuera-Torres and Oneto-Tamone’s results to generalize this formula.
Remark 69. Let Λ be a non-ordinary numerical semigroup with conductor c, subconductor c′ and dominant d. Then, c′ + d > c. Indeed, c′ + d ∈ Λ and by Remark 33 it
is strictly larger than d. So, it must be larger than or equal to c.
Theorem 70. Let Λ be a non-ordinary acute numerical semigroup with enumeration
λ, conductor c, subconductor c′ and dominant d. Let
m = min{λ−1 (c + c′ − 2), λ−1 (2d)}.

(6)

Then,
1. νm > νm+1
2. νi 6 νi+1 for all i > m.
Proof. Following the notations in Lemma 51, for i > λ−1 (c), g(i) = g. Thus, for
i > λ−1 (c) we have
νi 6 νi+1 if and only if #D(i + 1) > #D(i) − 1.

(7)

Let l = c − d − 1. Notice that l is the number of gaps between the conductor
and the dominant. Since Λ is acute, the l integers before c′ are also gaps. Let
us call k = λ−1 (c′ + d). For all 1 6 i 6 l, both (c′ − i) and (d + i) are in D(k)
because they are gaps and
(c′ − i) + (d + i) = c′ + d.
Moreover, there are no more gaps in D(k) because, if j 6 c′ −l−1 then c′ +d−j >
d + l + 1 = c and so c′ + d − j ∈ Λ. Therefore,
D(k) = {c′ − i : 1 6 i 6 l} ∪ {d + i : 1 6 i 6 l}.
Now suppose that j > k. By Remark 69, λk > c and so λj = λk + j − k =
c′ + d + j − k. Then,
D(j) = A(j) ∪ B(j),

30

where
A(j)

B(j)

=

=




{c′ − i : 1 6 i 6 l − j + k}
∪{d + i : j − k + 1 6 i 6 l}


∅

∅



{d + i : 1 6 i 6 λj − 2d − 1}
 {d + i : λj − d − c + 1 6 i 6 l}


∅

if λk 6 λj 6 c + c′ − 2,
otherwise.
if λk 6 λj 6 2d + 1
if 2d + 2 6 λj 6 c + d,
if c + d 6 λj 6 2c − 2,
if λj > 2c − 1.

Notice that A(j) ∩ B(j) = ∅ and hence

#D(j) = #A(j) + #B(j).
We have
#A(j)

#B(j)

=

=

So,
#A(j + 1) =



2(l − j + k)
0


0



λj − 2d − 1
 2c − 1 − λj


0


#A(j) − 2
#A(j)


#B(j)



#B(j) + 1
#B(j + 1) =
#B(j) − 1



#B(j)

if λk 6 λj 6 c + c′ − 2,
otherwise.
if λk 6 λj 6 2d + 1,
if 2d + 2 6 λj 6 c + d,
if c + d 6 λj 6 2c − 2,
if λj > 2c − 1.
if λk 6 λj 6 c + c′ − 2,
otherwise.
if λk 6 λj 6 2d
if 2d + 1 6 λj 6 c + d − 1
if c + d 6 λj 6 2c − 2
if λj > 2c − 1

Notice that c + c′ − 2 < c + d. Thus, for λj > c + d,

#D(j) − 1 if c + d 6 λj 6 2c − 2,
#D(j + 1) =
#D(j)
if λj > 2c − 1.
Hence, by (7), νi 6 νi+1 for all i > λ−1 (c + d) because λ−1 (c + d) > λ−1 (c).
Now, let us analyze what happens if λj < c + d.
If c + c′ − 2 6 2d then

 #D(j) − 2 if λk 6 λj 6 c + c′ − 2,
#D(j)
if c + c′ − 1 6 λj 6 2d,
#D(j + 1) =

#D(j) + 1 if 2d + 1 6 λj 6 c + d − 1.
and if 2d + 1 6 c + c′ − 2 then

 #D(j) − 2
#D(j) − 1
#D(j + 1) =

#D(j) + 1

if λk 6 λj 6 2d,
if 2d + 1 6 λj 6 c + c′ − 2,
if c + c′ − 1 6 λj 6 c + d − 1.

So, by (7) and since both c + c′ − 2 and 2d are larger than or equal to c, the
result follows.
31

Table 3: Klein quartic
i λi νi dORD (Ci )
0 0
1
2
1 3
2
2
2 5
2
2
3 6
3
2
4 7
2
4
5 8
4
4
Corollary 71. Let Λ be a non-ordinary acute numerical semigroup with enumeration
λ, conductor c and subconductor c′ . Let
m = min{λ−1 (c + c′ − 2), λ−1 (2d)}.
Then, m is the smallest integer for which
dORD (Ci ) = νi+1
for all i > m.
Example 72. Recall the Weierstrass semigroup at the point P0 on the Klein quartic
that we presented in Example 5. Its conductor is 5, its dominant is 3 and its subconductor is 3. In Table 3 we have, for each integer from 0 to λ−1 (2c − 2), the values λi ,
νi and dORD (Ci ).
For this example, λ−1 (c + c′ − 2) = λ−1 (2d) = 3 and so, m = min{λ−1 (c + c′ −
2), λ−1 (2d)} = 3. We can check that, as stated in Theorem 70, ν3 > ν4 and νi 6 νi+1
for all i > 3. Moreover, as stated in Corollary 71, dORD (Ci ) = νi+1 for all i > 3
while dORD (C2 ) 6= ν3 .
Lemma 73. Let Λ be a non-ordinary numerical semigroup with conductor c, subconductor c′ and dominant d.
1. If Λ is symmetric then min{c + c′ − 2, 2d} = c + c′ − 2 = 2c − 2 − λ1 ,
2. If Λ is pseudo-symmetric then min{c + c′ − 2, 2d} = c + c′ − 2,
3. If Λ is Arf then min{c + c′ − 2, 2d} = 2d,
4. If Λ is generated by an interval then min{c + c′ − 2, 2d} = c + c′ − 2.
Proof.
1. We already saw in the proof of Lemma 38 that if Λ is symmetric then
d = c − 2. So, c + c′ − 2 = d + c′ 6 2d because c′ 6 d. Moreover, by
Lemma 10, any non-negative integer i is a gap if and only if c − 1 − i ∈ Λ.
This implies that c′ − 1 = c − 1 − λ1 and so c′ = c − λ1 . Therefore,
c + c′ − 2 = 2c − 2 − λ1 .
32

2. If Λ is pseudo-symmetric and non-ordinary then d = c − 2 because 1 is a
gap different from (c − 1)/2. So, c + c′ − 2 = d + c′ 6 2d.
3. If Λ is Arf then c′ = d. Indeed, if c′ < d then d − 1 ∈ Λ and, by Lemma 16,
d − 1 > c, a contradiction. Since d 6 c − 2, we have 2d 6 c + c′ − 2.
4. Suppose Λ is generated by the interval {i, i + 1, . . . , j}. By Lemma 26,
there exists k such that c = ki and d = (k − 1)j. We have that c − d 6 j − i,
because otherwise (k + 1)i − kj = c − d − (j − i) > 1, and hence kj + 1
would be a gap greater than c. On the other hand d − c′ > j − i, and hence
2d − (c + c′ − 2) = d − c + d − c′ + 2 > i − j + j − i + 2 = 2.

Example 74. Consider the Hermitian curve over F16 . Its numerical semigroup is generated by 4 and 5. So, this is a symmetric numerical semigroup because it is generated
by two coprime integers, and it is also a semigroup generated by the interval {4, 5}.
In Table 4 we include, for each integer from 0 to 16, the values λi , νi and dORD (Ci ).
Notice that in this case the conductor is 12, the dominant is 10 and the subconductor
is 8. We do not give the values in the table for i > λ−1 (2c − 1) − 1 = 16 because
dORD (Ci ) = νi+1 for all i > λ−1 (2c − 1) − 1. We can check that, as follows from
Theorem 70 and Lemma 73, λ−1 (c + c′ − 2) = 12 is the largest integer m with
νm > νm+1 and so the smallest integer for which dORD (Ci ) = νi+1 for all i > m.
Notice also that, as pointed out in Lemma 73, c + c′ − 2 = 2c − 2 − λ1 .
Furthermore, in this example there are 64 rational points on the curve different
from P∞ and the map ϕ evaluating the functions of A at these 64 points satisfies
that the words ϕ(f0 ), . . . , ϕ(f57 ) are linearly independent whereas ϕ(f58 ) is linearly
1 ,...,Pn
(Ci ) = dORD (Ci ) for all i 6 56.
dependent to the previous ones. So, dP
ORD
Example 75. Let us consider now the semigroup of the fifth code associated to the
second tower of Garcia and Stichtenoth over F4 . As noticed in Example 18, this is
an Arf numerical semigroup. We set in Table 5 the values λi , νi and dORD (Ci ) for
each integer from 0 to 25. In this case the conductor is 24, the dominant is 20 and the
subconductor is 20. As before, we do not give the values for i > λ−1 (2c − 1) − 1 = 25.
We can check that, as follows from Theorem 70 and Lemma 73, λ−1 (2d) = 19 is the
largest integer m with νm > νm+1 and so, the smallest integer for which dORD (Ci ) =
νi+1 for all i > m.
Munuera and Torres in [45] and Oneto and Tamone in [47] proved that for
any numerical semigroup m 6 min{c + c′ − 2 − g, 2d − g}. Notice that for acute
semigroups this inequality is an equality.
Munuera and Torres in [45] introduced the definition of near-acute semigroups. They proved that the formula m = min{c + c′ − 2 − g, 2d − g} not only
applies for acute semigroups but also for near-acute semigroups. Next we give
the definition of near-acute semigroups.
Definition 76. A numerical semigroup with conductor c, dominant d and subdominant d′ is said to be a near-acute semigroup if either c− d 6 d− d′ or 2d− c+ 1 6∈ Λ.
33

Table 4: Hermitian curve
i
λi νi dORD (Ci )
0
0
1
2
1
4
2
2
2
5
2
3
3
8
3
3
4
9
4
3
5 10 3
4
6 12 4
4
7 13 6
4
8 14 6
4
9 15 4
5
10 16 5
8
11 17 8
8
12 18 9
8
13 19 8
9
14 20 9
10
15 21 10
12
16 22 12
12
Oneto and Tamone in [47] proved that m = min{c + c′ − 2 − g, 2d − g} if and
only if c + c′ − 2 6 2d or 2d − c + 1 6∈ Λ. Let us see next that these conditions in
Oneto and Tamone’s result are equivalent to having a near-acute semigroup.
Lemma 77. For a numerical semigroup the following are equivalent
1. c − d 6 d − d′ or 2d − c + 1 6∈ Λ,
2. c + c′ − 2 6 2d or 2d − c + 1 6∈ Λ.
Proof. Let us see first that (1) implies (2). If 2d − c + 1 6∈ Λ then it is obvious.
Otherwise the condition c − d 6 d − d′ is equivalent to d′ 6 2d − c which,
together with 2d − c + 1 ∈ Λ implies c′ 6 2d − c + 1 by definition of c′ . This in
turn implies that c + c′ − 2 < c + c′ − 1 6 2d.
To see that (1) is a consequence of (2) notice that by definition, d′ 6 c′ − 2.
Then, if c + c′ − 2 6 2d, we have d − d′ > d − c′ + 2 > c − d.
From all these results one concludes the next theorem.
Theorem 78.

1. For any numerical semigroup m 6 min{c + c′ − 2 − g, 2d − g}.

2. m = min{c + c′ − 2 − g, 2d − g} if and only if the corresponding numerical
semigroup is near-acute.
In [48] Oneto and Tamone give further results on m and in [49] the same
authors conjecture that for any numerical semigroup,
λm > c + d − λ1 .
34

Table 5:
i
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Garcia-Stichtenoth tower
λi νi dORD (Ci )
0
1
2
16 2
2
20 2
2
24 2
2
25 2
2
26 2
2
27 2
2
28 2
2
29 2
2
30 2
2
31 2
2
32 3
2
33 2
2
34 2
2
35 2
2
36 4
2
37 2
2
38 2
2
39 2
4
40 5
4
41 4
4
42 4
4
43 4
6
44 6
6
45 6
6
46 6
6

35

2.2.3 The ν sequence and Feng-Rao improved codes
The one-point codes whose set W of parity checks is selected so that the orders
outside W satisfy the hypothesis of Lemma 66 and W is minimal with this
property are called Feng-Rao improved codes. They were defined in [24, 35].
Definition 79. Given a rational point P of an algebraic smooth curve XF defined over
Fq with Weierstrass semigroup Λ and sequence ν with associated basis z0 , z1 , . . . and
given n other different points P1 , . . . , Pn of XF , the associated Feng-Rao improved
code guaranteeing correction of t errors is defined as
CR̃(t) =< (zi (P1 ), . . . , zi (Pn )) : i ∈ R̃(t) >⊥ ,
where
R̃(t) = {i ∈ N0 : νi < 2t + 1}.
2.2.4 On the improvement of the Feng-Rao improved codes
Feng-Rao improved codes will actually give an improvement with respect to
classical codes only if νi is decreasing at some i. We next study this condition.
Lemma 80. If Λ is an ordinary numerical semigroup with enumeration λ then

if i = 0,
 1
2
if 1 6 i 6 λ1 ,
νi =

i − λ1 + 2 if i > λ1 .
Proof. It is obvious that ν0 = 1 and that νi = 2 whenever 0 < λi < 2λ1 . So,
since 2λ1 = λλ1 +1 , we have that νi = 2 for all 1 6 i 6 λ1 . Finally, if λi > 2λ1
then all non-gaps up to λi −λ1 are in Ni as well as λi , and none of the remaining
non-gaps are in Ni . Now, if the genus of Λ is g, then νi = λi − λ1 + 2 − g and
λi = i + g. So, νi = i − λ1 + 2.
As a consequence of Lemma 80, the ν sequence is non-decreasing if Λ is
an ordinary numerical semigroup. We will see in this section that ordinary
numerical semigroups are in fact the only semigroups for which the ν sequence
is non-decreasing.
Lemma 81. Suppose that for the semigroup Λ the ν sequence is non-decreasing. Then
Λ is Arf.
Proof. Let λ be the enumeration of Λ. Let us see by induction that, for any
non-negative integer i,
(i) Nλ−1 (2λi ) = {j ∈ N0 : j 6 i} ⊔ {λ−1 (2λi − λj ) : 0 6 j < i}, where ⊔ means
the union of disjoint sets.
(ii) Nλ−1 (λi +λi+1 ) = {j ∈ N0 : j 6 i} ⊔ {λ−1 (λi + λi+1 − λj ) : 0 6 j 6 i}.
36

Notice that if (i) is satisfied for all i, then {j ∈ N0 : j 6 i} ⊆ Nλ−1 (2λi ) for all i,
and hence by Lemma 23 Λ is Arf.
It is obvious that both (i) and (ii) are satisfied for the case i = 0.
Suppose i > 0. By the induction hypothesis, νλ−1 (λi−1 +λi ) = 2i. Now, since
(νi ) is not decreasing and 2λi > λi−1 + λi , we have νλ−1 (2λi ) > 2i. On the other
hand, if j, k ∈ N0 are such that j 6 k and λj + λk = 2λi then λj 6 λi and
λk > λi . So, λ(Nλ−1 (2λi ) ) ⊆ {λj : 0 6 j 6 i} ⊔ {2λi − λj : 0 6 j < i} and hence
νλ−1 (2λi ) > 2i if and only if Nλ−1 (2λi ) = {j ∈ N0 : j 6 i} ⊔ {λ−1 (2λi − λj ) : 0 6
j < i}. This proves (i).
Finally, (i) implies νλ−1 (2λi ) = 2i + 1 and (ii) follows by an analogous argumentation.
Theorem 82. The only numerical semigroups for which the ν sequence is non-decreasing are ordinary numerical semigroups.
Proof. It is a consequence of Lemma 81, Lemma 38, Theorem 70 and Lemma 80.
Corollary 83. The only numerical semigroup for which the ν sequence is strictly
increasing is the trivial numerical semigroup.
Proof. It is a consequence of Theorem 82 and Lemma 80.
As a consequence of Theorem 82 we can show that the only numerical semigroups for which the associated classical codes are not improved by the FengRao improved codes, at least for one value of t, are ordinary semigroups.
Corollary 84. Given a numerical semigroup Λ define m(δ) = max{i ∈ N0 : νi < δ}.
There exists at least one value of δ for which {i ∈ N0 : νi < δ} ( {i ∈ N0 : i 6 m(δ)}
if and only if Λ is non-ordinary.

2.3 Generic errors and the τ sequence
All the results in these sections are based on [14, 15, 10]. Correction of generic
errors has already been considered in [53, 50, 36].
2.3.1 Generic errors
Definition 85. The points Pi1 , . . . , Pit (Pij 6= P ) are generically distributed if no
non-zero function generated by z0 , . . . , zt−1 vanishes in all of them. In the context of
one-point codes, generic errors are those errors whose non-zero positions correspond
to generically distributed points. Equivalently, e is generic if and only if ∆e = ∆t :=
{0, . . . , t − 1}.
Generic errors of weight t can be a very large proportion of all possible errors of weight t [33]. Thus, by restricting the errors to be corrected to generic
errors the decoding requirements become weaker and we are still able to correct almost all errors. In some of these references generic errors are called independent errors.
37

Example 86 (Generic sets of points in Hq ). Recall that the Hermitian curve from
Example 4. It is defined over Fq2 and its affine equation is xq+1 = y q + y.
The unique point at infinity is P∞ = (0 : 1 : 0). If b ∈ Fq then bq +b = T r(b) = 0
and the unique affine point with y = b is (0, b). There are a total of q such points. If b ∈
Fq2 \ Fq then bq + b = T r(b) ∈ Fq \ {0} and there are q + 1 solutions of xq+1 = bq + b,
so, there are q + 1 different affine points with y = b. There are a total of (q 2 − q)(q + 1)
such points. The total number of affine points is then q + (q 2 − q)(q + 1) = q 3 .
If we distinguish the point P∞ , we can take z0 = 1, z1 = x, z2 = y, z3 = x2 ,
z4 = xy, z5 = y 2 . . .
Non-generic sets of two points are pairs of points satisfying xq+1 = y q + y and
simultaneously vanishing at f = z1 + az0 = x + a for some a ∈ Fq2 . The expression
2 q
x + a represents a line with q points. There are q 2 such lines. There
 are a total of q 2
2 q
pairs of colinear points over lines of the form x + a and so q 2 non-generic errors.
q 2 (q)
1
Consequently, the portion of non-generic errors of weight 2 is q32 = q2 +q+1
.
(2)
q+1
q
A set of three points is non-generic if the points satisfy x
= y + y and simultaneously vanish at f = z1 + az0 = x + a for some a ∈ Fq2 or at f = z2 + az1 + bz0 =
y + ax + b for some a, b ∈ Fq2 .
The expression x+ a represents a line (which we call of type 1) with q points. There
are q 2 lines of type 1.
The line y + ax + b is called of type 2 if aq+1 = bq + b and of type 3 otherwise.
There are q 3 lines of type 2 and q 4 − q 3 lines of type 3.
Lines of type 2 have only one point. Indeed, a point on Hq and on the line y +ax+b
must satisfy xq+1 = (−ax − b)q + (−ax − b) = −(ax)q − ax − aq+1 . Notice that
(x + aq )q+1 = (x + aq )q (x + aq ) = (xq + a)(x + aq ) = xq+1 + xq aq + ax + aq+1 .
So, x = −aq is the unique solution to xq+1 = −(ax)q − ax − aq+1 and so the unique
point of Hq on the line y + ax + b is (−aq , aq+1 − b).
Lines of type 3 have q + 1 points. This follows by a counting argument. On
one hand, as seen before, a point on Hq and on the line y + ax + b must satisfy
xq+1 = −(ax)q − ax − bq − b. There are at most q + 1 different values of x satisfying
this equation and so at most q + 1 different points of Hq on the line y + ax + b. On
3
the other hand there are a total of q2 pairs of affine points. Each
 pair meets only in
one line. The number of pairs sharing lines of type 1 is q 2 q2 , the number of pairs
sharing lines of type 2 is 0 and the number of pairs sharing lines of type 3 is at most
q 3 (q − 1) q+1
2 , with equality only if all lines of type 3 have q + 1 points. Since


3
2 q
3
q 2 + q (q − 1) q+1
= q2 , we deduce that all the lines of type 3 must have q + 1
2
points.

In total there are q 2 3q sets of three points sharing a line of type 1 and (q 4 −

q 3 ) q+1
sets of three points sharing a line of type 3.
3
q2 (q3)+q3 (q−1)(q+1
1
3 )
.
= q2 +q+1
The portion of non-generic errors of weight 3 is then
3
(q3 )

38

2.3.2 Conditions for correcting generic errors
In the next lemma we find conditions guaranteeing the majority voting step for
generic errors. It is a reformulation of results that appeared in [51, 14, 10]
Lemma 87. Let Σt = N0 \ ∆t = t + N0 . The following conditions are equivalent.
1. νk > 2#(Nk ∩ ∆t ),
2. k ∈ Σt ⊕ Σt ,
3. τk > t.
Proof. Let A = {i ∈ Nk : i, k ⊖ i ∈ ∆t }, D = {i ∈ Nk : i, k ⊖ i ∈ Σt }. By an
argument analogous to that in the proof of Lemma 64, νk > 2#(Nk ∩ ∆e ) is
equivalent to #D > #A. If this inequality is satisfied then #D > 0 and so k ∈
Σt ⊕Σt . On the other hand, min Σt ⊕Σt = t⊕t > (t−1)⊕(t−1) = max ∆t ⊕∆t .
So, Σt ⊕ Σt ∩ ∆t ⊕ ∆t = ∅ and, if k ∈ Σt ⊕ Σt then k 6∈ ∆t ⊕ ∆t and so #A = 0
implying #D > #A.
The equivalence of k ∈ Σt ⊕ Σt and τk > t is straightforward.
The one-point codes whose set W of parity checks is selected so that the
orders outside W satisfy the hypothesis of Lemma 87 and W is minimal with
this property are called improved codes correcting generic errors. They were
defined in [4, 14].
Definition 88. Given a rational point P of an algebraic smooth curve XF defined
over Fq with Weierstrass semigroup Λ and sequence ν with associated basis z0 , z1 , . . .
and given n other different points P1 , . . . , Pn of XF , the associated improved code
guaranteeing correction of t generic errors is defined as
CR̃∗ (t) =< (zi (P1 ), . . . , zi (Pn )) : i ∈ R̃∗ (t) >⊥ ,
where

R̃∗ (t) = {i ∈ N0 : τi < t}.

2.3.3 Comparison of improved codes and classical codes correcting generic
errors
Classical evaluation codes are those codes for which the set of parity checks
corresponds to all the elements up to a given order. Thus, the classical evaluation code with maximum dimension correcting t generic errors is defined by
the set of checks R∗ (t) = {i ∈ N0 : i 6 m(t)} where m(t) = max{i ∈ N0 :
τi < t}. Then, by studying the monotonicity of the τ sequence we can compare
e ∗ (t) and R∗ (t) and the associated codes.
R
It is easy to check that for the trivial numerical semigroup one has τ2i =
τ2i+1 = i for all i ∈ N0 . That is, the τ sequence is
0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, . . .
The next lemma determines the τ sequence of all non-trivial ordinary semigroups.
39

Lemma 89. The non-trivial ordinary numerical semigroup with conductor c has τ
sequence given by

0
 if i 6 c
τi =
i−c+1
if i > c
2

Proof. Suppose that the numerical semigroup has enumeration λ. On one hand,
λ1 , . . . , λc are all generators and thus τi = 0 for i 6 c. For i > c, λi =
c + i − 1 > 2c. So, if λi is even (which is equivalent to c + i being odd) then
τi = λ−1 ( λ2i ) = c+i−1
− c + 1 = i−c+1
= ⌊ i−c+1
⌋. If λi is odd (which is equiv2
2
2
alent to either both c and i being even or being odd) then τi = λ−1 ( λi2−1 ) =
c+i−2
i−c+1
− c + 1 = i−c
⌋.
2
2 = ⌊ 2

Remark 90. The formula in Lemma 89 can be reformulated as τj = 0 for all j 6 c
and, for all i > 0, τc+2i+1 = τc+2i+2 = i + 1.
The next lemma gives, for non-ordinary semigroups, the smallest index m
for which τ is non-decreasing from τm on. We will use the notation ⌊a⌋Λ to
denote the semigroup floor of a non-negative integer a, that is, the largest nongap of Λ which is at most a.
Lemma 91. Let Λ be a non-ordinary semigroup with dominant d and let m = λ−1 (2d),
then
1. τm = c − g − 1 > τm+1 ,
2. τi < c − g − 1 for all i < m,
3. τi 6 τi+1 for all i > m.
Proof. For statement 1 notice that both 2d and 2d + 1 belong to Λ because they
must be larger than the conductor. Furthermore, τλ−1 (2d) = λ−1 (d) = c − g − 1
while τλ−1 (2d+1) = τλ−1 (2d)+1 < λ−1 (d) because d + 1 6∈ Λ.
Statement 2 follows from the fact that if λi < 2d then τi < λ−1 (d) = c−g −1.
For statement 3 suppose that i > m. Notice that 2d is the largest non-gap
that can be written as a sum of two non-gaps both of them smaller than the
conductor c. Then if j 6 k 6 i and λj + λk = λi it must be λk > c and so
τi = λ−1 (⌊λi − c⌋Λ ). Since both λ−1 and ⌊·⌋Λ are non-decreasing, so is τi for
i > m.
Corollary 92. The only numerical semigroups for which the τ sequence is non-decreasing
are ordinary semigroups.
A direct consequence of Corollary 92 is that the classical code determined
e ∗ (t) at least
by R∗ (t) is always worse than the improved code determined by R
for one value of t unless the corresponding numerical semigroup is ordinary.
e∗ (t) and R∗ (t) coincide from a certain
From Lemma 91 we can derive that R
point and we can find this point. We summarize the results of this section in
the next Corollary.

40

Corollary 93.

e∗ (t) ⊆ R∗ (t) for all t ∈ N0 .
1. R

e∗ (t) = R∗ (t) for all t > c − g.
2. R

e∗ (t) = R∗ (t) for all t ∈ N0 if and only if the associated numerical semigroup
3. R
is ordinary.
Proof. Statement 1 is a consequence of the definition of R∗ (t). Statement 2 is
clear if the associated semigroup is ordinary. Otherwise it follows from the
fact proved in Lemma 91 that the largest value of τi before it starts being nondecreasing is precisely c − g − 1 and that before that all values of τi are smaller
than c − g − 1. Statement 3 is a consequence of Corollary 92.
2.3.4 Comparison of improved codes correcting generic errors and Feng–
Rao improved codes
In next theorem we compare τi with ⌊ νi2−1 ⌋ and this will give a new characterization of Arf semigroups. Recall that t 6 ⌊ νi2−1 ⌋ guarantees the computation
of syndromes of order i when performing majority voting (Lemma 64).
Theorem 94. Let Λ be a numerical semigroup with conductor c, genus g, and associated sequences τ and ν. Then
1. τi > ⌊ νi2−1 ⌋ for all i ∈ N0 ,
2. τi = ⌊ νi2−1 ⌋ for all i > 2c − g − 1,
3. τi = ⌊ νi2−1 ⌋ for all i ∈ N0 if and only if Λ is Arf.
Proof. Let λ be the enumeration of Λ.
1. Suppose that the elements in Ni are ordered Ni,0 < Ni,1 < Ni,2 < · · · <
Ni,νi −1 . On one hand τi = Ni,⌊ νi −1 ⌋ . On the other hand Ni,j > j and this
2
finishes the proof of the first statement.
2. The result is obvious for the trivial semigroup. Thus we can assume that
c > g+1. Notice that τi = Ni,⌊ νi −1 ⌋ = ⌊ νi2−1 ⌋ if and only if all integers less
2

than or equal to ⌊ νi2−1 ⌋ belong to Ni . Now let us prove that if i > 2c−g −1
then all integers less than or equal to ⌊ νi2−1 ⌋ belong to Ni . Indeed, if
j 6 ⌊ νi2−1 ⌋ then λj 6 λi /2 and λi − λj > λi − λi /2 = λi /2 > c − 1/2. Since
λi − λj ∈ N0 this means that λi − λj > c and so λi − λj ∈ Λ.

3. Suppose that Λ is Arf. We want to show that for any non-negative integer
i, all non-negative integers less than or equal to ⌊ νi2−1 ⌋ belong to Ni . By
definition of τi there exists k with τi 6 k 6 i and λτi + λk = λi . Now, if j
is a non-negative integer with j 6 ⌊ νi2−1 ⌋, by statement 1 it also satisfies
j 6 τi . Then λi − λj = λτi + λk − λj ∈ Λ by the Arf property, and so
j ∈ Ni .

41

On the other hand, suppose that τi = ⌊ νi2−1 ⌋ for all non-negative integer
i. This means that all integers less than or equal to τr belong to Nr for
any non-negative integer r. If i > j > k then τλ−1 (λi +λj ) > j > k and
by hypothesis k ∈ Nλ−1 (λi +λj ) , which means that λi + λj − λk ∈ Λ. This
implies that Λ is Arf.

Statement 1) of Lemma 58 for the case when i > 0 is a direct consequence
of Theorem 94 and Lemma 51.
Finally, Theorem 94 together with Lemma 58 has the next corollary. Different versions of this result appeared in [4, 14, 10]. The importance of the result
is that it shows that the improved codes correcting generic errors do always require at most as many checks as the Feng–Rao improved codes correcting any
kind of errors. It also states conditions under which their redundancies are
equal and characterizes Arf semigroups as the unique semigroups for which
there is no improvement.
Corollary 95.

e∗ (t) ⊆ R(t)
e for all t ∈ N0 .
1. R

e∗ (t) = R(t)
e for all t > c − g.
2. R

e∗ (t) = R(t)
e for all t ∈ N0 if and only if the associated numerical semigroup is
3. R
Arf.

Proof. Statement 1. and 3. follow immediately from Theorem 94 and the fact


e = {i ∈ N0 : νi −1 < t} and R
e ∗ (t) = {i ∈ N0 : τi < t}. For statement
that R(t)
2
2., we can use that for i > 2c − g − 1, τi = ⌊ νi2−1 ⌋ (Theorem 94) and that for
i > 2c − g − 1, τi > c − g − 1 (Lemma 58), being c − g − 1 the largest value of τj
before it starts being non-decreasing (Lemma 91).

Further reading
We tried to cite the specific bibliography related to each section within the text.
Next we mention some more general references: The book [59] has many results on numerical semigroups, including some of the problems presented in
the first section of this chapter but also many others. The book [57] is also
devoted to numerical semigroups from the perspective of the Frobenius’ coin
exchange problem. Algebraic geometry codes have been widely explained in
different books such as [72, 67, 56]. For one-point codes and also their relation
with Weierstrass semigroups an important reference is the chapter [35].

Acknowledgments
The author would like to thank Michael E. O’Sullivan, Ruud Pellikaan and
Pedro A. Garcı́a-Sánchez for many helpful discussions. She would also like
42

to thank all the coauthors of the papers involved in this chapter. They are,
by order of appearence of the differet papers: Michael E. O’Sullivan, Pedro A.
Garcı́a-Sánchez, Anna de Mier, and Stanislav Bulygin.
This work was partly supported by the Spanish Government through projects
TIN2009-11689 “RIPUP” and CONSOLIDER INGENIO 2010 CSD2007-00004
“ARES”, and by the Government of Catalonia under grant 2009 SGR 1135.

References
[1] Roger Apéry. Sur les branches superlinéaires des courbes algébriques. C.
R. Acad. Sci. Paris, 222:1198–1200, 1946.
[2] Valentina Barucci, David E. Dobbs, and Marco Fontana. Maximality properties in numerical semigroups and applications to one-dimensional analytically irreducible local domains. Mem. Amer. Math. Soc., 125(598):x+78,
1997.
[3] Victor Blanco, Pedro A. Garcı́a Sánchez, and Justo Puerto. Counting numerical semigroups with short generating functions. International Journal
of Algebra and Computation, Accepted.
[4] Maria Bras-Amorós. Improvements to evaluation codes and new characterizations of Arf semigroups. In Applied algebra, algebraic algorithms and
error-correcting codes (Toulouse, 2003), volume 2643 of Lecture Notes in Comput. Sci., pages 204–215. Springer, Berlin, 2003.
[5] Maria Bras-Amorós. Acute semigroups, the order bound on the minimum
distance, and the Feng-Rao improvements. IEEE Trans. Inform. Theory,
50(6):1282–1289, 2004.
[6] Maria Bras-Amorós. Addition behavior of a numerical semigroup. In
Arithmetic, geometry and coding theory (AGCT 2003), volume 11 of Sémin.
Congr., pages 21–28. Soc. Math. France, Paris, 2005.
[7] Maria Bras-Amorós. A note on numerical semigroups. IEEE Trans. Inform.
Theory, 53(2):821–823, 2007.
[8] Maria Bras-Amorós. Fibonacci-like behavior of the number of numerical
semigroups of a given genus. Semigroup Forum, 76(2):379–384, 2008.
[9] Maria Bras-Amorós. Bounds on the number of numerical semigroups of
a given genus. J. Pure Appl. Algebra, 213(6):997–1001, 2009.
[10] Maria Bras-Amorós. On numerical semigroups and the redundancy of
improved codes correcting generic errors. Des. Codes Cryptogr., 53(2):111–
118, 2009.
[11] Maria Bras-Amorós and Stanislav Bulygin. Towards a better understanding of the semigroup tree. Semigroup Forum, 79(3):561–574, 2009.
43

[12] Maria Bras-Amorós and Anna de Mier. Representation of numerical semigroups by Dyck paths. Semigroup Forum, 75(3):677–682, 2007.
[13] Maria Bras-Amorós and Pedro A. Garcı́a-Sánchez. Patterns on numerical
semigroups. Linear Algebra Appl., 414(2-3):652–669, 2006.
[14] Maria Bras-Amorós and Michael E. O’Sullivan. The correction capability
of the Berlekamp-Massey-Sakata algorithm with majority voting. Appl.
Algebra Engrg. Comm. Comput., 17(5):315–335, 2006.
[15] Maria Bras-Amorós and Michael E. O’Sullivan. Duality for some families
of correction capability optimized evaluation codes. Adv. Math. Commun.,
2(1):15–33, 2008.
[16] Antonio Campillo and José Ignacio Farrán. Computing Weierstrass semigroups and the Feng-Rao distance from singular plane models. Finite
Fields Appl., 6(1):71–92, 2000.
[17] Antonio Campillo, José Ignacio Farrán, and Carlos Munuera. On the parameters of algebraic-geometry codes related to Arf semigroups. IEEE
Trans. Inform. Theory, 46(7):2634–2638, 2000.
[18] Frank Curtis. On formulas for the Frobenius number of a numerical semigroup. Math. Scand., 67(2):190–192, 1990.
[19] David E. Dobbs and Gretchen L. Matthews. On a question of Wilf concerning numerical semigroups. International Journal of Commutative Rings,
3(2), 2003.
[20] Sergi Elizalde. Improved bounds on the number of numerical semigroups
of a given genus. Journal of Pure and Applied Algebra, 214:1404–1409, 2010.
[21] Hershel M. Farkas and Irwin Kra. Riemann surfaces, volume 71 of Graduate
Texts in Mathematics. Springer-Verlag, New York, second edition, 1992.
[22] José Ignacio Farrán and Carlos Munuera. Goppa-like bounds for the generalized Feng-Rao distances. Discrete Appl. Math., 128(1):145–156, 2003. International Workshop on Coding and Cryptography (WCC 2001) (Paris).
[23] Gui-Liang Feng and T. R. N. Rao. A simple approach for construction of
algebraic-geometric codes from affine plane curves. IEEE Trans. Inform.
Theory, 40(4):1003–1012, 1994.
[24] Gui-Liang Feng and T. R. N. Rao. Improved geometric Goppa codes. I. Basic theory. IEEE Trans. Inform. Theory, 41(6, part 1):1678–1693, 1995. Special
issue on algebraic geometry codes.
[25] Ralf Fröberg, Christian Gottlieb, and Roland Häggkvist. On numerical
semigroups. Semigroup Forum, 35(1):63–83, 1987.

44

[26] William Fulton. Algebraic curves. Advanced Book Classics. AddisonWesley Publishing Company Advanced Book Program, Redwood City,
CA, 1989. An introduction to algebraic geometry, Notes written with the
collaboration of Richard Weiss, Reprint of 1969 original.
[27] Arnaldo Garcia and Henning Stichtenoth. On the asymptotic behaviour
of some towers of function fields over finite fields. J. Number Theory,
61(2):248–273, 1996.
[28] Pedro A. Garcı́a-Sánchez and José C. Rosales. Numerical semigroups generated by intervals. Pacific J. Math., 191(1):75–83, 1999.
[29] Olav Geil. On codes from norm-trace curves. Finite Fields Appl., 9(3):351–
371, 2003.
[30] Olav Geil and Ryutaroh Matsumoto. Bounding the number of Fq -rational
places in algebraic function fields using Weierstrass semigroups. J. Pure
Appl. Algebra, 213(6):1152–1156, 2009.
[31] Massimo Giulietti.
Notes on algebraic-geometric codes.
www.math.kth.se/math/forskningsrapporter/Giulietti.pdf.
[32] David M. Goldschmidt. Algebraic functions and projective curves, volume
215 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2003.
[33] Johan P. Hansen. Dependent rational points on curves over finite fields—
Lefschetz theorems and exponential sums. In International Workshop on
Coding and Cryptography (Paris, 2001), volume 6 of Electron. Notes Discrete
Math., page 13 pp. (electronic). Elsevier, Amsterdam, 2001.
[34] Petra Heijnen and Ruud Pellikaan. Generalized Hamming weights of qary Reed-Muller codes. IEEE Trans. Inform. Theory, 44(1):181–196, 1998.
[35] Tom Høholdt, Jacobus H. van Lint, and Ruud Pellikaan. Algebraic Geometry codes, pages 871–961. North-Holland, Amsterdam, 1998.
[36] Helge Elbrønd Jensen, Rasmus Refslund Nielsen, and Tom Høholdt. Performance analysis of a decoding algorithm for algebraic-geometry codes.
IEEE Trans. Inform. Theory, 45(5):1712–1717, 1999.
[37] Nathan Kaplan. Counting numerical semigroups by genus and some
cases of a question of Wilf. Preprint.
[38] Seon Jeong Kim. Semigroups which are not Weierstrass semigroups. Bull.
Korean Math. Soc., 33(2):187–191, 1996.
[39] Christoph Kirfel and Ruud Pellikaan. The minimum distance of codes in
an array coming from telescopic semigroups. IEEE Trans. Inform. Theory,
41(6, part 1):1720–1732, 1995. Special issue on algebraic geometry codes.

45

[40] Jiryo Komeda. On non-Weierstrass gap sequqences. Technical report,
Kanagawa Institute of Technology B-13, 1989. Research Reports of Kanagawa Institute of Technology B-13.
[41] Jiryo Komeda. Non-Weierstrass numerical semigroups. Semigroup Forum,
57(2):157–185, 1998.
[42] Joseph Lewittes. Places of degree one in function fields over finite fields.
J. Pure Appl. Algebra, 69(2):177–183, 1990.
[43] Monica Madero-Craven and Kurt Herzinger. Apery sets of numerical
semigroups. Comm. Algebra, 33(10):3831–3838, 2005.
[44] Nivaldo
Medeiros.
Listing
of
numerical
http://w3.impa.br/˜nivaldo/algebra/semigroups/.

semigroups.

[45] Carlos Munuera and Fernando Torres. A note on the order bound on
the minimum distance of AG codes and acute semigroups. Adv. Math.
Commun., 2(2):175–181, 2008.
[46] Carlos Munuera, Fernando Torres, and Juan E. Villanueva. Sparse numerical semigroups. In Applied algebra, algebraic algorithms and error-correcting
codes (Tarragona, 2009), volume 5527 of Lecture Notes in Comput. Sci., pages
23–31, Berlin, 2009. Springer.
[47] Anna Oneto and Grazia Tamone. On numerical semigroups and the order
bound. J. Pure Appl. Algebra, 212(10):2271–2283, 2008.
[48] Anna Oneto and Grazia Tamone. On the order bound of one-point algebraic geometry codes. J. Pure Appl. Algebra, 213(6):1179–1191, 2009.
[49] Anna Oneto and Grazia Tamone. On some invariants in numerical semigroups and estimations of the order bound. Semigroup Forum, 81(3):483–
509, 2010.
[50] Michael E. O’Sullivan. Decoding Hermitian codes beyond (dmin − 1)/2.
In IEEE Int. Symp. Information Theory, 1997.
[51] Michael E. O’Sullivan. A generalization of the Berlekamp-Massey Sakata
algorithm. Preprint, 2001.
[52] Michael E. O’Sullivan. New codes for the Berlekamp-Massey-Sakata algorithm. Finite Fields Appl., 7(2):293–317, 2001.
[53] Ruud Pellikaan. On decoding by error location and dependent sets of
error positions. Discrete Math., 106/107:369–381, 1992. A collection of
contributions in honour of Jack van Lint.
[54] Ruud Pellikaan, Henning Stichtenoth, and Fernando Torres. Weierstrass
semigroups in an asymptotically good tower of function fields. Finite
Fields Appl., 4(4):381–392, 1998.
46

[55] Ruud Pellikaan and Fernando Torres. On Weierstrass semigroups and
the redundancy of improved geometric Goppa codes. IEEE Trans. Inform.
Theory, 45(7):2512–2519, 1999.
[56] Oliver Pretzel. Codes and algebraic curves, volume 8 of Oxford Lecture Series
in Mathematics and its Applications. The Clarendon Press Oxford University
Press, New York, 1998.
[57] Jorge 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.
[58] José Carlos Rosales and Manuel B. Branco. Irreducible numerical semigroups. Pacific J. Math., 209(1):131–143, 2003.
[59] José Carlos Rosales and Pedro A. Garcı́a-Sánchez. Numerical semigroups,
volume 20 of Developments in Mathematics. Springer, New York, 2009.
[60] José Carlos Rosales, Pedro A. Garcı́a-Sánchez, Juan Ignacio Garcı́a-Garcı́a,
and Manuel B. Branco. Systems of inequalities and numerical semigroups.
J. London Math. Soc. (2), 65(3):611–623, 2002.
[61] José Carlos Rosales, Pedro A. Garcı́a-Sánchez, Juan Ignacio Garcı́a-Garcı́a,
and Manuel B. Branco. Arf numerical semigroups. J. Algebra, 276(1):3–12,
2004.
[62] José Carlos Rosales, Pedro A. Garcı́a-Sánchez, Juan Ignacio Garcı́a-Garcı́a,
and Manuel B. Branco. Numerical semigroups with a monotonic Apéry
set. Czechoslovak Math. J., 55(130)(3):755–772, 2005.
[63] José Carlos Rosales, Pedro A. Garcı́a-Sánchez, Juan Ignacio Garcı́a-Garcı́a,
and José Antonio Jiménez Madrid. The oversemigroups of a numerical
semigroup. Semigroup Forum, 67(1):145–158, 2003.
[64] José Carlos Rosales, Pedro A. Garcı́a-Sánchez, Juan Ignacio Garcı́a-Garcı́a,
and José Antonio Jiménez Madrid. Fundamental gaps in numerical semigroups. J. Pure Appl. Algebra, 189(1-3):301–313, 2004.
[65] Neil J. A. Sloane. The On-Line Encyclopedia of Integer Sequences,
A007323. http://www.research.att.com/∼njas/sequences/A007323.
[66] Henning Stichtenoth. A note on Hermitian codes over GF(q 2 ). IEEE Trans.
Inform. Theory, 34(5, part 2):1345–1348, 1988. Coding techniques and coding theory.
[67] Henning Stichtenoth. Algebraic function fields and codes. Universitext.
Springer-Verlag, Berlin, 1993.
[68] Karl-Otto Stöhr and José Felipe Voloch. Weierstrass points and curves
over finite fields. Proc. London Math. Soc. (3), 52(1):1–19, 1986.
47

[69] James J. Sylvester. Mathematical questions with their solutions. Educational Times, 41:21, 1884.
[70] Fernando
Torres.
Notes
on
Goppa
codes.
www.ime.unicamp.br/˜ftorres/RESEARCH/ARTS PDF/codes.pdf.
[71] Fernando Torres. On certain N -sheeted coverings of curves and numerical
semigroups which cannot be realized as Weierstrass semigroups. Comm.
Algebra, 23(11):4211–4228, 1995.
[72] Jacobus H. van Lint and Gerard van der Geer. Introduction to coding theory
and algebraic geometry, volume 12 of DMV Seminar. Birkhäuser Verlag,
Basel, 1988.
[73] Herbert S. Wilf. A circle-of-lights algorithm for the “money-changing
problem”. Amer. Math. Monthly, 85(7):562–565, 1978.
[74] Yufei Zhao. Constructing numerical semigroups of a given genus. Semigroup Forum, 80(2):242–254, 2010.

48

