card_pauliErrorsLe
theoremverifiedimported Lean
Cardinality of the bounded-weight Pauli error set. For natural numbers $n$ and $t$, the number of Pauli strings of length $n$ whose weight is at most $t$ is \[ |\mathcal{E}(n,t)| \;=\; \sum_{j=0}^{t} \binom{n}{j}\, 3^{\,j}. \] Here a Pauli string is a function $p : \mathrm{Fin}\,n \to \{I,X,Y,Z\}$, and its weight $\mathrm{wt}(p)$ is the number of coordinates $i$ with $p(i) \neq I$; the sum counts, for each $j \le t$, the $\binom{n}{j}$ choices of a weight-$j$ support together with the $3^{j}$ assignments of a non-identity Pauli to each chosen coordinate.
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 theorem card_pauliErrorsLe (n t : ℕ) : (PauliErrorsLe n t).card = ∑ j ∈ Finset.range (t + 1), n.choose j * 3 ^ j
- Source
- TCSlib, `card_pauliErrorsLe`
- 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_pauliErrorsLe← card_pauliErrorsLe (TCSlib/ErrorCorrectingCodes/QuantumHamming.lean:176): adapted
What was changed in
card_pauliErrorsLe--- TCSlib/ErrorCorrectingCodes/QuantumHamming.lean:176 (card_pauliErrorsLe) +++ as compiled here @@ -1,2 +1,13 @@ -/-- Clean Quantum Hamming counting identity. -/ +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 theorem card_pauliErrorsLe (n t : ℕ) : @@ -13,3 +24,3 @@ ext p; simp [PauliErrorsLe, pauliStringsExactSupport]; - exact Nat.lt_succ_iff.symm; + exact Iff.rfl; rw [ h_union, Finset.card_biUnion, Finset.sum_congr rfl ]; - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- PauliErrorsLeThe set of all Pauli strings of weight at most $t$:…
- pauliStringsExactSupportThe finset of all Pauli strings on $n$ qubits whose support equals exactly the given finset $S$.
- instFintypePauliStringinstFintypePauliString
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
- card_pauliStringsExactSupportNumber of Pauli strings with a prescribed support. Let $n$ be a natural number and let $S \subseteq \mathrm{Fin}\,n$ be a set of…
- Used by 1
- quantum_hamming_bound_rawQuantum Hamming bound for non-degenerate codes. Let $C \le \mathcal{H}_n$ be a subspace of the $n$-qubit Hilbert space that is a…
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 in/-- Clean Quantum Hamming counting identity. -/theorem card_pauliErrorsLe (n t : ℕ) : (PauliErrorsLe n t).card = ∑ j ∈ Finset.range (t + 1), n.choose j * 3 ^ j := by classical /- proof outline: - partition by `j = weight p` - partition by exact support `S` with `S.card = j` - count supports: `card (powersetCard j univ) = n.choose j` - each support contributes `3^j` by `card_pauliStringsExactSupport` -/ have h_union : PauliErrorsLe n t = Finset.biUnion (Finset.range (t + 1)) (fun j => Finset.biUnion (Finset.powersetCard j (Finset.univ : Finset (Fin n))) (fun S => pauliStringsExactSupport S)) := by ext p; simp [PauliErrorsLe, pauliStringsExactSupport]; exact Iff.rfl; rw [ h_union, Finset.card_biUnion, Finset.sum_congr rfl ]; · intro j hj; rw [ Finset.card_biUnion ]; · rw [ Finset.sum_congr rfl fun x hx => card_pauliStringsExactSupport x ]; rw [ Finset.sum_congr rfl fun x hx => by rw [ Finset.mem_powersetCard.mp hx |>.2 ] ] ; simp +decide [ Finset.card_univ ]; · intro S hS T hT hST; simp_all +decide [ Finset.disjoint_left, pauliStringsExactSupport ] ; · intros j hj k hk hjk; simp_all +decide [ Finset.disjoint_left ] ; unfold pauliStringsExactSupport; intro a x a_1 a_2 x_1 a_3 subst a_1 a_3 simp_all only [Finset.mem_filter, Finset.mem_univ, true_and] subst a_2 apply Aesop.BuiltinRules.not_intro intro a_1 subst a_1 simp_all only [not_true_eq_false];