AFTD Auto-Formalizing Theoretical Domains

parity_phase_fourth_difference

theoremverified

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
Used by 1

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.

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

    lines 8–10

    uses map_sum, map_smul, smul_eq_mul, Finset.mul_sum, Finset.sum_comm

      classical
      simp only [map_sum, map_smul, smul_eq_mul, Finset.mul_sum]
      rw [Finset.sum_comm]
  2. 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 ∈ ι.

    lines 11–12

    uses Finset.sum_eq_zero

      apply Finset.sum_eq_zero
      intro j hj
  3. 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.

    lines 13–15

    uses binary_affine_lift_fourth_difference, zero_add

      have hf := binary_affine_lift_fourth_difference 0
        (fun i : Fin 4 => L j (u i))
      simp only [zero_add] at hf
  4. 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).

    lines 16–27

    uses Finset.mul_sum, Finset.sum_congr, mul_comm

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

    line 28

    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

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