Polinomio libre de cuadrados

Polinomio sin raíz repetida

En matemáticas , un polinomio libre de cuadrados es un polinomio definido sobre un cuerpo (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 libre de cuadrados si y sólo si no tiene raíz múltiple en un campo algebraicamente cerrado que contenga sus coeficientes. Esto motiva que, en aplicaciones en física e ingeniería, a un polinomio libre de cuadrados se le llame comúnmente polinomio sin raíces repetidas .

En el caso de polinomios univariados, la regla del producto implica que, si p ² divide a f , entonces p divide la derivada formal f '  de f . Lo contrario también es cierto y, por tanto, es libre de cuadrados si y sólo si es el máximo común divisor del polinomio y su derivada. ^[2] ${\displaystyle f}$ ${\displaystyle 1}$

Una descomposición sin cuadrados o factorización sin cuadrados de un polinomio es una factorización en potencias de polinomios sin 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 a _k que no son constantes son polinomios libres de cuadrados coprimos por pares (aquí, se dice que dos polinomios coprimos son 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 sin cuadrados es el primer paso de los algoritmos de factorización polinomial que se implementan en los sistemas de álgebra informática . Por tanto, el algoritmo de factorización libre de cuadrados es básico en álgebra informática .

Sobre un campo 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 sin cuadrados anterior. Sobre un campo perfecto de característica distinta de cero p , este cociente es el producto de tal que i no es múltiplo de p . Otros cálculos de MCD y divisiones exactas permiten calcular la factorización sin cuadrados (ver factorización sin cuadrados sobre 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 máximo, el doble que 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. ${\displaystyle f}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle T_{n}}$ ${\displaystyle n}$ ${\displaystyle 2T_{n}}$

También se conocen algoritmos para el cálculo de la descomposición libre de cuadrados de polinomios multivariados , que proceden generalmente considerando un polinomio multivariado como un polinomio univariado con coeficientes polinomiales, y aplicando recursivamente un algoritmo univariado. ^[3]

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 MCD y divisiones exactas.

La entrada es, por tanto, un polinomio f distinto de cero , 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, así tenemos

${\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 configuramos y obtenemos eso ${\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 la 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=1;}$
${\displaystyle a_{1},\ldots ,a_{i-1}.}$

El grado de y es uno menos que el grado de As es el producto de la suma de los grados de es el grado de 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 total acumulado el tiempo del ciclo 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á limitado superiormente por el doble del tiempo necesario para calcular el MCD de y y el cociente de y por su GCD. ${\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 . 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 sólo si todos los exponentes de la descomposición libre de cuadrados son pares. En este caso, se obtiene una raíz cuadrada dividiendo estos exponentes por 2.

Por tanto, el problema de decidir si un polinomio tiene raíz cuadrada y 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 . Asociación para Maquinaria de Computación. págs. 26–35. doi :10.1145/800205.806320. ISBN 978-1-4503-7790-4. S2CID  12861227.
2. Tonto, David S.; Foote, Richard M. (2004). Álgebra abstracta . pag. 547.ISBN​ 978-81-265-3228-5.
3. Gianni, P .; Trager, B. (1996). "Algoritmos libres de cuadrados en característica positiva". Álgebra Aplicable en Ingeniería, Comunicaciones y Computación . 7 (1): 1–14. doi :10.1007/BF01613611. S2CID  36886948.