ose_two_layer_direct_embedding
For two layers over points in an inner-product space, if the first layer is isometric, the cross distances are Euclidean at vertical separation r, and second-layer distances lie between s times and one times the first-layer distances, then the vertical placement of the layers is noncontracting and has Lipschitz constant at most 1/s, for 0<s≤1.
Statement
theorem ose_two_layer_direct_embedding (A H : Type) [NormedAddCommGroup H] [InnerProductSpace ℝ H] (u : A → H) (r s : ℝ) (hs : 0 < s) (hs1 : s ≤ 1) (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, s * dist (u a) (u b) ≤ dist (true,a) (true,b) ∧ dist (true,a) (true,b) ≤ dist (u a) (u b)) → ∃ F : Bool × A → WithLp 2 (H × ℝ), ∀ x y, dist x y ≤ dist (F x) (F y) ∧ dist (F x) (F y) ≤ (1 / s) * dist x y
- Source
- arXiv:2611.08546, Section 6.1, two-layer cube metric
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- 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…
The proof, explained
The proof constructs an explicit embedding F from Bool × A into the L² direct sum H × ℝ by mapping each point (b, a) to (u(a), 0) if b is false and to (u(a), r) if b is true. The distance squared between any two embedded points decomposes by the Pythagorean theorem into the horizontal separation in H plus the vertical separation in ℝ. A four-way case analysis on the layer indicators shows that F preserves distances on layer 0 and between different layers, while on layer 1 the embedded distance is dist(u(a), u(d)). The sandwiching bounds s * dist(u(a), u(d)) ≤ dist((true, a), (true, d)) ≤ dist(u(a), u(d)) then guarantee that F is noncontracting and has Lipschitz constant at most 1/s.
Define the embedding F into H × ℝ and reduce to checking distortion bounds.
Assuming the layer 0 isometry hypothesis hf, the cross-distance formula hc, and the layer 1 distance bounds ht, we define F to place each point (b, a) at (u(a), 0) if b is false and at (u(a), r) if b is true in the L² direct sum H × ℝ. We then goal-reduce to showing that dist x y ≤ dist (F x) (F y) ≤ (1 / s) * dist x y for all pairs x, y.
intro hf hc ht let F : Bool × A → WithLp 2 (H × ℝ) := fun p => WithLp.toLp 2 (u p.2, if p.1 then r else 0) refine ⟨F, ?_⟩
Establish that 0 ≤ s and 1 ≤ 1 / s.
From 0 < s we obtain 0 ≤ s by le_of_lt. Since s ≤ 1 and s > 0, clearing denominators via le_div_iff₀ shows that 1 ≤ 1 / s.
uses
le_of_lt,le_div_iff₀have hs_nonneg : 0 ≤ s := le_of_lt hs have hD : 1 ≤ 1 / s := (le_div_iff₀ hs).2 (by linarith)
Compute the squared distance between embedded points under F via the Pythagorean theorem.
Rewriting distance as the norm of differences (dist_eq_norm) in the L² product space (WithLp.prod_norm_sq_eq_of_L2) shows that the squared distance between F(b, a) and F(c, d) is the squared distance dist(u a, u d)² in H plus the squared difference between the vertical coordinates in ℝ, simplified using Real.norm_eq_abs and sq_abs.
uses
dist_eq_norm,WithLp.prod_norm_sq_eq_of_L2,Real.norm_eq_abs,sq_abshave hsq : ∀ b c : Bool, ∀ a d : A, dist (F (b,a)) (F (c,d)) ^ 2 = dist (u a) (u d) ^ 2 + ((if b then r else 0) - (if c then r else 0)) ^ 2 := by intro b c a d rw [dist_eq_norm, WithLp.prod_norm_sq_eq_of_L2] simp [F, dist_eq_norm, Real.norm_eq_abs, sq_abs]
Split into four cases according to the layer indicators of the two points.
Given arbitrary points (b, a) and (c, d) in Bool × A, we perform case analysis on the boolean layer indices b and c, yielding the four cases (false, false), (false, true), (true, false), and (true, true).
intro ⟨b,a⟩ ⟨c,d⟩ cases b <;> cases c
Both points in layer 0: F preserves distances and the bounds hold.
When b = c = false, the vertical difference is 0 (sub_self, zero_pow, add_zero). Thus dist(F(false, a), F(false, d))² = dist(u a, u d)², which implies dist(F(false, a), F(false, d)) = dist(u a, u d) by nlinarith with dist_nonneg. By hypothesis hf, this equals dist((false, a), (false, d)). Since F preserves distance here, non-contraction holds reflexively (le_refl), and the upper bound follows from 1 ≤ 1 / s (le_mul_of_one_le_left).
uses
Bool.false_eq_true,sub_self,zero_pow,add_zero,dist_nonneg,le_refl,le_mul_of_one_le_left· have he := hsq false false a d simp only [Bool.false_eq_true, ↓reduceIte, sub_self, zero_pow, add_zero] at he have heq : dist (F (false,a)) (F (false,d)) = dist (u a) (u d) := by nlinarith [dist_nonneg (x := F (false,a)) (y := F (false,d)), dist_nonneg (x := u a) (y := u d)] rw [hf, heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩
First point in layer 0, second point in layer 1: F preserves cross-distances.
When b = false and c = true, the vertical difference is 0 - r = -r, whose square is r² (zero_sub, neg_sq). The squared distance under F is dist(u a, u d)² + r², which equals dist((false, a), (true, d))² by hypothesis hc. Taking square roots via nlinarith with dist_nonneg gives an exact distance match, from which the bounds follow as in the first case.
uses
Bool.false_eq_true,zero_sub,neg_sq,dist_nonneg,le_refl,le_mul_of_one_le_left· have he := hsq false true a d simp only [Bool.false_eq_true, ↓reduceIte, zero_sub, neg_sq] at he have hm := hc a d have heq : dist (F (false,a)) (F (true,d)) = dist (false,a) (true,d) := by nlinarith [dist_nonneg (x := F (false,a)) (y := F (true,d)), dist_nonneg (x := (false,a)) (y := (true,d))] rw [heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩
First point in layer 1, second point in layer 0: F preserves cross-distances by symmetry.
When b = true and c = false, the vertical difference is r - 0 = r (sub_zero). Symmetrizing the cross-distance hypothesis hc using dist_comm shows that the squared distance under F again matches dist((true, a), (false, d))². Extracting the equality of distances via nlinarith with dist_nonneg yields the bounds via le_refl and le_mul_of_one_le_left.
uses
Bool.false_eq_true,sub_zero,dist_comm,dist_nonneg,le_refl,le_mul_of_one_le_left· have he := hsq true false a d simp only [Bool.false_eq_true, ↓reduceIte, sub_zero] at he have hm := hc d a rw [dist_comm (false,d) (true,a), dist_comm (u d) (u a)] at hm have heq : dist (F (true,a)) (F (false,d)) = dist (true,a) (false,d) := by nlinarith [dist_nonneg (x := F (true,a)) (y := F (false,d)), dist_nonneg (x := (true,a)) (y := (false,d))] rw [heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩
Both points in layer 1: layer 1 distance bounds give the bi-Lipschitz condition.
When b = c = true, both points have height r, so the vertical separation vanishes (sub_self, zero_pow, add_zero), giving dist(F(true, a), F(true, d)) = dist(u a, u d). Hypothesis ht provides dist((true, a), (true, d)) ≤ dist(u a, u d), ensuring non-contraction. Furthermore, ht gives s * dist(u a, u d) ≤ dist((true, a), (true, d)); dividing by s > 0 via le_div_iff₀ and rewriting 1 / s (one_div, div_eq_inv_mul, mul_comm) establishes the upper Lipschitz bound dist(F x, F y) ≤ (1 / s) * dist x y.
uses
sub_self,zero_pow,add_zero,dist_nonneg,one_div,div_eq_inv_mul,le_div_iff₀,mul_comm· have he := hsq true true a d simp only [↓reduceIte, sub_self, zero_pow, add_zero] at he have heq : dist (F (true,a)) (F (true,d)) = dist (u a) (u d) := by nlinarith [dist_nonneg (x := F (true,a)) (y := F (true,d)), dist_nonneg (x := u a) (y := u d)] rw [heq] refine ⟨(ht a d).2, ?_⟩ have h := (ht a d).1 rw [one_div, ← div_eq_inv_mul] exact (le_div_iff₀ hs).2 (by simpa [mul_comm] using h)
add_zero- Adding zero to an element leaves it unchanged.
Bool.false_eq_true- The boolean values false and true are distinct.
dist_comm- The distance between two points in a metric space is symmetric.
dist_eq_norm- The distance between two points in a normed space equals the norm of their difference.
dist_nonneg- The distance between any two points in a metric space is non-negative.
div_eq_inv_mul- Division of a by b equals b⁻¹ multiplied by a.
le_div_iff₀- For a positive divisor c, a ≤ b / c is equivalent to a * c ≤ b.
le_mul_of_one_le_left- Multiplying a non-negative quantity by a factor of at least 1 does not decrease it.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
le_refl- The less-than-or-equal relation is reflexive.
mul_comm- Multiplication is commutative.
neg_sq- The square of a negated element equals the square of the element.
one_div- The reciprocal 1 / a equals the multiplicative inverse a⁻¹.
Real.norm_eq_abs- The norm of a real number is its absolute value.
sq_abs- The square of the absolute value of a real number equals its square.
sub_self- Subtracting an element from itself yields zero.
sub_zero- Subtracting zero leaves an element unchanged.
WithLp.prod_norm_sq_eq_of_L2- In an L² product of normed spaces, the squared norm of a pair is the sum of the squared norms of its components.
zero_pow- Zero raised to any non-zero natural power is zero.
zero_sub- Subtracting an element from zero gives its negation.
- In Lean, the Euclidean direct sum H × ℝ is formalized via the type wrapper WithLp 2 (H × ℝ).
- Several intermediate equalities between distances are deduced from equalities of their squares using nlinarith and the non-negativity of distances (dist_nonneg).
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_two_layer_direct_embedding (A H : Type) [NormedAddCommGroup H] [InnerProductSpace ℝ H] (u : A → H) (r s : ℝ) (hs : 0 < s) (hs1 : s ≤ 1) (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, s * dist (u a) (u b) ≤ dist (true,a) (true,b) ∧ dist (true,a) (true,b) ≤ dist (u a) (u b)) → ∃ F : Bool × A → WithLp 2 (H × ℝ), ∀ x y, dist x y ≤ dist (F x) (F y) ∧ dist (F x) (F y) ≤ (1 / s) * dist x y := by intro hf hc ht let F : Bool × A → WithLp 2 (H × ℝ) := fun p => WithLp.toLp 2 (u p.2, if p.1 then r else 0) refine ⟨F, ?_⟩ have hs_nonneg : 0 ≤ s := le_of_lt hs have hD : 1 ≤ 1 / s := (le_div_iff₀ hs).2 (by linarith) have hsq : ∀ b c : Bool, ∀ a d : A, dist (F (b,a)) (F (c,d)) ^ 2 = dist (u a) (u d) ^ 2 + ((if b then r else 0) - (if c then r else 0)) ^ 2 := by intro b c a d rw [dist_eq_norm, WithLp.prod_norm_sq_eq_of_L2] simp [F, dist_eq_norm, Real.norm_eq_abs, sq_abs] intro ⟨b,a⟩ ⟨c,d⟩ cases b <;> cases c · have he := hsq false false a d simp only [Bool.false_eq_true, ↓reduceIte, sub_self, zero_pow, add_zero] at he have heq : dist (F (false,a)) (F (false,d)) = dist (u a) (u d) := by nlinarith [dist_nonneg (x := F (false,a)) (y := F (false,d)), dist_nonneg (x := u a) (y := u d)] rw [hf, heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩ · have he := hsq false true a d simp only [Bool.false_eq_true, ↓reduceIte, zero_sub, neg_sq] at he have hm := hc a d have heq : dist (F (false,a)) (F (true,d)) = dist (false,a) (true,d) := by nlinarith [dist_nonneg (x := F (false,a)) (y := F (true,d)), dist_nonneg (x := (false,a)) (y := (true,d))] rw [heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩ · have he := hsq true false a d simp only [Bool.false_eq_true, ↓reduceIte, sub_zero] at he have hm := hc d a rw [dist_comm (false,d) (true,a), dist_comm (u d) (u a)] at hm have heq : dist (F (true,a)) (F (false,d)) = dist (true,a) (false,d) := by nlinarith [dist_nonneg (x := F (true,a)) (y := F (false,d)), dist_nonneg (x := (true,a)) (y := (false,d))] rw [heq] exact ⟨le_refl _, le_mul_of_one_le_left dist_nonneg hD⟩ · have he := hsq true true a d simp only [↓reduceIte, sub_self, zero_pow, add_zero] at he have heq : dist (F (true,a)) (F (true,d)) = dist (u a) (u d) := by nlinarith [dist_nonneg (x := F (true,a)) (y := F (true,d)), dist_nonneg (x := u a) (y := u d)] rw [heq] refine ⟨(ht a d).2, ?_⟩ have h := (ht a d).1 rw [one_div, ← div_eq_inv_mul] exact (le_div_iff₀ hs).2 (by simpa [mul_comm] using h)