A model-theoretic note on the Freiman–Ruzsa theorem

Abstract

A non-quantitative version of the Freiman–Ruzsa theorem is obtained for finite stable sets with small tripling in arbitrary groups, as well as for (finite) weakly normal subsets in abelian groups.

1 Introduction

A finite subset A of a group G is said to have doubling K if the product set $A\cdot A=\{a\cdot b\,|\, a, b \in A\}$ has size at most K|A|. Archetypal examples of sets with small doubling (where K is constant as the size of the group G, and the set A, tend to infinity) are cosets of subgroups. Theorems of Freiman–Ruzsa type assert that sets with small doubling are “not too far” from being subgroups in a suitable sense. Specifically, Freiman’s original theorem [6] asserts that a finite subset of the integers with small doubling is efficiently contained in a generalized arithmetic progression. A proof of an analogous statement for arbitrary abelian groups was given by Green and Ruzsa [7], based on Ruzsa’s proof of Freiman’s theorem [16]. A version of the result for abelian groups of bounded exponent with a particularly pleasing proof was given by Ruzsa in [17]. His result asserts that if A is a finite subset of an abelian group $(G,+)$ of exponent r such that $|A+A|\le K|A|$, then A is contained in a subgroup H of G of size at most $K^2 r^{K^4}|A|$. For $G={\mathbb {F}}_p^n$ with p a fixed prime, the exponent can be improved to $2K-1$ (see [5] and references therein). By considering the union of a subspace and K arbitrary linearly independent elements, it is not difficult to see that any bound on the size of a subgroup containing A must be exponential in K.

However, this example is still highly structured in the sense that a large part of the set has the structure of a subgroup, which suggests a natural reformulation of the problem. The Polynomial Freiman–Ruzsa Conjecture, which remains one of the central open problems in additive combinatorics, asserts that a subset A of doubling K in $\mathbb F_2^\infty$ can be covered by $C_1(K)$ many cosets of some subspace of size $C_2(K)|A|$, where both $C_1(K)$ and $C_2(K)$ are polynomials in K; or equivalently, that there are constants $C_3(K)$ and $C_4(K)$, each polynomial in K, such that for some coset $v+H$ of a subspace H of size $C_3(K)|A|$, we have that $A\cap (v+H)$ has size at least $|A|/C_4(K)$. For the best bounds known to date see [18, 20].

The above formulation of the Freiman–Ruzsa theorem resonates with a classical setting in model theory, namely weakly normal groups. Weakly normal groups, also known as 1-based stable groups, are groups for which every definable set is a boolean combination of instances of weakly normal formulae (see Sect. 2). In a weakly normal (stable) group, every definable subset is a boolean combination of cosets of definable subgroups [9]. Furthermore, every type over a model is the generic type of a coset of a (type-)definable subgroup: the subgroup is its model-theoretic stabiliser. Roughly speaking, a large proportion of a given definable set intersects a coset of a definable group, so they are commensurable.

For non-abelian groups, the suitable notion of doubling is tripling K, that is, the cardinality of $A\cdot A \cdot A$ is bounded by K|A|. Indeed, sets of small tripling have small doubling, but the converse need not hold. In this context, phenomena of Freiman–Ruzsa type are present in recent work of Hrushovski [11, Corollary 4.18], who showed that a set of small tripling in a (possibly infinite) group of bounded exponent is commensurable with a subgroup, inspired by classical results and techniques from stability theory in a non-standard setting.

Motivated by Hrushovski’s work, in this note we adapt the local approach to stability of Hrushovski and Pillay in [10, Theorem 4.1] in order to obtain a non-quantitative version of the Freiman–Ruzsa theorem for arbitrary (possibly infinite) groups under the assumption of stability. We say that a subset A of G is r-stable if there are no elements $a_1,\ldots , a_r, b_1, \ldots , b_r$ in G such that $b_j\cdot a_i$ belongs to A if and only if $i\le j$. In particular, we prove the following result.

Theorem A

Given real numbers $K\ge 1$ and $\epsilon >0$ and a natural number $r\ge 2$, there exists a natural number $n=n(K, \epsilon , r)$ such that for any (possibly infinite) group G and any finite r-stable subset $A\subseteq G$ with tripling K, there is a subgroup $H\subseteq A\cdot A ^{-1}$ of G with $A\subseteq C\cdot H$ for some $C\subseteq A$ of size at most n. Moreover, there exists $C'\subseteq C$ such that

$$\begin{aligned} |A \triangle (C'\cdot H)|\le \epsilon |H|.\end{aligned}$$

In particular, it follows from the Plünnecke-Ruzsa inequalities that

$$\begin{aligned} |A \triangle (C'\cdot H)|\le \epsilon K^2 |A|.\end{aligned}$$

In the case when G is abelian, it suffices to assume that A has doubling K. Furthermore, we shall prove that, when G is abelian, the subgroup H can be taken to be a boolean combination (of complexity only depending on K, $\epsilon$ and r) of translates of A.

In particular, on choosing $\epsilon =1$, Theorem A implies that there is some natural number $n_0=n(K, 1, r)$ such that any finite r-stable subset A of tripling K is contained in $n_0$ translates of a subgroup $H\subseteq A\cdot A ^{-1}$. It follows that $|A\cap g\cdot H|\ge |A|/n_0$ for some subgroup $H\leqslant G$ and some $g\in A$, which is a qualitative result in the spirit of Freiman–Ruzsa. As in the previous paragraph, when G is abelian, the complexity of such a subgroup H as a boolean combination of translates of A can be bounded solely in terms of K and r.

The above result dovetails with a suite of arithmetic regularity lemmas under the additional assumption of stability that have been obtained recently by Terry and the third author [25, 26], as well as by Conant, Pillay and Terry [2]. However, without the assumption of small doubling/tripling, the bound on the symmetric difference is at best $\epsilon |H|$. Furthermore, the group H so obtained in [2, 25, 26] has finite index in G so its size comparable to |G|, but not necessarily to |A|. The Theorem A is also reminiscent of work of Sisask [21, Theorem 5.4], who combined the assumption of small doubling with that of bounded VC-dimension in vector spaces over finite fields. Finally, we remark that closely related results were obtained by Conant [3, Corollary 1.4] for groups of bounded exponent. In a previous version of this article, Theorem A was stated with the upper bound

$$\begin{aligned} |A \triangle (C'\cdot H)|\le \epsilon |A|,\end{aligned}$$

which was subsequently improved by Conant [4, Theorem 1.6] to the current upper bound. Conant’s methods do not use the full power of stability but instead work in the more general setting of finite VC-dimension. We later noticed that our (non-standard) techniques already implied the finer bound in terms of H.

We also explore the interaction between model theory and recent work in additive combinatorics in a second direction. In [8] Green and Sanders showed that subsets of a locally compact abelian group G which are elements of the Fourier algebra ${\mathcal {A}}(G)$ belong to the coset ring ${\mathcal {W}}(G)$. They also gave an upper bound for the boolean complexity of the representation as elements in ${\mathcal {W}}(G)$ of such sets in terms of their Wiener norm. More recently, Sanders [19] showed that smallness of this norm implies stability, hence ${\mathcal {A}}(G)={\mathcal {W}}(G)\subseteq {\mathcal {S}}(G)$, where ${\mathcal {S}}(G)$ denotes the ring of stable subsets of G. He further observed that when G is not finite, it is possible for the latter inclusion to be strict.

In this paper we shall consider the ring $\mathcal {WN}(G)$ of subsets of G generated by all instances of weakly normal formulae, defined in Sect. 2. It is not difficult to see that $\mathcal {WN}(G)$ is contained in yet not identical to the stability ring ${\mathcal {S}}(G)$. Actually, we have the chain of inclusions

$$\begin{aligned} {\mathcal {W}}(G) \subseteq \mathcal {WN}(G) \subseteq {\mathcal {S}}(G).\end{aligned}$$

In fact, we shall show that $\mathcal {WN}(G)$ is equal to ${\mathcal {W}}(G)$ for abelian G (see Proposition 4.3). This is a local reformulation of the celebrated result by Hrushovski and Pillay [9, Theorem 4.1]. We further deduce a result of Freiman–Ruzsa type for finite subsets in $\mathcal {WN}(G)$.

Mimicking the definition of Sanders in [19], we say that a subset A of G has an (r, k, l)-weakly normal representation if

$$\begin{aligned}A = \bigcup \limits _{j=1}^k B_j \cap \bigcup \limits _{i=1}^l G\setminus C_r, \end{aligned}$$

where all the relations $B_1(x+ y),\ldots ,B_k(x+ y),C_1(x+ y),\ldots ,C_l(x+ y)$ are r-weakly normal.

Theorem B

Given natural numbers r, k, and l, there are natural numbers $n=n(r,k,l)$ and $m=m(r,k,l)$ such that for any abelian group G and any subset $A\subseteq G$ with an (r, k, l)-weakly normal representation, there are subgroups $H_1,\ldots , H_n$ of G, each contained in $A-A$, with

$$\begin{aligned}A\subseteq \bigcup \limits _{i=1}^{n} g_i+H_i,\end{aligned}$$

for some $g_1,\ldots , g_n$ in A. Furthermore, each $H_i$ is a boolean combinations of complexity at most m of translates of A.

In particular, if A is finite, we have that $|A\cap (g+H)|\ge |A|/n$ for some g in A and some subgroup $H\leqslant G$ contained in $A-A$.

In contrast to Theorem A, the subset A above need not have small doubling or tripling. Indeed, there is no correlation for finite sets between having a weakly normal representation and small doubling: consider the group $G={\mathbb {F}}_p^2$ and let A be the subset $({\mathbb {F}}_p\times \{0\} \cup \{0\}\times {\mathbb {F}}_p)$, which has a (2, 2, 0)-weakly normal representation. However, the quantity

$$\begin{aligned} \frac{|A+A|}{|A|} = \frac{p^2}{2p-1}\end{aligned}$$

is not uniformly bounded for large p.

Throughout this paper, we will assume a certain familiarity with model theory. We refer the reader to [24] for an excellent introduction to the subject. Basic notions related to local stability and weak normality are recalled and developed in Sects. 1 and 2 , respectively. Section 3 is devoted to a discussion of Keisler measures on a certain boolean algebra arising from sets of small tripling, and the associated measure-theoretic stabilizers. The proofs of our main results are given in Sect. 4.

2 Local stability

We work inside a sufficiently saturated model $\mathbb {U}$ of a complete theory T with infinite models in a language $\mathcal {L}$.

Recall that a formula $\varphi (x,y)$ is r-stable with respect to the partition of the variables into the tuples x and y if there are no tuples $a_1,\ldots , a_r, b_1, \ldots , b_r$ such that $\varphi (a_i,b_j)$ holds if and only if $i\le j$.

A formula is stable if it is r-stable for some r. Stable formulae are closed under boolean combinations (see [25] for a finitary version of this fact). A set X is $\varphi$-definable over a subset A of parameters if it is definable by a boolean combination of instances $\varphi (x,a)$ with a in A. By a $\varphi$-type over a subset A we mean a maximal finitely consistent collection of instances of the form $\varphi (x,a)$ or $\lnot \varphi (x,a')$ for $a, a'$ in A.

The space of $\varphi$-types $S_\varphi (\mathbb {U})$ is a compact Hausdorff 0-dimensional topological space, with basic clopen sets of the form

$$\begin{aligned}{}[X] =\{ p\in S_\varphi (\mathbb {U})\,|\, p \cup \{X(x)\} \text { is finitely consistent} \},\end{aligned}$$

where X(x) is $\varphi$-definable. Given a stable formula $\varphi (x,y)$ and a partial $\mathcal {L}$-type $\pi (x)$, the collection

$$\begin{aligned}X_\pi =\{q(x)\in S_\varphi (\mathbb {U})\,|\, q(x) \cup \pi (x) \text { is finitely consistent} \}\end{aligned}$$

is a closed, hence compact, subset of $S_\varphi (\mathbb {U})$ with integer-valued Cantor-Bendixson rank ${\text {CB}}_\varphi (\pi )$. Thus, any element q(x) in $X_{\pi }$ can be isolated from all other types of rank at least ${\text {CB}}_\varphi (q)$ by the neighbourhood $[\chi ]$ of some formula $\chi (x)$. Furthermore, the space $X_\pi$ contains only finitely many elements of maximal rank. The number of such elements is the $\varphi$-multiplicity of $\pi$, see [1, Chapter 6].

If $\varphi (x,y)$ is stable, then every $\varphi$-type p(x) over a small submodel M is definable, that is, there is a formula $\theta (y)$ with parameters over M such that

$$\begin{aligned} \varphi (x,m) \in p \ \Longleftrightarrow \ \theta (m),\end{aligned}$$

for all m in M. Furthermore, the definable set $\theta (y)$ above is unique and can be defined by a positive boolean combination of instances $\varphi (a,y)$ with parameters in M (cf. [10, Lemma 5.4]). We refer to this definable set as the $\varphi$-definition $(d_p\varphi )(y)$ of p. Given a superset $B\supseteq M$ of $\mathbb {U}$, there is a unique $\varphi$-type over B extending p which is again definable over M, namely

$$\begin{aligned} \{\varphi (x,b) \,|\, (d_p\varphi )(b)\}\cup \{\lnot \varphi (x,b') \,|\, \lnot (d_p\varphi )(b')\}.\end{aligned}$$

We refer to this type as the non-forking extension $p_{\mid {B}}(x)$ of p(x) to B. The global non-forking extension of p is the $\varphi$-type $p_{\mid {\mathbb {U}}}$. In fact, the unique global non-forking extension of p(x) is the only element in $X_p$ of rank ${\text {CB}}_\varphi (p)$, so p has $\varphi$-multiplicity 1 (cf. [1, Proposition 6.13 & Corollary 6.15]).

Henceforth, we will assume that the underlying structure $\mathbb {U}$ carries a definable group structure $(G,\cdot )$ without parameters. In order to analyse the structure of an arbitrary stable subset A of G, it suffices expand the language by a distinguished unary predicate, whose realisations are exactly the elements in A. Thus, we may assume that the formula $\varphi (x,y)= A(y\cdot x)$ is stable, for some fixed definable subset A of G.

Note that $\varphi (x,y)$ is equivariant (see [10, Definition 5.13]), that is, every left-translate of an instance of $\varphi$ is again an instance of $\varphi$. Given a stable equivariant formula $\varphi (x,y)$, there is a distinguished subgroup of G which is $\varphi$-definable, relative to G, as first observed in [10]. The following fact can be found in [2, Theorem 2.3].

Fact 1.1

Given a stable equivariant formula $\varphi (x,y)$ and a definable group G over a model M, there is a subgroup $G_\varphi ^0$ of finite index in G which is $\varphi$-definable over M (relative to G) such that for any coset C of $G_\varphi ^0$ and any $\varphi$-definable subset X, either $X\cap C$ or $C\setminus X$ is generic, in the sense that finitely many translates cover G.

The Cantor-Bendixson rank of a union is the maximum of the ranks of the sets in the union, so every generic $\varphi$-definable subset of G has maximal Cantor-Bendixson rank ${\text {CB}}_\varphi (G(x))$. On the other hand, if X is a $\varphi$-definable subset of G of maximal Cantor-Bendixson rank ${\text {CB}}_\varphi (G(x))$, it must be generic: indeed, since $G_\varphi ^0$ has finite index in G, there must be a coset C of $G_\varphi ^0$ such that $X\cap C$ has rank ${\text {CB}}_\varphi (G(x))$. We need only show that $C\cap X$ is generic. Otherwise, the set $C\setminus X$ is generic, so finitely many translates will cover G. Each such translate has maximal rank, yet every coset of $G^0_\varphi$ contains a unique $\varphi$-type of maximal rank.

Given a $\varphi$-type p(x) over a submodel M, we define its stabilizer to be the subgroup

$$\begin{aligned}{\text {Stab}}_\varphi (p)= \big \{g\in G\,|\, \forall u \big ( (d_p\varphi )(u) \leftrightarrow (d_p\varphi )(u\cdot g) \big ) \big \}. \end{aligned}$$

The stabilizer is clearly a definable subgroup of G with parameters from M. The following elementary remark shows that the stabilizer is $\varphi$-definable whenever G is abelian.

Remark 1.2

If $(G,+)$ is abelian, then the subgroup ${\text {Stab}}_\varphi (p)$ is $\varphi$-definable over M.

Proof

Let q(x) be the unique global non-forking extension of p(x). Choose a $\varphi$-formula

$$\begin{aligned} \chi (x)= \bigvee \limits _{j\in J} \bigwedge \limits _{i\in I} \varphi (x,b_{ij}) \wedge \lnot \varphi (x,c_{ij}) \end{aligned}$$

such that q lies in the neighborhood $[\chi ]$, with $\chi (x)$ of Cantor-Bendixson rank ${\text {CB}}_\varphi (p)$ and $\varphi$-multiplicity 1.

Now, an element g in G belongs to ${\text {Stab}}_\varphi (p)$ if and only if the $\varphi$-type $g+q$ equals q, that is, if and only if $\chi (x)-g$ belongs to q, or equivalently, if and only if

$$\begin{aligned} \bigvee \limits _{j\in J} \bigwedge \limits _{i\in I} (d_p\varphi )( b_{ij} +g) \wedge \lnot (d_p\varphi )( c_{ij}+g). \end{aligned}$$

Recall that $(d_p\varphi )(y)$ is a positive boolean combination of instances $\varphi (a, y)$. Since G is abelian, the formula $\varphi (x,y+z)$ is equivalent to $\varphi (x+ y, z)$, so the above condition on g is equivalent to a boolean combination $\psi (z,a')$ of instances of $\varphi (a', z)$, for some choice of parameters $a'$ in G. In particular, the formula

$$\begin{aligned} \exists u \forall z\big ({\text {Stab}}_\varphi (p)(z) \leftrightarrow \psi (z,u)\big ) \end{aligned}$$

holds in $\mathbb {U}$. Since M is an elementary substructure of $\mathbb {U}$, there are some parameters m in M such that ${\text {Stab}}_\varphi (p)(M)$ equals $\psi (M, m)$, and thus the $\varphi$-formula $\psi (z, m)$ defines the subgroup ${\text {Stab}}_\varphi (p)$ in G. $\square$

Note that if G is abelian, then $\varphi (x,y)=\varphi (y,x)$. Given global $\varphi$-types p(x) and q(y) in $S_\varphi (\mathbb {U})$, Harrington’s lemma [1, Lemma 6.8] yields that

$$\begin{aligned} q(y) \in [(d_p\varphi )(y)] \Leftrightarrow p(x) \in [(d_q\varphi )(x)].\end{aligned}$$

A standard argument yields the following result, whose short proof we include for completeness.

Remark 1.3

If $(G,+)$ is abelian, then given a $\varphi$-type p over M

$$\begin{aligned} {\text {CB}}_\varphi ({\text {Stab}}_\varphi (p)) \le {\text {CB}}_\varphi (p). \end{aligned}$$

Proof

Let q be a global type in $[{\text {Stab}}_\varphi (p)]$ of maximal rank, and choose a realization b of $q\!\!\upharpoonright _{M}$. Note that q is a non-forking extension of $q\!\!\upharpoonright _{M}$, since ${\text {Stab}}_\varphi (p)$ is definable over the model M. Let a realize the non-forking extension $p_{\mid {M\cup \{b\}}}$, which is definable over M by the formula $(d_p\varphi )(y)$. Thus, the element $a+b$ realizes p, since $-b$ belongs to ${\text {Stab}}_\varphi (p)$.

Let us first show that b realizes the non-forking extension $q\!\!\upharpoonright _{M\cup \{a\}}$ of $q\!\!\upharpoonright _{M}$. It suffices to see that $\varphi (a,b)$ holds if and only if $(d_q\varphi )(a)$. Now,

$$\begin{aligned} (d_q\varphi )(a)&\Longleftrightarrow p_{\mid {\mathbb {U}}}(x) \in [(d_q\varphi )(x)] {\mathop {\Longleftrightarrow }\limits ^{\text {Harrington}}} q(y) \in [(d_p\varphi )(y)] \\&\Longleftrightarrow (d_p\varphi )(b) \Longleftrightarrow \varphi (x,b) \in p_{\mid {M\cup \{b\}}} \Longleftrightarrow \varphi (a,b) \text { holds.} \end{aligned}$$

As the formula $\varphi$ is equivariant, addition by an element preserves the rank of formulae, so

$$\begin{aligned} {\text {CB}}_\varphi ({\text {Stab}}_\varphi (p))&= {\text {CB}}_\varphi (q\!\!\upharpoonright _{M}) = {\text {CB}}_\varphi (q\!\!\upharpoonright _{M\cup \{a\}}) = {\text {CB}}_\varphi (b/M\cup \{a\}) \\&= {\text {CB}}_\varphi (a+b/M\cup \{a\})\le {\text {CB}}_\varphi (a+b/M)={\text {CB}}_\varphi (p), \end{aligned}$$

as desired. $\square$

3 Weak normality

Given a natural number k, a formula $\psi (x,y)$ is k-weakly normal if, whenever the instances $\psi (x,b_1), \ldots , \psi (x,b_k)$ are pairwise distinct, the intersection $\bigcap _{i=1}^k \psi (x,b_i)$ is empty [9]. A formula is weakly normal if it is k-weakly normal for some natural number k. The conjunction of weakly normal formulae is again weakly normal. However, neither the negation nor the disjunction of two weakly normal formulae need necessarily be weakly normal.

It is easy to see that a k-weakly normal formula is k-stable. If not, there is a sequence $(a_i, b_i)_{1\le i\le k}$ witnessing the failure of stability. Since $a_j$ belongs to $\psi (x,b_j)$ but not to $\psi (x,b_i)$ for $i<j$, the instances are pairwise distinct. However, the element $a_1$ belongs to their common intersection, so $\psi (x,y)$ is not k-weakly normal. Furthermore, a formula $\psi (x,y)$ is 2-stable precisely if it is 2-weakly normal. Indeed, if $\psi (x,y)$ is not 2-weakly normal, we can find two distinct instances $\psi (x,b_1)$ and $\psi (x,b_2)$ with non-empty intersection. We may assume that there is some $a_2$ in $\psi (x,b_2)\setminus \psi (x,b_1)$. As the intersection $\psi (x,b_1)\cap \psi (x,b_2)$ is non-empty, choose $a_1$ in $\psi (x,b_1)\cap \psi (x,b_2)$ and note that

$$\begin{aligned} \psi (a_i,b_j) \Leftrightarrow 1\le i\le j\le 2,\end{aligned}$$

so $\psi (x,y)$ is not 2-stable.

Formulae which are 2-stable are very special. For example, in the setting of a group G with a fixed definable subset A, the formula $\varphi (x,y)=A(y\cdot x)$ is 2-stable if and only if A is either empty or a coset of a subgroup of G. Recall that a subset A of an abelian group G is Sidon if, whenever the 4-tuple $(a_1,a_2,a_3,a_4)$ of elements of A satisfies $a_1-a_2=a_3-a_4$, then $a_1=a_2$ (and hence $a_3=a_4$) or $a_1=a_3$ (and thus $a_2=a_4$). Sidon subsets of the integers, such as $2^{{\mathbb {N}}}$ or $3^{{\mathbb {N}}}$, are 3-stable, but need not lie in the coset ring ${\mathcal {W}}({\mathbb {Z}})$ [19].

Remark 2.1

In general, stability need not imply weak normality. For a Sidon set A of cardinality at least k, the formula $A(x+y)$ cannot be k-weakly normal. Choose k distinct elements $a_1,\ldots , a_k$ in A and consider the collection of sets $(-a_j+A)_{1\le j\le k}$. The element 0 belongs to their common intersection, yet they are pairwise distinct sets.

Since a definable set is defined over a submodel N if and only if it only has finitely many distinct automorphic copies over N (see for example [1, Proposition 1.11]), we deduce the following easy observation concerning sets defined by an instance of a weakly normal formula.

Remark 2.2

Let X be a definable set given by an instance of a weakly normal formula. Then the set X is definable over any submodel containing a realization of X.

A remarkable property of every weakly normal formula $\psi$ is that the definition $(d_p\psi )$ of every local type p over an arbitrary set of parameters is explicit, in contrast to a general stable formula (cf. [24, Theorem 8.3.1]): indeed, given a k-weakly normal formula $\psi (x,y)$, an instance $\psi (x,a)$ belongs to the $\psi$-type $p={\text {tp}}_\psi (c/A)$ if and only if it contains the set

$$\begin{aligned} {\mathcal {X}}_{p,\psi }= \bigcap \limits _{\psi (x,a') \in p} \psi (x,a').\end{aligned}$$

This set is definable since it is the intersection of at most $k-1$ instances in p (notice that ${\mathcal {X}}_{p,\psi }$ is the empty set if and only if the collection of positive instances $\psi (x,a')$ in p is empty). It suffices to set

$$\begin{aligned}(d_p\psi )(y) =\forall x \big ( {\mathcal {X}}_{p,\psi }(x) \rightarrow \psi (x,y) \big ) \hbox { when}\ {\mathcal {X}}_{p,\psi }\ne \emptyset , \end{aligned}$$

and

$$\begin{aligned}(d_p\psi )(y) = (y\ne y) \text { otherwise.}\end{aligned}$$

Remark 2.3

Assume that the formula $\chi (x,y)$ is a boolean combination of weakly normal formulae. Then every $\chi$-type p is definable over any submodel containing a realization of p.

Note that we do not require that the submodel contains the parameter set of p, which is assumed to be small with respect to the saturation of $\mathbb {U}$.

Proof

If the formula $\chi (x,y)$ is a boolean combination of the weakly normal formulae $\psi _1(x,y),\ldots , \psi _r(x,y)$, then the $\chi$-type $p={\text {tp}}_\chi (c/A)$ is determined by the collection of types $q_1={\text {tp}}_{\psi _1}(c/A), \ldots , q_r={\text {tp}}_{\psi _r}(c/A)$. Hence, the $\chi$-definition $(d_p\chi )$ is determined by the definable sets $\{(d_{q_i}\psi _i)\}_{1\le i\le r}$. Each $(d_{q_i}\psi _i)$ is determined by the corresponding definable set ${\mathcal {X}}_{q_i,\psi _i}$, as in the previous discussion, which is definable over any submodel containing c, by Remark 2.2. $\square$

A well-known result of Hrushovski and Pillay [9, Lemma 4.2] shows that, in a theory where all formulae are boolean combinations of weakly normal ones, types are generic in cosets of their stabilizers. In particular, groups definable in such theories are virtually abelian, that is, abelian-by-finite. We will provide a local version of their results for abelian groups, following closely [15, Lemma 2.6 & Remark 2.7].

Lemma 2.4

Let $(G,+)$ be abelian and assume that the formula $\varphi (x,y)=A(x+y)$ is a boolean combination of weakly normal formulae. Given a $\varphi$-type p over a model M, there exists some element m in M such that $p_{\mid {\mathbb {U}}}$ lies in the neighborhood $[m+{\text {Stab}}_\varphi (p)]$, that is, the type p implies the $\varphi$-formula over M defining the coset $m+{\text {Stab}}_\varphi (p)$.

Furthermore, the proof of the above result yields that ${\text {CB}}_\varphi ({\text {Stab}}_\varphi (p)) = {\text {CB}}_\varphi (p)$, but this fact will not be used in the sequel.

Proof

Let a be a realization of p(x). Since G is abelian, every coset of $H={\text {Stab}}_\varphi (p)$ is $\varphi$-definable (since $\varphi (x,y)$ is equivariant). We want to show that the coset $H+a$ is $\varphi$-definable over M. It suffices to show that it is definable over M, for M is an elementary substructure. Since the element a lies in $H+a$, if this coset is definable over M, then the type p must imply the corresponding $\varphi$-formula over M defining it. Remark 1.3 yields then the equality of ranks.

To prove that $H+a$ is definable over M, we need only show that $H+a$ is definable over a submodel $N\succeq M$ such that ${\text {tp}}(a/N)$ is an heir of ${\text {tp}}(a/M)$: indeed, suppose that $H+a$ is definable over such N, so there are an $\mathcal {L}_M$-formula $\theta (x,z)$ and some tuple n in N such that the formula $\theta (x,n)$ defines $H+a$. Note that this coset is definable over $M\cup \{a\}$. In particular, the formula

$$\begin{aligned} \forall x \big ((H+u)(x)\leftrightarrow \theta (x,n) \big )\end{aligned}$$

belongs to ${\text {tp}}(a/N)$. Thus, we find a tuple m in M such that $\theta (x, m)$ defines $H+a$, by inheritance of ${\text {tp}}(a/N)$ over M.

Now choose a $\varphi$-type q(x) over M of maximal Cantor-Bendixson rank ${\text {CB}}_\varphi (G)$. The extension $q_{\mid {M\cup \{a\}}}$ is definable over M, so it is finitely satisfiable over M [14, Lemma I.2.16]. Thus we can find some element c such that the type ${\text {tp}}(c/M\cup \{a\})$ is finitely satisfiable over M and extends $q_{\mid {M\cup \{a\}}}$. By a dual argument, we can find a submodel $N\succeq M$ containing c such that ${\text {tp}}(a/N)$ is an heir of ${\text {tp}}(a/M)$.

Claim

The element a realizes $p_{\mid {M\cup \{c-a\}}}$.

Proof of Claim

We need only show that $\varphi (a,c-a)$ holds if and only if $(d_p\varphi )(c-a)$ holds. Observe first that

$$\begin{aligned} {\text {CB}}_\varphi (G)&= {\text {CB}}_\varphi (q) = {\text {CB}}_\varphi ( q_{\mid {M\cup \{a\}}}) = {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(c/M\cup \{a\})) \\&= {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(c-a/M\cup \{a\}))\le {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(c-a/M))\le {\text {CB}}_\varphi (G). \end{aligned}$$

Hence, equality holds everywhere, so $r(y)={\text {tp}}_{\varphi }(c-a/M\cup \{a\})$ is definable over M and has maximal rank ${\text {CB}}_\varphi (G)$.

Now, the formula $\varphi (a,c-a)$ holds if and only if $\varphi (a,y)$ belongs to r(y), that is, if and only if the element a realizes $(d_r\varphi )(x)$, which is definable over M. Hence, the formula $\varphi (a,c-a)$ holds if and only if $p_{\mid {\mathbb {U}}}$ lies in $[(d_r\varphi )]$, which is equivalent to $r_{\mid {\mathbb {U}}}$ being contained in $[(d_p\varphi )]$, by Harrington’s lemma. Since $[(d_p\varphi )]$ is definable over M and the element $c-a$ realizes r, the latter is equivalent to $(d_p\varphi )(c-a)$, as desired. $\square \, {\tiny {{\mathrm{Claim}}}}$

Since $c=a+(c-a)$, the element c realizes the complete $\varphi$-type

$$\begin{aligned}&p_{\mid {M\cup \{c-a\}}} +(c-a)=\{ \theta (x) \ \varphi \text {-formula over }M\cup \{c-a\} \ | \ \theta \left( x-(c-a)\right) \\&\quad \in p_{\mid {M\cup \{c-a\}}} \},\end{aligned}$$

which is again a complete $\varphi$-type over $M\cup \{c-a\}$. In particular, the global $\varphi$-type $p_{\mid {\mathbb {U}}}+(c-a)$ is a non-forking extension of $p_{\mid {M\cup \{c-a\}}} +(c-a)$. By Remark 2.3, both types are definable over N (which contains c).

Let us now show that the coset $H+a$ is definable over N. It suffices to show that every automorphism $\sigma$ fixing N pointwise fixes the coset (setwise). Since $p_{\mid {\mathbb {U}}}+(c-a)$ is definable over N, the automorphism $\sigma$ fixes $p_{\mid {\mathbb {U}}}+(c-a)$, so

$$\begin{aligned} p_{\mid {\mathbb {U}}}+(c-a) = \sigma (p_{\mid {\mathbb {U}}}+(c-a)) = p_{\mid {\mathbb {U}}}+(c-\sigma (a)), \end{aligned}$$

since $p_{\mid {\mathbb {U}}}$ is definable over M. Thus, we have $p_{\mid {\mathbb {U}}}-a = p _{\mid {\mathbb {U}}}-\sigma (a)$, that is,

$$\begin{aligned} p_{\mid {\mathbb {U}}}= p _{\mid {\mathbb {U}}}+ (a-\sigma (a)), \end{aligned}$$

and hence $a-\sigma (a)$ lies in $H={\text {Stab}}_\varphi (p)$, as desired. $\square$

In analogy to the classical result for weakly normal theories, we conclude that $\varphi$-definable sets are boolean combination of cosets of $\varphi$-definable groups whenever $\varphi (x,y)=A(x+y)$ is a boolean combination of weakly normal formulae.

Corollary 2.5

In an abelian group G (written additively), assume that the formula $\varphi (x,y)=A(x+y)$ is a boolean combination of weakly normal formulae. Every $\varphi$-definable set is a boolean combination of cosets of $\varphi$-definable subgroups.

Note in particular that a coset of a $\varphi$-definable subgroup is a boolean combination of translates of A.

Proof

By a straightforward application of [24, Lemma 3.1.1], it suffices to show that whenever two $\varphi$-types $p_1$ and $p_2$ over a submodel M imply the same M-definable cosets of $\varphi$-definable subgroups (over M), then $p_1$ and $p_2$ are the same.

Let $a_1$ realize $p_1$ and choose a realization $a_2$ of ${p_2} _{\mid {M\cup \{a_1\}}}$. Set $H_1={\text {Stab}}_\varphi (p_1)$ and $H_2={\text {Stab}}_\varphi (p_2)$. By Lemma 2.4, both cosets $a_1+H_1$ and $a_2+H_2$ are M-definable. By assumption, since $p_1$ clearly implies the formula defining $a_1+H_1$, every realization of $p_2$ lies in $a_1+H_1$, and similarly for $p_1$. In particular, the element $a_1-a_2$ lies in $H_1\cap H_2$. The rank computation

$$\begin{aligned} {\text {CB}}_\varphi (H_2)&\le {\text {CB}}_\varphi (p_2)={\text {CB}}_\varphi ({p_2} _{\mid {M\cup \{a_1\}}}) = {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(a_2/M\cup \{a_1\}))\\&= {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(a_2-a_1/M\cup \{a_1\}))\le {\text {CB}}_\varphi ({\text {tp}}_{\varphi }(a_2-a_1/M))\le {\text {CB}}_\varphi (H_2) \end{aligned}$$

yields that $a_2-a_1$ realizes the non-forking extension of $q={\text {tp}}_{\varphi }(a_2-a_1/M)$ over $M\cup \{a_1\}$. As in the proof of Remark 1.3, Harrington’s Lemma implies that $a_1$ realizes ${p_1} _{\mid {M\cup \{a_2-a_1\}}}$. Since $a_2-a_1$ lies in $H_1={\text {Stab}}_\varphi (p_1)$, we have that $a_2=a_1+(a_2-a_1)$ realizes $p_1$. Thus the types $p_1$ and $p_2$ are equal, as desired. $\square$

4 Ideals and measures

A Keisler measure $\mu$ is a finitely additive probability measure on some boolean algebra of definable subsets of the ambient model [12]. Archetypal examples are measures $\mu _p$, with two possible values 0 and 1, given by global $\varphi$-types p, that is, for every $\varphi$-definable set X,

$$\begin{aligned} \mu _p(X)=1 \Leftrightarrow p \in [X].\end{aligned}$$

Given a Keisler measure $\mu$, the collection of sets of measure zero forms an ideal, that is, it is closed under subsets and finite unions. A partial type is said to be wide (with respect to $\mu$) if it contains no definable set of measure zero. In particular, since the collection of measure-0 sets forms an ideal, every wide partial type $\pi (x)$ over a parameter set A can be completed to a wide complete type over any arbitrary subset B containing A: indeed, the collection of formulae

$$\begin{aligned} \pi (x)\cup \{\lnot \varphi (x) \,|\, \varphi (x)\in {\mathcal {L}}_B \text { with } \mu (\varphi (x))=0 \}\end{aligned}$$

is clearly finitely consistent, and any completion of this partial type is wide. Note that we do not require that every formula in the completion has measure.

The measure $\mu$ is said to be definable over the submodel M (see [22, Definition 3.19]) if for every $\mathcal {L}$-formula $\varphi (x,y)$ and every $\epsilon >0$, there is a partition of $\mathbb {U}^{|y|}$ into $\mathcal {L}_M$-formulae $\rho _1(y),\ldots , \rho _m(y)$ such that for all pairs $(b, b')$ realizing $\rho _i(y)\wedge \rho _i(z)$, we have that

$$\begin{aligned} |\mu (\varphi (x,b)) -\mu (\varphi (x,b') )|<\epsilon . \end{aligned}$$

In particular, the set of tuples b with $\mu (\varphi (x,b))=0$ is type-definable over M and the map

$$\begin{aligned}\begin{array}{ccc} S_y(M) &{} \rightarrow &{} [0,1]\\ {\text {tp}}(b/M) &{} \mapsto &{} \mu (\varphi (x,b)) \end{array} \end{aligned}$$

is continuous, so the value $\mu (\varphi (x,b))$ only depends on ${\text {tp}}(b/M)$. Note that a global $\varphi$-type p is definable over M if and only if the corresponding measure $\mu _p$ is.

Every Keisler measure admits an expansion of the original language $\mathcal {L}$ in which it becomes definable (cf. [11, Section 2.6]). In this case, a formula of positive measure does not fork over $\emptyset$, see [11, Lemma 2.9 & Example 2.12].

In the presence of an ambient group G, we will consider the following notion of an acceptable set, which was introduced as a near-subgroup in [11, Definition 3.9].

Definition 3.1

A definable subset A of G is acceptable if there exists a Keisler measure $\mu$ on a boolean algebra of definable subsets of $(A\cup A^{ ^{-1}}\cup \{\mathrm {id}_G\})^3$ such that $\mu (A)>0$, the set $A\cup A^{ ^{-1}}\cup \{\mathrm {id}_G\}$ has measure 1 and $\mu (Y)=\mu (X)$ for all definable measurable subsets X and Y of $(A\cup A^{ ^{-1}} \cup \{\mathrm {id}_G\})^3$ whenever Y is a translate of X.

Example 3.2

Let G be an abelian group, or more generally, an amenable group, equipped with a finitely additive probability measure $\mu$. Every subset of positive measure becomes an acceptable subset of G witnessed by the restriction of $\mu$ with respect to a suitable boolean algebra of $(A\cup A ^{-1}\cup \{\mathrm {id}_G\})^3$. As above, we can expand the language of groups to a suitable language ${\mathcal {L}}$ in such a way that both A and the measure $\mu$ are definable.

Example 3.3

Consider a finite non-empty subset A of a (possibly infinite group) G with tripling K, that is, with $|A\cdot A\cdot A| \le K|A|$. Then $B=A\cup A ^{-1}\cup \{\mathrm {id}_G\}$ has size at least |A| and most $2 |A|+1$, and it follows from Ruzsa calculus that $|B\cdot B\cdot B|\le 14K^3 |A|$. Given a subset $X \subseteq B\cdot B\cdot B$, set

$$\begin{aligned} \mu (X) = \frac{|X|}{ |B\cdot B\cdot B|}.\end{aligned}$$

We have thus obtained a finitely additive measure $\mu$ such that $\mu (A)\ge (14K^3)^{-1}$. Hence, the set A is acceptable (with respect to the measure $\mu$).

Furthermore, if G is abelian, it follows from the Plünnecke-Ruzsa inequality [23, Corollary 6.29] that we need only assume that A has small doubling.

Given an acceptable subset A of G with respect to the finitely additive definable measure $\mu$ and a complete type p(x) over a submodel M containing the formula A(x), define its (measure-theoretic) stabilizer ${\text {Stab}}(p)$ to be the group generated by the set

$$\begin{aligned} \mathrm {st}(p)=\{g\in G: g\cdot p(x) \cup p(x) \text { is wide}\}. \end{aligned}$$

Note that $\mathrm {st}(p)$ contains the identity element of G, whenever the type p is wide. The set $\mathrm {st}(p)$, and hence ${\text {Stab}}(p)$, is invariant under automorphisms of $\mathbb {U}$ fixing M pointwise.

Inspired by the corresponding results in geometric stability theory, Hrushovski proved in [11, Theorem 3.5] that the measure-theoretic stabilizer is type-definable and equals the set $\mathrm {st}(p)\cdot \mathrm {st}(p)$, whenever p is a wide type containing an acceptable subset A(x) with respect to some (definable) measure $\mu$. Furthermore, the stabilizer is a normal subgroup of the group $\langle A \rangle$ generated by A and has of bounded index in $\langle A \rangle$, that is, the number of cosets of ${\text {Stab}}(p)$ in $\langle A \rangle$ is bounded by the cardinality of saturation of the ambient model $\mathbb {U}$. For our purposes, we need a much weaker statement, namely, that $\mathrm {st}(p)$ contains some wide complete type, for which we will now give a simple proof.

Lemma 3.4

Let A be an acceptable subset of G with respect to the measure $\mu$, which we assume to be definable over a submodel M. Given a wide type p(x) over M containing the formula A(x), there exists a wide type q(x) over M whose realizations belong to the M-invariant set $\mathrm {st}(p)$.

Proof

Consider a sequence $(a_i)_{i\in \mathbb {N}}$ of realizations of p such that ${\text {tp}}(a_i/M\cup \{a_j\}_{j<i})$ is wide. By a standard Ramsey argument, we may assume that the sequence is indiscernible over M. Set $q={\text {tp}}(a_2 ^{-1}\cdot a_1/M)$. Since $\mathrm {st}(p)$ is M-invariant, it suffices to show that the realization $a_2 ^{-1}\cdot a_1$ of q belongs to $\mathrm {st}(p)$. Otherwise, the partial type $a_2 ^{-1}\cdot a_1\cdot p(x)\cup p(x)$ is not wide and neither is $a_1\cdot p(x)\cup a_2 \cdot p(x)$ by translation-invariance of the measure (for A is acceptable and $a_2$ is an element of A). Thus, we can find some M-definable set X(x) in p(x) contained in A(x) such that

$$\begin{aligned} \mu ( a_j\cdot X \cap a_i\cdot X)= 0 \text { for } i\ne j.\end{aligned}$$

As the definable set X is wide, there exists some natural number k such that $\frac{1}{k}< \mu (X)=\mu (a_j\cdot X)$ for all j in $\mathbb {N}$, so

$$\begin{aligned}\mu \Big (\bigcup _{i=1}^k a_i \cdot X\Big ) = \sum _{i=1}^k \mu (a_i \cdot X) = k \cdot \mu (X)>1,\end{aligned}$$

which contradicts the assumption that $\mu$ is a probability measure. $\square$

A standard application of Ruzsa’s covering argument (cf. [23, Lemma 2.14]) yields the following auxiliary result, which resonates with Lemma 2.4.

Lemma 3.5

Let A be an acceptable subset of G with respect to the measure $\mu$, which we assume to be definable over a submodel M. Given a wide M-definable subgroup $H\subseteq A\cdot A ^{-1}$ of G, there is some finite subset C of A(M) such that A is contained in $C\cdot H$.

Proof

Note that $a\cdot H\subseteq (A\cup A ^{-1})^3$ is wide for every a in A. Hence, choose a maximal subset C of A (in $\mathbb {U}$) such that $(c\cdot H) \cap (c'\cdot H) =\emptyset$ for every $c\ne c'$ in C. In particular, given any a in A, there is some c in C such that $(a\cdot H) \cap (c\cdot H)$ is non-empty. Thus, the element a lies in $c\cdot H$ and so $A \subseteq C\cdot H$.

For each c in C, we have that $\mu (c\cdot H)=\mu (H)>\frac{1}{k}$ for some k in $\mathbb {N}$. As in the proof of Lemma 3.4, we deduce that C is finite. Since both A and H are definable over the model M and A is contained in $C\cdot H$, we can take C to be a subset of A(M), as desired. $\square$

Proposition 3.6

Let A be an acceptable subset of G with respect to the measure $\mu$, which we assume to be definable over a submodel M, and assume that the formula $\varphi (x,y)=A(y\cdot x)$ is stable. Then there exists some M-definable subgroup H of G contained in $A\cdot A ^{-1}$ such that $A\subseteq C\cdot H$ for some finite subset C of A(M).

Furthermore, if G is abelian, then H can be taken to be a boolean combination of translates of A.

Proof

Since the definable set A(x) is wide, we may extend it to a wide complete $\mathcal {L}$-type p(x) over M. The $\varphi$-type $q=p\!\!\upharpoonright _{\varphi }$ contains the instance $\varphi (x,\mathrm {id}_G)=A(x)$, so the M-definable group $H={\text {Stab}}_\varphi (q)$ is clearly contained in $A\cdot A ^{-1}$.

In order to conclude the result by Lemma 3.5 (together with Remark 1.2 when G is abelian), it suffices to show that H is wide. By Lemma 3.4, the set

$$\begin{aligned}\mathrm {st}(p)=\{g\in G(\mathbb {U}): g\cdot p(x) \cup p(x) \text { is wide}\} \end{aligned}$$

contains a wide type over M. So we need only show that $\mathrm {st}(p)\subseteq H$. Let $g \in \mathrm {st}(p)$ and denote by $q_{\mid {\mathbb {U}}}(x)$ in $S_\varphi (\mathbb {U})$ the global non-forking extension of $q=p\!\!\upharpoonright _{\varphi }$. Since formulae of positive measure do not fork over $\emptyset$, we have that the partial type $g\cdot q(x) \cup q(x)$ does not fork over M, hence it is a restriction of $q_{\mid {\mathbb {U}}}(x)$. In particular, the global $\varphi$-type $g ^{-1}\cdot q_{\mid {\mathbb {U}}}(x)$ is a non-forking extension of q(x). By uniqueness of the global non-forking extension, we conclude that

$$\begin{aligned}g ^{-1}\cdot q_{\mid {\mathbb {U}}}(x)= q_{\mid {\mathbb {U}}}(x),\end{aligned}$$

so $g ^{-1}$, and thus g, lies in H as desired. $\square$

5 Main results

We are now in a position to prove our main results. Let us begin by recalling Theorem A in the introduction for the reader’s convenience.

Theorem 4.1

Given real numbers $K\ge 1$ and $\epsilon >0$ and a natural number $r\ge 2$, there exists a natural number $n=n(K, \epsilon , r)$ such that for any (possibly infinite) group G and any finite r-stable subset $A\subseteq G$ with tripling K, there is a subgroup $H\subseteq A\cdot A ^{-1}$ of G with $A\subseteq C\cdot H$ for some $C\subseteq A$ of size at most n. Moreover, there exists $C'\subseteq C$ such that

$$\begin{aligned} |A \triangle (C'\cdot H)|<\epsilon |H|.\end{aligned}$$

In particular, we conclude that

$$\begin{aligned} |A \triangle (C'\cdot H)|<(\epsilon K^2) |A|,\end{aligned}$$

by the Plünnecke-Ruzsa inequality.

Remark 4.2

It follows from Proposition 3.6 that when G is abelian, the subgroup H can be taken to be a boolean combination (whose complexity only depends on K, $\epsilon$ and r) of translates of A.

Proof

The proof proceeds by contradiction. Assuming that the statement does not hold, there are fixed K, $\epsilon$ and r such that for each n in $\mathbb {N}$, we find a finite r-stable subset $A_{n}$ of a group $G_{n}$ with tripling K such that there are no subgroup $H\subseteq A_{n}\cdot A_{n} ^{-1}$ and a finite subset C of $A_n$ of size n with $A_{n}$ contained in $C\cdot H$ and $|A_n \triangle (C'\cdot H)|< \epsilon |H|$ for some $C'\subseteq C$.

Following the approach of [11, Section 2.6] (see also [2, Proof of Theorem 1.3] and [13, Section 2.3]), we consider a suitable expansion $\mathcal {L}$ of the language of groups and regard each group $G_{n}$ as an $\mathcal {L}$-structure $M_{n}$. Choose a non-principal ultrafilter ${\mathcal {U}}$ on $\mathbb {N}$ and consider the ultraproduct $M=\prod _{{\mathcal {U}}} M_{n}$. The language $\mathcal {L}$ is chosen in such a way that the sets $A=\prod _{\mathcal U} A_{n}$ and $B=\prod _{{\mathcal {U}}} B_{n}$ are $\mathcal {L}$-definable in the group $G=\prod _{{\mathcal {U}}} G_{n}$, where $B_{n}=A_{n}\cup A_{n} ^{-1}\cup \{\mathrm {id}_G\}$. Furthermore, the counting measure

$$\begin{aligned} \mu _n(X_n) = \frac{|X_n|}{ |B_{n}\cdot B_{n}\cdot B_{n}|},\end{aligned}$$

induces a definable Keisler measure $\mu$, namely the standard part of $\lim _{{\mathcal {U}}} \mu _{n}$, on the boolean algebra of $\mathcal {L}$-definable subsets of $B\cdot B\cdot B$, such that the set A is acceptable. Now choose a sufficiently saturated elementary extension $\mathbb {U}$ of the model M and note that $\mu$ is definable over M. Also, every collection of subgroups of $M_n$ induces an M-definable group in $G(\mathbb {U})$, and vice versa.

Note that the formula $\varphi (x,y)=A(y\cdot x)$ is r-stable, by Łoś’s theorem. Moreover, by construction the set A is acceptable. Hence, by Proposition 3.6, there is an M-definable subgroup H contained in $A\cdot A ^{-1}$ such that $A\subseteq C\cdot H$, for some finite set C in A(M). By Fact 1.1, after possibly increasing the size of C, we may assume that H is $H_\varphi ^0$.

Let $C'$ be the collection of coset representatives c in C such that $A\cap (c\cdot H)$ is wide. Since $\mu$ is finitely additive and $A\subseteq C\cdot H$, we have that

$$\begin{aligned} \mu (A)= \sum \limits _{c\in C} \mu \big (A \cap (c\cdot H)\big ) = \sum \limits _{c\in C'} \mu \big (A \cap (c\cdot H)\big ) = \mu \big (A \cap (C'\cdot H)\big ),\end{aligned}$$

so

$$\begin{aligned} \mu \big (A \setminus (C'\cdot H)\big ) = \mu (A) - \mu \big (A \cap (C'\cdot H)\big ) =0.\end{aligned}$$

Thus, in order to compute $\mu \big (A \triangle (C'\cdot H)\big )$, we need only consider

$$\begin{aligned} \mu \big ((C'\cdot H) \setminus A\big )=\sum \limits _{c\in C'} \mu \big ((c\cdot H)\setminus A\big ) .\end{aligned}$$

For c in $C'$, note that the definable set $c ^{-1}((c\cdot H)\setminus A)$ equals $H\setminus (c ^{-1}\cdot A)$, which is contained in $A\cdot A ^{-1}$, and hence has a (real-valued) measure. Since $\mu (H)>0$, the measure $\mu$ normalised by $\mu (H)$ induces a left-invariant Keisler measure on the definable subsets of H of the form $X\cap H$, where X is $\varphi$-definable over M. By [2, Theorem 2.3 (vi)], such a measure is unique and furthermore wide sets are exactly the generic sets (cf. Fact 1.1). By construction of $H_\varphi ^0$, we conclude that $\mu (H\setminus c ^{-1}\cdot A)=0$ for c in $C'$, so

$$\begin{aligned} \mu \big (A \triangle (C'\cdot H)\big )= \mu \big (A \setminus (C'\cdot H)\big ) + \mu \big ((C'\cdot H) \setminus A\big ) =0 <\frac{\epsilon }{2}\cdot \mu (H).\end{aligned}$$

However, for $n\ge |C|$ sufficiently large, we conclude by Łoś’s theorem that the corresponding trace $A_{n}$ is contained in $C(A_n)\cdot H(G_{n})$ and

$$\begin{aligned} \big |A_n\triangle \big (C'(A_n)\cdot H(G_n) \big )\big |<\epsilon |H(G_n)| .\end{aligned}$$

This yields the desired contradiction. $\square$

We now turn to the proof of Theorem B in the introduction. First, we note that a straightforward compactness argument yields (non-quantitative) bounds on the complexity of the representation of a weakly normal subset as a boolean combination of suitably chosen subgroups. The fact that the subgroups in Proposition 4.3 below can be expressed as bounded boolean combinations of translates of A goes beyond [19, Theorem 1.4].

Proposition 4.3

Given natural numbers r, k, and l, there are natural numbers $n=n(r,k,l)$ , $m=m(r,k,l)$ and $t=t(r,k,l)$ such that for any abelian group G and any subset $A\subseteq G$ with an (r, k, l)-weakly normal representation, the set A is a boolean combination of complexity at most t of cosets of subgroups $H_1,\ldots , H_n$ of G. Moreover, each subgroup $H_i$ is a boolean combination of complexity at most m of translates of A.

Proof

Otherwise, as in the proof of Theorem 4.1, assume that, for fixed positive integers r, k and l, there are n, m and t in $\mathbb {N}$, and an abelian group $G_{n,m,t}$ and a subset $A_{n,m,t}$ such that $A_{n,m,t}$ admits an (r, k, l)-weakly normal representation, but it is not a boolean combination of complexity at most t of cosets of n subgroups of G, each of which is a boolean combination of complexity at most m of translates of the set $A_{n,m,t}$.

Set $G_n=G_{n,n,n}$ and $A_n=A_{n,n,n}$. Since each $A_n$ has an (r, k, l)-weakly normal representation, there are r-weakly normal subsets $B_{n,1},\ldots ,B_{n,k}$ and $C_{n,1},\ldots ,C_{n,l}$ such that

$$\begin{aligned} A_n = \bigcup \limits _{j=1}^k B_{n,j} \cap \bigcup \limits _{i=1}^l G_n\setminus C_{n,i} .\end{aligned}$$

We consider an expansion $\mathcal {L}'$ of $\mathcal {L}$ with $k+l$ new predicates and regard each group $G_n$ as an $\mathcal {L}'$-structure $M_n$, where the predicates are interpreted as the sets $B_{n,1},\ldots ,B_{n,k}, C_{n,1},\ldots ,C_{n,l}$. Choose a non-principal ultrafilter ${\mathcal {U}}$ on $\mathbb {N}$, and consider the ultraproduct $G=\prod _{{\mathcal {U}}} G_n$. The definable set $A=\prod _{\mathcal U} A_n$ admits an (r, k, l)-weakly normal representation, by Łoś’s theorem, thus the definable set A is a boolean combination of r-weakly normal formulae.

By Corollary 2.5, the definable set A is a boolean combination of complexity at most $t_0$ of $n_0$ definable subgroups, each of which is itself a boolean combination of complexity at most $m_0$ of translates of A.

Łoś’s theorem gives the desired contradiction, by choosing $n\ge n_0+m_0+t_0$ sufficiently large. $\square$

Theorem 4.4

Given natural numbers r, k, and l, there are natural numbers $n=n(r,k,l)$ and $m=m(r,k,l)$ such that for any abelian group G and any subset $A\subseteq G$ with an (r, k, l)-weakly normal representation, there are subgroups $H_1,\ldots , H_n$ of G, each contained in $A-A$, with

$$\begin{aligned}A\subseteq \bigcup \limits _{i=1}^{n} g_i+H_i,\end{aligned}$$

for some $g_1,\ldots , g_n$ in A. Furthermore, each $H_i$ is a boolean combination of complexity at most m of translates of A.

Proof

As in the proof of Proposition 4.3, if the statement does not hold, there are fixed integers r, k and l such that for each n and m in $\mathbb {N}$, we find an abelian group $G_{n,m}$ and a subset $A_{n,m}$ such that $A_{n,m}$ admits an (r, k, l)-weakly normal representation, yet

$$\begin{aligned} A_{n,m}\not \subseteq \bigcup \limits _{i=1}^{n} g_i+H_i,\end{aligned}$$

for any $g_1,\ldots , g_n$ in $A_{n,m}$, for all subgroups $H_1,\ldots , H_n$ of $G_{n,m}$, each contained in $A_{n,m}-A_{n,m}$, which are boolean combinations of complexity at most m of translates of $A_{n,m}$.

Set $G_n=G_{n,n}$ and $A_n=A_{n,n}$. Choose a non-principal ultrafilter ${\mathcal {U}}$ on $\mathbb {N}$, and consider the ultraproduct $G=\prod _{{\mathcal {U}}} G_n$. Choose a sufficiently saturated elementary extension $\mathbb {U}$ of the model $M=\prod _{{\mathcal {U}}} M_n$. As observed before, the definable set $A=\prod _{\mathcal U} A_n$ admits an (r, k, l)-weakly normal representation, by Łoś’s theorem, so the formula $\varphi (x,y)=A(x+y)$ is a boolean combination of r-weakly normal formulae.

Let ${\mathcal {F}}$ be the family of cosets $m+H$, where m belongs to A(M) and the definable subgroup $H\subseteq A-A$ over M is given by a finite boolean combination of translates of A. By Łoś’s theorem, no finite collection of $\mathcal F$ covers A: otherwise, considering the traces of these subgroups in the corresponding $G_{n,n}$ for sufficiently large n, we would have that $A_{n,n}$ is covered by a finite union of translates of these subgroups, which have bounded complexity as boolean combinations of translates of $A_{n,n}$.

By compactness, we obtain a complete $\varphi$-type p(x) over M containing the formula $A(x)=\varphi (x,\mathrm {id}_G)$ such that the partial type

$$\begin{aligned} p(x)\cup \{\lnot (m+H)(x)\}_{m+H\in {\mathcal {F}}}, \end{aligned}$$

is consistent. By Remark 1.2, the subgroup ${\text {Stab}}_\varphi (p)$ is $\varphi$-definable, so it is a boolean combination of translates of A. Clearly ${\text {Stab}}_\varphi (p) \subseteq A-A$, by construction. Lemma 2.4 yields that the type p contains the definable set $\big (A\cap (m+{\text {Stab}}_\varphi (p))\big )(x)$, for some m in M. In particular, the M-definable set $\big (A\cap (m+{\text {Stab}}_\varphi (p))\big )(x)$ is non-empty, so there is a realisation in M, since M is an elementary substructure. Replacing the element m, we may assume that it lies in A(M). Hence, the coset $m+{\text {Stab}}_\varphi (p)$ belongs to the family ${\mathcal {F}}$, which contradicts our choice of p and hence implies the result. $\square$

As an immediate consequence we obtain the result for finite sets stated as Theorem B in the introduction. An analogous result holds whenever G carries a finitely additive probability measure $\mu$ on the boolean algebra of translates of A with $\mu (A)>0$.