Metric dimension reduction modulus for superlogarithmic distortion

The metric dimension reduction modulus $k_n^{\alpha }({\mathrm{\ell }}_{\mathrm{\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 $\alpha$. Determining sharp asymptotics for $k_n^{\alpha }({\mathrm{\ell }}_{\mathrm{\infty }})$ is a fundamental task in metric geometry, with $\alpha =\mathrm{\Theta }(\log n)$ bearing particular interest. A line of advances over the past decades has led to an upper bound on $k_n^{\alpha }({\mathrm{\ell }}_{\mathrm{\infty }})$ for $\alpha =\mathrm{\Omega }(\log n)$, but a matching lower bound has remained open. We close this gap, establishing: for every fixed $\beta >0$, k^α_n(\ell_\infty) =Θ\bigg(\frac{\log n}{\log(\fracα{\log n}+1)}\bigg)\quad 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 $\alpha$–embedding into some $d$–dimensional normed space.