AFTD Auto-Formalizing Theoretical Domains

weighted_two_section_log_concavity

theoremverified

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.

  1. 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.

    lines 8–13

    uses mul_nonneg, sub_nonneg.mpr

      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)
  2. 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).

    lines 14–15

    uses mul_nonneg, sub_nonneg.mpr

      have h3 : 0 ≤ 2 * (L + K) * (x * y - xm * yp) :=
        mul_nonneg (by linarith) (sub_nonneg.mpr horder)
  3. 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.

    lines 16–17

    uses mul_nonneg

      have h4 : 0 ≤ (L - 1) * (K - 1) * (2 * x * y - xm * yp - xp * ym) :=
        mul_nonneg (mul_nonneg (by linarith) (by linarith)) (by linarith)
  4. 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.

    line 18

    uses sub_nonneg.mp

      apply sub_nonneg.mp
  5. The 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`.

    lines 19–25

      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
  6. 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.

    line 26

    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.

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 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
See it in the graphDiscuss this resultChallenge it