Six standard deviations suffice

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.