cyclic_cubic_parity_repr_pair_sum
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.
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.
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_mulhave 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]
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.
uses
Finset.sum_congr,Finset.sum_ite_mem_eq,Finset.sum_commhave 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]
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.
uses
Finset.sum_congr,Finset.mul_sum,Finset.sum_boolerefine 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]
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.
uses
Finset.mem_filter,Finset.insert_subset_iff,Finset.singleton_subset_iffhave 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]
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}.
uses
Finset.mem_insert_self,Finset.Nonempty.card_pos,Finset.card_insert_le,Finset.card_singletonhave 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
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.
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
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.
/-- 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]