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:


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:


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:


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

  • $\begingroup$ thanks! Just to clarify your notation [x] is floor(x)? $\endgroup$ – Sam Palmer May 10 '20 at 16:57
  • $\begingroup$ 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) $\endgroup$ – Sam Palmer May 10 '20 at 17:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Tristan Nemoz May 10 '20 at 17:35
  • $\begingroup$ perfect! I should've also been clearer with my definition of [ ] $\endgroup$ – Sam Palmer May 10 '20 at 18:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.