A structure theorem for almost low-degree functions on the slice

The Fourier-Walsh expansion of a Boolean function $f \colon {0,1}^n \rightarrow {0,1}$ is its unique representation as a multilinear polynomial. The Kindler-Safra theorem (2002) asserts that if in the expansion of $f$, the total weight on coefficients beyond degree $k$ is very small, then $f$ can be approximated by a Boolean-valued function depending on at most $O(2^k)$ variables. In this paper we prove a similar theorem for Boolean functions whose domain is the `slice’ ${{[n]}\choose{pn}} = {x \in {0,1}^n\colon \sum_i x_i = pn}$,where$0 \ll p \ll 1$, with respect to their unique representation as harmonic multilinear polynomials. We show that if in the representation of $f\text{\hspace{0.17em}⁣}:\left(\genfrac{}{}{0px}{}{[n]}{pn}\right)\to \{0,1\}$, the total weight beyond degree $k$ is at most $ϵ$, where $ϵ=\min (p,1-p{)}^{O(k)}$, then $f$ can be $O(ϵ)$-approximated by a degree-$k$ Boolean function on the slice, which in turn depends on $O(2^k)$ coordinates. This proves a conjecture of Filmus, Kindler, Mossel, and Wimmer (2015). Our proof relies on hypercontractivity, along with a novel kind of a shifting procedure. In addition, we show that the approximation rate in the Kindler-Safra theorem can be improved from $ϵ+\exp (O(k)){ϵ}^{1\mathrm{/}4}$ to $ϵ+{ϵ}^2(2\ln (1\mathrm{/}ϵ){)}^k\mathrm{/}k!$, which is tight in terms of the dependence on $ϵ$ and misses at most a factor of $2^{O(k)}$ in the lower-order term.