import DeqMdErratum.Variational

/-!
# Kurdyka–Łojasiewicz (KŁ) Property and Theorem A.8

This file defines concave desingularizing functions, the Kurdyka–Łojasiewicz (KŁ) property
(`HasKLAt`, `HasKL`), proves the Uniformized KŁ Lemma on compact sets (`uniformized_kl`) by summing
desingularizing functions over a finite open subcover, and establishes Theorem A.8 of [3]
(Bolte–Sabach–Teboulle [1]): any bounded sequence satisfying sufficient decrease (H1),
relative error (H2), and subsequence continuity (H3) for a proper lower semicontinuous KŁ function
has finite length and converges to a critical point.
-/

open Filter Topology
open scoped BigOperators

namespace DeqMdErratum

section Desingularizing

/-- A desingularizing function `φ : ℝ → ℝ` on `[0, η)` as in the Kurdyka–Łojasiewicz inequality:
`φ(0) = 0`, `φ` is continuous on `[0, η)`, concave and `C¹` on `(0, η)`, and `φ' > 0` on `(0, η)`. -/
def DesingularizingFunction (η : ℝ) (φ : ℝ → ℝ) : Prop :=
  0 < η ∧
    φ 0 = 0 ∧
    ContinuousOn φ (Set.Ico 0 η) ∧
    ConcaveOn ℝ (Set.Ioo 0 η) φ ∧
    DifferentiableOn ℝ φ (Set.Ioo 0 η) ∧
    ContinuousOn (deriv φ) (Set.Ioo 0 η) ∧
    ∀ s ∈ Set.Ioo 0 η, 0 < deriv φ s

lemma DesingularizingFunction.antitoneOn_deriv {η : ℝ} {φ : ℝ → ℝ}
    (hφ : DesingularizingFunction η φ) :
    AntitoneOn (deriv φ) (Set.Ioo 0 η) := by
  refine hφ.2.2.2.1.antitoneOn_deriv fun s hs => ?_
  exact (hφ.2.2.2.2.1 s hs).differentiableAt (isOpen_Ioo.mem_nhds hs)

lemma DesingularizingFunction.mul_sub_le {η : ℝ} {φ : ℝ → ℝ}
    (hφ : DesingularizingFunction η φ) {s₂ s₁ : ℝ}
    (hs₂ : s₂ ∈ Set.Ico 0 η) (hs₁ : s₁ ∈ Set.Ioo 0 η) (h21 : s₂ ≤ s₁) :
    deriv φ s₁ * (s₁ - s₂) ≤ φ s₁ - φ s₂ := by
  rcases eq_or_lt_of_le h21 with rfl | hlt
  · simp
  have hIcc : Set.Icc s₂ s₁ ⊆ Set.Ico 0 η := fun t ht => ⟨hs₂.1.trans ht.1, ht.2.trans_lt hs₁.2⟩
  have hIoo : Set.Ioo s₂ s₁ ⊆ Set.Ioo 0 η := fun t ht => ⟨hs₂.1.trans_lt ht.1, ht.2.trans hs₁.2⟩
  have hcont : ContinuousOn φ (Set.Icc s₂ s₁) := hφ.2.2.1.mono hIcc
  have hdiff : DifferentiableOn ℝ φ (Set.Ioo s₂ s₁) := hφ.2.2.2.2.1.mono hIoo
  obtain ⟨c, hc, hslope⟩ := exists_deriv_eq_slope φ hlt hcont hdiff
  have hc_in : c ∈ Set.Ioo 0 η := hIoo hc
  have hanti : deriv φ s₁ ≤ deriv φ c := hφ.antitoneOn_deriv hc_in hs₁ hc.2.le
  rw [hslope] at hanti
  have hpos : 0 < s₁ - s₂ := sub_pos.mpr hlt
  exact (le_div_iff₀ hpos).mp hanti

lemma DesingularizingFunction.nonneg {η : ℝ} {φ : ℝ → ℝ}
    (hφ : DesingularizingFunction η φ) {s : ℝ} (hs : s ∈ Set.Ico 0 η) :
    0 ≤ φ s := by
  rcases eq_or_lt_of_le hs.1 with rfl | hpos
  · simp [hφ.2.1]
  · have hmul := hφ.mul_sub_le ⟨le_rfl, hφ.1⟩ ⟨hpos, hs.2⟩ hpos.le
    rw [sub_zero, hφ.2.1, sub_zero] at hmul
    have hderiv : 0 < deriv φ s := hφ.2.2.2.2.2.2 s ⟨hpos, hs.2⟩
    exact (mul_pos hderiv hpos).le.trans hmul

lemma concaveOn_finset_sum {ι : Type*} (S : Finset ι) {D : Set ℝ} (hD : Convex ℝ D)
    {φs : ι → ℝ → ℝ} (hφ : ∀ z ∈ S, ConcaveOn ℝ D (φs z)) :
    ConcaveOn ℝ D (fun s => ∑ z ∈ S, φs z s) := by
  refine ⟨hD, fun x hx y hy a b ha hb hab => ?_⟩
  simp only [smul_eq_mul]
  rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
  refine Finset.sum_le_sum fun z hz => ?_
  exact (hφ z hz).2 hx hy ha hb hab

lemma DesingularizingFunction.finset_sum {ι : Type*} (S : Finset ι) (hS : S.Nonempty)
    {ηz : ι → ℝ} {φz : ι → ℝ → ℝ} (hφ : ∀ z ∈ S, DesingularizingFunction (ηz z) (φz z)) :
    DesingularizingFunction (S.inf' hS ηz) (fun s => ∑ z ∈ S, φz z s) := by
  set η : ℝ := S.inf' hS ηz
  have hη_pos : 0 < η := (Finset.lt_inf'_iff hS).mpr fun z hz => (hφ z hz).1
  have h0 : (∑ z ∈ S, φz z 0) = 0 := Finset.sum_eq_zero fun z hz => (hφ z hz).2.1
  have hcont : ContinuousOn (fun s => ∑ z ∈ S, φz z s) (Set.Ico 0 η) := by
    refine continuousOn_finset_sum S fun z hz => ?_
    exact (hφ z hz).2.2.1.mono (Set.Ico_subset_Ico_right (Finset.inf'_le ηz hz))
  have hconc : ConcaveOn ℝ (Set.Ioo 0 η) (fun s => ∑ z ∈ S, φz z s) := by
    refine concaveOn_finset_sum S (convex_Ioo 0 η) fun z hz => ?_
    have hsub : Set.Ioo 0 η ⊆ Set.Ioo 0 (ηz z) := Set.Ioo_subset_Ioo_right (Finset.inf'_le ηz hz)
    exact ⟨convex_Ioo 0 η, fun x hx y hy a b ha hb hab =>
      (hφ z hz).2.2.2.1.2 (hsub hx) (hsub hy) ha hb hab⟩
  have hhasDeriv : ∀ s ∈ Set.Ioo 0 η,
      HasDerivAt (fun t => ∑ z ∈ S, φz z t) (∑ z ∈ S, deriv (φz z) s) s := by
    intro s hs
    refine HasDerivAt.fun_sum fun z hz => ?_
    have hs_z : s ∈ Set.Ioo 0 (ηz z) := ⟨hs.1, hs.2.trans_le (Finset.inf'_le ηz hz)⟩
    exact ((hφ z hz).2.2.2.2.1 s hs_z).differentiableAt (isOpen_Ioo.mem_nhds hs_z) |>.hasDerivAt
  have hdiff : DifferentiableOn ℝ (fun s => ∑ z ∈ S, φz z s) (Set.Ioo 0 η) :=
    fun s hs => (hhasDeriv s hs).differentiableAt.differentiableWithinAt
  have hderiv_eq : Set.EqOn (deriv (fun s => ∑ z ∈ S, φz z s))
      (fun s => ∑ z ∈ S, deriv (φz z) s) (Set.Ioo 0 η) :=
    fun s hs => (hhasDeriv s hs).deriv
  have hcont_deriv : ContinuousOn (deriv (fun s => ∑ z ∈ S, φz z s)) (Set.Ioo 0 η) := by
    refine ContinuousOn.congr ?_ hderiv_eq
    refine continuousOn_finset_sum S fun z hz => ?_
    exact (hφ z hz).2.2.2.2.2.1.mono (Set.Ioo_subset_Ioo_right (Finset.inf'_le ηz hz))
  have hpos_deriv : ∀ s ∈ Set.Ioo 0 η, 0 < deriv (fun s => ∑ z ∈ S, φz z s) s := by
    intro s hs
    rw [hderiv_eq hs]
    refine Finset.sum_pos (fun z hz => ?_) hS
    exact (hφ z hz).2.2.2.2.2.2 s ⟨hs.1, hs.2.trans_le (Finset.inf'_le ηz hz)⟩
  exact ⟨hη_pos, h0, hcont, hconc, hdiff, hcont_deriv, hpos_deriv⟩

end Desingularizing

section KLProperty

variable {n : ℕ}

/-- Pointwise Kurdyka–Łojasiewicz (KŁ) property of `f : E n → EReal` at `x_bar`. -/
def HasKLAt (f : E n → EReal) (x_bar : E n) : Prop :=
  x_bar ∈ effectiveDom f →
    ∃ η > (0 : ℝ), ∃ U ∈ 𝓝 x_bar, ∃ φ : ℝ → ℝ,
      DesingularizingFunction η φ ∧
        ∀ x ∈ U, x ∈ effectiveDom f →
          (f x_bar).toReal < (f x).toReal →
          (f x).toReal < (f x_bar).toReal + η →
          ∀ ω ∈ limitingSubdiff f x,
            1 ≤ deriv φ ((f x).toReal - (f x_bar).toReal) * ‖ω‖

/-- Global Kurdyka–Łojasiewicz property of `f` on `dom(∂ f)`. -/
def HasKL (f : E n → EReal) : Prop :=
  ∀ x_bar, (limitingSubdiff f x_bar).Nonempty → HasKLAt f x_bar

/-- The `ω`-limit set of a sequence `x : ℕ → E n`. -/
def omegaLimitSet (x : ℕ → E n) : Set (E n) :=
  {z | ∃ ψ : ℕ → ℕ, StrictMono ψ ∧ Tendsto (x ∘ ψ) atTop (𝓝 z)}

lemma omegaLimitSet_nonempty {x : ℕ → E n} (hbdd : Bornology.IsBounded (Set.range x)) :
    (omegaLimitSet x).Nonempty := by
  obtain ⟨z, _, ψ, hψ, hlim⟩ := tendsto_subseq_of_bounded hbdd (fun k => Set.mem_range_self k)
  exact ⟨z, ψ, hψ, hlim⟩

lemma omegaLimitSet_isClosed (x : ℕ → E n) : IsClosed (omegaLimitSet x) := by
  rw [← isSeqClosed_iff_isClosed]
  intro zn z hzn hzlim
  have hpick : ∀ m : ℕ, ∃ k ≥ m, ‖x k - zn m‖ < 1 / ((m : ℝ) + 1) := by
    intro m
    rcases hzn m with ⟨ψ, hψ_mono, hψ_lim⟩
    have hnear : ∀ᶠ j in atTop, ‖x (ψ j) - zn m‖ < 1 / ((m : ℝ) + 1) := by
      simpa [dist_eq_norm] using
        Metric.tendsto_nhds.mp hψ_lim (1 / ((m : ℝ) + 1)) (by positivity)
    rcases eventually_atTop.mp hnear with ⟨J, hJ⟩
    set j := max J m
    refine ⟨ψ j, ?_, hJ j (le_max_left J m)⟩
    exact (le_max_right J m).trans (hψ_mono.id_le j)
  choose idx hidx_ge hidx_near using hpick
  let seq : ℕ → ℕ := Nat.rec (idx 0) (fun m prev => idx (max (prev + 1) (m + 1)))
  have hseq_succ : ∀ m, seq m < seq (m + 1) := by
    intro m
    change seq m < idx (max (seq m + 1) (m + 1))
    exact lt_of_lt_of_le (lt_of_lt_of_le (Nat.lt_succ_self _) (le_max_left _ _))
      (hidx_ge (max (seq m + 1) (m + 1)))
  have hseq_mono : StrictMono seq := strictMono_nat_of_lt_succ hseq_succ
  have hseq_lim : Tendsto (x ∘ seq) atTop (𝓝 z) := by
    rw [Metric.tendsto_nhds]
    intro ε hε
    have hzn_near : ∀ᶠ m in atTop, dist (zn m) z < ε / 2 :=
      Metric.tendsto_nhds.mp hzlim (ε / 2) (by positivity)
    have hinv : ∀ᶠ m : ℕ in atTop, (1 : ℝ) / ((m : ℝ) + 1) < ε / 2 := by
      have ht : Tendsto (fun m : ℕ => 1 / ((m : ℝ) + 1)) atTop (𝓝 0) :=
        tendsto_one_div_add_atTop_nhds_zero_nat
      exact ht.eventually (gt_mem_nhds (by positivity))
    rcases eventually_atTop.mp (hzn_near.and hinv) with ⟨M, hM⟩
    refine eventually_atTop.mpr ⟨M + 1, fun m hm => ?_⟩
    cases m with
    | zero => omega
    | succ m' =>
      set t := max (seq m' + 1) (m' + 1)
      have ht_ge : M ≤ t := by
        have hm' : M ≤ m' + 1 := by omega
        exact hm'.trans (le_max_right _ _)
      obtain ⟨h1, h2⟩ := hM t ht_ge
      have hseq_eq : (x ∘ seq) (m' + 1) = x (idx t) := rfl
      rw [hseq_eq]
      calc
        dist (x (idx t)) z ≤ dist (x (idx t)) (zn t) + dist (zn t) z := dist_triangle _ _ _
        _ = ‖x (idx t) - zn t‖ + dist (zn t) z := by rw [dist_eq_norm]
        _ < 1 / ((t : ℝ) + 1) + ε / 2 := add_lt_add (hidx_near t) h1
        _ < ε := by linarith
  exact ⟨seq, hseq_mono, hseq_lim⟩

lemma omegaLimitSet_subset_closure {x : ℕ → E n} :
    omegaLimitSet x ⊆ closure (Set.range x) := by
  rintro z ⟨ψ, _, hψ_lim⟩
  exact mem_closure_of_tendsto hψ_lim (Eventually.of_forall fun j => Set.mem_range_self (ψ j))

lemma omegaLimitSet_isCompact {x : ℕ → E n} (hbdd : Bornology.IsBounded (Set.range x)) :
    IsCompact (omegaLimitSet x) := by
  obtain ⟨R, hR⟩ := hbdd.subset_closedBall (0 : E n)
  have hsub : omegaLimitSet x ⊆ Metric.closedBall (0 : E n) R :=
    omegaLimitSet_subset_closure.trans (closure_minimal hR Metric.isClosed_closedBall)
  exact (isCompact_closedBall (0 : E n) R).of_isClosed_subset (omegaLimitSet_isClosed x) hsub

lemma tendsto_infDist_omegaLimitSet_zero {x : ℕ → E n}
    (hbdd : Bornology.IsBounded (Set.range x)) :
    Tendsto (fun k => Metric.infDist (x k) (omegaLimitSet x)) atTop (𝓝 0) := by
  by_contra hnot
  have hne : (omegaLimitSet x).Nonempty := omegaLimitSet_nonempty hbdd
  rw [Metric.tendsto_nhds] at hnot
  push_neg at hnot
  rcases hnot with ⟨ε, hε, hfreq⟩
  have hfreq_ev : ∀ N : ℕ, ∃ k ≥ N, ε ≤ Metric.infDist (x k) (omegaLimitSet x) := by
    intro N
    rcases Filter.frequently_atTop.mp hfreq N with ⟨k, hk, hdist⟩
    refine ⟨k, hk, ?_⟩
    have hnn : 0 ≤ Metric.infDist (x k) (omegaLimitSet x) := Metric.infDist_nonneg
    simpa [Real.dist_eq, abs_of_nonneg hnn] using hdist
  let ψ : ℕ → ℕ := Nat.rec (Classical.choose (hfreq_ev 0))
    (fun _ prev => Classical.choose (hfreq_ev (prev + 1)))
  have hψ_mono : StrictMono ψ := by
    refine strictMono_nat_of_lt_succ fun m => ?_
    change ψ m < Classical.choose (hfreq_ev (ψ m + 1))
    exact Nat.lt_of_lt_of_le (Nat.lt_succ_self _)
      (Classical.choose_spec (hfreq_ev (ψ m + 1))).1
  have hψ_ge : ∀ m, ε ≤ Metric.infDist (x (ψ m)) (omegaLimitSet x) := by
    intro m
    cases m with
    | zero => exact (Classical.choose_spec (hfreq_ev 0)).2
    | succ m' => exact (Classical.choose_spec (hfreq_ev (ψ m' + 1))).2
  obtain ⟨z, _, φ, hφ_mono, hφ_lim⟩ :=
    tendsto_subseq_of_bounded hbdd (fun m => Set.mem_range_self (ψ m))
  have hz_mem : z ∈ omegaLimitSet x := ⟨ψ ∘ φ, hψ_mono.comp hφ_mono, hφ_lim⟩
  have hdist_lim : Tendsto (fun m => Metric.infDist (x (ψ (φ m))) (omegaLimitSet x)) atTop
      (𝓝 (Metric.infDist z (omegaLimitSet x))) :=
    (Metric.continuous_infDist_pt (omegaLimitSet x)).tendsto z |>.comp hφ_lim
  have hz_zero : Metric.infDist z (omegaLimitSet x) = 0 :=
    le_antisymm ((Metric.infDist_le_dist_of_mem hz_mem).trans_eq (dist_self z))
      Metric.infDist_nonneg
  rw [hz_zero] at hdist_lim
  have hlt : ∀ᶠ m in atTop, Metric.infDist (x (ψ (φ m))) (omegaLimitSet x) < ε :=
    hdist_lim.eventually (gt_mem_nhds hε)
  rcases hlt.exists with ⟨m, hm⟩
  exact (not_lt_of_ge (hψ_ge (φ m))) hm

/-- Uniformized Kurdyka–Łojasiewicz Lemma on a nonempty compact set `Ω` where `f` is constant. -/
theorem uniformized_kl {f : E n → EReal} {Ω : Set (E n)} {f_star : ℝ}
    (hΩ_ne : Ω.Nonempty) (hΩ_cpct : IsCompact Ω)
    (hΩ_dom : ∀ z ∈ Ω, z ∈ effectiveDom f)
    (hΩ_const : ∀ z ∈ Ω, (f z).toReal = f_star)
    (hΩ_sub : ∀ z ∈ Ω, (limitingSubdiff f z).Nonempty)
    (hKL : HasKL f) :
    ∃ ε > (0 : ℝ), ∃ η > (0 : ℝ), ∃ φ : ℝ → ℝ,
      DesingularizingFunction η φ ∧
        ∀ x : E n, Metric.infDist x Ω < ε → x ∈ effectiveDom f →
          f_star < (f x).toReal → (f x).toReal < f_star + η →
          ∀ ω ∈ limitingSubdiff f x, 1 ≤ deriv φ ((f x).toReal - f_star) * ‖ω‖ := by
  have hpt : ∀ z : Ω, ∃ (ηz : ℝ) (rz : ℝ) (φz : ℝ → ℝ),
      0 < ηz ∧ 0 < rz ∧ DesingularizingFunction ηz φz ∧
      ∀ x ∈ Metric.ball (z : E n) rz, x ∈ effectiveDom f →
        f_star < (f x).toReal → (f x).toReal < f_star + ηz →
        ∀ ω ∈ limitingSubdiff f x, 1 ≤ deriv φz ((f x).toReal - f_star) * ‖ω‖ := by
    intro ⟨z, hzΩ⟩
    obtain ⟨ηz, hηz, Uz, hUz, φz, hφz, hkl⟩ := hKL z (hΩ_sub z hzΩ) (hΩ_dom z hzΩ)
    obtain ⟨rz, hrz, hball⟩ := Metric.mem_nhds_iff.mp hUz
    refine ⟨ηz, rz, φz, hηz, hrz, hφz, fun x hx hx_dom hlt1 hlt2 ω hω => ?_⟩
    rw [← hΩ_const z hzΩ] at hlt1 hlt2 ⊢
    exact hkl x (hball hx) hx_dom hlt1 hlt2 ω hω
  choose ηz rz φz hηz_pos hrz_pos hφz_des hkl_ball using hpt
  have hcov : Ω ⊆ ⋃ z : Ω, Metric.ball (z : E n) (rz z) := fun z hz =>
    Set.mem_iUnion.mpr ⟨⟨z, hz⟩, Metric.mem_ball_self (hrz_pos ⟨z, hz⟩)⟩
  obtain ⟨S, hS_cov⟩ := hΩ_cpct.elim_finite_subcover (fun z : Ω => Metric.ball (z : E n) (rz z))
    (fun _ => Metric.isOpen_ball) hcov
  have hS_ne : S.Nonempty := by
    rcases hΩ_ne with ⟨z₀, hz₀⟩
    have hz₀_in := hS_cov hz₀
    rw [Set.mem_iUnion] at hz₀_in
    rcases hz₀_in with ⟨z, hz⟩
    exact ⟨z, (Set.mem_iUnion.mp hz).1⟩
  set U_union : Set (E n) := ⋃ z ∈ S, Metric.ball (z : E n) (rz z)
  have hU_open : IsOpen U_union :=
    isOpen_biUnion fun z _ => Metric.isOpen_ball
  obtain ⟨ε, hε_pos, hthick⟩ := hΩ_cpct.exists_thickening_subset_open hU_open hS_cov
  set η : ℝ := S.inf' hS_ne ηz
  set φ : ℝ → ℝ := fun s => ∑ z ∈ S, φz z s
  have hφ_des : DesingularizingFunction η φ :=
    DesingularizingFunction.finset_sum S hS_ne (fun z _ => hφz_des z)
  refine ⟨ε, hε_pos, η, hφ_des.1, φ, hφ_des, fun x hx_dist hx_dom hlt1 hlt2 ω hω => ?_⟩
  have hx_thick : x ∈ Metric.thickening ε Ω :=
    Metric.mem_thickening_iff.mpr ((Metric.infDist_lt_iff hΩ_ne).mp hx_dist)
  have hx_U : x ∈ U_union := hthick hx_thick
  rw [Set.mem_iUnion₂] at hx_U
  rcases hx_U with ⟨z, hzS, hz_ball⟩
  have hη_le : η ≤ ηz z := Finset.inf'_le ηz hzS
  have h_pt : 1 ≤ deriv (φz z) ((f x).toReal - f_star) * ‖ω‖ :=
    hkl_ball z x hz_ball hx_dom hlt1 (hlt2.trans_le (add_le_add_right hη_le f_star)) ω hω
  set s : ℝ := (f x).toReal - f_star
  have hs_in : s ∈ Set.Ioo 0 η := ⟨sub_pos.mpr hlt1, sub_lt_iff_lt_add'.mpr hlt2⟩
  have hhasDeriv : HasDerivAt φ (∑ w ∈ S, deriv (φz w) s) s := by
    refine HasDerivAt.fun_sum fun w hw => ?_
    have hsw : s ∈ Set.Ioo 0 (ηz w) := ⟨hs_in.1, hs_in.2.trans_le (Finset.inf'_le ηz hw)⟩
    exact ((hφz_des w).2.2.2.2.1 s hsw).differentiableAt (isOpen_Ioo.mem_nhds hsw) |>.hasDerivAt
  have hderiv_ge : deriv (φz z) s ≤ deriv φ s := by
    rw [hhasDeriv.deriv]
    refine Finset.single_le_sum (f := fun w => deriv (φz w) s) (fun w hw => ?_) hzS
    have hsw : s ∈ Set.Ioo 0 (ηz w) := ⟨hs_in.1, hs_in.2.trans_le (Finset.inf'_le ηz hw)⟩
    exact ((hφz_des w).2.2.2.2.2.2 s hsw).le
  exact h_pt.trans (mul_le_mul_of_nonneg_right hderiv_ge (norm_nonneg ω))

end KLProperty

section TheoremA8

variable {n : ℕ}

/-- Theorem A.8 of [3] (Bolte–Sabach–Teboulle [1]): any bounded sequence satisfying sufficient
decrease `(H1)`, relative error `(H2)`, and subsequence continuity `(H3)` for a proper, lower
semicontinuous, bounded-below KŁ function has finite length and converges to a critical point. -/
theorem theorem_A8 {f : E n → EReal} {x : ℕ → E n} {c₁ b : ℝ}
    (hf_proper : IsProper f)
    (_hf_lsc : LowerSemicontinuous f)
    (hf_bdd : ∃ m : ℝ, ∀ z : E n, (m : EReal) ≤ f z)
    (hf_kl : HasKL f)
    (hx0_dom : x 0 ∈ effectiveDom f)
    (hx_bdd : Bornology.IsBounded (Set.range x))
    (hc₁ : 0 < c₁)
    (hH1 : ∀ k : ℕ, f (x (k + 1)) + ((c₁ * ‖x (k + 1) - x k‖ ^ 2 : ℝ) : EReal) ≤ f (x k))
    (hb : 0 < b)
    (hH2 : ∀ k : ℕ, ∃ ω ∈ limitingSubdiff f (x (k + 1)), ‖ω‖ ≤ b * ‖x (k + 1) - x k‖)
    (hH3 : ∀ (x_bar : E n) (ψ : ℕ → ℕ), StrictMono ψ →
      Tendsto (x ∘ ψ) atTop (𝓝 x_bar) →
      Tendsto (fun j => f (x (ψ j))) atTop (𝓝 (f x_bar))) :
    Summable (fun k => ‖x (k + 1) - x k‖) ∧
      ∃ x_inf : E n, Tendsto x atTop (𝓝 x_inf) ∧ x_inf ∈ crit f := by
  have hx_dom : ∀ k : ℕ, x k ∈ effectiveDom f := by
    intro k
    induction k with
    | zero => exact hx0_dom
    | succ k ih =>
      refine ⟨?_, hf_proper.2 _⟩
      intro htop
      have hle := hH1 k
      rw [htop, EReal.top_add_coe] at hle
      exact ih.1 (top_le_iff.mp hle)
  let fk : ℕ → ℝ := fun k => (f (x k)).toReal
  have hfk_H1 : ∀ k : ℕ, fk (k + 1) + c₁ * ‖x (k + 1) - x k‖ ^ 2 ≤ fk k := by
    intro k
    have hle := hH1 k
    rw [← EReal.coe_toReal_of_mem_effectiveDom (hx_dom (k + 1)),
      ← EReal.coe_toReal_of_mem_effectiveDom (hx_dom k),
      ← EReal.coe_add, EReal.coe_le_coe_iff] at hle
    exact hle
  have hfk_anti : Antitone fk := by
    refine antitone_nat_of_succ_le fun k => ?_
    have hnn : 0 ≤ c₁ * ‖x (k + 1) - x k‖ ^ 2 := by positivity
    linarith [hfk_H1 k]
  rcases hf_bdd with ⟨m, hm⟩
  have hfk_bdd : ∀ k, m ≤ fk k := by
    intro k
    have hle := hm (x k)
    rwa [← EReal.coe_toReal_of_mem_effectiveDom (hx_dom k), EReal.coe_le_coe_iff] at hle
  have hfk_bddBelow : BddBelow (Set.range fk) := ⟨m, by rintro _ ⟨k, rfl⟩; exact hfk_bdd k⟩
  set f_star : ℝ := ⨅ k : ℕ, fk k
  have hfk_lim : Tendsto fk atTop (𝓝 f_star) :=
    tendsto_atTop_ciInf hfk_anti hfk_bddBelow
  have hf_star_le : ∀ k : ℕ, f_star ≤ fk k := fun k => ciInf_le hfk_bddBelow k
  have hdiff_tendsto : Tendsto (fun k => ‖x (k + 1) - x k‖) atTop (𝓝 0) := by
    have hsq_lim : Tendsto (fun k => c₁ * ‖x (k + 1) - x k‖ ^ 2) atTop (𝓝 0) := by
      have h0 : Tendsto (fun k => fk k - fk (k + 1)) atTop (𝓝 (f_star - f_star)) :=
        hfk_lim.sub (hfk_lim.comp (tendsto_add_atTop_nat 1))
      rw [sub_self] at h0
      refine tendsto_of_tendsto_of_tendsto_of_le_of_le tendsto_const_nhds h0 (fun k => by positivity) ?_
      intro k
      linarith [hfk_H1 k]
    have hsq0 : Tendsto (fun k => ‖x (k + 1) - x k‖ ^ 2) atTop (𝓝 0) := by
      have hdiv := hsq_lim.const_mul (1 / c₁)
      simp only [mul_zero] at hdiv
      refine hdiv.congr' (Eventually.of_forall fun k => ?_)
      field_simp
    have hsqrt := (Real.continuous_sqrt.tendsto 0).comp hsq0
    rw [Real.sqrt_zero] at hsqrt
    refine hsqrt.congr' (Eventually.of_forall fun k => ?_)
    exact Real.sqrt_sq (norm_nonneg _)
  -- Case split: either `fk` reaches `f_star` in finite time, or `f_star < fk k` for all `k`.
  by_cases hreach : ∃ k₀ : ℕ, fk k₀ = f_star
  · rcases hreach with ⟨k₀, hk₀⟩
    have hconst : ∀ k ≥ k₀, x k = x k₀ := by
      intro k hk
      obtain ⟨r, rfl⟩ := Nat.exists_eq_add_of_le hk
      induction r with
      | zero => rfl
      | succ r ih =>
        have hstep := hfk_H1 (k₀ + r)
        have h1 : fk (k₀ + r) ≤ fk k₀ := hfk_anti (Nat.le_add_right k₀ r)
        have h2 : f_star ≤ fk (k₀ + r + 1) := hf_star_le (k₀ + r + 1)
        have hsq_le : c₁ * ‖x (k₀ + r + 1) - x (k₀ + r)‖ ^ 2 ≤ 0 := by linarith
        have hsq_eq : ‖x (k₀ + r + 1) - x (k₀ + r)‖ ^ 2 = 0 := by
          nlinarith [sq_nonneg ‖x (k₀ + r + 1) - x (k₀ + r)‖]
        rw [sq_eq_zero_iff, norm_eq_zero, sub_eq_zero] at hsq_eq
        rw [← add_assoc, hsq_eq, ih (Nat.le_add_right k₀ r)]
    have hsumm : Summable (fun k => ‖x (k + 1) - x k‖) := by
      rw [← summable_nat_add_iff k₀]
      refine (summable_zero : Summable (fun _ : ℕ => (0 : ℝ))).congr fun m => ?_
      have h1 := hconst (m + k₀ + 1) (by omega)
      have h2 := hconst (m + k₀) (by omega)
      rw [h1, h2, sub_self, norm_zero]
    refine ⟨hsumm, x k₀, tendsto_atTop_of_eventually_const fun k hk => hconst k hk, ?_⟩
    rcases hH2 k₀ with ⟨ω, hω_mem, hω_norm⟩
    have hx_eq : x (k₀ + 1) = x k₀ := hconst (k₀ + 1) (Nat.le_succ k₀)
    rw [hx_eq, sub_self, norm_zero, mul_zero] at hω_norm
    have hω0 : ω = 0 := norm_eq_zero.mp (le_antisymm hω_norm (norm_nonneg _))
    rw [hx_eq, hω0] at hω_mem
    exact hω_mem
  · push_neg at hreach
    have hfk_gt : ∀ k : ℕ, f_star < fk k := fun k => lt_of_le_of_ne (hf_star_le k) (hreach k).symm
    set Ω : Set (E n) := omegaLimitSet x
    have hΩ_ne : Ω.Nonempty := omegaLimitSet_nonempty hx_bdd
    have hΩ_cpct : IsCompact Ω := omegaLimitSet_isCompact hx_bdd
    have hΩ_props : ∀ z ∈ Ω, z ∈ effectiveDom f ∧ (f z).toReal = f_star ∧ z ∈ crit f := by
      rintro z ⟨ψ, hψ_mono, hψ_lim⟩
      have hf_sub : Tendsto (fun j => f (x (ψ j))) atTop (𝓝 (f_star : EReal)) := by
        have hcoe := (EReal.continuous_coe_iff.mpr continuous_id).tendsto f_star |>.comp
          (hfk_lim.comp hψ_mono.tendsto_atTop)
        refine hcoe.congr' (Eventually.of_forall fun j => ?_)
        exact EReal.coe_toReal_of_mem_effectiveDom (hx_dom (ψ j))
      have hfz : f z = (f_star : EReal) :=
        tendsto_nhds_unique (hH3 z ψ hψ_mono hψ_lim) hf_sub
      have hz_dom : z ∈ effectiveDom f := by
        rw [effectiveDom, Set.mem_setOf_eq, hfz]
        exact ⟨EReal.coe_ne_top _, EReal.coe_ne_bot _⟩
      have hz_toReal : (f z).toReal = f_star := by rw [hfz, EReal.toReal_coe]
      refine ⟨hz_dom, hz_toReal, ?_⟩
      -- Shift `ψ` by 1 so `ψ' j ≥ j + 1`, and apply attentive closedness with `(H2)`.
      let ψ' : ℕ → ℕ := fun j => ψ (j + 1)
      have hψ'_mono : StrictMono ψ' :=
        hψ_mono.comp (strictMono_nat_of_lt_succ fun j => Nat.lt_succ_self _)
      have hψ'_ge : ∀ j, j + 1 ≤ ψ' j := fun j => hψ_mono.id_le (j + 1)
      have hxk_lim : Tendsto (fun j => x (ψ' j)) atTop (𝓝 z) :=
        hψ_lim.comp (tendsto_add_atTop_nat 1)
      have hfk_sub : Tendsto (fun j => (f (x (ψ' j))).toReal) atTop (𝓝 (f z).toReal) := by
        rw [hz_toReal]
        exact hfk_lim.comp hψ'_mono.tendsto_atTop
      have hω_ex : ∀ j, ∃ ω ∈ limitingSubdiff f (x (ψ' j)),
          ‖ω‖ ≤ b * ‖x (ψ' j) - x (ψ' j - 1)‖ := by
        intro j
        have hj1 : ψ' j - 1 + 1 = ψ' j := by have := hψ'_ge j; omega
        obtain ⟨ω, hω_mem, hω_norm⟩ := hH2 (ψ' j - 1)
        rw [hj1] at hω_mem hω_norm
        exact ⟨ω, hω_mem, hω_norm⟩
      choose ωk hωk_mem hωk_norm using hω_ex
      have hωk_lim : Tendsto ωk atTop (𝓝 (0 : E n)) := by
        rw [tendsto_zero_iff_norm_tendsto_zero]
        have hm_tend : Tendsto (fun j => ψ' j - 1) atTop atTop := by
          rw [tendsto_atTop_atTop]
          intro M
          refine ⟨M, fun j hj => ?_⟩
          have hj_ge := hψ'_ge j
          omega
        have hstep_lim : Tendsto (fun j => b * ‖x (ψ' j) - x (ψ' j - 1)‖) atTop (𝓝 0) := by
          have h0 := (hdiff_tendsto.comp hm_tend).const_mul b
          rw [mul_zero] at h0
          refine h0.congr' (Eventually.of_forall fun j => ?_)
          have hj1 : ψ' j - 1 + 1 = ψ' j := by have := hψ'_ge j; omega
          dsimp only [Function.comp_def]
          rw [hj1]
        exact tendsto_of_tendsto_of_tendsto_of_le_of_le tendsto_const_nhds hstep_lim
          (fun _ => norm_nonneg _) hωk_norm
      exact limitingSubdiff_closed_attentive hz_dom hxk_lim hfk_sub hωk_mem hωk_lim
    obtain ⟨ε, hε, η, hη, φ, hφ_des, hkl_unif⟩ :=
      uniformized_kl hΩ_ne hΩ_cpct (fun z hz => (hΩ_props z hz).1) (fun z hz => (hΩ_props z hz).2.1)
        (fun z hz => ⟨0, (hΩ_props z hz).2.2⟩) hf_kl
    have hdist_ev : ∀ᶠ k in atTop, Metric.infDist (x k) Ω < ε :=
      (tendsto_infDist_omegaLimitSet_zero hx_bdd).eventually (gt_mem_nhds hε)
    have hfk_ev : ∀ᶠ k in atTop, fk k < f_star + η :=
      hfk_lim.eventually (gt_mem_nhds (lt_add_of_pos_right f_star hη))
    rcases eventually_atTop.mp (hdist_ev.and hfk_ev) with ⟨K, hK⟩
    set C : ℝ := b / c₁
    have hC_pos : 0 < C := div_pos hb hc₁
    let d : ℕ → ℝ := fun k => ‖x (k + 1) - x k‖
    let Δφ : ℕ → ℝ := fun k => φ (fk k - f_star) - φ (fk (k + 1) - f_star)
    have hΔφ_nonneg : ∀ k ≥ K, 0 ≤ Δφ k := by
      intro k hk
      have hk_in : fk k - f_star ∈ Set.Ioo 0 η :=
        ⟨sub_pos.mpr (hfk_gt k), sub_lt_iff_lt_add'.mpr (hK k hk).2⟩
      have hk1_in : fk (k + 1) - f_star ∈ Set.Ico 0 η :=
        ⟨(sub_pos.mpr (hfk_gt (k + 1))).le,
          (hfk_anti (Nat.le_succ k)).trans_lt (hK k hk).2 |> sub_lt_iff_lt_add'.mpr⟩
      have hle_s : fk (k + 1) - f_star ≤ fk k - f_star :=
        sub_le_sub_right (hfk_anti (Nat.le_succ k)) f_star
      have hmul := hφ_des.mul_sub_le hk1_in hk_in hle_s
      have hderiv_pos : 0 < deriv φ (fk k - f_star) := hφ_des.2.2.2.2.2.2 _ hk_in
      have hsub_nn : 0 ≤ (fk k - f_star) - (fk (k + 1) - f_star) := sub_nonneg.mpr hle_s
      exact (mul_nonneg hderiv_pos.le hsub_nn).trans hmul
    have hkey : ∀ m : ℕ, 2 * d (K + 1 + m) ≤ d (K + m) + C * Δφ (K + 1 + m) := by
      intro m
      set k := K + 1 + m
      have hk_ge : K ≤ k := by omega
      have hkm1_add : K + m + 1 = k := by omega
      obtain ⟨ω, hω_mem, hω_norm⟩ := hH2 (K + m)
      rw [hkm1_add] at hω_mem
      have hω_norm' : ‖ω‖ ≤ b * d (K + m) := by simpa [d, hkm1_add] using hω_norm
      have hk_in : fk k - f_star ∈ Set.Ioo 0 η :=
        ⟨sub_pos.mpr (hfk_gt k), sub_lt_iff_lt_add'.mpr (hK k hk_ge).2⟩
      have hk1_in : fk (k + 1) - f_star ∈ Set.Ico 0 η :=
        ⟨(sub_pos.mpr (hfk_gt (k + 1))).le,
          (hfk_anti (Nat.le_succ k)).trans_lt (hK k hk_ge).2 |> sub_lt_iff_lt_add'.mpr⟩
      have hkl_k : 1 ≤ deriv φ (fk k - f_star) * ‖ω‖ :=
        hkl_unif (x k) (hK k hk_ge).1 (hx_dom k) (hfk_gt k) (hK k hk_ge).2 ω hω_mem
      have hderiv_pos : 0 < deriv φ (fk k - f_star) := hφ_des.2.2.2.2.2.2 _ hk_in
      have hkl_d : 1 ≤ deriv φ (fk k - f_star) * (b * d (K + m)) :=
        hkl_k.trans (mul_le_mul_of_nonneg_left hω_norm' hderiv_pos.le)
      have hle_s : fk (k + 1) - f_star ≤ fk k - f_star :=
        sub_le_sub_right (hfk_anti (Nat.le_succ k)) f_star
      have hconc_k := hφ_des.mul_sub_le hk1_in hk_in hle_s
      have hsub_eq : (fk k - f_star) - (fk (k + 1) - f_star) = fk k - fk (k + 1) := by ring
      rw [hsub_eq] at hconc_k
      have h_fdiff_le : fk k - fk (k + 1) ≤ (b * d (K + m)) * Δφ k := by
        have h_1 : fk k - fk (k + 1) ≤
            deriv φ (fk k - f_star) * (b * d (K + m)) * (fk k - fk (k + 1)) := by
          calc
            fk k - fk (k + 1) = 1 * (fk k - fk (k + 1)) := (one_mul _).symm
            _ ≤ (deriv φ (fk k - f_star) * (b * d (K + m))) * (fk k - fk (k + 1)) :=
              mul_le_mul_of_nonneg_right hkl_d (sub_nonneg.mpr (hfk_anti (Nat.le_succ k)))
        have h_2 : deriv φ (fk k - f_star) * (b * d (K + m)) * (fk k - fk (k + 1)) =
            (b * d (K + m)) * (deriv φ (fk k - f_star) * (fk k - fk (k + 1))) := by ring
        rw [h_2] at h_1
        exact h_1.trans (mul_le_mul_of_nonneg_left hconc_k (by positivity))
      have h_sq : d k ^ 2 ≤ (C * Δφ k) * d (K + m) := by
        have h1 : c₁ * d k ^ 2 ≤ fk k - fk (k + 1) := by
          dsimp [d]
          linarith [hfk_H1 k]
        have h2 : c₁ * d k ^ 2 ≤ (b * d (K + m)) * Δφ k := h1.trans h_fdiff_le
        have h3 := (le_div_iff₀' hc₁).mpr h2
        calc
          d k ^ 2 ≤ (b * d (K + m)) * Δφ k / c₁ := h3
          _ = (C * Δφ k) * d (K + m) := by dsimp [C]; ring
      have h_amgm : 4 * (C * Δφ k) * d (K + m) ≤ (d (K + m) + C * Δφ k) ^ 2 := by
        nlinarith [sq_nonneg (d (K + m) - C * Δφ k)]
      have h_sq4 : (2 * d k) ^ 2 ≤ (d (K + m) + C * Δφ k) ^ 2 := by
        calc
          (2 * d k) ^ 2 = 4 * d k ^ 2 := by ring
          _ ≤ 4 * ((C * Δφ k) * d (K + m)) := mul_le_mul_of_nonneg_left h_sq (by norm_num)
          _ = 4 * (C * Δφ k) * d (K + m) := by ring
          _ ≤ (d (K + m) + C * Δφ k) ^ 2 := h_amgm
      have h_rhs_nn : 0 ≤ d (K + m) + C * Δφ k := by
        have hnn1 : 0 ≤ d (K + m) := norm_nonneg _
        have hnn2 : 0 ≤ C * Δφ k := mul_nonneg hC_pos.le (hΔφ_nonneg k hk_ge)
        linarith
      nlinarith [sq_nonneg (2 * d k), sq_nonneg (d (K + m) + C * Δφ k)]
    have h_tele : ∀ N : ℕ, ∑ m ∈ Finset.range N, Δφ (K + 1 + m) =
        φ (fk (K + 1) - f_star) - φ (fk (K + 1 + N) - f_star) := by
      intro N
      induction N with
      | zero => simp
      | succ N' ih =>
        rw [Finset.sum_range_succ, ih]
        dsimp [Δφ]
        have heq1 : K + 1 + (N' + 1) = K + 1 + N' + 1 := by ring
        rw [heq1]
        ring
    have hsum_le : ∀ N : ℕ, ∑ m ∈ Finset.range N, d (K + 1 + m) ≤
        d K + C * φ (fk (K + 1) - f_star) := by
      intro N
      have h2sum : 2 * ∑ m ∈ Finset.range N, d (K + 1 + m) ≤
          (∑ m ∈ Finset.range N, d (K + m)) + C * ∑ m ∈ Finset.range N, Δφ (K + 1 + m) := by
        rw [Finset.mul_sum, Finset.mul_sum, ← Finset.sum_add_distrib]
        exact Finset.sum_le_sum fun m _ => hkey m
      have h_shift : ∑ m ∈ Finset.range N, d (K + m) ≤
          d K + ∑ m ∈ Finset.range N, d (K + 1 + m) := by
        cases N with
        | zero => simp [d]
        | succ N' =>
          rw [Finset.sum_range_succ' (fun m => d (K + m)) N', add_zero,
            Finset.sum_range_succ (fun m => d (K + 1 + m)) N']
          have hshift_eq : ∑ m ∈ Finset.range N', d (K + (m + 1)) =
              ∑ m ∈ Finset.range N', d (K + 1 + m) :=
            Finset.sum_congr rfl fun m _ => by ring_nf
          rw [hshift_eq]
          have hlast : 0 ≤ d (K + 1 + N') := norm_nonneg _
          linarith
      have hφ_end_nn : 0 ≤ φ (fk (K + 1 + N) - f_star) := by
        refine hφ_des.nonneg ?_
        have hge : K ≤ K + 1 + N := by omega
        exact ⟨(sub_pos.mpr (hfk_gt (K + 1 + N))).le,
          sub_lt_iff_lt_add'.mpr (hK (K + 1 + N) hge).2⟩
      have htele_le : ∑ m ∈ Finset.range N, Δφ (K + 1 + m) ≤ φ (fk (K + 1) - f_star) := by
        rw [h_tele N]
        linarith
      linarith [mul_le_mul_of_nonneg_left htele_le hC_pos.le]
    have hsumm_shift : Summable (fun m => d (K + 1 + m)) :=
      summable_of_sum_range_le (fun _ => norm_nonneg _) hsum_le
    have hsumm : Summable d := by
      rw [← summable_nat_add_iff (K + 1)]
      refine hsumm_shift.congr fun m => ?_
      ring_nf
    have hcauchy : CauchySeq x := cauchySeq_of_summable_dist <| by
      simpa [dist_eq_norm, norm_sub_rev, d] using hsumm
    obtain ⟨x_inf, hx_lim⟩ := cauchySeq_tendsto_of_complete hcauchy
    have hx_inf_omega : x_inf ∈ Ω := ⟨id, strictMono_id, hx_lim⟩
    exact ⟨hsumm, x_inf, hx_lim, (hΩ_props x_inf hx_inf_omega).2.2⟩

end TheoremA8

end DeqMdErratum
