AFTD Auto-Formalizing Theoretical Domains

boolean_derivative_add

theoremverified

The directional derivative operator D_v on Boolean functions is additive: D_v(g + h) = D_v(g) + D_v(h).

Statement

theorem boolean_derivative_add {n : ℕ} (v : Fin n → ZMod 2) (g h : (Fin n → ZMod 2) → ZMod 2) : boolean_derivative v (g + h) = boolean_derivative v g + boolean_derivative v h
Source
step towards boolean_derivative_conjecture_dim_eight
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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).

The proof, explained

The theorem states that the directional derivative operator on Boolean functions is additive, $D_v(g + h) = D_v(g) + D_v(h)$. By function extensionality, it suffices to compare values at an arbitrary point $x \in (\mathbb{Z}/2\mathbb{Z})^n$. Expanding the definition of directional derivative and pointwise addition yields the identity $(g(x) + h(x)) + (g(x+v) + h(x+v)) = (g(x) + g(x+v)) + (h(x) + h(x+v))$, which holds by associativity and commutativity in $\mathbb{Z}/2\mathbb{Z}$.

  1. To show that the two directional derivative functions are equal, it suffices to show that they agree on an arbitrary input $x$.

    By function extensionality (`ext x`), two functions from $(\mathbb{Z}/2\mathbb{Z})^n$ to $\mathbb{Z}/2\mathbb{Z}$ are identical if their values coincide on every input vector $x$.

    line 3

      ext x
  2. Evaluating both sides at $x$ reduces the equality to $(g(x) + h(x)) + (g(x + v) + h(x + v)) = (g(x) + g(x + v)) + (h(x) + h(x + v))$.

    Unfolding the definition of `boolean_derivative` and simplifying pointwise function additions using `Pi.add_apply` expresses both sides purely in terms of evaluations of $g$ and $h$ in $\mathbb{Z}/2\mathbb{Z}$.

    line 4

    uses boolean_derivative, Pi.add_apply

      simp only [boolean_derivative, Pi.add_apply]
  3. The two sides are equal, completing the proof.

    Both sides are sums of the exact same four terms: $g(x)$, $h(x)$, $g(x + v)$, and $h(x + v)$. The `ring` tactic closes the goal by associativity and commutativity of addition in the commutative ring $\mathbb{Z}/2\mathbb{Z}$.

    line 5

      ring
boolean_derivative
The directional derivative of a Boolean function $f$ in the direction of vector $v$ is given by $x \mapsto f(x) + f(x + v)$.
Pi.add_apply
Pointwise evaluation of a sum of functions: $(f + g)(x) = f(x) + g(x)$.

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 Boolean functions is linear over ZMod 2. -/theorem boolean_derivative_add {n : ℕ} (v : Fin n → ZMod 2) (g h : (Fin n → ZMod 2) → ZMod 2) : boolean_derivative v (g + h) = boolean_derivative v g + boolean_derivative v h := by  ext x  simp only [boolean_derivative, Pi.add_apply]  ring
See it in the graphDiscuss this resultChallenge it