Prove that a circle exists for which at least $n \in \mathbb{N}$ points have integer coordinates

This question is based on the fourth question in the 2003 edition of the Flemish Mathematics Olympiad.

Consider a grid of points with integer coordinates. If one chooses the number $R$ appropriately, the circle with center $(0, 0)$ and radius $R$ crosses a number of grid points. A circle with radius $1$ crosses 4 grid points, a circle with radius $2\sqrt{2}$ crosses 4 grid points and a circle with radius 5 crosses 12 grid points. Prove that for any $n \in \mathbb{N}$, a number $R$ exists for which the circle with center $(0, 0)$ and radius $R$ crosses at least $n$ grid points.

I have tried to solve this question by induction, considering a given point $(i, j)$, $i \gt j$, on the circle with radius $R$ and attempting to extract multiple points from this on a larger circle. In this case, the coordinates $(i+j,i-j)$ and $(i-j, i+j)$ are both on a circle with radius $\sqrt{2}R$. However, since $(j, i)$ is also a point on the circle, the number of crossed grid points remains the same. What is a correct way to prove the above statement?

• – Will Jagy Jun 17 '17 at 0:25
• Related video: Pi hiding in prime regularities – peterwhy Jun 17 '17 at 0:27
• If $a_1 + b_1 i, \ldots, a_n + b_n i$ are distinct irreducible Gaussian integers with $a_k, b_k > 0$ (and $a_k + b_k i \ne 1 + i$), then $(a_1 \pm b_1 i) (a_2 \pm b_2 i) \cdots (a_n \pm b_n i)$ will generate at least $2^n$ different points. – Daniel Schepler Jun 17 '17 at 0:41
• @Daniel Schepler I see what you are getting at: if we have $n$ such points on a certain circle, there are $\frac{2^n}{4}$ on this larger circle. Could you provide an elaborate answer below? – jvdhooft Jul 1 '17 at 8:43
• @jvdhooft Actually, you don't need all the points $a_k + b_k i$ to be on the same circle, since the modulus of $(a_1 \pm b_1 i) (a_2 \pm b_2 i) \cdots (a_n \pm b_n i)$ is independent of the choice of $\pm$. – Daniel Schepler Jul 1 '17 at 17:22

Let $a_1 + b_1 i, \ldots, a_n + b_n i$ be distinct irreducibles of the Gaussian integers $\mathbb{Z}[i]$, with $a_k > b_k > 0$ for each $k$. Then $a_1 + b_1 i, a_1 - b_1 i, \ldots, a_n + b_n i, a_n - b_n i$ are also distinct irreducibles such that no pair has ratio equal to a unit of $\mathbb{Z}[i]$. Therefore, since $\mathbb{Z}[i]$ is a UFD, the $4 \cdot 2^n$ numbers $(\pm 1, \pm i) (a_1 \pm b_1 i) \cdots (a_n \pm b_n i)$ are distinct. Each of them has $|z|^2 = (a_1^2 + b_1^2) \cdots (a_n^2 + b_n^2)$; therefore, the circle with radius $R = \sqrt{(a_1^2 + b_1^2) \cdots (a_n^2 + b_n^2)}$ has at least $4 \cdot 2^n$ integer points.

(This could easily be modified; for example, by taking $(\pm 1, \pm i) \cdot (2+i)^k (2-i)^{n-k}$, you get that the circle with radius $R = 5^{n/2}$ has at least $4(n+1)$ integer points.)

Following arguments are not mathematically rigorous, but I think it will explain the main idea.

The solution hinges on the fact that there are infinitely many values of $\phi \in [0, 2\pi)$ such that $\cos{\phi}$ and $\sin{\phi}$ are both rational. (This in turn depends on the fact that there are infinitely many Primitive Pythagorean Triples. A Pythagorean Triple $(a,b,c)$ is primitive if all three numbers are pairwise coprime).

For every Pythagorean Triple $(a,b,c)$, the point $(\frac{a}{c}, \frac{b}{c})$ lies on the unit circle and both co-ordinates are rational.

Given any $n \in \mathbb{N}$, choose at least $n$ primitive Pythagorean Triples $(a_1, b_1, c_1), (a_2, b_2, c_2), \dots, (a_n, b_n, c_n)$ such that the hypotenuse lengths $c_1, c_2, \dots c_n$ are all pairwise coprime. (You will need to prove that such a choice is possible). Then let $R = lcm(c_1, c_2, \dots c_n)$. This circle will contain at least $n$ grid points.

(In fact this circle will contain at least $4n$ grid points, so this is a huge overestimate. But the question asks for at least $n$ grid points).

Edit 1 It's not necessary to choose $n$ primitive triples such that $gcd(c_i,c_j) = 1$. Any $n$ primitive triples will suffice.

• How would one prove that it is possible to choose at least $n$ primitive Pythagorean triples for which $c_1, c_2, \ldots, c_n$ are all pairwise coprime? – jvdhooft Jun 21 '17 at 9:18
• I have to admit that in retrospect, choosing $n$ triples such that $c_1,c_2, \dots c_n$ seems a bit of an overkill. It suffices to choose any $n$ primitive triples. For any two primitive triples $(a_1,b_1,c_1)$ and $(a_2,b_2,c_2)$, the points $(a_1/c_1, b_1/c_1)$ and $(a_2/c_2, b_2/c_2)$ are different. This can be proved easily. – jgsmath Jun 22 '17 at 17:02
• Besides, the way I had in mind for proving that the choice of $n$ triples such that $gcd(c_i, c_j) = 1$ was possible rested on proving that there are infinitely many primes of the form $k^2 + 1$. This seems to be an unproven conjecture. – jgsmath Jun 22 '17 at 17:10