Polinomok faktorizációja

A matematikában a polinomok faktorizációja arra a módszerre utal amely során egy polinomot amelynek együtthatói egy adott testből származnak vagy egész számok, felbontunk tovább nem bontható úgynevezett irreducibilis polinomok szorzatára, amelyek együtthatói ugyanabból az előbb említett halmazból kerülnek ki.

A polinomok faktorizációjának története Hermann Schuberttel kezdődött aki 1793-ban először írt egy polinom faktorizációs algoritmust. Később Leopold Kronecker újra felfedezte Schubert algoritmusát 1882-ben és kiterjesztette többváltozós polinomokra. Ugyanakkor a legfontosabb ismeretek a témában nem túl régiek, mindössze 1965 után keletkeztek a számítógépes algebrai rendszerek megjelenésével. Egy kutatásában Erich Kaltofen azt írta 1982-ben, hogy:

Amikor a régen ismert véges algoritmusokat először alkalmazták számítógépekkel, kiderült, hogy ezen algoritmusok meglehetősen használhatatlanok. Az a tény, hogy manapság, majdnem minden egy- vagy kétváltozós polinom amelynek fokszáma nem nagyobb mint 100 és az együtthatói értelmes méretűek (maximum 100 biten ábrázolhatóak) faktorizálható modern algoritmusok segítségével kevesebb, mint néhány perc alatt számítógép segítségével rámutat arra, hogy milyen erővel és sikerességgel foglalkoztak ezzel a problémával [a matematikusok és számítástudósok] az elmúlt 50 évben.

Manapság egy akár 1000 fokú egyváltozós polinomnak a faktorizálása, amelynek együtthatói akár több ezer számjegyűek is lehetnek, néhány pillanat alatt elvégezhető számítógéppel.

A probléma részletesen

Az egész számok feletti vagy egy tetszőleges test fölötti polinomgyűrűk elemei egyedi faktorizációval rendelkeznek. Ez azt jelenti, hogy a gyűrű minden eleme felírható egy konstans és irreducibilis polinomok szorzataként. Továbbá ez a felbontás egyedi, eltekintve a szorzás sorrendjétől és invertálható elemek szorzatától. (Ezek azok az elemek amelyeknek létezik multiplikatív inverze a polinomgyűrű alapját adó struktúrában, tehát például az egészeknél ezek az 1 és a -1; míg a valós számok testénél minden nemnulla elem invertálható elem. Ha $f(x)$ akkor $c\neq 0$-ra $cf(x)$ is irreducibilis. Bővebben lásd: irreducibilis polinom.)

A faktorizáció az alap struktúrától függ. Például az algebra alaptételéből következően minden egész együtthatós polinom felbontható lineáris polinomok szorzatára ahol az együtthatók komplex számok. Egy valós együtthatós polinom esetén az irreducibilis elemek fokszáma maximum 2, míg a racionális számok felett az irreducibilis polinomok fokszáma bármilyen nagy lehet.

A polinomfaktorizáció csak olyan testek fölött értelmezhető amelyekkel számolni tudunk, vagyis amelyek elemei számítógéppel ábrázolhatóak és az aritmetikai műveletek elvégezhetőek számítógépen egy algoritmussal Fröhlich és Shepherson olyan testekre adtak példákat, amelyeken nem létezhet faktorizációs algoritmus.

Azon testekre amelyek fölötti polinomgyűrűknek létezik faktorizációs algoritmusuk, példa a prím testek (például a racionális számok teste ilyen) és ezek véges generált kiterjesztési. A mai modern algoritmusok általában a

• Négyzetmentes felbontás vagy a
• Véges testek fölötti faktorizációk

továbbfejlesztései, és olyan egyszerűsítési módszereket használnak, mint például:

• Többváltozós esetek redukálása egyváltozós esetre.
• A tisztán transzcendens testkiterjesztések esetén a többváltozós módszert alkalmazzák az eredeti test fölött. (lásd lent)
• A testkiterjesztésből származó együtthatós polinom faktorizációja az eredeti test fölötti polinomgyűrűben (lásd lent)
• A racionális együtthatós polinom faktorizációját visszavezetik egész együtthatós polinomok faktorizációjára. (lásd lent)
• Az egész együtthatós polinomok faktorizációját visszavezetik prímtestek feletti faktorizációra. (lásd lent)

Primitív rész–az együtthatók egyszerűsítése

Ebben a részben azt mutatjuk meg, hogy a Q racionális számok feletti polinomok felbontása és a Z vagyis az egész számok fölötti polinomok felbontása gyakorlatilag ugyanaz a probléma.

Egy p ∈ Z[X] polinom együtthatóinak a legnagyobb közös osztóját jelöljük cont(p)-vel. A p polinom primitív része primpart(p)=p/cont(p), amely egy primitív polinom és az együtthatói egészek. Ekkor a p felbontható a cont(p) és a primitív rész szorzatára. Ez a faktorizáció egyedi, eltekintve cont(p) előjelétől. Általában a cont(p) előjelét úgy választják meg, hogy a primitív rész főegyütthatója pozitív legyen.

Például:

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

egy faktorizáció a polinom primitív és a konstans részének szorzatára..

Minden q racionális együtthatós polinom felírható

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

alakban, ahol p ∈ Z[X] és c ∈ Z. A c konstanst válasszuk az eredeti polinom együtthatóinak a nevezőinek szorzatának. Ekkor cont(q)-t a következőképpen definiáljuk:

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

és q primitív része p. Hasonlóan az egész együtthatós polinomokhoz itt is felbonthatjuk a q polinomot egy racionális szám és egy primitív, egész együtthatós polinom szorzataként. Ez a faktorizáció szintén egyértelmű a racionális szám előjelétől eltekintve.

Például a

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

faktorizáció felbontja a polinomot egy konstans és a primitív részének szorzatára.

Gauss volt az első aki bebizonyította, hogy két primitív polinom szorzata szintén primitív. (lásd Gauss-lemma). Ez azt jelenti, hogy egy primitív polinom irreducibilis a racionális számok felett akkor és csak akkor, ha a primitív része irreducibilis az egész számok felett. Ez pedig azt jelenti, hogy a racionális együtthatós polinomok faktorizációja visszavezethető egész együtthatós polinomok faktorizációjára (konkrétan a polinom primitív részének faktorizációjára). Viszont az egész együtthatós polinomok faktorizációja megegyezik a primitív részük faktorizációjával és a kiemelt rész szorzatával.

Négyzetmentes faktorizáció

Ha egy polinom két vagy több faktora megegyezik (vagyis ha a polinomnak többszörös gyökei vannak), akkor a polinom felbontásában az adott faktor a négyzeten vagy általánosan annyiadik hatványon jelenik meg, ahányszoros gyöke az eredeti polinomnak a faktor gyöke (vagyis ha az adott faktor x−c, ha c az eredeti polinomnak 2, 3, 4, ... n szeres gyöke, akkor ennek a polinomnak a felbontásában az x−c a 2., 3., 4., ... n. hatványán szerepel). Ilyen esetben (vagyis ha egy faktor a felbontásban 2 vagy magasabb hatványon szerepel), akkor az adott faktor osztja nem csak az adott polinomot, hanem annak deriváltját (többváltozós polinom esetén, bármelyik változó szerinti deriváltat) is. Racionális együtthatós (vagy általánosan 0 karakterisztikus testből származó együtthatós) egyváltozós polinomok esetén Yum algoritmusa a fenti tulajdonságot felhasználva képes hatékonyan előállítani egy polinomnak olyan faktorizációját, amelynek minden faktora négyzetmentes. Az eredeti polinom faktorizációját megkaphatjuk a már négyzetmentes részek faktorizációjával. Így látható, hogy a polinomok négyzetmentes faktorizációja a legtöbb faktorizáció első lépése.

Yum algoritmusa kiterjeszthető a többváltozós polinomok esetére úgy, hogy a polinomot egyváltozós polinomnak tekintjük.

Abban az esetben ha a polinom együtthatói egy véges testből származnak, Yum algoritmusa csak akkor működik ha polinom fokszáma kisebb mint a test karakterisztikája, mivel különben a nemnulla polinomok deriváltja zérus lehet. Egy másik algoritmus a négyzetmentes faktorizáció előállítására lehet a legnagyobb közös osztó egymásutáni alkalmazása, először a polinomra és annak deriváltjára; lásd: Véges test fölötti polinomfaktorizáció.

Hagyományos módszerek

Az ebben a részben bemutatott "tankönyvi" módszerek hasznosak lehetnek, ha kézzel szeretnénk faktorizálni, ugyanakkor ezek az algoritmusok nem használatosak számítógépes rendszerekben, mivel prímfaktorizációra épülnek, ami a jelen pillanatban nagyobb komplexitású feladat (tehát "nehezebb"), mint a polinomok faktorizációja.

A lineáris elemek kiszámítása

Minden lineáris faktor megtalálható a polinomok racionális gyökeire vonatkozó tétel segítségével. Ha a faktorizálni kívánt polinom $a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$, alakú, akkor minden lineáris faktora $b_{1}x-b_{0}$, alakú, ahol $b_{1}$ egész szám és osztója $a_{n}$-nek, $b_{0}$ pedig egész és osztója $a_{0}$-nak. A megtalált lineáris faktorok ezután kiemelhetőek a polinomból polinomosztás segítségével. Ha az eredeti polinom olyan elemek szorzata amelyek közül legalább kettő legalább másodfokú, akkor ez a módszer csak részleges faktorizációt szolgáltat, különben a faktorizáció teljesen végigvihető.

Kronecker módszere

Mivel az egész együtthatós polinomok faktorainak is egész együtthatós polinomoknak kell lenniük, és egy egész együtthatós polinom helyettesítési értéke egész pontokban, egész (mivel egész számok véges szorzata, véges összege egész, vagyis az az egész számok zártak szorzásra és összeadásra), így polinom értékeinek prímfaktorizációját felhasználva, véges számú elemre redukálhatjuk a lehetséges (polinom)faktorokat.

Például, vegyük az

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

polinomot. Ha ez a polinom felbontható az egész számok felett, akkor legalább az egyik faktorának első vagy másodfokúnak kell lennie (lásd az algebra alaptételének egy megfelelő változatát). Három értékre van szükségünk ahol, hogy egy legfeljebb másodfokú polinomot egyértelműen meg tudjunk határozni. Legyenek ezek a pontok az $f(0)=2$, $f(1)=6$ és az$f(-1)=2$. Ha a 3 közül bármelyik érték 0 akkor máris találtunk egy gyököt és így a faktorizációs tétel alapján egy faktort is. Ha viszont egyik sem 0 akkor mindegyiknek csak véges mennyiségű osztója van. Például 2 egész számok segítségével csak a következőképpen írható:

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

Vagyis ha másodfokú faktor létezik akkor annak

1, 2, −1, vagy −2

értékűnek kell lennie az $x=0$ pontban, és az $x=-1$ pontban. Mivel 6-ot 8-féleképpen lehet felbontani így összesen

4×4×8 = 128

kombinációs lehetőség van, amelynek fele csak előjelben különbözik így ezeket elhagyva csak 64 másodfokú polinom marad, amit le kell tesztelni. Csak ezek a lehetséges faktorai $f(x)$-nek. Ezek tesztelése szerint

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

amit úgy kaptunk, hogy $p(0)=1$, $p(1)=3$ és $p(-1)=1$, osztja $f(x)$-et a megfelelő pontokban.

Az $f$ polinomot $p$-vel osztva megkapjuk a másik faktort: $q(x)=x^{3}-x+2$, így $f=pq$. Mivel kiderül. hogy mind $p$ és $q$ irreducibilis így $f$ irreducibilis faktorizációja:

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

(Van der Waerden, 5.4-es és 5.6-os szakasz)

---

---

---

---

Fordítás

• Ez a szócikk részben vagy egészben a Factorization of polynomials című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• Fröhlich, A. & Shepherson, J. C. (1955), "On the factorisation of polynomials in a finite number of steps", Mathematische Zeitschrift 62 (1), ISSN 0025-5874, DOI 10.1007/BF01180640
• Trager, B.M., "Algebraic Factoring and Rational Function Integration", Proc. SYMSAC 76 http://dl.acm.org/citation.cfm?id=806338
• Bernard Beauzamy, Per Enflo, Paul Wang (1994. október 1.). „Quantitative Estimates for Polynomials in One or Several Variables: From Analysis and Number Theory to Symbolic and Massively Parallel Computation”. Mathematics Magazine 67 (4), 243–257. o. DOI:10.2307/2690843. JSTOR 2690843.  (accessible to readers with undergraduate mathematics)
• A course in computational algebraic number theory, Graduate Texts in Mathematics. Berlin, New York: Springer-Verlag (1993). ISBN 978-3-540-55640-4 
• Kaltofen, Erich (1982), "Factorization of polynomials", Computer Algebra, Springer Verlag, Sablon:Citeseerx
• Knuth, Donald E. 4.6.2 Factorization of Polynomials, Seminumerical Algorithms, Third, The Art of Computer Programming, Reading, Massachusetts: Addison-Wesley, 439–461, 678–691. o. (1997). ISBN 0-201-89684-2 
• (1982) „Factoring polynomials with rational coefficients”. Mathematische Annalen 261 (4), 515–534. o. DOI:10.1007/BF01457454. ISSN 0025-5831. 
• Van der Waerden, Algebra (1970), trans. Blum and Schulenberger, Frederick Ungar.

További információk

• Kaltofen, Erich (1990), "Polynomial Factorization 1982-1986", Computers in Mathematics, vol. 125, Lecture Notes in Pure and Applied Mathematics, Marcel Dekker, Inc., Sablon:Citeseerx
• Kaltofen, Erich (1992), "Polynomial Factorization 1987–1991", Proceedings of Latin ’92, vol. 583, Springer Lect. Notes Comput. Sci., Springer, <http://www4.ncsu.edu/~kaltofen/bibliography/92/Ka92_latin.pdf>. Hozzáférés ideje: October 14, 2012