Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
He says that in the first sentence of the question: so yes he does. –  Niel de Beaudrap Sep 30 '11 at 15:10
add comment

2 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.