Here is the problem assigned at the end of class Monday, 9/14/98.  PREPARE
BRIEF WRITTEN SOLUTIONS FOR PROBLEMS 1 AND 2 FOR SUBMISSION IN CLASS ON
WEDNESDAY.


We'll consider arithmetic expressions involving binary +, *, and unary
minus, - , along with variables and numbers.  For simplicity, the only
numbers we'll allow are natural numbers 0,1,2,....

We've seen the main equational rules needed to ``flatten'' arithmetic
expressions, namely,

DISTRIBUTIVITY:
                   (e * (f + g)) = ((e * f) + (e * g)),

MINUS:
                           -(-e) = e,
                        -(f + g) = ((-f) + (-g)),
                       -(f *  g) = ((-f) * g).

To really reduce any arithmetic expression to a sum of monomials with
number coefficients, there are some other very familiar rules needed as
well:

COMMUTATIVITY of + and *:
                            (a + b) = (b + a),
                            (a * b) = (b * a).
(With commutativity we only need one-sided distributivity, which is why we
only included the left distributivity rule above.)

ASSOCIATIVITY of + and *:
                   (e + (f + g)) = ((e + f) + g),
                   (e * (f * g)) = ((e * f) * g).

INTEGER ARITHMETIC:
                               (n + m) = k   for all integers n,m,k s.t. n+m=k,
                               (n * m) = k   for all integers n,m,k s.t. nm=k.
(Notice that this describes an infinite set of equations.)

The STANDARD FORM of an arithmetic expression in one
variable X is illustrated by the fourth degree polynomial form

   ( (23 * (X * (X * (X * X)))) + 
    ( ((- 701) * (X * (X * X))) +
                       ((4 * X) + (- 3)) ) ).

Notice that in our standard form, products and sums are
right-parenthesized, the powers of X are in decreasong order, but not all
powers of X, eg, the X ``squared'' term, need appear.

PROBLEM 1: There are a few more equational rules needed to be able to
reduce an arbitrary arithmetic expression into the standard form above.
Supply these additional rules, and carefully justify your claim that these
additional rules combined with those above are sufficient to allow any
arithmetic expression to be reduced to standard form.


PROBLEM 2: Now let's allow the usual ``power'' notation in arithmetic
expressions.  Namely, (e ** n) is allowed for any expression e and integer
n > 1, and we want POLYNOMIAL FORM to look like

   ( (23 * (X ** 4))       + 
    ( ((- 701) * (X ** 3)) +
                  ((4 * X) + (- 3)) ) ).

To accomplish this, we add the rule
                         (e ** 2) = (e * e),
and an infinite set of rules of the form
                         (e ** n) = (e * (e ** m))
for all integers n,m > 1 s.t. m=n-1.  Explain why this works.


PROBLEM 3 (no writeup required): Prepare to discuss briefly in class how
the above results should be generalized to handle expressions with more
than one variable.