AFTD Auto-Formalizing Theoretical Domains

sum_pow_pauli_size

theoremverified

Weight enumerator of Pauli labels: summed over all 4^k labels, x^(k - pauli_size p) equals (x+3)^k. Per qubit the four Pauli choices contribute x (identity), 1, 1, 1 (X, Y, Z).

Statement

theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k
Source
step towards op_757_all_to_all_cnot_lower_bound
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • pauli_sizeThe weight (support size) of a k-qubit Pauli operator: the number of qubits on which the operator is not the identity.
  • PauliLabelA binary symplectic Pauli label on k qubits, given as a pair of binary vectors (x, z) in (ZMod 2)^k x (ZMod 2)^k.

The proof, explained

The theorem evaluates the Pauli weight enumerator by factoring each term into a per-qubit product and interchanging summation and multiplication. First, each label's weight x^(k - pauli_size p) is shown to factor into a product over the k qubits, contributing x at qubits where the label is identity and 1 elsewhere. Using the canonical equivalence between Pauli labels and functions Fin k → ℤ₂ × ℤ₂, the generalized distributive law (Fintype.prod_sum) swaps the sum and product into a product of k independent single-qubit sums. Finally, each single-qubit sum over the four Pauli choices evaluates to x + 1 + 1 + 1 = x + 3, yielding the total (x + 3)^k.

  1. k - pauli_size p is equal to the number of qubits where both components of p are zero.

    By definition, `pauli_size p` counts the qubits where at least one component of p is non-zero. Splitting the universe of k qubits into those satisfying this non-zero condition and those satisfying its negation (`Finset.card_filter_add_card_filter_not`), and simplifying the negation using De Morgan's laws (`Finset.filter_congr`), shows that the complement consists of the qubits where both components vanish. Since the total number of qubits is k (`card_univ`, `Fintype.card_fin`), linear arithmetic (`omega`) deduces that k - pauli_size p is the size of this complement. Rewriting with this equality replaces the exponent.

    lines 6–20

    uses Finset.card_filter_add_card_filter_not, Finset.filter_congr, card_univ, Fintype.card_fin

    lemma sum_pow_pauli_size_prod_per_qubit {k x : ℕ} (p : PauliLabel k) :
        x ^ (k - pauli_size p)
          = ∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1) := by
      have hcard : k - pauli_size p = (univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0)).card := by
        show k - (univ.filter (fun i : Fin k => p.1 i ≠ 0 ∨ p.2 i ≠ 0)).card = _
        have h2 := Finset.card_filter_add_card_filter_not (s := (univ : Finset (Fin k)))
          (p := fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0)
        have h3 : (univ.filter (fun i : Fin k => ¬ (p.1 i ≠ 0 ∨ p.2 i ≠ 0)))
            = univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) := by
          apply Finset.filter_congr
          intro i _
          simp
        rw [h3, card_univ, Fintype.card_fin] at h2
        omega
      rw [hcard]
  2. x^(k - pauli_size p) equals the product over all qubits of the factor testing whether both components of p are zero.

    Case analysis on whether each component of p(i) is zero simplifies the nested conditionals into a single condition testing both components (`Finset.prod_congr`). Rewriting with `Finset.prod_filter` transforms the product of this indicator into a product of the constant x over the set of qubits where p acts as the identity. Finally, `Finset.prod_const` evaluates this product as x raised to the number of identity qubits, completing the proof of the helper lemma.

    lines 21–29

    uses Finset.prod_congr, Finset.prod_filter, Finset.prod_const

      have hstep : (∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1))
          = ∏ i : Fin k, (if (p.1 i = 0 ∧ p.2 i = 0) then x else 1) := by
        apply Finset.prod_congr rfl
        intro i _
        by_cases h1 : p.1 i = 0 <;> by_cases h2 : p.2 i = 0 <;> simp [h1, h2]
      rw [hstep]
      rw [← Finset.prod_filter (s := univ) (p := fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) (f := fun _ => x)]
      rw [Finset.prod_const]
    
  3. For a single qubit, the sum of the Pauli factor over all four choices in ℤ₂ × ℤ₂ equals x + 3. automation

    The universe ℤ₂ × ℤ₂ is explicitly shown by finite decision (`decide`) to equal {(0, 0), (0, 1), (1, 0), (1, 1)}. Substituting this explicit four-element set and simplifying the sum evaluates the conditional on each pair: (0, 0) gives x, while (0, 1), (1, 0), and (1, 1) each give 1, summing to x + 1 + 1 + 1 = x + 3.

    lines 30–35

    lemma sum_pow_pauli_size_sum_zmod2_sq (x : ℕ) :
        (∑ c : ZMod 2 × ZMod 2, (if c.1 = 0 then (if c.2 = 0 then x else 1) else 1)) = x + 3 := by
      have hu : (univ : Finset (ZMod 2 × ZMod 2)) = {(0, 0), (0, 1), (1, 0), (1, 1)} := by decide
      rw [hu]
      simp
    
  4. The sum of x^(k - pauli_size p) over all Pauli labels is reindexed to a sum over functions g : Fin k → ℤ₂ × ℤ₂ of a per-qubit product.

    Using the per-qubit product lemma `sum_pow_pauli_size_prod_per_qubit`, each term in the sum is expressed as a product over qubits. The sum over Pauli labels (Fin k → ℤ₂) × (Fin k → ℤ₂) is then reindexed into a sum over functions g : Fin k → ℤ₂ × ℤ₂ using `Equiv.sum_comp` with the canonical bijection `sum_pow_pauli_size_equiv`. Definitional equality (`rfl`) simplifies the components of the reindexed functions so that the factor at qubit i depends directly on g(i).

    lines 36–45

    uses sum_pow_pauli_size_prod_per_qubit, Equiv.sum_comp, sum_pow_pauli_size_equiv

    /-- Weight enumerator of Pauli labels: `∑ p, x^(k - pauli_size p) = (x+3)^k`. -/
    theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k := by
      simp_rw [sum_pow_pauli_size_prod_per_qubit]
      rw [← Equiv.sum_comp (sum_pow_pauli_size_equiv k)]
      have h_prod : (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k,
          (if (sum_pow_pauli_size_equiv k g).1 i = 0 then (if (sum_pow_pauli_size_equiv k g).2 i = 0 then x else 1) else 1))
        = (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k,
          (if (g i).1 = 0 then (if (g i).2 = 0 then x else 1) else 1)) := by
        rfl
      rw [h_prod]
  5. Exchanging the summation over functions with the product over qubits yields a product of single-qubit sums.

    By the generalized distributive law `Fintype.prod_sum` applied in reverse, the sum over all functions g : Fin k → ℤ₂ × ℤ₂ of the product over qubits equals the product over all qubits i of the sum over all choices c ∈ ℤ₂ × ℤ₂.

    lines 46–48

    uses Fintype.prod_sum

      have h_swap := (@Fintype.prod_sum (Fin k) ℕ _ _ _ (fun _ => ZMod 2 × ZMod 2) _
        (fun _ c => if c.1 = 0 then if c.2 = 0 then x else 1 else 1)).symm
      rw [h_swap]
  6. The weight enumerator evaluates to (x + 3)^k.

    Each single-qubit sum is replaced by x + 3 using `sum_pow_pauli_size_sum_zmod2_sq`. The product of this constant over the k qubits of Fin k evaluates to (x + 3)^k via `prod_const`, `card_univ`, and `Fintype.card_fin`.

    lines 49–50

    uses sum_pow_pauli_size_sum_zmod2_sq, prod_const, card_univ, Fintype.card_fin

      simp_rw [sum_pow_pauli_size_sum_zmod2_sq]
      rw [prod_const, card_univ, Fintype.card_fin]
Finset.card_filter_add_card_filter_not
For any finite set s and decidable predicate p, the number of elements in s satisfying p plus the number of elements satisfying ¬p equals the total cardinality of s.
Finset.filter_congr
Two predicates that are logically equivalent on every element of a finite set s select the same filtered subset of s.
card_univ
The cardinality of the universal finset `univ` of a finite type α equals the cardinality of the type α.
Fintype.card_fin
The cardinality of the standard finite set Fin n is n.
Finset.prod_congr
If two finite sets are equal and two functions agree on every element of the set, their products over that set are equal.
Finset.prod_filter
The product of f(a) over elements of s satisfying predicate p equals the product over all elements of s of the conditional expression taking f(a) when p(a) holds and 1 otherwise.
Finset.prod_const
The product of a constant value b over a finite set s equals b raised to the cardinality of s.
sum_pow_pauli_size_prod_per_qubit
The weight enumerator term x^(k - pauli_size p) for a Pauli label p equals the product over all qubits i of the conditional factor that yields x if both components of p at qubit i are zero and 1 otherwise.
Equiv.sum_comp
Summing a function over a finite type is invariant under precomposition with an equivalence of finite types (reindexing a sum).
sum_pow_pauli_size_equiv
The canonical equivalence between functions from Fin k to ℤ₂ × ℤ₂ and Pauli labels (Fin k → ℤ₂) × (Fin k → ℤ₂).
Fintype.prod_sum
The generalized distributive law: the product over i of sums over j of f(i, j) equals the sum over all choice functions x of the product over i of f(i, x(i)).
sum_pow_pauli_size_sum_zmod2_sq
The sum of the single-qubit factor over all four pairs in ℤ₂ × ℤ₂ equals x + 3.
prod_const
The product of a constant value over a finite set equals that constant raised to the cardinality of the set.

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

open Finsetdef sum_pow_pauli_size_equiv (k : ℕ) : (Fin k → ZMod 2 × ZMod 2) ≃ PauliLabel k :=  Equiv.arrowProdEquivProdArrow (Fin k) (fun _ => ZMod 2) (fun _ => ZMod 2)lemma sum_pow_pauli_size_prod_per_qubit {k x : ℕ} (p : PauliLabel k) :    x ^ (k - pauli_size p)      = ∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1) := by  have hcard : k - pauli_size p = (univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0)).card := by    show k - (univ.filter (fun i : Fin k => p.1 i ≠ 0 ∨ p.2 i ≠ 0)).card = _    have h2 := Finset.card_filter_add_card_filter_not (s := (univ : Finset (Fin k)))      (p := fun i => p.1 i ≠ 0 ∨ p.2 i ≠ 0)    have h3 : (univ.filter (fun i : Fin k => ¬ (p.1 i ≠ 0 ∨ p.2 i ≠ 0)))        = univ.filter (fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) := by      apply Finset.filter_congr      intro i _      simp    rw [h3, card_univ, Fintype.card_fin] at h2    omega  rw [hcard]  have hstep : (∏ i : Fin k, (if p.1 i = 0 then (if p.2 i = 0 then x else 1) else 1))      = ∏ i : Fin k, (if (p.1 i = 0 ∧ p.2 i = 0) then x else 1) := by    apply Finset.prod_congr rfl    intro i _    by_cases h1 : p.1 i = 0 <;> by_cases h2 : p.2 i = 0 <;> simp [h1, h2]  rw [hstep]  rw [← Finset.prod_filter (s := univ) (p := fun i : Fin k => p.1 i = 0 ∧ p.2 i = 0) (f := fun _ => x)]  rw [Finset.prod_const]lemma sum_pow_pauli_size_sum_zmod2_sq (x : ℕ) :    (∑ c : ZMod 2 × ZMod 2, (if c.1 = 0 then (if c.2 = 0 then x else 1) else 1)) = x + 3 := by  have hu : (univ : Finset (ZMod 2 × ZMod 2)) = {(0, 0), (0, 1), (1, 0), (1, 1)} := by decide  rw [hu]  simp/-- Weight enumerator of Pauli labels: `∑ p, x^(k - pauli_size p) = (x+3)^k`. -/theorem sum_pow_pauli_size (k x : ℕ) : ∑ p : PauliLabel k, x ^ (k - pauli_size p) = (x + 3) ^ k := by  simp_rw [sum_pow_pauli_size_prod_per_qubit]  rw [← Equiv.sum_comp (sum_pow_pauli_size_equiv k)]  have h_prod : (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k,      (if (sum_pow_pauli_size_equiv k g).1 i = 0 then (if (sum_pow_pauli_size_equiv k g).2 i = 0 then x else 1) else 1))    = (∑ g : Fin k → ZMod 2 × ZMod 2, ∏ i : Fin k,      (if (g i).1 = 0 then (if (g i).2 = 0 then x else 1) else 1)) := by    rfl  rw [h_prod]  have h_swap := (@Fintype.prod_sum (Fin k) ℕ _ _ _ (fun _ => ZMod 2 × ZMod 2) _    (fun _ c => if c.1 = 0 then if c.2 = 0 then x else 1 else 1)).symm  rw [h_swap]  simp_rw [sum_pow_pauli_size_sum_zmod2_sq]  rw [prod_const, card_univ, Fintype.card_fin]
See it in the graphDiscuss this resultChallenge it