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$
  • $\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 '16 at 17:07
  • $\begingroup$ thanks.. can i search using latex notations etc? $\endgroup$ – thinker Mar 29 '16 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 '16 at 20:16
  • $\begingroup$ ah ok.. so how would i be able to search for the polynomial ? $\endgroup$ – thinker Mar 29 '16 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 '16 at 20:23
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$
  • $\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 '16 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 '16 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 '16 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 '16 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 '16 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$
  • $\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 '16 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 '16 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 '16 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 '16 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 '16 at 20:02

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.