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}\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):=\underset{x\in \{\pm 1{\}}^n}{\min }\Vert Ax{\Vert }_{\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)=\underset{\epsilon \in \{\pm 1{\}}^n}{\min }\underset{1\le i\le n}{\max }|L_i(\epsilon )|.$$

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

$$(Ax{)}_i=6-2|S△T_i|.$$

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

$$\Vert Ax{\Vert }_{\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 \mathrm{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|S△T_i|.$$

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\},W\subseteq \{7,8,9\}.$$

Let $w=|W|$. 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^{\text{*}}$ 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^{\ast }\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^{\ast })+(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^{\text{*}}$ 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=|W|$.

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^{\text{*}})+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^{\text{*}}$ 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^{\text{*}}$, giving $d_9(S,T_i^c)\le 2$.

If $w=3$, then $d_9(S,T_i^c)=d_6(U,C_i^{\text{*}})$. By applying the radius-$2$ covering of the $6$-cube by $C$ to the complement of $U$, the complements $C_i^{\text{*}}$ 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

$$\Vert Ax{\Vert }_{\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 \mathrm{1.666667.}$$

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|S△T_i|$, so $|(Ax{)}_i|\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,

$$\underset{x\in \{\pm 1{\}}^{17}}{\min }\Vert Ax{\Vert }_{\infty }=7.$$

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

$$C_{10c}\ge \frac{7}{\sqrt{17}}\approx \mathrm{1.697749.}$$

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|S△T_i|$, so $|(Ax{)}_i|\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

$$\underset{x\in \{\pm 1{\}}^8}{\min }\Vert Ax{\Vert }_{\infty }=5.$$

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 $\Vert Ax{\Vert }_{\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

$$C_{10c}\ge \frac{5}{\sqrt{8}}=\frac{5\sqrt{2}}{4}\approx \mathrm{1.767766953.}$$

$5$ is optimal at $n=8$

For $a\in [-1,1{]}^8$ and $t\ge 6$, if $⟨a,x⟩\ge t$ and $⟨a,y⟩\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}\left(\genfrac{}{}{0ex}{}{8}{i}\right)=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 $\sqrt{2}$ 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/\sqrt{8}$, 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|S△T_i|$ 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.

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.