Dado un polinomio f perteneciente a K[x], determinar si existen otros dos g y h de grado mayor que uno tales que f(x) = g(h(x)) = g o h, y, en caso de que existan, encontrarlos, es conocido como problema de descomposición para polinomios. Cuando dicha descomposición existe, problemas como la evaluación de f en un punto o la resolución de la ecuación f = 0 se pueden resolver de manera más simple. La generalización del problema de la descomposición al caso de funciones racionales es sin duda un problema más difícil. La descomposición de funciones racionales ha sido estudiada ya en [10] y en [8]. Recientemente, en [11] se presenta el primer algoritmo en tiempo polinomial para la descomposición de funciones racionales. No obstante dicho algoritmo requiere en uno de sus pasos la factorización de un polinomio sobre un cuerpo de funciones algebraicas. El propio Zippel comenta acerca de su algoritmo, que sería muy difícil descomponer funciones racionales de grado superior a 10. Nosotros presentamos en esta breve nota un algoritmo para la descomposición de funciones racionales siguiendo la idea de Barton & Zippel en [4] para el caso de polinomios. Aunque nuestro algoritmo requiere en principio un número exponencial, en el grado de f, de operaciones en el cuerpo K, resulta en la práctica más eficiente que el de Zippel, pues se pueden descomponer funciones racionales de grado mucho mayor que la cota por él estimada.
@article{urn:eudml:doc:38498,
title = {Un algoritmo de descomposici\'on de funciones racionales mediante polinomios casi-separados.},
journal = {Extracta Mathematicae},
volume = {11},
year = {1996},
pages = {475-479},
zbl = {0959.12005},
mrnumber = {MR1456545},
language = {es},
url = {http://dml.mathdoc.fr/item/urn:eudml:doc:38498}
}
Alonso, César; Gutiérrez, Jaime; Recio, Tomás. Un algoritmo de descomposición de funciones racionales mediante polinomios casi-separados.. Extracta Mathematicae, Tome 11 (1996) pp. 475-479. http://gdmltest.u-ga.fr/item/urn:eudml:doc:38498/