cyclic_cubic_parity_repr_nonempty
Every parity representation S of cyclic_cubic_syndrome n for n ≥ 6 is nonempty, because cyclic_cubic_syndrome n {0, 1, 2} = 1.
Statement
theorem cyclic_cubic_parity_repr_nonempty (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) : S.Nonempty- Source
- step towards cyclic_cubic_t_count_isotropy_lower_bound
- Verified
- 30 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…
- 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…
- 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
The proof proceeds by contradiction. For n ≥ 6, it considers the subset A = {0, 1, 2} ⊆ Fin n, which has cardinality 3 and matches the form of a cyclic consecutive triple, so its cyclic cubic syndrome equals 1. By the definition of a parity representation, the number of sets in S containing A must be odd (congruent to 1 modulo 2). If S were empty, this count would be 0, yielding 0 = 1 in ZMod 2, a contradiction.
The set A = {0, 1, 2} ⊆ Fin n is well-defined and has cardinality 3.
Since n ≥ 6, the elements 0, 1, and 2 are strictly less than n and define valid elements of Fin n. Equating coordinates shows they are pairwise distinct. Applying Finset.card_insert_of_notMem twice and Finset.card_singleton once computes the cardinality of {0, 1, 2} to be 3.
uses
Finset.card_insert_of_notMem,Finset.card_singleton,Finset.mem_singleton,Finset.mem_insertlet A : Finset (Fin n) := {⟨0, by omega⟩, ⟨1, by omega⟩, ⟨2, by omega⟩} have hA_card : A.card = 3 := by have h01 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by intro h; injection h with h; omega have h02 : (⟨0, by omega⟩ : Fin n) ≠ ⟨2, by omega⟩ := by intro h; injection h with h; omega have h12 : (⟨1, by omega⟩ : Fin n) ≠ ⟨2, by omega⟩ := 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 h12 h · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h) · exact h01 h · exact h02 h
The cyclic cubic syndrome evaluates to 1 on A: cyclic_cubic_syndrome n A = 1.
By definition, cyclic_cubic_syndrome n A equals 1 when A is of the form {j, (j+1) % n, (j+2) % n} for some j ∈ Fin n. Choosing j = 0, the remainders (0 + 1) % n and (0 + 2) % n simplify to 1 and 2 because 1 < n and 2 < n (via Nat.mod_eq_of_lt). Thus A matches the required cyclic triple, and if_pos establishes that the syndrome is 1.
uses
Nat.mod_lt,Finset.mem_insert,Finset.mem_singleton,Nat.mod_eq_of_lt,if_poshave h_syn : cyclic_cubic_syndrome n A = 1 := by unfold cyclic_cubic_syndrome have h : ∃ j : Fin n, have hn_pos : 0 < n := by have := j.isLt; omega A = {j, ⟨(j.val + 1) % n, Nat.mod_lt _ hn_pos⟩, ⟨(j.val + 2) % n, Nat.mod_lt _ hn_pos⟩} := by refine ⟨⟨0, by omega⟩, ?_⟩ dsimp [A] ext x simp only [Finset.mem_insert, Finset.mem_singleton] have h1 : (⟨(0 + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) = ⟨1, by omega⟩ := by ext; simp [Nat.mod_eq_of_lt (by omega : 1 < n)] have h2 : (⟨(0 + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) = ⟨2, by omega⟩ := by ext; simp [Nat.mod_eq_of_lt (by omega : 2 < n)] rw [h1, h2] exact if_pos h
Modulo 2, the number of sets in S that contain A is 1.
Since S is a parity representation of the syndrome and 1 ≤ |A| ≤ 3 (as |A| = 3), the definition of is_parity_repr implies that the number of elements in S containing A, considered in ZMod 2, equals cyclic_cubic_syndrome n A. Substituting the value 1 from the previous step gives |{y ∈ S | A ⊆ y}| ≡ 1 (mod 2).
have h_repr := hS.2 A ⟨by omega, by omega⟩ rw [h_syn] at h_repr
S is nonempty.
Assume for contradiction that S is empty. Then the subset of elements in S containing A is also empty (by Finset.filter_empty), so its cardinality is 0 (by Finset.card_empty). This forces 0 ≡ 1 (mod 2), an immediate contradiction.
uses
Finset.not_nonempty_iff_eq_empty,Finset.filter_empty,Finset.card_emptyby_contra h_empty rw [Finset.not_nonempty_iff_eq_empty] at h_empty have h_sub_empty : {y ∈ S | A ⊆ y} = ∅ := by rw [h_empty] exact Finset.filter_empty _ rw [h_sub_empty, Finset.card_empty] at h_repr revert h_repr decide
Finset.card_insert_of_notMem- For a finite set s and an element a ∉ s, the cardinality of {a} ∪ s is |s| + 1.
Finset.card_singleton- The cardinality of a singleton set {a} is 1.
Finset.mem_singleton- An element b belongs to {a} if and only if b = a.
Finset.mem_insert- An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Nat.mod_lt- For y > 0, the remainder x % y is strictly less than y.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
if_pos- If the condition c is true, the conditional expression (if c then t else e) evaluates to t.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is the empty set.
Finset.filter_empty- Filtering the empty set by any predicate yields the empty set.
Finset.card_empty- The cardinality of the empty set is 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
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.
/-- Every parity representation of the cyclic cubic syndrome for n ≥ 6 is nonempty because the syndrome at {0, 1, 2} equals 1. -/theorem cyclic_cubic_parity_repr_nonempty (n : ℕ) (hn : 6 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (cyclic_cubic_syndrome n)) : S.Nonempty := by let A : Finset (Fin n) := {⟨0, by omega⟩, ⟨1, by omega⟩, ⟨2, by omega⟩} have hA_card : A.card = 3 := by have h01 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by intro h; injection h with h; omega have h02 : (⟨0, by omega⟩ : Fin n) ≠ ⟨2, by omega⟩ := by intro h; injection h with h; omega have h12 : (⟨1, by omega⟩ : Fin n) ≠ ⟨2, by omega⟩ := 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 h12 h · simp only [Finset.mem_insert, Finset.mem_singleton]; rintro (h | h) · exact h01 h · exact h02 h have h_syn : cyclic_cubic_syndrome n A = 1 := by unfold cyclic_cubic_syndrome have h : ∃ j : Fin n, have hn_pos : 0 < n := by have := j.isLt; omega A = {j, ⟨(j.val + 1) % n, Nat.mod_lt _ hn_pos⟩, ⟨(j.val + 2) % n, Nat.mod_lt _ hn_pos⟩} := by refine ⟨⟨0, by omega⟩, ?_⟩ dsimp [A] ext x simp only [Finset.mem_insert, Finset.mem_singleton] have h1 : (⟨(0 + 1) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) = ⟨1, by omega⟩ := by ext; simp [Nat.mod_eq_of_lt (by omega : 1 < n)] have h2 : (⟨(0 + 2) % n, Nat.mod_lt _ (by omega)⟩ : Fin n) = ⟨2, by omega⟩ := by ext; simp [Nat.mod_eq_of_lt (by omega : 2 < n)] rw [h1, h2] exact if_pos h have h_repr := hS.2 A ⟨by omega, by omega⟩ rw [h_syn] at h_repr by_contra h_empty rw [Finset.not_nonempty_iff_eq_empty] at h_empty have h_sub_empty : {y ∈ S | A ⊆ y} = ∅ := by rw [h_empty] exact Finset.filter_empty _ rw [h_sub_empty, Finset.card_empty] at h_repr revert h_repr decide