Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 82 (Fourier Analysis)

The Fejér kernel for the printed normalization isIts endpoint coefficients at $\pm N$ are zero. It is nonnegative, and integrating its Fourier series gives ${\int }_{\mathbb{T}}{F}_N=1$. Hence ${\tilde{S}}_N(f)=f\ast F_N$ andThus the absolute constant can be $C=1$. Positivity of the Fejér kernel, rather than mere boundedness of its individual Fourier coefficients, is the reason this holds.

We give a quantitative construction for the whole open set, including the case of infinitely many component intervals. Pointwise divergence at a single point is insufficient here. Write $z=e^{2\pi it}$ and use normalized measure on $\mathbb{T}$.

First let $K$ be a finite union of closed arcs with $|K|\le 3\epsilon$, where $\epsilon$ is small. Choose a smooth function nonnegative function $u$, equal to one on $K$, with $u\le 1$ and $\eta :=\int u\le 6\epsilon$. This follows by making the transition regions around the finitely many arc endpoints sufficiently short. Define the analytic Herglotz integralIts real part is $(\eta +P[u](z))/(2\eta )>0$, where $P[u]$ is the disk Poisson integral, and $G(0)=1$. Smoothness of $u$ makes $G$ continuous and smooth function up to the circle; on $K$ its boundary real part is at least $1/(2\eta )$. The branch $H=\log G$ therefore has $H(0)=0$ andThe complex logarithm has no branch problem because $G$ lies in the right half-plane. Its smooth function boundary values give absolutely summable Taylor coefficients. Choose an analytic polynomial $A$, with zero constant coefficient, uniformly within $1/4$ of $H$ on the closed disk. Put $P(t)=\mathrm{Im}A(e^{2\pi it})/\pi$. Then $\Vert P{\Vert }_{\infty }\le 1/2+1/(4\pi )<1$.

If $D=\mathrm{deg}A$ and $m>D$, the modulated trigonometric polynomial $Q(t)=e^{2\pi imt}P(t)$ has spectrum in $[m-D,m+D]$. A sharp Fourier partial sum at $m$ selects exactly the negative-frequency half of $P$, since $A(0)=0$:Consequently, for every $t\in K$,The carrier frequency $m$ can be arbitrarily large. This compact-set Fourier amplification lemma uses a bounded imaginary part to obtain a large one-sided Fourier multiplier; no assertion about pointwise divergence is used.

Now let $E$ be any open set of measure $\delta$. DefineIf this is zero take $f=0$. Otherwise choose a decreasing sequence ${\delta }_j\downarrow 0$, with ${\delta }_1=\delta$, so small for $j\ge 2$ thatFor $j=1$ this inequality also holds: $B(\delta )>4$ and $B(\delta )/2\ge B(\delta )/4+1$. Let $L_j$ be an increasing compact exhaustion of $E$.

Using compact batching of a small open set, we recursively choose finite closed-arc unions $K_j\subset E$, of measure at most $3{\delta }_j$, such that $L_j$ is covered by the interiors of $K_1,\dots ,K_j$ andHere is the measure-theoretic justification. At step $j$, the uncovered portion has measure at most ${\delta }_j$. Its intersection with $L_j$ after removing the previously covered interiors is compact, and can be covered by finitely many closed arcs lying in $E$ with total length at most ${\delta }_j$ plus an arbitrarily small excess. By inner regularity of Lebesgue measure, a further compact subset of the uncovered open portion captures all but ${\delta }_{j+1}$ of its measure; cover it similarly. The combined finite arc union has length at most $3{\delta }_j$. This both covers the outstanding part of $L_j$ and ensures the next remainder estimate. In particular $E\subset {\bigcup }_j{K}_j$.

Apply the finite-arc construction to $K_j$ to get $P_j$ of degree $D_j$. Choose carriers $m_j$ recursively so that the bands $[m_j-D_j,m_j+D_j]$ are positive and strictly ordered with no overlap. SetThe frequency-separated Fourier block series and the Weierstrass M-test give a continuous complex-valued function with $\Vert f{\Vert }_{\infty }\le {\sum }_j{2}^{-j}=1$. At the cutoff $m_j$, all earlier bands have been included in full and every later band is absent. Thus on $K_j$,Every point of $E$ lies in some $K_j$, soValues of $\psi$ outside $0<\delta \le 1$ may be defined arbitrarily. The construction handles an arbitrary open set, not just one point or a finite collection of intervals. It also prevents cancellation explicitly: earlier bands contribute a bounded complete sum, and later bands contribute nothing at the chosen cutoff.

The printed interval has a typo: its right endpoint must be $2/3+\delta$, rather than $1/3+\delta$. Keep $\varphi$ as an unnormalized indicator function; only $\psi$ is normalized to have integral one. Thus useWith the Boolean literal printed interval, the convolution vanishes at $2/3$, so a sequence consisting entirely of $2/3$ is already a counterexample to the proposed majorization. For the corrected interval and every $t\in [1/3,2/3]$, all $t-s$ with $|s|\le \delta$ belong to the support of $\varphi$. Hence $f(t)=1$ there. Everywhere $0\le f\le 1$, giving $S_N\le {\sum }_{n\le N}f(u_n)$, including interval endpoints.

Put $L=1/3+2\delta$. For $k\ne 0$, direct integration and the convolution theorem give the exact Fourier coefficientsIn particular,This also supplies the required justification of the Fourier series. The convolution $f$ is continuous: it is the overlap length of two moving intervals, divided by $2\delta$. Its Fourier coefficients are absolutely summable, so the corresponding Fourier series converges uniformly to a continuous function $g$. Termwise integration gives $\hat{g}(k)=\hat{f}(k)$; the permitted uniqueness assertion applied to $f-g$ yields $g=f$.

Let $A_k={\sum }_{n\le N}{e}^{2\pi ik{u}_n}$. Split the absolutely convergent Fourier series at the arbitrary real cutoff $M>1$:There are fewer than $2M$ low-frequency terms and each coefficient has magnitude at most $L<1$. For the tail, $|A_k|\le N$ and ${\sum }_{|k|\ge M}{k}^{-2}\le C/M$. ThereforeThis proves the requested interval discrepancy estimate without an unjustified sharp truncation of the Fourier series.

For a nonzero integer $b$, let $a$ be the nearest integer to $b\sqrt{2}$. The integer $a^2-2b^2$ is nonzero, and $|a|\le \sqrt{2}|b|+1/2$. The suggested factorization yieldsThis is stronger than the stated lower bound for the fractional part, since the distance to the nearest integer is at most that fractional part. For $u_n=n\sqrt{2}$, the geometric series and $|\sin (\pi t)|\ge 2\Vert t{\Vert }_{\mathbb{R}/\mathbb{Z}}$ giveThus the low-frequency contribution is $O(M^2)$. Choose $M=\lceil 100N^{2/5}\rceil$ and $\delta =(2\sqrt{M}{)}^{-1}$; these choices satisfy $0<\delta <1/10$ for every $N\ge 1$. Both $\delta N$ and $N/(\delta M)$ are $O(N^{4/5})$, and so is $M^2$. Hence

Use the density form of the Szemerédi theorem: for fixed $\alpha >0$ and length $r$, every sufficiently large subset of $\{1,\dots ,N\}$ of size at least $\alpha N$ contains a nonconstant arithmetic progression of length $r$, as established in Szemerédi's density theorem. This theorem supplies a progression, not the desired averaging configuration; we now select the actual indices.

Take $r=2k+1$. Write the resulting progression asand put $y=a+kd\in A$. If $k=2m$ is even, select $y-d,y+d,\dots ,y-md,y+md$. These are $2m=k$ distinct members of the progression, and each opposite pair sums to $2y$. If $k=2m+1$ is odd, select those $2m$ opposite points together with $y$ itself. All $k$ selected points are distinct, and their sum is again $ky$. The case $k=1$ simply selects $y$.

In both cases the indices stay between $0$ and $2k$ and the difference $d$ is nonzero. Thus the precise answer isNo deletion of diagonal solutions and no multidimensional density theorem is needed. The averaging point is allowed to be one of the selected points, as it is in the odd case.

Use the uniform probability measure on the Boolean hypercube. The influence of a variable is the flip probabilityThe polynomial defining $f$ is interpreted over ${\mathbb{F}}_2$. Flipping the first coordinate adds $x_2+\cdots +x_n$ modulo two. This nonempty parity is balanced for $n\ge 2$, so

An explicit Tribes function works for every $n\ge 2$. Choose the largest integer $w\ge 1$ with $w{2}^w\le n$, let $m=\lfloor 2^w\log 2\rfloor$, and take the OR of $m$ disjoint ANDs of $w$ coordinates. Ignore the unused coordinates. Its zero probability is $(1-2^{-w}{)}^m$, between $1/4$ and $3/4$, and a used coordinate has influenceHere $n<2^{w+1}(w+1)$ by maximality. For the balance claim, $w=1$ gives probability $1/2$; for $w\ge 2$, $m\ge 2^w\log 2-1$ gives zero probability at most $e^{-\log 2+2^{-w}}<3/4$, while $(1-1/q{)}^q\ge 1/4$ for $q=2^w\ge 2$ gives a lower bound $(1/4{)}^{\log 2}>1/4$. Only the example was requested, but these checks fix its parameters unambiguously.

For the lower bound we prove the required consequence of Beckner's inequality with constants. Write the Fourier-Walsh transform as $f={\sum }_S\hat{f}(S){\chi }_S$, where ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}(f{\chi }_S)$. The discrete derivative of a Boolean function is $D_{i}f=(f-f(\cdot +e_i))/2$. Since $f$ takes values zero and one, $D_{i}f$ takes values $0,\pm 1/2$. Consequently Parseval's identity givesThe factor four is required for the printed $0/1$ convention. Also $V:=\mathrm{Var}(f)={\sum }_{S\ne \varnothing }|\hat{f}(S){|}^2\ge 3/16$ under the balance hypothesis.

The true Beckner's inequality states $\Vert T_{\rho }h{\Vert }_q\le \Vert h{\Vert }_p$ for $1<p\le q<\infty$, $0\le \rho \le \sqrt{(p-1)/(q-1)}$, with $T_{\rho }h={\sum }_S{\rho }^{|S|}\hat{h}(S){\chi }_S$. Apply it with $p=3/2$, $q=2$, $\rho =1/\sqrt{2}$ to $h_i={\chi }_{\{i\}}{D}_{i}f$, a function independent of coordinate $i$. Its nonzero values still have magnitude $1/2$. We obtainLet $a={\max }_i{I}_i(f)>0$. For an integer $\ell \ge 1$, the low-degree Fourier weight satisfiesFor the high-degree part the total influence identity givesTogether these imply $4V\le na(2^{\ell -1}{a}^{1/3}+1/(\ell +1))$.

Suppose, seeking a contradiction, that $a<\log n/(100n)$, with natural logarithms. Then $a<1/(100e)$ and $\ell =\lfloor \log (1/a)/(6\log 2)\rfloor \ge 1$. Hence $2^{\ell -1}{a}^{1/3}\le a^{1/6}/2$. Put $y=\log n$. The first term on the right is bounded bythe middle expression is maximized at $y=7$. Moreover $\log (1/a)\ge y/2$, since $y\le 100e^{y/2}$. ThusWe would have $4V<1/10$, contradicting $4V\ge 3/4$. ThereforeThis derives the stated Kahn-Kalai-Linial theorem bound from the actual noise operator on the Boolean hypercube inequality, rather than using the desired conclusion as an input.

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.