Irreducible polynomial over finite field

[Zoe-b]

Homework Statement

Factor x^16-x over the fields F₄ and F₈

Homework Equations

factored over Z (or Q), x^16-x = (x*(x - 1)*(x^2 + x + 1)*(x^4 + x^3 + x^2 + x + 1)*(x^8 - x^7 + x^5 - x^4 + x^3 - x + 1)

The Attempt at a Solution

I know the that quadratic and higher terms I have left do not have any linear factors.. I'm obviously missing something. But even with that I'm not really sure how to start checking- I *think* I'm right in saying I can check for irreducibility over F₂ first, because that would be implied by irreducibility over the larger field. Then there are less polynomials to check, but still a fair few for the term of degree 8..

Thanks in advance :)

 

[Hurkyl]

Try factoring over F₁₆ first.

 

[Zoe-b]

Ok.. so x^16-x splits completely over F(16) because the non-zero elements form a multiplicative group and each element a satisfies a^16= a
My problem now is that I really have very little concept of how the fields F(16) and F(8) are related to each other- for a while after starting this question I was thinking of them as being integers modulo 16 (or 8 respectively) but this is clearly wrong. How can I factor it into something with coefficients in F(4) without knowing how the elements of F(4) interact...?

 

[I like Serena]

As far as I can tell F₈ and F₁₆ are unrelated.
That is, there is no homomorphism that maps one onto another, since the orders of the respective multiplicative groups do not divide each other (being respectively 7 and 15).

So I'm very interested in what Hurkyl intended.


I was able to factorize the 8th degree polynomial into 4th degree polynomials by setting (in either F₄[x] or F₈[x]):
$$x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 = (x^4 + ax^3 + bx^2 + cx + 1)(x^4 + (a+1)x^3 + b^{-1} x^2 + (c+1)x + 1)$$

This is solvable in F4 and also in F8.
After that I could repeat the process with 2nd degree polynomials (with the last coefficient unequal to 1 btw).

 

[Zoe-b]

Well F(16) is useful for F(4)- I think because 4=2^2 , 16= 2^4 and 2 divides 4. Clearly 3 does not divide 4 so I'm struggling to see the relevance to F(8). I've now done it (I think!) for F(4), the polynomial splits completely into linear factors, each repeated 4 times. These are precisely the roots of x^4 - x, but (x^4-x)^4 gives x^16-x. This is dependent on being able to equate x^4 with x in F(4) but I think this is valid since every element of F(4) satisfies this equation.

F(8) has no linear factors other than 0,1 though so still a bit stuck..

 

[I like Serena]

I just checked and I can find no mapping of F16 to F4 that retains the field structure (adding as well as multiplication), so I do not see how factorization in F16 would help.

 

[Zoe-b]

Its not a mapping- F(4) is contained within F(16), no?

 

[I like Serena]

The elements are contained, but the multiplication and addition tables are different.

 

[Hurkyl]

I Like Serena: The subset of $\mathbb{F}_{16}$ of solutions to $x^4 - x$ form a subfield of $\mathbb{F}_{16}$. Since it has 4 elements it must be (isomorphic to) $\mathbb{F}_{4}$. In the language of Galois theory, $x \mapsto x^4$ is a field automorphism of $\mathbb{F}_{16}$. $\mathbb{F}_{4}$ is (isomorphic) to its fixed field.

If $\alpha$ and $\beta$ are primitive elements (over $\mathbb{F}_{2}$) of $\mathbb{F}_{4}$ and $\mathbb{F}_{16}$, then send $\alpha \mapsto \beta^5$ (or to $\beta^{10}$)

My problem now is that I really have very little concept of how the fields F(16) and F(8) are related to each other-

They don't much.

$\mathbb{F}_{16}$ consists of 2 elements of degree 1, 2 elements of degree 2, and 12 elements of degree 4 (over $\mathbb{F}_{2}$.

$\mathbb{F}_{8}$ consists of 2 elements of degree 1 and 6 elements of degree 3.

How do I know these facts? Because I know all of their subfields. The calculation would be a little more involved for, say, $\mathbb{F}_{64}$, but still a straightforward combinatorial exercise.


Since gcd(3,4) = 1, every element of $\mathbb{F}_{16}$ of degree 4 over $\mathbb{F}_{2}$ must also be degree 4 over $\mathbb{F}_{8}$. (of course, that same element would be degree 2 over $\mathbb{F}_{4}$)


There are various equivalent descriptions of $\alpha$ being degree n over $\mathbb{F}_{q}$:

• $\mathbb{F}_{q}(\alpha) \cong \mathbb{F}_{q^n}$
• The minimal polynomial of $\alpha$ over $\mathbb{F}_{q}$ has degree n
• The orbit of $\alpha$ under $x \mapsto x^q$ (i.e. the set $\{ \alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}, \cdots \}$) has n elements. (and these are the roots of the aforementioned minimal polynomial)

Just knowing the degrees of the roots (and that they're distinct) over $\mathbb{F}_2$ tells me that the irreducible factorization (over $\mathbb{F}_2$) is

$x^{16} - x$ = <linear> <linear> <quadratic> <quartic> <quartic> <quartic>​

In fact, if I have a model of $\mathbb{F}_{16}$ and know an algorithm for computing minimal polynomials, I could use it to actually compute the factors.

 

[I like Serena]

I Like Serena: The subset of $\mathbb{F}_{16}$ of solutions to $x^4 - x$ form a subfield of $\mathbb{F}_{16}$. Since it has 4 elements it must be (isomorphic to) $\mathbb{F}_{4}$. In the language of Galois theory, $x \mapsto x^4$ is a field automorphism of $\mathbb{F}_{16}$. $\mathbb{F}_{4}$ is (isomorphic) to its fixed field.

If $\alpha$ and $\beta$ are primitive elements (over $\mathbb{F}_{2}$) of $\mathbb{F}_{4}$ and $\mathbb{F}_{16}$, then send $\alpha \mapsto \beta^5$ (or to $\beta^{10}$)

I see! :)
A subfield.

So we can factorize $x^{16}-x$ into first degree polynomials with each of the elements of F₁₆.
And by selecting smart combinations of 2 factors, we can find quadratic ones in F₄.
Nice!

But if I see it correctly, this does not work with F₈.
F₁₆ does not seem to have a subfield that is isomorphic with F₈.

$\mathbb{F}_{16}$ consists of 2 elements of degree 1, 2 elements of degree 2, and 12 elements of degree 4 (over $\mathbb{F}_{2}$.

$\mathbb{F}_{8}$ consists of 2 elements of degree 1 and 6 elements of degree 3.

This I don't get.

I thought the multiplicative degrees of the 2 non-identity elements in F₄ would be 3.
In F₈ the (multiplicative) degrees of the 6 non-identity elements would be 7.
And F₁₆ would have 2 elements of order 3, 4 elements of order 5, and 8 elements of order 15.

The additive degrees of all non-identity elements would be 2 in each of the fields.

How are you counting this?

 

[Hurkyl]

How are you counting this?

I did give a list of things equivalent to what I mean by degree.

(p.s. I've never heard the concept you described called "degree". I usually hear it called the "order" of an (group) element)

(p.p.s. if you need to think in terms of subfields, you can use $\mathbb{F}_{2^{12}}$, which contains both $\mathbb{F}_{8}$ and $\mathbb{F}_{16}$)

 

[I like Serena]

I did give a list of things equivalent to what I mean by degree.

(p.s. I've never heard the concept you described called "degree". I usually hear it called the "order" of an (group) element)

(p.p.s. if you need to think in terms of subfields, you can use $\mathbb{F}_{2^{12}}$, which contains both $\mathbb{F}_{8}$ and $\mathbb{F}_{16}$)

Yeah well, I did not understand everything you wrote, so I just started at the beginning.
And you caught me - English is not my native language and in my language there is no distinction between the words degree and order.

But what do you mean by degree then? Do you mean the degree of polynomials?

As I understand it F₈ is isomorphic with $(\mathbb{Z}/2\mathbb{Z})[T]/(T^3+T+1)$.
So its elements are $\{0, 1, T, T^2, T+1, T^2+T, T^2+T+1, T^2+1\}$, which can also be written as $\{0, 1, T, T^2, T^3, T^4, T^5, T^6\}$.
But the degrees of these polynomials do not appear to correspond to the degrees you mentioned.

I'm still not getting it.

 

[Hurkyl]

But what do you mean by degree then?

I mean

There are various equivalent descriptions of $\alpha$ being degree n over $\mathbb{F}_{q}$:

• $\mathbb{F}_{q}(\alpha) \cong \mathbb{F}_{q^n}$
• The minimal polynomial of $\alpha$ over $\mathbb{F}_{q}$ has degree n
• The orbit of $\alpha$ under $x \mapsto x^q$ (i.e. the set $\{ \alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}, \cdots \}$) has n elements. (and these are the roots of the aforementioned minimal polynomial)