---
abstract: 'We show that if $A$ is a finite $K$-approximate subgroup of an $s$-step nilpotent group then there is a finite normal subgroup $H\subset A^{K^{O_s(1)}}$ modulo which $A^{O_s(\log^{O_s(1)}K)}$ contains a nilprogression of rank at most $O_s(\log^{O_s(1)}K)$ and size at least $\exp(-O_s(\log^{O_s(1)}K))|A|$. This partially generalises the close-to-optimal bounds obtained in the abelian case by Sanders, and improves the bounds and simplifies the exposition of an earlier result of the author. Combined with results of Breuillard–Green, Breuillard–Green–Tao, Gill–Helfgott–Pyber–Szabó, and the author, this leads to improved rank bounds in Freiman-type theorems in residually nilpotent groups and certain linear groups of bounded degree.'
address: 'Pembroke College, Cambridge, CB2 1RF, United Kingdom'
author:
- 'Matthew C. H. Tointon'
title: Polylogarithmic bounds in the nilpotent Freiman theorem
---

Introduction
============

This paper concerns *sets of small doubling* and *approximate groups* in non-abelian groups. This topic has been extensively covered in the recent mathematical literature; the reader may consult the author’s forthcoming book [@book] or the surveys [@bgt.survey; @app.grps; @ben.icm; @helf.survey; @sand.survey; @raconte-moi] for detailed background to the topic and examples of some of its many applications.

Given sets $A$ and $B$ in a group $G$ we define the *product set* $AB$ by $AB=\{ab:a\in A,b\in B\}$, and define $A^n$ recursively for $n\in{\mathbb{N}}$ by setting $A^1=A$ and $A^{n+1}=A^nA$. We also write $A^{-1}=\{a^{-1}:a\in A\}$ and $A^{-n}=(A^{-1})^n$. If $G$ is abelian we often use additive notation instead, for example writing $A+B$ or $nA$ in place of $AB$ or $A^n$, respectively.

By the *doubing* of a finite set $A$ we mean the ratio $|A^2|/|A|$, and when we say that a set has ‘small’ or ‘bounded’ doubling we mean that there is some constant $K\ge1$ such that $|A^2|\le K|A|$. Of course, this always holds for $K=|A|$, so $K$ should be thought of as being substantially smaller than $|A|$ in order for this to be meaningful.

One of the central aims in the theory of sets of small doubling is to describe the algebraic structure of such sets. The first result in this direction was Freiman’s theorem [@freiman], which describes sets of small doubling in terms of objects called *progressions*. Given elements $x_1,\ldots,x_r$ in an abelian group $G$ and reals $L_1,\ldots,L_r\ge0$, the *progression* $P(x;L)$ is defined via $P(x;L)=\{\ell_1x_1+\cdots+\ell_rx_r:|\ell_i|\le L_i\}$. Freiman’s theorem states that if a subset $A\subset{\mathbb{Z}}$ satisfies $|A+A|\le K|A|$ then there exists a progression $P$ of rank at most $r(K)$ and size at most $h(K)|A|$ such that $A\subset P$. This was subsequently generalised to an arbitrary abelian group by Green and Ruzsa [@green-ruzsa], where one must replace the progression with a *coset progression*, which simply means a set of the form $H+P$, with $H$ a finite subgroup and $P$ a progression.

The best bounds currently available in this theorem are due to Sanders (although Schoen [@schoen] had previously obtained similar bounds in the special case of subsets of integers). Sanders’s main result is the following variant of Freiman’s theorem; in it and elsewhere we write $\log^mK$ to mean $(\log K)^m$.

\[thm:sanders\] Let $A$ be a finite subset of an abelian group such that $|A+A|\le K|A|$. Then there exists a coset progression $H+P$ of rank at most $O(\log^{O(1)}2K)$ such that $H+P\subset 2A-2A$ and $|H+P|\ge\exp(-O(\log^{O(1)}2K))|A|$.

Combining \[thm:sanders\] with the so-called *covering argument* of Chang [@chang]—which we present in \[lem:chang\], below—one obtains the following bounds in Freiman’s theorem.

\[cor:sanders.ext\] Let $A$ be a finite subset of an abelian group such that $|A+A|\le K|A|$. Then there exists a coset progression $H+P$ of rank at most $O(K\log^{O(1)}2K)$ satisfying $|H+P|\le\exp(O(K\log^{O(1)}2K))|A|$ such that $A\subset H+P$.

These bounds are close to best possible, as can be seen by considering, for example, an appropriate union of $K$ translates of a finite subgroup or a rank-$1$ progression.

It is worth remarking that using a simpler covering argument due to Ruzsa [@ruzsa], on which Chang’s argument is based, one can also deduce the following variant of Theorem \[thm:sanders\]; we give details in Section \[sec:prelim\].

\[cor:sanders\] Let $A$ be a finite subset of an abelian group such that $|A+A|\le K|A|$. Then there exists a coset progression $H+P\subset 4A-4A$ of rank at most $O(\log^{O(1)}2K)$ satisfying $|H+P|\le K^8|A|$, and a set $X\subset A$ of size at most $\exp(O(\log^{O(1)}2K))$ such that $A\subset X+H+P$.

In this paper we are concerned with generalisations of these results to non-abelian groups, and specifically to nilpotent groups. The basic properties of nilpotent groups that we use can be found in [@hall Chapter 10] or [@book §5.2].

In the non-abelian setting it is usual for technical reasons to replace the small-doubling assumption $|A+A|\le K|A|$ with a slightly stronger assumption. This is usually either a ‘small-tripling’ assumption $|A^3|\le K|A|$, or the qualitativey even stronger assumtion that $A$ is a *$K$-approximate group*.

Given $K\ge1$, a subset $A$ of a group $G$ is said to be a *$K$-approximate subgroup of $G$*, or simply a *$K$-approximate group*, if $A^{-1}=A$ and $1\in A$, and if there exists $X\subset G$ with $|X|\le K$ such that $A^2\subset XA$.

The reasons for making these stronger assumptions are explained at length in [@tao.product.set; @book], but let us highlight the fact that a set $A$ satisfying $|A^2|\le K|A|$ is contained in the union of a few translates of a relatively small $O(K^{O(1)})$-approximate group [@tao.product.set Theorem 4.6], so there is no great loss of generality in doing so. Note, conversely, that if $A$ is a finite $K$-approximate group then $|A^m|\le K^{m-1}|A|$ for every $m\in{\mathbb{N}}$, a fact we will use on a number of occasions without further mention.

There are a number of ways to formulate the appropriate generalisation of a coset progression to non-abelian groups. The easiest to define is probably a *coset nilprogression*. Given elements $x_1,\ldots,x_r$ in a group $G$ and $L_1,\ldots,L_r\ge0$, the *nonabelian progression* $P(x;L)$ is defined to consist of all those elements of $G$ that can be expressed as words in the $x_i$ and their inverses in which each $x_i$ and its inverse appear at most $L_i$ times between them. We define $r$ to be the *rank* of $P(x;L)$. If the $x_i$ generate an $s$-step nilpotent group then $P(x;L)$ is said to be a *nilprogression* of step $s$, and in this instance we write $P_{\text{\textup{nil}}}(x;L)$ instead of $P(x;L)$. A set $P$ is said to be a *coset nilprogression* of rank $r$ and step $s$ if there exists a finite subgroup $H\subset P$, normalised by $P$, such that the image of $P$ in $\langle P\rangle/H$ is a nilprogression of rank $r$ and step $s$.

Another useful formulation is a closely related object called a *nilpotent progression*. Again, a nilpotent progression $\overline P(x;L)$ is defined using elements $x_1,\ldots,x_r$ in a nilpotent group $G$ and reals $L_1,\ldots,L_r\ge0$, but its definition is a little more involved than that of a nilprogression, so we refer the reader to any of [@bg; @nilp.frei; @book].

Nilpotent progressions have tripling bounded in terms of their rank and step, as do nilprogressions if the reals $L_1$ are large enough [@bt Corollary 3.16]. For technical reasons, it is also convenient to define a third type of progression in a non-abelian group, although in general this one will not have bounded doubling. Given $x_i$ and $L_i$ as above, the *ordered progression* $P_{\text{\textup{ord}}}(x;L)$ is defined to be $P_{\text{\textup{ord}}}(x;L)=\{x_1^{\ell_1}\cdots x_r^{\ell_r}:|\ell_i|\le L_i\}$.

The following result shows that it does not matter too much which of the above versions of progression we use.

\[prop:nilprog.equiv\] Let $G$ be an $s$-step nilpotent group, let $x_1,\ldots,x_r\in G$, and let $L_1,\ldots,L_r\in{\mathbb{N}}$. Then $P_{\text{\textup{ord}}}(x;L)\subset P_{\text{\textup{nil}}}(x;L)\subset\overline P(x;L)\subset P_{\text{\textup{ord}}}(x;L)^{(96s)^{s^2}r^s}$.

The bounds we state here are written more explicitly than in [@nilp.frei Proposition C.1], but bounds of the type we claim here can easily be read out of the argument there. \[prop:nilprog.equiv\] is also proved exactly as stated above in [@book Proposition 5.6.4].

The author has previously extended \[cor:sanders.ext\] to nilpotent groups, proving the following result.

\[thm:old\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be an $s$-step nilpotent group $s$, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist a subgroup $H$ of $G$ normalised by $A$ and a nilprogression $P_{\text{\textup{nil}}}(x;L)$ of rank at most $K^{O_s(1)}$ such that $$A\subset HP_{\text{\textup{nil}}}(x;L)\subset H\overline P(x;L)\subset A^{K^{O_s(1)}}.$$

In particular, $|H\overline P(x;L)|\le\exp(K^{O_s(1)})|A|$.

The aim of the present paper is to show that, like in the abelian case, if we ask for $HP$ to be dense in $A$, rather than the other way around, we can replace most of the polynomial bounds of \[thm:old\] with polylogarithmic bounds, as follows.

\[thm:new.gen\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be an $s$-step nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist a subgroup $H\subset A^{K^{e^{O(s)}}}$ normalised by $A$ and an ordered progression $P_{\text{\textup{ord}}}(x;L)\subset A^{e^{O(s^2)}\log^{O(s)}2K}$ of rank at most $e^{O(s^2)}\log^{O(s)}2K$ such that $$P_{\text{\textup{ord}}}(x;L)\subset P_{\text{\textup{nil}}}(x;L)\subset\overline P(x;L)\subset A^{e^{O(s^3)}\log^{O(s^2)}2K}$$ and $$|HP_{\text{\textup{ord}}}(x;L)|\ge\exp\left(-e^{O(s^2)}\log^{O(s)}2K\right)|AH|.$$

The proof of \[thm:old\] proceeds by an induction on the step $s$, in which \[thm:sanders\] features both in the base case $s=1$ and in the proof of the inductive step. The original proof used an earlier version of \[thm:sanders\], due to Green and Ruzsa, in which the bounds are polynomial rather than polylogarithmic. Let us emphasise, though, that losses elsewhere in the argument overwhelmed the bounds of \[thm:sanders\] to the extent that it made no difference to the shape of the final bounds to use the Green–Ruzsa result instead. In particular, proving \[thm:new.gen\] is not merely a case of substituting \[thm:sanders\] for the Green–Ruzsa result in the original proof: we also need to make the rest of the argument more efficient.

The one bound that is still polynomial in \[thm:new.gen\] is the bound $H\subset A^{K^{e^{O(s)}}}$; it appears that a new idea would be required to improve this any further (see \[rem:poly.bound\], below, for further details). Note, though, that in the case where the ambient group has no torsion the subgroup $H$ is automatically trivial, leaving only the polylogarithmic bounds, as follows.

\[thm:new.tf\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be a torsion-free $s$-step nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist an ordered progression $P_{\text{\textup{ord}}}(x;L)\subset A^{e^{O(s^2)}\log^{O(s)}2K}$ of rank at most $e^{O(s^2)}\log^{O(s)}2K$ such that $$P_{\text{\textup{ord}}}(x;L)\subset P_{\text{\textup{nil}}}(x;L)\subset\overline P(x;L)\subset A^{e^{O(s^3)}\log^{O(s^2)}2K}$$ and $$|P_{\text{\textup{ord}}}(x;L)|\ge\exp\left(-e^{O(s^2)}\log^{O(s)}2K\right)|A|.$$

As in the abelian case, Ruzsa’s covering argument combines with \[thm:new.gen\] to give the following variant.

\[cor:ruzsa\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be an $s$-step nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist a subgroup $H\subset A^{K^{e^{O(s)}}}$ normalised by $A$, a nilprogression $P_{\text{\textup{nil}}}(x;L)$ of rank at most $e^{O(s^2)}\log^{O(s)}2K$ such that $$P_{\text{\textup{nil}}}(x;L)\subset\overline P(x;L)\subset A^{e^{O(s^3)}\log^{O(s^2)}2K},$$ and a subset $X\subset G$ of size at most $\exp(e^{O(s^2)}\log^{O(s)}2K)$ such that $A\subset XHP_{\text{\textup{nil}}}(x;L)$.

In particular, $|H\overline P(x;L)|\le\exp(K^{e^{O(s)}})|A|$. In the torsion-free setting the subgroup $H$ is again trivial, and in that case we may conclude instead that $|\overline P(x;L)|\le\exp(e^{O(s^3)}\log^{O(s^2)}2K)|A|$.

Chang’s covering argument also allows us to recover \[thm:old\] with much more precise bounds, as follows.

\[cor:chang.ag\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be an $s$-step nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist a subgroup $H\subset A^{K^{e^{O(s)}}}$ normalised by $A$ and a nilprogression $P_{\text{\textup{nil}}}(x;L)$ of rank at most $e^{O(s^2)}K\log^{O(s)}2K$ such that $$A\subset HP_{\text{\textup{nil}}}(x;L)\subset H\overline P(x;L)\subset HA^{e^{O(s^3)}K^{s+1}\log^{O(s^2)}2K}.$$

In particular, $|H\overline P(x;L)|\le\exp(K^{e^{O(s)}})|A|$, or $|P(x;L)|\le\exp(e^{O(s^3)}K^{s+1}\log^{O(s^2)}2K)|A|$ in the torsion-free setting.

We deduce these corollaries in \[sec:covering\].

<span style="font-variant:small-caps;">Applications to other groups.</span> A theorem of Breuillard, Green and Tao [@bgt] states, in one form, that an arbitrary finite $K$-approximate group $A$ is contained in a union of at most $O_K(1)$ translates of a coset nilprogression of rank and step $O(K^2\log K)$ and size at most $K^{11}|A|$. This result is powerful enough to have some quite general applications, such as those contained in [@bgt §11] and [@bt; @tao.growth; @tt], but its usefulness is slightly lessened by the fact that it does not give an explicit bound on the number of translates needed to contain $A$. Partly for this reason, various papers by several different authors have given explicit versions of this theorem for certain specific classes of groups.

The approach taken in these results is generally first to reduce to the nilpotent case, and then to apply \[thm:old\] (or an earlier result of Breuillard and Green [@bg] valid only in the torsion-free setting) to obtain the nilprogression. Unsurprisingly, using \[thm:new.gen\] or one of its corollaries in place of \[thm:old\] in these arguments leads to better bounds in a number of cases. In \[sec:non-nilp\] we present such better bounds for linear groups over ${\mathbb{F}}_p$ or fields of characteristic zero, and in residually nilpotent groups.

<span style="font-variant:small-caps;">Acknowledgement.</span> I was prompted to revisit the bounds in \[thm:old\] by a question from Harald Helfgott.

Standard tools {#sec:prelim}
==============

In this section we record various standard results relating to sets of small doubling and approximate groups. This material is likely to be familiar to experts in the subject, who may therefore decide to skip straight to \[sec:details\].

\[lem:slicing\] Let $K,L\ge1$ and let $G$ be a group. Let $A\subset G$ be a $K$-approximate group and $B\subset G$ an $L$-approximate group. Then for every $m,n\ge2$ the set $A^m\cap B^n$ is covered by at most $K^{m-1}L^{n-1}$ left translates of $A^2\cap B^2$. In particular, $A^m\cap B^n$ is a $K^{2m-1}L^{2n-1}$-approximate group.

\[lem:fibre.pigeonhole\] Let $k\in{\mathbb{N}}$. Let $G$ be a group with a subgroup $H$, let $A\subset G$, and suppose that $A$ is contained in a union of $k$ left cosets of $H$. Then $A$ is contained in a union of $k$ left translates of $A^{-1}A\cap H$.

Let $x_1,\ldots,x_m\in A$ be representatives of the left cosets of $H$ containing at least one element of $A$, noting that $m\le k$ by hypothesis. If $a$ is an arbitrary element of $A\cap x_iH$ then there exists $h\in H$ such that $a=x_ih$. It follows that $h=x_i^{-1}a\in A^{-1}A$, and hence $h\in A^{-1}A\cap H$ and $a\in x_i(A^{-1}A\cap H)$.

\[thm:plun\] Let $G$ be an abelian group, and let $A$ be a finite subset of $G$. Suppose that $|A+A|\le K|A|$. Then $|mA-nA|\le K^{m+n}|A|$ for all non-negative integers $m,n$.

\[lem:covering\] Let $A$ and $B$ be finite subsets of some group and suppose that $|AB|/|B|\le K$. Then there exists a subset $X\subset A$ with $|X|\le K$ such that $A\subset XBB^{-1}$.

Let $H$ and $P$ be as given by \[thm:sanders\]. Then we have $$\begin{aligned}
\frac{|A+H+P|}{|H+P|}&\le\exp(O(\log^{O(1)}2K))\frac{|A+H+P|}{|A|}\\
   &\le K^5\exp(O(\log^{O(1)}2K))&\text{(by \cref{thm:plun})}\\
   &\le\exp(O(\log^{O(1)}2K)),\end{aligned}$$ and so \[lem:covering\] gives a set $X\subset A$ of size at most $\exp(O(\log^{O(1)}2K))$ such that $A\subset X+H+2P$. Now $2P$ is also a progression of the same rank as $P$. Moreover, since $H+P\subset 2A-2A$, we have $H+2P\subset 4A-4A$, and hence $|H+2P|\le K^8|A|$ by \[thm:plun\]. This completes the proof.

\[lem:chang\] Let $K,C\ge1$ and $m\in{\mathbb{N}}$. Let $G$ be a group, and suppose that $A\subset G$ is a finite $K$-approximate group. Suppose that $B\subset A^m$ is a set with $|B|\ge|A|/C$. Then there exist $t\ll\log C+m\log K$ and sets $S_1,\ldots,S_t\subset A$ satisfying $|S_i|\le2K$ such that $A\subset S_{t-1}^{-1}\cdots S_1^{-1}B^{-1}BS_1\cdots S_t$.

Let $k\in{\mathbb{N}}$, let $G$ be a group, and let $A$ be a subset of a group. Then a map $\varphi:A\to G$ is a *Freiman $k$-homomorphism*, or simply a *$k$-homomorphism*, if whenever $x_1,\ldots,x_k,y_1,\ldots,y_k\in A$ satisfy $$x_1\cdots x_k=y_1\cdots y_k$$ we have $${\varphi}(x_1)\cdots{\varphi}(x_k)={\varphi}(y_1)\cdots{\varphi}(y_k).$$ If $1\in A$ and ${\varphi}(1)=1$ then we say that ${\varphi}$ is *centred*.

\[lem:fr.hom.ap.grp\] Let $K\ge1$. Let $A$ be a $K$-approximate group, let $G$ be a group. Suppose that ${\varphi}:A\to G$ is a centred Freiman $3$-homomorphism. Then ${\varphi}(A)$ is a $K$-approximate group.

The set ${\varphi}(A)$ contains the identity by definition of a centred Freiman homomorphism. Moreover, for every $a\in A$ we have ${\varphi}(a^{-1}){\varphi}(a){\varphi}(1)={\varphi}(1)^3$, and hence $$\label{eq:centred}
{\varphi}(a^{-1})={\varphi}(a)^{-1},$$ so ${\varphi}(A)$ is symmetric. Finally, by definition there is a set $X$ of size at most $K$ such that $A^2\subset XA$. We may assume that $X$ is minimal satisfying this property, and hence that $X\subset A^3$. For each $x\in X$ there therefore exist elements $\alpha_1(x),\alpha_2(x),\alpha_3(x)\in A$ such that $x=\alpha_1(x)\alpha_2(x)\alpha_3(x)$. Set $Y=\{{\varphi}(\alpha_1(x)){\varphi}(\alpha_2(x)){\varphi}(\alpha_3(x)):x\in X\}$, noting that $|Y|\le K$. We claim that ${\varphi}(A)^2\subset Y{\varphi}(A)$, which will complete the proof. To prove this claim, fix $a_1,a_2\in A$, and let $x\in X$ and $a_3\in A$ be such that $a_1a_2=xa_3$. It follows from that ${\varphi}(a_1){\varphi}(a_2){\varphi}(a_3)^{-1}={\varphi}(\alpha_1(x)){\varphi}(\alpha_2(x)){\varphi}(\alpha_3(x))$, and so $a_1a_2\in Y{\varphi}(A)$ as claimed.

Proof of the main result {#sec:details}
========================

Before we prove \[thm:new.gen\], let us remark that at various points we make the seemingly unnecessary assumption that $K\ge2$. The reason for this is purely notational: it allows us to replace bounds such as $O(\log^{O(1)}2K)$ or $O(K^{O(1)})$ with the slightly more succinct $\log^{O(1)}2K$ or $K^{O(1)}$, respectively. Note that if $K<2$ then a $K$-approximate group is an actual subgroup, in which regime all of our main results become trivial, so we lose nothing in making this assumption.

We start the proof of \[thm:new.gen\] with the following result, a version of which with worse bounds was also central to the original proof of \[thm:old\].

\[prop:key.general\] Let $m>0$ and $s\ge\tilde s\ge2$ be integers, and let $K,\tilde K\ge2$. Let $G$ be an $s$-step nilpotent group generated by a finite $K$-approximate group, and let $\tilde A\subset A^m$ be a $\tilde K$-approximate group that generates an $\tilde s$-step nilpotent subgroup $\tilde G$ of $G$. Then there exist a normal subgroup $N\lhd G$ with $N\subset A^{K^{e^{O(s)}m}}$, an integer $r\le\log^{O(1)}2\tilde K$, and $\tilde K^{O(1)}$-approximate groups $A_0,\ldots,A_r\subset\tilde A^{O(1)}$ such that $$|A_0\cdots A_r|\ge\frac{|\tilde A|}{\exp(\log^{O(1)}2\tilde K)},$$ and such that, writing $\rho:G\to G/N$ for the quotient homomorphism, each group $\langle\rho(A_i)\rangle$ has step less than $\tilde s$.

The main ingredients in the proof of \[prop:key.general\] are the next three results.

\[prop:pre-chang.tor.free\] Let $s\ge2$ and $K\ge2$. Let $G$ be an $s$-step nilpotent group, and write $\pi:G\to G/[G,G]$ for the quotient homomorphism. Suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist an integer $r\le\log^{O(1)}2K$, elements $x_1,\ldots,x_r\in\pi(A^4)$, and a subgroup $H\subset\pi(A^4)$ such that $$\left|\left(A^{18}\cap\pi^{-1}(H)\right)\prod_{i=1}^r\left(A^{24}\cap\pi^{-1}(\langle x_i\rangle)\right)\right|\ge\frac{|A|}{\exp(\log^{O(1)}2K)}.$$

We prove \[prop:pre-chang.tor.free\] shortly.

\[lem:x\[G,G\]\] Let $s\ge2$. Let $G$ be an $s$-step nilpotent group, write $\pi:G\to G/[G,G]$ for the quotient homomorphism, and let $x\in G/[G,G]$. Then the group $\pi^{-1}(\langle x\rangle)$ has step at most $s-1$.

This is implicitly shown in the proofs of [@nilp.frei Propositions 4.2 & 4.3]; it is also proved explicitly in [@book Lemma 6.1.6 (i)].

\[prop:lower.step.in.quotient\] Let $m>0$ and $s\ge\tilde s\ge2$ be integers, and let $K\ge2$. Let $G$ be an $s$-step nilpotent group generated by a finite $K$-approximate group $A$, and let $\tilde G$ be an $\tilde s$-step nilpotent subgroup of $G$. Write $\pi:\tilde G\to\tilde G/[\tilde G,\tilde G]$ for the quotient homomorphism, and suppose that $H\subset\pi(A^m\cap\tilde G)$ is a finite group. Then there is a normal subgroup $N\lhd G$ such that $[\,\pi^{-1}(H),\ldots,\pi^{-1}(H)\,]_{\tilde s}\subset N\subset A^{K^{e^{O(s)}m}}$.

The bounds stated here are more precise than those stated in [@nilp.frei Proposition 7.1], but the bounds claimed here can be read out of the argument there. Alternatively, \[prop:lower.step.in.quotient\] is proved exactly as stated here in [@book Proposition 6.6.2].

Combine Proposition \[prop:pre-chang.tor.free\] with Lemmas \[lem:slicing\] and \[lem:x\[G,G\]\] and \[prop:lower.step.in.quotient\].

Before we prove \[prop:pre-chang.tor.free\] we isolate the following lemma, which is inspired by a lemma of Tao [@tao.product.set Lemma 7.7].

\[lem:splitting\] Let $G$ be a group, let $N\lhd G$ be a normal subgroup, and let $\pi:G\to G/N$ be the quotient homomorphism. Let $A$ be a symmetric subset of $G$, and define a map $\varphi:\pi(A)\to A$ by choosing, for each element $x\in\pi(A)$, an element $\varphi(x)\in A$ such that $\pi(\varphi(x))=x$. Then

1.  \[eq:split.inv\] for every $a\in A$ we have $a\in\left(A^2\cap N\right)\varphi(\pi(a))$; and

2.  \[eq:split.hom\] for every $x,y\in G/N$ with $x,y,xy\in\pi(A)$ we have $\varphi(xy)\in\varphi(x)\varphi(y)\left(A^3\cap N\right)$.

This is essentially just an observation: by definition of $\varphi$ we have $a\varphi(\pi(a))^{-1}\in A^2\cap N$ and $\varphi(y)^{-1}\varphi(x)^{-1}\varphi(xy)\in A^3\cap N$.

\[lem:pullback.large\] Let $G$ be a group, let $N\lhd G$ be a normal subgroup, and let $\pi:G\to G/N$ be the quotient homomorphism. Let $A$ be a finite symmetric subset of $G$, and let $P\subset\pi(A^m)$. Suppose that $|P|\ge c|\pi(A)|$. Then $|\pi^{-1}(P)\cap A^{m+2}|\ge c|A|$.

\[lem:fibre.pigeonhole\] implies that $|N\cap A^2|\ge|A|/|\pi(A)|$, which in turn implies that $|\pi^{-1}(x)\cap A^{m+2}|\ge|A|/|\pi(A)|$ for every $x\in\pi(A^m)$. In particular, $|\pi^{-1}(P)\cap A^{m+2}|\ge|A||P|/|\pi(A)|\ge c|A|$, as desired.

Write $\pi:G\to G/[G,G]$ for the quotient homomorphism, and note that $\pi(A)$ is a finite $K$-approximate subgroup of the abelian group $G/[G,G]$. Theorem \[thm:sanders\] therefore implies that there exists a finite subgroup $H\subset G/[G,G]$, and a progression $P=\{x_1^{\ell_1}\cdots x_r^{\ell_r}:|\ell_i|\le L_i\}$ with $r\le\log^{O(1)}2K$ such that $HP\subset\pi(A^4)$ and $|HP|\ge\exp(-\log^{O(1)}2K)|\pi(A)|$. Lemma \[lem:pullback.large\] then implies that $$\label{eq:pullback.large}
|\pi^{-1}(HP)\cap A^6|\ge\exp(-\log^{O(1)}2K)|A|.$$ Now let $\varphi:\pi(A^6)\to A^6$ be an arbitrary map such that $\pi(\varphi(x))=x$ for every $x\in\pi(A^6)$. Suppose that $a\in\pi^{-1}(HP)\cap A^6$, so that there exist $h\in H$ and $\ell_1,\ldots,\ell_r\in{\mathbb{Z}}$ such that $\pi(a)=hx_1^{\ell_1}\cdots x_r^{\ell_r}$. It follows from \[lem:splitting\] \[eq:split.inv\] that $$\begin{aligned}
a&\in\left(A^{12}\cap[G,G]\right)\varphi(\pi(a))\\
&=\left(A^{12}\cap[G,G]\right)\varphi(hx_1^{\ell_1}\cdots x_r^{\ell_r}),\end{aligned}$$ and hence by repeated application of \[lem:splitting\] \[eq:split.hom\] that $$\begin{aligned}
a&\in\left(A^{12}\cap[G,G]\right)\varphi(h)\prod_{i=1}^r\varphi(x_i^{\ell_i})\left(A^{18}\cap[G,G]\right)\\
  &\subset\left(A^{18}\cap\pi^{-1}(H)\right)\prod_{i=1}^r\left(A^{24}\cap\pi^{-1}(\langle x_i\rangle)\right).\end{aligned}$$ Since $a$ was an arbitrary element of $\pi^{-1}(HP)\cap A^6$, the proposition then follows from .

It is at this point that we diverge from the original proof of \[thm:old\].

\[prop:ind.tor-free.post.chang\] Let $m>0$ and $s\ge\tilde s\ge2$ be integers, and let $K,\tilde K\ge2$. Let $G$ be an $s$-step nilpotent group generated by a finite $K$-approximate group $A$, and let $\tilde A\subset A^m$ be a $\tilde K$-approximate group that generates an $\tilde s$-step nilpotent subgroup $\tilde G$ of $G$. Then there exist a normal subgroup $N\lhd G$ with $N\subset A^{K^{e^{O(s)}m}}$; an integer $r\le\log^{O(1)}2\tilde K$; finite $\tilde K^{O(1)}$-approximate groups $A_1,\ldots,A_r\subset\tilde A^{O(1)}$ such that, writing $\rho:G\to G/N$ for the quotient homomorphism, each group $\langle\rho(A_i)\rangle$ has step less than $\tilde s$; and a set $X\subset\tilde A$ of size at most $\exp(\log^{O(1)}2\tilde K)$ such that $\tilde A\subset XA_1\cdots A_r$.

This is immediate from \[prop:key.general,lem:covering\].

Using \[prop:ind.tor-free.post.chang\] to induct on the step, we arrive at the following result.

\[prop:tor-free.post.induc\] Let $m>0$ and $s\ge\tilde s\ge1$ be integers, and let $K,\tilde K\ge2$. Let $G$ be an $s$-step nilpotent group generated by a finite $K$-approximate group $A$, and let $\tilde A\subset A^m$ be a $\tilde K$-approximate group that generates an $\tilde s$-step nilpotent subgroup $\tilde G$ of $G$. Then there exist integers $r,\ell\le e^{O(\tilde s^2)}\log^{O(\tilde s)}2\tilde K$; a normal subgroup $N\lhd G$ satisfying $$\label{eq:tor-free.post.induc.N}
N\subset A^{e^{O(\tilde s^2)}K^{e^{O(s)}m}\log^{O(\tilde s)}2\tilde K};$$ finite $\tilde K^{e^{O(\tilde s)}}$-approximate groups $A_1,\ldots,A_r\subset\tilde A^{e^{O(\tilde s)}}$ such that, writing $\pi:G\to G/N$ for the quotient homomorphism, each group $\langle\pi(A_i)\rangle$ is abelian; and sets $X_1,\ldots,X_\ell\subset\tilde A^{e^{O(\tilde s)}}$ of size at most $\exp(e^{O(\tilde s)}\log^{O(1)}2\tilde K)$ such that $$\tilde A\subset N\prod\{A_1,\ldots,A_r,X_1,\ldots,X_\ell\},$$ with the product taken in some order.

Here, and throughout this paper, given an ordered set $X=\{x_1,\ldots,x_m\}$ of subsets and/or elements in a group $G$, we write that a product $\Pi$ of the members of $X$ is *equal to $\prod X$ with the product taken in some order* to mean that there is a permutation $\xi\in{\text{\textup{Sym}}}(m)$ such that $\Pi=\prod_{i=1}^m x_{\xi(i)}$. If $Y=\{y_1,\ldots,y_m\}$ is another ordered set of the same number subsets and/or elements of $G$, then we say that products $\prod X$ and $\prod Y$ are *taken in the same order* if $\prod X=\prod_{i=1}^m x_{\xi(i)}$ and $\prod Y=\prod_{i=1}^m y_{\xi(i)}$ for the same permutation $\xi$.

If $\tilde A$ is abelian then the proposition is trivially true with $r=1$, $\ell=0$, $A_1=\tilde A$ and $N=\{1\}$. We may therefore assume that $s\ge\tilde s\ge2$ and, by induction, that the proposition holds for all smaller values of $\tilde s$.

We start by rewriting the part of the statement we are trying to prove as $$N\subset A^{e^{O(\tilde s^2)}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s)}2\tilde K}.$$ This is exactly equivalent to , but writing the bound in this way makes it slightly easier to keep track of through the induction. For the same reason, at various points in the argument we use the trivial observation that any quantity bounded by $O(1)$ is also bounded by $e^{O(1)}$.

Applying Proposition \[prop:ind.tor-free.post.chang\], we obtain a normal subgroup $N_0\lhd G$ with $N_0\subset A^{K^{e^{O(s)}m}}$; an integer $r_0\le\log^{O(1)}2\tilde K$; finite $\tilde K^{e^{O(1)}}$-approximate groups $\tilde A_1,\ldots,\tilde A_{r_0}\subset\tilde A^{O(1)}\subset\tilde A^{e^{O(1)}}\subset A^{e^{O(1)}m}$ such that, writing $\rho:G\to G/N$ for the quotient homomorphism, each group $\langle\rho(\tilde A_i)\rangle$ has step less than $\tilde s$; and a set $X\subset\tilde A$ of size at most $\exp(\log^{O(1)}2\tilde K)$ such that $$\label{eq:induction.step}
\tilde A\subset X\tilde A_1\cdots\tilde A_r.$$ Since $G/N_0$ is generated by the $K$-approximate group $\rho(A)$, we may apply the induction hypothesis to each approximate subgroup $\rho(\tilde A_i)$ of $G/N_0$ to obtain, for each $i=1,\ldots,r_0$, integers $$\begin{aligned}
r_i,\ell_i&\le e^{O((\tilde s-1)^2)}\log^{O(\tilde s-1)}(2\tilde K^{e^{O(1)}})\\
   & \le e^{O(\tilde s(\tilde s-1))}\log^{O(\tilde s-1)}2\tilde K;\end{aligned}$$ a normal subgroup $N_i\lhd G$ containing $N_0$ and satisfying $$\begin{aligned}
N_i&\subset A^{e^{O((\tilde s-1)^2)}K^{e^{O(s)+O(\tilde s-1)}(e^{O(1)}m)}(e^{O(1)}\log2\tilde K)^{O(\tilde s-1)}}N_0\\
  &\subset A^{e^{O(\tilde s(\tilde s-1))}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s-1)}2\tilde K}N_0;\end{aligned}$$ finite $\tilde K^{e^{O(\tilde s)}}$-approximate groups $A_1^{(i)},\ldots,A_{r_i}^{(i)}\subset\tilde A_i^{e^{O(\tilde s-1)}}\subset\tilde A^{e^{O(\tilde s)}}$ such that, writing $\pi_i:G\to G/N_i$ for the quotient homomorphism, each group $\langle\pi_i(A_j^{(i)})\rangle$ is abelian; and sets $X_1^{(i)},\ldots,X_{\ell_i}^{(i)}\subset\tilde A_i^{e^{O(\tilde s-1)}}\subset\tilde A^{e^{O(\tilde s)}}$ satisfying $$\begin{aligned}
|X_j^{(i)}|&\le\exp(e^{O(\tilde s-1)}\log^{O(1)}(2\tilde K^{e^{O(1)}}))\\
   &\le\exp(e^{O(\tilde s)}\log^{O(1)}2\tilde K)\end{aligned}$$ such that $$\label{eq:induction.hyp}
\tilde A_i\subset N_i\prod\{A_1^{(i)},\ldots,A_{r_i}^{(i)},X_1^{(i)},\ldots,X_{\ell_i}^{(i)}\},$$ with the product taken in some order.

Defining $N=N_1\cdots N_{r_0}$, we then have $$\begin{aligned}
N&\subset A^{r_0e^{O(\tilde s(\tilde s-1))}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s-1)}2\tilde K}\cdot N_0\\
   &\subset A^{e^{O(\tilde s(\tilde s-1))}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s)}2\tilde K}\cdot N_0\\
   &\subset A^{e^{O(\tilde s(\tilde s-1))}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s)}2\tilde K}\cdot A^{K^{e^{O(s)}m}}\\
   &\subset A^{e^{O(\tilde s^2)}K^{e^{O(s)+O(\tilde s)}m}\log^{O(\tilde s)}2\tilde K}.\end{aligned}$$ Moreover, and imply that $$\tilde A\subset N\prod\{A_1^{(1)},\ldots,A_{r_1}^{(1)},\ldots,A_1^{(r_0)},\ldots,A_{r_{r_0}}^{(r_0)},X_1^{(1)},\ldots,X_{\ell_1}^{(1)},\ldots,X_1^{(r_0)},\ldots,X_{\ell_{r_0}}^{(r_0)},X\}$$ with the product taken in some order. We also have $$\begin{aligned}
(r_1+\ldots+r_{r_0})\,,\,(\ell_1+\ldots+\ell_{r_0}+1)&\le r_0e^{O(\tilde s(\tilde s-1))}\log^{O(\tilde s-1)}2\tilde K+1\\
   &\le e^{O(\tilde s(\tilde s-1))}\log^{O(\tilde s)}2\tilde K+1\\
   &\le e^{O(\tilde s^2)}\log^{O(\tilde s)}2\tilde K.\end{aligned}$$ Finally, since every $\langle\pi_i(A_j^{(i)})\rangle$ is abelian, every $\langle\pi(A_j^{(i)})\rangle$ certainly is, so the proof is complete.

\[prop:grp.in.normal\] Let $s\in{\mathbb{N}}$ and $K\ge1$. Let $G$ be an $s$-step nilpotent group generated by a finite $K$-approximate group $A$. Let $H\subset A^m$ be a subgroup of $G$. Then there exists a normal subgroup $N$ of $G$ such that $H\subset N\subset A^{K^{e^{O(s)}m}}$.

The bounds stated in [@nilp.frei Proposition 7.3] are less explicit than the ones claimed here; as usual, the bounds claimed here can be read out of the argument there, or alternatively found explicitly in [@book Corollary 6.5.2].

\[prop:prod.of.progs.and.small\] Let $s\in{\mathbb{N}}$ and $K\ge2$. Let $G$ be an $s$-step nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then there exist $k,\ell\le e^{O(s^2)}\log^{O(s)}2K$, ordered progressions $P_1,\ldots,P_k\subset A^{e^{O(s)}}$ of rank at most $e^{O(s)}\log^{O(1)}2K$, sets $X_1,\ldots,X_\ell\subset A^{e^{O(s)}}$ of size at most $\exp(e^{O(s)}\log^{O(1)}2K)$, and a subgroup $H<G$ normalised by $A$ satisfying $H\subset A^{K^{e^{O(s)}}}$ such that $$A\subset H\prod\{P_1,\ldots,P_k,X_1,\ldots,X_\ell\},$$ with the product taken in some order.

We may assume that $A$ generates $G$. Applying \[prop:tor-free.post.induc\] with $\tilde A=A$, we obtain integers $r,t\le e^{O(s^2)}\log^{O(s)}2K$; a normal subgroup $N\lhd G$ satisfying $N\subset A^{K^{e^{O(s)}}}$; finite $K^{e^{O(s)}}$-approximate groups $A_1,\ldots,A_r\subset A^{e^{O(s)}}$ such that, writing $\pi:G\to G/N$ for the quotient homomorphism, each group $\langle\pi(A_i)\rangle$ is abelian; and sets $X_1,\ldots,X_t\subset A^{e^{O(s)}}$ of size at most $\exp(e^{O(s)}\log^{O(1)}2K)$ such that $$A\subset N\prod\{A_1,\ldots,A_r,X_1,\ldots,X_t\}$$ with the product taken in some order.

For each $i=1,\ldots,r$, apply \[cor:sanders\] to the set $\pi(A_i)$ to obtain a subgroup $H_i\subset A_i^8N\subset A^{e^{O(s)}}N$ containing $N$, an ordered progression $P_i\subset A_i^8\subset A^{e^{O(s)}}$ of rank at most $e^{O(s)}\log^{O(1)}2K$, and a set $Y_i\subset A_i\subset A^{e^{O(s)}}$ of size at most $\exp(e^{O(s)}\log^{O(1)}2K)$, such that $A_i\subset Y_iH_iP_i$. Since $G/N$ is gererated by the $K$-approximate group $\pi(A)$, applying Proposition \[prop:grp.in.normal\] in $G/N$ implies that for each $i$ there is a normal subgroup $N_i\lhd G$ such that $H_i\subset N_i\subset A^{K^{e^{O(s)}}}N$. The subgroup $H=N_1\cdots N_r$ is then normal in $G$, and satisfies $$\begin{aligned}
H&\subset A^{rK^{e^{O(s)}}}N\\
   &\subset A^{K^{e^{O(s)}}}\end{aligned}$$ and $$A\subset H\prod\{P_1,\ldots,P_r,Y_1,\ldots,Y_r,X_1,\ldots,X_t\},$$ with the product taken in some order. This completes the proof.

Note that if $K<2$ then $A$ is a finite subgroup of $G$, and so the theorem holds with $A=H$. We may therefore assume that $K\ge2$. Let $k,\ell\le e^{O(s^2)}\log^{O(s)}2K$, $$\label{eq:P.S.contained}
P_1,\ldots,P_k,X_1,\ldots,X_\ell\subset A^{e^{O(s)}},$$ and $H\subset A^{K^{e^{O(s)}}}$ be as coming from \[prop:prod.of.progs.and.small\], noting in particular that $$\label{eq:prod.order}
AH\subset H\prod\{P_1,\ldots,P_k,X_1,\ldots,X_\ell\}.$$ The pigeonhole principle therefore implies that there exist elements $u_1,\ldots,u_\ell$ with $u_i\in X_i$ such that the product $\prod\{P_1,\ldots,P_k,u_1,\ldots,u_\ell\}$, taken in the same order as the product in , satisfies $$\begin{aligned}
\left|H\prod\{P_1,\ldots,P_k,u_1,\ldots,u_\ell\}\right|&\ge\frac{|AH|}{|X_1|\cdots|X_\ell|}\\
    &\ge\frac{|AH|}{\exp(e^{O(s)}\log^{O(1)}2K)^\ell}\\
    &\ge\frac{|AH|}{\exp(e^{O(s^2)}\log^{O(s)}2K)}.\end{aligned}$$ In particular, setting $Q_i=\{u_i^{-1},1,u_i\}$ for $i=1,\ldots,\ell$, we have $$\left|H\prod\{P_1,\ldots,P_k,Q_1,\ldots,Q_\ell\}\right|\ge\frac{|AH|}{\exp(e^{O(s^2)}\log^{O(s)}2K)},$$ with the product again taken in the same order.

Now $\prod\{P_1,\ldots,P_k,Q_1,\ldots,Q_\ell\}$ is an ordered progression, say $P_{\text{\textup{ord}}}(x;L)$. The ranks of the progressions $P_i$ coming from \[prop:prod.of.progs.and.small\] are at most $e^{O(s)}\log^{O(1)}2K$, and hence that the rank of $P_{\text{\textup{ord}}}(x;L)$ is at most $ke^{O(s)}\log^{O(1)}2K+\ell$, which is at most $e^{O(s^2)}\log^{O(s)}2K$. Furthermore, the containment implies that $$\begin{aligned}
P_{\text{\textup{ord}}}(x;L)&\subset A^{(k+\ell)e^{O(s)}}\\
   &\subset A^{e^{O(s^2)}\log^{O(s)}2K},\end{aligned}$$ and \[prop:nilprog.equiv\] therefore implies that $$P_{\text{\textup{ord}}}(x;L)\subset P_{\text{\textup{nil}}}(x;L)\subset\overline P(x;L)\subset A^{e^{O(s^3)}\log^{O(s^2)}2K}.$$ This comletes the proof.

\[rem:poly.bound\]The polynomial bound on the product set of $A$ required to contain $H$ in \[thm:new.gen\] comes from our applications of Propositions \[prop:lower.step.in.quotient\] and \[prop:grp.in.normal\]. These propositions are themselves both applications of the same result, namely [@nilp.frei Proposition 7.2], and so the polynomial bound in \[thm:new.gen\] can be traced to this result. It appears that a new idea would be required to improve this result in such a way as to remove the polynomial bound from \[thm:new.gen\].

Covering arguments {#sec:covering}
==================

In this section we use covering arguments to prove \[cor:ruzsa,cor:chang.ag\]. \[cor:ruzsa\] follows from \[thm:new.gen\] and a straightforward application of Ruzsa’s covering lemma, as follows.

We may assume that $A$ generates $G$. Let $H$ and $P=P_{\text{\textup{ord}}}(x;L)$ be as given by \[thm:new.gen\], noting that $H\lhd G$. Let $\pi:G\to G/H$ be the quotient homomorphism, and note that $$\begin{aligned}
\frac{|\pi(AP)|}{|\pi(P)|}&=\frac{|APH|}{|PH|}\\
   &\le\exp(e^{O(s^2)}\log^{O(s)}2K)\frac{|APH|}{|AH|}\\
   &=\exp(e^{O(s^2)}\log^{O(s)}2K)\frac{|\pi(AP)|}{|\pi(A)|}\\
   &\le\exp(e^{O(s^2)}\log^{O(s)}2K),\end{aligned}$$ the last inequality coming from the fact that $\pi(A)$ is a $K$-approximate group and $\pi(AP)\subset\pi(A)^{e^{O(s^2)}\log^{O(s)}2K}$. Applying \[lem:covering\] in the quotient $G/H$ therefore gives a set $X\subset A$ of size at most $\exp(e^{O(s^2)}\log^{O(s)}K)$ such that $A\subset XHPP^{-1}$. Now $PP^{-1}\subset A^{e^{O(s^2)}\log^{O(s)}2K}$ is an ordered progression of rank double that of $P$, which is still at most $e^{O(s^2)}\log^{O(s)}2K$. The corollary therefore follows from \[prop:nilprog.equiv\].

We may assume that $A$ generates $G$. Let $H$ and $P_0=P_{\text{\textup{ord}}}(x;L)$ be as given by \[thm:new.gen\], noting that $H\lhd G$. Let $\pi:G\to G/H$ be the quotient homomorphism, noting that $$\frac{|\pi(P_0)|}{|\pi(A)|}=\frac{|P_0H|}{|AH|}\ge\exp(-e^{O(s^2)}\log^{O(s)}2K).$$ Applying and \[lem:chang\] in the quotient $G/H$, we therefore have $$t\le e^{O(s^2)}\log^{O(s)}2K$$ and sets $S_1,\ldots,S_t\subset A$ with $|S_i|\le2K$ such that $$A\subset S_{t-1}^{-1}\cdots S_1^{-1}P_0^{-1}P_0S_1\cdots S_tH.$$ Enumerating the elements of each $S_i$ as $s_{1,i},\ldots,s_{r_i,i}$ and writing $$Q_i=\{s_{1,i}^{\epsilon_1}\cdots s_{r_i,i}^{\epsilon_{r_i}}:\epsilon_j,\in\{-1,0,1\}\},$$ the set $P=Q_{t-1}\cdots Q_1P_0^{-1}P_0Q_1\cdots Q_t$ is therefore an ordered progression of rank at most $$e^{O(s^2)}K\log^{O(s)}2K$$ satisfying $$A\subset PH\subset A^{4Kt+e^{O(s^2)}\log^{O(s)}2K}H\subset A^{e^{O(s^2)}K\log^{O(s)}2K}H.$$ The corollary therefore follows from \[prop:nilprog.equiv\].

Applications to non-nilpotent groups {#sec:non-nilp}
====================================

In this section we use our results to improve the bounds on the ranks of the coset nilprogressions appearing in various Freiman-type theorems in non-nilpotent groups. As in \[sec:details\], at various points we separate the trivial case $K<2$ from the meaningful case $K\ge2$ so as to avoid the need for multiplicative constants.

Our first corollary improves an earlier result of the author for residually nilpotent groups [@resid Corollary 1.4], and partially improves on \[cor:ruzsa\] for large values of $s$.

\[cor:resid\] Let $K\ge1$. Let $G$ be a residually nilpotent group, and suppose that $A\subset G$ is a finite $K$-approximate group. Then $A$ is contained in the union of at most $\exp(K^{O(1)})$ left translates of a coset nilprogression $P\subset A^{O_K(1)}$ of rank at most $\exp(O(K^{12}))$ and step at most $K^6$.

This compares with the bound of $\exp(\exp(K^{O(1)}))$ on the rank of $P$ obtained previously by the author using \[thm:old\].

It follows from [@resid Theorem 1.2] that there exist subgroups $H\lhd N<G$ such that $H\subset A^{O_K(1)}$, such that $N/H$ is nilpotent of step at most $K^6$, and such that $A$ is contained in a union of at most $\exp(K^{O(1))}$ left cosets of $N$. \[lem:fibre.pigeonhole\] then implies that $A$ is contained in a union of at most $\exp(K^{O(1))}$ left translates of $A^2\cap N$, which is a $K^3$-approximate group by \[lem:slicing\]. The desired result therefore follows from applying \[cor:chang.ag\] to the image of $A^2\cap N$ in $N/H$.

\[cor:resid\] gives a better rank bound than \[cor:ruzsa\] if the step of the ambient group is greater than $K^6$. It gives a better bound on number of translates of $P$ required to cover $A$ as soon as the step is logarithmic in $K$.

Our next corollary applies to linear groups over fields of prime order, and arises from combining \[cor:ruzsa\] with a result of Gill, Helfgott, Pyber and Szabó [@gill-helf Theorem 3].

\[cor:ghps\] Let $n\in{\mathbb{N}}$ and $K\ge1$, and let $p$ be a prime. Suppose that $A\subset GL_n({\mathbb{F}}_p)$ is a finite $K$-approximate group. Then there is a coset nilprogression $P\subset A^{K^{O_n(1)}}$ of rank at most $e^{O(n^2)}\log^{O(n)}2K$ and step at most $n$ such that $A$ is contained in the union of at most $\exp(K^{O_n(1)})$ left translates of $P$.

This compares with the bound of $K^{O_n(1)}$ on the rank of $P$ obtained by Gill, Helfgott, Pyber and Szabó using \[thm:old\].

If $K<2$ then $A$ is a finite subgroup and the corollary is trivial, so we may assume that $K\ge2$. It follows from [@gill-helf Theorem 3] that there exist subgroups $H\lhd N<GL_n({\mathbb{F}}_p)$ such that $H\subset A^{K^{O_n(1)}}$, such that $N/H$ is nilpotent of step at most $n$, and such that $A$ is contained in a union of at most $\exp(K^{O_n(1))}$ left cosets of $N$. \[lem:fibre.pigeonhole\] then implies that $A$ is contained in a union of at most $\exp(K^{O_n(1))}$ left translates of $A^2\cap N$, which is a $K^3$-approximate group by \[lem:slicing\]. The desired result therefore follows from applying \[cor:ruzsa\] to the image of $A^2\cap N$ in $N/H$.

One can obtain a similar result in characteristic zero by combining \[cor:chang.ag\] with a result of Breuillard, Green and Tao [@bgt.lin Theorem 2.5], as follows.

\[cor:bgt\] Let $n\in{\mathbb{N}}$ and $K\ge1$, and let $\Bbbk$ be a field of characterisic zero. Suppose that $A\subset GL_n(\Bbbk)$ is a finite $K$-approximate group. Then there is a coset nilprogression $P_1\subset A^{K^{O_n(1)}}$ of rank at most $e^{O(n^2)}\log^{O(n)}2K$ such that $A$ is contained in the union of at most $\exp(\log^{O_n(1)}2K)$ left translates of $P_1$, and a coset nilprogression $P_2\subset A^{K^{O_n(1)}}$ of rank at most $e^{O(n^2)}K^3\log^{O(n)}2K$ such that $A$ is contained in the union of at most $K^{O_n(1)}$ left translates of $P_2$.

If $K<2$ then $A$ is a finite subgroup and the corollary is trivial, so we may assume that $K\ge2$. It then follows from [@bgt.lin Theorem 2.5] that $A$ is contained in a union of at most $K^{O_n(1)}$ left cosets of a nilpotent subgroup $N$ of $GL_n(\Bbbk)$ of step at most $n-1$, and hence from \[lem:fibre.pigeonhole\] that $A$ is contained in a union of at most $K^{O_n(1)}$ left translates of $A^2\cap N$. \[lem:slicing\] implies that $A^2\cap N$ is a $K^3$-approximate group, and so the existence of $P_1$ follows from \[cor:ruzsa\] and the existence of $P_2$ follows from \[cor:chang.ag\].

In the special case in which $\Bbbk={\mathbb{C}}$, an argument of Breuillard and Green shows that the coset nilprogression appearing in \[cor:bgt\] can be replaced with simply a nilprogression, as follows.

\[cor:bg\] Let $n\in{\mathbb{N}}$ and $K\ge1$. Suppose that $A\subset GL_n({\mathbb{C}})$ is a finite $K$-approximate group. Then there is a nilprogression $P_1\subset A^{e^{O(n^3)}\log^{O(n^2)}2K}$ of rank at most $e^{O(n^2)}\log^{O(n)}2K$ such that $A$ is contained in a union of at most $\exp(e^{O(n^2)}\log^{O(n)}2K)$ left translates of $P_1$, and a nilprogression $P_2\subset A^{{e^{O(n^3)}K^{3n+3}\log^{O(n^2)}2K}}$ of rank at most $e^{O(n^2)}K^3\log^{O(n)}2K$ such that $A$ is contained in a union of at most $K^{O_n(1)}$ left translates of $P_2$.

For the convenience of the reader we reproduce the Breuillard–Green argument giving \[cor:bg\]. The argument is facilitated by the following two general results about complex linear groups, in which we write ${\text{\textup{Upp}}}_n({\mathbb{C}})$ to mean the group of upper-triangular $n\times n$ complex matrices.

\[thm:malcev\] Let $n\in{\mathbb{N}}$, and suppose that $G<GL_n({\mathbb{C}})$ is a soluble subgroup. Then $G$ contains a normal subgroup $U$ of index at most $O_n(1)$ that is conjugate to a subgroup of ${\text{\textup{Upp}}}_n({\mathbb{C}})$.

\[prop:red.tf\] Let $n,s\in{\mathbb{N}}$, and let $N$ be an $s$-step nilpotent subgroup of ${\text{\textup{Upp}}}_n({\mathbb{C}})$. Then there is a torsion-free $s$-step nilpotent group $\Gamma$ such that $N$ embeds into ${\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma$.

Although [@bg.sol Proposition 3.2] does not include the statement that $\Gamma$ has the same step as $N$, one can easily obtain this by replacing ${\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma$ with $({\mathbb{R}}^n/{\mathbb{Z}}^n)N$.

We follow part of the proof of [@bg.sol Corollary 1.5]. It follows from [@bgt.lin Theorem 2.5] that $A$ is contained in a union of at most $K^{O_n(1)}$ left cosets of a nilpotent subgroup $N$ of $GL_n({\mathbb{C}})$ of step at most $n-1$. By \[thm:malcev\] we may assume that $N\subset{\text{\textup{Upp}}}_n({\mathbb{C}})$, and then by \[prop:red.tf\] we may assume that there exists a torsion-free $(n-1)$-step nilpotent group $\Gamma$ such that $N={\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma$. \[lem:fibre.pigeonhole\] then implies that $A$ is contained in a union of at most $K^{O_n(1)}$ left translates of $A^2\cap({\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma)$.

Set $B=A^2\cap\left(\left[-\frac{1}{8},\frac{1}{8}\right]^n\times\Gamma\right)$. The set $\left[-\frac{1}{16},\frac{1}{16}\right]^n\times\Gamma$ is a $2^n$-approximate group; since $(\left[-\frac{1}{16},\frac{1}{16}\right]^n\times\Gamma)^2=\left[-\frac{1}{8},\frac{1}{8}\right]^n\times\Gamma$ and $(\left[-\frac{1}{16},\frac{1}{16}\right]^n\times\Gamma)^8={\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma$, \[lem:slicing\] therefore implies that $B$ is a $2^{3n}K^3$-approximate group, and that $A^2\cap({\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma)$ is contained in a union of at most $2^{7n}K$ left translates of $B$.

Let ${\varphi}:{\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma\to\left(-\frac{1}{2},\frac{1}{2}\right]^n\times\Gamma\subset{\mathbb{R}}^n\times\Gamma$ be the obvious lift. The restriction of ${\varphi}$ to $\left[-\frac{1}{8},\frac{1}{8}\right]^n\times\Gamma$ is a Freiman $3$-homomorphism, so \[lem:fr.hom.ap.grp\] implies that ${\varphi}(B)$ is a $2^{3n}K^3$-approximate subgroup of the torsion-free $s$-step nilpotent group ${\mathbb{R}}^n\times\Gamma$. \[cor:ruzsa,cor:chang.ag\] therefore imply the existence of a nilprogression $Q_1\subset{\varphi}(B)^{e^{O(n^3)}\log^{O(n^2)}2K}$ of rank at most $e^{O(n^2)}\log^{O(n)}2K$ such that ${\varphi}(B)$ is contained in a union of at most $\exp(e^{O(n^2)}\log^{O(n)}2K)$ left translates of $Q_1$, and a nilprogression $Q_2\subset{\varphi}(B)^{{e^{O(n^3)}K^{3n+3}\log^{O(n^2)}2K}}$ of rank at most $e^{O(n^2)}K^3\log^{O(n)}2K$ such that ${\varphi}(B)\subset Q_2$.

Write $\pi:{\mathbb{R}}^n\times\Gamma\to{\mathbb{R}}^n/{\mathbb{Z}}^n\times\Gamma$ for the quotient homomorphism, and note that $\pi({\varphi}(B))=B$, so that $A$ is contained in a union of at most $K^{O_n(1)}$ left translates of $\pi({\varphi}(B))$. The corollary therefore follows from setting $P_1=\pi(Q_1)$ and $P_2=\pi(Q_2)$.

The reason for tradeoff between the rank of $P$ and the number of translates of it required to cover $A$ in \[cor:bgt,cor:bg\] is that the bound on the number of cosets of $N$ needed to cover $A$ in [@bgt.lin Theorem 2.5] is stronger than the bound on the number of translates of the coset nilprogression needed to cover $A$ in \[cor:ruzsa\]. This tradeoff does not occur in \[cor:ghps\], as the corresponding bounds in [@gill-helf Theorem 3] are weaker.

[10]{} E. Breuillard and B. J. Green. Approximate groups, I: The torsion-free nilpotent case, *J. Inst. Math. Jussieu* **10**(1) (2011), 37–57. E. Breuillard and B. J. Green. Approximate groups, II: the solvable linear case, *Q. J. Math.* **62**(3) (2011), 513–521. E. Breuillard, B. J. Green and T. C. Tao. Approximate subgroups of linear groups, *Geom. Funct. Anal.* **21**(4) (2011), 774–819. E. Breuillard, B. J. Green and T. C. Tao. The structure of approximate groups, *Publ. Math. IHES.* **116**(1) (2012), 115–221. E. Breuillard, B. J. Green and T. C. Tao. Small doubling in groups, *Proc. of the Erdős centenery conference* (2013); arXiv:1301.7718. E. Breuillard and M. C. H. Tointon. Nilprogressions and groups with moderate growth, *Adv. Math.* **289** (2016), 1008–1055. M. C. Chang. A polynomial bound in Freiman’s theorem, *Duke Math. J.* **113**(3) (2002), 399–419. G. A. Freiman. Foundations of a structural theory of set addition, *Translations of Mathematical Monographs* **37**, Amer. Math. Soc., Providence, RI (1973). Translated from the 1966 Russian version, published by Kazan Gos. Ped. Inst.. N. Gill and H. A. Helfgott. Growth in solvable subgroups of $GL_r({\mathbb{Z}}/p{\mathbb{Z}})$, *Math. Ann.* **360**(1) (2014) 157–208. B. J. Green. Approximate groups and their applications: work of Bourgain, Gamburd, Helfgott and Sarnak, *Current events bulletin of the AMS* (2010), arXiv:0911.3354. B. J. Green. Approximate algebraic structure, *Proc. ICM 2014* vol. 1, 341–367. B. J. Green and I. Z. Ruzsa. Freiman’s theorem in an arbitrary abelian group, *J. Lond. Math. Soc.* **75**(1) (2007), 163–175. M. Hall. *The theory of groups*, Amer. Math. Soc./Chelsea, Providence, RI (1999). H. A. Helfgott. Growth in groups: ideas and perspectives, *Bull. Amer. Math. Soc.* **52** (2015), 357–413. A. I. Mal’cev. On certain classes of infinite soluble groups, *Mat. Sb.* **28** (1951), 567–588 (in Russian), *Amer. Math. Soc. Transl.* (2) **45** (1956), 1–21. G. Petridis. New proofs of Plünnecke-type estimates for product sets in groups, *Combinatorica* **32**(6) (2012), 721–733. I. Z. Ruzsa. An analog of Freiman’s theorem in groups, Structure theory of set addition, *Astérisque* **258** (1999), 323–326. T. Sanders. On the Bogolyubov–Ruzsa lemma, *Anal. PDE* **5**(3) (2012), 627–655. T. Sanders. The structure theory of set addition revisited, *Bull. Amer. Math. Soc.* **50** (2013), 93–127. T. Schoen. Near optimal bounds in Freiman’s theorem, *Duke Math. J.* **158** (2011), 1–12. T. C. Tao. Product set estimates for non-commutative groups, *Combinatorica* **28**(5) (2008), 547–594. T. C. Tao. Inverse theorems for sets and measures of polynomial growth, *Q. J. Math.* **68**(1) (2017), 13–57. R. Tessera and M. C. H. Tointon. Properness of nilprogressions and the persistence of polynomial growth of given degree, *Discrete Anal.* 2018:17, 38 pp. M. C. H. Tointon. Freiman’s theorem in an arbitrary nilpotent group, *Proc. London Math. Soc.* **109** (2014), 318–352. M. C. H. Tointon. Approximate subgroups of residually nilpotent groups, *Math. Ann.* **374** (2019), 499–515. M. C. H. Tointon. Raconte-moi…les groupes approximatifs, *Gaz. Math.* **160** (2019), 53–59. M. C. H. Tointon. *Introduction to approximate groups*, London Mathematical Society Student Texts **94**, Cambridge University Press, Cambridge (2020). B. A. F. Wehrfritz. *Infinite linear groups*, Springer-Verlag, Berlin (1973).
