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 
. We associate to each schoolgirl one of the fifteen points of , each row of schoolgirls with one of the 35 lines of , and each day with a partition of the points of into five lines; i.e., a spread of . A solution to the schoolgirl problem is then a set of 7 spreads, that form a partition of the lines of , otherwise known as a packing.
A packing of 
is
a partition of the 
lines of 
into 
spreads.
There exist two inequivalent packings of , 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 
for each prime power 
.
Regular packings and the result of Penttila and Williams
There is one particular spread of that is the most symmetric; the so-called regular spread of . If we take the 
points of the projective line 
and then blow-up the associated one-dimensional subspaces so that they become subspaces over 
, we arrive at mutually disjoint two-dimensional subspaces of 
yielding a spread of . A packing consisting only of regular spreads is called a a regular packing, and the two packings of are both regular packings. Lunardon attempted to prove in 1981 that regular packings do not exist when is odd, however, there is a flaw in his proof. Moreover, Prince (1998) discovered two regular packings of 
. In 1998, Blair Williams and Tim Penttila gave a construction of two families of regular packings of whenever is congruent to 2 modulo 3, and it subsumes all of the previously known examples of regular packings (including a construction by Denniston for 
).
Another way to view regular packings is to consider the Klein correspondence from the lines of to the points of the Klein quadric 
. A regular packing is then equivalent to a partition of the points of into 
elliptic quadrics.
A conjecture?
Perhaps it is too early to make the following conjecture?
A regular packing of exists if and only if 
.
Packings of 
and 
Gordon has been investigating all packings of , 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 . Here we have 357 lines and 24192 regular spreads; or alternatively, 357 points of 
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 
be the incidence matrix whose rows are the points of and whose columns are the solids that intersect in elliptic quadrics. Then a packing is just a column vector 
of 0′s and 1′s such that
where 
is the “all ones” vector. Moreover, the full collineation group of acts transitively on elliptic quadrics, and the stabiliser of one elliptic 
quadric has two orbits on elliptic quadrics disjoint from . So we can assume that the first coordinate of 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 
. In 
, there are 2850 lines and 2463426 regular spreads; a much harder computational problem.
Like this:
Like Loading...
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.
Also, Lunardon’s work was for q odd, not q prime.
Ta! Silly mistake has been amended …
Number of lines in PG(3,q) is wrong – should be (q^2+1)(q^2+q+1).
Thanks again!