%9-22-2005 \documentclass{beamer} % This file is a solution template for: % - Giving a talk on some subject. % - The talk is between 15min and 45min long. % - Style is ornate. \usepackage{color} \definecolor{hue}{rgb}{.202, .602, .58} \definecolor{red}{rgb}{.902, .02, .08} \definecolor{green}{rgb}{.02, .902, .08} \definecolor{blue}{rgb}{.02, .02, .908} \definecolor{orange}{rgb}{.902, .502, .08} %\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} \newcommand{\comment}[1]{} \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}}} \mode { \usetheme{Warsaw} %\usecolortheme[named=Green]{structure} %% must define Green... % or ... \setbeamercovered{transparent} % or whatever (possibly just delete it) } \usepackage[english]{babel} % or whatever \usepackage[latin1]{inputenc} % or whatever \usepackage{times} \usepackage[T1]{fontenc} % Or whatever. Note that the encoding and the font should match. If T1 % does not look nice, try deleting the line with the fontenc. \title{Codes, Groups, and Curves} \author{D.~Joyner} % - Use the \inst{?} command only if the authors have different % affiliation. \institute[Math Dept, USNA] % (optional, but mostly needed) { Department of Mathematics\\ US Naval Academy\\ % Annapolis, MD 21402 } \date[May, 2005]{\color{blue} Codes, Groups, and Curves \normalcolor\\ \ \\ {\footnotesize{%Wayne State and Oakland Univerity\\ Michigan\\ 10-11-2005}}} \subject{Talks} % This is only inserted into the PDF information catalog. Can be left % out. % If you have a file called "university-logo-filename.xxx", where xxx % is a graphic format that can be processed by latex or pdflatex, % resp., then you can add a logo as follows: \pgfdeclareimage[height=0.5cm]{mathheader}{mathheader} \logo{\pgfuseimage{mathheader}} % Delete this, if you do not want the table of contents to pop up at % the beginning of each subsection: \AtBeginSubsection[] { \begin{frame} \frametitle{Outline} \tableofcontents[currentsection,currentsubsection] \end{frame} } % If you wish to uncover everything in a step-wise fashion, uncomment % the following command: \beamerdefaultoverlayspecification{<+->} \begin{document} \begin{frame} \titlepage \end{frame} \begin{frame} \frametitle{Outline} \tableofcontents[pausesections] \pause \end{frame} \begin{frame} This computationally-oriented talk deals with some selected topics belonging to the intersection of the \color{blue} theory of error-correcting codes, \normalcolor the \color{orange} representation theory of finite groups, \normalcolor and the \color{green} theory of algebraic curves. \normalcolor \pause \vskip .3in We shall see that codes which exhibit unusual symmetry often times turn out to be very interesting objects of study. \pause \vskip .3in The main results are joint work with \color{red} Amy Ksir. \normalcolor %Lectures given to Wayne State University %and Oakland University, October 2005. \end{frame} %\section{Lecture 1: Codes and groups} \begin{frame} \frametitle{Codes and groups} Here all codes will be ``linear block codes''. \vskip .1in Since (linear, block) codes are vector spaces over finite fields, some very brief facts about \color{orange} finite fields \normalcolor will be recalled first. \vskip .1in \pause Let $\fff$ denote a finite field. It is known that the number of elements of $\fff$ must be a prime power: $2,3,4,5,7,8,9,11,13,16,17,19,25,...$. \end{frame} \section[Finite fields]{Finite fields} %We introduce some terminology and background about finite fields. %For details, see for example \cite{MS}. \begin{frame} \frametitle{Finite field} \framesubtitle{Constructions.} The {\bf prime fields}: If $p\geq 2$ is a prime then $\fff=GF(p)$ denotes the field $\zzz/p\zzz$ with addition and multiplication performed mod $p$. \pause ``GF'' stands for Galois field, named after \color{orange} Evariste Galois \normalcolor who died at the age of 20 after a duel. \pause \vskip .1in Analogies: \begin{center} $\fff[x]$ $\iff$ $\zzz$ $f(x)$ irreducible $\iff$ $p$ prine $\fff[x]/f(x)\fff[x]$ $\iff$ $\zzz/p\zzz$. \end{center} \end{frame} \begin{frame} \begin{center} {\bf Aside/amusing fact}: \end{center} For a ``random'' $k\times k$ matrix with {\bf real} entries, the ``probability'' that its rank is $k$ is of course $1$. \pause \vskip .1in 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...\ . \] \end{frame} \begin{frame} {\bf prime power fields}: $\fff=GF(p)$, $p$ prime $f(x)$ a monic irreducible in $\fff[x]$ of degree $r$. \pause Then: $\eee = \fff[x]/(f(x))= \fff[x]/f(x)\fff[x]$ is a field with $q=p^r$ elements. \pause \vskip .1in If $f(x)$ and $\eee$ are related in this way, we say that $f(x)$ is the {\bf defining polynomial} of $\eee$. \end{frame} \begin{frame} {\bf Facts}: (1) All finite fields arise from one of the above two constructions. \vskip .1in \pause (2) Up to isomorphism, there is only one field of order $q=p^r$,$r\geq 1$, denoted $GF(q)$. \vskip .1in \pause (3) For any finite field $\fff$, $\fff^\times$ is a cyclic group. \vskip .1in \pause $\alpha\in \fff$ is {\bf primitive element} $\iff$ $\fff^\times = \langle \alpha\rangle$. 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. \end{frame} \comment{ \subsection{Matrix representation} \begin{frame} %\begin{center} %{\bf Matrix representation} %\end{center} 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. \pause \vskip .1in 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$). \pause \vskip .1in $A$ is a $\deg(f)\times \deg(f)$ matrix with coefficients in $\mathbb{F}$ %(and the degree of $\mathbb{E}/\mathbb{F}$ is $m$). \end{frame} \begin{frame} 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 {\it matrix associated to $\beta$} to be $B=A^i$. \pause The matrix associated to $0\in\mathbb{E}$ will be the $m\times m$ zero matrix. \pause Therefore, there is a representation \[ \rho:\eee^\times \rightarrow \Aut_\fff (\fff^m)\cong GL(m,\fff) \] induced by the field $\eee\cong \fff^m$ acting on itself. \end{frame} \begin{frame} %\begin{example} {\bf Example}: Take $\fff=GF(2)$, \pause $\eee=GF(16)$, \pause defining polynomial of $\eee$: $f(x)=x^4+x^3+1$. \pause The non-zero elements of $GF(16)$: {\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],\ \ \ \] }} \end{frame} \begin{frame} {\tiny{ \[ \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} \end{frame} } \subsection{Conway polynomials} \begin{frame} There is no canonical choice of $GF(q)$ but there is a ``good'' choice: take $f(x)$ to be the \color{blue} Conway polynomial \normalcolor over $GF(p)$ of degree $r$. This is the default finite field constructed by GAP, SAGE and MAGMA. \pause \vskip .1in {\bf Construction}: Elements of $GF(p)$: the representatives $0, ..., p-1$ of the cosets modulo $p$. \pause Order these: $0 < 1 < 2 < ... < p-1$. \pause Order polynomials of degree $r$ over $GF(p)$: \pause Let $g(x) = g_rx^r + ... + g_0$ and $h(x) = h_rx^r + ... + h_0$ . \pause Define $g < h$ $\iff$ $\exists$ $k$ s.t. $g_i = h_i$ for $i > k$ and $(-1)^{r-k} g_k < (-1)^{r-k} h_k$. \end{frame} \begin{frame} 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 $\bullet\ $ $f_{p,r}(x)$ is monic, \pause \item $\bullet\ $ $f_{p,r}(x)$ is primitive, \pause \item $\bullet\ $ $m|n$ $\implies$ $f_{p,m}(x^{(p^n-1) / (p^m-1)}) \equiv 0 \pmod{f_{p,n}(x)}$. \end{itemize} \pause The fields \[ \fff_1\subset \fff_2\subset \fff_3\subset ... \] (constructed from a sequence of polynomials $f_1=f_{p,n_1}$, $f_2=f_{p,n_2}$, $f_3=f_{p,n_3}$, ... with $n_i|n_{i+1}$) have ``nice'' embedding properties. \pause \vskip .1in %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). \end{frame} \begin{frame} \frametitle{SAGE} \begin{center} \fbox{Advertisement} \end{center} \begin{itemize} \item \begin{center} For number theory and modular forms (and more), try \color{blue} SAGE\normalcolor ! \pause \color{blue} SAGE 0.7 \normalcolor is released! \end{center} \pause \item \begin{center} \color{blue} SAGE\normalcolor \ homepages: http://modular.ucsd.edu/sage/, http://sage.sourceforge.net \end{center} \pause \item \begin{center} It is \color{orange}open source\normalcolor\ and free! \end{center} \begin{figure}[h] \begin{center} \includegraphics[height=2.5cm,width=2cm]{/home/wdj/texfiles/latex-beamer/beamer/solutions/generic-talks/sage.eps} \end{center} \end{figure} \end{itemize} \end{frame} \comment{ \subsection{Fourier transforms on finite fields} \begin{frame} The usual Fourier transform \[ f(x)\longmapsto \int_{\rrr} f(x)e^{ixy}\, dx, \] \pause For finite field analog, need analog of: \pause $\bullet\ $ complex numbers = range of the FT \pause (the field $F(\xi)$ - constructed below) \pause $\bullet\ $ integral \pause (sum) \pause $\bullet\ $ $x\longmapsto e^{ixy}$ \pause (additive characters of $\fff$ - see below). \end{frame} \begin{frame} $p>2$ an odd prime \pause $a\longmapsto (\frac{a}{p})$ 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. \] Properties: \pause {\bf quadratic reciprocity}: $p>2$ $\implies$ $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$. \pause $p,\ell$ odd primes $\implies$ $(\frac{\ell}{p})(\frac{p}{\ell})=(-1)^{\frac{(p-1)(\ell-1)}{4}}$. \pause $2$ is a quadratic residue of $p$ $\iff$ $p\equiv \pm 1\pmod 8$. \end{frame} \begin{frame} Let $\fff = GF(p)$ and let $F=GF(\ell)$, where $\ell$ is a prime different from $p$ which is a quadratic residue of $p$. \pause Example: $\ell=2$ and $p\equiv 1\pmod 8$. \pause Analog of $\ccc$: 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. \] \pause Addition in $F(\xi)$ is as usual but multiplication is to be ``performed $\pmod{\xi^p-1}$''. \end{frame} \begin{frame} 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. \pause For any $b\in \fff$, define \[ \psi_b(a)=\psi_1(ab). \] %In particular, $\psi_0=1$. $\psi_b(a_1+a_2)=\psi_b(a_1)\psi_b(a_2)$, $\implies$ $\psi_b$ is an additive character. \pause \vskip .1in Every additive character of $\fff$ arises in this way. \end{frame} \begin{frame} {\bf Lemma}: %\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)] (Duality) 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} \end{frame} \begin{frame} %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. %\pause $f:\fff\rightarrow F(\xi)$ arbitrary. \pause \vskip .2in The {\bf Fourier transform} of $f$ is the function \[ FT_f(b)=\sum_{a\in \fff}f(a)\psi_b(a),\ \ \ \ b\in \fff. \] \end{frame} \begin{frame} %\begin{lemma} {\bf 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} \pause This formula is a consequence of orthogonality. \pause The FT on $\fff$ will be used later to construct codes with large automorphism groups! \end{frame} } \section{Linear codes} \begin{frame} The theory of error-correcting codes was originated by \color{orange} Richard Hamming \normalcolor in the late 1940's, a mathematician who worked for Bell Telephone. \pause \vskip .1in %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. \pause \vskip .1in The overall goal behind the theory of error-correcting codes is to {\it reliably enable digital communication}. \end{frame} \begin{frame} 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}. \pause When $\fff=GF(2)$ it is called a {\bf binary} code. \pause Scenario: You send an $n$-tuple of $0$'s and $1$'s (the codeword, $\mathbf{c}\in C$) across a noisy channel to your friend. \pause Your friend gets a corrupted version (the received word $\mathbf{r}\in \fff^n$, $\mathbf{r}\not= \mathbf{c}$). \pause Depending on how the code $C$ was constructed and the number of errors made, it is {\it possible} that the original codeword can be recovered. \pause This raises the natural question: given $C$, how many errors can $\mathbf{r}$ have and still be able to recover $\mathbf{c}$? Stay tuned... \end{frame} \begin{frame} A code of length $n$ and dimension $k$ (as a vector space over $\fff$) is called an {\bf $[n,k]$-code}. \pause 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)$.) \pause \vskip .1in We identify $C$ with the image of $G$. \end{frame} \begin{frame} The function \[ G:\fff^k\rightarrow C, \] \[ \mathbf{m}\longmapsto \mathbf{m}G, \] is called the {\bf encoder}. \pause \vskip .1in A vector $\mathbf{v}\in \fff^n$ is a codeword $\iff$ $H(\mathbf{v})=0$. \pause \vskip .1in $G$ = {\bf generating matrix} of $C$ $H$ = {\bf check matrix} of $C$. \pause \[ \begin{array}{ll} C&=\{\mathbf{c}\ |\ \mathbf{c}=\mathbf{m}G,\ {\rm some}\ \mathbf{m}\in \fff^k\}\\ &=\{\mathbf{v}\in \fff^n\ |\ H\mathbf{v}=\mathbf{0}\}. \end{array} \] \end{frame} \begin{frame} Any generator matrix $G$ of an $[n,k,d]$-code has rank $k$ so the row-reduced echelon form of $G$, call it $G'$, has no rows equal to the zero vector. \pause The row-reduction process $\implies$ {\bf Lemma} Any linear code is permutation equivalent to a code which has a generator matrix of the form $(I_k\ |\ A)$, where $I_k$ denotes the $k\times k$ identity matrix and $A$ is some $k\times (n-k)$ matrix. \end{frame} \begin{frame} $G=(I_k\ |\ A)$ $\iff$ $G$ is in {\bf standard form}. \pause \vskip .2in \begin{center} $G=(I_k\ |\ A)$ $\iff$ $H=(-A^t\ |\ I_{n-k})$ \end{center} \pause \vskip .1in Often a code $C$ is given using $G$ or using $H$. Rarely is a $C$ given by presenting all its codewords. \end{frame} \begin{frame} \begin{center} The Hamming $[7,4,3]$ code example \end{center} Let $\fff=GF(2)$. The code $C$ in this example is the subspace of $\fff^7$ with basis \[ \begin{array}{c} \mathbf{g}_1=(1 , 0 , 0 , 0 , 1 , 1 , 1),\\ \mathbf{g}_2=(0 , 1 , 0 , 0 , 0 , 1 , 1), \\ \mathbf{g}_3=(0 , 0 , 1 , 0 , 1 , 0 , 1). \\ \mathbf{g}_4=(0 , 0 , 0 , 1 , 1 , 1 , 0). \end{array} \] %\pause %There are 16 code words, %$\mathbf{c}=(c_1,c_2,c_3,c_4,c_5,c_6,c_7)$, %$c_i\in \fff$. \pause Given the ``information bits'' $c_1,c_2,c_3,c_4$ (the ``message''), the rest of the codeword (the ``check bits'') are determined by $ c_5=c_1+c_3+c_4, $ \pause $ c_6=c_1+c_2+c_4,\ $ \pause $ c_7=c_1+c_2+c_3. $ %\pause %We will see how to correct an error later. \end{frame} \begin{frame} Let $H=(\mathbf{h}_1,...,\mathbf{h}_7)$ denote the check matrix of $C$ corresponding to $G$. \pause Suppose a codeword %$\mathbf{c}=(c_1,c_2,c_3,c_4,c_5,c_6,c_7)$ was sent and $\mathbf{r}=(r_1,...,r_7)$ was received with exactly one error. \pause Then $H\mathbf{r}=\mathbf{h}_i$, for some $i$. \pause The error in $\mathbf{r}$ is in the $i-th$ bit. \end{frame} \comment{ \begin{frame} $G'$ = row-reduced echelon form of $G$ \pause rank$(G)=k$ $\implies$ $G'$ has no rows equal to the zero vector. \pause The standard basis column vectors $\mathbf{e}_1$, ..., $\mathbf{e}_k$ occur amongst $k$ columns of those of $G'$. \pause The corresponding coordinates of $C$ are called the {\bf information coordinates} (or information bits, if $C$ is binary) of $C$. \pause The remaining coordinates are the {\bf check} coordinates. \end{frame} } \begin{frame} The {\bf Hamming metric} is the function \[ d:\fff^n\times \fff^n\rightarrow \rrr, \] \[ d(\mathbf{v},\mathbf{w})=|\{i\ |\ v_i\not= w_i\}|=d(\mathbf{v}-\mathbf{w},\mathbf{0}). \] \pause \vskip .1in The {\bf Hamming weight} of a vector is simply its distance from the origin: \[ \wt(\mathbf{v})=d(\mathbf{v},\mathbf{0}). \] \pause \vskip .1in {\bf Example}: $d((1,1,1),(1,0,1))=1$, $\wt (1,1,0,0,1)=3$. \end{frame} \begin{frame} {\small {\bf Question}: How many vectors belong to the ``shell'' of radius $r$ about the origin $\mathbf{0}\in GF(q)^r$, $\{d(\mathbf{v},\mathbf{0})=r\}$? \pause \vskip .1in {\bf Answer}: $\left( \begin{array}{c} n\\ r \end{array} \right) (q-1)^r$. \pause \vskip .1in (Sketch: ``distance $r$'' means that there are exactly $r$ non-zero coordinates. The binomial coefficient describes the number of ways to choose these $r$ coordinates.) } \end{frame} \begin{frame} The {\bf minimum distance of $C$} is defined to be the number \[ d(C)=\min_{\mathbf{c}\not=\mathbf{0}} d(\mathbf{c},\mathbf{0}). \] \pause \vskip .2in An $[n,k]$-code with minimum distance $d$ is called an {\bf $[n,k,d]$-code}. \end{frame} \begin{frame} \frametitle{GUAVA} \begin{center} \fbox{Advertisement} \end{center} \begin{itemize} \item \begin{center} For error-correcting codes, try \color{green} GUAVA! \normalcolor \pause \color{green} GUAVA 2.4 \normalcolor now released! \end{center} \pause \item \color{green} GUAVA \normalcolor home: www.gap-system.org/Packages/guava.html \pause \item $\ $ \item \begin{center} It is \color{orange}open source\normalcolor\ and free! \end{center} \item \begin{figure}[h] \begin{center} \includegraphics[height=1cm,width=2cm]{/home/wdj/texfiles/latex-beamer/beamer/solutions/generic-talks/guava.eps} \end{center} \end{figure} \end{itemize} \end{frame} \begin{frame} A favorite of engineers: %\begin{quotation} {\bf Cyclic construction/example} 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. \pause \vskip .2in Pick a non-zero vector $\mathbf{a}\in \fff^n$. Let $C\subset \fff^n$ denote the vector space spanned by the cyclic permutations $g\mathbf{a}$, $g\in G$. \pause In general, there seems to be no easy way to determine the minimum distance $d=d(C)$ from $\mathbf{a}$ and $G$. \pause In fact, to merely determine $k=\dim(C)$ from $\mathbf{a}$ and $G$ uses the ideal theory of the ring $R_n=\fff[x]/(x^n-1)$.... \end{frame} \begin{frame} \begin{center} $G$-action on $C$ \end{center} \vskip .1in Let $G^*=\{\chi_1,...,\chi_n\}$ denote the dual group of $G$, where $\chi_i:G\rightarrow \fff^\times$. \pause \vskip .1in 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. \end{frame} \begin{frame} {\bf 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$. \pause \vskip .1in 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. \] \end{frame} \begin{frame} Let $\mathbf{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 $\mathbf{c}$. \pause \vskip .1in 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)$. \end{frame} \begin{frame} How does this code decompose as a $G$-module? \pause \vskip .1in We determine $G$-invariant basis vectors. Let \[ \begin{array}{l} \mathbf{w}_1=\mathbf{c}+\sigma(\mathbf{c})+\sigma^2(\mathbf{c})+\sigma^3(\mathbf{c})+\sigma^4(\mathbf{c}),\\ \mathbf{w}_2=\mathbf{c}+\alpha\sigma(\mathbf{c})+\alpha^2\sigma^2(\mathbf{c})+ \alpha^3\sigma^3(\mathbf{c})+\alpha^4\sigma^4(\mathbf{c}),\\ \mathbf{w}_3=\mathbf{c}+\alpha^2\sigma(\mathbf{c})+\alpha^4\sigma^2(\mathbf{c})+ \alpha^6\sigma^3(\mathbf{c})+\alpha^8\sigma^4(\mathbf{c}),\\ \mathbf{w}_4=\mathbf{c}+\alpha^3\sigma(\mathbf{c})+\alpha^6\sigma^2(\mathbf{c})+ \alpha^9\sigma^3(\mathbf{c})+\alpha^{12}\sigma^4(\mathbf{c}). \end{array} \] \end{frame} \begin{frame} Compute: $\sigma(\mathbf{w}_1)=\mathbf{w}_1$, $\sigma(\mathbf{w}_2)=\alpha^4\mathbf{w}_2$, $\sigma(\mathbf{w}_3)=\alpha^3\mathbf{w}_3$, and $\sigma(\mathbf{w}_4)=\alpha^2\mathbf{w}_4$. \pause \vskip .1in Hence, these form a $G$-invariant basis. \pause \vskip .1in Therefore \[ C\cong \fff\chi_0 \oplus\fff\chi_2\oplus\fff\chi_3\oplus\fff\chi_4. \] This is the decompositionof $C$ as a $G$-module. \end{frame} \begin{frame} 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. \end{frame} \begin{frame} %\begin{lemma} (Singleton bound) Every linear $[n,k,d]$ code $C$ satisfies \[ k+d\leq n+1. \] %\end{lemma} \pause \vskip .1in 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. \end{frame} \begin{frame} \pf Fix a basis of $\fff_q^n$ and write all the codewords in this basis. Delete the first $d-1$ coordinates in each codeword. Call this new code $C'$. \pause \vskip .1in Since $C$ has minimum distance $d$, this puncturing map $C\rightarrow C'$ is injective, so $|C|=|C'|$. \pause \vskip .1in $C\cong \fff^k$ $\implies$ $|C|=q^k$. \pause \vskip .1in $C'\subset \fff^{n-d+1}$ $\implies$ $|C'|\leq q^{n-d+1}$. \pause \vskip .1in This gives the inequality. \qed \end{frame} \begin{frame} 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. \pause \vskip .1in {\bf Lemma}: %\begin{lemma} If $\mathbf{v}\in \fff^n$ is arbitrary and $0[\frac{d-1}{2}]$, by the above lemma. \end{frame} \begin{frame} \begin{definition} We say that a linear $C$ is {\bf $t$-error correcting} if $|B_t(\mathbf{w})\cap C|\leq 1$. \end{definition} \vskip .1in \pause In particular, if a received word has no more that $t$ errors then there is a unique codeword within distance $t$ from that received word. \vskip .1in \pause Note: $t\leq [\frac{d-1}{2}]$ if and only if $d\geq 2t+1$. \end{frame} \subsection{Linear codes: examples} \begin{frame} %{\bf 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) = (\mathbf{H}_1,\mathbf{H}_2,...,\mathbf{H}_7) = \left( \begin{array}{c} \mathbf{h}_1\\ \mathbf{h}_2\\ \mathbf{h}_3 \end{array} \right) \] \end{frame} \begin{frame} 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} \mathbf{g}_1\\ \mathbf{g}_2\\ \mathbf{g}_3 \\ \mathbf{g}_4 \end{array} \right). \] This code $C$ is the $GF(2)$-linear span of the rows $\mathbf{g}_1,\mathbf{g}_2,\mathbf{g}_3,\mathbf{g}_4$ of $G$. \end{frame} \begin{frame} Now try the following experiment: Alice has ``information'' $c_1,c_2,c_3,c_4\in \fff$ she wants to send to Bob. She sends $\mathbf{c} =c_1\mathbf{g}_1+c_2\mathbf{g}_2+c_3\mathbf{g}_3+c_4\mathbf{g}_4\in C\subset GF(2)^7$. \vskip .1in \pause Bob receives the $7$ bits of $\mathbf{c}$, with 1 error, say $\mathbf{v}=(v_1,v_2,...,v_7)$. \pause You can not only determine where the error is but recover the information $c_1,c_2,c_3,c_4\in \fff$. \end{frame} \begin{frame} Let $H=(\mathbf{H}_1,\mathbf{H}_2,...,\mathbf{H}_7)$ and let $\mathbf{e}_1=(1,0,0,0,0,0,0)$, $\mathbf{e}_2$, ..., $\mathbf{e}_7$ denote the standard basis vectors of $\fff^7$. \vskip .1in \pause Let $\mathbf{e}$ denote the error vector, so $\mathbf{v}=\mathbf{c}+\mathbf{e}$. Once Bob finds $\mathbf{e}$, he can determine $\mathbf{c}$. \pause Compute the ``syndrome'' \[ H\mathbf{v}=H(\mathbf{c}+\mathbf{e}) =H\mathbf{c}+H\mathbf{e}=\mathbf{0}+\mathbf{H}_i=\mathbf{H}_i, \] for some $1\leq i\leq 7$. \pause \color{orange} The vector $\mathbf{c}$ is the same as $\mathbf{v}$ but with the $i^{th}$ bit flipped. Moreover, the first 4 coordinates of $\mathbf{c}$ are the ``information'' values $c_1,c_2,c_3,c_4\in \fff$. \normalcolor \end{frame} \begin{frame} {\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)] What are the best $t$-error-correcting codes, $t>1$? \end{itemize} \end{frame} {\comment{ \begin{frame} 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. \end{frame} }} \subsection{Linear codes: automorphisms} \begin{frame} What is an automorphism of a code? \vskip .1in \pause 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\}. \] \vskip .1in \pause There are no known methods for computing these groups which are polynomial time in the length $n$ of $C$. \end{frame} \begin{frame} If (a) $C_1$ and $C_2$ are two codes of length $n$, and (b) there is a permutation $\sigma\in S_n$ for which $(c_1,...,c_n)\in C_1$ $\iff$ $(c_{\sigma(1)},...,c_{\sigma(n)})\in C_2$, then we say $C_1$ and $C_2$ are {\bf permutation equivalent}, written \[ C_1\cong C_2. \] \vskip .1in \pause The parameters dimension and minimum distance are invariants in the equivalence class of a code: if $C_1\cong C_2$ then $\dim(C_1)=\dim(C_2)$ and $d(C_1)=d(C_2)$. \end{frame} \begin{frame} Let: $C$ be a $[n,k]$-code, \pause $G=\Aut(C)=$ (permutation) automorphism group, \vskip .1in \pause Define \[ \rho:G\rightarrow GL_k(\fff), \] \pause \[ \sigma\longmapsto ((c_1,...,c_n)\in C \longmapsto (c_{\sigma^{-1}(1)},...,c_{\sigma^{-1}(n)})\in C). \] \pause Therefore, $C$ is a (modular) representation space of $G$. \pause Our goal is to determine this representation in some cases. \end{frame} \comment{ %\section{Lecture 2: Quadratic residue codes and other group codes} \section{Group codes} \subsection{Cyclic codes revisited} \begin{frame} %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=\langle \sigma\rangle$ = cyclic group of order $n$ with generator $\sigma$. \pause $G$ acts on the set $\{0,1,...,n-1\}$ by $\sigma(i)=i+1$ mod $n$. \pause $\fff$=finite field \pause identify $\sigma:\fff^n\rightarrow \fff^n$ sending $(a_1,...a_{n-1},a_n)\longmapsto (a_n,a_1,...,a_{n-1})$. \pause %\begin{definition} {\bf 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'}=\sigma(\mathbf{c})=(c_2,...,c_n,c_1)$. %\end{definition} \end{frame} \begin{frame} \frametitle{Cyclic code example} %\begin{example} \label{ex:7,4,3} {\bf Example}: 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)=(\mathbf{g_1},\mathbf{g_2},\mathbf{g_3},\mathbf{g_4})^t \] \pause shift of $\mathbf{g_4}$ to the right = $\mathbf{g_1}+\mathbf{g_3}+\mathbf{g_4}$. \pause shift of $\mathbf{g_5}$ = $\mathbf{g_1}+\mathbf{g_2}+\mathbf{g_3}$. \pause shift of $\mathbf{g_6}$ = $\mathbf{g_2}+\mathbf{g_3}+\mathbf{g_4}$. \pause $\implies$ $C$ is closed under shifts to the right \pause $\implies$ $C$ is cyclic. %\end{example} \end{frame} %\begin{frame} %\begin{center} %$\{$ Codewords $\}$ $\iff$ $\{$ polynomials modulo $x^n-1$ $\}$ %$\mathbf{c}=(c_1,...,c_n)$ $\rightleftarrow$ $c(x)=c_1+c_2x+...+c_nx^{n-1}$ %\pause %$\sigma (\mathbf{c}) \iff xc(x)\pmod{x^n-1}. $ %\pause %$\sigma^2 (\mathbf{c}) \iff x^2c(x)\pmod{x^n-1}. $ %\pause %$\sigma^3 (\mathbf{c})+\sigma (\mathbf{c})+\mathbf{c) \iff (x^3+x+1)c(x)\pmod{x^n-1}.$ %\end{center} %and so on. %\end{frame} \begin{frame} Denote by $R_n$ the ring of polynomials with coefficients in $\mathbb{F}$ modulo $x^n-1$: \pause \[ R_n=\mathbb{F}[x]/(x^n-1) =\{a_0+a_1x+...+a_{n-1}x^{n-1}\ |\ a_i\in \fff. \] \pause $I$ is an ideal of $R_n$ $\iff$ \begin{itemize} \item $\bullet$ $f,g\in I$ $\implies$ $f+g\in I$, \item $\bullet$ $f\in I$, $r\in R_n$ $\implies$ $rf\in I$. \end{itemize} \pause codeword polynomials \[ \{c(x)=c_1+c_2x+...+c_nx^{n-1}\ |\ \mathbf{c}=(c_1,...,c_n)\in C\} \] associated to a cyclic code $C$ = ideal of $R_n$. \end{frame} \begin{frame} %\begin{lemma}\label{lemma:4} {\bf Lemma}: $\exists$ one-to-one correspondence: $\{$ cyclic codes of length $n$ over $\mathbb{F}$ $\}$ $\iff$ $\{$ ideals of $R_n$ $\}$. %\end{lemma} \pause \vskip .1in In fact GUAVA allows you to easily pass back and forth between codewords as vectors and codewords as polynomials. \pause \vskip .1in {\bf Lemma}: %\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} \pause \vskip .1in {\bf Definition}: $C$ = cyclic code of length $n$ $\iff$ ideal $I$ of $R_n$. $g(x)$ is a \textbf{generator polynomial} of $C$ if it is a generator of the ideal $I$. \end{frame} %\begin{frame} %\begin{example} %\frametitle{Cyclic code example revisited} % %We continue with the cyclic code example given previously. %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} % %\end{frame} \subsection{Non-abelian group codes} \begin{frame} %The following construction generalizes the above example %in an abstract way but will but be needed later. Let $G$ = finite group, $\fff$ = finite field. \pause If $x$ is an indeterminate $g\in G \iff x^g$, the formal ``$g$-th power'' symbol. (just as $x^i \iff i$, $0\leq i\leq n-1$ in $R_n$) \pause \[ \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. \pause $\dim \fff[G] = n=|G|$ \pause ideals in this algebra are codes. \end{frame} \subsection{Generalized quadratic residue codes} \begin{frame} 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}.) \end{frame} \begin{frame} $\ell,p$ primes, $p>2$ and $\ell\geq 2$ a quadratic residue of $p$. \pause Let $Q$ = set of quadratic residues in $\fff^\times$ \pause $N$ = set of nonquadratic residues in $\fff^\times$. \pause \vskip .1in orthogonality $\implies$ $\sum_{a\in \fff^\times}(\frac{a}{p})=0$ $\implies$ $|Q|=|N|$ $\implies$ $|Q|=\frac{1}{2}|\fff^\times|=|N|$. \end{frame} \begin{frame} Enumerate $\fff=GF(p)=\{0,1,...,p-1\}$. \pause Identify $GF(\ell)^p$ with \[ \{(f(0),f(1),...,f(p-1))\ |\ f:\fff\rightarrow GF(\ell)\}. \] \pause The {\bf generalized quadratic residue code} is the kernel of the F.T. on $Q$: \[ C_Q(\fff,F)=\{ (f(0),f(1),...,f(p-1))\ |\ FT_f(a)=0,\ \ \forall a\in Q\}. \] \pause Analogous GQR code for the nonresidues: \[ C_N(\fff,F)=\{(f(0),f(1),...,f(p-1))\ |\ FT_f(a)=0,\ \ \forall a\in N\}. \] \end{frame} \begin{frame} Let $Q=\{a_1,...,a_r\}$ (so $r=\frac{p-1}{2})$. \pause 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) \] \end{frame} \begin{frame} %\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}. \] \pause Determining $d$ for a quadratic residue code with $p$ ``large'' is a very hard problem. For example, recently M. Grassl published some tables of values $[n,k,d]$ for quadratic residue codes with $\ell=2,3$ and $p\leq 167$. \pause Another hard problem for these codes is to determine which coordinates the information bits lie in. \end{frame} \begin{frame} 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. \pause {\bf Definition} %\begin{definition} {\bf dual code} of $C$ is: \[ C^\perp = \{ {\mathbf v}\in \fff^n\ |\ {\mathbf v}\cdot {\mathbf c}=0, \ \forall {\mathbf c}\in C\}. \] \pause A code satisfying $C^\perp = C$ is called {\bf self-dual}. %\end{definition} \end{frame} \begin{frame} {\bf Lemma}: %\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. \] \pause \[ {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} \end{frame} \begin{frame} {\bf 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\}, \] \pause \[ \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). \end{frame} \begin{frame} Even more interesting is the fact that these codes have large automorphism groups. \pause {\bf Theorem}: %\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} \pause \vskip .1in This theorem says that $\hat{C}_Q(\fff,F)$ may be regarded as a representation space of $PSL(2,p)$. \end{frame} } \section{Groups} \begin{frame} \begin{center} $G$-modules \end{center} Let $G$ be a finite group, $F$ a field. \vskip .1in \pause A finite-dimensional $F$-vector space $V$ is a {\bf modular representation} of $G$ over $F$ or a (left) {\bf $F[G]$-module} if there is a homomorphism $\rho:G\rightarrow Aut_F(V)$. \vskip .1in \pause We say $V$ is {\bf irreducible} or {\bf simple} if there is no non-zero proper subspace $V'$ of $V$ which is $G$-invariant. \end{frame} \begin{frame} {\bf Example}: Let $G=C_2=\{1,\epsilon\}$, the cyclic group of order $2$, and $V=F^2$. \pause $G$ acts on $V$ by $1 (x,y)=(x,y)$ and $\epsilon (x,y)=(y,x)$, for $(x,y)\in V$. \pause $V$ is not an irreducible $G$-module since $V'=\{(x,x)\}\subset $ is a proper $G$-invariant subspace. \pause Indeed, \[ (x,y)=(x+y,x+y)+(\frac{x-y}{2},\frac{y-x}{2}). \] \end{frame} \begin{frame} {\bf Mascke's Theorem}: If $F$ is algebraically closed and either char$(F)=0$ or char$(F)=p$ does not divide $G$ then $V$ is semi-simple (i.e., for all $g\in G$, $\rho(g)$ is conjugate to a block-diagonal matrix). \vskip .1in \pause We say a representation $(\rho,V)$ is {\bf equivalent} to $(\rho',V')$ if there is an isomorphism (of $F$-vector spaces) \[ A:V\rightarrow V' \] such that, for all $v\in V$ and all $g\in G$, \[ \rho(g)Av=A\rho(g)v. \] ($A$ ``intertwines'' $\rho$ or $A:V\rightarrow V'$ is ``$G$-equivariant'') \end{frame} \begin{frame} Up to equivalence, each semi-simple representation decomposes into a direct sum of irreducibles. \pause If $\rho$ is a representation of $G$ then the {\bf character} of $\rho$ is the function ${\rm tr}\, \rho :G\rightarrow F$. \pause ${\rm tr}\rho$ is constant on each conjugacy class. \pause Set of conjugacy classes of $G$: \[ G_*=\{\gamma = \{x^{-1}gx\ |\ x\in G\}\} \] \pause set of equivalence classes of irreducible representations of $G$: $G^*$ \vskip .1in \pause \noindent {\bf Fact}: $|G_*|=|G^*|$. \end{frame} \begin{frame} \noindent {\bf Examples}: (1) If $G=S_n$ then there is a {\it natural} bijection between $G_*$ and $G^*$. \pause (2) $G$ a finite abelian group. $\implies$ $G_*=G$ and every irreducible representation of $G$ is $1$-dimensional. Once you fix a decomposition of $G$ into cyclics (by the fundamental theorem of abelian groups), there is a {\it natural} bijection between $G_* \cong G^*$. \vskip .1in \pause In general, there isn't a natural bijection (known). \end{frame} \begin{frame} \[ (\chi,\chi')= \frac{1}{|G|}\sum_{g\in G} \chi(g)\overline{\chi'(g)}. \] is the {\bf Schur inner product} between 2 characters. \pause \noindent {\bf Schur-Brauer Theorem}: Assume $F$ is algebraically closed and either characteristic $0$ or char$(F)=p$ does not divide $G$. Then the set $G^*$ \pause (a) is orthonormal with respect to the Schur inner product and \pause (b) spans the vector space of all class functions on $G$. \vskip .1in \pause (If either ``algebraically closed'' or the characteristic condition are dropped then the result can be false.) \end{frame} \section{Algebraic geometric codes} \begin{frame} \begin{center} AG codes \end{center} In the early 1980's a Russian mathematician \color{blue} V. D. Goppa \normalcolor discovered a way to associated to each ``nice'' algebraic curve $X$ defined over a finite field a family of error-correcting codes $C=C_X(D,E)$ whose length, dimension, and minimum distance distance can either be determined precisely or estimated in terms of some geometric parameters of the algebraic curve you started with. \pause \vskip .2in $\fff$ = finite field \vskip .1in $F$ = alg closure of $\fff$ \pause \vskip .1in We introduce Goppa's idea in the case of $X=\ppp^1$. \end{frame} %\subsection{The projective line} \begin{frame} \begin{center} {\bf The projective line} \end{center} \pause What is a point on this curve $\ppp^1$? \pause \vskip .1in $\ppp^1$ = set of lines through the origin in $F^2$. \pause \vskip .1in two points in $F^2-\{(0,0)\}$ are ``equivalent'' $\iff$ they lie on the same line \pause \vskip .1in $y\not=0$ $\implies$ equivalence class of $(x,y)$ denoted $[x/y:1]$, . \pause $y=0$ $\implies$ equivalence class of $(x,y)$ denoted $[1:0]$. \end{frame} \begin{frame} $GL(2,\ccc)$ acts by: $z\longmapsto \frac{az+b}{cz+d}$, $\left( \begin{array}{cc} a & b\\ c & d \end{array} \right)\in GL(2,\ccc)$. \pause \vskip .2in Similarly, $PGL(2,F)$ acts on $X=\ppp^1$. \pause \vskip .2in In fact, ${\rm Aut}(\ppp^1)=PGL(2,F)$. \end{frame} \subsection{Riemann-Roch spaces} \begin{frame} $F$-valued rational functions on the $\ppp^1$, denoted $F(\ppp^1)$. \pause \vskip .1in $x$ a ``local coordinate'' on $\ppp^1$ $\implies$ $F(\ppp^1)\cong F(x)$. \pause \vskip .1in {\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. \end{frame} \begin{frame} {\bf divisor of $f$} = $\div(f)$ = formal sum of zeros of $f$ minus the poles. \pause \vskip .1in $D=n_1P_1+...+n_kP_k$ a divisor then $\supp(D)=\{P_1,...,P_k\}$ is the {\bf support} of $D$. \pause \vskip .1in Example: $f$ = polynomial of degree $n$ in $x$ $\implies$ $\div(f)=P_1+...+P_n-n\infty$, $\supp(\div(f)) =\{P_1,...,P_n,\infty\}$, where $zeros(f)=\{P_1,...,P_n\}$. \pause \vskip .2in The abelian group of all divisors is denoted $\Div(\ppp^1)$. \end{frame} \begin{frame} $X=\ppp^1$ \pause $F(X)$ = function field of $X$ \pause $D$ a divisor on $X$ \pause \vskip .1in Riemann-Roch space $L(D)$: \[ L(D)=L_X(D)= \{f\in F(X)^\times \ |\ \div(f)+D\geq 0\}\cup \{0\}, \] \pause These are the rational functions whose zeros and poles are ``no worst than those specified by $D$''. \pause \vskip .1in Let $\ell(D)$ denote its dimension. \end{frame} \subsection{AG codes} \begin{frame} $X$ a curve, $D\in Div(X)$, $P_1,...,P_n\in X(\fff)$ distinct points and $E=P_1+...+P_n\in \Div(X)$. \pause \vskip .1in Assume $\supp(D)\cap \supp(E)=\emptyset$. \pause \vskip .2in Choose an $\fff$-rational basis for $L(D)$ and let $L(D)_\fff$ denote the corresponding vector space over $\fff$. (This is a set of functions in the local coordinated on $X=\ppp^1$.) \pause \vskip .1in This explicit data determines a code as follows. \end{frame} \begin{frame} Goppa's idea in the case of $X=\ppp^1$. \pause The {\bf algebraic geometric code} (AG code): \[ C=C(D,E)=\{(f(P_1),...,f(P_n))\ |\ f\in L(D)_\fff\}. \] \pause \vskip .1in $C$ = image of $L(D)_\fff$ under the evaluation map \[ \begin{array}{c} \eval_E:L(D)\rightarrow F^n,\\ f \longmapsto (f(P_1),...,f(P_n)). \end{array} \] \pause \vskip .1in {\it Note that describing $C$ explicitly depends on the ability to explicitly compute a basis of $L(D)$}. \end{frame} {\comment{ \subsection{The action of $G$ on $L(D)$} \label{sec:1} \begin{frame} $X=\ppp^1/F$ \pause \vskip .2in ${\rm Aut}(X)=PGL(2,F)$ \pause \vskip .2in Action of ${\rm Aut}(X)$ on $F(X)$: \[ \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))$. \end{frame} \begin{frame} ${\rm Aut}(X)$ acts on the group $\Div(X)$ of divisors of $X$ \pause \vskip .3in $D\in \Div(X)^G$ $\implies$ $G$ acts on $L(D)$: \[ \rho:G \rightarrow \Aut(L(D)). \] \end{frame} }} \begin{frame} A basis for the Riemann-Roch space for $\ppp^1$: \pause Let \[ m_P(x)= \left\{ \begin{array}{cc} x, & P=[1:0]=\infty,\\ (x-p)^{-1}, & P=[p:1]. \end{array} \right. \] \pause {\bf Lemma}: \begin{itemize} \item[(a)] $D>0$ $\implies$ \[ \{ 1,m_{P_i}(x)^k\ |\ 1\leq k\leq a_i, 0\leq i\leq s\} \] is a basis for $L(D)$. \vskip .1in \pause \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)$. \end{itemize} \end{frame} \begin{frame} In general, we have the following result. \vskip .1in %\begin{theorem} %\label{thrm:P1} {\bf Theorem}: 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. \pause 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. \end{frame} \begin{frame} \begin{itemize} \item[(a)] $D>0$ $\implies$ \[ \rho\cong 1\oplus_{i=1}^m \rho_i, \] where $\rho_i$ is a monomial 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$. \pause \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} \end{frame} \begin{frame} {\it The goal is to extend this result to other curves over arbitrary fields.} \pause \vskip .1in Here is an example of a result which goes in this direction. \pause \vskip .1in Let $p\geq 3$ be a prime, $F=GF(p)$, and let $X$ denote the curve defined by \[ y^2=x^p-x. \] This has genus $\frac{p-1}{2}$ and has $p+1$ $F$-rational points. \pause \vskip .1in The automorphism group $\overline{G}=\Aut_F(X)$ is (by G\"ob, a student of Stichtenoth) $\cong SL(2,p)$. \end{frame} \begin{frame} Let $P_1=(1:0:1)$ and let $H$ be its stabilizer in $\overline{G}$. $H$ is a solvable group of order $2p(p-1)$. \pause For each $m\geq 1$, the Riemann-Roch space of $D=mP_1$ has a basis consisting of monomials, \[ x^iy^j,\ \ \ \ \ \ 0\leq i\leq p-1,\ j\geq 0,\ 2i+pj\leq m. \] \pause Let $\rho:H\rightarrow Aut(L(D))$ denote the action of $H$ on $L(D)$, $D=P_1$. \pause \vskip .1in {\bf Observation} The semisimplification $\rho_{ss}$ of the representation $\rho$ of $H$ acting on $L(D)$ is the direct sum of one-dimensional representations of $H$. \end{frame} \begin{frame} Much more general results than this are desired. \pause \vskip .1in \color{blue} {\bf Conjecture}: \normalcolor Consider a non-singular hyperelliptic curve $X$ defined by $y^2=h(x)$, where $h(x)$ is a polynomial of odd degree $d>2$ with no double roots. \vskip .1in \pause Assume $P_i$, $i=0,1,...,s-1$, denote affine points on $X$ which: (a) are not ramification points, and \pause (b) have the property that if $i\not= j$ then $x_i\not= \pm x_j$, for all $i,j$. \vskip .1in \pause Let \[ e=(e_0,...,e_{s-1})\in \zzz^{s}, \] \[ D=e_0P_0+...+e_{s-1}P_{s-1}. \] \end{frame} \begin{frame} \begin{itemize} \item (1) For any $|e|>d/2$, we have \[ \dim L(D)=|e|+2-[\frac{d+1}{2}]. \] \pause Moreover, there is a basis $\{b_i\ |\ 1\leq i\leq \dim L(D)\}$ of $L(D)$, where each $b_i$ is a linear combination of functions of the form \[ f_{0,D' }(x,y)=\frac{y}{\prod_{i=0}^{s-1}(x-x_i)^{e'_i} } \] and \[ f_{1,D'}(x,y)=\frac{1}{\prod_{i=0}^{s-1}(x-x_i)^{e'_i} } , \] for some $D'=e'_0P_0+...+e'_{s-1}P_{s-1}$. \pause \item (2) If $0\leq |e|\leq \frac{d}{2}$, we have $L(D)=k$. \end{itemize} \end{frame} %\subsection{The Goppa codes} \begin{frame} Let $D \in Div(X)^G$, $\supp(D)\subset X(\fff)$. \vskip .1in \pause Let $P_1,...,P_n\in X(\fff)$ be distinct, $E=P_1+...+P_n\in \Div(X)^G$, $\supp(D)\cap \supp(E)=\emptyset$. \pause \vskip .1in The group $G=\Aut_\fff(X)$ acts on $C=C(D,E)$ 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)$. \end{frame} \begin{frame} Observe that this map, denoted $\phi(g)$, is well-defined. \pause \vskip .1in $\phi(g)$ induces a representation: \[ \phi:G\rightarrow \Aut(C)\cong GF_k(F). \] \pause \vskip .1in General conditions under which $\phi$ is injective are now known. \pause \vskip .1in \color{blue} When $p\equiv 1\pmod 4$ and $D$ is a $G$-equivariant divisor on $y^2=x^p-x$ over $GF(p)$ then the decomposition of the $G$-module $L(D)$ (and hence the associated code, when $\phi, {\rm eval}_E$ are injective) is known. \normalcolor \pause \vskip .2in \color{red} Wanted: \normalcolor More properties of this representation! \end{frame} \begin{frame} \begin{center} \color{blue} The End! \normalcolor \end{center} \end{frame} \end{document} %\begin{frame} \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{frame} \end{document} \section{Appendix: Representation-theoretic background} Let $G$ be a finite group, $F$ a field. A finite-dimensional $F$-vector space $V$ is a {\bf modular representation} of $G$ over $F$ or a (left) {\bf $F[G]$-module} if there is a homomorphism $\rho:G\rightarrow Aut_F(V)$. When $F=\ccc$ we drop the adjective ``modular''. We say $V$ is {\bf irreducible} or {\bf simple} if there is no non-zero proper subspace $V'$ of $V$ which is $G$-invariant. \noindent {\bf Example}: Let $G=C_2=\{1,\epsilon\}$, the cyclic group of order $2$. This acts on $V=F^2$ by $1 (x,y)=(x,y)$ and $\epsilon (x,y)=(y,x)$, for $(x,y)\in V$. It is not irreducible since $V'=\{(x,x)\}$ is $G$-invariant. \noindent {\bf Mascke's Theorem}: If $F$ is algebraically closd and either char$(F)=0$ or char$(F)=p$ does not divide $G$ then $V$ is semi-simple (i.e., for all $g\in G$, $\rho(g)$ is conjugate to a block-diagonal matrix). We say a representation $(\rho,V)$ is {\bf equivalent} to $(\rho',V')$ if there is an isomorphism (of $F$-vector spaces) $A:V\rightarrow V'$ such that, for all $v\in V$ and all $g\in G$, $\rho(g)Av=A\rho(g)v$. Up to equivalence, each semi-simple representation decomposes into a direct sum of irreducibles. If $\rho$ is a representation of $G$ then the {\bf character} of $\rho$ is the function ${\rm tr}\, \rho :G\rightarrow F$. Since ${\rm tr}(A^{-1}BA)={\rm tr}(B)$, ${\rm tr}\rho$ is constant on each conjugacy class. If \[ G_*=\{\gamma = \{x^{-1}gx\ |\ x\in G\}\} \] denotes the set of conjugacy classes of $G$ then ${\rm tr}\, \rho :G_*\rightarrow F$. Let $G^*$ denote the set of equivalence classes of irreducible representations of $G$. \noindent {\bf Fact}: $|G_*|=|G^*|$. \noindent {\bf Remark}: If $G=S_n$ then there is a {\it natural} bijection between $G_*$ and $G^*$. In general, there isn't one (known). \noindent {\bf Example}: Let $G$ be a finite abelian group. Then $G_*=G$ and every irreducible representation of $G$ is $1$-dimensional. Once you fix a decomposition of $G$ into cyclics (by the fundamental theorem of abelian groups), there is a natural bijection between $G_*$ and $G^*$. Let \[ (\chi,\chi')= \frac{1}{|G|}\sum_{g\in G} \chi(g)\overline{\chi'(g)}. \] This is the {\bf Schur inner product}. \noindent {\bf Schur-Brauer Theorem}: Assume $F$ is algebraically closed and either characteristic $0$ or char$(F)=p$ does not divide $G$. Then the set $G^*$ is orthonormal with respect to the Scur inner product and spans the vector space of all class functions on $G$. (If either ``algebraically closed'' or the characteristic condition are dropped then the result can be false.) \noindent {\bf Example}: Let $G=C_2\times C_2 =\{1,\alpha,\beta,\alpha\beta\}$. This group has character table \[ \begin{array}{c|cccc} & 1 & \alpha & \beta & \alpha\beta \\ \hline \chi_1 & 1 & 1 & 1 & 1 \\ \chi_2 & 1 & 1 & -1 & -1 \\ \chi_3 & 1 & -1 & 1 & -1 \\ \chi_4 & 1 & -1 & -1 & 1 \end{array} \] It is easy to check that the rows are orthogonal, as predicted by the Schur-Braur Theorem. If $(\rho,V)$ is a representation of $G$, let $[V]$ denote the equivalence class of $V$. Let $R(G)$ denote the Grothendieck group of all formal finite sums $\sum_i a_i [V_i]$. \noindent {\bf Fact}: $R(G)\cong \zzz [G^*]$.