The sixteen words of Theorem 15.4
DefinitionSpencerEight_Supplement_family16discrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
The matrices of Theorem 15.4 are the four-letter words read from left to right, one row at a time, from the array
so , , …, .
Formalization Note The Lean index is 0-based: family16 i is . Each word is a word of four letters.
Definition code
import Mathlib
import Definitions.Def_SpencerEight_Supplement_word
namespace SpencerEight.Supplement
open Letter in
/-- The sixteen `16 × 16` words `A₁, …, A₁₆` of Theorem 15.4 (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.290 (PDF p.290)),
read from left to right, one row at a time, from the printed array
`IIII XZZZ ZJXJ JIZJ JZJZ ZXXX JIJI XZJJ JJXX XXXI XIXZ JIJZ IJJX JJII XZXI ZIIZ`.
**Formalization Note** `family16 i` is the source's `A_{i+1}` (0-based index); `Fin (2^4)` is `Fin 16`. -/
def family16 : Fin 16 → Matrix (Fin (2 ^ 4)) (Fin (2 ^ 4)) ℝ :=
![word ![I, I, I, I], word ![X, Z, Z, Z], word ![Z, J, X, J], word ![J, I, Z, J],
word ![J, Z, J, Z], word ![Z, X, X, X], word ![J, I, J, I], word ![X, Z, J, J],
word ![J, J, X, X], word ![X, X, X, I], word ![X, I, X, Z], word ![J, I, J, Z],
word ![I, J, J, X], word ![J, J, I, I], word ![X, Z, X, I], word ![Z, I, I, Z]]
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.4, p.290 (PDF p.290)