Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Six standard deviations suffice

Author: Joel Spencer
Journal: Trans. Amer. Math. Soc. 289 (1985), 679-706
MSC: Primary 05A05
MathSciNet review: 784009
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given $n$ sets on $n$ elements it is shown that there exists a two-coloring such that all sets have discrepancy at most $K{n^{1/2}}$, $K$ an absolute constant. This improves the basic probabilistic method with which $K = c{(\ln 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 ${p_1}, \ldots ,{p_n} \in \{ 0,1\}$ may be approximated by ${\varepsilon _1}, \ldots ,{\varepsilon _n} \in \{ 0,1\}$ so that the forms have small error.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A05

Retrieve articles in all journals with MSC: 05A05

Additional Information

Article copyright: © Copyright 1985 American Mathematical Society