AFTD Auto-Formalizing Theoretical Domains

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

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