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$
  • 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 '13 at 17:24
  • $\begingroup$ I second azimut's query. His +1 answer takes care of the question in the first paragraph. $\endgroup$ – Jyrki Lahtonen Nov 3 '13 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$ – Jyrki Lahtonen Nov 3 '13 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$ – spectralmath Nov 3 '13 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$ – spectralmath Nov 3 '13 at 17:35
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$
  • $\begingroup$ Thank you very much. really I appreciate you Jyrki Lahtonen . $\endgroup$ – spectralmath Nov 3 '13 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$
  • $\begingroup$ so α^4=α^3+1 is my primitive element. so 1+x^3+x^4 is irreducible over F2 am i right? $\endgroup$ – spectralmath Nov 3 '13 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 '13 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$ – Pavel Čoupek Nov 3 '13 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 '13 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$ – Pavel Čoupek Nov 3 '13 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.