Fourier Concentration from Shrinkage

For a class $${\mathcal{F}}$$ of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent $${\Gamma_{\mathcal{F}}}$$ is the parameter measuring the reduction in size of a formula $${F\in\mathcal{F}}$$ after $${F}$$ is hit with a random restriction. A Boolean function $${f\colon \{0,1\}^n\to\{1,-1\}}$$ is Fourier-concentrated if, when viewed in the Fourier basis, $${f}$$ has most of its total mass on “low-degree” coefficients. We show a direct connection between the two notions by proving that shrinkage implies Fourier concentration: For a shrinkage exponent $${\Gamma_{\mathcal{F}}}$$ , a formula $${F\in\mathcal{F}}$$ of size $${s}$$ will have most of its Fourier mass on the coefficients of degree up to about $${s^{1/\Gamma_{\mathcal{F}}}}$$ . More precisely, for a Boolean function $${f\colon\{0,1\}^n\to\{1,-1\}}$$ computable by a formula of (large enough) size $${s}$$ and for any parameter $${r > 0}$$ , $$\sum_{A\subseteq [n]\; :\; |A|\geq s^{1/\Gamma} \cdot r} \hat{f}(A)^2\leq s\cdot{\mathscr{polylog}}(s)\cdot exp\left(-\frac{r^{\frac{\Gamma}{\Gamma-1}}}{s^{o(1)}} \right),$$ where $${\Gamma}$$ is the shrinkage exponent for the corresponding class of formulas: $${\Gamma=2}$$ for de Morgan formulas, and $${\Gamma=1/\log_2(\sqrt{5}-1)\approx 3.27}$$ for read-once de Morgan formulas. This Fourier concentration result is optimal, to within the $${o(1)}$$ term in the exponent of $${s}$$ . As a standard application of these Fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity. We also show the tight $${\Theta(s^{1/\Gamma})}$$ bound on the average sensitivity of read-once formulas of size $${s}$$ , which mirrors the known tight bound $${\Theta(\sqrt{s})}$$ on the average sensitivity of general de Morgan $${s}$$ -size formulas.