AFTD Auto-Formalizing Theoretical Domains

ose_spherical_two_layer_hilbert_distortion_upper

theoremverifiedoriginal

Let 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 mutual distances at least one. Give two copies any metric whose first-layer distances are the original distances, whose cross-layer squared distances equal r² plus the original squared distances, and whose second-layer distances equal the minimum of s times the squared original distance and the original distance. If r,s are positive and s²+2rs=1, the whole two-layer metric embeds in Hilbert space with distortion at most min(q,1/s).

Statement

theorem ose_spherical_two_layer_hilbert_distortion_upper (A H : Type) [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] (u : A → H) (c : H) (q r s : ℝ) (hq : 0 < q) (hq2 : 2 ≤ q ^ 2) (hr : 0 < r) (hs : 0 < s) (hid : s ^ 2 + 2 * r * s = 1) (hu : ∀ a, ‖u a - c‖ ^ 2 = q ^ 2 / 4) (hsep : ∀ a b, a ≠ b → 1 ≤ dist (u a) (u b)) (M : MetricSpace (Bool × A)) : letI := M; (∀ a b, dist (false,a) (false,b) = dist (u a) (u b)) → (∀ a b, dist (false,a) (true,b)^2 = r^2 + dist (u a) (u b)^2) → (∀ a b, dist (true,a) (true,b) = min (s * dist (u a) (u b)^2) (dist (u a) (u b))) → EmbedsIntoHilbertWithDistortion (Bool × A) (min q (1 / s))
Related work
arXiv:2611.08546, Section 6.1, and one_strongly_euclidean_spherical_core_extension
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • ose_two_layer_direct_embeddingFor two layers over points in an inner-product space, if the first layer is isometric, the cross distances are Euclidean at vertical…
  • 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_spherical_shrink_scalar_boundsUnder the small-s parameter assumptions for the spherical two-layer construction, the two radial scaling factors have the ordering and…
  • ose_sphere_two_scale_distance_identityFor two vectors on the same sphere of squared radius q²/4, the squared distance after independent radial scalings beta and alpha equals…
  • ose_spherical_small_scale_auxFor two spherical metric layers satisfying the displayed scalar inequalities and the two-scale norm identity, if the first-layer metric is…
Used by 1

Read back from the Lean

Let $A$ and $H$ be types, with $H$ equipped with the structure of a complete real inner product space (real Hilbert space). Let $u : A \to H$ be a map, $c \in H$ a center point, and $q, r, s \in \mathbb{R}$ scalars satisfying: 1. $q > 0$, 2. $q^2 \ge 2$, 3. $r > 0$, 4. $s > 0$, 5. $s^2 + 2rs = 1$, 6. for all $a \in A$, $\|u(a) - c\|^2 = q^2 / 4$, 7. for all $a, b \in A$, if $a \ne b$ then $\operatorname{dist}(u(a), u(b)) \ge 1$. Let $M$ be a metric space structure on $\text{Bool} \times A$. Suppose that under $M$: - for all $a, b \in A$, $\operatorname{dist}((\text{false}, a), (\text{false}, b)) = \operatorname{dist}(u(a), u(b))$, - for all $a, b \in A$, $\operatorname{dist}((\text{false}, a), (\text{true}, b))^2 = r^2 + \operatorname{dist}(u(a), u(b))^2$, - for all $a, b \in A$, $\operatorname{dist}((\text{true}, a), (\text{true}, b)) = \min(s \cdot \operatorname{dist}(u(a), u(b))^2, \operatorname{dist}(u(a), u(b)))$. Then $(\text{Bool} \times A, M)$ embeds into a Hilbert space with distortion at most $\min(q, 1/s)$ (i.e., EmbedsIntoHilbertWithDistortion (Bool × A) (min q (1 / s))).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem proves that the two-layer metric space embeds into a Hilbert space with distortion at most min(q, 1/s) by splitting into two cases based on whether s * q ≤ 1. In both cases, the points u(a) have diameter at most q, and the algebraic identity s² + 2rs = 1 implies s ≤ 1 and q ≥ 1. When s * q ≤ 1, the second-layer distance simplifies to s * dist², and an auxiliary spherical embedding lemma yields distortion at most q = min(q, 1/s). When s * q > 1, the second-layer distance is sandwiched between s * dist and dist, allowing a direct two-layer embedding lemma to achieve distortion at most 1/s = min(q, 1/s).

  1. Assume the metric conditions on the two-layer space and deduce q ≥ 1 and s ≤ 1.

    We introduce the hypotheses specifying the distances on the first layer, across layers, and on the second layer. From q > 0 and q² ≥ 2, non-linear arithmetic gives q ≥ 1. From s² + 2rs = 1 with r > 0 and s > 0, the term 2rs is strictly positive by `mul_pos`, so s² < 1, which implies s ≤ 1.

    lines 2–4

    uses mul_pos

      intro hf hc hb
      have hq1 : 1 ≤ q := by nlinarith
      have hs1 : s ≤ 1 := by nlinarith [mul_pos hr hs]
  2. Every point u(a) has distance q/2 from the center c: ‖u(a) - c‖ = q/2.

    The hypothesis gives ‖u(a) - c‖² = q²/4. Since norms are non-negative (`norm_nonneg`), taking square roots yields ‖u(a) - c‖ = q/2.

    lines 5–8

    uses norm_nonneg

      have hnorm (a : A) : ‖u a-c‖ = q/2 := by
        have h := hu a
        have hn : 0 ≤ ‖u a-c‖ := norm_nonneg _
        nlinarith
  3. The pairwise distance between any two original points satisfies dist(u(a), u(b)) ≤ q.

    By the triangle inequality (`dist_triangle`), dist(u(a), u(b)) ≤ dist(u(a), c) + dist(c, u(b)). Rewriting both distances as norms (`dist_eq_norm`, `dist_comm`) and substituting ‖u(·) - c‖ = q/2 gives dist(u(a), u(b)) ≤ q/2 + q/2 = q.

    lines 9–13

    uses dist_triangle, dist_eq_norm, dist_comm

      have hdiam (a b : A) : dist (u a) (u b) ≤ q := by
        have htri := dist_triangle (u a) c (u b)
        have h1 : dist (u a) c = q/2 := by rw [dist_eq_norm, hnorm]
        have h2 : dist c (u b) = q/2 := by rw [dist_comm, dist_eq_norm, hnorm]
        linarith
  4. Split into two cases based on whether s * q ≤ 1 or s * q > 1.

    We perform a case split on the inequality s * q ≤ 1. In the first case the distortion bound min(q, 1/s) equals q, while in the second case it equals 1/s.

    line 14

      by_cases hsmall : s*q ≤ 1
  5. In the small-scale regime (s * q ≤ 1), the scaling parameter β = min(q, 1/(sq)) satisfies all bounds required for the spherical embedding.

    Applying `ose_spherical_shrink_scalar_bounds` with the parameters q, r, s produces the bounds: 1 ≤ β ≤ q, (s*q)*β ≤ 1, (β - s*q)² ≤ 4r², and r² + q²(1 - (s*q)*β) ≤ q²r². We unpack these inequalities and define β = min(q, 1/(s*q)).

    lines 15–18

    uses ose_spherical_shrink_scalar_bounds

      · have hsc := ose_spherical_shrink_scalar_bounds q r s hq hq2 hr hs hid hsmall
        dsimp only at hsc
        rcases hsc with ⟨_, _, _, hβ1, hβq, hprod, hdiff, hparam⟩
        let β : ℝ := min q (1/(s*q))
  6. In the small-scale regime, the second-layer distance simplifies to dist((true, a), (true, b)) = s * dist(u(a), u(b))².

    The second-layer distance is min(s * dist(u(a), u(b))², dist(u(a), u(b))). Since dist(u(a), u(b)) ≤ q and s * q ≤ 1, transitivity (`le_trans`) and monotonicity of multiplication (`mul_le_mul_of_nonneg_left`) give s * dist(u(a), u(b)) ≤ 1. Multiplying by the non-negative distance (`dist_nonneg`, `mul_nonneg`, `sub_nonneg.mpr`) yields s * dist(u(a), u(b))² ≤ dist(u(a), u(b)), so the minimum evaluates to the first argument by `min_eq_left`.

    lines 19–26

    uses min_eq_left, dist_nonneg, le_trans, mul_le_mul_of_nonneg_left, mul_nonneg, sub_nonneg.mpr

        have ht : ∀ a b, dist (true,a) (true,b) = s * dist (u a) (u b)^2 := by
          intro a b
          rw [hb, min_eq_left]
          have hd0 : 0 ≤ dist (u a) (u b) := dist_nonneg
          have hdq := hdiam a b
          have hle : s * dist (u a) (u b) ≤ 1 := le_trans (mul_le_mul_of_nonneg_left hdq hs.le) hsmall
          have hp := mul_nonneg hd0 (sub_nonneg.mpr hle)
          nlinarith only [hp]
  7. The two-scale distance identity on the sphere of radius q/2 holds for the scaling factors s * q and β.

    This is an instantiation of `ose_sphere_two_scale_distance_identity` for any two points x, y with ‖x‖² = ‖y‖² = q²/4.

    lines 27–29

    uses ose_sphere_two_scale_distance_identity

        have hidentity (x y : H) (hx : ‖x‖^2 = q^2/4) (hy : ‖y‖^2 = q^2/4) :
            ‖β • x-(s*q) • y‖^2 = (β-s*q)^2*q^2/4+(s*q)*β*‖x-y‖^2 :=
          ose_sphere_two_scale_distance_identity H x y (s*q) β q hx hy
  8. There exists an embedding F of Bool × A into H × ℝ with distortion at most q.

    We invoke `ose_spherical_small_scale_aux`, supplying the geometric bounds on β, the sphere identity, the separation condition (dist(u(a), u(b)) ≥ 1 for a ≠ b), and the simplified layer distances. This produces the embedding F.

    lines 30–31

    uses ose_spherical_small_scale_aux

        obtain ⟨F, hF⟩ := ose_spherical_small_scale_aux A H u c q r s β hq1 hr.le hs hsmall
          hβ1 hβq hprod hdiff hparam hu hsep hidentity M hf hc ht
  9. The embedding F achieves distortion at most min(q, 1/s) in the case s * q ≤ 1.

    Since s > 0 and s * q ≤ 1, rewriting the division inequality (`le_div_iff₀`) shows q ≤ 1/s, so min(q, 1/s) = q by `min_eq_left`. Packing F together with the Hilbert space H × ℝ (with its ℓ₂ norm) provides the desired witness.

    lines 32–34

    uses min_eq_left, le_div_iff₀

        have hmin : min q (1/s) = q := min_eq_left ((le_div_iff₀ hs).2 (by nlinarith [hsmall]))
        rw [hmin]
        exact ⟨WithLp 2 (H × ℝ), inferInstance, inferInstance, inferInstance, F, hF⟩
  10. In the large-scale regime (s * q > 1), the second-layer distance is sandwiched: s * dist(u(a), u(b)) ≤ dist((true, a), (true, b)) ≤ dist(u(a), u(b)).

    The upper bound follows from min(x, y) ≤ y (`min_le_right`). For the lower bound, if a = b both sides are 0. If a ≠ b, points are separated by dist(u(a), u(b)) ≥ 1, which implies s * dist(u(a), u(b)) ≤ s * dist(u(a), u(b))². Together with s ≤ 1, this shows s * dist(u(a), u(b)) is bounded above by both arguments of the minimum, and `le_min` concludes the inequality.

    lines 35–47

    uses le_min, min_le_right, dist_nonneg, mul_nonneg

      · have hB : ∀ a b, s * dist (u a) (u b) ≤ dist (true,a) (true,b) ∧
            dist (true,a) (true,b) ≤ dist (u a) (u b) := by
          intro a b
          rw [hb]
          refine ⟨le_min ?_ ?_, min_le_right _ _⟩
          · by_cases hab : a=b
            · subst b; simp
            · have hd := hsep a b hab
              have hd0 : 0 ≤ dist (u a) (u b) := dist_nonneg
              have hp := mul_nonneg hs.le (mul_nonneg hd0 (by linarith : 0 ≤ dist (u a) (u b)-1))
              nlinarith only [hp]
          · have hp := mul_nonneg (by linarith : 0 ≤ 1-s) (dist_nonneg (x := u a) (y := u b))
            nlinarith only [hp]
  11. There exists an embedding F of Bool × A into H × ℝ with distortion at most 1/s.

    We apply `ose_two_layer_direct_embedding` with the distance sandwich condition on the second layer and the cross-layer squared distance condition, yielding an embedding F into H × ℝ with distortion 1/s.

    line 48

    uses ose_two_layer_direct_embedding

        obtain ⟨F,hF⟩ := ose_two_layer_direct_embedding A H u r s hs hs1 M hf hc hB
  12. The embedding F achieves distortion at most min(q, 1/s) in the case s * q > 1.

    From ¬(s * q ≤ 1) and s > 0, we have 1/s ≤ q by `div_le_iff₀`, so min(q, 1/s) = 1/s by `min_eq_right`. Rewriting the goal with this identity and providing F into H × ℝ concludes the proof.

    lines 49–51

    uses min_eq_right, div_le_iff₀

        have hmin : min q (1/s) = 1/s := min_eq_right ((div_le_iff₀ hs).2 (by nlinarith [hsmall]))
        rw [hmin]
        exact ⟨WithLp 2 (H × ℝ), inferInstance, inferInstance, inferInstance, F, hF⟩
dist_comm
The distance function is symmetric: dist(x, y) = dist(y, x).
dist_eq_norm
In a normed group, the distance between two points equals the norm of their difference: dist(a, b) = ‖a - b‖.
dist_nonneg
Distance between any two points is non-negative: 0 ≤ dist(x, y).
dist_triangle
The triangle inequality: dist(x, z) ≤ dist(x, y) + dist(y, z).
div_le_iff₀
For positive c, b / c ≤ a is equivalent to b ≤ a * c.
le_div_iff₀
For positive c, a ≤ b / c is equivalent to a * c ≤ b.
le_min
A number bounded above by both a and b is bounded above by their minimum: c ≤ a → c ≤ b → c ≤ min(a, b).
le_trans
Transitivity of the order relation: a ≤ b → b ≤ c → a ≤ c.
min_eq_left
If a ≤ b, then min(a, b) = a.
min_eq_right
If b ≤ a, then min(a, b) = b.
min_le_right
The minimum of two values is at most the second value: min(a, b) ≤ b.
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a non-negative scalar a preserves the inequality: a * b ≤ a * c.
mul_nonneg
The product of two non-negative numbers is non-negative: 0 ≤ a → 0 ≤ b → 0 ≤ a * b.
mul_pos
The product of two strictly positive numbers is strictly positive: 0 < a → 0 < b → 0 < a * b.
norm_nonneg
The norm of any element is non-negative: 0 ≤ ‖a‖.
ose_sphere_two_scale_distance_identity
For points x, y on a sphere of radius q/2 centered at the origin, ‖β • x - α • y‖² = (β - α)² (q²/4) + α β ‖x - y‖².
ose_spherical_small_scale_aux
Embeds the two-layer metric space into H × ℝ with distortion at most q when the second-layer distance is s times the original squared distance and the shrinkage bounds hold.
ose_spherical_shrink_scalar_bounds
Given parameters q > 0 with q² ≥ 2, r > 0, s > 0 with s² + 2rs = 1, and s * q ≤ 1, the scaling parameters α = s * q and β = min(q, 1/α) satisfy the algebraic bounds needed for the two-scale spherical embedding.
ose_two_layer_direct_embedding
Embeds the two-layer metric space into H × ℝ with distortion at most 1/s whenever second-layer distances are bounded between s * d and d.
sub_nonneg.mpr
If b ≤ a, then 0 ≤ a - b.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem ose_spherical_two_layer_hilbert_distortion_upper (A H : Type) [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] (u : A → H) (c : H) (q r s : ℝ) (hq : 0 < q) (hq2 : 2 ≤ q ^ 2) (hr : 0 < r) (hs : 0 < s) (hid : s ^ 2 + 2 * r * s = 1) (hu : ∀ a, ‖u a - c‖ ^ 2 = q ^ 2 / 4) (hsep : ∀ a b, a ≠ b → 1 ≤ dist (u a) (u b)) (M : MetricSpace (Bool × A)) : letI := M; (∀ a b, dist (false,a) (false,b) = dist (u a) (u b)) → (∀ a b, dist (false,a) (true,b)^2 = r^2 + dist (u a) (u b)^2) → (∀ a b, dist (true,a) (true,b) = min (s * dist (u a) (u b)^2) (dist (u a) (u b))) → EmbedsIntoHilbertWithDistortion (Bool × A) (min q (1 / s)) := by  intro hf hc hb  have hq1 : 1 ≤ q := by nlinarith  have hs1 : s ≤ 1 := by nlinarith [mul_pos hr hs]  have hnorm (a : A) : ‖u a-c‖ = q/2 := by    have h := hu a    have hn : 0 ≤ ‖u a-c‖ := norm_nonneg _    nlinarith  have hdiam (a b : A) : dist (u a) (u b) ≤ q := by    have htri := dist_triangle (u a) c (u b)    have h1 : dist (u a) c = q/2 := by rw [dist_eq_norm, hnorm]    have h2 : dist c (u b) = q/2 := by rw [dist_comm, dist_eq_norm, hnorm]    linarith  by_cases hsmall : s*q ≤ 1  · have hsc := ose_spherical_shrink_scalar_bounds q r s hq hq2 hr hs hid hsmall    dsimp only at hsc    rcases hsc with ⟨_, _, _, hβ1, hβq, hprod, hdiff, hparam⟩    let β : ℝ := min q (1/(s*q))    have ht : ∀ a b, dist (true,a) (true,b) = s * dist (u a) (u b)^2 := by      intro a b      rw [hb, min_eq_left]      have hd0 : 0 ≤ dist (u a) (u b) := dist_nonneg      have hdq := hdiam a b      have hle : s * dist (u a) (u b) ≤ 1 := le_trans (mul_le_mul_of_nonneg_left hdq hs.le) hsmall      have hp := mul_nonneg hd0 (sub_nonneg.mpr hle)      nlinarith only [hp]    have hidentity (x y : H) (hx : ‖x‖^2 = q^2/4) (hy : ‖y‖^2 = q^2/4) :        ‖β • x-(s*q) • y‖^2 = (β-s*q)^2*q^2/4+(s*q)*β*‖x-y‖^2 :=      ose_sphere_two_scale_distance_identity H x y (s*q) β q hx hy    obtain ⟨F, hF⟩ := ose_spherical_small_scale_aux A H u c q r s β hq1 hr.le hs hsmall      hβ1 hβq hprod hdiff hparam hu hsep hidentity M hf hc ht    have hmin : min q (1/s) = q := min_eq_left ((le_div_iff₀ hs).2 (by nlinarith [hsmall]))    rw [hmin]    exact ⟨WithLp 2 (H × ℝ), inferInstance, inferInstance, inferInstance, F, hF⟩  · have hB : ∀ a b, s * dist (u a) (u b) ≤ dist (true,a) (true,b) ∧        dist (true,a) (true,b) ≤ dist (u a) (u b) := by      intro a b      rw [hb]      refine ⟨le_min ?_ ?_, min_le_right _ _⟩      · by_cases hab : a=b        · subst b; simp        · have hd := hsep a b hab          have hd0 : 0 ≤ dist (u a) (u b) := dist_nonneg          have hp := mul_nonneg hs.le (mul_nonneg hd0 (by linarith : 0 ≤ dist (u a) (u b)-1))          nlinarith only [hp]      · have hp := mul_nonneg (by linarith : 0 ≤ 1-s) (dist_nonneg (x := u a) (y := u b))        nlinarith only [hp]    obtain ⟨F,hF⟩ := ose_two_layer_direct_embedding A H u r s hs hs1 M hf hc hB    have hmin : min q (1/s) = 1/s := min_eq_right ((div_le_iff₀ hs).2 (by nlinarith [hsmall]))    rw [hmin]    exact ⟨WithLp 2 (H × ℝ), inferInstance, inferInstance, inferInstance, F, hF⟩
See it in the graphDiscuss this resultChallenge it