Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
What do you mean by "characterization"? –  Qiaochu Yuan Oct 17 '12 at 7:07
1  
@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. –  mlbaker Oct 17 '12 at 7:12
1  
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
3  
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
add comment

3 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
In numerous places your post seems to lack a verb. –  mlbaker Apr 26 '13 at 20:16
add comment

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,

share|improve this answer
add comment

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.