31
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Good question. I always get uneasy when I see problems which implore students to "simplify" some expression. Even to declare something to be "simple" seems somewhat subjective. $\endgroup$
    – Mark Grant
    Apr 4, 2013 at 14:59
  • 17
    $\begingroup$ If I write "No", my answer will be rejected as too short. Surely a two-letter answer cannot be simplified any further. $\endgroup$ Apr 4, 2013 at 16:53
  • 3
    $\begingroup$ If it were up to me, I would define a simplified mathematical expression as an expression that has the least possible Kolmogorov complexity and the least possible computational complexity. $\endgroup$ Apr 4, 2013 at 17:39
  • 3
    $\begingroup$ Outside of very formal situations, every usage of "simplify" tends to be terminology with a conditioned meaning. You never tell people what it means (because you don't have the vocabulary for it) but you trust there is a built-up expectation for roughly what it means. Some students do not know what it means and would probably benefit from a more formal treatment. $\endgroup$ Apr 5, 2013 at 1:50
  • 1
    $\begingroup$ In group theory (and surely also different parts of mathematics), there is the huge topic of normal forms. Normal forms are usually not canonical, there are many choices. To make the notion of simplifying precise, one should decide what it means for a polynomial/function to be in normal form. For a polynomial, there are some obvious choices. $\endgroup$ Apr 5, 2013 at 18:26

9 Answers 9

36
$\begingroup$

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.

$\endgroup$
18
  • 2
    $\begingroup$ I don't think this answer is quite right. Specifically, there seems to be a concept of "simplified" that satisfies your two criteria while stopping short of solving the equivalence problem. Specifically, let us imagine that there is a computable procedure to enumerate all the various equivalent expressions to a given expression, by applying various algebraic rules or deductions of proofs or whatever, so that the set of these equivalence expressions forms a c.e. set. $\endgroup$ Apr 4, 2013 at 17:55
  • 1
    $\begingroup$ This process is as in our practice, at the blackboard, where we simplify an expression, but then realize suddenly that further simplifications are possible. $\endgroup$ Apr 4, 2013 at 17:56
  • 2
    $\begingroup$ The definition implicit in Joel's comments above is essentially the definition that I have used in my paper (see Carlo Beenakker's answer). The optimal simplified form is indeed uncomputable, as far as I am concerned. I further argue that this 'optimal' is not even particularly desirable, as a difference of just a few bits in representation length should not be considered relevant [since one can always change universal Turing machines anyways and change all codes by a bounded number of bits]. $\endgroup$ Apr 5, 2013 at 0:06
  • 2
    $\begingroup$ Also note that Moses (dl.acm.org/citation.cfm?id=806298 - paywall, google for it for a free version) has an excellent discussion for why 'canonical form' is an exceedingly bad definition of "simplest". $\endgroup$ Apr 5, 2013 at 0:09
  • 3
    $\begingroup$ +1. Henry, that is quite a remarkable result. Your notion of equivalence is stronger than the one I had proposed, since you say two expressions are equivalent if it is true that they define the same function, whereas I had said they are equivalent if it is provable in some fixed theory that they define the same function. For my equivalence, the equivalence classes are c.e., and the algorithmic solution is obtainable as I had described. For your solution, it is quite remarkable that the equivalence classes are not c.e... $\endgroup$ Apr 5, 2013 at 9:39
11
$\begingroup$

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 :)

$\endgroup$
6
  • $\begingroup$ Well, it's moot for instructors but not necessarily for students. They can correctly reduce a word to its simplest form, but there is no systematic way to determine whether they are correct. $\endgroup$ Apr 5, 2013 at 0:06
  • 6
    $\begingroup$ My colleague, Peter Doyle, often argued that $\sqrt2$ and $\sqrt{1/2}$ need shorter names, with just one syllable, like $e$ and $\pi$; he suggested using Roo and Ralf. $\endgroup$ Apr 5, 2013 at 0:56
  • 1
    $\begingroup$ See my paper - I agree with you. Defining 'simpler' when the two representations differ by just a few bits (information-theoretically) is pointless, since length is stably defined only up to a (small!) constant anyways. 'simpler' only makes sense when there is a non-trivial difference in MDL code length. $\endgroup$ Apr 5, 2013 at 1:21
  • 1
    $\begingroup$ I always thought the preference of $\frac{\sqrt{2}}{2}$ over $\frac{1}{\sqrt{2}}$ comes from the pre-calculators era. To compute the former you look for $\sqrt{2}$ in a table an then divide by $2$ by hand. To compute the latter you first need to "rationalize" the expression as you learned in your remedial math course. $\endgroup$ Apr 9, 2013 at 18:43
  • $\begingroup$ @Ramiro: Entonces es verdad que un radical en el denominador da mas miedo :) Eso explica tambien porque escriben $2\sqrt{2}$ en lugar de $\sqrt{8}$... $\endgroup$ Apr 10, 2013 at 3:44
9
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ I do not believe that minimum description length is always the best understandable form (compare polynomials in nested parentheses or ordered by exponent). But in my opinion simplifying something means to get an expression that is better understandable. $\endgroup$
    – user112109
    Apr 4, 2013 at 15:26
  • 2
    $\begingroup$ Note that the definition of 'simplest', as given in that paper relativizes: given a theory of what the reader currently 'understand', then the simplest expression is one which is shortest with respect to expressions relative to that theory. $\endgroup$ Apr 5, 2013 at 0:01
  • 3
    $\begingroup$ These 'notes' are published (dl.acm.org/citation.cfm?id=1005298). However, this was my first solo paper [so I stand behind the ideas, but I shudder at how awful the write-up is]. I really ought to write a better version of this. $\endgroup$ Apr 5, 2013 at 0:12
  • $\begingroup$ thank you, Jacques, for the link, I updated the reference. $\endgroup$ Apr 5, 2013 at 5:48
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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".

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ While I agree in spirit, this does not seem to be an answer to the actual question, which is about formal rigorous senses of "simplify". $\endgroup$
    – Todd Trimble
    Apr 5, 2013 at 11:30
  • $\begingroup$ @Todd: I agree. My whole mathematical life seems to be devoted to asking, or answering, different questions, or looking for a wider context! But my answer is in disagreement that there is a clear intuitive notion of simplification. On the other hand, the technical answers with regard to some standard expressions are clearly important, and computer algebra systems which do this can be very useful. $\endgroup$ Apr 5, 2013 at 17:48
  • $\begingroup$ @Ronnie: fair enough! I agree with your disagreement, in the sense that a formal notion of simplicity might not accord too well with a human's idea of it, which can be embedded in much larger surrounding neighborhoods of mathematics. Cf. Rota's remarks in Indiscrete Thoughts on the 'phenomenology of mathematical enlightenment'. $\endgroup$
    – Todd Trimble
    Apr 5, 2013 at 18:38
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.