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.
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.