Boolean functions on \(S_n\) which are nearly linear

Boolean functions on \(S_n\) which are nearly linear, Discrete Analysis 2021:25, 27 pp.

A Boolean function is a function \(f:\{0,1\}^n\to\{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 \(\mathbb R^n\). If \(f\) is given exactly by a formula \(f(x)=a_0+\sum_{i=1}^na_ix_i\), then it is easy to see (using the fact that \(f\) takes only the values 0 and 1) that each \(a_i\) must belong to \(\{-1,0,1\}\), and that at most one \(a_i\) can be non-zero. From this it follows that either \(f\) is constant or there exists \(i\) such that \(f(x)=x_i\) or \(f(x)=1-x_i\). 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 \(L_2\) 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 \(S_n\), since there are already many analogues for \(S_n\) of results concerning \(\{0,1\}^n\). This paper concerns an analogue for \(S_n\) of the Friedgut-Kalai-Naor theorem.

It is not immediately obvious what the right definition should be of a linear function defined on \(S_n\), since first we have to decide how we wish to embed \(S_n\) 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 \(S_n\) is given by an \(n\times n\) permutation matrix, which gives us a natural embedding of \(S_n\) into the \(n^2\)-dimensional space of all real \(n\times 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 \(x_{ij}\) for the characteristic function of the set of all permutations that take \(i\) to \(j\), a linear function \(f\) on \(S_n\) is one that has a formula of the form \(f=a_0+\sum_{i,j=1}^na_{ij}x_{ij}\).

The Boolean linear functions on \(S_n\) are slightly more complicated than those on \(\{0,1\}^n\), since if \(1\leq i\leq n\) and \(A\) is any subset of \(\{1,2,\dots,n\}\), then the sums \(\sum_{j\in A}x_{ij}\) and \(\sum_{j\in A}x_{ji}\) 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 \(C_{ij}\) of all permutations that send \(i\) to \(j\) a coset (so \(x_{ij}\) is the characteristic function of \(C_{ij}\)). Then two cosets \(C_{ij}\) and \(C_{kl}\) are disjoint if and only if either \(i=k\) and \(j\ne l\) or \(j=l\) and \(i\ne 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 \(\epsilon\)-disjoint family of cosets to be a set of \(O(n)\) cosets of which at most \(\epsilon n^2\) 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 \(S_n\) (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 \(S_n\) 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 \(S_n\) from a related result in the cube may well have further applications.