¿Con qué frecuencia el símbolo de Jacobi incorrectamente identificar residuos cuadráticos?

Question

Esto parece tan evidente que alguien tiene que haber investigado antes, pero no pude subir nada sustantivo después de un par de búsquedas en Google.

Deje $n$ ser impar el número natural. Es un hecho bien conocido que el símbolo de Jacobi $\left(\frac{a}{n}\right)=-1$ implica $a$ no es un QR modulo $n$, pero que $\left(\frac{a}{n}\right)=1$ no implica $a$ es un QR modulo $n$. Estoy interesado en todo lo "natural" preguntas acerca de la discrepancia $$s_n=\frac{\#\{a\in(\mathbb{Z}/n\mathbb{Z})^\times\mid\left(\frac{a}{n}\right)=1\}-\#\{a\in(\mathbb{Z}/n\mathbb{Z})^\times\mid a\text{ is a QR}\}}{\phi(n)}.$$ Por ejemplo, puede $s_n$ ser arbitrariamente cerca de 1? Si no, ¿qué es $\sup(s_n)$? Dado $r\in\mathbb{Q}\cap[0,1)$, hay siempre un $n$ tal que $r=s_n$? Dado $r\in\mathbb{Q}\cap[0,1)$, ¿cuál es la densidad asintótica de $\{n\in\mathbb{N}\mid s_n=r\}$? Hay $r$ de manera tal que este asintótica densidad es positiva?

Aquí es un gráfico que me produce de $s_n$ por extraño $1\leq n\leq 5000$:

Los valores que se produjeron fueron: $0, \frac{1}{4}, \frac{3}{8}, \frac{7}{16}, \frac{1}{2}, \frac{3}{4}$, lo que sin duda parece a punto de no sólo ser un par de posibles valores de $s_n$; sin embargo, yo no marque ninguna de las $n\geq 5000$, de los cuales hay un número considerable...

Answer 1

Para cualquier entero impar $n$, vamos a $k$ ser el número de los distintos impar de factores primos de a $n$, y escribir $ n = \Pi_{i=1}^k p_i^{\alpha_i}$. Si $a$ es coprime con $n$, $a$ es un cuadrado mod $n$ si y sólo si $a$ es un cuadrado mod $p_i^{\alpha_i}$ para todo i (por el Teorema del Resto Chino), y esto es cierto si y sólo si $a$ es un cuadrado mod $p_i$ para todo i (por Hensel del lema).

Si tienes que elegir un número $a$ $(\mathbb{Z}/n\mathbb{Z})^\times$ al azar, se puede conseguir que la $a$ es un cuadrado mod $p_i$ con una probabilidad de $\frac{1}{2}$, por lo que por el CRT, $a$ es un cuadrado mod de todos ellos (y por lo tanto mod n) con una probabilidad de $\frac{1}{2^k}$ (lo que pasa módulo de un número primo es independiente de lo que sucede en el resto de los números primos).

Mientras tanto, $\left(\frac a n\right) = \Pi_{i=1}^k \left(\frac a {p_i}\right)^{\alpha_i}$, así que si $n$ es un cuadrado, $\left(\frac a n\right) = 1$, de lo contrario $\left(\frac a n\right) = 1$ con una probabilidad de $\frac{1}{2}$.

Por lo tanto $s_n = 1 - \frac 1 {2^k}$ si n es un cuadrado, y $s_n = \frac 1 2 - \frac 1 {2^k}$ lo contrario.

Creo que esto implica que el asintótica densidades de $\{n \in \mathbb{N}, s_n = r\}$ siempre $0$, mientras que las densidades de $\{n \in \mathbb{N}, |s_n - \frac 1 2| < \epsilon \}$ $1$ cualquier $\epsilon > 0$.