AFTD Auto-Formalizing Theoretical Domains

binary_linear_lift_third_difference

theoremverified

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.

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

    line 9

      revert l
  2. 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}$.

    line 10

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