¿Cómo crece el tamaño del conjunto $A(R) = \{(a,b) \; | \; a,b \in N \times N, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$?

Question

¿Cómo afecta el tamaño del conjunto $$A(R) = \{(a,b) \; | \; a,b \in \mathbb{N} \times \mathbb{N}, \; \gcd(a,b) = 1, \; a^2 + b^2 \leq R^2\}$$ crecer como una función de la $R$?

Yo: claro que $|A(R)| \leq \pi R^2$ (ish). Desde $\mathbb{Z}_R \times \{1\} \subset A(R)$ también podemos decir $A(R) \geq R$ (ish). Creo que podemos escribir una fórmula similar a la $$|A(R)| = \frac{1}{2} \sum_{k \leq R} \phi(\lfloor \sqrt{k^2-R^2} \rfloor),$$ pero estoy bastante seguro de que el de arriba está mal. Incluso si era correcto, no tengo ninguna idea de cómo estimar.

También se me ocurre que si $F(n)$ es el número de maneras de representar el $n=a^2+b^2$$\gcd(a,b) = 1$, luego $$A(R) = \sum_{k \leq R^2} F(k).$$ Si mal no recuerdo $F(n)$ es exactamente conocido. Creo $$F \left(a^2 \prod_{i=1}^m q_i \prod_{i=1}^n p_i \right) = 2^n$$ donde $n/a^2$ es de planta cuadrada gratis, $q_i = 3 \mod 4$$p_i = 1 \mod 4$. Parece que esto podría ser difícil trabajar con ellos.

Answer 1

Si hacemos caso omiso de la coprimality restricción por un momento, nos fijamos en los conjuntos

$$B(R) = \{(a,b) \in\mathbb{N}^2 : a^2 + b^2 \leqslant R^2\}.$$

Es fácil ver que

$$\lvert B(R)\rvert = \frac{\pi}{4} R^2 + O(R).\tag{1}$$

Por otro lado, cada par $(a,b)$ $a^2 + b^2$ únicamente pueden ser escritos como $d\cdot (\alpha,\beta)$$\gcd(\alpha,\beta) = 1$, por lo que tenemos

$$\lvert B(R)\rvert = \sum_{d=1}^R \left\lvert A\biggl( \frac{R}{d}\biggr)\right\rvert.\tag{2}$$

Por generalizada de inversión de Möbius, $(2)$ es equivalente a

$$\lvert A(R)\rvert = \sum_{d=1}^R \mu(d)\left\lvert B\biggl(\frac{R}{d}\biggr)\right\rvert.\tag{3}$$

donde $\mu$ es la función de Möbius. Si $R$ está restringido a ser un número entero, debemos reemplazar la $\frac{R}{d}$$\left\lfloor\frac{R}{d}\right\rfloor$$(2)$$(3)$, y por debajo.

La inserción de $(1)$ a $(3)$, obtenemos

$$\lvert A(R)\rvert = \sum_{d=1}^R \mu(d) \left(\biggl( \frac{R}{d}\biggr)^2 + O\biggl(\frac{R}{d}\biggr)\right),\tag{4}$$

y como $\left\lvert \sum\limits_{d=1}^R\frac{\mu(d)}{d}\right\rvert \leqslant \sum\limits_{d=1}^R\frac{1}{d} = \log R + O(1)$, que se convierte en

$$\lvert A(R)\rvert = \frac{\pi}{4}R^2\sum_{d=1}^R \frac{\mu(d)}{d^2} + O(R\log R),\tag{5}$$

y ya

$$\sum_{d=1}^\infty \frac{\mu(d)}{d^2} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$$

y

$$\left\lvert \sum_{d=R+1}^\infty \frac{\mu(d)}{d^2}\right\rvert \leqslant \sum_{d=R+1}^\infty \frac{1}{d^2} < \frac{1}{R},$$

finalmente

$$\lvert A(R)\rvert = \frac{3}{2\pi}R^2 + O(R\log R).$$

Si restringimos el argumento de $A$ $B$ a ser números enteros, entonces en $(4)$ el dominante plazo es

$$\sum_{d=1}^R \mu(d)\biggl\lfloor\frac{R}{d}\biggr\rfloor^2 = \sum_{d=1}^R\mu(d)\biggl(\frac{R}{d}\biggr)^2 - \sum_{d=1}^R \mu(d)\Biggl(\biggl(\frac{R}{d}\biggr)^2 - \biggl\lfloor \frac{R}{d}\biggr\rfloor^2\Biggr),$$

y ya

$$\biggl(\frac{R}{d}\biggr)^2 - \biggl\lfloor \frac{R}{d}\biggr\rfloor^2 = \underbrace{\Biggl(\frac{R}{d}-\biggl\lfloor\frac{R}{d}\biggr\rfloor\Biggr)}_{< 1}\underbrace{\Biggl(\frac{R}{d}+\biggl\lfloor\frac{R}{d}\biggr\rfloor\Biggr)}_{\leqslant 2\frac{R}{d}} < 2\frac{R}{d}$$

vemos que el comportamiento asintótico no cambia, sólo la constante en el segundo fin de cambios a largo plazo.