Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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...

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

"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.

share|improve this answer
    
Thanks! If I could check both answers as correct I would! –  Brad Rodgers Jul 3 '10 at 22:21
    
There is also the incredible Nim addition and multiplication defined by JH Conway on the ordinals, that make $\omega^{\omega^\omega}$ an algebraic closure of F2 . But the multiplication is somewhat unpracical, so not really "explicit". See matrix.cmi.ua.ac.be/index.php/on2-conways-nim-arithmetics.html –  BS. Jul 11 '10 at 15:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.