Six Standard Deviations Suffice

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