$\}
As it is, this map is no good: we merely map $l+1$-tuples to $l+1$-tuples. But a slight variation on Theorem 1 (which follows directly from it) does the trick.
\begin{theorem}
{\bf Useful Polynomial Interpolation Theorem:} Let $F$ be a field. We are given $\alpha_1, \alpha_2, \ldots \alpha_{n}\in F$, pairwise distinct. Then for any distinct $i_1, i_2, \ldots i_{l+1} \in [n]$ and any $y_1, y_2, \ldots, y_{l+1}\in F, \exists$ unique polynomial $p(x)$ with degree $\leq l$ such that $p(\alpha_{i_t}) = y_i, \forall t \in [l+1]$.
\end{theorem}
This motivates the Reed Solomon Code (1960ish) as defined below:
\begin{itemize}
\item Given $n, q, k, \alpha_1, \ldots \alpha_n$, with $\alpha_i$ distinct elements of $\F_q$.
\item For $c = (c_0, c_1, \ldots c_{k-1})$, define polynomial $p_c(x) = c_0 + c_1x + \ldots c_{k-1}x^{k-1}$
\item The code is specified by the encoding function
$\rs : (c_0, c_1, \ldots c_{k-1}) := \left $, the evaluation of $p$ on each point of $\F_q^m$.
\end {itemize}
Note that this too is a linear code.
To determine the parameters of the code, we need a little bit of work.
\begin{itemize}
\item $n = q^m$
\item $k = {l+m \choose l}$ when $l \leq q-1$. This is merely the number of monomials of degree $\leq l$, and since the monomials form a basis for $P_m^l$, it is the dimension of our code. If $l \geq q$ it gets messy because of identities like $x^q = x, \forall x \in \F_q$, and thus we will ignore this case forever.
\item $d = \left(1-\frac{l}{q}\right)n$, because of the following result which will be proved later: Any non-zero polynomial on $\F_q^m$ of degree $\leq l$ is zero on at most $\frac{l}{q} q^m$ points. We already know this result for $m = 1$ (and indeed used it to prove the distance of the RS code).
\item $q = q$
\end{itemize}
Let us just pick some parameters arbitrarily to get a feel for the kinds of codes that we get.
\begin{itemize}
\item $m = 2$
\item $l = \frac{1}{3}q$
\item So $n = q^2$, $k = {\frac{1}{3}q + 2 \choose 2} \approx \frac{1}{18}q^2$, $d = \frac{2}{3}n = \frac{2}{3}q^2$
\end{itemize}
So $\exists [q^2, \frac{1}{18}q^2, \frac{2}{3}q^2]_q$ codes (note the constant rate and constant relative distance). Here $q \approx \sqrt{n}$, which is already much better than the RS code. With a slightly different choice of parameters, for any constant $m$, there is a family of $[q^m, \frac{1}{(2m)^m} q^m, \frac{1}{2} q^m]_q$ codes with good distance and $q \approx n^{1/m}$.
\section{The Plotkin Bound and Hadamard Codes }
Let us see what kind of binary RM codes exist. If we put $q = 2$, since $l \leq q-1$, we are forced to put $l = 1$. Thus we are dealing with linear multivariate polynomials over $\F_2$. The only parameter we can vary is $m$. We get $n=2^m$, $k = {m + 1\choose 1} = m+1$ and $d = 1/2 \cdot 2^m$. Now the rate of this code is horrendous, $m+1$ bits get encoded as $2^m$ bits. However, we get great relative distance (= 1/2). This code is called the Hadamard code.
Last lecture we saw the unnerving phenomenon that there cannot exist a binary code with more than $2$ codewords with relative distance $> 2/3$ \footnote{To recap, let $x,y,z$ be codewords in a code with relative distance $2/3 + \epsilon$. Look at $x-y$ and $x-z$. They are both of relative hamming weight $2/3 + \epsilon$. Thus they agree in at least $1/3 + 2\epsilon$ of the positions. So the relative distance between $y$ and $z$ is at most $2/3 - 2\epsilon$.} The Plotkin bound extends this idea to codes with relative distance $1/2$ and shows that the Hadamard codes are optimal for this distance.
\begin{theorem} {\bf Plotkin Bound:} If there exists a $(n,k,n/2)_2$ code, then $k \leq \log_2(2n)$.
\end{theorem}
\begin{proof-sketch}
Suppose the code consists of words $c_1, c_2, \ldots c_K \in {0,1}^n$. Create vectors $v_1, v_2 \ldots v_K \in {1,-1}^n$ by
$(v_i)_j = (-1)^{(c_i)_j}$. Now, the condition that $c_i$ and $c_j$ have distance at least $1/2$ is equivalent to the condition
that $v_i$ and $v_j$ have inner product $\left