AFTD Auto-Formalizing Theoretical Domains

binary_quadratic_four_cube_expansion

theoremverified

A binary quadratic form evaluated on a four-direction cube equals the sum of its linear vertex values and the six pairwise polar terms.

Statement

theorem binary_quadratic_four_cube_expansion {V : Type*}
    [AddCommGroup V] [Module (ZMod 2) V]
    (Q : QuadraticForm (ZMod 2) V) (u : Fin 4 → V) (x : Fin 4 → ZMod 2) :
    Q (∑ i : Fin 4, x i • u i) =
      (∑ i : Fin 4, x i * Q (u i)) +
      Q.polarBilin (u 0) (u 1)*x 0*x 1 +
      Q.polarBilin (u 0) (u 2)*x 0*x 2 +
      Q.polarBilin (u 0) (u 3)*x 0*x 3 +
      Q.polarBilin (u 1) (u 2)*x 1*x 2 +
      Q.polarBilin (u 1) (u 3)*x 1*x 3 +
      Q.polarBilin (u 2) (u 3)*x 2*x 3
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 evaluates a quadratic form $Q$ over $\mathbb{Z}/2\mathbb{Z}$ on a four-direction linear combination $\sum_{i=0}^3 x_i • u_i$. The key property over the field $\mathbb{Z}/2\mathbb{Z}$ is that every scalar satisfies $z^2 = z$, so the quadratic scaling $Q(x_i • u_i) = x_i^2 • Q(u_i)$ reduces to the linear expression $x_i * Q(u_i)$. Expanding the sum using the definition of a quadratic form produces the four vertex terms plus the six bilinear cross terms, after which ring algebra completes the proof.

  1. Every element of $\mathbb{Z}/2\mathbb{Z}$ is idempotent ($z^2 = z$).

    Since $\mathbb{Z}/2\mathbb{Z}$ contains only the elements $0$ and $1$, the identity $z^2 = z$ holds by finite case exhaustion, verified by `decide`.

    line 12

      have hid : ∀ z : ZMod 2, z*z=z := by decide
  2. Evaluating $Q$ on the linear combination $\sum_{i=0}^3 x_i • u_i$ expands into four vertex terms $x_i * Q(u_i)$ and six bilinear cross terms.

    The four-term sum over $\text{Fin } 4$ is expanded into individual summands using `Fin.sum_univ_succ`, `Fin.sum_univ_zero`, and `add_zero`. Next, `QuadraticMap.map_add` distributes the quadratic form across addition, generating the vertex terms and the polar terms, which are converted to the bilinear form via `QuadraticMap.polarBilin_apply_apply`. For each vertex term, `QuadraticMap.map_smul` pulls out the scalar squared ($x_i^2$), which reduces to $x_i$ by the idempotence lemma `hid`. Finally, the bilinear polar terms are factored by pulling out scalars via `map_add`, `map_smul`, `LinearMap.add_apply`, `LinearMap.smul_apply`, and `smul_eq_mul`.

    lines 13–16

    uses Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero, QuadraticMap.map_add, QuadraticMap.polarBilin_apply_apply, QuadraticMap.map_smul, map_add, map_smul, LinearMap.add_apply, LinearMap.smul_apply, smul_eq_mul

      simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero,
        QuadraticMap.map_add Q, ← QuadraticMap.polarBilin_apply_apply,
        QuadraticMap.map_smul Q, map_add, map_smul, LinearMap.add_apply,
        LinearMap.smul_apply, smul_eq_mul, hid]
  3. The expanded quadratic form matches the target expression.

    Both sides of the equality are identical polynomials in the quantities $x_i$, $Q(u_i)$, and $Q.\text{polarBilin}(u_i, u_j)$ over the commutative ring $\mathbb{Z}/2\mathbb{Z}$. The `ring!` tactic verifies this equivalence by normalizing both sides using the ring axioms.

    line 17

      ring!
Fin.sum_univ_succ
Decomposes a finite sum over `Fin (n + 1)` into the 0th term and the remaining sum over `Fin n`: $\sum_{i=0}^n f(i) = f(0) + \sum_{i=0}^{n-1} f(i + 1)$.
Fin.sum_univ_zero
A sum over the empty index set `Fin 0` equals zero.
add_zero
Adding zero to an element leaves it unchanged ($a + 0 = a$).
QuadraticMap.map_add
A quadratic map evaluated on a sum satisfies $Q(x + y) = Q(x) + Q(y) + \text{polar}(Q)(x, y)$.
QuadraticMap.polarBilin_apply_apply
Relates the bilinear polar form of a quadratic map to its polar evaluation: $(Q.\text{polarBilin}(x))(y) = \text{polar}(Q)(x, y)$.
QuadraticMap.map_smul
A quadratic map scales quadratically: $Q(a • x) = (a * a) • Q(x)$.
map_add
An additive map preserves addition: $f(x + y) = f(x) + f(y)$.
map_smul
A module homomorphism preserves scalar multiplication: $f(c • x) = c • f(x)$.
LinearMap.add_apply
The pointwise evaluation of the sum of two linear maps is $(f + g)(x) = f(x) + g(x)$.
LinearMap.smul_apply
The pointwise evaluation of a scalar multiple of a linear map is $(a • f)(x) = a • f(x)$.
smul_eq_mul
In a ring considered as a module over itself, scalar multiplication is ring multiplication: $a • b = a * b$.

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

theorem binary_quadratic_four_cube_expansion {V : Type*}    [AddCommGroup V] [Module (ZMod 2) V]    (Q : QuadraticForm (ZMod 2) V) (u : Fin 4 → V) (x : Fin 4 → ZMod 2) :    Q (∑ i : Fin 4, x i • u i) =      (∑ i : Fin 4, x i * Q (u i)) +      Q.polarBilin (u 0) (u 1)*x 0*x 1 +      Q.polarBilin (u 0) (u 2)*x 0*x 2 +      Q.polarBilin (u 0) (u 3)*x 0*x 3 +      Q.polarBilin (u 1) (u 2)*x 1*x 2 +      Q.polarBilin (u 1) (u 3)*x 1*x 3 +      Q.polarBilin (u 2) (u 3)*x 2*x 3 := by  have hid : ∀ z : ZMod 2, z*z=z := by decide  simp only [Fin.sum_univ_succ, Fin.sum_univ_zero, add_zero,    QuadraticMap.map_add Q, ← QuadraticMap.polarBilin_apply_apply,    QuadraticMap.map_smul Q, map_add, map_smul, LinearMap.add_apply,    LinearMap.smul_apply, smul_eq_mul, hid]  ring!
See it in the graphDiscuss this resultChallenge it