Erdős–Turán inequality

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,

$\underset{A}{sup}|\mu (A)-\mathrm{m}\mathrm{e}\mathrm{s}A|\le C(\frac{1}{n}+\sum _{k=1}^n\frac{|\hat{\mu }(k)|}{k}),$

where the supremum is over all arcs A ⊂ R/Z of the unit circle, mes stands for the Lebesgue measure,

$\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 s₁, s₂, s₃ ... ∈ R be a sequence. The Erdős–Turán inequality applied to the measure

${\mu }_m(S)=\frac{1}{m}\mathrm{\#}\{1\le j\le m|s_j\mathrm{m}\mathrm{o}\mathrm{d}1\in S\},S\subset [0,1),$

yields the following bound for the discrepancy:

$\begin{array}{cc}D(m)& (=\underset{0\le a\le b\le 1}{sup}|m^{-1}\mathrm{\#}\{1\le j\le m|a\le s_j\mathrm{m}\mathrm{o}\mathrm{d}1\le b\}-(b-a)|)\\ & \le C(\frac{1}{n}+\frac{1}{m}\sum _{k=1}^n\frac{1}{k}\left|\sum _{j=1}^m{e}^{2\pi i{s}_{j}k}\right|).\end{array}(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.

Additional references

• Template:Cite book