TY - JOUR
T1 - Six standard deviations suffice
AU - Spencer, Joel
N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 1985/6
Y1 - 1985/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84862598391&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84862598391&partnerID=8YFLogxK
U2 - 10.1090/S0002-9947-1985-0784009-0
DO - 10.1090/S0002-9947-1985-0784009-0
M3 - Article
AN - SCOPUS:84862598391
SN - 0002-9947
VL - 289
SP - 679
EP - 706
JO - Transactions of the American Mathematical Society
JF - Transactions of the American Mathematical Society
IS - 2
ER -