= Solution
Use normalized <Fourier-Walsh transform> coefficients $\widehat g(\xi)=2^{-n}\sum_x g(x)(-1)^{x\cdot\xi}$. The Hamming weight $|\xi|$ counts the nonzero coordinates. Norms on the input cube use uniform probability, and a frequency integral here is counting over $\xi\in\mathbb F_2^n$. A common alternative normalization multiplies both sides of the requested comparison by the same factor and does not change it.
<Beckner's inequality> states that for $1<p\leq q<\infty$ and $0\leq\rho\leq\sqrt{(p-1)/(q-1)}$, the <noise operator on the Boolean hypercube>, with coefficients $\widehat{T_\rho g}(\xi)=\rho^{|\xi|}\widehat g(\xi)$, satisfies $\|T_\rho g\|_q\leq\|g\|_p$. In particular choose $q=2$, $p=4/3$, $\rho=1/\sqrt3$.
Let $g=1_A$ and $\alpha=|A|/2^n$. Then $\|g\|_{4/3}^2=\alpha^{3/2}$. On frequencies of weight at most two, $\rho^{2|\xi|}\geq1/9$, so <Beckner's inequality> and <Parseval's identity> give the <low-degree Fourier mass of a sparse Boolean set> estimate
$$
S_{\leq2}:=\sum_{|\xi|\leq2}\widehat g(\xi)^2\leq9\sum_\xi\rho^{2|\xi|}\widehat g(\xi)^2=9\|T_\rho g\|_2^2\leq9\alpha^{3/2}.
$$
The <indicator function> is real and the cube characters are real, so the displayed squares equal the squared <absolute values>. Total <Fourier weight> is $\sum\widehat g(\xi)^2=\|g\|_2^2=\alpha$. If $2^n>2003$, then $0<\alpha\leq1/2003$ and $9\sqrt\alpha\leq9/\sqrt{2003}<1/2$, since $2003>18^2$. Therefore
$$
\boxed{S_{\leq2}<\frac\alpha2<\alpha-S_{\leq2}=\sum_{|\xi|>2}\widehat g(\xi)^2.}
$$
This establishes the strict comparison for every power $N=2^n>2003$, not merely for an unspecified very large threshold. The original PDF supplies the density condition and Beckner request, both missing from the converted TeX.
Back to article page
