/-- **Jensen's lemma on `ℝⁿ`** [CIL92, Lemma A.3], in the form of the
*Superposition* formalization. -/
theorem jensen_positive_measure {n : ℕ} (W : EuclSpace n → ℝ) (C : ℝ)
(hC : 0 ≤ C) (hconv : ConvexOn ℝ Set.univ (fun x => W x + C / 2 * ‖x‖ ^ 2))
(x₀ xs : EuclSpace n) (r δ : ℝ) (hr : 0 < r) (hδ : 0 < δ)
(hxs : xs ∈ closedBall x₀ r)
(hsphere : ∀ y, ‖y - x₀‖ = r → W y + 2 * δ * r < W xs) :
0 < volume {x | x ∈ ball x₀ r ∧ ∃ p : EuclSpace n, ‖p‖ ≤ δ ∧
∀ y ∈ closedBall x₀ r, W y + inner ℝ p y ≤ W x + inner ℝ p x} := by
set K := {x | x ∈ ball x₀ r ∧ ∃ p : EuclSpace n, ‖p‖ ≤ δ ∧
∀ y ∈ closedBall x₀ r, W y + inner ℝ p y ≤ W x + inner ℝ p x} with hKdef
-- Step 1: continuity
have hΦc : Continuous (fun x => W x + C / 2 * ‖x‖ ^ 2) := hconv.locallyLipschitz.continuous
have hWc : Continuous W := by
have := hΦc.sub ((continuous_const.mul (continuous_norm.pow 2)) :
Continuous (fun x : EuclSpace n => C / 2 * ‖x‖ ^ 2))
convert this using 1
funext x
simp
-- subgradients of Φ and the map g
have hsub := fun x => subgrad_exists hconv x
choose Q hQ0 using hsub
have hQ : ∀ x z, W x + C / 2 * ‖x‖ ^ 2 + inner ℝ (Q x) (z - x) ≤ W z + C / 2 * ‖z‖ ^ 2 :=
fun x z => hQ0 x z
let g : EuclSpace n → EuclSpace n := fun x => C • x - Q x
-- Step 3: uniqueness of the witness
have huniq : ∀ x ∈ ball x₀ r, ∀ p : EuclSpace n,
(∀ y ∈ closedBall x₀ r, W y + inner ℝ p y ≤ W x + inner ℝ p x) → p = g x := by
intro x hx p hp
set v := Q x - (C • x - p) with hv
have hxr : ‖x - x₀‖ < r := by rw [mem_ball, dist_eq_norm] at hx; exact hx
set t : ℝ := min (1 / (2 * (C + 1))) ((r - ‖x - x₀‖) / (‖v‖ + 1)) with ht
have ht0 : 0 < t := lt_min (by positivity) (div_pos (by linarith) (by positivity))
have ht1 : t ≤ 1 / (2 * (C + 1)) := min_le_left _ _
have ht2 : t ≤ (r - ‖x - x₀‖) / (‖v‖ + 1) := min_le_right _ _
have hyB : x + t • v ∈ closedBall x₀ r := by
rw [mem_closedBall, dist_eq_norm]
have e : x + t • v - x₀ = (x - x₀) + t • v := by abel
rw [e]
refine (norm_add_le _ _).trans ?_
rw [norm_smul, Real.norm_eq_abs, abs_of_pos ht0]
have h1 : t * (‖v‖ + 1) ≤ r - ‖x - x₀‖ := (le_div_iff₀ (by positivity)).mp ht2
nlinarith [norm_nonneg v]
have hup := hp _ hyB
have hlow := hQ x (x + t • v)
simp only [add_sub_cancel_left] at hlow
have hn : ‖x + t • v‖ ^ 2 = ‖x‖ ^ 2 + 2 * (t * inner ℝ x v) + t ^ 2 * ‖v‖ ^ 2 := by
rw [norm_add_sq_real, norm_smul, real_inner_smul_right, mul_pow, Real.norm_eq_abs, sq_abs]
rw [hn, real_inner_smul_right] at hlow
rw [inner_add_right, real_inner_smul_right] at hup
have hvv : ‖v‖ ^ 2 = inner ℝ (Q x) v - C * inner ℝ x v + inner ℝ p v := by
rw [← real_inner_self_eq_norm_sq]
conv_lhs => rw [hv]
rw [inner_sub_left, inner_sub_left, real_inner_smul_left]
ring
have hCt : C * t ≤ 1 / 2 := by
have : t * (2 * (C + 1)) ≤ 1 := (le_div_iff₀ (by positivity)).mp ht1
nlinarith
have htv := congrArg (fun z => t * z) hvv
have key : t * (‖v‖ ^ 2 - C / 2 * t * ‖v‖ ^ 2) ≤ 0 := by
have : t * (‖v‖ ^ 2 - C / 2 * t * ‖v‖ ^ 2)
= t * ‖v‖ ^ 2 - C / 2 * (t ^ 2 * ‖v‖ ^ 2) := by ring
rw [this]
nlinarith
have k2 : ‖v‖ ^ 2 - C / 2 * t * ‖v‖ ^ 2 ≤ 0 := by
by_contra hk
push Not at hk
linarith [mul_pos ht0 hk]
have k3 := mul_le_mul_of_nonneg_right hCt (sq_nonneg ‖v‖)
have hv0 : ‖v‖ ^ 2 ≤ 0 := by nlinarith [sq_nonneg ‖v‖]
have : v = 0 := by
have := pow_eq_zero_iff (n := 2) (two_ne_zero) |>.mp (le_antisymm hv0 (sq_nonneg _))
exact norm_eq_zero.mp this
rw [hv] at this
simp only [g]
rw [sub_eq_zero] at this
rw [this]; abel
-- Step 2: every small p is attained
have hattain : ∀ p : EuclSpace n, ‖p‖ ≤ δ → ∃ x ∈ K, g x = p := by
intro p hp
have hcont : ContinuousOn (fun x => W x + inner ℝ p x) (closedBall x₀ r) :=
(hWc.add (continuous_const.inner continuous_id)).continuousOn
obtain ⟨xp, hxpB, hxpmax⟩ := (isCompact_closedBall x₀ r).exists_isMaxOn
⟨x₀, mem_closedBall_self hr.le⟩ hcont
have hmax : ∀ y ∈ closedBall x₀ r, W y + inner ℝ p y ≤ W xp + inner ℝ p xp :=
fun y hy => hxpmax hy
have hxpin : xp ∈ ball x₀ r := by
rw [mem_ball, dist_eq_norm]
rw [mem_closedBall, dist_eq_norm] at hxpB
rcases hxpB.lt_or_eq with h | h
· exact h
· exfalso
have h1 := hsphere xp h
have h2 := hmax xs hxs
rw [mem_closedBall, dist_eq_norm] at hxs
have c1 : |inner ℝ p (xp - x₀)| ≤ δ * r := by
refine (abs_real_inner_le_norm _ _).trans ?_
rw [h]; exact mul_le_mul_of_nonneg_right hp hr.le
have c2 : |inner ℝ p (xs - x₀)| ≤ δ * r :=
(abs_real_inner_le_norm _ _).trans (mul_le_mul hp hxs (norm_nonneg _) hδ.le)
rw [inner_sub_right] at c1 c2
have := (abs_le.mp c1).2
have := (abs_le.mp c2).1
linarith
refine ⟨xp, ⟨hxpin, p, hp, hmax⟩, (huniq xp hxpin p hmax).symm⟩
-- (U): upper quadratic bound at points of K
have hU : ∀ x ∈ K, ∀ y ∈ closedBall x₀ r,
W y + C / 2 * ‖y‖ ^ 2 ≤ W x + C / 2 * ‖x‖ ^ 2 + inner ℝ (Q x) (y - x)
+ C / 2 * ‖y - x‖ ^ 2 := by
intro x hx y hy
obtain ⟨hxb, p, -, hwit⟩ := hx
have hpg := huniq x hxb p hwit
have h1 := hwit y hy
rw [hpg] at h1
have e1 : inner ℝ (g x) y - inner ℝ (g x) x
= C * inner ℝ x (y - x) - inner ℝ (Q x) (y - x) := by
rw [← inner_sub_right]
simp only [g]
rw [inner_sub_left, real_inner_smul_left]
have e2 : ‖y‖ ^ 2 = ‖x‖ ^ 2 + 2 * inner ℝ x (y - x) + ‖y - x‖ ^ 2 := by
have : y = x + (y - x) := by abel
conv_lhs => rw [this]
rw [norm_add_sq_real]
rw [e2]
nlinarith
-- Step 4: local Lipschitz bound for g on K
have hlip4 : ∀ θ > 0, ∀ x1 ∈ K, ∀ x2 ∈ K, ‖x1 - x₀‖ ≤ r - θ → ‖x2 - x₀‖ ≤ r - θ →
‖x1 - x2‖ ≤ θ / 2 → ‖g x1 - g x2‖ ≤ 3 * C * ‖x1 - x2‖ := by
intro θ hθ x1 hx1 x2 hx2 h1 h2 hd
set dd := ‖x1 - x2‖ with hddef
set Δ := Q x2 - Q x1 with hΔ
have hg : g x1 - g x2 = C • (x1 - x2) + Δ := by
simp only [g, hΔ, smul_sub]; abel
have hΔb : ‖Δ‖ ≤ 2 * C * dd := by
rcases eq_or_ne Δ 0 with h0 | h0
· rw [h0, norm_zero]; positivity
have hΔpos : 0 < ‖Δ‖ := norm_pos_iff.mpr h0
have hdpos : 0 < dd := by
rcases (norm_nonneg (x1 - x2)).eq_or_lt with h | h
· exfalso
have : x1 = x2 := sub_eq_zero.mp (norm_eq_zero.mp h.symm)
exact h0 (by rw [hΔ, this, sub_self])
· exact h
set t := 2 * dd with htdef
set u := (t / ‖Δ‖) • Δ with hu
have hun : ‖u‖ = t := by
rw [hu, norm_smul, Real.norm_eq_abs, abs_of_nonneg (by positivity)]
field_simp
have hyB : x1 + u ∈ closedBall x₀ r := by
rw [mem_closedBall, dist_eq_norm]
have : x1 + u - x₀ = (x1 - x₀) + u := by abel
rw [this]
refine (norm_add_le _ _).trans ?_
rw [hun]; linarith
have L2 := hQ x2 (x1 + u)
have U1 := hU x1 hx1 (x1 + u) hyB
have L1 := hQ x1 x2
have e1 : x1 + u - x2 = u + (x1 - x2) := by abel
have e2 : x1 + u - x1 = u := by abel
have e3 : x2 - x1 = -(x1 - x2) := by abel
rw [e1, inner_add_right] at L2
rw [e2, hun] at U1
rw [e3, inner_neg_right] at L1
have hΔu : inner ℝ (Q x2) u - inner ℝ (Q x1) u = t * ‖Δ‖ := by
rw [← inner_sub_left, ← hΔ, hu, real_inner_smul_right, real_inner_self_eq_norm_sq]
field_simp
have hΔx : -(‖Δ‖ * dd) ≤ inner ℝ (Q x2) (x1 - x2) - inner ℝ (Q x1) (x1 - x2) := by
rw [← inner_sub_left, ← hΔ]
exact neg_le_of_abs_le (abs_real_inner_le_norm _ _)
have key : dd * ‖Δ‖ ≤ dd * (2 * C * dd) := by
rw [htdef] at hΔu U1
nlinarith
exact le_of_mul_le_mul_left key hdpos
rw [hg]
refine (norm_add_le _ _).trans ?_
rw [norm_smul, Real.norm_eq_abs, abs_of_nonneg hC]
linarith
-- Step 5: conclusion
rw [pos_iff_ne_zero]
intro hK0
obtain ⟨c, hc⟩ := TopologicalSpace.exists_dense_seq (EuclSpace n)
let T : ℕ → ℕ → Set (EuclSpace n) := fun m j =>
K ∩ closedBall x₀ (r - 1 / ((m : ℝ) + 1)) ∩ closedBall (c j) (1 / (4 * ((m : ℝ) + 1)))
have hTK : ∀ m j, T m j ⊆ K := fun m j x hx => hx.1.1
have hTlip : ∀ m j, LipschitzOnWith (⟨3 * C, by positivity⟩ : NNReal) g (T m j) := by
intro m j
refine LipschitzOnWith.of_dist_le_mul fun x1 hx1 x2 hx2 => ?_
rw [dist_eq_norm, dist_eq_norm]
change ‖g x1 - g x2‖ ≤ 3 * C * ‖x1 - x2‖
have hm : (0 : ℝ) < 1 / ((m : ℝ) + 1) := by positivity
refine hlip4 (1 / ((m : ℝ) + 1)) hm x1 hx1.1.1 x2 hx2.1.1 ?_ ?_ ?_
· have := hx1.1.2; rwa [mem_closedBall, dist_eq_norm] at this
· have := hx2.1.2; rwa [mem_closedBall, dist_eq_norm] at this
· have a1 := hx1.2; have a2 := hx2.2
rw [mem_closedBall, dist_eq_norm] at a1 a2
have : x1 - x2 = (x1 - c j) - (x2 - c j) := by abel
rw [this]
refine (norm_sub_le _ _).trans ?_
have e : 1 / ((m : ℝ) + 1) / 2
= 1 / (4 * ((m : ℝ) + 1)) + 1 / (4 * ((m : ℝ) + 1)) := by
field_simp; ring
rw [e]; linarith
have hcover : K ⊆ ⋃ m, ⋃ j, T m j := by
intro x hx
have hxr : dist x x₀ < r := hx.1
obtain ⟨m, hm⟩ := exists_nat_one_div_lt (sub_pos.mpr hxr)
have hpos : (0 : ℝ) < 1 / (4 * ((m : ℝ) + 1)) := by positivity
obtain ⟨j, hj⟩ := hc.exists_dist_lt x hpos
refine mem_iUnion.mpr ⟨m, mem_iUnion.mpr ⟨j, ⟨hx, ?_⟩, ?_⟩⟩
· rw [mem_closedBall]; linarith
· rw [mem_closedBall]; exact hj.le
have hgK : volume (g '' K) = 0 := by
have hsubset : g '' K ⊆ ⋃ m, ⋃ j, g '' T m j := by
rintro _ ⟨x, hx, rfl⟩
obtain ⟨m, hm⟩ := mem_iUnion.mp (hcover hx)
obtain ⟨j, hj⟩ := mem_iUnion.mp hm
exact mem_iUnion.mpr ⟨m, mem_iUnion.mpr ⟨j, x, hj, rfl⟩⟩
refine measure_mono_null hsubset
(measure_iUnion_null fun m => measure_iUnion_null fun j => ?_)
exact lipschitzOn_image_null (hTlip m j) (measure_mono_null (hTK m j) hK0)
have hball : closedBall (0 : EuclSpace n) δ ⊆ g '' K := by
intro p hp
rw [mem_closedBall, dist_zero_right] at hp
obtain ⟨x, hxK, hgx⟩ := hattain p hp
exact ⟨x, hxK, hgx⟩
have := measure_mono_null hball hgK
exact (Metric.measure_closedBall_pos volume (0 : EuclSpace n) hδ).ne' this
/-- **Jensen's lemma on the product.** -/
theorem jensen : JensenLemma d := by
intro w lam hconv zh r hr hstrict δ hδ
have hH : (volume : Measure (EuclSpace d × EuclSpace d)).IsAddHaarMeasure := by
rw [Measure.volume_eq_prod]; infer_instance
set Φ := Φsplit d with hΦdef
set C := max lam 0 with hCdef
have hC0 : 0 ≤ C := le_max_right _ _
have hCl : 0 ≤ C - lam := sub_nonneg.2 (le_max_left _ _)
set vh := Φ.symm zh with hvh
have hΦvh : Φ vh = zh := Φ.apply_symm_apply zh
set W : EuclideanSpace ℝ (Fin (d + d)) → ℝ := fun v => w (Φ v) with hWdef
-- semiconvexity of W
have hconvW : ConvexOn ℝ univ (fun v => W v + C / 2 * ‖v‖ ^ 2) := by
refine ⟨convex_univ, fun a _ b _ s t hs ht hst => ?_⟩
have h1 := hconv.2 (mem_univ (Φ a)) (mem_univ (Φ b)) hs ht hst
simp only [smul_eq_mul] at h1 ⊢
have hΦ : Φ (s • a + t • b) = s • Φ a + t • Φ b := by
rw [map_add, map_smul, map_smul]
have hn1 := Φsplit_norm_sq (s • a + t • b)
have hna := Φsplit_norm_sq a
have hnb := Φsplit_norm_sq b
rw [← hΦdef, hΦ] at hn1
rw [← hΦdef] at hna hnb
rw [← hn1, ← hna, ← hnb] at h1
have hsq := norm_sq_convex_comb hst a b
have hab : 0 ≤ s * t * ‖a - b‖ ^ 2 := by positivity
have hconvsq : ‖s • a + t • b‖ ^ 2 ≤ s * ‖a‖ ^ 2 + t * ‖b‖ ^ 2 := by linarith
have h2 := mul_le_mul_of_nonneg_left hconvsq hCl
simp only [hWdef]
rw [hΦ]
nlinarith
have hWc : Continuous W := by
have h1 := convex_continuous hconvW
have h2 : Continuous (fun v : EuclideanSpace ℝ (Fin (d + d)) => C / 2 * ‖v‖ ^ 2) := by
fun_prop
convert h1.sub h2 using 1
funext v
simp
-- the strict maximum on the Euclidean ball
have hstrE : ∀ v ∈ closedBall vh r, v ≠ vh → W v < W vh := by
intro v hv hne
have hz : Φ v ∈ closedBall zh r := by
rw [mem_closedBall, dist_eq_norm, ← hΦvh, ← map_sub]
rw [mem_closedBall, dist_eq_norm] at hv
exact (Φsplit_norm_le _).trans hv
have hne' : Φ v ≠ zh := by
intro h; apply hne
rw [← hΦvh] at h
exact Φ.injective h
have := hstrict (Φ v) hz hne'
simp only [hWdef, hΦvh]
exact this
-- the gap on the sphere
obtain ⟨γ, hγ, hgap⟩ : ∃ γ > 0, ∀ y ∈ sphere vh r, W y ≤ W vh - γ := by
by_cases hS : (sphere vh r).Nonempty
· obtain ⟨y₀, hy₀, hmax⟩ := (isCompact_sphere vh r).exists_isMaxOn hS hWc.continuousOn
have hy₀b : y₀ ∈ closedBall vh r := sphere_subset_closedBall hy₀
have hy₀ne : y₀ ≠ vh := by
intro h
rw [h, mem_sphere, dist_self] at hy₀
linarith
have hlt := hstrE y₀ hy₀b hy₀ne
exact ⟨W vh - W y₀, by linarith, fun y hy => by have h' : W y ≤ W y₀ := hmax hy; linarith⟩
· refine ⟨1, one_pos, fun y hy => ?_⟩
exact absurd ⟨y, hy⟩ hS
set δ' := min δ (γ / (4 * r)) with hδ'def
have hδ' : 0 < δ' := lt_min hδ (by positivity)
have hδ'δ : δ' ≤ δ := min_le_left _ _
have hsphere : ∀ y, ‖y - vh‖ = r → W y + 2 * δ' * r < W vh := by
intro y hy
have h1 := hgap y (by rw [mem_sphere, dist_eq_norm]; exact hy)
have h2 : δ' ≤ γ / (4 * r) := min_le_right _ _
have h3 : 2 * δ' * r ≤ γ / 2 := by
have := mul_le_mul_of_nonneg_right h2 (by positivity : (0:ℝ) ≤ 2 * r)
have e : γ / (4 * r) * (2 * r) = γ / 2 := by field_simp; ring
nlinarith
linarith
-- Jensen's lemma on ℝ^{d+d}
have hpos := jensen_positive_measure W C hC0 hconvW vh vh r δ' hr hδ'
(mem_closedBall_self hr.le) hsphere
set KE := {x | x ∈ ball vh r ∧ ∃ p : EuclSpace (d + d), ‖p‖ ≤ δ' ∧
∀ y ∈ closedBall vh r, W y + inner ℝ p y ≤ W x + inner ℝ p x} with hKE
-- Φ maps it into the product Jensen set
have hsub : Φ '' KE ⊆ {z ∈ ball zh r | ∃ p₁ p₂ : EuclSpace d, ‖p₁‖ ≤ δ ∧ ‖p₂‖ ≤ δ ∧
IsLocalMax (fun z' => w z' + inner ℝ p₁ z'.1 + inner ℝ p₂ z'.2) z} := by
rintro _ ⟨v, ⟨hvb, p, hp, hmaxv⟩, rfl⟩
refine ⟨?_, (Φ p).1, (Φ p).2, ?_, ?_, ?_⟩
· rw [mem_ball, dist_eq_norm, ← hΦvh, ← map_sub]
rw [mem_ball, dist_eq_norm] at hvb
exact lt_of_le_of_lt (Φsplit_norm_le _) hvb
· exact ((Φsplit_fst_le p).trans hp).trans hδ'δ
· exact ((Φsplit_snd_le p).trans hp).trans hδ'δ
· unfold IsLocalMax IsMaxFilter
have hnb : Φ.symm ⁻¹' (ball vh r) ∈ 𝓝 (Φ v) := by
apply Φ.symm.continuous.continuousAt.preimage_mem_nhds
rw [Φ.symm_apply_apply]
exact isOpen_ball.mem_nhds hvb
filter_upwards [hnb] with z' hz'
have hz'b : Φ.symm z' ∈ closedBall vh r := ball_subset_closedBall hz'
have h1 := hmaxv (Φ.symm z') hz'b
simp only [hWdef, Φ.apply_symm_apply] at h1
rw [Φsplit_inner p (Φ.symm z'), Φsplit_inner p v] at h1
rw [← hΦdef, Φ.apply_symm_apply] at h1
change w z' + inner ℝ (Φ p).1 z'.1 + inner ℝ (Φ p).2 z'.2
≤ w (Φ v) + inner ℝ (Φ p).1 (Φ v).1 + inner ℝ (Φ p).2 (Φ v).2
linarith
-- positive measure transfers
refine lt_of_lt_of_le ?_ (measure_mono hsub)
rw [pos_iff_ne_zero]
intro h0
have h1 := null_image_cle volume volume Φ.symm h0
have e : Φ.symm '' (Φ '' KE) = KE := by
rw [Set.image_image]; simp
rw [e] at h1
exact (ne_of_gt hpos) h1