# Hardness of computing circles with max number of lattice points

You're given an $n\times n$ lattice $\mathcal{L}$, and you're asked to compute the maximum number of points in $\mathcal{L}$ that can belong to the same circle (the circle has to be enclosed by the outer sides of $\mathcal{L}$ and its center does not need to be in $\mathcal{L}$). How hard is this problem? Is it harder than factoring $n$? Are there decent bounds or estimates on the max number defined above?

It's probablyly much easier than factoring $n$, because you're looking for smooth numbers smaller than $n$ rather than for difficult factorizations; a smooth number is one that has many small factors, and these are the distances which will give you the most points on the lattice. If the center has to be at $(0,0)$, then you calculate how many lattice points are at distance $5^{a/2}13^{b/2}17^{c/2}29^{d/2}37^{e/2} \ldots$ using the formula for the number of ways of expressing a number as the sum of two squares. You can do the same thing for the circle centered at $(0,\frac{1}{2})$ or $(\frac{1}{2},\frac{1}{2})$. You can then do an optimization to find the largest value where this distance is less than $n/2$. I expect that this will be possible in polynomial time using dynamic programming.
I cannot imagine that the largest value would not correspond to the center having coordinates other than $0$ or $\frac{1}{2}$, but this should be proved.
• I don't know how one would prove this; I don't even know if it's true. It is true that the largest exponent on a prime required is order $\log \log n$, which means that exhaustive search can find the optimum answer in pseudopolynomial time $\log^{(\log\log n)} n$, which is still a lot better than factoring. I thought this could be sped up to polynomial time by dynamic programming, but I'm not sure that's right. Nov 29 '11 at 3:00
• Addendum to previous note: a clever exhaustive search algorithm can find the optimum answer in time $(\log n)^{O(\log\log\log n)}$. Nov 30 '11 at 1:19