Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 7 (Restriction and Kakeya Phenomena)

For a nonempty bounded set, let $N_{\delta }(E)$ be the least number of radius-$\delta$ balls covering $E$. The lower and upper Minkowski dimensions are respectivelyUsing comparable cubes or ball diameters gives the same limits. For an unbounded set one must specify a local or bounded-piece convention; these are the usual bounded-set definitions used in the Kakeya set problem.

For the digit set, fixing the first $k$ digits gives exactly $3^k$ cylinders in intervals of length $9^{-k}$. They cover the set with at most $3^k$ balls of comparable radius. Their base-nine prefix integers are separated by at least two, so these containing intervals have gaps at least $9^{-k}$. Choosing one point in each cylinder shows that a radius-$9^{-k}$ ball meets at most a bounded number of chosen points. Hence $N_{9^{-k}}(Q)\asymp 3^k$. For $9^{-(k+1)}<\delta \le 9^{-k}$, monotonicity sandwiches the covering number between constant multiples of $3^k$ and $3^{k+1}$. This proves the box-counting dimension of separated digit sets formula here:A planar Besicovitch set is a bounded set of zero Lebesgue measure containing a unit line segment in every unoriented direction. The following proof in fact applies to every bounded planar Kakeya set, whether its area is zero or positive.

Choose $M\asymp {\delta }^{-1}$ directions equally spaced in an angular interval of length, say, $\pi /2$, and one segment of the set in each direction. Let $T_j$ be its rectangle of length one and width comparable to $\delta$, lying in the $C\delta$ neighborhood $E_{C\delta }$. Put $F={\sum }_j{1}_{T_j}$. Then $\int F\asymp M\delta \asymp 1$. Two such Kakeya tubes at angle $\alpha$ have overlap at most $C{\delta }^2/\alpha$, since the intersection of their supporting strips is a parallelogram of that area. The trivial bound $C\delta$ applies for nearly parallel tubes. Thus, uniformly over their translations,Sum these intersections. Each row contributes at most $C\delta \log (2/\delta )$, so $\int F^2\lesssim \log (2/\delta )$. The Cauchy-Schwarz inequality on the union now gives the planar Kakeya neighborhood lower boundA cover of $E$ by $N_{\delta }(E)$ radius-$\delta$ balls covers $E_{C\delta }$ by their fixed-factor enlargements. Hence $N_{\delta }(E)\gtrsim {\delta }^{-2}/\log (2/\delta )$. Boundedness gives the matching upper exponent $N_{\delta }(E){\lesssim }_E{\delta }^{-2}$. Taking the lower and upper limits provesThe logarithmic neighborhood loss is compatible with zero area; it still forces full dimension.

A finite-field Kakeya set, also called a finite-field Besicovitch set, is a subset containing a complete affine line in a vector space $a+{\mathbb{F}}_{p}v$ in every nonzero direction $v$, with scalar multiples counted as the same direction. The line's translate may depend on the direction.

For odd $p$, take the union of the lines $y=mx-m^2/4$, $m\in {\mathbb{F}}_p$. Completing the square gives $x^2-y=(m/2-x{)}^2$. Thus that union is exactly $K_0=\{(x,y):x^2-y\text{ is a square, including zero}\}$. For each fixed $x$ there are $(p+1)/2$ such $y$, so $|K_0|=p(p+1)/2$. It contains every nonvertical slope. Add the vertical line $x=0$, whose overlap with $K_0$ has $(p+1)/2$ points. The tangent-line finite-field Kakeya construction consequently hasThe prime two is irrelevant to this asymptotic statement and can be handled by taking its whole plane.

For the high-dimensional lower bound, we give a direct polynomial method in combinatorics proof, which yields a stronger estimate. Suppose a finite-field Kakeya set $K\subseteq {\mathbb{F}}_p^n$ has fewer than $\left(\genfrac{}{}{0ex}{}{p+n-1}{n}\right)$ points. That binomial coefficient is the dimension of a bounded-total-degree polynomial space of polynomials of total degree at most $p-1$. Evaluation at the points of $K$ imposes fewer linear conditions than this dimension. By the rank-nullity theorem, there is a nonzero polynomial $P$ of total degree $d\le p-1$ vanishing on $K$.

For every nonzero $v$ choose the line $a_v+tv\subseteq K$. The polynomial $P(a_v+tv)$ in $t$ has degree at most $d<p$ and vanishes at all $p$ field elements, so it vanishes identically. Its coefficient of $t^d$ is the leading homogeneous polynomial part $P_d(v)$. Thus $P_d(v)=0$ for every nonzero $v$. The case $d=0$ is already impossible for a nonzero constant vanishing on a nonempty set; for $d>0$, the absence of a constant term in this homogeneous polynomial also gives $P_d(0)=0$.

A polynomial of degree less than $p$ in each variable cannot vanish at every point of ${\mathbb{F}}_p^n$ unless it is zero. To see this, induct on $n$: fix the first $n-1$ variables, apply the one-variable root bound in the last variable, then apply the induction hypothesis to each resulting coefficient polynomial. This forces $P_d=0$, contradicting the choice of the leading part. We have proved the finite-field Kakeya polynomial boundAt $n=15$ this implies the required bound with an explicit absolute constant:The argument is valid in every prime characteristic and does not invoke the lower bound as an unproved theorem.

Use $\widehat{f\sigma }(x)={\int }_{S^1}f(\omega )e^{-2\pi ix\cdot \omega }d\sigma (\omega )$, with arclength measure. We first bound the transform for constant density. By rotational symmetry, $\hat{\sigma }(x)={\int }_0^{2\pi }{e}^{-2\pi ir\cos \theta }d\theta$, $r=|x|$. For $r\ge 1$, remove neighborhoods of width $h=r^{-1/2}$ about the stationary points $0,\pi$. Their contribution is $O(h)$. On each remaining interval integrate by parts using the phase derivative $2\pi r\sin \theta$. The boundary terms are $O((rh{)}^{-1})$, and the integral of the derivative of its reciprocal is bounded bySplitting at the stationary points gives the same bound on the other half of the circle. Together with the trivial estimate for bounded $r$, this proves $|\hat{\sigma }(x)|\lesssim (1+|x|{)}^{-1/2}$.

For merely measurable $f$ there is no reason that its amplitude permits this integration by parts. Instead use Gaussian positivity for even extension moments. SetExpand the fourth power and integrate first in $x$. The Fourier transform of a Gaussian givesAll exchanges of integrals are justified by bounded amplitudes, finite surface measure and the integrable Gaussian. The kernel is nonnegative and $|f|\le 1$ almost everywhere. Taking the absolute value of the integral therefore gives $0\le I_R(f)\le I_R(1)$. The preceding scalar decay estimate and polar coordinates yieldFor the last bound split at $1$ and $R$; the tail becomes an integrable $e^{-\pi s^2}/s$ integral after $r=Rs$. Since the Gaussian is at least $e^{-\pi }$ on the radius-$R$ ball, the local fourth-moment restriction estimate for the circle follows:Every constant here is independent of $f$ and $R$.

For the requested connection to Besicovitch sets, let $\delta$ be small and dilate the unit segments of a bounded planar Kakeya set by ${\delta }^{-2}$. Their $\delta$-neighborhoods become direction-separated rectangles of length ${\delta }^{-2}$ and width ${\delta }^{-1}$. A smooth circle cap of angular width $c\delta$ has a Fourier extension operator of magnitude at least $c^{\prime }\delta$ on such a rectangle: after removing the constant phase, the tangential phase variation is $O(c)$ and the normal variation is $O(c^2)$. A frequency modulation translates the rectangle to any desired location. Choose separated caps for the rectangle directions, and multiply their modulated densities by independent Rademacher random variables. Because the caps are disjoint, the input remains bounded by one.

Apply the local fourth-moment estimate in a ball of radius $C_E{\delta }^{-2}$ containing the rectangles, then take expectation over the Rademacher random variables. The fourth moment dominates the square of the sum of squared packet magnitudes, givingThere are $M\asymp {\delta }^{-1}$ rectangles, each of area $\asymp {\delta }^{-3}$, so the integral of their sum is $\asymp {\delta }^{-4}$. Cauchy-Schwarz forces their union area to be at least $c_E{\delta }^{-4}/\log (1/\delta )$. Scaling back gives $|E_{C\delta }|{\gtrsim }_{E}1/\log (1/\delta )$, the planar Kakeya neighborhood lower bound. The covering-number argument in Question 1 then gives both Minkowski dimensions equal to two.

For odd $p$, write $e_p(t)=e^{2\pi it/p}$ and use the discrete paraboloidHere surface integration means $p^{-2}{\sum }_P$, whereas ambient norms below use unnormalized counting measure on ${\mathbb{F}}_p^3$. With the negative-phase transform convention,When $x_3=0$, additive-orthogonality of characters makes this one at $x=0$ and zero at all other points of that plane. When $x_3\ne 0$, completing the two squares givesThe Quadratic Gauss sum identity is $G(t{)}^2=\chi (-1)p$, where $\chi$ is the Legendre symbol. For completeness, counting the preimages of a square gives $G(t)=\chi (t)G(1)$ for nonzero $t$. Also $|G(1){|}^2={\sum }_{u,v}{e}_p(u^2-v^2)=p$, by the invertible change $(u,v)\mapsto (u-v,u+v)$ and orthogonality of characters. Since $\overline{G(1)}=G(-1)=\chi (-1)G(1)$, the asserted square identity follows. Thus for $p\equiv 3(\mathrm{mod}4)$,Using positive phase instead changes the sign inside the character, not the magnitude or any norm estimate.

Define $Eg(x)=p^{-2}{\sum }_{\xi \in P}g(\xi )e_p(x\cdot \xi )$, and define $R^{\ast }(2\to q)$ as the smallest constant forThe adjoint relative to these measures is $E^{\ast }h(\xi )={\sum }_{x}h(x)e_p(-x\cdot \xi )$. Consequently $E{E}^{\ast }h=h\ast \hat{\sigma }(-\cdot )$, where convolution is the unnormalized ambient sum. Put $K=\hat{\sigma }(-\cdot )-1_{\{0\}}$. Its supremum is at most $p^{-1}$, so convolution by $K$ has ${\ell }^1\to {\ell }^{\infty }$ norm at most $p^{-1}$.

Under the unnormalized ambient Fourier transform on a finite group, the convolution multiplier of $\hat{\sigma }(-\cdot )$ is $p^3\sigma =p{1}_P$, up to the harmless reflection convention. Thus the multiplier of $K$ is $p{1}_P-1$, with maximum absolute value at most $p$. The Plancherel theorem gives ${\ell }^2\to {\ell }^2$ norm at most $p$. The Riesz-Thorin interpolation theorem between these two bounds gives ${\ell }^{4/3}\to {\ell }^4$ norm at most one for convolution by $K$. Convolution by $1_{\{0\}}$ is the identity, whose ${\ell }^{4/3}\to {\ell }^4$ norm is at most one for counting measure. Hence $\Vert E{E}^{\ast }h{\Vert }_4\le 2\Vert h{\Vert }_{4/3}$.

By Lp duality and Hölder's inequality, $\Vert E^{\ast }h{\Vert }_{L^2(\sigma )}^2=⟨E{E}^{\ast }h,h⟩\le 2\Vert h{\Vert }_{4/3}^2$. Taking adjoints proves the finite-field paraboloid fourth-moment extension estimateIn fact this argument works for both residue classes of odd primes.

If $p\equiv 1(\mathrm{mod}4)$, choose $i\in {\mathbb{F}}_p$ with $i^2=-1$. The complete line $\ell =\{(t,it,0):t\in {\mathbb{F}}_p\}$ lies in $P$. For $g=1_{\ell }$ the normalized surface $L^2$ norm is $p^{-1/2}$, and orthogonality of characters gives $Eg(x)=p^{-1}{1}_{\{x_1+i{x}_2=0\}}$. That annihilator plane has $p^2$ points, so the isotropic-line obstruction to finite-field restriction givesThis tends to infinity along these primes for every $q<4$, as required.

A Boolean function takes each vector of bits to either zero or one. Use independent uniform input bits; the influence of a variable is the probability that flipping that bit changes the value. A quite fair Boolean function has $1/4\le \mathbb{E}f\le 3/4$. All logarithms in the estimates below are natural, except where a base is explicitly written.

Here is a balanced tribes construction with unused coordinates valid for every $n\ge 2$. For each $w\ge 1$ put $m_w=\lfloor (\log 2)2^w\rfloor$, and choose the largest $w$ with $w{m}_w\le n$. Partition $w{m}_w$ of the bits into $m=m_w$ blocks of size $w$. Let $f$ be one when at least one block is all ones, and ignore the other bits. This is a tribes function. With $s=2^{-w}$, its zero probability is $(1-s{)}^m$.

For $w=1$ the function is a single bit and has mean $1/2$. For $w\ge 2$, $ms\le \log 2$ and $ms\ge \log 2-s$. The elementary inequalities $-s/(1-s)\le \log (1-s)\le -s$ giveThus both output probabilities are between one quarter and three quarters.

A used bit is pivotal exactly when the other $w-1$ bits of its block are one and every other block fails. Hence its influence is $2^{1-w}(1-2^{-w}{)}^{m-1}\le 2^{1-w}$; unused bits have zero influence. Maximality of $w$ gives $n<(w+1)m_{w+1}\le (w+1)(\log 2)2^{w+1}$. Also $w\le {\log }_{2}n$ for $n\ge 2$: this is immediate for $w=1$, while for $w\ge 2$ one has $w{m}_w\ge 2^w$. ThereforeThis proves the requested existence with room in the constant. The dimension-one boundary case cannot satisfy the printed logarithmic bound: a quite fair function of one bit is nonconstant and has influence one, whereas $10\log 1=0$. Thus the statement requires the usual nontrivial range $n\ge 2$ (or its intended large-$n$ interpretation).

Use normalized Fourier-Walsh transform coefficients $\hat{g}(\xi )=2^{-n}{\sum }_{x}g(x)(-1{)}^{x\cdot \xi }$. The Hamming weight $|\xi |$ counts the nonzero coordinates. Norms on the input cube use uniform probability, and a frequency integral here is counting over $\xi \in {\mathbb{F}}_2^n$. A common alternative normalization multiplies both sides of the requested comparison by the same factor and does not change it.

Beckner's inequality states that for $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube, with coefficients $\widehat{T_{\rho }g}(\xi )={\rho }^{|\xi |}\hat{g}(\xi )$, satisfies $\Vert T_{\rho }g{\Vert }_q\le \Vert g{\Vert }_p$. In particular choose $q=2$, $p=4/3$, $\rho =1/\sqrt{3}$.

Let $g=1_A$ and $\alpha =|A|/2^n$. Then $\Vert g{\Vert }_{4/3}^2={\alpha }^{3/2}$. On frequencies of weight at most two, ${\rho }^{2|\xi |}\ge 1/9$, so Beckner's inequality and Parseval's identity give the low-degree Fourier mass of a sparse Boolean set estimateThe indicator function is real and the cube characters are real, so the displayed squares equal the squared absolute values. Total Fourier weight is $\sum \hat{g}(\xi {)}^2=\Vert g{\Vert }_2^2=\alpha$. If $2^n>2003$, then $0<\alpha \le 1/2003$ and $9\sqrt{\alpha }\le 9/\sqrt{2003}<1/2$, since $2003>18^2$. ThereforeThis establishes the strict comparison for every power $N=2^n>2003$, not merely for an unspecified very large threshold. The original PDF supplies the density condition and Beckner request, both missing from the converted TeX.

We use the Bose-Chowla Sidon construction, deriving its difference property explicitly. Let $p$ be an odd prime and choose a generator $\theta$ of the multiplicative group of a finite field of the quadratic finite field extension ${\mathbb{F}}_{p^2}$. Such a generator cannot belong to ${\mathbb{F}}_p$, so $1,\theta$ are linearly independent over the prime field. For each $t\in {\mathbb{F}}_p$, the nonzero field element $\theta +t$ has a unique exponent $a_t$ modulo $p^2-1$, with ${\theta }^{a_t}=\theta +t$. The $p$ exponents are distinct.

Suppose $a_s-a_t=a_u-a_v$ in the cyclic group. Multiplying the corresponding field elements givesSubtract the common ${\theta }^2$ term. Linear independence of $1,\theta$ gives $s+v=u+t$ and $sv=ut$. Thus the two unordered pairs are the roots of the same monic quadratic polynomial, so $\{s,v\}=\{u,t\}$. Either $s=u,v=t$, giving the same ordered difference, or $s=t,v=u$, giving two zero differences. This is exactly the Sidon set property.

Choose the integer representatives in $\{1,\dots ,p^2-1\}$. Equality of integer differences implies equality modulo $p^2-1$, so their Sidon property persists in the integers. Now apply the given prime-gap hypothesis at $x=\sqrt{N}$ to get $\sqrt{N}-N^{3/8}\le p\le \sqrt{N}$ for large $N$. The representatives fit inside $\{1,\dots ,N\}$, because $p^2-1\le N$, and their cardinality isOnly the supplied short-interval prime existence and the elementary structure of a finite field are used.

Write $m=|A|$, choose $u=\lfloor N^{3/4}\rfloor$, and let $A_i$ count the points of $A$ in the length-$u$ window ending at $i$, for $1\le i\le N+u$. Each element occurs in precisely $u$ such windows, so ${\sum }_i{A}_i=um$. The Cauchy-Schwarz inequality consequently givesOn the other hand, a pair $a<b$ of difference $d=b-a<u$ belongs to exactly $u-d$ windows; larger differences contribute none. The Sidon set condition permits at most one pair for each positive difference $d$. ThereforeCombining these two estimates proves the sliding-window upper bound for Sidon sets:If $D=(N+u)/u$, the final inequality for this quadratic polynomial implies $m\le \sqrt{N+u}+D$; otherwise $m(m-D)>N+u$. With the chosen $u$, $D=O(N^{1/4})$ and $\sqrt{N+u}=\sqrt{N}+O(N^{1/4})$. ThusTogether with part (i)'s construction, this proves that the maximum cardinality is $\sqrt{N}+o(\sqrt{N})$. The lower and upper error terms need not have the same size to establish that asymptotic conclusion.