Vacation research scholarship I

Over the summer break, Gordon and I each supervised a 2nd year undergraduate student in a research project. At UWA, the first course in group theory is in 3rd year, and we do not teach any combinatorics, so we needed to give each student a crash course before they could sink their teeth into a research problem. One of their outcomes was a blog post, and the first of these is by my student, who was also supervised by Sylvia Morris. His project was on “Sets of type (m,n) in projective spaces”.

Hello SymOmega readers! My name is Michael Martis, and I am a second year mathematics student here at UWA who applied for a research scholarship over the summer holidays. I was lucky enough to receive one, supervised by Dr. John Bamberg and a Ph. D. candidate Sylvia Morris. I’m writing this blog today to chronicle the course, and results, of my work over the last eight weeks or so.

In a finite projective space, a two-intersection set of type {(m, n)} is a collection of points that every hyperplane intersects in either {m} or {n} points. For instance, consider a line: every hyperplane either lies completely on the line (and hence intersects it at {q + 1} points), or meets it at one point. So the points of a line form a two-intersection set of type {(1, q + 1)}. There are plenty of more interesting two-intersection sets: the Hill-cap is a well known example consisting of 56 points in {\mathrm{PG}(5, 3)}. Aside from being fascinating objects in their own right, two-intersection sets have a number of useful properties. Firstly, and importantly for my project, they are amenable to computation. Moreover, there is a remarkable result (discovered by Delsarte in the early seventies) that links two-intersection sets to other mathematical objects: every two-intersection set gives rise to a two-weight linear code and a strongly regular graph. My research project involved enumerating an entire family of two-intersection sets in {\mathrm{PG}(5, 3)}.

In a finite projective space, a collineation is a “relabelling” of points that preserves lines (i.e. every set of collinear points must be mapped to a set of collinear points). Unsurprisingly, two collineations can be composed to form another collineation — groups of collineations can be built in this manner. In the past, John had noticed a peculiar fact: many “interesting” two-intersection sets in {\mathrm{PG}(5, 3)} were invariant under a specific collineation group (any Sylow 7-subgroup of the full collineation group, to be precise) – they could all be constructed by combining the points in certain orbits of this group. Moreover, it was known such two-intersection sets could be thought of as points in the Segre variety {\mathcal{S}_{2,1}}. We set out to completely explore this phenomenon: of the 52 orbits of the collineation group, we attempted to compute all subsets that give rise to two-intersection sets.

As we found out over the course of the holidays, this was no easy task. Our modus operandi was clear enough: John had previously used the mixed integer programming package Gurobi with success, so we chose to frame our search as a linear program. Doing so was fairly easy. We used the concept of an “orbit incidence matrix” – a matrix wherein the {(i, j)^{th}} entry was the number of points from the {i}th orbit incident with the {j}th hyperplane – and an “orbit inclusion vector” – a vector in which the {i}th entry was {0} or {1} depending on whether the {i}th orbit was excluded or included in the point set. We were looking for solutions to the following equation:

\displaystyle \textbf{x} \mathcal{M} = \left( \begin{smallmatrix} m \text{ or } n, & m \text{ or } n, & \ldots, & m \text{ or } n \end{smallmatrix} \right)

where {\mathcal{M}} is our orbit incidence matrix and {\textbf{x}} is an orbit inclusion vector. Although this was not quite a linear system, it was made into one without much hassle. For a given {\textbf{x}} solution, we defined another vector {\textbf{y}} wherein the {i}th entry was {0} or {1} depending on whether the {i}th hyperplane intersected {m} or {n} points. Finding all two-intersection sets was then equivalent to solving the following system of equations for {\textbf{x}}:

\displaystyle \textbf{x} \mathcal{M} + (n - m) \textbf{y} = \left( \begin{smallmatrix} m, & m, & \ldots, & m \end{smallmatrix} \right).

Finally, we used the great library nauty to scan the resulting orbit sets for isomorphism.

By extending results found by our own Prof. Gordon Royle and former staffer Prof. Tim Penttila, we were able to quickly sniff out viable parameter sets and were left with ten possible two-intersection values — a deceptively small number. Our naïve methods were enough to get through the first six or so, but the sheer size of the problem quickly started to get out of hand. We were finding plenty of solutions, but we were a long way away from a full enumeration. Our attempts at further optimisation met with limited success, and we briefly considered conceding defeat and changing targets to an easier collineation group. We were spurred on, however, by the remarkable results of our partial search. In one two-intersection value alone, we found over 500 unique sets, each of which gave rise to a new strongly regular graph! Given that the literature available listed maybe 20 known two-intersection sets, we felt that we had made quite an achievement and set our sights on publishing our results. These thoughts, however, were dashed by a new discovery. German mathematician Axel Kohnert had computed over 3000 two-intersection sets in {\mathrm{PG}(5, 3)}, which he had listed on his website, but left unpublished. Our roller-coaster of a research project continued: now our results would only be notable if we could fully enumerate our family of solutions – the very thing we were struggling to achieve.

Luckily, we happened to stumble upon a “silver bullet” of sorts. In a nutshell, we began to examine only those subsets that we absolutely had to, eliminating redundant computation. We came up with eight pairs of orbits: {\{ (1, 2), (1,3), (1,5), (1,6), (1,17), (1,18), (1,20), (1, 24) \}}. Using group theory, it was shown that any set of orbits was equivalent to a set of orbits containing one of these pairs. So, for a given set of orbits, we could find an equivalent set that contained either orbits 1 and 2, or orbits 1 and 3 or orbits 1 and 18, etc. As well as limiting our search to orbit sets that contained the given pairs, this had a huge advantage. Once we had found all orbit sets containing orbits 1 and 2, for example, we could exclude {\{1, 2\}} from appearing again in any further results. Not only could we exclude {\{1,2\}}, but we could exclude all of the other 52 pairs of orbits that were equivalent to {\{1,2\}}!

This kind of optimisation gave excellent results, but more was required – it still took weeks to find the two-intersection sets that included orbits 1 and 2. To speed up the process, we reapplied our successful strategy. More group theory was used to show that all orbit sets containing {\{1, 2\}} were equivalent to orbit sets containing either {\{1,2,3\}} or {\{1,2,5\}} or {\{1,2,24\}} etc. There were nine possible triples, in this example. So we “branched” our search in this manner whenever we found a case that was tough, sometimes going as deep as sextuples. Selectively applying computational power in this manner took our time-frame from weeks to hours and allowed us to successfully enumerate all two-intersection sets invariant under the given collineation group!

There was one other interesting fact about this collineation group, alluded to above, that helped motivate our research. A Segre embedding is a method of combining multiple projective spaces into one projective subspace of larger dimension. The image of such a map is called a Segre variety. We noted, and later proved, that the Segre map

\displaystyle \sigma([X_{1} : X_{2}], [Y_{1} : Y_{2} : Y_{3}]) = [X_{1} Y_{1} : X_{1} Y_{2} : X_{1} Y_{3} : X_{2} Y_{1} : X_{2} Y_{2} : X_{2} Y_{3}]

from {\mathrm{PG}(1, q) \times \mathrm{PG}(2, q)} to {\mathrm{PG}(5, q)} was a transversal of the orbits we have been discussing. That is, every orbit contained exactly one element of {\mathcal{S}_{2,1}} (the image of {\sigma}). To make the proof easier, we represented the projective space {\mathrm{PG}(5, q)} as the multiplicative group {\mathsf{GF}(q^6)^\times} over {\mathsf{GF}(q)^\times}. This meant that we had to transplant the concept of orbits, hyperplanes, and the Segre map into our new model. We knew that any element of order seven (there is only one, up to conjugacy) had orbits transversed by the Segre variety. Finding such an element proved to be easier than anticipated. We simply noted that seven divides {3^6 - 1}, the size of {\mathsf{GF}(q^6)^\times} over {\mathsf{GF}(q)^\times}. So {\omega^{52}}, where {\omega} is any primitive root of {\mathsf{GF}(q^6)}, was an element of order seven, and its orbits were equivalent to our orbits in {\mathrm{PG}(5, q)}. We chose the bilinear form {(x, y) \mapsto \mathsf{Trace}_{q^6 \rightarrow q}(xy)} as a “dot product” analogue, using it to test for point-hyperplane incidence. We also managed to prove that the multiplication map {(x, y) \mapsto xy} from {\mathsf{GF}(q^3)^\times \times \mathsf{GF}(q^2)^\times} to {\mathsf{GF}(q^6)^\times} was equivalent to the Segre map {\sigma}. These results allowed us to prove the relationship between our orbits and {\mathcal{S}_{2,1}} — we could now express two-intersection sets as corresponding point sets in the Segre variety. We are still investigating this relationship, particularly the geometric conditions, in the Segre variety, that are necessary or sufficient for the existence of two-intersection sets.

I haven’t mentioned everything we did over the last eight weeks: we also examined other projective spaces and converted our results into new strongly regular graphs. No wonder the project went overtime! Despite some frustrating days on the job, I am extremely grateful to have been given this opportunity, and would strongly recommend it to the mathematically inclined student out there. I came into this project not knowing what a group was, or what finite geometry could possibly be! The knowledge and experiences I have gained this summer are truly invaluable.


One thought on “Vacation research scholarship I

Add yours

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Up ↑

%d bloggers like this: