AFTD Auto-Formalizing Theoretical Domains

finite_avoidance_of_adaptive_cubic_moments

theoremverified

For a natural-valued defect count d on any finite sample space and any positive integer r, put R=r(r+1). If R times sum(d) plus6 times sum(binomial(d,3)) is strictly less than R times the sample-space size plus (4r-2) times sum(binomial(d,2)), some sample has defect count zero.

Statement

theorem finite_avoidance_of_adaptive_cubic_moments
    {J : Type*} [Fintype J] (d : J → ℕ) (r : ℕ) (hr : 1 ≤ r)
    (h : (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) +
        6 * (∑ j, ((d j).choose 3 : ℝ)) <
      (r : ℝ) * (r + 1) * Fintype.card J +
        (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) :
    ∃ j, d j = 0
Source
OP-306 / IN-338 general-route helpers for the strict prescribed-coloring conjecture in arXiv:2610.22142, Sections3.3.2 and6. Structural analysis of binary factorizations and exact finite averaging in experiments8399,8400,8402,8414. These are conditional certificate or method-diagnostic lemmas, not a new wild-number bound or research advance.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

We argue by contradiction, assuming every sample in the finite space J has defect count d(j) ≥ 1. For any integer d ≥ 1 and r ≥ 1, the cubic polynomial (1 - d)(d - r)(d - (r + 1)) is nonpositive because 1 - d ≤ 0 while the consecutive integer roots r and r + 1 ensure (d - r)(d - (r + 1)) ≥ 0. Expanding this cubic polynomial gives a pointwise inequality bounding a linear combination of d(j) and binomial(d(j), 3) from below by binomial(d(j), 2) and a constant. Summing this pointwise inequality over the entire sample space yields an inequality that contradicts the strict upper bound assumed in the theorem hypothesis, proving that some sample must have defect count zero.

  1. For any natural number d, 6 * (d.choose 3 : ℝ) = d * (d - 1) * (d - 2).

    We argue by induction on d. The base case d = 0 holds immediately since both sides evaluate to 0. For the inductive step d + 1, Pascal's recurrence expresses (d + 1).choose 3 as d.choose 2 + d.choose 3. Substituting d.choose 2 = d * (d - 1) / 2 and the induction hypothesis for 6 * d.choose 3, nonlinear arithmetic verifies the identity.

    lines 7–13

    uses Nat.choose_succ_succ, Nat.cast_choose_two

      induction d with
      | zero => norm_num
      | succ d ih =>
        rw [Nat.choose_succ_succ]
        push_cast
        rw [Nat.cast_choose_two]
        nlinarith only [ih]
  2. For all d, r ∈ ℕ, the cubic product (1 - d) * (d - r) * (d - (r + 1)) equals r * (r + 1) * (1 - d) + (4 * r - 2) * (d.choose 2) - 6 * (d.choose 3).

    Rewriting d.choose 2 in terms of d * (d - 1) / 2 and using the previous lemma for 6 * d.choose 3, both sides expand to the same cubic polynomial in d, which nonlinear arithmetic confirms.

    lines 19–20

    uses Nat.cast_choose_two, in338_choose_three

      rw [Nat.cast_choose_two]
      nlinarith only [in338_choose_three d]
  3. For all natural numbers d and r, the quadratic factor (d - r) * (d - (r + 1)) is nonnegative.

    We case split on whether d ≤ r. If d ≤ r, both factors d - r and d - (r + 1) are nonpositive, so their product is nonnegative. Otherwise d > r, which for natural numbers means r + 1 ≤ d; then both factors are nonnegative, and their product is again nonnegative.

    lines 24–29

    uses mul_nonneg_of_nonpos_of_nonpos, mul_nonneg

      have hpair : 0 ≤ ((d : ℝ) - r) * ((d : ℝ) - (r + 1)) := by
        by_cases h : d ≤ r
        · have h' : (d : ℝ) ≤ r := by exact_mod_cast h
          exact mul_nonneg_of_nonpos_of_nonpos (by linarith) (by linarith)
        · have h' : (r : ℝ) + 1 ≤ d := by exact_mod_cast (show r + 1 ≤ d by omega)
          exact mul_nonneg (by linarith) (by linarith)
  4. If d ≥ 1, the cubic expression (1 - d) * (d - r) * (d - (r + 1)) is nonpositive.

    Since d ≥ 1, the first factor 1 - d is nonpositive. Multiplying this nonpositive factor by the previously established nonnegative product (d - r) * (d - (r + 1)) yields a nonpositive result.

    lines 30–32

    uses mul_assoc, mul_nonpos_of_nonpos_of_nonneg, sub_nonpos.mpr

      have hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd
      simpa only [mul_assoc] using
        mul_nonpos_of_nonpos_of_nonneg (sub_nonpos.mpr hd') hpair
  5. Under the assumption that no sample has defect count zero, every sample j satisfies r * (r + 1) + (4 * r - 2) * ((d j).choose 2) ≤ r * (r + 1) * (d j) + 6 * ((d j).choose 3).

    Assuming for contradiction that d j ≠ 0 for all j, each defect count satisfies d j ≥ 1. Evaluating the cubic expression at d j gives a nonpositive value. Rewriting this via the cubic identity and rearranging terms with nonlinear arithmetic yields the desired pointwise inequality.

    lines 41–48

    uses in338_cubic_nonpos, in338_cubic_identity

      by_contra! hno
      have hp : ∀ j, (r : ℝ) * (r + 1) +
            (4 * (r : ℝ) - 2) * ((d j).choose 2 : ℝ) ≤
          (r : ℝ) * (r + 1) * (d j : ℝ) + 6 * ((d j).choose 3 : ℝ) := by
        intro j
        have hx := in338_cubic_nonpos (d j) r (by have := hno j; omega)
        rw [in338_cubic_identity] at hx
        nlinarith only [hx]
  6. Summing the pointwise inequality over all j ∈ J yields r * (r + 1) * |J| + (4 * r - 2) * ∑ j, ((d j).choose 2) ≤ r * (r + 1) * ∑ j, (d j) + 6 * ∑ j, ((d j).choose 3).

    Summing the pointwise inequality over the finite space J preserves the inequality. Distributing the sum across addition, factoring the constants out of the sums, and simplifying the constant sum over J to r * (r + 1) * |J| gives the aggregated bound.

    lines 49–51

    uses sum_le_sum, sum_add_distrib, sum_const, card_univ, nsmul_eq_mul, mul_sum

      have hs := sum_le_sum (fun j (_ : j ∈ (univ : Finset J)) => hp j)
      simp only [sum_add_distrib, sum_const, card_univ, nsmul_eq_mul,
        ← mul_sum] at hs
  7. There exists some sample j ∈ J with defect count d j = 0.

    The aggregated sum inequality directly contradicts the strict inequality assumed in the theorem statement, refuting the assumption that all defect counts are positive.

    line 52

      nlinarith only [h, hs]
Nat.choose_succ_succ
Pascal's identity: (n + 1).choose (k + 1) = n.choose k + n.choose (k + 1) for natural numbers n, k.
Nat.cast_choose_two
The binomial coefficient a.choose 2 cast into a division ring equals a * (a - 1) / 2.
in338_choose_three
For any natural number d, 6 * (d.choose 3) = d * (d - 1) * (d - 2) in the real numbers.
mul_nonneg_of_nonpos_of_nonpos
The product of two nonpositive numbers is nonnegative.
mul_nonneg
The product of two nonnegative numbers is nonnegative.
mul_assoc
Multiplication is associative: (a * b) * c = a * (b * c).
mul_nonpos_of_nonpos_of_nonneg
The product of a nonpositive number and a nonnegative number is nonpositive.
sub_nonpos.mpr
If a ≤ b, then a - b ≤ 0.
in338_cubic_nonpos
For natural numbers d ≥ 1 and r, the cubic expression (1 - d) * (d - r) * (d - (r + 1)) is nonpositive.
in338_cubic_identity
The identity (1 - d) * (d - r) * (d - (r + 1)) = r * (r + 1) * (1 - d) + (4 * r - 2) * (d.choose 2) - 6 * (d.choose 3) holds in ℝ for all d, r ∈ ℕ.
sum_le_sum
If f(i) ≤ g(i) for all i in a finite set s, then ∑ i ∈ s, f(i) ≤ ∑ i ∈ s, g(i).
sum_add_distrib
A sum distributes across addition: ∑ x ∈ s, (f(x) + g(x)) = ∑ x ∈ s, f(x) + ∑ x ∈ s, g(x).
sum_const
Summing a constant c over a finite set s equals |s| • c.
card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
nsmul_eq_mul
Natural scalar multiplication in a semiring equals multiplication by the cast of the natural number: n • a = (↑n) * a.
mul_sum
A constant factor distributes into a finite sum: c * ∑ i ∈ s, f(i) = ∑ i ∈ s, c * f(i).

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 2000000private lemma in338_choose_three (d : ℕ) :    6 * (d.choose 3 : ℝ) = (d : ℝ) * (d - 1) * (d - 2) := by  induction d with  | zero => norm_num  | succ d ih =>    rw [Nat.choose_succ_succ]    push_cast    rw [Nat.cast_choose_two]    nlinarith only [ih]private lemma in338_cubic_identity (d r : ℕ) :    (1 - (d : ℝ)) * ((d : ℝ) - r) * ((d : ℝ) - (r + 1)) =      (r : ℝ) * (r + 1) * (1 - (d : ℝ)) +        (4 * (r : ℝ) - 2) * (d.choose 2 : ℝ) - 6 * (d.choose 3 : ℝ) := by  rw [Nat.cast_choose_two]  nlinarith only [in338_choose_three d]private lemma in338_cubic_nonpos (d r : ℕ) (hd : 1 ≤ d) :    (1 - (d : ℝ)) * ((d : ℝ) - r) * ((d : ℝ) - (r + 1)) ≤ 0 := by  have hpair : 0 ≤ ((d : ℝ) - r) * ((d : ℝ) - (r + 1)) := by    by_cases h : d ≤ r    · have h' : (d : ℝ) ≤ r := by exact_mod_cast h      exact mul_nonneg_of_nonpos_of_nonpos (by linarith) (by linarith)    · have h' : (r : ℝ) + 1 ≤ d := by exact_mod_cast (show r + 1 ≤ d by omega)      exact mul_nonneg (by linarith) (by linarith)  have hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd  simpa only [mul_assoc] using    mul_nonpos_of_nonpos_of_nonneg (sub_nonpos.mpr hd') hpairtheorem finite_avoidance_of_adaptive_cubic_moments    {J : Type*} [Fintype J] (d : J → ℕ) (r : ℕ) (hr : 1 ≤ r)    (h : (r : ℝ) * (r + 1) * (∑ j, (d j : ℝ)) +        6 * (∑ j, ((d j).choose 3 : ℝ)) <      (r : ℝ) * (r + 1) * Fintype.card J +        (4 * (r : ℝ) - 2) * (∑ j, ((d j).choose 2 : ℝ))) :    ∃ j, d j = 0 := by  by_contra! hno  have hp : ∀ j, (r : ℝ) * (r + 1) +        (4 * (r : ℝ) - 2) * ((d j).choose 2 : ℝ) ≤      (r : ℝ) * (r + 1) * (d j : ℝ) + 6 * ((d j).choose 3 : ℝ) := by    intro j    have hx := in338_cubic_nonpos (d j) r (by have := hno j; omega)    rw [in338_cubic_identity] at hx    nlinarith only [hx]  have hs := sum_le_sum (fun j (_ : j ∈ (univ : Finset J)) => hp j)  simp only [sum_add_distrib, sum_const, card_univ, nsmul_eq_mul,    ← mul_sum] at hs  nlinarith only [h, hs]
See it in the graphDiscuss this resultChallenge it