Discrepancy theory: Difference between revisions

Revision as of 02:06, 28 February 2014

Latest revision as of 04:56, 16 August 2025

(53 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Theory of irregularities of distribution}}

{{cleanup|date=August 2008}}

{{more citations needed|date=January 2018}}

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 theory|measure-theoretic]] and [[Combinatorics|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 [[Hermann Weyl|Weyl]] on the uniform distribution of sequences in the unit interval.<ref>{{Cite journal|last1=Weyl|first1=Hermann|author1-link=Hermann Weyl|date=1 September 1916|title=Über die Gleichverteilung von Zahlen mod. Eins|trans-title=About the equal distribution of numbers|journal=Mathematische Annalen|language=de|volume=77|issue=3|pages=313–352|doi=10.1007/BF01475864|s2cid=123470919|issn=1432-1807|url=https://zenodo.org/record/2425535}}</ref>

== History ==

== HistoryTheorems ==

* The 1916 paper of [[H. Weyl|Weyl]] on the uniform distribution of sequences in the unit interval

Discrepancy theory is based on the following classic theorems:

* [[Geometric discrepancy theory]]

* The theorem of [[Tatyana Pavlovna Ehrenfest|van Aardenne-Ehrenfest]]

== Classic theorems ==

* Axis-parallel rectangles in the plane ([[Klaus Roth|Roth]], Schmidt)

* Discrepancy of half-planes (Alexander, [[Jiří Matoušek (mathematician)|Matoušek]])

* Arithmetic progressions (Roth, Sarkozy, [[Jozsef Beck|Beck]], Matousek & [[Joel Spencer|Spencer]])

* [[Beck–Fiala theorem]] <ref>{{cite journal

| title = “Integer"Integer-making”making" theorems

| journal = Discrete Applied Mathematics

| volume = 3

| issue = 1

| doi = 10.1016/0166-218x(81)90022-6

| author = József Beck and Tibor Fiala }}</ref>

| year = 1981

| pages=1–8| doi-access =free

}}</ref>

* Six Standard Deviations Suffice (Spencer)<ref>{{cite journal

|title = Six Standard Deviations Suffice

|author = Joel Spencer

|author-link = Joel Spencer

|journal = Transactions of the American Mathematical Society

|volume = 289

Line 32 ⟶ 35:

|publisher = Transactions of the American Mathematical Society, Vol. 289, No. 2

|jstor = 2000258

|doi-access= free

}}</ref>

== Major open problems ==

The unsolved problems relating to discrepancy theory include:

* Axis-parallel rectangles in dimensions three and higher (Folklorefolklore)

* [[János Komlós (mathematician)|Komlós]] conjecture

* The three permutations problem (Beck) – disproved by Newman and Nikolov.<ref>http://front.math.ucdavis.edu/1104.2922</ref>

* [[Erdős discrepancy problem]] – Homogeneous arithmetic progressions. The problem was stated by [[Paul Erdős|Erdős]]. He awarded $500 for the proof or disproof of the conjecture. The problem was solved eventualy in February 2014.<ref>{{cite paper

|title = A SAT Attack on the Erd̋os Discrepancy Conjecture

|author = Boris Konev and Alexei Lisitsa

|journal = Transactions of the American Mathematical Society

|date = 2014

|publisher = Department of Computer Science University of Liverpool, United Kingdom

}http://cgi.csc.liv.ac.uk/~konev/SAT14/sat14.pdf}</ref>

* [[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 Integrationintegration: [[Monte Carlo methodsmethod]]s in high dimensions.

* Computational Geometrygeometry: [[Divide -and -conquer algorithmsalgorithm]].

* Image Processingprocessing: [[Halftone|Halftoning]]

* Random trial formulation: [[Randomized controlled trial]]<ref>{{cite journal|last=Harshaw|first=Christopher| author2=Sävje, Fredrik | author3= Spielman, Daniel A | author4 = Zhang, Peng | title=Balancing covariates in randomized experiments with the Gram--Schmidt walk design | journal=Journal of the American Statistical Association | pages=2934–2946 | year=2024 |volume=119 |issue=548 |doi=10.1080/01621459.2023.2285474 | url= https://www.tandfonline.com/doi/full/10.1080/01621459.2023.2285474| arxiv=1911.03071 }}</ref><ref>{{cite video|last1=Spielman|first1=Daniel|date=11 May 2020|title= Using discrepancy theory to improve the design of randomized controlled trials|url= https://www.ias.edu/video/csdm/2020/0511-DanielSpielman}}</ref><ref>{{cite video|last1=Spielman|first1=Daniel|date=29 January 2021|title= Discrepancy Theory and Randomized Controlled Trials|url= https://www.youtube.com/watch?v=ZMRAeq-7hHU}}</ref>

== See also ==

*[[Discrepancy of hypergraphs]]

*[[Geometric discrepancy theory]]

== References ==

Line 61 ⟶ 59:

==Further reading==

*{{cite book |title=Irregularities of Distribution |last=Beck |first=József |authorlink= |coauthorsauthor2=Chen, William W. L. |year=1987 |publisher=Cambridge University Press |___location=New York |isbn=0-521-30792-9 |pages= |url= }}

*{{cite book |title=The Discrepancy Method: Randomness and Complexity |last=Chazelle |first=Bernard |authorlinkauthor-link=Bernard Chazelle |coauthors= |year=2000 |publisher=Cambridge University Press |___location=New York |isbn=0-521-77093-9 |pagesurl= https://archive.org/details/discrepancymetho0000chaz|url-access=registration }}

*{{cite book |title=Geometric Discrepancy: An Illustrated Guide |last=Matousek |first=Jiri |authorlink= |coauthors= |year=1999 |series=Algorithms and combinatorics |volume=18 |publisher=Springer |___location=Berlin |isbn=3-540-65528-X |pages= |url= }}

{{Authority control}}

[[Category:Diophantine approximation]]

[[Category:Unsolved problems in mathematics]]

[[Category:CombinatoricsDiscrepancy theory]]

[[Category:Measure theory]]