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.]

** — 1. Definability — **

Model theory studies *models* (or structures) of languages. For our purposes, a language consists of the basic symbols in logic (the boolean connectives, parentheses, the quantifiers, variables, and the equals sign) plus some additional relation and function symbols. For instance, the language of groups could be denoted as , since one needs the identity (which can be thought of as a -ary function, i.e. a constant symbol), the multiplication (a binary function), and the inverse function . The language of rings could be denoted as , the language of ordered rings could be denoted as , and so forth. To avoid cluttering the discussion with irrelevant formalities, we will use all the usual conventions of mathematical notation (e.g. using as shorthand for , using as short-hand for , etc.). In the applications to additive combinatorics, the language will either be the language of groups, or an extension thereof.

A *structure* for a language consists of some domain (which, by abuse of notation, we will also call ), together with an interpretation of the various relations and functions of as relations or functions on . For instance, every group is naturally a structure for the language of groups. (Indeed, one does not need to obey the group axioms in order to be a structure for this language; as long as contains a distinguished element , some binary operation , and some unary operation , it is a structure.)

Given a sentence (i.e. a formula with no free variables) in , a structure can interpret that sentence and give it a truth value in the usual manner; if it gives a true value, we write . For instance, in the language of groups, if is the associativity sentence , then will hold if is a group, but need not hold for other structures in the language of groups.

Given a formula with free variables in , cannot interpret that formula directly, but given any values for the free variables, can assign a truth value to the substituted formula , and we write if that sentence is true. The set

is then referred to as a *-definable* subset of , defined by the formula . For instance, in a group , the set of elements of order two is a -definable set, defined using the formula

Most subsets in a structure are not -definable. However one can increase the ability to define sets by adding constants. Given a set , we can *extend* the language to a new language by adding a constant symbol for each element (actually we shall usually abuse notation and write for ). The structure similarly extends to a structure for which has the same domain as , and interprets all existing symbols in the same way, but also interprets the constant symbol as . A subset of is said to be *-definable* if it is -definable in , i.e. there is a formula which can use constants from to define the set.

For instance, in the language of rings, and in the structure given by the real line (which is, of course, a ring), the singleton set is not -definable, but it is -definable, since one can use the formula “” to define it.

Even when one uses the entire domain as a set of constants, one cannot always define every single set. For instance, in the empty language (which has the basic notion of equality, but no other relations or symbols), and in an infinite model , the only -definable subsets of turn out to be the finite and cofinite subsets of ; one cannot for instance define the even integers from the integers from a single first-order formula in the empty language, even if one is allowed to use all the integers as constant symbols. (Of course, one can do so once one has the addition or multiplication symbol available.)

Another example: in the language of fields (or rings), if is an algebraically closed field, then the -definable sets are the boolean combinations of algebraic sets; this fact is closely related to Hilbert’s nullstellensatz (and can be proven by quantifier elimination). Similarly, in the language of ordered rings, if is the real line, then the -definable sets are the semi-algebraic sets, which is essentially a famous result of Tarski and Seidenberg. In particular, the one-dimensional -definable sets are finite boolean combinations of half-lines, a property known as o-minimality.

Sometimes it is necessary to leave the original structure for a larger structure that is an elementary extension of . What this means is that

- is an extension of (thus the domain of includes the domain of , and the interpretations of the relations and functions on and on agree on ); and
- Every sentence (allowing constant symbols from ) that is true in , is also true on . (The converse implication is then also true by taking negations.)

For instance, in the language of rings, the non-standard reals are an elementary extension of the standard reals. On the other hand, the reals are not an elementary extension of the rationals, because there are formulae such as which make sense and are true in the rationals, but not the reals.

Now for an important definition. Let be an elementary extension of , let be a subset of , and let be a tuple in . The *type* of over is the set of all formulae (using as constant symbols) which are satisfied by :

Informally, the type captures everything one can say in first-order logic about if one is only allowed to use the constant symbols .

A *complete type* over is a collection of formulae in which is the type of some tuple in some elementary extension of . A *partial type* over is a subset of a complete type over , i.e. a collection of formulae involving which is satisfied by some in some elementary extension. In that case we say that *realises* the partial type , and write .

For instance, each real number can be identified with a complete type over the rationals (using all the rationals as constants) in the language of totally ordered sets, by the Dedekind cut construction. However, there are additional complete types as well, such as those arising from infinitesimals.

By the completeness theorem, a partial type is nothing more than a set of formulae of a given arity involving which is logically consistent with all the sentences in that are true in ; and a complete type is a partial type which is maximal (given any formula , either or its negation lie in the complete type). One can view complete types as being ultrafilters on the language (modulo equivalence by sentences that are true in , i.e. modulo the theory of ).

For instance, in the language of ordered sets, and with being the natural numbers, the collection of formulae in cannot be satisfied in the natural numbers, but can be satisfied in elementary extensions of the natural numbers, e.g. the ordered set or the non-standard natural numbers, and so is a partial type over .

Thus we see that in order to realise a partial type, one may have to move to a larger structure, which can be inconvenient. There is a related inconvenience involving tuples in an elementary extension which are *elementarily indistinguishable* over if , i.e. there is no formula involving that can distinguish from . One obvious way in which indistinguishability can occur is if there is an *automorphism* on that fixes (where an automorphism is defined as a bijection which preserves all the structures in the language) and maps to , much as two elements of a field extension which are Galois conjugate to each other cannot be distinguished using polynomials in the base field. However, it is possible to have two elementary indistinguishable tuples in a structure for which no automorphism of exists that maps to .

Here is a concrete example: we use the language of order, let be the rationals, and let be the set consisting of . Then and have the same type over (i.e. are elementarily indistinguishable), but there is no -fixing automorphism that maps to because is the supremum of a subset of , and is not. On the other hand, if one extends the rationals to contain non-standard rationals, then an automorphism becmomes possible.

More generally, whenever and are elementarily indistinguishable, one can always find an elementary extension of (and hence of ) and an automorphism of for which maps to . (This appears to be some sort of swindle type argument, but I do not know the details.)

It is convenient to pre-empt all these issues of passing to an elementary extension by working with a *universal extension* of with the following two properties:

- (i) (Saturation) If has strictly smaller cardinality than , then every partial type over is realisable in (no need to pass to a further extension); and
- (ii) (Homogeneity) If is as above and are elementarily indistinguishable over , then there is an automorphism of that maps to (so again, no need to pass to a further extension).

I do not know fully how to obtain a saturated model (though it is standard in model theory textbooks); it does require some set-theoretic assumptions, such as the generalised continuum hypothesis, or the existence of a strongly inaccessible cardinal, though in practice one does not need such an absurdly huge model because one usually only needs saturation for sets of much smaller cardinality (e.g. countable). For instance, given any uncountable ordinal , one can obtain saturation for all of cardinality or less with a structure of cardinality . It seems that for the combinatorial applications we will in fact only need and to be countable, though we have not yet checked this fully.

It turns out that (i) formally implies (ii). Here is a sketch of a proof: to build an automorphism that fixes and maps to , we will greedily build up partial automorphisms that fix and map to , where is a set of strictly smaller cardinality than . By “partial automorphism”, we mean that if , then has the same type over (or over any other subset of ) as .

Clearly one can build a partial automorphism on the set . By transfinite induction (and by well-ordering using the least ordinal with the cardinality of ), it then suffices to show that whenever one has a partial automorphism , and an element outside of , one can extend the automorphism to an automorphism . But if one looks at the set of constraints that needs to satisfy (roughly, that any formula that is true for and , must also be true for and ), we see that any finite collection of these constraints is satisfiable (because it can be encoded as an existential sentence involving finitely many , which by the partial automorphism property of is equivalent to the corresponding (true) existential sentence involving ), and so by (i) it is realisable in , and the claim follows.

Property (ii) has a nice consequence: a -definable subset of is -definable if and only if it is invariant under all automorphisms of that fix .

Let’s now work in this universal model, with some set of constants. Every partial type (of some arity ) over defines a subset of ; this is an intersection of -definable sets (one for each formula in ), and is thus called a -definable set over . For instance, in the language of groups, if is a (possibly infinite) subset of a group , the *centraliser* is a -definable set over , but is not -definable in general. One can view -definable sets as analogous to a base of clopen sets in topology, whereas -definable sets are analogous to closed sets. Dually, we have the notion of a -definable set over , which is the complement of a -definable set over , or equivalently the union of -definable sets; this is the analogue of an open set. (For instance, is automatically -definable over .)

Not every interesting object involving is -definable or -definable; for instance, in the language of groups, if is a subgroup of , the *normaliser* is neither -definable or -definable in general (there are too many quantifiers hidden inside the statement !). Things might improve if one adds in a predicate for membership in , though I was a little unclear on this point.

(Thanks to Matthias Aschenbrenner, Juan Diego Caycedo, and Isaac Goldbring for comments and suggestions.)

## 23 comments

Comments feed for this article

16 October, 2009 at 1:37 am

Ben GreenTerry,

I’ll be following this with interest; I find this paper of Hrushovskii very intruiging indeed.

Best

Ben

16 October, 2009 at 6:30 am

Jason DyerWould you mind if we had an online component of sorts using this thread? If there’s a question posed here nobody knows the answer to could it be relayed to the reading group?

16 October, 2009 at 7:38 am

Terence TaoThat would be fine! This is somewhat experimental (as are so many other online mathematical activities); it will be interesting to see how the online and offline groups interact.

16 October, 2009 at 7:02 pm

joe the ratThank you for this post. This is amazing that this problem seems to be located between group theory and model theory.

17 October, 2009 at 2:41 pm

jozsefI tried to learn some model theory a few years ago when it turned out that the Group Configuration Theorem of Hrushovski has some amazing combinatorial corollaries. I did find an informal introduction to model theory by Ludomir Newelski which might complement Terry’s gentle introduction; “An essay on model theory” Central European Journal of Mathematics, Volume 1, Number 3 / September, 2003, pages 398-410.

While I’m still fighting with this classical result of Hrushovski, I’m looking forward to see some explanations of his new theorem by non-model-theorists.

19 October, 2009 at 10:20 am

andrescaicedoHi Jozsef,

Do you have any references on these combinatorial corollaries? I would be very interested.

19 October, 2009 at 7:24 pm

jozsefHi Andres,

Well, I can give you some indirect references only. I learned about the connection between the Group Configuration Theorem (GCT) and some combinatorial problems from my late friend and teacher Gyuri Elekes.

In 2001 Endre Szabo proved a beautiful theorem in algebraic geometry which is (partly) a corollary of GCT. (Endre Szabo wasn’t aware of this connection, but the result remained unpublished) Loosely speaking it says that if a low degree varieties contains at least points of an n x n x n Cartesian product then it is a cylinder or it is a pullback from the graph of the multiplication function of a group. My favorite application of this result is the following (due to Elekes and Szabo): the number of distinct distances between three non-collinear points and n point in the plane is at least (Much more than ) The only pointer which I can give you for these results is Elekes’ survey paper “Sums versus products in Number Theory, Algebra and Erdös Geometry” which is downloadable from the website

http://www.cs.elte.hu/~elekes/

19 October, 2009 at 10:10 pm

andrescaicedoThis is very interesting! Thanks.

18 October, 2009 at 10:09 pm

Thomas ScanlonWe have been reading (very slowly — we are at Theorem 3.4 now) Udi’s paper in our model theory seminar at Berkeley. What kind of on-line component to your seminar do you have in mind? Would it be more than threaded comments on this topic? It could be useful for us to post the questions and solutions from our respective seminars here or at whatever forum or wiki you establish for the on-line seminar.

19 October, 2009 at 5:00 am

Anand PillayWe at Leeds have also been looking at the paper since early September.

I first went through the proof of Theorem 3.4 , essentially stating the required background as needed. Dugald Macpherson has since then been looking at other sections, including 2 and 5. I will begin on section 4 this week.

The whole thing is very nice but there could be some clarifications here and there. We will first communicate any suggestions to Udi. But we would be otherwise happy to share insights and/or questions (although personally I may have trouble with any fancy online technology).

For motivation concerning Thm. 3.4 or treatment of special cases, one might want to look at section 7 of Pseudo-finite fields and related structures (Hrushovski, in Model Theory and Applications, quaderni di matematica, vol. 11), and section 4 of my Definability and definable groups in simple theories, JSL 1998.

19 October, 2009 at 9:03 am

Terence TaoWell, as with most of my forays into online mathematics, the planning for this online seminar is being made up as it goes along. It does seem that there is broader interest in this topic than I had previously realised, though.

It seems that UCLA is lagging a bit behind the Berkeley and Leeds seminars (our immediate goal is just to understand the

statementof Theorem 3.4, and how it gives some of the easier combinatorial applications), but it does seem to make a lot of sense to have a common location to discuss things.I think the simplest thing to do is to continue using this blog for now, but to encourage discussion in the comments of

allaspects of the Hrushovski paper (not just whatever is currently being looked at by the UCLA group). Hopefully this will help us to catch up to wherever the other groups are at, and I doubt the volume of postings will be so huge as to cause chaos. (If this does turn out to be the case, I may try to set up some fancier forum to organise things, but this seems to be a bit premature at this stage. The blog does have the advantages of having an established readership (in particular, Ehud himself has commented on this blog before), and the ability to comment without needing registration or any technical expertise.)Also, if anyone would like to start their own thread on this topic (e.g. if someone is willing to write up lecture notes from the Berkeley or Leeds seminar) then they can contact me and I can put the text on the blog here as a “guest blog”. (If I get a regular flow of submissions of this type, I may look to finding a more organised way to set this up, e.g. using the polymath resources, but I think that can wait until the level of activity becomes sufficiently high.)

19 October, 2009 at 11:56 am

Kristal CantwellHere is a set of lecture notes on model theory:

Click to access lecturenotes_modeltheory.pdf

Here is an article about saturated models:

http://en.wikipedia.org/wiki/Saturated_model

From the above the statement that every model has a saturated elementary extension implies the generalized continuum hypothesis.

20 October, 2009 at 4:13 am

Alex UsvyatsovActually, the last statement is not quite true.

In any case, although there is a slight set theoretic issue with saturated models, it can be easily avoided: in model theory, one only needs to work with a model U which is saturated and homogeneous with respect to some big cardinal lamda (so the properties “saturation” and “homogeneity” mentioned in Terry’s post hold over sets of cardinality less than lamda), and it is not so important that the cardinality of U is exactly lamda. Such models provably exist in ZFC.

There are other ways to deal with existence of saturated models, for example “proof by absoluteness”: most properties we are interested in in model theory are set-theoretically absolute (their truth does not depend on the model of set theory one works with), so it is harmless to assume that GCH holds for some big cardinal lamda.

Another small general remark that makes a (mild) connection between this blog and a previous online course of Terry’s on ergodic theory: types over a set A are simply ultra-filters on the Boolean algebra of A-definable sets (formulas). One can also look at a more general concept of a (finitely additive) probability measure on this space (a Keisler measure). The space of types is a compact totally disconnected topological space. Some of Keisler measures (in particular types) turn out (or can be assumed) to be definable, which means that they can be viewed as continuous functions from the type space to the reals. This allows the use of topological tools, which are often quite helpful.

Lastly a short response to Terry’s question about the power of the infinitary situation: it seems to be that some of it can be seen in Theorem 2.15, which is a variant of the so-called “Independence Theorem” (“3-Amalgamation Theorem” would be a better name), which roughly states that under certain conditions “free” (“large”) extensions of a type are compatible. This is a generalization of uniqueness of “free” (non-forking) extensions in stable theories, and has had many consequences in simple theories (generalizing results from stability). It also plays a crucial role in the proof of Theorem 3.4 in Udi’s paper, which is the central result on the model theoretic side.

22 October, 2009 at 4:34 am

Alex UsvyatsovI am sorry: it was pointed out to me that I have been reading an old version of Udi’s paper. In the most recent version, the Independence Theorem is Theorem 2.16.

Also, in my previous comment I forgot to mention that if you add a predicate for membership in a subgroup A (so if A is definable), then N(A) is definable as well: you need to say that for all x in A there is x’ in A such that yx=x’y (and vice versa).

The model theory group in Lisbon is also (slowly) reading Udi’s paper. We will be very happy to participate in an online reading group (although at this point it is too early for us to be able to say or ask anything intelligent).

19 October, 2009 at 2:11 pm

Ward HensonIn Urbana we also have had a working seminar since early September around the topic of Hruskovski’s paper. We began with some background (especially Terence Tao’s paper “The sum-product phenomenon in arbitrary rings”) and for the last four weeks we have been diving into Hrushovski. It would doubtless be helpful and also interesting for the various groups working in parallel to share their understanding (and confusion).

19 October, 2009 at 3:05 pm

Terence TaoIt looks like there is indeed a significant economy of scale to be gained here by having a common online seminar for all the separate physical seminars out there. (I’ve long felt that a similar economy of scale should be present for undergraduate teaching, but didn’t realise that it would also work at the research level.) So, I would like to open the comments here to everyone who has a question or comment about the paper or some other related topic to discuss.

I’ll start the ball rolling with the following question. From what I can see of the paper so far, the proofs of the combinatorial statements in Hrushovski’s paper proceed by a “correspondence principle” or “compactness and contradiction” method, in which one assumes that the combinatorial statement fails, and extracts from this (via compactness) some infinitary limit structure which is supposed to ultimately lead to some sort of contradiction. Fair enough – I’ve seen many arguments of this sort before, such as in Gromov’s proof of his theorem on groups of polynomial growth, or Furstenberg’s proof of Szemeredi’s theorem. My question though is what is the secret ingredient in the infinitary world that makes this correspondence powerful, and which is then difficult to replicate in the finitary world? In the case of Gromov’s theorem, it is the Montgomery-Zippin-Yamabe theory of topological groups; in the case of Furstenberg’s proof, it is the various tools of measurable dynamics, such as the ergodic theorem, conditional expectation, the Gram-Schmidt process, etc.. In Hrushovski’s paper, there is use of the Montgomery-Zippin-Yamabe theory, but this comes only for some of the deeper applications; as far as I can tell the proof of Hrushovski Corollary 1.2 (for instance) does not use any Lie theory or topological group theory, and still is something which looks beyond the reach of current combinatorial methods, so something nontrivial must be happening at the infinitary level (beyond just compactness).

I guess we’ll understand this once we get a better grip on Theorem 3.4, which the UCLA team is going to tackle later this week, I think, but I would be interested to hear other people’s thoughts on the matter. (Examples of simpler versions of Theorem 3.4 which still have non-trivial finitary implications would also be very much appreciated; I will have a look at the papers Pillay mentions. The Quaderni paper does not seem to be available online, though.)

20 October, 2009 at 12:08 am

Anand PillayHere is a kind of response to Terence Tao’s question about the power of the model theoretic methods. As with the other examples he mentions (theory of topological groups, measurable dynamics,..) there is a powerful and nontrivial theory around, namely stability theory, or rather neo-stability theory. This is a specialised area of model theory, which many people in the subject may not be exposed to. Stability theory (developed originally by Shelah) includes notions of forking, stationarity, orthogonality,…and was originally developed just in the context of stable (first order) theories, for reasons I will not go into here.

In fact if you are interested in more than simply getting through the paper there would be no harm in taking a bit of time to talk about stable theories in the UCLA seminar.

Anyway, in the past 15 years or so there has been an extension of this technology outside the realm of stable theories , to e.g. “simple” theories, and NIP theories. There are new features, such as independence theorem in simple theories, and studying measures in place of types in NIP theories…I call this neo-stability theory. (Neo) Stable group theory is just (neo) stability theory in the presence of a definable group operation, which has special features like the theory of generic types, connected components, stabilizers, invariant measures,.. What Udi has done beautifully in say 3.4 is to isolate some local assumptions on a situation (and which are consequences of being an ultraproduct of finite sets or structures) and which allow arguments in the case of groups definable in SIMPLE theories to go through, with of course additional finessing. There is an additional level of generality of working with v-definable (ind-definable) groups rather than definable ones, but it doesn’t really present technical obstacles.

So my basic point is that there is a theory here, going considerably beyond compactness, which one is plugging into. One can of course ask further, what precise technical aspects or specific theorems, provide the power to encode finite combinatorics or even to say “meaningful” things at the infinitary level. I may say more about it later.

20 October, 2009 at 6:58 pm

Terence TaoThanks for your comments! I will definitely be interested in understanding more about stability theory as the seminar here progresses.

26 October, 2009 at 10:40 am

Alex UsvyatsovI have finally gathered my thoughts enough to say something concerning Terry’s question above. In other words, this is my current (quite limited) view of some of the “secret ingredients” of the “finite-infinite” correspondence in Udi’s paper.

It seems to me that there are, in fact, two “correspondences” going on. The first is the more usual one, roughly between families of finite sets that look like subgroups and “near-subgroups” in the ultra-product (Definition 3.6). Given a near-subgroup , Udi obtains in Theorem 3.4 the “stabilizer” subgroup. This “bounds” between two subgroups (one type-definable, another ind-definable) which are very “close” (the quotient is of bounded index). This already allows him to deduce certain consequences on the “finite” world, using the first “finite-infinite correspondence” (the end of section 3 – of course, quite a bit of model theory on the “infinite side” is used just in those proofs). As I mentioned before, some of the power here is hidden in the stabilizer theorem, one of the main ingredients of which is the Independence Theorem 2.16. The techniques, as Anand was saying, generalize those of stability, simplicity, etc., and some of the main tools seem to be local stability, forking, and definable measures.

The second correspondence is possibly even more intriguing, and it is that between definable (type-definable, ind-definable…) groups in the “infinite” world (in a monster model) and compact (or locally compact) topological groups. These connections have been studied quite a bit recently in the context of dependent groups, specifically in the o-minimal context (“Pillay’s Conjecture”). In order to establish this correspondence, one again uses the fact that the stabilizer obtained in Theorem 3.4 is of bounded index. Now the tools of locally compact topological groups become available. It seems that Udi uses kind of a “transfer” principle for certain type of statements between the “Lie” world and the “infinite” world of the monster model, which then can be transferred back to the “finite” world; but I am less clear on this part at the moment.

19 October, 2009 at 6:56 pm

Terence TaoI’m forwarding (with permission) some earlier correspondence I had from Hrushovski about the intuition behind several key concepts in the paper, namely

indiscernibles, theforking ideal, andinvariant measures, as this may be of interest to various readers.—

Indiscerniblesare usually just a systematic way of using Ramsey’s theorem. Given a sequence , any formula in variables (and no parameters) can be viewed as a coloring of -subsets of the sequence, with two colors, true and false. Conversely a “definable” coloring in colors can be coded by about formulas. Logical compactness means that one can apply Ramsey’s theorem toalldefinable colorings sequentially and then take a limit, obtaining a fully homogeneous set. This is what we call an indiscernible sequence. In practice one can usually rewrite proofs using indiscernibles in such a way that Ramsey’s theorem is applied for a specific definable coloring. (But not always; the Paris-Harrington theorem can be viewed as a counterexample.)The

forking idealover a set of parameters A: it is contained in the intersection of the measure-0 ideal over all automorphism-invariant measures (Lemma 2.9), in particular over all A-definable measures. It’s not too wrong to think of “forking over A” as “measure zero for any measure defined over A” (but the definition is more elementary, and not identical to this.)Invariant measures: very close to the usual intuition of a finite -additive measure, but only sets definable with parameters are measured; on the other hand, there is an additional condition, that the measure be invariant under automorphisms acting on the parameters. For example Lebesgue measure on the interval or more generally on , restricted to semi-algebraic subsets, admits a unique extension to the interval (or in any bigger real closed field. (For this is an easy excercise: infinitesimal intervals must have measure , since they can be approximated by intervals with rational endpoints.)22 October, 2009 at 5:52 pm

Reading seminar 2: “Stable group theory and approximate subgroups”‘, by Ehud Hrushovski « What’s new[…] 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 […]

29 October, 2009 at 5:54 pm

Reading seminar 3: “Stable group theory and approximate subgroups”, by Ehud Hrushovski « What’s new[…] extension of (i.e. one that obeys the saturation and homogeneity properties as discussed in Notes 1. Later on, will contain the language of groups, and then we will rename as to emphasise […]

9 November, 2009 at 8:43 am

Anonymousin the second paragraph ”….since groups themselves have a doubling constant ….” is it G or X?