Euclidean Distortion of Negative-Type Metrics
Speaker: Kevin RenDate of Talk: October 9, 2026
Upstream link: Joint CalTech/UCLA Analysis Seminar
1. Setting
Recall the distortion of an embedding of a metric space:
Definition 1.
If \(f : X \to L_2\) for some metric space \((X, d)\), we say \(f\) has distortion \(D\) if there exists a constant \(s > 0\) such that
\[ s d(x, y) \leq \left\lVert f(x) - f(y) \right\rVert_2 <= sD d(x, y) \]for all \(x, y\in X\). \(c_2(X)\) is the minimal distortion among all embeddings \(f : X \to L_2\).
It is unclear what \(L_2\) is… Bourgain has a very celebrated theorem that says
Theorem 2. (Bourgain)
If \((X, d)\) is an \(n\)-point metric space, then \(c_2(X) = O \left( \log n \right)\).
This theorem has been presented before. Now Bourgain’s theorem is sharp: \(n\)-point expander graphs (what are these?) have distortions \(\Theta (\log n)\). The goal is to find conditions on \((X, d)\) under which Bourgain’s theorem can be improved.
2. Main Result?
Let us quickly describe what a negative-type metric is, along with another mystery condition that’s needed to state the main result.
Definition 3.
A function \(g : X \to L_2\) has a \((\beta , \gamma )\)-gap at scale \(\Delta > 0\) if \(d(x, y) \geq \Delta \) implies \(\left\lVert g(x) - g(y) \right\rVert_2 \geq \Delta \) and \(d(x, y) \leq \beta \Delta \) implies \(\left\lVert g(x) - g(y) \right\rVert_2 \leq \gamma \Delta \).
Definition 4.
\((X, d)\) is a negative-type metric if there exists \(g : X \to L_2\) such that \(d(x, y) = \left\lVert g(x) - g(y) \right\rVert_2^2\) for all \(x, y\).
Theorem 5.
Suppose \((X, d)\) is a negative-type metric and there exists a map \(g : X\to L_2\) with a \((\beta , \gamma )\)-gap at scale \(\Delta \). Then, there exists \(f : X \to L_2\) Lipschitz with
\[ \left\lVert f(x) - f(y) \right\rVert_2 \geq \frac{\beta \Delta }{\sqrt{\log n}} \]whenever \(d(x, y) \in [\Delta , 2 \Delta ]\).
This morally says that \(f\) has distortion \(\frac{1}{\beta }\sqrt{\log n}\), but only for points separated at a specific scale. Perhaps there’s an easy way to glue these together?
Most importantly for me, though, something I would like to understand is: consider Bourgain’s proof of his theorem. The insight was to sample functions of the form \(\operatorname{dist}(x, S)\), where \(S\subseteq X\), with a scale-sensitive weight on different \(S\)’s. Expander graphs must have some structure that makes this argument sharp; on the other hand there must be some feature of this proof that uses the lack of this structure (somehow) to get an improved distortion bound. So how does the “gap” structure and/or “negative-type” assumption helpful from this perspective? Or are they taking a different approach altogether?
(There is something said about projections and using the inner product structure that I don’t recall from Bourgain’s proof, for what it’s worth…)
3. Open Question(s)
It is known that \(L_p\) is negative type for \(1 \leq p\leq 2\), hence the speaker’s result gives an \(O \left( \sqrt{\log n} \right)\) distortion for any \(n\)-point subset of \(L_p\). When \(p = 1\) specifically, taking a Hamming cube saturates this upper bound. However, as \(p\) varies, the same construction only gives a lower bound of \(\Omega \left( (\log n) ^{\frac{1}{p}-\frac{1}{2}} \right)\).
Question 6.
Can the upper bound be improved for \(n\)-point subests of \(L_p\), \(1 < p \leq 2\), or is there a better extremising example for these spaces?