A spectral gap precludes low-dimensional embeddings

We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (a_ij) ∈ M_n(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ₂(A). Then for any finite-dimensional normed space (X, ⊥ · ⊥) we have (Equation presented) It follows that if an n-vertex O(1)-expander embeds with average distortion D ≧ 1 into X, then necessarily dim(X) ≳ n^c/^D for some universal constant c > 0. This is sharp up to the value of the constant c, and it improves over the previously best-known estimate dim(X) ≳ (log n)²/D² of Linial, London and Rabinovich, strengthens a theorem of Matoušek, and answers a question of Andoni, Nikolov, Razenshteyn and Waingarten.