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 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 be a finite non-empty subset of a (possibly non-abelian) group . We say that has bounded doubling if for some , where and is the cardinality of . By a non-commutative Freiman theorem, I mean a result that classifies (up to losses in the parameter) what sets of bounded doubling look like.
For instance, if , it is easy to see that occurs if and only if is a coset of a finite subgroup by an element in the normaliser of . More generally, as we mentioned earlier in this post, it can be shown by elementary means that if , where is the golden ratio, then sets of doubling less than are controlled by a finite subgroup. Here, we say that one finite set controls another if they have comparable size (i.e. and ) and if can be covered by a bounded number of left or right translates of (i.e. for some of size ). Note that if has bounded doubling, and controls , then 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 of groups with finite, the pullback of any structured set in to 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 ). This is a stronger condition in the nonabelian case; for instance, if for a finite subgroup and for some not in the normaliser of , then has small doubling but usually will have large tripling (due to the presence of in ). On the other hand, small tripling turns out to be sufficient to imply small quadrupling, etc. It is also convenient to assume symmetry . 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 is “simple” or “perfect” in some statistical sense. Recall that if a group is simple, then every non-trivial conjugacy class (with not the identity) will necessarily generate the group . In a similar vein, we have
where being a partial conjugacy class. If is sufficiently small depending on and the tripling constant, then is controlled by a finite subgroup of .
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 be symmetric and of bounded tripling in a semisimple algebraic group of bounded dimension. Then is either controlled by a finite subgroup of , or is contained in finitely many translates of a proper connected algebraic subgroup of .
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:
where the behave like a nested sequence of nilpotent balls in the following sense:
- Each of the is symmetric and contains the origin;
- Each of the control , with controlling ;
- (for ), where .
Furthermore one can take 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 has bounded tripling and obeys some additional properties, then is controlled by something structured, with some parameters “, where the parameter 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 of “increasingly bad” counterexamples in various groups , such that the have uniformly bounded tripling (and obey the other hypotheses uniformly in also), but for which the conclusion fails for any given , if is sufficiently large depending on . (For instance, might not be coverable by copies of a subgroup of size at least , if is large enough depending on .)
Now, one takes an ultraproduct of these finitary examples to create an infinitary “limiting example” in a much larger group (the ultraproduct of the ). Typically, and 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 , one can define a normalised cardinality of any finite set by , thus we are using as the “unit” of cardinality here. We can take an ultralimit of the also (and restrict to the standard part of this limit), to create a limiting “measure” (known as a Kiesler measure) which assigns an extended real number in to any definable subset of . Thus for instance . 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 , the group operations, the Keisler measure, and a finite number of constant elements of . (Thus for instance , or , or would be definable sets for constants and .) 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 , and similarly for bounded tripling conditions, and similar hypotheses.
The definable subsets of form a boolean algebra, and can be used as a base to define a topology on (closely related to the Stone topology of ). In particular, the closed sets of these topology are the intersection of a (possibly infinite) number of definable sets, and are thus known as -definable sets (or -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 , for instance by writing , , etc. for some sequence ; this is a typical construction in finitary additive combinatorics. Each of these is definable, so the intersection is -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 -definable rather than definable, it does not directly correspond to anything non-trivial in the finitary world.
In order to have -definable sets non-trivial, it is very useful to impose various compactness properties on the topology of definable sets; in particular, if was genuinely compact, then any family of definable sets which had non-empty finite intersections, would have non-empty complete intersections. In general, will not be compact in this manner, but it is possible to extend (and ) 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 (and ) 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 be an invariant Kiesler measure, and let which is symmetric and has small tripling in the sense that and . Then contains a normal -definable subgroup , which is wide in the sense that every definable set that contains has positive measure. (As is only -definable rather than definable, cannot be measured directly; one can only measure the definable sets that is contained in.)
If were itself definable, it would have positive measure, and it would not be hard to show that the subgroup controls . But in general is smaller than this. If for instance were a progression such as in the integers, then in the ultralimit would be something like a non-standard interval in the nonstandard integers (where is an unbounded nonstandard integer), and would be something like the intersection of the definable sets for all standard . Each of the would have positive measure (), but this measure goes to zero as , so 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 —
Lemma 5 (Locating a core set) Let be a symmetric set of small doubling, and let . Then there exists a set with such that .
(A weaker version of this lemma was also established by myself previously.)
Proof: (Sketch of Sanders’ proof) For any , the set has cardinality between and , where is the doubling constant of . From this observation and a pigeonholing argument, one can find a subset of which is not too small, with the property that is not much smaller than for any dense subset of , in particular
We now let be the set of elements such that the set is large; this set can be shown to be not too small. From (1) we then have
thus only shifts by a relative fraction of at most . Iterating this, we see that every element in cannot shift completely outside itself, and so must lie in as claimed.
(Sketch of the Croot-Sisask proof) This is a random sampling argument. Let be a bounded size random subset of . Then with high probability, one can approximate in an sense by . On the other hand, one can find many such that both sit inside with reasonable probability. Because of this, one can find many that do not shift very much. Letting be the set of such , one obtains the claim by a similar argument as before (using a function instead of a set , but the argument is much the same).
On the model-theoretic side, this lemma is like a weak version of Theorem 4 in which the subgroup is not assumed to be normal. Recall however in group theory that any finite index subgroup of a group contains a normal subgroup , formed by intersecting all the conjugates of together. It turns out that one can pull off a similar trick in the bounded tripling regime, and obtain
This is broadly analogous to Theorem 4; the -definable set in that theorem morally corresponds to the intersection of all the sets 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 such that for some large . Combining this with the hypothesis of Theorem 1, we can find (if is small enough) such that , and such that is quite large (cardinality at least ). Choosing large enough, we thus see from the pigeonhole principle that there is an intermediate power of whose doubling constant is small, say less than the golden ratio . But then by previous results, is controlled by a subgroup, and then it is not hard to show that 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 , there exists an integer (called the covering number of ) such that for every non-trivial conjugacy class , . (Basically, the point is that the dimension of a non-trivial conjugation-invariant subvariety of 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 in a simple group and any symmetric set in , one has ; in particular, cannot concentrate in if has strictly smaller dimension than . 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
for various algebraic varieties ; the details are slightly technical and will not be presented here.