\documentclass[hyperref={colorlinks=true}]{beamer}
\usepackage{amsmath,amsfonts,amsthm}
\usepackage[latin1]{inputenc}
\usepackage[OT2,T1]{fontenc}
\usepackage[frenchb]{babel}

\usepackage{xypic}\xyoption{tips}
\usepackage{pgfplots}
\usepackage{url}

% Beamer defaults:
% Uncomment a theme of choice...
%\usetheme{Berlin}
%\usetheme{Copenhagen}
\usetheme{Darmstadt}
%\usetheme{Marburg}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}
\usefonttheme{structurebold}
\setbeamercovered{dynamic}

\renewcommand{\AA}{\mathbb{A}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cC}{\mathcal{C}}
\renewcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\renewcommand{\cH}{\mathcal{H}}
\renewcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\renewcommand{\cR}{\mathcal{R}}
\newcommand{\cX}{\mathcal{X}}

\newcommand{\Aut}{\mathrm{Aut}}

\newtheorem{theoreme}{Théorème}
\newtheorem{lemme}[theoreme]{Lemme}
\newtheorem{proposition}[theoreme]{Proposition}

\begin{document}

\title{Le puzzle SET}
\author{David Kohel\newline
Institut de Mathématiques de Marseille}
\date{Marseille \newline 26 novembre 2018}


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

\begin{frame}\tableofcontents\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The puzzle SET}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Le puzzle SET}
Le puzzle \texttt{SET} consiste d'un ensemble de cartes, portant chaqu'un
un symbole ou graphique déterminé par un des trois valeurs pour chaqu'un
des quatre attributs:
\begin{itemize}
\item Couleur (bleu, rouge, vert) $\in \cC$,
\item Forme (losange, ovale, vague [ou cacahuète]) $\in \cF$,
\item Remplissage (vide, hachuré, plein) $\in \cR$,
\item Nombre (un, deux, trois) $\in \cN$.
\end{itemize}
\begin{definition}
Un SET est un ensemble de trois cartes distinctes, tel que pour chaqu'un des
quatre attributs les valeurs sont soit tous égales, soit tous distinctes
\end{definition}
\end{frame}

\begin{frame}
\frametitle{Objectifs du puzzle}

L'objectif du puzzle est de trouver tous les SETs parmi un ensemble de $12$
cartes distinctes. Par exemple, dans les cartes ci-dessous
\begin{center}
\begin{tabular}{c@{\;}c@{\;}c}
\includegraphics[scale=0.50]{img/RougeDiamondVide1.png}&
\includegraphics[scale=0.50]{img/RougeDiamondHach3.png}&
\includegraphics[scale=0.50]{img/RougeOvalHach1.png}\\
\includegraphics[scale=0.50]{img/RougeOvalSolid1.png}&
\includegraphics[scale=0.50]{img/VertSquigHach2.png}&
\includegraphics[scale=0.50]{img/VertDiamondSolid3.png}\\
\includegraphics[scale=0.50]{img/VertOvalVide1.png}&
\includegraphics[scale=0.50]{img/VioletSquigVide1.png}&
\includegraphics[scale=0.50]{img/VioletSquigHach2.png}\\
\includegraphics[scale=0.50]{img/VioletSquigSolid1.png}&
\includegraphics[scale=0.50]{img/RougeSquigHach2.png}&
\includegraphics[scale=0.50]{img/VertOvalHach1.png}
\end{tabular}
\end{center}
on identifie un premier SET:
\begin{center}
\begin{tabular}{c@{\;}c@{\;}c}
\includegraphics[scale=0.50]{img/RougeDiamondVide1.png}&
\includegraphics[scale=0.50]{img/VertOvalVide1.png}&
\includegraphics[scale=0.50]{img/VioletSquigVide1.png}
\end{tabular}
\end{center}
\end{frame}

\begin{frame}
\frametitle{An affine relation [en]}

If we (arbitrarily) label the values of an attribute by $0$, $1$, and $2$
in the field $\FF_3$, then the condition that a triple $(x,y,z)$ of values
are either all equal or all distinct is equivalent to the relation
$$
x + y + z = 0 \in \FF_3.
$$
A card in Set can be identified with vector $x = (x_1,x_2,x_3,x_4) \in \FF_3^4$
under a choice of labelings of its attributes.
\vspace{1mm}

A triple of cards constitutes a SET if and only if the triple $(x,y,z)$
of associated vectors satisfies
$$
x + y + z = 0 \in \FF_3^4.
$$
%that is, $x_i + y_i + z_i = 0$ for each coordinate, $1 \le i \le 4$.
\end{frame}

\begin{frame}
\frametitle{An affine line [en]}

\textbf{Example.}
Suppose for instance we have the triple of vectors in $\FF_3^4$,
$$
x = (1,0,0,0),\ y = (0,1,2,1),\ z = (2,2,1,2).
$$
We verify the relation $x + y + z = 0$.
If we fix $x$ as a base point and set $v = y-x = (2,1,2,1)$,
then we see that
$$
z = (1,2,1,2) + x = 2v + x,
$$
and hence $\{x,y,z\} = \{cv + x \;:\; c \in \FF_3 \} = L + x$, where
$L$ is the line spanned by $v$.
\vspace{2mm}

Such a triple of vectors is called an {\it affine line} (in $\FF_3^4$),
which motivates the definition of affine space.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Affine space}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Espace affine}

Un ensemble $\cE$ est muni d'une structure d'\textit{espace affine} par
la donnée d'un espace vectoriel $E$ (sa {\it direction})
et d'une application
%$\Theta$ qui associe un vecteur de $E$ à tout couple de points de $\cE$:
$$
\begin{array}{r@{\;}c@{\;}l}
\Theta: \cE \times \cE & \longrightarrow & E\\
                 (A,B) & \longmapsto     & \overrightarrow{AB}
\end{array}
$$
telle que
\begin{itemize}
\item
pour tout $A$ de $\cE$, l'application partiel $\Theta_A: \cE \rightarrow E$,
donnée par $$\Theta_A(B) = \overrightarrow{AB},$$ soit une bijection, et
\item
pour tous points $A$, $B$ ,$C$ de $\cE$, on ait $\overrightarrow{AB}
= \overrightarrow{AC} + \overrightarrow{CB}$.
\end{itemize}
\vspace{1mm}

Si la dimension d'un espace affine est un, on l'appelle une {\it droite affine};
si la dimension est deux, on dit un {\it plan affine}.
\end{frame}

\begin{frame}
\frametitle{Sous-espaces affines}
Un sous-ensemble $\cF$ de $\cE$ est un {\it sous-espace affine} si pour tout point
$A \in \cF$, l'ensemble $F = \Theta_A(\cF)$ est un sous-espace vectoriel de $E$.
On peut démontrer que $F$ est indépendent du choix de $A$.
\vspace{2mm}

\textbf{Remarque.} Toute espace vectoriel $E$ est un espace affine (qui est
sa propre direction et tel que $\Theta(u,v) = v - u$).

\vspace{2mm}

\begin{proposition}
Tout sous-espace affine $\cF$ d'un espace vectoriel $E$ est de la forme $F + v$,
où $F$ est un sous-espace vectoriel et $v \in E$ est un vecteur.
\end{proposition}
\vspace{2mm}

\textbf{Remarque.} La définition d'un espace affine ne place pas de condition
sur le corps de base de sa direction. Dans la suite on donne l'exemple des
droites affines dans $\FF_3^2$.
\vspace{2mm}

\end{frame}

\begin{frame}
\frametitle{Exemple: droites affines dans $\FF_3^2$}

\textbf{Exemple.} Soit $E = \FF_3^2$, un plan vectoriel sur $\FF_3$. Les droites
affines dans $E$ sont donc de la forme $D + v$, où $D$ est une droite vectorielle.
Il y a quatre droites $D$ dans $\FF_3^2$ et donc $12 = 4 \times 3$ droites affines.

\begin{center}
\begin{tikzpicture}[scale=0.50]
\begin{axis}[
    xmin=-1.5,xmax=1.5,
    ymin=-1.5,ymax=1.5,
    xtick={-1,0,1},
    ytick={-1,0,1},
    ymajorgrids=true,
    grid style=dashed,
]
% Affine points:
\addplot[color=black,mark=*,mark size=2pt]coordinates{(-1,-1)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(-1,0)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(-1,1)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(0,-1)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(0,0)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(0,1)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(1,-1)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(1,0)};
\addplot[color=black,mark=*,mark size=2pt]coordinates{(1,1)};
% Vertical affine lines:
\addplot[color=blue,]coordinates{(-1,-1.5)(-1,1.5)};
\addplot[color=red,]coordinates{(0,-1.5)(0,1.5)};
\addplot[color=blue,]coordinates{(1,-1.5)(1,1.5)};
% Other affine lines:
\addplot[domain=-1.5:0.5,color=blue,]{x+1};
\addplot[domain=0.5:1.5,color=blue,]{x-2};
\addplot[domain=-1.5:1.5,color=red,]{x};
\addplot[domain=-1.5:-0.5,color=blue,]{x+2};
\addplot[domain=-0.5:1.5,color=blue,]{x-1};
%
\addplot[domain=-0.5:1.5,color=blue,]{-x+1};
\addplot[domain=-1.5:-0.5,color=blue,]{-x-2};
\addplot[domain=-1.5:1.5,color=red,]{-x};
\addplot[domain=0.5:1.5,color=blue,]{-x+2};
\addplot[domain=-1.5:0.5,color=blue,]{-x-1};
%
\addplot[domain=-1.5:1.5,color=blue,]{1};
\addplot[domain=-1.5:1.5,color=red,]{0};
\addplot[domain=-1.5:1.5,color=blue,]{-1};
\end{axis}
\end{tikzpicture}\\
\quad{Droites affines dans $\FF_3^2$}
\end{center}

N.B. En général, le nombre de droites affines dans $\FF_p^n$ est
$$
|\PP^{n-1}(\FF_p)| \cdot |\FF_p^{n-1}| = \frac{(p^n-1)}{(p-1)} \cdot p^{n-1}\cdot
$$
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The main theorem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Isomorphisme et classes d'équivalence affine}

Une application $\varphi: \cE \rightarrow \cF$ d'espaces affines est
{\it affine} s'il existe une application linéaire $f: E \rightarrow F$
de leurs directions tel que
$$
\Theta(\varphi(A),\varphi(B)) = f(\Theta(A,B)).
$$

On rappelle que les donnés d'une structure d'espace affine sur $\cX$
et d'un point $A \in \cX$ déterminent une bijection $\iota = \Theta_A:
\cX \rightarrow E$.

Inversement, une bijection $\iota: \cX \rightarrow E$ induit une structure
d'espace affine $\Theta(A,B) = \iota(B) - \iota(A)$.
\vspace{2mm}

On dit que deux bijections $\iota_1,\iota_2: \cX \rightarrow E$, entre un ensemble
$\cX$ et un espace vectoriel $E$, sont dans la même classe {\it équivalence affine}
s'il existe un automorphisme affine $\varphi$ de $E$ tel que
$\iota_2 = \varphi \circ \iota_1$.
\end{frame}

\begin{frame}
\frametitle{Espaces affines de cardinal $3$}

Avant d'enoncer le théorème de classification des SET, on caracterise
les structures d'espace d'une ensemble de 3 éléments.

\begin{lemme}
Toute permutation de $\FF_3$ est affine.
\end{lemme}

\begin{proof}
Les automorphismes affines sont de la forme $x \mapsto ax + b$, pour
$(a,b) \in \FF_3^* \times \FF_3$, qui parcourrent les six permutations
de $\FF_3$.
\end{proof}

Par conséquent il n'y a qu'une seule classe d'équivalence affine d'un
ensemble de 3 éléments:

\begin{proposition}
Soit $\cX$ un ensemble de cardinal $3$. Toutes les bijections $\cX \rightarrow \FF_3$
appartiennent à la même classe d'équivalence affine.
\end{proposition}
\end{frame}

\begin{frame}
\frametitle{Le théorème principal}

Soient $\cC$, $\cF$, $\cR$ et $\cN$ les ensembles:
$$
\begin{array}{l}
\cC = \{ \texttt{bleu}, \texttt{rouge}, \texttt{vert} \},\\
\cF = \{ \texttt{losange}, \texttt{ovale}, \texttt{vague} \},\\
\cR = \{ \texttt{vide}, \texttt{hachuré}, \texttt{plein} \},\\
\cN = \{1,2,3\}.
\end{array}
$$
Des bijections de ces ensembles avec $\FF_3$ déterminent une structure
d'espace affine sur $\cE = \cC \times \cF \times \cR \times \cN$, avec
direction $E = \FF_3^4$.

\begin{theorem}
Soient fixées des bijections entre des attributs de couleur, forme,
remplissage, et nombre avec le corps $\FF_3$.
Les triples de cartes constituant un SET sont des droites affines
de $\cE$.
\end{theorem}
\end{frame}

\section{Conclusion}

\begin{frame}
\frametitle{Généralisations à quatre valeurs ?}

On peut se demander comment caracteriser les SETs si on admet 4 valeurs
(donc 4 cartes dans un SET, avec valeurs en chaque attribut soit tous
égales soit tous distinctes).
\vspace{2mm}

On peut mettre des attributs en bijection avec $\ZZ/4\ZZ$, $\FF_4$, ou $\FF_2^2$.
\vspace{2mm}

Pour que le choix d'une bijection parmi 24 soit non pertinant, il faut
une seule classe d'équivalence affine.
Or, les cardinaux d'automorphismes affines sont:
$$
\hspace{-4mm}|\Aut(\ZZ/4\ZZ)| = 2 \cdot 4 = 8,\;
|\Aut(\FF_4)| = 3 \cdot 4 = 12,\;
|\Aut(\FF_2^2)| = 6 \cdot 4 = 24.
$$
Seule le dernier parcourt toutes les permutations. On doit donc choisir
des bijections avec $E = \FF_2^2$, donnant une structure de plan affine
sur $\FF_2$.
\vspace{2mm}
\centerline{{\large\bf FIN}}

\end{frame}
\end{document}

\section{The field of three elements}

\begin{frame}
\frametitle{Le corps de trois éléments}

L'ensemble $\{0,1,2\}$, équipé de l'addition et la multiplication
$$
\begin{array}{c|ccc}
+ & 0 & 1 & 2\\ \hline
0 & 0 & 1 & 2\\
1 & 1 & 2 & 0\\
2 & 2 & 0 & 1
\end{array}
\qquad
\begin{array}{c|ccc}
\cdot & 0 & 1 & 2\\ \hline
0 & 0 & 0 & 0\\
1 & 0 & 1 & 2\\
2 & 0 & 2 & 1
\end{array}
$$
est un corps (anneau dont tout élément non nul est inversible).
\vspace{4mm}

On le note $\FF_3$.
\end{frame}
