\documentclass{slides}
\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}

\begin{document}
\maintitle{Toric Codes}
\vfil
\begin{center}
John B. Little

{\tt little@mathcs.holycross.edu}

Department of Mathematics and Computer Science,
College of the Holy Cross

Joint work with Hal Schenck (U. Illinois), 
Ryan Schwarz (U. Connecticut), Alex Simao, HC '08.

{AMS Special Session on Codes over Rings and Modules, Kalamazoo}

{October 17, 2008}
\end{center}

\begin{slide}
\slidetitle{Outline}

\begin{enumerate}
\item Toric code basics -- Codes from polytopes
\item Tools from algebraic geometry -- toric varieties; an example
\item Higher dimensional polytopes and Vandermonde determinants -- estimating $d$
of a toric code.
\end{enumerate}

[1]  J. Little and H. Schenck {\em Toric Codes and Minkowski Sums},
     SIAM Journal of Discrete Mathematics {\bf 20} (2006), 999--1014.
    
[2]  J. Little and R. Schwarz,
     {\em Toric Codes and Vandermonde Matrices}, AAECC {\bf 18} (2007), 349--367.
     
\end{slide}



\begin{slide}
\slidetitle{\S 1. Toric Code Basics}

Introduced by J. Hansen $\sim 1997$.  Elementary
description:

\begin{itemize}
\item Let $P$ be an integral convex polytope in $\R^m$, $m \ge 1$.
\item Points $\beta$ in the finite set $P\cap \Z^m$ correspond to
monomials $x^\beta$ (multi-index notation)
\item Let $L_P = {\rm Span}\{ x^\beta : \beta \in P \cap \Z^m\}$.
\item 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 Example: $RS(k,q)$ from $P = [0,k-1]\subset \R$ since
$L_P = {\rm Span}\{1,x,\ldots,x^{k-1}\}$.
\end{itemize}
\end{slide}

\begin{slide}
\slidetitle{Why Are They Interesting?}

\begin{itemize}
\item 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 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 (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{slide}

\begin{slide}
\slidetitle{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'$.

(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$.)
\end{slide}

\begin{slide}
\slidetitle{Small Needles In Huge Haystacks!}

For $m = 3$, $q = 5$, for instance, the generating function for 
the number of
${\rm AGL}(3,{\mathbb Z}_4)$-orbits on subsets of ${\mathbb Z}_4^3$ of size $k$:
\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*}
The ``middle term'' here is:
$$333347580600 x^{32}$$
``Most'' of these subsets give quite uninteresting codes.
But for instance, {\it one} of the $2128$ orbits
of size $k = 8$ consists of codes with $d = 42$ (better
than best previously known $d = 41$ according
to Grassl's table).  Clearly need some other tools(!)
\end{slide}



\begin{slide}
\slidetitle{\S 2. Tools from algebraic geometry}

Toric codes and toric varieties

\begin{itemize}
\item A polytope $P$ defines a normal fan $\Sigma_P$, hence an 
abstract toric variety $X = X_{\Sigma_P}$.
\item Also get a line bundle ${\cal L} = {\cal L}_P$
specified by $P$.
\item Subpolytopes correspond to subspaces of $H^0(X,{\cal L})$.
\item In case $m = 2$, main results of L. and Schenck [1]
show that for $q$ sufficiently large $d(C_P(\bF_q))$ can be 
bounded above and below by looking at subpolytopes $P' \subseteq P$ that
decompose as {\it Minkowski sums}
\end{itemize}
\end{slide}

\begin{slide}
\slidetitle{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{slide}

\begin{slide}
\slidetitle{Intuition For Proof}

Minkowski-reducible subpolygons $\leftrightarrow$ {\it reducible sections}
(Newton polygon of product of polynomials is a Minkowski sum).

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.

Bounds have been improved by Soprounov and Soprounova.
\end{slide}

\begin{slide}
\slidetitle{An Interesting Polygon}

Consider $P$ as below
\begin{center}
\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}
\end{center}
$P \subset [0,q-2]^2$ for all $q \ge 5$.

\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{slide}

\begin{slide}
\slidetitle{Reducible Curves}

From $P'$ we obtain curves $x(x-a)(y-b)(y-c) = 0$. If $a,b,c\in \Fqstar$
and $b\ne c$, then $s$ has $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{slide}

\begin{slide}
\slidetitle{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{slide}
\begin{slide}
\slidetitle{Arithmetic Of $\bF_8$ Matters}

$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{slide}

\begin{slide}
\slidetitle{\S 3. Higher-dimensional Polytopes and Vandermonde Matrices}

Some motivation:

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

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

(Well-known and standard observation for studying these codes --
implies the rows of $G$ are linearly independent, for instance.)
\end{slide}

\begin{slide}
\slidetitle{General Vandermondes}

\begin{itemize}
\item Let $P$ be an integral convex polytope, and
suppose $P \cap \Z^m = \{e(i) : 1 \le i\le \#(P)\}$.
\item Let $S = \{p_j : 1\le j\le \#(P)\}$
be any set of $\#(P)$ points in $(\Fqstar)^m$.
\item 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{slide}

%\begin{slide}
%\slidetitle{Other uses}
%
%Interestingly enough, the multivariate Vandermonde matrices
%have also made appearances in the study of
%\begin{itemize}
%\item multivariate polynomial interpolation
%\item polynomial equation solving
%\item Gr\"obner basis theory
%\item multipolynomial resultants
%\end{itemize}
%\end{slide}

\begin{slide}
\slidetitle{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) =$
$$ \pmatrix{ 1 & 1 & 1 & 1 & 1 & 1\cr
                  x_1 & x_2 & x_3 & x_4 & x_5 & x_6 \cr
                  y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \cr
                  x_1^2 & x_2^2 & x_3^2 & x_4^2 & x_5^2 & x_6^2 \cr
                  x_1y_1& x_2y_2 & x_3y_3 & x_4y_4 & x_5y_5 & x_6y_6 \cr
                  y_1^2 & y_2^2 & y_3^2 & y_4^2 & y_5^2 & y_6^2 \cr
                  }$$
\end{slide}

\begin{slide}
\slidetitle{Minimum Distance Theorem}

From L., Schwarz, [2]:

\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$ the homogeneous
linear system obtained the generator matrix, in columns corresponding to $S$,
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{slide}



\begin{slide}
\slidetitle{Codes From Simplices, etc.}

\begin{itemize}
\item Consider simplices of form
$$P_\ell = \mbox{Conv}(\ell e_i : i = 1,\ldots, m).$$
\item 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 Such ``simplicial configurations'' exist in any $T$ with 
$|T| = \ell(q-1)^m + 1$, so $d(C_{P_\ell}) = (q - 1)^m - \ell (q - 1)^{m-1}$.
\item Can do something very similar for parallelotopes
and codes from many subpolytopes.
\end{itemize}
\end{slide}


\begin{slide}
\slidetitle{Summary}

\begin{itemize}
\item  Toric codes are interesting and accessible (even for
undergraduate projects!)
\item But the results
on toric codes from simplices and parallelotopes show that $d$
is often quite {\it small} relative to $k$.
\item  It is an interesting problem to
determine criteria for polytopes (or subsets of the lattice points
in a polytope) that yield good evaluation codes.
\end{itemize}
\end{slide}
\end{document}
