Inmathematics, asequence (s₁,s₂,s₃, ...) ofreal numbers is said to beequidistributed, oruniformly distributed, if the proportion of terms falling in a subinterval is proportional to the length of that subinterval. Such sequences are studied inDiophantine approximation theory and have applications toMonte Carlo integration.

A sequence (s₁,s₂,s₃, ...) ofreal numbers is said to beequidistributed on a non-degenerateinterval [a,b] if for every subinterval [c,d ] of [a,b] we have

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{\left|\{s_1,\dots ,s_n\}\cap [c,d]\right|}{n}=\frac{d-c}{b-a}.}$

(Here, the notation |{s₁,...,s_n} ∩ [c,d ]| denotes the number of elements, out of the firstn elements of the sequence, that are betweenc andd.)

For example, if a sequence is equidistributed in [0, 2], since the interval [0.5, 0.9] occupies 1/5 of the length of the interval [0, 2], asn becomes large, the proportion of the firstn members of the sequence which fall between 0.5 and 0.9 must approach 1/5. Loosely speaking, one could say that each member of the sequence is equally likely to fall anywhere in its range. However, this is not to say that (s_n) is a sequence ofrandom variables; rather, it is a determinate sequence of real numbers.

We define thediscrepancyD_N for a sequence (s₁,s₂,s₃, ...) with respect to the interval [a, b] as

${\displaystyle D_N=\underset{a\le c\le d\le b}{sup}\left|\frac{\left|\{s_1,\dots ,s_N\}\cap [c,d]\right|}{N}-\frac{d-c}{b-a}\right|.}$

A sequence is thus equidistributed if the discrepancyD_N tends to zero asN tends to infinity.

Equidistribution is a rather weak criterion to express the fact that a sequence fills the segment leaving no gaps. For example, the drawings of a random variable uniform over a segment will be equidistributed in the segment, but there will be large gaps compared to a sequence which first enumerates multiples of ε in the segment, for some small ε, in an appropriately chosen way, and then continues to do this for smaller and smaller values of ε. For stronger criteria and for constructions of sequences that are more evenly distributed, seelow-discrepancy sequence.

Recall that iff is afunction having aRiemann integral in the interval [a,b], then its integral is the limit ofRiemann sums taken by sampling the functionf in aset of points chosen from a fine partition of the interval. Therefore, if some sequence is equidistributed in [a,b], it is expected that this sequence can be used to calculate the integral of a Riemann-integrable function. This leads to the following criterion^[1] for an equidistributed sequence:

Suppose (s₁,s₂,s₃, ...) is a sequence contained in the interval [a,b]. Then the following conditions are equivalent:

1. The sequence is equidistributed on [a,b].
2. For every Riemann-integrable (complex-valued) functionf : [a,b] →${\displaystyle \mathbb{C}}$, the following limit holds:

${\displaystyle \underset{N\to \mathrm{\infty }}{lim}\frac{1}{N}\sum _{n=1}^{N}f\left(s_n\right)=\frac{1}{b-a}{\int }_a^{b}f(x)dx}$

Proof

First note that the definition of an equidistributed sequence is equivalent to the integral criterion wheneverf is theindicator function of an interval: Iff =1[c,d], then the left hand side is the proportion of points of the sequence falling in the interval [c,d], and the right hand side is exactly${\displaystyle \frac{d-c}{b-a}.}$ This means 2 ⇒ 1 (since indicator functions are Riemann-integrable), and 1 ⇒ 2 forf being an indicator function of an interval. It remains to assume that the integral criterion holds for indicator functions and prove that it holds for general Riemann-integrable functions as well. Note that both sides of the integral criterion equation arelinear inf, and therefore the criterion holds forlinear combinations of interval indicators, that is,step functions. To show it holds forf being a general Riemann-integrable function, first assumef is real-valued. Then by usingDarboux's definition of the integral, we have for everyε > 0 two step functionsf1 andf2 such thatf1 ≤ f ≤ f2 and${\displaystyle {\int }_a^b(f_2(x)-f_1(x))dx\le \epsilon (b-a).}$ Notice that: ${\displaystyle \frac{1}{b-a}{\int }_a^b{f}_1(x)dx=\underset{N\to \mathrm{\infty }}{lim}\frac{1}{N}\sum _{n=1}^N{f}_1(s_n)\le \underset{N\to \mathrm{\infty }}{lim inf}\frac{1}{N}\sum _{n=1}^{N}f(s_n)}$ ${\displaystyle \frac{1}{b-a}{\int }_a^b{f}_2(x)dx=\underset{N\to \mathrm{\infty }}{lim}\frac{1}{N}\sum _{n=1}^N{f}_2(s_n)\ge \underset{N\to \mathrm{\infty }}{lim sup}\frac{1}{N}\sum _{n=1}^{N}f(s_n)}$ By subtracting, we see that thelimit superior and limit inferior of${\displaystyle \frac{1}{N}\sum _{n=1}^{N}f(s_n)}$ differ by at most ε. Since ε is arbitrary, we have the existence of the limit, and by Darboux's definition of the integral, it is the correct limit. Finally, for complex-valued Riemann-integrable functions, the result follows again from linearity, and from the fact that every such function can be written asf = u +vi, whereu,v are real-valued and Riemann-integrable. ∎

This criterion leads to the idea ofMonte-Carlo integration, where integrals are computed by sampling the function over a sequence of random variables equidistributed in the interval.

It is not possible to generalize the integral criterion to a class of functions bigger than just the Riemann-integrable ones. For example, if theLebesgue integral is considered andf is taken to be inL¹, then this criterion fails. As acounterexample, takef to be theindicator function of some equidistributed sequence. Then in the criterion, the left hand side is always 1, whereas the right hand side is zero, because the sequence iscountable, sof is zeroalmost everywhere.

In fact, thede Bruijn–Post Theorem states the converse of the above criterion: Iff is a function such that the criterion above holds for any equidistributed sequence in [a,b], thenf is Riemann-integrable in [a,b].^[2]

A sequence (a₁,a₂,a₃, ...) of real numbers is said to beequidistributed modulo 1 oruniformly distributed modulo 1 if the sequence of thefractional parts ofa_n, denoted by (a_n) or bya_n − ⌊a_n⌋, is equidistributed in the interval [0, 1].

• Theequidistribution theorem: The sequence of all multiples of anirrationalα,

0,α, 2α, 3α, 4α, ...

is equidistributed modulo 1.^[3]

• More generally, ifp is apolynomial with at least one coefficient other than theconstant term irrational then the sequencep(n) is uniformly distributed modulo 1.

This was proven by Weyl and is an application of van der Corput's difference theorem.^[4]

• The sequence log(n) isnot uniformly distributed modulo 1.^[3] This fact is related toBenford's law.
• The sequence of all multiples of an irrationalα by successiveprime numbers,

2α, 3α, 5α, 7α, 11α, ...

is equidistributed modulo 1. This is a famous theorem ofanalytic number theory, published byI. M. Vinogradov in 1948.^[5]

• Thevan der Corput sequence is equidistributed.^[6]

Weyl's criterion states that the sequencea_n is equidistributed modulo 1if and only if for all non-zerointegers ℓ,

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\sum _{j=1}^n{e}^{2\pi i\ell a_j}=0.}$

The criterion is named after, and was first formulated by,Hermann Weyl.^[7] It allows equidistribution questions to be reduced to bounds onexponential sums, a fundamental and general method.

Sketch of proof

If the sequence is equidistributed modulo 1, then we can apply the Riemann integral criterion (described above) on the function${\displaystyle f(x)=e^{2\pi i\ell x},}$ which has integral zero on the interval [0, 1]. This gives Weyl's criterion immediately. Conversely, suppose Weyl's criterion holds. Then the Riemann integral criterion holds for functionsf as above, and by linearity of the criterion, it holds forf being anytrigonometric polynomial. By theStone–Weierstrass theorem and an approximation argument, this extends to anycontinuous functionf. Finally, letf be the indicator function of an interval. It is possible to boundf from above and below by two continuous functions on the interval, whose integrals differ by an arbitrary ε. By an argument similar to the proof of the Riemann integral criterion, it is possible to extend the result to anyinterval indicator functionf, thereby proving equidistribution modulo 1 of the given sequence. ∎

• A quantitative form of Weyl's criterion is given by theErdős–Turán inequality.
• Weyl's criterion extends naturally to higherdimensions, assuming the natural generalization of the definition of equidistribution modulo 1:

The sequencev_n of vectors inR^k is equidistributed modulo 1 if and only if for any non-zero vector ℓ ∈ Z^k,

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\sum _{j=0}^{n-1}{e}^{2\pi i\ell \cdot v_j}=0.}$

Weyl's criterion can be used to easily prove theequidistribution theorem, stating that the sequence of multiples 0,α, 2α, 3α, ... of some real numberα is equidistributed modulo 1 if and only ifα is irrational.^[3]

Supposeα is irrational and denote our sequence bya_j = jα (wherej starts from 0, to simplify the formula later). Letℓ ≠ 0 be an integer. Sinceα is irrational,ℓα can never be an integer, so$e^{2\pi i\ell \alpha }$ can never be 1. Using the formula for the sum of a finitegeometric series,

${\displaystyle \left|\sum _{j=0}^{n-1}{e}^{2\pi i\ell j\alpha }\right|=\left|\sum _{j=0}^{n-1}{\left(e^{2\pi i\ell \alpha }\right)}^j\right|=\left|\frac{1-e^{2\pi i\ell n\alpha }}{1-e^{2\pi i\ell \alpha }}\right|\le \frac{2}{\left|1-e^{2\pi i\ell \alpha }\right|},}$

a finite bound that does not depend onn. Therefore, after dividing byn and lettingn tend to infinity, the left hand side tends to zero, and Weyl's criterion is satisfied.

Conversely, notice that ifα isrational then this sequence is not equidistributed modulo 1, because there are only a finite number of options for the fractional part ofa_j = jα.

A sequence${\displaystyle (a_1,a_2,\dots )}$ of real numbers is said to bek-uniformly distributed mod 1 if not only the sequence of fractional parts${\displaystyle a_n^{\prime }:=a_n-[a_n]}$ is uniformly distributed in${\displaystyle [0,1]}$ but also the sequence${\displaystyle (b_1,b_2,\dots )}$, where${\displaystyle b_n}$ is defined as${\displaystyle b_n:=(a_{n+1}^{\prime },\dots ,a_{n+k}^{\prime })\in [0,1{]}^k}$, is uniformly distributed in${\displaystyle [0,1{]}^k}$.

A sequence${\displaystyle (a_1,a_2,\dots )}$ of real numbers is said to becompletely uniformly distributed mod 1 it is${\displaystyle k}$-uniformly distributed for each natural number${\displaystyle k\ge 1}$.

For example, the sequence${\displaystyle (\alpha ,2\alpha ,\dots )}$ is uniformly distributed mod 1 (or 1-uniformly distributed) for any irrational number${\displaystyle \alpha }$, but is never even 2-uniformly distributed. In contrast, the sequence${\displaystyle (\alpha ,{\alpha }^2,{\alpha }^3,\dots )}$ is completely uniformly distributed for almost all${\displaystyle \alpha >1}$ (i.e., for all${\displaystyle \alpha }$ except for a set of measure 0).

A theorem ofJohannes van der Corput^[8] states that if for eachh the sequences_n+h −s_n is uniformly distributed modulo 1, then so iss_n.^[9][10][11]

Avan der Corput set is a setH of integers such that if for eachh inH the sequences_n+h −s_n is uniformly distributed modulo 1, then so is s_n.^[10][11]

Metric theorems describe the behaviour of a parametrised sequence foralmost all values of some parameterα: that is, for values ofα not lying in some exceptional set ofLebesgue measure zero.

• For any sequence of distinct integersb_n, the sequence (b_nα) is equidistributed mod 1 for almost all values ofα.^[7]
• The sequence (αⁿ) is equidistributed mod 1 for almost all values ofα > 1.^[12]

It is not known whether the sequences (eⁿ) or (πⁿ) are equidistributed mod 1. However it is known that the sequence (αⁿ) isnot equidistributed mod 1 ifα is aPV number.

A sequence (s₁,s₂,s₃, ...) of real numbers is said to bewell-distributed on [a,b] if for any subinterval [c,d ] of [a,b] we have

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{\left|\{s_{k+1},\dots ,s_{k+n}\}\cap [c,d]\right|}{n}=\frac{d-c}{b-a}}$

uniformly ink. Clearly every well-distributed sequence is uniformly distributed, but the converse does not hold. The definition of well-distributed modulo 1 is analogous.

For an arbitraryprobability measure space${\displaystyle (X,\mu )}$, a sequence of points${\displaystyle (x_n)}$ is said to be equidistributed with respect to${\displaystyle \mu }$ if the mean ofpoint measuresconverges weakly to${\displaystyle \mu }$:^[13]

${\displaystyle \frac{\sum _{k=1}^n{\delta }_{x_k}}{n}\Rightarrow \mu .}$

In anyBorelprobability measure on aseparable,metrizable space, there exists an equidistributed sequence with respect to the measure; indeed, this follows immediately from the fact that such a space isstandard.

The general phenomenon of equidistribution comes up a lot for dynamical systems associated withLie groups, for example in Margulis' solution to theOppenheim conjecture.

• Equidistribution theorem
• Low-discrepancy sequence
• Erdős–Turán inequality

• Kuipers, L.;Niederreiter, H. (2006) [1974].Uniform Distribution of Sequences. Dover Publications.ISBN 0-486-45019-8.
• Kuipers, L.;Niederreiter, H. (1974).Uniform Distribution of Sequences. John Wiley & Sons Inc.ISBN 0-471-51045-9.Zbl 0281.10001.
• Montgomery, Hugh L. (1994).Ten lectures on the interface between analytic number theory and harmonic analysis. Regional Conference Series in Mathematics. Vol. 84. Providence, RI:American Mathematical Society.ISBN 0-8218-0737-4.Zbl 0814.11001.

• Granville, Andrew; Rudnick, Zeév, eds. (2007).Equidistribution in number theory, an introduction. Proceedings of the NATO Advanced Study Institute on equidistribution in number theory, Montréal, Canada, July 11–22, 2005. NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 237. Dordrecht:Springer-Verlag.ISBN 978-1-4020-5403-7.Zbl 1121.11004.
• Tao, Terence (2012).Higher order Fourier analysis.Graduate Studies in Mathematics. Vol. 142. Providence, RI:American Mathematical Society.ISBN 978-0-8218-8986-2.Zbl 1277.11010.

• Weisstein, Eric W."Equidistributed Sequence".MathWorld.
• Weisstein, Eric W."Weyl's Criterion".MathWorld.
• Weyl's Criterion atPlanetMath.
• Lecture notes by Charles Walkden with proof of Weyl's Criterion

• Diophantine approximation
• Dynamical systems
• Ergodic theory

• CS1 German-language sources (de)
• Articles with short description
• Short description matches Wikidata