The constant
DefinitionSpencerEight_Supplement_Dmatdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
For , is the worst case of the matrix signing discrepancy over admissible families:
The constant of interest is ; Matrix Spencer bounds it above, and the families of Section 15 bound it below.
Formalization Note A real supremum. For the set is nonempty (all ) and bounded above by , so the supremum is genuine; both facts are proved in the mission's sanity file. The admissible matrices are the base mission's symmetric contractions.
Definition code
import Mathlib
import Definitions.Def_SpencerEight_IsSymmContraction
import Definitions.Def_SpencerEight_Supplement_discmat
namespace SpencerEight.Supplement
/-- The constant `D^mat_n` (Definition 15.1, Song, Zhang, *Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input*, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), pp.288-289 (PDF pp.288-289)): the
supremum of `discmat(A₁, …, A_n)` over all dimensions `1 ≤ d ≤ n` and all families of real symmetric
`d × d` matrices with `‖Aᵢ‖ ≤ 1` for every `i ∈ [n]`.
**Formalization Note** A real `sSup`. For `n ≥ 1` the set is nonempty (`d = 1`, all `Aᵢ = 0`) and bounded
above by `n` (triangle inequality), so the supremum is the true one; both facts are proved in
`Solutions/verification/SpencerEight_Supplement_sanity.lean`. The source defines `D^mat_n` only for
`n ≥ 1`; at `n = 0` the set is empty and the value is `0`, a case no statement uses. The admissible
matrices are the base mission's `IsSymmContraction` (symmetric, operator norm at most one). -/
noncomputable def Dmat (n : ℕ) : ℝ :=
sSup {r : ℝ | ∃ d : ℕ, 1 ≤ d ∧ d ≤ n ∧ ∃ A : Fin n → Matrix (Fin d) (Fin d) ℝ,
(∀ i, IsSymmContraction (A i)) ∧ r = discmat A}
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…), Definition 15.1, pp.288-289 (PDF pp.288-289)