AFTD Auto-Formalizing Theoretical Domains

finite_avoidance_of_weighted_cubic_cost

theoremverified

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

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.

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

    line 10

      by_contra! hno
  2. 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.

    lines 11–19

    uses sub_nonneg.mpr, mul_nonneg_of_nonpos_of_nonpos, mul_nonneg, mul_assoc

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

    lines 20–23

    uses sum_nonneg, mul_assoc, mul_nonneg

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

    line 24

      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

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