\documentclass{beamer}

\usepackage{amscd,amssymb,epsfig,manfnt}
\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}
\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}
\newtheorem{conj}{Conjecture}
\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[Cubic Surfaces and Codes]
{Cubic Surfaces and Codes}

\author
{John B. Little}

\institute[College of the Holy Cross]
{
   University of Illinois -- Seminar\\
}

\date[March 5, 2015]
{March 5, 2015}

\begin{document}

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

\begin{frame}
{\bf Outline}

\tableofcontents

\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 t0 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 A disclaimer}

As you will see, this is very much work in progress and 
I don't quite have the ``punchline'' yet.  \emph{Thanks for the opportunity
to speak on this though}. The process of preparing this talk has
been a good way to take stock of where I am in this project!
\end{frame}

\begin{frame}
{\bf ``A Mathematical Theory of Communication,'' Claude Shannon (1948)}

\[
\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 We'll consider ``linear block codes'' --
vector subspaces $C$ of $\F_q^n$ for some $n$.
\item Parameters $[n,k,d]$: the \emph{blocklength} $n$, the \emph{dimension} $k = \dim_{\F_q}(C)$, 
and the \emph{Hamming minimum weight/distance}
$$d =  \min_{x\ne 0\in C} {\rm weight}(x) = \min_{x\ne y\in C} d(x,y)$$
\item $t = \lfloor \frac{d-1}{2}\rfloor \Rightarrow$
all errors of weight $\le t$ can be corrected by ``nearest neighbor 
decoding''
\item 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}

\section{Evaluation codes from algebraic varieties}

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

\vskip 10pt 
Idea (in this form) goes back to work of Goppa from the late 1970's - early 1980's

\begin{itemize}
\item Let $X$ be an algebraic variety defined over $\F_q$, 
with $\mathcal{S} = \{P_1,\ldots,P_n\} \subseteq X(\F_q)$.
\item Let $\mathcal{L}$ be some vector subspace of the field of 
rational functions on $X$ with $f(P_i)$ defined
for all $f \in L$ and $P_i$.
\item Then consider the \emph{evaluation map}
\begin{eqnarray*}
ev : \mathcal{L} &\to& \F^{\, n}_q\\
       f &\mapsto& (f(P_1),\ldots,f(P_n))
\end{eqnarray*}
\item Image is a linear code of blocklength $n$, dimension $k \le \dim \mathcal{L}$, 
$d$ depends on properties of $X$, $\mathcal{S}$, $\mathcal{L}$
\end{itemize}
\end{frame}

\begin{frame}
{\bf The ``ur-examples''}

\begin{itemize}
\item The well-known (and extensively used) \emph{Reed-Solomon codes} 
$RS(k,q)$ are obtained with this construction by taking
$X = \P^1$, $n = q-1$, and $\mathcal{S}$ the set of nonzero affine
$\F_q$-rational points of $\P_1$.  
$\mathcal{L} = {\rm Span}\{1,x,\ldots,x^{k-1}\} = L((k-1)P_\infty)$ ($k < q$).  
\item This evaluation code has $d = (q-1) - (k-1) = n - k + 1$,
since some polynomials of degree $\le k-1$ have $k - 1$ roots in $\F_q$, but no more
\item A general bound says this is the \emph{biggest possible} $d$ for a given $n,k$(!) 
\item Goppa codes replace $\P^1$ with other algebraic curves over $\F_q$.
Known: can get some \emph{very good} codes with this construction 
for $q > 49$, $q$ a square.
\end{itemize}
\end{frame}

\begin{frame}
{\bf What about higher-dimensional varieties $X$?}

\begin{itemize}
\item Codes from some special varieties (quadrics, Hermitian varieties, Grassmannians, 
flag varieties, toric varieties, types of algebraic surfaces ... ) have been investigated, 
but this subject is still really in its infancy
\item One recurrent pattern:  If $X \subset \P^n$ for some $n > \dim X$, and $\mathcal{L}$
has the form $\{ f/g \mid f \in \F_q[x_0,\ldots,x_n]_s\}$ for some \emph{degree} $s$, then $d$ can
be (much) smaller than we hope because some $X \cap {\bf V}(f)$ can be \emph{reducible} and
contain lots of $\F_q$-rational points $\Rightarrow ev(f)$ are codewords of low weight.
\end{itemize}
\end{frame}

\begin{frame}
{\bf Example -- $s = 1$ codes from quadric surfaces}

\begin{itemize}
\item Say $q$ is odd to rule out characteristic 2 ``weirdness''
\item Smooth quadrics in $\P^3$ come in two ``flavors'' 
\item \emph{hyperbolic}: ruled surfaces like hyperbolic paraboloids (e.g. ${\bf V}(xy - zw)$).  Have
$X \simeq \P^1 \times \P^1$ in Segre embedding so $|X(\F_q)| = q^2 + 2q + 1$.
\item \emph{elliptic}: non-ruled -- analogous to real ellipsoids.  Have $|X(\F_q)| = q^2 + 1$ in this case.
\end{itemize}
\end{frame}

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

\begin{itemize}
\item Fix a linear form $g$ so $Y = {\bf V}(g) \cap X$ a smooth conic ($q + 1$ $\F_q$-points), 
take $\mathcal{S} = X(\F_q) - Y(\F_q)$, so $n = q^2 + q$ in hyperbolic case
and $n = q^2 - q$ in elliptic case.
\item Take ${\mathcal L} = \F_q[x,y,z,w]_1/g$.
\item In the elliptic case, every plane ${\bf V}(f)$ for $f \in \F_q[x,y,z,w]_1$ 
meets $X$ in either a single point or in a smooth conic ($q + 1$ $\F_q$-points).  Therefore, 
$d = q^2 - q - 1$.
\item In the hyperbolic case, the tangent planes to $X$ at $\F_q$-points
intersect $X$ in reducible conics consisting of two lines, so $2q + 1$ $\F_q$-points
and $d = q^2 - q - 1$ again.
\item \emph{But} codes from elliptic quadrics are \emph{much better} -- the same $d$
for a smaller $n$.  
\end{itemize}
\end{frame}

\begin{frame}
{\bf Zarzar's \emph{ansatz}}

In his 2007 U. Texas PhD thesis, Marcos Zarzar discussed the following idea.

\begin{itemize}
\item Take $\dim X = 2$.  Zeroes in codewords of an evaluation code
come from $\F_q$-points in ${\bf V}(f) \cap X$ for $f/g \in \mathcal{L}$.  But
as above for quadrics, if ${\bf V}(f) \cap X$ is reducible (and $q >> 0$) it can contain
many more $\F_q$-rational points than corresponding smooth ${\bf V}(f) \cap X$
(can quantify this).  
\item So good codes should come from surfaces $X$ containing few (or no) reducible curves
of small degree relative to the degree of the $f$ from $\mathcal{L}$.  
\end{itemize}
\end{frame}

\begin{frame}
{\bf The Neron-Severi group}

Precise statement uses the 
\emph{Neron-Severi} group of {\it divisors classes modulo algebraic equivalence}.

\textdbend This refers to divisors rational over the field of definition of $X$.

\begin{itemize}
\item For elliptic quadrics, $NS(X) = \Z \cdot [H]$, $H$ = any smooth conic plane section 
\item For hyperbolic quadrics, $NS(X) = \Z \cdot [L_1] \oplus \Z\cdot [L_2]$, where $L_i$ are
lines in the two rulings
\end{itemize}

Fact noted by Zarzar:  If $\deg X = d$ with $(d,{\rm char}(\F_q)) = 1$, 
${\rm rank}(NS(X)) = 1$, and $Y$ irreducible over $\F_q$ with $\deg Y < d$, 
then $X \cap Y$ is irreducible.  
\end{frame}

\section{Interlude -- counting rational points on varieties}

\begin{frame}
{\bf Counting $\F_q$-points on varieties -- the zeta function}

\begin{itemize}
\item For any given $X$ and $q$, it is, of course, a finite problem to determine
all $\F_q$-points on $X$ by ``brute force.''  
\item But there is also an extremely elegant and beatiful theory based
on the generating function known as the \emph{zeta function} of $X$.
\item Let $X$ be defined over $\F_q$ and let $N_r = |X(\F_{q^r})|$.
\item Then
$$Z(X,t) = \exp\left(\sum_{r=1}^\infty N_r \frac{t^r}{r}\right)$$
\end{itemize}
\end{frame}

\begin{frame}
{\bf The Weil Conjectures (Dwork, Deligne, ... )}

\begin{itemize}
\item Say $X$ can be viewed as reduction of a scheme over $\Z$
\item $Z(X,t)$ is a \emph{rational function} of $t$ whose numerator and denominator
factor into polynomials
\begin{itemize}
\item reflecting shape of cohomology of the complex variety $X(\C)$, and
\item and whose roots have special algebraic properties.
\end{itemize}
\item Best way to explain this is by giving the examples most relevant to 
our story ... 
\end{itemize}
\end{frame}

\begin{frame}
{\bf The zeta function of a smooth plane cubic curve}

\begin{itemize}
\item $Z(X,t) = \frac{[deg\ 2]}{[deg\ 1][deg\ 1]} = \frac{(1 - \alpha_1 t)(1 - \alpha_2 t)}{(1 - t)(1 - qt)}$,
where $|\alpha_i| = \sqrt{q}$ and $\alpha_1\alpha_2 = q$
\item Taking $\log$ of both sides of the equation 
$$\exp\left(\sum_{r=1}^\infty N_r \frac{t^r}{r}\right) = \frac{(1 - \alpha_1 t)(1 - \alpha_2 t)}{(1 - t)(1 - qt)}$$
and equating coefficients gives for all $r \ge 1$:
$$N_r = 1 + q^r - (\alpha_1^r + \alpha_2^r)$$
\item With $r = 1$ (and a bit more work),  Hasse-Weil-Serre:
$$1 + q - \lfloor 2\sqrt{q}\rfloor \le N_1 \le 1 + q + \lfloor 2\sqrt{q}\rfloor$$  
\end{itemize}

\end{frame}

\begin{frame}
{\bf The zeta function of a smooth cubic surface}

\begin{itemize}
\item $Z(X,t) = \frac{[deg\ 0] [deg\ 0]}{[deg\ 1][deg\ 7][deg\ 1]} = \frac{1}{(1 - t)P_2(t)(1 - q^2t)}$,
where $P_2(t) = (1 - qt)\prod_{j=1}^6 (1 - \alpha_j t)$,  with $|\alpha_j| = q$ all $j$.
\item Taking $\log$ of both sides of the equation 
and equating coefficients gives for all $r \ge 1$:
$$N_r = 1 + q^{2r} + q^r + \sum_{j=1}^6 \alpha_j^r$$
\item Tate conjecture (known to hold in this case, I think):  
the rank of $NS(X)$ equals $1 + $ the number of $\alpha_j$ equal to $q$.  
\end{itemize}

\end{frame}

\section{Cubic surfaces and codes}

\begin{frame}
{\bf A test case -- cubic surface codes}

\begin{itemize}
\item Construct codes from $X$ a smooth cubic surface in $\P^3$.
\item A first observation: there are \emph{many more} differences between cubics than
between quadrics -- different numbers of $\F_q$-points, different ranks of $NS(X)$, etc.  
\item Fortunately, this is a well-studied area, starting with
work of Cayley and Salmon from the 1850's (over $\C$).  
\item ``Fact 1:''  Over an algebraically closed field, a smooth cubic surface contains
exactly 27 straight lines, always in a particular highly symmetric and intricate configuration.
\item Symmetry group of the 27 lines is a group of order 51840 ($ = W(E_6)$)
\item For some $X$, some lines may only be defined over an algebraic extension of $\F_q$
\end{itemize}
\end{frame}

\begin{frame}
{\bf The Clebsch cubic}

\begin{figure}
\includegraphics[scale = 1.8]{clebsch.jpg}
\caption{A cubic surface with 27 real lines}
\end{figure}
(Figure by Stephan Endrass -- downloaded from page of Th. Bauer U. Marburg)
\end{frame}

\begin{frame}
{\bf The Frobenius action on the 27 lines}

\begin{itemize}
\item Because we assume $X$ is defined over $\F_q$ (where all $a \in \F_q$ satisfy $a^q = a$), 
the Frobenius mapping $F: (x,y,z,w) \to (x^q,y^q,z^q,w^q)$ takes $X$ to itself
\item $\Rightarrow$ $F$ also acts as a permutation of the lines on the cubic
over the algebraic closure $\overline{\F_q}$
\item There is a complete classification of the conjugacy classes in $W(E_6)$.
\item Which class $F$ (acting on the 27 lines) belongs to determines the structure of the cubic!
\item 25 possibilities summarized in two tables from a 1967 paper of Swinnerton-Dyer (and 
in a related table in Manin's \emph{Cubic Forms}). 
\end{itemize}
\end{frame}

\begin{frame}
{\bf An extract from the Swinnerton-Dyer table}

\emph{Exactly} five types of cubics with ${\rm rank}\ NS(X) = 1$ ($\Rightarrow$ \emph{no} $\F_q$-rational lines)

\[
\begin{array}{cccc}
      {\rm Class} & {\rm Perm Type} & N_1 = |X(\F_q)| & {\rm ord}(\eta_j) \\ \hline
          C_{10} & \{3,6^3,6\} & q^2 - q + 1 & 2,2,3,3,6,6\\
          C_{11} & \{3^9\}     & q^2 - 2q + 1& 3,3,3,3,3,3\\
          C_{12} & \{3,6^4\}   & q^2 + 2q + 1& 3,3,6,6,6,6\\
          C_{13} & \{3,12^3\}  & q^2 + 1 & 3,3,12,12,12,12\\ 
          C_{14} & \{9^3\}     & q^2 + q + 1 &9,9,9,9,9,9\\
\end{array}
\]
Notes: $\eta_j$ is a primitive ${\rm ord}(\eta_j)$th root of unity with  $\alpha_j = \eta_j q$.
Knowing the $\eta_j$ allows us to compute $N_r$ for all $r \ge 1$ as before.    

\end{frame}

\begin{frame}
{\bf Some experimental results for $s = 1$ codes}

At beginning of working on this -- generated cubic surfaces randomly, classified them
by the numbers of $\F_{q^r}$-points for $r = 1,2,3$, whether they contained
lines defined over $\F_q$, etc.  With $q = 7$, for instance:

\begin{itemize}
\item $C_{10}$ -- found $[43,4,30]$ and $[43,4,31]$ examples (best possible $d=35$)
\item $C_{11}$ -- found $[36,4,23]$ and $[36,4,24]$ examples (best possible $28 \le d \le 29$)   
\item $C_{12}$ -- \emph{all} $[64,4,51]$ (several hundred of them) (best possible $52 \le d \le 53$)
\item $C_{13}$ (very rare) -- found  $[50,4,37]$  (best possible $d = 42$)
\item $C_{14}$ (rare) -- found $[57,4,44]$ (best possible $d = 47$)
\end{itemize}

\end{frame}

\begin{frame}
{\bf What to make of all this?}

\begin{itemize}
\item $C_{12}$ cubics are pretty clearly the best for this construction.
\item Also, confirmation of Zarzar's \emph{ansatz}.  Cubics with ${\rm rank}\ NS(X) > 1$
can have reducible plane sections with as many as $3q + 1 = 22$ points with $q = 7$.  
The largest number of $\F_7$-points we were seeing in plane sections here for $q = 7$ is, e.g., $64 - 51 = 13$.   
\item \emph{Why 13?}  Recall the Hasse-Weil-Serre bound:  The maximum number of $\F_7$-points on 
a smooth plane cubic is $1 + 7 + \lfloor 2\sqrt{7}\rfloor = 13$.  Moreover, singular (but irreducible) 
plane sections all have either $q = 7$ (``split'' node), $q + 1 = 8$ (cusp), or $q + 2 = 9$ (``non-split'' node)
$\F_q$-points.  
\item Note: Some of the $C_{10}$ and $C_{11}$ surfaces don't have any plane sections with $13$ $\F_7$-points.
\end{itemize}
\end{frame}

\begin{frame}
{\bf A conjecture}

Based on lots of additional experimental evidence for prime powers $q \le 37$, 

\begin{conj}
For all $q \ge 5$ a $C_{12}$ cubic always contains optimal cubic plane sections, 
i.e. plane sections with the maximum number of $\F_q$-points for a smooth
plane cubic curve.
\end{conj}

\end{frame}

\begin{frame}
{\bf $C_{12}$ cubics -- a closer look}

For $C_{12}$ surfaces, can extract the following additional
information from Swinnerton-Dyer:

\begin{itemize}
\item All the lines on a $C_{12}$ are defined over $\F_{q^6}$ (the
degree 6 extension field of $\F_q$).  
\item The Frobenius orbits on the lines consist of:
\begin{itemize}
\item one coplanar $3$-cycle ($\Rightarrow$ those lines are defined over $\F_{q^3}$),  and 
\item four $6$-cycles, each consisting of two coplanar triangles, where $F$ takes
a line in one triangle to a line in the other triangle ($\Rightarrow$ those triangles
and the planes containing them are defined over $\F_{q^2}$)
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}
{\bf Well, so what?}

The information about the Frobenius orbits of the lines implies:

\begin{thm}
The equation of a $C_{12}$ cubic surface can be written (in four different ways) as
\begin{equation}
\label{detform}
\ell\cdot F(\ell)\cdot F^2(\ell) = m \cdot n \cdot F(n)
\end{equation}
where $\ell = 0$ is a plane defined over $\F_{q^3}$, $m = 0$ is a plane defined
over $\F_q$, and $n = 0$ is a plane defined over $\F_{q^2}$.
\end{thm}

The idea: $m = 0$ defines the plane of the 3-cycle orbit, which consists of
$m = F^i(\ell) = 0$, $i = 0,1,2$. 
A 6-cycle orbit consists of the other 6 ``obvious lines'' from \eqref{detform}.

\end{frame}

\begin{frame}
{\bf More details}

The ``obvious lines'' mentioned before are the

\begin{eqnarray*}
n = \ell = 0, &F(n) = F(\ell) = 0,& n = F^2(\ell) = 0\\
F(n) = \ell = 0, &n = F(\ell) = 0,& F(n) = F^2(\ell) = 0
\end{eqnarray*}

coming from the form of the equation \eqref{detform}.

\textdbend It is \emph{not} the case that \emph{every} cubic with an equation of the form \eqref{detform}
is a $C_{12}$, though.  There are also $C_{10}$'s and $C_{23}$'s of this form.   
\end{frame}

\begin{frame}
{\bf Using this form -- Conjecture holds for small $q$}

By means of these Cayley-Salmon form equation, it's not too difficult to 
generate cubics in all the projective equivalence classes of $C_{12}$'s over
a small enough field, and I have verified the conjecture that way for $5 < q < 11$.  

Still, would like a better reason(!)
\end{frame}

\begin{frame}
{\bf Two final (vague) observations}

\begin{itemize} 
\item The form \eqref{detform}
$$\ell\cdot F(\ell)\cdot F^2(\ell) = m \cdot n \cdot F(n)$$
is quite reminiscent of the \emph{Weierstrass form} of an elliptic curve
when you look at it the right way over $\F_q$:
$$({\rm irreducible\ cubic\ in\ } x) = w y^2$$
By taking plane sections of \eqref{detform}, might be possible
to use known facts about Weierstrass equations(!)
\item   But there's got to be a \emph{pigeonhole principle} component
too because the ultimate idea (if the conjecture is true!)
has to be: $X$ has lots of $\F_q$-points $\Rightarrow$
some plane section has lots of $\F_q$-points.  
\end{itemize}

\end{frame}

 
\end{document}

