On Average Distance, Level-1 Fourier Weight, and Chang's Lemma

Abstract

We study the maximum level-$1$ Fourier weight of Boolean functions, which is equivalent to the minimum average-distance problem on the hypercube. We first determine the dimension-free optimum at sufficiently small densities: there exists a universal $a_0>0$ such that the maximum level-$1$ Fourier weight for Boolean functions of mean smaller than $a_0$ is asymptotically attained by Hamming balls as the dimension $n\to \infty$. The key ingredient is an eventual Gaussian stop-loss domination inequality for normalized Rademacher sums. We then use an induction argument to improve the classical level-$1$ bound (Chang's lemma) in both the small- and large-density regimes. We apply these estimates to strengthen the Friedgut--Kalai--Naor theorem, study the corresponding average-distance problem in Euclidean space, and derive a sharp form of Chang's original lemma for ${\mathbb{F}}_2^n$: Hamming balls maximize the dimension of the span of the large Fourier coefficients.

32 pages; Problem 1 has been resolved now