Boolean functions on Sn which are nearly linear
- Computer Science
- Technion
- ORCID iD: 0000-0002-1739-0872
- More about Yuval Filmus
Editorial introduction
Boolean functions on Sn which are nearly linear, Discrete Analysis 2021:25, 27 pp.
A Boolean function is a function f:{0,1}n→{0,1}. Since a computer program can be naturally regarded as evaluating such a function, Boolean functions are the basic object of study in theoretical computer science.
It turns out that a fruitful way to study them is via analytical approaches such as looking at their Fourier transforms. Indeed, there is now a whole area of mathematics known as the analysis of Boolean functions, large enough to have its own section in Discrete Analysis, to which this paper belongs.
A central result in the area is the Friedgut-Kalai-Naor theorem, which concerns the structure of a Boolean function f that can be approximated (in a suitable sense) by the restriction to {0,1}n of an affine function defined on Rn. If f is given exactly by a formula f(x)=a0+∑ni=1aixi, then it is easy to see (using the fact that f takes only the values 0 and 1) that each ai must belong to {−1,0,1}, and that at most one ai can be non-zero. From this it follows that either f is constant or there exists i such that f(x)=xi or f(x)=1−xi. The theorem of Friedgut, Kalai and Naor is a stability version of this observation: they proved that if f is approximately linear (as measured by the L2 norm), then it can be approximated by a function of this kind.
A theme of increasing importance in the analysis of Boolean functions is to develop analogues of the major results in the area for important sets other than {0,1}n, such as the n-dimensional sphere, or the set of all subsets of [n] of size k for some n,k. One very natural set to consider is the symmetric group Sn, since there are already many analogues for Sn of results concerning {0,1}n. This paper concerns an analogue for Sn of the Friedgut-Kalai-Naor theorem.
It is not immediately obvious what the right definition should be of a linear function defined on Sn, since first we have to decide how we wish to embed Sn into a real vector space, and it is not quite as clear how to do this as it is for {0,1}n. However, every permutation of Sn is given by an n×n permutation matrix, which gives us a natural embedding of Sn into the n2-dimensional space of all real n×n matrices, so a good candidate for the definition of a linear function is the restriction of an affine function defined on that space. More concretely, if we write xij for the characteristic function of the set of all permutations that take i to j, a linear function f on Sn is one that has a formula of the form f=a0+∑ni,j=1aijxij.
The Boolean linear functions on Sn are slightly more complicated than those on {0,1}n, since if 1≤i≤n and A is any subset of {1,2,…,n}, then the sums ∑j∈Axij and ∑j∈Axji are Boolean functions. (They are the characteristic functions of, respectively, the set of all permutations that send i to an element of A and the set of all permutations that send an element of A to i.) It was shown by Ellis, Friedgut and Pilpel that these are the only examples. They are known as dictators, because the image or preimage of just one element i determines the function.
This fact can be expressed in a different way. Let us call the the set Cij of all permutations that send i to j a coset (so xij is the characteristic function of Cij). Then two cosets Cij and Ckl are disjoint if and only if either i=k and j≠l or j=l and i≠k. Then a Boolean linear function is the characteristic function of a union of disjoint cosets.
This reformulation is convenient for stating the main results of the paper, which concern Boolean functions that are approximately linear and linear functions that are approximately Boolean, with various notions of approximation, showing in each case that the function can be approximated by a function that is dictator-like. In one case the function is a dictator, but for other results the author defines an ϵ-disjoint family of cosets to be a set of O(n) cosets of which at most ϵn2 pairs fail to be disjoint. Each main result also has a converse, so the paper gives complete characterizations, with sharp parameters, thereby improving on earlier results by the author with Ellis and Friedgut.
The first step of the argument is to observe that Sn (if n is even, say) contains a copy of {0,1}n/2 – we just take the subgroup generated by n/2 disjoint transpositions. Cosets of this subgroup cover Sn evenly, so an averaging argument shows that if f is close to Boolean, then on most cosets it is close to Boolean. By the Friedgut-Kalai-Naor theorem it follows that on most cosets f is close to a dictator (that is, a function that depends only on one variable). In a series of further steps, this information is used to show that f itself comes from just a few cosets that are mostly disjoint. Although the paper appears to be the last word on a natural and interesting problem, the technique of deducing a result for Sn from a related result in the cube may well have further applications.