cyclic_cubic_parity_repr_eval_zero
For 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 c = 0.
Statement
theorem cyclic_cubic_parity_repr_eval_zero (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) : c = 0- Source
- step towards cyclic_cubic_t_count_isotropy_lower_bound
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- 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…
- cyclic_cubic_distinct_neighborsFor n ≥ 6 and any x : Fin n, the cyclic neighbors (x - 1) % n and (x + 1) % n are distinct.
- cyclic_cubic_parity_repr_pair_sumFor 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.
- cyclic_cubic_syndrome_isolatedFor n ≥ 6 and any x : Fin n, the cyclic cubic syndrome of {j, (x-1)%n, (x+1)%n} is 0 for all j ≠ x.
- Used by 1
- cyclic_cubic_t_count_isotropy_lower_boundFor every natural number n ≥ 6 and every finite set S : Finset (Finset (Fin n)), if is_parity_repr S (cyclic_cubic_syndrome n), then 2 * n…
The proof, explained
To show that c = 0, we prove that c(x) = 0 for an arbitrary x ∈ Fin n. We consider the cyclic neighbors p = x - 1 and q = x + 1 (mod n), which are distinct because n ≥ 6. An orthogonality relation for parity representations ensures that the sum ∑_j c_j * syndrome({j, p, q}) vanishes. Because no other index j ≠ x can form a consecutive cyclic triple with p and q, the sum collapses to the single term c(x) * syndrome({x, p, q}) = c(x) * 1 = 0, forcing c(x) = 0.
To evaluate the syndrome of {x, x - 1, x + 1} as 1, it suffices to show it equals a consecutive cyclic triple {j, j + 1, j + 2} with j = x - 1 (mod n).
By definition, cyclic_cubic_syndrome n A is 1 when A is of the form {j, j + 1, j + 2} mod n for some index j, and 0 otherwise. Unfolding the definition and rewriting with if_pos reduces the goal to providing a witness j; choosing j = (x - 1) % n leaves the equality of sets {x, x - 1, x + 1} = {j, j + 1, j + 2} to be verified.
uses
if_posprivate theorem cyclic_cubic_parity_repr_eval_zero_syndrome_one (n : ℕ) (hn : 6 ≤ n) (x : Fin n) : cyclic_cubic_syndrome n {x, (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)} = 1 := by unfold cyclic_cubic_syndrome rw [if_pos] refine ⟨⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩, ?_⟩
The index (j + 1) mod n equals x.
By extensionality on Fin n, we compare the underlying natural numbers. Using Nat.mod_add_mod, ((x + n - 1) % n + 1) % n rewrites to (x + n - 1 + 1) % n = (x + n) % n. Dropping the multiple of n with Nat.add_mod_right leaves x % n, which equals x since x < n.
uses
Fin.ext,Nat.mod_add_mod,Nat.add_mod_right,Nat.mod_eq_of_lthave hA : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = x := by apply Fin.ext simp only have h1 : ((x.val + n - 1) % n + 1) % n = (x.val + n - 1 + 1) % n := Nat.mod_add_mod _ _ _ rw [h1] have h2 : x.val + n - 1 + 1 = x.val + n := by omega rw [h2, Nat.add_mod_right, Nat.mod_eq_of_lt x.isLt]
The index (j + 2) mod n equals (x + 1) mod n.
Similarly, comparing values via Fin.ext, ((x + n - 1) % n + 2) % n rewrites by Nat.mod_add_mod to (x + n - 1 + 2) % n = ((x + 1) + n) % n, which simplifies to (x + 1) % n by Nat.add_mod_right.
uses
Fin.ext,Nat.mod_add_mod,Nat.add_mod_righthave hB : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) := by apply Fin.ext simp only have h1 : ((x.val + n - 1) % n + 2) % n = (x.val + n - 1 + 2) % n := Nat.mod_add_mod _ _ _ rw [h1] have h2 : x.val + n - 1 + 2 = (x.val + 1) + n := by omega rw [h2, Nat.add_mod_right]
The syndrome of {x, x - 1, x + 1} is 1.
Substituting the verified identities j + 1 = x and j + 2 = x + 1 turns {j, j + 1, j + 2} into {x - 1, x, x + 1}. Commuting the insertion of elements via Finset.insert_comm shows this equals {x, x - 1, x + 1}, completing the helper lemma.
uses
Finset.insert_commsimp only [hA, hB] exact Finset.insert_comm _ _ _
To prove c = 0, let x ∈ Fin n be arbitrary and let p = x - 1 and q = x + 1 be its cyclic neighbors; then p ≠ q.
By function extensionality, it suffices to prove c x = 0 for an arbitrary x. We set p = (x - 1) % n and q = (x + 1) % n. Because n ≥ 6, these two cyclic neighbors are distinct by cyclic_cubic_distinct_neighbors.
uses
cyclic_cubic_distinct_neighbors/-- For 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 c = 0. -/ theorem cyclic_cubic_parity_repr_eval_zero (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) : c = 0 := by funext x set p : Fin n := ⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ with hp set q : Fin n := ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ with hq have hpq : p ≠ q := by simpa only [hp, hq] using cyclic_cubic_distinct_neighbors n hn x
The sum ∑_j c_j * syndrome({j, p, q}) reduces to the single term c_x * syndrome({x, p, q}).
We apply Fintype.sum_eq_single to isolate the index x. For any j ≠ x, the set {j, p, q} cannot form three consecutive cyclic elements when n ≥ 6, so its syndrome is 0 by cyclic_cubic_syndrome_isolated. Each term for j ≠ x thus vanishes by mul_zero.
uses
Fintype.sum_eq_single,cyclic_cubic_syndrome_isolated,mul_zerohave hsingle : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = c x * cyclic_cubic_syndrome n {x, p, q} := by apply Fintype.sum_eq_single x intro j hjx rw [show cyclic_cubic_syndrome n {j, p, q} = 0 from by simpa only [hp, hq] using cyclic_cubic_syndrome_isolated n hn x j hjx] rw [mul_zero]
c x = 0, completing the proof that c = 0.
By cyclic_cubic_parity_repr_pair_sum, the sum ∑_j c_j * syndrome({j, p, q}) equals 0. Replacing the sum with its isolated term gives c_x * syndrome({x, p, q}) = 0. The helper lemma shows syndrome({x, p, q}) = 1, so this simplifies via mul_one to c_x = 0. Since x was arbitrary, c = 0.
uses
cyclic_cubic_parity_repr_pair_sum,cyclic_cubic_parity_repr_eval_zero_syndrome_one,mul_onehave hsum := cyclic_cubic_parity_repr_pair_sum n hn S hS c b h p q hpq rw [hsingle] at hsum have hsy : cyclic_cubic_syndrome n {x, p, q} = 1 := by simpa only [hp, hq] using cyclic_cubic_parity_repr_eval_zero_syndrome_one n hn x rw [hsy, mul_one] at hsum exact hsum
if_pos- If a condition c holds, then the conditional if c then t else e evaluates to t.
Fin.ext- Two elements of Fin n are equal if their underlying natural numbers are equal.
Nat.mod_add_mod- For natural numbers, ((m % n) + k) % n = (m + k) % n.
Nat.add_mod_right- Adding a multiple of the modulus does not change the remainder: (x + z) % z = x % z.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Finset.insert_comm- Inserting two elements into a finite set is commutative: {a, b} ∪ s = {b, a} ∪ s.
cyclic_cubic_distinct_neighbors- For n ≥ 6, the cyclic neighbors (x - 1) % n and (x + 1) % n of any x are distinct.
Fintype.sum_eq_single- A sum over a finite type reduces to the single term at a if all other terms vanish.
cyclic_cubic_syndrome_isolated- For n ≥ 6 and j ≠ x, the cyclic cubic syndrome of {j, (x - 1) % n, (x + 1) % n} is zero.
mul_zero- Multiplying any element by zero yields zero.
cyclic_cubic_parity_repr_pair_sum- For any parity representation S of cyclic_cubic_syndrome n and any pair p ≠ q, the weighted sum ∑_j c_j * syndrome({j, p, q}) is zero.
cyclic_cubic_parity_repr_eval_zero_syndrome_one- For n ≥ 6, the cyclic cubic syndrome on {x, (x - 1) % n, (x + 1) % n} is 1.
mul_one- Multiplying any element by one yields that element.
- The helper lemma cyclic_cubic_parity_repr_eval_zero_syndrome_one performs explicit modular arithmetic to verify that the set {x, x - 1, x + 1} mod n equals the consecutive cyclic triple {x - 1, x, x + 1}; on paper this cyclic reindexing is immediate.
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.
private theorem cyclic_cubic_parity_repr_eval_zero_syndrome_one (n : ℕ) (hn : 6 ≤ n) (x : Fin n) : cyclic_cubic_syndrome n {x, (⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n), (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)} = 1 := by unfold cyclic_cubic_syndrome rw [if_pos] refine ⟨⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩, ?_⟩ have hA : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = x := by apply Fin.ext simp only have h1 : ((x.val + n - 1) % n + 1) % n = (x.val + n - 1 + 1) % n := Nat.mod_add_mod _ _ _ rw [h1] have h2 : x.val + n - 1 + 1 = x.val + n := by omega rw [h2, Nat.add_mod_right, Nat.mod_eq_of_lt x.isLt] have hB : ((⟨(((⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)).val + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n)) = (⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) := by apply Fin.ext simp only have h1 : ((x.val + n - 1) % n + 2) % n = (x.val + n - 1 + 2) % n := Nat.mod_add_mod _ _ _ rw [h1] have h2 : x.val + n - 1 + 2 = (x.val + 1) + n := by omega rw [h2, Nat.add_mod_right] simp only [hA, hB] exact Finset.insert_comm _ _ _/-- For 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 c = 0. -/theorem cyclic_cubic_parity_repr_eval_zero (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) : c = 0 := by funext x set p : Fin n := ⟨(x.val + n - 1) % n, Nat.mod_lt _ (by omega)⟩ with hp set q : Fin n := ⟨(x.val + 1) % n, Nat.mod_lt _ (by omega)⟩ with hq have hpq : p ≠ q := by simpa only [hp, hq] using cyclic_cubic_distinct_neighbors n hn x have hsingle : ∑ j : Fin n, c j * cyclic_cubic_syndrome n {j, p, q} = c x * cyclic_cubic_syndrome n {x, p, q} := by apply Fintype.sum_eq_single x intro j hjx rw [show cyclic_cubic_syndrome n {j, p, q} = 0 from by simpa only [hp, hq] using cyclic_cubic_syndrome_isolated n hn x j hjx] rw [mul_zero] have hsum := cyclic_cubic_parity_repr_pair_sum n hn S hS c b h p q hpq rw [hsingle] at hsum have hsy : cyclic_cubic_syndrome n {x, p, q} = 1 := by simpa only [hp, hq] using cyclic_cubic_parity_repr_eval_zero_syndrome_one n hn x rw [hsy, mul_one] at hsum exact hsum