Discrepancy theory

In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be in. It is also called the theory of irregularities of distribution. This refers to the theme of classical discrepancy theory, namely distributing points in some space such that they are evenly distributed with respect to some (mostly geometrically defined) subsets. The discrepancy (irregularity) measures how far a given distribution deviates from an ideal one.

Discrepancy theory can be described as the study of inevitable irregularities of distributions, in measure-theoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity.


Classic theorems

Major open problems


See also


  1. József Beck and Tibor Fiala. ""Integer-making" theorems". Discrete Applied Mathematics. 3 (1). doi:10.1016/0166-218x(81)90022-6.
  2. Joel Spencer (June 1985). "Six Standard Deviations Suffice". Transactions of the American Mathematical Society. Transactions of the American Mathematical Society, Vol. 289, No. 2. 289 (2): 679–706. doi:10.2307/2000258. JSTOR 2000258.
  3. http://front.math.ucdavis.edu/1104.2922
  4. Boris Konev and Alexei Lisitsa (2014). "A SAT Attack on the Erd̋os Discrepancy Conjecture" (PDF). Department of Computer Science University of Liverpool, United Kingdom. Retrieved 27 February 2014.
  5. Tao, Terence (2015). "The Erdős discrepancy problem". arXiv:1509.05363Freely accessible.
  6. Tao, Terence (2015-09-18). "The logarithmically averaged Chowla and Elliott conjectures for two-point correlations; the Erdos discrepancy problem". What's new.

Further reading

This article is issued from Wikipedia - version of the 6/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.