A while ago, I used the mixed-integer linear programming software Gurobi to show that there are no Cameron-Liebler line classes with certain parameters, and recently I’ve looked at a similarly difficult computational problem: packings of 3-dimensional projective space. But first, some motivation.

## The Kirkman Schoolgirl problem

The “schoolgirl problem” posed by the Reverend Thomas Penyngton Kirkman in the Lady’s and Gentleman’s Diary of 1850, states:

“Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast.”

Cayley gave the first published solution to the problem, while Kirkman’s solution appeared in the Lady’s and Gentleman’s Diary of 1851. We can resolve the problem if we can settle the existence of a certain configuration in the projective space $PG(3,2)$. We associate to each schoolgirl one of the fifteen points of $PG(3,2)$, each row of schoolgirls with one of the 35 lines of $PG(3,2)$, and each day with a partition of the points of $PG(3,2)$ into five lines; i.e., a spread of $PG(3,2)$. A solution to the schoolgirl problem is then a set of 7 spreads, that form a partition of the lines of $PG(3,2)$, otherwise known as a packing.

A packing of $\mathbf{PG(3,q)}$ is

a partition of the $(q^2+1)(q^2+q+1)$ lines of $PG(3,q)$ into $q^2+q+1$ spreads.

There exist two inequivalent packings of $PG(3,2)$, and due to a result of Denniston (Some packings of projective spaces, 1972) and (independently) Beutelspacher (On parallelisms in finite projective spaces, 1974), there exists a packing of $PG(3,q)$ for each prime power $q$.

## Regular packings and the result of Penttila and Williams

There is one particular spread of $PG(3,q)$ that is the most symmetric; the so-called regular spread of $PG(3,q)$. If we take the $q^2+1$ points of the projective line $PG(1,q^2)$ and then blow-up the associated one-dimensional subspaces so that they become subspaces over $GF(q)$, we arrive at $q^2+1$ mutually disjoint two-dimensional subspaces of $GF(q)^4$ yielding a spread of $PG(3,q)$. A packing consisting only of regular spreads is called a a regular packing, and the two packings of $PG(3,2)$ are both regular packings. Lunardon attempted to prove in 1981 that regular packings do not exist when $q$ is odd, however, there is a flaw in his proof. Moreover, Prince (1998) discovered two regular packings of $PG(3,5)$. In 1998, Blair Williams and Tim Penttila gave a construction of two families of regular packings of $PG(3,q)$ whenever $q$ is congruent to 2 modulo 3, and it subsumes all of the previously known examples of regular packings (including a construction by Denniston for $PG(3,8)$).

Another way to view regular packings is to consider the Klein correspondence from the lines of $PG(3,q)$ to the points of the Klein quadric $Q^+(5,q)$. A regular packing is then equivalent to a partition of the points of $Q^+(5,q)$ into $q^2+q+1$ elliptic quadrics.

## A conjecture?

Perhaps it is too early to make the following conjecture?

A regular packing of $PG(3,q)$ exists if and only if $q\equiv 2\pmod 3$.

## Packings of $PG(3,3)$ and $PG(3,4)$

Gordon has been investigating all packings of $PG(3,3)$, and I will leave it to him to report on his work there, but along the way, he has shown that there are no regular packings in this space. So we turn to $PG(3,4)$. Here we have 357 lines and 24192 regular spreads; or alternatively, 357 points of $Q^+(5,4)$ and 24192 elliptic quadric sections. The latter will be my favourite way to view the problem. Now a covering problem such as this translates easily into a constraint satisfaction problem. Let $A$ be the incidence matrix whose rows are the points of $Q^+(5,4)$ and whose columns are the solids that intersect $Q^+(5,4)$ in elliptic quadrics. Then a packing is just a column vector $x$ of 0’s and 1’s such that

• $\sum x=21$
• $Ax=j$

where $j$ is the “all ones” vector. Moreover, the full collineation group of $Q^+(5,4)$ acts transitively on elliptic quadrics, and the stabiliser of one elliptic $E$ quadric has two orbits on elliptic quadrics disjoint from $E$. So we can assume that the first coordinate of $x$ is equal to 1, and that there are two programs arising from fixing one of two other coordinates to be 1. So I had two Gurobi programs to run, both returning “infeasible” after many hours of computation. The longest of the two jobs took 240 hours, ten days!

The next unknown case for the conjecture above is $q=7$. In $PG(3,7)$, there are 2850 lines and 2463426 regular spreads; a much harder computational problem.

December 5, 2012 10:39 am

The result for PG(3,3) was first proved by Alan Prince, Uniform parallelisms of PG(3,3), pages 193-200 in Geometry, combinatorial designs and related structures (ed. Hirschfeld, Magliveras and de Resmini), Proceedings of the 1st Pythagorean Conference held on Spetses, June 1-7, 1996, London Mathematical Society Lecture Note Series, 245, Cambridge University Press, Cambridge, 1997.

December 5, 2012 11:06 am

Also, Lunardon’s work was for q odd, not q prime.

• December 5, 2012 3:08 pm

Ta! Silly mistake has been amended …

January 23, 2013 9:00 am

Number of lines in PG(3,q) is wrong – should be (q^2+1)(q^2+q+1).

• January 23, 2013 9:22 am

Thanks again!

3. July 28, 2014 8:52 am

The same integer programming approach can possibly be used to determine which classical generalized hexagons of order q have ovoids (a set of points which intersects every line in exactly one point). By using an existing sage implementation of dancing links algorithm by Knuth I was able to determine this for q = 3 (there are 182 of them) but the computations for the dual split Cayley hexagon of order 4 were taking too long. My guess is that just like the case of q = 2, this dual wouldn’t have any ovoids.

Note that the non-existence of ovoids (of this kind) in a generalized hexagon imply that there are no semi-finite generalized hexagons containing that hexagon as a subgeometry.

• July 29, 2014 12:29 am

Correction: there are 3888 ovoids in H(3).

• July 29, 2014 9:35 am

Are you sure? I thought there was just one ovoid of $H(3)$ up to symmetry in $G_2(3)$, it’s stabiliser is $PSU(3,3):2$, and hence the number of ovoids in total is $|G_2(3):(PSU(3,3):2)|=351$.

4. July 29, 2014 10:25 pm

Yes. Note that I am talking about distance-2-ovoids here. I prefer calling them ovoids. Since each line intersect such an ovoid in exactly one point we can define them as binary solutions of $Ax = j$ where $A$ is the incidence matrix with rows indexed by lines. It can be checked computationally that there is exactly one ovoid of $H(3)$ up to symmetry in $G_2(3)$ with the stabilizer as the group $PSL(2,13)$. Or you can refer to http://cage.ugent.be/~hvm/artikels/132.pdf for a theoretical proof of this.

5. July 30, 2014 9:35 am

The standard is that ovoids are “distance-3-ovoids”, it’s not your choice mate. It’s confusing because a distance-2-ovoid is an $m$-ovoid where $m=1$! Anyway, as you say, there is a unique distance-2-ovoid of $H(3)$ up to symmetry, and its stabiliser is isomorphic to $PSL(2,13)$. So the total number of distance-2-ovoids here is $|G_2(3)| / |PSL(2,13)| = 3888$.

6. July 30, 2014 10:27 am

Sorry for the confusion. I gave the definition when I used the term in my first comment to avoid that.

I was not introduced to ovoids in a standard manner since the first I read about them was in context of polygonal valuations (http://www.sciencedirect.com/science/article/pii/S0012365X12004177) where it’s a bit natural to call distance-2-ovoids as simply ovoids. But yes, I guess I should try to stick to the more standard usage of the term.