1
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    @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.2012-09-06