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?



Numbers with few quadratic residues
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?


