Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 13 (Quasirandomness)

Use uniform expectations on the nonempty sets $X,Y$. Define the rectangle fourth moment and the normalized cut norm byThe first quantity is nonnegative, sinceits fourth root is the box norm. To bound the cut norm, fix $A,B$ and put $T={\mathbb{E}}_{x,y}f(x,y)1_A(x)1_B(y)$. The Cauchy-Schwarz inequality in $y$ givesA second Cauchy-Schwarz inequality, now in $(x,x^{\prime })$, yieldsbecause the squared mean of $1_A(x)1_A(x^{\prime })$ is at most one. Taking the maximum over rectangles gives the first direction of cut norm and rectangle fourth-moment equivalence:The normalization divides the rectangle sum by $mn$ and the fourth-moment sum by $m^2{n}^2$, so the bound is independent of the two set sizes.

For the reverse direction, rectangular discrepancy also controls pairings with arbitrary bounded real test functions. If $u:X\to [-1,1]$ and $v:Y\to [-1,1]$, decompose each into its positive and negative parts. For example, the layer cake representation givesEach of the four sign combinations in $u(x)v(y)$ is thus an integral of rectangular indicator functions. The triangle inequality and the definition of the cut norm show thatNow fix $x^{\prime },y^{\prime }$ and take $u(x)=f(x,y^{\prime })$, $v(y)=f(x^{\prime },y)$. The hypothesis $|f|\le 1$ makes these admissible tests. Multiplying their pairing by $f(x^{\prime },y^{\prime })$ and averaging givesConsequentlyTogether with part (a), this proves cut norm and rectangle fourth-moment equivalence. The intended equivalence is quantitative smallness: along any family of bounded functions, the normalized rectangle fourth moments tend to zero if and only if the normalized cut norms tend to zero. It does not assert equality of the two constants or norms.

For the unheaded existence request, use the probabilistic method. Choose every value $f(x,y)$ independently and uniformly from $\{-1,1\}$. For a rectangle with $x\ne x^{\prime }$ and $y\ne y^{\prime }$, its four entries are distinct, so independence and the zero mean of each sign give expectation zero for their product. If $x=x^{\prime }$ or $y=y^{\prime }$, the product is identically one. The number of ordered rectangles in this union of diagonal cases isTherefore the random sign rectangle fourth moment has expectationSome sign function has $Q(f)$ at most this expectation. Applying the bound in part (a) to that same function gives the simultaneous choicesBoth constants tend to zero whenever both dimensions tend to infinity, without any assumption on their relative rates of growth.

We prove a weighted version of the Szemerédi regularity lemma, which is sufficient for the grid application. For disjoint nonempty vertex sets $U,W$ in a graph, write $d(U,W)=e(U,W)/(|U||W|)$ for their edge density of a bipartite graph. Call the pair $\epsilon$-regular if every $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ with $|U^{\prime }|\ge \epsilon |U|$ and $|W^{\prime }|\ge \epsilon |W|$ satisfies $|d(U^{\prime },W^{\prime })-d(U,W)|\le \epsilon$.

The weighted Szemerédi regularity lemma states that, for every $0<\epsilon <1$, there are integers $M,v_0$ such that every graph on $v\ge v_0$ vertices has a set partition into at most $M$ nonempty cells $V_1,\dots ,V_k$, each of size at most $\epsilon v$, for whichThe sum is ordered. The cells need not have equal sizes; their weights replace the usual unweighted count of bad pairs.

To prove it, start with $k_0=\lceil 2/\epsilon \rceil$ nearly equal cells, taking $v\ge k_0$. Each has size at most $v/k_0+1\le \epsilon v$. Define the regularity energyHere even diagonal rectangles use the mean adjacency indicator, counting ordered pairs of vertices. Thus $0\le q\le 1$. Under a refinement, the old rectangle density is the weighted mean of the new ones, and the refinement variance identity for regularity energy givesIn particular refinement cannot decrease energy.

If the irregular-pair weight exceeds $\epsilon v^2$, choose witness subsets $U^{\prime }\subseteq U$, $W^{\prime }\subseteq W$ for every irregular unordered pair, and split each cell simultaneously by all its witnesses. There are at most $k-1$ such subsets in any one cell, so the new number of cells is at most $k{2}^k$. In an irregular rectangle, its witness has relative area at least ${\epsilon }^2$ and density discrepancy greater than $\epsilon$. Since the witness rectangle is now a union of refined rectangles, the Cauchy-Schwarz inequality applied to their weighted density discrepancies bounds the variance contribution from below bySumming over both orientations of all irregular pairs raises $q$ by more than ${\epsilon }^5$. Since $q\le 1$, after at most $\lceil {\epsilon }^{-5}\rceil$ rounds the required weight bound must hold. The finite recurrence $k\mapsto k{2}^k$, starting at $k_0$, supplies $M(\epsilon )$; all cells remain small because we only refine. This proves the stated weighted Szemerédi regularity lemma.

We next derive the triangle removal lemma from this version. First, three disjoint classes $U,W,Z$ whose pairs are $\epsilon$-regular pairs of density at least $d$ have many triangles if $\epsilon \le d/2$ and $\epsilon \le 1/4$. Fewer than $\epsilon |U|$ vertices of $U$ have fewer than $(d-\epsilon )|W|$ neighbours in $W$: otherwise that set of vertices, paired with all of $W$, would violate regularity. The same holds for $Z$. For each of the at least $(1-2\epsilon )|U|$ remaining vertices, both neighbour sets have relative size at least $d-\epsilon \ge \epsilon$. Regularity of $(W,Z)$ then supplies at least $(d-\epsilon )$ times the product of those two neighbour-set sizes edges. Thus the regular triangle counting lemma, also for unequal class sizes, givesFor a desired deletion tolerance $0<\eta <1$, take $\epsilon =\eta /100$, $d=\eta /4$, and a weighted regularity partition with at most $M=M(\epsilon )$ cells. Put $\tau =\epsilon /M$. Delete edges inside cells, between irregular pairs, between regular pairs of density less than $d$, and incident to cells smaller than $\tau v$. The first two deletions each cost at most $\epsilon v^2/2$. The sparse-pair deletion costs at most $d{v}^2/2$. For the last deletion, small-cell deletion in weighted regularity removes at most $M\tau v=\epsilon v$ vertices and at most $\epsilon v^2$ incident edges. The total is bounded byA triangle surviving these deletions would lie in three distinct cells, all of size at least $\tau v$, with all their pairs regular and of density at least $d$. The original graph would then have at least $d^3{\tau }^3{v}^3/16$ triangles. Therefore, witha graph on sufficiently many vertices with at most $\kappa v^3$ triangles can be made triangle-free by deleting fewer than $\eta v^2$ edges. This establishes the triangle removal lemma with every parameter depending only on $\eta$.

Now apply a tripartite graph encoding of a grid. Take separate vertex classes $X=[N]$, $Y=[N]$, $Z=\{2,\dots ,2N\}$. For each grid point $(x,y)$ in the given set, put in the three edgeswhere their endpoints belong respectively to $X\times Y$, $X\times Z$, and $Y\times Z$. Each point supplies a triangle. These $|A|$ triangles are edge-disjoint triangles, since any one of the three edge types uniquely determines the point that supplied it.

Conversely, any triangle with vertices $x\in X$, $y\in Y$, $z\in Z$ forces the three pointsto belong to $A$. Put $d=z-x-y$. For $d\ne 0$ these form a corner in an integer grid; for $d=0$ they all arise from the same grid point. Thus if there is no corner, the graph has exactly $|A|\le N^2$ triangles, yet destroying all triangles requires at least $|A|\ge \delta N^2$ edge deletions.

We may suppose $0<\delta \le 1$, since larger densities make the request vacuous. Use the triangle removal lemma with $\eta =\delta /32$. Our graph has $v=4N-1$ vertices, so, for sufficiently large $N$, its bound $N^2$ on the number of triangles is at most $\kappa v^3$. The lemma would delete fewer thanedges to destroy all triangles. This contradicts the lower bound $\delta N^2$ from the edge-disjoint family. Hence every sufficiently large positive-density square grid contains a nondegenerate corner, proving the requested corners theorem and in particular the existence of a suitable $N$.

There is a normalization omission in the printed conclusion: the discrepancy of a count of pairs must be bounded by a small function of the energy excess times $N^2$. We prove this normalized result, then give a counterexample to the literal bound without $N^2$. Write $ϵ$ for the energy excess parameter to avoid confusing it with an element of the third set.

For Fourier analysis on a finite abelian group, use $e_N(t)=e^{2\pi it/N}$ andCharacter orthogonality, ${\mathbb{E}}_x{e}_N(rx)=1$ for $r=0$ and zero otherwise, gives Fourier inversion and the Parseval identity on a finite group:Put $u=1_A$, $v=1_B$, $w=1_C$. Expanding the constraint $a_1+a_2=a_3+a_4$ by the same character orthogonality gives the additive energy identityThus ${\sum }_{r\ne 0}|\hat{u}(r){|}^4\le ϵ$, and every nonconstant Fourier coefficient on a finite abelian group of $u$ has modulus at most ${ϵ}^{1/4}$. Expanding the constraint in the triple count $T$ givesThe Cauchy-Schwarz inequality yieldsThe first squared norm is $\gamma$ by the Parseval identity on a finite group. For the second, multiplication by $2$ on ${\mathbb{Z}}_N$ has kernel size $h=\gcd (2,N)$ and every element of its image has exactly $h$ preimages. HenceThis proves that additive energy controls three-term progression mixing, including for even moduli:Thus the intended density-error function can be $F(ϵ)=\sqrt{2}{ϵ}^{1/4}$, which tends to zero. For odd moduli the factor $\sqrt{2}$ can be replaced by one.

To see why the literal unnormalized conclusion is false, take $N=q^2$ and let all three sets be the subgroup of multiples of $q$. Their densities are $1/q$. Every choice of three entries of that subgroup determines the fourth entry of an additive quadruple, so its energy is $q^3$. The excess parameter isEvery pair $(a,b)$ in the subgroup determines $c=2b-a$ there, giving $T=q^2$, whereas $\alpha \beta \gamma N^2=q$. Their difference is $q^2-q\to \infty$, which cannot be bounded by any function of $ϵ$ tending to zero. The missing $N^2$ is therefore a genuine source defect, not an alternative Fourier transform normalization.

The positive-power length assertion is an asymptotic one: it requires $N$ sufficiently large in terms of the density. Read literally for every $N$, it fails when $N=2$, $\delta =1/2$ and $A=\{1\}$, whose triple sumset is a singleton. We prove the intended result with this necessary qualification and an explicit positive exponent.

Embed the interval into the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$ with $M=8N$, and set $u=1_A$, $\alpha =|A|/M\ge \delta /8$. Since all integer triple sums lie in $[3,3N]$, this embedding introduces no collisions between distinct sums. Use normalized Fourier coefficients on a finite abelian group and normalized convolution on a finite group, and putThe function $F$ is nonnegative and has mean ${\alpha }^3$, so some $t_0$ satisfies $F(t_0)\ge {\alpha }^3$. We show that a whole translated Bohr set is contained in its positive support, hence in the triple sumset.

Put $\theta ={\alpha }^2/8$, $\rho =\alpha /4$, and define the large spectrumThe Parseval identity on a finite group gives ${\sum }_r|\hat{u}(r){|}^2=\alpha$, soAlso $|\hat{u}(r)|\le \alpha$, and therefore ${\sum }_r|\hat{u}(r){|}^3\le {\alpha }^2$. Using Fourier inversion and the convolution theorem on a finite group, for $b\in B$ we obtainConsequently $F(t_0+b)\ge {\alpha }^3/2>0$. This proves the translated Bohr neighborhood in a triple sumset:It remains to produce a long ordinary integer arithmetic progression in this translate; we supply the simultaneous approximation and the lifting argument. SetThus $d=|\Gamma |\le D$. Partition the $d$-dimensional unit cube into $Q^d$ boxes of side $1/Q$. The $Q^d+1$ pointscontain two in the same box by the pigeonhole principle. Their index difference gives an integer $q$ with $1\le q\le Q^d<M$ andIn particular $|e^{2\pi irq/M}-1|\le 2\pi /Q$. The identity $z^j-1=(z-1)(1+\cdots +z^{j-1})$ on the unit circle now shows thatAll residues $t_0+jq$ therefore lie in the triple sumset. Let $s_j\in [3,3N]$ be their actual integer representatives. Their successive differences are congruent to $q$ modulo $M$, and each lies in $[-(3N-3),3N-3]$, which is contained in $(-M/2,M/2)$. There is at most one integer in this interval in any specified residue class, so every difference $s_{j+1}-s_j$ is the same integer. It is nonzero because $0<q<M$. Thus the $s_j$ form an ordinary integer arithmetic progression of distinct elements, even though $M$ is composite. Reversing it if necessary makes the common difference positive.

For sufficiently large $N$, we have $Q\ge \frac{1}{2}{M}^{1/(D+1)}$ and $\rho \ge \delta /32$, whenceAbsorb this fixed prefactor by decreasing the exponent: withthe last lower bound is at least $N^{r_{\delta }}$ once $N$ is sufficiently large in terms of $\delta$. This proves a polynomial-length progression in $A+A+A$ by the polynomial-length progression in a dense triple sumset argument, without replacing the triple sumset by a fourfold difference set.