A spread of $PG(3,q)$ is a set of lines that forms a partition of the points. Since there are $(q+1)(q^2+1)$ points, and every line occupies $q+1$ points, we see that a spread consists of $q^2+1$ lines. A Cameron-Liebler line class of the projective space $PG(3,q)$ is a set $\mathcal{L}$ of lines that meets every spread in a fixed number $x$ of elements. So for example, if we take all the lines through a point $P$, then every spread must meet it in exactly 1 element, since $P$ lies is an exactly one element of a given spread. We say that $x$ is the parameter of the Cameron-Liebler line class.

These curious geometric objects arose in the work of Peter Cameron and Bob Liebler (‘Tactical decompositions and orbits of projective groups’) on collineation groups having equally many orbits on points as on lines. They showed, amongst many other things, that a Cameron-Liebler line class with parameter $x$ consists of $x(q^2 + q + 1)$ lines and that the only Cameron-Liebler line classes for $x = 1$ are the lines through a point or the lines lying in a plane. For $x = 2$, they proved that the only examples are unions of two disjoint examples with parameter 1. They also noticed that the complement of a Cameron-Liebler line class with parameter $x$ is a Cameron-Liebler line class with parameter $q^2 + 1 - x$. So we need only consider Cameron-Liebler line classes with parameter $x \le \lfloor(q^2 + 1)/2\rfloor$. Moreover, it was conjectured by Cameron and Liebler that there are no examples beyond $x\in\{1,2\}$ (and the complementary values), but this was disproved by Keldon Drudge (1999). Later Drudge and Bruen showed that there were counter-examples for every odd prime-power $q$ (in fact, with $x=(q^2+1)/2$). Tim Penttila and Patrick Govaerts (2005) then showed that there is a Cameron-Liebler line class of $PG(3,4)$ with parameter 7, thus showing that the conjecture is false for even values of $q$.

Now there is much more I could write here about Cameron-Liebler line classes, but I might leave that for a later post. Instead, I would like to report on one particular case; $PG(3,4)$. Here, the possible nontrivial values for $x$ that we need to consider are 3, 4, 5, 6, and 7. However, the results of Bruen-Drudge, Penttila and Govaerts-Penttila show that $x\notin \{3,4,5\}$. So the only outstanding parameter is $x=6$. Tim Penttila placed this problem on his old webpage some six years ago, and I found it again by accident this afternoon. So does such a Cameron-Liebler line class exist and how do we go about solving this problem?

First I need to recast Cameron-Liebler line classes in the language of linear algebra. Penttila (1991) showed that a Cameron-Liebler line class can be defined equivalently as a set of lines $\mathcal{L}$ such that for every line $\ell$ we have

$|\{m \in \mathcal{L} :m\text{ meets }\ell, m\ne \ell\}|=(q+1)x+(q^2-1)\chi_{\mathcal{L}}(\ell)$

where $\chi_{\mathcal{L}}$ is the characteristic function of $\mathcal{L}$. Now let $\Gamma$ be the concurrency graph of $PG(3,q)$: the vertices of $\Gamma$ are the lines, and they are adjacent if they are concurrent (and not equal). This graph is strongly regular with valency $q(q+1)^2$ and so the adjacency matrix $A$ for this graph has three distinct eigenvalues (namely $q(q+1)^2$, $q^2-1$ and $-q-1$). We can then write the definition of a Cameron-Liebler line class purely in (algebraic) graph theoretic language:

$A \chi_{\mathcal{L}} = (q+1)x \cdot \mathbf{j}+(q^2-1)\chi_{\mathcal{L}}$

where $\mathbf{j}$ is the constant function returning 1, and the action of $A$ on $\mathbb{R}^{V\Gamma}$ is just like we would imagine if we wrote $\chi_\mathcal{L}$ out as a 0-1 vector. That is,

$A\chi_{\mathcal{L}} (\ell)=\sum_{m\sim \ell}\chi_{\mathcal{L}}(m)$

where $\sim$ is the relation for $\Gamma$.

Now the problem of whether there exists a Cameron-Liebler line class of $PG(3,4)$ becomes are problem in integer linear programming. We could express the above equation as

$A(x\cdot\mathbf{j}-(q^2+1)\chi_{\mathcal{L}})=(q^2-1) \left(x\cdot\mathbf{j}-(q^2+1) \chi_{\mathcal{L}}\right),$

that is, $x\cdot\mathbf{j}-(q^2+1)\chi_{\mathcal{L}}$ is an eigenvector of $A$. Or we simply ask for a 0-1 vector $v$ such that

$(A - (q^2-1) I-\frac{(q+1)}{(q^2+q+1)}J) v=0$

and the scalar product of $v$ with $\mathbf{j}$ is $x(q^2+q+1)$. Now the automorphism group of this graph has permutation rank 3, so after assuming the first position of $v$ has value 1, I can also assume in turn that there are two other positions that can be switched on. I can then run two jobs on a linear programming solver to settle the problem. I used Gurobi, and it took less than 10 minutes (in series, and on my laptop) to establish that there is no Cameron-Liebler line class of $PG(3,4)$ with parameter 6.