one_strongly_euclidean_union_two_sets_distortion
There exists an absolute constant C > 0 such that every metric space X that is the union of two subsets U_1, U_2, each 1-strongly Euclidean in X, embeds into a real Hilbert space with distortion at most C.
Statement
theorem one_strongly_euclidean_union_two_sets_distortion : ∃ C : ℝ, 0 < C ∧ ∀ (X : Type) [MetricSpace X] (U : Fin 2 → Set X) (_hU : (⋃ i, U i) = Set.univ) (_hE : ∀ i, IsOneStronglyEuclidean (U i)), EmbedsIntoHilbertWithDistortion X C
- Formalizes
- arXiv:2611.08546, Sec. 1.1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- IsOneStronglyEuclideanA subset U of a metric space X is 1-strongly Euclidean in X if for every point x in X, there exists a real Hilbert space H and an isometry…
- 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…
- Used by 1
- ose_universal_extension_of_isometry_extensionIf a map from a metric space into a real inner-product space extends a prescribed core map with Lipschitz constant L, then every…
Read back from the Lean
There exists a constant $C \in \mathbb{R}$ with $C > 0$ such that for every metric space $X$ (of universe level 0) and every two-subset cover $U : \mathrm{Fin}\;2 \to \mathcal{P}(X)$ of $X$ (i.e., $\bigcup_{i} U(i) = X$), if each $U(i)$ is 1-strongly Euclidean (that is, for every point $x \in X$, the subset $U(i) \cup \{x\}$ isometrically embeds into some real Hilbert space), then $X$ embeds into some real Hilbert space with distortion at most $C$ (that is, there exists a real Hilbert space $H$ and a map $f : X \to H$ such that $\mathrm{dist}(x, y) \le \mathrm{dist}(f(x), f(y)) \le C \cdot \mathrm{dist}(x, y)$ for all $x, y \in X$).
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
To embed a metric space X covered by two 1-strongly Euclidean subsets U 0 and U 1 into a Hilbert space with constant distortion, we first extend the isometric embeddings of U 0 and U 1 to 7-Lipschitz maps F₁ and F₂ on all of X via Kirszbraun's extension theorem. We then combine F₁, F₂, and the distance function D(x) = dist(x, U 1) into an embedding E(x) = (F₁(x), F₂(x), D(x)) into an ℓ₂ sum of Hilbert spaces. The distance function D bridges the two sets: for cross pairs with x ∈ U 0 and y ∈ U 1, D(x) bounds the metric distance from above, yielding an overall distortion of at most 90 after rescaling.
The squared norm ‖∑ i, c i • w i‖² expands as ∑ i, ∑ j, c i * c j * ⟨w i, w j⟩.
We express the squared norm as the self inner product using `real_inner_self_eq_norm_sq`, then expand by bilinearity (`sum_inner`, `inner_sum`, `inner_smul_left`, `inner_smul_right`).
uses
real_inner_self_eq_norm_sq,sum_inner,inner_sum,inner_smul_left,inner_smul_righthave h1 : ‖∑ i, c i • w i‖ ^ 2 = ∑ i, ∑ j, c i * c j * inner ℝ (w i) (w j) := by rw [← real_inner_self_eq_norm_sq, sum_inner] refine Finset.sum_congr rfl fun i _ => ?_ rw [inner_sum] refine Finset.sum_congr rfl fun j _ => ?_ rw [inner_smul_left, inner_smul_right] simp only [conj_trivial] ring
The double sum ∑ i, ∑ j, c i * c j * ‖w i - w j‖² decomposes into 2 ∑ i, c i * ‖w i‖² - 2 ∑ i, ∑ j, c i * c j * ⟨w i, w j⟩.
We expand ‖w i - w j‖² via `norm_sub_sq_real`. Since the weights sum to 1, summing over j gives ∑ i, c i * ‖w i‖², and by swapping summation order (`Finset.sum_comm`), summing over i gives the same for w j.
uses
norm_sub_sq_real,Finset.sum_commhave h2 : ∀ i j, ‖w i - w j‖ ^ 2 = ‖w i‖ ^ 2 - 2 * inner ℝ (w i) (w j) + ‖w j‖ ^ 2 := fun i j => norm_sub_sq_real _ _ have h3 : ∑ i, ∑ j, c i * c j * ‖w i‖ ^ 2 = ∑ i, c i * ‖w i‖ ^ 2 := by refine Finset.sum_congr rfl fun i _ => ?_ rw [← Finset.sum_mul, ← Finset.mul_sum, hc, mul_one] have h4 : ∑ i, ∑ j, c i * c j * ‖w j‖ ^ 2 = ∑ j, c j * ‖w j‖ ^ 2 := by rw [Finset.sum_comm] refine Finset.sum_congr rfl fun j _ => ?_ rw [← Finset.sum_mul, ← Finset.sum_mul, hc, one_mul] have h5 : ∀ i j, c i * c j * ‖w i - w j‖ ^ 2 = c i * c j * ‖w i‖ ^ 2 - 2 * (c i * c j * inner ℝ (w i) (w j)) + c i * c j * ‖w j‖ ^ 2 := fun i j => by rw [h2]; ring
The variance identity ∑ i, ∑ j, c i * c j * ‖w i - w j‖² = 2 ∑ i, c i * ‖w i‖² - 2 ‖∑ i, c i • w i‖² holds.
Substituting the inner product expansion of ‖∑ i, c i • w i‖² into the expanded double sum and rearranging algebraically completes the identity.
rw [h1] simp_rw [h5, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.mul_sum] rw [h3, h4] ring
The continuous objective g(c) = ∑ c_i a_i - ‖∑ c_i y_i‖² achieves its maximum on the standard simplex at some point c, defining p = ∑ c_i y_i and A = ∑ c_i a_i.
Let v_i = x_i - z and a_i = ‖y_i‖² - L² ‖v_i‖². Since the simplex is compact (`isCompact_stdSimplex`), the continuous function g attains a maximum c, with p and A defined accordingly.
uses
isCompact_stdSimplexclassical let v : ι → E := fun i => x i - z let a : ι → ℝ := fun i => ‖y i‖ ^ 2 - L ^ 2 * ‖v i‖ ^ 2 let g : (ι → ℝ) → ℝ := fun c => ∑ i, c i * a i - ‖∑ i, c i • y i‖ ^ 2 have hg : Continuous g := by apply Continuous.sub · exact continuous_finsetSum _ fun i _ => (continuous_apply i).mul continuous_const · exact (continuous_norm.comp (continuous_finsetSum _ fun i _ => (continuous_apply i).smul continuous_const)).pow 2 obtain ⟨c, hc, hmax⟩ := (isCompact_stdSimplex ℝ ι).exists_isMaxOn ⟨_, single_mem_stdSimplex ℝ (Classical.arbitrary ι)⟩ hg.continuousOn have hcsum : ∑ i, c i = 1 := hc.2 have hc0 : ∀ i, 0 ≤ c i := hc.1 set p : F := ∑ i, c i • y i with hp set A : ℝ := ∑ i, c i * a i with hA
The maximum value A - ‖p‖² is non-positive.
Applying the variance identity `ose_var_identity` to both y and v together with the Lipschitz condition ‖y_i - y_j‖ ≤ L ‖v_i - v_j‖ shows that 2 A - 2 ‖p‖² ≤ -2 L² ‖∑ c_i v_i‖² ≤ 0.
uses
ose_var_identity-- the value at the maximum is nonpositive have hval : A - ‖p‖ ^ 2 ≤ 0 := by have e1 := ose_var_identity c hcsum y have e2 := ose_var_identity c hcsum v have hle : ∑ i, ∑ j, c i * c j * ‖y i - y j‖ ^ 2 ≤ ∑ i, ∑ j, c i * c j * (L ^ 2 * ‖v i - v j‖ ^ 2) := by refine Finset.sum_le_sum fun i _ => Finset.sum_le_sum fun j _ => ?_ refine mul_le_mul_of_nonneg_left ?_ (mul_nonneg (hc0 i) (hc0 j)) have hvv : v i - v j = x i - x j := by simp [v] rw [hvv] calc ‖y i - y j‖ ^ 2 ≤ (L * ‖x i - x j‖) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) (h i j) 2 _ = L ^ 2 * ‖x i - x j‖ ^ 2 := by ring have e3 : ∑ i, ∑ j, c i * c j * (L ^ 2 * ‖v i - v j‖ ^ 2) = L ^ 2 * ∑ i, ∑ j, c i * c j * ‖v i - v j‖ ^ 2 := by simp_rw [Finset.mul_sum] refine Finset.sum_congr rfl fun i _ => Finset.sum_congr rfl fun j _ => ?_ ring have e4 : A = ∑ i, c i * ‖y i‖ ^ 2 - L ^ 2 * ∑ i, c i * ‖v i‖ ^ 2 := by rw [hA, Finset.mul_sum, ← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun i _ => ?_ simp only [a] ring have e5 : 0 ≤ L ^ 2 * ‖∑ i, c i • v i‖ ^ 2 := by positivity rw [e3, e2] at hle rw [e1] at hle rw [e4] nlinarith
The first-order optimality condition a_j - A - 2 ⟨p, y_j - p⟩ ≤ 0 holds for every index j.
If this quantity S were positive, perturbing c towards the vertex j along the simplex (`convex_stdSimplex`) by t = S / (S + ‖y_j - p‖² + 1) would strictly increase g(c), contradicting maximality.
uses
convex_stdSimplexrefine ⟨p, fun j => ?_⟩ -- first-order condition at `j` have hfirst : a j - A - 2 * inner ℝ p (y j - p) ≤ 0 := by by_contra hcon rw [not_le] at hcon set S := a j - A - 2 * inner ℝ p (y j - p) with hS set M := ‖y j - p‖ ^ 2 with hM have hM0 : 0 ≤ M := by positivity set t : ℝ := S / (S + M + 1) with ht have hden : 0 < S + M + 1 := by linarith have ht0 : 0 < t := div_pos hcon hden have ht1 : t ≤ 1 := by rw [ht, div_le_one hden]; linarith have htM : t * M < S := by rw [ht, div_mul_eq_mul_div, div_lt_iff₀ hden] nlinarith let c' : ι → ℝ := (1 - t) • c + t • Pi.single j (1 : ℝ) have hc' : c' ∈ stdSimplex ℝ ι := convex_stdSimplex ℝ ι hc (single_mem_stdSimplex ℝ j) (by linarith) ht0.le (by ring) have hle := hmax hc' have e1 : ∑ i, c' i * a i = (1 - t) * A + t * a j := by simp only [c', Pi.add_apply, Pi.smul_apply, smul_eq_mul, add_mul, Finset.sum_add_distrib] rw [hA, Finset.mul_sum] congr 1 · exact Finset.sum_congr rfl fun i _ => by ring · simp [Pi.single_apply] have e2 : ∑ i, c' i • y i = p + t • (y j - p) := by simp only [c', Pi.add_apply, Pi.smul_apply, smul_eq_mul, add_smul, Finset.sum_add_distrib, mul_smul] rw [← Finset.smul_sum, ← Finset.smul_sum, ← hp] simp only [Pi.single_apply, ite_smul, one_smul, zero_smul, Finset.sum_ite_eq', Finset.mem_univ, if_true] simp only [smul_sub, sub_smul, one_smul] abel have e3 : ‖p + t • (y j - p)‖ ^ 2 = ‖p‖ ^ 2 + 2 * t * inner ℝ p (y j - p) + t ^ 2 * M := by rw [norm_add_sq_real, inner_smul_right, norm_smul, mul_pow, Real.norm_eq_abs, sq_abs] ring have hle' : (1 - t) * A + t * a j - ‖p + t • (y j - p)‖ ^ 2 ≤ A - ‖p‖ ^ 2 := by have := hle simp only [Set.mem_ofPred_eq, g] at this rw [e1, e2] at this exact this rw [e3] at hle' have : t * S ≤ t * (t * M) := by have : t * S = t * a j - t * A - 2 * t * inner ℝ p (y j - p) := by rw [hS]; ring nlinarith have := le_of_mul_le_mul_left this ht0 linarith
The point p satisfies ‖p - y_j‖ ≤ L ‖z - x_j‖ for all j.
Expanding ‖p - y_j‖² using `norm_sub_sq_real` and combining with the first-order condition and A - ‖p‖² ≤ 0 gives ‖p - y_j‖² ≤ L² ‖z - x_j‖². Taking square roots via `pow_le_pow_iff_left₀` proves the bound.
uses
norm_sub_sq_real,norm_sub_rev,pow_le_pow_iff_left₀-- conclude have hsq : ‖p - y j‖ ^ 2 ≤ (L * ‖z - x j‖) ^ 2 := by have e1 : ‖p - y j‖ ^ 2 = ‖y j‖ ^ 2 - 2 * inner ℝ (y j) p + ‖p‖ ^ 2 := by rw [norm_sub_rev, norm_sub_sq_real] have e2 : inner ℝ p (y j - p) = inner ℝ (y j) p - ‖p‖ ^ 2 := by rw [inner_sub_right, real_inner_comm, real_inner_self_eq_norm_sq] have e3 : ‖v j‖ = ‖z - x j‖ := by simp [v, norm_sub_rev] have e4 : a j = ‖y j‖ ^ 2 - L ^ 2 * ‖z - x j‖ ^ 2 := by simp only [a, e3] rw [mul_pow] rw [e2, e4] at hfirst nlinarith exact (pow_le_pow_iff_left₀ (norm_nonneg _) (mul_nonneg hL (norm_nonneg _)) (by norm_num)).1 hsq
For every finite s ⊆ I, the intersection of closed balls C(s) is non-empty, closed, convex, and has a unique element m(s) of minimal norm.
If I is empty the claim is trivial. Otherwise, each C(s) is an intersection of closed convex balls, non-empty by assumption. In a complete Hilbert space, every non-empty closed convex set contains a unique point minimizing the norm.
uses
dist_eq_normclassical by_cases hI : Nonempty I swap · exact ⟨0, fun i => (hI ⟨i⟩).elim⟩ obtain ⟨i₀⟩ := hI let C : Finset I → Set F := fun s => ⋂ i ∈ s, Metric.closedBall (y i) (ρ i) have hmemC : ∀ s p, p ∈ C s ↔ ∀ i ∈ s, ‖p - y i‖ ≤ ρ i := by intro s p simp [C, Metric.mem_closedBall, dist_eq_norm] have hCne : ∀ s, (C s).Nonempty := fun s => by obtain ⟨p, hp⟩ := h s exact ⟨p, (hmemC s p).2 hp⟩ have hCclosed : ∀ s, IsClosed (C s) := fun s => isClosed_biInter fun i _ => Metric.isClosed_closedBall have hCconv : ∀ s, Convex ℝ (C s) := fun s => convex_iInter₂ fun i _ => convex_closedBall _ _ have hmin : ∀ s, ∃ m ∈ C s, ∀ w ∈ C s, ‖m‖ ≤ ‖w‖ := by intro s obtain ⟨m, hm, hmeq⟩ := exists_norm_eq_iInf_of_complete_convex (hCne s) (hCclosed s).isComplete (hCconv s) (0 : F) refine ⟨m, hm, fun w hw => ?_⟩ have hb : BddBelow (Set.range fun w : C s => ‖(0 : F) - w‖) := ⟨0, by rintro _ ⟨w, rfl⟩; exact norm_nonneg _⟩ have := ciInf_le hb (⟨w, hw⟩ : C s) simp only [zero_sub, norm_neg] at hmeq this linarith choose m hmC hmmin using hmin
The net of minimal-norm points s ↦ m(s) is Cauchy along the directed system of finite subsets of I.
The norms ‖m(s)‖ are monotonically increasing with s and bounded above. Applying the parallelogram law `parallelogram_law_with_norm` to m(n) and m(N) with N ⊆ n shows ‖m(n) - m(N)‖² ≤ 2(S - ‖m(N)‖²), which is arbitrarily small for N sufficiently close to the supremum S.
uses
parallelogram_law_with_norm,pow_le_pow_left₀,dist_eq_normhave hsub : ∀ {s t : Finset I}, s ⊆ t → C t ⊆ C s := by intro s t hst p hp exact (hmemC s p).2 fun i hi => (hmemC t p).1 hp i (hst hi) have hmono : ∀ {s t : Finset I}, s ⊆ t → ‖m s‖ ≤ ‖m t‖ := fun hst => hmmin _ _ (hsub hst (hmC _)) have hbd : ∀ s, ‖m s‖ ≤ ‖y i₀‖ + ρ i₀ := by intro s have h1 : ‖m s‖ ≤ ‖m (insert i₀ s)‖ := hmono (Finset.subset_insert _ _) have h2 := (hmemC _ _).1 (hmC (insert i₀ s)) i₀ (Finset.mem_insert_self _ _) have h3 : ‖m (insert i₀ s)‖ ≤ ‖m (insert i₀ s) - y i₀‖ + ‖y i₀‖ := by simpa using norm_add_le (m (insert i₀ s) - y i₀) (y i₀) linarith have hbdd : BddAbove (Set.range fun s => ‖m s‖ ^ 2) := by refine ⟨(‖y i₀‖ + ρ i₀) ^ 2, ?_⟩ rintro _ ⟨s, rfl⟩ exact pow_le_pow_left₀ (norm_nonneg _) (hbd s) 2 set S : ℝ := ⨆ s, ‖m s‖ ^ 2 with hS have hcauchy : CauchySeq m := by rw [Metric.cauchySeq_iff'] intro ε hε have hlt : S - ε ^ 2 / 2 < S := by nlinarith [sq_pos_of_pos hε] obtain ⟨N, hN⟩ := exists_lt_of_lt_ciSup hlt refine ⟨N, fun n hn => ?_⟩ have hNn : N ⊆ n := hn have hmid : (1 / 2 : ℝ) • m n + (1 / 2 : ℝ) • m N ∈ C N := hCconv N (hsub hNn (hmC n)) (hmC N) (by norm_num) (by norm_num) (by norm_num) have h1 := hmmin N _ hmid have h2 : (1 / 2 : ℝ) • m n + (1 / 2 : ℝ) • m N = (1 / 2 : ℝ) • (m n + m N) := by rw [smul_add] rw [h2, norm_smul] at h1 simp only [Real.norm_eq_abs, abs_of_pos (by norm_num : (0 : ℝ) < 1 / 2)] at h1 have h3 := parallelogram_law_with_norm ℝ (m n) (m N) have hle : ‖m n‖ ^ 2 ≤ S := le_ciSup hbdd n have h4 : 2 * ‖m N‖ ≤ ‖m n + m N‖ := by linarith have h5 : (2 * ‖m N‖) * (2 * ‖m N‖) ≤ ‖m n + m N‖ * ‖m n + m N‖ := mul_self_le_mul_self (by positivity) h4 have h6 : ‖m n - m N‖ ^ 2 < ε ^ 2 := by nlinarith rw [dist_eq_norm] exact lt_of_pow_lt_pow_left₀ 2 hε.le h6 obtain ⟨p, hp⟩ := cauchySeq_tendsto_of_complete hcauchy
The limit p of m(s) lies in every ball Metric.closedBall (y i) (ρ i).
By completeness, m(s) converges to p (`cauchySeq_tendsto_of_complete`). For each i, m(s) eventually belongs to the closed ball centered at y i, so p belongs to it as well.
uses
cauchySeq_tendsto_of_complete,dist_eq_normrefine ⟨p, fun i => ?_⟩ have hev : ∀ᶠ s in Filter.atTop, m s ∈ Metric.closedBall (y i) (ρ i) := by filter_upwards [Filter.eventually_ge_atTop ({i} : Finset I)] with s hs have := (hmemC s (m s)).1 (hmC s) i (hs (Finset.mem_singleton_self i)) simpa [Metric.mem_closedBall, dist_eq_norm] using this have := Metric.isClosed_closedBall.mem_of_tendsto hp hev simpa [Metric.mem_closedBall, dist_eq_norm] using this
Any L-Lipschitz map on a subset G ⊆ E × F extends to a given single point z ∈ E.
By `ose_kirszbraun_finite`, every finite subcollection of distance constraints has a solution. Applying `ose_fip` yields a common point p in Hilbert space satisfying all constraints simultaneously.
uses
ose_kirszbraun_finite,ose_fipobtain ⟨p, hp⟩ := ose_fip (I := G) (fun q => q.1.2) (fun q => L * ‖z - q.1.1‖) (by intro s by_cases hs : Nonempty s · obtain ⟨p, hp⟩ := ose_kirszbraun_finite (ι := s) L hL (fun i => i.1.1.1) (fun i => i.1.1.2) z (fun i j => hG _ i.1.2 _ j.1.2) exact ⟨p, fun i hi => hp ⟨i, hi⟩⟩ · exact ⟨0, fun i hi => (hs ⟨⟨i, hi⟩⟩).elim⟩) exact ⟨p, fun q hq => hp ⟨q, hq⟩⟩
Any L-Lipschitz map from a subset of E to a complete Hilbert space F extends to an L-Lipschitz map on all of E.
We consider the family of L-Lipschitz extensions ordered by graph inclusion. By Zorn's lemma (`zorn_subset_nonempty`), there exists a maximal extension K. If K were not defined on all of E, `ose_one_point` would extend it to an additional point, contradicting maximality.
uses
zorn_subset_nonempty,ose_one_point,norm_sub_revclassical let P : Set (Set (E × F)) := {K | ∀ q ∈ K, ∀ q' ∈ K, ‖q.2 - q'.2‖ ≤ L * ‖q.1 - q'.1‖} obtain ⟨K, hGK, hK⟩ := zorn_subset_nonempty P (by intro c hcP hchain hne refine ⟨⋃₀ c, ?_, fun s hs => Set.subset_sUnion_of_mem hs⟩ rintro q ⟨s, hs, hq⟩ q' ⟨s', hs', hq'⟩ rcases hchain.total hs hs' with hss | hss · exact hcP hs' _ (hss hq) _ hq' · exact hcP hs _ hq _ (hss hq')) G hG have hKP : K ∈ P := hK.prop have hall : ∀ u : E, ∃ w : F, (u, w) ∈ K := by intro u obtain ⟨p, hp⟩ := ose_one_point L hL K hKP u refine ⟨p, ?_⟩ have hins : insert (u, p) K ∈ P := by rintro q (rfl | hq) q' (rfl | hq') · simp · simpa using hp q' hq' · have := hp q hq rw [norm_sub_rev p, norm_sub_rev u] at this simpa using this · exact hKP _ hq _ hq' exact hK.le_of_ge hins (Set.subset_insert _ _) (Set.mem_insert _ _) choose T hT using hall refine ⟨T, fun q hq => ?_, fun u v => hKP _ (hT u) _ (hT v)⟩ have := hKP _ (hT q.1) _ (hGK hq) simp only [sub_self, norm_zero, mul_zero] at this exact sub_eq_zero.1 (norm_le_zero_iff.1 this)
The transport map g satisfies dist(g y, g y') ≤ dist y y' + 2 * Metric.infDist y A.
Using the triangle inequality on H₁ and the hypothesis that dist(g y, φ a) ≤ dist y a for all a ∈ A, we take the infimum over a ∈ A via `Metric.le_infDist`.
uses
Metric.infDist_nonneg,Metric.infDist_le_infDist_add_dist,Metric.le_infDist,dist_triangle,dist_commclassical let r : X → ℝ := fun y => Metric.infDist y A have hr0 : ∀ y, 0 ≤ r y := fun y => Metric.infDist_nonneg have hrA : ∀ y, ∀ a ∈ A, r y ≤ dist y a := fun y a ha => Metric.infDist_le_dist_of_mem ha have hrL : ∀ y y', r y ≤ r y' + dist y y' := fun y y' => Metric.infDist_le_infDist_add_dist have hgg : ∀ y y', dist (g y) (g y') ≤ dist y y' + 2 * r y := by intro y y' have : (dist (g y) (g y') - dist y y') / 2 ≤ r y := by refine (Metric.le_infDist hA).2 fun a ha => ?_ have h1 := dist_triangle_right (g y) (g y') (φ a) have h2 := hg y a ha have h3 := hg y' a ha have h4 := dist_triangle y' y a rw [dist_comm y' y] at h4 linarith linarith
There exists a maximal 2-separated net N ⊆ B such that every y ∈ B is within distance Metric.infDist y A of some net point.
By Zorn's lemma (`zorn_subset_nonempty`), there is a maximal subset N ⊆ B satisfying r(y) ≤ 2 dist(y, y') for all distinct y, y' ∈ N. By maximality, every point of B is within distance r(y) of some point in N.
uses
zorn_subset_nonempty,dist_commobtain ⟨N, -, hN⟩ := zorn_subset_nonempty {N : Set X | N ⊆ B ∧ ∀ y ∈ N, ∀ y' ∈ N, y ≠ y' → r y ≤ 2 * dist y y'} (by intro c hcP hchain hne refine ⟨⋃₀ c, ⟨?_, ?_⟩, fun s hs => Set.subset_sUnion_of_mem hs⟩ · rintro y ⟨s, hs, hy⟩ exact (hcP hs).1 hy · rintro y ⟨s, hs, hy⟩ y' ⟨s', hs', hy'⟩ hne rcases hchain.total hs hs' with hss | hss · exact (hcP hs').2 _ (hss hy) _ hy' hne · exact (hcP hs).2 _ hy _ (hss hy') hne) ∅ ⟨by simp, by simp⟩ have hNB : N ⊆ B := hN.prop.1 have hNsep := hN.prop.2 have hNcov : ∀ y ∈ B, ∃ y0 ∈ N, dist y y0 ≤ r y := by intro y hy by_cases hyN : y ∈ N · exact ⟨y, hyN, by simpa using hr0 y⟩ · have hnot : ¬ (insert y N ⊆ B ∧ ∀ u ∈ insert y N, ∀ v ∈ insert y N, u ≠ v → r u ≤ 2 * dist u v) := by intro hins exact hyN (hN.le_of_ge hins (Set.subset_insert _ _) (Set.mem_insert _ _)) have hsubB : insert y N ⊆ B := Set.insert_subset hy hNB have : ∃ u ∈ insert y N, ∃ v ∈ insert y N, u ≠ v ∧ 2 * dist u v < r u := by by_contra hcon refine hnot ⟨hsubB, fun u hu v hv huv => ?_⟩ by_contra hlt exact hcon ⟨u, hu, v, hv, huv, not_le.1 hlt⟩ obtain ⟨u, hu, v, hv, huv, hlt⟩ := this rcases hu with rfl | hu <;> rcases hv with rfl | hv · exact (huv rfl).elim · exact ⟨v, hv, by linarith [dist_nonneg (x := u) (y := v)]⟩ · refine ⟨u, hu, ?_⟩ have := hrL u v rw [dist_comm v u] linarith · exact absurd hlt (not_lt.2 (hNsep u hu v hv huv)) let G : Set (H₂ × H₁) := (fun y => (ψ y, g y)) '' N
The map g on N extends to a 5-Lipschitz map T : H₂ → H₁.
On N, the separation condition implies dist(g y, g y') ≤ 5 dist(y, y') = 5 dist(ψ y, ψ y'). By Kirszbraun's extension theorem `ose_kirszbraun`, this extends to a 5-Lipschitz map T on all of H₂.
uses
dist_eq_norm,ose_kirszbraunhave hG : ∀ q ∈ G, ∀ q' ∈ G, ‖q.2 - q'.2‖ ≤ 5 * ‖q.1 - q'.1‖ := by rintro _ ⟨y, hy, rfl⟩ _ ⟨y', hy', rfl⟩ show ‖g y - g y'‖ ≤ 5 * ‖ψ y - ψ y'‖ rw [← dist_eq_norm, ← dist_eq_norm, hψ y (hNB hy) y' (hNB hy')] by_cases hyy : y = y' · subst hyy simp · have := hNsep y hy y' hy' hyy have := hgg y y' linarith obtain ⟨T, hT, hTL⟩ := ose_kirszbraun 5 (by norm_num) G hG have hTN : ∀ y ∈ N, T (ψ y) = g y := fun y hy => hT (ψ y, g y) ⟨y, hy, rfl⟩ have hTd : ∀ y ∈ B, ∀ y' ∈ B, dist (T (ψ y)) (T (ψ y')) ≤ 5 * dist y y' := by intro y hy y' hy' rw [dist_eq_norm, ← hψ y hy y' hy', dist_eq_norm] exact hTL _ _
For all y ∈ B and a ∈ A, dist(T (ψ y), φ a) ≤ 7 * dist y a.
Approximating y by its nearest net point y₀ ∈ N and applying the triangle inequality together with the Lipschitz bound on T and the transport property of g gives dist(T (ψ y), φ a) ≤ 7 dist(y, a).
uses
dist_triangle,dist_comm-- the cross estimate have hcross : ∀ y ∈ B, ∀ a ∈ A, dist (T (ψ y)) (φ a) ≤ 7 * dist y a := by intro y hy a ha obtain ⟨y0, hy0, hd⟩ := hNcov y hy have h1 := hTd y hy y0 (hNB hy0) rw [hTN y0 hy0] at h1 have h2 := hg y0 a ha have h3 := dist_triangle y0 y a rw [dist_comm y0 y] at h3 have h4 := hrA y a ha have h5 := dist_triangle (T (ψ y)) (g y0) (φ a) linarith
The combined map F : X → H₁, equal to φ on A and T ∘ ψ on B \ A, is 7-Lipschitz.
We check the Lipschitz bound by cases on whether points belong to A or B \ A. On A, F is an isometry; on B \ A, F is 5-Lipschitz; across A and B \ A, the cross estimate gives Lipschitz constant 7.
uses
dist_commrefine ⟨fun x => if x ∈ A then φ x else T (ψ x), fun a ha => by simp [ha], fun x y => ?_⟩ by_cases hx : x ∈ A <;> by_cases hy : y ∈ A · simp only [hx, hy, if_true] rw [hφ x hx y hy] linarith [dist_nonneg (x := x) (y := y)] · simp only [hx, hy, if_true, if_false] have hyB : y ∈ B := (hAB y).resolve_left hy have := hcross y hyB x hx rw [dist_comm, dist_comm x y] exact this · simp only [hx, hy, if_true, if_false] exact hcross x ((hAB x).resolve_left hx) y hy · simp only [hx, hy, if_false] have := hTd x ((hAB x).resolve_left hx) y ((hAB y).resolve_left hy) linarith [dist_nonneg (x := x) (y := y)]
Any 1-strongly Euclidean subset A isometrically embeds into a complete Hilbert space.
If A is empty, the zero map to ℝ works. If A is non-empty, picking a point a₀ ∈ A gives an isometric embedding of A ∪ {a₀} = A into a complete Hilbert space by definition.
classical rcases A.eq_empty_or_nonempty with rfl | ⟨a₀, ha₀⟩ · exact ⟨ℝ, inferInstance, inferInstance, inferInstance, fun _ => 0, by simp⟩ · obtain ⟨H, i1, i2, i3, f, hf⟩ := hE a₀ refine ⟨H, i1, i2, i3, fun x => if h : x ∈ A then f ⟨x, Or.inl h⟩ else 0, ?_⟩ intro a ha a' ha' simp only [ha, ha', dif_pos] exact hf.dist_eq _ _
For every y ∈ X, there exists a transport point p ∈ H satisfying dist(p, φ a) ≤ dist(y, a) for all a ∈ A.
By 1-strong Euclideanness on A ∪ {y}, there is an isometric embedding into a Hilbert space K. Applying `ose_one_point` with L = 1 to the graph of φ ∘ f⁻¹ gives the desired point p.
uses
ose_one_point,dist_eq_norm∃ p : H, ∀ a ∈ A, dist p (φ a) ≤ dist y a := by obtain ⟨K, i1, i2, i3, f, hf⟩ := hE y let G : Set (K × H) := (fun a : A => (f ⟨a.1, Or.inl a.2⟩, φ a.1)) '' Set.univ obtain ⟨p, hp⟩ := ose_one_point 1 zero_le_one G (by rintro _ ⟨a, -, rfl⟩ _ ⟨a', -, rfl⟩ show ‖φ a.1 - φ a'.1‖ ≤ 1 * ‖f _ - f _‖ rw [← dist_eq_norm, ← dist_eq_norm, hf.dist_eq, hφ _ a.2 _ a'.2, one_mul] rfl) (f ⟨y, Or.inr (Set.mem_singleton y)⟩) refine ⟨p, fun a ha => ?_⟩ have := hp _ ⟨⟨a, ha⟩, trivial, rfl⟩ simp only [one_mul] at this rw [dist_eq_norm] refine this.trans (le_of_eq ?_) rw [← dist_eq_norm, hf.dist_eq] rfl
Every point in X belongs to U 0 or U 1.
We choose distortion bound C = 90. Since U 0 ∪ U 1 covers X, every point x lies in U 0 or U 1.
classical refine ⟨90, by norm_num, ?_⟩ intro X _ U hU hE have hcov : ∀ x, x ∈ U 0 ∨ x ∈ U 1 := by intro x have : x ∈ ⋃ i, U i := hU ▸ Set.mem_univ x obtain ⟨i, hi⟩ := Set.mem_iUnion.1 this fin_cases i · exact Or.inl hi · exact Or.inr hi
There exist 7-Lipschitz extensions F₁ : X → H₁ and F₂ : X → H₂ of the isometric embeddings of U 0 and U 1.
Using `ose_euclidean_part`, `ose_transport`, and `ose_extend`, we construct 7-Lipschitz extensions F₁ and F₂ of the isometric embeddings of U 0 and U 1.
uses
ose_euclidean_part,ose_transport,ose_extendobtain ⟨H₁, i1, i2, i3, φ, hφ⟩ := ose_euclidean_part (U 0) (hE 0) obtain ⟨H₂, j1, j2, j3, ψ, hψ⟩ := ose_euclidean_part (U 1) (hE 1) have hext1 : ∃ F : X → H₁, (∀ a ∈ U 0, F a = φ a) ∧ ∀ x y, dist (F x) (F y) ≤ 7 * dist x y := by rcases (U 0).eq_empty_or_nonempty with he | hne · exact ⟨fun _ => 0, by simp [he], fun x y => by simp [dist_nonneg]⟩ · choose g hg using ose_transport (U 0) (hE 0) φ hφ exact ose_extend (U 0) (U 1) hcov φ hφ ψ hψ g hg hne have hext2 : ∃ F : X → H₂, (∀ a ∈ U 1, F a = ψ a) ∧ ∀ x y, dist (F x) (F y) ≤ 7 * dist x y := by rcases (U 1).eq_empty_or_nonempty with he | hne · exact ⟨fun _ => 0, by simp [he], fun x y => by simp [dist_nonneg]⟩ · choose g hg using ose_transport (U 1) (hE 1) ψ hψ exact ose_extend (U 1) (U 0) (fun x => (hcov x).symm) ψ hψ φ hφ g hg hne obtain ⟨F₁, hF₁, hL₁⟩ := hext1 obtain ⟨F₂, hF₂, hL₂⟩ := hext2 let D : X → ℝ := fun x => Metric.infDist x (U 1)
The distance function D(x) = Metric.infDist x (U 1) is 1-Lipschitz.
This is the standard 1-Lipschitz property of infimal distance (`Metric.infDist_le_infDist_add_dist`, `abs_le`).
uses
Metric.infDist_le_infDist_add_dist,dist_comm,abs_lehave hD : ∀ x y, |D x - D y| ≤ dist x y := by intro x y have h1 : D x ≤ D y + dist x y := Metric.infDist_le_infDist_add_dist have h2 : D y ≤ D x + dist y x := Metric.infDist_le_infDist_add_dist rw [dist_comm y x] at h2 exact abs_le.2 ⟨by linarith, by linarith⟩
The map E(x) = (F₁ x, F₂ x, D x) into the ℓ₂ product space satisfies ‖E x - E y‖² = ‖F₁ x - F₁ y‖² + ‖F₂ x - F₂ y‖² + |D x - D y|².
By definition of the ℓ₂ norm on product spaces (`WithLp.prod_norm_sq_eq_of_L2`).
uses
WithLp.prod_norm_sq_eq_of_L2let E : X → WithLp 2 (WithLp 2 (H₁ × H₂) × ℝ) := fun x => WithLp.toLp 2 (WithLp.toLp 2 (F₁ x, F₂ x), D x) have hEsq : ∀ x y, ‖E x - E y‖ ^ 2 = ‖F₁ x - F₁ y‖ ^ 2 + ‖F₂ x - F₂ y‖ ^ 2 + |D x - D y| ^ 2 := by intro x y rw [WithLp.prod_norm_sq_eq_of_L2] simp only [E, WithLp.prod_norm_sq_eq_of_L2] simp
E is 10-Lipschitz: ‖E x - E y‖ ≤ 10 * dist x y.
Summing the squared Lipschitz bounds 49 + 49 + 1 = 99 ≤ 100 on the three components and taking square roots shows E has Lipschitz constant at most 10.
uses
dist_eq_norm,pow_le_pow_left₀,pow_le_pow_iff_left₀have hUB : ∀ x y, ‖E x - E y‖ ≤ 10 * dist x y := by intro x y have h1 := hL₁ x y have h2 := hL₂ x y have h3 := hD x y rw [dist_eq_norm] at h1 h2 have hd := dist_nonneg (x := x) (y := y) have s1 : ‖F₁ x - F₁ y‖ ^ 2 ≤ (7 * dist x y) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) h1 2 have s2 : ‖F₂ x - F₂ y‖ ^ 2 ≤ (7 * dist x y) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) h2 2 have s3 : |D x - D y| ^ 2 ≤ dist x y ^ 2 := pow_le_pow_left₀ (abs_nonneg _) h3 2 have : ‖E x - E y‖ ^ 2 ≤ (10 * dist x y) ^ 2 := by rw [hEsq] nlinarith exact (pow_le_pow_iff_left₀ (norm_nonneg _) (by positivity) (by norm_num)).1 this
Each coordinate difference is bounded by the total norm ‖E x - E y‖.
Since ‖E x - E y‖² is the sum of three non-negative squares, each component difference is bounded by ‖E x - E y‖ via `pow_le_pow_iff_left₀`.
uses
pow_le_pow_iff_left₀have hc1 : ∀ x y, ‖F₁ x - F₁ y‖ ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (norm_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₂ x - F₂ y‖, sq_nonneg |D x - D y|] have hc2 : ∀ x y, ‖F₂ x - F₂ y‖ ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (norm_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₁ x - F₁ y‖, sq_nonneg |D x - D y|] have hc3 : ∀ x y, |D x - D y| ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (abs_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₁ x - F₁ y‖, sq_nonneg ‖F₂ x - F₂ y‖] -- the cross pairs
For cross pairs x ∈ U 0 and y ∈ U 1, dist x y ≤ 9 * ‖E x - E y‖.
Since y ∈ U 1, D(y) = 0, so D(x) ≤ ‖E x - E y‖. For any b ∈ U 1, the triangle inequality gives dist(x, y) - ‖F₂ x - F₂ y‖ ≤ 8 dist(x, b). Taking the infimum over b via `Metric.le_infDist` gives dist(x, y) ≤ ‖F₂ x - F₂ y‖ + 8 D(x) ≤ 9 ‖E x - E y‖.
uses
Metric.infDist_zero_of_mem,Metric.le_infDist,dist_triangle,dist_comm,dist_eq_norm,abs_of_nonneg,Metric.infDist_nonneghave hcross : ∀ x ∈ U 0, ∀ y ∈ U 1, dist x y ≤ 9 * ‖E x - E y‖ := by intro x hx y hy have hDy : D y = 0 := Metric.infDist_zero_of_mem hy have hmain : (dist x y - ‖F₂ x - F₂ y‖) / 8 ≤ D x := by refine (Metric.le_infDist ⟨y, hy⟩).2 fun b hb => ?_ have h1 := dist_triangle x b y have h2 : dist b y = dist (F₂ b) (F₂ y) := by rw [hF₂ b hb, hF₂ y hy, hψ b hb y hy] have h3 := dist_triangle (F₂ b) (F₂ x) (F₂ y) have h4 := hL₂ b x rw [dist_comm b x] at h4 rw [dist_eq_norm (F₂ x) (F₂ y)] at h3 linarith have h1 := hc2 x y have h2 := hc3 x y rw [hDy, sub_zero, abs_of_nonneg Metric.infDist_nonneg] at h2 linarith
For all x, y ∈ X, dist x y ≤ 9 * ‖E x - E y‖.
If both points lie in U 0 or both in U 1, the isometric property of F₁ or F₂ bounds the distance by ‖E x - E y‖. If one is in U 0 and the other in U 1, the cross-pair estimate applies.
uses
dist_comm,norm_sub_rev,dist_eq_normhave hLB : ∀ x y, dist x y ≤ 9 * ‖E x - E y‖ := by intro x y have hnn := norm_nonneg (E x - E y) rcases hcov x with hx | hx <;> rcases hcov y with hy | hy · have := hc1 x y rw [hF₁ x hx, hF₁ y hy, ← dist_eq_norm, hφ x hx y hy] at this linarith · exact hcross x hx y hy · have := hcross y hy x hx rw [dist_comm, norm_sub_rev] exact this · have := hc2 x y rw [hF₂ x hx, hF₂ y hy, ← dist_eq_norm, hψ x hx y hy] at this linarith
The scaled map 9 • E embeds X into a real Hilbert space with distortion at most 90.
Multiplying E by 9 scales distances so that dist(x, y) ≤ dist(9 • E x, 9 • E y) ≤ 90 dist(x, y), giving distortion at most 90.
uses
dist_eq_norm,smul_sub,norm_smulrefine ⟨WithLp 2 (WithLp 2 (H₁ × H₂) × ℝ), inferInstance, inferInstance, inferInstance, fun x => (9 : ℝ) • E x, fun x y => ?_⟩ have hs : dist ((9 : ℝ) • E x) ((9 : ℝ) • E y) = 9 * ‖E x - E y‖ := by rw [dist_eq_norm, ← smul_sub, norm_smul] norm_num rw [hs] exact ⟨hLB x y, by linarith [hUB x y]⟩
real_inner_self_eq_norm_sq- For any x in an inner product space over ℝ, ⟨x, x⟩ = ‖x‖².
sum_inner- The inner product is additive in the first argument: ⟨∑ i ∈ s, f i, x⟩ = ∑ i ∈ s, ⟨f i, x⟩.
inner_sum- The inner product is additive in the second argument: ⟨x, ∑ i ∈ s, f i⟩ = ∑ i ∈ s, ⟨x, f i⟩.
inner_smul_left- Scalars factor out of the first argument of the inner product: ⟨r • x, y⟩ = r * ⟨x, y⟩ in real inner product spaces.
inner_smul_right- Scalars factor out of the second argument of the inner product: ⟨x, r • y⟩ = r * ⟨x, y⟩.
norm_sub_sq_real- Law of cosines: ‖x - y‖² = ‖x‖² - 2⟨x, y⟩ + ‖y‖².
Finset.sum_comm- Flipping the order of summation: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
isCompact_stdSimplex- The standard simplex in ℝ^ι is compact.
ose_var_identity- Variance identity: for weights summing to 1, ∑ c_i c_j ‖w_i - w_j‖² = 2 ∑ c_i ‖w_i‖² - 2 ‖∑ c_i w_i‖².
convex_stdSimplex- The standard simplex is convex.
parallelogram_law_with_norm- Parallelogram law: ‖x + y‖² + ‖x - y‖² = 2‖x‖² + 2‖y‖².
cauchySeq_tendsto_of_complete- In a complete metric space, every Cauchy sequence converges to a limit.
ose_kirszbraun_finite- Finite Kirszbraun extension: a Lipschitz map on a finite set extends to one additional point in Hilbert space.
ose_fip- A family of closed balls with the finite intersection property has non-empty intersection in a complete Hilbert space.
zorn_subset_nonempty- Zorn's lemma: every non-empty partially ordered set in which every chain has an upper bound contains a maximal element.
ose_one_point- Kirszbraun extension to a single point: an L-Lipschitz map into complete Hilbert space extends to one more point.
Metric.infDist_le_infDist_add_dist- The infimal distance function to any set is 1-Lipschitz: infDist x s ≤ infDist y s + dist x y.
Metric.le_infDist- A point's distance to a set is at least c if it is at least c from every point in the set.
ose_kirszbraun- Kirszbraun extension theorem: any L-Lipschitz map from a subset of a Hilbert space to a complete Hilbert space extends to the whole space with the same Lipschitz constant L.
dist_triangle- Triangle inequality for metric distance: dist x z ≤ dist x y + dist y z.
ose_euclidean_part- A 1-strongly Euclidean subset isometrically embeds into a complete real Hilbert space.
ose_transport- For any point y, there exists a point in Hilbert space whose distance to each embedded point of A is at most its distance to y in X.
ose_extend- Given an isometric embedding on A and a transport map from B, there exists a 7-Lipschitz extension to the union.
abs_le- Two real numbers have absolute difference at most c iff their difference lies between -c and c.
WithLp.prod_norm_sq_eq_of_L2- The squared norm in the ℓ₂ product space is the sum of squared norms of components.
pow_le_pow_iff_left₀- For non-negative numbers, a^n ≤ b^n iff a ≤ b (for positive n).
pow_le_pow_left₀- If 0 ≤ a ≤ b, then a^n ≤ b^n.
Metric.infDist_zero_of_mem- The infimal distance from a point to a set containing it is zero.
abs_of_nonneg- The absolute value of a non-negative real number is itself.
Metric.infDist_nonneg- The infimal distance to a set is non-negative.
norm_sub_rev- The norm of a difference is symmetric: ‖x - y‖ = ‖y - x‖.
dist_comm- Metric distance is symmetric: dist x y = dist y x.
dist_eq_norm- In a normed space, dist x y = ‖x - y‖.
smul_sub- Scalar multiplication distributes over subtraction: r • (x - y) = r • x - r • y.
norm_smul- The norm scales by absolute value: ‖r • x‖ = ‖r‖ * ‖x‖.
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.
Lean’s trace was cut to the first 400 of 482 tactics.
theorem ose_var_identity {F : Type*} [NormedAddCommGroup F] [InnerProductSpace ℝ F] {ι : Type*} [Fintype ι] (c : ι → ℝ) (hc : ∑ i, c i = 1) (w : ι → F) : ∑ i, ∑ j, c i * c j * ‖w i - w j‖ ^ 2 = 2 * ∑ i, c i * ‖w i‖ ^ 2 - 2 * ‖∑ i, c i • w i‖ ^ 2 := by have h1 : ‖∑ i, c i • w i‖ ^ 2 = ∑ i, ∑ j, c i * c j * inner ℝ (w i) (w j) := by rw [← real_inner_self_eq_norm_sq, sum_inner] refine Finset.sum_congr rfl fun i _ => ?_ rw [inner_sum] refine Finset.sum_congr rfl fun j _ => ?_ rw [inner_smul_left, inner_smul_right] simp only [conj_trivial] ring have h2 : ∀ i j, ‖w i - w j‖ ^ 2 = ‖w i‖ ^ 2 - 2 * inner ℝ (w i) (w j) + ‖w j‖ ^ 2 := fun i j => norm_sub_sq_real _ _ have h3 : ∑ i, ∑ j, c i * c j * ‖w i‖ ^ 2 = ∑ i, c i * ‖w i‖ ^ 2 := by refine Finset.sum_congr rfl fun i _ => ?_ rw [← Finset.sum_mul, ← Finset.mul_sum, hc, mul_one] have h4 : ∑ i, ∑ j, c i * c j * ‖w j‖ ^ 2 = ∑ j, c j * ‖w j‖ ^ 2 := by rw [Finset.sum_comm] refine Finset.sum_congr rfl fun j _ => ?_ rw [← Finset.sum_mul, ← Finset.sum_mul, hc, one_mul] have h5 : ∀ i j, c i * c j * ‖w i - w j‖ ^ 2 = c i * c j * ‖w i‖ ^ 2 - 2 * (c i * c j * inner ℝ (w i) (w j)) + c i * c j * ‖w j‖ ^ 2 := fun i j => by rw [h2]; ring rw [h1] simp_rw [h5, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.mul_sum] rw [h3, h4] ringtheorem ose_kirszbraun_finite {E F : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F] {ι : Type*} [Fintype ι] [Nonempty ι] (L : ℝ) (hL : 0 ≤ L) (x : ι → E) (y : ι → F) (z : E) (h : ∀ i j, ‖y i - y j‖ ≤ L * ‖x i - x j‖) : ∃ p : F, ∀ i, ‖p - y i‖ ≤ L * ‖z - x i‖ := by classical let v : ι → E := fun i => x i - z let a : ι → ℝ := fun i => ‖y i‖ ^ 2 - L ^ 2 * ‖v i‖ ^ 2 let g : (ι → ℝ) → ℝ := fun c => ∑ i, c i * a i - ‖∑ i, c i • y i‖ ^ 2 have hg : Continuous g := by apply Continuous.sub · exact continuous_finsetSum _ fun i _ => (continuous_apply i).mul continuous_const · exact (continuous_norm.comp (continuous_finsetSum _ fun i _ => (continuous_apply i).smul continuous_const)).pow 2 obtain ⟨c, hc, hmax⟩ := (isCompact_stdSimplex ℝ ι).exists_isMaxOn ⟨_, single_mem_stdSimplex ℝ (Classical.arbitrary ι)⟩ hg.continuousOn have hcsum : ∑ i, c i = 1 := hc.2 have hc0 : ∀ i, 0 ≤ c i := hc.1 set p : F := ∑ i, c i • y i with hp set A : ℝ := ∑ i, c i * a i with hA -- the value at the maximum is nonpositive have hval : A - ‖p‖ ^ 2 ≤ 0 := by have e1 := ose_var_identity c hcsum y have e2 := ose_var_identity c hcsum v have hle : ∑ i, ∑ j, c i * c j * ‖y i - y j‖ ^ 2 ≤ ∑ i, ∑ j, c i * c j * (L ^ 2 * ‖v i - v j‖ ^ 2) := by refine Finset.sum_le_sum fun i _ => Finset.sum_le_sum fun j _ => ?_ refine mul_le_mul_of_nonneg_left ?_ (mul_nonneg (hc0 i) (hc0 j)) have hvv : v i - v j = x i - x j := by simp [v] rw [hvv] calc ‖y i - y j‖ ^ 2 ≤ (L * ‖x i - x j‖) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) (h i j) 2 _ = L ^ 2 * ‖x i - x j‖ ^ 2 := by ring have e3 : ∑ i, ∑ j, c i * c j * (L ^ 2 * ‖v i - v j‖ ^ 2) = L ^ 2 * ∑ i, ∑ j, c i * c j * ‖v i - v j‖ ^ 2 := by simp_rw [Finset.mul_sum] refine Finset.sum_congr rfl fun i _ => Finset.sum_congr rfl fun j _ => ?_ ring have e4 : A = ∑ i, c i * ‖y i‖ ^ 2 - L ^ 2 * ∑ i, c i * ‖v i‖ ^ 2 := by rw [hA, Finset.mul_sum, ← Finset.sum_sub_distrib] refine Finset.sum_congr rfl fun i _ => ?_ simp only [a] ring have e5 : 0 ≤ L ^ 2 * ‖∑ i, c i • v i‖ ^ 2 := by positivity rw [e3, e2] at hle rw [e1] at hle rw [e4] nlinarith refine ⟨p, fun j => ?_⟩ -- first-order condition at `j` have hfirst : a j - A - 2 * inner ℝ p (y j - p) ≤ 0 := by by_contra hcon rw [not_le] at hcon set S := a j - A - 2 * inner ℝ p (y j - p) with hS set M := ‖y j - p‖ ^ 2 with hM have hM0 : 0 ≤ M := by positivity set t : ℝ := S / (S + M + 1) with ht have hden : 0 < S + M + 1 := by linarith have ht0 : 0 < t := div_pos hcon hden have ht1 : t ≤ 1 := by rw [ht, div_le_one hden]; linarith have htM : t * M < S := by rw [ht, div_mul_eq_mul_div, div_lt_iff₀ hden] nlinarith let c' : ι → ℝ := (1 - t) • c + t • Pi.single j (1 : ℝ) have hc' : c' ∈ stdSimplex ℝ ι := convex_stdSimplex ℝ ι hc (single_mem_stdSimplex ℝ j) (by linarith) ht0.le (by ring) have hle := hmax hc' have e1 : ∑ i, c' i * a i = (1 - t) * A + t * a j := by simp only [c', Pi.add_apply, Pi.smul_apply, smul_eq_mul, add_mul, Finset.sum_add_distrib] rw [hA, Finset.mul_sum] congr 1 · exact Finset.sum_congr rfl fun i _ => by ring · simp [Pi.single_apply] have e2 : ∑ i, c' i • y i = p + t • (y j - p) := by simp only [c', Pi.add_apply, Pi.smul_apply, smul_eq_mul, add_smul, Finset.sum_add_distrib, mul_smul] rw [← Finset.smul_sum, ← Finset.smul_sum, ← hp] simp only [Pi.single_apply, ite_smul, one_smul, zero_smul, Finset.sum_ite_eq', Finset.mem_univ, if_true] simp only [smul_sub, sub_smul, one_smul] abel have e3 : ‖p + t • (y j - p)‖ ^ 2 = ‖p‖ ^ 2 + 2 * t * inner ℝ p (y j - p) + t ^ 2 * M := by rw [norm_add_sq_real, inner_smul_right, norm_smul, mul_pow, Real.norm_eq_abs, sq_abs] ring have hle' : (1 - t) * A + t * a j - ‖p + t • (y j - p)‖ ^ 2 ≤ A - ‖p‖ ^ 2 := by have := hle simp only [Set.mem_ofPred_eq, g] at this rw [e1, e2] at this exact this rw [e3] at hle' have : t * S ≤ t * (t * M) := by have : t * S = t * a j - t * A - 2 * t * inner ℝ p (y j - p) := by rw [hS]; ring nlinarith have := le_of_mul_le_mul_left this ht0 linarith -- conclude have hsq : ‖p - y j‖ ^ 2 ≤ (L * ‖z - x j‖) ^ 2 := by have e1 : ‖p - y j‖ ^ 2 = ‖y j‖ ^ 2 - 2 * inner ℝ (y j) p + ‖p‖ ^ 2 := by rw [norm_sub_rev, norm_sub_sq_real] have e2 : inner ℝ p (y j - p) = inner ℝ (y j) p - ‖p‖ ^ 2 := by rw [inner_sub_right, real_inner_comm, real_inner_self_eq_norm_sq] have e3 : ‖v j‖ = ‖z - x j‖ := by simp [v, norm_sub_rev] have e4 : a j = ‖y j‖ ^ 2 - L ^ 2 * ‖z - x j‖ ^ 2 := by simp only [a, e3] rw [mul_pow] rw [e2, e4] at hfirst nlinarith exact (pow_le_pow_iff_left₀ (norm_nonneg _) (mul_nonneg hL (norm_nonneg _)) (by norm_num)).1 hsqtheorem ose_fip {F : Type*} [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] {I : Type*} (y : I → F) (ρ : I → ℝ) (h : ∀ s : Finset I, ∃ p : F, ∀ i ∈ s, ‖p - y i‖ ≤ ρ i) : ∃ p : F, ∀ i, ‖p - y i‖ ≤ ρ i := by classical by_cases hI : Nonempty I swap · exact ⟨0, fun i => (hI ⟨i⟩).elim⟩ obtain ⟨i₀⟩ := hI let C : Finset I → Set F := fun s => ⋂ i ∈ s, Metric.closedBall (y i) (ρ i) have hmemC : ∀ s p, p ∈ C s ↔ ∀ i ∈ s, ‖p - y i‖ ≤ ρ i := by intro s p simp [C, Metric.mem_closedBall, dist_eq_norm] have hCne : ∀ s, (C s).Nonempty := fun s => by obtain ⟨p, hp⟩ := h s exact ⟨p, (hmemC s p).2 hp⟩ have hCclosed : ∀ s, IsClosed (C s) := fun s => isClosed_biInter fun i _ => Metric.isClosed_closedBall have hCconv : ∀ s, Convex ℝ (C s) := fun s => convex_iInter₂ fun i _ => convex_closedBall _ _ have hmin : ∀ s, ∃ m ∈ C s, ∀ w ∈ C s, ‖m‖ ≤ ‖w‖ := by intro s obtain ⟨m, hm, hmeq⟩ := exists_norm_eq_iInf_of_complete_convex (hCne s) (hCclosed s).isComplete (hCconv s) (0 : F) refine ⟨m, hm, fun w hw => ?_⟩ have hb : BddBelow (Set.range fun w : C s => ‖(0 : F) - w‖) := ⟨0, by rintro _ ⟨w, rfl⟩; exact norm_nonneg _⟩ have := ciInf_le hb (⟨w, hw⟩ : C s) simp only [zero_sub, norm_neg] at hmeq this linarith choose m hmC hmmin using hmin have hsub : ∀ {s t : Finset I}, s ⊆ t → C t ⊆ C s := by intro s t hst p hp exact (hmemC s p).2 fun i hi => (hmemC t p).1 hp i (hst hi) have hmono : ∀ {s t : Finset I}, s ⊆ t → ‖m s‖ ≤ ‖m t‖ := fun hst => hmmin _ _ (hsub hst (hmC _)) have hbd : ∀ s, ‖m s‖ ≤ ‖y i₀‖ + ρ i₀ := by intro s have h1 : ‖m s‖ ≤ ‖m (insert i₀ s)‖ := hmono (Finset.subset_insert _ _) have h2 := (hmemC _ _).1 (hmC (insert i₀ s)) i₀ (Finset.mem_insert_self _ _) have h3 : ‖m (insert i₀ s)‖ ≤ ‖m (insert i₀ s) - y i₀‖ + ‖y i₀‖ := by simpa using norm_add_le (m (insert i₀ s) - y i₀) (y i₀) linarith have hbdd : BddAbove (Set.range fun s => ‖m s‖ ^ 2) := by refine ⟨(‖y i₀‖ + ρ i₀) ^ 2, ?_⟩ rintro _ ⟨s, rfl⟩ exact pow_le_pow_left₀ (norm_nonneg _) (hbd s) 2 set S : ℝ := ⨆ s, ‖m s‖ ^ 2 with hS have hcauchy : CauchySeq m := by rw [Metric.cauchySeq_iff'] intro ε hε have hlt : S - ε ^ 2 / 2 < S := by nlinarith [sq_pos_of_pos hε] obtain ⟨N, hN⟩ := exists_lt_of_lt_ciSup hlt refine ⟨N, fun n hn => ?_⟩ have hNn : N ⊆ n := hn have hmid : (1 / 2 : ℝ) • m n + (1 / 2 : ℝ) • m N ∈ C N := hCconv N (hsub hNn (hmC n)) (hmC N) (by norm_num) (by norm_num) (by norm_num) have h1 := hmmin N _ hmid have h2 : (1 / 2 : ℝ) • m n + (1 / 2 : ℝ) • m N = (1 / 2 : ℝ) • (m n + m N) := by rw [smul_add] rw [h2, norm_smul] at h1 simp only [Real.norm_eq_abs, abs_of_pos (by norm_num : (0 : ℝ) < 1 / 2)] at h1 have h3 := parallelogram_law_with_norm ℝ (m n) (m N) have hle : ‖m n‖ ^ 2 ≤ S := le_ciSup hbdd n have h4 : 2 * ‖m N‖ ≤ ‖m n + m N‖ := by linarith have h5 : (2 * ‖m N‖) * (2 * ‖m N‖) ≤ ‖m n + m N‖ * ‖m n + m N‖ := mul_self_le_mul_self (by positivity) h4 have h6 : ‖m n - m N‖ ^ 2 < ε ^ 2 := by nlinarith rw [dist_eq_norm] exact lt_of_pow_lt_pow_left₀ 2 hε.le h6 obtain ⟨p, hp⟩ := cauchySeq_tendsto_of_complete hcauchy refine ⟨p, fun i => ?_⟩ have hev : ∀ᶠ s in Filter.atTop, m s ∈ Metric.closedBall (y i) (ρ i) := by filter_upwards [Filter.eventually_ge_atTop ({i} : Finset I)] with s hs have := (hmemC s (m s)).1 (hmC s) i (hs (Finset.mem_singleton_self i)) simpa [Metric.mem_closedBall, dist_eq_norm] using this have := Metric.isClosed_closedBall.mem_of_tendsto hp hev simpa [Metric.mem_closedBall, dist_eq_norm] using thistheorem ose_one_point {E F : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] (L : ℝ) (hL : 0 ≤ L) (G : Set (E × F)) (hG : ∀ q ∈ G, ∀ q' ∈ G, ‖q.2 - q'.2‖ ≤ L * ‖q.1 - q'.1‖) (z : E) : ∃ p : F, ∀ q ∈ G, ‖p - q.2‖ ≤ L * ‖z - q.1‖ := by obtain ⟨p, hp⟩ := ose_fip (I := G) (fun q => q.1.2) (fun q => L * ‖z - q.1.1‖) (by intro s by_cases hs : Nonempty s · obtain ⟨p, hp⟩ := ose_kirszbraun_finite (ι := s) L hL (fun i => i.1.1.1) (fun i => i.1.1.2) z (fun i j => hG _ i.1.2 _ j.1.2) exact ⟨p, fun i hi => hp ⟨i, hi⟩⟩ · exact ⟨0, fun i hi => (hs ⟨⟨i, hi⟩⟩).elim⟩) exact ⟨p, fun q hq => hp ⟨q, hq⟩⟩theorem ose_kirszbraun {E F : Type*} [NormedAddCommGroup E] [InnerProductSpace ℝ E] [NormedAddCommGroup F] [InnerProductSpace ℝ F] [CompleteSpace F] (L : ℝ) (hL : 0 ≤ L) (G : Set (E × F)) (hG : ∀ q ∈ G, ∀ q' ∈ G, ‖q.2 - q'.2‖ ≤ L * ‖q.1 - q'.1‖) : ∃ T : E → F, (∀ q ∈ G, T q.1 = q.2) ∧ ∀ u v, ‖T u - T v‖ ≤ L * ‖u - v‖ := by classical let P : Set (Set (E × F)) := {K | ∀ q ∈ K, ∀ q' ∈ K, ‖q.2 - q'.2‖ ≤ L * ‖q.1 - q'.1‖} obtain ⟨K, hGK, hK⟩ := zorn_subset_nonempty P (by intro c hcP hchain hne refine ⟨⋃₀ c, ?_, fun s hs => Set.subset_sUnion_of_mem hs⟩ rintro q ⟨s, hs, hq⟩ q' ⟨s', hs', hq'⟩ rcases hchain.total hs hs' with hss | hss · exact hcP hs' _ (hss hq) _ hq' · exact hcP hs _ hq _ (hss hq')) G hG have hKP : K ∈ P := hK.prop have hall : ∀ u : E, ∃ w : F, (u, w) ∈ K := by intro u obtain ⟨p, hp⟩ := ose_one_point L hL K hKP u refine ⟨p, ?_⟩ have hins : insert (u, p) K ∈ P := by rintro q (rfl | hq) q' (rfl | hq') · simp · simpa using hp q' hq' · have := hp q hq rw [norm_sub_rev p, norm_sub_rev u] at this simpa using this · exact hKP _ hq _ hq' exact hK.le_of_ge hins (Set.subset_insert _ _) (Set.mem_insert _ _) choose T hT using hall refine ⟨T, fun q hq => ?_, fun u v => hKP _ (hT u) _ (hT v)⟩ have := hKP _ (hT q.1) _ (hGK hq) simp only [sub_self, norm_zero, mul_zero] at this exact sub_eq_zero.1 (norm_le_zero_iff.1 this)theorem ose_extend {X : Type*} [MetricSpace X] {H₁ H₂ : Type*} [NormedAddCommGroup H₁] [InnerProductSpace ℝ H₁] [CompleteSpace H₁] [NormedAddCommGroup H₂] [InnerProductSpace ℝ H₂] (A B : Set X) (hAB : ∀ x, x ∈ A ∨ x ∈ B) (φ : X → H₁) (hφ : ∀ a ∈ A, ∀ a' ∈ A, dist (φ a) (φ a') = dist a a') (ψ : X → H₂) (hψ : ∀ b ∈ B, ∀ b' ∈ B, dist (ψ b) (ψ b') = dist b b') (g : X → H₁) (hg : ∀ y, ∀ a ∈ A, dist (g y) (φ a) ≤ dist y a) (hA : A.Nonempty) : ∃ F : X → H₁, (∀ a ∈ A, F a = φ a) ∧ ∀ x y, dist (F x) (F y) ≤ 7 * dist x y := by classical let r : X → ℝ := fun y => Metric.infDist y A have hr0 : ∀ y, 0 ≤ r y := fun y => Metric.infDist_nonneg have hrA : ∀ y, ∀ a ∈ A, r y ≤ dist y a := fun y a ha => Metric.infDist_le_dist_of_mem ha have hrL : ∀ y y', r y ≤ r y' + dist y y' := fun y y' => Metric.infDist_le_infDist_add_dist have hgg : ∀ y y', dist (g y) (g y') ≤ dist y y' + 2 * r y := by intro y y' have : (dist (g y) (g y') - dist y y') / 2 ≤ r y := by refine (Metric.le_infDist hA).2 fun a ha => ?_ have h1 := dist_triangle_right (g y) (g y') (φ a) have h2 := hg y a ha have h3 := hg y' a ha have h4 := dist_triangle y' y a rw [dist_comm y' y] at h4 linarith linarith obtain ⟨N, -, hN⟩ := zorn_subset_nonempty {N : Set X | N ⊆ B ∧ ∀ y ∈ N, ∀ y' ∈ N, y ≠ y' → r y ≤ 2 * dist y y'} (by intro c hcP hchain hne refine ⟨⋃₀ c, ⟨?_, ?_⟩, fun s hs => Set.subset_sUnion_of_mem hs⟩ · rintro y ⟨s, hs, hy⟩ exact (hcP hs).1 hy · rintro y ⟨s, hs, hy⟩ y' ⟨s', hs', hy'⟩ hne rcases hchain.total hs hs' with hss | hss · exact (hcP hs').2 _ (hss hy) _ hy' hne · exact (hcP hs).2 _ hy _ (hss hy') hne) ∅ ⟨by simp, by simp⟩ have hNB : N ⊆ B := hN.prop.1 have hNsep := hN.prop.2 have hNcov : ∀ y ∈ B, ∃ y0 ∈ N, dist y y0 ≤ r y := by intro y hy by_cases hyN : y ∈ N · exact ⟨y, hyN, by simpa using hr0 y⟩ · have hnot : ¬ (insert y N ⊆ B ∧ ∀ u ∈ insert y N, ∀ v ∈ insert y N, u ≠ v → r u ≤ 2 * dist u v) := by intro hins exact hyN (hN.le_of_ge hins (Set.subset_insert _ _) (Set.mem_insert _ _)) have hsubB : insert y N ⊆ B := Set.insert_subset hy hNB have : ∃ u ∈ insert y N, ∃ v ∈ insert y N, u ≠ v ∧ 2 * dist u v < r u := by by_contra hcon refine hnot ⟨hsubB, fun u hu v hv huv => ?_⟩ by_contra hlt exact hcon ⟨u, hu, v, hv, huv, not_le.1 hlt⟩ obtain ⟨u, hu, v, hv, huv, hlt⟩ := this rcases hu with rfl | hu <;> rcases hv with rfl | hv · exact (huv rfl).elim · exact ⟨v, hv, by linarith [dist_nonneg (x := u) (y := v)]⟩ · refine ⟨u, hu, ?_⟩ have := hrL u v rw [dist_comm v u] linarith · exact absurd hlt (not_lt.2 (hNsep u hu v hv huv)) let G : Set (H₂ × H₁) := (fun y => (ψ y, g y)) '' N have hG : ∀ q ∈ G, ∀ q' ∈ G, ‖q.2 - q'.2‖ ≤ 5 * ‖q.1 - q'.1‖ := by rintro _ ⟨y, hy, rfl⟩ _ ⟨y', hy', rfl⟩ show ‖g y - g y'‖ ≤ 5 * ‖ψ y - ψ y'‖ rw [← dist_eq_norm, ← dist_eq_norm, hψ y (hNB hy) y' (hNB hy')] by_cases hyy : y = y' · subst hyy simp · have := hNsep y hy y' hy' hyy have := hgg y y' linarith obtain ⟨T, hT, hTL⟩ := ose_kirszbraun 5 (by norm_num) G hG have hTN : ∀ y ∈ N, T (ψ y) = g y := fun y hy => hT (ψ y, g y) ⟨y, hy, rfl⟩ have hTd : ∀ y ∈ B, ∀ y' ∈ B, dist (T (ψ y)) (T (ψ y')) ≤ 5 * dist y y' := by intro y hy y' hy' rw [dist_eq_norm, ← hψ y hy y' hy', dist_eq_norm] exact hTL _ _ -- the cross estimate have hcross : ∀ y ∈ B, ∀ a ∈ A, dist (T (ψ y)) (φ a) ≤ 7 * dist y a := by intro y hy a ha obtain ⟨y0, hy0, hd⟩ := hNcov y hy have h1 := hTd y hy y0 (hNB hy0) rw [hTN y0 hy0] at h1 have h2 := hg y0 a ha have h3 := dist_triangle y0 y a rw [dist_comm y0 y] at h3 have h4 := hrA y a ha have h5 := dist_triangle (T (ψ y)) (g y0) (φ a) linarith refine ⟨fun x => if x ∈ A then φ x else T (ψ x), fun a ha => by simp [ha], fun x y => ?_⟩ by_cases hx : x ∈ A <;> by_cases hy : y ∈ A · simp only [hx, hy, if_true] rw [hφ x hx y hy] linarith [dist_nonneg (x := x) (y := y)] · simp only [hx, hy, if_true, if_false] have hyB : y ∈ B := (hAB y).resolve_left hy have := hcross y hyB x hx rw [dist_comm, dist_comm x y] exact this · simp only [hx, hy, if_true, if_false] exact hcross x ((hAB x).resolve_left hx) y hy · simp only [hx, hy, if_false] have := hTd x ((hAB x).resolve_left hx) y ((hAB y).resolve_left hy) linarith [dist_nonneg (x := x) (y := y)]theorem ose_euclidean_part {X : Type} [MetricSpace X] (A : Set X) (hE : IsOneStronglyEuclidean A) : ∃ (H : Type) (_ : NormedAddCommGroup H) (_ : InnerProductSpace ℝ H) (_ : CompleteSpace H) (φ : X → H), ∀ a ∈ A, ∀ a' ∈ A, dist (φ a) (φ a') = dist a a' := by classical rcases A.eq_empty_or_nonempty with rfl | ⟨a₀, ha₀⟩ · exact ⟨ℝ, inferInstance, inferInstance, inferInstance, fun _ => 0, by simp⟩ · obtain ⟨H, i1, i2, i3, f, hf⟩ := hE a₀ refine ⟨H, i1, i2, i3, fun x => if h : x ∈ A then f ⟨x, Or.inl h⟩ else 0, ?_⟩ intro a ha a' ha' simp only [ha, ha', dif_pos] exact hf.dist_eq _ _theorem ose_transport {X : Type} [MetricSpace X] {H : Type} [NormedAddCommGroup H] [InnerProductSpace ℝ H] [CompleteSpace H] (A : Set X) (hE : IsOneStronglyEuclidean A) (φ : X → H) (hφ : ∀ a ∈ A, ∀ a' ∈ A, dist (φ a) (φ a') = dist a a') (y : X) : ∃ p : H, ∀ a ∈ A, dist p (φ a) ≤ dist y a := by obtain ⟨K, i1, i2, i3, f, hf⟩ := hE y let G : Set (K × H) := (fun a : A => (f ⟨a.1, Or.inl a.2⟩, φ a.1)) '' Set.univ obtain ⟨p, hp⟩ := ose_one_point 1 zero_le_one G (by rintro _ ⟨a, -, rfl⟩ _ ⟨a', -, rfl⟩ show ‖φ a.1 - φ a'.1‖ ≤ 1 * ‖f _ - f _‖ rw [← dist_eq_norm, ← dist_eq_norm, hf.dist_eq, hφ _ a.2 _ a'.2, one_mul] rfl) (f ⟨y, Or.inr (Set.mem_singleton y)⟩) refine ⟨p, fun a ha => ?_⟩ have := hp _ ⟨⟨a, ha⟩, trivial, rfl⟩ simp only [one_mul] at this rw [dist_eq_norm] refine this.trans (le_of_eq ?_) rw [← dist_eq_norm, hf.dist_eq] rfl/-- A union of two 1-strongly Euclidean metric spaces embeds into a Hilbert space with constant distortion. -/theorem one_strongly_euclidean_union_two_sets_distortion : ∃ C : ℝ, 0 < C ∧ ∀ (X : Type) [MetricSpace X] (U : Fin 2 → Set X) (_hU : (⋃ i, U i) = Set.univ) (_hE : ∀ i, IsOneStronglyEuclidean (U i)), EmbedsIntoHilbertWithDistortion X C := by classical refine ⟨90, by norm_num, ?_⟩ intro X _ U hU hE have hcov : ∀ x, x ∈ U 0 ∨ x ∈ U 1 := by intro x have : x ∈ ⋃ i, U i := hU ▸ Set.mem_univ x obtain ⟨i, hi⟩ := Set.mem_iUnion.1 this fin_cases i · exact Or.inl hi · exact Or.inr hi obtain ⟨H₁, i1, i2, i3, φ, hφ⟩ := ose_euclidean_part (U 0) (hE 0) obtain ⟨H₂, j1, j2, j3, ψ, hψ⟩ := ose_euclidean_part (U 1) (hE 1) have hext1 : ∃ F : X → H₁, (∀ a ∈ U 0, F a = φ a) ∧ ∀ x y, dist (F x) (F y) ≤ 7 * dist x y := by rcases (U 0).eq_empty_or_nonempty with he | hne · exact ⟨fun _ => 0, by simp [he], fun x y => by simp [dist_nonneg]⟩ · choose g hg using ose_transport (U 0) (hE 0) φ hφ exact ose_extend (U 0) (U 1) hcov φ hφ ψ hψ g hg hne have hext2 : ∃ F : X → H₂, (∀ a ∈ U 1, F a = ψ a) ∧ ∀ x y, dist (F x) (F y) ≤ 7 * dist x y := by rcases (U 1).eq_empty_or_nonempty with he | hne · exact ⟨fun _ => 0, by simp [he], fun x y => by simp [dist_nonneg]⟩ · choose g hg using ose_transport (U 1) (hE 1) ψ hψ exact ose_extend (U 1) (U 0) (fun x => (hcov x).symm) ψ hψ φ hφ g hg hne obtain ⟨F₁, hF₁, hL₁⟩ := hext1 obtain ⟨F₂, hF₂, hL₂⟩ := hext2 let D : X → ℝ := fun x => Metric.infDist x (U 1) have hD : ∀ x y, |D x - D y| ≤ dist x y := by intro x y have h1 : D x ≤ D y + dist x y := Metric.infDist_le_infDist_add_dist have h2 : D y ≤ D x + dist y x := Metric.infDist_le_infDist_add_dist rw [dist_comm y x] at h2 exact abs_le.2 ⟨by linarith, by linarith⟩ let E : X → WithLp 2 (WithLp 2 (H₁ × H₂) × ℝ) := fun x => WithLp.toLp 2 (WithLp.toLp 2 (F₁ x, F₂ x), D x) have hEsq : ∀ x y, ‖E x - E y‖ ^ 2 = ‖F₁ x - F₁ y‖ ^ 2 + ‖F₂ x - F₂ y‖ ^ 2 + |D x - D y| ^ 2 := by intro x y rw [WithLp.prod_norm_sq_eq_of_L2] simp only [E, WithLp.prod_norm_sq_eq_of_L2] simp have hUB : ∀ x y, ‖E x - E y‖ ≤ 10 * dist x y := by intro x y have h1 := hL₁ x y have h2 := hL₂ x y have h3 := hD x y rw [dist_eq_norm] at h1 h2 have hd := dist_nonneg (x := x) (y := y) have s1 : ‖F₁ x - F₁ y‖ ^ 2 ≤ (7 * dist x y) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) h1 2 have s2 : ‖F₂ x - F₂ y‖ ^ 2 ≤ (7 * dist x y) ^ 2 := pow_le_pow_left₀ (norm_nonneg _) h2 2 have s3 : |D x - D y| ^ 2 ≤ dist x y ^ 2 := pow_le_pow_left₀ (abs_nonneg _) h3 2 have : ‖E x - E y‖ ^ 2 ≤ (10 * dist x y) ^ 2 := by rw [hEsq] nlinarith exact (pow_le_pow_iff_left₀ (norm_nonneg _) (by positivity) (by norm_num)).1 this have hc1 : ∀ x y, ‖F₁ x - F₁ y‖ ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (norm_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₂ x - F₂ y‖, sq_nonneg |D x - D y|] have hc2 : ∀ x y, ‖F₂ x - F₂ y‖ ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (norm_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₁ x - F₁ y‖, sq_nonneg |D x - D y|] have hc3 : ∀ x y, |D x - D y| ≤ ‖E x - E y‖ := by intro x y refine (pow_le_pow_iff_left₀ (abs_nonneg _) (norm_nonneg _) (two_ne_zero)).1 ?_ rw [hEsq] nlinarith [sq_nonneg ‖F₁ x - F₁ y‖, sq_nonneg ‖F₂ x - F₂ y‖] -- the cross pairs have hcross : ∀ x ∈ U 0, ∀ y ∈ U 1, dist x y ≤ 9 * ‖E x - E y‖ := by intro x hx y hy have hDy : D y = 0 := Metric.infDist_zero_of_mem hy have hmain : (dist x y - ‖F₂ x - F₂ y‖) / 8 ≤ D x := by refine (Metric.le_infDist ⟨y, hy⟩).2 fun b hb => ?_ have h1 := dist_triangle x b y have h2 : dist b y = dist (F₂ b) (F₂ y) := by rw [hF₂ b hb, hF₂ y hy, hψ b hb y hy] have h3 := dist_triangle (F₂ b) (F₂ x) (F₂ y) have h4 := hL₂ b x rw [dist_comm b x] at h4 rw [dist_eq_norm (F₂ x) (F₂ y)] at h3 linarith have h1 := hc2 x y have h2 := hc3 x y rw [hDy, sub_zero, abs_of_nonneg Metric.infDist_nonneg] at h2 linarith have hLB : ∀ x y, dist x y ≤ 9 * ‖E x - E y‖ := by intro x y have hnn := norm_nonneg (E x - E y) rcases hcov x with hx | hx <;> rcases hcov y with hy | hy · have := hc1 x y rw [hF₁ x hx, hF₁ y hy, ← dist_eq_norm, hφ x hx y hy] at this linarith · exact hcross x hx y hy · have := hcross y hy x hx rw [dist_comm, norm_sub_rev] exact this · have := hc2 x y rw [hF₂ x hx, hF₂ y hy, ← dist_eq_norm, hψ x hx y hy] at this linarith refine ⟨WithLp 2 (WithLp 2 (H₁ × H₂) × ℝ), inferInstance, inferInstance, inferInstance, fun x => (9 : ℝ) • E x, fun x y => ?_⟩ have hs : dist ((9 : ℝ) • E x) ((9 : ℝ) • E y) = 9 * ‖E x - E y‖ := by rw [dist_eq_norm, ← smul_sub, norm_smul] norm_num rw [hs] exact ⟨hLB x y, by linarith [hUB x y]⟩