Compact counterexamples to bi-Lipschitz dimension reduction

The explanation

Start with one point. Push copies of it one step away, each along its own direction. Make every direction perpendicular to all the others. Any two pushed points are then √2, about 1.414, apart. Hilbert space is a setting with endless perpendicular directions. So you can make as many pushed points as you like. Now try to copy the picture onto a flat sheet. Distances may stretch by up to a factor of 2, but they may never shrink.

Each copy must then sit within 2 of the starting point's copy. The copies must also stay more than 1 apart. Give each copy a small disk of radius 1/2. These disks cannot overlap, and all of them fit inside one disk of radius 2.5. That big disk has 25 times the area of a small one. So at most 25 pushed points can be copied. With 26, the copy must fail.

That bunch of points has a feature a simple test can measure. A set is called doubling if a fixed number of half-radius balls can cover any ball in it. The smaller balls must be centred on points of the set. The bunch fails this test. A ball of radius 1.5 around the starting point holds every point. A ball of radius 0.75 centred on any one point catches only that point. So 26 pushed points need 27 half-size balls, and more points need more. By contrast, every set inside a flat space of finitely many dimensions passes the test.

That last fact invites a reverse question. Lang and Plaut asked it in a paper published in 2001. Take a set in Hilbert space that passes the doubling test. Can it always be copied into some flat space of finitely many dimensions? The copy may use any number of dimensions. Distances may stretch by any fixed factor, called the distortion, but never shrink below a fixed scale. Such a copy is called a bi-Lipschitz embedding. Gupta, Krauthgamer and Lee asked the same question independently, in a 2003 paper on algorithms.

Partial answers came first. In 1983, Assouad showed that the answer is yes after a change of rules. Every doubling set can be copied once each distance is raised to a power below 1, like a square root. This trick is called snowflaking. For some other ways of measuring distance, the answer was no. Lafforgue and Naor in 2014, and Bartal, Gottlieb and Neiman in 2015, built doubling sets that cannot be copied. Their sets live in spaces called L_p and ℓ_p, with p greater than 2. Hilbert space is the case p = 2, and it stayed open. Schioppa announced a negative answer in 2017. He withdrew it after reporting a possible issue in its argument.

The obstacle is that the opening bunch is exactly what doubling forbids. A counterexample must hold many perpendicular directions without ever crowding them into one ball. The paper spreads them across a plane. It cuts the plane into rows and columns at sizes 1/1000, 1/1000², and so on. Each row and column gets a colour, repeating in a fixed cycleSource 1. A point in a row or column of some colour may be pushed off the plane. The push has the size of that level and points in that colour's own direction. Near any point, at any radius, only a few colours are in reach. The paper counts fewer than 300 choices thereSource 2. That gives a doubling constant of at most 300 × 16², which is 76,800Source 3. The set is fixed before any attempted copy is consideredSource 4.

Now suppose someone offers a copy into k dimensions with distortion D. The proof picks more colours than (1 + 2D)^k. For a flat sheet and a stretch of 2, that bound is 5², which is 25, so 26 colours. Where a row of one colour crosses a column of another, both pushes are allowedSource 5. The two pushed points are √2 times the level size apart. Calculus then shows the copy barely bends along suitable rows and columns. After rescaling, this yields one point per colour, all within D of a centre and more than 1 apart. That is the opening area count, now in k dimensions. It allows at most (1 + 2D)^k such points, so no copy existsSource 6. This works for every finite k and D.

So the answer to the question of Lang and Plaut is no. A bound on crowding alone cannot guarantee a faithful copy in finitely many dimensionsSource 7. The set built here is unbounded, since it contains a whole plane. A second result fixes that. Every infinite-dimensional Banach space contains a compact set with the same failureSource 8. A Banach space is a complete space where vectors have lengths. Compact means, roughly, that every endless sequence in the set has points bunching toward a limit in the set. Their doubling bound does not depend on the spaceSource 9. It is far larger, though: 1 + 6 × 76,800⁸. The same Hilbert set also sits exactly inside L_p for every finite p of at least 1Source 10. That settles a case Lafforgue and Naor had left open, p between 1 and 2Source 11.

How sure is this? A computer proof checker called Lean has a formal version of two statements. One is the Hilbert set with doubling constant at most 76,800 and no finite-dimensional copy at any finite distortion. The other is the compact Banach-space version with one universal doubling constant. The L_p consequence is not in the Lean scope note. No specialists have published a review yet.

What it doesn't show. This does not rule out copies after snowflaking, where Assouad's 1983 theorem still gives a yes.