symmetric_counterexample_func_eight_eq
The symmetric Boolean function symmetric_counterexample_func 8 on (Fin 8 → ZMod 2) equals symmetric_counterexample_func_eight.
Statement
theorem symmetric_counterexample_func_eight_eq : symmetric_counterexample_func 8 = symmetric_counterexample_func_eight- Source
- arXiv:2611.06744, Section 1
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- symmetric_counterexample_func_eightThe eight-variable symmetric Boolean function F_8 = 1 + σ_2 + σ_4 on (Fin 8 → ZMod 2), defined as the sum modulo two of 1 and the…
Read back from the Lean
The function symmetric_counterexample_func 8 equals the function symmetric_counterexample_func_eight (both of type (Fin 8 → ZMod 2) → 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 theorem shows that the general definition of the symmetric counterexample function on 8 variables specializes to `symmetric_counterexample_func_eight`. The proof applies functional extensionality to reduce function equality to pointwise agreement on an arbitrary vector x. A helper lemma expands the summation over j from 0 to 8/4 = 2 into its degree 0 (constant 1), degree 2, and degree 4 components. Rewriting with this expansion matches the definition of `symmetric_counterexample_func_eight` identically, finishing by reflexivity.
For any x : Fin 8 → ZMod 2, the function symmetric_counterexample_func 8 x expands to 1 + (∑ s ∈ powersetCard 2 univ, ∏ i ∈ s, x i) + (∑ s ∈ powersetCard 4 univ, ∏ i ∈ s, x i). automation
Unfolding the definition of `symmetric_counterexample_func` expresses the value as a sum over j ∈ {0, ..., 8 / 4} = {0, 1, 2} of the elementary symmetric polynomials of degree 2j. The `norm_num` tactic evaluates the index bound 8 / 4 + 1 = 3, unrolls the summation via `Finset.sum_range_succ`, and computes the j = 0 term (the empty product, which is 1), leaving the degree 2 and degree 4 sums.
uses
Finset.sum_range_succsimp only [symmetric_counterexample_func] norm_num [Finset.sum_range_succ]
To show symmetric_counterexample_func 8 = symmetric_counterexample_func_eight, it suffices to prove they agree on an arbitrary input vector x.
By functional extensionality (`funext`), two functions are equal if and only if they agree on all inputs x : Fin 8 → ZMod 2.
funext xThe functions agree pointwise on every input x.
Rewriting symmetric_counterexample_func 8 x with the key lemma expands it into 1 plus the degree 2 and degree 4 elementary symmetric polynomials. This matches the definition of symmetric_counterexample_func_eight x verbatim, closing the goal by reflexivity (`rfl`).
uses
symmetric_counterexample_func_eight_eq_keyrw [symmetric_counterexample_func_eight_eq_key] rfl
Finset.sum_range_succ- The sum of a function over {0, ..., n} equals the sum over {0, ..., n - 1} plus the term at n.
symmetric_counterexample_func_eight_eq_key- For any x : Fin 8 → ZMod 2, the function symmetric_counterexample_func 8 x expands to 1 plus the sum of products of pairs of coordinates plus the sum of products of quadruples of coordinates.
- In line 6, the `norm_num` tactic automatically computes 8 / 4 + 1 = 3, unrolls the finite sum over j ∈ {0, 1, 2} using `Finset.sum_range_succ`, and evaluates the empty product at j = 0 to 1 without displaying intermediate steps.
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.
private lemma symmetric_counterexample_func_eight_eq_key (x : Fin 8 → ZMod 2) : symmetric_counterexample_func 8 x = 1 + (∑ s ∈ Finset.powersetCard 2 Finset.univ, ∏ i ∈ s, x i) + (∑ s ∈ Finset.powersetCard 4 Finset.univ, ∏ i ∈ s, x i) := by simp only [symmetric_counterexample_func] norm_num [Finset.sum_range_succ]/-- Equivalence of symmetric_counterexample_func 8 with symmetric_counterexample_func_eight. -/theorem symmetric_counterexample_func_eight_eq : symmetric_counterexample_func 8 = symmetric_counterexample_func_eight := by funext x rw [symmetric_counterexample_func_eight_eq_key] rfl