AFTD Auto-Formalizing Theoretical Domains

binary_affine_quadratic_fourth_difference

theoremverified

The fourth alternating difference of twice the lift of a four-variable binary quadratic, with arbitrary affine terms, is four times a*f+b*e+c*d, where a,b,c,d,e,f are its six quadratic coefficients.

Statement

theorem binary_affine_quadratic_fourth_difference
    (a b c d e f t : ZMod 2) (l : Fin 4 → ZMod 2) :
    (∑ x : Fin 4 → ZMod 2,
      (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) *
        (2 * (((a*x 0*x 1 + b*x 0*x 2 + c*x 0*x 3 +
          d*x 1*x 2 + e*x 1*x 3 + f*x 2*x 3 + t +
          ∑ i : Fin 4, l i*x i).val : ℕ) : ZMod 8))) =
      4 * (((a*f + b*e + c*d).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

The proof, explained

The theorem asserts an identity in $\mathbb{Z}/8\mathbb{Z}$ for an alternating sum over $(\mathbb{Z}/2\mathbb{Z})^4$ depending on quadratic, linear, and constant coefficients in $\mathbb{Z}/2\mathbb{Z}$. Reverting the parameters turns the claim into a universal quantification over a finite domain of $2^{11} = 2048$ coefficient assignments. Since the truth of the identity over this finite domain is decidable, the proof is completed by exhaustive computation.

  1. It suffices to establish the identity universally for all parameter assignments $(a, b, c, d, e, f, t)$ and $l$.

    The fixed parameters $a, b, c, d, e, f, t \in \mathbb{Z}/2\mathbb{Z}$ and the linear coefficient function $l : \mathrm{Fin}\; 4 \to \mathbb{Z}/2\mathbb{Z}$ are moved from the local context back into the goal as universal quantifiers. This reformulates the goal as a closed proposition quantified over finite domains.

    line 12

      revert a b c d e f t l
  2. The identity holds for every choice of coefficients. automation

    The universal statement quantifies over a finite search space of $2^7 \cdot 2^4 = 2048$ configurations of binary coefficients, and for each configuration, the sum evaluates over the 16 elements of $(\mathbb{Z}/2\mathbb{Z})^4$ in the finite ring $\mathbb{Z}/8\mathbb{Z}$. Because the proposition is finite and decidable, the `decide` tactic verifies the equality by exhaustive kernel computation.

    line 13

      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_quadratic_fourth_difference    (a b c d e f t : ZMod 2) (l : Fin 4 → ZMod 2) :    (∑ x : Fin 4 → ZMod 2,      (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) *        (2 * (((a*x 0*x 1 + b*x 0*x 2 + c*x 0*x 3 +          d*x 1*x 2 + e*x 1*x 3 + f*x 2*x 3 + t +          ∑ i : Fin 4, l i*x i).val : ℕ) : ZMod 8))) =      4 * (((a*f + b*e + c*d).val : ℕ) : ZMod 8) := by  revert a b c d e f t l  decide
See it in the graphDiscuss this resultChallenge it