1

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.

ray
  • 1,507

1 Answers1

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.

André Nicolas
  • 507,029
  • 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 06 '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 06 '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 06 '12 at 20:56