%% 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')