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?


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?

  • $\begingroup$ Thank you, this makes sense. The numbers you construct (products of first odd primes) may not be minimal - because if we admit powers of primes in the factorization of n then we'd get relatively fewer residues, even better if we allow n even - but these improvements don't seem to help the asymptotic result. n ^ (1 - eps) is quite disappointing though. $\endgroup$ – Marek Rocki Oct 24 '10 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.