Gauss's Circle Problem [1] is to find the number of lattice points inside the boundary of a circle with a given radius and center at the origin. I'm interested in the "reversed" version of this problem. Given that I know the number of lattice points, what is the radius of the circle?
1
- 3$\begingroup$ What is the exact statement of the problem you want to solve. How is it different than Gauss' problem? $\endgroup$Boris Bukh– Boris Bukh2013-03-31 02:27:10 +00:00Commented Mar 31, 2013 at 2:27
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
The number of nodes for radius $r$ is $N_r \approx \pi r^2$ so you can invert to $r_N\approx\sqrt{\frac{N}{\pi}}$. If you wanted to derive the squared distance $r^2$ from $N$, you would have trouble but the square roots are bunched together so maybe that is accurate enough. This does leave some amount of uncertainty:
For $r$ from $\sqrt{1098}$ to $\sqrt{1105}-\varepsilon$ (SO $33.136$ to $33.24153$ and even a bit beyond that) we have $N_r=3456$. At $r=\sqrt{1105}=33.24154$ it jumps to $3488$ because there are $32$ points : $[4,33] ,[9,32],[12,31]$ and $[23,24]$ along with all the variations of making one or both negative and/or swapping the order.
So for $N=3456$ we have $\sqrt{\frac{N}{\pi}}=33.167=\sqrt{1100}$, a bit low perhaps. For $N=3488$ we have $\sqrt{\frac{N}{\pi}}=33.3206 =\sqrt{1110.26}$ This is high because $N$ jumps from $3488$ to $3496$ at $r=\sqrt{1108}$ and then jumps again to $3504$ at $r=\sqrt{1109}$
If you use known precise error bounds for the usual problem you could get error bounds for this dual problem but you can't avoid the uncertainty demonstrated above using a uniform formula.
