Six standard deviations suffice

Source abstract

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