Bounding the number of points on a curve using

a generalization of Weierstrass semigroups∗

arXiv:1202.0453v1 [math.AG] 2 Feb 2012

Peter Beelen† Diego Ruano‡

November 15, 2018

Abstract
In this article we use techniques from coding theory to derive upper
bounds for the number of rational places of the function field of an alge-
braic curve defined over a finite field. The used techniques yield upper
bounds if the (generalized) Weierstrass semigroup [3] for an n-tuple of
places is known, even if the exact defining equation of the curve is not
known. As shown in examples, this sometimes enables one to get an up-
per bound for the number of rational places for families of function fields.
Our results extend results in [5].

1 Introduction
Let Fq be the finite field with q elements and F /Fq be a function field [9]
of an algebraic curve C defined over Fq . We denote by N (F ) the number of
rational places of F and by g(F ) its genus. Even when the defining equation
of C is known explicitly, it can be useful to have a priori upper bounds for
N (F ). If only partial information is available about the curve C, it is often
still possible to give an upper bound on the number of rational places of F .
One such upper bound is the well-known Hasse–Weil upper bound, stating that
√
N (F ) ≤ q + 1 + 2g(F ) q. To use this upper bound, one only needs to know
(an upper bound for) the genus of F . In [5, Theorem 1] another type of an a
priori upper bound is given, which assumes the knowledge of the Weierstrass
semigroup H(P1 ) of a rational place P1 of F :

N (F ) ≤ # (H(P1 ) \ (qH ∗ (P1 ) + H(P1 ))) + 1,

∗ This work was supported in part by the Danish FNU grant 272-07-0266, the Dan-

ish National Research Foundation and the National Science Foundation of China (Grant
No.11061130539) for the Danish-Chinese Center for Applications of Algebraic Geometry in
Coding Theory and Cryptography and by Spanish grant MTM2007-64704.
† DTU-Mathematics, Technical University of Denmark, Matematiktorvet, Building 303,

2800 Kgs. Lyngby, Denmark P.Beelen@mat.dtu.dk

‡ Department of Mathematical Sciences, Aalborg University, Fr. Bajersvej 7G, 9220 Aal-

borg Øst, Denmark. diego@math.aau.dk

1
where qH ∗ (P1 )+H(P1 ) = {qλ+λ′ | λ, λ′ ∈ H(P1 ), λ 6= 0}. One may rightly ask
how often the situation arises in which one does not know the exact equation
of C, but one does know a Weierstrass semigroup. However, we will show in
examples that having only some information on the defining equation sometimes
is enough to compute the bound in [5] as well as our generalized bounds (see
Example 11). In order to extend the Geil–Matsumoto bound, we will in Section
2 consider the Weierstrass semigroup defined by several rational places [3]. In
section 3, we estimate the size of certain subsets of the set of rational places.
This second estimation can lead to a sharper estimate of the total number of
rational places. As done in [5], one may change viewpoint and use the bounds
obtained in this article to obtain information about the kind of (generalized)
semigroups that may occur when one assumes that the function field has many
rational places. This is also the point of view taken in Example 11, where it is
shown that a certain family of function fields of genus 6 cannot improve upon
known records from [10].
The main techniques to prove our results come from coding theory. More
precisely, we consider AG-codes constructed by evaluating functions from a
Riemann-Roch space L(G) (for suitable divisors G) in rational places of F . The
length of the resulting code is given by the number of rational places used in
this construction. Usually, the rational places are fixed and one is interested
in determining the minimum distance of the code. In this article, modifying
an idea from [5], we estimate the dimension of the code. Since the dimension
of a code cannot exceed its length, this gives information about the number of
rational places the function field F can have.

2 A generalization of the Geil–Matsumoto bound

In this section we will present a first generalization of the Geil–Matsumoto
bound [5]. Let P1 , . . . , Pn be n rational places of a given function field F
and denote by Q the set of N (F ) − n remaining rational places. Note though
that in the next section, Q will in general denote a subset of these PnN (F ) − n
places. For an n-tuple i = (i1 , . . . , in ) ∈ Zn we write deg(i) = j=1 ij and
Pn
L(i) = L( j=1 ij Pj ). Further we will denote with ej the n-tuple all of whose
coordinates are 0, except the j-th one, which is assumed to be 1. Then one has
for example that L(λej ) = L(λPj ).
Definition 1 Given i ∈ Zn , we define
Hi (Pj ) = {−vPj (f ) | f ∈ ∪k∈Z L(i + kej )\{0}}
Remark 2 1. We have H0 (Pj ) = H(Pj ), where 0 denotes the n-tuple con-
sisting of zeroes only.
2. Note that the set Hi (Pj ) does not depend on the j-th coordinate of i.
3. We remark that L(i + kej ) = {0}, for k < − deg(i), so it also holds that
Hi (Pj ) = {−vPj (f ) | f ∈ ∪k≥− deg(i) L(i + kej )\{0}}.

2
 4. Sets such as Hi (Pj ) were also mentioned in [2], where they were used
to compute lower bounds on the minimum distances of certain algebraic
geometry codes. In [2] it is also explained how to compute these sets. They
are closely related to the generalized Weierstrass semigroups introduced in
[3].

With this notation in place, we define the following functions:

Definition 3 Let i ∈ Zn and let j be an integer between 1 and n. If L(i) = L(i+

ej ) or if there exists λ ∈ H(Pj )\{0} and µ ∈ Hi (Pj ) such that µ + qλ = ij + 1,
we call the pair (i, i + ej ) negligible. Further we define

0 if the pair (i, i + ej ) is negligible,
δ(i, i + ej ) =
1 otherwise.

Lemma 4 Let (i, i + ej ) be a negligible pair such that L(i) ( L(i + ej ), and
write µ + qλ = ij + 1 for λ ∈ H(Pj )\{0} and µ ∈ Hi (Pj ). Then there exist
f ∈ L(λej ) and g ∈ L(i) such that f q g ∈ L(i + ej )\L(i).

Proof. Since λ ∈ H(Pj ), there exists a function f ∈ L(ej ) whose pole divisor
equals
Pn (f )∞ = λPj . Similarly there exists a function g ∈qL(i) such that (g) ≥
− k=0 ik Pk and −vPk (g) = µ. P This implies that −vPj (f g) = qλ + µ = ij + 1
and also that (f q g) ≥ −Pj − nk=0 ik Pk . Together these imply that f q g ∈
L(i + ej )\L(i) as desired. 
A pair (i, i + ej ) is negligible if deg(i) is large enough. More precisely, one
has:

Proposition 5 Let i ∈ Zn and let j be an integer between 1 and n and assume

that deg(i) ≥ (q + 2)(g(F ) + 1) − 3. Then the pair (i, i + ej ) is negligible.

Proof. Suppose that deg(i) ≥ (q + 2)(g(F ) + 1) − 3. Since this implies in

particular that deg(i) ≥ 2g(F ) − 1, the theorem of Riemann–Roch implies that
L(i) ( L(i + ej ). Since the semigroup H(Pj ) = {0, λ, . . . } has exactly g(F )
gaps, there exists an integer λ ∈ H(Pj )\{0} with λ ≤ g(F ) + 1. Therefore
deg(i + (1 − qλ)ej ) ≥ 2g(F ), so applying the theorem of Riemann–Roch again,
we see that there exists a function g ∈ L(i + (1 − qλ)ej ) such that −vPj (g) =
ij + 1 − qλ. By Definition 1, we see that ij + 1 − qλ ∈ Hi (Pj ). By Definition 3
the proposition now follows, since (ij + 1 − qλ) + qλ = ij + 1. 
Actually we showed the following more precise result:

Corollary 6 Let λj denote the smallest nonzero element of H(Pj ). Then the
pair (i, i + ej ) is negligible if deg(i) ≥ qλj + 2g(F ) − 1.

Now we come to the main theorem.

Theorem 7 Define M = (q + 2)(g(F ) + 1) − 3 and let i(−1) , . . . , i(M) be a

sequence of n-tuples such that:
1. deg(i(−1) ) = −1,

3
 2. for any k there exists a j such that i(k) − i(k−1) = ej .
PM
Then N (F ) ≤ n + k=0 δ(i(k−1) , i(k) ).

Proof. Note that by the properties of the divisor sequence, we have deg(i(k) ) =
k for any −1 ≤ k ≤ M . For any divisor G with support disjoint from Q, we
introduce the following notation:
N (F )−n
EvQ : L(G) → Fq

f 7→ (f (Q))Q∈Q

and CQ (G) = EvQ (L(G)). For an n-tuple i, we define

CQ (i) = EvQ (L(i)).

We will begin the proof of the theorem by showing the following three claims:
1. For any divisor G of degree deg(G) ≥ N (F ) − n + 2g(F ) − 1, it holds that
N (F )−n
CQ (G) = Fq .
2. For any k ≥ 0 we have dim(CQ (i(k) )) ≤ dim(CQ (i(k−1) )) + δ(i(k−1) , i(k) ).
3. dim(CQ (i(−1) )) = 0.
The first claim follows from a standard argument: the kernel of the eval-
N (F )−n P
uation map EvQ : L(G) → Fq PL(G − Q∈Q Q). Therefore
is given by
we get dim(CQ (G)) = dim(L(G)) − dim(L(G − Q∈Q Q)). Using the assump-
tion deg(G) ≥ N (F ) − n + 2g(F ) − 1 and the theorem of Riemann–Roch, this
expression simplifies to N (F ) − n.
The second claim is trivial if δ(i(k−1) , i(k) ) = 1, so we may assume that
(k−1) (k)
δ(i , i ) = 0. Since by assumption there exists j such that i(k) = i(k−1) +ej ,
we may apply Lemma 4 to conclude that there exist f ∈ L(λej ) for some λ > 0
and g ∈ L(i(k−1) ) such that f q g ∈ L(i(k) )\L(i(k−1) ). On the level of codes this
means that the code CQ (i(k) ) is generated as a vector space by the vectors of
CQ (i(k−1) ) and the vector EvQ (f q g). However, since the codes are defined over
Fq , we have EvQ (f q g) = EvQ (f g). On the other hand, since λ > 0, we see that
f g ∈ L(i(k−1) ) and therefore that EvQ (f g) ∈ CQ (i(k−1) ). The second claim
now follows.
The third claim is clear, since L(G) = {0} for any divisor of negative degree.

From the last two parts of the claim we find inductively that
M
X
dim(CQ (i(M) )) ≤ δ(i(k−1) , i(k) ).
k=0

On the other hand, combining a similar reasoning and Proposition 5, we find

that
dim(CQ (i(M) )) = dim(CQ (i(M) + lej ))

4
for any j and any natural number l. From this and the first claim we can
conclude that
dim(CQ (i(M) )) = N (F ) − n.
The theorem now follows. 
The above proof is inspired by the proof of the Geil–Matsumoto bound [5]. If
n = 1, the above theorem reduces to their result: If n = 1, the only choice for the
sequence i(−1) , . . . , i(M) is −1, 0, . . . , M . For n > 1, there are more possibilities.
In fact, we obtain a weighted oriented graph given by the lattice with vertices
{−1, . . . , M }n and edges (i, i + ej ), with weights w(i, i + ej ) = δ(i, i + ej ),
for i ∈ {−1, . . . , M }n and j = 1, . . . , n such that ij 6= M . In practice, we
consider the bound from Corollary 6 instead of the bound M in Theorem 7. We
do not need to consider the whole lattice, but can start with a one-dimensional
lattice and increase its size progressively. Then we just find an optimal sequence
i(−1) , . . . , i(M) , by finding a path from a vertex with degree −1 to a vertex with
degree M with minimum weight (using Dijkstra’s algorithm [4], which computes
a path with lowest weight between a particular vertex of a graph and every other
vertex of that graph).

Example 8 In this example we consider the function field of the Klein quartic
over F8 which has genus three. It can be described as F1 /F8 = F8 (x, y)/F8 ,
where x3 y + y 3 + x = 0. Of course it is well-known how many rational places
this function field has (namely 24) and it should be noted that the only purpose
of this example is to illustrate the theory.
There are three rational places occurring as poles and/or zeroes of the func-
tions x and y. We will denote these by P1 , P2 and P3 . More precisely we choose
them such that the following identities of divisors hold:

(x) = 3P1 − P2 − 2P3 and (y) = P1 + 2P2 − 3P3 .

From this, one can show that H = H(P1 ) = H(P2 ) = H(P3 ) = h3, 5, 7i and

L(i1 P1 + i2 P2 + i3 P3 ) = hxα y β | 3α + β ≥ −i1 , −α + 2β ≥ −i2 , −2α − 3β ≥ −i3 i.

(1)
Actually, one can prove that all rational places of the Klein quartic have the same
Weierstrass semigroup. The Geil–Matsumoto bound gives N (F1 ) ≤ 1 + 24 = 25
in this case, since H \ (8H ∗ + H) = {0, 3, 5, 6, . . . , 23, 25, 26, 28}.
We now compute the bound from Theorem 7, where we will consider n = 2,
and P1 , P2 as above. It is enough to consider a sequence of n-tuples (i(−1) , . . . , i(29) ),
since (i, i + ej ) is negligible if deg(i) ≥ 8 · 3 + 2 · 3 − 1 = 29 (Corollary 6). As
before we represent the divisor P1 , resp. P2 by e1 , resp. e2 and write
(k) (k) (k) (k)
ik = (i1 , i2 ) = i1 e1 + i2 e2 .

We computed a oriented graph as above, given by the {−1, . . . 29} × {0, . . . 4}

lattice, with weights given by δ(i, i + ej ) and got a path with minimum weight
given by

5
  (k)
 i = (k, 0), for k = −1, . . . , 23,
i(23+k) = (24, k − 1), for k = 1, . . . , 3,
 (26+k)
i = (25, k + 1), for k = 1, . . . , 3.
Then {k ≥ 0 | δ(i(k−1) , i(k) ) = 1} = {0, 3, 5, 6, . . . , 23, 25}, which implies that
N (F ) ≤ 2 + 22 = 24.
The Geil–Matsumoto bound is an improvement to the gonality bound, some-
times called Lewittes’ bound [7],
N (F ) ≤ qλ1 + 1,
where λ1 denotes the smallest non-zero element of H. In the above example
these bounds give rise to the same upper bound for N (F ). The following propo-
sition explains this phenomenon. We introduce the Apéry set of a numerical
semigroup [1, 8], which is the main tool for this result. For e ∈ H, the Apéry
set of H relative to e is defined to be Ap(H, e) = {λ ∈ H|λ − e ∈ / H}. One has
that Ap(H, e) is {w0 = 0, w1 , . . . , we−1 }, where wi is the smallest element of H
congruent with i modulo e, for i = 0, . . . , e − 1. Moreover, for λ ∈ H there exist
a unique i and k, with i ∈ {0, . . . , e − 1} and k ∈ N0 , such that λ = wi + ke.
Thus we have the disjoint union
e−1
[
H= {wi + eN0 },
i=0

in particular {e, w1 , . . . , we−1 } generates H.

Proposition 9 Let e ∈ H and λ1 the smallest non-zero element of H, then
#(H \ (eH ∗ + H)) = eλ1 .
In particular the bounds in [5, 7] give the same result if q ∈ H.
Proof. Let Ap(H, e) = {w0 = 0, w1 , . . . , we−1 } be the Apéry set of H
relative to e ∈ H. For any λ ∈ H we have
e−1
[ e−1
[
eλ + H = (eλ + wi + eN0 ) = (wi + eN≥λ ),
i=0 i=0

where N≥λ denotes the set of natural numbers greater than or equal to λ. This
implies that for λ < µ ∈ H we have eλ + H ⊃ eµ + H and thus
eH ∗ + H = eλ1 + H,
with λ1 the smallest element of H ∗ . The proposition now follows, since the
equality #(H \ (eλ1 + H)) = eλ1 is a well-known result for semigroups, see [6,
Chapter 10, Lemma 5.15]. 
The Weierstrass semigroup of Example 8 contains q = 8, the number of
elements of the base field. Therefore, both bounds in [5, 7] give the same result.
Namely, we have e = q = 8 and w0 = 0, w1 = 9, w2 = 10, w3 = 3, w4 = 12,
w5 = 5, w6 = 6, and w7 = 7.

6
Remark 10 The converse statement, namely that (in the notation of Proposi-
tion 9) #(H \ (eH ∗ + H)) = eλ1 implies that e ∈ H, is not necessarily true.
Consider for example the semigroup {0, 2, 4, 5, 6, . . . } generated by 2 and 5 and
suppose that e = 3.
On the other hand, for semigroups H generated by m and m + 1, with m a
natural number, this converse does hold: Suppose that #(H \ (eH ∗ + H)) = em,
then e(m + 1) ∈ em + H (by [6, Chapter 10, Lemma 5.15]), which would imply
that e = e(m + 1) − em ∈ H.
We conclude this section with an example that shows that the above tech-
niques also can be used when only partial information is given about the defining
equation of the function field.
Example 11 In this example we consider the function field F2 /F8 = F8 (x, y)/F8 ,
where x and y are related by an equation of the form
X
αy 4 + βy + x5 + ai,j xi y j = 0, (2)
(i,j)∈∆

where α and β are nonzero elements in F8 and ai,j are arbitrary elements in
F8 . Moreover ∆ = {(i, j) ∈ Z2 | 4i + 5j < 20, i ≥ 0, 5j + i > 5}. Another way
of stating the structure of the defining equation is that its Newton polygon is a
triangle with vertices (0, 0), (5, 0) and (0, 4). We will assume that the genus of
F2 equals 6, which amounts to saying if we interpret Equation (2) as a defining
equation of a curve, then this curve does not have any singularities.
Like for the Klein quartic in the previous example, we can derive information
about the divisors for x and y from the defining equation. In fact, denoting by
P1 the common zero of x and y and by P2 the unique pole of x (and y), we have
(x) ≥ P1 − 4P2 and (y) = 5(P1 − P2 ).
Using the assumption that g(F2 ) = 6, one can show that this implies
L(i1 P1 + i2 P2 ) = hxα y β | α + 5β ≥ −i1 , −4α − 5β ≥ −i2 , i1 ≥ 0i. (3)
In particular, we see that the semigroup of P2 (and in fact also P1 ) is generated
by 4 and 5. Since 8 ∈ H(P1 ), we see that the bound from [5] gives 33 for this
example. Any function field of genus 6 defined over F8 can have at most 34
points (i.e. N8 (6) ≤ 34), while it is also known that N8 (6) ≥ 33 [10]. Based on
this, one may hope that for a clever choice of the coefficients α, β and the ai,j
one can find a function field defined by an equation of the form as in (2) with
33 rational places. However, it turns out that using Theorem 7 with
 (k)
 i = (k, 0), for k = −1, . . . , 34,
 (34+k)

i = (34, k), for k = 1, . . . , 3,
(37+k)

 i = (34 + k, 3), for k = 1, . . . , 3,
 (40+k)
i = (37, 3 + k), for k = 1, . . . , 3.
that N (F2 ) ≤ 2 + 29 = 31. Note that we do not have to describe more values of
i(k) by Corollary 6.

7
3 A second generalization of the Geil–Matsumoto
bound
In this section we will generalize the previous results by estimating the size of
certain subsets of the set of rational places. Contrary to the previous section,
we will therefore in this section by Q denote some subset of the set of all ra-
tional places not containing any of the places P1 , . . . , Pn . The results from the
previous section can be refined in this setup. Further we define T = Fq \{0} for
convenience.

Definition 12 Let i ∈ Zn and let j be an integer between 1 and n. We call the

pair (i, i + ej ) T -negligible if either L(i) = L(i + ej ) or if

1. there exists λ ∈ H(Pj )\{0} and µ ∈ Hi (Pj ) such that µ + (q − 1)λ = ij + 1

and
2. for this λ there exists f ∈ L(λPj )\L((λ − 1)Pj ) such that f (Q) ∈ T for
all Q ∈ Q.

Further we define

0 if the pair (i, i + ej ) is T -negligible,
δT (i, i + ej ) =
1 otherwise.

Note that depending on the choice of Q, the function δT may change. Strictly
speaking we should therefore include Q in the notation for this function, but
for the sake of simplicity, we will not do this.

Lemma 13 Let (i, i + ej ) be a T -negligible pair such that L(i) ( L(i + ej ) and
write µ + (q − 1)λ = ij + 1 for λ ∈ H(Pj )\{0} and µ ∈ Hi (Pj ). Then there
exist f ∈ L(λej ) and g ∈ L(i) such that f q−1 g ∈ L(i + ej )\L(i) and such that
moreover f (Q) ∈ T for all Q ∈ Q.

Proof. Since λ ∈ H(Pj ), there exists a function f ∈ L(ej ) whose pole divisor
equals (f )∞ = λPj . By Definition 12 we can choose a function f such that
f (Q) ∈ T forPall Q ∈ Q. Similarly there exists a function g ∈ L(i) such
that (g) ≥ − nk=0 ik Pk and −vPj (g) = µ. This implies P that −vPj (f q−1 g) =
q−1 n
(q − 1)λ+ µ = ij + 1 and also that (f g) ≥ −(q − 1)λPj − j=0 ij Pj . Together
q−1
these imply that f g ∈ L(i + ej )\L(i) as desired. 
A pair (i, i + ej ) is negligible if deg(i) is large enough. More precisely, one
has:

Proposition 14 Let i ∈ Zn and let j be an integer between 1 and n. Define

Λ = #Q + 2g(F ) and MT = (q − 1)Λ + 2g(F ) − 1. Then any pair (i, i + ej )
satisfying deg(i) ≥ MT is T -negligible.

8
Proof. Suppose that deg(i) ≥ MT . Since then in particular deg(i) ≥ 2g(F ) − 1,
it follows from the theorem of Riemann–Roch that L(i) ( L(i + ej ). Also note
that deg(i+(1−(q−1)Λ)ej ) ≥ 2g(F ), so applying the theorem of Riemann–Roch
again, we see that there exists a function g ∈ L(i + (1 − (q − 1)Λ)ej ) such that
−vPj (g) = ij +1−(q−1)Λ. By Definition 1, we see that ij +1−(q−1)Λ ∈ Hi (Pj ).
Since the largest gap of the semigroup H(Pj ) is at most 2g(F ) − 1, the
number Λ is not a gap of H(Pj ). This means that there exists a function
f ∈ L(ΛPj ) such that −vPj (f ) = Λ. We cannot conclude yet from Definition
12 that the pair (i, i + ej ) is T -negligible, since f could have a zero among the
places in Q. However, from the proof of Theorem 7 and the definition of Λ we
see that for any j the evaluation map EvQ : L((Λ − 1)Pj ) → F#Q q is surjective.
Therefore, we can always choose f ∈ L(ΛPj )\L((Λ − 1)Pj ) such that f (Q) ∈ T
for all Q ∈ Q. 
The MT given in this proposition can be very large. Under some additional
conditions, we can obtain better results.

Proposition 15 Let i ∈ Zn and let j be an integer between 1 and n. Suppose

that for any λ ∈ H(Pj ) there exists f ∈ L(λPj )\L((λ−1)Pj ) such that f (Q) ∈ T
for all Q ∈ Q. If deg(i) ≥ (q + 1)(g(F ) + 1) − 3, then the pair (i, i + ej ) is
T -negligible.

Proof. Suppose that deg(i) ≥ (q + 1)(g(F ) + 1) − 3. Since then deg(i) ≥

2g(F ) − 1, it follows from the theorem of Riemann–Roch that L(i) ( L(i + ej ).
As in the proof of Proposition 5 we can conclude that there exists λ ∈ H(Pj )\{0}
with λ ≤ g(F ) + 1. This implies that deg(i + (1 − (q − 1)λ)ej ) ≥ 2g(F ), so
applying the theorem of Riemann–Roch again, we see that there exists a function
g ∈ L(i + (1 − (q − 1)λ)ej ) such that −vPj (g) = ij + 1 − (q − 1)λ. By Definition
1, we see that ij + 1 − (q − 1)λ ∈ Hi (Pj ). Furthermore by assumption, there
exists f ∈ L(λPj )\L((λ − 1)Pj ) such that f (Q) ∈ T for all Q ∈ Q. Therefore,
by Definition 12, the proposition follows. 
As in the previous section, we can refine the above statement:

Corollary 16 Let λj denote the smallest nonzero element of H(Pj ). Suppose

that for any λ ∈ H(Pj ) there exists f ∈ L(λPj )\L((λ−1)Pj ) such that f (Q) ∈ T
for all Q ∈ Q. Then the pair (i, i + ej ) is T -negligible if deg(i) ≥ (q − 1)λj +
2g(F ) − 1.

Now we come to the refinement of Theorem 7.

Theorem 17 Define Λ = #Q + 2g(F ) and MT = (q − 1)Λ + 2g(F ) − 1. Let

i(−1) , . . . , i(MT ) be a sequence of n-tuples such that:
1. deg(i(−1) ) = −1,
2. for any k there exists a j such that i(k) − i(k−1) = ej .
PMT
Then #Q ≤ k=0 δT (i(k−1) , i(k) ).

9
Proof. The proof is similar to that of Theorem 7. All the reasoning is similar
apart from the proof of the following claim:

For any k ≥ 0 we have dim(CQ (i(k) )) ≤ dim(CQ (i(k−1) )) + δT (i(k−1) , i(k) ).

This is clear if δT (i(k−1) , i(k) ) = 1, so we may assume that δT (i(k−1) , i(k) ) = 0.

We may apply Lemma 13 to conclude that there exist f ∈ L(λej ) for some
λ > 0 and g ∈ L(i(k−1) ) such that f q−1 g ∈ L(i(k) )\L(i(k−1) ). Moreover, we may
assume that f (Q) ∈ T for all Q ∈ Q. Since αq−1 = 1 for all α ∈ T , this implies
f (Q)q−1 = 1 for all Q ∈ Q. On the level of codes we have, as in Theorem 7, that
the code CQ (i(k) ) is generated as a vector space by the vectors of CQ (i(k−1) ) and
the vector EvQ (f q−1 g). However, we have EvQ (f q−1 g) = EvQ (g) ∈ CQ (i(k−1) ).
The claim now follows and the proof of the theorem can be concluded as that
of Theorem 7. 
In case n = 1 and the hypotheses from Proposition 15 are satisfied, we obtain
the following result:

Corollary 18 Suppose that for any λ ∈ H(P1 ) there exists f ∈ L(λP1 )\L((λ −
1)P1 ) such that f (Q) ∈ T for all Q ∈ Q. Then

#Q ≤ #H(P1 )\((q − 1)H ∗ (P1 ) + H(P1 )).

Proof. Since n = 1, the only sequence we can choose is −1, 0, 1, 2, . . . . However,

under the stated assumptions, a pair (k − 1, k) is T -negligible if and only if
k ∈ (q − 1)H ∗ (P1 ) + H(P1 ). 
We will now give some examples.

Example 19 This example is a continuation of Example 8. In particular we

will use the same notation as in that example. We choose P = P1 and Q to be
the set of all rational places Q satisfying x(Q) ∈ T and y(Q) ∈ T . Using the
divisors for x and y in Example 8, we see that the only rational places not in Q
are P1 , P2 and P3 .
Using Equation (1), we see that the conditions in Corollary 18 are satisfied
for our choice of Q. Therefore we find that

#Q ≤ #H(P1 )\(7H ∗ (P1 ) + H(P1 )) = #{0, 3, 5, . . . , 20, 22, 23, 25} = 21.

Also counting the rational points P1 , P2 and P3 we find that N (F1 ) ≤ 24. Since
N (F1 ) = 24, Corollary 18 gives a tight bound in this case.

Example 20 This example is a continuation of Example 11. There we have

seen that N (F2 ) ≤ 31. This can also been seen using Corollary 18. From
Equation (2), we see that there are at most 4 rational places P of F2 with
x(P ) = 0 or y(P ) = 0 and a unique pole of x and y. On the other hand
applying Corollary 18 to the semigroup H(P2 ) = h4, 5i, we get that #Q ≤ 26.
Therefore N (F2 ) ≤ 4 + 1 + 26 = 31.

10
References
[1] Roger Apéry. Sur les branches superlinéaires des courbes algébriques. C.
R. Acad. Sci. Paris, 222:1198–1200, 1946.
[2] Peter Beelen. The order bound for general algebraic geometric codes. Finite
Fields Appl., 13(3):665–680, 2007.
[3] Peter Beelen and Nesrin Tutaş. A generalization of the Weierstrass semi-
group. J. Pure Appl. Algebra, 207(2):243–260, 2006.
[4] E. W. Dijkstra. A note on two problems in connexion with graphs. Numer.
Math., 1:269–271, 1959.
[5] 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.
[6] Tom Høholdt, Jacobus H. van Lint, and Ruud Pellikaan. Algebraic ge-
ometry of codes. In Handbook of coding theory, Vol. I, II, pages 871–961.
North-Holland, Amsterdam, 1998.
[7] Joseph Lewittes. Places of degree one in function fields over finite fields.
J. Pure Appl. Algebra, 69(2):177–183, 1990.
[8] J. C. Rosales and P. A. Garcı́a-Sánchez. Numerical semigroups, volume 20
of Developments in Mathematics. Springer, New York, 2009.
[9] Henning Stichtenoth. Algebraic function fields and codes. Universitext.
Springer-Verlag, Berlin, 1993.
[10] Gerard van der Geer, Everett Howe, Kristin Lauter, and Christophe Ritzen-
thaler. manYPoints – Table of Curves with Many Points. Online available
at http://www.manypoints.org, 2011.

11