# Bounds for the size of a circle with a fixed number of integer points

I know that there are infinitely many rational points on the (unit) circle. I am interested in the following question:

How large has the radius of a circle to be, such that there are at least $n$ integer (lattice) points on it?

Actually, I am not interested in the precise number, but in some reasonable good upper bound $f(n)$. Something like, there is a circle of radius $\leq f(n)$ that has least $n$ integer points.

-
The radius must be at least about $\sqrt{\frac{n}{\pi}}$. Also see: en.wikipedia.org/wiki/Gauss_circle_problem –  Dan Brumleve Oct 31 '12 at 10:13
@DanBrumleve: Sorry, but my question was ambiguous. I meant integer points on the circle and not inside the circle. I made the question more precise. –  A.Schulz Oct 31 '12 at 10:26
Here is a lousy bound. There are $4(e+1)$ representations of $5^e$ as a sum of two squares of integers. –  André Nicolas Oct 31 '12 at 11:10

Edit: In the following I suppose that the center of the circle is $(0,0)$ and this extent easily to the case where the center is a lattice point.

If the radius of a circle is $r$ and we have $n$ lattice points on it (of cource $4|n$) then $r^2 \in \mathbb{N}$ and $r^2$ can be written as sum of two squares in $n$ different ways (assuming of course that $(a,b) \neq (-a,b)$ and $(a,b) \neq (b,a)$ for $a \neq b$).

So if you are asking if there is a function $f$ s.t. if $k \leq f(n)$ then $k$ can be written as sum of two squares in at least $n$ different ways then according to this paper the answer is no.

In theorem 4.3 is shown that for a prime $p$ there at most $8$ different ways to write $p$ as a sum of two squares.

However, there is a function $g$ s.t. for all $n \in \mathbb{N}, \ g(n)$ can be written as sum of two squares in $n$ different ways, so if this is what you are asking the answer is yes. This is a consequence of Theorem 4.4.

Theorem 4.4. says that if the prime numbers of the form $1 \pmod4$ in $m$ appear with exponents $a_1,a_2,\ldots , a_s$ and the prime numbers of the form $3 \pmod4$ in $m$ appear with even exponents then $m$ can be written as sum of two squares in $4(a_1+1)(a_2+1)\ldots(a_s+1)$ different ways.

Lets say that you want to find a circle with $4k$ lattice points. Then you can take the radius to be $5^{\frac{k-1}{2}}$.

e.g to find $8$ lattice points take the radius to be $\sqrt{5}$. The lattice points are $(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)$.

The best bound (assuming the circle is centered at zero) is the following:

Denote the primes of the form $1 \pmod 4$ as $p_1<p_2<\ldots$. Lets say that you want to find the smallest $m$ s.t. the circle with radius $m$ has $4n$ lattice points. Factor $n$ as $n=4a_1a_2\ldots a_s$ where $a_i$ are primes with $a_1\leq a_2\leq a_3 \leq \ldots \leq a_s$. Then the smallest $m$ is given by $m^2=p_1^{a_s-1}p_2^{a_{s-1}-1}p_3^{a_{s-2}-1}\ldots p_s^{a_1-1}$. This can be deduced from Theorem 4.4, the fact that for $a<b, \ r_1,r_2 \in \mathbb{N}, \ \text{ with } a^2>b \text{ and } r_1\geq 2 \Rightarrow a^{r_1r_2-1}>a^{r_1-1}b^{r_2-1}$ and the fact that $p_{i+1}<p_i^2, \ \forall i \in \mathbb{N}.$

For example the smallest radius $m$ witch give $48$ lattice points is $m=5\cdot \sqrt{13 \cdot 17}$.

-
I think you'll find that last circle has radius $\sqrt5$. But in fact you can get it down to $\sqrt5/\sqrt2$ with center $(1/2,1/2)$. No one said the center had to be a lattice point. –  Gerry Myerson Oct 31 '12 at 12:01
Correct, thanks. I will edit. –  P.. Oct 31 '12 at 12:06
@Pambos: Interesting! This is the bound that was mentioned by André Nicolas at the question's comment. Thanks for your longer answer. I am curious if one can find a better bound or if this is the best you can get. –  A.Schulz Oct 31 '12 at 13:23
In the same direction of @André Nicolas's bound, we can take the radius as the square root of the product of the first $m$ primes $\equiv 1\pmod{4}$, in order to have $4\cdot 2^m$ integer points on a circle having a radius that grows like $m^m$. –  Jack D'Aurizio Oct 31 '12 at 14:15