This question is about Joel Spencer's famous "six standard deviations" theorem. The theorem says that when $$ L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{in} x_n, \quad 1 \leq i \leq n, $$ are $n$ linear forms in $n$ variables with all $|a_{ij}| \leq 1$, then there exist numbers $\varepsilon_1,\dots,\varepsilon_n \in \{-1,+1\}$ such that $$ |L_i(\varepsilon_1,\dots,\varepsilon_n)| \leq K \sqrt{n} $$ for all $i$.

It is stated as Theorem 1 in:

Spencer, Joel. Six standard deviations suffice. Trans. Amer. Math. Soc. 289 (1985), no. 2, 679–706. Full text PDF (open access)

As noted at the end of the paper, the constant $K$ which Spencer obtained is actually $K=5.32$.

Question: does anybody know of a proof of the Theorem which gives a smaller value for the constant?

  • 9
    $\begingroup$ You should really include the statement of the theorem in your question. $\endgroup$ Jul 11 '14 at 7:30
  • 17
    $\begingroup$ It might be true that anyone who can help you knows the statement of the theorem. It might not, depending on how connected mathematics is. Either way, stating the result helps many other people who might view the question, and that is one of the goals of MO. $\endgroup$ Jul 11 '14 at 8:59
  • 3
    $\begingroup$ I checked the papers and reviews in MathSciNet which quote Spencer's paper. None of these mention an improved constant, so my guess is that Spencer's value is still the best. Asking Spencer himself might help as well. $\endgroup$
    – GH from MO
    Jul 11 '14 at 12:34
  • 2
    $\begingroup$ The second-to-last paragraph on page 705 (27 of the pdf) mentions that with similar techniques one might get a slightly better $K$ via optimization, however anything significantly better would likely require a different approach. $\endgroup$
    – Alex R.
    Jul 11 '14 at 18:04
  • 5
    $\begingroup$ @Kurisuto_Asutora: the standard lower bound is $.5\sqrt{n}$ for Hadamard set systems. $\endgroup$
    – Nik Weaver
    Jul 14 '14 at 1:34

Having done the original result it is exciting to see work on the constant. My 5.32 was certainly not meant to be best possible. For the lower bounds, using Hadamard Matrices (with coefficients +1,-1 as opposed to the set system with coefficients 0,1) gives a lower bound of K=1. -- js


In his Ph.D thesis, A. Belshaw finds $K=5.199$, but he also claims there that Kai Uwe Schmidt was able to get $K$ as low as $3.65$. The idea of the process is described in Section 5.6 although the actual computations rely on "personal communication".

See summit.sfu.ca/system/files/iritems1/13657/etd8131_ABelshaw.pdf

  • 5
    $\begingroup$ It looks like Schmidt's argument is included in Section 5.6 of the linked thesis. $\endgroup$
    – Mark Lewko
    Jan 11 '18 at 22:32
  • $\begingroup$ Thanks, I stood stuck at the first mention of "personal communication". $\endgroup$ Jan 11 '18 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.