ose_two_layer_cube_exact_extension_threshold
Let n be a natural number at least one, and let r and s be positive real numbers with s²+2rs=1. Consider any metric on pairs (b,x), where b is a Boolean and x is a Boolean n-tuple, satisfying all three conditions: d((false,x),(false,y)) is the Euclidean distance between the 0-1 vectors x,y; d((false,x),(true,y))² is r² plus their squared Euclidean distance; and d((true,x),(true,x with coordinate i flipped))=s for every x and coordinate i. Then for every real D there exists a map F from all pairs into Euclidean n-space, equal to x on each (false,x) and satisfying dist(F(a),F(b))≤D*d(a,b) for all a,b, if and only if max(1,sqrt(n)/(2r+s*sqrt(n)))≤D.
Statement
theorem ose_two_layer_cube_exact_extension_threshold (n : ℕ) (hn : 1 ≤ n) (r s : ℝ) (hr : 0 < r) (hs : 0 < s) (hid : s ^ 2 + 2 * r * s = 1) (M : MetricSpace (Bool × (Fin n → Bool))) : letI := M; (∀ (x y : Fin n → Bool), dist (false, x) (false, y) = dist (WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0) : EuclideanSpace ℝ (Fin n)) (WithLp.toLp 2 (fun i : Fin n => if y i then (1 : ℝ) else 0))) → (∀ (x y : Fin n → Bool), dist (false, x) (true, y) ^ 2 = r ^ 2 + dist (WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0) : EuclideanSpace ℝ (Fin n)) (WithLp.toLp 2 (fun i : Fin n => if y i then (1 : ℝ) else 0)) ^ 2) → (∀ (x : Fin n → Bool) (i : Fin n), dist (true, x) (true, Function.update x i (!(x i))) = s) → ∀ D : ℝ, (∃ F : (Bool × (Fin n → Bool)) → EuclideanSpace ℝ (Fin n), (∀ x, F (false, x) = WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0)) ∧ ∀ a b, dist (F a) (F b) ≤ D * dist a b) ↔ max 1 (Real.sqrt (n : ℝ) / (2 * r + s * Real.sqrt (n : ℝ))) ≤ D
- Related work
- arXiv:2611.08546, Sections 6.1–6.2, and one_strongly_euclidean_spherical_core_extension
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ose_boolean_cube_geometryThe standard Boolean cube in Euclidean space lies on the sphere about its center of squared radius n/4, and distinct vertices are…
- ose_boolean_cube_edge_extension_lower_boundFor an arbitrary placement of images of the Boolean cube vertices in Euclidean n-space, if every image lies within Lr of its corresponding…
- one_strongly_euclidean_spherical_core_extensionLet a family of points in a real inner-product space lie on a sphere of radius q/2, with q at least 1 and pairwise distances at least 1.…
- ose_boolean_cube_dist_sq_hammingThe squared Euclidean distance between two standard Boolean-cube vertices equals their Hamming distance.
- ose_hamming_flipA Boolean tuple and the tuple obtained by flipping one coordinate have Hamming distance one.
- Used by 1
- ose_two_layer_cube_universal_extension_thresholdFor n at least one and positive r,s with s²+2rs=1, consider any two-layer Boolean-cube metric whose first-layer distances are the…
Read back from the Lean
For every natural number $n \ge 1$, all positive real numbers $r, s > 0$ satisfying $s^2 + 2rs = 1$, and every metric space structure $M$ on $\text{Bool} \times (\text{Fin } n \to \text{Bool})$, if: 1. For all $x, y : \text{Fin } n \to \text{Bool}$, the distance between $(\text{false}, x)$ and $(\text{false}, y)$ equals the Euclidean ($\ell_2$) distance between their standard embeddings in $\mathbb{R}^n$ (where each coordinate is $1$ if true and $0$ if false); 2. For all $x, y : \text{Fin } n \to \text{Bool}$, the squared distance between $(\text{false}, x)$ and $(\text{true}, y)$ equals $r^2$ plus the squared Euclidean distance between their standard embeddings in $\mathbb{R}^n$; 3. For all $x : \text{Fin } n \to \text{Bool}$ and all $i : \text{Fin } n$, the distance between $(\text{true}, x)$ and $(\text{true}, x')$ equals $s$, where $x'$ is $x$ with the $i$-th coordinate negated; then for every real number $D$, the following are equivalent: - There exists a map $F : \text{Bool} \times (\text{Fin } n \to \text{Bool}) \to \text{EuclideanSpace } \mathbb{R} (\text{Fin } n)$ such that: - for all $x$, $F(\text{false}, x)$ is the standard 0-1 embedding of $x$ into Euclidean space, and - for all $a, b \in \text{Bool} \times (\text{Fin } n \to \text{Bool})$, $\text{dist}(F(a), F(b)) \le D \cdot \text{dist}(a, b)$ ($F$ is $D$-Lipschitz); - $\max\left(1, \frac{\sqrt{n}}{2r + s\sqrt{n}}\right) \le D$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
theorem ose_two_layer_cube_exact_extension_threshold (n : ℕ) (hn : 1 ≤ n) (r s : ℝ) (hr : 0 < r) (hs : 0 < s) (hid : s ^ 2 + 2 * r * s = 1) (M : MetricSpace (Bool × (Fin n → Bool))) : letI := M; (∀ (x y : Fin n → Bool), dist (false, x) (false, y) = dist (WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0) : EuclideanSpace ℝ (Fin n)) (WithLp.toLp 2 (fun i : Fin n => if y i then (1 : ℝ) else 0))) → (∀ (x y : Fin n → Bool), dist (false, x) (true, y) ^ 2 = r ^ 2 + dist (WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0) : EuclideanSpace ℝ (Fin n)) (WithLp.toLp 2 (fun i : Fin n => if y i then (1 : ℝ) else 0)) ^ 2) → (∀ (x : Fin n → Bool) (i : Fin n), dist (true, x) (true, Function.update x i (!(x i))) = s) → ∀ D : ℝ, (∃ F : (Bool × (Fin n → Bool)) → EuclideanSpace ℝ (Fin n), (∀ x, F (false, x) = WithLp.toLp 2 (fun i : Fin n => if x i then (1 : ℝ) else 0)) ∧ ∀ a b, dist (F a) (F b) ≤ D * dist a b) ↔ max 1 (Real.sqrt (n : ℝ) / (2 * r + s * Real.sqrt (n : ℝ))) ≤ D := by intro hf hc he D let U : (Fin n → Bool) → EuclideanSpace ℝ (Fin n) := fun x => WithLp.toLp 2 (fun i => if x i then (1 : ℝ) else 0) let c : EuclideanSpace ℝ (Fin n) := WithLp.toLp 2 (fun _ => (1 : ℝ)/2) let q : ℝ := Real.sqrt (n : ℝ) have hn0 : 0 ≤ (n : ℝ) := by positivity have hq0 : 0 ≤ q := Real.sqrt_nonneg _ have hqn : q^2 = (n : ℝ) := Real.sq_sqrt hn0 have hq1 : 1 ≤ q := Real.one_le_sqrt.mpr (by exact_mod_cast hn) have hU (x : Fin n → Bool) : ‖U x-c‖^2 = q^2/4 := by rw [hqn] exact (ose_boolean_cube_geometry n).1 x have hUsep (x y : Fin n → Bool) (hxy : x ≠ y) : 1 ≤ dist (U x) (U y)^2 := (ose_boolean_cube_geometry n).2 x y hxy constructor · rintro ⟨F,hFixed,hLip⟩ let x0 : Fin n → Bool := fun _ => false let i0 : Fin n := ⟨0, by omega⟩ let y0 : Fin n → Bool := Function.update x0 i0 (!(x0 i0)) have hUsq : dist (U x0) (U y0)^2 = 1 := by have h := ose_boolean_cube_dist_sq_hamming n x0 y0 change dist (U x0) (U y0)^2 = (hammingDist x0 y0 : ℝ) at h have hham : hammingDist x0 y0 = 1 := by dsimp [y0] exact ose_hamming_flip n x0 i0 rw [hham] at h simpa only [Nat.cast_one] using h have hUedge : dist (U x0) (U y0) = 1 := by have hd : 0 ≤ dist (U x0) (U y0) := dist_nonneg nlinarith have hD : 1 ≤ D := by have h := hLip (false,x0) (false,y0) rw [hFixed x0,hFixed y0,hf x0 y0,hUedge] at h nlinarith let v : (Fin n → Bool) → EuclideanSpace ℝ (Fin n) := fun x => F (true,x) have hnear (x : Fin n → Bool) : dist (v x) (U x) ≤ D*r := by have hx := hc x x simp only [dist_self,zero_pow,add_zero] at hx have hdist : dist (true,x) (false,x) = r := by rw [dist_comm] have hd : 0 ≤ dist (false,x) (true,x) := dist_nonneg nlinarith have h := hLip (true,x) (false,x) rw [hFixed x,hdist] at h exact h have hedge (x : Fin n → Bool) (i : Fin n) : dist (v x) (v (Function.update x i (!(x i)))) ≤ D*s := by have h := hLip (true,x) (true,Function.update x i (!(x i))) rw [he x i] at h exact h have hlower := ose_boolean_cube_edge_extension_lower_bound n r s D (by linarith) hr.le hs.le v hnear hedge have hden : 0 < 2*r+s*q := by positivity have hfrac : q/(2*r+s*q) ≤ D := (div_le_iff₀ hden).2 (by dsimp [q] at *; nlinarith [hlower]) exact max_le hD hfrac · intro hD have hf' (x y : Fin n → Bool) : dist (false,x) (false,y) = dist (U x) (U y) := hf x y have hc' (x y : Fin n → Bool) : dist (false,x) (true,y)^2 = r^2+dist (U x) (U y)^2 := hc x y obtain ⟨F,hFixed,hLip⟩ := one_strongly_euclidean_spherical_core_extension (Fin n → Bool) (EuclideanSpace ℝ (Fin n)) U c q r s hq1 hr hs hid hU hUsep M hf' hc' refine ⟨F,hFixed,fun a b => ?_⟩ exact le_trans (hLip a b) (mul_le_mul_of_nonneg_right hD dist_nonneg)