Massachusetts Institute of Technology Handout 4 6.044J/18.423J: Computability Theory of and with Scheme September 15, 1998 Professor Albert R. Meyer

Equations for Flattening Products over Sums

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 natural numbers n, m, k s.t. n + m=k,
(n * m) = k for all natural numbers n, m, k s.t. nm = k.
(Notice that this describes an infinite set of equations. In the coming handout on polynomial equation proof systems, it's shown that just the axioms
(n + 1) = k for all natural numbers n, k s.t. n + 1 = k,
imply all the above numerical axioms.)

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.