Group 3

From LeicesterIPSC
Jump to: navigation, search


Our Polynomial

[math]f(x)=x^{4}-20x^{2}+16[/math]

We know that [math]\alpha=\sqrt{3}+\sqrt{7}[/math] is a root in [math]{\mathbb C}[/math] and as [math]\alpha\in{\mathbb R}[/math] that [math]\alpha[/math] is a root in [math]{\mathbb R}[/math]

Factorise [math]f(x)[/math]

Over [math]{\mathbb Q}[/math]

Firstly we looked to see if our polynomial is irreducible over [math]{\mathbb Q}[/math] using "Eisenstein's criterion". For this to work we want a prime [math]p[/math] that divides [math]16[/math] and [math]20[/math] but does not divide [math]1[/math] and also [math]p^{2}[/math] does not divide [math]16[/math]. The only prime number that divides [math]16[/math] and [math]20[/math] is [math]2[/math]. However, [math]2^{2} = 4[/math] divides [math]16[/math] so we cannot apply Eisenstein's to show the function is irreducible over [math]{\mathbb Q}[/math].

For [math]f(x)[/math] to be reducible, we need to find a polynomial [math]g(x)[/math] and a polynomial [math]h(x)[/math] such that [math]f(x)=g(x)h(x)[/math] and [math]deg(g(x))[/math]and [math]deg(h(x))\neq 0[/math]. When know that the [math]deg( f(x))=4[/math] and that [math]deg (f(x))=deg (g(x)) + deg (h(x))[/math]. So we can assume without loss of generality that for [math]f(x)[/math] to be reducible in [math]{\mathbb Q}[/math] then the [math]deg(g(x))=1[/math] or [math]2[/math] and [math]deg(h(x))= 3[/math] or [math]2[/math]. If [math]deg(g(x))=1[/math], then we know that [math]f(x)[/math] has a root in [math]{\mathbb Q}[/math].

So to disprove this, we need to show that [math]f(x)[/math] has no linear roots in [math]{\mathbb Q}[/math], to do this we will use the "root test" (also known as the rational root theorem). In this example [math]k|16[/math] and [math]l|1[/math] so the possibilities for roots are [math]k/l=\pm1, \pm2, \pm4, \pm8, \pm16[/math]

So we then have to evaluate [math]f(x)[/math] for each of the possible values for [math]k/l[/math].

[math]k/l[/math] [math]f(k/l)[/math]
[math]\pm1[/math] -3
[math]\pm2[/math] -48
[math]\pm4[/math] -48
[math]\pm8[/math] 2832
[math]\pm16[/math] 60432

As none of these values are equal to [math]0[/math] there is no linear factor.

We have shown that there is no linear factor when factorising over [math]{\mathbb Q}[/math]. We now want to see whether our polynomial [math]f(x)=x^{4}-20x^{2}+16[/math] factorises into two polynomials in [math]{\mathbb Q}[/math] both of degree [math]2[/math].

[math]x^{4}-20x^{2}+16=(x^{2}+ax+b)(x^{2}+cx+d)[/math] with [math]a,b,c,d\in {\mathbb Q} [/math].

Multiplying out we get [math]x^{4}+(a+c)x^{3}+(b+ac+d)x^{2}+(cb+ad)x+bd[/math] this leaves us with four conditions to satisfy. These are:

  • [math]1)[/math] [math]a+c=0[/math]
  • [math]2)[/math] [math]b+ac+d=-20[/math]
  • [math]3)[/math] [math]bc+ad=0[/math]
  • [math]4)[/math] [math]bd=16[/math]

These four conditions lead to two cases:

  • Case [math]1.[/math] [math]c=0 \Rightarrow a=0[/math]
  • Case [math]2.[/math] [math]c\neq 0 \Rightarrow b-d=0 \Rightarrow b=d[/math]


Case [math]1:[/math]

If [math]a=0[/math]

[math]a=-c=0[/math]

[math]b+d=-20[/math]

[math]b=-20-d[/math]

[math]\Rightarrow (-20-d)d=16[/math]

[math]-20d-d^{2}=16[/math]

[math]d^{2}+20d+16=0[/math]

[math]\Rightarrow[/math] [math]d = \frac {-20 \pm \sqrt{400 - 64}}{2}[/math] [math]=\frac{-20 \pm 4\sqrt{21}}{2}[/math] [math]=-10\pm 2\sqrt{21}[/math]


This leads to a contradiction as there are no solutions to this equation that are elements in [math]{\mathbb Q}[/math].


Case [math]2:[/math]

If [math]d-b=0[/math]

[math]\Rightarrow b=d[/math]

[math]-a^{2}+2b=-20[/math]

[math]b^{2}=16 \Rightarrow b=\pm4[/math]

[math]a^{2}=2b+20[/math]

If [math]b=-4[/math] then [math]a^{2}=12[/math] [math]\Rightarrow[/math] [math]a=\pm \sqrt{12}[/math]

If [math]b=4[/math] then [math]a^{2}=28[/math] [math]\Rightarrow[/math] [math]a=\pm \sqrt{28}[/math]


This again leads to a contradiction as neither values of [math]a[/math] are elements in [math]{\mathbb Q}[/math].

So [math]f(x)[/math] can't be reduced in [math]{\mathbb Q}[/math]. This is due to the fact that it does not have any linear factors and does not factorise into [math]2[/math] polynomials [math]f(x)[/math] and [math]g(x)[/math] both of degree [math]2[/math].

Over [math]{\mathbb R}[/math] and [math]{\mathbb C}[/math]

After "polynomial division" ie, dividing [math]f(x)[/math] by [math] x-\sqrt{3}-\sqrt{7}[/math] we get [math] x^{3}+(\sqrt{3}+\sqrt{7})x^{2}+(-10+2\sqrt{21})x+4\sqrt{7}-4\sqrt{3}[/math] and so [math]f(x)=x^{4}-20x^{2}+16[/math] is reducible in [math]{\mathbb R}[/math] and [math]{\mathbb C}[/math]. This shows that a linear factor exists in [math]{\mathbb R}[/math], but we want to see if we can reduce it further. After showing that our root is a linear factor, naturally we looked to see if [math]x +\sqrt{3} +\sqrt{7}[/math] was also a root.

After another "polynomial division" dividing by [math]x +\sqrt{3} +\sqrt{7}[/math]. This left us with a quadratic [math]x^{2} - 10 +2\sqrt{21} [/math]. We then used the quadratic formula to find the remaining two roots of the equation:

[math]\frac {-b\pm\sqrt{b^{2}-4ac}}{2a}=\frac {-0\pm\sqrt{0^{2}-4(-10+2\sqrt{21})}}{2}[/math]
[math] = \pm\sqrt{10-2\sqrt{21}}[/math]

Hence, we have shown that our polynomial [math]f(x)[/math] is reducible over [math]{\mathbb R}[/math] and therefore reducible over [math]{\mathbb C }[/math]. We can express [math]f(x)[/math] in the following form:

[math]f(x) = (x-\sqrt{3}-\sqrt{7})(x+\sqrt{3}+\sqrt{7})(x+\sqrt{10-2\sqrt{21}})(x-\sqrt{10-2\sqrt{21}})[/math]

The above shows the factorisation of [math]f(x)[/math] as a product of irreducible polynomials over [math]{\mathbb R}[/math]. This is also the same factorisation over [math]{\mathbb C }[/math].

Reducible over [math]{\mathbb Z}_{p}[/math]

We are interested in whether our function [math]f(x)=x^{4}-20x^{2}+16[/math] is irreducible over [math]{\mathbb Z}_{p}[/math] and reducible over [math]{\mathbb Z}_{q}[/math] where [math]p,q[/math] are prime integers. In order to find out we use the root test starting for [math]p=2[/math] :

[math]x[/math] [math]f(x)[/math] [math]f(x)\in{\mathbb Z}_{2} [/math]
0 16 0
1 -3 1

As we can see from the table above the function has a root ([math]f(0)=0[/math]) in [math]{\mathbb Z}_{2}[/math] . Therefore [math]{\mathbb Z}_{q}[/math] is reducible for the prime [math]q=2[/math]. Next we do the same for [math]p=3[/math]:

[math]x[/math] [math]f(x)[/math] [math]f(x)\in{\mathbb Z}_{3} [/math]
0 16 1
1 -3 0
2 -48 0

This time we can see that the function has a root in [math]{\mathbb Z}_{3}[/math] . However, we are looking for a prime that the function is irreducible over. Next [math]p=5[/math]:

[math]x[/math] [math]f(x)[/math] [math]f(x)\in{\mathbb Z}_{5} [/math]
0 16 1
1 -3 2
2 -48 2
3 -83 2
4 -48 2

On this occasion we see that [math]f(x)[/math] does not have a root in [math]{\mathbb Z}_{5}[/math] . Thus the primes we were looking for are [math]p=5[/math] and [math]q=2[/math] or [math]q=3[/math] for [math]f(x)[/math] irreducible over [math]{\mathbb Z}_{p}[/math] and reducible over [math]{\mathbb Z}_{q}[/math].

Using [math]f(x)[/math] constructing a field [math]E[/math] of the form [math]{\mathbb Q}[x]/I[/math] for some ideal [math]I[/math]

We know that [math]f(x)[/math] is irreducible over [math]{\mathbb Q}[x][/math] and hence we know that [math](f(x))[/math] is a maximal ideal of [math]{\mathbb Q}[x][/math].

Looking at our field [math]E[/math] which equals:

[math]{\mathbb Q}[x]/(x^{4}-20x^{2}+16)[/math]

Now if we let [math]\theta=x+I[/math] where [math]\theta\in {\mathbb Q}[x]/I[/math]. Then [math]f(\theta)=0 \Rightarrow \theta^{4}-20\theta^{2}+16=0[/math] so [math]\theta^{4}=20\theta^{2}-16[/math].

We can write any polynomial of [math]\theta[/math] in the form

[math]a+b\theta+c\theta^{2}+d\theta^{3}[/math]

i.e. with the basis {[math]{1,\theta,\theta^{2},\theta^{3}}[/math]} and hence the [math]dim_{\mathbb Q}(E)=4[/math]

We then wanted to see how calculations work within this field [math]E[/math]. We already know [math]x^{4}+I=20x^{2}-16+I[/math] and we know wanted to calculate [math]\theta^{5}[/math], these are the following calculations required to calculate [math]\theta^{5}:[/math]

[math]\theta^{5}=\theta^{4}\theta[/math]
[math]=(x^{4}+I)(x+I)[/math]
[math]=(20x^{2}-16+I)(x+I)[/math]
[math]=20x^{3}-16x+I[/math]

Contructing a field with finite elements using [math]f(x)[/math]

To construct a field with size [math]5^{4}=625[/math], we start with our polynomial [math]f(x)=x^{4}-20x^{2}+16[/math] which we have already shown is irreducible in [math]{\mathbb Z}_{5}[/math] then a field with [math]625[/math] elements is given by:

[math]{\mathbb Z}_{5}[x]/( x^{4}-20x^{2}+16) [/math]

Its elements have the form [math]ax^{3}+bx^{2}+cx+d[/math] where [math]a,b,c[/math] and [math]d\in {\mathbb Z}_{5}[/math] and the multiplication is defined by [math]x^{4}-20x^{2}+16=0[/math], or by rearranging [math]x^{4}=4[/math].

Algebraic Elements of [math]f(x)[/math]

[math]\alpha=\sqrt{3}+\sqrt{7}[/math]
[math]\alpha^{2}=(\sqrt{3}+\sqrt{7})^{2}=10+2\sqrt{21}[/math]
[math]\alpha^{2}-10=2\sqrt{21}[/math]
[math](\alpha^{2}-10)^{2}=(2\sqrt{21})^{2}[/math]
[math]\alpha^{4}-20\alpha^{2}+100=84[/math]
[math]\alpha^{4}-20\alpha^{2}+16=0[/math]

[math]\Rightarrow f(\alpha)=0[/math]

[math]f(x)\in{\mathbb Q}[x]\Rightarrow\alpha[/math] is an algebraic number

[math]\Rightarrow {\mathbb R}\supseteq{\mathbb Q}[/math] is a field extension and [math]\alpha\in{\mathbb R}[/math] is algebraic over [math]{\mathbb Q}[/math]

[math]\Rightarrow[/math] Our field is [math]{\mathbb Q}[/math].

Hence for our field [math]{\mathbb Q}[/math] and polynomial [math]f(x)[/math] we have that this polynomial is the "minimal polynomial" of [math]\alpha[/math] over [math]{\mathbb Q}[/math].

References

http://en.wikipedia.org/wiki/Finite_field

http://en.wikipedia.org/wiki/Root_test

http://en.wikipedia.org/wiki/Polynomial_long_division

http://en.wikipedia.org/wiki/Minimal_polynomial_(field_theory)

http://en.wikipedia.org/wiki/Eisenstein's_criterion