Six standard deviations suffice

Author:
Joel Spencer

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

MSC:
Primary 05A05

MathSciNet review:
784009

Full-text PDF Free Access

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ózsef Beck and Tibor Fiala,*“Integer-making” theorems*, Discrete Appl. Math.**3**(1981), no. 1, 1–8. MR**604260**, 10.1016/0166-218X(81)90022-6**[2]**József Beck and Joel Spencer,*Integral approximation sequences*, Math. Programming**30**(1984), no. 1, 88–98. MR**755116**, 10.1007/BF02591800**[3]**Daniel J. Kleitman,*On a combinatorial conjecture of Erdős*, J. Combinatorial Theory**1**(1966), 209–214. MR**0200179****[4]**John E. Olson and Joel H. Spencer,*Balancing families of sets*, J. Combin. Theory Ser. A**25**(1978), no. 1, 29–37. MR**0480052****[5]**Walter Rudin,*Some theorems on Fourier coefficients*, Proc. Amer. Math. Soc.**10**(1959), 855–859. MR**0116184**, 10.1090/S0002-9939-1959-0116184-5**[6]**Joel Spencer,*Sequences with small discrepancy relative to 𝑛 events*, Compositio Math.**47**(1982), no. 3, 365–392. MR**681615**

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

Retrieve articles in all journals with MSC: 05A05

Additional Information

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

Article copyright:
© Copyright 1985
American Mathematical Society