AFTD Auto-Formalizing Theoretical Domains

symmetric_counterexample_func_ne_zero

theoremverifiedformalization

For every natural number n, the symmetric Boolean function symmetric_counterexample_func n is not identically zero.

Statement

theorem symmetric_counterexample_func_ne_zero (n : ℕ) : symmetric_counterexample_func n ≠ 0
Formalizes
arXiv:2611.06744, Corollary 1
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • symmetric_counterexample_funcFor any integer n, the symmetric Boolean function F_n on (Fin n → ZMod 2) is the sum over j from 0 to n / 4 of the elementary symmetric…

Read back from the Lean

For every natural number n, the function symmetric_counterexample_func n is not the zero function from (Fin n → ZMod 2) to ZMod 2 (that is, it is not identically zero; there exists some x : Fin n → ZMod 2 for which it evaluates to a non-zero value in ZMod 2).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof proceeds by contradiction: assuming the symmetric Boolean function is identically zero, we evaluate it on the all-zero input to obtain a contradiction. In the definition of the function as a sum of elementary symmetric polynomials of even degree 2j, only the degree-0 term (j = 0) contributes 1 because the empty product is 1. For every degree 2j with j > 0, every subset in the sum is nonempty and thus contains a zero factor, making all higher terms vanish. Evaluating at the all-zero vector therefore yields 1, contradicting that the function is identically zero.

  1. It suffices to derive a contradiction from the assumption that the function is identically zero.

    We proceed by contradiction and assume that `symmetric_counterexample_func n` is the constant zero function (named h).

    line 3

      intro h
  2. Evaluating the function on the all-zero input isolates the j = 0 summand, which equals 1.

    To show that the function evaluates to 1 on the all-zero vector (the subproof `key`), we unfold the definition of `symmetric_counterexample_func`. The function is a sum over j ∈ {0, …, ⌊n/4⌋} of elementary symmetric polynomials of degree 2j. Applying `Finset.sum_eq_single 0` reduces the outer sum to the term at j = 0, provided all other terms vanish. For j = 0, the sum runs over subsets of size 0 (only the empty set), whose empty product is 1, so `simp` verifies this term equals 1.

    lines 4–7

    uses Finset.sum_eq_single

      have key : symmetric_counterexample_func n (fun _ => (0 : ZMod 2)) = 1 := by
        unfold symmetric_counterexample_func
        rw [Finset.sum_eq_single 0]
        · simp
  3. For every index j ≠ 0 in the summation range, the corresponding summand vanishes on the all-zero input.

    For any j > 0, by `Finset.sum_eq_zero`, it suffices to show that each term ∏ i ∈ s, 0 is zero for subsets s of size 2j. By `Finset.mem_powersetCard`, |s| = 2j. Since j ≠ 0, linear arithmetic (`omega`) gives 2j > 0, so by `Finset.card_pos`, the set s is nonempty. Choosing any element i ∈ s, the factor at i is 0, so by `Finset.prod_eq_zero_iff`, the entire product vanishes.

    lines 8–18

    uses Finset.sum_eq_zero, Finset.prod_eq_zero_iff, Finset.mem_powersetCard, Finset.card_pos

        · intro j hj h0
          rw [Finset.sum_eq_zero]
          intro s hs
          rw [Finset.prod_eq_zero_iff]
          rw [Finset.mem_powersetCard] at hs
          obtain ⟨_, hcard⟩ := hs
          have : s.Nonempty := by
            rw [← Finset.card_pos, hcard]
            omega
          obtain ⟨i, hi⟩ := this
          exact ⟨i, hi, rfl⟩
  4. The side condition 0 ∈ {0, …, ⌊n/4⌋} holds, establishing that the function evaluates to 1 on the all-zero input.

    The remaining obligation from `Finset.sum_eq_single` requires that the term vanish if 0 were outside the index set {0, …, ⌊n/4⌋}. Because 0 < n / 4 + 1 is always true for any natural number n, the assumption 0 ∉ range(n / 4 + 1) is contradictory, and `simp` closes the goal. This completes the subproof `key`, showing the function evaluates to 1 on the all-zero input.

    line 19

        · intro h; simp at h
  5. A contradiction is reached, proving the theorem.

    Rewriting with the contradiction hypothesis h in `key` substitutes 0 for the function, yielding 0 = 1 in ZMod 2. Simplification (`simp`) recognises 0 = 1 as false, completing the proof.

    lines 20–21

      rw [h] at key
      simp at key
Finset.sum_eq_single
A finite sum ∑ x ∈ s, f x reduces to f a if f b = 0 for all b ≠ a in s, and f a = 0 if a ∉ s.
Finset.sum_eq_zero
A finite sum is zero if every term is zero.
Finset.prod_eq_zero_iff
In a domain without zero divisors, a finite product is zero if and only if at least one factor is zero.
Finset.mem_powersetCard
A set s belongs to the subsets of t of size k if and only if s ⊆ t and |s| = k.
Finset.card_pos
A finite set has strictly positive cardinality if and only if it is nonempty.

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

/-- The symmetric Boolean function F_n is nonzero for every n. -/theorem symmetric_counterexample_func_ne_zero (n : ℕ) : symmetric_counterexample_func n ≠ 0 := by  intro h  have key : symmetric_counterexample_func n (fun _ => (0 : ZMod 2)) = 1 := by    unfold symmetric_counterexample_func    rw [Finset.sum_eq_single 0]    · simp    · intro j hj h0      rw [Finset.sum_eq_zero]      intro s hs      rw [Finset.prod_eq_zero_iff]      rw [Finset.mem_powersetCard] at hs      obtain ⟨_, hcard⟩ := hs      have : s.Nonempty := by        rw [← Finset.card_pos, hcard]        omega      obtain ⟨i, hi⟩ := this      exact ⟨i, hi, rfl⟩    · intro h; simp at h  rw [h] at key  simp at key
See it in the graphDiscuss this resultChallenge it