\documentclass[10pt]{article}
\usepackage{amsfonts}
%\usepackage{epsfig}
\begin{document}
%--------------
%% preamble.tex
%% this should be included with a command like
%% \input{preamble.tex}
%% \lecture{1}{September 4, 1996 }{Daniel A. Spielman}{name
%% of poor scribe}
\hbadness=10000
\vbadness=10000
%\setlength{\oddsidemargin}{.25in}
%\setlength{\evensidemargin}{.25in}
%\setlength{\textwidth}{6in}
%\setlength{\topmargin}{-0.4in}
%\setlength{\textheight}{8.5in}
\newcommand{\handout}[5]{
\renewcommand{\thepage}{#1-\arabic{page}}
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { {\bf 6.440 Essential Coding Theory }
\hfill #2 }
\vspace{4mm}
\hbox to 5.78in { {\Large \hfill #5 \hfill} }
\vspace{2mm}
\hbox to 5.78in { {\it #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}
\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer:
#3}{Scribe: #4}{Lecture #1}}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{example}[theorem]{Example}
\newtheorem{assumption}[theorem]{Assumption}
\newcommand{\qed}{\rule{7pt}{7pt}}
\newcommand{\dis}{\mathop{\mbox{\rm d}}\nolimits}
\newcommand{\per}{\mathop{\mbox{\rm per}}\nolimits}
\newcommand{\area}{\mathop{\mbox{\rm area}}\nolimits}
\newcommand{\cw}{\mathop{\rm cw}\nolimits}
\newcommand{\ccw}{\mathop{\rm ccw}\nolimits}
\newcommand{\DIST}{\mathop{\mbox{\rm DIST}}\nolimits}
\newcommand{\OP}{\mathop{\mbox{\it OP}}\nolimits}
\newcommand{\OPprime}{\mathop{\mbox{\it OP}^{\,\prime}}\nolimits}
\newcommand{\ihat}{\hat{\imath}}
\newcommand{\jhat}{\hat{\jmath}}
\newcommand{\abs}[1]{\mathify{\left| #1 \right|}}
\newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip}
\newenvironment{proof-sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip}
\newenvironment{proof-idea}{\noindent{\bf Proof Idea}\hspace*{1em}}{\qed\bigskip}
\newenvironment{proof-of-lemma}[1]{\noindent{\bf Proof of Lemma #1}\hspace*{1em}}{\qed\bigskip}
\newenvironment{proof-attempt}{\noindent{\bf Proof Attempt}\hspace*{1em}}{\qed\bigskip}
\newenvironment{proofof}[1]{\noindent{\bf Proof}
of #1:\hspace*{1em}}{\qed\bigskip}
\newenvironment{remark}{\noindent{\bf Remark}\hspace*{1em}}{\bigskip}
% \makeatletter
% \@addtoreset{figure}{section}
% \@addtoreset{table}{section}
% \@addtoreset{equation}{section}
% \makeatother
\newcommand{\FOR}{{\bf for}}
\newcommand{\TO}{{\bf to}}
\newcommand{\DO}{{\bf do}}
\newcommand{\WHILE}{{\bf while}}
\newcommand{\AND}{{\bf and}}
\newcommand{\IF}{{\bf if}}
\newcommand{\THEN}{{\bf then}}
\newcommand{\ELSE}{{\bf else}}
% \renewcommand{\thefigure}{\thesection.\arabic{figure}}
% \renewcommand{\thetable}{\thesection.\arabic{table}}
% \renewcommand{\theequation}{\thesection.\arabic{equation}}
\makeatletter
\def\fnum@figure{{\bf Figure \thefigure}}
\def\fnum@table{{\bf Table \thetable}}
\long\def\@mycaption#1[#2]#3{\addcontentsline{\csname
ext@#1\endcsname}{#1}{\protect\numberline{\csname
the#1\endcsname}{\ignorespaces #2}}\par
\begingroup
\@parboxrestore
\small
\@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
\endgroup}
\def\mycaption{\refstepcounter\@captype \@dblarg{\@mycaption\@captype}}
\makeatother
\newcommand{\figcaption}[1]{\mycaption[]{#1}}
\newcommand{\tabcaption}[1]{\mycaption[]{#1}}
\newcommand{\head}[1]{\chapter[Lecture \##1]{}}
\newcommand{\mathify}[1]{\ifmmode{#1}\else\mbox{$#1$}\fi}
%\renewcommand{\Pr}[1]{\mathify{\mbox{Pr}\left[#1\right]}}
%\newcommand{\Exp}[1]{\mathify{\mbox{Exp}\left[#1\right]}}
\newcommand{\bigO}O
\newcommand{\set}[1]{\mathify{\left\{ #1 \right\}}}
\def\half{\frac{1}{2}}
% Coding theory addenda
\newcommand{\enc}{{\sf Enc}}
\newcommand{\dec}{{\sf Dec}}
\newcommand{\E}{{\rm Exp}}
\newcommand{\Var}{{\rm Var}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\integers}{{\mathbb Z}^{\geq 0}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\cal Q}}
\newcommand{\eqdef}{{\stackrel{\rm def}{=}}}
\newcommand{\from}{{\leftarrow}}
\newcommand{\vol}{{\rm Vol}}
\newcommand{\poly}{{\rm poly}}
\newcommand{\ip}[1]{{\langle #1 \rangle}}
\newcommand{\wt}{{\rm wt}}
\renewcommand{\vec}[1]{{\mathbf #1}}
\newcommand{\mspan}{{\rm span}}
\newcommand{\rs}{{\rm RS}}
\newcommand{\RM}{{\rm RM}}
\newcommand{\Had}{{\rm Had}}
\newcommand{\calc}{{\cal C}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\fig}[4]{
\begin{figure}
\setlength{\epsfysize}{#2}
\vspace{3mm}
\centerline{\epsfbox{#4}}
\caption{#3} \label{#1}
\end{figure}
}
\newcommand{\ord}{{\rm ord}}
\providecommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\embed}{{\rm Embed}}
\newcommand{\qembed}{\mbox{$q$-Embed}}
\newcommand{\calh}{{\cal H}}
\newcommand{\lp}{{\rm LP}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\lecture{6}{Feb 25, 2013}{M. Sudan}{Timothy Chu}
\section{Algebraic Codes Continued: Overview}
The scope of these notes will cover
\begin{enumerate}
\item Reed Solomon, Reed Muller, and Hadamard Codes
\item Duals of (Linear) Codes
\item Properties of finite fields, which will lead us to the Wozencraft Ensemble of Codes (which we did not finish during this lecture). For now, think of our foray into the Wozencraft ensemble of codes as an exercise understanding finite fields and what they can do for you. However, we do not actually get to the explicit description of the Wozencraft ensemble.
\end{enumerate}
\subsection{Basic Notation Review}
Recall from lecture $1$ that we described codes using the notation $(n, k, d)_q; R, \delta$ where:
\begin{enumerate}
\item The alphabet $\Sigma$ has $|\Sigma|=q$, and codewords reside in $\Sigma^n$.
\item $\triangle(C) \geq d$ (where $\triangle$ is the Hamming Distance metric).
\item $|C| \geq q^k$.
\end{enumerate}
$R$ and $\delta$ are defined as $\lim_{n \rightarrow \infty} \inf \frac{k}{n}$ and $\lim_{n \rightarrow \infty} \inf \frac{d}{n}$. Families of codes are described by the point $(\delta, R)$.
Previously, we introduced Reed Solomon and Reed Muller codes, which we will review shortly in these notes.
\vspace{3 mm}
For algebraic codes presented in these notes, we work over a finite field. These notes assume some basic familiarity about finite fields; namely, that most familiar operations with polynomials over the field $\mathbb{R}$ or $\mathbb{Q}$ (long division, interpolation, factorization) apply to the finite field $F_q$ of $q$ elements.
\section{General Ideas for Algebraic/polynomial Codes}
\begin{itemize}
\item Message = coefficients of polynomials
\item Encoding = Evaulation of polynomials at different values in , so
\item Evaluation $\Rightarrow$ Encoding
\item Interpolation $\Rightarrow$ Decoding from an error free code.
\end{itemize}
\subsection{Review of Reed Solomon Codes}
Recall the \textit{singleton bound}, proven in lecture $3$, which states that $k \leq n-d+1$, or $R \leq 1-\delta$.
%The original idea behind Reed Solomon codes was to create a polynomial whose coefficients are the $q$-ary bits of the words we desire to encode. The word is then encoded by evaluate the polynomials at some number $n > k$ points, and then using interpolation to recover the original message.
Reed Solomon codes are algebraic (linear) codes which meet the singleton bound (as long as $q \geq n$) and in practice, they are fast to decode (there exist fast decoding techniques due to Berlekamp, which will not be elaborated here).
\vspace{2mm}
A Reed Solomon code is created by choosing a set $(\alpha_1, \alpha_2, \ldots \alpha_n)$ of distinct elements from $\mathbb{F}_q$. Message $m = (m_0, m_1, \ldots m_{k-1})\in \mathbb{F}_q^k$ is associated with a polynomial $m(x) := m_{k-1}x^{k-1}+m_{k-2}x^{k-2} + \ldots + m_0$. $m$ is encoded via
Enc$(m) \equiv m(\alpha_1, \alpha_2, \ldots \alpha_n) \in \mathbb{F}_q^n$.
The code has dimension $k$ and the polynomial $m(x)$ has degree $k-1$. The Reed Solomon code is linear (see note below), so if two code words $x, y \in \mathbb{F}^q$, then $x-y \in C$. Polynomials of degree $k-1$ in a finite field $F_q$ have no more than $k-1$ roots, so $x-y$ has no more than $k-1$ bits with value $0$. So $\triangle (x, y) \geq n - k + 1$ for all $x$ and $y$, so $d \geq n-k+1$. This inequality is the reverse of the Singleton bound, which holds for all codes, and thus Reed Muller meets the Singleton Bound exactly.
\vspace{2 mm}
Note: it is not difficult to see from the encoding procedure that the Reed Solomon code is linear: specifically, the generator matrix $\in \mathbb{F}_q^{k \times n}$ of the code is
$$\left (\begin{array}{ccccc}
1 & 1 & \ldots & 1 \\
\alpha_1^1 & \alpha_2^1 & \ldots & \alpha_n \\
\alpha_1^2 & \alpha_2^2 & \ldots & \alpha_n^2 \\
\ldots & \ldots & \ldots & \ldots \\
\alpha_1^{k-1} & \alpha_2^{k-1} & \ldots & \alpha_n^{k-1}\\
\end{array} \right)$$
\section{Hadamard Code}
The Hadamard code is a linear code which has Hamming Distance roughly meets the Plotkin bound from lecture $4$. If $n = 2^j,$ then $d= 2^{j-1}$ (good) and $R= \frac{j+1}{2^j}$ (bad). The Hadamard Codes are described at the ends of the notes of the previous lecture.
The Hadamard Code is a special case of a first-order Reed Muller code over the field $\mathbb{F}_2$.
\section{Review of Reed Muller Codes}
A Reed Muller code can be constructed based on polynomials of low degree on a finite field $\mathbb{F}_q$. Let $m$ and $r$ be integers where $m$ is thought of to be much larger than $r$. Then the messages in this code are all $m$-multivariate polynomials $P$ of degree at most $r$ where each variable has individual degree at most $q-1$. The Reed Muller encoding of $P$ is the evaluation of $P$ on all $x \in F_q^m$ (the values of $P$ over all choice of values of the $m$ variables). There are $\binom{m+r}{m}$ elements in the message space.
For formal construction of the Reed Muller codes, see the scribe notes for lecture $5$.
\section{Performance of Reed Solomon and Reed Muller Codes}
\subsection{Reed Solomon Code}
-Evaluate univariate polynomials of degree $< k$ over $\mathbb{F}_q$ and looking at the coefficients. Code is an $[n,k,n-k+1]_q$ code with $n \leq q$.
Performance: $r+\delta \rightarrow 1 + \epsilon$.
\subsection{Reed Muller Codes}
-Evaluate $m$-variate polynomials of degree $\leq r$ (where $m$ is thought of as much greater than $r$) over $\mathbb{F}_q$, over the entire domain $\left(\mathbb{F}_q^m\right)$.
-Individual degree of each variable is $\leq q-1$ (We arrange for this since $x^q = x$ for all $x \in \mathbb{F}_q$).
\vspace{2 mm}
\noindent \textbf{Parameters of Reed Muller Codes}
\begin{itemize}
\item $n = q^m$.
\item $k = \binom{m+r}{m}$ if $r < q$, and $\left(\frac{r}{m}\right)^m, \binom{m}{r} \leq k \leq \binom{m+r}{r} $ for general $r$. If you think of $r$ as constant while $m$ goes to infinity, the lower bound of $\binom{m}{r}$ is pretty good.
\item If $r = a(q-1)+b$ where $b < q$, then $\delta = q^{-a}\cdot \left(1-\frac{b}{q}\right)$.
\end{itemize}
An explanation of for the values of $r$ and $\delta$ can be found in the scribe notes of lecture $5$. Let's now look at some examples, which we generate by plugging in choice values into the parameters of the Reed Muller codes.
\begin{example} Linear Polynomials ($r = 1$). \end{example}
\begin{itemize}
\item $n= q^m$
\item $k= m+1$
\item $\delta = 1 - \frac{1}{q}$
\item Number of codewords = $q^{m+1} = q\cdot n$
\end{itemize}
In the special case when $q = 2$, we have $\delta = \frac{1}{2}$. This is exactly the same construction as the Hadamard Code. Since the Reed Muller encodes messages as linear polynomials, we can write each such polynomial $f$ as $\sum_{i=1}^m a_i x_i +a_0$, where $a_i$ are constants and the $x_i$'s are the $m$ variables in the Reed Muller code.
We encode $f$ by evaluating it at all points $\{\alpha_1, \alpha_2, \ldots \alpha_m\}, \alpha_i \in \mathbb{F}_2$. Then the encoding is
$\sum_{i=1}^m a_i\alpha_i + a_0$ evaluated at all $\alpha_1, \alpha_2, \ldots \alpha_m \in \mathbb{F}_2^m$
Let's look at another example.
\begin{example} Bivariate polynomials \end{example}
\noindent \textbf{Parameters}: We establish that $m=2, r = \frac{q}{2}$. Then
\begin{itemize}
\item $n = q^2$
\item $k = \binom{m+r}{r} = \binom {\frac{q}{2}+2}{2} \sim \frac{q^2}{8} = \frac{n}{8}$
\item $R = \frac{k}{n} = \frac{1}{8}$
\item If $q = \sqrt{n}$, then $\delta = \frac{1}{2}$.
\end{itemize}
This example demonstrates the tradeoff between rate and distance versus alphabet size. In this example, our alphabet size is $\sqrt{n}$, which is much smaller than $n$, the minimum alphabet size required for Reed Solomon code (which is the Reed Muller code for single variate polynomials): Reed Solomon obtains the bounds $\frac{1}{2}$ and $\frac{1}{2}$ for $R$ and $\delta$ respectively, instead of $\frac{1}{8}$ and $\frac{1}{2}$. But $q$ would be at least $n$ in Reed Solomon as opposed to $\sqrt{n}$ in this example.
Because the alphabet of the codes are finite fields, and it is a reasonable problem to ask how one might construct large finite fields, the size of the alphabet is a relevant consideration in coding theory. (Maybe).
Now let's look at an example that is of significant interest in computational complexity theory.
\begin{example} Let $m = \frac{\log n}{\log \log n}, q = \log^2 n, r = \frac{1}{2} \log^2 n$ \end{example} (Example analysis incomplete)
Then
\begin{itemize}
\item $\delta = \frac{1}{2}$
\item $q = \log^3 n$.
\end{itemize}
The rate goes to $0$, but we're interested in seeing how quickly it goes to $0$. Note that $k \geq n^{1/3}$. But how should we precisely bound $k$? We would say $k \geq \left(\frac{r}{m}\right)^m = \left(\log n \right)^{\frac{\log n}{\log \log n}}$.
$n = q^m$, and so $k \geq \Omega\left(n^{1/2}\right)$
Moral of the story:
\begin{itemize}
\item $\delta = 1/2$ (which is really good), $|\Sigma|$ = polylog$(n)$.
\item $k$ vs $n$ relationship is polynomial.
\end{itemize}
(Place picture here with R and $\delta$ on the axes: Gilbert Varshamov bound, for $q = 2$).
\section{Duals of (Linear) Error Correcting Codes}
If $C = [n, k, d]_q$ code over $\mathbb{F}_q$, the \textbf{dual} of the code is the set
$$C^{\perp} = \{x \in \mathbb{F}_q^n | \forall y \in C, \langle x, y \rangle = 0 \}$$
where $\langle x, y \rangle$ is the standard dot product.
Because $C^\perp$ is the space of elements perpendicular to $C$, the dimension of $C^\perp$ is $n-k$. Thus $C^{\perp} = [n, n-k, d]_q$, where we have not said anything about $d$ yet.
\begin{lemma} If $G$ is the generator matrix for $C$ and $H$ is the parity check matrix, then $G^T$ is the parity check matrix for $C^\perp$ and $H^T$ is the generator matrix. \end{lemma}
\begin{proof} Let $x$ be an element of our message space. We note that the space spanned by $xH^T$ has the right number of dimensions to be a candidate for the space $C^\perp$, and $H^TG^T=(GH)^T=0$. It remains to show that $\langle xH^T$ and $x'G$ are perpendicular for all $x, x'$ in the message space.
\noindent However,
$$\langle xH^T x'G \rangle = xH^TG^Tx'=x(GH)^Tx' = 0$$ completing the proof of our lemma.
\end{proof}
Now we would like to figure out the distance $d$ in the dual code of $C$. Let's examine a few examples and their duals to try and figure this out.
\begin{example} Reed Solomon Code \end{example}
The Reed Solomon code is a \textit{Maximal Distance Separable (MDS) code}, meaning that the singleton bound is tight. Recall that the Singleton bound states that $A_q(n,d) \leq q^{n-d+1}$ where $A_q(n,d)$ is the number of codewords in an $\mathbb{F}_q$ \textit{block code} of length $n$ with minimum distance $d$.
\begin{lemma} The dual of Linear MDS code is MDS. \end{lemma}
\begin{proof}
Suppose $C$ is a code with generator matrix $G$ with columns $c_1, c_2, \ldots c_n$. This is a $k$ by $n$ matrix. Note that in an MDS code, every linear combination of the rows has Hamming weight at least $n-k+1$.
By lemma $4$, $C^{\perp}$ has $G^T$ as its parity check matrix. We wish to show now that if $C = [n, k, n-k+1]$ code, then $C^{\perp} = [n, n-k+1, k+1]$ code. That is, every subset of $k$ columns of $G$, the generator matrix, is linearly independent. The proof is as follows:
\begin{proof} Suppose that some $k$ columns are linearly dependent. Consider the $k$ by $k$ submatrix $M$ formed by these columns. Since the columns are linearly dependent, the rank of $M$ is less than $k$ so the rows of $M$ have some linearly dependence. Therefore there exists some linear combination of the rows of $M$ that sums to $0$, so we can use this same linear combination on the rows of $G$ whose sum has at least $k$ 0's, and thus has Hamming weight $\leq n-k$. But we've established that any linear combination of the rows of $G$ in an MDS code must have Hamming weight at least $n-k+1$. Contradiction.
\end{proof}
We've shown that the dual of an $[n, k, n-k+1]_q$ code is an $[n, n-k+1, k+1]_q$ code, which is MDS as desired.
\end{proof}
However, it turns out the dual of Reed Solomon codes are still Reed Solomon codes, so we do not get any new codes from taking the dual of a Reed Solomon code.
Now let's turn our attention to the dual of Reed Muller codes.
\begin{lemma} The dual of a Reed Muller Code is Reed-Muller. \end{lemma}
If we have a Reed Muller code in the primal with $\mathbb{F}_q, m, r$, the dual of the code has the same alphabet $\mathbb{F}_q$, the number of variables will remain $m$. In the initial Reed Muller code, we took the monomials of maximum degree $r$. If Reed Muller code $C$ is generated by all monomials of degree $< r$, then we conjecture that $C^\perp$ is generated by the set of monomials with degree $< m(q-1)-r$. We leave it as an exercise to verify that the sum of the dimensions of $C$ and our candidate $C^\perp$ is indeed $q^m$.
Before we prove this conjecture, let's look at a picture.
.................
(Incomplete section)
Suppose $r = \frac{3}{2}q$. Let's look at all the integer degree monomials we could have.
(Picture, bivariate polynomials, plotting the permissable exponents of $x$ and $y$. We look at the area of the square in the graph. The area of the dual correpsonds to the complement of the primal in the picture).
.................
Now let's go back to our proof that the dual of a Reed Muller code $C$ is Reed Muller, and in fact this dual is generated by the set of monomials with degree $< m(q-1)-r$. To do this, we must first prove a property of finite fields. Namely, summing a non-zero monomial in $m$ variables with degree less than $m(q-1)$ over all possible values $\mathbb{F}_q^m$ gives $0$. We leave it as an exercise to show that it suffices to prove the next claim.
\subsection{Some Properties of Finite Fields}
\begin{claim} If $P, Q \in \mathbb{F}_q[x]$ and deg$(P)$ + deg $(Q) < q-1$. Then $\sum_{\alpha \in \mathbb{F}_q} P(\alpha)\cdot Q(\alpha) = 0$ (in $\mathbb{F}_q$). \end{claim}
\begin{proof} Note: all equalities in the proof are for $\mathbb{F}_q$.
We can expand $P(x)Q(x)$ as the sum of monomials with degrees less than $q-1$. Therefore if we can show that $\sum_{\alpha \in \mathbb{F}_q} x^n = 0$ for all $n < q-1$, then adding some combination of these proves our claim.
\begin{lemma} $\sum_{\alpha \in \mathbb{F}_q} x^n = 0$ when $n < q-1$. \end{lemma}
\begin{proof} Let $\alpha_1, \alpha_2, \ldots \alpha_q$ be all the elements in $F_q$. Because $\mathbb{F}$ is a field (and thus has inverses), we can show without too much difficulty that for any $\beta \in \mathbb{F}_q$ that $\beta \alpha_1, \beta\alpha_2, \ldots \beta\alpha_n$ is a permutation of $\alpha_1, \ldots \alpha_n$ for any $\beta \in \mathbb{F}_q$. Namely, this is true when $\beta$ is a primitive root of $\mathbb{F}_q$, meaning that $\beta^x = 0 \Leftrightarrow x \equiv 0 \pmod {q-1}$. (The existence of primitive roots is a well-known property of finite fields, and is asserted here without proof).
Since $\beta \alpha_1, \beta\alpha_2, \ldots \beta\alpha_n$ is a permutation of $\alpha_1, \ldots \alpha_n$ for any $\beta \in \mathbb{F}_q$, then
$$\sum_{\alpha \in \mathbb{F}_q} (\beta\alpha)^n= \sum_{\alpha \in \mathbb{F}_q} \alpha^n$$
$$\Rightarrow \sum_{\alpha \in \mathbb{F}_q} (\beta^n-1)\alpha^n= 0$$
Since $n < q-1$, then $\beta^n \not= 1$ and thus $\beta^n-1 \not=0$. Therefore $\sum_{\alpha \in \mathbb{F}_q}\alpha^n = 0$ as desired.
\end{proof}
The lemma is proven, and therefore our initial claim is proven as well.
\end{proof}
Additionally, $\sum_{i=0}^{q-2} \alpha^i = 0$ if $\alpha \not=1$. This comes from noting that $\sum_{i=0}^{q-2} \alpha^i = \frac{\alpha^{q-1}-1}{\alpha-1}$ for $\alpha \not= 1 $, and it is a well known fact of finite fields that any $\alpha\not=0 \in F_{q}$ satisfies $\alpha^{q-1} - 1 = 0$.
\subsection{Return to Proof that Dual of Reed Muller is Reed Muller}
Recall that the generator matrix $G$ for a Reed Muller code with parameterse $m$ and $r$ has columns corresponding to elements of $F_q^m$ representing each possible input into our message (written as coefficients of a polynomial), rows corresponding to a monomial of degree $< r$, and entries corresponding to the valuation of the elements of $F_q^m$ corresponding to the column evaluated on the $m$-variate monomial of degree $< r$ corresponding to the rows.
We assert that a valid generator matrix $G^\perp$ for $C^\perp$ consists of the same construction but with each row corresponding to monomials of degree $< m(q-1)-r$. The dimensions are correct, so from lemma $4$, we only need to check that $G\left(G^\perp\right)^T = 0$. However, each entry of $G\left(G^\perp\right)^T$ is a sum of some monomial of degree $