You are currently browsing the monthly archive for June 2015.

Suppose that ${A \subset B}$ are two subgroups of some ambient group ${G}$, with the index ${K := [B:A]}$ of ${A}$ in ${B}$ being finite. Then ${B}$ is the union of ${K}$ left cosets of ${A}$, thus ${B = SA}$ for some set ${S \subset B}$ of cardinality ${K}$. The elements ${s}$ of ${S}$ are not entirely arbitrary with regards to ${A}$. For instance, if ${A}$ is a normal subgroup of ${B}$, then for each ${s \in S}$, the conjugation map ${g \mapsto s^{-1} g s}$ preserves ${A}$. In particular, if we write ${A^s := s^{-1} A s}$ for the conjugate of ${A}$ by ${s}$, then

$\displaystyle A = A^s.$

Even if ${A}$ is not normal in ${B}$, it turns out that the conjugation map ${g \mapsto s^{-1} g s}$ approximately preserves ${A}$, if ${K}$ is bounded. To quantify this, let us call two subgroups ${A,B}$ ${K}$-commensurate for some ${K \geq 1}$ if one has

$\displaystyle [A : A \cap B], [B : A \cap B] \leq K.$

Proposition 1 Let ${A \subset B}$ be groups, with finite index ${K = [B:A]}$. Then for every ${s \in B}$, the groups ${A}$ and ${A^s}$ are ${K}$-commensurate, in fact

$\displaystyle [A : A \cap A^s ] = [A^s : A \cap A^s ] \leq K.$

Proof: One can partition ${B}$ into ${K}$ left translates ${xA}$ of ${A}$, as well as ${K}$ left translates ${yA^s}$ of ${A^s}$. Combining the partitions, we see that ${B}$ can be partitioned into at most ${K^2}$ non-empty sets of the form ${xA \cap yA^s}$. Each of these sets is easily seen to be a left translate of the subgroup ${A \cap A^s}$, thus ${[B: A \cap A^s] \leq K^2}$. Since

$\displaystyle [B: A \cap A^s] = [B:A] [A: A \cap A^s] = [B:A^s] [A^s: A \cap A^s]$

and ${[B:A] = [B:A^s]=K}$, we obtain the claim. $\Box$

One can replace the inclusion ${A \subset B}$ by commensurability, at the cost of some worsening of the constants:

Corollary 2 Let ${A, B}$ be ${K}$-commensurate subgroups of ${G}$. Then for every ${s \in B}$, the groups ${A}$ and ${A^s}$ are ${K^2}$-commensurate.

Proof: Applying the previous proposition with ${A}$ replaced by ${A \cap B}$, we see that for every ${s \in B}$, ${A \cap B}$ and ${(A \cap B)^s}$ are ${K}$-commensurate. Since ${A \cap B}$ and ${(A \cap B)^s}$ have index at most ${K}$ in ${A}$ and ${A^s}$ respectively, the claim follows. $\Box$

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 ${B}$ containing a given approximate group ${A}$ as a “bounded index approximate subgroup”. Recall that a ${K}$-approximate group ${A}$ in a group ${G}$ for some ${K \geq 1}$ is a symmetric subset of ${G}$ containing the identity, such that the product set ${A^2 := \{ a_1 a_2: a_1,a_2 \in A\}}$ can be covered by at most ${K}$ left translates of ${A}$ (and thus also ${K}$ right translates, by the symmetry of ${A}$). For simplicity we will restrict attention to finite approximate groups ${A}$ so that we can use their cardinality ${A}$ as a measure of size. We call finite two approximate groups ${A,B}$ ${K}$-commensurate if one has

$\displaystyle |A^2 \cap B^2| \geq \frac{1}{K} |A|, \frac{1}{K} |B|;$

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

Theorem 3 Let ${G}$ be a group, and let ${K_1,K_2,K_3 \geq 1}$ be real numbers. Let ${A}$ be a finite ${K_1}$-approximate group, and let ${B}$ be a symmetric subset of ${G}$ that contains ${A}$.

• (i) If ${B}$ is a ${K_2}$-approximate group with ${|B| \leq K_3 |A|}$, then one has ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_1 K_2 K_3}$. Furthermore, for each ${s \in S}$, the approximate groups ${A}$ and ${A^s}$ are ${K_1 K_2^5 K_3}$-commensurate.
• (ii) Conversely, if ${B \subset SA}$ for some set ${S}$ of cardinality at most ${K_3}$, and ${A}$ and ${A^s}$ are ${K_2}$-commensurate for all ${s \in S}$, then ${|B| \leq K_3 |A|}$, and ${B}$ is a ${K_1^6 K_2 K_3^2}$-approximate group.

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

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 ${A}$ and ${B}$ are finite non-empty subsets of ${G}$, then one has ${B \subset SAA^{-1}}$ for some set ${S \subset B}$ with cardinality ${|S| \leq \frac{|BA|}{|A|}}$.

Proof: We take ${S}$ to be a subset of ${B}$ with the property that the translates ${sA, s \in S}$ are disjoint in ${BA}$, and such that ${S}$ is maximal with respect to set inclusion. The required properties of ${S}$ are then easily verified. $\Box$

Lemma 5 (Ruzsa triangle inequality) If ${A,B,C}$ are finite non-empty subsets of ${G}$, then

$\displaystyle |A C^{-1}| \leq |A B^{-1}| |B C^{-1}| / |B|.$

Proof: If ${ac^{-1}}$ is an element of ${AC^{-1}}$ with ${a \in A}$ and ${c \in C}$, then from the identity ${ac^{-1} = (ab^{-1}) (bc^{-1})}$ we see that ${ac^{-1}}$ can be written as the product of an element of ${AB^{-1}}$ and an element of ${BC^{-1}}$ in at least ${|B|}$ distinct ways. The claim follows. $\Box$

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

$\displaystyle \frac{|BA|}{|A|} \leq \frac{|B^2|}{|A|} \leq \frac{K_2 |B|}{|A|} \leq K_2 K_3$

left-translates of ${A^2}$, and hence by at most ${K_1 K_2 K_3}$ left-translates of ${A}$, thus ${B \subset SA}$ for some ${|S| \leq K_1 K_2 K_3}$. Since ${sA}$ only intersects ${B}$ if ${s \in BA}$, we may assume that

$\displaystyle S \subset BA \subset B^2$

and hence for any ${s \in S}$

$\displaystyle |A^s A| \leq |B^2 A B^2 A| \leq |B^6|$

$\displaystyle \leq K_2^5 |B| \leq K_2^5 K_3 |A|.$

By the Ruzsa covering lemma again, this implies that ${A^s}$ can be covered by at most ${K_2^5 K_3}$ left-translates of ${A^2}$, and hence by at most ${K_1 K_2^5 K_3}$ left-translates of ${A}$. By the pigeonhole principle, there thus exists a group element ${g}$ with

$\displaystyle |A^s \cap gA| \geq \frac{1}{K_1 K_2^5 K_3} |A|.$

Since

$\displaystyle |A^s \cap gA| \leq | (A^s \cap gA)^{-1} (A^s \cap gA)|$

and

$\displaystyle (A^s \cap gA)^{-1} (A^s \cap gA) \subset A^2 \cap (A^s)^2$

the claim follows.

Now we prove (ii). Clearly

$\displaystyle |B| \leq |S| |A| \leq K_3 |A|.$

Now we control the size of ${B^2 A}$. We have

$\displaystyle |B^2 A| \leq |SA SA^2| \leq K_3^2 \sup_{s \in S} |A s A^2| = K_3^2 \sup_{s \in S} |A^s A^2|.$

From the Ruzsa triangle inequality and symmetry we have

$\displaystyle |A^s A^2| \leq \frac{ |A^s (A^2 \cap (A^2)^s)| |(A^2 \cap (A^2)^s) A^2|}{|A^2 \cap (A^2)^s|}$

$\displaystyle \leq \frac{ |(A^3)^s| |A^4| }{|A|/K_2}$

$\displaystyle \leq K_2 \frac{ |A^3| |A^4| }{|A|}$

$\displaystyle \leq K_1^5 K_2 |A|$

and thus

$\displaystyle |B^2 A| \leq K_1^5 K_2 K_3^2 |A|.$

By the Ruzsa covering lemma, this implies that ${B^2}$ is covered by at most ${K_1^5 K_2 K_3^2}$ left-translates of ${A^2}$, hence by at most ${K_1^6 K_2 K_3^2}$ left-translates of ${A}$. Since ${A \subset B}$, the claim follows.

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

Proposition 6 Let ${A}$ be a ${K_1}$-approximate group, ${B}$ be a ${K_2}$-approximate group, and ${C}$ be a ${K_3}$-approximate group. If ${A}$ and ${B}$ are ${K_4}$-commensurate, and ${B}$ and ${C}$ are ${K_5}$-commensurate, then ${A}$ and ${C}$ are ${K_1^2 K_2^3 K_2^3 K_4 K_5 \max(K_1,K_3)}$-commensurate.

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

$\displaystyle |AC| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) (B^2 \cap C^2)| |(B^2 \cap C^2) C|}{|A^2 \cap B^2| |B^2 \cap C^2|}$

$\displaystyle \leq \frac{|A^3| |B^4| |C^3|}{ (|A|/K_4) (|B|/K_5)}$

$\displaystyle \leq K_4 K_5 \frac{K_1^2 |A| K_2^3 |B| K_3^2 |C|}{ |A| |B| }$

$\displaystyle = K_1^2 K_2^3 K_3^2 K_4 K_5 |C|.$

By the Ruzsa covering lemma, we may thus cover ${A}$ by at most ${K_1^2 K_2^3 K_3^2 K_4 K_5}$ left-translates of ${C^2}$, and hence by ${K_1^2 K_2^3 K_3^3 K_4 K_5}$ left-translates of ${C}$. By the pigeonhole principle, there thus exists a group element ${g}$ such that

$\displaystyle |A \cap gC| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|,$

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

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^2 K_2^3 K_3^3 K_4 K_5} |A|$

and similarly

$\displaystyle |A^2 \cap C^2| \geq \frac{1}{K_1^3 K_2^3 K_3^2 K_4 K_5} |C|$

and the claim follows. $\Box$

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

Proposition 7 Let ${A}$ be a ${K_1}$-approximate group, ${B}$ be a ${K_2}$-approximate group, and suppose that ${A}$ and ${B}$ are ${K_3}$-commensurate. Then ${A \cup B}$ is a ${K_1 + K_2 + K_1^2 K_2^4 K_3 + K_1^4 K_2^2 K_3}$-approximate subgroup, and ${A^2 \cap B^2}$ is a ${K_1^6 K_2^3 K_3}$-approximate subgroup.

Using this proposition, one may obtain a variant of the previous theorem where the containment ${A \subset B}$ is replaced by commensurability; we leave the details to the interested reader.

Proof: We begin with ${A \cup B}$. Clearly ${A \cup B}$ is symmetric and contains the identity. We have ${(A \cup B)^2 = A^2 \cup AB \cup BA \cup B^2}$. The set ${A^2}$ is already covered by ${K_1}$ left translates of ${A}$, and hence of ${A \cup B}$; similarly ${B^2}$ is covered by ${K_2}$ left translates of ${A \cup B}$. As for ${AB}$, we observe from the Ruzsa triangle inequality that

$\displaystyle |AB^2| \leq \frac{|A (A^2 \cap B^2)| |(A^2 \cap B^2) B^2|}{|A^2 \cap B^2|}$

$\displaystyle \leq \frac{|A^3| |B^4|}{|A|/K_3}$

$\displaystyle \leq K_1^2 K_2^3 K_3 |B|$

and hence by the Ruzsa covering lemma, ${AB}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left translates of ${B^2}$, and hence by ${K_1^2 K_2^4 K_3}$ left translates of ${B}$, and hence of ${A \cup B}$. Similarly ${BA}$ is covered by at most ${K_1^4 K_2^2 K_3}$ left translates of ${B}$. The claim follows.

Now we consider ${A^2 \cap B^2}$. Again, this is clearly symmetric and contains the identity. Repeating the previous arguments, we see that ${A}$ is covered by at most ${K_1^2 K_2^3 K_3}$ left-translates of ${B}$, and hence there exists a group element ${g}$ with

$\displaystyle |A \cap gB| \geq \frac{1}{K_1^2 K_2^3 K_3} |A|.$

Now observe that

$\displaystyle |(A^2 \cap B^2)^2 (A \cap gB)| \leq |A^5| \leq K_1^4 |A|$

and so by the Ruzsa covering lemma, ${(A^2 \cap B^2)^2}$ can be covered by at most ${K_1^6 K_2^3 K_3}$ left-translates of ${(A \cap gB) (A \cap gB)^{-1}}$. But this latter set is (as observed previously) contained in ${A^2 \cap B^2}$, and the claim follows. $\Box$