3
$\begingroup$

Show that each monic irreducible polynomial of $\mathbb{F}_q[x]$ of degree $m$ is the minimal polynomial of some element of $\mathbb{F}_{q^m}$ with respect to $\mathbb{F}_q$ .

Using theorem, find all the irreducible polynomials of degree 4 over F2. (Let α be a root of 1 + x^3 + x^4 ∈ F2[x].)

$\endgroup$
5
  • 1
    $\begingroup$ The part after "I messed it up" is not clear. What theorem do you mean? Where is the connection to the first part? $\endgroup$
    – azimut
    Nov 3, 2013 at 17:24
  • $\begingroup$ I second azimut's query. His +1 answer takes care of the question in the first paragraph. $\endgroup$ Nov 3, 2013 at 17:26
  • 1
    $\begingroup$ To prove that a quartic is irreducible you need to check that it doesn't have linear or irreducible quadratic divisors. A polynomial has a linear factor, iff it has a zero in the base field (here $\Bbb{F}_2$). There is only one irreducible quadratic polynomial in $\Bbb{F}_2[x]$. If you are asked to prove the irreducibility of $x^4+x^3+1$, then you have surely been given that irreducible quadratic in class :-) Hint: it is the only quadratic that does not have zeros in $\Bbb{F}_2$. $\endgroup$ Nov 3, 2013 at 17:31
  • $\begingroup$ i know what you say. but i must show this using the current theorem. so i did not get, exactly. $\endgroup$ Nov 3, 2013 at 17:32
  • $\begingroup$ to azimut with respects =) Using theorem, find all the irreducible polynomials of degree 4 over F2. (Let α be a root of 1 + x^3 + x^4 ∈ F2[x].) $\endgroup$ Nov 3, 2013 at 17:35

3 Answers 3

3
$\begingroup$

Adding my bit with a view of covering the possibility (somewhat implied by OP's comments) that the task really is to find all the irreducible quartic polynomials over $\Bbb{F}_2$ using the theorem that they must all be factors of $p(x)=x^{16}-x$.

The given minimal polynomial of $\alpha$, $f_1(x)=x^4+x^3+1$ is obviously one of those. A useful trick for finding another one is to go to the so called reciprocal polynomial, i.e. $$ f_2(x)=x^4f_1(\frac1x)=x^4(\frac1{x^4}+\frac1{x^3}+1)=1+x+x^4. $$ We immediately see that $$ f_2(\frac1\alpha)=\alpha^4f_1(\alpha)=0, $$ so $f_2(x)$ is a multiple of the minimal polynomial of $1/\alpha$. As the elements $\alpha$ and $1/\alpha$ generate the same extension field, their respective minimal polynomials must be of the same degree. Therefore $f_2(x)$ is the minimal polynomial of $1/\alpha$ and is, thus also irreducible.

Let's take stock. We know that in addition to $f_1(x)$ and $f_2(x)$ the polynomial $p(x)$ is divisible by $q(x)=x^4-x$ (if you don't know how to deduce this from properties of finite fields, then you can just calculate that $q(x)^4+q(x)=p(x)$. Thus we know that $p(x)$ factors like $$ p(x)=q(x) f_1(x) f_2(x) r(x), $$ where $r(x)$ is some yet unknown factor. We can partially factor $p(x)$ directly as follows: $$ p(x)=x(x^{15}-1)=x(x^5-1)(x^{10}+x^5+1)=x(x-1)(x^4+x^3+x^2+x+1)(x^{10}+x^5+1), $$ and $q(x)$ as follows: $$ q(x)=x(x^3-1)=x(x-1)(x^2+x+1), $$ where that last quadratic factor is irreducible.

I leave it as an exercise for you to check that $$ (x^2+x+1)f_1(x)f_2(x)=x^{10}+x^5+1. $$ Putting all this together gives us that the mystery factor $r(x)=f_3(x)=x^4+x^3+x^2+x+1$. I next claim that $f_3(x)$ is irreducible. As it has no zeros in $\Bbb{F}_2$ it has no linear factors in $\Bbb{F}_2[x]$. It cannot be a product of two distinct quadratics, because then it should be a factor of $q(x)$. It cannot be the square of a quadratic, because then its zeros would not be simple, but $f_3(x)$ is a factor of $p(x)$ that has 16 distinct zeros.

Thus the list $f_1(x), f_2(x), f_3(x)$ is a complete list of irreducible quartics in $\Bbb{F}_2[x].$


Yet another way of deducing the irreducibility of $f_3(x)$ is to observe that $f_3(x)\mid x^5-1$, so its zeros are fifth roots of unity. If you are familiar with the cyclicity of the multiplicative groups of finite fields, then you can immediately check that $\Bbb{F}_{16}$ has no proper subfields containing primitive fifth roots of unity. Therefore the minimal polynomial of a fifth root of unity over $\Bbb{F}_2$ must have degree four, i.e. equal to $f_3(x)$.

Observe that $f_3(x)$ is its own reciprocal polynomial. Polynomials with this property are called palindromic because you can equally well read their sequence of coefficients backwards. Therefore our first trick won't give us a fourth irreducible quartic.

$\endgroup$
1
  • $\begingroup$ Thank you very much. really I appreciate you Jyrki Lahtonen . $\endgroup$ Nov 3, 2013 at 19:26
3
$\begingroup$

This question is a bit strange, since the real work is in showing that all fields of order $q^m$ are isomorphic. If $\def\F{\Bbb F}P\in\F_q[X]$ is irreducible with $\deg P=m$, then $K=\F_q[X]/(P)$ is a field with $q^m$ elements in which the image $\bar X$ of $X$ has minimal polynomial$~P$ over$~\F_q$. If you know that necessarily $K\cong\F_{q^m}$, just choose an isomorphism and let $\alpha\in\F_{q^m}$ be the element corresponding to$~\bar X$ under the isomorphism.

There is a slight subtlety in that here you view $\F_q$ as a subfield of $\F_{q_m}$ by restriction (from $K$ to $\F_q$) of the chosen isomorphism. If you had already an embedding $\F_q\hookrightarrow\F_{q_m}$ when $\F_{q^m}$ was first given to you, then you must make sure to match that embedding, which plays a vital role when you talk about minimal polynomials over $\F_q$ of elements of $\F_{q^m}$. Fortunately this can always be done: every finite field is normal over the prime field $\F_p$, so there is a surjective morphism $\def\Gal{\operatorname{Gal}}\Gal(\F_{q^m}/\F_p)\to\Gal(\F_q/\F_p)$ that can be used to adjust the embedding to what is needed by applying an automorphism of $\F_{q^m}$.

$\endgroup$
3
$\begingroup$

Let $f$ be a monic irreducible polynomial over $\mathbb F_q$ of degree $m$ and $F$ be an algebraic closure of $\mathbb F_q$. $f$ has a zero $\alpha$ in $F$. So $f$ is the minimal polynomial of $\alpha$ over $\mathbb F_q$ and $$[\mathbb F_q(\alpha) : \mathbb F_q] = \deg(f) = m,$$ so $\lvert \mathbb F_q(\alpha)\rvert = q^m$. Since all finite fields of the same order are isomorphic, $\mathbb F_q(\alpha) \cong \mathbb F_{q^m}$. Thus, there is an element $a\in \mathbb F_{q^m}$ such that $f$ is its minimal polynomial.

For the subtle point why it is possible to find $a$ such that the minimal polynomial $f$ is not "twisted" by the isomorphism $\mathbb F_q(\alpha) \to \mathbb F_{q^m}$, see the discussion below and in particular the explanation of Marc van Leeuven.

$\endgroup$
9
  • $\begingroup$ so α^4=α^3+1 is my primitive element. so 1+x^3+x^4 is irreducible over F2 am i right? $\endgroup$ Nov 3, 2013 at 17:20
  • 2
    $\begingroup$ I answered the first part of your question: "Show that each monic irreducible polynomial of $\mathbb F_q[x]$ of degree $m$ is the minimal polynomial of some element of $\mathbb F_{q^m}$ with respect to $\mathbb F_q$. $\endgroup$
    – azimut
    Nov 3, 2013 at 17:23
  • $\begingroup$ I am not sure that the reasoning is correct (or, at least, complete): Say you have the isomorphism $\varphi:\mathbb{F}_q(\alpha)\rightarrow \mathbb{F}_{q^m}$. Then it is clear that $\varphi(\alpha)$ is a root of $\overline{\varphi}(f),$ where $\overline{\varphi}$ is the isomorphism $\varphi$ extended to the ring $\mathbb{F}_q[x]$ in the obvious way. But how would you ensure that it is a root of $f$ as well? For this to work, you need $\varphi$ to be $\mathbb{F}_q$-isomorphism. $\endgroup$ Nov 3, 2013 at 17:50
  • $\begingroup$ @PavelC: In the moment where you define $\alpha$, you know that $f$ is its minimal polynomial over $\mathbb F_q$. I've changed the order of the arguments in my answer to make this clear. $\endgroup$
    – azimut
    Nov 3, 2013 at 18:10
  • 1
    $\begingroup$ I think this still does not solve it (say you have $\mathbb{R}\subseteq \mathbb{C}$ and an automorphism of $\mathbb{C}$ which sends an element $\alpha \in \mathbb{C}\setminus \mathbb{R}$ to something other than its conjugate. Then the minimal polynomial of the element changes). $\endgroup$ Nov 3, 2013 at 18:25

You must log in to answer this question.

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