
\documentclass{beamer}
\usepackage{amscd,amssymb,epsfig}
\def\bF{{\mathbb F}}
\def\a{\alpha}
\def\Fqstar{\bF_q^{\,*}}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\N{\mathbb N}
\newcommand{\maintitle}[1]{\begin{center}\Large #1 \end{center}}
\newcommand{\slidetitle}[1]{\begin{par}\Large #1\end{par}}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}

\mode<presentation>
{
  \usetheme{Warsaw}

  \setbeamercovered{opaque}
}


\usepackage[english]{babel}

\usepackage[latin1]{inputenc}

\usepackage{times}
\usepackage[T1]{fontenc}

\title[Toric Codes]
{Toric Codes}

\author
{John B. Little}

\institute[College of the Holy Cross]
{
  Department of Mathematics and Computer Science\\
  College of the Holy Cross\\
  $\ $\\
  Joint work with Hal Schenck (U. Illinois), Ryan Schwarz (U. Connecticut), Alex Simao (Holy Cross)
}

\date[AMS 2008]
{AMS Special Session on Linear Codes Over Rings and Modules -- Kalamazoo, October 17, 2008}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}{Outline}
  \tableofcontents

\end{frame}

\section{Toric Code Basics}

\subsection{Codes from Polytopes}

\begin{frame}{The Definition And A First Example}

Introduced by J. Hansen $\sim 1997$ -- elementary
description:

\begin{itemize}
\item<1-> Let $P$ be an integral convex polytope in $\R^m$, $m \ge 1$.
\item<2-> Points $\beta$ in the finite set $P\cap \Z^m$ correspond to
monomials $x^\beta$ (multi-index notation)
\item<3-> Let $L_P = {\rm Span}\{ x^\beta : \beta \in P \cap \Z^m\}$.
\item<4-> Define
\begin{eqnarray*}
ev : L_P &\to& \bF^{\, (q-1)^m}_q\\
       f &\mapsto& (f(\gamma): \gamma \in (\Fqstar)^m)
\end{eqnarray*}
Image is the toric code $C_P(\bF_q)$.
\item<5-> Example:  $RS(k,q)$ is the
case $P = [0,k-1]\subset \R$ since
$L_P = {\rm Span}\{1,x,\ldots,x^{k-1}\}$.
\end{itemize}

\end{frame}

\begin{frame}{Why Are They Interesting?}

\begin{itemize}
\item<1-> Have many properties parallel to RS codes,
e.g. they are ``$m$-dimensional cyclic'' codes (set of codewords
is closed under a large automorphism group).
\item<2-> Computer searches by D. Joyner (USNA) showed that
some very good $m = 2$ toric codes exist (better than
any previously known codes in standard databases).
A number of other isolated very good examples found too.
\item<3-> (debatable, maybe!) Can apply lots of nice
algebraic geometry to study their properties (toric varieties,
intersection theory, line bundles, Riemann-Roch theorems)
\end{itemize}
\end{frame}

\begin{frame}{When Are Toric Codes Equivalent?}

Usually take $P \subset [0,q-2]^m \simeq ({\mathbb Z}_{q-1})^m$.

\begin{thm} If $S = P\cap {\mathbb Z}^m$ and
$S' = T(S)$ for some $T = {\rm AGL}(m,{\mathbb Z}_{q-1})$, the
resulting evaluation code from $S'$ is monomially equivalent
to $C_P({\bF_q})$.
\end{thm}

\emph{Note:} $S'$ may not be $P' \cap {\mathbb Z}^m$
for a convex polytope $P'$.

\vskip 10pt
(Monomial equivalence: There is an $n\times n$ permutation
matrix $\Pi$ and an $n\times n$ invertible diagonal matrix
$Q$ such that $G' = GQ\Pi$; implies that parameters are the
same.)
\end{frame}

\begin{frame}{Small Needles In Huge Haystacks!}

\begin{itemize}
\item<1-> For $m = 3$, $q = 5$, the generating function for the number of
${\rm AGL}(3,{\mathbb Z}_4)$-orbits on subsets
of ${\mathbb Z}_4^3$ of size $k$ is:
\begin{eqnarray*} &&1 + x + 2x^2 + 4x^3 + 16x^4 + 37x^5 + \\
                  &&147x^6 + 498x^7 + 2128x^8 + 8790x^9 + \\
                  &&39055x^{10} + 165885 x^{11} + \\
                  &&678826 x^{12} + 2584627x^{13} + \cdots
\end{eqnarray*}
\item<2-> The ``middle term'' here is $333347580600 x^{32}$.
\item<3-> ``Most'' of these subsets give quite uninteresting codes.
\item<4-> But \emph{one} of the $2128$ orbits for $k = 8$ gives codes
with $d = 42$ (best previously known: $d = 41$ according
to Grassl's table).
\end{itemize}
\end{frame}

\section{Tools From Algebraic Geometry}
\subsection{Toric Varieties}

\begin{frame}{Toric Codes And Toric Varieties}

\begin{itemize}
\item<1-> A polytope $P$ specifies a normal fan $\Sigma = \Sigma_P$, hence
an abstract toric variety $X = X_\Sigma$.
\item<2-> Also get a line bundle ${\mathcal L} = {\mathcal L}_P$
on $X$ specified by $P$.
\item<3-> Subpolytopes $P_i$ correspond to subspaces of $H^0(X,{\mathcal L})$.
\item<4-> In case $m = 2$, main results of
L. and Schenck {\it ``Toric surface codes and Minkowski sums''} show that
for $q$ sufficiently large, $d(C_P(\bF_q))$ can be
bounded above and below by looking at subpolygons
$P'\subseteq P$ that decompose as {\it Minkowski sums}.
\end{itemize}
\end{frame}

\begin{frame}{The Lower Bound}
\begin{thm}
Let $\ell$ be the largest positive integer such that there is some
$P' \subseteq P$ that decomposes as a Minkowski sum
$P' = P_1 + P_2 + \cdots + P_\ell$ with nontrivial $P_i$.
For all $q >> 0$, there is some $P'\subseteq P$ of this form such that
$$d(C_P(\bF_q)) \ge \sum_{i=1}^\ell d(C_{P_i}(\bF_q)) - (\ell-1)(q-1)^2.$$
\end{thm}
\end{frame}

\begin{frame}{Intuition For Proof}
\begin{itemize}
\item<1-> Minkowski-decomposable subpolygons $\Leftrightarrow$ {\it reducible sections}
$f_1f_2$ (Newton polygon of a product is the Minkowski sum).

\item<2-> Hasse-Weil upper and lower bounds for a curve $Y$:
$$q + 1 - 2g(Y) \sqrt{q} \le |Y(\bF_q)| \le q + 1 + 2g(Y)\sqrt{q}$$
$\Rightarrow$ when $q > $ (a crude
but explicit lower bound), reducible curves with $\ell$ components
must have more $\bF_q$-rational points than those with
$m < \ell$ components
\item<3-> Bounds have been improved by Soprounov and Soprounova.
\end{itemize}
\end{frame}

\subsection{An Example}

\begin{frame}{An Interesting Polygon}

\begin{columns}
\column{.4\textwidth}
\begin{figure}
\begin{picture}(70,70)(0,0)
\put(5,0){\line(0,1){70}}
\put(0,5){\line(1,0){70}}
\put(25,5){\circle*{6}}
\put(45,5){\circle*{6}}
\put(5,25){\circle*{6}}
\put(25,25){\circle*{6}}
\put(45,25){\circle*{6}}
\put(25,45){\circle*{6}}
\put(45,45){\circle*{6}}
\put(65,45){\circle*{6}}
\put(65,65){\circle*{6}}
\put(25,5){\line(1,0){20}}
\put(45,5){\line(1,2){20}}
\put(65,45){\line(0,1){20}}
\put(65,65){\line(-2,-1){40}}
\put(25,45){\line(-1,-1){20}}
\put(5,25){\line(1,-1){20}}
\end{picture}
\caption{The polygon $P$}
\end{figure}

$P \subset [0,q-2]^2$ for all $q \ge 5$.
\column{.6\textwidth}
\begin{itemize}
\item $P$ contains
$P' = \mbox{conv}\{(1,0),(2,0),(1,2),(2,2)\}$
($ = P_1 + P_2 + P_3$, $P_i$ line segments) and
$P'' = \mbox{conv}\{(1,0),(1,1),(3,2),(3,3)\}$
(similar).
\item No other decomposable $Q \subset P$
with more than three Minkowski summands
\item $\Rightarrow$ for $q > \#(P) + 3 = 12$,
$$d(C_P(\bF_q)) \ge (q-1)^2 - 3(q-1).$$
\end{itemize}
\end{columns}
\end{frame}

\begin{frame}{Reducible Curves}
From $P'$ we obtain $x(x-a)(y-b)(y-c) = 0$. If $a,b,c\in \Fqstar$
and $b\ne c$, then $3(q-1) - 2$ zeroes in $(\Fqstar)^2$.
Hence,
$$d(C_P(\bF_q)) \le (q-1)^2 - 3(q-1) + 2$$
and 
$d(C_P(\bF_q)) \ge (q-1)^2 - 3(q-1), q >> 0.$
Computations using Magma show that
\begin{eqnarray*}
d(C_P(\bF_5)) = 6^{(*)} & vs. & 4^2 - 3\cdot 4 + 2 = 6\\
d(C_P(\bF_7)) = 20 & vs. & 6^2 - 3\cdot 6 + 2 = 20\\
d(C_P(\bF_8)) = 28 & vs. & 7^2 - 3\cdot 7 + 2 = 30\\
d(C_P(\bF_9))  = 42 & vs. & 8^2 - 3\cdot 8 + 2 = 42\\
d(C_P(\bF_{11}))  = 72 & vs. & 10^2 - 3\cdot 10 + 2 = 72
\end{eqnarray*}
(${}^{(*)}$ code over $\bF_5$ is best known for $n = 16, k = 9$)
\end{frame}

\begin{frame}{More On $q = 8$}
Where does a codeword with $49 - 28 = 21$
zero entries come from?  Magma: exactly 49
such words.  One of them comes, for
instance, from the evaluation of
\begin{eqnarray*}
y + x^3y^3 + x^2 & \equiv & y(1 + x^3 y^2 + x^2 y^6) \\
                 & \equiv & y(1 + x^3 y^2 + (x^3 y^2)^3)
\end{eqnarray*}

Here congruences are mod $\langle x^7 - 1, y^7 - 1\rangle$,
the ideal of the
$\bF_8$-rational points of the 2-dimensional torus.  So
$1 + x^3 y^2 + (x^3 y^2)^3$ has exactly the same zeroes in
$(\bF_8^{\,*})^2$ as $y + x^3y^3 + x^2$.
\end{frame}

\begin{frame}{Arithmetic Of $\bF_8$ Matters}
Note: $1 + u + u^3$ is one of the two irreducible polynomials
of degree 3 in $\bF_2[u]$, hence
$$\bF_8 \cong \bF_2[u]/\langle 1 + u + u^3\rangle.$$
If $\beta$ is a root of $1 + u + u^3 = 0$ in $\bF_8$,
then $1 + x^3 y^2 + (x^3 y^2)^3 =$
$$(x^3 y^2 - \beta)(x^3 y^2 - \beta^2)(x^3 y^2 - \beta^4)$$
and there are exactly $3\cdot 7 = 21$ points in $(\bF_8^{\,*})^2$
where this is zero.  Still a
sort of {\it reducibility} that produces a section with
the largest number of zeroes here, even though the
reducibility only appears when we look
modulo the ideal $\langle x^7 - 1, y^7 - 1\rangle$ (!).

Similar phenomena in many other cases for small $q$.
\end{frame}

\section{Higher-dimensional Polytopes and Vandermonde Matrices}

\subsection{The Connection}

\begin{frame}{Motivation -- Reed-Solomon Case}

Square submatrices of the generator matrix $G$ for a Reed-Solomon
code are usual (one-variable) Vandermonde matrices:

$$V = \begin{pmatrix}1 & 1 & \cdots & 1\\
              \a^{j_1} & \a^{j_2} & \cdots & \a^{j_k}\\
              \vdots &\vdots & \ddots & \vdots\\
              (\a^{j_1})^{k-1} &  (\a^{j_2})^{k-1} & \cdots &  (\a^{j_k})^{k-1}\\
      \end{pmatrix}$$

\end{frame}

\begin{frame}{General Vandermondes}
\begin{itemize}
\item<1-> Let $P$ be an integral convex polytope, and
suppose $P \cap \Z^m = \{e(i) : 1 \le i\le \#(P)\}$.
\item<2-> Let $S = \{p_j : 1\le j\le \#(P)\}$
be any set of $\#(P)$ points in $(\Fqstar)^m$.
\item<3-> Picking orderings, define $V(P; S)$, the
{\it Vandermonde matrix} associated to $P$ and $S$, to be the
$\#(P)\times \#(P)$ matrix
$$V(P; S) = \left(p_j^{e(i)}\right),$$
where $p_j^{e(i)}$ is the value of the monomial $x^{e(i)}$ at
the point $p_j$.
\end{itemize}
\end{frame}

\begin{frame}{An Example}
Let $P = \mbox{conv}\{(0,0),(2,0),(0,2)\}$
in $\R^2$, and $S = \{(x_j,y_j)\}$ be any set of 6 points in
$(\Fqstar)^2$. For one particular choice of ordering of the
lattice points in $P$, we have $V(P; S) =$
$$ \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1\\
                  x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \\
                  y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\
                  x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2 & x_6^2 \\
                  x_1y_1& x_2y_2 & x_3y_3 & x_4y_4 & x_5y_5 & x_6y_6 \\
                  y_1^2 & y_2^2 & y_3^2 & y_4^2 & y_5^2 & y_6^2 \\
                  \end{pmatrix}$$
\end{frame}


\subsection{Estimating $d$ of a Toric Code}

\begin{frame}{Minimum Distance Theorem}
From L., Schwarz, {\it ``Toric Codes and Vandermonde Matrices''}

\begin{thm} Let $P \subset \R^m$ be an integral convex
polytope.  Let $d$ be a positive integer and assume that
in every set
$T \subset (\Fqstar)^m$ with $|T| = (q-1)^m - (d - 1)$
there exists some $S \subset T$ with $|S| = \#(P)$
such that $\det V(P; S) \ne 0$.
Then the minimum distance satisfies $d(C_P) \ge d$.
\end{thm}

Proof:  For all $S$, $\det V(P;S) \ne 0 \Rightarrow$ homogeneous
linear system has only the trivial solution so there are no
nonzero codewords with $(q-1)^m - (d - 1)$ zero entries.  Hence
every nonzero codeword has $\ge d$ nonzero entries.
\end{frame}

\begin{frame}{Codes From Simplices, etc.}
\begin{itemize}
\item<1-> Consider simplices of form $P_\ell = {\rm Conv}(\ell e_i : i = 1, \ldots, m)$.
\item<2-> Via a recursive determinant identity,
$\det V(P_\ell; S) \ne 0$ for ``simplicial configurations'' of points $S$ (essentially:
sets of points that look \emph{combinatorially} like the lattice points in a simplex of the
same dimension, same $\ell$)
\item<3-> Such ``simplicial configurations'' exist in any $T$ as before with
$|T| = \ell(q-1)^m + 1$, so $d(C_{P_\ell}) = (q - 1)^m - \ell(q - 1)^{m-1}$.
\item<4-> Can do something very similar for paralellotopes.
\item<5-> Also implies results for codes from many subpolytopes of these.
\end{itemize}
\end{frame}


\section*{Summary}

\begin{frame}{Summary}

  % Keep the summary *very short*.
  \begin{itemize}
  \item<1->  Toric codes are interesting and accessible (even for undergraduate projects!)
  \item<2->  But, the results on toric codes from simplices and parallelotopes show that $d$
         is often quite {\it small} relative to $k$.
  \item<3->
    It is an interesting and apparently subtle problem to
    determine criteria for polytopes (or subsets of the lattice points
    in a polytope) that yield good evaluation codes.
  \end{itemize}

\end{frame}

\appendix
\section<presentation>*{\appendixname}
\subsection<presentation>*{For Further Reading}

\begin{frame}
  \frametitle<presentation>{For Further Reading}

  \begin{thebibliography}{10}


  \beamertemplatearticlebibitems
  \bibitem{LittleSchenck}
    J. Little and H. Schenck,
    \newblock {\em Toric Codes and Minkowski Sums}
    \newblock SIAM Journal of Discrete Mathematics {\bf 20} (2006), 999--1014.
  \bibitem{LittleSchwarz}
    J. Little and R. Schwarz,
    \newblock {\em Toric Codes and Vandermonde Matrices}
    \newblock AAECC {\bf 18} (2007), 349--367.

  \end{thebibliography}
\end{frame}

\end{document}


