Simplificar un polinomio

Question

Dejemos que $f(x_1,\ldots, x_n)\in\Bbbk [x_1,\ldots,x_n]$ sea un polinomio dado (suponga $\Bbbk$ cerrado algebraicamente si se quiere). Supongamos que nos dan $n$ polinomios $v_1,\ldots v_n \in\Bbbk[x_1,\ldots, x_n]$ . Supongamos que conozca que existe un polinomio $P(t_1,\ldots,t_n)\in\Bbbk[t_1,\ldots,t_n]$ tal que

$$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]$$

Cómo encontrar $P$ explícitamente? ¿Existe algún programa informático que pueda resolver fácilmente este problema?

También me interesan las respuestas bajo la hipótesis de que $v_1,\ldots, v_n$ son homogéneos de grados $d_1,\ldots, d_n$ (y posiblemente algunas suposiciones simplificadoras sobre $d_i$ ), y/o $f$ es en sí mismo homogéneo.

Para mí esto es sólo una pregunta práctica que es lo suficientemente natural como para ser preguntada en MO; me disculpo si es totalmente trivial para algunas personas más conocedoras de los asuntos computacionales.

Answer 1

Esta es la (multivariante) descomposición funcional problema. Tiene una larga historia, que se remonta al trabajo de Ritt de 1922 y al de Engstrom de 1941. Véase la introducción de Algoritmos para la descomposición funcional de los polinomios de Laurent de Stephen Watt para una buena visión histórica. También le interesarán las referencias 1-8 de ese documento.

El trabajo más reciente (sobre el caso multivariante) que conozco es el de Faugère y Perret (véase también el diapositivas de la charla y un versión de la revista ). Su algoritmo no es trivial, y tratar de explicarlo aquí equivaldría a reproducir su documento, así que no lo haré.

EDIT: Tenga en cuenta que la mayoría de estos algoritmos son en dos piezas. Como se señaló, sólo una de estas piezas es realmente necesario aquí. Y mientras GB puede lo bueno de los algoritmos de descomposición funcional es que son capaces de utilizar toda la estructura presente en el problema, lo que realmente es mucho pedir a un GB genérico.

Answer 2

Es un problema estándar para la teoría de bases de Groebner, véase por ejemplo Ideales, variedades y algoritmos por David Cox, John Little, Donal O'Shea. En el anillo polinómico $k[x_1,x_2,\ldots,x_n,y_1,\ldots,y_n,f]$ considerar el 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))$ Si eliminamos las variables $x_1,x_2,\ldots,x_n$ utilizando la base de Groebner y si obtenemos una relación de eliminación de la siguiente forma $f-F(y_1,\ldots,y_n)$ para algún polinomio $F$ entonces $F$ es el polinomio de búsqueda y obtenemos que $f(x_1,\ldots,x_n)=F(v_1,v_2,\ldots,v_n).$