Matematika | Diszkrét Matematika » Estélyi István - Véges testek algebrai bővítései

http://www.doksihu Eötvös Loránd Tudományegyetem Estélyi István Véges testek algebrai bővítései Szakdolgozat matematika BSc, matematikus szak Témavezető: Dr. Pelikán József egyetemi adjunktus Algebra és Számelmélet Tanszék Budapest, 2010 http://www.doksihu Tartalomjegyzék Bevezetés 1 1. Véges testek algebrai bővítései 1.1 GF (q) algebrai lezártja 1.2 Steinitz-számok 1.3 GF (q N ) automorfizmuscsoportja 1.4 GF (q N ) multiplikatív csoportja . . . . 2 2 2 6 9 2. Polinomok, polinomfüggvények 2.1 Irreducibilitás GF (q) és GF (q N ) felett 2.2 Irreducibilis polinomok konstrukciója 2.3 Polinomfüggvények 13 13 15 17 3. Permutáció-polinomok 3.1 Permutáció-monomok 3.2 q-polinomok 3.3 Dickson-polinomok 18 18 20 24 4. Iterált prezentációk ∞ 4.1 GF (pp ) iterált prezentációi 28 29

Hivatkozások 33 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . http://www.doksihu Bevezetés A testek, testbővítések elmélete Gauss és Galois óta jelentős fejlődésen ment keresztül. Fontos mérföldkő volt ebben Steinitz [12] cikke A racionális számok algebrai bővítéseinek, lezártjának vizsgálata mára klasszikusnak számító algebrai témakör. Bár a véges testek számos gyakorlati alkalmazásuk miatt alpvető algebrai struktúrák, az algebrai bővítéseikkel foglalkozó szakirodalom viszonylag szerény. A szakdolgozat fő célja rövid betekintést nyújtani a véges testek algebrai bővítéseibe. A véges testekre vonatkozó kérdésekben az elsődleges forrás Lidl és Niederreiter [9] terjedelmes monográfiája volt, jóllehet a szakdolgozat inkább Brawley és Schnibben [2] munkájának felépítését követi. A szakdolgozat szerkezete a következő: • Az 1. fejezetben

a véges testek algebrai lezártját ill résztesteinek szerkezetét tárgyaljuk Steinitz nyomán Kitérünk az algebrai bővítések Galois-csoportjára és multiplikatív csoportjára is. • A 2. fejezetben polinomok olyan alapvető tulajdonságait vizsgáljuk, mint pl. az irreducibilitás Megvizsgáljuk, véges testek véges bővítéseire vonatkozó ismert eredmények milyen feltételek mellett teljesülnek tetszőleges algebrai bővítések felett, ill. fogalmaink miként terjeszthetők ki ebben az esetben • A 3. fejezet tárgya egy speciális polinomosztály a permutáció-polinomok Ezek közül a permutáció-monomomok, q-polinomok, valamint a Dicksonpolinomok tulajdonságait vizsgáljuk véges testek ill. tetszőleges algebrai bővítéseik felett • A 4. fejezetben iterált prezentációkkal és explicit bázisokkal foglalkozunk Ezek nem csupán GF (q N ) elemeinek reprezentációját adják a véges eset vektortér szemléletének mintájára, hanem egyúttal eljárást

is adnak a szorzás és összeadás elvégzésére, lehetővé téve konkrét számolások elvégzését véges testek tetszőleges algebrai bővítéseiben. Ezúton szeretném megköszönni témavezetőmnek, Pelikán Józsefnek számos értékes észrevételét, illetve az ajánlott bőséges szakirodalmat, amely nemcsak elengedhetetlen volt e szakdolgozat elkészítéséhez, hanem jóval meg is haladja annak kereteit. 1 http://www.doksihu 1. Véges testek algebrai bővítései 1.1 GF (q) algebrai lezártja Legyen p prím, q = pt prímhatvány, GF (q) a q-elemű test. A véges testek résztesteinek felépítését az alábbi állítás írja le: 1.1 Állítás Tetszőleges m, n pozitív egészekre GF (q m ) ≤ GF (q n ) ⇔ m|n Tekintsük most GF (q n! )-t minden n pozitív egészre. GF (q (n+1)! )-t úgy kapjuk GF (q n! )-ból, hogy veszünk egy pn+1 (x) ∈ GF [q n! , x], deg p = (n + 1) irreducibilis polinomot, ennek egy α gyökét GF (q n! )-hez adjungálva lesz GF (q (n+1)!

) = GF (q n! , α) Így egy láncot kapunk: GF (q) < GF (q 2 ) < · · · < GF (q n! ) < . Mivel testek láncának uniója test, ezért tekinthetjük a következő testet: Γ(q) = ∞ [ GF (q n! ) n=1 1.2 Tétel GF (q) algebrai lezártja Γ(q) Bizonyítás. Legyen α, β ∈ Γ(q) Ekkor elég nagy n-re α, β ∈ GF (q n! ) Mivel α, β algebrai GF (q) felett, ezért α ± β, αβ ∈ GF (q n! ) ≤ Γ(q). Az algebrailag zártsághoz legyen f (x) ∈ Γ[q, x]. Mivel f -nek véges sok együtthatója van, nagy n-re mind GF (q n! )-beliek, így f felbontási teste GF (q n! ) felett GF (q m ), n!|m. GF (q m ) ≤ GF (q m! ) ≤ Γ(q) miatt f valóban eslőfokú tényezőkre bomlik Γ(q) felett. Megjegyzés. GF (q n ) ≤ GF (q n! ) miatt az is igaz, hogy Γ(q) = ∞ S GF (q n ), n=1 q = pt esetén GF (pn ) ≤ GF (q n ) = GF (ptn ), így Γ(p) = Γ(q), vagyis az algebrai lezárt csak a karakterisztikától függ. 1.2 Steinitz-számok Az algebrai lezárt

résztesteinek tárgyalását nagyban megkönnyíti, a pozitív egészek fogalmának megfelelő kiterjesztjtése. A most következő tárgyalásmód Ernst Steinitz [12] cikkéből származik, amely nagy hatással volt a modern algebra fejlődésére. 2 http://www.doksihu 1.3 Definíció Steinitz-egész alatt a következő formális kifejezéseket fogjuk ∞ Q érteni: N = pki i , ahol pi az i-edik prímszám, ki ∈ {0, 1, 2, . ∞} i=1 Jelölés. A Steinitz egészek halmazát jelölje E Világos, hogy N ∈ E -re N ∈ N ⇔ ∀i ki ∈ N, és véges sok kivétellel ki = 0. Műveletek Steinitz-egészekkel, tulajdonságaik • Ha N = ∞ Q i=1 pki i , M = • Szorzás: M N = li = ∞. ∞ Q i=1 ∞ Q i=1 phi i , plii , akkor N = M ⇔ ∀i ki = li ∀i hi = ki + li , ahol hi = ∞, ha ki = ∞ vagy ∞ Q • Oszthatóság: N |M ⇔ ∀i ki ≤ li , ekkor ∃M/N = i=1 plii −ki ∈ E . Itt a kitevőben véges ki -re ∞ − ki = ∞, valamint ∞ − ∞ = 0. •

Legnagyobb közös osztó: (M, N ) = ∞ Q pmin(ki ,li ) i=1 • Legkisebb közös többszörös: [M, N ] = ∞ Q pmax(ki ,li ) i=1 Megjegyzés. Mivel {0, 1, 2, ∞} bármely részhalmazának van minimuma és maximuma is, ezért van értelme Steinitz-számok tetszőleges halmazának legkisebb közös többszöröséről, ill. legnagyobb közös osztójáról beszélni 1.4 Definíció N ∈ E Steinitz-számra legyen GF (q N ) = S GF (q d ). d∈N, d|N Az 1.2 tétel bizonyításának gondolatmenetéből és a hozzá fűzott megjegyzésből látszik, hogy ez valóban test 1.5 Tétel Tekintsük a következő E -ből Γ(q) résztesteinek halmazába menő leképezést: N 7− GF (q N ) Ez bijekció E és Γ(q) GF (q)-t tartalmazó résztesteinek halmaza között, továbbá • GF (q N ) véges ⇔ N véges • GF (q N ) ≤ GF (q M ) ⇔ N |M 3 http://www.doksihu • GF (q N ) ∩ GF (q M ) = GF (q (M,N ) ) • hGF (q N ), GF (q M )i = GF (q [M,N ] ) Bizonyítás. Az

injektivitás igazolásához tegyük fel, hogy M 6= N különböző Steinitz-számok Ekkor van olyan t = pki véges prímhatvány, amely M, N közül pontosan az egyiket osztja, mondjuk t|N , de t - M . Így GF (q t ) ≤ GF (q N ), viszont GF (q t ) * GF (q M ): Indirekte tegyük fel, hogy α ∈ GF (q t ) ≤ GF (q M ), ahol α a GF (q t ) primitív eleme. Ekkor valamely véges d|M -re α ∈ GF (q d ), ahonnan GF (q, α) = GF (q t ) ≤ GF (q d ) ≤ GF (q M ) miatt t|M következne, ami ellentmondás. A szürjektivitás igazolásához tekintsünk egy rögzített GF (q) ≤ F ≤ Γ(q) közbülső testet. Legyen S = {n ≥ 1 : GF (q n ) ≤ F} Ekkor   1∈S  [ n ∈ S ⇒ ∀d|n d ∈ S ⇒ F = GF (q n )   n∈S a, b ∈ S ⇒ (a, b) ∈ S Ha mutatunk egy N Steinitz-egészt, melyre n ∈ S ⇔ n|N , akkor készen vagyunk. Legyen N az S elemeinek legkisebb közös többszöröse Ez könnyen ellenőrizhetően megfelelő. A tétel további állításai azonnal adódnak

GF (q N ) 1.4 definíciójából és abból, hogy m, n pozitív egészekre GF (q m ) ≤ GF (q n ) ⇔ m|n. 1.51 Következmény Ha egy GF (q) ≤ F ≤ Γ(q) közbülső test minden ∞ valódi részteste véges, akkor F véges, vagy F = GF (q r ), ahol r prím. 1.52 Következmény Γ(q) jellemezhető úgy, mint GF (q Ω ), ahol Ω = ∞ Q i=1 p∞ i . 1.53 Következmény Γ(q)-nak nincs maximális részteste, azaz ∀F < Γ(q) valódi résztesthez ∃K : F < K < Γ(q) közbülső valódi résztest. 1.54 Következmény ∀F < Γ(q) [ Γ(q) : F ] ∈ / N, az algebrai lezárt egyik valódi résztestének sem véges fokú bővítése. Az eddigiekben a p-karakterisztikájú véges testek algebrai bővítéseit bizonyos véges testek láncának uniójaként állítottuk elő. Ez a szemlélet motiválja a következő definíciókat, melyek lehetővé teszik GF (q N ) kategóriaelméleti felépítését 4 http://www.doksihu 1.6 Definíció Osztósorozatnak azon d0 , d1 ,

pozitív egészekből álló (véges vagy végtelen) szigorúan monoton növő sorozatokat nevezzük, melyekre d0 = 1 és ∀i di |di+1 teljesül. Egy osztósorozat az N Steinitz-számhoz tart, ha tagjainak legkisebb közös többszöröse, [d0 , di , . ] = N 1.61 Következmény Tetszőleges (di ) osztósorozatra igazak a következők: • ∃N Steinitz-szám, melyre di N • Egy d pozitív egészre d|N ⇔ ∃i d|di 1.62 Következmény Az osztósorozat éppen akkor véges, ha ∃i di = N = lim di . i∞ Megjegyzés. Az N -hez tartó osztósorozatok az N Steinitz-szám osztóhálójának azon 1-gyel kezdődő részláncai, melyek legkisebb(egyetlen) felső korlátja az N . 1.7 Definíció hI, ≤i irányított halmaz, ha a ≤ kétváltozós reláció reflexív és tranzitív, továbbá I bármely két elemének létezik felső korlátja. 1.8 Definíció (Direkt rendszer) Legyen C kategória, hI, ≤i irányított halmaz, {Xi : i ∈ I} ⊆ Ob C a C objektumainak I elemeivel

indexelt családja, továbbá ∀i ≤ j-re fij : Xi Xj morfizmusok, melyekre • ∀i ∈ I fii = idXi • ∀i ≤ j ≤ k fik = fjk ◦ fij Ekkor az hXi , fij i párt I feletti direkt rendszernek nevezzük. 1.9 Definíció (Direkt limesz) Legyen hXi , fij i a C kategória objektumainak és morfizmusainak direkt rendszere Ennek direkt limesze a hX, φi i pár, ahol X ∈ Ob C, a φi : Xi X morfizmusokra pedig ∀i ≤ j esetén teljesül φi = φj ◦ fij . Jelölés: X = lim Xi − Az hX, φi i pár univerzális abban az értelemben, hogy ha hY, ψi i szintén a fenti tulajdonságokkal rendelkező pár, akkor egyértelműen létezik egy u : X Y morfizmus, melyre az alábbi diagram minden i ≤ j esetén kommutatív: 5 http://www.doksihu fij /X s j s 22 KKK φi φj ss s 22 KKK ss K s 22 KK s s % ys 22 X 22 2  ψj ψi 22  22 22  u 22  22     Xi2 KK Y Nem minden kategóriában létezik direkt limesz, de esetünkben kategóriánk objektumai algebrai

struktúrával ellátott halmazok, ezért a létezés rögtön adódik a következő konstrukcióból: 1.10 Állítás Tetszőleges N Steinitz-számhoz tartó (di ) osztósorozatra a hGF (q di ), ≤i direkt rendszer, melynek direkt limesze GF (q N ). Ez ugyanaz, mintha a testek diszjunk unióját faktorizálnánk a következő ∼ ekvivalenciarelációval: xi ∈ GF (q di ), xj ∈ GF (q dj ) esetén xi ∼ xj , ha ∃k : fik (xi ) = fjk (xj ) ∈ GF (q dk ) N di ∞ a di  GF (q ) GF (q ) = lim GF (q ) = − i=1 ∼ Bizonyítás. Világos, hogy GF (q di ) testek az fij : GF (q di ) , GF (q dj ) beágyazásokkal direkt rendszert alkotnak A φi kanonikus leképezések könnyen adódnak: minden xi ∈ GF (q di ) elemhez a ∼ szerinti [x] ∈ GF (q N ) ekvivalenciaosztályukat rendelik. Ezek segítségével definiáljuk GF (q N )-en a testműveleteket: [x] + [y] = [fik (x) + fjk (y)]. Tetszőleges x, y reprezentánsokhoz található ugyanis olyan GF (q dk ) test, melyben az x és

y alkalmas fik ill. fjk szerinti képei benne vannak, így ezek ott összeadhatók, az összeg ekvivalenciaosztálya pedig megfelelő választás az ekvivalenciaosztályok összegének. Ezzel tetszőleges GF (q) véges test összes algebrai bővítését általánosabban is definiáltuk, kiegészítve az 1.4 definíciót 1.3 GF (q N ) automorfizmuscsoportja Tekintsünk egy K|F testbővítést. K egy τ automorfizmusa F-automorfizmus, ha elemenként fixen hagyja F-et Ezen testautomorfizmusok csoportot 6 http://www.doksihu alkotnak a kompozícióra nézve, amit a testbővítés Galois-csoportjának nevezünk: Gal(K|F). Tudjuk, hogy ha n ∈ N, akkor: 1.11 Tétel i Gal GF (q n ) | GF (q) = {σi | σi (x) = xq , 1 ≤ i ≤ n} = hσ1 i ∼ = Zn   Megvizsgáljuk, mi lehet Gal(GF (q N ) | GF (q)), ha N Steinitz-szám. Legyen τ a GF (q N ) egy adott automorfizmusa, (di ) N osztósorozat. Ekkor ∀i-re τi = τ |GF (qdi ) szintén GF (q)-automorfizmusa GF (q di )-nek, így az 1.11

tétel miatt ∃!ti : 0 ≤ ti ≤ di , t τ (α) = τi (α) = αq i ∀α ∈ GF (q di ) Így a τ automorfizmust azonosíthatjuk a nemnegatív egészekből álló (ti ) sorozattal. GF (q di ) , GF (q di+1 ) miatt τi+1 (α) = τi (α) ∀α ∈ GF (q di ) . 0 ≤ ti ≤ di miatt ti+1 = ai di + ri ahol 1 ≤ ri ≤ di és 0 ≤ ai < di+1 di di α ∈ GF (q ) esetén t  τi+1 (α) = αq i = αq a i di qri Így rekurzíve ti+1 = ai di + ti , 0 ≤ ai < = αq di+1 , di ri =⇒ ti = ri ezt iterálva ti+1 = a0 + a1 d1 + . ai di (a0 = t1 ) Ezen felbátorodva: 1.12 Definíció Egy (di ) osztósorozatra az A = ∞ P ai di , ∀i (0 ≤ ai < i=0 di+1 ) di formális összeget (di )-alapú osztósornak nevezzük. 1.13 Definíció (Osztósorok összege) Az A = tósorok összege A + B = C = ∞ P ∞ P i=0 ai d i , B= ∞ P bi di osz- i=0 ci di osztósor, ahol ci a tagonkénti összeg i=0 átvitellel, vagyis c0 = a0 + b0 mod c1 = a1 + b1 + j mod dd12 ,

stb. d1 , d0 és ha a0 + b0 = j dd10 + c0 , akkor Megjegyzés. Vegyük észre, hogy ha N véges, akkor az osztósorok fenti összeadása épp a modN összeadás 7 http://www.doksihu 1.131 Példa Tekintsük a (10i ) osztósorozatot, legyen A = 2 9 + 8.10 (bi = 0, ha i ≥ 2) Ekkor A + B = 1 + 110 + 310 + ∞ P 2.10i , B = i=0 ∞ P 2.10i i=3 Ezzel analóg módon definiálható az osztósorok kivonása is. Megfigyelhetjük, hogy egy (di ) osztósorozatra a (di )-alapú osztósorok egy G(di ) Abelcsoportot alkotnak a 113 definícióbeli összeadásra nézve Ez a csoport valójában izomorfia erejéig független a (di ) osztósorozat választásától, ezért a továbbiakban Gd -vel jelöljük. 1.14 Definíció Legyen A = ∞ P ai di egy (di )-alapú osztósor. Általánosított i=0 q-monom alatt a következő formális kifejezést értjük: A mA (x) = xq = xq a0 +a1 d1 +.  a = (xq 0 )q a1 d1 . Láthatjuk, hogy mA (x) azonosítható a GF (q N ) résztesteinek

automorfizmusaiból álló iterált függvénysorozattal. Ha A véges, mA (x) közönséges q-polinom. Behelyettesítéssel mA (x) egy GF (q N )-en értelmezett függvénynek tekinthető a következőképpen: mA (x) : GF (q N ) / GF (q N ) α ahol A(k) az A k-adik részletösszege: A(k) = / k P αq A(k) ai di . Ez azért jó, mert min- i=0 d den α ∈ GF (q N ) benne van egy GF (q dk ) résztestbe, azaz (α)q k = α. Ezért r q dk |r esetén αq = α, vagyis az A osztósor k-nál nagyobb indexű tagjaihoz tartozó automorfizmusok indentikusan hatnak. Mindezt a következőképpen foglalhatjuk össze: 1.15 Tétel Legyen N Steinitz-szám, (di ) N osztósorozat Ekkor Gal GF (q N ) | GF (q) = {mA (x) : A (di )−alapú osztósor} ∼ = Gd   Itt mA ◦ mB = mA+B , az indexben a 1.13 definícióbeli összeadást értve Bizonyítás. Legyen τ a GF (q N ) tetszőleges GF (q)-automorfizmusa Ekkor τ -t először egyértelműen azonosíthatjuk a nemnegatív egészekből álló

8 http://www.doksihu (ti ) sorozattal, majd az ebből előállítható A osztósorral. A fentiek alapján ekkor GF (q N )-en τ (x) = mA (x). Másrészt mA iterált függvénysorozat alakjából látható, hogy mA minden A osztósorra GF (q N ) egy GF (q)-automorfizmusát adja. Ha A, B különböző osztósorok, akkor A(i) 6= B(i) valamely i-re, így mA |GF (qdi ) = mA(i) 6= mB(i) = mB |GF (qdi ) Tehát mA és mB különbözők GF (q di )-n, ezért a bővebb GF (q N )-en is. Az mA (mB (x)) = mA+B (x) azonosságból rögtön adódik, hogy mA ← A izomorfizmus a Galois-csoport és Gd között. 1.4 GF (q N ) multiplikatív csoportja Véges testek multiplikatív csoportja, sőt tetszőleges test multiplikatív csoportjának véges részcsoportjai jól ismertek: 1.16 Tétel Tetszőleges K test K ∗ multiplikatív csoportjának véges részcsoportja ciklikus Mielőtt rátérnénk GF (q N ) multiplikatív csoportjának meghatározására, tegyünk néhány észrevételt. 1.17

Definíció Legyen q prímhatvány, di N az N Steinitz-számhoz tartó osztósorozat. Legyen q N − 1 = lim (q di − 1) i∞ Megjegyzés. Mivel xm − 1|xn − 1 ⇔ m|n, q N − 1 jóldefiniált Steinitz-szám Nem nyilvánvaló azonban, miként áll elő kanonikus alakban. 1.171 Példa ∞ 22 − 1 = (2 − 1)(2 + 1)(22 + 1) · · · = ∞ Y Fi i=1 i−1 ahol Fi = 22 + 1, az i-edik Fermat-szám. A fenti definíció segítségével könnyebben megfogalmazható a következő tétel: 1.18 Tétel GF (q N )∗ -ban pontosan akkor van r-edrendű elem, ha r|q N − 1 Ekkor az r-edrendű elemek száma ϕ(r), ahol ϕ az Euler-függvény. 9 http://www.doksihu Bizonyítás. Tegyük fel, hogy r|q N −1 ⇔ r|q di −1, ha i ≥ j Ekkor minden i ≥ j-re GF (q di )-ben ϕ(r) darab r-edrendű elem van, így GF (q N )-ben is. Most legyen α ∈ GF (q N ) r-edrendű elem. Ekkor α ∈ GF (q di ) valamely i-re, így α ∈ GF (q di ) ≤ GF (q N ), ahonnan r|q di −1, q di −1|q N

−1 ⇒ r|q N −1. 1.181 Következmény GF (q N )∗ Abel torziócsoport, hiszen minden elem rendje véges. Az Abel torziócsoportok szerkezetét írja le a következő lemma: 1.19 Lemma Ha G Abel torziócsoport, akkor G = Q G` , ahol ` prím k G` = {α | ∃k : α` = 1} az `-hatvány rendű elemek részcsoportja. Bizonyítás. Ha g ∈ hGp | p 6= ` prími, akkor előáll g = ahol o(gi ) = pki i (pi 6= `). Legyen m = t Q i=1 t Q i=1 pki i . Ekkor g m = givi alakban, t Q i=1 givi m = 1, azaz o(g)|m. Mivel ` - m, ezért ` - o(g) Tehát hGp | p 6= ` prími-ben nincsen T valódi(6= 1) `-hatvány rendű elem, azaz hGp | p 6= ` prími G` = {1}. Q Gp , már csak azt kell belátni, hogy G minden Így hGp | p prími = p prím eleme előáll g = t Q i=1 ni = Q j6=i gini alakban, ahol gi ∈ Gpi . Legyen o(g) = n = t Q i=1 pki i , k pj j . Az ni -k (1 ≤ i ≤ t) legnagyobb közös osztója 1, így megfelelő vi ∈ Z (1 ≤ i ≤ t) együtthatókkal  felírás, mivel

gi = g ni választással g ni t P i=1 p i vi ni = 1, g = t Q g vi ni . Ez egy jó i=1 = g n = 1. A multiplikatív csoportra térve vegyük észre, hogy q = pt esetén GF (q N ) = GF (ptN ), ezért a prímtest felett eleve is feltételezett véges bővítés foka az általánosság megszorítása nélkül beolvasztható az N Steinitz-számba. Tételünk így a következő: 1.20 Tétel Legyen N Steinitz-szám, K = GF (pN ), p = charK Q Ekkor K ∗ = K` , ahol K` ∼ = Z`v , ha `v k pN − 1, azaz: `6=p prím ` 6= 2 esetén K` ∼ = ( {1} ha d - N , ahol d = o` (p) Z`k+s ha d|N és az ` kitevője N -ben k, pd − 1-ben s 10 prím. http://www.doksihu ` = 2 esetén ( K2 ∼ = {1} ha 2 - N vagy p = 2 Z2s+k−1 ha 2|N és a 2 kitevője N -ben k, p2 − 1-ben s Bizonyítás. Az 119 lemma alapján megkapjuk K ∗ előállítását a kívánt direktszorzat alakban. Az 118 tétel alapján α ∈ K` , o(α) = `v pontosan akkor lesz legmagasabb (`-hatvány) rendű elem, ha `v k

pN − 1. hαi ∼ = Z`v ≤ K` , az 1.18 tétel elemszámokra vonatkozó részéből azonnal adódik, hogy K` ∼ = Z`v . Vegyük észre, hogy p-edrendű elem nincs is K ∗ -ban, mivel p|pN −1 estetén valamely, i > 0-ra p|pdi −1 lenne, ami ellentmondás. Tehát Kp = {1} Legyen most ` páratlan prím, melyre K` szerepel a direktszorzatban. Ekkor szerkezete miatt K` -ben van `-edrendű elem, így `|pN − 1, ∃i : `|pdi − 1, azaz o` (p)|di , di |N ⇒ o` (p)|N . Tehát d = o` (p) jelöléssel d|N szükséges Az eddigiek alapján d|N esetén k = ∞ ⇔ K` ∼ = Z`∞ . Ezért a továbbiakban feltehető, hogy d|N és k ∈ N. Választunk egy speciális N -hez tartó osztósorozatot: d0 = 1, d1 = d, . dk+1 = d`k , dk+2 = N . Legyen K (i) = GF (pdi ), M = N/dk+1 Most (i) i szerinti teljes indukcióval belátjuk, hogy K` ∼ = Z`s+i−1 , vagy ami ezzel i−1 s+i−1 d` ekvivalens: ` kp −1. Ha i = 1, valóban, s definíciója szerint `s k pd − 1. Az indukciós lépéshez

1 ≤ i ≤ k esetén tekintsük az alábbi azonosságot:  i pd` − 1 = pd` i−1  − 1 (pd` i−1 )`−1 + · · · + pd` i−1 +1  i−1 Itt az első tényezőben `s+i−1 k pd` − 1, ami maga az indukciós feltevés. i = 1 esetén ∃a ∈ N : pd = a` + 1, a binomiális tétel szerint (pd )j ≡ ja` + 1 (mod `2 ) (0 ≤ l ≤ ` − 1), így `−1  X i−1 pd` l ≡ j=0 `−1 X (ja` + 1) ≡ j=0 i ≥ 2 esetén s+i−1 ≥ 2, pd` eleve `−1  X i−1 pd` j ≡` i−1 (` − 1)` a` + ` ≡ ` (mod `2 ) 2 ≡ 1 (mod `s+i−1 ) miatt a második tényezőre (mod `s+i−1 ) ⇒ j=0 adódik. Látható tehát, hogy ` k `−1  X pd` i−1 j ≡ ` (mod `2 ) j=0 P`−1  j=0 pd` i−1 j . Ezzel az indukciós lépést k 1 ≤ i ≤ k esetén igazoltuk. Végül kell még, hogy ha `s+k k pd` − 1, akkor 11 http://www.doksihu k `s+k k pd` M − 1, azaz `s+k k pN − 1. Ez azért igaz, mert ∀m ∈ N : m|M -re ` - M ⇒ ` - m, így p

d`k m −1= p d`k m−1 X ! −1 p  d`k j ! j=0  k j ahol m−1 pd` ≡ m (mod `), tehát nem osztható `-lel. j=0 Legyen most ` = 2 (ez eleve csak p 6= 2 esetén érdekes). Ekkor 1 = o2 (p), vagyis o2 (p)|N triviálisan igaz, így k = ∞ ⇔ K2 ∼ = Z2∞ . A továbbiakban 2 k ∈ N , és p ≡ 1 (mod 8) miatt s ≥ 3. Tekintsük a következő N -hez tartó osztósorozatot: d0 = 1, d1 = 2, . dk = 2k , dk+1 = N Legyen M = N/2k (i) Most i szerinti teljes indukcióval belátjuk, hogy K2 ∼ = Z2s+i−1 ⇔ 2s+i−1 k i p2 − 1. Ez i = 1-re s definíciójából adódik, az indukciós lépés 1 ≤ i ≤ k esetén ugyanúgy megy, mint előbb: P  i+1 pdi+1 − 1 = p2  − 1 = pd i − 1 pd i + 1  Itt 2s+i−1 k pdi −1 maga az indukciós feltevés, 2 k pdi +1 pedig azért áll fenn, mert egyrészt pdi + 1 páros, másrészt 4|pdi + 1 esetén 4| [(pdi + 1) − (pdi − 1)] lenne, ami ellentmondás. Végül 2s+k−1 k pN − 1, mert, ∀m ∈ N : m|M -re 2

- M ⇒ 2 - m, így p 2k m −1= p 2k ! −1 m−1 X p  2k j ! j=0 ahol a második tényező páratlan sok páratlan szám összege, tehát páratlan. Ezzel a tételt igazoltuk. 1.201 Példa GF (pΩ )∗ = Y Z`∞ `6=p prím 1.202 Példa Mivel a Fermat-számok páronként relatív prímek, az 1171 példa alapján azt kapjuk, hogy 2∞ ∗ GF (2 ) = ∞ Y i=1 12 ZFi http://www.doksihu 2. Polinomok, polinomfüggvények Ebben a fejeztben különféle polinomokkal kapcsolatos állítások kerülnek tárgyalásra, melyek segítségével kirajzolódnak bizonyos hasonlóságok és eltérések a véges testek ill. végtelen algebrai bővítéseik között Megfigyelhetjük, hogy némely véges testekre vonatkozó állítás szinte egy az egyben általánosítható. 2.1 Irreducibilitás GF (q) és GF (q N ) felett Ha a α algebrai GF (p) felett, akkor GF (p) feletti minimálpolinomját m(x)-szel jelölve azt kapjuk, hogy GF [p, α] ∼ = GF [p, x]/(m(x)) (2.11) Ha α

a GF (q) véges test primitív eleme, azaz GF (q)∗ = hαi, akkor m(x) ∈ GF [p, x] irreducibilis és deg m = t, ahol (q = pt ). 2.1 Tétel Tetszőleges t pozitív egészre létezik t-edfokú m(x) ∈ GF (p), GF (p) felett irreducibilis polinom, például GF (pt ) primitív elemeinek GF (p) feletti minimálpolinomjai. Megjegyzés. Utóbbi polinomokat primitív polinomnak nevezve láthatjuk, hogy minden primitív polinom irreducibilis, de korántsem minden irreducibilis polinom primitív. Pl GF [2, x]-ben három 4-edfokú irreducibilis polinom van: x4 + x + 1, x4 + x3 + 1, x4 + x3 + x2 + x + 1, de csak az első kettő primitív. Tekintsük az alábbi közismert tételeket: 2.2 Tétel Tetszőleges q prímhatvány és n pozitív egész esetén létezik p(x) ∈ GF [q, x] felett irreducibilis polinom. 2.3 Tétel Egy p(x) ∈ GF [q, x] m-edfokú irreducibilis polinom GF [q t , x]ben d = (m, t) darab, egyenként m/d-edfokú irreducibilis tényező szorzatára bomlik. Nevezetesen, p(x)

pontosan akkor irreducibilis GF (q t ) felett, ha (m, t) = 1. Nézzük, miként általánosíthatók GF (q) tetszőleges algebrai bővítéseire. A 2.3 tétel megfelelője a következő tétel: 2.4 Tétel Legyenek T, K Steinitz-számok, p(x) ∈ GF [q T , x] m-edfokú irreducibilis polinom Ekkor p(x) GF (q T K ) fölött d = (m, K) darab m/d-edfokú irreducibilis tényező szorzata. 13 http://www.doksihu Bizonyítás. Legyen GF (q t ) a p(x) együtthatóteste Szükségképpen t|T , legyen R = T /t. Egy (ri ) R osztósorozatra (tri ) T Mivel p(x) irreducibilis GF (q T ) fölött, így GF (q tri ) fölött is minden i-re Ezért a 23 tétel alapján ∀i : (m, ri ) = 1, tehát (m, R) = 1. Ha most (ki ) K osztósorozat, akkor (tri ki ) T K. d = (m, K) választással látható, hogy nagy i-re, mondjuk i ≥ j-re d = (m, ki ), sőt d = (m, ri ki ) Istmét a 23 tételt alkalmazva azt kapjuk, hogy GF [q trj kj , x]-ben p(x) d darab m/d-edfokú irreducibilis tényezőre bomlik. Ezen

polinomok egyike legyen ps (x) Megmutatjuk, hogy tovább bővítve ps (x) irreducibilis marad, tehát ez már a GF (q T K ) feletti felbontás. Tekintsük i ≥ j-re ui = rrji kkji -t. Vegyük észre, hogy (m, ui ) = 1, ahonnan a 23 tétel következtében ps (x) irreducibilis GF (q trj kj ui ) = GF (q tri ki ) felett minden i-re. Ezért ps (x) irreducibilis GF (q T K ) felett is, a tételt igazoltuk 2.41 Következmény Tetszőleges T, K Steinitz-számokra egy GF (q T ) feletti p(x), deg p = m irreducibilis polinom pontosan akkor lesz GF (q T K ) felett is irreducibilis, ha (m, K) = 1. A 2.2 tétel mintájára a következő tétel mondható ki a GF (q N ) feletti irreducibilis polinomok fokairól: 2.5 Tétel Legyen m pozitív egész, N Steinitz-szám Pontosan akkor létezik GF [q N , x]-ben irreducibilis m-edfokú polinom, ha m minden p prímosztójára Q p - N . Ha S = p, akkor ezzel ekvivalens, hogy p|N, p prím p(x) ∈ GF [q N , x], deg p(x) = m irreducibilis ⇐⇒ (m, S) = 1.

Bizonyítás. Először tegyük fel, hogy p(x) ∈ GF [q N , x], deg p(x) = m irreducibilis és a p prímre p∞ |N . Ha p(x) GF (q) feletti együtthatótestét GF (q t ) jelöli, akkor p(x) a GF (q N ) bármely részteste felett irreducibilis, ∞ nevezetesen GF (q t ) és GF (q tp ) felett is. Így a 241 következmény szerint (m, p∞ ) = 1, azaz p - m. Most tegyük fel, hogy (m, S) = 1. Legyen N = ∞ Q i=1 N = M R, ahol, M = Q pi |m pki i . Ekkor N felírható pki i . (m, S) = 1 miatt M véges, így GF (q M ) felett létezik irreducibilis m-edfokú p(x) polinom. Mivel (m, R) = 1, a 241 következmény szerint ez a p(x) polinom irreducibilis GF (q M R ) = GF (q N ) felett is. 14 http://www.doksihu 2.2 Irreducibilis polinomok konstrukciója Az alábbiakban ismertetünk egy rekurzív módszert, ami alkalmas tetszőlegesen nagy fokú irreducibilis polinomok előálítására. 2.6 Definíció Az f (x) n-edfokú polinom reciproka az f ∗ (x) = xn f ( x1 ) polinom. f (x)

reciprok polinom, ha f (x) = f ∗ (x) Tekintsük az alábbi polinomhalmazokat: • Pn = {f (x) ∈ GF [q, x] | deg f = n} • Sn = {f (x) ∈ GF [q, x] | deg f = n, f = f ∗ } A következő leképezéseket vizsgáljuk: φ : Pn S2n , φ(f (x)) = xn f (x + x1 ). A gk (x, 1) = 2Tk (x/2) Dickson-polinomok segítségével meghatározható φ inverze is. Tetszőleges b(x) = n−1 P bi (x2n−i + xi ) + bn xn ∈ S2n reciprok poli- i=0 nomra legyen ψ : S2n Pn , ψ(b(x)) = n−1 P bi gn−i (x, 1) + bn . Kimondható az i=0 alábbi tétel: 2.7 Tétel Az előbb definiált φ, ψ leképezések az alábbi tulajdonságokkal rendelkeznek: 1. φ ◦ ψ = idS2n , ψ ◦ φ = idPn 2. φ és ψ multiplikatív 3. d1 = deg f1 > deg f2 = d2 =⇒ φ(f1 + f2 ) = φ(f1 ) + xd1 −d2 φ(f2 ) 4. Ha b(x) ∈ S2n irreducibilis, akkor ψ(b(x)) is irreducibilis Ha a(x) ∈ Pn Sn , akkor ψ(a(x)a∗ (x)) irreducibilis. Bizonyítás. 1) Ha f (x) = n P ai xi , akkor φ(f (x)) = xn i=0 φ(f (x))∗

= x2n (x−n ) n−1 X Pn−1 i=0 ai (x + x−1 )i ∈ P2n ai (x + x−1 )i = xn f (x + x−1 ) = φ(f (x)), i=0 ezért φ(Pn ) ⊂ S2n . A fenti b(x)-et behelyettesítve: φ ◦ ψ(b(x)) = φ  n−1 X  bi gn−i (x, 1) + bn = xn i=0  n−1 X i=0 15  bi gn−i (x + x−1 , 1) + bn . http://www.doksihu A 3.19 állítást alkalmazva ez nem más, mint xn  n−1 X  bi (xn−i + x−(n−i) ) + bn = i=0 n−1 X bi (x2n−i + xi ) + bn xn = b(x). i=0 Tehát φ◦ψ = idS2n . A befejezéshez azt kell még észrevenni, hogy Pn és S2n elemszáma megegyezik: egy Pn -beli polinom főegyütthatója nemnulla, így az (p − 1)-féle lehet, mivel a többi együtthatóra nincs megkötés, |Pn | = (p − 1)pn . Az S2n -beli polinomok főegyütthatója persze itt nemnulla, de szimmetriaokok miatt csak n további együtthatót választhatunk szabadon. Így S2n = (p − 1)pn . 2) Legyenek f, g ∈ Pn polinomok, deg f (x) = r, deg g(x) = s. Ekkor φ((f g)(x)) = xr+s (f

g)(x+x−1 ) = xr f (x+x−1 )xs g(x+x−1 ) = φ(f (x))φ(g(x)). Most tegyük fel, hogy b, c ∈ S2n . Az 1 rész illetve idS2n és φ multiplikativitása alapján   φ ψ b(x)c(x)           = b(x)c(x) = φ ψ(b(x)) φ ψ(c(x)) = φ ψ b(x) ψ c(x) .   Istmét az 1. miatt φ injektív, szükségképpen ψ b(x)c(x) = ψ(b(x))ψ(c(x)) 3) Annyit kell csak észrevenni, hogy φ((f1 +f2 )(x)) = xd1 (f1 +f2 )(x+x−1 ) = xd1 f1 (x+x−1 )+xd1 −d2 xd2 f2 (x+x−1 ) 4) Indirekte tegyük fel, hogy egy b(x) ∈ S2n irreducibilis polinomra ψ(b(x)) = f (x)g(x), ahol deg f deg g ≥ 1. Ekkor a 1 és 2 rész alapján b(x) = (φ ◦ ψ)(b(x)) = φ(f (x))φ(g(x)), ami ellentmond b(x) irreducibilitásának. A második állításhoz tegyük fel, hogy a(x) ∈ Pn Sn , és ψ(a(x)a∗ (x)) = u(x)v(x), deg u, deg v ≥ 1. Erre φ-t alkalmazva a(x)a∗ (x) = φ(u(x))φ(v(x)). Mivel a(x) irreducibilis, a(x) osztja φ(u(x)) ill. φ(v(x)) valamelyikét, mondjuk a(x) | φ(u(x))

Másrészt a∗ (x) is irreducibilis és a(x) 6= a∗ (x), ezért a(x)a∗ (x) is osztja φ(u(x))-et, ami deg v(x) > 1 ⇒ deg φ(v(x)) > 2 miatt ellentmondás. 16 http://www.doksihu A φ leképezés iterálásával egy alkalmasan választott kezdőpolinomból reciprok irreducibilis 1-főegyütthatós – H. Meyn [10]-beli szóhasználatával élve "srim" (self-reciprocal, irreducible, monic) – polinomok végtelen sorozatát képezhetjük. Ezt a tényt 2 karakterisztikában Meyn [10], páratlan karakterisztikában S D Cohen [3] igazolták Egy ilyen konkrét polinomsorozattal, ∞ ∞ ahol a kezdőpolinom n-edfokú, megadható GF (pn·2 ) ill. GF (pn·2 ) iterált prezentációja. A kezdőpolinom választására pl az alábbi állítás ad kiindulási feltételt: 2.8 Állítás Legyen f (x) ∈ Pn irreducibilis polinom A φ(f (x)) polinom pontosan akkor irreducibilis GF (q n ) felett, ha x2 − βx + 1 ∈ GF [q n , x] is irreducibilis, ahol β az f (x)

tetszőleges gyökét jelöli GF (q n )-ben. Bizonyítás. Pontosan akkor lesz egy α ∈ GF (q n ) elemre φ(f (α)) = αn f (α + α−1 ) 6= 0, ha f (x) egyik β gyökére sem teljesül β = α + α−1 . Ez épp azt jelenti, hogy x2 − βx + 1-nek nincs α gyöke GF (q n )-ben, ami ekvivalens a x2 − βx + 1 polinom GF (q n ) feletti irreducibilitásával. 2.3 Polinomfüggvények Behelyettesítés révén minden f (x) ∈ GF [q, x] polinom reprezentál egy f : GF (q) − GF (q) függvényt. Könnyen adódik az alábbi állítás: 2.9 Állítás Minden f : GF (q) − GF (q) függvényhez található f (x) ∈ GF (q) polinom, ami reprezentálja. Ha még azt is feltesszük, hogy deg f < q, akkor ez a reprezentáns polinom egyértelmű. Valójában az is igaz, hogy f (x) és g(x) polinomok pontosan akkor reprezentájlák ugyanazt a függvényt, ha f (x) ≡ g(x) (mod xq − x). Megjegyzés. Ez a tulajdonság megkülönbözteti a véges testeket más kommutatív gyűrűktől: egy

R kommutatív gyűrű pontosan akkor véges test, ha az összes R − R függvénynek létezik polinom reprezentációja. A Lagrange interpolációs formula segítségével explicite is megadható egy adott f : GF (q) − GF (q) függvény r(x) (deg r < q) egyértelmű reprezentáns polinomja. Tekintsük ugyanis a következő segédpolinomot: ( 1 − (x − α)q−1 = 1 x=α 0 x= 6 α Ennek segítségével r(x) = X f (α)(1 − (x − α)q−1 ). α∈GF (q) 17 http://www.doksihu 3. Permutáció-polinomok Ebben a fejezetben azok a polinomok lesznek érdekesek számunkra, amelyek GF (q) elemeit permutálják. 3.1 Definíció (Permutáció-polinom) A GF (q) permutációit reprezentáló polinomokat permutáció-polinomoknak nevezzük. Általánosabban egy f (x) ∈ GF [q N , x] polinomot akkor nevezünk permutáció-polinomnak, ha a belőle behelyettesítéssel nyerhető függvény bijektív. Habár a permutáció-polinomok témaköre szakirodalomban gazdag, teljes

általánosságban nem sokat tudni róluk. Az alábbiakban három speciális osztályukat tárgyaljuk: permutáció-monomok, q-polinomok, Dickson-polinomok. Permutáció-polinomokal foglalkozik Lidl-Niederreiter [9] 7 fejezete, ill. a témakör történeti áttekintése megtalálható [11]-ben A szakirodalomban még sok más speciális permutáció-polinomot is vizsgálnak, lásd [1] Az alábbiakban vizsgált polinomosztályok kitüntetett szerepe Schur 1923-as sejtésével indokolható, melyet M. Fried bizonyított be 1970-ben: 3.2 Tétel Ha egy egész együtthatós polinom végtelen sok p prímre permutáció-polinomja GF (p)-nek (modulo p tekintve), akkor szükségképpen előáll lineáris polinomok, permutáció-monomok és Dickson-polinomok kompozíciójaként 3.1 Permutáció-monomok 3.3 Tétel Az xk monom pontosan akkor lesz GF (q) permutáció-polinomja, ha (k, q − 1) = 1 Bizonyítás. Ha α a GF (q) primitív eleme, akkor GF (q) minden β 6= 0 eleme egyértelműen áll

elő β = αb (0 ≤ b < q − 1) alakban, így az xk = β egyenletnek x = αt pontosan akkor megoldása, ha αtk = αb . Ennek megoldhatósága a következő lineáris kongruenciára vezethető vissza: kt ≡ b (mod q − 1) Ez közismerten akkor oldható meg t-ben, ha (k, q − 1)|b. Mivel ennek a kongruenciának minden b-re, így b = 1-re is megoldhatónak kell lennie, ez csak (k, q − 1) = 1 esetén lehetséges. Megjegyzés. Látható, hogy minden testautomorfizmus permutáció-polinom, de korántsem minden permutáció-polinom testautomorfizmus. 18 http://www.doksihu Az 1.17 definíciónak köszönhetően ez a tétel könnyen általánosítható: 3.4 Tétel Az xk monom pontosan akkor lesz GF (q N ) permutáció-polinomja, ha (k, q N − 1) = 1. Bizonyítás. Az xk monom pontosan akkor lesz GF (q N ) permutáció-polinomja, ha GF (q N ) minden GF (q d ), d|N véges résztestének permutációpolinomja Ez azt jelenti, hogy ha (di ) N osztósorozat, akkor az a

feltételünk, hogy minden i-re (k, q di − 1) = 1, azaz (k, q N − 1) = 1 legyen Másképp is megközelíthetjük a permutáció-monomokat. (km, N ) = 1 ⇔ (k, N ) = 1 és (m, N ) = 1, így az előző tételből azonnal adódik az alábbi állítás: 3.5 Állítás xkm permutáció-polinomja GF (q N )-nek ⇐⇒ xk és xm is permutáció-polinomja GF (q N )-nek Permutáció-monomok konstrukciójához ezért elég ismerni az x` alakúakat, ahol ` prím. A p = char GF (q) prímre xp a GF (p) feletti Frobeniusautomorfizmus, így xp permutáció-polinomja GF (q)-nak Az alábbi számelméleti tétel Zsigmondy 1892-es eredménye: 3.6 Tétel (Zsigmondy) Tetszőleges c, n > 1 pozitív egészekhez létezik ` prím, hogy o` (c) = n, kivéve, ha c = 2k − 1 és n = 2, ill. ha c = 2 és n = 6 3.61 Következmény Tetszőleges r prímekhez, q prímhatványhoz és m ≥ 2 pozitív egészhez létezik olyan ` prím, melyre o` (q) = rm . A 3.61 következmény [2]-ben a 414 lemma Segítségével

igazolhatjuk a következő tételt: 3.7 Tétel Tetszőleges N 6= Ω Steinitz-számra létezik végtelen sok ` prím, melyre x` a GF (q N ) permutáció-polinomja. Bizonyítás. Ha N = ∞ Q i=1 pki i 6= Ω, akkor létezik véges kitevő, legyen ez ki 6= ∞. Válasszunk egy pozitív egészekből álló szigorúan monoton növő (mj ) sorozatot, melyre ki < m1 < m2 < . teljesül A 361 következmény m alapján mindegyik mj -hez választható `j prím, hogy o`j (q) = pi j legyen. Ezekre a prímekre o`j (q) - N , tehát az x`j -k permutáció-monomjai GF (q N )nek. 19 http://www.doksihu 3.2 q-polinomok 3.8 Definíció Az L(x) = k P i αi xq , αk 6= 0 polinomokat q-polinomoknak i=0 nevezzük. L foka deg L = q k , avagy L q-foka, degq L = k Megjegyzés. A q-polinomokat szokás linearizált polinomnak is nevezni, ami a következő tulajdonságukra utal: ha L(x) ∈ GF [q n , x] q-polinom, akkor 1. L(α + β) = L(α) + L(β) minden α, β ∈ GF (q n ) esetén 2.

L(cα) = cL(α) minden c ∈ GF (q), α ∈ GF (q n ) esetén A továbbiakban GF (q n ) ill. GF (q N ) feletti q-polinomokkal foglalkozunk Látható, hogy L(x) az említett testek GF (q)-automorfizmusainak lineáris kombinációja, ezért L(x) ∈ GF [q n , x] tekinthető a GF (q n ), mint ndimenziós GF (q)-vektortér lineáris transzformációjának Mivel GF (q) minn den α elemére αq = α, feltehető, hogy degq L ≤ n−1, egyébként L-t ilyenné alakíthatjuk. Ha testeink végesek, más lineáris transzformáció nincs is: 3.9 Tétel A GF (q n ) mint n-dimenziós GF (q)-vektortér minden lineáris transzformációja egyértelműen reprezentálható egy L(x) = n−1 P i αi xq ∈ i=0 GF [q n , x] q-polinommal, melynek q-foka legfeljebb (n − 1) . q j−1 L(x) pontosan akkor lesz GF (q n ) permutáció-polinomja, ha az AL = (αj−i ) mátrix determinánsa nemnulla (a j − i alsó indexeket modn kell érteni): α0 α1q αn−1 α0q det AL = . . . . α1 α2q n−1 q .

αn−1 q n−1 . αn−2 . . . q n−1 . α0 6= 0 Bizonyítás. Legyenek L1 (x), L2 (x) olyan q-polinomok, melyek q-foka legn feljebb n − 1. Ha L1 (α) = L2 (α) a GF (q n ) minden α elemére, akkor xq − x|L1 (x) − L2 (x), ahonnan degq (L1 − L2 ) < n miatt L1 ≡ L2 . Tehát különböző q-polinomok különböző lineáris transzformációkat reprezentálnak Mivel a lineáris transzformációk ill. az n-nél kisebb q-fokú q-polinomok száma egy2 aránt q n , a tétel első felét igazoltuk. A második állításhoz tekintsük minden % ∈ GF (q n )-ra azt a %̄ oszlopvektort, i−1 melynek i-edik eleme %q , 1 ≤ i ≤ n. Legyen µ = L(%) Ezt q i−1 -re emelve minden 1 ≤ i ≤ n esetén azt kapjuk, hogy µ̄ = AL %̄. Így, ha %1 , %2 , %qn a 20 http://www.doksihu GF (q n ) adott sorbarendezése és R az az n × q n -es mátrix, melynek j-edik oszlopa %̄j , akkor M = AL R, ahol M az az n × q n -es mátrix, melynek j-edik oszlopa µ̄j . R rangja n,

különben valamely nemnulla λ = [λ0 , λ1 λn−1 ] n−1 + · · · + λ1 xq + λ0 x nem azosorvektorra λR = 0 lenne, vagyis a λn−1 xq nosan nulla q-polinom az azonosan nulla transzformációt reprezentálná, ami ellentmondás lenne a tétel első része miatt. Mivel a szorzatmátrix rangja legfeljebb akkora, mint a tényezők rangja, pontosan akkor lesz rkM = n, ha AL nemszinguláris. Másrészt, ha AL nemszinguláris, akkor invertálható, így R = A−1 L M, ahol A−1 L első sorát [β0 , β1 , βn−1 ]-gyel jelölve az L2 (x) = n−1 P βi x qi polinom az L(x) inverze, így L(x) tényleg permutáció- i=0 polinom. Amint az automorfizmuscsoportról szóló 1.3 fejezetben is láthattuk, egy GF (q N ) feletti q-polinom a GF (q N ) GF (q)-automorfizmusainak GF (q) feletti lineáris kombinációja, így tekinthető a GF (q N ), mint GF (q)-vektortér lineáris transzformációjának. A 39 tétel alapján különböző q-polinomok már egy megfelelő véges

résztesten is különböző transzformációt reprezentálnak, de mint látni fogjuk, GF (q N ) nem minden lineáris transzformációja reprezentálható q-polinomokkal. 3.10 Definíció Tekintsük a következő GF (q N ) feletti polinomokat: l(x) = k X αk xk és L(x) = i=0 k X αk x q k i=0 Ezeket egymás q-asszociáltjainak nevezzük, pontosabban L(x) az l(x) linearizált q-asszociáltja, l(x) pedig az L(x) hagyományos q-asszociáltja. A GF (q N ) feletti q-polinomok halmaza zárt az összeadásra, viszont nem zárt a szorzásra. Szerencsére azonban q-polinomok kompozíciója q-polinom, így definiálhatunk egy másik szorzást, amit "kompozíció" helyett "szimbolikus szorzás"-nak nevezünk. 3.11 Definíció A szimbolikus szorzás a q-polinomok halmazán értelmezett ⊗ bináris reláció, ami az L1 (x), L2 (x) q-polinomokhoz a kompozíciójukat rendeli: L1 (x) ⊗ L2 (x) = L1 (L2 (x)) Könnyen ellenőrizhető, hogy a GF (q N ) feletti q-polinomok

halmaza az összeadással, szimbolikus szorzással ill. GF (q)-beli elemmel való szorzással algebrát alkot. Ez az algebra általában nem kommutatív, de ha csak a GF (q) feletti q-polinomokat tekintjük, akkor igen. Igaz ugyanis a következő tétel: 21 http://www.doksihu 3.12 Tétel A q-polinomok és hagyományos q-asszociáltjaik közti L(x) ↔ l(x) megfeletetés izomorfizmus a q-polinomok GF (q)-algebrája és GF [q, x] között. Ezt a tételt nem bizonyítjuk, Lidl-Niederreiter [9] 3.59 lemmájának következménye P k Most megvizsgáljuk, mikor lesz egy L(x) = ki=0 αk xq ∈ GF [q N , x] polinom permutáció-polinomja GF (q N )-nek. Feltehető, hogy degq L < N Ha N nem véges, akkor ez eleve fennáll, egyébként visszakapjuk a már tárgyalt N esetet, amikor is L(x)-et modulo xq − x vehetjük. Ha N nem véges, legyen (di ) N olyan osztósorozat, melyre L(x) GF (q) feletti együtthatóteste GF (q d1 ). Mivel L(x) pontosan akkor permutáció-polinomja GF (q N )-nek,

ha GF (q di )-nek is minden i-re, ezért a 3.9 tételből azonnal adódik az alábbi tétel: k 3.13 Tétel Legyen az L(x) = ki=0 αk xq ∈ GF [q N , x] q-foka k < N , a (di ) N osztósorozat olyan, hogy az L(x) q-polinom GF (q) feletti együtthatóq j−1 teste GF (q d1 ). Most is tekinthetjük a AL = (αj−i ), ezúttal végtelen mátrixot, ahol az alsó indexeket mod(k + 1) kell érteni. L(x) pontosan akkor lesz GF (q n ) permutáció-polinomja, ha minden di > kra az AL mátrix di × di -s sarokdeterminánsai nemnullák. P Cirkuláns mátrixok és q-polinomok A 3.13 tétel, bár kétségkívül igaz, sajnos nem túl informatív, tekintettel az egyre nagyobb determinánsok meghatározásának nehézségeire. Abban az esetben viszont, ha a 39 tételben szereplő L(x) q-polinom GF (q) feletti, az αi együtthatókra teljesül αiq = αi , így az L(x)-hez asszociált mátrix (A)L = (αj−i ), az indexeket modulo n értve. Az ilyen típusú mátrixot cirkulánsnak nevezzük,

jelölése a továbbiakban C = C(α0 , α1 , αn−1 ) = (αj−i ) Egy cirkuláns mátrix determinánsa könnyebben meghatározható: 3.14 Lemma Tekintsük a C(α0 , α1 , αn−1 ) = (αj−i ) cirkuláns mátrixot, valamint az f (x) = Ekkor det C = n Q n−1 P αi xn−i GF (q) feletti polinomot. i=1 f (ωi ), ahol ωi -k n-edik egységgyökök xn − 1 GF (q) feletti i=1 felbontási testében. Bizonyítás. Legyen az xn − 1 polinom kísérő mátrixa R, ami a következő n × n-es mátrix: " # 0 1 R= In−1 0 22 http://www.doksihu Itt In−1 az (n − 1) × (n − 1)-es egységmátrix. Ennek k-adik hatványa k = 1, 2, . n-re " # 0 I k Rk = In−k 0 nevezetesen Rn = In . Így egy cirkuláns mátrix kifejezhető R polinomjaként: C(α0 , α1 , . αn−1 ) = n−1 X αi Rn−i , i=1 tehát C = f (R). Mivel R karakterisztikus polinomja xn − 1, R sajátértékei az ωi n-edik egységgyökök, melyek elemei xn − 1 GF (q) feletti felbontási

testének. Így C = f (R) sajátértékei f (ωi )-k, determinánsa pedig ezek szorzata Így bebizonyíthatjuk az alábbi Ore-tól származó tételt: 3.15 Tétel (Ore) Az L(x) = n−1 P i αi xq ∈ GF [q, x] q-polinom pontosan i=0 akkor lesz GF (q n ) permutáció-polinomja, ha L(x) hagyományos q-asszociáltjának, l(x)-nek egyik n-edik egységgyök sem gyöke. Bizonyítás. A 39 tétel alapján L(x) pontosan akkor lesz permutációpolinomja GF (q n )-nek, ha a C(α0 , α1 , αn−1 ) cirkuláns mátrix determinánsa nemnulla A 314 lemma alapján ez éppen akkor teljesül, ha az f (x) = n P αi xn−i polinomnak egyik n-edik egységgyök sem gyöke. Mivel az f (x) i=0 polinom f ∗ (x) = xn f (1/x) reciprokának gyökei f gyökeinek reciprokai, az iménti feltétel ekvivalens azzal, hogy f ∗ -nak egyik n-edik egységgyök sem n P gyöke. A befejezéshez vegyük észre, hogy f (x)∗ = αi xi = l(x), az L(x) i=0 hagyományos q-asszociáltja. Megjegyzés. Az l(x)

hagyományos q-asszociáltnak pontosan akkor gyöke egy n-edik egységgyök, ha l(x) és xn − 1 nem relatív prímek, azaz l(x) egyik p(x) irreducibilis faktora sem osztja xn − 1-et. A p(x) polinom periódusát e-vel jelölve p(x)|xn − 1 ⇐⇒ e|n. Ez a tétel ugyan gyengébb, mint a 3.9 tétel, cserébe viszont GF (q N ) felett is könnyen ellenőrizehtő feltételt nyújt L(x) permutáció-polinom voltára: 3.16 Tétel Legyen L(x) egy GF (q) feletti q-polinom Tegyük fel, hogy L(x) hagyományos q-asszociáltjának GF (q) feletti felbontása l(x) = p1 (x)t1 p2 (x)t2 . ps (x)ts , 23 http://www.doksihu ahol a pi (x) irreducibilis faktor periódusa ei . Egy N Steinitz-számra L(x) pontosan akkor lesz GF (q N ) permutáció-polinomja, ha 1 ≤ i ≤ s esetén ei - N . Bizonyítás. Válasszunk egy (di ) N osztósorozatot L(x) pontosan akkor lesz GF (q N ) permutáció-polinomja, ha minden GF (q di ) résztestének is permutáció-polinomja. Mivel e - N ⇔ ∀i e - di , a 315

tétel ill a hozzá fűzött megjegyzés alapján készen vagyunk. 3.3 Dickson-polinomok 3.17 Állítás R egységelemes kommutatív gyűrűben tetszőleges x, y ∈ R és k pozitív egész esetén bk/2c k k x +y = ! k−j k (−xy)j (x + y)k−2j k−j j X j=0 (3.31) Bizonyítás. A Waring-formula alapján az xk + y k szimmetrikus polinom a következőképpen fejezhető ki x, y elemi szimmetrikus polinomjai, x + y ill. xy segítségével: xk + y k = X (−1)i i+2j=k (i + j − 1)! (x + y)i (xy)j i!j! i = k − 2j helyettesítéssel épp a kívánt alakot kapjuk. 3.18 Definíció Rögzített a ∈ R esetén az (elsőfajú) gk (x, a) Dicksonpolinomokat a követkeőképp definiáljuk: bk/2c gk (x, a) = X j=0 ! k k−j (−a)j xk−2j k−j j (3.32) A Dickson-polinomok szoros kapcsolatban állnak a Tk (cos θ) = cos kθ Csebisev-polinomokal, ugyanis ha R = C , akkor (3.31)-ben x = eiθ , y = e−iθ helyettesítéssel 2 cos kθ = gk (2 cos θ, 1) adódik, ahonnan (3.32)

felhasználásával gk (2x, 1) = 2Tk (x) (3.33) Ez az azonosság lehetővé teszi, hogy a Csebisev-polinomokat tetszőleges páratlan karakterisztikájú test felett értelmezzük. (3.31)-ben y = a/x helyettesítéssel azonnal adódik az alábbi állítás: 24 http://www.doksihu 3.19 Állítás  gk ak a k x + ,a = x + k x x  Általában feltehetjük, hogy a 6= 0, mivel a gk (x, 0) = xk esetet már tisztáztuk. A Dickson-polinomok permutációs tulajdonságainak további vizsgálatához szükségünk lesz az alábbi lemmára: 3.20 Lemma Legyen a ∈ GF (q) tetszőleges nemnulla elem Ekkor GF (q) összes λ eleme előáll λ = β + a/β alakban, ahol β ∈ GF (q 2 ) nemnulla elem. Bizonyítás. Tekintsük az x2 −λx+a ∈ GF [q, x] polinomot Ennek GF (q) feletti felbontási testében, GF (q 2 )-ben létezik β gyöke, ami értelemszerűen nemnulla, és teljesül rá λ = β + a/β. 3.21 Tétel Legyen a 6= 0 GF (q)-beli elem Ekkor a gk (x, a) Dicksonpolinom pontosan akkor

permutáció-polinomja GF (q)-nak, ha (k, q 2 −1) = 1 Bizonyítás. Először tegyük fel, hogy (k, q 2 − 1) = 1 Mivel GF (q) véges, elég belátni, hogy gk (x, a) injektív. Ha gk (λ1 , a) = gk (λ2 , a), akkor a 320 lemma alapján létezik 0 6= β1 , β2 ∈ GF (q 2 ), hogy λ1 = β1 + a/β1 ill. λ2 = β2 + a/β2 , a 3.19 állítást felhasználva azt kapjuk, hogy β1k a ak ak a + k = gk β1 + , a = gk β2 + , a = β2k + k , β1 β1 β2 β2     átrendezve (β1k − β2k )(β2k β2k − ak ) = 0. (k, q 2 − 1) = 1 ⇒ (k, q − 1) = 1, ahonnan a permutáció-monomokra vonatkozó 33 tétel alapján β1 = β2 , vagy β1 β2 = a. Mindkét esetben λ1 = β1 + a/β1 = β2 + a/β2 = λ2 Most tegyük fel, hogy (k, q 2 − 1) = d > 1, belátjuk, hogy ekkor gk (x, a) nem injektív. Ha q páratlan és k páros, akkor 2|d, és valóban, páros k-ra gk (x, a) olyannyira nem injektív, hogy páros: gk (λ, a) = gk (−λ, a) minden λ ∈ GF (q)-ra. Egyébként feltehető,

hogy d-nek létezik páratlan ` prímosztója `|q 2 − 1 alapján két eset lehetséges: Ha `|q − 1, akkor az x` − 1 egyenletnek GF (q) fölött ` ≥ 3 megoldása van, így létezik β ∈ GF (q), hogy β 6= 1, β 6= a és β ` = 1. Ekkor `|k miatt β k = 1 is igaz, tehát  gk ak a k β + , a = β + k = 1 + a = gk 1 + a, a β β    β + βa = 1 + a ⇐⇒ (β − 1)(β − a) = 0, ami lehetetlen β választása miatt. Ha `|q + 1, akkor az xq+1 = a megoldható GF (q 2 )-ben. Legyen ugyanis θ a 25 http://www.doksihu GF (q 2 ) primitív eleme. Ekkor egyrészt θq+1 ∈ GF (q), mert gyöke (xq − x)nek, másrészt 1 ≤ i ≤ q − 1-re (θq+1 )i -k mind különböző elemei GF (q)-nak Így valamely i-re (θq+1 )i = a, erre az i-re λ = θi megoldás. `|q +1 ⇒ `|q 2 −1, így az x` − 1 egyenletnek GF (q 2 ) fölött ` ≥ 3 megoldása van, ezért van olyan γ ∈ GF (q 2 ) megoldás, ami 1-től és a/λ2 -től különböző. γ k = 1 és γ q+1 = 1 is teljesül,

így ak a ak a ,a gk λ + , a = λk + k = (γλ)k + = gk γλ + k λ λ (γλ) γλ     a = λ + (γλ)q ∈ GF (q), Az argumentumokra λ + λa = λ + λq ∈ GF (q), γλ + γλ a továbbá λ + λa = γλ + γλ ⇐⇒ (γ − a/λ)(γ − 1) = 0, ami nem teljesül γ választása miatt. Ha gk (x, a) Dickson-polinomot most GF (q N ) feletti polinomnak tekintjük, feltéve, hogy a ∈ GF (q N ) nemnula elem, akkor az alábbi általánosítás adódik: 3.22 Tétel A gk (x, a) Dickson-polinom pontosan akkor permutáció-polinomja GF (q N )-nek, ha (k, q 2 N ) = 1 Bizonyítás. Legyen a gk (x, a) együtthatóteste GF (q) felett GF (q t ), valamint (di ) N osztósorozat Ekkor a foka GF (q) felett t gk (x, a) éppen akkor permutáció-polinomja GF (q N )-nek, ha ∀di : t|di esetén permutációpolinomja GF (q di )-nek. A 321 tétel alapján ez azzal ekvivalens, hogy ∀di : t|di -re (k, q 2d − 1) = 1, ami azt jelenti, hogy (k, q 2N − 1) = 1, tekintve, hogy elég nagy i-re

t|di teljesül. Egyszerű következményként adódik az alábbi állítás: 3.23 Állítás A gkm (x, a) Dickson-polinom pontosan akkor permutációpolinomja GF (q N )-nek, ha gk (x, a) és gm (x, a) is az A 3.22 tétel alapján evidens, hogy ha p = char GF (q) esetén gp (x, a) permutáció-polinomja GF (q N )-nek. Jogosan merül fel a kérdés, mely ` 6= p prímekre lesz g` (x, a) permutáció-polinomja GF (q N )-nek. Szerencsére tételünk segítségével ez is könnyen megválaszolható Tetszőleges ` 6= p prímre (`, q N − 1) = 1 ⇐⇒ o` (q) - 2N . Ha egy ` prímre ez teljesül, akkor a 323 állítás értelmében minden hatványára is, így a 3.22 tételt a következőképpen is átfogalmazhatjuk: 26 http://www.doksihu 3.24 Tétel Legyenek p, ` prímek, q (véges) p-hatvány, N Steinitz-szám, a ∈ GF (q N ) nemnulla elem. Ekkor a g` (x, a) Dickson-polinom pontosan akkor permutáció-polinomja GF (q N )-nek, ha ` = p, vagy ha ` 6= p és o` (q) 2N . 3.241

Következmény Legyen N tetszőleges Ω-tól különböző Steinitzszám Ekkor tetszőleges a ∈ GF (q N ) nemnulla elemre létezik végtelen sok olyan ` prím, amelyre g` (x, a) permutáció-polinomja GF (q N )-nek. Bizonyítás. Lényegében ugyanaz, mint a 37 tételé Mivel N 6= Ω, így létezik olyan pi prím, melynek ki kitevője N -ben véges. A 361 állítás alapján bármely m pozitív egészre végtelen sok olyan ` prím van, melyre o` (p) = pm i . Ha m > ki , akkor ` megfelelő prím. Mivel különböző m-ekhez különböző ` prímeket választunk, a tételt igazoltuk. 27 http://www.doksihu 4. Iterált prezentációk Véges testre a legegyszerűbb példa a GF (p) prímtest, amit legkézenfekvőbb a modulo p maradékoknak tekinteni a szokásos műveletekkel. Némivel árnyaltabb a helyzet GF (q), q p-hatvány esetén. Ennek szokásos reprezentációjához szükségünk van egy n-edfokú f (x) ∈ GF [p, x] irreducibilis polinomra. Ekkor a (211) izomorfizmus

alapján GF (q) = {a0 + a1 α + · · · + at−1 αn−1 | ai ∈ GF (p)} egy GF (p) feletti n-dimenziós vektortérnek tekinthető úgy, hogy az összeadást koordinátánként végezzük, a szorzást pedig modulo f (x), azaz α-t az f (x) gyökének tekintjük. Ehhez persze szükség van egy konkrét f (x) ∈ GF [p, x] n-edfokú irreducibilis polinomra, melynek létezését ugyan garantálja a 2.1 tétel, de adott n-re nem mindig triviális találni Ezt a szemlélet és formalizmust terjesztjük ki az általános GF (q N ) algebrai bővítésekre. Mindez nagyban megkönnyíti a testekben való számolást 4.1 Definíció Tegyük fel, hogy GF (q)-ban ismertek az összeadás és szorzás algoritmusai, mondjuk a fenti módon, egy prímtest feletti konkrét irreducibilis polinom által Ekkor N Steinitz-egészre a GF (q N ) iterált prezentációja GF (q) felett az alábbi rendezett párok (di , fi (x)) sorozata, ahol (di ) N adott osztósorozat, (fi (x)) pedig adott polinomsorozat az

alábbi tulajdonságokkal: i ≥ 0-ra fi+1 (x) ∈ GF [q di , x] irreducibilis és deg fi+1 = di+1 /di . Megjegyzés. Ha N véges, akkor az osztósorozat és a polinomsorozat is véges, egyébként a fokszámra tett megkötés miatt mindkettőnek végtelennek kell lennie. 4.11 Példa Legyen GF (2) = {0, 1} adott, N = 4 GF (16) lehetséges iterált prezentációi például az alábbiak: • d0 = 1, d1 = 4, f1 (x) = x4 + x + 1 • d0 = 1, d1 = 2, d2 = 4, f1 (x) = x2 + x + 1, f2 (x) = x2 + x + α1 , ahol α1 az f1 (x) gyöke. Explicit bázis. Adott (di , pi (x)) iterált prezentációra tekintsük most az (αi ) sorozatot, ahol αi a pi (x) polinom gyöke minden i-re. Ekkor a GF (q N ) bázisát alkotják GF (q) felett az αi elemekből képezhető véges szorzatok, 28 http://www.doksihu vagyis a ∞ Q i=1 αiki alakú kifejezések, ahol 0 ≤ ki < deg pi , és véges sok ki- vétellel ki = 0. Ekkor GF (q N ) elemei a báziselemek véges lineáris kombinációi, így αi -k

polinomjainak tekintehtők Ennek megfelelően az alapműveletek GF (q N )-ben a szokásos polinomösszeadás és polinomszorzás, az αit , t > deg pi hatványok a pi (αi )=0 összefüggés szerint redukálhatók. A báziselemeket a következőképpen rendezhetjük: legyen ∞ Q i=1 αiki < ∞ Q i=1 αili , ha kt < lt , ahol t a legnagyobb index, amelyre kt 6= lt . Ha még GF (q) egy a0 = 0 < a1 < · · · < aq−1 rendezését is adottnak tekintjük, akkor az αi 7 q di−1 , ai 7 i hozzárendelésekkel GF (q)-t megfeleltettük a nemnegatív egészeknek úgy, hogy GF (q N ) minden eleméhez egy nemnegatív egész qalapú számrendszerbeli alakját rendeltük. A GF (q N )-beli műveletek N-en más összeadást és szorzást indukálnak, lásd a későbbi 4.51 példában ill bővebben Conway [4] könyvében. 4.2 Definíció GF (q N ) explicit bázisa GF (q) felett egy {λ1 , λ2 , } rendezett bázis a megfelelő λi λj = a1 λ1 + a2 λ2 + · · · +

ak(i,j) λk(i,j) redukciós egyenletekkel minden i, j-re, ahol az együtthatók GF (q)-beliek, k(i, j) pedig i-től és j-től függő pozitív egész. ∞ 4.1 GF (pp ) iterált prezentációi A továbbiakban egy speciális esetet tárgyalunk. 4.3 Lemma Legyen b ∈ GF (q), q p-hatvány Az xp −x−b polinom pontosan akkor irreducibilis GF (q) felett, ha nincs gyöke GF (q)-ban. Bizonyítás. Ha γ gyöke xp −x−b-nek GF (q) valamely bővítésében, akkor γ + a is gyöke minden a ∈ GF (p)-re. A polinomok fokát figyelembe véve így xp − x − b = Y (x − γ − a). a∈GF (p) Indirekte tegyük fel, hogy létezik GF [q, x]-ben g(x)|xp −x−b, 1 < deg g < p faktor. Ekkor deg g = r esetén g(x) = r X i=0 bi x i = r Y (x − γ − aj ), j=1 ahol bi -k GF (q)-beliek, aj -k pedig GF (p)-beliek. Így xr−1 együtthatója g(x)ben br−1 = rγ +a1 +· · ·+ar Itt r ∈ GF (p), tekintve, hogy 1 ∈ GF (p) r-szeri 29 http://www.doksihu összeadásával

kaptuk. A g(x) fokára tett megkötések miatt r 6= 0, így lehet vele osztani: γ = r−1 (br−1 − a1 − · · · − ar ) ∈ GF (q), tehát, ha xp − x − b nem irreducibilis, akkor van gyöke GF (q)-ban, sőt lineáris faktorokra bomlik benne. 4.4 Lemma Legyen q továbbra is a p prím hatványa, b ∈ GF (q) olyan, hogy xp − x − b irreducibilis GF (q) felett. xp − x − b egyik gyökét α-val jelölve α ∈ GF (q p ). Ekkor az xp − x − bαp−1 polinom irreducibilis GF (q p ) felett Bizonyítás. Ekkor α választása miatt GF (q p ) = {a0 + a1 α + · · · + ap−1 αp−1 | ai ∈ GF (q)}. (xp − x − bαp−1 )-be behelyettesítve x = a0 + a1 α + · · · + ap−1 αp−1 -et azt kapjuk, hogy αp−1 együtthatója cp − c − b, ahol c = ap−1 . Vegyük észre, hogy cp − c − b nem lehet 0, mert xp − x − b irreducibilis GF (q) felett. Ezért GF (q p ) egyik elemére sem teljesül xp − x − bαp−1 , így a 4.3 lemma alapján xp − x −

bαp−1 irreducibilis GF (q p ) felett. 4.5 Tétel (Conway) Legyen GF (p) adott, ahol p tetszőleges prím, (pi ) pedig p∞ -hez tartó osztósorozat. A pi (x) polinomsorozatot rekurzívan definiáljuk: 1. p1 (x) = xp − x − 1 2. pi+1 (x) = xp − x − πip−1 i≥1 ∞ Itt πi = α1 α2 . αi , ahol αj a pj (x) gyöke Ekkor (pi , pi (x)) a GF (pp ) iterált prezentációját adja GF (p) felett, sőt minden k pozitív egészre (pi , pi (x))ki=1 k a GF (pp ) iterált prezentációja GF (p) felett. Bizonyítás. Világos, hogy deg pk+1 (x) = pk+1 /pk = p, és definíciójuk miatt pk+1 ∈ GF [pk , x] minden i-re. Azt kell még belátni, hogy minden k k-ra pk+1 (x) irreducibilis GF (pp ) felett. Teljes indukció k szerint Minden a ∈ GF (p)-re p1 (a) = ap − a − 1 = −1, így a 43 lemma szerint p1 (x) = xp − x − 1 irreducibilis GF (p) felett. Az indukciós lépés pedig maga a 4.4 lemma ∞ 4.51 Példa Legyen p = 2 Ekkor GF (22 ) következő itrált prezentációját

kapjuk: di = 2i , p1 (x) = x2 + x + 1, pn+1 (x) = x2 + x + α1 α2 . αn , ahol αi ∞ a pi (x) gyöke. GF (22 ) explicit bázisa GF (2) felett: 1, α1 , α2 , α1 α2 , α3 , α1 α3 , α2 α3 , α1 α2 α3 , . | {z } GF (22 ) | | {z GF (24 ) } {z GF (28 ) 30 } http://www.doksihu A redukciós egyenletek pedig α12 = α1 + 1 αn2 = αn + α1 α2 . αn−1 , n > 1 k Ebben a rendezésben az első 2k báziselem GF (22 ) bázisát adja GF (2) felett. A szorzás ill összeadás szemléltetésére tekintsük pl. a β = α1 + α1 α2 , és a γ = α1 + α2 α3 elemeket: β + γ = (α1 + α1 α2 ) + (α1 + α2 α3 ) = α1 α2 + α2 α3 βγ = (α1 + α1 α2 )(α1 + α2 α3 ) = α12 + α12 α2 + α1 α2 α3 + α1 α22 α3 = 1 + α1 + α2 + α1 α2 + α3 + α1 α2 α3 + α12 + α2 α3 = α2 + α1 α2 + α3 + α1 α2 α3 + α2 α3 . i−1 Az αi = 22 megfeleltetéssel β = 2 + 22 = 6, γ = 2 + 22 · 24 = 66. Így azt ∞ kaptuk, hogy a GF (22 )-beli műveletek által N-en

indukált műveletekkel pl. 10 + 66 = 2 · 22 + 22 · 24 = 72, 10.66 = 22 + 2 · 22 + 24 + 2 · 22 · 24 + 22 24 = 220 ∞ A GF (22 ) speciális esetre Wiedemann [13] cikkében egy másik iterált prezentációt közöl: 4.6 Tétel (Wiedemann) Tekintsük a (2i ) 2∞ , osztósorozatot és az alábbi polinomsorozatot: 1. p1 (x) = x2 + x + 1 2. pi+1 (x) = x2 + αi x + 1, i ≥ 0, ∞ ahol αi a pi (x) gyöke. Ekkor (2i , pi (x)) a GF (22 ) iterált prezentációja GF (2) felett. Bizonyítás. Definiáljunk egy másik polinomsorozatot is: legyen q1 (x) = p1 (x), továbbá i ≥ 0-ra qi+1 (x) = x2 + αi−1 x + 1. Teljes indukcióval bei−1 bizonyítjuk, hogy i ≥ 1-re pi (x) és qi (x) is GF (22 ) feletti irreducibilis polinom. Könnyen látszik, hogy p1 (x) irreducibilis GF (2) felett, mert nincs gyöke GF (2)-ben. Tegyük fel, hogy az állítást 1 ≤ i ≤ m esetére már igazoltuk Tekintsük a pm+1 (x) = x2 + αm x + 1 polinomot Mim−1 vel αm a pm (x) ∈ GF [22 , x]

másodfokú irreducibilis polinom gyöke, így m m−1 m GF (22 ) = GF [22 , αm ]. Ezért pm+1 (x) és qm+1 (x) is GF (22 ) feletti polinomok Mivel másodfokúak, irreducibilitásukhoz elég, hogy nincs gyökük 31 http://www.doksihu m GF (22 )-ben. Indirekt módon tegyük fel, hogy a + bαm a pm+1 (x) gyöke, m−1 ahol a, b ∈ GF (22 ). Ezek alapján 2 + aαm + (a2 + 1) 0 = pm+1 (a + bαm ) = (b2 + b)αm 0 = (b2 + b + a2 + 1) + [(b2 + b)αm−1 + a]αm . m m−1 Mivel {1, αm } bázisa GF (22 )-nek GF (22 ) felett, szükségképpen mindkét együttható nulla. b2 + b + a2 + 1 = 0 ⇔ b2 + b = a2 + 1, ezt a másik együtthatóba behelyettesítve azt kapjuk, hogy (a2 + 1)αm−1 + a = 0, vagyis −1 qm (a) = a2 + αm−1 a + 1 = 0, ami ellentmondás qm (x) irreducibilitása miatt. Analóg módon igazolható, hogy qm+1 (x) irreducibilis. Felmerül a kérdés, mi lehet αi GF (2) feletti minimálpolinomja. A választ a 2.2 fejezetben tárgyalt φ leképezés adja: 4.7 Tétel Az

αi -k GF (2) feletti minimálpoliomját mi (x)-szel jelölve 1. m1 (x) = x2 + x + 1 i 2. mi+1 (x) = φ(mi (x)) = x2 mi (x + x−1 ), i≥1 i−1 Továbbá αi multiplikatív rendje osztója Fi -nek, ahol Fi = 22 Fermat-szám. + 1, az i-edik Bizonyítás. Világos, hogy α1 minimálpolinomja m1 (x) Mivel a pi (x) polinom gyökei és együtthatói közti összefüggésekből αi−1 = αi + αi−1 , teljes indukcióval azonnal adódik, hogy αi az mi (x) gyöke. Az, hogy mi (x) minimálpolinom, onnan látszik, hogy deg mi (x) = 2i , a lehető legkisebb Az i utolsó állításhoz vegyük észre, hogy az x2 + αi x + 1 ∈ GF [22 , x] irreducibilis i i −1 polinomnak αi+1 és αi+1 egyaránt gyöke. A GF (22 ) test σi (x) = x2 nemtrii−1 −1 viális GF (22 )-automorfizmusa αi+1 -t és αi+1 -t szükségszerűen egymásba 2i Fi −1 2 képezi, így αi+1 = αi+1 , vagyis αi+1 = 1. Megjegyzés. Wiedmann az első kilenc i-re azt tapasztalta, o(αi ) = Fi Az, hogy ez minden

i-re igaz-e, máig nyitott kérdés. 32 http://www.doksihu Hivatkozások [1] Amir Akbary, Qiang Wang, On Some Permutation Polynomials Over Finite Fields, Int. J Math Math Sci, (2005) 2631–2640 [2] Joel V. Brawley, George E Schnibben, Infinite Algebraic Extensions of Finite Fields, Contemporary mathematics, Vol. 95, Amer Math Soc., Providence, RI, 1989 [3] Stephen D. Cohen, The Explicit Constructions of Irreducible Polynomials Over Finite Fields, Designs, Codes and Cryptography, 2 (1992), 169–174. [4] J. H Conway, On numbers and games, Academic Press, New York, 1976. [5] Robert W. Fitzgerald, Joseph L Yucas, Factors of Dickson polynomials over finite fields, Finite Fields and Their Applications 11 (2005), 724–737. [6] Dirk Hachenberg, Explicit Iterative Constructions of Normal Bases and Completely Free Elements in Finite Fields, Finite Fields and Their Applications 2 (1996), 1–20. [7] Marie Henderson, Rex Matthews, Permutation properties of Chebyshev Polynomials of Second

Kind over a Finite Field, Finite Fields and Their Applications 1 (1994), 115–125. [8] Melsik K. Kyuregyan, Recursive constructions of N -polynomials over GF (2s ), Discrete Applied Mathematics, 156 (2008), 1554–1559. [9] Rudolf Lidl, Harald Niederreiter, Finite fields, 2nd ed., Cambridge University Press, Cambridge 1997. [10] Helmut Meyn, On the construction of irreducible self-reciprocal polynomials over finite fields, Appl. Alg in Eng Comm and Comp 1 (1990), 43–53. [11] Gary L. Mullen, Permutation Polynomials: A Matrix Analogue of Schur’s Conjecture and a Survey of Recent Results, Finite Fields and Their Applications 1 (1994), 242–258. 33 http://www.doksihu [12] E. Steinitz, Algebraiche Theorie der Körper, J reine angew Math 137 (1910), 167–309, Reprint: Algebraiche Theorie der Körper, New York, Chelsea Publ., 1950 [13] D. Wiedemann, An Iterated Quadratic Extension of GF(2), Fibonacci Quarterly, 26 (1988) 290–295. 34