Dirichlet's Approximation Theorem

Branko Ćurgus

On this page $\mathbb Z$ denotes the set of all integers and $\mathbb R$ denotes the set of all real numbers. We use the floor and the ceiling function defined on $\mathbb R$ respectively as \begin{align*} \lfloor x \rfloor & = \max \bigl\{ k \in \mathbb Z \ | \ k \leq x \bigr\}, \\ \lceil x\rceil & = \min \bigl\{ k \in \mathbb Z \ | \ x \leq k \bigr\}. \end{align*} An immediate consequence of these definitions is that for all $x \in \mathbb R$ we have \[ \lfloor x \rfloor \leq x \lt \lfloor x \rfloor + 1 \quad \text{and} \quad \lceil x\rceil -1 \lt x \leq \lceil x\rceil. \] Or, equivalently, \[ 0 \leq x - \lfloor x \rfloor \lt 1 \quad \text{and} \quad 0 \leq \lceil x\rceil - x \lt 1. \]
Dirichlet's Approximation Theorem. For every $\alpha \in \mathbb R$ and every $n \in \mathbb Z^+$ there exist $q \in \{1,\ldots,n\}$ and $p \in \mathbb Z$ such that \begin{equation*} \label{eq-DAT} \bigl| q \alpha - p \bigr| \lt \frac{1}{n}. \end{equation*} The formal statement is as follows \begin{equation*} \forall\, \alpha \in \mathbb R \ \ \forall\, n \in \mathbb Z^+ \quad \exists\,q \in \{1,\ldots,n\} \ \ \exists\,p \in \mathbb Z \qquad \bigl| q \alpha - p \bigr| \lt \frac{1}{n}. \end{equation*}
Proof. Let $\alpha \in \mathbb R$ be arbitrary and let $n \in \mathbb Z^+$ be arbitrary. Consider the following set of numbers \begin{equation} \label{eq-nnum} s \alpha - \lfloor s \alpha \rfloor, \qquad s \in \{0,1,\ldots,n\}. \end{equation} Since \begin{equation*} \forall\, s \in \{0,1,\ldots,n\} \qquad s \alpha - \lfloor s \alpha \rfloor \in [0,1) \end{equation*} and since \begin{equation*} \bigl[ 0, 1 \bigr) = \Bigl[ 0, \frac{1}{n} \Bigr) \bigcup \Bigl[ \frac{1}{n}, \frac{2}{n} \Bigr) \bigcup \cdots \bigcup \Bigl[ \frac{n-1}{n}, 1 \Bigr), \end{equation*} we think of the numbers in \eqref{eq-nnum} as $n+1$ pigeons which live in the following $n$ pigeonholes \begin{equation*} \Bigl[ 0, \frac{1}{n} \Bigr), \Bigl[ \frac{1}{n}, \frac{2}{n} \Bigr), \ldots, \Bigl[ \frac{n-1}{n}, 1 \Bigr). \end{equation*} By the Pigeonhole Principle there exists a pigeonhole with two pigeons. That is, there exists $k_0 \in \{0,1,\ldots,n-1\}$ and $s_1, s_2 \in \{0,1,\ldots,n\}$ such that $s_1 \lt s_2$ and (two pigeons in one pigeonhole) \begin{equation*} s_1 \alpha - \lfloor s_1 \alpha \rfloor, \ s_2 \alpha - \lfloor s_2 \alpha \rfloor \in \Bigl[ \frac{k_0}{n+1}, \frac{k_0+1}{n} \Bigr). \end{equation*} Since the length of the pigeonhole is $1/n$, the distance between the pigeons is less then $1/n$. That is: \begin{equation} \label{eg-contra0} \Bigl| \bigl( s_2 \alpha - \lfloor s_2 \alpha \rfloor \bigr) - \bigl( s_1 \alpha - \lfloor s_1 \alpha \rfloor \bigr) \Bigr| \lt \frac{1}{n}. \end{equation} Setting $q = s_2 - s_1$ and $p = \lfloor s_2 \alpha \rfloor - \lfloor s_1 \alpha \rfloor$, inequality \eqref{eg-contra0} becomes \begin{equation*} \bigl| q \alpha - p \bigr| \lt \frac{1}{n}. \end{equation*} Since $s_1, s_2, \lfloor s_1 \alpha \rfloor$ and $\lfloor s_2 \alpha \rfloor$ are integers, we have that $q, p \in \mathbb Z.$ It remains to prove that $q\in \{1,\ldots,n\}.$ Since $s_1 \lt s_2$, we have $q \gt 0$, that is $q \in \mathbb Z^+.$ Since $s_1, s_2 \in \{0,1,\ldots,n\}$, we have $s_2 - s_1 \leq n-0=n$. Thus, $q\in \{1,\ldots,n\}.$ This proves Dirichlet's Approximation Theorem.