Discrepancy theory
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
(Learn how and when to remove this template message)

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 measuretheoretic and combinatorial settings. Just as Ramsey theory elucidates the impossibility of total disorder, discrepancy theory studies the deviations from total uniformity.
Contents
History
 The 1916 paper of Weyl on the uniform distribution of sequences in the unit interval
 The theorem of van AardenneEhrenfest
Classic theorems
 Axisparallel rectangles in the plane (Roth, Schmidt)
 Discrepancy of halfplanes (Alexander, Matoušek)
 Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
 Beck–Fiala theorem ^{[1]}
 Six Standard Deviations Suffice (Spencer)^{[2]}
Major open problems
 Axisparallel rectangles in dimensions three and higher (Folklore)
 Komlós conjecture
 The three permutations problem (Beck) – disproved by Newman and Nikolov.^{[3]}
 Erdős discrepancy problem – Homogeneous arithmetic progressions. The problem was stated by Erdős, who offered $500 for the proof or disproof of the conjecture. A computerassisted proof of a special case of the conjecture was published in February 2014.^{[4]} In September 2015, Terence Tao announced a proof of the conjecture.^{[5]}^{[6]}
 Heilbronn triangle problem on the minimum area of a triangle determined by three points from an npoint set
Applications
 Numerical Integration: Monte Carlo methods in high dimensions.
 Computational Geometry: Divide and conquer algorithms.
 Image Processing: Halftoning
See also
References
 ^ József Beck and Tibor Fiala. ""Integermaking" theorems". Discrete Applied Mathematics. 3 (1): 1–8. doi:10.1016/0166218x(81)900226.
 ^ 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.
 ^ http://front.math.ucdavis.edu/1104.2922
 ^ 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.
 ^ Tao, Terence (2015). "The Erdős discrepancy problem". arXiv:1509.05363 .
 ^ Tao, Terence (20150918). "The logarithmically averaged Chowla and Elliott conjectures for twopoint correlations; the Erdos discrepancy problem". What's new.
Further reading
 Beck, József; Chen, William W. L. (1987). Irregularities of Distribution. New York: Cambridge University Press. ISBN 0521307929.
 Chazelle, Bernard (2000). The Discrepancy Method: Randomness and Complexity. New York: Cambridge University Press. ISBN 0521770939.
 Matousek, Jiri (1999). Geometric Discrepancy: An Illustrated Guide. Algorithms and combinatorics. 18. Berlin: Springer. ISBN 354065528X.