Weyl’s Equidistribution Theorem (Updated)

I introduced equidistributed sequences in an earlier post on the sequence formed by evaluating the sine function at primes in ascending order, and one theorem I mentioned the following theorem: 

Theorem 1. The following are equivalent:
1. (x_{n})_{n=1}^{\infty} is equidistributed distributed modulo 1;

2. For any integer m\neq0,

\displaystyle\lim_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}e^{2\pi i mx_{j}}=0;

3. For any Riemann integrable function f:\mathbb{T}\rightarrow\mathbb{C},


I omitted the proof in the aforementioned post, an omission I will now correct. The plan is to work through the proof and then use the theorem, along with some estimates for exponential sums, to present some examples of an equidistributed sequence. I first want to begin with some comments on the statement of Theorem 1.

The reader familiar with be Lebesgue integration may be wondering why ‘Riemann integrable’ appears in statement (3) instead of ‘Lebesgue integrable.’ Well, the theorem is false for a simple reason: we can modify a Lebesgue integrable function f on a countable set (more generally, a null set) without changing the value \int_{0}^{1}f. So if (x_{n})_{n=1}^{\infty} is equidistributed and f\equiv 1, then we can define a new function \tilde{f}:\mathbb{T}\rightarrow\mathbb{C} by


such that

\displaystyle\lim_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}\tilde{f}(x_{j})=0\text{ and }\int_{0}^{1}\tilde{f}=1

Proof. To establish equivalence, we will show that (1)\Longleftrightarrow(3) and (2)\Longleftrightarrow(1). Suppose that (1) holds and that f: \mathbb{T}\rightarrow\mathbb{C} is Riemann integrable. By considering real and imaginay parts separately, we may assume that f is real-valued. First, suppose that f\equiv c is a constant function. Then

\displaystyle\dfrac{1}{n}\sum_{k=1}^{n}f(x_{k})=c=\int_{0}^{1}cdt=\int_{0}^{1}f(t)dt,\indent\forall n\in\mathbb{N}

Now suppose that f=\mathbf{1}_{[a,b]}, where [a,b]\subset[0,1]. Then since (x_{n})_{n=1}^{\infty} is equidistributed by hypothesis,

\displaystyle\lim_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}f(x_{j})=\#\left\{x_{j}\mod{1}\in[a,b]: 1\leq j\leq n\right\}=b-a=\int_{0}^{1}f(t)dt

By the linearity of the integral, we see that (3) holds for all step functions f. By definition of Riemann integrability, for any \varepsilon>0, there exist step functions f_{1} and f_{2} such that f_{1}\leq f\leq f_{2} and



\begin{array}{lcl}\displaystyle\limsup_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}f(x_{j})-\int_{0}^{1}f(t)dt&\leq&\displaystyle\limsup_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}f_{2}(x_{j})-\int_{0}^{1}f(t)dt\\[.9 em]&=&\displaystyle\int_{0}^{1}[f_{2}(t)-f(t)]dt\\[.9 em]&\leq&\displaystyle\dfrac{\varepsilon}{2}\end{array}


\begin{array}{lcl}\displaystyle\liminf_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}f(x_{j})-\int_{0}^{1}f(t)dt&\geq&\displaystyle\liminf_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}f_{1}(x_{j})-\int_{0}^{1}f(t)dt\\[.9 em]&=&\displaystyle\int_{0}^{1}[f_{1}(t)-f(t)]dt\\[.9 em]&\geq&\displaystyle-\dfrac{\varepsilon}{2}\end{array}

We conclude that


(3)\Longrightarrow(1) is trivial, since we just take f=\mathbf{1}_{[a,b]}, for any subinterval [a,b]\subset[0,1].

Now suppose that (2) holds. As argued above, we may assume that f=\sum_{j=1}^{n}c_{j}\mathbf{1}_{[a_{j-1},a_{j})}, where 0=a_{0}<a_{1}<\cdots<a_{n}=1. By linearly interpolating between neighborhoods of the subinterval endpoints, we can find continuous functions f_{1} and f_{2} such that f_{1}\leq f\leq f_{2} and


Since we can repeat the argument used in (1)\Longrightarrow(2), we only need to show (3) holds for the step functions f_{1},f_{2}. Continuous functions can be uniformly approximated by trigonometric polynomials (see Fejer’s theorem or Stone-Weierstrass), so there exist trigonometric polynomials

\displaystyle g_{1}(x)=\sum_{j=0}^{m}\alpha_{j}e^{2\pi i jx},\indent g_{2}(x)=\sum_{j=0}^{m}\beta_{j}e^{2\pi i jx}

such that \left\|f_{i}-g_{i}\right\|_{\infty}<\frac{\varepsilon}{2}, for i=1,2. Hence, it suffices to show that


Since the argument is independent of i, we take i=1. Then using the hypothesis of (2) and the fact that \int_{0}^{1}e^{2\pi i j t}dt=0, for all integers j\neq0,

$latex \begin{array}{lcl}\displaystyle\lim_{n\rightarrow\infty}\dfrac{1}{n}\sum_{j=1}^{n}g_{1}(x_{j})-\int_{0}^{1}g_{1}(t)dt&=&\displaystyle\lim_{n\rightarrow\infty}\left(\dfrac{1}{n}\sum_{j=1}^{n}-\int_{0}^{1}\right)\left[\alpha_{0}+\cdots+\alpha_{m}e^{2\pi i m x_{j}}\right]\\[.9 em]&=&\displaystyle\alpha_{0}-\alpha_{0}\\[.9 em]&=&\displaystyle0\end{array}$

(3)\Longrightarrow(2) is immediate since trigonometric polynomials are Riemann integrable. \Box

A quick consequence of this theorem first proven by Hermann Weyl is that, for any irrational number \gamma, the sequence x_{n}:=n\gamma is equidistributed modulo 1. Indeed, applying the geometric summation formula, we obtain

\displaystyle\dfrac{1}{N}\sum_{n=1}^{N}f(n\gamma)=\dfrac{1}{N}\sum_{n=1}^{N}(e^{2\pi i j\gamma})^{n}=\dfrac{e^{2\pi i j\gamma}}{N}\cdot\dfrac{1-(e^{2\pi i j\gamma})^{N+1}}{1-e^{2\pi i j\gamma}},

for any integer nonzero integer j. Since the last expression is bounded in modulus by \frac{1}{N}\cdot\frac{2}{\left|1-e^{2\pi i j\gamma}\right|}, we see that

\displaystyle\dfrac{1}{N}\sum_{n=1}^{N}f(n\gamma)\longrightarrow 0, N\longrightarrow\infty

and equidistribution follows from condition (2) above.

Moreover, the sequence (n^{2}\gamma)_{n=1}^{\infty} is equidistributed modulo 1, for any irrational number \gamma. To prove this result, we will need a few estimates for exponential sums. To simplify the writing below, we introduce the notation

\displaystyle\left\|x\right\|_{\min}:=\min\left\{\left\{x\right\},1-\left\{x\right\}\right\},\indent\forall x\in\mathbb{R}

Note that \left\|\cdot\right\|_{\min} is not a norm; it is not positively homogeneous.

For positive integers a<b,

\displaystyle\left|\sum_{n=a}^{b}e^{2\pi i n\gamma}\right|\lesssim\min\left\{b-a,\dfrac{1}{\left\|\gamma\right\|_{\min}}\right\}

Proof. By the triangle inequality,

\displaystyle\left|\sum_{n=a}^{b}e^{2\pi i n\gamma}\right|\leq\sum_{n=a}^{b}\left|e^{2\pi i n\gamma}\right|=b-a+1\leq2(b-a)

and applying the geometric summation formula,

$latex \begin{array}{lcl}\displaystyle\left|\sum_{n=a}^{b}e^{2\pi i n\gamma}\right|=\left|\dfrac{e^{2\pi i a\gamma}\left[1-e^{2\pi i(b-a+1)\gamma}\right]}{1-e^{2\pi i\gamma}}\right|&\leq&\displaystyle\dfrac{2}{\left|1-e^{2\pi i \gamma}\right|}\\[.9 em]&\leq&\displaystyle\dfrac{2}{\left|\sin 2\pi\gamma\right|}\end{array}$

The function t\mapsto t-\sin(2t) is nonpositive on [0,\frac{\pi}{4}]. To see this, observe that the derivative is nonpositive on this interval on a subinterval [0,t] and \frac{\pi}{4}-\sin(\frac{\pi}{2})<0. The symmetry of \sin about t=\frac{\pi}{2} yields the second bound. \Box

Lemma 3. If \gamma is an irrational number, and a,q are coprime integers, with q\geq 2, such that \left|\gamma-\frac{a}{q}\right|\leq\frac{1}{q^{2}}, then

\displaystyle\left|\sum_{n=1}^{N}e^{2\pi i n^{2}\gamma}\right|\lesssim \dfrac{N}{\sqrt{q}}+\sqrt{(q+N)\log q}

for any integer N\geq1.

Proof. Let S=\sum_{n=0}^{N}e^{2\pi i n^{2}\gamma}. Then

\displaystyle\left|S\right|^{2}=S\cdot\overline{S}=\sum_{n_{1}=0}^{N}\sum_{n_{2}=0}^{N}e^{2\pi i(n_{1}^{2}-n_{2}^{2})\gamma}=\sum_{n_{1}=0}^{N}\sum_{n_{2}=0}^{N}e^{2\pi i(n_{1}-n_{2})(n_{1}+n_{2})\gamma}

Set h:=n_{1}-n_{2}, so that h ranges from -N to N. For a given h\leq0, n_{2}=n_{1}-h ranges from -h to N; for given h>0, n_{2} ranges from 0 to N-h. We can rewrite the expression for \left|S\right|^{2} as

\displaystyle\left|S\right|^{2}=\sum_{h=-N}^{N}\sum_{n_{2}=\max\left\{0,-h\right\}}^{\min\left\{N,N-h\right\}}e^{2\pi i h(h+2n_{2})\gamma}=\sum_{h=-N}^{N}e^{2\pi i h^{2}\gamma}\sum_{n_{2}=\max\left\{0,-h\right\}}^{\min\left\{N,N-h\right\}}e^{4\pi i hn_{2}\gamma}

The triangle inequality together with Lemma 2 yields the estimate


We need to now count the number of h for which the \min is N. Partition the interval [-N,N] into intervals of length at most \frac{q}{2} (e.g. intervals of the form [M,M+\frac{q}{2})). Note that there are at most \lceil{\frac{4N}{q}}\rceil such intervals. For some M\in[-N,N), set S':=\sum_{M\leq h\leq M+\frac{q}{2}}\min\left\{N,\left\|2h\gamma\right\|_{\min}^{-1}\right\}. By hypothesis, we can write \gamma=\frac{a}{q}+\theta, where \left|\theta\right|\leq\frac{1}{q^{2}}. Since we can write M as M=-N+(j-1)\frac{q}{2}, for some 1\leq j\leq\lceil{\frac{4N}{q}}\rceil, we see that 2M\leq2h<2M+q, which implies that the residue classes 2h\pmod{q} are distinct, where M\leq h<M+\frac{q}{2}, and therefore the residues 2ha\pmod{q} are distinct, since (a,q)=1. If 2ha\pmod{q} is not equivalent to -1,0,1, then


The contribution in S' from the residues 2ha\pmod{q} not equal to -1,0,1, is at most 3N, so

\displaystyle S'\leq3N+\sum_{{M\leq h<M+\frac{q}{2}}\atop{2ha\not\equiv-1,0,1\pmod{q}}}\min\left\{N,\left(\left\|\frac{2ha}{q}\right\|_{\min}-\frac{1}{q}\right)^{-1}\right\}

Since the residues classes 2ha\pmod{q} are distinct and the function \left\|\cdot\right\|_{\min} is symmetric about the midpoint, we see that \left\|\frac{2ha}{q}\right\|_{\min}, for h as above, takes a value in \left\{\frac{2}{q},\cdots,\frac{\lfloor{\frac{q}{2}}\rfloor}{q}\right\} at most twice. We get the estimate

\displaystyle S'\leq 3N+2\sum_{j=2}^{\lfloor{\frac{q}{2}}\rceil}\left(\frac{j-1}{q}\right)^{-1}=3N+2q\sum_{j=1}^{\lfloor{\frac{q}{2}}\rceil-1}\frac{1}{j}\lesssim N+q\log q,

where we use that the harmonic series grows logarithmically.

Putting our results above toegether, we obtain the estimate

\displaystyle\left|S\right|^{2}\lesssim\left\lceil{\frac{4N}{q}}\right\rceil\left(N+q\log q\right)\lesssim\left(\frac{N}{q}+1\right)\left(N+q\log q\right)\lesssim\frac{N^{2}}{q}+(N+q)\log q

Taking the square root of both sides and using the elementary inequality \sqrt{a^{2}+b^{2}}\leq \left|a\right|+\left|b\right|, we obtain the estimate

\displaystyle\left|S\right|\lesssim\sqrt{\dfrac{N^{2}}{q}+(q+N)\log q}\leq\dfrac{N}{\sqrt{q}}+\sqrt{(q+N)\log q}


The existence of such integers a,q in the statement of Lemma 3 follows from Dirichlet’s approximation theorem. So, for any irrational \gamma,

\begin{array}{lcl}\displaystyle\left|\dfrac{1}{N}\sum_{n=1}^{N}e^{2\pi i \gamma n^{2}}\right|\lesssim\dfrac{1}{N}\left(\dfrac{N}{\sqrt{q}}+\sqrt{(q+N)\log q}\right)&=&\displaystyle\dfrac{1}{\sqrt{q}}+\sqrt{\left(\frac{q}{N^{2}}+\frac{1}{N}\right)\log q}\\[.9 em]&\rightarrow&\displaystyle\frac{1}{\sqrt{q}},N\rightarrow\infty\end{array}

Since q can be taken arbitrarily large by Dirichlet’s theorem, statement (2) of Theorem 1 implies that (n^{2}\gamma)_{n=1}^{\infty} is equidistributed.

This entry was posted in math.CA, math.NT and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s