# The number of grid points near a circle question

I've just read The number of grid points near a circle.

I want to comment but I don't have the reputation so I have to post this as a question.

How do you prove that for each $x$ value less than $r\sqrt2/2$ there is a unique $y$ value and for each $y$ value less than $r\sqrt2/2$ there is a unique $x$ value?

My idea is that you could use the fact that the circle's gradient decreases from $0$ to $-1$ as $x$ goes from $0$ to $r\sqrt2/2$ and this implies that the line will not drop below one $y$ value for each $x$ value passed. However I can't think of how this can be formalized as a proof.

for each $x$ value less than $r\sqrt2/2$ there is a unique $y$ value

At a given position $0\le x\le\frac{r}{\sqrt 2}$, the point $(x,y)$ with

$$y = \left\lfloor\sqrt{r^2-x^2}\right\rfloor$$

is within the circle, and the point $(x, y+1)$ is outside. So the point must be counted.

Now about the uniqueness. Suppose there were a different point $(x,y')$ which should be counted as well. Since that point must lie inside the circle, it must satisfy $0\le y'<y$. You can now consider points around it. $(x,y'+1)$ will be inside since $y'+1\le y$ and $(x,y)$ is inside. $(x-1, y')$ must be inside since $(x,y')$ is inside and the circle and we are in the first quadrant. Likewise for $(x,y'-1)$. Both arguments will need discussion of a special case for $x=0$ resp. $y'=0$, but I'll leave that as an excercise for now.

So $(x+1,y')$ would be the most likely candidate for a point outside the circle. So let's see whether it can be outside the circle.

\begin{multline*} (x+1)^2+y'^2 \le (x+1)^2+(y-1)^2 = x^2+y^2 + 2x-2y+2 \\\le r^2+2x-2y+2 \le r^2+2(y-1)-2y+2 = r^2 \end{multline*}

There are three inequalities in there. The first is because $y'<y$, the second because $x^2+y^2\le r^2$ since $(x,y)$ is inside, and the third because $x<y$ since you are in the upper half of the first quadrant. The case of $x=y$ needs special treatment, but then $(x,y')$ would satisfy $x>y'$ and therefore already belong to the right half of the quadrant. Taken together, you have shown that $(x+1,y')$ cannot be outside the circle either, so $(x,y')$ will not be counted, so $(x,y)$ is unique for given $x$.

and for each $y$ value less than $r\sqrt2/2$ there is a unique $x$ value?

This is simply the same argument above, but with $x$ and $y$ changing their roles. So if you have one, you have both.