binary_affine_lift_fourth_difference
The fourth alternating finite difference of the lift to Z/8 of any affine binary function on a four-dimensional cube is zero.
Statement
theorem binary_affine_lift_fourth_difference
(a : ZMod 2) (l : Fin 4 → ZMod 2) :
(∑ x : Fin 4 → ZMod 2,
(-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) *
(((a + ∑ i : Fin 4, l i * x i).val : ℕ) : ZMod 8)) = 0- 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_fourth_differenceEvery finite Z/8 linear combination of lifted binary linear forms has zero fourth alternating difference on each four-direction cube.
The proof, explained
The theorem states that the fourth alternating finite difference of the integer lift to $\mathbb{Z}/8\mathbb{Z}$ of any affine function on $(\mathbb{Z}/2\mathbb{Z})^4$ is zero. Because the domain of affine functions on a four-dimensional binary cube is finite (comprising only $2 \times 2^4 = 32$ functions) and the cube has $16$ vertices, the claim is a finite combinatorial identity. The proof universally quantifies over all parameters and verifies the statement by exhaustive computation using Lean's `decide` tactic.
The alternating sum $\sum_{x \in (\mathbb{Z}/2\mathbb{Z})^4} (-1)^{\sum x_i} (a + \sum l_i x_i)$ evaluates to $0$ in $\mathbb{Z}/8\mathbb{Z}$ for all constants $a \in \mathbb{Z}/2\mathbb{Z}$ and linear functionals $l : \mathrm{Fin}\;4 \to \mathbb{Z}/2\mathbb{Z}$. automation
Reverting $a$ and $l$ turns the goal into a closed universal statement over finite domains. Since there are only $2$ choices for $a$ and $2^4 = 16$ choices for $l$, there are $32$ affine functions in total, and each sum involves the $2^4 = 16$ vertices of the four-dimensional hypercube. The `decide` tactic checks all 32 cases by exhaustive kernel evaluation, verifying that the identity holds in $\mathbb{Z}/8\mathbb{Z}$ for every case.
revert a l decide
- The proof relies entirely on exhaustive finite verification (`decide`) rather than an algebraic argument about finite difference operators or polynomial degrees of integer lifts.
- The compiler options `maxRecDepth` and `maxHeartbeats` on lines 1–2 are set to large values because evaluating the 16-term alternating sum across all 32 affine functions requires significant computational resources in Lean's kernel.
- The `revert a l` tactic on line 9 is a formal requirement to present the goal to `decide` as a closed universally quantified proposition over finite types.
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_affine_lift_fourth_difference (a : ZMod 2) (l : Fin 4 → ZMod 2) : (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (((a + ∑ i : Fin 4, l i * x i).val : ℕ) : ZMod 8)) = 0 := by revert a l decide