Péter Varjú

Je Voudrais

Julien Barral

Bernard Host

Frédéric Paulin

Stéphane Seuret

Çagr, Mikoªaj Je Remercie Aussi Arindam

Lison

Kajal

Matthew

Jonas Richard

Bingxiao

Wei Guo

Zicheng

Camille

Gabriel Davi

Et

Xiaodong

Eddie Benjamin

Émilien Vincent Guillaume

Linxiao

Thibault, Ruoci Sasha Salim

Cong

Lucile

Tiago

Yang

Maxime Joseph Robert

Mor Jeanne Anthony

Luc

Yi Thomas

= {a -B |

de nombreuses discussions très enrichissantes, pour son enthousiasme et

In the discretized setting, the size of a set is measured by its covering number by δ-balls (a.k.a. metric entropy), where δ is the scale. In this document, we investigate combinatorial properties of discretized sets under addition, multiplication and orthogonal projection. There are three parts. First, we prove sum-product estimates in matrix algebras, generalizing Bourgain's sum-product theorem in the ring of real numbers and improving higher dimensional sum-product estimates previously obtained by Bourgain-Gamburd. Then, we study orthogonal projections of subsets in the Euclidean space, generalizing Bourgain's discretized projection theorem to higher rank situations. Finally, in a joint work with Nicolas de Saxcé, we prove a product theorem for perfect Lie groups, generalizing previous results of Bourgain-Gamburd and Saxcé.

Résumé

Remerciement

Je voudrais remercier tout d'abord mon directeur Emmanuel Breuillard pour sa disponibilité et sa patience durant toutes ces années, pour m'avoir proposé un sujet de recherche très passionnant, pour ses remarques éclairantes et pour m'avoir fait découvrir de nouveaux horizons mathématiques.

I would like to thank my second advisor Péter Varjú for

Parfois, nous avons besoin d'une condition plus forte comme suit.

(0.2)

∀ρ ≥ δ, ∀x ∈ E, N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A).
Dans ces conditions, plus κ est grande, plus la non-concentration est forte. La notion de (δ, α) n -ensemble dans [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] correspond à la condition (0.2) avec κ maximal, i.e. κ = α. Ici, est un petit paramètre pour relâcher légèrement ces conditions. Ajouter le terme δ est de dire que la non-concentration est exigée de l'échelle δ jusqu'à l'échelle δ . Clairement, la condition (0.2) implique (0.1). La réciproque n'est pas vraie. Néanmoins, si l'on se permet de passer dans des sous-ensembles relativement grandes, on peut extraire un sous-ensemble ayant la propriété (0.2) d'un ensemble ayant la propriété (0.1).

Exemple. Soit A un sous-ensemble borélien borné de R n de dimension de Hausdor dim H A > α. Soit µ la mesure donnée par le lemme de Frostman. Théorème 0.1 (Lemme de Frostman [START_REF] Mattila | Geometry of sets and measures in Euclidean spaces[END_REF]Theorem 8.8]). Soit A un sousensemble borélien de R n . Si dim H (A) > α alors il existe une mesure borélienne nie non-nulle µ de support compact telle que Supp(µ) ⊂ A et ∀ρ > 0, ∀x ∈ R n , µ(B(x, ρ)) ≤ ρ α .

Il est alors immédiat que pour tout ρ > 0,

N ρ (A) ≥ µ(A)ρ -α .
C'est-à-dire, nous avons la non-concentration (1.1) avec κ = α.

En guise de conclusion, dans ce mémoire, un ensemble δ-discrétisé veut dire (parfois informellement) un ensemble dont la taille est mesurée par le nombre de δ-recouvrement et qui vérie en plus une condition de non-concentration du type (0.1) ou (0.2). Le sujet de cette thèse est d'étudier le comportement (surtout la croissance) des ensembles discrétisés sous des opérations telles que l'addition, la multiplication, l'action d'un groupe ou les projections orthogonales. Dans les sections suivantes, nous discuterons selon l'opération qui nous intéresse.

La théorie additive

Dans cette section, supposons que l'espace ambiant E est muni d'une structure de groupe abélien dont la loi est notée additivement. Soient A, B ⊂ E des sousensembles. Notons L'un des problèmes fondamentaux en combinatoire additive est d'obtenir une bonne dépendance explicite en K des constantes implicites dans le théorème précédent.

Dans le sens inverse, tout résultat démontré dans le cadre discrétisé entraînera sa contrepartie dans le cadre discret. Dans ce mémoire, nous nous contentons des résultats existants et ne démontrons rien de nouveau pour la théorie additive.

Estimées somme-produit

Maintenant, supposons que notre espace ambiant E est en plus muni d'une structure d'anneau. Soient A, B ⊂ E des sous-ensembles. Notons

A • B = {ab | a ∈ A, b ∈ B} .
Soit s ∈ N * . On écrit A s pour le produit itéré de A avec lui-même s fois, A • • • A.

De plus, on dénit récursivement

A 1 = A ∪ (-A) et ∀s ∈ N * , A s = A s-1 ∪ s-1 k=1 A k + A s-k ∪ s-1 k=1 A k • A s-k .
Autrement dit, A s est l'ensemble des éléments qui peuvent être obtenus en additionnant et multipliant au plus s éléments de A ∪ (-A).

Grosso modo, le problème somme-produit demande, étant donné un sousensemble de E, s'il croît vite sous l'addition, la soustraction et la multiplication et si ce n'est pas le cas, quels sont les obstructions. Ainsi, une estimée sommeproduit est une minoration pour la taille de A s avec s ≥ 2. Le premier résultat de ce genre est dû à Erd®s et Szemerédi [START_REF] Erd®s | On sums and products of integers[END_REF] pour l'anneau des réels R.

Théorème 0.3 ). Il existe une constante absolue c > 0 telle que pour tout sous-ensemble ni non-vide A de R, on ait max(|A + A|, |A • A|) ≥ c|A| 1+c . vi Cela est le point de départ de beaucoup de travaux qui ou bien établissent des estimées similaires pour des classes plus larges d'anneaux, ou bien améliorent des bornes existantes. Voir [START_REF] Tao | The sum-product phenomenon in arbitrary rings[END_REF] pour une approche élégante et plus d'histoire.

Bien que le théorème de Erd®s-Szemerédi concerne les réels1 , il ne s'agit pas d'un résultat dans le cadre discrétisé. À la diérence de la théorie additive, l'étude du phénomène somme-produit dans le cadre discrétisé dière de son analogue discret en plusieurs aspects. Par exemple, la multiplication par δ préserve le cardinal alors qu'elle réduit le nombre de δ-recouvrement de tout ensemble borné à une constante. De plus quand x varie de δ à 1, son comportement varie continûment entre celui d'un diviseur de zéro et celui d'un élément inversible. Malgré cela, on espère qu'un ensemble discrétisé typique croît très vite sous l'addition et la multiplication. Pour l'anneau R, cela a été conjecturé par Katz et Tao dans [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] et résolu par Bourgain [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]. Théorème 0.4 (Théorème somme-produit discrétisé de Bourgain [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]). Étant donnés κ > 0 et σ < 1, il existe une constante > 0 telle que la proposition suivante soit vraie pour δ > 0 susamment petit. Soit A un sous-ensemble de R tel que

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-. Alors N δ (A + A) + N δ (A • A) ≥ δ -N δ (A).
La démonstration de ce théorème utilise une analyse multi-échelle. On étudie d'abord la structure additive à chaque niveau. Cela peut être fait à l'aide du théorème de Freiman rappelé plus haut. Notamment, la première démonstration de Bourgain [START_REF] Bourgain | On the Erd®s-Volkmann and Katz-Tao ring conjectures[END_REF] fait appel à un théorème de Freiman quantitatif dû à Chang [START_REF] Chang | A polynomial bound in Freiman's theorem[END_REF]. Ensuite, on utilise la multiplication qui interagit entre les diérents niveaux pour déduire une croissance.

L'importance du théorème somme-produit de Bourgain peut être justiée par ses nombreuse applications. Lorsque le cadre discrétisé a été introduit dans [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF], il était conçu comme une stratégie générale pour démontrer les résultats dans le régime continu tout en utilisant les idées et les résultats venant du régime discret où l'on dispose de théories bien développées telles que la combinatoire arithmétique. Ainsi, l'une des motivations de Bourgain était d'établir la conjecture de Erd®s-Volkmann [START_REF] Erd®s | Additive Gruppen mit vorgegebener Hausdorscher Dimension[END_REF] qui arme qu'aucun sous-anneau borélien de R n'est de dimension de Hausdor strictement entre 0 et 1. La conjecture a aussi été résolue par Edgar et Miller [START_REF] Edgar | Borel subrings of the reals[END_REF] avec d'autres idées. Cependant, leur méthode ne sont pas quantitative, comparée à la méthode de Bourgain. De plus, comme prévu par Katz et Tao [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF], le théorème 0.4 fait également progrès sur le problème de distance de Falconer et sur une conjecture de Furstenberg en géométrie fractale. Parmi d'autres applications directes, citons aussi la construction explicite d'expanseurs monotones due à Bourgain et Yehudayo [START_REF] Bourgain | Expansion in SL 2 (R) and monotone expanders[END_REF]. Nous discuterons plus d'applications plus tard lorsque nous parlerons des théorèmes de projection et des théorèmes produit.

Bourgain et Gamburd ont obtenu des estimations similaires pour l'anneau C dans [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF] et plus tard pour l'anneau C n , le produit direct de C avec lui-même n fois, n ≥ 2, dans [START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF]. Les énoncés sont un peu diérentes puisque R n'a pas de sous-algèbre réel propre alors que C et C n en ont. De plus, l'anneau C n a des idéaux propres non-triviaux , i.e. il n'est pas simple. Dans le chapitre 3, nous démontrons une estimation somme-produit pour les algèbres simples de dimension nie sur R. Notons que par le théorème de Wedderburn et le théorème de Frobenius, une telle algèbre est isomorphe à M n (R), M n (C) ou M n (H), l'algèbre des matrices de taille n × n à coecients réels, complexes ou dans les quaternions, avec n ≥ 1. Avant d'énoncer le résultat, mentionnons que dans le contexte discret, Chang [START_REF] Chang | Additive and multiplicative structure in matrix spaces[END_REF] a étudié le problème somme-produit pour les matrices réelles et Tao [START_REF] Tao | The sum-product phenomenon in arbitrary rings[END_REF] a obtenu un théorème somme-produit concernant une algèbre quelconque. Théorème 3.1. Soit E une algèbre réelle normée2 simple de dimension nie.

Étant donnés κ > 0 et σ < dim(E), il existe une constante > 0 dépendant seulement de E, κ et σ telle que la proposition suivante soit vraie pour δ > 0 susamment petit. Soit A un sous-ensemble de E satisfaisant (i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-, (iv) pour tout sous-algèbre propre W de E, il existe a ∈ A tel que d(a, W ) ≥ δ .

Alors,

N δ (A + A)

+ N δ (A + A • A) ≥ δ -N δ (A).
La stratégie de la démonstration consiste à produire un tore riche an d'utiliser l'estimée somme-produit de Bourgain-Gamburd dans C n . Ici, un tore riche veut dire un sous-ensemble de taille relativement grande constitué d'éléments simultanément diagonalisables. L'idée du tore riche remonte jusqu'aux travaux de Helfgott [START_REF] Helfgott | Growth and generation in SL 2 (Z/pZ)[END_REF] et s'est montrée très utile pour démontrer des théorèmes produit dans beaucoup de situations, par exemple, le théorème produit discrétisé de Saxcé (théorem 0.7) dont nous parlerons un peu plus tard. En fait, notre méthode donne une stratégie pour obtenir des estimées somme-produit dans les algèbres simples à partir d'une estimée somme-produit dans le corps de base.

Nous obtenons également des estimations concernant la croissance d'un sousensemble discrétisé d'un espace euclidien sous l'action linéaire. Soient X un sous-ensemble borné de R n et A une collection d'endomorphismes de R n . On peut se demander si X croît vite sous l'addition et les transformations par les éléments de A, pourvu que A soit assez riche. Théorème 3.2. Soit n ∈ N * . Étant donnés κ > 0 et σ < n, il existe une constante > 0 telle que la proposition suivante soit vraie pour δ > 0 susamment petit. Soient A un sous-ensemble de End(R n ) et X un sous-ensemble de R n . Supposons que (i) A ⊂ B(0, δ -),

(ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) pour tout sous-espace propre non-trivial W de R n , il existe a ∈ A et w ∈ B W (0, 1) tel que d(aw, W ) ≥ δ , (iv) X ⊂ B(0, δ -),

(v) ∀ρ ≥ δ, N ρ (X) ≥ δ ρ -κ , (vi) N δ (X) ≤ δ -σ-.
Alors, N δ (X + X) + max a∈A N δ (X + aX) ≥ δ -N δ (X),

où aX = {ax | x ∈ X}.
Cela améliore un résultat de Bourgain-Gamburd [11, Proposition 1] où on exige une constante à la place de δ dans la condition (iii). Cette condition (iii) est une condition d'irréductibilité. Son aaiblissement est le dé technique principal dans la démonstration du théorème 3.2. Le facteur δ signie que la condition doit être vériée à l'échelle δ . Ainsi, le théorème 3.2 arme que la croissance a lieu même si l'on ne connaît rien à des échelles entre δ et 1. Cette amélioration est importante pour beaucoup d'applications parce que ce genre d'estimations sont souvent utilisées avec le théorème de Balog-Szemerédi-Gowers qui nécessite de restreindre les ensembles avec lesquels on travaille à des sousensembles de taille δ fois la taille initiale. Cette procédure détruit généralement toutes les informations au-dessus de l'échelle δ .

Revenons aux phénomènes somme-produit dans les algèbres. Au lieu de penser la somme et le produit comme étant les lois dans un anneau, on peut penser la somme comme étant l'addition dans un espace vectoriel et le produit comme étant les endomorphismes de cet espace vectoriel obtenus en considérant les multiplications à gauche et à droite. Avec ce point de vue, on retrouve facilement le théorème 3.1 à partir du théorème 3.2. Donc en fait le phénomène sommeproduit ne concerne pas seulement les anneaux. Le produit peut venir de l'extérieur, d'une action. On verra dans le chapitre 5 une estimation de type somme-produit pour les représentations de groupe de Lie.

On peut aussi déduire du théorème 3.2 une estimation somme-crochet dans les algèbres de Lie simples. Si A est un sous-ensemble d'une algèbre de Lie g, on écrit Corollaire 3.3. Soit g une algèbre de Lie réelle de dimension nie qui est en plus munie d'une norme. Étant donnés κ > 0 et σ < dim(g), il existe une constante > 0 telle que la proposition suivante soit vraie pour δ > 0 susamment petit. Soit A un sous-ensemble de g satisfaisant (i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-, (iv) pour tout sous-algèbre de Lie propre W de g, il existe a ∈ A tel que d(a, W ) ≥ δ .

Alors,

N δ (A + A) + N δ (A + [A, A]) ≥ δ -N δ (A).
ix 0.4 Orthogonal projections Soient 0 < m < n des entiers positifs. Soit Gr(R n , m) la grassmannienne des sous-espaces vectoriels de dimension m dans l'espace euclidien R n . Pour V ∈ Gr(R n , m), notons π V : R n → V la projection orthogonale sur V . Les propriétés fractales des projections orthogonales ont été beaucoup étudiées en géométrie fractale, en commençant par le théorème de projection de Marstrand [START_REF] Marstrand | Some fundamental geometrical properties of plane sets of fractional dimensions[END_REF]. Voir par exemple [START_REF] Falconer | Sixty years of fractal projections[END_REF] pour plus d'histoire. De manière informelle, un théorème de projection est une minoration pour la taille des projections d'un sous-ensemble sur de diérentes directions. Comme en générale on n'espère pas que la projection soit grande pour toutes les directions, le théorème s'exprime souvent par une majoration de la taille de l'ensemble des directions exceptionnelles, c'est-à-dire, des directions sur lesquelles la projection est petite. Par exemple, rappelons le résultat suivant obtenu dans une série de travaux dûs à Mattila et Falconer.

Théorème 0.5 (Mattila [44], Falconer [START_REF] Falconer | Hausdor dimension and the exceptional set of projections[END_REF], voir aussi [46, 5.3]). Soit A ⊂ R n un sous-ensemble borélien de dimension de Hausdor dim H (A) = α. Soit s > 0 un réel.

(i) Si 0 < s < α ≤ m, alors dim H {V ∈ Gr(R n , m) | dim H (π V (A)) < s} ≤ m(n -m) -(m -s). (ii) Si 0 < s ≤ m ≤ α, alors dim H {V ∈ Gr(R n , m) | dim H (π V (A)) < s} ≤ m(n -m) -(α -s).
Notons que m(n -m) est la dimension de Gr(R n , m) et que la notion de la dimension de Hausdor sur Gr(R n , m) ne dépend pas du choix spécique de la métrique car toutes les distances sur un compact sont équivalentes tant qu'elles dénissent la même topologie.

À l'aide de son théorème somme-produit discrétisé, Bourgain a établi un théorème de projection discrétisé pour les projections de rang 1. Avant d'énoncer le théorème, introduisons quelques notations an de formuler des conditions de non-concentration dans les espaces projectifs ou dans les grassmanniennes. Pour V ∈ Gr(R n , m) et W ∈ Gr(R n , n -m), on dénit

d (V, W ) = |det(v 1 , . . . , v m , w 1 , . . . , w n-m )| où (v 1 , . . . , v m ) est une base orthonormée de V et (w 1 , . . . , w n-m ) une base orthonormée de W . Par exemple, d (V, W ) = 0 si et seulement si V et W ont une intersection non-triviale. Pour ρ ≥ 0, on pose V (W, ρ) = {V ∈ Gr(R n , m) | d (V, W ) ≤ ρ}.
Théorème 0.6 (Bourgain [7,Theorem 5]). Soit n ≥ 2 un entier. Étant donnés 0 < α < n et κ > 0, il existe > 0 tel que la proposition suivante soit vraie pour δ > 0 susamment petit. Soit A ⊂ B R n (0, 1). Soit µ une mesure de probabilité sur l'espace projectif Gr(R n , 1). Supposons que

N δ (A) ≥ δ -α+ ; x ∀ρ ≥ δ, ∀x ∈ R n , N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A); ∀ρ ≥ δ, ∀W ∈ Gr(R n , n -1), µ(V (W, ρ)) ≤ δ -ρ κ .

Alors il existe un sous-ensemble

A ⊂ A et un ensemble de direction D ⊂ Gr(R n , 1) tels que N δ (A ) ≥ δ N δ (A), µ(D) ≥ 1 -δ et N δ (π θ (A )) ≥ δ -α n - dès que θ ∈ D et que A ⊂ A vérie N δ (A ) ≥ δ 2 N δ (A).
Plus tard, dans [START_REF] Orponen | A discretised projection theorem in the plane[END_REF], pour les sous-ensembles de R 2 , Orponen a obtenu une borne plus forte sous une codition de non-concentration plus forte. L'approche qui y est utilisée est diérente mais fait également appel à la théorie autour du phénomène somme-produit.

Il convient aussi de remarquer qu'il y a un ensemble de problèmes en parallèle concernant les projections des ensembles ou mesures auto-similaires. Par exemple, récemment, une conjecture de Furstenberg concernant transversalité entre les ensembles ×2-invariants et ×3-invariants a été résolue dans deux travaux indépendants, Shmerkin [START_REF] Shmerkin | On Furstenberg's intersection conjecture, self-similar measures, and the L q norms of convolutions[END_REF] et Wu [START_REF] Wu | A proof of Furstenberg's conjecture on the intersections of ×p and ×q-invariant sets[END_REF]. L'approche de Shmerkin utilise aussi les outils venant de la combinatoire additive et quelques idées dans la démonstration du théorème somme-produit de Bourgain. Voir aussi [START_REF] Shmerkin | Projections of self-similar and related fractals: a survey of recent developments[END_REF] pour plus d'informations.

L'objectif du chapitre 4 est de généraliser le théorème 0.6 aux projections de rang supérieur. Théorème 4.1. Soient 1 ≤ m < n des entiers. Étant donnés 0 < α < n et κ > 0, il existe > 0 tel que la proposition suivante soit vraie pour δ > 0 susamment petit. Soient A ⊂ B R n (0, 1) et µ une mesure de probabilité sur Gr(R n , m). Supposons que

N δ (A) ≥ δ -α+ ; ∀ρ ≥ δ, ∀x ∈ R n , N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A); ∀ρ ≥ δ, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ δ -ρ κ . Alors il existe D ⊂ Gr(R n , m) tel que µ(D) ≥ 1 -δ et N δ (π V (A )) ≥ δ -m n α- dès que V ∈ D et que A ⊂ A vérie N δ (A ) ≥ δ N δ (A).
Ce résultat est nouveau pour m > 1. En plus, comparée au théorème 0.6, notre borne inférieure est établie pour tout sous-ensemble assez grand de A au lieu de seulement les sous-ensembles assez grand d'une certaine partie de A. La démonstration du théorème 4.1 se fait par une récurrence sur le couple (n, m). L'approche dans la démonstration du théorème 0.6 combinée avec l'estimation somme-produit en dimension supérieure (théorème 3.2) montre le cas où m est un diviseur de n. Ensuite, de nouvelles idées sont utilisées pour ramener à ce cas spécial. xi 0.4.1 Motivation ergodique Le théorème de projection discrétisé de Bourgain constitue un ingrédient important dans le théorème de Bourgain-Furman-Lindenstrauss-Mozes [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF] sur l'équidistribution des orbites sur le tore R d /Z d sous les actions des sous-semi-groupes de SL d (Z). Ce résultat ergodique est d'autant plus intéressant qu'il est quantitatif. Par exemple, il a permis à Bourgain et Varjú [START_REF] Bourgain | Expansion in SL d (Z/qZ), q arbitrary[END_REF] d'établir l'existence de trous spectraux uniformes dans SL d (Z/qZ), avec q entier arbitraire.

Le théorème de Bourgain-Furman-Lindenstrauss-Mozes donne des énoncés qualitatifs sur les mesures stationnaires. Les quatre auteurs ont notamment démontré une propriété de raideur 3 . Dans [START_REF] Benoist | Mesures stationnaires et fermés invariants des espaces homogènes[END_REF], par les méthodes plus ergodiques, Benoist et Quint ont généralisé ce résultat de stiness à une classe beaucoup plus large de systèmes dynamiques. En particulier, pour l'action linéaire de SL d (Z) sur le tore R d /Z d , ils n'ont pas besoin de l'hypothèse de proximalité dans [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF]. Cependant, les résultats dans [START_REF] Benoist | Mesures stationnaires et fermés invariants des espaces homogènes[END_REF] ne sont pas quantitatifs. Donc si l'on veut des résultats quantitatifs, il faudrait reprendre la méthode de [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF]. L'approche dans [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF] est Fourier-analytique. Lorsqu'un sous-groupe Γ ⊂ SL d (Z) agit sur le tore, son transposé t Γ agit sur les coecients de Fourier. Une grande partie de la démonstration se concentre sur l'étude des grands coecients de Fourier sous cette action. Par la théorie des produits aléatoires de matrices, si Γ est proximal, alors les grands produits aléatoires dans Γ se comporte comme des projections de rang 1 composées avec des rotations, s'ils sont observés à la bonne échelle. C'est ainsi que le théorème 0.4 intervient. Maintenant, si Γ n'est pas proximal, les projections de rang supérieur vont jouer un rôle. Et nous espérons que le théorème 4.1 va être utile dans cette situation.

Conséquence sur les projections des fractales

Tout comme le théorème de projection discrétisé de Bourgain, le théorème 4.1 peut être utilisé pour déduire un théorème de projection en terme de dimension de Hausdor. Corollaire 4.2. Soient 1 ≤ m < n des entiers. Étant donnés 0 < α < n et κ > 0, il existe > 0 tel que la proposition suivante soit vraie. Soit A ⊂ R n un sous-ensemble borélien de dimension dim H (A) = α. Alors l'ensemble des directions exceptionnelles

V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α +
ne peut pas supporter de mesure non-nulle µ sur Gr(R n , m) ayant la propriété de non-concentration suivante,

∀ρ > 0, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ ρ κ .
Appliqué à une mesure de Frostman supportée par les directions exceptionnelles, cela donne Corollaire 4.3. Soient 1 ≤ m < n des entiers. Étant donnés 0 < α < n et κ > 0, il existe > 0 tel que la proposition suivante soit vraie. Soit A ⊂ R n un sous-ensemble borélien de dimension dim

H (A) = α. Alors dim H V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α + ≤ m(n -m) -1 + κ.
Par conséquent, on peut poser κ = = 0 dans l'estimation précédente. Comparée à ce qui est connu (le théorème 0.5), la constante 1 dans notre estimation est très faible pour la plupart des valeurs de m et de α. Néanmoins, notre résultat n'est pas entièrement recouvert par le théorème 0.5, notamment dans les deux situations suivantes

(i) (Projection sur des droites) m = 1 et α ∈ ]0, 1 + 1 n-1 [, (ii) (Projection sur des hyperplans) m = n -1 et α ∈ ]n -1 -1 n-1 , n[.
Par exemple, pour n = 2 et m = 1 (cas traité dans Bourgain [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]), cela donne,

dim H θ ∈ Gr(R 2 , 1) | dim H (π θ (A)) ≤ 1 2 dim H (A) = 0, pour tout ensemble borélien A avec 0 < dim H (A) < 2.

Estimées produit

Maintenant supposons que notre espace ambiant est un groupe multiplicatif G.

Comme plus haut, pour des sous-ensembles A et B de G, leur ensemble produit est noté par

AB = {ab | a ∈ A, b ∈ B} .

Nous écrivons aussi

A -1 = {a -1 | a ∈ A} pour l'ensemble inverse et A s = A • • • A pour l'ensemble produit itéré s-fois.
|(A ∪ {1} ∪ A -1 ) s | s |A 3 | |A| Os(1)
|A|.

En vue de cette inégalité, quand on étudie la croissance de A s , on s'intéresse particulièrement à la constante de triplement |A 3 | |A| . Une petite précision est nécessaire pour éviter de la confusion. Quand on parle de croissance dans les groupes en géométrie des groupes, on s'intéresse au comportement asymptotique de |A s | avec A une partie génératrice. Citons le théorème de Gromov qui caractérise les groupes de croissance polynomiale 4 . Alors qu'en combinatoire arithmétique, le cadre dans lequel nous nous plaçons, nous analysons de manière plus ne la quantité |A s | pour les valeurs petites de s. En particulier, les questions dans ce cadre ont du sens et sont intéressantes même si G est un groupe ni.

Dans le cadre discret, nous avons une très bonne compréhension des ensembles à petit triplement. La théorie commence par les travaux de Helfgott [START_REF] Helfgott | Growth and generation in SL 2 (Z/pZ)[END_REF][START_REF] Helfgott | Growth in SL 3 (Z/pZ)[END_REF] et mène à une généralisation aux groupes nis de type Lie par Breuillard-Green-Tao [START_REF] Breuillard | Approximate subgroups of linear groups[END_REF] et indépendamment par Pyber-Szabó [START_REF] Pyber | Growth in nite simple groups of Lie type[END_REF] et aboutit aussi à une classication des ensembles à petit triplement due à Breuillard-Green-Tao [START_REF] Breuillard | The structure of approximate groups[END_REF]. Le dernier résultat établit une conjecture de Helfgott-Lindenstrauss et peut être vu comme une généralisation du théorème de Freiman dans le cadre noncommutatif.

xiii Contrairement à ce qui se passe dans le cas commutatif, il y a peu d'espoir de transférer directement les estimées produit depuis le cadre discret au cadre discrétisé.

Néanmoins, l'analogue de l'inégalité (0.3) reste valable, comme montré par Tao [START_REF] Tao | Product set estimates for non-commutative groups[END_REF]Theorem 6.8]. Et c'est pour cela qu'on se concentre sur le triplement N δ (A 3 ) N δ (A) dans le cadre discrétisé aussi. En utilisant le théorème somme-produit de Bourgain, Bourgain et Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] ont les premiers résultats dans ce cadre, à savoir, un théorème produit pour les groupes de Lie SU(d), d ≥ 2. Cela a été ensuite généralisé par Saxcé [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF] aux groupes de Lie simples.

Théorème 0.7 (Théorème produit pour les groupes de Lie simples, Saxcé [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]).

Soit G un groupe de Lie simple. Il existe un voisinage U de l'élément neutre de G tel que la proposition suivante soit vraie. Étant donnés

σ < dim(G) et κ > 0, il existe > 0 tel que pour tout δ > 0 susamment petit, si A ⊂ U satisfait (i) N δ (A) ≤ δ -σ-; (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ ; (iii) pour tout sous-groupe propre fermé connexe H < G, il existe a ∈ A avec d(a, H) ≥ δ ; alors N δ (A 3 ) ≥ δ -N δ (A).
Ce résultat peut être comparé à celui de Breuillard-Green-Tao [START_REF] Breuillard | Approximate subgroups of linear groups[END_REF] dans le cadre discret. Tous les deux arment qu'un sous-ensemble typique dans un groupe simple a un grand triplement sauf s'il est coincé dans un sous-groupe.

Les théorèmes produit peuvent être appliqués pour obtenir des résultats de trou spectral. Cela est fait pour les groupes SU(d), d ≥ 2 par Bourgain-Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] et plus généralement pour les groupes compacts simples par Benoist-Saxcé [START_REF] Benoist | A spectral gap theorem in simple Lie groups[END_REF]. Ensuite, Boutonnet, Ioana et Golsedy [START_REF] Boutonnet | Local spectral gap in simple lie groups and applications[END_REF] ont introduit la notion de trou spectral local et ont étendu davantage ces résultats aux cas non-compacts. De l'autre côté, un théorème produit discrétisé peut avoir des conséquences concernant la dimension de Hausdor des sous-groupes boréliens. Ainsi, en combinant les techniques d'analyse de Fourier [START_REF] De Saxcé | Trou dimensionnel dans les groupes de Lie compacts semisimples via les séries de Fourier[END_REF], Lindenstrauss-Saxcé [START_REF] Lindenstrauss | Hausdor dimension and subgroups of SU (2)[END_REF] et Saxcé [START_REF] De Saxcé | Borelian subgroups of simple Lie groups[END_REF] ont montré qu'il n'y a pas de sous-groupe borélien dense de dimension de Hausdor intermédiaire dans un groupe de Lie connexe simple.

Si le groupe G est nilpotent, alors il n'est pas dicile de construire des sousensembles qui satisfont les hypothèses du théorème 0.7 mais qui ont un petit triplement. Par exemple, on peut prendre une somme de progressions arithmétiques si G est abélien. Et pour un groupe nilpotent quelconque, il y a une notion de nilprogression qui généralise les progressions arithmétiques, voir par exemple [START_REF] Breuillard | The structure of approximate groups[END_REF]. Ce contraste entre les groupes simples et les groupes nilpotents apparaît aussi avec l'existence de sous-groupe borélien dense de dimension intermédiaire. Erd®s et Volkmann [START_REF] Erd®s | Additive Gruppen mit vorgegebener Hausdorscher Dimension[END_REF] ont construit des sous-groupes de R de dimension de Hausdor arbitraire entre 0 et 1. Saxcé [START_REF] De Saxcé | Subgroups of fractional dimension in nilpotent or solvable Lie groups[END_REF] a étendu cette construction aux groupes de Lie nilpotents et à une large classe de groupes résolubles.

Dans un travail en commun avec Nicolas de Saxcé, nous étendons le théorème 0.7 aux groupes de Lie parfaits. Ceci constitue le résultat principal du chapitre 5. Rappelons qu'un groupe de Lie G est dit parfait si son algèbre de xiv Lie g satisfait la condition [g, g] = g. En particulier, les groupes de Lie semisimples sont parfaits. Rappelons que le quotient d'un groupe de Lie G par son radical R est semi-simple. Si G est simplement connexe alors G/R l'est aussi et donc un produit direct de groupes de Lie simples et simplement connexes. Les facteurs dans ce produit direct sont appelés les facteurs simples de G.

Théorème 5.1 (Théorème produit pour les groupes de Lie parfaits). Soit G un groupe de Lie parfait simplement connexe. Il existe un voisinage U de l'élément neutre de G tel que la proposition suivante soit vraie. Étant donnés σ < dim(G)

et κ > 0, il existe > 0 tel que pour tout δ > 0 susamment petit, si A ⊂ U satisfait (i) N δ (A) ≤ δ -σ-; (ii) pour tout facteur simple S de G, en notant π S : G → S la projection canonique, on a ∀ρ ≥ δ, N ρ (π S (A)) ≥ δ ρ -κ ;
(iii) pour tout sous-groupe propre fermé connexe

H < G, il existe a ∈ A avec d(a, H) ≥ δ ; alors N δ (A 3 ) ≥ δ -N δ (A).
Ici c'est pour des raisons pratiques que nous demandons à ce que G soit simplement connexe. Le résultat concerne en fait les groupes de Lie locaux, car nous restreignons à un voisinage de l'élément neutre.

L'idée de la démonstration est de réduire d'abord au cas où G est un produit semi-direct d'un groupe semi-simple par un groupe abelien. Et puis, dans ce cas spécial, on considère sa représentation adjointe et y montre une croissance. Enn, cette croissance dans l'algèbre de Lie est transférée au groupe de Lie grâce à l'utilisation de la formule de Campbell-Hausdor.

Ainsi, en étape intermédiaire, nous obtenons une estimation de type sommeproduit pour les représentations de groupe de Lie. C'est un résultat intéressant à part entière. Soit V une représentation linéaire de dimension nie sur R d'un groupe de Lie G. Soient X un sous-ensemble de V et A un sous-ensemble de G. Nous nous demandons si X croît vite sous l'addition et l'action de A. Pour s ≥ 1, on écrit A, X s pour désigner l'ensemble des éléments de V qui peuvent être exprimés comme sommes, diérences et produits d'au plus s éléments de A et de X. and Vinogradov notations f g are used throughout this document. We also write f g to say f g and g f . In this chapter we introduce the main results by providing backgrounds and motivations. For impatient readers, the main new results in this document are : (all in the discretized a.k.a metric entropy setting)

• A sum-product theorem for matrix algebras (Theorem 3.1).

• A sum-product estimate for sets in Euclidean space under linear transformation (Theorem 3.2).

• A projection theorem for orthogonal projections of rank ≥ 2 (Theorem 4.1).

• (Joint work with N. de Saxcé) A product theorem in perfect Lie groups (Theorem 5.1).

• (Joint work with N. de Saxcé) A sum-product estimate for representations of Lie groups (Theorem 5.2).

The notion of discretized sets

The notion of discretized sets was highlighted by Katz and Tao in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] as a framework for studying fractal properties of continuous sets by using combinatorial tools such as arithmetic combinatorics. In this section we introduce the setup.

The δ-covering number

Let (E, d) be a metric space. For ρ > 0 and x ∈ E, we denote by B(x, ρ) or by x (ρ) the closed ball centered at x and of radius ρ. And we write B E (x, ρ) to specify the ambient space when it is not clear. For A ⊂ E, we denote by A (ρ) the closed ρ-neighborhood of A :

A subset A is said to be ρ-separated if for any a ∈ A, a is the only element in the intersection B(a, ρ) ∩ A. Throughout this document, the variable δ stands for a positive real number which we refer to as the scale.

Denition. Let A be a relatively compact subset of (E, d). The δ-covering number of A, also known as the metric entropy of A, is dened as

N δ (A) = min N ≥ 0 | ∃x 1 , . . . , x N ∈ E, A ⊂ N i=1 B(x i , δ) .
Example. Let p be a prime number and let (Z p , | • | p ) be the ring of p-adic integers equipped with its usual p-adic absolute value. If A is a subset of Z p , then for all k ∈ N,

N p -k (A) = |π k (A)|
where π k : Z p → Z p /p k Z p Z/p k Z denotes the reduction modulo p k .

If we allow the scale δ to be zero, then N 0 (A) is exactly the cardinality of A. It is more interesting to study the asymptotic behavior of N δ (A) when δ goes to 0 from above.

Example. The lower and upper Minkowski dimensions of A ⊂ (E, d) can be dened as (see [45, 5.3])

dim M (A) = lim inf δ→0 log N δ (A) -log δ and dim M (A) = lim sup δ→0 log N δ (A) -log δ .
In particular, if N δ (A) δ→0 δ -α then they agree and are equal to α.

Now let E be the Euclidean space R n , n ≥ 1. Denote by λ the Lebesgue measure on R n . Besides the δ-covering number, we have other means to measure the size of a set at scale δ.

Lemma 2.1. Let δ > 0 and let A be a bounded subset of R n . Let à be a maximal 2δ-separated subset of A. Then

N 2δ (A) ≤ | Ã| ≤ N δ (A) ≤ N 1 (B(0, 2)) N 2δ (A), and δ -n λ(A (δ) ) n N δ (A).
In particular, changing the scale by a constant factor only aects the covering number by a constant factor. Moreover, A and its δ-neighborhood A (δ) have the same size when viewed at scale δ :

N δ (A (δ) ) n N δ (A).
That is why in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF], a δ-discretized set is dened to be a union of balls of radius δ. And in the proofs in later chapters, we can almost always replace A by its δ-neighborhood.

Example. Let µ be a compactly supported probability measure on R n . Its FourierStieltjes transform (see [START_REF] Katznelson | An introduction to harmonic analysis[END_REF]Chapter VI,[START_REF] Benoist | Convolution in perfect Lie groups[END_REF]) μ(ξ) = e -i ξ,x dµ(x), ξ ∈ R n , is K-Lipschitz for some K > 0 depending only on max x∈Supp(µ) x . Therefore, if we set, for t > 0,

A t = {ξ ∈ R n | |μ(ξ)| ≥ t}, then A ( t K ) 2t ⊂ A t .
Hence, it is natural to look at the set A t at scale t.

Non-concentration

If a bounded subset A ⊂ R n has size N δ (A) δ -α , we would like to think α as its dimension. But a ball of radius δ 1-α n also satises N δ (B(0, δ 1-α n )) δ -α . Clearly, a ball has very dierent properties compared to a fractal. To avoid this degenerate situation, we will often require some non-concentration properties on the set A. Let κ > 0 and > 0 be parameters. For example we often ask that (1.1)

∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ .
And sometimes we need a stronger condition as follows :

(1.2) ∀ρ ≥ δ, ∀x ∈ E, N δ (A ∩ x (ρ) ) ≤ δ -ρ κ N δ (A).
In these conditions the larger κ is, the stronger the non-concentration becomes. The notion of (δ, α) n -sets in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] corresponds to condition (1.2) with κ maximal, i.e. κ = α. Here is a small parameter to relax these conditions. We may understand it as saying that the non-concentration is required from scale δ to scale δ . Obviously, condition (1.2) implies (1.1). The converse is not true. Nevertheless, if we allow passing to a large subset, we can extract a subset having property (1.2) from a set having property (1.1).

Example. Let A be a bounded Borel set in R n of Hausdor dimension dim H A > α. Let µ be the measure given by Frostman's lemma. Theorem 1.1 (Frostman's lemma [START_REF] Mattila | Geometry of sets and measures in Euclidean spaces[END_REF]Theorem 8.8]). Let A be a Borel set of R n . If dim H (A) > α then there exists a nite nonzero compactly supported Borel measure µ with Supp(µ) ⊂ A such that

∀ρ > 0, ∀x ∈ R n , µ(B(x, ρ)) ≤ ρ α .
Then it is immediate that for any ρ > 0, we have

N ρ (A) ≥ µ(A)ρ -α .
In other words, we have the non-concentration (1.1) with κ = α.

Additive theory

In this section, suppose that the ambient space E is moreover equipped with a structure of abelian group. For subsets A, B ⊂ E, we write

-A = {-a | a ∈ A} , A + B = {a + b | a ∈ A, b ∈ B} and A -B = {a -b | a ∈ A, b ∈ B} .
Let s be a positive integer, we write sA for the s-fold sum-set A + • • • + A. By additive theory, we mean the study of the growth of sA or that of sA -s A, s, s ≥ 1.

Consider the discretized setting in E = R n . It turns out that by approximating R n by the lattice δ • Z d , we can transfer any result concerning additive properties in the discrete setting to the δ-discretized setting. For example, we have the Plünnecke-Ruzsa inequality. (B) then for all integers k ≥ 1 and l ≥ 0,

Lemma 2.4 (Plünnecke-Ruzsa inequality). For all

K ≥ 1, if N δ (A + B) ≤ KN δ
N δ (kA -lA) n K k+l N δ (B).
In particular, for any s ≥ 2, N δ (sA) is signicantly larger than N δ (A) if and only if N δ (A + A) is already signicantly larger than N δ (A). That is why an important problem in additive combinatorics is the classication of sets with small doubling (i.e. sets A such that |A + A| ≤ K|A|). Freiman's theorem says such sets are contained in generalized arithmetic progressions of comparable size (see [START_REF] Tao | Additive combinatorics[END_REF]Chapter 5]). Transferred into the discretized setting, it becomes Theorem 1.2 (Discretized version of Freiman's Theorem, [START_REF] Tao | Product set estimates for non-commutative groups[END_REF]Proposition 7.3]).

Let K ≥ 2 be a parameter. Let A be a bounded subset of R n . If N δ (A + A) ≤ KN δ (A) then there exists a set P which is the sum of O K,n (1) arithmetic progressions in R n such that A ⊂ P + B(0, δ) and |P | K,n N δ (A).

Having a good dependence of the implied constants on K is one of the central problems in additive combinatorics.

In the other way around, anything proved in the δ-discretized setting will imply its counterpart in the discrete setting. So in this document, we do not prove anything new for the additive theory of discretized sets.

Sum-product estimates

Now we suppose that our ambient space E has moreover a ring structure. For A and B subsets of E, we write

A • B = {ab | a ∈ A, b ∈ B} .
Let s be a positive integer, we write A s for the s-fold product-set A • • • A. Moreover, we dene recursively A 1 = A ∪ (-A) and for all positive integers s ≥ 2,

A s = A s-1 ∪ s-1 k=1 A k + A s-k ∪ s-1 k=1 A k • A s-k .
In other words, A s is the set of elements obtained from at most s elements of A ∪ (-A) by adding and multiplying them.

Roughly speaking, the sum-product problem asks, given a set A, whether A grows fast under addition, multiplication and subtraction and if not, what are the obstructions. Thus, a sum-product estimate is a lower bound for the size of A s with s ≥ 2. The rst result of this type is due to Erd®s and Szemerédi [START_REF] Erd®s | On sums and products of integers[END_REF] for the ring of real numbers R.

Theorem 1.3 (Erd®s-Szemerédi [28]

). There is an absolute constant c > 0 such that for any nonempty nite subset A of R, we have

max(|A + A|, |A • A|) ≥ c|A| 1+c .
This was the starting point of numerous works. They either establish similar estimates for broader classes of rings or improve existing bounds. See [START_REF] Tao | The sum-product phenomenon in arbitrary rings[END_REF] for an elegant treatment and more history.

Although the Erd®s-Szemerédi theorem concerns the ring of real numbers1 , it is not about discretized sets. Unlike the additive theory, the study of the sum-product phenomenon in the discretized setting diers in many ways from its discrete analogue. For example, the multiplication by δ preserves the cardinality while reduces the δ-covering number of any bounded set to a constant. And when x changes from δ to 1, its behavior continuously changes form that of a zero-divisor to that of an invertible element. Despite this, we expect typical discretized sets to grow quickly under addition and multiplication. For the ring R, this was conjectured by Katz and Tao in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF] and settled by Bourgain [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].

Theorem 1.4 (Bourgain [7]). Given κ > 0 and σ < 1, there is > 0 such that the following holds for δ > 0 suciently small. Let A be a subset of R, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-.
Then, (1.3)

N δ (A + A) + N δ (A • A) ≥ δ -N δ (A).
The proof of this theorem uses multi-scale analysis. Additive structure is analyzed at each level (using a quantitative Freiman's theorem due to Chang [START_REF] Chang | A polynomial bound in Freiman's theorem[END_REF] in Bourgain's rst proof in [START_REF] Bourgain | On the Erd®s-Volkmann and Katz-Tao ring conjectures[END_REF]) and then multiplicative information is used to show growth in size.

Bourgain's sum-product theorem is very inuential. It is used directly or indirectly in almost all results about discretized sets mentioned in this document. When the discretized setting was introduced in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF], it was conceived as a general strategy for proving results in the continuous regime (where sets are measured by its Hausdor dimension) while using ideas and results in the discrete regime where we have well-developed theory such as arithmetic combinatorics. Thus, one of the original motivations of Bourgain's theorem was the Erd®s-Volkmann ring conjecture [START_REF] Erd®s | Additive Gruppen mit vorgegebener Hausdorscher Dimension[END_REF] which asserts that no Borel subring of R has Hausdor dimension between 0 and 1. This conjecture was also settled by Edgar and Miller [27] using dierent ideas. However, their proof is not quantitative. Moreover, as anticipated in [START_REF] Katz | Some connections between Falconer's distance set conjecture and sets of Furstenburg type[END_REF], Bourgain's theorem also makes progress on the Falconer distance problem and the Furstenberg conjecture in fractal geometry. Among other direct applications, let us mention the construction of explicit monotone expanders by Bourgain and Yehudayo [START_REF] Bourgain | Expansion in SL 2 (R) and monotone expanders[END_REF]. We will discuss more applications later when we talk about projection and product estimates.

Bourgain and Gamburd have obtained similar estimates for the ring C in [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF] and later for the ring C n , the n-fold direct product of C with itself, in [START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF]. The statements are slightly dierent since R has no proper subalgebra while C and C n have. Moreover, C n has nontrivial proper ideals, i.e. it is not simple. In Chapter 3, we prove a sum-product estimate for nite-dimensional simple algebras over R. Note that by the Wedderburn structure theorem and the Frobenius theorem, such algebras are isomorphic to M n (R), M n (C) or M n (H), the algebra of n × n matrices over the real numbers, the complex numbers, or the quaternions, with n ≥ 1. Before stating the result, let us mention that in the discrete context, Chang [START_REF] Chang | Additive and multiplicative structure in matrix spaces[END_REF] investigated the sum-product problem for real matrices and Tao [START_REF] Tao | The sum-product phenomenon in arbitrary rings[END_REF] obtained a sum-product theorem concerning general algebras.

Theorem 3.1. Let E be a normed2 simple real algebra of nite dimension.

Given κ > 0 and σ < dim(E), there is > 0 depending on E, κ and σ such that the following holds for δ > 0 suciently small. Let A be a subset of E, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-, (iv) for every proper subalgebra W ⊂ E, there is a ∈ A such that d(a, W ) ≥ δ . Then, N δ (A + A) + N δ (A + A • A) ≥ δ -N δ (A).
The strategy is to produce a rich torus, i.e. a relatively large subset consisting of simultaneously diagonalizable elements, and then use the Bourgain-Gamburd sum-product estimate in C n . The idea of rich torus originated from the work of Helfgott [START_REF] Helfgott | Growth and generation in SL 2 (Z/pZ)[END_REF] and since then has been used to show product theorems in a lot of situations. For instance, the proof of Saxcé's product theorem (Theorem 1.7) consists also of producing a rich torus and applying the Bourgain-Gamburd sumproduct estimate in C n . Our method provides a general strategy for obtaining sum-product estimates in simple algebras from sum-product estimates in the base eld.

We also obtain related estimates concerning linear actions on Euclidean spaces. Let X be a bounded subset of the Euclidean space R n . Let A ⊂ End(R n ) be a collection of linear endomorphisms. We can ask whether X grows under addition and transformation by elements of A, provided that A is suciently rich. Theorem 3.2. Let n be a positive integer. Given κ > 0 and σ < n, there is > 0 such that the following holds for δ > 0 suciently small. Let A be a subset of End(R n ) and X a subset of R n , assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) for every nonzero proper linear subspace W ⊂ R n , there is a ∈ A and w ∈ B W (0, 1) such that d(aw, W ) ≥ δ , (iv) X ⊂ B(0, δ -), (v) ∀ρ ≥ δ, N ρ (X) ≥ δ ρ -κ , (vi) N δ (X) ≤ δ -σ-. Then, N δ (X + X) + max a∈A N δ (X + aX) ≥ δ -N δ (X),
where aX = {ax | x ∈ X}.

This improves a previous result of Bourgain and Gamburd [11, Proposition 1] where a constant is required instead of δ in the irreducibility condition (iii). The proof of Bourgain and Gamburd relies on this irreducibility hypothesis at all scales in a crucial way. It seems to us not easy to modify if we relax their assumption. Relaxing this hypothesis is the most important technical challenge in the proof of Theorem 3.2. A reason for which this improvement is important is that this kind of estimates are often used together with the Balog-Szemerédi-Gowers theorem, which requires restricting the sets we work with to subsets of size δ times the original size. This procedure usually destroys all information above scale δ .

Theorem 3.2 is actually a better formulation for the sum-product phenomenon since we can easily recover Theorem 3.1 form it by considering the left and right multiplications by elements of A as the collection of endomorphisms of E. Similarly, we can also obtain a "sum-bracket" estimate in simple Lie algebras.

If A is a subset of a Lie algebra g, write [A, A] = {[a, b] | a, b ∈ A}.
Corollary 3.3. Let g be a normed3 simple Lie algebra of nite dimension.

Given κ > 0 and σ < dim(g), there is > 0 such that the following holds for δ > 0 suciently small. Let A be a subset of g, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-, (iv) for every proper Lie subalgebra W of g, there is a ∈ A such that d(a, W ) ≥ δ .
Then,

N δ (A + A) + N δ (A + [A, A]) ≥ δ -N δ (A).

Orthogonal projections

Let 0 < m < n be positive integers. We write

Gr(R n , m) do denote the Grass- mannian of m-dimensional subspaces in R n . For V ∈ Gr(R n , m), denote by π V : R n → V the orthogonal projection onto V .
Fractal properties of orthogonal projections of subsets the Euclidean space have been intensively studied in fractal geometry starting from the renowned Marstrand projection theorem [START_REF] Marstrand | Some fundamental geometrical properties of plane sets of fractional dimensions[END_REF]. See the survey [START_REF] Falconer | Sixty years of fractal projections[END_REF] for more history. Roughly speaking the problem asks for lower bounds for the size of the projections of the set to dierent directions. Since in general, the projection can not be large for every direction. We ask more precisely for a bound on the size of exceptional directions where a exceptional direction means a subspace onto which the projection is small. Recall the following higher-dimensional projection theorem obtained in a series of works of Mattila and Falconer.

Theorem 1.5 (Mattila [44], Falconer [START_REF] Falconer | Hausdor dimension and the exceptional set of projections[END_REF], see also [46, 5.3

]). Let

A ⊂ R n be a Borel set of Hausdor dimension dim H (A) = α. For all s > 0, (i) if 0 < s < α ≤ m then dim H {V ∈ Gr(R n , m) | dim H (π V (A)) < s} ≤ m(n -m) -(m -s); (ii) if 0 < s ≤ m ≤ α then dim H {V ∈ Gr(R n , m) | dim H (π V (A)) < s} ≤ m(n -m) -(α -s).
Note that m(n -m) is the dimension of Gr(R n , m) and the notion of Hausdor dimension on Gr(R n , m) does not depend on the specic choice of the metric since all distances on a compact set are equivalent as long as they dene the same topology.

Using his discretized sum-product theorem, Bourgain established a discretized projection theorem concerning rank one projections. Before stating the theorem, let us introduce some notations in order to formulate non-concentration conditions in projective spaces or Grassmannians.

For V ∈ Gr(R n , m) and W ∈ Gr(R n , n -m), we dene d (V, W ) = |det(v 1 , . . . , v m , w 1 , . . . , w n-m )|
where (v 1 , . . . , v m ) is an orthonormal basis of V and (w 1 , . . . , w n-m ) an orthonormal basis of W . For example d (V, W ) = 0 if and only if V and W have nontrivial intersection. For ρ ≥ 0, we dene

V (W, ρ) = {V ∈ Gr(R n , m) | d (V, W ) ≤ ρ}.
Theorem 1.6 (Bourgain [7,Theorem 5]). Let n ≥ 2 be an integer. Given 0 < α < n and κ > 0, there exists > 0 such that the following holds for suciently small δ > 0. Let A be a subset of R n contained in the unit ball B(0, 1). Let µ be a probability measure on the projective space Gr(R n , 1). Assume that

N δ (A) ≥ δ -α+ ; ∀ρ ≥ δ, ∀x ∈ R n , N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A); ∀ρ ≥ δ, ∀W ∈ Gr(R n , n -1), µ(V (W, ρ)) ≤ δ -ρ κ .

Then there is a subset

A ⊂ A and a set of directions D ⊂ Gr(R n , 1) such that N δ (A ) ≥ δ N δ (A), µ(D) ≥ 1 -δ and N δ (π θ (A )) ≥ δ -α n - whenever θ ∈ D and A ⊂ A is a subset such that N δ (A ) ≥ δ 2 N δ (A).
Later in [START_REF] Orponen | A discretised projection theorem in the plane[END_REF], for sets in the plane R 2 , Orponen obtained shaper bound under stronger non-concentration condition for µ. The approach is dierent but nevertheless exploits the sum-product phenomenon.

It is also worth noting that there is a parallel set of problems which concerns projections of self-similar measures and self-similar sets. For instance, recently, a conjecture of Furstenberg concerning transversality between ×2 and ×3 invariant sets was settled in two independent works, Shmerkin [START_REF] Shmerkin | On Furstenberg's intersection conjecture, self-similar measures, and the L q norms of convolutions[END_REF] and Wu [START_REF] Wu | A proof of Furstenberg's conjecture on the intersections of ×p and ×q-invariant sets[END_REF]. Shmerkin's approach also uses tools form additive combinatorics and ideas from Bourgain's discretized sum-product theorem. See also the survey paper [START_REF] Shmerkin | Projections of self-similar and related fractals: a survey of recent developments[END_REF] for further references.

The main result of Chapter 4 is a generalization of Theorem 1.6 to higher rank projections. Theorem 4.1. Let m < n be positive integers. Given 0 < α < n and κ > 0, there exists > 0 such that the following holds for suciently small δ > 0. Let A be a subset of R n contained in the unit ball B(0, 1). Let µ be a probability measure on Gr(R n , m). Assume that

N δ (A) ≥ δ -α+ ; ∀ρ ≥ δ, ∀x ∈ R n , N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A); ∀ρ ≥ δ, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ δ -ρ κ . Then there is a set D ⊂ Gr(R n , m) such that µ(D) ≥ 1 -δ and N δ (π V (A )) ≥ δ -m n α- whenever V ∈ D and A ⊂ A is a subset such that N δ (A ) ≥ δ N δ (A).
For m > 1, our result is new. Moreover compared to Theorem 1.6, we establish the lower bound for all relatively large subsets of A. The proof goes by induction on the dimension pair (n, m). The approach in the proof of Theorem 1.6 combined with the higher dimensional sum-product estimate (Theorem 3.2) proves the cases where m divides n. New ideas are used to reduce other cases to these cases.

Ergodic theoretic motivation

Bourgain's discretized projection theorem is one of the main ingredients in the Bourgain-Furman-Lindenstrauss-Mozes theorem [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF] on equidistribution for orbits of subsemigroups of SL d (Z) on the torus. This last result can be used to study stationary measures. Namely, they obtained a stiness result. Note also that Bourgain and Varjú [START_REF] Bourgain | Expansion in SL d (Z/qZ), q arbitrary[END_REF] used Bourgain-Furman-Lindenstrauss-Mozes theorem in combination with the result in [START_REF] Varjú | Expansion in SL d (O K /I), I square-free[END_REF] to show expansion in SL d (Z/qZ), q arbitrary integer.

In [START_REF] Benoist | Mesures stationnaires et fermés invariants des espaces homogènes[END_REF], Benoist and Quint have generalized the stiness result of Bourgain-Furman-Lindenstrauss-Mozes to a much broader class of dynamical systems. In particular, for linear actions on tori, they do not need the proximality assumption in [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF]. However, the results in [START_REF] Benoist | Mesures stationnaires et fermés invariants des espaces homogènes[END_REF] are not quantitative.

The approach in [START_REF] Bourgain | Stationary measures and equidistribution for orbits of nonabelian semigroups on the torus[END_REF] is Fourier-analytic. While a subgroup Γ ⊂ SL d (Z) acts on the torus, its transpose t Γ acts on Fourier coecients. A large part of the proof focuses on the study of large Fourier coecients under this action. By the theory of random matrix products, if Γ is proximal, then large random products in Γ behave like rank one projections composed with rotations, if viewed at an appropriate scale. That is how Theorem 1.6 comes into play. If Γ is not proximal, higher rank projections will be involved. We hope that Theorem 4.1 can be used in this situation.

Consequence on fractal projections

Just like Bourgain's discretized projection theorem can be used to derive a projection theorem in terms of Hausdor dimension [7, Theorem 4], Theorem 4.1 has the following consequence. Corollary 4.2. Let m < n be positive integers. Given 0 < α < n and κ > 0, there is > 0 such that the following is true.

Let A ⊂ R n is a Borel subset of dimension dim H (A) = α. Then the set of exceptional directions V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α +
does not support any nonzero measure µ on Gr(R n , m) with the following nonconcentration property,

∀ρ > 0, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ ρ κ .
Applied to a Frostman measure supported on the set of exceptional directions, this gives Corollary 4.3. Let m < n be positive integers. Given 0 < α < n and κ > 0, there is > 0 such that the following holds.

Let A ⊂ R n be a Borel set of dimension dim H (A) = α. Then dim H V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α + ≤ m(n -m) -1 + κ.
In particular, as κ → 0, we get

dim H V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α ≤ m(n -m) -1.
This should be compared to the estimates already known in Theorem 1.5. Our result is not covered by Theorem 1.5 in the following two situations:

(i) (Projection to lines) m = 1 and α ∈ ]0, 1 + 1 n-1 [, (ii) (Projection to hyperplanes) m = n -1 and α ∈ ]n -1 -1 n-1 , n[.
For example, as known in Bourgain [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF], for n = 2 and m = 1, we have

dim H θ ∈ Gr(R 2 , 1) | dim H (π θ (A)) ≤ 1 2 dim H (A) = 0, for all Borel set A such that 0 < dim H (A) < 2.

Product estimates

Now let the ambient space be a multiplicative group G. As before, for subsets A and B of G, we write

AB = {ab | a ∈ A, b ∈ B}
to denote the product set. We write also A -1 = {a -1 | a ∈ A} for the inverse set and A s = A • • • A for the s-fold product set. This time we are interested in the growth of (A ∪ {1} ∪ A -1 ) s . Although the Plünnecke-Ruzsa inequality is false for general groups, we still have (see [START_REF] Tao | Additive combinatorics[END_REF]Proposition 2.40])

(1.4)

|(A ∪ {1} ∪ A -1 ) s | s |A 3 | |A| Os(1)
|A|.

That is why we are interested in sets with small tripling (i.e. |A 3 | ≤ K|A|).

In the discrete setting, we have very good understanding of such sets, starting with the works of Helfgott [START_REF] Helfgott | Growth and generation in SL 2 (Z/pZ)[END_REF][START_REF] Helfgott | Growth in SL 3 (Z/pZ)[END_REF], generalized by Breuillard-Green-Tao [START_REF] Breuillard | Approximate subgroups of linear groups[END_REF] and independently by Pyber-Szabó [START_REF] Pyber | Growth in nite simple groups of Lie type[END_REF] to nite groups of Lie types on the one hand and leading to a classication of small tripling set due to Breuillard-Green-Tao [START_REF] Breuillard | The structure of approximate groups[END_REF] on the other. The last result solves a conjecture of Helfgott-Lindenstrauss and can be viewed as a generalization of Freiman's theorem.

Unlike the commutative case, there is little hope to transfer directly product estimates from the discrete setting to the discretized setting.

Nevertheless, the analogue of (1.4) in the discretized setting holds, as shown by Tao [START_REF] Tao | Product set estimates for non-commutative groups[END_REF]Theorem 6.8]. That is why in the discretized setting, we also focus on the tripling. Using Bourgain's sum-product theorem, Bourgain and Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] obtained product theorem for SU(d), d ≥ 2. This is then generalized by Saxcé [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF] to simple Lie groups.

Theorem 1.7 (Product theorem for simple Lie groups, Saxcé [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]). Let G be a simple Lie group. There is a neighborhood U of the identity in G such that the following holds. Given σ < dim(G) and κ > 0, there exists > 0 such that for all δ > 0 suciently small, if

A ⊂ U satises (i) N δ (A) ≤ δ -σ-; (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ ;
(iii) for any proper closed connected subgroup H < G, there exists a ∈ A with d(a, H) ≥ δ ;

then N δ (A 3 ) ≥ δ -N δ (A).
This result can be compared to Breuillard-Green-Tao [START_REF] Breuillard | Approximate subgroups of linear groups[END_REF] in the discrete setting. It says a typical discretized set in a simple group has large tripling unless it is trapped in a subgroup.

Product theorems can be applied to get spectral gap results. This is done for the groups SU(d), d ≥ 2 by Bourgain-Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF] and for compact simple Lie groups by Benoist-Saxcé [START_REF] Benoist | A spectral gap theorem in simple Lie groups[END_REF]. Then Boutonnet-Ioana-Golsedy [START_REF] Boutonnet | Local spectral gap in simple lie groups and applications[END_REF] introduced the notion of local spectral gap and further extended the expansion result to noncompact settings. Discretized product theorems can also be applied to study the Hausdor dimension of measurable subgroups. Thus, combined with Fourier techniques [START_REF] De Saxcé | Trou dimensionnel dans les groupes de Lie compacts semisimples via les séries de Fourier[END_REF], Lindenstrauss-Saxcé [START_REF] Lindenstrauss | Hausdor dimension and subgroups of SU (2)[END_REF] and Saxcé [START_REF] De Saxcé | Borelian subgroups of simple Lie groups[END_REF] showed that there is no measurable dense subgroup of intermediate Hausdor dimension in connected simple Lie groups.

If the group G is nilpotent, then it is easy to construct a subset satisfying the assumptions of Theorem 1.7 but having small tripling. For example, we can take a sum of arithmetic progressions if G is abelian. And for a general nilpotent group, there is a notion of nilprogression which generalizes arithmetic progressions, see e.g. [START_REF] Breuillard | The structure of approximate groups[END_REF]. This contrast between simple groups and nilpotent groups also appears with the existence of measurable dense subgroups of intermediate dimension. Erd®s and Volkmann [START_REF] Erd®s | Additive Gruppen mit vorgegebener Hausdorscher Dimension[END_REF] constructed measurable subgroups of arbitrary Hausdor dimension in R. Saxcé [START_REF] De Saxcé | Subgroups of fractional dimension in nilpotent or solvable Lie groups[END_REF] extended this construction to nilpotent Lie groups and a large class of solvable groups.

In a joint work with Nicolas de Saxcé, we extend Theorem 1.7 to perfect Lie groups. This is the main result of Chapter 5. Recall that a Lie group G is said to be perfect if its Lie algebra g satises the condition [g, g] = g. It is a weaker condition than semisimplicity. The quotient of G by its radical R is semisimple. If G is simply-connected, then G/R is simply-connected, hence a direct product of simply-connected simple Lie groups. Factors appearing in this direct product are called simple factors of the group G.

Theorem 5.1 (Product theorem for perfect Lie groups). Let G be a simplyconnected perfect Lie group. There is a neighborhood U of the identity in G such that the following holds. Given σ < dim(G) and κ > 0, there exists > 0 such that for all δ > 0 suciently small, if

A ⊂ U satises (i) N δ (A) ≤ δ -σ-; (ii) for any simple factor S of G, denote by π S : G → S the canonical projec- tion, ∀ρ ≥ δ, N ρ (π S (A)) ≥ δ ρ -κ ;
(iii) for any proper closed connected subgroup H < G, there exists

a ∈ A with d(a, H) ≥ δ ; then N δ (A 3 ) ≥ δ -N δ (A).
We require G to be simply-connected only for notational convenience. The theorem is in fact about local Lie groups (a.k.a. analytic group chunk, see [START_REF] Serre | Lie algebras and Lie groups[END_REF]) because we restrict to a neighborhood of the identity. If G is a connected perfect Lie group, we can restrict to a neighborhood U such that U 3 lifted to G, the universal covering of G, is contained in the neighborhood given by Theorem 5.1 applied to G.

The idea of the proof is to rst reduce to the case where G is the semidirect product of a semisimple group by an abelian group. Then in this special case we consider its adjoint representation and show a growth statement in the adjoint representation. Finally, this growth in the Lie algebra can be transferred to the group by using the Campbell-Hausdor formula.

Thus, as an intermediate result, we obtain a sum-product type estimate for representations of Lie groups. It is an interesting result on its own right. The setting is the following. Let V be a nite-dimensional linear representation over R of a Lie group G. Let X be a bounded subset of V and A a bounded subset of G. We can ask whether X grows fast under addition and the action of A. For s ≥ 1, we dene A, X s to be the set of elements in V that can be obtained as sums, dierences and products of at most s elements of A and X.

Theorem 5.2 (Sum-product estimates in representations). Let G be a Lie group and V nite-dimensional linear representation of G over R. There exists a neighborhood U of the identity in G depending only on V such that the following holds. Given 0 , κ > 0, there exists s ≥ 1 and > 0 such that for all δ > 0 suciently small, if A ⊂ U and X ⊂ B V (0, 1) satisfy the following : (i) There is a Jordan-Hölder4 sequence 0 = V 0 < . . . < V l = V such that for every i = 1, . . . , l,

∀ρ ≥ δ, N ρ (π Vi/Vi-1 (A)) ≥ δ ρ -κ .
where

π Vi/Vi-1 : G → GL(V i /V i-1 ) denotes the representation of G on V i /V i-1 .
(ii) For any proper closed connected subgroup H < G, there exists a ∈ A with d(a, H) ≥ δ .

(iii) For any proper submodule W < V , there exists x ∈ X with d(x, W ) ≥ δ .

Then,

B V (0, δ 0 ) ⊂ A, X s + B V (0, δ).
Note that for irreducible representations, this is a variant of Theorem 3.2. It is in this special case that we use results from Chapter 3. The rest of the proof of Theorem 5.2 consists of reducing to this special case by an induction on the length of the Jordan-Hölder decomposition of V .

Considering R * acting on R, we can recover from Theorem 5.2 Bourgain's discretized sum-product theorem (Theorem 1.4). Similarly, we can recover the discretized sum-product estimates for C or H. Moreover, the method in the proof of Theorem 5.2 can be used to obtain sum-product estimates in semisimple algebras (i.e. sums of simple algebras).

Chapter 2 Generalities on discretized sets

In this chapter we collect some elementary and well-known results, especially arithmetic combinatorial tools, in the discretized setting. We provide proofs that are important or are not easily accessible in the literature. Some of the results are not used in later chapters.

Basics

We will rst work in the Euclidean space R n . Anything we prove in R n can be easily transferred to an arbitrary nite-dimensional normed vector space (at the price of losing a constant) if the proof is not already valid in general vector spaces.

Recall that λ denotes the Lebesgue measure.

Lemma 2.1. Let δ > 0 and let A be a bounded subset of R n . Let à be a maximal 2δ-separated subset of A. Then (2.1)

N 2δ (A) ≤ | Ã| ≤ N δ (A) ≤ N 1 (B(0, 2)) N 2δ (A),
and

| Ã| ≤ λ(A (δ) ) λ(B(0, δ)) ≤ 2 n N δ (A).
As a consequence,

N δ (A (δ) ) n N δ (A).
Proof. Let A and à be as in the statement of the lemma. Let B(x 1 , δ), . . . , B(x N , δ) be a cover of A by N = N δ (A) balls of radius δ.

If the balls B(a, 2δ), a ∈ à do not cover A then we could nd b ∈ A \ à such that à ∪ {b} is still 2δ-separated, contradicting the maximality of Ã. Therefore,

N 2δ (A) ≤ | Ã|.
Consider the map à → {1, . . . , N } which maps each a ∈ à to an index i such that a ∈ B(x i , δ). Since à is 2δ-separated, this map is injective. Hence

| Ã| ≤ N δ (A).
The last inequality in (2.1) follows from a more general estimate

(2.2) ∀ρ ≥ δ, N δ (A) ≤ N ρ (A) max x∈R n N δ (A ∩ B(x, ρ))
and the fact that N δ (B(x, 2δ)) = N 1 (B(0, 2)) for any x ∈ R n . To see inequality (2.2), we rst cover A by ρ-balls and then cover each of these ρ-balls by δ-balls.

Since à is 2δ-separeted, the balls B(a, δ), a ∈ à are pairwise disjoint and included in A (δ) . Hence | Ã|λ(B(0, δ)) ≤ λ(A (δ) ).

From

A ⊂ N i=1 B(x i , δ) follows that A (δ) ⊂ N i=1 B(x i , 2δ). Hence λ(A (δ) ) ≤ N δ (A)λ(B(0, 2δ)).
It is sometimes useful to change scales. Clearly, N δ (A) is nonincreasing in δ. Conversely, for all δ ≥ δ, we have

(2.3) N δ (A) n δ δ n N δ (A).
It is a consequence of (2.2) and the fact N δ (B(0, δ )) n (δ δ -1 ) n which can be proved using Lemma 2.1.

If f : R n → R n is a linear map with f ≤ K where K ≥ 1, or more generally if f : A → R n is K-Lipschitz, we have (2.4) N δ (f A) n K n N δ (A).
For a family of bounded sets (A i ) we have

N δ A i ≤ N δ (A i ).
This need not be an equality even if (A i ) is a disjoint family. However, we have an equality if A (δ) i are pairwise disjoint. When we want to intersect two discretized sets A, B ⊂ R n , we shall take the δ-neighborhood of at least one of the sets before intersecting. Note that N δ (A (δ) ∩ B (δ) ) can be large while at the same time A ∩ B is empty. The same is true for A (2δ) ∩ B (2δ) and A (δ) ∩ B (δ) . However, we have (2.5)

N δ (A (2δ) ∩ B) n N δ (A (δ) ∩ B (δ) ) n N δ (A ∩ B (2δ) ).

Ruzsa calculus

Let δ > 0 be the scale. Let A, B, C be bounded subsets of R n . All implied constants in Landau and Vinogradov notations depend on n. Again results in this section can be transferred to an arbitrary nite-dimensional normed vector space with a loss of a constant factor.

Let K ≥ 2 be a parameter. We denote by O(K) an unspecied nite set of cardinality O(K). Moreover, we write O(K; A) to indicate that it is a subset of A. For example, we have

O(K; A) + O(L; B) ⊂ O(KL, A + B). Lemma 2.2 (Ruzsa's covering lemma). Let K ≥ 2 be a parameter. If N δ (A + B) ≤ KN δ (A), then B ⊂ A -A + O(K; B) + B(0, δ).
Proof. Let B 0 be a maximal subset of B such that the translates b + A + B(0, δ 2 ) b∈B0 are disjoint. We have, on the one hand, for any b ∈ B, the translate

b + A + B(0, δ 2 ) is not disjoint from b + A + B(0, δ 2 ) for some b ∈ B 0 which means b ∈ A -A + B 0 + B(0, δ).
On the other hand, by the disjointness,

N δ (A + B) N δ 2 (A + B 0 ) ≥ |B 0 |N δ 2 (A).
Hence |B 0 | K.

We can approximate R n by the lattice δ • Z n . More precisely for a subset A ⊂ R n , we dene

à = a ∈ δ • Z n | A ∩ a (nδ) = ∅ .
Then A ⊂ Ã(nδ) and à ⊂ A (nδ) . Consequently N δ (A) | Ã|. Moreover these inclusions behave nicely under addition and subtraction. Namely, for all k, l ≥ 0,

kA -lA ⊂ k à -l à + B(0, n(k + l)δ) and conversely k à -l à ⊂ kA -lA + B(0, n(k + l)δ).
Using this approximation and the scale change estimate (2.1) we can translate additive combinatorial results in the discrete setting to the discretized setting. For the discrete version see the book [START_REF] Tao | Additive combinatorics[END_REF] or [START_REF] Petridis | New proofs of Plünnecke-type estimates for product sets in groups[END_REF] for the Plünnecke-Ruzsa inequality. B) then for all natural numbers k and l,

Lemma 2.3 (Ruzsa triangular inequality). We have

N δ (B)N δ (A -C) N δ (A -B)N δ (B -C).

Lemma 2.4 (Plünnecke-Ruzsa inequality). For all

K ≥ 1, if N δ (A + B) ≤ KN δ (
N δ (kA -lA) ≤ O(K) k+l N δ (B).

Energy and Balog-Szemerédi-Gowers theorem

Before stating the Balog-Szemerédi-Gowers theorem in the discretized setting let us recall some basic facts about energy in the discrete setting. Let ϕ : X → Y be a map between discrete sets and A a nite subset of X, dene the ϕ-energy of A to be

ω(ϕ, A) = y∈Y |A ∩ ϕ -1 (y)| 2 .
In other words, it is the square of the l 2 -norm of the push-forward of the counting measure on A under ϕ or the number of collisions of the map ϕ |A :

ω(ϕ, A) = ϕ * 1 A 2 2 = # {(a 1 , a 2 ) ∈ A × A : ϕ(a 1 ) = ϕ(a 2 )} .
For example, the usual additive energy between two subsets A and B of an abelian group G is ω(+, A × B) where + is the group law of G.

When nothing is known about ϕ, ω(ϕ, A) can be as small as |A| (when ϕ is injective) and as large as |A| 2 (when ϕ is constant on A). If the image of A by ϕ is small then the energy is large by the Cauchy-Schwarz inequality :

(2.6)

ω(ϕ, A) ≥ |A| 2 |ϕ(A)| .
The converse is not true. Nevertheless, we have a partial converse.

Lemma 2.5. Suppose there are K, M > 0 such that ω(ϕ, A)

≥ M K |A| and for all y ∈ Y , |A ∩ ϕ -1 (y)| ≤ M . Then there exists A ⊂ A such that |A | ≥ 1 2K |A| and |ϕ(A )| ≤ 2K M |A|.
Proof. The idea is to trim o small bers. We consider

Y = y ∈ Y | |A ∩ ϕ -1 (y)| ≥ M 2K
and let A = ϕ -1 (Y ). By the denition Y , we have

|A| ≥ y∈Y |A ∩ ϕ -1 (y)| ≥ M 2K |Y |. Hence |ϕ(A )| ≤ 2K M |A|.
From the denition of the energy and the assumptions of the lemma,

ω(ϕ, A) ≤ M 2K y / ∈Y |A ∩ ϕ -1 (y)| + M y∈Y |A ∩ ϕ -1 (y)| ≤ M 2K |A| + M |A |. It follows that |A | ≥ 1 2K |A|.
What Balog-Szemerédi-Gowers theorem roughly says is that if ϕ is a group law (or has some injectivity property similar to a group law) and A is a Cartesian product then the set A in the conclusion of Lemma 2.5 can be chosen to be a Cartesian product.

For discretized sets we have an analogous notion of energy.

Denition. Let ϕ : X → Y be a Lipschitz map between metric spaces and A a bounded subset of X. We dene the ϕ-energy of A at scale δ as

ω δ (ϕ, A) = N δ {(a, a ) ∈ A × A | d(ϕ(a), ϕ(a )) ≤ δ} .
Here we adhere to the convention that the distance on a Cartesian product X × Y of metric spaces is such that (i) The analogue of inequality (2.6) is true :

(2.7)

ω δ (ϕ, A) n,m N δ (A) 2 N δ (ϕ(A)) . (ii) If ψ : A → R n is another K-Lipschitz map, then (2.8
)

ω δ (ϕ, ψA) n K 2n ω δ (ϕ • ψ, A).
(iii) Let à be a maximal δ-separated subset of A.

Then

ω δ (ϕ, A) n # (a, a ) ∈ Ã × Ã | ϕ(a) -ϕ(a ) ≤ (1 + 2K)δ .
Proof. Let à be a maximal δ-separated subset of A.

(i) Let Y be a nite subset of R m such that ϕ(A) is covered by the balls of radius δ 2 centered at points in Y . Then

| Ã| ≤ y∈Y Ã ∩ ϕ -1 B(y, δ 2 ) ,
and by the denition of ω δ ,

y∈Y Ã ∩ ϕ -1 B(y, δ 2 ) 2 n ω δ (ϕ, A).
It follows from the Cauchy-Schwarz inequality that

| Ã| 2 n |Y | ω δ (ϕ, A).
(ii) It is an easy consequence of (2.4).

(iii) For each a ∈ A, choose ã ∈ Ã such that a -ã ≤ δ. Let Ω be a maximal 8δ-separated subset of {(a, a ) ∈ A × A | ϕ(a) -ϕ(a ) ≤ δ}.
Then the map (a, a ) → (ã, ã ) is injective from Ω to the set on the right-hand side of the desired inequality.

We will need the following additive version of Balog-Szemerédi-Gowers Theorem which gives a criterion for the additive energy between two sets to be large. See [START_REF] Tao | Product set estimates for non-commutative groups[END_REF]Theorem 6.10] where it is proved in a much broader context. Theorem 2.7 (Balog-Szemerédi-Gowers Theorem). Let A, B be bounded sub-

sets of R n . If ω δ (+, A × B) ≥ 1 K N δ (A) 3 2 N δ (B) 3 2 ,
then there exists

A ⊂ A and B ⊂ B such that N δ (A ) n K -O(1) N δ (A), N δ (B ) n K -O(1) N δ (Y )
and

N δ (A + B ) n K O(1) N δ (A) 1 2 N δ (B) 1 2 .

2.4 Basic sum-product estimates

First consider a situation where A ⊂ End(R n ) is a set of endomorphisms acting on a bounded subset X ⊂ R n in a Euclidean space. Let K ≥ 2 be a parameter. Similarly to the consideration of "good elements" in [13, Proposition 3.3] and the basic construction in [58, Proposition 3.1], we dene at scale δ > 0,

S δ (X; K) = f ∈ B End(R n ) (0, K) | N δ (X + f X) ≤ KN δ (X) .
Here are some basic properties of S δ (X; K). The main idea is that it behaves like an approximate ring.

Lemma 2.8. Let X ⊂ B(0, K) be a subset of R n , we have

(i) If a ∈ S δ (X; K) and b ∈ End(R n ) such that a -b ≤ Kδ, then b ∈ S δ (X; K O(1) ) (ii) If Id, a, b ∈ S δ (X; K), then a + b, a -b and ab all belong to S δ (X; K O(1)
).

(iii) Suppose that a invertible and a

-1 ≤ K. If a ∈ S δ (X; K), then a -1 ∈ S δ (X; K O(1)
).

(iv) If Id, a 1 , . . . , a s ∈ S δ (X; K), then

N δ (X + a 1 X + • • • + a s X) ≤ K O(1) N δ (X).
(v) If Id, a ∈ S δ (X; K), then for all ρ ≥ δ, we have

N ρ (X + aX) ≤ K O(1) N ρ (X).
In other words, a ∈ S ρ (X; K O(1) ).

Proof. (i) If N δ (X + aX) ≤ KN δ (X) and a -b ≤ Kδ, then

X + bX ⊂ X + aX + B(0, K 2 δ).
Hence N δ (X + bX) ≤ K O(1) N δ (X).

(ii) Let a, b ∈ S δ (X; K). By Ruzsa's covering lemma (Lemma 2.2),

aX ⊂ X -X + O(K) + B(0, δ), and bX ⊂ X -X + O(K) + B(0, δ).
Hence,

X + (a + b)X ⊂ 3X -2X + O(K 2 ) + B(0, 2δ), X + (a -b)X ⊂ 3X -2X + O(K 2 ) + B(0, 2δ).
Finally by the Plünnecke-Ruzsa inequality (Lemma 2.4),

N δ (X + (a + b)X), N δ (X + (a -b)X) ≤ K O(1) N δ (X).
Moreover, since a ≤ K, we have

X + abX ⊂ X + a(X -X + O(K) + B(0, δ)) ⊂ X + aX -aX + O(K) + B(0, Kδ) ⊂ 3X -2X + O(K 3 ) + B(0, 3Kδ) Hence, N δ (X + abX) ≤ K O(1) N δ (X).
(iii) If a ∈ GL n (R) and a -1 ≤ K, then X + a -1 X = a -1 (X + aX) and hence

N δ (X + a -1 X) ≤ K O(1) N δ (X + aX).
(iv) The argument is similar to that of (ii).

(v) For all ρ ≥ δ we have

N δ (X) ≤ max x∈R n N δ (X ∩ B(x, ρ))N ρ (X)
and for all

x ∈ R n , N δ (X + X + aX) N δ (X ∩ B(x, ρ))N ρ (X + aX).
If Id, a ∈ S δ (X; K), then by (iv),

N δ (X + X + aX) ≤ K O(1) N δ (X).
We obtain the desired estimate by combining the three inequalities above. Now let A be a bounded subset of a nite-dimensional normed algebra E. We can view left multiplications by a ∈ A as elements of End(E). Lemma 2.8 tells us that, if for some K ≥ 2,

N δ (A + a • A) ≤ KN δ (A)
for all a ∈ A, then for any positive integer s there is s = s (s) ≥ 1 such that

N δ (A + a • A) ≤ K s N δ (A)
for all a ∈ A s . Lemma 2.9. Let K ≥ 2 be a parameter.

If A ⊂ B E (0, K) is a subset of a nite-dimensional normed algebra E satisfying N δ (A + A) + N δ (A + A • A) ≤ KN δ (A),
then for any positive integer s,

N δ ( A s ) ≤ K Os(1) N δ (A).
Moreover, for any ρ ≥ δ,

N ρ ( A s ) ≤ K Os(1) N ρ (A).
This lemma is a sum-product analogue of property (1.4) in groups . This discretized version can be proved by mimicking the proof of its discrete counterpart in [START_REF] Breuillard | Lectures on approximate groups[END_REF]Lemma 5.5].

Proof. Without loss of generality, we can assume that the norm on E is submultiplicative and 0 ∈ A. We prove by induction on s that there exists k s ≥ 1 such that (2.9)

A s ⊂ k s A -k s A + O(K ks ; A ks ) + B(0, K ks δ).
This combined with the Plünnecke-Ruzsa inequality (Lemma 2.4) will nish the proof. For s = 2, the inclusion (2.9) is immediate from Ruzsa's covering lemma (Lemma 2.2). In particular, we have (2.10)

A • A ⊂ A -A + O(K; A • A) + B(0, δ).
For the induction step, we show that if (2.9) is true then A s ±A and A •A also satisfy an inclusion of the form (2.9). For A s ± A, this is clear. Multiplying A on the right to both sides of (2.9) yields

A s • A ⊂ k s (A • A) -k s (A • A) + O(K ks ; A ks ) • A + B(0, K ks+1 δ).
By (2.10),

k s (A • A) ⊂ k s A -k s A + O(K k 2 s ; k s A • A) + B(0, k s δ).
For any x ∈ A ks , by the discussion after the proof of Lemma 2.8,

N δ (A+x•A) ≤ K Os(1) N δ (A).
Hence by Ruzsa's covering lemma (Lemma 2.2) again,

x • A ⊂ A -A + O(K Os(1) ; A ks+1 ) + B(0, δ).
Taking union of O(K ks ) of such sets, we obtain

O(K ks ; A ks ) • A ⊂ A -A + O(K Os(1) ; A ks+1 ) + B(0, δ).

Putting these inclusions together gives

A s • A ⊂ (2k s + 1)A -(2k s + 1)A + O(K Os(1) ; A Os(1) ) + B(0, K Os(1) δ),
which nishes the proof of the induction step.

The "moreover" part is obtained by the same argument as in the proof of Lemma 2.8(v).

As a consequence of Lemma 2.9, in order to show that A 3 is substantially larger than A, we can show that A s is much larger than A. That is why the strategy of the proof of Theorem 3.1 is to show that for any 0 > 0 there is s ≥ 1 such that A s contains a ball of radius δ 0 .

Conversely, if a growth statement such as Theorem 3.1 is true then within a bounded number of steps, the set always grows to become δ-dense in a large ball. This kind of phenomenon is often proved using Fourier analysis, as shown by Bourgain [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]Theorem 6]. Below we extend this argument to higher dimensional situation. It is also worth noting that these arguments are analogue of arguments using the high dimension of irreducible representations in groups, such as those used in Sarnak-Xue [START_REF] Sarnak | Bounds for multiplicities of automorphic representations[END_REF], Gowers [START_REF] Gowers | Quasirandom groups[END_REF], Bourgain-Gamburd [START_REF] Bourgain | Uniform expansion bounds for Cayley graphs of SL 2 (F p )[END_REF] in the discrete setting and Bourgain-Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF], Saxcé [START_REF] De Saxcé | Trou dimensionnel dans les groupes de Lie compacts semisimples via les séries de Fourier[END_REF] in the discretized setting. In the following paragraphs, End(R n ) is endowed with the usual operator norm. Proposition 2.10. Let > 0. Given α > 0 and β > 0 such that α + β > n, there exists s = s(α + β -n, n) ≥ 1 such that the following is true for all δ > 0 suciently small. Let µ be a probability measure on B End(R n ) (0, 1) and ν a probability measure on B R n (0, 1). Assume that (i) for all ρ ≥ δ and all ξ, η ∈ R n with ξ = 1,

µ({a ∈ End(R n ) | t aξ ∈ B(η, ρ)}) ≤ δ -ρ α ;
(ii) for all ρ ≥ δ and all x ∈ R n , ν(B(x, ρ)) ≤ δ -ρ β .

Then there exists a 1 , . . . , a s ∈ Supp(µ) such that

B(0, δ s ) ⊂ a 1 X + • • • + a s X -a 1 X -• • • -a s X + B(0, δ)
where X = Supp(ν).

Lemma 2.11. Let , α, β, µ and ν be as in Proposition 2.10. Then for all

ξ ∈ R n with 1 ≤ ξ ≤ δ -1 , (2.11) |ν( t aξ)| dµ(a) n δ -2 ξ -α+β-n n+3 .
This lemma can be viewed as a higher dimensional extension of [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]Theorem 7].

Proof. First we prove that for any 1 ≤ R ≤ 2δ -1 , (2.12)

B(0,R) |ν(η)| 2 dη n δ -R n-β .
For any function ϕ, denote by ϕ -the function x → ϕ(-x). Similarly dene νfor any measure on R n . Choose a smooth function ϕ : R n → R supported on B(0, 1) and having

R n ϕ = 1.
Replace it with ϕ * ϕ -if necessary, we can assume that φ(ξ) ∈ R + for all ξ ∈ R n . From the continuity of φ, there is a constant c > 0 such that

φ(ξ) ≥ 1 2
for all ξ ∈ B(0, c).

For R > 0, set ϕ R (x) = c -n R n ϕ(c -1 Rx), x ∈ R n so that ϕ R ∞ n R n and Supp(ϕ R ) ⊂ B(0, cR -1
) and moreover

∀η ∈ B(0, R), φR (η) = φ cη R ≥ 1 2 .
Thus for all

1 ≤ R ≤ 2δ -1 , B(0,R) |ν(η)| 2 dη R n |ν(η)| 2 φR (η) dη.
By the Parseval identity, the right-hand side is equal to

(2π) n R n ϕ R dν * ν - n ϕ R ∞ (ν * ν -)(B(0, cR -1 )).
Using assumption (ii), the right-hand side can be bounded by

O n (δ -R n-β ).
This nishes the proof of (2.12). Now, consider

H R,t = {η ∈ B R n (0, R) | |ν(η)| ≥ t.} for 1 ≤ R ≤ δ -1 and 0 < t ≤ 1.
Since ν is K-Lipschitz for some constant K depending only on n, we have

H R,t + B(0, t 2K ) ⊂ H R+1, t 2 .
Thus λ(H (t/2K) R,t

)t 2 B(0,R+1) |ν| 2 n δ -R n-β and hence

N t (H R,t ) n δ -t -n-2 R n-β .
Let ξ ∈ R n be a vector of length

1 ≤ ξ = R ≤ δ -1 , then |ν( t aξ)| dµ(a) ≤ t + µ(H ξ R,t ).
where

H ξ R,t = {a ∈ End(R n ) | t aξ ∈ H R,t }.
From a covering of H R,t by t-Balls we can lift to a covering of H ξ R,t by sets of the form

{a ∈ End(R n ) | t aξ ∈ B(η, t)}. Using t ≤ 1, R ≤ δ -1
and assumption (i), we obtain, for all η ∈ R n ,

µ({a ∈ End(R n ) | t aξ ∈ B(η, t)}) ≤ µ({a ∈ End(R n ) | t a ξ R ∈ B( η R , 1 R )}) ≤ δ -R -α .
Therefore,

µ(H ξ R,t ) ≤ δ -R -α N t (H R,t ).
We obtain the desired estimate by setting t = R -α+β-n n+3 .

Proof of Proposition 2.10. Write τ = α+β-n n+3 and set R = min{δ -4 τ , δ -1 }. Let s be a positive integer. Taking the s-power of (2.11) and integrating over the annulus B(0, δ -1 ) \ B(0, R), we obtain

R≤ ξ ≤δ -1 |ν( t aξ)| dµ(a) s dξ ≤ δ -3s R n-τ s
for δ > 0 suciently small. Developing the left-hand side and using Fubini's theorem gives existence of a 1 , . . . , a s ∈ Supp(µ) such that

R≤ ξ ≤δ -1 |ν( t a 1 ξ)| • • • |ν( t a s ξ)| dξ ≤ δ -3s R n-τ s .
Denote by ν the image measure of ν ⊗s by the map

(x 1 , • • • , x s ) → a 1 x 1 + • • • + a s x s .
The above inequality and the choice of R yield

R≤ ξ ≤δ -1 | ν (ξ)| dξ ≤ δ s -4n τ .
Let ψ : R n → R be a smooth function supported on B(0, 1) and with

R n ψ = 1 and moreover ψ(ξ) ∈ R + for all ξ ∈ R n . Set ψ δ (x) = δ -n+n ψ(δ -1+ x) so that it is supported on B(0, δ 1-) and ψδ (ξ) = ψ(δ 1-ξ). The convolution ν * ψ δ is a smooth function supported on B(0, s + 1), hence there is x 0 ∈ Supp(ν * ψ δ ) such that (2.13) ν * ψ δ (x 0 ) n s -n .

By the Parseval identity, for all

x ∈ R n ν * ψ δ (x) = R n e -i ξ,x ν (ξ) φδ (ξ) dξ.
Hence for all x ∈ B(x 0 , δ s )

|ν * ψ δ (x 0 ) -ν * ψ δ (x)| ≤ B(0,R) |1 -e -i ξ,x-x0 | dξ + 2 R≤ ξ ≤δ -1 | ν (ξ)| dξ + 2 ξ ≥δ -1 | ψδ (ξ)| dξ n δ s R n+1 + 2δ s -4n τ + ξ ≥δ -1 | ψ(δ 1-ξ)| dξ Pick s = 4(n+1)
τ + 1 so that the rst two terms are O(δ ). To bound the last integral, we note that since ψ is smooth, we have | ψ(ξ)| m ξ -m for any m > n. Hence the last integral is

ξ ≥δ -1 | ψ(δ 1-ξ)| dξ m δ -m+m ξ ≥δ -1 ξ -m dξ n,m δ -n+m .
Now pick m large enough so that m -n ≥ and we obtain

|ν * ψ δ (x 0 ) -ν * ψ δ (x)| n, δ .
Combined with (2.13) we have B(0, δ s ) ⊂ Supp(ν ) -Supp(ν ) + B(0, 2δ 1-) when δ is small enough. This is almost what we want except here we need a 2δ 1--neighborhood instead of δ-neighborhood. To nish the proof it suces to see that we can work at the scale

δ 1 = ( δ 2 ) 1 1-
from the beginning. For example, the hypothesis (ii) implies that for all ρ ≥ δ 1 and all

x ∈ R n , ν(B(x, ρ)) ≤ δ -On( ) 1 ρ β .
Recall that all algebras in this document are associative and unital. Proposition 2.12. Let E be a nite-dimensional normed algebra over R. There is an integer s depending on E such that the following holds for all > 0 and for δ > 0 suciently small 1 . Let A ⊂ B E (0, 1). Assume that N δ (A) ≥ δ -dim(E)+ . Then there exist elements a 1 , . . . , a s ∈ A such that

B(0, δ O E ( ) ) ⊂ a 1 A + • • • + a s A -a 1 A -• • • -a s A + B(0, δ).
This proposition can be viewed as a discretized analogue of [START_REF] Breuillard | Lectures on approximate groups[END_REF]Lemma 6.4]. Note also that the statement with right multiplication instead of left one is equally true.

We want be bound ν(m -1 ξ (B(η, ρ))). We know that m ξ ≥ c. Consequently, from the Cartan decomposition of m ξ we see that

m -1 ξ (B(0, ρ)) ⊂ W ξ + B(0, c -1 ρ)
where W ξ is a n -1-dimensional subspace. Hence either m -1 ξ (B(η, ρ)) is empty or there is a 0 ∈ E such that

m -1 ξ (B(η, ρ)) ⊂ a 0 + W ξ + B(0, 2c -1 ρ).
We conclude that

µ {f ∈ End(E) | t f ξ ∈ B(η, ρ) = ν(m -1 ξ (B(η, ρ))) E δ -ρ,
which proves the claim and hence the proposition.

Noncommutative analogues

Let G be connected real Lie group. Let µ be a left-invariant Haar measure on G and d a left-invariant smooth metric on G.

Due to non-zero curvature, the precise estimates in Lemma 2.1 valid in R n does not hold in general. Nevertheless, the same type of estimates hold if we restrict ourself to a compact set and allow constants to depend on this compact. Actually, (G, d) is a locally reasonable metric group following the denition of Tao for all x, y, g ∈ B(1, R).

(iii) For any R ≥ 1, we have

µ(B(1, 2r)) G,R µ(B(1, r))
for all 0 < r < R.

Form these properties, estimates similar to Lemma 2.1 follows. Let us recall some of them, for more details see [START_REF] Tao | Product set estimates for non-commutative groups[END_REF][START_REF] Bourgain | On the Erd®s-Volkmann and Katz-Tao ring conjectures[END_REF]

. Let R ≥ 1. Let X ⊂ B(1, R). For all 0 < δ ≤ 1, we have X B(1, δ) ⊂ B(1, O G,R (δ))X, B(1, δ)X ⊂ X B(1, O G,R (δ)), (2.14) µ(X (δ) ) µ(B(1, δ)) G,R N δ (X),
and

N 2δ (X) G,R N δ (X) G,R N δ (X (δ) ).
There is also a useful property specic to Lie groups. For all 0 < δ ≤ 1 and all closed connected subgroups H < G,

N δ (B H (1, 1)) H δ -dim(H) .
The Plünnecke-Ruzsa inequality does not hold for noncommutative groups. However the Ruzsa triangular inequality still holds in the noncommutative setting. From it we can deduce a weak but noncommutative version of Plünnecke-Ruzsa inequality. In the discretized setting, its statement is the following. Lemma 2.13 (Tao [57,Theorem 6.8]). Let R ≥ 1 and K ≥ 2 be parameters.

If A ⊂ B G (1, R) satises N δ (A 3 ) ≤ KN δ (A) then for all s ≥ 1, N δ (A ∪ {1} ∪ A -1 ) s G,R K Os(1) N δ (A).
It is worth noting that the Balog-Szemerédi-Gowers Theorem also holds in the noncommutative and δ-discretized setting, see [57, Theorem 6.10].

Metric entropy version of the Petridis lemma

In this subsection, we prove an discretized version of a result known as the Petridis lemma [START_REF] Petridis | New proofs of Plünnecke-type estimates for product sets in groups[END_REF]. It implies the Plünnecke-Ruzsa inequality in the commutative setting and thus can be viewed as a substitute for Plünnecke-Ruzsa inequality in the noncommutative setting. Lemma 2.14 (Metric entropy version of the Petridis lemma). Let (G, d) be a locally reasonable metric group. Let R ≥ 1 and K ≥ 2 be parameters and let 0 < δ < 1 be a scale. If A and B are subsets of B G (1, R) such that N δ (AB) ≤ KN δ (A), then there exists A 0 ⊂ A such that for any subset

Y ⊂ B G (1, R), N δ (Y A 0 B) G,R KN δ (Y A 0 ).
Like in [START_REF] Tao | Product set estimates for non-commutative groups[END_REF], the strategy is to rst prove a continuous version. Then the lemma follows from properties of locally reasonable metric groups such as estimate (2.14). Till the end of this section, G denote a locally compact Lie group and µ an left-invariant Haar-measure.

The main idea in Petridis' proof is to consider a subset A 0 ⊂ A which minimizes the ratio |A0B| |A0| . So in the continuous setting we want a subset A 0 minimizing the ratio µ(A0B) µ(A0) . Let B denote the Borel σ-algebra of a locally compact group G. Write B >0 for the set of all Borel subsets of positive measure. Let B ⊂ G be a measurable relatively compact subset with positive measure and dene f :

B → R + ∪ {+∞} as f (A) = µ(AB), ∀A ∈ B.
Properties of the function f can be summarized as follows.

(i) (Monotonicity) for all

A, A ∈ B, if A ⊂ A , then f (A) ≤ f (A ). (ii) (Continuity from below) if (A n ) is sequence of measurable sets with A n ⊂ A n+1 for all n, then f ( n≥1 A n ) ≤ sup n f (A n ).
(iii) (Submodularity) for all A, A ∈ B,

f (A ∪ A ) + f (A ∩ A ) ≤ f (A) + f (A ).
(iv) (Bounded away from 0) there exists c > 0 such that f (A) ≥ c for all A ∈ B >0 .

(v) (Left-invariance) for all A ⊂ B and all g ∈ G, f (gA) = f (A).

From now on we can forget the denition of f and only use the above properties.

The only diculty for transferring Petridis' proof to the continuous setting is to prove the existence of sets minimizing the ratio f (A ) µ(A ) where A ranges over all subsets of A with positive measure. Lemma 2.15. Let A ⊂ G be a measurable subset of nite positive measure.

Let A >0 denote the set {A ∈ B >0 | A ⊂ A}. Assume that f : A → R + is a function satisfying properties (i)-(iv) above. Then the inmum K = inf A ∈A>0 f (A ) µ(A )
is reached. Moreover, countable unions of minimizing sets are minimizing. Consequently, up to a null set, there is a unique minimizing set of maximal measure. Any minimizing set is a subset of this set up to a null set.

Proof. We rst show that nite unions of nearly minimizing sets are nearly minimizing. More precisely we claim that if A , A ∈ A >0 are such that (2.15) f (A ) ≤ (K + )µ(A ) and f (A ) ≤ (K + )µ(A )

for some , ≥ 0, then

f (A ∪ A ) ≤ (K + + )µ(A ∪ A ).
To prove the claim, we note that f (A ∩ A ) ≥ Kµ(A ∩ A ) by the denition of K. Substituting this and (2.15) into the submodularity inequality yields

f (A ∪ A ) ≤ (K + )µ(A ) + (K + )µ(A ) -Kµ(A ∩ A ).
Then the monotonicity and modularity of µ gives the claim. Now choose a sequence (A n ) n≥1 of measurable sets with positive measure such that

f (A n ) ≤ (K + 2 -n ). Note that by the condition (iv), µ(A n ) ≥ c K+1 for any n ≥ 1. Hence µ(lim sup n→+∞ A n ) = lim N →+∞ µ( n≥N A n ) > 0.

By the claim, for all

k ≥ 1 f ( N +k n=N A n ) ≤ (K + 2 1-N )µ( N +k n=N A n ).
Taking the limit for k → +∞ and using condition (ii), we obtain

f ( n≥N A n ) ≤ (K + 2 1-N )µ( n≥N A n ).
Finally using condition (i) and taking the limit for N → +∞, we obtain

f (lim sup n→+∞ A n ) ≤ Kµ(lim sup n→+∞ A n ).
This proves the existence of minimizing sets.

The claim above already shows that nite unions of minimizing sets are minimizing. The fact that this is also true for countable unions follows from the continuity from below of f and µ. The union of a sequence (A n ) of minimizing sets with µ(A n ) tending to the supremum of the measure of all minimizing sets is a minimizing set of maximal measure. The uniqueness follows immediately.

Lemma 2.16 (Continuous version of the Petridis lemma). Let

f : B → R + ∪
{+∞} be a function satisfying properties (i)-(v) on page 26. Let A be a measurable subset with 0 < µ(A) < +∞. Then there exists a Borel set A 0 ⊂ A such that for any countable subset

Y ⊂ G, f (Y A 0 ) ≤ f (A) µ(A) µ(Y A 0 ).
Proof. The previous lemma shows the existence of a Borel subset A 0 ⊂ A such that

f (A 0 ) µ(A 0 ) = K = inf A ⊂A µ(A )>0 f (A ) µ(A ) ≤ f (A) µ(A) .
We consider the collection of subsets

Y ⊂ G such that f (Y A 0 ) ≤ Kµ(Y A 0 ) < +∞.
This collection contains {1}. It is closed under G-translation on the left by the left-invariance of f and µ. We claim that it is also closed under adding the identity element. Indeed, by the submodularity,

f (Y A 0 ∪ A 0 ) + f (Y A 0 ∩ A 0 ) ≤ f (Y A 0 ) + f (A 0 ).

By the denition of K, f (Y A

0 ∩ A 0 ) ≥ Kµ(Y A 0 ∩ A 0 ). Hence f ((Y ∪ {1})A 0 ) ≤ K(µ(Y A 0 ) + µ(A 0 ) -µ(Y A 0 ∩ A 0 )) = Kµ((Y ∪ {1}) ∪ A 0 ).
Thus, the conclusion of the lemma holds for any nite subset Y . Too see that it is also true if Y is countable it suces to use the continuity from below. Now we deduce Lemma 2.14 from Lemma 2.16.

Proof of Lemma 2.14. Let G, R, A, B and K be as in the statement of Lemma 2.14.

From N δ (AB) ≤ KN δ (A) and the basic properties of locally reasonable metric groups, we deduce that

µ(A (δ) B (δ) ) G,R N δ (AB)µ(B(1, δ)) G,R KN δ (A)µ(B(1, δ)) G,R Kµ(A (δ) )
Now we apply Lemma 2.16 to the set of positive measure A (δ) and the function

f : A → µ(A B (δ) ). We get A 0 ⊂ A (δ) such that for any countable set Y ⊂ G, µ(Y A 0 B (δ) ) G,R Kµ(Y A 0 ). Set A 1 = A (δ) 0 ∩ A so that we have both A 1 ⊂ A (δ) 0 and A 0 ⊂ A (δ) 1 . Let Y ⊂ B G (1, R). We claim that N δ (Y A 1 B) G,R KN δ (Y A 1 ),
which nishes the proof of Lemma 2.14.

To prove the claim, consider Ỹ ⊂ Y a nite subset such that Y ⊂ Ỹ (δ) . We know

µ( Ỹ A 0 B (δ) ) G,R Kµ( Ỹ A 0 ).
On the one hand, we can bound from above the right hand side by

µ( Ỹ A 0 ) ≤ µ(Y A (δ) 1 ) ≤ µ((Y A 1 ) (O G,R (δ)) ) G,R N δ (Y A 1 )µ(B(1, δ)).
On the other hand, we can bound from below the left hand side : there exists C G,R 1 such that

( Ỹ A 0 B) ( δ C ) ⊂ Ỹ A 0 B (δ) and Y A 1 B ⊂ Ỹ (δ) A (δ) 0 B ⊂ ( Ỹ A 0 B) (Cδ) . Hence µ( Ỹ A 0 B (δ) ) ≥ µ(( Ỹ A 0 B) ( δ C ) ) G,R N δ C ( Ỹ A 0 B)µ(B(1, δ C )).
Moreover, we have

µ(B(1, δ C )) G,R µ(B(1, δ))
and

N δ C ( Ỹ A 0 B) G,R N Cδ (( Ỹ A 0 B) (Cδ) ) G,R N Cδ (Y A 1 B) G,R N δ (Y A 1 B).
Putting all these inequalities together, we obtain the claim.

Chapter 3

Sum-product estimates in matrix algebras

In the chapter we generalize Bourgain's discretized sum-product theorem to matrix algebras. By normed algebra we mean an associative unital algebra over R endowed with a norm that makes the underlying linear space a normed vector space. Let E be a normed algebra. We want to understand, given a bounded subset A ⊂ E satisfying similar properties as in Theorem 1.4, how N δ ( A s ) grows and whether (1.3) or similar estimates hold. If we ask these questions for general real algebras, they can be as hard as the Freiman problem1 as illustrated by the following example. Let A 0 be a bounded subset of R containing 0. Consider A the set of matrices of the form 1 a 0 1 with a ∈ A 0 . Then for any positive integer s, every element in A s is of the form k a 0 k with a ∈ s A 0 and k ∈ {-s , . . . , s } where s is an integer depending on s. Conversely, for every a ∈ sA 0 , we have s a 0 s ∈ A s . Hence

N δ (sA 0 ) ≤ N δ ( A s ) s N δ (s A 0 ).
This means the growth of A under addition and multiplication is somehow equivalent to the growth of A 0 under only addition.

That is why we will restrict our attention to simple algebras. By the Wedderburn structure theorem and the Frobenius theorem, we know that a simple real algebra of nite dimension is isomorphic to M n (R), M n (C) or M n (H), the algebra of n × n matrices over the real numbers, the complex numbers, or the quaternions, for some n ≥ 1.

Theorem 3.1. Let E be a normed simple real algebra of nite dimension. Given κ > 0 and σ < dim(E), there is > 0 depending on E, κ and σ such that the following holds for δ > 0 suciently small. Let A be a subset of E, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-,
(iv) for every proper subalgebra W ⊂ E, there is a ∈ A such that d(a, W ) ≥ δ .

Then, (3.1)

N δ (A + A) + N δ (A + A • A) ≥ δ -N δ (A).
The case E = C is due to Bourgain and Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF]. So our result is new for dim(E) > 2.

The assumption (ii) is a non-concentration condition. It is to avoid the situation where A is a union of a bounded number of small balls. A subset A ⊂ E satisfying the condition (iv) will be said to be δ -away from subalgebras. This is the additional condition compared to the one-dimensional case. Without it A can be trapped in a small neighborhood of a proper subalgebra. Note the conclusion (3.1) is slightly weaker than that of Theorem 1.4. Here, instead of A • A, we need A + A • A to see the growth. Actually, the estimate (1.3) fails under the same assumptions as soon as dim(E) is greater than 1. Indeed, if A is a union of a segment of unit length and an orthonormal basis of E, then the set A satises the assumptions2 of Theorem 3.1 but A + A and A • A are both unions of a bounded number of unit segments. Thus (1.3) fails for such A.

Using the fact that all norms on a nite-dimensional linear space are equivalent, it is easy to see that the constant > 0 can be made independent of the choice of the norm while scale δ need to be smaller than a constant δ 0 depending on E, its norm, σ and κ. Moreover, this constant δ 0 can be made uniform for norms ranging in a compact set (for the topology of pointwise convergence). However, the dependence on the norm can not be removed completely as illustrated by the following example. Let E = C and A = [0, 1] • i. For any r > 0, consider the norm dened by ∀x, y ∈ R, x + iy r = r|x| + |y|. Then the assumptions of Theorem 3.1 are satised but N δ (A + A)

+ N δ (A + A • A) N δ (A) if r < δ.
Our second result concerns linear actions on Euclidean spaces. Let X be a bounded subset of the Euclidean space R n . Let A ⊂ End(R n ) be a collection of linear endomorphisms. We can ask whether X grows under addition and transformation by elements of A, provided that A is suciently rich. Theorem 3.2. Let n be a positive integer. Given κ > 0 and σ < n, there is > 0 such that the following holds for δ > 0 suciently small. Let A be a subset of End(R n ) and X a subset of R n , assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) for every nonzero proper linear subspace W ⊂ R n , there is a ∈ A and w ∈ B W (0, 1) such that d(aw, W ) ≥ δ . (iv) X ⊂ B(0, δ -), (v) ∀ρ ≥ δ, N ρ (X) ≥ δ ρ -κ , (vi) N δ (X) ≤ δ -σ-.
Then, (3.2)

N δ (X + X) + max a∈A N δ (X + aX) ≥ δ -N δ (X),
where aX = {ax | x ∈ X}.

This improves a previous result of Bourgain and Gamburd [11, Proposition 1].

As a simple corollary, we can obtain a "sum-bracket" estimate in simple Lie algebras. If A is a subset of a Lie algebra g, write

[A, A] = {[a, b] | a, b ∈ A}.
Corollary 3.3. Let g be a normed3 simple Lie algebra of nite dimension.

Given κ > 0 and σ < dim(g), there is > 0 such that the following holds for δ > 0 suciently small. Let A be a subset of g, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) N δ (A) ≤ δ -σ-, (iv) for every proper Lie subalgebra W of g, there is a ∈ A such that d(a, W ) ≥ δ .
Then,

N δ (A + A) + N δ (A + [A, A]) ≥ δ -N δ (A).

Outline of the proofs

Both Theorem 3.1 and Theorem 3.2 are deduced from the following theorem.

Theorem 3.4. Let E be a normed simple real algebra of nite dimension. Given κ > 0 and 0 > 0, there is > 0 and an integer s ≥ 1 such that the following holds for δ > 0 suciently small. Let A be a subset of E, assume that

(i) A ⊂ B(0, δ -), (ii) ∀ρ ≥ δ, N ρ (A) ≥ δ ρ -κ , (iii) A is δ -away from subalgebras.
Then, B(0, δ 0 ) ⊂ A s + B(0, δ).

Note that each of the conditions (ii) and (iii) rules out one obvious obstruction for A s to grow. Indeed, rstly, if A is covered by a bounded number of balls of radius ρ with ρ < δ 0 , then A s is covered by O s (1) balls of radius ρ. Secondly, if A is contained in the unit ball 4 and in the ρ-neighborhood of a proper subalgebra with ρ < δ 0 , then A s is contained in the O s (ρ)-neighborhood of the same proper subalgebra.

The main ingredient in the proof of Theorem 3.4 is a sum-product theorem [START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF]Corollary 8] due to Bourgain-Gamburd concerning the ring C n , the n-fold direct product of C with itself. Let n be a positive integer. We denote by ∆ the set of diagonal matrices in M n (C).

Theorem 3.5 ). Given κ > 0 and n a positive integer, there is a positive integer s ≥ 1 such that, for δ > 0 suciently small, the following holds. Let A be a subset of M n (C). Assume that (i) A ⊂ B(0, 1),

(ii) N δ (A) ≥ δ -κ , (iii) A ⊂ ∆ + B(0, δ).
Then there is η ∈ ∆ with η = 1 such that

[0, δ α ]η ⊂ A s + B(0, δ α+β ),
with some 0 ≤ α < C(n, κ) and some β > c(n, κ) > 0.

Let us sketch the proof of Theorem 3.4. In the following paragraphs, each s stands for some unspecied integer that can be bounded in terms of E, κ. In order to use the Bourgain-Gamburd theorem above, we need rst to embed the algebra E in M n (C) and then produce a lot of nearly simultaneously diagonalizable elements in A s . The standard way (since [START_REF] Helfgott | Growth and generation in SL 2 (Z/pZ)[END_REF]) to produce such elements is to use the fact that the centralizer of a matrix with n distinct eigenvalues is simultaneously diagonalizable. Since the set of matrices with at least one multiple eigenvalue is an algebraic subvariety of M n (C), to nd an element a ∈ A s with n distinct eigenvalues we use the technique of "escape from subvarieties", rst developed in [START_REF] Eskin | On uniform exponential growth for linear groups[END_REF]. For our discretized setting, a quantitative version of this technique is required since distance matters. For Lie groups, this is established in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]. Here we adapt the argument in the sum-product setting.

Once we have such an element a, we consider the map ϕ : x → ax -xa. We distinguish two cases.

(a) If ϕ(A) is large (N δ (ϕ(A)) ≥ δ κ N δ (A) with κ = κ 3 dim(E)
), then we will prove N δ ( A s ) ≥ δ -κ N δ (A) in this case. We remark that all element in ϕ(A) have zero trace. Hence if B is a set of matrices with a lot of dierent traces, then ϕ(A) + B contains a lot of disjoint translates of ϕ(A). In particular, N δ (ϕ(A) + B) N δ (ϕ(A))N δ (tr(B)). Thus, it suces to establish a lower bound on the size of the set of traces of A s . Indeed, we can prove tr( A s ) ≥ δ -2κ using the fact that the bilinear form (x, y) → tr(xy) is non-degenerate.

(b) Otherwise the set A must have a large intersection with a ber of ϕ, i.e.

there is y ∈ M n (C) such that N δ (A∩ϕ -1 (B(y, δ))) ≥ δ -κ . The dierence set of the above intersection consists of nearly simultaneously diagonalizable matrices. Then we can apply Theorem 3.5 to get a small segment at a smaller scale (a segment of length δ α is inside the δ α+β -neighborhood of A s , where α, β and s are the constants given by Theorem 3.5).

What we do is to repeat the same argument to A s if case (a) happens. After a bounded number of times, case (a) won't be possible because A s ⊂ B(0, O s (δ -Os( ) )). Hence eventually, case (b) is true, i.e. inside A s , there is a segment of direction ξ and length δ α at scale δ α+β . Then, using the fact that the two-sided ideal generated by ξ is the whole algebra E, we can prove that the small segment will grow into a small ball under left and right multiplication by elements of A.

This almost nishes the proof. The only problem is that the ball obtained is not large enough and it is at a dierent scale than δ. As in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF], this issue can be solved by applying the above argument at various scales ranging from δ

1 α+β to δ 0 α .
That is how the proof of Theorem 3.4 goes. To deduce Theorem 3.1 from it, we argue by contradiction and use Lemma 2.9 : if both A + A and A + A • A are small (i.e. (3.1) fails), then for every s, A s is small, and thus cannot grow into a large ball as Theorem 3.4 asserts.

To prove Theorem 3.2, a little more work is needed. First, in the special case where the collection of endomorphisms is so large that for every x ∈ X, Ax = {ax | a ∈ A} contains a ball of radius x , a Fubini-type argument yields (3.2). Then, using Lemma 2.8, we know that if (3.2) fails, then we have an upper bound for N δ (X + aX) for every a ∈ A s , s ≥ 1. Therefore, the idea of the proof is to apply Theorem 3.4 to make A grow into a fat ball in some subalgebra E ⊂ M n (R) so that we can use the special case. Here the subalgebra E can be understood as the subalgebra approximately generated by the set A. It inherits the irreducibility property (assumption (iii) in Theorem 3.2) from A. In particular, R n is an irreducible representation of E. Hence, by the Wedderburn structure theorem, E is isomorphic to

M n (R) or M n 2 (C) or M n 4 (H).
Here, a technical issue appears : in Theorem 3.4, the result depends on the norm on E. In the present situation, the norm on E is induced from that on M n (R). To have a control on it, we need a quantitative version of the Wedderburn theorem. Indeed, we show that under the quantitative irreducibility condition (iii) of Theorem 3.2, the normed algebra E is isomorphic to one of the three matrix algebras endowed with standard operator norm via a bi-Lipschitz map with Lipschitz constant controlled independently of A.

Organization of Chapter 3

In Section 3.1 we introduce some denitions and notation and then recall the ojasiewicz inequality from the theory of semianalytic sets. Sections 3.23.4 prepare for the proof of the main results. More precisely, Section 3.2 is dedicated to the "escape from subvariety" technique. Section 3.3 deals with a lower bound on the size the set of traces. Then in Section 3.4 we establish an eective version of the Wedderburn structure theorem. We complete the proof of Theorem 3.4 and deduce Theorem 3.1 in Section 3.5. Finally Theorem 3.2 is proved in Section 3.6 and Corollary 3.3 is deduced in Section 3.7.

Preliminaries

We rst set up notation and terminology and then recall the ojasiewicz inequality.

Notations and denitions

Throughout this chapter, n denotes a positive integer. Most of our estimates are about objects in some ambient space (a normed vector space or a normed algebra) and we write f V g and f = O V (g) to indicate that the implied constant depends not only on the dimension of V but also on the norm of V . We will omit the subscript when it depends only on the dimension n.

We endow the space R n with its usual Euclidean norm • and C n and H n with their respective l 2 -norm. All algebras are over R and unital. In an algebra E, 1 E denotes the multiplicative identity. All subalgebras of E contain 1 E . When K is a division algebra over R, denote by M n (K) the algebra of n by n matrices with coecients in K. For a real linear space V , denote by End(V ) the algebra of real endomorphisms of V . We identify End(R n ) with M n (R) in the usual way.

Since all our spaces are normed, we will need a notion of good bases : those which are well spaced. When V is R n or C n endowed with l 2 -norm, recall that its norm induces an l 2 -norm on each of its exterior powers. In this case the best bases are clearly orthonormal ones. Note that a basis (a 1 , . . . , a n ) is orthonormal if and only if ∀k, a k ≤ 1 and

a 1 ∧ • • • ∧ a n ≥ 1.
If we loosen this condition, we get a notion of good bases. However, the norm on an exterior power of V is properly dened only when V is equipped with an l 2 -norm and we will deal with other norms such as the operator norm on End(R n ). Thus, we need an equivalent formulation. Lemma 3.6. Let (a 1 , . . . , a n ) be a basis of a normed vector space V over R or C, then the following conditions are equivalent in the sense that if the i-th condition holds for some 0 < ρ i ≤ 1 then the j-th condition holds for some

ρ j V ρ O(1) i . (i) For all k = 1, . . . , n, a k ≤ ρ -1 1 and d(a k , Span(a 1 , . . . , a k-1 )) ≥ ρ 1 . (ii) For all k = 1, . . . , n, a k ≤ ρ -1 2 and all x ∈ V , its coordinates (x k ) k in the basis (a k ) k satisfy, ∀k, |x k | ≤ ρ -1 2 x .
Moreover, if the norm on V is an l 2 -norm, then they are also equivalent to the following conditions.

(iii) For all k = 1, . . . , n, a k ≤ ρ -1 3 and a 1 ∧ • • • ∧ a n ≥ ρ 3 . (iv) Any endomorphism that maps an orthonormal basis to (a 1 , . . . , a n ) is ρ -1 4bi-Lipschitz.

In condition (i), we adhere to the convention that Span(∅) means the zero subspace. This lemma is already known in [START_REF] Eskin | On uniform exponential growth for linear groups[END_REF]Lemma 7.5] and [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]Lemma 2.16]. We give an alternative proof.

Proof. Every norm on a nite-dimensional linear space is equivalent to an l 2norm. Hence it suces to prove the equivalences in the case where V = R n or C n endowed with the standard norm. First, (i) implies (iii) since we have

a 1 ∧ • • • ∧ a n = n k=1 d(a k , Span(a 1 , . . . , a k-1 )).
To see that (iii) implies (ii), let x ∈ E, then

x = x 1 a 1 + • • • + x n a n with (x i ) i the coordinates of x in (a i ) i . On the one hand, x ∧ a 2 ∧ • • • ∧ a n ≤ x a 2 • • • a n ≤ ρ -(n-1) 3
x .

On the other hand,

x ∧ a 2 ∧ • • • ∧ a n = x 1 a 1 ∧ • • • ∧ a n so x ∧ a 2 ∧ • • • ∧ a n = |x 1 | a 1 ∧ • • • ∧ a n ≥ ρ 3 |x 1 |. Hence |x 1 | ≤ ρ -n 3
x and the proof is similar for the other coordinates. Equivalence between (ii) and (iv) is clear. Finally, (iv) implies (i) because the inequality in (i) holds for an orthonormal basis with ρ 1 = 1 and a ρ -1 4 -bi-Lipschitz map will only introduce a factor ρ -1

4
or ρ 4 to these inequalities.

Remark. From the proof we see that the implied constant in the notation V in the lemma can be 1 if V is endowed with an l 2 -norm. Also, if V 0 is a xed normed vector space, then this implied constant is uniform for all subspaces V of V 0 .

Lemma 3.6 suggests the following denition.

Denition. Let 0 < ρ ≤ 1 be a parameter. We say a basis (a 1 , . . . , a n ) of a normed vector space V is ρ-almost orthonormal if it satises the condition (i) in Lemma 3.6 with ρ 1 = ρ.

Denition. Let 0 < ρ ≤ 1 be a parameter. Let V be a normed vector space.

We say that a subset A ⊂ V is ρ-away from linear subspaces if for every proper linear subspace W ⊂ V , there is a ∈ A such that d(a, W ) ≥ ρ.

Let E be a normed algebra. We say that a subset A ⊂ E is ρ-away from subalgebras if for every proper subalgebra W ⊂ E, there is a ∈ A such that

d(a, W ) ≥ ρ.
In a similar way, we dene the notion of being ρ-away from Lie subalgebras.

We have the following observation. Lemma 3.7. Let 0 < ρ ≤ 1 2 be a parameter. In a normed vector space V of nite dimension, if a subset A ⊂ B(0, ρ -1 ) is ρ-away from linear subspaces, then A contains a ρ-almost orthonormal basis. Conversely, if A contains a ρ-almost orthonormal basis, then A is ρ O V (1) -away from subspaces.

Proof. Assume that A ⊂ B(0, ρ -1 ) is ρ-away from linear subspaces. We can construct a ρ-basis from the set A by induction. For k = 1, . . . , dim(V ), suppose that a 1 , . . . , a k-1 are constructed, then Span(a 1 , . . . , a k-1 ) is a proper subspace of V . Hence there is a k ∈ A such that d(a k , Span(a 1 , . . . , a k-1 )) ≥ ρ.

Conversely, assume that A contains a ρ-almost orthonormal basis (a i ). For any proper linear subspace W ⊂ V , there is x ∈ V such that x = d(x, W ) = 1. By Lemma 3.6, we can write 1) , for all i. Consequently,

x = i x i a i , with |x i | ≤ ρ -O V (
d(x, W ) ≤ i |x i |d(a i , W ) ≤ ρ -O V (1) i d(a i , W ).
Hence there is i such that d(a i , W ) ≥ ρ O V (1) . Denition. Let 0 < ρ ≤ 1 be a parameter. Let A be subset of End(R n ). We say that A acts ρ-irreducibly on R n if for every nonzero proper linear subspace W ⊂ R n , there is a ∈ A and w ∈ B W (0, 1) such that d(aw, W ) ≥ ρ.

We say that a subalgebra E ⊂ End(R n ) acts ρ-irreducibly on R n if the set B E (0, 1) acts ρ-irreducibly on R n .

ojasiewicz inequality

The ojasiewicz inequality [42, Théorème 2, page 62] is a powerful tool which allows us to extract quantitative estimates from algebraic facts. Let us recall it here.

Theorem 3.8 (ojasiewicz 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)| ≥ 1 C min(1, d(x, Z)) C
where

Z = {x ∈ M | f (x) = 0}.
Note that we take the minimum between 1 and d(x, Z) to make the inequality true even if Z is empty.

Escaping from subvarieties

In this section we show that if a subset A of a simple algebra is not trapped in any subalgebra then we can escape from any subvariety within a bouned number of steps using addition and multiplication. The number of necessary steps depends only on the ambient algebra E. This is achieved in two steps. First, using only multiplication we can escape from linear subspaces (Proposition 3.11). Then, once the set is away from linear subspaces, we can escape from subvarieties using only addition (Lemma 3.13). Note that everything is quantitative. By escaping a subvariety we mean getting outside a neighborhood of that subvariety.

Escaping from linear subspaces

Let A be subset of a normed algebra E of nite dimension. Obviously, if A is away from linear subspaces, then it is away from subalgebras. We will see in this subsection that the converse is true if we are allowed to replace A with its product set A s .

The following is the subalgebra (and simpler) version of the Lemma 2.5 in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]. The proof is essentially the same. Lemma 3.9. Let 0 < ρ ≤ 1 2 be a parameter. Let A be a subset of a normed algebra E of nite dimension. If A ⊂ B(0, ρ -1 ) and A is ρ-away from subalgebras, then A contains a subset of cardinality at most dim(E) which is ρ O E (1) -away from subalgebras.

Proof. Let C ≥ 1 be a large constant. Suppose that a 1 , . . . , a k-1 are constructed. If {a 1 , . . . , a k-1 } is ρ C -away from subalgebras, then we are done. Otherwise there is a proper subalgebra W such that for all i = 1, . . . , k -1, d(a i , W ) < ρ C . Then choose from A an element a k such that d(a k , W ) ≥ ρ.

We prove by induction that at each step (a 1 , . . . , a k ) is a ρ O E (1) -almost orthonormal basis of its linear span V k = Span(a 1 , . . . , a k ). This is obvious for 1) -almost orthonormal basis (a 1 , . . . , a k-1 ). Hence for every

k = 1. For k ≥ 2, suppose that (a 1 , . . . , a k-1 ) is a ρ O E (1) -almost orthonormal basis of V k-1 . We can write a k = x 1 a 1 + • • • + x k-1 a k-1 + a k with x i ∈ R and a k = d(a k , V k-1 ). Consequently, x 1 a 1 +• • •+x k-1 a k-1 is the decomposition of the vector a k -a k in the ρ O E (
i = 1, . . . k -1, |x i | ≤ 2ρ -O E (1) a k ≤ ρ -O E (1) . Then ρ ≤ d(a k , W ) ≤ k-1 i=1 |x i |d(a i , W ) + a k ≤ ρ -O E (1) max 1≤i≤k-1 d(a i , W ) + a k ≤ ρ C-O E (1) + a k When C is large enough, this implies d(a k , V k-1 ) = a k ≥ ρ 2 . Hence, (a 1 , . . . , a k ) is a ρ O E (1) -almost orthonormal basis of V k .
We conclude that the construction must stop after at most dim(E) steps.

Then we have the analogue of Proposition 2.7 in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF].

Lemma 3.10. Let 0 < ρ ≤ 1 2 be a parameter. Let A be a subset of a normed simple algebra E of nite dimension. If A ⊂ B(0, ρ -1 ) and A is ρ-away from subalgebras, then for every nonzero proper linear subspace W of E, there is w ∈ B W (0, 1) and a ∈ A such that

d(aw, W ) ≥ ρ O E (1) or d(wa, W ) ≥ ρ O E (1) .
Proof. In view of Lemma 3.9, we can assume that A has exactly n = dim(E) elements a 1 , . . . , a n . We can further assume that A ⊂ B(0, 1) for we can replace A with its contraction ρ • A. We will treat the case where the norm on E is Euclidean. The general case follows easily since every norm on E is equivalent to an Euclidean one. Suppose the lemma were false. Then there would be a linear subspace W 0 of dimension 0 < k < n such that for all w ∈ B W0 (0, 1) and all i = 1, . . . , n, d(a i w, W 0 ) < ρ C and d(wa i , W 0 ) < ρ C for some large C. The actual value of this constant will be determined by the ojasiewicz inequality used below.

Consider the map f : Gr(E, k) × E n → R dened by

f (W ; x 1 , . . . , x n ) = n i=1 B W (0,1) d(x i w, W ) 2 + d(wx i , W ) 2 dw
where the integration dw is with respect to the k-dimensional Lebesgue measure on B W (0, 1). This map is well-dened and real analytic. This can be seen by observing that the tautological bundle π : T → Gr(E, k) of the Grassmannian has around every point an analytic local trivialization ϕ :

U × R k → π -1 (U) such that ∀W ∈ U, ϕ(W, •) : R k → π -1 ({W }) W is an isometry of Euclidean spaces.
From the choice of W 0 it follows that f (W 0 ; a 1 , . . . , a n ) ρ C . Hence by the ojasiewicz inequality (Theorem 3.8) applied to the compact set Gr(E, k) × B(0, 1) n , there is

W 1 ∈ Gr(E, k) and b 1 , . . . , b n ∈ E such that f (W 1 ; b 1 , . . . , b n ) = 0 and ∀i, a i -b i < ρ when the constant C is chosen large enough. The map f vanishing on (W 1 ; b 1 , . . . , b n ) is equivalent to every b i being in the subalgebra E W1 = {x ∈ E | xW 1 ⊂ W 1 and W 1 x ⊂ W 1 } .
Now our set A is not ρ-away from the subalgebra E W1 . Therefore E W1 must be the whole algebra E, which in turn implies that W 1 is a two-sided ideal in E. This contradicts the assumption that E is simple. Proposition 3.11. Let 0 < ρ < 1 2 be a parameter. Let A be a subset of a normed simple algebra E of dimension n. Assume that A ⊂ B(0, ρ -1 ) and A is ρ-away from subalgebras. Write A 1 = {1 E } ∪ A. Then for any η ∈ E with η ≥ ρ, the set 1) -away from linear subspaces in E.

A n 1 ηA n 1 contains a ρ O E (1) -almost orthonormal basis of E. Equivalently, A n 1 ηA n 1 is ρ O E (
Proof. We construct the basis inductively. First, let η 1 = η. Then for k = 1, . . . , n -1, suppose that after k steps, we have constructed

η 1 , . . . , η k ∈ A k ηA k such that (η 1 , . . . , η k ) is a ρ O E (1)
-almost orthonormal basis of W k = Span(η 1 , . . . , η k ). By Lemma 3.10, there is w ∈ B W k (0, 1) and a ∈ A such that either d(aw, W ) ≥ ρ O E (1) or d(wa, W ) ≥ ρ O E (1) . Let us deal with the former case, the latter case being similar. We can write w in the ρ O E (1) -almost orthonormal basis (η 1 , . . . , η k ),

w = w 1 η 1 + • • • + w k η k .
By Lemma 3.6, the coecients 1) , ∀i. Hence

|w i | ≤ ρ -O E (
d(aw, W k ) ≤ k i=1 |w i |d(aη i , W k ) ≤ ρ -O E (1) max i=1,...,k d(aη i , W k ).
Hence it is possible to pick i * ∈ {1, . . . , k} so that putting η k+1 = aη i * we have

d(η k+1 , W k ) ≥ ρ O E (1) . Then (η 1 , . . . , η k+1 ) is a ρ O E (1)
-almost orthonormal basis of its linear span.

3.2.2

Escaping from subvarieties, R n case Lemma 3.12. Let d ≥ 1 and 0 < ρ ≤ 1. Let (a 1 , . . . , a n ) be a ρ-almost orthonormal basis of R n . Dene

Γ d = x 1 a 1 + • • • + x n a n | ∀i, x i ∈ {0, . . . , d} .
For any polynomial function P : R n → R of degree at most d, we have

sup x∈B(0,1) |P (x)| n,d ρ -O n,d (1) max γ∈Γ d |P (γ)|.
Proof. We write R d [X i ] 1≤i≤n for the space of polynomials on R n of degree at most d. First consider the case where (a 1 , . . . , a n ) is the canonical basis. Let

Λ d = (x 1 , . . . , x n ) ∈ R n | ∀i, x i ∈ {0, . . . , d} .
By a simple induction on the number of variables n, we see

that if P ∈ R d [X i ] 1≤i≤n
and vanishes on Λ d then it must be the zero polynomial. Therefore the linear map

R d [X i ] 1≤i≤n → R Λ d P → (P (λ)) λ∈Λ d ,
is injective. Hence the coecients of P are controlled by max λ∈Λ d |P (λ)| and consequently for all r ≥ 0,

sup x∈B(0,r) |P (x)| n,d r d max λ∈Λ d |P (λ)|. (3.3)
For the general case consider ψ : R n → R n the unique linear map which sends the canonical basis to (a 1 , . . . , a n ). Thus ψ(Λ d ) = Γ d and, by Lemma 3.6, ψ(B(0, ρ -On (1) )) ⊃ B(0, 1). We obtain the desired estimate by applying inequality (3.3) to the polynomial P • ψ and r = ρ -On (1) .

Combining this lemma with Lemma 3.7, we have the following immediate consequence. Lemma 3.13. Let V be a normed vector space and P : V → R a nonzero polynomial map. Then there is an positive integer s depending only on the degree of P and the dimension of V such that the following holds for any parameters (1) .

0 < ρ ≤ 1 2 . Let A be a subset of V with A ⊂ B(0, ρ -1 ). If A is ρ-away from linear subspaces then there is a ∈ s(A ∪ {0}) such that |P (a)| V,P ρ O V,P

Trace set estimates

To each real algebra E we can associate a trace function tr E and a bilinear form τ E . Let x be an element of E, we dene tr E (x) to be the trace of the left multiplication by x as an endomorphism of E. For example, if E = M n (R), then tr E is n times the usual trace for matrices.

Let x, y ∈ E. We dene τ E (x, y) = tr E (xy). Thus τ E : E × E → R is a symmetric bilinear form. Observe that its kernel ker τ E is a two-sided ideal of E. It follows that τ E is non-degenerate if E is semisimple, i.e. direct sum of simple algebras. Note that the converse is true, but we won't need this fact here.

Let A be a bounded subset of a semisimple algebra E. In this section, we are interested in the size of the trace set of A 2 :

tr E (A 2 ) = {tr E (ab) | a, b ∈ A} .
The aim is to establish a lower bound under appropriate conditions. Here is the result. Lemma 3.14. Given > 0. The following is true for suciently small δ > 0.

Let E be a normed semisimple algebra of dimension n < +∞. Let A be a subset of E such that

• A ⊂ B(0, δ -),
• A is δ -away from linear subspaces in E.

Then N δ (tr E (A 2 )) E δ O( ) N δ (A) 1 n , where n = dim(E).
We begin with a lemma. Lemma 3.15. Let 0 < ρ ≤ 1 2 be a parameter. Let V be a normed vector space of dimension n and τ :

V × V → R a non-degenerate bilinear form. If (a i ) is a ρ-almost orthonormal basis of V , then for all x ∈ V , x V,τ ρ -O(1) max i |τ (a i , x)|.
Lemma 3.17. Let 0 < ρ ≤ 1 2 be a parameter. Let a ∈ M n (C) be a diagonalizable matrix. Assume that a < ρ -1 and its spectrum is a ρ-separated set (it may contain multiple eigenvalues). Then a is diagonal in a ρ O(1) -almost orthonormal basis of C n .

Proof. Let λ 1 , . . . , λ n be the eigenvalues of a (they appear with the corresponding multiplicity). Let v 1 , . . . , v n be the corresponding eigenvectors. Each v i can be chosen to be of unit length and we can further assume that (v i , v j ) = 0 whenever i = j but λ i = λ j . For k = 1, . . . , n, write V k = Span(v 1 , . . . , v k ). We will prove by induction on

k that (v 1 , . . . , v k ) is a ρ O k (1) -almost orthonormal basis of V k . This is clear when k = 1.
Let k be an integer between 1 and n-1. Suppose that

(v 1 , . . . , v k ) is a ρ O k (1) - almost orthonormal basis of V k . Let us show that d(v k+1 , V k ) > ρ O k (1) and thus (v 1 , . . . , v k , v k+1 ) is a ρ O k (1)
-almost orthonormal basis of V k+1 . Without loss of generality we can assume that among the eigenvalues λ 1 , . . . , λ k , only λ l+1 , . . . , λ k are equal to λ k+1 for some l ≤ k. Considering the orthogonal projection of v k+1 onto V k , we can decompose the vector v k+1 into (3.4)

v k+1 = k i=1 x i v i + v k+1 , where x 1 , . . . , x k ∈ C and v k+1 ∈ V ⊥ k . In particular, d(v k+1 , V k ) = v k+1 .
We can then express av k+1 in two dierent ways :

av k+1 = λ k+1 v k+1 = k i=1 λ k+1 x i v i + λ k+1 v k+1 ,
and

av k+1 = k i=1 λ i x i v i + av k+1 . It follows that l i=1 (λ k+1 -λ i )x i v l = λ k+1 v k+1 -av k+1 .
Denote by w k+1 the vector on the right-hand side. Its norm can be bounded : w k+1 ≤ 2 a v k+1 ≤ ρ -2 v k+1 . The left-hand side gives the coordinates of w k+1 in the basis (v 1 , . . . , v k ) which is ρ O k (1) -almost orthonormal by the induction hypothesis. Hence, by Lemma 3.6,

∀i = 1, . . . , l, |λ k+1 -λ i ||x i | ≤ ρ -O k (1) w k+1 ≤ ρ -O k (1) v k+1 .

Hence for all

i = 1, . . . , l, |x i | ≤ ρ -O k (1) v k+1 thanks to the assumption |λ k+1 - λ i | ≥ ρ.
In order to bound |x j | for j ≥ l + 1, we take the scalar product with v j on both sides of (3.4). We obtain

0 = l i=1 x i (v j , v i ) + x j .
Hence for all j = l + 1, . . . k, |x j | ≤ ρ -O k (1) v k+1 . Using (3.4) again we obtain 1) . This nishes the proof of the inductive step.

1 = v k+1 ρ -O k (1) v k+1 and then v k+1 ≥ ρ O k (

Eective Wedderburn theorem in M n (R)

For x ∈ M n (R) and A ⊂ M n (R) denote by C(x) and C(A) their respective centralizers, i.e.

C(x) = {y ∈ M n (R) | xy = yx} , C(A) = {y ∈ M n (R) | ∀x ∈ A, xy = yx} .
Lemma 3.18. Let 0 < ρ ≤ 1 be a parameter. For any g ∈ SL n (R), if g > ρ -n , then the subalgebra C(g) does not act ρ-irreducibly on R n .

Proof. Let g = kal be the Cartan decomposition of g, with k, l ∈ SO(n) and a = diag(a 1 , . . . , a n ) where its singular values a 1 , . . . , a n are arranged so that

a 1 ≥ a 2 ≥ • • • ≥ a n > 0. Assume that a 1 = g > ρ -n . Since a 1 • • • a n = det(g) = 1, there is p ∈ {1, . . . , n -1} such that a p+1 a p < ρ.
Put W = k Span(e 1 , . . . , e p ). It is a nonzero proper linear subspace of R n . We claim that for all x ∈ C(g) ∩ B(0, 1) and all w ∈ B W (0, 1), d(xw, W ) < ρ. Indeed, decomposing every vector v ∈ R n as v = v +v with v ∈ l -1 Span(e 1 , . . . , e p ) and v ∈ l -1 Span(e p+1 , . . . e n ), we see that

d(gv, W ) = av ≤ a p+1 v .
Moreover, for all w ∈ W ,

g -1 w ≤ a -1 p w .
Consequently, for all x ∈ C(g) ∩ B(0, 1) and all w ∈ B W (0, 1), we have xw = gxg -1 w, and thus

d(xw, W ) ≤ a p+1 xg -1 w ≤ a p+1 g -1 w ≤ a p+1 a p < ρ.
Lemma 3.19. Let 0 < ρ ≤ 1 2 be a parameter. If two real matrices x and y ∈ M n (R) are conjugate by a complex matrix g ∈ GL n (C) with g + g -1 < ρ -1 then there is a real matrix h ∈ GL n (R) which also conjugates them and moreover h + h -1 ≤ ρ -O (1) .

Proof. Assume that gxg -1 = y with x, y ∈ M n (R) and g ∈ GL n (C). We write g = g + ig with g , g ∈ M n (R) its real and imaginary part. From gx = yg we see that g x = yg and g x = yg . For λ ∈ C, consider h λ = g + λg . For all λ ∈ C, we have h λ x = yh λ . Hence whenever det(h λ ) = 0, h λ conjugates x and y. What remains to do is to nd appropriate λ ∈ R such that h λ and h -1 λ have bounded norms.

Dene P (λ) = det(h λ ). It is a polynomial with real coecients and its degree is at most n. We know that 1) .

|P (i)| = |det(g)| = |det(g -1 )| -1 g -1 O(1) ρ O(
It is easy to see that the coecients of P are controlled by max λ∈[0,1] |P (λ)|. Hence

|P (i)| max λ∈[0,1] |P (λ)|.
a change of basis matrix satisfying the desired norm estimate. Write ψ(i) and ψ(j) in this new basis,

ψ(i) = i Id n 2 0 0 -i Id n 2 and ψ(j) = A B C D .
The condition (3.5) is then equivalent to A = D = 0 and BC = CB = -Id n 2 . It is easy to check that the conjugation by the block diagonal matrix g = diag(C, Id n 2 ) preserve ψ(i) and conjugates ψ(j) to

0 -Id n 2 Id n 2 0 . Note that g + g -1 = C + B ψ(j) ρ -O(1)
. To conclude the proof we use Lemma 3.19 to make sure the change of basis matrix is real.

Sum-product estimate in simple algebras

We prove Theorem 3.4 and Theorem 3.1 in this section.

Sum-product theorem in C n

We will use Bourgain-Gamburd's sum-product theorem in C n (Theorem 3.5) in the a slightly stronger form. Corollary 3.20. Given κ > 0 and n ≥ 1, there is α ≥ 0, β > 0 and a positive integer s ≥ 1 such that, for > 0 suciently small and δ > 0 suciently small, the following holds. Let A be a subset of M n (C). Assume that

(i) A ⊂ B(0, δ -), (ii) N δ (A) ≥ δ -κ , (iii) A ⊂ ∆ + B(0, δ 1-).
Then there exists η in the algebra generated by A such that η = 1 and (3.6)

[0, δ α ]η ⊂ A s + B(0, δ α+β ).
The corollary mainly says that the segment length δ α and the new scale δ α+β in Theorem 3.5 can be chosen independently of A. This will be very useful when we use this diagonal case. Recall that ∆ denotes the set of diagonal matrices in

M n (C).
Proof. In this proof, let π i (a) denote the i-th diagonal entry of a for any i = 1, . . . , n and any a ∈ M n (C). Partitioning A into at most δ -On( ) parts of diameter 1 and choosing the part with the largest δ-covering number, we see that N δ (B(0, 1) ∩ (A -A)) ≥ δ -κ+On( ) . Thus we can assume that A ⊂ B(0, 1). By working at scale δ 1-, we can further assume A ⊂ ∆ + B(0, δ). Theorem 3.5 says that (3.6) is true for some α and β which may depend on A. Nevertheless, they can be bounded by constants depending only on n and κ. What we need to show is that they can actually be chosen independently of A. This is evident for β since (3.6) gets only weaker when β becomes smaller. Hence there exist 0 ≤ α 0 < C = C(n, κ), s 0 = s 0 (n, κ) ≥ 1 and η ∈ ∆ such that η = 1 and

(3.7) [0, δ α0 ]η ⊂ A s0 + B(0, δ α0+β ).
By replacing α 0 with α 0 + 1 2 β and β with 1 2 β we can assume that α 0 ≥ β. Fix an index i such that |π i (η)| n 1. Consider for any s ≥ 1, the set

Ω s = ω ∈ R + | ∃ξ ∈ A s , ξ ≤ sδ ω , d(ξ, ∆) ≤ sδ ω+ 1 2 β , |π i (ξ)| ≥ 1 s δ ω and [0, 1]ξ ⊂ A s + B(0, sδ ω+β ) .
We need to prove existence of α > 0 and s ≥ 1 depending only on n and κ such that α ∈ Ω s . It follows from (3.7) that α 0 ∈ Ω s0 . Now we show that if ω ∈ Ω s for some s ≥ 1 then there is

s = s (s, n, κ) ≥ 1 such that [ω + α 0 , ω + α 0 + 1 2 β] ⊂ Ω s . Indeed, for any γ ∈ [α 0 , α 0 + 1 2 β], by (3.7), there exists a ∈ A s0 such that δ γ η ∈ a + B(0, δ α0+β ). Thus d(a, ∆) ≤ δ α0+β ≤ δ γ+ 1 2 β and δ γ n π i (a) ≤ a δ γ .
By multiplying a to the relation

[0, 1]ξ ⊂ A s + B(0, sδ ω+β ) we obtain [0, 1]ξa ⊂ A s+s0 + B(0, s a δ ω+β ) ⊂ A s+s0 + B(0, O(s)δ ω+γ+β ).
Moreover, ξa n ξ a sδ ω+γ and

d(ξa, ∆) n d(ξ, ∆) a + ξ d(a, ∆) sδ ω+γ+ 1 2 β ,
and for δ > 0 suciently small,

|π i (ξa)| ≥ |π i (ξ)||π i (a)|-O n (d(ξ, ∆)d(a, ∆)) n 1 s δ ω+γ -O n (δ ω+γ+β ) n 1 s δ ω+γ
Hence ω + γ ∈ Ω s for some s = s (s, n, κ).

A simple induction yields that there exists a sequence (s k ) k≥0 depending only on n and κ such that for all k ≥ 0,

[(k + 1)α 0 , (k + 1)α 0 + k 2 β] ⊂ Ω s k .
Recall that α 0 depends on A but it is bounded by β ≤ α 0 ≤ C where β and C are constants given by Theorem 3.5 and depend only on n and κ. Put

α = 2C β + 1 C and K = 2α
β . For any choice of α 0 ∈ [β, C], the equation

(k + 1)α 0 ≤ α ≤ (k + 1)α 0 + k 2 β has a solution k satisfying k ≤ K. It follows that α ∈ Ω s k ⊂ Ω s K .
This concludes the proof since α and s K depend only on n and κ.

Small segment

The key step in the proof of Theorem 3.4 is to produce a small segment in A s .

Proposition 3.21. Given a nite-dimensional normed simple algebra E and κ > 0, there is s ≥ 1 and > 0, α, β > 0 such that the following is true for δ > 0 suciently small. Let A be subset of E. Assume that

(i) A ⊂ B(0, δ -), (ii) N δ (A) ≥ δ -κ , (iii) A is δ -away from subalgebras.
Then there is η ∈ E, η = 1 such that (3.8)

[0, δ α ]η ⊂ A s + B(0, δ α+β ).
Proof of Proposition 3.21. First observe that we can assume without loss of generality that E is a real subalgebra of M n (C) for some positive integer n and it contains a least one element with n distinct eigenvalues. Indeed, this is evident if E is isomorphic to M n (C) or M n (R) since for the latter case we can embed naturally M n (R) in M n (C). We don't need to worry about the norm because all linear isomorphisms are bi-Lipschitz and bi-Lipschitz maps only change the constants in the assumption and conclusion of the proposition.

If E is isomorphic to M n (H), then we can embed M n (H) in M 2n (C) by sending each entry x + iy + jz + kw ∈ H to a 2 × 2 block x+iy z+iw -z+iw x-iy .
It is easy to check that this embedding of E contains a diagonal matrix with distinct diagonal entries.

In this proof, s stands for an unspecied positive integer depending on n and κ that may increase from one line to another. Since A is δ -away from subalgebras, A s is δ O( ) -away from linear subspaces by Proposition 3.11 applied to any η ∈ A with η ≥ δ . Therefore, without loss of generality, we can assume that A is δ -away from linear subspaces in E.

Consider P : M n (C) → C dened by (3.9)

P (x) = i<j (λ i -λ j ) 2
where λ 1 , . . . , λ n are eigenvalues of x ∈ M n (C) (the n roots of the characteristic polynomial of x). The right-hand side of (3.9) is symmetric in (λ i ) and thus polynomial in the coecients of the characteristic polynomial of x. Hence x → |P (x)| 2 is a real polynomial on M n (C). Apply Lemma 3.13 to |P | 2 restricted to E. Since E contains an element with n distinct eigenvalues, we obtain an element a ∈ A s such that |P (a)| > δ O( ) and consequently the eigenvalues

λ 1 , . . . , λ n of a satisfy ∀i = j, |λ i -λ j | > δ O( ) .

Now consider the map

ϕ : M n (C) → M n (C) x → ax -xa.
Let κ = κ 9n 2 . We distinguish two cases according to the size of the image ϕ(A). First consider the case where

N δ ϕ(A) ≥ δ 2κ N δ (A).
In this case we can show a growth estimate. By Lemma 3.14, there is a subset A ⊂ A 2 such that tr E (A ) is δ-separated and of size |tr E (A )| ≥ δ -4κ . Here, we used the fact that dim(E) ≤ 2n 2 . Observe that tr E (ϕ(x)) = 0 for all x ∈ E, hence

N δ ϕ(A) + A N δ (ϕ(A))|tr E (A )| ≥ δ -2κ N δ (A).
Consequently,

N δ A s ≥ δ -κ N δ (A). (3.10)
Otherwise, we have

N δ ϕ(A) < δ 2κ N δ (A),
then by cutting A into "radius δ" bers, we see that

N δ (A) N δ ϕ(A) max y N δ ϕ -1 B(y, δ) ∩ A .
Hence there is

y * ∈ M n (C) such that N δ ϕ -1 B(y * , δ) ∩ A ≥ δ -κ . Put A = ϕ -1 B(y * , δ) ∩A-ϕ -1 B(y * , δ) ∩A so that N δ (A ) ≥ δ -κ and ϕ(A ) ⊂ B(0, 2δ).
Recall that |λ i -λ j | > δ O( ) for all i = j. Hence we can apply Lemma 3.17 to the matrix a. We obtain a change of basis matrix g ∈ GL n (C) such that g + g -1 < δ -O( ) and gag -1 is diagonal. Conjugation by g will change any estimate only by a factor of δ -O( ) or δ O( ) . Hence without loss of generality we can assume that a = diag(λ 1 , . . . , λ n ). Then an explicit computation gives an expression for ϕ in the standard basis : if

x = (x ij ) i,j ∈ M n (C), then ϕ(x) = (λ i -λ j )x ij i,j .
Therefore for any x ∈ M n (C), if ϕ(x) δ then d(x, ∆) < δ 1-O( ) . Consequently A ⊂ ∆ + B(0, δ 1-O( ) ). Then Corollary 3.20 gives constants α, β > 0 and integer s ≥ 1 depending only on n and κ and a unit vector η ∈ M n (C) such that (3.8) holds.

What we have proved is that either the proposition holds or we have (3.10). If we are in the latter case, we can iterate the same argument to A s . After at most O( n 2 κ ) iterations, (3.10) cannot be possible anymore, hence the proposition must be true.

Proof of Theorem 3.4.

Once A s contains a segment, it takes only a few more steps to produce a small ball. Proposition 3.22. Under the assumptions of Proposition 3.21, we have (3.11) B(0, δ α ) ⊂ A s + B(0, δ α+β ).

(v) For all ρ ≥ δ and all v, w ∈ R n with v = 1,

µ {f ∈ End(R n ) | f v ∈ w + B(0, ρ)} ≤ δ -ρ τ , then N δ (X + X) + max f ∈Supp(µ) N δ (X + f X) ≥ δ -N δ (X).
Proof. Let X and µ be as in the statement. Assume that N δ (X + X) ≤ δ -N δ (X). For all ρ ≥ δ we have

N δ (X + X) N ρ (X) max w∈R n N δ (X ∩ B(w, ρ)).
Therefore,

(3.14) max w N δ (X ∩ B(w, ρ)) ≤ δ -O( ) ρ κ N δ (X).
Let f be a random variable following the law µ. Dene

ϕ f : R n × R n → R n by ϕ f (x, y) = x + f y.
This map is δ --Lipschitz by assumption (iv). Consider the ϕ f -energy of X ×X. By Lemma 2.6(i),

N δ (X + f X) N δ (X) 4 ω δ (ϕ f , X × X) .
Hence by Jensen's inequality,

E N δ (X + f X) N δ (X) 4 E ω δ (ϕ f , X × X)
.

The rest of the proof consists of bounding the expectation E ω δ (ϕ f , X ×X) from above. Fix X a maximal δ-separated subset of X. By Lemma 2.6(iii),

E ω δ (ϕ f , X × X) x,x ,y,y ∈ X P f (y -y ) ∈ x -x + B(0, δ 1-2 ) .
Let ρ > 0 be a constant to be chosen later. We distinguish two cases according to whether y -y ≥ ρ. If it is the case then the assumption (v) yields for all x, x ∈ X,

P f (y -y ) ∈ x -x + B(0, δ 1-2 ) ≤ δ -O( ) ρ -τ δ τ .
Otherwise, the number of pairs (y, y ) such that y -y ≤ ρ can be bounded using (3.14).

#{(y, y ) ∈ X × X | y -y ≤ ρ} ≤ δ -O( ) ρ κ N δ (X) 2 .
Moreover, we have for all x, y, y ∈ X,

x ∈ X P f (y -y ) ∈ x -x + B(0, δ 1-2 ) ≤ δ -O( )
since the events on the left-hand side can occur simultaneously for at most

δ -O( ) dierent x ∈ X.
By combining these inequalities and assumption (iii) and taking ρ = δ τ -σ τ +κ , we obtain

E ω δ (ϕ f , X × X) ≤ δ -O( ) ρ -τ δ τ | X| 4 + ρ κ | X| 3 ≤ δ -O( ) (δ τ -σ ρ -τ + ρ κ )N δ (X) 3 ≤ δ κ(τ -σ) τ +κ -O( ) N δ (X) 3 .
It follows that when is small enough, E N δ (X + f X) ≥ δ -N δ (X).

Almost-generating a subalgebra

In view of Lemma 2.8 we know that in order to establish (3.2), it suces to prove it with A s + B(0, δ) in the place of A for some s ≥ 1. That's why we can focus on growth of A as a set of matrices. We cannot use Theorem 3.4 yet since we do not know if A is away from subalgebras. In this subsection, we show that we can nd a subalgebra E 0 of End(R n ) such that A is eectively away from subalgebras in E 0 at some scale. This subalgebra E 0 can be viewed as approximately generated by A. Moreover, under the quantitative irreducibility condition, E 0 shall be described by Proposition 3.16.

Proposition 3.25. For all 1 > 0 there is c > 0 such that for all 0 < < c, the following holds for all δ > 0 suciently small. Let A be subset of End(R n ). If

• A ⊂ B(0, δ -),

• A acts δ -irreducibly on R n ; then there exists δ 1 ∈ [δ, δ c ] and g ∈ GL n (R) with g + g -1 ≤ δ -O( ) such that for

E = End(R n ), M n 2 (C) R or M n 4 (H) R , gAg -1 ⊂ E + B(0, δ 1 )
and for all proper subalgebras F of E,

∃a ∈ A, d(gag -1 , F ) > δ 1 1 .
Proof. Let l 0 be the largest among all integer l ∈ N such that there exists a subalgebra E of End(R n ) of codimension l and such that A ⊂ E + B(0, δ ( 1 4 ) l ).

We know l 0 exists since 0 is clearly such an l. Set

δ 1 = δ 1 2 ( 1 4 ) l 0 . Thus δ ≤ δ 1 ≤ δ c1 with c 1 = 1 2 ( 1 4 ) n 2 . By the denition of l 0 there is a subalgebra E 0 of End(R n ) such that (3.15) A ⊂ E 0 + B(0, δ 2 1 )
and for any proper subalgebra F of E 0 , there is a ∈ A such that (3.16)

d(a, F ) > δ 1 2
1

We shall apply Proposition 3.16 to this subalgebra E 0 in order to conjugate it into one of the three "model" subalgebras. For any nonzero linear subspace W of R n , since A acts δ -irreducibly , there is w ∈ B W (0, 1) and a ∈ A such that d(aw, W ) > δ . Then there is a ∈ E 0 such that a -a < δ 1 . Hence

a < δ -+ δ 1 < δ -2 and d( a a w, W ) > δ 2 (δ -δ 1 ) ≥ δ 2 (δ -δ c1 ) > δ 4
when ≤ c1 2 . Thus E 0 acts δ 4 -irreducibly on R n . We conclude that there is g ∈ GL n (R) with g + g -1 < δ -O( ) and E = gE 0 g -1 is one of these three subalgebras :

End(R n ), M n 2 (C) R , M n 4 (H) R . The map x → gxg -1 is δ -O( ) -bi-Lipschitz.
Hence by (3.15) and (3.16),

gAg -1 ⊂ E + B(0, δ -O( ) δ 2 1 )
and

gAg -1 is δ O( ) δ 1 2
1 -away from proper subalgebras of E. When ≤ c1 1 C , we have δ 1 1 < δ C and hence both

δ -O( ) δ 2 1 ≤ δ 1 and δ O( ) δ 1 2 1 ≥ δ 1 1 .
This completes the proof.

Remark. From the proof we see that the new scale δ 1 can be chosen such that δ is an integer power of δ 1 .

3.6.3 Proof of Theorem 3.2.

The proof consists of putting together what precedes. The only technical diculty is due to change of working scale required by Proposition 3.25.

Proof of Theorem 3.2. Assume for a contradiction that for > 0 arbitrarily small, there exists A ⊂ End(R n ) and X ⊂ R n such that the assumptions in Theorem 3.2 are met but the conclusion fails, i.e. A ∪ {Id} ⊂ S δ (X; δ -) using the notation introduced in 2.4. Let 1 > 0 be a small constant to be chosen later. By applying Proposition 3.25 to the set A, we get a constant c > 0 depending on 1 , a new scale

δ 1 ∈ [δ, δ c ], an element g ∈ GL n (R) and a subalgebra E = End(R n ) or M n 2 (C) R or M n 4 (H) R such that g + g -1 ≤ δ -O( ) and gAg -1 ⊂ E + B(0, δ 1 )
and the projection of gAg -1 on E, which we will denote by A , is δ 1 1 -away from subalgebras in E. Moreover, we have (3.17)

A ⊂ gAg -1 + B(0, δ 1 ) Thus A ⊂ B(0, δ -O( ) + δ 1 ) ⊂ B(0, δ -O( c ) 1
).

Morever, for all ρ ≥ δ 1 , since gAg -1 ⊂ A + B(0, ρ), we have

N ρ (A ) N ρ (gAg -1 ) δ O( ) N ρ (A) ≥ δ O( ) ρ -κ ≥ δ O( c ) 1 ρ -κ .

53

So when is suciently small depending on 1 and c, we have both A ⊂ B(0, δ -1 1 ) and ∀ρ ≥ δ 1 , N ρ (A ) ≥ δ 1 1 ρ -κ . Let 0 > 0 be a small constant to be chosen later in the proof. Applying Theorem 3.4 to the set A at scale δ 1 inside the algebra E, we obtain an integer s ≥ 1 depending only on n, κ and 0 such that (3.18)

B E (0, δ 0 1 ) ⊂ A s + B(0, δ 1 ),
if 1 is chosen small enough depending on n, κ and 0 .

From A ⊂ S δ (X; δ -), we get for all a ∈ A,

N δ (gX + gag -1 gX) = N δ g(X + aX) ≤ δ -O( ) N δ (X) ≤ δ -O( ) N δ (gX).
That is to say gAg -1 ⊂ S δ (gX, δ -O( ) ). By Lemma 2.8(v), gAg -1 ⊂ S δ1 (gX; δ -O( ) ).

Then by Lemma 2.8(i),

A ⊂ S δ1 (gX; δ -O( c ) 1 ) ⊂ S δ1 (gX; δ -1 1 ),
provided that is suciently small compared to c 1 . Repeated use of Lemma 2.8(ii) yields

A s ⊂ S δ1 (gX; δ -Os( 1) 1
).

Then by (3.18) and Lemma 2.8(i),

B E (0, δ 0 1 ) ⊂ S δ1 (gX; δ -Os( 1) 1
).

In particular, δ 0

1 Id ∈ S δ1 (gX; δ -Os( 1) 1
). Hence, by Lemma 2.8(iii), ).

Then again by Lemma 2.8(ii), B E (0, 1) ⊂ S δ1 (gX; δ -Os( 1)-O( 0 ) 1

).

Hence for any given 2 > 0, we can choose suciently small 0 > 0 and 1 > 0 accordingly so that (3.19)

B E (0, 1) ⊂ S δ1 (gX; δ -2 1 ).
Take 2 to be the constant given by Lemma 3.23 depending on σ and κ. We would like to apply Lemma 3.23 to the set gX at scale δ 1 . It's easy to see that when is small enough,

gX ⊂ B(0, δ -O( ) ) ⊂ B(0, δ -2 1 ),
and for all ρ ≥ δ 1 ,

N ρ (gX) ≥ δ O( ) N δ (X) ≥ δ O( ) ρ -κ ≥ δ 2 1 ρ -κ .
So the rst two assumptions in Lemma 3.23 are satised but the conclusion fails by (3.19). This means the assumption (iii) must fail, namely, N δ1 (gX) > δ -σ-2

1

. Therefore, (3.20)

N δ1 (X) ≥ δ O( ) δ -σ-2 1 .
In other words, at scale δ 1 , the set X is almost full in B(0, δ -). The idea of the rest of the proof is to use multiplication of elements of A to propagate estimate (3.20) to smaller scales until we reach the original scale δ where we have the assumption N δ (X) ≤ δ -σ-.

We have by (3.18) and (3.17),

δ 1 2
1 Id ∈ A s + B(0, δ 1 ) ⊂ g A s g -1 + B(0, δ -Os( ) δ 1 ).

Hence there exists a ∈ A s such that a ∈ δ 1 2

1 Id + B(0, δ -Os( ) δ 1 ). Taking the square, we obtain a 2 ∈ δ 1 Id + B(0, δ -Os( ) δ 3 2 1 ). Thus, when is suciently small,

a 2 ∈ δ 1 Id + B(0, δ 1 2 )
.

For all ρ > 0, the multiplication by a 2 will transform a ρ-separated set in R n into a δ1ρ 2 -separated set. Hence,

N δ1ρ (a 2 X) N ρ (X).
Moreover a 2 X ⊂ B(0, δ -2 δ 1 ). Hence

N δ1ρ (X + a 2 X) ≥ δ O( ) N δ -2 δ1 (X)N δ1ρ (a 2 X) ≥ δ O( ) N δ1 (X)N ρ (X).
Lemma 2.8 tells us a 2 ∈ S δ (X, δ -Os( ) ) and for all ρ ≥ δ -1

1 δ, N δ1ρ (X + a 2 X) ≤ δ -Os( ) N δ1ρ (X).
Combining the two estimates above, we obtain (3.21)

N δ1ρ (X) ≥ δ Os( ) N δ1 (X)N ρ (X)
whenever δ 1 ρ ≥ δ.

According to the remark after the proof of Proposition 3.25, we can assume that there is an integer k with 1 ≤ k ≤ 1 c such that δ = δ k 1 . Applying (3.21) to

ρ = δ i 1 , i = 1, . . . , k -1, we obtain N δ k 1 (X) ≥ δ Os(k ) N δ1 (X) k .
Hence, by (3.20) and the assumption on X,

δ -σ-≥ N δ (X) ≥ δ -σ-2+Os(k ) ,
which is clearly impossible when is small enough and this nishes the proof.

Remark. Theorem 3.2 together with Lemma 3.10 yields another proof of Theorem 3.1. It suces to consider the action of left and right multiplications of elements of A on the set A. Actually, this proves something slightly stronger. Namely, the conclusion of Theorem 3.1 can be improved to

N δ (A + A) + max a∈A N δ (A + a • A) + max a∈A N δ (A + A • a) ≥ δ -N δ (A).
Chapter 4

Orthogonal projections of discretized sets

In this chapter we generalize Bourgain's discretized projection theorem (Theorem 1.6) to higher rank projections. Let 0 < m < n be positive integers. We denote by Gr(R n , m) the Grassmannian of m-dimensional subspaces in R n . For V ∈ Gr(R n , m), π V : R n → V stands for the orthogonal projection onto

V . If W ∈ Gr(R n , n -m), we dene d (V, W ) = v 1 ∧ • • • ∧ v m ∧ w 1 ∧ • • • ∧ w n-m
where (v 1 , . . . , v m ) is an orthonormal basis of V and (w 1 , . . . , w n-m ) an orthonormal basis of W . For example d (V, W ) = 0 if and only if V and W have nontrivial intersection. For ρ ≥ 0, we denote by V (W, ρ) the set of all V ∈ Gr(R n , m) such that d (V, W ) ≤ ρ. Recall that V (W, 0) is a submanifold of codimension 1 in Gr(R n , m) and belongs to the class of algebraic subvarieties known as Schubert cycles (see for example [START_REF] Griths | Principles of algebraic geometry[END_REF]Chapter 1,[START_REF] Bollobás | Projections of bodies and hereditary properties of hypergraphs[END_REF]).

Our main result is the following.

Theorem 4.1. Let m < n be positive integers. Given 0 < α < n and κ > 0, there exists > 0 such that the following holds for suciently small δ > 0.

Let A be a subset of R n contained in the unit ball B(0, 1). Let µ be probability measure on Gr(R n , m). Assume that (4.1)

N δ (A) ≥ δ -α+ ; (4.2) ∀ρ ≥ δ, ∀x ∈ R n , N δ (A ∩ B(x, ρ)) ≤ δ -ρ κ N δ (A); (4.3) ∀ρ ≥ δ, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ δ -ρ κ .
Then there is a set D ⊂ Gr(R n , m) such that µ(D) ≥ 1 -δ and

N δ (π V (A )) ≥ δ -m n α- whenever V ∈ D and A ⊂ A is a subset such that N δ (A ) ≥ δ N δ (A).
For 1 < m < n, our result is new. Hypothesis (4.2) is a Frostman type 1 non-concentration condition on A. Without it we can have example like A = B(0, δ 1-α n ), a ball of radius δ 1-α n , whose size is N δ (A) δ -α but whose projection to any V ∈ Gr(R n , m) is of size

N δ (π V (A)) δ -m n α .
Hypothesis (4.3) is a non-concentration condition on the distribution of the subspace V . The set V (W, ρ) can be thought of as a ρ-neighborhood of the Schubert cell V (W, 0). For example if m = 1, V lives in the projective space and (4.3) is asking µ to be not concentrated around any projective subspace. Note that the factor δ -in both (4.2) and (4.3) means that the non-concentration property needs to be satised up to scale δ . So the parameter κ is about how good the assumptions are and is about how much the assumptions can be relaxed and how good the conclusion is. Just like Bourgain's discretized projection theorem can be used to derive a projection theorem in terms of Hausdor dimension [7, Theorem 4], Theorem 4.1 has the following consequence. Corollary 4.2. Let m < n be positive integers. Given 0 < α < n and κ > 0, there is > 0 such that the following is true. Let A ⊂ R n is a Borel set of dimension dim H (A) = α. Then the set of exceptional directions

V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α +
does not support any nite Borel measure µ on Gr(R n , m) with the following non-concentration property,

∀ρ > 0, ∀W ∈ Gr(R n , n -m), µ(V (W, ρ)) ≤ ρ κ .
Applied to a Frostman measure supported on the set of exceptional directions, we get Corollary 4.3. Let m < n be positive integers. Given 0 < α < n and κ > 0, there is > 0 such that the following holds.

Let A ⊂ R n be a Borel set of dimension dim H (A) = α. Then dim H V ∈ Gr(R n , m) | dim H (π V (A)) ≤ m n α + ≤ m(n -m) -1 + κ.
Compared to what is already known (Theorem 1.5), the number 1 in our estimate is very weak. However, our result does provide something new for specic choice of n, m and α, namely when n m (m -1) < α ≤ m or when m < α < n n-m .

Strategy of the proof

Fix n, m and α. For > 0 and bounded subset A ⊂ R n we dene the set of exceptional directions to be

E(A) = {V ∈ Gr(R n , m) | ∃A ⊂ A, N δ (A ) ≥ δ N δ (A)
and N δ (π V (A )) < δ -m n α-}.

1 Cf. Frostman's lemma (Theorem 1.1).

58

When we want to specify , we write E(A, ) instead. Our task is to bound µ(E(A)). In order to prove Theorem 4.1 which says µ(E(A)) ≤ δ under the assumptions of the theorem, we prove instead that µ(E(A )) ≤ δ for some subset A of A.

Theorem 4.4. Let m < n be positive integers. Given 0 < α < n and κ > 0, there exists > 0 such that the following holds for suciently small δ > 0. Let A be a subset of R n contained in the unit ball B(0, 1). Let µ be a probability measure on Gr(R n , m). Assume (4.1), (4.2) and (4.3), then there exists

A ⊂ A such that µ(E(A )) ≤ δ .
This statement is seemingly weaker, but there is actually a rather formal argument which allows to deduce Theorem 4.1 from Theorem 4.4. We will show this implication in Proposition 4.17.

The proof of Theorem 4.4 starts with the special case where n = 2m. As in the m = 1 case in [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF], this special case is proved using a sum-product theorem. For m > 1, we need the higher dimensional sum-product estimate Theorem 3.2.

To see why this sum-product estimate can be helpful we remark that the space of m by m matrices, End(R m ), is dieomorphic to the complement of a codimension

1 Schubert cell in Gr(R 2m , m). More precisely, if R 2m is the direct sum of two subspaces V 1 and V 2 both of dimension m, then the map Gr(R 2m , m)\ V (V ⊥ 1 , 0) → L(V 2 , V 1 ) dened by V → π -1 V |V1 • π V |V2 is a dieomorphism. Here L(V 2 , V 1 )
stands for the space of linear maps from V 1 to V 2 .

Once we have Proposition 4.5 we would like reduce other cases to this special case. If m divides n, this is done easily by considering large slices of dimension n -m in A.

Proposition 4.6. Let q ≥ 3 be an integer. If Theorem 4.4 is true for n = (q -1)m and m then it is also true for n = qm and m.

If m does not divide n and m < n 2 , the idea is the following. Write n = qm+r with 0 < r < m. Let V 1 , . . . , V q be linear subspaces of dimension m in "generic" position. If the projection of A to the sum subspace V 1 + • • • + V q is large then its projection to one of the V i must be large as well. Proposition 4.7. Let 0 < m < n be such that qm < n where q ≥ 1. If Theorem 4.4 is true for n and m = qm then it is also true for n and m.

If m does not divide n and m > n 2 , we are in a dual situation to the previous one. So we consider intersections instead of sums of subspaces. Write n = q(n -m) + r with 0 < r ≤ n -m. Necessarily q ≥ 2. Let V 1 , . . . , V q be linear subspaces of dimension m in "generic" position. The intersection

V 1 ∩ • • • ∩ V q has dimension r. If the projection of A to V 1 ∩• • •∩V q is large
then we would like to conclude that its projection to one of the subspace V i must be large as well. However, this is not true unless we assume that A does not have any large slice orthogonal to V (see Proposition 4.26). If A does have a large slice of dimension n -r, we can produce large projections using this slice. Proposition 4.8. Let 0 < m < n be such that n = q(n -m) + r where q ≥ 1 and 0 < r ≤ n -m. If Theorem 4.4 is true for n and m = r then it is also true for n and m.

Let us see how we prove Theorem 4.4 by putting these propositions together.

Proof of Theorem 4.4. Propositions 4.5 and 4.6 imply the theorem for all pairs (n, m) such that m divides n. Consider the following order on pairs of positive integers. We say (n, m) ≺ (n , m ) if (n, min(m, n -m), m) is smaller than (n , min(m , n -m ), m ) for the lexicographical order.

If the theorem were false then let (n, m) be a ≺-minimal pair for which the theorem fails. We know that m does not divide n. If m < n 2 then write n = qm + r with 0 < r < m. We have (n, qm) ≺ (n, m). Hence Proposition 4.7 contradicts the minimality of (n, m). Otherwise m > n 2 , then write n = q(nm) + r with 0 < r ≤ n -m. We have (n, r) ≺ (n, m) and then Proposition 4.8 contradicts the minimality of (n, m).

Preliminaries

In this section we collect some elementary estimates about the Grassmannian and establish two useful lemmata about intersections.

Distance on the Grassmannian

For linear subspaces V, W of R n , we dene

d (V, W ) = v 1 ∧ • • • ∧ v r ∧ w 1 ∧ • • • ∧ w s
where (v 1 , . . . , v r ) is an orthonormal basis of V and (w 1 , . . . , w s ) an orthonormal basis of W . It is a distance when restricted to the projective space Gr(R n , 1) but only in this case. For example, d (V, W ) = 0 if and only if V and W have nontrivial intersection and d (V, W ) = 1 if and only if they are orthogonal to each other. For other cases, d (V, W ) falls between 0 and 1.

If v 1 , . . . , v r are vectors and w = w 1 ∧ • • • ∧ w s the wedge product of an orthonormal basis of W, then (4.4)

v 1 ∧ • • • ∧ v r ∧ w = π W ⊥ (v 1 ) ∧ • • • ∧ π W ⊥ (v r ) .
In particular, if (v 1 , . . . , v r ) is an orthonormal basis of V , then (4.5)

d (V, W ) = π W ⊥ (v 1 ) ∧ • • • ∧ π W ⊥ (v r ) .
If f : V → W is a linear map between euclidean spaces of same dimension, then the determinant of its matrix expressed in orthonormal bases up to a sign does not depend on the choice of the bases. Moreover, we have

|det(f )| = f (v 1 ) ∧ • • • ∧ f (v r )
where (v 1 , . . . , v r ) is an orthonormal basis of V . Together with (4.5) this gives yet another denition of

d (V, W ) if dim(V ) + dim(W ) = n, (4.6) d (V, W ) = |det(π W ⊥ |V )|, Similarly, π V2 (z) ≥ z 1 d (V 1 , V 2 ).
We get the lemma for q = 2 using the triangular inequality. Now, suppose the lemma is true for some q ≥ 2. Let us show the lemma for q + 1. Let V q = V q + V q+1 and z = π V q (z). The induction hypothesis applied to z and (

V 1 , . . . , V q-1 , V q ) gives z d (V 1 , . . . , V q-1 , V q + V q+1 ) ≤ π V1 (z) + • • • + π Vq-1 (z) + z .
The lemma applied to z and (V q , V q+1 ) gives

z d (V q , V q+1 ) ≤ π Vq (z ) + π Vq+1 (z ) = π Vq (z) + π Vq+1 (z) . Recall that d (V 1 , . . . , V q+1 ) = d (V 1 , . . . , V q-1 , V q + V q+1 ) d (V q , V q+1 ).
We obtain the desired estimate by multiplying the rst inequality by d (V q , V q+1 ) and combining it with the second. Lemma 4.11. If R n is a direct sum of V 1 , . . . , V q then for any bounded subset

A ⊂ R n , (4.12) N δ (A) n d (V 1 , . . . , V q ) -n q i=1 N δ (π Vi (A)). Proof. Suppose for each i ∈ {1, . . . , q}, π Vi (A) is covered by the balls x (δ) i , x i ∈ X i ⊂ V i . For each (x i ) i ∈ X 1 × • • • × X q , there is a unique x ∈ R n such that ∀i, π Vi (x) = x i . By Lemma 4.10, we have π -1 V1 (x (δ) 1 ) ∩ • • • ∩ π -1 Vq (x (δ) q ) ⊂ x (δ ) ,
where δ = d (V 1 , . . . , V q ) -1 qδ. So A is covered by the balls centered at such

x. Hence N δ (A) ≤ |X 1 | • • • |X q |.
We then conclude by using the scale change estimate (2.3).

Lemma 4.12. Let V, W be linear subspaces of R n . If V = π W (V ), then for all

x ∈ W , (4.13)

d (V, W ⊥ ) π V (x) ≤ π V (x) ≤ π V (x) .
In particular, if moreover dim V = dim W , then for all x ∈ W ,

d (V, W ⊥ ) x ≤ π V (x) ≤ x . Proof. Since V = π W (V ), we have V ⊥ ∩W ⊂ V ⊥ . Hence we can write x = y+z with y = π V (x) ∈ V and z ∈ V ⊥ ∩ W ⊂ V ⊥ . Then π V (x) = π V (y).
This gives the second inequality in (4.13).

It is clear that V and V have dierent dimensions if and only if V and W ⊥ have nontrivial intersection, which is equivalent to d (V, W ⊥ ) = 0. In this case, the rst inequality in the lemma holds.

Let us assume dim V = dim V . In this case there is g ∈ O(n) which exchanges V with V . We have Lemma 4.15. In the situation described above, if there is K ≥ 1 such that ∀θ ∈ Θ, λ(A θ ) ≥ λ(A)/K, then for any positive integer q > 0,

µ ⊗q ( (θ 1 , . . . , θ q ) | λ(A θ1 ∩ • • • ∩ A θq ) ≥ λ(A) 2K q ) ≥ 1 2K q .
Proof. By Fubini's theorem and then Jensen's inequality,

λ(A θ1 ∩ • • • ∩ A θq ) dµ ⊗q (θ 1 , . . . , θ q ) = A 1 A θ 1 (x) • • • 1 A θq (x) dµ ⊗q (θ 1 , . . . , θ q ) dλ(x) =λ(A) A 1 A θ (x) dµ(θ) q dλ(x) λ(A) ≥λ(A) A 1 A θ (x) dµ(θ) dλ(x) λ(A) q =λ(A) λ(A θ ) λ(A) dµ(θ) q ≥ λ(A) K q
The lemma follows.

The next lemma is about small probability events happening simultaneously. Let (E, µ) be a probability space. Suppose we have a collection of subsets (E i ) i∈{1,...,N } of E. We will think E i as events with small probability and we want to estimate the probability such that a lot of them happen together.

Here "a lot" is relatively to weights we give to the events. Let (a i ) i∈{1,...,N } be non-negative real numbers such that N i=1 a i = 1. For I ⊂ {1, . . . , N }, write a I = i∈I a i . The following lemma is an easy consequence of Markov's inequality. Lemma 4.16. With the notations above, we have, for any a > 0,

µ I|a I ≥a i∈I E i ≤ a -1 max i∈{1,...,N } µ(E i ).

Proof. Consider the Bernoulli random variables

X i = 1 Ei for i = 1, . . . , N so that µ(E i ) = E X i and µ I|a I ≥a i∈I E i = P N i=1 a i X i ≥ a .
Then it follows from Markov's inequality that

P N i=1 a i X i ≥ a ≤ a -1 E N i=1 a i X i ≤ a -1 max i∈{1,...,N } E X i .
This nishes the proof.

Proof. The statement about the assumptions (4.1) and (4.2) follows immediately from the inequality (2.4). As for the assumption (4.3), it suces to prove that for all W ∈ Gr(R n , n -m) and all ρ ≥ δ, (4.19)

f ⊥ * µ V (f ⊥ W, ρ) ≤ µ V (W, δ -O( ) ρ) .
From the Cartan decomposition of f , we see easily that ∀r = 1, . . . , n, r f ⊥ + ( r f ⊥ ) -1 ≤ δ -O( ) . For V ∈ Gr(R n , m), let v be the wedge product of an orthonormal basis of V and w that of W . We have

d (f ⊥ V, f ⊥ W ) = ( n f ⊥ )(v ∧ w) ( m f ⊥ )v ( n-m f ⊥ )w ≥ ( n f ⊥ ) -1 -1 v ∧ w m f ⊥ n-m f ⊥ ≥ δ O( ) d (V, W ). Hence f ⊥ V ∈ V (f ⊥ W, ρ) implies V ∈ V (W, δ -O( ) ρ), which establishes (4.19).
For the second statement, observe that there is a nite set à of cardinality

| Ã| = N δ (π V (A)) such that A ⊂ Ã + V ⊥ + B(0, δ).
Applying f and then π f ⊥ V on both sides, we obtain

π f ⊥ V (f A) ⊂ π f ⊥ V (f Ã) + B(0, δ 1-).

This proves that

N δ 1-(π f ⊥ V (f A)) ≤ N δ (π V (A)).
We conclude by the scale change estimate (2.3).

For the next statement, it suces to prove that f ⊥ V ∈ E(f A, O( )) whenever V ∈ E(A, ). Indeed, let V ∈ E(A, ). Then there exists A ⊂ A such that N δ (A ) ≥ δ N δ (A) and N δ (π V (A )) < δ -m n α-. On the one hand, by (2.4), we have N δ (f A ) ≥ δ O( ) N δ (f A). On the other hand, from (ii) it follows that

N δ (π f ⊥ V (f A )) ≤ δ -m n α-O( ) . Hence f ⊥ V ∈ E(f A, O( )).
For the last statement, it suces to prove for any x ∈ f ⊥ V , there exists y ∈ V such that (4.20)

f A ∩ π -1 f ⊥ V (x (δ) ) ⊂ f A ∩ π -1 V (y (δ 1-) ) . Indeed, if a ∈ A satises π f ⊥ V (f (a)) ∈ x (δ) , then f (a) ∈ x + f V ⊥ + B(0, δ).
Applying f -1 and then π V on both sides, we obtain

π V (a) ∈ π V (f -1 (x)) + B(0, δ 1-).
This proves (4.20) with y = π V (f -1 (x)).

It remains to show the non-concentration property (4.26) for B. Let ρ ≥ δ and x ∈ W . From (4.28), d (V, W ⊥ ) = d (V, V q ) ≥ δ O( ) . Hence, by (4.15) in Lemma 4.13,

N δ (B ∩ x (ρ) ) ≤ δ -O( ) N δ (π V (B) ∩ x (ρ) 0 ) where x 0 = π V (x). Moreover B ⊂ A (δ) q , hence (4.31)
N δ (B ∩ x (ρ) ) ≤ δ -O( ) N δ (π V (A q ) ∩ x (2ρ) 0
).

Then Lemma 4.11 applied to the set π V (A q )∩x (2ρ) 0 in V = q j=1 V j together with (4.28) yield

N δ (π V (A q ) ∩ x (2ρ) 0 ) ≤ δ -O( ) N δ (π V1 (A q ) ∩ x (2ρ) 1 ) q-1 j=2 N δ (π Vj (A q ))
where x 1 = π V1 (x 0 ). The required non-concentration property (4.26) then follows from (4.27) and (4.29).

Without the non-concentration property

As illustrated by the example in the introduction, the non-concentration condition (4.2) on A is crucial to have a gain > 0 in the conclusion. Without this condition, we still expect N δ (π V (A)) to be close to N δ (A) m n for generic V ∈ Gr(R n , m). This is the subject of the next proposition. Proposition 4.21. Given 0 < m ≤ n, 0 < α < n and κ > 0, there exists C < +∞ such that for all 0 < < 1 C , the following is true for all δ > 0 suciently small. Let A ⊂ R n be a subset contained in the unit ball and µ a probability measure on Gr(R n , m). Assume that (4.32)

N δ (A) ≥ δ -α-C .
Further assume the non-concentration property (4.3)

for µ if m < n. Then µ(E(A)) ≤ δ .
When m divides n, this follows almost immediately from Lemma 4.11. Then the task is to reduce to this special case. Since it shares the same set of ideas as the proof of Theorem 4.4, the proof below will only be outlined and more details can be found in the next section.

(e 1 , e 2 , e 3 ) is the standard basis in R 3 . While its projections to Re 1 ⊕ Re 3 and to Re 2 ⊕ Re 3 are both small (have dimension 1 in a 2-dimensional space), its projection to Re 3 is full dimensional. In this example, A contains a large slice orthogonal to V . This happens to be the major obstruction. Proposition 4.26. Let n, m, q, r be positive integers such that n = q(n-m)+r.

For any 0 < α < n and > 0, the following is true for suciently small δ > 0.

Let A ⊂ R n and V 1 , . . . , V q ∈ Gr(R n , m). Write V = V 1 ∩ • • • ∩ V q . Assume that (i) d (V ⊥ 1 , . . . , V ⊥ q ) ≥ δ ; (ii) δ -α+ ≤ N δ (A) ≤ δ -α-; (iii) For every j = 1, . . . , q, N δ (π Vj (A)) ≤ δ -m n α-; (iv) For all y ∈ V , N δ A ∩ π -1 V (y (δ) ) ≤ δ -n-r n α-.
Then there exists A ⊂ A such that N δ (A ) ≥ δ O( ) N δ (A) and

N δ (π V (A )) ≤ δ -r n α-O( ) .
This proposition is deduced from the following discrete analogue. Let n, m, q, r be as in Proposition 4.26. For I ⊂ {1, . . . , n}, we write I : Z n → Z I to denote the discrete projection (z i ) i∈{1,...,n} → (z i ) i∈I . Consider I 0 = {n -r + 1, . . . , n} and for j = 1, . . . , q I j = {1, . . . , n} \ {(j -1)(n -m) + 1, . . . , j(n -m)} . One of the ingredients is a discrete isoperimetric inequality due to Bollobás-Thomason [START_REF] Bollobás | Projections of bodies and hereditary properties of hypergraphs[END_REF] known as the uniform cover theorem. Let P({1, . . . , n}) denote the set of subsets of {1, . . . , n}. Recall that a multiset of subsets of {1, . . . , n} is a collection of elements of P({1, . . . , n}) which can have repeats. Giving such a multiset is equivalent to giving a map from P({1, . . . , n}) to N. Following Bollobás-Thomason, we say a multiset C is k-uniform cover of {1, . . . , n} if each element i ∈ {1, . . . , n} belongs to exactly k members of C. For exemple, with I j dened above, (I 1 \ I 0 , . . . , I q \ I 0 ) is a (q -1)-uniform cover of {1, . . . , n} \ I 0 . Theorem 4.28 (Uniform Cover theorem, Bollobás-Thomason [START_REF] Bollobás | Projections of bodies and hereditary properties of hypergraphs[END_REF]). Let Z be a nite subset of Z n . Let C be an k-uniform cover of {1, . . . , n}. Then we have

|Z| k ≤ I∈C | I (Z)|.
For example, if we consider projections onto all canonical m-dimensional subspaces. There is always one which has at least the expected size: there exists I ⊂ {1, . . . , n} such that |I| = m and | I (Z)| ≥ |Z| m/n . Lemma 4.29. Let I 0 ⊂ {1, . . . , n}. Let Z be a nite subset of Z n and C a k-uniform cover of {1, . . . , n} \ I 0 with q elements. Then (4.50)

|Z| 2q-k ≤ ω( I0 , Z) q-k I∈C | I0∪I (Z)|.
This lemma is a renement of the uniform cover theorem. Indeed, for I 0 = ∅, we have ω( I0 , Z) = |Z| 2 and we recover the uniform cover theorem from (4.50).

Proof. For all I ∈ C, we have For each y ∈ I0 (Z), we apply the uniform cover theorem (Theorem 4.28) to the set Z ∩ -1 I0 (y) seen as a nite subset of Z {1,...,n}\I0 ,

|Z ∩ -1 I0 (y)| k q ≤ I∈C | I (Z ∩ -1 I0 (y))| 1 q .
From the two inequalities above, we get

I0 * 1 Z k k q ≤ I∈C | I0∪I (Z)|.
Finally, Hölder's inequality implies

|Z| = I0 * 1 Z 1 ≤ I0 * 1 Z k 2q-k k q I0 * 1 Z 2q-2k 2q-k 2 .
We nish the proof by putting the last two inequalities together and recalling that ω( I0 , Z) = I0 * 1 Z 2 2 . Proof of Proposition 4.27. We use the notations introduced before Proposition 4.27. By (4.50), we have

|Z| q+1 ≤ ω( I0 , Z) q j=1 | Ij (Z)|.
If the rst statement does not hold. Then we have

ω( I0 , Z) ≥ 1 K q |Z| 1+ n-r n .
If the second statement fails as well, we can apply Lemma 2.5 with M = K|Z| n-r n and K = K q+1 . The third statement follows immediately.

Proof of Proposition 4.26. Let (e 1 , . . . , e n ) denote the standard basis of R n . First consider the special case where V ⊥ j is exactly Span(e (j-1)(n-m)+1 , . . . , e j(n-m) )

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

then B G (1, δ 0 ) ⊂ (A ∪ {1} ∪ A -1 ) s B G (1, δ).
This statement immediately implies Theorem 5.1, just like Theorem 3.4 implies Theorem 3.1 in the sum-product setting.

The rst step of the proof of Theorem 5.3 is to reduce to the case where the radical of G is abelian. In this reduction, we exploit the elementary algebraic fact that if R is a nilpotent group and R l the last nontrivial term in its lower central series and if H < G is a subgroup whose image under the projection R/R l is full then H = G. For the special case we use the Theorem 5.2 to show growth of log A ⊂ g under addition and action of A through the adjoint representation. To get back inside G, we use Campbell-Hausdor formula to show that we can approximate sums in g by products in G.

The proof of Theorem 5.2 is by induction on the length of the Jordan-Hölder sequence. The base case where V is an irreducible representation is a variant of Theorem 3.2. The induction step exploits the fact that X is δaway from submodules hence generates V as G-module. We use systematically the ojasiewicz inequality (recalled at Theorem 3.8) to extract quantitative estimates from algebraic facts.

Sum-product estimates in representations

In this section, we introduce a class of representations called P(G), show some basic properties of these representations and then prove Theorem 5.2.

Representations without trivial simple quotients

Denition. Let G be a connected Lie group. A representation V is said to be of class P(G) if there exists a sequence 0 = V 0 < V 1 < . . . < V l = V of subrepresentations of V such that, for each i = 1, . . . , l, the quotient representation V i /V i-1 is nontrivial 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 5.4. Let V be a representation of a connected Lie group G.

(i) (Subrepresentations and quotients representations) If W 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. The representation π dierentiates to a representation of the Lie algebra g of G, which we denote by T 1 π : g → End(V ). Then 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 exp is contained in Stab G (W ) • , the identity component of Stab G (W ).

We may assume that exp induces a dieomorphism from U to its image, and denote the inverse map by log. We 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 )) ≥ ρ. The argument in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]Lemma 2.5] shows 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.

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. This nishes the proof of the lemma. Let us prove this claim. Indeed, from the identity π(exp(x)) = e T1π(x) , we can express T 1 π(x) as an absolutely convergent series where C > 0 is some constant depending only on the the representation. This nishes the proof of the claim.

T 1 π(x) = -
Proof of Lemma 5.7. Let U be the neighborhood given by Lemma 5.8. On account of this lemma we can assume that A is nite of cardinality n ≤ dim G and ρ-away from proper stabilizers. Let 0 < k < dim(V ). Consider the analytic map f : G n × Gr(V, k) → R dened by The zero set of f is exactly

Z = {(g, W ) ∈ G n × Gr(V, k) | ∀i, g i ∈ Stab G (W )}.
By ojasiewicz inequality (Theorem 3.8) applied to Ū n × Gr(V, k), there is a constant C > 0 depending only on π such that for any (g, W ) ∈ U n × Gr(V, k),

f (g, W ) ≥ 1 C d (g, W ), Z C .
Assume that the result holds for all representations of length less than l ≥ 2, let V ∈ P(G) be a representation of length l, and suppose A ⊂ G and X ⊂ V satisfy conditions (i)-(iii) of the theorem, for some small > 0, to be specied later. Let 0 = V 0 < . . . < V l = V be the Jordan-Hölder sequence given by assumption (i). Write V = V /V 1 and denote by π : V → V the projection.

Then the module V has length l -1 and conditions (i) and (iii) are satised for A acting on π(X) ⊂ V . Note that it suces to show that for some constant C > 0, A, X s is Cδdense in B V (0, δ 0 ) because we can repeat the argument at the smaller scale δ C . Consequently, we can replace X by A, X (δ) s at any moment in the proof as long as s is a constant which depends only on the representation V and the parameters 0 and κ.

In what follows, we will use two methods to prove a subset is away from submodules. First, if X is ρ-away from submodules then its projections to any quotient module is also ρ-away from submodules. Secondly, if X ⊂ B V (0, 1) satises N δ (X) ≥ δ -dim(V )+ then X is δ O( ) -away from submodules. First step: We rst prove that there exists 1 > 0 and s 1 ≥ 1 depending on V , 0 and κ such that B V (0, δ 0 ) ⊂ π( A, X s1 ∩ B V (0, δ 1 )) + B V (0, δ).

Let 1 > 0 be a small parameter, whose precise value will be specied at the end of this step. By applying the induction hypothesis to V , whose length is at most l -1 and replacing X by A, X s , we can suppose that B V (0, δ 1 ) ⊂ π(X) (δ) . Cover X with δ -O( 1) balls of radius δ 1 , pick a ball B such that N δ (π(B ∩ X)) is maximal and translate it back to the origin to get N δ (π(X )) ≥ δ -dim(V )+O ( 1) , with X = (X -X) ∩ B V (0, δ 1 ). This lower size bound ensures that π(X ) is δ O( 1) -away from proper linear subspaces in V . The induction hypothesis, applied to the subset π(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 5.5 applied to the representation V 1 , with constants κ, 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 nd that (5.10) B V1 (0, δ 1 ) ⊂ A, X (δ) s2 + B V (0, δ).

Recalling the inclusion obtained in the rst step and setting s = s 1 + O s1 (s 2 ), we nd B V (0, δ 0 ) ⊂ A, X s + B V (0, O s1,s2 (δ)).

This nishes 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 contains a vector of length at least δ 2 , which allows to conclude by using the second step.

Let 0 < 3 < 1 4 2 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 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 l-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 coecient 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 l ≥ 1, we write O(d • ≥ l) to denote an unspecied element in G s of valuation at least l.

By the Baker-Campbell-Hausdor formula (cf. [START_REF] Dynkin | Calculation of the coecients in the Campbell-Hausdor formula[END_REF]), the map dened by (x, y) → x * y = log(exp(x) exp(y)) belongs to G 2 and moreover, (5.14) x * y = x + y + From that we deduce, by an induction on s, that (5.15)

x 1 * • • • * x s = x 1 + • • • + x s + O(d • ≥ 2).
We denote by Now we prove by an induction l, that there exists an integer C l and a word w l ∈ F s such that (5.17)

x 1 + • • • + x s = w * l x 1 C l , . . . , x s C l + O(d • ≥ l),
where w * l is the word map induced by w l which is well-dened on a neighborhood of 0 in g ×s . For l = 2, this is given by (5.15). Suppose it is true for l and we will prove it for l + 1. Let f be the sums of terms of degree l in the R ≥l on the right-hand side of (5.17). Since f has rational coecients, there is an integer C ≥ 1 such that we can write In the last step we used the fact that w * x1 C , . . . , xs C has valuation at least l. This nishes the proof of the induction step and concludes the proof of the lemma.

  [A, A] = {[a, b] | a, b ∈ A}.

[ 57 ,

 57 Denition 6.3]. Namely, (i) The topology on G is compatible with the metric d. Closed balls for d are compact. (ii) For any R ≥ 1, we have d(xg, yg), d(gx, gy), d(x -1 , y -1 ) G,R d(x, y)

δ -0 1 Id

 1 ∈ S δ1 (gX; δ -Os( 1)-O( 0 ) 1

Proposition 4 . 5 .

 45 Theorem 4.4 is true if n = 2m.

Proposition 4 . 27 .

 427 We use the notations above. For any parameter K ≥ 1 and any nite subset Z ⊂ Z n . One of the following statements is true. (i) There exists j ∈ {1, . . . , q} such that | Ij (Z)| ≥ K|Z| m n . (ii) There exists y ∈ Z I0 such that |Z ∩ -1 I0 (y)| ≥ K|Z| n-r n . (iii) There exists Z ⊂ Z such that |Z | ≥ 1 2K q+1 |Z| and | I0 (Z )| ≤ 2K q |Z| r n .

|

  I0∪I (Z)| = y∈ I 0 (Z) | I (Z ∩ -1 I0 (y))|.Hence, by Hölder's inequality,y∈ I 0 (Z) I∈C | I (Z∩ -1 I0 (y))|

n≥1 1 n

 1 id V -π(exp(x)) n whenever π(exp(x)) -id V < 1.It follows that there is r > 0 depending only on π such thatStab G (W ) ∩ B G (1, r) ⊂ exp(Stab g (W )). Let U = B G (1, r2 ). 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 ))

f (g 1

 1 , . . . , g n ; W ) = n i=1 B W (0,1) d(g i • w, W ) 2 dw.

  y] + O(d • ≥ 3).

  [x, y] * the group commutator x * y * (-x) * (-y) and by [x 1 , . . . , x s ] * the repeated group commutator [x 1 , [x 2 . . . , [x s-1 , x s ] * ] * ] * . We have by (5.14), [x, y] * = [x, y] + O(d • ≥ 3) and again by an induction on s, (5.16) [x 1 , . . . , x s ] * = [x 1 , . . . , x s ] + O(d • ≥ s + 1).

  Théorème 5.2 (Estimée somme-produit dans les représentations). Soient G un groupe de Lie et V un G-module de dimension nie. Il existe un voisinage U de l'élément neutre de G tel que la proposition suivante soit vraie. Étant donnés Chapter 1 Introduction For any set A, we denote by |A| or #A its cardinality. Landau notations O(f )

  f (x 1 , . . . , x s ) =where each m i is a repeated bracket of length l. Hence by(5.16) and (5.15), there is w ∈ F s a product of repeated commutators such thatf (x 1 , . . . , x s ) = w * x 1 C , . . . , x s C + O(d • ≥ l + 1).

					N i=1	m i	x 1 C	, . . . ,	x s C
	Hence
	x 1 + • • • + x s = w * l	x 1 C l	, . . . ,	x s C l	+ w * x 1 C	, . . . ,	x s C	+ O(d • ≥ l + 1)
	= w * l	x 1 C l	, . . . ,	x s C l	* w * x 1 C	, . . . ,	x s C	+ O(d

• ≥ l + 1).

Dans le cadre discrétisé, la taille d'un ensemble à l'échelle δ est évaluée par son nombre de recouvrement par δ-boules (également connu sous le nom de l'entropie métrique). Dans cette thèse, nous étudions les propriétés combinatoires des ensembles discrétisés sous l'addition, la multiplication et les projections orthogonales. Il y a trois parties principales. Premièrement, nous démontrons un théorème somme-produit dans les algèbres de matrices, qui généralise un théorème somme-produit de Bourgain concernant l'anneau des réels. On améliore aussi des estimées somme-produit en dimension supérieure obtenues précédemment par Bougain et Gamburd. Deuxièmement, on étudie les projections orthogonales des sous-ensembles de l'espace euclidien et étend ainsi le théorème de projection discrétisé de Bourgain aux projections de rang supérieur. Enn, dans un travail en commun avec Nicolas de Saxcé, nous démontrons un théorème produit dans les groupes de Lie parfaits. Ce dernier résultat généralise les travaux antérieurs de Bourgain-Gamburd et de Saxcé.

Dans leur article original, le théorème est énoncé pour l'anneau Z, mais leur démonstration est valable pour tout anneau intègre totalement ordonné. vii

Par normée on entend une norme qui fait de l'espace vectoriel sous-jacent un espace vectoriel normé. Et comme toutes les normes sur un espace vectoriel de dimension nie sont équivalentes, on peut la supposer sous-multiplicative. viii

Une action Γ X est dite µ-raide pour une mesure µ sur Γ si toute mesure µ-stationnaire est Supp(µ) -invariante. La terminologie est due à Furstenberg[START_REF] Furstenberg | Stiness of group actions[END_REF].

Un groupe est dit de croissance polynomiale si pour une/toute partie génératrice A, |A s | est majoré par un polynôme en s quand s tend vers +∞.

In their original paper, the theorem was stated for Z but their proof works in any totally ordered ring without zero-divisor.

By "normed" we mean there is a norm which makes the underlying linear space E a normed vector space. Since all norms on E are equivalent, we can always assume that the norm is submultiplicative if we want.

We mean a norm which makes the underlying linear structure a normed vector space.

We mean 0 = V 0 < . . . < V l = V are submodules such that V i /V i-1 are all irreducible.

d (x, y), (x , y ) 2 = d(x, x ) 2 + d(y, y ) 2for all pairs (x, y), (x , y ) ∈ X × Y .Lemma 2.6. Let n and m be positive integers. Let A ⊂ R n be a bounded subset and ϕ : R n → R m a K-Lipschitz map.

Proof. This is a direct consequence of Proposition 2.10. Without loss of generality, we can suppose that the norm on E is Euclidean. Denote by n the dimension of E. Let ν be the normalized restriction of the Lebesgue measure to A(δ) . The assumption (ii) of Proposition 2.10 for β = n follows immediately from Lemma 2.1.Let µ be the push forward of ν under the map E → End(E), a → l a where l a denote the left multiplication by a. We claim that µ satises the assumption (i) of Proposition 2.10 with α = 1.For any ξ ∈ E, denote by m ξ the linear endomorphism a → t l a ξ. The linear application E → End(E), ξ → m ξ is injective since E is unital. Thus, there exists c > 0 such that m ξ ≥ c ξ . Let ξ, η ∈ E with ξ = 1 and let ρ ≥ δ.1 smaller than a constant depending on E and .

Freiman problem asks, in a given abelian group, which subsets grow slowly under addition. Freiman's Theorem asserts that they are "close" to generalized arithmetic progressions. Obtaining a polynomial bound for this theorem is one of the fundamental open problems in additive combinatorics. See[START_REF] Tao | Additive combinatorics[END_REF] Chapter 5].

The condition dim(E) > 1 is needed to have assumption (iv).

We mean a norm which makes the underlying linear structure a normed vector space.

In this example, the norm on E is submultiplicative, i.e. ∀x, y ∈ E, xy ≤ x y . This assumption is not restrictive since every norm on E is equivalent to a submultiplicative one.

Each matrix is seen as an endomorphism of the Euclidean space R n , C n R 2n or H n R 4n .

π V (y) = d (Ry, V ⊥ ∩ (V + V )) y = d (Rgy, V ⊥ ∩ (V + V )) y .

Proof. For 0 < m ≤ n, denote by P(n, m) the statement we want to show. Note that for all n ≥ 1, P(n, n) is trivially true. We will proceed by an induction similar to that in the proof of Theorem 4.4. It suces to show the following two types of inductive steps. Let 0 < m ≤ n and q, r > 0 be integers.(i) If mq ≤ n, then P(n, qm) implies P(n, m).(ii) If n = q(n -m) + r with 0 < r ≤ n -m, then P(n, r) and P(n -r, m) imply P(n, m).

The V and τ in the subscript indicate that the implied constant depends not only on V but also on the bilinear form.

Proof. It suces to deal with the special case where V = R n endowed with the standard Euclidean norm. Let g be the endomorphism which sends the canonical basis to the ρ-almost orthonormal basis (a i ). By Lemma 3.6, g -1 ≤ ρ -O [START_REF] Aka | Diophantine properties of nilpotent Lie groups[END_REF] . Let s be the matrix of τ in the canonical basis. Then a straightforward computation tells us that for all x ∈ V , t gsx is the column vector (τ (a i , x)) i . Hence

Proof of Lemma 3.14. By Lemma 3.7, A contains a δ -almost orthonormal basis (a i ) 1≤i≤n of E. Thus, by Lemma 3.15 applied to the non-degenerate bilinear form τ E , for all x ∈ E, x < δ 1-O( ) whenever |tr E (a i x)| < δ for all i = 1, . . . , n.

Consider the map Θ : A → R n dened by x → tr E (a i x) i . On the one hand, this map is "almost injective" with the δ-blurred vision : for all x, y ∈ A, if Θ(x) -Θ(y) < δ then x -y < δ 1-O( ) . It follows that

On the other hand, the set Θ(A) is contained in the n-fold Cartesian product

We obtain the desired estimate by combining the two inequalities above.

Eective Wedderburn theorem

The Wedderburn theorem (see [START_REF] Lang | Algebra[END_REF]Chapter XVII,[START_REF] Benoist | A spectral gap theorem in simple Lie groups[END_REF] or [START_REF] Serre | Applications algébriques de la cohomologie des groupes. ii : théorie des algèbres simples[END_REF]) states that if R n is an irreducible representation of an nite-dimensional algebra E, then E is isomorphic to either M n (R) or M n 2 (C) or M n 4 (H). In this section we prove a quantied version of this algebraic fact. From now on, we endow these matrix algebras with operator norms 5 . Let M n 2 (C) R denote a xed embedding of M n 2 (C) in M n (R) and M n 4 (H) R a xed embedding of M n 4 (H) in M n (R).

Proposition 3.16. Let 0 < ρ ≤ 1 2 be a parameter. Let E be a subalgebra of M n (R) acting ρ-irreducibly on R n . Then either E = M n (R) or E is conjugate to M n 2 (C) R or to M n 4 (H) R by a change of basis matrix g ∈ GL(R n ) satisfying g + g -1 ≤ ρ -O (1) .

In particular, E is isomorphic to M n (R) or M n 2 (C) or M n 4 (H) by an isomorphism which is ρ -O(1) -bi-Lipschitz.

Eective diagonalization

The following lemma is implicit in [30, proof of Proposition 7.4]. We include its proof for the sake of completeness.

So there is λ 0 ∈ [0, 1] such that |P (λ 0 )| ρ O (1) . Take h = h λ0 . we have

and |det(h)| ρ O (1) , which implies (1) .

Here the rst inequality can be seen from the Cartan decomposition of h.

Proof of Proposition 3. [START_REF] Boutonnet | Local spectral gap in simple lie groups and applications[END_REF]. Consider K = C(E) the centralizer of E in M n (R).

From (the proof of) Wedderburn's theorem, K is a division algebra over R and E is equal to C(K), the centralizer of K. By the Frobenius theorem, the real division algebra K is isomorphic to R, C or H. The action of K on R n makes R n a K linear space. Hence n is even if K C and a multiple of

or respectively to M n 4 (H). The Skolem-Noether theorem (see [50, 12.6]) tells us all embeddings of M n 2 (C) or

4 (H) in M n (R) are conjugate (by a matrix in GL(R n )). We are going to show that under our quantitative irreducibility assumption, the change of basis matrix can be nicely chosen.

From the discussion above, we see that an embedding of M n 2 (C) is uniquely determined by an embedding of C in M n (R). Moreover, if K is conjugate to a xed embedding of C, then E is conjugate to a xed embedding of M n 2 (C) by the same change of basis matrix. The same applies to the quaternion case. That is why we are going to study embeddings of C and of H. Let ϕ 0 : C → M n (R) denote the embedding of C such that C(ϕ 0 (C)) = M n 2 (C) R and ψ 0 : H → M n (R) the embedding of H such that C(ψ 0 (H)) = M n 4 (H) R . When K is isomorphic to C, denote by ϕ : C → M n (R) the embedding of C whose image is K. The homomorphism ϕ is uniquely determined by ϕ(i) and we have E = C(ϕ(i)). The matrix ϕ(i) satises ϕ(i) 2 = -Id n , which implies that ϕ(i) is diagonalizable over C and its eigenvalues can only be i or -i. Its trace is real. Therefore the multiplicities of the two eigenvalues must be equal. We conclude that ϕ(i) is conjugate (over C) to the diagonal matrix diag(i Id n 2 , -i Id n 2 ). From Lemma 3.18 and the irreducibility assumptions on E, we have ϕ(i) ρ -O [START_REF] Aka | Diophantine properties of nilpotent Lie groups[END_REF] . Then by Lemma 3.17, ϕ(i) is conjugate to diag(i Id n 2 , -i Id n 2 ) by a change of basis matrix g ∈ GL n (C) satisfying g + g -1 ρ -O [START_REF] Aka | Diophantine properties of nilpotent Lie groups[END_REF] . The same is true for ϕ 0 (i). We conclude that ϕ(i) is conjugate to ϕ 0 (i) by a change of basis matrix g ∈ GL n (C) with g + g -1 ρ -O [START_REF] Aka | Diophantine properties of nilpotent Lie groups[END_REF] . Finally, thanks to Lemma 3.19, g can be chosen to be real. This nishes the proof for the case where K C.

When K is isomorphic to H, denote by ψ : H → M n (R) the embedding of H whose image is K. The homomorphism ψ : H → M n (R) is uniquely determined by ψ(i) and ψ(j) and E = C(ψ(i)) ∩ C(ψ(j)).

The two matrices ψ(i) and ψ(j) satisfy (3.5) ψ(i) 2 = ψ(j) 2 = -Id n and ψ(i)ψ(j) = -ψ(j)ψ(i).

Repeating the argument in the complex case, Lemma 3.18 gives the estimates ψ(i) , ψ(j) ρ -O(1) . Moreover, ψ(i) is conjugate to diag(i Id n 2 , -i Id n

2 ) by

Proof. Suppose that η ∈ E is a unit vector satisfying (3.8). Since A is δ -away from subalgebras, by Proposition 3.11, there is a δ O( ) -almost orthonormal basis of E of the form (a i ηb i ) i with a i , b i ∈ A dim(E) . Then (3.8) implies that for all i = 1, . . . , dim(E), [0, δ α ]a i ηb i ⊂ A s+2 dim(E) + B(0, δ α+β-O( ) ).

Moreover, Lemma 3.6 yields

Hence (3.11) holds for suciently small and slightly worse α, β and s.

Proof of Theorem 3.4. The idea is to apply Proposition 3.22 at various scales ranging from δ to δ . Let 1 , α, β and s be the constants given by Proposition 3.22 applied to κ 2 in place of κ. Let r = ln( 0) ln(α)-ln(α+β) and for k = 0, . . . , r, dene δ k = δ For all k = 1, . . . , r, assumptions of Proposition 3.21 at scale δ k are satised provided that < 1

Hence,

Hence, B(0, δ 0 ) ⊂ A rs + B(0, δ).

Proof of Theorem 3.1

We deduce Theorem 3.1 from Theorem 3.4 and Lemma 2.9.

Proof of Theorem 3.1. Suppose for a contradiction that for arbitrarily small > 0, there exists A ⊂ E satisfying the assumptions of Theorem 3.1 but

We will show a contradiction when is smaller than a constant depending only on E, κ and σ.

On the one hand, applying Theorem 3.4 with 0 = dim(E)-σ 2 dim(E) , we obtain an integer s ≥ 1 depending only on E, κ and σ and such that B(0, δ 0 ) ⊂ A s + B(0, δ).

Hence

(3.12)

On the other hand, by Lemma 2.9, (3.13)

The inequalities (3.12) and (3.13) lead to a contradiction when is suciently small.

Remark. Conversely, a growth statement like Theorem 3.1 always implies a statement like Theorem 3.4. The idea is to use the growth statement repeatedly until the set is nearly "full-dimensional" and then Proposition 2.10 shows that within a few more steps, it grows to "full dimension".

Growth under linear action

We prove Theorem 3.2 in this section.

Acting on R n , probabilistic method

We endow End(R n ) with its usual operator norm. Recall that we denote by

First we study the special case where the collection of endomorphisms A is the unit ball in End(R n ) or one of these two subalgebras. Actually, it is a direct consequence of [START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF]Proposition 1]. Here, we present an elementary proof of this easier fact. Lemma 3.23. Given κ > 0 and σ < n, there is > 0 such that the following holds for δ > 0 suciently small. Let E be End

Proof. Let µ be the normalized Lebesgue measure on B E (0, 1). It is easy to verify that µ satises the assumptions of the following proposition with τ = n.

Note that B E (0, 1) contains the identity Id.

Proposition 3.24. Given κ > 0 and 0 < σ < τ , there is > 0 such that the following holds for δ > 0 suciently small. Let X be a subset of R n and µ a probability measure on

(iv) The support of µ, Supp(µ) ⊂ B(0, δ -),

A sum-product estimate in simple Lie algebras

In this last section, we prove Corollary 3.3. Let g be a normed real simple Lie algebra. We consider the adjoint representation ad : g → End(g), i.e. ad(a)x = [a, x] for all a, x ∈ g.

Proof of Corollary 3.3. It suces to apply Theorem 3.2 to the set A ⊂ g and the set of endomorphisms ad(A) ⊂ End(g). Note that the kernel of ad is the center of g which is trivial for g is simple. Therefore, ad is a bi-Lipschitz map from g to its image. This gives the non-concentration condition on ad(A). Moreover, the quantitative irreducibility condition of Theorem 3.2 is guaranteed by the following lemma.

Lemma 3.26. Let 0 < ρ ≤ 1 2 be a parameter. Let A be a subset in a normed simple Lie algebra g of nite dimension. Assume that A ⊂ B(0, ρ -1 ) and that A is ρ-away from Lie subalgebras in g. Then ad(A) acts ρ Og(1) -irreducibly on g.

Proof. Without loss of generality, we can assume the norm on g to be Euclidean. The statement and proof of Lemma 3.9 remains valid when the word "subalgebra" is replaced by "Lie subalgebra". Actually this fact is implicit in [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]Lemma 2.5]. Therefore, as in the proof of Lemma 3.10, we can assume that A is nite of cardinality at most n and contained in B(0, 1). Write A = {a 1 , . . . , a n }.

Suppose the conclusion were false, which means there is W 0 linear subspace of dimension 0 < k < n such that for all w ∈ B W0 (0, 1) and all i = 1, . . . , n, d(ad(a i )w, W 0 ) < ρ C where C is a large constant to be determined by the use of the ojasiewicz inequality below. Consider the following real analytic map :

From the above, f (W 0 ; a 1 , . . . , a n ) ρ C . Application of the ojasiewicz inequality (Theorem 3.8) to the compact set Gr(g, k) × B(0, 1)

Now our set A is not ρ-away from the Lie subalgebra g W1 . Hence g W1 must be g, which in turn implies that W 1 is an ideal in g. This contradicts the simplicity of g.

The natural action of the orthogonal group O(n) on the Grassmannian preserves d , i.e.

because in this case we can always send

Moreover, when we have several subspaces, V 1 , V 2 , . . . , V q of R n , we dene

where for each i = 1, . . . , q, v i is the wedge product of the elements of an orthonormal basis of V i . For example, if x 1 , . . . , x n ∈ R n are unit vectors, then

Below are some other elementary properties of d . Lemma 4.9. If U, V, W are linear subspaces of R n , then (4.8)

Consequently, if V 1 , . . . , V q are also linear subspaces, then (4.9)

Proof. If the sum U + V is not a direct sum, then d (U, V, W ) = 0 and d (U, V ) = 0. Otherwise, let u and v be wedge products of orthonormal bases of U and V respectively. Then u ∧ v/ u ∧ v is the wedge product of an orthonormal basis of U + V . Then (4.8) follows immediately from the denition.

The estimates (4.9) can be obtained by a simple induction. The inequality (4.10) follows from (4.9) since, by (4.9), the right hand side of (4.10) is equal to d (V 1 , . . . , V q , W ) which, by (4.9) again, is equal to

Proof. We will proceed by induction. Let q = 2. Obviously, there is nothing to prove if V 1 + V 2 is not a direct sum. Moreover, without loss of generality, we can assume that

We have gy ∈ V and since

This proves the rst inequality in (4.13).

Lemma 4.13. Let V, W be linear subspaces of R n with dim V ≤ dim W and

In particular, if moreover dim V = dim W , then for any bounded subset A ⊂ W , (4.15)

Hence, by (4.13), π V (a -b) ≤ δ . We then conclude by using (2.3).

Lemma 4.14. Let V, W, U be linear subspaces of R n , with U ⊂ W . We have (4.16)

Proof. Both sides of (4.16) vanish if the dimension of V = π W (V ) is smaller than V . So we can assume that dim V = dim V = r. Let (v 1 , . . . , v r ) be an orthonormal basis of V . Then (π W (v 1 ), . . . , π W (v r )) is a basis of V . Moreover, by (4.4), we have

and

where u is the wedge product an orthonormal basis of U . The desired equality (4.16) follows from the fact

and Lemma 4.9 applied to V, U, W ⊥ :

Intersections

Here we collect two useful lemmata about intersections and unions of intersections.

The rst one is about intersections of large subsets. Let A be a Borel set in R n . Let Θ be an index set equipped with a probability measure µ and for each θ ∈ Θ, we have a Borel subset A θ of A. We need an appropriate measurability, namely, the map (x, θ) → 1 A θ (x) is required to be measurable.

Technical lemmata

In this section, we show the deduction of Theorem 4.1 from Theorem 4.4 and collect several other lemmata which are needed in the next section. Since they are mostly about technical details, it is advisable to skip their proofs for a rst reading. In this section, implied constants in Landau notations O(f ) and Vinogradov notations f g may depend on the dimension n and the parameter κ. Every statement is true only for δ > 0 suciently small and by suciently small we mean smaller that a constant depending on all other parameters (e.g. n, m, α, κ and ) but not on A nor on µ. Typically, if Proposition 4.17. Assume that 0 < m < n, 0 < α < n, κ > 0 and > 0 are parameters that make Theorem 4.4 true. Let A be a subset of R n contained in the unit ball. Let µ be a probability measure on Gr(R n , m). Assume that µ satises (4.3) and A satises (4.2) and (4.1 )

Then (4.17)

The idea is the following. A rst application of Theorem 4.4 gives a subset A ⊂ A with µ(E(A , )) ≤ δ . Either A is large enough in which case we are done or we can cut A out of A and apply Theorem 4.4 again. This will give us another subset A . Then we iterate until the union of these A s is large enough.

Proof. Let N ≥ 1 be positive integer. Suppose we have already constructed A 1 , . . . , A N such that A (δ) i are pairwise disjoint and µ(E(A i , )) ≤ δ for every i = 1, . . . , N . Either we have (4.18)

in which case we stop, or the set A \ N i=1 A (2δ) i satises both (4.1) and (4.2). In the latter case Theorem 4.4 gives us

N +1 is disjoint with any of A (δ) i , i = 1, . . . , N . When this procedure ends write A 0 = N i=1 A i . Then (4.18) and (4.1 ) im-

N δ (A0) . We claim that

65

where the index set I runs over subsets of {1, . . . , N } with i∈I a i ≥ δ 2 . The desired upper bound (4.17) then follows immediately from Lemma 4.16.

We now proceed to show the claim. Let V ∈ E(A, 3 ). By denition, there exists A ⊂ A with N δ (A ) ≥ δ 3 N δ (A) and N δ (π V (A )) ≤ δ -m n α-3 . Consider the index set I dened as

We have, by (2.1) and (2.5),

Hence i∈I a i ≥ δ 2 . On the other hand, for all i ∈ I, since

we have

Hence V ∈ E(A i , ) for all i ∈ I. This nishes the proof of the claim.

Action of linear transformations

Clearly, all the assumptions and the conclusion of Theorem 4.4 are invariant under the action of the orthogonal group O(n). The next proposition states that the action of a δ --bi-Lipschitz linear transformation only aects them by a factor of δ O( ) . Here, while f ∈ GL(R n ) acts on R n in the usual way, it acts on the Grassmannian by multiplication by f ⊥ := (f -1 ) * or equivalently,

Let A be a bounded subset of R n and µ a probability measure on Gr(R n , m).

(i) For each of the assumptions (4.1)(4.3) of Theorem 4.4, if it holds for A and µ with the parameters α, κ and then it also holds for the image set f A and the image measure f ⊥ * µ with the parameters α, κ and O( ) in the place of .

. In particular, if the conclusion of Theorem 4.4 holds for f A and f ⊥ * µ with some > 0 in the place of then it holds for A and µ with = O(1) .

(iv) For all V ∈ Gr(R n , m) and all x ∈ f ⊥ V ,

Non-concentration property for projections

Let A a subset of R n as in Theorem 4.4. We want to understand whether a projection of A still satises some similar regularity property as A does. More precisely we want a large subset A of A such that

for some κ 1 proportional to κ and some multiple of .

In the special case where m divides n, we have the following result. We will only need this non-concentration result in this special case, although a more general result might be true. Lemma 4.19. Let n = qm with q ≥ 2. For any parameters 0 < α < n, κ > 0 and > 0, the following is true for δ > 0 suciently small. If A is a subset of R n contained in the unit ball and µ is a probability measure on Gr(R n , m) satisfying the assumptions (4.1)(4.3) for the parameters α, κ and , then

The idea of the proof is the following. When V ∈ E(A), there is a large subset A with small projection to V . We then remove small bers of the projection π V : A → V to get A . Any large subset in of π V (A ) will have large preimage by π V . Thus if V / ∈ E reg (A) then there will be a cylinder with axis V ⊥ and radius ρ in which A is very dense. If there are a lot of such V we can then intersect these cylinders to get a ball of radius ρ 1 q which will contradict the assumption (4.2).

Proof. For conciseness, write

q -. Now we want to remove small bers of the map π V restricted to A . Consider the set

We have, for all y ∈ V ,

for otherwise y would belong to B and the intersection

would be empty. Consequently,

It follows that N δ (A ) ≥ δ -α+3 . Since V / ∈ E reg (A), the non-concentration property (4.21) fails for π V (A ). Hence there exists x ∈ V and ρ ≥ δ such that (4.23)

Let B be a maximal 6δ-separated subset of π V (A )∩x (ρ) . From (2.1) and (4.23), we have | B| ρ κ1 δ -α q -11 . Moreover for all y ∈ B, by the denition of A ,

. Since B is 6δ-separated, all these balls y (2δ) with center y ∈ B are 2δ-away from each other. Consequently,

This nishes the proof of the claim.

To obtain a contradiction, suppose that µ(E(A) \ E reg (A)) ≥ δ 2 . Note that the radius ρ in the claim depends on V . However, from (4.2) and (4.22) we know that it ranges from δ to δ 5 . For the argument below, we want (4.22) to hold for a lot of V ∈ E(A) \ E reg (A) with a same ρ ≥ δ. Indeed, by a simple pigeonhole argument 2 , we can nd a subset D ⊂ E(A) \ E reg (A) and a radius ρ ≥ δ such that µ(D) ≥ δ 3 and for all V ∈ D, there exists x ∈ V such that

and hence, by Lemma 2.1,

Let V 1 , . . . , V q be random elements of Gr(R n , m) independently distributed according to µ. On the one hand, from Lemma 4.15 applied to the restriction of µ to D, it follows that with probability at least 1 2 (ρ 2κ1 δ -4 ) q µ(D) q ≥ 1 2 ρ 2qκ1 δ -q , there exists

On the other hand, from (4.9) and (4.3), it follows that with probability at least 1 -(q -1)δ -ρ κ q , we have (4.25)

This means that for some (V 1 , . . . , V q ), both (4.24) and (4.25) hold. By Lemma 4.10, there exists x ∈ R n such that

Combining this with (4.24) yields

which is impossible with our choice of κ 1 .

2 Arrange dierent ρ into intervals of the form

Non-concentration property for slices

We will also consider slices of A, i.e. intersection of A with a δ-neighborhood of a ane subspace. When n = qm, we have similar non-concentration results for (n -m)-dimensional slices of A.

Lemma 4.20. Let n = qm with q ≥ 2 a positive integer. Let 0 < α < n, κ > 0 and > 0 be parameters. If the statement in Theorem 4.4 fails for the set A, then there is a (n -m)-dimensional ane subspace y + W and a subset

where

Here is an outline of the proof. The negation of Theorem 4.4 to A will imply that a large subset of A is a large subset of a Cartesian product (of q factors). Then, because of Lemma 4.19, the rst factor can be chosen to have the non-concentration property. This in turn will imply the non-concentration property of the Cartesian product of the q -1 rst factors. Now the negation of the projection theorem will give a large slice parallel to the Cartesian product of the q -1 rst factors. The slice is nearly as big as the Cartesian product. From this we conclude that it has also the non-concentration property.

Proof. Suppose the statement in Theorem 4.4 fails for the set A ⊂ R n . This means that for any subset A ⊂ A, µ(E(A )) > δ . In particular, E reg (A) is non-empty by Lemma 4. [START_REF] Breuillard | The structure of approximate groups[END_REF].

Let 1 = 3 κ . We construct by a simple induction a sequence of subspaces V 2 , . . . , V q and a nested sequence of subsets

This is possible since at each step, we have by (4.3),

)), there exists y ∈ V q such that (4.30)

After a translation, we can suppose y = 0. We write

q and set B 0 = A q ∩W (δ) and B = π W (B 0 ). We have N δ (B) ≥ δ -β+O( ) by (4.30) and the fact that B 0 ⊂ B (δ) .

Using the same argument in Proposition 4.17, we see that in order to show P(n, m), it suces to show µ(E(A )) ≤ δ for some subset A ⊂ A. In other words, if the conclusion of P(n, m) fails for the set A then for any subset

When qm < n, we have by Lemma 4.25,

Moreover the distribution of V conditional to the event dim(V ) = qm has the corresponding non-concentration property. By P(n, qm), we know that for any C > 0, if the constant C in (4.32) is large enough (depending on C ) then the probability that there exists A ⊂ A satisfying

Suppose that P(n, m) fails for A. Then by a simple induction we show that with probability at least δ O( ) , we have

and hence, by (4.12) applied to π V (A),

We obtain a contradiction if C is large compared to any of the implied constants in the previous Landau notations.

Proof of (ii), Case 1. Assume rstly that A contains large slice of dimension n -r. More precisely, assume that there exists W ∈ Gr(R n , n -r) and x ∈ R n such that

where C is the constant given by P(n -r, m) applied to 0 < m ≤ n -r, n-r n α and κ. Without loss of generality, we can assume that x = 0 and that Lemma 4.23 tells us that we can apply P(n -r, m) to B ⊂ W with the image measure of µ by π W . Then we can conclude using Lemma 4.24.

Proof of (ii), Case 2. Otherwise A does not contain any large slice of dimension n -r :

and that the distribution of V conditional to the event dim(V ) = r has a nonconcentration property. By P(n, r), we know that for any C > 0, if the constant C in (4.32) is large enough (depending on C ) then the probability that there exists A ⊂ A satisfying

Suppose that P(n, m) fails for A. Again by an induction we show that with probability at least δ O( ) , we have

and there exists

Together with (4.33), this implies by Proposition 4.26 that there exists

Again we obtain a contradiction if C is large compared to any of the implied constants in the previous Landau notations.

Proof of the main result

In this section, we prove Theorem 4.4 and thus Theorem 4.1. This is done by proving rst the base case where n = 2m (Propsoition 4.5) and then the induction steps (Propositions 4.6-4.8). Note that by Proposition 4.17, for a given pair (n, m), if Theorem 4.4 is true for these dimensions then so is Theorem 4.1.

Therefore, when we use Theorem 4.4 as induction hypothesis, the conclusion is µ(E(A)) ≥ δ while when we prove by contradiction by saying that A is a counterexample for Theorem 4.4, we are assuming µ(E(A )) > δ for all subsets A of A.

Like in the previous section, all implied constants in Landau and Vinogradov notations in this section may depend on n and κ. Again every statement in this section is true only for δ > 0 smaller than a constant depending on n, m, α, κ and .

Half dimensional projections

For the special case n = 2m, we follow mainly the proof in [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF] (which deals with the case m = 1) and use a technique in the proof of Proposition 2 in Bourgain-Glibichuk [START_REF] Bourgain | Exponential sum estimates over a subgroup in an arbitrary nite eld[END_REF].

Proof of Proposition 4.5. Let A ⊂ R n be a counterexample for Proposition 4.5. In particular, (4.34)

We will get a contradiction when is small enough. By Lemma 4.19, there is a subspace V 1 and a subset A 1 ⊂ A with the following properties:

On account of Lemma 4.18, we can suppose without loss of generality that

and this together with the inequalities (4.36) implies

)). We have, by (4.34) and (4.3), µ(D) ≥ δ -2δ 2 ≥ δ 2 . Let V ∈ D. By (4.6) and (4.7), we have

The same is true for π V |V2 . Then it follows easily from the Cartan decomposition that (4.37)

By (4.37), the map

Hence, by (2.8), we can bound from below the additive energy between π V X and π V Y ,

That is why we can apply the Balog-Szemerédi-Gowers theorem (Theorem 2.7) to get subsets

Applying π -1 V |V1 to the set in the last inequality and using (2.4), we obtain (4.40)

where

Let us apply Lemma 4.15 to the collection of subsets

with the restriction of µ to D. We obtain

By Ruzsa's triangular inequality (Lemma 2.3), (4.40) implies, for all

For the same reason N δ (X -X (δ) ∩ X (δ)

Then by Ruzsa's triangular inequality again, we have

Moreover, (4.40) with (2.4) gives (4.44)

where ϕ := ϕ V . Now successive use of Ruzsa's triangular inequality (recalling (4.42), (4.40), (4.43) and (4.44)) yields that for all V ∈ D , (4.45)

Moreover, by the Plünnecke-Ruzsa inequality (Lemma 2.4), (4.46)

Consider the set of endomorphisms

We claim that the assumptions of Theorem 3.2 are satised for A and X with replaced by O( ) and κ replaced by κ 8 . Therefore, when is small enough, (4.45) and (4.46) contradict Theorem 3.2.

Our claim about the assumptions (i), (iv) and (vi) are clear from what precedes. The assumption (v) follows from (4.35) and (4.38) because for any

Finally, to prove (ii) and (iii) we use Lemma 4.22 below. For any ρ ≥ δ and any f ∈ End(V 1 ), Lemma 4.22 gives the existence of a subspace

Hence by (4.3),

Observe that

Together with (4.41), this gives the assumption (ii), namely,

Moreover, for any nonzero proper linear subspace W ∈ V 1 , take w ∈ W some vector with w = 1 and consider

By Lemma 4.22 and (4.37), we have D ⊂ V (W , δ -O( ) ρ 0 ) for some W ∈ Gr(R n , m). In view of (4.41) and (4.3), we have δ O( ) ≤ δ -O( ) ρ κ 0 . Hence ρ 0 ≥ δ O( ) , which establishes (iii). Lemma 4.22. We use the notations in the proof above. For any nonzero vector

Proof. Without loss of generality, we can assume that dim(W ) = m -1. For any V ∈ Gr(R n , m), any v 2 ∈ V 2 and any w ∈ W , by (4.5), we have

As w can be any vector in W , we obtain

We conclude by setting W = (Rv 2 + W ) ⊥ ∈ Gr(R n , m) and using (4.7).

Projection of a slice

If the set A contains a relatively large slice of dimension 0 < n < n (a subset

) and if it has a correct non-concentration property then we can apply the induction hypothesis to B -y inside W . Instead of projecting to V distributed according to µ, we project to V = π W (V ). The rst lemma below shows that V is not concentrated and the next one shows the relationship between V being in E(B) ∩ Gr(W, m) and V being in E(B). Using this idea we prove Proposition 4.6. Lemma 4.23. Let 0 < m < n < n be integers and κ, > 0 be parameters. Let W ∈ Gr(R n , n ) and V be a random element of Gr(R n , m) having the following non-concentration property, (4.48)

Then with probability at least 1 -δ κ-, dim(V ) = m. Conditional to this event the distribution of V is a probability measure ν on Gr(W, m). It satises

Proof. We know that dim(V ) = m if and only if d (V, W ⊥ ) > 0. The rst part follows immediately from (4.48). Let us show the non-concentration property for ν. Let U be a

Lemma 4.24. Let 0 < m ≤ n < n be integers. Let 0 < α < n and > 0 be parameters. Let B ⊂ W be a bounded subset in a n -dimensional linear subspace W ⊂ R n . Then

Proof. Let V ∈ E(B, ) \ V (W ⊥ , δ ). Then there exists B ⊂ B such that

Denote by V the projection π W (V ). It follows from Lemma 4.13 that

That is why

Proof of Proposition 4.6. Let n = qm and suppose that Theorem 4.4 holds for n = (q -1)m and m. Let A and µ be as in Theorem 4.4 but for which the conclusion fails. By Lemma 4.20, there is an n -dimensional ane subspace y + W and a subset B ⊂ A (δ) ∩ (y + W ) such that

where β = q-1 q α. Without loss of generality, we can assume y = 0 and B ⊂ A. Let V be a random element of Gr(R n , m) distributed according to µ. Dene ν be as in Lemma 4.23. By the lemma, we can apply Theorem 4.4 combined with Proposition 4.17 to B ⊂ W with the probability measure ν on Gr(W, m). We obtain a constant > 0 depending only on n , β and κ such that when ≤ , ν E(B, ) ∩ Gr(W, m) ≤ δ .

Set 1 = 3 κ . By Lemma 4.24, we have

When ≤ O(1) , the last two inequalities together with (4.3) yield

which nishes the proof of Proposition 4.6.

Projection to a sum of subspaces

In the situation where m < n 2 , we consider the sum

where q is a positive integer such that qm < n and V 1 , . . . , V q are m-dimensional subspaces. Using the inequality (4.12), the size of the projection to V can be bounded in terms of the sizes of the projections to each V j . In the next lemma, we prove that if V i are independently randomly distributed according to a measure with an appropriate non-concentration property then the distribution of their sum V has a non-concentration property as well. This allows us to apply Theorem 4.4 with the dimensions n and m = qm. This idea leads to the proof of Proposition 4.7.

Lemma 4.25. Let n, m, q, r be positive integers such that qm + r = n. Let

Then with probability at least 1 -(q -1)δ κ-, we have (4.49)

Then the probability measure µ on Gr(R n , qm) dened as the distribution of

the event (4.49) satises the non-concentration

Proof. Let V 1 , . . . , V q be as in the statement. By their independence, for every

Hence, on account of (4.9), with probability at least 1 -(q -1)δ κ-, we have

. By (4.10), we know that if

then for some j = 1, . . . , q,

78 which happens with probability at most δ -ρ κ q . Therefore,

Proof of Proposition 4.7. Let n, m, q, r be positive integers such that qm+r = n. Suppose Theorem 4.4 is true for the dimensions n and m = qm but it fails for the dimensions n and m with parameters 0 < α < n, κ > 0 and > 0. Let A and µ be a counterexample, i.e. A and µ satisfy (4.1)(4.3) but µ(E(A )) > δ for all subsets A ⊂ A. We will get a contradiction when is smaller than a constant depending only on n, α and κ.

Let V 1 , . . . V q be random elements of Gr(R n , m) independently distributed according to µ. Let µ be the probability measure on Gr(R n , qm) dened as in Lemma 4.25. Thanks to Lemma 4.25, we can apply Theorem 4.4 combined with Proposition 4.17 with dimensions n and m = qm to the set A and the measure µ . It gives = (n, α, κ) > 0 such that if ≤ then the probability that there exists

The rest of the proof consist of proving a lower bound for the same probability. First, V 1 ∈ E(A) with probability at least δ . When this happens, there is

) with probability at least δ 2 . When this happens, there is

Then we continue this construction until we get A q .

To summarize, we have with probability at least δ (2q-1) ,

and there exists a subset A q ⊂ A satisfying N δ (A q ) ≥ δ q N δ (A) and for every

and hence, by Lemma 4.11,

This leads to a contradiction when ≤ O(1) .

Projection to intersection of subspaces I: a discrete model

When the projections of a set A to subspaces V 1 , . . . , V q are all small, we would like to say that its projection to the intersection

as well. This is not true. A typical example is A = (Re 1 ⊕ Re 2 ) ∪ Re 3 where for each j = 1, . . . , q. Then we conclude easily form Proposition 4.27 by setting K = δ -2 and

For the general case we consider a map f ∈ GL(R n ) which sends isometrically V to Span(e n-r+1 , . . . , e n ) and V ⊥ j to Span(e (j-1)(n-m)+1 , . . . , e j(n-m) ) for each j = 1, . . . , q. It is easy to see that f -1 ≤ n and

Therefore f is δ -O( ) -bi-Lipschitz. The conclusion for A follows from the special case applied to f A. Indeed, by the inequality (2.4) and Lemma 4.18, the hypotheses are satised for f A and f ⊥ V 1 , . . . , f ⊥ V q with replaced by O( ). Moreover, the conclusion for f A and Proof of Proposition 4.8. Let n, m, q, r be as in Proposition 4.8. Assume that Theorem 4.4 is true for the dimensions n and m = r and assume that A and µ are counterexample to Theorem 4.4 for the dimensions n and m with parameters 0 < α < n, κ > 0 and > 0. We begin by making two remarks. Firstly, we can assume that (4.51)

for otherwise, we could conclude directly by using Proposition 4.21.

Secondly, we can also assume that A does not contain very large slice of codimension r. More precisely, we can assume that

Indeed, if (4.52) fails, then put B = π W A ∩ (x + W (δ) ) and we can apply Proposition 4.21 to B ⊂ W to obtain that E(B) ∩ Gr(W, m) does not support any measure with the corresponding non-concentration property in Gr(W, m). We can conclude as in Subsection 4.3.2 by using Lemma 4.23 and Lemma 4. [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF].

From now on assume (4.51) and (4.52). Let V 1 , . . . , V q be random elements of Gr(R n , m) independently distributed according to µ. On account of (4.7), the non-concentration property (4.3) implies similar property for the distribution of

From Lemma 4.25 applied to V ⊥ 1 , . . . , V ⊥ q , we know that with probability at least 1 -(q -1)δ κ-, the intersection

82

Let µ be the distribution of V conditional to this event. Then µ has the non-concentration property

That is why we can apply Theorem 4.4 combined with Proposition 4.17 to the set A and the measure µ with n and m = r. We obtain = (n, α, κ) > 0 such that if ≤ then the probability that there exists A ⊂ A satisfying

As the conclusion of Theorem 4.4 fails for A, we have µ(E(A )) ≥ δ for all subsets A ⊂ A. Using a similar construction as in the proof of Proposition 4.7, we prove that with probability at least δ O( ) , we have

and there exists A q ⊂ A satisfying N δ (A q ) ≥ δ O( ) N δ (A) and for all j = 1, . . . , q,

Therefore, all the hypotheses of Proposition 4.26 are satised for the set A q with O( ) in the place of . In particular, the assumption (ii) is guaranteed by (4.1) and (4.51) and the assumption (iv) is guaranteed by (4.52). Hence there exists a subset A ⊂ A q such that

This leads to a contradiction when ≤ O(1) .

Projection of fractal sets

In this section we derive Corollary 4.2 and Corollary 4.3 from Theorem 4.1.

The ideas of the proof of Corollary 4.2 are contained in that of [START_REF] Bourgain | The discretized sum-product and projection theorems[END_REF]Theorem 4]. We include the proof here for the sake of completeness.

Proof of Corollary 4.2. Let 0 < m < n, 0 < α < n, κ > 0 be parameters. Let > 0 be one fourth of the constant given by Theorem 4.1 applied to these parameters. Let A and µ be a counterexample for the corollary with these parameters. Without loss of generality we can assume A ⊂ B(0, 1).

After normalizing µ we can suppose that it is a probability measure such that

Thus, the non-concentration condition (4.3) of Theorem 4.1 is satised for sufciently small δ.

By Frostman's lemma (recalled in Theorem 1.1), there is a nonzero Radon measure ν compactly supported on A such that (4.53)

For any V ∈ Supp(µ) we have dim H (π V (A)) ≤ η where η = m n α + 2 . By the denition of Hausdor dimension, for any k 0 ≥ 1, there is a cover

Integrating with respect to dµ(V ) and using Fubini's theorem, we obtain

This in turn implies that there exists k ≥ k 0 such that µ(E) ν k -2 where

Now x this k and set

Note that as we can choose k 0 arbitrarily large, we can make δ arbitrarily small.

Here we cannot apply Theorem 4.1 directly to the set A because it might not be regular enough. The idea is to partition A into regular parts. Let Q denotes the set of dyadic cubes in R n of side length δ:

Put L = n + 1. For l = 0, . . . , L, let A l be the union of all cubes Q ∈ Q such that

It is easy to see that A l are disjoint and L l=0 ν(A l ) ≥ (1-δ )ν(A). Moreover for any l = 0, . . . , L and any A ⊂ A l which is also a union of cubes in Q, we have

Hence, if ν(A l ) > 0, then for such A , (4.54)

the set of levels with sucient mass. For any l ∈ L, by (4.53),

and from (4.54) and (4.53), for any ρ ≥ δ and any x ∈ R n ,

In other words, the assumptions of Theorem 4.1 are satised for A l . Now for l ∈ L and V ∈ E, let A V,k,l be the union of

From the denition of L and E, we know that for any

Hence there exists l ∈ L such that ν(A V,k,l )

Therefore by setting

we have

This contradicts Theorem 4.1 applied to the set A l and the measure µ. Indeed,

and moreover

Now we deduce Corollary 4.3 from Corollary 4.2.

Proof of Corollary 4.3. We can choose a metric on the Grassmannian Gr(R n , m) which is invariant under the action of the group O(n). Observe that the exceptional set of directions

is measurable for the Borel σ-algebra on Gr(R n , m). Suppose that the Hausdor dimension of the exceptional set is larger than m(n-m)-1+κ for some κ. Then by Frostman's Lemma there exists a nonzero Radon measure µ supported on this exceptional set such that for all ρ > 0 and all V ∈ Gr(R n , m), µ(B(V, ρ)) ≤ ρ m(n-m)-1+κ . We are going to prove that µ satises the non-concentration property forbidden by Corollary 4.2. We x W ∈ Gr(R n , m) and apply the ojasiewicz inequality (recalled at Theorem 3.8) to the analytic function d (•, W ) 2 : Gr(R n , m) → R. We conclude that there is a constant C > 0 such that for any 0

Here again, the estimate is uniform in W thanks to the O(n)-invariance. Therefore,

This contradicts Corollary 4.2 if is suciently small and nishes the proof of Corollary 4.3.

Chapter 5

Product estimates in perfect

Lie groups

This last chapter is a joint work with Nicolas de Saxcé. The aim is to generalize Saxcé's discretized product theorem (Theorem 1.7) to perfect Lie groups.

In this chapter, by default, Lie groups and Lie algebras are real. Recall that a Lie group G is said to be perfect if its Lie algebra g satises the condition [g, g] = g. The radical R of G is the unique maximal normal closed connected solvable subgroup in G. The Lie algebra of R is the radical r of g. The quotient group G/R is semisimple. If G is simply connected, then G/R is simply connected, hence a direct product of simply connected simple Lie groups. Factors appearing in this direct product are called simple factors of the group G.

Theorem 5.1 (Product theorem for perfect Lie groups). Let G be a simplyconnected perfect Lie group. There is a neighborhood U of the identity in G such that the following holds. Given σ < dim(G) and κ > 0, there exists > 0 such that for all δ > 0 suciently small, if a subset A ⊂ U satises

(ii) for any simple factor S of G, denote by π S : G → S the canonical projection, ∀ρ ≥ δ, N ρ (π S (A)) ≥ δ ρ -κ ;

(iii) for any proper closed connected subgroup H < G, there exists a ∈ A with d(a, H) ≥ δ ;

For G = SU(d), d ≥ 2, this is due to Bourgain-Gamburd [START_REF] Bourgain | On the spectral gap for nitely-generated subgroups of SU(2)[END_REF][START_REF] Bourgain | A spectral gap theorem in SU(d)[END_REF]. For simple groups, it is due to Saxcé [START_REF] De Saxcé | A product theorem in simple Lie groups[END_REF]. Denition. A subset A satisfying condition (iii) will be said to be δ -away from closed connected subgroups.

As an intermediate result, we have a sum-product type estimate for representations of Lie groups which is interesting on its own right. Throughout this chapter, all linear representations are nite-dimensional and over the eld of real numbers. They all come with a norm. Constants in our results depend not only on the algebraic structure but also on the choice of the norm. However, since all norms on a nite-dimensional linear space are all equivalent, if we have the result for one norm, we have it for any norm at a loss of a constant factor. In particular, we can always assume that the norm is Euclidean.

Let V be a representation of G. Let A a subset of G and X a bounded subset of V . For s ≥ 1, recall that A, X s stands for the set of elements in V that can be obtained as sums, dierences and products of at most s elements of A and X.

Denition. For ρ > 0, we say X is ρ-away from submodules if for any proper submodule W < V , there is x ∈ X such that d(x, W ) ≥ ρ.

Theorem 5.2 (Sum-product estimates in representations). Let G be a Lie group and V nite-dimensional linear representation of G. There exists a neighborhood U of the identity in G depending only on V such that the following holds. Given 0 , κ > 0, there exists s ≥ 1 and > 0 such that for all δ > 0 suciently small, if A ⊂ U and X ⊂ B V (0, 1) satisfy the following :

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

where

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

(iii) X is δ -away from submodules.

Then,

In particular, considering R * acting on R, we can recover Bourgain's discretized sum-product theorem (Theorem 1.4). Similarly, we can recover discretized sum-product estimates for C or H.

Outline of the proof

The proof of Theorem 5.1 goes as follows. In view of Lemma 2.13, we can investigate the growth of (A ∪ {1} ∪ A -1 ) s , s ≥ 1. The strategy is to prove that after a bounded number of steps (depending on 0 ), it becomes δ-dense in a ball of radius δ 0 , for any prescribed 0 > 0.

Theorem 5.3. Let G be a simply connected perfect Lie group. There exists a neighborhood U of the identity in G such that the following holds. Given κ > 0 and 0 > 0, there exists > 0 and s ≥ 1 such that for all δ > 0 suciently small, if A is a subset of U such that (i) for any simple factor S i of G denote by π Si : G → S i the projection,

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 V /W . For (ii), note that a Jordan-Hölder sequence of G-submodules in V can be rened to a Jordan-Hölder sequence of H-submodules, and that if there is a trivial quotient in the rst sequence there must be also one in the rened sequence. Finally, (iii) is clear, since Jordan-Hölder decompositions of V into G-modules coincide with Jordan-Hölder decompositions into G/H-modules.

Remark. The class P(G) is the smallest class of nite-dimensional representations of G containing all non-trivial irreducible representation of G is in P(G) and such that if W and V are in P(G), and

Example.

• 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).

• The representation of

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

• Condition (i) of Theorem 5.2 implies V ∈ P(G).

Whenever V is a normed vector space, we endow the space of linear endomorphisms End(V ) with the associated operator norm. Moreover, the norm on V induces a norm on each submodule W . There is also a natural norm on each quotient V = V /W , given by the formula

where π : V → V is the canonical projection. Throughout this chapter, quotients will be equipped with this norm.

For example, with this convention, it is easy to see that if π : V → V is a quotient map then π(X) is ρ-away from submodules in V whenever X is ρ-away from submodules in V .

The proof of Theorem 5.2 goes by induction on the length of the Jordan-Hölder decomposition of V . We shall prove the base case, where V is a nontrivial irreducible representation, in the next subsection. The induction step will then be carried out in subsection 5.1.3.

Irreducible representations

In the case V is an irreducible representation of G, Theorem 5.2 is a variant of Theorem 3.2. We state it and prove it here for completeness. Theorem 5.5 (Base case: irreducible representations). Let G be a Lie group and π : G → GL(V ) an irreducible representation. There is a neighborhood U of the identity in G such that the following holds. Given 0 , κ > 0, there exist s ≥ 1 and > 0 such that for all δ > 0 suciently small, if A ⊂ U and X ⊂ B V (0, 1) satisfy

Observe that condition (i) implies that the representation V is non-trivial.

Recall that we say a subset A ⊂ End(V ) acts ρ-irreducibly on V for some ρ > 0 if for any proper linear subspace W ⊂ V , there is a ∈ A, w ∈ B W (0, 1) such that d(aw, W ) ≥ ρ.

Proposition 5.6. Let V be a nite-dimensional normed vector space. Given 0 , κ > 0, there exist s ≥ 1 and > 0 such that for all δ > 0 suciently small, if

In the following proof, we use the notations in Chapter 3 : if K is a division algebra over R then End(K n ) denotes the space of real endomorphisms of K n and M n (K) denotes the space of n × n matrices with coecients in K. Furthermore, we identify M n (K) with the subspace of End(K n ) consisting of K-linear maps.

Proof. Given 1 > 0, it follows from Proposition 3.25 that there exists c > 0 such that, provided > 0 is small enough, there exists a δ -O( ) -bi-Lipschitz linear bijection f :

and K n is endowed with its usual L 2 norm, and a scale δ

and for every proper subalgebra

Choosing 1 small enough in terms of 0 and κ, we may then apply Theorem 3.4 to conclude that, provided > 0 is suciently small, then for some integer s,

Therefore, without loss of generality, we may assume that V = K n and

(5.1)

We can further assume that v = 1. Then

90

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 (5.1), we have in particular

Hence, starting from (5.1), we may multiply both sides by δ 1 id to obtain

and iterating this procedure, we get, for all k ≥ 2, for some integers s k depending on k,

).

for some integers k ≥ 0 and s ≥ 1. Choosing k > 2 c and combining all these inclusions, we nd, for

which proves the proposition.

The above proposition readily implies Theorem 5.5.

Proof of Theorem 5.5. It suces to apply Proposition 5.6 to the set π(A) ⊂ End(V ). By assumption on A, conditions (i) and (iii) of the proposition are satised for the set π(A). That condition (ii) is also satised is a consequence of Lemma 5.7 below.

Lemma 5.7. 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 closed connected subgroups then π(A) acts ρ Oπ(1) -irreducibly on V .

The proof of this lemma is an application of ojasiewicz's inequality, but rst, it is convenient to reduce to the case where A is nite. For that, we use another lemma. Let π : G → GL(V ) be a representation and 0 < ρ < 1 2 a parameter. We say that a subset A ⊂ G 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 of W , i.e.,

away from closed connected subgroups then A contains a subset of cardinality at most dim G which is ρ Oπ(1) -away from proper stabilizers.

Here by O π (1) we mean a constant depending on the algebraic structure of G and π and the distance on G.

Remark. Note that in this 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 where n is some integer.

Assuming that π(A) does not act 1 nC ρ C -irreducibly on V , we can nd W ∈ Gr(V, k) such that for all a ∈ A and all w ∈ B W (0, 1), π(a)w ∈ W +B V (0, 1

Then it follows from the inequality above that there exists W ∈ Gr(V, k) 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 5.2 is the following lemma.

Lemma 5.9. Let G be a Lie group acting on a nite-dimensional normed vector space V . There exists a neighborhood U of the identity in G and a constant C ≥ 1 such that for any parameters δ, ρ 1 , ρ 2 with 0 < δ ≤ ρ 1 ≤ ρ 4 2 ≤ 1, the following holds when ρ 1 is suciently small.

Let

(5.3)

Proof. On account of Lemma 5.8, we may assume that A is nite of cardinal n ≤ dim(G) and is ρ 1 C

1 -away from proper stabilizers. Shrinking again the neighborhood U if necessary, we can further assume that the action on V of any element in A is 2-bi-Lipschitz.

Let σ : B V (0, ρ 2 ) → X be a section of the projection π, i.e. for any y ∈

The assumption (i) yields

because we have respectively

It follows from Lemma 5.10 that there exists a linear section ϕ :

The properties of σ imply the following properties for ϕ. For all y ∈ V and all

Let W 0 be the image subspace of ϕ. From the above, it follows that (5.4) the restriction π |W0 : W 0 → V is 2ρ -2 2 -bi-Lipschitz;

(5.5)

1 );

(5.6)

1 );

(5.7)

1 .

Let a 1 , . . . , a n be the elements of A and write a = (a 1 , . . . , a n ). Consider the analytic function dened on G ×n × Gr(V, dim(V )) dened by

By (5.7), we have f (a, W 0 ) ≤ ρ 1 3

1 . By ojasiewicz's inequality (Theorem 3.8) applied to the compact set Ū ×d × Gr(V, dim(V )), there exists a constant C depending only on the representation V such that for all g = (g 1 , . . . , g n ) ∈ U ×n and W ∈ Gr(V, dim(V )),

where Z is the zero set of f . Therefore there exists b = (b 1 , . . . , b n ) and

1 . The equality f (b, W ) = 0 exactly means that each b i belongs to the stabilizer Stab G (W ), and hence

1 -away from proper stabilizers, hence W must be a G-submodule. Finally, conclusions (5.2) and (5.3) follow from (5.4), (5.5), (5.6) and the fact that W is ρ

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 5.10 (Almost additive maps). Let 0 < δ ≤ ρ 1 ≤ ρ 2 ≤ 1 be parameters.

Let V and V be nite dimensional normed vector spaces.

Then there is a linear map ϕ : V → V such that for all x ∈ B V (0, ρ 2 ), σ(x) -ϕ(x)

V (-log δ + 1)ρ 1 .

Proof. Rescaling by a factor ρ -1 2 in V , we can suppose without loss of generality that ρ 2 = 1.

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

Using this and a simple induction, we prove that (5.8)

Let N be the integer such that 2 -N ≤ δ < 2 -N +1 . It follows from (5.8) and the assumption (i) that (5.9)

For any x ∈ [0, 1], let (x 1 , . . . , x N ) ∈ {0, 1} N be the N rst digits in its binary expansion, i.e. for some r ∈ [0, δ], x = N n=1 x n 2 -n + r. Then by the assumption (ii), (5.8) and (5.9),

Consequently,

This nishes the proof for the special case. For general normed vector space V , pick a basis (u 1 , . . . , u d ) consisting of vectors of unit length then apply the special case to each partial function t → σ(tu i ), i = 1, . . . , d. Then by (ii), we have the desired inequality for any vector in

where k ∈ N depends only on V and the choice of the basis. We conclude by using k times the almost additivity (ii).

We can now prove Theorem 5.2.

Proof of Theorem 5.2. The proof goes by induction on the length l of the Jordan-Hölder decomposition of V . The base case l = 1, where V is a nontrivial irreducible representation, corresponds to Theorem 5.5, and is proved above. to 3 . Using the induction hypothesis for the representation V with 4 and κ, we obtain

where s ≥ 1 is a constant depending only on V , 4 and κ. Replacing A, X (δ) s by X, we may assume without loss of generality that B V (0, δ 4 ) ⊂ π(X).

Lemma 5.9 applied with ρ 1 = δ 2 and ρ 2 = δ 4 gives a submodule W < V such that π |W is 3δ -4 -bi-Lipschitz and

(5.11)

) ⊂ X (δ1) where δ 1 = δ 2 C . We want to apply base case Theorem 5.5 to the nontrivial irreducible representation V /W at scale δ 1 with 3 and κ. Observe that π |W being 3δ -4 -bi-Lipschitz implies that π

Therefore when 4 and are small enough (according to V 1 , 3 and κ),

where s ≥ 1 is a constant depending only on V 1 , 3 and κ. Together with inclusion (5.11), this implies that

Cutting A, X s+1 into cylinders of axis V 1 and diameter δ 3 and picking the part with largest size, we see that

-away from submodules. Applying the induction hypothesis to A acting on π(X) ⊂ V , we know that

where s ≥ 1 is a constant depending only on V , 3 and κ. Let s = max{s , 2s+ 2} and set X = A, X s ∩ V (δ 3 ) 1 so that X is δ O( 3) -away from submodules and

At this stage apply Lemma 5.9 to the set X (δ) with ρ 1 = δ 2 and ρ 2 = δ 3 . If 3 is chosen suciently small compared to 2 , conclusion (5.3) fails. Therefore there must be v ∈ A, X (δ)

contains a vector of length at least δ 2 . If we did this argument at scale 1 C δ with C a large constant depending on s , we would get the claim of the third step. This nishes the proof of the theorem.

Product theorem for perfect Lie groups

In this section we prove Theorem 5.3.

Here, we adhere to the convention that the metric d on G is left-invariant and on any quotient G/N , the distance is dened by x, y ∈ G,

In particular the metric on G/N is left invariant and moreover if N is another normal closed subgroup of G such that N < N then the canonical projection

Unless the contrary is stated, throughout this section, G denotes a simply connected perfect Lie group and g its Lie algebra. Moreover R denotes the radical of G and r the radical of g.

Perfect Lie algebras and Lie groups

We will list some elementary and standard facts about perfect Lie groups and Lie algebras.

First, recall that r is nilpotent since g is perfect, see e.g. [2, Lemma 2.4]. Let s be a Levi factor of g, i.e. a Lie subalgebra s such that g = s r, see e.g. [START_REF] Serre | Lie algebras and Lie groups[END_REF]Corollary 1,p. 49]. Note that the group theoretic Levi decomposition holds for G, i.e. there is a closed connected subgroup S of Lie algebra s such that G = S R, because since G/R is simply connected, a section of g → g/r integrates to a section of G → G/R (cf. [54, Theorem 1, p. 152]). Lemma 5.11. 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.

Recall also that ideals in a semisimple Lie algebra are sums of its simple factors. Hence a maximal ideal is a sum of all simple factors except one.

Proof. Suppose the contrary, then n+r = g for some proper ideal 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, (5.12)

which is impossible since r is solvable and n is proper. Indeed, (5.12) is true for i = 0. Suppose that it is true for some i ≥ 0 then from [g, g] = g follows that

since n is an ideal. This is exactly (5.12) for i + 1 and nishes the proof of the lemma. Lemma 5.12 (Perfect abelian extension of a semisimple group). If r is abelian, then the adjoint representation of G is of class P.

Remark. 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).

Proof of Lemma 5.12. We have an exact sequence of G-modules 0 → r → g → g/r → 0, and by Proposition 5.4(i), all we need to check is that both r and g/r belong to P(G).

On the one hand, the representation G → GL(g/r) factors through G/R and the adjoint representation of the semisimple group G/R belongs to P(G/R). By Proposition 5.4(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, and moreover,

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 5.4(ii).

Remark. 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 nontrivial centers. For instance, let G = SL(2, R) F 2,2 , where F 2,2 is the free 2-nilpotent Lie algebra over 2 generators x, y, and the action of SL(2, R) is by linear substitution. The adjoint representation of G on its Lie algebra g = sl(2, R) F 2,2 is not of class P, because G acts trivially on the center of g, generated by [x, y].

Abelian extensions of semisimple groups

Here, we prove Theorem 5.3 in the case where the radical r is abelian. In some sense, this is the most important case of the result, as we will see in 5.2.3 that the general case follows from this one.

To prove Theorem 5.3 in this case, the idea is to apply Theorem 5.2 to the adjoint representation of G on its Lie algebra, and then to use the Campbell-Hausdor formula. Before that, we note that condition (i) in Theorem 5.3 automatically implies non-concentration for the image of A under any nontrivial group homomorphism. Lemma 5.13. Let H be another Lie group. Let ϕ : G → H be a nontrivial homomorphism. 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 5.3. Then

Proof. The isomorphism G/ ker ϕ → ϕ(G) is bi-Lipschitz when restricted to compact neighborhoods. Hence without loss of generality, we can suppose 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 [54, Theorem 4, p. 154], n is the Lie algebra of a normal closed connected subgroup N < G. This subgroup N contains ker ϕ. By Lemma 5.11, n is exactly the kernel of the projection of g to one of the simple factors of g/r. It follows that G/N is one of the simple factors of G. We deduce the desired estimate from condition (i) of Theorem 5.3 by using the fact that G/ ker ϕ → G/N is 1-Lipschitz.

Proof of Theorem 5.3, case where r is abelian. We start by the case where the radical r of g is abelian. In this proof, implied constants in Landau and Vinogradov notations depend G and the parameter κ.

By Lemma 5.12, the adjoint representation of G on g is of class P. We would like to apply Theorem 5.2 to A and X = log(AA -1 ∩ B G (1, δ )). The hypotheses of Theorem 5.2 are all met with replaced by O( ) : assumption (i) is guaranteed by Lemma 5.13; A being a δ -away from subgroups is exactly assumption (ii) of Theorem 5.3.

It remains to check that X is δ O( ) -away from any proper submodule W in g. We can assume W maximal. Hence it is a maximal proper ideal of g, which by Lemma 5.11 is the Lie algebra of ker π Si where S i is a simple factor of G. In particular, there are only nitely many such W . Shrinking the neighborhood U if necessary, it suces to check that AA -1 ∩ B G (1, δ ) is δ O( ) -away from ker π Si . By assumption (i), for any ρ ≥ δ,

The last quantity is larger than 1 if we choose

That is why we can use Theorem 5.2 to get an integer s ≥ 1 such that (5.13)

when is small enough. The idea is now to apply the Campbell-Hausdor formula at an order l such that the error term is of size at most δ. We identify an element of the free group F s generated by s elements and the word map 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 esasier 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-Hausdor formula. Lemma 5.14. Let exp : g → G denote the exponential map of a Lie group. We x a norm on g and a distance on G. For all integers s ≥ 1 and l ≥ 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 ,

This lemma is a metric analogue of [1, Lemma 3.5] and the proofs are similar.

Proof. Consider g-valued functions f dened on a neighborhood of 0 in g ×s that can be written as a sum of a convergent series f (x 1 , . . . , x s ) = We choose l > 1 and apply the lemma to x i of the form x i = Ad(a i )y i with a i ∈ A s and y i ∈ X. By denition X ⊂ B g (0, δ ), so the error term is indeed of size O s (δ l ) = O(δ), and therefore, for some s = O s,l (1). Recalling (5.13), we obtain

This nishes the proof of the theorem in the case r is abelian.

Proof of the product theorem, general case

We now have to explain how to deal with the case where the radical r is nilpotent but not necessarily 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

For A and B subsets of G, we shall write The precise lemma that we shall use is as follows.

Lemma 5.15. Let R i , i ≥ 1 denote the lower central series of R then for i ≥ 1

there is k ≥ 1 such that for all ρ > 0 small enough,

Proof. Denote by r i , i ≥ 1 the lower 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 , ∀j. Consider the map f j : R → R i+1 dened as

Hence f is a C 1 -dieomorphism on a neighborhood of 0. We conclude by using the fact that the exponential maps is a also bi-Lipschitz on a neighborhood of 0.

We are now ready to nish the proof of Theorem 5.3.

Proof of Theorem 5.3, general case. Here again implied constants in Landau and Vinogradov notations depend on G and κ.

Let R i , i ≥ 1 denote the lower central series of the group R, i.e. R 1 = R and R i+1 = [R, R i ]. Recall that since G is simply connected, these normal subgroups R i , i ≥ 1 are all closed and connected. 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]. The quotients G/R i are simply connected. We proceed by induction on the nilpotency class l of R. We already see that Theorem 5.3 holds if l ≤ 1. Now suppose that R has nilpotency class equal to l and that Theorem 5.3 has been proved if the nilpotency class is strictly less that l.

We rst remark that the assumptions of Theorem 5.3 are preserved when projecting to a quotient. The nilpotency class of the radical of G/R l is l -1. So by the induction hypothesis, we have when is small enough compared to 1 ,

where 1 > 0 is a constant which we will choose according to 0 and s ≥ 1 is an integer depending on κ and 1 . Without loss of generality, we can replace (A ∪ {1} ∪ A -1 ) s B G (1, δ) by A. In particular, B R (1, δ 1 ) ⊂ (R ∩ A)R l and B R l-1 (1, δ 1 ) ⊂ (R l-1 ∩ A)R l .

By Lemma 5.15, we have (1) .

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

, where π G/R l : G → G/R l denote the canonical projection.

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

). Then A satises the assumptions of Theorem 5.3 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 l involving in this inclusion is within distance δ 2 1 from the identity, we can conclude using (5.18) that

This nishes the proof of Theorem 5.3. Title : Sums, products and projections of discretized sets Keys words : Sum-product phenomenon, metric entropy, projection theorem, Lie groups, product theorem Abstract : In the discretized setting, the size of a set is measured by its covering number by δ-balls (a.k.a. metric entropy), where δ is the scale. In this document, we investigate combinatorial properties of discretized sets under addition, multiplication and orthogonal projection. There are three parts. First, we prove sum-product estimates in matrix algebras, generalizing Bourgain's sum-product theorem in the ring of real numbers and improving higher dimensional sum-product estimates previously obtained by Bourgain-Gamburd. Then, we study orthogonal projections of subsets in the Euclidean space, generalizing Bourgain's discretized projection theorem to higher rank situations. Finally, in a joint work with Nicolas de Saxcé, we prove a product theorem for perfect Lie groups, generalizing previous results of Bourgain-Gamburd and Saxcé.

He Weikun

Université Paris-Saclay Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France