Let the blue edges form a graph $B$ on $N$ vertices, and suppose there is no blue copy of $H$. For every vertex $x$, the graph $B[N_B(x)]$ has maximum degree at most one. Indeed, if some $y\in N_B(x)$ had two neighbours $z,w$ inside $N_B(x)$, thenwould be the five blue edges of a copy of $H$.

Let $d=\Delta (B)$. If $d\ge 2k$, then a maximum-degree neighbourhood, being a matching plus isolated vertices, has an independent set of size at least $d/2\ge k$. This is a red $K_k$. We may therefore assume $d<2k$. Part (b) givesIf $d<\sqrt{k}$, the greedy independent-set bound gives $\alpha (B)\ge N/(d+1)>k$ once $N=C{k}^2/\log k$. If $\sqrt{k}\le d<2k$, then part (b) giveswhen $C$ is sufficiently large. In either case there is a red $K_k$, so

For every vertex $x$, the hypothesis $\Delta (G[N(x)])\le 1$ says that $G[N(x)]$ is a disjoint union of edges and isolated vertices. HenceThe locally sparse graph independence bound, with $f=2d$, now givesAs in part (a), bounded $d$ is absorbed by decreasing the absolute constant.

Apply the Shearer independence bound for a triangle-free graph. It states that an $n$-vertex triangle-free graph of maximum degree at most $d$ has an independent set of sizefor an absolute $c>0$. The result is immediate for bounded $d$ after reducing $c$, while the theorem gives the asserted logarithmic gain for $d$ large. Thus

For completeness, the key input in Shearer's proof is to expose a random independent set one degree scale at a time. Triangle-freeness makes every neighbourhood independent, so conditioning on earlier choices creates no edges inside the available neighbours. The expected gain at degree scale $j$ is $\Omega (n_j/d)$; summing over the $\Theta (\log d)$ nonempty scales gives $\Omega (n\log d/d)$. The entropy, or hard-core-model, form of the argument makes this scale calculation rigorous without losing vertices counted at adjacent scales.

Part (iii) gives at least ${\eta }^2|A{|}^3$ additive quadruples. By the Balog-Szemerédi-Gowers theorem, there is $A^{\prime }\subseteq A$ withThe Freiman-Ruzsa theorem places $A^{\prime }$ in a coset progression $P$ whose rank is bounded in terms of $\eta$ and which satisfiesThus $A^{\prime }$ has density at least $C_1(\eta {)}^{-1}$ inside $P$.

The Szemerédi theorem in a bounded-rank coset progression says that, for fixed rank and density, every sufficiently large such progression has a nontrivial four-term progression in every subset of that density. If $|A|\ge C(\eta )$ for a sufficiently large $C(\eta )$, then $|P|\ge |A^{\prime }|\ge c(\eta )|A|$ crosses this threshold. It gives a nontrivial four-term progression in $A^{\prime }$, which is also contained in $A$. This proves the claim with a constant depending only on $\eta$.

For $s\in {\mathbb{F}}_p^n$, letThe number $T$ of ordered three-term arithmetic progressions in $A$ isBy the Cauchy-Schwarz inequality,The last sum is the additive energy of $A$, namely the number of additive quadruples. If $T\ge \eta |A{|}^2$, then

The Fourier density-increment proof of the Meshulam theorem controls three-term progressions through ordinary Fourier coefficients, equivalently the $U^2$ norm. Four-term progressions are controlled by the Gowers uniformity norm $U^3$. A function can have small correlation with every linear character while correlating strongly with a quadratic phase; such a function can have small $U^2$ norm but large $U^3$ norm. Ordinary Fourier uniformity therefore does not make the four-term progression count pseudorandom, and a large linear Fourier coefficient need not exist when that count is deficient. Quadratic or higher-order Fourier structure is needed.

The Finite-field Szemerédi theorem for four-term arithmetic progressions says that for every $\delta >0$ there is $N=N(\delta )$ such that, for every prime $p\ge 5$, whenever $|{\mathbb{F}}_p^n|\ge N$ and $A\subseteq {\mathbb{F}}_p^n$ has density at least $\delta$, there exist $x,d\in {\mathbb{F}}_p^n$ with $d\ne 0$ and

Choose $ϵ=1/6$ and a sufficiently large absolute constant $k$. Part (iii)'s size bound givesLetand choose a maximal dissociated set $\Lambda \subseteq \Gamma$. The entropy form of the Chang theorem givesand maximality gives $\Gamma \subseteq \mathrm{Span}(\Lambda )$.

Put $B=B(\Lambda ,1/(6|\Lambda |))$. If $y\in B$ and $\gamma \in \Gamma$, expressing $\gamma$ as a product of characters in $\Lambda$ and their inverses givesFor $f=1_{-A}\ast {\mu }_A$, Parseval identity givesAlso $\hat{\mu }(\gamma )=|\widehat{{\mu }_Y}(\gamma ){|}^{2k}$. Fourier inversion theorem therefore yieldsonce $k$ is large enough.

If $\Lambda$ is empty, interpret $B$ as $G$; the same Fourier estimate, using only the second term, is even stronger.

Part (iii) gives $\Vert f\ast \mu -f{\Vert }_{\infty }\le 1/6$. Applying this at $x$ and $x+y$ and using the last estimate givesFinally $f(0)=1$. Hence $f(y)\ge 1/3>0$ for every $y\in B$, while the support of $f$ is $A-A$. Consequently

Put $f=1_{-A}\ast {\mu }_A$. The probability measureis supported on $kY-kY$. Convolution by $\mu$ averages translates by points in this support, so convexity of the supremum norm givesThus

Apply the Croot-Sisask almost-periodicity theorem with the sampling set $A$, $S=G$, $f=1_{-A}$, and error $ϵ/k$. Since $A+G=G$, the doubling parameter is $K={\alpha }^{-1}$, and $\Vert 1_{-A}{\Vert }_p\le 1$. We obtain $X\subseteq G$ withsuch thatfor every $t\in X-X$. Every $x\in kX-kX$ is a sum of $k$ elements of $X-X$. Telescoping these $k$ shifts and using translation invariance and the triangle inequality for the Lp norm gives

One normalized form of the Croot-Sisask almost-periodicity theorem is as follows. If finite sets $A,S$ in a group satisfy $|A+S|\le K|A|$, $p\ge 2$, and $0<ϵ<1$, then for every function $f$ there is $T\subseteq S$ withsuch that

Iterate part (iv) as a density increment. At a stage with ambient vector space of dimension $n_i$ and relative density ${\alpha }_i$, either the sumset contains a coset of a $k$-dimensional subspace, or there is a subspace of codimension $O({\alpha }_i^{-2}k)$ and a coset on which the density is at least $3{\alpha }_i/2$. Translate that coset back to the subspace. Since the ambient group has characteristic two, this translation does not alter the translated set's sumset.

The densities grow geometrically, so the iteration has $O(\log ({\alpha }^{-1}))$ stages, while the total codimension lost isChoose $k=\lfloor c{\alpha }^{2}n\rfloor$ with a sufficiently small absolute $c>0$. The total codimension is then less than $n-k$, so every stage still has ambient dimension at least $k$. The density cannot increase indefinitely beyond one; therefore the first alternative must occur. When $c{\alpha }^{2}n<1$, take the zero-dimensional subspace; this is the usual integer rounding implicit in the asymptotic dimension bound. Thusfor an absolute $C>0$.

If $\beta <2^{-k}$, part (iii) gives the first alternative. Otherwise $\log ({\beta }^{-1})\le k\log 2$, so part (ii) gives a subspace $V$ of codimension $O({\alpha }^{-2}k)$ withThe function $1_A\ast {\mu }_V$ is nonnegative and has mean $\alpha$. HenceIt follows that

Let $H\le {\mathbb{F}}_2^n$ have dimension $k$. The valueis a multiple of $|H{|}^{-1}=2^{-k}$, and its average over $x$ is the density $\beta$ of $B$. If every coset of $H$ met $B$, then every value would be at least $2^{-k}$, forcing $\beta \ge 2^{-k}$. Thus $\beta <2^{-k}$ implies that some coset $x+H$ is disjoint from $B$, and therefore

Let $B={\mathbb{F}}_2^n\setminus (A+A)$ have density $\beta$. Since $1_A\ast 1_A$ vanishes on $B$,The zero-frequency contribution is ${\alpha }^2\beta$, soPut $\Gamma ={\mathrm{Spec}}_{\alpha /2}(1_B)$. Outside $\Gamma$, Parseval identity bounds the contribution byThereforebecause $|\widehat{1_B}(t)|\le \beta$. Chang's theorem places $\Gamma$ in a subspace $W$ of dimensionSet $V=W^{\perp }$. Then $V$ has this codimension, $V^{\perp }=W$, and adding the zero-frequency term $|\widehat{1_A}(0){|}^2={\alpha }^2$ gives

Use normalized Fourier analysis on a finite abelian group. If $A\subseteq {\mathbb{F}}_2^n$ has density $\alpha$, its large spectrum at level $\rho >0$ isThe Chang theorem states that this spectrum is contained in a subspace of dimensionEquivalently, it is contained in the span of a dissociated set of that size.

Assume $|A+A|\le K|A|$ and putThis set is symmetric, contains zero, and the Plünnecke-Ruzsa inequality givesIt also contains $A-A$, so for every $x\in A$,

To control $H+H=4A-4A$, observe again by Plünnecke-Ruzsa thatApply the Ruzsa covering lemma with $S=H+H$ and $T=A$. There is a set $Y$ with $|Y|\le K^9$ such thatConsequently $H$ is a $K^9$-approximate group. Taking a sufficiently large absolute constant $C$ gives

Construct $X\subseteq B$ greedily. Begin with one element of $B$. While some $b\in B$ satisfiesadjoin $b$ to $X$. The first translate contributes $|A|$ points to $A+X$, and each later translate contributes at least $|A|/2$ new points. Thereforeand hence

When the process stops, every $b\in B$ satisfies $|(A+b)\cap (A+X)|>|A|/2$. Each point in this intersection has the formand therefore gives a triple $(x,a,a^{\prime })\in X\times A\times A$ with $b=a-a^{\prime }+x$. Distinct intersection points give distinct $a^{\prime }$, so there are more than $|A|/2$ such triples.

For $b,b^{\prime }\in B$, the corresponding sets of possible $a^{\prime }\in A$ both have size greater than $|A|/2$ and hence intersect. Using a common $a^{\prime }$ givesso $b-b^{\prime }=a-c+x-y$. Thus

The Plünnecke-Ruzsa inequality says that if $A,B$ are finite nonempty subsets of an abelian group andthen for all nonnegative integers $m,n$,

Choose a nonempty $X\subseteq A$ minimizingthen $K^{\prime }\le K$. We first prove the Petridis minimal-growth lemmafor every finite $C$, by induction on $|C|$. Remove $c\in C$, write $C^{\prime }=C\setminus \{c\}$, and letThe new points contributed to $X+C$ by $X+c$ are exactly $|X\setminus X^{\prime }|$. Moreover, $X^{\prime }+B+c\subseteq (X+B+c)\cap (X+B+C^{\prime })$, soThe induction hypothesis, the identity $|X+B|=K^{\prime }|X|$, and minimality, which gives $|X^{\prime }+B|\ge K^{\prime }|X^{\prime }|$, yieldIteration with $C=(r-1)B$ gives

Finally, the Ruzsa triangle inequality givesas required.