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?
[Math] Characterization of irreducible polynomials over finite fields
finite-fieldspolynomials
Best Answer
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.