Why You Can't Beat Johnson–Lindenstrauss

The Johnson–Lindenstrauss lemma promises you can crush $n$ points into $m = O(\log n / \varepsilon^2)$ dimensions while preserving all pairwise distances to within a factor of $1 \pm \varepsilon$. That was 1984. For the next thirty‑three years the natural question hung open: is that logarithm‑over‑epsilon‑squared the truth, or an artefact of our proofs? Larsen and Nelson closed it in 2017. This post is about their lower bound and the coding argument that carries it.

Recap: what the upper bound says

Take $n$ points $x_1, \dots, x_n$ in $\mathbb{R}^d$ and any $\varepsilon \in (0, 1/2)$. Johnson and Lindenstrauss proved there is a linear map $f: \mathbb{R}^d \to \mathbb{R}^m$ with

such that for every pair $i, j$,

Here $n$ is the number of input points, $d$ is the ambient dimension you started in, $\varepsilon$ is the multiplicative distortion you will tolerate, and $m$ is the target dimension. In words: pick $m$ that grows like the logarithm of the number of points divided by the square of the accuracy you want, and there exists an embedding into $\mathbb{R}^m$ that stretches or shrinks every pairwise distance by at most $\varepsilon$. The remarkable thing is that $m$ does not depend on $d$ at all.

Standard constructions are random. Take $A \in \mathbb{R}^{m \times d}$ with i.i.d. $\mathcal{N}(0, 1/m)$ entries and set $f(x) = Ax$; the proof is a concentration bound for $\|Ax\|^2$ followed by a union bound over the $\binom{n}{2}$ pairs. The obvious question is whether we could do with $m$ smaller. Alon (2003) gave a partial answer — no better than $\Omega(\log n / (\varepsilon^2 \log(1/\varepsilon)))$ — leaving a stubborn $\log(1/\varepsilon)$ gap. Larsen and Nelson closed it.

What "tight" actually means

There are two flavours of lower bound one might hope for.

Distributional. No distribution over linear maps $\mathbb{R}^d \to \mathbb{R}^m$ can preserve the norm of a fixed vector to within $1 \pm \varepsilon$ with failure probability $\delta$ unless $m = \Omega(\varepsilon^{-2}\log(1/\delta))$. This is a lower bound on the tool — Distributional JL — and was settled by Jayram–Woodruff (2013) and independently Kane–Meka–Nelson (2011).

Existential. There exists a set of $n$ points such that any embedding into fewer than $m$ dimensions distorts some pairwise distance by more than $\varepsilon$. This is a lower bound on the JL lemma itself, and it does not immediately follow from the distributional one. A clever non‑oblivious embedding — one that inspects the point set before deciding what to do — might, in principle, beat the union‑bound construction.

Larsen and Nelson ruled that out.

The theorem

Theorem (Larsen–Nelson, 2017). For every $n \ge 2$, every $\varepsilon$ in the range $\log^{0.5001} n / \sqrt{n} < \varepsilon < 1$, and every $d \ge C\log n / \varepsilon^2$, there exists a set $X \subset \mathbb{R}^d$ of $n$ points such that any map $f: X \to \mathbb{R}^m$ preserving all pairwise Euclidean distances up to a factor of $1 \pm \varepsilon$ satisfies

Read that carefully. The map $f$ is arbitrary — not required to be linear, not required to be oblivious to the point set. The hard point set exists for every $\varepsilon$ in the stated range. And the dimension you land in must grow at the JL rate. So the JL upper bound is optimal up to a constant. This is the strongest form of "JL is tight" one could reasonably ask for.

The load‑bearing step, sketched honestly

I will sketch the shape of the argument; the full proof is a delicate exercise in metric entropy and I will be explicit about which steps I am gesturing at rather than proving.

The proof exhibits a specific hard set: $n$ nearly‑orthogonal unit vectors $u_1, \dots, u_n$ arising as the columns of a matrix with well‑controlled restricted‑isometry behaviour. An embedding $f$ preserving pairwise distances up to $1 \pm \varepsilon$ becomes, after centring, an approximate isometry: the images $y_i = f(u_i)$ satisfy $\|y_i\|^2 \approx 1$ and $\langle y_i, y_j\rangle \approx \langle u_i, u_j\rangle$ for all $i, j$.

Now the pivot. Discretize $\mathbb{R}^m$ into a grid at scale $\Theta(\varepsilon / \sqrt{m})$. Each $y_i$ falls into some grid cell; the entire point set becomes an encoding — a string of

The step that does the work: one shows this encoding is rich enough to recover approximate inner products with exponentially many query directions. This is a kind of chaining argument on Gaussian processes; the tools are Sudakov minoration — which lower‑bounds the Gaussian process's expected supremum via the packing number and thereby forces the entropy (code length) up — and Talagrand's generic chaining, which sharpens that entropy estimate by summing the covering contributions across all scales rather than settling for a single one. From the recovery property, one reads off an information‑theoretic lower bound on the encoding length. Note that $\log(\sqrt{m}/\varepsilon) = \log(1/\varepsilon) + \tfrac{1}{2}\log m$, and in the regime of interest the $\tfrac{1}{2}\log m$ term is absorbed into $\log(C/\varepsilon)$. Working it through gives

hence $m \ge \Omega(\log n / (\varepsilon^2 \log(1/\varepsilon)))$. That is Alon's bound. The extra $\log(1/\varepsilon)$ factor that Larsen and Nelson recover comes from replacing the flat grid with a scale‑sensitive net that tracks the $\varepsilon$‑precision along a hierarchy of scales — the technical heart of their paper, and the step I am not going to reproduce here.

What I want to flag clearly: the pivot is the encoding move. Everything else is bookkeeping around it. If you strip the argument to one sentence, it is "a $(1\pm\varepsilon)$‑preserving embedding into $\mathbb{R}^m$ is a bit‑efficient code for the input geometry, and the input geometry can be chosen to be information‑theoretically incompressible."

Why an encoding argument?

Here is the picture I keep in my head. A JL map is a compressor. If it uses $m$ dimensions and $b$ bits of precision per coordinate, it is a code of length $mb$ bits. If that code is any good at preserving inner products, it must distinguish among all the pairs and triples the input can produce. Larsen–Nelson build an input for which the number of geometrically distinguishable configurations is exponentially large — so the code length is forced to be at least $\log$ of that number. Bits in, bits out.

That is why the lower bound is called "optimality of JL and not merely of DJL." DJL bounds live in the world of what a fixed randomized construction can do to a single vector. Larsen–Nelson lives in the world of what any encoder can do to a fixed adversarial dataset. The stronger statement is stronger for a reason.

What is proved, sketched, and open

Let me be explicit, because it matters.

Proved. The upper bound $m = O(\log n / \varepsilon^2)$. The distributional lower bound $m = \Omega(\varepsilon^{-2} \log(1/\delta))$ for DJL (Jayram–Woodruff 2013, Kane–Meka–Nelson 2011). The existential lower bound $m = \Omega(\log n / \varepsilon^2)$ for the JL lemma itself in the regime $\varepsilon \ge \log^{0.5001} n / \sqrt{n}$ (Larsen–Nelson, 2017). The ultra‑small‑$\varepsilon$ regime (Alon–Klartag, 2017), which uses a different technique.

Sketched here, proved there. The chaining and scale‑sensitive net that recover the missing $\log(1/\varepsilon)$ factor. I gave you the shape; the paper has the geometry.

Open. The exact constant in front of $\log n / \varepsilon^2$. Upper and lower bounds match to constants but the sharp constant is unknown. A deterministic polynomial‑time construction of an adversarial point set attaining the Larsen–Nelson bound — the current proofs are existential.

Where the tightness fails, and why that is good news

Two caveats worth internalizing.

Structured inputs beat the bound. JL is tight in the worst case over $n$ points. If your data has low doubling dimension, or is sparse, or lives on a low‑dimensional manifold in $\mathbb{R}^d$, you can do better. The restricted isometry property in compressed sensing (Candès–Tao, Donoho, 2006) and doubling‑dimension embeddings exploit exactly this loophole. (Terminal embeddings (Mahabadi–Makarychev–Makarychev–Razenshteyn, 2018) are a different animal: they don't lower $m$ at all, but extend the $1 \pm \varepsilon$ guarantee to all of $\mathbb{R}^d$ rather than just the $n$ points, at the same target dimension.) The right reading of Larsen–Nelson is not "you can't do better" but "you can't do better without exploiting structure of the input."

Non‑Euclidean geometries can be different. The Larsen–Nelson result is specific to $\ell_2$. Analogous questions in $\ell_1$ and other norms have their own answers, some tight and some open.

But for the raw problem — $n$ arbitrary points, Euclidean distance, multiplicative distortion $1 \pm \varepsilon$ — the story is closed. The Gaussian projection you learned in your first pass through the lemma is not merely a nice construction. It is, up to constants, an optimal one — though it is the target dimension, not the Gaussianity, that is tight: Achlioptas (2003) showed $\pm 1$ entries achieve the same rate, and sparse‑JL constructions do too. What Larsen–Nelson pins down is the $m$, not the distribution you sample to reach it.