In mathematics, the Erdős–Turán inequality bounds the distance between a probability measure on the circle and the Lebesgue measure, in terms of Fourier coefficients. It was proved by Paul Erdős and Pál Turán in 1948. Let μ be a probability measure on the unit circle R/Z. The Erdős–Turán inequality states that, for any natural number n,
sup A | μ ( A ) − m e s A | ≤ C ( 1 n + ∑ k = 1 n | μ ^ ( k ) | k ) , {\displaystyle \sup _{A}\left|\mu (A)-\mathrm {mes} \,A\right|\leq C\left({\frac {1}{n}}+\sum _{k=1}^{n}{\frac {|{\hat {\mu }}(k)|}{k}}\right),}
where the supremum is over all arcs A ⊂ R/Z of the unit circle, mes stands for the Lebesgue measure,
μ ^ ( k ) = ∫ exp ( 2 π i k θ ) d μ ( θ ) {\displaystyle {\hat {\mu }}(k)=\int \exp(2\pi ik\theta )\,d\mu (\theta )}
are the Fourier coefficients of μ, and C > 0 is a numerical constant.
Application to discrepancy Let s1, s2, s3 ... ∈ R be a sequence. The Erdős–Turán inequality applied to the measure
μ m ( S ) = 1 m # { 1 ≤ j ≤ m | s j m o d 1 ∈ S } , S ⊂ [ 0 , 1 ) , {\displaystyle \mu _{m}(S)={\frac {1}{m}}\#\{1\leq j\leq m\,|\,s_{j}\,\mathrm {mod} \,1\in S\},\quad S\subset [0,1),}
yields the following bound for the discrepancy:
D ( m ) ( = sup 0 ≤ a ≤ b ≤ 1 | m − 1 # { 1 ≤ j ≤ m | a ≤ s j m o d 1 ≤ b } − ( b − a ) | ) ≤ C ( 1 n + 1 m ∑ k = 1 n 1 k | ∑ j = 1 m e 2 π i s j k | ) . ( 1 ) {\displaystyle {\begin{aligned}D(m)&\left(=\sup _{0\leq a\leq b\leq 1}{\Big |}m^{-1}\#\{1\leq j\leq m\,|\,a\leq s_{j}\,\mathrm {mod} \,1\leq b\}-(b-a){\Big |}\right)\\[8pt]&\leq C\left({\frac {1}{n}}+{\frac {1}{m}}\sum _{k=1}^{n}{\frac {1}{k}}\left|\sum _{j=1}^{m}e^{2\pi is_{j}k}\right|\right).\end{aligned}}\qquad (1)}
This inequality holds for arbitrary natural numbers m,n, and gives a quantitative form of Weyl's criterion for equidistribution. A multi-dimensional variant of (1) is known as the Erdős–Turán–Koksma inequality.
Notes
Additional references Harman, Glyn (1998). Metric Number Theory. London Mathematical Society Monographs. New Series. Vol. 18. Clarendon Press. ISBN 0-19-850083-1. Zbl 1081.11057.