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

Theorem 1 (Hrushovski Corollary 1.2, slightly modified)Let be symmetric and of bounded tripling, and let be (bounded) integers. Suppose that for at least of tuples , one haswhere 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:

Theorem 3 (Hrushovski Theorem 1.1, slightly modified)Let be symmetric and of bounded tripling in an arbitrary group . Then there exists a long sequencewhere 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 iswidein 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 — **

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

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

(say).

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

Corollary 6 (Locating a normal core set)Let be a symmetric set of small tripling, and let . Then there exists a set with such that , where .

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.

## 23 comments

Comments feed for this article

8 December, 2009 at 6:22 am

HaraldIn , surely you mean rather than ?

[Yes, thanks – T.]While this is true in a general moral sense, you may need some conditions, at least if the group is not simple; I understand, then, that you are still assuming that G is simple at this point. I was discussing this a little with Breuillard over the weekend – in my paper on SL_3, I proved this in all cases that I needed; it is clear that the hypotheses could be relaxed (in particular: while dim(V) always divided dim(G) in the cases I was studying, one need not make such a requirement, thanks to the fact that one can iterate the procedure) but it was and is not completely clear to me what the most general conditions would be.

You really mean that this should be true for all simple algebraic groups, with no further conditions? That would be very nice. I take you are getting polynomial growth?

(For the benefit of other readers: my approach to proving this is to stick V into different directions by conjugation, and to multiply the different copies of A \cap V that one gets.

One can always use stick V in “generic” directions, thanks to escape from subvarieties; in many circumstances, this is enough for the different copies of V to have only zero-dimensional pairwise intersections. If they do not, one should still get the result one wants unless an intersection of two copies of V has many elements of A on it –

but if that is the case, one can pass to that intersection and iterate, since it will have

lower dimension than V. I can see how this actually ought to work for any simple group, but I have not checked the details.)

8 December, 2009 at 12:03 pm

Terence TaoYes, this is all for simple groups; the plan here is to first get Freiman type theorems in the simple group case and then climb up a bunch of short exact sequences to get up to the semisimple case (since small doubling is more or less preserved under homomorphisms and with intersecting with fibres of such homomorphisms).

The Larsen-Pink argument shows that bounds of the form can be iteratively improved until the dependence of the exponent on the dimension becomes the optimal exponent . It’s not too different from the machinery in your paper: start with V and W being counterexamples to the inequality one is trying to prove, with V of maximal dimension and W of minimal dimension. One can conjugate one of these by an element of A (using escape from subvarieties and simplicity) to ensure that VW has strictly larger dimension than V, and hence the fibres have strictly lesser dimension than W generically. In particular, the estimates one wants are already true in those varieties. At this point one uses the double counting inequality mentioned in the post to get a contradiction.

This part of the argument is indeed polynomial, but the stuff about getting the normal subgroup has at least one exponential loss in it (perhaps two). We’re still working on trying to clean it all up…

9 December, 2009 at 2:32 am

AnonymousAnd I take the implied constants in {|A \cap V| \ll |A^{O(1)}|^{\dim(V)/\dim(G)}} depend only on the dimension and the degree of V and G?

8 December, 2009 at 6:26 am

HaraldPS. If G were not required to be simple, then, as I am sure you are aware, you could just take G = a Borel subgroup of what have you and U = the unipotent subgroup of B, and the inequality would not be true.

8 December, 2009 at 8:44 am

Ben GreenTerry,

The link to Larsen and Pink’s paper is broken. This one worked for me:

It doesn’t appear that this was ever published.

[Thanks! – T.]Ben

8 December, 2009 at 9:21 am

HaraldTerry,

Actually, which bit of Larsen and Pink is this implicit in?

8 December, 2009 at 10:26 am

Ben GreenHarald: Section 4.

8 December, 2009 at 3:04 pm

Terence TaoAnd also Section 5 of Hrushovski (in particular, Proposition 5.5 is the model-theoretic analogue of the dimension inequality mentioned here). It takes a certain amount of liberal translating from one language to another to put Hrushovski’s argument (itself a liberal translation of Larsen-Pink) in combinatorial form, though.

9 December, 2009 at 4:55 am

Emmanuel KowalskiI asked Richard Pink last year why this paper with Larsen had not been published, and he said that it had been accepted modulo modifications quite a while ago, but they never actually came to finalize those changes. He said the (potential) difficulties had been in their definition and use of “sufficiently general” subgroups (section 2), since this is not the standard notion of “generic” objects in algebraic geometry.

9 December, 2009 at 6:46 am

bengreenEmmanuel,

That’s amusing. Though I don’t properly understand the definition of “sufficiently general” since I don’t speak the language of schemes, it’s sort-of clear roughly what it means, and for that reason I personally rather like it. Maybe they were writing for a future audience of non algebraic geometers.

Best

Ben

9 December, 2009 at 11:31 am

ChaosHi i want to ask a question but maybe it is absurd:)

in any finite group can we calculate the number of elements which commute each other of course i mean different pair of elements i.e.

ab=ba ,where a is not equal to b

9 December, 2009 at 11:42 am

Chaosin fact i should change my question: of all finite groups with n elements,

suppose we have calculated commuting elements as above question,is there a maximum number of these elements?that is in all these groups,does one of them have a maximum number with the property that distinct elements commute each other?

10 December, 2009 at 1:35 am

Chaosgroups mentioned above are of course not abelian

10 December, 2009 at 8:01 pm

bengreenDear Chaos,

I believe that in a non-abelian group at most 5/8 of the pairs of elements can commute. This is a fun exercise in undergraduate group theory.

After that there is a jump to the next smallest possible proportion, and then a discrete series which accumulates somewhere; maybe 1/2, though I forget.

There is a fun article on this in an old edition (circa 1970) of “Eureka”, the magazine of the Cambridge Student maths society. As I’m in Princeton right now, I can’t supply the reference – maybe someone else can?

Ben

11 December, 2009 at 12:41 am

Thomas SauvagetThis maximum of 5/8 is attained for both the quaternion group and dihedral group , two groups of order 8.

The general issue of evaluating the probability that two elements of a nonabelian finite group commute is discussed in great detail in a 1979 paper in

Pacific J. Math.by Rusin which is freely available here. (Unfortunately, I couldn’t find a reference online for the “Eureka” magazine you mentionned.)It appears that there’s indeed an infinite series starting at 5/8 and accumulating at 1/2. The paper mentions several open problems regarding the possible density of in intervals [a,b] with , which seem still open (at least a quick glance at google scholar suggests so).

11 December, 2009 at 10:36 am

AnonymousThomas

The article is by Nigel Boston and it is in volume 43 of Eureka, published in Cambridge in 1983. The title is “nearly abelian groups”. It may well be an exposition of the paper of Rusin you mention above.

Ben

12 December, 2009 at 7:19 am

Laci PyberSome time ago in joint work with Endre Szabo´ we obtained a version of the “escape from subvarieties” inequality discussed above for finite subsets A of algebraic groups G. Our result holds under the condition that the symmetric set A generates G(F_q), G(F_q) does not normalise any closed subgroup H < G with 0 < dim(H) < dim(G) and the centraliser of G(F_q) in G is finite.

For more details see

http://www.renyi.hu/~endre/growth.pdf

26 December, 2009 at 1:39 am

ChaosThanks for your helps dear professor green and thomas sauvaget:) i’m surprising now because you answered my question one day later but i looked at this page in 11.12.2009 and i couldnt see anything about my question..maybe it is concerned with density of this site..anyway again and again thanks…

29 December, 2009 at 8:22 pm

John Baez“in some statistical set” should probably be “in some statistical sense”.

[Corrected, thanks – T.]27 January, 2010 at 11:09 am

Linear approximate groups « What’s new[…] The expectation is that -approximate groups are -controlled by “structured” objects, such as actual groups and progressions, though the precise formulation of this has not yet been finalised. (We say that one finite set -controls another if is at most times larger than in cardinality, and can be covered by at most left translates or right translates of .) The task of stating and proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog posts. […]

12 May, 2010 at 1:31 pm

Approximate subgroups of linear subgroups « What’s new[…] groups can concentrate in a (bounded complexity) subvariety; this is discussed at the end of this blog post. Possibly related posts: (automatically generated)Review: Predicting Conversion to […]

15 January, 2011 at 8:15 am

A note on approximate subgroups of GL_n(C) and uniformly nonamenable groups « What’s new[…] of a “noncommutative Freiman” type theorem in linear groups . As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the […]

23 January, 2011 at 7:13 am

The Peter-Weyl theorem, and non-abelian Fourier analysis on compact groups « What’s new[…] on this blog), and in a more recent paper of Hrushovski on approximate groups (also discussed previously). It is also analogous in many ways to the more well-known Furstenberg correspondence principle […]