AFTD Auto-Formalizing Theoretical Domains

prob_simplex_concaveOn_of_hasDerivAt2

theoremverified

A function on the open probability simplex {r : ∀x, 0 < r x, Σ r = 1} is concave if, at every point r of it and in every direction v with Σ v = 0, t ↦ F(r + t v) has derivative D1 r v at 0, t ↦ D1(r + t v) v has derivative D2 r v at 0, and D2 r v ≤ 0 (second-derivative test along segments).

Statement

theorem prob_simplex_concaveOn_of_hasDerivAt2 {X : Type*} [Fintype X] (Φ : (X → ℝ) → ℝ)
    (D1 D2 : (X → ℝ) → (X → ℝ) → ℝ)
    (h1 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →
      HasDerivAt (fun t : ℝ => Φ (r + t • v)) (D1 r v) 0)
    (h2 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →
      HasDerivAt (fun t : ℝ => D1 (r + t • v) v) (D2 r v) 0)
    (h3 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →
      D2 r v ≤ 0) :
    ConcaveOn ℝ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} Φ
Source
arXiv:2610.21231 (On the subadditivity of mutual f-information), Appendix B, proof of Lemma 4
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 2

The proof, explained

The proof establishes concavity of Φ on the open probability simplex by reducing it to single-variable concavity along line segments. For any two distributions a and b in the simplex, the displacement v = b - a has zero sum, so the entire segment connecting them stays within the open simplex. Using a chain-rule shift lemma, the restriction φ(t) = Φ(a + t • v) is shown to be twice differentiable on [0, 1] with second derivative D2(a + t • v, v) ≤ 0. The standard second-derivative test on [0, 1] then yields concavity of φ, which specializes at the endpoints to the concavity inequality for Φ.

  1. The open probability simplex S = {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} is convex.

    Given any two points a, b in the simplex and convex weights α, β ≥ 0 with α + β = 1, we verify the two defining conditions for α • a + β • b. For strict positivity at any coordinate x, if α > 0, the sum α a(x) + β b(x) is strictly positive by positivity reasoning; if α = 0, then β = 1 and the combination reduces to b(x) > 0. For the sum condition, linearity of summation distributes α • a + β • b into α ∑ a(x) + β ∑ b(x) = α · 1 + β · 1 = 1.

    lines 10–21

    uses Pi.add_apply, Pi.smul_apply, smul_eq_mul, Finset.sum_add_distrib, Finset.mul_sum

      have hS : Convex ℝ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by
        intro a ha b hb α β hα hβ hαβ
        refine ⟨fun x => ?_, ?_⟩
        · simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul]
          rcases hα.lt_or_eq with h | h
          · have := ha.1 x; have := hb.1 x; positivity
          · subst h
            have : β = 1 := by linarith
            subst this; simp [hb.1 x]
        · simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul, Finset.sum_add_distrib,
            ← Finset.mul_sum, ha.2, hb.2]
          linarith
  2. For any points a, b in the simplex, the direction v = b - a has coordinate sum 0, and the segment a + t • v lies in the simplex for all t ∈ [0, 1].

    To establish concavity of Φ on the simplex, it suffices to take arbitrary points a, b in the simplex and convex weights α, β ≥ 0 with α + β = 1, and show α Φ(a) + β Φ(b) ≤ Φ(α • a + β • b). Setting v = b - a, its coordinates sum to ∑ b(x) - ∑ a(x) = 1 - 1 = 0. For each t ∈ [0, 1], the point a + t • v rewrites as (1 - t) • a + t • b, which is a convex combination of a and b (since 0 ≤ 1 - t, 0 ≤ t, and (1 - t) + t = 1), hence lies in the simplex by its convexity.

    lines 22–31

    uses Finset.sum_sub_distrib

      refine ⟨hS, ?_⟩
      intro a ha b hb α β hα hβ hαβ
      set v : X → ℝ := b - a with hvdef
      have hv : ∑ x, v x = 0 := by simp [v, Finset.sum_sub_distrib, ha.2, hb.2]
      have hseg : ∀ t ∈ Set.Icc (0:ℝ) 1,
          a + t • v ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by
        intro t ht
        have : a + t • v = (1 - t) • a + t • b := by
          funext x; simp [v]; ring
        rw [this]; exact hS ha hb (by linarith [ht.2]) ht.1 (by ring)
  3. Directional derivatives along the segment can be translated from 0 to any parameter t.

    Define φ(t) = Φ(a + t • v) and ψ(t) = D1(a + t • v, v). A general shift lemma is proven: for any functional Gv, if s ↦ Gv((a + t • v) + s • v) has derivative d at s = 0, then s ↦ Gv(a + s • v) has derivative d at s = t. This follows from the chain rule applied to the composition with s ↦ s - t (which has derivative 1 at t), noting that (a + t • v) + (s - t) • v = a + s • v everywhere.

    lines 32–46

    uses sub_self, hasDerivAt_id', HasDerivAt.comp, mul_one, Filter.Eventually.of_forall, Function.comp, Pi.add_apply, Pi.smul_apply, smul_eq_mul

      set φ : ℝ → ℝ := fun t => Φ (a + t • v) with hφ
      set ψ : ℝ → ℝ := fun t => D1 (a + t • v) v with hψ
      have shift : ∀ (Gv : (X → ℝ) → ℝ) (d t : ℝ),
          HasDerivAt (fun s : ℝ => Gv ((a + t • v) + s • v)) d 0 →
          HasDerivAt (fun s : ℝ => Gv (a + s • v)) d t := by
        intro Gv d t h
        have hg : HasDerivAt (fun s : ℝ => Gv ((a + t • v) + s • v)) d (t - t) := by
          rw [sub_self]; exact h
        have hh : HasDerivAt (fun s : ℝ => s - t) 1 t := (hasDerivAt_id' t).sub_const t
        have := HasDerivAt.comp (h := fun s : ℝ => s - t) t hg hh
        rw [mul_one] at this
        refine this.congr_of_eventuallyEq (Filter.Eventually.of_forall fun s => ?_)
        simp only [Function.comp]
        congr 1
        funext x; simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul]; ring
  4. For each t ∈ [0, 1], φ has derivative ψ(t) at t, and ψ has derivative D2(a + t • v, v) at t.

    For any t ∈ [0, 1], the segment point a + t • v belongs to the simplex and v has sum 0. Applying hypothesis h1 at this base point gives that s ↦ Φ((a + t • v) + s • v) has derivative D1(a + t • v, v) = ψ(t) at s = 0, so the shift lemma implies that φ'(t) = ψ(t). Similarly, applying hypothesis h2 gives that s ↦ D1((a + t • v) + s • v, v) has derivative D2(a + t • v, v) at s = 0, so by the shift lemma, ψ'(t) = D2(a + t • v, v).

    lines 47–54

      have hd1 : ∀ t ∈ Set.Icc (0:ℝ) 1, HasDerivAt φ (ψ t) t := by
        intro t ht
        obtain ⟨hp, hs⟩ := hseg t ht
        exact shift Φ _ t (h1 _ hp hs v hv)
      have hd2 : ∀ t ∈ Set.Icc (0:ℝ) 1, HasDerivAt ψ (D2 (a + t • v) v) t := by
        intro t ht
        obtain ⟨hp, hs⟩ := hseg t ht
        exact shift (fun r => D1 r v) _ t (h2 _ hp hs v hv)
  5. The one-dimensional restriction φ is concave on the closed interval [0, 1].

    We apply the single-variable second-derivative test (`concaveOn_of_deriv2_nonpos`) on [0, 1], whose interior is (0, 1). The function φ is continuous on [0, 1] and differentiable on (0, 1) because it has derivative ψ(t) at every point in [0, 1]. Near any t ∈ (0, 1), the derivative deriv φ agrees with ψ on the open neighborhood (0, 1), so deriv φ is differentiable on (0, 1) with derivative D2(a + t • v, v). Finally, hypothesis h3 ensures D2(a + t • v, v) ≤ 0 everywhere on (0, 1) since each segment point is in the simplex and ∑ v(x) = 0.

    lines 55–74

    uses interior_Icc, concaveOn_of_deriv2_nonpos, convex_Icc, Set.Ioo_subset_Icc_self, Ioo_mem_nhds, Function.iterate_succ, Function.iterate_one, Function.comp

      have hint : interior (Set.Icc (0:ℝ) 1) = Set.Ioo 0 1 := interior_Icc
      have hcc : ConcaveOn ℝ (Set.Icc (0:ℝ) 1) φ := by
        refine concaveOn_of_deriv2_nonpos (convex_Icc 0 1)
          (fun t ht => (hd1 t ht).continuousAt.continuousWithinAt) ?_ ?_ ?_
        · rw [hint]; intro t ht
          exact (hd1 t (Set.Ioo_subset_Icc_self ht)).differentiableAt.differentiableWithinAt
        · rw [hint]; intro t ht
          have heq : deriv φ =ᶠ[nhds t] ψ := by
            filter_upwards [Ioo_mem_nhds ht.1 ht.2] with s hs
            exact (hd1 s (Set.Ioo_subset_Icc_self hs)).deriv
          exact ((hd2 t (Set.Ioo_subset_Icc_self ht)).congr_of_eventuallyEq
            heq).differentiableAt.differentiableWithinAt
        · rw [hint]; intro t ht
          have heq : deriv φ =ᶠ[nhds t] ψ := by
            filter_upwards [Ioo_mem_nhds ht.1 ht.2] with s hs
            exact (hd1 s (Set.Ioo_subset_Icc_self hs)).deriv
          rw [Function.iterate_succ, Function.iterate_one, Function.comp,
            ((hd2 t (Set.Ioo_subset_Icc_self ht)).congr_of_eventuallyEq heq).deriv]
          obtain ⟨hp, hs⟩ := hseg t (Set.Ioo_subset_Icc_self ht)
          exact h3 _ hp hs v hv
  6. The concavity inequality α Φ(a) + β Φ(b) ≤ Φ(α • a + β • b) holds.

    Evaluating the concavity of φ on [0, 1] at 0 and 1 with weights α and β gives α φ(0) + β φ(1) ≤ φ(α · 0 + β · 1) = φ(β). By definition of φ, φ(0) = Φ(a), φ(1) = Φ(a + v) = Φ(b), and φ(β) = Φ(a + β • v) = Φ(α • a + β • b) (using α = 1 - β). Substituting these equalities yields the concavity inequality for Φ.

    lines 75–81

    uses zero_smul, add_zero, one_smul, smul_eq_mul, mul_zero, mul_one, zero_add

      have := hcc.2 (x := 0) (y := 1) (by simp) (by simp) hα hβ hαβ
      simp only [φ, zero_smul, add_zero, one_smul, smul_eq_mul, mul_zero, mul_one, zero_add] at this
      have e1 : a + v = b := by funext x; simp [v]
      have e2 : a + β • v = α • a + β • b := by
        funext x; simp [v]; rw [show α = 1 - β by linarith]; ring
      rw [e1, e2] at this
      exact this
Pi.add_apply
Pointwise addition of functions: (f + g)(x) = f(x) + g(x).
Pi.smul_apply
Pointwise scalar multiplication of functions: (c • f)(x) = c • f(x).
smul_eq_mul
Scalar multiplication in ℝ coincides with standard real multiplication: a • b = a * b.
Finset.sum_add_distrib
Finite summation distributes over addition: ∑ (f(x) + g(x)) = ∑ f(x) + ∑ g(x).
Finset.mul_sum
Multiplication by a constant distributes over a finite sum: a * ∑ f(x) = ∑ (a * f(x)).
Finset.sum_sub_distrib
Finite summation distributes over subtraction: ∑ (f(x) - g(x)) = ∑ f(x) - ∑ g(x).
sub_self
Subtracting an element from itself yields zero: a - a = 0.
hasDerivAt_id'
The identity function x ↦ x has derivative 1 at every point.
HasDerivAt.comp
The chain rule for differentiation: if h has derivative h' at x and g has derivative g' at h(x), then g ∘ h has derivative g' * h' at x.
mul_one
Multiplication by one is the identity: a * 1 = a.
Filter.Eventually.of_forall
A property that holds everywhere holds eventually in any filter.
Function.comp
Function composition: (g ∘ f)(x) = g(f(x)).
interior_Icc
The interior of a closed interval [a, b] in ℝ is the open interval (a, b).
concaveOn_of_deriv2_nonpos
A continuous function on a convex set in ℝ that is twice differentiable on the interior with non-positive second derivative is concave.
convex_Icc
Any closed interval [a, b] in ℝ is a convex set.
Set.Ioo_subset_Icc_self
The open interval (a, b) is a subset of the closed interval [a, b].
Ioo_mem_nhds
If a < x < b, then the open interval (a, b) is an open neighborhood of x.
Function.iterate_succ
The (n+1)-th iterate of a function satisfies f^(n+1) = f^n ∘ f.
Function.iterate_one
The first iterate of a function is the function itself: f^1 = f.
zero_smul
Scaling any vector by the scalar zero yields zero: 0 • m = 0.
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
one_smul
Scaling an element by the scalar one leaves it unchanged: 1 • b = b.
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
zero_add
Adding zero on the left leaves an element unchanged: 0 + a = a.

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

theorem prob_simplex_concaveOn_of_hasDerivAt2 {X : Type*} [Fintype X] (Φ : (X → ℝ) → ℝ)    (D1 D2 : (X → ℝ) → (X → ℝ) → ℝ)    (h1 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →      HasDerivAt (fun t : ℝ => Φ (r + t • v)) (D1 r v) 0)    (h2 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →      HasDerivAt (fun t : ℝ => D1 (r + t • v) v) (D2 r v) 0)    (h3 : ∀ r : X → ℝ, (∀ x, 0 < r x) → ∑ x, r x = 1 → ∀ v : X → ℝ, ∑ x, v x = 0 →      D2 r v ≤ 0) :    ConcaveOn ℝ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} Φ := by  have hS : Convex ℝ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by    intro a ha b hb α β hα hβ hαβ    refine ⟨fun x => ?_, ?_⟩    · simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul]      rcases hα.lt_or_eq with h | h      · have := ha.1 x; have := hb.1 x; positivity      · subst h        have : β = 1 := by linarith        subst this; simp [hb.1 x]    · simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul, Finset.sum_add_distrib,        ← Finset.mul_sum, ha.2, hb.2]      linarith  refine ⟨hS, ?_⟩  intro a ha b hb α β hα hβ hαβ  set v : X → ℝ := b - a with hvdef  have hv : ∑ x, v x = 0 := by simp [v, Finset.sum_sub_distrib, ha.2, hb.2]  have hseg : ∀ t ∈ Set.Icc (0:ℝ) 1,      a + t • v ∈ {r : X → ℝ | (∀ x, 0 < r x) ∧ ∑ x, r x = 1} := by    intro t ht    have : a + t • v = (1 - t) • a + t • b := by      funext x; simp [v]; ring    rw [this]; exact hS ha hb (by linarith [ht.2]) ht.1 (by ring)  set φ : ℝ → ℝ := fun t => Φ (a + t • v) with hφ  set ψ : ℝ → ℝ := fun t => D1 (a + t • v) v with hψ  have shift : ∀ (Gv : (X → ℝ) → ℝ) (d t : ℝ),      HasDerivAt (fun s : ℝ => Gv ((a + t • v) + s • v)) d 0 →      HasDerivAt (fun s : ℝ => Gv (a + s • v)) d t := by    intro Gv d t h    have hg : HasDerivAt (fun s : ℝ => Gv ((a + t • v) + s • v)) d (t - t) := by      rw [sub_self]; exact h    have hh : HasDerivAt (fun s : ℝ => s - t) 1 t := (hasDerivAt_id' t).sub_const t    have := HasDerivAt.comp (h := fun s : ℝ => s - t) t hg hh    rw [mul_one] at this    refine this.congr_of_eventuallyEq (Filter.Eventually.of_forall fun s => ?_)    simp only [Function.comp]    congr 1    funext x; simp only [Pi.add_apply, Pi.smul_apply, smul_eq_mul]; ring  have hd1 : ∀ t ∈ Set.Icc (0:ℝ) 1, HasDerivAt φ (ψ t) t := by    intro t ht    obtain ⟨hp, hs⟩ := hseg t ht    exact shift Φ _ t (h1 _ hp hs v hv)  have hd2 : ∀ t ∈ Set.Icc (0:ℝ) 1, HasDerivAt ψ (D2 (a + t • v) v) t := by    intro t ht    obtain ⟨hp, hs⟩ := hseg t ht    exact shift (fun r => D1 r v) _ t (h2 _ hp hs v hv)  have hint : interior (Set.Icc (0:ℝ) 1) = Set.Ioo 0 1 := interior_Icc  have hcc : ConcaveOn ℝ (Set.Icc (0:ℝ) 1) φ := by    refine concaveOn_of_deriv2_nonpos (convex_Icc 0 1)      (fun t ht => (hd1 t ht).continuousAt.continuousWithinAt) ?_ ?_ ?_    · rw [hint]; intro t ht      exact (hd1 t (Set.Ioo_subset_Icc_self ht)).differentiableAt.differentiableWithinAt    · rw [hint]; intro t ht      have heq : deriv φ =ᶠ[nhds t] ψ := by        filter_upwards [Ioo_mem_nhds ht.1 ht.2] with s hs        exact (hd1 s (Set.Ioo_subset_Icc_self hs)).deriv      exact ((hd2 t (Set.Ioo_subset_Icc_self ht)).congr_of_eventuallyEq        heq).differentiableAt.differentiableWithinAt    · rw [hint]; intro t ht      have heq : deriv φ =ᶠ[nhds t] ψ := by        filter_upwards [Ioo_mem_nhds ht.1 ht.2] with s hs        exact (hd1 s (Set.Ioo_subset_Icc_self hs)).deriv      rw [Function.iterate_succ, Function.iterate_one, Function.comp,        ((hd2 t (Set.Ioo_subset_Icc_self ht)).congr_of_eventuallyEq heq).deriv]      obtain ⟨hp, hs⟩ := hseg t (Set.Ioo_subset_Icc_self ht)      exact h3 _ hp hs v hv  have := hcc.2 (x := 0) (y := 1) (by simp) (by simp) hα hβ hαβ  simp only [φ, zero_smul, add_zero, one_smul, smul_eq_mul, mul_zero, mul_one, zero_add] at this  have e1 : a + v = b := by funext x; simp [v]  have e2 : a + β • v = α • a + β • b := by    funext x; simp [v]; rw [show α = 1 - β by linarith]; ring  rw [e1, e2] at this  exact this
See it in the graphDiscuss this resultChallenge it