%% LyX 1.3 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[10pt]{article} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{amsthm,amsmath,amssymb} \IfFileExists{url.sty}{\usepackage{url}} {\newcommand{\url}{\texttt}} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] \numberwithin{equation}{section} %% Comment out for sequentially-numbered \numberwithin{figure}{section} %% Comment out for sequentially-numbered \theoremstyle{plain} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \newcommand{\g}{\mathfrak{g}} \newcommand{\M}{\mathcal{M}} \newcommand{\h}{\mathfrak{h}} \newcommand{\sut}{\mathfrak{n}} \newcommand{\ut}{\mathfrak{b}} \newcommand{\N}{\mathbb{N}} \newcommand{\A}{\mathcal{A}} \newcommand{\D}{\mathbb{D}} \newcommand{\C}{\mathbb{C}} \let\ker=\undefined \DeclareMathOperator{\ker}{Ker} \DeclareMathOperator{\im}{Im} \DeclareMathOperator{\ad}{ad} \DeclareMathOperator{\s}{span} \DeclareMathOperator{\Mat}{Mat} \DeclareMathOperator{\End}{End} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\tr}{Tr} \oddsidemargin=0.15in \evensidemargin=0.15in \topmargin=-.5in \textheight=9in \textwidth=6.25in \makeatother \begin{document} %\title{6.895: Lecture 14} %\author{Lecturer: Madhu Sudan\\ %Scribe: Alexey Spiridonov} %\maketitle \input{preamble.tex} \lecture{14}{October 27, 2004}{Madhu Sudan}{Alexey Spiridonov} \section{Motivation} Today's lecture's goal is to describe, informally, a family of codes that achieve better-than-random performance. This lecture does not describe these codes either accurately or completely; much extra reading is necessary to understand this material. While they are also incomplete, it may be helpful to refer to Jonathan Kelner's notes from 2002 \cite{kelnernotes}. In a previous lecture, we have shown that the Gilbert-Varshamov bound (obtained by a random construction) guarantees the existence of a family of codes such that \[ \delta=\Bigl(1-O(\frac{1}{\log_{2}q})\Bigr)-R.\] The Singleton bound, on the other hand, tells us that every family of codes is limited by $\delta\le1-R$. Therefore, the above construction approaches the optimum as $q$ grows. However, Plotkin's bound restricts the rate at which any family of codes can approach the Singleton bound: \[ R+\frac{q}{q-1}\delta\le1\Rightarrow R+\delta\lesssim1-\frac{1}{q}.\] The Gilbert-Varshamov construction requires an alphabet exponentially large in $n$ in order for the distance to have be $\frac{1}{O(n)}$ away from Singleton. (unlike Plotkin, which permits a linear dependence). The nonconstructive nature of the Gilbert-Varshamov bound aside, this slow convergence makes it impractical to get codes that are very close to the Singleton bound. The codes in this lecture are $[n,k,(1-\frac{1}{\sqrt{q}-1})n-k]_{q}$ codes; now, for $\frac{1}{O(n)}$ convergence, we only need an alphabet quadratic in $n$; this is much better. It is an open problem whether the {}``defect'' in the distance can be improved to $\frac{1}{q}$ to make Plotkin's bound tight. \section{Algebraic Geometry Codes} For the rest of the lecture, we will be working over the field $\F_{q}$, with $q$ a prime power. The codes we'll construct derive from Reed-Solomon (RS) codes, and share the essential mechanics. Our message space will be a subspace $\M$ of the $m$-variable polynomials of $\F_{q}$: $\M\subseteq\F[x_{1},\dots,x_{m}]$ (subspace means that $\M$ is closed under addition and multiplications by scalars from the field). We will encode a polynomial by evaluating it at a subset $S$ of points of $\F_{q}$ (rather than the whole space, as in RS codes). In order to get an efficient code, we want to make $\dim\M$ relatively larger, $|S|$ relatively smaller, and we are also looking to maximize the code's distance. Since it's a linear code, rather than look for the minimum number of places two polynomials' encodings differ, we can get the distance from the maximum number of zeros any $p\in\M$ can have on $S$. These codes are called {}``alebgraic geometry codes'' because the sets $S$ we will pick will be \emph{varieties,} objects that algebraic geometry studies. A \emph{variety} $V(p_{1},\dots p_{k})\subseteq\F_{q}^{m}$ is the set of common zeros of the polynomials $p_{i}$:\[ V(p_{1},\dots,p_{k})=\{ x\in\F_{q}^{m}:p_{i}(x)=0\forall1\le i\le k\}.\] \section{A Concrete Example} We will make a $[19,6,13]_{13}$ code. With a Reed-Solomon code, we would be able to get $[19,6,14]_{19}$ which gets us $1$ extra distance at the expense of a larger alphabet. Neither is unambiguously better -- it's a tradeoff. First off, we choose $q=13$ and $m=2$. We let $\M=\s\{1,x,y,x^{2},xy,y^{2}\}\subset\F_{13}[x,y]$ be the 2-variable monomials of degree $\le2$. Take $S=V(R)$, the set of zeros of the polynomial \[ R(x,y)=y^{2}-2(x-1)x(x+1).\] Since the domain of the polynomial has just $|\F_{13}^{2}|=169$ points, one can easily see by enumeration that the $|S|=19$. There are ways to speed up the computation of these roots, but in most applications, the search space is small, and the search only needs to be done once. So, in our code, $k=\dim\M=6$ and $n=|S|=19$. It remains to find the minimum distance $d$. It is achieved by a non-zero polynomial $p\in\M$ which has the most roots in $S$. In other words, we want to find $d=n-\max|V(p,R)|$: the maximum number of zeros that $p\in\M$ can have in common with $R$ without being identically zero. Since we want $d$ maximized, a scenario we want to avoid having all zeros of $p$ fall in $S$. This would happen, for instance, if $p$ divided $R$. Luckily, $R$ doesn't factor (is irreducible). Intuitively, if $0\ne f$ were to match a lot of zeros of $R$, it would need to approximate it well. However, polynomials in $f$ have degree at most 2, while $R$ has degree 3, so this shouldn't happen if $p\nmid R$. The following theorem makes this intuition precise. \begin{thm} [Bezout] Let $A(x,y)$ be a polynomial of degree $d_{A}$, and $B(x,y)$ be a polynomial of degree $d_{B}$ (both nonzero). If $|V(A,B)|\ge d_{A}d_{B}$, then $A$ and $B$ have a nontrivial common factor. \end{thm} \begin{proof} We only sketch an idea for a proof. This might not be the best approach for turning it into a formal argument; it's main intention is to give a flavor of the subject. We want to compute a quantity called the \emph{resultant} polynomial with respect to y:\[ r(x)=p(x,y)A(x,y)+q(x,y)B(x,y),\] where $p$ and $q$ are polynomials in $x,y$ chosen so that $r$ does not depend on $y$. We can pick find such an $r(x)\not\equiv0$ of degree $\le d_{A}d_{B}$, unless $A$ and $B$ have a common factor containing $y$. Now, if we pretend all common roots of $A$ and $B$ have distinct $x$ values, then there can't be more than $d_{A}d_{B}$ of them (otherwise the resultant would be zero, which implies that both original polynomials are zero); from this, it can be concluded that $A$ and $B$ cannot have zeros with $d_{A}d_{B}$ distinct $x$ coordinates. Since $A$ and $B$ don't have a common factor, one should always be able to find a change of coordinates ($u=ax+by$, $v=cx+dy$) to get all roots to have distinct coordinates. Thus, we would obtain the required bound on $V(A,B)$. \end{proof} From the theorem, it follows that no $p\in\M$ has more than 6 roots in $S$, so the minimum distance is $d=19-6=3$. Thus, we have the promised $[19,6,13]_{13}$ code. \section{General Construction} The essential ideas about constructing algebraic geometry (AG) codes in the previous sections are as follows: \begin{enumerate} \item We work over a vector space $\F_{q}^{m}$ with $q$ a prime power. Take our message space $\M$ to be a subspace of the $m$-variable polynomials on $\F_{q}^{m}$. Then, our message words can be viewed as elements of $\F_{q}^{\dim\M}$ (coordinates of $v\in\M$ in some basis), giving $k=\dim\M$. \item To send $p\in\M$, we send its the result of its evaluation on a special subset of $\F_{q}^{m}$, a variety $S=V(R_{1},\dots,R_{k})$. Then, $n=|S|$. \item We can find the minimum distance by an algebraic method using resultants. Our selections of $\M$ and $S$ are made to get the best distance we can. \end{enumerate} Constructions for the first family of such codes came riding on discoveries in algebraic geometry and number theory, and were very complex (due to Tsafsman, Vladuts, and Zink). Thereafter, Garcia and Stichtenoth made a considerably simplified construction. We present a derivative of this construction described by Pellikaan, Stichtenoth, and Torres. Shum recently discovered an $\tilde{O}(n^{2})$% \footnote{$\tilde{O}(n^{2})=O(n^{2}\log^{O(1)}n)$ is just a way to neglect a constant log power.% } for both a encoding and decoding algorithm. % \footnote{Thanks are also due to Sergey Yekhanin for his help in understanding this construction.% } For this construction, we will take $q=p^{2}$, $p$ prime. We will use two functions $\F_{q}\rightarrow\F_{p}$: the trace $\tr$ and the norm $N$, defined as follows:\begin{align*} N(x)=x^{p+1}; & \tr x=x^{p}+x.\end{align*} The fact that both of these functions map from $\F_{q}$ to the subfield $\F_{p}$ is a simple exercise. In addition, the trace is linear; this implies that it is a {}``$p\rightarrow1$'' map. In other words, the inverse image of any point $x\in\F_{p}$ consists of exactly $p$ points. To construct $S=S_{m}$, label the coordinates of $\F_{q}^{m}$ as $x_{1},\dots,x_{m}$. Let $R_{i}(x_{i},x_{i+1})=\tr x_{i+1}-\frac{N(x_{i})}{Tr(x_{i})}$% \footnote{It's not clear that this is a polynomial, but we treat it as such for the purposes of the construction.% }, and then we can define $S_{m}=V(R_{1},\dots,R_{m-1})$. Next, we inductively derive a lower bound for $S$ in terms of $q$ and $m$. The claim is that $|S_{i}|\ge p^{i}(p-1)$. Instead of dealing with $S'$, we will work with a subset defined so: \[ S_{i+1}\supseteq\{\vec{x}\in\F_{q}^{m}:\tr x_{j}\ne0,\tr x_{j+1}=\frac{N(x_{j})}{\tr x_{j}}\,\forall1\le j\le i+1\}=S_{i}'.\] In the base case, $m=1$, we just have the requirement $\tr x_{1}\ne0$; since the trace is $p\rightarrow1$, the size of the inverse image of $0$ is $p$, leaving $p(p-1)$. Compared to $S_{i}$, $S_{i+1}$ has an extra variable $x_{i+1}$, and the constraints $\tr x_{i+1}\ne0$ and $\tr x_{i+1}=\frac{N(x_{i})}{\tr x_{i}}$. For any fixed assignment of $(x_{1},\dots,x_{i})$, there are $p$ values of $x_{i+1}$ that satisfy both of the constraints. By induction, the claim follows. One might wonder why we obtained a lower bound rather than an upper bound (since we said we're trying to minimize $|S|$, relatively). However, given this lower bound, we will now produce the maximal message size and distance to match, and everything will work. We will pick some polynomials as a basis for $\M$ (although we won't specify what they are exactly). Call this basis $p_{1},\dots,p_{k}\in\F_{q}[x_{1},\dots,x_{m}]$; we will take them so that they have some helpful properties. We will associate with every $p\in\F_{q}[x_{1},\dots,x_{m}]$ an order $ord_{S}(p)$ with respect to $S$ that behaves like a degree of a polynomial. In particular, \begin{eqnarray*} ord_{S}(P+Q) & \le & \max(ord_{S}(P),ord_{S}(Q))\\ ord_{S}(PQ) & = & ord_{S}(P)+ord_{S}(Q)\\ \#\text{zeros of }P\text{ on }S & \le & ord_{S}(P),\text{ if }P\ne0.\end{eqnarray*} A possible construction for this order is to take the resultant of $P$ together with all $R(x_{i},x_{i+1})$. I believe the following few paragraphs contain some incorrect statements. The order permits us to make the $p_{i}$ quite structured. For instance, if we have $p$ and $q$ linearly independent, of the same order, one can clearly% \footnote{If one thinks of polynomial degrees, this statement is trivial. Since our orders are defined to behave exactly the same, so is this.% } replace them by $p',q'$ (having the same span) such that $ord_{S}(p')=ord_{S}(p)$ and $ord_{S}(q')