|
2
|
It is well known that the upper bound on the number of quadratic residues mod n is approximately n/2 and it reaches this bound for n prime. Is there any similar lower bound on the number of quadratic residues mod n? Some numerical experiments indicate that it would be somewhere at n^0.65 for highly composite n with many small factors, but can you point me at any more rigorous treatment of the subject? |
||
|
|
|
5
|
Edit: First version of this answer had a silly mistake (forgot to multiply by $n$ the first estimate). Argument is still the same but the final result changes. If you take $n$ to be the product of the first $r$ odd primes, then the number of quadratic residues modulo $n$ is bounded below by ${(1/2)}^rn$, by the Chinese remainder thm. On the other hand, $n$ is about $(1/2)e^{r\log r}$ by the prime number theorem, so you get a lower bound of $n^{1-c/\log \log n}$ for the number of quadratic residues. So you have a lower bound of the form $n^{1-\epsilon}$ for any $\epsilon>0$ if $n$ is large. I think the numbers I constructed will be minimal so you'll get your lower bound. What did the drowning analytic number theorist say? |
|||
|
