Leopardi-database-of-SRG-5ICC-2017-talk.tex

\documentclass[pdf,sprung,slideColor,nocolorBG]{beamer}
%
%\documentclass[hyperref={pdfpagelabels=false}]{beamer}
\mode<presentation>

\newenvironment{colortheme}[1]{
\def\ProvidesPackageRCS $##1${\relax}
\renewcommand{\ProcessOptions}{\relax}
\makeatletter
\input beamercolortheme#1.sty
\makeatother
}{}

\let\Tiny=\tiny
\usetheme{Adelaide}
\usefonttheme[stillsansseriftext]{serif}
\setbeamerfont{structure}{series=\bfseries}
\setbeamertemplate{frametitle}[default][center]
\usepackage[figurename={}]{caption}
\usepackage[latin1]{inputenc}
%\usepackage{amsmath}   %needed for \begin{align}... \end{align} environment
\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{amscd}
%\usepackage[all]{xy}
\usepackage{xcolor}
\usepackage{enumerate}
%
\newcommand{\slidecite}[1]{\tiny{(#1)}\normalsize{}}
\newcommand{\smallcite}[1]{\small{(#1)}\normalsize{}}

\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mf}[1]{\mathbf{#1}}
\newcommand{\Emph}[1]{\emph{\textcolor{blue}{#1}}}
\newcommand{\Red}[1]{\mathbf{\textcolor{red}{#1}}}

\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\To}{\rightarrow}

\newcommand{\Cay}[1]{\operatorname{Cay}\left(#1\right)}
\newcommand{\Clique}[1]{\omega\left(#1\right)}
\newcommand{\dual}[1]{\widetilde{#1}}
\newcommand{\support}[1]{\operatorname{supp}\left(#1\right)}
\newcommand{\weight}[1]{\operatorname{wt}\left(#1\right)}
\newcommand{\weightclass}[1]{\operatorname{wc}\left(#1\right)}

\newcommand{\F}{\mb{F}}
\newcommand{\G}{\mb{G}}
\newcommand{\R}{\mb{R}}
\newcommand{\Z}{\mb{Z}}
\newtheorem{Def}{Definition}
\newtheorem{Conjecture}{Conjecture}
\newtheorem{Question}{Question}
\newtheorem{Proposition}{Proposition}

\title{Yet another database of strongly regular graphs}
\author{Paul Leopardi}

\date{For 5th International Combinatorics Conference (5ICC)
\\
Monash University
\\
December 2017}

\institute{University of Melbourne
\\
Australian Government - Bureau of Meteorology}
\titlegraphic{
%\includegraphics[angle=0,width=10mm]{../../common/beamer-anu-colourlogo.png}
%\includegraphics[angle=0,width=20mm]{../../common/carma_logo.jpg}
}
\begin{document}

\frame{\titlepage}
\begin{frame}
\frametitle{Acknowledgements}
\begin{center}
Robin Bowen,
An Braeken,
Nathan Clisby,
Robert Craigen,
Joanne Hall,
David Joyner,
Philippe Langevin,
Matthew Leingang,
William Martin,
Padraig {\'O} Cath{\'a}in,
Judy-anne Osborn,
Dima Pasechnik,
William Stein,
Natalia Tokareva, and
Sanming Zhou.

~

Australian National University. University of Newcastle, Australia. University of Melbourne.

Australian Government - Bureau of Meteorology.

~

National Computational Infrastructure.

~

SageMath, CoCalc, Bliss, Nauty, MPI4py, SQLite3, DB Browser for SQLite, PostgreSQL, Psycopg2.
\end{center}
\end{frame}

\begin{frame}
\frametitle{Serious Question}
\begin{center}
\vspace{+10mm}
\large{}
What would \Emph{you} do with a ``large'' database of strongly regular graphs?
\normalsize{}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Overview}
%\begin{center}
\begin{itemize}
\item
Preliminaries: bent functions and their Cayley graphs.

~

\item
Some results in 8 dimensions.

~

\item
Precedents: other databases.

~

\item
Preliminary database and interface designs.

~

\item
Prototype databases.

~

\item
Prospects.

~

\item
Source code and documentation.
\end{itemize}

%\end{center}
\end{frame}

\section{Preliminaries}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{Motivation}

In a construction for Hada\-mard matrices, I encountered
two sequences of \Emph{bent} Boolean functions,
\begin{align*}
\sigma_m &: \F_2^{2m} \To \F_2, \quad \tau_m : \F_2^{2m} \To \F_2,
\end{align*}
whose Cayley graphs are \Emph{strongly regular} with parameters
\begin{align*}
(v,k,\lambda,\mu) &= (4^m, 2^{2 m - 1} - 2^{m-1}, 2^{2 m - 2} - 2^{m-1}, 2^{2 m - 2} - 2^{m-1}),
\end{align*}
but the graphs for $\sigma_m$ and $\tau_m$ are isomorphic only when

$m=1,2$ or $3.$

~

Question: \Emph{Which strongly regular graphs arise as Cayley graphs of bent Boolean functions?}

\slidecite{L 2014, 2015, 2017}
\end{frame}
\end{colortheme}

\begin{colortheme}{seagull}

\begin{frame}
\frametitle{Bent functions}
% Bent functions can be defined in a number of equivalent ways.
% The definition used here involves the Walsh Hadamard Transform.
\begin{Def}
\label{def-Walsh-Hadamard-transform}
The Walsh Hadamard transform of
a Boolean function $f : \F_2^{2m} \To \F_2$ is
\begin{align*}
W_f(x)
&:=
\sum_{y \in \F_2^{2m}} (-1)^{f(y) + \langle x, y \rangle}
\end{align*}
\end{Def}

\begin{Def}
\label{def-Bent-function}
A Boolean function $f : \F_2^{2m} \To \F_2$ is \Emph{bent}
if and only if its Walsh Hada\-mard transform has constant absolute value $2^{m}$.
% \cite[p. 74]{Dil74}
% \cite[p. 300]{Rot76}.
\end{Def}
\slidecite{Dillon 1974; Rothaus 1976}
\end{frame}
\begin{frame}
\frametitle{Dual bent functions}

\begin{Def}
\label{def-dual-Bent-function}
For a bent function  $f : \F_2^{2m} \To \F_2$, the function $\dual{f}$, defined by
\begin{align*}
(-1)^{\dual{f}(x)} &:= 2^{-m} W_f(x)
\end{align*}
is called the \Emph{dual} of $f$.
\end{Def}

~

The function $\dual{f}$ is also a bent function on $\F_2^{2m}$.

~

~

\slidecite{Dillon 1974; Rothaus 1976}
\end{frame}

\begin{frame}
\frametitle{Example}

The function  $f : \F_2^2 \To \F_2$  defined by $f(x) := x_0 x_1$
is bent, since
\begin{align*}
W_f(x)
=&
\sum_{y \in \F_2^2} (-1)^{f(y) + \langle x, y \rangle}
\\
=&\ (-1)^{f(0,0) + \langle x, (0,0) \rangle}
 + (-1)^{f(1,0) + \langle x, (1,0) \rangle} +
\\
\phantom{=}&\ (-1)^{f(0,1) + \langle x, (0,1) \rangle}
 + (-1)^{f(1,1) + \langle x, (1,1) \rangle}
\\
=&\ (-1)^{0 + 0} + (-1)^{0 + x_0} + (-1)^{0 + x_1} + (-1)^{1 + x_0 + x_1}
\\
=&\ 1 + (-1)^{x_0} + (-1)^{x_1} - (-1)^{x_0 + x_1}
\\
=&\ 2 \times (-1)^{f(x)},
\end{align*}
so $\dual{f} = f$, and $f$ is \Emph{self-dual}.
%
\end{frame}

\begin{frame}
\frametitle{Bent functions and affine functions}
Bent functions are at maximum Hamming distance from affine functions.
For $f : \F_2^2 \To \F_2,$ this distance is 1 \slidecite{Meier and Staffelbach 1989}.
\scriptsize{}
\begin{align*}
\begin{array}{|cccc|}
\hline
(0,0)& (1,0)& (0,1)& (1,1)
\\
\hline
0 & 0 & 0 & 0
\\
\Red{0}& \Red{0} & \Red{0} & \Red{1}
\\
\Red{0}& \Red{0} & \Red{1} & \Red{0}
\\
0 & 0 & 1 & 1
\\
\Red{0}& \Red{1} & \Red{0} & \Red{0}
\\
0 & 1 & 0 & 1
\\
0 & 1 & 1 & 0
\\
\Red{0}& \Red{1} & \Red{1} & \Red{1}
\\
\Red{1}& \Red{0} & \Red{0} & \Red{0}
\\
1 & 0 & 0 & 1
\\
1 & 0 & 1 & 0
\\
\Red{1}& \Red{0} & \Red{1} & \Red{1}
\\
1 & 1 & 0 & 0
\\
\Red{1}& \Red{1} & \Red{0} & \Red{1}
\\
\Red{1}& \Red{1} & \Red{1} & \Red{0}
\\
1 & 1 & 1 & 1
\\
\hline
\end{array}
\end{align*}
\normalsize{}
\end{frame}

\end{colortheme}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{Weights and weight classes}
\begin{Def}
The \Emph{weight} of a binary function is the cardinality of its \Emph{support}.
For $f$ on $\F_2^{2m}$
\begin{align*}
\support{f} &:= \{x \in \F_2^{2m} \mid f(x)=1 \}.
\end{align*}

A bent function $f$ on $\F_2^{2m}$ has weight
\begin{align*}
\weight{f} &= 2^{2 m - 1} - 2^{m-1} \quad (\text{weight class~} \weightclass{f}=0), \text{~or}
\\
\weight{f} &= 2^{2 m - 1} + 2^{m-1} \quad (\text{weight class~} \weightclass{f}=1).
\end{align*}
% If $f(0)=0$ then $\weightclass{\Cay{f}} := \weightclass{f}$.
\end{Def}
\end{frame}

\end{colortheme}

%\section{Cayley graphs and linear codes}

\begin{colortheme}{seagull}

\begin{frame}
\frametitle{The Cayley graph of a Boolean function}
%\begin{center}
The \Emph{Cayley graph} $\Cay{f}$ of a Boolean function

~

\begin{align*}
%
f : \F_2^n \To \F_2 \quad \text{where} \quad f(0) = 0
%
\end{align*}

~

is
an undirected graph with

\begin{align*}
V(\Cay{f}) &:= \F_2^n, \quad (x,y) \in E(\Cay{f}) \Leftrightarrow f(x+y) = 1.
\end{align*}

~

\slidecite{Bernasconi and Codenotti 1999}
\end{frame}

\begin{frame}
\frametitle{Strongly regular graphs}
%\begin{center}
A simple graph $\Gamma$ of order $v$ is \Emph{strongly regular} with parameters
$(v,k,\lambda,\mu)$ if

~

\begin{itemize}
 \item
each vertex has degree $k,$

~
 \item
each adjacent pair of vertices has $\lambda$ common neighbours, and

~
\item
each nonadjacent pair of vertices has $\mu$ common neighbours.
\end{itemize}

~

~

\slidecite{Brouwer, Cohen and Neumaier 1989}

%\end{center}
\end{frame}

\begin{frame}
\frametitle{Bent functions and strongly regular graphs}

\begin{Proposition}
\smallcite{Bernasconi and Codenotti 1999}

The Cayley graph $\Cay{f}$ of a bent function $f$ on $\F_2^{2m}$

with $f(0)=0$ is a strongly regular graph with $\lambda = \mu.$
\end{Proposition}

The parameters of $\Cay{f}$ are
\begin{align*}
(v,k,\lambda) = &(4^m, 2^{2 m - 1} - 2^{m-1}, 2^{2 m - 2} - 2^{m-1})
\\
  \text{or} \quad &(4^m, 2^{2 m - 1} + 2^{m-1}, 2^{2 m - 2} + 2^{m-1}).
\end{align*}

~

\slidecite{Menon 1962; Dillon 1974; Bernasconi and Codenotti 1999}
%\end{center}
\end{frame}
\end{colortheme}

\begin{colortheme}{seagull}

\begin{frame}
\frametitle{Extended affine equivalence}

\begin{Def}
For bent functions $f,g : \F_2^{2m} \To \F_2$,

$f$ is \Emph{extended affine equivalent} to $g$ if and only if
\begin{align*}
g(x) &= f(A x + b) + \langle c, x \rangle + \delta
\end{align*}
for some $A \in GL(2m,2)$, $b, c \in \F_2^{2m}$, $\delta \in \F_2$.
\end{Def}

~

~

\slidecite{Budaghyan, Carlet and Pott 2006; Carlet and Mesnager 2011}
\end{frame}

\end{colortheme}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{General linear equivalence}

\begin{Def}
For bent functions $f,g : \F_2^{2m} \To \F_2$,
$f$ is \Emph{general linear equivalent} to $g$ if and only if
\begin{align*}
g(x) &= f(A x)
\end{align*}
for some $A \in GL(2m,2)$.
\end{Def}
\end{frame}
\begin{frame}
\frametitle{Extended translation equivalence}

\begin{Def}
For bent functions $f,g : \F_2^{2m} \To \F_2$,

$f$ is \Emph{extended translation equivalent} to $g$ if and only if
\begin{align*}
g(x) &= f(x + b) + \langle c, x \rangle + \delta
\end{align*}
for $b, c \in \F_2^{2m}$, $\delta \in \F_2$.
\end{Def}
\end{frame}

\begin{frame}
\frametitle{Cayley equivalence}
\begin{Def}
%
For $f, g : \F_2^{2m} \To \F_2$, with both $f$ and $g$ bent,

we call $f$ and $g$ \Emph{Cayley equivalent},
and write $f \equiv g$,

if and only if $f(0)=g(0)=0$ and $\Cay{f} \equiv \Cay{g}$ as graphs.

~

Equivalently, $f \equiv g$ if and only if $f(0)=g(0)=0$ and

there exists a bijection $\pi : \F_2^{2m} \To \F_2^{2m}$ such that
\begin{align*}
g(x+y) &= f \big(\pi(x)+\pi(y)\big) \quad \text{for all~} x,y \in \F_2^{2m}.
\end{align*}
\end{Def}
\end{frame}
\begin{frame}
\frametitle{Extended Cayley equivalence}
\begin{Def}
For $f, g : \F_2^{2m} \To \F_2$, with both $f$ and $g$ bent,

if there exist $\delta, \epsilon \in \{0,1\}$ such that $f + \delta \equiv g + \epsilon$,

we call $f$ and $g$ \Emph{extended Cayley (EC) equivalent} and write $f \cong g$.
\end{Def}
Extended Cayley equivalence is an equivalence relation on the set of all bent functions on $\F_2^{2m}$.
\end{frame}

\begin{frame}
\frametitle{General linear equivalence \\ implies Cayley equivalence}

\begin{Theorem}
If $f$ is bent with $f(0)=0$ and $g(x) := f(A x)$ where $A \in GL(2m,2)$,
then $g$ is bent with $g(0)=0$ and $f \equiv g$.
\end{Theorem}
\begin{proof}
\begin{align*}
g(x+y) &= f\big(A(x+y)\big) = f(A x + A y)\quad \text{for all~} x,y \in \F_2^{2m}.
\end{align*}
\end{proof}

\end{frame}

\begin{frame}
\frametitle{Extended affine, extended translation, and extended Cayley equivalence (1)}

\begin{Theorem}
For $A \in GL(2m,2)$, $b, c \in \F_2^{2m}$, $\delta \in \F_2$,
$f : \F_2^{2m} \To \F_2$,

the function
\begin{align*}
h(x) &:= f(A x + b) + \langle c, x \rangle + \delta
\intertext{can be expressed as $h(x) = g(A x)$ where}
g(x) &:= f(x+b) + \langle (A^{-1})^T c, x \rangle + \delta,
\end{align*}
and therefore if $f$ is bent then $h \cong g$.
\end{Theorem}
\end{frame}

\begin{frame}
\frametitle{Extended affine, extended translation, and extended Cayley equivalence (2)}

Therefore, to determine the extended Cayley equivalence classes within the extended affine equivalence class of
a bent function $f : \F_2^{2m} \To \F_2$, for which $f(0)=0$, we need only examine
the extended translation equivalent functions of the form
\begin{align*}
f(x+b) + \langle c, x \rangle + f(b),
\end{align*}
for each $b, c \in \F_2^{2m}$.
\end{frame}

\end{colortheme}

\section{Some results in 8 dimensions}


\begin{colortheme}{seagull}

\begin{frame}
\frametitle{For 8 dimensions: \\ number of bent functions and EA classes}

According to Langevin and Leander (2011)
there are $99\,270\,589\,265\,934\,370\,305\,785\,861\,242\,880 \approx 2^{106}$ bent functions in dimension 8.

~

The number of EA classes has not yet been published, let alone a list of representatives.

~

~

~

~

\slidecite{Langevin and Leander 2011}
\end{frame}

\begin{frame}
\frametitle{For 8 dimensions, up to degree 3: \\ extended translation classes}

Ten extended affine classes are listed in Braeken's thesis (2006),

containing the following extended translation classes:

\tiny{}
\begin{align*}
\def\arraystretch{1.2}
\begin{array}{|cl|}
\hline
\text{Class} &
\text{Representative}
\\
\hline
\,[f_{ 8 , 1 }] & f_{ 8 , 1 } :=
\begin{array}{l}
x_{0} x_{1} + x_{2} x_{3} + x_{4} x_{5} + x_{6} x_{7}
\end{array}
\\
\,[f_{ 8 , 2 }] & f_{ 8 , 2 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{3} + x_{1} x_{4} + x_{2} x_{5} + x_{6} x_{7}
\end{array}
\\
\,[f_{ 8 , 3 }] & f_{ 8 , 3 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{6} + x_{1} x_{3} x_{4} + x_{1} x_{5} + x_{2} x_{3} + x_{4} x_{7}
\end{array}
\\
\,[f_{ 8 , 4 }] & f_{ 8 , 4 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{2} + x_{0} x_{4} + x_{1} x_{3} x_{4} + x_{1} x_{5} + x_{2} x_{3} + x_{6} x_{7}
\end{array}
\\
\,[f_{ 8 , 5 }] & f_{ 8 , 5 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{6} + x_{1} x_{3} x_{4} + x_{1} x_{4} + x_{1} x_{5} + x_{2} x_{3} x_{5} + x_{2} x_{4} + x_{3} x_{7}
\end{array}
\\
\,[f_{ 8 , 6 }] & f_{ 8 , 6 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{3} x_{4} + x_{1} x_{6} + x_{2} x_{3} x_{5} + x_{2} x_{4} + x_{5} x_{7}
\end{array}
\\
\,[f_{ 8 , 7 }] & f_{ 8 , 7 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{1} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{3} x_{4} + x_{1} x_{4} + x_{1} x_{5} + x_{2} x_{3} x_{5}
\\
+\,  x_{2} x_{4} + x_{6} x_{7}
\end{array}
\\
\,[f_{ 8 , 8 }] & f_{ 8 , 8 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{5} + x_{1} x_{3} x_{4} + x_{1} x_{6} + x_{2} x_{3} x_{5} + x_{2} x_{4} + x_{3} x_{7}
\end{array}
\\
\,[f_{ 8 , 9 }] & f_{ 8 , 9 } :=
\begin{array}{l}
x_{0} x_{1} x_{6} + x_{0} x_{3} + x_{1} x_{4} + x_{2} x_{3} x_{6} + x_{2} x_{5} + x_{3} x_{4} + x_{4} x_{5} x_{6} + x_{6} x_{7}
\end{array}
\\
\,[f_{ 8 , 10 }] & f_{ 8 , 10 } :=
\begin{array}{l}
x_{0} x_{1} x_{2} + x_{0} x_{3} x_{6} + x_{0} x_{4} + x_{0} x_{5} + x_{1} x_{3} x_{4} + x_{1} x_{6} + x_{2} x_{3} x_{5} + x_{2} x_{4}
\\
+\,  x_{3} x_{7}
\end{array}
\\
\hline
\end{array}
\end{align*}
\slidecite{Braeken 2006; Tokareva 2015}
\normalsize{}
\end{frame}

\end{colortheme}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{ET classes  $[f_{8,5}]$ and $[f_{8,6}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{../matrix_plot/re8_5_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[f_{8,5}]$: 9 extended Cayley classes}
  \label{fig:re8_5_bent_cayley_graph_index_matrix}
\end{minipage}%
\begin{minipage}{.48\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{../matrix_plot/re8_6_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[f_{8,6}]$: 9 extended Cayley classes}
  \label{fig:re8_6_bent_cayley_graph_index_matrix}
\end{minipage}
\end{figure}
The same 9 EC classes, with the same frequencies!

\slidecite{colormap: gist\_stern, colours matched to extended Cayley classes}
\end{frame}

\begin{frame}[fragile]
\frametitle{Functions $f_{8,5}$ and $f_{8,6}$ are linearly equivalent}

\Emph{Proof}

~

Apply the permutation $\pi := (x_0\ x_5\ x_4)(x_1\ x_2\ x_3)(x_6\ x_7)$ to
\footnotesize{
\begin{align*}
f_{8,5}
&=
x_{0} x_{1} x_{2} + x_{0} x_{6} + x_{1} x_{3} x_{4} + x_{1} x_{4} + x_{1} x_{5} + x_{2} x_{3} x_{5} + x_{2} x_{4} + x_{3} x_{7}
%\end{align*}
%}\normalsize{}
\intertext{\normalsize{to obtain}}
%\small{
%\begin{align*}
\pi(f_{8,5})
&=
x_{5} x_{2} x_{3} + x_{5} x_{7} + x_{2} x_{1} x_{0} + x_{2} x_{0} + x_{2} x_{4} + x_{3} x_{1} x_{4} + x_{3} x_{0} + x_{1} x_{6}
\\
&=
x_{0} x_{1} x_{2} + x_{0} x_{2} + x_{0} x_{3} + x_{1} x_{3} x_{4} + x_{1} x_{6} + x_{2} x_{3} x_{5} + x_{2} x_{4} + x_{5} x_{7}
\\
&= f_{8,6}.
\\
&\ \Box
\end{align*}
}\normalsize{}
\end{frame}

\end{colortheme}

\begin{colortheme}{seagull}

\begin{frame}[fragile]
\frametitle{For 8 dimensions: Bent functions from CAST-128 S-boxes}

The CAST-128 encryption algorithm is used in PGP and elsewhere.

CAST-128, including the S-boxes, is specified by IETF RFC 2144:
\begin{verbatim}
https://www.ietf.org/rfc/rfc2144.txt
\end{verbatim}

The algorithm uses 8 S-boxes,
each of which consists of 32 binary bent functions of degree 4 in 8 dimensions,
giving a total of 256 bent functions.

~

~

~

\slidecite{Adams 1997}
\end{frame}

\end{colortheme}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{CAST-128 ET class $[cast128_{1,0}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_1_0_weight_class_matrix.png}
  \captionof{figure}{$[cast128_{1,0}]$: weight classes ~~~~~~ ~~~~~~~~\\~~~~~}
  \label{fig:cast128_1_0_weight_class_matrix}
\end{minipage}
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_1_0_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{1,0}]$: $65\,536$ extended Cayley classes.\\Total including duals is $131\,072$.}
  \label{fig:cast128_1_0_bent_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
\slidecite{LHS colormap: gist\_stern; RHS colormap: jet}
\end{frame}

\begin{frame}
\frametitle{CAST-128 ET classes $[cast128_{2,1}]$ and $[cast128_{2,16}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_2_1_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{2,1}]$: $8\,256$ extended Cayley classes.\\Total including duals is $8\,256$.}
  \label{fig:cast128_2_1_bent_cayley_graph_index_matrix}
\end{minipage}%
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_2_16_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{2,16}]$: $32\,768$ extended Cayley classes.\\Total including duals is $65\,536$.}
  \label{fig:cast128_2_16_bent_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
\slidecite{colormap: jet}
\end{frame}

\begin{frame}
\frametitle{CAST-128 ET classes $[cast128_{4,27}]$ and $[cast128_{5,16}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_4_27_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{4,27}]$: $65\,536$ extended Cayley classes.\\Total including duals is $65\,536$.}
  \label{fig:cast128_4_27_bent_cayley_graph_index_matrix}
\end{minipage}%
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_5_16_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{5,16}]$: $33\,280$ extended Cayley classes.\\Total including duals is $66\,560$.}
  \label{fig:cast128_5_16_bent_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
\slidecite{colormap: jet}
\end{frame}

\begin{frame}
\frametitle{CAST-128 ET classes $[cast128_{5,27}]$ and $[cast128_{6,17}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_5_27_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{5,27}]$: $6\,144$ extended Cayley classes.\\Total including duals is $6\,144$.}
  \label{fig:cast128_5_27_bent_cayley_graph_index_matrix}
\end{minipage}%
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_6_17_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{6,17}]$: $65\,536$ extended Cayley classes.\\Total including duals is $65\,536$.}
  \label{fig:cast128_6_17_bent_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
\slidecite{colormap: jet}
\end{frame}

\begin{frame}
\frametitle{CAST-128 ET classes $[cast128_{7,15}]$ and $[cast128_{7,21}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_7_15_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{7,15}]$: $32\,768$ extended Cayley classes.\\Total including duals is $65\,536$.}
  \label{fig:cast128_7_15_bent_cayley_graph_index_matrix}
\end{minipage}%
\begin{minipage}{.48\textwidth}
  \centering
\includegraphics[width=.9\linewidth]{../matrix_plot/cast128_7_21_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[cast128_{7,21}]$: $32\,768$ extended Cayley classes.\\Total including duals is $65\,536$.}
  \label{fig:cast128_7_21_bent_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
\slidecite{colormap: jet}
\end{frame}
\end{colortheme}

\begin{colortheme}{seagull}

\begin{frame}[fragile]
\frametitle{For 8 dimensions: number of partial spread \\ bent functions and EA classes}

According to Langevin and Hou (2011)
there are $70\,576\,747\,237\,594\,114\,392\,064 \approx 2^{75.9}$ \Emph{partial spread} bent functions in dimension 8,
contained in $14\,758$ EA classes, of which $14\,756$ have degree 4.

~

The EA class representatives are listed at Langevin's web site

\begin{verbatim}
http://langevin.univ-tln.fr/project/spread/psp.html
\end{verbatim}

~

\slidecite{Langevin and Hou 2011}
\end{frame}

\end{colortheme}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{Example partial spread ET class $[psf_{9,5439}]$}
\begin{figure}
\centering
\begin{minipage}{.48\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{../matrix_plot/psf_9_5439_bent_cayley_graph_index_matrix.png}
  \captionof{figure}{$[psf_{9,5439}]$: 16 extended Cayley classes ~~ ~~~~ ~~~~ ~~~~~~~~~}
  \label{fig:psf_9_5439_bent_cayley_graph_index_matrix}
\end{minipage}
\begin{minipage}{.48\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{../matrix_plot/psf_9_5439_dual_cayley_graph_index_matrix.png}
  \captionof{figure}{$[psf_{9,5439}]$: 16 extended Cayley classes of dual bent functions}
  \label{fig:psf_9_5439_dual_cayley_graph_index_matrix}
\end{minipage}%
\end{figure}
6 of the 16 classes form 3 dual pairs of classes.

\slidecite{colormap: gist\_stern}
\end{frame}

\end{colortheme}

\section{Precedents}

\begin{colortheme}{seagull}
\begin{frame}
\frametitle{Precedents: databases of strongly regular graphs}
\begin{itemize}
 \item
Spence's lists of strongly regular graphs on at most 64 vertices.
 \begin{itemize}
  \item
Exhaustive lists of non-isomorphic graphs for some tuples of feasible parameters.
  \item
Flat text files.
 \end{itemize}

~

 \item
Brouwer's database of parameters of strongly regular graphs.

~

 \item
Cohen and Pasechnik's Sage implementation of Brouwer's database, with constructions.
 \begin{itemize}
  \item
Includes an example for each tuple of feasible parameters, if known.
  \item
Sage interface.
 \end{itemize}
\end{itemize}
\slidecite{Spence 1995-2006; Brouwer 2008-2017; Cohen and Pasechnik 2016-2017}
\end{frame}

\begin{frame}
\frametitle{Other recent mathematical databases}
\begin{itemize}
 \item
ISGCI - Information System on Graph Classes and their Inclusions
 \begin{itemize}
  \item
``\ldots an encyclopaedia of graph classes with an accompanying Java application that helps you to research what's known about particular graph classes.''
  \item
Web-based and Java interfaces.
 \end{itemize}

~

 \item
LMFDB - The L-functions and modular forms database
 \begin{itemize}
  \item
``The LMFDB is an extensive database of mathematical objects arising in Number Theory.''
  \item
Based on MongoDB and Python.
  \item
Web-based and Sage interfaces.
 \end{itemize}
\end{itemize}
\slidecite{H.N. de Ridder et al. 2001-2016; The LMFDB Collaboration 2007-2017}
\end{frame}

\end{colortheme}

\section{Preliminary designs}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{Database tables}
\begin{figure}
\centering
\begin{minipage}{\textwidth}
  \centering
\includegraphics[width=.75\linewidth]{Classification-schema-SQLite.png}
  \captionof{figure}{Database schema for SQLite version of the classification database.}
  \label{fig:Classification_schema_SQLite}
\end{minipage}%
\end{figure}
\end{frame}

\begin{frame}[fragile]
\frametitle{Sage interface: insert function}

\begin{verbatim}
insert_classification(conn, bfcgc, name=None):
\end{verbatim}

\begin{itemize}
 \item \texttt{conn}: Database connection.

~

 \item \texttt{bfcgc}: Cayley graph classification of the ET class of \\a bent function.

~

 \item \texttt{name}: Name of the ET class (optional).
\end{itemize}

\end{frame}

\begin{frame}[fragile]
\frametitle{Sage interface: select functions}

\begin{verbatim}
select_classification_where_bent_function(
    conn, bentf):
\end{verbatim}
\begin{itemize}
 \item \texttt{conn}: Database connection.
 \item \texttt{bentf}: Bent function representing an ET class.
\end{itemize}

~

\begin{verbatim}
select_classification_where_name(conn, name):
\end{verbatim}
\begin{itemize}
 \item \texttt{conn}: Database connection.
 \item \texttt{name}: Name of the ET class.
\end{itemize}

\end{frame}

\end{colortheme}

\section{Prototype databases}

\begin{colortheme}{jubata}

\begin{frame}
\frametitle{Prototype databases}
Three prototype relational databases, using SQLite:

\begin{itemize}
 \item\normalsize{}
Bent functions in 6 dimensions.
 \begin{itemize}
  \item\footnotesize{}
Database of 11 strongly regular graphs from 4 ET classes.
  \item\footnotesize{}
About 20 CPU minutes to calculate (2.93 GHz Intel Core i7, serial).
  \item\footnotesize{}
Database size 780 KB.
 \end{itemize}

 \item\normalsize{}
Bent functions in 8 dimensions, up to degree 3.
 \begin{itemize}
  \item\footnotesize{}
Database of 55 strongly regular graphs from 9 ET classes.
  \item\footnotesize{}
About 250 CPU hours to calculate (2.93 GHz Intel Core i7, serial).
  \item\footnotesize{}
Database size 65 MB.
 \end{itemize}

 \item\normalsize{}
Bent functions from the 8 S-boxes of CAST-128.
 \begin{itemize}
  \item\footnotesize{}
Database of more than \Emph{32 million} ($32\,914\,496$) strongly regular graphs from 256 ET classes and their duals.
  \item\footnotesize{}
About \Emph{9000 CPU hours} to calculate
(4500 CPU hours on\\NCI Raijin, MPI, 16 ranks, for 128 ET classes and their duals).
  \item\footnotesize{}
Database size \Emph{195 GB}.
 \end{itemize}
\end{itemize}

\normalsize{}
\end{frame}

\begin{frame}
\frametitle{Time to create SQLite CAST-128 database}
\begin{figure}
\centering
\begin{minipage}{.49\textwidth}
  \centering
  \includegraphics[width=1.0\linewidth]{CAST128-database-insert-times-by-existing.png}
  \label{fig:CAST128_database_insert_times_by_existing}
\end{minipage}
\begin{minipage}{.49\textwidth}
  \centering
  \includegraphics[width=1.0\linewidth]{CAST128-database-insert-times-by-time-of-day.png}
  \label{fig:CAST128_database_insert_times-By_time_of_day}
\end{minipage}%
\end{figure}
It took almost 3 days to insert 256 classifications \Emph{sequentially} into the SQLite version of the CAST-128 database.
\end{frame}

\begin{frame}
\frametitle{Using DB Browser with a prototype database}
\begin{figure}
\centering
\begin{minipage}{\textwidth}
  \centering
\includegraphics[width=1.00\linewidth]{Browser-session-SQLite.png}
%  \captionof{figure}{DB Browser session with a prototype classification database.}
  \label{fig:Browser_session_SQLite}
\end{minipage}%
\end{figure}
\end{frame}

\end{colortheme}

\section{Prospects}

\begin{colortheme}{jubata}

\begin{frame}[fragile]
\frametitle{Possible next steps}

\begin{itemize}
 \item
Submit ``Classifying bent functions by their Cayley graphs.''

~

 \item
Submit code to Sage project for review.

~

 \item
Gauge demand for the database. Find collaborators.

~

 \item
Arrange for hosting. Research Data Services?

~

 \item
Scale up to the partial spread bent functions?

 \begin{itemize}
  \item
This could be a database of about \Emph{2 billion SRGs},
\\
from 14\,758 ET classes, taking about \Emph{500\,000 CPU hours}
\\
to calculate and about \Emph{10 TB} to store.
 \end{itemize}
\end{itemize}
\end{frame}

\end{colortheme}

\section{Source code}

\begin{colortheme}{jubata}

\begin{frame}[fragile]
\frametitle{Source code and documentation}
~

CoCalc: Public worksheets, Sage and Python source code

\begin{verbatim}
http://tinyurl.com/Boolean-Cayley-graphs
\end{verbatim}

~

GitHub: Sage and Python source code

\begin{verbatim}
https://github.com/penguian/Boolean-Cayley-graphs
\end{verbatim}

~

SourceForge: Documentation

\begin{verbatim}
https://boolean-cayley-graphs.sourceforge.io/
\end{verbatim}
\end{frame}

\end{colortheme}

\end{document}