# Upper-bounding the min-distance between a circle and the set of coprime integer pairs

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$.

• Google "primitive circle problem." (Will add an answer later if it's not resolved by then.) Oct 27, 2016 at 21:05
• Thanks for this pointer, it is very related indeed! However, it seems that the primitive circle problem is typically studied in terms of the number $V(r) = \frac{6}{\pi}r^2 + O(r^{1+\epsilon})$ of primitive points inside a circle. However, in my problem I do not need bounds on the $O(r^{1+\epsilon})$ term (the typically studied problem), but lower bounds on increments of this error term.
– jens
Oct 27, 2016 at 21:51
• If you look at $m^2+n^2-r^2$, you're looking at gaps in the sequence of sums of two squares (well, two coprime squares). Oct 27, 2016 at 21:56
• Perhaps you might find the following useful : Adhikari and various coauthors (Chen and Granville to name two) have papers on visibility on points of the plane. The points nearest your ellipse , assuming the ellipse is contained in an n by n box, are visible from fewer than C log n points. There may be enough close points to the ellipse that you can see one from the center using this estimate. Gerhard "Maybe Close Is Good Enough?" Paseman, 2016.10.27. Oct 28, 2016 at 5:07

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 and follow the references there.

• $-3/5$ in the final exponent? Oct 28, 2016 at 16:12
• @GregMartin: No just 3/5 -- as in the prime number theorem. Missing a close bracket though. Oct 28, 2016 at 16:15
• @Lucia: Thanks a lot for your multiple answers. It takes me a while to unravel your answer because I am unfamiliar with number theory. Why do you say your previous version was overkill? Didn't it yield a much better exponent than the $-1/2+\epsilon$ that you have now? I am primarily interested in the best exponent, and to the extent that it is possible, in explicit (constant) factors. For the interest of other readers, may I suggest to restore your previous solution (in addition to the other two approaches)?
– jens
Oct 28, 2016 at 23:46
• It yielded a worse exponent! You want to get the exponent as negative as possible -- the earlier argument had -0.2375 while this has -1/2+epsilon. The exponent here is definitely the best known -- even if you omit the coprimality condition, nothing more is known. Oct 28, 2016 at 23:50
• Ah, of course! Thanks again for your valuable inputs. Now, for my understanding, how can I derive (or find a reference for) the identity which "follows from inclusion-exclusion"? I presume $\phi$ is the totient function, right? Do you think there is a chance of getting an explicit upper bound on $C_2$? And finally, do you reckon that your approach is extensible to ellipses?
– jens
Oct 29, 2016 at 0:10