Let $f \in \mathbb{Z}[x]$. Is the number of roots of $\bar{f}$ in $\bar{\mathbb{F}_p}$ bounded above by the number of roots of of $f$ in $\mathbb{C}$?

Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial. Consider $\bar{f} \in \mathbb{F}_p[x].$ Let $\rho_p$ be the number of distinct roots of $\bar{f}$ in $\overline{\mathbb{F}}_p$, the algebraic closure of $\mathbb{F}_p$. Also, let $\rho$ be the number of distinct roots of $f$ in $\mathbb{C}$.

Question 1:

Do you have a reference for showing that $\rho_p \leq \rho$ for all large primes $p$?

If not, then of course, I'd also be happy with an (understandable) argument that shows this. (I'm weak in algebraic number theory.)

Question 2:

Do we only need to assume that $p$ is such that $\bar{f}$ is nonzero in $\mathbb{F}_p$?

My background to the question: I actually have used the first result in counting the maximal subgroups (by their index) of groups of the form $\mathbb{Z}^k \rtimes \mathbb{Z}$ and similar metabelian groups. Now that I'm going back and rereading my work (to convert it into a paper) I've realized that I used this without justification.

• (1) If $r_1,r_2,...,r_{\rho+1}$ are different roots, then the coefficients are a non-zero solution of a homogeneous system that has the Vandermonde determinant of the $r_i$ as matrix. Therefore, all coefficients would be zero. Take into account that $\rho$ is equal to the degree of $f$. This argument doesn't have much to do with anything but that the coefficients are a domain, and well the fundamental theorem of algebra to know that $\rho$ is the degree. – user551819 Apr 25 '18 at 20:01
• The thing that is proper to characteristic $p$ is that $\rho_p$ can be strictly smaller than $\rho$. For example, for $f(x)=x^p-a$ the only root in $\overline{\mathbb{F}}_p$ is $a^{1/p}$, since $f(x)=(x-a^{1/p})^p$. – user551819 Apr 25 '18 at 20:06
• @totoro I do not understand your first comment. Would you mind expanding it into an answer and add more details? – Andrew Kelley Apr 28 '18 at 0:07

Yes, this is more or less immediate from considering the factorization of $f$ in $\mathbb{Z}[x]$. We can factor $f$ as $$f=af_1^{e_1}\dots f_n^{e_n}$$ where $a\in\mathbb{Z}$ and $f_1,\dots,f_n\in\mathbb{Z}[x]$ are distinct irreducible polynomials of positive degree. By Gauss's lemma, the $f_i$ are also irreducible in $\mathbb{Q}[x]$. An irreducible polynomial always has distinct roots in characteristic $0$, and distinct irreducible polynomials over a field have no roots in common with each other in any extension field. So each $f_i$ contributes $\deg f_i$ distinct roots to $f$ over $\mathbb{C}$, and so $f$ has $\sum_i \deg f_i$ distinct roots over $\mathbb{C}$.
Now, let $p$ be such that $\bar{f}\neq 0$. Reducing our factorization of $f$ mod $p$ we get a factorization $$\bar{f}=\bar{a}\bar{f}_1^{e_1}\dots \bar{f}_n^{e_n}.$$ Since $\bar{f}\neq 0$, none of these factors are $0$. But now it is clear that $\bar{f}$ cannot have more than $\sum_i \deg \bar{f}_i\leq\sum_i\deg f_i$ roots in $\overline{\mathbb{F}}_p$, since each root of $\bar{f}$ is a root of some $\bar{f}_i$. Thus $\rho_p\leq \rho$.
In fact, for all sufficiently large $p$, $\rho_p=\rho$. This can be proven, for instance, by computing $\gcd(f,f')$ in $\mathbb{Q}[x]$ using the Euclidean algorithm. This computation will only involve finitely many rational numbers and thus will be valid in $\mathbb{F}_p[x]$ for all sufficiently large $p$. Since $\frac{f}{\gcd(f,f')}$ has the same roots as $f$ but with no repeated roots (as long as $\deg f$ is less than the characteristic), this implies $\rho_p=\rho$ as long as $p$ is sufficiently large.
Alternatively, this fact is immediate from a bit of model theory. If there are infinitely many different $p$ such that $\rho_p\neq\rho$, take an ultraproduct $F$ of the fields $\overline{\mathbb{F}}_p$ for all such $p$. This ultraproduct $F$ will be a field of characteristic $0$. The statement "$f$ splits and does not have exactly $\rho$ distinct roots" can be expressed in the first-order language of rings and is true in each factor $\overline{\mathbb{F}}_p$, and thus it is also true in the ultraproduct $F$. But since $F$ has characteristic $0$, $f$ must have exactly $\rho$ distinct roots in $F$, so this is a contradiction.