import Mathlib

/-!
# Finite-Dimensional Variational Analysis Primitives

This module sets up the ambient Euclidean space `E n := EuclideanSpace ℝ (Fin n)` together with
proper extended-real functions, Fréchet (regular) subdifferentials, limiting (Mordukhovich)
subdifferentials, critical points, and normal cones, along with the calculus rules needed for
nonconvex composite optimization `f = g + h` with `g` smooth (`C¹`) on an open neighborhood.
-/

open Filter Topology
open scoped InnerProductSpace

namespace DeqMdErratum

/-- Ambient `n`-dimensional Euclidean space. -/
abbrev E (n : ℕ) := EuclideanSpace ℝ (Fin n)

section EuclideanHelpers

variable {n : ℕ}

lemma E_norm_sq_eq (x : E n) : ‖x‖ ^ 2 = ∑ j : Fin n, (x j) ^ 2 := by
  rw [EuclideanSpace.norm_sq_eq]
  refine Finset.sum_congr rfl fun j _ => ?_
  simp [Real.norm_eq_abs, sq_abs]

lemma E_norm_sq_sub_eq (x y : E n) : ‖x - y‖ ^ 2 = ∑ j : Fin n, (x j - y j) ^ 2 := by
  rw [E_norm_sq_eq]
  refine Finset.sum_congr rfl fun j _ => ?_
  simp

lemma E_inner_eq (x y : E n) : ⟪x, y⟫_ℝ = ∑ j : Fin n, x j * y j := by
  rw [PiLp.inner_apply]
  refine Finset.sum_congr rfl fun j _ => ?_
  simp [RCLike.inner_apply, mul_comm]

lemma E_abs_coord_le_norm (x : E n) (j : Fin n) : |x j| ≤ ‖x‖ := by
  have hsq : (x j) ^ 2 ≤ ‖x‖ ^ 2 := by
    rw [E_norm_sq_eq]
    exact Finset.single_le_sum (f := fun i => (x i) ^ 2) (fun i _ => sq_nonneg _) (Finset.mem_univ j)
  have hsqrt := Real.sqrt_le_sqrt hsq
  simpa [Real.sqrt_sq_eq_abs, Real.sqrt_sq (norm_nonneg x)] using hsqrt

lemma E_ext {x y : E n} (h : ∀ j, x j = y j) : x = y := by
  ext j
  exact h j

lemma E_single_apply (j i : Fin n) (c : ℝ) :
    (EuclideanSpace.single j c) i = if i = j then c else 0 := by
  simp

lemma E_inner_single_right (x : E n) (j : Fin n) :
    ⟪x, EuclideanSpace.single j (1 : ℝ)⟫_ℝ = x j := by
  simpa [real_inner_comm] using EuclideanSpace.inner_single_right j (1 : ℝ) x

lemma E_inner_single_left (j : Fin n) (x : E n) :
    ⟪EuclideanSpace.single j (1 : ℝ), x⟫_ℝ = x j := by
  rw [real_inner_comm]
  exact E_inner_single_right x j

lemma gradient_coord_eq_fderiv_single {g : E n → ℝ} {x : E n}
    (hg : DifferentiableAt ℝ g x) (j : Fin n) :
    gradient g x j = fderiv ℝ g x (EuclideanSpace.single j (1 : ℝ)) := by
  have hgrad : HasGradientAt g (gradient g x) x := hg.hasGradientAt
  have hfd : HasFDerivAt g ((InnerProductSpace.toDual ℝ (E n)) (gradient g x)) x :=
    hasGradientAt_iff_hasFDerivAt.mp hgrad
  rw [hfd.fderiv, InnerProductSpace.toDual_apply_apply]
  exact (E_inner_single_right (gradient g x) j).symm

lemma E_coord_continuous (j : Fin n) : Continuous (fun x : E n => x j) :=
  PiLp.continuous_apply 2 (fun _ : Fin n => ℝ) j

lemma E_mk_continuous {α : Type*} [TopologicalSpace α] (f : Fin n → α → ℝ)
    (hf : ∀ j, Continuous (f j)) :
    Continuous (fun t => WithLp.toLp 2 (fun j => f j t)) := by
  have hpi : Continuous (fun t => fun j : Fin n => f j t) := continuous_pi hf
  exact (PiLp.continuous_toLp 2 (fun _ : Fin n => ℝ)).comp hpi

lemma E_mk_continuousOn {α : Type*} [TopologicalSpace α] (f : Fin n → α → ℝ) (s : Set α)
    (hf : ∀ j, ContinuousOn (f j) s) :
    ContinuousOn (fun t => WithLp.toLp 2 (fun j => f j t)) s := by
  have hpi : ContinuousOn (fun t => fun j : Fin n => f j t) s := continuousOn_pi.mpr hf
  exact (PiLp.continuous_toLp 2 (fun _ : Fin n => ℝ)).comp_continuousOn hpi

end EuclideanHelpers

section ProperAndSubdiff

variable {n : ℕ}

lemma ereal_coe_add_eq_top_iff {a : ℝ} {b : EReal} :
    (a : EReal) + b = ⊤ ↔ b = ⊤ := by
  cases b with
  | bot => simp
  | top => simp
  | coe r =>
    have hne : ((a + r : ℝ) : EReal) ≠ ⊤ := EReal.coe_ne_top (a + r)
    simpa [EReal.coe_add] using hne

/-- The effective domain `{x | f x ≠ ⊤ ∧ f x ≠ ⊥}` of an extended-real function. -/
def effectiveDom (f : E n → EReal) : Set (E n) :=
  {x | f x ≠ ⊤ ∧ f x ≠ ⊥}

lemma mem_effectiveDom_iff {f : E n → EReal} {x : E n} :
    x ∈ effectiveDom f ↔ f x ≠ ⊤ ∧ f x ≠ ⊥ :=
  Iff.rfl

lemma EReal.coe_toReal_of_mem_effectiveDom {f : E n → EReal} {x : E n} (hx : x ∈ effectiveDom f) :
    ((f x).toReal : EReal) = f x :=
  EReal.coe_toReal hx.1 hx.2

/-- A function `f : E n → EReal` is proper if its effective domain is nonempty and it never
takes the value `⊥`. -/
def IsProper (f : E n → EReal) : Prop :=
  (∃ x, x ∈ effectiveDom f) ∧ ∀ x, f x ≠ ⊥

/-- Indicator function `ι_C` of a set `C ⊆ E n`, taking value `0` on `C` and `⊤` outside `C`. -/
noncomputable def indicatorE (C : Set (E n)) (x : E n) : EReal :=
  letI := Classical.propDecidable
  if x ∈ C then (0 : EReal) else ⊤

@[simp]
lemma indicatorE_of_mem {C : Set (E n)} {x : E n} (hx : x ∈ C) :
    indicatorE C x = (0 : EReal) := by
  classical
  exact if_pos hx

@[simp]
lemma indicatorE_of_notMem {C : Set (E n)} {x : E n} (hx : x ∉ C) :
    indicatorE C x = ⊤ := by
  classical
  exact if_neg hx

lemma effectiveDom_indicatorE (C : Set (E n)) : effectiveDom (indicatorE C) = C := by
  ext x
  by_cases hx : x ∈ C <;> simp [effectiveDom, hx]

lemma isProper_indicatorE {C : Set (E n)} (hC : C.Nonempty) : IsProper (indicatorE C) := by
  refine ⟨?_, ?_⟩
  · rcases hC with ⟨x, hx⟩
    exact ⟨x, by simp [effectiveDom, hx]⟩
  · intro x
    by_cases hx : x ∈ C <;> simp [hx]

/-- The Fréchet (regular) subdifferential `∂̂ f(x)`. -/
def frechetSubdiff (f : E n → EReal) (x : E n) : Set (E n) :=
  {v | x ∈ effectiveDom f ∧ ∀ ε > (0 : ℝ), ∃ δ > (0 : ℝ), ∀ y : E n,
    ‖y - x‖ < δ → (((f x).toReal + ⟪v, y - x⟫_ℝ - ε * ‖y - x‖ : ℝ) : EReal) ≤ f y}

/-- The limiting (Mordukhovich) subdifferential `∂ f(x)`. -/
def limitingSubdiff (f : E n → EReal) (x : E n) : Set (E n) :=
  {v | x ∈ effectiveDom f ∧ ∃ (xk vk : ℕ → E n),
    (∀ k, xk k ∈ effectiveDom f) ∧
    Tendsto xk atTop (𝓝 x) ∧
    Tendsto (fun k => (f (xk k)).toReal) atTop (𝓝 (f x).toReal) ∧
    (∀ k, vk k ∈ frechetSubdiff f (xk k)) ∧
    Tendsto vk atTop (𝓝 v)}

/-- Critical points `crit(f) = {x | 0 ∈ ∂ f(x)}`. -/
def crit (f : E n → EReal) : Set (E n) :=
  {x | (0 : E n) ∈ limitingSubdiff f x}

/-- Normal cone `N_C(x)` to a set `C ⊆ E n` at `x`. -/
def normalCone (C : Set (E n)) (x : E n) : Set (E n) :=
  {w | x ∈ C ∧ ∀ y ∈ C, ⟪w, y - x⟫_ℝ ≤ 0}

lemma frechetSubdiff_subset_limitingSubdiff (f : E n → EReal) (x : E n) :
    frechetSubdiff f x ⊆ limitingSubdiff f x := by
  intro v hv
  refine ⟨hv.1, fun _ => x, fun _ => v, fun _ => hv.1, tendsto_const_nhds,
    tendsto_const_nhds, fun _ => hv, tendsto_const_nhds⟩

lemma zero_mem_frechetSubdiff_of_isMin {f : E n → EReal} {x : E n}
    (hx : x ∈ effectiveDom f) (hmin : ∀ y, f x ≤ f y) :
    (0 : E n) ∈ frechetSubdiff f x := by
  refine ⟨hx, fun ε hε => ⟨1, one_pos, fun y _ => ?_⟩⟩
  have h1 : ((f x).toReal + ⟪(0 : E n), y - x⟫_ℝ - ε * ‖y - x‖ : ℝ) ≤ (f x).toReal := by
    rw [inner_zero_left, add_zero, sub_le_self_iff]
    exact mul_nonneg hε.le (norm_nonneg _)
  calc
    (((f x).toReal + ⟪(0 : E n), y - x⟫_ℝ - ε * ‖y - x‖ : ℝ) : EReal)
        ≤ ((f x).toReal : EReal) := EReal.coe_le_coe_iff.mpr h1
    _ = f x := EReal.coe_toReal_of_mem_effectiveDom hx
    _ ≤ f y := hmin y

lemma frechetSubdiff_congr_nhds {f₁ f₂ : E n → EReal} {x : E n} (h : f₁ =ᶠ[𝓝 x] f₂) :
    frechetSubdiff f₁ x = frechetSubdiff f₂ x := by
  have hx_eq : f₁ x = f₂ x := h.eq_of_nhds
  rcases Metric.eventually_nhds_iff.mp h with ⟨r, hr, hball⟩
  ext v
  constructor <;> rintro ⟨hx, hv⟩
  · refine ⟨?_, fun ε hε => ?_⟩
    · simpa [effectiveDom, hx_eq] using hx
    · rcases hv ε hε with ⟨δ, hδ, hle⟩
      refine ⟨min δ r, lt_min hδ hr, fun y hy => ?_⟩
      have hyδ : ‖y - x‖ < δ := lt_of_lt_of_le hy (min_le_left _ _)
      have hyr : dist y x < r := by
        simpa [dist_eq_norm] using lt_of_lt_of_le hy (min_le_right _ _)
      have hfy := hle y hyδ
      rwa [hx_eq, hball hyr] at hfy
  · refine ⟨?_, fun ε hε => ?_⟩
    · simpa [effectiveDom, hx_eq] using hx
    · rcases hv ε hε with ⟨δ, hδ, hle⟩
      refine ⟨min δ r, lt_min hδ hr, fun y hy => ?_⟩
      have hyδ : ‖y - x‖ < δ := lt_of_lt_of_le hy (min_le_left _ _)
      have hyr : dist y x < r := by
        simpa [dist_eq_norm] using lt_of_lt_of_le hy (min_le_right _ _)
      have hfy := hle y hyδ
      rwa [← hx_eq, ← hball hyr] at hfy

lemma limitingSubdiff_congr_nhds {f₁ f₂ : E n → EReal} {x : E n} (h : f₁ =ᶠ[𝓝 x] f₂) :
    limitingSubdiff f₁ x = limitingSubdiff f₂ x := by
  have hx_eq : f₁ x = f₂ x := h.eq_of_nhds
  rcases eventually_nhds_iff.mp h with ⟨U, hU_eq, hU_open, hxU⟩
  have sub_helper : ∀ {g₁ g₂ : E n → EReal},
      (∀ y ∈ U, g₁ y = g₂ y) → g₁ x = g₂ x →
      limitingSubdiff g₁ x ⊆ limitingSubdiff g₂ x := by
    intro g₁ g₂ hU hx_g v ⟨hx1, xk, vk, hdom, hxt, hft, hvk, hvt⟩
    have hev : ∀ᶠ k in atTop, xk k ∈ U := hxt.eventually (hU_open.mem_nhds hxU)
    rcases eventually_atTop.mp hev with ⟨K, hK⟩
    refine ⟨by simpa [effectiveDom, hx_g] using hx1,
      fun k => xk (k + K), fun k => vk (k + K), ?_, ?_, ?_, ?_, ?_⟩
    · intro k
      have hkU : xk (k + K) ∈ U := hK (k + K) (Nat.le_add_left K k)
      simpa [effectiveDom, hU _ hkU] using hdom (k + K)
    · exact hxt.comp (tendsto_add_atTop_nat K)
    · have hft_shift : Tendsto (fun k => (g₁ (xk (k + K))).toReal) atTop (𝓝 (g₁ x).toReal) :=
        hft.comp (tendsto_add_atTop_nat K)
      rw [← hx_g]
      refine hft_shift.congr' ?_
      filter_upwards with k
      have hkU : xk (k + K) ∈ U := hK (k + K) (Nat.le_add_left K k)
      rw [hU _ hkU]
    · intro k
      have hkU : xk (k + K) ∈ U := hK (k + K) (Nat.le_add_left K k)
      have hnhds : g₁ =ᶠ[𝓝 (xk (k + K))] g₂ :=
        eventually_nhds_iff.mpr ⟨U, hU, hU_open, hkU⟩
      rw [← frechetSubdiff_congr_nhds hnhds]
      exact hvk (k + K)
    · exact hvt.comp (tendsto_add_atTop_nat K)
  ext v
  exact ⟨fun hv => sub_helper hU_eq hx_eq hv, fun hv => sub_helper (fun y hy => (hU_eq y hy).symm) hx_eq.symm hv⟩

/-- Attentive closedness of the graph of the limiting subdifferential. -/
lemma limitingSubdiff_closed_attentive {f : E n → EReal} {x_bar ω_bar : E n}
    {xk ωk : ℕ → E n}
    (hx_bar_dom : x_bar ∈ effectiveDom f)
    (hxk_lim : Tendsto xk atTop (𝓝 x_bar))
    (hf_lim : Tendsto (fun k => (f (xk k)).toReal) atTop (𝓝 (f x_bar).toReal))
    (hωk : ∀ k, ωk k ∈ limitingSubdiff f (xk k))
    (hωk_lim : Tendsto ωk atTop (𝓝 ω_bar)) :
    ω_bar ∈ limitingSubdiff f x_bar := by
  have hdiag : ∀ k : ℕ, ∃ z u : E n,
      z ∈ effectiveDom f ∧
      ‖z - xk k‖ < 1 / ((k : ℝ) + 1) ∧
      |(f z).toReal - (f (xk k)).toReal| < 1 / ((k : ℝ) + 1) ∧
      u ∈ frechetSubdiff f z ∧
      ‖u - ωk k‖ < 1 / ((k : ℝ) + 1) := by
    intro k
    have hpos : (0 : ℝ) < 1 / ((k : ℝ) + 1) := by positivity
    rcases hωk k with ⟨_, zk, uk, hzk_dom, hzk_lim, hfzk_lim, huk_mem, huk_lim⟩
    have h1 : ∀ᶠ m in atTop, ‖zk m - xk k‖ < 1 / ((k : ℝ) + 1) := by
      simpa [dist_eq_norm] using Metric.tendsto_nhds.mp hzk_lim (1 / ((k : ℝ) + 1)) hpos
    have h2 : ∀ᶠ m in atTop, |(f (zk m)).toReal - (f (xk k)).toReal| < 1 / ((k : ℝ) + 1) := by
      simpa [Real.dist_eq] using Metric.tendsto_nhds.mp hfzk_lim (1 / ((k : ℝ) + 1)) hpos
    have h3 : ∀ᶠ m in atTop, ‖uk m - ωk k‖ < 1 / ((k : ℝ) + 1) := by
      simpa [dist_eq_norm] using Metric.tendsto_nhds.mp huk_lim (1 / ((k : ℝ) + 1)) hpos
    rcases (h1.and (h2.and h3)).exists with ⟨m, hm1, hm2, hm3⟩
    exact ⟨zk m, uk m, hzk_dom m, hm1, hm2, huk_mem m, hm3⟩
  choose zk uk hzk_dom hzk_near hfzk_near huk_mem huk_near using hdiag
  refine ⟨hx_bar_dom, zk, uk, hzk_dom, ?_, ?_, huk_mem, ?_⟩
  · rw [Metric.tendsto_nhds]
    intro ε hε
    have h_inv : ∀ᶠ k : ℕ in atTop, (1 / ((k : ℝ) + 1)) < ε / 2 := by
      have ht : Tendsto (fun k : ℕ => 1 / ((k : ℝ) + 1)) atTop (𝓝 0) :=
        tendsto_one_div_add_atTop_nhds_zero_nat
      exact ht.eventually (gt_mem_nhds (by positivity))
    have h_xk : ∀ᶠ k in atTop, dist (xk k) x_bar < ε / 2 :=
      (Metric.tendsto_nhds.mp hxk_lim) (ε / 2) (by positivity)
    filter_upwards [h_inv, h_xk] with k hk1 hk2
    calc
      dist (zk k) x_bar ≤ dist (zk k) (xk k) + dist (xk k) x_bar := dist_triangle _ _ _
      _ = ‖zk k - xk k‖ + dist (xk k) x_bar := by rw [dist_eq_norm]
      _ < ε := by linarith [hzk_near k]
  · rw [Metric.tendsto_nhds]
    intro ε hε
    have h_inv : ∀ᶠ k : ℕ in atTop, (1 / ((k : ℝ) + 1)) < ε / 2 := by
      have ht : Tendsto (fun k : ℕ => 1 / ((k : ℝ) + 1)) atTop (𝓝 0) :=
        tendsto_one_div_add_atTop_nhds_zero_nat
      exact ht.eventually (gt_mem_nhds (by positivity))
    have h_fk : ∀ᶠ k in atTop, dist ((f (xk k)).toReal) (f x_bar).toReal < ε / 2 :=
      (Metric.tendsto_nhds.mp hf_lim) (ε / 2) (by positivity)
    filter_upwards [h_inv, h_fk] with k hk1 hk2
    calc
      dist ((f (zk k)).toReal) (f x_bar).toReal
          ≤ dist ((f (zk k)).toReal) ((f (xk k)).toReal) + dist ((f (xk k)).toReal) (f x_bar).toReal :=
        dist_triangle _ _ _
      _ = |(f (zk k)).toReal - (f (xk k)).toReal| + dist ((f (xk k)).toReal) (f x_bar).toReal := by
        rw [Real.dist_eq]
      _ < ε := by linarith [hfzk_near k]
  · rw [Metric.tendsto_nhds]
    intro ε hε
    have h_inv : ∀ᶠ k : ℕ in atTop, (1 / ((k : ℝ) + 1)) < ε / 2 := by
      have ht : Tendsto (fun k : ℕ => 1 / ((k : ℝ) + 1)) atTop (𝓝 0) :=
        tendsto_one_div_add_atTop_nhds_zero_nat
      exact ht.eventually (gt_mem_nhds (by positivity))
    have h_ωk : ∀ᶠ k in atTop, dist (ωk k) ω_bar < ε / 2 :=
      (Metric.tendsto_nhds.mp hωk_lim) (ε / 2) (by positivity)
    filter_upwards [h_inv, h_ωk] with k hk1 hk2
    calc
      dist (uk k) ω_bar ≤ dist (uk k) (ωk k) + dist (ωk k) ω_bar := dist_triangle _ _ _
      _ = ‖uk k - ωk k‖ + dist (ωk k) ω_bar := by rw [dist_eq_norm]
      _ < ε := by linarith [huk_near k]

lemma frechetSubdiff_add_smooth_at {g : E n → ℝ} {h : E n → EReal} {x v : E n}
    (hg : DifferentiableAt ℝ g x) (hh_bot : ∀ y, h y ≠ ⊥) :
    v ∈ frechetSubdiff (fun y => (g y : EReal) + h y) x ↔
      v - gradient g x ∈ frechetSubdiff h x := by
  have hg_grad : HasGradientAt g (gradient g x) x := hg.hasGradientAt
  have hdom : ∀ y, y ∈ effectiveDom (fun z => (g z : EReal) + h z) ↔ y ∈ effectiveDom h := by
    intro y
    simp [effectiveDom, ereal_coe_add_eq_top_iff, EReal.add_eq_bot_iff, hh_bot y]
  have htoReal : ∀ {y}, y ∈ effectiveDom h →
      ((g y : EReal) + h y).toReal = g y + (h y).toReal := by
    intro y hy
    rw [← EReal.coe_toReal_of_mem_effectiveDom hy, ← EReal.coe_add]
    exact EReal.toReal_coe _
  constructor
  · rintro ⟨hx_dom, hv⟩
    have hx_h : x ∈ effectiveDom h := (hdom x).mp hx_dom
    refine ⟨hx_h, fun ε hε => ?_⟩
    rcases hv (ε / 2) (by positivity) with ⟨δ₁, hδ₁, hv_bound⟩
    have ho : (fun y => g y - g x - ⟪gradient g x, y - x⟫_ℝ) =o[𝓝 x] (fun y => y - x) :=
      hasGradientAt_iff_isLittleO.mp hg_grad
    rcases Metric.eventually_nhds_iff.mp (ho.bound (by positivity : (0 : ℝ) < ε / 2)) with
      ⟨δ₂, hδ₂, h_lin⟩
    refine ⟨min δ₁ δ₂, lt_min hδ₁ hδ₂, fun y hy => ?_⟩
    by_cases hy_top : h y = ⊤
    · simp [hy_top]
    have hy_dom : y ∈ effectiveDom h := ⟨hy_top, hh_bot y⟩
    have hy1 : ‖y - x‖ < δ₁ := lt_of_lt_of_le hy (min_le_left _ _)
    have hy2 : dist y x < δ₂ := by simpa [dist_eq_norm] using lt_of_lt_of_le hy (min_le_right _ _)
    have h_f := hv_bound y hy1
    dsimp only at h_f
    rw [htoReal hx_h, ← EReal.coe_toReal_of_mem_effectiveDom hy_dom, ← EReal.coe_add,
      EReal.coe_le_coe_iff] at h_f
    have h_g_abs : |g y - g x - ⟪gradient g x, y - x⟫_ℝ| ≤ (ε / 2) * ‖y - x‖ := by
      simpa [Real.norm_eq_abs] using h_lin hy2
    have h_g : g y - g x - ⟪gradient g x, y - x⟫_ℝ ≤ (ε / 2) * ‖y - x‖ :=
      (abs_le.mp h_g_abs).2
    have h_res : (h x).toReal + ⟪v - gradient g x, y - x⟫_ℝ - ε * ‖y - x‖ ≤ (h y).toReal := by
      rw [inner_sub_left]
      linarith
    rw [← EReal.coe_toReal_of_mem_effectiveDom hy_dom, EReal.coe_le_coe_iff]
    exact h_res
  · rintro ⟨hx_h, hv⟩
    refine ⟨(hdom x).mpr hx_h, fun ε hε => ?_⟩
    rcases hv (ε / 2) (by positivity) with ⟨δ₁, hδ₁, hv_bound⟩
    have ho : (fun y => g y - g x - ⟪gradient g x, y - x⟫_ℝ) =o[𝓝 x] (fun y => y - x) :=
      hasGradientAt_iff_isLittleO.mp hg_grad
    rcases Metric.eventually_nhds_iff.mp (ho.bound (by positivity : (0 : ℝ) < ε / 2)) with
      ⟨δ₂, hδ₂, h_lin⟩
    refine ⟨min δ₁ δ₂, lt_min hδ₁ hδ₂, fun y hy => ?_⟩
    by_cases hy_top : h y = ⊤
    · simp [hy_top]
    have hy_dom : y ∈ effectiveDom h := ⟨hy_top, hh_bot y⟩
    have hy1 : ‖y - x‖ < δ₁ := lt_of_lt_of_le hy (min_le_left _ _)
    have hy2 : dist y x < δ₂ := by simpa [dist_eq_norm] using lt_of_lt_of_le hy (min_le_right _ _)
    have h_sub := hv_bound y hy1
    rw [← EReal.coe_toReal_of_mem_effectiveDom hy_dom, EReal.coe_le_coe_iff] at h_sub
    have h_g_abs : |g y - g x - ⟪gradient g x, y - x⟫_ℝ| ≤ (ε / 2) * ‖y - x‖ := by
      simpa [Real.norm_eq_abs] using h_lin hy2
    have h_g : -(ε / 2) * ‖y - x‖ ≤ g y - g x - ⟪gradient g x, y - x⟫_ℝ := by
      linarith [(abs_le.mp h_g_abs).1]
    have h_res : ((g x : EReal) + h x).toReal + ⟪v, y - x⟫_ℝ - ε * ‖y - x‖ ≤ g y + (h y).toReal := by
      rw [htoReal hx_h]
      have hin : ⟪v, y - x⟫_ℝ = ⟪v - gradient g x, y - x⟫_ℝ + ⟪gradient g x, y - x⟫_ℝ := by
        rw [inner_sub_left]
        ring
      linarith
    dsimp only
    rw [← EReal.coe_toReal_of_mem_effectiveDom hy_dom, ← EReal.coe_add, EReal.coe_le_coe_iff]
    exact h_res

lemma limitingSubdiff_add_smooth_on_nhds {f h : E n → EReal} {g : E n → ℝ} {U : Set (E n)}
    {x v : E n} (hU : IsOpen U) (hxU : x ∈ U) (hg : ContDiffOn ℝ 1 g U)
    (hh : IsProper h) (hf : ∀ y ∈ U, f y = (g y : EReal) + h y) :
    v ∈ limitingSubdiff f x ↔ v - gradient g x ∈ limitingSubdiff h x := by
  have hcongr : f =ᶠ[𝓝 x] (fun y => (g y : EReal) + h y) :=
    eventually_nhds_iff.mpr ⟨U, hf, hU, hxU⟩
  rw [limitingSubdiff_congr_nhds hcongr]
  have hg_cont_grad : ContinuousOn (gradient g) U := by
    have hfd_cont : ContinuousOn (fderiv ℝ g) U := hg.continuousOn_fderiv_of_isOpen hU le_rfl
    have hdual : Continuous (InnerProductSpace.toDual ℝ (E n)).symm :=
      (InnerProductSpace.toDual ℝ (E n)).symm.continuous
    have hcomp : ContinuousOn (fun y => (InnerProductSpace.toDual ℝ (E n)).symm (fderiv ℝ g y)) U :=
      hdual.comp_continuousOn hfd_cont
    refine hcomp.congr fun y hy => ?_
    have hdiff : DifferentiableAt ℝ g y :=
      (hg.differentiableOn one_ne_zero y hy).differentiableAt (hU.mem_nhds hy)
    have hfd : fderiv ℝ g y = (InnerProductSpace.toDual ℝ (E n)) (gradient g y) :=
      (hasGradientAt_iff_hasFDerivAt.mp hdiff.hasGradientAt).fderiv
    rw [hfd, LinearIsometryEquiv.symm_apply_apply]
  have hdom : ∀ y, y ∈ effectiveDom (fun z => (g z : EReal) + h z) ↔ y ∈ effectiveDom h := by
    intro y
    simp [effectiveDom, ereal_coe_add_eq_top_iff, EReal.add_eq_bot_iff, hh.2 y]
  have htoReal : ∀ {y}, y ∈ effectiveDom h →
      ((g y : EReal) + h y).toReal = g y + (h y).toReal := by
    intro y hy
    rw [← EReal.coe_toReal_of_mem_effectiveDom hy, ← EReal.coe_add]
    exact EReal.toReal_coe _
  have hg_cont : ContinuousAt g x :=
    (hg.continuousOn.continuousAt (hU.mem_nhds hxU))
  constructor
  · rintro ⟨hx_dom, xk, vk, hxk_dom, hxt, hft, hvk, hvt⟩
    have hev : ∀ᶠ k in atTop, xk k ∈ U := hxt.eventually (hU.mem_nhds hxU)
    rcases eventually_atTop.mp hev with ⟨K, hK⟩
    have hx_h : x ∈ effectiveDom h := (hdom x).mp hx_dom
    refine ⟨hx_h, fun k => xk (k + K), fun k => vk (k + K) - gradient g (xk (k + K)),
      ?_, hxt.comp (tendsto_add_atTop_nat K), ?_, ?_, ?_⟩
    · intro k
      exact (hdom (xk (k + K))).mp (hxk_dom (k + K))
    · have hft' : Tendsto (fun k => ((g (xk (k + K)) : EReal) + h (xk (k + K))).toReal) atTop
          (𝓝 (g x + (h x).toReal)) := by
        simpa [htoReal hx_h] using hft.comp (tendsto_add_atTop_nat K)
      have hg_lim : Tendsto (fun k => g (xk (k + K))) atTop (𝓝 (g x)) :=
        hg_cont.tendsto.comp (hxt.comp (tendsto_add_atTop_nat K))
      have h_sub := hft'.sub hg_lim
      simp only [add_sub_cancel_left] at h_sub
      refine h_sub.congr' ?_
      filter_upwards with k
      have hk_dom : xk (k + K) ∈ effectiveDom h := (hdom (xk (k + K))).mp (hxk_dom (k + K))
      rw [htoReal hk_dom, add_sub_cancel_left]
    · intro k
      have hkU : xk (k + K) ∈ U := hK (k + K) (Nat.le_add_left K k)
      have hdiff : DifferentiableAt ℝ g (xk (k + K)) :=
        (hg.differentiableOn one_ne_zero _ hkU).differentiableAt (hU.mem_nhds hkU)
      exact (frechetSubdiff_add_smooth_at hdiff hh.2).mp (hvk (k + K))
    · have hgrad_lim : Tendsto (fun k => gradient g (xk (k + K))) atTop (𝓝 (gradient g x)) :=
        (hg_cont_grad.continuousAt (hU.mem_nhds hxU)).tendsto.comp
          (hxt.comp (tendsto_add_atTop_nat K))
      exact (hvt.comp (tendsto_add_atTop_nat K)).sub hgrad_lim
  · rintro ⟨hx_h, xk, uk, hxk_dom, hxt, hht, huk, hut⟩
    have hev : ∀ᶠ k in atTop, xk k ∈ U := hxt.eventually (hU.mem_nhds hxU)
    rcases eventually_atTop.mp hev with ⟨K, hK⟩
    refine ⟨(hdom x).mpr hx_h, fun k => xk (k + K), fun k => uk (k + K) + gradient g (xk (k + K)),
      ?_, hxt.comp (tendsto_add_atTop_nat K), ?_, ?_, ?_⟩
    · intro k
      exact (hdom (xk (k + K))).mpr (hxk_dom (k + K))
    · have hg_lim : Tendsto (fun k => g (xk (k + K))) atTop (𝓝 (g x)) :=
        hg_cont.tendsto.comp (hxt.comp (tendsto_add_atTop_nat K))
      have hsum := hg_lim.add (hht.comp (tendsto_add_atTop_nat K))
      rw [htoReal hx_h]
      refine hsum.congr' ?_
      filter_upwards with k
      exact (htoReal (hxk_dom (k + K))).symm
    · intro k
      have hkU : xk (k + K) ∈ U := hK (k + K) (Nat.le_add_left K k)
      have hdiff : DifferentiableAt ℝ g (xk (k + K)) :=
        (hg.differentiableOn one_ne_zero _ hkU).differentiableAt (hU.mem_nhds hkU)
      refine (frechetSubdiff_add_smooth_at hdiff hh.2).mpr ?_
      simpa [add_sub_cancel_right] using huk (k + K)
    · have hgrad_lim : Tendsto (fun k => gradient g (xk (k + K))) atTop (𝓝 (gradient g x)) :=
        (hg_cont_grad.continuousAt (hU.mem_nhds hxU)).tendsto.comp
          (hxt.comp (tendsto_add_atTop_nat K))
      simpa using (hut.comp (tendsto_add_atTop_nat K)).add hgrad_lim

lemma normalCone_subset_frechetSubdiff_indicator {C : Set (E n)} {x : E n} :
    normalCone C x ⊆ frechetSubdiff (indicatorE C) x := by
  rintro w ⟨hxC, hw⟩
  refine ⟨by simp [effectiveDom, hxC], fun ε hε => ⟨1, one_pos, fun y _ => ?_⟩⟩
  by_cases hyC : y ∈ C
  · simp only [indicatorE_of_mem hxC, indicatorE_of_mem hyC, EReal.toReal_zero, zero_add]
    rw [EReal.coe_nonpos]
    have h1 : ⟪w, y - x⟫_ℝ ≤ 0 := hw y hyC
    have h2 : 0 ≤ ε * ‖y - x‖ := mul_nonneg hε.le (norm_nonneg _)
    linarith
  · simp [indicatorE_of_notMem hyC]

lemma frechetSubdiff_indicator_subset_normalCone_of_convex {C : Set (E n)} (hC : Convex ℝ C)
    {x : E n} :
    frechetSubdiff (indicatorE C) x ⊆ normalCone C x := by
  rintro w ⟨hx_dom, hw⟩
  have hxC : x ∈ C := by simpa [effectiveDom_indicatorE] using hx_dom
  refine ⟨hxC, fun y hyC => ?_⟩
  by_contra! hpos
  have hyx_pos : 0 < ‖y - x‖ := by
    by_contra! hzero
    have hzero' : ‖y - x‖ = 0 := le_antisymm hzero (norm_nonneg _)
    rw [norm_eq_zero, sub_eq_zero] at hzero'
    subst hzero'
    simp at hpos
  set ε : ℝ := ⟪w, y - x⟫_ℝ / (2 * ‖y - x‖)
  have hε : 0 < ε := by positivity
  rcases hw ε hε with ⟨δ, hδ, hle⟩
  set t : ℝ := min 1 (δ / (2 * ‖y - x‖))
  have ht0 : 0 < t := lt_min one_pos (by positivity)
  have ht1 : t ≤ 1 := min_le_left _ _
  set z : E n := x + t • (y - x)
  have hzC : z ∈ C := by
    have hz_eq : z = (1 - t) • x + t • y := by
      simp [z, sub_smul, smul_sub]
      abel
    rw [hz_eq]
    exact hC hxC hyC (by linarith) ht0.le (by ring)
  have hzx : z - x = t • (y - x) := by simp [z]
  have hnorm_zx : ‖z - x‖ < δ := by
    rw [hzx, norm_smul, Real.norm_of_nonneg ht0.le]
    calc
      t * ‖y - x‖ ≤ (δ / (2 * ‖y - x‖)) * ‖y - x‖ :=
        mul_le_mul_of_nonneg_right (min_le_right _ _) (norm_nonneg _)
      _ = δ / 2 := by field_simp
      _ < δ := half_lt_self hδ
  have h_ind := hle z hnorm_zx
  simp only [indicatorE_of_mem hxC, indicatorE_of_mem hzC, EReal.toReal_zero, zero_add,
    EReal.coe_nonpos] at h_ind
  rw [hzx, inner_smul_right, norm_smul, Real.norm_of_nonneg ht0.le] at h_ind
  have hcalc : t * ⟪w, y - x⟫_ℝ - ε * (t * ‖y - x‖) = t * (⟪w, y - x⟫_ℝ / 2) := by
    dsimp [ε]
    field_simp
    ring
  rw [hcalc] at h_ind
  have : 0 < t * (⟪w, y - x⟫_ℝ / 2) := mul_pos ht0 (half_pos hpos)
  linarith

lemma frechetSubdiff_indicator_eq_normalCone_of_convex {C : Set (E n)} (hC : Convex ℝ C)
    {x : E n} :
    frechetSubdiff (indicatorE C) x = normalCone C x :=
  Set.Subset.antisymm (frechetSubdiff_indicator_subset_normalCone_of_convex hC)
    normalCone_subset_frechetSubdiff_indicator

lemma limitingSubdiff_indicator_eq_normalCone_of_closed_convex {C : Set (E n)}
    (_hC_closed : IsClosed C) (hC_conv : Convex ℝ C) {x : E n} :
    limitingSubdiff (indicatorE C) x = normalCone C x := by
  refine Set.Subset.antisymm ?_ ?_
  · rintro w ⟨hx_dom, xk, vk, hxk_dom, hxt, _, hvk, hvt⟩
    have hxC : x ∈ C := by simpa [effectiveDom_indicatorE] using hx_dom
    refine ⟨hxC, fun y hyC => ?_⟩
    have hle : ∀ k, ⟪vk k, y - xk k⟫_ℝ ≤ 0 := fun k =>
      (frechetSubdiff_indicator_subset_normalCone_of_convex hC_conv (hvk k)).2 y hyC
    have hlim : Tendsto (fun k => ⟪vk k, y - xk k⟫_ℝ) atTop (𝓝 ⟪w, y - x⟫_ℝ) :=
      hvt.inner (tendsto_const_nhds.sub hxt)
    exact le_of_tendsto hlim (Eventually.of_forall hle)
  · intro w hw
    exact frechetSubdiff_subset_limitingSubdiff _ _ (normalCone_subset_frechetSubdiff_indicator hw)

end ProperAndSubdiff

end DeqMdErratum
