symmetric_counterexample_eight_not_bent
The eight-variable symmetric Boolean function F_8 is not bent.
Statement
theorem symmetric_counterexample_eight_not_bent :
¬ is_bent symmetric_counterexample_func_eight- Formalizes
- arXiv:2611.06744 Corollary 1
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- is_bentA Boolean function f on (Fin n → ZMod 2) is bent if its Walsh-Hadamard transform has absolute value 2^(n/2) everywhere.
Read back from the Lean
The Boolean function symmetric_counterexample_func_eight on 8 variables is not bent (does not satisfy is_bent).
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
To show that the eight-variable symmetric Boolean function F_8 is not bent, we assume for contradiction that it is bent. By definition, a bent function on eight variables must have a Walsh–Hadamard transform of absolute value 2^(8/2) = 16 at every frequency vector, in particular at ω = 0. Because evaluating the Walsh–Hadamard transform at 0 is a finite sum over all 2^8 = 256 inputs, Lean's `decide` tactic verifies by direct calculation that the sum does not equal 16, refuting the assumption.
If F_8 were bent, its Walsh–Hadamard transform at ω = 0 would have absolute value 2^(8/2) = 16.
Assume for contradiction that F_8 is bent (hypothesis h). By the definition of `is_bent`, the absolute value of the Walsh–Hadamard transform at any frequency vector ω ∈ (ℤ/2ℤ)^8 must equal 2^(8/2) = 16. Instantiating this condition at ω = 0 gives the equality |∑_x (-1)^(F_8(x))| = 16 as hypothesis h0.
intro h have h0 := h 0
The Walsh–Hadamard transform at ω = 0 does not equal 16, yielding a contradiction. automation
Hypothesis h0 is moved back into the goal (`revert h0`) to form the implication that |∑_x (-1)^(F_8(x))| = 16 implies False. Because the sum ranges over the finite space (ℤ/2ℤ)^8 of size 256, the entire proposition is decidable by computation. The `decide` tactic evaluates this finite sum directly (which equals 164 ≠ 16) and derives False, closing the goal.
revert h0 decide
- Moving hypothesis h0 back into the goal with `revert` is a Lean bookkeeping step to present the proposition as an implication so that the decision procedure `decide` can evaluate it.
- The `decide` tactic operates by exhaustively computing the Walsh–Hadamard sum over all 2^8 = 256 inputs in the kernel, without recording intermediate mathematical deduction 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.
/-- The eight-variable symmetric Boolean function F_8 is not bent. -/theorem symmetric_counterexample_eight_not_bent : ¬ is_bent symmetric_counterexample_func_eight := by intro h have h0 := h 0 revert h0 decide