# Find center of circle of radius $r$ that overlaps exactly $\lfloor \pi r^2 \rceil$ points of the integer grid

Can a circle of a given radius $r$ always be placed (in $\mathbb{R}^2$) such that the number of points with integer coordinates inside the circle is equal to the nearest integer of the circle's area?

In other words, if we imagine a square grid with the centers of the grid squares at integer points (and thus corners at $(n+0.5,m+0.5)$ for $n,m \in \mathbb{N}$), we want to place the circle at a point where if we approximate it by squares whose center it includes, we get an approximation that with respect to area is as close as possible.

I found a few older papers dealing with the number of integer points on or inside a circle with center at the origin, but not quite what I am looking for. Seeing no good theoretical approach, I wrote a small brute-force program that tries to place circles as required by sampling centers $(x,y)$ with $0 \leq x \leq 0.5$ and $x \leq y \leq 0.5$ (sufficient due to invariance to translation by an integer vector and reflection through a diagonal), and it seems indeed that even for small $r$ (e.g. $r=\sqrt{2/\pi}$) not only what I describe above is possible, but also having the circle overlap exactly $\lfloor \pi r^2 \rceil-1$ or $\lfloor \pi r^2 \rceil+1$ integer points. Yet the size of the regions for the centers of appropriately placed circles get smaller and smaller as $r$ increases, and I cannot see a general patter of how to arrive at valid center coordinates by any other means.

-
What do you intend with $\lfloor x\rceil$? Do you mean the closest integer (something like $\lfloor x+\frac{1}{2}\rfloor$)? – robjohn Sep 30 '11 at 15:06
He says that in the first sentence of the question: so yes he does. – Niel de Beaudrap Sep 30 '11 at 15:10

It is always possible. Here is a nonconstructive proof.

Fix $r$. For any point $z$ in $\mathbb{R}^2$, let $f(z)$ be the number of lattice points inside a disc of radius $r$ centered at $z$. (Make some convention for how to deal with points on the boundary; it won't matter.) Then $$\int_{z \in [0,1]^2} f(z) \ d\mbox{Area} = \pi r^2$$

So there is some $z_{-}$ for which $f(z_{-}) < \pi r^2$ and some $z_{+}$ for which $f(z_{+})> \pi r^2$. Choose a path $\gamma$ from $z_{-}$ to $z_{+}$ which does not pass through any point which is at distance $r$ from two different lattice points. Since we only have to avoid finitely many points within $[0,1]^2$ to do this, it is always possible. Along that path, $f$ takes integer values and only changes by $\pm 1$. So it must be $\lfloor \pi r^2 \rceil$ at some point.

-

Define the integer valued functions $$f_{r}(x)=\left\{\begin{array}{}1&\text{if }|x|\le r\\0&\text{if }|x|>r\end{array}\right.$$ and $$g_r(x)=\sum_{k\in\mathbb{Z}^2}f_r(x{-}k)$$ The mean of $g_r$ over each lattice square is $\pi r^2$. To see this, first note that $g_r$ is $\mathbb{Z}^2$-periodic. Consider the square $[0,n]\times[0,n]$. The integral of $g_r$ over that square is greater than $\pi r^2(n-2\lceil r\rceil+1)^2$ (adding the areas of the circles that fit inside the square) and less than $\pi r^2(n+2\lfloor r\rfloor+1)^2$ (adding the areas of the circles that touch the square). The area of the square is $n^2$. The average of $g_r$ over one unit square is between $\pi r^2(n-2\lceil r\rceil+1)^2/n^2$ and $\pi r^2(n+2\lfloor r\rfloor+1)^2/n^2$ for any $n$. Thus, the mean of $g_r$ over each lattice square is $\pi r^2$.

Thus, $g_r$ is an integer valued, $\mathbb{Z}^2$-periodic function whose mean is $\pi r^2$. Since the boundary of each integer valued region is composed of circular arcs with radius $r$, we can always find a neighboring region whose value is $1$ higher (if the boundary arc is concave) or $1$ lower (if the boundary arc is convex). Thus, there must be regions where $g_r$ is $\lfloor\pi r^2\rfloor$ and regions where it is $\lceil\pi r^2\rceil$.

$g_r(x)$ is also the number of lattice points in a circle of radius $r$ centered at $x$. Therefore, the question is answered in the affirmative.

Addition: This same proof works in $\mathbb{R}^n$ when $\pi r^2$ is replaced by $\int_{\mathbb{R}^n}f_r(x)\;\mathrm{d}x$.

-