What’s new

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

Freiman’s theorem for solvable groups

21 June, 2009 in math.CO, math.GR, paper | Tags: Freiman's theorem, Milnor-Wolf theorem, nilpotent groups, solvable groups

I’m continuing the stream of uploaded papers this week with my paper “Freiman’s theorem for solvable groups“, submitted to Contrib. Disc. Math..  This paper concerns the problem (discussed in this earlier blog post) of determining the correct analogue of Freiman’s theorem in a general non-abelian group $G = (G,\cdot)$.  Specifically, if $A \subset G$ is a finite set that obeys the doubling condition $|A \cdot A| \leq K|A|$ for some bounded K, what does this tell us about A?  Heuristically, we expect A to behave like a finite subgroup of G (or perhaps a coset of such a subgroup).

When G is the integers (with the additive group operation), Freiman’s theorem then tells us that A is controlled by a generalised arithmetic progression P, where I say that one set A is controlled by another P if they have comparable size, and the former can be covered by a finite number of translates of the latter.  (One can view generalised arithmetic progressions as an approximate version of a subgroup, in which one only uses the generators of the progression for a finite amount of time before stopping, as opposed to groups which allow words of unbounded length in the generators.) For more general abelian groups, the Freiman theorem of Green and Ruzsa tells us that a set of bounded doubling is controlled by a generalised coset progression $P+H$, i.e. the sum of a generalised arithmetic progression P and a finite subgroup H of G.  (Of course, if G is torsion-free, the finite subgroup H must be trivial.)

In this paper we address the case when G is a solvable group of bounded derived length.  The main result is that if a subset of G has small doubing, then it is controlled by an object which I call a “coset nilprogression”, which is a certain technical generalisation of a coset progression, in which the generators do not quite commute, but have commutator expressible in terms of “higher order” generators.  This is essentially a sharp characterisation of such sets, except for the fact that one would like a more explicit description of these coset nilprogressions.   In the torsion-free case, a more explicit description (analogous to the Mal’cev basis description of nilpotent groups) has appeared in a very recent paper of Breulliard and Green; in the case of monomial groups (a class of groups that overlaps to a large extent with solvable groups), and assuming a polynomial growth condition rather than a doubling condition, a related result controlling A by balls in a suitable type of metric has appeared in very recent work of Sanders.  In the nilpotent case there is also a nice recent argument of Fisher, Peng, and Katz which shows that sets of small doubling remain of small doubling with respect to the Lie algebra operations of addition and Lie bracket, and thus are amenable to the abelian Freiman theorems.

The conclusion of my paper is easiest to state (and easiest to prove) in the model case of the lamplighter group $G = {\Bbb Z} \rtimes {\Bbb F}_2^\omega$, where ${\Bbb F}_2^\omega = \lim_{n \to \infty} {\Bbb F}_2^n$ is the additive group of doubly infinite sequences in the finite field ${\Bbb F}_2$ with only finitely many non-zero entries, and ${\Bbb Z}$ acts on this space by translations.  This is a solvable group of derived length two.  The main result here is

Theorem 1. (Freiman’s theorem for the lamplighter group) If $A \subset {\Bbb Z} \ltimes {\Bbb F}_2^\omega$ has bounded doubling, then A is controlled either by a finite subspace of the “vertical” group $\{0\} \times {\Bbb F}_2^\omega$, or else by a set of the form $\{ (n,\phi(n)): n \in P \}$, where $P \subset {\Bbb Z}$ is a generalised arithmetic progression, and $\phi: P \to {\Bbb F}_2^{\omega}$ obeys the Freiman isomorphism property $(n_1,\phi(n_1)) \cdot (n_2, \phi(n_2)) = (n_3,\phi(n_3)) \cdot (n_4,\phi(n_4))$ whenever $n_1,n_2,n_3,n_4 \in P$ and $n_1+n_2=n_3+n_4$.

This result, incidentally, recovers an earlier result of Lindenstrauss that the lamplighter group does not contain a Følner sequence of sets of uniformly bounded doubling.  It is a good exercise to establish the “exact” version of this theorem, in which one classifies subgroups of the lamplighter group rather than sets of small doubling; indeed, the proof of this the above theorem follows fairly closely the natural proof of the exact version.

One application of the solvable Freiman theorem is the following quantitative version of a classical result of Milnor and of Wolf, which asserts that any solvable group of polynomial growth is virtually nilpotent:

Theorem 2. (Quantitative Milnor-Wolf theorem) Let G be a solvable group of derived length O(1), let S be a set of generators for G, and suppose one has the polynomial growth condition $|B_S(R)| \leq R^d$ for some d = O(1), where $B_S(R)$ is the set of all words generated by S of length at most R.  If R is sufficiently large, then this implies that G is virtually nilpotent; more precisely, G contains a nilpotent subgroup of step O(1) and index $O(R^{O(1)})$.

The key points here are that one only needs polynomial growth at a single scale R, rather than on many scales, and that the index of the nilpotent subgroup has polynomial size.

The proofs are based on an induction on the derived length.  After some standard manipulations (basically, splitting A by an approximate version of a short exact sequence), the problem boils down to that of understanding the action $\rho$ of some finite set A on a set E in an additive group.  If one assumes that E has small doubling and that the action of A leaves E approximately invariant, then one can show that E is a coset progression, and the action of A can be described efficiently using the generators of that progression (after refining the set A a bit).

In the course of the proof we need two new additive combinatorial results which may be of independent interest.  The first is a variant of a well-known theorem of Sárközy, which asserts that if A is a large subset of an arithmetic progression P, then an iterated sumset kA of A for some $k=O(1)$ itself contains a long arithmetic progression. Here, we need the related fact that if A is a large subset of a coset progression, then an iterated subset kA for $k=O(1)$ contains a large coset progression Q, and furthermore this inclusion is “robust” in the sense that all elements the elements of Q have a large number of representations as sums of elements of A.  We also need a new (non-commutative) variant of the Balog-Szemerédi(-Gowers) lemma, which asserts that if A has small doubling, then A (or more precisely $A \cdot A^{-1}$) contains a large “core” subset D such that almost all of a large iterated subset kD of D still lies inside $A \cdot A^{-1}$).  (This may not look like the usual Balog-Szemerédi lemma, but the proof of the lemma is almost identical to the original proof of Balog and Szemerédi, in particular relying on the Szemerédi regularity lemma.

15 comments

21 June, 2009 at 1:41 pm

Anonymous

Missing “paper” tag. [Fixed, thanks - T.]

21 June, 2009 at 2:00 pm

pierre

Out of curiosity, how do you usually decide which journal to submit to?

Dear Pierre,

http://terrytao.wordpress.com/advice-on-writing-papers/submit-to-an-appropriate-journal/

for my thoughts on these sorts of issues.

22 June, 2009 at 3:26 am

David Speyer

Typo: In the statement of Theorem 1, and in the paragraph before it, I think your semidirect product is backwards. The integers act on $F_2^{\omega}$, right? [Corrected, thanks]

I am very happy to see both this paper and the new paper by Green and Breuillard. I’d like to focus on your Corollary 1.21, and why you truly need the hypothesis that G be totally torsion-free in order to take H=N. I thought your readers might be interested in a few examples over finite fields. In these examples, G is not totally torsion-free (because it is finite!), one cannot take H=N (the conclusion would then be false), and the statement of Corollary 1.21 becomes unfortunately trivial.

These examples show that a subset A of a solvable group G can have small doubling constant and yet be far from being contained in a nilpotent group (or a few cosets thereof).
At the same time, as I will say thereafter, a different kind of reduction to the nilpotent case should still be possible.

Example 1.-

Let $G = SL_3(K)$, where $K = Z/pZ$.

Let

$A = \left\{\left(\begin{matrix} r^k & x & y\\ 0 & s^k & z \\ 0 & 0 & (r s)^{-k}\end{matrix}\right) : x,y,z \in K, -N\leq k\leq N\right\}$,

where r and s are arbitrary elements of $K^*$.

The doubling constant is $<=4$, but A is far from being contained in anything nilpotent.

Example 2.-

Let $G = SL_3(K)$, where $K=Z/pZ$.

Let

$A = \left\{\left(\begin{matrix} r^k & k' & y\\ 0 & r^k & z \\ 0 & 0 & (r)^{-2k}\end{matrix}\right) : y,z \in K, -N\leq k\leq N, -M\leq k'\leq M\right\},$

where r is an arbitrary element in $K^*$.

The doubling constant is $\leq 4$, but, again, A is far from being nilpotent.

———-

It seems to me that one can make, nevertheless, make a general
reduction of the solvable case to the nilpotent case. Moreover, one
should be able to prove such a result with techniques available now.

—————

Very realistic conjecture. Let A be a subset of a solvable group G
of derived length at most l. Then, for any K, either

$|A A A| \geq K |A|$

or

there are subgroups $H_1\triangleleft H_2 \triangleleft \langle A\rangle$ such that

(a) $H_1$ is contained in $(A \cup \{I\} \cup A^{-1})^k$, where k depends only on l,
(b) A is contained in $<= K^C$ cosets of $H_2$, where C depends only on l, and
(c) $H_2/H_1$ is nilpotent.
—————–

I like to require these subgroups to be normal (which you haven't done); that makes the reduction more complete, and makes some of that business of K-approximate groups
automatically true. On the other hand, requiring $H_2 \triangleleft \langle A\rangle$
as opposed to just $H_2 < \langle A \rangle$ will probably make the proof more complicated. (Or do you think that $H_2\triangleleft \langle A\rangle$ is perhaps not even always true?)

The "very realistic conjecture" becomes a much harder conjecture (but is still probably true) if, instead of letting G be a solvable group of derived length <=l, we let G
be any subgroup of $SL_l(K)$ for any field K. I recently proved such a statement for
$SL_3(Z/pZ)$ (http://arxiv.org/abs/0807.2027, Thm 1.1). I am now working on growth in $SL_n(K)$, but I'll probably restrict myself to sets generating $SL_n(K)$ in the near future: I am having difficulties with sets that generate $SO_n$, for example.

Returning to the solvable case: the very realistic conjecture should yield to techniques related to the sum-product theorem. As you know, I really think the sum-product theorem is a special case of a more general statement on groups acting on groups. I prove a statement of that nature in section 3 of my $SL_3$ paper – it may very well be strong enough to use as the main tool to prove the (very realistic) conjecture, but it's certainly not something that solves the problem immediately.

At any rate, you see how the conjecture would reduce the solvable problem more or less completely to what Ben [Green] and Emmanuel [Breuillard] are doing. (In fact, since it has polynomial dependence, it will still be enough if some day a polynomial Freiman-Ruzsa theorem is proven.) I say "more or less" simply because the few cosets of $H_2$ occupied by elements of A may act on $H_2$ in an interesting way by conjugation, and that may force some sets to grow that would not grow otherwise; that still needs to be looked into.

Tell me what you think.

23 June, 2009 at 1:18 pm

Harald

My longer comments are not appearing; do you know what is the matter? Are you receiving them? [Your comment was caught in the automatic spam filter, but I restored it manually. -T.]

Dear Harald,

Thanks for the examples!

I think the conjecture is quite plausible (except perhaps for the polynomial dependence on K in the gap between A and H_2, which is rather ambitious with current technology – note we don’t have polynomial Freiman-Ruzsa even in the abelian case right now). In my paper I manage to control A by a slightly weaker object that I call a “coset nilprogression”. Roughly speaking, you are controlling A by a finite extension $H_2$ of a nilpotent group $N := H_2/H_1$, thus $0 \to H_1 \to H_2 \to N \to 0$, (and nilpotent groups can be viewed as towers of central extensions of the trivial group); coset nilprogressions are a bit more complicated, being a tower in which each stage is either a central extension or a finite extension, but they can come jumbled up in a funny way, in particular the finite stuff doesn’t necessarily come at the very top of the tower, but is sort of scattered through the tower. But it may actually be possible to disentangle this tower and pull all the finite stuff out as a big normal subgroup, as you suggest. I’ll have to think about it.

[Actually, with my nilprogressions, I'm not so much extending things by central groups, but rather by central progressions. This is sort of a fuzzy concept - the language of "approximate group theory" is not yet well developed enough to cleanly deal with extending an approximate group by another approximate group (e.g. extending a nilprogression by an arithmetic progression, somewhat similar to how your examples are operating) - and so the precise formalisation of this concept in my paper (Definition 1.11) is quite yucky, analogous to what the concept of a group extension $0 \to K \to G \to H \to 0$ would look like if one insisted on writing everything in coordinates, thus creating a partial inverse $\phi: H \to G$ and expressing elements of G in the form $k \phi(h)$ for $k \in K, h \in H$.]

25 June, 2009 at 8:15 am

Harald

Dear Terry,

>I think the conjecture is quite plausible (except perhaps for the polynomial dependence >on K in the gap between A and H_2, which is rather ambitious with current technology – >note we don’t have polynomial Freiman-Ruzsa even in the abelian case right now).

One doesn’t need polynomial Freiman-Ruzsa in any shape or form to get polynomial dependence here. In fact, I have already got polynomial dependence for A in a solvable subgroups of SL_3(Z/pZ) – well, actually, for any A in SL_3(Z/pZ). Otherwise I would not have been able to prove a result of the form |A A A| >> |A|^{1+epsilon} for subsets A of SL_3(Z/pZ) generating SL_3(Z/pZ).

In your paper, you are using ideas connected to Freiman-Ruzsa. I posit that these ideas belong to the study of nilpotent groups. The reduction of the solvable case to the nilpotent case can be managed entirely by what may call generalised sum-product technology (though the name is arguably outdated now), without any recourse to Freiman-Ruzsa. One great advantage of this is that we can get polynomial dependence right now.

>But it may actually be possible to disentangle this tower and pull all the finite stuff out >as a big normal subgroup, as you suggest. I’ll have to think about it.

I would be very curious to know what you get.

Best,
Harald

Dear Harald,

I suppose that our current range of polynomially quantitative techniques may indeed be able to get a polynomial solvable-to-nilpotent reduction, but my guess is that it would have to use some rather explicit structure of the solvable group. It isn’t quite the same, but Fisher-Katz-Peng’s paper make a kind of polynomial nilpotent-to-abelian reduction based primarily on the Baker-Campbell-Hausdorff formula.

I did some calculations. It does indeed seem that the methods in my paper give your claim except for the polynomial bounds. The key new point is that if a matrix is both nilpotent and of finite order (with integer coefficients), then it is the identity. As a consequence, when one is extending some coset nilprogression by a proper abelian progression, with the conjugation action of the former on the latter being nilpotent, the action of any finite abelian subgroup of the base coset nilprogression on the proper progression is trivial and so that finite abelian subgroup can be absorbed into the extension group (and can eventually be quotiented out). Combining this with the stuff in my paper and using induction disentangles the tower and eventually gives the claim (I’ll send you more detailed computations at some point).

Dear Terry,

>I suppose that our current range of polynomially quantitative techniques may indeed be >able to get a polynomial solvable-to-nilpotent reduction, but my guess is that it would >have to use some rather explicit structure of the solvable group.

I cannot fully agree. There are already partial statements one can prove without any explicit work. This makes me think that it might be possible to settle the “very realistic conjecture” I stated above without much explicit work at all.

(I’ve sent you something – it’s very preliminary, though.)

[...] weaker version of this lemma was also established by myself [...]

[...] and proving this statement is the noncommutative Freiman theorem problem, discussed in these earlier blog [...]

[...] a “noncommutative Freiman” type theorem in linear groups . As discussed in earlier blog posts, a general question in additive (or multiplicative) combinatorics is to understand the structure of [...]

[...] groups, nilpotent groups, solvable groups, or simple groups of Lie type) are also known; see these previous blog posts for a summary of several of these [...]

[...] of . The Borel group is solvable, and by using tools from additive combinatorics, such as Freiman’s theorem in solvable groups (or the Helfgott-Lindenstrauss conjecture, discussed in the previous quarter’s notes), one [...]

Cancel
{"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": 60, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "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.9358099102973938, "perplexity_flag": "head"}