Six standard deviations suffice

Joel Spencer

Research output: Contribution to journalArticlepeer-review


Given n sets on n elements it is shown that there exists a two-coloring such that all sets have discrepancy at most Kn1/2, K an absolute constant. This improves the basic probabilistic method with which K = c(1n n)1/2. The result is extended to n finite sets of arbitrary size. Probabilistic techniques are melded with the pigeonhole principle. An alternate proof of the existence of Rudin-Shapiro functions is given, showing that they are exponential in number. Given n linear forms in n variables with all coefficients in [-1, +1] it is shown that initial values p1……, pnÎ (0, 1) may be approximated by e1,&, enÎ (0, 1) so that the forms have small error.

Original languageEnglish (US)
Pages (from-to)679-706
Number of pages28
JournalTransactions of the American Mathematical Society
Issue number2
StatePublished - Jun 1985

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Six standard deviations suffice'. Together they form a unique fingerprint.

Cite this