AFTD Auto-Formalizing Theoretical Domains

ose_two_layer_cube_exact_hilbert_distortion

theoremverifiedoriginal

Let n be a natural number at least two, let r and s be positive reals with s²+2rs=1, and consider any metric on pairs (b,x) with a Boolean b and Boolean n-tuple x. For each pair x,y at Hamming distance h, assume the false-layer distance is sqrt(h), the false-to-true distance is sqrt(r²+h), and the true-layer distance is min(s*h,sqrt(h)). Then for every real D, there is a map of all these pairs into a real Hilbert space whose distances lie between the original distances and D times them if and only if min(sqrt(n),1/s)≤D.

Statement

theorem ose_two_layer_cube_exact_hilbert_distortion (n : ℕ) (hn : 2 ≤ 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) = Real.sqrt (hammingDist x y : ℝ)) → (∀ (x y : Fin n → Bool), dist (false,x) (true,y) = Real.sqrt (r ^ 2 + (hammingDist x y : ℝ))) → (∀ (x y : Fin n → Bool), dist (true,x) (true,y) = min (s * (hammingDist x y : ℝ)) (Real.sqrt (hammingDist x y : ℝ))) → ∀ D : ℝ, EmbedsIntoHilbertWithDistortion (Bool × (Fin n → Bool)) D ↔ min (Real.sqrt (n : ℝ)) (1 / s) ≤ D
Related work
arXiv:2611.08546, Section 6.1, two-layer cube
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • ose_cube_hilbert_antipodal_inequalityFor any map from the Boolean n-cube into a real inner-product space, the sum of squared antipodal distances is at most the sum over all…
  • ose_spherical_two_layer_hilbert_distortion_upperLet a family of points in a complete real inner-product space lie on a sphere of radius q/2, with q positive and q² at least two, and have…
  • 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…
  • EmbedsIntoHilbertWithDistortionA metric space X embeds into a real Hilbert space with distortion at most D if there exists a real Hilbert space H and a map f from X to H…
  • ose_boolean_cube_dist_sq_hammingThe squared Euclidean distance between two standard Boolean-cube vertices equals their Hamming distance.
  • ose_hamming_antipodeEvery Boolean n-tuple differs from its bitwise complement in exactly n coordinates.
  • ose_hamming_flipA Boolean tuple and the tuple obtained by flipping one coordinate have Hamming distance one.
  • ose_cube_scale_distortion_lowerIf a two-layer cube has second-layer edge distance s and antipodal distance m, and a noncontracting D-Lipschitz Hilbert map satisfies the…

Read back from the Lean

Let $n$ be a natural number with $n \ge 2$, and let $r, s$ be real numbers such that $r > 0$, $s > 0$, and $s^2 + 2rs = 1$. Let $M$ be a metric space structure on the type $\text{Bool} \times (\text{Fin } n \to \text{Bool})$. Assume that under the metric of $M$: 1. For all $x, y : \text{Fin } n \to \text{Bool}$, $\text{dist}((\text{false}, x), (\text{false}, y)) = \sqrt{\text{hammingDist}(x, y)}$; 2. For all $x, y : \text{Fin } n \to \text{Bool}$, $\text{dist}((\text{false}, x), (\text{true}, y)) = \sqrt{r^2 + \text{hammingDist}(x, y)}$; 3. For all $x, y : \text{Fin } n \to \text{Bool}$, $\text{dist}((\text{true}, x), (\text{true}, y)) = \min(s \cdot \text{hammingDist}(x, y), \sqrt{\text{hammingDist}(x, y)})$. Then, for every real number $D$, the metric space $\text{Bool} \times (\text{Fin } n \to \text{Bool})$ embeds into a Hilbert space with distortion $D$ if and only if $\min(\sqrt{n}, 1/s) \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_hilbert_distortion (n : ℕ) (hn : 2 ≤ 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) = Real.sqrt (hammingDist x y : ℝ)) → (∀ (x y : Fin n → Bool), dist (false,x) (true,y) = Real.sqrt (r ^ 2 + (hammingDist x y : ℝ))) → (∀ (x y : Fin n → Bool), dist (true,x) (true,y) = min (s * (hammingDist x y : ℝ)) (Real.sqrt (hammingDist x y : ℝ))) → ∀ D : ℝ, EmbedsIntoHilbertWithDistortion (Bool × (Fin n → Bool)) D ↔ min (Real.sqrt (n : ℝ)) (1 / s) ≤ D := by
  intro hAA hAB hBB D
  let q : ℝ := Real.sqrt (n : ℝ)
  have hnpos : 0 < (n : ℝ) := by exact_mod_cast (show 0 < n by omega)
  have hqpos : 0 < q := Real.sqrt_pos.2 hnpos
  have hqn : q^2 = (n : ℝ) := Real.sq_sqrt (le_of_lt hnpos)
  have hq2 : 2 ≤ q^2 := by rw [hqn]; exact_mod_cast hn
  have hs1 : s ≤ 1 := by nlinarith [mul_pos hr hs]
  let m : ℝ := min (s*(n : ℝ)) q
  have hm0 : 0 ≤ m := le_min (mul_nonneg hs.le (le_of_lt hnpos)) (le_of_lt hqpos)
  have hanti (x : Fin n → Bool) : dist (true,x) (true,fun i => !(x i)) = m := by
    rw [hBB, ose_hamming_antipode]
  have hedge (x : Fin n → Bool) (i : Fin n) :
      dist (true,x) (true,Function.update x i (!(x i))) = s := by
    rw [hBB, ose_hamming_flip]
    norm_num
    exact hs1
  constructor
  · intro hD
    rcases hD with ⟨H, hH, hI, hC, F, hF⟩
    letI : NormedAddCommGroup H := hH
    letI : InnerProductSpace ℝ H := hI
    letI : CompleteSpace H := hC
    have htype := ose_cube_hilbert_antipodal_inequality n H (fun x => F (true,x))
    have hbound := ose_cube_scale_distortion_lower n (by omega) M m s D hm0 hs H hanti hedge F hF htype
    have hsqpos : 0 < s*q := mul_pos hs hqpos
    have hminprod : min q (1/s) * (s*q) = m := by
      rw [min_mul_of_nonneg q (1/s) (le_of_lt hsqpos)]
      have e1 : q * (s*q) = s*(n : ℝ) := by rw [← hqn]; ring
      have e2 : (1/s) * (s*q) = q := by field_simp [ne_of_gt hs]
      rw [e1,e2]
    have hprod : min q (1/s) * (s*q) ≤ D * (s*q) := by
      rw [hminprod]
      nlinarith only [hbound]
    exact le_of_mul_le_mul_right hprod hsqpos
  · intro hD
    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)
    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) := by
      have h := (ose_boolean_cube_geometry n).2 x y hxy
      have hd : 0 ≤ dist (U x) (U y) := dist_nonneg
      nlinarith
    have hUsq (x y : Fin n → Bool) : dist (U x) (U y)^2 = (hammingDist x y : ℝ) :=
      ose_boolean_cube_dist_sq_hamming n x y
    have hUdist (x y : Fin n → Bool) : dist (U x) (U y) = Real.sqrt (hammingDist x y : ℝ) := by
      have h := hUsq x y
      have hr0 : 0 ≤ (hammingDist x y : ℝ) := by positivity
      have hroot := Real.sq_sqrt hr0
      have hd : 0 ≤ dist (U x) (U y) := dist_nonneg
      have hsqrt := Real.sqrt_nonneg (hammingDist x y : ℝ)
      nlinarith
    have hf (x y : Fin n → Bool) : dist (false,x) (false,y) = dist (U x) (U y) := by
      rw [hAA,hUdist]
    have hc (x y : Fin n → Bool) : dist (false,x) (true,y)^2 = r^2+dist (U x) (U y)^2 := by
      rw [hAB,Real.sq_sqrt (by positivity),hUsq]
    have hb (x y : Fin n → Bool) : dist (true,x) (true,y) =
        min (s*dist (U x) (U y)^2) (dist (U x) (U y)) := by
      rw [hBB,hUsq,hUdist]
    have hgood := ose_spherical_two_layer_hilbert_distortion_upper (Fin n → Bool)
      (EuclideanSpace ℝ (Fin n)) U c q r s hqpos hq2 hr hs hid hU hUsep M hf hc hb
    rcases hgood with ⟨H, hH, hI, hC, F, hF⟩
    letI : NormedAddCommGroup H := hH
    letI : InnerProductSpace ℝ H := hI
    letI : CompleteSpace H := hC
    refine ⟨H,hH,hI,hC,F,fun x y => ⟨(hF x y).1, ?_⟩⟩
    exact le_trans (hF x y).2 (mul_le_mul_of_nonneg_right hD dist_nonneg)
See it in the graphDiscuss this resultChallenge it