AFTD Auto-Formalizing Theoretical Domains

binary_affine_lift_fourth_difference

theoremverified

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.

  1. 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.

    lines 9–10

      revert a l
      decide

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

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
See it in the graphDiscuss this resultChallenge it