symmetric_counterexample_eight_ne_zero
The eight-variable symmetric Boolean function F_8 is not identically zero.
Statement
theorem symmetric_counterexample_eight_ne_zero :
symmetric_counterexample_func_eight ≠ 0- Formalizes
- arXiv:2611.06744 Corollary 1
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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_eight (from Fin 8 → ZMod 2 to ZMod 2) is not equal to the zero function 0 (that is, it is not identically zero).
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 claim is proved by finite computation. Because the symmetric Boolean function F_8 is defined on a finite domain of 2⁸ = 256 inputs with values in ℤ/2ℤ, equality to the zero function is a decidable proposition. The `decide` tactic checks this by evaluation (or finding a counterexample, such as the all-zero input where the function evaluates to 1) and verifies that the function is not identically zero.
The symmetric Boolean function F_8 is not the zero function. automation
The proof uses the `first` combinator to attempt several automated tactics. After `simp_all` and `omega` fail to close the goal, `decide` succeeds by direct computation: because the domain (Fin 8 → ZMod 2) is a finite type with 2⁸ = 256 elements and equality in ZMod 2 is decidable, equality with the zero function is decidable. In particular, evaluating the function at the all-zero vector yields 1, confirming it is non-zero.
symmetric_counterexample_func_eight ≠ 0 := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
- The proof employs the `first` tactic combinator to try several standard proof automation tactics in succession. The goal is closed by `decide`, which resolves the inequality by direct computation over the finite domain.
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 eight-variable symmetric Boolean function F_8 is not the zero function. -/theorem symmetric_counterexample_eight_ne_zero : symmetric_counterexample_func_eight ≠ 0 := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)