Determine minimal polynomial over a field

Question

Let $K = \mathbb{F}_2[x] / (x^3+x+1)$ [$K$ is a field, because $(x^3+x+1)$ is a maximal ideal in $\mathbb{F}_2[x]$].

Determine the minimal polynomial of $\overline{x+1}\in K$ over the field $\mathbb{F}_2$.

We need to find a monic polynomial $g\in \mathbb{F}_2[x]$ [they are automatically monic] such that $g$ generates $\{f\in\mathbb{F}_2[x] : f(\overline{x+1})=0\}$.

Confusing parts:
In principle, $g$ could be of any degree or is the degree limited?

We need something like $$\overline{x+1}^n + a_{n-1}\overline{x+1}^{n-1}+\ldots + a_1\overline{x+1} + a_0 = 0, a_j\in\mathbb{F}_2 $$

Of course we can try and see what works out, but is there a clear method to doing this?

Answer 1

Using your (a little cumbersome and perhaps confusing) notation, observe that $\;\overline{x+1}=\overline{x^3}\;$ in $\;K.\;$ I'd rather denote $\;w:=\overline x\;$ , so that you have $\;w^3+w+1=0\implies w+1=w^3\;$ and etc.

But observe then that

$$(w+1)^3+(w+1)^2+1=w^3+w^2+w+1+w^2+1+1=0\implies w+1\;\;\text{is a root of}\;\;$$

$$x^3+x^2+1\in\Bbb F_2[x]$$

Finally, just check the above polynomial is irreducible over $\;\Bbb F_2\;$ and we're done.

How did I reach the above? First, the wanted minimal polynomial must be either of degree one or three, as three is a prime (and thus the field extension has no non-trivial subextensions). Second, since $\;w\not\in\Bbb F_2\;$ , its minimal polynomial must be of degree three. Third, there are very few irreducible polynomials of degree three over $\;\Bbb F_2\;$ (in fact, of any given order there are't many...) .

Answer 2

You can find an easy bound on the degree, using linear algebra. Since every power of $\overline{x+1}$ is of the form $\overline{ax^2+bx+c}$, $\left(\overline{x+1}\right)^3$ will have to be spanned by $1,\overline{1+x},\left(\overline{1+x}\right)^2$. So its degree is at most $3$.

A method to find the minimal polynomial: write $\left(\overline{1+x}\right)^i$ for $i=0,1,2,3$, and search for linear dependence.

Here, $\left(\overline{1+x}\right)^2=\overline{1+x^2}$, and $\left(\overline{1+x}\right)^3=\overline{1+x+x^2+x^3}=\overline{x^2}$. So the minimal polynomial is $f(t)=t^3+t^2+\overline{1}$. Indeed,

$$\left(\overline{1+x}\right)^3+\left(\overline{1+x}\right)^2+\overline{1}=\overline{x^2}+\overline{x^2+1}+\overline{1}=\overline{0}$$

Answer 3

First of all, since $\mathbb{F}_2(\overline{x+1})=\mathbb{F}_2(\bar{x}) = \Bbb F_2[x]/(x^3+x+1)$, its minimal polynomial must have degree $3$. So one way of doing this is to compute $\overline{x+1}^2$ and $\overline{x+1}^3$ and then try to find a linear combination of $\bar1$, $\overline{x+1}$, $\overline{x+1}^2$ and $\overline{x+1}^3$ that is zero.

There is, however, another method. Denote $\varphi : K\to K:a\mapsto a^2$ the Frobenius automorphism. Then $\phi$ fixes $\mathbb{F}_2$, so it permutes the roots of the minimal polynomial. Hence these roots must be $\overline{x+1}$, $\varphi(\overline{x+1})$ and $\varphi^2(\overline{x+1})$. Hence the minimal polynomial is $$(t-(\overline{x+1}))(t-\varphi(\overline{x+1}))(t-\varphi^2(\overline{x+1}))=(t-(\overline{x+1}))(t-(\overline{x+1})^2)(t-(\overline{x+1})^4).$$ Now you just have to expand this factorization.

Answer 4

In general, if $K=k(w)$ and $\text{Irr}(w,k[X])=f(X)$, then $\text{Irr}(w+1,k[X])=f(X-1)$.

In this case, you plug $X-1$ into $X^3+X+1$ to get $X^3+X^2+1$.