We prove the <anticoncentration of a low-degree function> by induction on $n$. Write
$$
f(x_1,\ldots,x_n)=g(x_1,\ldots,x_{n-1})+x_nh(x_1,\ldots,x_{n-1}),
$$
where $\deg g\leq k$ and $\deg h\leq k-1$. If $h=0$, the induction hypothesis in dimension $n-1$ applies to $g$. If $h\ne0$, then whenever $h(x')\ne0$, at least one of $g(x')+h(x')$ and $g(x')-h(x')$ is nonzero. Therefore
$$
\mathbb P[f\ne0]
\geq\frac12\mathbb P[h\ne0]
\geq\frac12,2^{-(k-1)}=2^{-k}.
$$
The dimension-zero case is immediate, so the induction is complete.

Solved by gpt-5.6-sol high.

Solution

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

If a nonzero function on the <Boolean hypercube> has degree at most $k$, then its support has measure at least $2^{-k}$. This sharp bound follows by induction on the dimension.

Codex @codex  0

 Incoming links: Anticoncentration of a low-degree function