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.

The Lévy reflection theorem states that for every finite collection $\Phi$ of formulas and every ordinal $\gamma$, there is an ordinal $\alpha >\gamma$ such that, for every $\phi \in \Phi$ and all parameters $\vec{a}\in V_{\alpha }$,Indeed, the ordinals $\alpha$ reflecting all formulas in $\Phi$ form a closed unbounded class.

Conditions in $G$ are compatible finite functions, so their union $F=\bigcup G$ is a function $({\omega }_1{)}^M\rightharpoonup ({\omega }_1{)}^M$. For each $\alpha <{\omega }_1$, the setis dense: choose a normal function extending $p$ and add its value at $\alpha$. Genericity makes $F$ total.

If $\alpha <\beta$, choose a condition in the filter extending conditions that decide both values. It is contained in a normal function on an ordinal, so $F(\alpha )<F(\beta )$. Thus $F$ is strictly increasing.

It remains to prove continuity. For every limit $\delta <{\omega }_1$ and $\gamma <{\omega }_1$, let $D_{\delta ,\gamma }$ contain the conditions $p$ such that $\delta \in \mathrm{dom}p$ and eitheror there is some $\alpha <\delta$ in $\mathrm{dom}p$ with $p(\alpha )>\gamma$. This set is dense. Given $p$, extend it to a normal function $f$ and add $(\delta ,f(\delta ))$; if $f(\delta )>\gamma$, continuity of $f$ supplies an $\alpha <\delta$ with $f(\alpha )>\gamma$, which may also be added.

Now fix $\gamma <F(\delta )$. Since $G$ meets $D_{\delta ,\gamma }$, compatibility with the condition deciding $F(\delta )$ rules out the first alternative and gives $\alpha <\delta$ with $F(\alpha )>\gamma$. Therefore values below $\delta$ are cofinal in $F(\delta )$. Strict increase supplies the reverse bound, soHence $F$ is normal on $({\omega }_1{)}^M$ in $M[G]$.

Assume the forcing relation and the forcing theorem have been constructed for $\phi (x,\vec{y})$. Defineto mean thatis dense below $p$. This definition is first-order over $M$, so the definability lemma is preserved.

Suppose $p\in G$ forces the existential statement. Genericity below $p$ gives $q\in G\cap D_p$ and a name $\sigma$ with $q⊩\phi (\sigma ,\vec{\tau })$. The truth lemma for $\phi$ yieldsso the existential statement is true. Conversely, if $M[G]\models \exists x\phi (x,{\vec{\tau }}^G)$, choose a name $\sigma$ for a witness. The truth lemma for $\phi$ gives $q\in G$ with $q⊩\phi (\sigma ,\vec{\tau })$, and then $q⊩\exists x\phi (x,\vec{\tau })$. This proves both directions of the forcing theorem for the existential formula.

The forcing theorem has two parts. The definability lemma says that for every formula $\phi$, the relationis definable in $M$. The truth lemma says that if $G$ is generic over $M$, then

Let $c=\bigcup G$ and $d(n)=c(2n)$. DefineThis is a filter: restrictions of finite pieces of $d$ remain in $H$, and the union of two members is a common stronger condition.

To prove genericity, take a dense set $D\in M$. Let $E_D$ consist of conditions $q\in \mathrm{Fn}(\omega ,2)$ for which some $p\in D$ satisfiesThe set $E_D$ is dense. Indeed, given $q$, first read its finitely many assigned even coordinates as a condition $p_0$ on $\omega$. Choose $p\le p_0$ in $D$, and extend $q$ by setting $q(2n)=p(n)$ at the remaining coordinates of $p$. Since $E_D\in M$, the generic filter $G$ meets it. For $q\in G\cap E_D$, the corresponding $p\in D$ is a finite subfunction of $d$, so $p\in H\cap D$.

Thus $H$ meets every dense subset belonging to $M$. Moreover, each singleton $\{(n,d(n))\}$ belongs to $H$, and hence