Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

A.8. Véges testek

A.8. Véges testek

A véges testek közül már számos esetben foglalkoztunk a modulo p maradékosztályok Fp testével, ahol p prím. Néhány másfajta véges test is szerepelt, pl.egy 9 elemű az A.2.2b és egy 16 elemű az A.6.14d feladatban.

Ebben a pontban a véges testek többféle általános jellemzését is megadjuk.

Mindenekelőtt megjegyezzük, hogy a szorzás kommutativitását nem kell külön hangsúlyoznunk, mert Wedderburn nevezetes (és nehéz) tétele szerint véges nemkommutatív test nem létezik.

Előrebocsátjuk még, hogy ebben a pontban egy (általános) véges test elemeit görög nagybetűkkel, a nullelemet 0-val, az egységelemet 1-gyel, magát a testet pedig M-mel fogjuk jelölni.

1. Elemszám

A szisztematikus tárgyalást az elemszámok leírásával kezdjük.

A.8.1 Tétel

(i) Minden véges test elemszáma prímhatvány (beleértve az első hatványokat, azaz magukat a prímeket is).

(ii) Bármely pk prímhatványhoz izomorfiától eltekintve pontosan egy M véges test létezik, amelyre|M|=pk.❶

Ennek alapján pl. 100 elemű test nem létezik, 81 elemű viszont igen. A tételből az is következik, hogy két azonos elemszámú véges test szükségképpen izomorf, tehát pl. ha p prímszám, akkor nincs másfajta p elemű test, mint a modulo p maradékosztályok teste.

2. Összeadás

A következő tétel leírja a véges testek additív csoportjának a struktúráját.

A.8.2 Tétel

Legyen az M véges test elemszáma|M|=pk. Ekkor M az összeadásra nézve izomorf az Fp test feletti (akármelyik) k-dimenziós vektortér, azaz (pl.) Fpk additív csoportjával.❶

Ennek alapján M elemeit olyan k-dimenziós vektoroknak képzelhetjük, amelyek minden komponense Fp-beli, azaz minden komponens egy-egy modulo p maradékosztály és az összeadást ennek megfelelően kell végezni. Ebből következik, hogy bármely θM elemet önmagával p-szer összeadva mindig 0-t kapunk. Ezt úgy is fogalmazhatjuk, hogy az M additív csoportjában a nemnulla elemek (additív) rendje p.

3. Szorzás

A véges testek multiplikatív szerkezete is nagyon szép:

A.8.3 Tétel

Egy véges test nemnulla elemei a szorzásra nézve ciklikus csoportot alkotnak.❶

Ugyanezt úgy is megfogalmazhatjuk, hogy létezik olyan  M elem, amelynek a hatványaiként az M összes nemnulla elemét megkapjuk. Mivel ekkor Δ multiplikatív rendje o(Δ)=|M|–1=pk–1, ezért az M nemnulla elemei egyértelműen felírhatók Δj alakban, ahol j=0,1,2,…,pk–2. Ha speciálisan|M|=p, azaz M=Fp, akkor ez éppen azt jelenti, hogy Δ primitív gyök modulo p.

Megjegyezzük még, hogy a pk elemű test multiplikatív csoportjának ― a ciklikus csoportokra érvényes általános eredménynek megfelelően ― (nemcsak egy, hanem pontosan) ϕ(pk–1) darab generátoreleme van.

Egy véges test multiplikatív csoportjának (akármelyik) generátorelemét a test primitív elemének nevezzük. A pkelemű véges testben tehát ϕ(pk–1) primitív elem található.

4. Vektortér

A továbbiakban fontos szerepe lesz annak, hogy bármely véges test tartalmaz egy Fp típusú testet. Ez éppen az 1 egységelem által generált résztest lesz, amely az 1,1+1,…,1+1+…+1 alakú elemekből áll. Ha |M|=pk, akkor az A.8.2 Tétel szerint az 1 additív rendje (is) p, tehát p darab ilyen alakú (különböző) elem van. Könnyen látható, hogy ezek egy, az Fp-vel izomorf testet alkotnak.

Ennek megfelelően az M-et felfoghatjuk mint az Fp test bővítését. Ez többek között azt is jelenti, hogy M egy k-dimenziós vektortér Fp felett, tehát az A.8.2 Tételbeli izomorfia nemcsak az additív csoportok, hanem a megfelelő vektorterek között is fennáll.

Mindezt az alábbi tételben foglaljuk össze:

A.8.4 Tétel

Legyen az M véges test elemszáma|M|=pk. Ekkor M tartalmaz egy Fp-vel izomorf résztestet és e felett a részteste felett M egy k-dimenziós vektorteret alkot.❶

5. Testbővítés

Most megvizsgáljuk az imént bevezetett M:Fp testbővítés további vonatkozásait (itt erősen támaszkodunk majd az A.7 pontra).

Mivel deg(M:Fp)=k, ezért az A.7.1 feladat alapján minden θMalgebrai elem Fpfelett és degΘ|k.

Megmutatjuk, hogy M:Fpegyszerű bővítés. Legyen az M multiplikatív csoportjának a(z egyik) generátoreleme Δ. Ekkor a Δ-t tartalmazó legszűkebb résztest csak a teljes M lehet (hiszen minden nemnulla elemet már pusztán a szorzással is megkapunk), tehát Fp(Δ)=M.

Ebből az is következik, hogy k=deg(M:Fp)=deg(Fp(Δ):Fp)=

=degmΔ, azaz a Δ-nak az Fp test feletti foka pontosan k.

Ekkor az M-nek mint Fp feletti vektortérnek az 1 ,Δ,Δ2,…, Δk-1 elemek egy bázisát alkotják (itt az 1 az Fp és M testek közös egységelemét jelöli).

Természetesen a multiplikatív csoport generátorelemein, azaz a primitív elemeken kívül más θM elemekre is fennáll(hat) M=(Θ); ez pontosan a(z Fp felett) k-adfokú Θ-kra teljesül.

A fentiek lényegét az alábbi tételben foglaljuk össze:

A.8.5 Tétel

Legyen az M véges test elemszáma|M|=pk, Δ a multiplikatív csoport (egyik) generátoreleme és Fp az M-ben levő p elemű test. Ekkor

(i) M=Fp(Δ);

(ii) 1, Δ, Δ2,…,Δk-1 bázis M-ben mint Fp feletti vektortérben;

(iii) bármely θM-re degΘ|k;

(iv) θM,degθ=kM=Fpθ

6. Faktorgyűrű

Az M=Fp(Δ) előállításból az A.7.12 Tétel szerint kapjuk, hogy M izomorf az Fp[x]/(mΔ) faktorgyűrűvel. Ezt az A.6.6 Tétellel is összevetve a véges testek alábbi igen hasznos jellemzését nyerjük:

A.8.6 Tétel

A pk elemű véges testet megadhatjuk mint az Fp[x]/(f) faktorgyűrűt, ahol f egy k-adfokú irreducibilis polinom Fp felett.❶

Ez azt jelenti, hogy a pk elemű test elemeinek tekinthetjük a legfeljebb k–1-edfokú Fp[x]-beli polinomokat és ezekkel mint az f irreducibilis polinom szerinti osztási maradékokkal kell a műveleteket végezni.

Az A.8.1(ii) és A.8.6 Tételekből az is adódik, hogy az Fp test felett tetszőleges k-ra létezik k-adfokú irreducibilis polinom. Ugyanez érvényes bármely véges test felett is, sőt képletet is tudunk adni az adott fokú irreducibilis polinomok darabszámára (lásd az A.8.12b feladatot és az útmutatásnál szereplő megjegyzést).

Az Fp feletti k-adfokú irreducibilis polinomok között kitüntetett szerepe van azoknak, amelyek a pk elemű véges test primitív elemeinek, azaz a multiplikatív csoport generátorelemeinek a minimálpolinomjai. Ezeket (Fp felett)primitív polinomoknak nevezzük. (Ennek a fogalomnak semmi köze sincs a Gauss-lemmában szereplő, az egész számok feletti primitív polinomokhoz.)

7. Példa

Illusztrációként megkonstruáljuk a 125 elemű testet.

Ehhez az F5 test felett kell egy harmadfokú irreducibilis polinomot találnunk. Mivel egy harmadfokú polinom pontosan akkor irreducibilis, ha nincs gyöke az adott testben (ez magasabb fokszám esetén nem igaz, lásd az A.4.19 feladatot!), ezt könnyen tudjuk ellenőrizni, hiszen csak az F5 test összesen 5 darab elemét kell behelyettesítenünk. Így pl. f=x3+x+1 megfelel.

Az A.8.6 Tétel értelmében ekkor M elemeit a legfeljebb másodfokú α01x2x2 polinomoknak vehetjük, ahol αiF5 és ezekkel a polinomokkal mint az x3+x+1 szerint vett osztási maradékokkal kell számolni.

Például a 3+4x és 3+x2 elemek összege és szorzata (3+4x)+(3+x2)=

=1+4x+x2, illetve

Az M elemeit 340+301=141-beli vektorokkal is jelölhetjük, ekkor bázisnak az 1, x, x2 maradékokat célszerű választani. Ezzel a jelöléssel a fenti vektorok és a velük végzett műveletek a következőképpen festenek:

3 4 0 3 0 1 = 0 3 3   és 010

Jól látszik, hogy ez a fajta felírás kényelmessé teszi az összeadást, a szorzás elvégzésében azonban nem segít; a szorzáshoz mindenképpen a polinomos alakban kell gondolkodnunk, és a minimálpolinom szerinti redukciót kell felhasználnunk.

Hogyan kaphatjuk meg a test multiplikatív csoportjának egy generátorelemét?

A fenti konstrukcióban az x (vagy a második jelölésmóddal, a 010 vektor) akkor lesz megfelelő, ha a (multiplikatív) rendje|M|–1=124. Mivel a Lagrange-tétel alapján a csoport bármely elemének a 124-edik hatványa az egységelem, így csak azt kell ellenőriznünk, hogy kisebb (pozitív) kitevőjű hatványként megkapjuk-e az 1-et. Mivel 124=22·31, ezért elég a 4-edik és a 62-edik hatványt megvizsgálni: ha ezek egyike sem az egységelem, akkor a rend ezek egyikének sem osztója, és így csak 124 lehet.

Az x3=–1–x összefüggés alapján x4= –x x2≠1, tehát ox4. Azt, hogy x62=1 teljesül-e, a leggyorsabban a következőképpen dönthetjük el. Mivel (kommutatív) testben vagyunk, ezért (a nullosztómentesség, valamint x≠0 alapján)

Az x4= –(x+x2) egyenlőséget négyzetre emelve

adódik, majd ezt a binomiális tétellel negyedik hatványra emelve kapjuk, hogy

Mint láttuk, ebből x62=1 következik, tehát az x nem primitív elem.

Ekkor nyilván bármely m-re (xm)62=1, és így az x hatványai sem lehetnek primitív elemek. Emellett a(z összesen) két darab negyedrendű elem sem primitív. Mindezeket kiszűrve, bármelyik más elem viszont már megfelel a multiplikatív csoport generátorának.

Egy másik lehetőség, hogy keresünk F5 felett egy másik harmadfokú irreducibilis polinomot, amely már primitív, ilyen pl. az x3+3x+2, és az e szerinti faktorgyűrűként írjuk fel a 125 elemű testet. Ekkor az x (mint az x3+3x+2 polinom szerinti maradék) generátorelem lesz a multiplikatív csoportban.

Feladatok

A.8.1 Mutassuk meg, hogy egy pk elemű testben szabad tagonként p-edik hatványra emelni, azaz (Θ+Ψ)ppp.

A.8.2 Mivel egyenlő egy véges test összes nemnulla elemének a szorzata, illetve összege?

A.8.3 Hány gyöke van a pk elemű testben az xm-1 polinomnak?

A.8.4 A 13k elemű testben hány olyan Θ≠Ψ elempár létezik, amelyek egymás köbgyökei?

A.8.5

a) Tegyük fel, hogy egy nullosztómentes gyűrűben létezik olyan nemnulla elem, amelyet önmagával valahányszor összeadva a nullelemet kapjuk. Bizonyítsuk be, hogy ekkor létezik egy olyan egyértelműen meghatározott p prímszám, hogy a gyűrű bármely elemét p-szer önmagával összeadva mindig a nullelem adódik.

b) Mutassunk példát olyan végtelen testre, amely rendelkezik ezzel a tulajdonsággal.

Megjegyzés: Ezt a p-t a nullosztómentes gyűrű karakterisztikájának nevezzük. A pk elemű test karakterisztikája tehát p. — Ha nincs ilyen p, azaz egy nemnulla elemet önmagával akárhányszor összeadva sohasem kapjuk a nullelemet, akkor a (nullosztómentes) gyűrűt 0-karakterisztikájúnak vagy végtelen karakterisztikájúnak nevezzük. Így pl. Q, R és C karakterisztikája 0.

A.8.6 Hogyan konstruálhatunk 169, illetve 81 elemű testet?

A.8.7 Mutassuk meg, hogy a pk elemű M test éppen az xpk-x polinom gyökeiből áll [azaz xpk-x=θMx-θ].

M*A.8.8 Legyen f irreducibilis polinom Fpfelett. Igazoljuk, hogy fxpk-x akkor és csak akkor teljesül, ha degf|k.

A.8.9 Bizonyítsuk be, hogy a pk elemű test akkor és csak akkor tartalmaz pn elemű résztestet, ha n|k.

A.8.10 Lássuk be, hogy egy véges test bármely két (különböző) részteste különböző elemszámú.

*A.8.11 Legyen f=xkk-1xk-1+…+α1x+α0 egy primitív polinom Fp felett, és legyen A a következő k×k-as mátrix:

Mutassuk meg, hogy az A (különböző) hatványai és a nullmátrix a mátrixösszeadásra és a mátrixszorzásra nézve egy pk elemű testet alkotnak.

M*A.8.12 Hány k-adfokú, 1 főegyütthatójú

a) primitív; b) irreducibilis

polinom létezik Fp felett?

A.8.13 Tekintsük a p3 elemű M testet mint Fp feletti (3 dimenziós) vektorteret. Nevezzük az M egydimenziós altereit pontoknak, a kétdimenziós altereit pedig egyeneseknek. Egy pont akkor van rajta egy egyenesen, ha a megfelelő alterek tartalmazzák egymást. Mutassuk meg, hogy

a) bármely két egyenesnek egy közös pontja van, és bármely két ponton egy egyenes megy át;

b) mind a pontok, mind az egyenesek száma p2+p+1;

c) minden egyenesen p+1 pont helyezkedik el, és minden ponton p+1 egyenes halad át.

Megjegyzések: A fenti tulajdonságú struktúrákat (nemelfajuló) véges projektív síkoknak nevezzük. Ugyanez a konstrukció a p prím helyett egy pm prímhatvánnyal is elvégezhető, ekkor a p3m elemű véges testet kell a benne levő pm elemű test feletti vektortérnek tekinteni. Megoldatlan probléma, hogy egy véges projektív sík pontjainak a száma lehet-e más, mint p2m+pm+1, ahol p prím.

A véges projektív síkok szolgáltatták a nemtriviális extremális megoldásokat a 9.4.10 feladattal kapcsolatban (lásd a feladat második bizonyítása utáni megjegyzést), és tulajdonképpen projektív síkok szerepeltek („inkognitóban”) a 9.6.1 Tétel bizonyításában is.

A geometriai kapcsolat talán „szemléletesebbé” válik, ha a pontokat definiáló (egydimenziós) alterekből figyelmen kívül hagyjuk a nullvektort. Ekkor az egy pontot jellemző vektorok éppen egymás nemnulla skalárszorosai. Ezt úgy is felfoghatjuk, hogy egy „síkbeli” pontot homogénkoordinátákkal jellemzünk, azaz ugyanazt a pontot kapjuk, ha mindhárom koordinátát egy tetszőleges nemnulla skalárral megszorozzuk. Ez teljesen összhangban van a valós test feletti projektív sík megadásával. [A valós projektív síkot az euklideszi sík ideális pontokkal történő kibővítésével kapjuk, ahol az ideális pontok az adott irányú párhuzamos egyenesek metszéspontjai, és ezek egy ideális egyenest alkotnak. Az euklideszi sík (a1, a2) koordinátájú „közönséges” pontjának a projektív síkon azok a homogén koordinátás (α1, α2, α3) számhármasok felelnek meg, ahol α13=,α1, α232.]

A.8.14

Tekintsük az előző feladatbeli M-et, a pontok továbbra is legyenek az egydimenziós alterek, azonban most az egyeneseknek is az egydimenziós altereket válasszuk. Az illeszkedés definícióját úgy módosítjuk, hogy egy pont akkor van rajta egy egyenesen, ha a pontnak, illetve az egyenesnek megfelelő két (egydimenziós) altér merőleges egymásra. Mutassuk meg, hogy most is teljesülnek az előző feladat állításai.