boolean_derivative_dim_eight_has_period
For every Boolean function g on (Fin 8 → ZMod 2) and every nonzero vector v, the directional derivative of g along v has a nonzero period.
Statement
theorem boolean_derivative_dim_eight_has_period (g : (Fin 8 → ZMod 2) → ZMod 2) (v : Fin 8 → ZMod 2) (hv : v ≠ 0) : has_nonzero_period (boolean_derivative v g)- Source
- arXiv:2610.32239, Section 2
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- boolean_derivativeThe directional derivative of a Boolean function f on (Fin n → ZMod 2) along a vector v is the function x ↦ f(x) + f(x + v).
- has_nonzero_periodA Boolean function f has a nonzero period if there exists a nonzero vector a such that f(x + a) = f(x) for all x.
Read back from the Lean
For every function g : (Fin 8 → ZMod 2) → ZMod 2 and every vector v : Fin 8 → ZMod 2, if v ≠ 0, then the Boolean derivative of g with respect to v has a nonzero period; that is, there exists a vector a : Fin 8 → ZMod 2 such that a ≠ 0 and, for all x : Fin 8 → ZMod 2, boolean_derivative v g (x + a) = boolean_derivative v g x.
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 directional derivative of a Boolean function $g$ along a vector $v$ is defined by $(\Delta_v g)(x) = g(x) + g(x + v)$. To show that $\Delta_v g$ has a nonzero period, the proof takes the direction vector $v$ itself as the period. Evaluating $(\Delta_v g)(x + v)$ produces $g(x + v) + g(x + 2v)$, and since vector addition in characteristic 2 satisfies $2v = 0$, this simplifies to $g(x + v) + g(x) = (\Delta_v g)(x)$.
The direction vector $v$ serves as a candidate nonzero period for the directional derivative $\Delta_v g$.
By definition, a function has a nonzero period if there exists a nonzero vector $a$ such that translating the input by $a$ leaves the function unchanged. We provide $v$ as the witness, which is nonzero by the hypothesis $hv$.
use v, hvFor an arbitrary vector $x$, the periodicity condition is $g(x + v) + g(x + v + v) = g(x) + g(x + v)$.
Let $x$ be an arbitrary vector. Unfolding the definition of the Boolean directional derivative $(\Delta_v g)(y) = g(y) + g(y + v)$ on both sides transforms the goal $(\Delta_v g)(x + v) = (\Delta_v g)(x)$ into an equality between values of $g$.
intro x dsimp [boolean_derivative]
The periodicity equation holds identically.
Associating vector addition rewrites $x + v + v$ as $x + (v + v)$. Because the coordinates lie in $\mathbb{Z}/2\mathbb{Z}$, the vector space has characteristic 2, so $v + v = 0$ and $x + (v + v)$ simplifies to $x + 0 = x$. The left-hand side thus reduces to $g(x + v) + g(x)$, which equals $g(x) + g(x + v)$ by commutativity of addition, matching the right-hand side.
uses
add_assoc,CharTwo.add_self_eq_zero,add_zero,add_commrw [add_assoc, CharTwo.add_self_eq_zero, add_zero, add_comm]
add_assoc- Addition is associative: $(a + b) + c = a + (b + c)$.
CharTwo.add_self_eq_zero- In a semiring of characteristic 2, adding any element to itself yields zero: $x + x = 0$.
add_zero- Adding zero on the right leaves an element unchanged: $a + 0 = a$.
add_comm- Addition is commutative: $a + b = b + a$.
- Although the theorem is stated specifically for dimension 8 (vectors in $\mathrm{Fin}\ 8 \to \mathbb{Z}/2\mathbb{Z}$), the dimension plays no role in the proof; the result holds over any characteristic-2 space.
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 directional derivative of a Boolean function along a nonzero vector has a nonzero period. -/theorem boolean_derivative_dim_eight_has_period (g : (Fin 8 → ZMod 2) → ZMod 2) (v : Fin 8 → ZMod 2) (hv : v ≠ 0) : has_nonzero_period (boolean_derivative v g) := by use v, hv intro x dsimp [boolean_derivative] rw [add_assoc, CharTwo.add_self_eq_zero, add_zero, add_comm]