View source for Equidistributed sequence

{{Short description|Type of number sequence}}
In [[mathematics]], a [[sequence]] (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...) of [[real number]]s is said to be '''equidistributed''', or '''uniformly distributed''', if the proportion of terms falling in a subinterval is proportional to the length of that subinterval.  Such sequences are studied in [[Diophantine approximation]] theory and have applications to [[Monte Carlo integration]].

==Definition==
A sequence (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...) of [[real number]]s is said to be ''equidistributed'' on a non-degenerate [[Interval (mathematics)|interval]] [''a'', ''b''] if for every subinterval [''c'', ''d''{{space|hair}}] of [''a'', ''b''] we have
:<math>\lim_{n\to\infty}{ \left|\{\,s_1,\dots,s_n \,\} \cap [c,d] \right| \over n}={d-c \over b-a} . </math>
(Here, the notation |{''s''<sub>1</sub>,...,''s''<sub>''n''</sub>} ∩ [''c'', ''d''{{space|hair}}]| denotes the number of elements, out of the first ''n'' elements of the sequence, that are between ''c'' and ''d''.)

For example, if a sequence is equidistributed in [0,&nbsp;2], since the interval [0.5,&nbsp;0.9] occupies 1/5 of the length of the interval [0,&nbsp;2], as ''n'' becomes large, the proportion of the first ''n'' 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''<sub>''n''</sub>) is a sequence of [[random variable]]s; rather, it is a determinate sequence of real numbers.

===Discrepancy===
We define the '''discrepancy''' ''D''<sub>''N''</sub> for a sequence (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...) with respect to the interval [''a'',&nbsp;''b''] as

:<math>D_N = \sup_{a \le c \le d \le b} \left\vert \frac{\left|\{\,s_1,\dots,s_N \,\} \cap [c,d] \right|}{N} - \frac{d-c}{b-a} \right\vert .</math>

A sequence is thus equidistributed if the discrepancy ''D''<sub>''N''</sub> tends to zero as ''N'' 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, see [[low-discrepancy sequence]].

===Riemann integral criterion for equidistribution===
Recall that if ''f'' is a [[Function (mathematics)|function]] having a [[Riemann integral]] in the interval [''a'', ''b''], then its integral is the limit of [[Riemann sum]]s taken by sampling the function ''f'' in a [[Set (mathematics)|set]] 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<ref>Kuipers & Niederreiter (2006) pp. 2–3</ref> for an equidistributed sequence:

Suppose (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...) is a sequence contained in the interval [''a'', ''b'']. Then the following conditions are equivalent:
# The sequence is equidistributed on [''a'', ''b''].
# For every Riemann-integrable ([[Complex-valued function|complex-valued]]) function {{nowrap|''f'' : [''a'', ''b''] → <math>\mathbb{C}</math>}}, the following limit holds:

:: <math>\lim_{N \to \infty}\frac{1}{N}\sum_{n=1}^{N} f\left(s_n\right) = \frac{1}{b-a}\int_a^b f(x)\,dx</math>

:{| class="toccolours collapsible collapsed" width="90%" style="text-align:left"
!Proof
|-
|First note that the definition of an equidistributed sequence is equivalent to the integral criterion whenever ''f'' is the [[indicator function]] of an interval: If ''f'' = '''1'''<sub>[''c'', ''d'']</sub>, 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 <math>\textstyle\frac{d-c}{b-a}.</math>

This means 2 ⇒ 1 (since indicator functions are Riemann-integrable), and 1 ⇒ 2 for ''f'' 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 are ''linear'' in ''f'', and therefore the criterion holds for [[linear combination]]s of interval indicators, that is, [[step function]]s.

To show it holds for ''f'' being a general Riemann-integrable function, first assume ''f'' is real-valued. Then by using [[Darboux integral|Darboux's definition]] of the integral, we have for every ''ε''&nbsp;>&nbsp;0 two step functions ''f''<sub>1</sub> and ''f''<sub>2</sub> such that ''f''<sub>1</sub>&nbsp;≤&nbsp;''f''&nbsp;≤&nbsp;''f''<sub>2</sub> and <math>\textstyle\int_a^b (f_2(x) - f_1(x))\,dx \le \varepsilon(b-a).</math> Notice that:
:<math>\frac{1}{b-a}\int_a^b f_1(x)\,dx = \lim_{N\to\infty} \frac 1 N \sum_{n=1}^N f_1(s_n) \le \liminf_{N\to\infty} \frac 1 N \sum_{n=1}^N f(s_n)</math>
:<math>\frac{1}{b-a}\int_a^b f_2(x)\,dx = \lim_{N\to\infty} \frac 1 N \sum_{n=1}^N f_2(s_n) \ge \limsup_{N\to\infty} \frac 1 N \sum_{n=1}^N f(s_n)</math>
By subtracting, we see that the [[limit superior and limit inferior]] of <math>\textstyle \frac 1 N \sum_{n=1}^N f(s_n)</math> 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 as ''f''&nbsp;=&nbsp;''u'' + ''vi'', where ''u'', ''v'' are real-valued and Riemann-integrable.&nbsp;[[Q.E.D.|∎]]
|}
This criterion leads to the idea of [[Monte-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 the [[Lebesgue integral]] is considered and ''f'' is taken to be in [[Lp space|''L''<sup>1</sup>]], then this criterion fails. As a [[counterexample]], take ''f'' to be the [[indicator 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 is [[Countable set|countable]], so ''f'' is zero [[almost everywhere]].

In fact, the '''de Bruijn–Post Theorem''' states the converse of the above criterion: If ''f'' is a function such that the criterion above holds for any equidistributed sequence in [''a'', ''b''], then ''f'' is Riemann-integrable in [''a'', ''b''].<ref>http://math.uga.edu/~pete/udnotes.pdf, Theorem 8</ref>

==Equidistribution modulo 1==
A sequence (''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub>, ...) of real numbers is said to be '''equidistributed modulo 1''' or '''uniformly distributed modulo 1''' if the sequence of the [[fractional part]]s of ''a''<sub>''n''</sub>, denoted by (''a''<sub>''n''</sub>) or by ''a''<sub>''n''</sub>&nbsp;−&nbsp;⌊''a''<sub>''n''</sub>⌋, is equidistributed in the interval [0, 1].

===Examples===
[[File:Van der Corput sequence 999.svg|thumb|330px<!-- Use a multiple of 11 to reduce aliasing artifact -->|Illustration of the filling of the unit interval (''x''-axis) using the first ''n'' terms of the Van der Corput sequence, for ''n'' from 0 to 999 (''y''-axis). Gradation in colour is due to aliasing.]]
* The [[equidistribution theorem]]: The sequence of all multiples of an [[Irrational number|irrational]] ''α'',
::0, ''α'', 2''α'', 3''α'', 4''α'', ...
:is equidistributed modulo 1.<ref name=KN8>Kuipers & Niederreiter (2006) p.&nbsp;8</ref>
* More generally, if ''p'' is a [[polynomial]] with at least one coefficient other than the [[constant term]] irrational then the sequence ''p''(''n'') is uniformly distributed modulo 1.

This was proven by Weyl and is an application of van der Corput's difference theorem.<ref name=KN27>Kuipers & Niederreiter (2006) p.&nbsp;27</ref>

* The sequence log(''n'') is ''not'' uniformly distributed modulo 1.<ref name=KN8/> This fact is related to [[Benford's law]].
* The sequence of all multiples of an irrational ''α'' by successive [[prime number]]s,
::2''α'', 3''α'', 5''α'', 7''α'', 11''α'', ...
:is equidistributed modulo 1.  This is a famous theorem of [[analytic number theory]], published by [[I. M. Vinogradov]] in 1948.<ref name=KN129>Kuipers & Niederreiter (2006) p.&nbsp;129</ref>
* The [[van der Corput sequence]] is equidistributed.<ref name=KN127>Kuipers & Niederreiter (2006) p.&nbsp;127</ref>

===Weyl's criterion===
'''Weyl's criterion''' states that the sequence ''a''<sub>''n''</sub> is equidistributed modulo 1 [[if and only if]] for all non-zero [[integer]]s ℓ,
:<math>\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}e^{2\pi i \ell a_j}=0.</math>
The criterion is named after, and was first formulated by, [[Hermann Weyl]].<ref name=Weyl16>{{cite journal|last=Weyl|first=H.|author-link=Hermann Weyl|title=Über die Gleichverteilung von Zahlen mod. Eins |language=de |trans-title=On the distribution of numbers modulo one |journal=Math. Ann.|date=September 1916|volume=77|issue=3|pages=313–352 | doi=10.1007/BF01475864 |s2cid=123470919 |url=http://www.fuchs-braun.com/media/3ed54b58b68a224cffff80dffffffff1.pdf}}</ref> It allows equidistribution questions to be reduced to bounds on [[exponential sum]]s, a fundamental and general method.

:{| class="toccolours collapsible collapsed" width="90%" style="text-align:left"
!Sketch of proof
|-
|If the sequence is equidistributed modulo 1, then we can apply the Riemann integral criterion (described above) on the function <math>\textstyle f(x) = e^{2\pi i \ell x},</math> 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 functions ''f'' as above, and by linearity of the criterion, it holds for ''f'' being any [[trigonometric polynomial]]. By the [[Stone–Weierstrass theorem]] and an approximation argument, this extends to any ''continuous'' function ''f''.

Finally, let ''f'' be the indicator function of an interval. It is possible to bound ''f'' 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 any ''interval indicator'' function ''f'', thereby proving equidistribution modulo 1 of the given sequence.&nbsp;[[Q.E.D.|∎]]
|}

====Generalizations====
* A quantitative form of Weyl's criterion is given by the [[Erdős–Turán inequality]].
* Weyl's criterion extends naturally to higher [[dimension]]s, assuming the natural generalization of the definition of equidistribution modulo 1:

The sequence ''v''<sub>''n''</sub> of vectors in '''R'''<sup>''k''</sup> is equidistributed modulo 1 if and only if for any non-zero vector ℓ&nbsp;∈&nbsp;'''Z'''<sup>''k''</sup>,

: <math>\lim_{n\to\infty}\frac{1}{n}\sum_{j=0}^{n-1}e^{2\pi i \ell \cdot v_j}=0.</math>

====Example of usage====
Weyl's criterion can be used to easily prove the [[equidistribution theorem]], stating that the sequence of multiples 0, ''α'', 2''α'', 3''α'', ... of some real number ''α'' is equidistributed modulo 1 if and only if ''α'' is irrational.<ref name=KN8/>

Suppose ''α'' is irrational and denote our sequence by ''a''<sub>''j''</sub>&nbsp;=&nbsp;''jα'' (where ''j'' starts from 0, to simplify the formula later). Let ''ℓ''&nbsp;≠&nbsp;0 be an integer. Since ''α'' is irrational, ''ℓα'' can never be an integer, so <math display=inline>e^{2\pi i \ell \alpha}</math> can never be&nbsp;1. Using the formula for the sum of a finite [[geometric series]],
:<math>\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|},</math>
a finite bound that does not depend on ''n''. Therefore, after dividing by ''n'' and letting ''n'' tend to infinity, the left hand side tends to zero, and Weyl's criterion is satisfied.

Conversely, notice that if ''α'' is [[Rational number|rational]] then this sequence is not equidistributed modulo 1, because there are only a finite number of options for the fractional part of ''a''<sub>''j''</sub>&nbsp;=&nbsp;''jα''.
===Complete uniform distribution===
A sequence <math>(a_1,a_2,\dots) </math> of real numbers is said to be ''k-uniformly    distributed mod 1'' if not only the sequence of fractional parts <math>a_n':=a_n-[a_n]</math> is uniformly distributed in <math>[0,1]</math> but also the sequence <math>(b_1,b_2,\dots)</math>, where <math>b_n</math> is defined as <math>b_n:= (a'_{n+1}, \dots, a'_{n+k})\in [0,1]^k</math>, is uniformly distributed in <math>[0,1]^k</math>. 

A sequence <math>(a_1,a_2,\dots) </math> of real numbers is said to be ''completely uniformly    distributed mod 1'' it is <math>k</math>-uniformly distributed for each natural number <math>k\ge 1</math>. 

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

===van der Corput's difference theorem===
A theorem of [[Johannes van der Corput]]<ref>{{Citation | last=van der Corput | first=J. | author-link=Johannes van der Corput | title=Diophantische Ungleichungen. I. Zur Gleichverteilung Modulo Eins | publisher=Springer Netherlands | year=1931 | journal=[[Acta Mathematica]] | issn=0001-5962 | volume=56 | pages=373–456 | doi=10.1007/BF02545780 | zbl=0001.20102 | jfm=57.0230.05 | doi-access=free }}</ref> states that if for each ''h'' the sequence ''s''<sub>''n''+''h''</sub> − ''s''<sub>''n''</sub> is uniformly distributed modulo 1, then so is ''s''<sub>''n''</sub>.<ref>Kuipers & Niederreiter (2006) p.&nbsp;26</ref><ref name=Mon18>Montgomery (1994) p.&nbsp;18</ref><ref name=Mon2001>{{cite book | last=Montgomery | first=Hugh L. | author-link=Hugh Montgomery (mathematician) | chapter=Harmonic analysis as found in analytic number theory | zbl=1001.11001 | editor1-last=Byrnes | editor1-first=James S. | title=Twentieth century harmonic analysis–a celebration. Proceedings of the NATO Advanced Study Institute, Il Ciocco, Italy, July 2–15, 2000 | location=Dordrecht | publisher=Kluwer Academic Publishers | series=NATO Sci. Ser. II, Math. Phys. Chem. | volume=33 | pages=271–293 | year=2001 | doi = 10.1007/978-94-010-0662-0_13 | isbn=978-0-7923-7169-4 | chapter-url=http://www.nato-us.org/analysis2000/papers/montgomery.pdf }}</ref>

A '''van der Corput set''' is a set ''H'' of integers such that if for each ''h'' in ''H'' the sequence ''s''<sub>''n''+''h''</sub> − ''s''<sub>''n''</sub> is uniformly distributed modulo 1, then so is s<sub>''n''</sub>.<ref name=Mon18/><ref name=Mon2001/>

===Metric theorems===
Metric theorems describe the behaviour of a parametrised sequence for [[almost all]] values of some parameter ''α'': that is, for values of ''α'' not lying in some exceptional set of [[Lebesgue measure]] zero.

* For any sequence of distinct integers ''b''<sub>''n''</sub>, the sequence (''b''<sub>''n''</sub>''α'') is equidistributed mod 1 for almost all values of ''α''.<ref name=Weyl16/>
* The sequence (''α''<sup>{{space|hair}}''n''</sup>) is equidistributed mod 1 for almost all values of ''α'' > 1.<ref>{{citation | url=http://www.numdam.org/item?id=CM_1935__2__250_0 | title=Ein mengentheoretischer Satz über die Gleichverteilung modulo Eins | first=J. F. | last=Koksma | author-link=Jurjen Ferdinand Koksma | journal=[[Compositio Mathematica]] | volume=2 | year=1935 | pages=250–258 | zbl=0012.01401  | jfm=61.0205.01 }}</ref>
It is not known whether the sequences (''e''<sup>''n''{{space|hair}}</sup>) or ({{pi}}<sup>{{space|hair}}''n''{{space|hair}}</sup>) are equidistributed mod&nbsp;1.  However it is known that the sequence (''α''<sup>''n''</sup>) is ''not'' equidistributed mod&nbsp;1 if ''α'' is a [[PV number]].

==Well-distributed sequence==
A sequence (''s''<sub>1</sub>, ''s''<sub>2</sub>, ''s''<sub>3</sub>, ...) of real numbers is said to be '''well-distributed''' on [''a'', ''b''] if for any subinterval [''c'', ''d''{{space|hair}}] of [''a'', ''b''] we have
:<math>\lim_{n\to\infty}{ \left|\{\,s_{k+1},\dots,s_{k+n} \,\} \cap [c,d] \right| \over n}={d-c \over b-a} </math>
''uniformly'' in ''k''.  Clearly every well-distributed sequence is uniformly distributed, but the converse does not hold.  The definition of well-distributed modulo 1 is analogous.

==Sequences equidistributed with respect to an arbitrary measure==
For an arbitrary [[probability measure space]] <math>(X,\mu)</math>, a sequence of points <math>(x_n)</math> is said to be equidistributed with respect to <math>\mu</math> if the mean of [[Dirac delta function|point measures]] [[Convergence of measures#Weak convergence of measures|converges weakly]] to <math>\mu</math>:<ref name=KN171>Kuipers & Niederreiter (2006) p.&nbsp;171</ref>
:<math>\frac{\sum_{k=1}^n \delta_{x_k}}{n}\Rightarrow \mu \ . </math>
In any [[Borel measure|Borel]] [[probability measure]] on a [[separable space|separable]], [[metrizable]] space, there exists an equidistributed sequence with respect to the measure; indeed, this follows immediately from the fact that such a space is [[standard probability space|standard]]. 

The general phenomenon of equidistribution comes up a lot for dynamical systems associated with [[Lie group]]s, for example in Margulis' solution to the [[Oppenheim conjecture]].

==See also==
*[[Equidistribution theorem]]
*[[Low-discrepancy sequence]]
*[[Erdős–Turán inequality]]

==Notes==
{{reflist}}

==References==
* {{cite book | first1=L. | last1=Kuipers | first2=H. | last2=Niederreiter | author2-link = Harald Niederreiter | title=Uniform Distribution of Sequences | publisher=Dover Publications | year=2006 | orig-year=1974 | isbn=0-486-45019-8 }}
* {{cite book | first1=L. | last1=Kuipers | first2=H. | last2=Niederreiter | author2-link = Harald Niederreiter | title=Uniform Distribution of Sequences | publisher=John Wiley & Sons Inc. | year=1974 | isbn=0-471-51045-9 | zbl=0281.10001 }}
* {{cite book | last=Montgomery | first=Hugh L. | author-link=Hugh Montgomery (mathematician) | title=Ten lectures on the interface between analytic number theory and harmonic analysis | series=Regional Conference Series in Mathematics | volume=84 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=1994 | isbn=0-8218-0737-4 | zbl=0814.11001 }}

==Further reading==
* {{cite book | editor1-last=Granville | editor1-first=Andrew | editor2-last=Rudnick | editor2-first=Zeév | zbl=1121.11004 | title=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 | location=Dordrecht | publisher=[[Springer-Verlag]] | isbn=978-1-4020-5403-7 | series=NATO Science Series II: Mathematics, Physics and Chemistry | volume=237 | year=2007 }}
* {{cite book | zbl= 1277.11010 | last=Tao | first=Terence | author-link=Terence Tao | title=Higher order Fourier analysis | series=[[Graduate Studies in Mathematics]] | volume=142 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2012 | isbn=978-0-8218-8986-2 | url=http://terrytao.wordpress.com/books/higher-order-fourier-analysis/ }}

==External links==
* {{MathWorld|title=Equidistributed Sequence|urlname=EquidistributedSequence}}
* {{MathWorld|title=Weyl's Criterion|urlname=WeylsCriterion}}
* {{PlanetMath|title=Weyl's Criterion|urlname=WeylsCriterion}}
* [http://www.maths.manchester.ac.uk/~cwalkden/ergodic-theory/lecture06.pdf Lecture notes by Charles Walkden with proof of Weyl's Criterion]

[[Category:Diophantine approximation]]
[[Category:Dynamical systems]]
[[Category:Ergodic theory]]