Doubling is not enough?

0:00Doubling, and finitely many coordinates

A set of points is doubling if every ball in it can be covered by a fixed number of balls of half the radius. Every subset of a finite-dimensional Euclidean space is doubling, so being doubling is necessary for fitting into finitely many coordinates. Is it enough? A bi-Lipschitz embedding sends the points into some ℝᵏ and keeps every distance within a fixed factor D, after one rescaling. Lang and Plaut asked whether every doubling subset of Hilbert space has such an embedding into some finite-dimensional Euclidean space. Gupta, Krauthgamer and Lee asked the same question, for dimension reduction in algorithms. There were positive results after changing the distance. Assouad’s theorem embeds every doubling space once each distance is raised to a power below one, a snowflake. Naor and Neiman showed that, for powers close to one, the dimension can be bounded by the doubling constant alone, though the distortion still depends on the power. On the negative side, Lafforgue and Naor built doubling subsets of Lₚ, for p > 2, with no embedding into any finite-dimensional Euclidean space. Independently, Bartal, Gottlieb and Neiman found obstructions in the sequence spaces ℓₚ, for p > 2, and later Baudier, Święcicki and Swift gave an elementary proof. The Hilbert case stayed open. Schioppa announced a negative answer, but withdrew the preprint after reporting a possible issue. In our miniature of the construction, base points sit on a grid, and each point can rise by 1 unit in the direction of its horizontal strip’s color, or of its vertical strip’s color. We covered balls by balls of half the radius, at many centers and radii. The worst count stayed at 29 or 30, whether there were 5, 20 or 80 colors, although 80 colors use 80 separate directions. This is one level, and these are the worst counts we found, not a proof: a ball meets only a few strips, so it sees only a few colors, however many there are in total.

2:06The claims

Result 098 is one OpenAI preprint, 13 pages, dated September 25. It claims a fixed subset of Hilbert space, with doubling constant at most 76,800, that admits no bi-Lipschitz embedding into any finite-dimensional Euclidean space, at any finite distortion. That answers the Lang–Plaut question negatively. Hilbert space itself sits isometrically inside the function spaces Lₚ, for every finite p, so the same set lives there too; the paper says this answers Lafforgue and Naor’s question for p between 1 and 2, for those function spaces. And every infinite-dimensional real Banach space contains a compact doubling set, with one universal doubling bound, that admits no such embedding into any finite-dimensional normed space. The proof is by contradiction and compactness, so it is qualitative: it does not say how large a finite piece must be before it stops embedding. The Banach-space version places finite pieces of the set into the space with Dvoretzky’s theorem, and assembles them into a shrinking compact union. OpenAI published a Lean formalization of both the Hilbert theorem and the compact Banach theorem, 28 files and about 4,700 lines, matched against separate statements. In place of Dvoretzky’s theorem, the Lean files use the special shape of the set, placing finite pieces within a factor of 6 either way through an Auerbach-type system of vectors. We have not run the check.

3:39How the proof goes

The set lives over a base plane. At scale rⱼ = 1000⁻ʲ, horizontal strips of width rⱼ and vertical strips of width Wⱼ rⱼ are colored periodically with Nⱼ colors, and every pair of N and W recurs infinitely often. Each color at each level gets its own unit direction, perpendicular to everything else. A point of the plane may rise by rⱼ in the direction of one of its strips’ colors, at most one color per level, and at finitely many levels. Because the scales shrink a thousandfold, a ball of any radius sees fixed coarse coordinates, tiny fine ones, and at most one level in between, with fewer than 300 choices. Cutting the ball’s shadow on the plane into 256 small squares, and multiplying, gives the bound of 76,800. Now suppose an embedding into ℝᵏ with distortion D exists. Fixing the lifts and moving the base point gives a Lipschitz map on part of the plane, called a sheet. Its derivative has a horizontal and a vertical column. Over all sheets, take the largest possible squared length A of the horizontal column, and then the largest vertical B allowed alongside it. Near this extremal pair, an average derivative close to a reference value forces small mean-square variation, along the long rows and along the columns. Choose the number of colors N larger than the number of points, pairwise more than 1 apart, that fit in a ball of radius D in ℝᵏ, which is at most (1 + 2D)ᵏ. Use a level with N colors and vertical strips n times wider than the rows, inside a tiny square of a nearly extremal sheet. Along one long row and one column of each color, each lifted sheet differs from the base sheet by an offset that, measured in units of r, is nearly constant. Where a row of color i crosses a column of color m, both lifts are allowed, and the two lifted points are √2 r apart. Carrying the offsets along each row and column, to where every color’s row meets its own column, gives N points in a ball of radius D, pairwise more than 1 apart. That is too many, so no embedding exists.

6:00Where it stands

The preprint is not peer reviewed and has not been revised. OpenAI’s Lean formalization covers the Hilbert theorem with the explicit doubling bound, and the compact Banach theorem with a universal one; we have not run it. It is not among the papers OSVerify reviewed, and we have seen no expert review. If it holds, doubling is not enough. Bounded covering complexity alone does not guarantee that a subset of Hilbert space fits into finitely many coordinates at any finite distortion, even when the set is compact. Its snowflakes still embed, by Assouad’s theorem.