AFTD Auto-Formalizing Theoretical Domains

symmetric_counterexample_func_eight_eq

theoremverified

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.

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

    lines 5–6

    uses Finset.sum_range_succ

      simp only [symmetric_counterexample_func]
      norm_num [Finset.sum_range_succ]
  2. 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.

    line 10

      funext x
  3. The 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`).

    lines 11–12

    uses symmetric_counterexample_func_eight_eq_key

      rw [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.

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

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