AFTD Auto-Formalizing Theoretical Domains

concave_on_ioi_exists_supergradient_at_one

theoremverified

A function K concave on (0, ∞) has a supergradient at 1: there is ℓ with K(x) ≤ K(1) + ℓ (x - 1) for all x > 0 (the first-order inequality K_s(x) ≤ K_s(1) + K_s'(1)(x - 1) of Appendix C, with a one-sided derivative in place of K_s'(1)).

Statement

theorem concave_on_ioi_exists_supergradient_at_one {K : ℝ → ℝ}
    (hK : ConcaveOn ℝ (Set.Ioi (0 : ℝ)) K) :
    ∃ ℓ : ℝ, ∀ x > 0, K x ≤ K 1 + ℓ * (x - 1)
Source
helper for arXiv:2610.21231 (On the subadditivity of mutual f-information), Corollary 1 (Appendix C, first-order inequality for the concave K_s)
Verified
23 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof negates the concave function $K$ to obtain a convex function $F(x) = -K(x)$ on $(0, \infty)$, noting that $1$ belongs to the interior of this domain. Choosing the candidate supergradient slope $\ell = -F'_+(1)$ (the negative of the right derivative of $F$ at $1$), the bound $K(x) \le K(1) + \ell(x - 1)$ translates into the standard subgradient property of $F$. The inequality is then verified across three cases: for $x < 1$, the secant slope is bounded by the left derivative, which is in turn bounded by the right derivative; for $x = 1$, it holds with equality; and for $x > 1$, the right derivative is bounded by the secant slope.

  1. The negated function $F(x) = -K(x)$ is convex on $(0, \infty)$, and $1$ lies in the interior of $(0, \infty)$.

    Because $K$ is concave on $(0, \infty)$, its negation $F = -K$ is convex on $(0, \infty)$ by `hK.neg`. Furthermore, $(0, \infty)$ is an open set, so it equals its own interior by `interior_Ioi`; since $1 > 0$, we have $1 \in \mathrm{interior}(0, \infty)$.

    lines 4–6

    uses interior_Ioi

      have hF : ConvexOn ℝ (Set.Ioi (0 : ℝ)) (fun x => -K x) := hK.neg
      have h1 : (1 : ℝ) ∈ interior (Set.Ioi (0 : ℝ)) := by
        rw [interior_Ioi]; norm_num
  2. Choosing the candidate slope $\ell = -F'_+(1)$, the goal reduces to showing $K(x) \le K(1) + \ell(x - 1)$ for all $x > 0$, split into three cases: $x < 1$, $x = 1$, and $x > 1$.

    We instantiate the existential witness with $\ell = -\mathrm{derivWithin}(F, (1, \infty), 1)$, representing the negated right derivative $-F'_+(1)$. We introduce an arbitrary $x > 0$ and apply `lt_trichotomy` to partition into cases according to whether $x < 1$, $x = 1$, or $x > 1$.

    lines 7–8

    uses lt_trichotomy

      refine ⟨-derivWithin (fun x => -K x) (Set.Ioi 1) 1, fun x hx => ?_⟩
      rcases lt_trichotomy x 1 with hlt | heq | hgt
  3. When $x < 1$, the supergradient inequality $K(x) \le K(1) + \ell(x - 1)$ holds.

    For the convex function $F$, the secant slope from $x$ to $1$ is bounded above by the left derivative $F'_-(1)$ via `slope_le_leftDeriv_of_mem_interior`, which is bounded above by the right derivative $F'_+(1)$ via `leftDeriv_le_rightDeriv_of_mem_interior`. By transitivity, $\mathrm{slope}(F, x, 1) \le F'_+(1)$. Expanding the slope using `slope_def_field` gives $(-K(1) - (-K(x))) / (1 - x) \le F'_+(1)$. Because $1 - x > 0$, clearing the denominator with `div_le_iff₀` and rearranging using linear arithmetic (`nlinarith`) produces $K(x) \le K(1) + \ell(x - 1)$.

    lines 9–12

    uses slope_le_leftDeriv_of_mem_interior, leftDeriv_le_rightDeriv_of_mem_interior, slope_def_field, div_le_iff₀

      · have h := (hF.slope_le_leftDeriv_of_mem_interior hx h1 hlt).trans
          (hF.leftDeriv_le_rightDeriv_of_mem_interior h1)
        rw [slope_def_field, div_le_iff₀ (by linarith)] at h
        nlinarith
  4. When $x = 1$, the inequality holds trivially.

    Substituting $x = 1$ reduces the goal to $K(1) \le K(1) + \ell \cdot 0$, which simplifies immediately to $K(1) \le K(1)$.

    line 13

      · subst heq; simp
  5. When $x > 1$, the supergradient inequality $K(x) \le K(1) + \ell(x - 1)$ holds.

    For the convex function $F$, the right derivative at $1$ is bounded above by the secant slope from $1$ to $x$ by `rightDeriv_le_slope_of_mem_interior`, so $F'_+(1) \le \mathrm{slope}(F, 1, x)$. Unfolding the slope with `slope_def_field` yields $F'_+(1) \le (-K(x) - (-K(1))) / (x - 1)$. Since $x - 1 > 0$, multiplying by $x - 1$ using `le_div_iff₀` and rearranging via linear arithmetic (`nlinarith`) yields $K(x) \le K(1) + \ell(x - 1)$.

    lines 14–16

    uses rightDeriv_le_slope_of_mem_interior, slope_def_field, le_div_iff₀

      · have h := hF.rightDeriv_le_slope_of_mem_interior h1 (show x ∈ Set.Ioi (0:ℝ) from hx) hgt
        rw [slope_def_field, le_div_iff₀ (by linarith)] at h
        nlinarith
interior_Ioi
The interior of an open ray $(a, \infty)$ in a linearly ordered topological space is the open ray itself.
lt_trichotomy
In a linear order, any two elements $a$ and $b$ satisfy $a < b$, $a = b$, or $b < a$.
slope_le_leftDeriv_of_mem_interior
For a convex function on a set $S$, if $x \in S$ and $y$ is in the interior of $S$ with $x < y$, then the secant slope between $x$ and $y$ is at most the left derivative at $y$.
leftDeriv_le_rightDeriv_of_mem_interior
For a convex function on a set $S$, at any point in the interior of $S$, the left derivative is less than or equal to the right derivative.
slope_def_field
The secant slope of a function $f$ between two distinct points $a$ and $b$ is $(f(b) - f(a)) / (b - a)$.
div_le_iff₀
For a strictly positive divisor $c > 0$, an inequality $b / c \le a$ is equivalent to $b \le a \cdot c$.
rightDeriv_le_slope_of_mem_interior
For a convex function on a set $S$, if $x$ is in the interior of $S$ and $y \in S$ with $x < y$, then the right derivative at $x$ is at most the secant slope between $x$ and $y$.
le_div_iff₀
For a strictly positive divisor $c > 0$, an inequality $a \le b / c$ is equivalent to $a \cdot c \le b$.

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 concave_on_ioi_exists_supergradient_at_one {K : ℝ → ℝ}    (hK : ConcaveOn ℝ (Set.Ioi (0 : ℝ)) K) :    ∃ ℓ : ℝ, ∀ x > 0, K x ≤ K 1 + ℓ * (x - 1) := by  have hF : ConvexOn ℝ (Set.Ioi (0 : ℝ)) (fun x => -K x) := hK.neg  have h1 : (1 : ℝ) ∈ interior (Set.Ioi (0 : ℝ)) := by    rw [interior_Ioi]; norm_num  refine ⟨-derivWithin (fun x => -K x) (Set.Ioi 1) 1, fun x hx => ?_⟩  rcases lt_trichotomy x 1 with hlt | heq | hgt  · have h := (hF.slope_le_leftDeriv_of_mem_interior hx h1 hlt).trans      (hF.leftDeriv_le_rightDeriv_of_mem_interior h1)    rw [slope_def_field, div_le_iff₀ (by linarith)] at h    nlinarith  · subst heq; simp  · have h := hF.rightDeriv_le_slope_of_mem_interior h1 (show x ∈ Set.Ioi (0:ℝ) from hx) hgt    rw [slope_def_field, le_div_iff₀ (by linarith)] at h    nlinarith
See it in the graphDiscuss this resultChallenge it