Equidistributed sequence

Equidistributed sequenceMain

Community hub

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Equidistributed sequence

View on Wikipedia

from Wikipedia

Not found

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In mathematics, an equidistributed sequence is an infinite sequence of real numbers whose fractional parts are uniformly distributed in the unit interval [0,1), meaning that for any subinterval [a,b) ⊆ [0,1), the proportion of the first N terms whose fractional parts lie in [a,b) approaches b - a as N approaches infinity.^[1] This concept captures the idea of uniform spreading of points, ensuring that no subinterval is over- or under-represented in the limit.^[2] The foundational characterization of equidistribution is provided by Weyl's criterion, which states that a sequence {x_n} in [0,1) is equidistributed if and only if, for every nonzero integer k, the average (1/N) ∑_{n=1}^N exp(2πi k x_n) converges to 0 as N → ∞.^[1] This exponential sum condition offers a practical test for equidistribution, often applied using Fourier analysis, and generalizes to higher dimensions for multidimensional sequences.^[3] Originating from Hermann Weyl's work in 1916 on uniform distribution theory, the concept has roots in early 20th-century number theory and has been extended to probabilistic frameworks where sequences are equidistributed almost surely with respect to a parameter.^[3] Classic examples include the sequence of fractional parts {nα} for irrational α, which is equidistributed in [0,1) due to the dense and uniform wrapping of multiples of α modulo 1.^[4] Other notable cases are the fractional parts of n log 2, which arise in contexts like Benford's law for leading digits, and sequences generated by powers like {x^n} for almost all x > 1, as proven by Hardy and Littlewood in 1914.^[2] However, not all dense sequences are equidistributed; for instance, the fractional parts of ln n are dense in [0,1) but fail the uniformity condition.^[2] Equidistributed sequences play a central role in number theory for problems like Diophantine approximation and lattice point counting, in ergodic theory for studying mixing properties of dynamical systems, and in computational applications such as quasi-Monte Carlo integration for efficient numerical simulations.^[5] They also connect to concepts like low-discrepancy sequences, which enhance uniformity for finite prefixes, and have probabilistic interpretations where limiting frequencies match Lebesgue measure for almost every realization.^[3]

Fundamentals

Definition

An equidistributed sequence is a sequence of real numbers confined to the unit interval

[0,1)

that exhibits uniform distribution in an asymptotic sense. Formally, a sequence

(x_n)_{n=1}^\infty \subset [0,1)

is equidistributed modulo 1 if, for every subinterval

[a,b) \subseteq [0,1)

with

0 \leq a < b \leq 1

, the proportion of the first

N

terms lying within that subinterval approaches the length of the subinterval as

N

tends to infinity: \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \mathbf{1}_{[a,b)}(x_n) = b - a, $$ where $\mathbf{1}_{[a,b)}$ denotes the indicator function of the interval $[a,b)$. This condition ensures that the empirical distribution of the sequence converges weakly to the uniform distribution on $[0,1)$. The concept of equidistribution was introduced by Hermann Weyl in 1916, in the context of studying the uniform distribution of sequences modulo 1, particularly for polynomial sequences. Weyl's work formalized the idea that certain deterministic sequences can mimic the behavior of uniformly random points in the unit interval over long finite prefixes. A key property of equidistributed sequences is that they are necessarily dense in $[0,1)$, as the uniform limiting proportion precludes the sequence from avoiding any subinterval entirely in the limit. However, density is a weaker condition; a sequence can be dense in $[0,1)$ without being equidistributed if it disproportionately clusters in certain regions. Equidistribution thus provides a stronger notion of uniformity than mere density, distinguishing it from the probabilistic uniform distribution of a single point, which applies to individual realizations rather than the asymptotic behavior of an entire sequence. ### Equidistribution Modulo 1 The concept of equidistribution modulo 1 provides the primary framework for analyzing the uniform distribution of real sequences by projecting them onto the unit interval via fractional parts. For a sequence $(\alpha_n)_{n=1}^\infty$ in $\mathbb{R}$, the fractional part is defined as $\{\alpha_n\} = \alpha_n - \lfloor \alpha_n \rfloor \in [0,1)$. The original sequence is equidistributed modulo 1 if the sequence of fractional parts $(\{\alpha_n\})$ is equidistributed in [0,1), in the sense that for any subinterval $[a,b) \subset [0,1)$, \lim_{N \to \infty} \frac{1}{N} # { n \leq N : a \leq {\alpha_n} < b } = b - a, where $\#$ denotes the cardinality of the set. This reduction modulo 1 effectively folds the real line into a periodic structure, capturing the asymptotic density of points in the unit interval.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) This setting is intrinsically linked to the geometry of the torus, as the interval [0,1) with endpoints identified forms the one-dimensional torus $\mathbb{T} = \mathbb{R}/\mathbb{Z}$. Equidistribution modulo 1 thus equates to uniform distribution with respect to the Lebesgue measure on this compact abelian group. Equivalently, the points can be mapped to the unit circle in the complex plane via the exponential representation $e^{2\pi i \alpha_n}$, where uniform distribution on the torus corresponds to the sequence $ (e^{2\pi i \alpha_n})_{n=1}^\infty $ being uniformly distributed on the circle $ S^1 $. This perspective highlights the periodic nature of the modulo 1 operation and facilitates the use of Fourier analysis in studying distribution properties.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf)[](https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/) The modulo 1 framework is a prerequisite for numerous theorems in uniform distribution theory, with all major characterization criteria—such as those involving exponential sums or Riemann integrals—assuming this projection unless otherwise specified. A foundational result illustrating its power is Weyl's equidistribution theorem: if $\alpha \in \mathbb{R}$ is irrational, then the sequence $\{n \alpha\}_{n=1}^\infty$ is equidistributed modulo 1. This theorem, established through early applications of exponential sums, underscores the role of irrationality in ensuring uniformity on the torus.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) ## Characterization and Criteria ### Weyl's Criterion Weyl's criterion provides a fundamental characterization of equidistributed sequences in terms of exponential sums, originally introduced by Hermann Weyl in 1916 as part of his work on Diophantine approximation.[](https://eudml.org/doc/158730) A sequence $(x_n)_{n=1}^\infty$ in $[0,1)$ is equidistributed modulo 1 if and only if, for every nonzero integer $k \in \mathbb{Z} \setminus \{0\}$, \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N e^{2\pi i k x_n} = 0. This condition leverages the fact that the exponential functions $e^{2\pi i k x}$ form the characters on the torus $\mathbb{R}/\mathbb{Z}$, which are orthogonal with respect to the Lebesgue measure.[](https://www2.math.upenn.edu/~gressman/analysis/09-equidistribution.html) The proof proceeds in two directions. The necessity follows directly from the definition of equidistribution, as the average of the character over the empirical measure converges to its integral against the uniform measure, which vanishes for nontrivial characters. For sufficiency, continuous functions on the torus are uniformly approximated by trigonometric polynomials (linear combinations of these characters) via the Stone-Weierstrass theorem or Fejér's kernel, ensuring the averages converge to the integrals for all continuous test functions, and hence for indicators of intervals by density arguments.[](https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/) This criterion generalizes naturally to higher dimensions: a sequence $( \mathbf{x}_n )_{n=1}^\infty$ in $[0,1)^d$ is equidistributed modulo 1 if and only if, for every nonzero lattice point $\mathbf{k} \in \mathbb{Z}^d \setminus \{\mathbf{0}\}$, \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N e^{2\pi i \mathbf{k} \cdot \mathbf{x}_n} = 0, where the sums are Weyl sums over the integer lattice. For polynomial sequences, Weyl extended the criterion to show that if $P(t) = \alpha_s t^s + \cdots + \alpha_1 t + \alpha_0$ is a polynomial with real coefficients and at least one $\alpha_j$ (for $1 \leq j \leq s$) irrational, then the sequence $\{P(n)\}_{n=1}^\infty$ (fractional parts) is equidistributed modulo 1, proven by estimating the exponential sums via differencing and induction on the degree.[](https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/)[](https://eudml.org/doc/158730) ### Riemann Integral Criterion A sequence $\{x_n\}$ in the unit interval $[0,1)$ is equidistributed modulo 1 if and only if, for every continuous function $f: [0,1) \to \mathbb{C}$, \lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N f(x_n) = \int_0^1 f(x) , dx, where the integral is understood in the Riemann sense.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) This formulation captures the asymptotic behavior of the sequence through the convergence of empirical averages to the space average over the uniform measure on $[0,1)$.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) This integral criterion is equivalent to the standard definition of equidistribution in terms of subintervals of $[0,1)$, which requires the proportion of sequence terms falling into any interval $[a,b) \subset [0,1)$ to approach $b-a$ as $N \to \infty$. The equivalence follows from the density of trigonometric polynomials in the space of continuous functions on the circle, guaranteed by the Stone–Weierstrass theorem, allowing approximation of indicator functions of intervals by continuous functions and subsequently by polynomials whose averages can be controlled.[](https://terrytao.wordpress.com/2010/03/28/254b-notes-1-equidistribution-of-polynomial-sequences-in-torii/)[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) The criterion offers advantages over interval-based definitions by directly accommodating arbitrary continuous test functions, facilitating applications in numerical integration where the sequence serves as quadrature points.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) It also establishes a natural link to ergodic theory, where the convergence of time averages along orbits under measure-preserving transformations aligns with the individual ergodic theorem for Lebesgue-integrable functions on $[0,1)$.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) ### Discrepancy Measures Discrepancy measures provide a quantitative assessment of the uniformity of a sequence in the unit interval [0,1], capturing the deviation between the empirical distribution of the first $N$ points and the uniform Lebesgue measure.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) The classical (or extreme) discrepancy $D_N$ of a sequence $\{x_n\}$ is defined as D_N = \sup_{0 \leq a < b \leq 1} \left| \frac{1}{N} \sum_{n=1}^N \mathbf{1}{[a,b)}(x_n) - (b - a) \right|, $ where \mathbf{1}{[a,b)}

is the indicator function of the interval

[a,b)$.^[6] This supremum norm measures the maximum deviation over all subintervals, serving as a worst-case indicator of nonuniformity.^[6] A related measure is the star discrepancy

D_N^*

, which restricts the intervals to those anchored at 0: D_N^* = \sup_{0 \leq x \leq 1} \left| \frac{1}{N} \sum_{n=1}^N \mathbf{1}_{[0,x)}(x_n) - x \right|. $$ The star discrepancy is computationally simpler and bounds the classical discrepancy via $D_N^* \leq D_N \leq 2 D_N^*$.[](https://web.maths.unsw.edu.au/~josefdick/preprints/KuipersNied_book.pdf) For broader analysis, $L^p$ variants generalize these using the $L^p$ norm on the local discrepancy function, typically for the star case: D_N^{(p)} = \left( \int_0^1 \left| \frac{1}{N} \sum_{n=1}^N \mathbf{1}_{[0,x)}(x_n) - x \right|^p , dx \right)^{1/p}, \quad 1 \leq p < \infty. $ These L^p

discrepancies emphasize average deviations rather than extremes, with

p=2$ often linked to quadratic mean errors.^[6] In higher dimensions, these measures extend analogously to axis-aligned boxes.^[6] A sequence is equidistributed modulo 1 if and only if

D_N \to 0

(or equivalently

D_N^* \to 0

) as

N \to \infty

, providing a metric characterization beyond qualitative definitions.^[6] However, discrepancy cannot vanish arbitrarily fast; Roth's theorem establishes a lower bound in two dimensions, showing that for any set of

N

points in the unit square,

D_N \geq c (\log N)^{1/2} / N

for some constant

c > 0

.^[6] This logarithmic factor highlights inherent limitations on uniformity, with generalizations to

s

dimensions yielding bounds of order

N^{-1} (\log N)^{s-1}

.^[6] Discrepancy measures underpin error estimates in numerical integration, as captured by the Koksma-Hlawka inequality. For a function

f: [0,1] \to \mathbb{R}

of bounded variation

V(f)

, the integration error satisfies

\left| \int_0^1 f(x) \, dx - \frac{1}{N} \sum_{n=1}^N f(x_n) \right| \leq V(f) \, D_N^*.

∫01f(x)dx−N1n=1∑Nf(xn)

≤V(f)DN∗. This bound links low discrepancy to efficient quasi-Monte Carlo methods, where sequences with small $D_N^*$ minimize approximation errors relative to the function's smoothness.^[6] In higher dimensions, the inequality extends using the star discrepancy and appropriate variation norms.^[6]

Examples and Constructions

Classical Examples

One of the most fundamental examples of an equidistributed sequence is the sequence of fractional parts

\{n \alpha\}

for

n = 1, 2, 3, \dots

, where

\alpha

is an irrational number. This sequence, known as an irrational rotation on the unit circle, fills the interval

[0, 1)

uniformly as

n

increases. The equidistribution was established by Hermann Weyl in 1916 using his eponymous criterion, which requires that for every integer

k \neq 0

\lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N e^{2\pi i k n \alpha} = 0.

This sum is a geometric series whose magnitude is bounded by

\left| \frac{\sin(\pi k N \alpha)}{N \sin(\pi k \alpha)} \right| \leq \frac{1}{N |\sin(\pi k \alpha)|}.

Nsin(πkα)sin(πkNα)

≤N∣sin(πkα)∣1. Since $\alpha$ is irrational, $k \alpha$ is also irrational for $k \neq 0$ , ensuring $\sin(\pi k \alpha) \neq 0$ , and thus the expression tends to 0 as $N \to \infty$ .^[7] A specific instance is the sequence $\{n \log 2\}$ , where $\log 2$ denotes the natural logarithm of 2, which is irrational. This sequence is equidistributed modulo 1 and plays a role in applications like Benford's law for the distribution of leading digits in many natural datasets.^[2] Another classical example, predating Weyl's work, is the sequence of fractional parts $\{\alpha^n\}$ for $\alpha > 1$ irrational (or more generally for almost all $\alpha > 1$ ). This was proven equidistributed by G. H. Hardy and J. E. Littlewood in 1914 using properties of exponential sums.^[2] In contrast, if $\alpha = p/q$ is rational in lowest terms with $q > 1$ , the sequence $\{n \alpha\}$ is not equidistributed. It is periodic with period $q$ , taking only the $q$ distinct values $\{j p / q\}$ for $j = 0, 1, \dots, q-1$ , and thus clusters at these rational points rather than distributing uniformly across $[0, 1)$ .^[6] Not all dense sequences in [0,1) are equidistributed. For example, the sequence of fractional parts $\{\ln n\}$ for n = 1, 2, ... is dense in [0,1) due to the irrationality of multiples of ln, but it is not equidistributed because the points cluster near 0, failing Weyl's criterion.^[2] Another classical construction is the van der Corput sequence in base 2, where the $n$ -th term $x_n$ is formed by writing $n$ in binary, reversing its digits after the binary point, and interpreting the result as a binary fraction (e.g., $x_1 = 0.1_2 = 1/2$ , $x_2 = 0.01_2 = 1/4$ , $x_3 = 0.11_2 = 3/4$ ). This sequence is equidistributed modulo 1 due to the independence of the binary digits in its radical-inverse representation, which ensures that the partial sums in Weyl's criterion vanish for $k \neq 0$ . The construction generalizes to any base $b \geq 2$ , yielding equidistributed sequences with low discrepancy.^[6]

Algorithmic Constructions

Algorithmic constructions of equidistributed sequences focus on computational methods that generate points with low discrepancy, ensuring efficient coverage of the unit interval or cube for practical applications. These methods produce deterministic sequences that mimic uniform distribution more effectively than purely random ones, particularly in numerical integration where variance reduction is key. Low-discrepancy sequences, such as Halton and Sobol, are prominent examples, constructed using base representations to achieve equidistribution modulo 1.^[8] The Halton sequence is generated using the radical-inverse function in different prime bases for each dimension, ensuring low correlation between coordinates. For a one-dimensional case in base

b

(a prime number), the

n

-th term is defined as the radical-inverse

\phi_b(n) = \sum_{k=0}^\infty \frac{a_k}{b^{k+1}}

, where

n = \sum_{k=0}^\infty a_k b^k

with digits

a_k \in \{0, 1, \dots, b-1\}

. This construction yields an equidistributed sequence in

[0,1)

with discrepancy decreasing as

O((\log n)/n)

, outperforming random sequences in filling the space uniformly. In higher dimensions, distinct primes are chosen for each coordinate to maintain independence.^[8] Sobol sequences extend this idea using a binary representation and primitive polynomials to generate direction numbers, producing points via a linear combination modulo 2. The construction involves computing successive points as

x_{n+1} = x_n \oplus m_{j+1}

, where

\oplus

denotes bitwise XOR and

m_j

are direction numbers derived from primitive polynomials of degree

j

. This results in a low-discrepancy sequence with favorable properties in projections, achieving equidistribution and discrepancy bounds of

O((\log n)^s / n)

s

dimensions. Sobol sequences are particularly effective due to their recursive generation, allowing efficient computation without storing all prior points.^[9] Pseudorandom methods, such as linear congruential generators (LCGs), can also produce equidistributed sequences modulo 1 when parameters ensure a full period. An LCG is defined by

X_{n+1} = (a X_n + c) \mod m

, with the fractional parts

u_n = X_n / m

forming the sequence. For full period

m

(where

m

is a large prime power), the sequence

\{u_n\}

is equidistributed in

[0,1)

\gcd(c, m) = 1

a \equiv 1 \pmod{p}

for each prime

p

dividing

m

, and

a \equiv 1 \pmod{4}

if 4 divides

m

. These conditions, detailed in seminal analyses, guarantee uniform coverage over the period. In modern computational practice, these sequences are implemented in libraries for numerical integration, where low-discrepancy points reduce error compared to Monte Carlo methods. Python's SciPy library provides the scipy.stats.qmc module, supporting Halton and Sobol generators via classes like Halton and Sobol, which allow scrambling for improved properties and efficient sampling up to high dimensions. Similarly, MATLAB offers haltonset and sobolset functions to create quasirandom point sets, with built-in support for scrambling and net generation for integration tasks. These tools facilitate practical use in simulations, ensuring reproducible equidistributed samples.^[10]^[11]^[12]

Advanced Properties

Well-Distributed Sequences

A sequence

(x_n)_{n=1}^\infty

in the unit interval

[0,1)

is well-distributed modulo 1 if, for every subinterval

[a,b) \subseteq [0,1)

\lim_{N \to \infty} \sup_{h \geq 0} \left| \frac{A([a,b); N, h)}{N} - (b - a) \right| = 0,

N→∞limh≥0sup

NA([a,b);N,h)−(b−a)

=0, where $A([a,b); N, h)$ denotes the number of points $x_{h+1}, \dots, x_{h+N}$ that lie in $[a,b)$ .^[6] This uniformity over all starting indices $h$ ensures that the asymptotic distribution is independent of the initial segment, providing stronger control than mere equidistribution.^[6] Well-distributed sequences are equidistributed modulo 1, as the uniform bound implies the relative frequency converges to $b - a$ as $N \to \infty$ for every subinterval $[a,b)$ .^[6] However, the converse fails: there exist equidistributed sequences that are not well-distributed, such as those formed by concatenating permutations of the uniform grid $\{k/M : k = 0, \dots, M-1\}$ on $[0,1)$ for successively larger $M$ , where the ordering causes some consecutive block to deviate significantly from uniformity.^[13] The well-distributed property provides explicit control over consecutive blocks for every finite $N$ , distinguishing it from asymptotic equidistribution and making it valuable for uniform sampling applications where avoiding local clusters or imbalances at intermediate stages is essential.^[6] A representative example is the Kronecker sequence in higher dimensions, given by $x_n = ( \{n \alpha_1\}, \dots, \{n \alpha_s\} )$ for $n = 1, 2, \dots$ , where the $\alpha_i$ are real numbers such that $1, \alpha_1, \dots, \alpha_s$ are linearly independent over the rationals and the continued fraction expansions of the $\alpha_i$ satisfy suitable boundedness conditions to ensure the uniformity over shifts holds.^[6]

Complete Uniform Distribution

A sequence

(x_n)_{n=1}^\infty

of real numbers is completely uniformly distributed modulo 1 if every infinite subsequence

(x_{n_k})_{k=1}^\infty

is equidistributed modulo 1.^[6] This condition ensures that the asymptotic distribution remains uniform regardless of the selection of terms, provided the subsequence is infinite.^[6] However, no such infinite sequence exists modulo 1 with respect to Lebesgue measure, as any equidistributed sequence has infinitely many terms in every subinterval of positive length, allowing extraction of an infinite subsequence confined to a proper subinterval of length less than 1, which cannot be equidistributed over [0,1). This leads to a contradiction.^[6] This property is equivalent to every infinite subsequence achieving uniform density in every subinterval of

[0,1)

, meaning the proportion of terms falling into any

[a,b) \subset [0,1)

approaches

b-a

as the subsequence length tends to infinity.^[6] However, no infinite sequence can exhibit this property modulo 1 with respect to Lebesgue measure, as it contradicts the requirement of equidistribution implying positive density in every subinterval.^[6] Characterizations often involve the uniform vanishing of exponential sums over all infinite subsequences, i.e., for every nonzero integer

m

\lim_{K \to \infty} \frac{1}{K} \sum_{k=1}^K \exp(2\pi i m x_{n_k}) = 0

for every infinite

(n_k)

.^[6] The concept of complete uniform distribution was introduced by A. G. Postnikov.^[6] Characterizations of such sequences often involve connections to continued fraction expansions, where bounded partial quotients in the expansion of irrational rotation numbers contribute to strong uniformity properties across subsequences.^[6] There is also a relation to almost periodic sequences, for which the uniform distribution holds uniformly with respect to shifts, ensuring subsequence stability in topological groups.^[6] These characterizations and relations are typically considered in more general settings or with respect to arbitrary measures. In abstract settings or for certain measures, complete uniform distribution is a distinct strengthening of equidistribution that focuses on invariance under subsequence extraction, while well-distribution emphasizes uniformity over consecutive shifts; these properties are incomparable and, for non-degenerate measures like Lebesgue on [0,1), no sequence can satisfy complete uniform distribution (hence neither both nor the former alone).^[6]

Van der Corput's Difference Theorem

Van der Corput's difference theorem provides a sufficient condition for the equidistribution of a sequence modulo 1 based on the equidistribution properties of its pairwise differences. Specifically, let {x_n}{n=1}^\infty be a sequence in \mathbb{R}/\mathbb{Z}. If, for every fixed positive integer h, the sequence {x{n+h} - x_n}{n=1}^\infty is equidistributed in \mathbb{R}/\mathbb{Z}, then {x_n} is equidistributed in \mathbb{R}/\mathbb{Z}. A more general formulation states that {x_n} is equidistributed if the differences {x{n+m} - x_n} are equidistributed for each m = 1, \dots, h(N) where h(N) \to \infty as N \to \infty. This theorem, originally established by J. G. van der Corput, complements Weyl's criterion by leveraging structural properties of differences rather than direct Fourier analysis.^[14]^[15] The theorem can be expressed in terms of averaging over differences to capture the equidistribution condition. For any subinterval [a, b) \subseteq [0, 1), the equidistribution of {x_n} follows if

\lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \frac{1}{h(N)} \sum_{m=1}^{h(N)} \mathbf{1}_{[a,b)}(\{x_{n+m} - x_n\}) = b - a,

where h(N) \to \infty as N \to \infty and \mathbf{1}_{[a,b)} is the indicator function of [a, b). This averaging ensures that the empirical distribution of the differences approximates the uniform measure sufficiently well over growing ranges of m, implying the desired uniformity for the original sequence. The condition holds in particular when the differences are individually equidistributed for all fixed m.^[15]^[16] Applications of the theorem are prominent in the study of polynomial and lacunary sequences. For polynomial sequences x_n = P(n) where P is a polynomial of degree d \geq 1 with at least one coefficient other than the constant term being irrational, the first differences P(n+h) - P(n) form a polynomial of degree d-1, allowing induction on the degree to establish equidistribution via the theorem; this recovers Weyl's classical result on polynomial equidistribution. Similarly, for lacunary sequences such as x_n = n \alpha + \beta \sqrt{n} with \alpha irrational, the differences exhibit equidistribution properties that satisfy the theorem's hypothesis, yielding equidistribution of the sequence itself. These applications highlight the theorem's utility in reducing complexity through differencing.^[15]^[17] The proof of the theorem employs ergodic methods, particularly by considering the shift on the orbit closure of the sequence in the torus and applying the ergodic theorem to averages involving differences. By embedding the problem in an ergodic dynamical system and using the uniform distribution of differences to control return times or correlations, the theorem demonstrates that the original sequence's averages converge to integrals over the uniform measure. This approach, refined in modern treatments, connects the theorem to mixing properties in ergodic theory.^[15]^[16] Generalizations extend the theorem to higher-order differences, which are particularly effective for smoother sequences like higher-degree polynomials. For a sequence {x_n}, if the k-th order differences \Delta^k x_n = \sum_{j=0}^k (-1)^{k-j} \binom{k}{j} x_{n+j} are equidistributed modulo 1 for appropriate ranges, then {x_n} is equidistributed; this iterates the first-order case k times to handle degree-k polynomials with irrational leading coefficients. Such extensions maintain the averaging structure over differences but incorporate combinatorial identities for the higher orders, broadening applicability to more structured sequences.^[15]^[17]

Generalizations and Applications

Metric Theorems

Metric theorems establish that equidistributed sequences prevail for almost all parameters under Lebesgue measure, providing a probabilistic foundation for their ubiquity in parameter spaces such as the unit interval or continued fraction expansions. These results contrast deterministic criteria by focusing on measure-theoretic prevalence, ensuring that exceptions form sets of measure zero. Weyl's metric theorem asserts that the sequence

\{n \alpha\}

is equidistributed modulo 1 for almost all

\alpha \in [0,1]

with respect to Lebesgue measure. This holds because the exceptional set consists solely of rational

\alpha

, which has Lebesgue measure zero. The measure-theoretic formulation is

\mu(\{\alpha : \{n\alpha\} \text{ is not equidistributed}\}) = 0

, where

\mu

denotes Lebesgue measure.^[6] Khintchine's theorem extends this framework, showing that for any monotonic function

f: [0,1] \to \mathbb{R}

, the ergodic averages

\frac{1}{N} \sum_{n=1}^N f(\{n \alpha\})

converge to

\int_0^1 f(x) \, dx

for almost all

\alpha \in [0,1]

in the Lebesgue sense. This monotonicity condition facilitates the application of metric tools to broader classes of functions beyond continuous ones.^[6] Modern extensions in Diophantine approximation refine these ideas; for instance, the set of badly approximable numbers—irrationals

\alpha

for which there exists

c > 0

such that

|\alpha - p/q| > c/q^2

for all rationals

p/q

—has Lebesgue measure zero, despite exhibiting full Hausdorff dimension. This underscores the typical well-approximability of almost all

\alpha

, aligning with equidistribution's generic behavior under random parameters.^[18]

Equidistribution with Respect to Arbitrary Measures

A sequence

\{x_n\}

in the unit interval

[0,1)

is said to be equidistributed with respect to an arbitrary probability measure

\mu

[0,1)

if, for every continuous function

f: [0,1) \to \mathbb{R}

, the average of the values

f(x_n)

converges to the integral of

f

with respect to

\mu

\frac{1}{N} \sum_{n=1}^N f(x_n) \to \int_{[0,1)} f \, d\mu

N \to \infty

.^[19] This generalizes the classical notion of equidistribution, which corresponds to the case where

\mu

is the Lebesgue measure on

[0,1)

, and it captures weak convergence of the empirical measures

\frac{1}{N} \sum_{n=1}^N \delta_{x_n}

\mu

.^[19] An analogue of Weyl's criterion characterizes equidistribution with respect to

\mu

in terms of the Fourier-Stieltjes coefficients of

\mu

. Specifically, the sequence

\{x_n\}

is equidistributed with respect to

\mu

if and only if, for every integer

k \neq 0

\frac{1}{N} \sum_{n=1}^N e^{2\pi i k x_n} \to \hat{\mu}(k) := \int_{[0,1)} e^{2\pi i k x} \, d\mu(x)

N \to \infty

, with the case

k=0

holding trivially since both sides equal 1.^[20] For

k=0

, the convergence is immediate, and the non-trivial condition ensures the orthogonality of the characters with respect to the limiting measure. This criterion extends the standard Weyl criterion by replacing the vanishing condition for Lebesgue measure (where

\hat{\mu}(k) = 0

for

k \neq 0

) with convergence to the specific Fourier coefficients of

\mu

.^[20] For atomic measures, the notion simplifies: if

\mu = \sum_{j=1}^m p_j \delta_{y_j}

with

\sum p_j = 1

and distinct points

y_j \in [0,1)

, then equidistribution requires that the proportion of terms

x_n

equal to each

y_j

approaches

p_j

.^[19] Examples of non-uniform continuous measures include beta distributions, where

\mu

has density proportional to

x^{\alpha-1}(1-x)^{\beta-1}

for

\alpha, \beta > 0

; sequences equidistributed with respect to such measures arise in contexts requiring weighted sampling on

[0,1)

, such as certain probabilistic models or numerical integration schemes adapted to non-uniform densities.^[19] This generalization connects naturally to ergodic theory through Birkhoff's ergodic theorem, which implies that for a measure-preserving transformation

T

on a probability space

(X, \mu)

and almost every starting point

x \in X

, the orbit sequence

\{T^n x\}_{n=1}^\infty

satisfies the equidistribution property with respect to

\mu

for integrable functions, and hence for continuous functions when

X

is compact like the circle. In the ergodic case, the invariant measure

\mu

is unique, ensuring that generic orbits equidistribute with respect to it.

Higher Dimensions and Modern Applications

Equidistribution extends naturally to the unit hypercube

[0,1)^d

for

d \geq 2

, where a sequence

\{ \mathbf{x}_n \}_{n=1}^\infty

with

\mathbf{x}_n = (x_n^{(1)}, \dots, x_n^{(d)}) \in [0,1)^d

is equidistributed if the proportion of the first

N

points falling into any sub-rectangle approaches the volume of that sub-rectangle as

N \to \infty

. The multidimensional Weyl criterion characterizes this property: the sequence is equidistributed if and only if, for every nonzero integer vector

\mathbf{h} = (h_1, \dots, h_d) \in \mathbb{Z}^d \setminus \{\mathbf{0}\}

\lim_{N \to \infty} \frac{1}{N} \sum_{n=1}^N \exp\left(2\pi i \sum_{j=1}^d h_j x_n^{(j)}\right) = 0.

This criterion generalizes the one-dimensional case by replacing scalar frequencies with dot products over multi-indices.^[21] A fundamental construction in higher dimensions is provided by Kronecker's theorem on simultaneous Diophantine approximation, which states that if

1, \alpha_1, \dots, \alpha_d

are linearly independent over the rationals, then the sequence

\{ n \boldsymbol{\alpha} \}_{n=1}^\infty \mod 1

, where

\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_d)

, is equidistributed in

[0,1)^d

. This result ensures dense and uniform coverage for irrational rotation vectors, forming the basis for many explicit examples of equidistributed sequences in multiple dimensions.^[22] Quantifying equidistribution in higher dimensions often involves discrepancy measures, which bound the deviation from uniformity. The star discrepancy

D_N^{(d)}

N

points in

[0,1)^d

satisfies a lower bound established by Roth: for any

d \geq 2

D_N^{(d)} \geq c_d \frac{(\log N)^{(d-1)/2}}{N},

where

c_d > 0

is a dimension-dependent constant; this bound highlights the increasing challenge of achieving low discrepancy as

d

grows, with improvements by Schmidt for

d=2

and further refinements in higher dimensions.^[23] In modern applications, equidistributed sequences in higher dimensions underpin quasi-Monte Carlo (QMC) methods for numerical integration, where low-discrepancy point sets approximate integrals over

[0,1)^d

with error bounded by the Koksma-Hlawka inequality:

|\int f - \frac{1}{N} \sum f(\mathbf{x}_i)| \leq V(f) D_N^{(d)}

, and for sequences with

D_N^{(d)} = O((\log N)^d / N)

, the integration error is

O((\log N)^d / N)

for functions

f

of bounded variation

V(f)

. This outperforms standard Monte Carlo's

O(1/\sqrt{N})

O(1/N

) rate, especially in finance and physics simulations involving high-dimensional integrals.^[24] Cryptographic applications leverage multidimensional equidistribution for pseudorandom number generators (PRNGs), ensuring sequences pass statistical tests for uniformity across projections up to high dimensions. The Mersenne Twister algorithm, for instance, generates sequences that are 623-dimensionally equidistributed to within machine precision, making it suitable for simulations requiring long periods and high-dimensional uniformity while resisting predictability in non-cryptographic contexts.^[25] In machine learning, equidistributed low-discrepancy sequences facilitate uniform sampling in hypercubes for tasks like data augmentation and optimization. Post-2020 developments include using such sequences to generate sparse neural network architectures, where weights are selected via low-discrepancy points to achieve accuracies comparable to dense networks while significantly reducing computational complexity; additionally, neural low-discrepancy sequences (NeuroLDS), optimized via deep learning, minimize discrepancy in high dimensions for improved quasi-Monte Carlo integration in robot motion planning and generative modeling.^[26]^[27] Computational tools address the challenges of generating low-discrepancy sequences in higher dimensions, particularly lattice rules, which use rank-1 lattices for efficient QMC quadrature. The Lattice Builder library implements algorithms to construct optimal rank-1 lattices by minimizing weighted star discrepancy, supporting dimensions up to thousands for practical high-dimensional problems. Similarly, the QMCPy Python package provides randomized low-discrepancy sequences, including Sobol and lattice variants, with tools for fast kernel density estimation and integration error assessment.^[28] Recent advances in the 2020s have improved discrepancy bounds through AI optimization, with graph neural networks generating point sets that significantly outperform traditional constructions like Sobol sequences in discrepancy metrics, achieving up to 5 times lower star-discrepancy in 2D and better performance in dimensions up to 32, enabling better uniformity for applications in uncertainty quantification and AI-driven design. These methods iteratively refine point distributions using machine learning surrogates, closing gaps in classical bounds for moderate $N$ .^[29]^[27]

Info Pages

Talk Pages

Special Pages

Equidistributed sequence

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Equidistributed sequence