My Survey on Cameron-Liebler Classes & Low Degree Functions in Vector Spaces

Earlier this year there was a conference in Budapest, Hungary, named Sum(m)it280, to honor the cumulative 280th birthday of the Péter Frankl, Zoltán Füredi, Ervin Győri and János Pach. There the organizers asked participants for survey articles for a conference volume on extremal problems in combinatorics and geometry. Now I have worked a reasonably amount of what is known as Cameron-Liebler sets (or classes?) or Boolean degree 1 functions or antidesigns or completely regular codes of strength 0 and covering radius 1 or … (fill in more word) … on finite vector spaces $V(n, q)$. I have an old blog post on many of these different words and names here. I also have more posts on this topic here, here and here. Thus, I thought that this will be a reasonable topic for such a survey. Now first I thought that this was a great idea. Then I regretted the idea as it seemed to be much work. But now that I am done, it was actually quite a bit of fun. Below I will highlight some of the minuscule insights which I gained. And here is the preprint of the survey.

On a different note: Peter Keevash’s by now 10 years old preprint on the existence on designs got an update today! Maybe it will get published soon? Or already got published and I missed the news? In any case, this is my go-to example for how publishing a paper can take a very long time. Mostly because it came out while I was a second year PhD student, so it covers my academic career very well.

Formulating the Asymptotic Classification

Recall that $J_q(n, m)$ denotes the Grassmann scheme. That is, the $m$-spaces of $V(n, q)$ together with the graphs where two $m$-spaces are adjacent when their meet is an $i$-space (for some fixed $i$). Here I could classify asymptotically all examples for subsets which correspond to Boolean degree 1 functions. See here for details. In my paper in the Proceedings of the American Mathematical Society I phrase this (essentially, as I write $k$ for $m$ there) as follows:

Theorem: Let $q$ be a prime power and let $m$ be some integer, where $m \geq 2$.
Then there exists a number $c_0(m, q)$ such that for all $\max(m, n – m)$ ≥ c_0(m, q)$ all
Boolean degree $1$ functions on $m$-spaces are trivial.

This is a fine formulation, but when writing my survey I got unhappy about it. First of all, the proof only looks at $m=2$ and then $c_0(m+1, q) = c_0(m, q)+1$ is clear from previous work. Then $J_q(n, m)$ and $J_q(n, n-m)$ are isomorphic in some sense by duality, but the statement of the theorem is not fully symmetric. Now look at my formulation in my survey:

Theorem: Let $\min(n – m, m) \geq 2$. Then there exists a function $c(q)$ such
that the following holds: Suppose that $Y$ is a family of $m$-spaces of $V(n, q)$ with
$deg(f_Y) \leq 1$ and $|n – 2m| ≥ c(q)$. Then $Y$ is trivial.

Maybe I will change my mind about this in the future, but I much happier with this formulation. Also, the values for $c(q)$ are $0, 1, 1, 1$ for $q = 2,3, 4,5$ in this formulation, which is much nicer than the earlier $c_0(2, q) = 2, 3, 3, 3$.

Tables are Nice

Another problem I had with the topic in its current state is that there had been much recent work. Thus, I could no longer keep track of all the constructions and results. At least for me, things are much clearer now. In $J_q(4, 2)$ there exist many exceptional examples and thanks to this tables, I can know remember what they are:

Funnily enough, Morgan Rodgers (who, as several other people, gratefully took a look at a draft of my survey), had forgotten that he found two examples for $q=32$ and $x=495$ in his PhD thesis, not just one. This might have some consequences for our ongoing research (let’s see). It also shows how revisiting older material can be a good things,

The existence results in $J_q(4, 2)$ are clear, but in general dimension it gets messy as well. Currently, I am also happy about my attempt to summarize the situation there:

Overlooked Things

Without going into too much detail here, there is also the question for $m$-sets in an $n$-set which I call $J(n, m)$, the Johnson scheme. There is the question if a Boolean degree $2$ function depends on at most $4$ variables as it is true if one looks at the whole subspace lattice, or if it can depends on more. For $m < 2d$ it can easily depend on more. For $\min(n-m, m)$ large enough, $4$ is correct. Some time ago I noticed that in $J(8, 4)$ there is an example which depends on $5$ variables. Actually, and I am very thankful to Sasha Gavrilyuk for pointing this out, a general family of degree $2$ functions in $J(2m, m)$ with that property had been described earlier by Vorob’ev in this preprint which predates my observation. In fact, I knew the preprint, but I, strangely enough, somehow did not make the connection.

Anyway, I hope that others will also find my survey useful!