# Surprises simplifying simple polynomials

I came across some somewhat surprising behavior of Simplify today, on something very simple. Let's take two cubic polynomials that we know have the same value:

bySum = Sum[k^2, {k, 1, n}]

(1/6)*n*(1 + 3*n + 2*n^2)

byBernoulli = (BernoulliB[3, n + 1] - BernoulliB[3])/3

(1/3)*((1 + n)/2 - (3/2)*(1 + n)^2 + (1 + n)^3)


Now, I haven't done anything to simplify these two polynomials, so it's no surprise that they look different. However, Simplify helps less than you might think:

{bySum, byBernoulli} // Simplify

{(1/6)*n*(1 + n)*(1 + 2*n), (1/6)*n*(1 + 3*n + 2*n^2)}


Mathematica can still figure out that they're the same if you ask it, but the Simplify'd forms are different.

bySum == byBernoulli // Simplify

True


I was somewhat surprised by this. FullSimplify works as I'd expect, but this isn't the sort of problem where I'd expect to need it.

For what it's worth, this is Mathematica 8.0.4 on Windows 7 (x64).

-
The answers to my question here might shed some light on this issue. – Eli Lansey Apr 20 '12 at 21:44
From the answers, I guess that the "surprising behaviour" can be explained like this: when you evaluate Simplify[exp1==exp2], MMA doesn't simplify both expressions independently and see if they match, but it simplifies the subtraction and sees if it's zero, and it's not the same thing – Rojo Apr 21 '12 at 2:31
A lot of "surprises" I've found come from not thinking about the TreeForm and the LeafCount. See also sorting: mathematica.stackexchange.com/questions/2729/ordering-problem/… – tkott May 1 '12 at 0:37
Note that for simple expressions such as polynomials in one variable, comparing them with an ExpandAll is as effective as Simplify. – ogerard Jun 12 '12 at 6:31

We get different results because Simplify, working with a smaller range of accessible transformations than FullSimplify does, applied to structurally very different expressions at the begining, reaches only the local minimum of the default ComplexityFunction, being roughly close to LeafCount, unlike in case of FullSimplify even though its underlying ComplexityFunction may be the same.

Having defined :

bySum = Sum[k^2, {k, 1, n}];
byBernoulli = (BernoulliB[3, n + 1] - BernoulliB[3])/3;


we get :

bySum == byBernoulli // Simplify

True


because

Simplify[byBernoulli - bySum]

0


even though Simplify yields different results here :

  {bySum, byBernoulli} // Simplify


This is because at the begining we have very different forms of the expressions which we can observe with help of TreeForm and LeafCount assessing the complexity :

LeafCount /@ { bySum, byBernoulli, byBernoulli - bySum }

{13, 26, 40}

TreeForm /@ {bySum, byBernoulli}


A kind of expression not involving special functions where FullSimplify simplifies it in a much better way than Simplify one can find here. Knowing that algorithms behind FullSimplify contain a much wider range of transformations than Simplify the latter finds at certain stage only a local minimum (not sufficient in case of byBernoulli // Simplify to reach the global minimum) of the actual complexity function and therefore the resulting expressions are slightly different :

LeafCount /@ {bySum // Simplify, byBernoulli // Simplify}

{13, 15}

TreeForm /@ {bySum // Simplify, byBernoulli // Simplify}


unlike in case of FullSimplify :

{bySum , byBernoulli } // FullSimplify


We needn't use FullSimplify to get the same expressions, a simpler solution of the problem would be this :

{bySum, byBernoulli} // Factor


which is the same as the result of FullSimplify for the both expressions as well as Simplify for bySum. It should be mentioned here, that FullSimplify when applied to a factorizable polynomials tends to give that polynomial in the factorized form, i.e. Factor[poly] yields by default its factorized form if poly is factorizable in the field of rationals, however if we extend the rationals appropriately the results will be different, e.g. Factor[1 - 10 x^2 + x^4, Extension -> {Sqrt[2], Sqrt[3]}] (see this answer). So this is rather a special case, a more genreal approach (also for polynomials not factorizable in the rationals)
would be :

{bySum, byBernoulli} // Collect[#, n] & // Simplify


The result is the same as in the case of byBernoulli // Simplify.

-
I'm curious... did you really mean to bold an entire paragraph or was it an accident? Seems a bit excessive ;) – R. M. May 1 '12 at 0:56
@R.M Since the post had become a bit long I wanted to emphasize the essence. Sometimes I cannot express my thoughts more briefly. – Artes May 1 '12 at 1:07
Fair enough... I would've probably used the quote block to get a yellow background to draw attention, but I see that you're using it for outputs. – R. M. May 1 '12 at 1:12
Also, hope you don't mind me poking at such stuff — I do edit a lot! and tend to notice things ;) – R. M. May 1 '12 at 1:14
I find your suggestions meaningful, and if you see some flaws, edit my posts please. – Artes May 1 '12 at 1:21

FullSimplify is Simplify with additional transformation rules; some of these rules may be necessary to simplify a polynomial to a form where you can see the equality explicitly.

In case of polynomials, I usually use Simplify@Expand to group terms the same way; Expand brings the polynomial in an unambiguous standard form, at which point both results should be the same already. Applying Simplify afterwards is merely a matter of making it more readable.

polySimplify = Simplify[Expand[#]] &;

bySum = Sum[k^2, {k, 1, n}];
bySum // polySimplify

byBernoulli = (BernoulliB[3, n+1]-BernoulliB[3])/3;
byBernoulli // polySimplify

1/6 n (1+3 n+2 n^2)
1/6 n (1+3 n+2 n^2)

-