Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 Free Access

Abstract | References | Similar Articles | Additional Information

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


References [Enhancements On Off] (What's this?)

  • [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 $ n$ events, Compositio Math. 47 (1982), 365-392. MR 681615 (84c:10050)

Similar Articles

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

American Mathematical Society