This is the announced post on my recent paper with Yuval Filmus on Boolean degree functions on association schemes. The post will focus on what motivates the problem from various points of view.
Before I start, a small remark. I am using latex2wp for the first time in this post. Thanks to Luca Trevisan for providing this nice script.
During this post I avoid using many definition, while I cite things that use all kind of terminology. For this I wrote this blog post as a reference. We will go through the main steps in the paper and focus more on the wider context of the research, so the parts for which there is less space in papers and not enough time in talks.
1. Boolean Degree Functions
We want to talk about Boolean degree functions, so let us just extract this definition form the previous post: We consider some function
from some domain
to the reals. A good example to think about is
, the
-dimensional hypercube. In general the domain
should be a subset of layers of a highly symmetric poset where we can identify some form of coordinates
which compose the elements of
. In the case of
we can simply use the
coordinates. For
let
with
if
(so for
that is
) and
otherwise. Then
is a Boolean degree
function if we can write
and . Feel free to just write
instead of
, I add the
for reasons that are not particularly relevant here.
Notice that this is maybe slightly non-standard. Usually, the notion of a degree of a Boolean function is only defined for and there it is common to define the
slightly differently as functions with
, see for example O’Donnell’s book on the analysis Boolean functions. The purpose of this is that then all the
are pairwise orthogonal functions, so an orthogonal basis of the space of degree
functions, but as soon as we change
this is no longer the case, so we stick to
in this post.
As elaborated in more detail in the first post, there are many ways of viewing degree functions. Two more points of view, which I want to reemphasize, are the following (thanks to Yuval Filmus who suggested to emphasize this):
- Instead of using the parametrization and polynomials, we can also start by having a notion of
-junta. In the case of the hypercube, all elements of
for which we can decide its output based on
fixed coordinates are a
-junta. We then say that a Boolean degree
function is everything that is a linear combination of these
-juntas.
- Consider the Hamming graph on the hypercube, so the graph where two elements of
are adjacent if they differ in exactly one coordinate. The adjacency matrix has
eigenspaces
and a function
has degree
exactly when
.
In all examples in this post these different points of view (maybe in a slightly modified form) on degree functions exist and it is extremely helpful to be aware of these.
So what do we want to know about Boolean degree functions? We want to construct and classify them. For
this is very straightforward. There are
Boolean degree
functions which one finds instantaneously:
,
,
, and
. These are all: Suppose that
and
. Then it follows that
and
. Now we claim that
. If otherwise for instance
, then
and in particular
, so
is not Boolean anymore. In the following we call functions like
and
, which only depend on one coordinate, dictatorships.
So the question is not particularly interesting for , but there are many interesting follow-up questions, for instance in the analysis of Boolean functions …
- The famous Freidgut-Kalai-Naor (FKN) theorem says that when a function is close to a Boolean degree
function, then it is close to a dictatorship. This result has far too many applications to list here. Maybe the most surprising application to me was (when I first heard about it as someone who does not know much about social choice theory and who likes voting systems) that it implies a quantitative version of Arrow’s theorem.
- The classification shows that we can predict the value of
by just looking at one coordinate of
as long as
is a Boolean degree
function. If instead
is a Boolean degree
function, then can we say something similar? Indeed, we can. Nisan and Szegedy showed that a Boolean degree
depends on at most
coordinates. Recently, Chiarelli, Hatami and Saks improved this bound to
which is the best possible.
… and in algebraic combinatorics:
- A Boolean degree
functions is a special example for an equitable partition of the hypercube in two parts. Another one are perfect codes. Can we classify all perfect
-colorings? Maybe. Fon-Der-Flaass did produce a large number of them.
- They are also a special example of strength 0 equitable partitions. Meyerowitz classified these (but unpublished, see for example here for the result being mentioned).
2. New Domains
If we want to stick to Boolean degree functions, then we can make the question interesting again by changing
from
to some other domain. An easy option is the slice, that is all elements of
with
ones. That is the same as taking all
-sets of
. Lovasz’ linear algebra proof of the Erdös-Ko-Rado theorem, which uses Hoffman’s ratio bound, says the following:
Theorem 1 Let
. Let
be a family of pairwise intersecting
-sets of
. Then
. Equality holds if
is a Boolean degree
function.
It was shown by several people independently (see the introduction of our paper) that the only Boolean degree functions on
-sets of
are
,
,
and
, so we conclude that if
, then
is the indicator function of
for some
(the three other cases do not have the right size).
I am aware of the following classification results for Boolean degree functions on nice structures:
- All Boolean degree
functions on product domains are trivial. For instance the Hamming cube over an alphabet with
elements (so
). As for the hypercube, all example are constant or a dictator.
- All Boolean degree
functions on the symmetric group
(acting naturally on
) are classified as shown by David Ellis, Ehud Friedgut and Haran Pilpel. The obvious example is to take all elements of
which map
to
. It turns out that all examples are just a union of some of these examples (or their complements).
- Instead of taking just
-element subsets, one can consider the so-called multislice where one picks several specific
‘s. Non-surprisingly, all Boolean degree
functions are trivial.
Now what did Yuval and I do? We investigated the Boolean degree functions for some families association schemes. The main focus in our work is vector spaces, that is
-spaces of
. A large amount of work was done by finite geometers under the term Cameron-Liebler line class for the case
and
. The obvious examples for Boolean degree
functions are the following two: (1) all
-spaces containing a fixed
-space
, and (2) all
-spaces in a fixed
-space
. Of course we can take the union of both examples if
. And we can take complements of both examples. The surprising thing is that there are more examples for
: Drudge found in his PhD thesis another, non-trivial example for
(later generalized to all odd
). Since then, many more non-trivial examples were discovered.
On the other side of the story, Drudge showed in his PhD thesis that when we keep , but we have
, then for
all examples are trivial. Later Alexander Gavrilyuk, together with Ivan Yu. Mogilnykh and Illia Matkin showed the same for
and
. Based on this, Yuval and I obtained our main result:
Theorem 2 All Boolean degree
functions on
-spaces of
are trivial for
if
unless
.
Our argument is inductive as are the arguments for and
. The main point was in each case that a classification of all non-trivial Boolean degree
functions for
was possible. This in turn makes inductive arguments feasible.
There are many other structures, where similar arguments can be made, for instance bilinear form graphs or polar spaces. There are many connections between these structures as well, for instance Boolean degree functions of vector spaces induce Boolean degree
functions on polar spaces and bilinear form graphs. The other way around, a classification of Boolean degree
functions on bilinear form graphs or polar spaces can be most likely used to obtain a classification of Boolean degree
functions in vector spaces.
3. Outlook
Recently, there has been much activity for -sets of
. Here Yuval Filmus obtained a FKN theorem, Yuval and I obtained a Nisan-Szegedy-type theorem, and Keller and Klein a variant of the Kindler-Safra theorem. Similarly, Yuval Filmus also has an FKN theorem for the multislice and, together with O’Donnell and Wu, another result with a Nisan-Szegedy theorem and several similar results.
I am personally very interested in vector space analogs of these results due to the mentioned connection to the Erdös-Ko-Rado theorem. Recently, in a breakthrough the -to-
games conjecture was proven by Subhash Kot, Dor Minzer, and Muli Safra using a result on Boolean functions on vector spaces over
which have a large weight on low degrees. This result, which is closely related to the famous Unique Games Conjecture, certainly shows that this type of results is very interesting to investigate.
Acknowledgements I would like to thank Yuval Filmus and Anurag Bishnoi for proof-reading an earlier draft of this post and making valuable suggestions.
2 comments