Six standard deviations suffice

Author:
Joel Spencer

Journal:
Trans. Amer. Math. Soc. **289** (1985), 679-706

MSC:
Primary 05A05

DOI:
https://doi.org/10.1090/S0002-9947-1985-0784009-0

MathSciNet review:
784009

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given sets on elements it is shown that there exists a two-coloring such that all sets have discrepancy at most , an absolute constant. This improves the basic probabilistic method with which . 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 it is shown that initial values may be approximated by so that the forms have small error.

**[1]**J. Beck and T. Fiala,*Integer-making theorems*, Discrete Appl. Math.**3**(1981), 1-8. MR**604260 (82d:05088)****[2]**J. Beck and J. Spencer,*Integral approximation sequences*, Math. Programming**30**(1984), 88-98. MR**755116 (85j:11074)****[3]**D. Kleitman,*On a combinatorial conjecture of Erdös*, J. Combin. Theory**1**(1966), 209-214. MR**0200179 (34:78)****[4]**J. Olson and J. Spencer,*Balancing families of sets*, J. Combin. Theory Ser. A**25**(1978), 29-37. MR**0480052 (58:251)****[5]**W. Rudin,*Some theorems on Fourier coefficients*, Proc. Amer. Math. Soc.**10**(1959), 855-859. MR**0116184 (22:6979)****[6]**J. Spencer,*Sequences with small discrepency relative to**events*, Compositio Math.**47**(1982), 365-392. MR**681615 (84c:10050)**

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

Retrieve articles in all journals with MSC: 05A05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1985-0784009-0

Article copyright:
© Copyright 1985
American Mathematical Society