FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Finite fields and Splitting fields
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
Author Message
vedmundson@hotmail.com
science forum beginner


Joined: 20 Jul 2006
Posts: 1

PostPosted: Thu Jul 20, 2006 6:35 pm    Post subject: Finite fields and Splitting fields Reply with 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)
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.
Back to top
mariano.suarezalvarez@gma
science forum addict


Joined: 28 Apr 2006
Posts: 58

PostPosted: Thu Jul 20, 2006 6:57 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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
Back to top
Arturo Magidin
science forum Guru


Joined: 25 Mar 2005
Posts: 1838

PostPosted: Thu Jul 20, 2006 7:14 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

In article <1153420512.579184.318810@m73g2000cwd.googlegroups.com>,
<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
Back to top
W. Dale Hall
science forum Guru


Joined: 29 Apr 2005
Posts: 350

PostPosted: Thu Jul 20, 2006 7:41 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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.
Back to top
W. Dale Hall
science forum Guru


Joined: 29 Apr 2005
Posts: 350

PostPosted: Thu Jul 20, 2006 7:45 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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.
Back to top
Arturo Magidin
science forum Guru


Joined: 25 Mar 2005
Posts: 1838

PostPosted: Thu Jul 20, 2006 7:46 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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]/<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).

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
Back to top
W. Dale Hall
science forum Guru


Joined: 29 Apr 2005
Posts: 350

PostPosted: Thu Jul 20, 2006 7:51 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

Arturo Magidin wrote:
Quote:
In article <l%Qvg.174711$F_3.59602@newssvr29.news.prodigy.net>,
W. Dale Hall <mailtodhall@farir.com> 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]/<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).


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. (-:


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.
Back to top
W. Dale Hall
science forum Guru


Joined: 29 Apr 2005
Posts: 350

PostPosted: Thu Jul 20, 2006 8:08 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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
Back to top
Derek Holt
science forum beginner


Joined: 14 Jan 2006
Posts: 14

PostPosted: Fri Jul 21, 2006 1:26 pm    Post subject: Re: Finite fields and Splitting fields Reply with quote

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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
The time now is Fri Oct 20, 2017 12:12 pm | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0310s ][ Queries: 16 (0.0038s) ][ GZIP on - Debug on ]