symmetric_counterexample_func_ne_zero
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.
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).
intro hEvaluating 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.
uses
Finset.sum_eq_singlehave key : symmetric_counterexample_func n (fun _ => (0 : ZMod 2)) = 1 := by unfold symmetric_counterexample_func rw [Finset.sum_eq_single 0] · simp
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.
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⟩
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.
· intro h; simp at h
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.
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
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.
/-- 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