parity_phase_fourth_difference
Every finite Z/8 linear combination of lifted binary linear forms has zero fourth alternating difference on each four-direction cube.
Statement
theorem parity_phase_fourth_difference {V ι : Type*} [AddCommGroup V] [Module (ZMod 2) V] [Fintype ι] (c : ι → ZMod 8) (L : ι → V →ₗ[ZMod 2] ZMod 2) (u : Fin 4 → V) : (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (∑ j : ι, c j * ((L j (∑ i : Fin 4, x i • u 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- Built on 1
- binary_affine_lift_fourth_differenceThe fourth alternating finite difference of the lift to Z/8 of any affine binary function on a four-dimensional cube is zero.
- Used by 1
- binary_quadratic_polar_rank_le_two_of_parity_liftIf twice the binary lift of a quadratic form is a finite parity-phase polynomial modulo eight, its polar matrix has rank at most two.
The proof, explained
The theorem states that the fourth alternating difference on a four-direction cube of any Z/8 linear combination of lifted binary linear forms is zero. By linearity of the forms, the alternating sum over the cube vertices commutes with the summation over the index set ι. Factoring out the scalar coefficient c_j for each index reduces the claim to the vanishing of the fourth alternating difference of a single lifted binary linear form, which holds by binary_affine_lift_fourth_difference.
By linearity of each L_j and swapping summations, the total expression is rewritten as a sum over j ∈ ι of the fourth alternating difference of each term.
We enable classical logic. By linearity of each map L_j (using map_sum, map_smul, and smul_eq_mul), L_j applied to the linear combination ∑_i x_i • u_i expands to ∑_i x_i * L_j(u_i). Distributing the alternating sign factor (-1)^(∑_i (x_i).val) across the sum over j via Finset.mul_sum and exchanging the order of summation between x ∈ (ZMod 2)^4 and j ∈ ι using Finset.sum_comm, the goal becomes showing that the sum over j of the alternating sums is zero.
uses
map_sum,map_smul,smul_eq_mul,Finset.mul_sum,Finset.sum_commclassical simp only [map_sum, map_smul, smul_eq_mul, Finset.mul_sum] rw [Finset.sum_comm]
It suffices to show that for every j ∈ ι, the inner alternating sum vanishes.
By Finset.sum_eq_zero, a finite sum is zero if every term is zero. We introduce an arbitrary index j ∈ ι.
uses
Finset.sum_eq_zeroapply Finset.sum_eq_zero intro j hj
The fourth alternating difference of the lifted linear form x ↦ ∑_i L_j(u_i) * x_i vanishes in ZMod 8.
We instantiate the lemma binary_affine_lift_fourth_difference with constant term 0 and linear coefficients i ↦ L_j(u_i). Simplifying the constant 0 + ∑_i ... to ∑_i ... with zero_add establishes that the fourth alternating difference of this lifted linear form is 0.
uses
binary_affine_lift_fourth_difference,zero_addhave hf := binary_affine_lift_fourth_difference 0 (fun i : Fin 4 => L j (u i)) simp only [zero_add] at hf
For the fixed index j, the alternating sum factors as c_j times the fourth alternating difference of the linear form.
Using Finset.mul_sum, we pull the scalar c_j outside the sum over x. To show the summands match via Finset.sum_congr, we take an arbitrary x and rearrange the terms using commutativity of multiplication (mul_comm) and ring arithmetic (ring).
uses
Finset.mul_sum,Finset.sum_congr,mul_commcalc (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (c j * (((∑ i : Fin 4, x i * L j (u i)).val : ℕ) : ZMod 8))) = c j * (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (((∑ i : Fin 4, L j (u i) * x i).val : ℕ) : ZMod 8)) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x hx simp only [mul_comm] ring
The inner sum for index j evaluates to zero.
Substituting the vanishing of the alternating difference established in hf, the expression reduces to c_j * 0, which is 0 by mul_zero.
uses
mul_zero_ = 0 := by rw [hf, mul_zero]
map_sum- A linear map (or additive homomorphism) preserves finite sums: g(∑_{x ∈ s} f(x)) = ∑_{x ∈ s} g(f(x)).
map_smul- A linear map preserves scalar multiplication: f(c • x) = c • f(x).
smul_eq_mul- In a ring viewed as a module over itself, scalar multiplication coincides with ring multiplication: a • b = a * b.
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑_{i ∈ s} f(i) = ∑_{i ∈ s} a * f(i).
Finset.sum_comm- The order of summation in a double finite sum can be exchanged: ∑_{x ∈ s} ∑_{y ∈ t} f(x, y) = ∑_{y ∈ t} ∑_{x ∈ s} f(x, y).
Finset.sum_eq_zero- A finite sum is zero if every summand is zero.
binary_affine_lift_fourth_difference- The fourth alternating difference over (Z/2)^4 of the integer lift of any affine function x ↦ a + ∑_i l_i x_i evaluates to 0 in Z/8.
zero_add- Zero is the left additive identity: 0 + a = a.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
mul_comm- Multiplication is commutative: a * b = b * a.
mul_zero- Multiplying any ring element by zero on the right gives zero: a * 0 = 0.
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 parity_phase_fourth_difference {V ι : Type*} [AddCommGroup V] [Module (ZMod 2) V] [Fintype ι] (c : ι → ZMod 8) (L : ι → V →ₗ[ZMod 2] ZMod 2) (u : Fin 4 → V) : (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (∑ j : ι, c j * ((L j (∑ i : Fin 4, x i • u i)).val : ZMod 8))) = 0 := by classical simp only [map_sum, map_smul, smul_eq_mul, Finset.mul_sum] rw [Finset.sum_comm] apply Finset.sum_eq_zero intro j hj have hf := binary_affine_lift_fourth_difference 0 (fun i : Fin 4 => L j (u i)) simp only [zero_add] at hf calc (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (c j * (((∑ i : Fin 4, x i * L j (u i)).val : ℕ) : ZMod 8))) = c j * (∑ x : Fin 4 → ZMod 2, (-1 : ZMod 8) ^ (∑ i : Fin 4, (x i).val) * (((∑ i : Fin 4, L j (u i) * x i).val : ℕ) : ZMod 8)) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro x hx simp only [mul_comm] ring _ = 0 := by rw [hf, mul_zero]