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.
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.