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

A significant event in the history of discrepancy theory was the 1916 paper of Weyl on the uniform distribution of sequences in the unit interval.^{[1]}

## Theorems

Discrepancy theory is based on the following classic theorems:

- The theorem of van Aardenne–Ehrenfest
- 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
^{[2]} - Six Standard Deviations Suffice (Spencer)
^{[3]}

## Major open problems

The unsolved problems relating to discrepancy theory include:

- Axis-parallel rectangles in dimensions three and higher (folklore)
- Komlós conjecture
- Heilbronn triangle problem on the minimum area of a triangle determined by three points from an
*n*-point set

## Applications

Applications for discrepancy theory include:

- Numerical integration: Monte Carlo methods in high dimensions.
- Computational geometry: Divide-and-conquer algorithm.
- Image processing: Halftoning

## See also

## References

- ↑ Weyl, Hermann (1 September 1916). "Über die Gleichverteilung von Zahlen mod. Eins" (in de).
*Mathematische Annalen***77**(3): 313–352. doi:10.1007/BF01475864. ISSN 1432-1807. https://doi.org/10.1007/BF01475864. - ↑ József Beck and Tibor Fiala. ""Integer-making" theorems".
*Discrete Applied Mathematics***3**(1): 1–8. 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.

## 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. https://archive.org/details/discrepancymetho0000chaz. - Matousek, Jiri (1999).
*Geometric Discrepancy: An Illustrated Guide*. Algorithms and combinatorics.**18**. Berlin: Springer. ISBN 3-540-65528-X.

Original source: https://en.wikipedia.org/wiki/ Discrepancy theory.
Read more |