Polinomio libre de cuadrados

En matemáticas, un polinomio libre de cuadrados (también denominado polinomio sin cuadrados, polinomio sin raíces repetidas o polinomio sin raíces múltiples) es un polinomio definido sobre un cuerpo (o más generalmente, un dominio de integridad) que no tiene como divisor ningún cuadrado de un polinomio no constante.^[1] Se dice que un polinomio está libre de cuadrados si y solo si no tiene multiplicidad en un cuerpo 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 como un polinomio sin raíces repetidas.

Propiedades[editar]

En el caso de polinomios de una sola variable, la regla del producto implica que, si $p 2$ divide a $f$ , entonces $p$ divide a la derivada formal $f'$ de $f$ . Lo contrario también es cierto en característica cero y para polinomios sobre un cuerpo finito (o, más generalmente, sobre un cuerpo perfecto). Es decir, en estos casos, un polinomio está libre de cuadrados si y solo si el máximo común divisor del polinomio y de su derivada es $1$ .

Una descomposición libre de cuadrados o factorización sin cuadrados de un polinomio es una factorización en potencias de polinomios libres de cuadrados

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

donde los $a k$ que no son constantes son polinomios libres de cuadrados coprimos dos a dos (aquí, dos polinomios se dice que son coprimos cuando su máximo común divisor es una constante; en otras palabras, que se verifica la coprimalidad sobre el cuerpo de fracciones de los coeficientes que se consideran).^[1] Todo polinomio distinto de cero de una factorización libre de cuadrados es única salvo por 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 descomposición en fracciones simples y integración simbólica de fracciones. La factorización sin cuadrados es el primer paso de los algoritmos de factorización de polinomios desarrollados en sistemas algebraicos computacionales. Por tanto, el algoritmo de factorización libre de cuadrados es básico en el cálculo simbólico.

Sobre un cuerpo de característica 0, el cociente de $f$ por su máximo común divisor con respecto a su derivada, es el producto de $a_{i}$ en la descomposición sin cuadrados anterior. Sobre un cuerpo perfecto de característica distinta de cero $p$ , este cociente es el producto de $a_{i}$ tal que $i$ no es un múltiplo de $p$ . Los cálculos adicionales del máximo común divisor (MCD) y las divisiones exactas permiten calcular la factorización libre de cuadrados (consúltese factorización libre de cuadrados sobre un cuerpo finito). Con 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 del cálculo del MCD del polinomio de entrada y su derivada. Más precisamente, si $T_{n}$ es el tiempo necesario para calcular el MCD de dos polinomios de grado $n$ y el cociente de estos polinomios por el MCD, entonces $2T_{n}$ es un límite superior del tiempo necesario para calcular la descomposición libre de cuadrados.

También existen algoritmos conocidos para el cálculo de la descomposición libre de cuadrados de polinomios, que proceden generalmente considerando un polinomio multivariable como un polinomio de una variable con coeficientes polinomiales, y aplicando recursivamente un algoritmo de una variable.^[2]

Algoritmo de Yun[editar]

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

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

Si

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

es la factorización deseada, se tiene que

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

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

y

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

Si se configuran $b_{1}=f/a_{0}$ , $c_{1}=f'/a_{0}$ y $d_{1}=c_{1}-b_{1}'$ , se obtiene que

{\text{MCD }}(b_{1},d_{1})=a_{1},

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

y

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 $b_{k+1}=1$ se encuentran todos los $a_{i}.$

Esto se formaliza en un algoritmo de la siguiente manera:

$a_{0}:={\text{MCD}}(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
$a_{i}:={\text{MCD}}(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}';$
until $b=1;$

Salida $a_{1},\ldots ,a_{i-1}.$

El grado de $c_{i}$ y $d_{i}$ es menor en una unidad que el grado de $b_{i}.$ Como $f$ es el producto de $b_{i},$ la suma de los grados de $b_{i}$ es el grado de $f.$ A medida que la complejidad de los cálculos y divisiones del MCD 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 del algoritmo de Yun está limitado por el doble del tiempo necesario para calcular el MCD de $f$ y de $f'$ y el cociente de $f$ y $f'$ por su MCD.

Raíz cuadrada[editar]

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 libre de cuadrados son pares. En este caso, la raíz cuadrada se obtiene dividiendo por 2 estos exponentes.

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.

Referencias[editar]

↑ ^a ^b ^c ^d Yun, David Y.Y. (1976). «On square-free decomposition algorithms». SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation. Association for Computing Machinery. pp. 26-35. ISBN 978-1-4503-7790-4. S2CID 12861227. doi:10.1145/800205.806320.
↑ Gianni, P.; Trager, B. (1996). «Square-Free Algorithms in Positive Characteristic». Applicable Algebra in Engineering, Communication and Computing 7 (1): 1-14. S2CID 36886948. doi:10.1007/BF01613611.

Enlaces externos[editar]

Portal:Matemáticas. Contenido relacionado con Matemáticas.

Datos: Q7581979

[yun-1] Yun, David Y.Y. (1976). «On square-free decomposition algorithms». SYMSAC '76 Proceedings of the third ACM symposium on Symbolic and algebraic computation. Association for Computing Machinery. pp. 26-35. ISBN 978-1-4503-7790-4. S2CID 12861227. doi:10.1145/800205.806320.

[gianni-2] Gianni, P.; Trager, B. (1996). «Square-Free Algorithms in Positive Characteristic». Applicable Algebra in Engineering, Communication and Computing 7 (1): 1-14. S2CID 36886948. doi:10.1007/BF01613611.

[1]

[2]