% Set up title page information % used by \maketitle a bit later on Searching for Line Transitive, Point Imprimitive, Linear Spaces \thanks{Submitted in partial fulfilment of the requirements for the Bachelor of Science degree with Honours at The University of Western Australia}
Gregory Cresp
abstract.tex
%auto-ignore
\section*{Abstract}
A finite linear space is a finite set of points and lines, where any
two points lie on a unique line. Well known examples include
projective planes. This project focuses on linear spaces which admit
certain types of symmetries. Symmetries of the space which preserve
the line structure are called \emph{automorphisms}. A group of these
is called an \emph{automorphism group} of the linear space. Two
interesting properties of linear spaces are point imprimitivity and
line transitivity. Point imprimitive spaces admit a second structure
on the points aside from the lines, which is also preserved by an
automorphism group. In line transitive spaces, given any two lines,
an automorphism can be found that maps one line to the other.

Very few point imprimitive, line transitive linear spaces, apart from
projective planes, are known. Such spaces that have been found have
been surprising. One point of interest is whether such spaces are rare
and the known ones are in some sense exceptional, or if there are many
such spaces, but mathematicians have been looking in the wrong
places.

Here we investigate methods to construct a line transitive, point
imprimitive linear space over a given point set and automorphism
group. We  employ these methods on two given automorphism groups,
both on a set of $451$ points. This was an exceptional situation
identified in theoretical work of Praeger and Tuan. Included in this is the
development of an algorithm, written in GAP, an algebraic programming
system, and C, to perform these constructions. This algorithm is
extendible to a wider class of groups.

%Usually a search for spaces admitting a certain automorphism group is
%written specifically tailored to that group, based on combinatorial
%and algebraic existence criteria. The aim of this project is to write
%a share package for GAP, an algebraic programming system. This
%package will take a group and several parameters as input and
%systematically search for a linear space admitting this group as its
%automorphism group. The package will work in two parts. The first,
%written in GAP, will perform group analysis to provide more
%information about the group action and its orbits. Although GAP is
%very useful for group analysis it is not well suited to combinatorial
%searches. For speed, the second part will be written in C and will
%perform the search. It is hoped that, by the time the package is
%completed, some promising parameter sets will have been
%identified. These sets will be searched using the package.

acknow.tex
%auto-ignore
\begin{acknowledgements}
There are many people who contributed to the production of this
dissertation.

My thanks go to my supervisors Prof.~Cheryl E. Praeger and Dr.~Alice
Niemeyer. Without their time and effort this work would never have even
begun.

I would like to also acknowledge the assistance of Dr.~Anton
Betten. Much of the C code used in this work is based on code written
by him, and his advice on design theory was invaluable. My thanks go
to Mr.~Maska Law, who assisted with background on projective planes of
order 7, and Dr.~Rick McFeat, who directed me on Galios theory.

For their efforts in proof reading and their continued support
throughout the year, my sincerest thanks for Dr.~John Cresp, Mrs.~Judy
Cresp and Miss Kate Gilders.

Finally I must acknowledge the support of my fellow honours students
for their advice on latex, GAP and not going insane during the year.

\end{acknowledgements}

chapter1.tex
%auto-ignore
\chapter{Preliminaries}\label{chapt:prelims}

\section*{Introduction}

Our work will require a basic background in the theory of group
actions and permutations. We assume the reader already has a
background in group theory. Here we will introduce the idea of a group
acting on a set and how this action can alternatively be viewed as a group of
permutations on the set. This material will form the basis for work in
later chapters. Throughout this chapter we will let $\Omega$ denote a
finite set and $G$ a group. Also, $1_{G}$ will be used to denote the
identity of $G$, or $1$ if the group is clear from the
context. Although most of the theory given here also applies to
infinite sets and groups, we will restrict ourselves to finite sets
and groups.

\section{Permutation Groups}\label{sect:permgrps}
The study of permutation groups has been an important part of group
theory. In fact, it can easily be shown that any group is isomorphic to
some permutation group. We are interested in permutation groups on points
of our linear spaces. A permutation group is a group of permutations on
a given set, $\Omega$, using functional composition.

\begin{definition}
Let $\Omega$ be a set. A \emph{permutation} of $\Omega$ is a 1-1 and onto
map $\Omega\to\Omega$.
\end{definition}

We call the group of all permutations on $\Omega$ the \emph{symmetric
group} of $\Omega$ and denote it Sym$(\Omega)$. Any subgroup of
Sym$(\Omega)$ is called a \emph{permutation group on $\Omega$}.

\section{Group Actions}\label{sect:groupaction}

We will often have the elements of $G$ moving the elements of
$\Omega$ around in some way. An example of this is how the group of
rotations of the square affects the set of the vertices of the
square. This movement is called a group action.

\begin{definition}
Let $G$ be a group and $\Omega$ a set. A \emph{group action} of $G$ on
$\Omega$ is an assignment $\Omega\times G\to\Omega$, satisfying:
\begin{itemize}
\item $(\omega,1)\mapsto\omega$ for all $\omega\in\Omega$.
\item $((\omega,g),h)\mapsto(\omega,gh)$ for all $\omega\in\Omega,\ g,h\in G$.
\end{itemize}
The image of $(\omega,g)$ is denoted $\omega^g$.
\end{definition}

It is easy to see that any element of $G$ gives rise to a permutation
of $\Omega$. Consider the map $\varphi_g:\Omega\to\Omega$ given by
$\varphi_g(\omega)=\omega^g$ for all $\omega\in\Omega$. Clearly this is
a map from $\Omega$ into itself. Since $\Omega$ is a finite set,
$\varphi_g$ is 1-1 if and only if it is onto. Suppose
$\varphi_g(\alpha)=\varphi_g(\beta)$. Then $\alpha^g=\beta^g$, so
$(\alpha^g)^{g^{-1}}=(\beta^g)^{g^{-1}}$ and thus $\alpha=\beta$. We can
extend this idea to a function $\varphi:G\to\rm{Sym}(\Omega)$ by
$\varphi(g)=\varphi_g$. This is well defined, since each $\varphi_g$
is. This process gives us a permutation corresponding to
each element of $G$. This is referred to as the \emph{permutation
representation} of the action of $G$. We can, and will, use the group
action and its permutation representation interchangeably.

This permutation representation map $\varphi$ may not be one to
one. It may be that two different elements of $G$ act in the same
way. Since $\varphi$ is a homomorphism, this is equivalent to the
kernel of the map being non-trivial. By this we mean that there is
some non-identity $g\in G$ such that $\varphi(g)=1_{Sym(\Omega)}$. If
$\varphi$ is 1-1, the action is called faithful. If an action is
faithful then we can identify $G$ with $\varphi(G)\le\text{Sym}(\Omega)$.

\begin{definition}
Let $G$ act on $\Omega$. The action is said to be \emph{faithful} if
the only element of $G$ to fix all elements of $\Omega$ is $1$.
\end{definition}

Given $G$ acting on $\Omega$, we can also consider $G$ acting on the
subsets of $\Omega$. We define the \emph{set-wise image} of a
subset $S\subset\Omega$  under $g\in G$ to be
$S^g=\{\omega^g|\omega\in S\}$.

We are often interested in where in the set a given element can be
mapped to under the action. We call the set of all possible images of
a point the orbit of that point.
\begin{definition}
Given $G$ acting on $\Omega$ and some $\omega\in\Omega$, the
\emph{orbit} of $\omega$ under $G$, denoted $\omega^G$ is the set
$\{\omega^g|g\in G\}$.
\end{definition}

It is also often interesting to consider, for a given
$\omega\in\Omega$, which elements of $G$ fix $\omega$. The set of all
such elements is called the \emph{stabiliser of $\omega$} and is
denoted $G_{\omega}$.

\section{Properties of Actions}\label{sect:actionprops}

The first property of group actions we consider is transitivity. A
transitive action is one where it is possible to move from any element
in the set to any other element of the set. Another way of looking at
this is that $\Omega$ is one $G$-orbit.

\begin{definition}
Let $G$ be a group acting on $\Omega$. The action is \emph{transitive}
if, for any $\alpha,\beta\in\Omega$ there is some $g\in G$ such that
$\alpha^g=\beta$.
\end{definition}

The second property is primitivity. Before we can describe a primitive
action, we need to consider partitions and invariant partitions.

\begin{definition}
A \emph{partition} of a set $\Omega$ is a set of pairwise disjoint
subsets of $\Omega$, say $\mathcal{C}=\{C_1,C_2,\cdots,C_n\}$ such
that $\cup_{i=1}^{n}C_i=\Omega$.
\end{definition}

We call the subsets in a partition classes. An alternative name is
blocks, but we will see in Chapter \ref{chapt:designs} that this would
cause confusion with lines. A partition is said to be $G$-invariant
%when $G$ acts on $\Omega$ and the set-wise image of any class under
%any element of $G$ is also a class.
invariant partitions. A transitive action that is not
primitive is called \emph{imprimitive}. We will see later that we are
interested in imprimitive actions.

In many applications, we wish to find the size of an orbit without
having to explicitly calculate that orbit. One way of doing this is to
find the stabiliser of an element in the orbit.

\begin{theorem}[Orbit Stabiliser Theorem]\label{thm:ost}
Let $G$ act faithfully on $\Omega$, a finite set and
$\omega\in\Omega$. Then $|\omega^G|=\frac{|G|}{|G_{\omega}|}$.
\end{theorem}

For a proof of this see \cite[Theorem 1.4A]{dixonmortimer}.

A property of interest, but less importance to us, is regularity. We
say an action is \emph{semi-regular} if the point stabiliser of any point
fixes all points. A \emph{regular} action is one that
is semi-regular and transitive.

\begin{lemma}\label{lemma:regularidentify}
Let $G$ act faitfully and regularly on $\Omega$. Then we can identify
$\Omega$ with $G$ in such a way that $G$ acts by its group operation.
\end{lemma}
\begin{proof}
Since $G$ is faithful and regular, the only element of $G$ that can
fix any point is $1$. Taking any $\omega\in\Omega$ and
define the map $\phi:\Omega\to G$ by $\omega^g\mapsto
g$. Since the action is transitive, any $\alpha\in\Omega$ is
$\omega^g$ for some $g\in G$. Furthermore, if $\omega^g=\omega^h$ then
$\omega^{gh^{-1}}=\omega$ and hence, since the point stabiliser of any
point is $\{1\}$, $g=h$. Hence this map is well defined. Clearly if
$\phi(\alpha)=\phi(\beta)$ then
$\alpha=\omega^{\phi(\alpha)}=\omega^{\phi(\beta)}=\beta$ so the map
is 1-1. Also, by the Theorem \ref{thm:ost}, $|G|=|\omega|$ and both
are finite, so the map is also onto. Hence $\phi$ is an identification
of $\Omega$ with $G$. Finally, notice $\phi(\alpha^g)=\phi(\alpha)g$
for all $\alpha\in\Omega,g\in G$ by the definition of $\phi$.
\end{proof}

\section*{Conclusion}

We have introduced here the idea of a group action. There are several
properties of group actions that will be important to us in later
chapters. First, we will only be considering faithful actions, where
the only element of the group to fix all elements of the set is $1$.
We have also introduced imprimitive actions and transitive actions,
which will be used in defining properties of linear spaces in Chapter
\ref{chapt:ls}.

chapter2.tex
%auto-ignore
\chapter{Linear Spaces}\label{chapt:ls}

\section*{Introduction}
Before considering the main topic of this thesis - searching for
linear spaces with particular properties, we must first consider what
constitutes a finite linear space, and how we characterise these
properties. Here we introduce a linear space and define the two
properties of interest: line transitivity and point imprimitivity. We
will also consider the known examples of spaces with these
properties. We will briefly consider projective planes, but only to
explain why we decided not to search for them.

\section{Finite Linear Spaces}
A finite linear space is an ordered pair of sets, a set of points and
a set of lines.
\begin{definition}
Let $\mathcal{P}$ be a finite set and $\mathcal{L}$ a set of subsets
of $\mathcal{P}$. Elements of $\mathcal{P}$ are called \emph{points},
elements of $\mathcal{L}$ \emph{lines}. Then
$\mathcal{S}=(\mathcal{P},\mathcal{L})$ is a \emph{finite linear
space} if each line contains at least 2 points and,
given any two points, there is a unique line containing them both.
\end{definition}

In this dissertation we are only interested in finite linear spaces. We will
always take linear space to mean finite linear space.
We are mostly interested in looking at maps on the points which
preserve the line structure. We call these automorphisms.

\begin{definition}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space and
$g\in\rm{Sym}(\mathcal{P})$. Then $g$ is called an \emph{automorphism}
of $\mathcal{S}$ if, given any line $L\in\mathcal{L}$, the set-wise image,
$L^g=\{p^g|p\in L\}$ is also a line.
\end{definition}

It is clear that the composition of two automorphisms will be
an automorphism, since lines will be preserved throughout. It
thus makes sense to look at groups of automorphisms, using
functional composition. These will be subgroups of Sym$(\mathcal{P})$.

\begin{definition}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space and
$G\le \rm{Sym}(\mathcal{P})$. If all elements of $G$ are automorphisms
of $\mathcal{S}$ then $G$ is called an \emph{automorphism group} of
$\mathcal{S}$.
The group consisting of all automorphisms of $\mathcal{S}$ is called
the \emph{full automorphism group} of $\mathcal{S}$ and is denoted
Aut$(\mathcal{S})$.
\end{definition}

%From now on we will refer to $\mathcal{S}$ as a linear space with
%point set $\mathcal{P}$ and line set $\mathcal{L}$. We will let $G$
%denote an automorphism group of $\mathcal{S}$.
As we will see in Chapter \ref{chapt:designs}, we are often interested
in linear spaces with a constant line size. When this is the case, we
can construct some relationships between the number of lines and points,
the number of lines per point and the number of points per line.

\begin{lemma}\label{lemma:linesize}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space with
$|\mathcal{P}|=v$ and a constant line size $k$. Let $b=|\mathcal{L}|$
and $r$ be the number of lines through any point.
Then $b=\frac{v(v-1)}{k(k-1)}$, $bk=vr$ and $v-1=r(k-1)$.
\end{lemma}

\begin{proof}
Consider all pairs $(\{p_1,p_2\},L)$ where
$L\in\mathcal{L}$ and $p_1,p_2\in L $. Suppose there are $n$ of these.
If we first select a pair of points, then a line containing those
points we see $n=\frac{v(v-1)}{2}\cdot1$. If we select the line first,
then a pair of points on that line, $n=b\frac{k(k-1)}{2}$ hence
$b=\frac{v(v-1)}{k(k-1)}$.

Now consider the pairs $(p,L)$ with
$p\in\mathcal{P},L\in\mathcal{L},p\in L$.
By first selecting $p$, then $L$ with $p\in L$ we see there are $vr$
of these. Now by selecting $L$, then $p\in L$, there are $bk$ such
pairs. Hence $vr=bk$.

Combining these two equations, we see that
$vr=bk=\frac{v(v-1)}{k(k-1)}k=v\frac{v-1}{k-1}$. The result follows.
\end{proof}

\section{Projective Planes}

Projective planes are a sub-class of linear spaces. In essence, a
projective plane is a linear space where any two lines have a
unique point in common.

\begin{definition}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space. We call
$\mathcal{S}$ a \emph{projective plane} if
$|\mathcal{P}|\ge3$, every line contains at least 3 points and any two lines intersect in a unique point.
%\begin{itemize}
%\item There are at least 3 points, so $|\mathcal{P}|\ge3$
%\item Every line contains at least 3 points, so for $L\in\mathcal{L}, |L|\ge3$.
%\item Any two lines intersect in a unique point.
%\end{itemize}
\end{definition}

%The first two of these conditions are to prevent trivial projective
%planes.

In projective planes there is  a duality between points and
lines. This means that any correct statement involving points and
lines is also correct if the words `points' and `lines' are
exchanged. For example, if `every line contains exactly $k$ points' it
is also true that `every point lies on exactly $k$ lines'.

We can see then that projective planes are very specific objects. As we
will see in Section \ref{sect:lsexamples}, there is an infinite family
of projective planes which are linear spaces of the type we are
interested in. This relates to the exceptional nature of projective
planes, so in this dissertation projective planes will not be considered.

When a linear space has a constant line size, it is easy to decide
whether the space is a projective plane or not. This characterisation
of projective planes arises from the duality of points and lines.

\begin{lemma}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space with
constant line size. Then $\mathcal{S}$ is a projective plane if and
only if $|\mathcal{P}|=|\mathcal{L}|$.
\end{lemma}

\begin{proof}
%Suppose $\mathcal{S}$ is a projective plane. Then the number of points
%equals the number of lines by duality (consider the dual of the
%statement `there are $b$ lines').
Suppose $\mathcal{S}$ is a linear space with constant line size. Let
$v,b,k,r$ denote the
number of points, lines, points per line and lines per point
respectively. Consider the tuples $(L_1,L_2,p)$ where
$L_1,L_2\in\mathcal{L}$ and $p\in L_1\cap L_2$. Suppose there are $n$
of these. Since two lines intersect in at most one point (otherwise
the linear space condition is violated), we have $n\le b(b-1)$ and
equality occurs only for projective planes. Choose $L_1$, then $p\in
L_1$ then $L_2\ne L_1$ with $p\in L_2$, so we see $n=bk(r-1)$.

First suppose $\mathcal{S}$ is a projective plane. Then we can choose
$L_1$ and $L_2$ arbitrarily, they define a unique $p$. Hence
$n=b(b-1)=bk(r-1)$. It follows that $b-1=k(r-1)$. However,
$v-1=k(r-1)$ from Lemma \ref{lemma:linesize} and hence $v=b$.

Suppose there are equal numbers of points and lines, so $v=b$. In
Lemma \ref{lemma:linesize} we saw $bk=vr$ and $\frac{v(v-1)}{2}=b
\frac{k(k-1)}{2}$. It follows, since $v=b$, that $r=k$ and
$(v-1)=k(k-1)$. Thus $n=bk(r-1)=bk(k-1)=b(v-1)=b(b-1)$,
%\begin{eqnarray*}
%n&=&bk(r-1)\\
%&=&bk(k-1)\\
%&=&b(v-1)\\
%&=&b(b-1)
%\end{eqnarray*}
and hence $\mathcal{S}$ is a projective plane.
\end{proof}

\section{Properties of Linear Spaces}
An automorphism group of a linear space can be thought of as a group
action on the points in the obvious way. We can also consider the
induced action of this group on the lines, considering lines as
subsets of points. Two properties often of interest in group actions are
transitivity and imprimitivity. These were both discussed in Chapter
\ref{chapt:prelims}. We will now see how these ideas lead to two
important properties a linear space may have with respect to an
automorphism group.

The first property that we consider is line transitivity.

\begin{definition}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space and
$G\le \rm{Aut}(\mathcal{S})$. Then $G$ is said to be \emph{line
transitive} on $\mathcal{S}$ if the point-wise action of $G$ on
$\mathcal{L}$ is transitive. By this we mean that, given any two lines
$L_1,L_2\in\mathcal{L}$, there is some map $g\in G$ such that
$L_1^g=L_2$.
\end{definition}

We can see that if $G$ is line transitive and $G\le H\le
\rm{Aut}(\mathcal{S})$ then $H$ will also be line transitive, since
the required map between two lines could come from $G$. Thus line
transitivity is preserved `upwards'.

The second property of interest is point imprimitivity. We saw in
Section \ref{sect:actionprops} that a group action is said to be
imprimitive if it preserves some non-trivial partition of the set.

\begin{definition}
Let $\mathcal{S}=(\mathcal{P},\mathcal{L})$ be a linear space and
$G\le \rm{Aut}(\mathcal{S})$. Then $\mathcal{S}$ is said to be \emph{$G$-point
imprimitive} if there is some non-trivial
$G$-invariant partition of $\mathcal{P}$.
\end{definition}

Notice if a group leaves a partition invariant, then so will any
subgroup of it. Hence if $G$ is point imprimitive on $\mathcal{S}$,
then any subgroup of $G$ would also be. Thus point imprimitivity is
preserved `downwards'.

These two properties seem to be working in different directions. Line
transitivity needs lines, and hence points, to move around a lot, and
is preserved `upwards'. Point imprimitivity needs points to move little
under $G$ and is preserved `downwards'. It may therefore be difficult
to find some middle ground between these, where a space was be
both line transitive and point imprimitive. These two properties can
hold at the same time, see Section \ref{sect:lsexamples}.

%Part of the interest in this consideration is in the related question
%of when $G$ can be imprimitive on the lines of $\mathcal{S}$. It has
%been conjectured by Delandtsheer in \cite{} that if $G$ is point primitive on
%$\mathcal{S}$ then it must be line primitive. Since, by definition
%an action
%cannot be primitive unless it is transitive, the first consideration
%is when the space may be line transitive. This conjecture has been
%proven  to hold under a number of more restrictive conditions,
%including that the line size of the space is less than 30 in
%\cite[Theorem 2]{delandtsheer}.

\section{Isomorphic Linear Spaces}

As with many other algebraic structures, we have a concept of
isomorphism of linear spaces. Two linear spaces are isomorphic if they
have the same number of points and the
line structure is the same, up to some re-naming of the points.
%Given a linear space, it is possible to construct many spaces that
%initially seem unrelated to the first, but on closer inspection have
%the same underlying structure. This can be done by renaming the points
%in some fashion, but keeping the line structure the same. This idea of
%spaces having the same underlying structure is called isomorphism.

\begin{definition}
Suppose $\mathcal{S}_1=(\mathcal{P},\mathcal{L})$ and
$\mathcal{S}_2=(\mathcal{Q},\mathcal{M})$ are both linear spaces. Then
$\mathcal{S}_1$ and $\mathcal{S}_2$ are said to be \emph{isomorphic}
if there is some 1-1 and onto map $\varphi:\mathcal{P}\to\mathcal{Q}$
such that $\varphi(\mathcal{L})=\mathcal{M}$. This is denoted
$\mathcal{S}_1\cong\mathcal{S}_2$ and $\varphi$ is called an
\emph{isomorphism}.
\end{definition}
By $\varphi(\mathcal{L})=\mathcal{M}$ we mean that for any line
$L\in\mathcal{L}$, the point-wise image of $L$ under $\varphi$ is in
$\mathcal{M}$ and conversely, $\varphi^{-1}(M)\in\mathcal{L}$ for any
$M\in\mathcal{M}$.

If the two linear spaces have the same point set, say $\mathcal{P}$,
then the isomorphism will belong to Sym$(\mathcal{P})$.

Isomorphism is an important concept, since when working with linear
spaces there is no real difference between working with a space and
working with another isomorphic space.

\section{Examples of Point Imprimitive, Line Transitive, Linear
Spaces}\label{sect:lsexamples}

The first line transitive, point imprimitive, linear spaces to be
identified were projective planes. In fact, an infinite family of these
has been identified. This family consists of the Desarguesian
projective planes under the action of Singer cycles. We will outline
how such spaces and the action are constructed.

\subsection{Desarguesian Planes}

The non-zero elements of a field form a cyclic multiplicative group. A
generator of this group is called a \emph{primitive element} of the
field.

Take some prime power $q\in\Z$, so $q=p^n$ for some prime $p$ and some
integer $n$. Consider the field with $q$ elements, $\F_q$. We will use
$F_q$ to construct $F_{q^3}$. Take some irreducible polynomial $f(X)$ of
degree 3 in $\F_q[X]$. By irreducible, we mean all divisors of $f(X)$
have degree either $0$ (the constant polynomials) or degree
deg$(f(X))$. Let $\alpha$ be some zero of this ploynomal. Notice
$\alpha\notin\F_q$, since if it was, $X-\alpha$ would divide $f(X)$,
contradicting irreducability. Construct the field $\F_{q^3}$ by
$\F_{q^3}=\F_q(\alpha)=\{a+b\alpha+c\alpha|a,c,b\in\F_q\}$.

We say $f(X)$ is a \emph{primitive polynomial} if $\alpha$ is a
primitive element of $\F_{q^3}$ constructed in this way. We wish to
construct $\F_{q^3}$ using a primitive polynomial. Find some primitive
element, $\beta$, of $F_{q^3}$. Take its minimal polynomial, $f(X)$,
over $F_q$ (the monic polynomial of least degree such that
$f(\beta)=0$). Identify $\beta=X$. Now construct $\F_{q^3}$ by taking
all polynomials of degree less than $3$ from $\F_q[X]$, with
multiplication and addition modulo $f(X)$. We can think of $\F_{q^3}$ as
$V$, a 3 dimensional vector space over $q$, with basis
$\{1,X,X^2\}$. We see that this is indeed a basis, for if there were
$\alpha,\beta,\gamma\in\F_q$ not all $0$ such that $\alpha+\beta
X+\gamma X^2=0$ (in $\F_{q^3}$) this would violate $f(X)$ being the
minimal polynomial of $\alpha$, since deg($f(X)$)=3. Notice from this
construction, $X$ is a primivie element of $\F_{q^3}$.

Now define $\mathcal{S}=(\mathcal{P},\mathcal{L})$ by $\mathcal{P}$ being the
1-dimensional subspaces of $V$ and $\mathcal{L}$ the 2-dimensional
subspaces of $V$. Let a point lie on a line if the corresponding 1-D
subspace is a subset of the corresponding 2-D subspace. Notice that
any two distinct 1-D subspaces lie on a unique 2-D subspace and any
two 2-D subspaces intersect at a unique 1-D subspace. As a result,
$\mathcal{S}$ is a projective plane.

Note that any 2-D subspace contains exactly $q+1$ distinct 1-D
subspaces, so the space has a constant line size. Each non-zero
vector $x\in V$ lies on the unique 1-D subspace $\langle
x\rangle=\{\lambda x|\lambda\in\F_q\}$, and each 1-D subspace contains
$q-1$ non-zero vectors. There are $q^3-1$ non-zero vectors total, so
$|\mathcal{P}|=\frac{q^3-1}{q-1}=q^2+q+1$. Since $\mathcal{S}$ is a
projective plane, there are also $q^2+q+1$ lines.

We now construct the Singer cycle, acting on $\mathcal{S}$.
Take the degree 1 polynomial $X\in \F_{q^3}$ and consider $X$ acting
on $V$ by multiplication, so $g(X)\mapsto Xg(X)$. This
is an invertible linear transformation of $V$, since $X(\alpha g(X)+ \beta
h(X))=\alpha Xg(X) + \beta Xh(X)$ by the properties of multiplication
and addition
on fields, and $\F_{q^3}$ is a field, so $(X)^{-1}$ exists. This defines
an automorphism of $\mathcal{S}$, since invertible linear
transformations preserve subspaces, so 1-D subspaces (points) are
mapped to 1-D subspaces and 2-D subspaces (lines) to 2-D
subspaces, preserving incidence.

Since $X$ is a primitive element $\F_{q^3}$, it is a generator of the
multiplicative group $\F_{q^3}\setminus\{0\}$.
It follows that $\langle X\rangle\cong\Z_{q^3-1}$ is an automorphism
group of $\mathcal{S}$. Note this action on $\mathcal{P}$ is not
regular, since $(q^3-1)>|\mathcal{P}|$.

We claim that $K$, the kernel of the action of $\langle X\rangle$ on
$\mathcal{P}$ is the group of non-zero scalars of $\F_{q^3}$. Notice
the group of non-zero scalars of $\F_{q^3}$ is isomorphic to
$\F_q\setminus\{0\}$. Any element of $\F_q\setminus\{0\}$
fixes any point in $\mathcal{P}$. Take $p\in\mathcal{P}$, say
$p=\langle x\rangle$ for some $x\in
V$. Then take $\alpha\in\F_q\setminus\{0\}$. We see
$p^\alpha:=\alpha\langle x\rangle=\langle\alpha x\rangle=\langle
x\rangle=p$ since $\F_q$ is a field.
Hence $\F_q\setminus\{0\}$ is in the kernel of the action. We now show that any
element of the kernel of $\langle X\rangle$ on $\mathcal{P}$ is also
a non-zero scalar of $\F_{q^3}$.

Suppose we have some element of $\langle X\rangle$ that fixes
all points in $\mathcal{P}$. Let this element be $X^i$ for some
$i=1,2,\cdots,q^3-1$. Then, since $X^i$ fixes all points, in
particular, $X^i$ must fix the subspace generated by $1$, which is
$\F_q\setminus\{0\}$. Hence $1^{X^i}\in\F_q\setminus\{0\}$. Notice
that $X^i:1\mapsto X^i$ and hence $X^i\in\F_q\setminus\{0\}$.

As a multiplicative group, $\F_q\setminus\{0\}\cong\Z_{q-1}$. It
follows that the permutation group on $\mathcal{P}$ induced by
$\langle X\rangle$ is isomorphic to
%For any $x\in V$,
%$V_x=\{(\lambda,\lambda,\lambda)|\lambda\in \F_q, \lambda\ne0\}$ and hence
%$|V_x|=q-1$. We know $V\setminus(0,0,0)$ is a cyclic group of order $q^3-1$,
%so its induced action on points is isomorphic to
$\frac{\Z_{q^3-1}}{\Z_{q-1}}=\Z_{q^2+q+1}$. Now
$|\mathcal{P}|=q^2+q+1$, so this action is clearly regular. Hence we
can identify the points with $\Z_{q^2+q+1}$ and consider the action to
be addition modulo $q^2+q+1$. The action on the lines is isomorphic to
the same group and there are $q^2+q+1$ lines, so this action is
transitive on the lines.

Suppose that $q^2+q+1$ is not prime, so $q^2+q+1=ab$ for
$a,b\in\Z^+$, neither being 1. We can construct a partition with $a$
classes of size $b$ that is preserved by the Singer cycle.
Consider the partition $\mathcal{C}=\{C_1,C_2,\cdots,C_a\}$ where
$C_i=\{bj+i|j\in\{0,1,\cdots,a-1\}$. This partition is clearly
preserved by the action since $C_i^c$=$C_{i+c(\text{mod }a)}$ for all
$c\in\Z_{q^2+q+1}$. We thus have a point imprimitive, line transitive
action on a linear space. There are infinitely many values of $q$ such
that $q^2+q+1$ is not prime. Take $p\ne3$ to be prime. There are
infinitely many primes. Consider $q=p^2$. Then $p=1$ or $2$ (mod
3). Notice $1^2=2^2=1$ (mod 3), so $q=1$ (mod 3). Hence
$q^2+q+1=1+1+1=0$ (mod 3), so 3 divides $q^2+q+1$. Clearly then
$q^2+q+1$ is prime. Hence there are infinitely many
such projective planes. However, since projective planes are already
exceptional in some ways as linear spaces, the line transitive, point
imprimitive spaces that are not projective planes are of more interest.

\subsection{Other Linear Spaces}

Of the non projective planes, only a very small number have so far
been identified. The first was constructed by Mills in \cite{mills}. This
was a space on 91 points, where the size of each line was 6. This
space was constructed using a different method by Colbourn and
Colbourn in \cite{colbourne} and another, non-isomorphic space on 91 points
with the same line size was identified at the same time. In both
cases, the construction of line transitive, point imprimitive linear
spaces was not the aim of the research, it was instead a by-product of
other work.

The most recently identified such spaces is a class of 467 spaces each
having 729 points and a constant line size of 8. These are a complete
classification of point imprimitive, line transitive, linear spaces
with this number of points and line size. The classification was
completed in \cite{2-729-8-1}. In fact, these are the only linear
spaces achieving equality in the Delandtsheer-Doyen bound discussed in
Section \ref{sect:innerpairs}.

No more point imprimitive, line transitive, linear spaces
have been identified in the last 9 years and a total of only 469
such spaces, excluding projective planes, have been found. This leads
us to question whether such spaces are as rare as this suggests, or
whether, with more research, many more such spaces might be identified.

\section*{Conclusion}

We have introduced here the concept of a line transitive, point
imprimitive, finite, linear space. We have also noted that very few
such spaces, apart from projective planes, are known. At this stage
we have not introduced any methods for testing whether a given space
is line transitive or point imprimitive, nor any way of constructing
such spaces. These methods are based on a related area, design theory,
which we will introduce in
the following chapter.
%Chapter \ref{chapt:designs}.

chapter3.tex
%auto-ignore
\chapter{Design Theory}\label{chapt:designs}

\section*{Introduction}

We now introduce the concept of a design. The problem of finding line
transitive, point imprimitive, linear spaces is a special case of finding point
imprimitive, line transitive designs. The idea of a design parameter
set will be introduced. These parameters give information
about the possible existence of such a design. The problem then
becomes trying to show the existence of a design with parameters
satisfying known conditions.

The advantage of searching for designs is that,
although we are looking for a particular type of design, there are
some results arising from more general design theory which can
be used to these ends. Two of these results, the Orbit Theorem and the
Delandtsheer-Doyen Theorem, are presented here. How these results can be
used as part of a search will be discussed. This will be put into
practise in Chapter \ref{chapt:search}.

\section{$2$-$(v,k,1)$ Designs}

A $2$-$(v,k,1)$ design may be thought of as a special type of linear
space. In essence, it is a linear space where all the lines contain the
same number of points.
\begin{definition}
Suppose $\mathcal{D}=(\mathcal{P},\mathcal{L})$ where $\mathcal{P}$ is
a finite set and $\mathcal{L}$ is a set of subsets of
$\mathcal{P}$. We refer to elements of $\mathcal{P}$ as \emph{points}
and of $\mathcal{L}$ as \emph{lines} or \emph{blocks}. Then $\mathcal{D}$ is a
$2$-$(v,k,1)$ \emph{design} if
there are $v$ points, each line is a $k$-subset of $\mathcal{P}$ and,
given any 2 points in $\mathcal{P}$, there is exactly 1 line in
$\mathcal{L}$ containing them both.
%$\mathcal{L}$ containing them both.
%\begin{itemize}
%\item $|\mathcal{P}|=v$
%\item For any $L\in\mathcal{L}$, $|L|=k$
%\item Given any 2 points in $\mathcal{P}$, there is exactly 1 line in
%$\mathcal{L}$ containing them both.
%\end{itemize}
\end{definition}

We see that the last condition is exactly the same as the linear
space condition discussed in Chapter \ref{chapt:ls}. From now, when
$v$ and $k$ are not relevant, we will refer to $2$-$(v,k,1)$ designs
as designs.

$2\text{-}(v,k,1)$ designs are a specific class of $2\text{-}(v,k,\lambda)$
designs. The definition of a $2\text{-}(v,k,\lambda)$ design is the same,
except that every 2 points lie on exactly $\lambda$ lines.

Given the similarity between designs and linear spaces, it is not
surprising that automorphisms are defined in the same way.

\begin{definition}
Let $\mathcal{D}=(\mathcal{P},\mathcal{L})$ be a design.
An \emph{automorphism of $\mathcal{D}$} is a map
$\pi\in\rm{Sym}(\mathcal{P})$ such that $L^\pi\in\mathcal{L}$ for all $L\in\mathcal{L}$.
A group $G\le
\rm{Sym}(\mathcal{P})$ is an \emph{Automorphism group} of $\mathcal{D}$
if each of its elements is an automorphism of $\mathcal{D}$. The group
of all automorphisms of $\mathcal{D}$ is denoted Aut$(\mathcal{D})$.
\end{definition}
Here, as before, we define the action of $G$ on lines to the induced
action on $k$-subsets of points. Given
the definitions are the same, automorphism groups are the same whether
a space is considered as a design or just as a linear space.

We noted earlier that if a linear space is line transitive, then its
line set is the orbit of any line under the automorphism
group. It follows, since automorphisms are one to one, that the size
of the lines is constant in a line transitive, linear space.

\begin{lemma}
Let $(\mathcal{P},\mathcal{L})$ be a linear space and $G$ be a line transitive
automorphism group. Then the line size of the space is constant.
\end{lemma}
\begin{proof}
Take some fixed $L\in\mathcal{L}$. Now take any
$M\in\mathcal{L}$. Since $G$ is transitive on $\mathcal{L}$,
there is some $g\in G$ such that $M=L^g$. It follows that
$M=\{p^g|p\in L\}$ and hence, since $g$ is 1-1, $|M|=|L|$. This is true
for any $M$, so the line size is constant.
\end{proof}

Since any linear space with a constant line size is a $2$-$(v,k,1)$
design for some $v$ and $k$, any line transitive linear space is a line
transitive $2$-$(v,k,1)$ design. The line transitivity of the design
follows since any automorphism group of the space considered as a
linear space is also an automorphism group of the space considered as
a design.

\section{Parameter Sets}
We are interested in identifying line transitive, point imprimitive
linear spaces. Since we know all such spaces are designs, it is
sufficient to identify $G$-point imprimitive, line transitive
$2$-$(v,k,1)$ designs.


The first step in this is to identify $v$, $k$ and $G$ such that such
a design might exist. We call $v$, $k$ and $G$ a \emph{parameter set}.
The need to identify a parameter set seems hardly worth mentioning.
However, the approach to identifying parameter sets is very different to
identifying designs.

To identify potential parameter sets, it is a matter of excluding
those sets for which no design may exist. This is achieved using
numerical and combinatorial arguments on $v$ and $k$ and using group
theoretical arguments on $G$. Using these arguments it is possible to
narrow the parameter sets to be considered down to a relatively small
number. It is important to note however that this gives no guarantees
that a design will exist with these parameters. It then becomes a
matter of trying to construct a point imprimitive, line transitive
design with the given parameters.

It should be noted that the group $G$ is not usually identified as
a permutation group on $\mathcal{P}$.
%permutation representation, which is required for
%our search.
The possible permutation representations can be identified using group
theoretic arguments on the information known about $G$. It is often
the case that there may be more than one possible permutation
representation for a given $G$, or several groups $G$ with specific
detailed properties. Since there is no way of deciding if
any one representation or group is more correct than another, each of these
representations and groups needs to be searched separately.

The work of identifying parameter sets will not be considered
here. In remainder of this dissertation we will assume such a set has already
been identified.

\section{The Orbit Theorem}\label{sect:orbitthm}

We assume that we are working with a parameter set $v$, $k$, $G$,
where $G$ has a prescribed permutation representation on some
set $\mathcal{P}$ where $|\mathcal{P}|=v$. Since we require the final
design to be point imprimitive, we must already have $G$ imprimitive on
$\mathcal{P}$.

We wish to find $G$-line transitive $2$-$(v,k,1)$ designs
$\mathcal{D}=(\mathcal{P},\mathcal{L})$. The
problem then is to identify one or more line sets $\mathcal{L}$ which
result in a design. One brute force approach to solving this would be
to search all possible sets of $k$-subsets of $\mathcal{P}$ and check
which ones satisfy the design requirements and are orbits under
the $G$ action. In almost every case this is computationally impossible.

We noted earlier that, since we require $G$ to be transitive on
lines, $\mathcal{L}$ is the $G$-orbit of any line
$L\in\mathcal{L}$. To identify a line set it is sufficient then to
identify a single line $L$. Our problem reduces then to searching
possible $k$-subsets of $\mathcal{P}$. It is still computationally
impossible to check each set by first constructing its orbit under $G$
and then checking the design requirements. This is where our first
design theory result becomes useful. The Orbit Theorem gives necessary
and sufficient conditions on a $k$-subset for its orbit to be a
design. In fact, this result was originally written for more general
$t$-$(v,k,\lambda)$ designs, spaces where every $t$-subset of points
lies on exactly $\lambda$ blocks, but we only consider it in the context
useful to us here.

The ideas behind this theorem come from a construction used by Altop,
outlined in \cite{hughesandpiper}. This was used to construct
4-designs (similar to 2-designs, except every 4 points lie on exactly
$\lambda$ lines), which were always 5-designs. The theorem as we
present it here, along with the Delandtsheer-Doyen Theorem (Theorem
\ref{thm:dd}) formed the basis for the search performed in
\cite{familiesofdesigns}.

\input{orbittheorem}

\begin{remark}
We wish to use this theorem to construct $2\text{-}(v,k,1)$
designs. Given a $k$-subset $L$ satisfying the design property,
we must ensure that $\lambda=1$ in the equations above. This gives us
$|L^G|\cdot\frac{b_i}{|O_i|}=1$. Since $b_i=\frac{|O_i|}{\hat{b}}$, this
gives $|L^G|=\hat{b}$. This makes sense, since for a
$2\text{-}(v,k,1)$ design, $\hat{b}=b$, the number of lines,
as shown in Lemma \ref{lemma:linesize}. By the Orbit Stabiliser
Theorem, this gives $|G_L|=\frac{|G|}{|L^G|}=\frac{|G|}{\hat{b}}$. This
gives us a second condition to check on $k$-subsets. The design
property combined with the extra condition that
$|G_L|=\frac{|G|}{\hat{b}}$ is called the \emph{orbit condition}.
\end{remark}

Given $v$, $k$ and $G$ and a $k$-subset of $\mathcal{P}$, $L$, the
Orbit Theorem is used in the following way to check the orbit
condition on $L$. We first calculate $\hat{b}=\frac{v(v-1)}{k(k-1)}$. We use
this to check that $|G_L|=\frac{|G|}{\hat{b}}$. If not, then $L$ cannot
generate a $2\text{-}(v,k,1)$ design. Next we
construct $O_1,O_2,\cdots,O_m$, the orbits of $G$ on the 2-subsets of
$\mathcal{P}$. Finally, for each $i=1,2,\cdots,m$, we
calculate $b_i=\frac{|O_i|}{b}$ and check that there are exactly $b_i$
2-subsets of $\mathcal{P}$ from $O_i$ contained in $L$ for each
$i=1,2,\cdots,m$.

Notice that if we are checking many $k$-subsets, we only need to
calculate $\hat{b}$, $b_1,b_2,\cdots,b_m$ and $O_1,O_2,\cdots,O_m$
once. Checking $|G_L|$ and the number of $2$-subsets per $k$-subset
per orbit are computationally simple, so this test can be performed
very quickly.


\section{Inner Pairs}\label{sect:innerpairs}

Although the Orbit Theorem makes the check on $k$-subsets simple for a
given $k$-subset,
there are almost always more $k$-subsets than can reasonably be
checked. As we will see in Chapter \ref{chapt:search} there may be in excess
of $10^{20}$ such subsets. This number cannot be searched given
current computing power.

We need some further conditions to narrow the $k$-subsets we need to
consider down further. The first condition arises from the work of
Delandtsheer and Doyen in \cite{dd}. It is based on conditions all lines
of a point imprimitive design must satisfy.

The Delandtsheer-Doyen Theorem primarily gives numerical conditions on
$v$ and $k$ based on a non trivial G-invariant partition on the
points.
This numerical condition is used by researchers in identifying
parameter sets.

As we see in the proof, one of the numbers involved in this condition
has a significance to the design that we can use in our search. In
order to see this, we introduce the concept of an inner pair.

\begin{definition}
Let $\mathcal{C}=\{C_1, C_2, \cdots ,C_d\}$ be a non trivial
partition on the points of
$\mathcal{D}=(\mathcal{P},\mathcal{L})$. Then an \emph{inner pair} on
a line $L\in\mathcal{L}$ is a 2-subset of points in $L$ contained
within the same class $C_i$. Any pair of points that is not an inner
pair is called an \emph{outer pair}
\end{definition}

The following theorem and its proof were the main result of \cite{dd}.

\begin{theorem}[Delandtsheer-Doyen]\label{thm:dd}
Let $\mathcal{D}=(\mathcal{P},\mathcal{L})$ be a 2-$(v,k,1)$ design and
G be an automorphism group of $\mathcal{D}$. Suppose there is a non-trivial
G-invariant partition $\mathcal{C}$ of the point set $\mathcal{P}$ with d
classes, each of size c. Then there exist $x,y\in\Z^+$ such that
\begin{equation}\label{eqn:dd}
c = \frac{{k\choose 2}-x}{y} \hbox{ and }
d = \frac{{k\choose 2}-y}{x}.
\end{equation}
As a result, since $v=cd$,
\begin{equation}\label{eqn:ddineq}
v\leq ({k\choose 2}-1)^2
\end{equation}
\end{theorem}

\begin{proof}
Since $G$ is line transitive, the number of inner pairs per line, and
hence the number of outer pairs per line, is constant. Let $x, n$
denote the number of inner and outer pairs per line respectively. Then
\begin{equation}\label{eqn:dd1}
x+n={{k}\choose{2}}
\end{equation}
and $x,n\ge1$ since any pair is contained in at least one line.
Consider the pairs $(\{p_1,p_2\},L)$ of an outer pair $p_1,p_2\in\mathcal{P}$
and a line $L\in\mathcal{L}$ with $p_1,p_2\in L$. By counting the
points first then the line, and the line first then the points, we see
that, if $b=|\mathcal{L}|$,
\begin{equation}\label{eqn:dd2}
bn={{d}\choose{2}}c^2.
\end{equation}
We know from Lemma \ref{lemma:linesize}, since $v=cd$, that
\begin{equation}\label{eqn:dd3}
b=\frac{cd(cd-1)}{k(k-1)}.
\end{equation}
From Equations \ref{eqn:dd1}, \ref{eqn:dd2} and \ref{eqn:dd3} we see
\begin{eqnarray*}
ncd(cd-1)&=&k(k-1){d \choose 2}c^2\\
nd(cd-1)&=&2{k \choose 2}\frac{d(d-1)}{2}c\\
n(cd-1)&=&{k \choose 2}(d-1)c\\
n(cd-1)&=&(x+n)cd-{k \choose 2}c\\
-n&=&xcd-{k \choose 2}c\\
\end{eqnarray*}
and hence
\begin{equation}\label{eqn:dd4}
{{k}\choose{2}}-dx=\frac{n}{c}.
\end{equation}
Set $y={{k}\choose{2}}-dx$. Then clearly $y\in\Z^+$.
% and the result follows from rearranging Equation \ref{eqn:dd4}.
Since $n={k\choose2}-x$, clearly $c=\frac{{k\choose2}-x}{y}$. Also, since
$y={{k}\choose{2}}-dx$ we have $dx={{k}\choose{2}}-y$ and hence $d=\frac{{{k}\choose{2}}-y}{x}$.
\end{proof}

We see then from the proof that $x$ in Equation \ref{eqn:ddineq} is
the number of inner pairs per line, with respect to the partition
$\mathcal{C}$.

The number of inner pairs tells us something about how many points
there are from a given line per class. Since there is nothing to
distinguish the classes in this information, it can at most tell us how
many classes contain a given number of points, not which class. We must
also note that this information is not necessarily unique. For
example, if $x=1$ then there is a unique inner pair. The only way this
can happen is if, for any given line, there is exactly one class
containing 2 points and all other classes contain either 1 or 0 points
from the line. However, if $x=3$ it may be that, for a given line,
3 classes contain 2 points each and all other classes contain 0 or 1,
or it may be that 1 class contains 3 points and all others contain 0
or 1 point. Notice 3 points in the same class gives ${3}\choose{2}$$=3$
possible 2-subsets and hence 3 inner pairs.

We formalise this information as an intercept vector for the
lines. This vector can be thought of as a list $[d_0, d_1,\cdots, d_n]$
where, for any line and each $i$, $d_i$ is the number of classes
containing $i$
points from that line. Since $G$ is transitive on the line set and
preserves the partition, this vector will be constant across all
lines. As with the permutation representation of $G$,
this vector may not be uniquely determined by the parameters
$(c,d,x,y,G)$, so we may need to search more than once, using a
different intercept vector each time.

\section{Symmetry}\label{sect:symmetry}

There is no more information gained by identifying a number of
isomorphic designs than by identifying one of those designs. Once a
design has been identified, we could if we
wished construct a number of isomorphic designs from it as a separate
exercise to the search. In order to reduce the amount of work that
must be done during the search, we only try to search for k-subsets
that will yield non-isomorphic designs.

We must be careful however to only consider isomorphisms that preserve
the automorphism group $G$ and its line transitivity and point
imprimitivity. It may be that a design with $G$ as an automorphism
group has an isomorphic design that does not admit $G$. In this case,
the isomorphic design does not conform to our search requirements and
should not be considered.

We may define an equivalence relation on $k$-subsets of $\mathcal{P}$
that satisfy the design property of Theorem \ref{thm:orbit} based on
isomorphism of designs. We will say two such sets $L_1$ and $L_2$ are
equivalent if there exists some $\pi\in \text{Sym}(\mathcal{P})$ such
that $(L_1^G)^{\pi}=L_2^G$. If $L_1$ and $L_2$ are equivalent and both
starter blocks, then it follows, by the definition of an isomorphism,
that the designs $(\mathcal{P},L_1^G)$ and $(\mathcal{P},L_2^G)$ are
isomorphic.

Note that given two $k$-subsets $L_1$ and $L_2$, it is very difficult
to decide if there is some element of Sym$(\mathcal{P})$ mapping
$L_1^G$ to $L_2^G$. We instead work with subgroups of
Sym$(\mathcal{P})$.

Clearly then, we would like to check as few $k$-subsets per
equivalence class as possible. We would like to identify some property
that only one, or at least very few, $k$-subset per equivalence class
has.

We first note that if two $k$-subsets are in the same $G$-orbit, then
the line sets generated by them will be equal and hence
the $k$-subsets are equivalent. We thus only need to check one
$k$-subset per $G$-orbit. At the basic level, we could note that $G$
is transitive on
points. We could pick some arbitrary point $\alpha$. Given any
$k$-subset $L$, we could take any point $\beta\in L$ and there would
be some $g\in G$ such that $\alpha=\beta^g$. Hence $\alpha\in
L^g$. Thus we only need to consider $k$-subsets containing $\alpha$,
since every equivalence class contains at least one such
$k$-subset. This is not using as much information as we have
however. Since, if $(\mathcal{P},\mathcal{L})$ is not a projective
plane and $G$ is line transitive, $G$ will never
%$G$ will rarely
be regular on $\mathcal{P}$, we may be able to
fix $\beta$ and move the remaining points around in some way. Ideally
we would like to fix as many points as possible, to narrow down as
much as possible the number of $k$-subsets to consider.

This argument has so far only considered $k$-subsets generating equal
line sets, which is much more restrictive than than `isomorphic' line
sets. We would like to use a similar argument with a group of
isomorphisms of the designs. The following lemma gives a method of
identifying such a group.

\begin{lemma}\label{lemma:symmetry}
Let $G$ be point imprimitive and block transitive on a
$2\text{-}(v,k,1)$ design
$\mathcal{D}=(\mathcal{P},\mathcal{L})$. Let $H$ be such
that $G\trianglelefteq H\le\rm{Sym}(\mathcal{P})$.
Then for any $h\in H$, the image of $\mathcal{D}$ under $h$,
$\mathcal{D}^h=(\mathcal{P},\mathcal{L}^h)$ is a $2\text{-}(v,k,1)$
design isomorphic to $\mathcal{D}$. Furthermore, $G$ is an automorphism
group of $\mathcal{D}^h$, and is point imprimitive and line transitive
on $\mathcal{D}^h$.
\end{lemma}

\begin{proof}
Let $\mathcal{M}=\mathcal{L}^h$. Then $\mathcal{M}$ is a
set of $k$-subsets of $\mathcal{P}$, since $h$ is 1-1. Also, since $h$
is 1-1 on points, it must be 1-1 on 2-subsets. Thus any two points
$p_1, p_2\in\mathcal{P}$ are the image of a unique pair $q_1,
q_2$. There is a unique line $L\in\mathcal{L}$ containing $q_1$ and
$q_2$ so it follows that $L^h$ is the unique line in $\mathcal{M}$
containing $p_1$ and
$p_2$. Hence $\mathcal{D}^h$ is a $2\text{-}(v,k,1)$ design. Since
$h\in\rm{Sym}(\mathcal{P})$ it is clear that $\mathcal{D}^h\cong\mathcal{D}$.

We now need to show $G\le\rm{Aut}\mathcal{D}^h$ and $G$ is point
imprimitive and block transitive. Take $M\in\mathcal{M}$ and $g\in
G$. Then $M=L^h$ for some $L\in\mathcal{L}$. Hence
$M^g=L^{(hg)}$. Since $G\trianglelefteq H$, we know $hG=Gh$ so $hg=g_1h$ for some $g_1\in G$. Thus
$M^g=(L^{g_1})^h\in \mathcal{L}^h=\mathcal{M}$. So $G$ maps lines to
lines. Hence $G$ is an automorphism group on $\mathcal{D}^h$. Line
transitivity follows from the same argument. Take $M_1,
M_2\in\mathcal{M}$. Then $M_1=L_1^h, M_2=L_2^h$ for some
$L_1,L_2\in\mathcal{L}$. Since $G$ is transitive on $\mathcal{L}$,
there is some $g\in G$ such that $L_1^g=L_2$ and since $gh=hg_1$ for
some $g_1\in G$ it follows $M_1^{g_1}=M_2$. Finally,
$h$ preserves the point set, so $G$ is still point imprimitive.
\end{proof}

So if we can find some subgroup of Sym$(\mathcal{P})$ containing $G$
as a normal subgroup, we have a group of isomorphisms that preserve the
transitivity and imprimitivity of $G$. We then need only search one
$k$-subset from each orbit of this new, larger group.

We refer to this process of narrowing down the subsets to search as a
symmetry argument, since we are looking at orbits under a group action.

\section*{Conclusion}
There are two steps in searching for point imprimitive line transitive
linear spaces. We have shown all such spaces must be $2$-$(v,k,1)$
designs, so the first step is identifying potential parameters $v$ and
$k$ and a group $G$. The second set is trying to identify a design with
these parameters.

We have seen the search for a design becomes a search for $k$-subsets
satisfying the conditions given by the Orbit Theorem and the
Delandtsheer-Doyen Theorem. Such a search would normally be impossible, due to
the large number of possible subsets. By identifying an overgroup of
$G$ that normalises $G$, we can apply a symmetry argument to reduce
the number of $k$-subsets to examine by a factor of the order of this group.

chapter4.tex
%auto-ignore
\chapter{Examples of Two Searches}\label{chapt:search}

\section*{Introduction}

In this chapter we will introduce two parameter sets identified by
other researchers. We will outline how the methods given in Chapter
\ref{chapt:designs} are applied to these parameter sets. The
information gained here will be applied in Chapter
\ref{chapt:algorithm} to construct a search algorithm.
%Finally, we
%will outline the method used to search for designs on these
%parameters.
Although neither of the sets yielded designs, the methods
used here can be applied to a wider class of parameters.
%with little modification.


\section{The Parameter Sets}
The first parameter set we examined arose from
\cite[Theorem 6]{praegertuan}. This was one of a very small number of
parameter sets satisfying an extra group theoretic condition, and
having parameter $x$ from Theorem \ref{thm:dd} small. It
has $v=451=41\cdot11$ and $k=10$. By this we mean the point set has
451 points and each line contains 10 points. As is often the case, the
group $G$ acting on the points is only very generally
described. However, we are given that there is a $G$ invariant
partition with 11
classes of 41 points each. Further, the subgroup $K$ of $G$ which
fixes, set-wise, every class $C$ of this partition is
isomorphic to $D_{82}$, the dihedral group on 41 points. The dihedral
group can be thought of as the group of symmetries - rotations and
reflections - of a 41-gon. A little more information about $G$ is
given, which will be discussed in the next section. We
will call this parameter set 1.

The second parameter set is very similar to set 1. After the search on
set 1 failed, the logical step is to try to identify what part of
the parameter information may have prevented it from yielding a
design. As we will see
in section \ref{sect:usingorbit}, the fact that $D_{82}$ acts irregularly on
the class $C$ restricts the possible starter blocks greatly. Recall
the definition of a regular action from Section
\ref{sect:actionprops}. If we
change $G$ so that $K$ acts regularly on $C$, it may increase the
possibilities for valid starter blocks. Recall a starter block, as
described in Section \ref{sect:orbitthm} is a 10-subset of the
point-set which satisfies the design property given in Theorem
\ref{thm:orbit}.

Parameter set 2 thus begins with similar assumptions to set 1. We have
$v=451$ and $k=10$. We suppose there is a $G$-invariant partition with
11 classes of size 41, such that the subgroup $K$ fixing every class
$C$ of this partition set-wise is isomorphic to
$\Z_{41}$, the cyclic group with 41 elements. This group acts
regularly on each class $C$. Once this relaxation of the conditions of
parameter set 1 had been made, it was
noticed that parameter set 2 had been identified as a possible parameter set by
the work of a group at UWA\footnote{This group was Betten,
Delandtsheer, Niemeyer and Praeger. No papers have yet resulted from
this work.}. Since it had been identified by two
separate processes, parameter set 2 seemed an interesting set to search.

We now have the basic information to start the search process for two
searches. As we saw in the previous chapter, there are several steps
to perform before a computer based search for designs can be done.

\section{The Permutation Group $G$}\label{sect:permrep}

The first important step in any design search is identifying explicit
possibilities for the group $G$ and its permutation representations on
$\mathcal{P}$. Without these representations,
the Orbit Theorem criteria cannot be applied, since it relies on
$G$-orbits. The work of identifying these possible representations was
performed by Niemeyer and Praeger and an outline will be given here.

The first step performed by Niemeyer and Praeger
\cite{niemeyerpraeger} on both parameter sets was showing there there
is a second $G$-invariant partition, having 41 classes of size 11. The
existence of one of these two partitions, under a line transitive
group, implies the existence of
both, so we can always use the information given by either. The partitions
are orthogonal, in the sense that the intersection of two classes from the
different partitions is a unique point. We can thus think of these
partitions as forming a grid structure over the points, having 11
columns and 41 rows. The first partition is the columns of the
grid, the second is the rows of the grid. We can see this in Figure
\ref{fig:grid}.

\begin{figure}
\begin{center}
\includegraphics[width=10cm]{partitiondiagram.eps}
\caption{The grid structure on the points.}\label{fig:grid}
\end{center}
\end{figure}

We require some labelling of the rows and columns to describe actions
on them. Label the rows $0,1,\cdots,40$ and the columns
$0,1,\cdots,10$. We will refer to the point in row $e$, column $f$ as
$(e,f)$. At this stage there is nothing to distinguish different rows
or different columns, so we may make this labelling arbitrarily. This
is an identification of the points with
$\Z_{41}\times\Z_{11}$. Performing this identification is sensible,
since we will see later that $\Z_{41}\times\Z_{11}$ acts regularly on
the points.
We will often require a total ordering on the points. We will
compare points by column first, then row. Define
$(e,f)\le(g,h)$ if $f<h$ or $f=h$ and $e\le g$.

Having this grid structure makes describing the $G$ action easier,
since we can describe the action of a group element by the way it permutes
the rows and the columns. For both parameter sets it is clear then
that $G\le \rm{Sym}(41)\times\rm{Sym}(11)$ since $G$ preserves the
rows and columns. In fact, it was shown
\cite{niemeyerpraeger} that for both parameter sets, $G\le
H=\rm{AGL}(1,41)\times\rm{AGL}(1,11)$.

The Affine General Linear group on $\Z_p$, AGL$(1,p)$ consists of all
affine maps $\Z_p\to\Z_p$. These are maps of the form $\gamma\mapsto
a\gamma+b$ for some $a,b\in\Z_p, a\ne0$. Notice then that
AGL$(1,p)\cong\Z_{p}\cdot\Z_{p-1}$. In this case we have
AGL$(1,41)$ acting on the rows and AGL$(1,11)$ acting on the columns
of our grid structure. If $a$ and $b$ are primitive elements of $\Z_{41}$
and $\Z_{11}$ respectively, we can construct $H$ from the following
generators:
\begin{itemize}
\item $\alpha$, addition by 1 to the row, so $\alpha:(e,f)\mapsto(e+1,f)$.
\item $\beta$, addition by 1 to the column, so $\beta:(e,f)\mapsto(e,f+1)$.
\item $a$, multiplication on rows, so $a:(e,f)\mapsto(ae,f)$.
\item $b$, multiplication on columns, so $b:(e,f)\mapsto(e,bf)$.
\end{itemize}

In both parameter sets, $G$ contains, as a normal subgroup, the group
of additions on the rows and columns, $N=\Z_{41}\times\Z_{11}$. We can
see that $N=\langle\alpha,\beta\rangle$. Notice, as noted above, that
$N$ acts regularly on $\mathcal{P}$, since $\Z_{41}$ acts regularly on
the rows and $\Z_{11}$ on the columns. Hence identifying the points with
$N$ is possible, as we saw in Lemma \ref{lemma:regularidentify}.

Niemeyer and Praeger showed that for parameter set 1,
$G\cong(D_{82}\times \Z_{11})\cdot\Z_5\cong N\cdot(\Z_{2}\times\Z_{5})$ and for
parameter set 2,
$G\cong(\Z_{41}\times \Z_{11})\cdot\Z_5\cong N\cdot\Z_{5}$. Although
this describes the overall structure of the group, it does not define
how $G$ acts on the points.

In order to construct $D_{82}$ we need an involution on the rows. This
will be a multiplicative element of order 2. Such an element is
$a^{20}$, since $a$ has multiplicative order 40. Notice that
$a^{20}\cong-1$ (mod 41).

In both cases, Niemeyer and Praeger showed that $\Z_5$ must act
non-trivially on both that rows and the columns, and that its
permutation representation would be
some subgroup of $\langle a^8\rangle\times\langle b^2\rangle$. Notice
$a^8$ and $b^2$ are multiplicative elements of order 5 of $\Z_{41}$
and $\Z_{11}$ respectively. There are six possible subgroups of this
group of order 5. They are $\langle a\rangle,\langle ab\rangle, \langle
ab^2\rangle,\langle ab^3\rangle,\langle ab^4\rangle\text{ and }\langle
b\rangle$. Notice that every of element $\langle a\rangle$  fixes every
column and every element of $\langle b\rangle$ fixes every row. These
groups are thus ruled out by the non-triviality condition. We are left
with four possibilities for the action $\Z_5$, this leads to 4
possible, non-isomorphic, groups. We will denote the group constructed
using $\langle a^8b^{2i}\rangle$ by $G_i$ for $i=1,2,3,4$.
Further, Niemeyer and Praeger showed that $G_i\ncong G_j$ for $i\ne
j$. We will not give a proof of this non-isomorphism here, but it can
be seen in Section \ref{sect:testing} that the four different groups
give different results during testing of our final
algorithm. Isomorphic groups would have given the same results.

Let us consider how to construct $G_i$ for parameter set 1. Once
again, let $a$ and $b$ be primitive elements of $\Z_{41}$ and
$\Z_{11}$ respectively. Then $G_i$ has 4 generators:
\begin{itemize}
\item $\alpha$, addition by 1 to the row, so $\alpha:(e,f)\mapsto(e+1,f)$.
\item $\beta$, addition by 1 to the column, so $\beta:(e,f)\mapsto(e,f+1)$.
\item $a^{20}$, the involution on rows, so
$a^{20}:(e,f)\mapsto(-e\text{ (mod 41)},f)$.
\item $a^8b^{2i}$, the order 5 multiplication on rows and columns
where $a^8b^{2i}:(e,f)\mapsto(a^8e,b^{2i}f)$.
\end{itemize}

Constructing $G_i$ for, parameter set 2 is very similar. The
difference between the two parameter sets is the involution on rows,
$a^{20}$. Hence the generators of $G_i$ for parameter set 2 are
$\alpha$, $\beta$, and $a^8b^{2i}$.

We denote by $N_{\rm{Sym}(\mathcal{P})}(G)$ the \emph{normaliser of
$G$ in Sym$(\mathcal{P})$}. This is the largest subgroup of
Sym$(\mathcal{P})$ that contains $G$ as a normal subgroup, and if
$G\unlhd M\le\rm{Sym}(\mathcal{P})$, then $M\le N_{\rm{Sym}(\mathcal{P})}(G)$.

\begin{lemma}
The normaliser of G in Sym$(\mathcal{P})$ is
$N_{\rm{Sym}(\mathcal{P})}(G)=H$.
\end{lemma}
\begin{proof}
Since $N\unlhd G$ and $N$ is the unique normal subgroup of order 451,
any element of Sym$(\mathcal{P})$ which normalises $G$ must normalise
$N$. It follows that
$N_{\rm{Sym}(\mathcal{P})}(G)\le N_{\rm{Sym}(\mathcal{P})}(N)$. By
\cite[Exercise 2.5.6, p45]{dixonmortimer} we know that the normaliser
of a subgroup $M$ of $\rm{Sym}(\mathcal{P})$ that is regular on
$\mathcal{P}$ is $M\cdot\rm{Aut}(M)$. We claim that
$\rm{Aut}(N)=\Z_{40}\times\Z_{10}$.

We know that
$\rm{Aut}(\Z_{41})=\Z_{40}$ and $\rm{Aut}(\Z_{11})=\Z_{10}$, both
acting by multiplication.
Given $\phi$, an automorphism of $\Z_{41}$ and $\psi$, an automorphism
of $\Z_{11}$, we can construct an automorphism of
$\Z_{41}\times\Z_{11}$ by $(e,f)\mapsto(\phi(e),\psi(f))$. Hence
$\Z_{40}\times\Z_{10}\subseteq\rm{Aut}(N)$. Now
suppose $\varphi\in\rm{Aut}(N)$. Since $\varphi$ is a group
automorphism, it must map any normal subgroup to another, isomorphic
normal subgroup. It follows, since gcd$(41,11)=1$, that
$\varphi(\Z_{41})=\Z_{41}$ and $\varphi(\Z_{11})=\Z_{11}$. Hence
$\varphi|_{\Z_{41}}\in\rm{Aut}(\Z_{41})$ and
$\varphi|_{\Z_{11}}\in\rm{Aut}(\Z_{11})$. It remains to show that
$\varphi=(\varphi|_{\Z_{41}},\varphi|_{\Z_{11}})$. Notice
$\varphi(e,f)=\varphi((e,1)(1,f))=(\varphi|_{\Z_{41}}(e),1)(1,\varphi|_{\Z_{11}}(f))=(\varphi|_{\Z_{41}}(e),\varphi|_{\Z_{11}}(f))$
as required. Hence $\varphi\in\Z_{40}\times\Z_{10}$, so
$\rm{Aut}(N)\subseteq\Z_{40}\times\Z_{10}$.

We see then that $N_{\rm{Sym}(\mathcal{P})}(G)\le
N\cdot(\Z_{40}\times\Z_{10})=H$. We will
show equality by proving $G\unlhd H$, since then it follows that $H\le
N_{\rm{Sym}(\mathcal{P})}(G)$.
It is known that if $N\unlhd G$ and $G\le H$ then $G\unlhd H$ if
$\frac{G}{N}\unlhd \frac{H}{N}$. Clearly $N\unlhd G$, and notice
$\frac{H}{N}\cong \Z_{40}\times\Z_{10}$, which is abelian. Any
subgroup of an abelian group is normal, so it follows then that
$\frac{G}{N}\unlhd\frac{H}{N}$ and hence $G\unlhd H$.
\end{proof}

We have now identified, for both parameter sets, all possible
groups $G$ which arise as permutation groups on $\mathcal{P}$. Before
applying the Orbit
Theorem (Theorem \ref{thm:orbit}), we will use the Delandtsheer-Doyen
Theorem (Theorem \ref{thm:dd}) to examine the
overall structure of a line in any possible design. We will see in
Section \ref{sect:usingorbit}
that this structural information will assist in applying the Orbit Theorem.

\section{Applying the Delandtsheer-Doyen Theorem}

Since the Delandtsheer-Doyen Theorem (Theorem \ref{thm:dd}) only uses
information about the $G$-invariant partitions, there is no difference
between its application to parameter set 1 and parameter set 2. We
will give here the argument used on both parameter sets.

On these parameter sets, the Delandtsheer-Doyen Theorem will be particularly
useful, since there are two different partitions to apply it to. We
will thus be given inner pair information for both the partitions. We
will see in Section \ref{sect:masks} that this information can be put
together to greatly restrict the possible $k$-subsets we need to
examine. We will call
the partition with 11 classes of size 41 (the columns) partition 1. Using the
notation of Theorem \ref{thm:dd}, we have $d_1=11,c_1=41$. The second
partition, the rows, we will call partition 2 and this gives us
$d_2=41,c_2=11$.

The application of this theorem will give us information about the
number of points from a given line in the same column or row. We will
use the notation $n$-row to denote a row containing $n$ points from a
given line and $m$-column to denote a column containing $m$ points
from a given line.

We wish to calculate the values for $x$ and $y$ in Equation \ref{eqn:ddineq}
for both partitions. We call these $x_1, y_1$ and $x_2, y_2$ for
the first and second partitions respectively. Since $c_1=d_2, c_2=d_1$
it is clear that $x_2=y_1, y_2=x_1$. We are only interested in $x$
values, so we will solve equation \ref{eqn:ddineq} for partition 1 to
get $x_1$ and $y_1$ and hence $x_2$.

This gives us $41=\frac{{{10}\choose{2}}-x_1}{x_2}$
and $11=\frac{{{10}\choose{2}}-x_2}{x_1}$, solving to $x_1=4$,
$x_2=1$. We thus know there are 4 inner pairs on the first partition,
the columns, and 1 inner pair on the second partition, the rows. This
gives us possible intercept vectors of $[4,5,1,1]$ or $[3,4,4,0]$ for
the columns and $[32,8,1,0]$ for the rows. Recalling the definition of
these vectors from Section \ref{sect:innerpairs} we can interpret these. There is
only one possibility for the rows. Given any line, there will be
thirty two
0-rows, containing no points from the line, eight 1-rows containing 1 point
from the line, and the remaining row will contain 2 points from the
line. There are two possibilities we must consider independently for
the columns. First it may be that given any line, there will be four 0-columns
containing no points, five 1-columns, one 2-column and
one 3-column. The other possibility is that given any line,
there will be three 0-columns, four 1-columns and four 2-columns. It
is important to recall that all lines in the
design will have the same intercept vector. We will thus search
separately for designs having the first intercept vector for columns
and designs having the second intercept vector for columns.

It is important to consider how the intercept vectors on rows and
columns will work
together. For example, when we have a column containing 3 points from
a line, how many points do the three rows containing these three
points each contain? For each new point along these rows, how many
points does its column contain? To answer these questions, we
introduce the idea of a mask in Section \ref{sect:masks}.

\section{Masks}\label{sect:masks}

A mask can be thought of as a general map of what any line in the
design will look
like. It is a picture of the line, with all points included, but
without the rows or columns being labelled. From the mask it is clear
how many rows or columns contain any given number of points from the
line, and how these rows and columns interact. The search can then be
run to find designs conforming to each different mask individually. At
present these masks are constructed manually and any information they
provide is given as input to the search. It is hoped that in the future a
program will be developed to perform the mask construction automatically,
but this is outside the scope of this dissertation.

Obviously there will be different masks for the two possible intercept
vectors on columns. Once we have constructed all possible masks across all
possible intercept vectors, there is no further need to differentiate
between the various intercept vectors. Different intercept vectors are
distinguished by the different masks they produce.
%This differentiation will
%occur within the differentiation between masks anyway.

In this search the construction of the masks is made simpler since
there is only one 2-row. Once we have
decided how many points are in the columns containing the two points
from the 2-row, all other points must be on 1-rows. This will
completely determine the mask.
The set of all possible masks for our parameter sets can be seen in
Figure \ref{fig:masks}.

\begin{figure}
\begin{center}
\includegraphics[width=10cm]{maskdiagram.eps}
\caption{The possible masks for either parameter set}\label{fig:masks}
\end{center}
\end{figure}

We consider first the intercept vector $[4,5,1,1]$ on the
columns. There are 4
possibilities for the 2-row. Firstly, its two points may each
lie on 1-columns. This gives us mask
1A. Second, one of the points in the 2-row might lie of a 2-column
and the other on a 1-column. This gives us mask 1B. Next, one point
may be on the 3-column, the other on a 1-column. This is mask
1C. Finally, one of the points may be on the 3-column, the other of
them a 2-column, which is mask 1D.

We now consider the second possible intercept vector,
$[3,4,4,0]$ on columns. Consider again the two points contained in the unique
2-row. It may be that both points are on 1-columns, which is mask
2A. Second, one point may be on a 1-column, the other on a
2-column, giving mask 2B. Finally, both points could lie on 2-columns,
giving mask 2C.

We see then that there are 7 possible masks for this search. This
narrows down the possibilities for starter blocks to be considered
considerably. Next we
will examine the Orbit Theorem's application and a symmetry argument
to narrow down these possibilities further.

\section{Using the Orbit Theorem}\label{sect:usingorbit}

We will need to treat the two parameter sets separately
when applying the Orbit Theorem (Theorem \ref{thm:orbit}). This
follows since the theorem involves the $G$-orbits of pairs of
points and the groups involved are different. Here we will give a
description of the $G$-orbits on 2-subsets
of points and see how many 2-subsets a starter block must have from
each orbit in each case. We will also see restrictions the theorem
places on the starter block in parameter set 1.

We begin by applying of the theorem to parameter set 1. Recall that we
must consider four groups $G$ separately. We
consider the $G$-orbits on 2-subsets of points. We know that $G$
preserves the rows and columns, it follows that there will be 3 different
types of orbits. There will be orbits where the points in the
2-subsets come from the same row but different columns, orbits where
the points come from the same column but different rows and orbits
where the points come from different rows and
columns. Given the small numbers involved in this example, the orbits
can be constructed computationally. The GAP code used to do this
computation is found in Appendix \ref{app:code}. From this computation
we find that, for each of the four groups $G$, there are 25 orbits on
2-subsets. Of these, 5 orbits, those
containing pairs of points from the same column or the same row, each contain
$\frac{|G|}{2}=2255$ pairs of points. The remaining 20 orbits each contain
$|G|=4510$ pairs. These are the 2-subsets from different rows and columns.

We are looking for linear spaces, so we require $\hat{b}=b$, using
$\hat{b}$ as defined in the Orbit Theorem and $B$ the number of lines.
Recall
$\hat{b}=\frac{v(v-1)}{k(k-1)}=\frac{451\cdot450}{10\cdot9}=451\cdot5=\frac{|G|}{2}$,
it follows from the Orbit Theorem (Theorem \ref{thm:orbit}) that each
starter block contains $\frac{|O_i|}{b}=\frac{2|O_i|}{|G|}$ 2-subsets
from orbit $O_i$. Thus a starter block must contain exactly one
2-subset from each of the first
5, smaller orbits and two 2-subsets from the remaining 20 orbits. This
gives us the orbit condition on 10-subsets to be checked during the
search. Moreover, we note that $|G_L|=\frac{|G|}{b}=2$. We use this
fact to gain further information about the masks.

\begin{lemma}\label{lemma:maskcondition}
For parameter set 1, the intercept vector on columns is [5,2,4,0] and
the mask is mask 2A of Figure \ref{fig:masks}.
\end{lemma}

\begin{proof}
Let $L$ be a valid starter block for a $2\text{-}(v,k,1)$ design
corresponding to parameter set 1. Note that a pair
of points will uniquely determine a line. Thus if $L$ is fixed, the
two points contained in its unique 2-row must also be fixed. Call this
2-subset
$S$. There are two elements of $G$ that will fix $S$, by the Orbit
Stabiliser Theorem (Theorem \ref{thm:ost}), since we know
$|S^G|=\frac{|G|}{2}$. We can see that one of
these elements must be the identity, $1$. The other will be an
involution from the normal subgroup $D_{82}$. We know every involution
in $D_{82}$ fixes
exactly one row and permutes the others in pairs. Let $j$ be the
involution which fixes the row containing $S$. We thus require the element
$j\in(D_{82}\times\Z_{11})\cdot\Z_{5}$ to
fix $L$ set-wise. We know it fixes the row containing $S$ and permutes
all other rows, but preserves all columns. Hence $j$ must fix all 11
points in the row containing $S$. With the exception of the
columns containing $S$ there can thus be no 1-columns. If there were,
the point in this column would be mapped to a different point in the
same column, which could not be in $L$, so $L$ would not be
fixed. This tells us $L$ can have at most two 1-columns. Hence its intercept
vector on the columns must be $[5,2,4,0]$. Also, since these two
1-columns must make up the 2-row, we are restricted to only using the
mask 2A of Figure \ref{fig:masks}.
\end{proof}

We have thus restricted the search on parameter set 1 to only one of
its seven previously possible masks. This argument tells us more than
just which mask we must use. We noted
that $j\in(D_{82}\times\Z_{11})\cdot\Z_{5}$
must fix the line $L$. For this element to fix $L$, the rows of the
2 points in any given 2-column are restricted. We need these rows to
be one of the pairs that $j$ alternates. There are 20 possible
pairs of rows and each of the four 2-columns must use a unique pair
from these 20.

We now look at parameter set 2. Applying the Orbit Theorem here is
much easier. From computational work in GAP, we find that, for each of
the four possible groups $G_i$, there are 45
orbits on 2-subsets of points, each containing 2255 subsets.In this
case, $b=2255=|G|$ and the Orbit Theorem implies that a starter block
contains exactly $\frac{|O_i|}{b}=\frac{|G|}{|G|}=1$ 2-subsets from
each $G$-orbit $O_i$ on $2$-subsets. Further, we require that for any
starter block $L$,
$|G_L|=1$. As above, not that if $L$ is fixed then $S$, the 2 points it
contains in its unique 2-row must also be fixed. However, since the
size of each orbit on 2-subsets is $|G|$, it follows that $|G_S|=1$
and hence $G_L|=1$ as required. We need place no further restrictions
on starter blocks to ensure that $\lambda=1$.

We have seen here how the Orbit Theorem is applied to our two
parameter sets. In each case, the information on the number of
2-subsets per orbit per line was easily obtained. In addition, a
tight restriction was found in Lemma \ref{lemma:maskcondition} on
starter blocks for parameter set 1. This
restriction means the search will be much easier and quicker to
perform, but also means the parameter set is much less likely to
produce a design. As we will see, this parameter set did not yield a
design. The change between parameter sets 1 and 2 was designed to remove this
restriction. The search on that parameter set will thus be longer, but
may be more
likely to yield a design.

\section{Symmetry Arguments}\label{sect:usingsymmetry}

So far in this chapter, we have built up necessary
and sufficient conditions for a given $10$-subset of $\mathcal{P}$ to
generate a $2\text{-}(451,10,1)$ design under our given group
$G$. However, in both
cases, the number of possible $k$-subsets we need to check is still far
too large for a search to be performed in realistic time. As we noted
in Section \ref{sect:symmetry}, we can greatly reduce the number of
10-subsets we need to consider by only considering one starter block
per equivalence class. We also saw that equivalence classes can be
generated by considering the orbits of $k$-subsets under some
group $M$ where $G\unlhd M$ and $M$ preserves the $G$-invariant
partition. Here we will construct such a group for both searches
and show how its orbit information may be used to restrict the
$k$-subsets we need to consider.

We noted in Section \ref{sect:permrep} that for both parameter sets,
$N_{\rm{Sym}(\mathcal{P})}(G)=H=\rm{AGL}(1,41)\times\rm{AGL}(1,11)$,
with the action of $H$ on $\mathcal{P}$ as defined there. Further,
$H$ is the largest possible subgroup of Sym$(\mathcal{P})$ for which
this is true. By Lemma \ref{lemma:symmetry} we can use the orbits of
$H$ on $10$-subsets as equivalence classes of 10-subsets of
$\mathcal{P}$ without losing any information in our search. Recall $H$
consists of multiplications and additions on rows and columns.

We consider for now only parameter set 1. By Lemma \ref{lemma:maskcondition},
any starter block corresponds to mask 2A in Figure
\ref{fig:masks}. This gives us a unique 2-row, both these points lying
in 1-columns, and four 2-columns. Further, we know that rows of the 2 points
in a given 2-column lie in one of 20 predetermined pairs. Suppose that
$L$ is a starter block. We wish to find a new starter block, $\hat{L}$
that is in
the same equivalence class as $L$ but has some extra known
properties. Consider first the unique 2-row of $L$. We can map this to
row 0 via some row addition in $H$. We now have a starter block, say
$L_1$ which has row 0 as its unique 2-row. From here, we can map one
of the points in the 2-row to column 0 via a column addition. This
addition will preserve all rows, so the 2-row is still in row 0. We
now have a starter block $L_2$, equivalent to $L$, containing the
point $(0,0)$ and some other point
in row 0. Suppose the column of this other point is $f\ne0$. Since
$\Z_{11}$ is a field, $f^{-1}\in\Z_{11}$ will map $f$ to
$1$ (the inverse of $f$ in $\Z_{11}$). So there is a column
multiplication in $H$ mapping this second
point to the point $(0,1)$. Furthermore, since multiplication fixes
$0$, this multiplication will preserve the point $(0,0)$. This gives
us a starter block $L_3$, equivalent to $L$ and containing $(0,0)$ and
$(0,1)$. Now consider the
'leftmost' of the four 2-columns. That is, the 2-column with the
lowest column number. This must be at least column 2 since we know
that columns 0 and 1 are 1-columns. We cannot perform a column
addition, or a column multiplication, since either of these would move
one or both of $(0,0)$ and $(0,1)$. Similarly, we cannot perform a row
addition, since both $(0,0)$ and $(0,1)$ would be moved. However,
since row multiplications fix row 0, we can perform a row
multiplication. We can thus map one of the points in this 2-column into
row 1. Since the rows come in known pairs, this will also determine the row
of the other point in this column to be $-1$. Call the result of
applying these operations $\hat{L}$. Clearly $\hat{L}$ is equivalent
to $L$, since we
have performed 4 operations from $H$.

We have seen through this that given any starter block $L$, there is
another starter block $\hat{L}$ that is equivalent to $L$, satisfying
the following conditions:
\begin{itemize}
\item $(0,0)\in\hat{L}$
\item $(0,1)\in\hat{L}$
\item If $f$ is the lowest number 2-column in $\hat{L}$, then
column $f$ contains the points in the rows corresponding to the
row-pair $1,40$.
\end{itemize}
It is thus sufficient to only consider potential starter blocks
satisfying these conditions.

Given these conditions, we see there are very few choices to make for
potential starter blocks in parameter set 1. First we choose 4 columns
from $\{2,3,\dots,10\}$ to be the 2-columns. The first of these has
its rows decided. For the rest, we need to choose, in order, 3 row
pairs of the remaining 19. This gives us
%$\frac{9\cdot8\cdot7\cdot6}{4!}\cdot19\cdot18\cdot17\approx800000$
${9\choose4}\cdot19\cdot18\cdot17\approx800000$
possibilities.

We now consider parameter set 2. We could consider each of the 7
different masks separately, performing a slightly different argument
for each. Instead, we will give a general argument that can apply to
any mask.

Again, take $L$ to be a potential starter block. We first consider
$L$'s unique 2-row. As before, perform a row addition to make this
2-row row 0. This gives us starter block $L_1$, equivalent to $L$. In
this case the columns
containing the points from the 2-row might not be 1-columns. Of the two
points, take the point whose column contains more points, or pick
one arbitrarily if they contain the same number. Using a
column addition, map this column to column $0$. This gives us line
$L_2$, which has row 0 as a 2-row and contains the point $(0,0)$. Now,
as before, perform a column multiplication to map the second point in
the 2-row to column 1. This gives us $L_3$, which contains the
points $(0,0)$ and $(0,1)$ and column 0 contains at least as many
points as column 1. Finally, take $f$ to be leftmost (lowest
numbered) column containing a point from $L_3$, excluding columns 0 and
1. Take some point from column $f$ which is in $L_3$. Perform a
row multiplication to map this point's row to row 1. This gives us
$\hat{L}$, which satisfies the following conditions:
\begin{itemize}
\item $(0,0)\in\hat{L}$
\item $(0,1)\in\hat{L}$
\item Column 0 contains at least as many points as Column 1.
\item Excluding the points $(0,0)$ and $(0,1)$, if $f$ is the
numerically earliest column occupied by $\hat{L}$, then $(1,f)\in\hat{L}$.
%Apart from $(0,0)$ and $(0,1)$, the numerically earliest point in $\hat{L}$ lies in row 1.
\end{itemize}

We see that there are many more choices to be made for a potential
starter block in parameter set 2.

\section{Results of the Searches}\label{sect:results}

We will not in this chapter consider the exact mechanism used in
performing these searches. This work will be covered in Chapter
\ref{chapt:algorithm}. We will however consider the outcome of these
searches here. For both parameter sets, no valid starter blocks
were found. This means, assuming the search procedure was correct,
an issue which we consider in Section \ref{sect:testing}, that there
can be no $2\text{-}(451,10,1)$ designs admitting either
$(\Z_{41}\times\Z_{11})\cdot\Z_{5}$
or $(D_{82}\times\Z_{11})\cdot\Z_{5}$ as a line transitive and point
imprimitive automorphism group, for any of the permutation
groups of this type defined in Section \ref{sect:permrep}.

\section*{Conclusion}

Here we have presented two possible parameter sets to search on. We
have shown that group theoretic arguments may be used on very little
information to construct all possible permutation
groups given in the parameter sets. In both of these cases, we found
there were four distinct permutation groups, so in both cases
four separate searches need to be performed. In these cases however,
the arguments to be made before searching were the same for all four
groups. The only difference in the searches between the groups is
their orbits on pairs, used for the Orbit Theorem requirements.

We have also introduced here the idea of a mask. Masks are useful when
there are two or more different $G$-invariant partitions on the
points. We first need to apply the Delandtsheer-Doyen Theorem (Theorem
\ref{thm:dd}) and calculate the
intercept vectors on each partition. After this has been done, the
masks give an overall picture of the interaction between the number of
points per class from each partition. Although, as we will see in
\ref{sect:algorithm}, this information is not used in this search, it
was particularly useful in our first parameter set, since we were able
to show that only one mask of 7 could possibly result in a design.

Finally here we presented symmetry arguments for both the parameter
sets. We saw that in both cases we were able to fix 2 of the 10 points
in a starter block, and restrict the row location of 1 or 2 more
points. This greatly reduces the number of sets we need to consider in
the search.

As a result of this work, a search for designs conforming to these two
parameter sets was run. In both cases the search returned a negative
result, indicating that no $G$-point imprimitive and $G$-line transitive
designs exist conforming to either parameter set.

chapter5.tex
%auto-ignore
\chapter{The Search Algorithm} \label{chapt:algorithm}

\section*{Introduction}

Here we present the search algorithm that has been developed and used
to search the second parameter set given in Chapter
\ref{chapt:search}. The algorithm used to search the first parameter
set is of less interest here, given the exceptional nature of the
conditions on starter blocks. Using these conditions, a brute force
search on 10-subsets satisfying the mask and row pair conditions outlined
in Section \ref{sect:usingorbit} is sufficient.

We will outline here the two separate computational parts of the
search. For the group theoretic computations GAP was used, since it
is very powerful in these areas. The raw combinatorial
computation was performed in C, since C is much faster than GAP for
such work. Throughout this chapter, we will assume we are working with
a given permutation group $G_i$ on $\mathcal{P}$ for
some $i=1,2,3,4$. For each  permutation group, the procedure is repeated.
A full copy of the source code used for these computations may be
found in Appendix \ref{app:code}.

In Section \ref{sect:permrep} we labelled a point $(e,f)$
where $e$ is  the point's row and $f$ its column. We numbered
the rows and columns 0 to 40 and 0 to 10 respectively. When
programming, it is more convenient to have points labelled by a single
integer. This integer can then be used to reference arrays and
lists. To this end, within GAP the point $(e,f)$ was numbered
$f\times41+e+1$ and within C it was numbered
$f\times41+e$. The reason for this slight difference is that
in GAP arrays are referenced to start at 1, in C they start at 0. When
the C code reads points in, it subtracts 1 and when it outputs points
it adds 1 to account for this. In this chapter we will consider the
GAP numbering system, so points are numbered 1 to 451.

Notice this gives us an obvious ordering on points, which is
equivalent to the column first then row ordering we considered in
\ref{sect:permrep}. We order the
points based on increasing numbering. This leads to a natural,
lexographic ordering of subsets of $\mathcal{P}$.

\begin{definition}\label{defn:setordering}
Let $A,B\subset\mathcal{P}$, where $A=\{a_1,a_2,\cdots,a_n\}$,
and $B=\{b_1,b_2,\cdots,b_m\}$, with $a_1<a_2<\cdots<a_n$ and
$b_1<b_2<\cdots<b_m$.
Then $A<B$ if there is some $i$ with $1\le i\le min\{n,m\}$ such that
$a_j=b_j$ for all $j=1,2,\cdots i-1$ but $a_i<b_i$, or if $n<m$ and
$a_j=b_j$ for all $j=1,2,\cdots n$.
\end{definition}

\section{Calculating Orbits On Pairs}\label{sect:calcorbits}

As we saw in Section \ref{sect:orbitthm}, the first step in
using the Orbit Theorem to search a parameter set is to calculate the
orbits of the given group $G_i$ on unordered pairs from the point set
$\mathcal{P}$. Once a group has been
constructed acting on a set, it is a simple matter to construct orbits
of given points. This step is almost identical for both parameter
sets. The only difference in the constructions is that $G_i$ in
parameter set 1 is generated by an additional involution.

In Section \ref{sect:permrep} we found four generators for $G_i$ for
parameter set 1. Recall these were $\alpha$, an addition by 1 to the
row, $\beta$ an addition by 1 to the column, $a^{20}$, multiplication by
$-1$ (modulo 41) on the row and $a^8b^{2i}$, a multiplication of order
5 on the rows and the columns.
These elements can all be constructed as permutations in GAP and hence
the group $G_i$ generated by them constructed as a permutation group on
$\Z_{41}\times\Z_{11}$ .
The construction of $G_i$ for parameter set 2 is the same, except the
generator $a^{20}$, the involution on rows, is omitted.

Once this group construction has been performed, the orbit containing
each 2-subset of points is calculated. The 2-subsets are represented
by $\{r,s\}$ where $1\le r< s\le 451$. The set of all 2-subsets are
traversed, one by one.
% At each step, if the orbit of the 2-subset is not known it is
%calculated and all points on that orbit have their orbit recorded. As
When considering a 2-subset of points, if its orbit is already known, it is
ignored. If the 2-subset's orbit is not known, it is calculated and
all points in that orbit have their orbit recorded.
As we saw in Section \ref{sect:usingorbit}, there are 25 orbits on parameter set
1 and 45 on parameter set 2. Of these, 5 of the orbits on parameter
set 1 contain 2255 points, the rest 4510 points. All the orbits on
parameter set 2 contain 4510 points. The orbits are denoted by
integers, 1 to 25 for parameter set 1 and 1 to 45 for parameter set 2.

This orbit information needs to be accessible by the combinatorial
search. The orbit numbers are outputted to a file where the orbit of
the 2-subset $\{r,s\}$ with $1\le r< s\le 451$ is stored in line $r$, entry
$s$. %This can then be read into an array in the C code. In order to
%avoid having to order pairs of points in the C code, the orbit number
%for all pairs $(r,s)$ with $r\ne s$ is recorded.

\section{Conditions on Starter Blocks}\label{sect:starterblockconds}

An important step in the application of the Orbit Theorem is working
out how many 2-subsets from a starter block come from each orbit. At
the present stage this calculation must be done by hand and the
results inputted to the search algorithm. This calculation was
discussed in Section \ref{sect:usingorbit}.

%We saw in Chapter \ref{chapt:designs} the two different
%conditions for a given $k$-subset to generate a design. In Chapter
%\ref{chapt:search} we developed these conditions for the two parameter
%sets we are searching.
There are two main
conditions that must be satisfied by starter blocks. First is the
orbit condition, given by the Orbit Theorem (Theorem
\ref{thm:orbit}). The second is the intercept vector condition given
by the Delandtsheer-Doyen Theorem (Theorem \ref{thm:dd}).
We base our search, as we will see in the next section, on checking
$q$-subsets, with
$q\le k$. We thus require some similar conditions that can be applied
to a $q$-subset of $\mathcal{P}$ in order for it to be contained in
some starter block.

Suppose we have $n$ orbits on 2-subsets, say $O_1,O_2,\cdots,O_n$, and
an orbit condition that
a starter block must contain $b_i$ 2-subsets from $O_i$ for
$i=1,\dots,n$, as given in Theorem \ref{thm:orbit}. Suppose also the
intercept vector condition on a given $G_i$-invariant partition
$\mathcal{C}$ is $[d_0,d_1,\dots,d_k]$. Recall by this we mean that
for each starter block $L$ there are $d_i$ classes of $\mathcal{C}$
containing exactly $i$ points from $L$, for $i=0,\dots,k$.

From these two conditions we develop the partial orbit condition and
the partial intercept condition.

\begin{definition}
A $q$-subset $A$, with $q\le k$ is said to
satisfy the \emph{partial orbit condition} if $A$ contains no more
than $b_i$ 2-subsets from the orbit $O_i$, for each $i=1,\dots,n$, and
$A$ is said to satisfy the \emph{partial intercept condition} if there are
not more than $d_i$ classes of $\mathcal{C}$ containing exactly $i$
points from $L$, for $i=0,\dots,k$.
\end{definition}

It is clear that if $A$ does not satisfy the two partial conditions
then $A$ cannot be extended to a starter block by the addition of
points.  Also, any starter block must also
satisfy the partial conditions. We refer to a $q$-subset satisfying the
partial conditions as a \emph{partial starter block}. Where we are
dealing with $q$-subsets that may or may not satisfy the partial
conditions, we will refer to them as \emph{partial blocks}.

In this search we have two partitions, the rows and the columns. The
intercept vector for the rows is $[32,8,1]$, giving us a unique
2-row. The symmetry conditions from Section \ref{sect:usingsymmetry}
fix the two points in this 2-row.
%the unique 2-row is included in the symmetry conditions, for all other
For adding all other
points we need only ensure there is at most one point per
row. There are two possible intercept vectors on the columns,
$[4,5,1,1]$ and $[5,4,2,0]$. Checking the columns partial intercept
condition is slightly more complex, so we introduce the column
information of a $q$-subset. This information is useful in testing
conditions on the columns.

\begin{definition}
Let $S$ be a $q$-subset of $\mathcal{P}$. The \emph{column
information} of $S$ is the tuple ColInf($S)=(c_0,c_1,\cdots,c_{10})$ where
ColInf$(S)_i=c_i=|S\cap(\text{column }i)|$.
\end{definition}

%Given a subset $S$ of $\mathcal{P}$ we let ColInf($S$) denote the
%column information of $S$, so that ColInf($S)_i=|S\cap\text{column
%}i|$.
This gives a way to check the partial column condition. We now require
$$|\{j\in\{1,2,\cdots,10\}|\text{ColInf}(S)_j=i\}|\le d_i \text{ for all }i\le k.$$

\section{The Algorithm}\label{sect:algorithm}

We consider now an algorithm to search for starter blocks on the point set
$\mathcal{P}$. We note that the intercept vector
condition is in fact two concurrent conditions for our search, since
there is an intercept vector on the rows and one on the columns to consider.

%The algorithm used here is an orderly one. An \emph{orderly algorithm} is one
%that checks all possibilities in a lexographic order. In this case,
%the possibilities are all $q$-subsets of $\mathcal{P}$,
%for all $q\le k$. The ordering we use is as described in Definition
%\ref{defn:setordering}.

The algorithm used here checks all possibilities for q-subsets of
$\mathcal{P}$ with $q\le k$ in a lexographic order. The ordering we
use is as described in Definition \ref{defn:setordering}.

The algorithm is defined recursively. At each stage in the algorithm,
we have a partial starter block $A$. If $|A|=k$ then $A$ is a starter
block, so the algorithm is complete and we can use $A$ to construct a point
imprimitive, line transitive design. Otherwise, we will try to add a
point to $A$ to create a new, larger partial starter block. There are
several pieces of information we will need to do this.

Input to the algorithm will be the parameters of the design, $v$ and
$k$, the column and row lengths, $c$ and $d$, the orbits on pairs
information for the given group $G_i$, the intercept vectors on
columns and rows, the initial partial starter block $I$ and any
additional symmetry conditions. This initial partial starter block
consists of all points that are known to be in any starter block,
according to the symmetry conditions.

In this search,
we have $I=\{1,42\}$, corresponding to the points $(0,0)$ and
$(0,1)$, as identified in Section \ref{sect:usingsymmetry}. As noted
earlier, these points make up the unique 2-row, so the row intercept
vector is simple. The orbit information will be as calculated in GAP,
as outlined in Section \ref{sect:calcorbits}.

In order to avoid checking the same subset twice, we maintain, for
each subset $A$, a set of points $Q$ which still need to be considered
for addition to $A$. Once a point has been added to $A$ and tested,
this point is removed from $Q$.

The recursive function is

%\begin{verbatim}
\noindent Funct($A$,$Q$)\newline
\hspace*{1cm}Input: $A,Q\subset\mathcal{P}$ with $|A|<k$.

\noindent\hspace*{1cm}WHILE ( $Q$ not empty )\newline
\hspace*{2cm}find $a=\text{min}(Q)$\newline
\hspace*{2cm}remove $a$ from $Q$.\newline
\hspace*{2cm}IF ( $A\cup\{a\}$ violates the partial row, partial column or symmetry
conditions )\newline
\hspace*{3cm}discard $a$\newline
\hspace*{2cm}ELSE\newline
\hspace*{3cm}Create $B=A\union\{a\}$\newline
\hspace*{3cm}\# We must be careful not to alter the original $A$.\newline
\hspace*{3cm}IF ( B passes the partial orbit condition )\newline
\hspace*{4cm}IF ( $|B|=k$ )\newline
\hspace*{5cm}$B$ is a starter block. Output $B$.\newline
\hspace*{4cm}ELSE\newline
\hspace*{5cm}make $P$ a copy of $Q$\newline
\hspace*{5cm}\# We need to copy $Q$ so that subsequent calls to \newline
\hspace*{5cm}\# Funct do not alter it.\newline
\hspace*{5cm}Funct($B$,$P$)\newline
\hspace*{2cm}\# If we reach this point, $B$ could not be extended to a
starter block.\newline
\hspace*{2cm}\#Try adding another point to $A$ from $Q$.\newline
\hspace*{1cm}END WHILE\newline
\hspace*{1cm}\# Here $Q$ is empty, so $A$ cannot be extended to a
starter block. \newline
\hspace*{1cm} Output `A cannot be extended to a starter block.'\newline
\noindent END Funct
%\end{verbatim}

This algorithm will be proved correct in Lemma \ref{lemma:correctness}
First we will make a few comments about the notation used in the
algorithm by running it on an example. Suppose $A$ is some set,
$Q=\{1,2\}$.
% and that $A\cup\{1\}$ and $A\cup\{2\}$ both satisfy the
%partial intercept conditions and the symmetry conditions,
We first consider appending $1$ to $A$. If we were to just make the
assignment $A=A\cup\{1\}$ then, when we consider appending $2$ to $A$,
we will get $A\cup\{1,2\}$. This is the reason for using a new name
for the partial block $B$.

Now suppose that $B=A\cup\{1\}$ passes all conditions. Suppose we were to
run Funct$(B,Q)$. This call would remove $2$ from $Q$ and try
$B\cup\{2\}$. If this set was to fail, we would return to trying to
add points to $A$. However, we have removed 2 from $Q$, so $Q$ is now
empty. The algorithm would terminate without ever checking
$A\cup\{2\}$. This is why we must make a copy of $Q$ for use in recursion.

\subsection{Checking Conditions within the Algorithm}
The heart of this function is testing if adding $a$ to $A$ would
violate the row or column conditions. The row condition is easy to
test; we need only make sure that $a$ does not belong to the row
of any point in $A$. To check the column condition, we first find $j$,
the column number of $a$ and $c=\text{ColInf}(A)$. We now construct a new
column information, $c'$ by
$$ c'_l = \left\{ \begin{array}{l l}
c_l &\text{if}\ l\ne j\\
c_l+1 &\text{if}\ l=j\\
\end{array}\right. .
$$
We can then check the column condition on $c'$, as described in Section
\ref{sect:starterblockconds}.

Checking the symmetry condition will vary between searches. In this
search, the only additional symmetry condition used is that the third
point in $A$ (which will be the first point added to $I$) must come
from row 1, as described in Section
\ref{sect:usingsymmetry}. We also saw in that argument that column 0
must contain more points than column 1. This condition was relaxed for
the search as it would not have had a significant effect on the total
time taken for the search, but it would increase its complexity.

We notice that the set of points to consider for addition to
 $B=A\cup\{a\}$
is copied from those of $A$. Doing this is valid. Clearly the set of
points to consider for B must be a subset of the original
$Q$. Furthermore, we need not consider any point from the original $Q$
 which has already been removed. If there was some $a'\in Q$ that had
 been removed, then $A\cup\{a'\}$ cannot be extended to a starter
 block. Clearly then, $B\cup\{a'\}=A\cup\{a,a'\}$ cannot be extended
 to a starter
 block. Thus there is no need to consider $a'$ being appended to $B$.
%Notice that
%$\text{max}(A)< \text{min}(Q)$, since if not the orderly condition
%would be violated - we should be considering $A$ before some other
%earlier set (the set $(A\setminus
%\text{max}(A))\cup\{\text{min}(Q)\}$). Since at each stage we only
%remove the smallest point from $Q$, it must contain all points greater than
%$\text{min}(Q)$ that need to be considered.

The algorithm is started with Funct($I$,$\mathcal{P}\setminus(\text{row
}0)$). The initial $Q$ is chosen as $\mathcal{P}\setminus(
\text{row }0)$ since we wish to consider
consider all points from $\mathcal{P}$, but $I$ already contains
two points from row 0 so no more points may be added from row 0.

\begin{lemma}[Correctness of Funct]\label{lemma:correctness}
Suppose that $A,Q\subset\mathcal{P}$ with $|A|<k$. Then:
\begin{enumerate}
\item\label{item:terminate} The Funct$(A,Q)$, as described above, will
terminate.
\item\label{item:alloutput} Funct$(A,Q)$ will output all starter blocks $L$
with $A\subset L\subset A\cup Q$.
\item\label{item:correctoutput} If $L$ is outputted by Funct$(A,Q)$ then
$L$ is a starter block and hence $(\mathcal{P},L^{G_i})$ is a
$2\text{-}(v,k,1)$ design that is $G_i$-point imprimitive and
$G_i$-line transitive.
\end{enumerate}
\end{lemma}

\begin{proof}
\ref{item:terminate}. The algorithm terminating follows since at each
recursive step we are reducing $|Q|$ by 1. Notice that $|Q|$ is
initially finite and each call of Funct performs at most $|Q|$ operations.

\ref{item:alloutput}. Suppose the claim is false. Then there exist $A,
Q\subset\mathcal{P}$ such that $A$ can be extended via $Q$ to a
starter block $L$, but Funct$(A,Q)$ does not output $L$. Notice
$|A|<k$ is bounded above. Let $k'<k$ be the maximum size of such an
$A$. Take $A,Q\subset\mathcal{P}$, such that $|A|=k'$ and $L$ is an
extension of $A$ via $Q$ with $L$ a starter block not outputted by
Funct$(A,Q)$.
Suppose $L=A\cup\{a_1,a_2,\cdots,a_m\}$, where $a_i\in Q$ for
$i=1,2,\cdots,m$ and $a_i<a_j$ for all $i<j$. We will show that $L$
must be outputted, a contradiction. Notice that the while loop in
Funct$(A,Q)$ considers each point from $Q$, since it only terminates
when $Q$ is empty. Also, since $A\cup\{a_1\}\subseteq L$, it is a
partial starter block. If $m=1$ then $A\cup\{a_1\}=L$ and hence $L$
will be outputted. Suppose $m>1$. Then the algorithm will call
Funct$(B,P)$, where $B=A\cup\{a_1\}$ and $P\subset Q$. Since
$a_2,a_3,\cdots,a_m>a_1$, we see that $\{a_2,a_3,\cdots,a_m\}\subset
P$. This follows since the algorithm removes points from $Q$ in
increasing order. Hence $L$ is an extension of $B$ via $P$. However,
$|B|=k'+1>k'$, so $L$ must be outputted by the algorithm, by the
maximality of $k'$. Hence, regardless of the value of $m$, the
algorithm will always output $L$, a contradiction. Thus Funct$(A,Q)$
will output all starter blocks $L$ with $A\subset L\subset A\cup Q$,
for all $A,Q\subset\mathcal{P}$.

\ref{item:correctoutput}. If $L$ is outputted by the algorithm, then
$|L|=k$ and $L$ is a partial starter block. Thus $L$ must
be a starter block and hence $L$ satisfies the orbit condition. It
follows, by the Orbit Theorem (Theorem \ref{thm:orbit}), that
$(\mathcal{P},L^G)$ is a $2\text{-}(v,k,1)$ design.
\end{proof}

\section{Testing the Search}\label{sect:testing}

Ensuring the search is running correctly is a difficult task, due to
the large number of possibilities it must consider. There are three
main areas where the search may fail due to human or computer
failure. The search may not traverse the space of partial starter blocks
correctly, and as a result fail to check some
possibilities. Secondly, the conditions, either orbit or intercept,
may pass false positive results, where a $q$-subset passes the
condition incorrectly. Finally, a condition may give false negatives,
where a partial starter block fails a condition when it should
have passed.

In order to check these conditions, the partial blocks of size 6 were
considered. Size 6 was chosen since, as we will see later, it is the
largest size for which the number of partial blocks we need to
consider is practical. If we were to try and consider partial blocks
of size 7, any output would quickly become larger than any realistic storage
media. It seems reasonable that if the algorithm is  performing
correctly on 6-subsets, it ``should'' be doing so at later stages in the
search. Unfortunately, this is as rigorous as testing can be.

\subsection{Testing the Intercept Vector Condition}

The traversal of partial starter blocks and the partial intercept
conditions are
closely related. The algorithm is written so that no block is
considered if it violates the partial intercept condition. In this case the
partial intercept condition is broken into two conditions, a row and a column
condition, which are checked independently.

Here we present the tests used when searching using the column
intercept vector $[4,5,1,1]$. The same tests we performed for the
vector $[5,2,4,0]$,
although the number of partial blocks outputted at each stage varied.

\begin{sublemma}
The number of 6-subsets of $\mathcal{P}$ satisfying the partial intercept
vector condition for vector $[4,5,1,1]$ and the symmetry conditions is
$15719080$.
\end{sublemma}

\begin{proof}
%Let $S$ be such a 6-subset of $\mathcal{P}$.
The set of all possible column informations of a 6-subset conforming
to the partial intercept vector conditions and the symmetry conditions was
generated. In order for the symmetry conditions to be satisfied, we
need at least one point each from columns 0 and 1. There were 380 such
column informations.
%It can be shown that there are 380 possibilities for the column
%information of $S$.
 Given a column information, we need only select a
row for each point to completely determine $S$. Of these 6 points, we
know the rows of 3 of them by the symmetry conditions given in Section
\ref{sect:usingsymmetry}. We know the subset must contain the points
$(0,0)$ and $(0,1)$ and that the next smallest point lies in row 1.
%Three points, namely
%(0,0), (0,1) and the lexographically earliest of the remaining points,
%already have their row determined.
This leaves 3 rows to
determine. There are 3 possibilities for these points. They may all
lie in the same row (i), 2 may lie in 1 row and 1 in a different row (ii) or
all 3 may be in different rows (iii). Of the 380 column informations,
210 correspond to case (i), 145 to case (ii) and 25 to case (iii).
For case (i) there are $\frac{39\times38\times37}{3!}$ possible
choices for the rows, in case (ii) $\frac{39\times38\times37}{2!}$
choices and in case (iii) $39\times38\times37$ choices. This gives us
$210\times\frac{39\times38\times37}{3!}+145\times\frac{39\times38\times37}{2!}+25\times{39\times38\times37}=15719080$
possibilities.
\end{proof}

%By a separate consideration, it was found that there are 15719080
%possible 6-subsets of $\mathcal{P}$ satisfying the row and column
%conditions. This calculation was performed in two sets. First the
%column information of these blocks was considered. Here by column
%information, we mean the number of points per column. This is distinct
%from the column intercept vector, which tells us how many column
%contain each number of points. The column information tells us column
%one contains $e_1$ points, column 2 $e_2$ points and so on. It was
%found that there are 380 different possibilities for this satisfying
%the intercept vector and the symmetry requirements. Given one of
%these, we know the first point in column 0 lies on row 0, the first
%point on column 1 lies on row 0 and the next earliest point lies on
%row 1. This completely determines the fist 3 points. There are thus 3
%more points which have a column assigned by no row. There are 3
%possibilities on these 3 points. They may all come from the same
%column, 2 many come from one column and one from another, or they may
%all be from different columns.
%We see in the first case there are $\frac{39\times38\times37}{3!}$
%possible choices for the rows, in the second
%$\frac{39\times38\times37}{2!}$ choices and in the last case
%$39\times38\times37$ choices. Matching these to the number of
%corresponding column informations gives the result of 15719080
%possibilities.

When the algorithm is run without the partial orbit condition and told to
output any 6-partial blocks it finds passing the partial intercept condition,
it outputs exactly 15,719,080 partial blocks. This shows us that the
algorithm is traversing correctly and that the partial intercept conditions
are being correctly checked.

\subsection{Testing the Orbit Condition}

Testing the orbit condition relies on this output of all possible
6-partial blocks and the output of 6-blocks found that also satisfy
the orbit condition. There were approximately 1,500,000 partial blocks
found that passed the orbit condition according to the search,
depending on the permutation group. The fact that these numbers were
different for each group shows us these groups are indeed not
isomorphic. First, these
blocks were passed into GAP, where the orbit condition was rechecked
using the orbit information calculated inside GAP, rather than the
data outputted by GAP earlier. All of these partial blocks passed the
orbit condition here, which tells us there were no false positives on
the orbit condition.

Next, the set of 6-subsets that passed the partial intercept condition
but not the orbit
condition was generated. This was done by finding the difference
between the output of all partial blocks and those found to pass the
orbit condition.
%Since the algorithm is orderly, both these outputs
%are lexographically ordered, so this difference can be calculated in
%linear time.
We ran through the list of partial starter blocks, removing each
from the list of all possible 6-subsets. Since both lists are ordered,
this can be done very quickly.
%The ability to do this in linear time is important given
%the large amount of data.
%This difference set also had the orbit
%condition checked in GAP, and none of the blocks passed. This tells us
%there are no false negatives on the orbit condition.
All subsets remaining after this process had the partial orbit condition
checked in GAP. None of these subsets passed this condition. This tells us
there are no false negatives on the partial orbit condition.

This phase of testing verified that the algorithm was working correctly
at a depth of 6. Although this does not tell us directly that the
algorithm will function correctly up to a depth of 10, where it will
terminate, it is good evidence that it will do so.

\subsection{Testing the Algorithm on a Known Example}

The final phase in testing was to test the algorithm on a different
parameter set that has known results.
We consider the Singer Cycle acting on the Desarguesian Projective
Plane of order 7, as described in Section
\ref{sect:lsexamples}. Notice that $7^2+7+1=57=19\times3$, so we know
there exists at least one such line transitive, point imprimitive,
projective plane. In fact, it has been shown \cite{bosenair} that the
Desarguesian Plane is the only projective plane of order 7 up to
isomorphism. The corresponding parameter set is
$v=57,k=7$ and $G=\Z_{19}\times\Z_{3}$ acting as addition on
3 rows and 19 columns. Although we do not consider the
projective planes to be useful results in the overall search for point
imprimitive, line transitive, linear spaces, this set is useful
here. In particular, the small size of the point set makes the search
very easy to run and to check. There were only two changes that needed
to be made to the search code to run this search. First, the group $G$
needed to be constructed differently in GAP, but then the same GAP
code was used for finding orbits on unordered pairs of
points. Secondly, the constants for the number of rows and
columns, as well as the length of a line and the number of orbits
needed to be altered in the C code. This search was then run, it
resulted in a single starter block being found, which generated a
projective plane of order 7.

\section*{Conclusion}

The algorithm we have outlined here
checks for starter blocks using a branch and cut traversal. Using
this, it is possible to search a large number of possibilities (in
this case of the order of 10 million) in a small time (here about 15
minutes). In most cases it is required to run the algorithm several
times, over each permutation group ($G_i$) and each intercept vector
on each $G_i$-invariant partition.

The algorithm used for this search is easily adaptable to a larger
class of searches. First we require two orthogonal $G$-invariant
partitions, treated as rows and columns as we have done here. If, in
addition, one of the Delandtsheer-Doyen parameters $x$ and $y$ is 1
and the unique inner pair on the corresponding partition has been
fixed by a symmetry argument, this algorithm can be used on the
search. In order to use the algorithm here, we need only
change some of the inputted constants, such as the number of orbits on
2-subsets, and the number of classes per partition.

%We present here a branch and cut algorithm for searching for starter
%blocks. The basic premise of the algorithm is that we put all
%possible $q$-subsets of $\mathcal{P}$ for $q\le k$ into a tree. We
%have $q$-subsets at level $q$ in the tree. We store the subsets as
%ordered sets. The inheritance condition in the tree is that node $A$
%is a child of node $B$ if $B$ lexorgrphically precedes $A$ and $A$
%and $B$ differ in exaclty one point. The algorithm traverses the tree
%in some ordered fashion, and if it ever reaches a node where no
%possible child of that node can be a valid starter block, it cuts the
%branch from that node out of consideration. Since all descendants of
%a node $A$ contain $A$ as a subset, it is clear that if the points of
%$A$ violate either the orbit condition or the intercept vector
%condition is violated by $A$ then that condition will be violated by
%any child of $A$. The cut condition is thus the same as the orbit and
%intercept conditions.

%We define our traversal of the tree resursively. We will consider
%points in numerical order, examining them column by column. At each
%stage in the recursion we will have a partial block $A$ and know the
%column currently in consideration. We wish to add a new point to $A$
%and test the new block $A\cup\{a\}$. If this new block is still
%valid, we will recurse to the next level in two different ways. First
%we will consider $A\cup\{a\}$ and stay in the same column, then we
%will consider $A\cup\{a\}$ but move to the next column. At each stage
%of recursion we will branch at all possible choices for the point $a$
%in the current column.

%The approach for this traversal is slightly different between the two
%parameter sets. Parameter set 1's traversal is simple, since the tree
%to be considered is relatively small, and the conditions in place for
%this search are very specific. The traversal for parameter set 2 is
%more complicated and more general, this is the algorithm that can easily be adapted for different parameter sets.

codeappendix.tex
%auto-ignore
\chapter{Code for Searching}\label{app:code}
\section{Parameter Set 2 - $(\Z_{11}\times\Z_{41})\cdot\Z_{5}$}

The following is a listing of the C code used to perform the search
for paramter set 2. The parameter set is described in Chapter
\ref{chapt:search}, the algorithm used for the search is described in
Chapter \ref{chapt:algorithm}.

The code resides in three files: orbitwork.g, containing the GAP code
to generate orbits on 2-subsets; design451.c, containing C code to perform
the search; and datastructures.c, defining the datastructures used in
the search. Detailed information about the internals of the data
structures used here is not important, so only the header file
datastructures.h is included.

\section{Running the Search}

The two parts of the search were run on different machines. The GAP
processing was performed in GAP4, running on an AMD K6-350, with 128MB
of RAM. The C processing was run on an AMD K6-200, with 128MB of
RAM. Both systems were running Red Hat Linux 7.0. For each intercept
vector and permutation representation, the C based search took 15
minutes to run. Generating the orbit information in GAP took 10
minutes for each permutation representation.

\pagebreak
\section{orbitwork.g}
\input{orbitwork.g}

\pagebreak
\section{design451.h}
\input{design451.h}

\pagebreak
\section{design451.c}
\input{design451.c}

\pagebreak
\section{datastructures.h}
\input{datastructures.h}

conclusion.tex
%auto-ignore
\chapter{Conclusion}\label{chapt:conc}

In this dissertation, we have examined the problem of identifying point
imprimitive, line transitive, linear spaces. We have see that this is
the same as identifying point imprimitive, line transitive,
$2\text{-}(v,k,1)$ designs, which is in turn equivalent to searching for
$k$-subsets of a set with cardinality $v$ satisfying certain
properties.

Using the two main theorems considered here, the Orbit Theorem and the
Delandtsheer-Doyen Theorem, in this manner is not new. These results
were applied in the identification of almost all known examples of
such designs which are not also projective planes. Using the
Delandtsheer Doyen Theorem across multiple partitions to construct
masks, which we introduced in Section \ref{sect:masks} is a new
approach to this problem. We saw here that in some cases, these masks
can be used to greatly reduce the number of subsets that need to be
considered.

Eight different groups acting on the same point set were examined. The
search performed was for $2\text{-}(v,k,1)$ designs on this point
set, admitting one of the eight possible permutation groups, as a line
transitive, point imprimitive,
automorphism group. It was shown that there are no such designs. As a
result, these groups and the resultant parameter sets can be removed
from consideration for future work.

Perhaps a more important result of this research is the algorithm used
to perform the search on the last four groups. This algorithm
can be used for a broader class of searches, any search where there
are two orthogonal invariant partitions on the points and where $x$,
the Delandtsheer Doyen parameter on one of those partitions, is 1.

The drive for future work in this area then is the identification of
groups acting on some point set such that a $2\text{-}(v,k,1)$
design is likely to exist, admitting the group acting point
imprimitively and line transitively.

cresp_thesis.tex
% Standard LaTeX header file for dissertations.
% compile (LaTeX) with
% latex uwadissert
%
% preview with
% xdvi uwadissert
%
% print with
% dvips uwadissert

% Document Class
\documentclass[11pt,a4paper]{report} % to save paper in drafts you may
                     % wish to choose ` 11pt' or `10pt'
                     % in place of `12pt'
\usepackage{uwamaths} % Standard Maths Department macros package ... see
                      % documentation via the TeX webpage.
\usepackage{rotating} % Useful for printing wide tables sideways.
\usepackage{prettyref}         % Makes \pref{sec:xxx} equivalent
\usepackage{anysize}
\marginsize{3cm}{3cm}{3.5cm}{3cm}
\newcommand{\pref}{\prettyref} % to: Section~\ref{sec:xxx} etc.
                               % ... see webpage under `nice packages'
\theoremstyle{slant}
\newtheorem{sublemma}[subsubsection]{Lemma}

\singlespacing    % In drafts you may wish to comment out this line.

\title{                                 % Set up title page information
                                        % used by \maketitle a bit later on
   Searching for Line Transitive, Point Imprimitive, Linear Spaces
   \thanks{Submitted in partial fulfilment
   of the requirements for the Bachelor
   of Science degree with Honours at The
   University of Western Australia}
}
\author{Gregory Cresp}

\date{October 2001}
%\date{\today} % alternative to above line gives current date (for drafts)

%\pagestyle{headings}   % Alternative style ... see LaTeX book
%\markright{}

\parskip=6pt % Puts some vertical space between paragraphs.
          % Remove or change as you like. Personally, I'd
          % use 6-8 pt for 12 pt text... but more can
              % help waste space! Stuart Allie 28/7/95.

%\includeonly{intro,chapter1,chapter2,chapter3,chapter4,chapter5}       % uncomment this and insert chapters you
              % are currently working on ... saves a lot of
              % compilation time ... see LaTeX book

\begin{document}      % Start the document.
\pagenumbering{roman} % Roman page numbering until we get to dissertation body.
\maketitle            % Make a title page.

\include{abstract}    % Good to have an abstract.
\include{acknow}      % Acknowledgements
                      % File acknow.tex should begin: \begin{acknowledgements}
                      %                  ... and end: \end{acknowledgements}
\setcounter{page}{3}
\tableofcontents \pagebreak

\singlespacing
%\listoftables         % Comment out if you have no tables
%\listoffigures        % Comment out if you have no figures
%\include{glossary}    % Optional - most dissertations won't have or need one.

% \include files are compiled separately - each starts on a new page;
%          and anything following starts on a new page.
% \input just reads text in.
% \include also allows the use of the \includeonly command (see above)
%          good for when you are working on a single chapter.
% The argument of an \input or \include command is the name of the latex
% file minus the .tex extension e.g. \include{abstract} to include
% abstract.tex

% body of dissertation

\pagenumbering{arabic}
\include{intro}
\include{chapter1}
\include{chapter2}
\include{chapter3}
\include{chapter4}
\include{chapter5}
\include{conclusion}
\appendix
\include{codeappendix}

%\nocite{*}              % BibTeX instruction ... uncomment to include all
             % .bib file references
\bibliographystyle{uwa}  % BibTeX instruction ... use style file: uwa.bst
             % benign if BibTeX not used
\bibliography{cresp_thesis}       % BibTeX instruction ... read: uwa.bib
             % Also tells LaTeX to read in the .bbl file
             % (uwadissert.bbl in our case) ... if it exists.
\end{document}

intro.tex
%auto-ignore
\chapter{Introduction}

\section{Introduction}
A finite linear space is a finite set of points and lines such that
any two points lie on a unique line. There are two properties of
particular interest of linear spaces, line transitivity and point
imprimitivity, which we will introduce in more detail in Chapter \ref{chapt:ls}.

We refer to maps on the space which preserve the line structure as
automorphisms.
A linear space is line transitive if it is so
symmetric that,
given any two lines, an automorphism exists which maps one of
these lines to the other. If there is a non-trivial partition on points
that is preserved by all
automorphisms, then the space is called point imprimitive. Transitive
and imprimitive are defined more rigorously in Chapter \ref{chapt:prelims}.

There is much interest in finding particular examples of point
imprimitive, line transitive finite linear spaces. There are many
projective planes (a particular class of linear spaces where any two
lines meet at a point) known to have these properties. We will
consider an infinite family of such planes in Section
\ref{sect:lsexamples}. However, there
are very few known examples of spaces having these properties that are
not projective planes. One point of interest here is whether those
examples that are known are in some way exceptional, or whether there
are many examples, but they have yet to be identified. In order to
answer this question, more information and more examples need to be found.

Designs are a class of algebraic objects satisfying very particular
requirements. Some designs are also linear spaces and these designs
form an easily identifiable subclass of all designs, which we will
see in Chapter \ref{chapt:designs}. One way of
finding linear spaces of the type required is to construct designs
which are linear spaces and satisfy the required properties.

One way to construct designs uses a result known as the Orbit
Theorem (Theorem \ref{thm:orbit}). This theorem shows that a design
can be constructed from a group action on a set if a subset of a
particular size can be found with particular properties. One approach
to this is to write a program to search for such a subset. The group,
set and some design parameters are the initial conditions of the
search. Usually, there are so many subsets of the desired size that to
check all of them would be impossible. Group theory, design theory and
combinatorics are used before and during the search to narrow down the
search space. Of particular interest is the Delandtsheer-Doyen Theorem (Theorem
\ref{thm:dd}), which gives further conditions on the subsets,
relating to any invariant partition on the point set. We will
introduce how these results may be used in Chapter \ref{chapt:designs}.

These approaches will be put into practise in Chapter
\ref{chapt:search}. We will introduce two type of group actions on 451 points
that were used in searches for designs. These searches were
completed, but unfortunately found no examples. However, they serve as
good examples of how the theory may be
applied, and eliminate these actions from further consideration. The
algorithm used to perform the second search is discussed in Chapter
\ref{chapt:algorithm}, where we see that the same algorithm may be
used for a wider class of searches.

orbittheorem.tex
%auto-ignore

\begin{theorem}[Orbit Theorem]\label{thm:orbit}
Let $v$, $k\in \mathbb{N}$ and let $\mathcal{P}$ be a set with
$|\mathcal{P}|=v$. Let G be a permutation group on $\mathcal{P}$ and
$O_1, O_2,\ldots ,O_m$
be the orbits of G on the $2$-subsets of $\mathcal{P}$. Let $L$ be a
k-subset of $\mathcal{P}$. Define $\hat{b}=\frac{v(v-1)}{k(k-1)}$ and for
each $i=1,2,\cdots,m$, define $b_i=|\{Y\in O_i:\ Y\subset L\}|$. Then
there exists $\lambda\in\mathbb{N}$ such that $(\mathcal{P},L^G)$ is a
$2\text{-}(v,k,\lambda)$ design if and only if the numbers
$\frac{b_i}{|O_i|}$
are equal for all $i=1,2,\cdots,m$. Furthermore, if these numbers
are all equal, then $b_i=\frac{|O_i|}{\hat{b}}$ for each $i$.
\end{theorem}

The property that $\frac{b_i}{|O_i|}$ is independant of $i$ is called
the \emph{design property} and subsets satisfying it are called
\emph{starter blocks}. Note that the quantity $\hat{b}$ is not, in
general, an integer. However, if $(\mathcal{P},L^G)$ is a
$2\text{-}(v,k,1)$ design, and hence a linear space, then $\hat{b}$
is, by Lemma \ref{lemma:linesize}, the number of lines in the space
and hence an integer.

\begin{proof}
%Let $\mathcal{P}$ be a set of cardinality $v$.
Suppose $\hat{L}$ is a $k$-subset of $\mathcal{P}$. Define
$\mathcal{L}:=\hat{L}^G=\{\hat{L}^g|\ g\in G\}$.
It is clear that for any
$L\in\mathcal{L},\ |L|=k\hbox{ and }b_i=|\{Y\in O_i:\ Y\subset L\}|$,
since G is transitive on $\mathcal{L}$ and $O_i$ is G-invariant.
We wish to determine the number of blocks that contain a given $2$-subset of
$\mathcal{P}$. Take some $i$ with $1\leq i\leq m$, then take $T_1,\ T_2\in O_i$.
Notice that since $O_i$ is G-transitive, there exists $g\in G$ such that
$T_1^g=T_2$. It follows that
$\{L\in\mathcal{L}|\ T_1\subset L\}^g=\{L\in\mathcal{L}|\ T_2\subset L\}$ and
hence $|\{L\in\mathcal{L}|\ T_1\subset L\}|=|\{L\in\mathcal{L}|\ T_2\subset L\}
|$.
Thus the number of blocks containing a given $2$-subset of
$\mathcal{P}$ is constant within $O_i$.
Define $\lambda_i:=|\{L\in\mathcal{L}|\ T_1\subset L\}|$ to be this number.
Now examine the set of pairs
$\{(L,T)|\ L\in \mathcal{L},\ T\in O_i,\ T\subset L\}$. If we
first select a block, then a $2$-subset from $O_i$ contained in that block, we
see there are $|\mathcal{L}|\cdot b_i$ such pairs. If we first select a
$2$-subset from $O_i$, then a block containing that subset, we see there are
$|O_i|\cdot\lambda_i$ pairs. Thus
\begin{equation*}
\lambda_i=|\mathcal{L}|\cdot\frac{b_i}{|O_i|}.
\end{equation*}
If $\hat{L}$ satisfied the design property,
$\frac{b_i}{|O_i|}$ is independant of $i$ and hence
$\lambda_i$ is independent of $i$. Thus we have a constant, call it $\lambda$,
such that any $2$-subset of $\mathcal{P}$ is contained in exactly $\lambda$
elements of $\mathcal{L}$. It follows that $(\mathcal{P},\mathcal{L})$ is a
$2\text{-}(v,k,\lambda)$ design.
Then, using the same argument used in Lemma \ref{lemma:linesize}, but
noting that any 2 points are contained in $\lambda$ lines, we see that
$\lambda\hat{b}=|\mathcal{L}|$.
Hence $\frac{b_i}{|O_i|}=\frac{\lambda}{\lambda\hat{b}}$, and thus
$b_i=\frac{|O_i|}{\hat{b}}$.

Conversely, suppose $(\mathcal{P},\mathcal{L})$ is a $2\text{-}(v,k,\lambda)$
design. Take $\hat{L}$ as above to be any block in
$\mathcal{L}$. Clearly then $\lambda_i=\lambda$ for each $i$ and hence
each $\frac{b_i}{|O_i|}=\frac{\lambda}{|\mathcal{L}|}$, which is
independant of $i$. Notice by the above argument, this common value is
$\frac{1}{\hat{b}}$. Thus any block satisfies the design property.

\end{proof}

cresp_thesis.bbl
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\begin{thebibliography}{10}

\bibitem{bosenair}
R.~C. Bose and K.~R. Nair,  `On complete sets of {L}atin squares',
  \emph{Sankhy\=a} \textbf{5} (1941), 361--382.

\bibitem{colbourne}
M.~J. Colbourn and C.~J. Colbourn,  `Cyclic {S}teiner systems having multiplier
  automorphisms', \emph{Utilitas Math.} \textbf{17} (1980), 127--149.

\bibitem{dd}
A.~Delandtsheer and J.~Doyen,  `Most block-transitive $t$-designs are
  point-primitive', \emph{Geom. Dedicata} \textbf{29} (1989), no.~3, 307--310.

\bibitem{dixonmortimer}
J.~D. Dixon and B.~Mortimer, \emph{Permutation groups} (Springer-Verlag, New
  York, 1996).

\bibitem{hughesandpiper}
D.~R. Hughes and F.~C. Piper, \emph{Design theory} (Cambridge University Press,
  Cambridge, 1985).

\bibitem{mills}
W.~H. Mills,  `Two new block designs', \emph{Utilitas Math.} \textbf{7} (1975),
  73--75.

\bibitem{2-729-8-1}
W.~Nickel, A.~C. Niemeyer, C.~M. O'Keefe, T.~Penttila, and C.~E. Praeger,  `The
  block-transitive, point-imprimitive $2$-$(729,8,1)$ designs', \emph{Appl.
  Algebra Engrg. Comm. Comput.} \textbf{3} (1992), no.~1, 47--61.

\bibitem{familiesofdesigns}
W.~Nickel and A.~C. Niemeyer-Nickel,  `Two families of block-transitive,
  point-imprimitive block designs', \emph{ANU Mathematical Sciences Research
  Centre Report} (1990), no.~SMS-022-90.

\bibitem{niemeyerpraeger}
C.~E. Praeger and A.~C. Niemeyer, \emph{Private Communication} (2001).

\bibitem{praegertuan}
C.~E. Praeger and N.~D. Tuan,  `Inequalities involving the
  {D}elandtsheer-{D}oyen parameters for finite line-transitive linear spaces',
  \emph{J. Combin. Theory Ser. A} \textbf{102} (2003), 38--62.

\end{thebibliography}
