OctoInformBeta

OpenAI preprint, September 2026 · §5. Crossings force a packing contradiction (proof of Theorem 1)

One period block, selected lines and separated vectors: Small energy on a period block, and separation of lines of different colors at crossings

No bi-Lipschitz embedding of the constructed set into Euclidean space.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Let EE be a finite-dimensional real inner product space. The question is whether the constructed set SS, a subset of the Hilbert space ℓ2\ell^2 of square-summable real sequences, admits a bi-Lipschitz embedding into EE. The statements of this page compare the restrictions of a map f:S→Ef\colon S \to E to the sheets of SS, its planar pieces over subsets of the base plane, over one period block of a level, a rectangle of the base plane, and at the points where strips of two colors of that level cross.

The Constructed Set

The base plane ℝ2\mathbb{R}^2 of points p=(x,y)p = (x, y), with xx the horizontal and yy the vertical coordinate, carries the sup distance max⁡(|x−x′|,|y−y′|)\max(|x - x'|, |y - y'|) between pp and p′=(x′,y′)p' = (x', y').✦ The base vector of pp is xe0+ye1∈ℓ2x e_0 + y e_1 \in \ell^2, where e0e_0 and e1e_1 are the first two unit vectors.✦

Level j≥0j \ge 0 has the scale rj=1000−(j+1)r_j = 1000^{-(j+1)}, a number of colors NjN_j and a width factor WjW_j. The numbers NjN_j and WjW_j are positive integers read off from jj: if π:ℕ→ℕ×ℕ\pi\colon \mathbb{N} \to \mathbb{N} \times \mathbb{N} is the inverse of the standard pairing bijection of ℕ×ℕ\mathbb{N} \times \mathbb{N} onto ℕ\mathbb{N}, π(j)=(j′,j″)\pi(j) = (j', j'') and π(j′)=(λ,λ′)\pi(j') = (\lambda, \lambda'), then Nj=λ+1N_j = \lambda + 1 and Wj=λ′+1W_j = \lambda' + 1.✦ The horizontal strips of level jj are the sets qrj<y<(q+1)rjq r_j < y < (q+1) r_j, the vertical strips, of width WjrjW_j r_j, are the sets qWjrj<x<(q+1)Wjrjq W_j r_j < x < (q+1) W_j r_j, for q∈ℤq \in \mathbb{Z}, and the strip of index qq has color qmod⁡Njq \bmod N_j.✦ For a color i<Nji < N_j, the union of the strips of color ii of both kinds is Uj,i={(x,y):qrj<y<(q+1)rj or q′Wjrj<x<(q′+1)Wjrj for some q,q′∈i+Njℤ}.U_{j,i} = \{(x, y) : q r_j < y < (q+1) r_j \text{ or } q' W_j r_j < x < (q'+1) W_j r_j \text{ for some } q, q' \in i + N_j \mathbb{Z}\}.(1)✦ Each level jj and color ii also have a unit vector ej,ie_{j,i} of the standard basis of ℓ2\ell^2, orthogonal to e0e_0, to e1e_1 and to all the others.

A tuple w=(wj)j≥0w = (w_j)_{j \ge 0} is a sequence of finite support, each entry wjw_j being 00 or a displacement rjej,ir_j e_{j,i} of a color i<Nji < N_j.✦ A tuple ww is admissible at a point pp of the base plane when p∈Uj,ip \in U_{j,i} at every level jj with wj=rjej,iw_j = r_j e_{j,i}.✦ The sheet domain Ωw\Omega_w of a tuple ww is the set of points of the base plane at which ww is admissible.✦ The point (p,w)(p, w) is the vector xe0+ye1+∑jwjx e_0 + y e_1 + \sum_j w_j of ℓ2\ell^2✦, and the constructed set is S={(p,w):p∈ℝ2 and w a tuple admissible at p},S = \{(p, w) : p \in \mathbb{R}^2 \text{ and } w \text{ a tuple admissible at } p\},(2)✦ with the distance dd of ℓ2\ell^2.

Period Blocks

A segment II of the real line is a bounded interval with endpoints α<β\alpha < \beta.✦ The length of a segment II with endpoints α<β\alpha < \beta is |I|=β−α|I| = \beta - \alpha, and the uniform law of II is the probability measure obtained by restricting Lebesgue measure to (α,β](\alpha, \beta] and dividing by |I||I|. A rectangle Q=I×JQ = I \times J of the base plane is the product of two segments, its horizontal side II and its vertical side JJ.✦ The closed rectangle of a rectangle Q=I×JQ = I \times J is the product of the closed intervals II and JJ, the uniform law μQ\mu_Q of QQ is the product of the uniform laws of II and JJ, and the mean of a function hh on the base plane over QQ is ⟨h⟩Q=∫hdμQ\langle h \rangle_Q = \int h \, d\mu_Q.

A period block of level jj is a rectangle of the base plane, determined by a pair (u,v)(u, v) of integers.✦ The rectangle Q=I×JQ = I \times J of the period block (u,v)(u, v) of level jj spans one horizontal period NjWjrjN_j W_j r_j of the vertical strips and one vertical period NjrjN_j r_j of the horizontal strips.✦ For a color i<Nji < N_j, the column IiI_i and the row JiJ_i of color ii of the block are the closed intervals of xx and of yy over which the vertical and the horizontal strip of color ii cross the block: I=[uNjWjrj,(u+1)NjWjrj],Ii=[(uNj+i)Wjrj,(uNj+i+1)Wjrj],I = [u N_j W_j r_j,\ (u+1) N_j W_j r_j], \qquad I_i = [(u N_j + i) W_j r_j,\ (u N_j + i + 1) W_j r_j],(3)✦ J=[vNjrj,(v+1)Njrj],Ji=[(vNj+i)rj,(vNj+i+1)rj].J = [v N_j r_j,\ (v+1) N_j r_j], \qquad J_i = [(v N_j + i) r_j,\ (v N_j + i + 1) r_j].(4)✦

Sheets and Their Energy

Let ff be a map from SS to EE. The sheet of a tuple ww is the map Fw(p)=f(p,w)F_w(p) = f(p, w) from Ωw\Omega_w to EE.✦ When ff is Lipschitz, the global sheet F‾w\bar{F}_w of ww is a fixed Lipschitz map from the whole base plane to EE that agrees with FwF_w on Ωw\Omega_w.✦ The derivative columns Gx(p)G_x(p) and Gy(p)G_y(p) of a map GG from the base plane to EE are its derivative at pp applied to (1,0)(1, 0) and to (0,1)(0, 1).✦

Fix a tuple ww and a level jj, and write F=F‾wF = \bar{F}_w. For a color i<Nji < N_j, the tuple w(i)w^{(i)} agrees with ww off level jj and has the displacement rjej,ir_j e_{j,i} at level jj, and Fi=F‾w(i)F_i = \bar{F}_{w^{(i)}}.✦ The colors of the horizontal and the vertical strip of level jj at a point p=(x,y)p = (x, y) are cH(p)=⌊y/rj⌋mod⁡Njc_H(p) = \lfloor y / r_j \rfloor \bmod N_j and cV(p)=⌊x/(Wjrj)⌋mod⁡Njc_V(p) = \lfloor x / (W_j r_j) \rfloor \bmod N_j✦, and the selected columns are GHx(p)=(FcH(p))x(p)G_H^x(p) = (F_{c_H(p)})_x(p)✦ and GVy(p)=(FcV(p))y(p)G_V^y(p) = (F_{c_V(p)})_y(p).✦ For a point pp, the combined energy ℰ(p)\mathcal{E}(p) of ww and jj is the horizontal energy, the squared norm of GHx(p)−Fx(p)G_H^x(p) - F_x(p), weighted by Wj2W_j^2, plus the vertical energy, the squared norm of GVy(p)−Fy(p)G_V^y(p) - F_y(p): ℰ(p)=Wj2∥GHx(p)−Fx(p)∥2+∥GVy(p)−Fy(p)∥2.\mathcal{E}(p) = W_j^2 \, \|G_H^x(p) - F_x(p)\|^2 + \|G_V^y(p) - F_y(p)\|^2.(5)✦

The Claim

Theorem 1. Let EE be a finite-dimensional real inner product space and D≥0D \ge 0.

  1. If f:S→Ef\colon S \to E is DD-Lipschitz, then for every integer N≥1N \ge 1 and every η>0\eta > 0 there are a tuple ww, a level jj with Nj=NN_j = N and wj=0w_j = 0, and a period block of level jj whose closed rectangle QQ lies in Ωw\Omega_w, such that the combined energy ℰ\mathcal{E} of ww and jj satisfies ⟨ℰ⟩Q<η.\langle \mathcal{E} \rangle_Q < \eta.(6)✦

  2. If f:S→Ef\colon S \to E is DD-Lipschitz, ww is a tuple, jj a level, i<Nji < N_j a color and Q=I×JQ = I \times J the rectangle of a period block of level jj, with column IiI_i and row JiJ_i of color ii, then there is a height yy in the interior of JiJ_i with Wj2∥(Fi−F)(t,y)−(Fi−F)(s,y)∥2≤|I|2Nj⟨ℰ⟩Qfor all s,t∈I,W_j^2 \, \|(F_i - F)(t, y) - (F_i - F)(s, y)\|^2 \le |I|^2 N_j \langle \mathcal{E} \rangle_Q \quad \text{for all } s, t \in I,(7)✦ and an abscissa xx in the interior of IiI_i with ∥(Fi−F)(x,t)−(Fi−F)(x,s)∥2≤|J|2Nj⟨ℰ⟩Qfor all s,t∈J.\|(F_i - F)(x, t) - (F_i - F)(x, s)\|^2 \le |J|^2 N_j \langle \mathcal{E} \rangle_Q \quad \text{for all } s, t \in J.(8)✦

  3. If f:S→Ef\colon S \to E is DD-Lipschitz with d(z,z′)≤∥f(z)−f(z′)∥d(z, z') \le \|f(z) - f(z')\| for all z,z′∈Sz, z' \in S, ww is a tuple and jj a level with wj=0w_j = 0, and i≠mi \ne m are colors of level jj, then at every point pp of Ωw∩Uj,i∩Uj,m\Omega_w \cap U_{j,i} \cap U_{j,m} ∥Fi(p)−Fm(p)∥2≥2rj2.\|F_i(p) - F_m(p)\|^2 \ge 2 r_j^2.(9)✦

  4. If ff is as in (c) and N≥1N \ge 1 is an integer, there are points z0,…,zN−1z_0, \dots, z_{N-1} of EE with ∥zl∥≤D\|z_l\| \le D for every ll and ∥zl−zl′∥≥1for l≠l′.\|z_l - z_{l'}\| \ge 1 \quad \text{for } l \ne l'.(10)✦

  5. If YY is a compact subset of a pseudometric space XX and ρ>0\rho > 0, there is an integer MM such that n≤Mwhenever ξ1,…,ξn∈Y and d(ξl,ξl′)≥ρ for l≠l′.n \le M \quad \text{whenever } \xi_1, \dots, \xi_n \in Y \text{ and } d(\xi_l, \xi_{l'}) \ge \rho \text{ for } l \ne l'.(11)✦

  6. There is no map f:S→Ef\colon S \to E with d(z,z′)≤∥f(z)−f(z′)∥≤Dd(z,z′)for all z,z′∈S.d(z, z') \le \|f(z) - f(z')\| \le D \, d(z, z') \quad \text{for all } z, z' \in S.(12)✦

  7. If a>0a > 0 and D≥1D \ge 1, there is no map f:S→Ef\colon S \to E with ad(z,z′)≤∥f(z)−f(z′)∥≤Dad(z,z′)for all z,z′∈S.a \, d(z, z') \le \|f(z) - f(z')\| \le D a \, d(z, z') \quad \text{for all } z, z' \in S.(13)✦

In the paper, the result reads: transport along the selected lines, the lines at the heights yy and abscissas xx chosen in (b), gives NN points in the ball of radius DD of ℝk\mathbb{R}^k, where kk is the dimension of EE and ℝk\mathbb{R}^k stands for EE, with pairwise distances greater than 11, contradicting N>(1+2D)kN > (1 + 2D)^k by volume comparison.

What Is Checked

The claim is stated over the constructed set SS of (2) with the distance of ℓ2\ell^2, and over maps ff from SS to a finite-dimensional real inner product space EE with ∥f(z)−f(z′)∥\|f(z) - f(z')\| at most a multiple of d(z,z′)d(z, z') and, in (c), (d), (f) and (g), at least a multiple of it; over the global sheets and their derivative columns, the sets Uj,iU_{j,i} and Ωw\Omega_w, the period blocks with their rows and columns, and the mean of the combined energy (5) over a block; and, in (e), over compact subsets of pseudometric spaces.