AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_parity_repr_nonempty

theoremverified

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

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.

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

    lines 3–15

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

    lines 16–30

    uses Nat.mod_lt, Finset.mem_insert, Finset.mem_singleton, Nat.mod_eq_of_lt, if_pos

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

    lines 31–32

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

    lines 33–40

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

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