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}.\]Here the discrepancy $\mathrm{disc}(A)$ is defined as
\[\mathrm{disc}(A) := \min_{x\in\{\pm 1\}^n} \|Ax\|_\infty.\]Equivalently, if the linear forms are
\[L_i(x_1,\dots,x_n)=\sum_{j=1}^n a_{ij}x_j,\]then
\[\mathrm{disc}((a_{ij})_{i,j=1}^n)= \min_{\varepsilon\in\{\pm 1\}^n} \max_{1\le i\le n}\lvert L_i(\varepsilon)\rvert.\]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] | The 2 by 2 sign matrix with rows $(1,1)$ and $(1,-1)$. |
| $4/\sqrt{6}\approx 1.632993$ | [G2026] | A 6 by 6 sign matrix with exact discrepancy $4$. |
| $5/3\approx 1.666667$ | [X2026] | A 9 by 9 sign matrix with exact discrepancy $5$. |
Certificate for the $4/\sqrt{6}$ lower bound
Use the following sign matrix:
1 1 1 1 1 1
-1 -1 -1 1 1 1
-1 1 1 -1 1 1
-1 1 -1 1 -1 1
1 1 -1 -1 1 1
1 -1 1 -1 -1 1
All entries are ±1. For a sign vector x, let S be the set of columns where the corresponding coordinate of x is -1. For row number $i$, let T_i be the set of columns where that row has entry -1:
T1 = {}
T2 = {1,2,3}
T3 = {1,4}
T4 = {1,3,5}
T5 = {3,4}
T6 = {2,4,5}
Then
\[(Ax)_i = 6 - 2\lvert S\triangle T_i\rvert.\]Therefore the absolute value of the $i$th coordinate of Ax is at least $4$ whenever S is within Hamming distance $1$ of either T_i or the complement of T_i. The relevant centers are
{}, 123, 14, 135, 34, 245, 123456, 456, 2356, 246, 1256, 136
where, for example, 123 denotes the set {1,2,3}.
The sets of size 0, 1, 5, and 6 are covered by the centers {} and 123456. The sets of size 2 are covered as follows:
| S | center |
|---|---|
| 12 | 123 |
| 13 | 123 |
| 14 | 14 |
| 15 | 135 |
| 16 | 136 |
| 23 | 123 |
| 24 | 245 |
| 25 | 245 |
| 26 | 246 |
| 34 | 34 |
| 35 | 135 |
| 36 | 136 |
| 45 | 456 |
| 46 | 456 |
| 56 | 456 |
Since the centers are closed under complementation, this also covers the sets of size 4. The sets of size 3 are covered as follows:
| S | center |
|---|---|
| 123 | 123 |
| 124 | 14 |
| 125 | 1256 |
| 126 | 1256 |
| 134 | 14 |
| 135 | 135 |
| 136 | 136 |
| 145 | 14 |
| 146 | 14 |
| 156 | 1256 |
| 234 | 34 |
| 235 | 2356 |
| 236 | 2356 |
| 245 | 245 |
| 246 | 246 |
| 256 | 1256 |
| 345 | 34 |
| 346 | 34 |
| 356 | 2356 |
| 456 | 456 |
Thus every sign vector satisfies
\[\|Ax\|_\infty \ge 4.\]Equality is attained. For example,
x = (1,-1,1,1,1,1)^T
Ax = (4,2,0,-2,0,2)^T
Hence $\mathrm{disc}(A)=4$, and consequently
\[C_{10c}\ge \frac{4}{\sqrt{6}}\approx 1.632993.\]Certificate for the $5/3$ lower bound
Use the following sign matrix:
1 1 1 1 1 1 1 1 1
-1 -1 -1 1 1 1 1 1 1
-1 1 1 -1 -1 1 1 1 1
1 -1 -1 -1 -1 1 1 1 1
1 -1 1 -1 1 -1 1 1 1
-1 1 -1 -1 1 -1 1 1 1
-1 -1 1 1 -1 -1 1 1 1
1 1 -1 1 -1 -1 1 1 1
1 1 1 1 1 1 1 1 1
All entries are $\pm 1$. The ninth row is a duplicate of the first row; duplicate rows are allowed, and here it simply makes the displayed certificate square. This is a padding step in the row direction only: the construction still has nine columns, so it is not an $8$ by $8$ certificate.
For a sign vector $x$, let $S$ be the set of columns where the corresponding coordinate of $x$ is $-1$. For row number $i$, let $T_i$ be the set of columns where that row has entry $-1$:
T1 = {}
T2 = {1,2,3}
T3 = {1,4,5}
T4 = {2,3,4,5}
T5 = {2,4,6}
T6 = {1,3,4,6}
T7 = {1,2,5,6}
T8 = {3,5,6}
T9 = {}
Then
\[(Ax)_i = 9 - 2\lvert S\triangle T_i\rvert.\]Therefore the absolute value of the $i$th coordinate of $Ax$ is at least $5$ whenever $S$ is within Hamming distance $2$ of either $T_i$ or the complement of $T_i$.
We now prove this covering condition for the full $9$-cube. Write
\[S=U\cup W,\]where
\[U\subseteq\{1,\dots,6\},\qquad W\subseteq\{7,8,9\}.\]Let $w=\lvert W\rvert$. Since all the sets $T_i$ above are contained in ${1,\dots,6}$, for $i=1,\dots,8$ write $T_i=C_i$, where
C = {}, 123, 145, 2345, 246, 1346, 1256, 356
Let $C_i^*$ denote the complement of $C_i$ inside ${1,\dots,6}$. Then the complement of $T_i$ inside ${1,\dots,9}$ is
\[T_i^c=C_i^*\cup\{7,8,9\}.\]Thus the relevant distances in the full $9$-cube are
\[d_9(S,T_i)=d_6(U,C_i)+w\]and
\[d_9(S,T_i^c)=d_6(U,C_i^*)+(3-w).\]The last three coordinates are therefore accounted for by the terms $w$ and $3-w$.
The following finite fact about the $6$-cube will be used. The eight radius-$1$ balls around
C = {}, 123, 145, 2345, 246, 1346, 1256, 356
miss exactly the eight complements
C* = 123456, 456, 236, 16, 135, 25, 34, 124
Indeed, the codewords in $C$ have mutual Hamming distance at least $3$, so their radius-$1$ balls are disjoint and contain $8(1+6)=56$ vertices. Each listed vertex in $C^*$ has distance at least $2$ from every codeword in $C$, so none is in these balls. Since the $6$-cube has $64$ vertices, these are exactly the eight missed vertices.
The missed vertices are nevertheless within radius $2$ of $C$; respectively, one may use the following centers:
missed vertex: 123456 456 236 16 135 25 34 124
radius-2 center: 2345 246 123 1346 356 1256 2345 123
Now consider the four possible values of $w=\lvert W\rvert$.
If $w=0$, then $d_9(S,T_i)=d_6(U,C_i)$. The radius-$2$ covering of the $6$-cube by $C$ gives some $i$ with $d_9(S,T_i)\le 2$.
If $w=1$, then $d_9(S,T_i)=d_6(U,C_i)+1$ and $d_9(S,T_i^c)=d_6(U,C_i^)+2$. By the radius-$1$ statement above, either $U$ is within distance $1$ of some $C_i$, which gives $d_9(S,T_i)\le 2$, or $U=C_i^$ for some $i$, which gives $d_9(S,T_i^c)=2$.
If $w=2$, apply the previous $w=1$ case to the complement of $S$. Equivalently, either $U=C_i$ for some $i$, giving $d_9(S,T_i)=2$, or $U$ is within distance $1$ of some $C_i^*$, giving $d_9(S,T_i^c)\le 2$.
If $w=3$, then $d_9(S,T_i^c)=d_6(U,C_i^)$. By applying the radius-$2$ covering of the $6$-cube by $C$ to the complement of $U$, the complements $C_i^$ also form a radius-$2$ covering of the $6$-cube. Hence some $i$ satisfies $d_9(S,T_i^c)\le 2$.
Thus every vertex $S$ of the full $9$-cube is within Hamming distance $2$ of some $T_i$ or of some complement $T_i^c$. Consequently every sign vector satisfies
\[\|Ax\|_\infty\ge 5.\]Equality is attained. For example,
x = (-1,-1,1,-1,1,1,1,1,1)^T
Ax = (3,5,5,3,5,3,3,-3,3)^T
Hence $\mathrm{disc}(A)=5$, and consequently
\[C_{10c}\ge \frac{5}{\sqrt{9}}=\frac{5}{3}\approx 1.666667.\]Further remarks
- For large $n$, the best asymptotic lower bound remains $1$ [Band2024].
- Replacing the entrywise bound 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? (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.
- [G2026] Griego, Sebastian. 6 by 6 sign-matrix certificate for C10c, submitted to this repository (2026).
- [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.
- [X2026] Xie, Chuhan. 9 by 9 sign-matrix certificate for C10c, submitted to this repository (2026).
Contribution notes
ChatGPT Pro was used to generate an initial version of this page.