[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

901.0. "Cubic equations" by EAGLE1::DANTOWITZ (nothing personal ...) Wed Jul 13 1988 19:54

	What is the general solution for a cubic equation?

T.RTitleUserPersonal
Name
DateLines
901.1... like thisZFC::DERAMOSupersedes all previous personal names.Wed Jul 13 1988 23:1597
     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 degreeZFC::DERAMOSupersedes all previous personal names.Wed Jul 13 1988 23:3147
     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.3general purpose iterative solutionCTCADM::ROTHIf you plant ice you'll harvest windThu Jul 14 1988 10:4911
    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.4Fifth and higher.HPSTEK::XIAThu Jul 14 1988 14:093
    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.5FRACTL::HEERMANCEIn Stereo Where AvailableThu Jul 14 1988 17:355
    God I forgot how to find general solutions of third degree equations.
    
    Now I remember why!
    
    Martin H.
901.6filling in the holes in .1 and .2LISP::DERAMOHello, world\nTue Jul 26 1988 02:56109
     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.7beat that cubic to death!LISP::DERAMODaniel V. {AITG,LISP,ZFC}:: D'EramoWed Jul 27 1988 03:01174
     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.8cookbook for .7LISP::DERAMODaniel V. {AITG,LISP,ZFC}:: D'EramoWed Jul 27 1988 03:0751
     [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.9aren't all cubics solvable in radicals??VIDEO::OSMANtype video::user$7:[osman]eric.vt240Wed Jul 27 1988 20:2020
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.10they say it canLISP::DERAMODaniel V. {AITG,LISP,ZFC}:: D'EramoWed Jul 27 1988 23:3233
     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.11LISP::DERAMODaniel V. {AITG,LISP,ZFC}:: D'EramoThu Jul 28 1988 23:146
     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.12AUSSIE::GARSONThu Feb 25 1993 09:464
901.13CSC32::D_DERAMODan D'Eramo, Customer Support CenterFri Feb 26 1993 13:2727
        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.14AUSSIE::GARSONSat Feb 27 1993 02:358
    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.15clarification soughtHERON::BUCHANANThe was not found.Sat Feb 27 1993 14:4714
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.16CSC32::D_DERAMODan D'Eramo, Customer Support CenterSun Feb 28 1993 22:2856
        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.17Rate of hand-waving in -.1 would permit flightHERON::BUCHANANThe was not found.Mon Mar 01 1993 12:4919
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.18How do you buy *this* explanation?HERON::BUCHANANThe was not found.Mon Mar 01 1993 14:0728
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.19CSC32::D_DERAMODan D'Eramo, Customer Support CenterMon Mar 01 1993 17:079
        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.20AUSSIE::GARSONMon Mar 01 1993 19:4910
901.21there, not so much hand waving after all :-)CSC32::D_DERAMODan D'Eramo, Customer Support CenterSat Mar 06 1993 16:25109
        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.22Maple helpsHERON::BUCHANANThe was not found.Mon Mar 08 1993 16:0732
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.23CSC32::D_DERAMODan D'Eramo, Customer Support CenterMon Mar 08 1993 21:4830
        > 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