 Forum index » Science and Technology » Math
Author Message
vedmundson@hotmail.com
science forum beginner

Joined: 20 Jul 2006
Posts: 1 Posted: Thu Jul 20, 2006 6:35 pm    Post subject: Finite fields and Splitting fields How many elements are there in the splitting fields of the following
two polynomialsover GF(2)?

(a) x^3 + x^2 + x + 1

(b) x^3 + x^2 + 1.

I worked on this problem and these are both elements of GF(2^4). I'm
not entirely certain on how to solve this problem given that I've never
done it over a finite field.

Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)
and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) = x(x+1)(x+1(x+1).

I believe that I am doing this right, at least. In any case, I would
greatly appreciate any help on this problem. mariano.suarezalvarez@gma

Joined: 28 Apr 2006
Posts: 58 Posted: Thu Jul 20, 2006 6:57 pm    Post subject: Re: Finite fields and Splitting fields vedmundson@hotmail.com wrote:
 Quote: How many elements are there in the splitting fields of the following two polynomialsover GF(2)? (a) x^3 + x^2 + x + 1 (b) x^3 + x^2 + 1.

Are they irreducible over GF(2)? What is the relation between
the degree of a polynomial and the degree of its splitting field
as an extension of GF(2)? What is the relation between the degree
of an finite extension of GF(2) and its cardinality?

 Quote: I worked on this problem and these are both elements of GF(2^4). I'm not entirely certain on how to solve this problem given that I've never done it over a finite field. Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1) and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) = x(x+1)(x+1(x+1).

Hmm.

You probably mean that over *GF(2)* one has

x^3+x^2+x^2+1 = (1+x)^3.

Can you see what the splitting field of
x^3+x^2+x^2+1 is with this information?

-- m Arturo Magidin
science forum Guru

Joined: 25 Mar 2005
Posts: 1838 Posted: Thu Jul 20, 2006 7:14 pm    Post subject: Re: Finite fields and Splitting fields <vedmundson@hotmail.com> wrote:
 Quote: How many elements are there in the splitting fields of the following two polynomialsover GF(2)? (a) x^3 + x^2 + x + 1 (b) x^3 + x^2 + 1. I worked on this problem and these are both elements of GF(2^4). I'm not entirely certain on how to solve this problem given that I've never done it over a finite field. Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1)

This is wrong. (x^2+1)(x+1) = x^3+x^2+x+1, not x^3+x^2+1. (Had your
factorization been correct, it would have shown the factorization can
be done over GF(2) itself, no need to go to GF(2^4).

 Quote: and x^3 + x^2 + 1 = (x^2 + x)(x^2+1)

Again, this is wrong. You have

(x^2+x)(x^2+1) = x^4 + x^3 + x^2 + x, not x^3+x^2+1. Had your
factorization been correct, it would have shown that the polynomial
splits over GF(2).

 Quote: I believe that I am doing this right, at least.

Alas, no.

 Quote: In any case, I would greatly appreciate any help on this problem.

Okay. Let's take x^3+x^2+1. This is irreducible over GF(2), since it
has no roots and is degree 3 (any factorization would necessarily
involve a linear factor). Letting F = GF(2), let u be a root of
x^3+x^2+1 taken in some fixed algebraic closure, and let K=F(u); then
[K:F]=3, which means that K must be GF(2^3). The question is whether
the polynomial splits over K, or if you must take a further
extension. If it splits over K, then you are done. If not, then the
polynomial must factor as (x-u)g(x), where g(x) is an irreducible
quadratic, so the splitting field must be of degree 2 over K, and
therefore of degree 6 over F, meaning it will be GF(2^6). So the only
possibilities are that the splitting field of x^3+x^2+1 is degree 3
over F, in which case it has 8 elements; or else it is degree 6, in
which case it has 64 elements.

Which one is it? We know that

x^3+x^2+1 = (x+u)g(x) for some quadratic g(x) with coefficients in
K. We just need to figure out what g is; g(x) = x^2+sx+t, and we have

x^3+x^2+1 = (x+u)(x^2+sx+t)
= x^3 + sx^2 + tx + ux^2 + usx + ut
= x^3 + (s+u)x^2 + (t+us)x + ut.

So we must have s+u = 1, t+us = 0, ut=1. Now, the elements of K can be
written uniquely in the form a+bu+cu^2, with u^3 = u^2+1. So s = 1+u,
hence 0 = t+us = t+u(1+u) = t + u + u^2, so t = u+u^2; to verify note
that u^3+u^2 = 1, hence u(u^2+u) = 1. So t = u^2+u, as before.

Indeed:

(x+u)(x^2 + (1+u)x + (u+u^2))
= x^3 + (1+u)x^2 + (u+u^2)x
+ ux^2 + (u+u^2)x + (u^2+u^3)
= x^3 + x^2 + (u^2+u^3)
= x^3 + x^2 + 1.

Now: g(x) = x^2 + (1+u)x + (u+u^2). So you just need to check if this
polynomial has a root in K. The elements of K are of the form
a+bu+cu^2, with a, b, c in GF(2). Let r = a+bu+cu^2, and evaluate
g(r). Note that u^3 = 1+u^2 and u^4 = uu^3 = u+u^3 = 1+u+u^2.
We have:

g(r) = (a+bu+cu^2)^2 + (1+u)(a+bu+cu^2) + (u+u^2)
= a^2 + bu^2 + cu^4 + a+bu+cu^2 +au + bu^2 + cu^3 + u + u^2
= (a+a) + (b + a + 1)u + (b + c + b + 1)u^2 + cu^3 + cu^4
= (1+a+b)u + (1+c)u^2 + c(1+u^2) + c(1+u+u^2)
= (1+a+b+c)u + (1+c)u^2.

If this is going to be a root, we need c+1=0 and a+b+c+1=0.

So we must have c=1 and a+b=0.Thus the two roots we get are a=b=c=1,
and a=b=0, c=1. That is, r=1+u+u^2 and r=u^2.

For example, plug in u^2 into g. We have

g(u^2) = u^4 + (1+u)u^2 + (u+u^2)
= 1+u+u^2 + u^2+u^3 + u+u^2
= 1+u+u^2 + u^2 + 1+u^2 + u + u^2
= (1+1) + (1+1)u + (1+1+1+1)u^2 = 0.

Thus, g(x) has both roots in K already, so the splitting field of
x^3+x^2+1 is just K; hence it is degree 3 over F, and so has 8
elements.

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin W. Dale Hall
science forum Guru

Joined: 29 Apr 2005
Posts: 350 Posted: Thu Jul 20, 2006 7:41 pm    Post subject: Re: Finite fields and Splitting fields vedmundson@hotmail.com wrote:
 Quote: How many elements are there in the splitting fields of the following two polynomialsover GF(2)? (a) x^3 + x^2 + x + 1

This polynomial already splits into linear factors over GF(2):

Note that over the integers, we have this:

(x + 1)^3 = x^3 + 3x^2 + 3x + 1

and reducing mod 2, it becomes this

(x + 1)^3 = x^3 + x^2 + x + 1 (mod 2)

Alternatively, you could write (again over Z)

x^3 + x^2 + x + 1 = (x^2 + 1)(x + 1)

and use the fact that over GF(2), x^2 + 1 = (x + 1)^2:

(x + 1)^3 = x^3 + x^2 + x + 1 (mod 2)

 Quote: (b) x^3 + x^2 + 1. I worked on this problem and these are both elements of GF(2^4).

What do you mean? You've written polynomials over GF(2). They're
polynomials, not elements of some extension field. You could, I
suppose reduce them modulo some irreducible quartic polynomial
to map them to GF(2^4), but that doesn't solve any problem that
I can see.

 Quote: I'm not entirely certain on how to solve this problem given that I've never done it over a finite field. Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1) unbalanced parentheses^^^ and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) = x(x+1)(x^2+1) = x(x+1)(x+1(x+1).

How do you get that? This factorization works for the first
polynomial (see earlier section of article), but simply
multiplying it out (over Z) you get this:

(x^2 + 1)(x + 1) = x^3 + x^2 + x + 1

and you don't get to throw the linear term out just because
you have GF(2) coefficients, so this (which is your polynomial
from the first example) isn't actually the polynomial you wish
to be working with.

Note that if a cubic polynomial factors, it must factor into
the product of a linear factor by a quadratic factor. Linear
factors are easy to spot: they correspond to roots of your
original polynomial.

In fact, the polynomial

P(x) = x^3 + x^2 + 1

doesn't have any roots in GF(2):

x P(x)

0 1
1 1

Since it's a cubic, the fact that it has no roots implies
that it is irreducible. You can introduce a single root by
passing to the field GF(2^3), expressible as the quotient

GF(2^3) ~ GF(2)[x]/<P(x)>

where you take all polynomials over GF(2) and impose the
identity P(x) = 0, which amounts to imposing the condition
that x^3 = x^2 + 1.

This field has 8 elements, of course, and the polynomial
then splits into atleast a linear * quadratic. The question
arises as to whether that quadratic also splits. A quick
bit of pencil/paper work shows that the quadratic factor
is this

Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)

where alpha is the name of the root of P(x) added to GF(2)
to form GF(2^3), and a bit more work shows Q(x) doesn't have
any roots in GF(2^3).

Then, to get your splitting field, you need to take one
more quadratic extension, using Q(x) over GF(2^3) rather
than P(x) over GF(2).

I'll leave the rest to you.
 Quote: I believe that I am doing this right, at least. In any case, I would greatly appreciate any help on this problem.

I hope this is understandable, and that it helps.

Dale. W. Dale Hall
science forum Guru

Joined: 29 Apr 2005
Posts: 350 Posted: Thu Jul 20, 2006 7:45 pm    Post subject: Re: Finite fields and Splitting fields W. Dale Hall wrote:

Some buncha stuff, leading to this:

 Quote: This field has 8 elements, of course, and the polynomial then splits into atleast a linear * quadratic. The question arises as to whether that quadratic also splits. A quick bit of pencil/paper work shows that the quadratic factor is this Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1)

Darn that paper and pencil crap, anyhow:

Q(x) = x^2 + (alpha + 1) x + (alpha^2 + alpha)

Modulo any further typos, the rest looked OK

Dale. Arturo Magidin
science forum Guru

Joined: 25 Mar 2005
Posts: 1838 Posted: Thu Jul 20, 2006 7:46 pm    Post subject: Re: Finite fields and Splitting fields In article <l%Qvg.174711\$F_3.59602@newssvr29.news.prodigy.net>,
W. Dale Hall <mailtodhall@farir.com> wrote:

Hrmph...

[.snip.]

 Quote: In fact, the polynomial P(x) = x^3 + x^2 + 1 doesn't have any roots in GF(2): x P(x) 0 1 1 1 Since it's a cubic, the fact that it has no roots implies that it is irreducible. You can introduce a single root by passing to the field GF(2^3), expressible as the quotient GF(2^3) ~ GF(2)[x]/

At least one of us has made a mistake, since I think I found that the
polynomial does split in GF(2^3). Hrmph.

Of course, it could be that we both made mistakes; but at least I can
rest assured that one of us is correct in our assertion. (-:

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin W. Dale Hall
science forum Guru

Joined: 29 Apr 2005
Posts: 350 Posted: Thu Jul 20, 2006 7:51 pm    Post subject: Re: Finite fields and Splitting fields Arturo Magidin wrote:
 Quote: In article , W. Dale Hall wrote: Hrmph... [.snip.] In fact, the polynomial P(x) = x^3 + x^2 + 1 doesn't have any roots in GF(2): x P(x) 0 1 1 1 Since it's a cubic, the fact that it has no roots implies that it is irreducible. You can introduce a single root by passing to the field GF(2^3), expressible as the quotient GF(2^3) ~ GF(2)[x]/

My mistake. I made a mistake in computation of Q(x). I compounded it
by not repeating the calculation of Q(x) for all values of x in
GF(2^3), and so didn't correct my (now mistaken?) claim that the
polynomial didn't have its roots in GF(2^3). Rather than leave a
potential error hanging in the breeze, I'll go back and do the
calculation with the correct version of Q(x).

Since your value for g(x) is correct (and my follow-up to my original
reply to the OP contains that as the corrected value of Q(x)), I expect
that my next step will simply confirm your solution.

Dale. W. Dale Hall
science forum Guru

Joined: 29 Apr 2005
Posts: 350 Posted: Thu Jul 20, 2006 8:08 pm    Post subject: Re: Finite fields and Splitting fields W. Dale Hall wrote:
 Quote: W. Dale Hall wrote: Some buncha stuff, leading to this: This field has 8 elements, of course, and the polynomial then splits into atleast a linear * quadratic. The question arises as to whether that quadratic also splits. A quick bit of pencil/paper work shows that the quadratic factor is this Q(x) = x^2 + (alpha + 1) x + (alpha^2 + 1) Darn that paper and pencil crap, anyhow: Q(x) = x^2 + (alpha + 1) x + (alpha^2 + alpha) Modulo any further typos, the rest looked OK Dale.

I suppose not. Arturo Magidin's article showed this
new and improved quadratic factor does have roots in GF(2^3).
Here they are:

alpha^2, alpha^2 + alpha + 1

where alpha is the root of the linear factor that split off
when going from GF(2) to GF(2^3).

As Arturo indicated, the quadratic *does* split in GF(2^3),
so that is indeed the splitting field.

The lesson I learn, of course, is that I should proofread,
and proofread again. Not to mention repeat computations
when the data changes.

Duh.

Dale Derek Holt
science forum beginner

Joined: 14 Jan 2006
Posts: 14 Posted: Fri Jul 21, 2006 1:26 pm    Post subject: Re: Finite fields and Splitting fields Arturo Magidin wrote:
 Quote: In article <1153420512.579184.318810@m73g2000cwd.googlegroups.com>, vedmundson@hotmail.com> wrote: How many elements are there in the splitting fields of the following two polynomialsover GF(2)? (a) x^3 + x^2 + x + 1 (b) x^3 + x^2 + 1. I worked on this problem and these are both elements of GF(2^4). I'm not entirely certain on how to solve this problem given that I've never done it over a finite field. Over GF(2^4), x^3 + x^2 + 1 = (x^2+1)(x+1) = (x+1)(x+1(x+1) This is wrong. (x^2+1)(x+1) = x^3+x^2+x+1, not x^3+x^2+1. (Had your factorization been correct, it would have shown the factorization can be done over GF(2) itself, no need to go to GF(2^4). and x^3 + x^2 + 1 = (x^2 + x)(x^2+1) Again, this is wrong. You have (x^2+x)(x^2+1) = x^4 + x^3 + x^2 + x, not x^3+x^2+1. Had your factorization been correct, it would have shown that the polynomial splits over GF(2). I believe that I am doing this right, at least. Alas, no. In any case, I would greatly appreciate any help on this problem. Okay. Let's take x^3+x^2+1. This is irreducible over GF(2), since it has no roots and is degree 3 (any factorization would necessarily involve a linear factor). Letting F = GF(2), let u be a root of x^3+x^2+1 taken in some fixed algebraic closure, and let K=F(u); then [K:F]=3, which means that K must be GF(2^3). The question is whether the polynomial splits over K, or if you must take a further extension. If it splits over K, then you are done. If not, then the polynomial must factor as (x-u)g(x), where g(x) is an irreducible quadratic, so the splitting field must be of degree 2 over K, and therefore of degree 6 over F, meaning it will be GF(2^6). So the only possibilities are that the splitting field of x^3+x^2+1 is degree 3 over F, in which case it has 8 elements; or else it is degree 6, in which case it has 64 elements. Which one is it? We know that

Rather than carry out a detailed calculation, it is probably preferable
at this stage to make use of the general result that, if F = GF(q) is
any finite field and p is an irreducible polynomial of degree n
over F, then the splitting field of p has degree n over F. This
follows easily from the fact that there is a unique finite field of any
given prime power order, because adjoining any of the n roots of p
to F must result in the same extension field GF(q^n).

Derek Holt.

 Quote: x^3+x^2+1 = (x+u)g(x) for some quadratic g(x) with coefficients in K. We just need to figure out what g is; g(x) = x^2+sx+t, and we have x^3+x^2+1 = (x+u)(x^2+sx+t) = x^3 + sx^2 + tx + ux^2 + usx + ut = x^3 + (s+u)x^2 + (t+us)x + ut. So we must have s+u = 1, t+us = 0, ut=1. Now, the elements of K can be written uniquely in the form a+bu+cu^2, with u^3 = u^2+1. So s = 1+u, hence 0 = t+us = t+u(1+u) = t + u + u^2, so t = u+u^2; to verify note that u^3+u^2 = 1, hence u(u^2+u) = 1. So t = u^2+u, as before. Indeed: (x+u)(x^2 + (1+u)x + (u+u^2)) = x^3 + (1+u)x^2 + (u+u^2)x + ux^2 + (u+u^2)x + (u^2+u^3) = x^3 + x^2 + (u^2+u^3) = x^3 + x^2 + 1. Now: g(x) = x^2 + (1+u)x + (u+u^2). So you just need to check if this polynomial has a root in K. The elements of K are of the form a+bu+cu^2, with a, b, c in GF(2). Let r = a+bu+cu^2, and evaluate g(r). Note that u^3 = 1+u^2 and u^4 = uu^3 = u+u^3 = 1+u+u^2. We have: g(r) = (a+bu+cu^2)^2 + (1+u)(a+bu+cu^2) + (u+u^2) = a^2 + bu^2 + cu^4 + a+bu+cu^2 +au + bu^2 + cu^3 + u + u^2 = (a+a) + (b + a + 1)u + (b + c + b + 1)u^2 + cu^3 + cu^4 = (1+a+b)u + (1+c)u^2 + c(1+u^2) + c(1+u+u^2) = (1+a+b+c)u + (1+c)u^2. If this is going to be a root, we need c+1=0 and a+b+c+1=0. So we must have c=1 and a+b=0.Thus the two roots we get are a=b=c=1, and a=b=0, c=1. That is, r=1+u+u^2 and r=u^2. For example, plug in u^2 into g. We have g(u^2) = u^4 + (1+u)u^2 + (u+u^2) = 1+u+u^2 + u^2+u^3 + u+u^2 = 1+u+u^2 + u^2 + 1+u^2 + u + u^2 = (1+1) + (1+1)u + (1+1+1+1)u^2 = 0. Thus, g(x) has both roots in K already, so the splitting field of x^3+x^2+1 is just K; hence it is degree 3 over F, and so has 8 elements. -- ====================================================================== "It's not denial. I'm just very selective about what I accept as reality." --- Calvin ("Calvin and Hobbes" by Bill Watterson) ====================================================================== Arturo Magidin  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 The time now is Sat Mar 23, 2019 10:25 am | All times are GMT Forum index » Science and Technology » Math
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Choice function over finite sets Peter Webb Math 5 Fri Jul 21, 2006 3:28 am Finite # of subgroups -> Finite group tppytel@gmail.com Undergraduate 9 Sun Jul 16, 2006 1:47 am Finite cyclic semigroups David1132 Math 0 Sat Jul 15, 2006 9:37 am Need help with finite series! my7x57@realguns.com Math 17 Mon Jul 10, 2006 4:49 pm FLT in other fields Bart Goddard Math 0 Wed Jul 05, 2006 4:43 pm