Spencer discrepancy constant (“six standard deviations suffice”) ($C_{10c}$)

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

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

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,

$$\min_{x\in\{\pm 1\}^{17}}\lVert Ax\rVert_\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 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)

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

$$\min_{x\in\{\pm1\}^{8}}\lVert Ax\rVert_\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 $\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

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

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

• 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 (from the repository page)

• [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.

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 1.767767; best known upper bound 4.1 (3.65*). Values marked with an asterisk have minimal verification.

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]	Withdrawn. arXiv v2 (14 Apr 2026) comments: “the constant in Theorem 4.5 is corrected from 3.7 to 4.1”.
$4.1$	[PV2022]	v2 Theorem 4.5: $\lVert Ax\rVert_\infty\leqslant 4.1\sqrt{n}+O(1)$. Algorithmic.

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$.
$7/\sqrt{17}\approx 1.697749$	[L2026]	A 17 by 17 sign matrix with exact discrepancy $7$ ($16$ distinct rows, one repeated to square it).
$5/\sqrt{8}=\tfrac{5\sqrt2}{4}\approx 1.767767$	[H2026]	An 8 by 8 matrix over $\{-1,0,1\}$ with exact discrepancy $5$; column 8 is identically zero. Its eight rows are the perfect $[7,4]$ Hamming code: the sets $T_i$ below, together with their complements in $\{1,\dots,7\}$, are the 16 codewords, whose radius-1 balls partition $\{0,1\}^7$. Optimal at $n=8$; see below.