Suppose that are two subgroups of some ambient group , with the index of in being finite. Then is the union of left cosets of , thus for some set of cardinality . The elements of are not entirely arbitrary with regards to . For instance, if is a *normal* subgroup of , then for each , the conjugation map preserves . In particular, if we write for the conjugate of by , then

Even if is not normal in , it turns out that the conjugation map *approximately* preserves , if is bounded. To quantify this, let us call two subgroups *-commensurate* for some if one has

Proposition 1Let be groups, with finite index . Then for every , the groups and are -commensurate, in fact

*Proof:* One can partition into left translates of , as well as left translates of . Combining the partitions, we see that can be partitioned into at most non-empty sets of the form . Each of these sets is easily seen to be a left translate of the subgroup , thus . Since

and , we obtain the claim.

One can replace the inclusion by commensurability, at the cost of some worsening of the constants:

Corollary 2Let be -commensurate subgroups of . Then for every , the groups and are -commensurate.

*Proof:* Applying the previous proposition with replaced by , we see that for every , and are -commensurate. Since and have index at most in and respectively, the claim follows.

It turns out that a similar phenomenon holds for the more general concept of an *approximate group*, and gives a “classification” of all the approximate groups containing a given approximate group as a “bounded index approximate subgroup”. Recall that a -approximate group in a group for some is a symmetric subset of containing the identity, such that the product set can be covered by at most left translates of (and thus also right translates, by the symmetry of ). For simplicity we will restrict attention to finite approximate groups so that we can use their cardinality as a measure of size. We call finite two approximate groups *-commensurate* if one has

note that this is consistent with the previous notion of commensurability for genuine groups.

Theorem 3Let be a group, and let be real numbers. Let be a finite -approximate group, and let be a symmetric subset of that contains .

- (i) If is a -approximate group with , then one has for some set of cardinality at most . Furthermore, for each , the approximate groups and are -commensurate.
- (ii) Conversely, if for some set of cardinality at most , and and are -commensurate for all , then , and is a -approximate group.

Informally, the assertion that is an approximate group containing as a “bounded index approximate subgroup” is equivalent to being covered by a bounded number of shifts of , where approximately normalises in the sense that and have large intersection. Thus, to classify all such , the problem essentially reduces to that of classifying those that approximately normalise .

To prove the theorem, we recall some standard lemmas from arithmetic combinatorics, which are the foundation stones of the “Ruzsa calculus” that we will use to establish our results:

Lemma 4 (Ruzsa covering lemma)If and are finite non-empty subsets of , then one has for some set with cardinality .

*Proof:* We take to be a subset of with the property that the translates are disjoint in , and such that is maximal with respect to set inclusion. The required properties of are then easily verified.

Lemma 5 (Ruzsa triangle inequality)If are finite non-empty subsets of , then

*Proof:* If is an element of with and , then from the identity we see that can be written as the product of an element of and an element of in at least distinct ways. The claim follows.

Now we can prove (i). By the Ruzsa covering lemma, can be covered by at most

left-translates of , and hence by at most left-translates of , thus for some . Since only intersects if , we may assume that

and hence for any

By the Ruzsa covering lemma again, this implies that can be covered by at most left-translates of , and hence by at most left-translates of . By the pigeonhole principle, there thus exists a group element with

Since

and

the claim follows.

Now we prove (ii). Clearly

Now we control the size of . We have

From the Ruzsa triangle inequality and symmetry we have

and thus

By the Ruzsa covering lemma, this implies that is covered by at most left-translates of , hence by at most left-translates of . Since , the claim follows.

We now establish some auxiliary propositions about commensurability of approximate groups. The first claim is that commensurability is approximately transitive:

Proposition 6Let be a -approximate group, be a -approximate group, and be a -approximate group. If and are -commensurate, and and are -commensurate, then and are -commensurate.

*Proof:* From two applications of the Ruzsa triangle inequality we have

By the Ruzsa covering lemma, we may thus cover by at most left-translates of , and hence by left-translates of . By the pigeonhole principle, there thus exists a group element such that

and so by arguing as in the proof of part (i) of the theorem we have

and similarly

and the claim follows.

The next proposition asserts that the union and (modified) intersection of two commensurate approximate groups is again an approximate group:

Proposition 7Let be a -approximate group, be a -approximate group, and suppose that and are -commensurate. Then is a -approximate subgroup, and is a -approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment is replaced by commensurability; we leave the details to the interested reader.

*Proof:* We begin with . Clearly is symmetric and contains the identity. We have . The set is already covered by left translates of , and hence of ; similarly is covered by left translates of . As for , we observe from the Ruzsa triangle inequality that

and hence by the Ruzsa covering lemma, is covered by at most left translates of , and hence by left translates of , and hence of . Similarly is covered by at most left translates of . The claim follows.

Now we consider . Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that is covered by at most left-translates of , and hence there exists a group element with

Now observe that

and so by the Ruzsa covering lemma, can be covered by at most left-translates of . But this latter set is (as observed previously) contained in , and the claim follows.

## 4 comments

Comments feed for this article

6 June, 2015 at 5:38 am

A SAGE experiment on Nested Approximate Subgroups | Ashani Dasgupta[…] This concerns a computational experiment (in SAGE platform) inspired by an article by Terence Tao on Nested Approximate Subgroup. […]

8 June, 2015 at 6:43 pm

Ashani DasguptaProfessor Tao,

I am trying understand this article. However Ruzsa Calculus and allied topics are unknown to me (I have complete in by undergrad course in mathematics last year).

In my experience, tracking down good introductory book in any topic can be a critical and daunting task. So I thought of asking for your suggestion. Can you advice me to find a book on that topic to understand this article more vividly?

Regards,

Ashani Dasgupta

ashanidasgupta@yahoo.com

10 June, 2015 at 12:59 am

Terence TaoYou can try my book with Van Vu on these topics: https://terrytao.wordpress.com/books/additive-combinatorics/

10 June, 2015 at 12:59 am

Ashani DasguptaThanks for the response. I will