1
$\begingroup$

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!

$\endgroup$
7
  • 1
    $\begingroup$ Ordinarily, people count monic polynomials. Is that what you have in mind? $\endgroup$
    – Lubin
    Apr 4, 2013 at 0:19
  • $\begingroup$ No, I need to count all irreducible polynomials. $\endgroup$
    – William Stagner
    Apr 4, 2013 at 0:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Lubin
    Apr 4, 2013 at 0:22
  • $\begingroup$ Okay, that makes sense. Then I have no idea how to count the reducible polynomials by linear factors... $\endgroup$
    – William Stagner
    Apr 4, 2013 at 0:25
  • $\begingroup$ 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? $\endgroup$
    – William Stagner
    Apr 4, 2013 at 0:36

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – William Stagner
    Apr 4, 2013 at 1:21
  • $\begingroup$ 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)$ $\endgroup$
    – Lubin
    Apr 4, 2013 at 13:04
1
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .