weighted_two_section_log_concavity
Two log-concave local sections, with the stated likelihood and shifted weak comparisons, give the corresponding weighted log-concavity inequality for their binary extension.
Statement
theorem weighted_two_section_log_concavity (L K x xm xp y ym yp : ℝ)
(hL : 1 ≤ L) (hK : 1 ≤ K)
(hx : xm * xp ≤ x ^ 2) (hy : ym * yp ≤ y ^ 2)
(horder : xm * yp ≤ x * y)
(hshift : xm * yp + xp * ym ≤ 2 * x * y) :
((L + 1) * xm + (K - 1) * ym) *
((L - 1) * xp + (K + 1) * yp) ≤ (L * x + K * y) ^ 2- Source
- An elementary nonnegative decomposition for the one-vertex extension in OP-1399.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof establishes the inequality by showing that the difference between the right-hand side and the left-hand side, (L*x + K*y)^2 - ((L + 1)*xm + (K - 1)*ym)*((L - 1)*xp + (K + 1)*yp), is non-negative. An exact algebraic identity decomposes this difference into the sum of (x - y)^2 and four weighted terms: (L^2 - 1)*(x^2 - xm*xp), (K^2 - 1)*(y^2 - ym*yp), 2*(L + K)*(x*y - xm*yp), and (L - 1)*(K - 1)*(2*x*y - xm*yp - xp*ym). Each of these five terms is shown to be non-negative using the local log-concavity of the two sections, the likelihood ratio ordering, the shifted comparison, and the conditions L, K ≥ 1. Since the difference is a sum of non-negative quantities, it is non-negative, completing the proof.
The section log-concavity terms (L^2 - 1) * (x^2 - xm * xp) and (K^2 - 1) * (y^2 - ym * yp) are non-negative.
Because L ≥ 1 and K ≥ 1, non-linear arithmetic (`nlinarith`) establishes that 0 ≤ L^2 - 1 (hLsq) and 0 ≤ K^2 - 1 (hKsq). The section log-concavity hypotheses xm * xp ≤ x^2 and ym * yp ≤ y^2 imply that x^2 - xm * xp ≥ 0 and y^2 - ym * yp ≥ 0 via `sub_nonneg.mpr`. Multiplying each pair of non-negative terms with `mul_nonneg` yields non-negative products h1 and h2.
uses
mul_nonneg,sub_nonneg.mprhave hLsq : 0 ≤ L ^ 2 - 1 := by nlinarith have hKsq : 0 ≤ K ^ 2 - 1 := by nlinarith have h1 : 0 ≤ (L ^ 2 - 1) * (x ^ 2 - xm * xp) := mul_nonneg hLsq (sub_nonneg.mpr hx) have h2 : 0 ≤ (K ^ 2 - 1) * (y ^ 2 - ym * yp) := mul_nonneg hKsq (sub_nonneg.mpr hy)
The likelihood ratio ordering cross-term 2 * (L + K) * (x * y - xm * yp) is non-negative.
Since L ≥ 1 and K ≥ 1, linear arithmetic gives 0 ≤ 2 * (L + K). The assumption xm * yp ≤ x * y implies 0 ≤ x * y - xm * yp via `sub_nonneg.mpr`. Their product is non-negative by `mul_nonneg` (stored as h3).
uses
mul_nonneg,sub_nonneg.mprhave h3 : 0 ≤ 2 * (L + K) * (x * y - xm * yp) := mul_nonneg (by linarith) (sub_nonneg.mpr horder)
The shifted comparison term (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) is non-negative.
From L ≥ 1 and K ≥ 1, both L - 1 ≥ 0 and K - 1 ≥ 0. The shifted comparison hypothesis xm * yp + xp * ym ≤ 2 * x * y rearranges to 0 ≤ 2 * x * y - xm * yp - xp * ym by linear arithmetic. Multiplying these three non-negative factors together via `mul_nonneg` produces the non-negative term h4.
uses
mul_nonneghave h4 : 0 ≤ (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) := mul_nonneg (mul_nonneg (by linarith) (by linarith)) (by linarith)
It suffices to show that (L * x + K * y)^2 - ((L + 1) * xm + (K - 1) * ym) * ((L - 1) * xp + (K + 1) * yp) ≥ 0.
Applying `sub_nonneg.mp` reduces the inequality A ≤ B to showing that the difference B - A is non-negative.
uses
sub_nonneg.mpapply sub_nonneg.mpThe difference (L * x + K * y)^2 - ((L + 1) * xm + (K - 1) * ym) * ((L - 1) * xp + (K + 1) * yp) is identically equal to (x - y)^2 + (L^2 - 1) * (x^2 - xm * xp) + (K^2 - 1) * (y^2 - ym * yp) + 2 * (L + K) * (x * y - xm * yp) + (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym).
Expanding and collecting terms on both sides confirms this polynomial identity over the real numbers, verified automatically by `ring`.
calc (L * x + K * y) ^ 2 - ((L + 1) * xm + (K - 1) * ym) * ((L - 1) * xp + (K + 1) * yp) = (x - y) ^ 2 + (L ^ 2 - 1) * (x ^ 2 - xm * xp) + (K ^ 2 - 1) * (y ^ 2 - ym * yp) + 2 * (L + K) * (x * y - xm * yp) + (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) := by ring
The difference is non-negative, which establishes the theorem.
The term (x - y)^2 is non-negative as a square (`sq_nonneg`), and the remaining four terms h1, h2, h3, h4 were shown to be non-negative in the earlier steps. Repeated applications of `add_nonneg` show that their sum is non-negative.
uses
add_nonneg,sq_nonneg_ ≥ 0 := add_nonneg (add_nonneg (add_nonneg (add_nonneg (sq_nonneg (x - y)) h1) h2) h3) h4
add_nonneg- The sum of two non-negative elements is non-negative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a + b.
mul_nonneg- The product of two non-negative elements is non-negative: if 0 ≤ a and 0 ≤ b, then 0 ≤ a * b.
sq_nonneg- The square of any element is non-negative: 0 ≤ a ^ 2.
sub_nonneg.mp- If 0 ≤ a - b, then b ≤ a.
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
- The polynomial identity in lines 19–25 is verified by the `ring` tactic, which automatically expands and cancels all products on both sides without displaying intermediate algebraic manipulations.
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 weighted_two_section_log_concavity (L K x xm xp y ym yp : ℝ) (hL : 1 ≤ L) (hK : 1 ≤ K) (hx : xm * xp ≤ x ^ 2) (hy : ym * yp ≤ y ^ 2) (horder : xm * yp ≤ x * y) (hshift : xm * yp + xp * ym ≤ 2 * x * y) : ((L + 1) * xm + (K - 1) * ym) * ((L - 1) * xp + (K + 1) * yp) ≤ (L * x + K * y) ^ 2 := by have hLsq : 0 ≤ L ^ 2 - 1 := by nlinarith have hKsq : 0 ≤ K ^ 2 - 1 := by nlinarith have h1 : 0 ≤ (L ^ 2 - 1) * (x ^ 2 - xm * xp) := mul_nonneg hLsq (sub_nonneg.mpr hx) have h2 : 0 ≤ (K ^ 2 - 1) * (y ^ 2 - ym * yp) := mul_nonneg hKsq (sub_nonneg.mpr hy) have h3 : 0 ≤ 2 * (L + K) * (x * y - xm * yp) := mul_nonneg (by linarith) (sub_nonneg.mpr horder) have h4 : 0 ≤ (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) := mul_nonneg (mul_nonneg (by linarith) (by linarith)) (by linarith) apply sub_nonneg.mp calc (L * x + K * y) ^ 2 - ((L + 1) * xm + (K - 1) * ym) * ((L - 1) * xp + (K + 1) * yp) = (x - y) ^ 2 + (L ^ 2 - 1) * (x ^ 2 - xm * xp) + (K ^ 2 - 1) * (y ^ 2 - ym * yp) + 2 * (L + K) * (x * y - xm * yp) + (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) := by ring _ ≥ 0 := add_nonneg (add_nonneg (add_nonneg (add_nonneg (sq_nonneg (x - y)) h1) h2) h3) h4