Consider the set of coprime integer pairs $\mathcal{C} \subset \mathbb{Z}^2$ and the circle of radius $r$ centered at the origin. The function
$$f(r) = \min\_{(m,n) \in \mathcal{C}} \bigl| \sqrt{m^2 + n^2} - r \bigr|$$
represents the minimum Euclidean distance between $\mathcal{C}$ and the circle of radius $r$.


I am interested in an explicit upper bound on $f(r)$.
An obvious upper bound is $f(r) \leq \frac{1}{2}$ for $r \geq 1$, since circles of radius at least $1$ will cross the line $(1,\mathbb{Z})$ which consists of consecutive coprime pairs.
But I need way better than this, ideally a bound that tends to zero as $r \to \infty$.


First of all, is it even true that $\limsup\_{r \to \infty} f(r) = 0$?


The classical result on the asymptotic density of coprimes tending to $6/\pi^2$ would indeed suggest this, but the statement seems way too weak to be of any use here. I am also aware of the Jacobsthal function, though bounds thereof do not seem to help either for the question at hand.


**NB:** in my actual research problem I consider centered ellipses rather than circles, which might make the problem even harder. Specifically, I want to find a good upper bound on
$$\min\_{(m,n) \in \mathcal{C}} \left| \begin{bmatrix} m & n \end{bmatrix} \mathbf{A} \begin{bmatrix} m \\ n \end{bmatrix} - C \right|$$
for some $C > 0$ and positive definite $\mathbf{A} \in \mathbb{R}^{2 \times 2}$. This bound should tend to zero as $C \to \infty$.



Upper-bounding the min-distance between a circle and the set of coprime integer pairs
Here's an easy way to show that $f(r)$ goes to zero. Indeed it shows that $f(r) \le C r^{-1/2+\epsilon}$ for some constant $C$ and any $\epsilon > 0$.


We start with the observation that given any number $n$, 
$$ 
\sum\_{\substack{k\le x \\ (k,n) =1}} 1 = \frac{\phi(n)}{n} x + O(2^{\omega(n)}), 
$$ 
which follows from inclusion-exclusion (see Section 3.1 of Montgomery and Vaughan's book *Multiplicative number theory*, for this and other details below). Here $\omega(n)$ is the number of distinct prime factors of $n$. Since $\phi(n)/n$ is never too small (always bounded below by $c/\log \log n$), and $2^{\omega(n)}$ may be bounded by $n^{\epsilon/2}$, it follows that every interval of length $Cn^{\epsilon}$ contains an integer coprime to $n$. One can quantify this better, but this is enough. 


Now choose $n$ to be the largest integer below $r$. Therefore $\lceil r^2\rceil -n^2= N$ is an integer of size $\le 3r$. Now choose $m$ to be the largest integer below $\sqrt{N}$ that is also coprime to $n$. From our observation, we may choose $m$ within $Cn^{\epsilon}$ of $\sqrt{N}$, and so $0\le N-m^2 \le C\_1 \sqrt{N} n^{\epsilon}$.  

Then 
$$ 
0\le r - \sqrt{n^2 +m^2} \le \frac{1}{r} (r^2 -n^2-m^2) 
\le \frac{1}{r} (C\_1 \sqrt{N} n^{\epsilon}) \le C\_2 r^{-1/2 +\epsilon},
$$ 
as claimed. 


My earlier answer produced $p^2+m^2$ close to $r^2$ for a prime $p$, but this is overkill. You can also adapt the argument to ellipses $f(x,y)= ax^2+bxy+cy^2$ with discriminant $D=b^2-4ac <0$. One way to do this is to multiply $f(x,y)$ by $4a$ and complete the square, thus getting $(2ax+by)^2 -Dy^2$. Now look for coprime $(X,Y)$ with $X^2-DY^2$ close to $4ar^2$, and arrange for $Y$ to lie in a suitable progression (given $X$) so that you can recover $y=Y$ and $x =(X-bY)/(2a)$. 


Alternatively, you can use work toward the primitive circle problem. It $r\_0(n)$ denotes the number of primitive representations of $n$ as a sum of two squares then it is known that 
$$ 
\sum\_{n\le x} r\_0(n) = C x +O(x^{1/2} \exp(-C (\log x)^{3/5-\epsilon})),
$$ 
and this is enough to show that $f(r) \to 0$ (you just need to beat $\sqrt{x}$ in the error term). This again is known for ellipses; see for example [Nowak](http://math.mit.edu/classes/18.158/Nowak.pdf) and follow the references there. 


