Number of integer solutions to x^2 + y^2 <= n? [simple proof]

1. Dec 18, 2011

1. The problem statement, all variables and given/known data
I am stuck on a step from a simple proof in Gelfand's method of coordinates.
Here is a link to the part I am confused on. Pg. 44-45...
http://books.google.com/books?id=In...ether with an estimate of its error:"&f=false

It starts in the middle of page 44 and ends right below the part I have highlighted on page 45.

2. Relevant equations
pi*r^2 is area of a circle.
2*pi*r is the circumference of a circle.
diagonal of a 1 unit^2 square is √(2) units
distance formula is (x1-x2)^2 + (y1-y2)2 = d^2

3. The attempt at a solution
when it asked to prove that "the figure An lies entirely within the circle Kn'' and contains the circle kn' entirely within itself," I came up with an attempt by making a triangle ABC with A at (0,0), B at (Bx,0) and C at (0,Cy) and saying AB + AC < BC

next, using the distance formula, I changed AB to Bx2, AC to Cy2 , and BC to Bx2 + Cy2... That would mean that Bx2 + Cy2 < Bx2 + Cy2 which is clearly impossible! Does that qualify as a proof?

So since Kn'' has a radius that is √(2) bigger than Kn, then if the upper right vertex of a unit square is within the circumference of Kn, then it must also be within the circumference of Kn''. Because in order for it to extend beyond the circumference of Kn'' while still remaining in the circumference of Kn, then it would have to take up a distance larger than √(2) which is not possible for a 1 unit square. Same goes for Kn' not being completely within An because that would mean that one part of a unit square was inside the circumference of Kn' while the upper right hand corner of the same square was out of Kn... Not possible unless it had a straight line distance within the unit square that was longer than √(2).

OOOkay. Now that we have that part out of the way (hopefully it's right), the part I'm confused on is how they got from all the lead up steps to their final conclusion of:

|N-pi*n| < 2*pi(√(2n) + 1)

... I think they are trying to quantify the difference between the unit squares in An and the actual area of circle Kn. So they set minimum and maximum boundaries (Kn' and Kn'' respectively) that can help out. Kn' tells us the smallest circular boundary where An will stay within and Kn'' gives us the largest circle that will still be completely filled by An.

But i'm stuck on how they got the right side of the above inequality... All help will be appreciated; sorry for the long post!

Last edited: Dec 19, 2011
2. Dec 19, 2011

dodo

Hi, Nick,
I have not read in detail your proof, but if you're already convinced than the figure $A_n$ (made of N squares) is entirely contained inside the larger circle, and entirely contains the smaller circle, then it should be clear to you the inequality in the book (just before your highlighting) that expresses the relationship between the areas of these three figures:$$\pi(\sqrt n - \sqrt 2)^2 < N < \pi(\sqrt n + \sqrt 2)^2$$
Starting from there, expand the squares to obtain$$\pi(n - 2\sqrt {2n} + 2) < N < \pi(n + 2\sqrt {2n} + 2)$$
and now distribute the $\pi$ along the parentheses,$$\pi n - 2\pi\sqrt {2n} + 2\pi < N < \pi n + 2\pi\sqrt {2n} + 2\pi$$
subtract $\pi n$ all through,$$-2\pi\sqrt {2n} + 2\pi < N - \pi n < 2\pi\sqrt {2n} + 2\pi$$
factor out the common $2\pi$,$$-2\pi(\sqrt {2n} - 1) < N - \pi n < 2\pi(\sqrt {2n} + 1)$$
and now, as $\sqrt {2n} + 1$ is a larger positive quantity than $\sqrt {2n} - 1$ whenever $n > 0$, you might have just as well said$$-2\pi(\sqrt {2n} + 1) < N - \pi n < 2\pi(\sqrt {2n} + 1)$$
which is equivalent to$$|N - \pi n| < 2\pi(\sqrt {2n} + 1)$$
So, as you see, it's just some algebra, an almost mechanical "operations on symbols", that take you from one inequality to the other.

Hope this helps!

3. Dec 19, 2011

Oh wow thanks Dodo!

But I got stuck on this part of your response...

How were you able to change $$-2\pi(\sqrt {2n} - 1)$$ to $$-2\pi(\sqrt {2n} + 1)$$ ?

Thanks again

4. Dec 19, 2011

Wizlem

$$-2\pi\sqrt {2n} - 2\pi < -2\pi\sqrt {2n} + 2\pi$$

and so

$$-2\pi(\sqrt {2n} + 1) < -2\pi(\sqrt {2n} - 1)$$

and you still know $$-2\pi(\sqrt {2n} + 1) < N - \pi n$$

5. Dec 19, 2011

dodo

Hi, Nick,
Wizlem gave you the details, above. The general idea is that, for example, if you know that a number is between -5 and 6, you can also say that it is between -6 and 6... because the latter interval is larger and includes the former. Then, having chosen a symmetric interval, we can now say that our number is no greater than 6 in absolute value. The principle in your case is the same.