binary_linear_lift_third_difference
The third alternating finite difference of a lifted binary linear form on a three-dimensional cube equals four times the product of its three coefficients modulo eight.
Statement
theorem binary_linear_lift_third_difference (l : Fin 3 → ZMod 2) :
(∑ x : Fin 3 → ZMod 2,
(-1 : ZMod 8) ^ (∑ i : Fin 3, (x i).val) *
(((∑ i : Fin 3, l i*x i).val : ℕ) : ZMod 8)) =
4 * (((l 0*l 1*l 2).val : ℕ) : ZMod 8)- Source
- Supporting algebra for OP-3, arXiv:2610.01024, Section E.1; developed in deep session IN-184. These helpers do not establish a lower bound for arbitrary circuit gate lists.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- parity_phase_zero_third_momentIf a finite parity-phase polynomial is identically zero modulo eight, its binary third-moment tensor is zero; allowing repeated directions…
The proof, explained
The theorem evaluates the third alternating difference of a binary linear form lifted to $\mathbb{Z}/8\mathbb{Z}$ on the discrete 3-cube $(\mathbb{Z}/2\mathbb{Z})^3$, showing it equals $4(l_0 l_1 l_2) \pmod 8$. Because the space of coefficient vectors has size $2^3 = 8$ and each sum has only 8 terms, the identity is entirely finite. The proof generalizes over $l$ and dispatches the claim by exhaustive computational verification.
It suffices to establish the identity universally for all coefficient vectors $l$.
Reverting $l$ from the local context into a universal quantifier transforms the goal into $\forall l : \text{Fin } 3 \to \mathbb{Z}/2\mathbb{Z}, \dots$, making it a closed proposition over a finite type.
revert l
The identity holds for all $l$. automation
Because the function space $\text{Fin } 3 \to \mathbb{Z}/2\mathbb{Z}$ has cardinality $2^3 = 8$, the universal quantifier and the summations are over finite types. Lean's `decide` tactic checks all 8 possible assignments of $l$ and their corresponding 8-term sums by direct computation in $\mathbb{Z}/8\mathbb{Z}$.
decide
- The proof relies on `decide` to evaluate all 8 cases by finite computational reflection in the Lean kernel, which requires the increased recursion depth and heartbeat limits configured on lines 1 and 2.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 50000000theorem binary_linear_lift_third_difference (l : Fin 3 → ZMod 2) : (∑ x : Fin 3 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 3, (x i).val) * (((∑ i : Fin 3, l i*x i).val : ℕ) : ZMod 8)) = 4 * (((l 0*l 1*l 2).val : ℕ) : ZMod 8) := by revert l decide