Comparison of metric spectral gaps

Abstract

Let $A=(a_{ij})\in M_n(\R)$ be an $n$ by $n$ symmetric stochastic matrix. For $p\in [1,\infty)$ and a metric space $(X,d_X)$, let $γ(A,d_X^p)$ be the infimum over those $γ\in (0,\infty]$ for which every $x_1,...,x_n\in X$ satisfy $$ \frac{1}{n^2} \sum_{i=1}^n\sum_{j=1}^n d_X(x_i,x_j)^p\le \fracγ{n}\sum_{i=1}^n\sum_{j=1}^n a_{ij} d_X(x_i,x_j)^p. $$ Thus $γ(A,d_X^p)$ measures the magnitude of the {\em nonlinear spectral gap} of the matrix $A$ with respect to the kernel $d_X^p:X\times X\to [0,\infty)$. We study pairs of metric spaces $(X,d_X)$ and $(Y,d_Y)$ for which there exists $Ψ:(0,\infty)\to (0,\infty)$ such that $γ(A,d_X^p)\le Ψ(γ(A,d_Y^p))$ for every symmetric stochastic $A\in M_n(\R)$ with $γ(A,d_Y^p)<\infty$. When $Ψ$ is linear a complete geometric characterization is obtained. Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if $n\in \N$ and $p\in (2,\infty)$ then for every $f_1,...,f_n\in L_p$ there exist $x_1,...,x_n\in L_2$ such that {equation}\label{eq:p factor} \forall\, i,j\in \{1,...,n\},\quad \|x_i-x_j\|_2\lesssim p\|f_i-f_j\|_p, {equation} and $$ \sum_{i=1}^n\sum_{j=1}^n \|x_i-x_j\|_2^2=\sum_{i=1}^n\sum_{j=1}^n \|f_i-f_j\|_p^2. $$ This statement is impossible for $p\in [1,2)$, and the asymptotic dependence on $p$ in \eqref{eq:p factor} is sharp. We also obtain the best known lower bound on the $L_p$ distortion of Ramanujan graphs, improving over the work of Matoušek. Links to Bourgain--Milman--Wolfson type and a conjectural nonlinear Maurey--Pisier theorem are studied.

Clarifying remarks added, definition of p(n,d) modified, typos fixed, references added