Theorem 15.4 — sixteen words with discrepancy exactly , so
OpenSpencerEight.Supplement.theorem_15_4discrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
Let be the Kronecker words
in the letters of Section 15.2, and let be the largest root of . Then:
- each is a real symmetric signed permutation matrix with ;
- ;
- and ;
- the certified bracket holds:
- consequently .
The family is an explicit lower bound on the Matrix Spencer constant at : no signing of these sixteen involutions has norm below .
Formalization Note "Largest root" means and every real root of is at most . Truncated decimals are stated as intervals (, and likewise for ). The words are 16×16 matrices on indices in standard Kronecker order.
Differences from the source:
- encoding: z* is the largest root of q → q(z) = 0 ∧ every real root w of q satisfies w ≤ z; reason: definition of the largest (real) root; same number
- encoding: truncated decimals z* = 46.9247895…, 1 + √z* = 7.8501671176958… → 46.9247895 ≤ z < 46.9247896 and 7.8501671176958 ≤ 1 + √z < 7.8501671176959; reason: the source's convention (p.288) that a decimal followed by an ellipsis is a truncated expansion
- reading: D^mat_16/4 ≥ 1.962541779… → (1 + √z)/4 ≤ D^mat_16/4 ∧ 1.962541779 ≤ (1 + √z)/4 < 1.962541780; reason: the truncated decimal stands for the number (1 + √z*)/4 given by the family; this reading implies D^mat_16/4 ≥ 1.962541779
- encoding: A_1, …, A_16 ∈ ℝ^{16×16} → family16 : Fin 16 → Matrix (Fin (2^4)) (Fin (2^4)) ℝ, family16 i = A_{i+1}; reason: 0-based indexing and the standard Kronecker index order; same matrices
Preamble
import Mathlib import Definitions.Def_SpencerEight_Supplement_IsSignedPerm import Definitions.Def_SpencerEight_Supplement_family16 import Definitions.Def_SpencerEight_Supplement_discmat import Definitions.Def_SpencerEight_Supplement_Dmat
Formal statement
namespace SpencerEight.Supplement
/-- Theorem 15.4 (A family at `n = 16` with discrepancy exactly `1 + √z*`), 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). For the sixteen words `A₁, …, A₁₆` of `family16`:
1. each `Aᵢ` is a real symmetric signed permutation matrix with `Aᵢ² = I₁₆`;
2. `discmat(A₁, …, A₁₆) = 1 + √z*`, where `z*` is the largest root of
`q(z) = z⁴ − 88z³ + 2226z² − 14112z + 4805`;
3. `z* = 46.9247895…` and `1 + √z* = 7.8501671176958…` (truncated decimals);
4. `7850167116695/10¹² < discmat(A₁, …, A₁₆) < 7850167118696/10¹²`;
5. `D^mat_16 / 4 ≥ 1.962541779…`.
**Formalization Note** "Largest root" is: `q z* = 0` and every real root of `q` is at most `z*`. A decimal
followed by an ellipsis is a truncated expansion, so `z* = 46.9247895…` is
`46.9247895 ≤ z* < 46.9247896`, and likewise for `1 + √z*`. Clause 5 is read as
`D^mat_16/4 ≥ (1 + √z*)/4` together with the truncation `1.962541779 ≤ (1 + √z*)/4 < 1.962541780`;
`4 = √16`. -/
theorem theorem_15_4 :
(∀ i, (family16 i).IsSymm ∧ IsSignedPerm (family16 i) ∧ family16 i * family16 i = 1) ∧
∃ z : ℝ, z ^ 4 - 88 * z ^ 3 + 2226 * z ^ 2 - 14112 * z + 4805 = 0 ∧
(∀ w : ℝ, w ^ 4 - 88 * w ^ 3 + 2226 * w ^ 2 - 14112 * w + 4805 = 0 → w ≤ z) ∧
discmat family16 = 1 + Real.sqrt z ∧
46.9247895 ≤ z ∧ z < 46.9247896 ∧
7.8501671176958 ≤ 1 + Real.sqrt z ∧ 1 + Real.sqrt z < 7.8501671176959 ∧
(7850167116695 : ℝ) / 10 ^ 12 < discmat family16 ∧
discmat family16 < (7850167118696 : ℝ) / 10 ^ 12 ∧
(1 + Real.sqrt z) / 4 ≤ Dmat 16 / 4 ∧
1.962541779 ≤ (1 + Real.sqrt z) / 4 ∧ (1 + Real.sqrt z) / 4 < 1.962541780 := by sorry
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); letters and words p.289; Definition 15.1 pp.288-289