\documentclass[handout]{beamer}

\usepackage{amscd,amssymb,epsfig}
\def\F{{\mathbb F}}
\def\a{\alpha}
\def\Fq{\F_q}
\def\Fp{\F_p}
\def\Fqstar{\F_q^{\,*}}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R}
\def\C{\mathbb C}
\def\N{\mathbb N}
\def\P{\mathbb P}
\newtheorem{thm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\def\boxit#1{\vbox{\hrule\hbox{\vrule\kern3pt
      \vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}
\mode<presentation>
{
  \usetheme{Warsaw}

  \setbeamercovered{opaque}
}


\usepackage[english]{babel}

\usepackage[latin1]{inputenc}

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

\title[Toric Varieties in Coding Theory]
{Toric Varieties in Error-Control Coding Theory\\
Math in the Mountains Tutorial}

\author
{John B. Little}

\institute[College of the Holy Cross]
{
  Department of Mathematics and Computer Science\\
  College of the Holy Cross\\
}

\date[July 29-31, 2013]
{July 29-31, 2013}

\begin{document}

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

\section{Coding theory basics}

\begin{frame}
{\bf A bit of history}

\begin{itemize}
\item<1->Beginning of coding theory as a mathematical and engineering
subject came with a paper ``A Mathematical Theory of Communication''
by Claude Shannon (1948).
\item<2->Shannon lived from 1916 to 2001, and spent most of his working
career at Bell Labs and MIT.
\item<3->He also made fundamental contributions to cryptography and the
design of computer circuitry in earlier work coming from his Ph.D.
thesis.
\item<4->Other interests -- inventing gadgets, juggling, unicycles, chess(!)
\end{itemize}
\end{frame}

\begin{frame}
{\bf Shannon's conceptual communication set-up}

\[
\begin{matrix}
\hbox{message} &&&&\boxit{\hbox{noise}} &&&& \\
\downarrow&&&&\downarrow &\\
\boxit{\hbox{encoder}} & \rightarrow & \boxit{\hbox{trans.}}
& \rightarrow & \boxit{\hbox{channel}} &\rightarrow & \boxit{\hbox{rec.}} &\rightarrow &\boxit{\hbox{decoder}}\\
&&&&&&&&\downarrow \\
&&&&&&&&\hbox{message}
\end{matrix}
\]
\end{frame}

\begin{frame}
{\bf Examples}
\vskip 10pt
This is a \emph{very general} framework, incorporating examples such as
\begin{itemize}
\item communication with deep space
exploration craft (Mariner, Voyager, etc. -- the most important early application)
\item storing/retrieving information in computer memory
\item storing/retrieving audio information (CDs)
\item storing/rerieving video information (DVD and Blu-Ray disks)
\item wireless communication
\end{itemize}
A main goal of coding theory is the design of
coding schemes that achieve {\it error control\/}:
ability to detect and correct errors in received messages.
\end{frame}

\begin{frame}
{\bf The case we will look at}

\begin{itemize}
\item<1-> We'll consider ``linear block codes'' --
vector subspaces $C$ of $\F_q^n$ for some $n$.
\item parameters: $n$, $k = \dim_{\F_q}(C)$,
$$d = \min_{x\ne y\in C} d(x,y) = \min_{x\ne 0\in C} {\rm weight}(x)$$
(\emph{Hamming minimum distance/weight})
\item<2-> $t = \lfloor \frac{d-1}{2}\rfloor \Rightarrow$
all errors of weight $\le t$ can be corrected by ``nearest neighbor
decoding''
\item<3-> Good codes:  $k/n$ not too small (so not extremely
redundant), but at same time $d$ or $d/n$ not too small.
\end{itemize}
\end{frame}

\begin{frame}
{\bf Reed-Solomon codes}

\begin{itemize}
\item<1->  Pick a primitive element $\a$ for $\F_q$
(i.e. generator of the cyclic multiplicative
group of field), and write the
nonzero elements of $\F_q$ as $1,\a,\ldots,\a^{q-2}.$
\item<2-> Let $L_k = \{f \in \F_q[x] : \deg f < k\}.$
Then
\begin{eqnarray*}
ev : L_k &\to& \F^{\, q-1}_q\\
       f &\mapsto& (f(1),f(\a),\ldots,f(\a^{q-2}))
\end{eqnarray*}
is linear and one-to-one if $k < q$.
The image is called $RS(k,q)$.
\item<3-> All $f$ of degree $< k$ have at most $k-1$ roots in $\F_q$
(and some have exactly that many)
$$\Rightarrow d = (q-1) - (k-1) = n - k + 1.$$
(Singleton bound: $d \le n - k + 1$.)
\end{itemize}
\end{frame}


\begin{frame}
{\bf An example}

\bigskip
Using the standard monomial basis for $L_k$:
$$\{1,x,x^2,x^3,\ldots, x^{k-1}\}$$
The Reed-Solomon code $RS(3,16)$
(parameters: $n = 15, k = 3, d = 13$ over $\F_{16}$, so $16^3 = 4096$
distinct codewords)
has generator matrix:
$$G = \begin{pmatrix} 1&1&1&\cdots&1&1&\cdots&1\\
               1&\a&\a^2&\cdots&\a^7&\a^8&\cdots&\a^{14}\\
               1&\a^2&\a^4&\cdots&\a^{14}&\a&\cdots&\a^{13}\end{pmatrix}$$
(means: the rows of $G$ form a basis for $C = RS(3,16)$).
\end{frame}

\begin{frame}
{\bf How Reed-Solomon codes are used}

\begin{itemize}
\item<1-> Reed-Solomon codes are among the most useful codes in
engineering practice in  situations where
errors tend to occur in ``bursts'' rather than randomly.
\item<2-> E.g., $RS(3,16)$ has $d = 13$, corrects any
error vector of weight $\le \lfloor \frac{13 - 1}{2}\rfloor = 6$
in a received word over $\F_{16} \cong \F_2^4$.
\item<3-> A ``burst'' of up to 20 consecutive bit errors would affect
{\it at most 6\/} of the symbols of the message thought of as elements of
$\F_{16}$.  $RS(3,16)$ can correct any 20 or fewer {\it consecutive} bit
errors in a codeword.
\item<4-> Also have very efficient algebraic decoding algorithms
(Berlekamp-Massey, Euclidean (Sugiyama)).
\item<5->  Basis for the error-control coding used, for example,
in CD audio, deep-space exploration
craft like {\it Voyager\/}, etc.
\end{itemize}
\end{frame}

\section{Toric codes}

\begin{frame}
{\bf Toric code basics}

\vskip 10pt
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 Then consider the \emph{toric evaluation map}
\begin{eqnarray*}
ev : L_P &\to& \F^{\, (q-1)^m}_q\\
       f &\mapsto& (f(\gamma): \gamma \in (\Fqstar)^m)
\end{eqnarray*}
Image is the toric code $C_P(\F_q)$.

\end{itemize}
\end{frame}

\begin{frame}
{\bf First example, and ``generalized'' toric codes}

\begin{itemize}
\item<1-> Example: The Reed-Solomon code $RS(k,q)$ is obtained with
this construction by taking
$P = [0,k-1]\subset \R$, since $P \cap \Z = \{0,1,\ldots,k\}$ and
$L_P = {\rm Span}\{1,x,\ldots,x^{k-1}\}$.
\item<2-> Can also do the same construction for any $S \subseteq P \cap \Z^m$
\item<3-> Get \emph{subcodes} of $C_P(\Fq)$ in this way; will denote them
by $C_S(\Fq)$
\item<4-> Also very natural to consider these more general codes for
several reasons (more on this later)
\end{itemize}
\end{frame}

\begin{frame}
{\bf Why are they interesting?}

\begin{itemize}
\item All $C_S(\Fq)$ have 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 L-, students, and most systematically
and recently, Brown and Kasprzyk [BK] have showed that
some very good $m = 2$ generalized toric codes exist (better than
any previously known codes in standard databases).
\item (No argument about this, here, I hope!) 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}
{\bf Best known codes from this construction}

\begin{itemize}
\item<1->an $m = 2$ generalized toric code over $\F_8$ with
parameters $[49,8,34]$ -- found by one group at MSRI-UP REU in 2009
\item<2-> different $m = 3$ generalized toric codes over $\F_5$ with parameters
$[64,8,42]$ -- another group at MSRI-UP REU in 2009 and Alex Simao, HC '08
\item<3-> Seven new ``champions'' over $\F_8$
found by Brown and Kasprzyk, reported in [BK], apparently
motivated by the following one L- found in 2011.
\item<4-> With hindsight, all can be described in other ways too; toric construction
gave a framework for finding them, though.
\end{itemize}
\end{frame}

\begin{frame}
{\bf A typical ``current champion''}

\vskip 10pt
Over $\F_8$, take $S$ given by filled circles ($P = {\rm conv}(S)$ shown):

\begin{center}
\begin{picture}(70,70)(0,0)
\put(5,0){\line(0,1){70}}
\put(0,5){\line(1,0){70}}
\put(15,2){\line(0,1){6}}
\put(25,2){\line(0,1){6}}
\put(35,2){\line(0,1){6}}
\put(45,2){\line(0,1){6}}
\put(55,2){\line(0,1){6}}
\put(65,2){\line(0,1){6}}
\put(15,2){\line(0,1){6}}
\put(2,15){\line(1,0){6}}
\put(2,25){\line(1,0){6}}
\put(2,35){\line(1,0){6}}
\put(2,45){\line(1,0){6}}
\put(2,55){\line(1,0){6}}
\put(2,65){\line(1,0){6}}
\put(35,5){\circle*{4}}
\put(25,15){\circle{4}}
\put(35,15){\circle{4}}
\put(45,15){\circle*{4}}
\put(5,25){\circle*{4}}
\put(15,25){\circle*{4}}
\put(25,25){\circle*{4}}
\put(35,25){\circle{4}}
\put(45,25){\circle{4}}
\put(5,35){\circle*{4}}
\put(15,35){\circle*{4}}
\put(25,35){\circle{4}}
\put(35,35){\circle{4}}
\put(45,35){\circle*{4}}
\put(55,35){\circle*{4}}
\put(5,45){\circle*{4}}
\put(15,45){\circle{4}}
\put(25,45){\circle*{4}}
\put(35,45){\circle{4}}
\put(45,45){\circle{4}}
\put(45,55){\circle*{4}}
\put(5,25){\line(3,-2){30}}
\put(35,5){\line(1,1){10}}
\put(45,15){\line(1,2){10}}
\put(55,35){\line(-1,2){10}}
\put(46,55){\line(-4,-1){40}}
\end{picture}
\end{center}

Get a $[49,12,28]$ code -- best previously known for $n = 49$, $k = 12$ over $\F_8$ was $d = 27$.
\end{frame}

\begin{frame}
{\bf How were these found?}
\begin{itemize}
\item<1-> Nicest way to say it -- exhaustive ([BK]) and/or "heuristic"
(L-, etc.) \emph{search} through space of possible $S$
\item<2-> Not very satisfying, though!
\item<3-> There are general theoretical lower and upper bounds on $d$ that
apply to these codes (esp. work of D. Ruano, P. Beelen) \emph{but}
\item<4-> Not very easy to apply, and rarely sharp
\item<5-> Need some additional tools to make progress!
\end{itemize}
\end{frame}

\begin{frame}
{\bf A useful equivalence relation}

\vskip 10pt
Take $S \subset [0,q-2]^m \simeq ({\mathbb Z}_{q-1})^m$, so
corresponding monomials are linearly independent as functions
on $(\Fqstar)^m$.

\begin{thm} If $S' = T(S)$ for some $T = {\rm AGL}(m,{\mathbb Z}_{q-1})$,
$C_{S'}(\Fq)$ is monomially equivalent to $C_S({\F_q})$.
\end{thm}

\vskip 10pt
\emph{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$.  This implies $d(C_S) = d(C_{S'})$.
\end{frame}

\begin{frame}
{\bf Comments}

\vskip 10pt
\emph{Note:} Even when we take $S = P\cap\Z^m$ for a polytope,
$S'$ may not be $P' \cap {\mathbb Z}^m$
for any $P'$, so also \emph{need to} study
``generalized'' toric codes from arbitrary $S$ to make use of this idea.

\vskip 10pt
[BK] uses this in a crucial way -- idea was enumerate the affine equivalence
classes of $S$ contained in squares $[0,\ell]\times [0,\ell]$

\vskip 10pt
There are also cases where $C_S(\Fq)$ and $C_{S'}(\Fq)$ are
monomially equivalent, but $S$ and $S'$ come from different
affine equivalence classes.  The implication in the theorem
only goes the way stated.
\end{frame}


\begin{frame}
{\bf Small needles in huge haystacks!}

\vskip 10pt
For $m = 3$, $q = 5$, the generating function for number of
${\rm AGL}(3,{\mathbb Z}_4)$-orbits on $k$-sets in ${\mathbb Z}_4^3$:
\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}$(!)

\vskip 10pt
``Most'' of these subsets give quite uninteresting codes.
But {\it one} of the $2128$ orbits
of size $k = 8$ consists of codes with $d = 42$, the ``champion'' mentioned before.
\end{frame}

\section{Tools from the toric world}

\begin{frame}
{\bf From algebraic geometry}

\begin{itemize}
\item As we saw earlier, a lattice polytope $P$ defines an abstract 
toric variety $X_P$.
\item Also get a line bundle ${\cal L} = {\cal L}_P$
specified by $P$, with basis of sections given by monomials corresponding to
the lattice points in $P$.
\item Subsets of $P \cap \Z^m$ correspond to subspaces of $H^0(X,{\cal L})$.
\item Codewords come by evaluation, and the issue is: how many $\Fq$-rational
zeroes can a section have?
\item In case $m = 2$, main results of [LS1]
show that for $q$ sufficiently large, $d(C_P(\F_q))$ can be
bounded above and below by looking at subpolytopes $P' \subseteq P$ that
decompose as {\it Minkowski sums}.
\end{itemize}
\end{frame}

\begin{frame}
{\bf Intuition for proof}

\begin{itemize}
\item<1-> Minkowski-reducible subpolygons $\leftrightarrow$ {\it reducible sections}
(Newton polygon of a product is Minkowski sum of Newton polygons of factors).
\item<2-> Hasse-Weil upper and lower bounds for an irreducible curve $Y$:
$$q + 1 - 2p_a(Y) \sqrt{q} \le |Y(\F_q)| \le q + 1 + 2p_a(Y)\sqrt{q}$$
\item<3-> Using this, some intersection theory, and Riemann-Roch on the toric surface
defined by $P$, [LS1] bounds number of $\F_q$-rational points on
any reducible section of ${\cal L}_P$ in $(\Fqstar)^2 \subset X_P$
\item<4->  $\Rightarrow$ when $q > $ (a crude
but explicit lower bound), reducible curves with more components
must have more $\F_q$-rational points than those with fewer components.
\end{itemize}
\end{frame}

\begin{frame}
{\bf From lattice polytopes}

\begin{itemize}
\item<1-> Idea was tightened and extended in [SS1] -- $d$
for $C_P(\Fq)$ is connected with $L(P) = $ \emph{full Minkowski length}
of $P$ -- the maximum number of summands in a Minkowski sum decomposition
$Q = Q_1 + \cdots + Q_L$ for $Q \subseteq P$.
\item<2-> In [SS1], Soprunov and Soprunova showed that in the plane, every Minkowski-indecomposable polygon
is lattice equivalent to either
\begin{enumerate}
\item[(a)]  the unit lattice segment ${\rm conv}\{(0,0),(1,0)\}$,
\item[(b)]  the unit lattice simplex ${\rm conv}\{(0,0),(1,0),(0,1)\}$, or
\item[(c)]  the ``exceptional triangle'' $T_0 = {\rm conv}\{(0,0),(1,2),(2,1)\}$
\end{enumerate}
\end{itemize}
\end{frame}

\begin{frame}
{\bf The Soprunov-Soprunova Theorem}

\begin{theorem}[SS1]
If $q$ is larger than an explicit (smaller than in [LS1]) lower
bound depending on $L(P)$ and the area of $P$, then
\begin{equation}
d(C_P(\Fq)) \ge (q - 1)^2 - L(P)(q - 1) - \lfloor 2\sqrt{q}\rfloor + 1,
\end{equation}
and if no maximally decomposable $Q \subset P$ contains an
exceptional triangle, then
\begin{equation}
\label{NoT0}
d(C_P(\Fq)) \ge (q - 1)^2 - L(P)(q - 1).
\end{equation}
\end{theorem}
\end{frame}

\begin{frame}
{\bf An interesting polygon for $q \ge 5$}

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


\begin{itemize}
\item<1-> $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<2-> No other decomposable $Q \subset P$
with more than three Minkowski summands
\end{itemize}
\end{frame}


\begin{frame}
{\bf Reducible curves}

\vskip 10pt
Bounds from [LS1] or [SS1] $\Rightarrow$ for $q$ suff. large
$$d(C_P(\F_q)) \ge (q-1)^2 - 3(q-1).$$

\vskip 10pt
From $P'$ above, obtain reducible sections of $L_P$:
$s = x(x-a)(y-b)(y-c)$, with $3(q-1) - 2$ zeroes
in $(\Fqstar)^2$ if $a,b,c \in \Fqstar$, $b\ne c$.
Hence,
$$d(C_P(\F_q)) \le (q-1)^2 - 3(q-1) + 2.$$
\end{frame}

\begin{frame}
{\bf Minimum distances over different fields}

\vskip 10pt
Magma computations (package written by D. Joyner) show:
\begin{eqnarray*}
d(C_P(\F_5)) = 6 & vs. & 4^2 - 3\cdot 4 + 2 = 6\\
d(C_P(\F_7)) = 20 & vs. & 6^2 - 3\cdot 6 + 2 = 20\\
d(C_P(\F_8)) = 28 & vs. & 7^2 - 3\cdot 7 + 2 = 30\\
d(C_P(\F_9))  = 42 & vs. & 8^2 - 3\cdot 8 + 2 = 42\\
d(C_P(\F_{11})) = 72 & vs. & 10^2 - 3 \cdot 10 + 2 = 72.
\end{eqnarray*}
\end{frame}

\begin{frame}
{\bf More on $q = 8$}

\vskip 10pt
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
$\F_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
$(\F_8^{\,*})^2$ as $y + x^3y^3 + x^2$.
\end{frame}

\begin{frame}
{\bf Arithmetic of $\F_8$ matters!}

\vskip 10pt
$1 + u + u^3$ is one of the two irreducible polynomials
of degree 3 in $\F_2[u]$, hence
$$\F_8 \cong \F_2[u]/\langle 1 + u + u^3\rangle.$$
If $\beta$ is a root of $1 + u + u^3 = 0$ in $\F_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 $(\F_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}

\begin{frame}
{\bf Another Example: $P = {\rm conv}\{(0,0),(2,0),(3,1),(1,4)\}$}

\begin{center}
\begin{picture}(70,70)(0,0)
\put(5,0){\line(0,1){70}}
\put(0,5){\line(1,0){70}}
\put(15,2){\line(0,1){6}}
\put(25,2){\line(0,1){6}}
\put(35,2){\line(0,1){6}}
\put(45,2){\line(0,1){6}}
\put(55,2){\line(0,1){6}}
\put(65,2){\line(0,1){6}}
\put(15,2){\line(0,1){6}}
\put(2,15){\line(1,0){6}}
\put(2,25){\line(1,0){6}}
\put(2,35){\line(1,0){6}}
\put(2,45){\line(1,0){6}}
\put(2,55){\line(1,0){6}}
\put(2,65){\line(1,0){6}}
\put(5,5){\circle*{4}}
\put(15,5){\circle*{4}}
\put(25,5){\circle*{4}}
\put(15,15){\circle*{4}}
\put(25,15){\circle*{4}}
\put(35,15){\circle*{4}}
\put(15,25){\circle*{4}}
\put(25,25){\circle*{4}}
\put(15,35){\circle*{4}}
\put(15,45){\circle*{4}}
\put(5,5){\line(1,0){20}}
\put(25,5){\line(1,1){10}}
\put(35,15){\line(-2,3){20}}
\put(15,45){\line(-1,-4){10}}
\end{picture}
\end{center}

Have $L(P) = 4$, and $P$ contains
just one Minkowski sum of 4 indecomposable polygons, namely
the line segment $Q = {\rm conv}\{(1,0),(1,4)\}$.  Expect for $q$
sufficiently large,
$$d(C_P(\Fq)) = (q - 1)^2 - 4(q - 1).$$
\end{frame}



\begin{frame}
{\bf Leaving out lattice points}

\vskip 10pt
Now, study $C_S(\Fq)$ for $S$ contained in $P$ from before:
\begin{center}
\begin{picture}(70,70)(0,0)
\put(5,0){\line(0,1){70}}
\put(0,5){\line(1,0){70}}
\put(15,2){\line(0,1){6}}
\put(25,2){\line(0,1){6}}
\put(35,2){\line(0,1){6}}
\put(45,2){\line(0,1){6}}
\put(55,2){\line(0,1){6}}
\put(65,2){\line(0,1){6}}
\put(15,2){\line(0,1){6}}
\put(2,15){\line(1,0){6}}
\put(2,25){\line(1,0){6}}
\put(2,35){\line(1,0){6}}
\put(2,45){\line(1,0){6}}
\put(2,55){\line(1,0){6}}
\put(2,65){\line(1,0){6}}
\put(5,5){\circle*{4}}
\put(15,5){\circle*{4}}
\put(25,5){\circle*{4}}
\put(15,15){\circle*{4}}
\put(25,15){\circle{4}}
\put(35,15){\circle*{4}}
\put(15,25){\circle{4}}
\put(25,25){\circle*{4}}
\put(15,35){\circle{4}}
\put(15,45){\circle*{4}}
\put(5,5){\line(1,0){20}}
\put(25,5){\line(1,1){10}}
\put(35,15){\line(-2,3){20}}
\put(15,45){\line(-1,-4){10}}
\end{picture}
\end{center}

What happens?  $k = 7$ only (not $k = 10$), and ...

\end{frame}

\begin{frame}
{\bf Example, continued}

\begin{eqnarray*}
d(C_S(\F_7)) = 18 & {\rm vs.} & 6^2 - 4\cdot 6 = 12\\
d(C_S(\F_8)) = 33 & {\rm vs.} & 7^2 - 4\cdot 7 = 21\\
d(C_S(\F_9)) = 32 & = & 8^2 - 4\cdot 8 = 32\\
d(C_S(\F_{11})) = 70 & {\rm vs.} & 10^2 - 4\cdot 10  = 60\\
d(C_S(\F_{13})) = 96 & = & 12^2 - 4\cdot 12  = 96\\
d(C_S(\F_{16})) = 165 & = & 15^2 - 4\cdot 15  = 165\\
d(C_S(\F_{17})) = 192 & = & 16^2 - 4\cdot 16  = 192\\
d(C_S(\F_{19})) =  270 & {\rm vs.} & 18^2 - 4\cdot 18  = 252\\
d(C_S(\Fq)) & = & (q-1)^2 - 4(q-1) \quad {\rm all}\ q \ge 23 (?)
\end{eqnarray*}
\end{frame}


\begin{frame}
{\bf The minimum weight words}
\begin{itemize}
\item<1-> $C_S(\Fq) \subset C_P(\Fq)$, so $d(C_S(\Fq)) \ge d(C_P(\Fq))$
and
\item<2-> Conjecture: $d(C_P(\Fq)) = (q - 1)^2 - 4(q - 1)$ for all
$q \ge 23$.  Evidence: SS Theorem implies $\ge $, but the $C_P$ code
contains the words
${\rm ev}(x(y^4 + a_3 y^3 + a_2 y^2 + a_1 y + a_0))$
for all $a_i \in \Fq$.
\item<3->  Some of those quartic polynomials factor
$(y - \beta_1) \cdots (y - \beta_4)$ for $\beta_j$ distinct $\in \Fqstar$,
so $4(q - 1)$ zeroes in $(\Fqstar)^2$.
\item<4-> In $\Fq$ for $q$ sufficiently large,
there are \emph{also} polynomials of the form $y^4 + a_1 y + a_0$ that
factor this way; bounds not explicit enough to yield $q \ge 23$, though!
\end{itemize}
\end{frame}

\begin{frame}
{\bf Two ways to think about this ... }

\begin{itemize}
\item<1->  First (the ``glass is half-empty'' point of view):
leaving lattice points out of $P \cap \Z^m$
is only likely to improve $d$ dramatically for toric codes
when $q$ is small
\item<2->  Second (the ``glass is half-full'' point of view):
over larger fields, for many sets of lattice points
$S$ with ${\rm conv}(S) = P$, can often include \emph{all} of the
lattice points in $P \cap \Z^m$ and get toric codes of the
same minimum distance and larger dimension
\end{itemize}
\end{frame}

\section{Higher-dimensional polytopes and Vandermonde matrices}

\begin{frame}
{\bf Taking toric codes ``to the next dimension(s)''}

\begin{itemize}
\item<1-> This whole general area has only started to be explored
\item<2-> Intersection theory on higher-dimensional varieties
is more subtle and not so obvious how to apply it
\item<3-> Questions about polytopes and toric varieties
in higher dimensions are also more subtle (e.g. classification
of Minkowski-irreducible polytopes)
\item<4-> Some preliminary work in [LS2] and [SS2]
\end{itemize}
\end{frame}

\begin{frame}
{\bf A different approach}

\vskip 10pt
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}$$

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

\begin{frame}
{\bf General Vandermondes}

\begin{itemize}
\item Let $P$ be an integral convex polytope, and
write $P \cap \Z^m = \{e(i) : 1 \le i\le \ell\}$, $\ell = |P\cap \Z^m|$.
\item Let $S = \{p_j : 1\le j\le \ell\}$
be any set of $\ell$ points in $(\Fqstar)^m$.
\item Picking orderings,
define $V(P; S)$, the
{\it Vandermonde matrix} associated to $P$ and $S$, to be the
$\ell\times \ell$ 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}
{\bf Other uses}
\vskip 10pt
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{frame}

\begin{frame}
{\bf An Example}

\vskip 10pt
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}


\begin{frame}
{\bf Minimum Distance Theorem, [LS2]}

\vskip 10pt
\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| = \ell$
such that $\det V(P; S) \ne 0$.
Then the minimum distance satisfies $d(C_P) \ge d$.
\end{thm}

\vskip 10pt
Proof:  For all $S$, $\det V(P;S) \ne 0 \Rightarrow$ the homogeneous
linear system obtained from 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{frame}




\begin{frame}
{\bf  Codes from simplices}

\vskip 10pt
Consider $C_{P_\ell(m)}$ for $P_\ell(m)$ an $m$-dimensional
simplex of the form
$$P_\ell(m) = \mbox{conv}\{{\bf 0},\ell {\bf e}_1,\ldots, \ell {\bf e}_m\},$$
where the ${\bf e}_i$ are the standard basis vectors in $\R^m$.  (Corresponding
toric variety is the degree $\ell$ Veronese embedding of $\P^m$.
The corresponding
Vandermonde matrices also arise in the study of multivariate
interpolation using polynomials of bounded total degree.)

\vskip 10pt
Need to identify $S$ for which $\det(V(P_\ell(m);S)) \ne 0$.

\end{frame}

\begin{frame}

\begin{defn}
If $m = 1$, an $\ell$th order {\bf simplicial configuration}
is any collection of $\binom{1 + \ell}{\ell}$
distinct points in $\Fqstar$.
For $m \ge 2$,
we will say that a collection $S$ of $\binom{m + \ell}{\ell}$ points
in $(\Fqstar)^m$ is an $m$-dimensional
$\ell$th order {\bf simplicial configuration} if the following
conditions hold:
\begin{enumerate}
\item For some $i$, $1\le i \le m$, there are hyperplanes
$x_i = a_1, x_i = a_2, \ldots, x_i = a_{\ell+1}$
such that for each $1 \le j \le \ell+1$, $S$ contains exactly
$\binom{m - 1 + j - 1}{j - 1}$ points with $x_i = a_j$.
\item For each $j$, $1 \le j \le \ell + 1$,
the points in $x_i = a_j$ form an $(m-1)$-dimensional simplicial
configuration of order $j-1$.
\end{enumerate}
\end{defn}
\end{frame}

\begin{frame}
{\bf A ``simplicial configuration'' in $(\F_8^{\, *})^2$ -- ``log plot''.}

\begin{center}
\begin{picture}(200,205)(0,0)
\put(26,26){\vector(1,0){165}}
\put(26,26){\vector(0,1){165}}
\put(49,49){\circle*{5}}
\put(49,95){\circle*{5}}
\put(49,164){\circle*{5}}
\put(95,95){\circle*{5}}
\put(95,72){\circle*{5}}
\put(118,49){\circle*{5}}

%\put(0,0){$1$}
%\put(46,0){$\alpha$}
%\put(66,0){$\alpha^2$}
%\put(89,0){$\alpha^3$}
%\put(112,0){$\alpha^4$}
%\put(135,0){$\alpha^5$}
%\put(158,0){$\alpha^6$}
\put(49,23){\line(0,1){5}}
\put(75,23){\line(0,1){5}}
\put(97,23){\line(0,1){5}}
\put(120,23){\line(0,1){5}}
\put(143,23){\line(0,1){5}}
\put(166,23){\line(0,1){5}}

%\put(0,49){$\alpha$}
%\put(0,66){$\alpha^2$}
%\put(0,89){$\alpha^3$}
%\put(0,112){$\alpha^4$}
%\put(0,135){$\alpha^5$}
%\put(0,158){$\alpha^6$}
\put(23,49){\line(1,0){5}}
\put(23,72){\line(1,0){5}}
\put(23,95){\line(1,0){5}}
\put(23,118){\line(1,0){5}}
\put(23,141){\line(1,0){5}}
\put(23,164){\line(1,0){5}}
\end{picture}
\end{center}
\end{frame}





\begin{frame}
{\bf Some observations}

\begin{itemize}
\item<1-> Let $S$ be an $m$-dimensional $\ell$th order simplicial
configuration consisting of $\binom{m + \ell}{\ell}$
points, in hyperplanes $x_m = a_1, \ldots, x_m = a_{\ell+1}$.
\item<2-> Write $S = S'\cup S''$ where $S'$ is the union
of the points in $x_i = a_1, \ldots, a_\ell$, and $S''$
is the set of points in $x_i = a_{\ell + 1}$.
\item<3-> Let $\pi : \F_q^{\,m} \to \F_q^{\,m-1}$ be the projection on the
first $m - 1$ coordinates.
\item<4-> Both $S'$ and $\pi(S'')$ are themselves simplicial
configurations: $S'$ dimension $m$ and order $\ell - 1$;
$\pi(S'')$ dimension $m - 1$ and order $\ell$.
\end{itemize}

\end{frame}

\begin{frame}
{\bf A recurrence [LS2]}

\vskip 10pt
\begin{thm} Let $P_\ell(m)$ be as above and let $S$ be
an $\ell$th order simplicial configuration of $\binom{m + \ell}{\ell}$
points.
Then writing $p = (p_1,\ldots,p_m)$ for points $p\in (\Fqstar)^m$,
\begin{eqnarray*} \det V(P_\ell(m); S) &=&
\pm \prod_{p \in S'}(p_m - a_{\ell +1}) \\
&&\quad\cdot \det V(P_{\ell-1}(m); S')\\
&&\quad\cdot \det V (P_{\ell}(m-1); \pi(S''))
\end{eqnarray*}
\end{thm}

(Suggested by a computation in a paper on multivariate
interpolation by Chui and Lai -- ``poised sets'' for interpolation
by polynomials of degree bounded bounded by $\ell$.)
\end{frame}

%\begin{frame}
%{\bf An illustrative example}
%
%\vskip 10pt
%Consider all polynomials of degree $\le 2$ in three
%variables and the Vandermonde matrix $V(P_2(3); S)$.
%For notational simplicity,
%write points in a 3-dimensional simplicial
%configuration $S \subset (\Fqstar)^3$ of order 2
%as $(x_i,y_i,z_i)$, for $i = 1,\ldots, 10 = {3 + 2\choose 2}$.
%Here $S'$ consists of the first four points in $S$, and $S''$
%consists of the other six points.
%Under the hypothesis that
%$S$ is a simplicial configuration, we have
%$z_5 = z_6 = \cdots  = z_{10} = c$ for some $c$.
%\end{frame}

\begin{frame}
{\bf Consequences}

\begin{cor} Let $P_\ell(m)$ be as above and let $S$ be
an $\ell$th order simplicial configuration of $\binom{m + \ell}{\ell}$
points.  Then $\det V(P_\ell(m); S) \ne 0$.
\end{cor}

\begin{thm}  Let $\ell < q - 1$, and let $P_\ell(m)$ be
the simplex in $\R^m$ defined above.  Then the minimum
distance of the toric code $C_{P_\ell(m)}$ is given
by
$$d(C_{P_\ell(m)}) = (q-1)^m - \ell(q-1)^{m-1}.$$
\end{thm}
\end{frame}

\begin{frame}
{\bf The idea of the proof}

\vskip 10pt
The result on Vandermondes is used to show
$d(C_{P_\ell(m)}) \ge (q-1)^m - \ell(q-1)^{m-1}$.

\vskip 10pt
A pigeon-hole principle
argument constructs simplicial configurations $S \subset T$
for every $T$ with $|T| = \ell(q-1)^m + 1$.

\vskip 10pt
Other inequality comes from reducibles $(x_m - a_1)\ldots (x_m - a_\ell)$.
\end{frame}

\begin{frame}
{\bf 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{frame}

\begin{frame}
{\bf References for further study}

\begin{itemize}
\item[BK] G. Brown and A. Kasprzyk, {\em Seven new champion linear codes}, LMS J. of Computation and Mathematics {\bf 16} (2013), 109-117.
\item[LS1] J. Little and H. Schenck {\em Toric codes and Minkowski sums},
     SIAM J. of Discrete Math. {\bf 20} (2006), 999-1014.
\item[LS2] J. Little and R. Schwarz,
     {\em Toric Codes and Vandermonde matrices}, AAECC {\bf 18} (2007), 349-367.
\item[SS1] I. Soprunov and J. Soprunova {\em Toric surface codes and Minkowski length of polygons.} SIAM J. Discrete Math. {\bf 23} (2009), 384-400.
\item[SS2] I. Soprunov and J. Soprunova, {\em Bringing toric codes to the next dimension}. SIAM J. Discrete Math. {\bf 24} (2010), 655-665.
\end{itemize}
\end{frame}

\end{document}
