Spencer discrepancy constant (“six standard deviations suffice”)
Description of constant
$C_{10c}$ is the least constant $K$ for which one has \(\mathrm{disc}(A) \le K\sqrt{n}\qquad\text{for all }n\text{ and all }A\in[-1,1]^{n\times n}.\) for all $n\ge 1$ and all real $n\times n$ matrices $A$ with entries bounded in magnitude by $1$, where the discrepancy $\mathrm{disc}(A)$ is defined as \(\mathrm{disc}(A) \;:=\; \min_{x\in\{\pm 1\}^n}\ \|Ax\|_\infty.\) Equivalently, if $L_i(x_1,\dots,x_n)=\sum_{j=1}^n a_{ij}x_j$ are $n$ linear forms, then \(\mathrm{disc}((a_{ij})_{i,j=1}^n)=\min_{\varepsilon\in\{\pm 1\}^n}\max_{1\le i\le n}|L_i(\varepsilon)|.\)
Known upper bounds
| Bound | Reference | Comments |
|---|---|---|
| $5.32$ | [Spe1985] | Usually reported as $6$. The celebrated “six standard deviations suffice” theorem of Spencer; also applies to rectangular matrices or set systems. |
| $5.199$ | [Bel2013] | Re-optimizes Spencer’s method. |
| $3.65$ (unpublished) | Schmidt [Bel2013] | Some of the computations are given only as a personal communication. |
| $3\sqrt{3/2}\approx 3.674235$ | [PV2022] | Also gives an algorithmic version. |
Known lower bounds
| Bound | Reference | Comments |
|---|---|---|
| $1$ | Trivial | $A=[1]$. Also achieved by Hadamard matrices [Band2024]. |
| $\sqrt{2}\approx 1.414214$ | [Band2024] | $A = \begin{bmatrix}1&1\1&-1\end{bmatrix}$. |
Further remarks
- For large $n$, the best asymptotic lower bound remains $1$ [Band2024].
- Replacing the entrywise bound $|a_{ij}|\le 1$ by an $\ell_2$-bound on columns leads to the Komlós conjecture, which would imply (after scaling) Spencer-type discrepancy bounds.
References
- [AS2008] Alon, N.; Spencer, J. The Probabilistic Method, 3rd ed. Wiley, 2008. (See the discussion around “Six Standard Deviations Suffice”.)
- [Band2024] Bandeira, A. S. [Did just a couple of deviations suffice all along?](https://randomstrasse101.math.ethz.ch/posts/HowManyDeviations/) (problems 10–14). Randomstrasse 101 blog post (Dec 19, 2024).
- [Ban2010] Bansal, N. Constructive algorithms for discrepancy minimization. FOCS 2010, 3–10.
- [Bel2013] Belshaw, A. W. Strong Normality, Modular Normality, and Flat Polynomials: Applications of Probability in Number Theory and Analysis. PhD thesis, Simon Fraser University, 2013.
- [LM2015] Lovett, S.; Meka, R. Constructive discrepancy minimization by walking on the edges. SIAM J. Comput. 44 (5) (2015), 1573–1582. arXiv:1203.5747
- [MO175826] MathOverflow. Spencer’s “six standard deviations” theorem – better constants? Question 175826 (2014).
- [PV2022] Pesenti, L.; Vladu, A. Discrepancy Minimization via Regularization. arXiv:2211.05509
- [Spe1985] Spencer, J. Six standard deviations suffice. Trans. Amer. Math. Soc. 289 (2) (1985), 679–706.
Contribution notes
ChatGPT Pro was used to generate an initial version of this page.