# On simplification of polynomials in several variables

Let us consider a polynomial

expr = Expand[(x - 2*y + 1)^9 - x*(x + y)^8];


Mathematica does her best, simplifying it by

FullSimplify[expr]


$$x^8 (9-26 y)+4 x^7 (y (29 y-36)+9)-28 x^6 (2 y (y (13 y-18)+9)-3)+14 x^5 (y (y (y (139 y-288)+216)-72)+9)-14 x^4 (2 y (2 y (y (y (73 y-180)+180)-90)+45)-9)+28 x^3 (y (y (y (y (y (191 y-576)+720)-480)+180)-36)+3)-4 x^2 (2 y (y (y (y (y (y (577 y-2016)+3024)-2520)+1260)-378)+63)-9)+x (y (y (y (47 y-96)+72)-24)+3) (y (y (y (49 y-96)+72)-24)+3)-(2 y-1)^9$$

Are there general algorithms to reduce the above to $$(x - 2y + 1)^9 - x(x + y)^8$$?

• Suppose you generate a family of random polynomials in x and y, each with modest leaf count. Then for each polynomial p you evaluate LeafCount[p+Simplify[expr-p]] and keep some fraction of the polynomials which give the smallest LeafCount. Then slightly mutate each of those polynomials in all possible ways and repeat. The book "Illustrating Evolutionary Programming With Mathematica" describes and provides some tools for things like this. Given time I expect this will find solutions to problems like this. – Bill Jun 3 '19 at 18:04
• @Bill: Many thanks from me to you for the idea. It would be useful to realize it. I am a sceptic concerning that. – user64494 Jun 4 '19 at 4:57
• Here is a paper cs.bham.ac.uk/~wbl/biblio/gecco1999/RW-719.pdf I found which describes doing exactly this process to find simple forms of polynomials that don't just simply factor. The paper is old enough that I haven't been able to find the files that the author mentions, if we could track those down then that would really help, and it was done in Maple. If we can implement this in current MMA then perhaps we can slightly advance the state of simplification. – Bill Jun 4 '19 at 19:14