line_cubic_parity_repr_nonempty
Every parity representation of the line cubic syndrome for n ≥ 5 is nonempty, because line_syndrome n {0, 1, 2} = 1.
Statement
theorem line_cubic_parity_repr_nonempty (n : ℕ) (hn : 5 ≤ n)
(S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_syndrome n)) :
S.Nonempty- Source
- step towards line_cubic_t_count_lower_bound
- Verified
- 06 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 proof argues by contradiction. Since n ≥ 5, the set A = {0, 1, 2} is a well-defined consecutive triple of size 3, which makes the line syndrome evaluate to 1 on A. By the definition of a parity representation, the number of sets in S containing A must be odd (1 mod 2). If S were empty, this count would be 0, yielding the contradiction 0 = 1 in ℤ/2ℤ.
Define the set A = {0, 1, 2} ⊆ {0, …, n - 1} and establish that |A| = 3.
Since n ≥ 5, the numbers 0, 1, and 2 are valid indices in Fin n. We establish that 0, 1, and 2 are pairwise distinct in Fin n (via omega on their values), and then compute the cardinality of {0, 1, 2} by repeatedly applying the rule for the cardinality of inserting an element not already present into a set.
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
line_syndrome n A = 1.
Unfolding the definition of line_syndrome, the syndrome is 1 if A is a consecutive triple {i, i + 1, i + 2} for some i < n - 2, and 0 otherwise. Choosing i = 0 (which is valid since n ≥ 5 implies 0 < n - 2) shows that A is of this form, so the conditional evaluates to 1.
uses
if_poshave h_syn : line_syndrome n A = 1 := by unfold line_syndrome have h : ∃ i : Fin (n - 2), A = {⟨i.1, by omega⟩, ⟨i.1 + 1, by omega⟩, ⟨i.1 + 2, by omega⟩} := by refine ⟨⟨0, by omega⟩, ?_⟩ rfl exact if_pos h
The number of sets in S that contain A is odd, that is, |{y ∈ S | A ⊆ y}| ≡ 1 (mod 2).
Since S is a parity representation of line_syndrome n and 1 ≤ |A| = 3 ≤ 3, the representation condition guarantees that |{y ∈ S | A ⊆ y}| mod 2 equals line_syndrome n A. Substituting the value line_syndrome n A = 1 gives the congruence.
have h_repr := hS.2 A ⟨by omega, by omega⟩ rw [h_syn] at h_repr
S is nonempty.
Suppose for contradiction that S is empty. Then the subset {y ∈ S | A ⊆ y} is also empty, hence has cardinality 0. But by the parity representation property, its cardinality modulo 2 is 1, giving 0 = 1 in ℤ/2ℤ, which is a 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- Inserting an element into a finite set that does not already contain it increases its cardinality by 1.
Finset.card_singleton- A singleton set has cardinality 1.
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
if_pos- An if-then-else expression evaluates to its 'then' branch when the condition holds.
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 empty set has cardinality 0.
- On paper, showing that {0, 1, 2} has cardinality 3 is immediate; in Lean, elements of Fin n carry bounds checking (proven via omega), and proving the set has cardinality 3 requires explicitly showing that 0, 1, and 2 are pairwise distinct.
- The final contradiction that 0 = 1 in ℤ/2ℤ is dispatched computationally by decide.
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 line cubic syndrome for n ≥ 5 is nonempty. -/theorem line_cubic_parity_repr_nonempty (n : ℕ) (hn : 5 ≤ n) (S : Finset (Finset (Fin n))) (hS : is_parity_repr S (line_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 : line_syndrome n A = 1 := by unfold line_syndrome have h : ∃ i : Fin (n - 2), A = {⟨i.1, by omega⟩, ⟨i.1 + 1, by omega⟩, ⟨i.1 + 2, by omega⟩} := by refine ⟨⟨0, by omega⟩, ?_⟩ rfl 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