What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

# Tag Archive

You are currently browsing the tag archive for the ‘Ehud Hrushovski’ tag.

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

5 November, 2009 in math.CO, math.LO, Logic reading seminar | Tags: Ehud Hrushovski, definability, henry towsner | by Terence Tao | 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:

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

Read the rest of this entry »

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

15 October, 2009 in math.CO, math.LO, Logic reading seminar | Tags: Freiman's theorem, Ehud Hrushovski, definability, type, Isaac Goldbring | by Terence Tao | 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 »

### Recent Comments

Luqing Ye on 245A, Notes 2: The Lebesgue…
Frank on Soft analysis, hard analysis,…
andrescaicedo on Soft analysis, hard analysis,…
Richard Palais on Pythagoras’ theorem
The Coffee Stains in… on Does one have to be a genius t…
Benoît Régent-Kloeck… on (Ingrid Daubechies) Planning f…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
%anchor_text% on Books
Luqing Ye on 245B, Notes 7: Well-ordered se…
Arjun Jain on 245B, Notes 7: Well-ordered se…
Luqing Ye on 245A, Notes 2: The Lebesgue…
Luqing Ye on 245A, Notes 2: The Lebesgue…
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 43, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9326125979423523, "perplexity_flag": "middle"}