Spencer discrepancy constant (“six standard deviations suffice”)

Description of constant

$C_{10c}$ is the least constant $K$ for which one has

Here the discrepancy $\mathrm{disc}(A)$ is defined as

Equivalently, if the linear forms are

then

Known upper bounds

Known lower bounds

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

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:

Since the centers are closed under complementation, this also covers the sets of size 4. The sets of size 3 are covered as follows:

Thus every sign vector satisfies

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

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

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

where

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

Thus the relevant distances in the full $9$-cube are

and

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

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

Certificate for the $7/\sqrt{17}$ lower bound

Use the following $17$ by $17$ sign matrix. It has $16$ distinct rows in $17$ columns; the last row repeats the first (a duplicate row does not change the discrepancy) purely to make the matrix square.

  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  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  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 -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

As in the previous certificates, for a sign vector $x$ let $S$ be the set of columns where $x$ is $-1$, and for row $i$ let $T_i$ be the set of columns where that row is $-1$ (columns numbered $1$–$17$):

T1  = {}
T2  = {1,2,3,4,5,6,7}
T3  = {1,2,3,8,9,10,11}
T4  = {4,5,6,8,9,10,12}
T5  = {1,4,5,7,8,9,11,13}
T6  = {2,3,4,7,8,10,12,13}
T7  = {2,6,7,9,11,12,13}
T8  = {1,3,5,6,10,11,12,13}
T9  = {2,5,6,7,8,10,11,14}
T10 = {1,3,6,7,8,9,12,14}
T11 = {2,3,4,5,9,11,12,14}
T12 = {1,4,7,10,11,12,14}
T13 = {1,2,4,6,9,10,13,14}
T14 = {3,5,7,9,10,13,14}
T15 = {3,4,6,8,11,13,14}
T16 = {1,2,5,8,12,13,14}
T17 = {}

Then $(Ax)_i = 17 - 2\lvert S\triangle T_i\rvert$, so $\lvert (Ax)_i\rvert \ge 7$ exactly when $S$ is within Hamming distance $5$ of $T_i$ or of its complement. The $16$ sets $T_i$, together with their complements, thus form radius-$5$ Hamming balls that cover all of ${0,1}^{17}$; equivalently,

This was checked by exhaustive evaluation over all $2^{17}=131072$ sign vectors (and, independently, by verifying the radius-$5$ covering of the $17$-cube). Hence $\mathrm{disc}(A)=7$ and

The centres $T_i$ were found by a greedy set-cover search for a small radius-$5$ covering code of the $17$-cube; only $16\le 17$ balls are needed, which is what allows the matrix to be square. (Note $n=17$ continues the pattern $n=2^d+1$ of the $n=9$ construction)

Certificate for the $5/\sqrt{8}$ lower bound

Use the following $8$ by $8$ matrix. Entries lie in ${-1,0,1}\subset[-1,1]$, which is the range the definition of $C_{10c}$ allows; the eighth column is identically zero. Every previously recorded lower bound here uses a sign matrix, and that restriction is what this entry drops. Note that the upper-bound side quantifies over the same set: [PV2022]’s Theorem 4.5 reads “for every $A\in[-1,1]^{n\times n}$”.

 1  1  1  1  1  1  1  0
 1  1  1 -1 -1 -1 -1  0
 1  1 -1  1 -1 -1  1  0
 1  1 -1 -1  1  1 -1  0
 1 -1  1  1 -1  1 -1  0
 1 -1  1 -1  1 -1  1  0
 1 -1 -1  1  1 -1 -1  0
 1 -1 -1 -1 -1  1  1  0

As in the certificates above, for a sign vector $x$ let $S$ be the set of columns where $x$ is $-1$, and for row $i$ let $T_i$ be the set of columns $j\le 7$ where that row is $-1$:

T1 = {}          T5 = {2,5,7}
T2 = {4,5,6,7}   T6 = {2,4,6}
T3 = {3,5,6}     T7 = {2,3,6,7}
T4 = {3,4,7}     T8 = {2,3,4,5}

Then $(Ax)_i = 7 - 2\lvert S\triangle T_i\rvert$, so $\lvert (Ax)_i\rvert \ge 5$ exactly when $S$ is within Hamming distance $1$ of $T_i$ or of its complement in ${1,\dots,7}$. The sixteen sets $T_i$ and their complements are precisely the codewords of the perfect $[7,4]$ Hamming code, whose radius-1 balls partition ${0,1}^7$ — $16\cdot 8 = 128 = 2^7$ — so every $S$ is covered and

The eighth coordinate of $x$ is irrelevant, so this is an exhaustive check over $2^7=128$ cases; over all $2^8=256$ sign vectors the distribution of $\lVert Ax\rVert_\infty$ is $5$ (224 times) and $7$ (32 times). Equality is attained, e.g. at $x=(-1,-1,-1,-1,-1,-1,1,-1)^T$. Hence $\mathrm{disc}(A)=5$ and

$5$ is optimal at $n=8$

For $a\in[-1,1]^8$ and $t\ge 6$, if $\langle a,x\rangle\ge t$ and $\langle a,y\rangle\ge t$ then $2t\le\langle a,x+y\rangle\le\sum_i|x_i+y_i| =2\,(8-d(x,y))$, so $d(x,y)\le 8-t\le 2$. By Kleitman’s diameter theorem a subset of the $8$-cube of diameter $2$ has at most $\sum_{i\le 1}\binom{8}{i}=9$ elements, so each row certifies at most $2\cdot 9=18$ of the $256$ sign vectors, and $8\cdot 18=144<256$. Hence $\mathrm{disc}(A)\le 5$ for every $A\in[-1,1]^{8\times 8}$, and this certificate is best possible at $n=8$. The same argument gives the exact optima $\sqrt2$ at $n=2$ and $3/2$ at $n=4$; the three cases $n=2,4,8$ are the zero-slack rows of this counting bound and are now all attained.

How this was found

The reduction above turns the problem into one about covering codes: a matrix with $\mathrm{disc}\ge d$ at size $n$ is exactly a binary covering code of length $n$ and radius $r=(n-d)/2$, of size at most $2n$ and closed under complementation, giving $C_{10c}\ge (n-2r)/\sqrt{\max(n,P)}$ for $P$ centres. Evaluating that over every entry of Kéri’s table of bounds on $K(n,R)$ (old.sztaki.hu/~keri/codes/2_tables.pdf), the best value obtainable is $5/\sqrt8$, from the row Kéri marks as a perfect code; the second is $7/4$ from $K(15,4)\le 32$ and the third is $7/\sqrt{17}$, the bound recorded above, from $K(17,5)\le 32$. A search using this framing rediscovers the $n=17$ certificate of [L2026] from scratch in under a second.

Zeros are what make $n=8$ reachable. In a sign matrix at even $n$ every $(Ax)_i=n-2\lvert S\triangle T_i\rvert$ is even, so the discrepancy is even; beating $4$ at $n=8$ would need $\mathrm{disc}\ge 6$, i.e. $K(8,1)\le 16$, whereas $K(8,1)=32$. A single zero column breaks that parity constraint.

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).
• [L2026] Li, Youhua. 17 by 17 sign-matrix certificate for C10c, submitted to this repository (2026).
• [H2026] Y. H. 8 by 8 ${-1,0,1}$-matrix certificate for C10c from the perfect $[7,4]$ Hamming code, submitted to this repository (2026). Verification notes: howiehwong.github.io/poolish/constants.html.

Contribution notes

ChatGPT Pro was used to generate an initial version of this page.

The v2 erratum on Theorem 4.5 was checked against the arXiv comments field of 2211.05509 and against the statement of Theorem 4.5 in the v2 html. AI assistance was used to draft the wording.

← Back to the table of constants