# Probability that a random univariate polynomial of degree $n$ is irreducible?

Fix a prime $q.$ Let $p(x) = \sum_{i=0}^{n} p_i x^i \in \mathbb{F}_q[x]$ be a polynomial of degree $n,$ and $p$ is monic $(p_n = 1.)$

What is the probability that $p$ is irreducible:

• Over $\mathbb{F}_q[x]$? What I know so far: In $\mathbb{F}_q[x],$ the number of irreducible polynomials of degree $n$ is $O(\frac{q^n}{n}).$ So the probability should be $O(1/n).$
• Same polynomial, $p(x)$ treated as a polynomial over $\mathbb{Z}[x]$?

Motivation: Fix a prime $q,$ pick a random monic poly $p$ of degree $n,$ such all that coefficients of $p$ < $q.$ Test $p$ for irreducibility over both $\mathbb{Z}$ and $\mathbb{F}_q.$ Let $Pr_q$ denote the probability that $p$ is irreducible over $\mathbb{F}_q$ and $Pr_z$ that $p$ is irreducible over $\mathbb{Z}.$ Can we say something about $Pr_q > Pr_z$ or vice versa? Or they are not comparable at all?

• How are you randomly choosing a polynomial over $\mathbb{Q}[x]$? (You don't mean $\mathbb{Z}_q$, by the way; you mean $\mathbb{F}_q$, and you can strengthen the result to $\Theta(1/n)$.) I'm not sure I understand your motivation: for fixed $p$, if $P$ is irreducible $\bmod p$ then it's irreducible, so for any reasonable notion of "random polynomial" the probability that $P$ is irreducible is at least the probability that it's irreducible $\bmod p$. – Qiaochu Yuan May 26 '11 at 21:03
• I've edited the question. Fix a prime $q.$ Pick random poly $p(x)$ where all coefficients are uniformly chosen from $\mathbb{Z}$ and bounded by $q.$ – user2468 May 26 '11 at 21:24
• This may be useful. In this paper Arthur Benjamin and Curtis Bennett prove that, given two randomly chosen non-constant polynomials in $\mathbf{F}_q$, the probability that they are relatively prime is $1-\frac{1}{q}$. A polynomial is irreducible iff it is relatively prime to every polynomial of smaller, positive degree. So it might be possible to piece these probabilities together to get what you want. This may not be the best route to a solution, though. – Jeff May 26 '11 at 21:33
• @Jeff: thanks. I will read the paper. – user2468 May 26 '11 at 21:37
• How are you treating $p$ as a polynomial over $\mathbb{Z}[x]$? Are you identifying $\mathbb{F}_q$ with $\{ 0, 1, ... q - 1 \}$? – Qiaochu Yuan May 26 '11 at 21:49

The question in your motivation is much easier to answer than the actual question! But first: the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_q[x]$ is

$$\frac{1}{n} \sum_{d | n} \mu(d) q^{n/d} = \frac{1}{n} \left( q^n + O(\sqrt{n} q^{n/2}) \right)$$

by Möbius inversion, from which it follows that for fixed $n$ and $q \to \infty$ the probability that a monic polynomial of degree $n$ over $\mathbb{F}_q[x]$ is irreducible is $\frac{1}{n} + O(\sqrt{n} q^{-n/2})$. In particular it approaches $\frac{1}{n}$ exponentially fast.

If $p$ is lifted to a polynomial $\tilde{p} \in \mathbb{Z}[x]$, for example by identifying $\mathbb{F}_q$ with $\{ 0, 1, ... q-1 \}$, then if $p$ is irreducible, so is $\tilde{p}$. It follows that the probability that $\tilde{p}$ is irreducible is at least the probability that $p$ is irreducible.

To show strict inequality it suffices to exhibit a monic integer polynomial of degree $n$ which is irreducible but reducible $\bmod q$. There are many ways to do this (for $n \ge 2$ of course). For example, if $q \ge 5$ then $p(x) = x^n + (q - 2) x^{n-1} + 1$ is irreducible by Perron's criterion, but $p(1) = q$. If $q \ge 3$ and $\ell$ is a prime dividing $q - 1$, then $p(x) = x^n + \sum_{i=1}^{n-1} c_i \ell x^i + \ell$ is irreducible by Eisenstein's criterion, but by choosing the $e_i$ appropriately we can arrange to have $p(1) = q$ again. If $q = 2$ then I think one can use complex-analytic tricks but I don't know any good way to generate examples off the top of my head.

There are MO discussions about variants of your second question here and here. This is a hard circle of questions, and I am pretty sure the answer to the second problem as written depends strongly on how you identify elements of $\mathbb{F}_q$ with integers.

• It follows that the probability that p˜ is irreducible is at least the probability that p is irreducible. This statement, and the lifting answers my question. – user2468 May 26 '11 at 22:09