THÈSE DE DOCTORAT UNIVERSITÉ PARIS 6

Spécialité Mathématiques

Présentée par Guillaume Aubrun

Pour obtenir le grade de Docteur de l’Université Paris 6

Sujet de la thèse

Convexité en grande dimension, matrices aléatoires et théorie quantique de l’information

Soutenue le 15 décembre 2005 devant le jury composé de

MM. Philippe Biane Examinateur
Bernard Maurey Examinateur
Alain Pajor  Rapporteur
Gilles Pisier  Examinateur
Mark Rudelson Rapporteur
Stanisław Szarek Directeur de thèse

2

Je tiens à remercier Staszek Szarek pour avoir encadré ma thèse. Il a su me guider au travers de mathématiques variées et passionnantes. La confiance qu’il a placée en moi, au même titre que sa constante bonne humeur, ont contribué à rendre ces années agréables. Malgré la distance, il a toujours répondu à mes questions avec précision et patience.

Alain Pajor et Mark Rudelson ont accepté de rapporter ce travail, et ce en un délai très bref. Je leur en suis très reconnaissant. Je remercie également Alain pour les nombreuses discussions que nous avons eues au cours de la dernière année, qui ont joué un rôle prépondérant dans ce travail.

Merci aussi à Philippe Biane, Bernard Maurey et Gilles Pisier de me faire l’honneur de participer à mon jury.

J’ai eu la chance au cours de ces années d’effectuer plusieurs séjours à l’étranger. Je veux exprimer ici toute ma gratitude envers tous ceux qui ont rendu possibles ces voyages. Merci encore à Staszek et Margaretmary pour leur accueil. À Apostolos dont la générosité fut sans égale je dirai simplement : ευχαριστώ πολύ.

Cette thèse a été effectuée au sein de l’Équipe d’Analyse Fonctionnelle, je tiens à en remercier vivement tous les membres. Merci en particulier à Olivier Guédon qui a répondu à mes nombreuses interrogations. Ma formation mathématique doit aussi beaucoup aux groupes de travail organisés à Marne-la-Vallée, dont je remercie tous les participants, notamment Matthieu Fradelizi avec qui j’ai eu grand plaisir à travailler. Je remercie également Elisabeth Werner pour les longues discussions que nous avons eues.

Je suis toujours heureux de parler de mathématiques avec des amis ; je voudrais notamment citer Yves Cornulier et Romain Tessera avec qui j’ai de fortes interactions mathématiques. Merci aussi à tous les autres amis avec qui j’ai eu des fortes interactions non nécessairement mathématiques.

Merci enfin à Aurélie.

4

Table des matières

1 Petites déviations 19 1.1 Introduction et présentation des résultats . . . . . . . . . . . . 20 1.2 Small deviations for a random matrix . . . . . . . . . . . . . . 23

1.2.1 Convergence in terms of a Wasserstein distance …. 25 1.2.2 The small deviation inequality . . . . . . . . . . . . . . 26 1.2.3 Relation to determinants . . . . . . . . . . . . . . . . . 29 1.2.4 Convergence of the operators . . . . . . . . . . . . . . 33 1.2.5 An elementary proof of asymptotics for ψ_{TW} . . . . . . 38

2 Échantillonnage de corps convexes 43

2.1 Introduction et présentation des résultats . . . . . . . . . . . . 44 2.1.1 Notations et position du problème . . . . . . . . . . . . 44 2.1.2 Convexes et mesures log-concaves isotropes . . . . . . . 47 2.1.3 Matrices aléatoires et échantillonnage . . . . . . . . . . 52

2.2 Sampling convex bodies . . . . . . . . . . . . . . . . . . . . . 56 2.2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . 56 2.2.2 The case of the unit ball of ℓ_{p}^{n} . . . . . . . . . . . . . . 59 2.2.3 The case of unconditional log-concave measures : proof

of theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . . 65

2.3 Appendice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.3.1 Version quasi-isométrique du théorème 2.2 . . . . . . . 72

3 Théorie quantique de l’information 73

3.1 Introduction et présentation des résultats . . . . . . . . . . . . 74 3.1.1 Motivations et principales définitions . . . . . . . . . . 74 3.1.2 Estimation de certains paramètres géométriques liés à

la séparabilité et à l’intrication . . . . . . . . . . . . . 77 3.1.3 Faiblesse asymptotique du critère de Peres . . . . . . . 81

3.2 Separable states on N qudits . . . . . . . . . . . . . . . . . . . 82 3.2.1 Introduction and summary of results . . . . . . . . . . 82 3.2.2 Preliminaries about convex bodies . . . . . . . . . . . . 87 3.2.3 Proof of Theorem 3.2 : Small number of large subsystems 93 3.2.4 Proof of Theorem 3.3 : Large number of small subsystems 97 3.2.5 Proof of Theorem 3.4 : Tight upper bounds on the inradii100 3.2.6 Proof of Theorem 3.5 : Asymptotic weakness of PPT

criterion . . . . . . . . . . . . . . . . . . . . . . . . . . 102

3.3 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.3.1 Preuve du théorème 3.1 . . . . . . . . . . . . . . . . . 104 3.3.2 Preuve du théorème 3.4’ . . . . . . . . . . . . . . . . . 108 3.3.3 Majoration précise du supremum d’un processus gaussien109 3.3.4 Preuve du lemme 20 . . . . . . . . . . . . . . . . . . . 111

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

Introduction

7

Cette thèse s’inscrit dans le cadre de l’Analyse Géométrique Asymptotique, domaine en pleine expansion dont le but est l’étude des propriétés géométriques des corps convexes, ou des espaces normés, de dimension finie mais très grande. Cette discipline a émergé d’une branche de l’Analyse, la théorie locale des espaces de Banach, qui vise à étudier les espaces de Banach de dimension infinie à travers leurs sous-espaces de dimension finie. L’investigation du comportement de diverses quantités lorsque la dimension, ou tout autre paramètre pertinent, tend vers l’infini (ou vers 0, selon le contexte), est un thème central dans de nombreux domaines des mathématiques. Par exemple, une large branche de la théorie des Probabilités étudie de telles problématiques. Mais les résultats-limites sont parfois peu efficaces lorsqu’ils ne sont pas quantifiés, et cette étape de quantification est souvent d’une difficulté supérieure. Plusieurs exemples viennent de la théorie des matrices aléatoires. Leur utilité pour l’Analyse Géométrique Asymptotique n’est plus à démontrer. Il est en effet connu depuis E. Gluskin que des méthodes probabilistes permettent d’exhiber des corps convexes dont les propriétés géométriques sont, en un certain sens, extrémales, tandis que les exemples explicites ou déterministes construits jusqu’ici sont très loin de posséder de telles propriétés. Ces techniques nécessitent de contrôler la norme (ou d’autres paramètres) d’opérateurs aléatoires.

Le modèle le plus simple de matrices aléatoires est l’Ensemble Gaussien Unitaire, objet paradigmatique qui reflète les propriétés asymptotiques d’une plus large classe d’ensembles matriciels. Il consiste en la donnée d’une matrice hermitienne de taille n × n dont les coefficients sont des variables aléatoires gaussiennes complexes (essentiellement) indépendantes. La norme d’une telle matrice, ainsi que sa plus grande valeur propre λ_{max}, sous la normalisation adéquate, tendent presque sûrement vers une limite finie ℓ quand la dimension n tend vers l’infini. La phénomène de concentration de la mesure (dans notre cadre, pour la mesure gaussienne), outil fondamental utilisé notamment par V. Milman pour démontrer le théorème de Dvoretzky, nous permet d’écrire une inégalité de déviations pour λ_{max}. Cette inégalité décrit bien la décroissance gaussienne dans le régime des grandes déviations. Cependant, elle passe à côté d’un autre phénomène, plus subtil, découvert par C. Tracy et H. Widom : λ_{max} fluctue autour de sa limite à l’échelle n^{−2/3}, nettement en deçà de l’échelle n^{−1/2} usuelle dans le cadre gaussien. Cependant, le résultat de Tracy–Widom est un théorème-limite et peut difficilement être utilisé pour l’étude de matrices d’une taille donnée. Nous y remédions à travers l’inégalité suivante, qui constitue une version quantifiée du phénomène découvert par Tracy–Widom : pour toute dimension n et pour tout ε > 0

P(λ_{max} ⩾ ℓ + ε) ⩽ C exp (−cn max(ε^{3/2}, ε^{2})) ,

C et c étant des constantes universelles. Le régime ε^{3/2} correspond aux petites déviations et le régime ε^{2} aux grandes déviations, de type gaussien. Ce résultat a été obtenu indépendamment par M. Ledoux. Notre preuve, exposée dans le chapitre 1, utilise la méthode des polynômes orthogonaux (dans ce cas les polynômes de Hermite), qui repose sur la propriété d’invariance du modèle par conjugaison unitaire. La démonstration redonne également le théorème-limite de Tracy–Widom.

D’autres ensembles de matrices aléatoires ne jouissent pas des mêmes symétries et l’étude de leur spectre est plus délicate. Par exemple, fixons une variable aléatoire Z de loi ν, centrée et suffisamment régulière, et considérons une matrice dont les coefficients sont des copies indépendantes de Z. Le cas où Z est une gaussienne est relativement proche du cas décrit précédemment. Une telle matrice, à N lignes et n colonnes (N ⩾ n), peut être vue comme un opérateur de plongement de ℓ_{2}^{n} dans ℓ_{2}^{N}. Par un résultat de Z. Bai et Y. Yin, la distorsion (ou le nombre de conditionnement) de ce plongement, c’est-à-dire la manière dont la norme euclidienne est déformée, est contrôlée asymptotiquement (lorsque la dimension tend vers l’infini) par le rapport n/N. Il s’agit encore une fois d’un résultat-limite, sans analogue quantifié. Un problème géométrique équivalent est le suivant : soit N vecteurs aléatoires indépendamment distribués selon la mesure-produit ν^{⊗n}, est-ce que l’ellipsoïde d’inertie de la mesure ν^{⊗n} est loin de l’ellipsoïde d’inertie empirique reconstitué à partir des N échantillons ? Il n’y a aucune raison de se restreindre à des mesures-produits pour ce problème d’échantillonnage. En termes de matrices aléatoires, cette généralisation revient à considérer des matrices dont seulement les lignes sont indépendantes, en autorisant des dépendances parmi les coefficients d’une même ligne. On sort ainsi de la théorie classique des matrices aléatoires. Le problème de l’approximation de la matrice d’inertie a été étudié dans le cas de la mesure uniforme sur un corps convexe, suite aux travaux de R. Kannan, L. Lovász et M. Simonovits en géométrie algorithmique : leur motivation était d’approcher efficacement la position isotrope d’un corps convexe. Des améliorations ont ensuite été obtenues par J. Bourgain ainsi que M. Rudelson. Jusqu’à présent, les seuls exemples connus de convexes dont l’ellipsoïde d’inertie est uniformément approximable avec un nombre d’échantillons proportionnel à la dimension (on ne peut espérer mieux) étaient les convexes dont toutes les marginales sont uniformément sous-gaussiennes, classe fort restreinte. Nous montrons qu’il en est de même pour la boule-unité de ℓ_{1}^{n}, corps convexe très différent de ces exemples. Notre preuve utilise un résultat de représentation de la mesure uniforme sur les boules-unités des espaces ℓ_{p}^{n} afin de se ramener au cas d’une matrice à coefficients indépendants, ainsi qu’un argument de concentration de la mesure pour rendre utilisable le résultat-limite de Bai–Yin. Cette idée a l’inconvénient d’être spécifique aux cas des espaces ℓ_{p}^{n}, aussi nous développons une autre approche. La preuve de Bai–Yin repose sur la combinatoire de la méthode des moments ; en relaxant cette combinatoire, on peut englober la classe des mesures log-concaves inconditionnelles sur R^{n}. Pour ces mesures nous obtenons une conclusion plus faible : l’approximation isomorphe, et non plus quasi-isométrique. En contrepartie, le nombre d’échantillons nécessaire est réduit de manière spectaculaire à ρn, où ρ > 1 est un facteur arbitraire. Ce résultat est prouvé dans le chapitre 2.

Une autre idée centrale en Analyse Géométrique Asymptotique est la suivante : les corps convexes de grande dimension présentent des symétries cachées (ou tout au moins des symétries approximatives) qui ne sont décelables que lorsqu’on les regarde à travers une structure euclidienne adaptée. Autrement dit, étant donné un corps convexe, on cherche parmi toutes ses images affines la position la mieux équilibrée. Le choix d’une « bonne » position dépend du problème considéré : citons ainsi la M-position, la ℓ-position, ou bien la position isotrope évoquée précédemment. Nous illustrons ce principe à l’aide d’un nouvel exemple venu de la théorie quantique de l’information. Un problème fondamental dans ce domaine est la quantification du phénomène de l’intrication quantique. Cette problématique peut se reformuler en termes de géométrie convexe : l’ensemble D des états mélangés d’un système quantique est un corps convexe dans un espace de matrices, et le sous-ensemble S des états séparables (non-intriqués) est un corps convexe de même dimension. Récemment, S. Szarek a introduit des outils de l’Analyse Géométrique Asymptotique pour l’étude des relations géométriques (volumes, distances, etc) entre D et S dans le cadre des qubits. Nous poursuivons cette étude pour des particules quantiques plus complexes. L’une de nos principales découvertes est l’importance du rôle joué par la structure euclidienne induite par l’ellipsoïde de Löwner de S. Cette structure, qui se combine agréablement avec le produit tensoriel projectif de corps convexes, objet que nous introduisons, permet par exemple d’obtenir un ordre de grandeur étonnant et asymptotiquement exact pour le volume de l’ensemble S. Qui plus est, nous utilisons cette structure originale pour déduire des informations — asymptotiquement exactes, ici aussi — sur la géométrie de S vis-à-vis d’une structure euclidienne plus standard, celle induite par la norme de Hilbert–Schmidt, une question récemment étudiée dans une série d’articles de Gurvits et Barnum. Ces outils et ces résultats sont présentés dans le chapitre 3.

Les différents chapitres sont indépendants, les notations communes sont expliquées ci-après. Les trois chapitres ont une architecture similaire : la première partie est une introduction en français, qui motive et énonce les résultats. La seconde partie en anglais, qui contient les preuves des théorèmes, est un article de recherche, à des modifications mineures près. Ainsi, la partie 1.2 est publiée dans Séminaire de Probabilités [Aub1]. Les parties 3.2 (travail en collaboration avec S. Szarek) et 2.2 sont soumises à des revues internationales. Enfin, le chapitre 3 contient également quelques appendices dont le premier est un travail en collaboration avec S. Szarek et E. Werner.

On pourra trouver des versions ultérieures de ce manuscrit à l’adresse

http://www.institut.math.jussieu.fr/~aubrun/

This Ph.D. thesis lies within the framework of Asymptotic Geometric Analysis, an expanding field dealing with the study of geometric properties of convex bodies, or of normed spaces, of large but finite dimension. This subject branched out from the local theory of Banach spaces, a subfield of Analysis aiming at studying infinite-dimensional Banach spaces through their finite-dimensional subspaces. Investigation of the behavior of various quantities when the dimension, or other relevant parameter, tends to infinity (or to 0, as appropriate) is a central theme in many areas of mathematics. For example, a major branch of Probability theory deals with such questions. However, limit results may be not-too-useful when non-quantified, and this quantification step is often of higher complexity. Several examples arise from random matrix theory. One hardly need to show today how useful random matrices are for Asymptotic Geometric Analysis: it is known since E. Gluskin that probabilistic methods allow to exhibit convex bodies having, in some sense, extremal geometric properties, a feature which rarely was achieved via explicit/deterministic examples. These techniques often require controlling norms (or other parameters) of random operators.

The simplest model of random matrices is the Gaussian Unitary Example, a central object reflecting asymptotic properties of a wider class of matrix ensembles. This model is the data of a complex n × n Hermitian matrix with entries being random Gaussian variables (essentially) independent. Under proper normalization, the norm of such a matrix, as well as its largest eigenvalue λ_{max}, tend almost surely to a finite limit ℓ when the dimension n tends to infinity. The concentration of measure phenomenon (applied here for the Gaussian measure), a fundamental tool introduced by V. Milman in his proof of Dvoretzky’s theorem, allows us to write a deviation inequality for λ_{max}. This inequality provides a good description of Gaussian decay in the large deviation regime. However, it misses another phenomenon, more subtle, discovered by C. Tracy and H. Widom: λ_{max} fluctuates around its limit on the scale n^{−2/3}, clearly below the scale n^{−1/2} usual in the Gaussian framework. However, the Tracy-Widom result was a limit statement, not very efficient when studying matrices of a particular size. We fill this gap with the following inequality, which constitutes a quantified version of the Tracy-Widom phenomenon: for any dimension n and any ε > 0,

P(λ_{max} ⩾ ℓ + ε) ⩽ C exp (−cn max(ε^{3/2}, ε^{2})) ,

C and c being universal constants. The rate ε^{3/2} corresponds to small deviations whereas the rate ε^{2} to large Gaussian-type deviations. This result has been independently obtained by M. Ledoux. Our proof, presented in chapter 1, uses orthogonal polynomials technique (in this case the Hermite polynomials), which depends on the invariance property of the model under unitary conjugation. In addition, our argument allows to reprove the limit theorems of Tracy and Widom.

Other random matrix ensembles have less symmetries than the Gaussian ensemble and the study of their spectrum is more tricky. Fix for example a random variable Z with law ν, centered and regular enough. Consider a matrix with independent copies of Z as entries. If Z is Gaussian, this is quite close to the previous model. Such a matrix, with N rows and n columns, can be thought of as an embedding operator from ℓ_{2}^{n} into ℓ_{2}^{N}. By a result of Z. Bai and Y. Yin, the distortion (or the condition number) of this embedding, which is the way the Euclidean norm is deformed, is asymptotically controlled (when sizes increase to infinity) by the ratio n/N. Here again this is a limit result, without quantified version available. An equivalent geometric problem is the following: given N independent random vectors distributed according to the product measure ν^{⊗n}, is the inertia ellipsoid of the measure ν^{⊗n} far from the empirical inertia ellipsoid built from the N sample points? There is actually no reason for restricting oneself to product measures for this sampling problem. In the language of random matrices, this amounts to considering matrices with independent rows, but allowing dependencies within a single row. This setting goes beyond the classical random matrix theory. The sampling problem for the inertia matrix has been studied for the uniform measures on convex bodies, following the work of R. Kannan, L. Lovász and M. Simonovits in algorithmic geometry: their motivation was to efficiently approximate the isotropic position of a convex body. Improvements were then achieved by J. Bourgain, and M. Rudelson. The only known (to date) examples of convex bodies for which the inertia ellipsoid can be approximated using sample points whose number is linear in the dimension (we cannot hope for better) are those whose all marginals are uniformly sub-Gaussian, which is a very narrow class. We show that the same holds for the unit ball of ℓ_{1}^{n}, a body very far from those examples. Our proof uses a result on representation of the uniform measure on unit ball on ℓ_{p}^{n} spaces to get back a matrix with independent entries, as well as a concentration of measure argument which make usable the limit result of Bai–Yin. The drawback of this idea is its specificity to the ℓ_{p}^{n} spaces, therefore we develop another approach. The proof by Bai–Yin is based on the moment method; by generalizing the combinatorics involved there to a less restrictive setting we can encompass the wider class of all log-concave unconditional measures on R^{n}. For these measures we obtain a weaker conclusion: isomorphic approximation instead of almost isometric. On the other hand, the number of sample points required dramatically reduces to ρn, where ρ > 1 is an arbitrary number. This result is proved in chapter 2.

Another central idea in Asymptotic Geometric Analysis is the following: high-dimensional convex bodies possess hidden symmetries (or at least approximate symmetries), which can only be revealed by introducing a proper Euclidean structure. To find it, for a given convex body, we have to seek among its affine images for the appropriately balanced position. The choice of a “good” position may depend on the problem: it could be for example the M-position, the ℓ-position, or the previously mentioned isotropic position. We illustrate this principle with a new example coming from quantum information theory. One fundamental question in that field is to quantify the phenomenon of quantum entanglement, which can be phrased as a convex geometry problem. Namely, the set D of mixed states of a quantum system is a convex body in a matrix space, and its subset, the set S of separable (non-entangled) states is also a convex body of the same dimension. Recently, S. Szarek introduced the methods of Asymptotic Geometric Analysis to the study of geometric relationships (such as volumes, distances etc.) between D and S in the case of qubits. We carry on this investigation to more complex quantum particles. One of our main discoveries is the significance of the Euclidean structure induced by the Löwner ellipsoid of S. This structure nicely interplays with the projective tensor product of convex bodies, a notion which we introduce. It also enables us to obtain the order of magnitude of the volume of the set S, a surprising and asymptotically sharp result. Moreover, we use this Euclidean structure to obtain information — also asymptotically sharp — on the geometry of S with respect to the more standard Euclidean structure induced by the Hilbert–Schmidt norm, the theme that has been recently studied in a series of papers by Gurvits and Barnum. All these results and concepts are presented in chapter 3.

Notations

Dans toute la thèse, les symboles C, c, C′, c′, C_{0}, … désigneront des constantes, dont la valeur peut varier librement d’une occurrence à l’autre. Par constante on entend constante universelle, strictement positive et finie, ne dépendant d’aucun paramètre. Les dépendances seront toujours précisées.

Lorsque l’on travaille dans l’espace euclidien R^{n}, les coordonnées d’un vecteur x sont notées (x_{1}, …, x_{n}). Le produit scalaire est noté ⟨·, ·⟩ et la norme euclidienne associée est notée | · |. La boule-unité est B_{2}^{n} = {x ∈ R^{n}; |x| ⩽ 1} et la sphère-unité est S^{n−1} = {x ∈ S^{n−1}, |x| = 1}. La mesure de Lebesgue sur R^{n} est notée vol(·). Si A et B sont des parties de R^{n}, et α un réel, on utilise les notations

αA = {αa; a ∈ A},
A + B = {a + b; a ∈ A, b ∈ B}.

Un corps convexe dans R^{n} est une partie convexe compacte d’intérieur non vide. Un corps convexe K est dit symétrique s’il est symétrique par rapport à l’origine, c’est-à-dire si K = −K. Un corps convexe de R^{n} est dit inconditionnel s’il est symétrique par rapport aux hyperplans de coordonnées, c’est-à-dire si pour tout choix de signes (ε_{i}) ∈ {−1, 1}^{n}, on a

(x_{1}, …, x_{n}) ∈ K ⟺ (ε_{1}x_{1}, …, ε_{n}x_{n}) ∈ K.

De même, une mesure μ sur R^{n} est dite inconditionnelle si elle vérifie pour toute partie borélienne B et pour tout choix de signes (ε_{i}) ∈ {−1, 1}^{n}

μ(B) = μ ({(ε_{1}x_{1}, …, ε_{n}x_{n}); x ∈ B}) .

Pour 1 ⩽ p < +∞, on définit la norme ℓ_{p} sur R^{n} par

∥(x_{1}, …, x_{n})∥_{p} = (∑_{i=1}^{n} |x_{i}|^{p})^{1/p} .

Cette définition s’étend au cas p = +∞ en posant

∥(x_{1}, …, x_{n})∥_{∞} = max_{1⩽i⩽n} |x_{i}|.

La boule-unité associée est définie par

B_{p}^{n} = {x ∈ R^{n}; ∥x∥_{p} ⩽ 1}.

Les boules B_{p}^{n} sont des exemples de corps convexes inconditionnels. On note conv(A) l’enveloppe convexe d’un ensemble A ⊂ R^{n} et ext(K) l’ensemble des points extrémaux d’un convexe K.

Toutes les variables aléatoires que nous considérerons seront définies sur un espace probabilisé (Ω, A, P) suffisamment gros. On note E l’espérance associée à P. Si X est une variable aléatoire de loi μ, on écrit X ∼^{ℒ} μ. On fera communément l’abus de langage d’identifier une variable aléatoire et sa loi. On désigne par δ_{x} la masse de Dirac au point x. L’abréviation i.i.d. signifie « indépendantes et identiquement distribuées ». On désigne par N(0, σ^{2}) la mesure de probabilité gaussienne sur R de variance σ^{2}, donnée par la densité

\frac{dN(0, σ^{2})}{dx} = \frac{1}{σ\sqrt{2π}} exp (−\frac{x^{2}}{2σ^{2}} ) .

Un vecteur gaussien est un vecteur aléatoire (X_{1}, …, X_{n}) tel que toute combinaison linéaire des (X_{i}) est une variable aléatoire gaussienne. Un exemple de vecteur gaussien sur R^{n} est le vecteur gaussien standard, noté G_{R^{n}} et dont les coordonnées, dans n’importe quelle base orthonormale, sont des variables gaussiennes N(0, 1) indépendantes. On dit d’une variable aléatoire complexe X qu’elle suit la loi N_{C}(0, 2σ^{2}) si elle se décompose en X = Y + ıZ, où Y et Z sont des variables i.i.d. N(0, σ^{2}). On dit d’une suite (μ_{n}) de mesures boréliennes sur un espace métrique T qu’elle converge étroitement vers μ si pour toute fonction f continue bornée sur T, on a

lim_{n→∞} ∫_{T} fdμ_{n} = ∫_{T} fdμ.

Si X est une variable aléatoire, et α ∈ [1, 2], la norme Ψ_{α} de X est donnée par

∥X∥_{Ψ_{α}} = inf{t > 0; E exp(|X/t|^{α}) ⩽ 2}.

Si ∥X∥_{Ψ_{α}} ⩽ C < ∞, on dit que X est Ψ_{α} avec constante C. Le lemme suivant est classique

Lemme 1. Il existe des constantes universelles c, C telles que pour tout α ∈ [1, 2] et pour toute variable aléatoire X telle que ∥X∥_{Ψ_{α}} < ∞, on ait

c∥X∥_{Ψ_{α}} ⩽ sup_{p⩾1} \frac{(E|X|^{p})^{1/p}}{p^{1/α}} ⩽ C∥X∥_{Ψ_{α}}.

Démonstration. On peut supposer par homogénéité que ∥X∥_{Ψ_{α}} = 1, c’est-à-dire E exp(|X|^{α}) = 2. L’inégalité de droite est une conséquence de l’inégalité de Markov : on obtient pour tout u > 0

P(|X| ⩾ u) ⩽ 2 exp(−u^{α}).

L’inégalité de gauche s’obtient en développant exp(|X|^{α}) en série entière.

Dans ce paragraphe, le corps K désignera toujours R ou C. On note B(E) l’espace des endomorphismes d’un K-espace vectoriel E; B(K^{n}) est aussi l’espace des matrices carrées de taille n. On note Id la matrice identité. Les coefficients d’une matrice A ∈ B(K^{n}) dans la base canonique sont notés (a_{ij})_{1⩽i,j⩽n}. Si A est une matrice complexe, A^{†} désigne la transconjuguée de A. Dans le cas où A est une matrice réelle, A^{†} est simplement la transposée de A. Une matrice A telle que A = A^{†} est autoadjointe ; on note B_{sa}(E) l’ensemble des éléments autoadjoints de B(E). On note U(C^{n}) ou U_{n} le groupe unitaire. Si une matrice A est autoadjointe, ses valeurs propres sont réelles et on les range dans l’ordre croissant (en les comptant avec multiplicité) :

λ_{min}(A) = λ_{n}(A) ⩽ ⋯ ⩽ λ_{1}(A) = λ_{max}(A).

Si A et B sont des matrices autoadjointes, la notation A ⩽ B signifie que la matrice B − A est positive (c’est-à-dire λ_{min}(B − A) ⩾ 0). Si A est une matrice p × n, avec p ⩾ n, les valeurs singulières de A sont, par définition, les racines carrées des valeurs propres de A^{†}A

0 ⩽ s_{min(A)} = \sqrt{λ_{min}(A^{†}A)} ⩽ ⋯ ⩽ s_{max}(A) = \sqrt{λ_{max}(A^{†}A)}.

L’espace B(K^{n}), (ainsi que ses sous-espaces) est muni d’une mesure de Lebesgue (notée dA) induite par le produit scalaire de Hilbert–Schmidt

⟨A, B⟩_{HS} = trA^{†}B.

La norme associée à ce produit scalaire, appelée norme de Hilbert–Schmidt, s’écrit

∥A∥_{HS} = (∑_{i=1}^{n} s_{i}(A)^{2})^{1/2} = (∑_{i,j=1}^{n} |a_{ij}|^{2})^{1/2} .

Si E et F sont des K-espaces vectoriels, E ⊗ F est le produit tensoriel de E par F. Dans le cas où E et F sont munis d’un produit scalaire, on peut construire naturellement un produit scalaire sur E ⊗ F, en posant pour x, x′ ∈ E et y, y′ ∈ F

⟨x ⊗ y, x′ ⊗ y′⟩ = ⟨x ⊗ x′⟩_{E}⟨y ⊗ y′⟩_{F} ,

qui se prolonge bilinéairement de manière unique à l’espace tout entier. L’espace E ⊗ F, muni de ce produit scalaire, est noté E ⊗_{2} F ; c’est le produit tensoriel hilbertien de E et F. Tout ceci se généralise immédiatement à des produits tensoriels de plus de deux facteurs. Si x ∈ K^{n} et y ∈ K^{m}, on désigne par |x⟩⟨y| l’opérateur de rang 1 de K^{m} dans K^{n} défini par

∀z ∈ K^{m}, |x⟩⟨y|(z) = ⟨y, z⟩x.

Si (T, d) est un espace métrique compact et ε > 0, un ε-réseau de T est une partie finie N ⊂ T telle que tout point de T est à distance au plus ε d’au moins un point de N. On utilisera le résultat suivant, prouvé classiquement par un argument volumique (cf [Pis], Lemma 4.10)

Lemme 2. Pour tout ε > 0 et pour tout entier n, il existe un ε-réseau de S^{n−1} (pour la distance euclidienne) de cardinal inférieur à (1 + 2/ε)^{n}.

Pour les notations qui ne seraient expliquées ici, nous renvoyons aux références standard en Analyse Géométrique Asymptotique [Pis, Tom, MS, LQ].

Chapitre 1 Petites déviations pour la norme d’une matrice aléatoire

1.1 Introduction et présentation des résultats

Un objet central dans la théorie des matrices aléatoires est l’Ensemble Gaussien Unitaire (GUE). Une description en est la suivante : il s’agit, pour chaque dimension n, d’une mesure de probabilité P_{n} sur l’espace B_{sa}(C^{n}) donnée par la densité :

dP_{n} = \frac{1}{c_{n}} exp (−\frac{n}{2}trA^{2}) dA.

Ici c_{n} est une constante de normalisation. La mesure P_{n} est invariante par conjugaison unitaire. Elle peut être caractérisée par la construction alternative suivante : soit B ∈ B(C^{n}) une matrice aléatoire dont les n^{2} coefficients sont des variables aléatoires gaussiennes complexes de loi N_{C}(0, 1/n). Soit A la partie autoadjointe de B, définie par A = \frac{1}{2}(B + B^{†}). Alors A est distribuée selon la mesure P_{n}. En particulier, aux contraintes de symétrie près, les coefficients d’une matrice du GUE sont des variables aléatoires indépendantes. Ceci est même une caractérisation du GUE : toute mesure de probabilité sur B_{sa}(C^{n}) invariante par conjugaison unitaire et telle que les variables aléatoires (a_{ij})_{1⩽i⩽j⩽n} sont indépendantes se déduit de P_{n} par une transformation affine (voir [Meh], livre auquel nous renvoyons systématiquement pour tout ce qui suit). Cette propriété fait du GUE un objet modèle, dont on conjecture que les propriétés asymptotiques (quand la dimension n tend vers +∞) sont universelles, c’est-à-dire qu’elles sont communes à une large famille d’ensembles matriciels de construction similaire.

Si A est une matrice de B_{sa}(C^{n}), on note μ_{A} la mesure spectrale empirique associée à A, définie par

μ_{A} = \frac{1}{n} ∑_{i=1}^{n} δ_{λ_{i}(A)}.

Si B est un borélien de R, μ_{A}(B) est la proportion de valeurs propres de la matrice A qui appartiennent à l’ensemble B. Lorsque A est un élément du GUE (c’est-à-dire une matrice aléatoire distribuée selon P_{n}), la mesure μ_{A} est une mesure de probabilité aléatoire sur R. Un résultat célèbre de Wigner précise le comportement asymptotique de cette mesure : elle converge vers une mesure déterministe dont la densité a la forme d’un demi-cercle. Plus précisément, si pour chaque dimension n, A^{(n)} est une matrice aléatoire distribuée selon P_{n}, alors, presque sûrement, la suite de mesures empiriques (μ_{A^{(n)}}) converge étroitement vers la mesure μ_{c}, de support l’intervalle [−2, 2] et donnée par la densité

dμ_{c} := \frac{1}{2π} 1_{[−2,2]}\sqrt{4 − x^{2}}dx.

Ce résultat précise le comportement global du spectre de la matrice ; on dit qu’il s’agit du régime global. On ne peut rien en déduire sur le comportement asymptotique de la plus grande valeur propre de la matrice A. Néanmoins, le régime local aux extrémités du spectre est également connu (voir [Bai]) : presque sûrement, les valeurs propres extrêmes convergent vers le bord du support de la mesure-limite

lim_{n→∞} λ_{max}(A^{(n)}) = 2 et lim_{n→∞} λ_{min}(A^{(n)}) = −2.

Bien évidemment, grâce aux symétries de la mesure P_{n}, il est complètement équivalent de travailler sur λ_{max} ou sur λ_{min}. Notons également que ces résultats de convergence presque sûrs sont valables dans un contexte beaucoup plus général que celui du GUE (voir par exemple [Bai]).

Un problème plus délicat est celui des fluctuations de la plus grande valeur propre autour de sa limite ; Tracy et Widom ([TW1]) ont montré que l’ordre de grandeur de ces fluctuations est de n^{−2/3}, ce qui peut paraître surprenant car très différent de la situation « habituelle », comme dans le théorème central limite, où les fluctuations sont en n^{−1/2}. Plus précisément, Tracy et Widom ont montré la convergence en distribution

lim_{n→∞} n^{2/3}(λ_{max}(A^{(n)}) − 2) → T W.

où la variable aléatoire T W est distribuée selon une loi de probabilité explicite, mais dont la description demeure compliquée (on trouvera plus de détails dans la partie 1.2.3). Cette même distribution-limite apparaît aussi dans le calcul des fluctuations pour d’autres quantités : par exemple pour la plus grande sous-suite croissante d’une permutation aléatoire des n premiers entiers (voir [Led3] pour plus de précisions, et d’autres exemples où cette loi-limite apparaît). La queue (positive) de la distribution T W vérifie l’encadrement

∀x ⩾ 0, c′ exp(−C′x^{3/2}) ⩽ P(T W ⩾ x) ⩽ c exp(−Cx^{3/2}).

Cette estimation peut être déduite à partir d’une description de la loi T W en termes de fonctions de Painlevé obtenue dans [TW1] ; cependant la preuve de cette description est délicate. Dans la partie 1.2.5, nous donnons une preuve à l’aide de la représentation déterminantale, qui est un outil plus standard.

En analyse géométrique asymptotique, il est important de disposer d’inégalités valides en toute dimension, plutôt que de résultats-limites dont l’utilité pratique est souvent limitée. On aimerait ainsi une borne supérieure pour la probabilité

P(λ_{max}(A^{(n)}) ⩾ 2 + ε),

qui reflète le comportement découvert par Tracy et Widom. De telles inégalités de déviations peuvent parfois être démontrées par des principes généraux de concentration (voir [Led1]). L’inégalité de concentration gaussienne est valable pour n’importe quelle fonction lipschitzienne d’un vecteur gaussien dans R^{N}. En identifiant B_{sa}(C^{n}) à R^{n^{2}}, la plus grande valeur propre entre dans ce cadre. Comme par ailleurs l’inégalité Eλ_{max}(A^{(n)}) ⩽ 2 est connue (voir [Sza]), cela donne

∀ε > 0, P(λ_{max}(A^{(n)}) ⩾ 2 + ε) ⩽ exp(−nε^{2}/2).  (1.1)

Cette inégalité est valable en toute dimension ; cependant elle n’est pas asymptotiquement optimale pour des petites valeurs de ε. Prenons par exemple ε = tn^{−2/3} pour t fixé. Lorsque la dimension n tend vers l’infini, le membre de gauche de (1.1) tend vers une limite l ∈]0, 1[, tandis que le membre de droite tend vers 1 ; et pour t petit on a l ≪ 1. De fait, l’inégalité (1.1) est une inégalité de grandes déviations. Il est en fait possible de quantifier le théorème de Tracy–Widom et nous obtenons ainsi le résultat suivant, qui est exact pour le régime des petites déviations

Proposition 1.1 : Il existe des constantes universelles C et c telles que pour tout t ⩾ 0 et tout entier n, on ait

P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + t) ⩽ C exp(−cnt^{3/2}).

Comme ∥A∥ = max(λ_{max}(A), −λ_{min}(A)), on a aussi une inégalité similaire pour la norme de A^{(n)}. Notons que le même résultat a été obtenu indépendamment par M. Ledoux ([Led2]), par une approche différente. Le plan de notre preuve est simple : suivre pas à pas la preuve de Tracy et Widom en prenant soin à chaque étape de contrôler les différentes quantités impliquées de manière uniforme. Cela nécessite en particulier d’utiliser certaines estimations sur des fonctions spéciales. La preuve du résultat est présentée dans la section suivante, où les outils nécessaires sont également introduits. Nous obtenons en réalité un résultat formellement plus fort que la proposition 1.1 : la convergence n^{2/3}(λ_{max}(A^{(n)}) − 2) → T W a lieu au sens d’une distance de Wasserstein sur R associée à un coût adapté au problème ; nous renvoyons à la section 1.2.1 pour plus de détails.

1.2 A sharp small deviation inequality for the largest eigenvalue of a random matrix

We prove that the convergence of the largest eigenvalue λ_{1} of a n×n random matrix from the Gaussian Unitary Ensemble to its Tracy–Widom limit holds in a strong sense, specifically with respect to an appropriate Wasserstein-like distance. This unifying approach allows us both to recover the limiting behavior and to derive the inequality P(λ_{1} ⩾ 2 + t) ⩽ C exp(−cnt^{3/2}), valid uniformly for all n and t. This inequality is sharp for “small deviations” and complements the usual “large deviation” inequality obtained from the Gaussian concentration principle. Following the approach by Tracy and Widom, the proof analyses several integral operators, which converge in the appropriate sense to an operator whose determinant can be estimated.

Introduction

Let H_{n} be the set of n-dimensional (complex) Hermitian matrices. The general element of H_{n} is denoted A^{(n)}, and its entries are denoted (a_{ij}^{(n)}).

We exclusively focus on the Gaussian Unitary Ensemble GUE, which can be defined by the data of a probability measure P_{n} on H_{n} which fulfills the following conditions

1. The n^{2} random variables (a_{ii}^{(n)}), (ℜa_{ij}^{(n)})_{i<j}, (ℑa_{ij}^{(n)})_{i<j} are independent,

2. ∀i, a_{ii}^{(n)} follows the Gaussian law N(0, 1/n),

3. ∀i < j, ℜa_{ij}^{(n)} and ℑa_{ij}^{(n)} follow the Gaussian law N(0, 1/2n).

The measure P_{n} is uniquely determined by these three conditions because of the extra symmetry constraint a_{ij} = \overline{a_{ji}} ; it can also be made explicit. H_{n} is a vector space on which the scalar product ⟨u, v⟩ := tr(uv) induces an Euclidean structure, hence a Lebesgue measure. The probability measure P_{n} has a density with respect to this Lebesgue measure, which can be shown to equal

dP_{n} := \frac{1}{c_{n}} exp(−\frac{n}{2}trM^{2})dM,

where c_{n} is a normalization constant.

The GUE has the wonderful property of invariance under rotation : indeed the measure P_{n} is invariant under the conjugation action of the unitary group. This makes calculations easier and is very useful for the study of eigenvalues, which are also invariant under the same action.

From now on, “random matrix” means “element of (H_{n}, P_{n})” seen as a probability space. Let (Ω, P) denote the product of all these probability spaces ∏_{i=n}^{∞}(H_{n}, P_{n}) ; an element of Ω is a sequence of random matrices, the nth matrix being of size n. However, for all the questions we shall consider, the relationships between the H_{n}’s for different n’s are immaterial.

For more background, we refer the reader to the monograph [Meh]. Let λ_{1}(A^{(n)}) ⩾ λ_{2}(A^{(n)}) ⩾ ⋯ ⩾ λ_{n}(A^{(n)}) be the ordered eigenvalues of a random matrix A^{(n)}. The global asymptotic behavior of these eigenvalues is wellknown. The most famous result in this topic is the semi-circle law, which can be stated as follows : let N(A^{(n)}) be the probability measure on ℝ derived from the random matrix A^{(n)} in the following way (δ_{x} denotes the Dirac mass at point x)

N(A^{(n)}) := ∑_{k=1}^{n} δ_{λ_{k}(A^{(n)})}.

Then, P-almost surely, the sequence of probabilities (N(A^{(n)})) converges weakly to a deterministic measure μ_{c}, with a density with respect to Lebesgue measure given by

dμ_{c} := \frac{1}{2π} 1_{[−2,2]}\sqrt{4 − x^{2}}dx.

We are interested here in the asymptotic behavior of the largest eigenvalue λ_{1}(A^{(n)}), which is a so-called local problem. Classical results (see e.g. [DS], also for precise references to the original articles) claim that

lim_{n→∞} λ_{1}(A^{(n)}) = 2 P-almost surely.

The asymptotic behavior of λ_{1}(A^{(n)}) was further clarified by Tracy and Widom, who proved the following result : there exists a continuous decreasing function ψ_{TW} from ℝ onto (0, 1) such that

lim_{n→∞} P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) = ψ_{TW}(x).  (1.2)

This function ψ_{TW} naturally arises as a determinant linked to the socalled “Airy kernel”, which will be defined later. The most difficult point of Tracy and Widom’s work was to show that this function ψ_{TW} can be written in terms of a Painlevé function (see [TW1]). From this point one can deduce the asymptotic behavior of ψ_{TW} around +∞ and find universal positive constants C, c, C′, c′ such that for x large enough

c′ exp(−C′x^{3/2}) ⩽ ψ_{TW}(x) ⩽ c exp(−Cx^{3/2}).  (1.3)

The remainder of this article is organized as follows : in section 1.2.1, we define an appropriate Wasserstein distance and state our main theorem which asserts that Tracy–Widom convergence holds in this strong distance. In section 1.2.2, we derive from this theorem the small deviation inequality and compare it with the classical one. Section 1.2.3 introduces the needed framework of determinantal kernels, which are classical in this field, and section 1.2.4 contains the proof of the main theorem. Finally, section 1.2.5 contains an alternative simple deviation of upper bounds (1.3) for Tracy– Widom distribution.

1.2.1 Convergence in terms of a Wasserstein distance

We call tail function of a measure μ on ℝ the function ψ_{μ} : ℝ → [0, 1] defined by ψ_{μ}(x) := μ((x, +∞)). Such a function is decreasing, left-continuous, tends to 1 at −∞ and to 0 at +∞. The tail function just equals 1 minus the cumulative distribution function. The function appearing in the r.h.s. of (1.2) is the tail function of the Tracy–Widom distribution on ℝ (we denote this distribution by T W).

We want to prove that the law of the rescaled largest eigenvalue tends to the Tracy–Widom law in a strong sense. As we only focus on the upper tail, we can consider truncated laws, supported on an interval [a, +∞) for some real a. Let Λ_{n}^{a} be the probability measure with tail function defined by

ψ_{Λ_{n}^{a}}(x) = \{ \begin{matrix}P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) & if x ⩾ a \\ 1 & if x < a \end{matrix} .

Similarly, let T W^{a} be the truncated Tracy–Widom law defined by

ψ_{_{TW}_{a}}(x) = \{ \begin{matrix}ψ_{TW}(x) & if x ⩾ a \\ 1 & if x < a \end{matrix} .

We are going to show that for any a, Λ_{n}^{a} tends to T W^{a} with respect to the distance defined through a mass transportation problem in its Monge– Kantorovich formulation (see [RR]).

A mass transportation problem is the question of optimizing the transshipment from a measure to another with respect to to a given cost. More precisely, let μ and ν be two probability measures on the same space X, and c : X × X → ℝ_{+} a symmetric function vanishing on the diagonal (c(x, y) represent the price to pay to transfer a unit of mass from x to y). Ways to carry μ onto ν are represented through probability measures π on the square space X × X having μ and ν as marginals (this means that for any measurable subset A of X, π(A × X) = μ(A) and π(X × A) = ν(A)). We denote by Π(μ, ν) the space of such π.

The Wasserstein distance associated with the problem is the “minimum cost to pay”, defined by

d(μ, ν) = inf_{π∈Π(μ,ν)} ∫_{X^{2}} c(x, y)dπ(x, y).

We are going to consider a very special case of this problem. Let us suppose that X = ℝ and that the cost c is defined as follows

c(x, y) := |∫_{x}^{y} w(t)dt| ,  (1.4)

where w is a positive function.

We can now state the main result of this note

Theorem 1.1. Let w(x) := exp(γx^{3/2}) and let d be the Wasserstein distance associated with the cost induced by w via the formula (1.4). Then, for any fixed a ∈ ℝ, if γ > 0 is small enough, Λ_{n}^{a} tends to T W^{a} for the distance d

lim_{n→∞} d(Λ_{n}^{a}, T W^{a}) = 0.

1.2.2 The small deviation inequality

The simplest idea to get concentration inequalities for the largest eigenvalue of a GUE random matrix is to use Gaussian concentration ; it is a straightforward consequence of the measure concentration phenomenon in the Gaussian space (see [DS]) that

∀t > 0, ∀n, P_{n}(λ_{1}(A^{(n)}) ⩾ M_{n} + t) < exp(−nt^{2}/2),  (1.5)

where M_{n} is the median of λ_{1}(A^{(n)}) with respect to the probability measure P_{n}. One has the same upper estimate is the median M_{n} is replaced by the expected value 𝔼_{n}λ_{1}(A^{(n)}).

The value of M_{n} can be controlled : for example we have M_{n} ⩽ 2+c/\sqrt{n}. This will be for example a consequence of our Proposition. Plugging this into the equation (1.5), we get the following result, where C is a universal constant

∀t > 0, ∀n, P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + t) < C exp(−nt^{2}/2).  (1.6)

It has been proved after the redaction of this note in [Sza] (Appendix F) that 𝔼_{n}λ_{1}(A^{(n)}) ⩽ 2. This was done using the Harer–Zagier recurrence formula for the expected moments of the empirical measure. Note that the situation for the GOE (Gaussian Orthogonal Ensemble), an ensemble of real symmetric matrices defined in a similar way as GUE (see [Meh] for a precise definition), is much simpler since we can use standard comparison techniques for (real) Gaussian vectors, such as Slepian’s lemma. The proof can be found in [DS], it is very similar to the ideas presented in Appendix 3.3.4 in a different context. Note also that since the function λ_{1} is convex, its median with respect to P_{n} does not exceed its expected value ([Kwa]). This implies that one can choose C = 1 in the inequality (1.6). There are similar though not as simple results for P_{n}(λ_{1}(A^{(n)}) ⩽ 2 − t), but in this paper we will concentrate on the “upper tail” estimates.

The result of Tracy and Widom (1.2) shows that the majoration (1.6) is not optimal for very small values of t. If for example t is equal to xn^{−2/3} for a fixed x, then the right-hand side in concentration inequality (1.6) tends to 1 when n grows to ∞, whereas the left-hand side tends to ψ_{TW}(x), which can be very small.

We would like to derive from our Theorem a deviation inequality which would improve the inequality (1.6) for small values of t. For this purpose, the uniform convergence in (1.2) (which, by Dini’s theorem, follows formally form the pointwise convergence) is not enough. But we will prove in this section that our Theorem implies the following Proposition :

Proposition 1.1. There exist positive universal constants C and c such that for every positive t and any integer n

P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + t) ⩽ C exp(−cnt^{3/2}).  (1.7)

Of course, by symmetry of the law P_{n}, similar results are true for the smallest eigenvalue λ_{n}(A^{(n)})

P_{n}(λ_{n}(A^{(n)}) ⩽ −2 − t) ⩽ C exp(−cnt^{3/2}).  (1.8)

Using the fact that for a Hermitian matrix A, the norm equals the maximum absolute value of an eigenvalue, we get a similar estimate for ||A^{(n)}||

P_{n}(||A^{(n)}|| ⩾ 2 + t) ⩽ C exp(−cnt^{3/2}).  (1.9)

We need the following lemma to prove the proposition, which will help us to explicitly compute Wasserstein distance

Lemma 3. Suppose that the measures μ and ν are defined on ℝ, and that the cost c is defined by an integral, as in (1.4). If μ and ν are regular enough, for example if ψ_{μ} and ψ_{ν} are piecewise C^{1}, then the Wasserstein distance for the cost c equals

d(μ, ν) = ∫_{−∞}^{∞} w(t)|ψ_{μ}(t) − ψ_{ν}(t)|dx.  (1.10)

Proof. In fact, this transportation problem is explicitly solvable. For a onedimensional problem with a cost satisfying the Monge condition (which is always the case when the cost is defined using an integral as in (1.4)), the optimal transshipment is achieved through the map T defined as follows (see [RR], chapter 3.1)

∫_{−∞}^{x} dμ = ∫_{−∞}^{T (x)} dν.

Thus, we can compute the value of d(μ, ν)

d(μ, ν) = ∫_{0}^{1} c(ψ_{μ}^{−1}(u), ψ_{ν}^{−1}(u))du.

Let us consider first the particular case when ψ_{μ} ⩽ ψ_{ν}. This allows us to drop the absolute values in the definition of c (see (1.4)) and unfold the calculations. Using the appropriate changes of variables, we come to the equality (1.10).

For general μ and ν, define μ ∧ ν and μ ∨ ν using their tail functions

ψ_{μ∧ν}(x) = min(ψ_{μ}(x), ψ_{ν}(x)) and ψ_{μ∨ν}(x) = max(ψ_{μ}(x), ψ_{ν}(x)).

We easily check that ψ_{μ∧ν} ⩽ ψ_{μ∨ν}, d(ψ_{μ}, ψ_{ν}) = d(ψ_{μ∧ν}, ψ_{μ∨ν}) and that the value of the r.h.s. of (1.10) does not change if we replace ψ_{μ} and ψ_{ν} by ψ_{μ∧ν} and ψ_{μ∨ν}. This yields the conclusion for the general case.

Using this lemma, we get from our theorem (with a = 0), using the upper bound (1.3) for ψ_{TW}, the uniform estimate

∫_{0}^{∞} w(x)P_{n}(λ_{1}(A^{(n)}) ⩾ 2 + xn^{−2/3}) dx ⩽ C,

which implies immediately for x ⩾ 1 (keep in mind that ψ_{n} is decreasing)

ψ_{n}(x) ⩽ C exp(−γ(x − 1)^{3/2}) ⩽ C′ exp(−γ′x^{3/2}).  (1.11)

This is, up to the rescaling t = xn^{−2/3}, the content of the proposition.

Now we can also easily show that our theorem implies the Tracy–Widom limit (1.2) : using the uniform bound (1.11) and Lebesgue’s convergence theorem, we get from the Theorem that ψ_{TW} is the pointwise limit of the ψ_{n}’s on [a, +∞), and thus on the whole real line if we let a go to −∞.

It should be emphasized that recently (independently from and slightly preceding this work), this small deviations result has been proved by Ledoux in [Led2] using an argument based on the Harer–Zagier recurrence formula (see [HT] for a simple proof of this formula). The same paper by Ledoux contains another proof based on hypercontractivity which gives the result up to a polynomial factor ; this method works also for the Laguerre Unitary Ensemble (see [Led2] for the definition). However, the existence of a Tracy– Widom limit does not follow from this approach. More generally, many contributions to this and related topics either address the limit behavior or provide dimension-free bounds, rarely combining the two. Our technique captures both phenomena in a single “stroke”.

1.2.3 Relation to determinants

The remainder of this note is devoted to the proof of the main theorem. For simplicity, we will prove only the case a = 0, and drop all the superscripts. The proof for a general a requires only routine modifications.

We are first going to express all involved quantities in terms of determinants of certain operators. This is quite classical work due to Gaudin and Mehta (see [Meh]). Part of the calculations done here are present, at least implicitly, in the paper by Tracy and Widom ([TW1]).

We need new notation. Let (H_{n}) be the Hermite polynomials, which are defined by

H_{n}(t) := (−1)^{n} exp(t^{2})(\frac{d}{dt})^{n} exp(−t^{2}).

They are orthogonal for the measure on ℝ of density exp(−x^{2}) with respect to Lebesgue measure. Then we note

ϕ_{n}(t) := \frac{1}{\sqrt{d_{n}}} H_{n}(t) exp(−t^{2}/2),  (1.12)

where d_{n} := ∫_{ℝ} H_{n}(x)^{2}dx = 2^{n}n!\sqrt{π}. The family (ϕ_{n}) is therefore orthonormal in L^{2}(ℝ). We introduce

k_{n}(x, y) := ∑_{j=0}^{n−1} ϕ_{j}(x)ϕ_{j}(y).

We can associate to k_{n} an integral operator K_{n} acting on the Hilbert space L^{2}(ℝ) in the following way

(K_{n}f)(x) := ∫_{ℝ} k_{n}(x, y)f(y)dy.  (1.13)

This operator K_{n} is nothing but the orthogonal projection in L^{2}(ℝ) onto the subspace spanned by (ϕ_{j})_{1⩽j⩽n}.

This is a very general setting : if we have a measure space (X, μ) and a “kernel” k ∈ L^{2}(X × X), we can define an operator K on L^{2}(X) using a formula similar to (1.13). From now on, all kernels are assumed to belong to L^{2}(X × X) and are denoted by small letters ; associated integral operators are denoted by the corresponding capital letter.

It is straightforward to prove that Hilbert–Schmidt operators on L^{2}(X) are exactly integral operators with a L^{2} kernel. Moreover, the Hilbert– Schmidt norm of the operator and the L^{2} norm of the kernel coincide. This fact is proved in [GG], which is a good reference for a reader who wants more detail on integral operators. Let us just quote the formula for compositions of operators : if k and l are two kernels on the same space (X, μ), then the operator KL is an integral operator with kernel :

(kl)(x, y) = ∫_{X} k(x, z)l(z, y)dμ(z).  (1.14)

The tail function of λ_{1}(A^{(n)}) can now be expressed using the kernel k_{n}. The key formula is the following (see [Meh])

∀t ∈ ℝ, P_{n} (\begin{matrix}√ & \overline{n} \\ √ & \overline{2} \end{matrix}λ_{1}(A^{(n)}) ⩽ t) = det_{[t,∞)}(Id − K_{n}).  (1.15)

In the formula (1.15), the right-hand side must be understood as the determinant of the operator K_{n} acting on the space L^{2}([t, ∞)) (or equivalently of the operator with kernel equal to is the restriction of k_{n} to [t, ∞)^{2}). This restricted operator is denoted K_{n}^{[t]}.

It may not be immediately obvious how to define such a determinant, as the operator involved acts on an infinite-dimensional space. However, the operator K_{n} that we consider here has a finite rank, hence we can define its determinant as if it were acting on a finite-dimensional space.

A problem will arise when we want to consider limits of such operators, which might fail to have a finite rank. Fortunately, a whole theory of determinants (and traces) of integral operators exists (so-called “Fredholm” determinants). In fact, there are several possible ways to extend these concepts to the infinite-dimensional case. We will focus on a more algebraic approach, due to Grothendieck (see [GGK] or [Sim] for a complete exposition), which defines determinants of a nuclear (= trace class) perturbation of identity in terms of traces of its exterior powers (here N is a nuclear operator, for which trace is well-defined).

det(Id + N) := 1 + ∑_{k=1}^{∞} tr(Λ^{k}(N)).

Of course, this definition coincides with the usual one in the finite-dimen-sional case.

The presence of the factor \sqrt{n}/\sqrt{2} in equation (1.15) requires an explanation. It arose because there are several normalizations possible. We chose to define the GUE so that the first eigenvalue is about 2, while other authors, as Tracy and Widom in [TW1], prefer to locate it around \sqrt{2n} (there are still other normalizations but an exhaustive list would be too long). As we kept their notation for the kernels k_{n}, a scaling factor will appear when we pass from a normalization to the other one.

To get a nontrivial limit, we must replace the t in formula (1.15) by the following rescaling, as for the Tracy–Widom limit (1.2)

t = τ_{n}(x) := \begin{matrix}√ & \overline{n} \\ √ & \overline{2} \end{matrix}(2 + \frac{x}{n^{2/3}} ).

Let also k̃_{n} be the rescaled kernel

k̃_{n}(x, y) := \frac{1}{\sqrt{2}n^{1/6}} k_{n}(τ_{n}(x), τ_{n}(y)).

We can see using a change of variable that K̃_{n}^{[x]} and K_{n}^{[τ_{n}(x)]} have the same eigenvalues. More precisely, if f is a eigenfunction of K̃_{n}^{[x]}, then f ∘ τ_{n}^{−1} is a eigenfunction of K_{n}^{[τ_{n}(x)]}, with the same eigenvalue.

Plugging these renormalizations into the formula (1.15), we obtain

P_{n}(λ_{1}(A^{(n)}) ⩽ 2 + xn^{−2/3}) = det_{[x,+∞)}(Id − K̃_{n}).  (1.16)

Using the previous definition for the tail function ψ_{n}, we can write for a positive s

ψ_{n}(s) = 1 − det(Id − K̃_{n}^{[s]}).

The following result was known before Tracy and Widom’s work (see for example [For])

lim_{n→∞} k̃_{n}(x, y) = k(x, y),  (1.17)

uniformly on compact subsets in x and y.

Here k is the kernel, often called Airy kernel, defined by

k(x, y) := \frac{Ai(x)Ai′(y) − Ai′(x)Ai(y)}{x − y}.  (1.18)

The kernel k is extended by continuity to the diagonal. The function Ai is called the Airy function. It is very useful in physics and can be defined by several means. One of them is the following integral representation

Ai(z) := \frac{1}{2π} ∫_{−∞}^{∞} exp(i(zt + t^{3}/3))dt.

It can also be written as a combination of Bessel functions. It satisfies the Airy ODE

\frac{∂^{2}}{∂x^{2}} y(x) = xy(x).  (1.19)

The asymptotic behavior of Ai is well-known, for example [Sze] contains the following formula, valid when x tends to +∞

Ai(x) ∼ \frac{1}{2}3^{−1/4}\sqrt{π}x^{−1/4} exp(−\frac{2}{3^{3/2}} x^{3/2}).  (1.20)

The function ψ_{TW} can be defined using this Airy kernel

ψ_{TW}(x) := 1 − det(Id − K^{[x]}).  (1.21)

In [TW1] Tracy and Widom found another expression for ψ_{TW}. Let q be the solution of the Painlevé II ODE

\frac{∂^{2}}{∂x^{2}} q(x) = xq(x) + 2q(x)^{3},

which is determined by the asymptotics q(x) ∼ Ai(x) for x close to +∞. Then we have the representation

ψ_{TW}(x) = 1 − exp(− ∫_{x}^{∞}(t − x)q(t)^{2}dt).  (1.22)

It is easy to get from (1.20) and (1.22) the bounds (1.3) for the asymptotic behavior of ψ_{TW}. However, as we do not really need all the depth of Tracy and Widom’s results and connections to Painlevé functions, we will reprove this fact in a more elementary way at the end of this note.

1.2.4 Convergence of the operators

The convergence in (1.17) as determined in the existing literature is rather weak ; in particular, it does not imply convergence of the associated integral operators in the Hilbert–Schmidt norm or even in the operator norm on L^{2}. In particular, we are not a priori allowed to exchange limit and determinant in (1.16) when n tends to infinity.

Our main step will be to show that K̃_{n} tends to K with respect to the nuclear (trace class) norm. To that end we need several lemmas.

Lemma 4. The following equality holds

(\frac{∂}{∂x} + \frac{∂}{∂y} ) k_{n}(x, y) = −\sqrt{\frac{n}{2}} (ϕ_{n}(x)ϕ_{n−1}(y) + ϕ_{n−1}(x)ϕ_{n}(y)) .

Proof. We start with the Christoffel–Darboux formula (see [Sze])

k_{n}(x, y) = \sqrt{\frac{n}{2}} \frac{ϕ_{n}(x)ϕ_{n−1}(y) − ϕ_{n−1}(x)ϕ_{n}(y)}{x − y}.

Then we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to each term. We use the formula (1.12) and the following identities (those which are not obvious are shown in [Sze])

ϕ′_{n}(x) = −\frac{exp(−x^{2}/2)}{\sqrt{d_{n}}}(H′_{n}(x) − xH_{n}(x)).

H′_{n−1}(x) = 2xH_{n−1}(x) − H_{n}(x).
H′_{n}(x) = 2nH_{n−1}(x).

We obtain exactly the expected result.

Lemma 5. The following integral representation holds

k̃_{n}(x, y) = \frac{n^{1/6}}{2\sqrt{2}} ∫_{0}^{∞} ϕ_{n}(τ_{n}(x + z))ϕ_{n−1}(τ_{n}(y + z))  (1.23)
+ ϕ_{n−1}(τ_{n}(x + z))ϕ_{n}(τ_{n}(y + z))dz.

Proof. If we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to the right-hand side of (1.23) (there is no trouble with interchanging the operations “ \frac{∂}{∂x} + \frac{∂}{∂y}” and “∫_{0}^{∞}” since all the functions involved are Schwartz functions), we get after standard calculations

\frac{n^{1/6}}{2\sqrt{2}}(ϕ_{n}(τ_{n}(x))ϕ_{n−1}(τ_{n}(y)) + ϕ_{n−1}(τ_{n}(x))ϕ_{n}(τ_{n}(y))).

Lemma 4 asserts that we obtain exactly the same expression when we apply the operator \frac{∂}{∂x} + \frac{∂}{∂y} to the left member of (1.23). Thus, the two members of the equation are equal modulo a function (say, α) which only depends on x−y. But both members tend to zero when x et y tend to infinity in an independent way. Therefore the function α has to vanish identically and the lemma is proved.

Let us introduce extra notation. The following kernels are defined on [s, +∞)^{2}, where s is any positive number

a_{n}^{[s]}(x, y) := \frac{n^{1/12}}{2^{1/4}} ϕ_{n}(τ_{n}(x + y − s)).

b_{n}^{[s]}(x, y) := \frac{n^{1/12}}{2^{1/4}} ϕ_{n−1}(τ_{n}(x + y − s)).

a^{[s]}(x, y) := Ai(x + y − s).

The equality (1.23) can be translated in terms of operators (this is just a consequence of the formula (1.14) for the composition of kernels)

K̃_{n}^{[s]} = \frac{1}{2}(A_{n}^{[s]}B_{n}^{[s]} + B_{n}^{[s]}A_{n}^{[s]}).  (1.24)

A similar equality for the operator K is proved (exactly in the same way) in [TW1]

K^{[s]} = (A^{[s]})^{2}.  (1.25)

We shall subsequently show that (for a fixed s) the operators A_{n}^{[s]} and B_{n}^{[s]} tend to A^{[s]} with respect to the Hilbert–Schmidt norm. To that end, we need estimates for ϕ_{n} contained in two lemmas that follow.

Lemma 6. The functions ϕ_{n}, after rescaling, converge to Ai, uniformly on compact subsets in y :

ϕ_{n}(τ_{n}(y))2^{−1/4}n^{1/12} → Ai(y) and ϕ_{n−1}(τ_{n}(y))2^{−1/4}n^{1/12} → Ai(y). (1.26)

Proof. This is an immediate consequence of the following asymptotic formulae for Hermite polynomials due to Plancherel and Rotach. They can be found, in a slightly different presentation, in the book by Szegö ([Sze])

If x = \sqrt{2n + 1} + \frac{y}{\sqrt{2}n^{1/6}} , then ϕ_{n}(x) = 2^{1/4}n^{−1/12}(Ai(y) + O(n^{−3/4})).

The O holds when n tends to +∞, uniformly in y on compact subsets.

Lemma 7. We have a bound for ϕ_{n} which is uniform in n : there exists a positive constant c such that for any y > 0 and any integer n

\{ \begin{matrix}n^{1/12}ϕ_{n}(τ_{n}(y)) ⩽ C exp(−cy^{3/2}) \\ n^{1/12}ϕ_{n}(τ_{n−1}(y)) ⩽ C exp(−cy^{3/2}) \end{matrix} .  (1.27)

Proof. Let us sketch a proof of the first inequality in (1.27). We will use the following result, which is an exercise at page 403 in [Olv]. It is valid for x ⩾ 1

H_{n}(νx) ⩽ 1.13\sqrt{2π} exp(−ν^{2}/4)ν^{(3ν^{2}−1)/6} exp(ν^{2}x^{2}/2) (\frac{ζ}{x^{2} − 1})^{1/4} Ai(ν^{4/3}ζ).

where ν := \sqrt{2n + 1} and

ζ := (\frac{3}{4}x\sqrt{x^{2} − 1} − \frac{3}{4}Argchx)^{2/3} .

Using the definition of ϕ_{n} given in formula (1.12) and Stirling’s formula to estimate d_{n}, we obtain

n^{1/12}ϕ_{n}(νx) ⩽ C (\frac{ζ}{x^{2} − 1})^{1/4} Ai(ν^{4/3}ζ).

We deduce from (1.20) a bound for Ai, and we also use the inequality ζ ⩾ c(x − 1) to get

n^{1/12}ϕ_{n}(\sqrt{2n + 1}x) ⩽ Cn^{−1/6} \frac{1}{(x − 1)^{1/4}} exp(−c(2n + 1)(x − 1)^{3/2}). (1.28)

We now return to our notation through the change of variable

\sqrt{2n + 1} x = τ_{n}(y).

We can estimate x in the following way

x ⩾ 1 − \frac{c}{n} + \frac{y}{\sqrt{2}n^{1/6}\sqrt{2n + 1}}.

For y large enough, we even have

x ⩾ 1 + c\frac{y}{n^{2/3}} .  (1.29)

Combining (1.28) and (1.29) yields

n^{1/12}ϕ_{n}(τ_{n}(y)) ⩽ C \frac{1}{y^{1/4}} exp(−cy^{3/2}).

The factor y^{−1/4} can be deleted if c is made small enough. This inequality is only true for y large enough, but we keep in mind that convergence in (1.26) was uniform on compact subsets, so we can extend it to all positive y, and the inequality is proved. The same scheme of demonstration works for the second inequality, with τ_{n−1} instead of τ_{n}.

We are now ready to prove our main theorem

Proof. We denote by ||.||_{HS} the Hilbert–Schmidt norm and by ν the nuclear norm.

We are first going to estimate the quantity |ψ_{n}(s) − ψ_{TW}(s)| = | det(Id − K̃_{n}^{[s]})−det(Id−K^{[s]})|. To reach this goal, we will use the following majoration (see [GGK]), valid for any two nuclear operators A and B

| det(Id + A) − det(Id + B)| ⩽ ν(A − B)E^{1+ν(A)+ν(B)}.  (1.30)

It will be useful to notice that lemma 7 implies in particular the following remark : there is a positive C such that for any s ⩾ 0 and any integer n, all the quantities ||A_{n}^{[s]}||_{HS}, ||B_{n}^{[s]}||_{HS} and ||A^{[s]}||_{HS} are bounded by C (remember that the Hilbert–Schmidt norm is just the L^{2}-norm of the kernel). Using inequalities (1.24), (1.25) and the non-commutative Hölder inequality, we get that ν(K^{[s]}) and ν(K̃_{n}^{[s]}) are also bounded by the constant. Hence we can drop the exponential factor in formula (1.30)

|ψ_{n}(s) − ψ_{TW}(s)| ⩽ Cν(K̃_{n}^{[s]} − K^{[s]}).

We need to estimate the quantity ν(K̃_{n}^{[s]} − K^{[s]}). The key to do this is to use the equalities (1.24) et (1.25) to get

K̃_{n}^{[s]} − K^{[s]} = \frac{1}{4}((A_{n}^{[s]} − A^{[s]})(B_{n}^{[s]} + A^{[s]}) + (A_{n}^{[s]} + A^{[s]})(B_{n}^{[s]} − A^{[s]})
+ (B_{n}^{[s]} + A^{[s]})(A_{n}^{[s]} − A^{[s]}) + (B_{n}^{[s]} − A^{[s]})(A_{n}^{[s]} + A^{[s]})).

The non-commutative Hölder inequality yields

ν(K̃_{n}^{[s]} − K^{[s]}) ⩽ \frac{1}{2}||A_{n}^{[s]} − A^{[s]}||_{HS}||B_{n}^{[s]} + A^{[s]}||_{HS}  (1.31)
+ \frac{1}{2}||A_{n}^{[s]} + A^{[s]}||_{HS}||B_{n}^{[s]} − A^{[s]}||_{HS}.

The factors with a “+” are easy to get rid of : we can use the triangle inequality to write ||A_{n}^{[s]} +A^{[s]}||_{HS} ⩽ ||A_{n}^{[s]}||_{HS} +||A^{[s]}||_{HS}, which is uniformly bounded according to the remark following formula (1.30). We obtain

ν(K̃_{n}^{[s]} − K^{[s]}) ⩽ C(||A_{n}^{[s]} − A^{[s]}||_{HS} + ||B_{n}^{[s]} − A^{[s]}||_{HS}).

We can now calculate the Wasserstein distance from Λ_{n} to T W, using the expression given by lemma 3

d(Λ_{n}, T W) = ∫_{0}^{∞} exp(γs^{3/2})|ψ_{n}(s) − ψ_{TW}(s)|ds
⩽ C ∫_{0}^{∞} exp(γs^{3/2})(||A_{n}^{[s]} − A^{[s]}||_{HS} + ||B_{n}^{[s]} − A^{[s]}||_{HS})ds.

First deal with the term ||A_{n}^{[s]} − A^{[s]}||_{HS}. Using the definition of A_{n}^{[s]} and A^{[s]} we get

∫_{0}^{∞} exp(γs^{3/2})||A_{n}^{[s]} − A^{[s]}||_{HS}ds  (1.32)

= \sqrt{2} ∫_{0}^{∞} exp(γs^{3/2}) (∫_{0}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ds.

Fix an ε > 0 and use the uniform bound of lemma 7 : we get that for γ small enough, S large enough and any n

\sqrt{2} ∫_{S}^{∞} exp(γs^{3/2}) (∫_{0}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ds ⩽ ε.

Similarly, for Z large enough, any s smaller than S and any n

(∫_{Z}^{∞} z ((\frac{n^{1/12}}{2^{1/4}} ϕ_{n} ∘ τ_{n} − Ai)(z + s))^{2} dz)^{1/2} ⩽ \frac{ε}{\sqrt{2}S exp(S^{3/2})}.

Now we can split the integral in (1.32) into three terms to get (remember than convergence in lemma 6 was uniform on compact subsets)

∫_{0}^{∞} exp(γs^{3/2})||A_{n}^{[s]} − A^{[s]}||_{HS}ds ⩽ 3ε for n large enough.

We can write a similar estimate with B_{n} instead of A_{n}. We finally deduce that, for n large enough, d(Λ_{n}, T W) ⩽ 6Cε. Hence Λ_{n} tends to T W in the Wasserstein sense. This is the announced result.

1.2.5 An elementary proof of asymptotics for ψ_{TW}

To prove our theorem, we needed the upper asymptotics (1.3) for ψ_{TW}. It is possible to derive them from the representation (1.22) : keeping in mind that q ∼ Ai, we get from (1.20)

∫_{x}^{∞}(t − x)q^{2}(t)dt ⩽ C exp(−cx^{3/2}).

Hence, (1.22) yields

ψ_{TW}(x) ⩽ 1 − exp(−C exp(−cx^{3/2})) ⩽ C′ exp(−cx^{3/2}).

However, for sake of completeness, we are going to derive in this section this last result in a more elementary way, i.e. without using the Painlevé representation. To do this, we need some facts about integral operators. Of course, a general integral operator can fail to be nuclear (for example, any Hilbert–Schmidt operator from L^{2}(X) into itself can be written as an integral operator). Nevertheless, there exist several “nuclearity tests”, criteria ensuring that under some conditions, kernels generate nuclear operators ([GG],[GGK]). The main result in this topic is Mercer’s theorem, which enables us to expand a continuous self-adjoint kernel (i.e. the associated operator is self-adjoint) as a series of eigenfunctions of the operator. Unfortunately, these results are usually stated when dealing with a compact space of finite measure, and we have to consider half-infinite intervals [s, +∞). However, the standard proofs work also in this setting with only slight modifications.

A result which fits the present context is the following

Lemma 8. Let X = [s, +∞), equipped with the Lebesgue measure, and k be a kernel on X × X which satisfies the following conditions

1. k ∈ L^{2}(X × X), 2. k is jointly continuous,

3. K is positive self-adjoint as an operator on L^{2}(X),

4. There exists a continuous positive function ϱ in L^{2}(X) such that

|k(x, y)| ⩽ ϱ(x)ϱ(y)

for every x, y in X.

Then the operator K is nuclear and the trace formula holds

tr(K) = ∫_{s}^{∞} k(x, x)dx.  (1.33)

Proof. We are going to derive our result from the classical finite-measure case using a change of density trick. Let μ be the measure on X with density ϱ^{2} with respect to Lebesgue measure ; we have μ(X) < ∞. If we (isometrically) identify L^{2}(X, dx) with L^{2}(X, μ) sending f to f/ϱ, the integral operator K viewed from L^{2}(X, μ) into itself has kernel k(x, y)/ϱ(x)ϱ(y). To get the result we simply apply to the new kernel the following version of Mercer’s theorem (it can proved adapting straightforward the classical proof from [Smi]) : if μ is a finite Borel measure on X and k a continuous bounded positive selfadjoint kernel, then the associated operator K is nuclear and its trace is equal to the integral of the kernel along the diagonal.

Lemma 9. The following estimation holds

∃C, c > 0, ∀s > 0, ψ_{TW}(s) ⩽ C exp(−cs^{3/2}).

Proof. By definition (see [Sim]), we have

ψ_{TW}(s) = ∑_{k=1}^{∞}(−1)^{k−1}tr(Λ^{k}(K^{[s]})).

Using the fact that tr(Λ^{k}(K^{[s]})) ⩽ tr(K^{[s]})^{k}/k!, we get

|ψ_{TW}(s)| ⩽ exp(trK^{[s]}) − 1.

Actually, formula (1.21) shows that ψ_{T W} is positive since we have 0 ⩽ K^{[s]} ⩽ 1. In the end, the convexity of the exponential function on [0, trK^{[0]}] yields for s ⩾ 0

ψ_{T W} (s) ⩽ CtrK^{[s]}.

It is not hard to check that the kernel k^{[s]} satisfies the hypotheses of lemma 8 ; to check condition 4 we can cook up a function ϱ using Ai and its derivative.

Thus we can rewrite the trace of K^{[s]} as an integral

ψ_{T W} (s) ⩽ C ∫_{s}^{∞} ((Ai′(x))^{2} − xAi(x)) dx.  (1.34)

The value of K on the diagonal comes from (1.18) and the Airy ODE (1.19).

Using (1.20), we can write

∃C, c > 0 ∀s ⩾ 0 Ai(s) ⩽ C exp(−cs^{3/2}).  (1.35)

A similar majoration holds for Ai′ : we only need to write Ai′(s) = ∫_{s}^{∞} Ai′′(x)dx and to use formulae (1.19) and (1.35)

∃C, c > 0 ∀s ⩾ 0 Ai′(s) ⩽ C exp(−cs^{3/2}).  (1.36)

The conclusion comes when combining formulae (1.34), (1.35) and (1.36).

Possible Generalizations

Of course, we expect the inequalities analogous to (1.7) to be true in a much more general setting. Basically, each time a Tracy–Widom-like behavior has been proved or is suspected, we can ask whether such an uniform estimate holds.

The most natural extension would be the setting of general Wigner matrices, for which universality of Tracy–Widom limit has been proved by Soshnikov ([Sos]). However, the bounds on moments he obtained are not enough to derive the small deviations inequality.

Tracy and Widom proved results similar to (1.2), involving a different limit law, for the matrix ensembles GOE and GSE (the real orthogonal and the symplectic cases) in [TW2].

Several authors investigated the behavior of the largest s-number (also called singular value) of a rectangular m×n matrix with independent entries, when the ratio m/n tends to a limit in (0, 1). The paper [Joh] contains an result analogous to (1.2) for the Gaussian case (the so-called Wishart ensemble). There is strong numerical evidence indicating that a convergence on the scale n^{−2/3} as in Tracy–Widom behavior occurs also universally in this case, for the largest s-number, but also for the smallest one.

Another quantity of interest is the norm of a n × m random matrix when considered as a operator from ℓ_{p}^{n} to ℓ_{q}^{m}. Concentration results have been recently obtain in this case by Meckes (cf [Mec]).

In all these cases, we know concentration inequalities similar to (1.6), it would be interesting to prove the corresponding small deviation result.

Acknowledgements

I would like to express my sincere thanks and appreciation to my supervisor, Prof. Stanislaw J. Szarek, for our inspiring discussion and for his ongoing support. I would also like to thank Charles-Antoine Louët for his assiduous proofreading.

42 CHAPITRE 1. PETITES DÉVIATIONS

Chapitre 2

Échantillonnage de corps convexes : approximation de la matrice d’inertie

2.1 Introduction et présentation des résultats

2.1.1 Notations et position du problème

Dans tout ce chapitre, μ désigne une mesure de probabilité sur R^{n}, décroissement suffisamment vite à l’infini pour que nous n’ayons pas à nous préoccuper des problèmes de convergesce. Un cas particulier que nous considérerons est celui de la mesure uniforme sur un corps convexe K, notée μ_{K} et définie pour toute partie mesurable B de R^{n} par

μ_{K}(B) = \frac{vol(K ∩ B)}{vol(K)}.

Si μ est centrée, c’est-à-dire si elle vérifie ∫_{R^{n}} xdμ(x) = 0, sa matrice d’inertie A_{μ} est une matrice carrée symétrique, de taille n, définie par

(A_{μ})_{ij} = ∫_{R^{n}} x_{i}x_{j}dμ(x_{1}, …, x_{n}).

Alternativement, l’opérateur correspondant est

A_{μ} = ∫_{R^{n}} |x⟩⟨x|dμ(x).

Cette matrice est positive ; elle est définie positive si et seulement si le support de μ n’est pas contenu dans un hyperplan. Dans le cas où A_{μ} est la matrice identité, on dit que la mesure μ est isotrope. Un convexe K est dit isotrope si la mesure μ_{K} l’est.

Si μ est une mesure sur R^{n} et T : R^{n} → R^{n} est une application linéaire inversible, notons T_{∗}μ la mesure-image de μ par T, définie pour tout borélien B de R^{n} par

T_{∗}μ(B) = μ(T^{−1}B).

Dans le cas d’une mesure uniforme sur un convexe, on a la relation

T_{∗}μ_{K} = μ_{T K}.

Les matrices d’inertie de μ et de T_{∗}μ sont liées par l’égalité

A_{T_{∗}μ} = T A_{μ}T^{†}.  (2.1)

Par conséquent, dès lors que la matrice A_{μ} est inversible, il existe une transformation affine T telle que T_{∗}μ est isotrope.

On peut aussi définir l’ellipsoïde d’inertie d’une mesure μ comme étant l’unique ellipsoïde E tel que μ et μ_{E} aient la même matrice d’inertie. Cet ellipsoïde est connu en mécanique sous le nom d’ellipsoïde de Legendre (voir [MiPa1]).

Pour certaines applications, notamment algorithmiques (cf [KLS]), il est important de pouvoir déterminer la matrice d’inertie de μ à partir d’un petit nombre d’échantillons. Plus précisément, si (X_{i}) sont des vecteurs aléatoires indépendants et identiquement distribués de loi μ, l’approximation empirique de la mesure μ avec N échantillons est donnée par

μ_{N} = \frac{1}{N} ∑_{i=1}^{N} δ_{X_{i}}.

La suite de mesures (μ_{N}) est une approximation aléatoire de la mesure μ. Le théorème de Varadarajan ([Dud]), parfois appelé théorème fondamental de la statistique, nous dit que presque sûrement, la suite (μ_{N}) converge étroitement vers μ lorsque N tend vers +∞. Cependant, le nombre N d’échantillons nécessaires pour avoir une bonne approximation avec grande probabilité est en général exponentiel en la dimension (voir [GM] pour une question proche dans le cas d’un corps convexe). Si l’on cherche à n’approximer que la matrice d’inertie, ce nombre peut être choisi beaucoup plus petit. On sait que la suite (A_{μ_{N}}) converge vers A_{μ} presque sûrement et on cherche à quantifier cette convergence : étant donnée une tolérance ε > 0, quel nombre N d’échantillons faut-il prendre pour qu’avec grande probabilité

(1 − ε)A_{μ_{N}} ⩽ A_{μ} ⩽ (1 + ε)A_{μ_{N}}?  (2.2)

Lorsque l’on a (2.2), on dit que l’on a ε-approximation de la matrice d’inertie avec N échantillons.

Si μ est une mesure sur R^{n} et T : R^{n} → R^{n} est une application linéaire inversible, les matrices d’inertie empiriques de μ et T_{∗}μ vérifient

A_{(T_{∗}μ)_{N}} ∼^{ℒ} T A_{μ_{N}} T^{†}.  (2.3)

Par (2.1) et (2.3), on peut supposer que la mesure à échantillonner est isotrope, ce n’est nullement une restriction. Dans le cas d’une mesure isotrope, (2.2) s’écrit plus simplement

∥A_{μ_{N}} − Id∥_{op} ⩽ ε.  (2.4)

L’inégalité (2.4) est équivalente à

∀θ ∈ S^{n−1}, 1 − ε ⩽ |A_{μ_{N}} θ| ⩽ 1 + ε,

ou encore, comme A_{μ_{N}} = \frac{1}{N} ∑ |X_{i}⟩⟨X_{i}|, à

∀θ ∈ S^{n−1}, 1 − ε ⩽ \frac{1}{N} ∑_{i=1}^{N}⟨X_{i}, θ⟩^{2} ⩽ 1 + ε.

On peut par ailleurs construire des mesures sur R^{n} qui sont aussi mal approximables que l’on veut. Par exemple, si a est dans l’intervalle ]0, 1] et (e_{i}) est la base canonique de R^{n}, considérons la mesure μ̄_{a} définie par

μ̄_{a} = (1 − a)δ_{0} + \frac{a}{2n} ∑_{i=1}^{n} (δ_{\sqrt{\frac{n}{a}} e_{i}} + δ_{−\sqrt{\frac{n}{a}} e_{i}}) .  (2.5)

Cette mesure est bien isotrope. Si (X_{1}, …, X_{N}) sont indépendants et identiquement distribués de loi μ̄_{a}, alors avec probabilité (1 − a)^{N} les X_{i} sont tous nuls, et donc la matrice d’inertie empirique est la matrice nulle ! Pour a suffisamment petit, ces mesures sont donc très mal approximables par les mesures empiriques.

Le problème de savoir combien d’échantillons sont nécessaires pour obtenir l’ε-approximation de la matrice d’inertie d’un corps convexe avec grande probabilité a été posé pour la première fois dans [KLS]. Un certain nombre de résultats sur le sujet ont été obtenus depuis ; nous ne nous intéressons pas ici à la dépendance en ε.

Tout d’abord, Kannán, Lovász et Simonovits ont montré que N ⩾ C(ε)n^{2} échantillons garantissent l’ε-approximation avec probabilité supérieure à 1−ε. Bourgain ([Bou]) a ensuite amélioré la borne pour obtenir N ⩾ C(ε)n log^{3} n. Il a ensuite été montré par Giannopoulos et Milman ([GM]) qu’une petite modification de la preuve de Bourgain permettait d’obtenir N ⩾ C(ε)n log^{2} n. Ce même résultat a aussi été obtenu par Rudelson, qui a en fait montré l’inégalité générale suivante : si μ est une mesure isotrope et X un vecteur aléatoire de loi μ, alors

E∥A_{μ_{N}} − Id∥_{op} ⩽ C\sqrt{\frac{log n}{N}} (E|X|^{log N})^{1/ log N}  (2.6)

dès lors que le membre de droite est inférieur à 1. L’approche de Rudelson utilisait à l’origine le théorème des mesures majorantes de Fernique–Talagrand ; une preuve plus simple, basée sur les inégalités de Khintchine non commutatives de Lust-Piquard–Pisier, a ensuite été obtenue par Pisier. Pour utiliser l’inégalité (2.6), il est nécessaire de contrôler la quantité (E|X|^{log N})^{1/ log N}. Pour N ⩾ e^{2}, elle est toujours supérieure à (E|X|^{2})^{1/2}, qui vaut \sqrt{n} par la condition d’isotropie. Dans les meilleurs cas, on a aussi une inégalité inverse du type

(E|X|^{log N})^{1/ log N} ⩽ C\sqrt{n}.  (2.7)

C’est par exemple le cas pour les convexes inconditionnels (voir le lemme 11 ci-après), pour lesquels Giannopoulos, Hartzoulaki et Tsolomitis ont ainsi montré que N ⩾ C(ε)n log n échantillons suffisent à obtenir l’ε-approxima-tion de la matrice d’inertie avec probabilité supérieure à 1 − ε. Il est conjecturé (voir [Pao]) que l’on peut toujours obtenir une inégalité inverse du type (2.7), mais le résultat n’est connu que pour les convexes inconditionnels et les boules-unités des classes de Schatten (voir [BN1, GP]). Pour conclure dans le cas d’un convexe général, Rudelson utilise le lemme 10.3 ci-après qui fait intervenir un facteur logarithmique supplémentaire.

Ainsi, l’inégalité (2.6) est un outil puissant, mais qui ne permet pas d’espérer obtenir l’approximation de la matrice d’inertie avec moins de Cn log n échantillons. Il était d’ailleurs conjecturé (la conjecture apparaît explicitement dans [GHT]) que l’estimation N ⩾ C(ε)n log n est optimale pour un convexe général. Il est simple de voir que cette borne est optimale pour des exemples discrets. Considérons par exemple la mesure μ̄_{1} définie par (2.5), qui n’est autre que la mesure uniforme sur les sommets de la boule \sqrt{n}B_{1}^{n}, on obtient en utilisant (2.6) l’inégalité

E∥A_{(μ̄_{1})_{N}} − Aμ̄_{1}∥ ⩽ ε,

dès lors que N ⩾ Cn log n/ε^{2}. Mais si X est distribué selon μ̄_{1}, l’opérateur |X⟩⟨X| est la projection orthogonale sur une coordonnée aléatoire. Ainsi la matrice A_{(μ̄_{1})_{N}} est diagonale, et ses coefficients diagonaux sont distribués selon (p_{1}, …, p_{n}), où p_{i} est le nombre de boules que contient l’urne numéro i lorsque l’on place aléatoirement, uniformément et indépendamment N boules dans n urnes. Ce problème, connu sous le nom d’allocation aléatoire, a été longuement étudié ([KSC]), et il est nécessaire de prendre N ⩾ C(ε)n log n boules afin d’avoir

(1 − ε)N/n ⩽ min(p_{i}) ⩽ max(p_{i}) ⩽ (1 + ε)N/n.

Pour conclure, l’inégalité (2.6) de Rudelson s’applique dans un cadre général (n’importe quelle mesure isotrope sur R^{n}) et elle est optimale en toute généralité. Néanmoins, il est possible qu’en utilisant des outils spécifiques au cadre des corps convexe on puisse obtenir des améliorations.

2.1.2 Convexes et mesures log-concaves isotropes

Rappelons qu’un convexe K est dit isotrope si la mesure μ_{K} l’est, c’està-dire si sa matrice d’inertie est la matrice identité. Notons que cette définition est légèrement différente de celle utilisée habituellement en analyse géométrique asymptotique, où la normalisation est obtenue en imposant vol(K) = 1. Avec notre définition, contrôler le volume d’un convexe isotrope est équivalent à la conjecture de l’hyperplan (cf [MiPa1]). Introduisons maintenant la notion de mesure log-concave

Définition : Une mesure positive μ sur R^{n} est dite logarithmiquement concave (ou plus simplement : log-concave) si pour toutes parties A, B mesurables de R^{n} et pour tout θ dans ]0, 1[, on a

μ^{∗}(θA + (1 − θ)B) ⩾ μ(A)^{θ}μ(B)^{1−θ}.

Il se peut que A + B ne soit pas mesurable même si A et B le sont (voir [Sie]), d’où la nécessité d’introduire la mesure extérieure μ^{∗}. Alternativement, on pourrait se restreindre aux parties compactes. Borell a obtenu une caractérisation des mesures log-concaves particulièrement remarquable [Bor] : une mesure est log-concave si et seulement si elle a une densité par rapport à la mesure de Lebesgue sur l’espace affine engendré par son support, et si le logarithme de cette densité est une fonction concave (on autorise ici la valeur −∞ pour les fonctions concaves). Un exemple de mesure log-concave est donné par les mesures μ_{K} définies précédemment ; en effet la fonction − log(1_{K}) est concave si K est un ensemble convexe.

La classe des mesures log-concaves jouit de certaines propriétés de stabilité : ainsi les marginales de mesures log-concaves sont encore log-concaves. Plus précisément, soit μ une mesure log-concave sur R^{n} et E un sous-espace vectoriel. On identifie R^{n} à E × E^{⊥}. La mesure marginale μ|E, définie pour B ⊂ E borélien par

(μ|E)(B) = μ(B × E^{⊥}),

est aussi log-concave. C’est une conséquence de l’inégalité de Prékopa–Leindler (cf [Pré]). Ainsi, les marginales de mesures uniformes sur des convexes sont log-concaves. Réciproquement, si μ est une mesure log-concave sur R^{k}, on peut construire une suite (K_{n})_{n⩾k} de convexes, K_{n} ⊂ R^{n}, tels que la suite des mesures marginales

(μ_{K_{n}}|R^{k})_{n⩾k}

converge étroitement vers μ (voir par exemple [AKM]). La classe des mesures de probabilité log-concaves isotropes est une classe de mesures dont les matrices d’inertie sont bien approximables ; avant de développer ce point, listons-en quelques propriétés qui nous seront utiles.

Lemme 10. 1. Il existe une constante universelle C telle que si X est un vecteur aléatoire dans R^{n} distribué selon une loi log-concave isotrope, et si θ ∈ S^{n−1} est une direction, alors la variable aléatoire ⟨X, θ⟩ est Ψ_{1} avec constante C.

2. Il existe des constantes universelles c, C telles que si μ est une mesure de probabilité log-concave isotrope sur R^{n}, de densité f par rapport à la mesure de Lebesgue, alors pour toute direction θ ∈ S^{n−1}, on a

c ⩽ ∫_{θ^{⊥}} f(x)dx ⩽ C,

dx désignant ici la mesure de Lebesgue sur l’hyperplan θ^{⊥}.

3. Il existe une constante universelle C telle que pour tout convexe isotrope K ⊂ R^{n}, si X est un vecteur aléatoire de loi μ_{K}, alors la norme euclidienne de X est une variable aléatoire qui est Ψ_{2} avec constante C\sqrt{n}.

4. Il existe une constante universelle c telle que pour toute mesure de probabilité log-concave isotrope inconditionnelle μ, et pour tous nombres positifs (α_{1}, …, α_{n}), on a

μ({(x_{1}, …, x_{n}) tq |x_{1}| ⩾ α_{1}, …, |x_{n}| ⩾ α_{n}}) ⩽ e^{−c(α_{1}+···+α_{n})}.

On peut trouver la preuve de l’ensemble de ces résultats dans les notes [Gia]. Le fait 1 est dû à Borell et le fait 2 à Hensley ([Hen]). Leur preuve repose sur des inégalités valables pour des fonctions log-concaves de R dans R, en effet ⟨X, θ⟩ est une marginale de X, et est donc également log-concave. Le fait 3 est dû à Alesker ([Ale]), il est d’autant plus remarquable qu’il ne se généralise pas à toutes les mesures log-concaves (considérer par exemple, en dimension 1, une variable exponentielle). Le fait 4 a été prouvé par Bobkov et Nazarov ([BN1]). Le lemme suivant en est une conséquence

Lemme 11. Il existe une constante universelle C tel que pour tout vecteur aléatoire X = (x_{1}, …, x_{n}) de loi isotrope inconditionnelle log-concave et pour toute partie I ⊂ {1, …, n}, on a

E ∏_{i∈I} x_{i}^{2} ⩽ C^{#I}.

Démonstration. Soit z une variable aléatoire symétrique telle que P(|z| > t) = e^{−ct} pour tout t > 0. Soit Z = (z_{1}, …, z_{n}) un n-uplet de copies indépendantes de z. Le lemme 10.4 se reformule alors comme suit

P({|x_{1}| ⩾ α_{1}, …, |x_{n}| ⩾ α_{n}}) ⩽ P({|z_{1}| ⩾ α_{1}, …, |z_{n}| ⩾ α_{n}}).

La version intégrée de cette inégalité (qui s’obtient comme dans le cas d’un convexe inconditionnel traité dans [BN2]) s’écrit alors ainsi : pour toute mesure π positive sur (R^{+})^{n}, la fonction F : (R^{+})^{n} → R définie par

F (x_{1}, …, x_{n}) = π([0, x_{1}] × ⋯ × [0, x_{n}])

vérifie l’inégalité

EF (X) ⩽ EF (Z).

La fonction F_{I}(x_{1}, …, x_{n}) = ∏_{i∈I} x_{i}^{2} entre dans ce cadre et le lemme découle du fait que EF_{I}(Z) se calcule facilement (les coordonnées de Z sont indépendantes) et vaut (2/c^{2})^{#I}.

Les techniques présentées auparavant ne permettent pas d’obtenir l’approximation de la matrice d’inertie avec moins de Cn log n échantillons. Il existe cependant certaines mesures pour lesquelles on sait que l’on peut faire mieux. Introduisons la définition suivante

Définition : Si μ est une mesure de probabilité isotrope dans R^{n}, sa norme Ψ_{2}, notée Ψ_{2}(μ) est définie par

Ψ_{2}(μ) = sup_{θ∈S^{n−1}} ∥⟨X, θ⟩∥_{Ψ_{2}},

où X est un vecteur aléatoire de loi μ. On écrit aussi Ψ_{2}(K) pour Ψ_{2}(μ_{K})

Pour les mesures dont on contrôle la norme Ψ_{2}, il est possible d’approximer la matrice d’inertie avec un nombre de points proportionnel à la dimension. Plus précisément, on a la proposition suivante

Proposition 2.1. Il existe une constante universelle C telle que, si μ est une mesure de probabilité centrée sur R^{n}, si 0 ⩽ ε ⩽ 1/2 et si N ⩾ CΨ_{2}(μ)^{4}log(1/ε)/ε^{2}, alors avec probabilité supérieure à 1 − ε, on a ε-ap-proximation de la matrice d’inertie de μ avec N échantillons :

(1 − ε)A_{μ} ⩽ A_{μ_{N}} ⩽ (1 + ε)A_{μ}.  (2.8)

Démonstration. Cette proposition est très similaire aux résultats de [GM], néanmoins elle n’y figure pas sous cette forme. La preuve utilise la forme suivante des inégalités de Bernstein, que l’on peut trouver par exemple dans [BLM]

Lemme 12. Si (X_{i}) est une suite de variables aléatoires indépendantes, d’espérance nulle, telle que pour tout i, ∥X_{i}∥_{Ψ_{1}} ⩽ A, alors pour tout 0 < ε < 4A et pour tout n ⩾ 1

P (|∑_{i=1}^{n} X_{i}| ⩾ εn) ⩽ 2 exp(−ε^{2}n/16A^{2}).  (2.9)

On peut tout d’abord supposer que la mesure μ est isotrope, dans ce cas (2.8) est équivalent à

∀x ∈ S^{n−1}, 1 − ε ⩽ ⟨A_{μ_{N}} x, x⟩ ⩽ 1 + ε.  (2.10)

On va utiliser un argument de réseau. Fixons d’abord une direction θ ∈ S^{n−1}, et soit (X_{i}) des vecteurs aléatoires i.i.d. de loi μ. On a alors

∥⟨X_{i}, θ⟩^{2}∥_{Ψ_{1}} = ∥⟨X_{i}, θ⟩∥_{Ψ_{2}}^{2} ⩽ Ψ_{2}(μ)^{2}.

Et, comme E⟨X_{i}, θ⟩^{2} = 1

∥⟨X_{i}, θ⟩^{2} − 1∥_{Ψ_{1}} ⩽ 2Ψ_{2}(μ)^{2}.

Par les inégalités de Bernstein (lemme 12), pour tout α ⩽ 1

P (\frac{1}{N} |∑_{i=1}^{N}(⟨X_{i}, θ⟩^{2} − 1)| ⩾ α) ⩽ 2 exp (−\frac{α^{2}N}{64Ψ_{2}(μ)^{4}} ) .

Autrement dit,

∀θ ∈ S^{n−1}, P(1 − α ⩽ ⟨A_{μ_{N}} θ, θ⟩ ⩽ 1 + α) ⩾ 1 − 2 exp (−\frac{α^{2}N}{64Ψ_{2}(μ)^{4}} ) .

Soit maintenant N un α-réseau de S^{n−1} de cardinal inférieur à (3/α)^{n}. En utilisant la propriété d’approximation du réseau, on obtient

∥A_{μ_{N}} ∥ = sup_{x∈S^{n−1}}⟨A_{μ_{N}} x, x⟩ ⩽ sup_{θ∈N}⟨A_{μ_{N}} θ, θ⟩ + 2α∥A_{μ_{N}} ∥,

inf_{x∈S^{n−1}}⟨A_{μ_{N}} x, x⟩ ⩾ inf_{θ∈N}⟨A_{μ_{N}} θ, θ⟩ − 2α∥A_{μ_{N}} ∥.

Soit E l’événement « ∀θ ∈ N , 1 − α ⩽ ⟨A_{μ_{N}} θ, θ⟩ ⩽ 1 + α », qui implique

∀x ∈ S^{n−1}, \frac{1 − 5α}{1 − 2α} ⩽ ⟨A_{μ_{N}} x, x⟩ ⩽ \frac{1 + α}{1 − 2α}.

Lorsque α ⩽ 1/8, on a les inégalités (1+α)/(1−2α) ⩽ 1+4α et (1−5α)/(1− 2α) ⩾ 1 − 4α. En choisissant α = ε/4, on obtient donc (2.10) dès que E est vrai. Or, on a l’estimation

P(E) ⩾ 1 − 2 (\frac{12}{ε})^{n} exp (−\frac{ε^{2}N}{1024Ψ_{2}(μ)^{4}} ) .

La proposition est donc prouvée, en choisissant la constante C suffisamment grande.

La classe des convexes isotropes K tels que Ψ_{2}(K) soit borné indépendamment de la dimension est assez restreinte, elle contient par exemple les boules B_{p}^{n} pour p ⩾ 2. Il est naturel de se demander si, pour des corps convexes (ou des mesures log-concaves) pour lesquels la quantité Ψ_{2}(·) n’est pas bornée par une constante indépendante de la dimension, il est néanmoins possible d’avoir ε-approximation de la matrice d’inertie avec un nombre d’échantillons proportionnel à la dimension. Le premier exemple qui vient à l’esprit est celui de la boule B_{1}^{n}, car cet exemple est en quelque sorte à l’opposé des corps convexes pour lesquels Ψ_{2}(·) est borné. Nous verrons que l’approche via la théorie des matrices aléatoires permet de répondre positivement à cette question.

2.1.3 Matrices aléatoires et échantillonnage

Dans cette section, nous allons faire le lien entre les matrices aléatoires telles qu’elles ont été introduites auparavant et le problème de l’échantillonnage. Prenons le cas d’une mesure μ isotrope. La première remarque à faire est la suivante : la matrice d’inertie empirique, définie comme

A_{μ_{N}} = \frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}|,

peut aussi être vue comme le produit matriciel Γ_{N}^{†}Γ_{N}, où Γ_{N} est la matrice suivante, formée de N lignes et n colonnes

Γ_{N} = \frac{1}{\sqrt{N}} ( X_{1} ; X_{2} ; ⋮ ; X_{N} ) .  (2.11)

L’inégalité d’approximation de la matrice d’inertie ∥A_{μ_{N}} −Id∥ ⩽ ε se traduit sur la matrice Γ_{N} en

\sqrt{1 − ε} ⩽ s_{min}(Γ_{N}) ⩽ s_{max}(Γ_{N}) ⩽ \sqrt{1 + ε}.

Cette approche a été introduite par exemple dans [MePa]. Les lignes de la matrice Γ sont indépendantes, mais les colonnes ne le sont pas (sauf si la mesure μ échantillonnée peut s’écrire comme une mesure-produit μ_{1}⊗⋯⊗μ_{n}). C’est ici un point fondamental : en effet le comportement des valeurs singulières de matrices aléatoires dont les coefficients sont des variables aléatoires indépendantes est un sujet très étudié. On a par exemple les résultats suivants, dans le régime global et dans le régime local :

Théorèmes. Fixons une loi μ, d’espérance nulle, de variance 1 et possédant un moment d’ordre 4. Soit pour chaque couple d’entiers (n, N), N ⩾ n, une matrice aléatoire Γ = Γ_{n,N}, de taille n × N, dont les coefficients sont des variables aléatoires i.i.d. de loi μ. La mesure empirique associée aux valeurs singulières de \frac{1}{\sqrt{N}} Γ est définie par

μ_{Γ} = \frac{1}{n} ∑_{i=1}^{n} δ_{s_{i}(Γ)/\sqrt{N}}.

On considère une suite de couples (n, N) tendant vers l’infini de telle manière que le rapport n/N tende vers une limite β ∈]0, 1[. On a alors les théorèmeslimites suivants

– Marčenko–Pastur [MaPa] : Presque sûrement, la suite (μ_{Γ_{n,N}}) converge étroitement vers la mesure déterministe μ_{β}, supportée par l’intervalle [1 − \sqrt{β}, 1 + \sqrt{β}], donnée par la densité

\frac{dμ_{β}}{dx} = \frac{1}{πβx}\sqrt{((1 + \sqrt{β})^{2} − x^{2})(x^{2} − (1 − \sqrt{β}))^{2}}.

– Bai–Yin [BY] : Presque sûrement, on a les convergences :

lim_{(n,N)→∞} \frac{1}{\sqrt{N}} s_{min}(Γ_{n,N}) = 1 − \sqrt{β},

lim_{(n,N)→∞} \frac{1}{\sqrt{N}} s_{max}(Γ_{n,N}) = 1 + \sqrt{β}.

Le résultat le plus intéressant pour le problème de l’échantillonnage est le théorème de Bai–Yin : on cherche en effet à contrôler les valeurs singulières extrémales. Il y a priori deux obstacles majeurs qui nous empêchent d’appliquer ce théorème :

1. C’est seulement un résultat limite alors que l’on a en vue un résultat valide en toute dimension.

2. Les coefficients de la matrice Γ_{N} ne sont pas en général indépendants. Le problème posé par le point 1 est très similaire aux travaux présen-

tés dans le chapitre 1 : il faut raffiner la preuve d’un résultat-limite pour obtenir un résultat uniforme, c’est-à-dire valable en toute dimension. C’est vraisemblablement une tâche ardue, mais nous verrons que des résultats de concentration permettent ici de contourner le problème et de travailler directement à partir du résultat-limite.

Le point 2 est en revanche beaucoup plus fondamental : en effet la propriété d’indépendance des coefficients est utilisée de façon cruciale dans [BY].

Nous parvenons cependant à des résultats satisfaisants dans certains cas particuliers. Un résultat dû à Barthe, Guédon, Mendelson et Naor permet de décrire la mesure uniforme sur les boules B_{p}^{n} par des opérations élémentaires à partir de composantes 1-dimensionnelles ; cela permet de se ramener au cas où les coefficients sont indépendants et d’appliquer les théorèmes évoqués précédemment pour obtenir

Théorème 2.3 : Fixons 1 ⩽ p ⩽ +∞. Pour chaque couple (n, N), N ⩾ n, soit Γ_{N} la matrice définie par (2.11), les (X_{i}) étant uniformément distribués sur l’image homothétique isotrope de la boule B_{p}^{n}. Soit μ_{Γ} = 1/n ∑_{i=1}^{n} δ_{s_{i}(Γ)} la mesure spectrale empirique associée. Alors, si on considère une suite de couples (n, N) tendant vers l’infini de telle manière que le rapport n/N tende vers une limite β ∈]0, 1[, presque sûrement, la suite (μ_{Γ_{n,N}}) converge étroitement vers la distribution de Marchenko–Pastur μ_{β}.

De même, à partir du théorème de Bai–Yin, on peut obtenir le théorème suivant :

Théorème 2.1 : Pour tout ε > 0 et pour tout 1 ⩽ p ⩽ ∞, il existe une constante K = K(ε, p) telle que, si (X_{1}, …, X_{N}) sont i.i.d. uniformément sur l’image homothétique isotrope de la boule B_{p}^{n} et N ⩾ Kn, alors avec probabilité supérieure à 1 − ε, on a

∥\frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}| − Id∥ ⩽ ε.

Cela répond positivement à la question posée dans la section précédente : il est possible d’obtenir l’ε-approximation de la matrice d’inertie de la boule B_{1}^{n} avec un nombre d’échantillons qui est proportionnel à la dimension. à notre connaissance, c’est le premier exemple d’une famille de convexes (dans toutes les dimensions) dont la quantité Ψ_{2}(·) n’est pas bornée, pour laquelle un tel résultat d’approximation est prouvé.

Il y a très peu d’espoir d’obtenir une description de la mesure uniforme sur un convexe général aussi sympathique que dans le cas de la mesure uniforme sur B_{p}^{n}. Pour aller plus loin il est nécessaire de pénétrer dans la mécanique de la preuve du théorème de Bai–Yin ([BY]) et d’en adapter les rouages à notre contexte. Ceci est possible si l’on s’autorise une plus grande marge de manœuvre^{1}. Si l’approximation presque isométrique de la matrice d’inertie nécessite un contrôle total de toutes les erreurs, ce n’est pas le cas l’approximation isomorphe, où l’on cherche à obtenir une inégalité du type

1J’ai pu en fait démontrer la version forte — l’approximation quasi-isométrique — après la rédaction du manuscrit. Voir l’appendice 2.3.1.

\frac{1}{C} A_{μ} ⩽ A_{μ_{N}} ⩽ CA_{μ},

la constante C pouvant être choisie arbitrairement grande. Il est alors possible d’obtenir un résultat d’approximation, uniformément sur toute la classe des mesures log-concaves inconditionnelles :

Théorème 2.2 : Pour tout ρ > 1 il existe des constantes C(ρ), c(ρ), telles que, pour toute mesure log-concave isotrope inconditionnelle μ sur R^{n}, si (X_{1}, …, X_{N}) sont i.i.d. de loi μ avec N ⩾ ρn, alors avec probabilité supérieure à 1 − exp(−c(ρ)n^{1/11}), on a

∥A_{μ_{N}} ∥ ⩽ C(ρ) et ∥A_{μ_{N}}^{−1} ∥ ⩽ C(ρ),

ou en d’autres termes, pour tout θ dans S^{n−1}

\frac{1}{C(ρ)} ⩽ \frac{1}{N} ∑_{i=1}^{N}⟨X_{i}, θ⟩^{2} ⩽ C(ρ).

Il est frappant de remarquer que le facteur ρ > 1 peut être choisi aussi petit que possible. Par exemple, seulement [1.1n] échantillons suffisent à déterminer, avec une erreur contrôlée et une grande probabilité, la matrice d’inertie d’un convexe inconditionnel ! Ce phénomène ne semble pas avoir été observé précédemment. Il est bien sûr tentant de conjecturer qu’un résultat similaire reste vrai pour des convexes généraux ; répondre à cette question nécessiterait vraisemblablement de nouveaux outils car notre preuve utilise la propriété d’inconditionnalité de manière centrale.

2.2 Sampling convex bodies: the random matrix approach

We adapt results and techniques from the classical Random Matrix Theory (where matrices have independent entries) to the framework of matrices with independent rows. We prove that the inertia ellipsoid of a log-concave unconditional measure in R^{n} can be isomorphically approximated by cn sample points, for any c > 1. For ℓ_{p}^{n} balls we also obtain almost isometric approximation.

2.2.1 Introduction

The following notation will be kept throughout the paper: C, c, C′, ... denote absolute constants whose value may change from line to another. By μ we denote a probability measure on R^{n} which is isotropic, i.e. for any direction θ in the unit sphere S^{n−1}, ∫_{R^{n}}⟨x, θ⟩dμ = 0 and ∫_{R^{n}}⟨x, θ⟩^{2}dμ = 1. The random vectors X_{1}, …, X_{N} are i.i.d. according to μ. The matrix Γ = Γ_{N} and A = A_{N} denote respectively

Γ_{N} = \frac{1}{\sqrt{N}} ( X_{1} ; X_{2} ; ⋮ ; X_{N} )  (2.12)

A_{N} = Γ_{N}^{†}Γ_{N} = \frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}|  (2.13)

The matrix A must be thought of as the empirical approximation to the inertia matrix of μ, which equals the identity matrix because of the isotropy condition (E|X⟩⟨X| = Id). In this situation we say that Γ and A sample the measure μ (with N sample points). A natural question asked in [KLS] is then: how large the number N of sample points should be to ensure that the empirical inertia matrix A is, with high probability, (1 + ε)-close to the identity, in the sense that

P (∥\frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}| − Id∥ ⩾ ε) ⩽ ε  (2.14)

Note for future reference that ∥A∥ = ∥Γ∥^{2} = s_{1}(Γ)^{2} and ∥A^{−1}∥ = s_{n}(Γ)^{−2}, where s_{1}(Γ) (resp. s_{n}(Γ)) denotes the largest (resp. smallest) singular value of Γ. Of course N must also depend on the error ε allowed; however here we are interested in asymptotics when the dimension n tends to infinity. A general result in this direction was obtained by Rudelson, who proved in [Rud] the following result valid for any isotropic random vector X in R^{n} (X_{i} being i.i.d. copies of X)

E ∥\frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}| − Id∥ ⩽ C\sqrt{\frac{log n}{N}}(E∥X∥_{2}^{log N})^{1/ log N}  (2.15)

provided that the r.h.s. is smaller that 1, ∥ · ∥_{2} being the Euclidean norm on R^{n}.

To get any result using this inequality it is clear that one must take N at least c(ε)n log n, since the parenthesis in the r.h.s. is always larger than (E∥X∥_{2}^{2})^{1/2} = \sqrt{n}. In some cases this is sharp: consider for example the isotropic probability measure which assigns a mass 1/2n to the points ±\sqrt{n}e_{i}, where (e_{i}) is the canonical basis of R^{n}. This case is fairly simple to analyze, and is equivalent to the following probabilistic experiment: put randomly, uniformly and independently N balls into n urns. How large should be N such that, with high probability, all urns contain between (1 + ε)N/n balls and (1+ε)^{−1}N/n balls ? This is a classical problem and the answer is of order N ≈ c(ε)n log n ([KSC]), the bound obtained using (2.15). This example is the simplest example of a frame, which are studied in [Ver].

We are interested here in the case when μ has a log-concave density, and more specially when it is the uniform measure μ_{K} on a convex body K. We say that K is isotropic if μ_{K} is isotropic; note that this definition is slightly different from the usual one in asymptotic convex geometry, where normalization is achieved by setting vol(K) = 1. A special class of measures with extra symmetry properties is the class of unconditional measures: they are the measures μ which are invariant under reflections into coordinate hyperplanes, i.e. for any Borel set A ⊂ R^{n} and η in {−1, 1}^{n}, we have μ(A) = μ(S_{η}A), where S_{η} is the linear map defined by S_{η}(x_{1}, …, x_{n}) = (η_{1}x_{1}, …, η_{n}x_{n}). We similarly say that K is unconditional if μ_{K} is unconditional.

In the case of an isotropic convex body, it was proved by Kannan, Lovász and Simonovits ([KLS]) that (2.14) holds when N ⩾ C(ε)n^{2}, where C(ε) is a constant; we are not interested in the dependence in ε here. This was improved later to N ⩾ C(ε)n log^{3} n by Bourgain ([Bou]) and to N ⩾ C(ε)n log^{2} n by Rudelson as a consequence of (2.15). As noted in [GM], a slight modification of Bourgain’s argument also gives N ⩾ C(ε)n log^{2} n. In some special cases it is possible to use Rudelson’s technique with full strength: for unconditional bodies N ⩾ C(ε)n log n points are enough, as shown by Giannopoulos, Hartzoulaki and Tsolomitis ([GHT]).

Let us introduce now some useful terminology: for α ∈ [1, 2], the Ψ_{α} norm of a random variable f is defined by

∥f∥_{Ψ_{α}} = inf{t > 0 s.t. E exp((f/t)^{α}) ⩽ 2}  (2.16)

This is a Orlicz norm. Moreover, (2.16) implies the moments and tail estimates (C is an absolute constant)

∀p ⩽ 1, E|f|^{p} ⩽ (Cp∥f∥_{Ψ_{α}})^{p/α}  (2.17)
∀t > 0, P(|f| ⩾ t) ⩽ 2 exp(−(f/∥f∥_{Ψ_{α}})^{α})  (2.18)

An isotropic random vector X in R^{n} is said to be Ψ_{α} (with constant κ) is all its marginals are uniformly Ψ_{α}:

∀θ ∈ S^{n−1}, ∥⟨X, θ⟩∥_{Ψ_{α}} ⩽ κ

If a random vector is Ψ_{2} with constant κ, then the number of points in the approximation problem can be chosen to be proportional to the dimension: for every ε, there is a constant C depending on ε and on κ such that, if N ⩾ C(ε, κ)n and A defined as (2.13), then with probability larger than ε, ∥A − Id∥ ⩽ ε. This was previously shown in proposition 2.1. Much more can actually be proved for Ψ_{2} random vectors; see [MPT]. Examples of Ψ_{2} random vectors are vectors uniformly distributed on (the isotropic image of) the ℓ_{p}^{n} ball for p larger than 2 (see [BGMN]).

On the other hand, there is a very different class of measures for which, at least asymptotically, we can do better and take N proportional to n: the class of product measures. If μ = ν^{⊗n}, where ν is a probability measure on R, the entries of Γ are i.i.d. random variables, and this enters the setting of the following result of Bai and Yin ([BY]). The notation [·] stands for integer part.

Theorem (Bai–Yin): Fix a real number β ∈ (0, 1) and a measure ν on R with mean zero, variance one and finite fourth moment. For each n, let B^{(n)} be a n × N random matrix with entries i.i.d. according to ν, with N = [n/β]. Then, almost surely,

lim_{n→+∞} s_{1} (\frac{1}{\sqrt{N}} B^{(n)}) = 1 + \sqrt{β} and lim_{n→+∞} s_{n} (\frac{1}{\sqrt{N}} B^{(n)}) = 1 − \sqrt{β} (2.19)

The matrices B^{(n)} satisfying the hypotheses of the Bai–Yin theorem are sometimes called Wishart matrices. This theorem is a typical limit theorem from random matrix theory, and the drawback is that there is no quantitative estimate on the speed of convergence and no information for fixed n.

In this note we try to adapt results and techniques from Random Matrix Theory to the case of an isotropic measure uniformly distributed on a convex body. We show here that a proportional number of sample points is enough to obtain almost isometric approximation for ℓ_{p}^{n} balls, and to obtain isomorphic approximation for unconditional log-concave measures.

Theorem 2.1. For every ε > 0 and 1 ⩽ p ⩽ ∞, there is a constant K = K(ε, p) such that if (X_{1}, …, X_{N}) are i.i.d. uniformly distributed on the isotropic image of the unit ball of ℓ_{p}^{n} with N ⩾ Kn, then with probability larger than 1 − ε, we have

∥\frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}| − Id∥ ⩽ ε

Theorem 2.2. For any ρ > 1 there are constants C(ρ), c(ρ), such that for any isotropic unconditional log-concave measure μ on R^{n}, if (X_{1}, …, X_{N}) are i.i.d. according to μ with N ⩾ ρn, if A is defined as (2.13), then with probability larger than 1 − exp(−c(ρ)n^{1/11}) we have

∥A∥ ⩽ C(ρ) and ∥A^{−1}∥ ⩽ C(ρ)

or, in other words, for every θ in S^{n−1}

\frac{1}{C(ρ)} ⩽ \frac{1}{N} ∑_{i=1}^{N}⟨X_{i}, θ⟩^{2} ⩽ C(ρ)

I am not able to prove than the constant C(ρ) tends to 1 when ρ tends to infinity^{2}. On the other hand, we can take ρ close to 1. For example, only 1.1n sample points determine isomorphically the inertia ellipsoid of a n-dimensional unconditional log-concave measure.

Acknowledgement: I want to thank Alain Pajor and Olivier Guédon for many fruitful discussions and ideas.

2.2.2 The case of the unit ball of ℓ_{p}^{n}

For 1 ⩽ p < +∞, we write B_{p}^{n} for the unit ball of ℓ_{p}^{n}, i.e. B_{p}^{n} = {(x_{1}, …, x_{n}) ∈ R^{n} s.t. ∑ |x_{i}|^{p} ⩽ 1}. There exists a unique positive real λ_{n,p} such that λ_{n,p}B_{p}^{n} is isotropic, and we write B̃_{p}^{n} = λ_{n,p}B_{p}^{n}. We will use the following representation of the uniform measure on B_{p}^{n} by Barthe, Guédon, Mendelson and Naor in order to transfer results from the case with independent entries.

2I was actually able, after the manuscript was submitted. See Appendix 2.3.1.

Theorem ([BGMN]). Let (Y_{i}) be a n-tuple of i.i.d. random variables distributed according to the probability ν_{p} with density 1/(2Γ(1 + 1/p))e^{−|t|^{p}} (t ∈ R). We write Y = (Y_{1}, …, Y_{n}). Let also Z be an exponential random variable independent from Y (i.e. the density of Z is e^{−t}, t ⩾ 0). Then the random vector

\frac{Y}{(∑_{i=1}^{n} |Y_{i}|^{p} + Z)^{1/p}}  (2.20)

generates the normalized Lebesgue measure on B_{p}^{n}.

The following lemma will enable us to transfer the results from the independent case to the B_{p}^{n} case.

Lemma 13. Let Γ be a N × n matrix whose rows are i.i.d. random vectors distributed according to the Lebesgue measure on B̃_{p}^{n}. Let B = (b_{ij}) be a N ×n random matrix whose entries are independent and distributed according to ν_{p}. Let Δ be a N × N diagonal matrix with entries δ_{jj} = (∑_{i=1}^{n} |b_{ij}|^{p} + Z_{j})^{−1/p}, where Z_{j} are i.i.d. exponential random variables independent from B. Then the random matrices Γ and λ_{n,p}Δ · B have the same distribution (here · is the usual matrix product).

Proof. It is a direct application of the representation theorem.

Using this trick, results on Wishart matrices can be transferred to the case of random matrices sampling B̃_{p}^{n}, since the diagonal matrix Δ will be very close to the identity matrix. It is actually quite easy to get from lemma 13 a limit theorem holding almost surely using the result of Bai and Yin. It is here possible using concentration properties to derive from the almost sure result a result holding for all n (or for all n large enough). The following lemma will be useful

Lemma 14. For fixed n and fixed probability measure μ on R^{n}, if (Y_{i}) are i.i.d. random vectors distributed according to μ, then

Eλ_{max} (\frac{1}{N} ∑_{i=1}^{N} |Y_{i}⟩⟨Y_{i}|)

is a decreasing function of N, whereas

Eλ_{min} (\frac{1}{N} ∑_{i=1}^{N} |Y_{i}⟩⟨Y_{i}|)

is an increasing function of N.

Proof. Let N_{1} ⩾ N_{2}. Let also I be a random subset of cardinality N_{2} of {1, …, N_{1}}, uniformly chosen. We write E′ for the expectation with respect to I, this is just a short way to write a finite sum. It follows from the convexity of the function λ_{max} on the set of self-adjoint matrices that

Eλ_{max} (\frac{1}{N_{1}} ∑_{i=1}^{N_{1}} |X_{i}⟩⟨X_{i}|) = Eλ_{max} (\frac{1}{N_{2}} E′ ∑_{i∈I} |X_{i}⟩⟨X_{i}|)

⩽ EE′λ_{max} (\frac{1}{N_{2}} ∑_{i∈I} |X_{i}⟩⟨X_{i}|)

= Eλ_{max} (\frac{1}{N_{2}} ∑_{i=1}^{N_{2}} |X_{i}⟩⟨X_{i}|)

The second statement follows similarly from the concavity of the function λ_{min}.

We fix p ∈ [1, ∞]. Given ε > 0, we choose ρ such that 1 + 1/\sqrt{ρ} ⩽ (1 + ε)^{1/3} − ε/6 and 1 − 1/\sqrt{ρ} ⩾ (1 − ε)^{1/3} + ε/6. For each n and N, consider the matrix Γ sampling the uniform measure on B̃_{p}^{n} with N sample points, defined as (2.12). We will rather consider the matrix Γ̃ = \frac{λ_{n,p}}{\sqrt{N}} Δ · B, where B and Δ are defined as in lemma 13; hence Γ and Γ̃ are identically distributed. We may write Γ^{(n)}, B^{(n)}, ... to insist on the dependence in n. We write r for the normalization factor (Eb_{11}^{2})^{−1/2}, so that the matrix rB^{(n)} has i.i.d. entries with mean 0 and variance 1. We will prove the following lemmas about the matrices B and Δ appearing in the decomposition

Lemma 15. There is an integer n_{0} (depending only on ε and p) such that for any n ⩾ n_{0} and N ⩾ ρn, we have with probability larger that 1 − ε/2, if B is an N × n matrix with entries i.i.d. according to ν_{p}

(1 − ε)^{1/3}\sqrt{N} ⩽ s_{n}(rB) ⩽ s_{1}(rB) ⩽ (1 + ε)^{1/3}\sqrt{N}  (2.21)

Proof. We use here concentration of measure: it is known that the measures ν_{p} satisfies a Poincaré inequality on R (see [Led1]). This implies concentration for the product measures: for any k ⩾ 1 and any function f : R^{k} → R which is 1-Lipschitz with respect to the Euclidean distance on R^{k}

ν_{p}^{⊗k}({(v_{1}, …, v_{k}) s.t. |f(v_{1}, …, v_{k}) − E_{ν_{p}^{⊗k}}f| > t}) ⩽ C_{p} exp(−c_{p}t) (2.22)

This can be applied to the largest (resp. smallest) singular value of a matrix, which is a 1-Lipschitz function of the entries of the matrix with respect to the Hilbert–Schmidt distance, as can be seen from the min-max characterization (where M is a N × n matrix)

s_{1}(M) = max_{x∈S^{n−1}} max_{y∈S^{N−1}}⟨Mx, y⟩

s_{n}(M) = min_{x∈S^{n−1}} max_{y∈S^{N−1}}⟨Mx, y⟩

In our context, (2.22) gives

P(|s_{1}(rB^{(n)}) − Es_{1}(rB^{(n)})| ⩾ t) ⩽ C_{p} exp(−c_{p}t/r)  (2.23)
P(|s_{n}(rB^{(n)}) − Es_{n}(rB^{(n)})| ⩾ t) ⩽ C_{p} exp(−c_{p}t/r)  (2.24)

The matrix rB^{(n)} has i.i.d. entries with mean 0 and variance 1, therefore it enters the setting of Wishart matrices and the Bai–Yin theorem (2.19) holds: if N = [ρn], this gives that almost surely, lim_{n→∞} s_{1}(rB^{(n)})/\sqrt{N} = 1 + 1/\sqrt{ρ} and lim_{n→∞} s_{n}(rB^{(n)})/\sqrt{N} = 1 − 1/\sqrt{ρ}. A first consequence is that for any θ > 0 there is a integer n_{1} = n_{1}(ε, p, θ) such that for n ⩾ n_{1} and N = [ρn]:

1 − 1/\sqrt{ρ} − θ ⩽ Es_{n}(rB)/\sqrt{N} ⩽ Es_{1}(rB)/\sqrt{N} ⩽ 1 + 1/\sqrt{ρ} + θ (2.25)

Indeed, if for example the right inequality was false, then using (2.23) we get that for n large enough, P(s_{1}(rB)/\sqrt{N} ⩾ 1 + 1/\sqrt{ρ} + θ/2) ⩾ 1/2, and this contradicts the almost sure convergence. The other inequality is handled similarly. In order to use lemma 14, we would prefer a statement about the second moment rather that the expectation. This can be done using concentration; another consequence of (2.23) and (2.24) is that

E(s_{1}(rB))^{2} − (Es_{1}(rB))^{2} = ∫_{0}^{∞} P(|s_{1}(rB) − Es_{1}(rB)|^{2} > t)dt ⩽ \frac{2Cr^{2}}{c^{2}}

(2.26)

and similarly for s_{n}. Together with (2.25), this gives the existence of an integer n_{2} = n_{2}(ε, p, θ) such that for n ⩾ n_{2} and N = [ρn]

(1 − 1/\sqrt{ρ} − 2θ)^{2} ⩽ E(s_{n}(rB)/\sqrt{N})^{2} ⩽
⩽ E(s_{1}(rB)/\sqrt{N})^{2} ⩽ (1 + 1/\sqrt{ρ} + 2θ)^{2}

Lemma 14 allows to extend automatically these inequalities to all N ⩾ ρn. Using again (2.26) to come back to expectations, this gives a rank n_{3} = n_{3}(ε, p, θ) such that if n ⩾ n_{3} and N ⩾ ρn

1 − 1/\sqrt{ρ} − 3θ ⩽ Es_{n}(rB)/\sqrt{N} ⩽ Es_{1}(rB)/\sqrt{N} ⩽ 1 + 1/\sqrt{ρ} + 3θ

Using again concentration inequalities (2.23) and (2.24), this gives for n ⩾ n_{4}(ε, p, θ) and N ⩾ ρn, with probability larger that 1 − ε/2:

1 − 1/\sqrt{ρ} − 4θ ⩽ s_{n}(rB)/\sqrt{N} ⩽ s_{1}(rB)/\sqrt{N} ⩽ 1 + 1/\sqrt{ρ} + 4θ

It remains to choose θ = ε/24 to prove the lemma.

Lemma 16. There is an integer n′_{0} and a constant β (depending only on ε and p ⩽ 2) such that for any n ⩾ n′_{0} and N ⩽ exp(βn), if Δ is a N × N diagonal matrix with entries δ_{jj} = (∑_{i=1}^{n} |b_{ij}|^{p} + Z_{j})^{−1/p}, with (b_{ij}) i.i.d. according to ν_{p} and (Z_{j}) i.i.d. according to ν_{1}, then with probability larger than 1 − ε/2,

(1 − ε)^{1/3}(nE|b_{11}|^{p})^{−1/p} ⩽ s_{n}(Δ) ⩽ s_{1}(Δ) ⩽ (1 + ε)^{1/3}(nE|b_{11}|^{p})^{−1/p} (2.27)

Proof. Since p ⩽ 2, the random variables |b_{ij}|^{p} and Z_{j} are Ψ_{1} with constant depending on p, and the same is true for their centered versions |b_{ij}|^{p}−E|b_{11}|^{p} and Z_{j} − EZ_{j}. Applying Bernstein’s inequality (lemma 12), we get for any θ ⩽ C and any 1 ⩽ j ⩽ N

P (|∑_{i=1}^{N} |b_{ij}|^{p} + Z_{j} − nE|b_{ij}|^{p}| ⩾ θn + 1) ⩽ 2 exp(−c_{p}θ^{2}n)

By choosing θ small enough (depending on ε), we get for any fixed j, with probability larger than 1 − exp(−c(ε, p)n)

(1 − ε)^{1/3}(nE|b_{11}|)^{−1/p} ⩽ δ_{jj} ⩽ (1 + ε)^{1/3}(nE|b_{11}|)^{−1/p}

For n large enough, the conclusion of the lemma holds since s_{n}(Δ) = min(δ_{jj}) and s_{1}(Δ) = max(δ_{jj}).

Proof of theorem 2.1: For p ⩾ 2, a random vector uniformly distributed on the B̃_{p}^{n} ball is Ψ_{2} (see [BGMN]). Since for Ψ_{2} random vectors it is known that one can always take a proportional number of sample points (proposition 2.1), we can assume that p ⩽ 2.

The constant λ_{n,p} can be calculated using the representation theorem, or by direct calculation:

λ_{n,p} = (\frac{1}{vol(B_{p}^{n})} ∫_{B_{p}^{n}} x_{1}^{2}dx_{1} … dx_{n})^{−1/2} ∼_{n→∞} \frac{n^{1/p}(E|b_{11}|^{p})^{1/p}}{(Eb_{11}^{2})^{1/2}} (2.28)

And so for n bigger than some n_{1},

(1 − ε)^{1/3} \frac{(nE|b_{11}|^{p})^{1/p}}{(Eb_{11}^{2})^{1/2}} ⩽ λ_{n,p} ⩽ (1 + ε)^{1/3} \frac{(nE|b_{11}|^{p})^{1/p}}{(Eb_{11}^{2})^{1/2}}  (2.29)

Let now n bigger than max(n_{0}, n′_{0}, n_{1}), where n_{0} and n′_{0} appear in lemmas 15 and 16. Then the statements (2.21), (2.27) and (2.29) hold simultaneously with probability larger than 1 − ε. Using the inequalities s_{1}(Δ·B) ⩽ s_{1}(Δ)s_{1}(B) and s_{n}(Δ·B) ⩾ s_{n}(Δ)s_{n}(B), this implies s_{1}(Γ) ⩽ 1+ε and s_{n}(Γ) ⩾ 1−ε, provided n ⩾ max(n_{0}, n′_{0}, n_{1}) and ρn ⩽ N ⩽ exp(βn). We now by previous results ([Rud] for example) than the same conclusion holds true if N ⩾ C(ε)n log^{2} n. If we define n̄ to be the smallest number so that n̄ ⩾ max(n_{0}, n′_{0}, n_{1}) and C(ε)n̄ log^{2} n̄ ⩽ exp(βn̄), this proves the theorem with K(ε, p) = ρ and for n larger than n̄. This latter condition can be removed by enlarging the constant K(ε, p) to K′(ε, p) = max(ρ, C(ε) log^{2} n̄).

Remark: We used here the theorem of Bai–Yin as a “black box”. This has several serious drawbacks: for example we have no information of the behavior of the function C(ε) in theorem 2.1, it may even depend on p. The right thing to do to avoid these problems should be to prove an analogue of Bai–Yin theorem valid for all dimensions n, with deviations estimates depending on the moments of the entries. Such a localized version was obtained by Sodin ([Sod]) in the case of ±1 random variables where he could use special properties of the entries to simplify the calculations.

The same trick allows us to transfer available results for the so-called global regime:

Theorem 2.3. Fix 1 ⩽ p ⩽ +∞. For any n, let Γ be defined as usual, using N = [n/β] sample points according to the uniform measure on B̃_{p}^{n}. Let s_{n}(Γ) ⩽ ⋯ ⩽ s_{1}(Γ) be the singular values of Γ, and μ_{Γ} = 1/n ∑_{i=1}^{n} δ_{s_{i}(Γ)} be the empirical spectral measure: for every Borel set B ⊂ R, μ_{Γ}(B) is the proportion of singular values which fall in B. Then, almost surely, the sequence (μ_{Γ}) converges weakly to the Marčenko–Pastur distribution μ_{β} supported on the interval [1 − \sqrt{β}, 1 + \sqrt{β}] and with density

\frac{dμ_{β}}{dx} = \frac{1}{πβx}\sqrt{((1 + \sqrt{β})^{2} − x^{2})(x^{2} − (1 − \sqrt{β}))^{2}}

Proof. As in the previous proof, we use the alternative representation from lemma 13: Γ̃ = \frac{λ_{n,p}}{\sqrt{N}} Δ · B = Δ′ · B′ with Δ′ = λ_{n,p}(Eb_{11}^{2})^{1/2}Δ and B′ = \frac{1}{\sqrt{N}(Eb_{11}^{2})^{1/2}} B. The matrix B′ has i.i.d. entries with mean 0 and variance

1/\sqrt{N}. Let s_{n}(B′) ⩽ ⋯ ⩽ s_{1}(B′) be its singular values, and μ_{B′} = 1/n ∑_{i=1}^{n} δ_{s_{i}(B′)} be its empirical spectral measure. By the classical Marčenko– Pastur theorem (see [MaPa, OP]), almost surely, the sequence (μ_{B′}) converges weakly to μ_{β} when n tends to infinity. We want to prove that the same holds for (μ_{Γ}). Define δ to be the smallest number so that ∥Δ′∥ ⩽ 1 + δ and ∥Δ^{′−1}∥ ⩽ 1 + δ. By repeating the proof of lemma 16 and using (2.28), we obtain that the random variable δ tends almost surely to 0 when n tends to infinity.

Note that for every k ⩽ n, (1+δ_{n})^{−1}s_{k}(Γ) ⩽ s_{k}(B′) ⩽ (1+δ_{n})s_{k}(Γ). This implies in particular than for any a < b.

μ_{B′}([(1 + δ_{n})a, (1 + δ_{n})^{−1}b]) ⩽ μ_{Γ}([a, b]) ⩽ μ_{B′}([(1 + δ_{n})^{−1}a, (1 + δ_{n})b])

Consequently, we obtain that, almost surely,

lim_{n→∞} μ_{Γ}^{(n)}([a, b]) = lim_{n→∞} μ_{B′}^{(n)}([a, b]) = μ_{β}([a, b])

Since it is enough to check the weak convergence on intervals with rational endpoints, this proves the theorem.

Remark: The result of Theorem 2.3 was obtained independently by Pajor and Pastur ([PP]) using the Stieltjes transform method.

2.2.3 The case of unconditional log-concave measures: proof of theorem 2.2

We are first going to give a proof, based on the moments method, for the assertion on the norm of A. We work with the matrix Γ rather than with A. We denote the entries of Γ by (x_{ij}), i.e. x_{ij} is the jth coordinate of the vector X_{i}. We can also assume that N is not too large, for example N ⩽ n^{2}, since for larger values of N we can conclude using known results ([GHT] for example). We want to give an upper bound for E∥Γ∥^{2k} for an integer k as large as possible. We first need a truncation argument. Let E denote the event: “All entries of the matrix Γ have absolute value smaller than t_{0}”, where the truncation level t_{0}, depending on k and n, will be determined later. By lemma 10.1, the one-dimensional marginals of an isotropic logconcave measure are uniformly Ψ_{1}: there are absolute constants c, C such that for any i, j ,

P(|x_{ij}| > t) ⩽ C exp(−ct)

Therefore P(E^{c}) ⩽ CnN exp(−ct_{0}) ⩽ Cn^{3} exp(−ct_{0}). We then write

E∥Γ∥^{2k} = E(∥Γ∥^{2k}1_{E}) + E(∥Γ∥^{2k}1_{E^{c}})

On the small set E^{c} we can afford bad bounds. Denoting by ∥ · ∥_{HS} the Hilbert–Schmidt norm (Euclidean norm of the entries),

E(∥Γ∥^{2k}1_{E^{c}}) ⩽ \sqrt{E(∥Γ∥^{4k})}\sqrt{P(E^{c})} ⩽ \sqrt{E∥Γ∥_{HS}^{4k}}\sqrt{C}n^{3/2} exp(−ct_{0}/2)

Writing E∥Γ∥_{HS}^{4k} as 1/N^{2k}E(∑ x_{ij}^{2})^{2k} and expanding the sum, we obtain (nN)^{2k} terms of the form E ∏_{r=1}^{2k} x_{i_{r}j_{r}}. We bound each of them by

∏_{r=1}^{2k}(Ex_{i_{r}j_{r}}^{4k})^{1/2k}

by Hölder inequality, and use the moment version (2.18) of the Ψ_{1} property of the entries of Γ to get for an absolute constant C

E∥Γ∥_{HS}^{4k} ⩽ n^{2k}(Ck)^{4k}

Putting all estimates together, we obtain

E(∥Γ∥^{2k}1_{E^{c}}) ⩽ n^{k+3/2}(Ck)^{2k}\sqrt{C} exp(−ct_{0}/2)

We now set t_{0} = C_{1}k log n, where the absolute constant C_{1} is chosen so that E(∥Γ∥^{2k}1_{E^{c}}) ⩽ 1 (we will later choose k smaller than n).

It now remains to study E(∥Γ∥1_{E}). We bound the operator norm, which is the ℓ_{∞}^{n} norm of singular values, by the Schatten norm ∥A∥_{k} = (∑ s_{i}(Γ)^{k})^{1/k}.

∥Γ∥^{2k} ⩽ ∥A∥_{k}^{k} = tr(A^{k})

We get by expanding the trace that

Etr(A^{k})1_{E} = \frac{1}{N^{k}} ∑ Ex_{i_{1}j_{1}}x_{i_{1}j_{2}}x_{i_{2}j_{2}} … x_{i_{k}j_{k}}x_{i_{k}j_{1}}1_{E},

where the sum is taken over all indices i_{1}, …, i_{k} in {1, …, N} and j_{1}, …, j_{k} in {1, …, n}. Since the rows of Γ are independent, the expectation can be factorized as the product of N factors of the form

Ex_{1}^{α_{1}}x_{2}^{α_{2}} … x_{n}^{α_{n}}1_{F}  (2.30)

for some integers α_{1}, …, α_{n}, where X = (x_{1}, …, x_{n}) is a random vector distributed according to the sampled measure, and F is the event: “all coordinates of X have absolute value smaller than t_{0}”. Since the vector X, as well as its truncated variant X1_{F}, are unconditional, there are invariant under sign operators S_{η}, and this shows that the expectation (2.30) is zero when at least one of the α_{i} is odd. Now the arguments follows essentially the classical combinatorial techniques of [Gem, YBK], which for the reader’s convenience we repeat here. We are lead to the following inequality

E∥Γ∥^{2k}1_{E} ⩽ \frac{1}{N^{k}} ∑_{[(r_{1},s_{1}),...,(r_{2k},s_{2k})] V-graph} Ex_{r_{1}s_{1}} … x_{r_{2k}s_{2k}}1_{E}

where a V-graph is a 2k-uple of couples (r_{i}, s_{i}) ∈ {1, …, N} × {1, …, n} such that 1. r_{2p} = r_{2p−1}

2. s_{2p+1} = s_{2p} (and s_{1} = s_{2p})

3. Each couple (r_{i}, s_{i}) appears an even number of times.

Now we use the following strategy: if some x_{ij} appears 4 times or more, we bound it by t_{0}, and after this, since the event E has played its role, we also use 1_{E} ⩽ 1. Thus there only remain squared coefficients, which are treated by lemma 11 : for any I ⊂ {1, …, n}, we have

E ∏_{i∈I} x_{i}^{2} ⩽ C^{#I}.

Call two V-graphs G = [(r_{i}, s_{i})] and G′ = [(r′_{i}, s′_{i})] isomorphic if there exist permutations σ ∈ 𝔖_{N} and τ ∈ 𝔖_{n} such that r′_{i} = σ(r_{i}) and s′_{i} = τ(s_{i}). For a V-graph G = [(r_{1}, r_{1}), …, (r_{2k}, r_{2k})], we define the invariant ℓ by ℓ(G) := #{r_{i}} + #{s_{i}}. It the number of different indices that appear in G; note that 2 ⩽ ℓ(G) ⩽ k + 1. Also, the isomorphism class of G contains no more than N^{ℓ(G)} elements (recall that n ⩽ N).

Let n_{2}(G) be the number of indices i such that the couple (r_{i}, s_{i}) appears exactly 2 times in G and n_{+}(G) be the number of indices i such that the couple (r_{i}, s_{i}) appears 4 times or more in G. Since there are at least ℓ(G) − 1 different couples (r_{i}, s_{i}) in G, we get the relations ℓ(G) − 1 ⩽ \frac{1}{2}n_{2} + \frac{1}{4}n_{+} and n_{2} + n_{+} = 2k, which imply that n_{+} is smaller that 4(k − ℓ(G) + 1). Applying the strategy described before to bound the expectations, and gathering Vgraphs with the same ℓ, we get:

E∥Γ∥^{2k}1_{E} ⩽ (\frac{C}{N} )^{k} ∑_{l=2}^{k+1} N^{l}t_{0}^{4(k−l)+2}γ_{l}  (2.31)

where γ_{l} is the number of isomorphism classes of V-graphs G for which ℓ(G) = l. To each V-graph [(r_{1}, r_{1}), …, (r_{2k}, r_{2k})], we associate its type sequence, which is a sequence (τ_{1}, …, τ_{2k}) of elements of {T_{1}, T_{3a}, T_{3u}, T_{4}} defined as follows

• τ_{i} = T_{1} when (r_{i}, s_{i}) is an innovation, i.e. either r_{i} is not in the set {r_{j}, j < i} (row innovation), or s_{i} is not in the set {s_{j}, j < i} (column innovation). The first element is always an innovation. Also, row innovations can only occur when i is odd and column innovations when i is even.

• τ_{i} = T_{3a} or T_{3u} if (r_{i}, s_{i}) is the first repetition of an innovation, i.e. there exists i_{0} < i such that (r_{i_{0}}, s_{i_{0}}) = (r_{i}, s_{i}), and for every k such that i_{0} < k < i, (r_{k}, s_{k}) ≠ (r_{i}, s_{i}). If this repetition is ambiguous, i.e. if there exist an other unmatched innovation which is in the row/column in which (r_{i}, s_{i}) must lie, then we set τ_{i} = T_{3a}. If not, the repetition is unambiguous and we set τ_{i} = T_{3u}.

• τ_{i} = T_{4} in the other cases.

The type sequence is an invariant of V-graph isomorphism. Moreover, there are at most 4^{2k} = 16^{k} possible type sequence (this is very rough, but here we do not claim at optimality of constants). Also, there are exactly ℓ(G) − 1 innovations in a V -graph G, and consequently exactly ℓ(G) − 1 first repetitions of these innovations. Consequently, there are exactly 2(k−ℓ(G)+ 1) type T_{4} elements. The nice fact is that when ℓ becomes large, there are rather few isomorphism classes of V-graphs which have a given type sequence; this compensates for the fact that each individual isomorphism class is large. To check this fact, in each isomorphism class of V-graphs, we single out a element, called canonical V-graph, by the properties

• The first element is (1, 1)

• Each time a new index r_{i} (resp. s_{i}) appears, it is the smallest available one (i.e. the smallest number which is not in {r_{j}, j < i} (resp. {s_{j}, j < i}))

Note that in any canonical V-graph, all indices all smaller than k (they are even smaller than ℓ − 1). Now if we try to reconstruct a canonical V-graph from its type sequence starting from (1, 1), some steps are unambiguous: when τ_{i} = T_{1} (since the V-graph is canonical we must go to the next free row/column) and when τ_{i} = T_{3u}. The other steps (τ_{i} = T_{3a} and τ_{i} = T_{4}) are ambiguous, but for each of them there are at most k possible choices by the previous remark. The main lemma is now the following

Lemma 17 ([Gem],[YBK]). The number of ambiguous repetitions (τ_{i} = T_{3a}) in a V -graph is no more than twice the number of T_{4} elements (τ_{i} = T_{4}).

Proof. We give a very sketchy proof and refer to [Gem, YBK] for more details. We write n_{4} for the number of type T_{4} elements. If τ_{i} = T_{3a}, then τ_{i−1} ≠ T_{1}, otherwise there could not be ambiguity. If τ_{i−1} = T_{3a} or τ_{i−1} = T_{3u}, this means that at time i − 2 there must have been 3 unmatched innovations in the corresponding row/column. One can check that only type T_{4} elements can create such a situation, so this can occur at most n_{4} times (this is the delicate point). Also, it can happen that τ_{i−1} = T_{4}, but only at most n_{4} times. This proves the lemma.

The preceding discussion, together with lemma 17, gives

γ_{l} ⩽ 16^{k}k^{6(k−l+1)}  (2.32)

Plugging (2.32) into (2.31), we obtain

E(∥Γ∥^{2k}1_{E}) ⩽ C^{k}k^{6}t_{0}^{2} ∑_{l=2}^{k+1} (\frac{t_{0}^{4}k^{6}}{N} )^{k−l}

Recall that t_{0} = C_{1}k log n and choose now k = [n^{1/11}], so that for n large enough the parenthesis is smaller that 1, and the r.h.s. is bounded by C^{′k} for an absolute constant C′. Together with the estimate for E^{c}, this gives

For n ⩾ n_{0} and k = [n^{1/11}], E∥Γ∥^{k} ⩽ C^{′k}

By Markov inequality, we obtain immediately that

P(∥Γ∥ ⩾ 2C′) ⩽ E∥Γ∥^{k}/(2C′)^{k} ⩽ 1/2^{k}

and this proves the assertion on ∥A∥ = ∥Γ∥^{2}. It remains to show that s_{n}(Γ) is bounded away from 0. We are going actually to prove a more general result, from which the theorem follows immediately.

Proposition 2.2. For every C_{0} > 0 and ρ > 1 there are constants K = K(C_{0}, ρ), κ = κ(C_{0}, ρ) such that, for every isotropic log-concave measure μ, the matrix A sampling μ with N ⩾ ρn sample points, defined as (2.13), automatically satisfies

P(∥A^{−1}∥ > K) ⩽ P(∥A∥ > C_{0}) + exp(−κn)

Remark: Usually in random matrix theory, it is substantially harder to deal with the smallest eigenvalue than with the largest, hence the above proposition may surprise. We emphasize that it is only an isomorphic result.

Proof. The proof is similar to the proof of the main theorem in [LPRT], but here the log-concavity makes things much easier. We will rather work with the matrix Γ, seen as a linear operator from ℓ_{2}^{n} to ℓ_{2}^{N}, and we write | · | for the Euclidean norm in R^{n} or R^{N}. Note that ∥A^{−1}∥ ⩾ K is equivalent to the fact that there exists x in the sphere S^{n−1} such that |Γx| ⩽ 1/\sqrt{K}. Let now be N be a ε-net in S^{n−1} with cardinality smaller that (3/ε)^{n} (see lemma 2). Set also t = ε/\sqrt{C_{0}}. Let Ω̄ be the set of events ω such that ∥Γ(ω)∥ ⩽ \sqrt{C_{0}}. By the standard approximation argument, the event

Ω̄ ∩ {∃x ∈ S^{n−1} s.t. |Γx| ⩽ t}

is contained in the event

Ω̄ ∩ {∃x ∈ N s.t. |Γx| ⩽ 2t}

Consequently,

P(s_{n}(Γ) ⩽ t) ⩽ P(Ω̄^{c}) + #(N) max_{x∈S^{n−1}} P(|Γx| ⩽ 2t)

For fixed x in the sphere S^{n−1} and j between 1 and N, let f_{j} be the random variable ⟨X_{j}, x⟩. This is a marginal of μ. By lemma 10.2, when μ is a log-concave isotropic measure on R^{n}, the (n − 1)-dimensional measure of hyperplane sections is controlled up to universal constant: ∀θ ∈ S^{n−1} and t ∈ R, we have ∫_{θ^{⊥}+tθ} dμ ⩽ C for a universal constant C. This integral must be understood as ∫_{θ^{⊥}+tθ} g(x)dx, where g is the density of μ with respect to the Lebesgue measure on R^{n}. Consequently, there is an absolute constant C such that, for every s ⩾ 0, P(|f_{j}| ⩽ s) ⩽ Cs Calculations are now straightforward:

P(|Γx| ⩽ 2t) = P(∑_{j=1}^{N} f_{j}^{2} ⩽ 4t^{2}N)

= P(N − ∑_{j=1}^{N} f_{j}^{2}/4t^{2} ⩾ 0)

⩽ E exp(N − ∑_{j=1}^{N} f_{j}^{2}/4t^{2})
= (eE exp(−f_{1}^{2}/4t^{2}))^{N}
= e^{N} (∫_{0}^{1} P(exp(−f_{1}^{2}/4t^{2}) > s)ds)^{N}
= e^{N} (∫_{0}^{1} P(f_{1} ⩽ 2t\sqrt{log(1/s)})ds)^{N}
⩽ e^{N} (2Ct ∫_{0}^{1} \sqrt{log(1/s)}ds)^{N}
= (Ce\sqrt{π}t)^{N}

2.2. SAMPLING CONVEX BODIES 71 And consequently

P(s_{n}(Γ) ⩽ t) ⩽ P(∥A∥ ⩾ C_{0}) + (\frac{3\sqrt{C_{0}}}{t} )^{n} (Ce\sqrt{π}t)^{N}

and thus for any ρ, we can choose t and such that the conclusion of the proposition holds.

2.3 Appendice

2.3.1 Version quasi-isométrique du théorème 2.2

J’ai pu démontrer le résultat suivant, après la rédaction et la soumission d’une version préliminaire du manuscrit.

Théorème. Pour tout ε > 0, il existe des constantes C(ε), c(ε) > 0 telles que si μ est une mesure log-concave isotrope inconditionnelle sur R^{n} et X_{1}, …, X_{N} sont i.i.d. de loi μ avec N ⩾ C(ε)n, alors avec probabilité supérieure à 1 − exp(−c(ε)n^{1/11}) on a ε-approximation de la matrice d’inertie de μ :

∥\frac{1}{N} ∑_{i=1}^{N} |X_{i}⟩⟨X_{i}| − Id∥ ⩽ ε

Le lecteur est renvoyé à [Aub2] pour une preuve.

Chapitre 3 Problèmes géométriques en théorie quantique de l’information

3.1 Introduction et présentation des résultats

3.1.1 Motivations et principales définitions

L’intrication quantique est un phénomène de la mécanique quantique dans lequel deux systèmes physiques (ou un plus grand nombre) ne peuvent pas être décrits séparément, bien qu’ils puissent être spatialement éloignés. Cela implique que les propriétés observables des différents systèmes sont corrélées. Il est par exemple possible de préparer deux particules de telle manière qu’en observant successivement chacune d’entre elles, on observe toujours qu’elles se trouvent dans le même état, mais qu’il demeure néanmoins impossible de prédire le résultat de la première observation. Lorsque deux systèmes quantiques sont ainsi intriqués, une mesure effectuée sur un des systèmes semble influencer instantanément l’état de l’autre système. L’intrication est un des phénomènes sur lesquels reposent, par exemple, la théorie quantique de l’information et la cryptographie quantique ; pour plus de détails sur ce sujet on pourra consulter [NC] ou [CG].

Rappelons brièvement le formalisme de la mécanique quantique qui nous sera utile. Un système quantique S est décrit par son espace d’états H = H_{S}, qui est un espace de Hilbert complexe. Un état pur du système S est un vecteur unitaire ψ de H. Il est impossible de distinguer par une mesure l’état ψ de l’état αψ, où α est un nombre complexe de module 1, il est donc plus juste d’identifier l’ensemble des états à l’espace projectif sur H, ceci sera précisé ultérieurement. On ne considérera ici que des espaces d’états de dimension finie ; l’espace H_{S} est alors identifié à C^{D}, pour un entier D. Le système quantique le plus simple correspond à un espace d’états de dimension 2 ; un tel système est appelé un qubit. En théorie quantique de l’information, c’est l’unité minimale d’information, l’analogue du bit en théorie classique de l’information. Concrètement, un qubit peut par exemple être réalisé par le spin d’un photon. On appelle parfois qudit un système dont l’espace d’états associé est C^{D}, D > 2.

Si S_{1}, …, S_{N} sont des systèmes quantiques (disjoints) d’espaces d’états respectifs H_{1}, …, H_{N}, le système S formé de la réunion S_{1} ∪ ⋯ ∪ S_{N} est complètement décrit par l’espace d’états obtenu par le produit tensoriel hilbertien des espaces d’états :

H_{S} = H_{1} ⊗_{2} ⋯ ⊗_{2} H_{N}

On écrira généralement ⊗ au lieu de ⊗_{2} pour alléger les notations. Un état pur ψ du système S est dit pur séparable si c’est un tenseur pur, c’est-à-dire s’il peut s’écrire sous la forme ψ = ψ_{1} ⊗ ⋯ ⊗ ψ_{N}, où pour i variant de 1 à N, ψ_{i} est un état pur du système S_{i}. Cela correspond au cas où il n’y a pas d’interaction entre les sous-systèmes de S. Un état pur qui n’est pas pur séparable est dit pur intriqué.

En réalité, un système quantique n’est pas en général dans un seul état, mais dans une superposition (un mélange) de plusieurs états purs ψ_{1}, …, ψ_{k}, la probabilité d’observer le système dans l’état ψ_{i} étant donnée par un nombre réel positif λ_{i}. On a bien évidemment λ_{1} + ⋯ + λ_{k} = 1. Appelons ρ cet état superposé. Ce phénomène peut être formalisé à l’aide des opérateurs de densité. Un état pur ψ est identifié à |ψ⟩⟨ψ|, qui est le projecteur orthogonal sur la droite complexe engendrée par ψ. Ainsi, l’état mélangé ρ décrit précédemment s’écrit comme

ρ = ∑_{i=1}^{k} λ_{i}|ψ_{i}⟩⟨ψ_{i}|  (3.1)

L’ensemble des états mélangés sur un espace d’états H, noté D(H) ou plus simplement D lorsqu’il n’y a pas d’ambiguïté, est ainsi défini par

D(H) = conv {|ψ⟩⟨ψ|, ψ ∈ H, |ψ| = 1}

Désormais, le mot état sous-entendra toujours état mélangé, et les états purs seront toujours identifiés aux états mélangés de rang 1. Les éléments de D sont des opérateurs autoadjoints, positifs, de trace 1 ; réciproquement ces trois conditions sont suffisantes pour pouvoir écrire une décomposition du type (3.1). On a donc la description alternative

D(H) = {ρ ∈ B_{sa}(H), ρ ⩾ 0, trρ = 1}

Remarquons que l’ensemble des points extrémaux de D coïncide avec l’ensemble des états purs. L’ensemble D est convexe, l’espace affine qu’il engendre est l’hyperplan des matrices de trace 1, noté T_{1}. Ainsi, la dimension de D(H) égale d^{2} − 1, où d est la dimension complexe de H. Notons également que |ψ⟩⟨ψ| = |ϕ⟩⟨ϕ| si et seulement s’il existe un scalaire α de module 1 tel que ψ = αϕ; rappelons que dans ce cas les états ψ et ϕ ne peuvent pas être physiquement différenciés par une observation.

Revenons au cas d’un système formé de plusieurs sous-systèmes, c’està-dire d’un espace d’états de la forme H = H_{1} ⊗ ⋯ ⊗ H_{N}. Notons d la dimension de H. Si pour i entre 1 et N, ρ_{i} est un état sur H_{i}, alors l’opérateur ρ_{1} ⊗ ⋯ ⊗ ρ_{N} est un état sur H; un tel état est appelé état produit. Si un état produit est un état pur, c’est nécessairement un produit d’états purs (car si ρ_{1} ⊗ ⋯ ⊗ ρ_{N} est de rang 1, alors ρ_{i} est de rang 1 pour tout i).

La notion de séparabilité s’étend naturellement aux états mélangés. Un état est dit séparable s’il peut s’écrire comme un mélange d’états produits. Ainsi, l’espace des états séparables est

S(H_{1} ⊗ ⋯ ⊗ H_{N}) = conv{ρ_{1} ⊗ ⋯ ⊗ ρ_{N}, ρ_{i} ∈ D(H_{i})}

On écrira S(H) ou S pour alléger les notations, cette écriture est a priori ambiguë car S(H) dépend de la décomposition tensorielle de H; cependant le contexte sera toujours clair. Un état sera dit intriqué s’il n’est pas séparable. On a l’identification canonique

B_{sa}(H_{1}) ⊗ ⋯ ⊗ B_{sa}(H_{N}) ≃ B_{sa}(H_{1} ⊗ ⋯ ⊗ H_{N})

L’espace de gauche se plonge naturellement dans l’espace de droite, et ce plongement est surjectif car on a pris soin de considérer des espaces de Hilbert complexes ; il n’est pas injectif dans le cadre réel. Cette identification permet de voir S comme un sous-ensemble de D. De plus S et D ont la même dimension (encore une fois, ce ne serait pas vrai dans le cadre d’espaces de Hilbert réels). Cela peut par exemple se déduire du résultat général suivant : si ˙⊗ désigne le produit tensoriel ponctuel, c’est-à-dire

K_{1} ˙⊗ ⋯ ˙⊗K_{N} = {x_{1} ⊗ ⋯ ⊗ x_{N}; x_{i} ∈ K_{i}},

on a

vect(K_{1} ˙⊗ ⋯ ˙⊗K_{N}) = vect(K_{1}) ⊗ ⋯ ⊗ vect(K_{N})

Si ρ est séparable, il peut s’écrire comme un mélange d’états produits, mais aussi, en écrivant chaque facteur sous la forme (3.1), comme un mélange d’états produits purs. Comme on a l’identité

|ψ_{1}⟩⟨ψ_{1}| ⊗ ⋯ ⊗ |ψ_{N}⟩⟨ψ_{N}| = |ψ_{1} ⊗ ⋯ ⊗ ψ_{N}⟩⟨ψ_{1} ⊗ ⋯ ⊗ ψ_{N}|

on en déduit la description alternative de S

S(H) = conv{|ψ⟩⟨ψ|, ψ état pur séparable sur H}

L’ensemble D est invariant par conjugaison unitaire :

∀U ∈ U(H), ∀A ∈ D(H), on a UAU^{†} ∈ D(H)

Restreinte à l’hyperplan T_{1}, cette action est irréductible. En particulier, le point Id/d, où d est la dimension complexe de H, est le seul point fixé par toutes les isométries de D, c’est donc par exemple le centre de gravité de D. Cet état central est appelé état mélangé maximal. L’ensemble S a moins d’isométries ; si H = H_{1} ⊗ ⋯ ⊗ H_{N}, S(H) est invariant par conjugaison unitaire locale, c’est-à-dire par conjugaison par des matrices unitaires de la forme U_{1} ⊗ ⋯ ⊗ U_{N}, où U_{i} est un élément de U(H_{i}). Il peut y avoir d’autres isométries de S (par exemple, si H = C^{D}⊗C^{D}, l’opération d’échange ρ_{1} ⊗ ρ_{2} ⟶ ρ_{2} ⊗ ρ_{1}), mais l’action du groupe d’isométries de S n’est pas irréductible en général. On a néanmoins le résultat suivant :

Lemme 18. Le seul point fixé par toutes les isométries de S est l’état mélangé maximal Id/d. C’est donc en particulier le centre de gravité de S.

Démonstration. Soit un état ρ fixé par toutes les isométries de S, en particulier par conjugaison par toutes les matrices unitaires locales. On peut décomposer ρ comme

ρ = ∑_{j=1}^{k} λ_{j}ρ_{1}^{j} ⊗ ⋯ ⊗ ρ_{N}^{j}

où ρ_{i}^{j} est un état sur H_{i}. Soit U une matrice unitaire locale aléatoire, c’està-dire de la forme U = U_{1} ⊗ ⋯ ⊗ U_{N}, où U_{i} est distribuée selon la mesure de Haar sur U(H_{i}). Moyennons ρ sous la conjugaison par U :

E_{U}UρU^{†} = ∑_{j=1}^{k} λ_{j}E_{U_{1},...,U_{N}} (U_{1}ρ_{1}^{j}U_{1}^{†}) ⊗ ⋯ ⊗ (U_{N}ρ_{N}^{j}U_{N}^{†})

= ∑_{j=1}^{k} λ_{j}(E_{U_{1}}U_{1}ρ_{1}^{j}U_{1}^{†}) ⊗ ⋯ ⊗ (E_{U_{N}} U_{N}ρ_{N}^{j}U_{N}^{†})
= Id/d

Pour obtenir la dernière égalité, on a utilisé le fait que E_{U_{i}}U_{i}AU_{i}^{†} = tr(A)Id/d_{i} pour toute matrice A de B(H_{i}), où d_{i} est la dimension de H_{i}. Cette formule découle de l’observation suivante : comme la mesure de Haar est invariante par translation, l’application A → E_{U_{i}}U_{i}AU_{i} est invariante par conjugaison unitaire et donc E_{U_{i}}U_{i}AU_{i} est toujours un multiple de l’identité. Le coefficient multiplicatif est obtenu en remarquant que la conjugaison unitaire préserve la trace.

3.1.2 Estimation de certains paramètres géométriques liés à la séparabilité et à l’intrication

Il est important de savoir lequel des deux phénomènes prévaut : séparabilité ou intrication ? D’un point de vue géométrique, cette question peut prendre plusieurs formes, parmi lesquelles

(a) Calculer la distance géométrique entre D et S, c’est-à-dire déterminer le plus petit nombre K tel que

D − Id/d ⊂ K(S − Id/d)

Comme D et S ont même dimension, un tel nombre K existe nécessairement.

(b) Déterminer le rayon r de la plus grande boule contenue dans S, au sens de la norme Hilbert–Schmidt. Par le lemme 18, une telle boule peut être choisie centrée en l’état mélangé maximal Id/d. Le nombre r est appelé rayon interne de S.

(c) Comparer le volume de S et de D, le volume étant mesuré au sens de la mesure de Lebesgue induite par le produit scalaire de Hilbert–Schmidt.

Ces trois questions ont été posées à plusieurs reprises dans des articles de théorie quantique de l’information, par exemple [HHH2, GB1, GB2, GB3, RMNDMC]. Quelques résultats étaient connus avant nos travaux. Dans le cas d’un système homogène, formé de N particules de dimension D, l’espace d’états est H = (C^{D})^{⊗N} et sa dimension est notée d = D^{N}

(a) En ce qui concerne la distance géométrique, on a les estimations suivantes [RMNDMC, GB3]

D^{N−1} ⩽ K ⩽ D^{N/2+1}(2D − 1)^{N/2−1}

Même dans le cas le plus simple, celui des qubits (D = 2), la borne supérieure et la borne inférieure ne sont pas du même ordre de grandeur :

\frac{1}{2}d ⩽ K_{qubits} ⩽ \frac{2}{3}6^{N/2} = \frac{2}{3}d^{1.292...}

(b) Barnum et Gurvits ont montré dans [GB3] que

r ⩾ \frac{1}{D^{N/2+1}(2D − 1)^{N/2−1}}

Dans le cas des qubits, ils ont également obtenu une légère amélioration :

r_{qubits} ⩾ τ_{N}6^{−N/2} = τ_{N}d^{−1.292...}

pour une suite (τ_{N}) explicite vérifiant 1 < τ_{N} < \sqrt{3} et lim_{N→∞} τ_{N} = \sqrt{3}.

(c) Essentiellement rien n’était su à propos du volume.

Tout d’abord, nous montrons qu’il est possible de simplifier l’approche de Gurvits et Barnum dans le cas des qubits et de remplacer τ_{N} par \sqrt{3}.

Théorème 3.1. L’ensemble S((C^{2})^{⊗N}) contient une boule Hilbert–Schmidt de rayon \sqrt{3} 6^{−N/2}, centrée en l’état mélangé maximal Id/2^{n}. Ce résultat est donc une minoration du rayon interne de S

r_{qubits} ⩾ \sqrt{3} 6^{−N/2} = \sqrt{3} d^{−1.292...}

La preuve du théorème est donnée dans l’appendice 3.3.1. En appliquant des idées de géométrie des convexes, notamment une procédure de symétrisation et l’introduction de la largeur moyenne, qui dans ce cas peut être estimée, nous obtenons également les résultats ci-après, qui prennent tout leur sens lorsque l’on considère des systèmes suffisamment grands. En ce qui concerne le volume, la situation est sensiblement différente selon que l’on considère un système formé d’un petit nombre de gros sous-systèmes, ou d’un grand nombre de petits sous-systèmes. Le fait remarquable est que dans le second cas, il est nécessaire de changer de structure euclidienne pour pouvoir obtenir l’ordre de grandeur du volume. Plus précisément, on a les théorèmes suivants :

Théorème 3.2 (Petit nombre de gros sous-systèmes). Il existe des constantes universelles C, c > 0 telles que, pour tout D, N ⩾ 2,

\frac{c^{N}}{d^{1/2−1/2N}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C(N log N)^{1/2}}{d^{1/2−1/2N}}

Théorème 3.3 (Grand nombre de petits sous-systèmes). Il existe des constantes universelles C′, c′ > 0 telles que, pour tout D, N ⩾ 2,

\frac{c′}{d^{1/2+α_{D}}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C′(DN log N)^{1/2}}{d^{1/2+α_{D}}}

où

α_{D} := \frac{1}{2} log_{D}(1 + \frac{1}{D}) − \frac{1}{2D^{2}} log_{D}(D + 1)

Le cas des qubits (D = 2) a été obtenu par Szarek dans un article antérieur ([Sza]). Nos preuves se trouvent dans la partie suivante. Le théorème 3.3 est celui qui est le plus intéressant du point de vue de l’informatique quantique. Par exemple, dans le cas des qubits cela donne

\frac{c′}{d^{0.594...}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C′\sqrt{log d log log d}}{d^{0.594...}}  (3.2)

La double inégalité ainsi obtenue est précise à l’échelle des puissances de d; les facteurs logarithmiques parasites étant négligeables (la méthode utilisée rend inévitable l’apparition de tels facteurs). Il est de plus possible d’avoir des estimations raisonnables concernant les différentes constantes impliquées dans ces théorèmes.

Il est possible de déduire directement de la borne supérieure de (3.2) une borne supérieure pour le rayon interne de S. En effet le rayon interne de S est majoré par la quantité

(\frac{vol(S)}{vol(B_{HS})})^{1/n}

appelée rayon volumique de S. Le volume de D est connu (une formule exacte est obtenue dans [ŻS], et il peut aussi être estimé par des moyens plus élémentaires, voir la formule (3.8) dans la partie suivante), et le rayon volumique de D est de l’ordre de 1/\sqrt{d}. Cela donne

r_{qubits} ⩽ \frac{C log d log log d}{d^{1.094...}}

C’est un résultat intéressant car aucune borne supérieure sur le rayon interne n’était connue auparavant ; cependant la borne obtenue ne coïncide pas avec la borne inférieure du théorème 3.1. Il est en fait possible de démontrer un résultat plus précis :

Théorème 3.4 (Borne supérieure précise sur le rayon interne de S). Il existe une constante universelle C_{0} > 0 telle que, pour tout N, l’ensemble S((C^{2})^{⊗N}), ne contient pas de boule Hilbert–Schmidt de rayon

C_{0}\sqrt{N log N} 6^{−N/2}.

Rappelons que le théorème 3.1 dit exactement que S((C^{2})^{⊗N}) contient une boule Hilbert–Schmidt de rayon \sqrt{3} 6^{−N/2}. Le rayon interne de l’ensemble des états séparables est donc connu, à un facteur logarithmique près, dans le cas des qubits. Il est possible d’en déduire directement un résultat analogue pour des qudits (D > 2), mais dans ce cas la borne supérieure ne coïncide pas avec la borne inférieure de Gurvits et Barnum ([GB3])

Théorème 3.4’. Il existe une constante universelle C_{0} > 0 telle que, pour tout N et pour tout D ⩾ 2, l’ensemble S((C^{D})^{⊗N}) ne contient pas de boule Hilbert–Schmidt de rayon

C_{0}\sqrt{N log N} (\frac{3}{2}D^{2})^{−N/2}

La preuve de ce corollaire se trouve dans l’appendice 3.3.2.

3.1.3 Faiblesse asymptotique du critère de Peres

Le théorème 3.2 est un résultat global, au sens où il ne permet pas de dire quelque chose sur un état particulier. Or il est important de pouvoir déterminer si un état donné est séparable ou intriqué, et cette question est en général complexe. Dans le cas d’un système bipartite, il existe néanmoins un critère simple, appelé critère de Peres, qui est une condition nécessaire de séparabilité. Fixons un espace d’états H = C^{D} ⊗ C^{D}, ainsi qu’une base de C^{D}. Si un élément A de B_{sa}(H) peut s’écrire comme un opérateur produit A_{1} ⊗ A_{2}, avec A_{i} ∈ B_{sa}(C^{D}), on définit la transposition partielle de A (par rapport au premier sous-système) par

T (A) = A_{1}^{t} ⊗ A_{2},

où A → A^{t} est l’opération de transposition dans B_{sa}(C^{D}), pour la base choisie. L’opérateur T, défini uniquement pour les tenseurs purs, peut s’étendre de manière unique en un opérateur linéaire défini sur tout B_{sa}(H). Si ρ est un état, alors T ρ est un opérateur autoadjoint de trace 1. Si de plus T ρ est positif (c’est-à-dire si T ρ est un état), on dit que ρ est p.p.t. (transposé partiel positif). Remarquons que si T ρ dépend du choix de la base, ce n’est pas le cas de ses valeurs propres, et la notion de p.p.t. est donc intrinsèque. On peut aussi définir la transposition partielle par rapport au deuxième sous-système, mais la notion de p.p.t. obtenue est encore la même. L’observation de Peres est simplement le fait que tout état séparable est p.p.t.. Si l’on note PPT l’ensemble des états p.p.t., on a les inclusions

S ⊂ PPT ⊂ D

On sait, d’après le théorème 3.2, que l’ensemble S a un volume asymptotiquement beaucoup plus petit que celui de D. Qu’en est-il de l’ensemble PPT ? La réponse est donnée par le théorème suivant :

Théorème 3.5 (Faiblesse asymptotique du critère de Peres). Il existe une constante universelle c_{0} > 0 telle que pour tout système bipartite (H = C^{D} ⊗ C^{D}),

c_{0} ⩽ (\frac{vol(PPT)}{vol(D)})^{1/n}

Ainsi, lorsque D est suffisamment grand, le volume de PPT est très proche de celui de D, et donc beaucoup plus grand que celui de S. Pour deux gros systèmes, un état p.p.t. typique est en fait intriqué ! Le critère de Peres devient de moins en moins efficace pour détecter la séparabilité lorsque la dimension augmente.

3.2 Tensor product of convex sets and the volume of separable states on N qudits

This note deals with estimating the volume of the set of separable mixed quantum states when the dimension of the state space grows to infinity. This has been studied recently for qubits; here we consider larger particles. We also show that the partial transpose criterion becomes weaker when the dimension increases, and that the lower bound 6^{−N/2} on the (Hilbert– Schmidt) inradius of the set of separable states on N qubits obtained recently by Gurvits and Barnum is essentially optimal. We employ standard tools of classical convexity, high-dimensional probability and geometry of Banach spaces. One relatively novel point is a formal introduction of the concept of projective tensor products of convex bodies, and an initial study of this concept.

3.2.1 Introduction and summary of results

An important problem in quantum information theory is to estimate quantitatively some parameters related to entanglement. This phenomenon is thought to be at the heart of quantum information processing while, on the other hand, its experimental creation and handling are still challenging. The question of determining the volume of the set of separable states has been asked for example in [ŻHSL, HHH2],where we refer the reader for background and motivation. In this paper we obtain estimates which are meaningful when the dimension of the state space is “not too small,” and which are asymptotically tight as that dimension tends to infinity. The effective radius in the sense of volume (that is, the radius of the Euclidean ball of the same volume, also referred to as volume radius) of the set of separable states for qubits has been determined (precisely on the scale of powers of the dimension) in [Sza]. Here we apply the same techniques from asymptotic convex geometry to deal with more general particles.

3.2. SEPARABLE STATES ON N QUDITS 83

We now recall the mathematical framework and introduce some notation. The state space is a complex Hilbert space H = C^{D_{1}} ⊗ ⋯ ⊗ C^{D_{N}}. We write d = D_{1} … D_{N} for the dimension of H. This Hilbert space allows to describe quantum interactions between N particles; D_{j} = 2 corresponds to qubits and D_{j} = 3 to qutrits. We write B(H) for the space (or C^{∗}-algebra) of linear maps from H into itself, and B_{sa}(H) for the (real linear) subspace of selfadjoint operators. The space B(H) is endowed with the Hilbert–Schmidt, or Frobenius, scalar product defined by ⟨A, B⟩_{HS} := trA^{†}B (= ∑_{i,j=1}^{d} \overline{A_{ij}}B_{ij} if A and B are represented as matrices). A state on B(H) (which we will abbreviate to “a state on H”) can be represented as a positive (semi-definite) trace one element of B_{sa}(H). A state is said to be separable if it can be written as a convex combination of tensor products of N states, otherwise it is called entangled. That is, the set of states (also called in this context density operators or density matrices) is

D = D(H) := {ρ ∈ B_{sa}(H), ρ ⩾ 0, trρ = 1},

and the set of separable states is

S = S(H) := conv{ρ_{1} ⊗ ⋯ ⊗ ρ_{N}, ρ_{j} ∈ D(C^{D_{j}})}.

The notation S(H) is in principle ambiguous: separability of a state on B(H) is not an intrinsic property of the Hilbert space H or of the algebra B(H); it depends on the particular decomposition of H as a tensor product of (smaller) Hilbert spaces. However, this will not be an issue here since our study focuses on fixed decompositions.

D and S are convex subsets of B_{sa}(H) of (real) dimension n := d^{2} −1. We write T_{1} for the affine subspace generated by D (or S); it is the hyperplane of trace one matrices. The space B_{sa}(H) inherits a (real) Euclidean structure from the scalar product ⟨·, ·⟩_{HS}. The corresponding unit ball will be denoted by B_{HS} (or B_{HS}^{d}). We denote by vol the corresponding d^{2}-dimensional Lebesgue volume on B_{sa}(H); we will also write vol for the n-dimensional volume induced on T_{1}.

We shall concentrate on the special case when all the subsystems are identical, i.e., D_{1} = ⋯ = D_{N} = D. Our techniques also apply to general state spaces, but formulae which fit all the situations would be more cumbersome than for this “homogeneous” case. If H = (C^{D})^{⊗N}, there are two “regular” ways to make its dimension tend to infinity: either N ⩾ 2 is fixed and D tends to infinity, or D ⩾ 2 is fixed and N goes to infinity (as in [Sza] for D = 2). Surprisingly, it turns out that in the latter case the natural Euclidean structure is not the one given by the Hilbert–Schmidt scalar product, but rather a mixture of that product with a Killing-type form. Our goal is to prove the following theorems (recall that we work with H = (C^{D})^{⊗N} and that d = dim H = D^{N}, N = log_{D} d and n = dim D = d^{2} − 1 = D^{2N} − 1).

Theorem 3.2 (Small number of large subsystems). There exist universal constants C, c > 0 such that, for all D, N ⩾ 2,

\frac{c^{N}}{d^{1/2−1/2N}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C(N log N)^{1/2}}{d^{1/2−1/2N}}

We point out that considering the nth root of the ratio of volumes is natural from the geometric point of view: if the two sets had been Euclidean balls, we would have obtained the ratio of their radii, and so we are comparing the volume radii of S and D (see section 3.2.2 for additional geometric background).

Theorem 3.3 (Large number of small subsystems). There exist universal constants C′, c′ > 0 such that, for all D, N ⩾ 2,

\frac{c′}{d^{1/2+α_{D}}} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ \frac{C′(DN log N)^{1/2}}{d^{1/2+α_{D}}}

where

α_{D} := \frac{1}{2} log_{D}(1 + \frac{1}{D}) − \frac{1}{2D^{2}} log_{D}(D + 1)

For illustration, we list approximate values of α_{D} for small D’s: α_{2} ≈ 0.09436, α_{3} ≈ 0.06083, α_{4} ≈ 0.04420. Note that α_{D} is a positive decreasing function of D, asymptotically equivalent to 1/(2D log D).

Theorem 3.2 asserts that, as D → ∞, the ratio of the volume radii of S and D is of order d^{−(1/2−1/2N)} = D^{−(N−1)/2} (up to a multiplicative constant depending only on N). Theorem 3.3 is slightly less definite: while, for fixed D, the ratio in question is determined precisely on the scale of the powers of d, there are some (possibly parasitic) logarithmic factors. [We recall again that N = log_{D} d = log d/ log D.] We point out that, apart from the value of the numerical constant, the upper estimate in Theorem 3.3 is always sharper than that in Theorem 3.2. However, the gain α_{D} in the exponent is negligible if N is fixed and D → ∞.

It is possible to give reasonable estimates on the constants appearing in both theorems. One can, for example, take c = 1/\sqrt{6}, c′ = 0.3 and C = C′ = 6. It is also possible to establish a tighter asymptotic behavior of these constants (relevant if one is only interested in large values of d): one can have C and C′ tending to \sqrt{2} e^{1/4} and c′ tending to e^{3/4}/\sqrt{2π} as D or N tend to infinity. Finally, sharper estimates for specific dimensions can be obtained by using known results on, among others, efficient spherical codes; see Appendix G of [Sza] for an example of such calculation.

The case D = 2 of Theorem 3.3 was treated in detail in [Sza]. In this note we present additional ingredients required to deal with the general case. We point out that the (relatively) easy part is the estimation of vol(D), which of course does not depend on the tensor structure of H. It has been shown in [ŻS] that

vol(D) = \sqrt{d} (2π)^{d(d−1)/2} \frac{Γ(1) … Γ(d)}{Γ(d^{2})}  (3.3)

A direct calculation then yields that the volume radius of D behaves as e^{−1/4}d^{−1/2}(1 + O(1/d)) as d → ∞. It is also possible (and easy) to estimate the volume radius of D using techniques with the same flavor as the ones presented here. For example, it was shown in [Sza] that for any value of d that radius is contained between d^{−1/2}/2 and 2d^{−1/2} (see section 3.2.2 below). Finally, the fact that the volume radius in question is of order d^{−1/2} as d → ∞ follows from an early paper [ST].

The ratio of Euclidean volumes is not the only geometric parameter which is of interest here. An arguably more relevant parameter would be its analogue for the so-called Bures volume, which may be a more appropriate measure of size in the present context (see [BC]). Another quantity with physical significance is the largest number ε = ε(H) below which the mixture (1 − ε)Id/d + ερ is separable for any state ρ. Of course it is possible to derive from volume estimates an upper bound on this ε(H), but this bound is weaker that what is already known ([RMNDMC, GB2, GB3]). Still, the knowledge of the volume radii yields additional information also in this context: for ε ≫ (vol(S)/vol(D))^{1/ dim D}, the mixture (1 − ε)Id/d + ερ is entangled for “most of” ρ ∈ D, and not just for very special states as those constructed in [RMNDMC, GB2, GB3]. Another quantity that has been studied in [GB1, GB2, GB3] is the inradius of S, which is the radius of the inscribed Euclidean ball in S (here we assume that the balls are centered at Id/d, which is the natural center of both S and D). It seems that, prior to results on qubits in [Sza], the only upper bound which was known on the inradius of S was the inradius of D, or 1/\sqrt{d(d − 1)}. [A remarkable fact discovered in [GB1] is that the two inradii coincide when N = 2.] Theorem 3.3 improves on this for large N giving, up to logarithmic factors, the upper bound 1/d^{1+α_{D}}. Moreover, the techniques developed in [Sza] and in the present paper allow to tighten this bound substantially. We present the following sample result.

Theorem 3.4 (Tight upper bounds on the inradii of S and Σ). There exists an absolute constant C_{0} > 0 such that, for any N, the set Σ((C^{2})^{⊗N}), and hence also S((C^{2})^{⊗N}), does not contain any Hilbert–Schmidt ball of radius C_{0}\sqrt{N log N} 6^{−N/2}.

For comparison, let us cite the lower bound of 6^{−N/2} on the inradius of the set Σ noted in [Sza], Appendix H, and a similar lower bound on the a priori smaller inradius of S shown subsequently in [GB3]. This means that, at least for N qubits, the inradii of S and of Σ have been determined up to a multiplicative factor which is logarithmic in the dimension of the state space. The argument we present can be generalized to other values of D, leading to an upper bound for the inradii of Σ((C^{D})^{⊗N}) and S((C^{D})^{⊗N}) which is (D(D +1))^{−N/2} (again, up to a logarithmic factor). For the inradius of the set Σ this bound is essentially sharp. However, for D > 2, the value (D(D + 1))^{−N/2} does not coincide with the lower bound for the inradius of S((C^{2})^{⊗N}) that was found in [GB3] and which is of the form O((D(2D − 1))^{−N/2}). As was noticed in [GB3], a better upper bound for D > 2 is derived from our upper bound for D = 2 and is (up to a logarithmic factor) of the form (1.5 × D^{2})^{−N/2}. However, this still leaves a gap between the upper and lower estimates which is exponential in N (as N → ∞). A similar discussion of the bilateral case (N = 2, D → ∞) can be found in the Remark at the end of section 3.2.3.

Theorem 3.2 above means that typical (as measured by the standard volume) high-dimensional bipartite states are entangled. This statement is of global nature, and is therefore not helpful when one faces a given state and has to decide about its separability. In turn, lower bounds for the inradii of sets Σ, or for the quantity ε(H) mentioned above provide a sufficient condition for separability which, while very useful in some contexts, is conclusive for only a very small fraction of separable states. A very simple and efficient (at least in small dimensions) necessary condition is the so-called Peres partial transpose criterion ([Per]). We briefly recall what partial transposition is, say when the state space is H = C^{D} ⊗C^{D}. Fix a basis (e_{1}, …, e_{D}) of C^{D}, for example the canonical basis. Any state ρ on H can be uniquely expressed as

ρ = ∑_{i,j,α,β=1}^{D} ρ_{iα,jβ}|e_{i} ⊗ e_{α}⟩⟨e_{j} ⊗ e_{β}|

We then consider T ρ, the partial transpose of ρ (with respect to the first subsystem), defined by the formula

(T ρ)_{iα,jβ} = ρ_{jα,iβ}

One checks that T ρ is also an Hermitian operator of trace one which, however, is not necessarily positive. Following [HHH2], we write PPT (Positive Partial Transpose) for the set of states ρ for which T ρ is also positive. Note that while T ρ depends on the choice of the basis, its eigenvalues do not; so the set PPT is basis-independent. The Peres criterion simply reads: any separable state has a positive partial transpose. In other words, we have the inclusions S ⊂ PPT ⊂ D. An natural question (asked for example in [HHH2]) is then: what is the volume of PPT? Is it close to the volume of S, or rather to the volume of D? The following theorem answers the latter question.

Theorem 3.5 (Asymptotic weakness of PPT criterion). There exists an absolute constant c_{0} > 0 such that for any bipartite system (H = C^{D}⊗C^{D})

c_{0} ⩽ (\frac{vol(PPT)}{vol(D)})^{1/n}

An immediate corollary to Theorems 3.2 and 3.5 is that, for large D, the volume of PPT states is much bigger than the volume of separable states. This means that a typical high-dimensional PPT state is entangled, and thus that Peres criterion becomes weaker and weaker as the dimension increases. Theorem 3.5 is just a sample result; similar analysis may be performed for other bipartite and multipartite systems. On the other hand, it is quite conceivable that the quantity from Theorem 3.5 admits a nontrivial (i.e., < 1, independent of D) upper bound, even in the case of bipartite systems.

3.2.2 Preliminaries about convex bodies

In this section we list some known (or elementary) facts from convexity theory that will be needed in the sequel. A convex body is a convex compact subset of R^{n} (or of C^{m} identified with R^{2m}, or of an affine subspace of R^{n}) with nonempty interior. We will say that a convex body K is symmetric if it is symmetric with respect to the origin (i.e., K = −K). To a convex body K ⊂ R^{n} containing the origin in its interior one can canonically associate ∥ · ∥_{K}, the gauge of K, by setting, for x ∈ R^{n}, ∥x∥_{K} := inf{λ : x ∈ λK}. If K is symmetric, ∥ · ∥_{K} is the norm for which K is the unit ball. If K and L are two convex bodies in R^{n} which contain the origin in their interior, we define the geometric distance between K and L as the product αβ, where α (resp. β) is the smallest number for which K ⊂ αL (resp. L ⊂ βK). This quantifies how the shapes of K and L differ.

The Urysohn inequality

Let K ⊂ R^{n} be a convex body and u ∈ S^{n−1} be a unit vector. The width of K in the direction u is

w(K, u) := max_{x∈K}⟨u, x⟩

Geometrically, w(K, u) is the distance from the origin to the hyperplane tangent to K in the direction u. The mean width of K is simply the mean of the widths in all directions:

w(K) := ∫_{S^{n−1}} w(K, u)dσ(u)

where σ is the Lebesgue measure on the sphere, normalized so that σ(S^{n−1}) = 1. The classical Urysohn inequality, which is of isoperimetric flavor, states that among all convex bodies of given volume, the Euclidean ball has the minimal mean width. It can be written as follows (see, e.g., Appendix A of [Sza] for a proof)

(\frac{vol(K)}{vol(B_{n}^{2})})^{\frac{1}{n}} ⩽ w(K),

where B_{2}^{n} is the n-dimensional Euclidean unit ball. The quantity on the left-hand side equals the radius of the Euclidean ball which has the same volume as K and, as we mentioned earlier, is sometimes called the volume radius of K; we will denote it vrad(K). We will use the Urysohn inequality to estimate, among others, the volume radius of Σ, which is the quantity we are interested in. It is often more convenient to rewrite the inequality above by expressing the mean width via a Gaussian integral (rather than an integral over the sphere):

vrad(K) ⩽ \frac{1}{γ_{n}} E max_{x∈K}⟨x, G⟩,

where G is a N (0, Id_{n}) Gaussian vector, E is the expectation with respect to G and γ_{n} := \sqrt{2}Γ(\frac{n+1}{2})/Γ(\frac{n}{2}) is a constant which is close to \sqrt{n}. The identity w(K) = γ_{n}^{−1}E max_{x∈K}⟨x, G⟩ is checked by passing to polar coordinates. We will occasionally call E max_{x∈K}⟨x, G⟩ the Gaussian mean width of K and denote it w_{G}(K).

A special situation is when the body K is a polytope with v vertices on the unit sphere. In this case it is well-known (see Proposition 1.1.3. in [Tal] for a nice proof) that the expectation w_{G}(K) is smaller than \sqrt{2 log v}. A somewhat more complicated argument based on another proof ([Fer], Lemme 0.6.2) and supplemented by numerics shows that the same estimate works for a symmetric polytope with 2v vertices on the unit sphere (or just in the unit ball) provided v > 1 (see Appendix 3.3.3). We eventually obtain that, for v > 1 points (x_{i})_{i=1}^{v} in the unit ball,

vrad(conv\{±x_{i}\}_{i=1}^{v}) ⩽ w(conv\{±x_{i}\}_{i=1}^{v}) < \frac{1}{γ_{n}} \sqrt{2 log v}.  (3.4)

Note that since γ_{n} = w_{G}(B_{2}^{n}) ∼ \sqrt{n}, the quantity on the right will be small as long as log v ≪ n.

Symmetrization and the Rogers–Shephard inequality

Let H be an affine hyperplane in R^{n+1}, not containing the origin, and let W be a convex body in H. Consider the symmetrization Ω of W, defined by Ω := conv(W ∪ −W). This procedure is quite natural in the framework of convex bodies, since much more information is available about centrally symmetric convex bodies as opposed to general ones. In particular, Ω is the unit ball with respect to the norm ∥.∥_{Ω}. If h > 0 is the distance between H and the origin, then we have the following inequalities

2h vol(W) ⩽ vol(Ω) ⩽ 2h \frac{2^{n}}{n + 1}vol(W).  (3.5)

The left hand inequality is an immediate consequence of the Brunn–Minkowski inequality ([Gar]), and is an equality if the body W is centrally symmetric. The right hand inequality is the Rogers–Shephard inequality ([RS]) and equality is achieved when W is a simplex. The factor \frac{2^{n}}{n+1} may appear large, but we point out that its nth root, which is more relevant here, is smaller than 2.

We now consider symmetric versions of D and S, namely Δ := conv(D ∪ −D) and Σ := conv(S ∪ −S); then n = d^{2} − 1. The set Δ is just the Hermitian part of the unit ball of the usual Schatten class of trace class operators. In other words Δ = {A ∈ B_{sa}(H), ∥A∥_{1} ⩽ 1}, where ∥A∥_{1} is the trace class norm, i.e., the sum of singular values of A or, in our Hermitian setting, of the absolute values of the eigenvalues of A. [See section 3.2.2 for the functional-analytic interpretation of Σ.] The inequalities (3.5) imply now

\frac{1}{2} (\frac{vol(Σ)}{vol(Δ)})^{1/n} ⩽ (\frac{vol(S)}{vol(D)})^{1/n} ⩽ 2 (\frac{vol(Σ)}{vol(Δ)})^{1/n}  (3.6)

Therefore, we lose only a factor of 2 when passing from the ratio of the volume radii of S and D to the ratio of the volume radii of Σ and Δ. To be precise, the exponent obtained for the symmetrized bodies is 1/n whereas it should be 1/d^{2} (which is the reciprocal of the dimension of Δ and Σ), but this is not at all an issue. First, we can a posteriori change the exponent, this will at most slightly affect the constants. Second, the extra n+1 in (3.5) ensures that no modification of the constants is actually needed (see [Sza], Appendix C, for a precise general statement in this direction).

For future reference we recall here the estimates from [Sza] for the volume radius of D (cited in the Introduction), for the volume radius of Δ, and for the mean widths of these sets.

\frac{1}{\sqrt{d}} ⩽ vrad(Δ) = (\frac{vol(Δ)}{vol(B_{2}^{d^{2}})})^{1/d^{2}} ⩽ w(Δ) ⩽ \frac{2}{\sqrt{d}}  (3.7)

\frac{1}{2\sqrt{d}} ⩽ vrad(D) ⩽ w(D) ⩽ \frac{2}{\sqrt{d}}  (3.8)

While, as we mentioned in the Introduction, both a closed expression for vrad(D) and its precise asymptotic behavior (as the dimension increases) are known, and while presumably similar information about vrad(Δ) may be obtained via the methods of [ŻS], the compact and transparent inequalities from (3.7) and (3.8) are sufficient for our asymptotic results. Moreover, having upper bounds for the larger parameter w(·) will provide us with additional flexibility.

Ellipsoids associated to convex bodies

An ellipsoid is an affine image of the unit ball B_{2}^{n}. There is a one-to-one correspondence between symmetric ellipsoids and scalar products (or Euclidean structures). Indeed, if E = T B_{2}^{n}, with T a linear map, then E is the unit ball associated to the scalar product ⟨x, y⟩_{E} := ⟨T^{−1}x, T^{−1}y⟩. If K is a convex body in R^{n}, its polar body, denoted K^{∘}, is defined by K^{∘} = {x ∈ R^{n}, ∀y ∈ K, ⟨x, y⟩ ⩽ 1}. If 0 belongs to the interior of K, K^{∘} is also a convex body (if not, it fails to be bounded). We point out that ∥x∥_{K^{∘}} = max_{y∈K}⟨x, y⟩ and that the restriction of the gauge ∥ · ∥_{K^{∘}} to the sphere coincides with w(K, ·), the width function of K defined in section 3.2.2. We further note that the polar of a symmetric ellipsoid is again a symmetric ellipsoid. The following definition is useful for our purposes.

Definition: If K is a convex body in R^{n}, a John resolution of identity associated to K is a finite family (x_{i}, c_{i})_{i∈I}, where x_{i} belong to ∂K ∩ S^{n−1} (if K ⊂ B_{2}^{n} or B_{2}^{n} ⊂ K, these are contact points of K with the sphere) and c_{i} are positive numbers, such that

1. ∑ c_{i}x_{i} = 0

2. ∀y ∈ R^{n}, y = ∑ c_{i}⟨x_{i}, y⟩x_{i}

Condition 2 can be rephrased using Dirac notation as ∑ c_{i}|x_{i}⟩⟨x_{i}| = Id_{n}. Taking trace both sides, we see that necessarily ∑ c_{i} = n. We recall the following result due to John

Proposition 3.1 (John’s theorem). Let K be a convex body in R^{n}. Then there exists a unique ellipsoid of minimal volume containing K, called Löwner ellipsoid, which we denote Löw(K). Similarly, there exists a unique ellipsoid of maximal volume contained in K, called John ellipsoid, which we denote John(K). Moreover, the equality Löw(K) = B_{2}^{n} holds if and only if K ⊂ B_{2}^{n} and there exists a John resolution of identity associated to K. Similarly, the equality John(K) = B_{2}^{n} holds if and only if B_{2}^{n} ⊂ K and there exists a John resolution of identity associated to K.

For a proof of this theorem, see [Bal]. These ellipsoids are affine invariants: for any affine map T, we have John(T K) = T John(K) and Löw(T K) = T Löw(K). In the symmetric case (the one we mostly deal with in the sequel), John and Löwner ellipsoids are also symmetric and dual to each other with respect to polarity. More precisely, if K is symmetric, we have John(K^{∘}) = Löw(K)^{∘} and Löw(K^{∘}) = John(K)^{∘}; this is a consequence of the fact that for any symmetric ellipsoid E, we have vol(E^{∘}) = vol(B_{2}^{n})^{2}/vol(E). It is therefore immediate to pass from the statement about John ellipsoid to the statement about Löwner ellipsoid (actually the theorem is usually stated for the John ellipsoid only).

Tensor products of convex bodies

If K and K′ are convex bodies, respectively in R^{n} and R^{n′}, their projective tensor product is the convex body K ˆ⊗K′ in R^{n} ⊗ R^{n′} ∼ R^{nn′} defined as follows

K ˆ⊗K′ = conv{x ⊗ x′, x ∈ K, x′ ∈ K′}.

This terminology is motivated by the fact that when K and K′ are unit balls with respect to some norms, the set K ˆ⊗K′ is the unit ball of the corresponding projective tensor product norm on R^{n} ⊗ R^{n′}. The relevance of the notion to our discussion is obvious: the set of separable states is the projective tensor product of sets of states on factor spaces; more precisely, if H = H_{1} ⊗ H_{2}, then S(H) = D(H_{1}) ˆ⊗D(H_{2}). It is easy to see that the operation ˆ⊗ commutes with symmetrizations: if K̃ = conv(K ∪ −K) and K̃′ = conv(K′ ∪−K′), then conv(K ˆ⊗K′, −K ˆ⊗K′) = K̃ ˆ⊗K̃′. It follows that, in our notation, Σ(H) = Δ(H_{1}) ˆ⊗Δ(H_{2}). Since, as was pointed out in section 3.2.2, Δ is the unit ball in the trace class norm, Σ(H) is the unit ball of the projective tensor product of the spaces B_{sa}(H_{k}), k = 1, 2, each endowed with the trace class norm.

The definition of K ˆ⊗K′ — similarly as other definitions, comments and lemmas of this section — immediately generalizes to tensor products of any finite number of factors. However, for the sake of transparency, we shall concentrate in this section on the case of two bodies. We also point out that while the definition appears to be well-adapted to 0-symmetric sets, cones and linear maps as morphisms (this is used in the proof of Lemma 19 below and, later, in the first paragraph of section 5), the projective tensor product is not invariant under affine maps. We refer to [Sve], Chapter 2, for a discussion of related categorical issues.

If E = SB_{2}^{n} and E′ = S′B_{2}^{n′} are two ellipsoids, respectively in R^{n} and R^{n′}, their Hilbertian tensor product is the ellipsoid E ⊗_{2} E′ := (S ⊗ S′)B_{2}^{nn′}.

This definition does not depend on the choice of S and S′. It turns out that Löwner ellipsoids behave well with respect to projective tensor product, as the following lemma shows (note that the analogous statement does not hold for the John ellipsoid).

Lemma 19. Let K ⊂ R^{n} and K′ ⊂ R^{n′} be two convex bodies. Then the Löwner ellipsoid of their projective tensor product is the Hilbertian tensor product of the respective Löwner ellipsoids.

In terms of scalar products, for every x, y in R^{n} and x′, y′ in R^{n′}, we have

⟨x ⊗ x′, y ⊗ y′⟩_{Löw(K ˆ⊗K′)} = ⟨x, y⟩_{Löw(K)}⟨x′, y′⟩_{Löw(K′)}

Proof. First suppose that Löw(K) = B_{2}^{n} and Löw(K′) = B_{2}^{n′}. By John’s theorem, there exist John resolutions of identity for K and K′, respectively (x_{i}, c_{i})_{1⩽i⩽k} and (x′_{j}, c′_{j})_{1⩽j⩽k′}. We easily check that K ˆ⊗K′ ⊂ B_{2}^{nn′} = B_{2}^{n} ⊗_{2} B_{2}^{n′}. Moreover, (x_{i} ⊗ x′_{j}, c_{i}c′_{j})_{1⩽i⩽k,1⩽j⩽k′} is also a John resolution of identity for K ˆ⊗K′. It is enough to check this on pure tensors: take y ∈ R^{n} and y′ ∈ R^{n′} and verify the two conditions

1. ∑_{i=1}^{k} ∑_{j=1}^{k′} c_{i}c′_{j}x_{i} ⊗ x′_{j} = (∑_{i=1}^{k} c_{i}x_{i}) ⊗ (∑_{j=1}^{k′} c′_{j}x′_{j}) = 0

2. ∑_{i=1}^{k} ∑_{j=1}^{k′} c_{i}c′_{j}⟨x_{i} ⊗ x′_{j}, y ⊗ y′⟩x_{i} ⊗ x′_{j} = (∑_{i=1}^{k} c_{i}⟨x_{i}, y⟩x_{i}) ⊗ (∑_{j=1}^{k′} c′_{j}⟨x′_{j}, y′⟩x′_{j}) = y ⊗ y′

For the general case, let T and T′ be linear maps such that T Löw(K) = B_{2}^{n} and T′Löw(K′) = B_{2}^{n′}. Using the elementary identities Löw(T K) = T Löw(K) and (T ⊗ T′)(K ˆ⊗K′) = (T K) ˆ⊗(T′K′), the result follows from the previous particular case.

The next “Chevet–Gordon type” lemma relates the mean widths of convex sets to that of their projective tensor product. It is most conveniently stated for the mean Gaussian width w_{G}(·) defined in section 3.2.2.

Lemma 20. Let K ⊂ B_{2}^{n} ⊂ R^{n} and K′ ⊂ B_{2}^{n′} ⊂ R^{n′} be convex bodies, one of which is the convex hull of a subset of the corresponding unit sphere. Then

w_{G}(K ˆ⊗K′) ⩽ w_{G}(K) + w_{G}(K′).

Restating the assertion of the Lemma in terms of the standard mean width gives

w(K ˆ⊗K′) ⩽ \frac{γ_{n}}{γ_{nn′}} w(K) + \frac{γ_{n′}}{γ_{nn′}} w(K′) ⩽ \frac{w(K)}{\sqrt{n′}} + \frac{w(K′)}{\sqrt{n}},

The second inequality follows from the fact that the sequence (γ_{k}/\sqrt{k}) is increasing (which can be deduced from inequalities proved in [Luk]; the fact that the coefficients on the right hand side are approximately 1/\sqrt{n′} and 1/\sqrt{n} follows from the simpler relationship γ_{k} ≈ \sqrt{k}.) We thus get seemingly strong upper bounds for mean widths and, a fortiori, for volume radii of projective tensor products of convex bodies. However, in spite of its elegance, Lemma 20 will play only rather limited role in our arguments. This is because, when iterated, it yields asymptotically worse dependence on the number of factors than the techniques employed in subsequent sections. Accordingly, its main use will be in considerations involving few factors and in ameliorating the numerical constants which appear in the statements of the Theorems. The Lemma can be shown by an argument very similar to that of section 2c of [DS], we postpone the proof to appendix 3.3.4.

Finally, let us note that if K and K′ are circled convex bodies in respective complex vector spaces (a convex body K ⊂ C^{n} is said to be circled if K = e^{iθ}K for all real θ), then K ˆ⊗K′ is circled; as was the case for symmetrizations, the operation absconv (the absolute convex hull) commutes with the projective tensor product.

3.2.3 Proof of Theorem 3.2: Small number of large subsystems

The upper bound can be obtained through a standard discretization argument. Recall that, for δ > 0, a δ-net of a set K is a subset N ⊂ K such that for each x ∈ K there exists y ∈ N whose distance to x is smaller than δ. If N ⊂ C^{D}, we write P (N) for the polytope conv{±|x⟩⟨x|}_{x∈N} ⊂ B_{sa}(C^{D}). The following elementary lemma shows that if N is a net of the unit sphere of C^{D} — which may be identified with S^{2D−1} as a metric space — then P (N) is a good approximation of Δ(C^{D}).

Lemma 21. Let δ < \sqrt{2 − \sqrt{2}} ≈ 0.765 and let N be a δ-net of the unit sphere of C^{D}. Then

(1 − 2δ^{2} + δ^{4}/2)Δ(C^{D}) ⊂ P (N) ⊂ Δ(C^{D})

Proof. The second inclusion is trivial. Let us check the first one through the corresponding dual (polar) norms

∥A∥_{P (N)^{∘}} = max_{y∈N} |⟨y|A|y⟩|

∥A∥_{Δ(C^{D})^{∘}} = ∥A∥_{op} = max_{x∈C^{D},∥x∥=1} |⟨x|A|x⟩| = max_{λ∈σ(A)} |λ|,

where ∥ · ∥_{op} is the operator norm and σ(·) is the spectrum (recall that we consider only Hermitian matrices here). We need to show that ∥A∥_{P (N)^{∘}} ≥ (1 − 2δ^{2} + δ^{4}/2)∥A∥_{op}. To this end, let A ∈ B_{sa}(C^{D}) be such that ∥A∥_{op} and the largest eigenvalue of A are both equal to 1, and let x ∈ C^{D} be a norm one vector such that Ax = x. Choose y_{0} ∈ N verifying ∥x − y_{0}∥ ⩽ δ. We claim that ⟨y_{0}|A|y_{0}⟩ ≥ 1 − 2δ^{2} + δ^{4}/2; the inequality between the norms follows then by homogeneity. The claim is easily established by writing y_{0} = y_{1} + y_{2} with y_{1} = ⟨y_{0}|x⟩x and noting that ⟨y_{1}|A|y_{1}⟩ ≥ |⟨y_{0}|x⟩|^{2} ≥ (1 − δ^{2}/2)^{2}, |⟨y_{2}|A|y_{2}⟩| ≤ ∥y_{2}∥^{2} ≤ δ^{2}(1 − δ^{2}/4) and ⟨y_{1}|A|y_{2}⟩ = 0.

Tensoring the conclusion of the preceding lemma and recalling that Δ(C^{D})^{ˆ⊗N} = Σ(H) yields an inclusion (1 − 2δ^{2} + δ^{4}/2)^{N}Σ(H) ⊂ P (N)^{ˆ⊗N}. Observe that P (N)^{ˆ⊗N} is another symmetric polytope with at most 2(#N)^{N} vertices. It is well-known (lemma 2) that for δ ⩽ 1 we can find δ-nets in S^{2D−1} of cardinality not exceeding ⩽ (1 + 2/δ)^{2D}. We thus get a bound on the volume of the polytope using the estimation (3.4).

We note for future reference that the above discussion can be carried out using other Euclidean structures, the only constraint being that the vertices of the polytope are of norm not exceeding 1. Thus, if E is any ellipsoid containing Σ(H), we obtain

(\frac{vol(Σ(H))}{vol(E)})^{1/d^{2}} ⩽ inf_{0<δ<\sqrt{2−\sqrt{2}}} \frac{\sqrt{2 log ((1 + 2/δ)^{2DN})}}{γ_{d^{2}}(1 − 2δ^{2} + δ^{4}/2)^{N}}  (3.9)

Using E = B_{HS} and, say, δ = 1/\sqrt{N log 2N} leads to an estimate

vrad(Σ(H)) = O((DN log N)^{1/2}/d)

[Indeed, for large d we have then γ_{d^{2}} ∼ d, (1 − 2δ^{2} + δ^{4}/2)^{N} ∼ 1 and log ((1 + 2/δ)^{2DN}) ∼ DN log N.] We obtain the upper bound announced in Theorem 3.2 by combining this with the lower bound on vrad(Δ(H)) given by (3.7) and with (3.6).

The lower estimate will be proved by showing that Σ(H) contains a Euclidean ball of appropriately large volume. We start with the following lemma

Lemma 22. Let K := (B_{2}^{D})^{ˆ⊗m} be the projective tensor product of m copies of the D-dimensional Euclidean ball (real or complex). Then K contains the following multiple of the Euclidean ball in (C^{D})^{⊗m} (resp., (R^{D})^{⊗m})

\frac{1}{D^{(m−1)/2}} B_{2}^{D^{m}} ⊂ K.

Proof. Let (e_{1}, …, e_{D}) be the canonical basis of C^{D}. We write an element A of (C^{D})^{⊗m} as a generalized matrix: A = (a_{i_{1}...i_{m}}) stands for

A = D ; ∑ ; i_{1}, …, i_{m} = 1 a_{i_{1}...i_{m}}e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{m}}

The norm dual to ∥ · ∥_{K} is

∥A∥_{K^{∘}} = {max \atop x^{1}, …, x^{m} ∈ B_{2}^{D}} | D ; ∑ ; i_{1}, …, i_{m} = 1 a_{i_{1}...i_{m}}x_{i_{1}}^{1} … x_{i_{m}}^{m}| (3.10)

Let us write ∥A∥_{2} for the Euclidean norm of A, i.e., ∥A∥_{2}^{2} = ∑ |a_{i_{1}...i_{m}}|^{2}. We want to show that ∀A ∈ (C^{D})^{⊗m} we have D^{−(m−1)/2}∥A∥_{2} ⩽ ∥A∥_{K^{∘}}. By homogeneity, we can assume that ∥A∥_{2} = 1. Now choose x^{1}, …, x^{m−1} randomly and independently to be uniformly distributed on the unit sphere of C^{D}. We write E for the corresponding expectation. Let X_{k}, k = 1, …, D, be the random variable obtained by summing only on the kth “hyper-slice,” that is

X_{k} = X_{k}(x^{1}, …, x^{m−1}) := D ; ∑ ; i_{1}, …, i_{m−1} = 1 a_{i_{1}...i_{m−1}k}x_{i_{1}}^{1} … x_{i_{m−1}}^{m−1}

We can easily calculate E|X_{k}|^{2} since many cancellations come from the fact that E(x_{i}^{k}\overline{x_{j}^{l}}) = \frac{1}{D}δ_{kl}δ_{ij}. We obtain

E|X_{k}|^{2} = \frac{1}{D^{m−1}} D ; ∑ ; i_{1}, …, i_{m−1} = 1 |a_{i_{1}...i_{n−1}k}|^{2}

Therefore, E(∑_{k=1}^{D} |X_{k}|^{2}) = \frac{1}{D^{m−1}} . This implies the existence of unit vectors x^{1}, …, x^{m−1} such that denoting Y_{k} := X_{k}(x^{1}, …, x^{m−1}), we have

∑_{k=1}^{D} |Y_{k}|^{2} ⩾ \frac{1}{D^{m−1}} .

Choosing these points in (3.10), we obtain

∥A∥_{K^{∘}} ⩾ max_{x^{m}∈B_{2}^{D}} ∑_{k=1}^{D} X_{k}x_{k}^{m} = (∑_{k=1}^{D} |X_{k}|^{2})^{1/2} ⩾ \frac{1}{D^{(m−1)/2}}

Remark: It turns out that this lemma is surprisingly sharp. As shown in Lemma 26 below, even the a priori larger volume radius of K is (up to multiplicative factor depending only on m) of the same order D^{−(m−1)/2}. Note that for m = 2 we obtain even the optimal constant (these are the classical inclusion relations for balls in Schatten classes).

Let H = (C^{D})^{⊗N} and Γ(H) ⊂ B(H) be the convex hull of rank one product operators

Γ(H) := conv{|x_{1} ⊗ ⋯ ⊗ x_{N}⟩⟨y_{1} ⊗ ⋯ ⊗ y_{N}| : x_{1}, y_{1}, …, x_{N}, y_{N} ∈ B_{2}^{D}}.

The convex body Γ(H) is most naturally seen as the Nth projective tensor power of the set of (not necessarily Hermitian) operators on C^{D} whose trace class norm is ≤ 1. However, it can also be identified with (B_{2}^{D})^{ˆ⊗2N} when we identify B(K) with \overline{K} ⊗ K. It then follows from the preceding lemma that Γ(H) contains a Euclidean ball (a Hilbert–Schmidt ball in this context) of radius D^{−(2N−1)/2}.

The next lemma will relate Γ(H) to Σ(H), allowing to deduce that the latter body contains a suitably large Euclidean ball. Let d_{N} be the geometric distance between the sets Δ and Σ corresponding to N qubits, i.e. the smallest positive number such that Δ((C^{2})^{⊗N}) ⊂ d_{N}Σ((C^{2})^{⊗N}). We then have

Lemma 23. Let π : B(H) → B_{sa}(H) be the projection onto Hermitian part, π(A) := \frac{1}{2}(A + A^{†}). Then

π(Γ(H)) ⊂ d_{N} Σ(H).

Proof. It is enough to show that extreme points of π(Γ) are contained in d_{N}Σ. Any extreme point A of π(Γ) can be written as

A = \frac{1}{2} (|x_{1} ⊗ ⋯ ⊗ x_{N}⟩⟨y_{1} ⊗ ⋯ ⊗ y_{N}| + |y_{1} ⊗ ⋯ ⊗ y_{N}⟩⟨x_{1} ⊗ ⋯ ⊗ x_{N}|)

It may appear at the first sight that the above representation shows that A is separable. However, while the two terms in the parentheses are indeed product operators, they are not Hermitian and we can only conclude that A ∈ Δ(H) (as a Hermitian operator whose trace class norm is ≤ 1).

Let H_{i} be the 2-dimensional subspace of C^{D} spanned by x_{i} and y_{i} (if the vectors are proportional, add any vector to get a 2-dimensional space) and let H′ := H_{1} ⊗ ⋯ ⊗ H_{N}. Then A can be considered as an operator on H′; more precisely, as an element of Δ(H′) (and, conversely, any operator acting on H′ can be canonically lifted to one acting on H). Note that since we are in the asymptotics where N is small and D is large, the dimension of the problem has been dramatically decreased. Since A belongs to Δ(H′), it also belongs to d_{N}Σ(H′), and thus to d_{N}Σ(H).

To effectively apply Lemma 23, upper bounds on d_{N} are needed. It has been observed in [Sza], Appendix H, that d_{N} ≤ 6^{N/2}. This estimate has been subsequently slightly improved in [GB3] to 2/3×6^{N/2}, and even to a_{N} ×6^{N/2} with lim_{N→∞} a_{N} ≈ 0.624. [These bounds are in fact based on estimates for the a priori larger quantities, the geometric distances between Σ((C^{2})^{⊗N}) (or S((C^{2})^{⊗N}) − Id/2^{N}) and Hilbert–Schmidt balls, which are essentially reciprocals of the Hilbert–Schmidt inradii of these sets; and in this latter context they are “nearly optimal;” see Theorem 3.4 and the comments following it.] Thus Σ(H) ⊃ 3/2 × 6^{−N/2}π(Γ(H)); combining this inclusion with Lemma 22 or, more precisely, with the observation following the definition of Γ(H), we conclude that Σ(H) contains the Hilbert–Schmidt ball of radius 3/2 × 6^{−N/2}D^{−(2N−1)/2} = 3/2 × 6^{−N/2}/d^{1−1/2N}. This gives a lower bound for the volume radius which, together with (3.7), yields

(\frac{vol(Σ)}{vol(Δ)})^{1/d^{2}} ⩾ \frac{3/4 × 6^{−N/2}}{d^{1/2−1/2N}}

To conclude the proof of the theorem we pass to the bodies S and D using (3.6).

Remark: The bipartite case (N = 2) was studied in [GB1], which contains in particular the remarkable result that D and S have then the same inradius, which equals 1/\sqrt{d(d − 1)}. However, the inradii of the symmetrized bodies, which are (in both cases) comparable with the volume radii, are (asymptotically) very different: the inradius of Δ equals 1/\sqrt{d}, while the inradius of Σ has just been shown to be of order 1/d^{3/4}.

3.2.4 Proof of Theorem 3.3: Large number of small subsystems

This part deals with asymptotic estimations of volumes when N, the number of subsystems, tends to infinity whereas the dimension D of each subsystem remains bounded. This case is probably the one with most physical interest. When all subsystems are 2-dimensional (qubits), Theorem 3.3 has been proved in [Sza].

For the proof of the present case it is more convenient to deal with an affine image of Σ which is more balanced than Σ itself or, equivalently, to consider a new scalar product which is better adapted to the analysis of Σ than the Hilbert–Schmidt product. It is a known phenomenon that highdimensional convex bodies often enjoy hidden symmetries (or approximate symmetries) that are only revealed when one looks at them through a suitable Euclidean structure. In our situation, in the asymptotics when N is large and D is bounded, our Theorem 3.2, obtained with the usual Euclidean structure, misses the genuine volumic behavior of the bodies S and Σ. The appropriate scalar product will be here the one derived from the Löwner ellipsoid of Σ. To see why, just look back at the equation (3.9). This bound is the tightest when E is the Löwner ellipsoid of Σ. It turns out that it is possible to describe completely this ellipsoid. First recall that Σ(H) = Δ(C^{D}) ˆ⊗ … ˆ⊗Δ(C^{D}). By Lemma 19, it is enough to calculate the Löwner ellipsoid of Δ(C^{D}), and by tensoring we get the Löwner ellipsoid of Σ(H).

We will determine the Löwner ellipsoid of Δ(C^{D}) using the following elementary general lemma.

Lemma 24. Let u be a unit vector in R^{n} and H_{0} = {u}^{⊥} be the orthogonal hyperplane. Let h > 0 be real number and H = H_{0} + hu be a translate of H_{0}. We consider a convex body Ω = conv{W ∪ −W }, where W is a convex body in H. Then the following assertions are equivalent:

1. Ω is in Löwner position (i.e. the unit ball B_{2}^{n} is the Löwner ellipsoid of Ω).

2. h = 1/\sqrt{n} and B_{2}^{n} ∩ H is the Löwner ellipsoid of W.

Proof. Assume that Ω is in Löwner position, so Ω ⊂ B_{2}^{n}. By John’s theorem (Proposition 3.1), this means that there exists a John resolution of identity (x_{i}, c_{i}), with x_{i} ∈ Ω ∩ S^{n−1} and ∑ c_{i}|x_{i}⟩⟨x_{i}| = Id. Since x_{i} are extreme points of Ω, they must be in W or −W, and since Ω is symmetric we can assume they are all in W. Let P be the orthogonal projection onto H_{0}. It follows that ∑ c_{i}|P x_{i}⟩⟨P x_{i}| = P; note that ∥P x_{i}∥ = \sqrt{1 − h^{2}}. This means that (P x_{i}, c′_{i}) is a John resolution of identity in H_{0}, with c′_{i} = (1 − h^{2})c_{i}. By Proposition 3.1, (1−h^{2})^{−1/2}P W is in Löwner position, or equivalently B_{2}^{n}∩H is the Löwner ellipsoid of W. Moreover, we have the conditions ∑ c′_{i} = n − 1 and ∑ c_{i} = n, which force h = 1/\sqrt{n}.

The converse follows by retracing the above argument in the opposite direction.

Lemma 25. The Löwner ellipsoid of Δ(C^{D}) is determined by the following scalar product defined for A, B ∈ B_{sa}(C^{D}) by

⟨A, B⟩_{Löw(Δ(C^{D}))} = (1 + \frac{1}{D})tr(AB) − \frac{1}{D}tr(A)tr(B)

Proof. First remark that, because of its uniqueness, the Löwner ellipsoid of any body K must inherit all the symmetries of K. Since D(C^{D}) is invariant under unitary conjugations (i.e., the maps π_{U}(X) = UXU^{†} with U ∈ U(D)), the ellipsoid Löw(D(C^{D})) must be similarly invariant, and thus it is the circumscribed Euclidean ball. This is actually somewhat delicate; the relevant fact is that the action of the group {π_{U} : U ∈ U(D)} on the hyperplane T_{1} containing D(C^{D}) is irreducible (in particular, Id/D is the only fixed point and so it must be the center). In the language of convex bodies (see [Tom]) we say that D(C^{D}) has enough symmetries. On the other hand, the fact that this group acts transitively on the set of extreme points of D(C^{D}) (which are the pure states) implies by itself only that all these extreme points are contact points, i.e., belong to the boundary of the Löwner ellipsoid.

By Lemma 24, we know that the trace of the Löwner ellipsoid of Δ(C^{D}) on the hyperplane T_{1} is a Euclidean ball (centered at Id/D), so we have for some real numbers α and β

⟨A, B⟩_{Löw(Δ(C^{D}))} = αtr(AB) + βtr(A)tr(B)

To determine α and β, observe that ⟨ρ, ρ⟩_{Löw(Δ(C^{D}))} = 1 for any pure state (hence contact point) ρ, and that (from the condition on h in Lemma 24; note that n = D^{2}), ⟨Id/D, Id/D⟩_{Löw(Δ(C^{D}))} = 1/D^{2}. This gives α = 1 + 1/D and β = −1/D.

It is possible to use the Löwner ellipsoid of Σ(H) as the ellipsoid E in formula (3.9). Choosing δ = 1/\sqrt{N log 2N} as earlier, we obtain the upper estimate in the formula

\frac{1}{d} ⩽ (\frac{vol(Σ)}{vol(Löw(Σ))})^{1/d^{2}} ⩽ \frac{C\sqrt{DN log N}}{d}  (3.11)

The lower estimate follows from the classical fact ([Bal]) that for a centrally symmetric convex body K in R^{n}, we have the inclusion Löw(K) ⊂ \sqrt{n}K. Improvements on constants can be derived from a result of Barthe ([Bar]) which asserts that for an n-dimensional symmetric body K, the ratio

(\frac{vol(K)}{vol(Löw(K)})^{1/n}

is minimal when K is the unit ball of ℓ_{1}^{n} (and thus is at least (4/π)^{1/2}(Γ(n/2+ 1)/Γ(n + 1))^{1/n}) = \sqrt{\frac{2e}{π}}(1 − O(\frac{1}{n}))\frac{1}{\sqrt{n}} ; we recall that here n = d^{2}).

It remains to calculate the volume of the Löwner ellipsoid of Σ. It follows from Lemma 19 that, if Φ denotes a linear map which sends B_{2}^{D^{2}} onto Löw(Δ(C^{D})), then Ψ := Φ^{⊗N} maps B_{HS} onto Löw(Σ(H)). By Lemma 25, we can define Φ by Φ(A) = (1 + 1/D)^{−1/2}A if A has trace 0 and Φ(Id) = \sqrt{D} Id. This gives det(Φ) = \sqrt{D(1 + 1/D)^{1−D^{2}}} and finally

\frac{vol(Löw(Σ))}{vol(B_{HS})} = det(Ψ) = det(Φ)^{ND^{2N−2}} = d^{−α_{D}d^{2}}  (3.12)

To complete the proof it remains to combine the volume estimates (3.7), (3.11), (3.12) and (3.6).

3.2.5 Proof of Theorem 3.4: Tight upper bounds on the inradii

The idea is to show that there is a projection of the set Σ = Σ((C^{2})^{⊗N}) which is demonstrably small. Specifically, let P : B_{sa}(C^{2}) → B_{sa}(C^{2}) be the orthogonal projection onto the 3-dimensional subspace of trace zero matrices and let Π := P^{⊗N}. Since projective tensor products commute with linear maps (in the sense that (T_{1}⊗…⊗T_{s})(K_{1} ˆ⊗ … ˆ⊗K_{s}) = (T_{1}K_{1}) ˆ⊗ … ˆ⊗(T_{s}K_{s})), we have

Π (Σ((C^{2})^{⊗N})) = P^{⊗N} (Δ(C^{2})^{ˆ⊗N}) = (P (Δ(C^{2})))^{ˆ⊗N} .

Since Δ(C^{2}) is a cylinder whose axis coincides with the kernel of P, the image of Δ(C^{2}) under P is a 3-dimensional Euclidean ball of radius 1/\sqrt{2} (more precisely, D(C^{2}) − Id/2). Accordingly, the image of the corresponding set Σ under Π is the nth projective tensor power of such a ball. The relevant parameters of such sets (mean widths, volume radii) are majorized by the following statement, which is a complement of Lemma 4.

Lemma 26. There is an absolute constant C_{1} such that if D, m are positive integers (m ⩾ 2) and K := (B_{2}^{D})^{ˆ⊗m} is the projective tensor product of m copies of the D-dimensional Euclidean ball (real or complex), then

vrad(K) ⩽ w(K) < \frac{C_{1}\sqrt{m log m}}{D^{(m−1)/2}}

Proof. The first inequality in Lemma 26 — comparing the volume radius of a convex body to its mean width — is just the Urysohn inequality. The proof of the second follows the same lines as — but is simpler than — the approach that yielded formula (3.9). We present the details only for the case that is relevant to Theorem 3.4, namely D = 3 in the real setting. The argument is very similar to the one used in [Sza] to obtain an upper bound for the volume of Σ((C^{2})^{⊗m}), where the reader is referred for additional background and justifications.

We start by noting that, for any δ ∈ (0, \sqrt{2}), the sphere S^{2} contains a δ-net F whose cardinality is ⩽ 16/δ^{2}. On the other hand, an elementary geometric argument shows that the convex hull of any δ-net contains a (Euclidean) ball of radius 1−δ^{2}/2. Accordingly, the convex hull of F^{⊗m}, the mth tensor power of F, contains (1 − δ^{2}/2)^{m}(B_{2}^{3})^{ˆ⊗m}. Since #(F^{⊗m}) ⩽ (#F)^{m} ⩽ (4/δ)^{2m}, it follows from (3.4) that

w((1 − δ^{2}/2)^{m}(B_{2}^{3})^{ˆ⊗m}) ⩽ w(conv(F^{⊗m})) < γ_{3^{m}}^{−1}\sqrt{2 log ((4/δ)^{2m})}

and, consequently,

vrad((B_{2}^{3})^{ˆ⊗m}) ⩽ w((B_{2}^{3})^{ˆ⊗m}) < 2γ_{3^{m}}^{−1}(1 − δ^{2}/2)^{−m}\sqrt{m log (4/δ)}.

We now choose δ = 1/\sqrt{m log 2m}; then, for large m, (1 − δ^{2}/2)^{−m} ∼ 1, log (4/δ) ∼ \frac{1}{2} log m and γ_{3^{m}} ∼ 3^{m/2}. This yields the asserted upper bound on the mean width with C_{1} ∼ \sqrt{2/3} for large d. A more careful calculation using Lemma 20 for small m shows that C_{1} = 1.67263 works for all m. [The discussion of constants above and in the remainder of this section is specific to D = 2, but easily carries over to general case; for example, it is easy to show that C_{1} ∼ 1 works for large m and all D.) As in [Sza], further improvement are possible by working with explicit nets and/or by noting that F can be chosen to be symmetric, but we will not pursue them since it is likely that, for the problem at hand, sharper estimates can be obtained by analytic methods.

We now return to the proof of Theorem 3.4. From prior considerations, the image of Σ under the projection Π is congruent to 2^{−N/2}(B_{2}^{3})^{ˆ⊗N} and so, by Lemma 26,

w(Π(Σ)) = 2^{−N/2}w((B_{2}^{3})^{ˆ⊗N} < 3^{1/2}C_{1}\sqrt{N log N} 6^{−N/2}.

Since the inradius is trivially smaller than the mean width, and since the inradius of the set S of separable states does not exceed that of its symmetrization Σ, Theorem 3.4 follows (with C_{0} = 3^{1/2}C_{1} < 3). It is also routine to obtain an (identical or nearly identical) upper bound on the mean width of S; however, some care is needed because the dimensions of S and Σ are not the same.

Since our argument is of a global nature, we are not able to produce an explicit state in the ball of radius r := C_{0}\sqrt{N log N} 6^{−N/2} and centered at Id/d which is not separable. However, standard tools of asymptotic geometric analysis (cf. [ST] or [Pis]) imply that even stronger properties are satisfied “generically.” Denote by H_{0} the d_{0} := 3^{N}-dimensional range of the projection Π. Then, for most of the unit vectors u on the unit sphere of H_{0}, the state σ = Id/2^{N} + 2ru is not separable, and the same holds for any state ρ such that Π(ρ) = Π(σ) (here “most of” means that the exceptional set is of normalized measure < 2^{−d_{0}/2}). Moreover, a slightly weaker but comparable property holds simultaneously for all u in a “generic” (in the sense of the invariant measure on the corresponding Grassmannian) ⌈d_{0}/2⌉-dimensional subspace of H_{0}.

As mentioned in the introduction, the above argument can be generalized to other values of D and leads to an upper bound for the inradii of the sets Σ and S corresponding to (C^{D})^{⊗N} which is, up to a logarithmic factor, (D(D + 1))^{−N/2}. While this upper bound differs, for D > 2, from the lower bound for the inradius of S that was found in [GB3], it gives the correct order for the inradius of the set Σ. Indeed, Σ contains Löw(Σ)/d, which itself contains (D(D+1))^{−N/2}B_{HS} (this argument parallels the one for qubits given in [Sza], Appendix H, where we refer the reader for details).

3.2.6 Proof of Theorem 3.5: Asymptotic weakness of PPT criterion

We will use the following proposition which is taken from [MiPa2].

Proposition 3.2. Let K and L be convex bodies in R^{n} with the same centroid. Then

vol(K)vol(L) ⩽ vol(K − L)vol(K ∩ L),

where K − L := {x − y : x ∈ K, y ∈ L} is the Minkowski difference.

We apply the proposition with K = D and L = T D. This gives

\frac{vol(D)}{vol(PPT)} ⩽ \frac{vol(D − T D)}{vol(D)}  (3.13)

Note that we actually used the proposition in the space T_{1} ∼ R^{n}, seen as a vector space with Id/d as origin; the point Id/d is also the centroid of D (and T D), it is even the the only fixed point under the group of symmetries of D (cf. the proof of Lemma 25). We rewrite (3.13) using volume radii

(\frac{vol(D)}{vol(PPT)})^{1/n} ⩽ \frac{vrad(D − T D)}{vrad(D)}

Recall that we majorized the volume radius by the mean width using the Urysohn inequality (here mean width is also taken in T_{1}). This is very convenient since, as one can check immediately from the definition, the mean width is additive with respect to the Minkowski operations: w(D − T D) = w(D) + w(−T D). Since −T is an isometry, it preserves the uniform measure on the sphere S^{n−1} and thus w(−T D) = w(D). This gives

(\frac{vol(D)}{vol(PPT)})^{1/n} ⩽ \frac{2w(D)}{vrad(D)}

We now appeal to (3.8) to majorize the right hand side by 8, which proves Theorem 3.5 with c_{0} = 1/8. Note also that one can use the explicit formula (3.3) for the volume of D; this shows that asymptotically c_{0} tends to e^{−1/4}/4 ≈ 0.195. Moreover, numerical evidence (which presumably can be confirmed by rigorous calculation using appropriate Stirling-type formulae) suggests that vrad(D) ⩾ e^{−1/4}/\sqrt{d} for all dimensions d, which would imply that the asymptotic value is in fact a bound.

Finally, observe that the proof above works actually for any (Hilbert– Schmidt) isometry in T_{1} which fixes Id/d, and not only for the partial transpose T.

3.3 Appendices

3.3.1 Preuve du théorème 3.1

Products of Bloch balls and similar bodies G. Aubrun, S. J. Szarek, E. Werner

The purpose of this note is to show that the set of normalized separable states of an N-qubit quantum system contains a Hilbert–Schmidt ball of radius \sqrt{3} · 6^{− \frac{N}{2}} , centered at the normalized identity. This improves slightly a result of Gurvits and Barnum [GB2, GB3], and is based on fine-tuning of their method.

Notation. For any n ∈ ℕ, we single out in the space R^{n} a unit vector which we call e_{0}, or e_{0}^{(n)} to indicate the dimension. We will frequently identify R^{n} ⊗ R^{p} with R^{np} so that e_{0}^{(np)} ≃ e_{0}^{(n)} ⊗ e_{0}^{(p)}. A concrete example when this convention is going to be used is the space B_{sa}(C^{d}) of self-adjoint operators on the d-dimensional complex Hilbert space (or, equivalently, d×d Hermitian matrices), identified with R^{d^{2}} so that e_{0}^{(d^{2})} corresponds to Id/\sqrt{d}, the identity matrix normalized in the Hilbert–Schmidt norm. The above gradation is then compatible with canonical identifications B_{sa}(C^{d_{1}}) ⊗ B_{sa}(C^{d_{2}}) ≃ B_{sa}(C^{d_{1}} ⊗ C^{d_{2}}).

Let D_{N} = D((ℂ^{2})^{⊗N}) be the (convex) set of states on B((ℂ^{2})^{⊗N}) and let S_{N} be the (convex) subset of D_{N} consisting of the separable states. Then S_{N} = D_{1}^{ˆ⊗N}, where the projective tensor product of convex bodies K_{1}, …, K_{N} is defined by

K_{1} ˆ⊗ … ˆ⊗K_{N} = conv{x_{1} ⊗ ⋯ ⊗ x_{N}, x_{i} ∈ K_{i}}

We write B_{2}^{n} for the unit ball in R^{n} (centered at 0) and B̆_{2}^{n} for the unit ball intersected with the hyperplane e_{0}^{⊥}. With this notation, the Bloch ball D_{1} is equal to 1/\sqrt{2}(e_{0} + B̆_{2}^{4}) and, consequently, S_{N} = 2^{−N/2}(e_{0} + B̆_{2}^{4})^{ˆ⊗N}.

Results. In the above notation, the assertion stated at the beginning of the note can be rephrased as

Theorem 3.1 . For any N ⩾ 1

e_{0}^{⊗N} + \frac{1}{3^{\frac{N−1}{2}}} B̆_{2}^{4^{N}} ⊂ (e_{0} + B̆_{2}^{4})^{ˆ⊗N}.

Theorem 3.1 is proved by repeated application of the following Lemma 27. Let 0 ⩽ β ⩽ 1. Then for any n ⩾ 4

e_{0} + \frac{β}{\sqrt{3}} B̆_{2}^{4n} ⊂ (e_{0} + B̆_{2}^{4}) ˆ⊗(e_{0} + β B̆_{2}^{n}).

Proof. If K ∋ 0 is a closed convex subset of the Euclidean space, the (maximal) radius of ball centered at 0 and contained in K is given by

min_{|u|=1} max_{x∈K} ⟨x, u⟩

One can similarly express the in-radii of convex sets of lower dimension. In particular, the maximal radius of a ball inscribed in the projective tensor product (e_{0} + B̆_{2}^{4}) ˆ⊗(e_{0} + β B̆_{2}^{n}) and centered at e_{0} ⊗ e_{0} is

min_{|u|=1,u⊥e_{0}⊗e_{0}} max_{x∈B_{2}^{3},y∈βB̆_{2}^{n}} ⟨(e_{0} + x) ⊗ (e_{0} + y), u⟩.  (3.14)

The orthogonal complement of e_{0} ⊗ e_{0} in ℝ^{4} ⊗ ℝ^{n} is (ℝe_{0} ⊗ ℝ^{n−1}) ⊕ (ℝ^{3} ⊗ ℝe_{0})⊕(ℝ^{3} ⊗ℝ^{n−1}). Denoting m = n−1 and identifying the three summands with ℝ^{m}, ℝ^{3} and 3 × m matrices respectively, we may rewrite (3.14) as

Φ_{m}(β) := min_{|a|^{2}+|b|^{2}+∥A∥_{HS}^{2}=1} {max \atop |x| = 1, |y| = β} ⟨a, x⟩ + ⟨b, y⟩ + ⟨Ay, x⟩, (3.15)

where a, x ∈ ℝ^{3}, b, y ∈ ℝ^{m} and A is a 3×m matrix. The assertion of Lemma 27 is equivalent to Φ_{m}(β) ≥ β/\sqrt{3} for all m ≥ 3 and all β ∈ [0, 1]. (The reverse inequality is trivial; choose, for example, a = b = 0 and A = Id/\sqrt{3} if m = 3, and similarly for m > 3.)

Before proceeding, we point out that when m = 3, β = 1, the inequality Φ_{3}(1) ≥ 1/\sqrt{3} is equivalent to the case n = 4, β = 1 of Lemma 27 and, at the same time, to the case N = 2 of Theorem 3.1, that is, to the inradius of S_{2} being at least \frac{1}{2\sqrt{3}}. The in-radius of the set of separable states in the bilateral (two factors) case has been determined to be equal to the (easily calculated) in-radius of the set of all states in [GB1]. In the special case of S_{2} (two qubits) this is rather classical. One possible argument: the sufficiency of Peres’ partial transpose criterion for 2 ⊗ 2 systems ([HHH1]) means that S_{2} = D_{2} ∩ T (D_{2}), where T is the partial transpose (say, with respect to the first system), and so the equality of the in-radii of S_{2} and D_{2} follows from T being an (ℝ-linear) isometry which keeps Id/4 (the center of the balls) fixed.

We will show first that Φ_{3}(β) = \frac{β}{\sqrt{3}}. We have

Φ_{m}(β) = min_{|a|^{2}+|b|^{2}+∥A∥_{HS}^{2}=1} max_{|y|=β} (⟨b, y⟩ + max_{|x|=1} ⟨a, x⟩ + ⟨Ay, x⟩)
= min_{|a|^{2}+|b|^{2}+∥A∥_{HS}^{2}=1} max_{|y|=β} (⟨b, y⟩ + |Ay + a|) .  (3.16)

Consequently, proving Φ_{3}(β) ⩾ \frac{β}{\sqrt{3}} is equivalent to establishing that, for all a, b ∈ ℝ^{3} and for all 3 × 3 matrices A,

max_{|y|=β} (⟨b, y⟩ + |Ay + a|) ⩾ \frac{β}{\sqrt{3}} (|a|^{2} + |b|^{2} + ∥A∥_{HS}^{2})^{\frac{1}{2}} .

In turn, setting y′ = \frac{y}{β} and a′ = \frac{a}{β}, we see that the above is equivalent to showing that for all a′, b ∈ ℝ^{3} and for all 3 × 3 matrices A

max_{|y′|=1} ⟨b, y′⟩ + |Ay′ + a′| ⩾ \frac{1}{\sqrt{3}} (β^{2}|a′|^{2} + |b|^{2} + ∥A∥_{HS}^{2})^{\frac{1}{2}} .

The left hand side of the last inequality does not depend on β, while (for fixed a′, b, A) the right hand side is an increasing function of β. Since, as we observed, the inequality holds for β = 1, it does also hold for all β ∈ [0, 1).

It remains to show that, for m > 3, Φ_{m}(β) = Φ_{3}(β), or even just that Φ_{m}(β) ≥ Φ_{3}(β). The key observation is that the min-max expressions min_{a,b} max_{x,y} for given matrix A in (3.15) or (3.16) depend only on the singular values of the matrix A. This is most easily seen from the form in the second line of (3.16), either by

• a geometric argument, by noticing is that what counts there is the shape (semi-axes) of the ellipsoid βAB_{2}^{m}, or by

• an algebraic argument, by substituting A = UA_{1}V, where U ∈ O(3), V ∈ O(m), then changing variables to a_{1} = U^{†}a, y_{1} = V y, b_{1} = V b and noticing that

⟨b, y⟩ + |Ay + a| = ⟨b_{1}, y_{1}⟩ + |A_{1}y_{1} + a_{1}|

Accordingly, we may assume that at most the diagonal (i.e., 11, 22, and 33) entries of the matrix A are nonzero (what we actually need is that only the first three columns are allowed to be nonzero). With this restriction, the matrix A is in effect 3 × 3, and the only difference between Φ_{m}(β) and Φ_{3}(β) is then that in the formula for the former the vectors y and b do not need to be supported on the first three coordinates. While it is easy to believe that, with a matrix A supported on the first three columns “all the action” must be happening on the first three coordinates of R^{m}, more careful book-keeping is in order since we are dealing here with a min-max. Let us split y and b into components supported on the first 3 coordinates and on the remaining n − 3 coordinates, y = y′ + y′′ and b = b′ + b′′. Then

Φ_{m}(β) = min_{|a|^{2}+|b′|^{2}+|b′′|^{2}+∥A∥_{HS}^{2}=1} max_{{|x|=1 \atop |y′ |^{2}+|y′′ |^{2}=β^{2}}} ⟨Ay′, x⟩+⟨a, x⟩+⟨b′, y′⟩+⟨b′′, y′′⟩

Setting τ := \frac{|y′′|}{β}, θ := |b′′| and making the clearly optimal (for given τ) choice of y′′ to be a positive multiple of b′′, we can rewrite the above as

Φ_{m}(β) = min_{|a|^{2}+|b′|^{2}+∥A∥_{HS}^{2}=1−θ^{2}} max_{|x|=1,|y′|=β(1−τ^{2})^{1/2}}⟨Ax, y′⟩+⟨a, x⟩+⟨b′, y′⟩+θτβ

We now note that, for given a, b′, A, θ, τ, optimizing the sum of the first three terms under max over x, y′ yields at least \sqrt{1 − θ^{2}} Φ_{3}(β\sqrt{1 − τ^{2}}). Since Φ_{3}(t) = t/\sqrt{3}, we get

Φ_{m}(β) ≥ min_{θ∈[0,1]} max_{τ∈[0,1]} \sqrt{1 − θ^{2}} \frac{β\sqrt{1 − τ^{2}}}{\sqrt{3}} + θτβ = β min_{θ∈[0,1]} \sqrt{\frac{1 − θ^{2}}{3} + θ^{2}} .

The last minimum is clearly achieved at θ = 0 and equals 1/\sqrt{3}. It follows that Φ_{m}(β) ≥ β/\sqrt{3} = Φ_{3}(β), as required.

3.3.2 Preuve du théorème 3.4’

La preuve est due à Gurvits et apparaît implicitement dans [GB3]. Elle repose sur le lemme suivant, utilisé également dans [RMNDMC].

Lemme 28 (Les projections locales ne créent pas d’intrication). Soit H_{1}, …, H_{N} des espaces de Hilbert et, pour chacun d’entre eux, H′_{i} ⊂ H_{i} un sous-espace. On note H = ⨂ H_{i} et H′ = ⨂ H′_{i}. Soit, pour chaque i, π_{i} la projection orthogonale de H_{i} sur H′_{i}, de sorte que π := ⨂ π_{i} est la projection orthogonale de H sur H′. Soit A une matrice qui est un multiple positif d’un état séparable, c’est-à-dire

A ∈ R^{+}S(H_{1} ⊗ ⋯ ⊗ H_{N})

Alors, πAπ est un multiple positif d’un état séparable (sur H′), c’est-à-dire

πAπ ∈ R^{+}S(H′_{1} ⊗ ⋯ ⊗ H′_{N})

Démonstration. Il suffit d’écrire la définition de la séparabilité et d’utiliser l’égalité

π(ρ_{1} ⊗ ⋯ ⊗ ρ_{N})π = (π_{1}ρ_{1}π_{1}) ⊗ ⋯ ⊗ (π_{N}ρ_{N}π_{N})

Nous pouvons maintenant déduire facilement le théorème 3.4’ à partir du théorème 3.4. Pour D ⩾ 2, soit r_{D} le rayon de la plus grande boule Hilbert– Schmidt centrée en Id contenue dans le cône séparable R^{+}S((C^{D})^{⊗N}). Appliquons le lemme 28 avec H_{i} = C^{D} et H′_{i} = C^{2}. En utilisant le fait que ∥πρπ − Id_{(C^{2})^{⊗N}} ∥ ⩽ ∥ρ − Id_{(C^{D})^{⊗N}} ∥, on obtient immédiatement que r_{D} ⩽ r_{2}. Par ailleurs, la quantité r_{D} est reliée au rayon interne i_{D} de S((C^{D})^{⊗N}) par la relation

i_{D} = \frac{r_{D}}{\sqrt{D^{N}(D^{N} − r_{D}^{2})}}

Ainsi, l’inégalité r_{D} ⩽ r_{2} se traduit en

i_{D} ⩽ \frac{2^{N}i_{2}}{\sqrt{D^{2N} + i_{2}^{2}(2D)^{N}(D^{N} − 2^{N})}}

En utilisant la borne supérieure sur i_{2} qui provient du théorème 3.4, on obtient

i_{D} ⩽ \frac{C_{0}\sqrt{N log N}}{6^{N/2}} \frac{2^{N}}{D^{N}}

C’est exactement le contenu du théorème 3.4’.

3.3.3 Majoration précise du supremum d’un processus gaussien

Lemme 29. Si n ⩾ 2 et (X_{1}, …, X_{n}) est un vecteur gaussien tel que pour 1 ⩽ i ⩽ n, EX_{i}^{2} ⩽ 1, alors

E max_{1⩽i⩽n} |X_{i}| ⩽ \sqrt{2 log n}.

Démonstration. L’estimation E max X_{i} ⩽ \sqrt{2 log n} est bien connue ; voir par exemple la proposition 1.1.3. dans [Tal]. Notons qu’à la différence du résultat du lemme, cette estimation est aussi vraie pour n = 1. La preuve que nous présentons suit la preuve du lemme 0.6.2 dans [Fer]. Soit T un nombre à choisir ultérieurement. On écrit

E max_{1⩽i⩽n} |X_{i}| = ∫_{0}^{∞} P ( max_{1⩽i⩽n} |X_{n}| > t) dt.

Si 0 ⩽ t ⩽ T, on majore trivialement l’intégrande par 1, alors que si t > T on utilise la borne P(max |X_{n}| > t) ⩽ 2nP(G > t), où G désigne une variable gaussienne standard. Une intégration par parties donne ensuite

∫_{T}^{∞} P(G > t)dt = \frac{1}{\sqrt{2π}} e^{−T^{2}/2} − T P(G > T).

Il reste ensuite à optimiser selon la valeur de T. Ceci permet de prouver numériquement le lemme pour n ⩾ 4. Cependant, cela nécessite de calculer pour certaines valeurs de t la quantité P(G > t) qui fait intervenir une intégrale impropre, ce qu’il est possible d’éviter ici. En effet des inégalités très précises sont connues pour la fonction P(G > t). Il a par exemple été démontré dans [RW] que pour tout t ⩾ 0,

P(G > t) ⩾ \frac{1}{\sqrt{2π}} e^{−t^{2}/2} \frac{π}{(π − 1)t + \sqrt{t^{2} + 2π}} .

On vérifie alors numériquement que cette inégalité, couplée au choix

T = \sqrt{2 log n − 3/2},

permet de conclure pour n ⩾ 4.

Si n = 2 ou n = 3, on utilise le lemme suivant dû à Sidak (voir par exemple [SW, SSZ]) : si (X_{i})_{1⩽i⩽n} est un vecteur gaussien et si (Y_{i})_{1⩽i⩽n} est un n-uplet de variables gaussiennes indépendantes telles que pour chaque i, Y_{i} a même loi que X_{i}, alors

E max_{1⩽i⩽n} |X_{i}| ⩽ E max_{1⩽i⩽n} |Y_{i}|

On vérifie ainsi numériquement que la conclusion du lemme est également vraie si n = 2 ou n = 3.

Remarquons que pour n ⩾ 4 on a en fait prouvé le résultat suivant, qui est plus fort que la conclusion du lemme : si n ⩾ 4 et si (Y_{i})_{1⩽i⩽2n} sont des variables aléatoires gaussienes telles que pour tout 1 ⩽ i ⩽ 2n on a EY_{i}^{2} ⩽ 1, alors

E max_{1⩽i⩽2n} Y_{i} ⩽ \sqrt{2 log n}.  (3.17)

Cette propriété plus forte n’est pas vraie pour n = 2 ou n = 3 : en effet si l’on ne suppose pas que la famille (Y_{i}) est un vecteur gaussien, la quantité E max Y_{i} est maximale quand les variables aléatoires (Y_{i})_{1⩽i⩽2n} sont de variance 1 et telles que les événements {Y_{i} > α_{1/2n}}_{1⩽i⩽2n} forment une partition de l’espace probabilisé sous-jacent, où α_{t} l’unique nombre réel tel que P(G > t) = α_{t}. Sur cet exemple l’inégalité (3.17) est fausse pour n = 2 ou n = 3.

3.3.4 Preuve du lemme 20

Rappelons l’énoncé du lemme 20 :

Soient K ⊂ B_{2}^{n} ⊂ R^{n} et K′ ⊂ B_{2}^{n′} ⊂ R^{n′} des corps convexes, l’un d’entre eux étant l’enveloppe convexe d’une partie de la sphère-unité correspondante. Alors

w_{G}(K ˆ⊗K′) ⩽ w_{G}(K) + w_{G}(K′).

Par conséquent, en termes de la largeur moyenne usuelle,

w(K ˆ⊗K′) ⩽ \frac{γ_{n}}{γ_{nn′}} w(K) + \frac{γ_{n′}}{γ_{nn′}} w(K′) ⩽ \frac{w(K)}{\sqrt{n′}} + \frac{w(K′)}{\sqrt{n}},

Démonstration. La preuve est similaire à celle de la partie 2.3 de [DS]. L’ingrédient principal en est la version suivante du lemme de Slepian :

Lemme 30. Soit (X_{t})_{t∈T} et (Y_{t})_{t∈T} deux vecteurs gaussiens, indexés par le même ensemble fini T et vérifiant l’hypothèse

∀t, u ∈ T, E(X_{t} − X_{u})^{2} ⩽ E(Y_{t} − Y_{u})^{2}

Alors

E max_{t∈T} X_{t} ⩽ E max_{t∈T} Y_{t}

Supposons par exemple que ext(K) ⊂ S^{n−1} (la situation est évidemment symétrique en K et K′). On applique le lemme 30 avec T = ext(K)×ext(K′) et les processus X et Y définis par

X_{(t,t′)} = ⟨G_{R^{n}⊗R^{n′}}, t ⊗ t′⟩
Y_{(t,t′)} = ⟨G_{R^{n}}, t⟩ + ⟨G_{R^{n′}}, t′⟩

L’espace T n’est pas fini ; il est néanmoins compact et on applique en réalité le lemme 30 à toutes les parties finies de T, voir [Fer] pour plus de précisions. Il faut vérifier que l’hypothèse du lemme est vraie, c’est-à-dire prouver l’inégalité :

∀t, u ∈ S^{n−1}, ∀t′, u′ ∈ B_{2}^{n′}, |t ⊗ t′ − u ⊗ u′|^{2} ⩽ |t − u|^{2} + |t′ − u′|^{2}

En utilisant le fait que |t|^{2} = |u|^{2} = 1, cela équivaut à

⟨t, u⟩ + ⟨t′, u′⟩ ⩽ 1 + ⟨t, u⟩⟨t′, u′⟩

qui est bien vérifiée pour des vecteurs de norme inférieure à 1. Ceci prouve donc la conclusion du lemme 20 sur les largeurs moyennes gaussiennes. Il reste à prouver l’inégalité γ_{n}/γ_{nn′} ⩽ 1/\sqrt{n′}, qui est une conséquence du fait que la suite (γ_{k}/\sqrt{k}) est croissante. Pour voir ce dernier point, définissons la fonction h sur R^{+} par

h(y) = \frac{Γ(y + 1/2)}{\sqrt{y}Γ(y)}

La dérivée logarithmique de h vaut

(log h)′(y) = 𝟋(y + 1/2) − 𝟋(y) − \frac{1}{2y}

où 𝟋 (« digamma ») est la dérivée logarithmique de la fonction Γ : 𝟋 = (log Γ)′. Le fait que (log h)′ est strictement positif sur R^{+} découle de l’inégalité suivante, prouvée dans [Luk]

∀y > 0; y(𝟋(y + 1/2) − 𝟋(y)) ⩾ \frac{2y + 1}{4y + 1} > \frac{1}{2}

Ainsi la fonction h est croissante, et on conclut en remarquant que pour k ∈ 2N, h(k/2) = γ_{k}/\sqrt{k}.

Bibliographie

[Ale] Alesker, S. ψ_{2}-estimate for the Euclidean norm on a convex body in isotropic position. In Geometric aspects of functional analysis (Israel, 1992–1994), vol. 77 of Oper. Theory Adv. Appl. Birkhäuser, Basel, 1995, pp. 1–4.

[AKM] Artstein, S., Klartag, B. et Milman, V. The Santaló point of a function, and a functional form of Santaló inequality. Mathematika (à paraître).

[Aub1] Aubrun, G. A sharp small deviation inequality for the largest eigenvalue of a random matrix. In Séminaire de Probabilités XXXVIII, vol. 1857 of Lecture Notes in Math. Springer, Berlin, 2005, pp. 320–337.

[Aub2] Aubrun, G. Sampling convex bodies : a random matrix ap-

proach http://www.institut.math.jussieu.fr/~aubrun/sampling.

dvi, 2003.

[Bai] Bai, Z. D. Methodologies in spectral analysis of large-dimensional random matrices, a review. Statist. Sinica 9, 3 (1999), 611–677. Avec des commentaires de G. J. Rodgers et Jack W. Silverstein, et une réponse de l’auteur.

[BY] Bai, Z. D. et Yin, Y. Q. Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix. Ann. Probab. 21, 3 (1993), 1275–1294.

[Bal] Ball, K. An elementary introduction to modern convex geometry. In Flavors of geometry, vol. 31 of Math. Sci. Res. Inst. Publ. Cambridge Univ. Press, Cambridge, 1997, pp. 1–58.

[Bar] Barthe, F. On a reverse form of the Brascamp-Lieb inequality. Invent. Math. 134, 2 (1998), 335–361.

[BGMN] Barthe, F., Guédon, O., Mendelson, S. et Naor, A. A probabilistic approach to the geometry of the l_{p}^{n}-ball. Ann. Probab. 33, 2 (2005), 480–513.

[BN1] Bobkov, S. G. et Nazarov, F. L. On convex bodies and logconcave probability measures with unconditional basis. In Geometric aspects of functional analysis, vol. 1807 of Lecture Notes in Math. Springer, Berlin, 2003, pp. 53–69.

[BN2] Bobkov, S. G. et Nazarov, F. L. Large deviations of typical linear functionals on a convex body with unconditional basis. Progress in Probability 56 (2003), 3–13.

[Bor] Borell, C. Convex set functions in d-space. Period. Math. Hungar. 6, 2 (1975), 111–136.

[Bou] Bourgain, J. Random points in isotropic convex sets. In Convex geometric analysis (Berkeley, CA, 1996), vol. 34 of Math. Sci. Res. Inst. Publ. Cambridge Univ. Press, Cambridge, 1999, pp. 53–58.

[BLM] Bourgain, J., Lindenstrauss, J. et Milman, V. D. Minkowski sums and symmetrizations. In Geometric aspects of functional analysis (1986/87), vol. 1317 of Lecture Notes in Math. Springer, Berlin, 1988, pp. 44–66.

[BC] Braunstein, S. L. et Caves, C. M. Statistical distance and the geometry of quantum states. Phys. Rev. Lett. 72, 22 (1994), 3439–3443.

[CG] Cerf, N. et Gisin, N. L’étrange pouvoir de l’intrication quantique. La Recherche, hors-série 18 (2005), 84–89.

[DS] Davidson, K. R. et Szarek, S. J. Local operator theory, random matrices and Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, 317–366, Vol. II, 1819–1820. North-Holland, Amsterdam, 2001.

[Dud] Dudley, R. M. Real analysis and probability. The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software, Pacific Grove, CA, 1989.

[Fer] Fernique, X. Fonctions aléatoires gaussiennes, vecteurs aléatoires gaussiens. Université de Montréal Centre de Recherches Mathématiques, Montreal, QC, 1997.

[For] Forrester, P. J. The spectrum edge of random matrix ensembles. Nuclear Phys. B 402, 3 (1993), 709–728.

[Gar] Gardner, R. J. The Brunn-Minkowski inequality. Bull. Amer. Math. Soc. (N.S.) 39, 3 (2002), 355–405 (électronique).

[Gem] Geman, S. A limit theorem for the norm of random matrices. Ann. Probab. 8, 2 (1980), 252–261.

[Gia] Giannopoulos, A. Notes on isotropic convex bodies. http://

eudoxos.math.uoa.gr/~apgiannop/isotropic-bodies.ps, 2003.

[GHT] Giannopoulos, A., Hartzoulaki, M. et Tsolomitis, A. Random points in isotropic unconditional convex bodies. Journal of the London Mathematical Society (à paraître).

[GM] Giannopoulos, A. A. et Milman, V. D. Concentration property on probability spaces. Adv. Math. 156, 1 (2000), 77–106.

[GG] Gohberg, I. et Goldberg, S. Basic operator theory. Birkhäuser Boston, Mass., 1981.

[GGK] Gohberg, I., Goldberg, S. et Krupnik, N. Traces and determinants of linear operators, vol. 116 of Operator Theory : Advances and Applications. Birkhäuser Verlag, Basel, 2000.

[GP] Guédon, O. et Paouris, G. Concentration of mass on the schatten classes. Prépublication.

[GB1] Gurvits, L. et Barnum, H. Largest separable balls around the maximally mixed bipartite quantum state. Phys. Rev. A 66 (2002).

[GB2] Gurvits, L. et Barnum, H. Separable balls around the maximally mixed multipartite quantum states. quant-ph/0302102, 2003.

[GB3] Gurvits, L. et Barnum, H. Better bound on the exponent of the radius of the multipartite separable ball. quant-ph/0409095, 2004.

[HT] Haagerup, U. et Thorbjørnsen, S. Random matrices with complex Gaussian entries. Expo. Math. 21, 4 (2003), 293–337.

[Hen] Hensley, D. Slicing convex bodies—bounds for slice area in terms of the body’s covariance. Proc. Amer. Math. Soc. 79, 4 (1980), 619–625.

[HHH1] Horodecki, M., Horodecki, P. et Horodecki, R. Separability of mixed states : necessary and sufficient conditions. Phys. Lett. A 223, 1-2 (1996), 1–8.

[HHH2] Horodecki, M., Horodecki, P. et Horodecki, R. Mixed-state entanglement and quantum communication. In Quantum Information : An Introduction to Basic Theoretical Concepts and Experiments, Springer Tracts in Modern Physics. Springer, Berlin, 2001.

[Joh] Johnstone, I. M. On the distribution of the largest eigenvalue in principal components analysis. Ann. Statist. 29, 2 (2001), 295–327.

[KLS] Kannan, R., Lovász, L. et Simonovits, M. Random walks and an O^{∗}(n^{5}) volume algorithm for convex bodies. Random Structures Algorithms 11, 1 (1997), 1–50.

[KSC] Kolchin, V. F., Sevast′yanov, B. A. et Chistyakov, V. P. Random allocations. V. H. Winston & Sons, Washington, D.C., 1978. Traduit du russe, Traduction éditée par A. V. Balakrishnan, Scripta Series in Mathematics.

[Kwa] Kwapień, S. A remark on the median and the expectation of convex functions of Gaussian vectors. In Probability in Banach spaces, 9 (Sandjberg, 1993), vol. 35 of Progr. Probab. Birkhäuser Boston, Boston, MA, 1994, pp. 271–272.

[Led1] Ledoux, M. The concentration of measure phenomenon, vol. 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.

[Led2] Ledoux, M. A remark on hypercontractivity and tail inequalities for the largest eigenvalues of random matrices. In Séminaire de Probabilités XXXVII, vol. 1832 of Lecture Notes in Math. Springer, Berlin, 2003, pp. 360–369.

[Led3] Ledoux, M. Deviations inequalities on largest eigenvalues. http:

//www.lsp.ups-tlse.fr/Ledoux/Jerusalem.pdf, 2005.

[LQ] Li, D. et Queffélec, H. Introduction à l’étude des espaces de Banach. Analyse et probabilités. Société mathématique de France, 2004.

[LPRT] Litvak, A., Pajor, A., Rudelson, M. et Tomczak-Jaeger mann, N. Smallest singular value of random matrices and geometry of random polytopes. Advances in mathematics (à paraître).

[Luk] Luke, Y. L. Inequalities for the gamma function and its logarithmic derivative. Math. Balkanica 2 (1972), 118–123.

[MaPa] Marčenko, V. A. et Pastur, L. A. Distribution of eigenvalues in certain sets of random matrices. Mat. Sb. (N.S.) 72 (114) (1967), 507–536.

[Mec] Meckes, M. W. Concentration of norms and eigenvalues of random matrices. J. Funct. Anal. 211, 2 (2004), 508–524.

[Meh] Mehta, M. L. Random matrices, second ed. Academic Press Inc., Boston, MA, 1991.

[MePa] Mendelson, S. et Pajor, A. On singular values of matrices with independent rows. Prépublication.

[MPT] Mendelson, S., Pajor, A. et Tomczak-Jaegermann, N. Reconstruction and subgaussian processes. Prépublication.

[MiPa1] Milman, V. D. et Pajor, A. Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space. In Geometric aspects of functional analysis (1987–88), vol. 1376 of Lecture Notes in Math. Springer, Berlin, 1989, pp. 64–104.

[MiPa2] Milman, V. D. et Pajor, A. Entropy and asymptotic geometry of non-symmetric convex bodies. Adv. Math. 152, 2 (2000), 314–335.

[MS] Milman, V. D., and Schechtman, G. Asymptotic theory of finitedimensional normed spaces, vol. 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[NC] Nielsen, M. A. et Chuang, I. L. Quantum computation and quantum information. Cambridge University Press, Cambridge, 2000.

[Olv] Olver, F. W. J. Asymptotics and special functions. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1974. Computer Science and Applied Mathematics.

[OP] Oravecz, F. et Petz, D. On the eigenvalue distribution of some symmetric random matrices. Acta Sci. Math. (Szeged) 63, 3-4 (1997), 383–395.

[PP] Pajor, A. et Pastur, L. Communication personnelle.

[Pao] Paouris, G. Concentration of mass and central limit properties of isotropic convex bodies. Proc. Amer. Math. Soc. 133, 2 (2005), 565–575 (électronique).

[Per] Peres, A. Separability criterion for density matrices. Phys. Rev. Lett. 77, 8 (1996), 1413–1415.

[Pis] Pisier, G. The volume of convex bodies and Banach space geometry, vol. 94 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.

[Pré] Prékopa, A. On logarithmic concave measures and functions. Acta Sci. Math. (Szeged) 34 (1973), 335–343.

[RR] Rachev, S. T. et Rüschendorf, L. Mass transportation problems. Vol. I. Probability and its Applications (New York). Springer-Verlag, New York, 1998. Theory.

[RS] Rogers, C. A. et Shephard, G. C. Convex bodies associated with a given convex body. J. London Math. Soc. 33 (1958), 270–281.

[Rud] Rudelson, M. Random vectors in the isotropic position. J. Funct. Anal. 164, 1 (1999), 60–72.

[RMNDMC] Rungta, P., Munro, W., Nemoto, K., Deuar, P., Milburn, G. et Caves, C. Qudit entanglement. In Dan Walls Memorial Volume. Springer, Berlin, 2000. quant-ph/0001075.

[RW] Ruskai, M. B. et Werner, E. A Pair of Optimal Inequalities Related to the Error Function. quant-ph/9711207, 1997.

[SSZ] Schechtman, G., Schlumprecht, T. et Zinn, J. On the Gaussian measure of the intersection. Ann. Probab. 26 (1998), 346–357.

[Sie] Sierpiński, W. Sur la question de la mesurabilité de la base de M. Hamel. Fund. Math. 1 (1920), 105–111.

[Sim] Simon, B. Notes on infinite determinants of Hilbert space operators. Advances in Math. 24, 3 (1977), 244–273.

[Smi] Smithies, F. Integral equations. Cambridge Tracts in Mathematics and Mathematical Physics, no. 49. Cambridge University Press, New York, 1958.

[Sod] Sodin, S. On the smallest singular value of a bernoulli random matrix (following Bai and Yin). Appendice d’une prépublication de Artstein-Friedland-Milman “More geometric applications of Chernoff inequalities", 2005.

[Sos] Soshnikov, A. Universality at the edge of the spectrum in Wigner random matrices. Comm. Math. Phys. 207, 3 (1999), 697–733.

[Sve] Svetlichny, G. On the Foundations of Experimental Statistical

Sciences. www.mat.puc-rio.br/~svetlich/files/statsci.pdf, 1979.

[Sza] Szarek, S. Volume of separable states is super-doubly-exponentially small in the number of qubits. Phys. Rev. A (à paraître).

[ST] Szarek, S. et Tomczak-Jaegermann, N. On nearly Euclidean decomposition for some classes of Banach spaces. Compositio Math. 40, 3 (1980), 367–385.

[SW] Szarek, S. et Werner, E. A nonsymmetric correlation inequality for Gaussian measure. J. Multivariate Anal. 68 (1999), 193–211.

[Sze] Szegő, G. Orthogonal polynomials, third ed. American Mathematical Society, Providence, R.I., 1967. American Mathematical Society Colloquium Publications, Vol. 23.

[Tal] Talagrand, M. Spin glasses : a challenge for mathematicians, vol. 46 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer-Verlag, Berlin, 2003. Cavity and mean field models.

[Tom] Tomczak-Jaegermann, N. Banach-Mazur distances and finitedimensional operator ideals, vol. 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.

[TW1] Tracy, C. A. et Widom, H. Level-spacing distributions and the Airy kernel. Comm. Math. Phys. 159, 1 (1994), 151–174.

[TW2] Tracy, C. A. et Widom, H. On orthogonal and symplectic matrix ensembles. Comm. Math. Phys. 177, 3 (1996), 727–754.

[Ver] Vershynin, R. Frame expansions with erasures : an approach through the non-commutative operator theory. Appl. Comput. Harmon. Anal. 18, 2 (2005), 167–176.

[YBK] Yin, Y. Q., Bai, Z. D. et Krishnaiah, P. R. On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix. Probab. Theory Related Fields 78, 4 (1988), 509–521.

[ŻHSL] Życzkowski, K., Horodecki, P., Sanpera, A. et Lewenstein, M. On the volume of the set of mixed entangled states. Phys. Rev. A 58 (1998), 883–892.

[ŻS] Życzkowski, K. et Sommers, H.-J. Hilbert-schmidt volume of the set of mixed quantum states. J. Phys. A : Math. Gen. 36 (2003), 10115– 10130.