%9-27-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[October, 2005]{\color{blue} Codes, Groups, and Curves \normalcolor\\ \ \\ {\footnotesize{%Wayne State University\\ Michigan\\ 10-10-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} \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} \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} 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} 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} 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} Here is a picture of a code. \vskip .3in \begin{center} \unitlength=1.000000pt \begin{picture}(150.00,150.00)(0.00,0.00) %\put(0.00,0.00){$\bullet$} \put(0.00,0.00){$\circ$} \put(0.00,25.00){$\bullet$} \put(0.00,50.00){$\bullet$} %\put(0.00,75.00){$\bullet$} \put(0.00,75.00){$\circ$} \put(0.00,100.00){$\bullet$} \put(0.00,125.00){$\bullet$} %\put(0.00,150.00){$\bullet$} \put(0.00,150.00){$\circ$} \put(25.00,0.00){$\bullet$} \put(25.00,25.00){$\bullet$} \put(25.00,50.00){$\bullet$} \put(25.00,75.00){$\bullet$} \put(25.00,100.00){$\bullet$} \put(25.00,125.00){$\bullet$} \put(25.00,150.00){$\bullet$} \put(50.00,0.00){$\bullet$} \put(50.00,25.00){$\bullet$} \put(50.00,50.00){$\bullet$} \put(50.00,75.00){$\bullet$} \put(50.00,100.00){$\bullet$} \put(50.00,125.00){$\bullet$} \put(50.00,150.00){$\bullet$} %\put(75.00,0.00){$\bullet$} \put(75.00,0.00){$\circ$} \put(75.00,25.00){$\bullet$} \put(75.00,50.00){$\bullet$} %\put(75.00,75.00){$\bullet$} \put(75.00,75.00){$\circ$} \put(75.00,100.00){$\bullet$} \put(75.00,125.00){$\bullet$} %\put(75.00,150.00){$\bullet$} \put(75.00,150.00){$\circ$} \put(100.00,0.00){$\bullet$} \put(100.00,25.00){$\bullet$} \put(100.00,50.00){$\bullet$} \put(100.00,75.00){$\bullet$} %\put(100.00,75.00){\circle{200}} %- useless, too small \put(103.00,79.00){\oval(52,52)[t]} %top \put(103.00,79.00){\oval(52,52)[b]} %bottom \put(100.00,100.00){$\bullet$} \put(100.00,125.00){$\bullet$} \put(100.00,150.00){$\bullet$} \put(125.00,0.00){$\bullet$} \put(125.00,25.00){$\bullet$} \put(125.00,50.00){$\bullet$} \put(125.00,75.00){$\bullet$} \put(125.00,100.00){$\bullet$} \put(125.00,125.00){$\bullet$} \put(125.00,150.00){$\bullet$} %\put(150.00,0.00){$\bullet$} \put(150.00,0.00){$\circ$} \put(150.00,25.00){$\bullet$} \put(150.00,50.00){$\bullet$} %\put(150.00,75.00){$\bullet$} \put(150.00,75.00){$\circ$} \put(150.00,100.00){$\bullet$} \put(150.00,125.00){$\bullet$} %\put(150.00,150.00){$\bullet$} \put(150.00,150.00){$\circ$} \end{picture} \end{center} \end{frame} \begin{frame} The {\bf nearest neighbor decoding algorithm}: {\small{ {\fontfamily{phv}\selectfont \begin{enumerate} \item Input: A received vector $\mathbf{v}\in \fff^n$ with $t$ errors. Output: A codeword $\mathbf{c}\in C$ closest to $\mathbf{v}$. \item Enumerate the elements of the ball $B_t(\mathbf{v})$ about the received word. Set $\mathbf{c}=$``fail''. \item For each $\mathbf{w}\in B_t(\mathbf{v})$, check if $\mathbf{w}\in C$. If so, put $\mathbf{c}=\mathbf{w}$ and break to the next step; otherwise, discard $\mathbf{w}$ and move to the next element. \item Return $\mathbf{c}$. \end{enumerate} }}} Note ``fail'' is not returned unless $t>[\frac{d-1}{2}]$, by the above lemma. \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} \section{Groups} \begin{frame} Let $G$ be a finite group, $F$ a field. \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)$. When $F=\ccc$ we drop the adjective ``modular''. \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 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). \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) \pause Up to equivalence, each semi-simple representation decomposes into a direct sum of irreducibles. \end{frame} \begin{frame} 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 $G^*$ = set of equivalence classes of irreducible representations of $G$. \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) 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 {\it natural} bijection between $G_* \cong G^*$. \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 is orthonormal with respect to the Schur inner product and \pause spans the vector space of all class functions on $G$. \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} 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 generator matrix for $C$ $\iff$ basis of $L(D)$}. \pause length$(C)=\deg(E)=n$. \pause $\eval_E$ $1-1$ $\implies$ $\dim_{\fff}(C)=\dim_F(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 GL_k(F),\ \ \ \ \ \ k=\dim(C). \] \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 $C=C(D,E)$) 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^*]$.