finite_avoidance_of_adaptive_cubic_moments
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
- wild_odd_sharpness_of_adaptive_cubic_momentsFor any minimum proper coloring at odd order n>=3 and any finite family of rooted partitions into floor(n/3) blocks of size at least…
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.
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.
uses
Nat.choose_succ_succ,Nat.cast_choose_twoinduction d with | zero => norm_num | succ d ih => rw [Nat.choose_succ_succ] push_cast rw [Nat.cast_choose_two] nlinarith only [ih]
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.
uses
Nat.cast_choose_two,in338_choose_threerw [Nat.cast_choose_two] nlinarith only [in338_choose_three d]
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.
uses
mul_nonneg_of_nonpos_of_nonpos,mul_nonneghave 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)
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.
uses
mul_assoc,mul_nonpos_of_nonpos_of_nonneg,sub_nonpos.mprhave hd' : (1 : ℝ) ≤ d := by exact_mod_cast hd simpa only [mul_assoc] using mul_nonpos_of_nonpos_of_nonneg (sub_nonpos.mpr hd') hpair
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.
uses
in338_cubic_nonpos,in338_cubic_identityby_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]
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.
uses
sum_le_sum,sum_add_distrib,sum_const,card_univ,nsmul_eq_mul,mul_sumhave 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
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.
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).
- The algebraic identity verification in lines 13 and 20 and the term rearrangement in line 48 are discharged by nonlinear arithmetic automation (`nlinarith`).
- The final contradiction in line 52 is closed by linear arithmetic automation (`nlinarith`), detecting that A < B and B ≤ A cannot both hold.
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 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]