Let $n(r)$ be the maximum possible number of points with integer coordinates on a circle with radius $r$ in Cartesian plane. Prove that $n(r) < 6\sqrt[3]{3 \pi r^2}.$
Problem
Source: Iran Third Round MO 1998, Exam 2, P3
Tags: analytic geometry, geometry unsolved, geometry
02.06.2016 14:29
Sorry to revive,any idea to this?
02.06.2016 19:12
Let's prove the slightly better bound $n(r) < 2\pi r^{\frac{2}{3}}$ whenever $n(r) > 1$ --- $n(r) = 1$ could happen for arbitrarily small $r$ so we must exclude that. Since $n(r) > 1$ and any two lattice points have distance at least $1$, we have $r \geq \frac{1}{2}$. Thus there is nothing to prove if $n(r) \leq 3 < 2\pi \cdot (\frac{1}{2})^{\frac{2}{3}}$. Suppose $n(r) \geq 4$ and label these $n$ points as $A_1, A_2, \dots, A_n$ clockwise. There must exist an index $j$ such that the angle $A_{j-1}OA_{j+1} \leq \frac{4\pi}{n}$. It follows that the triangle $A_{j-1}A_jA_{j+1}$ has area at most $\frac{1}{2} \cdot (2r\sin(\pi/n))^2 \cdot \sin(2\pi/n) \leq 4\pi^3 \frac{r^2}{n^3}$. But a lattice triangle has area at least $\frac{1}{2}$, hence the result. A result of Bombieri and Pila shows that the exponent $\frac{2}{3}$ can be lowered to $\frac{1}{2} + \epsilon$, not only for a circle but for any smooth curve. Since the extreme example in that general case is a parabola, I suspect a better exponent can be obtained for circles. Perhaps even $r^{\epsilon}$ (which is true when the center has integer coordinates)?