There is no Cameron-Liebler line class of PG(3,4) with parameter 6

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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

Up ↑

%d bloggers like this: