AFTD Auto-Formalizing Theoretical Domains

line_cubic_parity_repr_nonempty

theoremverified

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

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ℤ.

  1. 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.

    lines 5–17

    uses Finset.card_insert_of_notMem, Finset.card_singleton, Finset.mem_singleton, Finset.mem_insert

      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
  2. 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.

    lines 18–23

    uses if_pos

      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
  3. 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.

    lines 24–25

      have h_repr := hS.2 A ⟨by omega, by omega⟩
      rw [h_syn] at h_repr
  4. 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.

    lines 26–33

    uses Finset.not_nonempty_iff_eq_empty, Finset.filter_empty, Finset.card_empty

      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
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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it