Metric dimension reduction modulus for logarithmic distortion

Given parameters $n$ and $α$, the metric dimension reduction modulus $k^α_n(\ell_\infty)$ is defined as the smallest $k$ such that every $n$--point metric space can be embedded into some $k$-dimensional normed space $X$ with bi--Lipschitz distortion at most $α$. A fundamental task in the theory of metric embeddings is to obtain sharp asymptotics for $k^α_n(\ell_\infty)$ for all choices of $α$ and $n$, with the range $α=Θ(\log n)$ bearing special importance. While advances in the theory lead to the upper bound $k^α_n(\ell_\infty) = O(\log n)$ for $α=Θ(\log n)$, obtaining a matching lower bound has remained an open problem. We prove that $k^{β\log n}_n(\ell_\infty) = Ω(\log n)$ for every constant $β>0$, thereby closing the long--standing gap and resolving a question from the 2018 ICM plenary lecture of Naor.