On the fourier tails of bounded functions over the discrete cube
Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan W. O’Donnell · 2006
A theorem of Bourgain [4] on Fourier tails states that if f :(-1, 1)n → (-1, 1) is a boolean-valued function on the discrete cube such that for any k > 0, [Σ|S| > k f(S)2 0, if [Σ|S| > k f(S)2 < exp(-O(k2 log k))] then essentially, f depends on only 2O(k) coordinates. We also show, perhaps surprisingly, that this result is sharp up to the log k factor in the exponent.Our proof uses Fourier analysis, as well as some extremal properties of the Chebyshev polynomials.