AFTD Auto-Formalizing Theoretical Domains

one_strongly_euclidean_union_two_sets_distortion

theoremverifiedformalization

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

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.

  1. 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`).

    lines 5–12

    uses real_inner_self_eq_norm_sq, sum_inner, inner_sum, inner_smul_left, inner_smul_right

      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
  2. 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.

    lines 13–24

    uses norm_sub_sq_real, Finset.sum_comm

      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
  3. 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.

    lines 25–28

      rw [h1]
      simp_rw [h5, Finset.sum_add_distrib, Finset.sum_sub_distrib, ← Finset.mul_sum]
      rw [h3, h4]
      ring
  4. 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.

    lines 37–51

    uses isCompact_stdSimplex

      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
  5. 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.

    lines 52–79

    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
  6. 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.

    lines 80–127

    uses convex_stdSimplex

      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
  7. 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.

    lines 128–140

    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
    
  8. 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.

    lines 145–171

    uses dist_eq_norm

      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
  9. 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.

    lines 172–212

    uses parallelogram_law_with_norm, pow_le_pow_left₀, dist_eq_norm

      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
  10. 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.

    lines 213–220

    uses cauchySeq_tendsto_of_complete, dist_eq_norm

      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 this
    
  11. 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.

    lines 227–235

    uses ose_kirszbraun_finite, ose_fip

      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⟩⟩
    
  12. 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.

    lines 242–270

    uses zorn_subset_nonempty, ose_one_point, norm_sub_rev

      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)
    
  13. 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`.

    lines 280–295

    uses Metric.infDist_nonneg, Metric.infDist_le_infDist_add_dist, Metric.le_infDist, dist_triangle, dist_comm

      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
  14. 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.

    lines 296–331

    uses zorn_subset_nonempty, dist_comm

      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
  15. 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₂.

    lines 332–347

    uses dist_eq_norm, ose_kirszbraun

      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 _ _
  16. 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).

    lines 348–359

    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
  17. 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.

    lines 360–375

    uses dist_comm

      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)]
    
  18. 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.

    lines 380–388

      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 _ _
    
  19. 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.

    lines 393–408

    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
    
  20. 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.

    lines 416–425

      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
  21. 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.

    lines 426–440

    uses ose_euclidean_part, ose_transport, ose_extend

      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)
  22. 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`).

    lines 441–446

    uses Metric.infDist_le_infDist_add_dist, dist_comm, abs_le

      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⟩
  23. 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`).

    lines 447–454

    uses WithLp.prod_norm_sq_eq_of_L2

      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
  24. 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.

    lines 455–468

    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
  25. 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₀`.

    lines 469–484

    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
  26. 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‖.

    lines 485–501

    uses Metric.infDist_zero_of_mem, Metric.le_infDist, dist_triangle, dist_comm, dist_eq_norm, abs_of_nonneg, Metric.infDist_nonneg

      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
  27. 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.

    lines 502–515

    uses dist_comm, norm_sub_rev, dist_eq_norm

      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
  28. 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.

    lines 516–522

    uses dist_eq_norm, smul_sub, norm_smul

      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]⟩
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

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]⟩
See it in the graphDiscuss this resultChallenge it