boolean_derivative_exists_of_has_period
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.
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$.
uses
funexthave : ∃ i, v i ≠ 0 := by by_contra! h exact hv (funext h) rcases this with ⟨i, hi⟩
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$.
have hvi : v i = 1 := by generalize hv_i : v i = a at * fin_cases a · contradiction · rfl
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.
use fun x => x i * f x
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)$.
ext x dsimp [boolean_derivative] rw [hf, hvi]
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$.
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
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.
/-- 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