Polinomio libre de cuadrados

En matemáticas , un polinomio libre de cuadrados es un polinomio univariado (sobre un cuerpo o un dominio de integridad ) que no tiene raíces múltiples en un cuerpo algebraicamente cerrado que contenga sus coeficientes. En característica 0, o sobre un cuerpo finito , un polinomio univariado es libre de cuadrados si y solo si no tiene como divisor ningún cuadrado de un polinomio no constante . ^{[ 1 ]} En aplicaciones de 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 . Lo contrario también es cierto y por lo tanto,${\displaystyle f}$es libre de cuadrados si y solo si${\displaystyle 1}$es el máximo común divisor del polinomio y su derivada. ^{[ 2 ]}

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 libres de cuadrados coprimos por pares (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 no nulo admite una factorización libre de cuadrados, que es única salvo la multiplicación y división de los factores por constantes no nulas. 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 se prefiere a menudo 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 fundamental en álgebra computacional .

Sobre un campo de característica 0, el cociente de${\displaystyle f}$por su máximo común divisor (MCD) con su derivada es el producto de la${\displaystyle a_{i}}$en la descomposición libre de cuadrados anterior. Sobre un campo perfecto de característica no nula p , este cociente es el producto de la${\displaystyle a_{i}}$de tal manera que i no sea un múltiplo de p . Cálculos adicionales del 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 que la del cálculo del MCD del polinomio de entrada y su derivada. Más precisamente, si${\displaystyle T_{n}}$es el tiempo necesario para calcular el MCD de dos polinomios de grado${\displaystyle n}$y el cociente de estos polinomios por el MCD, entonces${\displaystyle 2T_{n}}$es un límite superior para el tiempo necesario para calcular la descomposición libre de cuadrados completa.

También se conocen algoritmos para la descomposición sin cuadrados de polinomios multivariados , que generalmente proceden considerando un polinomio multivariado como un polinomio univariado con coeficientes polinómicos y aplicando recursivamente un algoritmo univariado. ^{[ 3 ]}

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

La entrada es, por lo tanto, un polinomio no nulo 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 por lo tanto

${\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${\displaystyle b_{1}=f/a_{0}}$,${\displaystyle c_{1}=f'/a_{0}}$y${\displaystyle d_{1}=c_{1}-b_{1}'}$, lo entendemos

${\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}.}$

Repitiendo este proceso hasta${\displaystyle b_{k+1}=1}$ encontramos todos los${\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 ${\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}';}$ hasta${\displaystyle b_{i}=1;}$ Producción${\displaystyle a_{1},\ldots ,a_{i-1}.}$

El grado de${\displaystyle c_{i}}$y${\displaystyle d_{i}}$es uno menos que el grado de${\displaystyle b_{i}.}$Como${\displaystyle f}$es el producto de la${\displaystyle b_{i},}$la suma de los grados de la${\displaystyle b_{i}}$es el grado de${\displaystyle f.}$Como la complejidad de los cálculos y divisiones del MCD aumenta de forma más que lineal con el grado, se deduce que el tiempo total de ejecución del bucle "repetir" 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á limitado superiormente por el doble del tiempo necesario para calcular el MCD de${\displaystyle f}$y${\displaystyle f'}$y el cociente de${\displaystyle f}$y${\displaystyle f'}$por su MCD.

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

Un polinomio tiene raíz cuadrada si y solo si todos los exponentes de su descomposición en polinomios libres de cuadrados son pares. En este caso, la raíz cuadrada se obtiene dividiendo dichos exponentes entre 2.

Así pues, el problema de determinar si un polinomio tiene raíz cuadrada, y de calcularla en caso afirmativo, es un caso particular de factorización sin cuadrado. En el apartado de Polinomios al Cuadrado se proporciona un algoritmo para calcular la raíz cuadrada .