Members of the family
DefinitionSpencerEight_Supplement_familyBdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
Fix a basis of over and let be its coordinate map. For ,
with computed in . With self-dual this is the member of in Theorem 15.6.
Formalization Note The coordinate map is b.repr.
Definition code
import Mathlib
import Definitions.Def_SpencerEight_Supplement_pauliP
namespace SpencerEight.Supplement
/-- The member `P_x := P_{x, x³+x}` of the family `B_k` 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 `x ∈ GF(2^k)`, where `F₂^k` is identified with `GF(2^k)` through the basis `b`:
`x = ∑ᵢ cᵢ bᵢ ↔ c = (c₁, …, c_k)`. So `P_x = P_{φ(x), φ(x³+x)}` with `φ` the coordinate map of `b`;
`x³ + x` is computed in `GF(2^k)` and then read as a vector.
**Formalization Note** `GF(2^k)` is `GaloisField 2 k`; the coordinate map is `b.repr`. The theorem
applies this to a self-dual basis (`IsSelfDualBasis b`), for which `φ(x)ᵢ = Tr[x bᵢ]`. -/
noncomputable def familyB {k : ℕ} (b : Module.Basis (Fin k) (ZMod 2) (GaloisField 2 k))
(x : GaloisField 2 k) : Matrix (Fin k → ZMod 2) (Fin k → ZMod 2) ℝ :=
pauliP (fun i => b.repr x i) (fun i => b.repr (x ^ 3 + x) i)
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, and Step 1 of its proof, p.292 (PDF pp.291-292)