The signed permutation
DefinitionSpencerEight_Supplement_pauliPdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
For , is the real matrix with rows and columns indexed by and entries
where .
Formalization Note is Fin k → ZMod 2, and is raised to the representative or of .
Definition code
import Mathlib
namespace SpencerEight.Supplement
/-- The matrix `P_{u,v}` of Theorem 15.6 (Song, Zhang, *Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input*, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), p.291 (PDF p.291)): for `u, v ∈ F₂^k`,
the real matrix with rows and columns indexed by `F₂^k` whose entry at `(y, y ⊕ u)` is `(−1)^{v·y}`
and whose other entries are `0`; `v·y = ∑ᵢ vᵢ yᵢ ∈ F₂` is the dot product.
**Formalization Note** `F₂^k` is `Fin k → ZMod 2` (so `2^k` rows and columns, indexed by the vectors
themselves, as in the source); `y ⊕ u` is `y + u`; `(−1)^{v·y}` is `(−1)^{(v·y).val}` with
`(v·y).val ∈ {0, 1}`. -/
def pauliP {k : ℕ} (u v : Fin k → ZMod 2) : Matrix (Fin k → ZMod 2) (Fin k → ZMod 2) ℝ :=
fun y z => if z = y + u then (-1 : ℝ) ^ (∑ i, v i * y i).val else 0
end SpencerEight.Supplement
Source
Song, Zhang, Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), Theorem 15.6, p.291 (PDF p.291)