Reading seminar 6: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

This is the last reading seminar of this quarter for the Hrushovski paper. Anush Tserunyan continued working through her notes on stable theories. We introduced the key notion of non-forking extensions (in the context of stable theories, at least) of types when constants are added; these are extensions which are “as generic as possible” with respect to the constants being added. The existence of non-forking extensions can be used for instance to generate Morley sequences – sequences of indiscernibles which are “in general position” in some sense.

Reading seminar 5: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

After a one-week hiatus, we are resuming our reading seminar of the Hrushovski paper. This week, we are taking a break from the paper proper, and are instead focusing on the subject of stable theories (or more precisely, -stable theories), which form an important component of the general model-theoretic machinery that the Hrushovski paper uses. (Actually, Hrushovski’s paper needs to work with more general theories than the stable ones, but apparently many of the tools used to study stable theories will generalise to the theories studied in this paper.)

Roughly speaking, stable theories are those in which there are “few” definable sets; a classic example is the theory of algebraically closed fields (of characteristic zero, say), in which the only definable sets are boolean combinations of algebraic varieties. Because of this paucity of definable sets, it becomes possible to define the notion of the Morley rank of a definable set (analogous to the dimension of an algebraic set), together with the more refined notion of Morley degree of such sets (analogous to the number of top-dimensional irreducible components of an algebraic set). Stable theories can also be characterised by their inability to order infinite collections of elements in a definable fashion.

The material here was presented by Anush Tserunyan; her notes on the subject can be found here. Let me also repeat the previous list of resources on this paper (updated slightly):

• Henry Towsner’s notes (which most of Notes 2-4 have been based on; updated to remove references to homogeneity, using only countable saturation);
• Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
• Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
• Anand Pillay’s sketch of a simplified proof of Theorem 1.1.

Nonstandard analogues of energy and density increment arguments

In the course of the ongoing logic reading seminar at UCLA, I learned about the property of countable saturation. A model of a language is countably saturated if, every countable sequence of formulae in (involving countably many constants in ) which is finitely satisfiable in (i.e. any finite collection in the sequence has a solution in ), is automatically satisfiable in (i.e. there is a solution to all simultaneously). Equivalently, a model is countably saturated if the topology generated by the definable sets is countably compact.

Update, Nov 19: I have learned that the above terminology is not quite accurate; countable saturation allows for an uncountable sequence of formulae, as long as the constants used remain finite. So, the discussion here involves a weaker property than countable saturation, which I do not know the official term for. If one chooses a special type of ultrafilter, namely a “countably incomplete” ultrafilter, one can recover the full strength of countable saturation, though it is not needed for the remarks here. Most models are not countably saturated. Consider for instance the standard natural numbers as a model for arithmetic. Then the sequence of formulae “” for is finitely satisfiable in , but not satisfiable.

However, if one takes a model of and passes to an ultrapower , whose elements consist of sequences in , modulo equivalence with respect to some fixed non-principal ultrafilter , then it turns out that such models are automatically countably compact. Indeed, if are finitely satisfiable in , then they are also finitely satisfiable in (either by inspection, or by appeal to Los’s theorem and/or the transfer principle in non-standard analysis), so for each there exists which satisfies . Letting be the ultralimit of the , we see that satisfies all of the at once.

In particular, non-standard models of mathematics, such as the non-standard model of the natural numbers, are automatically countably saturated.

This has some cute consequences. For instance, suppose one has a non-standard metric space (an ultralimit of standard metric spaces), and suppose one has a standard sequence of elements of which are standard-Cauchy, in the sense that for any standard one has for all sufficiently large . Then there exists a non-standard element such that standard-converges to in the sense that for every standard one has for all sufficiently large . Indeed, from the standard-Cauchy hypothesis, one can find a standard for each standard that goes to zero (in the standard sense), such that the formulae “” are finitely satisfiable, and hence satisfiable by countable saturation. Thus we see that non-standard metric spaces are automatically “standardly complete” in some sense.

This leads to a non-standard structure theorem for Hilbert spaces, analogous to the orthogonal decomposition in Hilbert spaces:

Theorem 1 (Non-standard structure theorem for Hilbert spaces) Let be a non-standard Hilbert space, let be a bounded (external) subset of , and let . Then there exists a decomposition , where is “almost standard-generated by ” in the sense that for every standard , there exists a standard finite linear combination of elements of which is within of , and is “standard-orthogonal to ” in the sense that for all .

Proof: Let be the infimum of all the (standard) distances from to a standard linear combination of elements of , then for every standard one can find a standard linear combination of elements of which lie within of . From the parallelogram law we see that is standard-Cauchy, and thus standard-converges to some limit , which is then almost standard-generated by by construction. An application of Pythagoras then shows that is standard-orthogonal to every element of .

This is the non-standard analogue of a combinatorial structure theorem for Hilbert spaces (see e.g. Theorem 2.6 of my FOCS paper). There is an analogous non-standard structure theorem for -algebras (the counterpart of Theorem 3.6 from that paper) which I will not discuss here, but I will give just one sample corollary:

Theorem 2 (Non-standard arithmetic regularity lemma) Let be a non-standardly finite abelian group, and let be a function. Then one can split , where is standard-uniform in the sense that all Fourier coefficients are (uniformly) , and is standard-almost periodic in the sense that for every standard , one can approximate to error in norm by a standard linear combination of characters (which is also bounded).

This can be used for instance to give a non-standard proof of Roth’s theorem (which is not much different from the “finitary ergodic” proof of Roth’s theorem, given for instance in Section 10.5 of my book with Van Vu). There is also a non-standard version of the Szemerédi regularity lemma which can be used, among other things, to prove the hypergraph removal lemma (the proof then becomes rather close to the infinitary proof of this lemma in this paper of mine). More generally, the above structure theorem can be used as a substitute for various “energy increment arguments” in the combinatorial literature, though it does not seem that there is a significant saving in complexity in doing so unless one is performing quite a large number of these arguments.

One can also cast density increment arguments in a nonstandard framework. Here is a typical example. Call a non-standard subset of a non-standard finite set dense if one has for some standard .

Theorem 3 Suppose Szemerédi’s theorem (every set of integers of positive upper density contains an arithmetic progression of length ) fails for some . Then there exists an unbounded non-standard integer , a dense subset of with no progressions of length , and with the additional property that

for any subprogression of of unbounded size (thus there is no sizeable density increment on any large progression).

Proof: Let be a (standard) set of positive upper density which contains no progression of length . Let be the asymptotic maximal density of inside a long progression, thus . For any , one can then find a standard integer and a standard subset of of density at least such that can be embedded (after a linear transformation) inside , so in particular has no progressions of length . Applying the saturation property, one can then find an unbounded and a set of of density at least for every standard (i.e. of density at least ) with no progressions of length . By construction, we also see that for any subprogression of of unbounded size, hs density at most for any standard , thus has density at most , and the claim follows.

This can be used as the starting point for any density-increment based proof of Szemerédi’s theorem for a fixed , e.g. Roth’s proof for , Gowers’ proof for arbitrary , or Szemerédi’s proof for arbitrary . (It is likely that Szemerédi’s proof, in particular, simplifies a little bit when translated to the non-standard setting, though the savings are likely to be modest.)

I’m also hoping that the recent results of Hrushovski on the noncommutative Freiman problem require only countable saturation, as this makes it more likely that they can be translated to a non-standard setting and thence to a purely finitary framework.

An elementary non-commutative Freiman theorem

Let be a finite subset of a non-commutative group . As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those which obey small doubling conditions such as or . A full classification here has still not been established. However, I wanted to record here an elementary argument (based on Exercise 2.6.5 of my book with Van Vu, which in turn is based on this paper of Izabella Laba) that handles the case when is very close to :

Proposition 1 If , then and are both finite groups, which are conjugate to each other. In particular, is contained in the right-coset (or left-coset) of a group of order less than .

Remark 1 The constant is completely sharp; consider the case when where is the identity and is an element of order larger than . This is a small example, but one can make it as large as one pleases by taking the direct product of and with any finite group. In the converse direction, we see that whenever is contained in the right-coset (resp. left-coset ) of a group of order less than , then (resp. ) is necessarily equal to all of , by the inclusion-exclusion principle (see the proof below for a related argument).

Proof: We begin by showing that is a group. As is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let . Then we can write and for . If were equal to , then and we would be done. Of course, there is no reason why should equal ; but we can use the hypothesis to boost this as follows. Observe that and both have cardinality and lie inside , which has cardinality strictly less than . By the inclusion-exclusion principle, this forces to have cardinality greater than . In other words, there exist more than pairs such that , which implies that . Thus there are more than elements such that for some (since is uniquely determined by ); similarly, there exists more than elements such that for some . Again by inclusion-exclusion, we can thus find in for which one has simultaneous representations and , and so , and the claim follows.

In the course of the above argument we showed that every element of the group has more than representations of the form for . But there are only pairs available, and thus .

Now let be any element of . Since , we have , and so . Conversely, every element of has exactly representations of the form where . Since occupies more than half of , we thus see from the inclusion-exclusion principle, there is thus at least one representation for which both lie in . In other words, , and the claim follows.

To relate this to the classical doubling constants , we first make an easy observation:

Lemma 2 If , then .

Again, this is sharp; consider equal to where generate a free group.

Proof: Suppose that is an element of for some . Then the sets and have cardinality and lie in , so by the inclusion-exclusion principle, the two sets intersect. Thus there exist such that , thus . This shows that is contained in . The converse inclusion is proven similarly.

Proposition 3 If , then is a finite group of order , and for some in the normaliser of .

The factor is sharp, by the same example used to show sharpness of Proposition 1. However, there seems to be some room for further improvement if one weakens the conclusion a bit; see below the fold.

Proof: Let (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of has more than representations of the form for . By the argument used to prove Proposition 1, this shows that is a group; also, since there are only pairs , we also see that .

Pick any ; then , and so . Because every element of has representations of the form with , , and occupies more than half of and of , we conclude that each element of lies in , and so and .

The intersection of the groups and contains , which is more than half the size of , and so we must have , i.e. normalises , and the proposition follows.

Because the arguments here are so elementary, they extend easily to the infinitary setting in which is now an infinite set, but has finite measure with respect to some translation-invariant Kiesler measure . We omit the details. (I am hoping that this observation may help simplify some of the theory in that setting.)

Reading seminar 4: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

This week, Henry Towsner concluded his portion of reading seminar of the Hrushovski paper, by discussing (a weaker, simplified version of) main model-theoretic theorem (Theorem 3.4 of Hrushovski), and described how this theorem implied the combinatorial application in Corollary 1.2 of Hrushovski. The presentation here differs slightly from that in Hrushovski’s paper, for instance by avoiding mention of the more general notions of S1 ideals and forking.

Here is a collection of resources so far on the Hrushovski paper:

• Henry Towsner’s notes (which most of Notes 2-4 have been based on);
• Alex Usvyatsov’s notes on the derivation of Corollary 1.2 (broadly parallel to the notes here);
• Lou van den Dries’ notes (covering most of what we have done so far, and also material on stable theories); and
• Anand Pillay’s sketch of a simplified proof of Theorem 1.1.

Reading seminar 3: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

This week, Henry Towsner continued some model-theoretic preliminaries for the reading seminar of the Hrushovski paper, particularly regarding the behaviour of wide types, leading up to the main model-theoretic theorem (Theorem 3.4 of Hrushovski) which in turn implies the various combinatorial applications (such as Corollary 1.2 of Hrushovski). Henry’s notes can be found here.

A key theme here is the phenomenon that any pair of large sets contained inside a definable set of finite measure (such as ) must intersect if they are sufficiently “generic”; the notion of a wide type is designed, in part, to capture this notion of genericity.

Reading seminar 2: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

At UCLA we just concluded our third seminar in our reading of “Stable group theory and approximate subgroups” by Ehud Hrushovski. In this seminar, Isaac Goldbring made some more general remarks about universal saturated models (extending the discussion from the previous seminar), and then Henry Towsner gave some preliminaries on Kiesler measures, in preparation for connecting the main model-theoretic theorem (Theorem 3.4 of Hrushovski) to one of the combinatorial applications (Corollary 1.2 of Hrushovski).

As with the previous post, commentary on any topic related to Hrushovski’s paper is welcome, even if it is not directly related to what is under discussion by the UCLA group. Also, we have a number of questions below which perhaps some of the readers here may be able to help answer.

Note: the notes here are quite rough; corrections are very welcome. Henry’s notes on his part of the seminar can be found here.

(Thanks to Issac Goldbring for comments.)

Reading seminar: “Stable group theory and approximate subgroups”, by Ehud Hrushovski

One of my favorite open problems, which I have blogged about in the past, is that of establishing (or even correctly formulating) a non-commutative analogue of Freiman’s theorem. Roughly speaking, the question is this: given a finite set in a non-commutative group which is of small doubling in the sense that the product set is not much larger than (e.g. for some ), what does this say about the structure of ? (For various technical reasons one may wish to replace small doubling by, say, small tripling (i.e. ), and one may also wish to assume that contains the identity and is symmetric, , but these are relatively minor details.)

Sets of small doubling (or tripling), etc. can be thought of as “approximate groups”, since groups themselves have a doubling constant equal to one. Another obvious example of an approximate group is that of an arithmetic progression in an additive group, and more generally of a ball (in the word metric) in a nilpotent group of bounded rank and step. It is tentatively conjectured that in fact all examples can somehow be “generated” out of these basic examples, although it is not fully clear at present what “generated” should mean.

A weaker conjecture along the same lines is that if is a set of small doubling, then there should be some sort of “pseudo-metric” on which is left-invariant, and for which is controlled (in some suitable sense) by the unit ball in this metric. (For instance, if was a subgroup of , one would take the metric which identified all the left cosets of to a point, but was otherwise a discrete metric; if were a ball in a nilpotent group, one would use some rescaled version of the word metric, and so forth.) Actually for technical reasons one would like to work with a slightly weaker notion than a pseudo-metric, namely a Bourgain system, but let us again ignore this technicality here.

Recently, using some powerful tools from model theory combined with the theory of topological groups, Ehud Hrushovski has apparently achieved some breakthroughs on this problem, obtaining new structural control on sets of small doubling in arbitrary groups that was not previously accessible to the known combinatorial methods. The precise results are technical to state, but here are informal versions of two typical theorems. The first applies to sets of small tripling in an arbitrary group:

Theorem 1 (Rough version of Hrushovski Theorem 1.1) Let be a set of small tripling, then one can find a long sequence of nested symmetric sets , all of size comparable to and contained in , which are somewhat closed under multiplication in the sense that for all , and which are fairly well closed under commutation in the sense that . (There are also some additional statements to the effect that the efficiently cover each other, and also cover , but I will omit those here.)

This nested sequence is somewhat analogous to a Bourgain system, though it is not quite the same notion.

If one assumes that is “perfect” in a certain sense, which roughly means that there is no non-trivial abelian quotient, then one can do significantly better:

Theorem 2 (Rough version of Hrushovski Corollary 1.2) Let be a set of small tripling, let , and suppose that for almost all -tuples (where ), the conjugacy classes generate most of in the sense that . Then a large part of is contained in a subgroup of size comparable to .

Note that if one quotiented out by the commutator , then all of the conjugacy classes would collapse to points. So the hypothesis here is basically a strong quantitative assertion to the effect that the commutator is extremely large, and rapidly fills out most of itself.

Here at UCLA, a group of logicians and I (consisting of Matthias Aschenbrenner, Isaac Goldbring, Greg Hjorth, Henry Towsner, Anush Tserunyan, and possibly others) have just started a weekly reading seminar to come to grips with the various combinatorial, logical, and group-theoretic notions in Hrushovski’s paper, of which we only have a partial understanding at present. The seminar is a physical one, rather than an online one, but I am going to try to put some notes on the seminar on this blog as it progresses, as I know that there are a couple of other mathematicians who are interested in these developments.

So far there have been two meetings of the seminar. In the first, I surveyed the state of knowledge of the noncommutative Freiman theorem, covering broadly the material in my previous blog post. In the second meeting, Isaac reviewed some key notions of model theory used in Hrushovski’s paper, in particular the notions of definability and type, which I will review below. It is not yet clear how these are going to be connected with the combinatorial side of things, but this is something which we will hopefully develop in future seminars. The near-term objective is to understand the statement of the main theorem on the model-theoretic side (Theorem 3.4 of Hrushovski), and then understand some of its easier combinatorial consequences, before going back and trying to understand the proof of that theorem.

[Update, Oct 19: Given the level of interest in this paper, readers are encouraged to discuss any aspect of that paper in the comments below, even if they are not currently being covered by the UCLA seminar.]