AFTD Auto-Formalizing Theoretical Domains

finite_avoidance_of_three_binomial_moments

theoremverified

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.

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

    line 9

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

    lines 10–16

    uses Nat.exists_eq_succ_of_ne_zero, Nat.choose_succ_succ, Nat.choose_one_right

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

    lines 17–20

    uses Finset.sum_le_sum, Finset.sum_add_distrib, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one

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

    line 21

      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

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