3
$\begingroup$

Question 1: Find $[K:\mathbb{F_2}]$

Idea: I have tried looking at the irreducibility of the polynomial, $X^4+X+1 $ and have so far been unsuccessful. Is there another way to do this apart from using Eisenstein's criterion, which I have already tried?

Then if it were irreducible, and since $\alpha$ is a root of $P(X)= X^4+X+1$, then $[\mathbb{F_2}(\alpha):\mathbb{F_2}]$ would be equal to deg$P(X)=4$

Question 2: Find the minimal polynomial for $\alpha^{-1}$ over $\mathbb{F_2}$

Idea: First find the minimal polynomial for $\alpha$ over $\mathbb{F_2}$, call this $M(X)=a_nX^n+a_{n-1}X^{n-1}+ ... + a_0$. Then the minimal polynomial for $\alpha^{-1}$ will be $N(X)=a_0 X^n+a_1 X^{n-1}+...+a_n$. Now, since $\alpha$ is a root of a degree 4 polynomial, I believe its deg$M(x)\leq 4$ although I have not managed to find it

Would really appreciate some help from you, thanks

$\endgroup$
5
  • $\begingroup$ I don't think this is the first time irreducibility of $x^4+x+1$ over $\Bbb{F}_2$ has been handled on our site. You could search :-) Eisenstein cannot be applied, because there are no primes in $\Bbb{F}_2$. Nor in any other field. Fields have no primes - only units. Eisenstein is useful only when the field is the field of fractions of a PID. Your idea for question 2 is a good one, and it works. Search for reciprocal polynomial. $\endgroup$
    – Jyrki Lahtonen
    Mar 29, 2016 at 17:07
  • $\begingroup$ thanks.. can i search using latex notations etc? $\endgroup$
    – thinker
    Mar 29, 2016 at 20:03
  • $\begingroup$ Unfortunately the local search engine strips LaTeX, and therefore fails. Google (restricted to the site) is a bit better, but not reliable in matching LaTeX strings. That is one of the major shortcomings of the search functionality. Good luck! As long as you make a good faith attempt at searching, no one has anything to complain! $\endgroup$
    – Jyrki Lahtonen
    Mar 29, 2016 at 20:16
  • $\begingroup$ ah ok.. so how would i be able to search for the polynomial ? $\endgroup$
    – thinker
    Mar 29, 2016 at 20:17
  • $\begingroup$ Try suitable general searches. For example, when I gave the site search engine the input degree four irreducible polynomials. It gives this list. And then this post is one of the first hits. Also, take a look at the sidebar and the lists of Linked and Related questions. $\endgroup$
    – Jyrki Lahtonen
    Mar 29, 2016 at 20:23

2 Answers 2

Reset to default
5
$\begingroup$

Clearly it has no roots, so it has no irreducible linear or cubic factors. The only irreducible degree $1$ polynomial over $\Bbb F_2$ is $x^2+x+1$, so the only possible quadratic factorization is as $(x^2+x+1)^2=x^4+x^2+1$ which clearly is not your polynomial. Hence it is irreducible. This means the degree of the extension is $4$. Eisenstein is a criterion for irreducibility over the rationals though, it doesn't apply in $\Bbb F_2$

If you are worried about negative powers, then let's reformulate this as $[\Bbb F[\alpha]:\Bbb F]$ which is clearly a vector space of degree $4$ over $\Bbb F_2$. But then we know that $\Bbb F_2[\alpha]\cong \Bbb F_2[x]/(x^4+x+1)$ by the map

$$\begin{cases} \Bbb F_2[x]\to \Bbb F_2[\alpha]\\ x\mapsto \alpha\end{cases}$$

The map is clearly surjective, and by definition of the minimal polynomial and the fact that $\Bbb F_2[x]$ is a PID, we see the kernel is exactly $(x^4+x+1)$. But then the first isomorphism theorem for rings says that $\Bbb F_2[\alpha]\cong \Bbb F_2[x]/(x^4+x+1)$ as desired. Since the polynomial is generated by an irreducible in a PID, it is a maximal ideal, so the quotient $\Bbb F_2[\alpha]$ is a field. But since $\Bbb F_2(\alpha)$ is the smallest field containing $\alpha$, it must be that $\Bbb F_2(\alpha)\subseteq\Bbb F_2[\alpha]$. The inclusion in the other direction is trivial, hence the dimensions are equal.

For your second question, note that $p(x^{-1})=x^{-4}+x^{-1}+1$ is something which is zero when you put in $\alpha^{-1}$, so if you multiply it by $x^4$ you get

$$x^4p(x^{-1})=1+x^3+x^4$$

plugging in $\alpha^{-1}$ we get $\alpha^{-4}\cdot p(\alpha) = 0$, so this is the minimal polynomial for $\alpha^{-1}$, since you can get irreducibility from the same things we said for $\alpha$, namely that there are no roots, and it is not equal to $x^4+x^2+1$.

$\endgroup$
8
  • $\begingroup$ a dumb question : how do I jump from $\alpha$ is a root of some irreductible degree $4$ polynomial to $[\mathbb{F}_2(\alpha) : \mathbb{F}_2] = 4$ ? $\endgroup$
    – reuns
    Mar 29, 2016 at 17:21
  • $\begingroup$ @user1952009 because the polynomial is irreducible, it means that $1,\alpha,\alpha^2,\alpha^3$ are linearly independent, so the space $\Bbb F_2(\alpha)$ is a $4$-dimensional vector space over $\Bbb F_2$, which is the definition of the field extension degree. $\endgroup$
    – Adam Hughes
    Mar 29, 2016 at 17:38
  • $\begingroup$ ok, all the positive powers of $\alpha$ are in the $\mathbb{F}_2$ vector space generated by $1,\alpha,\alpha^2,\alpha^3$. (and if those powers of $\alpha$ were lying in some smaller vector space, that would give a lower degree minimal polynomial for $\alpha$). but what about the negative powers of $\alpha$ ? and all the other elements we added to the field ($\mathbb{F}_2$ is not a good example but you see what I mean) ? $\endgroup$
    – reuns
    Mar 29, 2016 at 17:49
  • $\begingroup$ @user1952009 if you multiply $\alpha^4+\alpha+1=0$ by $\alpha^{-1}$ you'll see that $$\alpha^3+1+\alpha^{-1}=0\iff \alpha^{-1}=\alpha^3+1$$ so $\alpha^{-1}$ (and other negative powers) are all linearly dependent on the set I gave as well. $\endgroup$
    – Adam Hughes
    Mar 29, 2016 at 17:52
  • $\begingroup$ and for the other elements, it is the same argument ? for each $u$ in the vector space, there is polynomial of degree $4$ whose $u$ is some root : $\sum_{k=0}^4 u^k c_k = 0$, and multiplying by $u^{-1}$ we see that $u^{-1}$ is linearly dependent of $1,u,u^2,u^3$, hence that vector space is indeed a field (hence it is $\mathbb{F}_2(\alpha)$) $\endgroup$
    – reuns
    Mar 29, 2016 at 17:57
2
$\begingroup$

if $\alpha$ is a root of $P(X)= X^4+X+1$ then it exist in $\mathbb{GF_{16}}$ and indeed $\alpha$ is primitive element of $\mathbb{GF_{16}}$ .it's minimal polynomial with respect to $\mathbb{GF_2}$ is $X^4+X+1 $ itself.

for the second part we have $\alpha^{-1}$ = $\alpha^{14}$ because $\alpha^{14} = \alpha^{3}+1$ and $\alpha \times \alpha^{14} =\alpha \times (\alpha^{3}+1)= \alpha^{4}+\alpha = 1$ because we know $\alpha^{4}+\alpha+1=0$. so the minimal polynomial with respect to $\mathbb{GF_2}$ containing $\alpha^{14}$ comes from producting conjugacy class $\{ \alpha^{7},\alpha^{11},\alpha^{13},\alpha^{14} \} \Rightarrow (x+\alpha^{7})(x+\alpha^{11})(x+\alpha^{13})(x+\alpha^{14})$ which after simplification yields in: $$x^4+x^3+1$$

$\endgroup$
6
  • $\begingroup$ You should comment on irreducibility in your first statement: the op indicated that was one of his main areas of issue. $\endgroup$
    – Adam Hughes
    Mar 29, 2016 at 16:59
  • $\begingroup$ $X^4+X+1$ is a Primitive Polynomial so there is no doubt in it's irreducibility. en.wikipedia.org/wiki/Finite_field under section GF(16) $\endgroup$
    – K.K.McDonald
    Mar 29, 2016 at 17:06
  • $\begingroup$ Yes, but you prove something is primitive by showing a root generates, so in particular you need to show irreducibility, so your logic is circular. $\endgroup$
    – Adam Hughes
    Mar 29, 2016 at 17:07
  • $\begingroup$ you are right. but irreducibility can be shown only by inspection. so I think there is no point in doing the search yourself. it's better to use the results provided by tables. $\endgroup$
    – K.K.McDonald
    Mar 29, 2016 at 17:14
  • $\begingroup$ @K.K.McDonald thank you for your answer. how do we know that $\alpha^{-1}=\alpha^{14}$? Is this done by brute force multiplying out many powers of $\alpha$ as this would take a very long time, especially for an exam.. or is there another way you got this? $\endgroup$
    – thinker
    Mar 29, 2016 at 20:02

You must log in to answer this question.

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