This page gives the details and results of various computer classifications of partial spreads of lines in finite projective spaces, done by Leonard H. Soicher using the GRAPE package within the GAP system. In particular, as of 10 August 2000, the following have been classified (up to equivalence under the projective general linear group):
We include GAP/GRAPE log-files with this document. These explicitly give the partial spreads classified and their stabilizers, together with the commented GAP/GRAPE code used for the computations. These log-files should be of use both to finite geometers and to those seeking extended examples of the use of GRAPE. For the really impatient, the results are here.
Let V be an (n+1)-dimensional vector space over the finite field GF(q). The projective space PG(n,q) is the geometry whose elements are the subspaces of V, with two elements being incident if one is contained in the other. The points and lines of PG(n,q) are respectively the 1- and 2-dimensional subspaces of V. We identify a line with the set of points it contains.
A partial spread in PG(n,q) is a set of lines, no pair of which has a point in common.
A partial spread in PG(n,q) is maximal if it is not properly contained in any partial spread of PG(n,q).
A partial spread in PG(n,q) which forms a partition of the points of PG(n,q) is called a spread.
Two partial spreads in PG(n,q) are equivalent if there is an element of the projective general linear group PGL(n+1,q) mapping one to the other.
GRAPE is a GAP package for computing with finite graphs endowed with group actions. The GRAPE philosophy is that a graph gamma always comes together with a known subgroup A of the automorphism group of gamma, and then A is used to store gamma efficiently and to speed up computations with gamma.
To compute partial spreads in PG(n,q), we first use GRAPE to construct the graph gamma whose vertices are labelled by the lines of PG(n,q), with two vertices joined by an edge if and only if their corresponding lines have no point in common. The associated group gamma.group of automorphisms of gamma is PGL(n+1,q) in its permutation action on the lines of PG(n,q). Now the partial spreads in PG(n,q) are given precisely by the complete subgraphs of gamma, with maximal complete subgraphs giving maximal partial spreads. We determine the maximal complete subgraphs of gamma up to gamma.group-equivalence using GRAPE/GAP. We may then determine all complete subgraphs up to equivalence from the maximal ones. GAP is used to determine the stabilizer for each partial spread classified. Precise details of the computations are given in the log-files which follow. Note that the specialized computation for PG(3,7) is somewhat different.
We give the results as log-files of the computations in GAP/GRAPE. In these log-files, a point x in PG(n,q) is represented by the unique non-zero (row-)vector in (the 1-space) x having first (from the left) non-zero entry equal to 1. A line in PG(n,q) is represented by the set of points it contains. All of our classifications are up to equivalence of partial spreads, and for each partial spread s classified we give generators in PGL(n+1,q) for the stabilizer of s. These generators are given by their pre-images in GL(n+1,q). Matrices are printed as lists of their rows, and matrices act on the right. For readability we print an element in the prime field GF(p) as an integer i in the range 0,...,p-1 (so in a vector or matrix, the integer i represents i*One(GF(p)) in GAP, where p is the characteristic of GF(q)). The given runtimes are in CPU-milliseconds on a 350 MHz Pentium II PC running Linux.
The complete classification of partial spreads in PG(3,2) is here (this classification should be well-known). There is exactly one maximal partial spread (up to equivalence), and it has size 5.
The complete classification of partial spreads in PG(4,2) is here. This classification has been verified by hand and studied in: N.A. Gordon, R. Shaw and L.H. Soicher, Classification of partial spreads in PG(4,2), Mathematics Research Reports (University of Hull) XIII (2000), No.1. Here is an updated (2004) version of this report. There are exactly eight maximal partial spreads (up to equivalence): one of size 5, three of size 7, and four of size 9.
The complete classification of partial spreads in PG(3,3) is here. There are exactly three maximal partial spreads (up to equivalence): one of size 7 and two of size 10.
The complete classification of maximal partial spreads in PG(3,4) is here. There are exactly twenty-nine maximal partial spreads (up to equivalence): six of size 11, three of size 12, thirteen of size 13, four of size 14, and three of size 17.
Added 15 May 2002 (updated 16 July 2003): The above classification of maximal partial spreads in PG(3,4) has been used by Jungnickel and Storme to discover new maximal sets of MOLS of order 16. See: D. Jungnickel and and L. Storme, Maximal partial spreads in PG(3,4) and maximal sets of mutually orthogonal latin squares of order 16, Discrete Math. 261 (2003), 361-371. We further remark that the classification of maximal partial spreads in PG(3,4) can now be done much more quickly using the new version (4.1) of GRAPE, by using a new feature which allows the function CompleteSubgraphs to classify (maximal) cliques up to the action of the group associated with the graph input to that function.
The complete classification of maximal partial spreads in PG(3,7) of size 45 and invariant under a group of order 5 is here. There are exactly fifteen such partial spreads (up to equivalence).
Remark Olof Heden independently and earlier discovered a maximal partial spread of size 45 in PG(3,7), killing the conjecture that a maximal partial spread in PG(3,q) which is not a spread has size at most q2-q+2. It is not (yet) known whether his partial spread is invariant under a group of order 5.
Added 15 May 2002: Heden's discovery is now published in O. Heden, A maximal partial spread of size 45 in PG(3,7), Des. Codes Cryptography 22 (2001), 331-334. Amazingly, Andries Brouwer has since classified all maximal partial spreads of size 45 in PG(3,7).
A useful recent reference is: J. Eisfeld and L. Storme, (Partial) t-spreads and minimal t-covers in finite projective spaces, Lecture notes from the Socrates Intensive Course on Finite Geometry and its Applications, Ghent, April 2000.
Partial spreads in PG(3,q) are studied in Section 17.6 of the book: J.W.P. Hirschfeld, Finite Projective Spaces of Three Dimensions, Clarendon Press, Oxford, 1985, where, in PG(3,q), a partial spread of size k is called a k-span and a maximal partial spread of size k is called a complete k-span.
| Leonard Soicher's Home Page | Queen Mary Design Research Group | Design Resources on the Web |