Suppose we have some irrational $x > 0$ and some $\epsilon > 0$. I want to show that there is at most one rational approximation $\frac{a}{b}$ such that both $| x - \frac{a}{b}| < \epsilon$ and $b < \frac{1}{\sqrt{2 \epsilon}}$

Here are my thoughts. Let $N \in \mathbb{N}$ be the least integer greater than $\frac{1}{\sqrt{2 \epsilon}}$. Then we can use Dirichlet's Approximation Theorem, to get $p,q \in \mathbb{Z}$ such that $1 \leq q < N$, and $|x - \frac{p}{q}| < \frac{1}{N^2} < 2 \epsilon$. I don't know how to deal with that $2$ though, and this says nothing about uniqueness. On the other hand, if we work the other direction and bound $| x - \frac{p}{q}| < \epsilon$, this gives us the wrong bound on $q$.

Honestly I haven't done much work with rational approximations, so I'm pretty lost. If there are any useful theorems or ideas to look into, please let me know! Thanks!

The motivation for this problem comes from Shor's algorithm. In particular, the process of finding the period of $f(r) = x^r \mod N$ for some $x \in \mathbb{Z} / N \mathbb{Z}$ relies on the fact that there is at most one good rational approximation of this form.

I figured out the answer. Leaving it here for anyone in the future looking for an answer to this question.

It turns out, Dirichlet approximations were too heavy of machinery. Suppose we have two rational approximations to $x \in \mathbb{R}$. Call them $\frac{a}{b}$ and $\frac{c}{d}$. So:

  • $|x - \frac{a}{b}| < \epsilon$
  • $|x - \frac{c}{d}| < \epsilon$
  • $0 < b < \frac{1}{\sqrt{2 \epsilon}}$
  • $0 < d < \frac{1}{\sqrt{2 \epsilon}}$

Consider the difference between the two rational approximations. By the triangle inequality, we have: $$ |\frac{a}{b} - \frac{c}{d}| \leq |\frac{a}{b} - x| + |x - \frac{c}{d}| < 2 \epsilon$$

Using our constraints on the denominators though, we have: \begin{align*} |\frac{a}{b} - \frac{c}{d}| &= | \frac{ad - bc}{bd}| \\ &> \left | \frac{ad - bc}{(1/\sqrt{2 \epsilon})(1/\sqrt{2\epsilon})} \right |\\ & = 2 \epsilon |ad - bc| \end{align*}

Combining our inequalities, we have: $$2 \epsilon |ad - bc| < \left |\frac{a}{b} - \frac{c}{d} \right | < 2 \epsilon$$ Looking at the first and third term, and dividing out by $2 \epsilon$ yields: $$ |ad - bc| < 1$$ But $|ad - bc|$ is a non-negative integer! And so it must be zero. Hence, $ad = bc$. From here, showing that $\frac{a}{b} = \frac{c}{d}$ is easy.


Your Answer

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

Browse other questions tagged or ask your own question.