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?

Improve this question
$\endgroup$
8
  • 9
    $\begingroup$ You should really include the statement of the theorem in your question. $\endgroup$
    – Neil Strickland
    Commented 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$
    – Douglas Zare
    Commented 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
    Commented 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.
    Commented 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
    Commented Jul 14, 2014 at 1:34

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I assume nobody have found an example set with $K>1$. $\endgroup$
    – Thomas Dybdahl Ahle
    Commented 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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .