Notes on Equidistribution

Jacques Verstraete
Department of Mathematics
University of California, San Diego
La Jolla, CA, 92093.
E-mail: [email protected].

1 Introduction
For a real number a we write {a} for the fractional part of a. A sequence (an )nN is
equidistributed if for every a, b [0, 1] with a < b,
|{n N : {an } (a, b)}|
= b a.
N
N
lim

For convenience, we refer to the nth term as representative of the whole sequence. For

instance, the sequence n 2 appears to be equidistributed as the plot of the fractional

parts up to one thousand suggests, whereas log n does not:
1.0

1.0

0.8

0.8

0.6

0.6

0.4

0.4

0.2

0.2

200

400

600

800

1000

200

400

600

800

1000

Plot of { 2n} and {log n} for n 1000.

We shall see shortly that the evidence supports the truth for these two examples. Weyls
(1909) celebrated equidistribution theorem states that integer multiples of an irrational
1

number are equidistributed. The key to proving Weyls Theorem is the equivalence of
equidistribution with vanishing upper bounds on exponential sums sums of the form
N

exp(2if (n))

n=1

where f : N C. It is traditional to write e(x) instead of exp(2ix). The following is

a part of Weyls criterion for equidistribution:
Theorem 1 A sequence an is equidistributed if and only if for each k N,
N
1
e(kan ) = 0.
N N
n=1

lim

This is to say that if we wrap the sequence an around the unit circle in the complex plane
k times, then the centroid of the points obtained converges to the origin. The proof of
this theorem is fairly straightforward, and hinges on approximating integrable functions
by step functions and trigonometric polynomials specically the Stone-Weierstrass
theorem. We defer the proof of the theorem until later, since it is part of more general
theory.

2 Weyls Equidistribution Theorem

For an irrational , we want to show that the sequence n is equidistributed. This is
an instant consequence of Weyls criterion and the following lemma. Throughout this
material, is the distance from the real number to the nearest integer.
Lemma 1 Let , R. Then for N N,
N




e(n + ) min{N, (2)1 }

n=1

Proof. The constant does not aect the inequality. If = 0, then the sum is N . If
= 0, then the sum is e()(1 e(n))/(1 e()) since it is a geometric series. As
sin z =

1 iz
(e eiz ),
2i

this is at most | sin |1 . Since | sin | 2, the inequality follows.

Theorem 2 Let be irrational. Then n is equidistributed.

Proof. By Weyls criterion, we have to show for every k N that
N

1 

lim
e(kn) = 0.

N N
n=1

Now k is irrational, so by the last lemma if N is large enough then the sum is at most
1/2k. Relative to N , this is a constant, and therefore
N

1
1 

e(kn)

N n=1
N

which clearly converges to zero.

In the proof of Weyls Theorem above, a key fact is that k is non-zero when is
irrational. In the next sections, we will be exploring equidistribution of polynomial sequences i.e. sequences {(n)} where is a monic polynomial and is irrational. In this
case, a key to bounding the appropriate exponential sum is the quality of approximation
of by a rational with small denominator.

3 Rational approximation
How well can we approximate an irrational number by a rational number? Of course
the answer is arbitrarily well since the rationals are dense in the reals. More importantly,
given N N, how well can one approximate by a rational with denominator at most
N ? A good answer is given by the so-called Dirichlet box principle, which is in fact an
application of the pigeonhole principle.
Theorem 3 Let R and N N. Then there exist p, q N such that q N and

p 
1

.
 
q
q(N + 1)
Proof. Notice that for distinct 0 n N , we have {n} [0, 1] so there are two
integers m, n N such that {m} and {n} lie in an interval of width 1/(N + 1). It is
left then as an exercise as to what q should be.
The reader may then verify the following consequence of Dirichlets Theorem as an
exercise:
Corollary 1 Let R. Then there are innitely many pairs (p, q) of coprime integers
such that | p/q| 1/q 2 .
3

3.1 Liouvilles Theorem

It is not hard to check that this corollary is best possible by considering algebraics of
degree two over Q. More generally, one has Liouvilles Theorem (1844):
Theorem 4 Let R be algebraic of degree n over Q. Then there is a constant c > 0
such that for any p, q N,

p 
c

  > n .
q
q
Proof. Let f be an irreducible polynomial of degree n with integer coecients such
that f () = 0 for instance consider a minimal polynomial for over Q and use Gauss
Lemma. For any p, q N, we have |q n f (p/q)| 1. By the mean value theorem, there is
x [, p/q] such that
f (p/q) f ()
= f (x).
p/q
Taking absolute values we obtain
|f (x)|| p/q|

1
qn

which completes the proof upon taking c = 1/|f (x)|.

The above result shows that transcendental numbers exist any real for which Theorem 4 fails in the sense that for every n there exists p, q such that | p/q| 1/q n is
called a Liouville number and must be transcendental. The Thue-Siegel-Roth Theorem,
proved rst by Thue (1909) shows further that if is algebraic over Q, then for every
> 0 the inequality

p 
1

  < 2+
q
q
has only nitely many solutions (p, q), and so the c/q n term in Liouvilles Theorem can
be replaced by q 2+o(1) as q . Lang conjectures the upper bound 1/(q 2 log q)1+o(1) as
q .

4 Bounds on exponential sums

A rst step to proving bounds on exponential sums is the following lemma:
Lemma 2 Let M, r, N N and let 1 , 2 , . . . , M be real numbers with i j r1
whenever i = j. Then
M

i=0

{ 1
}
min
, N 2N + 2r(log N + 2).
i
4

Proof. Without loss of generality, i [1/2, 1/2] and the contribution to the sum
from the non-negative i is at least one half of the total. We may assume 0 0 <
1 < < n . Then
n

i=0

{ 1
}
r
r
min
,N
N+
N+
.
i
N
i
i>r/N

If N > r, then the last term is at most r(log n + 1). However since n/r n 1/2, we
have 2n r < N and so the bound is r(log N +1) in this case. If N r, then estimating
the last term with logarithms shows that it is at most r log(2nN/r) + r r(log N + 1).
It follows that the whole sum is at most 2N + 2r(log N + 2).

Lemma 3 Let N, M N, and let R be chosen so that there exists p, q N with

(p, q) = 1 and | p/q| 1/q 2 . Then
M

n=1

{
min

} ( 2M
)
1
,N
+ 1 (2N + 4q(log N + 2)).
n +
q

Proof. For i, j N, it is straightforward to see that

i j (i j)p/q

|i j|
.
q2

When 0 < |i j| q/2, (i j)p/q 1/q since p and q are relatively prime, whereas
|i j|/q 2 1/2q. It follows that i j 1/2q for 0 < |i j| q/2. Split the range
of summation, namely [M ], into m M/(q/2 + 1) + 1 intervals I1 , I2 , . . . , Im of length
at most q/2 + 1. On each of these intervals, we apply the last lemma with r = 2q, so
that for each j [m],

{
min

nIj

}
1
, N 2N + 4q(log N + 2).
n +

It follows that the entire sum is at most

2mN + 4qm(log 2q + 2) <

( 2M
q

This completes the proof.

)
+ 1 (2N + 4q(log N + 2)).

5 Weyl dierencing
The above lemmas allow us to nd bounds on exponential sums using a method known
as Weyl dierencing. This method is encapsulated by the following lemma.
Lemma 4 Let N N and M [N ], and let f : [N ] C. Then
M 1 N m
N

2

N 



e(f (n))
e(f (n + m) f (n)).


M
n=1
m=0 n=1

Proof. We have the identity

N

M N m
1
e(f (n)) =
e(f (n + m)).
M m=1 n=1m
n=1

Applying Cauchy-Schwarz to this identity, we get

N
M
N m

2
2
1 



e(f (n))
e(f (n + m)) .


M m=1 n=1m
n=1

Applying the dierencing method to the inner sum, the whole expression is bounded
above by
M M

1 

e(f (n + k) f (n + ))

M k=1 =1 nI
k,

where Ik, consists of all n such that 1 n + k N and 1 n + N . This is the key
point of the lemma: the inner sum depends only on |k |, which takes on at most M
values. Letting m = |k |, each value of m occurs at most N times and so we get the
bound
M 1 N m

N 

e(f (n + m) f (n)).

M m=0 n=1
This is the required bound.
Weyl use the method of dierencing to show that (n) is equidistributed whenever is
a monic non-constant polynomial. We apply this result explicitly in the quadratic case
as follows:
Theorem 5 Let q, N N and let be a monic quadratic polynomial. Suppose R
and for some relatively prime p, q N, | p/q| 1/q 2 . Then
N

 ( 4N
)1/2


+1
(2N + 4q(log N + 2))1/2 .
e((n))

q
n=1

Proof. Consider the preceding lemma with f (x) = (x) and M = N . It is necessary
to estimate
N
1N
m




e(f (n + m) f (n)).

m=0 n=1

The inner sum is

m
N

{


e(2mn) min

n=1

}
1
,N m
22m

according to Lemma 1. Doubling the range of m, this is at most

2N
2

m=0

{
min

}
1
,N .
m

By Lemma 3 with M = 2N 2, this sum is at most

( 4N
)
+ 1 (2N + 4q(log N + 2)).
q
Applying Lemma 4,
N

2 ( 4N
)


e((n))
+ 1 (2N + 4q(log N + 2)).

q
n=1

This completes the proof.

An equidistribution theorem for (n) when is monic and quadratic follows quickly
from Theorem 5:
Corollary 2 Let be a monic quadratic polynomial and irrational. Then (n) is
equidistributed.
Proof. Fix k N. Innitely many choices of q are available so that there exists p, q
relatively prime with |k p/q| 1/q 2 . By Weyls criterion, we require
N

1 

e(k(n)) 0

N n=1

as N . The upper bound for the left side given by Theorem 5 is

(4

1 )1/2 (
4q(log N + 2) )1/2
+
2+
.
q N
N

For each xed q, taking the limit as N the above expression converges to
Since q can be taken to be arbitrarily large, the limit must be zero.
7

8/q.

This corollary eectively shows that if is irrational and is quadratic, then for innitely
many N we have
N





e((n)) N log N .

n=1

The reader may wish to nd for which the above sum is as close to linear in N as
desired for innitely many N .
Before we move on to the case that is a polynomial of higher degree, we consider Gauss
sums. Remarkably, it is possible to give a simple explicit formula in the case (x) = x2 ,
as shown by Gauss (1811). Let denote the quadratic character in ZN , so (x) = 1 if x
is a non-zero quadratic residue, (x) = 1 if x is a non-residue, and (0) = 0. This is
a special example of a character of a group, and much here be generalized to work with
characters of general abelian groups. Gauss proved the following result, which can be
proved fairly simply by squaring each side (recall here = e2i/N ):
Lemma 5 Let N be prime. Then




(x) x  = N .

xZN

It is actually a tricky task to determine the sign of the sum itself. It can be shown (as

Gauss did after determining the sum up to sign) that the sum is N if N = 1 mod 4

2
and i N if N = 3 mod 4. The reader may then wish to check the value of N
n=1 e(n ).

6 Equidistribution of polynomials
Weyl generalized his equidistribution theorem to show that for a polynomial , (n) is
equidistributed if and only if has at least one non-constant irrational coecient. This
result actually follows quickly from the dierencing method of Lemma 4, and generalizes
as follows:
Theorem 6 Let an be a sequence such that an+m an is equidistributed for all m N.
Then an is itself equidistributed.
Proof. Lemma 4 gives, for any xed M [N ],
N
M 1
N m
2

1
1 
1 


lim 2 
e(an )
lim
e(an+m an ).

N N
M m=0 N N n=1
n=1

The inner term for m = 0 is N . Since an+m an is equidistributed for all m N,

N m
1
e(an+m an ) = 0
lim
N N
n=1

for each m N. So the inner sum converges to 1 for m = 0 and to zero otherwise. It
follows that
N
2
1 
1

lim
e(a
)


n
2
N N
M
n=1
and since M was arbitrary, the limit is zero. By Weyls criterion, this means an is
equidistributed.
Corollary 3 If is a monic polynomial and is irrational, then (n) is equidistributed.
Proof. This is Weyls Theorem if is linear. Suppose has degree k 2 and proceed
by induction on k. Let = km, which is an irrational number, and an = (n). Then

an+m an = nk1 + := (n)

where is a monic polynomial of degree k 1. By induction, (n)

is equidistributed
and therefore an+m an is equidistributed for every xed m N. The last lemma nishes
the proof.

7 Weyls Inequality
We turn now to bounds on exponential sums with polynomial exponent. The main
result of this section, which gives such a bound depending on the quality of rational
approximation of the leading coecient of the polynomial exponent, is Weyls inequality.
We need the following preliminary lemma.
Lemma 6 Let k, n N. For every > 0, the number d(n) of ways of writing n has an
ordered product of k positive integers satises d(n) n .

Proof. Let n = ri=1 pai i where p1 , p2 , . . . , pr are the primes in [n] and ai is a non-negative
integer. Then the number (n) of divisors of n satises
(n) =

i=1

(ai + 1).

Fixing t [r],
(n)

(ai + 1)

i=1

2ai

i=t+1

(log2 n + 1)

i=1

i=t+1

(1 + log2 n) n

t 1/ log2 t

a / log2 pi

pi i

(
2 log n )
exp 2t log log n +
.
log pt

Choose t = log n/(log log n)2 . Then the above expression is at most n4/ log log n . Now
the number of ways of writing n as an ordered product of k positive integers is at most
(n)k n .
The reader may check that one make take = 4/ log log n, and this is roughly best
possible up to the constant four in the exponent, which can be improved to log 2 as
n . We are now in a position to prove Weyls Inequality, which we state in the
following form:

Theorem 7 Let denote a monic linear polynomial of degree k 2 and let R

satisfy | p/q| 1/q 2 where (p, q) = 1. Then for every > 0,
N


( 1 q log N
1 )21k


.
e((n)) N 1+
+
+

q
Nk
N
n=1

Proof. For j [k 1] let

fj := fj (m1 , m2 , . . . , mj+1 ) =

k!
mkj m1 . . . mj .
(k j)! j+1

We shall prove that for j [k],

j
Mi  M
j+1
N

2j






2j j1
e((n)) N
e(fj )


n=1

i=1 mi =0 mj+1 =1

where M1 = N 1 and Mi = N j<i mj for i 2. For j = 1, this is precisely Lemma

4. Proceeding inductively, assume we have the above inequality up to a certain value
10

j 1, then

2
j1 Mi  Mj
N

2j


j




e((n))
N 2 2j
e(fj1 )


n=1

i=1 mi =0 mj =1

j 2j

N2

2
j1 Mi  Mj




N j1
e(fj1 )

i=1 mi =0 mj =1

2j j1

j1 Mi  Mj
2



e(f
)

j1 
i=1 mi =0 mj =1

2j j1

j
Mi  M
j+1




e(fj )

i=1 mi =0 mj+1 =1

as required. Now we use the case j = k 1, namely

Mk
Mi 
N
k1

2k1






2k1 k
e((n))
e(fk1 ).
N


n=1

i=1 mi =0 mk =1

We consider rst the contribution to the sum from all terms where some mi is zero. Since
fk1 = 0 in that case, the contribution is trivially less than N k1 . Now consider the
contribution from all terms where no mi is zero. Crucially, fk1 is linear in all variables
and therefore Lemma 1 applies:
Mk


{


e(fk1 ) min

mk =1

1
, N }.
2k!m1 m2 . . . mk

We change the summation variables to m := k!m1 m2 . . . mk1 . With M = k!N k1 , by

k1
Lemma 6, there are at most M < k! N 2 solutions to m = k!m1 m2 . . . mk1 for
m [M ]. Therefore the sums are at most

m=1

{
min

}
1
,N .
m

By Lemma 3, this is at most

k! N 2

k1

( 2M
q

)
+ 1 (2N + 4q(log N + 2)).
11

Finally, cleaning up all the upper bounds together gives, for any > 0,
N

2k1


e((n))

n=1

2k1 k

k! N

2k1

( 2M
q

)
+ 1 (2N + 4q(log N + 2))

1 )
k! N
+
(2N + 4q(log N + 2))
qN k N k
( 1 q log N
1)
k1
k!+1 N 2 (1+)
+
+
.
q
Nk
N

2k1 (1+)

( 2M

Taking 2k1 th roots completes the proof.

The reader should verify that Weyls Inequality does not show that the exponential sum
is o(N ), so equidistribution of (n) does not follow immediately. It is possible to obtain
equidistribution from Weyls Inequality by carefully partition the range of summation
of the exponential sum according to an innite sequence q1 , q2 , . . . of integers such that
| pi /qi2 | 1/qi2 where (pi , qi ) = 1 for all i, and the details are left to the reader.
We also remark that there is a weakness in the proof where we replace the summation
variable m1 m2 . . . mk by m and use the estimate on the number of divisors uniformly
for all terms in the sum. This is responsible for the N in Weyls Inequality, and one
may take 1/ log log N . In reality, this can be improved to (log N )c for a constant c
depending on k, since for every > 0, for almost every integer n, (n) = (log n)log 2+ .

8 Application to rational approximation

We show how to use Weyls Inequality to say something more about rational approximation. Another view of Dirichlets Theorem is to state that for every N N and R,
there exists q N such that q 1/N . Putting forth the same question for (q)
where is a monic polynomial with integer coecients, we shall use Weyls Inequality
to prove the following theorem:
Theorem 8 Let R and k, N N where k 2 and let 0 < < 2k1 . Then there
exists q N such that
q k N .
The following lemma shows that if a set A of elements of ZN is disjoint from a large

interval, then there is a non-zero r such that |A(r)|

is large. The idea is that if Theorem 8 were false, and is close to P/Q, then A = {P, 2k P, . . . , N k P } is disjoint from

(2QN , 2QN ], and so |A(r)|

is large for some non-zero r, but this would contradict
Theorem 7, Weyls Inequality.
12

Lemma 7 Let Q be a prime and A ZQ , and suppose A (2M, 2M ] = . Then there

exists r : 0 < r < (Q/M )2 such that

|A(r)|

Proof. Put I = (M, M ] and note

M |A|
.
2Q

(I I)(x)A(x) = 0.

xZQ

It follows that

2 A(r)
= 0.
|I(r)|

rZQ

Taking out the term for r = 0 and using the triangle inequality, we obtain

2 |A(r)|

|I(r)|
4M 2 |A|.
r=0

However by Lemma 1,


1



|I(r)|
=
rx  min{ r , |I|}.
Q
xI
If Q/2 < r < Q/2, then this is min{Q/r, 2M }. Consequently if L = (Q/M ),

( Q )2

2 |A(r)|

2 + |A|
|I(r)|
max |A(r)|
|I(r)|
0<|r|L
r
r
r=0
|r|>L

3|A|Q

|I|Q max |A(r)|

+
.
0<rL
L2

Therefore there exists r for which |A(r)|

M |A|/2Q.
Proof of Theorem 8. Approximate arbitrarily closely by a rational P/Q with Q
prime. Without loss of generality, = P/Q. If the theorem were false, then A =
{P, 2k P, . . . , N k P } and (2M, 2M ] are disjoint when M = QN . Applying the last
lemma, we nd r such that 0 < r (Q/M )2 2N 2 , and such that

|A(r)|
N 1 .
Let R = N k1/4 . Via Dirichlets Theorem, choose q R with qr/N < 1/R using
Dirichlets Theorem. If R q > 12 N 1/4 , then Weyls Inequality shows that for any > 0
we have
k1

|A(r)|
N 1+2
.
13

This is a contradiction since < 2k1 . Therefore q 21 N 1/4 , which shows

(qr)k N (k1)(2+1/4)

N
N 13k/4+(k1)(2) N
R

by the choice of . Also by the choice of ,

qr N 1/4+2 < N,
and this completes the proof.

14