AFTD Auto-Formalizing Theoretical Domains

boolean_derivative_exists_of_has_period

theoremverified

For any nonzero period v of a Boolean function f, there exists some Boolean function g such that the directional derivative of g along v is f.

Statement

theorem boolean_derivative_exists_of_has_period {n : ℕ} (v : Fin n → ZMod 2) (hv : v ≠ 0) (f : (Fin n → ZMod 2) → ZMod 2) (hf : ∀ x, f (x + v) = f x) : ∃ g : (Fin n → ZMod 2) → ZMod 2, boolean_derivative v g = f
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

Since the period vector $v$ is nonzero, it must have at least one coordinate $v(i) \neq 0$, which must be $1$ because coordinates take values in $\mathbb{Z}/2\mathbb{Z}$. We define the candidate antiderivative $g(x) = x(i) f(x)$. Its Boolean directional derivative along $v$ is $g(x) + g(x + v) = x(i) f(x) + (x(i) + 1) f(x + v)$, which simplifies by the periodicity of $f$ to $(2 x(i) + 1) f(x)$. Because $2 = 0$ in $\mathbb{Z}/2\mathbb{Z}$, the term $2 x(i) f(x)$ vanishes, leaving $f(x)$ as desired.

  1. There exists a coordinate index $i$ at which $v(i) \neq 0$.

    Because $v$ is nonzero by hypothesis ($v \neq 0$), not all of its coordinates can be zero. If they were, function extensionality (`funext`) would imply $v = 0$, contradicting $v \neq 0$. Thus, by contradiction, we obtain an index $i$ such that $v(i) \neq 0$.

    lines 3–6

    uses funext

      have : ∃ i, v i ≠ 0 := by
        by_contra! h
        exact hv (funext h)
      rcases this with ⟨i, hi⟩
  2. The coordinate $v(i)$ equals $1$.

    The vector coordinates take values in $\mathbb{Z}/2\mathbb{Z}$, which contains only $0$ and $1$. A case exhaustion (`fin_cases`) on the value of $v(i)$ rules out $0$ by contradiction (since $v(i) \neq 0$) and leaves $v(i) = 1$.

    lines 7–11

      have hvi : v i = 1 := by
        generalize hv_i : v i = a at *
        fin_cases a
        · contradiction
        · rfl
  3. It suffices to show that the function $g(x) = x(i) \cdot f(x)$ has directional derivative $f$ along $v$.

    We supply the explicit candidate function $g(x) = x(i) f(x)$ as the witness to satisfy the existential goal.

    line 12

      use fun x => x i * f x
  4. For any input vector $x$, the directional derivative $(D_v g)(x)$ simplifies to $x(i) f(x) + (x(i) + 1) f(x)$.

    To show two functions are equal, we check them pointwise for an arbitrary input $x$ (`ext x`). Unfolding the definition of the Boolean derivative gives $g(x) + g(x + v) = x(i) f(x) + (x + v)(i) f(x + v)$. Rewriting with the periodicity assumption $f(x + v) = f(x)$ and the fact that $v(i) = 1$ reduces this to $x(i) f(x) + (x(i) + 1) f(x)$.

    lines 13–15

      ext x
      dsimp [boolean_derivative]
      rw [hf, hvi]
  5. The expression $x(i) f(x) + (x(i) + 1) f(x)$ equals $f(x)$.

    Expanding the product gives $x(i) f(x) + x(i) f(x) + f(x) = 2 x(i) f(x) + f(x)$. Since the arithmetic is in $\mathbb{Z}/2\mathbb{Z}$, we have $2 = 0$, so the term $2 x(i) f(x)$ vanishes, leaving $f(x)$. The equality is verified by `linear_combination` using $2 = 0$.

    lines 16–17

      have h2 : (2 : ZMod 2) = 0 := rfl
      linear_combination (x i * f x) * h2
funext
Two functions are equal if they produce equal values for all inputs (function extensionality).

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

/-- Every Boolean function with period v is the directional derivative of some Boolean function along v. -/theorem boolean_derivative_exists_of_has_period {n : ℕ} (v : Fin n → ZMod 2) (hv : v ≠ 0) (f : (Fin n → ZMod 2) → ZMod 2) (hf : ∀ x, f (x + v) = f x) : ∃ g : (Fin n → ZMod 2) → ZMod 2, boolean_derivative v g = f := by  have : ∃ i, v i ≠ 0 := by    by_contra! h    exact hv (funext h)  rcases this with ⟨i, hi⟩  have hvi : v i = 1 := by    generalize hv_i : v i = a at *    fin_cases a    · contradiction    · rfl  use fun x => x i * f x  ext x  dsimp [boolean_derivative]  rw [hf, hvi]  have h2 : (2 : ZMod 2) = 0 := rfl  linear_combination (x i * f x) * h2
See it in the graphDiscuss this resultChallenge it