Metric dimension reduction modulus for superlogarithmic distortion

Abstract

The metric dimension reduction modulus $k^{\hat{I}}{\pm }_n({\ell }_{\infty })$ is the smallest $k$ such that every $n$--point metric space can be embedded into some $k$-dimensional normed space, with bi--Lipschitz distortion at most $\hat{I}\pm$. Determining sharp asymptotics for $k^{\hat{I}}{\pm }_n({\ell }_{\infty })$ is a fundamental task in metric geometry, with $\hat{I}\pm =\hat{I}˜(\log n)$ bearing particular interest. A line of advances over the past decades has led to an upper bound on $k^{\hat{I}}{\pm }_n({\ell }_{\infty })$ for $\hat{I}\pm =\hat{I}\text{c◯}(\log n)$, but a matching lower bound has remained open. We close this gap, establishing: for every fixed ${\hat{I}}^2>0$, $$ k^α_n(\ell_\infty) =Θ\bigg(\frac{\log n}{\log(\fracα{\log n}+1)}\bigg)\quad \mbox{for every $α\geq β\log n$}. $$ This resolves a question from Naor's 2018 ICM plenary lecture. Our result is obtained by characterizing the minimum dimension $d$ for which, with high probability, a random regular graph admits an $\hat{I}\pm$--embedding into some $d$--dimensional normed space.

Significant revision: our results now include the superlogarithmic distortion regime in addition to the logarithmic regime. The proof is also simplified