24
$\begingroup$

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?

$\endgroup$
8
  • 9
    $\begingroup$ You should really include the statement of the theorem in your question. $\endgroup$ Jul 11, 2014 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, 2014 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, 2014 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, 2014 at 18:04
  • 5
    $\begingroup$ @Kurisuto_Asutora: the standard lower bound is $.5\sqrt{n}$ for Hadamard set systems. $\endgroup$
    – Nik Weaver
    Jul 14, 2014 at 1:34

2 Answers 2

19
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I assume nobody have found an example set with $K>1$. $\endgroup$ Jan 26, 2022 at 20:52
15
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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