Universality and coverage of irrational multiples of $2\pi$ In $[0, 2\pi)$

Question

This related to the proof of universality (pg 196),and partially related to the question Why is Deutsch's gate universal?, however i'm trying to workout a more rigorous proof and understanding of why irrationality is so important.

For $\theta_k \in [0,2\pi)$, $\theta_k = (k\theta)\text{mod }2\pi$, I am struggling to see how for a sequence $k \in \mathbb{Z}$, $k = {1\dots} N$ that the set of $\theta_k$ fills up the interval $[0,2\pi)$, and why is is important that $\theta$ is an irrational multiple of $2\pi$. Does irrationality indicate the uniqueness of each $\theta_k$? This is something I was trying to prove but can't seem to get very far, based on

$\alpha \mod \beta = a - \beta[\alpha/\beta]$, where $[]$ is the floor.

using $\alpha = \gamma(2\pi)$, where $\gamma$ is irrational, and $\beta=2\pi$

$\theta_k =k\gamma(2\pi) - 2\pi[k\gamma(2\pi)/2\pi] = k\gamma(2\pi) - 2\pi[k\gamma]$, however I can't see how this yields uniqueness for irrational $\gamma$ and not for a rational $\gamma$.

If $\gamma$ is rational $\gamma = \frac{p}{q}$, then $\frac{kp}{q}$ is still unique unless $k=1$.

....Or I could just be taking entirely the wrong approach!

Answer 1

There are two statements in your question:

1. If $\theta$ is a rational number of $2\,\pi$, then $\left(\theta_k\right)_{k\in\mathbf{Z}}$ does not reach every $x\in[0\,;\,2\,\pi)$
2. If $\theta$ is an irrational number of $2\,\pi$, then $\left(\theta_k\right)_{k\in\mathbf{Z}}$ does reach every $x\in[0\,;\,2\,\pi)$

We can prove that while the former is true, the latter is false.

Let us consider the first one for now. Let $\theta=2\,q\,\pi$ with $q\in\mathbf{Q}$. Then we can write $q=\frac{a}{b}$ with $(a,b)\in\mathbf{Z}^2$. We can then show that the sequence $\left(\theta_k\right)_{k\in\mathbf{Z}}$ contains at most (exactly actually, if $\frac{a}{b}$ is the irreducible form of $q$) $b$ different elements modulo $2\,\pi$. Indeed, we have:

$$\theta_{k+b}=(k+b)\,\theta\,\mathrm{mod}\,2\,\pi = k\,\theta+2\,a\,\pi\,\mathrm{mod}\,2\,\pi=k\,\theta\,\mathrm{mod}\,2\,\pi=\theta_k$$

Hence, the sequence $\left(\theta_k\right)_{k\in\mathbf{Z}}$ if $b$-periodic. As such, it contains at most $b$ different elements. Hence, the sequence $\left(\theta_k\right)_{k\in\mathbf{Z}}$ does not reach every $x\in[0\,;\,2\,\pi)$.

Let us now consider the second statement. Let $\theta=2\,\gamma\,\pi$ with $\gamma$ being an irrational number. Let $x=2\,k'\,\pi+x'$. Then:

$$\theta_k=x\,\mathrm{mod}\,2\,\pi\iff2\,k\,\gamma\,\pi=2\,k'\,\pi+x'$$

There are now two cases: either $\gamma\,\pi$ is rational, either it isn't. In the first case, $2\,k\,\gamma\,\pi$ is always rational. Hence, it cannot reach $1+2\,k'\,\pi$ whatever $k'$ is since it is an irrational number. Hence, let us now now consider that $\gamma\,\pi$ is irrational. Then $2\,k\,\gamma\,\pi$ is always irrational (for $k\neq0$). Let us consider $x'=\pi$ then. The equation becomes:

$$2\,k\,\gamma=2\,k'+1$$

Since $\gamma$ is irrational, then so is $2\,k\,\gamma$. However, $2\,k'+1$ is rational. Hence, this equation cannot hold. Hence, in every case, we found $x'\in[0\,;\,2\,\pi)$ such that $x'$ is not reached by the sequence $\left(\theta_k\right)_{k\in\mathbf{Z}}$.

However, what you can also prove is that every $x'\in[0\,;\,2\pi)$ can be approached as close as you want, given that $\gamma$ is irrational.

Indeed, let us consider the subgroup of $(\mathbf{R}, +)$ spanned by $\theta$ and $2\,\pi$, that is:

$$\left\{p\,\theta+2\,q\,\pi\middle|(p,q)\in\mathbf{Z}^2\right\}$$

As a subgroup of $(\mathbf{R}, +)$, it is either discrete (like $\mathbf{Z}$) or dense (like $\mathbf{Q}$) within $\mathbf{R}$. In our case, we can show that it is dense within $\mathbf{R}$.

Let us assume that it is discrete. Then, there exists $\lambda=p\,\theta+2\,q\pi$ such that every element $x$ of this set can be written as $x=k\,\lambda$, with $k\in\mathbf{Z}$. Since we know that $2\,\pi$ is in this group, we can write:

$$2\,\pi=k\,\lambda=2\,k\,p\,\gamma\,\pi+2\,k\,q\,\pi\iff 1=k\,p\,\gamma+k\,q\iff\gamma=\frac{\frac1k-q}{p}$$

Hence, it implies that $\gamma$ is rational, which we assumed to be false. Hence, this group is dense within $\mathbf{R}$. What that means is that every element of $\mathbf{R}$ can be approached arbitrarily close using an element of this subgroup. More formally:

$$\forall\varepsilon>0, \forall x\in\mathbf{R},\exists(p, q)\in\mathbf{Z}^2,|p\theta+2\,q\,\pi-x|<\varepsilon$$

By reducing modulo $2\,\pi$, you can finally conclude that every $x'\in[0\,;\,2\,\pi)$ can be approached arbitrarily close by a member of the sequence $\left(\theta_k\right)_{k\in\mathbf{Z}}$.