ose_spherical_two_layer_hilbert_distortion_upper
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
- ose_two_layer_cube_exact_hilbert_distortionLet 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…
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).
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.
uses
mul_posintro hf hc hb have hq1 : 1 ≤ q := by nlinarith have hs1 : s ≤ 1 := by nlinarith [mul_pos hr hs]
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.
uses
norm_nonneghave hnorm (a : A) : ‖u a-c‖ = q/2 := by have h := hu a have hn : 0 ≤ ‖u a-c‖ := norm_nonneg _ nlinarith
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.
uses
dist_triangle,dist_eq_norm,dist_commhave 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
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.
by_cases hsmall : s*q ≤ 1In 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)).
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))
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`.
uses
min_eq_left,dist_nonneg,le_trans,mul_le_mul_of_nonneg_left,mul_nonneg,sub_nonneg.mprhave 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]
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.
uses
ose_sphere_two_scale_distance_identityhave 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 hyThere 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.
uses
ose_spherical_small_scale_auxobtain ⟨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 htThe 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.
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⟩
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.
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]
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.
uses
ose_two_layer_direct_embeddingobtain ⟨F,hF⟩ := ose_two_layer_direct_embedding A H u r s hs hs1 M hf hc hBThe 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.
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.
- The target Hilbert space is constructed as the ℓ₂ direct sum H × ℝ via `WithLp 2 (H × ℝ)`, and the required algebraic, inner-product, and completeness instances are inferred automatically by Lean.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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⟩