AFTD Auto-Formalizing Theoretical Domains

symmetric_counterexample_eight_not_bent

theoremverifiedformalization

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.

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

    lines 4–5

      intro h
      have h0 := h 0
  2. 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.

    lines 6–7

      revert h0
      decide

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

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