diam girth nameyeardelim, 75mm 74e année, 2021–2022 1188 ††thanks: The author
was supported by a Junior Research Fellowship from Trinity College, Cambridge.

# Average distortion embeddings, nonlinear spectral gaps, and a metric John
theorem

after Assaf Naor

Alexandros Eskenazis  Trinity College
University of Cambridge
Cambridge, CB2 1TQ, United Kingdom  Institut de Mathématiques de Jussieu
CNRS & Sorbonne Université
Paris, 75252, France<EMAIL_ADDRESS>
(Janvier 2022)

##  1 Introduction

Preamble. The main purpose of this survey is to present a concise exposition
of some applications of the theory of nonlinear spectral gaps which can serve
as a roadmap for newcomers in the field and experts alike. Having as our main
focus a result (Theorem 1) of [71], we shall highlight some ideas which have
played a pivotal role in recent developments and mention connections with
classical geometric and algorithmic questions. The material of this paper is a
mere expository repackaging of a selection of such developments and any
difference in presentation is solely cosmetic.

Let $(\mathcal{M},d_{\mathcal{M}})$, $(\mathcal{N},d_{\mathcal{N}})$ be two
metric spaces and $D\in[1,\infty)$. We say that
$(\mathcal{M},d_{\mathcal{M}})$ embeds into $(\mathcal{N},d_{\mathcal{N}})$
with bi-Lipschitz distortion at most $D$ if there exists a scaling factor
$\sigma\in(0,\infty)$ and a map $f:\mathcal{M}\to\mathcal{N}$ such that

$\forall\ x,y\in\mathcal{M},\qquad\sigma d_{\mathcal{M}}(x,y)\leq
d_{\mathcal{N}}\big{(}f(x),f(y)\big{)}\leq\sigma Dd_{\mathcal{M}}(x,y).$ (1)

Following [71], we say that an _infinite_ 111The study of average distortion
embeddings for _finite_ metric spaces goes back at least to the work of [83]
(see also [1] for various related notions). metric space
$(\mathcal{M},d_{\mathcal{M}})$ embeds into $(\mathcal{N},d_{\mathcal{N}})$
with $q$-average distortion $D$, where $q>0$, if for every Borel probability
measure $\mu$ on $\mathcal{M}$, there exists
$\sigma=\sigma_{\mu}\in(0,\infty)$ and a $\sigma D$-Lipschitz map
$f=f_{\mu}:\mathcal{M}\to\mathcal{N}$ with

$\int\\!\\!\\!\\!\int_{\mathcal{M}\times\mathcal{M}}d_{\mathcal{N}}\big{(}f(x),f(y)\big{)}^{q}\,\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y)\geq\sigma^{q}\int\\!\\!\\!\\!\int_{\mathcal{M}\times\mathcal{M}}d_{\mathcal{M}}(x,y)^{q}\,\mathop{}\\!\mathrm{d}\mu(x)\mathop{}\\!\mathrm{d}\mu(y).$
(2)

If the target space $\mathcal{N}$ is a normed space, the parameter
$\sigma_{\mu}$ can be omitted by rescaling.

The $\theta$-snowflake of a metric space $(\mathcal{M},d_{\mathcal{M}})$ is
the metric space $(\mathcal{M},d_{\mathcal{M}}^{\theta})$, $\theta\in(0,1]$.
The primary goal of this survey is to present a self-contained proof of the
following deep embedding theorem of [71] in which asymptotically optimal
bounds for the quadratic average distortion (i.e. corresponding to exponent
$q=2$ in equation eq:av-dist above) of $\tfrac{1}{2}$-snowflakes of finite-
dimensional normed spaces into the separable Hilbert space $\ell_{2}$ are
established. The, so called, _average John theorem_ reads as follows.

[Average John] There exists a universal constant $C\in(0,\infty)$ such that
the $\tfrac{1}{2}$-snowflake of any finite-dimensional normed space
$(X,\|\cdot\|_{X})$ admits an embedding into $\ell_{2}$ with quadratic average
distortion at most $C\sqrt{\log(\mathrm{dim}(X)+1)}$.

Theorem 1 is a metric counterpart of a classical theorem of [42], asserting
that any finite-dimensional normed space embeds into $\ell_{2}$ with bi-
Lipschitz distortion at most $\sqrt{\mathrm{dim}(X)}$. This statement is
famously optimal, e.g. for $X=\ell_{1}^{d}$ or $X=\ell_{\infty}^{d}$, yet
Naor’s theorem shows that an exponential improvement of the relevant
distortion is possible if one relaxes the pointwise lower bound of the bi-
Lipschitz condition eq:bi-lip to the averaged requirement eq:av-dist and
replaces the normed space $(X,\|\cdot\|_{X})$ by its $\tfrac{1}{2}$-snowflake.
Before explaining the ideas that come into the proof of Theorem 1, it is worth
pointing out that both of these modifications of John’s theorem are necessary
in order to deduce bounds for the distortion which are subpolynomial on
$\mathrm{dim}(X)$. In fact, the average John theorem is optimal in three
distinct ways.

$\bullet$ If one is interested in bi-Lipschitz embeddings of snowflakes of
normed spaces $X$ into $\ell_{2}$ in lieu of average distortion embeddings,
then the relevant distortion has to depend polynomially on $\mathrm{dim}(X)$.
Indeed, in [71, Lemma 2], it is shown that the bi-Lipschitz distortion
required to embed the $\theta$-snowflake of $\ell_{\infty}^{d}$ into
$\ell_{2}$ is at least a constant multiple of $d^{\theta/2}$. The proof relies
on metric cotype.

$\bullet$ The exponent $\tfrac{1}{2}$ is the least amount of snowflaking that
one needs to perform in order to obtain embeddings whose quadratic average
distortion depends subpolynomially on $\mathrm{dim}(X)$. More specifically, in
[71, Lemma 13] it is shown that for any $\varepsilon\in(0,\tfrac{1}{2}]$, the
quadratic average distortion required to embed the
$(\tfrac{1}{2}+\varepsilon)$-snowflake of $\ell_{1}^{d}$ into $\ell_{2}$ is at
least a constant multiple of $d^{\varepsilon}$. The proof relies on Enflo
type.

$\bullet$ Finally, $\sqrt{\log\mathrm{dim}(X)}$ is the asymptotically optimal
bound for the quadratic average distortion required to embed the
$\tfrac{1}{2}$-snowflake of an arbitrary finite-dimensional space $X$ into
$\ell_{2}$. This will be further explained (for $X=\ell_{\infty}^{d}$) in
Remark 6.1 below.

In the rest of the introduction, we shall describe the strategy of the proof
of the average John theorem and introduce the necessary background.

###  1.1 Nonlinear spectral gaps

Let $\triangle^{n-1}=\\{(\pi_{1},\ldots,\pi_{n})\in[0,1]^{n}:\
\sum_{i=1}^{n}\pi_{i}=1\\}$ be the $n$-dimensional standard simplex. Consider
a (row)-stochastic matrix $A=(a_{ij})_{i,j=1}^{n}\in M_{n}(\mathbb{R})$, that
is, a matrix for which $(a_{i1},\ldots,a_{in})\in\triangle^{n-1}$ for every
$i\in\\{1,\ldots,n\\}$. Given a vector
$\pi=(\pi_{1},\ldots,\pi_{n})\in\triangle^{n-1}$, we say that the matrix $A$
is $\pi$-reversible if $\pi_{i}a_{ij}=\pi_{j}a_{ji}$ for every
$i,j\in\\{1,\ldots,n\\}$. These objects admit a classical probabilistic
interpretation. Consider the discrete-time homogeneous Markov chain
$(X_{t})_{t\geq 0}$ on the state space $\\{1,\ldots,n\\}$ with transition
probabilities given by

$\forall\ i,j\in\\{1,\ldots,n\\},\qquad\mathbb{P}\\{X_{t+1}=j\ |\
X_{t}=i\\}=a_{ij},$ (3)

where $t\geq 0$. If the transition matrix $A$ is $\pi$-reversible, then $\pi$
is also a stationary distribution for the process $(X_{t})_{t\geq 0}$, that
is, if $X_{0}$ is distributed according to $\pi$ then so is $X_{t}$ for any
$t\geq 1$. This is expressed algebraically by the matrix identity $\pi A=\pi$,
where $\pi$ is thought of as a row-vector. In the probabilistic framework
above, reversibility simply means that the Markov process is invariant under
time reversal in the sense that $(X_{0},X_{1},\ldots,X_{T})$ has the same
joint distribution as $(X_{T},X_{T-1},\ldots,X_{0})$ for any $T\in\mathbb{N}$.

Consider the Hilbert space
$L_{2}(\pi)=(\mathbb{R}^{n},\|\cdot\|_{L_{2}(\pi)})$ whose (semi-)norm is
given by

$\forall\
x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{n},\qquad\|x\|_{L_{2}(\pi)}=\Big{(}\sum_{i=1}^{n}\pi_{i}x_{i}^{2}\Big{)}^{\frac{1}{2}}.$
(4)

Analytically, the stochastic matrix $A$ is $\pi$-reversible if and only if it
defines a self-adjoint contraction on $L_{2}(\pi)$ with real eigenvalues which
we shall denote by
$1=\lambda_{1}(A)\geq\lambda_{2}(A)\geq\cdots\geq\lambda_{n}(A)\geq-1$. The
spectral gap of $A$ is the algebraic quantity $1-\lambda_{2}(A)$ which is
known to encode important combinatorial properties of the matrix. It is a
simple linear algebra exercise to show that the reciprocal
$\gamma(A)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(1-\lambda_{2}(A))^{-1}$
of the spectral gap is the least constant $\gamma\in(0,\infty]$ for which the
inequality

$\forall\
x_{1},\ldots,x_{n}\in\ell_{2},\qquad\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|x_{i}-x_{j}\|_{\ell_{2}}^{2}\leq\gamma\sum_{i,j=1}^{n}\pi_{i}a_{ij}\|x_{i}-x_{j}\|_{\ell_{2}}^{2}$
(5)

holds true. It is a well-known consequence of Cheeger’s inequality (see, e.g.,
[23]) that upper bounds on $\gamma(A)$ are equivalent to good expansion
properties of the underlying weighted graph defined by $A$.

The above analytic characterization of a spectral gap as an optimal constant
in a functional inequality was the starting point for the theory of _nonlinear
spectral gaps_ , of which Theorem 1 is the latest application. Let
$(\mathcal{M},d_{\mathcal{M}})$ be a metric space and $p\in(0,\infty)$. If
$\pi\in\triangle^{n-1}$ and $A$ is a $\pi$-reversible stochastic matrix, the
spectral gap of $A$ with respect to $d_{\mathcal{M}}^{p}$, denoted by
$\gamma(A,d_{\mathcal{M}}^{p})$, is the least $\gamma\in(0,\infty]$ such that

$\forall\
x_{1},\ldots,x_{n}\in\mathcal{M},\qquad\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{p}\leq\gamma\sum_{i,j=1}^{n}\pi_{i}a_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{p}.$
(6)

If the metric $d_{\mathcal{M}}$ is inherited by a norm $\|\cdot\|$, we will
denote $\gamma(A,d_{\mathcal{M}}^{p})$ by $\gamma(A,\|\cdot\|^{p})$. As
explained in [63], unless $\mathcal{M}$ is a singleton, if
$\gamma(A,d_{\mathcal{M}}^{p})$ is finite then $\lambda_{2}(A)$ is bounded
away from 1 by a positive quantity depending only on
$\gamma(A,d_{\mathcal{M}}^{p})$. On the other hand, obtaining sensible upper
bounds for $\gamma(A,d_{\mathcal{M}}^{p})$ in terms of the usual spectral gap
$1-\lambda_{2}(A)$ is a notoriously hard task even for very structured metric
spaces $(\mathcal{M},d_{\mathcal{M}})$. This difficulty reflects the fact that
nonlinear spectral gap inequalities eq:nsg capture delicate interactions of
spectral properties of the matrix $A$ and geometric characteristics of the
underlying metric space $(\mathcal{M},d_{\mathcal{M}})$.

The study of nonlinear spectral gap inequalities eq:nsg has led to very
fruitful investigations which have been impactful in various areas of
mathematics and theoretical computer science such as metric geometry,
geometric group theory, operator algebras, Alexandrov geometry and
approximation algorithms. We refer, for instance, to the works of [56], [37],
[49, 50], [82], [73], [46], [62, 63, 64], [65], [68, 69, 71, 7, 6] (see also
Section 6 below for a high-level exposition of some of those). The pertinence
of nonlinear spectral gaps to the study of average distortion embeddings into
normed spaces and Theorem 1 stems from an important duality principle which
was discovered by [68] and which we shall now describe.

###  1.2 Duality

Fix $\pi\in\triangle^{n-1}$ and a $\pi$-reversible stochastic matrix $A\in
M_{n}(\mathbb{R})$. Let $(\mathcal{M},d_{\mathcal{M}})$ be a metric space,
$(Y,\|\cdot\|_{Y})$ be a normed space and assume that the $\theta$-snowflake
of $\mathcal{M}$ embeds into $Y$ with $q$-average distortion $D\in[1,\infty)$.
Then, for $x_{1},\ldots,x_{n}\in\mathcal{M}$, there exist
$y_{1},\ldots,y_{n}\in Y$ such that $\|y_{i}-y_{j}\|_{Y}\leq
Dd_{\mathcal{M}}(x_{i},x_{j})^{\theta}$ for every $i,j\in\\{1,\ldots,n\\}$ and

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|y_{i}-y_{j}\|_{Y}^{q}\geq\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{\theta
q}.$ (7)

Therefore, we have

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{\theta
q}\\!\stackrel{{\scriptstyle\eqref{eq:comp1}}}{{\leq}}\\!\gamma(A,\|\cdot\|_{Y}^{q})\sum_{i,j=1}^{n}\pi_{i}a_{ij}\|y_{i}-y_{j}\|_{Y}^{q}\leq\\!D^{q}\gamma(A,\|\cdot\|_{Y}^{q})\\!\sum_{i,j=1}^{n}\pi_{i}a_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{\theta
q}$

which implies that $\gamma(A,d_{\mathcal{M}}^{\theta q})\leq
D^{q}\gamma(A,\|\cdot\|_{Y}^{q})$. Moreover222As usual, we denote by
$\ell_{q}(Y)=\big{\\{}y=(y_{n})_{n\geq 1}\in Y^{\mathbb{N}}:\
\|y\|_{\ell_{q}(Y)}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\big{(}\sum_{n\geq
1}\|y_{n}\|_{Y}^{q}\big{)}^{1/q}<\infty\big{\\}}$., as tensorization gives the
identity $\gamma(A,\|\cdot\|_{Y}^{q})=\gamma(A,\|\cdot\|_{\ell_{q}(Y)}^{q})$
and $\gamma(A,\|\cdot\|_{W}^{q})$ is only determined by the finite-dimensional
structure of $W$, the above simple argument shows that if the
$\theta$-snowflake of $\mathcal{M}$ embeds with $q$-average distortion
$D\in[1,\infty)$ into any Banach space $Z$ which is finitely representable in
$\ell_{q}(Y)$, then $\gamma(A,d_{\mathcal{M}}^{\theta q})\leq
D^{q}\gamma(A,\|\cdot\|_{Y}^{q})$ for any $\pi$-reversible stochastic matrix
$A\in M_{n}(\mathbb{R})$. The first important step towards Theorem 1 is the
following striking converse to this implication, proven by [68, Theorem 1.3].

[Naor’s duality principle] Suppose that $q,D\in[1,\infty)$ and
$\theta\in(0,1]$. Let $(\mathcal{M},d_{\mathcal{M}})$ be a metric space and
$(Y,\|\cdot\|_{Y})$ be a Banach space such that for every $n\in\mathbb{N}$ and
$\pi\in\triangle^{n-1}$, every $\pi$-reversible stochastic matrix $A\in
M_{n}(\mathbb{R})$ satisfies

$\gamma(A,d_{\mathcal{M}}^{\theta q})\leq D^{q}\gamma(A,\|\cdot\|_{Y}^{q}).$
(8)

Then, for any $\varepsilon>0$ the $\theta$-snowflake of $\mathcal{M}$ embeds
into some ultrapower333We refer to [39] for background on ultraproducts of
Banach spaces. For the purposes of this discussion it suffices to say that an
ultrapower $Z^{\mathcal{U}}$ of a Banach space $Z$ is a Banach space
containing $Z$ with various compactness properties such that any finite-
dimensional subspace of $Z^{\mathcal{U}}$ embeds into $Z$ with distortion
$1+\varepsilon$ for any $\varepsilon>0$. of $\ell_{q}(Y)$ with $q$-average
distortion at most $D+\varepsilon$.

We emphasize that Theorem 1.2 is an _existential_ result whose proof does not
shed any light on any additional properties of the average distortion
embeddings at hand. Its proof consists of an elegant Hahn–Banach separation
argument which we shall present in Section 2. In the setting of the average
John theorem, the metric space $\mathcal{M}$ is a finite-dimensional normed
space $(X,\|\cdot\|_{X})$, $Y$ is the Hilbert space $\ell_{2}$, $q=2$ and
$\theta=\tfrac{1}{2}$. As any ultrapower of $\ell_{2}$ is itself a Hilbert
space (see [39]), Naor’s duality theorem shows that the embedding statement of
Theorem 1 is equivalent to the following comparison estimate for nonlinear
spectral gaps.

Let $(X,\|\cdot\|_{X})$ be a finite-dimensional normed space. Then, for every
$n\in\mathbb{N}$ and $\pi\in\triangle^{n-1}$, every $\pi$-reversible
stochastic matrix $A\in M_{n}(\mathbb{R})$ satisfies

$\gamma(A,\|\cdot\|_{X})\leq\frac{C\log(\mathrm{dim}(X)+1)}{1-\lambda_{2}(A)},$
(9)

where $C\in(0,\infty)$ is a universal constant.

Theorem 1.2 has implicitly appeared as a special case of a much more general
result concerning nonlinear spectral gaps of complex interpolation spaces [71,
Theorem 25]. This family of substantially stronger nonlinear spectral gap
inequalities can be used to prove (via Theorem 1.2) the existence of refined
average distortion embeddings of snowflakes of Banach spaces which are not
captured by Theorem 1. This task is undertaken in great detail in [71], yet
most of these results go beyond the scope of the present survey. In Section 4,
we shall present a self-contained proof of Theorem 1.2 which completely avoids
the complex interpolation machinery of [71] and is a modification of an
argument which appeared in [70, Section 5]. In Section 5, we shall present
some extensions and refinements of Theorems 1 and 1.2 and highlight some key
ideas from their proofs in [71].

###  1.3 Extrapolation

As explained above, the forthcoming proof of Theorem 1.2 does not rely on any
sophisticated analytic machinery beyond elementary spectral properties of
matrices. We will however use the following extrapolation principle for
Poincaré inequalities.

######  Proposition 1.

For every $1\leq p\leq q<\infty$ there exist $c(p,q),C(p,q)\in(0,\infty)$ such
that the following conclusion holds. For every normed space
$(X,\|\cdot\|_{X})$, every $n\in\mathbb{N}$, $\pi\in\triangle^{n-1}$ and every
$\pi$-reversible stochastic matrix $B\in M_{n}(\mathbb{R})$, we have

$c(p,q)\cdot\gamma(B,\|\cdot\|_{X}^{q})^{\frac{p}{q}}\leq\gamma(B,\|\cdot\|_{X}^{p})\leq
C(p,q)\cdot\gamma(B,\|\cdot\|_{X}^{q}).$ (10)

Proposition 1 is the vector-valued version (due to [22, 24]) of the
extrapolation principle for Poincaré inequalities [56]. In Section 3, we shall
also discuss a strengthening of Proposition 1 and its relation to a long-
standing problem in the nonlinear theory of Banach spaces.

###  1.4 Historical discussion

Motivated by a classical theorem of [85] and kickstarted by [19], the _Ribe
program_ is a vast research program in metric geometry which aims to uncover
deep structural analogies between the local theory of normed spaces and
(nonlinear) metric spaces. In the nearly four decades that lapsed since
Bourgain’s formalization of its objectives, the Ribe program has been an
extraordinary source of surprising phenomena which arise when one studies
metric spaces through the lens of Banach space theory and, vice versa, when
one considers normed spaces as objects in the metric category. Numerous such
key insights obtained in the last two decades originate in works of Naor and
his collaborators. We refer to the surveys of [45], [67, 70], [13], [15] and
[34] and to the monograph of [77] for a snapshot of some of these advances and
their applications to other areas of mathematics and theoretical computer
science.

Theorem 1 is a prime example of a result conceptually belonging in the Ribe
program for multiple reasons. Firstly, the statement of the theorem contains a
highly nonlinear operation (snowflaking) performed on a norm and the desired
embedding itself is not realized by a linear operator despite the fact that
both the source and the target space are linear. Moreover, as already
mentioned, the proof of Theorem 1 relies on the theory of nonlinear spectral
gaps, a large part of which has been developed in the context of the Ribe
program (see the discussion on expanders with respect to Banach spaces in
Section 6.3 below). Finally, as discussed in [71, Section 1.4], Naor’s initial
interest in this research direction stemmed from a question regarding the
embeddability of expanders into low-dimensional normed spaces raised by [8] in
the context of the approximate nearest neighbor search problem. A negative
answer to this question (see Theorem 6.1 below) by [69, 71] which follows
easily from Theorem 1 shall be explained in detail in Section 6.1. Theorem 6.1
also provides a new negative answer to an old question of [43] who asked
whether every $n$-point metric space admits a bi-Lipschitz embedding with
constant distortion into a $d$-dimensional normed space, where $d=O(\log n)$.
This question had previously been answered negatively by [10] for small
distortions and [55] in general. Naor’s works provide a novel and more robust
approach to this problem as they highlight a specific criterion (spectral gap)
which implies the intrinsic high-dimensionality of the metric space at hand.
Johnson and Lindenstrauss raised this question as a step towards finding a
metric version of the aforementioned classical theorem of [42]. A deep and
impactful nonlinear John theorem was discovered via a completely different
route in the influential work of [18]. Quite surprisingly, Theorem 1, which
answers negatively the question of Johnson and Lindenstrauss, is itself a
metric version of John’s theorem.

Structure of the paper. In Sections 2 and 3 we present the proofs of Theorem
1.2 and Proposition 1 respectively. In Section 4 we use Proposition 1 to prove
Theorem 1.2 which, combined with Theorem 1.2, completes the proof of Theorem
1. In Section 5 we present some refinements of Theorems 1 and 1.2 from [71]
and highlight key ideas used in their proofs. Finally, Section 6 contains a
high-level account of further geometric and algorithmic applications of the
theory of nonlinear spectral gaps.

Asymptotic notation. In what follows we use the convention that for
$a,b\in[0,\infty]$ the notation $a\gtrsim b$ (respectively $a\lesssim b$)
means that there exists a universal constant $c\in(0,\infty)$ such that $a\geq
cb$ (respectively $a\leq cb$). The notations $\lesssim_{\xi}$ and
$\gtrsim_{\chi}$ mean that the implicit constant $c$ depends on $\xi$ and
$\chi$ respectively.

Acknowledgements. I am very grateful to Florent Baudier, Manor Mendel and
Assaf Naor for helpful discussions and constructive feedback.

##  2 Duality and average distortion

In this section we present the proof of Naor’s duality Theorem 1.2. Despite
the fact that the theorem is stated for an _arbitrary_ metric space
$(\mathcal{M},d_{\mathcal{M}})$, the crux of the argument is the following
special case in which $\mathcal{M}$ is assumed to be _finite_. The general
case follows by a (standard yet lengthy) discretization and compactness
argument which can be found in [71, Section 7]. The finitary version stated
below was proven in the case that $\pi$ is the normalized counting measure in
[68, Theorem 1.3], where it is said that the argument is inspired by the proof
of [12, Lemma 1.1].

[Naor’s duality – finitary version] Suppose that $q,D\in[1,\infty)$,
$\theta\in(0,1]$, $n\in\mathbb{N}$ and fix
$\pi\in\mathrm{int}(\triangle^{n-1})$. Let
$\mathcal{M}=(\\{x_{1},\ldots,x_{n}\\},d_{\mathcal{M}})$ be a metric space and
$(Y,\|\cdot\|_{Y})$ be a Banach space such that every $\pi$-reversible
stochastic matrix $A\in M_{n}(\mathbb{R})$

$\gamma(A,d_{\mathcal{M}}^{\theta q})\leq D^{q}\gamma(A,\|\cdot\|_{Y}^{q}).$
(11)

Then, for any $\varepsilon>0$ there exists $m\in\mathbb{N}$ and a function
$f=f_{\varepsilon}:(\mathcal{M},d_{\mathcal{M}}^{\theta})\to\ell_{q}^{m}(Y)$
which is $(D+\varepsilon)$-Lipschitz satisfying the condition

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|f(x_{i})-f(x_{j})\|_{\ell_{q}^{m}(Y)}^{q}\geq\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{\theta
q}.$ (12)

######  Proof 2.1.

It clearly suffices to assume that $\theta=1$ as otherwise we can simply apply
the same result to the $\theta$-snowflake of $\mathcal{M}$. Let
$\mathcal{C}\subseteq M_{n}(\mathbb{R})$ be the class of all symmetric
$n\times n$ matrices $(c_{ij})$ for which there exist $y_{1},\ldots,y_{n}\in
Y$, not all of which are equal, with

$\forall\ i,j\in\\{1,\ldots,n\\},\qquad
c_{ij}=\frac{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q}}{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}\|y_{r}-y_{s}\|_{Y}^{q}}\cdot\|y_{i}-y_{j}\|_{Y}^{q}.$
(13)

Moreover, let $\mathcal{P}\subseteq M_{n}(\mathbb{R})$ be the class of all
symmetric $n\times n$ matrices with nonnegative entries and vanishing diagonal
and consider the convex hull
$\mathcal{Q}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{conv}(\mathcal{C}+\mathcal{P})$.

Let $T=(t_{ij})_{i,j=1}^{n}$ be the $n\times n$ matrix with entries given by
$t_{ij}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(D+\varepsilon)^{q}d_{\mathcal{M}}(x_{i},x_{j})^{q}$
for $i,j\in\\{1,\ldots,n\\}$. We shall prove that $T\in\mathcal{Q}$. Suppose
that this is not the case. Then, by the Hahn–Banach separation theorem, there
exists a nonzero symmetric $n\times n$ matrix $H=(h_{ij})_{i,j=1}^{n}$ with
vanishing diagonal such that

$\inf_{(b_{ij})_{i,j=1}^{n}\in\mathcal{Q}}\sum_{i,j=1}^{n}h_{ij}b_{ij}\geq(D+\varepsilon)^{q}\sum_{i,j=1}^{n}h_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{q}.$
(14)

Since $\mathcal{Q}$ contains a translate of $\mathcal{P}$, choosing
$(b_{ij})_{i,j=1}^{n}\in\mathcal{P}$ whose only nonzero entries are those
indexed by $(k,\ell)$ and $(\ell,k)$, where $k\neq\ell$, we deduce that
$h_{ij}\geq 0$ for every $i,j\in\\{1,\ldots,n\\}$. Moreover, as $\pi_{i}\neq
0$ for every $i\in\\{1,\ldots,n\\}$, we can define the parameter

$\sigma\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\max_{i\in\\{1,\ldots,n\\}}\frac{1}{\pi_{i}}\sum_{r\neq
i}h_{ir}\in(0,\infty)$ (15)

and consider the matrix $A=(a_{ij})_{i,j=1}^{n}$ whose entries are given by

$\forall\ i,j\in\\{1,\ldots,n\\},\qquad
a_{ij}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\cases{}{h_{ij}}{\sigma\pi_{i}},&\mbox{if
}i\neq j\\\ 1-\frac{1}{\sigma\pi_{i}}\sum_{r\neq i}h_{ir},\mbox{if }i=j.$ (16)

By construction, $A$ is a $\pi$-reversible stochastic matrix as the choice of
$\sigma$ guarantees that its entries are nonnegative. Moreover, inequality
eq:hb can be equivalently rewritten as

$\inf_{(b_{ij})_{i,j=1}^{n}\in\mathcal{Q}}\sum_{i,j=1}^{n}\pi_{i}a_{ij}b_{ij}\geq(D+\varepsilon)^{q}\sum_{i,j=1}^{n}\pi_{i}a_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{q}.$
(17)

Combining eq:in-terms-of-a with the definition eq:nsg of nonlinear spectral
gaps, we deduce that

$\inf_{(b_{ij})_{i,j=1}^{n}\in\mathcal{Q}}\sum_{i,j=1}^{n}\pi_{i}a_{ij}b_{ij}\geq\frac{(D+\varepsilon)^{q}}{\gamma(A,d_{\mathcal{M}}^{q})}\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{q}$
(18)

On the other hand, since $\mathcal{C}\subseteq\mathcal{Q}$, we have

$\begin{split}\inf_{(b_{ij})_{i,j=1}^{n}\in\mathcal{Q}}\sum_{i,j=1}^{n}\pi_{i}a_{ij}b_{ij}&\leq\inf_{(b_{ij})_{i,j=1}^{n}\in\mathcal{C}}\sum_{i,j=1}^{n}\pi_{i}a_{ij}b_{ij}\\\
&=\inf_{y_{1},\ldots,y_{n}\in
Y}\frac{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q}}{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}\|y_{r}-y_{s}\|_{Y}^{q}}\sum_{i,j=1}^{n}\pi_{i}a_{ij}\|y_{i}-y_{j}\|_{Y}^{q}\\\
&=\frac{1}{\gamma(A,\|\cdot\|_{Y}^{q})}\cdot\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q}.\end{split}$
(19)

Combining eq:du1, eq:du2 and rearranging, we deduce that
$\gamma(A,d_{\mathcal{M}}^{q})\geq(D+\varepsilon)^{q}\gamma(A,\|\cdot\|_{Y}^{q})$
which contradicts the assumption eq:dual-fin, thus proving that
$T\in\mathcal{Q}$.

Since $T\in\mathcal{Q}$ and all matrices in $\mathcal{P}$ have nonnegative
entries, we deduce that there exists $m\in\mathbb{N}$,
$(\mu_{1},\ldots,\mu_{m})\in\triangle^{m-1}$ and $n$-tuples of points
$\\{y_{1}(k),\ldots,y_{n}(k)\\}\subset Y$ not all of which are equal for each
$k\in\\{1,\ldots,m\\}$ such that

$(D+\varepsilon)^{q}d_{\mathcal{M}}(x_{i},x_{j})^{q}\geq\sum_{k=1}^{m}\underbrace{\mu_{k}\
\frac{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q}}{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}\|y_{r}(k)-y_{s}(k)\|_{Y}^{q}}}_{w_{k}}\cdot\|y_{i}(k)-y_{j}(k)\|_{Y}^{q},$
(20)

for every $i,j\in\\{1,\ldots,n\\}$. Consider the mapping
$f:\mathcal{M}\to\ell_{q}^{m}(Y)$ given by

$\forall\ i\in\\{1,\ldots,n\\},\qquad
f(x_{i})=\big{(}w_{1}^{1/q}y_{i}(1),\ldots,w_{m}^{1/q}y_{i}(m)\big{)}.$ (21)

Then, for $i,j\in\\{1,\ldots,n\\}$ we have

$\split\|f(x_{i})-f(x_{j})\|_{\ell_{q}^{m}(Y)}=\Big{(}\sum_{k=1}^{m}w_{k}\|y_{i}(k)-y_{j}(k)\|_{Y}^{q}\Big{)}^{\frac{1}{q}}\stackrel{{\scriptstyle\eqref{eq:from-Q}}}{{\leq}}(D+\varepsilon)d_{\mathcal{M}}(x_{i},x_{j}),$
(22)

which is equivalent to $\|f\|_{\mathrm{Lip}}\leq D+\varepsilon$. Finally,

$\split\sum_{i,j=1}^{n}\pi_{i}\pi_{j}&\|f(x_{i})-f(x_{j})\|_{\ell_{q}^{m}(Y)}^{q}=\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\sum_{k=1}^{n}w_{k}\|y_{i}(k)-y_{j}(k)\|_{Y}^{q}\\\
\stackrel{{\scriptstyle\eqref{eq:from-Q}}}{{=}}\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\sum_{k=1}^{m}\mu_{k}\
\frac{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q}}{\sum_{r,s=1}^{n}\pi_{r}\pi_{s}\|y_{r}(k)-y_{s}(k)\|_{Y}^{q}}\cdot\|y_{i}(k)-y_{j}(k)\|_{Y}^{q}\\\
=\sum_{r,s=1}^{n}\pi_{r}\pi_{s}d_{\mathcal{M}}(x_{r},x_{s})^{q},$ (23)

which proves the average lower bound and completes the proof.

It is worth emphasizing that Naor’s Theorem 2 is an important addition to a
long list of results in which the existence of a map with favorable metric
properties is proven using duality or by exploiting the cone structure of
$\ell_{p}$-distance matrices. We refer, for instance, to the works of [86],
[20], [47], [88] on isometric embeddings, [58] on factorization theory, [57,
Proposition 15.5.2] on bi-Lipschitz embeddings, [11], [28] on metric dimension
reduction and [12], [62] on extensions of Lipschitz mappings.

##  3 Extrapolation and snowflake embeddings

In this section we present the proof of Proposition 1. The argument relies on
some elementary properties of the vector-valued Mazur map [60]. If
$(\Omega,\mu)$ is a measure space, $(X,\|\cdot\|_{X})$ is a normed space and
$p,q\in[1,\infty)$, consider the map $\mathsf{M}_{p,q}:L_{p}(\mu;X)\to
L_{q}(\mu;X)$ whose action on $f\in L_{p}(\mu;X)$ is given by

$\forall\
\omega\in\Omega,\qquad(\mathsf{M}_{p,q}f)(\omega)=\frac{f(\omega)}{\|f(\omega)\|_{X}^{1-\frac{p}{q}}}$
(24)

when $f(\omega)\neq 0$ and $(\mathsf{M}_{p,q}f)(\omega)=0$ when $f(\omega)=0$.
We will use the following lemma.

Let $p,q\in[1,\infty)$. For any normed space $(X,\|\cdot\|_{X})$ and any
functions $f,g:\Omega\to X$ with
$\max\\{\|f\|_{L_{p}(\mu;X)},\|g\|_{L_{p}(\mu;X)}\\}\leq 1$, we have

$\big{\|}\mathsf{M}_{p,q}f-\mathsf{M}_{p,q}g\big{\|}_{L_{q}(\mu;X)}\lesssim_{p,q}\big{\|}f-g\big{\|}_{L_{p}(\mu;X)}^{\min\\{\frac{p}{q},1\\}}.$
(25)

######  Proof 3.1.

The scalar-valued case $X=\mathbb{R}$ of the proposition is classical444Since
$M_{p,q}h=|h|^{p/q}\mathrm{sign}(h)$, the scalar case is a consequence of the
pointwise inequalities
$|\mathrm{sign}(\alpha)|\alpha|^{\omega}-\mathrm{sign}(\beta)|\beta|^{\omega}|\leq
c_{1}(\omega)|\alpha-\beta|^{\omega}$ and
$|\mathrm{sign}(\alpha)|\alpha|^{\frac{1}{\omega}}-\mathrm{sign}(\beta)|\beta|^{\frac{1}{\omega}}|\leq
c_{2}(\omega)\max\\{|\alpha|,|\beta|\\}^{\frac{1}{\omega}-1}|\alpha-\beta|$
which are valid for every $\alpha,\beta\in\mathbb{R}$ and $\omega\in(0,1]$.
and can be found in [16, Section 9.1]. Consider two functions
$\theta,\phi:\Omega\to\\{x\in X:\ \|x\|_{X}=1\\}$ such that
$f=\|f\|_{X}\theta$ and $g=\|g\|_{X}\phi$. Then, we have
$\mathsf{M}_{p,q}f=\|f\|_{X}^{p/q}\theta$ and
$\mathsf{M}_{p,q}g=\|g\|_{X}^{p/q}\phi$ which imply the inequality

$\split\|\mathsf{M}_{p,q}f-\mathsf{M}_{p,q}g\|_{L_{q}(\mu;X)}&=\big{\|}\|f\|_{X}^{\frac{p}{q}}\theta-\|g\|_{X}^{\frac{p}{q}}\phi\big{\|}_{L_{q}(\mu;X)}\\\
\leq\underbrace{\big{\|}\|f\|_{X}^{\frac{p}{q}}-\|g\|_{X}^{\frac{p}{q}}\big{\|}_{L_{q}(\mu;\mathbb{R})}}_{{\tiny\leavevmode\hbox
to10.08pt{\vbox to10.08pt{\pgfpicture\makeatletter\hbox{\hskip
5.03984pt\lower-5.03984pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.83984pt}{0.0pt}\pgfsys@curveto{4.83984pt}{2.673pt}{2.673pt}{4.83984pt}{0.0pt}{4.83984pt}\pgfsys@curveto{-2.673pt}{4.83984pt}{-4.83984pt}{2.673pt}{-4.83984pt}{0.0pt}\pgfsys@curveto{-4.83984pt}{-2.673pt}{-2.673pt}{-4.83984pt}{0.0pt}{-4.83984pt}\pgfsys@curveto{2.673pt}{-4.83984pt}{4.83984pt}{-2.673pt}{4.83984pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}+\underbrace{\big{\|}\|g\|_{X}^{\frac{p}{q}}(\theta-\phi)\big{\|}_{L_{q}(\mu;X)}}_{{\tiny\leavevmode\hbox
to10.08pt{\vbox to10.08pt{\pgfpicture\makeatletter\hbox{\hskip
5.03984pt\lower-5.03984pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{4.83984pt}{0.0pt}\pgfsys@curveto{4.83984pt}{2.673pt}{2.673pt}{4.83984pt}{0.0pt}{4.83984pt}\pgfsys@curveto{-2.673pt}{4.83984pt}{-4.83984pt}{2.673pt}{-4.83984pt}{0.0pt}\pgfsys@curveto{-4.83984pt}{-2.673pt}{-2.673pt}{-4.83984pt}{0.0pt}{-4.83984pt}\pgfsys@curveto{2.673pt}{-4.83984pt}{4.83984pt}{-2.673pt}{4.83984pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-1.25pt}{-1.6111pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>(26)

By the scalar-valued version of eq:mazur applied to $\|f\|_{X}$ and
$\|g\|_{X}$, we have

$\leavevmode\hbox to14.18pt{\vbox
to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.89111pt}{0.0pt}\pgfsys@curveto{6.89111pt}{3.8059pt}{3.8059pt}{6.89111pt}{0.0pt}{6.89111pt}\pgfsys@curveto{-3.8059pt}{6.89111pt}{-6.89111pt}{3.8059pt}{-6.89111pt}{0.0pt}\pgfsys@curveto{-6.89111pt}{-3.8059pt}{-3.8059pt}{-6.89111pt}{0.0pt}{-6.89111pt}\pgfsys@curveto{3.8059pt}{-6.89111pt}{6.89111pt}{-3.8059pt}{6.89111pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\
\lesssim_{p,q}\big{\|}\|f\|_{X}-\|g\|_{X}\big{\|}_{L_{p}(\mu;\mathbb{R})}^{\min\\{\frac{p}{q},1\\}}\leq\big{\|}f-g\big{\|}_{L_{p}(\mu;X)}^{\min\\{\frac{p}{q},1\\}}.$
(27)

Moreover, if
$\mathop{}\\!\mathrm{d}\nu=\|g\|_{X}^{p}\mathop{}\\!\mathrm{d}\mu$, then
$\nu(\Omega)\leq 1$ and thus for $q\leq p$ we have

$\split\leavevmode\hbox to14.18pt{\vbox
to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.89111pt}{0.0pt}\pgfsys@curveto{6.89111pt}{3.8059pt}{3.8059pt}{6.89111pt}{0.0pt}{6.89111pt}\pgfsys@curveto{-3.8059pt}{6.89111pt}{-6.89111pt}{3.8059pt}{-6.89111pt}{0.0pt}\pgfsys@curveto{-6.89111pt}{-3.8059pt}{-3.8059pt}{-6.89111pt}{0.0pt}{-6.89111pt}\pgfsys@curveto{3.8059pt}{-6.89111pt}{6.89111pt}{-3.8059pt}{6.89111pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\
&=\|\theta-\phi\|_{L_{q}(\nu;X)}\leq\|\theta-\phi\|_{L_{p}(\nu;X)}=\big{\|}\|g\|_{X}\theta-\|g\|_{X}\phi\big{\|}_{L_{p}(\mu;X)}\\\
\leq\big{\|}\|g\|_{X}-\|f\|_{X}\big{\|}_{L_{p}(\mu;\mathbb{R})}+\big{\|}\|f\|_{X}\theta-\|g\|_{X}\phi\big{\|}_{L_{p}(\mu;X)}\leq
2\|f-g\|_{L_{p}(\mu;X)}.$ (28)

On the other hand, if $p\leq q$, Hölder’s inequality gives

$\split\leavevmode\hbox to14.18pt{\vbox
to14.18pt{\pgfpicture\makeatletter\hbox{\hskip 7.09111pt\lower-7.09111pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{6.89111pt}{0.0pt}\pgfsys@curveto{6.89111pt}{3.8059pt}{3.8059pt}{6.89111pt}{0.0pt}{6.89111pt}\pgfsys@curveto{-3.8059pt}{6.89111pt}{-6.89111pt}{3.8059pt}{-6.89111pt}{0.0pt}\pgfsys@curveto{-6.89111pt}{-3.8059pt}{-3.8059pt}{-6.89111pt}{0.0pt}{-6.89111pt}\pgfsys@curveto{3.8059pt}{-6.89111pt}{6.89111pt}{-3.8059pt}{6.89111pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{{{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}\
=\|\theta-\phi\|_{L_{q}(\nu;X)}\leq\|\theta-\phi\|_{L_{p}(\nu;X)}^{\frac{p}{q}}\cdot\|\theta-\phi\|_{L_{\infty}(\nu;X)}^{1-\frac{p}{q}}\stackrel{{\scriptstyle\eqref{eq:bound-21}}}{{\leq}}2\|f-g\|_{L_{p}(\mu;X)}^{\frac{p}{q}},$
(29)

which completes the proof of the lemma.

Equipped with the estimates of Lemma 3, we now ready to prove Proposition 1.

######  Proof 3.2 (Proof of Proposition 1).

We shall first prove the rightmost inequality of eq:extrapolation. Let
$x_{1},\ldots,x_{n}\in X$ and consider the function $f:\\{1,\ldots,n\\}\to X$
given by $f(i)=x_{i}$. Unless all the vectors $x_{1},\ldots,x_{n}$ are equal,
we can rescale so that the constraint

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|x_{i}-x_{j}\|_{X}^{p}=1$ (30)

is satisfied, which in particular, by Jensen’s inequality, implies that
$\|f-\mathbb{E}_{\pi}f\|_{L_{p}(\pi;X)}\leq 1$, where
$\mathbb{E}_{\pi}f\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sum_{i=1}^{n}\pi_{i}f(i)$.
Consider the function
$g=\mathsf{M}_{p,q}(f-\mathbb{E}_{\pi}f):\\{1,\ldots,n\\}\to X$. Then, we have

$\split
1&=\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|f(i)-f(j)\|_{X}^{p}=\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|\mathsf{M}_{q,p}g(i)-\mathsf{M}_{q,p}g(j)\|_{X}^{p}\\\
\stackrel{{\scriptstyle\eqref{eq:mazur}}}{{\lesssim}}_{p,q}\Big{(}\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|g(i)-g(j)\|_{X}^{q}\Big{)}^{\frac{p}{q}}\leq\gamma(B,\|\cdot\|_{X}^{q})^{\frac{p}{q}}\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|g(i)-g(j)\|_{X}^{q}\Big{)}^{\frac{p}{q}}\\\
=\gamma(B,\|\cdot\|_{X}^{q})^{\frac{p}{q}}\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|\mathsf{M}_{p,q}(f-\mathbb{E}_{\pi}f)(i)-\mathsf{M}_{p,q}(f-\mathbb{E}_{\pi}f)(j)\|_{X}^{q}\Big{)}^{\frac{p}{q}}\\\
\stackrel{{\scriptstyle\eqref{eq:mazur}}}{{\lesssim}}_{p,q}\\!\gamma(B,\|\cdot\|_{X}^{q})^{\frac{p}{q}}\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|f(i)-f(j)\|_{X}^{p}\Big{)}^{\frac{p}{q}}\\!\\!\\!=\gamma(B,\|\cdot\|_{X}^{q})^{\frac{p}{q}}\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|x_{i}-x_{j}\|_{X}^{p}\Big{)}^{\frac{p}{q}},$

where in both inequalities we used that
$\max\\{\|f-\mathbb{E}_{\pi}f\|_{L_{p}(\pi;X)},\|g\|_{L_{q}(\pi;X)}\\}\leq 1$.
Finally, taking an infimum of the right-hand side over all
$x_{1},\ldots,x_{n}\in X$ satisfying eq:normalize0, we deduce that
$1\lesssim_{p,q}\gamma(B,\|\cdot\|_{X}^{q})^{p/q}\gamma(B,\|\cdot\|_{X}^{p})^{-p/q}$
which concludes the proof.

The proof of the leftmost inequality is almost identical yet we repeat it for
completeness. Let $x_{1},\ldots,x_{n}\in X$ and consider the function
$\phi:\\{1,\ldots,n\\}\to X$ given by $\phi(i)=x_{i}$. Without loss of
generality, we can again assume that the constraint

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|x_{i}-x_{j}\|_{X}^{q}=1,$ (31)

is satisfied, which implies that
$\|\phi-\mathbb{E}_{\pi}\phi\|_{L_{q}(\pi;X)}\leq 1$ by Jensen’s inequality.
Consider the function
$\psi=\mathsf{M}_{q,p}(\phi-\mathbb{E}_{\pi}\phi):\\{1,\ldots,n\\}\to X$.
Then, we have

$\split
1&=\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|\phi(i)-\phi(j)\|_{X}^{q}=\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|\mathsf{M}_{p,q}\psi(i)-\mathsf{M}_{p,q}\psi(j)\|_{X}^{q}\\\
\stackrel{{\scriptstyle\eqref{eq:mazur}}}{{\lesssim}}_{p,q}\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|\psi(i)-\psi(j)\|_{X}^{p}\leq\gamma(B,\|\cdot\|_{X}^{p})\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|\psi(i)-\psi(j)\|_{X}^{p}\\\
=\gamma(B,\|\cdot\|_{X}^{p})\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|\mathsf{M}_{q,p}(\phi-\mathbb{E}_{\pi}\phi)(i)-\mathsf{M}_{q,p}(\phi-\mathbb{E}_{\pi}\phi)(j)\|_{X}^{p}\\\
\stackrel{{\scriptstyle\eqref{eq:mazur}}}{{\lesssim}}_{p,q}\gamma(B,\|\cdot\|_{X}^{p})\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|\phi(i)-\phi(j)\|_{X}^{q}\Big{)}^{\frac{p}{q}}=\gamma(B,\|\cdot\|_{X}^{p})\Big{(}\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|x_{i}-x_{j}\|_{X}^{q}\Big{)}^{\frac{p}{q}}$

where in both inequalities we used that
$\max\\{\|\phi-\mathbb{E}_{\pi}\phi\|_{L_{q}(\pi;X)},\|\psi\|_{L_{p}(\pi;X)}\\}\leq
1$. Finally, taking an infimum of the right-hand side over all
$x_{1},\ldots,x_{n}\in X$ satisfying eq:normalize, we deduce that
$1\lesssim_{p,q}\gamma(B,\|\cdot\|_{X}^{p})\gamma(B,\|\cdot\|_{X}^{q})^{-p/q}$
which concludes the proof.

Even though the vector-valued version of Matoušek’s extrapolation theorem
(Proposition 1) suffices for the proof of Theorem 1 which will be presented in
the next section, we digress to mention the following stronger result of [71].

######  Proposition 2.

Fix $p\in(0,\infty)$ and $\theta\in(0,1)$. There exists
$D_{0}=D_{0}(p,\theta)\in(1,\infty)$ such that the $\theta$-snowflake of any
normed space $(X,\|\cdot\|_{X})$ embeds with $p$-average distortion $D_{0}$
into $X$.

The discussion preceeding the statement of Theorem 1.2 shows that Proposition
1 is a formal consequence of Proposition 2, whose proof also relies on
properties of the vector-valued Mazur map eq:mazur-map. In fact, as explained
in [71, Remark 47], Proposition 2 implies improved bounds for the parameters
$c(p,q),C(p,q)$ appearing in Proposition 1. Proposition 2 is the average
distortion analogue of the following classical open problem in the nonlinear
theory of Banach spaces.

######  Question 3.3.

Does there exist $\theta\in(0,1)$ and an infinite-dimensional Banach space
$(X,\|\cdot\|_{X})$ whose $\theta$-snowflake does not admit a bi-Lipschitz
embedding into $X$?

A classical result of [86] implies that for every $\theta\in(0,1)$, the
$\theta$-snowflake of $L_{2}$ admits an isometric embedding into $L_{2}$.
Schoenberg’s theorem was later extended by [20], who showed that for every
$p\in(0,2]$ and $\theta\in(0,1)$, the $\theta$-snowflake of $L_{p}$ admits an
isometric embedding into $L_{p}$. Despite decades of attention, Question 3.3
remains stubbornly open even for the spaces $X=L_{p}$, where $p\in(2,\infty)$.
In the forthcoming work of [32], it is proven that arbitrarily small
logarithmic perturbations of this question have a negative answer. More
precisely, it is shown that for every $\theta\in(0,1)$,
$\eta\in(0,\min\\{\theta,1-\theta\\})$ and $p\in(2,\infty)$, the metric
transforms $(L_{p},\omega_{\theta,\eta}\circ d_{L_{p}})$ of $L_{p}$ do not
admit a bi-Lipschitz embedding into $L_{p}$, where

$\omega_{\theta,\eta}(t)=t^{\theta}\log^{\eta}(1+t)\qquad\mbox{or}\qquad\omega_{\theta,\eta}(t)=\frac{t^{\theta}}{1+\log^{\eta}(1+t)}.$
(32)

We refer to [27, Chapter 3] for further results in this direction.

##  4 Proof of the average John theorem

Having established the duality principle of Theorem 1.2 and the extrapolation
inequalities of Proposition 1, we are well equipped to proceed to the proof of
Theorem 1 via Theorem 1.2. We start with some preliminary properties of
_nonlinear Rayleigh quotients_ which will help us analyze nonlinear spectral
gaps. The following simplification of the original proof of Theorem 1 was
sketched in [71, Remark 31].

###  4.1 Nonlinear Rayleigh quotients

Fix $p\geq 1$, a metric space $(\mathcal{M},d_{\mathcal{M}})$ and a
probability measure $\pi\in\triangle^{n-1}$. Let $L_{p}(\pi;\mathcal{M})$ be
the metric space $(\mathcal{M}^{n},d_{L_{p}(\pi,\mathcal{M})})$ whose metric
is given by

$d_{L_{p}(\pi;\mathcal{M})}(\bm{x},\bm{y})=\Big{(}\sum_{i=1}^{n}\pi_{i}d_{\mathcal{M}}(x_{i},y_{i})^{p}\Big{)}^{\frac{1}{p}},$
(33)

where
$\bm{x}=(x_{1},\ldots,x_{n}),\bm{y}=(y_{1},\ldots,y_{n})\in\mathcal{M}^{n}$.
Moreover, we shall use the ad hoc notation $L_{p}(\pi;\mathcal{M})^{\dagger}$
for the subset $L_{p}(\pi;M)\setminus\\{(x,\ldots,x):\ x\in\mathcal{M}\\}$ of
$L_{p}(\pi;\mathcal{M})$.

Let $A\in M_{n}(\mathbb{R})$ be a row-stochastic matrix that is
$\pi$-stationary (in the sense that $\pi A=\pi$) and
$\bm{x}=(x_{1},\ldots,x_{n})\in L_{p}(\pi;\mathcal{M})^{\dagger}$. Following
[70, Section 5.1], we consider the corresponding nonlinear Rayleigh quotient
given by

$\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p})\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\frac{\sum_{i,j=1}^{n}\pi_{i}a_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{p}}{\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},x_{j})^{p}}.$
(34)

By definition, if $A$ is $\pi$-reversible, the nonlinear spectral gap eq:nsg
satisfies

$\gamma(A,d_{\mathcal{M}}^{p})=\sup_{\bm{x}\in
L_{p}(\pi;\mathcal{M})^{\dagger}}\frac{1}{\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p})}.$
(35)

We will need the following properties of nonlinear Rayleigh quotients.

Let $(\mathcal{M},d_{\mathcal{M}})$ be a metric space, $p\geq 1$,
$\lambda\in[0,1]$ and $\pi\in\triangle^{n-1}$. If $A,B\in M_{n}(\mathbb{R})$
are $\pi$-stationary stochastic matrices and $\bm{x}\in
L_{p}(\pi;\mathcal{M})^{\dagger}$, then we have

  1. (i)

$\mathcal{R}(\bm{x};\lambda
A+(1-\lambda)B,d_{\mathcal{M}}^{p})=\lambda\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p})+(1-\lambda)\mathcal{R}(\bm{x};B,d_{\mathcal{M}}^{p})$.

  2. (ii)

$\mathcal{R}(\bm{x};\lambda
A+(1-\lambda)\mathsf{Id}_{n},d_{\mathcal{M}}^{p})=\lambda\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p})$,
where $\mathsf{Id}_{n}$ is the identity matrix.

  3. (iii)

$\mathcal{R}(\bm{x};AB,d_{\mathcal{M}}^{p})^{\frac{1}{p}}\leq\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p})^{\frac{1}{p}}+\mathcal{R}(\bm{x};B,d_{\mathcal{M}}^{p})^{\frac{1}{p}}$.

  4. (iv)

$\mathcal{R}(\bm{x};B^{t},d_{\mathcal{M}}^{p})\leq
t^{p}\mathcal{R}(\bm{x};B,d_{\mathcal{M}}^{p})$ for every $t\in\mathbb{N}$.

######  Proof 4.1.

The first property is evident from the definition eq:nrq and the second
follows from (i) since
$\mathcal{R}(\bm{x};\mathsf{Id}_{n},d_{\mathcal{M}}^{p})=0$. Moreover, (iv)
follows by iterating (iii) so we are left to prove that. Notice that $AB$ is
$\pi$-stationary and the triangle inequality gives

$\split\Big{(}\sum_{i,j=1}^{n}&\pi_{i}(AB)_{ij}d_{\mathcal{M}}(x_{i},x_{j})^{p}\Big{)}^{\frac{1}{p}}\leq\Big{(}\sum_{i,j=1}^{n}\pi_{i}\sum_{k=1}^{n}a_{ik}b_{kj}\big{(}d_{\mathcal{M}}(x_{i},x_{k})+d_{\mathcal{M}}(x_{k},x_{j})\big{)}^{p}\Big{)}^{\frac{1}{p}}\\\
\leq\Big{(}\sum_{i,j,k=1}^{n}\pi_{i}a_{ik}b_{kj}d_{\mathcal{M}}(x_{i},x_{k})^{p}\Big{)}^{\frac{1}{p}}+\Big{(}\sum_{i,j,k=1}^{n}\pi_{i}a_{ik}b_{kj}d_{\mathcal{M}}(x_{k},x_{j})^{p}\Big{)}^{\frac{1}{p}}\\\
=\Big{(}\sum_{i,k=1}^{n}\pi_{i}a_{ik}d_{\mathcal{M}}(x_{i},x_{k})^{p}\Big{)}^{\frac{1}{p}}+\Big{(}\sum_{k,j=1}^{n}\pi_{k}b_{kj}d_{\mathcal{M}}(x_{k},x_{j})^{p}\Big{)}^{\frac{1}{p}},$
(36)

where in the last equality we used the stationarity of $A$ in the form
$\pi_{k}=\sum_{i=1}^{n}\pi_{i}a_{ik}$. The desired inequality (iii) follows
from eq:iii after renormalizing.

Apart from the elementary properties of Lemma 4.1, we shall also need the
following standard computation of nonlinear Rayleigh quotients in Hilbert
space. Recall that for every normed space $(X,\|\cdot\|_{X})$, every matrix
$B\in M_{n}(\mathbb{R})$ induces a linear operator
$B\otimes\mathsf{Id}_{X}:L_{p}(\pi;X)\to L_{p}(\pi;X)$ that is given by
$(B\otimes\mathsf{Id}_{X})(x_{1},\ldots,x_{n})=(\sum_{j=1}^{n}b_{ij}x_{j})_{i=1}^{n}$.

Fix $\pi\in\triangle^{n-1}$ and let $B\in M_{n}(\mathbb{R})$ be a
$\pi$-reversible stochastic matrix. For every Hilbert space
$(\mathcal{H},\|\cdot\|_{\mathcal{H}})$ and $\bm{x}\in
L_{2}(\pi;\mathcal{H})^{\dagger}$ with $\sum_{i=1}^{n}\pi_{i}x_{i}=0$, we have

$\mathcal{R}(\bm{x};B^{2},\|\cdot\|_{\mathcal{H}}^{2})=1-\frac{\|(B\otimes\mathsf{Id}_{\mathcal{H}})\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2}}{\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2}}.$
(37)

######  Proof 4.2.

Let $\langle\cdot,\cdot\rangle_{\mathcal{H}}$ be the inner product of
$\mathcal{H}$ and notice that

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|x_{i}-x_{j}\|_{\mathcal{H}}^{2}=2\sum_{i=1}^{n}\pi_{i}\|x_{i}\|_{\mathcal{H}}^{2}-2\left\langle\sum_{i=1}^{n}\pi_{i}x_{i},\sum_{j=1}^{n}\pi_{j}x_{j}\right\rangle_{\mathcal{H}}=2\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2},$
(38)

since $\sum_{i=1}^{n}\pi_{i}x_{i}=0$. Moreover, since $B^{2}$ is
$\pi$-stationary and stochastic, we have

$\split&\sum_{i,j=1}^{n}\pi_{i}(B^{2})_{ij}\|x_{i}-x_{j}\|_{\mathcal{H}}^{2}=\sum_{i,j=1}^{n}\pi_{i}(B^{2})_{ij}(\|x_{i}\|_{\mathcal{H}}^{2}+\|x_{j}\|_{\mathcal{H}}^{2})-2\sum_{i=1}^{n}\pi_{i}\left\langle
x_{i},\sum_{j=1}^{n}(B^{2})_{ij}x_{j}\right\rangle_{\mathcal{H}}\\\
=2\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2}-2\sum_{i=1}^{n}\pi_{i}\big{\langle}x_{i},\big{(}(B^{2}\otimes\mathsf{Id}_{\mathcal{H}})\bm{x}\big{)}_{i}\big{\rangle}_{\mathcal{H}}=2\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2}-2\|(B\otimes\mathsf{Id}_{\mathcal{H}})\bm{x}\|_{L_{2}(\pi;\mathcal{H})}^{2},$

where in the last equality we additionally used the $\pi$-reversibility of
$B$. The conclusion now readily follows by the definition eq:nrq of nonlinear
Rayleigh quotients.

###  4.2 Proof of Theorem 1.2

In the proof of Theorem 1.2 we will use the following pointwise estimate of
nonlinear Rayleigh quotients of normed spaces which are isomorphic to a
Hilbert space.

Let $(X,\|\cdot\|_{X})$ be a normed space and $D\in[1,\infty)$. Suppose that
there exists a Hilbertian norm $\|\cdot\|_{\mathcal{H}}:X\to\mathbb{R}_{+}$
such that

$\forall\ y\in X,\qquad\|y\|_{\mathcal{H}}\leq\|y\|_{X}\leq
D\|y\|_{\mathcal{H}}.$ (39)

Then, for every $\pi\in\triangle^{n-1}$ and every $\pi$-reversible stochastic
matrix $B\in M_{n}(\mathbb{R})$,

$\mathcal{R}(\bm{x};B^{2},\|\cdot\|_{\mathcal{H}}^{2})\geq
1-\eta^{2}\quad\Longrightarrow\quad\mathcal{R}(\bm{x};B,\|\cdot\|_{X}^{2})\geq\frac{(1-\eta
D)^{2}}{4},$ (40)

where $\bm{x}\in L_{2}(\pi;X)^{\dagger}$ and $\eta\in(0,1/D)$.

######  Proof 4.3.

Without loss of generality, we can translate the components $x_{i}$ of the
vector $\bm{x}\in L_{2}(\pi;X)^{\dagger}$ to assume that
$\sum_{i=1}^{n}\pi_{i}x_{i}=0$. Then, the assumption
$\mathcal{R}(\bm{x};B^{2},\|\cdot\|_{\mathcal{H}}^{2})\geq 1-\eta^{2}$ can be
equivalently rewritten due to Lemma 4.1 as

$\|(B\otimes\mathsf{Id}_{\mathcal{H}})\bm{x}\|_{L_{2}(\pi;\mathcal{H})}\leq\eta\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}.$
(41)

Therefore,

$\|(B\otimes\mathsf{Id}_{X})\bm{x}\|_{L_{2}(\pi;X)}\stackrel{{\scriptstyle\eqref{eq:isomorph}}}{{\leq}}D\|(B\otimes\mathsf{Id}_{\mathcal{H}})\bm{x}\|_{L_{2}(\pi;\mathcal{H})}\stackrel{{\scriptstyle\eqref{eq:uselema}}}{{\leq}}\eta
D\|\bm{x}\|_{L_{2}(\pi;\mathcal{H})}\stackrel{{\scriptstyle\eqref{eq:isomorph}}}{{\leq}}\eta
D\|\bm{x}\|_{L_{2}(\pi;X)},$ (42)

and thus, by the triangle inequality,

$\|\bm{x}-(B\otimes\mathsf{Id}_{X})\bm{x}\|_{L_{2}(\pi;X)}\geq\|\bm{x}\|_{L_{2}(\pi;X)}-\|(B\otimes\mathsf{Id}_{X})\bm{x}\|_{L_{2}(\pi;X)}\stackrel{{\scriptstyle\eqref{useisom}}}{{\geq}}(1-\eta
D)\|\bm{x}\|_{L_{2}(\pi;X)}.$ (43)

Since $B$ is row-stochastic, Jensen’s inequality for the convex function
$\|\cdot\|_{X}^{2}$ gives

$\sum_{i,j=1}^{n}\pi_{i}b_{ij}\|x_{i}-x_{j}\|_{X}^{2}\geq\sum_{i=1}^{n}\pi_{i}\Big{\|}x_{i}-\sum_{j=1}^{n}b_{ij}x_{j}\Big{\|}_{X}^{2}=\|\bm{x}-(B\otimes\mathsf{Id}_{X})\bm{x}\|_{L_{2}(\pi;X)}^{2}.$
(44)

On the other hand, using the triangle inequality we get

$\sum_{i,j=1}^{n}\pi_{i}\pi_{j}\|x_{i}-x_{j}\|_{X}^{2}\leq\sum_{i,j=1}^{n}\pi_{i}\pi_{j}(\|x_{i}\|_{X}+\|x_{j}\|_{X})^{2}\leq
4\|\bm{x}\|_{L_{2}(\pi;X)}^{2}.$ (45)

Combining eq:nrq, eq:22, eq:11 and eq:33 we deduce that

$\mathcal{R}(\bm{x};B,\|\cdot\|_{X}^{2})\geq\frac{(1-\eta D)^{2}}{4},$ (46)

which concludes the proof.

Equipped with Lemma 4.2, we can complete the proof of Theorem 1.2. The main
idea is to consider a Hilbertian norm which nicely approximates our given norm
on $\mathbb{R}^{d}$ and then use the implication eq:iso-impli. In order to
ensure that the assumption of eq:iso-impli is satisfied we shall apply a trick
that was used by [82], who attributed it to V. Lafforgue: we will replace $A$
by a large enough power of the form
$\big{(}\tfrac{A+\mathsf{Id}_{n}}{2}\big{)}^{t}$. We will then be able to
return to an inequality involving $A$ rather than its power using Lemma 4.1.

######  Proof 4.4 (Proof of Theorem 1.2).

Suppose that $X=(\mathbb{R}^{d},\|\cdot\|_{X})$ and fix
$\pi\in\triangle^{n-1}$, a $\pi$-reversible stochastic matrix $A\in
M_{n}(\mathbb{R})$ and a vector $\bm{x}\in L_{1}(\pi;X)^{\dagger}$. In view of
eq:nrq-sg, we need to prove a lower bound on
$\mathcal{R}(\bm{x};A,\|\cdot\|_{X})$. Notice that, by properties (ii) and
(iv) of Lemma 4.1, we have the inequality

$\mathcal{R}(\bm{x};A,\|\cdot\|_{X})=2\mathcal{R}\Big{(}\bm{x};\frac{A+\mathsf{Id}_{n}}{2},\|\cdot\|_{X}\Big{)}\geq\frac{2}{t}\mathcal{R}\Big{(}\bm{x};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}\Big{)}$
(47)

for every $t\in\mathbb{N}$. Moreover, by the vector-valued extrapolation
inequalities of Proposition 1 and the expression eq:nrq-sg of nonlinear
spectral gaps in terms of nonlinear Rayleigh quotients, we conclude that there
exists a point $\bm{y}\in L_{2}(\pi;X)^{\dagger}$ satisfying

$\mathcal{R}\Big{(}\bm{x};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}\Big{)}\gtrsim\mathcal{R}\Big{(}\bm{y};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}^{2}\Big{)}.$
(48)

Let $D_{X}\in[1,\infty)$ be the least constant for which there exists a
Hilbertian norm $\|\cdot\|_{\mathcal{H}}:\mathbb{R}^{d}\to\mathbb{R}_{+}$ such
that the following inequality is satisfied,

$\forall\ y\in\mathbb{R}^{d},\qquad\|y\|_{\mathcal{H}}\leq\|y\|_{X}\leq
D_{X}\|y\|_{\mathcal{H}}.$ (49)

As $\mathcal{H}$ is isometric to $\ell_{2}^{d}$, the spectral gap of
$\big{(}\tfrac{A+\mathsf{Id}_{n}}{2}\big{)}^{2t}$ with respect to
$\|\cdot\|^{2}_{\mathcal{H}}$ satisfies

$\gamma\Big{(}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{2t},\|\cdot\|_{\mathcal{H}}^{2}\Big{)}=\gamma\Big{(}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{2t},|\cdot|^{2}\Big{)}=\frac{1}{1-\big{(}\frac{1+\lambda_{2}(A)}{2}\big{)}^{2t}}.$
(50)

Therefore, for the parameter

$t^{\ast}(A)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\left\lceil\frac{\log(2D_{X})}{\log(\frac{2}{1+\lambda_{2}(A)})}\right\rceil\lesssim\frac{\log(D_{X}+1)}{1-\lambda_{2}(A)}$
(51)

we have the estimate

$\gamma\Big{(}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{2t^{*}(A)},\|\cdot\|_{\mathcal{H}}^{2}\Big{)}\stackrel{{\scriptstyle\eqref{eq:eucl-
gamma}\wedge\eqref{eq:power}}}{{\leq}}\frac{1}{1-\frac{1}{4D_{X}^{2}}},$ (52)

which combined with eq:nrq-sg immediately implies that

$\mathcal{R}\Big{(}\bm{y};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{2t^{*}(A)},\|\cdot\|_{\mathcal{H}}^{2}\Big{)}\geq
1-\frac{1}{4D_{X}^{2}}.$ (53)

Therefore, in view of eq:hilbe-norm and eq:got-hilbert-bound, the pointwise
estimate of Lemma 4.2 applied to the matrix
$B=\big{(}\tfrac{A+\mathsf{Id}_{n}}{2}\big{)}^{t^{*}(A)}$ and
$\eta=\tfrac{1}{2D_{X}}$ implies that

$\mathcal{R}\Big{(}\bm{y};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t^{*}(A)},\|\cdot\|_{X}^{2}\Big{)}\geq\frac{1}{16}.$
(54)

Finally, combining eq:take-power, eq:use-extra and eq:got-X-bound for
$t=t^{\ast}(A)$ we deduce that

$\mathcal{R}(\bm{x};A,\|\cdot\|_{X})\gtrsim\frac{1}{t^{*}(A)}\stackrel{{\scriptstyle\eqref{eq:power}}}{{\gtrsim}}\frac{1-\lambda_{2}(A)}{\log(D_{X}+1)}.$
(55)

By John’s theorem [42], since $X$ is $d$-dimensional we have
$D_{X}\leq\sqrt{d}$ and the desired estimate eq:estimate thus follows by
rearranging eq:almost-done and using eq:nrq-sg.

As explained in the introduction, Theorem 1 is equivalent to Theorem 1.2 via
the duality principle of Theorem 1.2.

######  Proof 4.5 (Proof of Theorem 1).

Combining Theorems 1.2 and 1.2, we deduce that the $\tfrac{1}{2}$-snowflake of
any $d$-dimensional normed space embeds into an ultrapower of $\ell_{2}$ with
quadratic average distortion at most $C\sqrt{\log d}$, where $d\geq 2$ and
$C\in(0,\infty)$ is a universal constant. This immediately yields the
conclusion of Theorem 1 since any ultrapower of $\ell_{2}$ is itself a Hilbert
space [39].

##  5 Beyond Hilbertian embeddings

Theorem 1 is a special case of a much more general embedding theorem proven by
[71]. As a matter of fact, a lot of the ideas required to prove this more
general statement have already been used in the Hilbertian case. A key
ingredient required to go beyond Theorem 1 is the notion of _Markov type_
introduced by [12].

A metric space $(\mathcal{M},d_{\mathcal{M}})$ has Markov type
$p\in(0,\infty)$ with constant $M\in(0,\infty)$ if for every $n\in\mathbb{N}$,
$\pi\in\triangle^{n-1}$, every $\pi$-reversible matrix $A\in
M_{n}(\mathbb{R})$ and every $\bm{x}\in L_{p}(\pi;\mathcal{M})$, we have

$\forall\
t\in\mathbb{N},\qquad\mathcal{R}(\bm{x};A^{t},d_{\mathcal{M}}^{p})\leq M^{p}t\
\mathcal{R}(\bm{x};A,d_{\mathcal{M}}^{p}).$ (56)

The least such constant $M\in(0,\infty)$ will be denoted by
$\mathsf{M}_{p}(\mathcal{M})$.

In [12], it was shown that any Hilbert space $\mathcal{H}$ has
$\mathsf{M}_{2}(\mathcal{H})=1$. Following [14], we say that a normed space
$(X,\|\cdot\|_{X})$ is $p$-uniformly smooth, where $p\in[1,2]$, if there
exists a constant $S\in(0,\infty)$ such that

$\forall\ x,y\in
X,\qquad\frac{\|x\|_{X}^{p}+\|y\|_{X}^{p}}{2}\leq\Big{\|}\frac{x+y}{2}\Big{\|}_{X}^{p}+S^{p}\Big{\|}\frac{x-y}{2}\Big{\|}_{X}^{p}.$
(57)

The least such constant $S\in(0,\infty)$ will be denoted by
$\mathsf{S}_{p}(X)$. A deep theorem of [72] asserts that every $p$-uniformly
smooth normed space $(X,\|\cdot\|_{X})$ has Markov type $p$ with constant

$\mathsf{M}_{p}(X)\lesssim\mathsf{S}_{p}(X).$ (58)

An inspection of the proof of Theorem 1.2 reveals that the power of the norm
in the estimate eq:estimate can be improved for spaces of Markov type
$p\in(1,2]$. Indeed, replacing eq:take-power with eq:mtype and using the
extrapolation inequality eq:extrapolation, we deduce that for every $\bm{x}\in
L_{p}(\pi;X)^{\dagger}$ there exists $\bm{y}\in L_{2}(\pi;X)^{\dagger}$ for
which we have the estimate

$\split\mathcal{R}(\bm{x};A,&\|\cdot\|_{X}^{p})=2\mathcal{R}\Big{(}\bm{x};\frac{A+\mathsf{Id}_{n}}{2},\|\cdot\|_{X}^{p}\Big{)}\\\
\stackrel{{\scriptstyle\eqref{eq:mtype}}}{{\gtrsim}}_{{}_{\mathsf{M}_{p}(X)}}\frac{1}{t}\mathcal{R}\Big{(}\bm{x};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}^{p}\Big{)}\stackrel{{\scriptstyle\eqref{eq:extrapolation}}}{{\gtrsim}}\frac{1}{t}\mathcal{R}\Big{(}\bm{y};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}^{2}\Big{)}.$
(59)

Then, repeating the rest of the proof mutatis mutandis, we deduce the bound

$\gamma(A,\|\cdot\|_{X}^{p})\lesssim_{{}_{\mathsf{M}_{p}(X)}}\frac{\log(\mathrm{dim}(X)+1)}{1-\lambda_{2}(A)},$
(60)

which, in view of eq:npss and Theorem 1.2, implies the following embeddability
result.

For every $S\in(0,\infty)$, there exists $C(S)\in(0,\infty)$ such that the
following holds. If $p\in[1,2]$ and $(X,\|\cdot\|_{X})$ is a finite-
dimensional normed space with $\mathsf{S}_{p}(X)\leq S$, then the
$\tfrac{p}{2}$-snowflake of $(X,\|\cdot\|_{X})$ admits an embedding into
$\ell_{2}$ with quadratic average distortion at most
$C(S)\sqrt{\log(\mathrm{dim}(X)+1)}$.

Theorem 1 is a special case of Theorem 5 as $\mathsf{S}_{1}(X)=1$ for any
$(X,\|\cdot\|_{X})$. However, Theorem 5 is a refinement of the average John
theorem in that it captures the fact that more structured normed spaces (i.e.
spaces with bounded $p$-uniform smoothness constant) require a lesser amount
of snowflaking in order to be embedded into $\ell_{2}$ with quadratic average
distortion which depends subpolynomially on the dimension. It is worth
emphasizing that for 2-uniformly smooth spaces (such as $L_{r}(\mu)$ with
$2<r<\infty$), Theorem 5 shows that _no_ snowflaking is necessary for such an
embedding to exist.

This approach can be further exploited even for target spaces which are not
Hilbertian. Following [14], we say that a normed space $(X,\|\cdot\|_{X})$ is
$q$-uniformly convex, where $q\in[2,\infty)$, if there exists a constant
$K\in(0,\infty)$ such that

$\forall\ x,y\in
X,\qquad\Big{\|}\frac{x+y}{2}\Big{\|}_{X}^{q}+\frac{1}{K^{q}}\Big{\|}\frac{x-y}{2}\Big{\|}_{X}^{q}\leq\frac{\|x\|_{X}^{q}+\|y\|_{X}^{q}}{2}.$
(61)

The least such constant $K\in(0,\infty)$ will be denoted by
$\mathsf{K}_{q}(X)$. Observe that $\mathsf{K}_{2}(\ell_{2})=1$. Theorem 5
admits the following non-Hilbertian generalization. We shall denote by
$\mathsf{c}_{Y}(\mathcal{M})$ the infimal distortion of a bi-Lipschitz
embedding $f:(\mathcal{M},d_{\mathcal{M}})\to(Y,\|\cdot\|_{Y})$.

For every $S,K\in(0,\infty)$, there exists $C(S,K)\in(0,\infty)$ such that the
following holds. If $1\leq p\leq 2\leq q<\infty$, $(X,\|\cdot\|_{X})$ is a
Banach space with $\mathsf{S}_{p}(X)\leq S$ and $(Y,\|\cdot\|_{Y})$ is a
Banach space with $\mathsf{K}_{q}(Y)\leq K$, then the $\frac{p}{q}$-snowflake
of $X$ admits an embedding into $\ell_{q}(Y)$ with $q$-average distortion at
most $C(S,K)(\log(\mathsf{c}_{Y}(X)+1))^{1/q}$.

In view of the duality principle555Observe that a direct application of
Theorem 1.2 and eq:p/q would imply that the $\tfrac{p}{q}$-snowflake of $X$
admits such an embedding into an ultrapower of $\ell_{q}(Y)$ rather than
$\ell_{q}(Y)$ itself. Taking an ultrapower in this statement is redundant if
$X$ is assumed to be $p$-uniformly smooth and $Y$ is $q$-uniformly convex, as
was shown in [71, Corollary 23]. We shall not address this delicate issue
here. of Theorem 1.2, Theorem 5 is equivalent the following nonlinear spectral
gap inequality. For every $n\in\mathbb{N}$, $\pi\in\triangle^{n-1}$ and every
$\pi$-reversible matrix $A\in M_{n}(\mathbb{R})$, we have

$\gamma(A,\|\cdot\|_{X}^{p})\lesssim_{{}_{\mathsf{M}_{p}(X),\mathsf{K}_{q}(Y)},p,q}\log(\mathsf{c}_{Y}(X)+1)\gamma(A,\|\cdot\|_{Y}^{q}).$
(62)

Fix $\bm{x}\in L_{p}(\pi;X)^{\dagger}$ with $\sum_{i=1}^{n}\pi_{i}x_{i}=0$.
Using Markov type and extrapolation as in eq:use-mtype, we deduce that for any
$t\in\mathbb{N}$, there exists $\bm{y}\in L_{q}(\pi;X)^{\dagger}$ with
$\sum_{i=1}^{n}\pi_{i}y_{i}=0$ such that

$\mathcal{R}(\bm{x};A,\|\cdot\|_{X}^{p})\gtrsim_{{}_{\mathsf{M}_{p}(X)},p,q}\frac{1}{t}\mathcal{R}\Big{(}\bm{y};\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t},\|\cdot\|_{X}^{q}\Big{)}.$
(63)

Moreover, if
$B_{t}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}(\tfrac{A+\mathsf{Id}_{n}}{2})^{t}$,
the argument of eq:22 and eq:33 implies that

$\split\mathcal{R}(\bm{y};B_{t},\|\cdot\|_{X}^{q})\gtrsim_{q}&\frac{\|\bm{y}-(B_{t}\otimes\mathsf{Id}_{X})\bm{y}\|_{L_{q}(\pi;X)}^{q}}{\|\bm{y}\|^{q}_{L_{q}(\pi;X)}}\\\
\geq\big{(}1-\|B_{t}\otimes\mathsf{Id}_{X}\|_{L_{q}^{{}^{0}}(\pi;X)\to
L_{q}^{{}^{0}}(\pi;X)}\big{)}^{q},$ (64)

where $L_{q}^{{}^{0}}(\pi;Z)=\\{\bm{z}\in L_{q}(\pi;Z):\
\sum_{i=1}^{n}\pi_{i}z_{i}=0\\}$. Therefore, we have

$\gamma(A,\|\cdot\|_{X}^{p})\stackrel{{\scriptstyle\eqref{eq:222}\wedge\eqref{eq:nrq-
sg}\wedge\eqref{eq:333}}}{{\lesssim_{{}_{\mathsf{M}_{p}(X)},p,q}}}\frac{t}{(1-\|B_{t}\otimes\mathsf{Id}_{X}\|_{L_{q}^{{}^{0}}(\pi;X)\to
L_{q}^{{}^{0}}(\pi;X)})^{q}}.$ (65)

Notice that by the definition of $\mathsf{c}_{Y}(X)$,

$\|B_{t}\otimes\mathsf{Id}_{X}\|_{L_{q}^{{}^{0}}(\pi;X)\to
L_{q}^{{}^{0}}(\pi;X)}\leq\mathsf{c}_{Y}(X)\|B_{t}\otimes\mathsf{Id}_{Y}\|_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}$ (66)

and moreover

$\split\|B_{t}\otimes\mathsf{Id}_{Y}\|_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}=\Big{\|}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}^{t}&\otimes\mathsf{Id}_{Y}\Big{\|}_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}\\\
\leq\Big{\|}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}\otimes\mathsf{Id}_{Y}\Big{\|}_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}^{t}.$ (67)

Combining eq:41, eq:42 and eq:43, we finally deduce that for any
$t\in\mathbb{N}$,

$\gamma(A,\|\cdot\|_{X}^{p})\lesssim_{{}_{\mathsf{M}_{p}(X)},p,q}t\cdot\Big{(}1-\mathsf{c}_{Y}(X)\Big{\|}\Big{(}\frac{A+\mathsf{Id}_{n}}{2}\Big{)}\otimes\mathsf{Id}_{Y}\Big{\|}_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}^{t}\Big{)}^{-q}.$ (68)

Optimizing over $t$ we thus conclude that

$\gamma(A,\|\cdot\|_{X}^{p})\lesssim_{{}_{\mathsf{M}_{p}(X)},p,q}\frac{\log(\mathsf{c}_{Y}(X)+1)}{\log\big{(}1/\|(\frac{A+\mathsf{Id}_{n}}{2})\otimes\mathsf{Id}_{Y}\|_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}\big{)}}$ (69)

Observe that so far we have been very closely following the Hilbertian proof.
Indeed, if $Y$ is a Hilbert space and $q=2$, then the operator norm appearing
in eq:66 is simply $\tfrac{1+\lambda_{2}(A)}{2}$ and thus eq:estimate follows
from eq:66 and John’s theorem which asserts that
$\mathsf{c}_{\ell_{2}}(X)\leq\sqrt{\mathrm{dim}X}$. In the general (Banach
space-valued) setting of Theorem 5, we need a more robust argument to show
that the operator norm
$\big{\|}(\tfrac{A+\mathsf{Id}_{n}}{2})\otimes\mathsf{Id}_{Y}\big{\|}_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}$ is bounded away from 1 by a quantity which depends on
the nonlinear spectral gap $\gamma(A,\|\cdot\|_{Y}^{q})$. To do this, we will
leverage the $q$-uniform convexity of the normed space $(Y,\|\cdot\|_{Y})$.

Fix a metric space $(\mathcal{M},d_{\mathcal{M}})$ and $q\in(0,\infty)$. If
$\pi\in\triangle^{n-1}$ and $A\in M_{n}(\mathbb{R})$ is a $\pi$-reversible
stochastic matrix, the _nonlinear absolute spectral gap_ of $A$ with respect
to $d_{\mathcal{M}}^{q}$, denoted by $\gamma_{+}(A,d_{\mathcal{M}}^{q})$, is
the least constant $\gamma_{+}\in(0,\infty]$ such that

$\forall\
x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}\in\mathcal{M},\qquad\sum_{i,j=1}^{n}\pi_{i}\pi_{j}d_{\mathcal{M}}(x_{i},y_{j})^{q}\leq\gamma_{+}\sum_{i,j=1}^{n}\pi_{i}a_{ij}d_{\mathcal{M}}(x_{i},y_{j})^{q}.$
(70)

The terminology stems from the fact that
$\gamma_{+}(A,|\cdot|^{2})=(1-\max_{i=2,\ldots,n}|\lambda_{i}(A)|)^{-1}$,
where $1=\lambda_{1}(A)\geq\lambda_{2}(A)\geq\cdots\geq\lambda_{n}(A)\geq-1$
are the eigenvalues of $A$. Nonlinear spectral gaps and nonlinear absolute
spectral gaps are related via the following inequalities.

Fix $q\in[1,\infty)$, $n\in\mathbb{N}$ and $\pi\in\triangle^{n-1}$. For every
$\pi$-reversible stochastic matrix $A\in M_{n}(\mathbb{R})$ and every metric
space $(\mathcal{M},d_{\mathcal{M}})$, we have

$2\gamma(A,d_{\mathcal{M}}^{q})\leq\gamma_{+}\Big{(}\frac{A+\mathsf{Id}_{n}}{2},d_{\mathcal{M}}^{q}\Big{)}\leq
2^{2q+1}\gamma(A,d_{\mathcal{M}}^{q}).$ (71)

The elementary proof of Lemma 5 can be found in [68, Lemma 2.3]. The
pertinence of absolute spectral gaps in the ensuing discussion is that, in the
case of uniformly convex spaces, they have a useful connection to vector-
valued operator norms of adjacency matrices. This is manifested by the
following proposition of [63, Lemma 6.6], whose proof relies on Pisier’s
martingale cotype inequality for $q$-uniformly convex spaces [80].

######  Proposition 3.

Fix $q\in[2,\infty)$ and let $(Y,\|\cdot\|_{Y})$ be a $q$-uniformly convex
normed space. Then, for every $n\in\mathbb{N}$, $\pi\in\triangle^{n-1}$ and
every $\pi$-reversible stochastic matrix $C\in M_{n}(\mathbb{R})$, we have

$\|C\otimes\mathsf{Id}_{Y}\|_{L_{q}^{{}^{0}}(\pi;Y)\to
L_{q}^{{}^{0}}(\pi;Y)}\leq\Big{(}1-\frac{1}{(2^{q-1}-1)\mathsf{K}_{q}(Y)^{q}\gamma_{+}(C,\|\cdot\|_{Y}^{q})}\Big{)}^{\frac{1}{q}}.$
(72)

Proposition 3 is proven by [63] for the special case that $\pi$ is the uniform
measure on $\\{1,\ldots,n\\}$ and $C$ is a symmetric stochastic matrix. The
proof of the general statement presented here is similar to this special case
and we thus omit it. Plugging the bound eq:bound|| in eq:66 for
$C=\frac{A+\mathsf{Id}_{n}}{2}$, we finally deduce that

$\split\gamma(A,\|\cdot\|_{X}^{p})\stackrel{{\scriptstyle\eqref{eq:66}\wedge\eqref{eq:bound||}}}{{\lesssim}}_{{}_{\\!\\!\\!\\!\\!\\!\\!\mathsf{M}_{p}(X),\mathsf{K}_{q}(Y)},p,q}\log(\mathsf{c}_{Y}(X)&+1)\gamma_{+}\Big{(}\frac{A+\mathsf{Id}_{n}}{2},\|\cdot\|_{Y}^{q}\Big{)}\\\
\stackrel{{\scriptstyle\eqref{eq:abs}}}{{\lesssim_{q}}}\log(\mathsf{c}_{Y}(X)+1)\gamma(A,\|\cdot\|_{Y}^{q}).\
\hskip 30.35657pt\Box$ (73)

##  6 Geometric and algorithmic applications

In this final section, we present a selection of geometric and algorithmic
applications of nonlinear spectral gaps (mostly without proofs) and related
open questions.

###  6.1 Nonembeddability of expanders into low-dimensional normed spaces

Let $G=(V,E)$ be a $d$-regular graph on the vertex set $\\{1,\ldots,n\\}$. We
shall denote by $A_{G}$ the normalized adjacency matrix of $G$, that is, the
$n\times n$ symmetric stochastic matrix whose entries are given by
$(A_{G})_{ij}=\frac{{\bf 1}_{\\{i,j\\}\in E}}{d}$, where
$i,j\in\\{1,\ldots,n\\}$. A sequence
$\\{G_{n}=(V_{n},E_{n})\\}_{n=1}^{\infty}$ of $d$-regular graphs with
$|V_{n}|\to\infty$ as $n\to\infty$ is called an expander graph sequence if
$\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}})<\infty$. The existence of regular
expander graph sequences is a classical fact that can be proven via the
probabilistic method ([79] and [17]), while deterministic constructions are
notoriously more involved (see, e.g., the book of [23]). Embeddability
properties of connected expanders viewed as metric spaces when equipped with
the shortest path distance were first investigated by [53] who, among other
results, showed that if an $n$-vertex $d$-regular expander embeds with
quadratic average distortion $D$ in a $k$-dimensional normed space, then
$k\gtrsim(\log_{d}n)^{2}/D^{2}$. We shall now present the following (sharp)
improvement of Linial, London and Rabinovich’s result due to [69] as a
consequence of the average John theorem.

For every $q\in[1,\infty)$, there exists $c(q)\in(0,\infty)$ such that the
following holds for every $\gamma,D\in[1,\infty)$. Let $G=(V,E)$ be a
$d$-regular connected graph on $n$ vertices with $\gamma(A_{G})\leq\gamma$ and
let $(X,\|\cdot\|_{X})$ be a normed space such that $(G,d_{G})$ admits an
embedding into $X$ with $q$-average distortion at most $D$. Then,

$\mathrm{dim}(X)\geq n^{c(q)/\gamma D\log d}.$ (74)

######  Proof 6.1.

We shall first prove the case $q=1$. By the assumption, there exists a
$D$-Lipschitz map666As is common, we shall identify the graph $G$ with its
vertex set $V$ thus writing $f:G\to X$ rather than $f:V\to X$. Moreover, we
will always denote by $d_{G}$ the shortest path distance on $V$.
$f:(G,d_{G})\to(X,\|\cdot\|_{X})$ satisfying the average lower bound

$\frac{1}{n^{2}}\sum_{u,v\in
V}\|f(u)-f(v)\|_{X}\geq\frac{1}{n^{2}}\sum_{u,v\in V}d_{G}(u,v).$ (75)

Let $k=\mathrm{dim}(X)$. Applying Theorem 1 for the measure
$\mu=\frac{1}{n}\sum_{u\in V}\delta_{f(u)}$ on $X$, we deduce that there
exists a $O(\sqrt{\log k})$-Lipschitz function
$h:(X,\|\cdot\|_{X}^{1/2})\to\ell_{2}$ such that

$\frac{1}{n^{2}}\sum_{u,v\in
V}\|h(f(u))-h(f(v))\|_{\ell_{2}}^{2}\geq\frac{1}{n^{2}}\sum_{u,v\in
V}\|f(u)-f(v)\|_{X}.$ (76)

Since the graph $G$ is a regular expander, inequality eq:spegap implies that

$\split\frac{1}{n^{2}}\sum_{u,v\in
V}\|h(f(u))-h(f(v))\|_{\ell_{2}}^{2}&\leq\frac{2\gamma}{dn}\sum_{\\{a,b\\}\in
E}\|h(f(a))-h(f(b))\|_{\ell_{2}}^{2}\\\ \lesssim\frac{\gamma\log
k}{dn}\sum_{\\{a,b\\}\in E}\|f(a)-f(b)\|_{X}\lesssim\gamma D\log k,$ (77)

where in the last two inequalities we used the Lipschitz conditions for $h$
and $f$. On the other hand, the graph $G$ is $d$-regular and therefore, for
any fixed $u\in V$ there exist at least $\frac{n}{2}$ vertices $v\in V$ such
that $d_{G}(u,v)\geq\lfloor\log_{d}(n/2)\rfloor$. Hence, we have

$\frac{1}{n^{2}}\sum_{u,v\in V}d_{G}(u,v)\gtrsim\log_{d}n,$ (78)

which, combined with eq:x1, eq:x2 and eq:x3, implies that

$\log_{d}n\lesssim\gamma D\log k,$ (79)

thus completing the proof of eq:expanders for $q=1$. To address the general
case $q\geq 1$, we need a slight modification of this argument. It is a formal
consequence of [71, Proposition 6] and Theorem 1, that for any $q\geq 1$, the
$\tfrac{1}{2}$-snowflake of any finite-dimensional normed space $X$ embeds
into $\ell_{2}$ with $(2q)$-average distortion at most
$C(q)\sqrt{\log(\mathrm{dim}(X)+1)}$. Considering a $O(\sqrt{\log
k})$-Lipschitz embedding satisfying the analogue of eq:x2 with power $2q$
instead of the embedding $h$ and repeating the above argument completes the
proof of eq:expanders for general $q\geq 1$.

A few historical comments are in order. Due to the existence of regular
expander graph sequences, Theorem 6.1 implies that for arbitrarily large $n$,
there exists an $n$-point metric space $(\mathcal{M}_{n},d_{\mathcal{M}_{n}})$
such that if $\mathcal{M}_{n}$ admits an embedding with bi-Lipschitz
distortion $D$ into a finite-dimensional normed space $X$, then
$\mathrm{dim}(X)\geq n^{c/D}$ for some universal constant $c\in(0,\infty)$.
Therefore, Theorem 6.1 provides a negative answer to the question of [43]
discussed in Section 1.4. A different negative answer to this question had
been given in important work of [55], who devised an ingenious random family
of metric spaces and showed that they satisfy this property using input from
real algebraic geometry. It is worth mentioning that a precursor of Theorem
6.1 is a result of [51, Proposition 4.1], who showed that if an $n$-vertex
regular expander embeds in $\ell_{\infty}^{d}$ with bi-Lipschitz distortion at
most $D$, then $d\geq n^{c/D}$ for some universal constant $c\in(0,\infty)$.

Quantitatively, Theorem 6.1 provides a sharp relation between the dimension of
the target space $X$, the number of vertices of $G$ and the distortion $D$.
Indeed, a classical theorem of [44] asserts that for every $n\in\mathbb{N}$
and $D\geq 1$, any $n$-point metric space $\mathcal{M}$ admits a bi-Lipschitz
embedding with distortion at most $D$ into some $d$-dimensional normed space
$X$, where $d\lesssim_{D}n^{C/D}$ for some universal constant
$C\in(0,\infty)$. This result was later refined by [54], who showed that one
can always take $X=\ell_{\infty}^{d}$ as a target space in this statement.

The optimality of Theorem 6.1 which follows from the works of [44] and [54]
immediately implies that the $O(\sqrt{\log\mathrm{dim}(X)})$ upper bound for
the average distortion in Theorem 1 is sharp. Indeed, suppose that the
$\tfrac{1}{2}$-snowflake of $X=\ell_{\infty}^{d}$ admitted an embedding into
$\ell_{2}$ with quadratic average distortion $o(\sqrt{\log d})$. Then, the
proof of Theorem 6.1 would show that if an $n$-vertex expander embeds with bi-
Lipschitz distortion $D$ in $\ell_{\infty}^{d}$, then

$\log n=o(D\log d).$ (80)

However, this inequality contradicts the embedding theorem of [54].

Following the terminology of [70], we say that an infinite-dimensional Banach
space $(X,\|\cdot\|_{X})$ admits (quadratic) average dimension reduction with
distortion $D\in(1,\infty)$ if for any $n\in\mathbb{N}$ there exists
$k_{n}=k_{n}^{D}(X)\in\mathbb{N}$ satisfying

$\lim_{n\to\infty}\frac{\log k_{n}}{\log n}=0$ (81)

such that the following condition holds. For any $n$ points
$x_{1},\ldots,x_{n}\in X$, there exists a subspace $F=F(x_{1},\ldots,x_{n})$
of $X$ with $\mathrm{dim}F\leq k_{n}$ and points $y_{1},\ldots,y_{n}\in F$
satisfying $\|y_{i}-y_{j}\|_{X}\leq D\|x_{i}-x_{j}\|_{X}$ for every
$i,j\in\\{1,\ldots,n\\}$ and

$\frac{1}{n^{2}}\sum_{i,j=1}^{n}\|y_{i}-y_{j}\|_{X}^{2}\geq\frac{1}{n^{2}}\sum_{i,j=1}^{n}\|x_{i}-x_{j}\|_{X}^{2}.$
(82)

As every finite metric space embeds isometrically in $\ell_{\infty}$, the
aforementioned result of [55] (or Theorem 6.1) implies that $\ell_{\infty}$
does not admit average dimension reduction with any distortion $D>1$. The
following tantalizing question remains open.

######  Question 6.2.

Does $\ell_{1}$ admit average dimension reduction with any distortion $D>1$?

We note that the bi-Lipschitz analogue of Question 6.2 is answered by a famous
theorem of [21] (see also [52] for a different influential proof) who showed
that for arbitrarily large $n$ and $D>1$ there exists an $n$-point subset of
$\ell_{1}$ which does not admit a bi-Lipschitz embedding into any subspace of
$\ell_{1}$ of dimension at most $n^{c/D^{2}}$, where $c\in(0,\infty)$ is a
universal constant.

###  6.2 Average distortion embeddings of $\ell_{p}$ into $\ell_{2}$

In Theorem 1, it was established that any finite-dimensional normed space
$(X,\|\cdot\|_{X})$ admits an embedding into $\ell_{2}$ with quadratic average
distortion $O(\sqrt{\log(\mathrm{dim}(X)+1)})$ via the nonlinear spectral gap
inequality eq:estimate. As explained in Remark 6.1, this estimate for the
quadratic average distortion is asymptotically optimal yet, quite
surprisingly, there exist many non-Hilbertian normed spaces which embed with
constant quadratic average distortion in $\ell_{2}$. The following result is
the main theorem of [68].

There exists $C\in(0,\infty)$ such that for any $p\in(2,\infty)$, the normed
space $\ell_{p}$ admits an embedding into $\ell_{2}$ with quadratic average
distortion $Cp$.

Theorem 6.2 is established in [68] via the nonlinear spectral gap inequality

$\forall\
p>2,\qquad\gamma(A,\|\cdot\|_{\ell_{p}}^{2})\lesssim\frac{p^{2}}{1-\lambda_{2}(A)},$
(83)

which holds for any $\pi\in\triangle^{n-1}$ and any $\pi$-reversible
stochastic matrix $A\in M_{n}(\mathbb{R})$, and the duality principle of
Theorem 1.2. Once again, eq:lp is proven in [68] in the special case that
$\pi$ is the uniform measure on $\\{1,\ldots,n\\}$ and $A$ is a symmetric
stochastic matrix. The proof of the more general statement presented here
(which is equivalent to Theorem 6.2) is identical. In [68], Theorem 6.2 and
eq:lp were used to give new lower bounds for the $\ell_{p}$-distortion of
random connected $d$-regular graphs, Ramanujan graphs and abelian
Alon–Roichman graphs, improving earlier results of [56]. It is worth pointing
out that eq:lp is no longer valid when $p\in[1,2)$.

###  6.3 Expanders with respect to Banach spaces

Combinatorial expanders are ubiquitous geometric objects whose metric
structure is notoriously incompatible with Euclidean geometry. Nonlinear
spectral gaps allow us to analyze non-Euclidean analogues of these exotic
metrics. Let $(\mathcal{M},d_{\mathcal{M}})$ be a metric space. A sequence
$\\{G_{n}\\}_{n=1}^{\infty}$ of $d$-regular graphs with $|G_{n}|\to\infty$ is
called an expander graph sequence with respect to $\mathcal{M}$ if
$\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}},d_{\mathcal{M}}^{2})<\infty$. If such
graphs exist, we say that $(\mathcal{M},d_{\mathcal{M}})$ admits a sequence of
$d$-regular expanders. The following influential observation on the
embeddability of expanders is essentially due to [56].

######  Proposition 4.

Let $(\mathcal{M},d_{\mathcal{M}})$ be a metric space and fix
$\gamma,q\in(0,\infty)$. Suppose that $G=(V,E)$ is a $d$-regular connected
graph on $n$ vertices with $\gamma(A_{G},d_{\mathcal{M}}^{q})\leq\gamma$. If
$(G,d_{G})$ embeds into $(\mathcal{M},d_{\mathcal{M}})$ with $q$-average
distortion at most $D$, then $D\gtrsim\frac{\log_{d}n}{\gamma^{1/q}}$.

######  Proof 6.3.

By the assumption, there exists $\sigma\in(0,\infty)$ and a $\sigma
D$-Lipschitz map $f:(G,d_{G})\to(\mathcal{M},d_{\mathcal{M}})$ satisfying the
average lower bound

$\frac{1}{n^{2}}\sum_{u,v\in
V}d_{\mathcal{M}}\big{(}f(u),f(v)\big{)}^{q}\geq\frac{\sigma^{q}}{n^{2}}\sum_{u,v\in
V}d_{G}(u,v)^{q}\gtrsim\sigma^{q}(\log_{d}n)^{q},$ (84)

where the second inequality follows from eq:x4 and Jensen’s inequality. On the
other hand, by the definition eq:nsg of $\gamma(A,d_{\mathcal{M}}^{q})$, we
have

$\frac{1}{n^{2}}\sum_{u,v\in
V}d_{\mathcal{M}}\big{(}f(u),f(v)\big{)}^{q}\leq\frac{2\gamma}{dn}\sum_{\\{a,b\\}\in
E}d_{\mathcal{M}}\big{(}f(a),f(b)\big{)}^{q}\leq\gamma\sigma^{q}D^{q},$ (85)

where the last inequality follows from the Lipschitz condition for $f$.
Rearranging, we deduce the desired lower bound for the $q$-average distortion
$D$.

Deciding whether a given non-Euclidean metric space admits a sequence of
expanders is a notoriously difficult problem in metric geometry, even when
specified to normed spaces. By Proposition 4, it is clear that if there exists
a sequence $\\{G_{n}\\}_{n=1}^{\infty}$ of regular expanders with respect to a
normed space $(X,\|\cdot\|_{X})$, then $X$ cannot contain subspaces uniformly
isomorphic to $\\{\ell_{\infty}^{m}\\}_{m=1}^{\infty}$ as it would then bi-
Lipschitzly contain all finite metric spaces with uniform distortion. Normed
spaces which do not uniformly contain $\\{\ell_{\infty}^{m}\\}_{m=1}^{\infty}$
are said to have finite cotype in Banach space theory jargon [59]. Strikingly,
this is the only known necessary condition for a normed space to admit an
expander graph sequence and the following general question remains open.

######  Question 6.4.

Is every combinatorial expander also an expander with respect to any normed
space of finite cotype?

Such implications, asserting that a classical spectral gap implies a nonlinear
spectral gap, are currently only known for substantially smaller classes of
normed spaces from works of [56], [78], [82] and [73]. It is worth mentioning
that even the following question, which is formally weaker than Question 6.4
in view of Proposition 4, remains open.

######  Question 6.5.

Does there exist a sequence of finite metric spaces
$\\{(\mathcal{M}_{n},d_{\mathcal{M}_{n}})\\}_{n=1}^{\infty}$ with
$|\mathcal{M}_{n}|\to\infty$ as $n\to\infty$ such that for any normed space
$(X,\|\cdot\|_{X})$ of finite cotype, the bi-Lipschitz distortion required to
embed $\mathcal{M}_{n}$ into $X$ satisfies
$\mathsf{c}_{X}(\mathcal{M}_{n})\gtrsim_{X}\log|\mathcal{M}_{n}|$?

A positive answer to Question 6.5 would imply a striking dichotomy in the
embeddability of finite metric spaces into infinite-dimensional normed spaces.
If such a normed space $X$ does not have finite cotype, then it bi-Lipschitzly
contains every finite metric space with distortion $1+\varepsilon$ for any
$\varepsilon>0$ [59]. On the other hand, if $X$ is an arbitrary infinite-
dimensional space, then any finite metric space $\mathcal{M}$ admits a bi-
Lipschitz embedding into $X$ with distortion $O(\log|\mathcal{M}|)$ by the
theorems of [26] and [18]. A positive answer to Question 6.5 would imply that
this bound is always optimal under the (necessary) assumption that $X$ has
finite cotype.

In regard to Question 6.4, even the _existence_ of a sequence
$\\{G_{n}\\}_{n=1}^{\infty}$ of regular graphs which are expanders with
respect to any space of finite cotype remains unknown. The strongest available
result in this direction is the following profound theorem of [49], whose
proof is an ingenious combination of algebraic and vector-valued harmonic
analytic methods. We say that a normed space $(X,\|\cdot\|_{X})$ has
nontrivial type if $X$ does not contain subspaces uniformly isomorphic to
$\\{\ell_{1}^{m}\\}_{m=1}^{\infty}$ [59]. Any space of nontrivial type has
finite cotype, but the converse is not true (e.g. for $\ell_{1}$).

There exists a sequence of regular graphs $\\{G_{n}\\}_{n=1}^{\infty}$ which
is an expander graph sequence with respect to any normed space of non-trivial
type.

Lafforgue’s graphs can be obtained as Cayley graphs of finite quotients of co-
compact lattices in $SL_{3}(\mathbb{Q}_{p})$, where $p$ is a prime and
$\mathbb{Q}_{p}$ is the field of $p$-adic rationals.

A completely different construction of a sequence of regular graphs which are
expanders with respect to a large family of norms was presented in work of
[63]. Theirs is a vector-valued adaptation of the zig-zag product construction
of [84] and the resulting graphs are expanders with respect to any normed
space which admits an equivalent uniformly convex norm. Clearly any such space
has nontrivial type but the converse is not true [81]. While we will not
outline the argument of [63], it is worth pointing out that it consists of a
novel construction of a base graph along with an adaptation of the zig-zag
iteration of [84]. The necessity of the uniform convexity assumption in this
argument stems from this iteration procedure. On the other hand, the
construction of the base graph (which was straightforward in the case of
combinatorial expanders) has raised influential questions in vector-valued
harmonic analysis that led to investigations of independent interest ([63];
[29, 30]).

###  6.4 Expanders with respect to Alexandrov spaces

A complete geodesic metric space $(\mathcal{M},d_{\mathcal{M}})$ is an
Alexandrov space of nonpositive curvature (or a CAT(0) space) if for any
quadruple of points $x,y,z,m\in\mathcal{M}$ such that $m$ is a metric midpoint
of $x$ and $y$, that is,
$d_{\mathcal{M}}(m,x)=d_{\mathcal{M}}(m,y)=\tfrac{1}{2}d_{\mathcal{M}}(x,y)$,
we have

$d_{\mathcal{M}}(z,m)^{2}\leq\frac{1}{2}d_{\mathcal{M}}(z,x)^{2}+\frac{1}{2}d_{\mathcal{M}}(z,y)^{2}-\frac{1}{4}d_{\mathcal{M}}(x,y)^{2}.$
(86)

If the reverse inequality holds true for any such quadruple
$x,y,z,m\in\mathcal{M}$, then $\mathcal{M}$ is an Alexandrov space of
nonnegative curvature. Alexandrov spaces of nonpositive (respectively
nonnegative) curvature are (potentially singular) metric spaces which
generalize Riemannian manifolds with nonpositive (resp. nonnegative) sectional
curvature.

An argument of [87] shows that any regular combinatorial expander is also an
expander with respect to any Hilbert manifold with a CAT(0) Riemannian metric
(see also [73, Corollary 4.10]). The first systematic study of expanders with
respect to (non-smooth) Alexandrov spaces of nonpositive curvature was
undertaken by [64], who showed the following theorem.

There exists a CAT(0) space $(\mathcal{M},d_{\mathcal{M}})$ and a sequence
$\\{G_{n}\\}_{n=1}^{\infty}$ of 3-regular graphs such that
$\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}},d_{\mathcal{M}}^{2})<\infty$, yet a
random $d$-regular graph ${\bf G}$ on $n$ vertices satisfies $\gamma(A_{\bf
G},d_{\mathcal{M}}^{2})\gtrsim(\log_{d}n)^{2}$ with probability $1-o_{n}(1)$
as $n\to\infty$.

Theorem 6.4 reveals a striking difference between nonlinear spectral gaps with
respect to Alexandrov spaces of nonpositive curvature and classical spectral
gaps, as a random $d$-regular graph on $n$-vertices is a combinatorial
expander with probability $1-o_{n}(1)$ as $n\to\infty$ for any fixed
$d\in\mathbb{N}$ [17]. The following question remains open.

######  Question 6.6.

Does every CAT(0) space admit a sequence of regular expanders? More
ambitiously, does there exists a sequence of $O(1)$-regular graphs
$\\{G_{n}\\}_{n=1}^{\infty}$ with $|G_{n}|\to\infty$ such that
$\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}},d_{\mathcal{M}}^{2})<\infty$ for every
CAT(0) space $(\mathcal{M},d_{\mathcal{M}})$?

A positive answer to the stronger statement in Question 6.6 would imply (in
view of Proposition 4) the existence of arbitrarily large finite metric spaces
requiring logarithmic distortion to be embedded in any Alexandrov space of
nonpositive curvature. The following question was asked by [31].

######  Question 6.7.

Does there exist a sequence of finite metric spaces
$\\{(\mathcal{M}_{n},d_{\mathcal{M}_{n}})\\}_{n=1}^{\infty}$ with
$|\mathcal{M}_{n}|\to\infty$ as $n\to\infty$ such that for any CAT(0) space
$(\mathcal{N},\|\cdot\|_{\mathcal{N}})$, the bi-Lipschitz distortion required
to embed $\mathcal{M}_{n}$ into $\mathcal{N}$ satisfies
$\mathsf{c}_{\mathcal{N}}(\mathcal{M}_{n})\gtrsim_{\mathcal{N}}\log|\mathcal{M}_{n}|$?

In the dual nonnegative curvature regime, the analogue of Question 6.6 was
answered by [5], who showed that there exists an Alexandrov space of
nonnegative curvature which does not admit any sequence of regular expanders.
Moreover, they asked the following dual to Question 6.7.

######  Question 6.8.

Does there exist an Alexandrov space of nonnegative curvature
$(\mathcal{N},d_{\mathcal{N}})$ such that any finite metric space
$(\mathcal{M},d_{\mathcal{M}})$ embeds into $\mathcal{N}$ with bi-Lipschitz
distortion
$\mathsf{c}_{\mathcal{N}}(\mathcal{M})\lesssim\sqrt{\log|\mathcal{M}|}$?

In their paper, they specifically asked Question 6.8 for the concrete
Alexandrov space $\mathcal{P}_{2}(\mathbb{R}^{3})$, which is the space of all
Borel probability measures $\mu$ on $\mathbb{R}^{3}$ satisfying
$\int_{\mathbb{R}^{3}}\|x\|_{\ell_{2}^{3}}^{2}\,\mathop{}\\!\mathrm{d}\mu(x)<\infty$
equipped with the Wasserstein $\mathsf{W}_{2}$-distance.

###  6.5 Coarse non-universality

Let $(\mathcal{M},d_{\mathcal{M}})$ and $(\mathcal{N},d_{\mathcal{N}})$ be two
metric spaces and $\omega,\Omega:[0,\infty)\to[0,\infty)$ two moduli
satisfying $\omega\leq\Omega$ pointwise and
$\lim_{t\to\infty}\omega(t)=\infty$. A mapping $f:\mathcal{M}\to\mathcal{N}$
is a coarse embedding with lower and upper moduli $\omega$ and $\Omega$
respectively if

$\forall\ x,y\in\mathcal{M},\qquad\omega\big{(}d_{\mathcal{M}}(x,y)\big{)}\leq
d_{\mathcal{N}}\big{(}f(x),f(y)\big{)}\leq\Omega\big{(}d_{\mathcal{M}}(x,y)\big{)}.$
(87)

A family of metric spaces
$\\{(\mathcal{M}_{\alpha},d_{\mathcal{M}_{\alpha}})\\}_{\alpha}$ is said to
embed equi-coarsely into a metric space $(\mathcal{N},d_{\mathcal{N}})$ if
there exist two moduli $\omega,\Omega:[0,\infty)\to[0,\infty)$ satisfying
$\omega\leq\Omega$ pointwise and $\lim_{t\to\infty}\omega(t)=\infty$ and a
family of coarse embeddings
$\\{f_{\alpha}:\mathcal{M}_{\alpha}\to\mathcal{N}\\}_{\alpha}$ with lower and
upper moduli $\omega$ and $\Omega$. The pertinence of nonlinear spectral gaps
in coarse geometry stems from the following influential observation of [36,
37].

######  Proposition 5.

Fix $d\in\mathbb{N}$, $p\in(0,\infty)$ and let $(\mathcal{M},d_{\mathcal{M}})$
be a metric space. Suppose that $\\{G_{n}=(V_{n},E_{n})\\}_{n=1}^{\infty}$ is
a sequence of connected $d$-regular graphs with $|V_{n}|\to\infty$ and
$\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}},d_{\mathcal{M}}^{p})<\infty$. Then, the
family of graphs $\\{(G_{n},d_{G_{n}})\\}_{n=1}^{\infty}$ equipped with their
shortest path distances does not equi-coarsely embed into $\mathcal{M}$.

######  Proof 6.9.

Let
$\gamma\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sup_{n\in\mathbb{N}}\gamma(A_{G_{n}},d_{\mathcal{M}}^{p})<\infty$.
Suppose that there exist two moduli $\omega,\Omega:[0,\infty)\to[0,\infty)$
with $\lim_{t\to\infty}\omega(t)=\infty$ and mappings
$f_{n}:V_{n}\to\mathcal{M}$ with

$\forall\ x,y\in V_{n},\qquad\omega\big{(}d_{G_{n}}(x,y)\big{)}\leq
d_{\mathcal{M}}\big{(}f(x),f(y)\big{)}\leq\Omega\big{(}d_{G_{n}}(x,y)\big{)}.$
(88)

By definition of nonlinear spectral gaps, we have

$\frac{1}{|V_{n}|^{2}}\sum_{u,v\in
V_{n}}d_{\mathcal{M}}\big{(}f_{n}(u),f_{n}(v)\big{)}^{p}\leq\frac{2\gamma}{d|V_{n}|}\sum_{\\{a,b\\}\in
E_{n}}d_{\mathcal{M}}\big{(}f_{n}(a),f_{n}(b)\big{)}^{p}.$ (89)

Moreover, using the upper modulus, we get

$\frac{2\gamma}{d|V_{n}|}\sum_{\\{a,b\\}\in
E_{n}}d_{\mathcal{M}}\big{(}f_{n}(a),f_{n}(b)\big{)}^{p}\stackrel{{\scriptstyle\eqref{eq:coarse-
assume}}}{{\leq}}\frac{2\gamma}{d|V_{n}|}\sum_{\\{a,b\\}\in
E_{n}}\Omega(1)^{p}=\gamma\Omega(1)^{p}.$ (90)

Finally, as each graph $G_{n}$ is $d$-regular, for any $u\in V_{n}$ there
exist at least $\frac{|V_{n}|}{2}$ vertices $v\in V_{n}$ such that
$d_{G_{n}}(u,v)\geq\lfloor\log_{d}(|V_{n}|/2)\rfloor$. Thus, the lower modulus
gives

$\frac{1}{|V_{n}|^{2}}\sum_{u,v\in
V_{n}}d_{\mathcal{M}}\big{(}f_{n}(u),f_{n}(v)\big{)}^{p}\stackrel{{\scriptstyle\eqref{eq:coarse-
assume}}}{{\geq}}\frac{1}{|V_{n}|^{2}}\sum_{u,v\in
V_{n}}\omega\big{(}d_{G_{n}}(u,v)\big{)}^{p}\geq\frac{\omega(\lfloor\log_{d}(|V_{n}|/2)\rfloor)^{p}}{2}.$

Combining all the above, we deduce that

$\forall\
n\in\mathbb{N},\qquad\omega(\lfloor\log_{d}(|V_{n}|/2)\rfloor)^{p}\leq
2\gamma\Omega(1)^{p},$ (91)

which clearly contradicts the coarse condition
$\lim_{t\to\infty}\omega(t)=\infty$.

An important consequence of Gromov’s observation is that if
$(\mathcal{M},d_{\mathcal{M}})$ admits a sequence of regular expanders
$\\{G_{n}\\}_{n=1}^{\infty}$, then there exists a metric space (e.g. the
disjoint union $\bigsqcup_{n\geq 1}(G_{n},d_{G_{n}})$) which does not admit a
coarse embedding into $\mathcal{M}$. Consequently, the mere existence of
combinatorial expanders implies that Hilbert spaces are not coarsely universal
which is a well-known theorem of [25]. Moreover, Lafforgue’s Theorem 6.3
implies the existence of a metric space which does not admit a coarse
embedding into any Banach space of non-trivial type. The coarse non-
universality of this class was previously established in work of [61] by
proving that Banach spaces of non-trivial type with cotype $q$ have _sharp_
metric cotype $q$. Understanding whether every Banach space of cotype $q$ has
sharp metric cotype $q$ is the central open problem in the theory of metric
cotype of Banach spaces; see [33] for the best known results to date. If this
was the case, then the following (currently open) question on coarse
embeddings would have a negative answer.

######  Question 6.10.

Does every separable metric space embed coarsely into some Banach space of
finite cotype?

It follows from Proposition 5 that a negative answer to Question 6.10 would
also be a consequence of the existence of a sequence of regular graphs
$\\{G_{n}\\}_{n=1}^{\infty}$ which are expanders with respect to any normed
space of finite cotype simultaneously, let alone from a positive answer to the
much stronger Question 6.4.

Despite the fact that Question 6.6 on the existence of expanders with respect
to Alexandrov spaces of nonpositive curvature remains open, the coarse non-
universality of this class was established by [31], thus answering a question
raised by [35]. The main technical contribution of this work is the proof that
every CAT(0) space $\mathcal{M}$ has sharp metric cotype 2 which formally
implies that $\ell_{q}$ does not admit a coarse embedding in $\mathcal{M}$ for
any $q>2$. In contrast to this result, the very surprising fact that there
exist coarsely universal Alexandrov spaces of nonnegative curvature was proven
by [5].

###  6.6 Approximate nearest neighbor search

Fix a parameter $c>1$. The $c$-Approximate Nearest Neighbor Search problem is
defined as follows. Given an $n$-point dataset $\mathcal{P}$ in some metric
space $(\mathcal{M},d_{\mathcal{M}})$, we want to build a data structure777For
the purposes of this survey, a data structure of size $M$ is an array
$A[1\ldots M]$ of numbers (the “memory”) along with an algorithm which, given
a point $q\in\mathcal{M}$, returns a point $\widehat{p}\in\mathcal{P}$. that,
given any query point $q\in\mathcal{M}$, returns a point
$\widehat{p}\in\mathcal{P}$ with $d_{\mathcal{M}}(q,\widehat{p})\leq
c\min_{p\in\mathcal{P}}d_{\mathcal{M}}(q,p)$. In practice, this problem can be
reduced to its “decision version” (see [38]), which is the $c$-Approximate
_Near_ Neighbor Search ($c$-ANN) problem at a _pre-fixed_ distance scale
$r>0$. In the $c$-ANN problem at scale $r$, we are again given an $n$-point
dataset $\mathcal{P}$ in some metric space $(\mathcal{M},d_{\mathcal{M}})$ and
we want to build a data structure that, given any query point
$q\in\mathcal{M}$ for which there exists a point $p^{\ast}\in\mathcal{P}$ with
$d_{\mathcal{M}}(q,p^{\ast})\leq r$, returns a point
$\widehat{p}\in\mathcal{P}$ with $d_{\mathcal{M}}(q,\widehat{p})\leq cr$. The
main parameters to optimize are the _space_ the data structure occupies and
the _time_ it takes to answer a query. A majority of the research conducted on
this problem has focused on $d$-dimensional normed spaces rather than general
metric spaces and moreover most of the algorithms in the literature are
_randomized_ in the sense that they return a random point $\widehat{p}$
satisfying $d_{\mathcal{M}}(q,\widehat{p})\leq cr$ with probability at least
$1-\delta$ for some pre-fixed confidence parameter $\delta\in(0,1)$.

The first approaches to the $c$-ANN problem for $d$-dimensional norms produced
data-independent data structures, in which the memory cells accessed by the
algorithm do not depend on the dataset $\mathcal{P}$ but only on the query
point $q$. In particular, building such data structures via (oblivious) metric
dimension reduction has been used with great success for the Hilbert space
$\ell_{2}^{d}$ ([41]; [38]), the hypercube $\\{-1,1\\}^{d}$ equipped with the
Hamming distance [48] and spaces which (effectively) embed in them [2, 74].
While dimension reduction techniques yield data structures with polynomial
space for these norms, these results are often far from practical due to the
large degree of said polynomial. To overcome this barrier, [41] introduced an
influential technique called _Locality-Sensitive Hashing_ (LSH) relying on
(data-independent) randomized space partitions. Somewhat informally, a
distribution $\mathcal{D}$ over a family of partitions of $\mathcal{M}$ is
called _sensitive_ at scale $r$ up to error $c$ if any two points at distance
at most $r$ are $\mathcal{D}$-likely to belong in the same cluster of the
partition and any two points at distance at least $cr$ are
$\mathcal{D}$-unlikely to do so (where the implicit probabilities affect the
space and time requirements of the data structure). As shown by [41], a
(computationally efficient) sensitive distribution over random partitions can
serve as a pre-filter for the dataset $\mathcal{P}$ as the query point $q$ is
very likely to be indistinguishable from its near neighbors but is unlikely to
collide with points $p$ having $d_{\mathcal{M}}(q,p)>cr$. Using LSH, they were
able to improve the space requirements over the existing $c$-ANN algorithms to
almost linear for large enough accuracy parameters $c>1$. We refer to the
thorough survey of [4] for a detailed account of these and other contributions
on the $c$-ANN problem and further references.

Despite these advances towards the $c$-ANN problem, researchers proved strong
impossibility results [66, 76] for the existence of data-independent data
structures arising from LSH, thus creating the necessity for the development
of efficient data-_dependent_ algorithms. Historically, the first such result
was proven by [40] for $\ell_{\infty}^{d}$. In recent years, this approach has
gained a lot of momentum, especially in view of the works of [2] for the Ulam
metric, [3, 9] for $\ell_{2}^{d}$ and [8] for 1-symmetric norms. A
breakthrough in this direction was presented in the work of [6] who showed the
following theorem for _general_ $d$-dimensional normed spaces. It is worth
emphasizing that their result does not a priori give any bound on the running
time of the algorithm, it just restricts the number of memory locations the
data structure is allowed to probe.

Fix $\varepsilon\in(0,1)$ and let $X$ be a $d$-dimensional normed space. There
exists a randomized data structure for $O\big{(}\frac{\log
d}{\varepsilon^{2}}\big{)}$-ANN over $X$ with the following properties:

  1. $\bullet$

The space used by the data structure is $n^{1+\varepsilon}\cdot d^{O(1)}$;

  2. $\bullet$

The query procedure probes $n^{\varepsilon}\cdot d^{O(1)}$ words in memory.

In order to prove Theorem 6.6, the authors introduced a geometric parameter
called the cutting modulus $\Xi(\mathcal{M},\varepsilon)$ associated to a
metric space $(\mathcal{M},d_{\mathcal{M}})$ and a parameter
$\varepsilon\in(0,1)$, which governs the following data-dependent partitioning
scheme: every finite dataset in $\mathcal{M}$ either has a subset of
proportional size (measured appropriately) which is contained in a ball of
radius $\Xi(\mathcal{M},\varepsilon)$ or admits a cut which is
$\varepsilon$-sparse. Relying on this notion, they were able to show the
following general partitioning theorem.

Let $(\mathcal{M},d_{\mathcal{M}})$ be a finite metric space and fix
$n\in\mathbb{N}$, $\varepsilon\in(0,\tfrac{1}{4})$. There exists a collection
$\mathcal{C}$ of subsets of $\mathcal{M}$ with
$\log|\mathcal{C}|=O\big{(}\log|\mathcal{M}|\log(\log|\mathcal{M}|/\varepsilon)\big{)}$
such that for any $n$-point dataset $\mathcal{P}$ in $\mathcal{M}$, we have
one of the following two properties:

  1. $\bullet$

Either there exists $x_{0}\in\mathcal{M}$ and
$R\leq\Xi(\mathcal{M},\varepsilon)$ such that $|\mathcal{P}\cap
B_{\mathcal{M}}(x_{0},R)|\geq\tfrac{n}{50}$, or

  2. $\bullet$

There exists a subcollection $\\{S_{1},\ldots,S_{m}\\}\subseteq\mathcal{C}$
such that

$\forall\
i\in\\{1,\ldots,m\\},\qquad\frac{n}{50}\leq|S_{i}\cap\mathcal{P}|\leq\frac{49n}{50}$
(92)

and for every $x,y\in\mathcal{M}$ with $d_{\mathcal{M}}(x,y)\leq 1$, we have

$\\#\big{\\{}i\in\\{1,\ldots,m\\}:\ {\bf 1}_{S_{i}}(x)\neq{\bf
1}_{S_{i}}(y)\big{\\}}\leq 50\varepsilon m.$ (93)

Theorem 6.6 suggests a very natural LSH with approximation
$O(\Xi(\mathcal{M},\varepsilon))$ since, at each step of the algorithm, we
either have a dense ball of radius $\Xi(\mathcal{M},\varepsilon)$ or we have a
collection of subsets with a distribution that decreases the size of the
dataset and rarely splits the query from its nearby points in the dataset. The
relevance of those results with the subject of this survey stems from the fact
that Theorem 1.2 implies that if $X$ is a normed space, then the cutting
modulus satisfies

$\Xi(X,\varepsilon)\lesssim\frac{\log(\mathrm{dim}(X)+1)}{\varepsilon^{2}}.$
(94)

The main idea of the proof of eq:bound-cut is to apply eq:estimate to the
adjacency matrices of geometric graphs associated to finite subsets of $X$. If
such a graph does not have a subset of proportional size (with respect to the
underlying stationary measure) contained in a ball of radius
$\Omega(\log(\mathrm{dim}(X)))$, then the nonlinear spectral gap inequality
eq:estimate implies that it also cannot have large (classical) spectral gap
and thus admits a sparse cut by Cheeger’s inequality. A combination of Theorem
6.6 and eq:bound-cut implies Theorem 6.6. We refer to the work of [6] for the
precise definition of the cutting modulus and the proofs of these results.

In their follow-up work, [7] proved the existence of data structures for ANN
over $d$-dimensional normed spaces with slightly worse (but still
subpolynomial) approximation and reasonable bounds for the running time. Some
of their results still rely on elements of the theory of nonlinear spectral
gaps, whereas others use the existence of a remarkable uniform homeomorphism
between spheres of Banach spaces which originates in the resolution of the
distortion problem by [75].

## References

  * [1] Ittai Abraham, Yair Bartal and Ofer Neiman  “Advances in metric embedding theory”  In _Adv. Math._ 228.6, 2011, pp. 3026–3126  DOI: 10.1016/j.aim.2011.08.003
  * [2] Alexandr Andoni, Piotr Indyk and Robert Krauthgamer  “Overcoming the $\ell_{1}$ non-embeddability barrier: algorithms for product metrics”  In _Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms_ SIAM, Philadelphia, PA, 2009, pp. 865–874
  * [3] Alexandr Andoni, Piotr Indyk, Huy L. Nguyễn and Ilya Razenshteyn  “Beyond locality-sensitive hashing”  In _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms_ ACM, New York, 2014, pp. 1018–1028  DOI: 10.1137/1.9781611973402.76
  * [4] Alexandr Andoni, Piotr Indyk and Ilya Razenshteyn  “Approximate nearest neighbor search in high dimensions”  In _Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures_ World Sci. Publ., Hackensack, NJ, 2018, pp. 3287–3318
  * [5] Alexandr Andoni, Assaf Naor and Ofer Neiman  “Snowflake universality of Wasserstein spaces”  In _Ann. Sci. Éc. Norm. Supér. (4)_ 51.3, 2018, pp. 657–700  DOI: 10.24033/asens.2363
  * [6] Alexandr Andoni et al.  “Data-dependent hashing via nonlinear spectral gaps”  In _STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ ACM, New York, 2018, pp. 787–800  DOI: 10.1145/3188745.3188846
  * [7] Alexandr Andoni et al.  “Hölder homeomorphisms and approximate nearest neighbors”  In _59th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2018_ IEEE Computer Soc., Los Alamitos, CA, 2018, pp. 159–169  DOI: 10.1109/FOCS.2018.00024
  * [8] Alexandr Andoni et al.  “Approximate near neighbors for general symmetric norms”  In _STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ ACM, New York, 2017, pp. 902–913
  * [9] Alexandr Andoni and Ilya Razenshteyn  “Optimal data-dependent hashing for approximate near neighbors”  In _STOC’15—Proceedings of the 2015 ACM Symposium on Theory of Computing_ ACM, New York, 2015, pp. 793–801
  * [10] Juan Arias-de-Reyna and Luis Rodríguez-Piazza  “Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces”  In _Israel J. Math._ 79.1, 1992, pp. 103–111  DOI: 10.1007/BF02764804
  * [11] Keith Ball  “Isometric embedding in $l_{p}$-spaces”  In _European J. Combin._ 11.4, 1990, pp. 305–311  DOI: 10.1016/S0195-6698(13)80131-X
  * [12] Keith Ball  “Markov chains, Riesz transforms and Lipschitz maps”  In _Geom. Funct. Anal._ 2.2, 1992, pp. 137–172  DOI: 10.1007/BF01896971
  * [13] Keith Ball  “The Ribe programme” Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058  In _Astérisque_ , 2013, pp. Exp. No. 1047, viii, 147–159
  * [14] Keith Ball, Eric A. Carlen and Elliott H. Lieb  “Sharp uniform convexity and smoothness inequalities for trace norms”  In _Invent. Math._ 115.3, 1994, pp. 463–482  DOI: 10.1007/BF01231769
  * [15] Florent P. Baudier and William B. Johnson  “Metric embeddings: bilipschitz and coarse embeddings into Banach spaces [book review of MR3114782]”  In _Bull. Amer. Math. Soc. (N.S.)_ 53.3, 2016, pp. 495–506  DOI: 10.1090/bull/1523
  * [16] Yoav Benyamini and Joram Lindenstrauss  “Geometric nonlinear functional analysis. Vol. 1” 48, American Mathematical Society Colloquium Publications  American Mathematical Society, Providence, RI, 2000, pp. xii+488  DOI: 10.1090/coll/048
  * [17] Béla Bollobás  “The isoperimetric number of random regular graphs”  In _European J. Combin._ 9.3, 1988, pp. 241–244  DOI: 10.1016/S0195-6698(88)80014-3
  * [18] Jean Bourgain  “On Lipschitz embedding of finite metric spaces in Hilbert space”  In _Israel J. Math._ 52.1-2, 1985, pp. 46–52  DOI: 10.1007/BF02776078
  * [19] Jean Bourgain  “The metrical interpretation of superreflexivity in Banach spaces”  In _Israel J. Math._ 56.2, 1986, pp. 222–230  DOI: 10.1007/BF02766125
  * [20] Jean Bretagnolle, Didier Dacunha-Castelle and Jean-Louis Krivine  “Lois stables et espaces $L^{p}$”  In _Ann. Inst. H. Poincaré Sect. B (N.S.)_ 2, 1965/1966, pp. 231–259
  * [21] Bo Brinkman and Moses Charikar  “On the impossibility of dimension reduction in $l_{1}$”  In _J. ACM_ 52.5, 2005, pp. 766–788  DOI: 10.1145/1089023.1089026
  * [22] Qingjin Cheng  “Sphere equivalence, property H, and Banach expanders”  In _Studia Math._ 233.1, 2016, pp. 67–83  DOI: 10.4064/sm8396-4-2016
  * [23] Giuliana Davidoff, Peter Sarnak and Alain Valette  “Elementary number theory, group theory, and Ramanujan graphs” 55, London Mathematical Society Student Texts  Cambridge University Press, Cambridge, 2003, pp. x+144  DOI: 10.1017/CBO9780511615825
  * [24] Tim de Laat and Mikael de la Salle  “Banach space actions and $L^{2}$-spectral gap”  In _Anal. PDE_ 14.1, 2021, pp. 45–76  DOI: 10.2140/apde.2021.14.45
  * [25] Alexander N. Dranishnikov, Guihua Gong, Vincent Lafforgue and Guoliang Yu  “Uniform embeddings into Hilbert space and a question of Gromov”  In _Canad. Math. Bull._ 45.1, 2002, pp. 60–70  URL: https://doi.org/10.4153/CMB-2002-006-9
  * [26] Aryeh Dvoretzky  “Some results on convex bodies and Banach spaces”  In _Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960)_ Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961, pp. 123–160
  * [27] Alexandros Eskenazis  “Geometric Inequalities and Advances in the Ribe Program” Thesis (Ph.D.)–Princeton University  ProQuest LLC, Ann Arbor, MI, 2019, pp. 399  URL: http://gateway.proquest.com.ezp.lib.cam.ac.uk/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqm&rft_dat=xri:pqdiss:13878226
  * [28] Alexandros Eskenazis  “$\varepsilon$-isometric dimension reduction for incompressible subsets of $\ell_{p}$” Preprint available at https://arxiv.org/abs/2109.06602, 2021
  * [29] Alexandros Eskenazis and Paata Ivanisvili  “Polynomial inequalities on the Hamming cube”  In _Probab. Theory Related Fields_ 178.1-2, 2020, pp. 235–287  DOI: 10.1007/s00440-020-00973-y
  * [30] Alexandros Eskenazis and Paata Ivanisvili  “Sharp growth of the Ornstein–Uhlenbeck operator on Gaussian tail spaces” To appear in Israel J. Math.. Preprint available at https://arxiv.org/abs/2011.01359, 2021
  * [31] Alexandros Eskenazis, Manor Mendel and Assaf Naor  “Nonpositive curvature is not coarsely universal”  In _Invent. Math._ 217.3, 2019, pp. 833–886  DOI: 10.1007/s00222-019-00878-1
  * [32] Alexandros Eskenazis and Assaf Naor  “On coarse and uniform embeddings into $L_{p}$” Preprint, 2021
  * [33] Ohad Giladi, Manor Mendel and Assaf Naor  “Improved bounds in the metric cotype inequality for Banach spaces”  In _J. Funct. Anal._ 260.1, 2011, pp. 164–194  URL: https://doi.org/10.1016/j.jfa.2010.08.015
  * [34] Gilles Godefroy  “De Grothendieck à Naor: une promenade dans l’analyse métrique des espaces de Banach”  In _Gaz. Math._ , 2017, pp. 13–24
  * [35] Mikhail Gromov  “Asymptotic invariants of infinite groups”  In _Geometric group theory, Vol. 2 (Sussex, 1991)_ 182, London Math. Soc. Lecture Note Ser.  Cambridge Univ. Press, Cambridge, 1993, pp. 1–295
  * [36] Mikhail Gromov  “Spaces and questions” GAFA 2000 (Tel Aviv, 1999)  In _Geom. Funct. Anal._ , 2000, pp. 118–161
  * [37] Mikhail Gromov  “Random walk in random groups”  In _Geom. Funct. Anal._ 13.1, 2003, pp. 73–146  DOI: 10.1007/s000390300002
  * [38] Sariel Har-Peled, Piotr Indyk and Rajeev Motwani  “Approximate nearest neighbor: towards removing the curse of dimensionality”  In _Theory Comput._ 8, 2012, pp. 321–350  DOI: 10.4086/toc.2012.v008a014
  * [39] Stefan Heinrich  “Ultraproducts in Banach space theory”  In _J. Reine Angew. Math._ 313, 1980, pp. 72–104  DOI: 10.1515/crll.1980.313.72
  * [40] Piotr Indyk  “On approximate nearest neighbors under $l_{\infty}$ norm” Special issue on FOCS 98 (Palo Alto, CA)  In _J. Comput. System Sci._ 63.4, 2001, pp. 627–638  DOI: 10.1006/jcss.2001.1781
  * [41] Piotr Indyk and Rajeev Motwani  “Approximate nearest neighbors: towards removing the curse of dimensionality”  In _STOC ’98 (Dallas, TX)_ ACM, New York, 1999, pp. 604–613
  * [42] Fritz John  “Extremum problems with inequalities as subsidiary conditions”  In _Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948_ Interscience Publishers, Inc., New York, N. Y., 1948, pp. 187–204
  * [43] William B. Johnson and Joram Lindenstrauss  “Extensions of Lipschitz mappings into a Hilbert space”  In _Conference in modern analysis and probability (New Haven, Conn., 1982)_ 26, Contemp. Math.  Amer. Math. Soc., Providence, RI, 1984, pp. 189–206  DOI: 10.1090/conm/026/737400
  * [44] William B. Johnson, Joram Lindenstrauss and Gideon Schechtman  “On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces”  In _Geometrical aspects of functional analysis (1985/86)_ 1267, Lecture Notes in Math.  Springer, Berlin, 1987, pp. 177–184  DOI: 10.1007/BFb0078145
  * [45] Nigel J. Kalton  “The nonlinear geometry of Banach spaces”  In _Rev. Mat. Complut._ 21.1, 2008, pp. 7–60  DOI: 10.5209/rev_REMA.2008.v21.n1.16426
  * [46] Takefumi Kondo  “${\rm CAT}(0)$ spaces and expanders”  In _Math. Z._ 271.1-2, 2012, pp. 343–355  DOI: 10.1007/s00209-011-0866-y
  * [47] Jean-Louis Krivine  “Plongement des espaces normés dans les $L^{p}$ pour $p>2$”  In _C. R. Acad. Sci. Paris_ 261, 1965, pp. 4307–4310
  * [48] Eyal Kushilevitz, Rafail Ostrovsky and Yuval Rabani  “Efficient search for approximate nearest neighbor in high dimensional spaces”  In _SIAM J. Comput._ 30.2, 2000, pp. 457–474  DOI: 10.1137/S0097539798347177
  * [49] Vincent Lafforgue  “Un renforcement de la propriété (T)”  In _Duke Math. J._ 143.3, 2008, pp. 559–602  DOI: 10.1215/00127094-2008-029
  * [50] Vincent Lafforgue  “Propriété (T) renforcée banachique et transformation de Fourier rapide”  In _J. Topol. Anal._ 1.3, 2009, pp. 191–206  DOI: 10.1142/S1793525309000163
  * [51] James R. Lee, Manor Mendel and Assaf Naor  “Metric structures in $L_{1}$: dimension, snowflakes, and average distortion”  In _European J. Combin._ 26.8, 2005, pp. 1180–1190  DOI: 10.1016/j.ejc.2004.07.002
  * [52] James R. Lee and Assaf Naor  “Embedding the diamond graph in $L_{p}$ and dimension reduction in $L_{1}$”  In _Geom. Funct. Anal._ 14.4, 2004, pp. 745–747  DOI: 10.1007/s00039-004-0473-8
  * [53] Nathan Linial, Eran London and Yuri Rabinovich  “The geometry of graphs and some of its algorithmic applications”  In _Combinatorica_ 15.2, 1995, pp. 215–245  DOI: 10.1007/BF01200757
  * [54] Jiří Matoušek  “Note on bi-Lipschitz embeddings into normed spaces”  In _Comment. Math. Univ. Carolin._ 33.1, 1992, pp. 51–55
  * [55] Jiří Matoušek  “On the distortion required for embedding finite metric spaces into normed spaces”  In _Israel J. Math._ 93, 1996, pp. 333–344  DOI: 10.1007/BF02761110
  * [56] Jiří Matoušek  “On embedding expanders into $l_{p}$ spaces”  In _Israel J. Math._ 102, 1997, pp. 189–197  DOI: 10.1007/BF02773799
  * [57] Jiří Matoušek  “Lectures on discrete geometry” 212, Graduate Texts in Mathematics  Springer-Verlag, New York, 2002, pp. xvi+481  DOI: 10.1007/978-1-4613-0039-7
  * [58] Bernard Maurey  “Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces $L^{p}$” With an English summary, Astérisque, No. 11  Société Mathématique de France, Paris, 1974, pp. ii+163
  * [59] Bernard Maurey  “Type, cotype and $K$-convexity”  In _Handbook of the geometry of Banach spaces, Vol. 2_ North-Holland, Amsterdam, 2003, pp. 1299–1332  DOI: 10.1016/S1874-5849(03)80037-2
  * [60] Stanisław Mazur  “Une remarque sur l’homéomorphie des champs fonctionnels”  In _Studia Math._ 1.1, 1929, pp. 83–85  URL: http://eudml.org/doc/216983
  * [61] Manor Mendel and Assaf Naor  “Metric cotype”  In _Ann. of Math. (2)_ 168.1, 2008, pp. 247–298  URL: https://doi.org/10.4007/annals.2008.168.247
  * [62] Manor Mendel and Assaf Naor  “Spectral calculus and Lipschitz extension for barycentric metric spaces”  In _Anal. Geom. Metr. Spaces_ 1, 2013, pp. 163–199  DOI: 10.2478/agms-2013-0003
  * [63] Manor Mendel and Assaf Naor  “Nonlinear spectral calculus and super-expanders”  In _Publ. Math. Inst. Hautes Études Sci._ 119, 2014, pp. 1–95  DOI: 10.1007/s10240-013-0053-2
  * [64] Manor Mendel and Assaf Naor  “Expanders with respect to Hadamard spaces and random graphs”  In _Duke Math. J._ 164.8, 2015, pp. 1471–1548  DOI: 10.1215/00127094-3119525
  * [65] Masato Mimura  “Sphere equivalence, Banach expanders, and extrapolation”  In _Int. Math. Res. Not. IMRN_ , 2015, pp. 4372–4391  DOI: 10.1093/imrn/rnu075
  * [66] Rajeev Motwani, Assaf Naor and Rina Panigrahy  “Lower bounds on locality sensitive hashing”  In _SIAM J. Discrete Math._ 21.4, 2007, pp. 930–935  DOI: 10.1137/050646858
  * [67] Assaf Naor  “An introduction to the Ribe program”  In _Jpn. J. Math._ 7.2, 2012, pp. 167–233  DOI: 10.1007/s11537-012-1222-7
  * [68] Assaf Naor  “Comparison of metric spectral gaps”  In _Anal. Geom. Metr. Spaces_ 2.1, 2014, pp. 1–52  DOI: 10.2478/agms-2014-0001
  * [69] Assaf Naor  “A spectral gap precludes low-dimensional embeddings”  In _33rd International Symposium on Computational Geometry_ 77, LIPIcs. Leibniz Int. Proc. Inform.  Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 50, 16
  * [70] Assaf Naor  “Metric dimension reduction: a snapshot of the Ribe program”  In _Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures_ World Sci. Publ., Hackensack, NJ, 2018, pp. 759–837
  * [71] Assaf Naor  “An average John theorem”  In _Geom. Topol._ 25.4, 2021, pp. 1631–1717  DOI: 10.2140/gt.2021.25.1631
  * [72] Assaf Naor, Yuval Peres, Oded Schramm and Scott Sheffield  “Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces”  In _Duke Math. J._ 134.1, 2006, pp. 165–197  DOI: 10.1215/S0012-7094-06-13415-4
  * [73] Assaf Naor and Lior Silberman  “Poincaré inequalities, embeddings, and wild groups”  In _Compos. Math._ 147.5, 2011, pp. 1546–1572  DOI: 10.1112/S0010437X11005343
  * [74] Huy L. Nguyễn  “Algorithms for High Dimensional Data” Thesis (Ph.D.)–Princeton University, 2014  URL: http://arks.princeton.edu/ark:/88435/dsp01b8515q61f
  * [75] Edward Odell and Thomas Schlumprecht  “The distortion problem”  In _Acta Math._ 173.2, 1994, pp. 259–281  DOI: 10.1007/BF02398436
  * [76] Ryan O’Donnell, Yi Wu and Yuan Zhou  “Optimal lower bounds for locality-sensitive hashing (except when $q$ is tiny)”  In _ACM Trans. Comput. Theory_ 6.1, 2014, pp. Art. 5, 13  DOI: 10.1145/2578221
  * [77] Mikhail I. Ostrovskii  “Metric embeddings” Bilipschitz and coarse embeddings into Banach spaces 49, De Gruyter Studies in Mathematics  De Gruyter, Berlin, 2013, pp. xii+372  DOI: 10.1515/9783110264012
  * [78] Narutaka Ozawa  “A note on non-amenability of $\mathcal{B}(l_{p})$ for $p=1,2$”  In _Internat. J. Math._ 15.6, 2004, pp. 557–565  DOI: 10.1142/S0129167X04002430
  * [79] Mark S. Pinsker  “On the complexity of a concentrator”  In _7th International Teletraffic Conference_ , 1973
  * [80] Gilles Pisier  “Martingales with values in uniformly convex spaces”  In _Israel J. Math._ 20.3-4, 1975, pp. 326–350  DOI: 10.1007/BF02760337
  * [81] Gilles Pisier  “Un exemple concernant la super-réflexivité”  In _Séminaire Maurey-Schwartz 1974–1975: Espaces $L^{p}$ applications radonifiantes et géométrie des espaces de Banach, Annexe No. 2_, 1975, pp. 12
  * [82] Gilles Pisier  “Complex interpolation between Hilbert, Banach and operator spaces”  In _Mem. Amer. Math. Soc._ 208.978, 2010, pp. vi+78  DOI: 10.1090/S0065-9266-10-00601-0
  * [83] Yuri Rabinovich  “On average distortion of embedding metrics into the line and into $l_{1}$”  In _Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing_ ACM, New York, 2003, pp. 456–462  DOI: 10.1145/780542.780609
  * [84] Omer Reingold, Salil Vadhan and Avi Wigderson  “Entropy waves, the zig-zag graph product, and new constant-degree expanders”  In _Ann. of Math. (2)_ 155.1, 2002, pp. 157–187  DOI: 10.2307/3062153
  * [85] Martin Ribe  “On uniformly homeomorphic normed spaces”  In _Ark. Mat._ 14.2, 1976, pp. 237–244  DOI: 10.1007/BF02385837
  * [86] Isaac J. Schoenberg  “Metric spaces and positive definite functions”  In _Trans. Amer. Math. Soc._ 44.3, 1938, pp. 522–536  DOI: 10.2307/1989894
  * [87] Mu-Tao Wang  “A fixed point theorem of discrete group actions on Riemannian manifolds”  In _J. Differential Geom._ 50.2, 1998, pp. 249–267  URL: http://projecteuclid.org/euclid.jdg/1214461170
  * [88] James H. Wells and Lynn R. Williams  “Embeddings and extensions in analysis”, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84  Springer-Verlag, New York-Heidelberg, 1975, pp. vii+108