AFTD Auto-Formalizing Theoretical Domains

boolean_derivative_dim_eight_has_period

theoremverified

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)$.

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

    line 3

      use v, hv
  2. For 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$.

    lines 4–5

      intro x
      dsimp [boolean_derivative]
  3. 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.

    line 6

    uses add_assoc, CharTwo.add_self_eq_zero, add_zero, add_comm

      rw [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$.

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