5A AM +IJHK?JEI B )IOFJJE?=O /@ +@A 5AGKA?AI

(1)

Some New Constructions of Asymptotically Good Code Sequences

Nils Henry Williams Rasmussen

Master's Thesis in Algebraic Geometry

Department of Mathematics University of Bergen

Norway 30 May 2006

(2)

(3)

Acknowledgements

I rst of all want to thank my advisor, Professor Trygve Johnsen, for introducing me to the eld of algebraic-geometric codes. His suggestions on topics of interest have been most valuable for the way this thesis has developed.

I also want to thank everybody else at Pure Mathematics who have in some way contributed to this thesis.

(4)

(5)

Introduction

1.1 Asymptotic Properties of Codes

Letnbe a positive integer andq a prime power. Aq-ary codeCof lengthnis a nonempty subset ofFⁿ_q with at least two elements. The elements ofC will be called codewords. The distance between two vectorsx= (x₁, . . . , x_n) and y= (y₁, . . . , y_n) is d(x, y) :=|{i∈ {1, . . . , n} |x_i 6=

y_i}|. The weight of a vector xiswt(x) :=d(x,0). The minimum distance ofC is the smallest positive integer d ≤ n such that there exist two elements x, y ∈ C satisfying d(x, y) = d. The dimension of C is k:= log_q(|C|). A q-ary code of length n, dimension k, and minimum distancedis called an[n, k, d]_q code. If it is anF_q-linear subspace ofFⁿ_q, we say thatC is an [n, k, d]_q-linear code. Note that in that case, the minimum distance of C is the same as the minimum weight among the nonzero codewords.

We furthermore dene the relative minimum distanceδ:=d/nand the coderate R:=k/n. In this thesis we will be interested in innite sequences (C_i)^∞_i=1 of codes where the length approaches innity. Given δ∈[0,1], we are interested in nding an innite sequence(C_i)^∞_i=1 of [n_i, k_i, d_i]_q codesC_i with δ = lim inf_i→∞d_i/n_i such that R = lim inf_i→∞k_i/n_i is nonzero.

If the code sequence satiseslim inf_i→∞d_i/n_i 6= 0and lim inf_i→∞k_i/n_i 6= 0, we say that it is asymptotically good.

We deneU_q:={(δ, R)|there exists an innite sequence of [n_i, k_i, d_i]_q codes(C_i)^∞_i=1 with n_i → ∞such that d_i/n_i →δ andk_i/n_i→R}. It is well-known that there exists a continuous functionα_q(δ) such that

U_q ={(δ, R)|0≤R≤α_q(δ)}.

To this date, we only know some upper and lower bounds for this function, but not the exact values of it, except for the points(0,1)and(δ,0)for(q−1)/q ≤δ ≤1. The subject of nding new bounds forα_q(δ) has been the issue of some considerable research throughout the years.

In 1950, the GilbertVarshamov bound was found. It states that α_q(δ)≥R_GV := 1−H_q(δ),

where

H_q(δ) =δlog_q(q−1)−δlog_q(δ)−(1−δ) log_q(1−δ)

is the q-ary entropy function. For δ close to 0 and close to (q−1)/q, this is still the best bound known to this date. The bound was not improved until 1982.

7

(8)

The 1982 improvementknown as the TsfasmanVladuµZink boundwas due to the discovery of algebraic-geometric codes dened in 1981 by V.D. Goppa. LetXbe a nonsingular, projective curve dened over F_q, and let n be a positive integer less than or equal to the number ofF_q-rational points onX. Let P₁, . . . , P_n beF_q-rational points onX, and let Gbe anF_q-rational divisor with support disjoint from {P₁, . . . , P_n}. Dene the mapping

ψ:L(G) −→ Fⁿ_q

f 7−→ (f(P₁), . . . , f(P_n)).

We call the image of this mapping a Goppa code. The 1982 improvement used an innite sequence of curves with a large number of F_q-rational points, and a Goppa code was dened on each curve. The length of the code was equal to the number of F_q-rational points on the curve in question. This resulted in the bound

α_q(δ)≥R_TVZ:= 1−δ− 1

√q−1,

given thatqis a square prime power. Forq ≥49, this became an improvement of the Gilbert Varshamov bound forδclose toq/(2(q−1)). For larger values ofq, the interval of improvement increases.

To my knowledge, the TsfasmanVladuµZink bound wasn't improved until 2001, when Chaoping Xing found good divisors G on X which increased the minimum distance of the Goppa codes around the areas whereR_TVZ and R_GV intersect. In 2003, Xing found a fur- ther improvement using nonlinear codes dened over algebraic curves, which was a linear improvement of the TsfasmanVladuµZink bound. That same year, Elkies found another linear improvement, which to this date is still the best one. It is given by

α_q(δ)≥1−δ− 1

√q−1 + log_q

1 + 1 q³

for square prime powersq.

In this thesis, I have given a presentation of how all these results have been found. I open with the classical bounds, such as the upper Plotkin bound and the GilbertVarshamov bound. All this is in Chapter 2. The following chapter presents theory about algebraic curves over nite elds which is used throughout the entire rest of this thesis. Chapter 3 concludes with the RiemannRoch theorem for curves over nite elds.

Chapter 4 presents the construction of Goppa codes and closes with a code sequence found by Chaoping Xing in 2005 that shows that Goppa codes attain the asymptotic Gilbert Varshamov bound. In Chapter 5 we get to see how these codes can be used to nd the TsfasmanVladuµZink bound. In Chapter 6 I present the two improvements found in 2003.

Before presenting my own work and results, I also touch three other subjects concerning special kinds of codes. Stichtenoth discovered in 2005 that transitive codes meet Elkies's 2003 bound. A natural question to ask is then whether transitive codes are as asymptotically good as codes in general, which today is still unanswered. An outline of Stichtenoth's construction is presented in Chapter 7.

The second subject I touch is the asymptotic properties of frameproof codes, which Chaop- ing Xing found a new lower bound for in 2002. The reason why I have included a chapter of frameproof codes in this thesis, is that any linear code is also a frameproof code, and so it

(9)

1.2 Generalised Algebraic-Geometric Codes 9 follows that all asymptotic results we have obtained for linear codes so far in my thesis also apply for frameproof codes. All of this we nd in Chapter 8.

Finally, I present some other possible constructions of codes from algebraic geometry, found by Xing, Niederreiter, and Lam. Such work has been important when it comes to improvements of the TsfasmanVladuµZink bound, since both 2003 improvements were made by codes dierent from Goppa codes. However, some constructions have proved to give the same codes as the Goppa construction gives us. In Chapter 9 I give two cases where the codes turn out to be Goppa codes and one case where they don't, which I take a closer look at in the last two chapters.

1.2 Generalised Algebraic-Geometric Codes

The code construction presented in the end of Chapter 9 denes a generalisation of the Goppa codes and was found in 1999 by Xing, Niederreiter, and Lam. In short, with notations as before, it involves evaluating the functions ofL(G)in closed points of higher degree on the curve X. Ifsis a positive integer andP₁, . . . , P_sare closed points of degreek₁, . . . , k_s, respectively, let C₁, . . . , C_s be[n_i, k_i, d_i]_q-linear codes, respectively, wheren₁, . . . , n_s are positive integers. Let Gbe an F_q-rational divisor with support disjoint from{P₁, . . . , P_s}. If f ∈L(G), thenf(P_i) is an element inF_q_ki,0≤i≤s. Dene isomorphisms φ_i :F_q_ki −→C_i. Letn=n₁+· · ·+n_s. Dene the mapping

φ:L(G) −→ Fⁿ_q

f 7−→ (φ₁(f(P₁)), . . . , φ_s(f(P_s))).

We call the image ofφa generalised algebraic-geometric code.

It is obvious that this is a generalisation of the Goppa codes. A natural question to ask is whether constructions involving Goppa codes can be generalised to involve generalised algebraic-geometric codes. I have made two attempts of this in Chapter 10. The rst construction, presented in Section 10.1, involves using all points of degree 1 and 2 on the curves of an innite curve sequence with manyF_q2-rational points. The codesC₁, . . . , C_sare all[1,1,1]_q and[2,2,1]_q codes. This has given the rather pleasing result

R≥R₁:= 1−2δ− 1 q−1,

for any prime powerq. This is not a good bound for large values of δ, but for small values, this comes very close to the GilbertVarshamov bound.

Another idea I have tried out, is letting C₁, . . . , C_s be asymptotically good codes, the lengths of which approach innity as the length ofC approaches innity. Such a construction is given in Section 10.3. It appears that this also gives us an asymptotically good code sequence, but not as good asR₁ except for large values of δ.

For the sake of completeness, I have also included a construction made by Antonino Spera, presented as R₂ in Section 10.2, which is interesting because it doesn't demand a curve sequence, but only one single curve.

Improvements made on Goppa codes should also be possible to make on generalised algebraic-geometric codes. Xing's 2001 improvement using good divisors G was a natural start, since it improves the codes for small values of δ, and it was very tempting to try and

(10)

improveR₁ around the areas where it is closest to the GilbertVarshamov bound. The at- tempt produced a successful result, although the improvement is not enough to reach the GilbertVarshamov bound. It is all presented in Section 11.1.

It is an open question whether other improvements made on Goppa codes can also be made on generalised algebraic-geometric codes. One such question is presented in the end of Chapter 11.

(11)

Chapter 2

Bounds on Codes

In this chapter I present the classical upper and lower bounds on codes, concluding with the 1950 GilbertVarshamov bound. I begin by introducing some notation and important facts.

Throughout this chapter, when we are given a code C and nothing else is mentioned, the minimum distance ofC will be assumed to bed, the dimension will be k, the code length n, the relative minimum distanceδ, and the number of codewordsM.

Most of this material is taken from [10], pp. 2537.

Denition 2.1. Let q be a prime power. We dene V_q := {(δ, R) ∈ [0,1]²|there exists an [n, k, d]_q-code with _n^d =δ and ^k_n =R}. U_q is the set of points (δ, R) such that there exists an innite sequence of codes(C_i)^∞_i=1 with minimum distanced_i, dimensionk_i, and length n_i such that n_i→ ∞ and

i→∞lim(d_i/n_i, k_i/n_i) = (δ, R).

If δ, R >0, then we say that the code sequence is asymptotically good.

Proposition 2.2. Letqbe a prime power. There exists a continuous functionα_q(δ), δ∈[0,1], such that

U_q ={(δ, R)|0≤R≤α_q(δ)}.

Moreover, α_q(0) = 1, and α_q(δ) = 0 for ^q−1_q ≤δ ≤1. We also have that α_q(δ) decreases in the interval[0,^q−1_q ].

Proof. See Theorem 1.3.1 in [13].

Note that this function is of the form α_q(δ) = sup{R|(δ, R) ∈ U_q}. This proposition is also valid if we restrict U_q to only apply for linear codes. We then denote the function by α^lin_q (δ).

Theorem 2.3 (the Singleton Bound). Letq be a prime power and n, k, dpositive integers.

If C is an [n, k, d]_q code, then

k≤n−d+ 1.

Proof. Suppose C has minimum distance d. For each codeword (x₁, . . . , x_n), delete the last d−1elementsx_n−d+2, . . . , x_n such that we are left with(x₁, . . . , x_n−d+1). Then all the words are still dierent from one another, or else the minimum distance would be strictly less than d. Now we have a code C⁰ of length n−d+ 1 and the same number of words as in C. We haveq^k=|C|=|C⁰| ≤q^n−d+1, sok≤n−d+ 1.

11

(12)

Corollary 2.4 (the Asymptotic Singleton Bound). Let q be a prime power. We have that

α_q(δ)≤1−δ.

Proof. Sincek≤n−d+ 1, dividing bynon both sides yieldsR≤1−δ+_n¹. Lettingn→ ∞, we getα_q(δ)≤1−δ.

Theorem 2.5 (the Plotkin Bound, 1960). Letq be a prime power. For any[n, k, d]_q-code, we have

d≤ nq^k(q−1) (q^k−1)q .

Proof. The average distance of all pairs of codewords can't be less than the minimum distance d. LetM =q^k, the number of codewords in C. The number of all ordered pairs of codewords isM(M−1). Then

d≤ 1

M(M −1) X

x,y∈C

d(x, y).

Ifx is inC, denote it by(x₁, . . . , x_n). Set m_i,a=|{x∈C|x_i =a}|. It is clear that X

a∈F^q

m_i,a=M

for anyi∈ {1, . . . , n}. Let δ_a,b= 1 ifa=band δ_a,b= 0 if a6=b. We have M(M −1)d ≤ X

x,y∈C

d(x, y) = Xn

i=1

X

x,y∈C

(1−δ_x_i_,y_i)

= Xn

i=1

X

a,b∈F^q

(1−δ_a,b)m_i,am_i,b = Xn

i=1







X

a∈Fq

m_i,a





2

−X

a∈Fq

m²_i,a





= Xn

i=1



M²− X

a∈Fq

m²_i,a



≤ Xn

i=1



M²−1 q



X

a∈Fq

m_i,a





2



= nq−1 q M².

The last inequality follows from the CauchySchwartz inequality: In general,



X

a∈F^q

x_ay_a





2

≤



X

a∈F^q

x²_a







X

a∈F^q

y_a²



.

The results in the calculations follow when we put each y_a = 1 and each x_a = m_i,a. This completes the proof.

Corollary 2.6 (the Asymptotic Plotkin Bound). Let q be a prime power. We have α_q(δ) = 0 for q−1

q < δ≤1 and

α_q(δ)≤R_P(δ) := 1− q

q−1δ for 0≤δ ≤ q−1 q .

(13)

13 Proof. Whend > n^q−1_q , then Theorem 2.5 gives us

d ≤ nq^k(q−1) q(q^k−1) q^kn(q−1) ≥ dqq^k−dq q^k(n(q−1)−dq) ≥ −dq q^k(dq−n(q−1)) ≤ dq

M =q^k ≤ dq

dq−n(q−1) = d

d−n^q−1_q . (2.1)

Now, if we xδ = ^d_n, the expression on the right remains constant for varying n. If we take logarithms on both sides, divide bynon both sides, and letn→ ∞, we get 0 on the right-hand side, and so ^k_n =R goes to 0 as well, proving the rst part of the corollary.

In order to prove the second part, we must construct a codeC⁰ of lengthn⁰ small enough so thatd > n⁰^q−1_q . Assume0≤δ≤ ^q−1_q and dene

n⁰=

(d−1)q q−1

. Thenn⁰ < n, since

(d−1)q q−1

≤ (d−1)q

q−1 ≤ d−1 δ < n.

Also, it is clear thatd > n⁰^q−1_q , since n⁰·q−1

q =

(d−1)q q−1

·q−1

q ≤ (d−1)q

q−1 ·q−1

q =d−1< d.

So given a code C⁰ with word length n⁰ and minimum distance d, we are allowed to apply (2.1).

We dene C⁰ the following way: Consider then−n⁰ last symbols of the codewords ofC and consider the dierent subsets of words ending in the samen−n⁰ symbols. Then one of these subsets hasM⁰ elements where

M⁰≥ M

qⁿ⁻ⁿ⁰ =qⁿ⁰^−n+k,

or else we would haveM < qⁿ⁰^−n+k·qⁿ⁻ⁿ⁰ =q^k, a contradiction. We let C⁰ consist of these M⁰ words. We have from (2.1) that

M

qⁿ⁻ⁿ⁰ ≤M⁰ ≤ d

d−n⁰^q−1_q ≤d. (2.2)

The last inequality follows because d−n⁰q−1

q ≥d−(d−1)q

q−1 ·q−1

q =d−(d−1) = 1.

Rewrite (2.2) asqⁿ⁰⁻ⁿM ≤M⁰ ≤d.

(14)

Letd=bδnc and n >>0. Then we have qⁿ⁰^−n+k ≤ bδnc

(d−1)q q−1

−n+k ≤ log_qbδnc k ≤ n−

(d−1)q q−1

+ log_qbδnc< n−(d−1)q

q−1 + 1 + log_qbδnc k < n−bδncq

q−1 + q

q−1+ 1 + log_qbδnc k < n−(δn−1)q

q−1 + q

q−1 + 1 + log_qbδnc R < 1− δq

q−1 + 2q

n(q−1)+ 1

n +log_qbδnc n α_q(δ) ≤ 1− δq

q−1. This nishes the proof.

Lemma 2.7. Letq be a prime power,n, dpositive integers, andC a code of lengthnoverF_q, and suppose that any word with distance at leastd to all words inC is also inC. Then

|C|

Xd−1

i=0

n i

(q−1)ⁱ ≥qⁿ. Proof. Suppose that

|C|

Xd−1

i=0

n i

(q−1)ⁱ < qⁿ.

That means that when we take ad−1ball around each codeword, there is some wordxinFⁿ_q that is not covered. Thenxhas distance at leastdto all codewords inC, a contradiction.

Theorem 2.8 (the GilbertVarshamov Bound, 1950). Let q be a prime power, n, k, d positive integers. If

q^n−k+1>

d−1X

i=0

n i

(q−1)ⁱ, then there exists an [n, k, d]_q-linear code over F_q.

Proof. We induct on k. For k = 1, the theorem is trivial, since it is possible to make a 1- dimensional code with any minimum distanced ∈ {1, . . . , n}. Suppose the inequality holds forn, k−1, d, that there exists an[n, k−1, d]_q-linear code C overF_q, and that the inequality also holds for n, k, d. We shall try to construct an [n, k, d]_q-linear code from C. We rewrite the inequality as

qⁿ> q^k−1 Xd−1

i=0

n i

(q−1)ⁱ.

Then, according to the previous lemma, there exists a wordx⁰∈/ C with distance at leastdto each word inC. We want to show that if we expandC withx⁰, then all words in the code will

(15)

15 still have weight at leastd. It will then follow that the minimum distance is stilld. Suppose x∈C and α∈F_q\ {0}. Then

wt(x+αx⁰) = wt(α⁻¹x+x⁰) =d(−α⁻¹x, x⁰)≥d.

This completes the proof.

Before nding the asymptotic GilbertVarshamov bound, we will need some results concerning the entropy function, which will also be used a lot throughout this thesis.

Denition 2.9 (the q-ary Entropy Function). Let q be a positive integer and δ a real number satisfying 0< δ≤ ^q−1_q . Then we have

H_q(δ) :=δlog_q(q−1)−δlog_q(δ)−(1−δ) log_q(1−δ), H_q(0) := 0.

Theorem 2.10 (Stirling's Formula). Letq, n be positive integers. Then log_q(n!) =nlog_q(n)−n+O(log_qn).

Lemma 2.11. If q, n are positive integers and t is a nonnegative integer such that 0 ≤ t≤

(q−1)n

q , then the last term in

Xt

i=0

n i

(q−1)ⁱ is the largest.

Proof. Letθ≤ ^(q−1)n_q . We then have n!

θ!(n−θ)!(q−1)^θ− n!

(θ−1)!(n−θ+ 1)!(q−1)^θ−1 ≥ 0 m n!(q−1)^θ(n−θ+ 1)−n!(q−1)^θ−1θ

θ!(n−θ+ 1)! ≥ 0

m n!(q−1)^θ−1((q−1)(n−θ+ 1)−θ) ≥ 0

m (q−1)(n−θ+ 1) ≥ θ

m

q(n+ 1)−n−1 ≥ θq m

θ ≤ q(n+ 1)−n−1 q

m

θ ≤ (q−1)n+q−1

q ,

which is true.

(16)

Lemma 2.12. Letq, n be positive integers,ta nonnegative integer satisfying 0≤t≤ ^(q−1)n_q . Then

n⁻¹log_q Xt

i=0

n i

(q−1)ⁱ

!

=H_q t

n

+o(1).

Note that this is equivalent with stating that

n→∞lim n⁻¹log_q Xt

i=0

n i

(q−1)ⁱ

!

= lim

n→∞H_q t

n

.

Proof. From Lemma 2.11, we know that sincet≤ ^(q−1)n_q , then the last term in Xt

i=0

n i

(q−1)ⁱ

is the largest. That means that when we multiply that term with the number of terms in the sum, we get a larger number than the sum gives us:

n t

(q−1)^t≤ Xt

i=0

n i

(q−1)ⁱ≤(t+ 1) n

t

(q−1)^t. The left-hand side of this inequality gives us

n⁻¹log_q Xt

i=0

n i

(q−1)ⁱ

!

≥n⁻¹log_q n

t

+n⁻¹log_q(q−1)^t

=n⁻¹log_q

n!

t!(n−t)!

=n⁻¹ log_q(n!)−log_q(t!)−log_q(n−t)!

=n⁻¹

nlog_q(n)−n+O(log_q(n))

−tlog_q(t) +t−O(log_q(t))

−(n−t) log_q(n−t) + (n−t)−O(log_q(n−t))

= t

nlog_q(q−1) + log_q(n)− t

nlog_q(t)

−

1− t n

log_q

n

1− t

n

+o(1)

= t

nlog_q(q−1)− t

nlog_q(t) + t

nlog_q(n)

−

1− t n

log_q

1− t

n

+o(1)

(17)

17

= t

nlog_q(q−1)− t nlog_q

t n

−

1− t n

log_q

1− t

n

+o(1)

=H_q t

n

+o(1).

The right-hand side of the inequality gives us n⁻¹log_q

Xt

i=0

n i

(q−1)ⁱ

!

≤n⁻¹log_q(t+ 1) +n⁻¹log_q n

t

+n⁻¹log_q(q−1)^t. The rst term iso(1), and the rest of the expression is the same as when we took logarithms of the left-hand side of the inequality and divided byn. Equality follows.

Corollary 2.13 (the Asymptotic GilbertVarshamov Bound). Letq be a prime power.

We then have

α^lin_q (δ)≥R_GV(δ) := 1−H_q(δ).

Proof. Suppose we have positive integersn, k, dsatisfying

|C| ·

d−1X

i=0

n i

(q−1)ⁱ> qⁿ.

Then, according to Theorem 2.8, there exists an[n, k, d]_q-linear code. Taking logarithms on both sides and dividing byn, we obtain

R+n⁻¹log_q Xd−1

i=0

n i

(q−1)ⁱ >1.

Lettingn→ ∞, we get

α^lin_q (δ)≥1− lim

n→∞ n⁻¹

d−1X

i=0

n i

(q−1)ⁱ

!

= 1−H_q(δ).

The last equality follows from Lemma 2.12.

(18)

(19)

Chapter 3

Curves over Finite Fields

Before presenting the denition of Goppa codes and the TsfasmanVladuµZink bound, we will need some results from algebraic curves dened over nite elds, which I present in this chapter. We start by dening what is meant by a curve dened overF_q for q a prime power, and what is meant byF_q-rational points andF_q-rational divisors. I conclude this chapter by proving that the RiemannRoch theorem is valid for curves over nite elds.

The entire material is taken from [10], pages 103109, except for Proposition 3.8, which is taken from Proposition 2.3.4, page 173 in [13].

Throughout this chapter,k=F_q will denote a nite eld, andk⁰ will denote the closure of k. X will be assumed to be a non-singular, projective curve dened overk, i.e. its prime ideal p(X) has a basis{F₁, . . . , F_r} where eachF_i has coecients ink. A point x= (x₀, . . . , x_n)∈ Pⁿ_k0 will be calledk-rational if for all i,x_i 6= 0 ⇒ x_j/x_i∈k, j= 0, . . . , r. The Galois group of k⁰overkwill be denoted byGal(k⁰/k). The elementσ ∈Gal(k⁰/k)we dene asσ(x_i) :=x^q_i, the Frobenius automorphism ofX. Ifx= (x₀, . . . , x_n), then we deneσ(x) := (σ(x₀), . . . , σ(x_n)). LetΓ_k(X) be the coordinate ring of X over k. Thenf =F/G∈k⁰(X)will be dened to bek-rational if F, G∈Γ_k(X) and G6= 0 inΓ_k(X). The eld k(X) will denote the set of all k-rational functions in k⁰(X). Div⁰(X) denotes the set of all divisors onX. Pic⁰(X) denotes the set of all equivalence classes of divisors onX. If D∈Div⁰(X), then we letD denote the corresponding equivalence class. A closed point on X over k will be assumed to be a pair (O_v,m_v), where v is a discrete valuation of k(X) and O_v is the associated DVR over k with maximal idealm_v.

Ifx = (x₀, . . . , x_n) is a point on X such that x_i = 1for some i= 0, . . . , n, then k(x) will denote the eld extension ofkgenerated by the coordinates of x.

Denition 3.1. LetD∈Div⁰(X),D=P

n_xx. Letσ(D) :=P

n_xσ(x). ThenDis dened to be k-rational if σ(D) =D. We denote the set of all such divisors by Div(X). An equivalence classD∈Pic⁰(X)is dened to be k-rational if it contains at least onek-rational divisor. The set of such equivalence classes is denoted byPic(X).

Proposition 3.2. Suppose x is a point on X over k⁰. Suppose k(x) =F_q^ν for some positive integerν. Then x, σ(x), . . . , σ^ν−1(x) are all distinct andσ^ν(x) =x.

Proof. We can assume that x = (1, x₁, . . . , x_n) by rst making a change of coordinates if necessary. Ifσⁱ(x) =σ^j(x) for 0≤i < j ≤ν−1, then σ^j−i(x_s) =x_s for s= 1, . . . , n. Then x₁, x₂, . . . , x_n ∈F_qj−i. Sincex₁, . . . , x_n were also assumed to generateF_q^ν from F_q, it follows thatF_q^ν ⊆F_q^j−i, a contradiction.

19

(20)

σ^ν(x) = x follows directly from the fact that each element x₁, . . . , x_n is in F_q^ν and the denitionσ(x_i) =x^q_i.

Denition 3.3. Letx be a point onX overk⁰. A k-rational divisorP is dened to be prime if it is of the form

P =P_x= Xν

i=1

σⁱ⁻¹(x),

whereν is the degree of x over k. The points σⁱ⁻¹(x) are called the components of P.

Proposition 3.4. A divisor D ∈ Div⁰(X) is k-rational if and only if it can be written as D = P

P a_PP, where all the P are prime divisors, a_P ∈ Z, and a_P 6= 0 for only a nite number ofP.

Proof. Suppose D = P

Pa_PP, where all the P are prime divisors, a_P ∈ Z, and a_P 6= 0 for only a nite number ofP. Then clearly,σ(D) =σ(P

a_PP) =P

a_Pσ(P) =P a_PP. Conversely, ifD=P

xa_xx isk-rational, letν be a common multiple for the degrees of all the componentsx. Thenσ^ν(x) =xfor allxandD=σ(D) =σ²(D) =· · ·=σ^ν−1(D). Now, if we put in the expression forDin this equation, we getP

xa_xx=σ(P

xa_xx) =σ²(P

xa_xx) =

· · · = σ^ν−1(P

xa_xx) ⇒ P

xa_xx = P

xa_xσ(x) = P

xa_xσ²(x) = · · · = P

xa_xσ^ν−1(x). This shows that for any given x, the coecient of x, σ(x), . . . , σ^ν−1(x) are the same. Since [k(x) :k]dividesν, we can put x+σ(x) +· · ·+σ^ν−1(x) =b_xP_x, whereb_x is an integer andP_x is the prime divisor associated withx, and soD=P

Pxa_xb_xP_x=P

Pc_PP, as desired.

Denition 3.5. Dene two pointsx andy to be equivalent ify=σ^s(x)for some nonnegative integers. We denote the equivalence class of x by x.

Proposition 3.6. Let f ∈ k⁰(X). Then div(f) is k-rational if and only if f ∈ k(X), up to multiplication by constants.

Proof. Supposef ∈k(X) and letdiv(f) =P

xv_x(f)·x, wherev_x(f) is the valuation off in x. Now, ifx is a point andσⁱ(x) =y, then sincef isk-rational, we have thatv_x(f) =v_y(f). It follows that

div(f) = X

x

v_x(f)·(x+σ(x) +· · ·+σ^ν^x⁻¹(x))

= X

x

v_x(f)·P_x,

whereν_x= [k(x) :k]. It follows by Proposition 3.4 that div(f) isk-rational.

Conversely, supposediv(f) =P

xv_x(f)·xis ak-rational divisor,f =F/G∈k⁰(X),G6= 0 inΓ_k⁰(X). Since div(f) is k-rational, then if the point x is a zero in F, then σⁱ(x) is also a zero. Proposition 3.4 gives that the zeros have the same multiplicity. The same goes for G. It follows thatF, G∈Γ_k(X), and so f ∈k(X).

Denition 3.7. Let L⁰(D) = {f ∈ k⁰(X)\ {0} |div(f) +D 0} ∪ {0}. Then we dene L(D) :=L⁰(D)∩k(X). The dimension of L⁰(D) as a vector space over k⁰ isl⁰(D), andl(D) is the dimension ofL(D) as a vector space over k.

Proposition 3.8. LetDbe a k-rational divisor onX. ThenL(D) andL⁰(D)have a common basis. In particular, l(D) =l⁰(D).

(21)

21 Proof. Let

L⁰(D) = Mm

i=1

f_i·k⁰.

Letk⁰⁰ be a nite extension of k so that f₁, . . . , f_m ∈k⁰⁰(X). Let {α₁, . . . , α_ν} be a basis for k⁰⁰as a vector space overk. Then the Galois groupGal(k⁰⁰/k)consists ofν elements with the Frobenius homomorphism as generator, and we have from Proposition 3.2 thatGal(k⁰⁰/k) = {σ, . . . , σ^ν}.

Dene

g_i,j = Xν

s=1

σ^s(α_j·f_i) = Xν

s=1

σ^s(α_j)·σ^s(f_i).

We show that g_1,1, . . . , g_1,ν, . . . , g_m,ν ∈k(X) and generate L⁰(D). Then anm-subset of these will be a basis forL⁰(D), and they will hence also be a basis forL(D).

First of all, if β ∈ k⁰⁰, it follows that σ(β) +· · ·+σ^ν(β) ∈ k. (Proof: σ, . . . , σ^ν take the element β₁ to all of its (not necessarily distinct) conjugates β₂, . . . , β_ν. So β₁+· · ·+β_ν = σ(β₁) +· · ·+σ^ν(β₁). Also, there exists a polynomial with coecients in k that factors as (x−β₁)(x−β₂)· · ·(x−β_ν). The coecient of x^ν−1 in this polynomial isβ₁+β₂+· · ·+β_ν, but since the polynomial has coecients ink, thenβ₁+β₂+· · ·+β_ν must be ink.) It follows that given an elementf ∈k⁰⁰(X), thenσ(f) +· · ·+σ^ν(f)∈k(X).

To prove thatg_1,1, . . . , g_1,ν, . . . , g_m,ν generateL⁰(D), note that the matrix

G =







σ(α₁) σ²(α₁) . . . σ^ν(α₁) σ(α₂) σ²(α₂) . . . σ^ν(α₂)

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

σ(α_ν) σ²(α_ν) . . . σ^ν(α_ν)







by standard Galois theory has nonzero determinant, so the elementsP

sσ^s(α₁·f₁),P

sσ^s(α₂· f₁), . . . ,P

sσ^s(α_ν ·f₁) are linearly independent for eachf_i. Also, for eachα_j, we get linearly independent elements if we vary thef_i. So we only need to show that each div(g_i,j) +D0. To show this, it suces to show that f ∈L⁰(D) ⇒ σ(f) ∈L⁰(D), since then g_i,j will be nothing more than a linear combination of elements fromL⁰(D). We will here use the property thatDis ak-rational divisor. But rst we show that σ(div(f)) = div(σ(f)).

Note that for a point x, we have that σ is a ringhomomorphism from O_x to O_σ(x). If ord_x(f) =n≥0 andm_x is the maximal ideal in the associated DVRO_x, thenf ∈mⁿ_x/mⁿ⁺¹_x . Ifh is an element that generates m_x, then this means thathⁿ is the highest power of h that divides f in O_x. We write f =hⁿ·f⁰, where f⁰ is a unit in O_x. Then σ(f) = σ(h)ⁿ·σ(f⁰). We have h(x) = 0. Taking σ(h) and evaluating it in σ(x) gives σ(h(x)) = σ(0) = 0. It is clear thatσ(f⁰) is a unit, sinceσ(f⁰⁻¹)is its inverse. Then σ(h) generates the maximal ideal m_σ(x) in the DVR O_σ(x), and it follows that ord_σ(x)(σ(f)) = n. A similar argument applies for negative orders. It follows thatσ(div(f)) = div(σ(f)).

Suppose now that div(f_i) +D 0. Then σ(div(f_i)) +σ(D) 0. Since σ(D) =D, the above result gives usdiv(σ(f_i)) +D0, as desired.

Proposition 3.9. LetK be a canonical divisor. Then K contains ak-rational element.

Proof. Choose anf ∈k(X) such thatdf 6= 0. Thendf will also have coecients in k. The rest of the proof is now identical of the proof in Proposition 3.6.

(22)

Corollary 3.10. Let K be a k-rational canonical divisor. Then l(K) =l⁰(K).

Corollary 3.11 (the RiemannRoch Theorem). Let D be a k-rational divisor, K a rational canonical divisor. Then

l(D) = deg(D) + 1−g+l(K−D).

(23)

Chapter 4

Goppa Codes

In this chapter I present the construction of Goppa codes. This construction was discovered by V.D. Goppa in 1981 and is based on curves over nite elds. It is this construction that Tsfasman, Vladuµ, and Zink used when they managed to improve the asymptotic Gilbert Varshamov bound in 1982.

I begin this chapter by giving the basic denitions and results concerning Goppa codes.

I will then give two examples of how to construct such codes. I conclude this chapter by presenting an innite sequence of Goppa codes that attains the GilbertVarshamov bound, made by Chaoping Xing in 2005.

The material in Section 4.1 of this chapter is taken from [14]. The example of the Hermite curve in Section 4.2 can be found on page 62 of [14]. Section 4.3 is a presentation of [18].

Throughout this chapter, X will always be assumed to be a non-singular projective curve dened overF_q. The divisorsD, G, G^∗; constantsd, k, n, d^∗, k^∗; and mapsα, α^∗, β^∗will always be assumed to be as dened in Denition 4.1, Proposition 4.2, Denition 4.6, and Deni- tion 4.13, unless specied otherwise. The genus of the curve X shall always be denoted by g. The eld of rational functions onX with coecients inF_q will be denoted by F_q(X). The set ofF_q-rational points on X will be denoted byX(F_q), and its cardinality by |X(F_q)|. The discrete valuation ring overF_q at the closed pointP will be denoted byO_P.

All divisors and closed points will in this chapter be assumed to be F_q-rational unless stated otherwise.

4.1 Denitions

Denition 4.1. Let P₁, . . . , P_n be distinct points of X of degree 1 over F_q and let D = P₁+· · ·+P_n be a divisor. Let Gbe a divisor satisfying Supp(G)∩Supp(D) =∅. Dene the linear mapα:L(G)−→Fⁿ_q by

f 7−→(f(P₁), . . . , f(P_n)).

Then the image of the map denes a linear codeC(D, G) called a Goppa code.

Proposition 4.2. For a Goppa code C(D, G), we have dimension k=l(G)−l(G−D) and minimum distance d≥n−deg(G).

Proof. We haveC(D, G)∼=L(G)/ker(α), so we must show thatker(α) =L(G−D). Suppose f ∈ ker(α). Thenf(P_i) = 0, i= 1, . . . , n, so div(f) D. Thus, f ∈L(G−D). Conversely,

23

(24)

suppose f ∈ L(G−D). Then div(f) D since P_i ⊀ G, i = 1, . . . , n. It follows that f(P_i) = 0, i= 1, . . . , n.

To show thatd≥n−deg(G), suppose the Hamming weight ofα(f)isd. This means that f(P_i) = 0forn−dpoints among theP_i, sayP_i₁, . . . , P_i_n−d. Thenf ∈L(G−P_i₁− · · · −P_i_n−d), and div(f) + G−P_i₁ − · · · −P_i_n−d 0. Taking degrees on both sides and noting that deg(div(f)) = 0, we getdeg(G)−(n−d)≥0, sod≥n−deg(G).

Remark 4.3. The last part of this proposition is only useful ifn−deg(G)≥2, since d≥1 always.

Corollary 4.4. Ifdeg(G)< n, then α is an injection and k=l(G).

Denition 4.5. LetE be a divisor. Then we dene the vector space Ω(E) as follows.

Ω(E) ={ω|ω is a rational dierential form with div(ω)E} ∪ {0}.

Denition 4.6. Dene the linear mapα^∗: Ω(G−D)−→Fⁿ_q by η7−→(res_P₁(η), . . . ,res_P_n(η)).

Then the image of the map denes a linear codeC^∗(D, G) of length n.

Proposition 4.7. Let ω be a rational dierential form, div(ω) = K. Dene a map β^∗ : L(K+D−G)−→Fⁿ_q by

f 7−→(res_P₁(f ω), . . . ,res_P_n(f ω)).

Then the image ofβ^∗ is the same as the image of α^∗.

Proof. Suppose(res_P₁(η), . . . ,res_P_n(η))∈C^∗(D, G). Sinceη is a rational dierential form, we can write it asf ω for some f ∈F_q(X). We then have f ω∈Ω(G−D), sodiv(f) + div(ω) = div(f) +KG−D. That is equivalent withdiv(f)∈L(K+D−G).

Proposition 4.8. For a codeC^∗(D, G), we have dimension k^∗ =l(K+D−G)−l(K−G) and minimum distanced^∗≥deg(G) + 2−2g.

Proof. Letf, ω be as in Proposition 4.7. We rst show that f ω can't have order≤ −2in any P_i, i= 1, . . . , n. This follows from Proposition 4.7, as f ω=η for some η∈Ω(G−D). Since Supp(G)∩Supp(D) =∅, we have thatη can only have poles of order 1 in eachP_i.

We now nd the dimensionk^∗ by proving that ker(β^∗) = L(K−G). The formula for k^∗ then follows from the fact thatC^∗(D, G)∼=L(K+D−G)/ker(β^∗).

Supposeη ∈Ω(G−D)and res_P_i(η) = 0, i= 1, . . . , n. Thenη∈Ω(G). Letf ω=η. Then div(f ω)G. Sodiv(f) +K−G0, which is the same as saying f ∈L(K−G).

Conversely, supposef ∈L(K−G). Thendiv(f)+K G. SinceSupp(G)∩{P₁, . . . , P_n}=

∅, thenf ω has order at least 0 in eachP_i.

To prove thatd^∗≥deg(G) + 2−2g, suppose we have res_P_i(f ω) = 0 for n−d^∗ points P_i, sayP_i₁, . . . , P_i_n−d∗. We want to show that f ∈L(K+D−P_i₁ − · · · −P_i_n−d∗ −G), because then2g−2 +n−(n−d^∗)−deg(G)≥0.

Now, sincef ω has nonnegative order inP_i₁, . . . , P_i_n−d∗, then f ω∈Ω(G−D+P_i₁+· · ·+ P_i_n−d∗). So div(f) +K G−D+P_i₁ +· · ·+P_i_n−d∗. It follows that f ∈ L(K−G+D− P_i₁ − · · · −P_i_n−d∗), as desired.

5A AM +IJHK?JEI B )IOFJJE?=O /@ +@A 5AGKA?AI

Some New Constructions of Asymptotically Good Code Sequences

Contents

Chapter 1

Introduction

1.1 Asymptotic Properties of Codes

1.2 Generalised Algebraic-Geometric Codes

Chapter 2

Bounds on Codes

Chapter 3

Curves over Finite Fields

Chapter 4

Goppa Codes

4.1 Denitions

5A AM +IJHK?JEI B )IOFJJE?=O /@ +@A 5AGKA?AI