3
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ The link to sciencedirect.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ May 14, 2023 at 11:57
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! If I could check both answers as correct I would! $\endgroup$ Jul 3, 2010 at 22:21
  • 1
    $\begingroup$ 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 $\endgroup$
    – BS.
    Jul 11, 2010 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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