Take a sheet of grid paper and draw a straight line in any direction from the origin. What is the closest non-zero grid point $\boldsymbol{p}\in\mathbb{Z}^2$ within a distance $\epsilon>0$ of the line?


I have been unable to construct an example where the distance is large for any $\epsilon$. I would like to prove the following:


$\forall \epsilon>0 ~~ 
\exists R>0 ~~
\forall \boldsymbol{v} \in \mathbb{R}^2 ~~ 
\exists\boldsymbol{q}\in\mathbb{Z}^2, \|\boldsymbol{q}\| < R$ such that:


$\frac{|p\_x v\_y - p\_y v\_x|}{\|\boldsymbol{v}\|}<\epsilon$


where the LHS is the point-line distance.



Lattice points close to a line
The statement that you want to prove follows from Dirichlet's Theorem, which says that for any real number $\alpha$ and for any positive integer $Q$, there is a fraction $a/q$ with $|q|\le Q$ such that
$$|\alpha-a/q|\le 1/q(Q+1).$$
Here $\alpha$ is the slope of your line and $Q$ is playing the role of $R$, with $1/(Q+1)$ playing the role of $\epsilon$. Of course in your problem the actual numerical value of $R$ as a function of $\epsilon$ depends, up to a constant, on what norms you are using. Also technically, to make the connection clearer, you should choose $\alpha$ to be the slope of the line or its reciprocal, whichever is smaller.


For a paticular choice of $\mathbf{v}$ the fastest way to actually find the best integer vectors, as Igor pointed out, is by using the continued fraction algorithm. If you understand the connection to Dirichlet's Theorem then it should be clear how to do this.


