Algebraic Simplification: A Guide for the Perplexed Joel Moses* Project MAC, MIT, Cambridge, Massachusetts Algebraic simplification is examined first from the point of view of a user who needs to comprehend a large expression, and second from the point of view of a designer who wants to construct a useful and efficient system. First we describe various techniques akin to substitution. These techniques can be used to decrease the size of an expression and make it more intelligible to a user. Then we delineate the spectrum of approaches to the design of automatic simplification capabilities in an algebraic manipulation system. Systems are divided into five types. Each type provides different facilities for the manipulation and simplification of expressions. Finally we discuss some of the theoretical results related to algebraic simplification. We describe several positive results about the existence of powerful simplification algorithms and the number-theoretic conjectures on which they rely. Results about the nonexistence of algorithms for certain classes of expressions are included. Key Words and Phrases: algebraic manipulation, algebraic simplification, canonical simplification CR Categories: 3.1, 3.2, 3.6, 4,9, 5.2, 5.9 Copyright (~) 1971, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted, provided that reference is made to this pub- lication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Association for Computing Machinery. This is a revised version of the paper which appeared in the Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, March 23-25, 1971, pp. 282-304. 1. Introduction Simplification is the most pervasive process in algebraic manipulation. It is also the most controversial. Much of the controversy is due to the difference between the desires of a user and those of a system designer. The user wants expressions which he can comprehend. The designer wants expressions which can be manipu- lated with great ease and efficiency. Users tolerate, and in fact prefer, a certain amount of redundancy in an answer. For example, they usually desire to see expres- sions containing the twelve trigonometric and hyperbolic functions. Designers would prefer giving a user only sines and cosines or just exponentials with complex arguments. There is one property of simplification about which both users and designers can agree. That is, that simpli- fication changes only the form or representation of an expression, not its value. Thus an ideal, but not very helpful, way to describe simplification is that it is the process which transforms expressions into a form on which the remaining steps of a computation can be most efficiently performed. The problem of representation for algebraic expres- sions is especially acute because there are so many equivalent ways to represent an expression. Frequently one of these equivalent forms is much more useful than another, and, just as frequently, it is a nontrivial problem to recognize the equivalence. For example, it * Department of Electrical Engineering. Work reported herein was supported by Project MAC, an MIT research program sponsored by the Advanced Research Projects Agency of tthe Department of Defense under Office of Naval Research contract number N00014- 70-A-0362-0001. 527 Communications August 1971 of Volume 14 the ACM Number 8is rare that we do not want to recognize that an expres- sion is equivalent to 0, but many of us have difficulty in recognizing the following identities: (2;+4~) 3- 6(2 ~+4~) - 6 = 0 or log tan (½x + ~Tr) - sinh -t tan x = 0. Consider how much more difficult the problems become when we deal with expressions which are several pages long. Yet expressions of such size are quite common in algebraic manipulation! An additional difficulty is that the usual manipulatory algorithms can easily magnify a bad choice of representation. For example, the deriva- tive of a product of n factors can be a sum of n terms each of n or more factors. Another issue which arises in discussions of simpli- fication is related to the local or global nature of the problem. If expression A is deemed simpler than its equivalent expression B in one context, then is A to be considered simpler than B in every context? A perfectly strict answer is no. For example, xT/(x 12 + 1) is a more compact representation of the rational function it represents than ~(4x3)x4/[(x4) 3 + I]. The former is usually easier to manipulate and comprehend. However, when integrating, the latter expression indicates a pat- tern which suggests the substitution y = x 4 which yields f ¼Ydy, y~+ 1 a much simpler integration problem than that which is posed by the first expression. Designers would prefer a system in which the simplification steps are the same in every context. Users clearly would prefer a system which could take contextual information into account in deriving a simplified expression. A related issue regarding simplification is the extent to which the concept can be formalized. The point that we made above is that the simplest form of an expres- sion depends on one's goals or, in other words, on the context. One would be hard put to formalize the goals of all potential users. However, we can obtain theoretical results for simplification algorithms which have useful properties. One such property is that the algorithm simplifies to zero any expression equivalent to 0. A stronger property is that the simplifier reduces all equivalent expressions to a single (canonical) expression. Historically, simplification was required in algebraic manipulation systems because the manipulatory algo- rithms produced sloppy results. For example, the un- simplified result of differentiating ax + xe x' with respect to x is an expression such as O.x + a. 1 + 1.e ~ + x.e~.2.x. "Simplifying the derivative above would yield an expres- sion like a q- e x2 + 2x~e ~. With the ever growing use of algebraic manipulation, it has become increasingly apparent that