# At most of degree 4 irreducible polynomials over $\mathbb{Z}_3$

Let's denote a polynomial of degree $k$: $f(x) = (a_1,\ldots ,a_k) := a_1x^k+\cdots +a_k$. Find all irreducible monic polynomials over $\mathbb{Z}_3$ of degree at most $4$.

For $\deg f = 1$, we have $f = (1,0),(1,1),(1,2)$. This serves as a generator for all Reducible monics of degree $2$. We have total of 6 ways to uniquely multiply them to obtain a monic of degree $2$ and since there are $9$ total, this leaves us $3$, thus:
For $\deg f=2$, we have $f = (1,0,1),(1,1,2),(1,2,1)$.

For $\deg f=3$, we have total of $27$ monics and the generator of reducibles of $\deg 3$ is the union of the irreducibles of $\deg 1$ and $\deg 2$ and so we have multiply them in "all possible ways" that yield something of degree $3$.
The counting gets messy here:
For degree $1$ irreducibles, we can cube each of them, $3$ ways. We can Square one and multiply by another, $6$ ways and we can multiply them all for a total of $10$ ways.
Since we want the product to be of degree $3$ , we need to multiply $\deg f=1$ irreducibles with $\deg f=2$ irreducibles, that gives us another $9$ possibilities.
Are there $19$ reducibles of degree $3$? (i.e 8 irreducibles?)

Concern: Are all these products unique, that is, do we count everything exactly once?

For $\deg f=4$, we can (hopefully) count analogously.

I can write tables for small degrees and test everything out by hand and find irreducibles in some amount of effort. What to do when we find all irreducibles of , say, at most degree $8$ over $\mathbb{Z}_{17}$?

Is there a quicker method of determining irreducibility or weeding out the irreducibles of a given degree? The end of goal is still explicitly finding all of them.

• See this entry on wikipedia. – WimC Oct 29 '16 at 9:12
• @WimC ah, thanks, that confirms my observations. Do you have any tips on how to explicitly write them all out, though? For the fourth degree, $N(3,4) = 18$. It would be bothersome to write all the $81$ polynomials out and see what fits – Alvin Lepik Oct 29 '16 at 9:35

You can do the following: The Galois Group of $\mathbb{F}_{81}$ is the cyclic group $C_4$. There are $18$ orbits of size $4$, the others are of order $2$ or $1$. These orbit are of the form $\{z^k,z^{3k}, z^{9k}, z^{27k} \}$, for $z$ a primitive element and the exponents taken $\operatorname{mod} 81$. An irreducible polynomial is then given by $(z-z^k)(z-z^{3k})(z-z^{9k})(z-z^{27k})$.
The elements of $\mathbb{F}_{81}$ are, by Galois theory, invariant for a subgroup $H$ of the Galois group $G$, there is only such (non trivial) subgroup namely the sqyare of the generator of $G$, the Frobenius exponential map of order $3$. This means that we are to look out for values $k$ for which $z^k$ is invariant under the Frobenius map of order $9$, i.e. the $k$ for which $$z^{9k} = z$$, or, equivalently $z^{8k} = 1$. Since the order of $z$ is $80$ this gives rise to the values $k \in \{10, 20, 30, 40, 50, 60, 70, 80\}$ .
• A good start, but there is the (minor) catch that if $k$ is a multiple of ten, then $z^k$ is in the subfield $\Bbb{F}_9$. Those have quadratic minimal polynomials. Or, if $10\mid k$, then $z^{9k}=z^k$. – Jyrki Lahtonen Oct 29 '16 at 13:56
• @Jyrki Indeed, $10$ does indeed give an orbit of size $2$. As there are $81$ points in total not all the orbits can have a size of $4$. I only thought that it was the wish of the OP not to wade through a total of $81$ polynomials. I'll edit my answer to reflect the values for $k$ that give rise to an orbit of size $<4$. – Marc Bogaerts Oct 29 '16 at 17:11