# Characterization of irreducible polynomials over finite fields

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?

-
What do you mean by "characterization"? –  Qiaochu Yuan Oct 17 '12 at 7:07
@Qiaochu: That's a very good question, of course. I'm interested in any condition that would be equivalent to (and hopefully, more concrete than) irreducibility when the field is finite. Eisenstein's criterion is nice, but it's only sufficient and not necessary. –  mew Oct 17 '12 at 7:12
Eisenstein's criterion doesn't apply here. Finite fields don't have any prime elements. What's not concrete about irreducibility? The only reasonable way I can think of to answer this question is to point you to an algorithm for determining whether a polynomial is irreducible (see en.wikipedia.org/wiki/Berlekamp's_algorithm ). –  Qiaochu Yuan Oct 17 '12 at 7:54
This question is difficult. To see this draw the parallel to integers, when you would be asking for a characterization of sequences of decimal digits that form the decimal expansions of prime numbers. In a polynomial ring over a finite field such number theoretic questions are often easier (this is a theme in Rosen, but it is still difficult. The relevant chapter of Lidl & Niederreiter has a few bits. –  Jyrki Lahtonen Oct 17 '12 at 12:40

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.

-

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,

-

You may see the text "Finite Fields" by Michael Waldschmidt. Corollary 37. A $n$-cyclotomic polynomial over a finite field of cardinality $q$ (a power of a prime $p$) if and only if the class of $q$ modulo $n$ has order $\varphi(n)$ (Euler's totient function if and only if $q$ is a generator of the group of units of $\mathbb Z/n\mathbb Z$.

-
In numerous places your post seems to lack a verb. –  mew Apr 26 '13 at 20:16