7
$\begingroup$

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?

    • 0
      @Qiaochu: by incomparable, I meant "we don't know which one is going to be larger than the other".2011-05-26

    1 Answers 1

    8

    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.

    • 0
      *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.2011-05-26