Factorisació de polinomis

En les matemàtiques i àlgebra computacional, la factorisació de polinomis o factorisació 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. Factorisació polinòmica és una de les ferramentes fonamentals dels sistemes d'àlgebra computacional.

Eixemple

L'història de la factorisació polinòmica comença en Hermann Schubert qui en 1793 va descriure el primer algoritme de factorisació 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 de factorisació ú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 factorisació 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 complex. 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 factorisació 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 de factorisació.

Els camps dels coeficients per als que es coneixen algoritmes de factorisació inclouen camps principals (és dir, els número racional i l'aritmètica modular sobre cosins) i les seues extensions de camp finit. 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:

• Factorisació sense radicals
• Factorisació 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.

Factorisació primitiva basada en contingut

Vore també: Lema de Gauss

En esta secció, es mostra que la factorisació 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 factorisació de p com el producte d'un número entero i un polinomi primitiu. Esta factorisació é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 factorisació 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 factorisació en un número racional i un polinomi primitiu en coeficients sancers. Esta factorisació é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 factorisació 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 factorisació sobre els número racional d'un polinomi en coeficients racionals és la mateixa que la factorisació sobre els número entero de la seua part primitiva. Per un atre costat, la factorisació sobre els número entero d'un polinomi en coeficients sancers és el producte de la factorisació de la seua part primitiva per la factorisació del seu contingut.

En atres paraules, integer GDD computation permet reduir la factorisació d'un polinomi sobre els número racional a la factorisació d'un polinomi primitiu en coeficients sancers, i reduir la factorisació sobre els número entero a la factorisació 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 factorisació sobre una extensió purament transcendent de F a la factorisació 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).«Factoring polynomials with rational coefficients».Mathematische Annalen.261(4)

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

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