MOLS.tex

\documentclass{article}

\usepackage[maxbibnames=99]{biblatex}

\addbibresource{MOLS.bib}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
% \usepackage{amsrefs}
\usepackage{xargs}
\usepackage[pdftex,dvipsnames]{xcolor}
\usepackage[colorinlistoftodos,prependcaption,textsize=tiny]{todonotes}
\usepackage{enumitem}
\usepackage{titling}


% \usepackage{cite}
% \usepackage{natbib}

% \usepackage{apacite}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}
\newcommandx{\unsure}[2][1=]{\todo[linecolor=red,backgroundcolor=red!25,bordercolor=red,#1]{#2}}
\newcommandx{\change}[2][1=]{\todo[linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1]{#2}}
\newcommandx{\info}[2][1=]{\todo[linecolor=OliveGreen,backgroundcolor=OliveGreen!25,bordercolor=OliveGreen,#1]{#2}}
\newcommandx{\improvement}[2][1=]{\todo[linecolor=Plum,backgroundcolor=Plum!25,bordercolor=Plum,#1]{#2}}
\newcommandx{\thiswillnotshow}[2][1=]{\todo[disable,#1]{#2}}
\newcommand{\PG}{\mathrm{PG}}

\title{{\Huge Latin Hypercubes and Finite Projective Geometry} \\
  Summer Project 2020--2021}
% \subtitle{Summer project 2020-2021}
\author{Jake Faulkner \\
  Advisor: Geertrui Van de Voorde}
\date{University of Canterbury}


\begin{document}
\maketitle
\pagebreak
\section{Affine and Projective Spaces}
To begin we need some definitions, of latin squares and of vector spaces over finite fields.

\subsection{Finite Projective Spaces}

The original motivation for projective geometry was on making rigorous
statements such as “parallel lines meet at infinity”, where in particular artists were interested in perspective drawing that accurately reflected projective properties of eyesight (such as parallel train tracks appearing to meet at the horizon).
Whilst the study of projective geometry originally
began with real projective spaces, whose application to perspective drawing was
clear, such notions of points at infinity turn out to be useful when working in
finite geometry too. We will see how projective geometry has can help us understand the
traditionally combinatorial latin squares and hypercubes, but first we need some
preliminaries from finite projective geometry.

\begin{definition}
  The vector space \(V(n, q)\) is the vector space whose vectors are the ordered \(n\)-tuples of elements in \(\mathbb{F}_q\) and scalars in \(\mathbb{F}_q\).
\end{definition}

\begin{definition}
  The projective space \(\PG(n, q)\) is the geometry whose points, lines, dimension \(k\) subspaces are lines, planes and rank \(k + 1\) subspaces in \(V(n + 1, q)\) respectively. Incidence of subspaces in \(\PG(n, q)\) is inherited naturally from incidence in \(V(n + 1, q)\).
\end{definition}

Most of our work will be done using constructions involving \(\PG(2, q)\) and \(\PG(3, q)\). The following housekeeping lemmas will be useful for these constructions.

\begin{lemma}\label{lemma:1}
  The number of rank \(k\) subspaces in \(V(n, q)\) is \(\frac{(q^n - 1)(q^n - q)\ldots (q^n - q^{k - 1})}{(q^k - 1)(q^k - q)\ldots (q^k - q^{k - 1})}\).
\end{lemma}
\begin{proof}
  The numerator of describes the number of ways we can choose \(k\) ordered linearly independent points from \(V(n, q)\) to span a rank \(k\) subspace. The denominator counts the number of ordered bases in a rank \(k\) subspace.
\end{proof}
\begin{corollary}
  The number of rank \(k\) subspaces in \(V(n, q)\) containing a given subspace of rank \(d \leq k\) is
  \(\frac{(q^{n - d} - 1)(q^{n - d} - q) \ldots (q^{n - d} - q^{k - d - 1})}{(q^{k - d} - 1) (q^{k - d} - q) \ldots (q^{k - d} - q^{k - d - 1})}\).
\end{corollary}

\begin{lemma}\label{lemma:2}
  Given two subspaces \(V_1\) and \(V_2\) of a vector space \(V\), \(\dim (V_1 + V_2) = \dim V_1 + \dim V_2 - \dim (V_1 \cap V_2)\).
\end{lemma}

\begin{proof}
  Let \(V_1\) and \(V_2\) be two subspaces of a vector space \(V\) and consider a basis \(B\) for their intersection \(V_1 \cap V_2\). The basis \(B\) may be extended by adding additional basis vectors to get a basis for \(V_1\) and \(V_2\), we will call these bases \(B_1\) and \(B_2\) respectively.
  It follows that,

  \begin{equation*}
    | B_1 \cup B_2 | = |B_1| + |B_2| - |B_1 \cap B_2|
  \end{equation*}

  Each term describes the dimension of \(V_1 + V_2\), \(V_1\), \(V_2\), and \(V_1 \cap V_2\) respectively.
\end{proof}

We may define the dimension of a projective subspace \(\Pi\) in \(\PG(n, q)\) as one less than the dimension of the associated vector space \(V\).
\begin{definition}
  The projective dimension of a subspace \(\Pi\) in \(\PG(n, q)\) is one less than the dimension of the associated vector space in \(V(n + 1, q)\).
\end{definition}

\begin{definition}\label{def:1}
  The projective span of \(k\) subspaces in \(PG(n, q)\), \(\langle \Pi_1, \Pi_2, \ldots, \Pi_k \rangle = \bigcap \{U  | U \subseteq V(n + 1, q) \land \Pi_1 + \Pi_2 + \cdots + \Pi_k \subseteq U \land U \text{is a vector subspace}\}\)
\end{definition}

Lemma~\ref{lemma:2} then gives us two immediate corollaries from Definition~\ref{def:1}.
\begin{corollary}\label{cor:1}
  Given two hyperplanes \(\Pi_1\) and \(\Pi_2\) in a finite projective space \(\PG(n, q)\), \(\dim(\langle \Pi_1, \Pi_2 \rangle) = \dim (\Pi_1) + \dim (\Pi_2) - \dim (\Pi_1 \cap \Pi_2)\).
\end{corollary}

\begin{corollary}
  In \(PG(2, q)\) two distinct lines \(L_1\) and \(L_2\) must always meet a point.
\end{corollary}
\begin{proof}
  Using Corollary~\ref{cor:1},

  \begin{equation*}
    \dim L_1 \cap L_2 = \dim L_1 + \dim L_2 - \dim (\langle L_1, L_2 \rangle) = 0
  \end{equation*}
  This relies on the fact that \(L_1 \neq L_2\), so that \(\dim (\langle L_1, L_2 \rangle) = 2\).
\end{proof}

When we start to work with latin squares and hypercubes we will not always have a field to work with, so it helps to define a notion of a projective space that is independent of the concept of a field. To do this we introduce the notion of an axiomatic projective plane (and later an axiomatic projective space of any dimension).

\begin{definition}
  A \textit{projective plane} is a set of points \(P\) and lines \(L \subset \mathcal{P}(P)\) such that the following axioms hold:

  \begin{enumerate}
    \item Given any pair of points \(x, y\) there exists a unique line \(l\) such that \(\{x, y\} \subseteq l\).\label{axiom:1}
    \item Given any pair of lines \(l_1, l_2\) we have \(l_1 \cap l_2 = \{x\}\), that is they intersect at a single point.\label{axiom:2}
    \item There exists four points, no three of which are collinear.\label{axiom:3}
  \end{enumerate}

  A projective plane is called finite if its point set is finite.
\end{definition}


The axioms we have defined give a remarkable amount of structure to our geometry.

\begin{lemma}\label{lemma:p-l-bijection}
  Given a line \(l\) and a point \(p \notin l\) in a finite projective plane, the number of lines through \(p\) is equal to the number of points on \(l\).
\end{lemma}
\begin{proof}
  Consider a line \(l\), and a point \(p \notin l\) in a finite projective plane. Given any point \(q \in l\) Axiom~\ref{axiom:1} gives us a line through \(p\) and \(q\), so the number of points on \(l\) is at most the number of lines through \(p\). On the other hand,
  any line through \(p\) must intersect \(l\) at a single point by Axiom~\ref{axiom:2}, so the number of points on \(l\) is at least the number of lines through \(p\). No two lines through \(p\) can intersect \(l\) at the same point without violating Axiom~\ref{axiom:2}. Therefore the number of lines through \(p\) is equal to the number of points on \(l\).
\end{proof}

\begin{corollary}~\label{cor:line-count}
  Given any two lines \(l_1, l_2\), \(|l_1| = |l_2| = n + 1\) for some positive integer \(n\).
\end{corollary}
\begin{proof}
  Consider a point \(p\) not on \(l_1\) and \(l_2\) (note that this may always be done due to Axiom~\ref{axiom:3}) and let \(L\) be the set of lines through \(p\). The set of points on \(l_{1}\) may be put in bijection with \(L\), so \(|l_{1}| = |L|\). The points on \(l_2\) may also be put in bijection with lines through \(p\) by Lemma~\ref{lemma:p-l-bijection},
  so \(|l_2| = |L| = |l_1| = n + 1\).
\end{proof}

\begin{corollary}
  If in a finite projective plane with point set \(P\) and line set \(L\) the number of points (lines) incident to a line (point) is \(n + 1\), then \(|P| = |L| = n^2 + n + 1\).
\end{corollary}
\begin{proof}\label{cor:p-count}
  Consider an arbitrary point \(p\) in the plane. There are \(n + 1\) lines through \(p\) and each of these lines has \(n\) points excluding \(p\). Other than at \(p\) the lines are disjoint, thus \(|P| = n(n + 1) + 1\).
  To see that \(|P| = |L|\) we can double count \(S = \{(p, l) | l \in L, p \in l\}\). By Corollary~\ref{cor:line-count} incident to each point \(p\) is \(n + 1\) lines, so \(|S| = (n + 1)|P|\), and incident to each line \(l\) is \(n + 1\) points, so \(|S| = (n + 1)|L|\). Therefore \((n + 1)|P| = (n + 1)|L|\) and \(|P| = |L| = n^2 + n + 1\).
\end{proof}

The \(n\) for which \(|P| = n^2 + n + 1\) is called the \textit{order} of the projective plane.
As support for later proofs we will want the following lemma,

\begin{definition}\label{definition:proj-order}
  A projective plane with \(n^{2} + n + 1\) points is a projective plane of order \(n\).
\end{definition}

\begin{lemma}\label{lemma:easy-proj}
  Let \(n \geq 2\). A set of \(n^{2} + n + 1\) points \(P\) and \(n^{2} + n + 1\) lines \(L\) such that,

  \begin{enumerate}
    \item Each line \(l \in L\) has \(n + 1\) points.
    \item Any pair of lines intersects at exactly one point.
    \item \(|P| = |L| = n^{2} + n + 1\)
  \end{enumerate}

  is a projective plane of order \(n\).
\end{lemma}

\begin{proof}
  Axiom~\ref{axiom:2} is already given, so we need only show Axiom~\ref{axiom:1} and Axiom~\ref{axiom:3}. Axiom~\ref{axiom:1} follows from the fact that because every pair of lines intersects at a unique point, every pair of points must be on at most one line. There are \(\binom{n^{2} + n + 1}{2}\) pairs of points in \(P\) and \((n^{2} + n + 1)\binom{n + 1}{2}\) pairs of points covered by lines in \(L\), and because \(\binom{n^{2} + n + 1}{2} = (n^{2} + n + 1)\binom{n + 1}{2}\) every pair of points must be on exactly one line.
  To show Axiom~\ref{axiom:3} consider two lines \(l\), \(m\) intersecting at a point \(u\). Because each line has \(n + 1 \geq 3\) points there are two points on \(l\), \(p\) and \(q\), and two points on \(m\), \(r\) and \(s\) that are not shared between \(l\) and \(m\) and are distinct from \(u\). No line can then contain any three of \(p, q, r, s\) without violating Axiom~\ref{axiom:1} or Axiom~\ref{axiom:2}.
\end{proof}

One question we still haven't answered is for what \(n\) is it possible to construct an axiomatic projective plane? This is an open problem with the following famous conjecture,

\begin{conjecture}[Prime Power Conjecture]
  The order of any finite projective plane is always \(n = p^k\), for some prime \(p\) and integer \(k \geq 1\).
\end{conjecture}

% \subsection{Duality}


% The axioms of the projective plane are self-dualising, that is if one exchanges the roles of points and lines in Axioms~\ref{axiom:1},~\ref{axiom:2} and~\ref{axiom:3} equivalent axioms will fall out. This duality can produce “dual theorems” that are sometimes useful, for instance the alternative proof
% that \(|P| = |L|\) in Corollary~\label{cor:p-count} would be to dualise the argument counting points and count the number of lines. Duality can be expressed more in a general projective space \(\PG(d,q)\) by exchanging the roles of points and hyperplanes, span with intersection and the phrases ``contianed in'' with ``containing''.
% For instance we have the following statement following from Corrolary \ref{cor:1}, the intersection of any two distinct hyperplanes in \(\PG(d, q)\) is a plane with co-dimension 2. The dual statement reads ``the span of any two distinct point in \(\PG(d, q)\) is a line''. We will use ideas of duality to help us work with some tricky hyperplanes.
\subsection{Affine Planes}

An axiomatic affine plane is more like the geometry taught in schools, where lines may be parallel to each other. Here we formally define the notion of parallelism and explore affine planes in relation to projective planes.

\begin{definition}

  An affine plane is a set of points \(P\) and lines \(L \subset \mathcal{P}(P)\) such that the folloming axioms hold:

  \begin{enumerate}
    \item Every two points are incident with a unique line.~\label{axiom:aff-1}
    \item Given a line \(l\) and a point \(p \notin l\), there exists a unique line \(m\) through \(p\) such that \(m \cap l = \emptyset\).~\label{axiom:aff-2}
    \item There are three points that are not collinear.~\label{axiom:aff-3}
  \end{enumerate}
\end{definition}

We call two lines \(l\) and \(m\) satisfying \(m \cap l = \emptyset\) or \(l = m\) “parallel”, and we can show that the natural relationship induced by parallelism is an equivalence relation.

\begin{lemma}\label{lemma:parallel}
  For any pair of lines \(l, m\) in an affine plane, let \(l \sim m\) if and only if \(l\) and \(m\) are parallel, then \(\sim\) is an equivalence relation.
\end{lemma}
\begin{proof}
  From the definition of parallelism \(\sim\) is clearly reflexive and symmetric. To see that the transitivity property holds, suppose we have a line \(m\) and two lines \(l, l^{\prime}\) distinct from \(m\), such the \(l\) is parallel to \(m\) and \(m\) is parallel to \(l^{\prime}\) but there exists \(p \in l \cap l^{\prime}\).
  It then follows that because \(m\) is parallel to both \(l\) and \(l^{\prime}\) that \(p \notin m\), Axiom~\ref{axiom:aff-2} says there should be a unique line parallel to \(m\) through \(p\), and therefore \(l = l^{\prime}\). Thus if \(l\) is parallel to \(m\) and \(m\) is parallel to \(l^{\prime}\) then \(l\) is parallel to \(l^{\prime}\).
\end{proof}

Because parallelism forms an equivalence relation we can partition the set of lines into parallel classes, which aree the equivalence classes of \(\sim\).

\begin{lemma}\label{lemma:parallelclasses}
  Let \(P_{1}\) and \(P_{2}\) be the parallel classes of two lines \(l_{1}\) and \(l_{2}\) that are not parallel, then \(|P_{1}| = |P_{2}|\).
\end{lemma}
\begin{proof}
  Begin by picking a point \(p\) on \(l_{1} \setminus l_{2}\) and \(q\) on \(l_{2} \setminus l_{1}\). The line \(m\) through \(p\) and \(q\) intersects \(l_{1}\) and \(l_{2}\) and is thus in neither parallel class. For each point on \(m \setminus \{p\}\) a there is a unique line passing through \(p\) parallel to \(l_{1}\), each line parallel to \(l_{1}\) must intersect \(m\)
  (and these no intersection point may be shared by two parallel lines), so it follows that \(|m| = |P_{1}|\). Similar logic follows for lines through \(P_{2}\) and \(m\) so that \(|P_{2}| = |m|\). Thus \(|P_{1}| = |m| = |P_{2}|\).
\end{proof}

We can use Lemma~\ref{lemma:parallelclasses} to define a notion of order similar to Definition~\ref{definition:proj-order} for Projective Planes.

\begin{definition}\label{definition:affine-order}
An affine plane with a parallel class \(P\) of size \(n\) is an affine plane of order \(n\). By Lemma~\ref{lemma:parallelclasses} the order of an affine plane is well defined.
\end{definition}

\begin{lemma}\label{lemma:affine-lines}
  In an affine plane of order \(n\), every line has \(n\) points.
\end{lemma}
\begin{proof}
  Following our prior logic in Lemma~\ref{lemma:parallelclasses}, if we pick a line \(l\) and another line \(m\) such that \(m\) is not parallel to \(l\) we may put the points of \(l\) in one to one correspondence with lines in the parallel class of \(m\) so that \(|l| = n\).
\end{proof}

\begin{lemma}\label{lemma:affine-points}
  An affine plane of order \(n\) has \(n^{2}\) points.
\end{lemma}
\begin{proof}
  Pick a line \(l\) and it's parallel class \(P\). For any point \(p\) there is a unique line \(m\) parallel to \(l\) through \(p\). At the same time \(l_{1} \cap l_{2} = \emptyset\) for any pair of distinct lines \(l_{1}\) and \(l_{2}\) in \(P\). Therefore the lines of \(P\) partition the point set of the affine plane.
  By Lemma~\ref{lemma:affine-lines} it therefore follows that there are \(n^{2}\) points in the affine plane.
\end{proof}

\begin{lemma}
  An affine plane of order \(n\) has \(n(n + 1)\) lines.
\end{lemma}

\begin{proof}
  Picking any two distinct points \(p\) and \(q\) we can construct a unique line containing both \(p\) and \(q\), and for any line we pick any pair of points that determine the same line. Therefore there are

  \begin{equation*}
    \frac{\binom{n^{2}}{2}}{\binom{n}{2}} = n(n + 1)
  \end{equation*}

  distinct lines in an the affine plane of order \(n\), using Lemma~\ref{lemma:affine-lines} and Lemma~\ref{affine-points}.
\end{proof}

\begin{lemma}
  In an affine plane of order \(n\) every point has \(n + 1\) lines incident with it.
\end{lemma}
\begin{proof}
  Fix a point \(p\) in the plane. Picking one of the \(n^{2} - 1\) points besides \(p\), say \(q\), will determine a line through \(p\). For each pair \((p, q)\) spanning a line \(l\), \(n - 1\) other choices for \(q\) span the same line, so the number of lines through \(p\) is

  \begin{equation}
    \frac{n^{2} - 1}{n - 1} = n + 1.
  \end{equation}
\end{proof}

The relationship between projective planes and affine planes is predictably close, in fact the existence of an affine plane is equivalent to the existence of a projective plane.

\begin{theorem}
  The existence of an affine plane of order \(n\) is equivalent to the existence of a projective plane of order \(n\).
\end{theorem}
\begin{proof}
  Assume we have an affine plane of order \(n\) with points \(P\) and lines
\(L\). Partition the set of lines in the plane \(L\) into parallel classes
\(P_{1}, P_{2}, \ldots, P_{n + 1}\). Add \(n + 1\) points
\(E_{1}, E_{2}, \ldots, E_{n + 1}\) to \(P\) representing each parallel class and add
a line \(L_{\infty} = \{E_{i} | 1 \le i \le n + 1\}\) to \(L\). Then for each line
\(l \in L\) we will add the point \(E_{i}\) to \(l\) where \(E_{i}\) represents
the parallel class \(P_{i}\) that \(l\) belongs to. We now have
\(n^{2} + n + 1\) points, and \(n^{2} + n + 1\) lines with the property that any
pair of lines intersects at exactly one point. Each pair of nonparallel lines in the
affine plane will still intersect at a single point and every pair of parallel lines will
now intersect at \(l_{\infty}\) as they belong to the same parallel class, every line by definition will intersect \(l_{\infty}\) at it's parallel class. From
Lemma~\ref{lemma:easy-proj} this implies our points and lines form a projective
plane of order \(n\).

  Now assume we are given a projective plane of order \(n\) with points \(P\)
and lines \(L\). Pick any line \(l \in L\) and let
\(L^{\prime} = \{l^{\prime} \setminus l | l^{\prime} \in L \setminus \{l\}\}\) and \(P^{\prime} = P \setminus \{l\}\). We will now
show \(P^{\prime}\) and \(L^{\prime}\) forms an affine plane of order \(n\). The lines in
\(L^{\prime}\) may be partitioned into classes \(\{P_{1}, P_{2}, \ldots, P_{n + 1}\}\),
one class for each point \(p \in l\) containing each of the \(n\) lines apart from
\(l\) incident to \(p\) in the projective plane. Because each pair of lines in a
projective plane intersects at one point the lines in \(P_{i}\) must be parallel
(having removed their intersection on \(l\)), and moreover as the lines have
\(n\) points each and \(|P_{i}| = n\) they partition the points and satisfy
Axiom~\ref{axiom:aff-2} of an affine plane. Lines from distinct parallel classes
must intersect at a unique point in \(P^{\prime}\) as they intersected at a unique
point not on \(l\) in the projective plane. Any pair of points in \(P^{\prime}\) will
still have a line through both as they did in the projective plane. A set of
three points that are not collinear may be obtained by taking two points on a
given line \(m \in L^{\prime}\) and a single point not on \(m\), these points cannot be
collinear. Thus \((P^{\prime}, L^{\prime})\) forms an affine plane of order \(n\).
\end{proof}

\subsection{\(k\)-nets of order \(n\)}


\begin{definition}\label{def:net}
  A net of degree \(k \geq 2\) and order \(n\) (hereafter a \(k\)-net of order \(n\)) is a set of \(n^2\) points and \(k\) parallel classes such that each parallel class consists of \(n\)
  disjoint lines of size \(n\) and such that lines of distinct parallel classes meet in a unique point.
\end{definition}

\(k\)-Nets can be thought of as a generalisation of the incidence properties of an affine plane, indeed the following lemma establishes that affine planes are a special case of \(k\)-nets of order \(n\).

\begin{lemma}
  An \((n + 1)\)-net of order \(n \geq 2\) is an affine plane of order \(n\).
\end{lemma}

\begin{proof}
  Suppose we have an \((n + 1)\)-net of order \(n\), we will show that the axioms for an affine plane follow from those of the net.
  Axiom~\ref{axiom:aff-1} directly follows from the definition of a net, as every pair of lines is either parallel or intersecting in a single point. The next axiom,~\ref{axiom:aff-2}, follows from the fact that because the parallel classes partition the plane,
  given a line \(l\) identifying a parallel class and a point \(p\) not on that line there is a single line in the parallel class through \(p\). The third axiom, Axiom~\ref{axiom:aff-3} follows from the fact that if \(n \geq 2\) one can identify 3 points, two on one line \(l\), and a third not on \(l\), these points cannot be collinear.
\end{proof}

Because each parallel class partitions the point set every point in a \(k\)-net of order \(n\) is incident to \(k\) lines, one from each parallel class.

One remarkable property of a \(n\)-net of order \(n\) is that it may be extended uniquely to an affine plane. This will be used later to show some interesting theorems about mutually orthogonal latin squares.

\begin{lemma}\label{lemma:net-extension}
  An \(n\)-net of order \(n\) can be extended in a unique way to an \((n + 1)\)-net of order \(n\).
\end{lemma}

\begin{proof}
  Suppose we have an \(n\)-net of order \(n\), \(N\), we will define a set of
\(n\) new lines that, together with \(N\), will form the \((n + 1)\)-net of order \(n\), \(N^{\prime}\).
Pick a point \(p_{1}\) from among the set of \(n^{2}\) points in \(N\), and
define the line \(l_{1}\) to be set of \(n + 1\) points not collinear with \(p_{1}\). The next line \(l_{2}\) will be constructed by picking
\(p_{2} \notin l_{1}\) and taking the set of points not collinear to \(p_{2}\), and
so on to get a set of \(n\) lines and points
\(p_{1}, l_{1}, p_{2}, l_{2}, \ldots, p_{n}, l_{n}\). To see that the lines are
disjoint we are going to show that the relationship ``\(p \parallel q \iff p = q \text{\,
or\,} p \text{\,and} q \text{\,are not collinear in \,} N\)'' is an equivalence relation.
Reflexivity and symmetry are clear so it just remains to show that the
relationship \(\parallel\) is transitive. Suppose we have three distinct points
\(p, q, r\) such that \(p \parallel q\), \(q \parallel r\), but \(p\) and \(r\) are collinear.
The net axioms guarantee exactly one line through \(q\) that is parallel to
\(pr\). The remaining \(n - 1\) lines through \(q\) must intersect the line
\(pr\) in one of \(n\) points on \(pr\) except \(p\) and \(r\) since \(q\) is on
a line with neither. However by the pigeonhole principle we conclude that two
lines through \(q\) must intersect at the same point on the line \(pr\), a
contradicton since every pair of points in a net can have at most one line
through them. As the relation \(\parallel\) is reflexive, symmetric and transitive, it
is by definition an equivalence relation. The lines \(l_{1}, l_{2}, \ldots, l_{n}\)
are the equivalence classes of \(\parallel\) and therefore are pairwise disjoint. Now
consider a line \(m\) in the original \(n\)-net \(N\). Each of the \(n\) points
on \(m\) must lie on exactly one of the lines \(l_{1}, l_{2}, \ldots, l_{n}\), and no
pair of points may lie on a line as they are collinear on \(m\). It therefore
follows that there is a bijection between the \(n\) points on \(m\) and the
lines \(l_{1}, l_{2}, \ldots, l_{n}\) and so each line \(l_{i}\) intersects each line
in the net \(N\) exactly once. So the net \(N^{\prime}\), defined by adding the lines
\(l_{1}, l_{2}, \ldots, l_{n}\) to \(N\), is an \((n + 1)\)-net of order \(n\).
\end{proof}
\section{Projective Spaces and Orthogonal Hypercubes}


\begin{definition}
  A latin square of order \(n\) is an \(n \times n\) array, where each entry in the array is assigned one of \(n\) symbols such that every symbol appears exactly once in each row and each column.
\end{definition}

Given two latin squares we say they are \textit{orthogonal} if when superimposing the first square over the second each of the \(n^2\) possible ordered pair of symbols appears exactly once.
A set of \(M \geq 2\) of latin squares is \textit{mutually orthogonal} it is pairwise orthogonal, this is often abbreviated to a set of MOLS of order \(n\). Lemma~\label{mols-bound} answers the quesiton ``What is the largest set of mutually orthogonal latin squares of a given order?''

\begin{lemma}\label{lemma:mols-bound}
  Let \(M\) be a set of mutually orthogonal latin squares of order \(n \geq 2\), then \(|M| \leq n - 1\).
\end{lemma}
\begin{proof}
  Let \(M = \{A^i\}\) be a set of mutually orthogonal latin squares \(A^i, 1 \leq i \leq |M|\) of order \(n \geq 2\). Without loss of generality we may assume that the first row of each latin square is given by \(1, 2, 3, \ldots n\), because we may permute symbols to make this so if it isn't already for any given latin square without affecting orthogonality.
  We will now count the multi-set \(N = \{A^1_{21}, A^2_{21}, \ldots, A^{|M|}_{21}\}\). Because the symbol above \(A^i_{21}\) is fixed to one \(A^i_{21} \in {2, 3, \ldots, n}\) for each \(i\), and moreover because \((A^i_{1k}, A^j_{1k}) = (k, k)\) for each \(1 \leq i, j \leq |M|, 1 \leq k \leq n\) we cannot have \(A^i_{21} = A^j_{21}\) for any \(1 \leq i, j \leq |M|\).
  It therefore follows that \(N\) is a subset of \({2, 3, \ldots, n}\) and \(|M| = |N| \leq n - 1\).
\end{proof}

We call a set of \(M = n - 1\) mutually orthogonal latin squares of order \(n\) a \textit{complete set}.

\begin{theorem}~\label{thm:mols}
  A set of \(n - 1\) mutually orthogonal latin squares of order \(n\) always exists if n is a prime power.
\end{theorem}
\begin{proof}
  Consider \(PG(2, n)\), which always exists for prime powers, and the line at infinity \(L_{\infty}\). Distinguish two of the \(n + 1\) points on this line as \(r\) and \(c\) respectively.
  We will call the \(n\) lines through \(r\) (excluding the line at infinity) our row lines, and the \(n\) lines through \(c\) our column lines, generically these lines are referred to as coordinate lines. Denote the row lines \(r = \{r_{1}, r_{2}, \ldots, r_{n}\}\) and coordinate lines \(c = \{c_{1}, c_{2}, \ldots, c_{n}\}\) respectively.
  Each point can be uniquely determined by the intersection of a row line and a column line, so we may coordinatise the entries of a latin square according to intersections of coordinate lines.
  The remaining \(n - 1\) points on the line at infinity each have \(n\) lines through them (excluding the line at infinity) and these lines we will refer to as symbol lines. Each of the \(n - 1\) points will be used to define a latin square. Fix a point in \(L_{\infty} - \{r, c\}\) and call it \(L_i\). There are \(n\) lines through \(L_{i}\) excluding \(L_{\infty}\), \(S_{1}^{i}, S_{2}^{i}, \ldots, S^{i}_{n}\).
  The latin square \(A^{i}\) will be constructed by letting \(A^{i}_{x,y} = j\) if and only if the intersection point of \(r_{x}\) and \(c_{y}\) lies on \(S^{i}_{j}\). Because each symbol line intersects each coordinate line only once, and any pair of row (column) lines cannot intersect in the affine plane, each row and column has exactly one of each symbol.
  Taking the set of \(n - 1\) latin squares defined in this fashion we need only show orthogonality. Given two symbol lines \(S_i\) and \(S_j\) from two different latin squares we know that these intersect at a single point which cannot be in the line at infinity.
  Where the symbol lines intersect is therefore the only place where \((i, j)\) appears upon superimposing the two latin squares and so the set of \(n - 1\) latin squares we have defined is mutually orthogonal.
\end{proof}


Theorem~\ref{thm:mols} may seem redundant in light of what follows in Theorem~\ref{thm:mols-to-net}, however the logic in the proof of Theorem~\ref{thm:mols} is crucial to understanding the setup for Theorem~\ref{thm:general-ortho-proof} later on so keep this slightly repititive thinking in mind.
Theorem~\ref{thm:mols-to-net} seeks to find a constructive equivalence between a net and a set of MOLS.

\begin{theorem}\label{thm:mols-to-net}
  The existence of \(k\) mutually orthogonal latin squares of order \(n\) is equivalent to the existence of a \((k + 2)\)-net of order \(n\).
\end{theorem}
\begin{proof}

  Suppose we have a set \(M = \{A^{1}, A^{2}, \ldots, A^{k}\}\) of \(k\) MOLS of order \(n\). Let \(\mathcal{P} = \mathbb{Z}_{n}^{2}\) be a set of
\(n^{2}\) points. To define a \((k + 2)\)-net of order \(n\) we will define
\(k + 2\) parallel classes of lines with points in \(\mathcal{P}\). The rows and columns,
\(r_{i} = \{(i, y) | y \in \mathbb{Z}_{n}\}\) and
\(c_{j} = \{(x, j) | x \in \mathbb{Z}_{n}\}\), form the first two parallel classes
\(R\) and \(C\) respectively. For each latin square \(A^{i} \in M\) we let
\(P_{i} = \{l_{1}^{i}, l_{2}^{i}, \ldots, l_{n}^{i}\}\) be the parallel class
defined by \((x, y) \in l_{j}^{i}\) if and only if \(A^{i}_{x, y} = j\).
Clearly each pair of lines \((r, c) \in R \times C\) intersect at exactly one point.
Because no position in \(A^{i}\) is assigned twice the lines in \(P_{i}\) are
indeed parallel. Because each symbol \(j\) appears once in \(A^{i}\) for each
row and column it follows that each line in \(P_{i}\) has \(n\) points and
intersects each line in \(R\) and \(C\) just once. Let \(l_{j} \in P_{i}\) and \(l_{k} \in P_{l}\) for some \(i \ne l\), because \(A^{i}\) and \(A^{l}\) are orthogonal there is exactly one point \((x_{0}, y_{0})\) such that \(A^{i}_{x_{0}, y_{0}} = j\) and \(A^{l}_{x_{0}, y_{0}} = k\), so the lines \(l_{j}\) and \(l_{k}\) meet at exactly one point.
So we have a set of \(k + 2\) parallel classes
of \(n\) lines containing \(n\) points meeting Definition~\ref{def:net} and hence the points \(\mathcal{P}\) and defined in \(P\) form a \((k + 2)\)-net of order \(n\).

  Starting from a \((k + 2)\)-net of order \(n\) with points \(\mathcal{P}\) and lines \(L\), pick two distinct parallel
classes \(R = \{r_{1}, r_{2}, \ldots, r_{n}\}\) and
\(C = \{c_{1}, c_{2}, \ldots, c_{n}\}\). To coordinatise the points, let \(\varphi : \mathbb{Z}_{n}^{2} \to \mathcal{P}\) be the function defined by
\(\varphi(x, y) = p\) if and only \(r_{x} \cap c_{y} = \{p\}\). To see that \(\varphi\) is one
to one, suppose \(\varphi(x, y) = \varphi(x^{\prime}, y^{\prime})\) and WLOG assume \(x \neq x^{\prime}\) (the
case \(y \neq y^{\prime}\) is identical), then
\(r_{x} \cap c_{y} = r_{x^{\prime}} \cap c_{y^{\prime}} = \{p\}\) which implies
\(r_{x} \cap r_{x^{\prime}} \neq \emptyset\), this is a contradiction as we know these lines are
parallel. Because \(|\mathbb{Z}_{n}^{2}| = |\mathcal{P}| = n^{2}\) and \(\varphi\) is one to one
we may also conclude \(\varphi\) is onto and bijective. From the remaining \(k\) parallel classes besides \(R\) and \(C\)
\(\{P_{1}, P_{2}, \ldots, P_{k}\}\), we will define a set \(M\) of \(k\) MOLS of order
\(n\), \(M = \{A^{1}, A^{2}, \ldots, A^{k}\}\). For each of the \(n\) lines in
\(P_{i}\), \(\{l_{1}, l_{2}, \ldots, l_{n}\}\), define \(A^{i}_{x,y} = j\) if and only
\(\varphi(x, y) \in l_{j}\). Because two lines from distinct parallel classes intersect
at a unique point, it follows that \(A^{i}\) is a latin square as each line from
\(P_{i}\) intersect each line in \(R\) and \(C\) exactly once. A pair of distinct latin square \(A^{i}\) and \(A^{l}\) defined in this manner are also orthogonal, because two lines \(l_{j} \in P_{i}\) and \(l_{k} \in P_{l}\) intersect at exactly one point \(p\), and so \(A^{i}_{x, y} = k\) and \(A^{l}_{x, y} = l\) intersect at exactly one point \((x, y) = \varphi^{-1}(p)\).
It follows then that \(M\) is a set of \(k\) mutually orthogonal latin squares.
\end{proof}
\begin{corollary}
  The existence of a set of \(n - 1\) MOLS of order \(n\) is equivalent to the existence of an affine plane of order \(n\).
\end{corollary}
\begin{corollary}\label{cor:proj-MOLS}
  The existence of a set of \(n - 1\) MOLS of order \(n\) is equivalent to the existence of a projective plane of order \(n\).
\end{corollary}

One can also extend a set of \(n - 2\) MOLS of order \(n\) to a set of \(n - 1\) MOLS of order \(n\).

\begin{theorem}~\label{thm:mols-extension}
  A set of \(n - 2\) MOLS of order \(n\) may be extended to a set of \(n - 1\) MOLS of order \(n\).
\end{theorem}

\begin{proof}
  Assume we have a set of \(n - 2\) MOLS of order \(n\), \(M = \{A^{1}, A^{2}, \ldots, A^{n - 2}\}\). Using Theorem~\ref{thm:mols-to-net} we may take \(M\) and construct a \(n\)-net, and then using Lemma~\ref{lemma:net-extension} obtain a \((n + 1)\)-net of order \(n\). Then by Corollary~\ref{cor:proj-MOLS} and Theorem~\ref{thm:mols} we can construct a set of \(n - 1\) MOLS, \(n - 2\) will be the original MOLS in \(M\) and the last coming from the extension in Lemma~\ref{lemma:net-extension}.
\end{proof}


We will attempt to generalise some of our results to latin squares in higher dimensions, but first we need some definitions of what that even means.
\begin{definition}\label{def:hypercube}
  A (d, n, r, t)-hypercube of dimension \(d\), order \(n\), class \(r\) and type \(t\) is an \(n \times n \times \cdots \times n\) (\(d\) times) array on \(n^r\) distinct symbols such that in every t-subarray (that is, fix \(t\) coordinates and allow the remaining \(d - t\) coordinates to vary) each of the \(n^r\)
  distinct symbols appears exactly \(n^{d - t - r}\) times.
  Moreover, if \(d \geq 2r\) two such hypercubes are \textit{orthogonal} if when superimposed each of the \(n^{2r}\) possible distinct pairs appears exactly \(n^{d - 2r}\) times. A set of hypercubes is mutually orthogonal if each pair of hypercubes in the set are orthogonal.
\end{definition}

The familiar latin square is a \((2, n, 1, 0)\)-hypercube. We will be interested in extending the classic result given in Theorem~\ref{thm:mols}, to do this we require a
theorem that bounds the size of a mutually orthogonal set of hypercubes of dimension \(d\), order \(n\), type \(t\) and class \(r\). In~\cite{ETHIER2012430} we have the following theorem bounding sets of MOHC:

\begin{theorem}~\label{thm:mut-ortho}\cite[Theorem 2.4]{ETHIER2012430}
  The maximum number of mutually orthogonal hypercubes (MOHC) of dimension \(d\), order \(n\), type \(t\) and class \(r\) is bounded above by

  \begin{equation}
    \frac{1}{n^r - 1}\left(n^d - 1 - \binom{d}{1}(n - 1) - \binom{d}{2}{(n - 1)}^2 - \cdots - \binom{d}{t} {(n - 1)}^t\right). \label{eq:ortho-bound}
  \end{equation}

\end{theorem}

A complete set of mutually orthogonal \((d,n,r,t)\)-hypercubes is a set of MOHC attaining the bound in Theorem~\ref{thm:mut-ortho}. The following theorem is a generalisation of Theorem~\ref{thm:mols} to arbitrary dimensions.

\begin{theorem}\label{thm:general-ortho-proof}
  Let \(q\) be a prime power, then there exists a complete set of mutually orthogonal \((d, q, 1, d - 1)\)-hypercubes.
\end{theorem}

\begin{proof}
  Let \(q\) be a prime power, and let \(X = \{e_{1}, e_{2}, \ldots, e_{d}\}\) where \(e_{i} = (0, 0, \ldots, 1, 0, \ldots, 0)_{q}\) is a point in \(\PG(d, q)\) whose homogeneous coordinates have a 1 in the \(i\)th position and zero everywhere else. Define \(H_{\infty}\) to be the hyperplane at infinity in \(\PG(d, q)\).
  By removing some \(e_i \in X\) from \(X\) we get a subset \(S\) of \(d - 1\) points in \(X\) that spans a codimension 2 space contained in \(H_{\infty}\). Furthermore there are \(q\) hyperplanes through \(S\) apart from \(H_{\infty}\). These planes are defined by the equations \(x_i X_i + X_{d + 1}\) and \(X_{i} = 0\).
  The \(q\) hyperplanes through the projective span of some subset \(S\) of \(X\) we will call coordinate hyperplanes. Let \(D\) be a set of \(d\) coordinate hyperplanes through the projective span of \(d\) codimension 2 spaces with basis \(X \setminus \{e_{i}\}\) for each \(i \in \{1, 2, \ldots, d\}\). To show that these hyperplanes intersect at a single affine point construct the homogoneous system of linear equations \(A \mathbf{x} = \mathbf{0}\) where,

  \begin{equation*}
    A = \begin{bmatrix}
      x_1 & 0 & \ldots & 0 & 0 & \alpha_1 \\
      0 & x_2 & \ldots & 0 & 0 & \alpha_2 \\
      \ldots \\
      0 & 0 & \ldots & 0 & x_d & \alpha_d
    \end{bmatrix}
  \end{equation*}

  Where \(\alpha_l = 0\) if the hyperplane it describes is defined by the equation \(X_l = 0\) and \(\alpha_l = 1\) otherwise.
  This matrix has rank \(d\) and hence \(A \mathbf{x} = \mathbf{0}\) a single projective point as a solution, namely \((\alpha_1 x_1, \alpha_2 x_2, \ldots, \alpha_d x_d, 1)\), and this proves the claim that the intersection of the hyperplanes in \(D\) is a single affine point in \(\PG(d, q)\). We will now coordinatise the points of the affine space in terms of
  the intersection of coordinate hyperplanes through the \(d\) codimension 2 spaces with basis \(X \setminus \{e_{i}\}\) for each \(i \in \{1, 2, \ldots, d\}\).
  Our analogue to symbol planes in Theorem~\ref{thm:mut-ortho} will be symbol hyperplanes whose intersection with the hyperplane at infinity does not include \(X\). Let \(H\) be the set of codimension 2 spaces in \(H_{\infty}\) not containing \(X\).
  These hyperplanes are described by systems of equations \(X_{d + 1} = 0\) and \(c_{1}X_{1} + c_{2} X_{2} + \cdots + c_{d}X_{d} = 0\) with each \(c_{i} \ne 0\), and hence there are \(\frac{(q - 1)^{d}}{q - 1} = (q - 1)^{d - 1}\) hyperplanes in \(H_{\infty}\) not intersecting \(X\) at any point.

  Let \(\mathcal{H} = \{H^{1}, H^{2}, \ldots, H^{{(q - 1)}^{d - 1}}\}\) be a set of \(q \times q \times \cdots \times q\) (\(d\) times) arrays. To define \(\mathcal{H}^{i}\) one considers all \(q\) hyperplanes \(S_{1}, S_{2}, \ldots, S_{n}\) through some codimension 2 space in the set \(H\) and let \(\mathcal{H}^{i}_{(x_{1}, x_{2}, \ldots, x_{d})} = j\) if and only if \((x_{1}, x_{2}, \ldots, x_{d}, 1) \in S_{j}\).
  We must show that these arrays are a complete set of MOHC.
  Taking any hyperplane through any of the planes in \(\mathcal{H}\) gives us a hyperplane of the form \(c_1X_1 + c_2X_2 + \ldots + c_d X_d + c_{d + 1}X_{d + 1} = 0\), with each \(c_i\) non-zero (to avoid including one of the basis vectors).
  We can now consider its intersection with \(d - 1\) coordinate planes (describing a \((d - 1)\)-subarray), and WLOG assume that these planes are of the form \(x_i X_i + X_{d + 1}\) for each \(1 \leq i \leq d - 1\). Their intersection is the homogenous solution to the following,

  \begin{equation*}
    A = \begin{bmatrix}
      x_1 & 0 & \ldots & 0 & 0 & 1 \\
      0 & x_2 & \ldots & 0 & 0 & 1 \\
      \ldots \\
      0 & 0 & \ldots & x_{d - 1} & 0 & 1 \\
      c_1 & c_2 & \ldots & c_{d - 1} & c_d & c_{d + 1}
    \end{bmatrix}
  \end{equation*}

  This system has rank at least \(d - 1\) and at most \(d\) so the solution space is either a point or a line. If the solution space is a line, or point at infinity we may add the restriction \(X_{d + 1} = 0\) and obtain,
  \(X_1 = X_2 = \ldots = X_{d - 1} = 0\) and plugging this into our last equation get \(c_d X_d = 0\). Because \(c_d \neq 0\) we have \(X_d = 0\) and the solution \((0, 0, \ldots, 0)\) --- a contradiction. Thus the solution must be an affine point and thus that any 1-subarray in a cube \(H^{i}\) will contain each of the \(q\) symbols exactly once, and hence that \(H^{i}\) is a hypercube.
  Picking two symbol hyperplanes from two distinct hypercubes \(H_{i}\) and \(H_{j}\) their intersection is a \((d - 2)\)-dimensional space with \(\sum_i^{d - 2} q^{i} - \sum_i^{d - 3} q^{i} = q^{d - 2}\) affine points, so \(H_{i}\) and \(H_{j}\) are orthogonal.

  By Theorem~\ref{thm:mut-ortho}, the maximum number of mutually orthogonal \((d, q, 1, d - 1)\)-hypercubes is \((q - 1)^{d - 1}\), so \(\mathcal{H}\) is a complete set of mutually orthogonal \((d, n, 1, d - 1)\)-hypercubes.
\end{proof}


Theorem~\ref{thm:general-ortho-proof} has been proven elsewhere in literature, notably in~\cite{MR1644242} (albeit a slight generalisation is given there). Mullen and Laywine use polynomials of the form \(f_{a_1, a_2, \ldots, a_d}(x_1, x_2, \ldots, x_d) = a_1x_1 + a_2x_2 + \ldots a_d x_d\), with at least two \(a_i\) nonzero, to define a complete set of mutually orthogonal \((d, n, 1, 0)\)-hypercubes.
The polynomials for which all \(a_i\) is nonzero are precisely the hyperplanes not through \(X\) given in Theorem~\ref{thm:general-ortho-proof}. The remaining polynomials correspond to hyperplanes that intersect with one or more of the basis points in \(X\). Whilst this proof was found indepedently of Laywine and Mullen,
we have shown it is the same as what they end up with.

It would be nice if, like in the two dimensional case, the existence of a complete set of \((d,n,r,0)\)-hypercubes implied the existence of a projective space \(\PG(d, n)\), 
however~\cite{MR1904388} suggests that without further restrictions of the hypercubes chosen we cannot construct the right geometry.

\section{Mutually Orthogonal Soduku}

Soduku are a special case of latin squares, an object we have already discussed. A soduku of order \(n^{2}\) is a latin square of order \(n^{2}\)  with the property that each \(n \times n\) subsquare has each symbol exactly once.
Because soduku are latin squares the definition of orthogonality for latin squares is equally valid for soduku. However soduku differ from latin squares in terms of how many orthogonal soduku one can have, as the following lemma demonstrates.

\begin{lemma}\label{lemma:orth-soduku}
If \(M\) is a set of \(k\) mutually orthogonal soduku latin squares (MOSLS) of order \(n^{2}\), then \(k \leq n^{2} - n\)
\end{lemma}

\begin{proof}
Suppose we have a set \(M = \{S^{1}, S^{2}, \ldots S^{k}\}\) of \(k\) soduku of order n, and WLOG assume that the first row of symbols in each soduku in \(M\) are such that the first row is given by \(1, 2, \ldots, n^{2}\). Now consider how many possible symbols we may pick for the entry (2, 1) of each soduku. For each soduku we have a choice of one of \(q^{2}\) symbols, of which \(1, 2, \ldots n\) are forbidden as they are in the first subsquare of the soduku. If for some \(i \ne j\) we have \(S^{i}_{2, 1} = k =  S^{j}_{2, 1}\) then \(S^{i}\) and \(S^{j}\) are not orthogonal because \(S^{i}_{1, k} = k = S^{j}_{1, k}\) so no \(k \leq q^{2} - q\).
\end{proof}

As we saw in Theorem~\ref{thm:mols-extension} it is always possible to extend a set of \(n - 2\) MOLS of order \(n\) to a set of \(n - 1\) MOLS of order \(n\). The natural extension of Theorem~\ref{mols-extension} would be something like the following,

\begin{conjecture}~\label{conj:mosls-ortho}
For \(n \geq 2\), if there exists a set \(M\) of \(n^{2} - n - 1\) MOSLS of order \(n^{2}\), then there exists an extension of \(M\) to a complete set of \(n^{2} - n\) MOSLS of order \(n^{2}\)
\end{conjecture}

However Conjecture~\ref{conj:mosls-ortho} is not true, and in fact it's not even true for the nicest cases (the prime powers). In~\cite{Dhaeseleer2017}, Theorem~\ref{thm:mosls-extension} was shown with a constructive proof.

\begin{theorem}~\label{thm:mosls-extension}
Let \(q > 3\) be a prime power, then there exists a maximal set of \(q^{2} - q - 1\) MOSLS of order \(q^{2}\).
\end{theorem}

The proof of this makes use of a correspondence between a soduku latin square of
order \(q^{2}\) for prime powers \(q\) and the projective space \(\PG (4, q)\).
The \(q^{2} \times q^{2}\) array \(A = (a_{ij})\) is coordinatised by identifying the
position \((i, j)\) in \(A\) with the projective point with homogeneous
coordinates \((1, a, b, c, d)_{q}\), where \(1 \leq a, b, c, d \leq q\) are integers
(mapped to \(\mathbb{F}_{q}\)) such that \(i = (a - 1)q + b\) and
\(j = (c - 1)q + d\). In this way each affine point of \(\PG (4, q)\)
corresponds to a unique position in \(A\). Soduku latin squares of the
\textit{parallel type} are defined by taking a line \(l\) in \(H_{\infty}\) skew to
three chosen lines, \(R : x_{0} = x_{1} = x_{2} = 0\),
\(C : x_{0} = x_{3} = x_{4} = 0\) and \(S : x_{0} = x_{1} = x_{3} = 0\) and
assigning each of the \(q^{2}\) symbols to the positions corresponding to each
of the affine points on each of the \(q^{2}\) planes through the line \(l\). In~\cite{Dhaeseleer2017} this was shown to always give a soduku latin square. Orthogonal sets
of parallel soduku correspond to sets of skew lines in \(H_{\infty}\). So to find a maximal
set of \(q^{2} - q - 1\) MOSLS of order \(q^{2}\), we actually find a maximal
partial spread of \(q^{2} - q - 1\) lines skew to \(R\), \(C\) and \(S\). We then need to check that there are no other extensions possible that are not parallel.

Finding the correct partial spread turns out to be a complicated endeavour, but
using GAP~\cite{GAP4} soduku were constructed that meet the criteria laid out
in~\cite{Dhaeseleer2017}. In Figure~\ref{fig:soduku} five soduku of order \(q^{2} = 9\) are constructed using the techniques outlined in~\cite{Dhaeseleer2017}.

To verify that the set of mutually orthogonal soduku in Figure~\ref{fig:soduku}
are not extendable, a constraint satisfaction problem solver was employed.
Constraint satisfaction problem solvers take in a set of constraint on a defined
set of variables and attempts to find any assignments to the set of variables
that satisfy all the given constraints. In this case, the set of variables are
the positions of the final soduku, and the constraints are the soduku latin
square constraints plus all the orthogonality constraints implied by the other
soduku latin squares. The particular solver chosen was Minion~\cite{minion06},
for its fast and scalable constraint solver with particular emphasis on its
table based constraints. Not only can minion show that indeed there are no
extensions of the soduku given in Figure~\ref{fig:soduku}, but in
Figure~\ref{fig:almost-soduku} we have a near miss, an orthogonal array that
satisfies the subsquare and column constraints but not row constraints of a
soduku. In terms of near miss soduku, Figure~\ref{fig:almost-soduku} is probably
the closest one can come to extending the orthogonal set.

\begin{figure}

  \begin{center}

\[
  \begin{array}{ccc|ccc|ccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
8 & 9 & 7 & 2 & 3 & 1 & 5 & 6 & 4 \\
6 & 4 & 5 & 9 & 7 & 8 & 3 & 1 & 2 \\
\hline
2 & 3 & 1 & 5 & 6 & 4 & 8 & 9 & 7 \\
9 & 7 & 8 & 3 & 1 & 2 & 6 & 4 & 5 \\
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \\
\hline
3 & 1 & 2 & 6 & 4 & 5 & 9 & 7 & 8 \\
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \\
5 & 6 & 4 & 8 & 9 & 7 & 2 & 3 & 1 \\
\end{array}\quad\begin{array}{ccc|ccc|ccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \\
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
9 & 7 & 8 & 3 & 1 & 2 & 6 & 4 & 5 \\
3 & 1 & 2 & 6 & 4 & 5 & 9 & 7 & 8 \\
6 & 4 & 5 & 9 & 7 & 8 & 3 & 1 & 2 \\
\hline
5 & 6 & 4 & 8 & 9 & 7 & 2 & 3 & 1 \\
8 & 9 & 7 & 2 & 3 & 1 & 5 & 6 & 4 \\
2 & 3 & 1 & 5 & 6 & 4 & 8 & 9 & 7 \\
            \end{array}\]
          \[\begin{array}{ccc|ccc|ccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
9 & 7 & 8 & 3 & 1 & 2 & 6 & 4 & 5 \\
5 & 6 & 4 & 8 & 9 & 7 & 2 & 3 & 1 \\
\hline
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \\
6 & 4 & 5 & 9 & 7 & 8 & 3 & 1 & 2 \\
2 & 3 & 1 & 5 & 6 & 4 & 8 & 9 & 7 \\
\hline
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \\
3 & 1 & 2 & 6 & 4 & 5 & 9 & 7 & 8 \\
  8 & 9 & 7 & 2 & 3 & 1 & 5 & 6 & 4 \\
\end{array}
\]

  \[\begin{array}{ccc|ccc|ccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
6 & 4 & 5 & 9 & 7 & 8 & 3 & 1 & 2 \\
8 & 9 & 7 & 2 & 3 & 1 & 5 & 6 & 4 \\
\hline
5 & 6 & 4 & 8 & 9 & 7 & 2 & 3 & 1 \\
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \\
3 & 1 & 2 & 6 & 4 & 5 & 9 & 7 & 8 \\
\hline
9 & 7 & 8 & 3 & 1 & 2 & 6 & 4 & 5 \\
2 & 3 & 1 & 5 & 6 & 4 & 8 & 9 & 7 \\
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \\
\end{array}\quad\begin{array}{ccc|ccc|ccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
5 & 6 & 4 & 8 & 9 & 7 & 2 & 3 & 1 \\
9 & 7 & 8 & 3 & 1 & 2 & 6 & 4 & 5 \\
\hline
3 & 1 & 2 & 6 & 4 & 5 & 9 & 7 & 8 \\
4 & 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 \\
8 & 9 & 7 & 2 & 3 & 1 & 5 & 6 & 4 \\
\hline
2 & 3 & 1 & 5 & 6 & 4 & 8 & 9 & 7 \\
6 & 4 & 5 & 9 & 7 & 8 & 3 & 1 & 2 \\
7 & 8 & 9 & 1 & 2 & 3 & 4 & 5 & 6 \\
\end{array}\]
\end{center}
\caption{\label{fig:soduku}Five MOSLS of order \(q^{2} = 9\) that cannot be extended to six MOSLS of order \(9\).}
\end{figure}


\begin{figure}
  \begin{center}
    \[
  \begin{array}{ccc|ccc|ccc}

1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 \\
4 & 5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 \\
    7 & 8 & 9 & 7 & 8 & 9 & 7 & 8 & 9 \\
    \hline
8 & 9 & 7 & 8 & 9 & 7 & 8 & 9 & 7 \\
2 & 3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 \\
    5 & 6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 \\
    \hline
6 & 4 & 5 & 6 & 4 & 5 & 6 & 4 & 5 \\
9 & 7 & 8 & 9 & 7 & 8 & 9 & 7 & 8 \\
3 & 1 & 2 & 3 & 1 & 2 & 3 & 1 & 2 \\
  \end{array}\]
\caption{\label{fig:almost-soduku}A near miss extension of the MOSLS in Figure~\ref{fig:soduku}}
\end{center}
\end{figure}


% \section{Hypercubes and MDS Codes}

% The following section is a survey of known results about the connection between sets of mutually orthogonal hypercubes and MDS codes. As in the previous section we will mainly study these from a geometric angle, and connect what others have done to objects in geometry.
% We are interested in codes, sets of vectors over finite fields of a fixed length.

% \begin{definition}
%   An \((n, M, d)\) \(q\)-ary code \(C\) is a set of \(M\) vectors in \(\mathbb{F}_{q}^{n}\) with the property that any two vectors in the code (known as \textit{codewords}) \(\mathbf{u}, \mathbf{v} \in C\) have a \textit{hamming distance} of at least \(d\) --- that is the number of positions \(\mathbf{u}\) and \(\mathbf{v}\) disagree in is at least \(d\).
% \end{definition}

% The hamming distance function \(d(\mathbf{u}, \mathbf{v})\) is defined to be the number of positions \(i\) such that \(\mathbf{u}_{i} \neq \mathbf{v}_{i}\), and it is not too hard to show that the hamming distance is a metric function (being positive semi-definite, symmetric, and obeying the triangle inequality).
% The following bound is known as the \textit{Singleton Bound}, and it is a relatively crude upper bound on the number of codewords that can be a \(q\)-ary code of fixed length and distance.

% \begin{lemma}[Singleton Bound]
%   Given an \((n, M, d)\)-code \(C\) over \(\mathbb{F}_{q}^{n}\), \(M \leq q^{n - d + 1}\).
% \end{lemma}

% \begin{proof}
%   Suppose that \(C\) is an \((n, M, d)\)-code over \(\mathbb{F}_{q}^{n}\). Because \(C\) has distance \(d\) the first \(n - d + 1\) positions of each codeword must be unique, otherwise we would have two codewords \(\mathbf{u}, \mathbf{v}\) with distance \(n - (n - d + 1) = d - 1\) which is a contradiction.
%   So there can only be as many codewords as there are vectors in \(\mathbf{F}_{q}^{n - d + 1}\), and the bound \(M \leq q^{n - d + 1}\) follows.
% \end{proof}

% Codes that meet the Singleton Bound are called Maximally Distance Separated (MDS), on account of being a code with the largest distance of a fixed size. It turns out that MDS codes may be placed in one to one correspondence with another kind of object in geometry, projective arcs.

% \begin{definition}
%   A projective \(k\)-arc is a set of points in \(\PG(n, q)\), \(n \geq 3\) is a set of \(k \geq n + 1\) points such that no \(n + 1\) points lie in a common hyperplane.
% \end{definition}
% oeuaoeu
% These arcs are in some


\pagebreak
\printbibliography
% \bibliography{MOLS}{}

%   \bibliographystyle{apacite}

  % \bibliographystyle{apacite}
\end{document}