Long Quadratic Residue Codes

Greg Coy1


Contents

in A long standing problem has been to develop ``good" binary linear block codes, $ C$, to be used for error-correction. The length of the block is denoted $ n$ and the dimension of the code is denoted $ k$. So in this notation $ C\subseteq GF(2)^n$ is a $ k$-dimensional subspace.

Another important parameter is the smallest weight of any non-zero codeword, $ d$. This is related to error-correction because $ C$ can correct $ [\frac{d-1}{2}]$ errors.

We will construct an interesting family of codes $ C_{i}$ which have the property that $ \frac{\log_2(\vert C_i\vert)}{n}$ has a limit $ =\frac{1}{4}$ and $ \frac{d}{n}$ has a limit $ \geq\frac{1}{4}$. We will also investigate how this family violates the ``fake Goppa conjecture." Moreover, we can show that the Goppa conjecture is incompatible with a conjecture on hyperelliptic curves over finite fields, which we call the ``small content conjecture."

Introduction

A linear code, $ C$, of length $ n$ is a subspace of $ GF(q)^{n}$ for some prime power $ q$ and some $ n>1$. The addition on $ C$ is inherited from the usual coordinate-wise addition on $ GF(2)^n$. Let $ C$ be a linear code of length $ n$ over $ {\mathbb{F}}=GF(q)$. If $ q=2$ then the code is called binary. We assume that $ {\mathbb{F}}^{n}$ has been given the standard basis $ \mathbf{e}_{1}=(1,0,...,0)\in{\mathbb{F}}^{n}$, $ \mathbf{e}_{2}=(0,1,0,...,0)\in{\mathbb{F}}^{n}$, ..., $ \mathbf{e}_{n}=(0,0,...,0,1)\in{\mathbb{F}}^{n}$. The dimension of $ C$ is denoted $ k$, so the number of elements of $ C$ is equal to $ q^{k}$. A subset of $ GF(q)^n$ without an addition operation is called a non-linear code.

Another important parameter associated to the code is the number of errors which it can, in principle, correct. For this notion, we need to introduce the Hamming metric. For any two $ \mathbf{x},\mathbf{y}\in{\mathbb{F}}^{n}$, let $ d(\mathbf{x},\mathbf{y})$ denote the number of coordinates where these two vectors differ:

$\displaystyle d(\mathbf{x},\mathbf{y})=\vert\{1\leq i\leq n \vert x_{i}\not=y_{i}\}\vert.$ (1)

This is called the Hamming distance or Hamming metric. Define the weight $ w$ of $ \mathbf{v}$ to be the number of non-zero entries of $ \mathbf{v}$. Note, $ d(\mathbf{x},\mathbf{y})=w(\mathbf{x}-\mathbf{y})$ because the vector $ \mathbf{x}-\mathbf{y}$ has non-zero entries only at locations where $ \mathbf{x}$ and $ \mathbf{y}$ differ. The smallest distance between distinct codewords in a linear code $ C$ is the minimum distance of $ C$:

$\displaystyle d=d(C)=\min_{\mathbf{c}\in C, \mathbf{c}\not=\mathbf{0}}d(\mathbf{0},\mathbf{c})$ (2)

A linear code $ C$ of length $ n$ and dimension $ k$ over $ \mathbb{F}$ has a basis of $ k$ vectors of length $ n$. If those vectors are arranged as rows of a matrix $ G$, then we call the $ k\times n$ matrix $ G$ a generator matrix for $ C$.

Example 1   The following matrix is a generator matrix for a code of length $ 9$, dimension $ 4$, and minimum distance $ 3$ over $ GF(2)$.

\begin{displaymath} G=\left( \begin{array}{ccccccccc} 0&0&0&0&1&0&1&0&1\\ 0&1... ...\ 0&0&1&1&0&1&0&0&0\\ 1&0&0&1&0&1&0&1&1 \end{array}\right) \end{displaymath}

Definition 1   A linear code $ C$ of length $ n$ is a cyclic code if whenever $ \mathbf{c}=(c_1,...,c_n)$ is a codeword then so is its cyclic shift $ \mathbf{c'}=(c_2,...,c_n,c_1)$.

Example 2   Consider the binary code $ C$ with generator matrix

\begin{displaymath} G= \left( \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 0 & 0 & 0\\... ...0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array}\right) \end{displaymath}

Clearly these four rows $ \mathbf{g_1}$, $ \mathbf{g_2}$, $ \mathbf{g_3}$, $ \mathbf{g_4}$ are obtained from the previous row by a shift to the right. Also note the shift of $ \mathbf{g_4}$ to the right is equal to $ \mathbf{g_5}=\mathbf{g_1}+\mathbf{g_3}+\mathbf{g_4}$. The shift of $ \mathbf{g_5}$ to the right is $ \mathbf{g_6}=\mathbf{g_1}+\mathbf{g_2}+\mathbf{g_3}$. And the shift of $ \mathbf{g_6}$ is $ \mathbf{g_7}=\mathbf{g_2}+\mathbf{g_3}+\mathbf{g_4}$. The shift of $ \mathbf{g_7}$ is $ \mathbf{g_1}$. Therefore, the linear code generated by $ G$ is invariatant under shifts to the right. Therefore $ C$ is a cyclic code.

Cyclic codewords are conveniently represented as polynomials modulo $ x^n-1$. In fact, if $ \mathbf{c}=(c_1,\cdots,c_n)$ then let

$\displaystyle c(x)=c_1+c_2x+\cdots+c_nx^{n-1} $

denote the associated codeword polynomial. In this notation the cyclic shift $ \mathbf{c'}=(c_2,...,c_n,c_1)$ of $ \mathbf{c}$ corresponds to the polynomial $ xc(x)\pmod{x^n-1}$. In other words cyclic shifts correspond to multiplication by $ x$. Since cyclic shifts leave cyclic codes invariant, multiplication by any power of $ x$ modulo $ x^n-1$ corresponds to a codeword in $ C$. Since $ C$ is a linear code, the sum of any two such codeword polynomials is another codeword polynomial. Therefore, in fact, the product of any codeword polynomial times any polynomial in $ x$ modulo $ x^n-1$ is another codeword polynomial.

Denote by $ R_n$ the ring of polynomials with coefficients in $ \mathbb{F}$ modulo $ x^n-1$:

$\displaystyle R_n=\mathbb{F}[x]/(x^n-1).$ (3)

Define an ideal $ I$ of $ R_n$ to be any subset of $ R_n$ closed under addition and multiplication by an arbitrary element of $ R_n$: In other words an ideal in $ R_n$ is simply a subset closed under addition and multiplication by an arbitrary polynomial modulo $ x^n-1$. In particular, the collection of codeword polynomials associated to a cyclic code is an ideal of $ R_n$.

Lemma 1   There is a natural one-to-one correspondence between cyclic codes of length $ n$ over $ \mathbb{F}$ and ideals of $ R_n$.

This can be found in any book on coding theory, for example MacWilliams and Sloane [MS].

In fact the algebraic software package GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials.

In order to define the generator polynomial of a cyclic code we need the following mathematical fact.

Lemma 2   Every ideal $ I$ of $ R_n$ is of the form $ g(x)R_n$. In other words every element of $ I$ is a multiple of $ g(x)$ for some polynomial $ g(x)$ in $ R_n$.

Ideals of the form $ I=g(x)R_n$ are called principal ideals, and $ g(x)$ is called a generator of the ideal $ I$.

Proof Suppose not. Let $ s(x)$ be a non-zero element in $ I$ of smallest degree. Pick an arbitrary non-zero element $ f(x)$ in $ I$. By the division algorithm, we can write $ f(x)=q(x)s(x)+r(x)$ where $ q$ and $ r$ are polynomials and either $ r(x)=0$ or the degree of $ r(x)$ is strictly less than the degree of $ s(x)$. Notice that $ r(x)=f(x)-q(x)s(x)$ belongs to $ I$ by definition. This contradicts the assumption that $ s(x)$ has smallest degree unless $ r(x)=0$. Therefore every element of $ I$ is a multiple of $ s(x)$. Take $ g(x)=s(x)$. $ \Box$

Definition 2   Let $ C$ be a cyclic code of length $ n$. Let $ I$ be the ideal corresponding to $ C$ by Lemma 1. We call $ g(x)$ a generator polynomial of $ C$ if it is a generator of $ I$.

Example 3   We continue with Example 2. Let $ g(x)=1+x^2+x^3$. This is the codeword polynomial associated to the top row of the generator matrix. $ g(x)$ is the generator polynomial of the cyclic code $ C$. Note that $ x^7-1=(x+1)(x^3+x^2+1)(x^3+x+1)$.

More generally we have the following result:

Lemma 3   The generator polynomial always divides $ x^n-1$.

Proof By the division algorithm $ x^n-1=q(x)g(x)+r(x)$ for some quotient $ q(x)$ and some remainder $ r(x)$ of degree less than $ g(x)$. In $ R_n$ this means that $ r(x)=-q(x)g(x)$. So $ r(x)$ corresponds to a codeword since $ g(x)$ is the generator polynomial. This is impossible since $ g(x)$ has minimal degree of any codeword in $ C$ unless $ r(x)=0$.$ \Box$

Lemma 4   If the generator polynomial $ g(x)$ of a cyclic code $ C$ has degree $ r$ then $ dim(C)=n-r$.

Proof To prove this it suffices to show that $ \vert C\vert=q^{n-r}$. Note that

$\displaystyle \langle g(x) \rangle=\{g(x)f(x) \vert f(x)\in \textbf{F}_q[x]/(x^n-1), {\rm {deg}}(f(x))\leq n-r-1\} $

has $ q^{n-r}$ elements. $ \Box$

Quadratic Residue Codes

Let $ p$ be a prime. We denote by $ GF(p)^\times$ the subset of non-zero elements in the field $ GF(p)$. For any finite field $ F$, $ F^\times$ is a cyclic group. A generator of that cyclic group is a called a primitive element of the field $ F$.

We define $ x\in GF(p)^\times$ to be a quadratic residue if $ x \pmod{p}$ is a square in the finite field $ GF(p)^\times$. Let $ Q\subseteq GF(p)^\times$ denote the subset of quadratic residues and $ N\subseteq GF(p)^\times$ denote the subset of non-quadratic residues.

A simple observation is that $ Q$ is a subgroup of $ GF(p)^\times$, in particular a quadratic residue times another quadratic residue is a quadratic residue. Similarly, a quadratic residue times a quadratic non-residue is a quadratic non-residue. In particular we can represent the quotient $ GF(p)^\times/Q$ using two elements, the identity $ 1$ and a fixed quadratic non-residue:

$\displaystyle \{1\cdot Q,\eta\cdot Q\}=GF(p)^\times/Q, $

where $ \eta$ denotes a fixed quadratic non-residue.

Definition 3   The Legendre symbol is defined by

\begin{displaymath} \left( \frac{a}{p}\right)= \left\{ \begin{array}{ll} 1,& {\rm if } a\in Q,\\ -1,& {\rm if } a\in N. \end{array}\right. \end{displaymath}

Observe that by the above discussion the Legendre symbol is a multiplicative character on $ GF(p)^\times$.

Lemma 5   $ \vert Q\vert=\vert N\vert=\frac{p-1}{2}$.

Proof Follows from the above observation by a simple counting argument. $ \Box$

Now let us define the family of quadratic residue codes.

Definition 4   Let $ p$ be a prime such that $ 2$ is a quadratic residue $ \pmod p$ (by quadratic reciprocity, we know $ p\equiv \pm1\pmod 8$). Choose an integer $ m$ such that $ 2^m-1$ is divisible by $ p$ and let $ \theta$ denote a primitive element of $ GF(2^m)$. Let $ \alpha =\theta^{(2^m-1)/p}$. Let

$\displaystyle g_Q(x)=\prod_{r\in Q}(x-\alpha^r), \ g_N(x)=\prod_{r\in N}(x-\alpha^r). $

Define $ C_Q$ to be the cyclic code of length $ p$ with generator polynomial $ g_Q$ and define $ C_N$ to be the cyclic code of length $ p$ with generator polynomial $ g_N$. These define the quadratic residue codes, or QR codes.

Note that these generator polynomials, $ g_Q$ and $ g_N$ both divide $ x^p-1$. By the lemma above $ \dim(C_Q)=\dim(C_N)=\frac{p+1}{2}$.

Example 4   This is the generator matrix for the QR code $ C_Q$ of length $ p=7$.

\begin{displaymath} G= \left( \begin{array}{ccccccc} 1&1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 0&0&1&1&0&1&0\\ 0&0&0&1&1&0&1 \end{array}\right) \end{displaymath}

For any binary code $ C$ of length $ n$ let $ \hat{C}$ denote the extended code defined by

$\displaystyle \hat{C}=\{(c_1,\cdots,c_n,c_{n+1}) \vert c_{n+1}=c_1+\cdots+c_n, (c_1,\cdots,c_n)\in C\}. $

For example if $ C$ is the code $ C_Q$ above then $ (1,1,0,1,0,0,0,1)$ belongs to $ \hat C$ since $ (1,1,0,1,0,0,0)$ belongs to $ C$.

Recall that ([MS],§1.9), the check matrix of $ \hat C$ is

\begin{displaymath} \hat H=\left( \begin{array}{clc} 1&1 \dots&1\\ & &0\\ &H& \vdots\\ & &0 \end{array} \right) \end{displaymath}

Lemma 6   If $ p\equiv 1 \pmod 4$ then $ (\hat C_Q)^\perp =\hat C_N$. If $ p\equiv -1 \pmod 4$ then $ (\hat C_N)^\perp =\hat C_N$ and $ (\hat C_Q)^\perp =\hat C_Q$.

One of the most remarkable facts about quadratic residue codes is the following theorem.

Theorem 1 (Gleason-Prange)   If $ p\equiv \pm1\pmod 8$ then the automorphism group of $ \hat C_Q$ contains a group isomorphic to $ PSL(2,p)$.

Recall that the automorphism group of a binary code of length $ n$ is the group of all permutations of the $ n$ coordinates which send codewords to codewords.

We intend to extend the Gleason-Prange theorem to a new class of codes studied here (called ``QQR codes").

Quasi-Quadratic Residue Codes

These are some observations on the interesting paper by Bazzi and Mitter [BM].

If $ S \subseteq GF(p)$, let $ f_S(x) = \prod_{a\in S}(x - a) \in GF(p)[x]$. Let $ \chi$ be the quadratic residue character, which is $ 1$ on the set $ Q$ quadratic residues in $ GF(p)^\times$, $ -1$ on the set $ N$ non-quadratic residues, and is 0 on $ 0\in GF(p)$. Let $ R = GF(2)[x]/(x^p - 1)$ and $ r_S \in R$ denotes the polynomial

$\displaystyle r_S(x) =\sum_{i\in S} x^i, $

where $ S \subseteq GF(p)$. (Note that $ r_S^2=r_{2S}$, where $ 2S$ is the set of elements $ 2s\in GF(p)$, for $ s\in S$. In particular, since $ Q\subseteq GF(p)^\times$ is a subgroup, $ r_Q^2=r_Q$ if and only if $ 2\in Q$ if and only if $ p\equiv \pm1\pmod 8$ (by the quadratic reciprocity law). Moreover, if $ 2\in N$ then $ r_Q^2=r_N$.)

Define the QQR code as

$\displaystyle C_{NQ}=\{(r_N r_S, r_Q r_S) \vert S \subseteq GF(p)\}, $

where $ N,Q$ are as above. These are binary codes of length $ 2p$ and dimension $ p$.

Lemma 7 (Bazzi-Mitter [BM], Proposition 3.3)   Assume $ 2$ and $ -1$ are non-quadratic residues mod $ p$ (i.e. $ p \equiv 3 \pmod 8$).

If $ c=(r_N r_S, r_Q r_S)$ is a nonzero codeword of the $ [2p,p]$ binary code $ C_{NQ}$ then the weight of this codeword can be expressed in terms of a character sum as

$\displaystyle wt(c)=p - \sum_{a\in GF(p)} \chi(f_S(a)), $

if $ \vert S\vert$ is even, and

$\displaystyle wt(c)=p + \sum_{a\in GF(p)} \chi(f_{GF(p)-S}(a)), $

if $ \vert S\vert$ is odd.

In fact, looking carefully at their proof, one finds the following result:

Lemma 8   Let $ c=(r_N r_S, r_Q r_S)$ be a nonzero codeword of $ C_{NQ}$.
(a)
If $ \vert S\vert$ is even

$\displaystyle wt(c)=p - \sum_{a\in GF(p)} \chi(f_S(a)). $

(b)
If $ \vert S\vert$ is odd and $ p\equiv 1 \pmod 4$ then the weight is

$\displaystyle wt(c)=p - \sum_{a\in GF(p)} \chi(f_{GF(p)-S}(a)). $

(c)
If $ p\equiv 3\pmod 4$ and $ \vert S\vert$ odd both hold then

$\displaystyle wt(c)=p + \sum_{a\in GF(p)} \chi(f_{GF(p)-S}(a)). $

Proof If $ A,B\subseteq GF(p)$ then we claim

$\displaystyle wt(r_A r_B)=\sum_{k\in GF(p)} {\rm parity} \vert A\cap (k-B)\vert, $ (4)

where $ k-B=\lbrace k-b \vert b\in B\rbrace$. In general it is true that $ (\sum_\ell a_\ell x^\ell)(\sum_m b_m x^m)=\sum_n c_n x^n, c_n=\sum_{\ell+m=n} a_\ell b_m$. Indeed,

$\displaystyle r_A(x) r_B(x)=\sum_{k\in GF(p)} n_k x^k,$

where $ n_k$ counts the $ x\in A$, $ y\in B$ such that $ x+y=k$. Now

$\displaystyle n_k\equiv \sum_{x\in A\cap (k-B)} 1=\vert A\cap (k-B)\vert \pmod 2, $

so (4) is true.

Let $ S \subseteq GF(p)$, then we have

$\displaystyle p-wt(r_Q r_S)-wt(r_N r_S)=\sum_{a\in GF(p)} 1- {\rm parity} \vert Q\cap (a-S)\vert- {\rm parity} \vert N\cap (a-S)\vert. $

Let

$\displaystyle T_a(S)=1- {\rm parity} \vert Q\cap (a-S)\vert- {\rm parity} \vert N\cap (a-S)\vert. $

Case 1. If $ \vert S\vert$ is even and $ a\in S$ then $ 0\in a-S$ so $ \vert Q\cap (a-S)\vert$ odd implies that $ \vert N\cap (a-S)\vert$ is even, since 0 is not included in $ Q\cap (a-S)$ or $ N\cap (a-S)$. Likewise, $ \vert Q\cap (a-S)\vert$ even implies that $ \vert N\cap (a-S)\vert$ is odd. Therefore $ T_a(S)=0$.

Case 2. If $ \vert S\vert$ is even and $ a\notin S$ then parity $ \vert Q\cap (a-S)\vert=$parity $ \vert N\cap (a-S)\vert$. If $ \vert Q\cap (a-S)\vert$ is even then $ T_a(S)=1$ and if $ \vert Q\cap (a-S)\vert$ is odd then $ T_a(S)=-1$.

Case 3. $ \vert S\vert$ is odd. We claim that $ (a-S)^c=a-S^c$. (Proof: Let $ s\in S$ and $ \bar s\in S^c$. Then $ a-s=a-\bar s\implies s=\bar s$, which is obviously a contradiction. Therefore $ (a-S)\cap (a-S^c)=\emptyset$, so $ (a-S)^c\supseteq(a-S^c).$ Replace $ S$ by $ S^c$ to prove the claim.) Also note that

$\displaystyle Q\cap (a-S)\sqcup Q\cap (a-S^c)=GF(p)\cap Q=Q $

has $ \vert Q\vert=\frac{p-1}{2}$ elements. So

$\displaystyle {\rm parity} \vert Q\cap (a-S)\vert={\rm parity} \vert Q\cap (a-S^c)\vert $

iff $ \vert Q\vert$ is even and

$\displaystyle {\rm parity} \vert Q\cap (a-S)\vert \neq {\rm parity} \vert Q\cap (a-S^c)\vert $

iff $ \vert Q\vert$ is odd.

Conclusion.

$\displaystyle \vert S\vert {\rm even\colon} T_a(S)=\prod_{x\in a-S}\left( \frac{x}{p}\right) $

$\displaystyle \vert S\vert {\rm odd and} p\equiv 3\pmod 4\colon T_a(S)=-T_a(S^c) $

$\displaystyle \vert S\vert {\rm odd and} p\equiv 1\pmod 4\colon T_a(S)=T_a(S^c) $

From which the lemma follows. $ \Box$

Remark 1  

Remarks on QQR Codes: These codes have very interesting but unexplained behavior. The conjecture of Bazzi-Mitter that they (or a subsequence of them) form a ``good family'' of codes (where the rate, relative minimum distance pair $ (R,\delta)$ stays bounded away from the axes $ R=0$ and $ \delta=0$) seems not to be consistent with the above (very limited) data on $ (R,\delta)$ values, except possibly in the case $ p\equiv 1\pmod 8$.

For a result similar in spirit to the lemma above, see also [HV]. For more information on quadratic residue codes, see [MS], [HP], [vLM], and [W].


Long Quadratic Residue Codes

We now introduce a new code, constructed similarly to the Quasi-Quadratic Residue Codes discussed earlier:

$\displaystyle C=\lbrace ({r}_N r_S, {r}_Q r_S, {r}_N r_{S^c}, {r}_Q r_{S^c}) \vert\ S\subseteq GF(p)\rbrace $

where, for $ p$ prime and $ T\subseteq GF(p)$,

$\displaystyle r_T(x)=\sum_{i\in T} x^i. $

Observe that this code is non-linear with respect to the usual coordinate-wise addition.

For any $ S \subseteq GF(p)$, let

$\displaystyle c_S=({r}_N r_S, {r}_Q r_S, {r}_N r_{S^c}, {r}_Q r_{S^c}) $

and let

$\displaystyle v_S=({r}_N r_S, {r}_Q r_S, {r}_N r_{S}, {r}_Q r_{S}). $

If $ S_1\Delta S_2$ denotes the symmetric difference between $ S_1$ and $ S_2$ then it is easy to check that

$\displaystyle c_{S_1}+c_{S_2}=v_{S_1\Delta S_2}.$ (5)

We know that

\begin{displaymath} wt({r}_N r_S,{r}_Q r_S) = \left\{ \begin{array}{ll} p-\sum_{... ...t S\vert {\rm odd and} p\equiv 3\pmod 4, \end{array}\right. \end{displaymath}

by Lemma 8. If $ p\equiv 1 \pmod 4$ then

\begin{displaymath}\begin{array}{ll} wt\left( {r}_N r_S, {r}_Q r_S, {r}_N r_{S^c... ...\right)+ \left(\frac{f_{S^c} (a)}{p}\right)\right]. \end{array}\end{displaymath} (6)

We have the following trivial estimates:

$\displaystyle \vert\sum_{a\in GF(p)} \left(\frac{f_S (a)}{p}\right)\vert \leq \vert S^c\vert $

and

$\displaystyle \vert\sum_{a\in GF(p)} \left(\frac{f_{S^c} (a)}{p}\right)\vert \leq \vert S\vert, $

therefore

$\displaystyle \vert\sum_{a\in GF(p)} \left[\left(\frac{f_S (a)}{p}\right)+ \left(\frac{f_{S^c} (a)}{p}\right)\right]\vert \leq \vert S^c\vert+\vert S\vert=p. $

This implies the minimum non-zero weight $ \rho$ of $ C$ satisfies $ \rho\geq p$, when $ p\equiv 1 \pmod 4$.

We now compute the size of $ C$. We now prove the claim: if $ p\equiv 3\pmod 4$ then the map that sends $ S$ to the codeword $ ({r}_N r_S, {r}_Q r_S, {r}_N r_{S^c}, {r}_Q r_{S^c})$ is injective. This implies $ \vert C\vert=2^p$. Suppose not, then there are two subsets $ S_1, S_2\subseteq GF(p)$ that are mapped to the same codeword. Subtracting, the subset $ T=S_1\Delta S_2$ satisfies $ r_Q r_T=r_N r_T=r_Q r_{T^c}=r_N r_{T^c}=0$. If $ \vert T\vert$ is even then $ 0=(r_Q + r_N)r_T=(r_{GF(p)}-1)r_T=r_T$. This forces $ T$ to be the empty set, so $ S_1=S_2$. Now if $ \vert T\vert$ is odd then similar reasoning implies that $ T^c$ is the empty set. Therefore, $ S_1=\emptyset$ and $ S_2=GF(p)$ or vice versa. This proves the claim.

In case $ p\equiv 1 \pmod 4$, claim: $ \vert C\vert=2^{p-1}$. Again, suppose there are two subsets $ S_1, S_2\subseteq GF(p)$ that are mapped to the same codeword. Then the subset $ T=S_1\Delta S_2$ for which $ r_Q r_T=r_N r_T=r_Q r_{T^c}=r_N r_{T^c}=0$. This implies either $ T=\emptyset$ or $ T=GF(p)$. Therefore, either $ S_1=S_2$ or $ S_1=S_2^c$.

We have proven the following result.

Theorem 2   The non-linear code $ C$ has length $ n=4p$ and minimum non-zero weight $ \rho\geq p$. It has size $ M=2^{p-1}$ if $ p\equiv 1 \pmod 4$, and size $ M=2^p$ if $ p\equiv 3\pmod 4$.

Duality in the LQR code

First, a few observations.

For any $ T\subseteq GF(p)$, let $ \overline{T}$ denote the set which is $ T\cup \{0\}$ if $ 0\notin T$, and $ T-\{0\}$ if $ 0\in T$.

By (5), it suffices to find the minimum non-zero weight of $ v_S$, $ S \subseteq GF(p)$. We first find a ``duality'' relation between $ v_S$ and $ v_{S^c}$, and $ c_S$ and $ c_{S^c}$.

By (6), it is obvious that if $ p\equiv 1 \pmod 4$ then $ v_S=v_{S^c}$.

If $ p\equiv 1 \pmod 4$ then $ r_{GF(p)}r_Q=r_{GF(p)}r_N=0$, so

$\displaystyle v_{GF(p)}=(0,0,0,0)\in R_p^4=GF(2)^n. $

If $ p\equiv 3\pmod 4$ then $ r_{GF(p)}r_Q=r_Q$, $ r_{GF(p)}r_N=r_N$, so

$\displaystyle v_{GF(p)}=(r_N,r_Q,r_N,r_Q). $

These facts together with (5) imply: if $ p\equiv 1 \pmod 4$ then $ c_S=c_{S^c}$; if $ p\equiv 3\pmod 4$ then $ c_S=c_{S^c}+(r_N,r_Q,r_N,r_Q)$. Consequently, if $ p\equiv 3\pmod 4$ then

\begin{displaymath} \begin{array}{ll} v_{S_1\Delta S_2}=c_{S_1}+c_{S_2}&= c_{S_1... ...,r_N,r_Q) =v_{(S_1\Delta S_2)^c}+(r_N,r_Q,r_N,r_Q). \end{array}\end{displaymath}

In particular, if $ p\equiv 3\pmod 4$ then $ v_S=v_{S^c}+(r_N,r_Q,r_N,r_Q), $ and this can be more compactly re-expressed as

$\displaystyle v_S=v_{\overline{S^c}},$ (7)

provided $ p\equiv 3\pmod 4$.

By (5), we have

$\displaystyle c_S=c_{S^c},$ (8)

provided $ p\equiv 1 \pmod 4$. Now that we know this, we can write, if $ p\equiv 1 \pmod 4$,

$\displaystyle v_{S_1\Delta S_2}=c_{S_1}+c_{S_2}=c_{S_1}+c_{S_2^c} =v_{S_1\Delta S_2^c}=v_{(S_1\Delta S_2)^c}. $

In particular,

$\displaystyle v_S=v_{S^c},$ (9)

provided $ p\equiv 1 \pmod 4$. This is also a consequence of (5) and (8). (So now we have at least three proofs of this fact!)

Linear version of the LQR code

Let us denote the map $ S\longmapsto c_S$ by $ \phi$ and its inverse (which only exists if $ p\equiv 3\pmod 4$) by $ \psi$.

When $ p\equiv 3\pmod 4$, define ``addition'' $ \oplus$ on $ C$ by

$\displaystyle c_{S_1}\oplus c_{S_2}=c_{S_1\Delta S_2},$ (10)

for arbitrary subsets of $ GF(p)$. It is easy to check that this operation $ \oplus$ is well-defined in case $ p\equiv 3\pmod 4$.

The surprising fact is the following result.

Lemma 9   In case $ p\equiv 1 \pmod 4$, (10) is well-defined.

Proof Assume $ p\equiv 1 \pmod 4$. Recall from the above discussion that $ \phi$ is a 2-to-1 map from the set $ 2^{GF(p)}$ of subsets of $ GF(p)$ to the codewords of $ C$. For all $ c\in C$, there is a $ S \subseteq GF(p)$ and $ c=c_T$ (for $ T\subseteq GF(p)$) if and only if $ T=S$ or $ T=S^c$. We know $ c_{S_1^c\Delta S_2}=c_{S_1\Delta S_2^c}=c_{S_1^c\Delta S_2^c} =c_{(S_1\Delta S_2)^c}$. This implies $ \oplus$ does not depend on the choice in $ \phi^{-1}(c_{S_1})=\{S_1,S_1^c\}$, $ \phi^{-1}(c_{S_2})=\{S_2,S_2^c\}$ made to compute the right-hand side of (10). $ \Box$

This operation $ \oplus$ is commutative, since the symmetric difference operation $ \Delta$ is symmetric, and it is associative since $ \Delta$ is associative. Each element is the inverse of itself and the element $ c_\emptyset = 0$ is the identity.

Therefore, $ C$ is a vector space over $ GF(2)$ with the operation $ \oplus$. When $ p\equiv 3\pmod 4$, the set of codewords $ c_S$, $ S$ a singleton subset of $ GF(p)$, form a basis. When $ p\equiv 1 \pmod 4$, the set of codewords $ c_S$, $ S$ a singleton subset of $ GF(p)$, are linearly dependent (their sum is 0), so do not form a basis. However, if you just omit one (any one - pick your least favorite), you get a basis.

Define the metric $ d_\oplus$ as follows. For $ c_1,c_2\in C$, let

$\displaystyle d_\oplus(c_1,c_2)=wt(c_1\oplus c_2). $

Of course, the Hamming metric, denoted $ d_H$ to be unambiguous, satisfies $ d_H(c_1,c_2)=wt(c_1+ c_2)$.

We make a few remarks comparing $ d_\oplus$ to $ d_H$. If $ c\in C\cong R_p^4$ is written $ c=(p_1(c),p_2(c),p_3(c),p_4(c))$, for polynomials $ p_i(c)\in R_p$, then

$\displaystyle wt(c_1\oplus c_2)= wt(p_1(c_1\oplus c_2))+wt(p_2(c_1\oplus c_2))+ wt(p_3(c_1\oplus c_2))+wt(p_4(c_1\oplus c_2)), $

and

$\displaystyle wt(c_1+ c_2)= wt(p_1(c_1+ c_2))+wt(p_2(c_1+ c_2))+ wt(p_3(c_1+ c_2))+wt(p_4(c_1+ c_2)). $

By definition of $ C$,

$\displaystyle wt(p_1(c_1\oplus c_2))=wt(p_1(c_1+ c_2)), wt(p_2(c_1\oplus c_2))=+wt(p_2(c_1+ c_2)). $

On the other hand, if $ c_1=c_{S_1}$, $ c_2=c_{S_2}$,

$\displaystyle wt(p_3(c_1\oplus c_2))+wt(p_4(c_1\oplus c_2)) =wt(r_Nr_{(S_1\Delta S_2)^c})+wt(r_Qr_{(S_1\Delta S_2)^c}) $

and

$\displaystyle wt(p_3(c_1+ c_2))+wt(p_4(c_1+ c_2)) =wt(r_Nr_{S_1\Delta S_2})+wt(r_Qr_{S_1\Delta S_2}). $

The difference between $ d_\oplus(c_1,c_2)$ and $ d_H(c_1,c_2)$ can now by computed using Lemma 8.

We assert that, with this notion of addition, the ``$ \oplus$-Hamming metric'' on $ (C,\oplus)$ is the more ``natural'' one to use.

This and the previous section prove the following result.

Theorem 3   The linear code $ (C,\oplus)$ has length $ n=4p$ and minimum $ \oplus$-distance $ d\geq p$. It has size $ M=2^{p-1}$ if $ p\equiv 1 \pmod 4$, and size $ M=2^p$ if $ p\equiv 3\pmod 4$.

The fake Singleton bound

Here is an example from Amin Shokrollahi [S].

This example will construct, in a naive way, a set of $ 2^m$ vectors, call it $ C$, in $ {\mathbb{F}}_2^{2m}$, and an addition $ \&$ in $ C$, such that $ C$ is a binary vector space under $ \&$, and such that the weight of $ c\&c'$ is always at least $ n$ (this construction gets you all the way to the ``fake Singleton" bound). Here it is.

Let $ \ell$ denote the $ n$-dimensional vector in which all entries are $ 1$. Let $ C = \{ ( a , a+\ell) \vert a \in {\mathbb{F}}_2^m\}$. For $ c = ( a , a + \ell)$ and $ c' = (a', a'+\ell)$ let $ c \& c' := ( a + a' , a + a'+\ell)$. Under this ``addition" $ C$ becomes a binary vector space. The weight of any element in $ C$ is $ m$, so the $ \&$-distance of any two elements in $ C$, defined as the weight of their $ \&$-addition, is $ m$. This is a code of length $ n=2m$, dimension $ k=m$, and minimum $ \&$-distance $ d_{\&}=m$, so the fake singleton bound $ k+d_{\&}\leq n+1$ is almost attained. In particular, we have asymptotic rate $ R=\frac{1}{2}$ and relatively minimum $ \oplus$-distance $ \delta_{\&}=\frac{1}{2}$.

Gilbert-Varshamov

Background

The volume of a Hamming sphere of radius $ r$ in $ GF(2)^n$ is

$\displaystyle V(n,r)=\sum_{i=0}^r \left(\begin{array}{c} n\ i\end{array}\right). $

The binary version of the Gilbert-Varshamov bound asserts that there is a code $ C$ (possibly non-linear) of length $ n$ and minimum distance $ d$ which has at least $ \frac{2^n}{V(n,d-1)}$ elements [HP]. A well-known conjecture of Goppa asserts that the binary version of the Gilbert-Varshamov bound is asymptotically exact ([JV],[G]).

Conjecture 1 (Fake Goppa Conjecture)   There is no infinite family of codes $ (C_i,\oplus)$, with addition $ \oplus$ not the usual coordinatewise addition and distance $ d_\oplus$ as above, for which the binary version of the $ \oplus$-Gilbert-Varshamov bound is asymptotically exact.

Figure 1: The Gilbert-Varshamov bound: $ R\geq 1-H(\delta )$
\includegraphics[height=5cm,width=5cm]{gilbertvarshamov.eps}

Here $ H(\delta)=\delta-\delta\log_2(\delta)-(1-\delta)\log_2(1-\delta)$ is sometimes referred to as the entropy of the code.

The Gilbert-Varshamov bound implies that there is a code with relative minimum distance $ \delta=0.25$ and rate $ R\geq0.21...$. However our code $ (C,\oplus)$ above yields $ \delta_\oplus=0.25$ and $ R=0.25$.

Therefore we have constructed a linear binary code which beats the $ \oplus$-Gilbert-Varshamov bound, thereby disproving the fake Goppa's conjecture.

Goppa's conjecture was investigated recently by Jiang and Vardy [JV], where they proved that there is a code $ C$ (possibly non-linear) of ``sufficiently large" length $ n$ and minimum distance $ d$ which has at least $ c\frac{2^n}{V(n,d-1)}\log_2 (V(n,d-1))$ elements, where $ c$ is a positive constant which they do not determine. Our result is somewhat different because we show that if $ \delta_\oplus=0.25$ then the rate $ R=\frac{\log_2(\vert C\vert)}{n}$ can be taken larger than that predicted either by $ \oplus$ analogs of the Gilbert-Varshamov bound or the Jiang-Vardy bound.

Connection with hyperelliptic curves

A hyperelliptic curve over $ GF(p)$ is a polynomial equation of the form $ y^2=h(x)$ where $ h(x)$ is a polynomial with coefficients in $ GF(p)$ with distinct roots. We will consider the hyperelliptic curve $ X_S$ defined by $ y^2=f_S(x)$ where $ f_S$ is defined in section 3. We will let $ \vert X_S(GF(p))\vert$ denote the cardinality of the set of all $ (x,y)$ satisfying $ y^2=f_S(x)$ plus the number of points at infinity on $ X_S$. We define the content of $ X_S$ to be $ \vert X_S(GF(p))\vert/p$.

Conjecture 2 (Small content conjecture for split hyperelliptics)  

For an infinite number of primes $ p$ for which $ p\equiv 1 \pmod 4$, the content of $ X_S$ is less than $ 1.57$.

The goal of this section is to prove the following result which relates the theory of error-correcting codes to the theory of hyperelliptic curves over finite fields.

Theorem 4   If the small content conjecture is true then Goppa's conjecture is false.

Proof Recall Goppa's conjecture is that the binary Gilbert-Varshamov is best possible for any family of binary codes. The GV bound states that the rate $ R$ is greater than or equal to $ 1-H(\delta)$, where $ H(\delta)=\delta-\delta\log_2(\delta)-(1-\delta)\log_2(1-\delta)$. According to Goppa's conjecture if $ R=\frac{1}{4}$ then the best possible $ \delta$ is $ \delta_0=.215$. This means that the minimum distance of our long quadratic residue code with rate $ R=\frac{1}{4}$ satisfies $ d<\delta_0\cdot 4p=.859p$. Recall that the weight of a codeword $ c$ in this LQR code is the weight of the 4-tuple of polynomials $ (r_Nr_S,r_Qr_S,r_Nr_{S^c},r_Qr_{S^c})$. Let us assume $ \vert S\vert$ is even for simplicity. Then by Lemma 8 and remark 1 we know that the $ wt(r_Nr_S,r_Qr_S)=2p+2-\vert X_S(GF(p))\vert$. Now suppose $ \vert S\vert$ is odd and $ p\equiv 1 \pmod 4$. Then By lemma 8 and remark 1 we know that the $ wt(r_Nr_S,r_Qr_S)=2p+1-\vert X_S(GF(p))\vert$. By the small content conjecture, $ wt(r_Nr_S,r_Qr_S)\geq 2p+1-\vert X_S(GF(p))\vert>2p-1.57p=.43p$. Therefore $ min_S wt((r_Nr_S,r_Qr_S,r_Nr_{S^c},r_Qr_{S^c}))\geq 2\cdot min_S wt(r_Nr_S,r_Qr_S)>.86p$. This contradicts the estimate above.$ \Box$

Acknowledgements: I thank Prof. Amin Shokrollahi of the Ecole Polytechnique Federale de Lausanne in Switzerland for his helpful remarks.

Bibliography

[BM] L. Bazzi and S. Mitter, Some constructions of codes from group actions, preprint, 2001.

[Gap] The GAP Group, GAP - Groups, Algorithms, and Programming, Version 4.4; 2002, (http://www.gap-system.org).

[G] V. D. Goppa, Bounds for codes, Dokl. Acad. Nauk. 333(1993)423.

[GU] GUAVA homepage and GUAVA's GAP page

[HP] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge Univ. Press, 2003.

[HV] T. Helleseth and J. F. Voloch, Double circulant quadratic residue codes, IEEE Transactions in Information Theory, to appear.
Available on Prof. Voloch's preprint webpage

[JV] T. Jiang and A. Vardy, Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes, IEEE Trans Info Theory, to appear.

[M] Jason McGowan, Implementing generalized Reed-Solomon codes and a cyclic code decoder in GUAVA, USNA Honors Thesis 2004-2005.

[MS] F. MacWilliams and N. Sloane, The theory of error-correcting codes, North-Holland, 1977.

[S] A. Shokrollahi, email communication, 2-2006.

[vLM] J. van Lint, F. J. MacWilliams, Generalized quadratic residue codes, Proc. IEEE Trans Info Theory 24(1978)730-737.

[W] H. N. Ward, Quadratic residue codes and symplectic groups, J. Algebra 29(1974)150-171.

About this document ...

Long Quadratic Residue Codes

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -t 'G. Coy Math Honors Thesis 2005-2006' -split 0 finalhonorspaper.tex

The translation was initiated by David Joyner on 2006-04-19

Footnotes

... Coy1
Department of Mathematics, United States Naval Academy, Honors Thesis 2005-2006, Advisor Prof. Joyner, wdj@usna.edu
David Joyner 2006-04-19