AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_parity_repr_pair_sum

theoremverified

For n ≥ 6 and any distinct pair p ≠ q, the sum ∑_j c_j * s({j, p, q}) vanishes for any affine evaluation on a parity representation.

Statement

theorem cyclic_cubic_parity_repr_pair_sum (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) (c : Fin n → ZMod 2) (b : ZMod 2) (h : ∀ y ∈ S, (∑ j ∈ y, c j) = b) (p q : Fin n) (hpq : p ≠ q) : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = 0
Source
step towards cyclic_cubic_parity_repr_eval_zero
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • cyclic_cubic_parity_repr_orthoEvery parity representation S of cyclic_cubic_syndrome n satisfies ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and ∑_{y ∈ S} ∑_{j ∈ y}…
  • cyclic_cubic_syndromeFor a natural number n and a finite subset A of Fin n, cyclic_cubic_syndrome n A returns 1 in ZMod 2 if there exists j : Fin n such that A…
  • is_parity_reprA finite set S of nonempty parities on n qubits is a parity representation of a syndrome s if the moment of S at every non-empty subset A…
Used by 1
  • cyclic_cubic_parity_repr_eval_zeroFor n ≥ 6, any affine evaluation (∑_{j ∈ y} c_j = b) on all parities y ∈ S of a parity representation S of cyclic_cubic_syndrome n forces…

The proof, explained

The proof evaluates the double sum ∑_{y ∈ S, {p, q} ⊆ y} ∑_{j ∈ y} c_j in two different ways. On one hand, each inner sum is identically b, so the double sum reduces to b times the number of sets in S containing the pair {p, q}, which vanishes modulo 2 by the orthogonality of parity representations on pairs. On the other hand, interchanging the summation order factors the double sum into ∑_j c_j times the number of sets in S containing {j, p, q}, which by definition of a parity representation equals ∑_j c_j * cyclic_cubic_syndrome n {j, p, q}. Equating the two evaluations proves that the syndrome sum is zero.

  1. The double sum ∑_{y ∈ S, {p, q} ⊆ y} ∑_{j ∈ y} c_j evaluates to 0.

    Since the affine evaluation ∑_{j ∈ y} c_j is equal to b for every y ∈ S, replacing the inner sum with b reduces the double sum to |{y ∈ S : {p, q} ⊆ y}| * b in ZMod 2. Because p ≠ q, the pair {p, q} has size 2. By cyclic_cubic_parity_repr_ortho_card_le_two, any subset of size between 1 and 2 is contained in an even number of blocks of S, so this count is 0 in ZMod 2, making the product 0.

    lines 3–14

    uses Finset.sum_congr, Finset.mem_filter, Finset.sum_const, nsmul_eq_mul, Finset.card_pair, cyclic_cubic_parity_repr_ortho_card_le_two, zero_mul

      have h_zero : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) = 0 := by
        have h1 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =
            ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), b := by
          refine Finset.sum_congr rfl (fun y hy => ?_)
          rw [Finset.mem_filter] at hy
          exact h y hy.1
        rw [h1, Finset.sum_const, nsmul_eq_mul]
        have hpq_card : ({p, q} : Finset (Fin n)).card = 2 := Finset.card_pair hpq
        have hcard1 : 1 ≤ ({p, q} : Finset (Fin n)).card := by omega
        have hcard2 : ({p, q} : Finset (Fin n)).card ≤ 2 := by omega
        have hz := cyclic_cubic_parity_repr_ortho_card_le_two n hn S hS {p, q} hcard1 hcard2
        rw [hz, zero_mul]
  2. The double sum can be rewritten by exchanging the summation order: ∑_{y ∈ S, {p, q} ⊆ y} ∑_{j ∈ y} c_j = ∑_{j} ∑_{y ∈ S, {p, q} ⊆ y} (if j ∈ y then c_j else 0).

    Each inner sum over j ∈ y is extended to a sum over all j : Fin n using the indicator (if j ∈ y then c_j else 0) via Finset.sum_ite_mem_eq. Applying Finset.sum_comm then exchanges the order of summation.

    lines 15–21

    uses Finset.sum_congr, Finset.sum_ite_mem_eq, Finset.sum_comm

      have h_swap : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =
          ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} := by
        have h1 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =
            ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j : Fin n, if j ∈ y then c j else 0 := by
          refine Finset.sum_congr rfl (fun y _ => ?_)
          exact (Finset.sum_ite_mem_eq y c).symm
        rw [h1, Finset.sum_comm]
  3. For each fixed j, the inner sum over y equals c_j * |{y ∈ S : {p, q} ⊆ y ∧ j ∈ y}| in ZMod 2.

    Since c_j is independent of y, it factors out using Finset.mul_sum. The remaining sum of indicators (if j ∈ y then 1 else 0) is converted by Finset.sum_boole to the cardinality of the subcollection of sets y containing {p, q} and j.

    lines 22–30

    uses Finset.sum_congr, Finset.mul_sum, Finset.sum_boole

        refine Finset.sum_congr rfl (fun j _ => ?_)
        have h2 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), if j ∈ y then c j else 0) =
            c j * ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), if j ∈ y then (1 : ZMod 2) else 0 := by
          rw [Finset.mul_sum]
          refine Finset.sum_congr rfl (fun y _ => ?_)
          split_ifs <;> ring
        rw [h2]
        congr 1
        rw [Finset.sum_boole]
  4. The subcollection {y ∈ S : {p, q} ⊆ y ∧ j ∈ y} is identically {y ∈ S : {j, p, q} ⊆ y}.

    By set extensionality, an element y contains both {p, q} and j if and only if {j, p, q} ⊆ y, which follows from membership simplification and propositional logic.

    lines 31–36

    uses Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff

        have h_filt : {y ∈ S.filter (fun y => {p, q} ⊆ y) | j ∈ y} =
            S.filter (fun y => {j, p, q} ⊆ y) := by
          ext y
          simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff]
          tauto
        rw [h_filt]
  5. The cardinality |{y ∈ S : {j, p, q} ⊆ y}| in ZMod 2 equals cyclic_cubic_syndrome n {j, p, q}, establishing h_swap.

    The set {j, p, q} has size at least 1 (as it contains j) and at most 3 (by adding elements one by one). Since 1 ≤ |{j, p, q}| ≤ 3, the definition of the parity representation hS ensures that the number of sets in S containing {j, p, q} modulo 2 is precisely cyclic_cubic_syndrome n {j, p, q}.

    lines 37–46

    uses Finset.mem_insert_self, Finset.Nonempty.card_pos, Finset.card_insert_le, Finset.card_singleton

        have hcard1 : 1 ≤ ({j, p, q} : Finset (Fin n)).card := by
          have : ({j, p, q} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩
          exact Finset.Nonempty.card_pos this
        have hcard2 : ({j, p, q} : Finset (Fin n)).card ≤ 3 := by
          have h1 := Finset.card_insert_le j {p, q}
          have h2 := Finset.card_insert_le p {q}
          rw [Finset.card_singleton] at h2
          omega
        have h_repr := hS.2 {j, p, q} ⟨hcard1, hcard2⟩
        exact h_repr
  6. The sum ∑_{j : Fin n} c_j * cyclic_cubic_syndrome n {j, p, q} is 0.

    Rewriting with h_swap and h_zero shows that the target sum equals the double sum, which is 0.

    line 47

      rw [← h_swap, h_zero]
Finset.sum_congr
If two index sets are equal and two functions agree on the index set, their sums are equal.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.sum_const
Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
nsmul_eq_mul
Scalar multiplication by a natural number equals multiplication by the natural number cast into the ring.
Finset.card_pair
For two distinct elements a ≠ b, the unordered pair {a, b} has cardinality 2.
cyclic_cubic_parity_repr_ortho_card_le_two
For n ≥ 6 and a parity representation S, any subset of size 1 or 2 is contained in an even number of elements of S (its count modulo 2 is 0).
zero_mul
Zero times anything is zero.
Finset.sum_ite_mem_eq
Summing an indicator function over the universal set equals the sum of the function restricted to the specified subset.
Finset.sum_comm
The order of two finite summations can be exchanged (Fubini's theorem for finite sums).
Finset.mul_sum
Multiplication distributes over a finite sum, so a constant factor can be factored out.
Finset.sum_boole
Summing a boolean indicator (1 if true, 0 if false) over a finite set yields the cardinality of the satisfying subset.
Finset.insert_subset_iff
An inserted set insert(a, s) is a subset of t if and only if a ∈ t and s ⊆ t.
Finset.singleton_subset_iff
A singleton {a} is a subset of s if and only if a ∈ s.
Finset.mem_insert_self
An element a is always an element of insert(a, s).
Finset.Nonempty.card_pos
A nonempty finite set has strictly positive cardinality.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_singleton
A singleton set has cardinality 1.

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

/-- For n ≥ 6 and any distinct pair p ≠ q, summing c_j * cyclic_cubic_syndrome n {j, p, q} over j gives 0. -/theorem cyclic_cubic_parity_repr_pair_sum (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) (c : Fin n → ZMod 2) (b : ZMod 2) (h : ∀ y ∈ S, (∑ j ∈ y, c j) = b) (p q : Fin n) (hpq : p ≠ q) : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = 0 := by  have h_zero : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) = 0 := by    have h1 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =        ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), b := by      refine Finset.sum_congr rfl (fun y hy => ?_)      rw [Finset.mem_filter] at hy      exact h y hy.1    rw [h1, Finset.sum_const, nsmul_eq_mul]    have hpq_card : ({p, q} : Finset (Fin n)).card = 2 := Finset.card_pair hpq    have hcard1 : 1 ≤ ({p, q} : Finset (Fin n)).card := by omega    have hcard2 : ({p, q} : Finset (Fin n)).card ≤ 2 := by omega    have hz := cyclic_cubic_parity_repr_ortho_card_le_two n hn S hS {p, q} hcard1 hcard2    rw [hz, zero_mul]  have h_swap : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =      ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} := by    have h1 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j ∈ y, c j) =        ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), ∑ j : Fin n, if j ∈ y then c j else 0 := by      refine Finset.sum_congr rfl (fun y _ => ?_)      exact (Finset.sum_ite_mem_eq y c).symm    rw [h1, Finset.sum_comm]    refine Finset.sum_congr rfl (fun j _ => ?_)    have h2 : (∑ y ∈ S.filter (fun y => {p, q} ⊆ y), if j ∈ y then c j else 0) =        c j * ∑ y ∈ S.filter (fun y => {p, q} ⊆ y), if j ∈ y then (1 : ZMod 2) else 0 := by      rw [Finset.mul_sum]      refine Finset.sum_congr rfl (fun y _ => ?_)      split_ifs <;> ring    rw [h2]    congr 1    rw [Finset.sum_boole]    have h_filt : {y ∈ S.filter (fun y => {p, q} ⊆ y) | j ∈ y} =        S.filter (fun y => {j, p, q} ⊆ y) := by      ext y      simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff]      tauto    rw [h_filt]    have hcard1 : 1 ≤ ({j, p, q} : Finset (Fin n)).card := by      have : ({j, p, q} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩      exact Finset.Nonempty.card_pos this    have hcard2 : ({j, p, q} : Finset (Fin n)).card ≤ 3 := by      have h1 := Finset.card_insert_le j {p, q}      have h2 := Finset.card_insert_le p {q}      rw [Finset.card_singleton] at h2      omega    have h_repr := hS.2 {j, p, q} ⟨hcard1, hcard2⟩    exact h_repr  rw [← h_swap, h_zero]
See it in the graphDiscuss this resultChallenge it