I recently came across this paper by Friedgut that shows low sensitivity boolean functions are close to juntas. This was an unintuitive result to me, as I thought I could easily imagine a function on the boolean hypercube that is a linear combination of many low-degree monomials, and therefore has low sensitivity, but still depends on every coordinate. take for example a linear combination of all $O(n^2)$ 2-parities. Eventually I realized that this can be resolved by realizing that such a function can't have it's image in $\{-1,1\}$, i.e. it can't be boolean. Is there some general result that restricts the fourier spectrum of any low-sensitivity function on the hypercube when we further assume it is boolean?
This paper helps give some relevant theory, though it doesn't explain why the function I describe above cant be boolean. One of the formal results it gives is that any boolean function must have a fourier transform whose convolution with itself is the delta function. But I'm not sure what this means practically, or whether it implies any kind of sparsity result for low-sensitivity functions.
If anyone has intuition as to how booleanity restricts the fourier spectrum of a function on the hypercube, or references that might lend me some, it would be much appreciated!
Best,
Paul
EDIT: After thinking some more about the intuition given in the second paper I linked, I think I may be able to offer an explanation for why an linear combination (e.g. of constant weight) of all 2-parities can't be boolean. That paper suggests that the fourier transform $\widehat{f(s)}$ should be orthogonal to every shifted version of itself. In this example, $\widehat{f(s)}$ has some constant value at all vectors with hamming weight 2, and 0 elsewhere. A shifted version of this, $\widehat{f(s+s')}$, is just a permutation of the coordinates of the frequency vectors (I'm thinking of the sets in the fourier domain as being represented with binary inclusion-indicator vectors). I can think of many permutations of the indices of the set of all hamming-weight 2 frequency vectors that would yield a shifted fourier transform that is non-orthogonal to the original: Take for example the permutation that adds $s' = (1,1,1,1,...,0)$ to each frequency vector. So for example $$\widehat{f}((1,1,0,...,0)+(1,1,1,1,...,0)) = \widehat{f}(0,0,1,1,...,0)=C,$$ Thus, there exists $s,s'\neq \textbf{0}$ such that $\widehat{f}(s)\widehat{f}(s+s')=C^2$, and since there are no negative coefficients to compensate for this, the shifted transform is non-orthogonal.
Similarly, I can see why a non-trivial (i.e. non-dictator) function is boolean according to this definition. The Majority function in 3 variables has the fourier series $\frac{x_1}{2}+\frac{x_2}{2}+\frac{x_3}{2}-\frac{x_1x_2x_3}{2}$. The only way to shift the fourier series to have a any non-zero entries would be to e.g. add the shift vector $(1,1,0)$
$$\widehat{f}((1,0,0)+(1,1,0))=\widehat{f}(0,1,0)=\frac{1}{2}$$ $$\widehat{f}((0,1,0)+(1,1,0))=\widehat{f}(1,0,0)=\frac{1}{2}$$ $$\widehat{f}((0,0,1)+(1,1,0))=\widehat{f}(1,1,1)=-\frac{1}{2}$$ $$\widehat{f}((1,1,1)+(1,1,0))=\widehat{f}(0,0,1)=\frac{1}{2}$$
It is easy to see from this that the convolution at $(1,1,0)$
$$\widehat{f}\ast \widehat{f}(1,1,0)=\sum_{x\in \{0,1\}^3} \widehat{f}(x)\widehat{f}(x+(1,1,0))=0$$
I can see how this is true for all shifts. So the shifted fourier spectrum is still orthogonal for all non-trivial shifts, i.e. the convolution of the fourier spectrum with itself is the delta function, and and the function should be boolean according to the result from Tamuz that I shared above. So that checks out.
However, I'm still having trouble understanding the intuition about what kinds of spectra will have this property. It seems like a very simple definition, but the examples I've been able to work through so far aren't revealing a simple rule.
