fractional_kr_cover_clique_weight_ge_one
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
- join_complete_turan_fractional_cover_and_total_weightLet n, r, a be integers with r ≥ 3 and a ≤ n. The edge weighting w_a is a fractional K_r-cover of G_a = K_a ∨ T_{r-1}(n-a), and the total…
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.
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.
have h1 : 0 ≤ j - 1 := by linarith have h2 : 0 ≤ r - j := by linarith
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.
uses
mul_nonneghave h3 : 0 ≤ (j - 1) * (r - j) := mul_nonneg h1 h2The 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.
uses
div_nonneg,le_of_lthave h4 : 0 ≤ (j - 1) * (r - j) / r := div_nonneg h3 (le_of_lt hr)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.
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
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.
/-- 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