# Quantum expanders and geometry of operator spaces

Gilles Pisier

► To cite this version:

Gilles Pisier. Quantum expanders and geometry of operator spaces. Journal of the European Mathematical Society, 2014, 16, pp.1183 - 1219. 10.4171/jems/458. hal-05460824

HAL Id: hal-05460824

https://hal.science/hal-05460824v1

Submitted on 15 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Gilles Pisier

# Quantum expanders and geometry of operator spaces

Received September 11, 2012 and in revised form March 20, 2013

**Abstract.** We show that there are well separated families of quantum expanders with asymptotically the maximal cardinality allowed by a known upper bound. This has applications to the “growth” of certain operator spaces: It implies asymptotically sharp estimates for the growth of the multiplicity of $M_N$-spaces needed to represent (up to a constant $C > 1$) the $M_N$-version of the $n$-dimensional operator Hilbert space $OH_n$ as a direct sum of copies of $M_N$. We show that, when $C$ is close to 1, this multiplicity grows as $\exp(\beta nN^2)$ for some constant $\beta > 0$. The main idea is to relate quantum expanders with “smooth” points on the matricial analogue of the Euclidean unit sphere. This generalizes to operator spaces a classical geometric result on $n$-dimensional Hilbert space (corresponding to $N = 1$). In an appendix, we give a quick proof of an inequality (related to Hastings’s previous work) on random unitary matrices that is crucial for this paper.

**Keywords.** Quantum expander, operator space, completely bounded map, smooth point

The term “quantum expander” is used by Hastings [11] and by Ben-Aroya and Ta-Shma [3] to designate a sequence $\{U^{(N)} | N \ge 1\}$ of $n$-tuples $U^{(N)} = (U_1^{(N)}, \dots, U_n^{(N)})$ of $N \times N$ unitary matrices such that there is an $\varepsilon > 0$ satisfying the following “spectral gap” condition:

$$ \forall N \forall x \in M_N \quad \left\| \sum_{j=1}^{n} U_j^{(N)} (x - N^{-1} \operatorname{tr}(x)) U_j^{(N)*} \right\|_2 \le n(1-\varepsilon) \|x - N^{-1} \operatorname{tr}(x)\|_2, \quad (0.1) $$

where $\| \cdot \|_2$ denotes the Hilbert–Schmidt norm on $M_N$. More generally, the term is extended to the case when this is only defined for infinitely many $N$’s, and also to $n$-tuples of matrices satisfying merely $\sum_j U_j^{(N)} U_j^{(N)*} = \sum_j U_j^{(N)*} U_j^{(N)} = nI$.

We will say that an $n$-tuple $U^{(N)}$ satisfying (0.1) is an $\varepsilon$-quantum expander. We refer the reader to the survey [2] for more information and references on quantum expanders.

In analogy with the classical expanders (see below), one seeks to exhibit (and hopefully to construct explicitly) sequences $\{U^{(N_m)} | m \ge 1\}$ of $n$-tuples of $N_m \times N_m$ unitary matrices that are $\varepsilon$-quantum expanders with $N_m \to \infty$ while $n$ and $\varepsilon > 0$ remain fixed.

<footnote>G. Pisier: Texas A&M University, College Station, TX 77843, U.S.A., and Université Paris VI, Inst. Math. Jussieu, Equipe d’Analyse, Case 186, 75252 Paris Cedex 05, France; e-mail: pisier@math.tamu.edu</footnote>

<footnote>Mathematics Subject Classification (2010): Primary 46L07, 47L25, 46B85; Secondary 46B09</footnote>
When $G$ is a finite group generated by $S = \{t_1, \dots, t_n\}$ the associated Cayley graph $\mathcal{G}(G, S)$ is said to have a spectral gap if the left regular representation $\lambda_G$ satisfies

$$ \left\| \sum \lambda_G(t_j)_{|\mathbb{I}|} \right\| < n(1 - \varepsilon) \qquad (0.2) $$

where $\mathbb{I}$ denotes the constant function 1 on $G$. Obviously, this is equivalent to the condition that the unitaries $U_j = \lambda_G(t_j)$ satisfy (0.1) when restricted to diagonal matrices $x$ (here $N = |G|$). In this light, quantum expanders appear as a non-commutative version of the classical ones.

More precisely, (0.2) holds iff the unitaries $U_j = \lambda_G(t_j)$ satisfy (0.1) for all $x$ in the orthogonal complement of the right translation operators. This is easy to deduce from the decomposition into irreducibles of $\lambda_G \otimes \bar{\lambda}_G$, in which the component of the trivial representation corresponds to the restriction to the right translation operators.

In addition, for any irreducible representation $\pi$ of $G$, (0.2) implies that the unitaries $(\pi(t_j))$ satisfy (0.1) because the non-trivial irreducible components of the representation $\pi \otimes \bar{\pi}$ are contained in $\lambda_G$. See Remark 1.6 for more on this.

A sequence of Cayley graphs $\mathcal{G}(G^{(m)}, S^{(m)})$ constitutes an expander in the usual sense if (0.2) is satisfied with $\varepsilon > 0$ and $n$ fixed while $|G^{(m)}| \to \infty$.

Expanders (equivalently expanding graphs) have been extremely useful, especially (in the applied direction) since Margulis and Lubotzky–Phillips–Sarnak obtained explicit constructions (as opposed to random ones). We refer to [17, 12] for more information and references.

They have also been used with great success for operator algebras and in operator theory (see e.g. [35, 6, 13], and also [27, 5]). In [13], it is crucial that when the dimensions $N, N'$ are suitably different, say if $N$ is much larger than $N'$, and $U^{(N)}$ satisfies (0.1), then $U^{(N)}$ and $U^{(N')}$ are separated in the sense that there is a fixed $\delta = \delta(\varepsilon) > 0$ such that for all $x \in M_{N \times N'}$, $\| \sum_j U_j^{(N)} x U_j^{(N')*} \|_2 \le n(1 - \delta) \|x\|_2$ (see Remark 1.13).

Motivated by operator theory considerations, it is natural to wonder what happens when $N = N'$. We will say that two $n$-tuples $u = (u_j)$ and $v = (v_j)$ of $N \times N$ unitary matrices are $\delta$-separated if

$$ \forall x \in M_N \quad \left\| \sum_{j=1}^{n} u_j x v_j^* \right\|_2 \le n(1 - \delta) \|x\|_2. $$

Equivalently this means that

$$ \left\| \sum_{j=1}^{n} u_j \otimes \bar{v}_j \right\| \le n(1 - \delta) $$

where $\bar{v}_j$ denotes the complex conjugate of the matrix $v_j$, and the norm is the operator norm on $\ell_2^N \otimes \bar{\ell}_2^N$. This can be interpreted in operator space theory as a rough sort of orthogonality related to the “operator space Hilbert space OH”.

Note for example that when (0.2) holds then, for any pair of inequivalent irreducible representations $\pi, \sigma$ on $G$, the $n$-tuples $(\pi(t_j))$ and $(\sigma(t_j))$ are $\varepsilon$-separated.
Let $U(N) \subset M_N$ denote the group of unitary matrices. The main result of §1 asserts that for any $0 < \delta < 1$ there is a constant $\beta = \beta_\delta > 0$ such that for each $0 < \varepsilon < 1$, for all sufficiently large integers $n$ (i.e. $n \ge n_0(\varepsilon, \delta)$), for any integer $N$ there is a $\delta$-separated family $\{u(t) | t \in T\} \subset U(N)^n$ of $\varepsilon$-quantum expanders such that

$$|T| \ge \exp(\beta n N^2).$$

Thus we can “pack” as many as $m = \exp(\beta n N^2)$ $\delta$-separated $\varepsilon$-quantum expanders inside $U(N)^n$. This number $m$ is remarkably large. In fact, in some sense it is as large as it can be. Indeed, it is known ([37, 10], see also Remark 1.5) that the maximal $m$ is at most $\exp(\beta'n N^2)$ for some constant $\beta'$.

In §2, we use quantum expanders to investigate the analogue for operator spaces of a well known geometric property of Euclidean space: The unit sphere in a Hilbert space is smooth. Equivalently all its points admit a unique norming functional. In our extension of this, “norming” will be with respect to the operator space duality. Moreover, unicity has to be understood modulo an equivalence relation: for any $x = (x_j) \in M_N(E)^n$ we define $\text{Orb}(x)$ as the set of all $x'$ of the form $x' = (ux_jv) \in M_N(E)^n$ for some $u, v \in U(N)$. Then if $x$ is “norming” some point, any $x' \in \text{Orb}(x)$ is also “norming” that same point. When $E$ is an operator space and $x \in M_N(E)$, we will say that $y \in M_N(E^*) M_N$-norms $x$ if $\|\sum x_j \otimes y_j\| = \|x\|_{M_N(E)} \|y\|_{M_N(E^*)}$. We will say that $x$ is $M_N$-smooth in $M_N(E)$ if the only points $y$ with $\|y\|_{M_N(E^*)} = 1$ that $M_N$-norm $x$ are all in a single orbit in $M_N(E^*)$. Let us now turn to the case $E = \text{OH}_n$. There we show that, if $x \in U(N)^n$ is viewed as an element of $M_N(\ell_2^n)$, then $x$ is $M_N$-smooth in $M_N(E)$ iff $x$ is an $\varepsilon$-quantum expander for some $\varepsilon > 0$.

More generally, in Lemma 1.12 we prove a more precise quantified version of this: if $x$ is an $\varepsilon$-quantum expander and if two points $y, z \in M_N(E^*)$ both $M_N$-norm $x$ up to some error $\delta$, then the distance of the orbits $\text{Orb}(y)$ and $\text{Orb}(z)$ is uniformly small, i.e. majorized by a function $f_\varepsilon(\delta)$ that tends to 0 when $\delta \to 0$. Here the distance is meant with respect to the renormalized Euclidean norm $y \mapsto (nN)^{-1/2}\|y\|_2$ for which any $y \in U(N)^n$ has norm 1 (where $\| \cdot \|_2$ denotes the norm in $\ell_2(n \times N^2)$).

This also has a geometric application. Consider the following problem for an $n$-dimensional normed space $E$: Given a constant $C > 1$, estimate the minimal number $k = k_E(C)$ of functionals $f_1, \dots, f_k$ in the dual $E^*$ such that

$$\forall x \in E \quad \sup_{1 \le j \le k} |f_j(x)| \le \|x\| \le C \quad \sup_{1 \le j \le k} |f_j(x)|.$$

Geometrically this means that (in the real case) the symmetric convex body that is the unit ball of $E^*$ is equivalent (up to the factor $C$) to a polyhedron with vertices included in $\{\pm f_j\}$ and hence with at most $2k$ vertices (so its polar, which is equivalent to the unit ball of $E$, has at most $2k$ faces). For instance, the $n$-dimensional cube has $2^n$ vertices and $2n$ faces. When $E$ has (real) dimension $n$ it is well known (see e.g. [25, pp. 49–50]) that

$$k_E(C) \le \left( \frac{3C}{C-1} \right)^n.$$
For example if $C = 2$ we have $k_E(C) \le 6^n$. This exponential order of growth in $n$ is optimal for $E = \ell_2^n$ (or $\ell_p^n$ for $1 \le p < \infty$); but of course $k_E(C) = n$ for $E = \ell_\infty^n$, and there is important available information and a conjecture (see [22]) about conditions on a general sequence $\{E(n) | n \ge 1\}$ with $\dim(E(n)) = n$ ensuring that $k_{E(n)} \ge \exp(O(n))$ for some $c > 0$.

We now describe the matricial analogue of $k_E$ that we estimate using quantum expanders. Let $E$ be an operator space. Fix an integer $N \ge 1$. We denote by $k_E(N, C)$ the smallest $k$ such that there are linear maps $f_j : E \to M_N(1 \le j \le k)$ satisfying

$$ \forall x \in M_N(E) \quad \sup_{1 \le j \le k} \|(\mathrm{Id} \otimes f_j)(x)\|_{M_N(M_N)} \le \|x\|_{M_N(E)} \\ \le C \sup_{1 \le j \le k} \|(\mathrm{Id} \otimes f_j)(x)\|_{M_N(M_N)}. $$

It is not hard to adapt the corresponding Banach space argument to show that for any $n$-dimensional $E$, any $C > 1$ and any $N$ we have

$$ k_E(N, C) \le \left( \frac{3C}{C-1} \right)^{2nN^2} = \exp\left( 2\log\left(\frac{3C}{C-1}\right) nN^2 \right). $$

Using the “packing” of $\epsilon$-quantum expanders described above, we can show that the operator space version of Hilbert space (i.e. the space $OH$ from [26]) satisfies a lower bound of the same order of growth, namely we show for $E = OH_n$ (see Theorem 2.8) that there are numbers $C_1 > 1$ and $b > 0$ such that for any $n$ large enough and any $N$ we have

$$ k_E(N, C_1) \ge \exp(bnN^2). \qquad (0.3) $$

Moreover, this also holds for $E = \ell_1^n$ with its maximal operator space structure and for $E = R_n + C_n$ (see Remark 2.10).

We also show (see Theorem 2.15) that for any $R > 1$ and for any $n, N$ suitably large there is a collection $\{E_t | t \in T_1\}$ of $n$-dimensional subspaces of $M_N$ (each spanned by an $n$-tuple of unitary matrices) with cardinality $\ge \exp(\beta_R nN^2)$ such that the cb-distance $d_{cb}(E_s, E_t)$ of any distinct pair in $T_1$ satisfies

$$ d_{cb}(E_s, E_t) \ge R. $$

The cb-distance $d_{cb}$ is the analogue of the Banach–Mazur distance for operator spaces. The preceding shows that the metric entropy of the space of $n$-dimensional operator spaces equipped with the (so-called) “distance” $d_{cb}$ is extremely large for small distances. This can be viewed as a somewhat more quantitative version of the non-separability of the space of $n$-dimensional operator spaces first proved in [13]. We plan to return to this in a future publication (see [30]).

The above (0.3) suggests that the class of finite-dimensional operator spaces $E$ such that $(\log k_E(N, C))/N^2 \to 0$ should be investigated. We call such spaces matricially sub-Gaussian.

In the forthcoming paper [29] we introduce a class of operator spaces, which we call “subexponential”, for which the same Grothendieck type factorization theorem from
[13, 31] still holds (see the recent paper [32] for simpler proofs of the latter). We also give there examples of non-exact subexponential operator spaces or $C^*$-algebras.

The definition of “subexponential” involves the growth of a sequence of integers $N \mapsto K_E(N, C)$ attached to an operator space $E$ (and a constant $C > 1$), in a way that is similar but seems different from $k_E(N, C)$. We denote by $K_E(N, C)$ the smallest $K$ such that there is a single (embedding) linear map $f: E \to M_K$ satisfying

$$ \forall x \in M_N(E) \quad \|(\mathrm{Id} \otimes f)(x)\|_{M_N(M_K)} \le \|x\|_{M_N(E)} \le C \|(\mathrm{Id} \otimes f)(x)\|_{M_N(M_N)}. $$

Roughly the latter sequence is bounded iff $E$ is exact with exactness constant $\le C$ (in the sense of [27, §17]) while it is such that $(\log K_E(N, C))/N \to 0$ iff $E$ is $C$-subexponential.

**Note.** There is an obvious upper bound (for a fixed constant $C$) $K_E(N, C) \le Nk_E(N, C)$, so the growth of $K_E$ is dominated by that of $k_E$, but we know nothing in the converse direction. Various other questions are mentioned at the end of §3.

# 1. Quantum expanders

Fix integers $n, N$. Throughout this paper we denote by $M_N$ the space of $N \times N$ complex matrices and by $U(N)$ the subset of $N \times N$ unitary matrices.

We identify $M_N$ with the space $B(\ell_2^N)$ of bounded operators on the $N$-dimensional Hilbert space denoted by $\ell_2^N$.

We denote by tr (resp. $\tau_N$) the usual trace (resp. the normalized trace) on $M_N$. Thus $\tau_N = N^{-1}$ tr. We denote by $S_2^N$ the Hilbert space obtained by equipping $M_N$ with the corresponding scalar product. The associated norm is the classical Hilbert–Schmidt norm.

For simplicity we write

$$ H = L_2(\tau_N), $$

i.e. $H$ is the Hilbert space obtained by equipping the space $M_N$ with the norm

$$ \|\xi\|_H = (N^{-1} \mathrm{tr}(|\xi|^2))^{1/2} = N^{-1/2} \|x\|_{S_2^N}. $$

We denote

$$ H_0 = \{I\}^{\perp} \subset H. $$

Throughout this paper, we consider operators of the form $T = \sum x_j \otimes \bar{y}_j$, with $x_j, y_j \in M_N$, that we view as acting on $\ell_2^N \otimes \overline{\ell_2^N}$. Identifying as usual $\ell_2^N \otimes \overline{\ell_2^N}$ with $S_2^N$, we may consider $T$ as an operator acting on $M_N$ defined by

$$ \forall \xi \in M_N \quad T(\xi) = \sum x_j \xi y_j^*, $$

and we then have

$$ \begin{aligned} \left\| \sum x_j \otimes \bar{y}_j \right\| &= \sup \left\{ \left\| \sum x_j \xi y_j^* \right\|_2 \mid \xi \in M_N, \|\xi\|_2 \le 1 \right\} \\ &= \sup \left\{ \left| \sum \mathrm{tr}(x_j \xi y_j^* \eta^*) \right| \mid \|\xi\|_2 \le 1, \|\eta\|_2 \le 1 \right\}, \end{aligned} \quad (1.1) $$
or equivalently $\| \sum x_j \otimes \bar{y}_j : \ell_2^N \otimes \overline{\ell_2^N} \to \ell_2^N \otimes \overline{\ell_2^N} \| = \|T : S_2^N \to S_2^N \|$. Actually it will be convenient to view $T$ as an operator acting on $H = L_2(\tau_N)$. We have trivially

$$ \|T\|_{B(H)} = \|T\|_{B(S_2^N)}. $$

Let $x = (x_j) \in (M_N)^n$ and $y = (y_j) \in (M_N)^n$. Let $\text{Orb}(x)$ denote the 2-sided unitary orbit of $x = (x_j)$, i.e.

$$ \text{Orb}(x) = \{(ux_jv) \mid u, v \in U(N)\}. $$

We will denote

$$ d(x, y) = \left( \sum_j \|x_j - y_j\|_{L_2(\tau_N)}^2 \right)^{1/2}, $$

and

$$ d'(x, y) = \inf\{d(x', y) \mid x' \in \text{Orb}(x)\} = \inf\{d(x', y') \mid x' \in \text{Orb}(x), y' \in \text{Orb}(y)\}. $$

The last equality holds because of the 2-sided unitary invariance of the norm in $S_2^N$ or equivalently of $H = L_2(\tau_N)$.

**Definition 1.1.** Fix $\delta > 0$. We will say that $x, y$ in $M_N^n$ are $\delta$-separated if

$$ \left\| \sum x_j \otimes \bar{y}_j \right\| \le (1 - \delta) \left\| \sum x_j \otimes \bar{x}_j \right\|^{1/2} \left\| \sum y_j \otimes \bar{y}_j \right\|^{1/2}. $$

A family of elements is called $\delta$-separated if any two distinct members in it are $\delta$-separated.

Let $x = (x_j) \in M_N^n$ and $y = (y_j) \in M_N^n$ be normalized so that $\| \sum x_j \otimes \bar{x}_j \| = \| \sum y_j \otimes \bar{y}_j \| = 1$. Equivalently, this definition means that for any $\xi, \eta \in M_N$ in the unit ball of $S_2^N$ we have

$$ \left| \sum \operatorname{tr}(x_j \xi y_j^* \eta^*) \right| \le 1 - \delta. $$

Using polar decompositions $\xi = u|\xi|$ and $\eta = v|\eta|$, we obtain $\left| \sum \operatorname{tr}(x_j \xi y_j^* \eta^*) \right| = \left| \sum \operatorname{tr}(x_j u |\xi| y_j^* |\eta| v^*) \right|$. Let $\hat{x}_j = v^* x_j u$. Equivalently we have, for any unitary $u, v$,

$$ \left| \sum \operatorname{tr}(\hat{x}_j |\xi| y_j^* |\eta|) \right| \le 1 - \delta. $$

A fortiori, taking $|\xi| = |\eta| = N^{-1/2}I$ we find $|\sum \tau_N(\hat{x}_j y_j^*)| \le 1 - \delta$ and hence

$$ d(\hat{x}, y)^2 \ge 2\delta; $$

taking the inf over unitary $u, v$, the $\delta$-separation of $x, y$ implies

$$ d'(x, y) \ge (2\delta)^{1/2}. \qquad (1.2) $$

In other words, rescaling this to the case when $n^{1/2}x_j, n^{1/2}y_j, \xi, \eta$ are all unitary, we have proved:
**Lemma 1.2.** Consider n-tuples $x = (x_j) \in U(N)^n$ and $y = (y_j) \in U(N)^n$. If $x, y$ are $\delta$-separated then $d'(x, y) \ge (2\delta n)^{1/2}$.

Recall that we denote

$$H_0 = \{I\}^{\perp}.$$

To any n-tuple $u = (u_j) \in U(N)^n$ we associate the operator $(\sum u_j \otimes \bar{u}_j)(1-P)$ on $\ell_2^N \otimes \bar{\ell}_2^N$ where $P$ denotes the $\perp$-projection onto the scalar multiples of $I = \sum e_j \otimes \bar{e}_j$. Equivalently, up to normalization, we will consider $T_u : H_0 \to H_0$ defined for all $\xi \in H_0$ by

$$T_u(\xi) = \sum u_j \xi u_j^*.$$

We will denote by

$$S_{\varepsilon} = S_{\varepsilon}(n, N) \subset U(N)^n$$

the set of all n-tuples $u = (u_j) \in U(N)^n$ such that

$$\|T_u : H_0 \to H_0\| \le \varepsilon n.$$

Equivalently, this means that for all $x \in M_N$, we have

$$\left\| \sum u_j (x - \tau_N(x)I) u_j^* \right\|_H \le \varepsilon n \|x\|_H.$$

Our goal is to prove the following:

**Theorem 1.3.** For any $0 < \delta < 1$ there is a constant $\beta_\delta > 0$ such that for each $0 < \varepsilon < 1$ and for all sufficiently large integers $n$ (i.e. $n \ge n_0$ with $n_0$ depending on $\varepsilon$ and $\delta$) and for all $N \ge 1$, there is a $\delta$-separated subset $T \subset S_\varepsilon$ such that $|T| \ge \exp(\beta_\delta n N^2)$.

**Remark 1.4.** Actually, the proof will show that if we are given sets $A_N \subset U(N)^n$ such that $\inf_N \mathbb{P}(A_N) \ge \alpha > 0$, then for each $N$ we can find a subset $T$ as above contained in $A_N \cap S_\varepsilon$, but with $\beta_\delta$ and $n_0$ now also depending on $\alpha$.

**Remark 1.5.** The order of growth of our lower bound $\exp(\beta n N^2)$ in Theorem 1.3 is roughly optimal because of the upper bound given explicitly in [10] (and implicitly in [37]). The latter upper bound can be proved as follows. Let $m_{\max}$ be the maximal number of a $\delta$-separated family in $U(N)^n$. Consider the normed space obtained by equipping $M(N)^n$ with the norm $|||x||| = \| \sum x_j \otimes \bar{x}_j \|^{1/2}$. Then since its (real) dimension is $2nN^2$, by a well known volume argument [25, pp. 49–50] there cannot exist more than $(1 + 2/\delta')^{2nN^2}$ elements in its unit ball at mutual $||| \cdot |||$-distance $\ge \delta'$. Note that $d(x, y) \le |||x - y|||$ for any pair $x, y$ in $M(N)^n$. Thus, if $u, v \in U(N)^n$ are $\delta$-separated in the above sense then $x = n^{-1/2}u$ and $y = n^{-1/2}v$ are in the $||| \cdot |||$-unit ball and by (1.2) we have $|||x - y||| \ge (2\delta)^{1/2}$, therefore

$$m_{\max} \le (1 + \sqrt{2/\delta})^{2nN^2} \le \exp\{2\sqrt{2/\delta} n N^2\}.$$
**Remark 1.6.** Let $G$ be a Kazhdan group (see [1]) with generators $t_1, \dots, t_n$, so that there is $\delta > 0$ such that $\| \sum_{j=1}^n \pi(t_j) \| \le n(1-\delta)$ for any unitary representation without any invariant (non-zero) vector. Let $\mathcal{I} = \mathcal{I}(N)$ denote the set of $N$-dimensional irreducible representations $\pi : G \to U(N)$. It is known (see [1]) that the latter set is finite and in fact there is a uniform bound on $|\mathcal{I}(N)|$ for each $N$. For any $\pi \in \mathcal{I}$ we set

$$u_j^\pi = \pi(t_j).$$

Then (here by $\pi \neq \sigma$ we mean $\pi$ is not equivalent to $\sigma$)

$$\sup_{\pi \neq \sigma \in \mathcal{I}} \left\| \sum_j u_j^\pi \otimes \bar{u}_j^\sigma \right\| \le n(1-\delta),$$

so that the family $\{u^\pi | \pi \in \mathcal{I}\} \subset U(N)^n$ is $\delta$-separated in the above sense. By Remark 1.5, we know $|\mathcal{I}(N)| \le m_{\max} \le \exp(c_\delta nN^2)$. The problem to estimate the maximal possible value of $|\mathcal{I}(N)|$ when $N \to \infty$ (with $\delta$ and $n$ remaining fixed, but $G$ possibly varying) is investigated in [19]: some special cases are constructed for which $|\mathcal{I}(N)|$ grows like $\exp(cN)$; however, we feel that Theorem 1.3 gives evidence that there should exist cases for which $|\mathcal{I}(N)|$ grows like $\exp(cN^2)$.

**Remark 1.7.** Recall (see [27, p. 324, Th. 20.1]) that for any $n$-tuple of unitary operators on any Hilbert space $H$ we have

$$\left\| \sum_j u_j \otimes \bar{u}_j \right\| \ge 2\sqrt{n-1}.$$

Note that $2\sqrt{n-1} < n$ for all $n \ge 3$ (so there is also an $0 < \varepsilon < 1$ such that $2\sqrt{n-1} + \varepsilon n < n$).

Let $0 < \varepsilon < 1$. In analogy with Ramanujan graphs (see [17]) an $n$-tuple $u = (u_j)$ in $U(N)^n$ will be called $\varepsilon$-Ramanujan if

$$\|T_u : H_0 \to H_0\| \le 2\sqrt{n-1} + \varepsilon n.$$

We will denote by

$$R_\varepsilon = R_\varepsilon(n, N) \subset U(N)^n$$

the set of all such $n$-tuples.

We refer to [17, 12] for more information on expanders and Ramanujan graphs.

The next result due to Hastings [11] has been a crucial inspiration for our work:

**Lemma 1.8 (Hastings).** If we equip $U(N)^n$ with its normalized Haar measure $\mathbb{P}$, then for each $n$ and $\varepsilon > 0$ the set $R_\varepsilon(n, N)$ defined above satisfies

$$\lim_{N \to \infty} \mathbb{P}(R_\varepsilon(n, N)) = 1.$$
This is best possible in the sense that Lemma 1.8 fails if $2\sqrt{n}-1$ is replaced (in the definition of $R_\epsilon(n, N)$) by any smaller number. However, we do not really need this sharp form of Lemma 1.8 (unless we insist on making $n_0(\epsilon)$ as small as possible in Theorem 1.3). So we give in the appendix a quicker proof of a result that suffices for our needs (where $2\sqrt{n}-1$ is replaced by $C'\sqrt{n}$, $C'$ being a numerical constant) and which in several respects gives us better estimates than Lemma 1.8.

Lemma 1.9 below can be viewed as a non-commutative variant of results in [24] (see also [23] where the non-commutative case is already considered) in the style of [18] (see also [7, 21]). We view this as a (weak) sort of non-commutative Sauer lemma, which it might be worthwhile to strengthen.

In the next two lemmas, we equip $U(N)^n$ with the metric $d$ (we also use $d'$), and for any subset $A \subset U(N)^n$ and any $\epsilon > 0$ we denote by $N(A, d, \epsilon)$ the smallest number of open $d$-balls of radius $\epsilon$ with center in $U(N)^n$ that cover $A$.

**Lemma 1.9.** Let $a > 0$. Let $A \subset U(N)^n$ be a (measurable) subset with $\mathbb{P}(A) > a$. Then, for any $c < \sqrt{2}$, $N(A, d, c\sqrt{n}) \ge a \exp(KrnN^2)$ where $r = (1-c^2/2)^2$ and $K$ is a universal constant. Assuming moreover that $a \ge \exp(-KrnN^2/2)$ (note that there is $n_0(a, r)$ such that this holds for all $n \ge n_0(a, r)$ and all $N \ge 1$), we find that $N(A, d, c\sqrt{n}) \ge \exp(bnN^2)$ where $b = Kr/2$.

*Proof.* Let $\Omega = U(N)^n$. We may clearly assume (by Haar measure inner regularity) that $A$ is compact. Let $\mathcal{N} = N(A, d, c\sqrt{n})$. By definition, $A$ is included in the union of $\mathcal{N}$ open balls with $d$-radius $c\sqrt{n}$. By translation invariance of $d$ and $\mathbb{P}$, all these balls have the same $\mathbb{P}$-measure equal to $F(c)$. Therefore $a < \mathbb{P}(A) \le \mathcal{N}F(c)$ and hence

$$aF(c)^{-1} < \mathcal{N}.$$

Thus we need a lower bound for $F(c)^{-1}$. Let $u$ denote the unit in $U(N)^n$ so that $u_j = 1$ for $1 \le j \le n$. Using a ball centered at $u$ to compute $F(c)$, we have

$$F(c) = \mathbb{P}\{\omega \in U(N)^n \mid \sum_{j=1}^{n} \mathrm{tr}(|\omega_j - 1|^2) < c^2 n N\}.$$

Since $\sum_{j=1}^n \mathrm{tr}(|\omega_j - 1|^2) = 2Nn - 2 \sum_{j=1}^n \Re \mathrm{tr}(\omega_j)$, we have

$$F(c) = \mathbb{P}\{\omega \mid \sum_{j=1}^{n} \Re \mathrm{tr}(\omega_j) > nN(1 - c^2/2)\}.$$

We will now use the known sub-Gaussian property of $\sum_{j=1}^n \Re \mathrm{tr}(\omega_j)$: there is a universal constant $K$ such that for any $\lambda > 0$ we have

$$\mathbb{P}\{\omega \mid \sum_{j=1}^{n} \Re \mathrm{tr}(\omega_j) > \lambda\} \le \exp(-K\lambda^2/n). \quad (1.3)$$

Taking this for granted, let us complete the proof. Fix $c < \sqrt{2}$. Recalling $r = (1-c^2/2)^2 > 0$, this yields

$$F(c) \le \exp(-KnN^2r).$$
Thus we conclude that

$$N > a \exp(KrnN^2).$$

Taking $c = 1$, $r = 1/4$, the last assertion becomes obvious.

Let us now give a quick argument for the known inequality (1.3): We will denote by $Y^{(N)}$ a random $N \times N$-matrix with i.i.d. complex Gaussian entries with mean zero and second moment equal to $N^{-1/2}$, and we denote by $(Y_j^{(N)})$ a sequence of i.i.d. copies of $Y^{(N)}$. It is well known that the polar decomposition $Y^{(N)} = U|Y^{(N)}|$ is such that $U$ is uniformly distributed over $U(N)$ and independent of $|Y^{(N)}|$. Moreover there is an absolute constant $\chi > 0$ such that $\mathbb{E}|Y^{(N)}| = \chi^{-1}I$. See e.g. [18, p. 80]. Therefore, we have a conditional expectation operator $\mathcal{E}$ (corresponding to integrating the modular part) such that $\sum \mathfrak{R} \operatorname{tr}(\omega_j) = \chi \mathcal{E}(\sum \mathfrak{R} \operatorname{tr}(Y_j^{(N)}))$, where $\omega_j$ denotes the unitary part in the polar decomposition of $Y_j^{(N)}$.

Then, since $x \mapsto \exp wx$ is convex for any $w > 0$, we have the announced sub-Gaussian property

$$\mathbb{E} \exp(w \sum \mathfrak{R} \operatorname{tr}(\omega_j)) \le \mathbb{E} \exp(w \chi \sum \mathfrak{R} \operatorname{tr}(Y_j^{(N)})) = \exp(\chi^2 w^2 n/4),$$

from which it follows, by Chebyshev's inequality, that $\mathbb{P}\{\sum \mathfrak{R} \operatorname{tr}(\omega_j) > \lambda\} \le \exp(\chi^2 w^2 n/4 - \lambda w)$, and optimising $w$ so that $\lambda = \chi^2 wn/2$ we finally obtain

$$\mathbb{P}\{\sum \mathfrak{R} \operatorname{tr}(\omega_j) > \lambda\} \le \exp(-K\lambda^2/n),$$

with $K = \chi^{-2}$. The above simple argument follows [18, Ch. 5], but, in essence, (1.3) can be traced back to [8, Lemma 3]. $\square$

The next lemma is a simple covering argument.

**Lemma 1.10.** Fix $b, c > 0$. Let $A \subset U(N)^n$ be a subset with $N(A, d, c\sqrt{n}) \ge \exp(bnN^2)$. Fix $c' < c$ and $b' < b$. Then there is an integer $n_0$ (depending only on $b - b'$ and $c - c'$ and independent of $N$) such that if $n \ge n_0$ we have $N(A, d', c'\sqrt{n}) \ge \exp(b'nN^2)$ and there is a subset $T' \subset A$ with $|T'| \ge \exp(b'nN^2)$ such that $d'(s, t) \ge c'\sqrt{n}$ whenewer $s \ne t \in T'$.

*Proof.* Fix $\varepsilon > 0$. It is well known that there is an $\varepsilon$-net $N_\varepsilon \subset U(N)$ with respect to the operator norm with $|N_\varepsilon| \le (K/\varepsilon)^{2N^2}$. Indeed, since the real dimension of $M_N$ is $2N^2$, a classical volume argument (see e.g. [25, pp. 49–50]) produces such a net inside the unit ball of $M_N$. It can then be adjusted to be inside $U(N)$. See also [33, p. 175] for more delicate estimates. For any $x \in U(N)^n$, we have $d(uxv, u'xv') \le (\|u - u'\| + \|v - v'\|)\sqrt{n}$ for any $u, u', v, v' \in U(N)$. Therefore we have $N(\mathrm{Orb}(x), d, 2\varepsilon\sqrt{n}) \le |N_\varepsilon|^2 \le \exp(4N^2) \log(K/\varepsilon)$. From this it follows immediately that

$$N(A, d, c'\sqrt{n} + 2\varepsilon\sqrt{n}) \le N(A, d', c'\sqrt{n}) \exp(4N^2) \log(K/\varepsilon).$$

Since $c' < c$ we can choose $\varepsilon > 0$ so that $c' + 2\varepsilon = c$. Then by our assumption $N(A, d, c'\sqrt{n} + 2\varepsilon\sqrt{n}) = N(A, d, c\sqrt{n}) \ge \exp(bnN^2)$. Thus we find

$$N(A, d', c'\sqrt{n}) \ge \exp(bnN^2) \exp(-4N^2) \log(K/\varepsilon).$$
Since $b-b' > 0$ there is clearly an integer $n_0$ (depending only on $b-b'$ and $\varepsilon = (c-c')/2$) such that $4 \log(K/\varepsilon) < (b-b')n$ for all $n \ge n_0$. Thus we obtain

$$N(A, d', c'\sqrt{n}) \ge \exp(b'nN^2).$$

The last assertion is then clear: any maximal subset $T' \subset A$ such that $d'(s, t) \ge c'\sqrt{n}$ for all $s \ne t \in T'$ must satisfy (by maximality) $N(A, d', c'\sqrt{n}) \le |T'|$. $\square$

In general, for a pair $u, v \in U(N)^n$, $\delta$-separation is a much stronger condition than separation with respect to the distance $d'$. The main virtue of the next two lemmas is to show that for a pair $u, v \in S_\varepsilon$ with $\varepsilon$ suitably small, the two conditions become essentially equivalent. To prove these, we will now crucially use the spectral gap.

**Lemma 1.11.** Let $0 < \varepsilon, \varepsilon' < 1$. Let $u = (u_j) \in U(N)^n$ and $v = (v_j) \in M_N^n$ be merely such that $\|\sum v_j \otimes \bar{v}_j\| \le n$. Assume $u \in S_\varepsilon$ and also

$$d'(u, v) \ge \sqrt{2n(1 - \varepsilon)}. \qquad (1.4)$$

Then

$$\left\| \sum u_j \otimes \bar{v}_j \right\| \le n(\varepsilon^{1/5}(2^{-4/5} + 2^{6/5}) + 2\varepsilon^{1/2}).$$

Moreover, if we assume in addition that $v \in S_\varepsilon$, then the preceding estimate can be improved to

$$\left\| \sum u_j \otimes \bar{v}_j \right\| \le n(3\varepsilon^{1/3} + 2\varepsilon). \qquad (1.5)$$

Conversely, it is easy to show that for any pair $u, v \in M_N^n$ such that $\sum \tau_N(|u_j|^2) = \sum \tau_N(|v_j|^2) = n$ (in particular for any $u, v \in U(N)^n$),

$$\left\| \sum u_j \otimes \bar{v}_j \right\| \le n\varepsilon' \qquad (1.6)$$

implies

$$d'(u, v) \ge \sqrt{2n(1 - \varepsilon)}. \qquad (1.7)$$

*Proof.* Let $\|v\|_H^2 = (1/n) \sum_j \tau_N|v_j|^2$. Note that $\|v\|_H \le 1$ and $\|u\|_H \le 1$. For any $x \in M_N$, we will denote $\|x\|_{L_2(\tau_N)} = (\tau_N|x|^2)^{1/2}$ and $\|x\|_{L_1(\tau_N)} = \tau_N|x|$. Note for later use that a consequence of Cauchy–Schwarz is

$$\forall x, y \in M_N \quad \|xy\|_{L_1(\tau_N)} \le \|x\|_{L_2(\tau_N)} \|y\|_{L_2(\tau_N)}. \qquad (1.8)$$

Recall that

$$\left\| \sum u_j \otimes \bar{v}_j \right\| = \sup \left\{ \left| \sum \tau_N(u_j x v_j^* y^*) \right| \mid x, y \in B_{L_2(\tau_N)} \right\}.$$

Let us denote $x.u.y = (xu_jy)_{1 \le j \le n}$ and let $F$ be the bilinear form on $M_N \times M_N$ defined by

$$F(x, y) = \langle x.u.y, v \rangle_H = \frac{1}{n} \sum_j \tau_N(xu_j yv_j^*).$$
Then

$$ \left\| \frac{1}{n} \sum_j u_j \otimes \bar{v}_j \right\| = \| F : L_2(\tau_N) \times L_2(\tau_N) \to \mathbb{C} \|. $$

We start with the proof of (1.5), assuming that both $u, v$ belong to $S_\epsilon$. Firstly we claim that for any $x, y \in M_N$ we have

$$ |F(x, y)| \le \tau_N |x|\tau_N |y| + \epsilon \|(1-P)(|x|)\|_{L_2(\tau_N)} \|(1-P)(|y|)\|_{L_2(\tau_N)} $$

and hence assuming $x, y \in B_{L_2(\tau_N)}$ we have

$$ |F(x, y)| \le \tau_N |x|\tau_N |y| + \epsilon. \quad (1.9) $$

To check this claim we use the polar decompositions $x = U|x|$, $y = V|y|$ and we write

$$ \begin{aligned} F(x, y) &= \langle U|x| \cdot u \cdot V|y|, v \rangle_{\mathcal{H}} = \frac{1}{n} \sum_j \tau_N (|x|^{1/2} u_j V|y|^{1/2}) [|y|^{1/2} v_j^* U|x|^{1/2}]) \\ &= \langle |x|^{1/2} \cdot u \cdot V|y|^{1/2}, |x|^{1/2} U^* v|y|^{1/2} \rangle_{\mathcal{H}}. \end{aligned} $$

Therefore

$$ |F(x, y)| \le \|x|^{1/2} \cdot u \cdot V|y|^{1/2}\|_{\mathcal{H}} \|x|^{1/2} U^* v|y|^{1/2}\|_{\mathcal{H}}. \quad (1.10) $$

Now we observe that if we denote again by $T_u$ the operator acting on $L_2(\tau_N)$ defined by $T_u(x) = \sum_j u_j x u_j^* - n \tau_N(x) I$ (equivalently $T_u = (\sum_j u_j \otimes \bar{u}_j)(1-P)$) we have, for any $a, b \in M_N$,

$$ \begin{aligned} \|a \cdot u \cdot b\|_{\mathcal{H}}^2 &= (1/n) \tau_N ((n \tau_N(bb^*) + T_u(bb^*))a^*a) \\ &= \tau_N(bb^*) \tau_N(a^*a) + (1/n) \tau_N(T_u(bb^*)a^*a) \end{aligned} $$

and hence, since $\|T_u\| \le \epsilon n$ and $T_u = (1-P)T_u(1-P)$,

$$ \|a \cdot u \cdot b\|_{\mathcal{H}}^2 \le \tau_N(bb^*) \tau_N(a^*a) + \epsilon \|(1-P)(bb^*)\|_{L_2(\tau_N)} \|(1-P)(a^*a)\|_{L_2(\tau_N)}. $$

This yields

$$ \| |x|^{1/2} \cdot u \cdot V|y|^{1/2} \|_{\mathcal{H}}^2 \le \tau_N |x| \tau_N |y| + \epsilon \|(1-P)(|x|)\|_{L_2(\tau_N)} \|(1-P)(|y|)\|_{L_2(\tau_N)}. $$

A similar bound holds for $\| |x|^{1/2} U^* v|y|^{1/2} \|_{\mathcal{H}}$. Thus (1.10) leads to our claim. Secondly by (1.4) for any $U, V \in U(N)$ we have

$$ \|U \cdot u \cdot V - v\|_{\mathcal{H}}^2 \ge n^{-1} d'(u, v)^2 \ge 2(1 - \epsilon') $$

and hence

$$ \Re \langle U \cdot u \cdot V, v \rangle_{\mathcal{H}} \le \epsilon'. $$

Recall that the unit ball of $M_N$ is the closed convex hull of $U(N)$. Thus we have

$$ \| F : M_N \times M_N \to \mathbb{C} \| \le \epsilon'. $$
Let us assume $x, y \in B_{L_2(\tau_N)}$. Let $p$ (resp. $q$) denote the spectral projection of $|x|$ (resp. $|y|$) corresponding to the spectral set $\{|x| \le \lambda\}$ (resp. $\{|y| \le \lambda\}$). Note that by Chebyshev's inequality we have $\tau_N(1-p) \le 1/\lambda^2$ (resp. $\tau_N(1-q) \le 1/\lambda^2$). Let $x' = (1-p)|x|$ and $y' = (1-q)|y|$. By (1.8) (since $\|1-p\|_{L_2(\tau_N)} \le \lambda^{-1/2}$) we have

$$ \tau_N |x'| \le \lambda^{-1}. $$

Similarly

$$ \tau_N |y'| \le \lambda^{-1}. $$

We now write

$$ F(|x|, |y|) = F(p|x|+x', q|y|+y') = F(p|x|, q|y|) + F(x', |y|) + F(p|x|, y'). \quad (1.11) $$

By (1.9) we have

$$ |F(x', |y|)| \le \tau_N |x'| \tau_N |y| + \varepsilon \le \lambda^{-1} + \varepsilon $$

and similarly

$$ |F(p|x|, y')| \le \lambda^{-1} + \varepsilon. $$

Thus we deduce from (1.11) that

$$ |F(|x|, |y|)| \le \varepsilon' \lambda^2 + 2(\lambda^{-1} + \varepsilon). $$

Choosing $\lambda = (\varepsilon')^{-1/3}$ to minimize over $\lambda > 0$ yields the upper bound $3\varepsilon'^{1/3} + 2\varepsilon$, when restricting to $x, y \ge 0$. Since our assumptions on the pair $u, v$ are shared by the pair $UuV, v$ for any $U, V \in U(N)$, we may apply the polar decompositions $x = U|x|$ and $y = V|y|$ to deduce the same upper bound for an arbitrary pair $x, y$. Thus we obtain (1.5).

We now turn to (1.4). There we assume only $u \in S_\varepsilon$ and $\| \sum v_j \otimes \bar{v}_j \| \le n$. Then (since we still have $\| |x|^{1/2} U^* v |y|^{1/2} \|_H \le 1$) inequality (1.9) can be replaced by

$$ |F(x, y)| \le (\tau_N |x| \tau_N |y| + \varepsilon)^{1/2}, \quad (1.12) $$

and the preceding reasoning leads to

$$ |F(x, y)| \le \varepsilon' \lambda^2 + 2(\lambda^{-1} + \varepsilon)^{1/2} \le \varepsilon' \lambda^2 + 2\lambda^{-1/2} + 2\varepsilon^{1/2}. $$

Choosing $\lambda = (2\varepsilon')^{-2/5}$ to minimize, we obtain the announced upper bound $\varepsilon'^{1/5}(2^{-4/5} + 2^{6/5}) + 2\varepsilon^{1/2}$, thus completing the proof of (1.4).

The converse implication (1.6) ⇒ (1.7) is obvious: Indeed, for any $U, V \in U(N)$, inequality (1.6) implies $|\sum \tau_N(Uu_j V v_j^*)| \le n\varepsilon'$ and hence since we assume $\sum \tau_N(u_j^* u_j) = \sum \tau_N(v_j^* v_j) = n$ we have

$$ d(U.u.V, t)^2 = 2n - 2\mathfrak{R} \sum \tau_N(Uu_j V v_j^*) \ge 2n(1 - \varepsilon'), $$

and taking the infimum over $U, V \in U(N)$ we obtain (1.7). $\square$

**Proof of Theorem 1.3.** Our original proof was based on Hastings's Lemma 1.8, but the current proof, based instead on (4.6), allows for more uniformity with respect to $N$. Note
however that if we could prove a sharper form of (1.5) (e.g. with $\epsilon$ in place of $2\epsilon$) then Lemma 1.8 would allow us to cover values of $n$ as small as $n = 3$, for all $N$ large enough (while using (4.6) requires $C'n^{-1/2} < n$).

By (4.6) there is a constant $C'$ such that

$$ \forall N \ge 1 \quad \mathbb{E} \left\| \sum_{j=1}^{n} U_j \otimes \bar{U}_j (1-P) \right\| \le C' \sqrt{n} $$

where $\mathbb{E}$ is with respect to the normalized Haar measure on $U(N)^n$. By Chebyshev's inequality, this implies $\mathbb{P}(S_\epsilon) > 1/2$ for all $N \ge 1$, assuming only that $n > n_0(\epsilon)$ for a suitably adjusted value of $n_0(\epsilon)$ (say we require $\epsilon^{-1}C'n^{-1/2} < 1/2$). We will now apply Lemmas 1.9 and 1.10 to the subset $A = S_\epsilon$.

Fix $0 < \epsilon, \delta < 1$. Let $0 < \epsilon' < 1$ be such that $3\epsilon'^{1/3} = (1 - \delta)/2$ and let $\epsilon_0$ be such that $2\epsilon_0 = (1 - \delta)/2$. Let $c' = \sqrt{2(1 - \epsilon')}$ and $c = \sqrt{2(1 - \epsilon'/2)}$ so that we have $c' < c < \sqrt{2}$.

Assume $\epsilon \le \epsilon_0$. Let $r = \epsilon'^2$ and $b = K\epsilon'^2/2$ and say $b' = b/2$ so that $b-b'$ and $c-c'$ depend only on $\epsilon'$ (or equivalently on $\delta$). For $n \ge n_0(\epsilon, \epsilon')$, Lemmas 1.9 and 1.10 give us a subset $T \subset S_\epsilon$ such that $|T| \ge \exp(K\epsilon'^2nN^2/4)$ and such that $d'(s, t) \ge \sqrt{2(1 - \epsilon')}$ for all $s \ne t$. Then Lemma 1.12 (specifically (1.5)) gives us that $s, t$ are $\delta$-separated since $\epsilon \le \epsilon_0$ and our choice of $\epsilon_0, \epsilon'$ is adjusted so that $3\epsilon'^{1/3} + 2\epsilon_0 = 1 - \delta$. This completes the proof for any $\epsilon \le \epsilon_0$ and in particular for $\epsilon = \epsilon_0$. The remaining case $\epsilon_0 < \epsilon < 1$ then follows automatically since $S_{\epsilon_0} \subset S_\epsilon$ if $\epsilon_0 < \epsilon$. $\square$

One defect of Lemma 1.11 is that when $\epsilon'$ is close to 1, its conclusion is void (however small $\epsilon$ can be). This is corrected by the next lemma, the main interest of which is the case when $\delta$ and $f_\epsilon(\delta)$ are small.

**Lemma 1.12.** Fix $0 < \epsilon < 1$. There is a positive function $\delta \mapsto f_\epsilon(\delta)$ defined for $0 < \delta < 1$, such that $f_\epsilon(\delta) = O_\epsilon(\delta^{1/4})$ when $\delta \to 0$, and satisfying the following property:

Consider $u = (u_j) \in S_\epsilon \subset U(N)^n$ and $v = (v_j) \in M_N^n$ such that $\| \sum v_j \otimes \bar{v}_j \| \le n$. The condition

$$ d'(u, v) \ge f_\epsilon(\delta)\sqrt{n} \quad (1.13) $$

implies

$$ \left\| \sum u_j \otimes \bar{v}_j \right\| \le n(1 - \delta). \quad (1.14) $$

*Proof.* Assume for contradiction that $\| \sum u_j \otimes \bar{v}_j \| > n(1 - \delta)$. Then there are $\xi, \eta$ in the unit sphere of $H = L_2(\tau_N)$ such that

$$ \Re \tau_N \left( \sum u_j \xi v_j^* \eta^* \right) > n(1 - \delta). $$

Let $\xi = U|\xi|$ and $\eta = V|\eta|$ be their polar decompositions, and let $w_j = V^*u_j U$ so that we can write

$$ \Re \tau_N \left( \sum w_j |\xi| v_j^* |\eta| \right) > n(1 - \delta). \quad (1.15) $$
Recall $T_u(\xi) = \sum u_j \xi u_j^*$. Note that since $U \otimes \tilde{U}$ and $V \otimes \tilde{V}$ preserve $I$ (and hence $I^\perp$), we have $\|T_u\| = \|T_u\|$. Therefore $w \in S_\epsilon$. Using the scalar product in $H$ we have

$$ \Re \sum (|\eta|^{1/2} w_j |\xi|^{1/2}, |\eta|^{1/2} v_j |\xi|^{1/2}) > n(1-\delta), $$

and by Cauchy-Schwarz

$$ (\sum \|\eta\|^{1/2} w_j |\xi|^{1/2} \|_H^2)^{1/2} (\sum \|\eta\|^{1/2} v_j |\xi|^{1/2} \|_H^2)^{1/2} > n(1-\delta). $$

Note that since $\sum v_j \otimes \bar{v}_j \le n$ we have $\langle (\sum v_j \otimes \bar{v}_j)\xi, |\eta| \rangle = \sum \|\eta|^{1/2} v_j |\xi|^{1/2} \|_H^2 \le n$, and similarly with $w_j$ in place of $v_j$. Thus the last inequality implies a fortiori

$$ \left\langle \left( \sum w_j \otimes \bar{w}_j \right) |\xi|, |\eta| \right\rangle > n(1 - \delta)^2, \quad (1.16) $$

and the same with $v_j$ in place of $w_j$.

Let $e = (1-P)|\xi|$ and $d = (1-P)|\eta|$. Recall that $P(|\xi|) = \tau_N(|\xi|)I$ and $P(|\eta|) = \tau_N(|\eta|)I$, and $|\xi|, |\eta|$ are unit vectors, so that $\tau_N(|\xi|) = (1 - \|e\|_H^2)^{1/2}$ and $\tau_N(|\eta|) = (1 - \|d\|_H^2)^{1/2}$. Let $\omega = \|e\|_H \|d\|_H$. By Cauchy-Schwarz we have $\omega + (1 - \|e\|_H^2)^{1/2} (1 - \|d\|_H^2)^{1/2} \le 1$ and hence $(1 - \|e\|_H^2)^{1/2} (1 - \|d\|_H^2)^{1/2} \le 1 - \omega$. Since $w \in S_\epsilon$, we have

$$ \left\langle \left( \sum w_j \otimes \bar{w}_j \right) |\xi|, |\eta| \right\rangle = \langle T_w e, d \rangle + n \tau_N(|\xi|) \tau_N(|\eta|) \le \varepsilon n \omega + n(1-\omega). $$

Thus, (1.16) yields

$$ \omega \le (1 - \varepsilon)^{-1} (2\delta - \delta^2). \quad (1.17) $$

Moreover, (1.16) implies

$$ n^{-1} \sum \|w_j|\xi|w_j^* - |\eta|\|_H^2 = 2 - 2n^{-1} \left\langle \left( \sum w_j \otimes \bar{w}_j \right) |\xi|, |\eta| \right\rangle < 2(2\delta - \delta^2). \quad (1.18) $$

But since $(I-P)(w_j|\xi|w_j^* - |\eta|) = w_j e w_j^* - d$ for each $j$, we have

$$ \|e\|_H - \|d\|_H = \|w_j e w_j^*\|_H - \|d\|_H \le \|w_j e w_j^* - d\|_H \le \|w_j|\xi|w_j^* - |\eta|\|_H $$

so that (1.18) implies $(\|e\|_H - \|d\|_H)^2 < 2(2\delta - \delta^2)$. Therefore

$$ \|e\|_H^2 + \|d\|_H^2 < 2\omega + 2(2\delta - \delta^2) \le 2(2\delta - \delta^2)((1 - \varepsilon)^{-1} + 1). \quad (1.19) $$

We can write

$$ w_j |\xi| v_j^* |\eta| = w_j P(|\xi|) v_j^* P(|\eta|) + w_j e v_j^* P(|\eta|) + w_j P(|\xi|) v_j^* d + w_j e v_j^* d $$

and we find

$$ \begin{aligned} n(1 - \delta) &< \Re \tau_N \left( \sum w_j |\xi| v_j^* |\eta| \right) \\ &\le \Re \tau_N \left( \sum w_j v_j^* \right) \tau_N(|\xi|) \tau_N(|\eta|) + n \|e\|_H \tau_N(|\eta|) + n \tau_N(|\xi|) \|d\|_H + n \|e\|_H \|d\|_H \end{aligned} $$
and a fortiori

$$n(1 - \delta) < \Re \tau_N \left( \sum w_j v_j^* \right) \tau_N(|\xi|) \tau_N(|\eta|) + n \|e\|_H + n \|d\|_H + n \|e\|_H \|d\|_H.$$

Note that $n\|e\|_H + n\|d\|_H + n\|e\|_H\|d\|_H \le n2^{1/2}(\|e\|_H^2 + \|d\|_H^2)^{1/2} + n\|e\|_H\|d\|_H$. By (1.19) and (1.17), we obtain

$$\tau_N(|\xi|) \tau_N(|\eta|) \Re \tau_N \left( \sum w_j v_j^* \right) > n(1 - \theta)$$

with

$$\theta = \delta + 2^{1/2}(2(2\delta - \delta^2)((1 - \epsilon)^{-1} + 1))^{1/2} + (1 - \epsilon)^{-1}(2\delta - \delta^2).$$

Note that $\theta$ is $O(\delta^{1/4})$ when $\delta \to 0$ and there is clearly some $\delta_\epsilon > 0$ such that $0 < \theta < 1$ for all $\delta \le \delta_\epsilon$. Thus, assuming $0 < \delta \le \delta_\epsilon$ we have $1 - \theta > 0$ and we find

$$\Re \tau_N \left( \sum w_j v_j^* \right) > n(1 - \theta).$$

This is a lower bound for the real part of the scalar product in $\ell_2^n(H)$ of $w = (w_j)$ and $v = (v_j)$ which are both in the ball of radius $\sqrt{n}$. Therefore we deduce from this

$$d(w, v)^2 \le 2n - 2\Re \tau_N \left( \sum w_j v_j^* \right) < 2n\theta.$$

If we now set $f_\epsilon(\delta) = (2\theta)^{1/2}$ for all $\delta \le \delta_\epsilon$, and $f_\epsilon(\delta) = 3$ (say) for $\delta_\epsilon < \delta < 1$, we have in any case $d(w, v) < f_\epsilon(\delta)\sqrt{n}$.

Thus we have proved that $\|\sum u_j \otimes \bar{v}_j\| > n(1 - \delta)$ implies $d'(u, v) < f_\epsilon(\delta)\sqrt{n}$. This is equivalent to the fact that (1.13) implies (1.14), and moreover for each $0 < \epsilon < 1$ there is a constant $c_\epsilon > 0$ such that for any $0 < \delta < 1$ we have $f_\epsilon(\delta) \le c_\epsilon \delta^{1/4}$. $\square$

**Remark 1.13.** Let $f_\epsilon(\delta)$ be any function such that $(1.13) \Rightarrow (1.14)$. Then Lemma 1.12 has the following consequence: Assume $u = (u_j) \in S_\epsilon$. Then for any $v = (v_j) \in U(k)^n$ with $k \le (1 - f_\epsilon(\delta)^2)N$ we have

$$\| \sum u_j \otimes \bar{v}_j \| \le n(1 - \delta).$$

Indeed, if $\| \sum u_j \otimes \bar{v}_j \| > n(1 - \delta)$, then we set $v'_j = v_j \oplus 0 \in M_N$ so that $\| \sum v'_j \otimes \bar{v}'_j \| \le n$, and also $\| \sum u_j \otimes \bar{v}'_j \| > n(1 - \delta)$. By Lemma 1.12, it follows that $d'(u, v') < f_\epsilon(\delta)\sqrt{n}$. But since $|\langle u'_j, v'_j \rangle| \le k/N$ for any $u'_j \in U(N)$, we have $d(u', v')^2 = n + n(k/N) - 2 \sum \langle u'_j, v'_j \rangle \ge n(1 - k/N)$, and hence $d'(u, v') \ge \sqrt{n}(1 - k/N)^{1/2}$, which leads to $(1 - k/N)^{1/2} < f_\epsilon(\delta)$. This contradiction concludes the proof.
## 2. Application to operator spaces

We start with a specific notation. Let $u : E \to F$ be a linear map between operator spaces. We denote, for any given $N \ge 1$,

$$u_N = \mathrm{Id} \otimes u : M_N(E) \to M_N(F).$$

Moreover, if $E, F$ are two operator spaces that are isomorphic as Banach spaces, we set

$$d_N(E, F) = \inf\{\|u_N\| \|(u^{-1})_N\|\}$$

where the inf runs over all the isomorphisms $u : E \to F$. We set $d_N(E, F) = \infty$ if $E, F$ are not isomorphic.

Recall that

$$\|u\|_{cb} = \sup_{N \ge 1} \|u_N\|.$$

Recall also that, if $E, F$ are completely isomorphic, we set

$$d_{cb}(E, F) = \inf\{\|u\|_{cb} \|u^{-1}\|_{cb}\}$$

where the inf runs over all the complete isomorphisms $u : E \to F$.

When $E, F$ are both $n$-dimensional, a compactness argument shows that

$$d_{cb}(E, F) = \sup_{N \ge 1} d_N(E, F).$$

We will apply the preceding to $M_N$-spaces. When $N = 1$, the latter coincide with the usual Banach spaces. When $N > 1$, roughly the complex scalars are replaced by $M_N$.

Let $(A_i)_{i \in I}$ be a family of von Neumann or $C^*$-algebras. Let $Y = \bigoplus_{i \in I} A_i$ denote their direct sum. This can be described as the algebra of bounded families $(a_i)_{i \in I}$ with $a_i \in A_i$ for all $i \in I$, equipped with the norm $\|a\| = \sup_{i \in I} \|a_i\|$. We will concentrate on the case when $A_i = M_N$ for all $i \in I$. In that case, following the Banach space tradition, we denote the space $Y = \bigoplus_{i \in I} A_i$ by $\ell_\infty(I; M_N)$.

**Definition 2.1.** An operator space $X$ is called an $M_N$-space if, for some set $I$, it can be embedded completely isometrically in $\ell_\infty(I; M_N)$.

Our main interest will be to try to understand for which spaces the cardinality of $I$ is unusually small.

To place things in perspective, we recall that for any (complex) Banach space $X$ there is an isometric embedding $J : X \to \ell_\infty(I; \mathbb{C})$ defined by $(Jx)(\phi) = \phi(x)$. Here $I$ is the unit ball, denoted by $B_{X^*}$, of the space $X^*$.

In analogy with this, for any $M_N$-space there is a canonical completely isometric embedding $\hat{J} : X \to \ell_\infty(\hat{I}; M_N)$ defined again by $(Jx)(\phi) = \phi(x)$, but with $\hat{I} = B_{CB(X,M_N)}$ in place of $B_{X^*}$. The space $\ell_\infty(\hat{I}; M_N)$ can alternatively be described as $\bigoplus_{i \in \hat{I}} Z_i$ with $Z_i = M_N$ for all $i \in \hat{I}$.

Just like operator spaces, $M_N$-spaces enjoy a nice duality theory (see [16, 20] for more information). Indeed, by Roger Smith's lemma, we have $\|u\|_{cb} = \|u_N\|$ for any $u$ with values in an $M_N$-space (see e.g. [27, p. 26]), and $M_N$-spaces are characterized among operator spaces by this property. The following reformulation of Smith's lemma is useful.
**Lemma 2.2.** Fix an integer $N \ge 1$. Let $E \subset B(H)$ be a finite-dimensional operator space and let $c \ge 1$ be a constant. The following properties are equivalent:

(i) For any operator space $F$ and any $u: F \to E$ we have $\|u\|_{cb} \le c\|u_N\|$.

(ii) There is an $M_N$-space such that $d_{cb}(E, \hat{E}) \le c$.

(iii) Let $C$ be the class of all (compression) mappings $v: E \to B(H', H'')$ of the form $x \mapsto P_{H''x|H'}$ where $H', H''$ are arbitrary subspaces of $H$ of dimension at most $N$. Let $\hat{J}: E \to \bigoplus_{v \in C} Z_v$ with $Z_v = B(H', H'')$ be defined by $\hat{J}(x) = \bigoplus_{v \in C} v(x)$, and let $\hat{E} = \hat{J}(E)$. Then $d_{cb}(E, \hat{E}) \le c$.

*Proof.* (ii)$\Rightarrow$(i) follows from Roger Smith's lemma and (iii)$\Rightarrow$(ii) is trivial. Conversely, if (i) holds, let $\hat{E}$ be the $M_N$-space obtained using the embedding $\hat{J}: E \to \bigoplus_{v \in C} Z_v$ appearing in (iii). Obviously $\|E \to \hat{E}\|_{cb} \le 1$. Let us denote by $u: \hat{E} \to E$ the inverse mapping. A simple verification shows that $\|u_N\| = 1$ and hence (i) implies $\|u\|_{cb} \le c$. In other words (i)$\Rightarrow$(iii). $\square$

Therefore, when $X$ is an $M_N$-space, the knowledge of the space $M_N(X)$ determines that of $M_n(X)$ for all $n > N$, and hence the whole operator space structure of $X$.

Given a general operator space $X \subset B(H)$, by restricting to $M_N(X)$ (and “forgetting” $M_n(X)$ for $n > N$), we obtain an $M_N$-space $M_N$-isometric to $X$. We will say that the latter $M_N$-space is *induced* by $X$.

Conversely, given an $M_N$-space $X$ there is a minimal and a maximal operator space structure on $X$ inducing the same $M_N$-space. When $N = 1$, we recover the Blecher-Paulsen theory of minimal and maximal operator spaces associated to Banach spaces (see [16, 20] for more on this).

Let $E$ be a finite-dimensional operator space. For each integer $N$, let $E[N]$ denote the induced $M_N$-space. Then it is easy to check that $E$ can be identified (completely isometrically) with the ultraproduct of $\{E[N]\}$ relative to any free ultraproduct on $\mathbb{N}$. Thus the operator space structure of $E$ can be encoded by the sequence of $M_N$-spaces $\{E[N] | N \ge 1\}$. Note that $E[N]$ is induced by $E[N+1]$ for any $N$, so that one could picture the set of $n$-dimensional operator spaces as infinite branches of trees where the $N$-th node consists of an $M_N$-space, and any node is induced by any successor.

We can associate to each $M_N$-space a dual one $X^\dagger$, isometric to the operator space dual $X^*$, but defined by

$$ \forall n \in \mathbb{N} \forall y \in M_n(X^\dagger) \quad \|y\|_{M_n(X^\dagger)} = \sup_{f \in M_N(X)} \|(I \otimes f)(y)\|_{M_n(M_N)}, $$

where we view $M_N(X)$ as a subset of $CB(X^*, M_N)$ in the usual way. In other words we have a completely isometric embedding $J_\dagger: X^\dagger \to \ell_\infty(I; M_N)$ defined by

$$ J_\dagger(z) = \bigoplus_{f \in M_N(X)} f(z) = \bigoplus_{f \in M_N(X)} [f_{ij}(z)]. $$

Just as for operator spaces, there is a notion of “Hilbert space” for $M_N$-spaces. We will denote it by $OH(n, N)$. The latter can be defined as follows. First we have an analogue
of the Cauchy-Schwarz inequality due to Haagerup: for all $x = (x_j) \in M_N^n$ and $y = (y_j) \in M_N^n$,

$$ \left\| \sum x_j \otimes \bar{y}_j \right\| \le \left\| \sum x_j \otimes \bar{x}_j \right\|^{1/2} \left\| \sum y_j \otimes \bar{y}_j \right\|^{1/2}. \quad (2.1) $$

Fix $N$. Let $S(n, N)$ (resp. $B(n, N)$) denote the set of $n$-tuples $x = (x_j)$ in $M_N$ such that $\| \sum x_j \otimes \bar{x}_j \| = 1$ (resp. $\| \sum x_j \otimes \bar{x}_j \| \le 1$). Then $S(n, N)$ (resp. $B(n, N)$) is the analogue of the unit sphere (resp. ball) in the $M_N$-space $OH(n, N)$. The space $X = OH(n, N)$ is isometric to $\ell_2^n$, with its orthonormal basis $(e_j)$, and embedded into $\ell_\infty(I; M_N)$ with $I = B(n, N)$ (we could also take $I = S(n, N)$). The embedding $J_{oh}: OH(n, N) \to \ell_\infty(I; M_N)$ is defined by

$$ \forall j = 1, \dots, n \quad J_{oh}(e_j) = \bigoplus_{x \in B(n, N)} x_j. $$

The latter is the analogue of $n$-dimensional Hilbert space among $M_N$-spaces, and indeed when $N = 1$ we recover the $n$-dimensional Hilbert space.

**Definition 2.3.** Let $E$ be an operator space with basis $(e_j)$. Let $\xi_j$ be the biorthogonal basis of $E^*$. Let $x = \sum x_j \otimes e_j \in M_N(E)$ and $y = \sum y_j \otimes \xi_j \in M_N(E^*)$. Assuming $x \ne 0$ and $y \ne 0$, we say that $y$ $M_N$-norms $x$ (with respect to $M_N(E)$) if

$$ \left\| \sum x_j \otimes y_j \right\| = \|x\|_{M_N(E)} \|y\|_{M_N(E^*)}. $$

In the particular case when $E = OH_n$, we slightly modify this (since $E^* = \bar{E}$): Given $x, y \in M_N(OH_n)$, we say that $y$ $M_N$-norms $x$ if

$$ \left\| \sum x_j \otimes \bar{y}_j \right\| = \left\| \sum x_j \otimes \bar{x}_j \right\|^{1/2} \left\| \sum y_j \otimes \bar{y}_j \right\|^{1/2}. $$

Let $x \in M_N(E)$. For $a, b \in M_N$ we denote by $axb$ the matrix product (that is, $(a \otimes 1)x(b \otimes 1)$ in tensor product notation using $M_N(E) = M_N \otimes E$). We denote

$$ \mathrm{Orb}(x) = \{uxv \in M_N(E) \mid u, v \in U(N)\}. $$

Note that if $y \in M_N(E^*)$ $M_N$-norms $x$ then the same is true for any $y' \in \mathrm{Orb}(y) \subset M_N(E^*)$. Actually, any $y' \in \mathrm{Orb}(y)$ $M_N$-norms any $x' \in \mathrm{Orb}(x)$.

**Definition 2.4.** We say that $x \in M_N(E)$ is an $M_N$-smooth point of $M_N(E)$ if the set of points $y$ in the unit sphere of $M_N(E^*)$ that $M_N$-norm $x$ is reduced to a single orbit.

The following simple proposition explains the direction we will be taking next.

**Proposition 2.5.** Let $x, y \in M_N(OH_n)$. Assume

$$ x = (x_j) \in U(N)^n \quad \text{and} \quad \|T_x : H_0 \to H_0\| < n, $$

where $T_x = \sum x_j \otimes \bar{x}_j(1-P)$ (i.e. $T_x$ has a spectral gap at $n$). Then $y$ norms $x$ with respect to $M_N(OH_n)$ iff $y$ is a multiple of an element of $\mathrm{Orb}(x)$, i.e. iff there are $\lambda > 0$ and $u, v \in U(N)$ such that $y_j = \lambda v x_j u$ for all $1 \le j \le n$.
Proof. Recall that whenever the $x_j$'s are finite-dimensional unitaries we have $\|\sum x_j \otimes \bar{x}_j\|^{1/2} = \sqrt{n}$. Assume $y$ is a multiple of an element of $\text{Orb}(x)$, i.e. $y_j = \lambda v x_j u$ for some non-zero scalar $\lambda$ (which may well be taken positive if we wish). Then $\|\sum x_j \otimes y_j\| = |\lambda|n$, $\|x\|_{M_N(OH_n)} = \sqrt{n}$ and $\|y\|_{M_N(OH_n)} = |\lambda|\sqrt{n}$, so indeed $y$ norms $x$.

Conversely, assume that $y$ norms $x$. Multiplying $y$ by a scalar we may assume that $\|y\|_{M_N(OH_n)} = \sqrt{n}$, and $\|\sum x_j \otimes \bar{y}_j\| = \|\sum x_j \otimes \bar{x}_j\|^{1/2}\sqrt{n} = n$. Let $\xi, \eta$ in the unit sphere of $H = L_2(\tau_n)$ be such that

$$ \sum \tau_N(x_j \xi y_j^* \eta^*) = n. $$

Let $\xi = u|\xi|$ and $\eta = v|\eta|$ be the polar decompositions, and let $x'_j = v^*x_j u$. Using the trace property, this can be rewritten using the scalar product in $H$ as

$$ \sum \langle |\eta|^{1/2} x'_j |\xi|^{1/2}, |\eta|^{1/2} y_j |\xi|^{1/2} \rangle = n, $$

and hence since $n^{-1/2}(|\eta|^{1/2}x'_j|\xi|^{1/2})$, $n^{-1/2}(|\eta|^{1/2}y_j|\xi|^{1/2})$ are both in the unit ball of the (smooth!) Hilbert space $\ell_2^\eta(H)$, they must coincide. Moreover they both must be on the unit sphere. Therefore $\sum \|\eta|^{1/2}x'_j|\xi|^{1/2}\|_H^2 = n$. Equivalently $\sum \tau_N(x'_j|\xi|x'_j^*|\eta|) = n$. But we have obviously $\|T_{x'} : H_0 \to H_0\| = \|T_x : H_0 \to H_0\| < n$. Therefore $|\xi|$ and $|\eta|$ must be multiples of $I$, so that by our normalization we have $|\xi| = |\eta| = I$, and we conclude that $y = x'$. $\square$

In other words, the preceding proposition shows that quantum expanders constitute $M_N$-smooth points of $M_N(OH_n)$:

**Corollary 2.6.** Assume $x = (x_j) \in U(N)^n$. Then $x = \sum x_j \otimes e_j$ is an $M_N$-smooth point in $M_N(OH_n)$ iff $\|T_x : H_0 \to H_0\| < n$.

Proof. The “if” part follows from the preceding statement. Conversely, we claim that if $\|T_x : H_0 \to H_0\| = n$ then $x$ is not an $M_N$-smooth point in $M_N(OH_n)$. Since this claim is unchanged if we replace $x$ by any $x'$ in $\text{Orb}(x)$, we may assume that $x_1 = 1$. Then if $\|T_x : H_0 \to H_0\| = n$, there is $0 \neq \xi \in H_0$ such that $\|T_x(\xi)\| = n\|\xi\|$, and hence (by the uniform convexity of Hilbert space) $x_j \xi x_j^* = x_1 \xi x_1^* = \xi$ for all $j$. This implies that the commutant of $\{x_j\}$ is not reduced to the scalars, and hence in a suitable basis, $x_j = x_j^1 \oplus x_j^2 \in M_{N_1} \oplus M_{N_2}$ for some $N_1, N_2 \ge 1$ with $N_1 + N_2 = N$. Then the choice of $y_j = x_j^1 \oplus 0$ produces $y \in M_N^n$ not in $\text{Orb}(x)$ and such that $\|\sum x_j \otimes \bar{y}_j\| = n$. Thus $x$ is not an $M_N$-smooth point in $M_N(OH_n)$, proving our claim. $\square$

**Remark 2.7.** Let $E$ be any $n$-dimensional operator space with a basis $(e_j)$. Assume that for any $u = (u_j) \in U(N)^n$ we have $\|\sum u_j \otimes e_j\|_{M_N(E)} = \sqrt{n}$ and also that $\|\sum a_j \otimes e_j\|_{M_N(E)} \le \|\sum a_j \otimes \bar{a}_j\|^{1/2}$ for all $a = (a_j) \in M_N^n$. Then, by the same proof, for any $x = (x_j) \in U(N)^n$ such that $\|T_x : H_0 \to H_0\| < n$ as above, the point $x = \sum x_j \otimes e_j$ is an $M_N$-smooth point in $M_N(E)$. Indeed, any $y$ in the unit ball of $M_N(E^*)$ that $M_N$-norms $x$ with respect to $M_N(E)$ is a fortiori in the unit ball of $M_N(OH_n)$.
Lemma 1.12 above can be viewed as a refinement of this: assuming $\|T_x : H_0 \to H_0\| < \epsilon n$ we have a certain form of “uniform smoothness” of $OH_n$ at $x$, the points that almost $M_N$-norm $x$ up to $\delta n$ are in the orbit of $x$ up to $f_\epsilon(\delta)n$. See Remark 2.9 for more on this point.

**Notation.** Let $E$ be a finite-dimensional operator space. Fix $C > 0$. We denote by $k_E(N, C)$ the smallest integer $k$ such that there is a subspace $F$ of $M_N \oplus \cdots \oplus M_N$ (with $M_N$ repeated $k$ times) such that $d_N(E, F) \le C$.

Note that for any $E \subset M_n$ we have $k_E(N, 1) = 1$ for any $N \ge n$.

The next statement is our main result in this section. It gives a lower bound for $k_E(N, C_1)$ when $E = OH_n$. We will show later (see Lemma 2.11) that a similar upper bound holds for all $n$-dimensional operator spaces. Thus for $E = OH_n$ (and also for $E = \ell_1^n$ or $E = R_n + C_n$, see Remark 2.10) the growth of $N \mapsto k_E(N, C_1)$ is essentially extremal.

**Theorem 2.8.** There are numbers $C_1 > 1$, $b > 0$, $n_0 > 1$ such that for any $n \ge n_0$ and $N \ge 1$, we have

$$k_{OH_n}(N, C_1) \ge \exp(bnN^2).$$

We start by recalling the classical argument dealing with the Banach space case, i.e. the case $N = 1$. Let $E$ be an $n$-dimensional Banach space. Assume that, for some $C > 1$, $E$ embeds $C$-isomorphically into $\ell_\infty^k$. For convenience we write $C = (1 - \delta)^{-1}$ for some $\delta > 0$. Our embedding assumption means that there is a set $T$ in the unit ball of $E^*$ such that for any $x \in E$ we have

$$(1 - \delta)\|x\| \le \sup_{t \in T} |t(x)| \le \|x\|. \qquad (2.2)$$

Then for any $x$ in the unit ball of $E$, there are $t_x \in T$ and $\omega_x \in \mathbb{C}$ with $|\omega_x| = 1$ such that $1 - \delta \le \Re(\omega_x t_x(x))$.

Now assume $E = \ell_2^n$. Then identifying $E$ and $E^*$ as usual, we see that $1 - \delta \le \Re(\omega_x t_x(x))$ implies $\|x - \omega_x t_x\|^2 \le 2\delta$. In the case of real Banach spaces, $\omega_x = \pm 1$ and we conclude quickly, but let us continue for the sake of analogy with the case $N > 1$. We have just proved that the set $\{\omega t \mid \omega \in \mathbb{T}, t \in T\}$ is a $\sqrt{2\delta}$-net in the unit ball of $E = \ell_2^n$. Fix $\epsilon > 0$. Let $N(\epsilon) \approx 2\pi/\epsilon$ be such that there is an $\epsilon$-net in $\mathbb{T}$. It follows that there is a $(\sqrt{2\delta} + \epsilon)$-net $\mathcal{N}$ in the unit ball of $E = \ell_2^n$ with $|\mathcal{N}| \le N(\epsilon)|T|$. But by a well known volume estimate (see e.g. [25, pp. 49–50]), any $\delta'$-net in the unit ball of $E = \ell_2^n$ must have cardinality at least $(1/\delta')^n$. Thus we conclude that $(\sqrt{2\delta} + \epsilon)^{-n} \le N(\epsilon)|T|$. This yields

$$(2\pi)^{-1}\epsilon(\sqrt{2\delta} + \epsilon)^{-n} \le |T|.$$

For any $\delta < 1/2$, we may choose $\epsilon > 0$ so that $\sqrt{2\delta} + \epsilon < 1$, thus we find that there is a number $b > 0$ for which we obtain $|T| \ge \exp(bn)$, and hence $k_{OH_n}(1, (1 - \delta)^{-1}) \ge \exp(bn)$.
**Remark 2.9.** The preceding argument still works when $E$ is uniformly convex with modulus $\varepsilon \mapsto \delta(\varepsilon)$. This means that if $x_1, x_2$ in the unit ball $B_E$ satisfy $\|x_1 - x_2\| \ge \varepsilon$ then $\|(x_1 + x_2)/2\| \le 1 - \delta(\varepsilon)$. Indeed, the only property we used is that for any $\varepsilon > 0$ there is $r > 0$ such that $x_1, x_2 \in B_E$ and $\xi_1, \xi_2 \in B_{E^*}$ satisfy

$$ \Re(\xi_1(x_1)) > 1 - r, \quad \Re(\xi_2(x_2)) > 1 - r \quad \text{and} \quad \|\xi_1 - \xi_2\| < r, $$

then we must have $\|x_1 - x_2\| < \varepsilon$. To check this, note that

$$ \|(x_1 + x_2)/2\| \ge |\xi_1(x_1 + x_2)/2| \ge |\xi_1(x_1)/2 + \xi_2(x_2)/2| - \|\xi_1 - \xi_2\|/2 > 1 - r - r/2, $$

thus if $r = \delta(\varepsilon)/2$ then $\|(x_1 + x_2)/2\| > 1 - \delta(\varepsilon)$ and hence we must have $\|x_1 - x_2\| < \varepsilon$.

Recall that a Banach space $E$ is uniformly convex iff its dual $E^*$ is uniformly smooth (see [4]). Thus since $E = OH_n$ is self-dual, Lemma 1.12 can be interpreted as the $M_N$-analogue of the uniform smoothness of $E^*$.

A completely different proof, with no restriction on $\delta$ or equivalently on the constant $C$, can be given by a well known argument using real or complex Gaussian random variables. We restrict ourselves to the real case for simplicity. Let $\gamma_n$ be the canonical Gaussian measure on $\mathbb{R}^n$. Assume (2.2) holds. Let $q = \int \exp(x^2/4) \gamma_1(dx) < \infty$. Note that since $\mathcal{T}$ is included in the unit ball we have

$$ \int \exp\left(\sup_{t \in \mathcal{T}} t(x)^2/4\right) \gamma_n(dx) \le \sum_{t \in \mathcal{T}} \int \exp(t(x)^2/4) \gamma_n(dx) \le q |\mathcal{T}|. $$

But by (2.2), if we reset $C = (1 - \delta)^{-1}$, we find $C^{-1}\|x\| \le \sup_{t \in \mathcal{T}} |t(x)|$ and hence

$$ \left( \int \exp(C^{-2}|x|^2/4) \gamma_1(dx) \right)^n \le \int \exp\left(C^{-2} \sum |x_j|^2/4\right) \gamma_n(dx) \\ \le \int \exp\left(\sup_{t \in \mathcal{T}} t(x)^2/4\right) \gamma_n(dx) \le q |\mathcal{T}|. $$

Thus if we define $b = b_C > 0$ by $\int \exp(C^{-2}|x|^2/4) \gamma_1(dx) = \exp b$, we find $|\mathcal{T}| \ge q^{-1} \exp(nb)$ and we conclude

$$ k_{OH_n}(1, C) \ge q^{-1} \exp(b_C n). $$

See [29] for random matrix versions of this argument.

**Proof of Theorem 2.8.** The proof follows the strategy of the first proof outlined above for $N = 1$, but using Theorem 1.3 instead of the lower bound on the metric entropy of the unit ball of $\ell_2^n$. Consider an $n$-dimensional operator space $E$. Let $k = k_E(N, C)$. Let again $C = (1 - \delta)^{-1}$. Then there is a set $\mathcal{T}$ with $|\mathcal{T}| = k$ and completely contractive mappings $\phi_t : E \to M_N$ such that

$$ \forall x \in M_N(E) \quad (1 - \delta) \|x\|_{M_N(E)} \le \sup_{t \in \mathcal{T}} \|(\phi_t)_N(x)\|_{M_N(M_N)}. \quad (2.3) $$
Let $e_j$ be a basis for $E$ so that each $x$ can be developed as $x = \sum x_j \otimes e_j \in M_N \otimes E$. Let $y(t) \in M_N(E^*)$ be the element associated to $\phi_t : E \to M_N$. Let $e_j^+ \in E^*$ be the basis of $E^*$ that is biorthogonal to $(e_j)$. Then $y(t)$ (or equivalently $\phi_t$) can be written as $y(t) = \sum y_j(t) \otimes e_j^+ \in M_N \otimes E^*$, and (2.3) can be rewritten as

$$ \forall x \in M_N(E) \quad (1-\delta) \|x\|_{M_N(E)} \le \sup_{t \in \mathcal{T}} \left\| \sum x_j \otimes y_j(t) \right\|_{M_N(M_N)}. \quad (2.4) $$

Moreover each $y(t)$ is in the unit ball of $M_N(E^*) = CB(E, M_N)$. We now assume $E = OH_n$. Let us denote by $T(\varepsilon, \delta) \subset U(N)^n$ the set appearing in Theorem 1.3. Fix $0 < \varepsilon < 1$ and $0 < \delta_0 < 1$. By Lemma 1.12 we can choose $0 < \delta < 1$ small enough so that

$$ 2f_{\varepsilon}(2\delta) < \sqrt{2\delta_0}. \quad (2.5) $$

We then set $T_0 = T(\varepsilon, \delta_0)$. Thus we have $|T_0| \ge \exp(\beta_0 n N^2)$ for some $\beta_0 > 0$, and the elements of $T_0$ are $\delta_0$-separated. By (2.4),

$$ \forall x = (x_j) \in T_0 \quad (1-\delta)n^{1/2} \le \sup_{t \in \mathcal{T}} \left\| \sum x_j \otimes y_j(t) \right\|_{M_N(M_N)}. $$

Let $(v_j(t)) = (n^{1/2} \overline{y_j(t)})$ so that we have

$$ \forall x = (x_j) \in T_0 \quad (1-\delta)n \le \sup_{t \in \mathcal{T}} \left\| \sum x_j \otimes \overline{v_j(t)} \right\|_{M_N(M_N)}. $$

For any $x \in T_0$ there is a point $t_x \in \mathcal{T}$ such that

$$ (1-\delta)n \le \left\| \sum x_j \otimes \overline{v_j(t_x)} \right\|. $$

Let $v_x = (v_j(t_x))$. By Lemma 1.12, the last inequality implies $d'(x, v_x) < f_{\varepsilon}(\delta')\sqrt{n}$ for any $\delta' > \delta$. Moreover by the converse (much easier) part of Lemma 1.11, we know that $d'(x, y) \ge \sqrt{2\delta_0\overline{n}}$ for any $x \ne y \in T_0$, since $x, y$ are $\delta_0$-separated. We claim that after suitably adjusting the parameters $\delta, \varepsilon$ we have $|T_0| \le |\mathcal{T}|$. Indeed, assume that $|T_0| > |\mathcal{T}|$; then there must exist $x \ne y \in T_0$ such that $v_x = v_y$. We then have, for any $\delta' > \delta$,

$$ \sqrt{2\delta_0 n} \le d'(x, y) \le d'(x, v_x) + d'(v_x, y) = d'(x, v_x) + d'(v_y, y) \le 2f_{\varepsilon}(\delta')\sqrt{n} $$

and hence $\sqrt{2\delta_0} \le 2f_{\varepsilon}(2\delta)$, which is impossible by (2.5). This proves our claim that $|T_0| \le |\mathcal{T}|$, and hence $|\mathcal{T}| \ge \exp(\beta_0 n N^2)$. Let $C_1 = (1-\delta)^{-1}$. Thus, with $\delta$ determined by (2.5), we have proved $k_{OH_n}(N, C) \ge \exp(\beta_0 n N^2)$. $\square$

**Remark 2.10.** Let $E$ be any $n$-dimensional operator space with a basis $(e_j)$. Assume that there is a scaling factor $\lambda > 0$ (which does not play any role in the estimate) such that for any $u = (u_j) \in U(N)^n$ we have $\lambda \| \sum u_j \otimes e_j \|_{M_N(E)} = \sqrt{n}$ and also $\lambda \| \sum a_j \otimes e_j \|_{M_N(E)} \le \| \sum a_j \otimes \bar{a}_j \|^{1/2}$ for all $a = (a_j) \in M_N^n$. Then, arguing as in Remark 2.7, we find $k_E(N, C_1) \ge \exp(\beta n N^2)$. This shows that this estimate is valid for $R_n + C_n$ (take $\lambda = 1$) and for $\ell_1^n$ equipped with its maximal operator space structure (take $\lambda = n^{-1/2}$).
We now turn to the reverse inequality to that in Theorem 2.8. This general estimate is easy to check by a rather routine argument.

**Lemma 2.11.** Let E be an n-dimensional operator space. Then for any $0 < \delta < 1$ we have

$$k_E(N, (1 - \delta)^{-1}) \le (1 + 2\delta^{-1})^{2nN^2}.$$

Therefore, for any operator space X and any finite-dimensional subspace $E \subset X$ we have

$$\forall C > 1 \quad \limsup_{N \to \infty} \frac{\log k_E(N, C)}{N^2} < \infty.$$

*Proof.* Let $x \in M_N(E)$ and let $\hat{x} : E^* \to M_N$ denote the associated linear mapping. Recall $\|x\| = \|\hat{x}\|_{cb}$. By Lemma 2.2, $\|\hat{x}\|_{cb} = \sup\{\|(\hat{x})_N(y)\|_{M_N(M_N)} | y \in B_N\}$ where we denote by $B_N$ the unit ball of $M_N(E^*)$ viewed as a real space. Since the latter ball is $2nN^2$-dimensional, it contains a $\delta$-net $\{y_i | i \le m\}$ with cardinality $m \le (1 + 2\delta^{-1})^{2nN^2}$ (see e.g. [25, pp. 49–50]). By an elementary estimate, we then have (for any $x \in M_N(E)$)

$$\sup_{i \le m} \|(\hat{x})_N(y_i)\| \le \|\hat{x}\|_{cb} = \|x\| \le (1 - \delta)^{-1} \sup_{i \le m} \|(\hat{x})_N(y_i)\|. \quad (2.6)$$

Let $u : E \to \bigoplus_{i \le m} M_N$ be the mapping defined by (here again $\hat{y}_i : E \to M_N$ is associated to $y_i$)

$$u(e) = \bigoplus_{i \le m} \hat{y}_i(e)$$

for any $e \in E$. Let $F \subset \bigoplus_{i \le m} M_N$ be the range of $u$. Then (2.6) says that $\|u_N\| \le 1$ and $\|u_N^{-1}\| \le 1 + \delta$, and hence $d_N(E, F) \le (1 - \delta)^{-1}$. Thus $k_E(N, (1 - \delta)^{-1}) \le m$. $\square$

**Definition 2.12.** An operator space X will be called *matricially C-sub-Gaussian* if

$$\limsup_{N \to \infty} \frac{\log k_E(N, C)}{N^2} = 0$$

for any finite-dimensional subspace $E \subset X$. We say that X is *matricially sub-Gaussian* if it is matricially C-sub-Gaussian for some $C \ge 1$. (See Remark 3.2 for the reason behind “matricially”.)

*Note.* If X itself is finite-dimensional, it suffices to consider $E = X$.

We will denote by $C_g(X)$ the smallest C such that X is matricially C-sub-Gaussian.

The preceding result (resp. Remark 2.10) shows that when $C < C_1$, then OH (resp. $\ell_1$ or $R + C$) is not matricially C-sub-Gaussian. In sharp contrast, any C-exact operator space E (we recall the definition below) is clearly matricially C-sub-Gaussian since, for any $c > C$, it satisfies $k_E(N, c) = 1$ for all N large enough. We do not know whether conversely the latter property implies that E is C-exact (but we doubt it).
**Remark 2.13.** Given an operator space X, it is natural to introduce the following parameter:

$$k_X(N, C; d) = \sup\{k_E(N, C) \mid E \subset X, \dim(E) = d\}.$$

We will say that X is uniformly matricially sub-Gaussian if there is C such that

$$\forall d \ge 1 \quad \limsup_{N \to \infty} \frac{\log k_X(N, C; d)}{N} = 0.$$

It is easy to check that if X is uniformly exact (resp. uniformly subexponential, uniformly matricially sub-Gaussian) then all ultrapowers of X are exact (resp. subexponential, matricially sub-Gaussian). Note however (I am indebted to Yanqi Qiu for this remark) that the converse is unclear.

For example, R or C (or R ⊕ C), any commutative C*-algebra A, or any space of the form A ⊗_min M_N is uniformly exact. It would be interesting to characterize uniformly exact operator spaces.

We now turn to a different application of quantum expanders to operator spaces, which requires a refinement of our main result.

For any n × n matrix w and any v ∈ M_N^n, we denote by w.v ∈ M_N^n the n-tuple defined by

$$(w.v)_i = \sum_j w_{ij} v_j.$$

Note that if w is unitary, i.e. w ∈ U(n), then

$$\sum_i (w.v)_i \otimes \overline{(w.v)_i} = \sum_j v_j \otimes \bar{v}_j. \qquad (2.7)$$

Also note that if w ∈ U(n), for any v, v' ∈ M_N^n we have

$$d(w.v, w.v') \le d(v, v'). \qquad (2.8)$$

Moreover, it is easy to check (e.g. using (1.1)) that for all w ∈ M_n with operator norm ||w|| and for all v ∈ M_N^n we have

$$\left\| \sum (w.v)_i \otimes \overline{(w.v)_i} \right\| \le \|w\|^2 \left\| \sum_j v_j \otimes \bar{v}_j \right\|, \qquad (2.9)$$

and hence by (2.1), for any u, v ∈ U(N)^n,

$$\left\| \sum u_i \otimes \overline{(w.v)_i} \right\| \le \|w\|n. \qquad (2.10)$$

Also

$$d(w.v, w.v') \le \|w\|d(v, v').$$

We will say that u, v ∈ U(N)^n are strongly δ-separated if v and w.u are δ-separated for any w ∈ U(n). Equivalently, for any pair w, w' ∈ U(n) the pair (w.u, w'.v) is δ-separated.
Explicitly, this can be written like this:

$$ \forall w \in U(n) \quad \left\| \sum_{i,j} w_{ij} u_j \otimes \bar{v}_i \right\| \le n(1-\delta). \qquad (2.11) $$

We will use again (see Lemma 1.10) the following elementary fact: There is a positive constant $D$ such that for each $0 < \xi < 1$ and each $n$ there is a $\xi$-net $N_\xi \subset U(n)$, with respect to the operator norm, of cardinality

$$ |N_\xi| \le (D/\xi)^{2n^2}. $$

We will need the following refinement of Theorem 1.3.

**Lemma 2.14.** For each $0 < \delta < 1$ there is a constant $\beta'_\delta > 0$ such that for any $0 < \varepsilon < 1$ and for all $n \ge n_0$ and all $N$ such that $N^2/n \ge N_0$ (with $n_0$ depending on $\varepsilon$ and $\delta$, and $N_0$ depending on $\delta$), there is a strongly $\delta$-separated subset $T_1 \subset S_\varepsilon$ such that $|T_1| \ge \exp(\beta'_\delta n N^2)$. More generally, for each $\alpha > 0$, there are $\beta'_{\delta,\alpha} > 0$ and $n_0 = n_0(\varepsilon, \delta, \alpha)$ such that, if $n \ge n_0$ and $N^2/n \ge N_0$, any subset $A_N \subset U(N)^n$ with $\mathbb{P}(A_N) > \alpha$ contains a strongly $\delta$-separated subset of $S_\varepsilon$ with cardinal $\ge \exp(\beta'_{\delta,\alpha} n N^2)$.

*Proof.* Fix $0 < \delta < 1$ and let $\xi = (1-\delta)/2$ so that $\delta_1 = \delta + \xi = (1+\delta)/2$. Note that $0 < \delta < \delta_1 < 1$. We define $\varepsilon_0$ so that $2\varepsilon_0^{1/2} = (1-\delta_1)/2$ and $\varepsilon'$ so that $\varepsilon'^{1/5}(2^{-4/5}+2^{6/5}) = (1-\delta_1)/2$. Note that $0 < \varepsilon_0, \varepsilon' < 1$ and

$$ 1 - \delta_1 = \varepsilon'^{1/5}(2^{-4/5} + 2^{6/5}) + 2\varepsilon_0^{1/2}. $$

Now assume $0 < \varepsilon \le \varepsilon_0$. By Lemma 1.11 we know that for any $u \in S_\varepsilon$ and any $v \in U(N)^n$ such that $\| \sum v_j \otimes \bar{v}_j \| \le n$ we have

$$ \left\| \sum u_j \otimes \bar{v}_j \right\| > n(1 - \delta_1) \Rightarrow d'(u, v) < \sqrt{2n(1 - \varepsilon')}. \qquad (2.12) $$

By Lemmas 1.9 and 1.10 and using (4.6) as in the proof of Theorem 1.3 we know that for $n \ge n_0(\varepsilon, \varepsilon')$,

$$ N(S_\varepsilon, d', \sqrt{2n(1-\varepsilon')}) \ge \exp(b'nN^2) $$

for some $b'$ depending only on $\delta$ (more precisely, we set again $r = \varepsilon'^2, b = K\varepsilon'^2/2$ and $b' = b/2$).

Let $T_1 \subset S_\varepsilon$ be a maximal subset such that any two points in $T_1$ are strongly $\delta$-separated. By maximality of $T_1$ for any $u \in S_\varepsilon$ there is $x \in T_1$ such that $u, x$ are not strongly $\delta$-separated. This means that there is $w \in U(n)$ such that

$$ \left\| \sum u_j \otimes \overline{(w \cdot x)_j} \right\| > n(1 - \delta). $$

Choose $w' \in N_\xi$ such that $\|w - w'\| \le \xi$. Then by (2.10) and the triangle inequality we have

$$ \left\| \sum u_j \otimes \overline{(w'.x)_j} \right\| \ge \left\| \sum u_j \otimes \overline{(w.x)_j} \right\| - n\xi > n(1 - \delta - \xi) = 1 - \delta_1. $$
By (2.12) it follows that $d'(u, w'.x) < \sqrt{2n(1 - \varepsilon')}$. In other words, we find that the set
$T_2 = \{w'.x | w' \in \mathcal{N}_{\xi}, x \in T_1\}$ is a $\sqrt{2n(1 - \varepsilon')}$-net for $S_{\varepsilon}$, and hence

$$
\exp(b'nN^2) \le N(S_\varepsilon, d', \sqrt{2n(1-\varepsilon')}) \le |T_2| \le |\mathcal{N}_\xi| |T_1| \le (D/\xi)^{2n^2} |T_1|.
$$

This yields

$$
|T_1| \geq (2D/(1-\delta))^{-2n^2} \exp(b'nN^2).
$$

Assuming $\varepsilon \le \varepsilon_0$, this completes the proof, since for $N^2/n \ge N_0(\delta)$ the first factor can be absorbed, say, by choosing $\beta'_\delta = b'/2$. The case $\varepsilon_0 < \varepsilon < 1$ follows a fortiori since $S_{\varepsilon_0} \subset S_\varepsilon$.

The last assertion follows (for suitably adjusted values of $\beta'_\delta$ and $n_0$) as in Remark 1.4. Indeed, choosing $n_0$ large enough (depending on $\alpha$) we can make sure that $\mathbb{P}(S_\varepsilon) > 1 - \alpha/2$ so that $\mathbb{P}(A_N \cap S_\varepsilon) > \alpha/2$. We can then run the preceding proof using the set $A_N \cap S_\varepsilon$ in place of $S_\varepsilon$. $\square$

**Theorem 2.15.** For any $R > 1$, there are numbers $\beta_1 > 0$, $n_0 > 1$ and a function $n \mapsto N_0(n)$ from $\mathbb{N}$ to itself such that for any $n \ge n_0$ and $N \ge N_0(n)$, there is a family $\{E_t \mid t \in T_1\}$ of $n$-dimensional subspaces of $M_N$, of cardinality $|T_1| \ge \exp(\beta_1 n N^2)$, such that for any $s \ne t \in T_1$ we have

$d_{cb}(E_s, E_t) > R.$

Proof. Fix $0 < \delta < 1$. We will prove this for $R = (1 - \delta)^{-1}$. We will use the set $T_1$ from the preceding lemma and we let $E_t = \text{span}\{t_1, \dots, t_n\}$. We may clearly assume (say by perturbation) that $\{t_1, \dots, t_n\}$ are linearly independent for all $t \in T_1$ so that $\dim(E_t) = n$ (but this will be automatic, see below). Consider $s \ne t \in T_1$. Let $W \in M_n$, and let $W : E_s \to E_t$ denote the associated linear map so that $W_{s,j} = \sum_i W_{ij} t_i$.

We claim that we can “make sure” that for all $N$ large enough

$$
\mathrm{tr} |W| \le n(1 - \delta)^{1/2}.
$$

We first clarify what we mean here by “N large enough”. Let $0 < \gamma_1 < 1$ be such that

$$
(1 - \gamma_1)^{-1} (1 - \delta) = (1 - \delta)^{1/2}, \qquad (2.13)
$$

and let

$$
\Delta_{N,n}(t) = n^2 \sup_{i \neq j} |\tau_N(t_i t_j^*)|.
$$

Then we require that $N$ is large enough (depending on a fixed $n$) so that with respect to
the uniform probability on $U(N)^n$ we have

$$
\mathbb{P}\{t \in U(N)^n \mid \Delta_{N,n}(t) < \gamma_1\} > 1/2. \quad (2.14)
$$

Clearly this is possible because, by the almost sure weak convergence, we know that
$\tau_N(t_i t_j^*) \to 0$ when $N \to \infty$ for any $1 \le i \ne j \le n$.

Using the last assertion in the preceding lemma, we see that we may assume

$$
\forall t \in T_1 \quad \Delta_{N,n}(t) < \gamma_1.
$$
To verify the above claim, we will use an idea from [20] (refining one in [13]). First we note that for any matrix $a = [a_{ij}]$ and for any $t \in U(N)^n$, if we assume $\tau_N(t_i t_j^*) = 0$ for all $i \neq j$, then we have, by (1.1),

$$|\operatorname{tr}(a)| \le \left\| \sum a_{ij} t_i \otimes \bar{t}_j \right\|.$$

More generally, with the notation from (1.1), we have $\langle \sum a_{ij} t_i \otimes \bar{t}_j(I), I \rangle = \sum a_{ii} + \sum_{i \neq j} a_{ij} \tau_N(t_i t_j^*)$ and $|\sum_{i \neq j} a_{ij} \tau_N(t_i t_j^*)| \le \Delta_{N,n} \sup_{i \neq j} |a_{ij}|$. Therefore, without this assumption, we still have

$$|\operatorname{tr}(a)| \le \left\| \sum a_{ij} t_i \otimes \bar{t}_j \right\| + \gamma_1 \|a\|_1. \quad (2.15)$$

By (2.11) and an extreme point argument (since the unitaries are the extreme points of the unit ball of $M_n$) we have, for any $s \neq t \in T_1$ and any $w \in M_n$,

$$\left\| \sum \bar{w}_{ij} s_i \otimes \bar{t}_j \right\| \le \|w\| n(1 - \delta). \quad (2.16)$$

Now we can write for any $W : E_s \to E_t$, by (2.16),

$$\left\| \sum W s_j \otimes \overline{(w.t)_j} \right\| \le \|W\|_{cb} \left\| \sum s_j \otimes \overline{(w.t)_j} \right\| \le \|W\|_{cb} \|w\| n(1 - \delta).$$

Therefore

$$\left\| \sum_{i,j,k} W_{i,j} \bar{w}_{j,k} t_i \otimes \bar{t}_k \right\| \le \|W\|_{cb} \|w\| n(1 - \delta),$$

hence (replacing $w$ by its transpose) by (2.15) we have

$$|\operatorname{tr}(W w^*)| \le \|W\|_{cb} \|w\| n(1 - \delta) + \gamma_1 \|W w^*\|_1,$$

and hence taking the sup over all $w \in U(n)$,

$$\|W\|_1 = \operatorname{tr} |W| \le \|W\|_{cb} n(1 - \delta) + \gamma_1 \|W\|_1.$$

Thus, we conclude by (2.13) that

$$\operatorname{tr} |W| \le \|W\|_{cb} n(1 - \gamma_1)^{-1} (1 - \delta) = n \|W\|_{cb} (1 - \delta)^{1/2}. \quad (2.17)$$

Applying (2.17) with $W^{-1}$ in place of $W$ we find

$$\operatorname{tr} |W^{-1}| \le n \|W^{-1}\|_{cb} (1 - \delta)^{1/2},$$

and hence

$$\operatorname{tr} |W| \operatorname{tr} |W^{-1}| \le n^2 \|W\|_{cb} \|W^{-1}\|_{cb} (1 - \delta),$$

but we will justify below that any invertible matrix in $M_n$ satisfies

$$n^2 \le \operatorname{tr} |W| \operatorname{tr} |W^{-1}|, \quad (2.18)$$

so that we obtain

$$d_{cb}(E_s, E_t) \ge (1 - \delta)^{-1} = R.$$

To check (2.18) recall that for any pair $W_1, W_2 \in M_n$ the Schatten $p$-norms $\| \cdot \|_p$ satisfy, whenever $0 < p, q, r$ and $1/r = 1/p + 1/q$,

$$\|W_1 W_2\|_r \le \|W_1\|_p \|W_2\|_q.$$

Moreover $\|I\|_r = n^{1/r}$. Therefore, (2.18) follows by taking $r = 1/2$ and $p = q = 1$. $\square$
### 3. Random matrices and subexponential operator spaces

In a forthcoming sequel [29] to this paper, we introduce and study a generalization of the notion of exact operator space that we call subexponential. We briefly outline this here.

Our goal is to study a generalization of the notion of exact operator space for which the version of Grothendieck's theorem obtained in [31] is still valid.

**Notation.** Let $E$ be a finite-dimensional operator space. Fix $C > 0$. We denote by $K_E(N, C)$ the smallest integer $K$ such that there is an operator subspace $F \subset M_K$ such that

$$d_N(E, F) \leq C.$$

Note that obviously

$$K_E(N, C) \leq Nk_E(N, C). \qquad (3.1)$$

**Definition 3.1.** We say that an operator space $X$ is $C$-subexponential if

$$\limsup_{N \to \infty} \frac{\log K_E(N, C)}{N} = 0$$

for any finite-dimensional subspace $E \subset X$. We say that $X$ is subexponential if it is $C$-subexponential for some $C \geq 1$.

**Note.** If $X$ itself is finite-dimensional, it suffices to consider $E = X$.

We will denote by $C(X)$ the smallest $C$ such that $X$ is $C$-subexponential.

Recall that an operator space $X$ is called $C$-exact if for any finite-dimensional subspace $E \subset X$ and any $c > C$ there $k$ and $F \subset M_k$ such that $d_{cb}(E, F) < c$. We denote by $\mathrm{ex}(X)$ the smallest such $C$. We say that $X$ is exact if it is $C$-exact for some $C \geq 1$.

We observe in [29] that a finite-dimensional $E$ is $C$-exact iff for any $c > C$ the sequence $N \mapsto K_E(N, c)$ is bounded. In this light “subexponential” seems considerably more general than “exact”.

As shown by Kirchberg, a $C$*-algebra is exact iff it is 1-exact. We do not know whether the analogue of this for subexponential (or for matricially sub-Gaussian) $C$*-algebras is true. See [27, Ch. 17] or [5] for more background on exactness.

In [29] we show that for essentially all the results proved in either [13] or [31] we can replace exact by subexponential in the assumptions. Moreover, we show that there is a 1-subexponential $C$*-algebra that is not exact.

**Remark 3.2.** In the same vein, it is natural to call an operator space $X$ $C$-sub-Gaussian if $\limsup_{N \to \infty} N^{-2}\log K_E(N, C) = 0$ for any finite-dimensional subspace $E \subset X$. We do not have significant information about this class at this point, but to avoid confusion, we decided to call the spaces in Definition 2.12 “matricially sub-Gaussian”. Clearly by (3.1) “matricially sub-Gaussian” implies “sub-Gaussian” but the converse is unclear.
**Problems.** 1) Let $C > 1$. Assume that a finite-dimensional space $E$ satisfies $k_E(N, C) \le 1$ for all $N$. What does that imply about $E$? Is $E$ exact with a control on its exactness constant?

2) Assume $E$ is subexponential for some constant $C$. What growth does that imply for $N \mapsto k_E(N, C)$ (here $C$ could be a different constant)?

3) What is the order of growth (when $N \to \infty$) of $\log K_E(N, C)$ for $E = \ell_1^n$ or $E = OH_n$? In particular, when $C$ is close to 1, is it $O(N)$? or to the contrary does it grow like $N^2$?

**4. Appendix**

In this appendix we give a quick proof of an inequality that can be substituted in §2 for Hastings's result from [11], quoted above as Lemma 1.8. Our inequality is less sharp in some respects but stronger in some other. We only prove that (for some numerical constant $C$) $\mathbb{P}\{(u_j) \in U(N)^n \mid \|(\sum u_j \otimes \bar{u}_j)(1-P)\| > 4C\sqrt{n} + \epsilon n\} \to 1$ when $N \to \infty$ for any $\epsilon > 0$, while Hastings proves this with $2\sqrt{n-1}$ in place of $4C\sqrt{n}$, which is best possible. However the inequality below remains valid with more general (and even matricial) coefficients, and it gives a bound valid uniformly for all sizes $N$ (see (4.6)). It shows that up to a universal constant all moments of the norm of a linear combination of the form

$$S = \sum_j a_j U_j \otimes \bar{U}_j (1-P)$$

are dominated by those of the corresponding Gaussian sum

$$S' = \sum_j a_j Y_j \otimes \bar{Y}_j.$$

The advantage is that $S'$ is now simply separately a Gaussian random variable with respect to the independent Gaussian random matrices $(Y_j)$ and $(\bar{Y}_j)$.

We recall that we denote by $P$ the orthogonal projection onto the multiples of the identity. Also recall we denote by $S_2^N$ the space $M_N$ equipped with the Hilbert–Schmidt norm (recall $S_2^N \simeq \ell_2^N \otimes 2 \ell_2^N$). We will view elements of the form $\sum x_j \otimes \bar{y}_j$ with $x_j, y_j \in M_N$ as linear operators acting on $S_2^N$ as follows:

$$T(\xi) = \sum_j x_j \xi y_j^*,$$

so that

$$\| \sum x_j \otimes \bar{y}_j \| = \|T\|_{B(S_2^N)} \quad (4.1)$$

We denote by $(U_j)$ a sequence of i.i.d. random $N \times N$ matrices uniformly distributed over the unitary group $U(N)$. We will denote by $(Y_j)$ a sequence of i.i.d. Gaussian random $N \times N$ matrices, more precisely each $Y_j$ is distributed like the variable $Y$ that is such that $\{Y(i, j)N^{1/2}\}$ is a standard family of $N^2$ independent complex Gaussian variables with
mean zero and variance 1. In other words $Y(i, j) = (2N)^{-1/2}(g_{ij} + \sqrt{-1} g'_{ij})$ where $g_{ij}, g'_{ij}$ are independent Gaussian normal $N(0, 1)$ random variables.

We denote by $(Y'_j)$ an independent copy of $(Y_j)$.

We will denote by $\|\cdot\|_q$ the Schatten $q$-norm ($1 \le q \le \infty$), i.e. $\|x\|_q = (\text{tr}(|x|^q))^{1/q}$, with the usual convention that for $q = \infty$ this is the operator norm.

**Lemma 4.1.** There is an absolute constant $C$ such that for any $p \ge 1$ we have, for any scalar sequence $(a_j)$ and any $1 \le q \le \infty$,

$$ \mathbb{E} \left\| \sum_{j=1}^{n} a_j U_j \otimes \bar{U}_j (1-P) \right\|_{q}^{p} \le C^p \mathbb{E} \left\| \sum_{j=1}^{n} a_j Y_j \otimes \bar{Y}_j \right\|_{q}^{p} $$

(in fact, this holds for all $k$ and all matrices $a_j \in M_k$ with $a_j \otimes$ in place of $a_j$).

*Proof.* We assume that all three sequences $(U_j), (Y_j)$ and $(Y'_j)$ are mutually independent. The proof is based on the well known fact that the sequence $(Y_j)$ has the same distribution as $U_j|Y_j|$, or equivalently that the two factors in the polar decomposition $Y_j = U_j|Y_j|$ of $Y_j$ are mutually independent. Let $\mathcal{E}$ denote the conditional expectation operator with respect to the $\sigma$-algebra generated by $(U_j)$. Then we have $U_j \mathbb{E}|Y_j| = \mathcal{E}(U_j|Y_j|) = \mathcal{E}(Y_j)$, and moreover

$$ (U_j \otimes \bar{U}_j) \mathbb{E}(|Y_j| \otimes |\bar{Y}_j|) = \mathcal{E}(U_j|Y_j| \otimes \overline{U_j|Y_j|}) = \mathcal{E}(Y_j \otimes \bar{Y}_j). $$

Let

$$ T = \mathbb{E}(|Y_j| \otimes |\bar{Y}_j|) = \mathbb{E}(|Y| \otimes |\bar{Y}|). $$

Then we have

$$ \sum a_j (U_j \otimes \bar{U}_j) T(I-P) = \mathcal{E}((\sum a_j Y_j \otimes \bar{Y}_j)(I-P)). $$

Note that by rotational invariance of the Gaussian measure we have $(U \otimes \bar{U})T(U^* \otimes \bar{U}^*) = T$. Indeed, since $UYU^*$ and $Y$ have the same distribution it follows that also $UYU^* \otimes \overline{UYU^*}$ and $Y \otimes \bar{Y}$ have the same distribution, and hence so do their moduli.

Viewing $T$ as a linear map on $S_2^N = \ell_2^N \otimes \bar{\ell}_2^N$, this yields

$$ \forall U \in U(N) \quad T(U\xi U^*) = U T(\xi) U^*. $$

Representation theory shows that $T$ must be simply a linear combination of $P$ and $I-P$. Indeed, the unitary representation $U \mapsto U \otimes \bar{U}$ on $U(N)$ decomposes into exactly two distinct irreducibles, by restricting to either the subspace $\mathbb{C}I$ or its orthogonal. Thus, by Schur's Lemma we know a priori that there are two scalars $\chi'_N, \chi_N$ such that $T = \chi'_N P + \chi_N(I-P)$. We may also observe that $\mathbb{E}(|Y|^2) = I$ so that $T(I) = I$ and hence $\chi'_N = 1$, therefore

$$ T = P + \chi_N(I - P). $$
Moreover, since $T(I) = I$ and $T$ is self-adjoint, $T$ commutes with $P$ and hence $T(I-P) = (I-P)T$, so that we have

$$ \sum_{j=1}^{n} a_j (U_j \otimes \bar{U}_j)(1-P)T = \mathcal{E} \left( \sum_{j=1}^{n} a_j (Y_j \otimes \bar{Y}_j)(I-P) \right). \quad (4.2) $$

We claim that $T$ is invertible and there is an absolute constant $C_0$ so that

$$ \|T^{-1}\| = \chi_N^{-1} \le C_0. $$

From this and (4.2) it follows immediately that for any $p \ge 1$,

$$ \mathbb{E} \left\| \sum_{j=1}^{n} a_j (U_j \otimes \bar{U}_j)(1-P) \right\|_{q}^{p} \le C_0^p \mathbb{E} \left\| \sum_{j=1}^{n} a_j (Y_j \otimes \bar{Y}_j)(1-P) \right\|_{q}^{p}. \quad (4.3) $$

To check the claim it suffices to compute $\chi_N$. For $i \ne j$ we have a priori $T(e_{ij}) = e_{ij} \langle T(e_{ij}), e_{ij} \rangle$ but (since $\mathrm{tr}(e_{ij}) = 0$) we know $T(e_{ij}) = \chi_N e_{ij}$. Therefore for any $i \ne j$ we have $\chi_N = \langle T(e_{ij}), e_{ij} \rangle$, and the latter we can compute:

$$ \langle T(e_{ij}), e_{ij} \rangle = \mathbb{E} \mathrm{tr}(|Y| e_{ij} |Y|^* e_{ij}^*) = \mathbb{E}(|Y|_{ii} |Y|_{jj}). $$

Therefore,

$$ \begin{aligned} N(N-1)\chi_N &= \sum_{i \ne j} \mathbb{E}(|Y|_{ii} |Y|_{jj}) = \sum_{i,j} \mathbb{E}(|Y|_{ii} |Y|_{jj}) - \sum_{j} \mathbb{E}(|Y|_{jj}^2) \\ &= \mathbb{E}(\mathrm{tr} |Y|)^2 - N \mathbb{E}(|Y|_{11}^2). \end{aligned} $$

Note that $\mathbb{E}(|Y|_{11}^2) = \mathbb{E}\langle |Y|e_1, e_1 \rangle^2 \le \mathbb{E}\langle |Y|^2 e_1, e_1 \rangle = \mathbb{E}\|Y(e_1)\|_2^2 = 1$, and hence

$$ N(N-1)\chi_N = \sum_{i \ne j} \mathbb{E}(|Y|_{ii} |Y|_{jj}) \ge \mathbb{E}(\mathrm{tr} |Y|)^2 - N. $$

Now it is well known that $E|Y| = b_N I$ where $b_N$ is determined by $b_N = N^{-1}\mathbb{E}\mathrm{tr}|Y| = N^{-1}\|Y\|_1$ and $\mathrm{inf}_N b_N > 0$ (see e.g. [18, p. 80]). Actually, by a well known limit theorem originating in Wigner's work (see [36]), when $N \to \infty$, $N^{-1}\|Y\|_1$ tends almost surely to the $L_1$-norm denoted by $\|c\|_1$ of a circular random variable $c$ normalized in $L_2$. Therefore, $N^{-2}\mathbb{E}(\mathrm{tr}|Y|)^2$ tends to $\|c\|_1$. We have

$$ \chi_N = (N(N-1))^{-1} \sum_{i \ne j} \mathbb{E}(|Y|_{ii} |Y|_{jj}) \ge (N(N-1))^{-1} \mathbb{E}(\mathrm{tr}|Y|)^2 - (N-1)^{-1}, $$

and this implies

$$ \liminf_{N \to \infty} \chi_N \ge \|c\|_1^2, $$

and actually $\chi_N \to \|c\|_1^2$. In any case, we have

$$ \inf_N \chi_N > 0, $$

proving our claim with $C_0 = (\mathrm{inf}_N \chi_N)^{-1}$.
We will now deduce from (4.3) the desired estimate by a classical decoupling argument for multilinear expressions in Gaussian variables.

We first observe $\mathbb{E}((Y \otimes \bar{Y})(I-P)) = 0$. Indeed, by orthogonality, a simple calculation shows that $\mathbb{E}(Y \otimes \bar{Y}) = \sum_{ij} \mathbb{E}(Y_{ij} \bar{Y}_{ij})e_{ij} \otimes \bar{e}_{ij} = \sum_{ij} N^{-1} e_{ij} \otimes \bar{e}_{ij} = P$, and hence $\mathbb{E}((Y \otimes \bar{Y})(I-P)) = 0$.

We will use

$$ (Y_j, Y'_j) \stackrel{\text{dist}}{=} ((Y_j + Y'_j)/\sqrt{2}, (Y_j - Y'_j)/\sqrt{2}) $$

and if $\mathbb{E}_Y$ denotes the conditional expectation with respect to $Y$ we have (recall that $\mathbb{E}(Y_j \otimes \bar{Y}_j)(I-P) = 0$)

$$ \sum_{j=1}^{n} a_j Y_j \otimes \bar{Y}_j (I-P) = \mathbb{E}_Y \left( \sum_{j=1}^{n} a_j Y_j \otimes \bar{Y}_j (I-P) - \sum_{j=1}^{n} a_j Y'_j \otimes \bar{Y}'_j (I-P) \right). $$

Therefore

$$ \begin{aligned} \mathbb{E} \left\| \sum_{j=1}^{n} a_j Y_j \otimes \bar{Y}_j (1-P) \right\|_{q}^{p} &\le \mathbb{E} \left\| \sum_{j=1}^{n} a_j Y_j \otimes \bar{Y}_j (1-P) - \sum_{j=1}^{n} a_j Y'_j \otimes \bar{Y}'_j (I-P) \right\|_{q}^{p} \\ &= \mathbb{E} \left\| \sum_{j=1}^{n} a_j (Y_j + Y'_j)/\sqrt{2} \otimes \overline{(Y_j + Y'_j)/\sqrt{2}} (1-P) \right. \\ &\qquad \left. - \sum_{j=1}^{n} a_j (Y_j - Y'_j)/\sqrt{2} \otimes \overline{(Y_j - Y'_j)/\sqrt{2}} (I-P) \right\|_{q}^{p} \\ &= \mathbb{E} \left\| \sum_{j=1}^{n} a_j (Y_j \otimes \bar{Y}'_j + Y'_j \otimes \bar{Y}_j)(1-P) \right\|_{q}^{p} \end{aligned} $$

and hence by the triangle inequality

$$ \le 2^p \mathbb{E} \left\| \sum_{j=1}^{n} a_j (Y_j \otimes \bar{Y}'_j)(1-P) \right\|_q^p. $$

Thus we conclude a fortiori that

$$ \mathbb{E} \left\| \sum_{j=1}^{n} a_j U_j \otimes \bar{U}_j (1-P) \right\|_{q}^{p} \le (2C_0)^p \mathbb{E} \left\| \sum_{j=1}^{n} a_j (Y_j \otimes \bar{Y}'_j) \right\|_{q}^{p}, $$

so that we can take $C = 2C_0$. $\square$

**Theorem 4.2.** Let C be as in the preceding lemma. Let

$$ \hat{S}^{(N)} = \sum_{j=1}^{n} a_j U_j \otimes \bar{U}_j (1-P). $$

Then

$$ \limsup_{N \to \infty} \mathbb{E} \| \hat{S}^{(N)} \| \le 4C \left( \sum |a_j|^2 \right)^{1/2}. \quad (4.4) $$
Moreover we have almost surely

$$ \limsup_{N \to \infty} \| \hat{S}^{(N)} \| \le 4C \left( \sum |a_j|^2 \right)^{1/2}. \quad (4.5) $$

In addition, there is a constant $C' > 0$ such that for any scalars $(a_j)$,

$$ \forall N \ge 1 \quad \mathbb{E} \| \hat{S}^{(N)} \| \le C' \left( \sum |a_j|^2 \right)^{1/2}. \quad (4.6) $$

*Proof.* A very direct argument is indicated in Remark 4.5 below, but we prefer to base the proof on [9] in the style of [29] in order to make it clear that it remains valid with matrix coefficients. By [29, (1.1)] applied twice (for $k=1$) (see also [29, Remark 1.5]) one finds, for any even integer $p$,

$$ \mathbb{E} \operatorname{tr} \left| \sum_{j=1}^{n} a_j (Y_j \otimes \tilde{Y}_j') \right|^p \le (\mathbb{E} \operatorname{tr} |Y|^p)^2 \left( \sum |a_j|^2 \right)^{p/2}. \quad (4.7) $$

Therefore, by the preceding lemma,

$$ \mathbb{E} \operatorname{tr} |\hat{S}^{(N)}|^p \le C^p (\mathbb{E} \operatorname{tr} |Y|^p)^2 \left( \sum |a_j|^2 \right)^{p/2}, $$

and hence a fortiori

$$ \mathbb{E} \| \hat{S}^{(N)} \|^p \le N^2 C^p (\mathbb{E} \| Y \|^p)^2 \left( \sum |a_j|^2 \right)^{p/2}. $$

We then complete the proof, as in [29], using only the concentration of the variable $\|Y\|$. We have an absolute constant $\beta'$ and $\varepsilon(N) > 0$ tending to zero when $N \to \infty$, such that

$$ (\mathbb{E} \| Y \|^p)^{1/p} \le 2 + \varepsilon(N) + \beta' \sqrt{p/N}, $$

and hence

$$ (\mathbb{E} \| \hat{S}^{(N)} \|^p)^{1/p} \le N^{2/p} C (2 + \varepsilon(N) + \beta' \sqrt{p/N})^2 \left( \sum |a_j|^2 \right)^{1/2}. $$

Fix $0 < \varepsilon < 1$. If we choose $p$ to be the minimal even integer so that $N^{2/p} \le \exp \varepsilon$, i.e. $p = 2([\varepsilon^{-1} \log N] + 1)$ (note that $p > 2\varepsilon^{-1} \log N$ and also $p \ge 2$), we obtain

$$ \mathbb{E} \| \hat{S}^{(N)} \| \le (\mathbb{E} \| \hat{S}^{(N)} \|^p)^{1/p} \le 4e^{\varepsilon C(1 + \varepsilon^{-1} \varepsilon'(N))} \left( \sum |a_j|^2 \right)^{1/2} $$

where $\varepsilon'(N)$ is independent of $\varepsilon$ and satisfies $\varepsilon'(N) \to 0$ when $N \to \infty$. Clearly (4.4) and (4.6) follow.

Let $R_N = 4C(1 + \varepsilon^{-1}\varepsilon'(N))(\sum |a_j|^2)^{1/2}$. By Chebyshev's inequality, $(\mathbb{E}\|\hat{S}^{(N)}\|^p)^{1/p} \le e^\varepsilon R_N$ implies

$$ \mathbb{P}\{\|\hat{S}^{(N)}\| > e^{2\varepsilon} R_N\} \le \exp(-\varepsilon p) = N^2. $$

From this it is immediate that almost surely

$$ \limsup_{N \to \infty} \| \hat{S}^{(N)} \| \le e^{2\varepsilon} 4C \left( \sum |a_j|^2 \right)^{1/2}, $$

and hence (4.5) follows. $\square$
**Remark 4.3.** The same argument can be applied when $a_j \in M_k$ for any integer $k > 1$. Then we find

$$ \limsup_{N \to \infty} \mathbb{E} \left\| \sum_{j=1}^{n} a_j \otimes U_j \otimes \bar{U}_j (1-P) \right\| \le 4C \max \left\{ \left\| \sum a_j^* a_j \right\|^{1/2}, \left\| \sum a_j a_j^* \right\|^{1/2} \right\}. $$

Moreover we have almost surely

$$ \limsup_{N \to \infty} \left\| \sum_{j=1}^{n} a_j \otimes U_j \otimes \bar{U}_j (1-P) \right\| \le 4C \max \left\{ \left\| \sum a_j^* a_j \right\|^{1/2}, \left\| \sum a_j a_j^* \right\|^{1/2} \right\}. $$

**Remark 4.4.** The preceding also allows us to majorize double sums of the form

$$ \sum_{i \neq j} a_{ij} \otimes U_i \otimes \bar{U}_j. $$

Indeed, we have $\mathcal{E}(Y_i \otimes \bar{Y}_j) = (U_i \otimes \bar{U}_j)(\mathbb{E}|Y| \otimes \mathbb{E}|Y|)$ for any $i \neq j$, and there is a constant $b > 0$ (independent of $N$) such that $\mathbb{E}|Y| \ge bI$. Therefore, for any $p \ge 1$, any $k$, any sequence $(a_{ij})$ in $M_k$, and any $1 \le q \le \infty$, we have

$$ \mathbb{E} \left\| \sum_{i \neq j} a_{ij} \otimes U_i \otimes \bar{U}_j \right\|_q^p \le b^{-2p} \mathbb{E} \left\| \sum_{i \neq j} a_{ij} \otimes Y_i \otimes \bar{Y}_j \right\|_q^p \le 2^p b^{-2p} \mathbb{E} \left\| \sum_{i \neq j} a_{ij} \otimes Y_i \otimes \bar{Y}_j' \right\|_q^p. $$

**Remark 4.5.** We refer the reader to [28, Theorem 16.6] for a self-contained proof of (4.7) for double sums of the form $\sum_{i,j} a_{ij} Y_i \otimes \bar{Y}_j'$ for scalar coefficients $a_{ij}$.

*Acknowledgements.* Thanks to Kate Juschenko for useful conversations at an early stage of this investigation. I am grateful to Mikael de la Salle for simplifying the proof of Lemma 1.11, and to him and Yanqi Qiu for numerous corrections. Thanks also to S. Szarek for a useful suggestion on the appendix.

This research was partially supported by ANR-2011-BS01-008-01.

## References

[1] Bekka, B., de la Harpe, P., Valette, A.: Kazhdan's Property (T). Cambridge Univ. Press, Cambridge (2008) Zbl 1146.22009 MR 2415834

[2] Ben-Aroya, A., Schwartz, O., Ta-Shma, A.: Quantum expanders: motivation and constructions. Theory Comput. 6, 47–79 (2010) Zbl 1213.81052 MR 2719757

[3] Ben-Aroya, A., Ta-Shma, A.: Quantum expanders and the quantum entropy difference problem. arXiv:quant-ph/0702129 (2007)

[4] Benyamini, Y., Lindenstrauss, J.: Geometric Nonlinear Functional Analysis. Vol. 1. Amer. Math. Soc., Providence, RI (2000) Zbl 0946.46002 MR 1727673

[5] Brown, N. P., Ozawa, N.: C*-Algebras and Finite-Dimensional Approximations. Grad. Stud. Math. 88, Amer. Math. Soc., Providence, RI (2008) Zbl 1160.46001 MR 2391387

[6] Davidson, K., Szarek, S.: Local operator theory, random matrices and Banach spaces. In: Handbook of the Geometry of Banach Spaces, Vol. I, North-Holland, Amsterdam, 317–366 (2001) Zbl 1067.46008 MR 1863696
[7] Elton, J.: Sign-embeddings of $\ell_1^n$, Trans. Amer. Math. Soc. **279**, 113-124 (1983) Zbl 0525.46011 MR 0704605

[8] Figà-Talamanca, A., Rider, D.: A theorem of Littlewood and lacunary series for compact groups. Pacific J. Math. **16**, 505-514 (1966) Zbl 0142.10501 MR 0206626

[9] Haagerup, U., Thorbjoernsen, S.: Random matrices and K-theory for exact C*-algebras. Doc. Math. **4**, 341-450 (1999) Zbl 0933.46051 MR 1710376

[10] de la Harpe, P., Robertson, A. G., Valette, A.: On the spectrum of the sum of generators for a finitely generated group. Israel J. Math. **81**, 65-96 (1993) Zbl 0791.43008 MR 1231179

[11] Hastings, M.: Random unitaries give quantum expanders, Phys. Rev. A **76**, no. 3, 032315, 11 pp. (2007) MR 2486279

[12] Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc. **43**, 439-561 (2006) Zbl 1147.68608 MR 2247919

[13] Junge, M., Pisier, G.: Bilinear forms on exact operator spaces and $B(H) \otimes B(H)$. Geom. Funct. Anal. **5**, 329-363 (1995) Zbl 0832.46052 MR 1334870

[14] Ledoux, M.: The Concentration of Measure Phenomenon. Amer. Math. Soc., Providence, RI (2001) Zbl 0995.60002 MR 1849347

[15] Ledoux, M., Talagrand, M.: Probability in Banach Spaces. Isoperimetry and Processes. Springer, Berlin (1991) Zbl 0748.60004 MR 1102015

[16] Lehner, F., $M_n$-espaces, sommes d'unitaires et analyse harmonique sur le groupe libre. PhD thesis, Univ. Paris VI (1997)

[17] Lubotzky, A.: Discrete Groups, Expanding Graphs and Invariant Measures. Progr. Math. 125, Birkhäuser (1994) Zbl 0826.22012 MR 1308046

[18] Marcus, M. B., Pisier, G.: Random Fourier Series with Applications to Harmonic Analysis. Ann. of Math. Stud. 101, Princeton Univ. Press (1981) Zbl 0474.43004 MR 06305320

[19] Meshulam, R., Wigderson, A.: Expanders in group algebras. Combinatorica **24**, 659-680 (2004) Zbl 1080.05043 MR 2096820

[20] Oikhberg, T., Ricard, É.: Operator spaces with few completely bounded maps. Math. Ann. **328**, 229-259 (2004) Zbl 1054.46042 MR 2030376

[21] Pajor, A.: Sous-espaces $\ell_1^n$ des espaces de Banach. Travaux en Cours 16, Hermann, Paris (1985) Zbl 1032.46021 MR 0903247

[22] Pisier, G.: Remarques sur un résultat non publié de B. Maurey. In: Seminar on Functional Analysis, 1980-1981, exp. V, 13 pp., École Polytech., Palaiseau (1981); http://www.numdam.org/numdam-bin/feuilleter?j=SAF Zbl 0491.46017 MR 0659306

[23] Pisier, G.: De nouvelles caractérisations des ensembles de Sidon. In: Mathematical Analysis and Applications, Adv. Math. Suppl. Stud. 7B, Academic Press, 685-726 (1981) Zbl 0468.43008 MR 0634264

[24] Pisier, G.: Condition d'entropie et caractérisations arithmétiques des ensembles de Sidon. In: Modern Topics in Harmonic Analysis (Torino/Milano, 1982), Vol. II, Inst. di Alta Mat., Roma, 911-944 (1983) Zbl 0539.43004 MR 0748887

[25] Pisier, G.: The Volume of Convex Bodies and Banach Space Geometry. Cambridge Univ. Press (1989) Zbl 0933.46013 MR 1036275

[26] Pisier, G.: The operator Hilbert space OH, complex interpolation and tensor norms. Mem. Amer. Math. Soc. **122**, no. 585 (1996) Zbl 0932.46046 MR 1342022

[27] Pisier, G.: Introduction to Operator Space Theory. Cambridge Univ. Press, Cambridge (2003) Zbl 1093.46001 MR 2006539

[28] Pisier, G.: Grothendieck's Theorem, past and present. Bull. Amer. Math. Soc. **49**, 237-323 (2012) Zbl 1244.46006 MR 2888168

[29] Pisier, G.: Random matrices and subexponential operator spaces. Israel J. Math., to appear
[30] Pisier, G.: On the metric entropy of the Banach–Mazur compactum. arXiv:1306.5325 (2013)

[31] Pisier, G., Shlyakhtenko, D.: Grothendieck's theorem for operator spaces. Invent. Math. **150**, 185–217 (2002) [Zbl 1033.46044 MR 1930886](https://zblmathCentral.e3math Central Online) [arXiv:1003.4604](https://arXiv.org/abs/1003.4604)

[32] Regev, O., Vidick, T.: Elementary proofs of Grothendieck theorems for completely bounded norms. J. Operator Theory, to appear

[33] Szarek, S.: The finite-dimensional basis problem with an appendix on nets of Grassmann manifolds. Acta Math. **151**, 153–179 (1983) [Zbl 0554.46004 MR 0723008](https://zblmathCentral.e3math Central Online)

[34] Szarek, S.: Nets of Grassmann manifold and orthogonal group. In: Proc. Research Workshop in Banach Space Theory, Univ. of Iowa, 169–185 (1981) [Zbl 0526.53047 MR 0724113](https://zblmathCentral.e3math Central Online)

[35] Voiculescu, D.: Property T and approximation of operators. Bull. London Math. Soc. **22**, 25–30 (1990) [Zbl 0718.46023 MR 1026768](https://zblmathCentral.e3math Central Online)

[36] Voiculescu, D., Dykema, K., Nica, A.: Free Random Variables. Amer. Math. Soc., Providence, RI (1992) [Zbl 0795.46049 MR 1217253](https://zblmathCentral.e3math Central Online)

[37] Wassermann, S.: C\*-algebras associated with groups with Kazhdan's property T. Ann. of Math. **134**, 423–431 (1991) [Zbl 0754.4640 MR 1127480](https://zblmathCentral.e3math Central Online)