En matemáticas , un polinomio libre de cuadrados es un polinomio definido sobre un campo (o más generalmente, un dominio integral ) que no tiene como divisor ningún cuadrado de un polinomio no constante . [1] Un polinomio univariado es cuadrado libre si y solo si no tiene raíz múltiple en un campo algebraicamente cerrado que contiene sus coeficientes. Esto motiva que en aplicaciones de física e ingeniería, un polinomio libre de cuadrados se denomina comúnmente polinomio sin raíces repetidas .
En el caso de polinomios univariados, la regla del producto implica que, si p 2 divide f , entonces p divide la derivada formal f ' de f . Lo contrario también es cierto en la característica cero y para polinomios sobre un campo finito (o, más generalmente, sobre un campo perfecto ). Es decir, en estos casos, un polinomio es cuadrado libre si y solo si 1 es el máximo común divisor del polinomio y su derivada.
Una descomposición libre de cuadrados o factorización libre de cuadrados de un polinomio es una factorización en potencias de polinomios libres de cuadrados
donde los de a k que no son constantes son polinomios libres de cuadrados coprimos por pares (aquí, dos polinomios se dice que el coprimo es su máximo común divisor es una constante; en otras palabras, es la coprimalidad sobre el campo de fracciones de los coeficientes que se considera). [1] Todo polinomio distinto de cero es una factorización libre de cuadrados, que es única hasta la multiplicación y división de los factores por constantes distintas de cero. La factorización libre de cuadrados es mucho más fácil de calcular que la factorización completa en factores irreductibles y, por lo tanto, a menudo se prefiere cuando la factorización completa no es realmente necesaria, como para la descomposición de fracciones parciales y la integración simbólica de fracciones racionales . La factorización libre de cuadrados es el primer paso de los algoritmos de factorización polinomial que se implementan en los sistemas de álgebra computarizada . Por lo tanto, el algoritmo de factorización libre de cuadrados es básico en álgebra computacional .
Sobre un campo de característica 0, el cociente de por su MCD con su derivada es el producto de la en la descomposición sin cuadrados anterior. Sobre un campo perfecto de característica p distinta de cero , este cociente es el producto de latal que i no es un múltiplo de p . Los cálculos adicionales de GCD y las divisiones exactas permiten calcular la factorización sin cuadrados (consulte la factorización sin cuadrados en un campo finito ). En la característica cero, se conoce un algoritmo mejor, el algoritmo de Yun, que se describe a continuación. [1] Su complejidad computacional es, como mucho, el doble de la del cálculo MCD del polinomio de entrada y su derivada. Más precisamente, si es el tiempo necesario para calcular el MCD de dos polinomios de grado y el cociente de estos polinomios por el MCD, entonces es un límite superior para el tiempo necesario para calcular la descomposición libre al cuadrado.
También existen algoritmos conocidos para el cálculo de la descomposición libre de cuadrados de polinomios multivariados , que proceden generalmente considerando un polinomio multivariado como un polinomio univariante con coeficientes polinomiales, y aplicando recursivamente un algoritmo univariante. [2]
Algoritmo de Yun
Esta sección describe el algoritmo de Yun para la descomposición sin cuadrados de polinomios univariados sobre un campo de característica 0 . [1] Procede mediante una sucesión de cálculos GCD y divisiones exactas.
Por tanto, la entrada es un polinomio f distinto de cero , y el primer paso del algoritmo consiste en calcular el MCD a 0 de f y su derivada formal f ' .
Si
es la factorización deseada, tenemos así
y
Si ponemos , y , lo entendemos
y
Iterando este proceso hasta encontramos todos los
Esto se formaliza en un algoritmo de la siguiente manera:
repetir
Hasta que
Producción
El grado de y es uno menos que el grado de Como es el producto de la la suma de los grados del es el grado de Como la complejidad de los cálculos y las divisiones de GCD aumenta más que linealmente con el grado, se deduce que el tiempo de ejecución total del ciclo de "repetición" es menor que el tiempo de ejecución de la primera línea del algoritmo, y que el tiempo de ejecución total de El algoritmo de Yun está limitado por el doble del tiempo necesario para calcular el MCD de y y el cociente de y por su GCD.
Raíz cuadrada
En general, un polinomio no tiene raíz cuadrada . Más precisamente, la mayoría de los polinomios no se pueden escribir como el cuadrado de otro polinomio.
Un polinomio tiene una raíz cuadrada si y solo si todos los exponentes de la descomposición sin cuadrados son pares. En este caso, la raíz cuadrada se obtiene dividiendo por 2 estos exponentes.
Por tanto, el problema de decidir si un polinomio tiene raíz cuadrada y de calcularla si existe, es un caso especial de factorización libre de cuadrados.
Notas
Referencias
- ↑ a b c d Yun, David YY (1976). "Sobre algoritmos de descomposición sin cuadrados" . SYMSAC '76 Actas del tercer simposio ACM sobre computación simbólica y algebraica. Asociación para Maquinaria de Computación. págs. 26–35. doi : 10.1145 / 800205.806320 . ISBN 978-1-4503-7790-4. S2CID 12861227 .
- ^ Gianni, P .; Trager, B. (1996). "Algoritmos cuadrados libres en característica positiva". Álgebra aplicable en Ingeniería, Comunicación y Computación . 7 (1): 1-14. doi : 10.1007 / BF01613611 . S2CID 36886948 .