Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 168 (Analysis of Boolean Functions)

Write $q=1-p$, $\mu =q-p$, $\sigma =2\sqrt{pq}$, and ${\varphi }_S(x)={\prod }_{j\in S}(x_j-\mu )/\sigma$. The functions ${\varphi }_S$ form the p-biased product measure orthonormal basis, so the Fourier expansion is $f={\sum }_S{\hat{f}}_p(S){\varphi }_S$. The normalized discrete derivative of a Boolean function satisfiesApplying Parseval identity and then exchanging two finite sums gives

The noise operator on the Boolean hypercube acts diagonally on the same basis: $T_{\rho }{\varphi }_S={\rho }^{|S|}{\varphi }_S$. Hence the noise stability isIts derivative isTaking the right-hand value at $\rho =0$ leaves exactly the linear Fourier weight ${\sum }_i{\hat{f}}_p(\{i\}{)}^2$, while taking the left-hand value at $\rho =1$ gives $\mathbf{I}(f)$.

Solved by gpt-5.6-sol high.

It is enough to consider three alternatives $A,B,C$. Encode each voter's three pairwise preferences by $(x_i,y_i,z_i)$, where $x_i=1$ means $A>B$, $y_i=1$ means $B>C$, and $z_i=1$ means $C>A$. A valid ranking excludes $(1,1,1)$ and $(-1,-1,-1)$. Independence of irrelevant alternatives gives three Boolean functions $u,v,w$ for the social comparisons. Unanimity and transitivity force $u=v=w$: fixing arbitrary $x$, taking $y=-x$ and $z$ constantly equal to $u(x)$ shows $v(-x)=-u(x)$, and cyclic symmetry gives the claim.

Choose the voters' valid rankings independently and uniformly. A social Condorcet paradox is absent exactly whenThus transitivity for every profile gives $3\mathbb{E}[u(x)u(y)]=-1$. Conditional on $x_i$, the bit $y_i$ equals $x_i$ with probability $1/3$ and differs with probability $2/3$, so $(x,y)$ has correlation $-1/3$. ThereforeThe Fourier formula, valid for negative correlation, givesby Parseval identity. Among the numbers $(-1/3{)}^m$, the unique minimum is $-1/3$, attained at $m=1$. Equality in this weighted average therefore forces all Fourier mass onto level one. Hence $u$ is a linear Boolean function with zero constant term. Such a function can have only one nonzero coefficient: otherwise varying two coordinates would make it assume more than two values. Thus $u(x)=x_j$ or $u(x)=-x_j$ for some $j$, making voter $j$ a dictator and proving Arrow theorem.

Solved by gpt-5.6-sol high.

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.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when, for every $J\subseteq [n]$ with $|J|\le r$ and every $u\in \{0,1{\}}^J$,

The regularity lemma for Boolean functions states that for every $\epsilon ,p,r,\delta$ there is $T$ such that every Boolean function has a set $J$, $|J|\le T$, for which a ${\mu }_p$-random $u\in \{0,1{\}}^J$ satisfiesHere $f_u$ is the restriction obtained by fixing the coordinates in $J$ to $u$.

Solved by gpt-5.6-sol high.

If $\alpha >1/2$, monotonicity already gives $\mathbb{E}{f}^{(1/2)}\ge \alpha >1/2$, so assume $\alpha \le 1/2$. Suppose for a contradiction that $\mathbb{E}{f}^{(1/2)}\le 1/2$. By the mean value theorem, some $s\in (p,1/2)$ satisfiesThe Margulis-Russo formula identifies this derivative with the appropriately normalized total influence, so ${\mathbf{I}}_s(f)$ is bounded solely in terms of $\zeta$. The $p$-biased Friedgut junta theorem then supplies, for any small $\eta >0$, a Boolean $J$-junta $h$ with $|J|\le r(\zeta ,\eta )$ and

Because $f$ is monotone, ${\mathbb{P}}_s(f=1)\le 1/2$, hence ${\mathbb{P}}_s(h=0)\ge 1/2-\eta \ge 1/4$ when $\eta \le 1/4$. It follows thatFor some assignment $u$ on $J$ with $h(u)=0$, therefore, ${\mathbb{E}}_s{f}_u\le 4\eta$. Monotonicity and $p<s$ imply ${\mathbb{E}}_p{f}_u\le 4\eta$. Choose $\eta <\alpha /5$, set $\epsilon =\eta$, and take $r\ge |J|$. Thencontradicting $(\epsilon ,p,r)$-quasirandomness. Thus $\mathbb{E}{f}^{(1/2)}>1/2$.

Solved by gpt-5.6-sol high.

Replace $\mathcal{A}$ by its upward closure of a set family $\overline{\mathcal{A}}$; this remains an intersecting family and can only make the desired containment easier. Apply the regularity lemma for Boolean functions to its indicator with parameters $(\epsilon /10,p,r,\epsilon /2)$, where $r$ is chosen from part (ii) with density threshold $\epsilon /2$. We obtain a bounded set $J$ such that all but $\epsilon /2$ of the ${\mu }_p$-weighted restrictions are $(\epsilon /10,p,r)$-quasirandom.

Let $\mathcal{B}\subseteq \mathcal{P}(J)$ consist of assignments $u$ for which the restriction is quasirandom and has $p$-biased expectation at least $\epsilon /2$. Restrictions excluded because of irregularity contribute at most $\epsilon /2$, and the remaining excluded restrictions contribute at most $\epsilon /2$ by their conditional density. Hence

It remains to prove that $\mathcal{B}$ is intersecting. If disjoint $u,v\in \mathcal{B}$ existed, part (ii) would give ${\mathbb{E}}_{1/2}{f}_u>1/2$ and ${\mathbb{E}}_{1/2}{f}_v>1/2$. Couple two unbiased complementary assignments on $[n]\setminus J$. Since two subsets of a common finite probability space having measures greater than $1/2$ must intersect, some complementary pair would make both restrictions equal to one. Together with disjoint $u,v$, this would produce two disjoint members of $\mathcal{A}$, a contradiction. Therefore $\mathcal{B}$ is intersecting, proving the Dinur-Friedgut junta theorem for intersecting families with $m=|J|$.

Solved by gpt-5.6-sol high.

Assume first that no two members of the uniform set family $\mathcal{A}\subseteq [n{]}^{(k)}$ meet in exactly one point. Fix $A_0\in \mathcal{A}$. Since $\mathcal{A}$ is an intersecting family, every $B\in \mathcal{A}$ then contains at least two elements of $A_0$. ConsequentlyThis proves the stated dichotomy.

If the small alternative holds, then for sufficiently large $n$ any fixed $i$ has all but at most $\epsilon \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ members of $\mathcal{A}$ containing it. Otherwise choose $A,B\in \mathcal{A}$ with $A\cap B=\{i\}$. Every $C\in \mathcal{A}$ not containing $i$ must meet both $A\setminus \{i\}$ and $B\setminus \{i\}$, soFor sufficiently large $n$ this is at most $\epsilon \left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$, as required.

Solved by gpt-5.6-sol high.

Write the multilinear polynomial as $f=g+x_{n}h$, where $g$ is independent of $x_n$, $\mathrm{deg}g\le k$, and $\mathrm{deg}h\le k-1$. Put $m_3=\mathbb{E}{X}_n^3$. The Cauchy-Schwarz inequality gives $|m_3|\le \sqrt{C}$, and independence givesChoose $A=A(C)\ge 1$ so large thatInduction on $n$, using $2a{b}^3\le a^2{b}^2+b^4$ and the orthogonal identity $\Vert f{\Vert }_2^2=\Vert g{\Vert }_2^2+\Vert h{\Vert }_2^2$, now yields

If $\mathbb{E}{X}_i^3=0$ and $C\le 9$, the cubic term vanishes. Taking $A=3$ and applying the induction hypothesis gives exactly

Solved by gpt-5.6-sol high.

The relevant invariance principle for a low-degree multilinear polynomial is the following. Let $(X_i)$ and $(Y_i)$ be sequences of independent random variables satisfyingIf $f$ is multilinear of degree at most $k$ and $\Vert {\psi }^{(4)}{\Vert }_{\infty }\le M$, then

For the proof, use the Lindeberg replacement method. Replace $X_i$ by $Y_i$ one coordinate at a time and write $f=u_i+z_i{v}_i$, where $u_i=E_{i}f$ and $v_i=D_{i}f$ depend only on the other coordinates. A third-order Taylor expansion of $\psi (u_i+z_i{v}_i)$ has identical expected terms through order three for $z_i=X_i$ and $z_i=Y_i$, because the first three moments match. Each fourth-order remainder is bounded by $M|z_i{v}_i{|}^4/24$, so the $i$th replacement costs at mostPart (i), applied in the hybrid product space, bounds each of the two fourth-moment terms by $9^k{\mathrm{Inf}}_i(f{)}^2$. Thus the cost is at most $(M/12)9^k{\mathrm{Inf}}_i(f{)}^2$. The triangle inequality and summation over $i$ prove the result.

Solved by gpt-5.6-sol high.

Apply the coordinate-replacement proof from part (ii) directly to the quadratic formThe zero diagonal makes $f$ multilinear. For coordinate $i$,and the row and column assumptions implyEvery hybrid vector appearing during replacement has independent centered variance-one coordinates with fourth moments at most $9$. The degree-one case of part (i) therefore givesThe fourth-order Taylor remainder from replacing coordinate $i$ is at most $(M/12)\mathbb{E}(D_{i}f{)}^4\le 12M$. Summing the $n$ replacement errors yields the stronger estimate

Solved by gpt-5.6-sol high.