Factorización de polinomios

Todos los factores lineales con coeficientes racionales se pueden encontrar utilizando la prueba de la raíz racional . Si el polinomio a factorizar es${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$, entonces todos los posibles factores lineales son de la forma${\displaystyle b_{1}x-b_{0}}$, dónde${\displaystyle b_{1}}$es un factor entero de${\displaystyle a_{n}}$y${\displaystyle b_{0}}$es un factor entero de${\displaystyle a_{0}}$Se pueden probar todas las combinaciones posibles de factores enteros, y cada una válida se puede factorizar mediante la división larga de polinomios . Si el polinomio original es producto de factores de los cuales al menos dos son de grado 2 o superior, esta técnica solo proporciona una factorización parcial; de lo contrario, la factorización es completa. En particular, si hay exactamente un factor no lineal, será el polinomio que queda después de factorizar todos los factores lineales. En el caso de un polinomio cúbico , si el cúbico es factorizable, la prueba de la raíz racional proporciona una factorización completa, ya sea en un factor lineal y un factor cuadrático irreducible, o en tres factores lineales.

El método de Kronecker tiene como objetivo factorizar polinomios univariados con coeficientes enteros en polinomios con coeficientes enteros.

El método utiliza el hecho de que evaluar polinomios enteros en valores enteros debe producir números enteros. Es decir, si${\displaystyle f(x)}$es un polinomio con coeficientes enteros, entonces${\displaystyle f(a)}$es un número entero tan pronto como a sea un número entero. Solo hay un número finito de posibles valores enteros para un factor de a . Entonces, si${\displaystyle g(x)}$es un factor de${\displaystyle f(x),}$el valor de${\displaystyle g(a)}$debe ser uno de los factores de${\displaystyle f(a).}$

Si uno busca todos los factores de un grado dado d , puede considerar${\displaystyle d+1}$valores,${\displaystyle a_{0},\ldots ,a_{d}}$para a , que dan un número finito de posibilidades para la tupla${\displaystyle (f(a_{0}),\ldots ,f(a_{d})).}$Cada${\displaystyle f(a_{i})}$tiene un número finito de divisores${\displaystyle b_{i,0},\ldots ,b_{i,k_{i}}}$y, cada uno${\displaystyle (d+1)}$-tupla donde el${\displaystyle i^{\text{th}}}$la entrada es un divisor de${\displaystyle f(a_{i})}$, es decir, una tupla de la forma${\displaystyle (b_{0,j_{1}},\ldots ,b_{d,j_{d}})}$, produce un polinomio único de grado como máximo${\displaystyle d}$, que se puede calcular mediante interpolación polinómica . Cada uno de estos polinomios se puede comprobar para determinar si es un factor mediante división polinómica . Dado que había un número finito de${\displaystyle a_{i}}$y cada uno${\displaystyle f(a_{i})}$tiene un número finito de divisores, hay un número finito de tales tuplas. Por lo tanto, una búsqueda exhaustiva permite encontrar todos los factores de grado como máximo d .

Por ejemplo, considere

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$.

Si este polinomio se factoriza sobre Z , entonces al menos uno de sus factores${\displaystyle p(x)}$debe ser de grado dos o inferior, por lo tanto${\displaystyle p(x)}$está determinado de forma única por tres valores . Por lo tanto, calculamos tres valores.${\displaystyle f(0)=2}$,${\displaystyle f(1)=6}$y${\displaystyle f(-1)=2}$. Si uno de estos valores es 0, tenemos un factor lineal. Si los valores son distintos de cero, podemos enumerar las posibles factorizaciones para cada uno. Ahora bien, 2 solo puede factorizarse como

1×2, 2×1, (−1)×(−2), o (−2)×(−1).

Por lo tanto, si existe un factor polinómico entero de segundo grado, debe tomar uno de los valores

p (0) = 1, 2, −1 o −2

y lo mismo para p (−1). Hay ocho factorizaciones de 6 (cuatro para 1×6 y cuatro para 2×3), lo que da un total de 4×4×8 = 128 posibles tríos ( p (0), p (1), p (−1)), de los cuales la mitad se puede descartar como los negativos de la otra mitad. Por lo tanto, debemos comprobar 64 polinomios enteros explícitos.${\displaystyle p(x)=ax^{2}+bx+c}$como posibles factores de${\displaystyle f(x)}$. Probarlos exhaustivamente revela que

${\displaystyle p(x)=x^{2}+x+1}$

construido a partir de ( g (0), g (1), g (−1)) = (1,3,1) factores${\displaystyle f(x)}$.

Dividiendo f ( x ) entre p ( x ) se obtiene el otro factor.${\displaystyle q(x)=x^{3}-x+2}$, de modo que${\displaystyle f(x)=p(x)q(x)}$Ahora se puede probar recursivamente para encontrar factores de p ( x ) y q ( x ), en este caso usando la prueba de la raíz racional. Resulta que ambos son irreducibles, por lo que la factorización irreducible de f ( x ) es: ^{[ 5 ]}

${\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).}$

Si${\displaystyle f(x)}$es un polinomio univariado sobre los enteros, que se supone libre de contenido y libre de cuadrados , se comienza calculando una cota${\displaystyle B}$de tal manera que cualquier factor${\displaystyle g(x)}$tiene coeficientes de valor absoluto acotados por${\displaystyle B}$De esta manera, si${\displaystyle m}$es un número entero mayor que${\displaystyle 2B}$y si${\displaystyle g(x)}$se conoce módulo${\displaystyle m}$, entonces${\displaystyle g(x)}$puede reconstruirse a partir de su modificación de imagen${\displaystyle m}$.

El algoritmo de Zassenhaus procede de la siguiente manera. Primero, elija un número primo.${\displaystyle p}$de tal manera que la imagen de${\displaystyle f(x){\bmod {p}}}$permanece libre de cuadrados y del mismo grado que${\displaystyle f(x)}$Una elección aleatoria casi siempre satisfará estas restricciones, ya que solo un número finito de números primos no las satisfacen, a saber, los divisores primos del producto del discriminante y el coeficiente principal del polinomio. Luego factoriza .${\displaystyle f(x){\bmod {p}}}$Esto produce polinomios enteros.${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$cuyo producto coincide${\displaystyle f(x){\bmod {p}}}$. A continuación, aplique el levantamiento de Hensel ; esto actualiza el${\displaystyle f_{i}(x)}$de tal manera que su producto coincida${\displaystyle f(x){\bmod {p}}^{a}}$, dónde${\displaystyle a}$es lo suficientemente grande como para${\displaystyle p^{a}}$supera${\displaystyle 2B}$: así cada uno${\displaystyle f_{i}(x)}$corresponde a un polinomio entero bien definido. Módulo${\displaystyle p^{a}}$, el polinomio${\displaystyle f(x)}$tiene${\displaystyle 2^{r}}$factores (hasta unidades): los productos de todos los subconjuntos de${\displaystyle \{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}}$. Estos factores módulo${\displaystyle p^{a}}$no tienen por qué corresponder a los factores "verdaderos" de${\displaystyle f(x)}$en${\displaystyle \mathbb {Z} [x]}$, pero podemos probarlos fácilmente mediante división en${\displaystyle \mathbb {Z} [x]}$De esta forma, todos los factores verdaderos irreducibles se pueden encontrar comprobando como máximo${\displaystyle 2^{r}}$casos, reducidos a${\displaystyle 2^{r-1}}$casos omitiendo complementos. Si${\displaystyle f(x)}$es reducible, el número de casos se reduce aún más eliminando aquellos${\displaystyle f_{i}(x)}$que aparecen en un factor verdadero ya encontrado. El algoritmo de Zassenhaus procesa cada caso (cada subconjunto) rápidamente; sin embargo, en el peor de los casos, considera un número exponencial de casos.

El primer algoritmo de tiempo polinomial para factorizar polinomios racionales fue descubierto por Lenstra, Lenstra y Lovász y es una aplicación del algoritmo de reducción de base reticular (LLL) de Lenstra-Lenstra-Lovász . ^{[ 6 ]}

Una versión simplificada del algoritmo de factorización LLL es la siguiente: calcular una raíz compleja (o p -ádica) α del polinomio${\displaystyle f(x)}$a alta precisión, luego utilice el algoritmo de reducción de base reticular Lenstra-Lenstra-Lovász para encontrar una relación lineal aproximada entre 1, α , α ² , α ³ , . . . con coeficientes enteros, que podría ser una relación lineal exacta y un factor polinomial de${\displaystyle f(x)}$Se puede determinar un límite de precisión que garantice que este método produzca un factor o una prueba de irreducibilidad. Si bien este método finaliza en tiempo polinomial, no se utiliza en la práctica debido a que la red tiene alta dimensión y entradas muy grandes, lo que ralentiza el cálculo.

La complejidad exponencial en el algoritmo de Zassenhaus proviene de un problema combinatorio: cómo seleccionar los subconjuntos correctos de${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$. Las implementaciones de factorización de última generación funcionan de manera similar a Zassenhaus, excepto que el problema combinatorio se traduce a un problema de retículo que luego se resuelve mediante LLL. ^{[ 7 ]} En este enfoque, LLL no se utiliza para calcular coeficientes de factores, sino para calcular vectores con${\displaystyle r}$entradas en {0,1} que codifican los subconjuntos de${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$correspondientes a los factores verdaderos irreducibles.

Podemos factorizar un polinomio${\displaystyle p(x)\in K[x]}$donde el campo${\displaystyle K}$es una extensión finita de${\displaystyle \mathbb {Q} }$Primero, utilizando la factorización libre de cuadrados , podemos suponer que el polinomio es libre de cuadrados. A continuación, definimos el anillo cociente.${\displaystyle L=K[x]/p(x)}$de grado${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$; este no es un campo a menos que${\displaystyle p(x)}$es irreducible, pero es un anillo reducido ya que${\displaystyle p(x)}$es libre de cuadrados. De hecho, si

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$

es la factorización deseada de p ( x ), el anillo se descompone de forma única en cuerpos como:

${\displaystyle L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).}$

Encontraremos esta descomposición sin conocer la factorización. Primero, escribimos L explícitamente como un álgebra sobre${\displaystyle \mathbb {Q} }$: elegimos un elemento aleatorio${\displaystyle \alpha \in L}$, que genera${\displaystyle L}$encima${\displaystyle \mathbb {Q} }$con alta probabilidad por el teorema del elemento primitivo . Si este es el caso, podemos calcular el polinomio mínimo.${\displaystyle q(y)\in \mathbb {Q} [y]}$de${\displaystyle \alpha }$encima${\displaystyle \mathbb {Q} }$, al encontrar un${\displaystyle \mathbb {Q} }$-relación lineal entre 1, α , . . . , α ⁿ . Usando un algoritmo de factorización para polinomios racionales, factorizamos en irreducibles en${\displaystyle \mathbb {Q} [y]}$:

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y).}$

Así pues, tenemos:

${\displaystyle L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),}$

dónde${\displaystyle \alpha }$corresponde a${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$. Esto debe ser isomorfo a la descomposición anterior de${\displaystyle L}$.

Los generadores de L son x junto con los generadores de${\displaystyle K}$encima${\displaystyle \mathbb {Q} }$; escribiendo estos como polinomios en${\displaystyle \alpha }$, podemos determinar las incrustaciones de${\displaystyle x}$y${\displaystyle K}$en cada componente${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$. Al encontrar el polinomio mínimo de${\displaystyle x}$en${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$, calculamos${\displaystyle p_{i}(x)}$y por lo tanto factor${\displaystyle p(x)}$encima${\displaystyle K.}$

En general, la mayoría de los polinomios no tienen raíces cuadradas. Sin embargo, algunas aplicaciones, como la función de los ingenieros eléctricos para obtener los parámetros Y a partir de la impedancia de un punto de excitación de una red de dos puertos, ^{[ 8 ]} sí utilizan polinomios al cuadrado que deben factorizarse en dos polinomios idénticos de raíz cuadrada. El siguiente algoritmo factorizará un polinomio al cuadrado,${\displaystyle {\sqrt {x^{6}-6x^{5}+17x^{4}-36x^{3}+52x^{2}+48x+36}}}$, en dos raíces polinómicas idénticas,${\displaystyle R=X^{3}-3x^{2}+4x-6}$, utilizando un ejemplo de Mathematics Stack Exchange . ^{[ 9 ] [ 10 ]}

${\displaystyle {\begin{aligned}&{\begin{array}{|l|l|l|}\hline Q&R&R(2Q+R)\\\hline \\0&x^{3}&x^{6}\\\hline \\x^{3}&-3x^{2}&6x^{5}-9x^{4}\\\hline \\x^{3}-3x^{2}&4x&8x^{4}-24x^{3}+16x^{2}\\\hline \\x^{3}-3x^{2}+4x&-6&-12x^{3}+36x^{2}-48x+36\\\hline \end{array}}&{\begin{array}{|c|c|c|c|c|c|c|c|}\hline R&x^{3}&&-3x^{2}&&4x&&-6\\\hline 1&x^{6}&-6x^{5}&17x^{4}&-36x^{3}&52x^{2}&48x&36\\&x^{6}&&&&&&\\\hline 2&&-6x^{5}&17x^{4}&&&&\\&&-6x^{5}&9x^{4}&&&&\\\hline 3&&&8x^{4}&-36x^{3}&52x^{2}&&\\&&&8x^{4}&-24x^{3}&16x^{2}&&\\\hline 4&&&&-12x^{3}&36x^{2}&-48x&36\\&&&&-12x^{3}&36x^{2}&-48x&36\\\hline \end{array}}\end{aligned}}}$

Pasos:

Paso 1: Calcular la raíz cuadrada del término principal,${\displaystyle x^{6}}$y colócalo,${\displaystyle x^{3}}$, en el término principal de la solución R, fila de la solución polinómica en la parte superior, y coloque el${\displaystyle x^{6}}$término en la fila 1 justo debajo del polinomio que se va a factorizar, como se muestra.

Paso 2: Restar el valor recién colocado${\displaystyle x^{6}}$del polinomio que se va a factorizar, y bajar los dos términos siguientes a la fila 2.

Paso 3 : Duplique el estado actual del polinomio R de la solución, luego agregue un nuevo término, Q, de tal manera que R(2Q+R) niegue el término principal de la fila 2, y coloque el negativo de R(2Q+R) en el espacio inferior de la fila 2.

Paso 4: Resta los dos números de la fila 2, coloca los resultados en la fila 3 y baja los dos términos siguientes de la fila 1 a la fila 3.

Paso 5: Repita el proceso para todas las filas y columnas restantes hasta completarlo.

Una vez completado, el polinomio R de la solución aparecerá en la columna R de la tabla de la izquierda y en la fila R de la tabla de la derecha.