Descomposición polinómica

En matemáticas, una descomposición polinómica expresa un polinomio f como la composición funcional.${\displaystyle g\circ h}$de polinomios g y h , donde g y h tienen grado mayor que 1; es una descomposición funcional algebraica . Se conocen algoritmos para descomponer polinomios univariados en tiempo polinomial .

Los polinomios que se pueden descomponer de esta manera son polinomios compuestos ; los que no se pueden descomponer son polinomios indescomponibles o, a veces, polinomios primos ^{[ 1 ]} (que no deben confundirse con los polinomios irreducibles , que no se pueden factorizar en productos de polinomios ). El grado de un polinomio compuesto es siempre un número compuesto , el producto de los grados de los polinomios que lo componen.

El resto de este artículo trata únicamente sobre polinomios univariados; también existen algoritmos para polinomios multivariados de grado arbitrario. ^{[ 2 ] [ 3 ] [ 4 ]}

En el caso más simple, uno de los polinomios es un monomio . Por ejemplo,

${\displaystyle f(x)=x^{6}-3x^{3}+1}$

se descompone en${\displaystyle g\circ h}$, dónde

${\displaystyle g(x)=x^{2}-3x+1{\text{ y }}h(x)=x^{3}}$

desde

${\displaystyle f(x)=(g\circ h)(x)=g(h(x))=g(x^{3})=(x^{3})^{2}-3(x^{3})+1,}$

utilizando el símbolo del operador de anillo${\displaystyle {\boldsymbol {\circ }}}$para denotar la composición de funciones . Lo escribimos como

${\displaystyle x^{6}-3x^{3}+1=(x^{2}-3x+1)\circ (x^{3})}$

tratar los polinomios implícitamente como funciones de${\displaystyle x}$.

Menos trivial,

${\displaystyle {\begin{aligned}&x^{6}-6x^{5}+21x^{4}-44x^{3}+68x^{2}-64x+41\\={}&(x^{3}+9x^{2}+32x+41)\circ (x^{2}-2x).\end{aligned}}}$

Un polinomio puede tener distintas descomposiciones en polinomios indescomponibles donde${\displaystyle f=g_{1}\circ g_{2}\circ \cdots \circ g_{m}=h_{1}\circ h_{2}\circ \cdots \circ h_{n}}$dónde${\displaystyle g_{i}\neq h_{i}}$para algunos${\displaystyle i}$La restricción en la definición a polinomios de grado mayor que uno excluye las infinitas descomposiciones posibles con polinomios lineales.

Joseph Ritt demostró que${\displaystyle m=n}$y los grados de los componentes son los mismos, pero posiblemente en diferente orden; este es el teorema de descomposición polinomial de Ritt . ^{[ 1 ] [ 5 ]} Por ejemplo,${\displaystyle x^{2}\circ x^{3}=x^{3}\circ x^{2}}$De hecho, solo son posibles tres tipos de intercambio de posiciones: entre monomios; entre polinomios de Chebyshev${\displaystyle T_{i}(x)}$; y entre${\displaystyle \left(x^{k}\,u\left(x\right)^{p},x^{p}\right)\leftrightarrow \left(x^{p},x^{k}\,u\left(x^{p}\right)\right)}$— resumido como "Todo polinomio puede escribirse como una composición de indescomponibles, de forma única salvo permutaciones y unidades." ^{[ 6 ]} Por ejemplo:

${\displaystyle x^{14}\,\left(x^{98}+1\right)^{2}=\left(x\,\left(x^{7}+1\right)^{2}\right)\circ \left(x^{7}\right)\circ \left(x^{2}\right)=\left(x^{2}\right)\circ \left(x\,\left(x^{14}+1\right)\right)\circ \left(x^{7}\right)}$

${\displaystyle T_{2}(x)\circ T_{3}(x)=T_{3}(x)\circ T_{2}(x)=32\,x^{6}-48\,x^{4}+18\,x^{2}-1}$

Una descomposición polinómica puede permitir una evaluación más eficiente de un polinomio. Por ejemplo,

${\displaystyle {\begin{aligned}&x^{8}+4x^{7}+10x^{6}+16x^{5}+19x^{4}+16x^{3}+10x^{2}+4x-1\\={}&\left(x^{2}-2\right)\circ \left(x^{2}\right)\circ \left(x^{2}+x+1\right)\end{aligned}}}$

can be calculated with 3 multiplications and 3 additions using the decomposition, while Horner's method would require 7 multiplications and 8 additions.

A polynomial decomposition enables calculation of symbolic roots using radicals, even for some irreducible polynomials of degree greater than 4. This technique is used in many computer algebra systems.^[7] For example, using the decomposition

${\displaystyle {\begin{aligned}&x^{6}-6x^{5}+15x^{4}-20x^{3}+15x^{2}-6x-1\\={}&\left(x^{3}-2\right)\circ \left(x^{2}-2x+1\right),\end{aligned}}}$

the roots of this irreducible polynomial can be calculated as^[8]

${\displaystyle 1\pm 2^{1/6},1\pm {\frac {\sqrt {-1\pm {\sqrt {3}}i}}{2^{1/3}}}.}$

In the case of quartic polynomials, if there is a decomposition, it can give a simpler form than the general formula. For example, the decomposition

${\displaystyle {\begin{aligned}&x^{4}-8x^{3}+18x^{2}-8x+2\\={}&(x^{2}+1)\circ (x^{2}-4x+1)\end{aligned}}}$

gives the roots^[8]

${\displaystyle 2\pm {\sqrt {3\pm i}}}$

but straightforward application of the quartic formula gives a form that is difficult to simplify and difficult to understand; one of the four roots is:

${\displaystyle 2-{\frac {\sqrt {{9\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{2/3}+36\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}+156} \over {\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}}{6}}-{{\sqrt {-\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}-{{52} \over {3\left({\frac {8{\sqrt {10}}i}{3^{3/2}}}+72\right)^{1/3}}}+8}} \over 2}.}$

The first algorithm for polynomial decomposition was published in 1985,^[9] though it had been discovered in 1976,^[10] and implemented in the Macsyma/Maximacomputer algebra system.^[11] That algorithm takes exponential time in worst case, but works independently of the characteristic of the underlying field.

A 1989 algorithm runs in polynomial time but with restrictions on the characteristic.^[12]

A 2014 algorithm calculates a decomposition in polynomial time and without restrictions on the characteristic.^[13]

• Joel S. Cohen (2003). «Capítulo 5. Descomposición polinómica». Álgebra computacional y computación simbólica: métodos matemáticos . ISBN 1-56881-159-4.