Question

An old question that occurred to me again recently: are there any explicit formula known for sequences of irreducible polynomials $g_{p^n}(X)$ in $Z/pZ[X]$ such that for the finite field with $p^n$ elements

$F_{p^n} = (Z/pZ)[X] / (g_{p^n}).$

Such polynomials exist, as anyone who's studied algebra knows, but I've always seen their existence proved nonconsctructively. Ideally, I'm looking for something like

$g_{p^n}(X) = X^n+c_{n-1}(p^n)X^{n-1}+...,$

where $c_{n+1}(p^n)$ is some familiar expression, or something with generating functions, etc.

I'm not an algebraist, so this could have a very obvious answer. One could experiment around with low lying irreducible polynomials to try to come up with a nice pattern, I think, but the fact that I've never seen this presented in an algebra text leads me to suspect that no such formula actually exist and a better answer would come from just asking people in a position to know. In some ways, I realize, it may be like asking for a formula for the nth prime...

Answer 1

There is no known simple explicit formula for an irreducible polynomial of given degree $n$ over $\mathbb{F}_p$. However there has been a lot of work on explicit irreducible polynomials for certain families of $n$, notably $n$ of the form $rq^s$ where $r$ is fixed and $q$ is a fixed prime. For one modest contribution to this field see this paper but also see the papers it cites.

Answer 2

"Explicit formula" is indeed too much to ask. Computationally a presentation of the finite field will be needed. Richard Parker is an expert on such computations, and the page http://www.math.rwth-aachen.de/~Frank.Luebeck/data/ConwayPol/index.html about so-called Conway polynomials might be of interest. There is plenty of other literature.