9
$\begingroup$

This seems so obvious that someone must have investigated it before, but I couldn't turn up anything substantive after a few Google searches.

Let $n$ be an odd natural number. It is a well-known fact that the Jacobi symbol $\left(\frac{a}{n}\right)=-1$ implies $a$ is not a QR modulo $n$, but that $\left(\frac{a}{n}\right)=1$ does not imply $a$ is a QR modulo $n$. I'm interested in all of the "natural questions" about the discrepancy $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)}.$ For example, can $s_n$ get arbitrarily close to 1? If not, what is $\sup(s_n)$? Given $r\in\mathbb{Q}\cap[0,1)$, is there always an $n$ such that $r=s_n$? Given $r\in\mathbb{Q}\cap[0,1)$, what is the asymptotic density of $\{n\in\mathbb{N}\mid s_n=r\}$? Are there $r$ such that this asymptotic density is positive?

Here is a graph I produced of $s_n$ for odd $1\leq n\leq 5000$:

enter image description here

The values that occurred were: $0, \frac{1}{4}, \frac{3}{8}, \frac{7}{16}, \frac{1}{2}, \frac{3}{4}$, which would certainly seem to point to there only being a few possible values of $s_n$; however, I didn't check any of the $n\geq 5000$, of which there are a substantial number...

1 Answers 1

3

For any odd integer $n$, let $k$ be the number of distinct odd prime factors of $n$, and write $ n = \Pi_{i=1}^k p_i^{\alpha_i}$. If $a$ is coprime with $n$, then $a$ is a square mod $n$ if and only if $a$ is a square mod $p_i^{\alpha_i}$ for all i (by the Chinese Remainder Theorem), and this is true if and only if $a$ is a square mod $p_i$ for all i (by Hensel's lemma).

If you pick a number $a$ in $(\mathbb{Z}/n\mathbb{Z})^\times$ at random, you get that $a$ is a square mod $p_i$ with probability $\frac{1}{2}$, so by the CRT, $a$ is a square mod all of them (and thus mod n) with probability $\frac{1}{2^k}$ (what happens modulo a prime number is independant from what happens at the rest of the primes).

Meanwhile, $\left(\frac a n\right) = \Pi_{i=1}^k \left(\frac a {p_i}\right)^{\alpha_i}$, so if $n$ is a square, $\left(\frac a n\right) = 1$, otherwise $\left(\frac a n\right) = 1$ with probability $\frac{1}{2}$.

Thus $s_n = 1 - \frac 1 {2^k}$ if n is a square, and $s_n = \frac 1 2 - \frac 1 {2^k}$ otherwise.

I think this implies that the asymptotic densities of $\{n \in \mathbb{N}, s_n = r\}$ is always $0$, while the densities of $\{n \in \mathbb{N}, |s_n - \frac 1 2| < \epsilon \}$ is $1$ for any $\epsilon > 0$.

  • 0
    An excellent, comprehensive answer. Thanks!2011-04-18