# Simplifying a polynomial

Let $f(x_1,\ldots, x_n)\in\Bbbk [x_1,\ldots,x_n]$ be a given polynomial (assume $\Bbbk$ algebraically closed if you want). Suppose that we are given $n$ polynomials $v_1,\ldots v_n \in\Bbbk[x_1,\ldots, x_n]$. Suppose that we know that there exists a polynomial $P(t_1,\ldots,t_n)\in\Bbbk[t_1,\ldots,t_n]$ such that

$$f(x_1,\ldots,x_n)=P(v_1(x_1,\ldots,x_n),\ldots,v_n(x_1,\ldots,x_n))\in\Bbbk[x_1,\ldots,x_n]$$

How to find $P$ explicitely? Is there a computer program that can easily solve this problem?

I'm also interested in answers under the hypothesis that $v_1,\ldots, v_n$ are homogeneus of degrees $d_1,\ldots, d_n$ (and possibly some symplifying assumptions on $d_i$), and/or $f$ is itself homogeneus.

To me this is just a practical question which is natural enough to be asked on MO; I apologize if it is totally trivial for some people more knowledgeable in computational matters.

• Have you looked at SAGBI basis algorithms? Oct 31, 2011 at 18:06
• Well, in principle, it is just a huge system of linear equations for the coefficients of $P$. So, if the degree and the number of variables are not too large, you should be able to set it up and solve. Of course, the complexity of this naive approach goes up fast as $n$ grows but I see no reason why it shouldn't unless your polynomials have some special structure. Oct 31, 2011 at 18:18
• Max: I think the $v_i$ are given, not free to be chosen. Oct 31, 2011 at 19:47
• @Max: the problem is something like this: given $f$ and $v$ such that $f=P\circ v$ for some polynomial $P$, find $P$ explicitely. @Melania: maybe you could expand a bit and make the comment become an answer? Oct 31, 2011 at 22:09
• @Qfwfq: this is very far from a trivial problem. But it turns out to have some rather efficient solutions. This requires deep algorithmic thinking, see the references I point to. Nov 1, 2011 at 0:29

This is the (multivariate) functional decomposition problem. It has a long history, going back to 1922 work by Ritt and 1941 work by Engstrom. See the introduction to Algorithms for the Functional Decomposition of Laurent Polynomials by Stephen Watt for a nice historical overview. You will also be interested in references 1-8 in that paper.

The most recent work (on the multivariate) case that I am aware of is that of Faugère and Perret (see also the slides for the talk and a journal version). Their algorithm is non-trivial, and trying to explain it here would amount to reproducing their paper, so I won't do that.

EDIT: Note that most of these algorithms are in two pieces. As was pointed out, just one of these pieces is really needed here. And while GB can be used, the good thing about the functional decomposition algorithms is that they are able to use all of the structure present in the problem, which is really too much to ask for from a generic GB.

• no, that is wrong way Nov 1, 2011 at 8:42
• As far as I can see, the functional decomposition problem as defined in the linked papers is: given $f$, find $P$ and $v$. In Qfwfq’s question, $v$ is also given. Nov 1, 2011 at 11:37
• If you look at (most of) the algorithms, they split into 2 pieces. Qfwfq's problem reduces to using just one of the two. Nov 1, 2011 at 12:25

It is a standard problem for Groebner basis theory, see for example Ideals, varieties, and algorithms by David Cox, John Little, Donal O'Shea. In the polynomial ring $k[x_1,x_2,\ldots,x_n,y_1,\ldots,y_n,f]$ consider the ideal $I=(f-f(x_1,\ldots,x_n), y_1-v_1(x_1,\ldots,x_n),\ldots,y_n-v_n(x_1,\ldots,x_n))$.If we eliminate the variables $x_1,x_2,\ldots,x_n$ by using Groebner basis and if we get a elimination relation of the following form $f-F(y_1,\ldots,y_n)$ for some polynomial $F$, then $F$ is the looking polynomial and we obtain that $f(x_1,\ldots,x_n)=F(v_1,v_2,\ldots,v_n).$

• This works, but is in some ways overkill. This is because there is a lot of structure in the presentation of the ideal above which is usually not exploitable by (most) GB algorithms. Plus it is well-known that GB is extremely sensitive to variable ordering -- which ordering would you choose for this problem? Why? Nov 1, 2011 at 12:29
• @ Jacques. I agree that for big degree polynomials it doest works well. But I dont sure if your's method is better in this case. The standard procedure $\tt{Eliminate}$ allows doesnt care about ordering. Nov 1, 2011 at 17:33