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

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.