Polinomio sin cuadrados

Polinomio sin raíz repetida

En matemáticas , un polinomio libre de cuadrados es un polinomio univariante (sobre un cuerpo o un dominio integral ) que no tiene raíz múltiple en un cuerpo algebraicamente cerrado que contiene sus coeficientes. En característica 0, o sobre un cuerpo finito , un polinomio univariante es libre de cuadrados si y solo si no tiene como divisor ningún cuadrado de un polinomio no constante . ^[1] En aplicaciones en física e ingeniería, un polinomio libre de cuadrados se denomina comúnmente polinomio sin raíces repetidas .

La regla del producto implica que, si p ² divide a f , entonces p divide a la derivada formal f ′  de f . La inversa también es cierta y, por lo tanto, es libre de cuadrados si y solo si es el máximo común divisor del polinomio y su derivada. ^[2] ${\displaystyle f}$ ${\displaystyle 1}$

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.

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{n}^{n}=\prod _{k=1}^{n}a_{k}^{k}\,}$

donde aquellos de los a _k que no son constantes son polinomios coprimos por pares y libres de cuadrados (aquí, se dice que dos polinomios son coprimos si su máximo común divisor es una constante; en otras palabras, esa es la coprimalidad sobre el cuerpo de fracciones de los coeficientes que se considera). ^[1] Todo polinomio distinto de cero admite 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 irreducibles , y por lo tanto a menudo se prefiere cuando la factorización completa no es realmente necesaria, como para la descomposición en 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 de polinomios que se implementan en los sistemas de álgebra computacional . Por lo tanto, el algoritmo de factorización libre de cuadrados es básico en álgebra computacional .

Sobre un cuerpo de característica 0, el cociente de por su máximo común divisor (MCD) con su derivada es el producto de en la descomposición libre de cuadrados anterior. Sobre un cuerpo perfecto de característica p distinta de cero , este cociente es el producto de tal que i no es un múltiplo de p . Otros cálculos de MCD y divisiones exactas permiten calcular la factorización libre de cuadrados (véase factorización libre de cuadrados sobre un cuerpo finito ). En característica cero, se conoce un algoritmo mejor, el algoritmo de Yun, que se describe a continuación. ^[1] Su complejidad computacional es, como máximo, el doble de la del cálculo del 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 de cuadrados completa. ${\displaystyle f}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle T_{n}}$ ${\displaystyle n}$ ${\displaystyle 2T_{n}}$

También se conocen algoritmos para 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. ^[3]

Algoritmo de Yun

Esta sección describe el algoritmo de Yun para la descomposición libre de cuadrados de polinomios univariados sobre un campo de característica 0. [ ^1] Se desarrolla mediante una sucesión de cálculos de MCD y divisiones exactas.

La entrada es entonces un polinomio distinto de cero f , y el primer paso del algoritmo consiste en calcular el MCD a ₀ de f y su derivada formal f' .

Si

${\displaystyle f=a_{1}a_{2}^{2}a_{3}^{3}\cdots a_{k}^{k}}$

es la factorización deseada, tenemos entonces

${\displaystyle a_{0}=a_{2}^{1}a_{3}^{2}\cdots a_{k}^{k-1},}$

${\displaystyle f/a_{0}=a_{1}a_{2}a_{3}\cdots a_{k}}$

y

${\displaystyle f'/a_{0}=\sum _{i=1}^{k}ia_{i}'a_{1}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

Si establecemos , y , obtenemos que ${\displaystyle b_{1}=f/a_{0}}$ ${\displaystyle c_{1}=f'/a_{0}}$ ${\displaystyle d_{1}=c_{1}-b_{1}'}$

${\displaystyle \gcd(b_{1},d_{1})=a_{1},}$

${\displaystyle b_{2}=b_{1}/a_{1}=a_{2}a_{3}\cdots a_{n},}$

y

${\displaystyle c_{2}=d_{1}/a_{1}=\sum _{i=2}^{k}(i-1)a_{i}'a_{2}\cdots a_{i-1}a_{i+1}\cdots a_{k}.}$

Iterando este proceso hasta que encontremos todos los ${\displaystyle b_{k+1}=1}$ ${\displaystyle a_{i}.}$

Esto se formaliza en un algoritmo de la siguiente manera:

${\displaystyle a_{0}:=\gcd(f,f');\quad b_{1}:=f/a_{0};\quad c_{1}:=f'/a_{0};\quad d_{1}:=c_{1}-b_{1}';\quad i:=1;}$
repetir hasta salida
${\displaystyle a_{i}:=\gcd(b_{i},d_{i});\quad b_{i+1}:=b_{i}/a_{i};\quad c_{i+1}:=d_{i}/a_{i};\quad i:=i+1;\quad d_{i}:=c_{i}-b_{i}';}$
${\displaystyle b_{i}=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

El grado de y es uno menos que el grado de Como es el producto de la suma de los grados de es el grado de Como la complejidad de los cálculos y divisiones de MCD aumenta más que linealmente con el grado, se deduce que el tiempo total de ejecución del bucle de "repetición" es menor que el tiempo de ejecución de la primera línea del algoritmo, y que el tiempo total de ejecución del algoritmo de Yun está acotado superiormente por el doble del tiempo necesario para calcular el MCD de y y el cociente de y por su MCD. ${\displaystyle c_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle b_{i}.}$ ${\displaystyle f}$ ${\displaystyle b_{i},}$ ${\displaystyle b_{i}}$ ${\displaystyle f.}$ ${\displaystyle f}$ ${\displaystyle f'}$ ${\displaystyle f}$ ${\displaystyle f'}$

Raíz cuadrada

En general, un polinomio no tiene raíz cuadrada polinómica . Más precisamente, la mayoría de los polinomios no se pueden escribir como el cuadrado de otro polinomio.

Un polinomio tiene raíz cuadrada si y solo si todos los exponentes de la descomposición libre de cuadrados son pares. En este caso, la raíz cuadrada se obtiene dividiendo estos exponentes por 2.

Por lo 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

1. 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 . Association for Computing Machinery. págs. 26–35. doi :10.1145/800205.806320. ISBN 978-1-4503-7790-4.S2CID12861227  .​
2. Dummit, David S.; Foote, Richard M. (2004). Álgebra abstracta . pág. 547. ISBN 978-81-265-3228-5.
3. Gianni, P. ; Trager, B. (1996). "Algoritmos sin cuadrados en característica positiva". Álgebra aplicable en ingeniería, comunicación y computación . 7 (1): 1–14. doi :10.1007/BF01613611. S2CID  36886948.