\documentclass[12pt]{article} \usepackage{amssymb} \usepackage{amsmath} \usepackage{multicol} \usepackage{hyperref} \newtheorem{definition}{Definition} \newtheorem{lemma}{Lemma} \newtheorem{example}{Example} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{remark}{Remark} \def\ppp{{\mathbb{P}}} \def\aaa{{\mathbb{A}}} \def\fff{{\mathbb{F}}} \def\eee{{\mathbb{E}}} \def\qqq{\mathbb{Q}} \def\rrr{\mathbb{R}} \def\ccc{\mathbb{C}} \def\zzz{\mathbb{Z}} \def\nnn{\mathbb{N}} \def\pf{{\bf proof}:\ } \def\qed{$\Box$} \def\wt{{\rm{wt}}} \def\div{{\rm{div}}} \def\deg{{\rm{deg}}} \def\Div{{\rm{Div}}} \def\supp{{\rm{supp}}} \def\eval{{\rm{eval}}} \def\Aut{{\rm{Aut}}} \oddsidemargin -.25in \textwidth 6.75in \topmargin -.5in \textheight 9in \begin{document} \title{Introduction to codes\\ from a representation-theoretic perspective} \author{David Joyner\thanks{Math. Dept, USNA, wdj@usna.edu. I'd like to thank the Harvey Mudd Mathematics Department, especially Mike Orrison, for their hospitality.}} \date{5-12-2005} \maketitle This expository paper deals with some selected topics belonging to the intersection of the theory of error-correcting codes and the representation theory of finite groups. We shall see that codes which exhibit unusual symmetry often times turn out to be very interesting objects of study. Notes of lectures given to undergraduate math majors at Harvey Mudd College, May 2005. \tableofcontents \section{Lecture 1: Codes and groups} Let $\fff$ denote a finite field. Since codes are vector spaces over finite fields, some very brief facts about finite fields will be recalled first. \subsection{Finite fields} We introduce some terminology and background about finite fields. For details, see for example \cite{MS}. The {\bf prime fields}: If $p\geq 2$ is a prime then $GF(p)$ denotes the field $\zzz/p\zzz$ with addition and multiplication performed mod $p$. The {\bf prime power fields}: Suppose $q=p^r$ is a prime power, $r>1$, and put $\fff=GF(p)$. Let $\fff[x]$ denote the ring of all polynomials over $\fff$ and let $f(x)$ denote a monic irreducible polynomial in $\fff[x]$ of degree $r$. The quotient $\eee = \fff[x]/(f(x))= \fff[x]/f(x)\fff[x]$ is a field with $q$ elements. One may think of $\fff[x]$ as an analog of $\zzz$, $f(x)$ as an analog of a prime $p$, and $\fff[x]/f(x)\fff[x]$ as an analog of $\zzz/p\zzz$. If $f(x)$ and $\eee$ are related in this way, we say that $f(x)$ is the {\bf defining polynomial} of $\eee$. Any defining polynomial factors completely into distinct linear factors over the field it defines. All finite fields arise from one of the above two constructions. Up to isomorphism, there is only one field of order $q=p^r$,$r\geq 1$, denoted $GF(q)$. (Here ``GF'' stands for Galois field, named after the French mathematician E. Galois who died after a sword fight at the age of 23 ... .) For any finite field $\fff$, the multiplicative group of non-zero elements $\fff^\times$ is a cyclic group. An $\alpha\in \fff$ is called a {\bf primitive element} if it is a generator of $\fff^\times$. A defining polynomial $f(x)$ of $\fff$ is said to be {\bf primitive} if it has a root in $\fff$ which is a primitive element. \subsubsection{Matrix representation} Let $\mathbb{E}$ denote a field extension of the finite field $\mathbb{F}$. Each element of $\mathbb{E}$ may be represented as an invertible matrix with entries in $\mathbb{F}$. Here's how. Let $\alpha\in\mathbb{E}$ denote a generator of the cyclic group $\mathbb{E}^\times$. Let $f(x)$ denote the minimal polynomial of $\alpha$ (the lowest degree monic polynomial in $\fff[x]$ which has $\alpha$ as a root). Take the matrix associated to $\alpha$, denoted $A$, to be the companion matrix of $f(x)$ (so the characteristic polynomial of $A$ is $f$). If the degree of $f(x)$ is $m$, then $A$ is an $m\times m$ matrix with coefficients in $\mathbb{F}$ (and the degree of $\mathbb{E}/\mathbb{F}$ is $m$). If $\beta\in\mathbb{E}$ denotes any other non-zero element, then we can write $\beta=\alpha^i$, for some $i$ (because $\mathbb{E}^\times$ is a cyclic group). Take the matrix associated to $\beta$ to be $B=A^i$. The matrix associated to $0\in\mathbb{E}$ will be the $m\times m$ zero matrix. Therefore, there is a representation \[ \rho:\eee^\times \rightarrow \Aut_\fff (\fff^m) \] induced by this action of the field $\eee$ acting on itself, regarded as (an $\fff$-vector space identified with) $\fff^m$. \begin{example} Taking $\fff=GF(2)$ and $\eee=GF(16)$ with defining polynomial $f(x)=x^4+x^3+1$, we can represent the non-zero elements of $GF(16)$ as the following $15$ matrices: {\tiny{ \[ \left[ \begin {array}{cccc} 0&0&0&1\\ \noalign{\medskip}1&0&0&0\\ \noalign{\medskip}0&1&0&0\\ \noalign{\medskip}0&0&1&1 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 0&0&1&1\\ \noalign{\medskip}0&0&0&1\\ \noalign{\medskip}1&0&0&0\\ \noalign{\medskip}0&1&1&1 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 0&1&1&1\\ \noalign{\medskip}0&0&1&1\\ \noalign{\medskip}0&0&0&1\\ \noalign{\medskip}1&1&1&1 \end {array} \right], \left[ \begin {array}{cccc} 1&1&1&1\\ \noalign{\medskip}0&1&1&1\\ \noalign{\medskip}0&0&1&1\\ \noalign{\medskip}1&1&1&0 \end {array} \right], \] \[ \left[ \begin {array}{cccc} 1&1&1&0\\ \noalign{\medskip}1&1&1&1\\ \noalign{\medskip}0&1&1&1\\ \noalign{\medskip}1&1&0&1 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 1&1&0&1\\ \noalign{\medskip}1&1&1&0\\ \noalign{\medskip}1&1&1&1\\ \noalign{\medskip}1&0&1&0 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 1&0&1&0\\ \noalign{\medskip}1&1&0&1\\ \noalign{\medskip}1&1&1&0\\ \noalign{\medskip}0&1&0&1 \end {array} \right], \left[ \begin {array}{cccc} 0&1&0&1\\ \noalign{\medskip}1&0&1&1\\ \noalign{\medskip}0&1&0&1\\ \noalign{\medskip}1&1&0&0 \end {array} \right],\ \ \ \] \[ \left[ \begin {array}{cccc} 1&1&0&0\\ \noalign{\medskip}0&1&1&0\\ \noalign{\medskip}1&0&1&1\\ \noalign{\medskip}1&0&0&1 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 1&0&0&1\\ \noalign{\medskip}1&1&0&0\\ \noalign{\medskip}0&1&1&0\\ \noalign{\medskip}0&0&1&0 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 0&0&1&0\\ \noalign{\medskip}1&0&0&1\\ \noalign{\medskip}1&1&0&0\\ \noalign{\medskip}0&1&0&0 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 0&1&0&0\\ \noalign{\medskip}0&0&1&0\\ \noalign{\medskip}1&0&0&1\\ \noalign{\medskip}1&0&0&0 \end {array} \right],\ \ \ \left[ \begin {array}{cccc} 1&0&0&0\\ \noalign{\medskip}0&1&0&0\\ \noalign{\medskip}0&0&1&0\\ \noalign{\medskip}0&0&0&1 \end {array} \right] . \] }} Of course, matrix addition and multiplication corresponds to addition and multiplication of the corresponding field elements. \end{example} \subsubsection{Conway polynomials} There is no canonical choice of $GF(q)$ but there is a ``good'' choice: take $f(x)$ to be the Conway polynomial over $GF(p)$ of degree $r$. This is the default finite field constructed by GAP and MAGMA. We reproduce the definition on Frank Luebeck's Conway polynomials web page \cite{Lu}, which we refer to for further details and references. A standard notation for the elements is given via the representatives $0, ..., p-1$ of the cosets modulo $p$. We order these elements by $0 < 1 < 2 < ... < p-1$. We introduce an ordering of the polynomials of degree $r$ over $GF(p)$. Let $g(x) = g_rx^r + ... + g_0$ and $h(x) = h_rx^r + ... + h_0$ (by convention, $g_i=h_i=0$ for $i>r$). Then we define $g < h$ if and only if there is an index $k$ with $g_i = h_i$ for $i > k$ and $(-1)^{r-k} g_k < (-1)^{r-k} h_k$. The {\bf Conway polynomial} $f_{p,r}(x)$ for $GF(p^r)$ is the smallest polynomial of degree $r$ with respect to this ordering such that: \begin{itemize} \item $f_{p,r}(x)$ is monic, \item $f_{p,r}(x)$ is primitive, that is, any zero is a generator of the (cyclic) multiplicative group of $GF(p^r)$, \item for each proper divisor $m$ of $r$ we have that $f_{p,m}(x^{(p^r-1) / (p^m-1)}) \equiv 0 \pmod{f_{p,r}(x)}$; that is, the $(p^r-1) / (p^m-1)$-th power of a zero of $f_{p,r}(x)$ is a zero of $f_{p,m}(x)$. \end{itemize} These polynomials are not easy to compute but the fields $\fff_1,\fff_2,...$ constructed from a sequence \[ f_{p,r_1},\ f_{p,r_2},\ f_{p,r_3}, ...\ \ \ {\rm with}\ \ \ r_i|r_{i+1}, \] have ``nice'' embedding properties. Sounds complicated but actually these fields are very easy to deal with using \cite{GAP} or GUAVA, GAP's error-correcting codes package \cite{G1} (see the online GUAVA manual or \cite{G2} for examples). \subsection{Linear codes: generalities} The theory of error-correcting codes was originated by Hamming in the late 1940's, a mathematician who worked for Bell Telephone. Some of his codes actually arose earlier in various isolated connections - for example, statistical design theory and in soccer betting(!). Hamming's motivation was to program a computer to correct ``bugs'' which arose in punch-card programs. The overall goal behind the theory of error-correcting codes is to reliably enable digital communication. A {\bf (linear error-correcting) code $C$ of length $n$ over $\fff$} is a vector subspace of $\fff^n$ and its elements are called {\bf codewords}. (When $\fff=GF(2)$ it is called a {\bf binary} code. These are the most important codes from the practical point of view.) Think of the following scenario: You are sending an $n$-vector of $0$'s and $1$'s (the codeword) across a noisy channel to your friend. Your friend gets a corrupted version (the received word differs from the codeword in a certain number of error positions). Depending on how the code $C$ was constructed and the number of errors made, it is possible that the original codeword can be recovered. This raises the natural question: given $C$, how many errors can be corrected? Stay tuned... A code of length $n$ and dimension $k$ (as a vector space over $\fff$) is called an {\bf $[n,k]$-code}. In abstract terms, an $[n,k]$-code is given by a short exact sequence \begin{equation} \label{eqn:1} 0 \rightarrow \fff^k \stackrel{G}{\rightarrow} \fff^n \stackrel{H}{\rightarrow} \fff^{n-k} \rightarrow 0. \end{equation} (``Short exact'' means (1) the arrow $G$ is injective, i.e., $G$ is a full-rank $k\times n$ matrix, (2) the arrow $H$ is surjective, and (3) ${\rm image}(G)={\rm kernel}(H)$.) We identify $C$ with the image of $G$. The function \[ G:\fff^k\rightarrow C, \] \[ \vec{m}\longmapsto \vec{m}G, \] is called the {\bf encoder}. Since the sequence (\ref{eqn:1}) is exact, a vector $\vec{v}\in \fff^n$ is a codeword if and only if $H(\vec{v})=0$. If $\fff^n$ is given the usual standard vector space basis then the matrix of $G$ is a {\bf generating matrix} of $C$ and the matrix of $H$ is a {\bf check matrix} of $C$. In other words, \[ \begin{array}{ll} C&=\{\vec{c}\ |\ \vec{c}=\vec{m}G,\ {\rm some}\ \vec{m}\in \fff^k\}\\ &=\{\vec{c}\in \fff^n\ |\ H\vec{c}=\vec{0}\}. \end{array} \] When $G$ has the block matrix form \[ G=(I_k\ |\ A), \] where $I_k$ denotes the $k\times k$ idenity matrix and $A$ is some $k\times (n-k)$ matrix, then we say $G$ is in {\bf standard form}. By abuse of terminology, if this is the case then we say $C$ is in {\bf standard form}. The matrix $G$ has rank $k$, so the row-reduced echelon form of $G$, call it $G'$, has no rows equal to the zero vector. In fact, the standard basis vectors $\vec{e}_1$, ..., $\vec{e}_k$ of the column space $\fff^k$ occur amongst $k$ columns of those of $G'$. The corresponding coordinates of $C$ are called the {\bf information coordinates} (or information bits, if $C$ is binary) of $C$. {\footnotesize{ Aside: For a ``random'' $k\times k$ matrix with {\bf real} entries, the ``probability'' that its rank is $k$ is of course $1$. This is because ``generically'' a square matrix with real entries is invertible. In the case of finite fields, this is not the case. For example, the probability that a ``large random'' $k\times k$ matrix with entries in $GF(2)$ is invertible is \[ \lim_{k\rightarrow \infty} \frac{(2^k-1)(2^k-2)...(2^k-2^{k-1})}{2^{k^2}} =\prod_{i=1}^\infty (1-2^{-i}) =0.288...\ . \] For more interesting facts like these, see Lecture 7 in A. Barg's EENEE 739C course (online \cite{Ba}). }} The {\bf Hamming metric} is the function \[ d:\fff^n\times \fff^n\rightarrow \rrr, \] \[ d(\vec{v},\vec{w})=|\{i\ |\ v_i\not= w_i\}|=d(\vec{v}-\vec{w},\vec{0}). \] The {\bf Hamming weight} of a vector is simply its distance from the origin: \[ \wt(\vec{v})=d(\vec{v},\vec{0}). \] {\small {\bf Question}: How many vectors belong to the ``shell' of radius $r$ about the origin $\vec{0}\in GF(q)^r$? {\bf Answer}: $\left( \begin{array}{c} n\\ r \end{array} \right) (q-1)^r$. Think about it! (Hint: ``distance $r$'' means that there are exactly $r$ non-zero coordinates. The binomial coefficient describes the number of ways to choose these $r$ coordinates.) } The {\bf minimum distance of $C$} is defined to be the number \[ d(C)=\min_{\vec{c}\not=\vec{0}} d(\vec{c},\vec{0}). \] (It is not hard to see that this is equal to the closest distance between any two distinct codewords in $C$.) An $[n,k]$-code with minimum distance $d$ is called an {\bf $[n,k,d]$-code}. \begin{quotation} {\bf Cyclic construction} Let $G$ denote the cyclic group of order $n$. Let $p$ denote a prime for which the finite field $\fff=GF(p)$ contains a primitive $n$-th root of unity. Assume that $G$ acts on $\fff^n$ by cyclically permuting the coordinates. Pick a non-zero vector $\vec{a}\in \fff^n$. Let $C\subset \fff^n$ denote the vector space spanned by the cyclic permutations $g\vec{a}$, $g\in G$. In general, there seems to be no easy way to determine the minimum distance $d=d(C)$ from $\vec{a}$ and $G$. Let $G^*=\{\chi_1,...,\chi_n\}$ denote the dual group of $G$, where $\chi_i:G\rightarrow \fff^\times$. (Since $p$ is a prime for which $\fff$ contains all the $n$-th roots of unity, there are $n$ such characters.) The vector space $C$ is $G$-invariant, by definition, so \[ C\cong m_1\fff[\chi_1]\oplus ...\oplus m_n\fff[\chi_n], \] as $G$-modules, where $m_i\geq 0$ is the multiplicity of the $i$-th character. This is analogous to the fact that any ``nice'' complex-valued periodic function can be expanded in a Fourier series using powers of a complex exponential function. As far as I know, there is no easy way to determine the minimum distance $d=d(C)$ from the characters $\chi_i$'s and the ``Fourier coefficients'' $m_i$'s. \begin{example} Take $\fff=GF(11)$, which contains all the $5$-th roots of unity. Let $\alpha\in \fff$ denote a $5$-th root of unity (for example, take $\alpha=4$). Let $\sigma:\fff^5\rightarrow \fff^5$ denote the cyclic shift sending $(a,b,c,d,e)\longmapsto (b,c,d,e,a)$ and let $G=\langle \sigma\rangle$. The $\fff$-valued dual group of $G$, denoted $G^*$, is the set of functions $\chi_i=\chi^i$, where $\chi:G\rightarrow \fff^\times$ is defined by \[ \chi(\sigma^i)=\alpha^i,\ \ \ 0\leq i\leq |G|-1. \] Let $\vec{c}=(1,0,2,0,3)\in \fff^5$ and let $G$ denote the $4\times 5$ matrix whose rows are the cyclic shifts of $\vec{c}$. The row-reduced echelon form of $G$ is \[ \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 5\\ 0 & 1 & 0 & 0 & 3\\ 0 & 0 & 1 & 0 & 10\\ 0 & 0 & 0 & 1 & 3 \end{array} \right), \] so the code $C$ whose generator matrix is $G$ is a cyclic $[5,4,2]$-code over $GF(11)$. How does this code decompose as a $G$-module? First, we must determine $G$-invariant basis vectors. To this end, let \[ \begin{array}{l} \vec{w}_1=\vec{c}+\sigma(\vec{c})+\sigma^2(\vec{c})+\sigma^3(\vec{c})+\sigma^4(\vec{c}),\\ \vec{w}_2=\vec{c}+\alpha\sigma(\vec{c})+\alpha^2\sigma^2(\vec{c})+ \alpha^3\sigma^3(\vec{c})+\alpha^4\sigma^4(\vec{c}),\\ \vec{w}_3=\vec{c}+\alpha^2\sigma(\vec{c})+\alpha^4\sigma^2(\vec{c})+ \alpha^6\sigma^3(\vec{c})+\alpha^8\sigma^4(\vec{c}),\\ \vec{w}_4=\vec{c}+\alpha^3\sigma(\vec{c})+\alpha^6\sigma^2(\vec{c})+ \alpha^9\sigma^3(\vec{c})+\alpha^{12}\sigma^4(\vec{c}). \end{array} \] (Since $\alpha^5=1$ some of these exponents can be reduced if desired.) Note that $\sigma(\vec{w}_1)=\vec{w}_1$, $\sigma(\vec{w}_2)=\alpha^4\vec{w}_2$, $\sigma(\vec{w}_3)=\alpha^3\vec{w}_3$, and $\sigma(\vec{w}_4)=\alpha^2\vec{w}_4$. Therefore, these form a $G$-invariant basis and we have \[ C\cong \fff[\chi_0]\oplus\fff[\chi_1] \oplus\fff[\chi_2]\oplus\fff[\chi_3]\oplus\fff[\chi_4]. \] In this case, every representation of $G$ occurs in $C$, each with multiplicity one. \end{example} \end{quotation} \begin{lemma} (Singleton bound) Every linear $[n,k,d]$ code $C$ satisfies \[ k+d\leq n+1. \] \end{lemma} Note: this bound does not depend on the size of $\fff$. A code $C$ whose parameters satisfy $k+d=n+1$ is called {\bf maximum distance separable} or {\bf MDS}. Such codes, when they exist, are in some sense best possible. \pf Fix a basis of $\fff_q^n$ and write all the codewords in this basis. Delete the first $d-1$ coordinates in each code word. Call this new code $C'$. Since $C$ has minimum distance $d$, these codewords of $C'$ are still distinct. There are therefore $q^k$ of them. But there cannot be more than $q^{n-d+1}=|\fff_q^{n-d+1}|$ of them. This gives the inequality. \qed The {\bf rate} of the code is $R=k/n$ - this measures how much information the code can transmit. The {\bf relative minimum distance} of the code is $\delta =d/n$ - this is directly related to how many errors can be corrected. \begin{lemma} If $\vec{v}\in \fff^n$ is arbitrary and $0[\frac{d-1}{2}]$, by the above lemma. \begin{definition} We say that a linear $C$ is {\bf $t$-error correcting} if $|B_t(\vec{w})\cap C|\leq 1$. \end{definition} Note that $t\leq [\frac{d-1}{2}]$ if and only if $d\geq 2t+1$. The general goal in the theory is to optimize the following properties: \begin{itemize} \item the rate, $R=k/n$, \item the relative minimum distance, $\delta = d/n$, \item the speed at which a ``good'' encoder for the code can be implemented, \item the speed at which a ``good'' decoder for the code can be implemented. \end{itemize} There are (sometimes very technical) constraints on which these can be achieved, as we have seen with the Singleton bound and the sphere-packing bounds. \subsection{Linear codes: examples} We shall consider as an example one of the first codes constructed - one of an infinite family of codes called Hammming codes. {\bf The Hamming $[7,4,3]$ binary code}: Let $\fff=GF(2)$. The code $C$ in this example has check matrix defined by \[ H= \left( \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \end{array} \right) (\vec{H}_1,\vec{H}_12,...,\vec{H}_7) = \left( \begin{array}{c} \vec{h}_1\\ \vec{h}_2\\ \vec{h}_3 \end{array} \right) \] and generator matrix by \[ G= \left( \begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{array} \right) = \left( \begin{array}{c} \vec{g}_1\\ \vec{g}_2\\ \vec{g}_3 \\ \vec{g}_4 \end{array} \right). \] This code $C$ is the $GF(2)$-linear span of the rows $\vec{g}_1,\vec{g}_2,\vec{g}_3,\vec{g}_4$ of $G$. Now try the following experiment: have a friend secretly pick $c_1,c_2,c_3,c_4\in \fff$, compute $\vec{c} =c_1\vec{g}_1+c_2\vec{g}_2+c_3\vec{g}_3+c_4\vec{g}_4\in C\subset GF(2)^7$, and tell you the $7$ bits of $\vec{c}$, lying once. Suppose that they tell you $\vec{v}=(v_1,v_2,...,v_7)$. You can not only determine when they lied to you, but what the ``secret'' values $c_1,c_2,c_3,c_4\in \fff$ are. Magic? No, but it is a neat trick. Here are 2 ways to do it. \begin{itemize} \item[Idea 1] (Syndromes): Compute the vector $\vec{s}=H\vec{v}$ (this vector is called a ``syndrome''). Since the columns of $H$ consist of all possible non-zero 3-tuples of $0$'s and $1$'s, if $\vec{s}$ is non-zero then it must be one of the columsn of $H$, say the $i^{th}$ one. The vector $\vec{c}$ is the same as $\vec{v}$ but with the $i^{th}$ bit flipped. Moreover, the first 4 coordinates of $\vec{c}$ are the ``secret'' values $c_1,c_2,c_3,c_4\in \fff$. {\small{ Why does this work? First, if $\vec{c}\in C$ then, by definition of $H$, we must have $H\vec{c}=\vec{0}$. Let $\vec{H}_1,\vec{H}_2,...,\vec{H}_7$ denote the seven columns of $H$ and let $\vec{e}_1,\vec{e}_2,...,\vec{e}_7$ denote the standard basis vectors of $\fff^7$. Note that \[ H\vec{v}=H(\vec{c}+\vec{e}_i)=H\vec{c}+H\vec{e}_i=\vec{0}+\vec{H}_i, \] for each $1\leq i\leq 7$. Since your friend lied in exactly one place, the column number of the syndrome is the place where the lie was made. }} {\bf Natural questions}: \begin{itemize} \item[(a)] How does this construction generalize? Does this decoder generalize? \item[(b)] Are there any ``better'' one error-correcting codes? \item[(c)] Are there analogous two error-correcting codes? \end{itemize} Hamming constructed a more general family of one error-correcting binary codes of length $n=2^r-1$, $r=2,3,4,...$. The example above is the case $r=3$. The decoder generalizes as well. There are no better one error-correcting codes. To some people, the ``two error-correcting BCH codes'' \cite{MS} are the analogs of these Hamming codes. However, what family of linear two error-correcting codes have the best paramaters is still an open question in general. \item[Idea 2] (Tanner graphs): Construct the bipartite graph $\Gamma$ whose vertices $V$ are labeled by the coordinates of the code (so $|V|=n$) and whose edges are labeled by the rows $\vec{h}_i$ of a check matrix $H$ of $C$ (so $|E|=n-k$). In the above example, it is this following graph: \vskip .5in \begin{center} \begin{picture}(200,200) \put(0,200){\circle{22}} \put(-4,198){$x_5$} \put(28,147){$\vec{h}_1$} \put(162,147){$\vec{h}_2$} \put(112,42){$\vec{h}_3$} \put(100,200){\circle{22}} \put(96,198){$x_4$} \put(200,200){\circle{22}} \put(196,198){$x_6$} \put(0,100){\circle{22}} \put(-4,98){$x_3$} \put(100,100){\circle{22}} \put(96,98){$x_1$} \put(200,100){\circle{22}} \put(196,98){$x_2$} \put(100,10){\circle{22}} \put(96,8){$x_7$} \put(100,50){\circle*{10}} \put(100,50){\line(2,1){90}} \put(100,50){\line(0,-1){28}} \put(100,50){\line(-2,1){90}} \put(100,50){\line(0,1){38}} \put(150,150){\circle*{10}} \put(150,150){\line(1,1){42}} \put(150,150){\line(1,-1){42}} \put(150,150){\line(-1,1){42}} \put(150,150){\line(-1,-1){42}} \put(50,150){\circle*{10}} \put(50,150){\line(1,1){42}} \put(50,150){\line(1,-1){42}} \put(50,150){\line(-1,1){42}} \put(50,150){\line(-1,-1){42}} \end{picture} \end{center} The check equations correspond to the solid black vertices, the coordinates of the codes to the labeled vertices, and the edges correspond to the terms occurring in the parity check equation. This is called a ``Tanner graph'' (\cite{Ta}, \S B). For each check vertex, add up the incident coordinate vertices $\pmod 2$. The error position is determined by the following table: \begin{center} \begin{tabular}{|c|c|}\hline parity failure region(s) & error position \\ \hline none & none \\ $\vec{h}_1$, $\vec{h}_2$, $\vec{h}_3$ & 1 \\ $\vec{h}_2$, $\vec{h}_3$ & 2 \\ $\vec{h}_1$, $\vec{h}_3$ & 3 \\ $\vec{h}_1$, $\vec{h}_2$ & 4\\ $\vec{h}_1$ & 5 \\ $\vec{h}_2$ & 6 \\ $\vec{h}_3$ & 7 \\ \hline \end{tabular} \vskip .1in \end{center} {\bf Natural questions}: \begin{itemize} \item[(a)] Which bipartite graphs arise as a Tanner graph of a binary code? \item[(b)] The theory of bipartite graphs is extensive. Does the theory have useful coding-theoretic implications? %\item[(c)] %Which Tanner graphs have the property that the set of all %check vertices is ``non-deficient'' (see \cite{Ch})? \item[(c)] How does the Tanner graph depend on the choice of the check matrix $H$ for $C$? \end{itemize} See \cite{Ta} for details and references in this direction. See also N. Sloane \cite{S} for some unsolved problems associated with other graph-theoretic connections with coding theory. \end{itemize} \subsection{Linear codes: automorphisms} What is an automorphism of a code? How do you construct a code with a ``large'' number of automorphisms? Can any finite group be realized as the automorphism group of a code? This section will address these questions. To avoid some minor complications, we shall only deal with the simplest case of automorphisms of binary codes. Let $S_n$ denote the symmetric group on $n$ letters. The {\bf (permutation) automorphism group} of a code $C$ of length $n$ is simply the group \[ \Aut(C)=\{\sigma\in S_n \ |\ (c_1,...,c_n)\in C\implies (c_{\sigma(1)},...,c_{\sigma(n)})\in C\}. \] There is a more general definition of the automorphism group of a linear code over $\fff$. In general, (a) the permutation automorphism group is always a subgroup of the full automorphism group, and (b) in the case of a binary linear code the two groups agree. For simplicity, here we only deal with the permutation automorphism group, which, for brevity, we simply call the automorphism group of $C$. If $C_1$ and $C_2$ are two codes of length $n$ and if there is a permutation $\sigma\in S_n$ for which $(c_1,...,c_n)\in C_1$ if and only if $(c_{\sigma(1)},...,c_{\sigma(n)})\in C_2$, then we say $C_1$ and $C_2$ are {\bf permutation equivalent}. This will be written \[ C_1\cong C_2. \] It is a general fact that permutations preserve dimension and minimum distance: if $C_1\cong C_2$ then $\dim(C_1)=\dim(C_2)$ and $d(C_1)=d(C_2)$. Recall that the generator matrix $G$ of an $[n,k,d]$-code has rank $k$, and that the row-reduced echelon form of $G$, call it $G'$, has no rows equal to the zero vector. One immediate consequence of the row-reduction process is that one can permute the columns of $G'$, if necessary, to obtain a matrix of the form \[ G''=(I_k\ |\ A), \] where $I_k$ denotes the $k\times k$ idenity matrix and $A$ is some $k\times (n-k)$ matrix. We have just verified the following result. \begin{lemma} Any linear code is permutation equivalent to a code which is in standard form. \end{lemma} Let $C$ be a code, let $G=\Aut(C)\subset S_n$ denote the (permutation) automorphism group, and let $\Aut_\fff(C)$ denote the automorphism group of $C$ as an $\fff$-vector space. We have a group homomorphism \[ \rho:G\rightarrow \Aut_{\fff}(C)\cong GL_k(\fff), \] defined as follows: an element in $G$ is associated to the linear transformation which permutes the coordinates in the ``obvious way'', \[ \sigma\longmapsto ((c_1,...,c_n)\in C \longmapsto (c_{\sigma^{-1}(1)},...,c_{\sigma^{-1}(n)})\in C). \] Because of this, $C$ is a representation space of $G$. Representation theory raises her head! \subsubsection{Application to decoding} We discuss permutation decoding - a decoding method which only works when you have a group action on the code. Here is an extremely useful lemma. \begin{lemma} Suppose $\vec{v}=\vec{c}+\vec{e}$, where $\vec{c}\in C$ and $\vec{e}\in \fff^n$ is an ``error vector'' with Hamming weight $\wt (e)\leq t$. The information coordinates of $\vec{v}$ are correct if and only if $\wt (H\vec{v})\leq t$. \end{lemma} See \cite{HP}, \S 10.2. Let $G$ denote the permutation automorphism group of $C$. The {\bf permutation decoding algorithm} is: {\small{ {\fontfamily{phv}\selectfont \begin{enumerate} \item Input: A received vector $\vec{v}\in \fff^n$. Output: A codeword $\vec{c}\in C$ closest to $\vec{v}$. \item For each $g\in G$, compute $\wt (H(g\vec{v}))$ until one with $\wt (H(g\vec{v}))\leq t$ is found (if none is found, the algorithm fails). \item Extract the information symbols from $g\vec{v}$, and use $G$ to compute codeword $\vec{c_g}$ from them. \item Return $g^{-1}\vec{c_g}={\rm Decode}(\vec{v})$. \end{enumerate} }}} This is implemented in GUAVA. For example, if $G$ acts transitively then permutation decoding will correct at least one error. The key problem is to find a set of permutations in $G$ which moves the non-zero positions in every possible error vector of weight $\leq t$ out of the information positions. (This set, called a {\bf PD-set}, will be used in step 1 above instead of the entire set $G$.) {\bf Natural questions}: \begin{itemize} \item[(a)] Are there any interesting (useful and practical or ``merely'' mathematically beautiful) examples? \item[(b)] How does $C$ decompose as a $G$-module? \item[(c)] Does its character contain interesting coding-theoretic information? \item[(d)] Is there a permutation list-decoder? \end{itemize} In the next lecture, question (a) is addressed. For (a)-(c), I refer to \cite{JK}. For a basic introduction to list decoding, see \cite{Le}. \section{Lecture 2: Quadratic residue codes and other group codes} In this lecture, we give several group-theoretical constructions which lead to codes having lots of extra symmetry. \subsection{Cyclic codes revisited} One of the simplest ``group codes'' is the family of cyclic groups, introduced in a very naive way in the last lecture. Here we use a more algebraic approach. Let $G$ denote a cyclic group of order $n$ with generator $\sigma$. Suppose $G$ acts on the set $\{0,1,...,n-1\}$ by $\sigma(i)=i+1$ mod $n$. Consider a finite field $\fff$ and let us identify $\sigma$ with the cyclic shift sending $\sigma:\fff^n\rightarrow \fff^n$ sending $(a_1,...a_{n-1},a_n)\longmapsto (a_n,a_1,...,a_{n-1})$ and let $G=\langle \sigma\rangle$. \begin{definition} A linear code $C$ of length $n$ is a \textbf{cyclic code} if whenever $\mathbf{c}=(c_1,...,c_n)$ is a codeword then so is its cyclic shift $\mathbf{c'}=(c_2,...,c_n,c_1)$. \end{definition} \begin{example}\label{ex:7,4,3} Consider the binary code $C$ with generator matrix \[ G= \left( \begin{array}{ccccccc} 1 & 0 & 1 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array} \right) \] Clearly these four rows $\vec{g_1}$, $\vec{g_2}$, $\vec{g_3}$, $\vec{g_4}$ are obtained from the previous by a shift to the right. Also notes the shift of $\vec{g_4}$ to the right is equal to $\vec{g_5}=\vec{g_1}+\vec{g_3}+\vec{g_4}$. The shift of $\vec{g_5}$ to the right is $\vec{g_6}=\vec{g_1}+\vec{g_2}+\vec{g_3}$. And the shift of $\vec{g_6}$ is $\vec{g_7}=\vec{g_2}+\vec{g_3}+\vec{g_4}$. The shift of $\vec{g_7}$ is $\vec{g_1}$. Therefore, the linear code generated by $G$ is invariate under shifts to the right. Therefore $C$ is a cyclic code. \end{example} Cyclic codewords are conveniently represented as polynomials modulo $x^n-1$. In fact, if $\vec{c}=(c_1,...,c_n)$ then let \[ c(x)=c_1+c_2x+...+c_nx^{n-1} \] denote the associated \textbf{codeword polynomial}. In this notation the cyclic shift $\vec{c'}=(c_2,...,c_n,c_1)$ of $\vec{c}$ corresponds to the polynomial $xc(x)\pmod{x^n-1}$. In other words cyclic shifts correspond to multiplication by $x$. Since cyclic shifts leave cyclic codes invariant, multiplication by any power of $x$ modulo $x^n-1$ corresponds to a codeword in $C$. Since $C$ is a linear code, the sum of any two such codeword polynomials is another codeword polynomial. Therefore, in fact, the product of any codeword polynomial times any polynomial in $x$ modulo $x^n-1$ is another codeword polynomial. Denote by $R_n$ the ring of polynomials with coefficients in $\mathbb{F}$ modulo $x^n-1$: \begin{equation} \label{equation:R_n} R_n=\mathbb{F}[x]/(x^n-1). \end{equation} Define an \textbf{ideal} $I$ of $R_n$ to be any subset of $R_n$ closed under addition and multiplication by an arbitrary element of $R_n$: \begin{itemize} \item If $f,g\in I$ then $f+g\in I$, and \item If $f\in I$ and $r\in R_n$ then $rf\in I$. \end{itemize} In other words an ideal in $R_n$ is simply a subset closed under addition and multiplication by an arbitrary polynomial modulo $x^n-1$. In particular, the collection of codeword polynomials associated to a cyclic code is an ideal of $R_n$. \begin{lemma}\label{lemma:4} There is natural one-to-one correspondence between cyclic codes of length $n$ over $\mathbb{F}$ and ideals of $R_n$. \end{lemma} This can be found in any book on coding theory, for example MacWilliams and Sloane \cite{MS}. In fact GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials. In order to define the generator polynomial of a cyclic code we need the following mathematical fact. \begin{lemma} Every ideal $I$ of $R_n$ is of the form $g(x)R_n$. In other words every element of $I$ is a multiple of $g(x)$ for some polynomial $g(x)$ in $R_n$. \end{lemma} Ideals which are of the form $I=g(x)R_n$ are called \textbf{principal ideals} and $g(x)$ is called a \textbf{generator} of the ideal $I$. \textbf{Proof} Suppose not. Let $s(x)$ be a non-zero element in $I$ of smallest degree. Pick an arbitrary non-zero element $f(x)$ in $I$. By the division algorithm, we can write $f(x)=q(x)s(x)+r(x)$ where $q$ and $r$ are polynomials and the degree of $r(x)$ is strictly less than the degree of $s(x)$. Notice that $r(x)=f(x)-q(x)s(x)$ belongs to $I$ by definition. This contradicts the assumption that $s(x)$ has smallest degree unless $r(x)=0$. Therefore every element of $I$ is a multiple of $s(x)$. Take $g(x)=s(x)$. $\Box$ \begin{definition} Let $C$ be a cyclic code of length $n$. Let $I$ be the ideal corresponding to $C$ by Lemma \ref{lemma:4}. We call $g(x)$ a \textbf{generator polynomial} of $C$ if it is a generator of $I$. \end{definition} \begin{example} We continue with Example \ref{ex:7,4,3}. Let $g(x)=1+x^2+x^3$. This is the codeword polynomial associated to the top row of the generator matrix. $g(x)$ is the generator polynomial of the cyclic code $C$. Note that $x^7-1=(x+1)(x^3+x^2+1)(x^3+x+1)$. \end{example} \subsection{Non-abelian group codes} The following construction generalizes the above example in an abstract way but will but be needed later. Let $G$ be any finite group and let $\fff$ be any finite field. Here is a very general construction of a code $C$ whose automorphism group contains $G$. If $x$ is an indeterminate and $g\in G$ then we let the formal symbol $x^g$ denote ``$g$-th power'' of $x$. The group algebra \[ \fff[G]=\{ \sum_{g\in G} c_g x^g\ |\ c_g\in \fff\} \] is a left $G$-module under the action \[ \lambda (g)(x^h)=x^{gh},\ \ \ g,h\in G. \] (Note: $\lambda (g_1)\lambda(g_2)(x^h) =\lambda(g_1)x^{g_2h}=x^{g_1g_2h}=\lambda (g_1g_2)(x^h)$, for $g_1,g_2,h\in G$.) Therefore, $\lambda$ defines an action of $G$ on $\fff[G]$ called the regular representation. Let the dimension of $\fff[G]$ be denoted $n$ (so $n=|G|$ is simply the size of $G$ since the ``coordinates'' of an element of $\fff[G]$ are indexed by $G$). Now, pick any element $a\in \fff[G]$ and consider the the $G$-orbit of $a$ \[ G\cdot a=\{\lambda(g)(a)\ |\ g\in G\}. \] If $a=\sum_{h\in G} c_h x^h$ then $\lambda(g)(a)=\sum_{h\in G} c_hx^{gh}=\sum_{h\in G}c_{g^{-1}h}x^h$. Finally, let $C$ be the vector subspace spanned by $G\cdot a$: \[ C={\rm Span}(\{\lambda(g)(a)\ |\ g\in G\}) ={\rm Span}(\{\sum_{h\in G}c_{g^{-1}h}x^h\ |\ g\in G\}). \] In this case, $G$ acts on $C$ the left by permuting coordinates via the left action of $G$ on itself, so $G\subset \Aut(C)$. More generally, one may take $C$ to be any $G$-submodule of $\fff[G]$. \subsection{QR codes} Usually quadratic residue codes are constructed as a special type of cyclic code. However, here we define them using Fourier transforms. (For the usual definition, see for example \cite{MS}.) \subsubsection{Fourier transforms on finite fields} There is a finite field analog of the usual Fourier transform \[ f(x)\longmapsto \int_{\rrr} f(x)e^{ixy}\, dx, \] on the additive group of field of real numbers $\rrr$. (It is doubtful that Fourier had finite fields in mind in the early 1800's when he used Fourier series to solve the heat equation!) First, for the analog of $e^{ixy}$, we need to know how to construct the additive characters of $\fff$. Let $p>2$ denote an odd prime and let $(\frac{a}{p})$ denote the {\bf Legendre character}: \[ (\frac{a}{p})= \left\{ \begin{array}{ll} 1,& a\not=0\ {\rm quadratic\ residue\ mod}\ p,\\ -1,& a\not= 0\ {\rm quadratic\ nonresidue\ mod}\ p,\\ 0, & a=0. \end{array} \right. \] By {\bf quadratic reciprocity}, if $p>2$ we have $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$. If $p,\ell$ are both odd primes then we have $(\frac{\ell}{p})(\frac{p}{\ell})=(-1)^{\frac{(p-1)(\ell-1)}{4}}$. In particular, $2$ is a quadratic residue of $p$ if and only if $p\equiv \pm 1\pmod 8$. Let $\fff = GF(p)$ and let $F=GF(\ell)$, where $\ell$ is a prime different from $p$ which is a quadratic residue of $p$. For example, we shall take $\ell=2$ and $p\equiv 1\pmod 8$. If $\xi$ is a $p-th$ root of unity in a field containing $F$ then every $w\in F(\xi)$ can be uniquely written as \[ w=w_0+w_1\xi+w_2\xi^2+...+w_{p-1}\xi^{p-1},\ \ \ w_i\in F. \] Addition in $F(\xi)$ is as usual but multiplication is to be ``performed $\pmod{\xi^p-1}$''. We think of $F(\xi)$ as the analog of the field of complex numbers. Define an additive character $\psi_1:\fff\rightarrow F(\xi)^\times$ by $\psi_1(a)=\xi^a$, $a\in \fff$. Clearly, $\psi_1(a_1+a_2)=\xi^{a_1+a_2}=\xi^{a_1}\xi^{a_2}= \psi_1(a_1)\psi_1(a_2)$, for all $a_1,a_2\in \fff$, so $\psi_1$ is an additive character. For any $b\in \fff$, define \[ \psi_b(a)=\psi_1(ab). \] In particular, $\psi_0=1$. Since $\psi_b(a_1+a_2)=\psi_b(a_1)\psi_b(a_2)$, for all $a_1,a_2\in \fff$, it follows that $\psi_b$ too is an additive character. \begin{lemma} \begin{itemize} \item[(a)] (Orthogonality) As elements of $F$, we have \[ \sum_{c\in \fff}\psi_a(c)\psi_b(c) = \left\{ \begin{array}{ll} p,& a+b=0,\\ 0,& a+b\not= 0. \end{array} \right. \] (Note: if $\ell=2$ then here $p=1$ in $F$.) \item[(b)] If $\psi:\fff\rightarrow F(\xi)$ is any additive character of $\fff$ (i.e., satisfies $\psi(a_1+a_2)=\psi(a_1)\psi(a_2)$, for all $a_1,a_2\in \fff$) then there is a unique $b\in \fff$ such that $\psi=\psi_b$. \end{itemize} \end{lemma} The first part is a special case of ``Schur orthogonality''. The second part is a special case of the duality between elements of an abelian group and its dual group of characters. A proof (which the interested reader who knows a little group theory might try on his/her own) can be found many books on group theory or finite fields. Let $f:\fff\rightarrow F(\xi)$ be any function. The {\bf Fourier transform} of $f$ is the function \[ FT_f(b)=\sum_{a\in \fff}f(a)\psi_b(a),\ \ \ \ b\in \fff. \] \begin{lemma} (Fourier inversion) If $f:\fff\rightarrow F(\xi)$ is any function \[ f(a)=|\fff|^{-1}\sum_{b\in \fff} FT_f(b)\psi_b(-a),\ \ \ \ a\in \fff. \] (Recall, $|\fff|^{-1}$ is to be regarded as an element of $F(\xi)$.) \end{lemma} This is a consequence of orthogonality. \subsubsection{Generalized quadratic residue codes} If ``useful and practical'' fought ``mathematically beautiful'' in a battle over the quadratic residue codes, ``mathematically beautiful'' would win. These codes seems to have reasonably fast encoders and decoders but lack good parameters\footnote{Although there are some extremely interesting but conjectural results in Bazzi-Mittel \cite{BM} which use QR code-like constructions to construct related codes whch seem to have very good parameters.}. However, they have striking mathematical properties, especally as related to representation theory. We follow \cite{MS}, \S 16.4-16.5. Again, let $\ell,p$ be primes with $p>2$ and $\ell\geq 2$ a quadratic residue of $p$. Let $Q$ denote the set of quadratic residues in $\fff^\times$ and $N$ denote the set of nonquadratic residues in $\fff^\times$. In other words, $a\in Q$ if and only if $(\frac{a}{p})=1$ and $a\in N$ if and only if $(\frac{a}{p})=-1$. Since $(\frac{...}{p})$ defines a non-trivial character of $\fff^\times$, orthogonality implies $\sum_{a\in \fff^\times}(\frac{a}{p})=0$. This implies $|Q|=|N|$, so $|Q|=\frac{1}{2}|\fff^\times|=|N|$. Let us enumerate the elements of $\fff=GF(p)$ in some way, say $\fff=\{0,1,...,p-1\}$. Now identify $GF(\ell)^p$ with the vector space of function values \[ \{(f(0),f(1),...,f(p-1))\ |\ f:\fff\rightarrow GF(\ell)\}. \] The {\bf generalized quadratic residue code} is the subspace of functions in the kernel of the Fourier transform on $Q$: \[ C_Q(\fff,F)=\{ (f(0),f(1),...,f(p-1))\ |\ FT_f(a)=0,\ \ \forall a\in Q\}. \] There is an analogous code for the nonresidues: \[ C_N(\fff,F)=\{(f(0),f(1),...,f(p-1))\ |\ FT_f(a)=0,\ \ \forall a\in N\}. \] Though tempting, this last one is not called the generalized quadratic nonresidue code! Instead, usually these two are simply referred to as the generalized quadratic residue codes. Let $Q=\{a_1,...,a_r\}$ (so $r=\frac{p-1}{2})$. From this definition, we see that a check matrix for $C_Q(\fff,F)$ is \[ H= \left( \begin{array}{cccc} \psi_{a_1}(0) & \psi_{a_1}(1) & ... & \psi_{a_1}(p-1) \\ \psi_{a_2}(0) & \psi_{a_2}(1) & ... & \psi_{a_2}(p-1) \\ \vdots & & & \vdots \\ \psi_{a_r}(0) & \psi_{a_r}(1) & ... & \psi_{a_r}(p-1) \end{array} \right) = \left( \begin{array}{cccc} 1 & \xi^{a_1} & ... & \xi^{a_1(p-1)} \\ 1 & \xi^{a_2} & ... & \xi^{a_2(p-1)} \\ \vdots & & & \vdots \\ 1 & \xi^{a_r} & ... & \xi^{a_r(p-1)} \end{array} \right) \] \begin{lemma} The parameters $[n,k,d]$ of the generalized quadratic residue codes satisfy \[ n=p,\ \ \ k=\frac{p+1}{2},\ \ \ d\geq \sqrt{p}. \] \end{lemma} Determining $d$ for a quadratic residue code with $p$ ``large'' is a very hard problem. For example, recently M. Grassl published some tables extending those in chapter 16 of \cite{MS} of values $[n,k,d]$ for quadratic residue codes with $\ell=2,3$ and $p\leq 167$. Another apparently hard problem for these codes is to determine which coordinates the information bits lie in. Let $\overline{C}_Q(\fff,F)$ denote the code generated by $C_Q(\fff,F)$ and the all $1$'s vector and $\overline{C}_N(\fff,F)$ denote the code generated by $C_N(\fff,F)$ and the all $1$'s vector. \begin{definition} If $C$ is any $[n,k]$-code over $\fff$ then the {\bf dual code} $C^\perp$ is a $[n,n-k]$-code defined by the vector space of all $n$-vectors orthogonal every codeword: \[ C^\perp = \{ {\vec v}\in \fff^n\ |\ {\vec v}\cdot {\vec c}=0, \ \forall {\vec c}\in C\}, \] where \[ {\vec v}\cdot {\vec w}=v_1w_1+v_2w_2+...+v_nw_n\in \fff, \] where ${\vec v}=(v_1,...,v_n)$, ${\vec w}=(w_1,...,w_n)$. A code satisfying $C^\perp = C$ is called {\bf self-dual}. \end{definition} Dual codes are often useful to have lying around. One nice property they have: a parity check matrix of $C$ is a generating matrix for $C^\perp$. \begin{lemma} \[ {C}_Q(\fff,F)^\perp =\left\{ \begin{array}{ll} \overline{C}_Q(\fff,F),& p\equiv 1\pmod 4,\\ \overline{C}_N(\fff,F),& p\equiv -1\pmod 4, \end{array} \right. \] \[ {C}_N(\fff,F)^\perp =\left\{ \begin{array}{ll} \overline{C}_N(\fff,F),& p\equiv 1\pmod 4,\\ \overline{C}_Q(\fff,F),& p\equiv -1\pmod 4, \end{array} \right. \] \end{lemma} (This is proven in \S 16.4 in \cite{MS}.) In other words, if $p\equiv 1\pmod 4$ then all the codewords in the code $C=C_Q(\fff,F)$ are orthogonal to themselves! (Such a code is sometimes called ``self-orthogonal''.) \subsubsection{Extended quadratic residue codes} Define the {\bf extended quadratic residue codes} by \[ \hat{C}_Q(\fff,F) =\{(c_1,...,c_p,c_\infty)\ |\ (c_1,...,c_p)\in C_Q(\fff,F),\ c_\infty=\alpha\sum_{i=1}^p c_i\}, \] \[ \hat{C}_N(\fff,F) =\{(c_1,...,c_p,c_\infty)\ |\ (c_1,...,c_p)\in C_N(\fff,F),\ c_\infty=\alpha\sum_{i=1}^p c_i\}, \] where $1+\alpha^2 p=0$ (either choice of sign will work). These codes are self-dual if $p\equiv 1\pmod 4$ and are the dual of each other if $p\equiv -1\pmod 4$. Even more interesting is the fact that these codes have large automorphism groups. \begin{theorem} (Gleason-Prange) Assume $\ell=2$ and $p\equiv \pm 1\pmod 8$. The automorphism group $\Aut(\hat{C}_Q(\fff,F))$ contains a subgroup isomorphic to $PSL(2,p)$. \end{theorem} See \cite{MS}, \S 16.5 for a proof of this and more details on how the permutation automorphism acts on the code (see also \S 6.6 of \cite{HP}). This theorem says that $\hat{C}_Q(\fff,F)$ may be regarded as a representation space of $PSL(2,p)$. The action of $G=PSL(2,p)$ on $C=\hat{C}_Q(\fff,F)$ is reminiscent of the Weil representation of $SL(2)$ over a $p$-adic field, one of the more remarkable representations in mathematics. See Ward \cite{W} for more of this fascinating story. As was mentioned above, these codes seem to lack good parameters. However, work is still being done to improve estimates on the minimum distance $d$ of these QR codes (see for example Voloch \cite{V} and recent work of M. Grassl referenced there). \section{Lecture 3: Algebraic geometric codes for $\ppp^1$} Let $\fff=GF(q)$ denote a finite field and let $F$ denote an algebraic closure of $\fff$. In the early 1980's a Russian mathematician Goppa discovered a way to associated to each ``nice'' algebraic curve defined over a finite field a family of error-correcting codes whose length, dimension, and minimum distance distance can either be determined precisely or estimated in terms of some geometric parameters of the curve you started with. Rather than going into detail about Goppa's general construction, we shall focus on a very special case where these constructions can be made very explicitly. We must first build up some geometrical background before these codes can be introduced. \subsection{The projective line} What exactly is the projective line $\ppp^1$? The analogy to keep in mind is that $\ppp^1$ is analogous to the complex plane compactified by adding the point at infinity, i.e. the Riemann sphere $\hat{\ccc}$. Algebraically, in a rigorous treatment points are replaced by places - ``valuations'' on the function field $F(\ppp^1)$. We shall, for reasons of space (pun intended), emphasize intuition over precision. What is a point? $\ppp^1$ (as a set) may be thought of as the set of lines through the origin in affine space $F^2$. We say two points in $F^2-\{(0,0)\}$ are ``equivalent'' if they lie on the same line (this is an equivalence relation). If $y\not=0$ then we denote the equivalence class of $(x,y)$ by $[a:1]$, where $a=x/y$. If $y=0$ then we denote the equivalence class of $(x,y)$ by $[1:0]$. This notation is called the {\bf projective coordinate} notation for elements of $\ppp^1$. The group $GL(2,\ccc)$ acts on the Riemann sphere by linear fractional (``M\"obius'') transformations, $z\longmapsto \frac{az+b}{cz+d}$, $\left( \begin{array}{cc} a & b\\ c & d \end{array} \right)\in GL(2,\ccc)$. This action factors through $PGL(2,\ccc)$ since scalar matrices act trivially. Similarly, $PGL(2,F)$ acts on $X=\ppp^1$. In fact, ${\rm Aut}(X)=PGL(2,F)$. \subsection{Riemann-Roch spaces} The only meromorphic functions on the Riemann sphere are the rational functions, so we focus on the $F$-valued rational functions on the $\ppp^1$, denoted $F(\ppp^1)$. Let $f\in F(\ppp^1)$, so $f(x)=\frac{p(x)}{q(x)}$ is a rational function where $x$ is a ``local coordinate'' on $\ppp^1$ and $p(x),q(x)$ are polynomials. In other notation, \[ F(\ppp^1)=F(x). \] For example, a polynomial $f(x)$ of degree $n$ in $x$ is an element of $F(\ppp^1)$ which has $n$ zeros (by the fundamental theorem of algebra) and a pole of order $n$ at ``the point at infinity'', denoted $\infty$. (What this really means is that $f(1/x)$ has a pole of order $n$ at $x=0$.) A {\bf divisor on $\ppp^1$} is simply a {\it formal} linear combination of points with integer coefficients, only finitely many of which are non-zero. The {\bf divisor of $f$} is the formal sum of zeros of $f$ minus the poles, counted according to multiplicity. These sums include any zero or pole at the ``point at infinity'' on $\ppp^1$. For any given divisor $D$, the set of points occuring in the formal sum defining $D$ whose integer coefficient is non-zero is called the {\bf support} of $D$, written $\supp(D)$. The divisor of a rational function $f$ is denoted $\div(f)$. If $f$ is, for example, a polynomial of degree $n$ in $x$ then $\div(f)=P_1+...+P_n-n\infty$ and $\supp(\div(f)) =\{P_1,...,P_n,\infty\}$, where the $P_i$'s denote the zeros of $f$. Since divisors are merely formal integral combinations of points, the sum and difference of any two divisors is another divisor. The abelian group of all divisors is denoted $\Div(\ppp^1)$. Let $X=\ppp^1$ and let $F(X)$ denote the function field of $X$ (the field of rational functions on $X$). If $D$ is any divisor on $X$ then the Riemann-Roch space $L(D)$ is a finite dimensional $F$-vector space given by \[ L(D)=L_X(D)= \{f\in F(X)^\times \ |\ \div(f)+D\geq 0\}\cup \{0\}, \] where $\div(f)$ denotes the divisor of the function $f\in F(X)$. These are the rational functions whose zeros and poles are ``no worst than those specified by $D$''. Let $\ell(D)$ denote its dimension. Let $\infty=[1:0]\in X$ denote the point at infinity. In this case, the Riemann-Roch theorem becomes \[ \ell(D)-\ell(-2\infty -D)=\deg(D)+1. \] It is known (and easy to show) that if $\deg(D)<0$ then $\ell(D)=0$ and if $\deg(D)\geq 0$ then $\ell(D)=\deg(D)+1$. \subsection{The action of $G$ on $L(D)$} \label{sec:1} Let $X=\ppp^1/F$, so ${\rm Aut}(X)=PGL(2,F)$, where $F$ is algebraically closed. The action of ${\rm Aut}(X)$ on $F(X)$ is defined by \[ \begin{array}{cccc} \rho:&{\rm Aut}(X)&\longrightarrow &{\rm Aut}(F(X)),\\ & g &\longmapsto & (f\longmapsto f^g) \end{array} \] where $f^g(x)=(\rho(g)(f))(x)=f(g^{-1}(x))$. Note that $Y=X/G$ is also smooth and $F(X)^G=F(Y)$. Of course, ${\rm Aut}(X)$ also acts on the group $\Div(X)$ of divisors of $X$, denoted $g(\sum_P d_P P)=\sum_P d_Pg(P)$, for $g\in {\rm Aut}(X)$, $P$ a prime divisor, and $d_P \in \zzz$. It is easy to show that $\div(f^g)=g(\div(f))$. Because of this, if $\div(f)+D\geq 0$ then $\div(f^g)+g(D)\geq 0$, for all $g\in \Aut(X)$. In particular, if the action of $G\subset \Aut(X)$ on $X$ leaves $D\in \Div(X)$ stable then $G$ also acts on $L(D)$. We denote this action by \[ \rho:G \rightarrow \Aut(L(D)). \] A basis for the Riemann-Roch space is explicitly known for $\ppp^1$. For notational simplicity, let \[ m_P(x)= \left\{ \begin{array}{cc} x, & P=[1:0]=\infty,\\ (x-p)^{-1}, & P=[p:1]. \end{array} \right. \] \begin{lemma} \label{lemma:P1basis} Let $P_0=\infty=[1:0]\in X$ denote the point corresponding to the localization $F[x]_{(1/x)}$. For $1\leq i\leq s$, let $P_i=[p_i:1]$ denote the point corresponding to the localization $F[x]_{(x-p_i)}$, for $p_i\in F$. Let $D=\sum_{i=0}^s a_i P_i$ be a divisor, $a_k\in\zzz$ for $0\leq k\leq s$. \begin{itemize} \item[(a)] If $D$ is effective then \[ \{ 1,m_{P_i}(x)^k\ |\ 1\leq k\leq a_i, 0\leq i\leq s\} \] is a basis for $L(D)$. \item[(b)] If $D$ is not effective but $\deg(D)\geq 0$ then write $D=dP+D'$, where $\deg(D')=0$, $d>0$, and $P$ is any point. Let $q(x)\in L(D')$ (which is a 1-dimensional vector space) be any non-zero element. Then \[ \{ m_P(x)^{i}q(x)\ |\ 0\leq i\leq d\} \] is a basis for $L(D)$. \item[(c)] If $\deg(D)<0$ then $L(D)=\{0\}$. \end{itemize} \end{lemma} The first part is Lemma 2.4 in \cite{Lo}. The other parts follow from the definitions and the Riemann-Roch theorem. In general, we have the following result. \begin{theorem} \label{thrm:P1} Let $X$, $F$, $G\subset {\rm Aut}(X)=PGL(2,F)$, and $D=\sum_{i=0}^s a_i P_i$ be a divisor as above. Let $\rho:G\rightarrow {\rm Aut}(L(D))$ denote the associated representation. This acts trivially on the constants (if any) in $L(D)$; we denote this action by $1$. Let $S={\rm supp}(D)$ and let \[ S=S_1\cup S_2\cup ... \cup S_m \] be the decomposition of $S$ into primitive $G$-sets. \begin{itemize} \item[(a)] If $D$ is effective then \[ \rho\cong 1\oplus_{i=1}^m \rho_i, \] where $\rho_i$ is a representation on the subspace \[ V_i=\langle m_P(x)^{\ell_j}\ |\ 1\leq \ell_j\leq a_j, \ P\in S_i\rangle, \] satisfying $\dim(V_i)=\sum_{P_j\in S_i} a_j$, for $1\leq i \leq m$. Here $\langle ... \rangle$ denotes the vector space span. \item[(b)] If $\deg(D)>0$ but $D$ is not effective then $\rho$ is a subrepresentation of $\rho:G\rightarrow Aut_F\, L(D')$, where $D'$ is a $G$-equivariant effective divisor satisfying $D'\geq D$. \end{itemize} \end{theorem} \pf (a) Fix an $i$ such that $1\leq i \leq m$. Consider the subspace $V_i$ of $L(D)$. Since $G$ acts by permuting the points in $S_i$ transitively, this action induces an action $\rho_i$ on $V_i$. This action on $V_i$ is irreducible since the action on $S_i$ is transitive, by definition. Clearly $\oplus_{i=1}^m \rho_m$ is a subrepresentation of $\rho$. For dimension reasons, this subrepresentation must be all of $\rho$, modulo the constants (the trivial representation). (b) Since $D$ is not effective, we may write $D=D^+-D^-$, where $D^+$ and $D^-$ are non-zero effective divisors. The action of $G$ must preserve $D^+$ and $D^-$. Since $L(D)$ is a $G$-submodule of $L(D^+)$, the claim follows. \qed \subsection{The codes} Let $D$ be a divisor in $X(F)$ stabilised by $G$ whose support is contained in $X(\fff)$. Let $P_1,...,P_n\in X(\fff)$ be distinct points and $E=P_1+...+P_n\in \Div(X)$ be stabilized by $G$. This implies that $G$ acts on the set $\supp(E)$ by permutation. Assume $\supp(D)\cap \supp(E)=\emptyset$. Choose an $\fff$-rational basis for $L(D)$ and let $L(D)_\fff$ denote the corresponding vector space over $\fff$. Let $C=C(D,E)$ denote the {\bf algebraic geometric code} \begin{equation} \label{eqn:AGcode} C=\{(f(P_1),...,f(P_n))\ |\ f\in L(D)_\fff\}. \end{equation} This is the image of $L(D)_\fff$ under the evaluation map \begin{equation} \label{eqn:eval} \begin{array}{c} \eval_E:L(D)\rightarrow F^n,\\ f \longmapsto (f(P_1),...,f(P_n)). \end{array} \end{equation} These are also called ``classical Goppa codes''. The group $G$ acts on $C$ by $g\in G$ sending \[ c=(f(P_1),...,f(P_n))\in C\longmapsto c'=(f(g^{-1}(P_1)),...,f(g^{-1}(P_n))), \] where $f\in L(D)$. First, we observe that this map, denoted $\phi(g)$, is well-defined. In other words, if $eval_E$ is not injective and $c$ is also represented by $f'\in L(D)$, so $c=(f'(P_1),...,f'(P_n))\in C$, then we can easily verify $(f(g^{-1}(P_1)),...,f(g^{-1}(P_n)))= (f'(g^{-1}(P_1)),...,f'(g^{-1}(P_n)))$. (Indeed, $G$ acts on the set $\supp(E)$ by permutation.) This map $\phi(g)$ induces a homomorphism of $G$ into the permutation automorphism group of the code $\Aut(C)$, denoted \begin{equation} \label{eqn:phi} \phi:G\rightarrow \Aut(C). \end{equation} Let $P$ be the permutation automorphism group of the code $C=C(D,E)$ defined in (\ref{eqn:AGcode}). In many cases it is known that the map $\phi:G\rightarrow P$ is an isomorphism (see \cite{JK2}, \cite{We}). In any case, using (\ref{eqn:phi}), we regard $C$ as a $G$-module. In particular, the (bijective) evaluation map $\eval_E:L(D)\rightarrow C$ in (\ref{eqn:eval}) is $G$-equivariant. Since $G$ acts (via $\phi$) as a permutation on $C$, we have proven the following result. \begin{proposition} Under the conditions above, the representation $\rho$ of $G$ on $L(D)$ is equivalent to a representation $\rho'$ with with property that, for all $g\in G$, $\rho'(g)$ is a permutation matrix. \end{proposition} \subsection{Memory application} If $C$ is an linear code with non-trivial permutation group then this extra symmetry of the code may be useful in practice. In order to store the elements of $C$, we need only store one element in each $G$-orbit, so this symmetry can be used to more efficiently store codewords in memory on a computer. \vskip .3in {\it Acknowledgement}: Parts of these notes have been copied verbatim from joint work with my colleague W. Traves \cite{JT} and with my students W. Irons \cite{I} and J. McGowan \cite{Mc}. \begin{thebibliography}{99} \bibitem[Ba]{Ba} A. Barg, UMCP web page, \verb+http://www.enee.umd.edu/~abarg/+ \bibitem[BM]{BM} L. Bazzi and S. Mitter, {\it Some constructions of codes from group actions}, preprint, 2001. %\bibitem[Ch]{Ch} Chartrand, {\bf Introduction to graph theory}, %Dover, 1977. \bibitem[Gap]{GAP} The GAP~Group, \textbf{GAP -- Groups, Algorithms, and Programming, Version 4.4}; 2002, \verb+(http://www.gap-system.org)+. \bibitem[G1]{G1}%{GUAVA_home} GUAVA home \verb+http://cadigweb.ew.usna.edu/~wdj/gap/GUAVA/+ \bibitem[G2]{G2}%{GUAVA_examples} GUAVA examples \verb+http://cadigweb.ew.usna.edu/~wdj/gap/GUAVA/GUAVA_examples.html+ \bibitem[HP]{HP} W. C. Huffman and V. Pless, {\bf Fundamentals of error-correcting codes}, Cambridge Univ. Press, 2003. \bibitem[I]{I} W. Irons, {\it A polynomial-time probabilistic algorithm for the minimum distance of an arbitrary linear non-binary error-correcting code}, \verb+http://cadigweb.ew.usna.edu/~wdj/irons/+ \bibitem[JK1]{JK} D. Joyner and A. Ksir, {\it Modular representations on some Riemann-Roch spaces of modular curves $X(N)$,} in {\bf Computational Aspects of Algebraic Curves} (Editor: T. Shaska), Lecture Notes in Computing, World Scientific, 2005. \bibitem[JK2]{JK2} ------ and ------, {\it Automorphism groups of some AG codes}, to appear (in PAMS?) \bibitem[JT]{JT} ------ and W. Traves, ``Representations of finite groups on Riemann-Roch spaces,'' 2003 preprint, available at \newline \verb+http://front.math.ucdavis.edu/math.AG/0210408+ \bibitem[Lo]{Lo} D. Lorenzini, {\bf An invitation to arithmetic geometry}, Grad. Studies in Math, AMS, 1996. \bibitem[Le]{Le} C. Lennon, {\it List-decoding of generalized Reed-Solomon codes Using Sudan's algorithm}, \verb+http://cadigweb.ew.usna.edu/~wdj/lennon/+ \bibitem[Lu]{Lu} F. Luebeck, {\it Conway polynomials page}, \newline \verb+http://www.math.rwth-aachen.de:8001/~Frank.Luebeck/data/ConwayPol/index.html+ \bibitem[MS]{MS} F. MacWilliams and N. Sloane, {\bf The theory of error-correcting codes}, North-Holland, 1977. \bibitem[Mc]{Mc} J. McGowan, {\it Implementing generalized Reed-Solomon codes and a cyclic code decoder in GUAVA}, \verb+http://cadigweb.ew.usna.edu/~wdj/mcgowan/+ \bibitem[S]{S} N. Sloane, {\it Unsolved Problems in graph theory arising from the study of codes}, in {\bf Graph Theory Notes of New York} 18 (1989), pp. 11-20. \bibitem[Ta]{Ta} R. M. Tanner, {\it A transform theory for a class of group-invariant codes,} IEEE Trans. Infor. Theory 1988 \bibitem[vLM]{vLM} J. van Lint, F. J. MacWilliams, ``Generalized quadratic residue codes,'' Proc. IEEE Trans Info Theory \underline{24}(1978)730-737. \bibitem[V]{V} J. Voloch, {\it Computing the minimum distance of cyclic codes}, preprint available on the webpage \newline \verb+http://www.ma.utexas.edu/users/voloch/preprint.html+ \bibitem[W]{W} H. N. Ward, {\it Quadratic residue codes and symplectic groups}, J. Algebra \underline{29}(1974)150-171. \bibitem[We]{We} S. Wesemeyer, ``On the automorphism group of various Goppa codes,'' \emph{IEEE Trans. Info. Theory.}, 44(1998)630-643. \end{thebibliography} \end{document}