1. fejezet. Polinomok Polinomok szorzása

1. fejezet Polinomok 1.1. Polinomok szorzása Legyen F egy test e´ s legyenek f, g polinomok F felett. Tegyuk ¨ fel, hogy f = n m α0 + α1 x + · · · + αn x e´ s g = β0 + β1 x + · · · + βm x , ahol αi , βi ∈ F. Legyen h = γ0 +γ1x+· · ·+γm+n xm+n az f e´ s g polinomok szorzata. Ekkor, i ∈ {0, . . . , n+m} esetén, i X γi = αj βi−j , j=0

ahol feltesszuk, ¨ hogy αn+1 = · · · = αn+m = βm+1 = · · · = βn+m = 0. Szam´ ´ ıtsuk ki, hogy a fenti formulat ´ hasznalva, ´ hany ´ testbeli muveletre ˝ van szuks´ ¨ eg a szorzat kiszam´ ´ ıtas ´ ahoz. ´ A γi szamot ´ i + 1 szorzassal ´ e´ s i o¨ sszeadassal, ´ azaz o¨ sszesen 2i + 1 testbeli muvelettel ˝ hatarozhatjuk ´ meg. Tehat ´ a szorzatpolinom kiszam´ ´ ıtas ´ ahoz ´ m+n X i=0

2i + 1 =

(2m + 2n + 2)(m + n + 1) = m2 + n2 + 2mn + 2n + 2m + 1 2

(1.1)

testbeli muvelet ˝ szuks´ ¨ eges. A tovabbiakban ´ az algebrai algoritmusok költségét a test- illetve gyur ˝ u˝ beli muveletek ˝ szam ´ aval ´ fogjuk mérni. Az egyszerubb ˝ o¨ sszehasnl´ıtas ´ kedvée´ rt bevezetjuk ¨ a nagyordo´ jelölést. Legyen, f : N → R egy fuggv´ ¨ eny. Azt mondjuk, hogy f egy költegf ´ uggv ¨ eny, ´ ha létezik N > 0, ugy ´ hogy f (n) > 0 minden n > N 1

2

Polinomok

esetén. Azaz, egy költségfuggv´ ¨ eny véges sok kivételt˝ol eltekintve nem-negat´ıv e´ rtékeket vesz fel. Legyenek ϕ, ψ : N → N költségfuggv´ ¨ enyek. Azt mondjuk, hogy ϕ nagyordo´ ” ψ”, ha léteznek c > 0 e´ s N ∈ N, hogy minden n > N esetén ϕ(n) 6 cψ(n); ´ırasban, ´ a ϕ fuggv´ ¨ eny O(ψ)”. Tehat ´ ha egy ϕ fuggv´ ¨ eny O(ψ), akkor, elegend˝oen nagy ” e´ rtékekre, ϕ nem nagyobb mint a ψ egy alkalmas konstansszorosa. Példa 1.1.1 Legyen ϕ egy polinomfuggv´ ¨ eny, azaz, n ∈ N esetén, legyen ϕ(n) = max{0, α0 + α1 n + · · · + αk nk } ahol αk > 0 (a trukkos ¨ megadas ´ azért szuks´ ¨ eges mert feltesszuk, ¨ hogy ϕ(n) > 0). Nem nehéz belatni, ´ hogy léteznek c ∈ R e´ s N ∈ N melyekkel, n > N esetén, k ϕ(n) 6 cn , azaz, ebben az esetben, a ϕ fuggv´ ¨ eny O(nk ). A (1.1) egyenlet szerint, két legfeljebb n-edfoku ´ polinom hagyomanyos ´ 2 modon ´ történ˝o szorzas ´ anak ´ a költsége legfeljebb 4n + 4n + 1 tesbeli muvelet. ˝ A 2 nagyordo´ jelölést hasznalva, ´ a költség tehat ´ O(n ) testmuvelet. ˝ Azaz, a testbeli muveletek ˝ szama ´ hozzavet˝ ´ olegesen a fok négyzetes fuggv´ ¨ enye. A következ˝o nehany ´ fejezetben megvizsgaljuk, ´ hogyan lehet ezt jav´ıtani.

´ (DFT) 1.2. A diszkrét Fourier transzformácio Legyen F egy test, legyen n ∈ N e´ s legyen ω egy F-beli primit´ıv egységgyök; azaz, ω n = 1 e´ s, minden i ∈ {1, . . . , n − 1} esetén ω i 6= 1. Példa 1.2.1 Ha F = C, akkor minden n esetén létezik primit´ıv egységgyök, példaul ´ exp(2iπ/n). Példa 1.2.2 Tegyuk ¨ fel, hogy F = Fq egy véges test e´ s legyen ω egy n-dik primit´ıv egységgyök, azaz ω n = 1. A nullat ´ ol ´ kul¨ ¨ onböz˝o F-beli elemek csoportot alkotnak, e´ s ebben a csoportban az ω egy n rendu ˝ elem. Lagrange tétele miatt, n osztja a csoport rendjét, azaz n|q − 1. Tegyuk, ¨ most fel, hogy n|q − 1 e´ s legyen m = (q − 1)/n. Ismert, hogy az Fq \ {0} egy ciklikus csoport, ´ıgy létezik ν ∈ Fq , melyre igaz, hogy, ν q−1 = 1, de minden Jegyzet friss´ ıtve:

2007. m´ ajus 8.

Algebrai Algoritmusok

3

i ∈ {1, . . . , q − 1} esetén ν i 6= 1. Azaz ν primit´ıv (q − 1)-dik egységgyök. Ekkor könnyu ˝ igazolni, hogy ω = ν m egy primit´ıv n-dik egységgyök. A fenti két gondolatmenetet o¨ sszerakva kapjuk, hogy az Fq testben pontosan akkor létezik primit´ıv n-dik egységgyök, ha n|q − 1. A tovabbiakban ´ feltesszuk, ¨ hogy F egy test e´ s ω egy n-dik primit´ıv egységgyök. Legyen f = α0 + α1 x + · · · + αk xk egy polinom. Az f polinom diszkrét Fourier transzformaltj ´ at ´ a következ˝oképpen definialjuk: ´ DFTω f = f (1), f (ω), . . . , f (ω n−1) .

Azaz, a diszkrét Fourier transzformaci ´ o´ (DFT) nem mas, ´ mint az f polinom egy primit´ıv egységgyök hatvanyain ´ vett e´ rtéke. Jelölje F[x] az F test feletti polinomalgebrat ´ e´ s tekintsuk ¨ az Fn = {(α1 , . . . , αn ) | α1 , . . . , αn ∈ F} vektorteret. Az Fn vektortéren e´ rtelmezhetjuk ¨ a pontonkénti szorzast, ´ e´ s ezzel n az F vektortér egy F-algebrav ´ a´ valik. ´ Lemma 1.2.3 A DFTω : F[x] → Fn lekepez ´ es ´ egy szurjekt´ ¨ ıv F-algebra-homon morfizmus melynek magja az x − 1 polinom altal ´ generalt ´ (xn − 1) ideal. ´ Tehat ´ n n a DFTω lekepez ´ es ´ tekintheto˝ egy F[x]/(x − 1) → F izomorfizmuskent. ´ ´ . Tetsz˝oleges f, g ∈ F[x] e´ s α, β ∈ F esetén, f g(α) = f (α)g(α), B IZONYÍ T AS (f + g)(α) = f (α) + g(α), e´ s (βf )(α) = β(f (α)), amib˝ol következik, hogy DFTω valoban ´ egy F-algebra-homomorfizmus. Belatjuk, ´ hogy DFTω szurjekt´ ¨ ıv. Legyen f1 = 1 e´ s i ∈ {1, . . . , n − 1} esetén 0 definialjuk ´ fi = (x − ω ) · · · (x − ω i−1) polinomokat. Ekkor az f0 polinomnak nincs gyöke F-ben, i ∈ {1, . . . , n − 1} esetén pedig az fi polinom gyökei az 1 = ω 0 , . . . , ω i−1 elemek. Azaz, ha a DFTω fi sorvektorokat egy matrixba ´ helyezzuk, ¨ akkor egy fels˝o haromsz¨ ´ og alaku ´ matrixot ´ kapunk melynek atl ´ oj ´ aban ´ nemnulla mennyiségek talalhat ´ ok. ´ Ezért ennek a matrixnak ´ a sorai generalj ´ ak ´ az n F vektortetet, e´ s mivel a DFTω F[x] egy altér, a DFTω leképezés szurjekt´ ¨ ıv. n i n n i Legyen I = (x − 1). Nyilvan ´ (ω ) − 1 = (ω ) − 1 = 1 − 1 = 0, ezért n x − 1 ∈ ker DFTω . Mivel ker DFTω egy ideal ´ F[x]-ben, kapjuk, hogy I 6 F[x]. Az F[x] gyur ˝ uben ˝ e´ rvényes a maradékos osztas ´ tétele, ezért minden g ∈ F[x] Jegyzet friss´ ıtve:

2007. m´ ajus 8.

4

Polinomok

esetén egyértelmuen ˝ léteznek u e´ s v polinomok melyekre g = u(xn − 1) + v e´ s deg v 6 n − 1 teljesul; ¨ azaz, g + I = v + I. Ebb˝ol következik, hogy az I ideal ´ minden mellékosztalya ´ egyértelmuen ˝ reprezentalhat ´ o´ egy legfeljebb (n − 1)edfoku ´ polinommal, azaz, dim F[x]/I = n. Tehat, ´ dim F[x]/I = dim Fn , amib˝ol ker DFTω = I = (xn − 1) következik. 2 Jelölje Qn az F[x]/(xn −1) hanyadosgy ´ ur ˝ ut. ˝ A fentiek szerint, a Qn hanyados´ gyur ˝ uben ˝ minden elem egyéretelmuen ˝ reprezentalhat ´ o´ egy legfeljebb (n − 1)edfoku ´ polinommal, ezért Qn -t azons´ıthatjuk ezen polinomok halmazaval. ´ Két Qn -beli polinom o¨ sszegét kiszam´ ´ ıthatjuk a hagyomanyos ´ modon, ´ szorzatukat n pedig a x = 1 relaci ´ o´ felhasznal ´ as ´ aval ´ kapjuk.

Példa 1.2.4 Legyen n = 3, f = 1 + x − 2x2 , e´ s legyen g = 2 − x + x2 . Szam´ ´ ıtsuk ki Qn -ban az f g szorzatot:

f g = (1 + x − 2x2 )(2 − x + x2 ) = 2 − x + x2 + 2x − x2 + x3 − 4x2 + 2x3 − 2x4 = = 2 − x + x2 + 2x − x2 + 1 − 4x2 + 2 − 2x = 5 − x − 4x2 .

Ha α1 , . . . , αn paronk´ ´ ent kul¨ ¨ onböz˝o testbeli elemek e´ s β1 , . . . , βn ∈ F akkor létezik pontosan egy n − 1-edfoko´ polinom melyre, minden i-re, f (αi ) = βi teljesul. ¨ Azaz, egy Q-beli polinom kétféleképpen is reprezentalhat ´ o: ´ egyrészt a hagyomanyos ´ modon ´ az egyutthat ¨ ovektor ´ aval, ´ illetve az 1, ω, . . . , ω n−1 elemeken felvett e´ rtékeivel. A 1.2.3 lemma szerint, a két reprezentaci ´ o´ egyenértéku. ˝ A fejezet elején ismertetett modszer ´ seg´ıtségével a hagyomanyos ´ reprezentaci ´ oban ´ 2 O(n ) testbeli muvelet ˝ szuks´ ¨ eges két polinom szorzas ´ ahoz, ´ a masodik ´ reprezentaci ´ oban ´ pedig ezt meg lehet tenni n testbeli szorzas ´ seg´ıtségével. Ha tehat ´ 2 gyorsan (azaz kevesebb mint O(n ) testmuvelet ˝ elvégzésével) valtani ´ tudunk a reprezentaci ´ ok ´ között, akkor az eddiginél gyorsabban tudunk polinomokat szorozni. Jegyzet friss´ ıtve:

2007. m´ ajus 8.


5

Mivel a DFTω : Qn → Fn egy linearis ´ transformaci ´ o, ´ reprezentalhat ´ o´ egy matrixsszal. ´ Valoban, ´   1 1 1 ··· 1  2 n−1    1 ω ω · · · ω   2 4 2(n−1)   ω ··· ω DFTω (α0 + α1 x + · · · + αn−1 xn−1 ) = (α0 , . . . , αn−1 )  1 ω .   . . . . . .. .. .. ..   ..   2 1 ω n−1 ω 2(n−1) · · · ω (n−1)

Jelölje Vω a fenti egyenl˝oségben szerepl˝o matrixot. ´ A mértani sorozat o¨ sszegképletét alkalmazva kapjuk, hogy ha n ∤ k, akkor n−1 X

ω ki = 0,

i=0

amib˝ol adodik, ´ hogy Vω Vω−1 = nI, ahol I az egységmatrix. ´ Mas ´ szoval, ´ −1 (Vω ) = (1/n)Vω−1 . Tehat ´ a Fourier transzformaci ´ o´ inverze is egy Fourier transzformaci ´ o, ´ e´ s mindkett˝o megkaphato´ egy matrixszorz ´ assal, ´ azaz O(n2 ) testbeli muvelettel. ˝

´ (FFT) 1.3. A gyors Fourier transformácio Legyen n egy paros ´ szam, ´ ω egy primit´ıv n-dik egységgyök egy F testben, n−1 f = α0 + α1 x + · · · + αn−1 x pedig egy legfeljebb (n − 1)-edfoku ´ F[x]-beli polinom. Szeretnénk meghatarozni, ´ az f polinom diszkrét Fourier transzformaltj ´ at, ´ azaz n−1 ki szeretnénk szam´ ´ ıtani az f (1), f (ω), . . . , f (ω ) e´ rtékeket. Az el˝oz˝o fejezet végén lév˝o e´ szrevétel miatt, ez O(n2 ) testbeli muvelettel ˝ lehetséges. Ebben a fejezetben megmutatjuk, hogy ehhez valoj ´ aban ´ csak O(n log n) testbeli muveletet ˝ kell elvégezni. El˝oször hatarozzuk ´ meg az f polinom xn/2 − 1 e´ s xn/2 + 1 polinomokkal vett r0 e´ s r1 maradékait. Ehhez alapesetben egy maradékos osztast ´ kellene elvégezni, de a jelen szituaci ´ oban ´ a maradékok egyszerubben ˝ is megkaphatok. ´ Az xn/2 −1 polinommal vett maradékot kiszam´ ´ ıthatjuk ugyanis ugy, ´ hogy az f polinomn/2 ban elvégezzuk ¨ az x = 1 helyettes´ıtést. Az f = α0 + α1 x + α2 x2 + · · · + αn/2 xn/2 + αn/2+1 xn/2+1 + · · · + αn−1 xn−1 Jegyzet friss´ ıtve:

2007. m´ ajus 8.

6

Polinomok

polinomban az xn/2 = 1 helyettes´ıtést végrehajtva kapjuk, hogy r0 = α0 + α1 x + α2 x2 + · · · + αn/2 + αn/2+1 x + · · · + αn−1 xn/2−1 = = (α0 + αn/2 ) + (α1 + αn/2+1 )x + · · · + (αn/2−1 + αn−1 )xn/2−1 . Hasonloan, ´ r1 = (α0 − αn/2 ) + (α1 − αn/2+1 )x + · · · + (αn/2−1 − αn−1 )xn/2−1 . Ekkor léteznek olyan q0 e´ s q1 polinomok melyekkel f = q0 (xn/2 − 1) + r0 e´ s f = q1 (xn/2 + 1) + r1 teljesul. ¨ Ezért, mivel ω n/2 = −1, i > 0 esetén azt kapjuk, hogy f (ω 2i ) = q0 (ω 2i)(ω ni − 1) + r0 (ω 2i) = r0 (ω 2i ) e´ s f (ω 2i+1 ) = q1 (ω 2i+1 )(ω niω n/2 + 1) + r1 (ω 2i+1 ) = r1 (ω 2i+1 ) Nyilvan, ´ r1 (ω 2i+1 ) = r1∗ (ω 2i ), ahol r1∗ (x) = r1 (ωx). Tehat ´ az r0 (1), r0 (ω 2 ), . . . , r0 (ω n−2) mennyiségek meghatarozhat ´ ok ´ az r0 , az r1 (ω), r1 (ω 3), . . . , r1 (ω n−1 ) mennyiségek pedig az r1∗ polinom ω 2 szerint vett Fourier transzformalt ´ anak ´ seg´ıtségével. Mivel ez egy kisebbrend˝o Fourier transzformalt, ´ a feladatot ´ıgy két egyszerubb ˝ feladatra redukaltuk. ´ Tétel 1.3.1 Az 1. algoritmus helyesen szam´ ´ ıtja ki az f polinom diszkret ´ Fourier transzformaltj ´ at. ´ Az algoritmus vegrehajt ´ asa ´ O(n log n) testbeli muveletet ˝ igenyel. ´ ´ . A fenti gondolatmenet igazolja, hogy az algoritmus helyes. B IZONYÍ T AS Szam´ ´ ıtsuk ki az algoritmus költségét. Jelölje S(n) az algoritmus végrehajtas ´ ahoz ´ szuks´ ¨ eges muveletek ˝ szam ´ at. ´ Az els˝o if utas´ıtasban ´ nincs testmuvelet. ˝ Az els˝o két set utas´ıtas ´ muveletig´ ˝ enye legfeljebb (3/2)n testmuvelet, ˝ a masodik ´ két set utas´ıtas ´ muveletig´ ˝ enye pedig legfeljebb 2S(n/2) testmuvelet. ˝ Tehat, ´ S(1) = 0 e´ s S(n) 6 2S(n/2) + (3/2)n. Indukcioval ´ igazolhato, ´ hogy S(n) 6 (3/2)n log2 n = O(n log n). 2 Ezek utan ´ kiszam´ ´ ıthatjuk két polinom szorzatat. ´ Jegyzet friss´ ıtve:

2007. m´ ajus 8.


7

1. algoritmus: FFT Input: n = 2k , f = α0 + α1 x + · · · + αn−1 xn−1 , ω, ω 2, . . . , ω n−1 Output: f (1), f (ω), . . . , f (ω n−1) if n = 1 then return α0 end if set r0 = (α0 + αn/2 ) + (α1 + αn/2+1 )x + · · · + (αn/2−1 + αn−1 )xn/2−1 set r1∗ = (α0 − αn/2 ) + ω(α1 − αn/2+1 )x + · · · + ω n/2−1 (αn/2−1 + αn−1 )xn/2−1 set (β0 , . . . , βn/2−1 ) = FFT(n/2, r0 , 1, ω 2, ω 4 . . . , ω n ) set (γ0 , . . . , γn/2−1 ) = FFT(n/2, r1∗ , 1, ω 2, ω 4 . . . , ω n ) return (β0 , γ0 , β1 , γ1 , . . . , βn/2−1 , γn/2−1 ) Algoritmus 1: Gyors Fourier Transzformaci ´ o´ u ¨ (FFT)

2. algoritmus: FAST M ULTIPLICATION Input: f, g ∈ F[x] melyekre deg f + deg g 6 2k − 1 ω primit´ıv 2k -dik egységgyök. Output: f g ∈ F[x] k

szam´ ´ ıtsuk ki ω 2 , . . . , ω 2 −1 mennyiségeket return (DFTω )−1 (DFTω f · DFTω g) Algoritmus 2: Gyors polinomszorzas ´

Jegyzet friss´ ıtve:

2007. m´ ajus 8.

8

Polinomok

Tétel 1.3.2 Legyen F egy test, ω ∈ F egy 2k -dik primit´ıv egyseggy¨ ´ ok es ´ legyenek k f, g ∈ F[x] polinomok melyekre deg f +deg g 6 2 . Ekkor az 2. algoritmus helyesen szam´ ´ ıtja ki az f, g polinomok szorzatat. ´ Az algoritmus vegrehajt ´ asa ´ O(n log n) testbeli muveletet ˝ igenyel. ´ ´ . Az eddig elmondottak igazoljak, B IZONYÍ T AS ´ hogy az algoritmus helyes. 2 n−1 Az ω , . . . , ω mennyiségeket kiszam´ ´ ıthatok ´ n − 1 szorzas ´ seg´ıtségével. A DFTω költésge O(n log n) testmuvelet, ˝ a return utas´ıtasban ´ lév˝o pontonkénti Így az algoritmus költsége O(n log n) vektorszorzas ´ költsége n testmuvelet. ˝ testmuvelet. ˝ 2 Abban az esetben, ha tetsz˝oleges gyur ˝ u ˝ felett akarunk polinomokat szorozni, a Schönhage-Strassen algoritmus alkalmazhato. ´ Az algoritmust itt nem targyaljuk, ´ de kimondjuk a következ˝o tételt. Tétel 1.3.3 (Sch¨ onhage-Strassen) Legyen R egy kommutat´ıv gyur ˝ u, ˝ es ´ legyenek f, g ∈ F[x] polinomok melyre deg f + deg g 6 n − 1. Ekkor az f g szorzat meghatarozhat ´ o´ legfeljebb O(n(log n)(log log n)) gyur ˝ ubeli ˝ muvelet ˝ seg´ıtseg ´ evel. ´

1.4. Példa Lassunk ´ egy példat ´ az el˝oz˝o fejezetben targyalt ´ algoritmusokra. Tekintsuk ¨ az 2 3 2 4 f = 1 + x + x + 2x e´ s a g = 2 + x + 2x + x polinomokat az F3 test felett. Mivel deg f + deg g = 7, az 1. algoritmusban n = 8 valaszt ´ as ´ szuks´ ¨ eges. A 2 gond az, hogy F3 -ban minden nem-nulla α elemre α = 1 teljesul, ¨ tehat ´ F3 -ban nincs primit´ıv 8-dik egységgyuk. ¨ Az 1.2.2 példa szerint azonban az F9 testben van ilyen egységgyök, tehat ´ az f g polinom szorzatat ´ FFT seg´ıtségével F9 felett szam´ ´ ıthatjuk ki (a szorzat nyilvan ´ valtozatlan ´ marad, ha egy testb˝ov´ıtésben hatarozzuk ´ meg). Az F9 testhez szuks´ ¨ egunk ¨ van egy irredicibilis F3 feletti polinomra. Könnyu ˝ 2 szamol ´ as ´ mutatja, hogy az t − t − 1 polinomnak nincs gyöke F3 -ban, ezért irreducibilis. Az F9 test tehat ´ megkaphato´ mint az F3 [t]/(t2 − t − 1) faktorgyur ˝ u. ˝ A faktorgyur ˝ u ˝ elemei az α + βt alaku ´ polinomok. Ezen polinomok o¨ sszeadasa ´ 2 a hagyomanyos ´ modon ´ történik, szorzaskor ´ pedig felhasznaljuk ´ az t = 1 + t Jegyzet friss´ ıtve:

2007. m´ ajus 8.


9

o¨ sszefugg´ ¨ est. Példaul, ´ (1 + t)(2 + t) = 2 + 3t + t2 = 2 + 1 + t = t. Az alabbi ´ tabl ´ azat ´ a F9 nem-nulla elemei közötti szorzot ´ abl ´ at ´ tartalmazza. 1 2 t 1+t 2+t 2t 1 + 2t 2 + 2t · 1 1 2 t 1+t 2+t 2t 1 + 2t 2 + 2t 2 2 1 2t 2 + 2t 1 + 2t t 2+t 1+t t t 2t 1 + t 1 + 2t 1 2 + 2t 2 2+t 1 + t 1 + t 2 + 2t 1 + 2t 2 t 2+t 2t 1 1 t 2 + 2t 2 1+t 2t 2 + t 2 + t 1 + 2t 2t t 2 + 2t 2 + t 2 1+t 1 1 + 2t 2t 1 + 2t 1 + 2t 2 + t 2 2t 1+t 1 2 + 2t t 1 2t 1 + 2t t 2 2 + 2t 2 + 2t 1 + t 2 + t A fenti szorzot ´ abl ´ ab ´ ol ´ leolvashato, ´ hogy ω = t egy primit´ıv 8. egységgyök. 1 2 3 Valoban, ´ t = t, t = 1 + t, t = 1 + 2t, t4 = 2, t5 = 2t, t6 = 2 + 2t, t7 = 2 + t, t8 = 1. Szam´ ´ ıtsuk ki az f = 1+x+x2 +2x3 polinom diszkrét Fourier transzformaltj ´ at ´ 2 az FFT algoritmus szerint. Az els˝o rekurzioban ´ r0 = f = 1 + x + x + 2x3 , illetve r1∗ = 1 + tx + t2 x2 + 2t3 x3 = 1 + tx + (1 + t)x2 + (2 + t)x3 . Az FFT kiszam´ ´ ıtas ´ ahoz ´ a rekurziot ´ harmadik mélységig kell megh´ıvni, a szam´ ´ ıtas ´ részleteit az 1.4 tabl ´ azat ´ tartalmazza. Az algoritmus helyességének igazolasa ´ soran ´ alkalmazott gondolatmenetet hasznalva, ´ a tabl ´ azatban ´ szerepl˝o polinomok diszkrét Fourier transzformaltjai ´ az utols ´ o´ sortol ´ kezd˝od˝oen leolvas´ hatok. ´ Igy kapjuk, hogy DFTω f = (2, 1, 2 + 2t, 1, 2, 2t, 1 + t, 2 + t), e´ s hasonloan, ´ DFTω g = (0, 0, 2 + t, 0, 1, t, 2t, 2t + 1), tehat ´ DFTω f · DFTω g = (0, 0, 2t, 0, 2, 2 + 2t, 2 + t, 1 + t). A szorzat kiszam´ ´ ıtas ´ ahoz, ´ most a h = 2tx2 + 2x4 + (2 + 2t)x5 + (2 + t)x6 + (1 + t)x7 polinom Fourier transzformaltj ´ at ´ kell meghatarozni ´ a ω −1 szerint: DFTω−1 h = (1, 0, 1, 2, 1, 1, 2, 1). Jegyezzuk ¨ meg, hogy F3 -ban 1/8 = 2, tehat ´ a szorzatpolinom f g = 2(1 + x2 + 2x3 + x4 + x5 + 2x6 + x7 ) = 2 + 2x2 + x3 + 2x4 + 2x5 + x6 + 2x7 .


2007. m´ ajus 8.

10

Polinomok

f = 1 + x + x2 + 2x3 (2, 1, 2 + 2t, 1, 2, 2t, 1 + t, 2 + t)

r1∗ = 1 + tx + (1 + t)x2 + +(2 + t)x3 (1, 1, 2t, 2 + t)

r0 = 1 + x+ +x2 + 2x3 (2, 2 + 2t, 2, 1 + t)

r0 = 2 (2, 2)

r1∗ = (2 + 2t)x (2 + 2t, 1 + t)

2 2

2 + 2t

1+t

r0 = 2 + t+ +(2 + 2t)x (1, 2t)

1 2t

r1∗ = 2t+ +(1 + t)x (1, 2 + t)

1

2+t

1.1. tabl ´ azat. ´ Az f = 1 + x + x2 + 2x3 polinom diszkrét Fourier transzformaltja ´ FFT seg´ıtségével

g = 2 + x + 2x2 + x4 (0, 0, 2 + t, 0, 1, t, 2t, 1 + 2t)

r0 = x + 2x2 (0, 2 + t, 1, 2t)

r0 = 2 + x (0, 1)

0 1

r1∗

r1∗ = 1 + tx + (2 + 2t)x2 (0, 0, t, 1 + 2t)

= 1 + (1 + t)x (2 + t, 2t)

2+t

2t

r0 = 2t + tx (0, t)

0

t

r1∗ = (2 + t)+ +(1 + 2t)x (0, 1 + 2t)

0

1 + 2t

1.2. tabl ´ azat. ´ Az g = 2 + x + 2x2 + x4 polinom diszkrét Fourier transzformaltja ´ FFT seg´ıtségével


2007. m´ ajus 8.


11

2tx2 + 2x4 + (2 + 2t)x5 + (2 + t)x6 + (1 + t)x7 (1, 0, 1, 2, 1, 1, 2, 1)

r0 = 2 + (2 + 2t)x+ +2x2 + (1 + t)x3 (1, 1, 1, 2)

r0 = 2 (1, 1)

1 1

r1∗ = 1 + tx + x2 + +(1 + 2t)x3 (0, 2, 1, 1) r0 = 2 + x (0, 1)

r1∗ = x (1, 2)

1

0

2

1

r1∗ = 2x (2, 1)

2

1

1.3. tabl ´ azat. ´ Az 2tx2 + 2x4 + (2 + 2t)x5 + (2 + t)x6 + (1 + t)x7 polinom diszkrét Fourier transzformaltja ´ FFT seg´ıtségével

1.5. Polinomok faktorizálása A tovabbiakban ´ F egy test, altal ´ aban ´ véges. Legyen f ∈ F[x]. Célunk, hogy meghatarozzuk ´ f irreducibilis felbontas ´ at: ´ α

f = f1 1 · · · fnαn ,

(1.2)

ahol az fi -k paronk´ ´ ent nem asszocialt ´ irreducibilis polinomok. Célunk, hogy a feladatot kevés” testbeli muvelet ˝ seg´ıtségével végezzuk ¨ el. Mivel egy legfeljebb ” (n − 1)-edfoku ´ polinom megadhato´ az α1 , . . . , αn−1 egyutthat ¨ ok ´ seg´ıtségével, egy ilyen polinom bitmérete legfeljebb log2 α1 + · · · + log2 αn + n ami O(n log q), ha F = Fq . Tehat ´ az a célunk, hogy az algoritmus muveletsz ˝ ama ´ polinomialis ´ legyen n-ben e´ s log q-ban. Az els˝o lépés az itt ismertetett faktorizaci ´ os ´ eljar ´ asban, ´ hogy a problémat ´ visszavezetjuk ¨ a négyzetmentes polinomok esetére. Egy polinomot négyzetmentesnek nevezunk, ¨ ha az 1.2 felbontasban ´ α1 = · · · = αn = 1. Az f többszörös tényez˝oit a derivalt ´ seg´ıtségével izolaljuk. ´ Legyen f = α0 + · · · + αk xk , ekkor f ′ = α1 + 2α2 x + · · · + kαk xk−1 . Lemma 1.5.1 Legyen f ∈ F[x]. Jegyzet friss´ ıtve:

2007. m´ ajus 8.

12

Polinomok (1) Ha f = uk v, ahol u, v ∈ F[x], akkor f ′ = uk−1(ku′ v + uk v ′ ).

Azaz, uk−1|f . (2) Ha f = uv, ahol u es ´ v relat´ıv pr´ımek es ´ u′ 6= 0, akkor u ∤ f ′ . (3) Ha f ′ = 0, akkor vagy f konstans, vagy char F = p es ´ f = g p ahol g ∈ F[x]. ´ . A Leibniz szabaly B IZONYÍ T AS ´ szerint, f g = f ′ g + f g ′ . Ezt alkalmazva az all´ ´ ıtas ´ következik. A (3) all´ ´ ıtas ´ bizony´ıtas ´ ahoz, ´ emlékezzunk, ¨ hogy ha char F = p akkor (α0 + α1 x + · · · + αn xn )p = α0p + α1p xp + · · · + αnp xnp . 2 Elso˝ eset: f ′ = 0. Ha f ′ = 0, e´ s f nem konstans polinom, akkor char F = p e´ s f = g p , ahol g ∈ F[x]. Legyen F = Fq ahol q = pd . Ekkor α ∈ Fq esetén, (αp

d−1

d

)p = αp = α. Tehat, ´ egy α elem p-dig gyöke αp

d−1

. A fentiek miatt

f = α0 + αp xp + αmp xmp . e´ s f = g p ahol g = α0p

d−1

+ αpp

d−1

d−1

p xm . x + · · · + αmp

Tehat ´ ebben az esetben a g polinom O(n log q) aritmetikai muvelettel ˝ meghatarozhat ´ o, ´ az f felbontas ´ at ´ pedig visszavezettuk ¨ az alacsonyabb foku ´ g polinom felbontas ´ ara. ´ Masodik ´ eset: f ′ 6= 0. Ha f ′ 6= 0, akkor a f / gcd(f, f ′ ) polinom négyzetmentes, ´ıgy azt az alabbiakban ´ közölt modon ´ faktorizaljuk. ´ Ezutan ´ gcd(f, f ′ ) polinomra a fenti eljar ´ ast ´ ismételten végrehajtjuk. Ett˝ol a ponttol ´ F = Fq e´ s legyen f egy négyzetmentes polinom. Fel´ırjuk f -et f = f1 · · · fn alakba, ahol fi az f polinom i-edfoku ´ tényez˝oinek szorzata. A következ˝o lemmat ´ nem bizony´ıtjuk. d

Lemma 1.5.2 Az xq − x polinom azon 1 foegy ˝ utthat ¨ os ´ irreducibilis polinomok szorzata melyek foka osztoja ´ d-nek. Jegyzet friss´ ıtve:

2007. m´ ajus 8.


13

Tehat ´ a fenti kul¨ ¨ onböz˝o foku ´ felbontasban, ´ f1 = gcd(f, xq − x). Aztan ´ 2 q f2 = gcd(f /f1 , x − x), stb. Azt is jegyezzuk ¨ meg, hogy ezzel az algoritmussal hatékonyan tesztelhet˝o, hogy f irreducibilis-e, ugyanis f akkor e´ s csakis akkor irreducibilis, ha f = fk ahol k = deg f . A tovabbiakban ´ feltesszuk, ¨ hogy f négyzetmentes polinom mely azonos foku ´ tényez˝ok szorzata. Az el˝oz˝o fejezetekben ismertetett eljar ´ asok ´ seg´ıtségével a felbontasi ´ probléma visszavezethet˝o erre az esetre. Lemma 1.5.3 Ha q paratlan, ´ akkor n o q − 1 (q−1)/2 . =1 = α ∈ Fq | α 2

´ . Emlékezzunk, B IZONYÍ T AS ¨ hogy F∗q = Fq \ {0} egy ciklikus csoport, melyben van pontosan egy (q ˝ részcsoport; jelölje H. Ugyanakkor a J = n o − 1)/2 rendu (q−1)/2 α ∈ Fq | α = 1 halmaz is egy részcsoportja F∗q -nak e´ s nyilvan ´ H 6 J < F∗q teljesul. ¨ Mivel |F∗q : H| = 2, az all´ ´ ıtas ´ következik. 2 Lemma 1.5.4 Legyen q paratlan ´ es ´ legyen f egy n-edfoku´ negyzetmentes ´ polinom mely d-edfoku´ irreducibilisek szorzata. Ha u egy egyenletes eloszlas ´ u´ 2d 2d legfeljebb (n − 1)-edfoku´ veletlen ´ polinom, akkor, legalabb ´ (q − 1)/(2q ) > 4/9 d (q −1)/2 valosz´ ´ ınus ˝ eggel, ´ gcd(u − 1, f ) valodi ´ osztoja ´ f -nek. ´ . Legyen f = f1 · · · fn az f polinom kul¨ B IZONYÍ T AS ¨ onböz˝o foku ´ felbontasa. ´ Mivel ∼ fi irreducibilis, F[x]/(fi ) egy test, nevezetesen F[x]/(fi ) = Fqn . Jelölje ui az u polinom fi szerint vett maradékat ´ e´ s tekintsuk ¨ ui-t, az F[x]/(fi ) test elemeként. Ekkor, ui egyenletes eloszlas ´ u ´ véletlen eleme F[x]/(fi )-nek. Tovabb ´ a, ´ a k´ınai maradéktétel szerint, az ui elemek, mint valosz´ ´ ınus´ ˝ egi valtoz ´ ok, ´ fuggetlenek. ¨ A fenti lemma szerint, azon |{ui | u(q

d

−1)/2

− 1 = 0}| = (q d − 1)/2, d

d

(q −1)/2

(q −1)/2

tehat ´ annak valosz´ ´ ınus´ ˝ ege, hogy a u1 − 1 e´ s u2 − 1 közul ¨ pontosan az d d 2d (q −1)/2 ´ ıtjuk, hogy ebben az esetben gcd(u egyik 0 (q − 1)/(2q ). All´ − 1, f ) valodi ´ d

(q −1)/2


2007. m´ ajus 8.

d

(q −1)/2

osztoja ´ az f -nek. Valoban, ´ ha példaul ´ u1 − 1 = 0, de u2 d d d (q −1)/2 (q −1)/2 f1 |u − 1 de f2 ∤ u − 1, tehat ´ f1 | gcd(f, u(q −1)/2 − 1).

− 1 6= 0 akkor

14

Polinomok Könnyu ˝ latni, ´ hogy 1 q 2d − 1 1 = − 2d , 2d 2 2q 2q

azaz a fenti mennyiség monoton növekv˝o fuggv´ ¨ enye a q d -nek. Tehat ´ akkor lesz d d 2d legkisebb, ha q legkisebb, azaz q = 3. Következésképp, (q − 1)/(2q 2d) > 4/9 2 A Cantor-Zassenhaus algoritmus ugy ´ muk¨ ˝ odik, hogy egy véletlen u polid (q −1)/2 nomra kiszam´ ´ ıtja a h = gcd(u − 1, f ) polinomot. Ha ez valodi ´ osztoja ´ f -nek, akkor a muveletet ˝ megismétli a h e´ s f /h polinomokkal. Vilagos, ´ hogy a h e´ s az f /h polinomok mindketten d-edfoku ´ irreducibilisek szorzata.

1.6. Példa Tekintsuk ¨ a következ˝o F5 [x]-beli polinomot e´ s hatarozzuk ´ meg az irreducibilis felbontas ´ at: ´ f = 3 + 2x + x2 + 2x3 + x4 + x5 + 4x8 + 2x9 + x10 + x11 + 3x12 + 4x13 + 2x14 + 2x16 + x17 . Az els˝o lépésben kiszam´ ´ ıtjuk a f1 = f / gcd(f, f ′ ) = 1 + 3x + 3x2 + 3x3 + x4 + x5 polinomot, mely az el˝oz˝o fejezetben targyaltak ´ miatt négyzetmentes. Az f1 polinom els˝o-, masod-, ´ e´ s harmadfoku ´ irreducibilis tényez˝oinek szorzata rendre h1 = gcd(x5 − x, f1 ) = 1, h2 = gcd(x25 − x, f1 ) = 1 + x + x2 , h3 = gcd(x125 − x, f1 ) = 1 + 2x + x3 . A fentiekb˝ol latszik, ´ hogy a h1 e´ s a h2 polinomok irreducibilisek, ezért a 2 3 4 1 + 3x + 3x + 3x + x + x5 polinom irreducibilis felbontasa: ´ 1 + 3x + 3x2 + 3x3 + x4 + x5 = (1 + x + x2 )(1 + 2x + x3 ). Tekintsuk ¨ most az f /f1 = 3 + 3x + 3x2 + x5 + x6 + x7 + x10 + x11 + x12 Jegyzet friss´ ıtve:

2007. m´ ajus 8.


15

hanyadost ´ e´ s jelölje f most ezt a polinomot. Ismét szam´ ´ ıtsuk ki a f1 = f / gcd(f, f ′ ) = 1 + x + x2 négyzetmentes polinomot. A fentiek miatt, f1 irreducibilis. Legyen most f := f /f1 = 3 + x5 + x10 . Mivel f ′ = 0, az f polinom egy masik ´ polinom 5-dik hatvanya: ´ f = 3 + x5 + x10 = (3 + x + x2 )5 . Faktorizaljuk ´ most az f := 3 + x + x2 polinomot. Mivel gcd(f, f ′ ) = 1, f négyzetmentes. Hatarozzuk, ´ meg az els˝ofoku ´ tényez˝oinek szorzatat: ´ h1 = gcd(x5 − x, f ) = 3 + x + x2 . Tehat ´ f két els˝ofoku ´ irreducibilis szorzata. Hasznaljuk ´ a Cantor-Zassenhaus algoritmust az f polinom felbontas ´ ara. ´ Valasszunk ´ egy random u polinomot, mondjuk u = 4x, e´ s legyen h = gcd(u(5−1)/2 − 1, f ) = gcd(u2 − 1, f ) = 4 + x, tehat ´ els˝ore szerencsénk volt. Egyszeru ˝ osztas ´ utan ´ kapjuk, hogy f /h = 2 + x, tehat ´ f = (4 + x)(2 + x). Tehat ´ 3 + 2x + x2 + 2x3 + x4 + x5 + 4x8 + 2x9 + x10 + x11 + 3x12 + 4x13 + 2x14 + 2x16 + x17 = = (4 + x)5 (2 + x)5 (1 + x + x2 )2 (1 + 2x + x3 ). Vizsgaljuk ´ meg, mekkora szerencsére van szuks´ ¨ eg az utols ´ o´ lépésben, azaz az els˝ofoku ´ polinomok közul ¨ hany ´ ad irreducibilis faktort. Valamilyen komputer-algebrai rendszerrel könnyen lathatjuk, ´ hogy az u polinom 25 lehetséges valaszt ´ asa ´ közul ¨ pontosan 12 esetén lesz a gcd(u2 − 1, f ) polinom els˝ofoku. ´ Tehat ´ a Las Vegas modszer ´ ebben az esetben közel 1/2 valosz´ ´ ınus´ ˝ eggel muk¨ ˝ odik. Jegyzet friss´ ıtve:

2007. m´ ajus 8.

16

Polinomok

´ algoritmus k¨ 1.7. A faktorizácios oltsége Becsulj ¨ uk ¨ meg a 1.5 fejezetben ismertetett faktorizaci ´ os ´ algoritmus költségét. Ehhez el˝oször idézzuk ¨ fel a gyors hatvanyoz ´ as ´ algoritmusat. ´ Legyen a egy multiplikat´ıv algebrai struktura ´ egy eleme, e´ s legyen n egy természetes szam. ´ Az an mennyiség kiszam´ ´ ıtas ´ ahoz ´ a hagyomanyos ´ eljar ´ ast ´ alkalmazva n − 1 szorzasra ´ n van szuks´ ¨ eg. Ha azonban az alabbi ´ eljar ´ ast ´ alkalmazzuk, akkor az a hatvany ´ legfeljebb 2 log2 n szorzassal ´ meghatarozhat ´ o: ´ (i) ha n = 1 akkor an = a. (ii) ha n > 2 e´ s n paros ´ akkor an = an/2 · an/2 (rekurz´ıv h´ıvas); ´ (iii) ha n > 2 e´ s n paratlan ´ akkor an = a · a(n−1)/2 · a(n−1)/2 (rekurz´ıv h´ıvas); ´ A fenti eljar ´ as ´ költségére vonatkozo´ all´ ´ ıtas ´ igazolas ´ ahoz ´ jelölje S(n) az an kiszam´ ´ ıtas ´ ahoz ´ szuks´ ¨ eges muveletek ˝ szam ´ at. ´ Ekkor S(1) = 0, S(2n) = S(n) + 1, e´ s S(2n + 1) = S(n) + 2 teljesul, ¨ e´ s az all´ ´ ıtas ´ teljes indukcioval ´ igazolhato. ´ Ez a gondolatmenet adja a következ˝o lemmat. ´ Lemma 1.7.1 Egy multiplikat´ıv struktur ´ aban ´ an kiszam´ ´ ıthato´ O(log n) szorzas ´ felhasznal ´ as ´ aval. ´ Legyen f ∈ F[x], e´ s szam´ ´ ıtsuk ki hany ´ muvelet ˝ szuks´ ¨ eges az els˝o redukcio´ ′ ′ elvégzéséhez. Ha f 6= 0, akkor az f / gcd(f, f ) kiszam´ ´ ıtas ´ an ´ al ´ a következ˝o költségek lépnek fel: (i) f ′ kiszam´ ´ ıtasa: ´ O(n) aritmetikai muvelet; ˝ (ii) gcd(f, f ′ ) kiszam´ ´ ıtasa: ´ O(n3 ) aritmetikai muvelet; ˝ (iii) f / gcd(f, f ′ ) kiszam´ ´ ıtasa: ´ O(n2 ) aritmetikai muvelet. ˝ Tehat ´ a négyzetmentes f / gcd(f, f ′ ) polinom kiszam´ ´ ıtas ´ anak ´ költsége O(n3) aritmetikai muvelet. ˝ Ha f ′ = 0, akkor létezik g ∈ F[x] melyre f = g p e´ s a g polinom meghataroz ´ as ´ anak ´ költsége n darab, pd−1 -ik hatvanyra ´ emelés, ahol q = pd e´ s p pr´ım. A gyors hatvanyoz ´ as ´ algoritmusat ´ hasznalva ´ ez elvégezhet˝o O(n log q) aritmetikai muvelet ˝ seg´ıtségével. Tehat ´ az els˝o redukcio´ költsége O(n3 log q) aritmetikai muvelet. ˝ Jegyzet friss´ ıtve:

2007. m´ ajus 8.


17

Tegyuk ¨ fel most, hogy az f polinom négyzetmentes e´ s deg f = n. Ek2 n kor ki kell szam´ ´ ıtani a gcd(xq − x, f ), gcd(xq − x, f ), . . . , gcd(xq − x, f ) legnagyobb közös osztokat. ´ Az eukildeszi algoritmust közvetlenul ¨ alkalmazva i q 3i gcd(x − x, f ) kiszam´ ´ ıtas ´ ahoz ´ O(q ) aritmetikai muveletre ˝ van szuks´ ¨ eg, ezért i q ez nem jarhat ´ o´ ut. ´ Hatarozzuk ´ meg a x − x polinom f szerinti maradékat ´ i q okosabban. Az x polinom f szerinti maradékat ´ meghatarozhatjuk ´ gyors hatvanyoz ´ assal ´ O(i log q) = O(n log q) muveletet ˝ végrehajtva F[x]/(f )-ben. Mivel i i 2 egy F[x]/(f )-beli szorzas ´ költsége O(n ) testmuvelet, ˝ az xq e´ s az xq − x polinomok f szerinti maradékai meghatarozhat ´ ok ´ O(n3 log q) aritmetikai muvelettel. ˝ i q 3 Ezutan ´ a gcd(x − x, f ) kiszam´ ´ ıthato´ legfeljebb O(n ) aritmetikai muvelet ˝ fel4 hasznal ´ as ´ aval. ´ Tehat ´ az n darab gcd kiszam´ ´ ıtas ´ anak ´ költsége O(n log q). Lassuk ´ végul ¨ a harmadik fazist. ´ Ebben feltesszuk, ¨ hogy f négyzetmentes e´ s d-edfoku ´ irreducibilisek szorzata. Egy faktor meghataroz ´ as ´ ahoz ´ venni kell egy legfeljebb (n − 1)-edfoku ´ random polinomot, ahol deg f = n, e´ s tekinteni kell a d (q −1)/2 gcd(u − 1, f ) legnagyobb közös osztot. ´ A fenti gondolatok felhasznal ´ as ´ aval ´ 3 a gcd meghatarozhat ´ o´ O(n log q) muvelettel. ˝ A fenti szam´ ´ ıtas ´ eredménye az alabbi ´ tétel. Tétel 1.7.2 Legyen f ∈ Fq [x] es ´ legyen n = deg f . A 1.5 fejezetben vazolt ´ eljar ´ as ´ 4 O(n log q) muvelet ˝ elvegz ´ ese ´ utan ´ legalabb ´ 4/9 valosz´ ´ ınus ˝ eggel ´ az f polinom egy valodi ´ osztoj ´ at ´ adja. Azaz az f polinom irreducibilis tenyez ´ okre ˝ bontas ´ anak ´ 5 varhat ´ o´ költsege ´ O(n log q) aritmetikai muvelet. ˝ ´ . A tétel els˝o all´ B IZONYÍ T AS ´ ıtas ´ anak ´ igazolasa ´ a tétel el˝otti gondolatmenet, a masodik ´ all´ ´ ıtas ´ igazolas ´ ahoz ´ lényegében azt kell e´ szrevenni, hogy az deg f = n ezért az eljar ´ ast ´ legfeljebb n-szer kell sikeresen végrehajtani. Mivel, egy sikeres végrehajtas ´ valosz´ ´ ınus´ ˝ ege legalabb ´ 4/9, n sikerhez O(n) végrehajtas ´ szuks´ ¨ eges. A bizony´ıtas ´ részleteit itt nem közöljuk. ¨ 2

´ ´ 1.8. Alkalmazás: BCH kodok konstrukcioja A következ˝okben a polinomfaktorizaci ´ os ´ algoritmus alkalmazas ´ at ´ targyaljuk ´ a hibajav´ıto´ kodok ´ elméletében. Jegyzet friss´ ıtve:

2007. m´ ajus 8.

18

Polinomok

Legyen Fq egy véges test e´ s tekintsunk ¨ egy V vektorteret az Fq test felett. A V vektortér egy C alterét linearis ´ kodnak ´ nevezzuk. ¨ A kod ´ hossza dim V , a kod ´ dimenzioja ´ dim C, a dim C/ dim V mennyiség neve pedig jelsebesség, vagy kodol ´ asi ´ sebesség. Példa 1.8.1 Legyen V = F32 e´ s legyen C = {(0, 0, 0), (1, 1, 1)}. Nyilvan ´ C egy linearis ´ kod ´ V -ben, melynek hossza 3, dimenzioja ´ 1, jelsebessége pedig 1/3. A C kod ´ neve ismétléses kod. ´ A C elemeit kodszavaknak ´ nevezzuk. ¨ Két kodsz ´ o´ a = (α1 , . . . , αn ) e´ s b = (β1 , . . . , βn ) Hamming tavols ´ aga ´ a δ(a, b) = |{i | αi 6= βi }| mennyiség. Könnyu ˝ latni, ´ hogy a Hamming tavols ´ ag ´ egy metrika a kodszavak ´ között, e´ s az is azonnal adodik, ´ hogy a Hamming tavols ´ ag ´ eltolas ´ invarians, ´ azaz d(a, b) = d(a + x, b + x) teljesul ¨ minden a, b, x ∈ V esetén. A fenti a szo´ Hamming sulya ´ az a 0-tol ´ valo´ Hamming tavols ´ aga, ´ jele pedig w(a). Egy kod ´ minimalis ´ tavols ´ aga ´ a következ˝o: d(C) = min{δ(a, b) | a 6= b ∈ C}. Ha egy kod ´ minimalis ´ tavols ´ aga ´ d, akkor ⌈d/2⌉ hibat ´ tudunk vele jav´ıtani. A fenti ismétléses koddal ´ példaul ´ egy hiba jav´ıthato. ´ Lemma 1.8.2 Egy linearis ´ kod ´ eseten ´ d(C) = min {w(a) | a ∈ C \ {0}} . ´ . Legyen d a jobboldali kifejezés. Nyilvan B IZONYÍ T AS ´ d(C) 6 d. Legyen u, v ∈ C melyekre d(u, v) = d(C) teljesul. ¨ Ekkor nyilvan ´ d(u, v) = d(u − u, v − u) = d(0, v) = w(v). Tehat ´ d 6 d(C). 2 Legyen Fq egy véges test, e´ s legyen β egy Fqm -beli elem. A β minimal´ polinomja Fq felett az az Fq [x]-beli minimalis ´ fokszam ´ u ´ g f˝opolinom, melyre Jegyzet friss´ ıtve:

2007. m´ ajus 8.


19

g(β) = 0 teljesul. ¨ A minimalpolinom ´ létezik e´ s egyéretelmu, ˝ nevezetesen, a minimalpolinom ´ nem mas ´ mint azon polinomok gcd-je melyeknek a β elem gyöke. Következésképp, ha g a minimalpolinomja ´ egy β elemnek, e´ s f ∈ Fq [x] polinom melynek β gyöke, akkor g|f . A minimalpolinom ´ szugs´ ¨ egképpen irreducibilis. Az ismétléses kod ´ nem tuls ´ agosan ´ hatékony kod, ´ ezért az alabbiakban ´ egy masik ´ kodot ´ ismertetunk, ¨ az ugynevezett ´ BCH kodot. ´ Legyen Fq egy véges test, legyen β egy primit´ıv n-dik egységgyök Fqm -ben e´ s legyen g az az 1 f˝oegyutt¨ 2 δ−1 hatos ´ polinom mely a β, β , . . . , β elemek minimalpolinomjainak ´ a legkisebb közös többszöröse. A legyen C a g képe altal ´ generalt ´ ideal ´ az Fq [x]/(xn − 1) faktorgyur ˝ uben. ˝ Ekkor C-t egy BCH kodnak ´ nevezzuk, ¨ jele pedig BCH(q, n, δ). A g polinomot a kod ´ generatorpolinomj ´ anak ´ nevezzuk. ¨ Példa 1.8.3 Alkossunk BCH(3, 26, δ) kodokat. ´ Keresni kell egy Fqm testet melyben van 26-ik egységgyök, illetve meg kell keresni az adott egységyök minimalpolinomj ´ at. ´ A 26-ik egységgyököt a F27 testben keressuk. ¨ Ha β egy 26 ilyen egységgyök, akkor β kielég´ıti a f = x − 1 polinomot, tehat ´ a β minimalpolinomj ´ at ´ meghatarozhatjuk ´ az f polinom irreducibilis felbontas ´ ab ´ ol. ´ ′ 25 ′ Mivel f = 2x , gcd(f, f ) = 1, ezért f négyzetmentes. Hatarozzuk ´ meg az f azonos foku ´ irreducibilis tényez˝oinek a szorzatat. ´ Szam´ ´ ıtas ´ mutatja, hogy gcd(f, x3 − x) = x2 − 1, tehat ´ x2 − 1 = (x − 1)(x + 1) tényez˝oje az f -nek. Legyen f1 = f /(x2 − 1) = x24 + x22 + x20 + x18 + x16 + x14 + x12 + x10 + x8 + x6 + x4 + x2 + 1. Ekkor gcd(f1 , x9 − x) = 1,

e´ s

gcd(f1 , x27 − x) = f1 ,

tehat ´ f1 harmadfoku ´ irreducibilisek szorzata. A Cantor-Zassenhaus algoritmus seg´ıtségével meghatarozhatjuk ´ az f1 felbontas ´ at, ´ amib˝ol az f felbontasa ´ adodik: ´ f = (x − 1)(x + 1)(x3 − x + 1)(x3 − x − 1)(x3 + x2 − 1)(x3 + x2 + x − 1) (x3 + x2 − x + 1)(x3 − x2 + 1)(x3 − x2 + x + 1)(x3 − x2 − x − 1). Jegyzet friss´ ıtve:

2007. m´ ajus 8.

20

Polinomok

Legyenek g1 , . . . , g10 az f fenti faktorai. Legyen F27 = F3 [x]/(g3 ) = F[x]/(x3 − x + 1) e´ s legyen β = x ∈ F27 . Nyilvan ´ β 26 = 1, de kis szamol ´ as ´ azt is mutatja, hogy 2 13 β 6= 1, e´ s hogy β 6= 1, tehat ´ β egy 26-ik primit´ıv egységgyök. Tovabb ´ a´ a 3 β ∈ F27 minimalpolinomja ´ F3 felett g3 = x − x + 1. A g3 tovabbi ´ gyökei β 3 e´ s β 9 . Az alabbi ´ tabl ´ azat ´ tartalmazza, hogy a β kul¨ ¨ onböz˝o hatvanyainak ´ mi a minimalpolinomja: ´

hatvany ´

β, β , β 4, β 2, β 7, β 17 , β 5, β 8, 14

minimalpolinom ´

β0 β 13 β 3, β 9 β 16 , β 22 β 10 , β 12 β 6 , β 18 β 11 , β 21 β 23 , β 25 β 15 , β 19 β 20 , β 24

g1 g2 g3 g4 g5 g6 g7 g8 g9 g10

A fentiek figyelembevételével a β egységgyök seg´ıtségével az alabbi ´ BCH(3, 26, δ) Jegyzet friss´ ıtve:

2007. m´ ajus 8.


21

kodokat ´ képezhetjuk: ¨ δ

a β hatvanyai ´

generatorpolinom ´

δ=2 δ=4 δ=5

β, β 3 , β 9 β, β 2 , β 3 , β 6 , β 9 , β 18 β, β 2 , β 3 , β 4 , β 6 , β 9, β 10 , β 12 , β 18 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 9 , β 10 , β 12 , β 15 , β 18 , β 19 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 7 , β 9 , β 10 , β 11 , β 12 , β 15 , β 18 , β 19 , β 21 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 7, β 8 , β 9 , β 10 , β 11 , β 12 , β 15 , β 18 , β 19 , β 20 , β 21 , β 24 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 7 , β 8 , β 9 , β 10 , β 11 , β 12 , β 13 , β 15 , β 18 , β 19 , β 20 , β 21 , β 24 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 7, β 8 , β 9 , β 10 , β 11 , β 12 , β 13 , β 14 , β 15 , β 16 , β 18 , β 19 , β 20 , β 21 , β 22 , β 24 β, β 2 , β 3 , β 4 , β 5 , β 6 , β 7, β 8 , β 9 , β 10 , β 11 , β 12 , β 13 , β 14 , β 15 , β 16 , β 17 , β 18 , β 19 , β 20 , β 21 , β 22 , β 23 , β 24 , β 25

g3 g3 g6 g3 g5 g6

δ=7 δ=8 δ = 13

δ = 14

δ = 17

δ = 26

g3 g5 g6 g9 g3 g5 g6 g7 g9 g3 g5 g6 g7 g9 g10

g2 g3 g5 g6 g7 g9 g10

g2 g3 g4 g5 g6 g7 g9 g10

g2 g3 g4 g5 g6 g7 g8 g9 g10

Tekintsuk ¨ a tovabbiakban ´ a δ = 13 e´ rtékhez tartozo´ kodot, ´ melynek generatorpolinomja ´ g = g3 g5 g6 g7 g9 g10 = x18 + x17 − x14 − x13 + x12 − x11 + x9 − x7 − x6 − x5 + x4 + x − 1. 26 Legyen V = F3 [x]/(x26 − 1) ∼ ´ generalt ´ idealt ´ megkapjuk mint = F3 . A g képe altal 2 7 a g, gx, gx , . . . , gx polinomok altal ´ generalt ´ alteret. Tehat ´ a kod ´ dimenzioja ´ 8. Kis szamol ´ as ´ mutatja, hogy a minimalis ´ tavols ´ ag ´ pedig 13. Tehat ´ a kod ´ 6 hibat ´ jav´ıt.

Tétel 1.8.4 Legyen C egy BCH(q, n, δ) kod ´ melynek generatorpolinomja ´ g. Ekkor (i) C hossza n, dimenzioja ´ n − deg g; Jegyzet friss´ ıtve:

2007. m´ ajus 8.

22

Polinomok

(ii) egy h legfeljebb (n − 1)-edfoku´ polinom eseten ´ h ∈ C akkor es ´ csakis akkor ha g|h; (ii) C minimalis ´ tavols ´ aga ´ legalabb ´ δ. ´ . (i) A kod B IZONYÍ T AS ´ konstrukcioj ´ ab ´ ol ´ következik, hogy a kod ´ dimenzioja ´ n. Legyen g a kod ´ generatorpolinomja, ´ e´ s legyen k = deg g. Mivel a g a β, . . . , bδ−1 elemek minimalpolinomjainak ´ a legkisebb közös többszörose, az xn − 1 polinomnak pedig mindegyik β i gyöke, azt kapjuk, hogy g|xn − 1. A C kod ´ nem n n n mas, ´ mint a (g, x − 1)/(x − 1) = (g)/(x − 1) altér. Az izomorfizmus tételek szerint azonban, Fq [x]/(g) (g)/(xn − 1) ∼ = Fq [x]/(xn − 1) ezért dim C = dim Fq [x]/(xn − 1) − Fq [x]/(g) = n − k. (ii) Legyen h ∈ C. Ekkor létezik u, q ∈ Fq [x] melyre gu = q(xn − 1) + h teljesul, ¨ n n azaz h = gu − q(x − 1). Mivel g|x − 1, g|h. Tegyuk ¨ fel most, hogy g|h. Ekkor h = ug e´ s mivel deg h, deg g 6 n − 1, h = ug fennalt ´ Fq [x]-ben is. Tehat, ´ h ∈ C. (iii) Az el˝oz˝o lemmab ´ ol ´ következik, hogy a ∈ V = F[x]/(xn − 1) esetén a ∈ C akkor e´ s csakis akkor, ha a(β) = · · · = a(β δ−1 ) = 0. Legyenek (a0 , . . . , an−1 ) az a koordinat ´ ai ´ a standard bazisban. ´ A fentiek miatt, a ∈ C akkor e´ s csakis akkor, ha   1 1 ··· 1   β2 ··· β δ−1  β    2 4 2(δ−1)  = (0, . . . , 0). β ··· β (a0 , . . . , an−1 )   β   .. .. ..   .  . . n−1 2(n−1) (d−1)(n−1) β β ··· β

Vegyuk ¨ e´ szre, hogy a fenti matrixban ´ tetsz˝oleges (δ − 1) × (δ − 1) almatrix ´ egy Vandermonde matrix, tehat ´ tetsz˝oleges ilyen almatrix ´ invertalhat ´ o. ´ Legyen a ∈ C e´ s legyenek i1 , . . . , iw ∈ {1, . . . , n} azok az ij indexek melyre aij 6= 0. Ekkor w(a) = w. Legyen b az a vektor i1 , . . . , iw pozicioj ´ u ´ elemeib˝ol all ´ o´ vektor e´ s legyen M a fenti matrix ´ i1 , . . . , iw indexu ˝ sorokbol ´ all ´ o´ almatrixa. ´ Ekkor bM = 0, e´ s mivel b 6= 0, M szingularis. ´ Mivel Ebb˝ol következik, hogy az M sorainak szama ´ legalabb ´ δ, azaz w > δ. Tehat ´ minden kodsz ´ o´ Hamming sulya ´ legalabb ´ δ. 2


2007. m´ ajus 8.


23

´ polinomgyur 1.9. Ideálok sokváltozos ˝ uben ˝ Az alabbi ´ fejezetben többvaltoz ´ os ´ polinokkal kapcsolatos kérdésekkel foglalkozunk. Példa 1.9.1 Tekintsunk ¨ egy kétkaru ´ robotot melynek egyik karja, mely egyik végén csukloval ´ rögz´ıtve van, 5 centi hosszu, ´ masik pedig, mely egy csukloval ´ csatlakozik az els˝ohöz 3 centi hosszu. ´ Mindkét csuklo´ tetsz˝oleges szögben elfordulhat. Tekintsuk ¨ robotunkat egy olyan koordinata ´ rendszerben melynek origoja ´ az els˝o kar rögz´ıtéséhez esik. Az els˝o kar (x, y, z) végpontja kielég´ıti a x2 + y 2 + z 2 = 25 egyenletet. A kar (u, v, w) végpontja pedig kielég´ıti a (u − x)2 + (v − y)2 + (w − z)2 = 9 egyenletet. Tehat ´ azon pontok melyeket a robot karja elér a fenti két egyenlet megoldasaib ´ ol ´ kaphatok. ´ A tovabbiakban ´ F egy test e´ s R = F[x1 , . . . , xn ]. Ha f1 , . . . , fs ∈ R, akkor hf1 , . . . , fs i jelöli az fi -k altal ´ generalt ´ idealt. ´ Nyilvan ´ ( s ) X hf1 , . . . , fs i = qi fi | qi ∈ R . i=1

A fenti {f1 , . . . , fs } generatorrendszert ´ az ideal ´ bazis ´ anak ´ nevezzuk. ¨ Legyen I = hf1 , . . . , fs i. Ekkor V (I) jelöli az I altal ´ meghatarozott ´ algebrai sokasagot: ´ V (I) = {α ∈ Fn | f (α) = 0 minden f ∈ I esetén} = = {α ∈ Fn | f1 (α) = · · · = fs (α) = 0}. A fenti egyenl˝oség bizony´ıtas ´ at ´ az olvasora ´ b´ızom. Mas ´ szoval ´ az algebrai sokasag ´ nem mas, ´ mint az I idealban ´ lév˝o polinomok közös gyökeinek a halmaza. Az idealokkal ´ e´ s a sokasagokkal ´ kapcsolatban az alabbi ´ kérdések merulnek ¨ fel: Jegyzet friss´ ıtve:

2007. m´ ajus 8.

24

Polinomok

(i) mekkora V (I)? (ii) V (I) = ∅? (iii) I = R? (iv) f ∈ R esetén f ∈ I? A fenti kérdések eldöntésében a Gröbner bazosok ´ fognak seg´ıteni. Példa 1.9.2 Legyen F = R e´ s legyen f = x2 + y 2 = 9. Ekkor V (hf i) elemei egy origo´ köruli, ¨ 3 sugaru ´ kört alkotnak. Tehat ´ a V (I)-ben végtelen sok pont van. Az R gyur ˝ u ˝ xα1 1 · · · xαnn alaku ´ elemeit monomoknak mondjuk. Mindegyik monom azonos´ıthato´ a α = (α1 , . . . , αn ) egyutthat ¨ ovektor ´ seg´ıtségével. Ebben az α esetben a fenti monom jele x . A tovabbiakban ´ jelölje M az R-beli monomok halmazat. ´ Az M elemeinek egy ≺ teljes rendezését monomialis ´ rendezésnek nevezzuk, ¨ ha (i) ≺ egy jol ´ rendezés (azaz minden nemures ¨ halmazban van legkisebb elem); (i) ha x, y, z ∈ M e´ s x ≺ y, akkor yz ≺ xz. Ha α = (α1 , . . . , αn ), akkor az xα monom foka deg xα = α1 + · · · + αn . Példa 1.9.3 Az alabbiakban ´ bemutatjuk a gyakorlatban leggyakrabban hasznalt ´ monomialis ´ rendezéseket. Könnyen lathat ´ o, ´ hogy a lenti példak ´ valoban ´ monomialis ´ rendezéseket adnak, ennek igazolas ´ at ´ az olvasora ´ hagyom. Legyen nek α, β ∈ N egyutthat ¨ ovektorok. ´ Lexikografikus vagy szot ´ ari ´ rendezes: ´ xα ≺lex xβ akkor e´ s csakis akkor, ha az els˝o nemnulla elem az α − β vektorban negat´ıv. Példaul ´ n = 3 esetén x42 ≺lex x1 x2 x23 ≺lex x1 x22 x3 ≺lex x31 . Fokszam ´ szerinti, aztan ´ szot ´ ari ´ rendezes: ´ xα ≺dlex xβ akkor e´ s csakis akkor, ha deg x < deg y vagy deg x = deg y e´ s x ≺lex y. Itt x31 ≺dlex x42 ≺dlex x1 x2 x23 ≺dlex x1 x22 x3 . Fokszam ´ szerinti aztan ´ ford´ıtott lexikografikus rendezes: ´ xα ≺drlex xβ akkor e´ s csakis akkor, ha deg x < deg y vagy deg x = deg y e´ s y ≺lex x. Itt x31 ≺drlex x1 x22 x3 ≺drlex x1 x2 x23 ≺lex x42 . Jegyzet friss´ ıtve:

2007. m´ ajus 8.


25

P Legyen f = cα xα ∈ R egy polinom e´ s legyen ≺ egy monomialis ´ rendezés. Ekkor a következ˝o fogalmakat hasznaljuk: ´ (i) minden cα xα egy tag; multifoka α = (α1 , . . . , αn ); (ii) a polinom multifoka a legmagasabb multifoku ´ tag multifoka; jele mdeg f . (iii) a polinom f˝oegyutthat ¨ oja ´ a legmagasabb multifoku ´ tag egyutthat ¨ oja; ´ (iv) a polinom f˝otagja a legmagasabb multifoku ´ tag; (v) a polinom f˝omonomja a legmagasabb multifoku ´ tagban lév˝o monom. Példa 1.9.4 Legyen f = 2x3 + 3xy 2 z + 4xz 3 . Ekkor az f polinom f˝otagja a fenti harom ´ rendezést tekintve a kovetkez˝o. Lexikografikus: 2x3 ; fokszam ´ sze2 rinti aztan ´ lexikografikus 3xy z; fokszam ´ szerinti aztan ´ ford´ıtott lexikografikus: 3 4xz . Többvaltoz ´ os ´ polinomgyur ˝ uben ˝ is lehetséges a maradékos osztashoz ´ hasonlo´ eljar ´ ast ´ definialni. ´ Lemma 1.9.5 Legyenek f, f1 , . . . , fs ∈ R. Ekkor leteznek ´ q1 , . . . , qs , r ∈ R polinomok melyekkel f = q1 f1 + · · · + qs fs + r teljesul, ¨ es ´ vagy r = 0, vagy az r polinom egyetlen tagja sem oszthato´ az f1 , . . . , fs polinomok fotagjainak ˝ egyikevel ´ sem. A bizony´ıtas ´ el˝ott egy példat ´ mutatunk. Példa 1.9.6 Legyenek f = x2 y + xy 2 + y 2 , f1 = xy − 1, f2 = y 2 − 1. Redukaljuk ´ az f polinomot az f1 e´ s f2 polinomok szerint. Dolgozzunk a lexikografikus rendezés szerint. Vegyuk ¨ e´ szre, hogy az f1 f˝otagja (xy) osztja az f f˝otagjat ´ (x2 y), nevezetesen x2 y = x · xy. Tehat ´ a g = f − xf1 = xy 2 + xy 2 polinom alacsonyabb multifoku. ´ Ekkor f = g1 + xf1 teljesul. ¨ Az f1 polinom f˝otagja (xy) most a g 2 polinom f˝otagjat ´ (xy ) osztja, nevezetesen xy 2 = y · xy. Tehat, ´ g2 = g1 − yf1 = 2 x + y + y e´ s f = g1 + xf1 = g2 + (x + y)f1 teljesul. ¨ A g2 polinom f˝otagja x mely nem oszthato´ sem az f1 sem az f2 polinom f˝otagjaval. ´ Mentsuk ¨ at ´ tehat ´ ezt a 2 f˝otagot a maradékba, e´ s legyen r1 = x. Legyen g3 = g2 − r1 = y + y. Ekkor a g3 f˝otagja y 2 oszthato´ az f2 f˝otagjaval ´ (y 2), e´ s g3 − f2 = y + 1 egy alacsonyabb multifoku ´ polinom. Ebb˝ol kapjuk, hogy f = (y + 1) + (x + y)f1 + f2 + x. Most Jegyzet friss´ ıtve:

2007. m´ ajus 8.

26

Polinomok

sem az y, sem az 1 nem oszthato´ sem az f1 , sem az f2 f˝otagjaval, ´ tehat ´ azt a maradékhoz csapjuk. Tehat ´ az f polinom redukcioja ´ soran ´ az f = (x + y)f1 + f2 + (x + y + 1) fel´ırast ´ kapjuk. A q1 = x+y e´ s az q2 = 1 polinomok jatsz ´ ak ´ a hanyados ´ szerepét, az r = x+y+1 polinom pedig a maradék. Valoban, ´ az r egyik tagja sem oszthato´ sem az f1 , sem az f2 f˝otagjaval. ´ A 1.9.5 lemma bizony´ıtasa. ´ Legyenek f, f1 , . . . , fs a tétel feltételeinek eleget tev˝o polinomok. Ekkor az alabbi ´ eljar ´ assal ´ kaphatjut meg a q1 , . . . , qs , r polinomokat. 1. Legyen r = 0, p = f , e´ s q1 = · · · = qs = 0. 2. Ha létezik i index melyre ltfi |lt p, akkor legyen qi = qi + lt p/lt fi , p = p − (lt p/lt fi )fi . 3. Ha ilyen index nem létezik, akkor legyen r = r + lt p, p = p − lt p. 4. Ha p 6= 0 akkor vissza 1.-re. 5. Output q1 , . . . , qs , r. Könnyen latszik, ´ hogy a fenti eljar ´ as ´ véges sok lépés utan ´ véget e´ r, e´ s hogy az eljar ´ as ´ outputja helyes. 2 Példa 1.9.7 Sajnos a fenti eljar ´ as ´ nem olyan hatékony mint az egyvaltoz ´ os ´ polinomgyur ˝ uben ˝ ismert hasonlo´ eljar ´ as. ´ Ha ugyanis az algoritmus outputjaban ´ r = 0 akkor tudjuk, hogy f ∈ hf1 , . . . , fs i. Ha azonban r 6= 0, abbol ´ nem követ2 kezik, hogy f 6∈ hf1 , . . . , fs i. Legyen példaul ´ f = xy − x, f1 = xy + 1, f2 = y 2 − 1. Ekkor f = yf1 +0f2 +(−x−y), ugyanakkor f = xf2 , amib˝ol f ∈ hf1 , f2 i következik. Tehat ´ a fenti eljar ´ as ´ nem alkalmas arra, hogy eldöntsuk, ¨ hogy egy elem benne van-e egy idealban. ´ Kés˝obb definialjuk ´ a Gröbner bazis ´ fogalmat, ´ amely ezt a problémat ´ orvosolja majd.

1.10. Monomiális ideálok e´ s Hilbert bázistétele Az R gyur ˝ u ˝ egy idealj ´ at ´ monomialis ´ idealnak ´ nevezzuk, ¨ ha monomok generalj ´ ak. ´ Jegyzet friss´ ıtve:

2007. m´ ajus 8.


27

Lemma 1.10.1 Legyen A ⊆ Nn es ´ legyen I = hxα : α ∈ Ai egy monomialis ´ ideal. ´ Ekkor f ∈ R eseten ´ a következok ˝ ekvivalensek: (i) f ∈ I; (ii) f minden tagja eleme I-nek. ´ . Tegyuk B IZONYÍ T AS ¨ fel, hogy f ∈ I. Ekkor létezik B ⊆ A véges részhalmaz melyre X α f= x qα α∈B

teljesul, ¨ ahol α ∈ B esetén qα ∈ R. Vegyuk ¨ e´ szre, hogy a fenti egyenl˝oség baloldalan ´ szerepl˝o f polinom minden monomja szerepel a jobboldalon is. A jobboldalon viszont minden tag oszthato´ xα -val, ahol α ∈ A. Tehat, ´ ha xβ az f egy monomja, akkor valoban ´ létezik α ∈ A, melyre xα |xβ teljesul. ¨ A masik ´ irany ´ nyilvanval ´ o. ´ 2 A fenti lemmab ´ ol ´ kovetkezik az alabbi ´ eredmény. Lemma 1.10.2 Ket ´ monomialis ´ ideal ´ akkor es ´ csakis akkor egyenlo, ˝ ha ugyanazokat a monomokat tartalmazzak. ´ Tétel 1.10.3 (Dickson lemmája) Legyen A ⊆ Nn es ´ legyen I = hxα |α ∈ Ai. Ekkor letezik ´ B ⊆ A veges ´ reszhalmaz, ´ melyre I = hxα |α ∈ Ai. Következesk ´ epp, ´ minden monomialis ´ ideal ´ vegesen ´ generalt. ´ ´ . Legyen α = (α1 , . . . , αn ) e´ s β = (β1 , . . . , βn ). Ekkor α 6 β, ha minden B IZONYÍ T AS i esetén, αi 6 βi . Legyen B az A minimalis ´ elemeinek a részhalmaza. Azaz, B = {α ∈ A | 6 ∃β ∈ A, β < α}. Vilagos, ´ hogy minden α ∈ A esetén csak véges sok β ∈ A létezik melyre β 6 α teljesul. ¨ Tehat, ´ ha α ∈ A ⊆ B, akkor, a fentiek miatt, létezik egy α > α1 > · · · > αk lanc, ´ mely nem b˝ov´ıthet˝o, azaz αk ∈ B. Tehat ´ minden α ∈ A esetén létezik β ∈ B melyre β 6 α tejlesul. ¨ Vegyuk ¨ e´ szre, hogy ekkor xβ |xα . Ebb˝ol az is következik, hogy csak azt kell mar ´ igazolni, hogy B véges. A B halmaz végességét n-szerinti indukcioval ´ igazoljuk. Ha n = 1 akkor a monomok jol ´ rendezett halmazt alkotnak, e´ s minden részhalmazban létezik pontosan egy minimalis, ´ nevezetesen a legkisebb fokszam ´ u. ´ Jegyzet friss´ ıtve:

2007. m´ ajus 8.

28

Polinomok Tegyuk ¨ fel, hogy n > 2, legyen A∗ = {(α1 , . . . , αn−1 ) | (α1 , . . . , αn−1, αn ) ∈ A valamely αn esetén},

e´ s legyen B ∗ az A∗ minimalis ´ elemeinek a halmaza. Az indukcios ´ feltevés sze∗ ∗ rint B véges. Minden β = (β1 , . . . , βn−1 ) ∈ B esetén valasszunk ´ γβ elemet ´ ıtjuk, melyre (β1 , . . . , βn−1, γβ ) ∈ A e´ s legyen γ ezen γβ elemek maximuma. All´ hogy minden (α1 , . . . , αn ) ∈ B esetén αn 6 γ. Valoban, ´ ha (α1 , . . . , αn ) ∈ B, ak∗ kor létezik egy (β1 , . . . , βn−1 ) ∈ B elem melyre (β1 , . . . , βn−1 ) 6 (α1 , . . . , αn−1 ). Ha αn > γ, akkor (β1 , . . . , βn−1, γβ ) 6 (β1 , . . . , βn−1 , γ) < (α1 , . . . , αn ), e´ s ´ıgy (α1 , . . . , αn ) nem minimalis, ´ ami ellentmondas. ´ A fenti gondolatmenet eredménye, hogy a B halmaz elemeinek utols ´ o´ koordinat ´ ai ´ korlatosak. ´ Hasonlo´ gondolatmenet mutatja azonban, hogy a B halmaz elemeinek barmely ´ poz´ıcioban ´ lév˝o koordinat ´ ai ´ korlatosak, ´ tehat ´ B egy valoban ´ egy véges halmaz. 2 Ha f egy polinom, akkor lt f jelöli az f f˝otagjat. ´ Ha G az R egy részhalmaza, akkor lt G = {lt f | f ∈ G}. K¨ ovetkezmény 1.10.4 (Hilbert bázistétele) Legyen I 6 R egy ideal ´ es ´ legyen G egy veges ´ reszhalmaz, ´ melyre hlt Gi = hlt Ii. Ekkor hGi = I. Következesk ´ epp ´ minden R-beli ideal ´ vegesen ´ generalt. ´ ´ . Nyilvan B IZONYÍ T AS ´ hGi 6 I, ´ıgy csak az I 6 hGi tartalmazast ´ kell igazolni. Legyen G = {g1 , . . . , gs } e´ s legyen f ∈ I. Ekkor léteznek, q1 , . . . , qs , r polinomok, melyekkel f = q1 g1 + · · · + qs gs + r ahol vagy r = 0 vagy az r egyik tagja sem oszthato´ a gi polinomok f˝otagjainak egyikével sem. Ha r 6= 0, akkor r = f − q1 g1 − · · · − qs gs ∈ I, azaz lt f ∈ hlt Ii = hlt Gi. Ebb˝ol az következik, hogy az f f˝otagja oszthato´ egy G-beli polinom f˝otagjaval, ´ ami ellentmondas. ´ Tehat ´ r = 0 következik, e´ s ´ıgy f ∈ hGi. 2 Egy gyur ˝ ut ˝ Noether-félének nevezunk, ¨ ha balidealok ´ nem-csökken˝o lanca ´ mindig stabilizal ´ odik. ´ K¨ ovetkezmény 1.10.5 Ha F egy test akkor F[x1 , . . . , xn ] egy Noether-fele ´ gyur ˝ u. ˝ Jegyzet friss´ ıtve:

2007. m´ ajus 8.


29

´ . Legyen I1 6 I2 6 · · · 6 Ik 6 · · · idealok B IZONYÍ T AS ´ egy nem csökken˝o lanca. ´ S Ekkor I = Ik is egy ideal, ´ e´ s I, az el˝oz˝o eredmény e´ rtelmében, végesen generalt: ´ I = hf1 , . . . , fs i. Ekkor létezik m melyre f1 , . . . , f2 ∈ Im teljesul, ¨ azaz, I = Im . Ekkor, Im = Im+1 = · · · , azaz a lanc ´ valoban ´ stabilizal ´ odik. ´ 2

1.11. Gr¨ obner bázisok Legyen I 6 R egy ideal. ´ A G ⊂ I véges halmazt az I ideal ´ Gröbner bazis ´ anak ´ nevezzuk, ¨ ha hlt Gi = hlt Ii. Nyilvan ´ a Gröbner bazis ´ defin´ıcioja ´ fugg ¨ a monomialis ´ rendezést˝ol. Lemma 1.11.1 Egy ideal ´ Gröbner bazisa ´ gyur ˝ uelmleti ˝ ertelemben ´ is bazisa ´ az idealnak. ´ Tovabb ´ a, ´ minden idealnak ´ van Gröbner bazisa. ´ ´ . Az els˝o all´ B IZONYÍ T AS ´ ıtas ´ az 1.10.4 következményb˝ol adodik, ´ m´ıg a masodik ´ all´ ´ ıtas ´ a 1.10.3 lemmab ´ ol ´ következik. 2 Ígértuk, ¨ hogy a korabban ´ ismertetett maradékos osztas ´ algoritmus Gröbner bazisokkal ´ hatékony lesz. Lemma 1.11.2 Legyen G egy I ideal ´ Gröbner bazisa, ´ es ´ legyen f ∈ R. Ekkor egyertelm ´ uen ˝ letezik ´ olyan r polinom melyre f − r ∈ I es ´ az r egyetlen tagja sem oszthato´ egyetlen lt G-beli monommal sem. ´ . A létezés az 1.9.5 lemma következménye. Tegyuk B IZONYÍ T AS ¨ fel, hogy f = h1 + r1 = h2 + r2 ahol h1 , h2 ∈ I e´ s r1 , r2 ∈ R e´ s az r1 , r2 polinomok egyetlen tagja sem oszthato´ egyetlen lt G-beli monommal sem. Ekkor r1 − r2 = h2 − h1 ∈ I, e´ s lt (r1 − r2 ) ∈ lt I. Mivel lt I = lt G, lt (r1 − r2 ) oszthato´ valamely lt g-vel, ahol g ∈ G. Mivel az r1 − r2 polinom minden tagja vagy az r1 vagy az r2 polinomnak is tagja, kapjuk, hogy r1 = r2 = 0, azaz r1 = r2 . 2 Ha G egy ideal ´ Gröbner bazisa, ´ akkor, f ∈ R esetén f rem G jelöli az el˝oz˝o lemmaban ´ szerepl˝o r maradékot. K¨ ovetkezmény 1.11.3 Legyen G egy I ideal ´ Gröbner bazisa, ´ es ´ legyen f ∈ I. Ekkor f ∈ I akkor es ´ csakis akkor, ha f rem G = 0. Jegyzet friss´ ıtve:

2007. m´ ajus 8.

30

Polinomok

Legyenek g, h ∈ R \ {0}, legyen α = (α1 , . . . , αn ) = mdeg g, legyen β = (β1 , . . . , βn ) = mdeg h, e´ s legyen γ = (max(α1 , β1 ), . . . , max(αn , βn )). Ekkor a g e´ s h polinomok S-polinomja az S(g, h) =

xγ xγ g− h lt g lt h

polinom. A következ˝o lemma bizony´ıtasa ´ gyakorlat. Lemma 1.11.4 Ha g, h ∈ R \ {0}, akkor S(g, h) = −S(h, g) es ´ S(g, h) ∈ hg, hi. A következ˝o all´ ´ ıtas ´ seg´ıtségével eldönthet˝o, hogy egy véges halmaz Gröbner bazis ´ vagy sem. Tétel 1.11.5 Egy veges ´ halmaz G = {g1 , . . . , gs } ⊂ R Gröbner bazisa ´ az hGi idealnak ´ akkor es ´ csakis akkor, ha S(gi , gj ) rem (g1 , . . . , gs ) = 0 minden 1 6 i < j 6 s eseten. ´

Példa 1.11.6 Tekintsuk ¨ az I = f1 = xy 2 + x, f2 = x2 y − 1 idealt. ´ Szam´ ´ ıtsuk ki az I ideal ´ egy Gröbner bazis ´ at. ´ Legyen G = {f1 , f2 } e´ s hatarozzuk ´ meg az S(f1 , f2 ) polinomot: α = mdeg f1 = (1, 2), β = mdeg f2 = (2, 1), ezért γ = (max(α1 , β1 ), max(α2 , β2 )) = (2, 2). Ezért S(f1 , f2 ) =

xγ xγ x2 y 2 x2 y 2 2 2 f1 − f2 = (x y − 1) = x2 + y. (xy + x) − lt f1 lt f2 xy 2 x2 y

Lathat ´ o, ´ hogy az f3 nem redukalhat ´ o´ f1 e´ s f2 szerint. Egy lehetséges mod ´ a probléma feloldas ´ ara, ´ hogy a fenti S-polinomot elnevezzuk ¨ f3 -nak, e´ s hozza´ adjuk a G generatorrendszerhez: ´ a tovabbiakban ´ legyen tehat ´ G = {f1 , f2 , f3 }. Az uj ´ G szerint az S(f1 , f2 ) polinom a nulla polinomma´ redukalhat ´ o. ´ Hatarozzuk ´ meg most a S(f1 , f3 ) polinomot, majd redukaljuk ´ G szerint: x2 y 2 x2 y 2 2 2 3 2 3 2 3 S(f1 , f3 ) = 2 (xy − 1) − 2 = x − y → x − y − x − y = −y − y. xy x Az el˝oz˝o lépéshez hasonloan, ´ legyen f4 = y 3 + y e´ s legyen G = {f1 , f2 , f3 , f4 }. Szam´ ´ ıtsuk most ki az S(f3 , f4 ) polinomot majd redukaljuk ´ G szerint: S(f3 , f4 ) =

x2 y 3 2 x2 y 3 3 (x + y) − (y + y) = x2 y3

= y 4 − x2 y → y 4 − x2 y − yy 3 − y 2 = −x2 y − y 2 → −x2 y − y 2 + x2 y − 1 = −y 2 − 1. Jegyzet friss´ ıtve:

2007. m´ ajus 8.


31

Ha f5 = y 2 + 1, akkor könnyu ˝ szamol ´ as ´ mutatja, hogy a G = {f1 , . . . , f5 } = {xy 2 + x, x2 y − 1, x2 + y, y 3 + y, y 2 + 1} rendszerben minden S(fi , fj ) polinom a nulla polinomma´ redukalhat ´ o. ´ Tehat ´ ekkor G a fenti ideal ´ Gröbner bazisa. ´ A fenti eljar ´ as ´ altal ´ anos´ ´ ıthato, ´ e´ s az alabbi ´ algoritmus seg´ıtségével egy ideal ´ Gröbner bazisa ´ meghatarozhat ´ o. ´ Legyen X ⊆ R egy véges részhalmaz e´ s legyen I = hXi. 1.) Legyen G = X. 2.) Legyen S = {S(fi, fj ) rem G | ahol fi , fj ∈ G}. 3.) Ha S 6= {0} akkor G = G ∪ S e´ s vissza 2.)-re. 4.) Output G. Tétel 1.11.7 A fenti eljar ´ as ´ veges ´ sok lep ´ es ´ utan ´ veget ´ er ´ outputja pedig az I ideal ´ egy Gröbner bazisa. ´ ´ . Gyakorlat. 2 B IZONYÍ T AS Példa 1.11.8 A Gröbner bazis ´ seg´ıtségével eldönthetjuk, ¨ hogy egy adott polinom eleme-e egy idealnak. ´ Legyen I az el˝oz˝o példaban ´ szerepl˝o ideal, ´ e´ s 4 2 3 4 2 3 legyenek f = x + x y − xy − xy e´ s g = −x + x y − xy − xy. Redukaljuk ´ el˝oször az f polinomot G szerint: f → −xy 3 − xy → 0. Tehat ´ f ∈ I. Redukaljuk ´ most a g polinomot: g → 2x2 y − xy 3 − xy → xy 3 − xy + 2 → −2xy + 2. Tehat, ´ ebben az esetben g rem G 6= 0, e´ s a 1.11.3 következmény miatt, g 6∈ I. Tekintsuk ¨ a 1.11.6 példat, ´ legyen G = {xy 2 + x, x2 y − 1, x2 + y, y 3 + y, y 2 + 1} e´ s I = hGi. Mivel G egy Gröbner bazis, ´ kaljuk, hogy hGi = I and hlt Ii = hlt Gi =

2 2 2 3 2 xy , x y, x , y , y . Vegyuk ¨ e´ szre azonban, hogy a fenti generatorrendszer ´ nem minimalis ´ generatorrendszere ´ a hlt Ii monomialis ´ idealnak, ´ ugyanis példaul ´

2 3 3 2 y ∈ y , tehat ´ y elhagyhato´ a hlt Ii generatorai ´ közul, ¨ e´ s igy y +1 is elhagyhato´ a Gröbner bazisb ´ ol. ´ Hasonloan ´ megmutathato, ´ hogy az x2 y − 1 e´ s az xy 2 + x Jegyzet friss´ ıtve:

2007. m´ ajus 8.

32

Polinomok

polinomok is elhagyhatok. ´ Tehat, ´ a {x2 + y, y 2 + 1} halmaz is Gröbner bazisa ´ I-nek. Egy ideal ´ G Gröbner bazis ´ at ´ minimalisnak ´ nevezunk, ¨ ha tetsz˝oleges g ∈ G esetén lt g 6∈ hlt G \ {lt g}i. Lemma 1.11.9 Minden idealnak ´ letezik ´ minimalis ´ Gröbner bazisa. ´ ´ . A lemma el˝otti gondolatmenetet kell alkalmazni. 2 B IZONYÍ T AS Egy ideal ´ G Gröbner bazis ´ at ´ redukaltnak ´ nevezzuk, ¨ ha g ∈ G esetén g egyik tagja sem eleme a hlt G \ {lt g}i. Tekintsuk ¨ a fenti I idealt. ´ Ekkor x2 +y 2 +y+1 ∈ I e´ s a Gröbner bazis ´ defin´ıcioj ´ ab ´ ol ´ következik, hogy G′ = {x2 + y 2 + y + 1, y 2 + 1} is Gröbner bazisa ´ I-nek. Mivel a G′ els˝o elemének y 2 tagja oszthato´ a masodik ´ ′ 2 2 elem f˝otagjaval, ´ G nem redukalt. ´ Az x +y +y+1 polinom azonban redukalhat ´ o´ 2 2 2 2 az y + 1 polinommal: x + y + y + 1 → x + y. A G ideal ´ redukalt. ´ Tétel 1.11.10 Minden I 6 R idealnak ´ van pontosan egy redukalt ´ Gröbner bazisa ´ (egy fix monomialis ´ rendezesre ´ nezve). ´

1.12. Gr¨ obner bázisok alkalmazásai A Gröbner bazisok ´ egyik legfontosabb alkalmazas ´ at ´ a polimomialis ´ egyenletrendszerek megoldas ´ an ´ al ´ talaljuk. ´ Példa 1.12.1 Tekintsuk ¨ az f = (y 2 + 6)(x − 1) − y(x2 + 1) e´ s

g = (x2 + 6)(y − 1) − x(y 2 + 1)

feletti polinomokat a Q test felett. Az f e´ s g egyenletek meghataroznak ´ két görbét: V (f ) = {(x, y) |f (x, y) = 0} and V (g) = {(x, y) |g(x, y) = 0}. Hatarozzuk ´ meg az V (f ) ∩ V (g) metszetet. El˝oször meghatarozzuk ´ az I = hf, gi Gröbner bazis ´ at. ´ A Gröbner bazis ´ 3 polinombol ´ all: ´ G = {x2 −5x+y 2 −5y +12, y 2x−5xy +6x+y 3 −6y 2 +11y −6, y 4 −6y 3 +15y 2 −26y +24}. Jegyzet friss´ ıtve:

2007. m´ ajus 8.


33

A harmadik polinom csak az y valtoz ´ ot ´ tartalmazza, ezért azt az ismert modon ´ megoldhatjuk e´ s kapjuk, hogy ennek két racionalis ´ gyöke van: 2 e´ s 3. A az els˝o e´ s a masodik ´ polinomba a 2-t helyettes´ıtve az 4x − 10x + 6x + 8 − 24 + 22 − 6 = 0 2 e´ s az x − 5x + 4 − 10 + 12 = x2 − 5x + 6 polinomot kapjuk. A masodik ´ polinom gyökei 2 e´ s 3, ami azt jelenti, hogy ebben az esetben a (3, 2) e´ s (2, 2) metszéspontokat kapjuk. Ha a 3 gyököt helyettes´ıtjuk ¨ be az els˝o két poli2 nomba, akkor a 9x−15x+6x+27−54+33−6 = 0 e´ s az x −5x+9−15+12 = x2 −5x+6 polinomokat kapjuk. A masodik ´ gyökei 2 e´ s 3, melyekb˝ol a (2, 3) e´ s a (3, 3) metszéspontokat kapjuk. Így a két görbének négy racionalis ´ metszéspontja van: (2, 2), (3, 2), (2, 3) e´ s (3, 3). Ezek a metszéspontok a racionalis ´ megoldasai ´ az f = 0, g = 0 egyenletrendszernek is. A következ˝o alkalmazas ´ a geometria terulet´ ¨ er˝ol szarmazik. ´ Példa 1.12.2 Igazoljuk, hogy a haromsz¨ ´ og sulyvonalai ´ egy pontban metszik egymast. ´ Az altal ´ anoss ´ ag ´ megsértése nélkul ¨ feltehetjuk, ¨ hogy a haromsz¨ ´ ogunk ¨ harom ´ csucsa ´ A = (0, 0), B = (1, 0) e´ s az C = (x, y) pontok. Tegyuk ¨ fel, hogy a haromsz¨ ´ ogunk nem elfajulo, ´ ami azzal ekvivalens, hogy y 6= 0. Legyenek P , Q, e´ s R rendre a BC, AC, e´ s az AB oldalak középpontjai. Ekkor P = ((x+1)/2, y/2), Q = (x/2, y/2), e´ s R = (1/2, 0). Legyen S = (u, v) az AP e´ s BQ sulyvonalak ´ metszéspontja. Vegyuk ¨ e´ szre, hogy v 6= 0. Be kell latnunk, ´ hogy a CR sulyvonal ´ athalad ´ az S ponton. Mivel A = (0, 0), a feltétel, hogy S az AP egyenesen fekszik kifejezhet˝o a x+1 u = v y egyenlettel. Mivel y, v 6= 0, ebb˝ol a f1 = uy − v(x + 1) = 0 egyenl˝oséget kapjuk. Hasonloan, ´ az a tény, hogy S a BQ egyenesen fekszik az x−2 u−1 = y v e´ s az f2 = (x − 2)v − (u − 1)y Jegyzet friss´ ıtve:

2007. m´ ajus 8.

34

Polinomok

egyenletekkel fejezhet˝o ki; illetve az, hogy S a CR egyenesen fekszik az x − 1/2 u − 1/2 = v y e´ s az f3 = −2xv + 2yu − y + v egyenletekkel fejezhet˝o ki. Hogyan e´ p´ıtjuk ¨ be az y 6= 0 feltételt a modellunkbe? ¨ Egyszeruen ˝ bevezetunk ¨ egy uj ´ Y valtoz ´ ot, ´ e´ s az y 6= 0 ekvivalens az f4 = yY −1 = 0 polinomialis ´ egyenlettel. Az all´ ´ ıtas, ´ hogy a harom ´ sulyvonal ´ egy pontban metszi egymast ´ következik az f3 ∈ hf1 , f2 , f4 i all´ ´ ıtasb ´ ol. ´ Legyen I = hf1 , f2 , f4 i. Az all´ ´ ıtast ´ az ideal ´ Gröbner bazis ´ anak ´ kiszam´ ´ ıtas ´ aval ´ igazoljuk. A tanult eljar ´ ast ´ alkalmazva kapjuk, hogy a G = {vY − 1/3, y − 3v, x − 3u + 1} redukalt ´ Gröbner bazisa ´ I-nek. Redukaljuk ´ G szerint az f3 polinomot: f3 → −6uv + 3v + 2yu − y → 3v − y → 0. Tehat ´ f3 valoban ´ eleme az I idealnak. ´ Igazoljuk most, hogy a sulyvonalak ´ harmadoljak ´ egymast. ´ Mutassuk meg példaul, ´ hogy S az RC szakasz harmadoloja. ´ Ehhez azt kell belatni, ´ hogy az RS vektor haromszor ´ olyan hosszu ´ mint az RC vektor: 3RS = 3(u − 1/2, v) = (x − 1/2, y) = RC, amib˝ol a g1 = 3u − x − 1 = 0, illetve a g2 = 3v − y = 0 egyenleteket kapjuk. Ezen egyenletek ellentettjei azonban tagjai Gröbner bazisnak, ´ ´ıgy g1 , g2 ∈ I. Tehat ´ az all´ ´ ıtas ´ az RC sulyvonalra ´ következik, e´ s hasonloan ´ meg lehet mutatni a többi sulyvonalra ´ is.


2007. m´ ajus 8.

1. fejezet. Polinomok Polinomok szorzása

Recommend Documents