Weikun He
email: weikun.he@mail.huji.ac.il

Nicolas De Saxcé
email: desaxce@math.univ-paris13.fr

Sum-product for real Lie groups

Sum-product for real Lie groups

Weikun He, Nicolas de Saxcé

Introduction

Throughout this paper, G will denote a connected real Lie group, endowed with a left-invariant Riemmanian metric. For x ∈ G and ρ > 0, we denote by B G (x, ρ) the ball of center x and radius ρ in G. For A ⊂ G and ρ > 0, A (ρ) stands for the ρ-neighborhood of A and N (A, ρ) stands for the covering number of A by ρ-balls, i.e.

N (A, ρ) = min N ∈ N | ∃ x 1 , . . . , x N ∈ G, A ⊂ N i=1 B G (x i , ρ) .
The same notation is used for other metric spaces.

Sum-product theorem in representations of Lie groups

In the first part of this paper, we study the sum-product phenomenon in representations of Lie groups. We shall work with some linear representation of G over some finite-dimensional real vector space V , endowed with some norm. We shall also refer to representations of G as G-modules. For A ⊂ G, X ⊂ V and s ≥ 1, we denote by A, X s the set of elements in V that can be obtained as combinations of sums, differences and products of at most s elements from A and X.

Note that the distance on G induces a natural distance on each of its quotients. Let N G be a closed normal subgroup. We denote by π G/N : G → G/N the canonical projection. Then there is a unique distance on G/N satisfying ∀x, y ∈ G, d(π G/N (x), π G/N (y)) = d(x -1 y, N ). Throughout this paper, all quotients G/N will be endowed with this distance.

Following [START_REF] De | A product theorem in simple Lie groups[END_REF], we say that a subset A ⊂ G is ρ-away from closed connected subgroups for some parameter ρ > 0 if for any proper closed connected subgroup H < G, there exists a ∈ A with d(a, H) > ρ. Similarly, we say that a subset X ⊂ V is ρ-away from submodules if for any proper G-submodule W < V , there exists x ∈ X with d(x, W ) > ρ.

We say that a G-module V is in P(G) if the trivial representation does not appear as a simple quotient in the Jordan-Hölder decomposition of G -see Definition 2.1.

Theorem 1.1 (Sum-product theorem in representations of class P). Let G be a connected real Lie group and V ∈ P(G). There exists a neighborhood U of the identity in G such that, for every ε 0 , κ > 0, there exist s ≥ 1 and ε > 0 such that the following holds for any δ > 0 sufficiently small. Assume A ⊂ U and X ⊂ B V (0, 1) satisfy:

(i) For any proper closed connected normal subgroup N G, ∀ρ ≥ δ, N (π G/N (A), ρ) ≥ δ ε ρ -κ ;

(ii) A is δ ε -away from closed connected subgroups;

(iii) X is δ ε -away from submodules.

Then, B V (0, δ ε0 ) ⊂ A, X (δ) s . This is a bounded generation statement which can be viewed as a generalization of previous sum-product results in rings. For example, applying to G = R * acting on V = R, one recovers a version Bourgain's discretized sum-product theorem [START_REF] Bourgain | On the Erdős-Volkmann and Katz-Tao ring conjectures[END_REF][START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]. Note that this is not a new proof of Bourgain's theorem as the latter is used as an ingredient in the proof of Theorem 1.1.

In Section 2, Theorem 1.1 will be proved in a more precise form where the conditions (i) and (ii) can be slightly relaxed. See Theorem 2.3.

Product theorem in perfect Lie groups

In the second part of this paper, we use Theorem 1.1 to derive a product theorem in perfect Lie groups. For subsets A, B ⊂ G of a Lie group G, we denote by AB their product set, i.e. AB = {ab | a ∈ A, b ∈ B}.

For k ≥ 2, we denote by A k the k-fold product set of A with itself, A • • • A.

To avoid confusion with Cartesian products between sets, we write A ×k for the Cartesian power A × • • • × A.

Recall that a Lie group is perfect if its Lie algebra g is perfect, i.e. satisfies [g, g] = g. Theorem 1.2 (Product theorem in perfect Lie groups). Let G be a connected perfect Lie group. There exists a neighborhood U of the identity in G such that given κ > 0, there exists ε > 0 such that the following holds for δ > 0 sufficiently small. Let A be a subset of U such that: (i) N (A, δ) ≤ δ -dim G+κ ;

(ii) for any proper closed connected normal subgroup N G, ∀ρ ≥ δ, N (π G/N (A), ρ) ≥ δ ε ρ -κ ;

(iii) A is δ ε -away from closed connected subgroups in G.

Then N (AAA, δ) ≥ δ -ε N (A, δ).

For G = SU(2), the above theorem was proved by Bourgain-Gamburd [START_REF] Bourgain | On the spectral gap for finitelygenerated subgroups of SU(2)[END_REF], and for a general simple Lie group by the second author [START_REF] De | A product theorem in simple Lie groups[END_REF], borrowing many ideas from the work of Bourgain and Gamburd [START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] on the spectral gap property in SU(d).

It is not difficult to see that the assumption of perfectness is optimal for such a product theorem to hold, in the following sense.

Proposition 1.3. Let G be a simply connected Lie group which is not perfect with Lie algebra g. Write d = dim g -dim[g, g]. For any neighborhood U of the identity in G, for any κ ∈ (0, 1) and for any δ > 0 small enough, there exists

A ⊂ U such that (i) N (A, δ) ≈ U δ -dim G+d(1-κ) ; (ii) for any proper closed connected normal subgroup N G, ∀ρ ≥ δ, N (π G/N (A), ρ) U ρ -κ ; (iii) A is 1 O U (1) -away from closed connected subgroups in G. but N (AAA, δ) U N (A, δ).
Note that in a closely related setting, Salehi Golsefidy and Varjú [START_REF] Salehi Golsefidy | Expansion in perfect groups[END_REF] have already observed that perfectness is a sufficient and necessary condition for an expansion result to hold. In fact, at different places, our arguments share some conceptual similarities with the recent work of Salehi Golsefidy [START_REF] Salehi | Super-approximation, I: p-adic semisimple case[END_REF][START_REF] Salehi | Super-approximation, II: the p-adic and bounded powers of square-free integers cases[END_REF] on superapproximation. Also, these examples of approximate subgroups can be seen as discretized analogues of measurable subgroups of intermediate dimension whose existence is known in abelian Lie groups [START_REF] Erdős | Additive Gruppen mit vorgegebener Hausdorffscher Dimension[END_REF] and solvable Lie groups [START_REF] De | Subgroups of fractional dimension in nilpotent or solvable Lie groups[END_REF].

We shall prove Theorem 1.2 and Proposition 1.3 in Section 3.

Applications

We conclude this introduction by mentioning several applications to Theorems 1.1 and 1.2 above. The first is that the spectral gap property discovered by Bourgain and Gamburd [START_REF] Bourgain | On the spectral gap for finitelygenerated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] in the setting of SU(d), d ≥ 2 generalizes to all compact semisimple Lie groups.

Theorem 1.4. Let G be a compact connected semisimple Lie group, with Lie algebra g, and write L 2 0 (G) for the space of zero-mean square-integrable functions on G. Let µ be a probability measure on G whose support generates a dense subgroup in G. Assume moreover that in some basis for g, for every g ∈ Supp µ, the matrix of Ad g has algebraic entries. Then the convolution operator

T µ : L 2 0 (G) → L 2 0 (G) f → f * µ satisfies T µ < 1.
The local spectral gap property introduced by Boutonnet, Ioana and Salehi Golsefidy in [START_REF] Boutonnet | Local spectral gap in simple Lie groups and applications[END_REF] for non-compact Lie groups can also be generalized to a general connected perfect Lie group, but in order to keep statements as elementary as possible, we do not make this precise here.

Originally, discretized expansion statements were introduced by Katz and Tao [START_REF] Hawk | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] and used by Bourgain [START_REF] Bourgain | On the Erdős-Volkmann and Katz-Tao ring conjectures[END_REF] to study Hausdorff dimensions of sum-sets and product-sets in R and give a quantitative solution to the Erdős-Volkmann conjecture: If A is any Borel measurable subset of R with dim H A ∈ (0, 1), then dim H A + AA > dim H A. The theorems proven here have similar consequences on the Haudorff dimension of sum and product sets in semi-simple algebras or perfect Lie groups. In particular, it should be possible to generalize the results of the second author presented in [START_REF] De | Borelian subgroups of simple Lie groups[END_REF] to the setting of perfect Lie groups; we hope to address these matters in another paper.

Another nice application of Theorem 1.1 is the very recent work of Li [START_REF] Li | Discretized sum-product and Fourier decay in R n[END_REF][START_REF] Li | Fourier decay, renewal theorem and spectral gaps for random walks on split semisimple lie groups[END_REF] on the regularity of the Furstenberg measure associated to a random walk on a semisimple Lie group.

Finally, our results could be used to construct new family of expanders, in the spirit of the works of Bourgain-Yehudayoff [START_REF] Bourgain | Expansion in SL 2 (R) and monotone expanders[END_REF] or Vigolo [START_REF] Vigolo | Measure expanding actions, expanders and warped cones[END_REF].

Sum-product theorem in representations of G

The goal of this section is to prove Theorem 1.1 from the introduction. In fact, our proof will yield a slightly more precise version, see Theorem 2.3.

Representations without trivial simple quotients

We now define the class of representations to which our theorem will apply, and gather some elementary properties. Then, we state the refined version of Theorem 1.1 which will be proved here, Theorem 2.3. Definition 2.1. Let G be a connected Lie group. We let P(G) denote the class of finite-dimensional linear representations V of G such that there exists a sequence

{0} = V 0 < V 1 < • • • < V = V of subrepresentations of V such that, for each i = 0, . . . , -1, the quotient representation V i+1 /V i is non-trivial and irreducible.
Equivalently, V is in P(G) if the trivial representation does not appear as a simple quotient in a Jordan-Hölder decomposition of V . This property, of course, does not depend on the choice of the Jordan-Hölder decomposition. We now list some elementary properties of representations in P(G). Proposition 2.2. Let V be a representation of a connected Lie group G.

(i) If W is a subrepresentation of V , then V belongs to P(G) if and only if both W and V /W belong to P(G).

(ii) If H is a closed subgroup of G and V ∈ P(H) as a representation of H, then V ∈ P(G).

(iii) Let H be a normal subgroup of G. If the representation G → GL(V ) factors through G/H, then V ∈ P(G/H) as a representation of G/H if and only if V ∈ P(G) as a representation of G.

Proof. Indeed, (i) follows from the fact that the set of simple quotients of the Jordan-Hölder decomposition of V is the union of those of W and those of V /W . For (ii), note that a Jordan-Hölder sequence of G-submodules in V can be refined to a Jordan-Hölder sequence of H-submodules, and that if there is a trivial quotient in the first sequence there must be also one in the refined sequence. Finally, (iii) is clear, since Jordan-Hölder decompositions of V into G-modules coïncide with Jordan-Hölder decompositions into G/H-modules.

Remark 1. The class P(G) is the smallest class of finite-dimensional G-modules that contains all non-trivial irreducible representations of G and is closed under extension (i.e., if W and V are in P(G), and 0

→ W → V → V → 0 is a short exact sequence of G-modules, then V is in P(G)).
Example 1.

• If a representation V contains the trivial representation, then it is not in P(G). Similarly, if V admits the trivial representation as a quotient, then it is not in P(G).

• Let n be a positive integer. The representation of G = R * + on R n given by g • v = gv (scalar multiplication) is in P(G).

• The adjoint representation of a semisimple Lie group G is in P(G).

Throughout this article, we shall consider representations of G as normed vector spaces: By normed G-module, we mean a G-module endowed with a norm which makes the underlying linear space a normed vector space.

Whenever V is a normed vector space, and W ≤ V is a linear subspace, we shall alway consider on W the norm induced by the norm on V , and on quotient space V = V /W the norm given by the formula

∀v ∈ V, π(v) = d(v, W ),
where π : V → V is the canonical projection. Finally, we endow the space of linear endomorphisms End(V ) with the associated operator norm.

Let ρ ∈ (0, 1 2 ) be a parameter and V a normed G-module, we say that a subset X ⊂ V is ρ-away from submodules if for every proper submodule W < V , there exists x ∈ X such that d(x, W ) ≥ ρ. Similarily, a subset A ⊂ G is said to be ρ-away from closed connected subgroups if for every proper closed connected subgroup H, there exists a ∈ A such that d(a, H) ≥ ρ. Finally, a subset A ⊂ G is said to be ρ-away from identity components of proper stabilizers if for any subspace W ⊂ V which is not a G-submodule, there exists

a ∈ A such that d(a, (Stab G W ) • ) ≥ ρ, where (Stab G W ) • denotes the identity component of the stabilizer Stab G W of W in G.
We shall prove the following.

Theorem 2.3 (Sum-product in representations of class P). Let G be a connected real Lie group and V a normed G-module. There exists a neighborhood U of the identity in G such that, for every ε 0 , κ > 0, there exist s ≥ 1 and ε > 0 such that the following holds for any δ > 0 sufficiently small. Assume A ⊂ U and X ⊂ B V (0, 1) satisfy:

(i) There is a Jordan-Hölder sequence 0 = V 0 < . . . < V = V such that for every i = 0, . . . , -1,

∀ρ ≥ δ, N (p Vi+1/Vi (A), ρ) ≥ δ ε ρ -κ , where p Vi+1/Vi : G → GL(V i+1 /V i ) denotes the representation of G on V i+1 /V i ;
(ii) A is δ ε -away from identity components of proper stabilizers;

(iii) X is δ ε -away from submodules.

Then,

B V (0, δ ε0 ) ⊂ A, X s + B V (0, δ).
Note that the assumption (i) implies that V is of class P(G). The proof goes by induction on the length of V (i.e. the length of any Jordan-Hölder decomposition of V ). We shall prove the base case, where V is a non-trivial irreducible representation, in the next subsection. The induction step will then be carried out in Subsection 2.3.

Irreducible representations

In the case V is an irreducible representation of G, the above theorem is a variant of [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF]Theorem 3]. For clarity, we restate our theorem in this particular case. Then, we shall explain how to derive it from the first author's sum-product theorem in simple algebras [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF]Theorem 2].

Theorem 2.4 (Base case: irreducible representations). Let G be a connected real Lie group and π V : G → GL(V ) a non-trivial irreducible representation. There exists a neighborhood U of the identity in G such that, for every ε 0 , κ > 0, there exist s ≥ 1 and ε > 0 such that the following holds for any δ > 0 sufficiently small. Assume A ⊂ U and X ⊂ B V (0, 1) satisfy:

(i) For every ρ ≥ δ, N (π V (A), ρ) ≥ δ ε ρ -κ ; (ii) A is δ ε -away from identity components of proper stabilizers; (iii) There exists v ∈ X such that v ≥ δ ε . Then, B V (0, δ ε0 ) ⊂ A, X s + B V (0, δ).
The proof of this theorem is based on Proposition 2.5 below, a sum-product statement in matrix representations, which is essentially contained in [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF]. Below, A denotes a subset of End(V ), for some real vector space V , and A s denotes the set of elements in End(V ) that can be obtained as combinations of sums and products of at most s elements in A. If V is a real vector space, if A is a subset of End V , and if ρ ∈ (0, 1 2 ) is a parameter, we say that A acts ρ-irreducibly on V if for every non-trivial proper linear subspace W < V , there exists v ∈ B W (0, 1) and a ∈ A such that d(a • v, W ) ≥ ρ. Proposition 2.5 (Sum-product in irreducible representations). Let V be a finite-dimensional normed vector space. Given ε 0 , κ > 0, there exist s ≥ 1 and ε > 0 such that the following holds. Let A ⊂ B End(V ) (0, δ -ε ) be a subset of End V and v ∈ V a vector. Assume that

(i) For every ρ ≥ δ, N (A, ρ) ≥ δ ε ρ -κ ; (ii) A acts δ ε -irreducibly on V ; (iii) δ ε ≤ v ≤ δ -ε . Then B V (0, δ ε0 ) ⊂ A s • v + B V (0, δ).
Proof. Given ε 1 > 0, it follows from [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF]Proposition 31] that there exists c > 0 such that, provided ε > 0 is small enough, there exists a δ -O(ε) -bi-Lipschitz linear bijection f :

V → K n , where K is R, C or the quaternions H, n is dim V dim K
and K n is endowed with its usual L 2 norm, and a scale δ

1 with δ ≤ δ 1 ≤ δ c such that f Af -1 ⊂ Mat n (K) + B(0, δ 1 )
and such that for every proper real subalgebra

F < End(K n ), ∃a ∈ A : d(f af -1 , F ) ≥ δ ε1 1 .
Choosing ε 1 small enough in terms of ε 0 and κ, we may then apply [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF]Theorem 5] to conclude that, provided ε > 0 is sufficiently small, for some integer s,

B Matn(K) (0, δ ε0 1 ) ⊂ f A s f -1 + B Matn(K) (0, δ 1 )
. Therefore, without loss of generality, we may assume that V = K n and

B Matn(K) (0, δ ε0 1 ) ⊂ A + B Matn(K) (0, δ 1 ). (1)
We can further assume that v = 1. Then

B V (0, δ ε0 1 ) ⊂ A • v + B V (0, δ 1 )
. In other words, the conclusion of the proposition holds at scale δ 1 . It remains to bring the scale back to δ. To do this, we note that from (1), we have in particular δ 1 2

1 id ∈ A + B Matn(K) (0, δ 1 ).
Hence, starting from (1), we may multiply both sides by δ

1 2
1 id to obtain

B V (0, δ 1 ) ⊂ B V (0, δ ε0+ 1 2 1 ) ⊂ A 2 • v + B V (0, 2δ 3
1 ), and iterating this procedure, we get a sequence of integers

s 2 = 1, s 3 = 2, s 4 , . . . such that for any k ≥ 2, B V (0, s k δ k 2 1 ) ⊂ A s k+1 • v + B V (0, s k+1 δ k+1 2

1

).

Choose k > 2 c so that s k δ k 2 1 ≤ δ.
Combining all these inclusions, we find, for

s = s 2 + • • • + s k , B V (0, δ ε0 1 ) ⊂ A s • v + B V (0, δ), which proves the proposition.
The above proposition readily implies Theorem 2.4.

Proof of Theorem 2.4. It suffices to apply Proposition 2.5 to the set π V (A) ⊂ End(V ). By the assumption on A, conditions (i) and (iii) of the proposition are satisfied for the set π V (A). That condition (ii) is also satisfied is a consequence of Lemma 2.6 below.

Lemma 2.6. Let 0 < ρ < 1 2 be a parameter. Let π : G → GL(V ) be a nontrivial irreducible representation. There is a neighborhood U of 1 in G such that if A ⊂ U is ρ-away from identity components of proper stabilizers then π(A) acts ρ Oπ(1) -irreducibly on V .

It might be interesting to understand how the implied constant in O π (1) depends on π and G, especially if one wants to have explicit constants in Theorems 1.1 and 1.2. Our proof does not provide any insight on this matter since we rely on an application of Łojasiewicz's inequality and effectivizing Łojasiewicz's inequality can be difficult and involves mathematics far away from the scope of the present paper (see for example [START_REF] Kollár | An effective Łojasiewicz inequality for real polynomials[END_REF] and references therein).

The proof of this lemma is an application of Łojasiewicz's inequality (which we recall below as Theorem 2.8). First, it is convenient to reduce to the case where A is finite. This reduction is the subject of the next lemma. Given a representation π : G → GL(V ) of G, a subset A ⊂ G and a parameter ρ ∈ (0, 1 2 ), we say that A is ρ-away from proper stabilizers if for any linear subspace W of V which is not a G-submodule, there exists an element a in A whose distance to the stabilizer Stab G W is at least ρ. Lemma 2.7. Let 0 < ρ < 1 2 be a parameter. Let π : G → GL(V ) be a representation. There is a neighborhood U of 1 in G such that if A ⊂ U is ρ-away from identity components of proper stabilizers then A is ρ Oπ(1) -away from proper stabilizers. In fact, A contains a subset of cardinality at most dim G which is ρ Oπ(1) -away from proper stabilizers.

Proof. The representation π differentiates to a representation of the Lie algebra g of G, which we denote by T 1 π : g → End(V ). The stabilizer of W in g

Stab g W = {x ∈ g | T 1 π(x)W ⊂ W }
is the Lie algebra of Stab G W . In particular, its image under the exponential map is contained in (Stab G W ) • , the identity component of Stab G W . We may assume that exp induces a diffeomorphism from U to its image, and denote the inverse map by log. Say that log A is ρ-away from proper stabilizers in g if for any linear subspace W < V which is not a G-submodule, there exists a ∈ A such that d(log a, Stab g W ) ≥ ρ.

We claim that there is a neighborhood U of 1 in G such that if A ⊂ U is ρaway from identity components of proper stabilizers then log A is ρ C -away from proper stabilizers in g and conversely if log A is ρ-away from proper stabilizers then A is ρ C -away from proper stabilizers. Let us prove this claim. Let x ∈ g. From the identity π(e x ) = e T1π(x) , we can express T 1 π(x) as an absolutely convergent series

T 1 π(x) = - n≥1 1 n id V -π(e x )
n whenever π(e x ) -id V < 1. Therefore, if e x ∈ Stab G W is such that the above series converges, then x ∈ Stab g W . It follows that there is r > 0 depending only on π such that

B G (1, r) ∩ Stab G W ⊂ exp(Stab g W ). Let U = B G (1, r 2
). Then for any g ∈ U and any proper linear subspace W ,

1 C d(g, (Stab G W ) • ) ≤ d(log g, Stab g W ) ≤ Cd(g, Stab G W )
where C > 0 is some constant depending only on the the representation. This proves our claim, and the first part of the lemma. For the second part, one can reproduce the argument in [22, Lemma 2.5] to show that if log A is ρ-away from proper stabilizers then log A contains a subset of cardinality at most dim g which is ρ O dim(g) (1) -away from stabilizers.

Remark 2. Note that in the above lemma, the neighborhood U depends on the representation π, and not only on G. This is readily seen by considering

G = R, V = C R 2 , and π(x)v = e inx v, n ∈ N.
Let us recall Łojasiewicz's inequality [16, Théorème 2, page 62] before we proceed to prove Lemma 2.6.

Theorem 2.8 (Łojasiewicz's inequality). Let M be a real analytic manifold endowed with a Riemannian distance d and let f : M → R be a real analytic map. If K is a compact subset of M , then there is C > 0 depending on K and f such that for all x ∈ K,

|f (x)| ≥ C -1 min(1, d(x, Z)) C where Z = {x ∈ M | f (x) = 0}.
Proof of Lemma 2.6. Let U be the neighborhood given by Lemma 2.7. On account of this lemma we may assume that A is finite of cardinality n ≤ dim G and ρ-away from proper stabilizers.

Let 0 < k < dim(V ) and consider the real-analytic map f :

G n ×Grass(k, V ) → R defined by f (g 1 , . . . , g n ; W ) = n i=1 B W (0,1) d(g i • w, W ) 2 dw.
The integration is with respect to the k-dimensional Lebesgue measure on each W ∈ Grass(k, V ). To see that this map is real-analytic, remark that we can trivialize locally the tautological bundle over Grass(k, V ), i.e. for any W 0 ∈ Grass(k, V ) there is a neighborhood U of W 0 in Grass(k, V ) and a map ϕ : U × R k → V such that for all W ∈ Grass(k, V ), the partial map ϕ(W, •) : R k → V is linear and have W as image. Moreover, we can choose ϕ to be real-analytic and such that ϕ(W, •) : R k → W is an isometry for the Euclidean structures, for any W ∈ Grass(k, V ). Thus, for all W ∈ Grass(k, V ) and all i = 1, . . . , n,

B W (0,1) d(g i • w, W ) 2 dw = B R k (0,1) (g i • ϕ(W, v)) ∧ ϕ(W, e 1 ) ∧ • • • ∧ ϕ(W, e k ) 2 dv
where (e 1 , . . . , e k ) is the standard basis of R k . The righthand side is obviously real analytic. The zero set of f is exactly

Z = {(g, W ) ∈ G n × Grass(k, V ) | ∀i, g i ∈ Stab G W }.
By Łojasiewicz's inequality (Theorem 2.8) applied on Ū n × Grass(k, V ), there is a constant C > 0 such that for any (g,

W ) ∈ U n × Grass(k, V ), f (g, W ) ≥ 1 C d (g, W ), Z C .
Assuming that A does not act 1 C ρ C -irreducibly on V , we can find W ∈ Grass(k, V ) such that for all a ∈ A and all w ∈ B W (0, 1), π(a)w

∈ W + B V (0, 1 C ρ C ). So f (a 1 , . . . , a n , W ) ≤ 1
C ρ C , and by the inequality above there exists W ∈ Grass(k, V ) such that for all a ∈ A, d(a, Stab G W ) ≤ ρ, so that A is not ρ-away from proper stabilizers.

Induction step

The core of the induction step in the proof of Theorem 2.3 is the following lemma. It is a quantitative discretized version of the following elementary fact: let V be a G-module, and

V 1 , X two submodules of V ; if π : V → V /V 1 maps X onto V /V 1 and if X ∩ V 1 = {0}, then V = X ⊕ V 1 .
Once more, the proof relies on Łojasiewicz's inequality. Lemma 2.9. Let G be a connected Lie group and V a normed G-module. There exist a neighborhood U of the identity in G and a constant C ≥ 1 such that for any parameters 0 < η < τ < 1, the following holds when δ is sufficiently small. Let V 1 be a proper submodule of V and π : V → V /V 1 the canonical projection. Let A ⊂ U and X ⊂ B V (0, 1) and assume that

(i) A, X 3 ∩ V (δ) 1 ⊂ B V (0, δ Cτ ), (ii) π(X) = B V /V1 (0, δ η ),
(iii) A is δ τ -away from identity components of proper stabilizers.

Then there exists a submodule W < V such that:

(a) The restriction π |W : W → V /V 1 is 3δ -η -bi-Lipschitz; (b) B W (0, δ η ) ⊂ X (δ τ ) and X ⊂ W (δ τ ) .
Proof. For convenience, we write V = V /V 1 . On account of Lemma 2.7, which gives us the neighborhood U , we may assume that A is finite of cardinality n ≤ dim(G) and is δ C1τ -away from proper stabilizers, where C 1 ≥ 2 is a constant depending only on V . Shrinking again the neighborhood U if necessary, we can ensure that the action on V of any element in A is 2-bi-Lipschitz.

Assumption (ii) allows us to pick a section σ : B V (0, δ η ) → X of the projection π, i.e. for any y ∈ B V (0, δ η ),

π • σ(y) = y.
The choice of such σ is arbitrary. In fact, thanks to assumption (i), different choices only differ by at most δ Cτ . Indeed, for any x ∈ X, we have x-σ(π(x)) ∈ (X -X) ∩ V 1 and therefore, by assumption (i),

x -σ(π(x)) ≤ δ Cτ .

(

) 2
Again from assumption (i), it follows that σ is almost a morphism of G-modules, in the sense that for all y, z ∈ B V (0, δ η ) and all a ∈ A,

σ(y) ≤ δ Cτ if y ∈ B V (0, δ); (3)
σ(y) + σ(z) -σ(y + z) ≤ δ Cτ if y + z ∈ B V (0, δ η ); (4)
a • σ(y) -σ(a • y) ≤ δ Cτ if a • y ∈ B V (0, δ η ). (5)
Indeed, we have, respectively, σ(y)

∈ X ∩ V (δ) 1 , σ(y) + σ(z) -σ(y + z) ∈ 3X ∩ V 1 and a • σ(y) -σ(a • y) ∈ (A • X -X) ∩ V 1 .
In particular, ( 3) and ( 4) says that σ is almost additive; by Lemma 2.10 below, σ is close to a genuine linear map. More precisely, there exists a linear section ϕ :

V → V of π (i.e. π • ϕ = Id V ) such that for all y ∈ B V (0, δ η ), ϕ(y) -σ(y) ≤ δ (C-1)τ , (6)
provided δ is small enough. From the linearity of ϕ, the fact that X ⊂ B V (0, 1), and ( 2), ( 5) and ( 6), we obtain that for all y ∈ V , all a ∈ A and all x ∈ X, ϕ(y) ≤ 2δ -η y ; a • ϕ(y) -ϕ(a • y) ≤ δ (C-3)τ y ;

x -ϕ(π(x)) ≤ δ (C-2)τ .

Let W 0 be the image subspace of ϕ. From the above, it follows that:

the restriction π |W0 : W 0 → V is 2δ -η -bi-Lipschitz; (7)
X ⊂ W 0 + B V (0, δ (C-2)τ ); (8)
B W0 (0, δ η /2) ⊂ ϕ(B V (0, δ η )) ⊂ X + B V (0, δ (C-1)τ ); (9) ∀a ∈ A, ∀w ∈ B W0 (0, 1), d(a • w, W 0 ) ≤ δ (C-3)τ . (10)
The inequality [START_REF] Salehi Golsefidy | Expansion in perfect groups[END_REF] says that W 0 is almost invariant under the action of A. We now use Łojasiewicz's inequality to show that it is close to a G-submodule. Let a 1 , . . . , a n be the elements of A and write a = (a 1 , . . . , a n ). Consider the real-analytic function on G ×n × Grass(dim(V ), V ) defined by

f (g 1 , . . . , g n ; W ) = n i=1 B W (0,1) d(g i • w, W ) 2 dw.
From [START_REF] Salehi Golsefidy | Expansion in perfect groups[END_REF] follows f (a, W 0 ) ≤ δ (2C-7)τ , provided δ is small enough. By Łojasiewicz's inequality (Theorem 2.8) applied to the compact set Ū ×d ×Grass(dim(V ), V ), there exists a constant C 2 depending only on the representation V such that for all g = (g 1 , . . . , g n ) ∈ U ×n and W ∈ Grass(dim(V ), V ),

f (g, W ) ≥ 1 C 2 d((g, W ), Z) C2 ,
where Z is the zero set of f . Therefore, there exists b = (b 1 , . . . , b n ) ∈ G ×n and W ∈ Grass(dim(V ), V ) such that f (b, W ) = 0 and

d((a, W 0 ), (b, W )) ≤ δ C1τ , provided 2C -7 ≥ (C 1 + 1)C 2 .
The equality f (b, W ) = 0 exactly means that each b i belongs to the stabilizer Stab G W , and hence

A ⊂ (Stab G W ) (δ C 1 τ )
But A is δ C1τ -away from proper stabilizers, hence W must be a G-submodule.

Finally, conclusions (a) and (b) follow from ( 7), ( 8), ( 9) and the fact that W is δ C1τ -close to W 0 .

In the above proof, we made use of the following elementary lemma, a discretized version of the fact that any continuous additive map between two vector spaces is automatically linear. Lemma 2.10 (Almost additive maps). Let 0 < δ < ρ 1 < ρ 2 ≤ 1 be parameters. Let V and V be finite-dimensional normed vector spaces. If σ :

B V (0, ρ 2 ) → V satisfies (i) σ(B V (0, δ)) ⊂ B V (0, ρ 1 ) and (ii) for all x, y ∈ B V (0, ρ 2 ), if x + y ∈ B V (0, ρ 2 ) then σ(x) + σ(y) -σ(x + y) ∈ B V (0, ρ 1 ).
Then there is a linear map ϕ : V → V such that for all x ∈ B V (0, ρ 2 ), σ(x) -ϕ(x)

V (-log δ + 1)ρ 1 .

Moreover, if there are linear maps π : V → V and ψ : V → V such that π • σ = ψ on B V (0, ρ 2 ), then we may also ensure that π • ϕ = ψ on V .

Proof. We first consider the special case where ρ 2 = 1 and V = R. In this case define ϕ : R → V to be the unique linear map such that ϕ(1) = σ(1). From assumption (ii), it follows that

∀x ∈ [0, 1 2 ], 2σ(x) -σ(2x) ≤ ρ 1 .
Using this and a simple induction, we prove that

∀n ∈ N, σ(2 -n ) -ϕ(2 -n ) ≤ ρ 1 . (11)
Let N be the integer such that 2 -N ≤ δ < 2 -N +1 . It follows from [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF] and

assumption (i) that ϕ(2 -N ) ≤ 2ρ 1 (12)
For any x ∈ [0, 1], let (x 1 , . . . , x N ) ∈ {0, 1} N be the N first digits in its binary expansion, i.e. for some r ∈ [0, δ], x = N n=1 x n 2 -n + r. Then by assumption (ii), [START_REF] He | Discretized sum-product estimates in matrix algebras[END_REF] and [START_REF] Hawk | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF],

σ(x) -ϕ(x) ≤ N n=1 x n σ(2 -n ) -ϕ(2 -n ) + σ(r) + 2 N r ϕ(2 -N ) + N ρ 1 ≤ (2N + 5)ρ 1 . Consequently, σ(-x) -ϕ(-x) ≤ ϕ(x) -σ(x) + σ(-x) + σ(x) -σ(0) + σ(0) ≤ (2N + 7)ρ 1 .
This proves the lemma in the case V = R and ρ 2 = 1. For general normed vector space V , in the case ρ 2 = 1, pick a basis (u 1 , . . . , u d ) consisting of vectors of unit length then apply the special case to each partial function σ i : t → σ(tu i ), i = 1, . . . , d. This yields linear maps ϕ 1 , . . . , ϕ d : R → V , and we define ϕ :

V → V by ϕ(t 1 u 1 + • • • + t d u d ) = ϕ 1 (t 1 ) + • • • + ϕ d (t d ).
Then by (ii), we have the desired inequality for any vector in

B V (0, 1) ∩ ([-1, 1]u 1 + • • • + [-1, 1]u d ). This domain contains a ball B V (0, 1 k )
where k ∈ N depends only on V and the choice of the basis. We conclude by using k times the almost additivity (ii).

The general case ρ 2 ≤ 1 follows from the case ρ 2 = 1, by considering the map σ : V → V defined by σ (x) = σ(ρ 2 x).

The moreover part is clear from the proof.

We are now ready to prove Theorem 2.3. The main idea is to use induction on the length of the module. Note that among the assumptions of Theorem 2.3, (ii) is preserved by passing to any submodule or any quotient of V and (iii) is preserved by passing to any quotient. Finally, (i) passes to the quotient V /V 1 of V by the first submodule V 1 in the Jordan-Hölder decomposition. Thus by the induction hypothesis, it is easy to produce a large ball in V /V 1 . Then it can be proved (this is done in the third step of the proof below) that we can produce a large vector in V 1 and hence a large ball in V 1 by the base case. Then a technical difficulty arises : a large ball in V /V 1 and a large ball in V 1 does not add up to a ball in V . To deal with this difficulty we need to produce the large ball in V /V 1 using only vectors of controlled length (this is done in the first step in the proof below). Another technical difficulty is in the third step where we want to produce vector in V 1 of length ≥ δ ε2 for any given ε 2 > 0. The idea is that, otherwise we could apply Lemma 2.9 to conclude that X is trapped in a submodule, which would contradict assumption ((iii)).

Proof of Theorem 2.3. The proof goes by induction on the length of the module V . The base case = 1, where V is a non-trivial irreducible representation, corresponds to Theorem 2.4, and is proved above. Assume that the result holds for all representations of length less than ≥ 2, let V ∈ P(G) be a representation of length , and suppose A ⊂ G and X ⊂ V satisfy conditions (i)-(ii)-(iii) of the theorem, for some small ε > 0. Let 0 = V 0 < . . . < V = V be the Jordan-Hölder sequence given by assumption (i). Write V = V /V 1 and denote by π V : V → V the projection. Then the module V has length -1 and as noted above, the conditions in Theorem 2.3 are satisfied for A acting on π V (X) ⊂ V . First step: We first prove that there exists ε 1 > 0 and s 1 ≥ 1 depending on V , ε 0 and κ such that

B V (0, δ ε0 ) ⊂ π V ( A, X s1 ∩ B(0, δ ε1 )) + B V (0, δ).
Let ε 1 ∈ (0, ε 0 ) be a small parameter, whose precise value will be specified at the end of this step. By applying the induction hypothesis to V , whose length is at most -1, and replacing X by A, X s , we may assume that B V (0, δ ε1 ) ⊂ π V (X) (δ) . Cover X with δ -O(ε1) balls of radius δ 2ε1 , pick a ball B such that N (π V (B ∩ X), δ) is maximal, and translate it back to the origin to get N (π V (X ), δ) ≥ δ -dim(V )+O(ε1) , with X = (X -X) ∩ B V (0, δ 2ε1 ). This lower bound ensures that π V (X ) is δ O(ε1) -away from proper linear subspaces in V . The induction hypothesis, applied to the subset π V (X ) ⊂ V , with acting set A, yields the desired inclusion provided that ε 1 is small enough. Second step: Assuming X (δ) ∩ V 1 contains a large vector. Let s 2 , ε 2 > 0 be the quantities given by Theorem 2.4 applied to the representation V 1 , with constants κ, ε 1 . We may choose s 2 and ε 2 uniformly over all choices for V 1 ; indeed, up to a (dim V )-bi-Lipschitz isomorphism of G-modules, there are only finitely many choices for V 1 . And assume that there exists v ∈ X (δ) ∩ V 1 with v ≥ δ ε2 . Then, using the base case for the action of G on the irreducible module V 1 , we find that

B V1 (0, δ ε1 ) ⊂ A, X (δ) s2 + B V (0, δ). ( 13
)
Now let z ∈ B V (0, δ ε0 ). By the first step, we may find y ∈ A, X s1 ∩ B V (0, δ ε1 ) and t ∈ V 1 such that z = y + t + O(δ). Necessarily, t < 2δ ε1 , so that by ( 13), t ∈ A, X 2s2 + O(δ). All in all, setting s = s 1 + O s1 (s 2 ), we find

B V (0, δ ε0 ) ⊂ A, X s + B V (0, O s1,s2 (δ)).
This finishes the proof of the theorem in this case. Third step: Finally, we prove that there exists s 3 ≥ 1 depending on V , ε 0 and κ such that A, X

s3 ∩ V 1 always contains a vector of length at least δ ε2 , which allows to conclude, using the second step.

Let C be the constant given by Lemma 2.9. Let 0 < ε 3 < ε2 C be a parameter whose value will be chosen later according to ε 2 . Let 0 < ε 4 < ε 3 be a parameter whose value will be chosen later according to ε 3 . Using the induction hypothesis for the representation V with ε 4 and κ, and replacing A, X

s by X, we may assume without loss of generality that

B V (0, δ ε4 ) ⊂ π V (X). (14)
Either A, X 3 ∩ V (δ) 1 contains a vector of length ≥ δ ε2 , in which case we are done or A, X 3 ∩ V (δ) 1 ⊂ B V (0, δ ε2 ). In the latter case, Lemma 2.9 applied with τ = ε2 C and η = ε 4 gives a submodule W < V such that the restriction of π V to W is 3δ -ε4 -bi-Lipschitz and

B W (0, 1 2 δ ε4 ) ⊂ X (δ1) (15)
where

δ 1 = δ ε 2
C . Now we apply the base case, Theorem 2.4, to the non-trivial irreducible representation V /W with ε 3 and κ. Observe that π

V |W being 3δ -ε4 - bi-Lipschitz implies that π V /W |V1 : V 1 → V /W is 4δ -ε4 -bi-Lipschitz. Hence, for the projections p V /W : G → End(V /W ) and p V1 : G → End(V 1 ), we have ∀ρ ≥ δ, N (p V /W (A), ρ) ≥ δ O(ε4) N (p V1 (A), ρ) ≥ δ O(ε4)+ε ρ κ .
Therefore, provided ε 4 and ε are small enough in terms of V 1 , ε 3 and κ, Theorem 2.4 yields some constant s ≥ 1 depending only on V /W , κ and ε 3 such that

B V /W (0, δ ε3 ) ⊂ π V /W ( A, X s ) + B V /W (0, δ).
Together with inclusion [START_REF] Li | Fourier decay, renewal theorem and spectral gaps for random walks on split semisimple lie groups[END_REF], this implies that

N A, X s + X, δ 1 (δ -1 1 δ ε3 ) dim V /W (δ -1 1 δ ε4 ) dim W ≥ δ -dim V 1 δ O(ε3) .
Cutting A, X s+1 into cylinders of axis V 1 and diameter δ ε3 and picking the part with largest size, we see that

N ( A, X 2s+2 ∩ V (δ ε 3 ) 1 , δ 1 ) ≥ δ -dim V 1 δ O(ε3) , which ensures that X := A, X 2s+2 ∩ V (δ ε 3 ) 1 is δ O(ε3)
-away from proper linear subspaces and a fortiori from submodules. Remembering ( 14), we know that

π V (X ) = B V (0, δ ε3 ).
At this stage apply Lemma 2.9 to the set X with τ = ε2

C and η = ε 3 . If ε 3 is chosen sufficiently small compared to ε 2 , conclusion (b) fails while all assumptions except (i) are satisfied. So there must v ∈ A, X 3 ∩ V (δ) 1 with v > δ ε2 . This concludes the proof of the theorem.

A product theorem for perfect Lie groups

The goal of this section is to use Theorem 2.3 to prove Theorem 1.2. More precisely, we prove the following essentially equivalent version of Theorem 1.2, which is a bounded generation statement. Theorem 3.1 (Product theorem in perfect Lie groups). Let G be a connected perfect Lie group. There exists a neighborhood U of the identity in G such that given κ > 0 and ε 0 > 0, there exist ε > 0 and s ≥ 1 such that the following holds for δ > 0 sufficiently small. Let A be a subset of U such that:

(i) For any projection π i : G → G/H i to a simple factor, ∀ρ ≥ δ, N (π i (A), ρ) ≥ δ ε ρ -κ ; (ii) A is δ ε -away from closed connected subgroups in G. Then B G (1, δ ε0 ) ⊂ (A ∪ {1} ∪ A -1 ) s B G (1, δ).
Theorem 1.2 follows immediately from Theorem 3.1 in combination with Ruzsa-type inequality [START_REF] Tao | Product set estimates for non-commutative groups[END_REF]Theorem 6.8].

The proof of Theorem 3.1 goes as follows. We shall first prove the special case where the radical of our perfect Lie group G is abelian. In this case, the adjoint representation of G belongs to P(G), as we shall see in Lemma 3.4 below. So Theorem 2.3 applies and shows that we can produce in the Lie algebra g of G a large ball using addition and the adjoint action of G: B g (0, δ ε0 ) ⊂ A, log A (δ) s . Then we want to exponentiate this inclusion to the level of the group G. For that, we use the Campbell-Hausdorff formula, which allows us to approximate sums in g by products in G with any desired precision; this is the content of Lemma 3.6. Finally, to deduce the general case from the special case, we shall use an induction on the nilpotency class of the radical of G.

adjoint representation belongs to P(G/R). By Proposition 2.2(iii) , g/r is of class P as a representation of G.

On the other hand, r is totally reducible under the action of the semisimple group S = G/R, and moreover,

r = [s, r],
because g is perfect and r abelian. This implies that r is a representation of class P for S, and therefore for G by Proposition 2.2 (iii).

Remark 3. If G is not perfect, then g/[g, g] is non-zero, and G acts trivially on g/[g, g], so that the adjoint representation does not belong to P(G).

Remark 4. It is not true in general that the adjoint representation of a perfect connected Lie group is of class P. Indeed, there exist perfect Lie algebras with non-trivial centers. For instance, let F 2,2 denote the free 2-nilpotent Lie algebra over 2 generators x, y. It is the Lie algebra of the Heisenberg group H 3 (R). The action of SL(2, R) on F 2,2 by linear substitution integrates to an action of SL(2, R) on H 3 (R) by group automorphisms. This allows us the define the Lie group G = SL(2, R) H 3 (R). Its Lie algebra g = sl(2, R) F 2,2 is perfect. However, the adjoint representation of G is not of class P, because G acts trivially on the center of g, generated by [x, y].

Abelian extensions of semi-simple groups

Here, we prove Theorem 3.1 in the case where the Lie algebra of G can be written as a semi-direct product g = s r, with r abelian. We shall see in 3.3 that the general case follows from this one.

We fix a connected perfect Lie group G with Lie algebra g = s r, where s is semi-simple and r is an abelian ideal. To prove Theorem 3.1 in this case, the idea is to apply Theorem 2.3 to the adjoint representation of G on its Lie algebra, and then to use the Campbell-Hausdorff formula. Before that, we note that condition (i) in Theorem 3.1 automatically implies non-concentration for the image of A under any non-trivial group homomorphism. Lemma 3.5. Let G be a perfect connected Lie group. Given a non-trivial homomorphism ϕ : G → H to some connected Lie group H, there exists a neighborhood U of the identity in G such that the following holds. Let ε > 0 and κ > 0 be parameters and let A ⊂ U be a subset satisfying condition (i) of Theorem 3.1. Then ∀ρ ≥ δ, N (ϕ(A), ρ) ϕ δ ε ρ -κ .

Proof. The isomorphism G/ ker ϕ → ϕ(G) is bi-Lipschitz when restricted to compact neighborhoods. Hence without loss of generality, we may assume that H = G/ ker ϕ. Since ker ϕ is closed, there exists a neighborhood U of the identity in G, such that ∀x, y, d(x -1 y, ker ϕ) = d(x -1 y, (ker ϕ) • ). This allows us to further assume that ker ϕ is connected.

Let n be a maximal proper ideal of g containing the Lie algebra of ker ϕ. By Lemma 3.3, n is exactly the kernel of the projection of g to one of its simple factors. It follows n is the Lie algebra of a proper closed normal subgroup N G, with G/N one of the simple factors of G. We deduce the desired estimate from condition (i) of Theorem 3.1 by using the fact that G/ ker ϕ → G/N is 1-Lipschitz.

Proof of Theorem 3.1, in the case where r is abelian. In this proof, implied constants in Landau and Vinogradov notations depend on G and on the parameter κ.

By Lemma 3.4, the adjoint representation of G on g is of class P. Setting X = log(A -1 A ∩ B G (1, δ ε )) ⊂ g, the hypotheses of Theorem 2.3 are all met with ε replaced by O(ε). Indeed, assumption (i) is guaranteed by Lemma 3.5, and A being a δ ε -away from subgroups is exactly assumption (ii) of Theorem 3.1. So it remains to check that X is δ O(ε) -away from any proper submodule W in g. We may assume that W is maximal. Then, it is a maximal proper ideal of g, which by Lemma 3.3 is equal to the kernel H i of some projection π i : g → g/h i of G on a simple factor. In particular, there are only finitely many such W . Shrinking the neighborhood U if necessary, it suffices to check that

A -1 A ∩ B G (1, δ ε ) is δ O(ε) -away from H i . By assumption (i), for any ρ ≥ δ, N (π i (A -1 A ∩ B G (1, δ ε )), ρ) ≥ max g N (π i (A ∩ B G (g, δ ε )), ρ) ≥ δ O(ε) N (π i (A), ρ) ≥ δ O(ε) ρ -κ .
The last quantity is larger than 1 if we choose ρ = δ Cε with a large constant

C = O(1). This shows that A -1 A ∩ B G (1, δ ε ) is δ O(ε) -away from ker π i .
Thus, we can apply Theorem 2.3 to get an integer s ≥ 1 such that

B g (0, δ ε0 ) ⊂ A, X s + B g (0, δ) (17)
when ε is small enough. The idea is now to apply the Campbell-Hausdorff formula at an order such that the error term is of size at most δ. We identify an element w of the free group F s generated by s elements and the word map w : G ×s → G it induces. If x, y are elements in g, we want to approximate e x+y by a word in e x , e y . For example, with a remainder term of order 2, e x+y = e x e y e O( x 2 + y 2 ) . In order to get a remainder term of order 3, it is easier to approximate e 2(x+y) , and then, we get e 2(x+y) = (e x ) 2 (e y ) 2 (e y ) 2 e x (e y ) -2 (e x ) -1 e O( x 3 + y 3 ) . We shall use the following lemma, which generalizes these elementary computations, and follows from the Campbell-Hausdorff formula. Lemma 3.6. Let exp : g → G denote the exponential map of a Lie group. We fix a Euclidean norm on g and endow G with the associated left-invariant Riemannian metric. For all integers s ≥ 1 and ≥ 1, there exists an integer C ≥ 1, a word map w ∈ F s and a neighborhood U of 0 in g such that for all x 1 , . . . , x s ∈ U ,

d exp(Cx 1 + • • • + Cx s ), w(exp x 1 , . . . , exp x s ) ( x 1 + • • • + x s ) .
Proof. Consider g-valued functions f defined on a neighborhood of 0 in g ×s that can be written as a sum of a convergent series

f (x 1 , . . . , x s ) = +∞ k=1 f k (x 1 , . . . , x s ) where for each k, f k (x 1 , . . . , x s ) is a Q-linear combination of repeated brackets [x i1 , . . . , x i k ] = [x i1 , [x i2 , . . . , [x i -1 , x i k ] . . . ]] of length k.
The series converges on B g (0, r) ×s for some r > 0 in the sense that the numerical series obtained by replacing each repeated bracket of length k by r k and each coefficient by its absolute value is convergent. Identifying two such functions if they agree on a neighborhood of 0, we get a linear space G s over Q. Equipped with its obvious Lie bracket, G s is a graded Lie algebra over Q. For ≥ 1, we write O(d • ≥ ) to denote an unspecified element in G s of valuation at least . By the Baker-Campbell-Hausdorff formula [START_REF] Dynkin | Calculation of the coefficients in the Campbell-Hausdorff formula[END_REF], the map defined by (x, y) → x * y = log(exp(x) exp(y)) belongs to G 2 and moreover,

x * y = x + y + 1 2 [x, y] + O(d • ≥ 3). (18)
From that we deduce, by induction on s, that

x 1 * • • • * x s = x 1 + • • • + x s + O(d • ≥ 2). (19)
We and again by induction on s,

[x 1 , . . . , x s ] * = [x 1 , . . . , x s ] + O(d • ≥ s + 1). (20)
Now we prove by induction on that there exists an integer C and a word w ∈ F s such that

x 1 + • • • + x s = w * x 1 C , . . . , x s C + O(d • ≥ ), (21)
where w * is the word map induced by w , which is well defined on a neighborhood of 0 in g ×s . For = 2, this is given by [START_REF] Salehi | Super-approximation, I: p-adic semisimple case[END_REF]. Suppose the result has been proved for some ≥ 2. Let f be the sums of terms of degree in the remainder term O(d • ≥ ) on the right-hand side of [START_REF] De | Borelian subgroups of simple Lie groups[END_REF]. Since f has rational coefficients, there is an integer C ≥ 1 such that we can write

f (x 1 , . . . , x s ) = N i=1 m i x 1 C , . . . , x s C
where each m i is a repeated bracket of length . Therefore, by ( 20) and ( 19), there is w ∈ F s a product of repeated commutators such that

f (x 1 , . . . , x s ) = w * x 1 C , . . . , x s C + O(d • ≥ + 1).
Thus,

x 1 + • • • + x s = w * x 1 C , . . . , x s C + w * x 1 C , . . . , x s C + O(d • ≥ + 1) = w * x 1 C , . . . , x s C * w * x 1 C , . . . , x s C + O(d • ≥ + 1).
In the last step we used the fact that w * x1 C , . . . , xs C has valuation at least . This finishes the proof of the induction step and concludes the proof of the lemma.

To conclude the proof of Theorem 3.1 in the case r is abelian, we choose > 1 ε and apply Lemma 3.6 to elements x i of the form x i = Ad(a i )y i , with a i ∈ A s and y i ∈ X. By definition X ⊂ B g (0, δ ε ), so the error term is indeed of size O s (δ ε ) = O(δ), and therefore, for some s = O s, [START_REF] Benoist | Convolution in perfect Lie groups[END_REF]. Recalling [START_REF] Onishchik | Foundations of Lie theory[END_REF], we obtain

B G (1, δ ε0 ) ⊂ exp[C • B g (0, δ ε0 )] ⊂ exp[C • A, X s + B g (0, Cδ))] ⊂ A s B G (1, O(δ)).
This finishes the proof of the theorem in the case r is abelian.

Proof of the product theorem, general case

We now explain how to deal with a perfect Lie group G with Lie algebra g = s r, where r is nilpotent by Lemma 3.2 but not abelian. This will follow from the previous case, together with a quantitative version of the following fact: If R is a nilpotent Lie group, a subset A ⊂ R generates the group R if and only if A mod [R, R] generates R/[R, R].

For A and B subsets of a group G, we shall write Proof. Denote by r i , i ≥ 1 the descending central series of the Lie algebra r. Let (z 1 , . . . , z m ) be a basis of r i+1 consisting of commutators z j = [x j , y j ] with x j ∈ r and y j ∈ r i . For each j, consider the map f j : R → R i+1 defined by

f j (t) = [exp( √ tx j ),
T 0 f (h 1 , . . . , h m ) = h 1 z 1 + • • • + h m z m ,
so it is a C 1 -diffeomorphism on a neighborhood of 0. This implies that for some constant c > 0 depending only on R,

B Ri+1 (1, cρ 2 ) ⊂ f (B R (0, ρ)) ⊂ [B R (1, ρ), B Ri (1, ρ)] m .
This finishes the proof of the lemma, because for ρ small enough, B Ri+1 (1, cρ 2 ) • B Ri+1 (1, cρ 2 ) ⊃ B Ri+1 (1, 2cρ 2 ).

Approximate subgroups in non-perfect Lie groups

Here we prove Proposition 1.3. First, observe that in a nontrivial abelian Lie group, generalized arithmetic progressions (i.e. sums of arithmetic progressions) are the prototypes of approximate subgroups. Then in a non-perfect Lie group G, it suffices to lift a generalized arithmetic progression in its abelianization G/[G, G] to obtain an approximate subgroup with the desired properties.

Proof of Proposition 1.3. First consider the abelian case G = R ×d , with d ≥ 1.

Let κ ∈ (0, 1]. Given a neighborhood U of 0 ∈ R ×d , let r > 0 be such that B R d (0, r) ⊂ U . Define

P = δ κ x ∈ R ×d | x ∈ Z ×d ∩ [-δ -κ r, δ -κ r] ×d .
It is easy to check that P satisfy the required properties. Now let G be a simply connected non-perfect Lie group. Then G/[G, G] R ×d where d = dim g -dim[g, g]. Let π : G → R ×d the projection. Given a neighborhood U of 1 G ∈ G, let r > 0 be such that B G (1 G , 2r) ⊂ U and B R d (0, r) ⊂ π(U ). Let P be defined as above and put A = B G (1 G , 2r) ∩ π -1 (P ).

On the one hand, N (A, δ) ≈ G,r δ -dim[g,g] N (π(A), δ) ≈ G,r δ -dim[g,g] N (P, δ) ≈ G,r δ -dim[g,g]-dκ , and for similar reason, N (AAA, δ) G,r δ -dim[g,g] N (P + P + P, δ) G,r N (A, δ).

On the other hand, when δ is small so that δ κ < r, A is δ κ -dense in B G (1 G , r), that is, B G (1 G , r) ⊂ A (δ κ ) .

It follows immediately that for any connected normal subgroup N G, π G/N (A) is δ κ -dense in B G/N (1 G/N , r) and hence ∀ρ ≥ δ, N (π G/N (A), ρ) G,r ρ -κ .

Moreover, it is not difficult to see that given a simply connected Lie group G and r > 0, there is c = c(G, r) > 0 such that no proper closed connected subgroup is c-dense in B G (1 G , r). From this we deduce that A is (c -δ κ )-away from proper closed connected subgroups.

  exp[C Ad(a 1 )y 1 + • • • + C Ad(a s )y s ] ∈ w(a 1 e y1 a -1 1 , . . . , a s e ys a -1 s )B G (1, O(δ)) ∈ (A ∪ {1} ∪ A -1 ) s B G (1, O(δ)),

  [A, B] to denote the set of all commutators [a, b], a ∈ A, b ∈ B. This notation is in conflict with the group theoretic commutator which is the subgroup generated by all commutators. Despite this inconvenience, it will be clear from the context what [A, B] means. The precise lemma that we shall use is as follows. Lemma 3.7. Let R be a connected nilpotent Lie group with descending central series R i , i ≥ 1, i.e. R 1 = R and for i ≥ 1, R i+1 = [R, R i ]. For each i ≥ 1 there is k ≥ 1 such that for all ρ > 0 small enough, B Ri+1 (1, ρ 2 ) ⊂ [B R (1, ρ), B Ri (1, ρ)] k .

  and further definef : R m → R i+1 by f (t 1 , . . . , t m ) = f 1 (t 1 ) • • • f m (t m ).The function f is of class C 1 and its differential at 0 is

	[exp(	√	exp( -ty j ), exp( √ √ ty j )] -tx j )]	if t ≥ 0 if t < 0

Acknowledgements. This project started during the preparation of W.H.'s doctoral thesis at Université Paris 11, in Orsay, under the supervision of Emmanuel Breuillard and Péter Varjú. We thank them for their support and advice. We also thank the referee for some useful comments on an earlier version of the paper.

* W.H. was partially supported by ERC grant ErgComNum 682150.

Perfect Lie algebras and Lie groups

We begin by recording some elementary facts about perfect Lie groups and Lie algebras.

Let G be a connected Lie group with Lie algebra g. Using Levi's decomposition theorem [START_REF] Serre | Lie algebras and Lie groups[END_REF]Corollary 1,p. 49], we may write g as a semi-direct product g = s r of a semi-simple Lie algebra s and a solvable radical r. Writing s = s 1 ⊕ • • • ⊕ s k as a sum of simple ideals, one sees that for each i in {1, . . . , k}, h i = (⊕ j =i s j ) r is an ideal in g. The Lie algebra h i is the Lie algebra of a closed normal subgroup H i G. The projection maps π i : G → G/H i are the projections of G to its simple factors. Note that any left-invariant Riemannian metric d on G induces a left-invariant metric on G/H i . Indeed, if N G is any closed normal subgroup, one defines a distance on the quotient G/N by

For later use, we now list three elementary and standard lemmas about perfect Lie algebras. Lemma 3.2. If g is a perfect Lie algebra, then its solvable radical r is nilpotent. In particular, g can be written as a semi-direct product g = s r of a semi-simple Lie algebra s with a nilpotent ideal r.

Proof. See for instance [START_REF] Benoist | Convolution in perfect Lie groups[END_REF]Lemma 2.4]. Lemma 3.3. Let g be a perfect Lie algebra, with Levi decomposition g = s r. The image of a proper ideal of g under the map g → g/r is a proper ideal. In particular, the image of a maximal proper ideal is a maximal proper ideal.

Proof. Let n be an ideal in g such that n + r = g. We want to show that n = g. Denote by D i r, i ≥ 0 the derived series of r, i.e. D 0 r = r and D i+1 r = [D i r; D i r], ∀i ≥ 0. We show by induction that ∀i ≥ 0,

Indeed, ( 16) is true for i = 0. Suppose that it is true for some i ≥ 0; then it follows from [g, g] = g that

because n is an ideal in g. Since r is solvable, we may take i such that D i r = 0 to conclude that n = g. Lemma 3.4 (Perfect abelian extension of a semi-simple group). Let G be a perfect Lie group with Lie algebra g. If the radical r of g is abelian, then the adjoint representation of G is of class P.

Proof of Lemma 3.4. We have an exact sequence of G-modules

and by Proposition 2.2(i), all we need to check is that both r and g/r belong to P(G). Let R be the solvable radical of G; it is equal to the closed connected subgroup of G with Lie algebra r. The Lie group G/R is semi-simple, so its

We are now ready to finish the proof of Theorem 3.1.

Proof of Theorem 3.1, general case. Here again implied constants in Landau and Vinogradov notations depend on G and κ. Write the Lie algebra of G as a semi-direct product g = s r, with s semi-simple and r a nilpotent ideal, and let R be the nilpotent radical of G, i.e. the closed connected normal subgroup of G with Lie algebra r. The proof goes by induction on the nilpotency class of R.

We have already seen that Theorem 3.1 holds if ≤ 1. Now suppose that R has nilpotency class equal to ≥ 2 and that Theorem 3.1 has been proved if the nilpotency class is strictly less than .

Let R i , i ≥ 1 denote the lower central series of the group R. Each R i , i ≥ 1 is closed and connected, and the Lie algebra of R i is exactly the i-th term in the lower central series of r, see e.g. [START_REF] Onishchik | Foundations of Lie theory[END_REF]Theorem 5.7,p. 55]. We first remark that the assumptions of Theorem 3.1 are preserved when projecting to a quotient. The nilpotency class of the radical of G/R is -1. Let ε 1 > 0 be some constant, whose value will be specified later. By the induction hypothesis applied to G/R , provided ε is small enough compared to ε 1 , for some integer s depending on κ and ε 1 ,

Without loss of generality, we may replace (A ∪ {1} ∪ A -1 ) s B G (1, δ) by A, and assume that

By Lemma 3.7, we also have (1) .

From these inclusions and the fact that R is in the center of R, it follows that

Covering A 2 by balls of radius 1 2 δ 3ε1 , we obtain

Then A satisfies the assumptions of Theorem 3.1 with κ = 1 and ε = O(ε 1 ). Hence if ε 1 is small enough compared to ε 0 , then by the induction hypothesis again,

for some s depending on ε 0 . Since any element in R involved in this inclusion is within distance δ 2ε1 from the identity, we can conclude using [START_REF] De | A product theorem in simple Lie groups[END_REF] that

This finishes the proof of Theorem 3.1.


• Involves sampling and scoring.

• 6 degrees of freedom.

• Docking remains as a challenging problem. • Conventional approaches digitise proteins into 3D Cartesian grids...

• ...and use FFTs to calculated TRANSLATIONAL correlations:

BUT for docking, have to REPEAT for many rotations.

EROS-DOCK 3 / 16

• Atomistic or "coarse-grained" (CG) representations.

• Monte-Carlo or gradient-based techniques to search local energy minima.

EROS-DOCK 4 / 16

• The space 3D Euler angle rotations represented by a quaternion "π-ball".

• Used previously for shape registration.

• Never used before for docking. • First walk to identify spaces that lead to clash.

• Second walk to compute energies.

No Clash

Clash

• On average 94% of the π-ball search space is pruned • Only 6% of orientations are used to compute energies.

EROS-DOCK 11 / 16

Comparing EROS-DOCK With ATTRACT and ZDOCK

• 173 Docking Benchmark 4 target complexes.

• EROS-MIN uses ATTRACT minimizations for a fair comparison.

EROS-DOCK

• All pairwise solutions.

• Combinatorial problem.

• Fast RMSD computational methods.

•

  Hartley, Richard I., and Fredrik Kahl. "Global optimization through rotation space search." International Journal of Computer Vision 82.1 (2009): 64-79. Zacharias, Martin. "Proteinprotein docking with a reduced protein model accounting for sidechain flexibility." Protein Science 12.6 (2003): 1271-1282. Repeat for each pair... • Ready to look for "clash rotations"... EROS-DOCK • Build a list of all possible "clash cone angles". • Repeat for each pair ... If |R a -L b | > σ ab then a and b will never clash, else a and b will clash.

EROS-DOCK

If ω > β ab + ∆ s s will never clash, else s will clash. Using the Quaternion π-Ball

• Series of sample rotations dividing the π-ball into 8 cubes.

• The sample rotations represented as nodes in a 3D "search tree" data structure.

• Angular resolution 7.5 degrees.