# Elementary proof of the equidistribution theorem

I'm looking for references to (as many as possible) elementary proofs of the Weyl's equidistribution theorem, i.e., the statement that the sequence $\alpha, 2\alpha, 3\alpha, \ldots \mod 1$ is uniformly distributed on the unit interval. With "elementary" I mean that it does not make use of complex analysis in particular the Weyl's criterion.

Thank you very much.

• Weyl's criterion doesn't use complex analysis, just basic properties of complex numbers, and it can be stated without complex numbers at all (for example using real trigonometric functions). – Pablo Shmerkin Sep 18 '11 at 18:52
• What is your definition of equidistributed? – Igor Rivin Sep 18 '11 at 19:00
• Pablo: Since Carlo refers to Weyl's criterion under the label "complex analysis", probably he means "complex numbers". Personally I think restating Weyl's criterion using trig functions in place of e^{ix} would make the situation look overly complicated. – KConrad Sep 18 '11 at 20:12
• Presumably, any basis of $L^2$ would work (orthogonal polynomials of some sort), but I don't really see the point, since Weyl's proof is half a page. – Igor Rivin Sep 18 '11 at 20:15
• Have you checked the Kuipers-Niederreiter book to see if there's a non-Weyl proof there? – Gerry Myerson Sep 18 '11 at 20:34

There is a really easy proof that just uses the Pigeonhole principle. Let $$\alpha$$ be irrational.

Lemma: For any $$\delta >0$$, there is an $$n>0$$ such that $$(n \alpha) \in (- \delta, \delta) \setminus \{ 0 \}$$.

Proof: Choose $$N$$ large enough that $$1/N < \epsilon$$. Divide $$[0,1]$$ up into $$N$$ segments of length $$1/N$$. By pigeonhole, there are $$j$$ and $$k$$ such that $$(j \alpha)$$ and $$(k \alpha)$$ land in the same segment. So $$((j-k) \alpha) \in (-\delta, \delta)$$. Since $$\alpha$$ is irrational, $$((j-k) \alpha) \neq 0$$. $$\square$$

Now, fix $$0 \leq p < q \leq 1$$ and $$\epsilon>0$$. Our goal is to show that $$\begin{multline*} q-p-\epsilon \leq \lim_{N \to \infty} \inf \frac{\#\{ k \leq N : (k \alpha) \in (p,q) \}}{N} \\ \leq \lim_{N \to \infty} \sup \frac{\#\{ k \leq N : (k \alpha) \in (p,q) \}}{N} \leq q-p+\epsilon. \end{multline*}$$

Choose $$\delta >0$$ such that $$\frac{(q-p)/\rho -1}{1/\rho+1} \geq q-p-\epsilon \quad \mbox{and} \quad \frac{(q-p)/\rho +1}{1/\rho-1} \leq q-p+\epsilon$$ for all $$\rho$$ with $$|\rho| < \delta$$.

Choose $$n$$ such that $$n \alpha \in (-\delta, \delta) \setminus \{ 0 \}$$. Write $$\rho = (n \alpha)$$. Break up the set of values $$(k \alpha)$$ into arithmetic progressions based on $$k$$ modulo $$n$$. So each segment is of the form $$(\beta + j \rho)$$. It is enough to prove that the lim inf and lim sup contributed by each progression lie between $$q-p-\epsilon$$ and $$q-p+\epsilon$$, as the total contribution is a weighted average from the contributions from the progressions.

Break each progression up into segments according to $$\lfloor \beta + j \rho \rfloor$$. The initial segment and final segment each contain at most $$1/ |\rho|$$ terms. The segments in the middle contain between $$1/\rho - 1$$ and $$1/\rho+1$$ terms of which between $$(q-p)/\rho -1$$ and $$(q-p)/\rho+1$$ are between $$p$$ and $$q$$. Since $$((q-p)/\rho-1)/(1/\rho+1)$$ and $$((q-p)/\rho+1)/(1/\rho-1)$$ were chosen to lie in $$(q-p-\epsilon, q-p+\epsilon)$$, the average of all of these terms lies in the required interval. And the terms from the initial segments can only drag the average off by at most $$(2/|\rho|)/(N/n)$$, which goes to $$0$$. QED.

Hardy and Wright give a proof based on continued fractions in Section 23.10 of "An introduction to the theory of numbers" (reference valid at least in the 4th edition).

Interestingly, their endnotes to Chapter 23 claim that the "equidistribution" form of the theorem is not due to Kronecker (the statement they call "Kronecker's theorem" is the density of $$\{n\alpha\}$$; they give a number of elementary proofs of that weaker result), but "independently to Bohl, Sierpinski and Weyl".

• Probably Harold Bohr, not "Bohl"... – paul garrett Jul 6 '17 at 1:10
• @paulgarrett It is actually P. Bohl: eudml.org/doc/149304 – Michael Greinecker Jul 6 '17 at 7:53
• @MichaelGreinecker, aha! Thanks for that clarification! – paul garrett Jul 6 '17 at 19:52

An elementary proof was given by Alberto Zorzi in

An Elementary Proof for the Equidistribution Theorem
The Mathematical Intelligencer September 2015, Volume 37, Issue 3, pp 1–2

Unfortunately the article is behind a paywall. The proof makes use of the following elementary criterium for equidistribution. As usual, $$\{\}$$ denotes the fractional part of a real number.

LEMMA 1. A sequence $$(x_n)$$ is equidistributed in $$[0,1)$$ if and only if $$\lim_{N\rightarrow \infty} \left( {1\over N}\sum_{n=1}^N \{x_n\} - {1\over N}\sum_{n=1}^N \{x_n+a\}\right) = 0.$$ for any real number a.

Not sure if this qualifies, but there is a short proof using Fourier Analysis. No hardcore stuff, just Fejér's Theorem. See Chapter 3 of Körner's Fourier Analysis book (there are 110 chapters in the book, so this really is one of the first things that is covered).

• This would basically be Weyl's proof, I think - the key idea there is to smooth the characteristic function of the interval [a,b] on which one wishes to count points n\alpha. The Fejer kernel (or de la Vallee Poussin kernel) is one way to do that. (I'd have to admit that I haven't bothered actually going to look at the book before making this comment.) – Ben Green Sep 19 '11 at 9:11
• I have to admit that I hadn't bothered actually going to look at Weyl's proof before posting this answer. – Tony Huynh Sep 20 '11 at 9:33

Here is an elementary proof for the equidistribution of orbits of irrational rotations. Let $$\alpha$$ be any irrational number and fix $$0\le a. We need to show that

$$$$\tag{1}\label{eq:equidistribution} \frac{\# \left\{0\le j < n\,:\,\{j\alpha\} \in[a,b]\right\}}{n}\xrightarrow[n\to\infty]{}b-a.$$$$

The idea is to choose a rational number $$p/q$$ close enough to $$\alpha$$ with a large enough denominator, then take $$n$$ large enough and use the facts that the orbits of a rotation by $$p/q$$ are evenly spaced within the unit interval, with a distance of $$1/q$$ between orbit points, and that orbits of the rotation by $$\alpha$$ stay close to orbits of the same point under rotations by $$p/q$$ along pieces of orbits of size smaller then $$q$$. In this respect the current proof is motivated by and similar to the proof by Hardy and Wright mentioned on this page.

We will need the following standard and easy-to-prove lemma:

Lemma: Assume $$\alpha\in\mathbb{R}$$ and that $$p$$ and $$q$$ are coprime integers satisfying $$$$\tag{2}\label{eq:best} \left|\alpha-p/q\right| < \frac{1}{q^2}.$$$$ Then for every $$0\le i < q$$ there exists a unique $$0 \le j < q$$ such that $$\{j\alpha\}\in \left[\frac{i}{q},\frac{i+1}{q}\right)$$.

Proof: Without loss of generality assume that $$\alpha > \frac{p}{q}$$. Then $$0 < j\alpha - j\frac{p}{q} < \frac{1}{q}$$ for every $$0\leq j. Writing $$jp = s_j q + r_j$$ with $$0\leq r_j we see that the integer part of $$j\alpha$$ is $$s_j$$ which implies $$\frac{r_j}{q} < \{j\alpha\} < \frac{r_j+1}{q}$$. Since $$p$$ and $$q$$ are coprime the map $$j\mapsto r_j$$ is a bijection on $$\{0,\ldots,q-1\}$$ so we are done.

Getting back to our sheeps, fix any $$\varepsilon>0$$. By Dirichlet's theorem there are arbitrarily large rational approximations to $$\alpha$$ that satisfy \eqref{eq:best}. Choose $$p$$ and $$q$$ coprime that satisfy \eqref{eq:best} with $$q$$ large enough ( such that $$\frac{2}{q}<\frac{\varepsilon}{3}$$ ), and choose $$N$$ to be large enough ( such that $$\frac{q}{N}<\frac{\varepsilon}{3}$$ ).

Then, for any $$n\ge N$$, write $$n = sq+r$$ with $$0\le r < q$$. The following estimate holds: \begin{align*} \# \left\{0\le j < n\,:\,\{j\alpha\} \in[a,b]\right\} & \ge \sum_{t=1}^{s} \# \left\{(t-1)q\le j < tq\,:\,\{j\alpha\} \in[a,b]\right\} \\ & \ge s\left(q(b-a) - 2\right) \\ & = n\left(b-a\right) - 2s - r(b-a). \end{align*}

In the second inequality the number of subintervals from a partition of the unit interval into $$q$$ subintervals of length $$1/q$$ that intersect $$[a,b]$$ bounds the number of orbit points in $$[a,b]$$. The error in this count is at most two, the reason being that in any partition of the interval into subintervals there are at most two subintervals that intersect $$[a,b]$$ but are not contained in it. Since $$\frac{s}{n} \leq \frac{1}{q} < \frac{\varepsilon}{3}$$ and $$\frac{r}{n} \leq \frac{q}{n} < \frac{\varepsilon}{3}$$, this proves that

$$\frac{\# \left\{0\le j < n\,:\,\{j\alpha\} \in[a,b]\right\}}{n} \ge b-a - \varepsilon.$$

The other inequality is proved similarly: \begin{align*} \# \left\{0\le j < n\,:\,\{j\alpha\} \in[a,b]\right\} & \le \sum_{t=1}^{s+1} \# \left\{(t-1)q\le j < tq\,:\,\{j\alpha\} \in[a,b]\right\} \\ & \le (s+1)\left(q(b-a) + 2\right) \\ & = n\left(b-a\right) + 2(s+1) + (q - r)(b-a), \end{align*} so, $$\frac{\# \{0\le j < n\,:\,\{j\alpha\} \in[a,b]\}}{n} \le b-a + \varepsilon.$$ Since $$\varepsilon$$ is arbitrary, this proves \eqref{eq:equidistribution}.