Distribution of \{ n \alpha \}

Prepared by Valerio De Angelis

We prove the following theorem:

Theorem A

Let \alpha be a real number, and let x_n = \{ n \alpha \} be the fractional part of n\alpha.

i) If \alpha is rational, then the sequence x_n is periodic, and so \{ x_n:n \ge 1 \} is a finite set

ii) If \alpha is irrational, then x_n is uniformly distributed over the interval [0,1), in the sense that for every interval I \subseteq [0,1),

Proof of part i)

If \alpha = p/q, where p and q are integers, then

So x_n has period q, and \{ x_n : n \ge 1 \} = \{ x_1, x_2, \dots, x_q \}.

Proof of part ii)

We will make use of the following basic real analysis result:

Theorem B Any continuous function f(x) on [0,1] can be expressed as an infinite sum

This infinite sum is called the Fourier series of the function f(x). In addition, if we write

we have

Most textbooks of real analysis discuss Fourier series. We will not provide a proof of Theorem B in these notes. For a good online reference, click here.

Note: The meaning of the first statement in the theorem is that

for every x. In other words, given any x and any \epsilon > 0 (which we can think of as a tolerance level for the error), we can find some N such that |S_m(x) - f(x)| \le \epsilon as soon as m is larger than N, but this number N may well be different for different x. The second statement is stronger: it tells us that given a tolerance number \epsilon > 0 for the difference |S_m(x) - f(x)|, we can find a single N such that when m is larger than N, |S_m(x) - f(x)| \le \epsilon is true for every x. This is expressed by saying that the infinite series converges uniformly to f(x) on [0,1].

We now proceed to the proof of (1), assuming that \alpha is irrational. For any interval I \subseteq [0,1), let's denote by \chi_I(x) the indicator function of I, that is,

So (1) is equivalent to:

Note that \int_0^1 \chi_I(x) \, dx = |I|, so that (2) is the same as

We will first prove that (3) holds for any continuous function f(x) on [0,1] (of course, \chi_I(x) is not continuous). So we will prove that for any continuous function f(x) on [0,1]

First we fix an \epsilon > 0 and use Theorem B to find some m such that the partial sum S_m(x) = \sum_{j=0}^m ( a_j \sin(2 \pi j x) + b_j \cos (2 \pi j x)) is uniformly within \epsilon of f(x), that is S_m(x) - \epsilon \le f(x) \le S_m(x) + \epsilon for all x in [0,1]. Then we calculate

So we are led to consider the sums \sum_{k=1}^n \sin(2 \pi j x_k) and \sum_{k=1}^n \cos(2 \pi j x_k). To compute these sums, we note that they are the imaginary and real part, respectively, of the sum \sum_{k=1}^n \exp(2 \pi i j x_k), which is easily computed for j > 0 :

The crucial ingredient for the legitimacy of this calculation is the fact that \alpha is irrational, because it ensures that for every non-zero integer j, \sin(\pi j \alpha) \ne 0.

So we conclude that for each fixed non-zero integer j,

This means that all the terms in the sums over j in (5) will tend to zero as n gets large, except the term in the second sum with j = 0.

Since the sums in (5) are finite, we can find some N such that

whenever n \ge N. Then we conclude that if n \ge N,

Now note that b_0 = \int_0^1 f(x) \, dx, as it follows by integrating the Fourier series for f(x) over [0,1].

So we have proved that given any \epsilon > 0, we can find some N such that

whenever n \ge N. In just the same way we can prove that

and we conclude that \left| \frac{1}{n} \sum_{k=1}^n f(x_k) - \int_0^1 f(x) \, dx \right| \le 3 \epsilon for all large N. This means, by definition, that \lim_{n \to \infty} \sum_{k=1}^n f(x_k) = \int_0^1 f(x) \, dx, and (4) is proved.

To finish our proof, we now need to show that (3) follows from (4). The idea is simple: even though \chi_I(x) is not continuous, we can approximate it with continuous functions. To be precise, for each \epsilon > 0 we can find a continuous function f(x) such that \chi_I(x) \le f(x) and \int_0^1 f(x) \, dx \le |I| + \epsilon.

For example, if I=[a,b], we can take \delta \le \frac{\epsilon}{2} in the picture below to make the shaded area less than \epsilon, with some obvious modifications in case one of the end points of I is an end point of [0,1].

Then we find, for large enough n,

In a similar way, we can find a continuous function g(x) such that g(x) \le \chi_I(x) and \int_0^1 g(x) \, dx \ge |I| - \epsilon (take the base of the trapezoid in the figure to be inside I). Then for large enough n we have

In conclusion, we have proved that given any \epsilon > 0, we have | \frac{1}{n} \sum_{k=1}^n \chi_I(x_k) - |I| \, | \le 2 \epsilon for all large enough n, which means that \lim_{n \to \infty} \sum_{k=1}^n \chi_I(x_k) = |I|, and (3) is proved. This concludes the proof of Theorem A.

Notes

The problem of determining the asymptotic distribution of sequences determined by simple transformations of the unit interval has been much investigated. The sequence we considered in this problem arises from the transformation T(x)=x+\alpha \pmod{1} (a translation by \alpha), because we have x_n = T^n(0). A much more difficult problem is to understand the distribution of sequences arising from multiplication by a number, for example T(x) = \alpha x. Iteration of this transformation leads to sequences such as x_n = (3/2)^n \pmod{1}, for which it is unknown whether the asymptotic distribution is uniform.

A combinatorial and fairly elementary proof of Theorem A is found in An Introduction to the Theory of Numbers, 6th edition (2008) by Hardy and Wright, Theorem 445, pp. 520-521. (This reference provided by Allen Stenger). A succinct proof along the lines of our exposition is in An Introduction to Ergodic Theory by Peter Walters, Springer-Verlag Graduate Texts in Mathematics, 2000, Theorem 1.8.