Is there a "mathematical" definition of "simplify"?

Question

Every mathematician knows what "simplify" means, at least intuitively. Otherwise, he or she wouldn't have made it through high school algebra, where one learns to "simplify" expressions like $x(y+x)+x^2(y+1+x)+3(x+3)$.

But is there an accepted rigorous "mathematical" definition of "simplify" not just for algebraic expressions but for general expressions, which could involve anything, like transcendental functions or recursive functions? If not, then why? I would think that computer algebra uses this idea.

Answer 1

In full generality, there provably isn't any method for complete simplification (i.e., bringing an expression into a canonical simplest form). Simplifying should have two key properties: it should be algorithmic, and simplifying two different expressions for the same thing should give the same simplified form. If you have a simplification method with these properties, then it gives an algorithm for deciding whether two expressions are equivalent. However, Richardson proved that there is no algorithm to decide whether two closed-form expressions define the same function. (Of course you have to specify what you consider "closed-form". See D. Richardson, Some Undecidable Problems Involving Elementary Functions of a Real Variable, Journal of Symbolic Logic 33 (1968), 514-520, http://www.jstor.org/stable/2271358.)

Of course simplifying becomes easy if you give up on these properties. If you don't care about algorithms, just choose a representative for each equivalence class arbitrarily and declare it simplified. If you don't care whether equivalent expressions simplify to the same result, then just declare everything is already simplified.

This argument rules out only a very general notion of simplification. It still makes sense in many important special cases, and as Joel David Hamkins observes in the comments, one could still define a notion of simplicity even if there is no full simplification method.

Added in response to comments: Let's state things more precisely. Let the class $E$ of closed-form expressions contain $\log 2$, $\pi$, $e^x$, $\sin x$, and $|x|$ and be closed under addition, subtraction, multiplication, and composition of functions. These expressions all define continuous functions that are numerically computable (in the sense that one can algorithmically compute arbitrarily close approximations to their values at any given points). Call expressions $e_1$ and $e_2$ equivalent if they define the same function.

Richardson proved that there is no algorithm that can test whether two expressions in $E$ are equivalent. It follows immediately that no algorithm can bring elements of $E$ into any canonical form. I.e., there is no computable function $f$ from $E$ to $E$ such that $f(e_1)=f(e_2)$ iff $e_1$ and $e_2$ are equivalent.

Furthermore, one cannot even do it in the gradual sense described in the comments: there is no computable function $f$ from $\mathbb{N} \times E$ to $E$ with the following property: $f(n,e)$ is always equivalent to $e$, and if $e_1$ and $e_2$ are equivalent, then for all sufficiently large $n$ we have $f(n,e_1)=f(n,e_2)$ (of course how large $n$ needs to be may depend on $e_1$ and $e_2$). Think of $n$ as describing how hard you have tried to simplify your input, with the idea being that you eventually reach the canonical simplest form when $n$ is large enough, but you won't know when you've reached it (so you'll always be left wondering whether increasing $n$ would lead to further simplifications).

This observation requires a different proof, but it is not difficult. If such an $f$ existed, you could computably enumerate all the equivalent pairs $(e_1,e_2)$: to do so, loop through all triples $(e_1,e_2,n) \in E \times E \times \mathbb{N}$ and output $(e_1,e_2)$ whenever $f(n,e_1)=f(n,e_2)$. However, it is easy to computably enumerate the inequivalent pairs: loop through all expressions $e_1$ and $e_2$, rational numbers $x$, and natural numbers $k$, and output $(e_1,e_2)$ if numerically computing the corresponding functions at $x$ to within error less than $1/k$ shows that these functions differ at $x$. All inequivalent pairs will occur in this list, so if we could separately enumerate all the equivalent pairs (using the magic simplification function $f$), then we could solve the equivalence problem by seeing which list $(e_1,e_2)$ turned up in. That would contradict Richardson's theorem, and consequently $f$ does not exist.

What makes this tricky is that it's tempting to think the equivalent pairs should be computably enumerable. Can't you write down a list of all the expressions equivalent to $e$ by manipulating $e$ in all possible ways? Richardson's theorem implies that you cannot (for example, high school algebra manipulations are insufficient to get all equivalences, so high school classes give entirely the wrong impression). Proving two functions are different is easy, but proving two functions are the same is not, and there is no systematic way to do it.

Answer 2

What is simpler, $1+\tan^2\theta$ or $\sec^2\theta$? I prefer to put trig expressions exclusively in terms of $\sin$, $\cos$, and $\tan$, but the second expression is shorter.

What is simpler, $$x^6-20x^5+148x^4-518x^3+907x^2-758x+240$$ or

$$(x-1)(x-1)(x-2)(x-3)(x-5)(x-8)?$$

You may want your polynomials expressed in terms of the standard basis $1,x,x^2,\ldots$, or factored into linear terms; or then again, expressed in Bernstein form.

The solution in each case depends on what is required from the expression, so the answer to your question is that "simplify" is not well defined. What happens in practice is that instructors in remedial math courses teach some simplification rules so the students obtain a canonical answer that can be compared to the answer at the back of the textbook... And what dumb rules they are sometimes! I particularly mind that students learn to write $\sin(\pi/4) = \frac{\sqrt{2}}{2}$ instead of the "simpler" $\frac{1}{\sqrt{2}}$ (apparently some authors think that the students will be scared if there is a radical in the denominator). As a result the students learn not to think by themselves.

But all of this is moot... the true answer is that "simplifying" an expression may not be practical if, for instance, your expression is a word representing an element of a group whose word problem is not solvable :)

Answer 3

I guess you'll find much of what you would like to know in this 2004 paper by Jacques Carette (published here):

We give the first formal definition of the concept of simplification for general expressions in the context of Computer Algebra Systems. The main mathematical tool is an adaptation of the theory of Minimum Description Length, which is closely related to various theories of complexity, such as Kolmogorov Complexity and Algorithmic Information Theory. In particular, we show how this theory can justify the use of various “magic constants” for deciding between some equivalent representations of an expression, as found in implementations of simplification routines.

Answer 4

In general, probably not. However, confluence is a well studied property of rewriting systems. This is also known as the Church–Rosser property after Alonzo Church and J. Barkley Rosser who proved that the $\lambda$-calculus has this property.

Answer 5

I hesitate to submit this in the company of the more informed answers already present, but it seems that in the special case of polynomials, "simplified" form is basically conjunctive normal form or disjunctive normal form: an outer layer of + or * with all operands being only * or +, respectively. It also seems to me that this pattern is generally accepted as, if not the, then at least a simplified form for any kind of combination of functions. So, for example, $$e^t(1 + t) + t(1 + e^t) = e^t + 2t e^t + t$$ can be said to be simplified on account of being fully disjunctive-normal, having a layer of + followed by a layer of * followed by one of exponentials. By grouping terms one can obtain a narrower tree structure (such as $e^t(1 + 2t) + t$) but some of the deeper nodes (groups) would have operations (namely, addition) that occurred higher on the tree. Many of the objections made in above answers/comments touch on why this kind of tradeoff is inevitable.

Edit: It occurred to me that the statement about "any kind of combination of functions" has more meaning when it's given more context. So, for example, an expression similar to the above can be written in several ways: $$t + (1 + 2t) e^t + (t^2 - t - 1) e^{2t} = t + e^t + 2te^t + t^2 e^{2t} - t e^{2t} - e^{2t} = (1 + e^t - e^{2t}) + (2e^t - e^{2t}) t + e^{2t} t^2$$ in which the first is simplified as an element of $\mathbb{R}[t][e^t]$, the second as one of $\mathbb{R}[t,e^t]$, and the third as one of $\mathbb{R}[e^t,t]$. Some people might even quibble with the order of terms in a polynomial (such as $1 - t^2 + t$ versus $1 + t - t^2$ or $-t^2 + t + 1$), which suggests to me that the whole simplified-polynomial business (as seen in practice if not principle) is a combination of choosing a presentation of the polynomial ring, and choosing a term order as in Groebner bases.

Nonetheless, even if there is no precise definition of "simplify", it is possible to assign a number of criteria, such as the above, that, although being impossible to meet simultaneously, can individually indicate any number of expressions as being "not simplified".

Answer 6

I wanted to write this as a comment in support of Carlo Beenakkers answer but it was too long so I place it as an answer myself.

Simplification might be associated with the concept of expression economy.

In that line of thought, to simplify is to make more economical without loss of mathematical meaning.

But what measure of economy of an expression could one possibly use?

Just to illustrate (surely more eficient representation schemes could be devised), one could take for example the number of symbols in the expression above.

They are 7 symbols: x,(,y,+,),1,3 which means we can represent the expression in base 7 with the number resulting from the concatenation (in the order of the expression) of the algarism associated with each symbol.

The same procedure applied to the above expression once simplified would probably deliver a smaller number (comparing both once converted back to the same base, for example binary)

The concept of economy could therefore be attacched to the product of the number of symbols used and the number of digits of the number representation of the expression, somehow following a criteria for number base economy evaluation (Hayes, 2001) http://www.americanscientist.org/issues/pub/third-base and which reflects in the final binary number obtained.

Answer 7

I would like to confuse matters, perhaps, by bringing in a higher dimensional viewpoint. The following type of example was given by John Baez.

The diagram

$$\matrix{||| & |||||\cr ||| & |||||}$$ can be expressed symbolically by $$2\times (3+5)= 2\times 3 + 2 \times 5.$$ But the symbolic "on a line" expression involves many conventions which have to be learned. Which expression is "simpler"? Current computers work serially, on a line, as I understand it, and $2$-dimensional, or higher, rewriting has not been computerised, but is used in knot theory, higher category theory, and higher dimensional group theory.

The term "simplify" depends on the use, as others have observed above. The "simplest" description of a vector space over a given field is its dimension, but that does not mean we want to remove vector spaces from the literature. In my own field, a common statement has been that "groupoids reduce to groups", but the group description in a given case may be more complicated, since it requires choosing base points and trees (Ugh!). See my Grothendieck quote.

This reflects perhaps that mathematical understanding is about understanding structural implications, so "simplicity" depends on the background structure, and the way this is expressed. A "bigger" structure may make things look simpler!

Answer 8

There is a theory called Kolmogorov Complexity(KC,also called algorithmic information) which has been initiated by Chaitin,Solomonoff,and Kolmogorov.Roughly speaking,an object is simple if it's KC is shorter,it is related to recursive function or computability theory,or uncomputabilty ,See Kolmogorov complexity and it's application by Ming Li and Vitanyi for the exact definition and examples.or http://www.scholarpedia.org/article/Algorithmic_complexity. It may be what you are looking for.

Answer 9

I doubt there is a rigorous definition of simple expressions but in restricted cases there are some notions that may be what you're looking for. In the case of boolean expressions Quine & McCluskey defined minimum forms.

Minimum in their sense, however, was more related to implementation in digital hardware than simple in the sense you seem to mean.