This is an adaptation of a talk I gave recently for a program at IPAM. In this talk, I gave a (very informal and non-rigorous) overview of Hrushovski’s use of model-theoretic techniques to establish new Freiman-type theorems in non-commutative groups, and some recent work in progress of Ben Green, Tom Sanders and myself to establish combinatorial proofs of some of Hrushovski’s results.

— 1. Non-commutative Freiman theorems —

To avoid a preponderance of quantifiers, I will be somewhat loose with the {O()} notation and with terminology such as “bounded” here. Precise statements can be found in Hrushovski’s paper (and in a forthcoming paper of Ben, Tom, and myself).

Let {A} be a finite non-empty subset of a (possibly non-abelian) group {G}. We say that {A} has bounded doubling if {|A \cdot A| \leq K|A|} for some {K = O(1)}, where {A \cdot A = \{ab: a,b \in A \}} and {|A|} is the cardinality of {A}. By a non-commutative Freiman theorem, I mean a result that classifies (up to losses in the {K} parameter) what sets of bounded doubling look like.

For instance, if {K=1}, it is easy to see that {|A \cdot A| \leq |A|} occurs if and only if {A} is a coset {xH=Hx} of a finite subgroup {H} by an element {x} in the normaliser {N(H)} of {H}. More generally, as we mentioned earlier in this post, it can be shown by elementary means that if {K < \phi}, where {\phi := \frac{1+\sqrt{5}}{2} = 1.618\ldots} is the golden ratio, then sets of doubling less than {K} are controlled by a finite subgroup. Here, we say that one finite set {B} controls another {A} if they have comparable size (i.e. {|B| = O(|A|)} and {|A| = O(|B|)}) and if {A} can be covered by a bounded number of left or right translates of {B} (i.e. {A \subset X \cdot B, B \cdot X} for some {X} of size {|X| = O(1)}). Note that if {B} has bounded doubling, and {B} controls {A}, then {A} has bounded doubling also. Thus it is natural for the conclusion of a Freiman-type theorem to be that a set of bounded doubling is controlled by a “structured” set of small doubling.

What does “structured” mean exactly? There is not yet a full consensus on what the list of structured objects should be (see this earlier post for more discussion), but things are well understood in the abelian case, at least. Examples of structured sets of bounded doubling here include

  • Finite subgroups;
  • Arithmetic progressions;
  • Generalised arithmetic progressions (i.e. sums of arithmetic progressions) of bounded dimension;
  • Coset progressions (sums of finite subgroups and generalised arithmetic progressions);
  • Balls in a word metric (or weighted word metric, with some generators allowed to have weight zero if they have finite order). These are closely related to coset progressions, indeed they are essentially the same class of sets (up to mutual control).

Freiman’s theorem, proven in the torsion-free abelian case by Freiman (with simplified proofs later given by Ruzsa and by Bilu), and in the general abelian case by Green and Ruzsa, asserts (roughly speaking) that all sets of small doubling are controlled by a coset progression (or equivalently, by a ball in a word metric). Except for the issue of quantifying constants, this is a satisfactory description of sets of small doubling. (For more on the question of improving the constants, see this guest blog post of Ben Green.)

In the non-abelian case, known examples of structured sets of bounded doubling include

  • Finite subgroups;
  • Balls in a (weighted) word metric in a nilpotent group (of bounded step);
  • Extensions of a structured set of bounded doubling by finite groups (i.e. given a short exact sequence {0 \rightarrow K \rightarrow G \rightarrow H \rightarrow 0} of groups with {K} finite, the pullback of any structured set in {H} to {G} will still qualify as a structed set of small doubling).

One may optimistically conjecture that this is the full list (up to control), in that every set of small doubling in an arbitrary group is controlled by a structured set of small doubling in the above list. This may be a bit too optimistic, but I do not know of any counterexamples, and in various special groups (e.g. nilpotent groups, free groups, simple or semisimple algebraic groups, and to a lesser extent solvable groups) the claim has been largely (though not completely) verified.

A small technical note: it is often convenient to work not with sets of small doubling, but rather sets of small tripling (so {|A \cdot A \cdot A| = O(|A|)}). This is a stronger condition in the nonabelian case; for instance, if {A = H \cup \{x\}} for a finite subgroup {H} and for some {x} not in the normaliser of {H}, then {A} has small doubling but usually will have large tripling (due to the presence of {HxH} in {A^3}). On the other hand, small tripling turns out to be sufficient to imply small quadrupling, etc. It is also convenient to assume symmetry {A = A^{-1}}. The connections between these properties is well understood, for instance it is known that every set of small doubling is controlled by a symmetric set of small tripling.

— 2. Hrushovski’s results —

Using a new (and rather non-trivial) model-theoretic result in stable group theory (of which I will say more later), Hrushovski was able to establish three results of Freiman type in non-abelian settings. The first result is the easiest to prove (following more or less directly from the model-theoretic result), but requires that {A} is “simple” or “perfect” in some statistical sense. Recall that if a group {G} is simple, then every non-trivial conjugacy class {g^G := \{ hgh^{-1}: h \in G \}} (with {g} not the identity) will necessarily generate the group {G}. In a similar vein, we have

Theorem 1 (Hrushovski Corollary 1.2, slightly modified) Let {A \subset G} be symmetric and of bounded tripling, and let {m, k \geq 1} be (bounded) integers. Suppose that for at least {(1-\epsilon)} of tuples {a_1,\ldots,a_k \in A^2}, one has

\displaystyle |a_1^A \ldots a_k^A| \geq |A|/m,

where {a^A := \{hah^{-1}: h \in A \}} being a partial conjugacy class. If {\epsilon} is sufficiently small depending on {k, m} and the tripling constant, then {A} is controlled by a finite subgroup of {G}.

By combining the model theoretic results with some techniques from algebraic group theory (in particular, some machinery of Larsen and Pink) the following variant was shown:

Theorem 2 (Hrushovski Theorem 1.3, slightly modified) Let {A \subset G} be symmetric and of bounded tripling in a semisimple algebraic group {G} of bounded dimension. Then {A} is either controlled by a finite subgroup of {G}, or is contained in finitely many translates of a proper connected algebraic subgroup of {G}.

Finally, by combining the model theoretic results with the deep theory of Gleason and Yamabe on Hilbert’s fifth problem, the following general result was obtained in an arbitrary group:

Theorem 3 (Hrushovski Theorem 1.1, slightly modified) Let {A \subset G} be symmetric and of bounded tripling in an arbitrary group {G}. Then there exists a long sequence

\displaystyle A^4 \supset B_1 \supset B_2 \supset \ldots \supset B_M

where the {B_i} behave like a nested sequence of nilpotent balls in the following sense:

  • Each of the {B_i} is symmetric and contains the origin;
  • Each of the {B_i} control {B_{i-1}}, with {B_1} controlling {A^4};
  • {B_i \cdot B_i \subset B_{i-1}};
  • {[B_i,B_j] \subset B_{i+j}} (for {i+j \leq M}), where {[B_i,B_j] := \{ghg^{-1}h^{-1}: g \in B_i, h \in B_j \}}.

Furthermore one can take {M} to be arbitrarily large compared to the constants in the control statements.

The conclusion is similar to, but not quite identical with, a certain “weak Freiman theorem” conjectured by Ben Green (and partially verified by Tom Sanders). It is not yet well understood how to exploit this type of conclusion effectively, but nevertheless this represents one of the deepest facts we know about sets of bounded doubling in a completely arbitrary group.

Let me briefly (and inaccurately) describe how model theory enters in this picture. In each of these claims, we are trying to prove a combinatorial statement, which is roughly of the form “if {A \subset G} has bounded tripling and obeys some additional properties, then {A} is controlled by something structured, with some parameters {K}“, where the parameter {K} determines how strong the control is.

We use the compactness and contradiction method to establish such claims. Suppose the claim failed, then by negating all the quantifiers (and invoking the axiom of choice if necessary), one can find a sequence {A_n \subset G_n} of “increasingly bad” counterexamples in various groups {G_n}, such that the {A_n} have uniformly bounded tripling (and obey the other hypotheses uniformly in {n} also), but for which the conclusion fails for any given {K}, if {n} is sufficiently large depending on {K}. (For instance, {A_n} might not be coverable by {K} copies of a subgroup of size at least {|A_n|/K}, if {n} is large enough depending on {K}.)

Now, one takes an ultraproduct of these finitary examples {A_n \subset G_n} to create an infinitary “limiting example” {A \subset G} in a much larger group {G} (the ultraproduct of the {G_n}). Typically, {A} and {G} will now both be uncountably infinite, and so notions of cardinality are no longer useful to define “small doubling” or “small tripling”. However, in each finite setting {A_n \subset G_n}, one can define a normalised cardinality {\mu_n(B)} of any finite set {B\subset G_n} by {\mu_n(B) := |B|/|A_n|}, thus we are using {A_n} as the “unit” of cardinality here. We can take an ultralimit of the {\mu_n} also (and restrict to the standard part of this limit), to create a limiting “measure” {\mu(B)} (known as a Kiesler measure) which assigns an extended real number in {[0,+\infty]} to any definable subset {B} of {G}. Thus for instance {\mu(A)=1}. We will not precisely define what it means for a set to be definable here, but roughly it means any set that can be defined in terms of {A}, the group operations, the Keisler measure, and a finite number of constant elements of {G}. (Thus for instance {A \cdot A}, or {x_1 \cdot A \cap x_2 \cap A}, or {Sym_\alpha(A) := \{ x \in A: \mu(A \cap xA) > \alpha \}} would be definable sets for constants {x_1,x_2 \in G} and {\alpha\in {\mathbb R}}.) The Keisler measure behaves in many ways like a Haar measure (in particular, it is left-invariant and right-invariant), although there are some technical differences, most notably it is only finitely additive rather than countably additive.

Anyway, with this Kiesler measure in hand, a bounded doubling condition becomes {\mu(A \cdot A) = O(1)}, and similarly for bounded tripling conditions, and similar hypotheses.

The definable subsets of {G} form a boolean algebra, and can be used as a base to define a topology on {G} (closely related to the Stone topology of {G}). In particular, the closed sets of these topology are the intersection of a (possibly infinite) number of definable sets, and are thus known as {\bigcap}-definable sets (or {\bigwedge}-definable sets, or type-definable sets). Such sets can be non-trivial in this infinitary world but do not rigorously have any non-trivial presence in any finitary setting. For instance, one could imagine continually refining the set {A}, for instance by writing {A_1 := A \cap (x_1 \cdot A)}, {A_2 := A_1 \cap (x_2 \cdot A_1)}, etc. for some sequence {x_1,x_2,\ldots}; this is a typical construction in finitary additive combinatorics. Each of these {A_i} is definable, so the intersection {\bigcap_{i=1}^\infty A_i} is {\bigcap}-definable. In a finitary setting, such an infinite intersection would likely be trivial (i.e. empty); but in the infinitary setting the intersection can remain non-trivial. But as it is only {\bigcap}-definable rather than definable, it does not directly correspond to anything non-trivial in the finitary world.

In order to have {\bigwedge}-definable sets non-trivial, it is very useful to impose various compactness properties on the topology of definable sets; in particular, if {G} was genuinely compact, then any family of definable sets which had non-empty finite intersections, would have non-empty complete intersections. In general, {G} will not be compact in this manner, but it is possible to extend {G} (and {A}) to a larger model which is an elementary extension of the existing model (in the sense that every first-order statement true in the original model, is still true then the extension), in such a way that this sort of compactness property is obtained (at least when one does not use an enormous number of constants when building definable sets). This type of property is known as saturation, and one can always find a saturated extension after enlarging {G} (and {A}) a sufficiently large number of times. (This “sufficiently large” may be extremely large, depending on how strong a saturation property one wants; for instance, measurable cardinals may be involved.)

Once one has saturation, the definable sets behave well in various ways, and one can study how numerous these sets are, and how they relate to each other. Part of this study is known as stability theory, or stable group theory when applied particularly to group models. By using methods from this theory, one can define various useful notions (such as the “dimension” of a definable set, or the notion of various elements being “in general position” within a definable set). Using this type of machinery, Hrushovski proved a rather technical result in stable group theory, which when specialised to the context of sets of small tripling, gives

Theorem 4 (Hrushovski Theorem 3.4, special case) Let {\mu} be an invariant Kiesler measure, and let {A \subset G} which is symmetric and has small tripling in the sense that {\mu(A) = 1} and {\mu(A \cdot A \cdot A) < \infty}. Then {A^4} contains a normal {\bigcap}-definable subgroup {S}, which is wide in the sense that every definable set that contains {S} has positive measure. (As {S} is only {\bigcap}-definable rather than definable, {S} cannot be measured directly; one can only measure the definable sets that {S} is contained in.)

If {S} were itself definable, it would have positive measure, and it would not be hard to show that the subgroup {S} controls {A}. But in general {S} is smaller than this. If for instance {A_n} were a progression such as {\{-n,\ldots,n\}} in the integers, then in the ultralimit {A} would be something like a non-standard interval {\{-N,\ldots,N\}} in the nonstandard integers (where {N} is an unbounded nonstandard integer), and {S} would be something like the intersection of the definable sets {S_i := \{ x: ix \in A \} = \{ -\lfloor N/i\rfloor, \ldots, \lfloor N/i\rfloor\}} for all standard {i}. Each of the {S_i} would have positive measure ({1/i}), but this measure goes to zero as {i \rightarrow \infty}, so {S} does not itself has positive measure; but it remains wide (and is a normal subgroup).

As mentioned earlier, this theorem is one of the key ingredients used to prove Theorems 1, 2, 3, though in the case of Theorems 2, 3 one also needs methods from algebraic group theory and from topological group theory respectively.

— 3. Combinatorial approach —

Recently, Sanders and Croot-Sisask independently provided elementary proofs of the following result:

Lemma 5 (Locating a core set) Let {A} be a symmetric set of small doubling, and let {k \geq 1}. Then there exists a set {S \subset A} with {|S| \gg_k |A|} such that {S^k \subset A^4}.

(A weaker version of this lemma was also established by myself previously.)

Proof: (Sketch of Sanders’ proof) For any {B \subset A}, the set {B \cdot A} has cardinality between {|A|} and {K|A|}, where {K} is the doubling constant of {A}. From this observation and a pigeonholing argument, one can find a subset {B} of {A} which is not too small, with the property that {B' \cdot A} is not much smaller than {B \cdot A} for any dense subset {B'} of {B}, in particular

(say).

We now let {S} be the set of elements {s} such that the set {B' := B \cap sB} is large; this set can be shown to be not too small. From (1) we then have

\displaystyle |(B \cdot A) \cap s(B \cdot A)| \geq |(B \cap sB) \cdot A| \geq (1 - \frac{1}{10 k}) |B \cdot A|,

thus {s} only shifts {B \cdot A} by a relative fraction of at most {1/10k}. Iterating this, we see that every element in {S^k} cannot shift {B \cdot A} completely outside itself, and so must lie in {(B \cdot A) \cdot (B \cdot A)^{-1} \cdot A^4} as claimed.

(Sketch of the Croot-Sisask proof) This is a random sampling argument. Let {\Sigma} be a bounded size random subset of {A}. Then with high probability, one can approximate {1_A * 1_A} in an {L^2} sense by {\frac{|\Sigma|}{|A|} 1_{\Sigma} * 1_A}. On the other hand, one can find many {s} such that {\Sigma, s\Sigma} both sit inside {A} with reasonable probability. Because of this, one can find many {s} that do not shift {1_A*1_A} very much. Letting {S} be the set of such {s}, one obtains the claim by a similar argument as before (using a function {1_A*1_A} instead of a set {B \cdot A}, but the argument is much the same). \Box

On the model-theoretic side, this lemma is like a weak version of Theorem 4 in which the subgroup {S} is not assumed to be normal. Recall however in group theory that any finite index subgroup {H} of a group {G} contains a normal subgroup {H'}, formed by intersecting all the conjugates of {H} together. It turns out that one can pull off a similar trick in the bounded tripling regime, and obtain

Corollary 6 (Locating a normal core set) Let {A} be a symmetric set of small tripling, and let {k \geq 1}. Then there exists a set {S \subset A} with {|S| \gg_k |A|} such that {(S^A)^k \subset A^4}, where {S^A := \{ asa^{-1}: a \in A, s \in S \}}.

This is broadly analogous to Theorem 4; the {\bigcap}-definable set {S} in that theorem morally corresponds to the intersection of all the sets {S = S_k} arising in Corollary 6, though I have not attempted to make this correspondence more rigorous than a mere heuristic analogy.

Ben Green, Tom Sanders and I were able to use Corollary 6 to provide finitary (and quantitative) proofs of Theorems 1, 2 of Hrushovski, though Theorem 3 still eludes us. Here is a sketch of the proof of Theorem 1. Using Corollary 6, we can find a tiny (but not too tiny) set {S} such that {(S^A)^{kl} \subset A^4} for some large {l}. Combining this with the hypothesis of Theorem 1, we can find (if {\epsilon} is small enough) {a_1,\ldots,a_k \in S} such that {(a_1^A \ldots a_k^A)^l \subset A^4}, and such that {a_1^A \ldots a_k^A} is quite large (cardinality at least {|A|/m}). Choosing {l} large enough, we thus see from the pigeonhole principle that there is an intermediate power {B = (a_1^A \ldots a_k^A)^r} of {a_1^A \ldots a_k^A} whose doubling constant is small, say less than the golden ratio {\phi}. But then by previous results, {B} is controlled by a subgroup, and then it is not hard to show that {A} is controlled also.

The proof of Theorem 2 is similar. In lieu of the hypothesis of Theorem 1, one uses the classical fact that in a simple group {G}, there exists an integer {k} (called the covering number of {G}) such that for every non-trivial conjugacy class {g^G}, {(g^G)^k = G}. (Basically, the point is that the dimension of a non-trivial conjugation-invariant subvariety of {G} must increase when one doubles it.) The next ingredient is a sharp form of the “escape from subvarieties” phenomenon, namely that for any algebraic variety {V} in a simple group {G} and any symmetric set {A} in {G}, one has {|A \cap V| \ll |A^{O(1)}|^{\dim(V)/\dim(G)}}; in particular, {A} cannot concentrate in {V} if {V} has strictly smaller dimension than {V}. This estimate is (very) implicit in work of Larsen and Pink, and later by Hrushovski; closely related estimates were also established by Helfgott. One can obtain this estimate by inspecting the double counting identity

\displaystyle |A \cap V| |A \cap W| = \sum_{x \in (A^2 \cap VW)} |A \cap (V \cap x W^{-1}) \cap x A^{-1}|

for various algebraic varieties {V,W}; the details are slightly technical and will not be presented here.