line_cubic_parity_repr_ortho
Every parity representation S of line_syndrome n satisfies ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and ∑_{y ∈ S} ∑_{j ∈ y} c_j = 0, because singletons and pairs have syndrome 0.
Statement
theorem line_cubic_parity_repr_ortho (n : ℕ)
(S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n))
(c d : Fin n → ZMod 2) :
(∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) = 0) ∧
(∑ y ∈ S, (∑ j ∈ y, c j) = 0)- Source
- step towards line_cubic_t_count_lower_bound
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- line_syndromeThe syndrome of the line cubic form assigns 1 to adjacent triples {i, i+1, i+2} and 0 to all other subsets of Fin n.
- Used by 1
- line_cubic_t_count_lower_boundFor any n ≥ 5, every parity representation of the line cubic syndrome has cardinality at least 2n + 1.
The proof, explained
The theorem proves that any parity representation S of line_syndrome n satisfies bilinear orthogonality ∑_{y ∈ S} (∑_{j ∈ y} c_j)(∑_{k ∈ y} d_k) = 0 and linear orthogonality ∑_{y ∈ S} ∑_{j ∈ y} c_j = 0 over ZMod 2. The argument first establishes a lemma: singletons and pairs have count 0 modulo 2 because line_syndrome is supported only on 3-element line segments {i, i+1, i+2}. For the main theorem, exchanging summation orders rewrites the bilinear sum as a linear combination of parity counts of supersets of pairs {j, k}, and rewrites the linear sum as a combination of parity counts of supersets of singletons {j}. Since {j, k} and {j} have cardinality at most 2, every term vanishes by the lemma.
For any subset A with 1 ≤ |A| ≤ 2, the count modulo 2 of sets in S containing A reduces to showing that A cannot be a 3-element line segment {i, i+1, i+2}.
Since |A| ≤ 2, we have |A| ≤ 3, so the parity representation hypothesis equates the count modulo 2 of supersets of A to line_syndrome n A. By definition, line_syndrome n A is 1 if A = {i, i+1, i+2} for some index i, and 0 otherwise. In the latter case the count is immediately 0; in the former case, we obtain such an index i and must derive a contradiction to rule it out.
have hA3 : A.card ≤ 3 := by omega have hrepr := hS.2 A ⟨hA1, hA3⟩ rw [hrepr] unfold line_syndrome split_ifs with h · rcases h with ⟨i, hi⟩
A subset A with |A| ≤ 2 cannot be a 3-element line segment, so its count modulo 2 of supersets in S is zero.
The three elements i, i+1, and i+2 in Fin n are strictly increasing and therefore pairwise distinct. By inserting elements one by one (`Finset.card_insert_of_notMem`, `Finset.card_singleton`, `Finset.mem_singleton`, `Finset.mem_insert`), the cardinality of {i, i+1, i+2} is 3. By `congr_arg`, A = {i, i+1, i+2} implies |A| = 3, which contradicts the assumption |A| ≤ 2. The remaining case where A is not a 3-element segment evaluates to 0 directly by reflexivity (`rfl`).
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.mem_singleton,Finset.mem_insert,congr_arghave hc : ({⟨i.val, by omega⟩, ⟨i.val + 1, by omega⟩, ⟨i.val + 2, by omega⟩} : Finset (Fin n)).card = 3 := by let a : Fin n := ⟨i.val, by omega⟩ let b : Fin n := ⟨i.val + 1, by omega⟩ let c : Fin n := ⟨i.val + 2, by omega⟩ change ({a, b, c} : Finset (Fin n)).card = 3 have hab : a ≠ b := by intro h; injection h with h; omega have hac : a ≠ c := by intro h; injection h with h; omega have hbc : b ≠ c := by intro h; injection h with h; omega rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · intro h; simp only [Finset.mem_singleton] at h; exact hbc h · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h) · exact hab h · exact hac h have h_card_eq := congr_arg Finset.card hi omega · rfl
It suffices to prove that for each pair of indices j and k, the sum ∑_{y ∈ S} (if j ∈ y then c_j else 0) * (if k ∈ y then d_k else 0) is zero.
We split the conjunction with `constructor`. For the bilinear sum, we rewrite the restricted sums over y as unrestricted sums over all elements of Fin n using indicator functions (`Finset.sum_ite_mem_eq`) and expand their product into a double sum over j and k via `Finset.sum_mul_sum`. Exchanging the order of summation (`Finset.sum_comm`), it suffices by `Finset.sum_eq_zero` to show that the inner sum over y vanishes for each fixed j and k.
uses
Finset.sum_congr,Finset.sum_ite_mem_eq,Finset.sum_mul_sum,Finset.sum_comm,Finset.sum_eq_zeroconstructor · have h1 : (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) = ∑ y ∈ S, ∑ j : Fin n, ∑ k : Fin n, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0) := by refine Finset.sum_congr rfl (fun y _ => ?_) rw [← Finset.sum_ite_mem_eq y c, ← Finset.sum_ite_mem_eq y d] rw [Finset.sum_mul_sum] rw [h1, Finset.sum_comm] refine Finset.sum_eq_zero (fun j _ => ?_) rw [Finset.sum_comm] refine Finset.sum_eq_zero (fun k _ => ?_)
For fixed j and k, the sum over y ∈ S equals (c_j * d_k) times the cardinality modulo 2 of the sets y ∈ S containing {j, k}.
The product of indicators (if j ∈ y then c_j else 0) * (if k ∈ y then d_k else 0) is c_j * d_k when both j ∈ y and k ∈ y, and 0 otherwise. Factoring out c_j * d_k (`Finset.mul_sum`), the remaining sum of booleans equals the cardinality modulo 2 of {x ∈ S | j ∈ x ∧ k ∈ x} by `Finset.sum_boole`. We rewrite this set as the filter of sets y ∈ S such that {j, k} ⊆ y (`Finset.mem_filter`, `Finset.insert_subset_iff`, `Finset.singleton_subset_iff`).
uses
Finset.mul_sum,Finset.sum_congr,Finset.sum_boole,Finset.mem_filter,Finset.insert_subset_iff,Finset.singleton_subset_iffhave h_split : (∑ y ∈ S, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0)) = (c j * d k) * ∑ y ∈ S, (if j ∈ y ∧ k ∈ y then (1 : ZMod 2) else 0) := by rw [Finset.mul_sum] refine Finset.sum_congr rfl (fun y _ => ?_) by_cases hj : j ∈ y <;> by_cases hk : k ∈ y <;> simp [hj, hk] rw [h_split, Finset.sum_boole] have h_filt : {x ∈ S | j ∈ x ∧ k ∈ x} = S.filter (fun y => {j, k} ⊆ y) := by ext y simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff] rw [h_filt]
Each (j, k) term vanishes, completing the proof of the bilinear identity.
The set {j, k} is nonempty (`Finset.mem_insert_self`), so its cardinality is at least 1 (`Finset.Nonempty.card_pos`). Furthermore, |{j, k}| ≤ |{k}| + 1 = 2 by `Finset.card_insert_le` and `Finset.card_singleton`. By `line_cubic_parity_repr_ortho_card_le_two`, the number of elements of S containing {j, k} is 0 in ZMod 2. Multiplying by c_j * d_k yields 0 (`mul_zero`).
uses
Finset.mem_insert_self,Finset.Nonempty.card_pos,Finset.card_insert_le,Finset.card_singleton,line_cubic_parity_repr_ortho_card_le_two,mul_zerohave hne : ({j, k} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩ have hcard1 : 1 ≤ ({j, k} : Finset (Fin n)).card := Finset.Nonempty.card_pos hne have hcard2 : ({j, k} : Finset (Fin n)).card ≤ 2 := by have := Finset.card_insert_le j {k} rw [Finset.card_singleton] at this omega have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j, k} hcard1 hcard2 rw [h_zero, mul_zero]
It suffices to show that for each index j, the sum ∑_{y ∈ S} (if j ∈ y then c_j else 0) is zero.
For the second conjunct, we rewrite ∑_{j ∈ y} c_j as the unrestricted sum ∑_{j} (if j ∈ y then c_j else 0) using `Finset.sum_ite_mem_eq`. Exchanging the summation order (`Finset.sum_comm`), it suffices by `Finset.sum_eq_zero` to show that the sum over y ∈ S vanishes for each fixed index j.
uses
Finset.sum_congr,Finset.sum_ite_mem_eq,Finset.sum_comm,Finset.sum_eq_zero· have h1 : (∑ y ∈ S, ∑ j ∈ y, c j) = ∑ y ∈ S, ∑ 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_eq_zero (fun j _ => ?_)
For fixed j, the sum over y ∈ S equals c_j times the cardinality modulo 2 of the sets y ∈ S containing {j}.
Factoring c_j out of the sum (`Finset.mul_sum`), the remaining sum over y ∈ S of the indicator for j ∈ y evaluates to the cardinality of {x ∈ S | j ∈ x} modulo 2 by `Finset.sum_boole`. The membership condition j ∈ y is equivalent to {j} ⊆ y (`Finset.mem_filter`, `Finset.singleton_subset_iff`).
uses
Finset.mul_sum,Finset.sum_congr,Finset.sum_boole,Finset.mem_filter,Finset.singleton_subset_iffhave h_split : (∑ y ∈ S, if j ∈ y then c j else 0) = c j * ∑ y ∈ S, (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 [h_split, Finset.sum_boole] have h_filt : {x ∈ S | j ∈ x} = S.filter (fun y => {j} ⊆ y) := by ext y simp only [Finset.mem_filter, Finset.singleton_subset_iff] rw [h_filt]
Each j term vanishes, completing the proof of linear orthogonality.
The singleton {j} has cardinality 1 (`Finset.card_singleton`), which satisfies 1 ≤ |{j}| ≤ 2. Applying `line_cubic_parity_repr_ortho_card_le_two` gives that the number of elements in S containing {j} is 0 in ZMod 2. Multiplying by c_j gives 0 (`mul_zero`).
uses
Finset.card_singleton,line_cubic_parity_repr_ortho_card_le_two,mul_zerohave hcard1 : 1 ≤ ({j} : Finset (Fin n)).card := by rw [Finset.card_singleton] have hcard2 : ({j} : Finset (Fin n)).card ≤ 2 := by rw [Finset.card_singleton]; omega have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j} hcard1 hcard2 rw [h_zero, mul_zero]
congr_arg- Applying a function to equal arguments yields equal results.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_insert_of_notMem- Inserting an element not already in a finite set increases its cardinality by 1.
Finset.card_singleton- The cardinality of any singleton set {a} is 1.
Finset.insert_subset_iff- The set insert a s is a subset of t if and only if a ∈ t and s ⊆ t.
Finset.mem_filter- An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_insert- An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_insert_self- An element a belongs to insert a s.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
Finset.mul_sum- A factor distributes into a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
Finset.Nonempty.card_pos- A nonempty finite set has strictly positive cardinality.
Finset.singleton_subset_iff- The singleton {a} is a subset of s if and only if a ∈ s.
Finset.sum_boole- The sum of a boolean indicator over a finite set equals the cardinality of the subset satisfying the predicate, cast into the ring.
Finset.sum_comm- The order of summation in a double finite sum can be exchanged.
Finset.sum_congr- Two sums over equal sets are equal if their terms agree on that set.
Finset.sum_eq_zero- A finite sum is zero if every summand is zero.
Finset.sum_ite_mem_eq- Summing an indicator-weighted term over all elements is equal to summing the term over the subset where the indicator holds.
Finset.sum_mul_sum- The product of two sums equals the double sum of the pairwise products of their terms.
line_cubic_parity_repr_ortho_card_le_two- For any parity representation S of line_syndrome n and any subset A with 1 ≤ |A| ≤ 2, the number of sets in S containing A is 0 modulo 2.
mul_zero- Multiplying any element by zero yields zero.
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.
lemma line_cubic_parity_repr_ortho_card_le_two (n : ℕ) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n)) (A : Finset (Fin n)) (hA1 : 1 ≤ A.card) (hA2 : A.card ≤ 2) : ((S.filter (fun y => A ⊆ y)).card : ZMod 2) = 0 := by have hA3 : A.card ≤ 3 := by omega have hrepr := hS.2 A ⟨hA1, hA3⟩ rw [hrepr] unfold line_syndrome split_ifs with h · rcases h with ⟨i, hi⟩ have hc : ({⟨i.val, by omega⟩, ⟨i.val + 1, by omega⟩, ⟨i.val + 2, by omega⟩} : Finset (Fin n)).card = 3 := by let a : Fin n := ⟨i.val, by omega⟩ let b : Fin n := ⟨i.val + 1, by omega⟩ let c : Fin n := ⟨i.val + 2, by omega⟩ change ({a, b, c} : Finset (Fin n)).card = 3 have hab : a ≠ b := by intro h; injection h with h; omega have hac : a ≠ c := by intro h; injection h with h; omega have hbc : b ≠ c := by intro h; injection h with h; omega rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton] · intro h; simp only [Finset.mem_singleton] at h; exact hbc h · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h) · exact hab h · exact hac h have h_card_eq := congr_arg Finset.card hi omega · rfl/-- Every parity representation of the line cubic syndrome satisfies bilinear self-orthogonality and linear orthogonality to the all-ones vector. -/theorem line_cubic_parity_repr_ortho (n : ℕ) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n)) (c d : Fin n → ZMod 2) : (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k) = 0) ∧ (∑ y ∈ S, (∑ j ∈ y, c j) = 0) := by constructor · have h1 : (∑ y ∈ S, (∑ j ∈ y, c j) * (∑ k ∈ y, d k)) = ∑ y ∈ S, ∑ j : Fin n, ∑ k : Fin n, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0) := by refine Finset.sum_congr rfl (fun y _ => ?_) rw [← Finset.sum_ite_mem_eq y c, ← Finset.sum_ite_mem_eq y d] rw [Finset.sum_mul_sum] rw [h1, Finset.sum_comm] refine Finset.sum_eq_zero (fun j _ => ?_) rw [Finset.sum_comm] refine Finset.sum_eq_zero (fun k _ => ?_) have h_split : (∑ y ∈ S, (if j ∈ y then c j else 0) * (if k ∈ y then d k else 0)) = (c j * d k) * ∑ y ∈ S, (if j ∈ y ∧ k ∈ y then (1 : ZMod 2) else 0) := by rw [Finset.mul_sum] refine Finset.sum_congr rfl (fun y _ => ?_) by_cases hj : j ∈ y <;> by_cases hk : k ∈ y <;> simp [hj, hk] rw [h_split, Finset.sum_boole] have h_filt : {x ∈ S | j ∈ x ∧ k ∈ x} = S.filter (fun y => {j, k} ⊆ y) := by ext y simp only [Finset.mem_filter, Finset.insert_subset_iff, Finset.singleton_subset_iff] rw [h_filt] have hne : ({j, k} : Finset (Fin n)).Nonempty := ⟨j, Finset.mem_insert_self j _⟩ have hcard1 : 1 ≤ ({j, k} : Finset (Fin n)).card := Finset.Nonempty.card_pos hne have hcard2 : ({j, k} : Finset (Fin n)).card ≤ 2 := by have := Finset.card_insert_le j {k} rw [Finset.card_singleton] at this omega have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j, k} hcard1 hcard2 rw [h_zero, mul_zero] · have h1 : (∑ y ∈ S, ∑ j ∈ y, c j) = ∑ y ∈ S, ∑ 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_eq_zero (fun j _ => ?_) have h_split : (∑ y ∈ S, if j ∈ y then c j else 0) = c j * ∑ y ∈ S, (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 [h_split, Finset.sum_boole] have h_filt : {x ∈ S | j ∈ x} = S.filter (fun y => {j} ⊆ y) := by ext y simp only [Finset.mem_filter, Finset.singleton_subset_iff] rw [h_filt] have hcard1 : 1 ≤ ({j} : Finset (Fin n)).card := by rw [Finset.card_singleton] have hcard2 : ({j} : Finset (Fin n)).card ≤ 2 := by rw [Finset.card_singleton]; omega have h_zero := line_cubic_parity_repr_ortho_card_le_two n S hS {j} hcard1 hcard2 rw [h_zero, mul_zero]