# 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.

## History

- The 1916 paper of Weyl on the uniform distribution of sequences in the unit interval
- The theorem of van Aardenne-Ehrenfest

## Classic theorems

- Axis-parallel rectangles in the plane (Roth, Schmidt)
- Discrepancy of half-planes (Alexander, Matoušek)
- Arithmetic progressions (Roth, Sarkozy, Beck, Matousek & Spencer)
- Beck–Fiala theorem
^{[1]} - Six Standard Deviations Suffice (Spencer)
^{[2]}

## Major open problems

- Axis-parallel 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 computer-assisted 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
*n*-point 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. ""Integer-making" theorems".
*Discrete Applied Mathematics*.**3**(1). doi:10.1016/0166-218x(81)90022-6. - ↑ 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 (2015-09-18). "The logarithmically averaged Chowla and Elliott conjectures for two-point 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 0-521-30792-9. - Chazelle, Bernard (2000).
*The Discrepancy Method: Randomness and Complexity*. New York: Cambridge University Press. ISBN 0-521-77093-9. - Matousek, Jiri (1999).
*Geometric Discrepancy: An Illustrated Guide*. Algorithms and combinatorics.**18**. Berlin: Springer. ISBN 3-540-65528-X.