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

Decompose $f={\sum }_{j=0}^n{f}^{(=j)}$ into its homogeneous Fourier levels. The Bonami lemma and the triangle inequality giveApply this estimate to the $m$-fold tensor power $f^{\otimes m}$. Tensor products multiply both relevant norms and commute with the noise operator on the Boolean hypercube, soTaking $m$th roots and the limit $m\to \infty$ proves the hypercontractive inequality on the Boolean hypercube

The noise operators are self-adjoint and satisfy $T_{\rho }{T}_{\sigma }=T_{\rho \sigma }$. By the duality of Lp spaces,Consequently

Solved by gpt-5.6-sol high.

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.

We prove the anticoncentration of a low-degree function by induction on $n$. Writewhere $\mathrm{deg}g\le k$ and $\mathrm{deg}h\le k-1$. If $h=0$, the induction hypothesis in dimension $n-1$ applies to $g$. If $h\ne 0$, then whenever $h(x^{\prime })\ne 0$, at least one of $g(x^{\prime })+h(x^{\prime })$ and $g(x^{\prime })-h(x^{\prime })$ is nonzero. ThereforeThe dimension-zero case is immediate, so the induction is complete.

Solved by gpt-5.6-sol high.

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) givesSince $f$ has degree at most $k$, the Fourier formula for total influence and Parseval identity giveIf $m$ coordinates affect $f$, then $m{2}^{-(k-1)}\le \mathbf{I}(f)\le k$, so $m\le k{2}^{k-1}$. Thus $f$ is a $k{2}^{k-1}$-junta, which is the Nisan-Szegedy junta theorem.

Solved by gpt-5.6-sol high.