For irrational real number $r$, find $n \in \mathbb{Z}$ such that $|nr - [nr]| < 10^{-10}$.

Question

This problem is from the book "A Walk Through Combinatorics" by Richard Bona.

For any irrational number $r$, there exists a positive integer $n$ such that the distance of $nr$ from the nearest integer is less than $10^{-10}$.

I've seen a couple of proofs after my own attempt, which all use the pigeon-hole principle (after all, that was the name of the section of the text), and it makes me wonder if I'm missing something.

The outline of my argument was that since $\mathbb{Q}$ is dense in $\mathbb{R}$, we can find a rational number $p/q$ arbitrarily close to $r$. I think this would imply that $q(p/q) = p = [qr]$ (this is where I'm a little unsure), where $[x]$ denotes the nearest integer to $x$ . Since $p/q$ is arbitrarily close to $r$,

$$|r - p/q| < \epsilon << 10^{-10} \implies q|r - p/q| = |qr - [qr]| < q\epsilon < 10^{-10}$$

where $\epsilon$ is some small positive real number.

Is my reasoning correct? It seems that since $p/q$ is within such a small distance from $r$ that $q(p/q) = p$ would have to be within such a small distance from $qr$, making $p = [qr]$, but this is a little hand-wavy and I'm not sure how to prove or disprove such a claim. Thanks.

Answer 1

Your oversight is that $q$ gets arbitrarily large; the heuristic analysis would conclude $q \epsilon \approx \infty \cdot 0$, which tells you nothing. In fact, I believe it can be shown that the set of possibilities for $|qr - [qr]|$ will actually be dense in $[0, 1/2]$.

To make this argument work, it isn't enough for $p/q$ to be close to $r$: it has to be unusually close to $r$.

Fortunately, this can be done. For any irrational real number $r$, the convergents of its continued fraction are a sequence of rational numbers converging to $r$, each having the property that

$$ \left| r - \frac{p}{q} \right| < \frac{1}{q^2} $$

You should be able to adapt your argument to work if you restrict yourself to such approximations.

Answer 2

$G:= \mathbb Z +r\mathbb Z \subset \mathbb R$ is a subgroup of $\mathbb R$. Because $r$ is irrational $G$ is a free abelian group of rank two. In particular it is not cyclic and therefore not discrete (the discrete subgroups of $\mathbb R$ are just the cyclic ones). A non-discrete subgroup of $\mathbb R$ is dense in $\mathbb R$. So you find elements in $G\setminus \{0\}$ arbitrary close to $0$. Is it clear to you how such an element gives rise to your number $n$?