Distribution of

Prepared by Valerio De Angelis

We prove the following theorem:

Theorem A

Let be a real number, and let fractional part of .

i) If is rational, then the sequence is periodic, and so is a finite set

ii) If is irrational, then is uniformly distributed over the interval , in the sense that for every interval I,
(1)

Proof of part i)

If , where p and q are integers, then . So has period q, and

Proof of part ii)

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

Theorem B Any continuous function on can be expressed as an infinite sum

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 (which we can think of as a tolerance level for the error), we can find some m such that as soon as k is larger than m, but this number m may well be different for different x. The second statement is stronger: it tells us that given a tolerance number for the difference , we can find a single m such that when k is larger than m, is true for every x. This is expressed by saying that the infinite series converges uniformly to on

We now proceed to the proof of (1), assuming that is irrational. For any interval I, let's denote by the indicator function of I, that is,

.

Then the first digit of is equal to d if and only if , and we have

.

So (1) is equivalent to:
2)

Note that , so that (2) is the same as
(3)

We will first prove that (3) holds for any continuous function on (of course, is not continuous). So we will prove:
(4)

First we fix an and use Theorem B to find some m such that the partial sum is uniformly within of , that is for all x in . Then we calculate

(5).

So we are led to consider the sums and . To compute these sums, we note that they are the imaginary and real part, respectively, of the sum , which is easily computed:

.

The crucial ingredient for the legitimacy of this calculation is the fact that is irrational, because it ensures that for every non-zero integer j, .

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

and

.

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 .

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

and

whenever . Then we conclude that if ,

.

Now note that , as it follows by integrating the Fourier series for over .

So we have proved that given any , we can find some N such that

whenever . In just the same way we can prove that

,

and we conclude that for all large N. This means, by definition, that , and (4) is proved.

To finish our proof, we now need to show that (3) follows from (4). The idea is simple: even though is not continuous, we can approximate it with continuous functions. To be precise, for each we can find a continuous function such that and .

For example, if , we can take in the picture below to make the shaded area less than , with some obvious modifications in case one of the end points of I is an end point of .

Then we find, for large enough n,

In a similar way, we can find a continuous function such that and (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 , we have

for all large enough n, which means that , and (3) is proved. This concludes the proof of Theorem A.

Notes

The problem of determining the asymptotic distribution of sequences determined by simple transformtions of the unit interval has been much investigated. The sequence we considered in this problem arises from the transformation (a translation by ), because we have . A much more difficult problem is to understand the distribution of sequences arising from multiplication by a number, for example . Iteration of this transformation leads to sequences such as , 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", by Hardy and Wright, Theorem 445, pp. 390-391. (This reference provided by Allen Stenger). A succinct proof along the lines of our exposition is in "An introduction to Ergodic Theory" by P.Walters, Springer-Verlag GTM, Theorem 1.8.