| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 901.1 | ... like this | ZFC::DERAMO | Supersedes all previous personal names. | Wed Jul 13 1988 20:15 | 97 |
| Suppose you start off with a polynomial equation of the
form
3 2
ax + bx + cx + d = 0
The first substitution I make is
b
x = y - --
3a
2
This has the effect of removing the y term from the
resulting polynomial equation for y. I didn't memorize
the coefficients that result, I usually just work out
the substitution. Suppose the result becomes:
3
y + Py + Q = 0
Now, if you use this substitution:
P
y = z - ---
3z
(I didn't invent this, by the way, I read it somewhere.
:-) then you get:
3
3 P
z - ---- + Q = 0
3 3
3 z
3
Multiply through by z to get a quadratic equation in
3
z . We know how to solve these, the roots are:
2 3
3 - Q +/- sqrt(Q + 4(P/3) )
z = --------------------------
2
Take one of the cube roots, and call it Z. Let w be
a complex cube root of one, so that
2 -1 +/- sqrt(-3)
w + w + 1 = 0, or w = ---------------
2
2
and so the three cube roots are Z, Zw, and Zw . Plug
into the substitution formula to get the y roots:
2
P Pw 2 Pw
y1 = Z - --- y2 = Zw - --- y3 = Zw - ---
3Z 3Z 3Z
b
Then x1, x2, x3 are determined from xi = yi - --.
3a
Dan
P.S.
Note that the quadratic actually gave two possible values
for z cubed. Suppose you call the cube root of one of
them Z and the cube root of the other Z'. Then Z and
Z' are related by
3
3 P
(ZZ') = --
3
3
If you work it out you will see that either one generates
the same three values of y. If you take
2 3
Z = any cube root of - Q + sqrt(Q + (P/3) )
-----------------------
2
and then take
2 3
Z' = the cube root of - Q - sqrt(Q + (P/3) )
-----------------------
2
such that ZZ' = P/3, then the y roots are
2 2
y1 = Z + Z' y2 = Zw + Z'w y3 = Zw + Z'w
|
| 901.2 | ... and fourth degree | ZFC::DERAMO | Supersedes all previous personal names. | Wed Jul 13 1988 20:31 | 47 |
| For the fourth degree equation
4 3 2
ax + bx + cx + dx + e = 0
again remove the next-to-the-highest degree term by the
substituion x = y - b/4a [in general, x = y - b/na for
the nth degree equation]. Call the result
4 2
y + Py + Qy + R = 0
Now, suppose we factored this as
4 2 2 2
y + Py + Qy + R = (y + Ay + B)(y - Ay + C) = 0
Well, if you play with it for a while you can determine
B and C in terms of A and get a third degree equation
2
in A . You solve that as in .-1 :-) :-) :-) :-) :-)
Then your four roots for y are the two pairs from the
two quadratics you get once you solve for A [and determine
B and C from it].
I have the equations for B and C in terms of A, and the
cubic for A squared in terms of P, Q, and R, at home, so I
can't type them in now. Knowing the process is enough, you
can always rederive these each time, but it is faster to
have written them down somewhere. :-)
If the four roots are r1, r2, r3, r4 then the split into two
quadratics can be done three ways:
(y - r1)(y - r2) and (y - r3)(y - r4)
(y - r1)(y - r3) and (y - r2)(y - r4)
(y - r1)(y - r4) and (y - r2)(y - r3)
The three solutions for A squared each correspond to
one of these. Then solving for A gives you a choice
for the + or - square root of A squared. Either choice
generates the same pair {B,C}, the choice just decides
which of the two is called B and which is called C.
Dan
|
| 901.3 | general purpose iterative solution | CTCADM::ROTH | If you plant ice you'll harvest wind | Thu Jul 14 1988 07:49 | 11 |
| If you just need numeric values for any of these, you're better off
calculating the roots by an iterative method, since the algebraic
methods have numerous special cases to worry about (and have
iteration imbedded in them anyway in the form of root extractions.)
See note 866 for a reliable method of taking roots in general.
[Most mathematical handbooks, such as AMS55 have a description of the
solutions to low-order polynomials...]
- Jim
|
| 901.4 | Fifth and higher. | HPSTEK::XIA | | Thu Jul 14 1988 11:09 | 3 |
| For fifth and higher order Poly., detour to note 881 (Not that we
know how to do it, but take a look anyway :-).
Eugene
|
| 901.5 | | FRACTL::HEERMANCE | In Stereo Where Available | Thu Jul 14 1988 14:35 | 5 |
| God I forgot how to find general solutions of third degree equations.
Now I remember why!
Martin H.
|
| 901.6 | filling in the holes in .1 and .2 | LISP::DERAMO | Hello, world\n | Mon Jul 25 1988 23:56 | 109 |
| Just a few more details on .1 and .2. The coefficients
can be elements of an arbitrary field. Assume that a
is nonzero.
If you start with
3 2
ax + bx + cx + d = 0
and make the substitution
b
x = y - --
3a
then you end up with
3
y + Py + Q = 0
where
2 3 2
3ac - b 2b - 9abc + 27a d
P = ------- Q = ------------------
2 3
3a 27a
Reply .1 describes what to do from here. The substitution
P
y = z - --
3z
3
eventually yields a quadratic in z with solution
3 1 2 3
z = - ( - Q +/- sqrt( Q + 4(P/3) ))
2
and the three solutions in terms of y are given by
k P/3
y = zw - --- k = 0, 1, 2
k k
w
for any such z, where w is a primitive cube root of 1.
If you start with
4 3 2
ax + bx + cx + dx + e = 0
and make the substitution
b
x = y - --
4a
then you end up with
4 2
y + Py + Qy + R = 0
where
2 2 3
8ac - 3b 8a d - 4abc + b
P = --------- Q = ----------------
2 3
8a 8a
3 2 2 4
256a e - 64a bd + 16ab c - 3b
R = ------------------------------
4
256a
The solution here was to factor this as
2 2
(y + Ay + B)(y - Ay + C) = 0
2
where A satisfies the cubic equation
6 4 2 2 2
A + 2PA + (P - 4R)A - Q = 0
and where B and C are given in terms of A by
1 2 2 Q 1 2 2 Q
B = - (P + A - -) C = - (P + A + -)
2 A 2 A
Dan
P.S.
I did say to assume that a is nonzero, because there
are divisions by (powers of) a in the above. There are
also divisions by (powers of) 2 and 3, so these must
be nonzero, also! That is, the field cannot in genereal
have characteristic 2 or 3. The solutions to the quadratics
that come up may require a division by 2, and the solutions
to the cubics may require a division by 3. In those
cases, it may not be possible to express the roots in
terms of radicals.
|
| 901.7 | beat that cubic to death! | LISP::DERAMO | Daniel V. {AITG,LISP,ZFC}:: D'Eramo | Wed Jul 27 1988 00:01 | 174 |
| First, some notation. Let w be a primitive cube root
of 1, so that w^3 = 1, w^4 = w, etc., and in particular
w^2 + w + 1 = 0. In the complex numbers, w is
(-1 +/- sqrt(-3))/2. Also, let b0, b1, b2 be the three
roots of a cubic equation.
The discussion in 881.* about Galois theory led me to try to
use those ideas to solve a cubic equation. The key comment
in 881.* was that if a permutation of the roots was a cycle
or rotation, like (b0,b1,b2)->(b1,b2,b0), then that
permutation would transform the sum
b0 + b1 w + b2 w^2
into itself times a power of w. Since w^3 = 1, such
a permutation would leave the cube of the sum unchanged.
So I started with (b0 + b1 w + b2 w^2)^3 is unchanged
if you rotate the roots, i.e., (b0,b1,b2)->(b1,b2,b0)->
(b2,b0,b1). Now, I'll diverge a little to symmetric
functions. A polynomial function like x^3 + y^3 + z^3
is completely symmetrical in its arguments -- any
permutation [not just a rotation] of the arguments leaves
the function unchanged. A nice result about zeroes of
polynomials is that any symmetrical polynomial function
of the roots can be expressed as a function of the
coefficients of the roots.
This is very neat. For second degree polynomials, let
(x - b0)(x - b1) = x^2 - s1 x + s2; any symmetrical
[polynomial] function of b0 and b1 can be expressed in
terms of s1 and s2. For example, b0^2 + b1^2 = s1^2 - 2 s2.
For third degree, there will be an s3, where
(x - b0)(x - b1)(x - b2) = x^3 - s1 x^2 + s2 x - s3.
The Galois theory expression of this is that if the
coefficients of a polynomial are in the field F, and
A is an element of the field F(b0,b1,...) [the smallest
field containing F and all the roots of the [irreducible?]
polynomial in question], such that every automorphism
of F(b0,b1,...) that leaves F fixed leaves A fixed, then
A is in F.
So back to the cubic -- (b0 + b1 w + b2 w^2)^3 is left
fixed by automorphisms that rotate the roots, but not
necessarily by all automorphisms. And anyway, even if
we knew what its value was, we need three linear equations
to solve for b0, b1, and b2. So I also decided to consider
[the cube of] b0 + b2 w + b1 w^2. Note that this is also
unchanged by rotations of the roots, and is transformed
into a rotation of the first expression by other permutation
of the roots. Since I needed three equations, I eventually
ended up with, in matrix notation:
[ 1 1 1 ] [b0] [B0] 1 [ 1 1 1 ] [B0] [b0]
[ 1 w w^2 ] [b1] = [B1] or - [ 1 w^2 w ] [B1] = [b1]
[ 1 w^2 w ] [b2] [B2] 3 [ 1 w w^2 ] [B2] [b2]
In the general case, with w a primitive nth root of 1,
the entry in row i and column j of the matrix, where
i and j go from 0, ..., n-1, is w^ij. For the inverse
matrix, the element is (w^(n-1)ij)/n.
So to solve the cubic, you have to compute B0, B1, and
B2, and the only way to do that is from the coeeficients
of the polynomial:
(x - b0)(x - b1)(x - b2) = x^3 - s1 x^2 + s2 x - s3
s1 = b0 + b1 + b2, s2 = b0 b1 + b1 b2 + b2 b0, s3 = b0 b1 b2
... and we know that any symmetric function of the three
roots can be expressed in terms of s1, s2, and s3.
Well, I knew B0 = b0 + b1 + b2 = s1. And I knew B1^3
and B2^3 were "almost symmetric". So I took the expression
for B1, b0 + b1 w + b2 w^2 and cubed it and wrote out
the result symbollically. Yuck.
The results were
B1^3 = s1^3 - 3 s1 s2 + 9 s3 + 3 w M + 3 w^2 N
B2^3 = s1^3 - 3 s1 s2 + 9 s3 + 3 w N + 3 w^2 M
B1 B2 = s1^2 - 3 s2 [I'll slip this in here.]
where
M = b0^2 b1 + b1^2 b2 + b2^2 b0
N = b0 b1^2 + b1 b2^2 + b2 b0^2
Yes, they are almost symmetric. But what are M and N?
They aren't symmetric. Rotations keep M and N unchanged,
but the other permutations interchange M and N.
The answer: M + N is symmetric. MN is symmetric. In
general, a two-place symmetric function of M and N is
a three-place symmetric function of the roots. So, I
added M and N [easy] and multiplied them [harder] and
figured out that:
M + N = s1 s2 - 3 s3
MN = s1^3 s3 + s2^2 - 6 s1 s2 s3 + 9 s3^2.
Now, this is enough to determine M and N: in fact what
we have here is a quadratic equation (x - M)(x - N) =
x^2 - (M + N)x + MN. At this point, I realized that
the traditional solution of quadratics was this same
mess with n=2 and w = -1. (the primitive square root of 1)
[temporarily consider b0,b1 with s1,s2 as given before
for quadratics]
E.g., [1 1] [b0] = [B0]
[1 w] [b1] [B1]
where "rotating" b0 and b1 turned B1 into -B1, so that
B1^2 is symmetric: B1^2 = (b0 - b1)^2 = b1^2 - 2 b0 b1 +
+ b1^2 = s1^2 - 4 s2. So b0 - b1 = +/- sqrt(s1^2 - 4 s2).
Taking the + square root gives
b0 = (s1 + sqrt(s1^2 - 4 s2))/2 [look familiar?]
b1 = (s1 - sqrt(s1^2 - 4 s2))/2
Taking the - square root reverses those.
So, back up to where I realized that solving the quadratic
for M and N was sort of a n=2 version of what I was doing
in the n=3 (cubic) case.
At this point I could solve for M and N given the
expressions for M + N and for MN in terms of s1, s2,
and s3. Then I could plug those in for the expressions
for B1^3 and B2^3. Take the cube roots of those, and
plug back in to the matrix equation to get b0, b1, b2.
The cubic polynomial is solved again!
I could even see the tie-ins to the earlier method.
The substitution x = y - b/3a is, in this notation [where
a = 1, b = - s1, c = s2, d = - s3] the same as
y = x - s1/3. We are "subtracting out" the average root
so that the new s1', s2', s3' for y has s1' = 0. You
can see how this simplifies the resulting expressions here,
because many of the terms contain a factor of s1. Also,
the result B1 B2 = s1^2 - 3 s2 restricts which of the
three cube roots one takes for cuberoot(B2^3) given the
choice made for B1 from among the three cube roots of
B1^3. The +/- in the square root in the quadratic solution
for M and N reverses the roles of M and N in a way also
seen in the solution in reply .1.
There are other things here that relate to the discussion in
881.* about Galois groups. Taking the cubes of B1 and B2
kind of "factors out" the normal subgroup of rotations of
(b0,b1,b2) from the complete group of all permutations of
(b0,b1,b2), leaving a quotient group which is the same as
the group for quadratic equations. Also, this analysis for
n=2 is ridiculous (it is obscured by the easy solution of
quadratics), for n=3 is "derives" the solution of cubics
that I had once read in a CRC book, for n=4 it will be much
harder, and for n=5 one can begin to understand how it could
be theoretically impossible.
If I had a computer package to grind through the algebra,
I would write out M and N and then b0, b1, and b2 in
terms of s1, s2, and s3 -- then plug them back into
x^3 - s1 x^2 + s2 x - s3 to see if the result is zero.
But without MAPLE or anything like that, I just tried
a few numerical examples and verified that the method
in .1 got the same results (and that those results actually
gave zero when plugged into the original polynomial!).
There's a lot left out here, but I'm tired, so I'll spare
you. :-)
Dan
|
| 901.8 | cookbook for .7 | LISP::DERAMO | Daniel V. {AITG,LISP,ZFC}:: D'Eramo | Wed Jul 27 1988 00:07 | 51 |
| [I posted .7 and .8 earlier with a mistake, so I deleted
them and am reposting these corrected versions.]
Summary of .-1:
Let b0, b1, b2 be the zeroes of the cubic polynomial
(x - b0)(x - b1)(x - b2) = x^3 - s1 x^2 + s2 x - s3.
Therefore s1 = b0 + b1 + b2
s2 = b0 b1 + b1 b2 + b2 b0
s3 = b0 b1 b2
Let w be a primitive cube root of 1, so that w^3 = 1,
and w^2 + w + 1 = 0. [This requires that the field not
be of characteristic 3, where x^3 - 1 factors as (x - 1)^3.]
Let b0 + b1 + b2 = B0
b0 + b1 w + b2 w^2 = B1
b0 + b1 w^2 + b2 w = B2
Then B0, B1, B2 are given by
B0 = s1
B1^3 = (s1^3 - 3 s1 s2 + 9 s3) + 3 w M + 3 w^2 N
B2^3 = (s1^3 - 3 s1 s2 + 9 s3) + 3 w N + 3 w^2 M
[Choice of cube roots subject to: B1 B2 = s1^2 - 3 s2]
where M = b0^2 b1 + b1^2 b2 + b2^2 b0
N = b0 b1^2 + b1 b2^2 + b2 b0^2
M + N = s1 s2 - 3 s3
MN = s1^3 s3 + s2^3 - 6 s1 s2 s3 + 9 s3^2
Solve the quadratic (x - M)(x - N) = x^2 - (M + N)x + MN = 0
using the expression for M and N in terms of the
coefficients s1, s2, and s3. [This may not work in a
field of characteristic two.]
Plug these values into the expressions for B1^3 and B^3,
and take the cube roots to find B1 and B2. The choice
of cube roots -- each Bi^3 technically has three -- must
satisfy B1 B2 = s1^2 - 3 s2.
Now solve for the roots in terms of B0, B1, and B2:
b0 = 1/3 (B0 + B1 + B2 )
b1 = 1/3 (B0 + B1 w^2 + B2 w )
b2 = 1/3 (B0 + B1 w + B2 w^2)
Dan
|
| 901.9 | aren't all cubics solvable in radicals?? | VIDEO::OSMAN | type video::user$7:[osman]eric.vt240 | Wed Jul 27 1988 17:20 | 20 |
| Regarding .6, which I quote the end of:
Dan
P.S.
I did say to assume that a is nonzero, because there
are divisions by (powers of) a in the above. There are
also divisions by (powers of) 2 and 3, so these must
be nonzero, also! That is, the field cannot in genereal
have characteristic 2 or 3. The solutions to the quadratics
that come up may require a division by 2, and the solutions
to the cubics may require a division by 3. In those
cases, it may not be possible to express the roots in
terms of radicals.
Does this mean that not all cubics are solvable in radicals? I thought
they were though.
/Eric
|
| 901.10 | they say it can | LISP::DERAMO | Daniel V. {AITG,LISP,ZFC}:: D'Eramo | Wed Jul 27 1988 20:32 | 33 |
| re .9
>> Does this mean that not all cubics are solvable in radicals? I thought
>> they were though.
I thought they were, too. I said it may not be possible
because I thought about it and couldn't find a way to get
around the divisions by 2 and 3. But one of my textbooks
has the following:
*****
Exercise 49.2:
Can the splitting field K of x^2 + x + 1 over Z2 [the
field of residue classes of integers modulo 2] be obtained
by adjoining a square root of an element in Z2 of an
element in Z2? Is K an extension of Z2 by radicals?
Answers in the back of the book:
No. Yes, K is an extension of Z2 by radicals.
*****
Nowhere have I read of an exception for fields of
characteristic 2 or 3, but I haven't come up with an
expression in radicals for those cases, either. So
"authority" says it can be done, but I would still like
to see it.
Dan
|
| 901.11 | | LISP::DERAMO | Daniel V. {AITG,LISP,ZFC}:: D'Eramo | Thu Jul 28 1988 20:14 | 6 |
| Aha, progress! In the "exercise 49.2" of reply .10,
the elements of the field K are 0, 1, a, and 1+a, where
a and 1+a are the two zeroes of x^2 + x + 1. Apparently
this is an extension by radicals because a^3 = 1.
Dan
|
| 901.12 | | AUSSIE::GARSON | | Thu Feb 25 1993 06:46 | 4 |
| Let a be the greatest positive root of the equation x�-3x�+1=0.
Show that [a^1788] and [a^1988] are both divisible by 17 where [x]
denotes the integer part of x.
|
| 901.13 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Fri Feb 26 1993 10:27 | 27 |
| Let the roots be a, b, c, ordered such that a > 1 > b > 0 > c > -1,
and work in the ring Z[a,b,c].
The original polynomial is (x-a)(x-b)(x-c) = x^3 - s1 x^2 + s2 x - s3,
where s1 = a + b + c, s2 = ab + ac + bc, s3 = abc (here s1=3,
s2 = 0, s3 = -1).
Now c^n is a root of the polynomial (x-a^n)(x-b^n)(x-c^n)
= x^3 - S1 x^2 + S2 x - S3, where S1, S2, and S3 can be
expressed as a sum of products of the terms s1, s2, and s3,
and S1, S2,and S3 are integers.
Now look at this modulo 17 in Z[a,b,c]. The first polynomial
has roots 4,5,11 mod 17 and so factors to (x-4)(x-5)(x-11).
Therefore x^3 - S1 x^2 + S2 x - S3 factors to (x-4^n)(x-5^n)(x-11^n).
For n=1788 this is (x-1)(x-4)(x-13) and S1 = 1 + 4 + 13 = 1 mod 17.
For n=1988 this is (x-1)(x-13)(x-4) and S1 = 1 + 13 + 4 = 1 mod 17.
So for either n, S1 = a^n + b^n + c^n = 1 mod 17.
Now 0 < |b|,|c| < 1 so b^n and c^n for these two large, even
values of n are small positive numbers and 0 < b^n + c^n < 1.
So [a^n] is simply one less than the integer a^n + b^n + c^n,
and so [a^n] = 0 mod 17.
Dan
|
| 901.14 | | AUSSIE::GARSON | | Fri Feb 26 1993 23:35 | 8 |
| Clever! (although I can't say that I've fully grokked it yet and I
wonder whether the high school students for whom this question was
posed would have been expected to solve it that way)
What's the ring Z[a,b,c]?
It looks to me that b and c are complex so you probably need
|b|<1 and |c|<1 in place of 1 > b > 0 > c > -1.
|
| 901.15 | clarification sought | HERON::BUCHANAN | The was not found. | Sat Feb 27 1993 11:47 | 14 |
| Dan,
Neat idea.
> Now look at this modulo 17 in Z[a,b,c]. The first polynomial
> has roots 4,5,11 mod 17 and so factors to (x-4)(x-5)(x-11).
> Therefore x^3 - S1 x^2 + S2 x - S3 factors to (x-4^n)(x-5^n)(x-11^n).
^^^^^^^^^
I would like to understand better this step here, which you denote
be the word "therefore". I agree it's obvious, but *why* is it obvious?!
Cheers,
Andrew.
|
| 901.16 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Sun Feb 28 1993 19:28 | 56 |
| re .14,
> What's the ring Z[a,b,c]?
The "integers" of the field Q(a,b,c). :-) Essentially, take
the closure of Z union {a,b,c} under addition, subtraction,
and multiplication, where Z is the set of signed integers.
> It looks to me that b and c are complex so you probably need
> |b|<1 and |c|<1 in place of 1 > b > 0 > c > -1.
The given polynomial does have three real roots, in the ranges
stated. In fact, the roots are 1 + 2 cos(theta) for theta =
20 degrees, 140 degrees, and 260 degrees.
re .15
> I would like to understand better this step here, which you denote
>by the word "therefore". I agree it's obvious, but *why* is it obvious?!
Multiple choice:
a) Wow, you saw my hand waving from all the way across the ocean!
b) You don't get the answer otherwise, so it has to be. :-)
c) It's hard to explain, but it feels right.
Well, how about this? We have x^3 - S1 x^2 + S2 x - S3
= (x - a^n)(x - b^n)(x - c^n). Now plug in y^n for x to
get y^3n - S1 y^2n + S2 y^n - S3 = (y^n - a^n)(y^n - b^n)(y^n - c^n)
Mod 17 that has to be (y^n - 4^n)(y^n - 5^n)(y^n - 11^n)
[is that more obvious?]. Now put back the x in place of y^n.
Alternatively, let Q(a,b,c) be the rationals with the three
roots a,b,c of p(x) = x^3 - 3x^2 + 1 adjoined. Let Z/17Z be
the field of integers module 17.
Define h:Q(a,b,c) -> Z/17Z by starting with
h(0) = 0 mod 17
h(1) = 1 mod 17
h(a) = 4 mod 17
h(b) = 5 mod 17
h(c) = 11 mod 17
The domain of h can be extended to all of Q(a,b,c) in such a
way that h is a homomorphism, i.e., h(x + y) = h(x) + h(y)
and h(xy) = h(x) h(y).
h can then be extended to a homomorphism H:Q(a,b,c)[x] -> (Z/17Z)[x]
between the two specified rings of polynomials.
If P(x) = (x - a^n)(x - b^n)(x - c^n), then H(P(x)) has to be
(x - h(a)^n)(x - h(b)^n)(x - h(c)^n) mod 17.
Dan
|
| 901.17 | Rate of hand-waving in -.1 would permit flight | HERON::BUCHANAN | The was not found. | Mon Mar 01 1993 09:49 | 19 |
| Dan, you rascal, :-)
> Well, how about this? We have x^3 - S1 x^2 + S2 x - S3
> = (x - a^n)(x - b^n)(x - c^n). Now plug in y^n for x to
> get y^3n - S1 y^2n + S2 y^n - S3 = (y^n - a^n)(y^n - b^n)(y^n - c^n)
> Mod 17 that has to be (y^n - 4^n)(y^n - 5^n)(y^n - 11^n)
> [is that more obvious?]. Now put back the x in place of y^n.
Obviously bogus, certainly.
> Define h:Q(a,b,c) -> Z/17Z by starting with
etc
> The domain of h can be extended to all of Q(a,b,c) in such a
> way that h is a homomorphism
Oh yes? What's h(1/17), for instance?
Not convinced,
Andrew.
|
| 901.18 | How do you buy *this* explanation? | HERON::BUCHANAN | The was not found. | Mon Mar 01 1993 11:07 | 28 |
| Dan,
Let's work entirely over Z.
S1 is a sum of products of s1,s2,s3. Write it S1 = z(s1,s2,s3). Obviously:
S1 == z(s1,s2,s3) mod 17
Now write:
s1 = a+b+c t1 = 4+5+11
s2 = ab+bc+ac t2 = 4.5+4.11+5.11
s3 = abc t3 = 4.5.11
and si == ti mod 17.
So S1 == z(t1,t2,t3) mod 17
S1 through z is just a function of a,b & c. And we've shown that mod 17
it is equivalent to exactly the same function of the numbers 4,5,11.
Now we know that S1 = a^n + b^n + c^n
So we can say S1 == 4^n + 5^n + 11^n mod 17.
Similarly for S2 & S3, but we weren't so interested in them.
Cheers,
Andrew.
|
| 901.19 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Mon Mar 01 1993 14:07 | 9 |
| Andrew,
That looks good, thanks. No need to verify by computing
a^n with a high-precision arithmetic package. :-)
Maybe the h's only work over Z[a,b,c] instead of Q(a,b,c).
Division isn't a problem there.
Dan
|
| 901.20 | | AUSSIE::GARSON | | Mon Mar 01 1993 16:49 | 10 |
| re .16
> The given polynomial does have three real roots, in the ranges
> stated. In fact, the roots are 1 + 2 cos(theta) for theta =
> 20 degrees, 140 degrees, and 260 degrees.
Oops, yes, you're right. I was working on x�-3x�-1=0
^
pretty stupid considering I was the one who posted the problem!
|
| 901.21 | there, not so much hand waving after all :-) | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Sat Mar 06 1993 13:25 | 109 |
| re .17: Oh yes? What's h(1/17), for instance?
The mistake there was to switch from a ring extension of Z
(the signed integers) to a field extension of Q (the
rationals), but the approach does work if you stick with
rings.
Let the roots of p(x) = x^3 - 3x^2 + 1 be a, b, and c.
p(x) is an irreducible element of Z[x] of degree three.
Galois theory says that if integers A, B, and C are chosen
so that the 3! numerical values of t = Aa + Bb + Cc
are all distinct as you permute a,b,c [i.e., Aa+Bb+Cc,
Aa+Bc+Cb,Ab+Ba+Cc,Ab+Bc+Ca,Ac+Ba+Cb,Ac+Bb+Ca are all
different], then the field Q(t) = Q(a,b,c). For irreducible
cubics such as p(x) the choice A=1, B=-1, C=0 will always work
(i.e., t = a - b). So here Q(a,b,c) = Q(t) where t=a-b.
To find an equation for t, note that its complete set of
conjugate values are {a-b,b-c,c-a,b-a,c-b,a-c}. The
polynomial with those roots is t^6 - 18t^4 + 81t^2 - 81
which factors to (t^3 - 9t + 9)(t^3 - 9t - 9). So take
t to be a root of F(t) = t^3 - 9t + 9 and you can solve
for a,b,c. The final result will be
a = - 1 + t + (1/3)t^2
b = - 1 + (1/3)t^2
c = 5 - t - (2/3)t^2
So p(x) factors over Q(t) as (x - a)(x - b)(x - c) =
(x - (- 1 + t + (1/3)t^2))(x - (- 1 + (1/3)t^2))(x - (5 - t - (2/3)t^2))
where t is a root of F(t) = t^3 - 9t + 9.
If we assign the roots of p(x) so that a > b > c then a is
approx. 2.88, b is approx. 0.65, c is approx. -0.53. The
problem is to find [a^n] mod 17 for n = 1788 and n = 1988.
|b| and |c| are less than one and |b| > |c| and b > 0 while
c < 0, so a^n will be very little less than a^n + b^n + c^n.
We recognize a^n + b^n + c^n as minus a coefficient from the
polynomial Pn(x) = (x-a^n)(x-b^n)(x-c^n). If we write out
Pn(x) = x^3 - S1 x^2 + S2 x - S3 then we see
S1 = a^n + b^n + c^n
S2 = a^n b^n + a^n c^n + b^n c^n
S3 = a^n b^n c^n
The point of this is that by symmetry the coefficients of
Pn(x) must all be integers. If we write s1 = a+b+c,
s2 = ab + ac + bc, s3 = abc, then we have
p(x) = x^3 - 3x^2 + 1 = x^3 - s1 x^2 + s2 x - s3
so s1 = 3, s2 = 0, s3 = -1. S3 is obviously (s3)^n = (-1)^n,
but S1 and S2 as symmetric functions of a,b,c must also be
sums of products of the integers s1, s2, and s3, and thus
be integers themselves. So S1 = a^n + b^n + c^n is an
integer, a^n is just less than S1, and in fact
S1 - 1 = [a^n] < a^n < S1
Now just as the field Q(t) is defined as the set of q+rt+st^2
for q,r,s in Q, subject to t^3 - 9t + 9 = 0, we can also define
the ring Z[t] as the set of i+jt+kt^2 for i,j,k in Z, subject
again to t^3 - 9t + 9 = 0.
Unfortunately, (1/3)t^2 is not an element of Z[t], so a,b,c
are not in Z[t]. However, 3a, 3b, and 3c are elements of
Z[t]. Consider the polynomial (x-3a)(x-3b)(x-3c) in Z[t].
By symmetry its coefficients will all be integers. Likewise
the coefficients of (x-(3a)^n)(x-(3b)^n)(x-(3c)^n) will
also be integers. Write that as x^3 - W1 x^2 + W2 - W3 and
you get W1 = (3a)^n + (3b)^n + (3c)^n is an integer, and
in fact W1 = (3^n)(a^n + b^n + c^n) = 3^n S1 (where S1 is
also known to be an integer).
But W1 is in Z[t] because 3a = -3+3t+t^2, 3b=-3+t^2, and 3c=15-3t-2t^2.
Here is where we can now map everything into the ring
(actually a field) of integers modulo 17, denoted Z/17Z.
F(t) = t^3 - 9t + 9 has three roots in Z/17Z: 7,11,16.
Pick one of those to be h(t), and define h(i + jt + kt^2)
to be (i + j h(t) + k (h(t))^2) mod 17. Then h:Z[t] -> Z/17Z
preserves +,-,*. If we use h(t) = 7, then
3a = -3+3t+t^2 => h(3a) = 16
3b = -3+t^2 => h(3b) = 12
3c = 15-3t-2t^2 => h(3c) = 15
Note that 3*11, 3*4, and 3*5 mod 17 are 16, 12, and 15, but
I'm not saying h(a) = 11, h(b) = 4, h(c) = 15, because I am
only defining h for elements of Z[t].
But given h(3a), h(3b), and h(3c) we can see that
h(W1) = h((3a)^n + (3b)^n + (3c)^n)
= h((3a)^n) + h((3b)^n) + h((3c)^n) mod 17
= (h(3a))^n + (h(3b))^n + (h(3c))^n mod 17
= 16^n + 12^n + 15^n mod 17
= 4 for n=1788, 13 for n=1988.
But also h(W1) = h(3^n S1) = h(3^n) h(S1) = h(3)^n h(S1)
= 3^n S1 mod 17.
3^1788 = 4 mod 17 and 3^1988 = 13 mod 17, so for both
values of n we see S1 = 1 mod 17.
Then from the earlier result: S1 - 1 = [a^n] < a^n < S1
we see [a^n] = 0 mod 17.
Dan
|
| 901.22 | Maple helps | HERON::BUCHANAN | The was not found. | Mon Mar 08 1993 13:07 | 32 |
| Dan,
I agree with you that we ought to be able to explain what's going on
in a clean way.
Why do you introduce t? The discriminant of p(x) is 81, so its
Galois group is C_3, not S_3. (This is confirmed by the fact that
you find that [Q(t):Q] = 3.) Thus Q(a,b,c) = Q(a). So p(x) splits over
Q(a). And indeed, Maple does not disappoint us:
> alias(a=RootOf(x^3-3*x^2+1));
I, a
> factor(x^3-3*x^2+1,a);
2 2
(x - a) (x - 2 - 2 a + a ) (x - 1 + 3 a - a )
Now a,b,c lie in Q(a) and in Z[a]. We can now define h along the
same lines as in your note, but we don't have to worry about division by 3.
> Then h:Z[a] -> Z/17Z preserves +,-,*.
This is where you hide your hand-waving this time round :-) We are
skating near to the bottomless pit of note 881.*. The basic deal seems to be
that the whole Galois machinery, including the Galois group itself, is mapped by
this h chap you suppute. And allegedly this is a key tool of Galois analysis.
That's what this "density/shape" stuff is about.
I'll have a look at 881 tonight, to see if I can grok it.
Cheers,
Andrew.
|
| 901.23 | | CSC32::D_DERAMO | Dan D'Eramo, Customer Support Center | Mon Mar 08 1993 18:48 | 30 |
| > Why do you introduce t?
I don't have Maple here, so dividing x^3 - 3x^2 + 1 by
(x - a) left me with (x - a)(x^2 + (a - 3)x + a(a - 3)).
Using the quadratic equation solving formula doesn't show
that b and c are in Q(a). But I knew they were in Q(t),
so I used that. I didn't think to symbolically compute
the square root of (a-3)^2 - 4a(a-3) in Q(a).
> This is where you hide your hand-waving this time round :-)
I don't know, it seems to me that h exists. :-)
If Z[x] is all polynomials in the variable x with coefficients
in Z, and p(x) = x^3 - 3x^2 + 1, and I is the ideal
< p(x) > = { p(x) f(x) | f(x) in Z[x] }
and J the ideal
< p(x), 17 > = { p(x) f(x) + 17 g(x) | f(x), g(x) in Z[x] }
then Z[a] is Z[x]/I, there is a canonical h1 : Z[x]/I -> Z[x]/J,
and h2 : Z[x]/J -> Z/17Z is just substitution for x.
Then define h(u) = h2(h1(u)). Is there really hand-waving
here?
Dan
|