How does pigeonhole principle imply that $|\theta_k-\theta_j|\leq 2\pi/N<\delta$ where $\theta_k=(k\theta)\mod 2\pi$

Question

I am trying to understand this part from the book Page 196, Quantum Computation and Quantum Information by Nielsen and Chuang.

Here $R_{\hat{n}}(\theta)=\cos(\theta/2)I-i(\hat{n}.\vec{\sigma})\sin(\theta/2)$ and $\theta$ is defined such that $\cos(\theta/2)=\cos^2(\pi/8)$ and therefore $\theta$ can be shown to be an irrational multiple of $2\pi$.

So, in the statement we are taking, the desired accuracy as $\delta>0$, an integer $N$ is chosen such that $\delta>\frac{2\pi}{N}$.

Defining $\theta_k$ so that $\theta_k\in[0,2\pi)$ and $\theta_k=(k\theta)\mod 2\pi$, i.e., $k\theta=2\pi t+\theta_k$.

How do I make sense of the rest of the statement ?

How does pigeonhole principle implies that $|\theta_k-\theta_j|\leq 2\pi/N<\delta$ for some distinct integers $j,k\in 1,2,\cdots,N$ ?

Pigeonhole Principle Definitions

1. If n objects are distributed over m places, and if n > m, then some place receives at least two objects. equivalently, if n objects are distributed over n places in such a way that no place receives more than one object, then each place receives exactly one object.

2. If n objects are distributed over m places, and if n < m, then some place receives no object. equivalently, If n objects are distributed over n places in such a way that no place receives no object, then each place receives exactly one object.

Can I make use of this definition to prove $|\theta_k-\theta_j|\leq 2\pi/N$ ?

Answer 1

Pretty sure you need $N+1$ values. Separate $[0,2\pi)$ into $N$ bins of equal length $2\pi/N$, so $$ I_i = [2\pi (i-1)/N, 2\pi i/N)$$ for $1 \leq i \leq N$. By the pigeon hole principle we’d then get two $\theta_k,\theta_l$ in the same bin.

If we take $[0,1)$ instead of $[0,2\pi)$ we might for example have $\theta_1=1/10$, $\theta_2=9/10$ and the distance is clearly bigger than $1/2$. So you’d need $N+1=3$ points for this to work.

Answer 2

Due to irrationality, you won’t hit $2\pi$ for any $\theta_j$ with $1\leq j\leq N$ so there will be no repeats in the $\theta_j$ values.

By pigeonhole, the $\theta_j$ split the unit circle into $N$ subintervals whose boundaries are the $\theta_j$ values. They are are most spread apart when they are equally distributed on the circle. Thus at least two $\theta_i,\theta_j$ are at most $2\pi/N$ radians apart in absolute difference, at the two endpoints of the shortest interval.