# Probability that an irreducible polynomial has a root modulo a prime $p$

Let $$q$$ be an irreducible polynomial over $$\mathbb{Z}.$$ What is the probability that $$q$$ has at least one root modulo a prime $$p?$$

For quadratic $$q,$$ the probability should be about a half by quadratic reciprocity in combination with completing the square. The probability that a general function from $$\mathbb{F}_p$$ to itself has a root is about $$\frac{e-1}{e}.$$ Therefore, one would guess as the degree of the polynomial goes to infinity, that the probability approaches this number.

• For an irreducible polynomial of degree n whose Galois group is $G \subset S_n$, the density of primes for which there is a solution modulo $p$ equals the probability that an element $g \in G$ has a fixed point (by Cebotarev Density). If $G = S_n$, this is the probability that $g$ is not a derangement, which does tend to $1 - e^{-1}$. However, for other $G$, the answer may differ. If $G$ is abelian, the only element with a fixed point is the identity (irreducibility implies $G$ is necessarily transitive in $S_n$), so the density of primes which have a root is $1/n \rightarrow 0 \ne 1-e^{-1}$. – Lorem Ipsum Feb 3 at 5:02
• @LoremIpsum Also you should probably mention Chebotarev works only for $p$ much larger than ... some parameters of $\zeta_K$, in particular as the degree of $[K:Q]\to \infty$ we need $p \to \infty$ faster to apply Chebotarev. For $p$ fixed and $\deg(f) \to \infty$ choosing the coefficients of $f$ in an acceptable random way we can probably say $c=\prod_{a \bmod p} f(a)$ $\to$ to a product of independent uniform random variables, so $Pr[c \equiv 0 \bmod p] \to 1-(1-p^{-1})^p$. For $p$ of moderate growth finding which setting applies probably depends on the grand Riemann hypothesis – reuns Feb 3 at 6:31
• It may be worth pointing out that in the Abelian case the events $a$ is root of $q$ modulo $p$ are not independent. It's more like when $G$ is abelian, if there is a single root of $q$ modulo $p$, then there will be $n$ roots modulo $p$. In other words, the presence of a single root modulo $p$ implies that $q$ splits into linear factors modulo $p$. This explains why a purely combinatorial argument gives wrong results when $G$ is abelian. – Jyrki Lahtonen Feb 3 at 7:12
• So, are the probabilities bounded between $1/n$ where $n$ is the degree and $\frac{e-1}{e}?$ – J. E. Pascoe Feb 3 at 16:27
• Dear @J.E.Pascoe, finding the best bounds is a good question! If G is transitive, then the stabilizer H of a point has index n, and all elements in H fix a point. This gives a lower bound 1/n. On the other hand, if $n = q$ is prime and $G = \mathrm{Aff}(\mathbf{F}_q)$ is the affine group, then the number of derangements is only $|G|/n$, which gives the bound $(n-1)/n$. For example, for a prime $q$, the polynomial $x^q - 2$ has a solution modulo $p$ for a set of primes of density $1 - 1/q$. In fact, it turns out that it is bounded between $1/n$ and $1-1/n$ (continued...) – Lorem Ipsum Feb 4 at 0:26