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

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!

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 actually, none of these statements are true.

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}}$$.

• thanks! Just to clarify your notation [x] is floor(x)? May 10 '20 at 16:57
• I've just worked throught, thanks for such a detailed answer, I have one question, how does $k\,\theta+2\,a\,\pi[2\,\pi]=k\,\theta[2\,\pi]=\theta_k$, I can't see how the l.h.s reduces to the right, thanks! (I am a number theory noob! so apologies for my ignorance) May 10 '20 at 17:18
• Forgive me for this, I used French notations assuming they were also used internationally. $x=y[p]$ is just the same as $x=y\,\mathrm{mod}\,p$. This also answers your second question: since $2\,a\,\pi = 0\,\mathrm{mod}\,2\,\pi$ (because $a$ is a whole number), then $k\,\theta + 2\,a\,\pi = k\,\theta\,\mathrm{mod}\,2\,\pi$. Finally, $k\,\theta\,\mathrm{mod}\,2\,\pi$ is $\theta_k$ by definition. May 10 '20 at 17:35
• perfect! I should've also been clearer with my definition of [ ] May 10 '20 at 18:20