\section{Diophantine approximation}\label{sec:diophapprox}

The following result is often stated with the condition that $Q$
be an integer. Let us prove it for all real $Q\geq 1$. (This variant
is of course
well-known; see, e.g., Lemma 2.1 in Vaughan's {\em The Hardy-Littlewood Method}, 2nd. ed.)

\begin{lemma}[Dirichlet's approximation theorem]\label{lem:dirithm}\index{Dirichlet's approximation theorem|boldindex}
  Let $\alpha\in \mathbb{R}$, $Q\geq 1$. Then there are integers $a$,
  $1\leq q\leq Q$ with $(a,q)=1$ such that
  \begin{equation}\label{eq:kukulir}
    \left|\alpha - \frac{a}{q}\right|< \frac{1}{q Q}.\end{equation}
\end{lemma}
If only a non-strict inequality $\leq$ is desired in (\ref{eq:kukulir}),
the proof below can be modified so as to give a strict inequality for $q$,
that is, $q<Q$.
\begin{proof}
  Let $m = \lfloor Q\rfloor$. Consider the following $m+1$ points
  in the circle $\mathbb{R}/\mathbb{Z}$:
  \[0\cdot \alpha,
  1\cdot \alpha, \dotsc, m\cdot \alpha\; \mo \mathbb{Z}.\] 
  At least two of them must be at distance 
  no more than $1/(m+1)$ from each other. Call them $b_1 \alpha \mo \mathbb{Z}$,
  $b_2 \alpha \mo \mathbb{Z}$,
  $b_1<b_2$. Then
  \[d((b_2 - b_1) \alpha,\mathbb{Z}) = d(b_2 \alpha - b_1 \alpha,\mathbb{Z})\leq
  \frac{1}{m+1} < \frac{1}{Q},\]
  i.e., there is an integer $a$ such that $|(b_2 - b_1) \alpha - a|<1/Q$.
  Define $q = b_2 - b_1$. Then $|\alpha - a/q|<1/q Q$. If $a$, $q$ are not
  coprime, divide both of them by $(a,q)$.
\end{proof}
It is also possible to prove the same lemma using the basic theory of continued fractions;
see Thm. 164 in Hardy-Wright or Thm. 9 in Khinchin's {\em Continued fractions}.


Lemma \ref{lem:dirithm} tells us that, for any $\alpha\in \mathbb{R}$,
there are good approximations $a/q$ to $\alpha$ with $q$ not too large.
However, sometimes we want a $q$ that is
neither too large nor too small. The following lemma shows that
we can fix that, provided that the approximation $a/q$ is not too good
(nor too bad).

\begin{lemma}\label{lem:hardio}
  Let $\alpha\in \mathbb{R}$. Let $a$ and $q\geq 1$ be coprime integers such that
  $\epsilon = |\alpha - a/q|$ satisfies $0<\epsilon\leq 1/q^2$.
  Then, for $Q = 1/\epsilon q$, there exist coprime integers $a'$, $q'$ such that
  \[\left|\alpha - \frac{a'}{q'}\right|\leq \frac{1}{q' Q}\;\;\;\;\;\;
  \text{and}\;\;\;\;\;\;\frac{Q}{2} < q'\leq Q.\]
\end{lemma}
\begin{proof}
  By the definition of $\epsilon$ and $Q$, we have $|\alpha - a/q|=\epsilon=1/q Q$.
  Since $\epsilon\leq 1/q^2$, we see that $q\leq Q$. 
Dirichlet's approximation theorem (Lem.~\ref{lem:dirithm}) assures us
that there exist coprime integers $a_1$, $1\leq q_1\leq Q$ such that
$|\alpha - a_1/q_1|<1/q_1 Q$. Then $a/q \ne a_1/q_1$, and so
\[\left|\frac{a}{q} - \frac{a_1}{q_1}\right|\geq \frac{1}{q q_1}.\]

At the same time, 
\[\left|\frac{a}{q} - \frac{a_1}{q_1}\right|\leq
\left|\alpha - \frac{a}{q}\right| + \left|\alpha - \frac{a_1}{q_1}\right|<
\frac{1}{q Q} + \frac{1}{q_1 Q}.\]
Hence $1/q Q + 1/q_1 Q > 1/q q_1$, and
so $q + q_1 > Q$.
If $q_1> Q/2$, let $a'/q' = a_1/q_1$. If $q_1\leq Q/2$, then $q>Q/2$,
and we may let $a'/q' = a/q$.
\end{proof}


The idea of using different
approximations to the same $\alpha$ is, of course, not new, even
within the context of the circle method: see,
e.g., Vaughan, op. cit., \S 2.8, Ex. 2. Lemma \ref{lem:hardio} can be
seen as a convenient formulation of an existing general idea.

On a different but related note:
we will not use continued fractions, and thus need not review
the basic nomenclature of the area; however,
the following remark may be useful for some readers.
The approximations $a/q$, $a'/q'$ are not necessarily ``successive
approximants''; we do not want to assume
that the approximation $a/q$ we are given arises from a continued fraction.
At the same time, it follows from \cite[Thm.~13]{zbMATH03191380}.
that, if $a/q$ is in fact a continued-fraction approximant, then
either the next approximant is a valid value for $a'/q'$ or $a/q$ itself
is a valid value for $a'/q'$.

