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.

Prove that: $$\left|\left\{ \langle a,b \rangle\in \mathbb{N}\times\mathbb{N}:a^2+b^2\le n \right\}\right|=\frac{\pi}{4}n+O(\sqrt{n})$$

I heard something about that the number of lattice points under the graph of a function is asymptotically equal to the area under the graph, but I don't understand it. I tried to estimate the cardinality of this set by simple for me operations that is:

for a given $a$, every $b$ is ok iff $b^2\le n-a^2$, so for a given $a$ we have $\left\lfloor\sqrt{n-a^2}\right\rfloor +1$ lattice points, then the cardinality is equal to: $\displaystyle\sum_{a=0}^{\lfloor\sqrt{n}\rfloor}\left( \left\lfloor\sqrt{n-a^2}\right\rfloor +1 \right)$, but I don't know to get the result $\frac{\pi}{4} n + O(\sqrt{n})$ from this. I tried to use integrals to estimate this sum, but nothing useful occurred.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Outline: I will (reluctantly) assume that by $\mathbb{N}$ you mean the positive integers. Associate with each of the lattice points you are counting the $1\times 1$ square that has that lattice point as its upper right-hand corner. (I would use lower left-hand corner if you included $0$ in $\mathbb{N}$. But it doesn't really matter, $O(\sqrt{n})$ covers a lot of sins.)

The sum of the areas of the squares is exactly the number of lattice points.

Let $U$ be the union of the squares. Then $U$ is contained in the quarter-circle with radius $\sqrt{n}+2$, and contains the quarter-circle with radius $\sqrt{n}-2$. (We can get away with something a bit cheaper than $2$.)

The difference between the areas of these quarter-circles is $O(\sqrt{n})$. So the area of $U$ differs from $\pi n/4$ by $O(\sqrt{n})$.

Remark: Your procedure will also work, if you marry it with the geometric interpretation described above.

share|improve this answer
    
This illustrates the general principle that the number of lattice points in a region is approximately equal to its area, with a maximum error proportional to its perimeter. Higher-dimensional versions also exist. –  Erick Wong Sep 6 '12 at 15:58
    
@Andre Nicolas, thank you very much. I think I fully understood your explanation, I like it. But I don't know how my approach can be fixed, are you saying that it can be done? –  ray Sep 6 '12 at 20:43
    
@ray: Divide interval from $0$ to $n$ into $n$ subintervals, and use a version of my $1\times 1$ squares. You can catch the number of squares between an upper Riemann sum and a lower Riemann sum for the integral. –  André Nicolas Sep 6 '12 at 20:56

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.