finite_avoidance_of_weighted_cubic_cost
For any natural-valued defect function on a finite sample space and any nonnegative real weights, a strictly negative weighted sum of (d-1)(d-3)(d-4) guarantees a sample with zero defects. This is elementary weighted finite averaging, not a uniform moment bound.
Statement
theorem finite_avoidance_of_weighted_cubic_cost {J : Type*} [Fintype J] (d : J → ℕ) (w : J → ℝ) (hw : ∀ j,0≤w j) (h : (∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4))<0) : ∃ j,d j=0
- Source
- IN-342 resumed helper for OP-306, arXiv:2610.22142 Sections3.3.2 and6. This is a weighted interface to the existing finite/adaptive cubic avoidance route. The new proposed square-polynomial weighting of invalid-color counts is tested only in experiments8807,8812,8822,8824. No uniform inequality, novel wild-number bound, or research advance is asserted by this conditional helper.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- wild_odd_sharpness_of_weighted_cubic_costAt any positive odd complete-graph order n>=3, for any minimum proper coloring and any finite family of rooted floor(n/3)-block partitions…
The proof, explained
The proof argues by contradiction: assume no sample has zero defects, so every defect count d(j) is a positive integer. On the positive integers d ≥ 1, the cubic polynomial (d - 1)(d - 3)(d - 4) is pointwise nonnegative, because d - 1 ≥ 0 and the two factors (d - 3) and (d - 4) always share the same sign (both nonpositive when d ≤ 3, and both nonnegative when d ≥ 4). Because the weights are nonnegative, the weighted sum of these cubic terms must also be nonnegative, contradicting the hypothesis that the sum is strictly negative.
Assume for contradiction that no sample has zero defects, meaning d(j) ≠ 0 for all j ∈ J.
We argue by contradiction using `by_contra! hno`. Supposing the existential conclusion is false provides the hypothesis `hno` that every sample j ∈ J has d(j) ≠ 0.
by_contra! hno
For every sample j ∈ J, the cubic factor (d(j) - 1)(d(j) - 3)(d(j) - 4) is nonnegative.
Fix j ∈ J. Because d(j) is a nonzero natural number, linear integer arithmetic (`omega`) gives 1 ≤ d(j), so d(j) - 1 ≥ 0 by `sub_nonneg.mpr`. To show that the remaining factor (d(j) - 3)(d(j) - 4) is nonnegative, we perform a case split on whether d(j) ≤ 3: if d(j) ≤ 3, then both d(j) - 3 ≤ 0 and d(j) - 4 ≤ 0, so their product is nonnegative by `mul_nonneg_of_nonpos_of_nonpos`; if d(j) > 3, then d(j) ≥ 4 in ℕ, so both d(j) - 3 ≥ 0 and d(j) - 4 ≥ 0, and their product is nonnegative by `mul_nonneg`. Multiplying the two nonnegative factors (d(j) - 1) and (d(j) - 3)(d(j) - 4) with `mul_nonneg` (rearranged by `mul_assoc`) establishes that the cubic polynomial is nonnegative.
uses
sub_nonneg.mpr,mul_nonneg_of_nonpos_of_nonpos,mul_nonneg,mul_assochave hp (j : J) : 0≤((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4) := by have hd : (1 : ℝ)≤d j := by exact_mod_cast (show 1≤d j by have := hno j;omega) have hpair : 0≤((d j : ℝ)-3)*((d j : ℝ)-4) := by by_cases hh : d j≤3 · have hh' : (d j : ℝ)≤3 := by exact_mod_cast hh exact mul_nonneg_of_nonpos_of_nonpos (by linarith) (by linarith) · have hh' : (4 : ℝ)≤d j := by exact_mod_cast (show 4≤d j by omega) exact mul_nonneg (by linarith) (by linarith) simpa only [mul_assoc] using mul_nonneg (sub_nonneg.mpr hd) hpair
The weighted sum ∑ j, w(j) * (d(j) - 1) * (d(j) - 3) * (d(j) - 4) is nonnegative.
By `sum_nonneg`, a sum of nonnegative terms is nonnegative. For each j ∈ J, the weight w(j) is nonnegative by hypothesis `hw`, and the cubic term was proved nonnegative in the previous step (`hp`). Applying `mul_nonneg` with associativity (`mul_assoc`) shows that each summand is nonnegative, so their sum is nonnegative.
uses
sum_nonneg,mul_assoc,mul_nonneghave hs : 0≤∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4) := by apply sum_nonneg intro j _ simpa only [mul_assoc] using mul_nonneg (hw j) (hp j)
A contradiction is reached, concluding the proof.
Linear arithmetic (`linarith`) closes the proof by finding a direct contradiction between the fact that the weighted sum is nonnegative (≥ 0, established in the previous step) and the theorem's hypothesis `h` that the weighted sum is strictly negative (< 0).
linarith
sub_nonneg.mpr- If b ≤ a, then 0 ≤ a - b.
mul_nonneg_of_nonpos_of_nonpos- If a ≤ 0 and b ≤ 0, then 0 ≤ a * b (the product of two nonpositive numbers is nonnegative).
mul_nonneg- If 0 ≤ a and 0 ≤ b, then 0 ≤ a * b (the product of two nonnegative numbers is nonnegative).
mul_assoc- Multiplication is associative: (a * b) * c = a * (b * c).
sum_nonneg- A finite sum of nonnegative elements is nonnegative.
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.
open Finsetopen scoped BigOperatorsset_option maxHeartbeats 2000000theorem finite_avoidance_of_weighted_cubic_cost {J : Type*} [Fintype J] (d : J → ℕ) (w : J → ℝ) (hw : ∀ j,0≤w j) (h : (∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4))<0) : ∃ j,d j=0 := by by_contra! hno have hp (j : J) : 0≤((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4) := by have hd : (1 : ℝ)≤d j := by exact_mod_cast (show 1≤d j by have := hno j;omega) have hpair : 0≤((d j : ℝ)-3)*((d j : ℝ)-4) := by by_cases hh : d j≤3 · have hh' : (d j : ℝ)≤3 := by exact_mod_cast hh exact mul_nonneg_of_nonpos_of_nonpos (by linarith) (by linarith) · have hh' : (4 : ℝ)≤d j := by exact_mod_cast (show 4≤d j by omega) exact mul_nonneg (by linarith) (by linarith) simpa only [mul_assoc] using mul_nonneg (sub_nonneg.mpr hd) hpair have hs : 0≤∑ j,w j*((d j : ℝ)-1)*((d j : ℝ)-3)*((d j : ℝ)-4) := by apply sum_nonneg intro j _ simpa only [mul_assoc] using mul_nonneg (hw j) (hp j) linarith