finite_avoidance_of_three_binomial_moments
For a natural-valued function d on a finite sample space J, if the sum of d plus the sum of binomial(d,3) is strictly less than the cardinality of J plus the sum of binomial(d,2), then d is zero at some sample.
Statement
theorem finite_avoidance_of_three_binomial_moments {J : Type*} [Fintype J] (d : J → ℕ) (h : (∑ j : J, d j) + (∑ j : J, (d j).choose 3) < Fintype.card J + (∑ j : J, (d j).choose 2)) : ∃ j, d j = 0
- Source
- Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- prm_ghw_dimension_reduction_zeroFor any finite field K and parameters e, m, r, the generalized Hamming weight of PRM_K(e + 0*(|K|-1), m) of rank r equals that of PRM_K(e,…
The proof, explained
The proof argues by contradiction: assume d(j) ≠ 0 for every j in J. Since d(j) ≥ 1, writing d(j) = r + 1 and applying Pascal's identity shows that 1 + binomial(d(j), 2) ≤ d(j) + binomial(d(j), 3) holds pointwise. Summing this inequality over the finite space J yields |J| + ∑ binomial(d(j), 2) ≤ ∑ d(j) + ∑ binomial(d(j), 3), directly contradicting the assumed strict inequality.
Assume for contradiction that d(j) ≠ 0 for all j ∈ J.
The proof proceeds by contradiction: assuming the negation of the existential conclusion, namely that d is non-zero everywhere on J, we seek to derive False.
by_contra! hno
For every j ∈ J, 1 + binomial(d(j), 2) ≤ d(j) + binomial(d(j), 3).
Since d(j) ≠ 0, we can write d(j) = r + 1 for some natural number r. Using Pascal's identity, we expand binomial(r + 1, 2) as r + binomial(r, 2) and binomial(r + 1, 3) as binomial(r, 2) + binomial(r, 3). The inequality becomes 1 + r + binomial(r, 2) ≤ (r + 1) + binomial(r, 2) + binomial(r, 3), which holds by linear arithmetic since the right-hand side has the extra non-negative term binomial(r, 3).
uses
Nat.exists_eq_succ_of_ne_zero,Nat.choose_succ_succ,Nat.choose_one_righthave pointwise : ∀ j, 1+(d j).choose 2 ≤ d j+(d j).choose 3 := by intro j obtain ⟨r,he⟩ := Nat.exists_eq_succ_of_ne_zero (hno j) rw [he] simp only [Nat.choose_succ_succ,Nat.choose_one_right] change 1+(r+r.choose 2) ≤ (r+1)+(r.choose 2+r.choose 3) omega
|J| + ∑ j, binomial(d(j), 2) ≤ ∑ j, d(j) + ∑ j, binomial(d(j), 3).
Summing the pointwise inequality over all j in the universal finset of J preserves the inequality. Distributing the additions and simplifying the sum of the constant 1 over J to |J| gives the desired inequality on the totals.
uses
Finset.sum_le_sum,Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_onehave hi := Finset.sum_le_sum (fun j (_ : j ∈ (Finset.univ : Finset J)) => pointwise j) simp only [Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_one] at hi have hi' : Fintype.card J+(∑ j : J, (d j).choose 2) ≤ (∑ j : J, d j)+(∑ j : J, (d j).choose 3) := by exact_mod_cast hi
False, completing the contradiction.
The summed inequality |J| + ∑ j, binomial(d(j), 2) ≤ ∑ j, d(j) + ∑ j, binomial(d(j), 3) directly contradicts the hypothesis h, which asserts the strict inequality in the opposite direction. Linear arithmetic closes the goal.
omega
Nat.exists_eq_succ_of_ne_zero- Any non-zero natural number can be written as the successor of some natural number: if n ≠ 0, then n = k + 1 for some k.
Nat.choose_succ_succ- Pascal's recurrence identity for binomial coefficients: (n + 1).choose (k + 1) = n.choose k + n.choose (k + 1).
Nat.choose_one_right- For any natural number n, n.choose 1 = n.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i of a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.sum_add_distrib- The sum of two functions over a finite set splits into the sum of the sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
Finset.sum_const- The sum of a constant value b over a finite set s equals the cardinality of s scalar-multiplied by b.
Finset.card_univ- The cardinality of the universal finset univ of a finite type α equals Fintype.card α.
nsmul_eq_mul- Natural number scalar multiplication n • a equals the product n * a.
mul_one- Multiplying an element by 1 on the right leaves it unchanged: a * 1 = a.
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 scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem finite_avoidance_of_three_binomial_moments {J : Type*} [Fintype J] (d : J → ℕ) (h : (∑ j : J, d j) + (∑ j : J, (d j).choose 3) < Fintype.card J + (∑ j : J, (d j).choose 2)) : ∃ j, d j = 0 := by by_contra! hno have pointwise : ∀ j, 1+(d j).choose 2 ≤ d j+(d j).choose 3 := by intro j obtain ⟨r,he⟩ := Nat.exists_eq_succ_of_ne_zero (hno j) rw [he] simp only [Nat.choose_succ_succ,Nat.choose_one_right] change 1+(r+r.choose 2) ≤ (r+1)+(r.choose 2+r.choose 3) omega have hi := Finset.sum_le_sum (fun j (_ : j ∈ (Finset.univ : Finset J)) => pointwise j) simp only [Finset.sum_add_distrib,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_one] at hi have hi' : Fintype.card J+(∑ j : J, (d j).choose 2) ≤ (∑ j : J, d j)+(∑ j : J, (d j).choose 3) := by exact_mod_cast hi omega