%%the paper \documentclass{amsart} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{xca}[theorem]{Exercise} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} % Absolute value notation \newcommand{\abs}[1]{\lvert#1\rvert} % Blank box placeholder for figures (to avoid requiring any % particular graphics capabilities for printing this document). \newcommand{\blankbox}[2]{% \parbox{\columnwidth}{\centering % Set fboxsep to 0 so that the actual size of the box will match the % given measurements more closely. \setlength{\fboxsep}{0pt}% \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}% }% } \def\Gm{{\mathbb G}_m} \def\Z{{\mathbb Z}} \def\F{{\mathbb F}} \def\isom{\cong} \def\P{{\mathbb P}} \def \d{\delta} \def \t{\tau} \def \m{{\mathfrak m}} \def \spec{\operatorname{Spec}} \def \supp{\operatorname{supp}} \def \cl{{\mathcal L}} \def \co{{\mathcal O}} \def \cz{{\mathcal Z}} \def \ce{{\mathcal E}} \def \cf{{\mathcal F}} \def \cp{{\mathcal P}} \def \x{{\mathbf x}} \def \y{{\mathbf y}} \def \f{{\mathbf f}} \def \real{\operatorname{Re}} \def \ringX{{\mathbf X}} \def\ringE{{\mathbf E}} \def\ringf{{\mathbf f}} \def\ringO{{\mathbf O}} \begin{document} \title{Lee weights of $\Z/4\Z$-codes from elliptic curves} \author{Jos\'e Felipe Voloch} \address{Department of Mathematics, University of Texas, Austin, TX 78712} \email{voloch@math.utexas.edu} % \thanks will become a 1st page footnote. \thanks{The first author was supported in part by NSA Grant \#MDA904-97-1-0037 and TARP Grant \#ARP-006.} % Information for second author \author{Judy L. Walker} \address{Department of Mathematics and Statistics, University of Nebraska, Lincoln, NE 68588-0323} \email{jwalker@math.unl.edu} \thanks{The second author was supported in part by NSF Grant \#DMS-9709388.} % General info \subjclass{Primary 94B27; Secondary 11T71, 11G07} \date{\today} \thanks{To Dick Blahut, in honor of his sixtieth birthday.} \keywords{Codes, Artin rings, Exponential sums, Elliptic curves} \begin{abstract} In \cite{W1}, the second author defined algebraic geometric codes over rings. This definition was motivated by two recent trends in coding theory: the study of algebraic geometric codes over finite fields, and the study of codes over rings. In that paper, many of the basic parameters of these new codes were computed. However, the Lee weight, which is very important for codes over the ring $\Z/4\Z$, was not considered. In \cite{VW}, this weight measure, as well as the more general Euclidean weight for codes over $\Z/p^l\Z$, is considered for algebraic geometric codes arising from elliptic curves. In this paper, we will focus on the specific case of codes over $\Z/4\Z$ and we will show how everything works in an explicit example. \end{abstract} \maketitle \section{Introduction} The study of linear codes over finite rings has received much attention lately. This is due in large part to the paper of Hammons, et al.~(\cite{HKCSS}), in which it is shown that certain nonlinear binary codes are actually the images of linear codes over the ring $\Z/4\Z$ under the Gray map. This idea has prompted many authors (see \cite{CM} or \cite{sole}, for example) to consider the question of how to construct linear codes over $\Z/4\Z$, with the hope that these codes might have good binary images under the Gray map. In \cite{W1}, a new method of constructing linear codes over $\Z/4\Z$ was proposed. The idea there was to generalize the construction of algebraic geometric codes over finite fields (\cite{St}, \cite{TV}) to allow the use of a local Artin ring to play the role of the finite field. In that paper, the length, dimension (rank), and minimum Hamming distance of these new codes were computed. However, the crucial Lee weight, which is the same as the Hamming weight of their binary images under the Gray map, was not treated there. It turns out that computing the minimum Lee weight of an algebraic geometric code is very difficult. In \cite{thesis}, it is shown how the notion of Lee weight for codes over $\Z/4\Z$ generalizes to a weight measure called Euclidean weight for codes over $\Z/p^l\Z$, where $p$ is any prime and $l\geq 1$ is an integer. Also in that paper, the minimum Euclidean weight of an algebraic geometric code over $\Z/p^l\Z$ is expressed in terms of an exponential sum. In \cite{VW}, a bound on this sum is found in the special case that the curve over which the code is defined is a certain type of elliptic curve. In this paper, we will examine in detail the case of \cite{VW} where $p = l = 2$, so that the code in question is a code over $\Z/4\Z$. To illustrate our results, we work a specific example in detail. \section{Galois and Witt rings, and Algebraic geometric codes over them} \label{defs} A common method of constructing long codes over small fields is to construct a code over an extension field and then consider the trace code. A similar approach can be taken to construct codes over the ring $\Z/4\Z$ by first constructing codes over a {\it Galois Ring} $GR(4,m)$, and then considering the trace code. Recall (\cite{HKCSS}) that the Galois Ring $GR(4,m)$ is simply $(\Z/4\Z)[x]/(f)$, where $f \in (\Z/4\Z)[x]$ is monic, irreducible, and a divisor of the polynomial $x^{2^m-1}-1$. More generally, the Galois ring $GR(p^l,m)$ is $(\Z/p^l\Z)[x]/(f)$, where $f \in (\Z/p^l\Z)[x]$ is monic and irreducible and divides the polynomial $x^{p^m-1}-1$. Notice that $GR(p^l,1) \simeq \Z/p^l\Z$. Recall that the {\it Teichm\"uller set} of $GR(p^l,m)$ is the multiplicative lifting of the field $\F_{p^m}$ living inside $GR(p^l,m)$. It is often more convenient to think of the ring $GR(4,m)$ as the ring $W_2(\F_{2^m})$ of 2-dimensional {\it Witt vectors} over the field $\F_{2^m}$. As a set, this ring looks like vectors of length 2 with coordinates in $\F_{2^m}$, and the operations are given as follows: \begin{align*} (a_0,a_1) + (b_0, b_1) &= (a_0+b_0, a_1 + b_1 + a_0b_0) \\ (a_0,a_1) \cdot (b_0, b_1) &= (a_0b_0, a_0^2b_1 + b_0^2a_1) \end{align*} This ring may be thought of as the quotient modulo $4$ of $W(\F_{2^m})$, the ring of infinite length Witt vectors over $\F_{2^m}$ (see \cite{Lang}). Also, one can consider Witt rings over fields of characteristic other than 2, or of finite lengths other than $2$. Notice that the map \begin{align} \label{iso} W_2(\F_2) &\to \Z/4\Z \\ \intertext{given by} (0,0) &\mapsto 0 \nonumber \\ (1,0) &\mapsto 1 \nonumber \\ (0,1) &\mapsto 2 \nonumber \\ (1,1) &\mapsto 3 \nonumber \end{align} is an isomorphism of rings. More generally, $W_l(\F_p) \simeq \Z/p^l\Z$ for any prime $p$ and any positive integer $l$. Similarly, $W_2(\F_{2^m}) \simeq GR(4,m)$ for all $m$ and more generally $W_l(\F_{p^m}) \simeq GR(p^l,m)$. The Teichm\"uller set of $GR(p^l,m)$ corresponds to the vectors in $W_l(\F_{p^m})$ which are zero beyond the first coordinate. The map $F:W_l(\F_{p^m}) \to W_l(\F_{p^m})$ given by $(a_0, a_1, \dots, a_{l-1}) \mapsto (a_0^p, a_1^p, \dots, a_{l-1}^p)$ is an additive endomorphism of order $m$. The trace map $T:W_l(\F_{p^m}) \to W_l(\F_p) \simeq \Z/p^l\Z$ is given by $T(a) = F(a) + F^2(a) + \dots + F^{m-1}(a)$. The generalization of algebraic geometric codes which we will describe below will make sense for any {\it local Artin} ring $A$. Recall that a local ring is one with only one maximal ideal. $GR(p^l,m)$ is local with its unique maximal ideal being the one generated by $p$. In $W_l(\F_{p^m})$, this ideal consists of the elements having zeros in the first coordinate. An Artin ring is one in which every descending chain of ideals is eventually stable; since any finite ring obviously satisfies this property, $GR(p^l,m) \simeq W_l(\F_{p^m})$ is an Artin ring. Next, we describe how to generalize the construction of algebraic geometric codes over finite fields (\cite{TV}, \cite{St}) to give codes over local Artin rings such as $W_l(\F_{p^m}) \simeq GR(p^l,m)$. The set-up for the generalized construction is as follows: Let $A$ be a local Artin ring, and let $\ringX$ be a curve defined over $A$ (i.e., a connected irreducible scheme over $\spec A$ which is smooth and of relative dimension one). One may think of $\ringX$ as being defined by polynomial equations with coefficients in $A$. In this case, $A$-points on $\ringX$ are solutions in $A$ to the equations defining $\ringX$. Letting $\m$ be the maximal ideal of $A$, we get a curve $X$ over the field $A/\m$ by reducing the equations defining $\ringX$ modulo $\m$. By reducing the coordinates of an $A$-point of $\ringX$ modulo $\m$, we get a $A/\m$-rational point of $X$. We say two $A$-points of $\ringX$ are {\it disjoint} if their reductions modulo $\m$ give two distinct $A/\m$-rational points of $X$. Let $\cz$ be a set of disjoint $A$-points on $\ringX$. Associated to a line bundle $\cl$ on $\ringX$ is an $A$-module $\Gamma(\ringX, \cl)$ of rational functions on $\ringX$, and $\cl$ may easily be chosen so that it makes sense to evaluate the functions in $\Gamma(\ringX, \cl)$ at the points of $\cz$. With $A$, $\ringX$, $\cz = \{Z_1, \dots, Z_n\}$, and $\cl$ as above, the algebraic geometric code $C_A(\ringX, \cz, \cl)$ is defined to be the image of the evaluation map \begin{align*} \Gamma(\ringX, \cl) &\to A^n \\ f &\mapsto (f(Z_1), \dots, f(Z_n)) \end{align*} Some of the properties of these codes are summarized in the following theorem; see \cite{W1} for proofs. \begin{theorem}\label{ringcodes} Let $\ringX$, $X$, $\cl$, and $\cz = \{Z_1, \dots, Z_n\}$ be as above. Let $g$ denote the genus of $X$, and suppose $2g-2 < \deg \cl < n$. Set $C = C(\ringX, \cz, \cl)$. Then $C$ is a linear code of length $n$ over $A$, and is free as an $A$-module. The dimension (rank) of $C$ is $k = \deg \cl + 1 - g$, and the minimum Hamming distance of $C$ is at least $n - \deg \cl$. Further, under the additional assumption that $A$ is Gorenstein, the class of algebraic geometric codes is closed under taking duals. In particular, there exists a line bundle $\ce$ such that $C^\perp = C(\ringX, \cz, \ce)$. \end{theorem} \begin{remark} {\rm The rings $W_l(\F_p) \simeq \Z/p^l\Z$ and $W_l(\F_{p^m}) \simeq GR(p^l,m)$ are Gorenstein, so everything in the above theorem applies to these rings in particular.} \end{remark} In practice, one is usually most interested in codes over the ring $\Z/4\Z$. Such a code can be obtained in two ways using the construction above. First, one can simply set $A = \Z/4\Z$ and construct an algebraic geometric code over $\Z/4\Z$ directly. The drawback of this is that the codes obtained in this manner will be short. A second method is to set $A = W_2(\F_{2^m}) = GR(4,m)$, construct an algebraic geometric code over $A$, and then apply the trace map $T:A \to \Z/4\Z$ coordinatewise to the code to get a code over $\Z/4\Z$. Since $T:\Z/4\Z \to \Z/4\Z$ is the identity map, we need only consider the second of these two constructions. \section{Lee weight} \label{lee} Theorem \ref{ringcodes} gives the length, dimension, and minimum Hamming distance of an algebraic geometric code over a ring. However, for codes over $\Z/4\Z$, the relevant weight measure is the Lee weight. The reason for this is that the Gray map is an isometry $$ ((\Z/4\Z)^n, \text{Lee weight}) \to ((\F_2)^{2n}, \text{Hamming weight}) $$ so that the minimum Hamming weight of the binary image of a $\Z/4\Z$-code is the Lee weight of the code over $\Z/4\Z$. Our goal is to find the minimum Lee weight of (trace codes of) algebraic geometric codes over $\Z/4\Z$. Recall that the Lee weight is defined on $\Z/4\Z$ by $w_L(0) = 0$, $w_L(1) = w_L(3) = 1$, and $w_L(2) = 2$. The Lee weight of a vector in $(\Z/4\Z)^n$ is the sum of the Lee weights of the coordinates of the vector. Our first task is to find an ``algebraic'' expression for Lee weight, so that it will be easier to study. Notice that for each $x \in \Z/4\Z$, $w_L(x)$ is exactly half the square of the distance in the complex plane between $1 = i^0$ and $i^x$, where $i = \sqrt{-1}$. Using a little trigonometry, we see that $w_L(x) = 1- \cos(\frac{\pi}{2}x) = 1 - \real(e^{\pi i x/2})$. Therefore, for a vector $\x = (x_1, \dots, x_n)$ in $(\Z/4\Z)^n$, we have \begin{align*} w_L(\x) &= \sum_{j=1}^n (1 - \real(e^{\pi i x_j/2})) \\ &\geq n - \left|\sum_{j=1}^n e^{\pi i x_j/2}\right|. \end{align*} If the vector $\x$ is actually a codeword in a trace code of an algebraic geometric code, then we have $$ \x = (T(f(Z_1)), \dots, T(f(Z_n))) $$ where $Z_1, \dots, Z_n$ are disjoint $A$-points on some curve $\ringX$ over $A = W_2(\F_{2^m}) \simeq GR(4,m)$ and $f$ is a global section of a line bundle on $\ringX$. In this case, we have $$ w_L(\x) \geq n - \left|\sum_{j=1}^n e^{\pi i T(f(Z_j))/2}\right| $$ so we see that finding a lower bound on the minimum Lee weight of the trace code of an algebraic geometric code amounts to finding an upper bound on the modulus of an exponential sum of the form \begin{equation} \label{sum} \sum_{j=1}^n e^{\pi i T(f(Z_j))/2}. \end{equation} In the case of the projective line, sums similar to this have received much attention recently; see \cite{KHC} and \cite{L}. In both cases, the $A$-points on $\P^1$ over which the sum is taken are not arbitrary but instead are the Teichm\"uller points of $A$. An analogous concept exists for certain elliptic curves over rings, and it is here where we will focus our attention for the remainder of this paper. \section{Ordinary Elliptic Curves and Canonical Lifts} An elliptic curve over a field of characteristic 2 is called {\it ordinary} if its group of $2$-torsion points has order 2. (Otherwise, its group of $2$-torsion points is trivial, and the curve is called {\it supersingular}.) Every elliptic curve has an isogeny called the {\it Frobenius}; on points, the Frobenius takes $(x,y)$ to $(x^2,y^2)$. A special case of Serre-Tate theory (see \cite{LST} or \cite{K}) implies that every ordinary elliptic curve $E$ over a finite field $k$ of characteristic 2 has a {\it canonical lift} to an elliptic curve over the ring of infinite length Witt vectors $W(k)$. By reducing modulo $4$, we get that $E$ has a canonical lift to an elliptic curve $\ringE$ over $W_2(k)$. The existence of a canonical lift is in fact equivalent to the existence of an injective homomorphism $\tau:E(k) \to \ringE(W_2(k))$, called the {\it elliptic Teichm\"uller lift}. $W_2(k)$-points $Z$ on $\ringE$ which are of the form $Z = \tau(P)$ for some $k$-rational point $P$ on $E$ are the analogies of the Teichm\"uller points on $\P^1$. Our first question, then, is: How can we tell if an elliptic curve $\ringE$ over $W_2(k)$ is actually the canonical lift of an ordinary elliptic curve over $k$? The answer to this question is found in the next proposition, which is true for any characteristic $p>0$ and is proven in \cite{VW}. Before we can state it, however, we need one more definition. Let $\ringX$ be a scheme over $W_l(k)$, where $k$ is a field and $l \geq 0$. The {\it Greenberg transform} $G(\ringX)$ is the variety over $k$ formed by writing out the equations for $\ringX$ in terms of their Witt components. For example, if $\ringX$ is the elliptic curve over $W_2(\F_2)$ defined by the equation $\y^2 + \x\y = \x^3 + 1$, then $G(\ringX)$ is the variety over $\F_2$ defined by the equations $y_0^2 + x_0 y_0 = x_0^3 + 1$ and $x_0 y_0^3 + x_0^2 y_1 + x_1 y_0^2 = x_0^3 + x_0^4 x_1$. Notice that the $k$-rational points of $G(\ringX)$ are in one-to-one correspondence with the $W_l(k)$-points of $\ringX$. \begin{proposition}\label{calcaid} Let $k$ be a perfect field of characteristic $p > 0$ and $E/k$ an ordinary elliptic curve. If $\ringE$ is the canonical lift of $E$ to $W_2(k)$, then $\deg x_1 < 3p, \deg y_1 < 4p$. Conversely, let $\ringE$ be any elliptic curve defined over $W_2(k)$ with reduction $E$. Assume that the projection given by reduction from $G(\ringE)$ to $E$ admits a section $\t$ in the category of $k$-schemes over $E \setminus \{O\}$ (where $O$ is the origin for the group law on $E$) given by $(x_0,y_0) \mapsto (\x, \y)=((x_0,x_1),(y_0,y_1))$ where $x_1,y_1$ are regular away from $O$ and satisfy $\deg x_1 < 3p, \deg y_1 < 4p$. Then $\t$ is regular at $O$, $\ringE$ is the the canonical lift of $E$ and $\t$ is the elliptic Teichm\"uller lift. \end{proposition} \section{A simplification in the case of characteristic $2$} \label{redn} Let $k$ be a finite field of characteristic $2$ and let $E$ be the elliptic curve over $k$ defined by the Weierstrass equation $y^2 + x y = x^3 + a$, for some $a \in k$. $E$ is the reduction modulo $2$ of the curve $\ringE$ over $W_2(k)$ with equation $\y^2 + \x \y = \x^3 + (a, a^2)$, and it is easy to check that the map $\tau: E(k) \to \ringE(W_2(k))$ given by $(x_0,y_0) \mapsto ((x_0,a),(y_0,(x_0^2 + x_0) y_0 + x_0^3 + a x_0^2 + a))$ satisfies the hypotheses of Proposition \ref{calcaid}. Therefore, we know that $\ringE$ is the canonical lift of $E$ and $\tau$ is the elliptic Teichm\"uller lift on points. For an integer $r \geq 1$, we may consider the line bundle $\cl = \co_\ringE(r \ringO)$ on $\ringE$. Global sections of this line bundle must have their only pole at $\ringO$ and that pole must have order at most $r$. Since $\x$ has a pole of order $2$ at $\ringO$ and $\y$ has a pole of order $3$ at $\ringO$, this means that elements of $\Gamma(\ringE, \cl)$ are of the form $A + B \y$, where $A$ and $B$ are polynomials in $\x$ of degrees at most $\lfloor \frac{r}2 \rfloor$ and $\lfloor \frac{r-3}2 \rfloor$ respectively. Using the map $\tau$ above, we see that for $P \in E(k)$ and $f \in \Gamma(\ringE, \cl)$, we have $$ f(\tau(P)) = (f_0(P), f_1(P)) $$ as a Witt vector, where $f_0$ and $f_1$ are rational functions on $E$ which have poles only at $O$ and those poles are of orders at most $r$ and $2r + 1$ respectively. In other words, $f_0 \in \Gamma(E, \co_E(rO))$ and $f_1 \in \Gamma(E, \co_E((2r+1)O))$. Thus, for this particular curve $\ringE$ and a line bundle of the form $\cl = \co_\ringE(r\ringO)$, the sum \ref{sum} is the same as the sum \begin{equation} \label{sum2} \sum_{j=1}^n e^{\pi i T(f_0(P), f_1(P)) / 2} \end{equation} Notice that this sum no longer involves $\ringE$, but instead is expressed solely in terms of data on the curve $E$, which is defined over the field $k$. Further, we can actually say something much stronger. It is true that {\it every} ordinary elliptic curve over a field $k$ of characteristic 2 is is isomorphic over $\bar k$ to a curve with Weierstrass equation $y^2 + xy = x^3 + a$; see \cite{Silv}, Propositions A.1.1 and A.1.2. Since the degree of a line bundle is invariant under base change, this means that for every ordinary elliptic curve in characteristic 2, finding a bound on a sum of the form \ref{sum} is equivalent to finding a bound on a sum of the form \ref{sum2}. \section{The bound} We need one more result in order to bound the modulus of our sums \ref{sum} and \ref{sum2}. This result can be proven much more generally (see \cite{VW}), but we will state it in only the specific case we need here. First, we set up some notation. Let $E$ be an elliptic curve over the field $\F_{2^m}$, and let $K$ denote the field of rational functions on $E$. Let $f_0, f_1 \in K$, and assume $f_i \in \Gamma(E, \co_E(r_i O))$ where $O$ is the origin of $E$ and $r_i \geq 1$ is an integer for $i = 0, 1$. Set $\f = (f_0, f_1) \in W_2(K)$. Let $\cp = E(k) \setminus \{O\}$, and for $P \in \cp$, define $\f(P) = (f_0(P), f_1(P)) \in W_2(\F_{2^m})$. Let $F$ be the additive endomorphism defined in Section \ref{defs}, and let $T:W_2(\F_{2^m}) \to W_2(\F_2) \simeq \Z/4\Z$ be the trace map which was also defined in that section. \begin{theorem}\label{schmid} With notation as above, assume that $\f$ is not of the form $\f = F(\mathbf g) - \mathbf g + \mathbf c$ for any $\mathbf g \in W_2(K)$ and $\mathbf c \in W_2(\F_{2^m})$. Then $$ \left| \sum_{P \in \cp} e^{\pi i T(\f(P))/2} \right| \leq (1 + \max\{2 r_0, r_1\}) 2^{\frac{m}2}. $$ \end{theorem} A proof of a more general version of this theorem can be found in \cite{VW}, and most of the steps can actually be found in either \cite{S1} or \cite{S2}. The basic idea is to consider the degree of the Artin $L$-function of the Artin-Schreier-Witt cover of $\ringE$ defined by $F(\mathbf t) - \mathbf t = \f$. Notice that if $\f$ is of the excluded form, then $T(\f(P))$ would be a constant vector. By combining this result with the argument in Section \ref{redn} above, we get the following result. \begin{theorem}\label{char2sum} Let $\ringE$ be an elliptic curve over $W_2(\F_{2^m})$ which is the canonical lift of an elliptic curve $E$ over $\F_{2^m}$. Let $\cz = \{\tau(P) \, | \, P \in E(\F_{2^m}) \setminus \{O\}$, where $\tau:E(\F_{2^m}) \to \ringE(W_2(\F_{2^m}))$ is the elliptic Teichm\"uller lift. Let $f \in \Gamma(\ringE, \co_\ringE(r\ringO))$ for some integer $r \geq 1$. Then $$ \left| \sum_{Z \in \cz} e^{\pi i T(f(Z))/2} \right| \leq (2r+2) 2^\frac{m}2, $$ unless $f \circ \tau \in W_2(\F_{2^m})$ is of the form $F(\mathbf g) - \mathbf g + \mathbf c$ for some Witt vector $\mathbf g$ of rational functions on $E$ and some $\mathbf c \in W_2(\F_{2^m})$. \end{theorem} We can now translate this back into a statement about codes. \begin{theorem} \label{char2code} Let $\ringE$ and $\cz$ be as above, and let $\cl = \co_\ringE(r\ringO)$ for some integer $r \geq 1$. Set $C = C_{\Z/4\Z}(\ringE, \cz, \cl)$. Then the minimum Lee weight of the code $T(C)$ satisfies $$ w_L(T(C)) \geq n - (2r + 2)2^{\frac{m-3}2}, $$ where $n = \#\cz$ is the length of $C$. \end{theorem} \begin{proof} Let $f$ be a global section of $\cl$. If $f \circ \tau$ is not of the form excluded by Theorem \ref{char2sum}, then the Lee weight of the trace of the codeword corresponding to $f$ satisfies the desired inequality by that theorem. Otherwise, the trace of the codeword corresponding to $f$ is constant, so its Lee weight is either $0$, $n$, or $2n$. \end{proof} \section{An Example} Let $\ringE$ be the curve over $W_2(\bar\F_2)$ defined by the equation $\y^2 + \x \y = \x^3 - \x^2 - 2 \x - 1$, so that its reduction modulo $2$ is the curve $E$ over $\bar\F_2$ defined by the equation $y^2 + x y = x^3 + x^2 + 1$. (Although $E$ is isomorphic over $\bar\F_2$ to the curve with equation $y^2 + x y = x^3 + 1$, we work with $E$ rather than this latter curve because $E$ has more $\F_8$-rational points.) It is easy to check that if $(x_0, y_0)$ is a point on $E$, then $((x_0,1), (y_0,x_0^2(1+y_0)))$ is a point on $\ringE$. Further, the map $\tau:E(\bar\F_2) \to \ringE(W_2(\bar\F_2))$ given by $(x_0,y_0) \mapsto ((x_0,1),(y_0,x_0^2(1+y_0)))$ satisfies the hypotheses of Proposition \ref{calcaid} above, so we can conclude that $\ringE$ is the canonical lift of $E$. We will construct a code over $W_2(\F_8)$ using $\ringE$. Applying the trace map will give us a code over $\Z/4\Z$, and applying the Gray map will give us a binary code. Write $\F_8 = \F_2[t]/(t^3+t+1)$. In addition to the origin $O$, there are 13 finite $\F_8$-rational points on $E$. They are the elements of the set: \begin{align*} \cp = \{ &(0, 1), (t^2, 1 + t), (t^2, 1 + t + t^2), (t, 1 + t^2), (t, 1 + t + t^2), \\ &(t + t^2, 1 + t^2), (t + t^2, 1 + t), (1 + t^2, 0), (1 + t^2, 1 + t^2), \\ &(1 + t, 0), (1 + t, 1 + t), (1 + t + t^2, 0), (1 + t + t^2, 1 + t + t^2) \} \end{align*} Applying the map $\tau$ described above, one gets the origin $\ringO$ of $\ringE$ and the following thirteen points of $\ringE$ defined over $W_2(\F_8)$: \begin{align*} \cz = \{&((0, 1), (1, 0)), ((t^2, 1), (1 + t, 1 + t + t^2)), ((t^2, 1), (1 + t + t^2, t)), \\ &((t, 1), (1 + t^2, t + t^2)), ((t, 1), (1 + t + t^2, 1 + t^2)),\\ &((t + t^2, 1), (1 + t^2, 1 + t)), ((t + t^2, 1), (1 + t, t^2)), \\ &((1 + t^2, 1), (0, 1 + t + t^2)), ((1 + t^2, 1), (1 + t^2, 1)), \\ &((1 + t, 1), (0, 1 + t^2)), ((1 + t, 1), (1 + t, 1)), \\ &((1 + t + t^2, 1), (0, 1 + t)), ((1 + t + t^2, 1), (1 + t + t^2, 1))\} \end{align*} We wish to consider the code $C = C_{W_2(\F_8)}(\ringE, \cz, \cl)$, where $\cl = \co_{\ringE}(3 \ringO)$. The degree of $\cl$ is $3$, so by the Riemann-Roch theorem \cite{W1}, the rank of the $W_2(\F_8)$-module $\Gamma(\ringE, \cl)$ is 3. It is easy to check that $\{1, \x, \y\}$ is a basis for this module, so a $(3 \times 13)$ generator matrix for $C$ is constructed simply by evaluating these three functions at each of the thirteen points in $\cz$. In fact, we are interested in the trace code $T(C)$ of $C$, which will be a code over $W_2(\F_2) = \Z/4\Z$. By a ring-version of Theorem VIII.1.6 of \cite{St}, we know that the rank of $T(C)$ (as a $\Z/4\Z$-module) is at most 7; we will show that it is exactly 7. Since $\{1, t, t^2\}$ is a basis for $W_2(\F_8)$ as a $W_2(\F_2)$-module, we know that $$ \{1, t, t^2, \x, t \x, t^2 \x, \y, t \y, t^2 \y\} $$ is a basis for $\Gamma(\ringE, \cl)$ as a $W_2(\F_2)$-module. Some subset of this basis, when evaluated at the points in $\cz$, will give us a set of codewords whose traces form a basis for the trace code $T(C)$. Since $T(1)$, $T(t)$, and $T(t^2)$ are all proportional, we can throw away $t$ and $t^2$, and look at the $7 \times 13$ matrix whose rows are $(T(f(Z_1)), \dots, T(f(Z_{13})))$, where $Z_1, \dots, Z_{13}$ are the points in $\cz$ and $f$ runs over the set $\{1, \x, t \x, t^2 \x, \y, t \y, t^2 \y\}$. If this matrix has full rank (7), then it is the generator matrix for $T(C)$. The matrix described above works out to be (after replacing elements of $W_2(\F_2)$ with their usual representatives in the ring $\Z/4\Z$, as given in \ref{iso}): \[ \left( \begin{array}{ccccccccccccc} 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 3 & 3 & 3 & 3 & 3 \\ 0 & 1 & 1 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 & 1 & 1 \\ 0 & 2 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 1 & 1 & 3 & 3 \\ 3 & 3 & 1 & 1 & 3 & 3 & 1 & 2 & 3 & 2 & 3 & 2 & 3 \\ 2 & 0 & 3 & 1 & 1 & 1 & 2 & 2 & 3 & 0 & 2 & 2 & 1 \\ 2 & 1 & 1 & 2 & 1 & 0 & 3 & 0 & 2 & 2 & 1 & 2 & 3 \end{array} \right) \] Since the submatrix consisting of the last 7 columns of this matrix has determinant 3 $\pmod 4$, this is indeed a generator matrix for the trace code. By Theorem \ref{char2code}, the minimum Lee weight of the code with the above generator matrix is at least 5. One can check that in fact it is exactly 5. By appending a check digit which is the sum of the first three coordinates, we get a code over $\Z/4\Z$ of length 14, rank 7, and minimum Lee weight 6. The generator matrix is: \[ \left( \begin{array}{cccccccccccccc} 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 1\\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 3 & 3 & 3 & 3 & 3 & 2\\ 0 & 1 & 1 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 & 1 & 1 & 2\\ 0 & 2 & 2 & 1 & 1 & 1 & 1 & 2 & 2 & 1 & 1 & 3 & 3 & 0\\ 3 & 3 & 1 & 1 & 3 & 3 & 1 & 2 & 3 & 2 & 3 & 2 & 3 & 3\\ 2 & 0 & 3 & 1 & 1 & 1 & 2 & 2 & 3 & 0 & 2 & 2 & 1 & 1\\ 2 & 1 & 1 & 2 & 1 & 0 & 3 & 0 & 2 & 2 & 1 & 2 & 3 & 0 \end{array} \right) \] Applying the Gray map gives a binary code of length 28 with $2^{14} = 16384$ codewords and minimum Hamming distance 6. The best code with this length and number of codewords has minimum Hamming distance 7. It is interesting to note that the first four rows and the odd-numbered columns of the generator matrix above define the $[7,4]$ Hamming code over $\Z/4\Z$ (see \cite{HKCSS}). Since only the functions $1$ and $\x$ are used here, this gives a construction of this code as a trace code of an algebraic geometric code over $\P^1$. For a more direct construction of the $[7,4]$ Hamming code over $\Z/4\Z$ as an algebraic geometric code, see \cite{W2}. %\bibliographystyle{amsplain} %\bibliography{refs2} %\end{document} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \begin{thebibliography}{10} \bibitem{CM} A.~R. Calderbank and G.~M. McGuire, \emph{Construction of a $(64, 2^{37}, 12)$ code via {G}alois rings}, Designs, Codes, and Cryptography \textbf{10} (1997), 157--165. \bibitem{HKCSS} A.~R.~Hammons Jr., P.~V. Kumar, A.~R. Calderbank, N.~J.~A. Sloane, and P.~Sol\'e, \emph{The {$\Z_4$}-linearity of {K}erdock, {P}reparata, {G}oethals, and related codes}, IEEE Transactions on Information Theory \textbf{40} (1994), 301--319. \bibitem{K} N.~M. Katz, \emph{Serre-tate local moduli}, Algebraic surfaces (Orsay, 1976-78), Lecture Notes in Math., vol. 868, Springer, Berlin-New York, 1981, pp.~138--202. \bibitem{KHC} P.~V. Kumar, T.~Helleseth, and A.~R. Calderbank, \emph{An upper bound for some exponential sums over {G}alois rings and applications}, IEEE Transactions on Information Theory \textbf{41} (1995), 456--468. \bibitem{Lang} S.~Lang, \emph{Algebra}, Addison-Wesley, Reading, MA, 1974. \bibitem{L} W-C.~W. Li, \emph{Character sums over $p$-adic fields}, preprint, 1997. \bibitem{LST} J.~Lubin, J-P. Serre, and J.~Tate, \emph{Elliptic curves and formal groups}, Proc.~of the Woods Hole summer institute in algebraic geometry, 1964. \bibitem{S1} H.~L. Schmid, \emph{Zur arithmetik der zyklischen $p$-{K\"o}rper}, Crelles J. \textbf{176} (1936), 161--167. \bibitem{S2} \bysame, \emph{Kongruenzzetafunktionen in zyklischen {K\"o}rpern}, Abh.~Preuss. Akad.~Wiss.~Math.-Nat.~Kl. \textbf{1941} (1942), 30pp. \bibitem{Silv} J.~Silverman, \emph{The arithmetic of elliptic curves}, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. \bibitem{sole} P.~Sol\'e, \emph{A quaternary cyclic code and a family of quadriphase sequences with low correlation}, Coding Theory and Applications (Toulon, 1988) (New York), Lecture Notes in Computer Science, vol. 388, Springer, 1989, pp.~193--201. \bibitem{St} H.~Stichtenoth, \emph{Algebraic function fields and codes}, Springer, Berlin, 1993. \bibitem{TV} M.~A. Tsfasman and S.~G.~Vl\v adu\c t, \emph{Algebraic-geometric codes}, Kluwer, Dordrecht, 1991. \bibitem{VW} J.-F. Voloch and J.~L. Walker, \emph{Euclidean weights of codes from elliptic curves over rings}, submitted for publication. \bibitem{W1} J.~L. Walker, \emph{Algebraic geometric codes over rings}, submitted for publication. \bibitem{thesis} \bysame, \emph{Algebraic geometric codes over rings}, Ph.D. thesis, University of Illinois, 1996. \bibitem{W2} \bysame, \emph{The {N}ordstrom {R}obinson code is algebraic geometric}, IEEE Transactions on Information Theory \textbf{43} (1997), 1588--1593. \end{thebibliography} \end{document}