\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} \def\ck{{\mathcal K}} \def\cf{{\mathcal F}} \def\cl{{\mathcal L}} \def\co{{\mathcal O}} \def\cp{{\mathcal P}} \def\cz{{\mathcal Z}} \def\ce{{\mathcal E}} \def\spec{\operatorname{Spec}} \def\rk{\operatorname{rank}} \def\im{\operatorname{im}} \def\ev{\operatorname{ev}} \def\re{\operatorname{Re}} \def\u{{\mathbf u}} \def\y{{\mathbf y}} \def\x{{\mathbf x}} \def\z{{\mathbf z}} \def\u{{\mathbf u}} \def\a{{\mathbf a}} \def\b{{\mathbf b}} \def\c{{\mathbf c}} \def\f{{\mathbf f}} \def\g{{\mathbf g}} \def\h{{\mathbf h}} \def\X{{\mathbf X}} \def\H{{\mathbf H}} \def\U{{\mathbf U}} \def\E{{\mathbf E}} \def\G{{\mathbf G}} \def\D{{\mathbf D}} \def\wt{\operatorname{wt}} \def\m{{\mathfrak m}} \def\kstar{{\mathcal K}^*} \def\rank{\operatorname{rank}} \def\supp{\operatorname{supp}} \def\F{{\mathbb F}} \def\Z{{\mathbb Z}} \def\P{{\mathbb P}} \def\A{{\mathbb A}} \def\zerovec{{\mathbf 0}} \def\call{{L}} \def\subxclosed{{\begin{array}{c}{x \in X} \\ {x \text{ closed }}\end{array}}} \begin{document} \title{Codes over rings from curves of higher genus} %!PN \author{Jos\'e Felipe Voloch} \address{Department of Mathematics, University of Texas, Austin, TX 78712} \email{voloch@math.utexas.edu} \thanks{The first author was supported in part by NSA Grant \#MDA904-97-1-0037 and TARP grant \#ARP-006.} % author two information \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.} \begin{abstract} We construct certain error-correcting codes over finite rings and estimate their parameters. These codes are constructed using plane curves and the estimates for their parameters rely on constructing ``lifts'' of these curves and then estimating the size of certain exponential sums. \end{abstract} \maketitle %\begin{keywords} %codes, algebraic geomety, plane curves, codes over rings. %\end{keywords} \section{Introduction} The purpose of this paper is to construct certain error-correcting codes over finite rings and estimate their parameters. For this purpose, we need to develop some tools; notably an estimate for the dimension of trace codes over rings (generalizing work of van der Vlugt over fields) and some results on lifts of affine curves from fields of characteristic $p$ to Witt vectors of length two. This work partly generalizes our previous work on elliptic curves, although there are some differences which we will point out below. A code is a subset of $A^n$, where $A$ is a finite set (called the alphabet). Usually $A$ is just the field of two elements and, in this case, one speaks of binary codes. For various reasons one often restricts attention to linear codes, which are linear subspaces of $A^n$ when $A$ is a field. However, there are non-linear binary codes (such as the Nordstrom-Robinson, Kerdock, and Preparata codes) that outperform linear codes for certain parameters. These codes have remained somewhat mysterious until recently when Hammons, et al.~(\cite{HKCSS}) discovered that one can obtain these codes from linear codes over rings (i.e. submodules of $A^n$, $A$ a ring) via the Gray mapping, which we recall below. In a different vein, over the last decade there has been a lot of interest in linear codes coming from algebraic curves over finite fields. The construction of such codes was first proposed by Goppa in \cite{G}; see \cite{St} or \cite{TV} for instance. In \cite{TVZ}, it is proven that for $q \ge 49$ a square, there exist sequences of codes over the finite field with $q$ elements which give asymptotically the best known linear codes over these fields. The second author has extended Goppa's construction to curves over finite rings and shown, for instance, that the Nordstrom-Robinson code can be obtained from her construction followed by the Gray mapping; see \cite{Wa1} and \cite{Wa2}. While most of the parameters for these new codes were estimated in the above papers, the crucial parameter needed to describe the error-correcting capability of the images of these codes under the Gray mapping was still lacking. In our previous work (\cite{VW1}, \cite{VW2}) we used elliptic curves which were canonical lifts of their reductions and we were able to estimate the minimum distance in that case. Curves of higher genus unfortunately do not have canonical lifts so we need to proceed differently. We find that on an open set there are lifts which are sufficiently good so we use those. For these codes, the missing parameter can be estimated and we do so. We also obtain finer estimates on the dimension of the trace codes. The work of Mochizuki \cite{Moch}, indicates that there might be a general framework for working with lifts for curves of higher genus, with the proviso that the lift of points is only on {\it certain} open subsets of the curve. Mochizuki defines an analogue of ordinary curves and of canonical liftings for such. It remains to be seen if the corresponding lift of points is of small degree, which is essential for applications. \section{Codes over Witt rings} In this section we recall the definition of the ring of Witt vectors over a finite field and prove some general results about such rings and codes over them. The two theorems in this section are both generalizations of results which are known in the finite field case. We believe that Theorem~\ref{Hilb90} is known, but we include it for lack of a good reference. In contrast, Theorem~\ref{wittdelsarte} is new, having only appeared previously in the second author's thesis (\cite{thesis}). Recall the definitions of the Frobenius and trace maps for finite fields: Let $p$ be prime and consider the field extension $\F_{p^m}/\F_p$. Then the Frobenius automorphism $\sigma:\F_{p^m} \to \F_{p^m}$ is the element of $\operatorname{Gal}(\F_{p^m}/\F_p)$ given by $\sigma(x) = x^p$, and the trace map $tr:\F_{p^m} \to \F_p$ is given by $tr(x) = x + \sigma(x) + \sigma^2(x) + \dots + \sigma^{m-1}(x) = x + x^p + x^{p^2} + \dots + x^{p^{m-1}}$. We will be working mostly with rings of Witt vectors or Witt rings, for short. See, e.g., \cite{Serre} for an introduction to Witt rings. Let us just point that the Witt ring $W_l(\F_{p^m})$ is, as a set, $\F_{p^m}^l$, and the operations are defined by \begin{align*} (x_0, x_1, \ldots, x_{l-1}) + (y_0, y_1, \ldots, y_{l-1}) &= (S_0, S_1, \ldots, S_{l-1}),\\ (x_0, x_1, \ldots, x_{l-1}) (y_0, y_1, \ldots, y_{l-1}) &= (P_0, P_1, \ldots, P_{l-1}), \end{align*} where the $S_i$'s and $P_i$'s are certain polynomials with integer coefficients in $x_0$, $x_1, \ldots, x_{l-1}$, $y_0$, $y_1, \ldots, y_{l-1}$. In particular, we have \begin{align*} (x_0, x_1) + (y_0, y_1) &= (x_0 + y_0, x_1 + y_1 + \frac{1}{p}((x_0 + y_0)^p - x_0^p - y_0^p))\\ (x_0, x_1) (y_0, y_1) &= (x_0 y_0, x_0^p y_1 + y_0^p x_1) \end{align*} The ring $W_l(\F_{p^m})$ is a local ring with maximal ideal generated by $p$, satisfying $p^l=0$ and having residue field $\F_{p^m}$. It is easy to check that the Galois Ring $GR(p^l,m)$ of degree $m$ over $\Z/p^l\Z$ is isomorphic to the ring $W_l(\F_{p^m})$ of length $l$ Witt vectors over the field with $p^m$ elements. In particular, $W_l(\F_p) \cong \Z/p^l\Z$. One can now define the Frobenius and trace maps for a Witt ring $W_l(\F_{p^m})$. Let $\x = (x_0, x_1, \dots, x_{l-1}) \in W_l(\F_{p^m})$. The Frobenius $F:W_l(\F_{p^m}) \to W_l(\F_{p^m})$ is given by $F(\x) = F((x_0, x_1, \dots, x_{l-1})) = (x_0^p, x_1^p, \dots, x_{l-1}^p)$. The trace map $T : W_l(\F_{p^m}) \to W_l(\F_p) \cong \Z/p^l\Z$ is given by $T(\x) = \x + F(\x) + \dots + F^{m-1}(\x)$. It is a standard fact that for any $\x = (x_0, x_1, \dots, x_{l-1}) \in W_l(\F_{p^m})$, we have $p\x = (0, x_0^p, x_1^p, \dots, x_{l-2}^p)$ and $\x \cdot (y_0, 0, \dots, 0) = (x_0 y_0, x_1 y_0^p, \dots, x_{l-1}y_0^{p^{l-1}})$ for every $y_0 \in \F_{p^m}$. We would like to prove a version of Delsarte's Theorem for Witt rings. The usual statement of this theorem goes as follows: Let $C$ be a linear code over $\F_{q^m}$. Denote by $tr(C)$ the linear code over $\F_q$ obtained by applying the trace map $tr: \F_{q^m} \to \F_q$ coordinatewise to the codewords of $C$. Denote by $C|_{\F_q}$ the subcode of $C$ consisting of all codewords whose coordinates all lie in $\F_q$. Then $$ (C|_{\F_q})^\perp = tr(C^\perp). $$ In order prove our version of this theorem, we must check that several of the standard properties of $\sigma$ and $tr$ still hold for $F$ and $T$. This checking is done in the following technical lemma. \begin{lemma}\label{tracefrobprops} Let $\pi:W_l(\F_{p^m}) \to \F_{p^m}$ be the natural projection, and let $\sigma$, $tr$, $F$, and $T$ be as above. Then \begin{enumerate} \item\label{commute}$\pi \circ F = \sigma \circ \pi$ and $\pi \circ T = tr \circ \pi$. \item\label{onto} The map $T:W_l(\F_{p^m}) \to W_l(\F_p) = \Z/p^l\Z$ is onto. \item\label{nonzero teich} There is some $x_0 \in F_{p^m}$ with $T((x_0, 0, \dots, 0)) \not\equiv 0 \pmod p$. \item\label{nonzero mult} Let $\x$ be a nonzero element of $W_l(\F_{p^m})$. Then there is some $\y \in W_l(\F_{p^m})$ with $T(\x\y) \neq 0$. \end{enumerate} \end{lemma} \begin{proof} Part~(\ref{commute}) is straight forward calculation. Consider an arbitrary element $\x = (x_0, x_1, \dots, x_{l-1}) \in W_l(\F_{p^m})$. We have $\pi \circ F (\x) = \pi ((x_0^p, x_1^p, \dots, x_{l-1}^p)) = x_0^p = \sigma\circ\pi(\x)$ and $\pi \circ T(\x) = \pi(\x + F(\x) + \dots + F^{m-1}(\x)) = x_0 + x_0^p + \dots + x_0^{p^{m-1}} = tr(x_0) = tr\circ\pi (\x)$. For (\ref{onto}), first note that it is well known that $tr:\F_{p^m} \to \F_p$ is onto (see, for example, \cite{St}). Since $\pi$ is onto, we see that $\pi \circ T = tr \circ \pi$ is onto. If $T$ is not onto, then its image is contained in a $\Z/p^l\Z$-submodule of $\Z/p^l\Z$, i.e., an ideal. Since $\Z/p^l\Z$ is local with maximal ideal $(p)$, we have $T(W_l(\F_{p^m})) \subset p \Z/p^l\Z$, which implies $\pi \circ T = 0$, contradicting (\ref{commute}). Now suppose that (\ref{nonzero teich}) fails, and let $\x$ be any element of $W_l(\F_{p^m})$. We can write $\x = (x_0, 0, \dots, 0) + p \y$ for some $\y \in W_l(\F_{p^m})$. Then $T(\x) = T((x_0, 0, \dots, 0)) + p T(y) \in p \Z/p^l\Z$. Since $\x$ was arbitrary, this contradicts (\ref{onto}) above. Finally, to see why (\ref{nonzero mult}) is true, write $\x = (x_0, x_1, \dots, x_{l-1})$ and let $i$ be minimal with $x_i \neq 0$. Then $\x = p^i ((\sigma^{-i}(x_i), 0, \dots, 0) + p \x')$ for some $\x' \in W_l(\F_{p^m})$. By (\ref{nonzero teich}), there is some $y_0 \in F_{p^m}$ such that $\pi(T((\sigma^{-i}(x_i) y_0, 0, \dots, 0))) \neq 0$. But then \begin{align*} T(\x \cdot (y_0, 0, \dots, 0)) &= T(p^i((\sigma^{-i}(x_i) y_i, 0, \dots, 0) + p \x' \cdot (y_0, \dots, 0))) \\ &= p^i T(\sigma^{-i}(x_i)y_0, 0, \dots, 0) + p^{i+1} T(\x' \cdot (y_0, 0, \dots, 0)). \end{align*} Since this is nonzero modulo $p^{i+1}$, it is nonzero. \end{proof} We are now equipped to prove a version of Delsarte's theorem for codes over Witt rings. \begin{theorem}\label{wittdelsarte} Let $C$ be any linear code over $W_l(\F_{p^m})$ and let $C^\perp$ be the dual code of $C$. Write $C|_{\Z/p^l\Z}$ for the subcode $C \cap (\Z/p^l\Z)^n$ of $C$. Then $$ (C|_{\Z/p^l\Z})^\perp = T(C^\perp). $$ \end{theorem} \begin{proof} (following \cite{St}) First we show $T(C^\perp) \subset (C|_{\Z/p^l\Z})^\perp $. For this, it is enough to show that $\c \cdot T(\a) = 0$ for every $\c = (c_1, \dots, c_n) \in C|_{\Z/p^l\Z}$ and $\a = (a_1, \dots, a_n) \in C^\perp$. But $$ \c \cdot T(\a) = \sum_{i=1}^n c_i T(a_i) = T(\sum c_i a_i) = T(\c \cdot \a) = T(0) = 0. $$ To see that $(C|_{\Z/p^l\Z})^\perp \subset T(C^\perp)$, it is enough to show that $(T(C^\perp))^\perp \subset C|_{\Z/p^l\Z}$. Suppose not. Then for some $\u \in (T(C^\perp))^\perp$, $\u \not\in C$. Hence there is some ${\mathbf v} \in C^\perp$ with $\u \cdot \mathbf v \neq 0$. By Lemma~\ref{tracefrobprops}(\ref{nonzero mult}), there is some $\x \in W_l(\F_{p^m})$ with $T(\x \u \cdot \mathbf v) \neq 0$. So we have $$ 0 \neq T(\x \u \cdot \mathbf v) = T(\u \cdot \x \mathbf v) = \u \cdot T(\x \mathbf v). $$ However, $\x \mathbf v \in C^\perp$ and so $T(\x \mathbf v) \in T(C^\perp)$, which means that $\u \cdot T(\x \mathbf v) = 0$, a contradiction. \end{proof} Finally, we would like to point out that the proof of the additive form of Hilbert's Theorem 90 as given in \cite{L} goes through for Witt vectors. It is given here for reference. \begin{theorem}\label{Hilb90} (Hilbert's Theorem 90 for Witt vectors) Let $F:W_l(\F_{p^m}) \to W_l(\F_{p^m})$ be the map $(a_0, \dots, a_{l-1}) \mapsto (a_0^p, \dots, a_{l-1}^p)$ and let $T:W_l(\F_{p^m}) \to W_l(\F_p)$ be the trace mapping, so that $T(\a) = \a + F(\a) + \dots + F^{m-1}(\a)$. Then for any $\a \in W_l(\F_{p^m})$, we have $T(\a) = 0$ if and only if $\a = \b - F(\b)$ for some $\b \in W_l(\F_{p^m})$. \end{theorem} \begin{proof} Clearly $T(\b - F(\b)) = 0$, so assume $\a \in W_l(\F_{p^m})$ is arbitary with $T(\a) = 0$. Since the map $T$ is onto by Lemma~\ref{tracefrobprops}(\ref{onto}) above, there is some $\c \in W_l(\F_{p^m})$ with $T(\c) = 1_{W_l(\F_p)}$. Setting $$ \b = \sum_{r=0}^{m-2}\sum_{i=0}^r F^i(\a) F^r(\c), $$ it is straightforward to check that $\a = \b - F(\b)$. \end{proof} \section{Algebraic geometric codes over rings } In \cite{Wa1}, the idea of algebraic geometric codes over rings other than fields is introduced, and foundational results about these codes are proven. In \cite{Wa2}, the methods of \cite{Wa1} are used to explicitly construct the $\Z/4\Z$-version of the Nordstrom-Robinson code as an algebraic geometric code. In order to construct other codes over $\Z/4\Z$ with good nonlinear binary shadows, we must first investigate the Lee and Euclidean weights of these codes. In this section, we recall the definitions and some results from \cite{Wa1} and explain how the Lee and Euclidean weights of algebraic geometric codes over rings are related to exponential sums. Let $A$ be a local Artinian ring with maximal ideal $\m$. We assume that the field $A/\m$ is finite; say $A/\m = \F_q$. For example, we could take $A = W_l(\F_{p^m})$, and then $\m = (p)$ and $A/\m = \F_{p^m}$. Let $\X$ be a curve over $A$, that is, a connected irreducible scheme over $\spec A$ which is smooth of relative dimension one. Let $\X \times_{\spec A} \spec \F_q = X \subset \X$ be the fiber of $\X$ over the closed point of $\spec A$. We assume $X$ is absolutely irreducible, so that it is the type of curve on which algebraic geometric codes over $\F_q$ are defined. Let $\cz = \{Z_1, \dots, Z_n\}$ be a set of $A$-points on $\X$ with distinct specializations $P_1, \dots, P_n$ in $X$. Recall that in the case of a curve $C$ over a field $k$, given a (Weil) divisor $D$ on a curve $C$, there is a corresponding line bundle $\co_C(D)$, and we have the $k$-vector space of global sections of $\co_C(D)$. $$ L(D) = \Gamma(C,\co_C(D)) = \{f \in k(C) \, | \, \operatorname{div}(f) + D \geq 0\} \cup \{0\}. $$ A similar thing holds in the case of the curve $\X$ over $A$ and a Cartier divisor. Thus, for a Cartier divisor $\D$ on $\X$, we define $$ L(\D) = \Gamma(\X,\co_\X(\D)) $$ to be the $A$-module of global sections of $\co_\X(\D)$ on $\X$. In particular, let $\G$ be a (Cartier) divisor on $\X$ such that no $P_i$ is in the support of $\G$, and let $\cl = \co_\X(\G)$ be the corresponding line bundle. For each $i$, $\Gamma(Z_i, \cl|_{Z_i}) \simeq A$, and thinking of elements of $L(\G)$ as rational functions on $\X$, we may think of the composition $L(\G) \to \Gamma(Z_i, \cl|_{Z_i}) \to A$ as evaluation of these functions at $Z_i$. Summing over all $i$, we have a map $\gamma: L(\G) \to \bigoplus \Gamma(Z_i, \cl|_{Z_i}) \to A^n$, given by $f \mapsto (f(Z_1), \dots, f(Z_n))$. \begin{definition} Let $A$, $\X$, $\cz$, $\cl$, and $\gamma$ be as above. Define $C_A(\X,\cz,\cl)$ to be the image of $\gamma$. $C_A(\X, \cz, \cl)$ is called the algebraic geometric code over $A$ associated to $\X$, $\cz$, and $\cl$. \end{definition} The following theorem summarizes some of the main results of \cite{Wa1}. \begin{theorem} Let $\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(\X, \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$. \end{theorem} \remark The minimum Hamming distance is obtained by comparing zeros and poles and the dimension computation is a consequence of the Riemann-Roch Theorem. These estimates require the assumption $2g-2 < \deg \cl < n$. The duality result follows from a generalized version of the Residue Theorem which holds for Gorenstein rings. See \cite{Wa1} for details. For applications, one is usually concerned with constructing codes over $\Z/4\Z$, or more generally, over rings of the form $\Z/p^l\Z$, where $p$ is prime and $l \ge 1$. We can use algebraic geometry to construct such codes in two different ways. First, we can simply set $A = \Z/p^l\Z$ in the definition of algebraic geometric codes above. Alternatively, we can construct an algebraic geometric code over $W_l(\F_{p^m})$ and look at the associated trace code over $W_l(F_p) = \Z/p^l\Z$. The Gray map allows us to construct (non-linear) binary codes from codes over $\Z/4\Z$ and is defined as follows. Consider the map $\phi: \Z/4\Z \to \F_2^2$ defined by $\phi(0)=(0,0), \phi(1) = (0,1), \phi(2)=(1,1),\phi(3)=(1,0)$. Now we define a map, again denoted by $\phi: (\Z/4\Z)^n \to \F_2^{2n}$, by applying the previous $\phi$ to each coordinate. For linear codes over rings of the form $\Z/p^l\Z$, it is often either the Euclidean or Lee weight rather than the Hamming weight which is of interest. In particular, when $p^l = 4$, the Euclidean and Lee weights are closely related, and the Lee weight gives the Hamming weight of the associated nonlinear binary code. We begin by defining Euclidean weights. We identify an element $x$ of the cyclic group $\Z/p^l\Z$ with the corresponding $p^l$th root of unity via the map $$ x \to e_{p^l}(x) := e^{2 \pi i x / {p^l}}. $$ \begin{definition} The Euclidean distance between $x$ and $y$ is the distance $d_E(x,y)$ in the complex plane between the points $e_{p^l}(x)$ and $e_{p^l}(y)$, and the Euclidean weight of $x$ is the distance $w_E(x)$ between $e_{p^l}(x)$ and $e_{p^l}(0) = 1$. \end{definition} We have \begin{align*} w_E(x) &= \sqrt{\sin^2 \left(\frac{2 \pi x}{p^l}\right) + (1 - \cos \left(\frac{2 \pi x}{p^l}\right))^2} \\ &= \sqrt{2 - 2 \cos \left(\frac{2 \pi x}{p^l}\right)}. \end{align*} In fact, it is usually the square of the Euclidean weight in which one is interested. This is given by $w_E^2 (x) = 2 - 2 \cos (\frac{2 \pi x}{p^l})$. For vectors $\x = (x_1, \dots, x_n)$ and $\y = (y_1, \dots, y_n)$ over $\Z/p^l\Z$, we define \begin{align*} d_E^2(\x,\y) &= \sum_{j = 1}^n d_E^2(x_j,y_j)\\ \intertext{and} w_E^2(\x) &= \sum_{j = 1}^n w_E^2(x_j) \end{align*} For example, the squared Euclidean weight of the all-one vector in $(\Z/p^l\Z)^n$ is $2n(1 - \cos({2 \pi/p^l}))$. Using the Taylor expansion of cosine, we get that this is at least $4n \frac{\pi^2}{p^{2l}}(1 + \frac{\pi^2}{3 p^{2l}})$. Further, any other nonzero constant vector in $(\Z/p^l\Z)^n$ has squared Euclidean weight at least this. For general vectors, since $\cos (\frac{2 \pi x}{p^l})= \re\left(e_{p^l}(x)\right)$, we have \begin{align*} w_E^2(\x) &= \sum_{j = 1}^n\left(2 - 2\re\left(e_{p^l}(x_j)\right)\right)\\ & = 2n - 2 \re \sum_{j = 1}^n e_{p^l}(x_j) \\ & \geq 2n - 2 \left|\sum_{j = 1}^n e_{p^l}(x_j)\right|. \end{align*} Hence, to find a lower bound on the minimum Euclidean weight of a linear code over $\Z/p^l\Z$, it is enough to find an upper bound on the modulus of the exponential sum $$ \sum_{j = 1}^n e_{p^l}(x_j). $$ Now consider the case ${p^l} = 4$. Then $e_4(0) = 1$, $e_4(1) = i$, $e_4(2) = -1$, and $e_4(3) = -i$. Hence $w_E^2(0) = 0$, $w_E^2(1) = w_E^2(3) = 2$, and $w_E^2(2) = 4$. Since the Lee weight is defined by $w_L(0) = 0$, $w_L(1) = w_L(3) = 1$, and $w_L(2) = 2$, we have $$ w_L(x) = \frac12 w_E^2(x) $$ for any $x \in \Z/4\Z$. From this we see that the Euclidean weight of a codeword over $\Z/4\Z$ is twice the Hamming weight of the binary codeword obtained by applying the Gray map. Notice that the Lee weight of a constant vector in $(\Z/4\Z)^n$ is either $0$, $n$, or $2n$. Finally, let $C$ be an algebraic geometric code over $W_l(\F_{p^m})$, and let $T: W_l(\F_{p^m}) \to \Z/p^l\Z$ denote the trace map as before. We are interested in the minimum Euclidean weight of $T(C)$, the trace code of $C$, which is a linear code over $\Z/p^l\Z$. Codewords in $T(C)$ are of the form $(T(f(Z_1)), \dots, T(f(Z_n)))$, where $f$ is a rational function on some curve $\X$ defined over $W_l(\F_{p^m})$ and $Z_1, \dots, Z_n$ are $W_l(\F_{p^m})$-points on $\X$. From the argument above, to find a lower bound for the minimum Euclidean weight of $T(C)$ it suffices to find an upper bound on the modulus of $$ \sum_{j=1}^n e_{p^l}(T(f(Z_j))) = \sum_{j=1}^n e^{2 \pi i T(f(Z_j))/p^l}. $$ To estimate these kinds of sums, Theorem~\ref{expsum} below, which we proved in \cite{VW1}, is very useful. Let $X$ be a curve over the finite field $\F_q$, where $q = p^m$ with $p$ prime. Denote by $K = \F_q(X)$ the function field of $X$. Let $f_0,\ldots,f_{l-1} \in K$ and consider the Witt vector $\f = (f_0,\ldots,f_{l-1}) \in W_l(K)$. Let $X_0$ be the maximal affine open subvariety of $X$ where $f_0,\ldots,f_{l-1}$ do not have poles and let $P \in X_0(\F_q)$. We can then consider the Witt vector $\f(P) = (f_0(P),\ldots,f_{l-1}(P)) \in W_l(\F_q)$. Letting $T:W_l(\F_q) \to W_l(\F_p) \cong \Z/p^l\Z$ denote the trace map, we can consider the exponential sum $$ S_{\f,\F_q} = \sum_{P \in X_0(\F_q)} e^{2\pi i T(\f(P))/p^l}. $$ \begin{theorem}\label{expsum} With notation as above, assume $X \setminus X_0$ consists of the points above the valuations $v_1,\ldots,v_s$ of $K$. Let $g$ be the genus of $X$, $n_{ij} = -v_j(f_i)$, $i = 0, \ldots, l-1$, $j = 1, \ldots, s$, and assume that $\f$ is not of the form $\f = F(\g) - \g + \c$ for any $\g \in W_l(K)$ and $\c \in W_l(\F_q)$, where $F$ denotes the additive endomorphism on $W_l(K)$ given by $F(g_0, g_1, \dots, g_{l-1}) = (g_0^p, g_1^p, \dots, g_{l-1}^p)$. Then $|S_{\f,\F_q}| \le Bq^{1/2}$, where $$B \le 2g-1 + \sum_{j=1}^s \max \{ p^{l-1-i}n_{ij} \mid 0 \le i \le l-1 \}\deg v_j.$$ \end{theorem} \section{Liftings} In what follows, we consider an affine curve $\U$ over $W_2(k)$ defined by a polynomial equation $\H(\x,\y) = 0$. Assume that $\H(\x,\y)$ has the form $\sum_{di+ej\leq de} a_{ij}\x^i \y^j$ where $d$ and $e$ are relatively prime integers, $a_{e0} \not\equiv 0 \pmod p$, and $a_{0d} \not\equiv 0 \pmod p$. Assume further that the affine curve $U$ defined over $k$ by $H(x_0,y_0) = 0$, where $H$ is the reduction of $\H$ modulo $p$, is smooth. Letting $\X$ be the projective closure of $\U$, we have that $X = \X \times_{\spec W_2(k)} \spec k$ is the projective closure of $U$, and we see that $X \setminus U$ consists of a single point, which we call the point at infinity. Moreover, the genus $g$ of $X$ can be computed to be $(d-1)(e-1)/2$ by the Pl\"ucker formula. Let $R = k[x_0, y_0]/H(x_0, y_0)$ be the coordinate ring of $U$. For $f \in R$, let $\deg f$ denote the order of the pole at infinity of $f$. \begin{lemma}\label{lin comb} Let $a, b, c \in R$ with $(a,b) = 1$, $\deg(a) = n$, $\deg(b) = m$, and $\deg(c) = r$. Then there exist $u, v \in R$ satisfying $au + bv = c$ with $\deg(u) \leq m+s$ and $\deg(v) \leq n+s$, where $s = \max\{2g, r-n-m\}$. \end{lemma} \begin{proof} Let $P_{\infty}$ be the point at infinity of $X$. Then $a \in L(nP_{\infty})$, $b \in L(mP_{\infty})$, and $c \in L(rP_{\infty})$. For any positive integer $s$, consider the map $L((m+s)P_{\infty})\oplus L((n+s)P_{\infty}) \to L((n+m+s)P_{\infty})$ given by $(u,v) \mapsto au+bv$. We wish first to describe the kernel of this map. If $au+bv=0$, then since $(a,b) = 1$, we have $u=bz$ and $v=-az$ for some $z \in R$, which is then in $L(sP_{\infty})$. Thus the kernel is isomorphic to $L(sP_\infty)$. Now we examine the image. If $s> 2g$, Riemann-Roch gives the dimensions of $L(sP_\infty)$, $L((m+s)P_\infty) \oplus L((n+s)P_{\infty})$, and $L((n+m+s)P_\infty)$ as $s-g+1$, $(m+s+n+s)-2g+2$, $(n+m+s)-g+1$, respectively. Thus, since the dimension of our domain is equal to sum of the dimension of our range with the dimension of our kernel, our map must be surjective. Since we want $c$ in the image we take $n+m+s \ge r$ and $s \ge 2g$. \end{proof} The next theorem uses explicit computations with Witt vectors to show that there is a ``lift of points'' from $U$ to $\U$. Notice that part (2) of the theorem, giving the lower bound on what the degrees of the coordinates of the ``lift'' must be, is primarily of theoretical interest and is not used in the remainder of the paper. \begin{theorem}\label{lift exists} Assume that the equation $\H(\x,\y) = 0$ satisfies the conditions above. Let $P_{\infty}$ be the unique point of $X$ at infinity. Then there is a ``lift of points'' $\lambda:X(k)\setminus\{P_\infty\} \to \X(W_2(k))$ given by $\lambda((x_0, y_0)) = ((x_0, x_1),(y_0,y_1))$, where $x_1$ and $y_1$ are polynomials in $x_0$ and $y_0$ satisfying \begin{enumerate} \item $x_1$ and $y_1$ have poles of order at most $(d-1)(pe+e-1)$ and $(e-1)(pd+d-1)$ respectively at $P_\infty$, and \item If the genus of $X$ is at least two, then either $x_1$ has a pole at $P_\infty$ of order at least $p(e-1)$, or $y_1$ has a pole at $P_\infty$ of order at least $p(d-1)$. \item For any $\f \in L(r Z_\infty)$, we have $\f \circ \lambda = (f_0, f_1)$, a Witt vector of rational functions on $X$. Further, $\deg f_0 \leq r$ and $\deg f_1 \leq \gamma(r)$, where $\gamma(r)$ is a linear polynomial in $r$, independent of $\f$ and satisfying $\gamma(r) \leq p(r-1) + (d-1)(e-1)(p+1) = p(r-1) + 2 g (p+1)$. \end{enumerate} \end{theorem} \begin{proof} Notice first that $x_0$ has a pole at $P_\infty$ of order $d$ and $y_0$ has a pole at $P_\infty$ of order $e$. By calculations in the Witt ring, we see that if $x_1$ and $y_1$ are polynomials in $x_0$ and $y_0$ such that $\H((x_0, x_1), (y_0, y_1)) = 0$ whenever $H(x_0, y_0) = 0$, then $x_1$ and $y_1$ must satisfy $$ \left(\partial H/\partial x_0\right)^p x_1+ \left(\partial H/\partial y_0\right)^p y_1 + J(x_0, y_0) = 0 $$ where $J(x_0, y_0)$ is a polynomial in $x_0$ and $y_0$, having a pole of order at most $pde$ at $P_\infty$. We can apply Lemma~\ref{lin comb} with $a = \left(\partial H/\partial x_0\right)^p$, $b = \left(\partial H/\partial y_0\right)^p$, and $c = J(x_0, y_0)$. Then $n = \deg a = pd(e-1)$, $m = \deg b = pe(d-1)$, and $r \leq pde$. Since $g = (d-1)(e-1)/2$, we have $s = \max\{(d-1)(e-1), pde - pd(e-1) - pe(d-1)\} = (d-1)(e-1)$. Lemma~\ref{lin comb} then gives us that $x_1$ and $y_1$ exist with $\deg x_1 \leq pe(d-1) + (d-1)(e-1) = (pe+e-1)(d-1)$ and $\deg y_1 \leq pd(e-1) + (d-1)(e-1) = (pd+d-1)(e-1)$. To see why at least one of the two lower bounds mentioned in the theorem must hold, let $\lambda: X(k)\setminus\{P_\infty\} \to \X(W_2(k))$ be any lift of points. Recall that the Greenberg transform $G(\X)$ of $\X$ can be thought of as the variety over $k$ obtained by looking at the coordinate components of the Witt vector equations which define $\X$. In particular, the coordinate ring of the affine part of $G(\X)$ is $k[x_0,y_0,x_1,y_1]/(H(x_0,y_0), H_1(x_0,y_0,x_1,y_1))$, so there is a canonical map $G(\X) \to X$. Then $\lambda$ is in fact a map from the affine open subset $U = X \setminus\{P_\infty\}$ of $X$ to the Greenberg transform $G(\X)$ which is a partial splitting of the map $G(\X) \to X$. Since the genus of $X$ is at least $2$, a result of Raynaud (\cite{R}) implies that $G(\X)$ is affine, so that the image of the extension $\overline{\lambda}:X \to \overline{G(\X)}$ (where $\overline{G(\X)}$ is the projective closure of $G(\X)$) cannot lie entirely within $G(\X)$. In particular, we must have $\overline{\lambda}(P_\infty) \in \overline{G(\X)} \setminus G(\X)$. Examining the implications of this condition at a local parameter for $P_\infty$, we get our desired lower bound as follows. Since $\gcd(d,e) = 1$ by assumption, we can find integers $u,v$ with $du + ev = 1$. This means that $t = x_0^{-u}y_0^{-v}$ is a local parameter at $P_\infty$. Then we have that $t \circ \lambda = (t_0, t_1)$, where $t_0 = x_0^{-u}y_0^{-v}$ and $t_1 = -v t_0^p y_0^{-p} y_1 - u t_0^p x_0^{-p} x_1$. The condition on $\overline{\lambda}(P_\infty)$ above amounts to a requirement that $t_1$ have a pole at $P_\infty$. But the valuation of $t_1$ at $P_\infty$ is at least $\min\{p - ep + v_{P_\infty}(y_1), p - dp + v_{P_\infty}(x_1)\}$. Requiring this minimum to be negative proves (2) of the theorem. Finally, to see why (3) is true, first notice that $L(rZ_\infty)$ has a basis consisting of all those monomials $\x^i \y^j$ which satisfy the three conditions $0 \leq j \leq d-1$, $0\leq i$, and $di + ej \leq r$. If $(x_0, y_0) \in X(k) \setminus\{P_\infty\}$, then we have $$ \x^i \y^j (\lambda((x_0, y_0))) = (x_0^iy_0^j, i(x_0^iy_0^j)^p x_0^{-p} x_1 + j (x_0^i y_0^j)^p y_0^{-p} y_1). $$ The first coordinate of the above expression has degree $di + ej \leq r$, and the second has degree at most $$ \max\{p(di+ej) - pd + \deg x_1, p(di + je) - pe + \deg y_1\} $$ which is at most $p(r-1) + (p+1)(d-1)(e-1) = p(r-1) + 2(p+1)g$. Adding constant multiples of these monomials together will not increase the degrees of the coordinate functions. \end{proof} \begin{corollary}\label{plane expsum} Let $\X$, $X$, and $\lambda: X(k) \to \X(W_2(\F_q))$ be as above. Let $P_\infty$ be the unique point at infinity on $X$, and let $Z_\infty$ be any $W_2(\F_q)$-point of $\X$ containing $P_\infty$. For a positive integer $r$ and a rational function $\f \in L(rZ_\infty)$, let $S_{\f,\F_q}$ denote the exponential sum $$ S_{\f,\F_q} = \sum_{P \in X(\F_q) \setminus \{P_\infty\}} e^{2 \pi i T(\f(\lambda(P)))/p^2}. $$ Then $|S_{\f,\F_q}| \leq ((2p+4)g + p(r-1) - 1) \sqrt q$. \end{corollary} \begin{proof} Write $\f(\lambda(P)) = (f_0(P), f_1(P))$. By (3) of Theorem~\ref{lift exists}, we know that $f_0 \in L(r P_\infty)$ and $f_1 \in L(p(r-1) + 2(p+1)g P_\infty)$. Applying Theorem~\ref{expsum} above, we get the desired bound. \end{proof} \section{A lower bound on the size of the trace code} Let $q = p^m$ and, as before, let $\U$ denote an affine curve over $W_2(\F_q)$ defined by a polynomial equation $\H(\x,\y)$ satisfying the conditions of the previous section. Let $\X$ be the projective closure of $\U$, and $U$ and $X$ the reductions modulo $p$ of $\U$ and $\X$ respectively. Let $T$ denote both the trace map $W_l(\F_q) \to W_l(\F_p)$ and the coordinate-wise trace map $(W_l(\F_q))^n \to (W_l(\F_p))^n$. Let $r$ be a positive integer and denote by $\ev:L(r Z_\infty) \to (W_l(\F_q))^n$ the map which defines the code. Corollary~\ref{plane expsum} above can be used to estimate the squared Euclidean weight of the trace code $T(C)$ of an algebraic geometric code $C$. In this section and the next, our aim is to estimate the size of $T(C)$. While it is true that $T(C)$ will be a linear code over $\Z/p^l\Z$ (a $\Z/p^l\Z$-module), it need not be true that $T(C)$ is a free code (module). Thus, we are forced to discuss the cardinality, rather than the rank, of $T(C)$. We will do this by considering the size of the kernel of the trace map $T$. In this section, we find an upper bound on the size of this kernel, hence a lower bound on the size of the trace code. The general structure of our approach follows the approach taken by van der Vlugt in \cite{vV} as he studied trace codes of algebraic geometric codes over finite fields. In particular, the following result extends to rings a result of van der Vlugt \cite{vV} over fields. \begin{proposition}\label{hypoth} Let $\f \in L(r Z_\infty)$ and suppose that $\f \circ \lambda$ is not of the form $F(\h) - \h + \c$ for any $\h \in W_l(K)$ and $\c \in W_l(k)$. Write $\f \circ \lambda = (f_0, \dots, f_{l-1})$ with each $f_j \in K$, and suppose that \begin{equation}\label{hypoth ineq} \max\{p^{l-1-j} \deg f_j \, | \, 0 \leq j \leq l-1\} < \frac{\#X(k) - 1}{\sqrt q} + 1 - 2g. \end{equation} Then $T(\ev(\f)) \neq 0$. \end{proposition} \remark In specific examples, this proposition can be made to involve a general condition on the divisor $r Z_\infty$ rather than a condition on the function $\f$. \endremark \begin{proof} Assume that $T(\ev(\f)) = 0$. Then $T(\f \circ \lambda(P)) = 0$ for all $P \in X(\F_q) \setminus \{P_\infty\}$. Further, $\f \circ \lambda$ is not constant by assumption, so $$ \left|\sum_{P \in X(\F_q)\setminus\{P_\infty\}} e^{2 \pi i T(\f\circ\lambda(P))/p^l} \right| = \#X(\F_q) - 1. $$ But also, by Theorem~\ref{expsum} we have $$ \left|\sum_{P \in X(\F_q)\setminus\{P_\infty\}} e^{2 \pi i T(\f\circ\lambda(P))/p^l} \right| \leq (2g - 1 + \max\{p^{l-1-j} \deg f_j \, | 0 \leq j \leq l-1\})\sqrt q. $$ Putting this together we have $$ \#X(\F_q) - 1 \leq (2g - 1 + \max\{p^{l-1-j} \deg f_j \, | 0 \leq j \leq l-1\})\sqrt q, $$ which contradicts the assumption of the proposition. \end{proof} \begin{theorem}\label{kernel} Let $\f \in L(rZ_\infty)$ and assume that condition (\ref{hypoth ineq}) holds. Then $T(\ev(\f)) = 0$ if and only if $\f \circ \lambda = F(\g) - \g$ for some $\g \in W_l(K)$. \end{theorem} \begin{proof} If $\f \circ \lambda = F(\g) - \g$, then a coordinate of $T(\ev(\f))$ is $T(\f\circ\lambda(P)) = T((F(\g))(P) - \g(P)) = T(F(\g(P))) - T(\g(P)) = 0$. Conversely, suppose that $T(\ev(\f)) = 0$. Then we know that $\f \circ \lambda$ is of the form $F(\h) - \h + \c$ for some $\h \in W_l(K)$ and some $\c \in W_l(\F_q)$ by Proposition~\ref{hypoth} above. But then we have $0 = T(\f \circ \lambda(P)) = T(F(\h(P)) - \h(P)) + T(\c) = T(\c)$ so that $T(\c) = 0$. By Theorem~\ref{Hilb90}, $\c$ must be of the form $\b - F(\b)$ for some $\b \in W_l(\F_q)$. But then we have $\f \circ \lambda = F(\h) - \h + \b - F(\b) = F(\h - \b) - (\h-\b)$ and we are done. \end{proof} We see from Theorem~\ref{kernel} that finding the size of $\ker T$ is equivalent to finding the size of the set $$ \{\g \in W_l(K) \, | \, F(\g) - \g = \f \circ \lambda \text{ for some } \f \in L(r Z_\infty)\}. $$ In order to study this set, we restrict to the case $l = 2$. For $\f \in L(r Z_\infty)$, we have that $\f \circ \lambda = (f_0, f_1)$ with $f_j \in L(r_j P_\infty)$, where $r_0 = r$ and $r_1 = \gamma(r)$, for some linear polynomial $\gamma$ which we compute explicitly from the equation for the curve and the map $\lambda$. Condition (\ref{hypoth ineq}) of Theorem~\ref{hypoth} can be rewritten as \begin{equation}\label{hypoth2} \max\{pr, \gamma(r)\} < \frac{\#X(k) - 1}{\sqrt{q}} + 1 - 2g. \end{equation} In particular, notice that (\ref{hypoth2}) does not depend at all on a specific choice of rational function $\f \in L(rZ_\infty)$. Assuming (\ref{hypoth2}), we know that if $T(\ev(\f)) = 0$, then $\f \circ \lambda = F(\g) - \g$. If we write $\g = (g_0, g_1)$ we see that $$ (f_0, f_1) = F(g_0, g_1) - (g_0, g_1) = (g_0^p - g_0, g_1^p - g_1 - \frac{1}{p} ((g_0^p - g_0)^p - (g_0^{p^2} - g_0^p))). $$ Combining this with our knowledge about $f_0$ and $f_1$, we see that $$ p \deg g_0 \leq r $$ and $$ \max\{p \deg g_1, (p^2-p+1)\deg g_0\} \leq \gamma(r). $$ This gives three conditions which must be satisfied: \begin{enumerate} \item $\deg g_0 \leq \lfloor \frac{r}{p}\rfloor$ \item $\deg g_0 \leq \lfloor \frac{\gamma(r)}{p^2-p+1}\rfloor$ \item $\deg g_1 \leq \lfloor \frac{\gamma(r)}{p}\rfloor$ \end{enumerate} Putting (1) and (2) together, we have proven the following: \begin{theorem}\label{lift kernel} In the case where $l = 2$, if $T(\ev(\f)) = 0$ and condition (\ref{hypoth2}) is satisfied, then $\f \circ \lambda = F(\g) - \g$, where $\g = (g_0, g_1) \in W_l(K)$ with $g_j \in L(s_jP_\infty)$ where $$ s_0 = \min\{ \lfloor \frac{r}{p} \rfloor, \lfloor \frac{\gamma(r)}{p^2-p+1} \rfloor \} $$ and $$ s_1 = \lfloor\frac{\gamma(r)}{p}\rfloor. $$ \end{theorem} We now set out to bound the size of $\ker T$. We will do this by bounding the number of pairs $(g_0, g_1) \in W_l(K)$ such that, in the notation of the previous theorem, $g_j \in L(s_j P_\infty)$ and $F((g_0, g_1)) - (g_0, g_1) = \f \circ \lambda$ for some $\f \in L(r Z_\infty)$ satisfying (\ref{hypoth2}) and such that $T(\ev (\f)) = 0$. Because of the existence of $\lambda$, there exists also $\phi: \U \to \U^{\sigma}$ lifting Frobenius by \cite{Bu1}. Let us choose some function $\x$ regular on $\U$. Then $\phi^*(d\x)/p \equiv \omega \pmod p$, where $\omega$ is a differential regular on $U$, as shown by Mazur in \cite{M}. \begin{lemma}\label{diff} If $\f\circ\lambda = (f_0,f_1)$ then $df_1/dx = (df_0/dx)^p\omega/dx -f_0^{p-1}df_0/dx $. \end{lemma} \begin{proof} Let $\phi:\U \to \U^\sigma$ be the lift of Frobenius. Then we have $f_1 \equiv (\f\circ\phi - \f^p)/p \pmod p$. Differentiating this last equation gives $$ df_1 \equiv (\phi^*(d\f)- p\f^{p-1}d\f)/p \pmod p. $$ Also, $$ \phi^*(d\f) \equiv \phi^*(d\x)(d\f/d\x)\circ\phi). $$ Combining these two equations gives $$ df_1 \equiv \omega (d\f/d\x)\circ\phi) -\f^{p-1}d\f \pmod p, $$ which simplifies to (using that $\g\circ\phi \equiv \g^p \pmod p$ for any $\g$) $$ df_1/dx = (df_0/dx)^p\omega/dx -f_0^{p-1}df_0/dx $$ as desired. \end{proof} \begin{theorem}\label{ker size} Under the above conditions, \begin{align*} \#\ker(T) &\leq \#L(\lfloor\frac{r}{p}\rfloor P_\infty) \cdot \#L(\lfloor\frac{\gamma(r)}{p^2}\rfloor P_\infty)\\ &\leq q^{\lfloor\frac{\gamma(r)}{p^2}\rfloor + \frac{r}{p} + 2}. \end{align*} \end{theorem} \begin{proof} Let $A(x)= \frac{1}{p} ((x^p - x)^p - (x^{p^2} - x^p)) \mod p$. Then $A'(x)= -(x^p - x)^{p-1}-x^{p-1}$. Suppose that $\f\circ\lambda = F(\g)-\g$, where $\g=(g_0,g_1)$. By computation with Witt vectors, this translates to the pair of equations $f_0=g_0^p-g_0$ and $f_1= g_1^p-g_1-A(g_0)$. Differentiating these equations gives $df_0/dx=-dg_0/dx$ and \begin{align*} -dg_1/dx &= df_1/dx + A'(g_0)g_0'\\ &= (df_0/dx)^p\omega/dx -f_0^{p-1}df_0/dx + A'(g_0)g_0'\\ &= -(dg_0/dx)^p\omega/dx +(g_0^p-g_0)^{p-1}dg_0/dx + A'(g_0)g_0'\\ &= -(dg_0/dx)^p\omega/dx -g_0^{p-1}dg_0/dx. \end{align*} Thus, if $\deg \f = r$, then $\deg f_0 \le r , \deg f_1 \le \gamma (r)$. It then follows that $\deg g_0 \le r/p$ and $\deg g_1 \le \gamma(r)/p$. Moreover, $g_1 = \Psi(g_0) + u^p$, where $\Psi(g_0)$ is a fixed solution to $d\Psi(g_0)/dx=-(dg_0/dx)^p\omega/dx -g_0^{p-1}dg_0/dx$, with $\deg \Psi(g_0) \le s/p$, provided such solution exists (otherwise we cannot have such a pair $(g_0,g_1)$). Then $\deg u \le \gamma(r)/p^2$. Given $r$, the number of possible $(g_0,g_1) \in W_l(\F_q)$ is at most the number of possible $g_0$ times the number of possible $u$. This gives the first estimate in the theorem. The second follows from using the trivial estimate that $\dim L(D) \leq \deg D + 1$ for any effective divisor $D$ on a curve $X$ over a field. \end{proof} \begin{theorem}\label{lower bound} In the situation above, the cardinality of the trace code satisfies $$ \#T(C) \geq q^{2r - 2g - \lfloor\frac{r}{p}\rfloor - \lfloor\frac{\gamma(r)}{p^2}\rfloor}. $$ \end{theorem} \begin{proof} Just use the fact that $\#C = q^{2(r+1-g)}$ and the estimate on the size of the kernel of the trace map in Theorem~\ref{ker size}. \end{proof} \section{An upper bound on the size of the trace code} After finding a lower bound on the size of the trace code in the previous section, the aim of this section is to find an upper bound on how large a trace code can be. \begin{definition} For $B \subseteq (W_l(\F_{p^m}))^n$, define \begin{align*} F(B) &:= \{(F(b_1), \dots, F(b_n)) \, | \, (b_1, \dots, b_n) \in B\}\\ \intertext{and} B|_{W_l(\F_p)} &:= B \cap (W_l(\F_p))^n. \end{align*} If $B$ is a free $W_l(\F_{p^m})$-module, we denote by $\rk(B)$ its rank. \end{definition} \begin{proposition}\label{upper bound} (compare \cite{St} Proposition VIII.1.4, p223) Let $C$ be a free code over the ring $W_l(\F_{p^m})$ and let $B \subseteq C$ be a free subcode such that $F(B) \subseteq C$. Then $$ \#T(C) \leq p^{lm(\rk(C) - \rk(B))} \cdot \#B|_{W_l(\F_p)}. $$ \end{proposition} \begin{proof} Define $\wp:B \to C$ by $\wp(b) = F(b) - b$. Then $b \in \ker\wp \iff F(b) = b \iff b \in B|_{W_l(\F_p)}$. But $T(a) = T(F(a))$ for any $a$, so $\im \wp \subseteq \ker T$. Thus $$ \#\ker T \geq \#\im\wp = \#B/\#\ker\wp = \#B/\#B|_{W_l(F_p)} $$ and the result follows by simply noting that $\#T(C) = \#C/\#\ker T$. \end{proof} Because of the existence of $\lambda$, we know that the Frobenius lifts to a map $\Phi: R \to R$, where $R = \Gamma(\U, \co_\X(\U))$ is the ring of regular functions on $\U$. Further, for $\f \in R$ we have $F(\f \circ \lambda) = (\Phi(\f))\circ \lambda$. \begin{lemma} In the situation of Theorem~\ref{lift exists}, assume $d