On construction and generalization of algebraic geometry codes^{∗}

Ryutaroh Matsumoto^{†} Department of Electrical and Electronic Engineering, Tokyo Institute of Technology, 152-8552 Japan Email: ryutaroh@ss.titech.ac.jp

and

Shinji Miura SONY Corporation Information and Network Technologies Laboratories Japan Email: miura@av.crl.sony.co.jp

March 4, 2000

Abstract

The construction, estimation of minimum distance, and decoding algorithms of algebraic geometry codes can be explained without using advanced mathematics by the notion of weight domains. We clarify the relation between algebraic geometry codes and linear codes from weight domains. Then we review a systematic construction which yields all weight domains.

1 Introduction

Algebraic geometry codes were defined in an algebraic geometric way, and many facts about them, in particular estimation of minimum distance and decoding algorithms, are also stated and proved algebraic geometrically. So it had been difficult to understand algebraic geometry codes without the theory of algebraic curves. Recently Høholdt et al. [HvLP97, HvLP98] observed that definition, estimation of minimum distance, and decoding algorithms of algebraic geometry codes could be explained using only the notion of a weight function, which is essentially a discrete valuation, and made understanding of algebraic geometry codes much easier. First we survey the construction of linear codes with weight functions.

∗This paper appeared in the Proceedings of Algebraic Geometry, Number Theory, Coding Theory and Cryptography, University of Tokyo, Tokyo, Japan, January 19–20, 2000 (ed. T.

Katsura et al.), pp. 3–15. The proceedings was published July 2000.

†He is supported by JSPS Research Fellowships for Young Scientists.

Linear codes obtained with weight functions are generalization of so-called one-point algebraic geometry codes. Next we survey a characterization of linear codes from weight functions and their comparison to the ordinary one-point AG codes.

We construct linear codes from a commutative ring equipped with a weight function, which we call a weight domain. Finally we survey a systematic construction which yields all weight domains.

We omit proofs of assertions and refer the reader to appropriate literatures when they are available in English.

2 Evaluation codes and weight functions

2.1 Definition of evaluation codes

Throughout this paper K denotes a fixed finite field, and N_{0} the set of nonnegative integers. R denotes a commutative K-algebra, and n a positive integer in this section.

Definition 2.1 [HvLP98, Definition 3.5] A function ρ : R → N_{0} ∪ {−∞} is said to be a weight function on R if

1. ρ(f) = −∞ iff f = 0.

2. ρ(cf) = ρ(f) for all nonzero c ∈ K.

3. ρ(f + g) ≤ max{ρ(f), ρ(g)} and the equality holds if ρ(f) ≠ ρ(g).

4. If ρ(f) = ρ(g) ≠ −∞, then there exists c ∈ K such that ρ(f − cg) < ρ(g).

5. ρ(fg) = ρ(f) + ρ(g), where the sum of an integer and −∞ is −∞.

Remark 2.2 A weight function is a generalization of the degree of univariate polynomials.

If R is a K-algebra with a weight function ρ, then there exists a K-basis {f_{1}, f_{2}, … } such that ρ(f_{i}) < ρ(f_{i+1}) for all i [HvLP98, Proposition 3.12]. We regard the set K^{n} consisting of n-tuples of elements in K as a commutative ring with the componentwise addition and multiplication. Let φ : R → K^{n} be an epimorphism of K-algebras. For a positive integer ℓ, we define the evaluation code E_{ℓ} ⊂ K^{n} by the linear space spanned by φ(f_{1}), …, φ(f_{ℓ}), and its dual code C_{ℓ}.

Let F/K be an algebraic function field of one variable [Sti93], Q a place of degree one of F/K, v_{Q} the discrete valuation at Q, and L(∞Q) = ⋃_{i=0}^{∞} L(iQ). Then −v_{Q} is a weight function on the ring L(∞Q). Let P_{1}, …, P_{n} be pairwise distinct places of degree one, and φ : L(∞Q) → K^{n}, f ↦ (f(P_{1}), …, f(P_{n})). Then φ is an epimorphism of K-algebras, E_{ℓ} is a functional one-point algebraic geometry code, and C_{ℓ} is a residual one.

Let g = ♯{m ∈ N_{0} | there is no f ∈ R such that ρ(f) = m}. By elementary arguments we can show that E_{ℓ} is an [n, ℓ, d] code such that d ≥ n + 1 − ℓ − g if ρ(f_{ℓ}) < n [HvLP98, Corollary 5.19], and the minimum distance of C_{ℓ} is at least ℓ + 1 − g [HvLP98, Theorem 5.24]. They correspond to the Goppa bound for the minimum distance of algebraic geometry codes.

2.2 Relation between an evaluation code and a one-point AG code

It is interesting what we can say about a ring with a weight function. The following is known.

Theorem 2.3 [Mat99b] Let R be a K-algebra with a weight function ρ and R ≠ K. Then there exist an algebraic function field F/K, its place Q of degree one, and a positive integer e such that F is the quotient field of R, R ⊆ L(∞Q) = ⋃_{i=0}^{∞} L(iQ), and ρ = −e × v_{Q}. In other words, there exist a projective algebraic curve χ defined over K and a K-rational point Q ∈ χ such that R is the ring of K-rational functions regular at χ \ {Q} and ρ is a multiple of the pole order of rational functions at Q. In particular, R is finitely generated over K, and is an integral domain.

Hereafter we call a K-algebra with a weight function a weight domain.

Evaluation codes and their duals are generalization of one-point AG codes. It is interesting whether we can obtain a good linear code as (the dual of) an evaluation code that is never obtained as a one-point AG code. Suppose that R is a weight domain with a weight function ρ. If R is integrally closed, then the evaluation code E_{ℓ} and its dual C_{ℓ} can be obtained as one-point AG codes. Thus to compare evaluation codes and ordinary AG codes, it is enough to compare evaluation codes (and its duals) on R with evaluation codes (and its duals) on the normalization of R. It is shown that we cannot obtain an evaluation code on R better than that on the normalization of R [Mat99a]. For precise statements, see [Mat99a].

3 Construction of weight domains

3.1 Construction of general weight domains

In this section, we review a class of defining equations which yields all weight domains. The results in this section were already shown in [Miu97, Miu98, Pel], and they were in part shown in the earlier paper [Miu94]. But our proofs are new and simpler than the original given in [Miu97, Miu98] and similar to the proofs in [Pel]. The second author proved his results [Miu97, Miu98] using the theory of algebraic function fields [Sti93], while we prove all the results in an elementary way. Note that the second author did not know the notion of weight domains and he did not state facts in his papers [Miu94, Miu97, Miu98] in the framework of the weight domain.

Let H be a subsemigroup of N_{0}. We call {ρ(f) | 0 ≠ f ∈ R} the associated semigroup of a weight domain R with a weight function ρ. We shall consider a weight domain R with the associated semigroup H.

Lemma 3.1 If H = {0} then R = K.

Proof. Let x ∈ R and ρ(x) = 0. By the condition 4 in Definition 2.1, there exists c ∈ K such that ρ(x − c) = −∞, which implies x = c.

So we assume that H ≠ {0}. N_{0} \ H is finite iff the greatest common divisor of H is 1 [HvLP98, Corollary 5.12]. ρ/ gcd(H) is also a weight function on R. So we may assume without loss of generality that N_{0} \ H is finite by replacing ρ with ρ/ gcd(H) if necessary. If H = N_{0} then R is the univariate polynomial ring over K [Mat99b]. So hereafter we also assume that H ≠ N_{0}.

Suppose that A_{t} = {a_{1}, …, a_{t}} is a generating set of H and a_{i} ≠ 0 for i = 1, …, t. We shall introduce a monomial order induced from A_{t}.

Definition 3.2 For (m_{1}, …, m_{t}), (n_{1}, …, n_{t}) ∈ N_{0}^{t}, we define (m_{1}, …, m_{t}) ≻ (n_{1}, …, n_{t}) if

a_{1}m_{1} + ⋯ + a_{t}m_{t} > a_{1}n_{1} + ⋯ + a_{t}n_{t},

or

a_{1}m_{1} + ⋯ + a_{t}m_{t} = a_{1}n_{1} + ⋯ + a_{t}n_{t},

and m_{1} = n_{1}, m_{2} = n_{2}, …, m_{i−1} = n_{i−1}, m_{i} < n_{i}, for some 1 ≤ i ≤ t.

Notice that the definition of ≻ depends on the order of elements in A_{t}.

Definition 3.3 [Miu94, Definition 6 and 8], [Miu97, Section 5.2], [Miu98, pp. 1408– 1409] We define B(A_{t}) = {(n_{1}, …, n_{t}) ∈ N_{0}^{t} | if a_{1}n_{1} + ⋯ + a_{t}n_{t} = a_{1}m_{1} + ⋯ + a_{t}m_{t} for some (m_{1}, …, m_{t}) ∈ N_{0}^{t} then (n_{1}, …, n_{t}) ⪯ (m_{1}, …, m_{t})}, and V (A_{t}) to be the set of minimal elements in N_{0}^{t} \ B(A_{t}) with respect to the partial order in N_{0}^{t} such that (m_{1}, …, m_{t}) is smaller than (n_{1}, …, n_{t}) if m_{i} ≤ n_{i} for i = 1, …, t.

Choose x_{i} ∈ R such that ρ(x_{i}) = a_{i}. Let X_{i} be variable over K for i = 1, …, t, and I ⊂ K[X_{1}, …, X_{t}] the kernel of the evaluation homomorphism X_{i} ↦ x_{i}. We shall show that R = K[x_{1}, …, x_{t}] (Corollary 3.5), and characterize the form of the reduced Gröbner basis for I with respect to ≺ (Theorem 3.10). Then we shall show that if a set of polynomials is in such a form then it defines a weight domain conversely (Theorem 3.11). Basic facts in the Gröbner basis theory can be found in [AL94, CLO96]. We assume that the reader is familiar with Gröbner bases. For N = (n_{1}, …, n_{t}) ∈ N_{0}^{t}, we denote X_{1}^{n_{1}} ⋯ X_{t}^{n_{t}} (resp. x_{1}^{n_{1}} ⋯ x_{t}^{n_{t}}) by X^{N} (resp. x^{N}).

Proposition 3.4 [Miu94, Lemma 10], [Miu97, Lemma 5.13], [Miu98, p. 1410] {x^{N} | N ∈ B(A_{t})} forms a K-basis for R.

Proof. By the definitions of B(A_{t}) and the weight function, the elements in {x^{N} | N ∈ B(A_{t})} are linearly independent.

Let h be a nonzero element in R. There exists N ∈ B(A_{t}) such that ρ(x^{N}) = ρ(h), and c_{N} ∈ K such that ρ(h − c_{N}x^{N}) < ρ(h). By repeating this argument, we can write h as

∑_{N∈B(A_{t})} c_{N}x^{N}.

We have shown that h can be written as a linear combination of elements in {x^{N} | N ∈ B(A_{t})}.

Corollary 3.5 [Miu94, Lemma 9], [Miu97, Lemma 5.3], [Miu98, p. 1406] R = K[x_{1}, …, x_{t}].

Definition 3.6 The delta set of I, denoted by Δ(I), is {N ∈ N_{0}^{t} | X^{N} is not the leading monomial of any nonzero polynomial in I with respect to ≺}.

Lemma 3.7 [Miu97, Section 5.4], [Miu98, p. 1417] Δ(I) = B(A_{t}).

Proof. We claim that Δ(I) ⊆ B(A_{t}). Suppose that there is N ∈ Δ(I) \ B(A_{t}). By Proposition 3.4, we can write x^{N} as

∑_{\begin{matrix}M∈B(A_{t}) \\ ρ(x^{M})≤ρ(x^{N}) \end{matrix}} c_{M}x^{M}.

Consider the polynomial

X^{N} − ∑_{\begin{matrix}M∈B(A_{t}) \\ ρ(x^{M})≤ρ(x^{N}) \end{matrix}} c_{M}X^{M}.

Then it belongs to I and by the definition of B(A_{t}) its leading monomial is X^{N}, which is a contradiction.

Since {x^{N} | N ∈ Δ(I)} forms a K-basis for R [AL94, Proposition 2.1.6], we can see that Δ(I) = B(A_{t}) by Proposition 3.4.

Lemma 3.8 [Miu94, Lemma 7], [Miu97, Lemma 5.10], [Miu98, p. 1409] V (A_{t}) is finite.

Proof. The assertion is a special case of Dickson’s Lemma [AL94, Exercise 1.4.12].

Definition 3.9 For each N ∈ V (A_{t}), we can write x^{N} as

∑_{M∈B(A_{t})} c_{M}x^{M},

in a unique way. We define the polynomial F_{N} ∈ K[X_{1}, …, X_{t}] to be

X^{N} − ∑_{M∈B(A_{t})} c_{M}X^{M}.

Theorem 3.10 [Miu94, Lemma 14], [Miu97, Theorem 5.16], [Miu98, pp. 1410– 1411] {F_{N} | N ∈ V (A_{t})} is the reduced Gröbner basis for I with respect to ≺.

Proof. F_{N} ∈ I for each N ∈ V (A_{t}), and {X^{N} | N ∈ V (A_{t})} is the set of minimal elements in the set of leading monomials of I. Thus by the definition of Gröbner basis, {F_{N} | N ∈ V (A_{t})} is a Gröbner basis. It is clear that {F_{N} | N ∈ V (A_{t})} is the reduced Gröbner basis for I.

We shall prove a converse to Theorem 3.10.

Theorem 3.11 [Miu94, Theorem 1], [Miu97, Theorem 5.17], [Miu98, p. 1411], [Pel, Theorem 5.11] For M = (m_{1}, …, m_{t}) ∈ N_{0}^{t}, we define Ψ(M) = a_{1}m_{1} + ⋯ + a_{t}m_{t}. For each N ∈ V (A_{t}) choose a polynomial G_{N} in K[X_{1}, …, X_{t}] of the form

X^{N} + c_{M}X^{M} + ∑_{L∈B(A_{t}), Ψ(L)<Ψ(N)} c_{L}X^{L},

such that Ψ(N) = Ψ(M), M ∈ B(A_{t}), and c_{M} ≠ 0. Let J be the ideal generated by {G_{N} | N ∈ V (A_{t})}. If {G_{N} | N ∈ V (A_{t})} is a Gröbner basis (automatically becoming the reduced one) with respect to ≺, then K[X_{1}, …, X_{t}]/J is a weight domain with the weight function ρ(X^{L} mod J) = Ψ(L) for L ∈ B(A_{t}).

Proof. Notice that V (A_{t}) + N_{0}^{t} = N_{0}^{t} \ B(A_{t}). Since {G_{N} | N ∈ V (A_{t})} is a Gröbner basis, Δ(J) = N_{0}^{t} \ (V (A_{t}) + N_{0}^{t}). Thus Δ(J) = B(A_{t}) and {X^{L} mod J | L ∈ B(A_{t})} forms a K-basis for K[X_{1}, …, X_{t}]/J.

We shall check whether ρ is a weight function. The conditions 1–4 of weight functions (Definition 2.1) are satisfied by the discussion in the previous paragraph. We shall check the condition 5. Let E_{1}, E_{2} be polynomials written as linear combinations of monomials in {X^{N} | N ∈ B(A_{t})}. In order to calculate the weight of E_{1}E_{2} mod J, we have to write E_{1}E_{2} as a linear combination of monomials in {X^{N} | N ∈ B(A_{t})}, which can be done by Gröbner basis division. Let E_{3} be the remainder on division of E_{1}E_{2} by {G_{N} | N ∈ V (A_{t})}. By the form of {G_{N} | N ∈ V (A_{t})}, we can see that ρ(E_{1}E_{2} mod J) = ρ(E_{3} mod J).

Remark 3.12 In this survey a weight function has values in N_{0}. Pellikaan and Geil [Gei99] extend the notion of weight functions to taking values in a general semigroup and genelarize Theorem 3.11 in [Gei99, Theorem 1.7.1].

Proposition 3.13 [Miu97, Lemma 5.21], [Miu98, p. 1413] We retain notations from Theorem 3.11. ρ(X^{L} mod J) = Ψ(L) for all L ∈ N_{0}^{t}.

Proof. In order to calculate ρ(X^{L} mod J), we have to write X^{L} mod J as a linear combination of {X^{L′} mod J | L′ ∈ B(A_{t})}, which can be done by dividing X^{L} by {G_{N} | N ∈ V (A_{t})}. Let L′′ be the exponent of the leading monomial of the remainder on division of X^{L} by {G_{N} | N ∈ V (A_{t})}. Then by definition ρ(X^{L} mod J) = Ψ(L′′). By the form of {G_{N} | N ∈ V (A_{t})}, we can see that Ψ(L) = Ψ(L′′).

Remark 3.14 When we construct a weight domain as in Theorem 3.11, we can easily find a K-basis for the weight domain with pairwise distinct weights as in the proof of Theorem 3.11. Such a basis is indispensable with code construction and decoding algorithms of AG codes. This fact is stated in a different way in [SH95, Proposition 13].

Remark 3.15 Saints and Heegard defined the notion of a projective algebraic curve in special position [SH95, Definition 11]. The projective closure of the affine algebraic curve defined in Theorem 3.11 is in special position if it is nonsingular and a_{1} < ⋯ < a_{t}. Conversely, if a projective algebraic curve χ is in special position with respect to a point Q, then the affine coordinate ring of the affine algebraic curve χ \ {Q} is a weight domain.

For construction of weight domains and linear codes on them, we have to calculate B(A_{t}) and V (A_{t}). It is not obvious how to calculate B(A_{t}) and V (A_{t}). We shall clarify it.

Definition 3.16 For i = 0, …, a_{1} − 1, we define b_{i} = min{x ∈ H | x ≡ i (mod a_{1})}, and L_{i} to be the minimum element N ∈ N_{0}^{t} with respect to ≺ such that Ψ(N) = b_{i}, where Ψ is as in Theorem 3.11.

Notice that we can easily calculate L_{0}, …, L_{a_{1}−1} when we are given a sequence a_{1}, …, a_{t}.

Lemma 3.17 Let L_{i} = (ℓ_{1}, …, ℓ_{t}). Then ℓ_{1} = 0.

Proof. Suppose that ℓ_{1} > 0. Then b_{i} = ℓ_{1}a_{1}+ℓ_{2}a_{2}+⋯+ℓ_{t}a_{t} > ℓ_{2}a_{2}+⋯+ℓ_{t}a_{t} ∈ H, which contradicts to the definition of b_{i}.

Proposition 3.18 [Miu94, Lemma 5 and 7], [Miu97, Lemma 5.9 and 5.10], [Miu98, pp. 1408–1409] Let

e_{i} = (\overbrace{0, …, 0}^{i−1}, 1, 0, …, 0) ∈ N_{0}^{t},

for i = 2, …, t. Then

B(A_{t}) = {L_{i} + (j, 0, …, 0) | 0 ≤ i ≤ a_{1} − 1, 0 ≤ j},
V (A_{t}) ⊆ {L_{i} + e_{j} | 0 ≤ i ≤ a_{1} − 1, 2 ≤ j ≤ t}.

Proof. The second assertion follows from the first and the definition of V (A_{t}). We shall prove the first.

Let x ∈ H, i = x mod a_{1}, and j = (x − b_{i})/a_{1}. Then x = b_{i} + ja_{1}, and Ψ(L_{i} + (j, 0, …, 0)) = x. Suppose that Ψ(N) = x for some N ∈ N_{0}^{t}. It is enough to show that L_{i} + (j, 0, …, 0) ⪯ N to prove the first assertion by the definition of B(A_{t}).

Let N = (n_{1}, …, n_{t}). If n_{1} < j then L_{i} +(j, 0, …, 0) ≺ N by the definition of ≺. If n_{1} > j then Ψ(0, n_{2}, …, n_{t}) = x − n_{1}a_{1} < x − ja_{1} = b_{i}, which is a contradiction. So hereafter we assume that j = n_{1}.

Since ≺ is a monomial order, it is enough to show that L_{i} ⪯ (0, n_{2}, …, n_{t}). Because Ψ(0, n_{2}, …, n_{t}) = b_{i}, L_{i} ⪯ (0, n_{2}, …, n_{t}) by the definition of L_{i}.

3.2 Construction of telescopic weight domains

It is difficult to check whether a given set of polynomials in Theorem 3.11 is a Gröbner basis by hand. We shall show that if H is telescopic then the set of polynomials in Theorem 3.11 automatically forms a Gröbner basis and we can write B(A_{t}) and V (A_{t}) in a more explicit way than Proposition 3.18. We call a weight domain telescopic if the associated semigroup is telescopic.

Definition 3.19 A sequence a_{1}, …, a_{t} is said to be telescopic if a_{i}/d_{i} belongs to the semigroup generated by a_{1}/d_{i−1}, …, a_{i−1}/d_{i−1} for i = 2, …, t, where d_{i} is the greatest common divisor of a_{1}, …, a_{i}. A subsemigroup of N_{0} is said to be telescopic if it can be generated by a telescopic sequence.

Lemma 3.20 Let L_{i} be as in Definition 3.16. If a_{1}, …, a_{t} is telescopic, then {L_{i} | i = 0, …, a_{1} − 1} = {(0, n_{2}, …, n_{t}) | 0 ≤ n_{i} < d_{i−1}/d_{i} for i = 2, …, t}.

Proof. Suppose that L_{i} = (0, ℓ_{2}, …, ℓ_{t}), and ℓ_{j} ≥ d_{j−1}/d_{j} for some j ≥ 2. By the definition of telescopic sequences, (d_{j−1}/d_{j})a_{j} belongs to the semigroup generated by a_{1}, …, a_{j−1}. Let α_{1}a_{1} + ⋯ + α_{j−1}a_{j−1} = (d_{j−1}/d_{j})a_{j}, and L′_{i} = (ℓ_{1}+α_{1}, …, ℓ_{j−1}+α_{j−1}, ℓ_{j}−(d_{j−1}/d_{j}), ℓ_{j+1}, …, ℓ_{t}). Then Ψ(L_{i}) = Ψ(L′_{i}) and L′_{i} ≺ L_{i}, which contradicts to the definition of L_{i}. We have shown that {L_{i} | i = 0, …, a_{1} − 1} ⊆ {(0, n_{2}, …, n_{t}) | 0 ≤ n_{i} < d_{i−1}/d_{i} for i = 2, …, t}.

Is is easy to see that both sets have a_{1} elements. So the assertion is proved.

Corollary 3.21 [Miu94, Theorem 1 (VI)], [Miu97, Theorem 5.43], [Miu98, p. 1419] Suppose that the sequence a_{1}, …, a_{t} is telescopic. Then

B(A_{t}) = {(n_{1}, …, n_{t}) ∈ N_{0}^{t} | 0 ≤ n_{i} < d_{i−1}/d_{i} for i = 2, …, t},
V (A_{t}) = \{(\overbrace{0, …, 0}^{i−1}, d_{i−1}/d_{i}, 0, …, 0) | i = 2, …, t\}.

Proof. The assertions follow directly from the previous lemma, Proposition 3.18, and the definition of ≺ and V (A_{t}).

Remark 3.22 A similar fact to Corollary 3.21 is shown in [KP95, Lemma 6.4] and [HvLP98, Lemma 5.34].

Theorem 3.23 [Miu94, p. 462, Remark], [Miu97, Corollary 5.36], [Miu98, p. 1418] Suppose that a_{1}, …, a_{t} is telescopic. Then the set of polynomials {G_{N} | N ∈ V (A_{t})} forms a Gröbner basis.

Proof. The assertion follows directly from Theorem 3 and Proposition 4 in [CLO96, Section 2.9].

Remark 3.24 A special case of the previous theorem is in [HvLP98, Example 5.36], [Pel, Proposition 5.12].

Remark 3.25 Further applications of telescopic semigroups in coding theory can be found in [HvLP98, KP95]. Research articles on telescopic semigroups are listed in [KP95, Remark 6.7].

Remark 3.26 It is desirable to choose generators a_{1}, …, a_{t} as few as possible. A generating set of H is said to be minimal if H is not generated by its proper subset. We can prove that a minimal generating set is unique, each generating set contains the minimal one, and if H is telescopic then we can make the minimal generating set a telescopic sequence. A proof can be found in [Miu97, Miu98].

3.3 Construction of plane weight domains

If the associated semigroup is generated by two numbers, then the weight domain can be obtained as the affine coordinate ring of a plane affine algebraic curve. We call such a weight domain plane. In this subsection we write down the defining equation of a plane weight domain explicitly.

We retain notations from Section 3.1 unless otherwise specified. Let a = a_{1}, b = a_{2}, X = X_{1}, and Y = X_{2}. Since we assume that N_{0} \ H is finite and not empty, a and b are relatively prime [HvLP98, Corollary 5.12] and greater than 1. Note that in this case a, b is a telescopic sequence and a plane weight domain is a special case of a telescopic weight domain.

As a special case of Corollary 3.21 we have

Corollary 3.27 [Miu97, Section 7.2]

B(A_{t}) = {(i, j) ∈ N_{0}^{2} | 0 ≤ i, 0 ≤ j < a},
V (A_{t}) = {(0, a)}.

F_{N} in Theorem 3.10 and G_{N} in Theorem 3.11 is of form

Y^{a} + c_{b,0}X^{b} + ∑_{ia+bj<ab} c_{i,j}X^{i}Y^{j},  (1)

where c_{b,0} ≠ 0 and c_{i,j} ∈ K.

We shall clarify which algebraic curve can have a plane model of the form (1).

Proposition 3.28 [Miu97, Theorem 5.17 (9)], [Miu98, p. 1412] Let χ be a nonrational nonsingular projective algebraic curve over K. If there is a Krational point Q ∈ χ, then χ can have a plane model of the form (1).

Proof. Let F be the field of K-rational functions on χ, v_{Q} the discrete valuation at Q, and x, y ∈ F \K functions such that they are regular at χ\{Q} and v_{Q}(x) and v_{Q}(y) are relatively prime. From the definition of x, y, the pole divisor of x (resp. y) is −v_{Q}(x)Q (resp. −v_{Q}(y)Q).

[F : K(x)] = −v_{Q}(x) and [F : K(y)] = −v_{Q}(y) [Sti93, Theorem I.4.11], and [F : K(x, y)] divides both [F : K(x)] and [F : K(y)]. Thus [F : K(x, y)] = 1.

K[x, y] is a weight domain with the weight function −v_{Q}. Thus K[x, y] is the affine coordinate ring of an affine algebraic curve defined by a polynomial of the form (1), where we set a = −v_{Q}(x) and b = −v_{Q}(y).

Remark 3.29 The second author observed that we can easily construct algebraic geometry codes on affine algebraic curves defined by polynomials of form (1) in [Miu92].

Remark 3.30 An overlapping but different construction of weight domains is in [HvLP98, Proposition 3.17], [Pel, Proposition 4.6].

References

[AL94] William W. Adams and Phillippe Loustaunau, An introduction to Gröbner bases, Graduate Studies in Mathematics, vol. 3, American Mathematical Society, 1994.

[CLO96] David Cox, John Little, and Donal O’Shea, Ideals, varieties, and algorithms, 2nd ed., Springer-Verlag, Berlin, 1996.

[Gei99] Olav Geil, Codes based on an 𝔽_{q}-algebra, Ph.D. thesis, Aalborg Univ., Denmark, December 1999.

[HvLP97] Tom Høholdt, Jacobus H. van Lint, and Ruud Pellikaan, Order functions and evaluation codes, Proc. AAECC-12, Lecture Notes in Computer Science, vol. 1255, Springer-Verlag, 1997, pp. 138–150.

[HvLP98] Tom Høholdt, Jacobus H. van Lint, and Ruud Pellikaan, Algebraic geometry codes, Handbook of Coding Theory (Vera Pless and William Cary Huffman, eds.), Elsevier, 1998, pp. 871–961.

[KP95] Christoph Kirfel and Ruud Pellikaan, The minimum distance of codes in an array coming from telescopic semigroups, IEEE Trans. Inform. Theory 41 (1995), no. 6, 1720–1732.

[Mat99a] Ryutaroh Matsumoto, Linear codes on nonsingular curves are better than those on singular curves, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN 0916-8508) E82-A (1999), no. 4, 665–670.

[Mat99b] Ryutaroh Matsumoto, Miura’s generalization of one-point AG codes is equivalent to Høholdt, van Lint and Pellikaan’s generalization, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (ISSN 0916-8508) E82-A (1999), no. 10, 2007–2010.

[Miu92] Shinji Miura, Algebraic geometric codes on certain plane curves, Transactions of IEICE (ISSN 0913-5707) J75-A (1992), no. 11, 1735– 1745 (Japanese).

[Miu94] Shinji Miura, Constructive theory of algebraic curves, Proceedings of the 17th Symposium on Information Theory and Its Applications (Hiroshima, Japan), December 1994, pp. 461–464 (Japanese).

[Miu97] Shinji Miura, Ph.D. thesis, Univ. Tokyo, May 1997 (Japanese).

[Miu98] Shinji Miura, Linear codes on affine algebraic curves, Transactions of IEICE (ISSN 0913-5707) J81-A (1998), no. 10, 1398–1421 (Japanese).

[Pel] Ruud Pellikaan, On the existence of order functions, to appear in Journal of Statistical Planning and Inference, available from http://

www.win.tue.nl/math/dw/personalpages/ruudp/.

[SH95] Keith Saints and Chris Heegard, Algebraic-geometric codes and multidimensional cyclic codes: A unified theory and algorithms for decoding using Gröbner bases, IEEE Trans. Inform. Theory 41 (1995), no. 6, 1733–1751.

[Sti93] Henning Stichtenoth, Algebraic function fields and codes, Springer-Verlag, Berlin, 1993.