concave_on_ioi_exists_supergradient_at_one
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
- subadditive_f_generator_satisfies_weight_boundFirst claim of Corollary 1 of arXiv:2610.21231: let s be twice continuously differentiable and positive on (0, ∞) with s'' < 0, let K_s(x)…
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.
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)$.
uses
interior_Ioihave hF : ConvexOn ℝ (Set.Ioi (0 : ℝ)) (fun x => -K x) := hK.neg have h1 : (1 : ℝ) ∈ interior (Set.Ioi (0 : ℝ)) := by rw [interior_Ioi]; norm_num
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$.
uses
lt_trichotomyrefine ⟨-derivWithin (fun x => -K x) (Set.Ioi 1) 1, fun x hx => ?_⟩ rcases lt_trichotomy x 1 with hlt | heq | hgt
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)$.
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
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)$.
· subst heq; simp
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)$.
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$.
- The right derivative $F'_+(1)$ of the convex function $F(x) = -K(x)$ is formalized using Mathlib's `derivWithin` on the ray $(1, \infty)$ at the point $1$.
- The algebraic rearrangements after clearing denominators in the cases $x < 1$ and $x > 1$ are closed by `nlinarith`, which distributes the negative signs and simplifies products.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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