binary_quadratic_four_cube_expansion
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
- binary_quadratic_polar_quartic_relationIf twice the binary lift of a quadratic form has zero fourth alternating difference on every four-direction cube, its polar bilinear form…
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.
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`.
have hid : ∀ z : ZMod 2, z*z=z := by decide
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`.
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_mulsimp 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]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.
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
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.
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!