A spectral gap precludes low-dimensional embeddings

We prove that there is a universal constant C>0 with the following property. Suppose that n∈ mathbbN and that mathsfA=(aij)∈ Mn(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of mathsfA by λ2(mathsfA). Then for it any finite-dimensional normed space (X,|·|) we have forall, x1,ldots,xn∈ X,qquad dim(X)≥ frac12 expleft(Cfrac1-λ2(mathsfA)√nbigg(fracsumi=1nsumj=1n|xi-xj|2sumi=1nsumj=1naij|xi-xj|2bigg)frac12right). This implies that if an n-vertex O(1)-expander embeds with average distortion D≥ 1 into X, then necessarily dim(X)gtrsim nc/D for some universal constant c>0, thus improving over the previously best-known estimate dim(X)gtrsim (log n)2/D2 of Linial, London and Rabinovich, strengthening a theorem of Matouvsek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.