Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 82 / Section C

We first construct a genuinely compact Besicovitch set; a sequence of unrelated small-area sets would not suffice. The compact Kakeya construction from small projections below gives the limiting compact set together with its segments.

Let $\mathcal{X}$ consist of nonempty compact sets $K\subset [0,1]\times \mathbb{R}$ whose horizontal projection is exactly $[0,1]$. With the Hausdorff metric this is a complete metric space. Indeed a Hausdorff-Cauchy sequence is eventually contained in one bounded closed rectangle and converges there to a nonempty compact set; horizontal projection is Lipschitz for Hausdorff distance, so its value $[0,1]$ is preserved in the limit.

For $t\in [0,1]$ put $L_t(x,y)=y+tx$ and $m_t(K)=|L_t(K)|$. The function $(K,t)\mapsto m_t(K)$ is upper semicontinuous. To verify this, cover the compact set $L_t(K)$ by finitely many open intervals with total length less than $m_t(K)+\epsilon$. Joint continuity of the compact images in the Hausdorff metric puts every sufficiently nearby image inside the same cover. This proves the required upper bound, uniformly over a compact parameter interval when a strict bound holds throughout it.

Fix $q\in [0,1]$ and $\epsilon >0$. The setis open. It is also dense, by the following explicit finite approximation. Given $K$ and tolerance $h>0$, partition $[0,1]$ into $N$ equal subintervals and choose $(j/N,y_j)\in K$ at each left endpoint. Above that subinterval put the segmentEach segment lies within $\sqrt{1+q^2}/N$ of its chosen point in $K$. Add a finite $h/2$-net of points of $K$ to their union, ensuring the reverse Hausdorff inclusion. For large $N$ the resulting compact set $K^{\prime }$ belongs to $\mathcal{X}$ and has Hausdorff distance less than $h$ from $K$. The image of each segment under $L_t$ has length $|t-q|/N$, and the added points contribute zero length. Henceso $K^{\prime }\in U(q,\epsilon )$.

Take a finite grid of $q$'s whose $\epsilon$-neighborhoods cover $[0,1]$. The finite intersection of the open dense sets $U(q,\epsilon )$ is dense and implies ${\sup }_{0\le t\le 1}{m}_t(K)<2\epsilon$. Thusis open and dense. The Baire category theorem gives a compact $K\in {\bigcap }_{r\ge 1}{V}_{1/r}$, and therefore $m_t(K)=0$ for every $t\in [0,1]$.

DefineThis is the continuous image of the compact set $K\times [0,1]$, hence compact. Its section at horizontal coordinate $t$ is $L_t(K)$, of measure zero. The Fubini theorem gives $|B|={\int }_0^1{m}_t(K)dt=0$. For every slope $x\in [0,1]$, horizontal surjectivity supplies $(x,y)\in K$, and $B$ contains the segment $(t,y+tx)$, $0\le t\le 1$, of length $\sqrt{1+x^2}\ge 1$. Four rotated copies, through angles $0,\pi /4,\pi /2,3\pi /4$, cover all unoriented directions. Their finite union $\mathcal{B}$ is compact, has area zero, and contains a unit subsegment in every direction:The point-line dual construction is the mechanism in Körner's construction; the density calculation above supplies the needed proof, rather than assuming that small-area sets automatically admit a suitable nested limit.

For the multiplier discussion, define $T_D$ by $\widehat{T_{D}g}(\xi )=1_{\{|\xi |\le 1\}}\hat{g}(\xi )$. The Plancherel theorem gives boundedness on $L^2$. We explain why a putative $L^p$ bound, $1<p<2$, would contradict Kakeya packing; duality of Lp spaces then treats $p>2$.

First, such a bound would force the vector-valued inequalityfor arbitrary directions $v_j$, where $P_v$ is the half-plane Fourier projection onto the half-plane $\xi \cdot v<0$. To see the important curvature step, let $T_R$ project onto the radius-$R$ disk and modulate by $e^{iR{v}_j\cdot x}$. Its conjugated symbol is $1_{\{|\xi +R{v}_j|\le R\}}$, tending almost everywhere to $1_{\{\xi \cdot v_j<0\}}$. Dilations give the same putative norm bound for every $R$. Apply this common operator to ${\sum }_j{ϵ}_j{e}^{iR{v}_j\cdot x}{g}_j$, average over independent random signs, and use the Khintchine inequality. Letting $R\to \infty$ gives the displayed estimate by $L^2$ convergence and Fatou lemma, first for finitely many smooth function functions and then by approximation. The disk has a boundary normal in every direction; a fixed polygon does not.

The geometric input for this overview is the standard finite Perron tree packing used in Fefferman's original proof: for arbitrarily small $\eta >0$ one obtains long thin rectangles $R_j$ with $A={\sum }_j|R_j|$ and $|{\bigcup }_j{R}_j|\le \eta A$, while fixed longitudinal translates $R_j^{\prime }$ are pairwise disjoint. This is a quantitative finite arrangement, stronger than merely having a compact null set. The splitting/sliding procedure subdivides an angular triangle into narrow triangles and overlaps their bases; the extensions along their axes separate in reverse order. Its area estimate has the form ${\alpha }^{2m}+2(1-\alpha )$ relative to the original total triangle area: the merged central part shrinks by ${\alpha }^2$ at each generation, and the accumulated caps contribute at most $2(1-\alpha )$. Taking $\alpha$ close to one and then $m$ large makes the ratio arbitrarily small. Inscribed rectangular portions retain a fixed proportion of the total area. The reflected extensions explain why the translates can be disjoint even though the original rectangles overlap strongly.

Here is the analytic contradiction, with the relevant powers explicit. Take $g_j=1_{R_j}$. In coordinates parallel and perpendicular to the long axis $v_j$, the directional Hilbert transform integrates only along that axis. If the longitudinal interval is $[0,\ell ]$, then outside itOn a fixed translate such as $s\in [5\ell ,6\ell ]$, this has magnitude at least ${\pi }^{-1}\log (6/5)$. Since $P_v=(I-i{H}_v)/2$ up to the harmless choice of half-plane sign, $|P_{v_j}{g}_j|\ge c_0>0$ on $R_j^{\prime }$. Their disjointness gives a lower bound $c_0{A}^{1/p}$ for the vector-valued output norm.

Writing $h={\sum }_j{1}_{R_j}$, Hölder's inequality for $p<2$ givesThe putative vector-valued inequality would implywhich is impossible as $\eta \downarrow 0$. The disk multiplier is self-adjoint, so a bound for $p>2$ would give one for its conjugate exponent below two. Thus the disk multiplier is bounded only at $p=2$ among $1<p<\infty$. This explains both the random-sign step and the precise geometric amplification; it is not an assertion that frequency rectangles by themselves produce a logarithmic norm blow-up.

Use a Boolean circuit of unbounded-fan-in AND and OR gates, with negations pushed to the input Boolean literals. Its circuit depth is the largest number of AND/OR gates on an input-to-output path, and its circuit size $M$ counts these gates. Constants and Boolean literals may be supplied as inputs. Equivalent standard size conventions only enlarge the absolute constants. One can merge adjacent gates of the same type; the depth-reduction argument below keeps the two possible normal forms available at each gate.

A random restriction with parameter $p$ independently leaves each variable live with probability $p$ and otherwise fixes it to zero or one with probability $(1-p)/2$ each. The Håstad switching lemma states that for a width-$w$ DNF or conjunctive normal form $F$,Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most $s$ has both a DNF and a conjunctive normal form of width at most $s$ and has real multilinear degree at most $s$. Indeed every leaf condition is a product of at most $s$ factors $x_i$ or $1-x_i$; sum the accepting leaves. The switching lemma controls the canonical decision tree, hence implies this representation bound.

We detail the Boolean circuit simplification parameters. First use a $1/10$-random restriction. For a bottom AND gate, let $X$ count its live Boolean literals on the event that no fixed Boolean literal kills it. For $w$ distinct Boolean literals,Thus the probability of retaining more than $s$ live Boolean literals without becoming constant is at most $5^{-s}$. The same calculation applies to bottom OR gates, with the opposite killing value. Repeated Boolean literals are removed and contradictory Boolean literals make a constant gate. A union bound makes all nonconstant bottom gates width at most $s$, except with probability at most $M_0{5}^{-s}$.

Now apply $d-1$ successive restrictions, each retaining probability $1/(10s)$ of the remaining variables. At a two-layer gate, the current bottom forms are width-$s$ DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most $s$ by $2^{-s}$. Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most $s$, and merge its outer gate with the adjacent gate of the same type. This removes one layer. Repeat upwards until the output has a depth-$s$ decision tree.

The bookkeeping matters: although a decision tree may give $2^s$ clauses, each subsequent switching event is charged to the corresponding original Boolean circuit gate, not to each newly created clause. The lemma permits any number of terms. Each original gate is charged once, so the sum of the failure probabilities is at most $M{2}^{-s}$, without an extra exponential size factor. Conditioning on successful preceding stages is harmless because each next restriction is fresh and the width bound holds for every preceding success. For a general Boolean circuit the conjunctive normal form or DNF representation at a shared gate can be chosen separately for each outgoing use; no extra gates need to be counted as switching targets.

The composed restriction has live-variable probabilityFixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimateFor $d=1$, the initial bottom-gate argument alone gives this conclusion. This is a depth-reduction estimate, not the desired Fourier-tail theorem used as a black box.

Next derive exactly how restrictions affect the Fourier-Walsh transform. Let $J$ be the random live set and $a$ the fixed assignment outside $J$. With ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, the restricted coefficient at $U\subset J$ isOrthogonality of the fixed-coordinate characters eliminates cross terms after averaging over $a$. Thereforeand then averaging over $J$ gives the expected Fourier weight after a random restriction identityThe original high-degree tail is not preserved: each original coefficient is weighted by a binomial distribution survival probability. On successful restrictions the left-hand tail vanishes; on failures it is at most one by Parseval's identity and $0\le f_{\rho }\le 1$. Hence its expectation is at most $M{2}^{-s}$.

Put $u=t^{1/d}$. If $u\ge 40$, choose $s=\lfloor u/40\rfloor \ge 1$ and the preceding value of $p$. For every $|S|>t$, the binomial distribution mean satisfiesIts variance is at most $\mu$. The Chebyshev inequality givesThus the exact expectation identity bounds at least half the original tail above $t$, andWhen $u<40$ the same bound follows from the trivial total-weight bound ${\sum }_S|\hat{f}(S){|}^2\le 1$. We obtain explicit absolute constants,This supplies the requested overview of the Linial-Mansour-Nisan theorem with the actual switching scale, gate-count bookkeeping and restriction-to-Fourier calculation. The argument uses the unbounded-fan-in AND/OR Boolean circuit basis; allowing arbitrary gates would make the theorem false, since one parity gate could have all its nonconstant Fourier weight at level $n$. The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.