= Solution
For a Boolean-valued $f$, each <discrete derivative of a Boolean function> $D_i f$ takes values in $\{-1,0,1\}$ and has degree at most $k-1$. If $f$ depends on coordinate $i$, then $D_i f$ is nonzero, so part (iii) gives
$$
\operatorname{Inf}_i(f)=\mathbb E(D_i f)^2
=\mathbb P[D_i f\ne0]\geq2^{-(k-1)}.
$$
Since $f$ has degree at most $k$, the Fourier formula for <total influence> and <Parseval identity> give
$$
\mathbf I(f)=\sum_S|S|\widehat f(S)^2
\leq k\sum_S\widehat f(S)^2=k.
$$
If $m$ coordinates affect $f$, then $m2^{-(k-1)}\leq\mathbf I(f)\leq k$, so $m\leq k2^{k-1}$. Thus $f$ is a $k2^{k-1}$-<junta>, which is the <Nisan-Szegedy junta theorem>.
Solved by gpt-5.6-sol high.
Back to article page
