Characterization of irreducible polynomials over finite fields

Question

How much is known about irreducible polynomials over finite fields? I have seen the formula (a result of Möbius inversion) that gives the number of such polynomials, but I am looking for something more; say, a characterization of those sequences $(a_n, \ldots, a_0)$ which are the coefficients of a degree-$n$ irreducible polynomial over the finite field with $q = p^n$ elements. Does such a thing exist (even in special cases)? Might such a thing exist, or has it in some way been shown that such a characterization is impossible?

Answer 1

Trying to say something more. I don't know, if this is at all what you were hoping.

Let us agree to look at monic polynomials only. Things like the following are known. If you specify any low degree part $a_dx^d+\cdots a_1x+a_0$ with a non-zero constant term, then asymptotically (for degree $n$ much higher than $d$) the residue classes of irreducible polynomials of degree $n$ modulo $x^{d+1}$ are uniformly distributed. In other words, each such low degree part appears equally often at the tail of an irreducible polynomial (well, the distribution is not exactly uniform for any specific $n$, but asymptotically the error term becomes negligible).

This result is obviously an analogue of Dirichlet's result of equidistribution of rational primes into (coprime) residue classes modulo $m$. Its proof is IMHO a bit simpler. See, e.g. Rosen's book.

Does this kill some of your hopes?

Families of known irreducible polynomials are few. The first one that comes to mind is the family of cyclotomic polynomials with zeros that are primitive roots of unity of an order that is a power of three. These polynomials $$ \phi_{3^\ell}(x)=x^{2\cdot3^{\ell-1}}+x^{3^{\ell-1}}+1 $$ remain irreducible over the field of two elements. The proof is an exercise in Lidl & Niederreiter, and is essentially equivalent to showing that two is a primitive root modulo $3^\ell$. This family of irreducible polynomials is admittedly very sparse.

Answer 2

I don't know if this is enough for you or if you know the formula, but there exists a way to directly compute all the irreducible polynomials over $\mathbb F_p$ inductively.

Recall that for every integer $n$, there is only one field, namely $\mathbb F_{p^n}$, such that $[K : \mathbb F_p] = n$. It so happens that this field is the splitting field of the polynomial $x^{p^n}-x$, and that if $p(x) \, | \, x^{p^n}-x$ is irreducible, then its roots generate an extension of $\mathbb F_p$ which is of degree $d$ (isomorphic to $\mathbb F_{p^d}$), hence $d \, | \, n$, and using such facts, if we finish the argument one gets $$ x^{p^n} - x = \prod_{d \, | \, n} \left( \prod_{p \text{ irr. deg } d} p(x) \right) $$ where the second product is taken over all the irreducible polynomials of degree $d$. Therefore, we can use induction to compute all the irreducible factors of degree $n$ of $x^{p^n} - x$ when we know those of degree dividing $n$ being less than $n$.

Hope that helps,