3
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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?

Improve this answer
$\endgroup$
1
  • $\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
    Commented Oct 24, 2010 at 18:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .