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.

  • 4
    $\begingroup$ 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}$. $\endgroup$ – Lorem Ipsum Feb 3 at 5:02
  • 1
    $\begingroup$ @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 $\endgroup$ – reuns Feb 3 at 6:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Feb 3 at 7:12
  • $\begingroup$ So, are the probabilities bounded between $1/n$ where $n$ is the degree and $\frac{e-1}{e}?$ $\endgroup$ – J. E. Pascoe Feb 3 at 16:27
  • 1
    $\begingroup$ 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...) $\endgroup$ – Lorem Ipsum Feb 4 at 0:26

Your Answer

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

Browse other questions tagged or ask your own question.