quadratic_bent_form_three_is_bent
The standard quadratic form on (Fin 6 → ZMod 2) given by z 0 * z 1 + z 2 * z 3 + z 4 * z 5 is bent.
Statement
theorem quadratic_bent_form_three_is_bent : is_bent (fun z : Fin 6 → ZMod 2 => z 0 * z 1 + z 2 * z 3 + z 4 * z 5)
- Source
- arXiv:2610.32239, Lemma 4.1
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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 function $f : (\text{Fin } 6 \to \mathbb{Z}/2\mathbb{Z}) \to \mathbb{Z}/2\mathbb{Z}$ given by $f(z) = z(0) z(1) + z(2) z(3) + z(4) z(5)$ is bent (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
The bentness of the 6-variable quadratic form $z_0 z_1 + z_2 z_3 + z_4 z_5$ requires showing that its Walsh–Hadamard transform has absolute value $2^{6/2} = 8$ at every frequency vector $\omega \in (\mathbb{Z}/2\mathbb{Z})^6$. Because the domain $(\mathbb{Z}/2\mathbb{Z})^6$ has only 64 elements, this is a finite, decidable proposition. Unfolding the definition reduces the theorem to an exhaustive evaluation over all 64 inputs, which is verified by Lean's computational decision procedure.
The goal is to show that for every frequency vector $\omega \in (\mathbb{Z}/2\mathbb{Z})^6$, the Walsh-Hadamard sum has absolute value $2^{6/2} = 8$.
Unfolding the definition of `is_bent` expresses the bentness condition explicitly: for every vector $\omega : \text{Fin } 6 \to \mathbb{Z}/2\mathbb{Z}$, the Walsh-Hadamard transform $\sum_{x} (-1)^{f(x) + x \cdot \omega}$ must have absolute value equal to $2^{6/2} = 8$.
unfold is_bentThe Walsh-Hadamard transform magnitude is 8 for every frequency vector $\omega$. automation
Because the domain $\text{Fin } 6 \to \mathbb{Z}/2\mathbb{Z}$ is finite (containing $2^6 = 64$ elements), the universal quantifier over $\omega$ and the sums over $x$ are completely finite. The `decide` tactic resolves the goal by exhaustive computation over all 64 vectors.
decide
- The proof relies on `decide` to evaluate the Walsh-Hadamard transform exhaustively on all 64 frequency vectors in $(\mathbb{Z}/2\mathbb{Z})^6$ via kernel reduction, rather than using an algebraic argument about quadratic forms.
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 quadratic form z₁z₂ + z₃z₄ + z₅z₆ on 6 variables is a bent function. -/theorem quadratic_bent_form_three_is_bent : is_bent (fun z : Fin 6 → ZMod 2 => z 0 * z 1 + z 2 * z 3 + z 4 * z 5) := by unfold is_bent decide