## Notes of Emmanuel Breuillard’s second lecture 07-03-2017

Introduction to approximate groups, II

1. Approximate groups

Naively, think of a finite subset ${A}$ in a group as approximately a subgroup if it does not increase much under multiplication. Here are various measurements:

• ${|AA|\leq K|A|}$. This is called small doubling.
• A weaker assumption is small tripling ${|AAA|\leq K|A|}$.
• Prob${_{a,b\in A}(ab\in A)\geq \frac{1}{K}}$.
• Coincidences ${ab=cd}$ are frequent:

$\displaystyle \begin{array}{rcl} |\{(a,b,c,d)\in A^4\,;\,ab=cd\}|\geq\frac{1}{K}|A|^3. \end{array}$

• ${\exists X\subset G}$ with ${|X|\leq K}$ and ${AA\subset XA}$.

In his Combinatorica paper, T. Tao showed that all these notions are roughly equivalent: there exists a universal constant ${C}$ such that for every ${K}$ there exists ${K'\leq K^C}$ such that if one of these properties holds with constant ${K}$ for some set ${A}$, then any other holds with constant ${K'}$ for a set ${A'}$ such that ${|A\cap A'|\geq |A|/K'}$, ${|A'|\leq K'|A|}$. Therefore Tao has chosen the following

Definition 1 (Tao) A finite set ${A\subset G}$ is a ${K}$-approximate group if

1. ${1\in A}$, ${A^{-1}=A}$,
2. there exists ${X\subset G}$ with ${|X|\leq K}$ and ${AA\subset XA}$.

Beware that small doubling does not imply small tripling. Indeed, the union of a subgroup ${H}$ and an element ${x\notin H}$ satisfies ${|AA|\leq 4|A|}$ but ${|AAA|\geq (|A|-1)^2}$.

This shows that one indeed needs to go to a smaller set ${A'}$ which has small tripling (here, remove ${x}$). However, small tripling implies small ${n}$-pling for all ${n\geq 3}$. In fact, more is true: ${|AA\cdots A|\leq K^C|A|}$ with ${C}$ independent on the number of factors.

2. Rusza’s distance

Definition 2 (Rusza) The Rusza distance between finite subsets ${A}$ and ${B}$ of group ${G}$ is

$\displaystyle \begin{array}{rcl} d(A,B)=\log\frac{|AB^{-1}|}{\sqrt{|A||B|}}. \end{array}$

Thus ${|AA|\leq K|A|\Leftrightarrow d(A,A^{-1})\leq \log K}$.

This is symmetric, nonnegative and satisfies triangle inequality. Furthermore, ${d(A,A)=0}$ iff ${A}$ is a coset of a finite group.

This is used in the proof that small tripling implies small ${n}$-pling.

Proof of triangle inequality

Consider map

$\displaystyle \begin{array}{rcl} AC^{-1}\times B\rightarrow AB^{-1}\times BC^{-1},\quad (x,b)\mapsto (a_x b^{-1},bc_x^{-1}), \end{array}$

where ${x=a_x c_x^{-1}}$, ${a_x\in A}$, ${c_x\in C}$. This map is injective.

This shows that ${|AC^{-1}||B|\leq |AB^{-1}||BC^{-1}|}$, qed.

Question. Is there some interesting geometry in this semi-metric ?

Lemma 3 (Rusza’s covering lemma) Assume that ${|AB|\leq K|A|}$. Then ${\exists X\subset B}$ such that ${|X|\leq K}$ and ${B\subset AA^{-1}X}$.

Indeed, pick a maximal set ${X\subset B}$ such that ${Ax}$, ${x\in X}$ are disjoint.

3. Further combinatorial tools

The theory has a small number of elementary tricks. We give 3 of them.

Proposition 4 (Plunnecke-Rusza, Petridis) When ${G}$ is abelian, if ${|A+A|\leq K|A|}$, then ${|mA-nA|\leq K^{m+n}|A|}$. In particular, small doubling implies small tripling.

Petridis has found a non-abelian version of this.

Lemma 5 (Petridis) If ${|AB|\leq K|A|}$, then there exists ${X\subset A}$ such that for all ${C\subset G}$, ${|CXB|\leq K|CX|}$.

Taking ${C=\{1\}}$ shows that ${X}$ is a definite fraction of ${B}$.

Proof. Pick ${X\subset A}$ such that ${\frac{|XB|}{|X|}}$ is minimal (hence ${\leq K}$). Then argue by induction on ${|C|}$.

Theorem 6 (Balog-Szemeredi-Gowers) Let ${A}$, ${B\subset G}$. Let ${\mathcal{G}}$ be a bipartite graph with vertex sets ${A}$ and ${B}$. Assume that

• ${|A|=|B|}$.
• ${|}$edges of ${\mathcal{G}|\geq \frac{1}{K}|A||B|}$.
• ${|A\cdot_\mathcal{G}B|\leq K|A|}$,

where ${A\cdot_\mathcal{G}B=\{ab\,;\,(a,b)}$ is an edge of ${\mathcal{G}\}}$. Then there exist ${A'\subset A}$ and ${B'\subset B}$ of size comparable to ${|A|}$ and such that ${|A'B'|\leq K^C|A|}$.

The proof is graph theory.

4. Statement of the structure theorem

Theorem 7 (Breuillard-Green-Tao) Let ${k\geq 1}$. Let ${A\subset G}$ be a finite group such that ${|AA|\leq K|A|}$. Then there exists a virtually nilpotent subgroup ${H}$ of ${G}$ and ${g\in G}$ such that ${|A\cap gH|\geq \frac{1}{C(K)}|A|}$.

${C(K)}$ depends only on ${K}$, not on ${G}$. Unfortunately, the proof does not give an effective bound on ${C(K)}$.

One can be more precise: ${H=F\cdot N}$ where ${N}$ is nilpotent with bounded number of generators and nilpotency class. Also${F}$ is bounded in the product of boundedly many copies o ${(A\cup A^{-1})^C}$.

Apply Rusza’s covering theorem, one gets ${A\subset H\cdot X}$ for some ${X\subset G}$ with ${|X|\leq C(K)}$.

4.1. Link with Gromov’s polynomial growth theorem

As it stands, this statement implies Gromov’s polynomial growth theorem. Indeed, if ${G}$ has a polynomial growth, there are infinitely many ${n}$ such that ${|S^{2n}|\leq K|S^n|}$. The structure theorem implies that ${S^n\subset H_n X_n}$, ${|X_n|\leq C(K)}$. If ${n>C(K)}$, then the index of ${H}$ is the subgroup generated by ${S}$ is at most ${C(H)}$.

4.2. Link with Margulis lemma

Corollary 8 Let ${X}$ be a metric space with bounded geometry (every ball of radius 4 is covered by a bounded number ${K}$ of balls of radius 1). Let ${\Gamma}$ a discrete group of isometries of ${X}$. For ${\epsilon\leq \epsilon_0(K)}$, the subgroup generated by the set ${S_\epsilon(x_0)}$ of elements ${\gamma\in \Gamma}$ such that ${d(\gamma x_0,x_0)<\epsilon}$ is virtually nilpotent.

Proof. Since ${(S_\epsilon(x_0))^n\subset S_{n\epsilon}(x_0)}$, ${S_\epsilon(x_0)}$ has small doubling.