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 Green
Terry,
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 Dyer
Would 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 Tao
That 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 rat
Thank 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
jozsef
I 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
andrescaicedo
Hi Jozsef,
Do you have any references on these combinatorial corollaries? I would be very interested.
19 October, 2009 at 7:24 pm
jozsef
Hi 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.
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
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
http://www.cs.elte.hu/~elekes/
19 October, 2009 at 10:10 pm
andrescaicedo
This is very interesting! Thanks.
18 October, 2009 at 10:09 pm
Thomas Scanlon
We 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 Pillay
We 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 Tao
Well, 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 statement of 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 all aspects 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 Cantwell
Here 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 Usvyatsov
Actually, 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 Usvyatsov
I 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 Henson
In 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 Tao
It 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 Pillay
Here 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 Tao
Thanks 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 Usvyatsov
I 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 Tao
I’m forwarding (with permission) some earlier correspondence I had from Hrushovski about the intuition behind several key concepts in the paper, namely indiscernibles, the forking ideal, and invariant measures, as this may be of interest to various readers.
—
Indiscernibles are 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 to all definable 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 ideal over 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
Anonymous
in the second paragraph ”….since groups themselves have a doubling constant ….” is it G or X?