Source
Johnson and Lindenstrauss (1984), LIT-1153, Contemporary Mathematics 26: 189–206, read in NOTE-930 from a scan of the published article. Filed for later use; it answers no question of the record’s yet.
What was actually shown
The quantity. L(X, n) is the smallest L such that every f from an n-point subset of X into ℓ₂ extends to all of X with ‖f̃‖_lip ≤ L‖f‖_lip. L(p, n) is L(L_p(0, 1), n). Log x means max(1, ln x).
Upper bound (Theorem 1). sup_{n≥2} (Log n)^(−1/2) L(∞, n) < ∞, so L(X, n) ≤ K√(Log n) for every metric space X. The proof takes the image A = f[M] ⊂ ℓ₂ and applies Lemma 1, the dimension reduction of THEORY-397, with τ = 1/2: a map g⁻¹ from A into ℓ₂ᵏ, k ≤ K log n, with ‖g⁻¹‖_lip ≤ 1 and ‖g‖_lip ≤ 3. It extends g by Kirszbraun’s theorem, passes to ℓ∞ᵏ by the identity (norm 1, inverse norm √k), extends there by the non-linear Hahn–Banach theorem, and composes back: ‖f̃‖_lip ≤ 3√k‖f‖_lip ≤ 3K√(log n)‖f‖_lip.
Lower bound (Theorem 3). There is δ > 0 such that for all n ≥ 2 and 1 ≤ p < 2, L(p, n) ≥ δ(Log n/Log Log n)^(1/p−1/2). Since L(∞, n) ≥ L(1, n), L(∞, n) ≥ δ(Log n/Log Log n)^(1/2). The proof uses Lemma 4: L_p contains subspaces E with d(E, ℓ₂ᴺ) ≤ 2 onto which every projection has norm at least δN^(1/p−1/2), with N = Log n/(2 Log Log n), and a linearization from Lindenstrauss (1964) with a smoothing lemma (Proposition 1, Lemma 5), which the reading followed only in outline.
What could have come out otherwise. An n-point subset of some metric space and a map into ℓ₂ with no extension of constant O(√(log n)) would refute Theorem 1. The proof of Theorem 1 was read in full; Proposition 1 and Lemma 5, used only for Theorem 3, were followed in outline.
What this does not say
- That √(log n) is sharp. The gap to the lower bound is (Log Log n)^(1/2), and the paper leaves sharpness open. It is still open in the record’s later reading: Lee and Naor (LIT-1152, NOTE-927, §1.4) say no known lower bound beats √(log n) for any target. Their C log n/log log n (THEORY-396) holds for every Banach target and is weaker than this bound for Hilbert space.
- Anything about targets other than Hilbert space, except through Theorem 3’s L_p subspaces and THEORY-398’s separated case.
- Anything about embedding the metric space itself. The paper’s Problems 3 and 4 ask about that and leave it open. Problem 4, distortion K√(log n) into ℓ₂, is answered in the negative by the record’s inference from Linial, London and Rabinovich (THEORY-394): every n-point metric embeds with distortion O(log n), and constant-degree expanders need Ω(log n). That paper cites neither Problem 4 nor this one; the inference is the record’s.
- Explicit constants. K is shown to exist; the steps are loose (Theorem 1’s last step needs K ≥ 1).
Connections
- THEORY-397: this account uses that one’s dimension reduction as its first step. The extension is the purpose the lemma was proved for.
- THEORY-398: the paper’s other extension theorem, for separated domains, where the constant depends on the ratio of diameter to separation and not on n.