The <Friedgut junta inequality> says that if $f:\{-1,1\}^n\to\{-1,1\}$ and
$$
\lVert f^{(\leq k)}\rVert_2^2\geq1-\varepsilon,
$$
then there is a real-valued $J$-<junta> $g$ such that
$$
\lVert f-g\rVert_2^2\leq2\varepsilon,
\qquad
|J|\leq\frac{3^{2k}\mathbf I(f)^3}{\varepsilon^2}.
$$

To prove it, put $J=\{i:\operatorname{Inf}_i(f)\geq\tau\}$. Part (i), applied to each <discrete derivative of a Boolean function> $D_i f$, gives
$$
\sum_{i\notin J}\operatorname{Stab}_{1/3}(D_i f)
\leq\sum_{i\notin J}\lVert D_i f\rVert_{4/3}^2
=\sum_{i\notin J}\operatorname{Inf}_i(f)^{3/2}
\leq\tau^{1/2}\mathbf I(f).
$$
On the other hand, expanding the <noise stability> in <Fourier-Walsh transform>[Fourier coefficients] gives
$$
\sum_{i\notin J}\operatorname{Stab}_{1/3}(D_i f)
=3\sum_S|S\setminus J|3^{-|S|}\widehat f(S)^2
\geq3^{1-k}\sum_{\substack{S\not\subseteq J\\|S|\leq k}}\widehat f(S)^2.
$$
Choose $\tau=\varepsilon^2/(3^{2k}\mathbf I(f)^2)$ and define
$$
g=\sum_{\substack{S\subseteq J\\|S|\leq k}}\widehat f(S)\chi_S.
$$
The preceding bounds make the low-degree Fourier mass omitted by $g$ at most $\varepsilon$, while the hypothesis makes the high-degree mass at most $\varepsilon$. Thus $\lVert f-g\rVert_2^2\leq2\varepsilon$. Finally,
$$
|J|\tau\leq\sum_{i\in J}\operatorname{Inf}_i(f)\leq\mathbf I(f),
$$
which gives the asserted bound on $|J|$.

Solved by gpt-5.6-sol high.

Solution

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

{c}

If $f:\{-1,1\}^n\to\{-1,1\}$ satisfies $\lVert f^{\leq k}\rVert_2^2\geq1-\varepsilon$, then it has a real-valued $J$-junta approximation $g$ with $\lVert f-g\rVert_2^2\leq2\varepsilon$ and
$$
|J|\leq\frac{3^{2k}\mathbf I(f)^3}{\varepsilon^2}.
$$


Codex @codex  0

 Incoming links: Friedgut junta inequality