cyclic_cubic_min_t_count_eq_of_bounds
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.
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.
uses
le_antisymmunfold cyclic_cubic_min_t_count apply le_antisymm
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.
uses
csInf_le,OrderBot.bddBelow· obtain ⟨S, hS, rfl⟩ := h_ex exact csInf_le (OrderBot.bddBelow _) ⟨S, hS, rfl⟩
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.
uses
le_csInf· apply le_csInf · obtain ⟨S, hS, rfl⟩ := h_ex exact ⟨S.card, S, hS, rfl⟩
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.
· 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
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.
/-- 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