AFTD Auto-Formalizing Theoretical Domains

cyclic_cubic_min_t_count_eq_of_bounds

theoremverified

If there exists a parity representation of cardinality k, and all parity representations have cardinality at least k, then cyclic_cubic_min_t_count n = k.

Statement

theorem cyclic_cubic_min_t_count_eq_of_bounds (n k : ℕ) (h_ex : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (cyclic_cubic_syndrome n) ∧ S.card = k) (h_lb : ∀ S : Finset (Finset (Fin n)), is_parity_repr S (cyclic_cubic_syndrome n) → k ≤ S.card) : cyclic_cubic_min_t_count n = k
Source
step towards cyclic_cubic_phase_min_t_count_eq_two_n_add_five
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • cyclic_cubic_min_t_countFor a natural number n, cyclic_cubic_min_t_count n is the infimum in ℕ of the cardinalities of all parity representations S : Finset…
  • 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…
  • 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…

The proof, explained

By definition, cyclic_cubic_min_t_count n is the infimum of the set of cardinalities of all parity representations for the cyclic cubic syndrome. The proof shows that this infimum equals k by antisymmetry. The upper bound cyclic_cubic_min_t_count n ≤ k holds because k is the cardinality of an assumed parity representation and ℕ is bounded below; the lower bound k ≤ cyclic_cubic_min_t_count n holds because the set is nonempty and every parity representation is assumed to have cardinality at least k.

  1. To show cyclic_cubic_min_t_count n = k, it suffices to prove cyclic_cubic_min_t_count n ≤ k and k ≤ cyclic_cubic_min_t_count n.

    Unfolding the definition of cyclic_cubic_min_t_count expresses it as the infimum (sInf) of the set of cardinalities of all parity representations for cyclic_cubic_syndrome n. By the antisymmetry of the order on ℕ (le_antisymm), equality reduces to establishing the two opposing inequalities.

    lines 3–4

    uses le_antisymm

      unfold cyclic_cubic_min_t_count
      apply le_antisymm
  2. cyclic_cubic_min_t_count n ≤ k

    From the hypothesis h_ex, let S be a parity representation of cardinality k. The natural numbers have a bottom element 0, so any set of natural numbers is bounded below (OrderBot.bddBelow). Since k belongs to the set of cardinalities, the infimum of the set is at most k by csInf_le.

    lines 5–6

    uses csInf_le, OrderBot.bddBelow

      · obtain ⟨S, hS, rfl⟩ := h_ex
        exact csInf_le (OrderBot.bddBelow _) ⟨S, hS, rfl⟩
  3. The set of cardinalities of parity representations is nonempty.

    To prove k ≤ sInf, we apply le_csInf, which requires showing that the set is nonempty and that k bounds every element from below. The representation S of size k from h_ex provides an explicit witness that the set is nonempty.

    lines 7–9

    uses le_csInf

      · apply le_csInf
        · obtain ⟨S, hS, rfl⟩ := h_ex
          exact ⟨S.card, S, hS, rfl⟩
  4. k ≤ cyclic_cubic_min_t_count n

    For any element b in the set, b is the cardinality of some parity representation S. The lower bound hypothesis h_lb guarantees that k ≤ S.card = b. Since k is a lower bound for all elements and the set is nonempty, k is at most the infimum.

    lines 10–11

        · rintro _ ⟨S, hS, rfl⟩
          exact h_lb S hS
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
csInf_le
In a conditionally complete lattice, the infimum of a set bounded below is less than or equal to any element of that set.
OrderBot.bddBelow
Any subset of a preorder with a bottom element is bounded below.
le_csInf
In a conditionally complete lattice, a is less than or equal to the infimum of a set s if s is nonempty and a is a lower bound for every element of s.

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

/-- If there exists a parity representation of cardinality k, and all parity representations have cardinality at least k, then cyclic_cubic_min_t_count n = k. -/theorem cyclic_cubic_min_t_count_eq_of_bounds (n k : ℕ) (h_ex : ∃ S : Finset (Finset (Fin n)), is_parity_repr S (cyclic_cubic_syndrome n) ∧ S.card = k) (h_lb : ∀ S : Finset (Finset (Fin n)), is_parity_repr S (cyclic_cubic_syndrome n) → k ≤ S.card) : cyclic_cubic_min_t_count n = k := by  unfold cyclic_cubic_min_t_count  apply le_antisymm  · obtain ⟨S, hS, rfl⟩ := h_ex    exact csInf_le (OrderBot.bddBelow _) ⟨S, hS, rfl⟩  · apply le_csInf    · obtain ⟨S, hS, rfl⟩ := h_ex      exact ⟨S.card, S, hS, rfl⟩    · rintro _ ⟨S, hS, rfl⟩      exact h_lb S hS
See it in the graphDiscuss this resultChallenge it