The packings of $\mathrm{PG}(3,3)$

Abstract

Packings of $\mathrm{PG}(3,q)$ are closely related to Kirkman’s problem of the 15 schoolgirls from 1850 and its generalizations: 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. The packings of $\mathrm{PG}(3,2)$ give rise to two of seven solutions of Kirkman’s problem. Here, we continue the problem of classifying packings of $\mathrm{PG}(3,q)$ by settling the case $q=3.$ We find that there are exactly 73,343 packings of $\mathrm{PG}(3,3)$.

1 Introduction and statement of results

A spread of $\mathrm{PG}(3,q)$ is a set of $q^2+1$ lines that are pairwise disjoint and hence partition the set of points. A packing of $\mathrm{PG}(3,q)$ is a set of $q^2+q+1$ spreads that are pairwise disjoint and hence partition the set of lines. Two packings are isomorphic if they can be mapped upon each other by a collineation of $\mathrm{PG}(3,q).$ For a survey of packings, see [12, 13], or the CRC handbook of combinatorial designs [4]. It is well-known that there are two packings of $\mathrm{PG}(3,2)$ (cf. [5]), each invariant under a group of order 168, and that one can be obtained from the other by applying the polarity associated to the standard bilinear form on ${\mathbb {F}}_q^4.$ For details, we refer to [10, Sect. 17.4]. The situation for $\mathrm{PG}(3,3)$ is examined in the present paper. Our result is the following:

Theorem 1

There are, up to isomorphism, 73,343 packings of $\mathrm{PG}(3,3).$

Some comments are in order: The packings in $\mathrm{PG}(3,2)$ were first observed by Cayley [3] and Kirkman [14], both in 1850, as solutions to Kirkman’s famous problem of the fifteen schoolgirls [15]:

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.

The first time that all seven solutions of Kirkman’s problem appear in print seems to be the 1922 paper by Cole [5], which also lists the automorphism groups of each object (but still does not mention any connection to geometry). The adaptation of Kirkmans problem to match packings in $\mathrm{PG}(3,q)$ for arbitrary $q$ can be found in Hirschfeld [10]:

If $(q^2 + 1)(q + 1)$ schoolgirls go walking each day in $q^2 +1$ rows of $q+1,$ they can walk for $q^2 +q+1$ days so that each girl has walked in the same row as has every other girl and hence with no girl twice.

Of course, here we are only interested in those solutions whose underlying design is that of points and lines in $\mathrm{PG}(3,q)$ and $q=3.$

How difficult is this problem? The space $\mathrm{PG}(3,2)$ has 15 points and 35 lines and there is up to isomorphism only one spread. The space $\mathrm{PG}(3,3)$ has 40 points and 130 lines, but there are two spreads to consider. Next in line is $\mathrm{PG}(3,4)$ with 85 points and 357 lines, and with three isomorphism types of spreads (cf. [6]). This information is summarized in Table 1. The three last columns of the table show the order of the stabilizer of the spread in the group ${\mathrm{P} \Gamma \mathrm{L}}(4,q)$, the order of ${\mathrm{P} \Gamma \mathrm{L}}(4,q)$ and the number of (labelled) spreads of this type. The number of labelled spreads is the quotient $|{\mathrm{P} \Gamma \mathrm{L}}(4,q)| / |S_{{\mathrm{P} \Gamma \mathrm{L}}(4,q)}|.$ As the table shows, the number of labelled spreads increases rapidly, making the problem much harder with increasing $q$. In this paper, we classify the packings of $\mathrm{PG}(3,3).$ Considering that there are over 5 million labelled spreads in $\mathrm{PG}(3,4)$, we believe that the classification of packings in $\mathrm{PG}(3,4)$ is out of reach at present.

Table 1 Spreads in $\mathrm{PG}(3,q)$ for small $q$

The packings in $\mathrm{PG}(3,3)$ have an extra structure which is due to the fact that there are two spreads in $\mathrm{PG}(3,3).$ For this reason, the packings of $\mathrm{PG}(3,3)$ can be classified by their type $(j,13-j)$ where $j$ is the number of Desarguesian spreads and $13-j$ is the number of Hall spreads. Information about the packings for any given type is given in Table 2. Moreover, information about the automorphism groups and their action on the set of spreads is presented in Table 3. Information about the self-polar packings is listed in Table 4, while the polar pairs are listed in Table 5.

Table 2 The packings of $\mathrm{PG}(3,3)$

Table 3 The groups of some of the packings of $\mathrm{PG}(3,3)$

Table 4 The self polar packings of $\mathrm{PG}(3,3)$

Table 5 The pairs of packings of $\mathrm{PG}(3,3)$ that are polar to each other

The remainder of this paper is devoted to a proof of this result. The structure of the paper is as follows. In Sect. 2, we give the theoretical underpinnings for our classification algorithm. In Sect. 3, we describe the classification algorithm in the most basic form. A refinement is presented in Sect. 4, using the lexicographic ordering. In Sect. 5, we discuss the way in which packings are created from subobjects. In Sect. 6, we make some comments on the algorithm and we compare our results with earlier work.

2 Methodology

Most classification algorithms proceed along a chain of “subobjects.” The subobjects serve as a stepping stone towards the classification that one wishes to achive. The subobjects are classified and extended to larger subobjects. If this process is repeated sufficiently often, the target objects will be classified eventually. Our approach is based on an old idea of Schmalz [23, 24], who introduces a data structure to store “local” isomorphisms. This eliminates the need for backtracking. Our algorithm is explained in more detail and with more examples in [2].

To explain the method of classification used in this paper, let us start by fixing some notation. Most of this is standard, but the presentation here is somewhat more detailed than that of other sources.

Let ${\mathcal {Y}}$ denote the objects that we wish to classify (the target objects). Let $G$ denote the symmetry group, i.e., a group acting on ${\mathcal {Y}}$, the orbits of which we call isomorphism classes. Assume that there is a class of subobjects ${\mathcal {X}}$, also acted upon by $G$, and that the relation ${\mathcal {R}} \subseteq {\mathcal {X}} \times {\mathcal {Y}}$ is $G$-invariant.

The idea is to choose subobjects in such a way that they are “easy” to classify but “sufficiently large” so that the target objects related to a given subobject can be computed efficiently. For terminology (and notation) regarding finite group actions, we refer to Wielandt [26].

If $X \in {\mathcal {X}},$ let

$$\begin{aligned} \mathrm{Up}(X) = \{ (Z,Y) \in {\mathcal {R}} \mid Z = X \} \end{aligned}$$

the up-set of $X$. If $Y \in {\mathcal {Y}},$ let

$$\begin{aligned} \mathrm{Down}(Y) = \{ (X,Z) \in {\mathcal {R}} \mid Z = Y \} \end{aligned}$$

the down-set of $Y$. Observe that both the up-set and the down-set consists of pairs of elements from the relation ${\mathcal {R}}.$

The group $G_X$ acts on $\mathrm{Up}(X)$, and the orbits are called up-orbits. Likewise, the group $G_Y$ acts on $\mathrm{Down}(Y)$, and the orbits are called down-orbits. Now assume that we have representatives $P_1,\ldots , P_m$ of the $G$-orbits on ${\mathcal {X}}$, as well as representatives $Q_1,\ldots , Q_n$ of the $G$-orbits on ${\mathcal {Y}},$ so that

$$\begin{aligned} {\mathcal {X}} = \bigcup _{i=1}^m P_i^G \quad \text{ and } \quad {\mathcal {Y}} = \bigcup _{j=1}^n Q_j^G. \end{aligned}$$

Let $T_{i,1}, \ldots , T_{i,m_i}$ be representatives for the orbits of $G_{P_i}$ on $\mathrm{Up}(P_i),$ with ${\mathcal {T}}_{i,a} = T_{i,a}^{G_{P_i}}.$ These orbits are called the up-orbits associated with $P_i$. Let $S_{j,1}, \ldots , S_{j,n_j}$ be representatives for the orbits of $G_{Q_j}$ on $\mathrm{Down}(Q_j),$ with ${\mathcal {S}}_{j,b} = S_{j,b}^{G_{Q_j}}.$ These orbits are called the down-orbits associated with $Q_j.$ Thus we have

$$\begin{aligned} \mathrm{Up}(P_i) = \bigcup _{a=1}^{m_i} {\mathcal {T}}_{i,a} = \bigcup _{a=1}^{m_i} T_{i,a}^{G_{P_i}} \quad \text{ and } \quad \mathrm{Down}(Q_j) = \bigcup _{b=1}^{n_j} {\mathcal {S}}_{j,b} = \bigcup _{b=1}^{n_j} S_{j,b}^{G_{Q_j}}. \end{aligned}$$

Let

$$\begin{aligned} {\mathfrak {T}}_i = \{ {\mathcal {T}}_{i,a} \mid a = 1,\ldots ,m_i \} \end{aligned}$$

and

$$\begin{aligned} {\mathfrak {S}}_j = \{ {\mathcal {S}}_{j,b} \mid b = 1,\ldots ,n_j \}. \end{aligned}$$

Finally, let

$$\begin{aligned} {\mathfrak {T}}= \bigcup _{i=1}^m {\mathfrak {T}}_i \quad \text{ and }\quad {\mathfrak {S}}= \bigcup _{j=1}^n {\mathfrak {S}}_j. \end{aligned}$$

We have:

Lemma 2

([1, Lemma1]) There is a canonical bijection $\psi$ between the sets ${\mathfrak {T}}$ and ${\mathfrak {S}}$. That is, each orbit in ${\mathfrak {T}}$ is paired with exactly one orbit from ${\mathfrak {S}}$ (and conversely). In particular, the sets ${\mathfrak {T}}$ and ${\mathfrak {S}}$ have the same size.

We remark that the canonical bijection $\psi$ comes from the action of $G$ on the flags (incident pairs) of the relation ${\mathcal {R}}$. The orbits of this action are in bijection to both the elements of ${\mathfrak {T}}$ and the elements of ${\mathfrak {S}}.$ For our purposes, ${\mathcal {Y}}$ is the set of packings of $\mathrm{PG}(3,q)$, $G$ is the group $\mathrm{PGL}(4,q)$, and ${\mathcal {X}}$ is the set of $k$ pairwise line-disjoint spreads, where $k$ is some parameter that can be chosen. The up-set of a set of $k$ disjoint spreads is the set of packings containing these $k$ spreads. The down-set of a packing consists of all $k$-subsets of spreads chosen from the packing.

We define the classification graph

$$\begin{aligned} \Gamma _{{\mathcal {X}},{\mathcal {Y}},G} \end{aligned}$$

to be the following bipartite multigraph on $m+n$ vertices. The vertices are the elements of the sets $\{P_1,\ldots ,P_m\}$ and $\{Q_1,\ldots ,Q_n\},$ with an edge between $P_i$ and $Q_j$ whenever there is a ${\mathcal {T}}_{i,a}\in {\mathfrak {T}}_i$ and an ${\mathcal {S}}_{j,b} \in {\mathfrak {S}}_j$ with $\psi ({\mathcal {T}}_{i,a})= {\mathcal {S}}_{j,b}.$ This graph is a multigraph as there may be multiple choices for $(a,b)$ for a given $(i,j).$

Let us now look at the lifting and classification in some more detail. The set ${\mathcal {X}}$ is the set of all subobjects. The set ${\mathcal {Y}}$ is the set of target objects. The relation ${\mathcal {R}}$ is inclusion. The symmetry group $G$ acts on ${\mathcal {R}}$. In the beginning, the classification of $G$-orbits on ${\mathcal {X}}$ is computed. This means that the representatives $P_1,\ldots ,P_m$ are listed, together with their stabilizer groups. In the next step, the lifting step, the sets $\mathrm{Up}(P_i)$ are computed for $i=1,\ldots ,m,$ and the up-orbits ${\mathfrak {T}}_i$ are determined using the action of the groups $G_{P_i}$. This means that we know representatives $T_{i,a}$ with ${\mathcal {T}}_{i,a} = T_{i,a}^{G_{P_i}}$ for $a = 1,\ldots , m_i.$ In the classification step, the $Q_1,\ldots ,Q_n$ are computed. This is done by establishing the pairing $\psi .$ For more details on the liftings, see Sect. 5. For more details on the classification, see Sect. 3, and its refinements in Sect. 4.

The present problem requires us to look at the group $G=\mathrm{PGL}(4,q)$ acting on $\mathrm{PG}(3,q).$ We define a partial packing of size $k$ in $\mathrm{PG}(3,q)$ to be a set of $k$ pairwise disjoint spreads. Thus, a packing is a partial packing of size $q^2+q+1$. Recall that we let ${\mathcal {X}}$ be the set of partial packings of size $k$ for some small value of $k$, and we let ${\mathcal {Y}}$ be the set of packings of $\mathrm{PG}(3,3)$ (i.e., the partial packings of size 13). The problem of computing the up-set $\mathrm{Up}(X)$ for a partial packing $X \in {\mathcal {X}}$ will be addressed in Sect. 5. Computing $\mathrm{Down}(Y)$ for a packing $Y \in {\mathcal {Y}}$ is trivial: simply consider the ${q^2+q+1 \atopwithdelims ()k}$ subsets of partial packings consisting of exactly $k$ of the spreads in $Y$.

3 The basic Schmalz algorithm

We use Lemma 2 to compute the transversal of $G$-orbits on ${\mathcal {Y}},$ assuming that the transversal $P_1,\ldots ,P_m$ of $G$-orbits on ${\mathcal {X}}$ has been computed. The algorithm is best described in terms of the graph $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}.$ Recall that this graph has two classes of vertices. The first class is the orbits of $G$ on ${\mathcal {X}}$. The second class is the orbits of $G$ on ${\mathcal {Y}}$ (as yet unknown). We often identify the vertices with the orbit representatives $P_i$ and $Q_j$, respectively. The edges of the graph correspond to pairs of elements from ${\mathfrak {T}}$ and ${\mathfrak {S}}$ that correspond under the bijection $\psi$ (which as yet is also unknown).

Underpinning the bijection $\psi$ is a choice of group elements that realize the bijection in the sense that they take orbit representatives to orbit representatives. This needs some explanation:

If for some pairs $(i,a)$ and $(j,b)$ we have

$$\begin{aligned} \psi \big ({\mathcal {T}}_{i,a}\big ) = {\mathcal {S}}_{j,b}, \end{aligned}$$

(1)

then there exists an element $g \in G$ with

$$\begin{aligned} T_{i,a}^g = S_{j,b}. \end{aligned}$$

(2)

While the bijection $\psi$ is canonical, the choice of the element $g$ in (2) is not. If $u \in \mathrm{Stab}_{G}(T_{i,a})$ and $v \in \mathrm{Stab}_G(S_{j,b})$ then $ugv$ satisfies (2) whenever $g$ does. However, this ambiguity does not bother us. For our purposes, it is important that an element $g$ as in (2) can be computed.

Since the edges in the classification graph $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}$ correspond to pairs ${\mathcal {T}}_{i,a}$ and ${\mathcal {S}}_{j,b}$ corresponding under $\psi$ as in (1), we can label each edge by the associated group element $g$ as in (2).

The idea to store these group elements goes back to Schmalz [23, 24]. For this reason, we decide to call the group element $g \in G$ satisfying (2) the Schmalz isomorphism element.

Suppose we have computed the $G$-orbits on ${\mathcal {X}}$. Suppose that $P_1,\ldots ,P_m$ are the representatives of the orbits and that we know the stabilizer groups $G_{P_i}$ for all $i$. Furthermore, we assume that we have constructive recognition of these orbits: Given an arbitrary element $X \in {\mathcal {X}},$ we can compute an element $g \in G$ such that $X^g = P_i$ for some $i$ (depending on $X$).

Our classification algorithm is easily described. We have two main steps, called Lift and Classify. Classify in turn invokes two algorithms, Define and Eliminate.

In Lift, we compute the sets $\mathrm{Up}(P_i)$ for all $i=1,\ldots ,m.$ Once this is done, we compute the orbits of $G_{P_i}$ on $\mathrm{Up}(P_i)$ for all $i=1,\ldots ,m.$ This gives representatives $T_{i,a}$ for orbits ${\mathcal {T}}_{i,a}$ for $a=1,\ldots , m_i$ and all $i=1, \ldots , m.$ It also furnishes the stabilizer groups $G_{P_i,T_{i,a}} = \mathrm{Stab}_{G_{P_i}}(T_{i,a})$ for $a=1,\ldots , m_i$ and all $i=1, \ldots , m.$ Thus, the sets ${\mathfrak {T}}_i = \{ {\mathcal {T}}_{i,a} \mid a = 1,\ldots , m_i \}$ and ${\mathfrak {T}}= \bigcup _i {\mathfrak {T}}_i$ are known.

In Classify, we loop over the set ${\mathcal {C}}= \{ \Pi _2(T_{i,a}) \mid i=1,\ldots ,m, \; a=1,\ldots , m_i \}$, where $\Pi _2$ is the projection onto the second component (recall that the $T_{i,a}$ are pairs, one element from ${\mathcal {X}}$ and one from ${\mathcal {Y}}$). The strategy is to shrink the set ${\mathcal {C}}$ down to a transversal $Q_1,\ldots ,Q_n$ for the $G$-orbits on ${\mathcal {Y}}.$ This is achieved by invoking Define and Eliminate in turn for elements from ${\mathcal {C}}$. We set $j = 1.$

For Define, we pick the first element in ${\mathcal {C}}$, call it $Q_j,$ and remove it from ${\mathcal {C}}.$ This defines our next representative of a $G$-orbit on ${\mathcal {Y}}.$ We let $i$ and $a$ be so that $\Pi _2(T_{i,a}) = Q_j.$ At this point, the group $G_{P_i,T_{i,a}} \le G_{Q_j}$ is known.

The algorithm Eliminate will remove all isomorphic copies of $Q_j$ from ${\mathcal {C}}$ and compute the group $G_{Q_j}$ from the subgroup $G_{P_i,T_{i,a}}.$ For each element $(X,Q_j) \in \mathrm{Down}(Q_j)$, perform the following algorithm. Determine an element $h_1 \in G$ with $X^{h_1} = P_k$ for some $k\in \{1,\ldots ,m\}$ (depending on $X$). This can be done by assumption. Then compute an element $h_2 \in G_{P_k}$ such that $(P_k,Q_j^{h_1})^{h_2} = T_{k,c}$ for some $c \in \{a,\ldots ,m_k\}.$ This element $h_2$ can be computed easily from the information stored by Lift. If $k=i$ and $c=a,$ we find that $h_1h_2$ is a coset representative for the group $G_{P_i,T_{i,a}}$ in $G_{Q_j}$ and we save it. Otherwise, we delete $\Pi _2(T_{k,c})$ from ${\mathcal {C}}.$ Once all elements of $\mathrm{Down}(Q_j)$ have been processed, the coset representatives saved form a complete set of coset representatives of $G_{P_i,T_{i,a}}$ in $G_{Q_j}.$ Once all elements in $\mathrm{Down}(Q_j)$ have been processed, Eliminate is done.

The algorithm Classify then replaces $j$ by $j+1.$ Unless ${\mathcal {C}}$ is empty, another round of Define and Eliminate is performed. Once ${\mathcal {C}}$ is empty, Classify sets $n$ to $j$ and the classification is completed. The sets $Q_1,\ldots ,Q_n$ form a transversal of the $G$-orbits on ${\mathcal {Y}}.$ In addition, the stabilizers $G_{Q_j}$ have been computed for all $j=1,\ldots ,n.$

We remark that constructive recognition is possible with the following little twist. The idea is to label the edges of the classification graph $\Gamma$ by the Schmalz isomorphisms. So, in Classify, once the elements $h_1$ and $h_2$ have been computed, one simply stores $(h_1h_2)^{-1}$ as a label of the edge leading from $T_{k,c}$ to the appropriate down-orbit of $Q_j.$ Then we can perform constructive recognition. Namely, if an object $Y \in {\mathcal {Y}}$ is given, the following algorithm Recognize computes an element $g\in G$ such that $Y^g = Q_j$ for some $j$ (depending on $Y$):

Recognize: Given $Y \in {\mathcal {Y}},$ pick an arbitrary element $(X,Y) \in \mathrm{Down}(Y)$. Then compute a group element $g_1 \in G$ such that $X^{g_1} = P_i$ for some $i$ (depending on $X$). Using the data stored by the algorithm Lift, compute another group element $g_2 \in G_{P_i}$ with $Y^{g_1g_2} = T_{i,c}$ for some $c$ depending on $Y^{g_1}$. Look up the label of the edge in the graph $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}.$ This gives a Schmalz isomorphism element $g_3 \in G$ such that $Y^{g_1g_2g_3} = Q_j$ for some $j$ depending on $Y$. Output $g := g_1g_2g_3.$

4 The lexicographic ordering

The graphs $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}$ are often very large. In order to make them more useful, we reduce the number of edges (following an idea of [1]). We have to be careful though: Each $Q_j$ needs to have an edge to at least one $P_i$ for some $i$. The lexicographic ordering of subsets can be used to “weed out” edges of the graph. Let $W$ be a totally ordered set. For subsets $A$ and $B$ of $W$ we write $A \prec B$ if $A$ precedes $B$ in the lexicographic ordering of subsets of $W$. We decide to consider lexicographically least orbit representatives. Thus, we ask that $P_i$ is lex-least in $P_i^G,$ that $Q_j$ is lex-least in $Q_j^G$, and that $T_{i,a}$ is lex-least in $T_{i,a}^{G_{P_i}}$. Similarly, we ask that $P_1 \prec P_2 \prec \cdots \prec P_m$ and likewise for all other orbit representatives that we consider.

Let $H$ be a group acting on $W.$ We observe that if $Q \subseteq W$ is lex-least in its $H$-orbit then, for $s \le |Q|$, the first $s$ elements of $Q$ form a set that is lex-least in its $H$-orbits also. Now, let us consider again the situation of Lemma 2. The previous remark implies that for any orbit representative $Q_j$ of a $G$-orbit on ${\mathcal {Y}},$ the first $s$ elements of $Q_j$ form a set that must be a $P_i$ for some $i.$ This is true for any $s \le |Q_j|$.

This leads us to consider the relation ${\mathcal {R}}^* \subseteq {\mathcal {X}} \times {\mathcal {Y}}$ with

$$\begin{aligned} (X,Y) \in {\mathcal {R}}^* \; \text{ if } \; (X,Y) \in {\mathcal {R}} \; \text{ and } \; \min y^{G_X} > \max X \; \forall \; y \in Y \setminus X. \end{aligned}$$

(3)

The set

$$\begin{aligned} \mathrm{Up}^*(X) = \{ (Z,Y) \in {\mathcal {R}}^* \mid Z = X \} \end{aligned}$$

is called special up-set. The group $G_X$ acts on $\mathrm{Up}^*(X)$, and the orbits are called special up-orbits. For $Y \in {\mathcal {Y}}$, the special down-set is the set

$$\begin{aligned} \mathrm{Down}^*(Y) = \{ (X,Z) \in {\mathcal {R}}^* \mid Z = Y \}. \end{aligned}$$

The orbits of $G_Y$ on $\mathrm{Down}^*(Y)$ are called special down-orbits. Let ${\mathcal {T}}_{i,1}^*,\ldots , {\mathcal {T}}_{i,m_i^*}^*$ be the special up-orbits associated with $P_i$, with representatives $T_{i,a}^*$ for the orbit ${\mathcal {T}}_{i,a}^*$, $a=1,\ldots ,m_i^*$. Also, let ${\mathcal {S}}_{j,1}^*,\ldots , {\mathcal {S}}_{j,n_j^*}^*$ be the special down-orbits associated with $Q_j,$ with representatives $S_{j,b}^*$ for the orbit ${\mathcal {S}}_{j,b}^*$, $b=1,\ldots ,n_j^*$. Thus we have

$$\begin{aligned} \mathrm{Up}^*(P_i) = \bigcup _{a=1}^{m_i^*} {\mathcal {T}}_{i,a}^* = \bigcup _{a=1}^{m_i^*} \Big (T_{i,a}^*\Big )^{G_{P_i}} \end{aligned}$$

and

$$\begin{aligned} \mathrm{Down}^*(Q_j) = \bigcup _{b=1}^{n_j^*} {\mathcal {S}}_{j,b}^* = \bigcup _{b=1}^{n_j^*} \Big (S_{j,b}^*\Big )^{G_{Q_j}}. \end{aligned}$$

Let

$$\begin{aligned} {\mathfrak {T}}_i^* = \{ {\mathcal {T}}_{i,a}^* \mid a = 1,\ldots ,m_i^* \} \end{aligned}$$

and

$$\begin{aligned} {\mathfrak {S}}_j^* = \{ {\mathcal {S}}_{j,b}^* \mid b = 1,\ldots ,n_j^* \}. \end{aligned}$$

Finally, let

$$\begin{aligned} {\mathfrak {T}}^* = \bigcup _{i=1}^m {\mathfrak {T}}_i^* \quad \text{ and }\quad {\mathfrak {S}}^* = \bigcup _{j=1}^n {\mathfrak {S}}_j^*. \end{aligned}$$

The canonical pairing $\psi$ between the elements of ${\mathfrak {T}}$ and the elements of ${\mathfrak {S}}$ induces a canonical pairing between ${\mathfrak {T}}^*$ and ${\mathfrak {S}}^*.$ Thus special up-orbits and special down-orbits are paired. In particular $|{\mathfrak {T}}^*|=|{\mathfrak {S}}^*|.$ Define the graph $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}^*$ as the subgraph of $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}$ whose multi-edges correspond to the paired orbits from ${\mathfrak {T}}^*$ and ${\mathfrak {S}}^*.$

Let us now go over the isomorph rejection procedure once more, considering the effect of using the lexicographic ordering. Our emphasis is on working out the differences between the algorithms using lex-least reduction and the algorithm described in Sect. 3.

The function Lift is modified to compute the orbits on $\mathrm{Up}^*(P_i)$ (which is a subset of $\mathrm{Up}(P_i)$). The function Eliminate needs to be reworked a little:

At first, we still consider any element $(X,Q_j) \in \mathrm{Down}(Q_j)$ (no star here). We then compute $h_1 \in G$ with $X^{h_1} = P_k$ for some $k.$ Then we check if $(X^{h_1}, Q_j^{h_1}) = (P_k,Q_j^{h_1}) \in {\mathcal {R}}^*.$ If it is, we have no problem continuing as before to find an element $h_2 \in G_{P_k}$ such that $(P_k,Q_j^{h_1})^{h_2} = T_{k,c}$ for some $c \in \{1,\ldots ,m_k^*\}.$ Otherwise, if $(P_k,Q_j^{h_1}) \not \in {\mathcal {R}}^*,$ we stop and proceed with the next element in $\mathrm{Down}(Q_j).$

5 The exact cover problem

There are exactly two isomorphism classes of spreads in $\mathrm{PG}(3,3),$ namely the Desarguesian spread and the Hall spread. Let us list these two spreads here. A spread in $\mathrm{PG}(3,3)$ is a collection of 10 lines. Taking a cue from coding theory, we represent lines in $\mathrm{PG}(3,q)$ by $2 \times 4$ matrices with entries in ${\mathbb {F}}_q$ (“generator matrices”). The associated line in $\mathrm{PG}(3,3)$ is the rowspan of the matrix. The Desarguesian spread and the Hall spread in $\mathrm{PG}(3,3)$ can be described by means of the following 15 lines, represented as $2 \times 4$ matrices over the field ${\mathbb {F}}_3$:

$$\begin{aligned} \begin{array}{c} \left[ \begin{array}{c} 1000\\ 0100\\ \end{array} \right] \\ \left[ \begin{array}{c} 0010\\ 0001\\ \end{array} \right] \\ \left[ \begin{array}{c} 1010\\ 0101\\ \end{array} \right] \\ \left[ \begin{array}{c} 1020\\ 0102\\ \end{array} \right] \\ \left[ \begin{array}{c} 1001\\ 0120\\ \end{array} \right] \\ \end{array} \quad \begin{array}{c} \left[ \begin{array}{c} 1011\\ 0121\\ \end{array} \right] \\ \left[ \begin{array}{c} 1021\\ 0122\\ \end{array} \right] \\ \left[ \begin{array}{c} 1002\\ 0110\\ \end{array} \right] \\ \left[ \begin{array}{c} 1012\\ 0111\\ \end{array} \right] \\ \left[ \begin{array}{c} 1022\\ 0112\\ \end{array} \right] \\ \end{array} \quad \begin{array}{c} \left[ \begin{array}{c} 1011\\ 0112\\ \end{array} \right] \\ \left[ \begin{array}{c} 1021\\ 0111\\ \end{array} \right] \\ \left[ \begin{array}{c} 1002\\ 0110\\ \end{array} \right] \\ \left[ \begin{array}{c} 1012\\ 0122\\ \end{array} \right] \\ \left[ \begin{array}{c} 1022\\ 0121\\ \end{array} \right] \\ \end{array} \end{aligned}$$

The Dearguesian spread is made up of the 10 lines associated to the matrices in the first two columns. The Hall spread is made up of the 10 lines associated to the matrices in the first and last columns. The Desarguesian spread has an automorphism group of order 5760 and the Hall spread has a group of order 1920. Since $|\mathrm{PGL}(4,3)| = 12,130,560$, we find that there are 2106 copies of the Desarguesian spread and 6318 copies of the Hall spread in $\mathrm{PG}(3,3).$ Let ${\mathcal {S}}$ be the set of these $8424 = 2106+6318$ spreads in $\mathrm{PG}(3,3).$ The problem of classifying all packings requires us to choose 13 of the 8424 spreads in ${\mathcal {S}}$, pairwise (line-) disjoint, and to classify these choices up to isomorphism under the group $G = \mathrm{PGL}(4,3).$ For the classification, we consider the action of $G$ on the set ${\mathcal {Y}}$ of packings of $\mathrm{PG}(3,3).$ We apply the method of classifying suitable subobjects as stepping stone in solving the full problem. As subobjects we choose the set ${\mathcal {X}}$ of partial packings of size 3.

In the first step, we classify the partial packings of size 3 under the action of the group $G$. In Table 6, we show the number of nonisomorphic ways to choose $i$ pairwise disjoint spreads from the set ${\mathcal {S}}$ of 8424 spreads in $\mathrm{PG}(3,3)$ for $i=1,2,3.$ There are 1274 isomorphism types of partial packings in $\mathrm{PG}(3,3).$ For later purposes, we record the fact that the number of all partial packings of size three (i.e., packings not up to isomorphimsm) can be computed from the data given in the table. Using the orbit stabilizer theorem and the stabilizer orders listed in the table, we find that there are around $1.1 \times 10^{10}$ partial packings of size 3.

Table 6 Classification of partial packings

In the next step, we consider the search for packings arising from these partial packings. Consider a partial packing $X$. In order to compute the liftings of this partial packing, we need to find all packings $Y$ that contain $X.$ We transform this problem into an instance of an Exact Cover problem. Each line of $\mathrm{PG}(3,3)$ that is not part of any of the spreads in the partial packing $X$ needs to be “covered” by exactly one of the $13-3=10$ spreads that we are going to select from ${\mathcal {S}}\setminus X$ to form $Y \setminus X$. The details of this step are as follows.

We say that a spread $s \in {\mathcal {S}}$ is live with respect to $X$ if no line of $s$ is part of a spread from the set $X.$ That is, $s \cap x = \emptyset$ for all $x \in X.$ For each partial packing $X = \{x_1,x_2,x_3\}$ of size three, we compute the set

$$\begin{aligned} {\mathcal {S}}_X = \{ s \in {\mathcal {S}}\mid s \; \text{ is } \text{ live } \text{ for } X \} \end{aligned}$$

of live spreads associated with it. Given a partial spread $X$, we define an instance of an exact cover problem:

Let ${\mathcal {L}}_X$ be the set of $130 - 30 = 100$ lines that are not contained in any of the spreads of $X$. We define an incidence matrix $A_X$ between the lines in ${\mathcal {L}}_X$ and the live spreads in ${\mathcal {S}}_X$ as follows: Fix an ordering of the elements of ${\mathcal {L}}_X$ and the elements of ${\mathcal {S}}_X.$ The rows of $A_X$ correspond to the elements of ${\mathcal {L}}_X$ in the chosen order. The columns of $A_X$ correspond to the elements of ${\mathcal {S}}_X$ in the chosen order. For a line $\ell \in {\mathcal {L}}_X$ and a live spread $s \in {\mathcal {S}}_X,$ the corresponding entry in $A_X$ is one if $\ell \in s$ and zero otherwise. The problem of finding all packings containing $X$ is equivalent to solving the system

$$\begin{aligned} A_X \cdot \mathbf{x} = \mathbf{1} \end{aligned}$$

(4)

where $\mathbf{1}$ is the all-one vector of length $|{\mathcal {L}}_X|$ and $\mathbf{x}$ is a zero/one vector of length $|{\mathcal {S}}_X|$ with exactly $13-3 = 10$ ones and the rest zeros.

For each of the 1274 orbits of partial packings of size 3 from Table 6, we pick a representative set $X$. For this partial packing $X$, the lifting process described above is performed. The packings resulting from the liftings are stored.

The third and final step in the classification is invoked once the solutions of the system (4) are determined. In this step, the orbits under the stabilizer $G_X$ in $\mathrm{PGL}(4,3)$ are computed. Then, the classification algorithm from Sect. 3 is applied to these packings. The orbits of $G_X$ on the liftings are the ${\mathfrak {T}}_i$ (here, $i$ is the index of the orbit on partial packings associated with $X$). The algorithm computes the classification graph $\Gamma _{{\mathcal {X}},{\mathcal {Y}},G}$ where ${\mathcal {X}}$ is the set of partial packings of size 3 and ${\mathcal {Y}}$ is the set of packings of $\mathrm{PG}(3,3).$ Of course, the set ${\mathcal {Y}}$ is never fully considered. All that we need is the union of all $\mathrm{Up}(X)$ where $X$ runs over a transversal of the $G$-orbits on partial packings of size 3. This leads to the result described in Theorem 1.

The results of Table 3 were obtained using the system GAP [9].

6 Some final comments

The idea of Sect. 4 is applied to reduce the number of edges in the classification graph. To do so, we rely on the relation ${\mathcal {R}}^*$ between partial packings and live spreads. The condition for a pair $(X,Y) \in {\mathcal {R}}$ to lie in ${\mathcal {R}}^*$ is the following: Let $x_{\max } := \max X$ be the largest spread in $X$ in the lexicographic ordering. According to (3), a packing $Y$ is in relation ${\mathcal {R}}^*$ to $X$ if for each spread $y \in Y \setminus X,$ the condition $\min y^{G_X} > x_{\max }$ holds true. Thus, the lexicographic order yields a condition which reduces the number of live spreads involved in the lifting of a partial packing $X,$ thereby reducing the size of the coefficient matrix $A_X.$ This reduction is particularly effective if $x_{\max }$ is large.

In order to solve the equations (4), the algorithm Dancing Links (DLX) of Knuth [16] is used. The size of the coefficient matrix $A_X$ varies, but frequently we have around 800 columns (and 100 rows). This is quite manageable for Knuth’s algorithm. All 1274 instances of the exact cover problem can be created and solved in less than 20 min, provided the lexicographic ordering is used to reduce the size of the set of live spreads as described in Sect. 4. This leaves us with 8,342,028 packings. The set ${\mathfrak {T}}^*$ of orbits under the respective stabilizer of the partial packing has size 7,272,182. Without imposing the lexicographic condition, the number of packings arising from the lifts is 28,287,067, computed in roughly 30 minutes.

Mathon [17] presents various algorithms to search for spreads and packings, different from our method. Denniston [8] reports having found 9 packings of $\mathrm{PG}(3,3)$, and he estimates that there are many more. In [19], Prince classifies the 7 packings of $\mathrm{PG}(3,3)$ invariant under a group of order 5. Our result confirms this: As we see from Table 2, there is one packing of type $(11,2)$ invariant under a group of order 10, one further packing of type $(6,7)$ invariant under a group of order 10, one packing of type $(1,12)$ invariant under a group of order 360 and four more packings of type $(1,12)$ invariant under a group of order 5.

In [20], Prince is interested in uniform packings. These are packings which are made up solely from spreads of one type. A regular packing is a uniform packing made up from the Desarguesian spread. He shows that there is no regular packing of $\mathrm{PG}(3,3).$ The same result was already very briefly mentioned in [8]. In our table, we see that there is no packing of type $(13,0)$, confirming this result yet another time. Prince goes on to search for uniform packings of type $(0,13)$. He finds at least 54 such packings. Our results show that there are exacty 2860 such packings.

In [11], Johnson classifies the packings of $\mathrm{PG}(n,q)$ whose group acts doubly transitively on the set of spreads. Only the two packings of $\mathrm{PG}(3,2)$ have this property. Packings with groups acting transitively on the set of spreads are more frequent. There are the regular examples due to Penttila and Williams [18] (this encompasses the example of Denniston [7]) and the 45 examples due to Prince [21] in $\mathrm{PG}(3,5).$ As we can see from Table 2 (and also from Table 3), there is no transitive packing in $\mathrm{PG}(3,3).$ On a slightly different note, we mention that Topalova and Zhelezova [25] determine that there are 92 transitive packings of $\mathrm{PG}(5,2)$ (transitive in the sense of transitive on spreads). A different notion of transitivity is considered in [22].