Proving Inverses Exist in Finite Fields: A Common Challenge in Field Theory

[Palindrom]

First the easy one (I think):

Show that x⁴-22x³+1 is irreducable (is that how it's spelled?) over Q.


Now the one that's giving me a headache:

Suppose E/F, when [E:F]=2, and char(E)>2. Prove that there exists u in E, s.t. E=F(u), when u is a root of p(x)=x^2-a, for a in F.

Tried all kinds of stuff, it just won't lead me anywhere. I guess it's probably easy, but it's bothering me.

Thanks in advance!

 

[Muzza]

For the first one, use the http://planetmath.org/encyclopedia/RationalRootTheorem.html .

 

[Palindrom]

For the first one, use the http://planetmath.org/encyclopedia/RationalRootTheorem.html .

It's the first thing I thought of. Problem is, the degree of my polynomial is 4. So It's actually no good... (You still don't know that it's irreducable, only that it has no roots).

 

[Muzza]

Ah yes, that's true. Maybe this will work:

x^4 - 22x^3 + 1 can't be factored as (x - a)p(x) where p is some polynomial (which is what the rational root theorem tells us).

Suppose it could be factored like (x^2 + ax + b)(x^2 + cx + d) = x^4 - 22x^3 + 1. Expand the LHS, equate coefficients, and see what you get.

I imagine that would cover all cases.

After actually trying this myself, it appears to be much harder than I thought ;)

 

[Palindrom]

It is, It's the second thing I tried... :rofl:
Any more ideas?

 

[fourier jr]

show that Q[x] mod the ideal generated by your polynomial is a field. then the polynomial is irreducible, by the following results (they're probably in your book somewhere. i don't think they have names though):
a) an ideal A = (p(x)) in F[x] (polynomials over a field) is maximal <==> p(x) is irreducible over F
b) let R be commutative with identity & let M be an ideal of R. then M is maximal <==> R/M is a field
show that the quotient ring is a field, then (p(x)) is maximal, then the polynomial is irreducible

got to think about the second one for a bit though...

 

[Hurkyl]

The second one is easy. If [E:F] = 2, then E is generated over F by the root of a quadratic. Now, apply the quadratic formula...

 

[mathwonk]

since hurkyl has solved your problem, do you see why it is needed that charac (k) > 2? can you find a counterexample when charac(k) = 2?

 

[Palindrom]

since hurkyl has solved your problem, do you see why it is needed that charac (k) > 2? can you find a counterexample when charac(k) = 2?

Well, first of all you're going to have to tell me what a quadratic and the quadratic formula are. I don't know the terms in English, I apologize.

Second of all, your question in exactly the next question I have to solve, only it's phrased like that:
"Prove that the proposition above is incorrect, when char(E)=2".

I guess it'll screw up the quadratic formula, whatever that is.
So what is it? :uhh:

 

[matt grime]

Quadratic means degree two poly.

Any degree two extension of E is E[t] for some t satisfying x^2+bx+c, some degree two poly with coefficients in E

The "roots" of a quadratic x^2+bx+c can be found by completing the square over the complexes, right? mimic that here:

x^2+bx+c = (x+b/2)^2 +c-(b^2)/4 = y^2 +d after a change of variable y=x+b/2 since x=t is a root of the first, y=t+b/2 is a root of the second as long as the char isn't two then you're ok.


For a counter example in char 2, you need only consider F_4 over F_2, the fields of 4 and 2 elements resp. since a in F_2 means a^2=a, thus x^2+a = x^2+a^2 = (x+a)^2, in char 2.

 

[Palindrom]

Thanks a lot everyone!

And when char(E)=2, b/2 doesn't exist, since 1+1=0.

 

[mathwonk]

has anyone figured out irreducibility of the original equation? it is reducible mod 2,3, and 5. eisenstein fails on it, as well as when x is replaced by x-1, x-1, x+2 and x-2.

any other ideas?

 

[fourier jr]

i already did that one... \/ \/

show that Q[x] mod the ideal generated by your polynomial is a field. then the polynomial is irreducible, by the following results (they're probably in your book somewhere. i don't think they have names though):
a) an ideal A = (p(x)) in F[x] (polynomials over a field) is maximal <==> p(x) is irreducible over F
b) let R be commutative with identity & let M be an ideal of R. then M is maximal <==> R/M is a field
show that the quotient ring is a field, then (p(x)) is maximal, then the polynomial is irreducible

 

[mathwonk]

you seem to have merely restated the problem in an equivalent way, but not to have diminished the difficulty any. or am i missing something?

i.e. how do you actually check that the quotient ring is a field?

 

[Palindrom]

What I eventually did was write it as a product of 2 quadratics (learned a new word too ), whose leading coefficients are 1, and started writing equations for the other 4 coefficients. Got kinda ugly, so I got sick of it, but I think it would work if I would continue a bit more...

I'm sure there should be some more elegant way. I'll think about it tommorow...

 

[Hurkyl]

I'm sure it would work: I used it for a similar type of problem.

Of course, I took it as an excuse to try learning Magma, so I had it do most of the messy work.

 

[fourier jr]

i.e. how do you actually check that the quotient ring is a field?

you just do it. take elements f(x) + (p(x)), g(x) + (p(x)), h(x) + (p(x)) in Q[x]/(p(x)) & show that they satisfiy the field properties. i thought in most algebra books "verify blah blah is a field/group/etc" is problem 1 in the intro section on fields. that makes things a lot easier, imo.

 

[mathwonk]

it seems trivial if you quit trying to be clever and just write it down. i.e. the factors look like x^2 + ax + 1, and x^2 + bx + 1, or else

x^2 +ax-1 and x^2 +bx -1, and either way you get a+b = 0 and a+b = -22, right away.

does this check?


fourier jr, i think you are missing the point in your post. if not, then please just go ahead and "do it" for me. admittedly checking a quotient object is a ring is trivial, but not checking it is a field. you do not seem to understand the difference between a ring and a field.

I.e. it is not problem 1 anywhere. the difficulty is entirely proportional to the difficulty of checking irreducibility of the polynomial you are modding out.


there is a ridiculously impractical way to check irreducibility of any polynomial in the world, over the rationals, due i believe to kronecker.

i.e. you assume that f = gh, all with integer coefficients. then it follows that for every integer argument a, you have f(a) = g(a)h(a). now a polynomiloa of degree d is entirely determined by its value at d+1 points.

so you just pick any d+1 differen integers, (where d is an upper bound for the degree of the polynomials g,h) plug them all into f, and then factor them each all different ways into two factors, a finite but lnegthy process.

That gives a finite sequence of possibilities for the values of g,h at these d+1 points, and hncafints eqece of posbilities for g,h themselves.

then write down, via the lagrange interpolation formula, all possible polynomials g,h having these values. if they do not work, nothing will.

in the case above, using a = 0,1,-1, one has to write down all possible factorizations of the numbers 1, 20 and 24, already formidable by hand in the last two cases.

this factoring technique can be found in the great algebra book by van der waerden.

 

[fourier jr]

turning an irreducibily problem into a routine exercise like checking the field properties sounds pretty good to me. that's how i learned it anyway.

 

[mathwonk]

I agree with yoiu that this is a useful approach to amny things, but it still seems to me to leave one hard task in verifying you have a field. Namely the part about showing every non zero element has an inverse still seems hard. how do you do that routinely?

e.g. if the irreducible polynomial were say p(x) = x^3 + x^2 + x + 1, to show that say q(x) = x^2 -5x + 3 has an inverse h(x) we need to solve the equation

hq = 1 + pr, for some polynomial r.

for a specific q, this could be done by the euclidean algorithm, but if we do not know the polynomial p is irreducible, we have to prove this will result eventually in a remainder which is a constant. I do not know how to do that, simply from first principles.

It is a specific hard problem, proportional to the complexity of the polynomial p.

Does this make sense?