card_pauliStringsExactSupport
theoremverifiedimported Lean
Number of Pauli strings with a prescribed support. Let $n$ be a natural number and let $S \subseteq \mathrm{Fin}\,n$ be a set of coordinates. The number of Pauli strings $p$ of length $n$ whose support $\mathrm{supp}(p)$ equals exactly $S$ is $3^{|S|}$.
Statement
set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open scoped Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in open Complex Matrix in lemma card_pauliStringsExactSupport {n : ℕ} (S : Finset (Fin n)) : (pauliStringsExactSupport (n:=n) S).card = 3 ^ S.card
- Source
- TCSlib, `card_pauliStringsExactSupport`
- Lean proof
- By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.card_pauliStringsExactSupport← card_pauliStringsExactSupport (TCSlib/ErrorCorrectingCodes/QuantumHamming.lean:139): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- PauliNZ.toBasisEmbeds a non-identity Pauli ($X$, $Y$, or $Z$) from the three-element type $\mathrm{PauliNZ}$ into the full Pauli basis $\{I,X,Y,Z\}$.
- support_mkWithSupportSupport of a Pauli string built from prescribed data. Fix $n$, a finset $S \subseteq \mathrm{Fin}\,n$, and an assignment…
- mkWithSupportGiven a finset $S \subseteq \mathrm{Fin}\,n$ and an assignment $f : S \to \mathrm{PauliNZ}$, constructs the Pauli string that equals…
- supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- PauliNZA 3-element type for non-identity single-qubit Pauli operators, used in counting arguments.
- pauliStringsExactSupportThe finset of all Pauli strings on $n$ qubits whose support equals exactly the given finset $S$.
- instFintypePauliStringinstFintypePauliString
- PauliBasisThe four Pauli basis elements $\{I,X,Y,Z\}$, represented as an inductive type.
- PauliStringA Pauli string of length $n$ is a function $p : \mathrm{Fin}\,n \to \mathrm{PauliBasis}$.
- Used by 3
- WickContraction.fromInvolution_toInvolutionWickContraction.fromInvolution_toInvolution
- card_pauliErrorsLeCardinality of the bounded-weight Pauli error set. For natural numbers $n$ and $t$, the number of Pauli strings of length $n$ whose weight…
- WickContraction.mem_uncontracted_iff_not_contractedWickContraction.mem_uncontracted_iff_not_contracted
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.
set_option linter.mathlibStandardSet false inopen scoped BigOperators inopen scoped Real inopen scoped Nat inopen scoped Classical inopen scoped Pointwise inset_option maxRecDepth 4000 inset_option synthInstance.maxHeartbeats 20000 inset_option synthInstance.maxSize 128 inset_option relaxedAutoImplicit false inset_option autoImplicit false inopen Complex Matrix inlemma card_pauliStringsExactSupport {n : ℕ} (S : Finset (Fin n)) : (pauliStringsExactSupport (n:=n) S).card = 3 ^ S.card := by classical /- Standard proof outline: - show the subtype `{p // support p = S}` is in bijection with `S → PauliNZ` via `mkWithSupport` - `Fintype.card (S → PauliNZ) = 3^(S.card)` - translate to finset-card -/ rw [ show pauliStringsExactSupport S = Finset.image ( fun f : S → PauliNZ => mkWithSupport S f ) ( Finset.univ ) from by ext p simp [pauliStringsExactSupport] constructor <;> intro hp · have h_non_id : ∀ i ∈ S, p i ≠ PauliBasis.I := by simp +decide [← hp, support] use fun i => if p i = PauliBasis.X then PauliNZ.X else if p i = PauliBasis.Y then PauliNZ.Y else PauliNZ.Z funext i by_cases hi : i ∈ S <;> simp_all +decide [mkWithSupport] · cases hpi : p i <;> aesop · unfold support at hp subst hp simp_all only [ne_eq, Finset.mem_filter, Finset.mem_univ, true_and, not_false_eq_true, implies_true, Decidable.not_not] · obtain ⟨a, rfl⟩ := hp exact support_mkWithSupport S a ]; · rw [ Finset.card_image_of_injective, Finset.card_univ ] ; aesop; intro f g hfg have h_eq : ∀ i : S, f i = g i := by intro i; replace hfg := congr_fun hfg i; simp_all +decide [ mkWithSupport ] ; rcases f_i : f i with ( _ | _ | _ ) <;> rcases g_i : g i with ( _ | _ | _ ) <;> simp_all +decide [ PauliNZ.toBasis ] exact funext h_eq;