Skip to content

There are no regular packings of PG(3,3) or PG(3,4)

December 1, 2012

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.

About these ads
6 Comments leave one →
  1. Tim Penttila permalink
    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.

  2. Tim Penttila permalink
    December 5, 2012 11:06 am

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

  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.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 38 other followers

%d bloggers like this: