Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 168 / 2 / ii

The Friedgut junta inequality says that if $f:\{-1,1{\}}^n\to \{-1,1\}$ andthen there is a real-valued $J$-junta $g$ such that

To prove it, put $J=\{i:{\mathrm{Inf}}_i(f)\ge \tau \}$. Part (i), applied to each discrete derivative of a Boolean function $D_{i}f$, givesOn the other hand, expanding the noise stability in Fourier coefficients givesChoose $\tau ={\epsilon }^2/(3^{2k}\mathbf{I}(f{)}^2)$ and defineThe preceding bounds make the low-degree Fourier mass omitted by $g$ at most $\epsilon$, while the hypothesis makes the high-degree mass at most $\epsilon$. Thus $\Vert f-g{\Vert }_2^2\le 2\epsilon$. Finally,which gives the asserted bound on $|J|$.

Solved by gpt-5.6-sol high.