Algebraic Geometric codes on Hirzebruch
surfaces

arXiv:1801.08407v1 [cs.IT] 25 Jan 2018

Jade Nardi

∗

January 26, 2018

Abstract
We define a linear code Cη (δT , δX ) by evaluating polynomials of bidegree (δT , δX ) in the Cox ring on Fq -rational points of the Hirzebruch
surface on the finite field Fq . We give explicit parameters of the code,
notably using Gröbner bases. The minimum distance provides an upper bound of the number of Fq -rational points of a non-filling curve on a
Hirzebruch surface. We also display some punctured codes having optimal
parameters.

AMS classification : 94B27, 14G50, 13P25, 14G15, 14M25
Keywords: Hirzebruch surface, Algebraic Geometric code, Gröbner basis, Rational scroll

Introduction
Until the 00’s, most Goppa codes were associated to curves. In 2001 S.H. Hansen
[8] estimated parameters of Goppa codes associated to normal projective varieties of dimension at least 2. As Hansen required very few assumptions on the
varieties, the parameters he gave depended only on the Seshadri constant of the
line bundle, which is hard to compute in practice. New classes of error correcting codes have thus been constructed, focusing on specific well-known families
of varieties to better grasp the parameters. Among Goppa codes associated to
a surface which have been studied until now, some toric and projectives codes
are based on Hirzebruch surfaces.
Toric codes, first introduced by J. P. Hansen [7] and further investigated by
D. Joyner [9] and D. Ruano [12], are Goppa codes on toric varieties evaluating
global sections of a line bundle at the Fq -rational points of the torus.
Projective codes evaluate homogeneous polynomials on the rational points
of a variety embedded in a projective space. A first example of projective codes
is Reed-Muller projective codes on P2 [10]. A. Couvreur and I. Duursma [2]
studied codes on the biprojective space P1 × P1 embedded in P3 . The authors
took advantage of the product structure of the variety, yielding a description
of the code as a tensor product of two well understood Reed-Muller codes on
∗

Institut de Mathématiques de Toulouse ; UMR 5219, Université de Toulouse ; CNRS UPS
IMT, F-31062 Toulouse Cedex 9, France jade.nardi@math.univ-toulouse.fr. Funded by ANR
grant ANR-15-CE39-0013-01 "manta"

1

P1 . C. More recently Carvalho and V. G.L. Neumann [1] examined the case of
rational surface scrolls S(a1 , a2 ) as subvarieties of Pa1 +a2 +1 , which extends the
result on P1 × P1 , isomorphic to S(1, 1).
In this paper we establish the parameters of Goppa codes corresponding to
complete linear systems on Hirzebruch surfaces Hη , a family of projective toric
surfaces. This framework expands preceding works while taking advantage of
toric and projective points of view.
Regarding toric codes, we extend the evaluation map on the whole toric
variety. This is analogous to the extension of affine Reed-Muller codes by projective ones introduced by G. Lachaud [10], in the sense that we also evaluate
at "points at infinity". In other words toric codes on Hirzebruch surfaces can
be obtained by puncturing the codes studied here at the 4q points lying on
the 4 torus-invariant divisors, that have at least one zero coordinates. As in
the Reed-Muller case, the growth of minimum distance through the extension
process appears to be about the half of that of the length, as proved in Section
6.
Respecting the projective codes cited above, it turns out that the rational
surface scrolls are the range of some projective embedding of a Hirzeburch surface, H0 for P1 × P1 and Ha1 −a2 for S(a1 , a2 ). However no embedding of the
Hirzebruch surface into a projective space is required for our study and the Cox
ring replaces the usual Fq [X0 , . . . , Xr ] used in the projective context. Moreover,
the embedded point of view forces to only evaluate polynomials of the Cox ring
that are pullbacks of homogeneous polynomials of Fq [X0 , X1 , . . . , Xr ] under this
embedding. No such constraint appears using the Cox ring and polynomials of
any bidegree can be examined.
Whereas coding theorists consider evaluation codes which evaluation map
is injective, C. Carvalho and V. G.L. Neumann (loc. cit.) extensively studied
codes associated to a non necessarily injective evaluation map. In the present
work no assumption of injectivity is needed. The computation of the dimension
of the code does not follow from Riemann-Roch theorem. This grants us a wider
range of possible values of the size of the alphabet for a given degree, including
the small ones.
The linear code Cη (δT , δX ) is defined as the evaluation code on Fq -rational
points of Hη of the set R(δT , δX ) of homogeneous polynomials of bidegree
(δT , δX ), defined in Section 1. The evaluation is naively not well-defined for
a polynomial but a meaningful definition à la Lachaud [10] is given in Paragraph 1.2.
Here the parameters of the code Cη (δT , δX ) are displayed as combinatoric
quantities from which quite intricate but explicit formulae can be deduced in
Propositions 2.4.1 and 4.2.3. The rephrasing of the problem in combinatorial
terms is already a key feature in Hansen’s [7] and Carvalho and Neumann’s
works [1] that is readjusted here to fit a wider range of codes.
A natural way to handle the dimension of these codes is to calculate the
number of classes under the equivalence relation ≡ on the set R(δT , δX ) that
identifies two polynomials if they have the same evaluation on every Fq -rational
point of the Hirzebruch surface. Our strategy is to first restrict the equivalence
relation ≡ on the set of monomials M(δT , δX ) of R(δT , δX ) and a handy characterization for two monomials to be equivalent is given. We then prove that
2

comprehending the equivalence relation over monomials is enough to compute
the dimension.
Theorem A. The dimension of the code Cη (δT , δX ) satisfies
dim Cη (δT , δX ) = #∆(δT , δX ),

where ∆(δT , δX ) is a set of representatives of M(δT , δX ) under the equivalence
relation ≡. It only depends on the parameter η, the bidegree (δT , δX ) and the
size q of the finite field.
As for the dimension, the first step of the determination of the minimum distance is to bound it by below with a quantity that only depends on monomials.
Again the strategy is similar Carvalho and Neumann’s one [1] but, even though
they mentioned Gröbner bases, they did not fully benefit from the potential
of the tools provided by Gröbner bases theory. Indeed linear codes naturally
involve linear algebra but the problem can be considered from a commutative
algebra perspective. The definition of the evaluation on each homogeneous component extends naturally to the whole ring Fq [T1 , T2 , X1 , X2 ] so the ideal I of
polynomials vanishing at every Fq -rational point of the Hirzebruch surface is
well-defined. A good understanding of the Gröbner basis of I, through Section
3, shortens the proof of the following theorem.
Theorem B. Let us fix (ǫT , ǫX ) ∈ N2 such that ǫT , ǫX ≥ q. The minimum
distance dη (δT , δX ) satisfies
dη (δT , δX ) ≥

min

M∈∆(δT ,δX )

#∆(ǫT , ǫX )M

where ∆(ǫT , ǫX )M is defined in Notation 4.1.1. It is an equality unless δT < 0,
η divides δT and q ≤ ηδ . In this case, the lower bound is trivially zero.
It only depends on the parameter η, the bidegree (δT , δX ) and the size q of
the finite field.
The pullback of homogeneous polynomials of degree δX on S(a1 , a2 ) ⊂ Pr
studied by C. Carvalho and V. G.L. Neumann are polynomials of bidegree
(a2 δX , δX ) on Ha1 −a2 . The parameters established here match in this special
case, proving that the lower bound is reached. The parameters also coincide with
the one given by A. Couvreur and I. Duursma [2] in the case of the biprojective
space P1 × P1 , isomorphic to Hirzebruch surface H0 .
It is worth pointing out that the codes Cη (δT , δX ) with δT negative have
never been studied until now. The last section highlights an interesting feature
of these codes that leads to a good puncturing. It results codes of length q(q +1)
but with the same dimension and the same minimum distance.
We emphasize that the lower bound of the minimum distance in this paper
does not result from upper bound of the number of rational point of embedded curves but from purely algebraic and combinatoric considerations. This
approach, already highlighted by Couvreur and Duursma [2], stands out from
the general idea that one estimates the parameters of an evaluation code though
the knowledge of features of the variety X, like its cohomology groups for the
dimension or the number of rational points of subvarieties of X for the minimum distance. It also offers the great perspective of solving geometric problems
3

thanks to coding theory results. Moreover, the non injectivity of the evaluation
map means that there exists a filling curve, that is a curve that contains every
Fq -rational point of Hη . From a number theoretical point of view, the minimum distance offers an upper bound of the number of Fq -rational points of a
non filling curve, regardless its geometry and its smoothness, even if there exist
some filling curves.

1

Codes on Hirzebruch surfaces

1.1

Hirzebruch surfaces

We gather here some results about Hirzebruch surfaces over a field k, given in
[4] for instance.
Let η be a non negative integer. The Hirzebruch surface Hη can be considered from different points of view.

On one hand, the Hirzebruch surface Hη is the toric variety corresponding
to the fan Ση (see Figure 1).
(0, 1)
(−1, 0)
(−η, −1)

v1

u2
v2

(1, 0)

u1

Figure 1: Fan Ση
The fan Ση being a refining of the one of P1 , it yields a ruling Hη → P1 of
fiber F ≃ P1 and section σ. The torus-invariant divisors D1 , D2 , E1 and E2
corresponding to the rays spanned respectively by v1 , v2 , u1 , u2 generate the
Picard group of Hη , described in the following proposition.
Proposition 1.1.1. The Picard group of the Hirzebruch surface Hη is the free
Abelian group
Pic Hη = ZF + Zσ
where

F = E1 ∼ E2 and σ = D2 ∼ D1 + ηE1 .

(1)

We have the following intersection matrix.
F
σ

F
0
1

σ
1
η

As a simplicial toric variety, the surface Hη considered over k carries a Cox
ring R = k[T1 , T2 , X1 , X2 ]. Each monomial M = T1c1 T2c2 X1d1 X2d2 of R is associated to a torus-invariant divisor
DM = d1 D1 + d2 D2 + c1 E1 + c2 E2 .
4

(2)

The degree of the monomial M is defined as the Picard class of the divisor
DM . The couple of coordinates (δT , δX ) of DM in the basis (F , σ) is called the
bidegree of M and denoted by bideg(M ). By (1) and (2),
{
It is convenient to set

= c1 + c2 − ηd1 ,
= d1 + d2 .

δT
δX

(3)

δ = δT + ηδX .

2

This gives the Z -grading on R
R=

⊕

(δT ,δX )∈Z2

H 0 (Hη , OHη (δT F + δX σ)) =

⊕

(δT ,δX )∈Z2

R(δT , δX )

where R(δT , δX ) is the k-module of homogeneous polynomials of bidegree (δT , δX ) ∈
Z2 . Note that the Fq -module R(δT , δX ) is non zero if and only if δX ∈ N and
δ ∈ N.
On the other hand, using Theorem 5.1.11 [4], the Hirzebruch surface can
be displayed as a geometric quotient of an affine variety under the action of an
algebraic group. This description is given for instance by Reid [11]. Let us define
an action of the product of multiplicative groups Gm ×Gm over (A2 ∖ {(0, 0)})×
(A2 ∖ {(0, 0)}): write (t1 , t2 ) for the first coordinates on A2 , (x1 , x2 ) on the
second coordinates on A2 and (λ, µ) for elements of Gm × Gm . The action is
given as follows:
(λ, µ) ⋅ (t1 , t2 , x1 , x2 ) = (λt1 , λt2 , µλ−η x1 , µx2 ).

Then the Hirzebruch surface Hη is isomorphic to the geometric quotient
(A2 ∖ {(0, 0)}) × (A2 ∖ {(0, 0)}) /G2m .

This description enables us to describe a point of Hη by its homogeneous
coordinates (t1 , t2 , x1 , x2 ).

1.2

Evaluation map

We consider now the case k = Fq .

From the ruling Hη → P1 , the number of Fq rational points of the Hirzebruch
surface Hη is
N = #Hη (Fq ) = (q + 1)2 .

Let (δT , δX ) ∈ Z × N such that δ ≥ 0. Given a polynomial F ∈ R(δT , δX ) and
a point P of Hη , the evaluation of F at P is defined by F (P ) = F (t1 , t2 , x1 , x2 ),
where (t1 , t2 , x1 , x2 ) is the only tuple that belongs to the orbit of P under the
action of G2m and has one of these forms:
• (1, a, 1, b) with a, b ∈ Fq ,
• (0, 1, 1, b) with b ∈ Fq ,

• (1, a, 0, 1) with a ∈ Fq ,
5

• (0, 1, 0, 1).

The evaluation code Cη (δT , δX ) is defined as the image of the evaluation
map
R(δT , δX ) → FN
q
ev(δT ,δX ) ∶ {
(4)
F ↦ (F (P ))P ∈Hη(Fq ) .

Note that this code is Hamming equivalent to the Goppa code C(OHη (δT F +
δX σ), Hη (Fq )), as defined by Hansen [8]. The weight ω(c) of a codeword
c ∈ Cη (δT , δX ) is the number of non-zero coordinates. The minimum weight
among all the non-zero codewords is called the minimum distance of the code
Cη (δT , δX ) and is denoted by dη (δT , δX ).

Dimension of the evaluation code Cη (δT , δX ) on
the Hirzebruch surface Hη

2

Let us consider η ≥ 0 and (δT , δX ) ∈ Z × N such that δ = δT + ηδX ≥ 0.

Notation 2.0.1. The kernel of the map ev(δT ,δX ) is denoted by I(δT , δX ).
From the classical isomorphism
Cη (δT , δX ) ≃ R(δT , δX )Ò I(δ , δ ),
T X

the dimension of the evaluation code Cη (δT , δX ) equals to the dimension of
any complementary vector space of I(δT , δX ) in R(δT , δX ). This is tantamount to compute the range of a well-chosen projection map on R(δT , δX )
along ker ev(δT ,δX ) .

2.1

Focus on monomials

The aim of this section is to display such a projection map that will be denoted
by π(δT ,δX ) , such that in addition the image of a monomial is a monomial.
The existence of such a projection is not true in full generality: given a vector
subspace W of a vector space V and a basis B of V , it is not always possible to
find a basis of W composed of difference of elements of B and a complementary
space of W whose basis is a subset of B.
With this goal in mind, our strategy is to focus first on monomials of
R(δT , δX ). Let us define the following equivalence relation on the set of monomials of R(δT , δX ).

Definition 2.1.1. Let us define a binary relation ≡ on the set M(δT , δX ) of
monomials of R(δT , δX ). Let M1 , M2 ∈ M(δT , δX ). We note M1 ≡ M2 if they
have the same evaluation at every Fq -rational point of Hη , i.e.
M1 ≡ M2 ⇔ ev(δT ,δX ) (M1 ) = ev(δT ,δX ) (M2 ) ⇔ M1 − M2 ∈ I(δT , δX ).

The key point of this section is to prove that, even if this equivalence relation can be defined over all R(δT , δX ), the number of equivalence classes when
considering all polynomials is the same as when regarding only monomials. This
section thus goals to prove Theorem A, stated in the introduction.
6

2.2

Combinatorial point of view of the equivalence relation on monomials

Throughout this article, the set R(δT , δX ) are pictured as a lattice polygon is
N × N of coordinates (d2 , c2 ). This point of view, inherited directly from the
toric structure, was already used by J. P. Hansen [7]. It will be useful to handle
the computation of the dimension and the minimum distance as a combinatorial
problem.
Definition 2.2.1. Let (δT , δX ) ∈ Z × N. Let us define the lattice polygon
P(δT , δX ) = {(a, b) ∈ Z2 ∣ a ≥ 0, b ≥ 0, a ≤ δX and ηa + b ≤ δ}

associated to the divisor D = δE1 + δX D1 ∼ δT F + δX σ.

Being intersection of Z2 with half planes, it is easily seen that P(δT , δX ) is
the lattice polygon with vertices
• (0, 0), (δX , 0), (δX , δT ), (0, δ) if δT > 0,

• (0, 0), ( ηδ , 0), (0, δ) if δT < 0 and η > 0 or δT = 0.

Notation 2.2.2. Let us set

δ
A = A(η, δT , δX ) = min (δX , ) = {
η

δ
η

δX
= δX +

δT
η

if δT ≥ 0,
otherwise,

the x-coordinate of the right-most vertices of the polygon P(δT , δX ).

Let us highlight that A is not necessary an integer if δT < 0. Thus it does
not always appears as the first coordinate of an element of P(δT , δX ). It is the
case if and only if η ∣ δT and the only element of P(δT , δX ) such that A is its
first coordinate is (A, 0).
We thus observe that
P(δT , δX ) = {(a, b) ∈ N2 ∣ a ∈ ⟦0, ⌊A⌋⟧ and b ∈ ⟦0, δT + η(δX − a)⟧}

(5)

Example 2.2.3. Figure 2 gives the three examples of possible shapes of the polygon P(δT , δT ). The first one is the case η = 0, and the last two ones correspond
to η > 0 and depend on the sign of δT , which determines the shape of P(δT , δX ).
All proofs of explicit formulae in Propositions 2.4.1 and 4.2.3 distinguish these
cases.

Thanks to (3), a monomial of R(δT , δX ) is entirely determined by the couple
(d2 , c2 ). Then each integer point in the polynomial P(δT , δX ) corresponds to
a unique monomial. More accurately, for any couple (d2 , c2 ) ∈ P(δT , δX ), we
define the monomial
M (d2 , c2 ) = T1 T

δ +η(δx −d2 )−c2

T2c2 X1δX −d2 X2d2 ∈ M(δT , δX ).

(6)

Definition 2.2.4. The equivalence relation ≡ on M(δT , δX ) and the bijection
{

P(δT , δX ) → M(δT , δX )
(d2 , c2 ) ↦ M (d2 , c2 )

endow P(δT , δX ) with a equivalence relation, also denoted by ≡, such that
(d2 , c2 ) ≡ (d′2 , c′2 ) ⇔ M (d2 , c2 ) ≡ M (d′2 , c′2 ).
7

(7)

c2

c2
δ

c2
δ

δ = δT

A = δX d 2
(a) η = 0
e.g. P(7, 4)

A = δX

A < δX

d2

(b) η > 0, δT > 0
e.g. P(2, 3) in H2

d2

(c) η > 0, δT ≤ 0
e.g. P(−2, 5) in H2

Figure 2: Different shapes of the polygon P(δT , δX )
Proposition 2.2.5. Let two couples (d2 , c2 ) and (d′2 , c′2 ) be in P(δT , δX ) and
let us write
M = M (d2 , c2 ) = T1c1 T2c2 X1d1 X2d2 and M ′ = M (d′2 , c′2 ) = T1 1 T2 2 X1 1 X2 2 .
c′

c′

d′

d′

Then (d2 , c2 ) ≡ (d′2 , c′2 ) if and only if

q − 1 ∣ di − d′i ,
q − 1 ∣ cj − c′j ,

(C1)
(C2)

di = 0 ⇔ d′i = 0,

cj = 0 ⇔

c′j

(C3)

= 0.

(C4)

Proof. The conditions (C1), (C2), (C3) and (C4) clearly imply that M (d2 , c2 ) ≡
M (d′2 , c′2 ), hence (d2 , c2 ) ≡ (d′2 , c′2 ). To prove the converse, assume that M ≡ M ′
and write
M = M (d2 , c2 ) = T1c1 T2c2 X1d1 X2d2 and M ′ = M (d′2 , c′2 ) = T1 1 T2 2 X1 1 Xn2 .
c′

c′

d′

d′

Let x ∈ Fq . Then M (1, x, 1, 1) = M ′ (1, x, 1, 1), which means xc2 = xc2 . But
′

this equality is true for any element x of Fq if and only if (T2q − T2 ) ∣ (T2c2 − T2 2 ).
c′

This is equivalent to c2 = c′2 = 0 or c2 c′2 ≠ 0 and T2q−1 − 1 ∣ T2 2 (T2 2 2 − 1), which
means that q − 1 ∣ c2 − c′2 and proves (C2) and (C4) for i = 2.
Repeating this argument evaluating at (1, 1, 1, x) for every x ∈ Fq gives q −
1 ∣ d2 − d′2 and d2 = 0 if and only if d′2 = 0, i.e. (C1) and (C3) for i = 2.
Moreover, we have d1 + d2 = d′1 + d′2 = δX , which means that q − 1 ∣ d2 − d′2 if
′
and only if q − 1 ∣ d1 − d′1 . Evaluating at (1, 1, 0, 1) gives 0d1 = 0d1 . Then d1 = 0
′
if and only if d1 = 0. This proves (C1) and (C3) for i = 1.
It remains the case of c1 and c′1 . We have
c′ −1

c1 − c′1 = c′2 − c2 − η(d′1 − d1 )

c −c′

and q − 1 divides c2 − c′2 and d′1 − d1 . Then it also divides c1 − c′1 . Evaluating at
(0, 1, 1, 1) yields like previously c1 = 0 of and only if c′1 = 0.
8

Remark 2.2.6. The conditions of Lemma 2.2.5 also can be written
ci = c′i = 0 or ci c′i ≠ 0 and q − 1 ∣ c′i − ci ,

di = d′i = 0 or di d′i ≠ 0 and q − 1 ∣ d′i − di .

(8)
(9)

Besides, the conditions involving q are always satisfied for q = 2.
Observation 2.2.7. The conditions (C3) and (C4) mean that a point of the
polygon P(δT , δX ) lying on an edge can be equivalent only with a point lying
on the same edge. Therefore the equivalence class of a vertex of P(δT , δX ) is a
singleton.
To show that the number of equivalence classes equals to the dimension of
the code Cη (δT , δX ) as stated in Theorem A, we goal to choose a set K(δT , δX )
of representatives of the equivalence classes of P(δT , δX ) under the relation ≡,
which gives naturally a set of representatives ∆(δT , δX ) for M(δT , δX ) under
the binary relation ≡.
Notation 2.2.8. Let (δT , δX ) ∈ Z × N and q ≥ 2. Let us set
AX = {α ∈ N ∣ 0 ≤ α ≤ min(⌊A⌋, q − 1)} ∪ {A} ∩ N

K(δT , δX ) = {(α, β) ∈ N2 ∣

α ∈ AX
}
0 ≤ β ≤ min(δ − ηα, q) − 1 or β = δ − ηα

∆(δT , δX ) = {M (α, β) ∣ (α, β) ∈ K(δT , δX )}.

Notice that K(δT , δX ) is nothing but P(δT , δX ) cut out by the set
({d2 ≤ q − 1} ∪ {d2 = A}) ∩ ({c2 ≤ q − 1} ∪ {c2 = δ − ηd2 )}) .

We now give a map that displays K(δT , δX ) as a set of representatives of
P(δT , δX ) under the equivalence relation ≡.

Definition 2.2.9. Let us set the map p(δT ,δX ) ∶ P(δT , δX ) → P(δT , δX ) such
that for every couple (d2 , c2 ) ∈ P(δT , δX ) its image p(δT ,δX ) (d2 , c2 ) = (d′2 , c′2 ) is
defined as following.
• If d2 = 0 or d2 = A, then d′2 = d2 ,

• Otherwise, we choose d′2 ≡ d2 mod q − 1 with 1 ≤ d′2 ≤ q − 1.

and
• If c2 = 0, then c′2 = 0,

• If c2 = δT + η(δX − d2 ), then c′2 = δT + η(δX − d′2 ),

• Otherwise, we choose c′2 ≡ c2 mod q − 1 with 1 ≤ c′2 ≤ q − 1.
Proposition 2.2.10.
1. The map p(δT ,δX ) induces a bijection from the quotient set P(δT , δX )/ ≡ to K(δT , δX ).
2. The set K(δT , δX ) is a set of representatives of P(δT , δX ) under the equivalence relation ≡.

3. The set ∆(δT , δX ) is a set of representatives of M(δT , δX ) under the
equivalence relation ≡.
9

Proof. First notice that elements of K(δT , δX ) are invariant under p(δT ,δX ) .

The inclusion p(δT ,δX ) (P(δT , δX )) ⊂ K(δT , δX ) is clear by definitions of
K(δT , δX ) (Not. 2.2.8) and p(δT ,δX ) (Def. 2.2.9). The equality follows from
the invariance of K(δT , δX ).

Last, we prove that p(δT ,δX ) (d2 , c2 ) ≡ (d2 , c2 ) for every couple (d2 , c2 ) ∈
P(δT , δX ). Take a couple (d2 , c2 ) ∈ P(δT , δX ) and denote by (d′2 , c′2 ) its image under p(δT ,δX ) . We have to prove that (d2 , c2 ) and (d′2 , c2 ) satisfy all the
conditions of Proposition 2.2.5.
By definition of p(δT ,δX ) , it is clear that conditions (C1), (C2), (C3), as
well as the the forward implication of (C4), are true. It remains to prove that
c′i = 0 ⇒ ci = 0 for i ∈ {1, 2}.
Let us prove only the case i = 2. So assume that c′2 = 0. Then c2 = 0 or
c2 = δT + η(δX − d2 ). However,
c2 = δT + η(δX − d2 ) ⇔ δT + η(δX − d′2 ) = 0 ⇔ d′2 = δX +

δX
.
η

This is only possible when δT ≤ 0 and then d′2 = A. By condition (C3), this
implies that d2 = A and then c2 = 0. This proves the first item.
The second assertion is a straightforward consequence of the first one.
Finally the third assertion yields from the definition of the equivalence relation ≡ on P(δT , δX ) via the bijection (7).

Corollary 2.2.11. The number of equivalence classes #∆(δT , δX ) of M(δT , δX )
under ≡ is equal to the cardinality of K(δT , δX ).
Proof. Its results from Definition 2.2.4 and Proposition 2.2.10.

2.3

Proof of Theorem A

The proof essentially rests on the following endomorphism π(δT ,δX ) on R(δT , δX )
defined on the basis of monomials M(δT , δX ) by conjugation of p(δT ,δX ) by the
bijection (7).
Definition 2.3.1. Let us set the linear map π(δT ,δX ) ∶ R(δT , δX ) → R(δT , δX )
such that for every monomial M (d2 , c2 ) ∈ R(δT , δX ) for (d2 , c2 ) ∈ P (δT , δX ),
π(δT ,δX ) (M (d2 , c2 )) = M (p(δT ,δX ) (d2 , c2 )).

Theorem A follows from the following proposition.
Proposition 2.3.2. The linear map π(δT ,δX ) is the projection along I(δT , δX )
onto Span ∆(δT , δX ). Moreover the set ∆(δT , δX ) is linearly independent modulo I(δT , δX ).

Proof. By construction of ∆(δX , δT ) and the definition of π(δT ,δX ) , it is clear
that range π(δT ,δX ) ⊂ Span ∆(δT , δX ). Also, by Proposition 2.2.10 and the bijection (7), any monomial of ∆(δT , δX ) is invariant under π(δT ,δX ) , which ensures
that range π(δT ,δX ) = Span ∆(δT , δX ) and that π(δT ,δX ) is a projection. Then

R(δT , δX ) = range π(δT ,δX ) ⊕ ker π(δT ,δX ) = Span ∆(δT , δX ) ⊕ ker π(δT ,δX ) . (10)
10

By Proposition 2.2.10, we have
∀ M ∈ M(δT , δX ), M − π(δT ,δX ) (M ) ∈ I(δT , δX ),

which proves the inclusion ker π(δT ,δX ) = range(Id −π(δT ,δX ) ) ⊂ I(δT , δX ).
The proof is completed by proving that the only zero linear combination of
elements of ∆(δT , δX ) that belongs to I(δT , δX ) is the trivial one.
On one hand, this implies that the family ∆(δT , δX ) is linearly independent
modulo I(δT , δX ). On the other hand, it also implies
I(δT , δX ) ∩ Span(∆(δT , δX ) = {0},

which entails the equality ker π(δT ,δX ) = I(δT , δX ). Indeed, ker π(δT ,δX ) is a complementary space of Span(∆(δT , δX )) in R(δT , δX ) by (10). Since ker π(δT ,δX )
is included in I(δT , δX ), if the intersection of I(δT , δX ) and Span(∆(δT , δX ))
is the nullspace then ker π(δT ,δX ) = I(δT , δX ).
To this end, let us assume that a linear combination of elements of ∆(δT , δX )
H=

∑

(α,β)∈K(δT ,δX )

λα,β M (α, β)

satisfies ev(δT ,δX ) (H) = 0.
On one side, H(1, 0, 1, 0) = λ0,0 , H(1, 0, 0, 1) = λδX ,0 , H(0, 1, 0, 1) = λδX ,δT
and H(0, 1, 1, 0) = λ0,δ . Then
λ0,0 = λδX ,0 = λδX ,δT = λ0,δ = 0.

On the other side, evaluating at (1, a, 1, 0) for any a ∈ Fq gives
H(1, a, 1, 0) =

min(q−1,δ−1)

∑

β=1

λ0,β aβ = 0.

Then the polynomial
min(q−1,δ−1)

∑

λ0,β X β

β=1

of degree lesser than (q −1) has q zeros. This implies that λ0,β = 0 for any β such
that (0, β) ∈ K(δT , δX ). Evaluating at (1, a, 0, 1), we can deduce that λδX ,β = 0
for any β such that (δX , β) ∈ K(δT , δX ).
Repeating the previous argument by evaluating at (1, 0, 1, a), we get λα,0 = 0
for any α such that (α, 0) ∈ K(δT , δX ).
Evaluating at (0, 1, 1, a) gives λα,B(α) = 0, with B(α) = δ − ηα, for any α
such that (α, B(α)) ∈ K(δT , δX ).
For any a, b ∈ Fq , we then have
H(1, a, 1, b) =

min(q−1,δX −1)

∑

α=1

⎛min(q−1,M(α)−1)
⎞
λα,β aβ bα = 0
∑
⎝
⎠
β=1

which implies that for any a ∈ Fq , the polynomial
min(q−1,δX −1)

∑

α=1

⎛min(q−1,M(α)−1)
⎞
λα,β aβ X α
∑
⎝
⎠
β=1
11

of degree lesser than (q −1) has q zeros and, thus, is zero. By the same argument
on each coefficient as polynomials of variable a, we then have proved that the
linear combination H is zero.

Proposition 2.3.2 displays ∆(δT , δX ) as a set of representatives of R(δT , δX )
modulo I(δT , δX ) and proves Theorem A, which can be rephrased as follow.
Corollary 2.3.3. The dimension of the code Cη (δT , δX ) equals to
dim Cη (δT , δX ) = #K(δT , δX ).
Proof. It a straightforward consequence of Corollary 2.2.11 and Theorem A.

Example 2.3.4. We can easily deduce from Corollary 2.3.3 that the evaluation
map ev(δT ,δX ) is surjective if δT ≥ q and δX ≥ q. Indeed, in this case,
K(δT , δX ) = {(α, β) ∈ N2 ∣

α ∈ ⟦0, q − 1⟧ ∪ {δX }
},
β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}

so that dim Cη (δT , δX ) = #K(δT , δX ) = (q + 1)2 = N .

c2
δ

δT

δX

d2

Figure 3: P(3, 4) with q = 3 in H1
Example 2.3.5. Let us set η = 2 and q = 3. Let us sort the monomials of
R(−2, 5), grouping the ones with the same image under ev(−2,5) , using Proposition 2.2.10, and associating at each group a couple in K(−2, 5).
12

Exponents (c1 , c2 , d1 , d2 ) of T1c1 T2c2 X1d1 X2d2
Couple in K(−2, 5)
(8, 0, 5, 0)
(0, 0)
(7, 1, 5, 0) ∼ (5, 3, 5, 0) ∼ (3, 5, 5, 0) ∼ (1, 7, 5, 0)
(0, 1)
(0, 2)
(6, 2, 5, 0) ∼ (4, 4, 5, 0) ∼ (2, 6, 5, 0)
(0, 8, 5, 0)
(0, 8)
(6, 0, 4, 1) ∼ (2, 0, 2, 3)
(1, 0)
(5, 1, 4, 1) ∼ (3, 3, 4, 1) ∼ (1, 5, 4, 1) ∼ (1, 1, 2, 3)
(1, 1)
(4, 2, 4, 1) ∼ (2, 4, 4, 1)
(1, 2)
(1, 6)
(0, 6, 4, 1) ∼ (0, 2, 2, 3)
(4, 0, 3, 2)
(0, 2)
(3, 1, 3, 2) ∼ (1, 3, 3, 2)
(2, 1)
(2, 2)
(2, 2, 3, 2)
(0, 4, 3, 2)
(2, 4)
(0, 0, 1, 4)
(4, 0)
Then the dimension of the code is #K(−2, 5) = 13.
c2

c2
=δ
−η
d2

d2
Figure 4: Dots in P(−2, 5) correspond to elements of K(−2, 5).

2.4

Explicit formulae for the dimension of Cη (δT , δX ) and
examples

By Corollary 2.3.3, computing the dimension is now reduced to the combinatorial question of the number of couples in K(δT , δX ). The key of the proof
of Proposition 2.4.1 below is to give a well-chosen partition of K(δT , δX ) from
which we can easily deduce its cardinality. Putting aside the very particular
case of η = 0, two cases have to be distinguished according to the sign of δT ,
which determinates the shape of P(δT , δX ) and the value of A. These two cases
are themselves subdivided into several subcases, depending on the position of
the preimage s of q under the function x ↦ δ − ηx with respect to AX , defined
in Notation 2.2.8.

13

Proposition 2.4.1. On H0 , the dimension of the evaluation code C0 (δT , δX )
equals to
dim C0 (δT , δX ) = (min(δT , q) + 1) (min(δX , q) + 1) .
On Hη with η ≥ 1, we set

⎧
min(δT , q) + 1 if δT ≥ 0 and q ≤ δX ,
⎪
⎪
⎪
1
if δT ≤ 0, q ≤ A and η ∣ δT ,
m = min(⌊A⌋ , q − 1), h = ⎨
⎪
⎪
⎪
0
otherwise,
⎩

⎧
⌊s⌋ if s ∈ [0, m],
⎪
⎪
δ−q
⎪
and ̃
s = ⎨ −1 if s < 0,
s=
⎪
η
⎪
⎪
⎩ m if s > m.
The evaluation code Cη (δT , δX ) on the Hirzebruch Surface Hη has dimension
dim Cη (δT , δX ) = (q + 1)(̃
s + 1) + (m − ̃
s) (δ + 1 − η (

m+̃
s+1
)) + h.
2

Remark 2.4.2. The previous proposition generalizes the result of [1], in which
the authors studied rational scrolls. By Example 3.1.16. [4], the rational scroll
S(a1 , a2 ) for a1 ≥ a2 ≥ 1 is isomorphic to the Hirzebruch surface H(a1 −a2 ) . It
is easily checked that this geometric isomorphism induces a Hamming isometry
between the codes. We thus can compare our result with theirs for η = a1 −
a2 and δT = a2 δX . Despite the appearing difference due to a different choice
of monomial order (see Definition 3.0.2 and Remark 3.0.3), both formulae do
coincide.
Proof. To prove the case η = 0, it is enough to write
K(δT , δX ) = {(α, β) ∈ N2 ∣

α ∈ ⟦0, min(δX , q) − 1⟧ ∪ {δX }
}.
0 ≤ β ≤ min(δT , q) − 1 or β = δ − ηα

Now, assume η ≥ 1 and δT > 0.

• Let us assume that q > δX .

– If q > δ also, then s < 0 and
K(δT , δX ) = ⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧}
δX

α=0

δX

and thus #K(δT , δX ) = ∑ (δ − ηα + 1) = (δX + 1) (δT + η
α=0

– If δT ≤ q ≤ δ, then 0 ≤ s ≤ δX and one can write

δX
+ 1) .
2

⎛ ⌊s⌋
⎞
K(δT , δX ) = ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}}
⎝α=0
⎠
∪

⎛ δX
⎞
⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧} .
⎝α=⌊s⌋+1
⎠
14

⌊s⌋

and thus #K(δT , δX ) = ∑ (q + 1) +
α=0

δX

∑ (δ + 1 − ηα)

α=⌊s⌋+1

= (q + 1)(⌊s⌋ + 1) + (δX − ⌊s⌋) (δ + 1 − η

δX + ⌊s⌋ + 1
).
2

– If δX < q < δT , then s > δX and
K(δT , δX ) = ( ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}})
δX

α=0

and then #K(δT , δX ) = (q + 1)(δX + 1).
• Let us assume that q ≤ δX .
– If

δ
η+1

< q, then 0 ≤ s < q and ⌊s⌋ ∈ AX .
⎛ ⌊s⌋
⎞
K(δT , δX ) = ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}}
⎝α=0
⎠
∪

⎞
⎛ q−1
⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧}
⎠
⎝α=⌊s⌋+1

∪ {(δX , β) ∣ β ∈ ⟦0, h⟧}.

Then
⌊s⌋

q−1

α=0

α=⌊s⌋+1

#K(δT , δX ) = ∑ (q + 1) +

∑ (δ + 1 − ηα) + h + 1.

= (q + 1)(⌊s⌋ + 1) + (q − 1 − ⌊s⌋) (δ + 1 − η
– If q ≤

δ
,
η+1

q + ⌊s⌋
)+h+1
2

then s ≥ q and
q−1

K(δT , δX ) = ( ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}})∪{(δX , β)∣β ∈ ⟦0, h⟧}.
α=0

Then #K(δT , δX ) = (q + 1)q + h + 1.
Finally assume η ≥ 1 and δT ≤ 0.
Let us rewrite K(δT , δX ) to lead to formulae that coincide with the general
one given above according to the position of q in the increasing sequence

with A = ηδ . For any α ∈ AX ,

η
A < A ≤ ηA,
η+1

q ≤ δ − ηα ⇔ α ≤
15

δ−q
= s < A.
η

• If q > ηA, then s < 0 and we can write
⌊A⌋

K(δT , δX ) = ⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧}
α=0

⌊A⌋

and thus #K(δT , δX ) = ∑ (δ − ηα + 1) = (⌊A⌋ + 1) (δ + 1 − η
α=0

⌊A⌋
).
2

• If A < q ≤ ηA (with η ≥ 2), we have
K(δT , δX ) =

⎛ ⌊s⌋
⎞ ⎛ ⌊A⌋
⎞
⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}} ∪ ⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧}
⎝α=0
⎠ ⎝α=⌊s⌋+1
⎠

and then
⌊s⌋

⌊A⌋

α=0

α=⌊s⌋+1

#K(δT , δX ) = ∑ (q + 1) +

∑ (δ − ηα + 1)

= (q + 1)(⌊s⌋ + 1) + (⌊A⌋ − ⌊s⌋) (δ + 1 − η
• If

η
A
η+1

⌊A⌋ + ⌊s⌋ + 1
).
2

< q ≤ A, then q − 1 < ⌊A⌋.
⎛ ⌊s⌋
⎞
K(δT , δX ) = ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}}
⎝α=0
⎠
∪

⎞
⎛ q−1
⋃ {(α, β) ∣ β ∈ ⟦0, δ − ηα⟧}
⎠
⎝α=⌊s⌋+1

∪ {(A, 0)} ∩ N2 .

Then
⌊s⌋

q−1

α=0

α=⌊s⌋+1

#K(δT , δX ) = ∑ (q + 1) +

∑ (δ − ηα + 1) + 1{η ∣ δT }

= (q + 1)(⌊s⌋ + 1) + (q − 1 − ⌊s⌋) (δ + 1 − η
• If q ≤

η
A,
η+1

q + ⌊s⌋
) + 1{η ∣ δT }.
2

then s ≥ q and
q−1

K(δT , δX ) = ( ⋃ {(α, β) ∣ β ∈ ⟦0, q − 1⟧ ∪ {δ − ηα}}) ∪ {(A, 0)} ∩ N2
α=0

which gives #K(δT , δX ) = (q + 1)q + 1{η ∣ δT } .

16

c2

c2

c2

c2

ηA

ηA

ηA

ηA

d2

d2

d2

d2

(a) ηA ≤ q = 11

ηA
η+1

−η

−η

−η

−η

d2

=δ

=δ

=δ

=δ

A

c2

c2

c2

c2
ηA
η+1

A

d2

(b) A < q = 7 ≤ ηA

ηA
η+1

A

(c) q = A = 4

ηA
η+1

d2

(d) q = 2 ≤

A

d2

η
A
η+1

Figure 5: P(−2, 5) in H2 for different values for q.

2.5

Examples

Example 2.5.1. Let us compute the dimension of the code C2 (−2, 5) using the
previous formula on different finite fields. We have A = 4 ∈ N. See Figure 5.
• On F11 , m = A, s < 0, ̃
s = −1,

4
dim C2 (−2, 5) = (4 + 1) (−2 + 2 (5 − ) + 1) = 25.
2
• On F7 , m = A, s = ̃
s = 0,
5
dim C2 (−2, 5) = (7 + 1) + 4 (−2 + 2 (5 − ) + 1) = 8 + 16 = 24.
2
• On F4 , m = 3, s = ̃
s = 2,
6
dim C2 (−2, 5) = (4 + 1)(2 + 1) + (−2 + 2 (5 − ) + 1) + 1 = 15 + 3 + 1 = 19.
2
• On F2 , m = 1, s = ̃
s = 1,

dim C2 (−2, 5) = (2 + 1)(1 + 1) + 1 = 6 + 1 = 7.

Example 2.5.2. To illustrate the cases q ≤ δX , let us compute the dimension
of the code C2 (1, 3) using the previous formula on F3 and F2 . See Figure 6.
• On F3 , m = 2, s = ̃
s = 2, h = 1, dim C2 (1, 3) = (3 + 1)(2 + 1) + 1 + 1 = 14.

• On F2 , m = 1, s = 2.5 > m, ̃
s = 1, h = 1, dim C2 (−2, 5) = (2+1)(1+1)+1+1 =
6 + 1 = 8.

Example 2.5.3. On H2 , let us compute the dimension of the code C2 (5, 3) on
the finite fields F13 , F7 and F4 . See Figure 7. Since q > δX , we have m = δX = 3.
17

c2

c2

δ

δ

c2

c2

=δ

=δ

−η

−η

d2

d2

δ
η+1

δ
η+1

δT

δT

d2

δX
(a)

δ
η+1

d2

δX
(b) q = 2 ≤

< q = δX = 3

δ
η+1

Figure 6: P(1, 3) in H2
c2

c2

c2

δ

δ

δ
c2

c2

c2

=δ

=δ

=δ

−η

−η

−η

d2

d2

d2

δT

δT

δX
(a) δ < q = 13

δT

d2

δX

d2

(b) δT ≤ q = 7 ≤ δ

δX

d2

(c) δX < q = 4 < δT

Figure 7: P(5, 3) in H2
• On F13 , s < 0 then ̃
s = −1.
• On F7 , s = ̃
s = 2.

dim C2 (5, 3) = (3 + 1)(5 + 3 + 1) = 36.

dim C2 (5, 3) = (7 + 1)(2 + 1) + (3 − 2) (5 + 2 (3 −

• On F4 , s > m then ̃
s = m = 3.

3+2+1
) + 1) = 24 + 6 = 30.
2

dim C2 (5, 3) = (4 + 1)(3 + 1) = 20.
18

3

Gröbner Basis

Our strategy to compute the dimension of the code highlights the key role of
monomials in our study. This idea remains predominant in the calculus of the
minimum distance, through the use of Gröbner bases. Until now, every technique we used has come from linear algebra, focusing on the finite dimensional
vector spaces R(δT , δX ) and vector subspaces ker ev(δT ,δX ) . From now on, the
minimum distance problem is handled in term of commutative algebra by considering not only homogeneous components but the whole ideal in the ring R.
Notation 3.0.1. We now consider the evaluation map on R,
⎧
R
⎪
⎪
ev ∶ ⎨ F = ∑ F(δ ,δ )
T X
⎪
⎪
(δT ,δX )
⎩

→ FN
q
↦
∑

(δT ,δX )

ev(δT ,δX ) (F(δT ,δX ) ) ,

a ring homomorphism which kernel is denoted by I = ker ev ⊂ R.
The ideal I is a graded ideal and
I=

⊕

(δT ,δX )∈Z×N

I(δT , δX ).

Let us first recall classical facts about Gröbner bases. The reference for this
section is [3].
Let R be a polynomial ring. A monomial order is a total order on the
monomials, denoted by <, satisfying the following compatibility property with
multiplication: for all monomials M, N, P ,
M < N ⇒ M P < N P and M < M P.
For every polynomial F ∈ R, one can define the leading term of F to be the
greatest term of F for this ordering, denoted by LT(F ).
Let I be an ideal of the polynomial ring R, endowed with a monomial order
<. The monomial ideal LT(I) ⊂ R associated to I is the ideal generated by the
leading terms LT(F ) of all polynomials F ∈ I. A subset G of an ideal I is a
Gröbner basis of the ideal I if
LT(I) = ⟨LT(g) ∣ g ∈ G⟩ .
The first step to use tools from Gröbner bases theory is setting a monomial
order over R = Fq [T1 , T2 , X1 , X2 ].
Definition 3.0.2. Let us define a order on monomials of R by stating that
T1 1 T2 2 X1 1 X2 2 < T1c1 T2c2 X1d1 X2d2
c′

c′

d′1

+ d′2
d′2

d′

d′

if and only if
d′1 + d′2 < d1 + d2 or ∣

= d1 + d2
< d2

19

RR d′
RRR 1
or RRRR d′2
RRR c′
R 2

= d1
= d2
< c2

RR
RRR
RR
or RRRR
RR
RRR
RR

d′1
d′2
c′2
c′1

= d1
= d2
= c2
< c1

One can easily check that < is a monomial order.
Remark 3.0.3. The choice of this monomial order is motivated by the choice of
representatives of monomials under ≡, and so by the choice of the projection map
π(δT ,δX ) . Actually π(δT ,δX ) (M ) is chosen for any monomial M ∈ M(δT , δX ) to
be the smallest element for the order < among all monomials that are equivalent
to M .
Notice that exchanging the role of d1 and d2 and the one of c1 and c2 , we
recover the monomial order chosen by Carvalho and Neumann [1].
Notation 3.0.4. Let (δT , δX ) ∈ Z × N. Let us set

G(δT , δX ) = {M − M ′ ∣ M, M ′ ∈ M(δT , δX ) such that M ≡ M ′ }

and

G=

⋃

(δT ,δX )

G(δT , δX ).

Proposition 3.0.5. The set G is a Gröbner basis of I.

Proof. Let us first prove that G(δT , δX ) is a spanning family for the vector
space I(δT , δX ) for any couple (δT , δX ) ∈ Z × N. By definition, it is clear that
G(δT , δX ) ⊂ I(δT , δX ). Furthermore, by Proposition 2.3.2, the map π(δT ,δX ) is
a projection along I(δT , δX ). Hence
ker π(δT ,δX ) = I(δT , δX ) = range(Id −π(δT ,δX ) ).

Since M ≡ π(δT ,δX ) (M ) for every M ∈ M(δT , δX ), the set G(δT , δX ) contains
all the binomials of the form M − π(δT ,δX ) (M ) and then
range(Id −π(δT ,δX ) ) ⊂ Span G(δT , δX ),

which implies that Span G(δT , δX ) = I(δT , δX ) and the set G is a basis of the
ideal I.
Now, let use Buchberger’s Criterion (see [3] §6 Th.6). Let
F = T1c1 T2c2 X1d1 X2d2 − T1 1 T2 2 X1 1 X2 2
c′

and

c′

d′

d′

̃
̃
d
d
c
c
F̃ = T1c̃1 T2c̃2 X1d1 X2d2 − T1 1 T2 2 X1 1 X2 2
̃′

̃′

̃′

̃′

be two polynomials of G. Let us assume without loss of generality that the
leading term is the second one in each polynomial. Let us set
C1 = max(c′1 , c̃′1 ), C2 = max(c′2 , c̃′2 ), D1 = max(d′1 , d̃′1 ) and D2 = max(d′2 , d̃′2 ).

The S-polynomial of F and F̃

T C1 T C2 X1D1 X2D2 ̃
T C1 T C2 X1D1 X2D2
F
F− 1 2
S(F, F̃) = 1 2
LT (F )
LT (F̃)
= T1

C1 −c′1 +c1

− T1

C2 −c′2 −c2

T2

C1 −c̃′1 +c̃1

D1 −d′1 +d1

X1

C2 −c̃′2 −c̃2

T2

20

D2 −d′2 −d2

X2

D1 −d̃′1 +d̃1

X1

D2 −d̃′2 −d̃2

X2

belongs to R(C1 + C2 − a1 D1 − a2 D2 , D1 + D2 ). Moreover, using that F and
F̃ satisfy the conditions of Lemma 2.2.5, we have to prove that S(F, F̃) also
satisfies these conditions.
The only conditions which verification is not trivial are (C3) and (C4). Let
us give details for condition (C4) and i = 1, i.e.
C1 − c′1 + c1 = 0 ⇔ C1 − c̃′1 + c̃1 = 0

Assume that C1 − c′1 + c1 = 0. Recall that C1 = max(c′1 , c̃′1 ).

• If C1 = c′1 , then c1 = 0. Since F ∈ G, c′1 = 0 = C1 .

• If C1 = c̃′1 , then C1 − c′1 ≥ 0 and c1 ≥ 0 and their sum is zero. Then
C1 = c′1 = c1 = 0.

In both cases, C1 = max(c′1 , c̃′1 ) = 0, which implies that c̃′1 = 0 and, since
F̃ ∈ G, c̃1 = 0. Then C1 − c̃′1 + c̃1 = 0.
By symmetry, the equivalence is immediate.
Then S(F, F̃) ∈ G(C1 + C2 − a1 D1 − a2 D2 , D1 + D2 ) and then the remainder
on division of S(F, F̃) by G is obviously zero.
Remark 3.0.6. Since every polynomial in G is homogeneous, the ideal I is homogeneous. This gives a natural graduation of the quotient
RÒ =
I

⊕ (R(δT , δX )Ò I(δT , δX ))

(δT ,δX )

Let us recall an interesting property of Gröbner bases (see [13] Proposition
1.1) that will be used to compute the minimum distance of the code.
Proposition 3.0.7. Let I be an ideal of a polynomial ring R with Gröbner basis
G. Then, setting π as the canonical projection of R onto RÒ I , the set
{π(M ) ∣ M monomials of R such that for all g ∈ G, LT(g) ∤ M }
is a basis of RÒ I as a vector space.

Corollary 3.0.8. Let (δT , δX ) ∈ Z × N such that δ ≥ 0. A basis of a complementary space of I(δT , δX ) in R(δT , δX ) is the set {M ∈ M(δT , δX )∣∀g ∈ G, LT(g) ∤
M }.
Proof. By Propositions 3.0.5 and 3.0.7, the set

⎫
⎧
⎪
⎪
⎪
⎪
M(δT , δX ) ∣ ∀ g ∈ G, LT(g) ∤ M ⎬
B = ⎨M ∈
⋃
⎪
⎪
⎪
⎪
(δT ,δX )∈Z×N
⎭
⎩

is a basis of a complementary of I seen as Fq -vector subspace of R. Every
element of B is homogeneous. The result consists only on restricting on a homoegenous component.
In Proposition 2.3.2 we displayed ∆(δT , δX ) as a basis of R(δT , δX ) modulo
the subspace I(δT , δX ) for each couple (δT , δX ). Actually the image under the
canonical projection of the union of the ∆(δT , δX ) is exactly the basis given by
the previous proposition, as stated in the following lemma.
21

Lemma 3.0.9. Let us set ∆ = ⋃(δT ,δX ) ∆(δT , δX ). Then ∆ is the set of monomials of R that are not divisible by the leading term of any polynomial of G.
Proof. Let G = T1 1 T2 2 X1 1 X2 2 − T1c1 T2c2 X1d1 X2d2 ∈ G(ǫT , ǫX ). By definition of G
and Lemma 2.2.5, there exist k, l ∈ Z such that
c′

c′

d′

d′

d′2 = d2 + k(q − 1), d′1 = d1 − k(q − 1), c′2 = c2 + l(q − 1) and c′1 = c1 − (l + ηk)(q − 1).

Let us assume that the first monomial is the leading one. Since d′1 + d′2 = d1 + d2
and c′1 + c′2 − ηd′1 = c1 + c2 − ηd1 , this implies that either d′2 > d2 or d′2 = d2 and
c′2 > c2 . This means that either k ∈ N∗ or k = 0 and l ∈ N∗ .
Let (α, β) ∈ K(δT , δX ) and M = M (α, β) ∈ ∆(δT , δX ). Let us assume that
LT(G) divides M , that is to say
ǫX − d′2

c′1 =

d′2 ≤ α

= d′1
c′2
ǫT + η(ǫX − d′2 ) − c′2

≤ δX − α
≤β

≤ δ − ηα − β

(i)
(ii)
(iii)
(iv)

We want to reach a contradiction.
• Let first assume that k ∈ N∗ . By condition (C1) for i = 2, this implies that
d2 ≥ 1 and then d′2 ≥ q. Since LT(G) divides M , we deduce that d′2 ≤ α.
The only possible value for α is thus α = A if A ∈ N.

– If δT ≥ 0, then α = A = δX and then, by (ii), d′1 = 0. By condition
(C3) for i = 1, d1 = 0 and then k = 0, which leads to a contradiction.

– If δT < 0 et η ∣ δT , α = A = ηδ . Then, by definition of K(δT , δX ) (Not.
2.2.8),
β = δ + η(δX − α) = 0.

By (iii) and (iv), c′1 = c′2 = 0. By condition (C4), c1 = c2 = 0. But
c′1 + c′2 = c1 + c2 = ǫT + ηd′1 = ǫT + ηd1 , which implies that d′1 = d1 and
then k = 0. This leads to a contradiction.

• Now, let us assume that k = 0 and l ∈ N∗ . As before, we have c′2 ≥ q. Since
c′2 ≤ β, by Notation 2.2.8, β = δT + η(δX − α). Then c′1 = 0 and c1 = 0,
which contradicts the hypothesis l ≠ 0.
We then have proved that ∆ is a subset of the set of monomials non divisible
by the leading term of any polynomial in G. But these two sets are basis of two
complementary spaces of a same vector space by Proposition 2.3.2 and Corollary
3.0.8. Therefore, these two sets coincide.

4
4.1

Minimum distance of Cη (δT , δX )
Proof of the the lower bound of the minimum distance
in Theorem B

Let us fix (ǫT , ǫX ) ∈ N2 such that ǫT , ǫX ≥ q.
22

Notation 4.1.1. Let us set
∆(ǫT , ǫX )F = {N ∈ ∆(ǫT , ǫX ) ∣ LT(F ) ∣ N }

with ∆(ǫT , ǫX ) defined in Notation 2.2.8.

Let F ∈ R(δT , δX ) ∖ ker ev(δT ,δX ) and Z(F ) its zero set in Hη . We define
NF = #Z(F )(Fq ).

We prove now the lower bound
dη (δT , δX ) ≥

#∆(ǫT , ǫX )M .

min

M∈∆(δT ,δX )

To prove equality, we explicit the minimum above in Proposition 4.2.3. Then in
Proposition 4.2.4 we produce polynomials which codewords have weight exactly
equal to this lower bound, ensuring it is indeed the minimum distance.
Proof of the lower bound. Recall that the minimum distance is defined by
dη (δT , δX ) =

min

F ∈R(δT ,δX )
F ∉ker ev(δT ,δX )

ω(ev(δT ,δX ) (F )).

First, Proposition 2.3.2 gives ev(δT ,δX ) (F ) = ev(δT ,δX ) (π(δT ,δX ) (F )) and
then
dη (δT , δX ) =

min

F ∈Span ∆(δT ,δX )

ω(ev(δT ,δX ) (F )) =

min

F ∈Span ∆(δT ,δX )

N − NF ,

so that we aim to bound from below N − NF uniformly in F ∈ Span ∆(δT , δX ).

Let us fix such a polynomial F ∈ Span ∆(δT , δX ).
Second, we aim to regard NF as the dimension of some vector space. For
this purpose, fix (ǫT , ǫX ) ∈ Z × N and consider the map
ev(ǫT ,ǫX ),F ∶ {

F
R(ǫT , ǫX ) → FN
q
.
G ↦ (G(Q))Q∈Z(F )(Fq )

For ǫT , ǫX ≥ q the evaluation map ev(ǫT ,ǫX ) is surjective by Example 2.3.4.
The map ev(ǫT ,ǫX ),F is thus also surjective for any F ∈ R(δT , δX ), as illustrated
by the diagram
ev(ǫT ,ǫX ),F
R(ǫT , ǫX )

Hη (Fq )

ev(ǫT ,ǫX )

Z(F )(Fq )

Fq

Fq

It follows that
NF = dim (R(ǫT , ǫX )Ò ker ev
23

(ǫT ,ǫX ),F

).

.

̃F of NF such that N − N
̃F turns
Third we aim to display an upper bound N
to be easier to handle. Let us denote by ⟨F ⟩ the ideal of R generated by F and
by ⟨F ⟩(ǫT ,ǫX ) the subspace F R(ǫT − δT , ǫX − δX ) ⊂ R(ǫT , ǫX ) spanned by F .
̃F ≥ NF
Observing that ker ev(ǫT ,ǫX ) + ⟨F ⟩(ǫT ,ǫX ) ⊂ ker ev(ǫT ,ǫX ),F , we get N
with
̃F = dim (R(ǫT , ǫX )Ò
N
).
ker ev
+ ⟨F ⟩
(ǫT ,ǫX )

Hence

dη (δT , δX ) ≥

min

F ∈Span ∆(δT ,δX )

(ǫT ,ǫX )

̃F
N −N

(11)

̃F uniformly in F ∈ Span ∆(δT , δX ).
and we are now reduced to bound from below N −N
Fourth, we now prove that

̃F ≥ #∆(ǫT , ǫX )F .
N −N

(12)

In fact, we display ∆(ǫT , ǫX )F as a subfamily of ∆(ǫT , ǫX ) which complement
would be a spanning family of the vector space R(ǫT , ǫX ) modulo the vector
subspace ker ev(ǫT ,ǫX ) + ⟨F ⟩(ǫT ,ǫX ) .
By Corollary 3.0.8 and Lemma 3.0.9,
∆(ǫT , ǫX ) = {M monomials of R(ǫT , ǫX ) such that ∀ g ∈ G, LT (g) ∤ M }

is a basis of R(ǫT , ǫX ) modulo I(ǫT , ǫX ). By Example 2.3.4, its cardinality
equals to N .
As F is a homogeneous element, the ideal I + ⟨F ⟩ is homogeneous. Let Ĝ be
a Gröbner basis of the ideal I + ⟨F ⟩ that contains G ∪ {F }. Using Proposition
3.0.7 and restricting on each homogeneous component as in Corollary 3.0.8, the
set
̃ T , ǫX ) = {M monomials of R(ǫT , ǫX ) such that ∀ h ∈ G,
̂ LT (h) ∤ M }
∆(ǫ

̃F .
is a basis of R(ǫT , ǫX ) modulo I(ǫT , ǫX ) + ⟨F ⟩(ǫT ,ǫX ) of cardinality N
̂ we have ∆(ǫT , ǫX )F ⊂ ∆(ǫT , ǫX ) ∖ ∆(ǫ
̃ T , ǫX ), from
Since G ⊂ Ĝ and F ∈ G,
which (12) follows.

We conclude the proof noticing that ∆(ǫT , ǫX )F = ∆(ǫT , ǫX )LT(F ) for every
polynomial F and using (11) and (12).

4.2

Explicit formulae of the minimum distance

From now on, let us set ǫX = q + δX and ǫT = q + δ where as usual δ = δT + ηδX .
The hypotheses δX for R(δT , δX ) for R(δT , δX ) for not be zero imply that
ǫT and ǫX are greater than q. By Theorem B, one way to compute a lowerbound of the minimum distance is to calculate #∆(ǫT , ǫX )M for every monomial
M ∈ ∆(δT , δX ) and then minimize the quantity over ∆(δT , δX ).
Proposition 4.2.1. Let (α0 , β0 ) ∈ K(δT , δX ), defined in Notation 2.2.8. Then

#∆(ǫT , ǫX )M(α0 ,β0 ) = max(q − α0 + 1{α0 =δX } , 1) max(q − B(α0 ) + 1{β0 =B(α0 )} , 1)

where B(α0 ) = δ − ηα0 unless

η ≥ 1, δT < 0, η ∣ δT , q ≤ ηδ ,
24

(H)

and (α0 , β0 ) = (A, 0). In this case,

#∆(ǫT , ǫX )M(A,0) = 0.

Proof. Set M = M (α0 , β0 ) = T1δ−ηα0 −β0 T2β0 X1δX −α0 X2α0 with (α0 , β0 ) ∈ K(δT , δX ),
that is to say according to Notation 2.2.8
0 ≤ α0 ≤ min(⌊A⌋, q − 1) or α0 = A,
0 ≤ β0 ≤ min(δ − ηα0 , q) − 1 or β0 = δT + η(δX − α0 ).

Let N ∈ ∆(ǫT , ǫX ). Write
N = T1 T

ǫ +η(ǫX −α)−β

T2β X1ǫX −α X2α ∈ ∆(ǫT , ǫX )

with (α, β) ∈ K(ǫT , ǫX ). Since ǫT , ǫX ≥ q, then

0 ≤ α ≤ q − 1 or α = ǫX ,
0 ≤ β ≤ q − 1 or β = ǫT + η(ǫX − α).

Suppose that M divides N . Then
α0 ≤ α

δX − α0 ≤ ǫX − α
β0 ≤ β

δ − ηα0 − β0 ≤ ǫT + η(ǫX − α) − β
One can rewrite the previous conditions as
α0 ≤ α ≤ q + α0

and

β0 ≤ β ≤ q + η(ǫX − α + α0 ) + β0 .

Since α ≤ ǫX and α0 , β0 ∈ N, both upperbounds are greater than q −1. Moreover,
q + α0 = ǫX ⇔ α0 = δX ,

q + η(ǫX − α + α0 ) + β0 = ǫT + η(ǫX − α) ⇔ β0 = B(α0 ).

To sum up, determining #∆(ǫT , ǫX )M is equivalent to compute the number
of couples (α, β) ∈ K(ǫT , ǫX ) satisfying the following conditions.
{

α0 ≤ α ≤ q − 1
β0 ≤ β ≤ q − 1

or {α = ǫX and α0 = δX }
or {β = ǫT + η(ǫX − α) and β0 = B(α0 )}

(⋆)

Moreover,
• If δX ≥ q and α0 = δX , the only α that satifies (⋆) is α = ǫX .

• If δT + ηδT ≥ q and β0 = δT + ηδT , the only β satifying (⋆) is β = ǫT + ηǫX .

Then, one can write

#∆(ǫT , ǫX )M

⎧
(q − α0 )(q − β0 )
⎪
⎪
⎪
⎪
⎪
(q − α0 ) max(q − B(α0 ) + 1, 1)
=⎨
max(q − δX + 1, 1)(q − β0 )
⎪
⎪
⎪
⎪
⎪
max(q
−
δX + 1, 1) max(q − B(α0 ) + 1, 1)
⎩
25

if
if
if
if

α0
α0
α0
α0

< δX
< δX
= δX
= δX

and
and
and
and

β0
β0
β0
β0

< B(α0 ),
= B(α0 ),
< B(α0 ),
= B(α0 ).

Note that #∆(ǫT , ǫX )M(α0 ,β0 ) can be zero. If
η ≥ 1, δT < 0, η ∣ δT

q ≤ ηδ ,

and

(H)

then there is no couple (α, β) that satisfies (⋆). In any other case, a couple
(α0 , β0 ) ∈ K(δT , δX ) is less or equal to q − 1 or equal to δX . Then either (α0 , β0 )
or (α0 , ǫT + η(ǫX − α0 )) satisfies (⋆).
From now on, we assume that the situation (H) does not hold.
To lowerbound the minimum distance, it remains to minimize
max(q − α0 + 1{α0 =δX } , 1) max(q − β0 + 1{β0 =B(α0 )} , 1)

over (α0 , β0 ) ∈ K(δT , δX ). The problem can be reduced to minimize a univariate
function, thanks to the following lemma.
Lemma 4.2.2. Let η ≥ 0 and (δT , δX ) ∈ Z × N such that δ ≥ 0. Assume that the
situation (H) does not hold. Then
dη (δT , δX ) ≥ min f (α0 )
α0 ∈AX

with AX defined in Notation 2.2.8 and

f (α0 ) = max(q − α0 + 1α0 =δX , 1) max(q − δ + ηα0 + 1, 1)

Proof. By Theorem B, we have to minimize #∆(δT , δX )M(α0 ,β0 ) for (α0 , β0 ) ∈
K(δT , δX ). The only observation we need to prove this lemma is that for each
α0 ∈ AX , for all β ∈ ⟦0, min(B(α0 ), q) − 1⟧,
q − β0 ≥ q − B(α0 ) + 1.

Substituting in the formula of Proposition 4.2.1 gives the desired conclusion.
In other words, Lemma 4.2.2 means that the minimum is reached by monomials of the form M (α0 , δ − ηα0 ) for α0 ∈ AX .

Proposition 4.2.3. Let η ≥ 0, (δT , δX ) ∈ Z × N with δ ≥ 0. Assume that (H)
does not hold. The code Cη (δT , δX ) on the Hirzebruch surface Hη has minimum
distance that is given as follows:
• If η ≥ 1,

– If q > δ, then
dη (δT , δX ) = {

(q + 1δX =0 )(q − δ + 1) if δT ≥ 0 or (δT < 0 and η ≥ 2)
(q − δ)(q + 1)
if δT < 0 and η = 1

δ
– If max ( η+1
, δT ) < q ≤ δ, then

dη (δT , δX ) = q − ⌊
δ
, δT ),
– If q ≤ max ( η+1

δ−q
⌋
η

dη (δT , δX ) = max(q − δX + 1, 1)
26

• if η = 0,

dη (δT , δX ) = max(q − δX + 1, 1) max(q − δT + 1, 1)

We first prove the lower bounding. Equality will follow from Proposition
4.2.4, exhibiting polynomials associated to words of minimum weight.
Proof. By Lemma 4.2.2, we aim to prove the lower bound by minimizing the
function f on AX , the function and the set depending on parameters η, δT , δX
and q.
Let us highlight that AX ⊂ [0, δX ] regardless of parameters.
The form of the function f as a product of two maxima of a linear function
with 1 implies that the real function f ∶ [0, δX ] → R is a concave piecewise
function. The pieces depend on the size of q with respect to the parameters.
More precisely, note that
q − δ + ηα0 + 1 ≤ 1 ⇔ α0 ≤ s

δ−q
has already been defined in Section 2.4.
η
Then f is a piecewise function that has a decreasing linear polynomial on
the interval [0, s] and a concave quadratic function on the interval [s, δX [ with
negative dominant coefficient, provided that s ∈ [0, δX [.
If s ≤ 0, then the function f is quadratic and concave on [0, δX [. Finally, if
s ≥ δX , then f is decreasing on [0, δX [.
Then the minimum point of f on AX is the floor or the ceiling of one the
bound of these intervals.
Let us first suppose that η > 0 and δT ≥ 0. Then
where s =

AX = {

⟦0, δX ⟧
if δX ≤ q
⟦0, q − 1⟧ ∪ {δX } if δX ≥ q

1. If δT + ηδX < q, then s < 0 and q > δX . In this case
f (α0 ) = {

(q − α0 )(q − δ + ηα0 + 1) if α0 ≠ δX ,
(q − δX + 1)(q − δT + 1) if α0 = δX .

• If δX = 0, then AX = {0} and

min f (α0 ) = f (δX ) = (q + 1)(q − δT + 1).

α0 ∈AX

• Otherwise, on the interval [0, δX − 1], the minimum is reached by one
of the bounds of the interval, i.e. α0 = 0 or α0 = δX − 1 (see Fig. 8).
In addition, one can notice that f (δX ) = f (δX − 1) + η(q − δX − 1), i.e.
f (δX ) > f (δX − 1).

The minimum of the function f on AX is reached either by α0 = 0 or
α0 = δX − 1. It remains to compare both values.
We have f (0) ≤ f (δX − 1) if and only if
qηδX ≥ (δX − 1)(q − δT − η + 1) + ηq
27

22
21
20
19
18
17
16
15
14
13
12
11
1 2 3 4 δ5X
Figure 8: Graph of f when q > δ
e.g. (η, δT , δX , q) = (1, 1, 5, 7)
which is equivalent to
q(δX − 1)(η − 1) ≥ −(δX − 1)(δT + η − 1)

(13)

Since η ≥ 1, δT ≥ 0, δX ≥ 1 and q ≥ 2, the left hand side is non negative,
whereas the the right hand side is non positive. The inequation (13)
is thus always satisfied and
min f (α0 ) = f (0) = q(q − δ + 1)

α0 ∈AX

δ
2. If max ( η+1
, δT ) < q ≤ δ, then δX ≥ 1 and ⌊s⌋ ∈ ⟦0, min(δX , q) − 1⟧). In this
case

⎧
(q − α0 )
if α0 ≤ s,
⎪
⎪
⎪
(q − α0 )(η(α0 − s) + 1)
if α0 ≠ δX and α0 ≥ s,
f (α0 ) = ⎨
⎪
⎪
⎪
max(q
−
δ
+
1,
1)(q
−
δ
+
1)
if
α0 = δX .
X
T
⎩

See Figure 9 for examples of graph of the function f .

The possible arguments for the minimum are ⌊s⌋, ⌊s⌋ + 1, min(q, δX ) − 1
and δX .
First notice that ⌊s⌋ ≤ q − 1 and

f (⌊s⌋ + 1) = (q − ⌊s⌋ − 1)(η(⌊s⌋ + 1 − s) + 1

= f (⌊s⌋) − 1 + (q − ⌊s⌋)η(⌊s⌋ + 1 − s).

Therefore

f (⌊s⌋ + 1) ≥ f (⌊s⌋).

(14)

Second let us check that the minimum of f cannot be reached by α0 = δX .
28

9
8
7
6
5
4
3
2
1

9
8
7
6
5
4
3
2
1
1 2 3 4 5 ⌊s⌋ ⌈s⌉ 8 δX

s 2 δX
(b) δX < q
e.g. (η, δT , δX , q) = (1, 3, 3, 5)

(a) δX ≥ q
e.g. (η, δT , δX , q) = (3, 1, 9, 9)

δ
Figure 9: Examples of graph of the function f when max ( η+1
, δT ) < q ≤ δ

• If δX ≤ q, then f (δX ) = f (δX −1)+η(q−δX −1) and f (δX ) > f (δX −1).

• If δX ≥ q, then f (δX ) = η(δX − s) + 1 ≥ η(q − 1 − s) + 1 = f (q − 1).

Then the minimum of f is reached by either α0 = ⌊s⌋ or α0 = min(δX , q)−1.
• If δX ≥ q, we want to prove that f (⌊s⌋) ≤ f (q − 1).
f (q − 1) = η(q − s − 1) + 1

≥ η(q − ⌊s⌋ − 1) + 1
≥ q − ⌊s⌋ + (η − 1)(q − ⌊s⌋ − 1) since ⌊s⌋ ≤ q − 1

≥ q − ⌊s⌋ = f (⌊s⌋)

• If If δX ≤ q, we want to prove that f (⌊s⌋) ≤ f (δX − 1).
Let us assume ⌊s⌋ ≠ δX − 1 and f (⌊s⌋) > f (δX − 1) and let us display
a contradiction.
f (⌊s⌋) > f (δX − 1) ⇔ ⌊s⌋ < δX − 1 − η(δX − 1 − s)(q − δX + 1)
Since the right hand side is an integer, we have
f (⌊s⌋) > f (δX − 1) ⇒ s < δX − 1 − η(δX − 1 − s)(q − δX + 1)
Replacing s by its value, we get
δT
< −1 − η(δX − 1 − s)(q − δX + 1)
η
But the assumption ⌊s⌋ ≠ δX − 1 ensures that δX − 1 > s and then
η(δX − 1 − s)(q − δX + 1) ≥ 0. It is a contradiction with δT ≥ 0.
Then, in both cases,
min f (α0 ) = f (⌊s⌋) = q − ⌊s⌋

α0 ∈AX

29

δ
, δT ), then s ≥ min(δX , q) and
3. if q ≤ max ( η+1

f (α0 ) = max(q − α0 + 1α0 =δX , 1).

This is a decreasing function on [0, δX ], as f (δX − 1) = f (δX ). It follows
easily that
min f (α0 ) = f (δX ) = {

α0 ∈AX

1
q − δX + 1

if q < δX ,
if q ≥ δX .

Now, let us focus on the case η > 0 and δT < 0. Let us recall that
A = ηδ < δX . Since (H) is not satisfied, A never belongs to AX if A ≥ q and then
AX = {
Moreover, s = A −
f (α0 ) = {

q
η

⟦0, ⌊A⌋⟧ if A ≤ q,
⟦0, q − 1⟧ if A ≥ q.

< A. . Since δX ∉ AX , one can rewrite

(q − α0 )(q − η(A − α0 ) + 1) if α0 ≥ s and α0 ≤ q − 1
(q − α0 )
if α0 ≤ s and α0 ≤ q − 1

1. If δ = ηA < q, then s < 0 and AX = ⟦0, ⌊A⌋⟧. Therefore the function f can
be written
f (α0 ) = (q − α0 )(q + η(α0 − A) + 1)
It is increasing then decreasing on AX so its minimum is reached for either
α0 = 0 or α0 = ⌊A⌋. Let us compare f (0) and f (⌊A⌋).
f (0) ≤ f (⌊A⌋) ⇔ ⌊A⌋(q + η(⌊A⌋ − A) + 1) ≤ qη⌊A⌋

• If ⌊A⌋ ≠ 0 we can simplify by ⌊A⌋ and, writing {A} = A − ⌊A⌋, we get
f (0) ≤ f (⌊A⌋) ⇔ 1 − η{A} ≤ q(η − 1)

However, 0 ≤ η{A} ≤ η − 1, which implies that 1 − η{A} ≤ 1 whereas
the right hand-side is a non negative integer. Then the right handside is greater than the left one if and only if it is non zero, which is
equivalent to to η ≥ 2. Then
f (0) ≤ f (⌊A⌋) ⇔ η ≥ 2

Note in addition that if η = 1, then A ∈ N and {A} = A − ⌊A⌋ = 0.
min f (α0 ) = {

α0 ∈AX

q(q − δT + 1)
if η ≥ 2
(q − δT − δX )(q + 1) if η = 1

• If ⌊A⌋ = 0, i.e if δ < η, both formulae above coincide.
2. If

δ
η+1

< q ≤ δ, then

⌊s⌋ ∈ Ax = {

⟦0, ⌊A⌋⟧ if q > A = ηδ ,
⟦0, q − 1⟧ if q ≤ A.
30

19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
1 ⌊s⌋ ⌈s⌉ 4 ⌊A⌋ 6
Figure 10: Graph of f for ηδ < q ≤ δ and η ≥ 2
e.g. (η, δT , δX , q) = (2, −5, 9, 8)
The function f has a linear decreasing piece on [0, s] and then it is concave
on [0, min(⌊A⌋, q − 1)], as illustrated in Figure 9.
Then it can be proved in a same way as in the second case for δT ≥ 0
(Equation (14)) that
f (⌊s⌋ + 1) ≥ f (⌊s⌋).
The minimum of f on AX is thus either reached for α0 = ⌊s⌋ or
• α0 = ⌊A⌋ if q > A,

• α0 = q − 1 if q ≤ A.

Let us prove that the minimum is reached at α0 = ⌊s⌋ in both cases.
• If q > A, let us first notice that, since s < A, we have ⌊s⌋ ≤ ⌊A⌋.
If they are equal, the problem is solved.
Otherwise, one can write that
f (A) = (q − A)(q + 1) > f (⌊s⌋).

Considering f as a fonction on R, it is concave on [⌊s⌋ + 1, A], then
f (⌊A⌋) ≥ f (⌊s + 1⌋) ≥ f (⌊s⌋)
31

• If q ≤ A, we have

f (q − 1) = η(q − 1 − s) + 1 = q − s + (η − 1)(q − 1 − s).

Since the conditions (H) do not occur, we have η ≥ 2.

f (q − 1) = q − s + (η − 1)(q − 1 − s),
η−1
1
q ≤ s,
≥ q − s + (η − 1) (q (1 − ) + 1) since
η
η
q
≥ q − s + ( + 1)
because η ≥ 2,
2
≥q−s+1
because q ≥ 2,
≥ f (⌊s⌋) = q − ⌊s⌋

because s − 1 ≤ ⌊s⌋.

Then, in both cases, min f (α0 ) = f (⌊s⌋) = q − ⌊s⌋.
α0 ∈AX

3. If q ≤

δ
,
η+1

then s ≥ q. For all α ∈ AX = ⟦0, q − 1⟧,
f (α0 ) = max(q − α0 , 1).

Since q − 1 ∈ AX , we have

min f (α0 ) = f (q − 1) = 1

α0 ∈AX

Finally, for η = 0, the expression in the first maximum is a decreasing
function of α0 and the expression in the second maximum does not depend on
α0 anymore. Then
min f (α0 ) = f (δX ) = max(q − δX + 1, 1) max(q − δT + 1, 1)

α0 ∈AX

The following proposition displays some polynomials which codewords has
weight that reaches the lower bound given in Proposition 4.2.3.
Proposition 4.2.4. Write Fq = {ξ1 , ξ2 , . . . , ξq }.
• If η ≥ 1,

– If q > δ, set
F (T1 , T2 , X1 , X2 ) = {

X1δX ∏δi=1 (T2 − ξi T1 )
−δT
T +δX
(T2 − ξi T1 )
X1 X2δX +δT ∏δi=1

if δT ≥ 0 or η ≥ 2
if δT < 0 and η = 1

δ
– If max ( η+1
, δT ) < q ≤ δ, write s = ⌊ δ−q
⌋. Set
η

F (T1 , T2 , X1 , X2 ) = T2 T

δ +η(δX −s)−q

s

η
∏(X2 − ξi T1 X1 ) ∏ (T2 − aT1 )
i=1

32

a∈Fq

δ
, δT ), set mX = min(q, δX ). Set
– If q ≤ max ( η+1
mX

F (T1 , T2 , X1 , X2 ) = X2δX −mX T2δT ∏ (X2 − ξi X1 T1η )
i=1

• if η = 0, set mT = min(q, δT ) and mX = min(q, δX ). Set
mX

mT

i=1

j=1

F (T1 , T2 , X1 , X2 ) = X2δX −mX T2δT −mT ∏ (X2 − ξi X1 T1η ) ∏ (T2 − ξj T1 )
Then the weight of the codeword associated to F in Cη (δT , δX ) reaches the minimum distance.
Proof. We give here the details only for the first case. The others cases are left
to the reader.
Let us assume that q > δ and δT ≥ 0 or η ≥ 2. Then
δ

F (T1 , T2 , X1 , X2 ) = X1δX ∏(T2 − ξi T1 )
i=1

vanishes at every point of the form (1, ξi , x1 , x2 ) or (t1 , t2 , 0, 1), that is to say
at (δ)(q + 1) + q + 1 − δ points.
Let us assume that η = 1, q > δ and δT < 0. The polynomial
δT +δX

F (T1 , T2 , X1 , X2 ) = X1−δT X2δX +δT ∏ (T2 − ξi T1 )
i=1

vanishes at every point of the form (1, ξi , x1 , x2 ), (t1 , t2 , 0, 1) or (t1 , t2 , 1, 0), that
is to say at (δT + δX )(q + 1) + 2(q + 1 − δT − δX ) points.

Remark 4.2.5. The parameters for the code C0 (δT , δX ) on P1 × P1 , are the same
as in [2] (see Theorem 2.1 and Remark 2.2).

5

Upperbound on the number of Fq -rational points
of curves on Hirzebruch surfaces

Proposition 4.2.3 gives an upper bound on the number of Fq -rational points of a
non-filling curve on a Hirzebruch surface Hη . It is worth to highlight that there
exists a filling curve of bidegree (δT , δX ) if and only if q < δ.

Corollary 5.0.1. Let η ≥ 0 and (δT , δX ) ∈ Z × N with δ = δT + ηδX ≥ 0. Assume
that (H) does not hold. Let C be a non-filling curve on the Hirzebruch surface
Hη which Picard class is δT F + δX σ. Then the number of Fq -rational point of
the curve C is upper-bounded as follow.
• If η ≥ 1,

– If q > δ, then

⎧
(q + 1)δT
if δX = 0 and δT ≥ 0,
⎪
⎪
⎪
#C(Fq ) ≤ ⎨ q(δ + 1) + 1 if δX ≠ 0 and (δT ≥ 0 or (δT < 0 and η ≥ 2)),
⎪
⎪
⎪
⎩ (q + 1)(δ + 1) if δT < 0 and η = 1.
33

δ
, δT ) < q ≤ δ, then
– If max ( η+1

#C(Fq ) ≤ q 2 + q + 1 + ⌊

δ−q
⌋.
η

δ
– If q ≤ max ( η+1
, δT ) and q ≥ δX ,

#C(Fq ) ≤ q 2 + q + δX .
• if η = 0,

#C(Fq ) ≤ (q + 1)2 − max(q − δX + 1, 1) max(q − δT + 1, 1).

Moreover each upper bound is reached by Proposition 4.2.4.
These upper bounds cannot be compared to Hasse-Weil bound since the
curves that reach these bounds can be highly reducible and singular, as displayed
in Proposition 4.2.4.

6

Punctured codes

J. P. Hansen [7] and B. L. De La Rosa Navarro and M. Lahyane [5] studied
codes, only on Fq with q big enough so that the evaluation map is injective,
that turn to be punctured codes of our evaluation code Cη (δT , δX ).

In [5], the authors in fact considered a punctured code of Cη (δT , 0) at q + 1
coordinates as the evaluation code of polynomials of bidegree (δT , 0) outside the
fiber F for q ≥ δT . They obtained a quite bad puncturing since here the code
Cη (δT , 0) has parameters [N, k, d] = [(q + 1)2 , δT + 1, (q + 1)(q − δT + 1)] whereas
theirs has parameters [N − (q + 1), k, d − (q + 1)].
Among other toric surfaces, J.P. Hansen studied toric codes on Hirzeburch
surfaces that evaluates polynomials of R(δT , δX ) for δT , δX > 0 only on points
lying on Fq -rational points of the torus G2m for δT , δX > 0 and δT + ηδX < q − 1.
This is the code obtained from puncturing Cη (δT , δX ) at the 4q rational points
of Z(T1 T2 X1 X2 ) = D1 +D2 +E1 +E2 . He obtained a quite good puncturing since
here the code Cη (δT , δX ) has parameters [N, k ′ , d′ ] = [(q+1)2 , (δX +1)(δT +η δ2X +
1), q(q−δT +1)] whereas theirs has parameters [N −4q, k ′, ≤ d′ −(3q−δ−1)]. Note
that, as stated in the introduction, the difference between minimum distances
is at least 2q, the half of the difference between the lengths. The feature can
also be observed when extending Reed-Muller codes to projective Reed-Muller
codes [10].
We highlight here an interesting puncturing of codes Cη (δT , δX ) when δT is
negative, in the sense that all common zero coordinates of codewords and only
them are punctured. Let us define the linear code Cη⋆ (δT , δX ) over Fq obtained
by punctuation of the code Cη (δT , δX ) at the points of Z(X1 ) = D1 .
Theorem 6.0.1. Let η ≥ 1, δT < 0 and δX > 0. The code Cη⋆ (δT , δX ) has length
q(q + 1) and has the same dimension and minimum distance as Cη (δT , δX ).
34

Proof. Every monomial M = T1c1 T2c2 X1d1 X2d2 ∈ R(δT , δX ) on Hη satisfies
0 ≤ c1 + c2 = δT + ηd1 < ηd1 .

Hence d1 > 0 and M is zero on X1 = 0.

Remark 6.0.2. The theorem is true even if the condition (H) holds.
Example 6.0.3. Here are some examples of punctured code F3 , of length 12
that reach the bounds given by code.tables [6].
η
1
1
2
2
2
2

δT
-1
-1
-1
-1
-2
-2

δX
2
3
1
3
2
3

Parameters of Cη⋆ (δT , δX )
[12,3,8]
[12,6,4]
[12,2,9]
[12,10,2]
[12,4,6]
[12,8,3]

References
[1] Cicero Carvalho and Victor G. L. Neumann. Projective Reed-Muller type
codes on rational normal scrolls. Finite Fields Appl., 37:85–107, 2016.
[2] Alain Couvreur and Iwan Duursma. Evaluation codes from smooth quadric
surfaces and twisted Segre varieties. Des. Codes Cryptogr., 66(1-3):291–303,
2013.
[3] David A. Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. Springer, Cham, fourth
edition, 2015. An introduction to computational algebraic geometry and
commutative algebra.
[4] David A. Cox, John B. Little, and Henry K. Schenck. Toric varieties,
volume 124 of Graduate Studies in Mathematics. American Mathematical
Society, Providence, RI, 2011.
[5] Brenda Leticia De La Rosa Navarro and Mustapha Lahyane. Algebraicgeometric codes from rational surfaces. In Algebra for secure and reliable
communication modeling, volume 642 of Contemp. Math., pages 173–180.
Amer. Math. Soc., Providence, RI, 2015.
[6] Markus Grassl. Bounds on the minimum distance of linear codes and
quantum codes. Online available at http://www.codetables.de, 2007.
Accessed on 2018-01-01.
[7] Johan P. Hansen. Toric varieties Hirzebruch surfaces and error-correcting
codes. Appl. Algebra Engrg. Comm. Comput., 13(4):289–300, 2002.
[8] Søren Have Hansen. Error-correcting codes from higher-dimensional varieties. Finite Fields Appl., 7(4):531–552, 2001.
[9] David Joyner. Toric codes over finite fields. Appl. Algebra Engrg. Comm.
Comput., 15(1):63–79, 2004.
35

[10] Gilles Lachaud. The parameters of projective Reed-Muller codes. Discrete
Math., 81(2):217–221, 1990.
[11] Miles Reid. Chapters on algebraic surfaces. In Complex algebraic geometry
(Park City, UT, 1993), volume 3 of IAS/Park City Math. Ser., pages 3–159.
Amer. Math. Soc., Providence, RI, 1997.
[12] Diego Ruano. On the parameters of r-dimensional toric codes. Finite Fields
Appl., 13(4):962–976, 2007.
[13] Bernd Sturmfels. Gröbner bases and convex polytopes, volume 8 of University Lecture Series. American Mathematical Society, Providence, RI,
1996.

36

