# 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 prof 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 $$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.$$

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)$ up 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".

-

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