AFTD Auto-Formalizing Theoretical Domains

fractional_kr_cover_clique_weight_ge_one

theoremverified

For rational r > 0 and 1 ≤ j ≤ r, the quantity 1 + (j - 1)(r - j)/r is at least 1.

Statement

theorem fractional_kr_cover_clique_weight_ge_one (r j : ℚ) (hr : 0 < r)
    (hj1 : 1 ≤ j) (hjr : j ≤ r) :
    1 ≤ 1 + (j - 1) * (r - j) / r
Source
arXiv:2610.41371 Lemma 3.2
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any rational numbers $r$ and $j$, if $0 < r$, $1 \le j$, and $j \le r$, then $1 \le 1 + (j - 1) \cdot (r - j) / r$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that 1 + (j - 1)(r - j)/r ≥ 1 for 1 ≤ j ≤ r and r > 0, the proof shows that the added term is non-negative. The numerator factors j - 1 and r - j are non-negative by the bounds on j, so their product is non-negative. Dividing by the positive denominator r preserves non-negativity, and adding this non-negative quotient to 1 completes the inequality.

  1. Both j - 1 and r - j are non-negative.

    From the hypotheses 1 ≤ j and j ≤ r, linear arithmetic directly establishes that 0 ≤ j - 1 and 0 ≤ r - j.

    lines 5–6

      have h1 : 0 ≤ j - 1 := by linarith
      have h2 : 0 ≤ r - j := by linarith
  2. The product (j - 1)(r - j) is non-negative.

    Since both factors j - 1 and r - j are non-negative, their product (j - 1)(r - j) is non-negative by mul_nonneg.

    line 7

    uses mul_nonneg

      have h3 : 0 ≤ (j - 1) * (r - j) := mul_nonneg h1 h2
  3. The fraction (j - 1)(r - j) / r is non-negative.

    From the hypothesis 0 < r, we obtain 0 ≤ r via le_of_lt. Dividing the non-negative numerator (j - 1)(r - j) by the non-negative denominator r yields a non-negative quotient by div_nonneg.

    line 8

    uses div_nonneg, le_of_lt

      have h4 : 0 ≤ (j - 1) * (r - j) / r := div_nonneg h3 (le_of_lt hr)
  4. The inequality 1 ≤ 1 + (j - 1)(r - j) / r holds.

    Since (j - 1)(r - j) / r ≥ 0, adding this quantity to 1 yields at least 1, which linear arithmetic (linarith) verifies.

    line 9

      linarith
mul_nonneg
The product of two non-negative elements is non-negative.
div_nonneg
The quotient of two non-negative elements is non-negative.
le_of_lt
A strict inequality a < b implies the non-strict inequality 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

/-- Inequality showing the clique edge weight sum is at least 1 when 1 ≤ j ≤ r. -/theorem fractional_kr_cover_clique_weight_ge_one (r j : ℚ) (hr : 0 < r)    (hj1 : 1 ≤ j) (hjr : j ≤ r) :    1 ≤ 1 + (j - 1) * (r - j) / r := by  have h1 : 0 ≤ j - 1 := by linarith  have h2 : 0 ≤ r - j := by linarith  have h3 : 0 ≤ (j - 1) * (r - j) := mul_nonneg h1 h2  have h4 : 0 ≤ (j - 1) * (r - j) / r := div_nonneg h3 (le_of_lt hr)  linarith
See it in the graphDiscuss this resultChallenge it