# Degree 2 Boolean Functions on Grassmann Graphs

Jan De Beule111Department of Mathematics and Data Science, research group
Digital Mathematics, Vrije Universiteit Brussel, B–1050 Brussels, Belgium,
<EMAIL_ADDRESS>Jozefien D’haeseleer222 Dept. of
Mathematics: Analysis, Logic and Discrete Math., Ghent University, Belgium,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
Ferdinand Ihringer222 Dept. of Mathematics: Analysis, Logic and Discrete
Math., Ghent University, Belgium<EMAIL_ADDRESS><EMAIL_ADDRESS>Jonathan Mannaert111Department of Mathematics
and Data Science, research group Digital Mathematics, Vrije Universiteit
Brussel, B–1050 Brussels, Belgium<EMAIL_ADDRESS>
(17 Oct 2022)

###### Abstract

We investigate the existence of Boolean degree $d$ functions on the Grassmann
graph of $k$-spaces in the vector space ${\mathbb{F}}_{q}^{n}$. For $d=1$
several non-existence and classification results are known, and no non-trivial
examples are known for $n\geq 5$. This paper focusses on providing a list of
examples on the case $d=2$ in general dimension and in particular for
$(n,k)=(6,3)$ and $(n,k)=(8,4)$.

We also discuss connections to the analysis of Boolean functions, regular
sets/equitable bipartitions/perfect 2-colorings in graphs, $q$-analogs of
designs, and permutation groups. In particular, this represents a natural
generalization of Cameron-Liebler line classes.

##  1 Introduction

The research presented here is motivated by a variety of open problems in only
loosely related areas such as finite geometry, Boolean function analysis,
association schemes and design theory. Since it seems reasonable to assume
that most readers are not familiar with concepts and conventions in all of
these areas, we provide a relatively long introduction. We refer to [26] for a
more detailed discussion of degree $1$ functions.

More technical details and definitions are omitted from the the introduction
and can be found in Section 2.

###  1.1 Low Degree Boolean Functions

It is a well-known fact that one can write any $0,1$-valued (Boolean) function
on the hypercube $\\{0,1\\}^{n}$ as a real, multilinear polynomial of degree
at most $n$. The study of such functions which we can write as a polynomial of
some bounded degree $d$ has been very fruitful. For instance, it has been
observed countless times that a Boolean degree one function on the hypercube
is of the form $0$, $1$, $x_{i}$, or $1-x_{i}$ for some
$i\in\\{1,\ldots,n\\}$:

######  Theorem 1.1 (Folklore).

A Boolean degree $1$ function on the hypercube depends on at most one
coordinate.

One of the fundamental results in Boolean function analysis (see [40] for a
detailed introduction) is a characterization by Nisan and Szegedy of Boolean
degree $d$ functions in [39].

######  Theorem 1.2 (Nisan, Szegedy (1994)).

A Boolean degree $d$ function on the hypercube depends on at most $d2^{d-1}$
coordinates.

Let $\gamma(d)$ denote the optimal upper bound for given $d$, that is there
exists a Boolean degree $d$ function depending on $\gamma(d)$ coordinates, but
not depending on $\gamma(d)+1$ coordinates. Nisan and Szegedy showed that
$\gamma(d)\leq d2^{d-1}$. They also described a Boolean degree $d$ function
with $2^{d}-1$ relevant variables. Recently, better upper and lower bounds of
magnitude $O(2^{d})$ were found, see [11] and subsequent work. The better
lower bound was, in a different context, first observed in [12].

In the last few years, there has been interest in comparable results on
domains different from the hypercube. For instance see [13] or [26] and the
references therein. One example is the Johnson graph $J(n,k)$, also known as
slice of the hypercube, which consists of all $k$-subsets of
$\\{1,\ldots,n\\}$, two subsets adjacent when their intersection has size
$k-1$. For instance, a classification of Boolean degree $1$ functions on the
Johnson graph has been obtained several times independently, see [24] and
[36]. Note that $k$ and $n-k$ have to be at least $2$ as otherwise all
functions have degree $1$.

######  Theorem 1.3.

Let $n-k,k\geq 2$. A Boolean degree $1$ function on the Johnson graph $J(n,k)$
depends on at most one coordinate.

Filmus and the third author generalized the result by Nisan and Szegedy to the
Johnson graph [27].

######  Theorem 1.4 (Filmus et al. (2019)).

There exists a constant $C$ such that the following holds. If $C^{d}\leq k\leq
n-C^{d}$ and $f:\binom{\\{1,\ldots,n\\}}{k}\rightarrow\\{0,1\\}$ has degree
$d$, then $f$ depends on at most $\gamma(d)$ coordinates.

As before, bounds on $k$ are necessary here, but $C^{d}\leq k\leq n-C^{d}$
seems overly generous. Our (very) limited investigation here suggests that for
$d=2$, we only need to exclude $(n,k)=(6,3)$ and $k<2d$, see Section 3. In
fact, recently Filmus showed in [25] that if we do not insist on the upper
bound $\gamma(d)$ derived from the hypercube, but just some upper bound in
$O(1)$, then $2d\leq k\leq n-2d$ suffices.

Recently, Theorem 1.4 has been extended to several other structures, for
instance the multislice [28] by Filmus, O’Donnell and Wu, and to the perfect
matching scheme by Dafni, Filmus, Lifshitz, Lindzey, and Vinayls [13].

###  1.2 Cameron-Liebler Line Classes and Boolean Functions on the Grassmann
Graph

Our main focus are low degree Boolean functions on the Grassmann graph
$J_{q}(n,k)$ which consists of all $k$-subspaces of an $n$-dimensional vector
space over the finite field of order $q$, two subspaces adjacent when their
meet has dimension $k-1$. Let ${\mathcal{F}}$ be a family of $k$-spaces of
$V\coloneqq{\mathbb{F}}_{q}^{n}$. We read ${\mathcal{F}}$ as a Boolean
function over the reals, that is we identify it with the function $f$ from all
$k$-spaces of $V$ to the reals, where $f(S)=1$ if $S\in{\mathcal{F}}$ and
$f(S)=0$ otherwise. Let $T$ be a subspace of $V$. Let $x_{T}$ denote the
family of all $k$-spaces which are incident with $T$. We say that a (not
necessarily: Boolean) function $f$ has degree $d$ if we can write $f$ as a
linear combination (over the reals) of all $x_{T}$ with $\dim(T)=d$.

The study of Boolean degree $1$ functions, limited to $k=2$, under the name of
Cameron-Liebler line classes is actually older than most of the aforementioned
results. In the Grassmann graph, $1$-spaces (in projective notation: points)
or, equivalently, $(n-1)$-spaces (hyperplanes) are a natural choice for
variables, see §2.2 for details. It was conjectured by Cameron and Liebler in
[9] that, as for the hypercube and the Johnson graph, all degree $1$ examples
are the trivial ones:

######  Conjecture 1.5 (Cameron, Liebler (1982)).

Let $n\geq 4$ and $k=2$. If $f$ is a Boolean degree $1$ function on the
Grassmann graph $J_{q}(n,k)$, then $f$ depends on at most one point and one
hyperplane.

More explicitly, the conjecture suggests that $f$ is one of
$0,x_{P},x_{H},x_{P}+x_{H},1,1-x_{P},1-x_{H},1-x_{P}-x_{H}$ for some $1$-space
$P$ and some $(n-1)$-space $H$ with $P\nsubseteq H$. In the terminology of
finite geometry, they suggested that an example either consists of none of the
lines ($2$-spaces), a point-pencil, a dual point-pencil, the union of a point-
pencil and a dual point-pencil or the complement of any of these examples. In
a breakthrough result, Drudge showed in his PhD thesis [19] that this
conjecture fails for $(n,k,q)=(4,2,3)$. Nowadays many counterexamples to the
Conjecture of Cameron and Liebler are known if $(n,k)=(4,2)$ and $q\geq 3$;
see [8, 14, 22, 23, 31, 33]. The general case of $k>2$ has been investigated
more recently, for instance see [4, 15, 16, 26, 35, 41]. Indeed, it has been
shown in [26] that Conjecture 1.5 holds for $k\geq 2$ and $q\in\\{2,3,4,5\\}$
if we exclude the case $(n,k)=(4,2)$.

In analogy to Theorem 1.4, it seems natural to assume that when $n-k$ and $k$
are large enough, that is $n-k,k\geq C(d)$ for some $C(d)$ independent of $n$
and $k$, then all degree $d$ functions on the Grassmann graph $J_{q}(n,k)$
only depend on very few coordinates $x_{P}$ and $x_{H}$, that is on the
intersection with very few points and hyperplanes. Our results here give an
indication of what $C(d)$ could be.

In Section 5.1 and in Section 5.2 we construct Boolean degree $2$ functions
which depend on many coordinates. For this, we use finite symplectic and
orthogonal geometries.

###  1.3 Equitable Bipartitions

A regular set or equitable bipartition of a $k$-regular graph $\Gamma$ is a
subset $S$ of vertices of $\Gamma$ such that there exists constants $a$ and
$b$ such that a vertex in $S$ has precisely $a$ neighbors in $S$ and such that
a vertex not in $S$ has precisely $b$ neighbors in $S$. The eigenvalues of the
quotient matrix

$\begin{pmatrix}a&k-a\\\ b&k-b\end{pmatrix}$

are also eigenvalues of the adjacency matrix of $\Gamma$ [32, Lemma 9.3.1].
Equitable bipartitions are known under various other names, for instance
perfect $2$-colorings, completely regular codes, or intriguing sets, see also
[26] and the references therein.

Boolean degree $1$ functions in some classical lattices, in particular Johnson
and Grassmann graphs, are equitable bipartitions (for instance, this follows
from our discussion in §2.4). More generally, equitable bipartitions
correspond to Boolean degree $d$ functions which (in the terminology of
Boolean function analysis) have no weights on degrees in $\\{1,\ldots,d-1\\}$.
Regular sets on the hypercube are well-investigated, primarly due to Fon-der-
Flaass [29]. There has been recent work on the Johnson graph, most notably the
equitable bipartitions of the Johnson graph $J(n,3)$ have been classified for
$n$ odd, see [30]. Recently, this attracted much research: regular sets of
degree $2$ have been classified in the Johnson graph by Vorob’ev in [44];
Metsch and De Winter investigated small equitable bipartitions in the the
Grassmann graph of planes $J_{q}(n,3)$ [17]; Mogilnykh surveyed equitable
bipartitions in $J_{2}(6,3)$ and $J_{q}(n,2)$ [37].

##  2 Preliminaries

###  2.1 Projective Geometry

Using projective notation, in ${\mathbb{F}}_{q}^{n}$ we denote $1$-space as
points, $2$-spaces as lines, $3$-spaces as planes, $4$-spaces as solids,
$(n-2)$-spaces as colines, and $(n-1)$-spaces as hyperplanes. For a vector
space $V$, let $\genfrac{[}{]}{0.0pt}{}{V}{k}$ denote its $k$-dimensional
subspaces. We denote the $q$-binomial (or: Gaussian) coefficient by
$\genfrac{[}{]}{0.0pt}{}{n}{k}_{q}\coloneqq|\genfrac{[}{]}{0.0pt}{}{V}{k}|$
for $V={\mathbb{F}}_{q}^{n}$. We write
$[n]_{q}\coloneqq\genfrac{[}{]}{0.0pt}{}{n}{1}_{q}=\frac{q^{n}-1}{q-1}$.
Usually, we do not put the $q$ and write $\genfrac{[}{]}{0.0pt}{}{n}{k}$ and
$[n]$. Note that

$\genfrac{[}{]}{0.0pt}{}{n}{k}=\prod_{i=0}^{k-1}\frac{[n-i]}{[k-i]}.$

Several of our constructions use well-known finite simple groups, namely the
symplectic group $\text{Sp}(n,q)$ and orthogonal group $O^{\varepsilon}(n,q)$.
We try to keep this reasonably self-contained by providing explicit equations,
but we refer to standard literature on finite geometry and the classical
finite simple groups for more details, see [42].

###  2.2 Analysis of Boolean Functions

Recall the concept of a Booleean degree $d$ function in ${\mathbb{F}}_{q}^{n}$
on $k$-spaces from §1.2. We say that a Boolean function $f$ is a $j$-junta if
there is a set $J$ of points and hyperplanes with $|J|=j$ such that we can
write $f$ as a polynomial in $x_{R}$, $R\in J$. A rather trivial example of a
$2$-junta is the set $f$ of $k$-spaces inside a fixed hyperplane $\pi$ or
trough a fixed point $p\not\in\pi$. As we can write
$f=x_{p}+\alpha\sum_{r\in\genfrac{[}{]}{0.0pt}{}{\pi}{1}}x_{r}+\beta\sum_{r\in\genfrac{[}{]}{0.0pt}{}{V}{1}\setminus\genfrac{[}{]}{0.0pt}{}{\pi}{1}}x_{r}$
for suitable real constants $\alpha$ and $\beta$, this is a Boolean degree $1$
function. It only depends on $x_{p}$ and $x_{\pi}$, thus it is a $2$-junta.

We summarize easy, well-known facts in the following lemma. It shows that for
fixed degree $d$, induction on $n$ and $k$ is feasible. Therefore it motivates
our study of small $n$ and $k$ to establish an inductive basis.

######  Lemma 2.1.

Let $n-d\geq k\geq d\geq 1$. Let $f,g$ be Boolean degree $d$ functions on
$J_{q}(n,k)$ with $d\geq 1$. Let $P$ be a $1$-space and $H$ a hyperplane of
$V\coloneqq{\mathbb{F}}_{q}^{n}$. Then all of the following have degree $d$:

  1. (a)

The (not necessarily Boolean) functions $0$, $1$, $f+g$, $f-g$, and $1-f$.

  2. (b)

The set $\\{S\in\genfrac{[}{]}{0.0pt}{}{H}{k}:f(S)=1\\}$.

  3. (c)

The set $\\{S/P\in\genfrac{[}{]}{0.0pt}{}{V/P}{k-1}:f(S)=1\\}$.

###### Proof.

Clearly, any linear combination of two degree $d$ functions has degree $d$.
This shows (a).

For (b): Write $f$ as

$f=\sum_{T\in\genfrac{[}{]}{0.0pt}{}{V}{d}}c_{T}x_{T}.$

For a $k$-space $S\subseteq H$, we have that $f(S)=1$ if and only if $h(S)=1$,
where

$h\coloneqq\sum_{T\in\genfrac{[}{]}{0.0pt}{}{H}{d}}c_{T}x_{T}.$

So $h$ has degree $d$ and is the characteristic function of the set.

The statements (b) and (c) are dual. ∎

We will show in Lemma 2.3 that there exists a relatively easy upper bound
which shows that in the Grassmann graph any function depends on at most
$C_{n,k}q^{n-k}$ coordinates.

######  Lemma 2.2.

Let $n\geq 2k\geq 2$. Then there exists a $q_{0}$ such that for all $q\geq
q_{0}$ there exists a family ${\mathcal{H}}$ of $(n-k+1)$-spaces in
${\mathbb{F}}_{q}^{n}$ with $|{\mathcal{H}}|=k^{2}(n-k+1)$ such that for each
$k$-space $S$ we have that $\langle
S\cap\bigcup_{H\in{\mathcal{H}}}H\rangle=S$.

###### Proof.

For a $k$-space $S$ and $(n-k+1)$-spaces $H_{1},\ldots,H_{m}$ with $m\leq
k^{2}(n-k)$ put $T_{m}(S)=\langle S\cap\bigcup_{i=1}^{m}H_{i}\rangle$.
Consider the property (P) that $\dim(T_{m}(S))<m$. First we calculate the
probability $p_{m}$ that random $H_{1},\ldots,H_{m}$ have property (P). We
claim that $p_{m}<(1+o(1))q^{m-k-1}$ (as $q\rightarrow\infty$) and our proof
proceeds by induction on $m$.

Clearly, $p_{1}=0$ as $H_{1}$ intersects $S$ nontrivially. For $m>1$, the
probability that $H_{1},\ldots,H_{m-1}$ satisfy (P) is $p_{m-1}$. Suppose that
$\dim(T_{m-1}(S))\geq m-1$. If $\dim(T_{m-1}(S))>m-1$, then
$\dim(T_{m}(S))\geq m$, so property (P) is not satisfied. If
$\dim(T_{m-1}(S))=m-1$, then there are $[k]-[m-1]=q^{m-1}[k-m+1]$ points in
$S\setminus T_{m-1}(S)$ and $[m-1]$ points in $T_{m-1}(S)$. Hence, the
probability that $H_{m}$ meets $S$ only in $T_{m-1}(S)$ is at most
$\frac{[m-1]}{[k]}$ (as $H_{m}$ meets $S$ nontrivially and this is the
probability of a point of $S$ being in $T_{m-1}(S)$). Hence, by the union
bound for the two cases $\dim(T_{m-1}(S))<m-1$ and $\dim(T_{m-1}(S))\geq m-1$,

$\displaystyle p_{m}<p_{m-1}+\frac{[m-1]}{[k]}<(1+o(1))q^{m-k-1}.$

This completes the proof of the claim.

Now let us pick $k^{2}(n-k+1)$ random $(n-k+1)$-spaces. Let $X$ denote the
random variable which counts the number of $k$-spaces $S$ with
$\dim(T_{d}(S))<k$. Recall that
$\genfrac{[}{]}{0.0pt}{}{n}{k}<(1+o(1))q^{k(n-k)}$. Then

$\displaystyle{\mathbb{E}}(X)=\genfrac{[}{]}{0.0pt}{}{n}{k}\cdot
p_{k}^{k(n-k+1)}<(1+o(1))q^{k(n-k)}\cdot q^{-k(n-k+1)}<1.$

Hence, by linearity of expectation, there exists a choice of $k^{2}(n-k+1)$
$(n-k+1)$-spaces with $T_{m}(S)=S$ for all $k$-spaces $S$. ∎

######  Lemma 2.3.

Let $1<k<n-1$. Then there exists a $q_{0}$ such that for all $q\geq q_{0}$ we
have that any Boolean function on $J_{q}(n,k)$ is a
$k^{2}(n-k+1)\frac{q^{n-k+1}-1}{q-1}$-junta.

###### Proof.

By duality, we assume that $k\leq n/2$. Put $V={\mathbb{F}}_{q}^{n}$. By Lemma
2.2, we can find a set ${\mathcal{H}}$ of $k^{2}(n-k+1)$ subspaces of
dimension $n-k+1$ such that any $k$-space $T$ contains at least $k$ points in
$\bigcup_{H\in{\mathcal{H}}}H$ which span $T$. For each $T$, let us denote $k$
such points by ${\mathcal{P}}(T)$. Then

$f=\sum_{f(T)=1}\prod_{P\in{\mathcal{P}}(T)}x_{P}.$

Hence, we see that $f$ depends on at most
$k^{2}(n-k+1)\cdot\frac{q^{n-k+1}-1}{q-1}$ points. ∎

###  2.3 The Spectra of Johnson and Grassmann Graphs

Let $n\geq 2k$. Consider the eigenvalues of the adjacency matrices of the
Johnson graph $J(n,k)$ and the Grassmann graph $J_{q}(n,k)$. These are well-
understood objects, for instance see Chapter 9 in [7]. Both graphs have $k+1$
eigenspaces $V_{0},V_{1},\ldots,V_{k}$ with a natural ordering: the eigenspace
$V_{d}$ has dimension
$\genfrac{[}{]}{0.0pt}{}{n}{d}-\genfrac{[}{]}{0.0pt}{}{n}{d-1}$ (where we read
$\genfrac{[}{]}{0.0pt}{}{n}{d}=\binom{n}{d}$ for the Johnson graph). Corollary
3.2.3 in [43] implies

######  Lemma 2.4.

Let $n\geq 2k$ and consider $J_{q}(n,k)$, then we have for every $0\leq d\leq
k$ that $V_{0}+\ldots+V_{d}=\langle x_{D}:\dim D=d\rangle$.

In particular, the first eigenspace is spanned by the all-ones vector (or, as
we identify vectors and functions here, $f=1$). Note that the eigenvalue of
$J_{q}(n,k)$ corresponding to the eigenspace $V_{j}$ is

$q^{j+1}[k-j][n-k-j]-[j].$

Asking for an equitable bipartitions is the same as asking for a set with
characteristic function in $V_{0}+V_{d}$ for some $d$, see [32, §9.3].

###  2.4 Some Equivalent Definitions

The next result emphasizes the (well-known) fact that there are three ways of
looking at degree $d$ functions: We can see them as degree $d$ polynomials, we
can see them as functions in certain eigenspaces, or we can see them as a
certain type of functions in posets. We include some minor variants which we
consider useful. We assume that $d\leq k$.

The $d$-space-to-$k$-space incidence matrix $A=(a_{ij})$ of $J_{q}(n,k)$ is
the
$(\genfrac{[}{]}{0.0pt}{}{n}{d}\times\genfrac{[}{]}{0.0pt}{}{n}{k})$-matrix
indexed by $d$-spaces and $k$-spaces of ${\mathbb{F}}_{q}^{n}$ where
$a_{ij}=1$ if the $i$-th $d$-space lies in the $j$-th $k$-space and $a_{ij}=0$
otherwise.

######  Proposition 2.5.

Let $n\geq 2k$. For $f$ a real function on $J_{q}(n,k)$ the following are
equivalent:

  1. (a)

The function $f$ has degree $d$.

  2. (b)

The function $f$ lies in $V_{0}+\ldots+V_{d}$.

  3. (c)

The function $f$ is orthogonal to $V_{d+1}+\ldots+V_{n}$.

  4. (d)

There exists a weighting
$\text{wt}:\genfrac{[}{]}{0.0pt}{}{V}{d}\rightarrow{\mathbb{R}}$ such that for
all $S\in\genfrac{[}{]}{0.0pt}{}{V}{k}$ we have

$f(S)=\sum_{D\in\genfrac{[}{]}{0.0pt}{}{S}{d}}\text{wt}(D).$

  5. (e)

The function $f$ lies in the image of the $d$-space-to-$k$-space incidence
matrix.

###### Proof.

Lemma 2.4 shows the equivalence of (a) and (b). The equivalence of (b) and (c)
follows from the fact that the common eigenspaces of the association scheme
$J_{q}(n,k)$ are pairwise orthogonal (as its adjacency matrices are
symmetric). Further, (a) and (d) are equivalent: If (a) holds, then we can
write $f$ as

$f=\sum_{D\in\genfrac{[}{]}{0.0pt}{}{V}{d}}c_{D}x_{D}.$

Take $\text{wt}(D)=c_{D}$ to obtain (d). Conversely, if (d) holds, then take
$c_{D}=\text{wt}(D)$ to see that $f$ has degree $d$. Note that
$D\in\genfrac{[}{]}{0.0pt}{}{V}{d}$ lies on some
$S\in\genfrac{[}{]}{0.0pt}{}{V}{k}$. Let $A$ denote the $d$-space-to-$k$-space
incidence matrix. Then (d) states that $f=A^{T}\cdot\text{wt}$. Here we see wt
as a vector of weights. Hence, (d) and (e) are equivalent. ∎

###  2.5 Boolean Functions and Designs

Classical designs live in the Johnson graph. Let $n\geq 2k\geq 2d\geq 0$. A
(classical) $d$-$(n,k,\lambda)$ design in the Johnson graph $J(n,k)$ is a
family ${\mathcal{D}}$ of $k$-sets such that each $d$-set lies in exactly
$\lambda$ elements of ${\mathcal{D}}$. A $d$-$(n,k,\lambda)$ design in the
Grassmann graph $J_{q}(n,k)$ is a family ${\mathcal{D}}$ of $k$-spaces such
that each $d$-space lies in exactly $\lambda$ elements of ${\mathcal{D}}$. The
existence of these $q$-analogs of classical designs was settled (at least in
some weak sense) asymptotically by Fazeli, Lovett, and Vardy in 2014 [21], but
for small parameters deciding existence is notoriosly hard. Maybe most
prominently, a classical $2$-$(7,3,1)$ design is well-known as the Fano plane.
The existence of a $2$-$(7,3,1)$ design in $J_{q}(7,3)$, the so-called
$q$-analog, is a long-standing open problem.

Let ${\mathcal{D}}$ be a $d$-$(n,k,\lambda)$ design of the Grassmann graph
$J_{q}(n,k)$. By a standard double counting argument,
$|{\mathcal{D}}|=\lambda\genfrac{[}{]}{0.0pt}{}{n}{d}/\genfrac{[}{]}{0.0pt}{}{k}{d}$.
For any family ${\mathcal{F}}$ such that the characteristic function $f$ of
${\mathcal{F}}$ has degree $d$, then $|{\mathcal{D}}\cap{\mathcal{F}}|$ only
depends on $|{\mathcal{D}}|$ and $|{\mathcal{F}}|$. Indeed, Boolean degree $d$
functions are precisely the objects with this property. It is a case of what
Delsarte called design-orthogonality, see also [18].

######  Corollary 2.6.

Let $n\geq 2k$. Consider a $d$-$(n,k,\lambda)$ design ${\mathcal{D}}$ of
$J_{q}(n,k)$ with characteristic function $g$. If ${\mathcal{F}}$ is a degree
$d$ subset of $J_{q}(n,k)$, then
$|{\mathcal{F}}\cap{\mathcal{D}}|=|{\mathcal{F}}|\cdot|{\mathcal{D}}|/\genfrac{[}{]}{0.0pt}{}{n}{k}$.
If also $\langle g^{\gamma}:\gamma\in\mathrm{P\Gamma
L}(n,q)\rangle=V_{0}+V_{d+1}+\ldots+V_{k}$, then the converse holds too.

Hence, if ${\mathcal{F}}$ has degree $d$, then
$|{\mathcal{D}}|\cdot|{\mathcal{F}}|/\genfrac{[}{]}{0.0pt}{}{n}{k}$ is an
integer. This is a well-known generalization of the fact that if $k$ divides
$n$, then the size of a Boolean degree $1$ function is divisible by
$\genfrac{[}{]}{0.0pt}{}{n-1}{k-1}$ (using $1$-$(n,k,\lambda)$ designs, that
is spreads). We list the divisibility conditions which derive from the known
designs in §B.

##  3 Degree 2 in Hypercube and Johnson Scheme

Consider the hypercube $\\{0,1\\}^{n}$. Nisan and Szegedy (Theorem 1.2) showed
that a Boolean degree $d$ function on the hypercube depends on at most
$d2^{d-1}$ variables, so a Boolean degree $2$ functions depends on at most 4
variables. Hence, one can obtain a complete list by considering the first four
input variable $x,y,z,w$: Up to permutation and negation of the input, Boolean
degree 2 functions are

$\displaystyle 0,~{}~{}x,~{}~{}x\text{ AND }y=xy,~{}~{}x\text{ XOR
}y=x+y-xy,~{}~{}xy+(1-x)z,$ $\displaystyle\text{Ind}(x{=}y{=}z)=xy+xz+yx-x-
y-z+1,$ $\displaystyle\text{Ind}(x{\leq}y{\leq}z{\leq}w\text{ OR
}x{\geq}y{\geq}z{\geq}w).$

Here $\text{Ind}(B)$ is the indicator of $B$. This list was first obtained by
Camion, Carlet, Charpin, and Sendrier in [10]. For $d=3$ a Boolean degree $2$
function depends on at most $10$ variables, see [45]. Note that $3\cdot
2^{2}=12>10$.

Now consider the Johnson graph $J(n,k)$ with $n\geq 2k$. For $k=3$ there are
countless examples for degree $2$ functions which depends on an arbitrary
amount of coordinates, see [25, 27] for more details and conjectures. All
equitable bipartitions of degree $2$ are classified for $k=3$ [20, 30]. For
$n$ divisible by $d$ and $k\leq 2d-1$, we can find a partition ${\mathcal{L}}$
of $\\{1,\ldots,n\\}$ into $d$-sets. Then

$f(x)=\sum_{S\in{\mathcal{L}}}\prod_{i\in S}x_{i}$

has degree $d$. This function corresponds to the family of $k$-sets containing
one of the $d$-sets of $\mathcal{L}$. This is a very special case of what
Martin calls groupwise complete design, see [34].

For $J(8,4)$ we found an example that depends on $5$ variables. Identify
$J(8,4)$ as a subset of $\\{0,1\\}^{8}$ and take all vertices which start with
one of

$\displaystyle 11000,01100,00110,00011,10001,$ $\displaystyle
11100,01110,00111,10011,11001.$

For an alternative description, let $Z$ be the cyclic group of order $5$ with
its natural action on $\\{1,\ldots,5\\}$. Then we can take any $4$-set which
intersects $\\{1,\ldots,5\\}$ in one of the orbits $\\{1,2\\}^{Z}$ or
$\\{1,2,3\\}^{Z}$. It is an equitable bipartition with quotient matrix

$\displaystyle\begin{pmatrix}8&8\\\ 6&10\end{pmatrix}.$

Recall that Boolean degree $2$ function on the hypercube depends on at most
$4$ coordinates. Thus, the behavior of the Johnson graph is notably different
from the hypercube.

##  4 Examples for General Degree

###  4.1 Trivial Examples

Let $2d\leq 2k\leq n$ and let $\perp$ be some polarity of
${\mathbb{F}}_{q}^{n}$. For a $d$-space $T$, let $x_{T,i}$ denote all
$k$-spaces $S$ with $\dim(S\cap T)=d-i$, and $x_{T^{\perp},i}$ denote all
$k$-spaces $S$ with $\dim(S\cap T^{\perp})=d-i$. We call these examples
trivial. We also call all examples trivial which one can obtain from these
examples by taking unions, differences, and complements.

For our main interest, $d=2$, there are three examples to emphasize.

######  Example 4.1.

  1. (a)

The set of all $k$-spaces through a fixed $2$-space $L$: $x_{L}=x_{P}x_{Q}$.
Here $P$ and $Q$ are points which span $L$.

  2. (b)

The set of all $k$-spaces in a fixed $(n-2)$-space $C$: $x_{C}=x_{H}x_{K}$.
Here $H$ and $K$ are hyperplanes which intersect in $C$.

  3. (c)

The set of all $k$-spaces through a fixed $1$-space $P$ in a fixed
$(n-1)$-space $H$: $x_{P}x_{H}$. Here $P\subseteq H$.

Note that the last example is particularly interesting. Let $C$ be an
$(n-2)$-space. Let ${\mathcal{H}}$ be the set of $q+1$ hyperplanes through
$C$. For each hyperplane $H\in{\mathcal{H}}$, pick a point $P_{H}\subseteq H$
outside of $C$. Then

$f=\sum_{H\in{\mathcal{H}}}x_{H}x_{P_{H}}$

is a Boolean degree $2$ function of size
$(q+1)\genfrac{[}{]}{0.0pt}{}{n-1}{k-1}$. It is a $2(q+1)$-junta.

###  4.2 A (Partial) Spread

Here we describe a union of trivial examples which we consider noteworthy. Let
${\mathcal{S}}$ be a family of $d$-spaces of ${\mathbb{F}}_{q}^{n}$ which are
pairwise disjoint. Such a family is called a partial spread. Clearly,
$|{\mathcal{S}}|\leq[n]/[d]$. In case of equality ${\mathcal{S}}$ is called a
spread. Indeed, spreads exist if and only if $d$ divides $n$, see [2]. The
maximal size of ${\mathcal{S}}$ when $d$ does not divide $n$ was determined
recently in [38]. Clearly,

$f=\sum_{S\in{\mathcal{S}}}x_{S}$

is a Boolean degree $d$ function for $k$-spaces if $k\leq 2d-1$. It shows that
any type of Nisan-Szegedy theorem (for which we assume $q$ fixed and
$n\rightarrow\infty$) needs to exclude the case $k\leq 2d-1$.

###  4.3 Free Constructions from the Hypercube

Let $h:\\{0,1\\}^{m}\rightarrow\\{0,1\\}$ be a Boolean degree $d$ function on
the hypercube. Further, take a linear independent set
$B=\\{b_{1},\ldots,b_{m}\\}$ in ${\mathbb{F}}_{q}^{n}$ (here $n\geq m$).
Define a Boolean degree $d$ function $f$ on the subspaces $S$ of
${\mathbb{F}}_{q}^{n}$ by putting

$f(S)=h((x_{\langle b_{i}\rangle}(S))_{i\in\\{1,\ldots,m\\}}).$

In [11] a Boolean degree $d$ function is described which depends on
$m=\ell(d)\coloneqq 3\cdot 2^{d-1}-2$ variables. Hence, a Boolean degree $d$
function on $J_{q}(n,k)$ can depend on $\ell(d)$ variables. If $B$ is not
linear independent, then $f$ depends on less than $\ell(d)$ variables.

For $q$ fixed and $d$ sufficiently large, this is the best construction for
low degree Boolean functions on $J_{q}(n,k)$ which we are aware of.

For $(n,k)=(8,4)$ we describe a Boolean degree $2$ function in §5.2 which
seems to depend on more than $C(q^{4}+q^{3}+q^{2}+q+1)$ variables (we can only
show that it depends on at least $q^{3}+q^{2}+q+1$ variables).

##  5 Global Degree 2 Examples from Polar Spaces

The most famous example for a nontrivial Boolean degree $1$ function exists in
$J_{q}(4,2)$ (for $q$ odd) and is closely related to the elliptic quadric
$O^{-}(4,q)$. For degree $2$ we went through all polar spaces in small
dimensions.

###  5.1 Examples for Planes

We consider examples on planes, that is $k=3$.

####  5.1.1 Symplectic Spaces

Let $n\geq 6$. Consider a (possibly degenerate) symplectic form $\sigma$ on
${\mathbb{F}}_{q}^{n}$. If $n$ is even, then
$\sigma(x,y)=x_{1}y_{2}-x_{2}y_{1}+\ldots+x_{n-1}y_{n}-x_{n}y_{n-1}$ is a
nondegenerate choice for $\sigma$. We say that $x,y$ are orthogonal if
$\sigma(x,y)=0$. Let $S$ be a subspace. We write $S^{\perp}$ for the subspace
of vectors orthogonal to $S$. The radical of $S$ is $S\cap S^{\perp}$. We say
that $S$ is isotropic if its radical is $S$, and that $S$ is nondegenerate if
its radical is trivial.

There are two types of $2$-spaces with respect to $\sigma$: Let
${\mathcal{L}}_{1}$ denote the set of isotropic $2$-space, and let
${\mathcal{L}}_{2}$ denote the set of nonisotropic $2$-spaces.

There are also two types of $3$-spaces with respect to $\sigma$: Let $\Pi_{1}$
denote the set of isotropic planes, and let $\Pi_{2}$ denote the set of planes
with a point as a radical.

We claim that $\Pi_{i}$ has degree $2$ for $i\in\\{1,2\\}$: Put

$f=\frac{1}{q^{2}+q+1}\sum_{L\in{\mathcal{L}}_{1}}x_{L}-\frac{q+1}{q^{2}(q^{2}+q+1)}\sum_{L\in{\mathcal{L}}_{2}}x_{L}.$

Clearly, $f$ has degree $2$ and corresponds to the set $\Pi_{1}$. It remains
to see that $f$ is Boolean. All $q^{2}+q+1$ lines in an isotropic plane $\Pi$
are isotropic, so $f(\Pi)=1$. A plane $\Pi$ with a point as radical has $q+1$
isotropic lines and $q^{2}$ nondegenerate lines, so then $f(\Pi)=0$.

Now assume that $n$ is even and that $\sigma$ is nondegenerate.

The symmetry group of this example is $\text{Sp}(n,q)$. The number of line
orbits equals the number of plane orbits as there are precisely two types of
each. Thus, this is an example for equality in Block’s lemma, Lemma A.1. The
group $\text{Sp}(n,q)$ acts transitive on points, hence the example is a
$1$-design and therefore an equitable bipartition. For $n=6$, this was already
observed in [17]. The quotient matrix is

$\displaystyle\begin{pmatrix}q[3][n-5]&q^{n-4}[2][3]\\\
[2][n-4]&[3]q[n-3]-[2][n-4]\end{pmatrix}.$

######  Remark 5.1.

A similar construction works for even degree $d$ and $k=d+1$.

####  5.1.2 Quadrics

Let $n\geq 6$. Consider a quadratic form $Q$ on ${\mathbb{F}}_{q}^{n}$, for
instance $Q(x)=x_{1}^{2}+x_{2}x_{3}+\ldots+x_{n-1}x_{n}$ for $n$ odd. Let
${\mathcal{Q}}$ denote the singular points $\langle x\rangle$ (so $Q(x)=0$).
We say that a subspace of ${\mathbb{F}}_{q}^{n}$ is totally singular if all
its points are singular.

Let ${\mathcal{L}}_{i}$ denote the family of lines which intersect
${\mathcal{Q}}$ in $i$ points. As $Q$ is quadratic, ${\mathcal{L}}_{i}$ is
empty unless $i\in\\{0,1,2,q+1\\}$. A line in one of these sets is called
exterior line, tangent, secant, or totally singular line, respectively. There
are five types of planes with respect to $Q$. In bracket we provide the
explicit isomorphy type in ${\mathbb{F}}_{q}^{3}$.

Let $\Pi_{1}$ denote the family of totally singular planes (isomorphic to the
quadratic form $Q^{\prime}(x)=0$).

Let $\Pi_{2}$ denote the family of planes of double line type (isomorphic to
$Q^{\prime}(x)=x_{1}^{2}$).

Let $\Pi_{3}$ denote the family of planes with exactly one singular point
(isomorphic to $Q^{\prime}(x)=x_{1}^{2}+\alpha x_{1}x_{2}+\beta x_{2}^{2}$
such that $x_{1}^{2}+\alpha x_{1}x_{2}+\beta x_{2}^{2}$ is irreducible over
${\mathbb{F}}_{q}$).

Let $\Pi_{4}$ denote the family of planes with exactly two totally singular
lines (isomorphic to $Q^{\prime}(x)=x_{1}x_{2}$).

Let $\Pi_{5}$ denote the family of conic planes (isomorphic to
$Q^{\prime}(x)=x_{1}^{2}+x_{1}x_{2}$).

Let $A=(a_{ji})$ denote the $5\times 4$ matrix such that $a_{ji}$ denotes the
number of lines of ${\mathcal{L}}_{i}$ in a plane of $\Pi_{j}$. Then

$A=\begin{pmatrix}0&0&0&q^{2}+q+1\\\ 0&q^{2}+q&0&1\\\ q^{2}&q+1&0&0\\\
0&q-1&q^{2}&2\\\ \binom{q}{2}&q+1&\binom{q+1}{2}&0\end{pmatrix}.$

Then

$A\left(-\frac{q+1}{q^{4}+q^{3}+q^{2}},\frac{1}{q^{2}+q+1},-\frac{q+1}{q^{4}+q^{3}+q^{2}},\frac{1}{q^{2}+q+1}\right)^{T}=(1,1,0,0,0)^{T},$

so $\Pi_{1}\cup\Pi_{2}$ has degree $2$. We can write the characteristic
function of it as

$f_{1}=-\frac{q+1}{q^{4}+q^{3}+q^{2}}\sum_{L\in{\mathcal{L}}_{0}\cup{\mathcal{L}}_{2}}x_{L}+\frac{1}{q^{2}+q+1}\sum_{L\in{\mathcal{L}}_{1}\cup{\mathcal{L}}_{q+1}}x_{L}.$

If $n$ and $q$ are even, and $Q$ is of hyperbolic type, then this example is
isomorphic to the symplectic example in Section 5.1.1, but not when $q$ is
odd. Its quotient matrix is identical to the symplectic example.

For $q=2$, we also find the following example which corresponds to
$\Pi_{1}\cup\Pi_{3}$:

$f_{2}=\frac{15}{64}\sum_{L\in{\mathcal{L}}_{0}}x_{L}-\frac{1}{42}\sum_{L\in{\mathcal{L}}_{1}}x_{L}-\frac{11}{168}\sum_{L\in{\mathcal{L}}_{2}}x_{L}+\frac{1}{7}\sum_{L\in{\mathcal{L}}_{q+1}}x_{L}.$

For $(n,q)=(6,2)$ with $Q$ of elliptic type $O^{-}(6,q)$, $\Pi_{1}$ is empty.
Hence, for $q=2$ the sets $\Pi_{i}=\Pi_{1}\cup\Pi_{i}$ for $i=2,3$ have degree
$2$, and so any $\Pi_{i}$ with $i\in\\{2,\ldots,4\\}$ has degree 2.

###  5.2 Examples for Solids

We consider examples on solids, that is $k=4$. Let $n=8$. Let $Q$ be a
nondegenerate quadratic form of elliptic type $O^{-}(8,q)$, for instance
$Q(x)=x_{1}^{2}+\alpha x_{1}x_{2}+\beta x_{2}^{2}+x_{3}^{2}+\ldots+x_{8}^{2}$
such that $x_{1}^{2}+\alpha x_{1}x_{2}+\beta x_{2}^{2}$ is irreducible over
${\mathbb{F}}_{q}$. The terminology is identical to §5.1.2, so ${\mathcal{Q}}$
is the set of singular points and we partition the lines set into
${\mathcal{L}}_{0}\cup{\mathcal{L}}_{1}\cup{\mathcal{L}}_{2}\cup{\mathcal{L}}_{q+1}$.
There are the following types of solids. In bracket we provide the explicit
isomorphy type in ${\mathbb{F}}_{q}^{4}$.

Let ${\mathcal{S}}_{1}$ denote the set of all solids of double plane type
(with a quadratic form of type $Q^{\prime}(x)=x_{1}^{2}$).

Let ${\mathcal{S}}_{2}$ denote the set of all solids with two totally singular
planes (type $Q^{\prime}(x)=x_{1}x_{2}$).

Let ${\mathcal{S}}_{3}$ denote the set of all solids with with precisely one
totally singular line (type $Q^{\prime}(x)=x_{1}^{2}+\alpha x_{1}x_{2}+\beta
x_{2}^{2}$).

Let ${\mathcal{S}}_{4}$ denote the set of all solids that intersect
${\mathcal{Q}}$ in a cone with a point as base over a conic (type
$Q^{\prime}(x)=x_{1}^{2}+x_{1}x_{2}$).

Let ${\mathcal{S}}_{5}$ denote the set of all nondegenerate solids of
hyperbolic type $O^{+}(4,q)$ (type $Q^{\prime}(x)=x_{1}x_{2}+x_{3}x_{4}$).

Let ${\mathcal{S}}_{6}$ denote the set of all nondegenerate solids of elliptic
type $O^{-}(4,q)$ (type $Q^{\prime}(x)=x_{1}^{2}+\alpha x_{1}x_{2}+\beta
x_{2}^{2}+x_{3}^{2}$).

The example below can be seen as a generalization of the example by Bruen and
Drudge for degree $1$ in [8]. Let $A=(a_{ji})$ denote the $6\times 4$ matrix
such that $a_{ji}$ denotes the number of lines of ${\mathcal{L}}_{i}$ in a
solid of $\Pi_{j}$.

$\displaystyle A=\begin{pmatrix}0&q^{2}(q^{2}+q+1)&0&q^{2}+q+1\\\
0&q(q^{2}-1)&q^{4}&2q^{2}+2q+1\\\ q^{4}&q(q+1)^{2}&0&1\\\
\frac{1}{2}q^{3}(q-1)&q^{3}+2q^{2}&\frac{1}{2}q^{3}(q+1)&q+1\\\
\frac{1}{2}q^{2}(q-1)^{2}&(q+1)(q^{2}-1)&\frac{1}{2}q^{2}(q+1)^{2}&2(q+1)\\\
\frac{1}{2}q^{2}(q^{2}+1)&(q+1)(q^{2}+1)&\frac{1}{2}q^{2}(q^{2}+1)&0\end{pmatrix}.$

Then we see that

$A\left(\frac{q+1}{q^{3}(q^{2}+q+1)},0,-\frac{q+1}{q^{3}(q^{2}+q+1)},\frac{1}{q^{2}+q+1}\right)^{T}=(1,1,1,0,0,0)^{T}.$

Hence, ${\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}\cup{\mathcal{S}}_{3}$ is a
degree $2$ set. The corresponding degree $2$ polynomial is

$f=\frac{q+1}{q^{3}[3]}\left((\sum_{L\in{\mathcal{L}}_{0}}x_{L})-(\sum_{L\in{\mathcal{L}}_{2}}x_{L})\right)+\frac{1}{[3]}\sum_{L\in{\mathcal{L}}_{q+1}}x_{L}.$

Note that
$|{\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}\cup{\mathcal{S}}_{3}|=(q^{4}+1)(q^{3}+1)(q^{2}+1)[5]$.

This example for $J_{q}(8,4)$ seems to depend on almost all coordinates which
is in contrast to $J(8,4)$ where we only obtained an example depending on $5$
coordinates, see Section 3. Formally, we can show the following:

######  Proposition 5.2.

The example ${\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}\cup{\mathcal{S}}_{3}$
depends on at least $q^{4}-q^{3}+q^{2}-q+3$ variables of type $x_{P}$ and
$x_{H}$ for $P$ a $1$-space and $H$ an $(n-1)$-space.

###### Proof.

Put
${\mathcal{S}}={\mathcal{S}}_{1}\cup{\mathcal{S}}_{2}\cup{\mathcal{S}}_{3}$.
On average, a point of ${\mathbb{F}}_{q}^{8}$ lies in $(q^{3}+1)(q^{2}+1)[5]$
elements of ${\mathcal{S}}$. A singular point lies in
$(q+1)(q^{2}+1)^{2}(q^{3}+1)$ elements of ${\mathcal{S}}$. Hence, a non-
singular point lies on

$\displaystyle\frac{[8]\cdot(q^{3}+1)(q^{2}+1)[5]-(q^{4}+1)(q^{2}+q+1)\cdot(q+1)(q^{2}+1)^{2}(q^{3}+1)}{[8]-(q^{4}+1)(q^{2}+q+1)}$
$\displaystyle=(q^{3}+1)[4]^{2}=:\alpha$

elements of ${\mathcal{S}}$. Dually, a hyperplane of ${\mathbb{F}}_{q}^{8}$
contains at most $\alpha$ elements of ${\mathcal{S}}$. Hence, we need at least

$\left\lceil\frac{|{\mathcal{S}}|}{\alpha}\right\rceil=q^{4}-q^{3}+q^{2}-q+3$

points and hyperplanes to cover all elements of ${\mathcal{S}}$. Now suppose
that ${\mathcal{S}}$ only depends on a set ${\mathcal{R}}$ of less than
$q^{4}-q^{3}+q^{2}-q+3$ points and hyperplanes. Then there exist $4$-spaces
$S\in{\mathcal{S}}$ and $T\not\in{\mathcal{S}}$ which are non-incident with
all elements of ${\mathcal{R}}$. Hence, we cannot distinguish between $S$ and
$T$ based on ${\mathcal{R}}$ which contradicts that ${\mathcal{S}}$ only
depends on ${\mathcal{R}}$. ∎

By Lemma 2.3, the preceding result is tight up to a constant factor (as
$q\rightarrow\infty$). Hence, there exists a degree $2$ function on
$J_{q}(8,4)$ which depends, up to a constant factor, the maximum number of
coordinates.

##  6 Other Examples

###  6.1 Local Degree 2 Examples for Planes

Here we provide an (incomplete) selection of examples which are of degree $2$
and which stabilize a partial flag of subspaces, but are not trivial.

####  6.1.1 A Line and a Complementary Spread

For $n=6$, let $L$ be a line and let ${\mathcal{C}}$ be a set of $q^{2}+1$
colines through $L$ which pairwise meet in $L$. Note that ${\mathcal{C}}$
exists because ${\mathbb{F}}_{q}^{4}$ possesses line spreads. Then the set
$\\{\Pi\text{ a plane}:\dim(\Pi\cap L)=0\text{ and }\exists
C\in{\mathcal{C}}:\Pi\subseteq C\\}$ has degree $2$ and size $(q^{2}+1)\cdot
q^{2}(q+1)$. We can write its characteristic function $f$ as

$f=\sum_{C\in{\mathcal{C}}}(x_{C}-x_{L}).$

The example is a $(q+1)(q^{2}+2)$-junta: we can decide if an element is in the
set by testing inclusion for each of the $q+1$ hyperplanes through the
$q^{2}+1$ colines through $L$, together with testing the inclusion for each of
the $q+1$ points of $L$.

####  6.1.2 Incident Point-Plane-Hyperplane

Figure 1: The point-plane-hyperplane example from §6.1.2. The planes of
$\Pi_{1}$ and $\Pi_{2}$ correspond to the planes with dashed border.

Let $n=6$. Pick a point $P$, a plane $\Pi$, and a hyperplane $H$ such that
$P\subseteq\Pi\subseteq H$.

Let $\Pi_{1}$ be the set of all planes not in $H$ which meet $\Pi$ in a line
through $P$.

Let $\Pi_{2}$ the set of all planes in $H$ whose meet with $\Pi$ is a point
different from $P$.

Then $\Pi_{1}\cup\Pi_{2}$ corresponds to a degree $2$ function and has size
$q^{3}(q+1)+(q^{2}+q)q^{4}=(q^{2}+1)\cdot q^{3}(q+1)$. To see that it has
degree 2, consider the types of lines:

Let ${\mathcal{L}}_{1}$ be the set of all lines in $\Pi$ through $P$.

Let ${\mathcal{L}}_{2}$ be the set of all lines in $\Pi$ not through $P$.

Let ${\mathcal{L}}_{3}$ be the set of all lines in $H$ whose meet with $\Pi$
is $P$.

Let ${\mathcal{L}}_{4}$ be the set of all lines in $H$ whose meet with $\Pi$
is a point, but not $P$.

Let ${\mathcal{L}}_{5}$ be the set of all lines in $H$ which are skew to
$\Pi$.

Let ${\mathcal{L}}_{6}$ be the set of all lines whose meet with $H$ is $P$.

Let ${\mathcal{L}}_{7}$ be the set of all lines whose meet with $H$ is a point
in $\Pi$, but not $P$.

Let ${\mathcal{L}}_{8}$ be the set of all lines whose meet with $H$ is a point
not in $\Pi$.

Then we can write the characteristic function $f$ of $\Pi_{1}\cup\Pi_{2}$ as

$\displaystyle f=$
$\displaystyle\frac{q^{3}}{[3][2]}\sum_{L\in{\mathcal{L}}_{1}}x_{L}+\frac{-q}{[3]}\sum_{{\mathcal{L}}_{2}\cup{\mathcal{L}}_{3}}x_{L}$
$\displaystyle+\frac{1}{[3][2]}\sum_{{\mathcal{L}}_{4}\cup{\mathcal{L}}_{7}}x_{L}+\frac{q+1}{q[3]}\sum_{{\mathcal{L}}_{5}\cup{\mathcal{L}}_{6}}x_{L}+\frac{-1}{q^{2}[3]}\sum_{{\mathcal{L}}_{8}}x_{L}.$

See Figure 1 for an illustration. The example is a $(q^{2}+q+2)$-junta: we can
decide if an element is in $\Pi_{1}\cup\Pi_{2}$ by testing inclusion for the
$q^{2}+q+1$ points in $\Pi$ and $H$.

###  6.2 Some Sporadic Examples

Here are some sporadic example for $(n,q)=(6,2)$. Despite our best efforts, we
did not manage to generalize them. The reader can find some more sporadic
examples, which are also equitable bipartitions, in [37].

####  6.2.1 Incident Line-Solid

For $n=6$ and $q=2$, let $M$ be a line and let $C$ be a coline with
$M\subseteq C$. There are $q+1$ hyperplanes through $C$ and $q+1$ points on
$M$. For each of the $q+1$ points $P\subseteq M$, choose a distinct hyperplane
$H_{P}$ through $C$.

Let $\Pi_{1}$ denote the set of all planes $\pi$ with $M\subseteq\pi\subseteq
C$.

Let $\Pi_{2}$ denote the set of all planes $\pi$ not in $C$ which meet $M$ in
some point $P$ and satisfy $\pi\subseteq H_{p}$.

Let $\Pi_{3}$ denote the set of all planes which meet $M$ in some point $p$
and and $C$ in a line. Note that $\Pi_{2}\subseteq\Pi_{3}$.

The set $\Pi_{1}\cup\Pi_{3}$ has degree $2$ and size
$(q+1)+q^{3}(q+1)^{2}+q^{3}(q^{2}+1)(q+1)$. It is a $2(q+1)$-junta: test all
points on $L$ and all hyperplanes through $C$.

Then set $\Pi_{1}\cup\Pi_{2}$ has degree $2$ and size $(q+1)+q^{3}(q+1)^{2}$.
The example is a $2(q+1)$-junta (as before). Its characteristic function can
be written as

$f=\sum_{P\in\genfrac{[}{]}{0.0pt}{}{M}{1}}(x_{P}-x_{P}x_{H_{P}}),$

where $f$ is the characteristic function of $\Pi_{1}\cup\Pi_{2}\cup\Pi_{3}$
and also has degree $2$.

####  6.2.2 Incident Point-Line-Plane-Hyperplane

For $n=6$ and $q=2$, let $P$ be a $1$-space, $M$ a $2$-space, $\Pi$ a
$3$-space, and $H$ a $5$-space such that $P\subseteq M\subseteq\Pi\subseteq
H$.

Let $\Pi_{1}$ denote all planes in $H$ which contain $M$.

Let $\Pi_{2}$ denote all planes not in $H$ which meet $\Pi$ in a line through
$P$ different from $M$.

Let $\Pi_{3}$ denote all planes in $H$ which meet $\Pi$ in a point on $M$
different from $P$.

The set $\Pi_{1}\cup\Pi_{2}\cup\Pi_{3}$ has degree $2$ and size $7+16+32=55$.
The example is a $(3q+1)$-junta, that is a $7$-junta: we can decide if an
element is in $\Pi_{1}\cup\Pi_{2}$ by testing inclusion for $H$ and the points
in a triangle which includes $M$.

###  6.3 Unexplained Computer Examples

We found some examples by computer which we could not derive from any of the
other examples. We present these and their symmetries in the following table.
In the structure description, we denote the the cyclic group of order $m$ by
$C_{m}$, the symmetric group of order $m!$ by $S_{m}$, and the dihedral group
of order $m$ by $D_{m}$. We write $a^{b}$ if an orbit of length $a$ occurs $b$
times. For plane orbits, we only provide those that constitute the degree $2$
example.

size | stab size | point orbits | line orbits | plane orbits | structure
---|---|---|---|---|---
80 | 61440 | $32,20,10,1$ | $320,160,60,40^{2},16,10,5$ | $40^{2}$ | $C_{2}^{5}\rtimes(C_{2}^{4}\rtimes S_{5})$
85 | 86016 | $32,14^{2},2,1$ | $224^{2},84,32,28^{2},16,7^{2},1$ | $56,21,8$ |  $G$, see below
177 | 64 | $32,4^{7},2^{4},1^{7}$ | $32^{8},16^{15},8^{8},4^{8},2^{24},1^{11}$ | $16^{4},8^{10},2^{13},1^{7}$ | $C_{2}^{3}\times D_{8}$
420 | 126 | $42,21$ | $126^{4},63,42,21,14,7$ | $126^{3},42$ | $S_{3}\times(C_{7}\rtimes C_{3})$

Here
$G=(C_{4}{\times}C_{2}^{3}){\rtimes}(C_{2}{\times}(C_{2}^{3}{\rtimes}PSL(3,2)))$.

##  7 Concluding Remarks

(1) In case of the Johnson graph, let us remark that a classification of
Boolean degree $2$ functions in $J(n,k)$ appears feasible, but goes beyond the
scope of the present work.

(2) For $d=1$ and $k=2$, Bamberg and Penttila [1] classified all subgroups of
$\mathrm{P\Gamma L}(n,q)$ which have the same number of orbits on points and
lines. This answered a conjecture by Cameron and Liebler in [9]. In light of
§A, the following generalization is natural:

######  Problem 7.1.

Classify all subgroups of $\mathrm{P\Gamma L}(n,q)$ with the same number of
orbits on $d$-spaces and $k$-spaces, that is all Boolean degree $d$ functions
on $J_{q}(n,k)$ for which equality holds in Lemma A.1.

(3) In [13] it was shown for several domains that one can write a Boolean
degree $d$ function as a constant depth decision tree. In case of the
Grassmann graph, the natural queries are “Is a point contained in a subspace?”
and “Is a subspace in a hyperplane?”. In light of our collection of examples,
one is tempted to make the following conjecture:

######  Conjecture 7.2.

For every given $q$ and $d$, there exists a $k_{0}$ such that if $k,n-k\geq
k_{0}$, then every Boolean degree $d$ function on $J_{q}(n,k)$ is a constant
depth decision tree.

One might also conjecture that the depth only depends polynomially on $q$. A
related, but less specific conjecture can be found in [27].

##### Acknowledgment

We thank Sam Adriaensen, John Bamberg, and Alexander L. Gavrilyuk for very
helpful comments. We thank Yuval Filmus for several suggestions, including the
list in §3 and Conjecture 7.2. We thank Yuriy Tarannikov for informing us
about [10] and [45]. We thank the referee for their careful reading of the
document. The second and third authors are each supported by a postdoctoral
fellowship of the Research Foundation – Flanders (FWO).

##  Appendix A Permutation Groups and Block’s Lemma

In 1982 Cameron and Liebler investigated subgroups of $\mathrm{P\Gamma
L}(n,q)$ and their orbits on points and lines of the vector space of the
vector space ${\mathbb{F}}_{q}^{n}$, see [9]. An application of Block’s lemma
[3] shows that any subgroup of $\mathrm{P\Gamma L}(n,q)$ has at least as many
orbits on lines as it has on points. In case of equality the orbits of lines
have, in our terminology here, degree $1$.

In this section we concisely discuss a generalization of this application of
Block’s lemma to degree $d$, i.e. we show that a subgroup of $\mathrm{P\Gamma
L}(n,q)$ has at least as many orbits on $k$-spaces of ${\mathbb{F}}_{q}^{n}$
as on $d$-spaces if $d\leq k\leq n/2$. Again, if equality occurs, then the
orbits on $k$-spaces have degree $d$ in the Grassmann graph $J_{q}(n,k)$.

######  Lemma A.1 ([3]).

Let $G$ be a group acting on two finite sets $X$ and $X^{\prime}$, with
respective sizes $n$ and $m$. Let $O_{1},\ldots,O_{s}$, respectively
$O^{\prime}_{1},\ldots,O^{\prime}_{t}$ be the orbits of the action on $X$,
respectively $X^{\prime}$. Suppose that $R\subseteq X\times X^{\prime}$ is a
$G$-invariant relation and call $A=(a_{ij})$ the $n\times m$ matrix of this
relation, i.e. $a_{ij}=1$ if and only if $x_{i}Rx^{\prime}_{j}$ and $a_{ij}=0$
otherwise, after having ordered the elements of $X$ and $X^{\prime}$
arbitrarily. Let $\chi_{S}$ denote the characteristic vector of a set $S$.

  * (i)

The vectors $A^{T}\chi_{O_{i}}$, $i=1,\ldots,s$, are linear combinations of
the vectors $\chi_{O^{\prime}_{j}}$.

  * (ii)

If $A$ has full row rank, then $s\leq t$. If $s=t$, then all vectors
$\chi_{O^{\prime}_{j}}$ are linear combinations of the vectors
$A^{T}\chi_{O_{i}}$, hence $\chi_{O^{\prime}_{j}}\in\mathrm{Im}(A^{T})$.

Let $G\leqslant\mathrm{P\Gamma L}(n,q)$, $n\geq 4$, let $2\leq k<n$, $d\leq k$
and $d\leq n/2$, and let $X$, respectively $X^{\prime}$ be the set of
$d$-spaces, respectively $k$-spaces of ${\mathbb{F}}_{q}^{n}$. The incidence,
i.e. the symmetrised set theoretic containment, between an element of $X$ and
$X^{\prime}$ is $G$-invariant. Furthermore, the incidence matrix is the
incidence matrix of the $k$-space design of ${\mathbb{F}}_{q}^{n}$, and this
matrix has full row rank by [5]. If $s=t$, i.e. if $G$ has equally many orbits
on the $d$-spaces as on the $k$-spaces, then the characteristic vector of each
of the orbits of $k$-spaces lies in $\mathrm{Im}(A^{T})$.

In [9], Cameron and Liebler studied collineation groups having equally many
point as line orbits, that is $(d,k)=(1,2)$. Conjecture 1.5 translates in this
context that such a group is line transitive, or fixes a hyperplane and acts
transitively on the lines of the hyperplanes, or, dually, fixes a point and
acts transitively on the lines through the fixed point.

We call two $k$-spaces of ${\mathbb{F}}_{q}^{n}$ skew if and only if they only
share the zero vector. A partition of the points of ${\mathbb{F}}_{q}^{n}$ in
$k$-spaces is called a spread of ${\mathbb{F}}_{q}^{n}$ in $k$-spaces. It is
well known that such a spread exists if and only if $k\mid n$, e.g. when $n=4$
and $k=2$, there are spreads of lines in ${\mathbb{F}}_{q}^{n}$. By
Proposition 3.1 of [9], for any set $L$ of lines of ${\mathbb{F}}_{q}^{4}$,
$\chi_{L}\in\mathrm{Im}(A^{T})\iff|L\cap S|=x$ (a natural number, only
depending on $L$), and for any line spread $S$ of ${\mathbb{F}}_{q}^{4}$.
Often, a Cameron-Liebler line class of ${\mathbb{F}}_{q}^{4}$ is defined using
its characterization with relation to line spreads of ${\mathbb{F}}_{q}^{4}$.
When $k\nmid n$, a set $K$ of $k$-spaces of ${\mathbb{F}}_{q}^{n}$ is called a
Cameron-Liebler set $k$-spaces of ${\mathbb{F}}_{q}^{n}$ if and only if
$\chi_{K}\in\mathrm{Im}(A^{T})$. This is the case $d=1$ and $k\geq 1$ found in
a geometrical context in [4].

Note that the statements of Block’s lemma are only unidirectional, i.e. an
orbit of $k$-spaces under a collineation group with equally many point orbits
as orbits on $k$-spaces is a Cameron-Liebler set of $k$-spaces, but the
converse is not true, the union of all $k$-spaces through a fixed point $P$
and contained in a fixed hyperplane not through $P$ is a Cameron-Liebler set
of $k$-spaces which is not the orbit under a collineation group with equally
many point as $k$-space orbits.

We do not know if a classification of such subgroups of $\mathrm{P\Gamma
L}(n,q)$ is feasible, but we will see in §5.1.1 that the symplectic group
$\text{Sp}(n,q)$ provides us with some examples when $n$ and $d$ are even.

##  Appendix B Divisibility Conditions

In the following we summarize known divisibility conditions based on the
survey by Braun, Kiermaier, Wassermann [6].

###  B.1 Small Parameters

For $(n,k)=(6,3)$, a $2$-$(6,3,c(q+1))$ design has size $c(q^{3}+1)[5]$.
Existence is known for $(q,c)=(2,1),(3,3),(4,2),(5,13)$. Hence, for
$q=2,3,4,5$ we obtain that $|{\mathcal{F}}|$ needs to be divisible by
$5,10,17,2$, respectively.

For $(n,k)=(7,3)$, a $2$-$(7,3,\lambda)$ design has size
$\lambda(q^{2}-q+1)[7]$. Existence is known for
$(q,\lambda)=(2,3),(3,5),(4,21),(5,31)$. Hence, for $q=2,3,4,5$ we obtain that
$|{\mathcal{F}}|$ needs to be divisible by $[5]=\frac{q^{5}-1}{q-1}$.

For $(n,k)=(8,4)$, a $2$-$(8,4,c(q^{2}+q+1))$ design has size $c(q^{4}+1)[7]$.
Existence is known for $(q,c)=(2,7),(3,455),(4,5733),(5,20181)$. Hence, for
$q=2,3,4,5$ we obtain that $|{\mathcal{F}}|$ needs to be divisible by
$93,121,341,781$, respectively.

###  B.2 Suzuki’s construction

Let $q$ be a prime and $n\geq 7$ be an integer satisfying
$\text{gcd}(n,4!)=1$. Then there exists a $2$-$(n,3,q^{2}+q+1)$ design. See
[6, Theorem 11]. Hence,

######  Lemma B.1.

Let ${\mathcal{F}}$ be a degree $2$ family of $3$-spaces in
${\mathbb{F}}_{q}^{n}$. Then $(q^{3}-1)|{\mathcal{F}}|$ is divisible by
$q^{n-2}-1$.

For instance, for $n=11$ and $q=2,3,4,5$ or $7$: $(q^{3}-1)|{\mathcal{F}}|$ is
divisible by $511,19\,682,262\,143,1\,953\,124$ or $40\,353\,606$,
respectively.

###  B.3 More Conditions in the Binary Case

######  Lemma B.2.

Let $m\geq 3$. Suppose that ${\mathcal{F}}$ is a set of $3$-spaces in
${\mathbb{F}}_{2}^{n}$ of degree 2, then the following holds:

  1. (a)

If $n=8m$, then $C|{\mathcal{F}}|$ is divisible by $2^{8m-2}-1$, where
$C\in\\{42,312\\}$.

  2. (b)

If $n=9m$, then $42\cdot|{\mathcal{F}}|$ is divisible by $2^{9m-2}-1$.

  3. (c)

If $n=10m$, then $210\cdot|{\mathcal{F}}|$ is divisible by $2^{10m-2}-1$.

  4. (d)

If $n=13m$, then $42\cdot|{\mathcal{F}}|$ is divisible by $2^{13m-2}-1$.

###### Proof.

By [6, Section 5.2], there exist (a) $2$-$(8m,3,C)_{2}$ designs for
$C\in\\{42,312\\}$, (b) $2$-$(9m,3,42)_{2}$ designs for $m\geq 3$, (c)
$2$-$(10m,3,210)_{2}$ designs for $m\geq 3$, and (d) $2$-$(13m,3,42)_{2}$
designs for $m\geq 3$. ∎

## References

  * [1] J. Bamberg and T. Penttila, Overgroups of Cyclic Sylow Subgroups of Linear Groups, Comm. Algebra 36(7) (2008) 2503–2543.
  * [2] A. Beutelspacher, Partial spreads in finite projective spaces and partial designs, Math. Z. 145 (1975) 211–229.
  * [3] R. E. Block, On the orbits of collineation groups, Math. Z. 96 (1967) 33–49.
  * [4] A. Blokhuis, M. De Boeck, and J. D’haeseleer, Cameron-Liebler sets of $k$-spaces in ${\rm PG}(n,q)$, Des. Codes Cryptogr. 87(8) (2019) 1839–1856.
  * [5] R. C. Bose. A note on Fisher’s inequality for balanced incomplete block designs, Ann. Math. Statistics 20 (1949) 619–620.
  * [6] M. Braun, M. Kiermaier, and A. Wassermann, $q$-Analogs of Designs: Subspace Designs, In: M. Greferath, M. Pavčević, N. Silberstein, M. Vázquez-Castro (eds), Network Coding and Subspace Designs. Signals and Commun. Technol. Springer, Cham., 2018 171–211.
  * [7] A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989.
  * [8] A. A. Bruen and K. Drudge, The construction of Cameron-Liebler line classes in PG$(3,q)$, Finite Fields Appl. 5(1) (1999) 35–45.
  * [9] P. J. Cameron and R. A. Liebler, Tactical decompositions and orbits of projective groups, Linear Algebra Appl. 46 (1982) 91–102.
  * [10] P. Camion, C. Carlet, P. Charpin, and N. Sendrier, On Correlation-immune functions, In: Feigenbaum, J. (eds), Advances in Cryptology – CRYPTO ’91. CRYPTO 1991. Lecture Notes in Comput. Sci., vol 576. Springer, Berlin, Heidelberg.
  * [11] J. Chiarelli, P. Hatami, and M. Saks, An Asymptotically Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function, Combinatorica 40(2) (2020) 237–244.
  * [12] C. Carlet and Yu. Tarannikov, Covering Sequences of Boolean Functions and Their Cryptographic Significance, Des. Codes Cryptogr. 25 (2002) 263–279.
  * [13] N. Dafni, Y. Filmus, N. Lifshitz, N. Lindzey, and M. Vinyals, Complexity measures on symmetric group and beyond, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (2021) 87:1–87:5.
  * [14] J. De Beule, J. Demeyer, K. Metsch, and M. Rodgers, A new family of tight sets in $Q^{+}(5,q)$, Des. Codes Cryptogr. 78(3) (2016) 655–678.
  * [15] J. De Beule and J. Mannaert, A modular equality for Cameron-Liebler line classes in projective and affine spaces of odd dimension, Finite Fields Appl. 82 (2022) 102047.
  * [16] J. De Beule, J. Mannaert, and L. Storme. Cameron-Liebler $k$-sets in subspaces and non-existence conditions, Des. Codes Cryptogr. 90(3) (2022) 633–651.
  * [17] S. De Winter and K. Metsch, Perfect 2-Colorings of the Grassmann Graph of Planes, Electron. J. Combin. 27(1) (2020) P1.21.
  * [18] P. Delsarte, Pairs of vectors in the space of an association scheme, Philips Res. Rep. 32 (1977) 373–411.
  * [19] K. W. Drudge, Extremal sets in projective and polar spaces, PhD thesis, The University of Western Ontario, 1998.
  * [20] R. J. Evans, A. L. Gavrilyuk, S. Goryainov, and K. Vorob’ev, Equitable 2-partitions of the Johnson graphs $J(n,3)$, arXiv:2206.15341 [math.CO], 2022.
  * [21] A. Fazeli, S. Lovett, and A. Vardy, Nontrivial $t$-designs over finite fields exist for all $t$, J. Combin. Theory Ser. A 127 (2014) 149–160.
  * [22] T. Feng, K. Momihara, M. Rodgers, Q. Xiang, and H. Zou, Cameron–
Liebler line classes with parameter $x=\frac{(q+1)^{2}}{3}$, Adv. Math. 385
(2021), 107780.

  * [23] T. Feng, K. Momihara, and Q. Xiang, Cameron-Liebler line classes with parameter $x=\frac{q^{2}-1}{2}$, J. Combin. Theory Ser. A 133 (2015) 307–338.
  * [24] Y. Filmus, Friedgut–Kalai–Naor theorem for slices of the Boolean cube, Chic. J. Theoret. Comput. Sci. (2016).
  * [25] Y. Filmus, Junta threshold for low degree Boolean functions on the slice, arXiv:2203.04760 [math.CO] (2022).
  * [26] Y. Filmus and F. Ihringer, Boolean degree 1 functions on some classical association schemes, J. Combin. Theory Ser. A 162 (2019) 241–270.
  * [27] Y. Filmus and F. Ihringer, Boolean constant degree functions on the slice are juntas, Discrete Math. 342(12) (2019).
  * [28] Y. Filmus, R. O’Donnell, and X. Wu, A log-Sobolev inequality for the multislice, with applications, Proceedings of the 10th Innovations in Theoretical Computer Science conference (ITCS’19) (2019) 34:1–34:12.
  * [29] D. G. Fon-Der-Flaass, Perfect 2-colorings of a hypercube, Sib. Math. J. 48 (2007) 740–745.
  * [30] A. L. Gavrilyuk and S. V. Goryainov, On perfect 2-colorings of Johnson graphs $J(v,3)$, J. Combin. Des. 21(6) (2013) 232–252.
  * [31] A. Gavrilyuk, I. Matkin, and T. Penttila, Derivation of Cameron–Liebler line classes, Des. Codes Cryptogr. 86(1) (2018) 231–236.
  * [32] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
  * [33] P. Govaerts and T. Penttila, Cameron–Liebler line classes in PG$(3,4)$, Bull. Belg. Math. Soc. Simon Stevin, 12(5) (2005) 793–804.
  * [34] W. J. Martin, Completely regular designs of strength one, J. Alg. Combin. 3(2) (1994) 177–185.
  * [35] K. Metsch, A gap result for Cameron-Liebler $k$-classes, Discrete Math. 340(6) (2017) 1311–1318.
  * [36] A. D. Meyerowitz, Cycle-balanced partitions in distance-regular graphs, J. Combin. Inform. System Sci. 17(1-2) (1992) 39–42.
  * [37] I. Mogilnykh, Completely regular codes in Johnson and Grassmann graphs with small covering radii, Electron. J. Combin. 29(2) (2022) P2.57.
  * [38] E. Năstase and P. Sissokho, The structure of the minimum size supertail of a subspace partition, Des. Codes Cryptogr. 83 (2017) 549–563.
  * [39] N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity, 4(4) (1994) 301–313.
  * [40] R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014.
  * [41] M. Rodgers, L. Storme, and A. Vansweevelt, Cameron-Liebler $k$-classes in ${\rm PG}(2k+1,q)$, Combinatorica 38(3) (2018) 739–757.
  * [42] D. E. Taylor, The geometry of the classical groups, Heldermann, Berlin, 1992.
  * [43] F. Vanhove, Incidence geometry from an algebraic graph theory point of view, PhD Thesis, 2011.
  * [44] K. Vorob’ev, Equitable 2-partitions of Johnson graphs with the second eigenvalue, arXiv:2003.10956v1 [math.CO] (2020).
  * [45] A. Zverev, On the Structure of the Spectrum Support of Boolean Functions, Boolean Functions, In: Cryptology and Information Security, NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., Volume 18, 2008.