Category Archive

You are currently browsing the category archive for the ‘Logic reading seminar’ category.

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

4 December, 2009 in Logic reading seminar, math.LO | Tags: | by | Leave a comment

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.

Read the rest of this entry »

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

20 November, 2009 in Logic reading seminar, math.LO | by | 11 comments

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, {\omega}-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):

Read the rest of this entry »

Nonstandard analogues of energy and density increment arguments

16 November, 2009 in Logic reading seminar, math.CO, math.LO | Tags: , | by | 2 comments

In the course of the ongoing logic reading seminar at UCLA, I learned about the property of countable saturation. A model {M} of a language {L} is countably saturated if, every countable sequence {P_1(x), P_2(x), \ldots} of formulae in {L} (involving countably many constants in {M}) which is finitely satisfiable in {M} (i.e. any finite collection {P_1(x),\ldots,P_n(x)} in the sequence has a solution {x} in {M}), is automatically satisfiable in {M} (i.e. there is a solution {x} to all {P_n(x)} 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 {{\Bbb N}} as a model for arithmetic. Then the sequence of formulae “{x > n}” for {n=1,2,3,\ldots} is finitely satisfiable in {{\Bbb N}}, but not satisfiable.

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

In particular, non-standard models of mathematics, such as the non-standard model {*{\Bbb N}} of the natural numbers, are automatically countably saturated.

This has some cute consequences. For instance, suppose one has a non-standard metric space {*X} (an ultralimit of standard metric spaces), and suppose one has a standard sequence {(x_n)_{n \in {\mathbb N}}} of elements of {*X} which are standard-Cauchy, in the sense that for any standard {\varepsilon > 0} one has {d( x_n, x_m ) < \varepsilon} for all sufficiently large {n,m}. Then there exists a non-standard element {x \in *X} such that {x_n} standard-converges to {x} in the sense that for every standard {\varepsilon > 0} one has {d(x_n, x) < \varepsilon} for all sufficiently large {n}. Indeed, from the standard-Cauchy hypothesis, one can find a standard {\varepsilon(n) > 0} for each standard {n} that goes to zero (in the standard sense), such that the formulae “{d(x_n,x) < \varepsilon(n)}” 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 {*H} be a non-standard Hilbert space, let {S} be a bounded (external) subset of {*H}, and let {x \in H}. Then there exists a decomposition {x = x_S + x_{S^\perp}}, where {x_S \in *H} is “almost standard-generated by {S}” in the sense that for every standard {\varepsilon > 0}, there exists a standard finite linear combination of elements of {S} which is within {\varepsilon} of {S}, and {x_{S^\perp} \in *H} is “standard-orthogonal to {S}” in the sense that {\langle x_{S^\perp}, s\rangle = o(1)} for all {s \in S}.

Proof: Let {d} be the infimum of all the (standard) distances from {x} to a standard linear combination of elements of {S}, then for every standard {n} one can find a standard linear combination {x_n} of elements of {S} which lie within {d+1/n} of {x}. From the parallelogram law we see that {x_n} is standard-Cauchy, and thus standard-converges to some limit {x_S \in *H}, which is then almost standard-generated by {S} by construction. An application of Pythagoras then shows that {x_{S^\perp} := x-x_S} is standard-orthogonal to every element of {S}. \Box

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 {\sigma}-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 {*G} be a non-standardly finite abelian group, and let {f: *G \rightarrow [0,1]} be a function. Then one can split {f = f_{U^\perp} + f_U}, where {f_U: *G \rightarrow [-1,1]} is standard-uniform in the sense that all Fourier coefficients are (uniformly) {o(1)}, and {f_{U^\perp}: *G \rightarrow [0,1]} is standard-almost periodic in the sense that for every standard {\varepsilon > 0}, one can approximate {f_{U^\perp}} to error {\varepsilon} in {L^1(*G)} 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 {X} of a non-standard finite set {Y} dense if one has {|X| \geq \varepsilon |Y|} for some standard {\varepsilon > 0}.

Theorem 3 Suppose Szemerédi’s theorem (every set of integers of positive upper density contains an arithmetic progression of length {k}) fails for some {k}. Then there exists an unbounded non-standard integer {N}, a dense subset {A} of {[N] := \{1,\ldots,N\}} with no progressions of length {k}, and with the additional property that

\displaystyle \frac{|A \cap P|}{|P|} \leq \frac{|A \cap [N]|}{N} + o(1)

for any subprogression {P} of {[N]} of unbounded size (thus there is no sizeable density increment on any large progression).

Proof: Let {B \subset {\Bbb N}} be a (standard) set of positive upper density which contains no progression of length {k}. Let {\delta := \limsup_{|P| \rightarrow \infty} |B \cap P|/|P|} be the asymptotic maximal density of {B} inside a long progression, thus {\delta > 0}. For any {n > 0}, one can then find a standard integer {N_n \geq n} and a standard subset {A_n} of {[N_n]} of density at least {\delta-1/n} such that {A_n} can be embedded (after a linear transformation) inside {B}, so in particular {A_n} has no progressions of length {k}. Applying the saturation property, one can then find an unbounded {N} and a set {A} of {[N]} of density at least {\delta-1/n} for every standard {n} (i.e. of density at least {\delta-o(1)}) with no progressions of length {k}. By construction, we also see that for any subprogression {P} of {[N]} of unbounded size, {A} hs density at most {\delta+1/n} for any standard {n}, thus has density at most {\delta+o(1)}, and the claim follows. \Box

This can be used as the starting point for any density-increment based proof of Szemerédi’s theorem for a fixed {k}, e.g. Roth’s proof for {k=3}, Gowers’ proof for arbitrary {k}, or Szemerédi’s proof for arbitrary {k}. (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

10 November, 2009 in expository, Logic reading seminar, math.CO | Tags: | by | 15 comments

Let {X} be a finite subset of a non-commutative group {G}. As mentioned previously on this blog (as well as in the current logic reading seminar), there is some interest in classifying those {X} which obey small doubling conditions such as {|X \cdot X| = O(|X|)} or {|X \cdot X^{-1}| = O(|X|)}. 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 {|X \cdot X|} is very close to {|X|}:

Proposition 1 If {|X^{-1} \cdot X| < \frac{3}{2} |X|}, then {X \cdot X^{-1}} and {X^{-1} \cdot X} are both finite groups, which are conjugate to each other. In particular, {X} is contained in the right-coset (or left-coset) of a group of order less than {\frac{3}{2} |X|}.

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

Proof: We begin by showing that {S := X \cdot X^{-1}} is a group. As {S} is symmetric and contains the identity, it suffices to show that this set is closed under addition.

Let {a, b \in S}. Then we can write {a=xy^{-1}} and {b=zw^{-1}} for {x,y,z,w \in X}. If {y} were equal to {z}, then {ab = xw^{-1} \in X \cdot X^{-1}} and we would be done. Of course, there is no reason why {y} should equal {z}; but we can use the hypothesis {|X^{-1} \cdot X| < \frac{3}{2}|X|} to boost this as follows. Observe that {x^{-1} \cdot X} and {y^{-1} \cdot X} both have cardinality {|X|} and lie inside {X^{-1} \cdot X}, which has cardinality strictly less than {\frac{3}{2} |X|}. By the inclusion-exclusion principle, this forces {x^{-1} \cdot X \cap y^{-1} \cdot X} to have cardinality greater than {\frac{1}{2}|X|}. In other words, there exist more than {\frac{1}{2}|X|} pairs {x',y' \in X} such that {x^{-1} x' = y^{-1} y'}, which implies that {a = x' (y')^{-1}}. Thus there are more than {\frac{1}{2}|X|} elements {y' \in X} such that {a = x' (y')^{-1}} for some {x'\in X} (since {x'} is uniquely determined by {y'}); similarly, there exists more than {\frac{1}{2}|X|} elements {z' \in X} such that {b = z' (w')^{-1}} for some {w' \in X}. Again by inclusion-exclusion, we can thus find {y'=z'} in {X} for which one has simultaneous representations {a = x' (y')^{-1}} and {b = y' (z')^{-1}}, and so {ab = x'(z')^{-1} \in X \cdot X^{-1}}, and the claim follows.

In the course of the above argument we showed that every element of the group {S} has more than {\frac{1}{2}|X|} representations of the form {xy^{-1}} for {x,y \in X}. But there are only {|X|^2} pairs {(x,y)} available, and thus {|S| < 2|X|}.

Now let {x} be any element of {X}. Since {X \cdot x^{-1} \subset S}, we have {X \subset S \cdot x}, and so {X^{-1} \cdot X \subset x^{-1} \cdot S \cdot x}. Conversely, every element of {x^{-1} \cdot S \cdot x} has exactly {|S|} representations of the form {z^{-1} w} where {z, w \in S \cdot x}. Since {X} occupies more than half of {S \cdot x}, we thus see from the inclusion-exclusion principle, there is thus at least one representation {z^{-1} w} for which {z, w} both lie in {X}. In other words, {x^{-1} \cdot S \cdot x = X^{-1} \cdot X}, and the claim follows. \Box

To relate this to the classical doubling constants {|X \cdot X|/|X|}, we first make an easy observation:

Lemma 2 If {|X \cdot X| < 2|X|}, then {X \cdot X^{-1} = X^{-1} \cdot X}.

Again, this is sharp; consider {X} equal to {\{x,y\}} where {x,y} generate a free group.

Proof: Suppose that {xy^{-1}} is an element of {X \cdot X^{-1}} for some {x,y \in X}. Then the sets {X \cdot x} and {X \cdot y} have cardinality {|X|} and lie in {X \cdot X}, so by the inclusion-exclusion principle, the two sets intersect. Thus there exist {z,w \in X} such that {zx=wy}, thus {xy^{-1}=z^{-1}w \in X^{-1} \cdot X}. This shows that {X \cdot X^{-1}} is contained in {X^{-1} \cdot X}. The converse inclusion is proven similarly. \Box

Proposition 3 If {|X \cdot X| < \frac{3}{2} |X|}, then {S := X \cdot X^{-1}} is a finite group of order {|X \cdot X|}, and {X \subset S \cdot x = x \cdot S} for some {x} in the normaliser of {S}.

The factor {\frac{3}{2}} 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 {S = X^{-1} \cdot X = X \cdot X^{-1}} (the two sets being equal by Lemma 2). By the argument used to prove Lemma 2, every element of {S} has more than {\frac{1}{2}|X|} representations of the form {xy^{-1}} for {x,y \in X}. By the argument used to prove Proposition 1, this shows that {S} is a group; also, since there are only {|X|^2} pairs {(x,y)}, we also see that {|S| < 2|X|}.

Pick any {x \in X}; then {x^{-1} \cdot X, X \cdot x^{-1} \subset S}, and so {X \subset x\cdot S, S \cdot x}. Because every element of {x \cdot S \cdot x} has {|S|} representations of the form {yz} with {y \in x \cdot S}, {z \in S \cdot x}, and {X} occupies more than half of {x \cdot S} and of {S \cdot x}, we conclude that each element of {x \cdot S \cdot x} lies in {X \cdot X}, and so {X \cdot X = x \cdot S \cdot x} and {|S| = |X \cdot X|}.

The intersection of the groups {S} and {x \cdot S \cdot x^{-1}} contains {X \cdot x^{-1}}, which is more than half the size of {S}, and so we must have {S = x \cdot S \cdot x^{-1}}, i.e. {x} normalises {S}, and the proposition follows. \Box

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

Read the rest of this entry »

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

5 November, 2009 in Logic reading seminar, math.CO, math.LO | Tags: , , | by | 5 comments

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:

Read the rest of this entry »

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

29 October, 2009 in Logic reading seminar, math.LO | Tags: , , , | by | 4 comments

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 {X \cdot X^{-1}}) must intersect if they are sufficiently “generic”; the notion of a wide type is designed, in part, to capture this notion of genericity.

Read the rest of this entry »

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

22 October, 2009 in Logic reading seminar, math.GR, math.LO | Tags: , , , , | by | 15 comments

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

Read the rest of this entry »

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

15 October, 2009 in Logic reading seminar, math.CO, math.LO | Tags: , , , , | by | 23 comments

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 {X} in a non-commutative group {G} which is of small doubling in the sense that the product set {X \cdot X := \{ xy: x, y \in X \}} is not much larger than {X} (e.g. {|X \cdot X| \leq K|X|} for some {K = O(1)}), what does this say about the structure of {X}? (For various technical reasons one may wish to replace small doubling by, say, small tripling (i.e. {|X \cdot X \cdot X| = O( |X| )}), and one may also wish to assume that {X} contains the identity and is symmetric, {X^{-1} = X}, 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 {K := |X \cdot X|/|X|} 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 {X} is a set of small doubling, then there should be some sort of “pseudo-metric” {\rho} on {G} which is left-invariant, and for which {X} is controlled (in some suitable sense) by the unit ball in this metric. (For instance, if {X} was a subgroup of {G}, one would take the metric which identified all the left cosets of {X} to a point, but was otherwise a discrete metric; if {X} 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 {X} be a set of small tripling, then one can find a long sequence of nested symmetric sets {X_1 \supset X_2 \supset X_3 \supset \ldots}, all of size comparable to {X} and contained in {(X^{-1} X)^2}, which are somewhat closed under multiplication in the sense that {X_i \cdot X_i \subset X_{i-1}} for all {i > 1}, and which are fairly well closed under commutation in the sense that {[X_i, X_j] \subset X_{i+j-1}}. (There are also some additional statements to the effect that the {X_n} efficiently cover each other, and also cover {X}, 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 {X} 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 {X_0} be a set of small tripling, let {X := X_0^{-1} X_0}, and suppose that for almost all {l}-tuples {a_1, \ldots, a_l \in X} (where {l=O(1)}), the conjugacy classes {a_i^X := \{ x^{-1} ax: x \in X \}} generate most of {X} in the sense that {|a_1^X \cdot \ldots \cdot a_l^X| \gg |X|}. Then a large part of {X} is contained in a subgroup of size comparable to {X}.

Note that if one quotiented out by the commutator {[X,X]}, then all of the conjugacy classes {a_i^X} would collapse to points. So the hypothesis here is basically a strong quantitative assertion to the effect that the commutator {[X,X]} is extremely large, and rapidly fills out most of {X} 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.]

Read the rest of this entry »

Archives