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.

I'm trying to find the number of $3$rd degree irreducible polynomials over $\mathbb{F}_3$ and $\mathbb{F}_5$.

Since a $3$rd degree polynomial is irreducible if and only if it is divisible by a $1$st degree polynomial, my strategy is to count the number of $3$rd degree polynomials and subtract the number of reducible ones.

I have figured that the number of $3$rd degree polynomials over a finite field $\mathbb{F}_q$ is $$(q-1)(q^3)=q^4-q^3,$$ but I'm having trouble figuring out how many of these are reducible. I'm having trouble with this, because just counting linear factors doesn't work, i.e. $$3x*4x=12x^2=2x^2=2x*x $$

in $\mathbb{F}_5$ (by the way, how does this not contradict $F[x]$ being a UFD?)

Thank you!

share|improve this question
1  
Ordinarily, people count monic polynomials. Is that what you have in mind? –  Lubin Apr 4 '13 at 0:19
    
No, I need to count all irreducible polynomials. –  William Stagner Apr 4 '13 at 0:20
2  
Uniqueness of factorization is always described or defined up to units of the ring in question. Here, the units of $k[x]$ are the constants of $k$. So God’s in his heaven, all’s right with the world. –  Lubin Apr 4 '13 at 0:22
    
Okay, that makes sense. Then I have no idea how to count the reducible polynomials by linear factors... –  William Stagner Apr 4 '13 at 0:25
    
Since I can multiply any irreducible polynomial by the inverse of its leading coefficient to get a monic irreducible polynomial, then the number of irreducibles is the number of monic irreducibles multiplied by the order of the field - 1, right? –  William Stagner Apr 4 '13 at 0:36

2 Answers 2

up vote 2 down vote accepted

This is a question that comes up over and over again; with the right search skills you and I could both find earlier related questions on SE. The idea is this, though: First, I'll count monics only. A monic irreducible of degree three has for its roots three conjugate irrationalities. Any one of these generates the field of cardinality $p^3$ — for our constant field we’re taking $\mathbb F_p$ for $p=3,5$. In that field of cardinality $p^3$, $p$ of them are already in $\mathbb F_p$. So there are $p^3-p$ cubic irrationalities in $\mathbb F_{27}$ and $\mathbb F_{125}$, respectively. In both cases, you divide by $3$ to get the number of monic irreducibles of degree $3$. Now just multiply by $p-1$ to count all the irreducibles.

The story gets both more complicated and more interesting if you want to count, say, irreducibles of degree $6$, but I’ll leave that to others, whose answers in any case will be more complete and more succinct than mine.

share|improve this answer
    
Thank you for the reply! Could you explain why you divide by $p^3-p$ by $3$ to obtain the number of monic irreducible polynomials? –  William Stagner Apr 4 '13 at 1:21
    
Because if $\alpha$, $\beta$, and $\gamma$ make up a set of conjugates, then $(x-\alpha)(x-\beta)(x-\gamma)$ is a polynomial with coeffs in $\mathbb F_p$, necessarily irreducible. So the set of all conj. triples can be looked at as the same as the set of monic irreds of deg $3$, and there are $N/3$ triples, if $N$ is the number of cubic irrationalities in the $\mathbb F(p^3)$ –  Lubin Apr 4 '13 at 13:04

The total number of irreducible polynomials of degree $n$ over a field $\mathbb{F}_p$ is

$$\psi(n)=\frac{p-1}{n}\sum_{d|n}\mu(d)p^{n/d}$$ where $\mu(n)$ is the Möbius function $$ \mu(n) = \left\{ \begin{array}{ll} 1 & \mbox{if $n=1$};\\ 0 & \mbox{if $n$ is a square};\\ (-1)^r & \mbox{if $n$ has $r$ distinct prime factors } .\end{array} \right. $$

share|improve this answer
    
Thank you for the answer! Unfortunately, we haven't proved this fact yet, so I don't think I'm able to use it. –  William Stagner Apr 4 '13 at 1:06
    
@ThomasAndrews you're right, I knew I was forgetting a factor somewhere. I fixed it now –  Brent J Apr 4 '13 at 1:17
    
@WilliamStagner perhaps you can just use it to double check your work then... –  Brent J Apr 4 '13 at 1:18
    
This is such a neat result, I always tried to slip it in when I was teaching abstract algebra. –  Lubin Apr 4 '13 at 13:23

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.