Lemma 4.3 — a power sum bounded by its first values
ProvedQuantumHMMR.lemma_4_3p2o-gran-per-chapterp2o-plan-paperp2o-v1pseudorandomnessquantum-informationunitary-designs
Let and . Suppose
If , then for every
The bound controls a finite spectral expansion from its first few values, without bounding the coefficients individually, which would introduce a dependence on the dimension.
Differences from the source:
- reading: b_i, λ_i of unspecified type → complex numbers b_i, λ_i; reason: the eigenvalues of a moment operator are complex in general; complex covers real
Preamble
import Mathlib
Formal statement
namespace QuantumHMMR
/-- **Lemma 4.3** (Dujmovic–Haferkamp–Poremba, *On the pseudorandomness of simple quantum processes*, arXiv:2610.02100 (held version, sha256 9920ec45…4f20), Eq. (15), p.13). Let `D ≥ 1` and `0 < ρ < 1`. Suppose
`u_j = Σ_{i=1}^{D} b_i λ_i^j` for `j ≥ 1`, with `|λ_i| ≤ ρ`. If `|u_1|, …, |u_D| ≤ B`, then for every
`j ≥ D`, `|u_j| ≤ B · D · 2^D · C(j + D - 2, D - 1) · ρ^{j-D}`.
**Formalization Note** `b_i, λ_i` are complex numbers, indexed by `Fin D`. The natural-number
subtractions `j + D - 2`, `D - 1`, `j - D` are exact under `D ≥ 1`, `j ≥ D`. -/
theorem lemma_4_3 (D : ℕ) (hD : 1 ≤ D) (ρ : ℝ) (hρ0 : 0 < ρ) (hρ1 : ρ < 1)
(b lam : Fin D → ℂ) (hlam : ∀ i, ‖lam i‖ ≤ ρ) (B : ℝ)
(hB : ∀ j : ℕ, 1 ≤ j → j ≤ D → ‖∑ i, b i * lam i ^ j‖ ≤ B) :
∀ j : ℕ, D ≤ j →
‖∑ i, b i * lam i ^ j‖ ≤ B * D * 2 ^ D * ((j + D - 2).choose (D - 1) : ℝ) * ρ ^ (j - D) := by sorry
end QuantumHMMR
Source
Dujmovic–Haferkamp–Poremba, On the pseudorandomness of simple quantum processes, arXiv:2610.02100 (held version sha256 9920ec45…), Lemma 4.3, Eq. (15), p.13
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.