Estimate on the number of solutions of congruences

Question

Let $F$ be an irreducible, integral polynomial. Is it true that$$|\{\nu:F(\nu)\equiv 0\mbox{ mod } n,\ 0\le\nu<n\}|\ll n^{\epsilon}$$as $n\rightarrow+\infty$? How can one show it?

Answer 1

Yes. Indeed we have the stronger bound $$ S(n) = \#\{\nu:F(\nu)\equiv 0\mbox{ mod } n,\ 0\le\nu<n\} \ll_F (\deg F)^{\omega(n)} $$ where $\omega(n)$ is the number of distinct prime factors of $n$; this implies a bound of the shape $\ll_{F,\varepsilon} n^\varepsilon$ for every $\varepsilon>0$.

By the Chinese remainder theorem, $S(n)$ is a multiplicative function of $n$. If $p$ is prime, then $S(p)$ has at most $\deg F$ roots. Then Hensel's lemma allows us to lift those roots to at most $\deg F$ roots modulo $p^k$ for all $k\ge1$. That gives the bound $S(n) \le (\deg F)^{\omega(n)}$ ...

... except that there are two lies in the above account:

1. $F(x)$ might be identically zero modulo $p$, and then there will be $p$ roots instead of at most $\deg F$;
2. Some of the roots might be singular modulo certain primes and have multiple lifts to roots modulo $p^k$.

Both of these problems, however, affect only finitely many prime powers, and the ultimate effect is to change $\le$ into $\ll_F$ in the argument above.