In mathematics, discrepancy theory describes the deviation of a situation from the state one would like it to be. It is also called 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

Ramsey theory

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...

 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
  Tatyana Pavlovna Ehrenfest
  Tatyana Pavlovna Ehrenfest, later van Aardenne-Ehrenfest, was a Dutch mathematician. She was the daughter of Paul Ehrenfest and Tatyana Alexeyevna Afanasyeva .Tatyana Ehrenfest was born in Vienna, and spent her childhood in St Petersburg...
  
  

Classic theorems

• Axis-parallel rectangles in the plane (Roth
  Klaus Roth
  Klaus Friedrich Roth is a British mathematician known for work on diophantine approximation, the large sieve, and irregularities of distribution. He was born in Breslau, Prussia, but raised and educated in the UK. He graduated from Peterhouse, Cambridge in 1945...
  
  , Schmidt)
• Discrepancy of half-planes (Alexander, Matoušek
  Jirí Matoušek (mathematician)
  Jiří Matoušek is a Czech mathematician working in computational geometry. He is a professor at Charles University in Prague and is the author of several textbooks and research monographs....
  
  )
• Arithmetic progressions (Roth, Sarkozy, Beck
  József Beck
  József Beck is a Harold H. Martin Professor of Mathematics at Rutgers University.His contributions to combinatorics include the partial colouring lemma and the Beck–Fiala theorem in discrepancy theory, the algorithmic version of the Lovász local lemma, the two extremes theorem in combinatorial...
  
  , Matousek & Spencer
  Joel Spencer
  Joel Spencer is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervision of Andrew Gleason...
  
  )
• Beck-Fiala theorem
• Six Standard Deviations Suffice (Spencer)

Major open problems

• Axis-parallel rectangles in dimensions three and higher (Folklore)
• Komlós
  János Komlós (mathematician)
  János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
  
   conjecture
• The three permutations problem (Beck) - disproved by Newman and Nikolov.
• Erdős discrepancy problem‎ - Homogeneous arithmetic progressions (Erdős
  Paul Erdos
  Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
  
  , $500)

Applications

• Numerical Integration: Monte Carlo methods in high dimensions.
• Computational Geometry: Divide and conquer algorithms.
• Image Processing: Halftoning