# 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? – J.C. Ottem Oct 31 '11 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. – fedja Oct 31 '11 at 18:18
Max: I think the $v_i$ are given, not free to be chosen. – Noah Stein Oct 31 '11 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? – Qfwfq Oct 31 '11 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. – Jacques Carette Nov 1 '11 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.

-
+1 and accepted answer! – Qfwfq Nov 1 '11 at 1:20
no, that is wrong way – Melania Nov 1 '11 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. – Emil Jeřábek Nov 1 '11 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. – Jacques Carette Nov 1 '11 at 12:25
I see, thanks for the explanation. – Emil Jeřábek Nov 1 '11 at 14:12

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? – Jacques Carette Nov 1 '11 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. – Melania Nov 1 '11 at 17:33