3
$\begingroup$

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.

                        enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ see my math.stackexchange.com/questions/2302054/… $\endgroup$ – Will Jagy Jun 17 '17 at 0:25
  • 1
    $\begingroup$ Related video: Pi hiding in prime regularities $\endgroup$ – peterwhy Jun 17 '17 at 0:27
  • 3
    $\begingroup$ 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. $\endgroup$ – Daniel Schepler Jun 17 '17 at 0:41
  • $\begingroup$ @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? $\endgroup$ – jvdhooft Jul 1 '17 at 8:43
  • $\begingroup$ @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$. $\endgroup$ – Daniel Schepler Jul 1 '17 at 17:22
2
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – jvdhooft Jun 21 '17 at 9:18
  • $\begingroup$ 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. $\endgroup$ – jgsmath Jun 22 '17 at 17:02
  • $\begingroup$ 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. $\endgroup$ – jgsmath Jun 22 '17 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.