Constructive proof of Kronecker’s density theorem

A couple months ago I shared a blog post on Dirichlet’s approximation theorem which we may use to prove that integer angles are dense in the unit circle. Now, I tried to go further and show that \forall k \in \mathbb{N}, e^{i k\mathbb{N}} is dense in the unit circle. This particular result is interesting because it leads one to deduce that \forall N \in \mathbb{N}, {\bigcap}_{n=0}^N sin( p_n\mathbb{N}) is dense in [-1,1]  where p_n is the nth prime.

This week I learned about the Weyl equidistribution theorem from which this particular result follows as an immediate corollary. However, I wondered whether there might be a simpler proof and after searching I came across a short paper on Kronecker’s density theorem which had exactly the result I wanted and a bit more. The purpose of this blog post is to present the proof contained in this paper.

Kronecker’s density theorem:
If \theta \in \mathbb{R} \setminus \pi \mathbb{Q} , then \{ e^{i \theta n} | n \in \mathbb{Z} \} is dense in the unit circle.

Proof:

1. \mathbb{Q} \pi is dense in \mathbb{R} so it’s enough to prove that:

\begin{aligned} \forall t \in \mathbb{R} \forall \epsilon \in \pi \mathbb{Q} \exists n \in \mathbb{Z}, |e^{it}-e^{in\theta}|<\epsilon \end{aligned} 

Equivalently we have:

\begin{aligned} \forall t \in \mathbb{R} \forall \epsilon \in \mathbb{Q} \pi \exists p,q  \in \mathbb{Z}, |p\theta -t+2q\pi|<\epsilon \end{aligned}

2. Without loss of generality, we may assume that 0<\theta< 2 \pi since given that \theta \notin \mathbb{Q} \pi \exists k \in \mathbb{Z} ,

\begin{aligned} 0< \theta - 2k \pi < 2 \pi \end{aligned} 

It’s sufficient to prove the case t=0 since if we have found p,q \in \mathbb{Z} such that

\begin{aligned} |p\theta +2q\pi|<\epsilon \end{aligned}

for any t \in \mathbb{R} we can find k \in \mathbb{Z} such that:

\begin{aligned} |k - \frac{t}{p\theta+2q \pi}| <1 \end{aligned}

To obtain k it’s sufficient to take the integer part of the fraction in the inequality.

Now, it follows that we have:

\begin{aligned} kp\theta -t+2kq\pi|= |p\theta+2q\pi| |k - \frac{t}{p\theta+2q \pi}|< |p\theta -t+2q\pi|<\epsilon \end{aligned}

3. For fixed \epsilon \in \mathbb{Q} \pi the proof strategy is as follows:

a) starting at e^{i\theta} we move anti-clockwise around the unit circle in steps of arc length \theta until we cross the positive x-axis.

b) \theta \notin \mathbb{Q} \pi so we reach e^{i\theta_1}  where 0< \theta_1<\theta and

\begin{aligned} \exists k \in \mathbb{N}, k\theta=2\pi+\theta_1 \end{aligned}

c) if \theta_1-\theta > \epsilon we’re done. Otherwise, we repeat the procedure with \theta := \theta_1 .

d) The remainder of this proof will show that we can find an upper-bound for the number of iterations of \theta_n required.

5. Before proceeding, it’s useful to note that there exists \{k_n \}_{n=1}^{\infty} \subset \mathbb{N} where at the first iteration we have:

\begin{aligned} k_1\theta = \theta_1 + 2\pi \implies \theta_1 = k_1 \theta mod 2\pi < \theta \end{aligned}

So at the nth iteration we have:

\begin{aligned} \theta_n = \theta \prod_{i=1}^{n} k_i mod 2 \pi \end{aligned}

6. If \theta_i - \theta_{i-1} > -\epsilon , then we’re done as we have:

\begin{aligned} 0< \theta_{i-1}-\theta_{i}= (k_i - 1) \theta \prod_{j=1}^{i-1} k_i mod 2 \pi < \epsilon \end{aligned}

Otherwise, let’s define the smallest M \in \mathbb{N} such that:

\begin{aligned} M \epsilon > \theta \end{aligned}

If the process continued after the Mth iteration we would have:

\begin{aligned} 0< \theta_M < \theta_{M-1} -\epsilon < \theta_{M-2}-\epsilon-\epsilon < ...< \theta-M\epsilon < 0 \end{aligned}

a contradiction.

Note 1: The arguments in this blog post are taken almost entirely from the original paper with some slight modifications.

Note 2: The fact that the proof is constructive is very nice as Kronecker was a very strong advocate of constructive proofs.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s