Factorización de polinomis

En les matemàtiques i àlgebra computacional, la factorización de polinomis o factorización polinòmica es referix a factorizar un polinomi en coeficients en un camp dau o en els número entero en factors irreducibles en coeficients en el mateix domini. Factorización polinòmica és una de les ferramentes fonamentals dels sistemes d'àlgebra computacional.

Eixemple

L'història de la factorización polinòmica comença en Hermann Schubert qui en 1793 va descriure el primer algoritme d'factorización de polinomis, i Leopold Kronecker, qui redescubrió l'algoritme de Schubert en 1882 i la va ampliar a polinomis multivariados i en coeficients en una extensió algebraica. Pero la major part dels coneiximents sobre este tema no és major que al voltant de l'any 1965 i els primers sistemes d'àlgebra computacional. En una entrevista sobre el tema, Erich Kaltofen va escriure en 1982 (vore la bibliografia):

Quan els algoritmes de passos finitos llarc temps coneguts es varen posar per primera volta en els ordenadors, varen resultar ser altament ineficiente. El fet de que casi qualsevol polinomi uni o multivariado de fins a grau 100 i en coeficients de tamany moderat (fins a 100 bits) es pot factorizar per mig d'algoritmes moderns en uns pocs minuts indica l'èxit en que este problema s'ha atacat durant els últims quinze anys.

Formulació

Anells de polinomis sobre els sancers o sobre un camp són dominis d'factorización única. Açò significa que cada element d'estos anells és el producte d'una constant i el producte de polinomis irreducibles (aquells que no són el producte de dos polinomis no constants). Per una atra part, esta descomposició és única fins a la multiplicació dels factors per constants invertibles.

La factorización depén del camp base. Per eixemple, el teorema fonamental de l'àlgebra, que establix que tot polinomi en coeficients complexos té raïls complexes, implica que un polinomi en coeficients sancers es pot factorizar (per mig d'algoritmes numèrics) en factors llineals sobre els número complejo. De la mateixa manera, sobre els número real, els factors irreducibles tenen grau com a molt dos, mentres que hi ha polinomis de qualsevol grau que són irreducible sobre els número racional.

La factorización polinòmica només té sentit per a coeficients en un camp computable en a on cada element pot ser representat en una computadora i existixquen algoritmes per a les operacions aritmètiques. Fröhlich i Shepherson han proporcionat eixemples d'estos camps per als que pugues no existir cap algoritme d'factorización.

Els camps dels coeficients per als que es coneixen algoritmes d'factorización inclouen camps principals (és dir, els número racional i l'aritmètica modular sobre cosins) i les seues extensions de camp finito. Coeficients sancers també són manejables: el método de Kronecker només és interessant des d'un punt de vista històric, els algoritmes moderns provenen d'una successió de:

• Factorización sense radicals
• Factorización sobre camps finitos

i reduccions:

• Des del cas multivariado al univariado.
• Des de coeficients en una extensió purament transcendental al cas multivariado sobre el camp base (vore més avall)
• Des de coeficients en una extensió algebraica a coeficients en el camp base
• Des de coeficients racionals a coeficients sancers (vore més avall)
• Des de coeficients sancers a coeficients en un camp primer en p elements, per a cert p.

Factorización primitiva basada en contingut

En esta secció, es mostra que la factorización sobre Q (els número racional) i sobre Z (els sancers) és essencialment el mateix problema.

El contingut d'un polinomi p ∈ Z[X], denotat com "cont(p)", és, fins al seu signe, el màxim comú divisor dels seus coeficients. La part primitiva de p és primpart(p)=p/cont(p), que és un polinomi primitiu en coeficients sancers. Açò definix una factorización de p com el producte d'un número entero i un polinomi primitiu. Esta factorización és única fins al signe del contingut. És usual elegir el signe del contingut tal que el coeficient principal de la part primitiva siga positiu.

Per eixemple,

$-10x^2+5x+5=(-5)\cdot (2x^2-x-1)$

és una factorización en el contingut i la part primitiva.

Cada polinomi Q en coeficients racionals pot ser escrit com

$q=\frac{p}{c},$

a on p ∈ Z[X] i C ∈ Z: n'hi ha prou en prendre per a C un múltiple de tots els denominadors dels coeficients de Q (per eixemple, el seu producte) i p = cq. El contingut de Q es definix com:

$\text{cont}(q)=\frac{\text{cont}(p)}{c},$

i la part primitiva de q és la de p. Sobre els polinomis en coeficients sancers, açò definix una factorización en un número racional i un polinomi primitiu en coeficients sancers. Esta factorización és també única fins a l'elecció del signe.

Per eixemple,

$\frac{1}{3}{x}^5+\frac{7}{2}{x}^2+2x+1=\frac{1}{6}(2x^5+21x^2+12x+6)$

és una factorización en el contingut i la part primitiva.

Gauss va demostrar en primer lloc que el producte de dos polinomis primitius també és primitiu (Lema de Gauss). Açò implica que un polinomi primitiu és irreducible sobre els racionals si i només si és irreducible sobre els número entero. Ademés implica que la factorización sobre els número racional d'un polinomi en coeficients racionals és la mateixa que la factorización sobre els número entero de la seua part primitiva. Per un atre costat, la factorización sobre els número entero d'un polinomi en coeficients sancers és el producte de la factorización de la seua part primitiva per la factorización del seu contingut.

En atres paraules, integer GDD computation permet reduir la factorización d'un polinomi sobre els número racional a la factorización d'un polinomi primitiu en coeficients sancers, i reduir la factorización sobre els número entero a la factorización d'un número entero i un polinomi primitiu.

Tot lo anterior se seguix complint si Z és substituït per un anell de polinomis sobre un camp F i Q se substituïx per un camp de cocients racionals sobre F en les mateixes variables, en l'única diferència de que "fins a un signe" deu substituir-se per "fins a la multiplicació per una constant invertible en F". Açò permet reduir la factorización sobre una extensió purament transcendent de F a la factorización de polinomis multivariados sobre F.

Referències

• (1955).«On the factorisation of polynomials in a finite number of steps».Mathematische Zeitschrift.62(1)ISSN 0025-5874.
• «Algebraic Factoring and Rational Function Integration».Proc. SYMSAC 76 http://dl.acm.org/citation.cfm?aneu=806338.
• (accessible to readers with undergraduate mathematics)
• (1993) A course in computational algebraic number theory, Berlin, New York: Springer-Verlag. ISBN 978-3-540-55640-4.
• (1982).«Computer Algebra».Springer Verlag.Consultat el 20 de setembre de 2012.

• (1982).Mathematische Annalen.261(4)

515–534.ISSN 0025-5831.doi:10.1007/BF01457454.

• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.