Boolean Degree 1 Functions on Association Schemes

This is the announced post on my recent paper with Yuval Filmus on Boolean degree ${1}$ 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 ${1}$ Functions

We want to talk about Boolean degree ${1}$ functions, so let us just extract this definition form the previous post: We consider some function ${f: D \rightarrow {\mathbb R}}$ from some domain ${D}$ to the reals. A good example to think about is ${D = \{ 0, 1 \}^n}$ , the ${n}$ -dimensional hypercube. In general the domain ${D}$ should be a subset of layers of a highly symmetric poset where we can identify some form of coordinates ${P}$ which compose the elements of ${D}$ . In the case of ${\{ 0, 1 \}^n}$ we can simply use the ${n}$ coordinates. For ${i \in P}$ let ${x_i^+: D \rightarrow {\mathbb R}}$ with ${x_i^+(v) = 1}$ if ${i \in v}$ (so for ${\{ 0, 1 \}^n}$ that is ${v_i = 1}$ ) and ${x_i^+(v) = 0}$ otherwise. Then ${f}$ is a Boolean degree ${1}$ function if we can write

$\displaystyle f = c + \sum_{i \in P} c_i x_i^+$

and ${f(D) \subseteq \{ 0, 1 \}}$ . Feel free to just write ${x_i}$ instead of ${x_i^+}$ , 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 ${D = \{ 0, 1 \}^n}$ and there it is common to define the ${x_i^+}$ slightly differently as functions with ${x_i^+(D) \in \{ -1, 1 \}}$ , see for example O’Donnell’s book on the analysis Boolean functions. The purpose of this is that then all the ${x_i^+}$ are pairwise orthogonal functions, so an orthogonal basis of the space of degree ${1}$ functions, but as soon as we change ${D}$ this is no longer the case, so we stick to ${\{ 0, 1 \}}$ in this post.

As elaborated in more detail in the first post, there are many ways of viewing degree ${d}$ 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 ${d}$ -junta. In the case of the hypercube, all elements of ${D}$ for which we can decide its output based on ${d}$ fixed coordinates are a ${d}$ -junta. We then say that a Boolean degree ${d}$ function is everything that is a linear combination of these ${d}$ -juntas.
Consider the Hamming graph on the hypercube, so the graph where two elements of ${\{0,1\}^n}$ are adjacent if they differ in exactly one coordinate. The adjacency matrix has ${n+1}$ eigenspaces ${V_0 + V_1 + \ldots + V_n}$ and a function ${f}$ has degree ${d}$ exactly when ${f \in V_0 + V_1 + \ldots + V_d}$ .

In all examples in this post these different points of view (maybe in a slightly modified form) on degree ${d}$ functions exist and it is extremely helpful to be aware of these.

So what do we want to know about Boolean degree ${1}$ functions? We want to construct and classify them. For ${D = \{ 0, 1 \}^n}$ this is very straightforward. There are ${4}$ Boolean degree ${1}$ functions which one finds instantaneously: ${0}$ , ${1}$ , ${x_i^+}$ , and ${1 - x_i^+}$ . These are all: Suppose that ${f(0\ldots 0) = 0}$ and ${f(10\ldots0) = 1}$ . Then it follows that ${c = 0}$ and ${c_1 = 1}$ . Now we claim that ${f = x_1^+}$ . If otherwise for instance ${f(010\ldots0) = 1}$ , then ${c_2 = 1}$ and in particular ${f(110\ldots 0) = 2}$ , so ${f}$ is not Boolean anymore. In the following we call functions like ${x_i^+}$ and ${1-x_i^+}$ , which only depend on one coordinate, dictatorships.

So the question is not particularly interesting for ${D = \{ 0, 1 \}^n}$ , 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 ${1}$ 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 ${f(v)}$ by just looking at one coordinate of ${v}$ as long as ${f}$ is a Boolean degree ${1}$ function. If instead ${f}$ is a Boolean degree ${d}$ function, then can we say something similar? Indeed, we can. Nisan and Szegedy showed that a Boolean degree ${d}$ depends on at most ${d2^{d-1}}$ coordinates. Recently, Chiarelli, Hatami and Saks improved this bound to ${O(2^d)}$ which is the best possible.

… and in algebraic combinatorics:

A Boolean degree ${1}$ 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 ${2}$ -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 ${1}$ functions, then we can make the question interesting again by changing ${D}$ from ${\{ 0, 1 \}^n}$ to some other domain. An easy option is the slice, that is all elements of ${\{0, 1 \}^n}$ with ${k}$ ones. That is the same as taking all ${k}$ -sets of ${\{ 1, \ldots, n \}}$ . Lovasz’ linear algebra proof of the Erdös-Ko-Rado theorem, which uses Hoffman’s ratio bound, says the following:

Theorem 1 Let ${n > 2k}$ . Let ${\mathcal{F}}$ be a family of pairwise intersecting ${k}$ -sets of ${\{ 1, \ldots, n \}}$ . Then ${|\mathcal{F}| \leq \binom{n-1}{k-1}}$ . Equality holds if ${\mathcal{F}}$ is a Boolean degree ${1}$ function.

It was shown by several people independently (see the introduction of our paper) that the only Boolean degree ${1}$ functions on ${k}$ -sets of ${\{ 1, \ldots, n \}}$ are ${0}$ , ${1}$ , ${x_i^+}$ and ${1-x_i^+}$ , so we conclude that if ${|\mathcal{F}| = \binom{n-1}{k-1}}$ , then ${x_i^+}$ is the indicator function of ${\mathcal{F}}$ for some ${i}$ (the three other cases do not have the right size).

I am aware of the following classification results for Boolean degree ${1}$ functions on nice structures:

All Boolean degree ${1}$ functions on product domains are trivial. For instance the Hamming cube over an alphabet with ${q}$ elements (so ${\{ 0, \ldots, q-1\}^n}$ ). As for the hypercube, all example are constant or a dictator.
All Boolean degree ${1}$ functions on the symmetric group ${S_n}$ (acting naturally on ${\{ 1, \ldots, n \}}$ ) are classified as shown by David Ellis, Ehud Friedgut and Haran Pilpel. The obvious example is to take all elements of ${S_n}$ which map ${i}$ to ${j}$ . It turns out that all examples are just a union of some of these examples (or their complements).
Instead of taking just ${k}$ -element subsets, one can consider the so-called multislice where one picks several specific ${k}$ ‘s. Non-surprisingly, all Boolean degree ${1}$ functions are trivial.

Now what did Yuval and I do? We investigated the Boolean degree ${1}$ functions for some families association schemes. The main focus in our work is vector spaces, that is ${k}$ -spaces of ${\mathbb{F}_q^n}$ . A large amount of work was done by finite geometers under the term Cameron-Liebler line class for the case ${n=4}$ and ${k=2}$ . The obvious examples for Boolean degree ${1}$ functions are the following two: (1) all ${k}$ -spaces containing a fixed ${1}$ -space ${p}$ , and (2) all ${k}$ -spaces in a fixed ${(n-1)}$ -space ${H}$ . Of course we can take the union of both examples if ${p \notin H}$ . And we can take complements of both examples. The surprising thing is that there are more examples for ${q > 2}$ : Drudge found in his PhD thesis another, non-trivial example for ${q=3}$ (later generalized to all odd ${q}$ ). 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 ${k=2}$ , but we have ${n > 4}$ , then for ${q \in \{ 2, 3 \}}$ all examples are trivial. Later Alexander Gavrilyuk, together with Ivan Yu. Mogilnykh and Illia Matkin showed the same for ${q=4}$ and ${q=5}$ . Based on this, Yuval and I obtained our main result:

Theorem 2 All Boolean degree ${1}$ functions on ${k}$ -spaces of ${\mathbb{F}_q^n}$ are trivial for ${k, n-k \geq 2}$ if ${q \in \{ 2, 3, 4, 5\}}$ unless ${(n, k) = (4, 2)}$ .

Our argument is inductive as are the arguments for ${k=2}$ and ${n>4}$ . The main point was in each case that a classification of all non-trivial Boolean degree ${1}$ functions for ${(n, k) = (4, 2)}$ 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 ${1}$ functions of vector spaces induce Boolean degree ${1}$ functions on polar spaces and bilinear form graphs. The other way around, a classification of Boolean degree ${1}$ functions on bilinear form graphs or polar spaces can be most likely used to obtain a classification of Boolean degree ${1}$ functions in vector spaces.

3. Outlook

Recently, there has been much activity for ${k}$ -sets of ${\{ 1, \ldots, n \}}$ . 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 ${2}$ -to- ${2}$ games conjecture was proven by Subhash Kot, Dor Minzer, and Muli Safra using a result on Boolean functions on vector spaces over ${\mathbb{F}_2}$ 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.

One comment

Pingback: Proving Spectral Bounds With Quotient Matrices | Ratio Bound – A Combinatorics Blog

	The Independence Num… on Six Spectral Bounds
	The Independence Num… on Schrijver’s SDP Bound fo…
	Proving Spectral Bou… on Boolean Degree 1 Functions on…
	Proving Spectral Bou… on Translating Terminology: Equit…
	Six Spectral Bounds… on Huang’s Breakthrough, Cv…

Share this:

Like this:

Related

One comment

Leave a Reply Cancel reply