Estimar la cardinalidad del conjunto

Question

Demuestra que: $$\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})$$

Escuché algo acerca de que el número de puntos de red bajo la gráfica de una función es asintóticamente igual al área bajo la gráfica, pero no lo entiendo. Intenté estimar la cardinalidad de este conjunto mediante operaciones simples para mí que son:

para un $a$ dado, cada $b$ está bien si $b^2\le n-a^2$, entonces para un $a$ dado tenemos $\left\lfloor\sqrt{n-a^2}\right\rfloor +1$ puntos de red, entonces la cardinalidad es igual a: $\displaystyle\sum_{a=0}^{\lfloor\sqrt{n}\rfloor}\left( \left\lfloor\sqrt{n-a^2}\right\rfloor +1 \right)$, pero no sé cómo obtener el resultado $\frac{\pi}{4} n + O(\sqrt{n})$ a partir de esto. Intenté usar integrales para estimar esta suma, pero no ocurrió nada útil.

Answer 1

Esquema: Supondré (a regañadientes) que por $\mathbb{N}$ te refieres a los enteros positivos. Asocia con cada uno de los puntos de la red que estás contando el cuadrado de $1\times 1$ que tiene ese punto de la red como su esquina superior derecha. (Yo usaría la esquina inferior izquierda si incluyeras el $0$ en $\mathbb{N}$. Pero realmente no importa, $O(\sqrt{n})$ cubre muchos pecados).

La suma de las áreas de los cuadrados es exactamente el número de puntos de la red.

Sea $U$ la unión de los cuadrados. Entonces $U$ está contenido en el cuarto de círculo con radio $\sqrt{n}+2$, y contiene el cuarto de círculo con radio $\sqrt{n}-2. (Podemos salirnos con algo un poco más barato que $2$).

La diferencia entre las áreas de estos cuartos de círculo es $O(\sqrt{n})$. Así que el área de $U$ difiere de $\pi n/4$ por $O(\sqrt{n})

.

Observación: Tu procedimiento también funcionará, si lo combinas con la interpretación geométrica descrita anteriormente.