LINEAR CODES DEFINED FROM HIGHER-DIMENSIONAL VARIETIES

A Dissertation

Submitted to the Graduate Faculty of the Louisiana State University and Agricultural and Mechanical College in partial fulfillment of the requirements for the degree of Doctor of Philosophy

in

The Department of Mathematics

by Gary Lynn Salazar B.S., Baylor University, 1994 August 2000

Acknowledgments

I attribute this accomplishment to the Lord who continues to grace us with uncountable blessings. I also want to thank those educators who have had a positive and valuable influence on me. In particular, an appreciation is expressed to Rose Volcik and Glover Laird for their willingness to sacrifice numerous hours and unceasing efforts to cultivate a skilled young scientist. Also, I am grateful to David Pennington for his instruction and encouragement in the field of chemistry. I wish to extend a special expression of gratitude to my advisor, Robert Lax, whose insight and advice have been indispensable.

I must also acknowledge my family which has remained a source of invaluable encouragement and inspiration. First, I want to thank my mom, Sheryl Salazar, who has always believed in me and has provided me with the confidence to pursue my dreams. I wish to extend thanks to my grandfathers, Cecil King and Juan Salazar, who have continually served as my role models. Also, I remain extensively appreciative of my fiancée, Jenny Potter, whose love and support helped me to withstand the difficulties I faced and inspired me to complete the task of obtaining a doctoral degree. Lastly, I wish to dedicate this dissertation to my late father, Manuel Salazar, who provided me with knowledge of the importance of family and social responsibility.

Table of Contents

Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1 The Feng-Rao Bound and Affine Variety Codes. . . . . . . . . . . . . . . . . . . 2 1.1 Affine Variety Codes . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Improved Geometric Codes . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Type I Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Codes on Fermat Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1 Gröbner Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Higher-Dimensional Varieties . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Fermat Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 Fermat Surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Vita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

Abstract

We establish an algebraic foundation to complement the improved geometric codes of Feng and Rao. Viewing linear codes as affine variety codes, we utilize the Feng-Rao minimum distance bound to construct codes with relatively large dimensions. We examine higher-dimensional affine hypersurfaces with properties similar to those of Hermitian curves. We determine a Gröbner basis for the ideal of the variety of rational points on certain affine Fermat varieties. This result is applied to determine parameters of codes defined from Fermat surfaces.

Introduction

Linear codes obtained by methods from algebraic geometry have gained significant notoriety since 1982, when Tsfasman, Vlǎduţ, and Zink [10] determined the existence of a sequence of algebraic-geometric (or Goppa) codes that exceeded the Gilbert-Varshamov bound on the minimum distance. In 1995, G.-L. Feng and T.R.N. Rao [4] introduced the concept of improved geometric Goppa codes from plane curves. Absent of algebraic geometry, they were able to improve the current one-point Goppa codes from curves that have a single point at infinity.

The goal of this dissertation is to produce an algebraic foundation to complement these so-called “improved geometric codes.” We shall also expand this notion to include affine varieties of arbitrary dimension.

In Chapter 1, we describe affine varieties and a formation of linear codes defined by them. We also develop and expand the fundamentals of improved geometric codes and the Feng-Rao bound on the minimum distance of a code. We conclude this chapter by examining codes from Type I curves, including Hermitian curves.

In Chapter 2, we review the theory of Gröbner bases and investigate its applications to higher-dimensional varieties. We determine a Gröbner basis for the ideal of the variety of rational points on certain affine Fermat varieties. This result is applied to determine parameters of codes defined from Fermat surfaces.

Generally, we will have restrictions on code length and minimum distance. We will require the Feng-Rao bound on the minimum distance to create codes with relatively large dimensions.

Chapter 1 The Feng-Rao Bound and Affine Variety Codes

1.1 Affine Variety Codes

Let 𝔽_{q} be the finite field with q elements. Let S ⊆ 𝔽_{q}[x_{1}, …, x_{k}]. Let \overline{𝔽}_{q} denote an algebraic closure of 𝔽_{q}. The k-tuple (a_{1}, …, a_{k}) ∈ \overline{𝔽}_{q}^{k} is called a solution of S if f(a_{1}, …, a_{k}) = 0 for all f in S. The affine variety in \overline{𝔽}_{q}^{k} defined by S, denoted V (S), is the set of all solutions of S. The elements (a_{1}, …, a_{k}) of V (S) are known as the points of V (S). Further, if each coordinate of a point of V (S) lies in 𝔽_{q}, then the point is called an 𝔽_{q}-rational point of V (S). Note that if I is the ideal of 𝔽_{q}[x_{1}, …, x_{k}] generated by the set S, then V (I) = V (S). Definition 1.1. For I an ideal of 𝔽_{q}[x_{1}, …, x_{k}], define

I_{q} := I + (x_{1}^{q} − x_{1}, …, x_{k}^{q} − x_{k}).

Remark 1.2. The points of V (I_{q}) are precisely the 𝔽_{q}-rational points of V (I).

Since the polynomials x_{i}^{q} − x_{i} ∈ I_{q} for each i such that 1 ≤ i ≤ k, we have that I_{q} is a zero-dimensional ideal. Moreover, by Seidenberg’s Lemma 92 [9], I_{q} is in fact a radical ideal.

The ring R = 𝔽_{q}[x_{1}, …, x_{k}]/I_{q} is called the coordinate ring of the variety V (I_{q}). The elements of R are designated by f̄, where f̄ represents the equivalence class f +I_{q}, for each polynomial f. Let 𝔸^{n} = 𝔽_{q}^{n} be affine n-space over 𝔽_{q}, where n is the number of points of the affine variety V (I_{q}). After ordering the points P_{1}, …, P_{n} of V (I_{q}), define an evaluation map ϕ : R ↦ 𝔸^{n} by ϕ(f̄) = (f(P_{1}), …, f(P_{n})), where f̄ = f +I_{q}. The mapping ϕ is easily seen to be an isomorphism of 𝔽_{q}-vector spaces. Definition 1.3. A linear code of length n over 𝔽_{q} is a vector subspace of 𝔽_{q}^{n}.

Let I be an ideal of 𝔽_{q}[x_{1}, …, x_{k}] and P_{1}, …, P_{n} be all the points of V (I_{q}). Let L be an 𝔽_{q}-vector subspace of the coordinate ring R. Definition 1.4. The affine variety codes, C(I, L) and C^{⊥}(I, L), are defined as follows:

C(I, L) = ϕ(L)
C^{⊥}(I, L) = ϕ(L)^{⊥}

where ϕ(L) is the image of L under the evaluation map ϕ, and ϕ(L)^{⊥} is the orthogonal complement of ϕ(L) with respect to the usual inner product on 𝔸^{n}. Remark 1.5. (i) Every 𝔽_{q}-linear code can be represented as an affine variety code.

(ii) A different ordering of the points would yield an equivalent code, so a linear code with the same length, dimension, and minimum distance.

We define a weighted-degree lexicographic ordering on the (monic) monomials of 𝔽_{q}[x_{1}, …, x_{k}]. For each of the variables x_{j}, where 1 ≤ j ≤ k, we can assign a positive integer, wt(x_{j}). The weight of a monomial, x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}}, is defined as

wt(x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}}) = ∑_{j=1}^{k} i_{j}wt(x_{j}).

To define the total ordering <_{t} on the monomials, apply the rule:

x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}} <_{t} x_{1}^{j_{1}}x_{2}^{j_{2}} … x_{k}^{j_{k}} if
(i) wt(x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}}) < wt(x_{1}^{j_{1}}x_{2}^{j_{2}} … x_{k}^{j_{k}}) or
(ii) wt(x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}}) = wt(x_{1}^{j_{1}}x_{2}^{j_{2}} … x_{k}^{j_{k}}) and there exists an l
such that i_{m} = j_{m} for 1 ≤ m ≤ l − 1 and i_{l} < j_{l}.

With this ordering we can further describe the elements of the coordinate ring R of the variety V (I_{q}). Let T^{k} denote the set of (monic) monomials of 𝔽_{q}[x_{1}, …, x_{k}], i.e. T^{k} = {x_{1}^{α_{1}} … x_{k}^{α_{k}}|α_{i} ∈ ℕ for 1 ≤ i ≤ k}. To simplify notation, we will sometimes write x^{α} for x_{1}^{α_{1}} … x_{k}^{α_{k}} where α = (α_{1}, …, α_{k}) ∈ ℕ^{k}. For every nonzero polynomial f ∈ 𝔽_{q}[x_{1}, …, x_{k}], we can express f as f = c_{1}x^{β_{1}} + c_{2}x^{β_{2}} + ⋯ + c_{s}x^{β_{s}} with 0 ≠ c_{i} ∈ 𝔽_{q}, x^{β_{i}} ∈ T^{k} and x^{β_{s}} <_{t} ⋯ <_{t} x^{β_{2}} <_{t} x^{β_{1}}. Define the leading monomial of f, denoted lm(f), by lm(f) = x^{β_{1}}. Also, define the leading term of f, denoted lt(f), by lt(f) = c_{1}x^{β_{1}}.

Definition 1.6. The footprint or Δ-set of an ideal I ⊆ 𝔽_{q}[x_{1}, …, x_{k}] is defined by Δ(I) := T^{k} \ {lm(f)|f ∈ I, f ≠ 0}.

Example 1.7. Let I be the principal ideal in 𝔽_{4}[x_{1}, x_{2}] generated by the polynomial x_{1}^{3} + x_{2}^{2} + x_{2}. This is known as the (affine) Hermitian curve over 𝔽_{4}. Note that I_{q} = ⟨x_{1}^{3} + x_{2}^{2} + x_{2}, x_{1}^{4} − x_{1}, x_{2}^{4} − x_{2}⟩. Let wt(x_{1}) = 2 and wt(x_{2}) = 3. An explanation of the motivation to choose these integers will follow later. Then we have Δ(I_{q}) = {1, x_{1}, x_{1}^{2}, x_{2}, x_{1}x_{2}, x_{1}^{2}x_{2}, x_{2}^{2}, x_{2}^{3}}.

Definition 1.8. For an ideal I ⊆ 𝔽_{q}[x_{1}, …, x_{k}], we define the H-sequence as H := {h_{i}}_{i=1}^{n′} the increasing sequence (under the ordering <_{t}) of the elements of Δ(I_{q}). With a slight abuse of notation, we will indicate that the monomial h_{i} appears in the H-sequence by the notation h_{i} ∈ H.

Remark 1.9. For h_{i} ∈ H, we claim that if a monomial m divides h_{i}, then m ∈ H. For if not, m ∉ H implies there exists a polynomial f ∈ I_{q} such that lm(f) = m. Therefore, (\frac{h_{i}}{m})f ∈ I_{q} and lm((\frac{h_{i}}{m})f) = (\frac{h_{i}}{m})m = h_{i}. Thus, h_{i} ∉ H, which is a contradiction.

In Example 1.7, H = {1, x_{1}, x_{2}, x_{1}^{2}, x_{1}x_{2}, x_{2}^{2}, x_{1}^{2}x_{2}, x_{2}^{3}}. Note that the corresponding weights of each of the eight monomials are distinct.

Proposition 1.10. The elements of the set {h̄_{1}, …, h̄_{n′}} form a basis for the coordinate ring R. Therefore, dim 𝔽_{q}[x_{1}, …, x_{k}]/I_{q} = |Δ(I_{q})| = n.

Proof. Since R is spanned by the set of equivalence classes of monomials that are not the leading monomial of any polynomial in I_{q}, it suffices to show that {h̄_{1}, …, h̄_{n′}} is a linearly independent set of elements of R. Suppose there exists c_{1}, c_{2}, …, c_{n′} ∈ 𝔽_{q} not all zero such that c_{1}h̄_{1} + c_{2}h̄_{2} + ⋯ + c_{n′} h̄_{n′} = ¯0. Therefore, f = c_{1}h_{1}+c_{2}h_{2}+⋯+c_{n′}h_{n′} ∈ I_{q}. Then lm(f) = h_{i} for some i. However, h_{i} ∈ Δ(I_{q}) implies that f ∉ I_{q}, which is a contradiction. It follows that n = n′. □

1.2 Improved Geometric Codes

We will next present several definitions that were first given by G.-L. Feng and T. R. N. Rao. [4]

Definition 1.11. Let L(\underline{r}) be the the linear subspace of R generated by the set \{h̄_{1}, …, h̄_{r}\}. More generally, let L(\underline{r}, v_{1}, …, v_{l}) denote the subspace generated by {h̄_{1}, …, h̄_{r}, h̄_{v_{1}}, …, h̄_{v_{l}}} where r + 1 < v_{1} < ⋯ < v_{l} for some l ≥ 0. Note that if l = 0 then L(\underline{r}, v_{1}, …, v_{l}) = L(\underline{r}).

Definition 1.12. If h_{i} = x_{1}^{i_{1}}x_{2}^{i_{2}} … x_{k}^{i_{k}} and h_{j} = x_{1}^{j_{1}}x_{2}^{j_{2}} … x_{k}^{j_{k}} then put h_{i,j} := x_{1}^{α_{1}}x_{2}^{α_{2}} … x_{k}^{α_{k}} where for l = 1, …, k,

α_{l} = \begin{cases}i_{l} + j_{l} & if i_{l} + j_{l} < q \\ i_{l} + j_{l} − (q − 1) & otherwise. \end{cases}

By this construction, h_{i,j} ≤_{t} h_{i}h_{j}. However, h_{i,j} and h_{i}h_{j} are equal as functions; i.e. when viewed as mappings from 𝔽_{q}^{k} into 𝔽_{q}, h_{i,j} and h_{i}h_{j} are identical.

Definition 1.13. Let h_{r} ∈ H. A monomial h is said to be consistent with h_{r} if h̄ ∈ L(\underline{r}) \ L(\underline{r − 1}) and wt(h) = wt(h_{r}). If h is consistent with h_{r}, then we write h ∼ h_{r}.

Lemma 1.14. If h <_{t} h_{r}, then h̄ ∈ L(\underline{r − 1}).

Proof. Suppose h <_{t} h_{r} and h̄ ∈ L(\underline{s}) for some s ≥ r. Then h+I_{q} = ∑_{i=1}^{s}(k_{i}h_{i})+I_{q} for some k_{i} ∈ 𝔽_{q} for 1 ≤ i ≤ s with k_{s} ≠ 0. Thus, f = ∑_{i=1}^{s}(k_{i}h_{i}) − h ∈ I_{q} and lm(f) = h_{s} since k_{s} ≠ 0 and h <_{t} h_{r} ≤_{t} h_{s}. This is a contradiction since the monomial h_{s} ∈ Δ(I_{q}). □

Corollary 1.15. If h ∼ h_{r}, then h_{r} ≤_{t} h.

Lemma 1.16. If h̄_{i,j} ∈ L(\underline{r})\L(\underline{r − 1}) and wt(h_{i})+wt(h_{j}) = wt(h_{r}), then h_{i}h_{j} = h_{i,j} ∼ h_{r}.

Proof. In order to show that h_{i,j} ∼ h_{r}, we only need to show that wt(h_{i,j}) = wt(h_{r}). If h_{i}h_{j} = h_{i,j} then the conclusion is satisfied. Assume h_{i}h_{j} ≠ h_{i,j}. Then we have wt(h_{i,j}) < wt(h_{i}) + wt(h_{j}) = wt(h_{r}). Hence, h_{i,j} <_{t} h_{r}. By Lemma 1.14, we have h̄_{i,j} ∈ L(\underline{r − 1}), which is a contradiction. □

Definition 1.17. Let h_{i}, h_{j} ∈ H such that wt(h_{i})+wt(h_{j}) ≤ wt(h_{n}) and h_{i,j} ∼ h_{r}. If for each pair (u, v) such that 1 ≤ u ≤ i, 1 ≤ v ≤ j and (u, v) ≠ (i, j) we have h̄_{u,v} ∈ L(\underline{r − 1}), then h_{i,j} is called a well-behaving term (consistent with h_{r}).

Lemma 1.18. Let h_{i}, h_{j}, and h_{r} ∈ H. If h_{i}h_{j} = h_{r} then h_{i,j} is a well-behaving term consistent with h_{r}.

Proof. Suppose h_{i}, h_{j}, h_{r} ∈ H such that h_{i}h_{j} = h_{r}. Then h_{r} = h_{i}h_{j} = h_{i,j}. Clearly, h_{i,j} ∼ h_{r}. Let (u, v) be such that 1 ≤ u ≤ i, 1 ≤ v ≤ j and (u, v) ≠ (i, j). Then h_{u,v} ≤_{t} h_{u}h_{v} <_{t} h_{i}h_{j} = h_{r}. Hence, h̄_{u,v} ∈ L(\underline{r − 1}). □

In Example 1.7, note that h_{4,4} = x_{1} = h_{2} although h_{4}h_{4} = x_{1}^{4}. Thus, h_{4,4} is consistent with h_{2}. However, h_{4,4} is not a well-behaving term since h̄_{1,2} ∈ L(\underline{2}). On the other hand, since x_{1}^{3} + x_{2}^{2} + x_{2} ∈ I_{q}, we have h_{2,4} = x_{1}^{3} ∼ x_{2}^{2} = h_{6}. Therefore, h_{2,4} ∼ h_{6}. Upon further inspection, h_{2,4} is in fact a well-behaving term.

Definition 1.19. Define N_{r} := {(i, j)|h_{i,j} is a well-behaving term consistent with h_{r}}. Put N_{r} := |N_{r}|.

In Example 1.7 N_{1} = 1, N_{2} = 2, N_{3} = 2, N_{4} = 3, N_{5} = 4, N_{6} = 5, N_{7} = 6, N_{8} = 8. Since x_{1}^{3} + x_{2}^{2} + x_{2} ∈ I_{q}, we have x_{1}^{3} ∼ x_{2}^{2} and x_{1}^{3}x_{2} ∼ x_{2}^{3}. Hence, the monomials h_{2,4} and h_{4,2} as well as h_{1,6}, h_{3,3}, and h_{6,1} are all consistent with h_{6}. Upon further inspection, they are all well-behaving terms also. Hence, N_{6} = 5. Also, the monomials h_{2,7}, h_{4,5}, h_{5,4}, and h_{7,2} as well as h_{1,8}, h_{3,6}, h_{6,3}, and h_{8,1} are all consistent with h_{8}. Upon further inspection, they are all well-behaving terms also. Hence, N_{8} = 8.

Lemma 1.20. For 1 ≤ r ≤ n, N_{r} is uniquely expressible as

N_{r} = {(i_{1}, j_{1}), …, (i_{N_{r}}, j_{N_{r}})}

where i_{1} = j_{N_{r}} < i_{2} = j_{N_{r}−1} < ⋯ < i_{N_{r}} = j_{1}.

Proof. Let (i_{α}, j_{α}) and (i_{β}, j_{β}) be distinct elements of N_{r}, where without loss of generality, we may assume i_{α} ≤ i_{β}. Assume j_{α} ≤ j_{β}. Then i_{α} ≤ i_{β} and j_{α} ≤ j_{β} with (i_{α}, j_{α}) ≠ (i_{β}, j_{β}) along with h_{i_{α},j_{α}} ∼ h_{r} imply that h_{i_{β},j_{β}} is not a well-behaving term. This is a contradiction. Thus, j_{β} < j_{α}. Suppose i_{α} = i_{β}, then j_{β} < j_{α} and h_{i_{β},j_{β}} ∼ h_{r} imply h_{i_{α},j_{α}} is not a well-behaving term. This is also a contradiction. Thus, for 1 ≤ l ≤ N_{r}, each i_{l} is distinct. Also, since h_{i,j} = h_{j,i} then (i, j) ∈ N_{r} implies that (j, i) ∈ N_{r}. □

Proposition 1.21. For h_{r} = x_{1}^{r_{1}} … x_{n}^{r_{n}} ∈ H, N_{r} ≥ ∏_{i=1}^{n}(r_{i} + 1).

Proof. For each divisor d of h_{r}, we have d ∈ H and \frac{h_{r}}{d} ∈ H by Remark 1.9. There are ∏_{i=1}^{n}(r_{i} + 1) such divisors. Thus each divisor yields a distinct pair (i, j) such that h_{i}h_{j} = h_{r}. By Lemma 1.18, each such h_{i,j} is a well-behaving term consistent with h_{r}. □

It is easy to see that N_{r} can be strictly greater than just the number of monomial divisors of h_{r}. Consider h_{6} = x_{2}^{2} from Example 1.7. The number of divisors of x_{2}^{2} is 3 and N_{6} = 5.

Definition 1.22. Let H_{r} denote the r×n matrix defined by H_{r} := [h_{i}(P_{j})], where 1 ≤ i ≤ r and 1 ≤ j ≤ n. Note that H_{r} is a parity check matrix for the affine variety code C^{⊥}(I, L(\underline{r})).

Definition 1.23. Consider the code C^{⊥}(I, L) where L = L(\underline{r}, v_{1}, …, v_{l}). Define

H_{r}^{∗} := (\begin{matrix}& H_{r} \\ h_{v_{1}}(P_{1}) & ⋯ & h_{v_{1}}(P_{n}) \\ ⋮ & ⋮ & ⋮ \\ h_{v_{l}}(P_{1}) & ⋯ & h_{v_{l}}(P_{n}) \end{matrix}) .

Note that H_{r}^{∗} is a parity check matrix for C^{⊥}(I, L) and if l = 0, then H_{r}^{∗} = H_{r}.

We will now discuss the minimum distance of the codes with parity check matrix H_{r}^{∗}. Let h′_{i} := (h_{i}(P_{1}), …, h_{i}(P_{n})) and h′_{i,j} := (h_{i,j}(P_{1}), …, h_{i,j}(P_{n})). For each c = (c_{1}, …, c_{n}) ∈ 𝔽_{q}^{n}, 1 ≤ i ≤ n, and 1 ≤ j ≤ n define the following syndromes: s_{i}(c) := h′_{i}c^{T} and S_{i,j}(c) := h′_{i,j}c^{T}. Note that if c is a codeword, then s_{i}(c) = 0 for i = 1, 2, …, r, v_{1}, v_{2}, …, v_{l}, and that S_{i,j}(c) = 0 if h̄_{i,j} ∈ L(\underline{r}, v_{1}, …, v_{l}). Let S_{c} := [S_{i,j}(c)] be the n × n matrix of syndromes. Since h_{i,j} and h_{i}h_{j} are equal as functions, then S_{c} = H_{n}D(c)H_{n}^{T} where D(c) is the diagonal n × n matrix with c on the diagonal,

D(c) = (\begin{matrix}c_{1} & 0 & … & 0 \\ 0 & c_{2} & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & … & 0 & c_{n} \end{matrix}) .

The square matrix H_{n} must have full rank. For if there existed k_{1}, …, k_{r} ∈ 𝔽_{q} such that ∑_{i=1}^{n}(k_{i}h′_{i}) = (0, …, 0), then the function f = ∑_{i=1}^{n}(k_{i}h_{i}) must vanish at each of the points P_{1}, …, P_{n}. Hence, f ∈ I(V (I_{q})) = I_{q} since I_{q} is radical. However, lm(f) ∈ H implies that lm(f) ∈ Δ(I_{q}), which is a contradiction. Since H_{n} and H_{n}^{T} both have full rank, then we have rank S_{c} = rank D(c) = wt(c). Proposition 1.24. Suppose c = (c_{1}, …, c_{n}) is a codeword of the code with parity check matrix H_{r}^{∗}. If s_{r+1}(c) ≠ 0, then wt(c) ≥ N_{r+1}. Proof. Since c is a codeword, then s_{i}(c) = 0 for 1 ≤ i ≤ r. For each of the N_{r+1}- many h_{i,j} which are well-behaving terms consistent with h_{r+1}, we have S_{i,j}(c) ≠ 0. This follows since each h̄_{i,j} ∈ L(\underline{r + 1}) \ L(\underline{r}) implies h_{i,j} + I_{q} = ∑_{i=1}^{r+1}(k_{i}h_{i}) + I_{q} for some k_{i} ∈ 𝔽_{q}, 1 ≤ i ≤ r + 1 with k_{r+1} ≠ 0. Thus, there exists a polynomial f ∈ I_{q} such that h_{i,j} = ∑_{i=1}^{r+1}(k_{i}h_{i}) + f. Then,

h′_{i,j} = ∑_{i=1}^{r+1}(k_{i}h′_{i}) + (f(P_{1}), …, f(P_{n})).

Since f ∈ I_{q}, we have

S_{i,j}(c) = ∑_{i=1}^{r+1}(k_{i}h′_{i}c^{T}) + (0, …, 0)c^{T} = ∑_{i=1}^{r+1}(k_{i}s_{i}(c)) = k_{r+1}s_{r+1}(c)

since s_{i}(c) = 0 for 1 ≤ i ≤ r. Since k_{r+1} ≠ 0 and s_{r+1}(c) ≠ 0, we have S_{i,j}(c) ≠ 0. However, h_{i,j} a well-behaving term implies that for each pair (u, v) such that 1 ≤ u ≤ i, 1 ≤ v ≤ j and (u, v) ≠ (i, j) we have h̄_{u,v} ∈ L(\underline{r}). Thus S_{u,v}(c) = 0. Let N_{r+1} = {(i_{1}, j_{1}), …, (i_{N_{r+1}}, j_{N_{r+1}})} where i_{1} = j_{N_{r+1}} < i_{2} = j_{N_{r}} < ⋯ < i_{N_{r+1}} = j_{1} as denoted in Lemma 1.20. For 1 ≤ l ≤ N_{r+1}, the j_{l}-th row of the matrix S_{c} has zeros in the first i_{l} − 1 entries and the i_{l}th entry, namely S_{i_{l},j_{l}}(c), is nonzero. Since i_{1} < i_{2} < ⋯ < i_{N_{r+1}}, then the set of rows {h′_{j_{1}}, …, h′_{j_{N_{r+1}}}} are linearly independent. Hence, rank S_{c} = wt(c) ≥ N_{r+1}. □

Theorem 1.25. Suppose H_{r}^{∗} is a parity check matrix of a nontrivial linear code. Let δ′ := min{N_{v}|v ∉ {1, …, r, v_{1}, …, v_{l}}}, then the code has minimum distance at least δ′. In this case, δ′ is called the Feng-Rao bound for the minimum distance.

Proof. Let c be a nonzero codeword. Let p be the smallest index such that s_{u}(c) = 0 for 1 ≤ u ≤ p and s_{p+1}(c) ≠ 0. Let’s show the existence of such a p < n. Assume s_{u}(c) = 0 for 1 ≤ u ≤ n. Then h′_{u}c^{T} = 0 for 1 ≤ u ≤ n. Therefore, c ∈ C^{⊥}(I, L(\underline{n})). However, C^{⊥}(I, L(\underline{n})) has dimension 0. Thus, c = (0, …, 0). This is a contradiction. Note that p + 1 ∉ {1, …, r, v_{1}, …, v_{l}} since c is a codeword. However, c is also a codeword for C^{⊥}(I, L(\underline{p})). By Proposition 1.24, we know that wt(c) ≥ N_{p+1} ≥ δ′. □

Suppose you desire a code of length n to have a designed minimum distance of δ. Simply construct an affine variety code C^{⊥}(I, L) where V (I_{q}) has n points and L is the linear subspace of the coordinate ring R spanned by {h̄_{i}|h_{i} ∈ H, N_{i} < δ}. Then L can be expressed in the form L(\underline{r}, v_{1}, …, v_{l}) where

(i) for 1 ≤ v ≤ r, we have N_{v} < δ;
(ii) N_{r+1} ≥ δ;
(iii) for r + 1 < v ≤ n, if N_{v} < δ then v ∈ {v_{1}, …, v_{l}}.

For the case when I defines a plane curve that has one point at infinity, these codes are the so-called “improved” geometric Goppa codes of Feng and Rao [4]. They are constructed by starting with the usual geometric Goppa code where L = L(1, 2, …, v_{l}) which has the same minimum distance bound δ. The above construction deletes certain generators of L(1, 2, …, v_{l}) while maintaining the same minimum distance bound. When generators are deleted, the dimension of L is decreased, which in turn increases the dimension of the code C^{⊥}(I, L), thereby forming an “improved” code. Note that δ′ as defined in Theorem 1.25 is also a lower bound on the minimum distance of the constructed code. Note that δ ≤ δ′. Therefore, in order to obtain a tighter lower bound, we may assume δ = N_{v} for some v.

Thus, the minimum distance of the code C^{⊥}(I, L), where L = L(\underline{r}, v_{1}, …, v_{l}), is bounded below by some N_{v}. Recall, N_{v} depends on the number of h_{i,j} ∼ h_{v} (i.e., wt(h_{i,j}) = wt(h_{v}) and h̄_{i,j} ∈ L(\underline{v}) \ L(\underline{v − 1})). Hence, in order to increase the bound on the minimum distance, we must increase the number of such h_{i,j}. To accomplish this it is beneficial to assign the weights of each of the variables such that each generator polynomial of I has at least two monomials of equal weight. In Example 1.7, by assigning wt(x_{1}) = 2 and wt(x_{2}) = 3, we obtain wt(x_{1}^{3}) = wt(x_{2}^{2}) for the lone generator polynomial x_{1}^{3} + x_{2}^{2} + x_{2}. Definition 1.26. Define P_{r} := {(i, j)|wt(h_{i}) + wt(h_{j}) = wt(h_{r})}. Theorem 1.27. Let V (I_{q}) be an affine variety, where I is an ideal in 𝔽_{q}[x_{1}, …, x_{n}]. Let H be the monomial sequence obtained from Δ(I_{q}). Then N_{r} ⊆ P_{r}. Proof. Let (i, j) ∈ N_{r}. Suppose h_{i} = x_{1}^{i_{1}} … x_{n}^{i_{n}} and h_{j} = x_{1}^{j_{1}} … x_{n}^{j_{n}} ∈ H. We know i_{l} ≤ q − 1 and j_{l} ≤ q − 1 for 1 ≤ l ≤ n. Consider the monomials h_{u} = x_{1}^{u_{1}} … x_{n}^{u_{n}} and h_{v} = x_{1}^{v_{1}} … x_{n}^{v_{n}} where for 1 ≤ l ≤ n :

u_{l} = \begin{cases}i_{l} + j_{l} − (q − 1) & if i_{l} + j_{l} ≥ q \\ i_{l} & otherwise \end{cases}

and

v_{l} = \begin{cases}0 & if i_{l} + j_{l} ≥ q \\ j_{l} & otherwise. \end{cases}

Note that u_{l} ≤ i_{l} and v_{l} ≤ j_{l} for 1 ≤ l ≤ n. Therefore, h_{i} is a multiple of h_{u} and h_{j} is a multiple of h_{v}. Thus h_{u}, h_{v} ∈ H. Assume there exists an l such that i_{l} + j_{l} ≥ q.

Then, h_{u} ≤_{t} h_{i} and h_{v} <_{t} h_{j}. This implies that u ≤ i, v < j and (u, v) ≠ (i, j). However, by construction h_{u,v} = h_{i,j} ∼ h_{r}, so that h̄_{u,v} ∈ L(\underline{r}) \ L(\underline{r − 1}). Thus, h_{i,j} is not a well-behaving term, which is a contradiction. Therefore, i_{l} + j_{l} < q for 1 ≤ l ≤ n, and so h_{i}h_{j} = h_{i,j}. Hence wt(h_{i}) + wt(h_{j}) = wt(h_{i,j}) = wt(h_{r}), since h_{i,j} ∼ h_{r}, which implies that (i, j) ∈ P_{r}. □

Therefore a necessary condition for h_{i,j} to be a well-behaving term consistent with h_{r} is that it must satisfy: wt(h_{i}) + wt(h_{j}) = wt(h_{r}). Corollary 1.28. If (i, j) ∈ N_{r}, then h_{i,j} = h_{i}h_{j}. Example 1.29. Let I be the principal ideal in 𝔽_{8}[x_{1}, x_{2}] generated by the polynomial x_{1}^{3} + x_{1}x_{2}^{3} + x_{2}. This is known as the affine Klein quartic curve over 𝔽_{8}. The variety V (I_{q}) contains 22 points. Let wt(x_{1}) = 3 and wt(x_{2}) = 2. Then we have

Δ(I_{q}) = {x_{1}^{α}x_{2}^{β}|0 ≤ α ≤ 2, 0 ≤ β ≤ 7, and if α > 0, then β < 7}.

Thus, the H-sequence is

{1, x_{2}, x_{1}, x_{2}^{2}, x_{1}x_{2}, x_{2}^{3}, x_{1}^{2}, x_{1}x_{2}^{2}, …, x_{1}^{2}x_{2}^{6}}.

Note that

P_{6} = P_{7} = {(1, 7), (1, 6), (2, 4), (3, 3), (4, 2), (6, 1), (7, 1)}.

However, N_{6} = {(1, 6), (2, 4), (4, 2), (6, 1)} and N_{7} = {(1, 7), (3, 3), (7, 1)}. Hence, N_{6} ≠ P_{6} and N_{7} ≠ P_{7}.

Whenever wt(h_{i}) = wt(h_{j}), we have P_{i} = P_{j}. However, since N_{i} and N_{j} are disjoint, we know that N_{i} ≠ P_{i} and/or N_{j} ≠ P_{j}. In the next section we will discuss a class of codes in which N_{r} = P_{r} for each r. Remark 1.30. Kirfel and Pellikaan [7] defined a minimum distance bound which they originally called the Feng-Rao bound, but which was later renamed the order bound [5]. This bound is related to the sets P_{r} defined above. The Feng-Rao bound is tighter than the order bound to the true minimum distance. However, for Type I curves, it follows from Theorem 1.35 that these bounds are identical.

1.3 Type I Curves

Definition 1.31. If wt(h_{i}) < wt(h_{i+1}) for 1 ≤ i ≤ n − 1, then the H-sequence is said to contain distinct weights. Lemma 1.32. If the H-sequence contains distinct weights, then

N_{r} = {(i, j)|h_{i,j} ∼ h_{r}}.

Proof. We need to show that if h_{i,j} ∼ h_{r} then h_{i,j} is a well-behaving term. For any u ≤ i and v ≤ j with (u, v) ≠ (i, j), we have that

wt(h_{u,v}) ≤ wt(h_{u}) + wt(h_{v}) < wt(h_{i}) + wt(h_{j}) = wt(h_{r}).

Hence, h̄_{u,v} ∈ L(\underline{r − 1}). □ Definition 1.33. The affine plane curves over 𝔽_{q} defined by the principal ideal I = ⟨x_{1}^{a} + x_{2}^{b} + f(x_{1}, x_{2})⟩ ⊆ 𝔽_{q}[x_{1}, x_{2}] where gcd(a, b) = 1 and deg f < min{a, b} are the so-called Type I curves of Feng and Rao. We may assume that a < q and b < q.

Given a Type I curve, we set wt(x_{1}) = b and wt(x_{2}) = a so that wt(x_{1}^{a}) = wt(x_{2}^{b}). Let H = {h_{i}}_{i=1}^{n} be the corresponding sequence of the elements of Δ(I_{q}). Proposition 1.34. For Type I curves, H contains distinct weights. Proof. Since x_{1}^{a} + x_{2}^{b} + f(x_{1}, x_{2}) ∈ I_{q}, its leading monomial, x_{1}^{a} ∉ Δ(I_{q}). Thus, any multiple of x_{1}^{a} is not in Δ(I_{q}). Suppose there exists two monomials of H, h_{i} = x_{1}^{i_{1}}x_{2}^{i_{2}} and h_{j} = x_{1}^{j_{1}}x_{2}^{j_{2}} where i_{1} < a and j_{1} < a such that wt(h_{i}) = wt(h_{j}). Then i_{1}b + i_{2}a = wt(h_{i}) = wt(h_{j}) = j_{1}b + j_{2}a implies that a(i_{2} − j_{2}) = b(j_{1} − i_{1}).

However, |j_{1} − i_{1}| < a and gcd(a, b) = 1 imply that i_{1} = j_{1} and i_{2} = j_{2}. Thus, h_{i} = h_{j}. Hence, H contains distinct weights. □ Theorem 1.35. For Type I curves, P_{r} = N_{r} for 1 ≤ r ≤ n. Proof. By Lemma 1.32 and Proposition 1.34, we know that N_{r} = {(i, j)|h_{i,j} ∼ h_{r}}. By Theorem 1.27, it suffices to show that (i, j) ∈ P_{r} implies that h_{i,j} ∼ h_{r}. Suppose h_{i} = x_{1}^{i_{1}}x_{2}^{i_{2}}, h_{j} = x_{1}^{j_{1}}x_{2}^{j_{2}}, and h_{r} = x_{1}^{r_{1}}x_{2}^{r_{2}} are members of H such that wt(h_{i}) + wt(h_{j}) = wt(h_{r}). Since i_{1}, j_{1}, and r_{1} are each less than a, then either h_{r} = h_{i}h_{j} or h_{r} = h_{i}h_{j}x_{1}^{−a}x_{2}^{b} = x_{1}^{i_{1}+j_{1}−a}x_{2}^{i_{2}+j_{2}+b}. If h_{r} = h_{i}h_{j}, then by Lemma 1.18, the conclusion is satisfied. We may assume that h_{r} ≠ h_{i}h_{j}. Then, i_{1} + j_{1} = r_{1} + a and i_{2} + j_{2} + b = r_{2}. Therefore,

h_{i}h_{j} = x_{1}^{r_{1}+a}x_{2}^{r_{2}−b} = x_{1}^{r_{1}}x_{2}^{r_{2}−b}(g − x_{2}^{b} − f) = x_{1}^{r_{1}}x_{2}^{r_{2}−b}g − h_{r} − x_{1}^{r_{1}}x_{2}^{r_{2}−b}f

where g = x_{1}^{a} + x_{2}^{b} + f(x_{1}, x_{2}), the defining polynomial for the ideal I. Now, x_{1}^{r_{1}}x_{2}^{r_{2}−b}g ∈ I_{q} and wt(h_{r}) > wt(x_{1}^{r_{1}}x_{2}^{r_{2}−b}lm(f)). Therefore, h̄_{i}h̄_{j} ∈ L(\underline{r}) \ L(\underline{r − 1}). To apply Lemma 1.16, we want h̄_{i,j} ∈ L(\underline{r}) \ L(\underline{r − 1}). Assume that h_{i,j} ≠ h_{i}h_{j}. Since r_{2} − b < q, we have r_{1} + a ≥ q. Thus, h_{i}h_{j} − h_{i,j} = p(x_{1}, x_{2})(x_{1}^{q} − x_{1}) for some polynomial p(x_{1}, x_{2}). Since x_{1}^{q} − x_{1} ∈ I_{q}, we have h̄_{i,j} = h̄_{i}h̄_{j}. Hence, h̄_{i,j} ∈ L(\underline{r}) \ L(\underline{r − 1}) and by Lemma 1.16, h_{i,j} ∼ h_{r}. □. Definition 1.36. A special class of Type I curves are the Hermitian curves. They are curves in which I = ⟨x_{1}^{q} + x_{2}^{q+1} + x_{1}⟩ ⊆ 𝔽_{q^{2}}[x_{1}, x_{2}]. The variety V (I_{q^{2}}) has q^{3} rational points. Remark 1.37. In Definition 1.36, we could have also included ideals of the form I^{∗} = ⟨x_{2}^{q} + x_{1}^{q+1} + x_{2}⟩. Their footprints, Δ(I_{q^{2}}) and Δ(I_{q^{2}}^{∗}) are not equal. However, for their respective monomial sequences, H = {h_{i}}_{i=1}^{q^{3}} and H^{∗} = {h_{i}^{∗}}_{i=1}^{q^{3}}, we do have the property that wt(h_{i}) = wt(h_{i}^{∗}) for 1 ≤ i ≤ n = q^{3}. Since P_{r} = N_{r} for 1 ≤ r ≤ n, the codes C^{⊥}(I, L) and C^{⊥}(I^{∗}, L) where L = L(\underline{r}, v_{1}, …, v_{l}) have the exact same minimum distance bound. Since the length, dimension, and minimum distance bounds are equal, we can simply examine the case as stated in the definition.

For Hermitian curves,

Δ(I_{q^{2}}) = {x_{1}^{α_{1}}x_{2}^{α_{2}}|0 ≤ α_{1} ≤ q − 1 and 0 ≤ α_{2} ≤ q^{2} − 1}.

For h_{r} = x_{1}^{r_{1}}x_{2}^{r_{2}} ∈ H we can compute N_{r}. Since the x_{1} exponent of any monomial in the H-sequence is bounded above by q − 1, we have

\begin{aligned}N_{r} & = P_{r} = \{(i, j)|wt(h_{i}) + wt(h_{j}) = wt(h_{r})\} \\ & = \{(i, j)|h_{i}h_{j} = h_{r} or h_{i}h_{j} = x_{1}^{r_{1}+q}x_{2}^{r_{2}−q−1}\}. \end{aligned}

Thus,

N_{r} = |N_{r}| = |{monomial divisors of either h_{r} or x_{1}^{r_{1}+q}x_{2}^{r_{2}−q−1}}|

= \begin{cases}(r_{1} + 1)(r_{2} + 1) & if r_{2} ≤ q \\ (r_{1} + 1)(r_{2} + 1) + (q − r_{1} − 1)(r_{2} − q) & otherwise. \end{cases}

Example 1.38. Consider the Hermitian curve over 𝔽_{9} defined by the principal ideal I = ⟨x_{1}^{3} + x_{2}^{4} + x_{1}⟩ ⊆ 𝔽_{9}[x_{1}, x_{2}]. We set wt(x_{1}) = 4 and wt(x_{2}) = 3. Also, Δ(I_{9}) = {x_{1}^{α_{1}}x_{2}^{α_{2}}|0 ≤ α_{1} ≤ 2 and 0 ≤ α_{2} ≤ 8}. Therefore, the H-sequence is

{1, x_{2}, x_{1}, x_{2}^{2}, x_{1}x_{2}, x_{1}^{2}, x_{2}^{3}, …, x_{1}^{2}x_{2}^{8}}.

Then, N_{1} = 1, N_{2} = 2, N_{3} = 2, N_{4} = 3, N_{5} = 4, N_{6} = 3, N_{7} = 4. Also, for r ≥ 8 we have N_{r} ≥ 6. Hence, the affine variety code C^{⊥}(I, L(\underline{7})) over 𝔽_{9} has length 27, dimension 20, and minimum distance at least 6.

Chapter 2 Codes on Fermat Surfaces

2.1 Gröbner Bases

In this section we will introduce some Gröbner basis theory necessary for the subsequent sections of this chapter. We shall mostly follow the notation and terminology of Adams and Loustaunau [1]. Fix a monomial ordering. Definition 2.1. Let f and g be two nonzero polynomials in 𝔽_{q}[x_{1}, …, x_{k}]. We say that f reduces to r modulo g (or by g) in one step, denoted by

f ⟶^{g} r,

if and only if lm(g) divides a nonzero term X that appears in f and

r = f − \frac{X}{lt(g)}g.

Note that we have subtracted from the polynomial f the entire term X and have replaced it with strictly smaller terms under our ordering. For the case when X = lt(f), we are applying the division algorithm to f by dividing by g and receiving r as our remainder. Definition 2.2. Let f, r and f_{1}, …, f_{l} be polynomials in 𝔽_{q}[x_{1}, …, x_{k}] with f_{i} ≠ 0 for 1 ≤ i ≤ l and let F = {f_{1}, …, f_{l}}. We say that f reduces to r modulo F, denoted by

f ⟶^{F}_{+} r,

if and only if there exist a sequence of indices i_{1}, i_{2}, …, i_{s} ∈ {1, …, l} and a sequence of polynomials r_{1}, …, r_{s−1} ∈ 𝔽_{q}[x_{1}, …, x_{k}] such that

f ⟶^{f_{i_{1}}} r_{1} ⟶^{f_{i_{2}}} r_{2} ⟶^{f_{i_{3}}} ⋯ ⟶^{f_{i_{s−1}}} r_{s−1} ⟶^{f_{is}} r.

Definition 2.3. A polynomial r is called reduced with respect to a set of nonzero polynomials F = {f_{1}, …, f_{l}} if either r = 0 or no monomial that appears in r is divisible by some lm(f_{i}) where 1 ≤ i ≤ l. Definition 2.4. A set of nonzero polynomials G = {g_{1}, …, g_{l}} contained in an ideal I is called a Gröbner basis for I if and only if for each nonzero polynomial f ∈ I there exists some i, where 1 ≤ i ≤ l, such that lm(g_{i}) divides lm(f). Theorem 2.5. Let I be a nonzero ideal of 𝔽_{q}[x_{1}, …, x_{k}]. The following statements are equivalent for a set of nonzero polynomials G = {g_{1}, …, g_{l}} ⊆ I.

(i) G is a Gröbner basis for I.
(ii) f ∈ I if and only if f ⟶^{G}_{+} 0.
(iii) Δ(I) = {x_{1}^{α_{1}} … x_{k}^{α_{k}}|For each i, 1 ≤ i ≤ l, we have lm(g_{i}) ∤ x_{1}^{α_{1}} … x_{k}^{α_{k}}}.

Proof. (i) ⇒ (ii) Let f be a polynomial. Then there exists an r such that f ⟶^{G}_{+} r, where r is reduced with respect to G. Thus, f − r ∈ ⟨G⟩ ⊆ I. Hence, f ∈ I if and only if r ∈ I. Clearly, if r = 0 (i.e. f ⟶^{G}_{+} 0) then f ∈ I. Conversely, suppose f ∈ I. Then r ∈ I and by (i), there exists g_{i} ∈ G such that lm(g_{i})|lm(r). However, since r is reduced with respect to G, we must have r = 0.

(ii) ⇒ (iii) Put

A = {x_{1}^{α_{1}} … x_{k}^{α_{k}}|For each i, 1 ≤ i ≤ l, we have lm(g_{i}) ∤ x_{1}^{α_{1}} … x_{k}^{α_{k}}}.

Since {g_{1}, …, g_{l}} ⊆ I, we have Δ(I) ⊆ A. Suppose x_{1}^{α_{1}} … x_{k}^{α_{k}} ∉ Δ(I). Then, there exists a polynomial f ∈ I such that lm(f) = x_{1}^{α_{1}} … x_{k}^{α_{k}}. By (ii), f reduces to 0 modulo G. Therefore, there exists g_{i} ∈ G such that lm(g_{i})|x_{1}^{α_{1}} … x_{k}^{α_{k}}. Hence, x_{1}^{α_{1}} … x_{k}^{α_{k}} ∉ A.

(iii) ⇒ (i) Suppose f ∈ I. Then we have lm(f) ∉ Δ(I). By (iii), there exists g_{i} ∈ G such that lm(g_{i})|lm(f). □

Lemma 2.6. Let G = {g_{1}, …, g_{l}} be a Gröbner basis for I ⊆ 𝔽_{q}[x_{1}, …, x_{k}]. Then for all f ∈ 𝔽_{q}[x_{1}, …, x_{k}] the reduction of f with respect to G is unique.

Proof. Suppose f ⟶^{G}_{+} r_{1} and f ⟶^{G}_{+} r_{2} with r_{1} and r_{2} reduced with respect to G. Note that f − r_{1} ∈ I and f − r_{2} ∈ I. Therefore, r_{1} − r_{2} ∈ I. Since r_{1} − r_{2} is reduced with respect to G, we must have r_{1} − r_{2} = 0. □

Remark 2.7. Let I be an ideal in 𝔽_{q}[x_{1}, …, x_{k}]. Let G be a Gröbner basis for I_{q}. Let f be a polynomial in 𝔽_{q}[x_{1}, …, x_{k}]. Suppose f ∉ I_{q} and let c_{1}x^{β_{1}} + ⋯ + c_{s}x^{β_{s}} (where x^{β_{s}} <_{t} ⋯ <_{t} x^{β_{1}}) be the unique reduction of f with respect to G. Then x^{β_{1}}, …, x^{β_{s}} are in Δ(I_{q}). Suppose x^{β_{1}} = h_{r}, the r-th element in the H-sequence (cf. Definition 1.8). Then, f̄ ∈ L(\underline{r}) \ L(\underline{r − 1}).

Indeed, since f + I_{q} = c_{1}x^{β_{1}} + ⋯ + c_{s}x^{β_{s}} + I_{q}, we have f ∈ L(\underline{r}). Assume f ∈ L(\underline{r − 1}). Then f + I_{q} = ∑_{i=1}^{r−1} k_{i}h_{i} + I_{q} where k_{i} ∈ 𝔽_{q} for 1 ≤ i ≤ r − 1. Thus,

c_{1}x^{β_{1}} + I_{q} = ∑_{i=1}^{r−1} k_{i}h_{i} − (c_{2}x^{β_{2}} + ⋯ + c_{s}x^{β_{s}}) + I_{q}

implies that h_{r} ∈ L(\underline{r − 1}), which is a contradiction.

Corollary 2.8. Let h_{i}, h_{j} ∈ H and suppose h_{i,j} ∉ I_{q}. Reduce h_{i,j} with respect to a Gröbner basis G for I_{q}. Let h_{r} be the leading monomial of the reduction. Then h_{i,j} ∼ h_{r} if and only if wt(h_{i,j}) = wt(h_{r}).

Note that Remark 2.7 implies that h_{i,j} can only be consistent with the leading monomial of its reduction with respect to the Gröbner basis G. Also, there is a discrepancy for the case when h_{i,j} ∈ I_{q}. In this case the reduction of h_{i,j} with respect to G is 0. Clearly, h_{i,j} cannot be consistent with any h_{r}. However, when we examine the Fermat surfaces in Section 2.4, this case will not play a role.

Definition 2.9. Let f and g be nonzero polynomials in 𝔽_{q}[x_{1}, …, x_{k}]. Put L = lcm(lm(f), lm(g)). The S-polynomial of f and g, denoted by S(f, g), is defined as

S(f, g) = \frac{L}{lt(f)}f − \frac{L}{lt(g)}g.

These S-polynomials play a vital role in the computation of a Gröbner basis. More specifically, we are interested in the reduction of S-polynomials of any two polynomials in the Gröbner basis as demonstrated by Buchberger’s Criterion [1]. Theorem 2.10. (Buchberger’s Criterion) Let G = {g_{1}, …, g_{l}} be a set of nonzero polynomials in 𝔽_{q}[x_{1}, …, x_{k}]. Then G is a Gröbner basis for the ideal I = ⟨g_{1}, …, g_{l}⟩ if and only if for all i ≠ j, we have S(g_{i}, g_{j}) ⟶^{G}_{+} 0. Proof. See [1]. □

From this Criterion we have a procedure, known as Buchberger’s Algorithm, for computing a Gröbner basis. We can begin with the initial generators of our ideal I, say f_{1}, …, f_{l}, and determine the S-polynomial of any two generators. Then reduce the S-polynomial with respect to the set of generators. If the reduction is nonzero, then add it to your set of generators for I.

Repeat the process of computing reductions of S-polynomials of pairs of generators from this “growing” set of generators. Eventually, after adding enough reductions to your generator set all S-polynomials of pairs of generators will reduce to zero with respect to the final set of generators (cf. [1]). This set will be a Gröbner basis for the ideal I. The algorithm is shown below.

As an easy consequence of Definition 2.4, we have Lemma 2.11. Suppose G = {g_{1}, …, g_{l}} is a Gröbner basis for the ideal I. If lm(g_{2}) divides lm(g_{1}), then {g_{2}, …, g_{l}} is also a Gröbner basis for I. Proof. See [1]. □

Buchberger’s Algorithm

INPUT: F = {f_{1}, …, f_{l}} ⊆ 𝔽_{q}[x_{1}, …, x_{k}] with f_{i} ≠ 0 for 1 ≤ i ≤ l OUTPUT: G = {g_{1}, …, g_{s}}, a Gröbner basis for ⟨f_{1}, …, f_{l}⟩ INITIALIZATION: G := F, G := {{f_{i}, f_{j}}|f_{i} ≠ f_{j} ∈ G} WHILE G ≠ ∅ DO

Choose any {f, g} ∈ G G := G \ {{f, g}} S(f, g) ⟶^{G} r, where r is reduced with respect to G. IF r ≠ 0 THEN

G := G ∪ {{u, r}| for all u ∈ G}.
G := G ∪ {r}

Definition 2.12. A Gröbner basis G = {g_{1}, …, g_{l}} is called a reduced Gröbner basis if, for all i, lm(g_{i}) = lt(g_{i}) and g is reduced with respect to G \ {g_{i}}, i.e. no term that appears in g_{i} is divisible by lm(g_{j}) for some j ≠ i.

2.2 Higher-Dimensional Varieties

We now direct our attention to codes defined over higher-dimensional varieties of the form V (I_{q}) where I_{q} ⊆ 𝔽_{q}[x_{1}, …, x_{k}] for some k ≥ 3. In this section we will consider principal ideals I = ⟨g⟩ with the following properties:

\begin{matrix}(i) & g(x_{1}, …, x_{k}) = x_{1}^{d} + f(x_{2}, …, x_{k}) \\ (ii) & lm(g) = x_{1}^{d} \\ (iii) & d|(q − 1) \end{matrix}

Define n := (q − 1)/d. Following Buchberger’s Algorithm, we will construct a Gröbner basis for the ideal I_{q} = ⟨g, f_{1}, …, f_{k}⟩ where f_{i} := x_{i}^{q} − x_{i} for 1 ≤ i ≤ k.

Consider the S-polynomials. We have separated all possible S-polynomials into 12 various types.

(1) \begin{aligned}S(g, f_{1}) & = \frac{x_{1}^{q}}{x_{1}^{d}} g − \frac{x_{1}^{q}}{x_{1}^{q}} f_{1} = x_{1}^{q−d}g − f_{1} = x_{1}^{q} + x_{1}^{q−d}f(x_{2}, …, x_{k}) − x_{1}^{q} + x_{1} \\ & = x_{1}^{q−d}f(x_{2}, …, x_{k}) + x_{1} \end{aligned}

which can be reduced successively by g an additional n − 1 times to obtain

S(g, f_{1}) ⟶^{g}_{+} x_{1}((−1)^{n+1}[f(x_{2}, …, x_{k})]^{n} + 1).

This can be further reduced, if necessary, by some of the f_{i}. If there exists an exponent e_{i} ≥ q of x_{i} in the expansion of [f(x_{2}, …, x_{k})]^{n}, then reduce the previous reduction by f_{i}. In essence, such a reduction replaces x_{i}^{q} with x_{i} whenever possible.

(2)  \begin{aligned}For i ≥ 2, S(g, f_{i}) & = \frac{x_{1}^{d}x_{i}^{q}}{x_{1}^{d}} g − \frac{x_{1}^{d}x_{i}^{q}}{x_{i}^{q}} f_{i} = x_{i}^{q}g − x_{1}^{d}f_{i} \\ & = x_{1}^{d}x_{i}^{q} + x_{i}^{q}f − x_{1}^{d}x_{i}^{q} + x_{1}^{d}x_{i} = x_{i}^{q}f + x_{1}^{d}x_{i}, \end{aligned}

which can be reduced by both f_{i} and g.

S(g, f_{i}) ⟶^{f_{i}} x_{i}^{q}f + x_{1}^{d}x_{i} − f(f_{i}) = x_{1}^{d}x_{i} + x_{i}f ⟶^{g} x_{1}^{d}x_{i} + x_{i}f − x_{i}g = x_{i}f − x_{i}f = 0.

(3)  \begin{aligned}S(f_{i}, f_{j}) & = \frac{x_{i}^{q}x_{j}^{q}}{x_{i}^{q}} f_{i} − \frac{x_{i}^{q}x_{j}^{q}}{x_{j}^{q}} f_{j} = x_{j}^{q}f_{i} − x_{i}^{q}f_{j} \\ & = x_{i}^{q}x_{j}^{q} − x_{i}x_{j}^{q} − x_{i}^{q}x_{j}^{q} + x_{i}^{q}x_{j} = x_{i}^{q}x_{j} − x_{i}x_{j}^{q}, \end{aligned}

which can be reduced by both f_{i} and f_{j}.

S(f_{i}, f_{j}) ⟶^{f_{i}} x_{i}^{q}x_{j}−x_{i}x_{j}^{q}−x_{j}f_{i} = x_{i}x_{j}−x_{i}x_{j}^{q} ⟶^{f_{j}} x_{i}x_{j}−x_{i}x_{j}^{q}+x_{i}f_{j} = x_{i}x_{j}−x_{i}x_{j} = 0.

Note that through (1), (2), and (3), we have examined all the S-polynomials determined by the pairs of the k + 1 initial generators of I_{q}. At this point, we now have G = {g, f_{1}, …, f_{k}, S^{∗}(g, f_{1})} where S^{∗}(g, f_{1}) is the reduction of S(g, f_{1}) by G \ {S^{∗}(g, f_{1})} discussed in (1).

Let h_{α} denote an arbitrary polynomial in the variables x_{2}, …, x_{k} such that x_{1}h_{α} ∈ G. Let h_{β} denote an arbitrary polynomial in the variables x_{2}, …, x_{k} such that h_{β} ∈ G. We may assume that lm(h_{α}) = lt(h_{α}) and lm(h_{β}) = lt(h_{β}). These polynomials are defined to be “in progress,” of course. Right now, we have one of type h_{α}, namely S^{∗}(g, f_{1}), and k − 1 of type h_{β} ∈ G. We now must consider the following S-polynomials.

(4) \begin{aligned}S(g, x_{1}h_{α}) & = \frac{x_{1}^{d}lt(h_{α})}{x_{1}^{d}}g − \frac{x_{1}^{d}lt(h_{α})}{x_{1}lt(h_{α})}x_{1}h_{α} = lt(h_{α})g − x_{1}^{d}h_{α} \\ & = x_{1}^{d}lt(h_{α}) + lt(h_{α})f − x_{1}^{d}h_{α} = lt(h_{α})f − x_{1}^{d}[h_{α} − lt(h_{α})], \end{aligned}

which can be reduced by g.

\begin{matrix}S(g, x_{1}h_{α}) ⟶^{g} & lt(h_{α})f − x_{1}^{d}[h_{α} − lt(h_{α})] + g[h_{α} − lt(h_{α})] \\ = & lt(h_{α})f + f[h_{α} − lt(h_{α})] = fh_{α}. \end{matrix}

(5) \begin{aligned}S(f_{1}, x_{1}h_{α}) & = \frac{x_{1}^{q}lt(h_{α})}{x_{1}^{q}}f_{1} − \frac{x_{1}^{q}lt(h_{α})}{x_{1}lt(h_{α})}x_{1}h_{α} = lt(h_{α})f_{1} − x_{1}^{q}h_{α} \\ & = x_{1}^{q}lt(h_{α}) − x_{1}lt(h_{α}) − x_{1}^{q}h_{α} = −x_{1}lt(h_{α}) − x_{1}^{q}[h_{α} − lt(h_{α})], \end{aligned}

which can be reduced by both f_{1} and x_{1}h_{α}.

\begin{matrix}S(f_{1}, x_{1}h_{α}) ⟶^{f_{1}} & − x_{1}lt(h_{α}) − x_{1}^{q}[h_{α} − lt(h_{α})] + f_{1}[h_{α} − lt(h_{α})] \\ = & − x_{1}lt(h_{α}) − x_{1}[h_{α} − lt(h_{α})] = −x_{1}h_{α} ⟶^{x_{1}h_{α}} −x_{1}h_{α} + x_{1}h_{α} = 0. \end{matrix}

(6) For i ≥ 2, S(f_{i}, x_{1}h_{α}) = \frac{lcm(x_{i}^{q}, x_{1}lt(h_{α}))}{x_{i}^{q}}f_{i} − \frac{lcm(x_{i}^{q}, x_{1}lt(h_{α}))}{x_{1}lt(h_{α})}x_{1}h_{α} = x_{1}h′

where h′ is a polynomial in the variables x_{2}, …, x_{k}. If x_{1}h′ is reducible by G, then the reduction must be of the form x_{1} times a polynomial independent of x_{1} (i.e., a polynomial in F_{q}[x_{2}, …, x_{k}]).

(7)  \begin{aligned}S(g, h_{β}) & = \frac{x_{1}^{d}lt(h_{β})}{x_{1}^{d}}g − \frac{x_{1}^{d}lt(h_{β})}{lt(h_{β})}h_{β} = lt(h_{β})g − x_{1}^{d}h_{β} \\ & = x_{1}^{d}lt(h_{β}) + lt(h_{β})f − x_{1}^{d}h_{β} = lt(h_{β})f − x_{1}^{d}[h_{β} − lt(h_{β})], \end{aligned}

which can be reduced by both g and h_{β}.

\begin{matrix}S(g, h_{β}) ⟶^{g} & lt(h_{β})f − x_{1}^{d}[h_{β} − lt(h_{β})] + g[h_{β} − lt(h_{β})] = lt(h_{β})f + f[h_{β} − lt(h_{β})] \\ = & fh_{β} ⟶^{h_{β}} fh_{β} − fh_{β} = 0. \end{matrix}

(8) \begin{aligned}S(f_{1}, h_{β}) & = \frac{x_{1}^{q}lt(h_{β})}{x_{1}^{q}}f_{1} − \frac{x_{1}^{q}lt(h_{β})}{lt(h_{β})}h_{β} = lt(h_{β})f_{1} − x_{1}^{q}h_{β} \\ & = x_{1}^{q}lt(h_{β}) − x_{1}lt(h_{β}) − x_{1}^{q}(h_{β}) = −x_{1}lt(h_{β}) − x_{1}^{q}[h_{β} − lt(h_{β})], \end{aligned}

which can be reduced by both f_{1} and h_{β}.

\begin{matrix}S(f_{1}, h_{β}) ⟶^{f_{1}} & − x_{1}lt(h_{β}) − x_{1}^{q}[h_{β} − lt(h_{β})] + f_{1}[h_{β} − lt(h_{β})] \\ = & − x_{1}lt(h_{β}) − x_{1}[h_{β} − lt(h_{β})] = −x_{1}h_{β} ⟶^{h_{β}} −x_{1}h_{β} + x_{1}h_{β} = 0. \end{matrix}

(9)  For i ≥ 2, S(f_{i}, h_{β}) = \frac{lcm(x_{i}^{q}, lt(h_{β}))}{x_{i}^{q}}f_{i} − \frac{lcm(x_{i}^{q}, lt(h_{β}))}{lt(h_{β})}h_{β} = h_{γ}

where h_{γ} is a polynomial in the variables x_{2}, …, x_{k}. If this is reducible by G, then the reduction must be independent of x_{1}.

(10) S(x_{1}h_{α}, h_{β}) = \frac{x_{1}lcm(lt(h_{α}), lt(h_{β}))}{x_{1}lt(h_{α})}x_{1}h_{α} − \frac{x_{1}lcm(lt(h_{α}), lt(h_{β}))}{lt(h_{β})}h_{β} = x_{1}h_{δ}

where h_{δ} is a polynomial in the variables x_{2}, …, x_{k}. If x_{1}h_{δ} is reducible by G, then the reduction must be of the form x_{1} times a polynomial independent of x_{1}.

Finally, let h_{α_{1}} and h_{α_{2}} denote any two polynomials in the variables x_{2}, …, x_{k} such that x_{1}h_{α_{1}}, x_{1}h_{α_{2}} ∈ G. Similarly, let h_{β_{1}} and h_{β_{2}} denote any two polynomials in the variables x_{2}, …, x_{k} such that h_{β_{1}}, h_{β_{2}} ∈ G.

S(x_{1}h_{α_{1}}, x_{1}h_{α_{2}}) = \frac{lcm(lt(h_{α_{1}}), lt(h_{α_{2}}))}{lt(h_{α_{1}})}x_{1}h_{α_{1}} − \frac{lcm(lt(h_{α_{1}}), lt(h_{α_{2}}))}{lt(h_{α_{2}})}x_{1}h_{α_{2}} = x_{1}h_{ϵ}

where h_{ϵ} is a polynomial in the variables x_{2}, …, x_{k}. If x_{1}h_{ϵ} is reducible by G, then the reduction must be of the form x_{1} times a polynomial independent of x_{1}.

(12)  S(h_{β_{1}}, h_{β_{2}}) = \frac{lcm(lt(h_{β_{1}}), lt(h_{β_{2}}))}{lt(h_{β_{1}})}h_{β_{1}} − \frac{lcm(lt(h_{β_{1}}), lt(h_{β_{2}}))}{lt(h_{β_{2}})}h_{β_{2}} = h_{ζ}

where h_{ζ} is a polynomial in the variables x_{2}, …, x_{k}. If this is reducible by G, then the reduction must be independent of x_{1}.

Since the code length of C^{⊥}(I, L) is equal to the the number of rational points of V (I_{q}), we need to work with varieties with many rational points to obtain long codes. Observe that in Buchberger’s Algorithm, each time an S-polynomial fails to reduce to zero, we append a new polynomial to G. When this occurs, we are informed that any multiple of the leading monomial of the polynomial does not appear in Δ(I_{q}). Hence, in order to make |Δ(I_{q})| relatively large, we would like a large number of these S-polynomials to reduce to zero.

Consider the “first” S-polynomial represented in (4); namely, S(g, S^{∗}(g, f_{1})). When does this reduce to zero? Note that S(g, S^{∗}(g, f_{1})) reduces to zero if and only if

f((−1)^{n+1}f^{n} + 1) = (−1)^{n+1}f^{n+1} + f ⟶^{F}_{+} 0.

Lemma 2.13. Suppose n is a divisor of q − 1 that satisfies n + 1 = (char 𝔽_{q})^{m} for some integer m. Then there exists a subfield of 𝔽_{q} with n + 1 elements. Proof. Suppose there exist positive integers d and n such that dn = q − 1 and n+1 = (char 𝔽_{q})^{m} for some integer m. Express q = (char 𝔽_{q})^{t} where t is a positive integer. Then d = (q − 1)/n implies that

d = \frac{(char 𝔽_{q})^{t} − 1}{(char 𝔽_{q})^{m} − 1}.

Since d is an integer, it follows that m|t. Therefore, there exists a subfield of 𝔽_{q} with n + 1 elements [6]. □

Let 𝔽_{n+1} denote that subfield. Suppose f = c_{1}m_{1} + ⋯ + c_{s}m_{s} where c_{i} ∈ 𝔽_{q} and m_{i} ∈ T^{k} for 1 ≤ i ≤ s. Note that

(−1)^{n+1} = \begin{cases}−1 & if char 𝔽_{q} ≠ 2 \\ 1 & if char 𝔽_{q} = 2. \end{cases}

So we always have (−1)^{n+1} = −1 in 𝔽_{q}. Therefore,

(−1)^{n+1}f^{n+1} + f = −f^{n+1} + f = −(c_{1}m_{1} + ⋯ + c_{s}m_{s})^{n+1} + (c_{1}m_{1} + ⋯ + c_{s}m_{s})
= −((c_{1}m_{1})^{n+1} + ⋯ + (c_{s}m_{s})^{n+1}) + c_{1}m_{1} + ⋯ + c_{s}m_{s}
= (c_{1}m_{1}) − (c_{1}m_{1})^{n+1} + ⋯ + (c_{s}m_{s}) − (c_{s}m_{s})^{n+1}.

When does this reduce to zero by F? To answer this question, we will use the following concept. Definition 2.14. [8] A polynomial f ∈ 𝔽_{q}[x_{2}, …, x_{k}] is called an (𝔽_{q}^{k−1}, 𝔽_{n+1})- polynomial if the image of f when restricted to 𝔽_{q}^{k−1} is contained in 𝔽_{n+1}.

In fact, given this condition, we will show next that all S-polynomials that are independent of x_{1} will reduce to zero. This leaves us with a Gröbner basis of the form

{x_{1}(g_{1}), …, x_{1}(g_{s}), g, f_{2}, …, f_{k}}

for the ideal I_{q}. Theorem 2.15. Let g(x_{1}, …, x_{k}) := x_{1}^{d} + f(x_{2}, …, x_{k}) ∈ 𝔽_{q}[x_{1}, …, x_{k}], where d|(q − 1), n := \frac{q−1}{d}, n + 1 = (char 𝔽_{q})^{m} for some positive integer m, f is an (𝔽_{q}^{k−1}, 𝔽_{n+1})-polynomial, and lt(g) = x_{1}^{d}. Put I = ⟨g⟩ ⊆ 𝔽_{q}[x_{1}, …, x_{k}] and let J = ⟨f^{n} − 1⟩ ⊆ 𝔽_{q}[x_{2}, …, x_{k}]. If {g_{1}, …, g_{s}, f_{2}, …, f_{k}} is a Gröbner basis for J_{q}, where f_{i} := x_{i}^{q} − x_{i} for 2 ≤ i ≤ k, then {x_{1}(g_{1}), …, x_{1}(g_{s}), g, f_{2}, …, f_{k}} is a Gröbner basis for I_{q}. Proof. Put I′ := ⟨x_{1}(g_{1}), …, x_{1}(g_{s}), g, f_{2}, …, f_{k}⟩. We need to show I′ ⊆ I_{q}. It suffices to show that x_{1}(g_{i}) ∈ I_{q} for all i such that 1 ≤ i ≤ s. Since g_{i} ∈ J_{q}, then g_{i} = ∑_{j=2}^{k} p_{j}f_{j} + p_{1}[f^{n} − 1] for some p_{1}, p_{2}, …, p_{k} ∈ 𝔽_{q}[x_{2}, …, x_{k}]. Therefore, x_{1}(g_{i}) = ∑_{j=2}^{k} x_{1}p_{j}f_{j} + p_{1}x_{1}[f^{n} − 1]. Since f_{j} ∈ I_{q} for 2 ≤ j ≤ k, we have that ∑_{j=2}^{k} x_{1}p_{j}f_{j} is in I_{q}. Also, x_{1}[f^{n} − 1] is the negative of the reduction of S(g, f_{1}) represented in (1). Hence, x_{1}(g_{i}) ∈ I_{q}. Thus, I′ ⊆ I_{q}.

Put K := ⟨f⟩ ⊆ 𝔽_{q}[x_{2}, …, x_{k}]. Since I_{q}, J_{q}, and K_{q} are radical ideals, put a := number of points of V (I_{q}) = |Δ(I_{q})|, b := number of points of V (J_{q}) = |Δ(J_{q})|, c := number of points of V (K_{q}) = |Δ(K_{q})|. Notice that

b = |{(c_{2}, …, c_{k}) ∈ 𝔽_{q}^{k−1}|f(c_{2}, …, c_{k}) ∈ 𝔽_{n+1} \ {0}}|

and

c = |{(c_{2}, …, c_{k}) ∈ 𝔽_{q}^{k−1}|f(c_{2}, …, c_{k}) = 0}|.

For c_{1} ∈ 𝔽_{q} we have that c_{1}^{d} ∈ 𝔽_{n+1} since (c_{1}^{d})^{n+1} = (c_{1})^{q−1+d} = c_{1}^{d}. For each nonzero element y ∈ 𝔽_{n+1} there exists d-many choices for c_{1} ∈ 𝔽_{q} such that c_{1}^{d} = y. Therefore, from the defining polynomial g(x_{1}, …, x_{k}), we have a = db + c. Note that Δ(I′) ⊆ {x_{1}^{α_{1}} … x_{k}^{α_{k}}|0 ≤ α_{1} < d, 0 ≤ α_{i} < q for 2 ≤ i ≤ k, and either α_{1} = 0 or x_{2}^{α_{2}} … x_{k}^{α_{k}} ∈ Δ(J_{q})}. Therefore,

|Δ(I′)| ≤ q^{k−1} + (d − 1)|Δ(J_{q})| = q^{k−1} + (d − 1)b.

Since I′ ⊆ I_{q}, then Δ(I_{q}) ⊆ Δ(I′). Thus, a = |Δ(I_{q})| ≤ |Δ(I′)|.

Assume that |Δ(I_{q})| < |Δ(I′)|. Hence,

a = db + c < q^{k−1} + (d − 1)b,

which implies that b + c < q^{k−1}. However,

b + c = |{(c_{2}, …, c_{k}) ∈ 𝔽_{q}^{k−1}|f(c_{2}, …, c_{k}) ∈ 𝔽_{n+1} \ {0}}|
+ |{(c_{2}, …, c_{k}) ∈ 𝔽_{q}^{k−1}|f(c_{2}, …, c_{k}) = 0}|
= |{(c_{2}, …, c_{k}) ∈ 𝔽_{q}^{k−1}|f(c_{2}, …, c_{k}) ∈ 𝔽_{n+1}}| = q^{k−1}

since f is an (𝔽_{q}^{k−1}, 𝔽_{n+1})-polynomial, which is a contradiction. Therefore, we have |Δ(I_{q})| = |Δ(I′)|. Thus, Δ(I_{q}) = Δ(I′) = {x_{1}^{α_{1}} … x_{k}^{α_{k}}|0 ≤ α_{1} < d, 0 ≤ α_{i} < q for 2 ≤ i ≤ k, and either α_{1} = 0 or x_{2}^{α_{2}} … x_{k}^{α_{k}} ∈ Δ(J_{q})}. By Theorem 2.5, we have that {x_{1}(g_{1}), …, x_{1}(g_{s}), g, f_{2}, …, f_{k}} is a Gröbner basis for I_{q}. □

2.3 Fermat Varieties

Specifically, consider the Fermat varieties defined by the ideal

I = ⟨x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} + b⟩ ⊆ 𝔽_{q}[x_{1}, …, x_{k}]

where nd = q − 1, n + 1 = (char 𝔽_{q})^{m} for some positive integer m, and b ∈ 𝔽_{n+1}, which is a subfield of 𝔽_{q} by Lemma 2.13. The following table displays all varieties of this type for q ≤ 729 = 3^{6}. Note that this includes all affine Hermitian varieties. This is the case when q = (d − 1)^{2}.

We now wish to determine the exact number of solutions in 𝔽_{q}^{k} for the equation x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} + b = 0 satisfying the above conditions. This has been done previously by [11] and [12]. However, the argument is usually done using character sums. We will provide a simpler explanation.

Fermat Varieties Table

\begin{matrix}q & d & n & q & d & n & q & d & n \\ 4 & 3 & 1 & 64 & 63 & 1 & 289 & 18 & 16 \\ 8 & 7 & 1 & 81 & 10 & 8 & 343 & 57 & 6 \\ 9 & 4 & 2 & 81 & 40 & 2 & 361 & 20 & 18 \\ 16 & 5 & 3 & 121 & 12 & 10 & 512 & 73 & 7 \\ 16 & 15 & 1 & 125 & 31 & 4 & 512 & 511 & 1 \\ 25 & 6 & 4 & 128 & 127 & 1 & 529 & 24 & 22 \\ 27 & 13 & 2 & 169 & 14 & 12 & 625 & 26 & 24 \\ 32 & 31 & 1 & 243 & 121 & 2 & 625 & 156 & 4 \\ 49 & 8 & 6 & 256 & 17 & 15 & 729 & 28 & 26 \\ 64 & 9 & 7 & 256 & 85 & 3 & 729 & 91 & 8 \\ 64 & 21 & 3 & 256 & 255 & 1 & 729 & 364 & 2 \end{matrix}

Note that c^{d} ∈ 𝔽_{n+1} for all c ∈ 𝔽_{q} since (c^{d})^{n+1} = (c)^{q−1+d} = c^{d}. Therefore, x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} + b is an (𝔽_{q}^{k−1}, 𝔽_{n+1})-polynomial. Put y_{j} := x_{j}^{d} for 1 ≤ j ≤ k. Consider the solutions in 𝔽_{n+1}^{k} to the equation y_{1} + ⋯ + y_{k} + b = 0. Assume that exactly i of the y_{j} are nonzero. For 1 ≤ i ≤ k, define z_{i,b} to be the number of ways to choose i elements a_{1}, …, a_{i} ∈ 𝔽_{n+1} \ {0} such that a_{1} + ⋯ + a_{i} + b = 0. For i = 0, we set

z_{0,b} = \begin{cases}1 & if b = 0 \\ 0 & otherwise. \end{cases}

For each nonzero y_{j} ∈ 𝔽_{n+1} there exists d-many x_{j} ∈ 𝔽_{q} such that x_{j}^{d} = y_{j}. Of course, if y_{j} = 0 then x_{j} = 0. Thus, the number of solutions to x_{1}^{d} +⋯+x_{k}^{d} +b = 0 in which there are exactly i nonzero x_{j} is \binom{k}{i}z_{i,b}d^{i}. Hence, the number of solutions over 𝔽_{q}^{k} to x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} + b = 0 is ∑_{i=0}^{k} \binom{k}{i}z_{i,b}d^{i}. Now, we will examine the two cases of z_{i,b} more explicitly beginning with a recursive formula. Lemma 2.16. [3] For i ≥ 2, z_{i,b} = n^{i−1} − z_{i−1,b}. Proof. There are n^{i−1} ways to choose elements a_{1}, …, a_{i−1} from 𝔽_{n+1} \{0}. Exactly z_{i−1,b} of these choices have the property that a_{1}+⋯+a_{i−1}+b = 0. However, for each of these z_{i−1,b} choices there does not exist a nonzero a_{i} such that a_{1}+⋯+a_{i}+b = 0. On the other hand, if a_{1} + ⋯ + a_{i−1} + b ≠ 0, then there exists a unique nonzero a_{i} such that a_{1} + ⋯ + a_{i} + b = 0. □ Proposition 2.17. (i) The number of solutions in 𝔽_{q}^{k} to x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} = 0 is

\frac{q^{k} + n(1 − d)^{k}}{n + 1} .

(ii) The number of solutions over 𝔽_{q}^{k} to x_{1}^{d} + x_{2}^{d} + ⋯ + x_{k}^{d} + b = 0 when b ≠ 0 is

\frac{q^{k} − (1 − d)^{k}}{n + 1} .

Proof. (i) b = 0. Note that z_{0,0} = 1 and z_{1,0} = 0. Therefore, by expansion of the recursive formula, we obtain that for i ≥ 2,

z_{i,0} = n^{i−1} − n^{i−2} + ⋯ + (−1)^{i}n = ∑_{l=0}^{i−2}(−1)^{l}n^{i−1−l}.

Note that z_{i,0} is also expressed as a geometric series, so

z_{i,0} = \frac{(−1)^{i}n[1 − (−n)^{i−1}]}{1 + n} = \frac{n^{i} + (−1)^{i}n}{n + 1}

for i ≥ 0. Hence, the number of solutions is

∑_{i=0}^{k} \binom{k}{i}d^{i} \frac{n^{i} + (−1)^{i}n}{n + 1} = \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(dn)^{i} + \frac{n}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(−d)^{i}

= \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(q − 1)^{i} + \frac{n}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(−d)^{i}

= \frac{1}{n + 1}(q^{k}) + \frac{n}{n + 1}(1 − d)^{k} = \frac{q^{k} + n(1 − d)^{k}}{n + 1} .

(ii) b ≠ 0. Note that z_{0,b} = 0 and z_{1,b} = 1. Therefore, by expansion of the recursive formula, we obtain that for i ≥ 1,

z_{i,b} = n^{i−1} − n^{i−2} + ⋯ + (−1)^{i}n + (−1)^{i+1} = ∑_{l=0}^{i−1}(−1)^{l}n^{i−1−l}.

Note that z_{i,b} is expressed as a geometric series, so

z_{i,b} = \frac{(−1)^{i+1}[1 − (−n)^{i}]}{1 + n} = \frac{n^{i} + (−1)^{i+1}}{n + 1}

for i ≥ 0. Hence, the number of solutions is

∑_{i=0}^{k} \binom{k}{i}d^{i} \frac{n^{i} + (−1)^{i+1}}{n + 1} = \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(dn)^{i} + \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(−1)^{i+1}d^{i}

= \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(q − 1)^{i} − \frac{1}{n + 1} ∑_{i=0}^{k} \binom{k}{i}(−d)^{i}

= \frac{1}{n + 1}(q^{k}) − \frac{1}{n + 1}(1 − d)^{k} = \frac{q^{k} − (1 − d)^{k}}{n + 1} .□

Throughout the rest of this chapter, we will choose to assign the variables equal weight. Thus we may assume wt(x_{1}) = wt(x_{2}) = ⋯ = wt(x_{k}) = 1. Note that our monomial ordering is then simply the degree lexicographic ordering.

Generally, it is difficult to describe the H-sequence for Fermat varieties of dimension k. However, we can obtain a description of N_{r} under certain circumstances. In the next section we will show that the hypothesis in the following theorem is valid in the case of Fermat surfaces. Theorem 2.18. Let V (I_{q}) be an affine variety defined by I ⊆ 𝔽_{q}[x_{1}, …, x_{k}] where k ≥ 3. Suppose that wt(x_{i}) = wt(x_{j}) for 1 ≤ i, j ≤ k. For each h_{i}, h_{j}, h_{r} ∈ H, if h_{i,j} = x_{1}^{p_{1}}x_{2}^{p_{2}} … x_{k}^{p_{k}} ∼ h_{r} = x_{1}^{r_{1}}x_{2}^{r_{2}} … x_{k}^{r_{k}} implies that p_{n} ≤ r_{n} for 3 ≤ n ≤ k, then N_{r} = ∏_{n=1}^{k}(r_{n} + 1). Proof. By Proposition 1.21, we know that N_{r} ≥ ∏_{n=1}^{k}(r_{n}+1). Assume equality does not hold. Then there exist elements h_{i} = x_{1}^{i_{1}} … x_{k}^{i_{k}}, h_{j} = x_{1}^{j_{1}} … x_{k}^{j_{k}} ∈ H such that h_{i}h_{j} = h_{i,j} is a well-behaving term consistent with h_{r} but h_{i}h_{j} ≠ h_{r}. By Lemma 1.20, we may assume that h_{i} and h_{j} are non-divisors of h_{r}. This implies that there exist α and β such that i_{α} > r_{α} and j_{β} > r_{β}. Since i_{n} + j_{n} ≤ r_{n} for 3 ≤ n ≤ k (by our hypothesis) and h_{r} <_{t} h_{i}h_{j} (by Corollary 1.15), we have α, β ∈ {1, 2} and i_{1} + j_{1} ≥ r_{1}.

We will show that h_{i,j} cannot be well-behaving. We will find h_{u} = x_{1}^{u_{1}} … x_{k}^{u_{k}} and h_{v} = x_{1}^{v_{1}} … x_{k}^{v_{k}} such that h_{u} <_{t} h_{i}, h_{v} <_{t} h_{j}, and h_{u}h_{v} = h_{r}.

Put u_{1} := min{i_{1}, r_{1}}. For 2 ≤ n ≤ k put

u_{n} := min{r_{n}, ∑_{l=1}^{k} i_{l} − ∑_{l=1}^{n−1} u_{l}}.

Put v_{n} := r_{n} − u_{n} for 1 ≤ n ≤ k. Now, since wt(h_{i}) + wt(h_{j}) = wt(h_{r}), we have that

∑_{n=1}^{k} i_{n} + ∑_{n=1}^{k} j_{n} = ∑_{n=1}^{k} r_{n}.

Clearly, ∑_{n=1}^{k} u_{n} ≤ ∑_{n=1}^{k} i_{n}.

Assume ∑_{n=1}^{k} u_{n} < ∑_{n=1}^{k} i_{n}. Then, for all n such that 2 ≤ n ≤ k,

u_{n} = r_{n} < ∑_{l=1}^{k} i_{l} − ∑_{l=1}^{n−1} u_{l}

(otherwise, ∑_{l=1}^{k} i_{l} = ∑_{l=1}^{n} u_{l} ≤ ∑_{l=1}^{k} u_{l}, which is a contradiction). Furthermore, u_{1} = i_{1} < r_{1} (otherwise, ∑_{n=1}^{k} u_{n} = ∑_{n=1}^{k} r_{n} < ∑_{n=1}^{k} i_{n}, which is a contradiction). Therefore,

i_{1} + ∑_{n=2}^{k} r_{n} = ∑_{n=1}^{k} u_{n} < ∑_{n=1}^{k} i_{n} = ∑_{n=1}^{k} r_{n} − ∑_{n=1}^{k} j_{n}

which implies that i_{1} + j_{1} ≤ i_{1} + ∑_{n=1}^{k} j_{n} < r_{1}, which is a contradiction. Thus, ∑_{n=1}^{k} u_{n} = ∑_{n=1}^{k} i_{n}.

By construction,

∑_{n=1}^{k} v_{n} = ∑_{n=1}^{k} r_{n} − ∑_{n=1}^{k} u_{n} = ∑_{n=1}^{k} r_{n} − ∑_{n=1}^{k} i_{n} = ∑_{n=1}^{k} j_{n}.

Let h_{u} = x_{1}^{u_{1}} … x_{k}^{u_{k}} and h_{v} = x_{1}^{v_{1}} … x_{k}^{v_{k}}. So, wt(h_{u}) = wt(h_{i}) and wt(h_{v}) = wt(h_{j}). Note that h_{u}h_{v} = h_{r}. Therefore, h_{u}, h_{v} ∈ H by Remark 1.9. We claim that h_{u} <_{t} h_{i} and h_{v} <_{t} h_{j}.

Suppose u_{1} = r_{1} < i_{1}. Then we have h_{u} <_{t} h_{i}. Also, u_{1} = r_{1} implies that v_{1} = r_{1} − u_{1} = 0. Hence, if j_{1} > 0 then h_{v} <_{t} h_{j}. If j_{1} = 0, then since h_{j} ∤ h_{r}, we have r_{2} < j_{2}. This implies that v_{2} < j_{2} and h_{v} <_{t} h_{j}.

Suppose u_{1} = i_{1} ≤ r_{1}. Since h_{i} ∤ h_{r}, we have r_{2} < i_{2}. Thus, u_{2} < i_{2} and h_{u} <_{t} h_{i}. Also, u_{1} = i_{1} and i_{1} + j_{1} ≥ r_{1} imply that v_{1} ≤ j_{1}. If i_{1} + j_{1} > r_{1}, then v_{1} < j_{1} and so h_{v} <_{t} h_{j}. If i_{1} + j_{1} = r_{1}, then since h_{j} ∤ h_{r}, we have r_{2} < j_{2}. This implies that v_{2} < j_{2} and h_{v} <_{t} h_{j}.

Thus, in each of the cases we have h_{u,v} = h_{r} with h_{u} <_{t} h_{i} and h_{v} <_{t} h_{j}. Hence, h_{i,j} is not a well-behaving term, which is a contradiction. □

2.4 Fermat Surfaces

Theorem 2.19. Consider the affine variety V (I_{q}) defined by a Fermat surface where I = ⟨x_{1}^{d} + x_{2}^{d} + x_{3}^{d} + b⟩ ⊆ 𝔽_{q}[x_{1}, x_{2}, x_{3}] and d satisfies 1 < d < q. The set of leading terms of the reduced Gröbner basis for I_{q} is {x_{1}^{d}, x_{2}^{q}, x_{3}^{q}, x_{1}x_{2}^{q−1}, x_{1}x_{2}^{q−d}x_{3}^{d}} if and only if d|(q − 1), n + 1 = (char 𝔽_{q})^{m} for some integer m where n := (q − 1)/d, and b ∈ 𝔽_{n+1} \ {0}.

Proof. (⟸) We apply Buchberger’s Algorithm and carefully examine two of the S-polynomials. First,

S(g, f_{1}) ⟶^{g} x_{1}((−1)^{n+1}f^{n} + 1) = x_{1}(−f^{n} + 1) = x_{1}(−(x_{2}^{d} + x_{3}^{d} + b)^{n} + 1),

whose leading term is −x_{1}x_{2}^{q−1}. Second,

S(f_{2}, S^{∗}(g, f_{1})) = x_{1}x_{2}^{q} − x_{1}x_{2} + x_{1}x_{2}(−(x_{2}^{d} + x_{3}^{d} + b)^{n} + 1),

which has leading term −x_{1}x_{2}^{d(n−1)+1}x_{3}^{d} = −x_{1}x_{2}^{q−d}x_{3}^{d} since the term x_{1}x_{2}^{q} is canceled. Currently in the algorithm we have G =

{x_{1}^{d} + x_{2}^{d} + x_{3}^{d} + b, x_{2}^{q} − x_{2}, x_{3}^{q} − x_{3}, x_{1}((x_{2}^{d} + x_{3}^{d} + b)^{n} − 1), x_{1}x_{2}(x_{2}^{d} + x_{3}^{d} + b)^{n} − x_{1}x_{2}^{q}}.

The set of leading monomials of G is

{x_{1}^{d}, x_{2}^{q}, x_{3}^{q}, x_{1}x_{2}^{q−1}, x_{1}x_{2}^{q−d}x_{3}^{d}}.

All other S-polynomials must reduce to zero since the set of leading monomials implies that Δ(I_{q}) ⊆ A ∪ B ∪ C, where

\begin{aligned}A & = \{x_{2}^{β}x_{3}^{γ}|0 ≤ β < q, 0 ≤ γ < q\} \\ B & = \{x_{1}^{α}x_{2}^{β}x_{3}^{γ}|1 ≤ α < d, 0 ≤ β < q − d, 0 ≤ γ < q\} \\ C & = \{x_{1}^{α}x_{2}^{β}x_{3}^{γ}|1 ≤ α < d, q − d ≤ β < q − 1, 0 ≤ γ < d\}. \end{aligned}

Thus,

|Δ(I_{q})| ≤ q^{2} + (d − 1)(q − d)q + (d − 1)(d − 1)d

= q^{2} + (d − 1)q^{2} − dq(d − 1) + d(d − 1)^{2} = dq^{2} + dq(1 − d) + d(1 − d)^{2}

= d(q^{2} + q(1 − d) + (1 − d)^{2}) = d\frac{q^{3} − (1 − d)^{3}}{q − (1 − d)} = \frac{q^{3} − (1 − d)^{3}}{\frac{q−1+d}{d}}

= \frac{q^{3} − (1 − d)^{3}}{\frac{q−1}{d} + 1} = \frac{q^{3} − (1 − d)^{3}}{n + 1} ,

which is the actual number of points of V (I_{q}) by Proposition 2.17.

(⟹) Assume d ∤ (q−1). Express (q−1) = nd+r where n ≥ 1 and 1 ≤ r ≤ d−1. Suppose r ≠ d − 1. Then in the ring 𝔽_{q}[x_{1}, x_{2}, x_{3}]/I_{q} we have

x_{1} + I_{q} = x_{1}^{q} + I_{q} = x_{1}^{r+1}(x_{1}^{d})^{n} + I_{q} = x_{1}^{r+1}(−1)^{n}(x_{2}^{d} + x_{3}^{d} + b)^{n} + I_{q}.

Thus, the polynomial f = x_{1}^{r+1}(−1)^{n}(x_{2}^{d} + x_{3}^{d} + b)^{n} − x_{1} ∈ I_{q} and lm(f) = x_{1}^{r+1}x_{2}^{dn}. However, since r + 1 < d and dn < q − 1, we know that x_{1}^{r+1}x_{2}^{dn} is not a multiple of any of the leading terms of the Gröbner basis, which is a contradiction. Suppose r = d − 1, then q = (n + 1)d. Note that n + 1 > 1 implies that n + 1 = (char 𝔽_{q})^{m} for some m > 0. Therefore,

x_{1} + I_{q} = x_{1}^{q} + I_{q} = (x_{1}^{d})^{n+1} + I_{q} = (−1)^{n+1}(x_{2}^{d} + x_{3}^{d} + b)^{n+1} + I_{q}

= (−1)^{n+1}(x_{2}^{d(n+1)} + x_{3}^{d(n+1)} + b^{n+1}) + I_{q} = (−1)^{n+1}(x_{2}^{q} + x_{3}^{q} + b^{n+1}) + I_{q}

= (−1)^{n+1}(x_{2} + x_{3} + b^{n+1}) + I_{q}.

Thus, the polynomial f = x_{1} − (−1)^{n+1}(x_{2} + x_{3} + b^{n+1}) ∈ I_{q} and lm(f) = x_{1}. However, x_{1} is not a multiple of any of the leading terms of the Gröbner basis, which is a contradiction. Hence, d|(q − 1).

Assume n + 1 = st where s =(char 𝔽_{q})^{k} for some k ≥ 0 and (char 𝔽_{q}) ∤ t with t an integer greater than 1. In the ring 𝔽_{q}[x_{1}, x_{2}, x_{3}]/I_{q} we have that

x_{1}^{d} + I_{q} = x_{1}^{q−1+d} + I_{q} = x_{1}^{nd+d} + I_{q} = (x_{1}^{d})^{n+1} + I_{q} = (−1)^{n+1}(x_{2}^{d} + x_{3}^{d} + b)^{n+1} + I_{q}
= (−1)^{n+1}((x_{2}^{d} + x_{3}^{d} + b)^{n+1} + (x_{2}^{d} − x_{2}^{q−1+d}) + (x_{3}^{d} − x_{3}^{q−1+d})) + I_{q}
= (−1)^{n+1}((x_{2}^{d} + x_{3}^{d} + b)^{st} + x_{2}^{d} − x_{2}^{q−1+d} + x_{3}^{d} − x_{3}^{q−1+d}) + I_{q}
= (−1)^{n+1}((x_{2}^{ds} + x_{3}^{ds} + b^{s})^{t} + x_{2}^{d} − x_{2}^{q−1+d} + x_{3}^{d} − x_{3}^{q−1+d}) + I_{q}

Thus, the polynomial

f = (−1)^{n+1}((x_{2}^{ds} + x_{3}^{ds} + b^{s})^{t} + x_{2}^{d} − x_{2}^{q−1+d} + x_{3}^{d} − x_{3}^{q−1+d}) − x_{1}^{d} ∈ I_{q}.

Since

dst = d(n + 1) = dn + d = q − 1 + d,

we have that x_{2}^{dst} − x_{2}^{q−1+d} = 0 and lm(f) = x_{2}^{ds(t−1)}x_{3}^{ds} and its coefficient is (−1)^{n+1}t. Note that

ds(t − 1) = d(st − s) = d(n + 1 − s) ≤ dn = q − 1

and (−1)^{n+1}t ≠ 0 over 𝔽_{q}. Thus, x_{2}^{ds(t−1)}x_{3}^{ds} is not a multiple of any of the leading terms of the Gröbner basis, which is a contradiction. Hence n + 1 = (char 𝔽_{q})^{m} for some integer m.

From the proof of (⟸) we know that the leading terms imply that

|Δ(I_{q})| = \frac{q^{3} − (1 − d)^{3}}{n + 1} .

Therefore, by Proposition 2.17, b ≠ 0. □ Corollary 2.20. Let V (I_{q}) be the affine variety defined by a Fermat surface where I = ⟨x_{1}^{d} + x_{2}^{d} + x_{3}^{d} + b⟩ ⊆ 𝔽_{q}[x_{1}, x_{2}, x_{3}] where d|(q − 1), n + 1 = (char 𝔽_{q})^{m} for some integer m where n := (q − 1)/d, and b ∈ 𝔽_{n+1} \ {0}. A Gröbner basis for I_{q} is {x_{1}^{d} + x_{2}^{d} + x_{3}^{d} + b, x_{2}^{q} − x_{2}, x_{3}^{q} − x_{3}, x_{1}((x_{2}^{d} + x_{3}^{d} + b)^{n} − 1), x_{1}x_{2}(x_{2}^{d} + x_{3}^{d} + b)^{n} − x_{1}x_{2}^{q}}. Corollary 2.21. (i) For each polynomial g_{i} of the Gröbner basis G in Corollary 2.20, if x^{α} = x_{1}^{α_{1}}x_{2}^{α_{2}}x_{3}^{α_{3}} is a monomial that appears in g_{i} such that wt(x^{α}) = wt(lm(g_{i})), where lm(g_{i}) = x_{1}^{β_{1}}x_{2}^{β_{2}}x_{3}^{β_{3}}, then β_{1} ≥ α_{1} and β_{1} + β_{2} ≥ α_{1} + α_{2}.

(ii) Suppose f reduces to r modulo G. Also, suppose lm(f) = x_{1}^{β_{1}}x_{2}^{β_{2}}x_{3}^{β_{3}} and lm(r) = x_{1}^{α_{1}}x_{2}^{α_{2}}x_{3}^{α_{3}}. If wt(lm(f)) = wt(lm(r)) then β_{1} ≥ α_{1} and β_{1} + β_{2} ≥ α_{1} + α_{2}. Proof. This follows by inspection of the polynomials in the Gröbner basis in Corollary 2.20. □

For the remainder of this chapter we will assume that V (I_{q}) satisfies the conditions stated in Corollary 2.20. We will now show that for each h_{r} ∈ H, its corresponding N_{r} is easy to determine. Lemma 2.22. For h_{i} = x_{1}^{i_{1}}x_{2}^{i_{2}}x_{3}^{i_{3}}, h_{j} = x_{1}^{j_{1}}x_{2}^{j_{2}}x_{3}^{j_{3}}, and h_{r} = x_{1}^{r_{1}}x_{2}^{r_{2}}x_{3}^{r_{3}} ∈ H, if h_{i,j} = x_{1}^{p_{1}}x_{2}^{p_{2}}x_{3}^{p_{3}} is consistent with h_{r}, then p_{3} ≤ r_{3}. Proof. First we will show that for Fermat surfaces h_{i,j} ∉ I_{q}. Indeed, if h_{i,j} = x_{1}^{p_{1}}x_{2}^{p_{2}}x_{3}^{p_{3}} ∈ I_{q}, then x_{1}^{q}x_{2}^{q}x_{3}^{q} ∈ I_{q}. It follows that x_{1}x_{2}x_{3} ∈ I_{q}. However, there does not exist a Gröbner basis polynomial whose leading term divides x_{1}x_{2}x_{3}, which is a contradiction. Now, by Remark 2.7, we have that h_{r} is the leading monomial of the reduction of h_{i,j} with respect to the Gröbner basis. Also, h_{i,j} ∼ h_{r} implies that wt(h_{i,j}) = wt(h_{r}). Therefore, Corollary 2.21 implies that p_{1} + p_{2} ≥ r_{1} + r_{2}. However, since h_{i,j} and h_{r} have the same total degree, we have p_{3} ≤ r_{3}. □ Proposition 2.23. For the Fermat surfaces of this section, we have that N_{r} = ∏_{i=1}^{3}(r_{i} + 1), the number of monomial divisors of h_{r}. Proof. This follows from Lemma 2.22 and Theorem 2.18. □

Not only are we interested in the actual value of N_{r}, but in order to determine the dimensions of our codes we need to know how many times that value occurs. Put

S_{t} = |{h_{r} ∈ H|N_{r} ≤ t}|.

The footprint of the ideal I_{q} can be expressed as Δ(I_{q}) = U \ (V ∪ W) where

\begin{aligned}U & = \{x_{1}^{α}x_{2}^{β}x_{3}^{γ}|0 ≤ α < d, 0 ≤ β < q, 0 ≤ γ < q\}, \\ V & = \{x_{1}^{α}x_{2}^{q−1}x_{3}^{γ}|1 ≤ α < d, 0 ≤ γ < q\}, \\ W & = \{x_{1}^{α}x_{2}^{β}x_{3}^{γ}|1 ≤ α < d, q − d ≤ β ≤ q − 2, d ≤ γ < q\}. \end{aligned}

Since N_{r} is simply the number of monomial divisors of h_{r}, we know from Δ(I_{q}) that S_{t} = |U_{t}| − |V_{t}| − |W_{t}| where

\begin{aligned}U_{t} & = \{(α, β, γ)|αβγ ≤ t, 1 ≤ α ≤ d, 1 ≤ β ≤ q, 1 ≤ γ ≤ q\} \\ V_{t} & = \{(α, γ)|αqγ ≤ t, 2 ≤ α ≤ d, 1 ≤ γ ≤ q\} \\ W_{t} & = \{(α, β, γ)|αβγ ≤ t, 2 ≤ α ≤ d, q − d < β < q, d < γ ≤ q\}. \end{aligned}

However, if we restrict

t < 2(q − d + 1)(d + 1),

then C_{t} = ∅. Hence,

S_{t} = |U_{t}| − |V_{t}|.

If we fix the value of the product βγ, call it x, then |{α|(α, β, γ) ∈ U_{t}}| = min{d, ⌊t/x⌋}. Hence,

|U_{t}| = ∑_{x=1}^{t} f_{t}(x)g(x)

where

f_{t}(x) = min{d, ⌊t/x⌋}

and

g(x) = |{(β, γ)|βγ = x, 1 ≤ β ≤ q, 1 ≤ γ ≤ q}|.

If we fix the value of the product αγ, call it y, then

|V_{t}| = ∑_{y=2}^{⌊t/q⌋} h(y)

where

h(y) = |{(α, γ)|αγ = y, 2 ≤ α ≤ d, 1 ≤ γ ≤ q}|.

Thus, for t < 2(q − d + 1)(d + 1) we have

S_{t} = ∑_{x=1}^{t} f_{t}(x)g(x) − ∑_{y=2}^{⌊t/q⌋} h(y).

For affine variety codes C^{⊥}(I, L) of length \frac{q^{3}−(1−d)^{3}}{n+1} where I = ⟨x_{1}^{d}+x_{2}^{d}+x_{3}^{d}+b⟩ ⊆ 𝔽_{q}[x_{1}, x_{2}, x_{3}], if we want a minimum distance lower bound of δ, then we put L = span{h̄_{r}|N_{r} < δ}. Hence, L has dimension S_{δ−1}. Thus, our code has dimension

\frac{q^{3} − (1 − d)^{3}}{n + 1} − S_{δ−1}.

Example 2.24. Suppose you desire a code over 𝔽_{4} to have length 36 and minimum distance at least 6. Consider the affine variety code C^{⊥}(I, L) where the ideal I = ⟨x_{1}^{3} + x_{2}^{3} + x_{3}^{3} + 1⟩ ⊆ 𝔽_{4}[x_{1}, x_{2}, x_{3}], put L = span{h̄_{r}|N_{r} < 6}. We need to calculate S_{5} = ∑_{x=1}^{5} f_{5}(x)g(x) with f_{5}(x) = min{3, ⌊5/x⌋} and

g(x) = |{(β, γ)|βγ = x, 1 ≤ β ≤ 4, 1 ≤ γ ≤ 4}|.

Thus,

S_{5} = 3g(1) + 2g(2) + g(3) + g(4) + g(5) = 3 + 4 + 2 + 3 + 0 = 12.

Hence, C^{⊥}(I, L) is a [36, 24, ≥ 6]-code over 𝔽_{4}, i.e. a code of length 36, dimension 24, and minimum distance at least 6. The actual minimum distance is 6 since the columns of the parity check matrix H_{r}^{∗} corresponding to the points P_{1} = (1, α^{2}, α^{2}), P_{2} = (1, 1, α^{2}), P_{3} = (α, 1, 1), P_{4} = (α, α, 1), P_{5} = (α^{2}, α, α), and P_{6} = (α^{2}, α^{2}, α), where α is a generator of the multiplicative group of 𝔽_{4}, are linearly dependent. Example 2.25. Suppose you wish to obtain a code over 𝔽_{9} with length 252 and minimum distance at least 12. Consider the affine variety code C^{⊥}(I, L) where I = ⟨x_{1}^{4} + x_{2}^{4} + x_{3}^{4} + 1⟩ ⊆ 𝔽_{9}[x_{1}, x_{2}, x_{3}], put L = span{h̄_{r}|N_{r} < 12}. Now, S_{11} = ∑_{x=1}^{11} f_{11}(x)g(x) with f_{11}(x) = min{4, ⌊11/x⌋} and

g(x) = |{(β, γ)|βγ = x, 1 ≤ β ≤ 9, 1 ≤ γ ≤ 9}|.

Therefore,

\begin{aligned}S_{11} & = 4g(1) + 4g(2) + 3g(3) + 2g(4) + 2g(5) + ∑_{x=6}^{11} g(x) \\ & = 4 + 8 + 6 + 6 + 4 + 4 + 2 + 4 + 3 + 2 + 0 = 43. \end{aligned}

Thus, our code is a [252, 209, ≥ 12], 𝔽_{9}-linear code.

References

[1] W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, American Mathematical Society, 1994.

[2] D. Cox, J. Little, and D. O’Shea: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer-Verlag, New York, 1992.

[3] J. Fitzgerald, Applications of Gröbner Bases to Linear Codes, Doctoral dissertation, Louisiana State University, 1996.

[4] G.-L. Feng and T. R. N. Rao, “Improved Geometric Goppa Codes, Part I: Basic Theory”, IEEE Transactions on Information Theory, vol. 41, no. 6, pp. 1678-1693, Nov. 1995.

[5] T. Høholdt, J. H. van Lint, and R. Pellikaan, “Algebraic Geometry Codes,” in Handbook of Coding Theory, V. Pless, W. C. Huffman and R. A. Brualdi, Eds., pp. 871-961 (vol. 1), Elsevier, Amsterdam, 1998.

[6] T. W. Hungerford, Algebra, Springer-Verlag, New York, 1974.

[7] C. Kirfel and R. Pellikaan, “The Minimum Distance of Codes in an Array Coming from Telescopic Semigroups,” IEEE Transactions on Information Theory, vol. 41, no. 6, pp. 1720-1732, Nov. 1995.

[8] L. Rédei, Lacunary Polynomials over Finite Fields, North-Holland, Amsterdam, 1973.

[9] A. Seidenberg, “Constructions in Algebra,” Transactions of the American Mathematical Society, 197, pp. 273-313, 1974.

[10] M. A. Tsfasman, S. G. Vlǎduţ, and T. Zink, “Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound,” Math. Nachrichten, 109, pp. 21-28, 1982.

[11] A. Weil, “Numbers of Solutions of Equations in Finite Fields,” Bulletin of the American Mathematical Society, 55, pp. 497 - 508, 1949.

[12] J. Wolfmann, “The Number of Solutions of Certain Diagonal Equations Over Finite Fields,” J. Number Theory, vol. 42, no. 3, pp. 247-257, 1992.

Vita

Gary Salazar was born on April 15, 1972 in Waco, Texas. He finished his undergraduate studies in mathematics and chemistry at Baylor University in May, 1994. After a year of graduate studies at Baylor University, Gary decided to pursue a doctorate in mathematics specializing in the field of coding theory at Louisiana State University. He is currently a candidate for the doctoral degree in mathematics which will be awarded in August, 2000.