Csoportok a matematika

E¨ otv¨ os Lor´ and Tudom´ anyegyetem Term´ eszettudom´ anyi Kar

Csoportok a matematika k¨ ul¨ onb¨ oz˝ o ter¨ uletein Szakdolgozat

Harkai Alexandra D´ ora Matematika B.Sc., Matematikai elemz˝o szakir´any T´emavezet˝o: K´ arolyi Gyula, egyetemi docens Algebra ´es Sz´amelm´elet Tansz´ek

Budapest 2010

Tartalomjegyz´ ek 1. Csoportelm´ eleti bevezet˝ o

4

2. A Pell-egyenletek ´ es az egys´ egcsoport 9 2.1. A Pell-egyenlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2. Megk¨ozel´ıt´es az algebrai sz´amelm´elet seg´ıts´eg´evel . . . . . . . . . . . 11 2.3. A Dirichlet-egys´egt´etel . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3. Csoportok ´ es Cayley-gr´ afok 3.1. A Lov´asz-sejt´es . . . . . . 3.2. Cayley-gr´afok . . . . . . . 3.3. Expander gr´afok . . . . . 3.4. Algebrai gr´afelm´elet . . . 3.5. Egy numerikus p´elda . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

16 16 17 21 23 24

4. Elliptikus g¨ orb´ ek 29 4.1. R´eszcsoportok s´ıkban ´es terekben . . . . . . . . . . . . . . . . . . . . 29 4.2. Elliptikus g¨orb´ek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.3. Az elliptikus g¨orb´ek csoporttulajdons´aga . . . . . . . . . . . . . . . . 33

1

Bevezet´ es A csoportelm´elet a matematika azon ´aga, amely megv´alaszolja azt a ” k´erd´est, hogy ‘Mi a szimmetria?’ ” – Nathan C. Carter Nem csak a matematik´aban, hanem a fizika, a k´emia, s˝ot a m˝ uv´eszetek k¨ ul¨onf´ele ter¨ uletein is tal´alkozhatunk csoportokkal. Megjelennek a relativit´aselm´eletben, krist´alyszerkezetek le´ır´asakor, a s´ık vagy a t´er csemp´ekkel” t¨ort´en˝o kirak´as´an´al, a ” Rubik-kocka mozgat´asai is kifejezhet˝ok a csoportok nyelv´en, s˝ot a zen´eben a kvintk¨or is egy ciklikus csoporttal ´ırhat´o le [6]. A csoportelm´elet seg´ıts´eg´evel felt´arhat´o egy halmaz m˝ uk¨od´ese, fel´ep´ıt´ese ´es meg´erthetj¨ uk a benn¨ uk rejl˝o rendszert, szab´alyoss´agokat. A csoportok tanulm´anyoz´asa alapvet˝o fontoss´ag´ u az absztrakt algebr´aban, ugyanis a k¨ ul¨onb¨oz˝o algebrai strukt´ ur´ak (gy˝ ur˝ uk, testek, vektorterek) tulajdonk´eppen maguk is mind alapvet˝oen csoportok, a tov´abbi m˝ uveleti saj´atoss´agok k¨ ul¨onb¨oztetik meg ˝oket, ezek jelentik azokat a plusz tulajdons´agokat, amelyek k¨ ul¨on ´erdekess´e ´es nem utols´o sorban hasznoss´a teszik ˝oket. M´ar az els˝o´eves algebr´aban ´es sz´amelm´eletben is tal´alkozunk olyan t´etelekkel, melyek csoport- ´es gy˝ ur˝ uelm´eleti h´att´errel rendelkeznek. Ilyenek az Euler-Fermatt´etel, a Lagrange-t´etel, valamint modulo p primit´ıv gy¨ok l´etez´ese, ami annak speci´alis esete, hogy minden v´eges test multiplikat´ıv csoportja ciklikus. A kriptogr´afi´aban alkalmazott diszkr´et logaritumus pedig u ´gy is megfogalmazhat´o, hogy a modulo p marad´ekoszt´alyok a szorz´asra n´ezve ciklikus csoportot alkotnak. Dolgozatomban kifejezetten maguknak a csoportoknak a hasznoss´ag´ara, sz´eles k¨or˝ u alkalmaz´asaira szeretn´ek r´avil´ag´ıtani n´eh´any konkr´et p´elda seg´ıts´eg´evel. Megold´asukon kereszt¨ ul m´elyebben bemutatom, hogyan jelennek meg a csoportok a matematika legk¨ ul¨onb¨oz˝obb ter¨ uletein ´es seg´ıtenek meg´erteni, ´atl´atni a probl´em´ak fel´ep´ıt´es´et, m˝ uk¨od´es´et. Az els˝o fejezetben bemutatom azokat a csoportelm´eleti fogalmakat, melyeket a k´es˝obbiek sor´an fel fogok haszn´alni, illetve melyeknek ismerete alapvet˝o fontoss´ag´ u 2

a tov´abbiak meg´ert´es´ehez. Az itt r´eszletezett t´etelek ´es defin´ıci´ok nagyr´eszt Szab´o ´ Endre, Pelik´an J´ozsef, Agoston Istv´an, P´alfy P´eter P´al, K´arolyi Gyula ´es Szab´o Csaba ´or´ain hangzottak el. A m´asodik fejezetben a nevezetes Pell-egyenletek megold´asain kereszt¨ ul ismertetem az ide´alok ´es az egys´egcsoport egy alkalmaz´as´at, a harmadik fejezet a Cayleygr´afok tulajdons´agait felhaszn´alva egy m´elyebb absztrakt algebrai t´etel k¨ovetkezm´enyeit mutatja be. A negyedik fejezetben egy, az elliptikus g¨orb´eken ´ertelmezett csoport tulajdons´agaival foglalkozom. A dolgozatban felhaszn´alt a´br´ak a Wikipedia szabadon felhaszn´alhat´o k´epei k¨oz¨ ul ´es a Wolfram MathWorld oldal´ar´ol sz´armaznak, az ´altalam rajzolt ´abr´akat pedig a KmPlot ny´ılt forr´ask´od´ u programmal k´esz´ıtettem.

3

1. fejezet Csoportelm´ eleti bevezet˝ o Sz´amos algebrai, illetve legink´abb speci´alisan csoportelm´eleti ismeretre fogok ´ep´ıteni a dolgozatban, ez´ert a bevezet˝o fejezetben o˝sszefoglalom azokat a fogalmakat, amiket a k´es˝obbiek sor´an felhaszn´alok. Ezek d¨ont˝o t¨obbs´egben szigor´ uan csoportelm´eleti t´etelek ´es defin´ıci´ok, melyek ugyan mind menynyis´eg¨ ukben, mind m´elys´eg¨ ukben csak kis r´esz´et k´epezik a csoportelm´eleti alapismereteknek [15], azonban a bemutatott probl´em´ak m´ar ´ıgy is megoldhat´oak lesznek. Mivel a p´eld´ak a matematika k¨ ul¨onb¨oz˝o ter¨ uleteir˝ol sz´armaznak, egy kev´es gy˝ ur˝ uelm´eleti, geometriai ismeretre is sz¨ uks´eg lesz. A legfontosabbak term´eszetesen maga a csoport a fogalma, valamint a hozz´a szorosan kapcsol´od´o defin´ıci´ok lesznek: 1. Defin´ıci´ o. [csoport] Csoportnak nevez¨ unk egy olyan nem¨ ures G halmazt, amelyen ´ertelmezve van egy bin´aris m˝ uvelet (·) a k¨ovetkez˝o tulajdons´agokkal: • b´armely k´et a, b ∈ G eset´en ab ∈ G (m˝ uveleti z´arts´ag) • minden a, b, c ∈ G elemekre (ab)c=a(bc) (a m˝ uvelet asszociat´ıv) • egy´ertelm˝ uen l´etezik egy kit¨ untetett e ∈ G elem, amelyre igaz, hogy ∀ a ∈ G elemre ea = a = ae (k´etoldali egys´egelem l´etez´ese) • ∀ a ∈ G elemhez egy´ertelm˝ uen l´etezik egy b = a−1 elem, amelyre igaz, hogy aa−1 = e = a−1 a, ahol e a csoport fent defini´alt egys´egeleme (k´etoldali inverz l´etez´ese) 2. Defin´ıci´ o. [rend] Egy G csoport |G| rendje a csoport elemeinek sz´ama, egy g ∈ G elem rendje pedig az a legkisebb n ∈ N, amelyre g n = e. 4

3. Defin´ıci´ o. [Abel-csoport] Egy G csoport Abel-csoport, ha kommutat´ıv, vagyis ∀ a, b ∈ G eset´en ab = ba. Egy csoportnak nevezetes r´eszhalmazai lehetnek, k¨ ul¨on fontosak azok, amelyek o¨r¨oklik” az eredeti csoport strukt´ ur´aj´at, esetleg k¨ovetkeztetni lehet bel˝ol¨ uk az eg´esz ” csoport szerkezet´ere. 4. Defin´ıci´ o. [komplexus] Komplexusnak nevezz¨ uk egy csoport r´eszhalmazait. A komplexusokon defini´alunk egy szorz´ast a k¨ovetkez˝ok´eppen: K −1 = {k −1 | k ∈ K}, valamint K1 K2 = {k1 k2 | k1 ∈ K1 , k2 ∈ K2 }. Komplexusokat elemmel is szorozhatunk, ez egyelm˝ u komplexussal val´o szorz´ast jelent: gK = {g}K = {gk | g ∈ G, k ∈ K}. (Hasonl´oan defini´alhat´o Kg is.) 5. Defin´ıci´ o. [r´eszcsoport] Egy G csoportnak r´eszcsoportja ∅ = 6 H ⊂ G, ha ugyanarra a csoportm˝ uveletre ´es az inverzk´epz´esre n´ezve is z´art, ezt H < G-vel jel¨olj¨ uk. 1. P´ elda. [r´eszcsoport] Az eg´esz sz´amok (Z, +) csoportj´aban r´eszcsoportot alkotnak a k nemnulla eg´esszel oszthat´o sz´amok. 6. Defin´ıci´ o. [gener´ator] Egy S ⊂ G r´eszhalmaz ´altal gener´alt hSi csoport az a legsz˝ ukebb r´eszcsoportja G-nek, amely tartalmazza S-t. Egy G csoport gener´atora az az S ⊂ G halmaz, melyre hSi = G, ahol hSi jel¨oli a gener´atorelemek ´es inverzeik kombin´aci´oib´ol el˝o´all´ıthat´o elemek halmaz´at. 7. Defin´ıci´ o. [v´egesen gener´alt Abel-csoport] Egy (G, +) Abel-csoport v´egesen gener´alt, ha l´etezik v´eges sz´am´ u g1 , . . . , gs ∈ G, melyekseg´ıts´eg´evel ∀g ∈ G elem egy´ertelm˝ uen fel´ırhat´o ∀g ∈ G : g = n1 g1 + . . . + ns gs alakban, ahol n1 , . . . , ns ∈ Z. Ekkor {g1 , . . . , gs } a G csoport egy gener´atorhalmaza. K¨onnyen l´athat´o, hogy minden v´eges Abel-csoport v´egesen gener´alt, de ford´ıtva nem igaz. 8. Defin´ıci´ o. [ciklikus csoport] Ciklikusnak nevezz¨ uk azokat a csoportokat, melyek egy elemmel gener´alhat´ok. 2. P´ elda. [ciklikus csoport] Az eg´esz sz´amok (Z, +) csoportja, valamint m eg´eszekre a (mod m) marad´ekoszt´alyok csoportjai. 5

9. Defin´ıci´ o. [szabad csoport] Szabad csoportnak nevez¨ unk egy G csoportot, ha l´etezik olyan S gener´atora, hogy a gener´atorelemek ´es inverzeik szozatak´ent G minden eleme pontosan egyf´elek´eppen ´ırhat´o fel. 10. Defin´ıci´ o. [mell´ekoszt´aly] Egy H < G r´eszcsoport mell´ekoszt´alyai G-ben azok a komplexusok, melyeket a G-beli g elemekkel val´o szorz´assal kapunk: gH ´es Hg a H r´eszcsoport g szerinti bal-, illetve jobboldali mell´ekoszt´alya. 11. Defin´ıci´ o. [norm´aloszt´o] A G csoport egy N r´eszcsoportja norm´aloszt´o (N / G), ha ∀g ∈ G-re teljes¨ ul, hogy gN = N g. A G csoport egy N norm´aloszt´oj´ at norm´alis r´eszcsoportnak is szok´as nevezni. 3. P´ elda. [norm´aloszt´o] A Dn di´edercsoportokban norm´aloszt´okat alkotnak az ir´ any´ıt´astart´o transzform´aci´ok r´eszcsoportjai. 12. Defin´ıci´ o. [direkt ¨osszeg] A G Abel-csoport a G1 , . . . , Gn r´eszcsoportjainak direkt ¨osszege azt a G , ha G minden eleme egy´ertelm˝ uen fel´ırhat´o a Gi csoportok elemeinek szorzatak´ent g1 , . . . , gn alakban, ahol gi ∈ Gi . (Nem kommutat´ıv esetben a Gi r´eszcsoportoknak norm´alis r´eszcsoportok kell lenni¨ uk.) 4. P´ elda. [direkt ¨osszeg] A C12 ciklikus csoport felbonthat´o k´et csoport direkt ¨osszeL g´ere: C12 ∼ = C3 C4 . 13. Defin´ıci´ o. [faktorcsoport] Egy G csoport N norm´aloszt´oj´anak mell´ekoszt´alyaib´ol alkotott csoport a (gN )(hN ) = (gh)n m˝ uveletre n´ezve, amit G/N -nel jel¨ol¨ unk. Bizonyos csoportok strukt´ ur´ai k¨oz¨ott lehet hasonl´os´ag: 14. Defin´ıci´ o. [homomorfizmus] Homomorfizmus egy olyan ϕ : G → H lek´epez´es, amely m˝ uvelettart´o, vagyis minden ∀a, b ∈ G elemre ϕ(a) · ϕ(b) = ϕ(ab). 15. Defin´ıci´ o. [izomorfizmus] Egy ϕ homomorfizmus izomorfizmus, ha bijekt´ıv. Ekkor l´etezik hozz´a egy ϕ−1 = ψ inverz homomorfizmus: ϕ(ψ(a)) = a = ψ(ϕ(a)). 5. P´ elda. [homomorfizmus, izomorfizmus] A nemnegat´ıv sz´amok (R, ·) csoportja izomorf a val´os sz´amok (R, +) csoportj´aval, az izomorfizmus pedig a logaritm´al´as: ln ab = ln a + ln b. 16. Defin´ıci´ o. [automorfizmus] Egy csoport ¨onmag´ara val´o izomorfizmus´at automorfizmusnak nevezz¨ uk. 6

17. Defin´ıci´ o. [gr´afizomorfizmus] G1 = (V1 , E1 ) ´es G1 = (V1 , E1 ) gr´afokra a bijekt´ıv φ : V1 → V2 lek´epez´es gr´afizomorfizmus, ha meg˝orzi a szomsz´eds´agi rel´aci´ot, vagyis ∀{u, v} ∈ E1 ⇐⇒ {φ(u), φ(v)} ∈ E2 . 18. Defin´ıci´ o. [gr´afautomorfizmus] Egy gr´af ¨onmag´ara val´o izomorfizmusa gr´afautomorfizmus. A csoportokhoz hasonl´o strukt´ ur´akkal is fogunk dolgozni: 19. Defin´ıci´ o. [f´elcsoport] A f´elcsoport egy olyan nem¨ ures halmaz, amelyen defini´alva van egy asszociat´ıv, k´etv´altoz´os m˝ uvelet, vagyis: ∀a, b ∈ G eset´en ab ∈ G ´es (ab)c = a(bc). 20. Defin´ıci´ o. [gy˝ ur˝ u] Egy (R, +, ·) strukt´ ur´at gy˝ ur˝ unek nevez¨ unk, ha (R, +) Abel-csoport, (R, ·) pedig f´elcsoport, valamint ha a szorz´as disztribut´ıv az ¨osszead´asra n´ezve, azaz a, b, c ∈ R elemekre a(b + c) = ab + ac ´es (a + b)c = ac + bc. Az R kommutat´ıv, ha (R, ·) kommutat´ıv. 21. Defin´ıci´ o. [ide´al] Az (R, +, ·) kommutat´ıv gy˝ ur˝ u I ⊂ R r´eszhalmaza ide´al, ha: • (I, +) < (R, +) • ∀i ∈ I, ∀r ∈ R eset´en ri ∈ I 6. P´ elda. [ide´al] Az eg´esz sz´amok gy˝ ur˝ uj´eben a k nemnulla eg´esszel oszthat´o sz´ amok ide´alt alkotnak. 22. Defin´ıci´ o. [test] Az R gy˝ ur˝ u test, ha kommutat´ıv ´es (R, ·) csoport. 23. Defin´ıci´ o. [testb˝ov´ıt´es] Ha K r´eszteste a L testnek, akkor L-t K b˝ov´ıt´es´enek nevezz¨ uk, K < L pedig egy testb˝ov´ıt´es, amit L | K-val is jel¨ol¨ unk. 7. P´ elda. [testb˝ov´ıt´es] Egy test v´eges b˝ov´ıt´ese a Q sz´amtest egy n-edfok´ u α algebrai n−1 sz´ammal val´o b˝ov´ıt´ese, Q(α) = {r0 + r1 α + . . . + rn−1 α | ri ∈ Q}. 24. Defin´ıci´ o. [algebrai eg´esz(1)] Egy K sz´amtestben α ∈ K algebrai eg´esz, ha l´etezik olyan 1 f˝oegy¨ utthat´oj´ u f (x) ∈ Z[x] polinom, melynek gy¨oke, vagyis f (α) = 0. 25. Defin´ıci´ o. [algebrai eg´esz(2)] Egy K sz´amtestben α ∈ K algebrai eg´esz, ha az 1 f˝oegy¨ utthat´oj´ u, Q f¨ol¨otti minim´alpolinomja Z[x]-ben van. 7

26. Defin´ıci´ o. [monomorfizmus] Egy injekt´ıv homomorfizmust monomorfizmusnak nevez¨ unk. Legyen K egy n-fok´ u algebrai sz´amtest ´es legyenek σ1 , . . . , σn : K → C a Qmonomorfizmusok. 27. Defin´ıci´ o. [konjug´alt] α ∈ K sz´am konjug´altjai a σi (α) sz´amok. 8. P´ elda. [b˝ov´ıt´es] Ha α nem val´os, m´asodfok´ u algebrai sz´am, akkor a Q(α) b˝ov´ıt´es komplex sz´amokat ad. 28. Defin´ıci´ o. [algebrai sz´amtest] Algebrai sz´amtestnek nevezz¨ uk Cnek egy K r´esztest´et, amely Q-nak v´eges fok´ u b˝ov´ıt´ese. 29. Defin´ıci´ o. [egyszer˝ u b˝ov´ıt´es] Egy K test egy elemmel val´o b˝ov´ıt´es´et egyszer˝ u b˝ov´ıt´es´enek nevezz¨ uk. 30. Defin´ıci´ o. [b˝ov´ıt´es foka] Egy K f¨ol¨otti L b˝ov´ıt´es foka a K f¨ol¨otti L vektort´er n dimenzi´oja, ezt [L : K] = n-nel jel¨olj¨ uk. 1. T´ etel. [v´egesen gener´alt Abel-csoportok alapt´etele] [22, 25] • Minden v´egesen gener´alt Abel-csoport izomorf ciklikus pr´ımhatv´anyrend˝ u csoportok ´es v´egtelen ciklikus csoportok direkt ¨osszeg´evel. Vagyis minden ilyen G csoportra: G∼ = Zn ⊕ Zq1 ⊕ · · · ⊕ Zqt ahol az n, q1 , · · · , qt sz´amok ´ert´ekei a sorrendt˝ol eltekintve egy´ertelm˝ uen meghat´arozottak ´es a q1 , · · · , qt sz´amok (nem felt´etlen¨ ul k¨ ul¨onb¨oz˝o) pr´ımek hatv´anyai. • Minden v´egesen gener´alt G Abel-csoportra: G∼ = Zn ⊕ Zk1 ⊕ · · · ⊕ Zku ahol a ki |ki+1 (∀i = 1, · · · , u − 1-re). Itt n ´es k1 , · · · , ku ´ert´ekei ´es sorrendje is G ´altal egy´ertelm˝ uen meghat´arozottak.

8

2. fejezet A Pell-egyenletek ´ es az egys´ egcsoport N´eh´any egyszer˝ ubb p´elda, ami el˝osz¨or esz¨ unkbe juthat, amikor az eml´ıtett algebrai stukt´ ur´akr´ol besz´el¨ unk: • f´elcsoportok: (N, +), (Z, ·), (Zn×n , ·) • csoportok: (Z, +), (Zn , +), (Q, ·), (R, ·), (C, ·), (H, ·), (A ∈ Rn×n | det(A) 6= 0, ·) • gy˝ ur˝ uk: (Z, +, ·), (H, +, ·), (Zn×n , +, ·), (Rn×n , +, ·) Most egy hasonl´oan egyszer˝ u strukt´ ura seg´ıts´eg´evel fogjuk megmutatni, hogy menynyire j´ol haszn´alhat´ok az absztrakt algebrai m´odszerek jelen esetben egy nevezetes probl´ema, nevezetesen a Pell-egyenletek megold´as´ara.

2.1.

A Pell-egyenlet

A Pell-egyenlet” elnevez´es Leonhard Eulert˝ol sz´armazik, aki Lord Brouncker ” munk´aj´at tanulm´anyozta a nevezetes diophantoszi egyenletr˝ol, de v´eletlen¨ ul ¨osszekeverte Brouncker ´es John Pell nev´et. M´ar az o´kori g¨or¨og¨oket ´es indiaiakat is ´erdekelt´ek a Pell-egyenletek, k¨ ul¨on¨osen az x2 − 2y 2 = 1 alak´ u, ugyanis ennek megold´asai nagyon szoros kapcsolatban √ vannak a 2 racion´alis k¨ozel´ıt´es´evel. Ha az egyenlet egy megold´asa x ´es y, akkor xy √ uket azok a nagyon j´o racion´alis k¨ozel´ıt´ese lesz 2-nek. Diophantoszr´ol kapt´ak a nev¨

9

t¨obbv´altoz´os polinomi´alis egyenletek, melyekben csak eg´esz megold´asokat enged¨ unk meg. Indi´aban Brahmagupta m´ar 628-ban k´esz´ıtett m´odszert a Pell-egyenlet ´es m´as kvadratikus egyenletek megold´as´ara, de Lord Brouncker volt az els˝o eur´opai matematikus, aki ´altal´anos megold´ast tal´alt a nevezetes egyenletre. A XII. ´es XIV. sz´azadban k´et, szint´en indiai matematikus, Bhaskara ´es Narayana is tal´alt a´ltal´anos megold´ast az egyenletre. 31. Defin´ıci´ o. [Pell-egyenlet] Pell-egyenletnek nevezz¨ uk az x2 − dy 2 = 1 alak´ u diophantoszi egyenletet, illetve ´altal´anosabb form´aban az x2 − dy 2 = c alak´ u egyenleteket, ahol d ∈ Z+ , c ∈ Z, eg´eszek k¨oz¨ott keress¨ uk.

√ d∈ / Q. Az (x, y) megold´asokat teh´at az

Jelen dolgozatban azonban csak az x2 − 2y 2 = 1 alak´ u egyenlettel fogok m´elyebben foglalkozni. A Pell-egyenlet gy¨okeinek meghat´aroz´as´ara sz´amos m´odszer l´etezik: l´anct¨ortekkel, faktoriz´aci´o kvadratikus szit´aval, s˝ot, kvantumsz´am´ıt´og´eppel is kereshet¨ unk megold´asokat. Ha van egy nemtrivi´alis x1 , y1 kiindul´o megold´asunk (y1 6= 0), akkor v´egtelen sok tov´abbi megold´ast a´ll´ıthatunk el˝o egy egyszer˝ u k´eplettel: √ √ xi + yi d = (x1 + y1 d)i Ezzel ekvivalens a k¨ovetkez˝o rekurzi´o [8]: xi+1 = x1 xi + dy1 yi yi+1 = x1 yi + y1 xi ´ Erdekess´ eg tov´abb´a, hogy az els˝o- ´es m´asodfaj´ u Csebisev-polinomok (Ti ´es Ui ) 2 2 is a megold´asai lehetnek a p − nq = 1 Pell-egyenletnek a Q[x] egyv´altoz´os polinomgy˝ ur˝ u felett, ha n = x2 − 1, m´egpedig a k¨ovetkez˝ok´eppen: 2 Ti2 − (x2 − 1)Ui−1 =1

10

Tov´abb´a hasonl´o k´epletet is kapunk a t¨obbi megold´as el˝oa´ll´ıts´ara: √ √ Ti + Ui−1 x2 − 1 = (x + x2 − 1)i Ez a megfigyel´es is sugallja, hogy a Pell-egyenlet megold´asa sor´an ´erdemes t´amaszkodni az algebrai sz´amelm´elet eszk¨ozt´ar´ara, ez´ert most olyan megk¨ozel´ıt´est fogunk alkalmazni, ami felhaszn´alja a sz´amgy˝ ur˝ ukkel kapcsolatos ismereteinket.

2.2.

Megk¨ ozel´ıt´ es az algebrai sz´ amelm´ elet seg´ıts´ eg´ evel

A x2 − dy 2 = 1 egyenletet szorzatt´a alak´ıtva az (x −

√ dy)(x +

√ dy) = 1

alak´ u egyenletet kapjuk. Ennek a faktoriz´aci´onak a c´elja az, hogy a megfelel˝o sz´amgy˝ ur˝ uben dolgozhassunk, ´ıgy szorzatk´ent el˝o´all´ıthassuk az egyenlet jobb oldal´an a´ll´o 1-et. √ √ √ √ ur˝ uben Mivel x, y ∈ Z, ez´ert x − dy ´es x + dy sz´amokkal a Z( d) ⊆ Q( d) gy˝ szeretn´enk ´es fogunk sz´amolni. A k´es˝obbiekben fontos lesz az a megfigyel´es, hogy √ ennek a b˝ov´ıt´esnek a foka [Q( d) : Q] = 2. √ √ 32. Defin´ıci´ o. [norma(1)] Egy Q( d)-beli z = a + b d sz´am konjug´altja z = √ a − b d ´es norm´aja: N (z) = zz = a2 − db2 Az ´ıgy bevezetett norma defin´ıci´oja egy´ebk´ent nem m´as, mint az algebrai sz´amtestekben ´altal´aban haszn´alt norma [9] speci´alis esete: 33. Defin´ıci´ o. [norma(2)] Ha K algebrai test Q f¨ol¨ott ´es α egy K-beli eg´esz, akkor α-nak n konjug´altja l´etezik C-ben, az α sz´am norm´aja ekkor N (α) = α1 · · · αn . Term´eszetesen a defin´ıci´ob´ol k¨ovetkezik, hogy α norm´aja f¨ ugg a K testt˝ol, hiszen p´eld´aul m´ıg a 2 norm´aja a racion´alis sz´amtest f¨ol¨ott 2, addig a Gauss-racion´alis sz´amok k¨or´eben 4 lesz.

11

2. T´ etel. [multiplikativit´as] A norma k´epz´ese ´es a konjug´al´as is multiplikat´ıv: N (z)N (w) = N (zw) zw = z · w Az ´ıgy defini´alt norma ´es konjug´al´as teh´at kulcsfontoss´ag´ u lesz a Pell-egyenlet gy¨okeinek meghat´aroz´as´an´al, hiszen ekkor az x, y megold´asok egy´ertelm˝ uen megfe√ √ leltethet˝ok egy Z( d)-beli sz´amnak: z = x + dy. Ez azt jelenti, hogy az eredeti egyenlet a bevezetett sz´amgy˝ ur˝ uben a k¨ovetkez˝o egyenlett´e alak´ıthat´o: N (z) = 1. Vegy¨ uk ´eszre, hogy b´armely z megold´asra, vagyis ha N (z) = 1, akkor z is megold´as ´es z = z1 , hiszen N (z) = z · z = zz = zz = N (z). Hasonl´oan N (−z) = (−z) · −z = (−1) · z · (−1) · z = (−1) · z · (−1) · z = (−1) · z · (−1) · z = zz = N (z). Ezek alapj´an teh´at meg´allap´ıthatjuk, hogy ha tal´alunk egy z0 megold´ast, akkor abb˝ol el˝oa´ll´ıthatjuk a zn = ±z0n , n ∈ Z megold´asokat, ezeknek megfelel˝o x, y sz´amok megold´asai lesznek Pell-egyenletnek [6].

2.3.

A Dirichlet-egys´ egt´ etel

Egy gy˝ ur˝ uben fontos speci´alis elemek azok, melyek invert´alhat´oak, az (R, ·) multiplikat´ıv f´elcsoport eset´eben ugyanis nem k¨ovetelt¨ uk meg az invert´alhat´os´agot: 34. Defin´ıci´ o. [egys´eg] Egy R gy˝ ur˝ u (R, ·) multiplikat´ıv f´elcsoportj´aban egys´egnek nevezz¨ uk azokat az elemeket, amelyeknek l´etezik inverze, vagyis azon u ∈ R elemek, melyekre ∃v = u−1 : uv = vu = 1R , ahol 1R a multiplikat´ıv egys´egelem. 3. T´ etel. [egys´egcsoport] Egy R gy˝ ur˝ u egys´egeinek U (R) halmaza (multiplikat´ıv) csoportot alkot az R-beli szorz´asra n´ezve. Bizony´ıt´ as. • asszociativit´as: trivi´alis, hiszen mag´ara az R gy˝ ur˝ ure is igaz • m˝ uveleti z´arts´ag: −1 −1 =⇒ ∃(u1 u2 )−1 = u−1 u1 ∈ U (R), u2 ∈ U (R) =⇒ ∃u−1 1 , u2 2 u1 : −1 −1 −1 −1 −1 (u1 u2 )(u1 u2 )−1 = (u1 u2 )u−1 2 u1 = u1 (u2 u2 )u1 = u1 1R u1 = u1 u1 = 1R • egys´egelem: trivi´alis, hiszen 1R az eredeti gy˝ ur˝ uben is multiplikat´ıv egys´egelem 12

• inverz elem: trivi´alisan l´etezik, hiszen pontosan az invert´alhat´o elemeket vett¨ uk be a csoportba  √ ur˝ uj´eben: 9. P´ elda. [egys´egek] A Z( d) eg´eszeinek gy˝ √ √ √ • d = 2 eset´en z = 2 + 1 sz´amra: ( 2 + 1)( 2 − 1) = 2 − 1 = 1 √ √ √ • d = 5 eset´en z = 5 + 2 sz´amra: ( 5 + 2)( 5 − 2) = 5 − 4 = 1 Mint l´atni fogjuk, v´egtelen sok egys´eg van. 4. T´ etel. [egys´egek norm´aja] Egy R algebrai sz´amgy˝ ur˝ u r eleme akkor ´es csak akkor tartozik az U (R) egys´egcsoportba, ha norm´aja N (r) = ±1. Bizony´ıt´ as. Itt csak azt mutatjuk meg, hogy egys´egcsoport elemeinek norm´aja ±1. Az r gy˝ ur˝ uelem pontosan akkor eleme U (R)-nek, ha ∃r−1 : rr−1 = 1. Ekkor a norma multiplikativit´asa miatt N (r)N (r−1 ) = N (rr−1 ) = N (1) = 1. Mivel az a norma az eg´esz sz´amokra k´epez, az r sz´am N (r) norm´aja csak ±1 lehet.  √ Jegyezz¨ uk meg, hogy az eredeti sz´amgy˝ ur˝ unk (Z( d)) kommutat´ıv! Ebb˝ol k¨ovet√ kezik, hogy az U (Z( d)) egys´egcsoport, amivel most dolgozni fogunk, Abel-csoport lesz. Egy Abel-csoport torzi´omentes rangj´ara t¨obb, ekvivalens defin´ıci´o l´etezik [27], ezek k¨oz¨ ul praktikus ´es elegend˝o is most a legegyszer˝ ubb: 35. Defin´ıci´ o. [egys´egcsoport rangja] Egy G Abel-csoport rangja az az n sz´am, amely a maxim´alis Z-line´arisan f¨ uggetlen, G-beli r´eszhalmazok sz´amoss´aga. Ez az n sz´am invari´ans a vektorterek dimentzi´oj´ahoz hasonl´oan, amit a kicser´el´esi t´etel mond ki. √ ur˝ uvel dolgoA Pell-egyenletb˝ol sz´armaztatott algebrai probl´ema a Z( d) gy˝ √ zik. Alapvet˝oen a Q( d) sz´amtesttel dolgozn´ank, de mi csak az egyenlet eg´esz megold´asait keress¨ uk. A sz´amtestek algebrai eg´eszeivel juthatunk el a megfelel˝o sz´amgy˝ ur˝ uh¨oz. A tov´abbiakban a r¨ovids´eg kedv´e´ert a K algebrai sz´amtest algebrai eg´eszeinek gy˝ ur˝ uj´et OK -vel fogjuk jel¨olni. √ √ A Q( d) sz´amtest algebrai eg´eszei d ≡ 2, 3 (mod 4) eset´en pontosan a Z( d)beli sz´amok lesznek. A d ≡ 0 (mod 4) esetben d nem n´egyzetmentes, ekkor az 13

egyenlet visszavezethet˝o egy n´egyzetmentes d sz´amra. A d ≡ 1 (mod 4) esetben a √ √ 2) Z( d+1 )-beli sz´ a mokkal kell sz´ a molnunk. Mindezek miatt a tov´ a bbiakban a Q( 2 √ test algebrai eg´eszeinek t´argyal´as´an´al dolgozhatunk a Z( 2) sz´amokkal. 36. Defin´ıci´ o. [kvadratikus test] Kvadratikus sz´amtest egy olyan K algebrai sz´am√ √ / Z, d > 0 eset´eben val´ os test, amely m´asodfok´ u Q f¨ol¨ott. Q( d) eset´eben, ha d ∈ kvadratikus testr˝ol besz´el¨ unk, d < 0 eset´en k´epzetes vagy imagin´arius kvadratikus testr˝ol. Arra a k´erd´esre, hogy milyen a t´argyalt egys´egcsoport szerkezete (´es a´ltal´aban tetsz˝oleges sz´amtestben az egys´egcsoport´e), a Dirichlet-egys´egt´etel fog v´alaszt adni. 37. Defin´ıci´ o. [be´agyaz´as] Ha σi : K → R, akkor val´os be´agyaz´asnak nevezz¨ uk, egy´ebk´ent komplex be´agyaz´asnak. A val´os be´agyaz´asok sz´am´at r1 , a komplexek´et r2 jel¨oli. ´Igy kapjuk a k¨ovetkez˝o kanonikus be´agyaz´ast: σ : K → Rr1 × Cr2 = Rn Ez a kanonikus be´agyaz´as egy injekt´ıv gy˝ ur˝ uhomomorfizmus, melyre σ(x) = (σ1 (x), · · · , σr1 +r2 (x)). 5. T´ etel. [Dirichlet-egys´egt´etel(1)] Egy OK gy˝ ur˝ u U (OK ) egys´egcsoportja v´egesen gener´alt ´es a rangja r = r1 + r2 − 1, ahol r1 a val´os be´agyaz´asok, r2 pedig a komplex be´agyaz´asok konjug´alt p´arjainak sz´ama. 6. T´ etel. [Dirichlet-egys´egt´etel(2)] [5] Egy K test U (K) egys´egcsoportja izomorf a G × Zr csoporttal, ahol G az 1-nek K gy˝ ur˝ ubeli gy¨okeit tartalmaz´o ciklikus csoport, ´es r = r1 + r2 − 1. (M´ask´epp: G a K-ba es˝o komplex egys´eggy¨ok¨ok v´eges ciklikus csoportja.) Mivel egy Q-monomorfizmus komplex konjug´altja is Q-monomorfizmus, a σi -k et ´atsz´amozva p´arba a´ll´ıthatjuk o˝ket a k¨ovetkez˝ok´eppen: Legyenek a val´os be´agyaz´asok σ1 , · · · , σr1 , a komplexek pedig σr1 +1 , · · · , σn u ´gy, hogy j = 1, · · · , r2 -re minden σr1 +j -t a komplex konjug´altj´aval, σr1 +r2 +j -vel p´aros´ıtjuk o¨ssze. ´Igy ad´odik, hogy 2r2 komplex be´agyaz´as van, valamint [K : Q] = n = r1 + 2r2 . 14

Az egys´egcsoport strukt´ ur´aj´at teh´at ismerj¨ uk, meghat´arozhatjuk a rangj´at ´es el˝o´all´ıthatjuk csoportok direkt szorzatak´ent is. Ezek alapj´an egy val´os kvadratikus test egys´egcsoportj´anak rangja 1, az imagin´arius kvadratikus testek´e pedig 0 lesz. √ √ A Pell-egyenlet eset´eben a Q( d) kvadratikus testtel, illetve Z( d) eg´eszekkel dolgozunk, melynek U (OK ) egys´egcsoportja 1 rang´ u. Mivel a Dirichlet-egys´egt´etel kimondja, hogy ez a csoport v´egesen gener´alt, ez´ert elegend˝o megkeresni a gener´ator´at. A v´egesen gener´alt Abel-csoportok alapt´etele szerint minden v´egesen gener´alt Abel-csoport egy v´eges rang´ u szabad Abel-csoport ´es egy v´eges Abel-csoport direkt o¨sszege, melyek izomorfizmus erej´eig egy´ertelm˝ uen meghat´arozottak. A vizsg´alt Pell-egyenlet eset´en az U egys´egcsoport teh´at U∼ =G×H = Z × Z2 ∼ √ ad´odik, ahol az egyenlet egy nemtrivi´alis megold´asa, 3+2 2 v´alaszthat´o a H csoport gener´ator´anak, ezen k´ıv¨ ul G = {±1}. Mivel a vizsg´alt p´eld´aban x2 − 2y 2 6≡ 3 (mod 4) miatt −1 norm´aj´ u egys´eg nem l´etezik, az egys´egek pontosan a Pell-egyenlet megold´asait adj´ak. A d ≡ 1 √ miatt o¨sszetettebb a megold´asok szerkezete, x2 − dy 2 ≡ −1 (mod 4) esetben d+1 2 is el˝ofordulhat, tov´abb´a az egys´egcsoport elemeire x, y nem felt´etlen¨ ul lesznek eg´esz sz´amok, ´ıgy ott az egys´egek ´es a megold´asok k¨oz¨otti kapcsolat bonyolultabb.

15

3. fejezet Csoportok ´ es Cayley-gr´ afok ´ Altal´ aban a csoportok ´es k¨ ul¨on¨osen a diszkr´et csoportok strukt´ ur´aj´anak vizsg´alatakor fontos szerepe van a csoport gener´atorainak. A gener´atorelemek sz´ama ´es rendje sokat el´arul a csoport szerkezet´er˝ol ´es rendj´er˝ol is, ezen k´ıv¨ ul csoportok k¨oz¨otti hasonl´os´agokra is k¨ovetkeztethet¨ unk. A csoportok gener´etorhalmazainak seg´ıts´eg´evel a felrajzolhatjuk Cayley-gr´afjaikat, ami szint´en egy hasznos eszk¨oz a strukt´ ura felt´ar´as´aban. A Cayley-gr´afok tulajdons´agait a v´eges vagy v´egesen gener´alt csoportok eset´en (ezek u ´gynevezett diszkr´et csoportok) fogom vizsg´alni. Egy G csoporthoz a´ltal´aban t¨obbf´elek´eppen v´alaszthatunk gener´atorhalmazt, ez a v´alaszt´as pedig tetsz˝oleges, ´ıgy a csoportelemek a gener´atorelemek m´as-m´as kombin´aci´ojak´ent fognak el˝o´allni. Amikor teh´at egy csoporthoz felrajzoljuk a Cayleygr´afj´at, az term´eszetesen k¨ ul¨onb¨oz˝o elemeknek megfeleltetett cs´ ucsokat fog ¨osszek¨otni, att´ol f¨ ugg˝oen, hogyan v´alasztottuk ki az S gener´atorhalmazt. A Cayley-gr´afokat sok helyen haszn´alj´ak: alapvet˝o eszk¨oz a kombinatorikus ´es a geometriai csoportelm´eletben, a m´asodrend˝ u logik´aban [5], a p´arhuzamos programoz´asban h´al´ozati topol´ogiak´ent haszn´alj´ak ir´any´ıtatlan, 3-regul´aris v´altozatait, a gy˝ ur˝ us kock´akat [17].

3.1.

A Lov´ asz-sejt´ es

Tov´abbi ´erdekess´eg, hogy egy m´aig nyitott probl´ema is kapcsol´odik a Cayleygr´afokhoz: a Lov´asz-sejt´es 1970-b˝ol, mely a Hamilton-k¨or¨ok klasszikus probl´em´aj´aval foglalkozik [1, 7, 10]. 38. Defin´ıci´ o. [cs´ ucs-tranzitivit´as] Ha egy G = (V, E) gr´afnak minden ∀u, v ∈ V 16

cs´ ucsp´arra l´etezik olyan φ : V → V gr´afautomorfizmusa, amelyre φ(u) = v, akkor a G gr´af cs´ ucs-tranzit´ıv. 1. Sejt´ es. [Lov´asz-sejt´es] Minden v´eges, ¨osszef¨ ugg˝o cs´ ucs-tranzit´ıv gr´af tartalmaz Hamilton-utat. Hamilton-k¨or eset´eben a sejt´esre t¨obb ellenp´eld´at is ismer¨ unk: a 2-cs´ ucs´ u teljes gr´af (K2 ), a Petersen gr´af, a Coxeter-gr´af, valamint az ut´obbi kett˝ob˝ol a cs´ ucsok h´aromsz¨oggel val´o helyettes´ıt´es´evel kapott gr´afban sincs Hamilton-k¨or. ´Igy a Lov´aszsejt´es er˝os´ıtett v´altozata: 2. Sejt´ es. [er˝os Lov´asz-sejt´es] Az ¨ot ismert kiv´etelen k´ıv¨ ul minden v´eges, ¨osszef¨ ugg˝ o cs´ ucs-tranzit´ıv gr´af tartalmaz Hamilton-k¨ort. Mivel minden Cayley-gr´af cs´ ucs-tranzit´ıv, a sejt´es egy gyeng´ıtett v´altozat´at is megfogalmazhatjuk: 3. Sejt´ es. [Lov´asz-sejt´es Cayley-gr´afokra] Minden v´eges, ¨osszef¨ ugg˝o Cayley-gr´ af tartalmaz Hamilton-k¨ort. A sejt´es tov´abb´a nem igaz ir´any´ıtott Cayley-gr´afokra. A gyenge sejt´es m´asodik v´altozat´at speci´alis esetekben csoportelm´eleti eszk¨oz¨okkel ´erdemes vizsg´alni, Abelcsoportokra p´eld´aul k¨onnyen igazolhat´o az a´ll´ıt´as.

3.2.

Cayley-gr´ afok

Egy Γ Cayley-gr´af egy G diszkr´et csoport strukt´ ur´aj´at k´odolja a tetsz˝olegesen v´alasztott S gener´atorhalmaz szerint, ´ıgy a csoport szerkezet´et seg´ıt felt´arni. 39. Defin´ıci´ o. [sz´ınezett Cayley-gr´af ] Egy G diszkr´et csoport tetsz˝oleges S gener´atorhalmaz´ahoz a Γ = Γc (G, S) ir´any´ıtott sz´ınezett Cayley-gr´af a k¨ovetkez˝ok´eppen k´esz´ıthet˝o el: • az S gener´atorhalmaz s elemeihez egy cs sz´ınt rendel¨ unk • a G csoport minden g elem´ehez egy´ertelm˝ uen hozz´arendelj¨ uk Γ egy cs´ ucs´at: V (Γ) ↔ G • minden g ∈ G ´es s ∈ S p´arhoz a Γ gr´afban a g ´es s · g cs´ ucsok k¨oz¨ott egy ir´any´ıtott, cs sz´ın˝ u ´el megy 17

Ha az S-t u ´gy v´alasztjuk, hogy szimmetrikus gener´atorhalmaz legyen (vagyis minden s ∈ S : s−1 ∈ S), akkor egy olyan ~Γ(G, S) ir´any´ıtott Cayley-gr´afot kapunk, ~ : vu ∈ E). ~ amelynek minden ´ele k´etszeres: ∀uv ∈ E Ha eltekint¨ unk az ´elek sz´ınez´es´et˝ol, akkor a ~Γ(G, S) ir´any´ıtott Cayley-gr´afot kapjuk, ha az ir´any´ıt´ast sem vessz¨ uk figyelembe, akkor a Γ(U, V ) Cayley-gr´afot. 10. P´ elda. [Cayley-gr´af ] (egy-k´et kisebb diszkr´et csoport, a gener´atora ´es egy ´abra a gr´afr´ol) Fontos megjegyezni, hogy az e egys´egelemet nem vessz¨ uk be az S gener´atorhalmazba, hiszen ezzel csak hurok´eleket kapn´ank minden egyes cs´ ucshoz. Elmondhat´o, hogy ha S val´oban gener´atora G-nek, akkor a Cayley-gr´af ¨osszef¨ ugg˝o lesz, t¨obbsz¨or¨os ´elek 2-rend˝ u elemekn´el fordulhatnak el˝o, valamint pontosan akkor kapunk k¨ormentes gr´afot, vagyis Cayley-f´at, ha G szabad csoport, hiszen ekkor ´all el˝o minden g ∈ G elem a gener´atorelemek egy´ertelm˝ u kombin´aci´ojak´ent. A Cayley-gr´afr´ol tov´abbi alapvet˝o tulajdons´agokat is meg´allap´ıthatunk: • minden ir´any´ıtott ´es ir´any´ıtatlan Cayley-gr´af is cs´ ucs-tranzit´ıv • a ~Γ(G, S) Cayley-digr´af regul´aris, m´egpedig d = |S| eset´eben minden cs´ ucsb´ol pontosan d darab ´el megy ki ´es d darab ´el fut be, melyek sz´ama term´eszetesen f¨ ugg a v´alasztott gener´atorhalmazt´ol • az ir´any´ıtott Cayley-gr´af er˝osen ¨osszef¨ ugg˝o • a Γ(G, S) Cayley-gr´af regul´aris, minden cs´ ucs foka |S ∪ S −1 − {1}| Minden, a gr´afban megtal´alhat´o k¨or egy ¨osszef¨ ugg´est fog jelenteni az elemekre n´ezve a k¨ovetkez˝ok´eppen: A k¨or¨on haladva folyamatosan jegyezz¨ uk fel az ´elek sz´ın´ehez tartoz´o gener´atorelemeket (visszafel´e mutat´o ´elen is haladhatunk el˝ore, mivel ez az inverz elemmel val´o szorz´ast jelenti), majd mikor vissza´ert¨ unk a kiindul´o elemhez, meg´allunk. A feljegyzett elemeket o¨sszeszorozzuk a megfelel˝o sorrendben, s mivel a k¨or visszat´er o¨nmag´aba, az e egys´egelemet fogjuk kapni a szorz´as v´egeredm´enyek´epp. Ezt egy rel´aci´o nak nevezz¨ uk. A gr´afban minden k¨or egy ilyen rel´aci´ot fog jelenteni, ami m´ar a konkr´et elemekt˝ol f¨ uggetlen¨ ul, eg´eszen absztrakt m´odon jellemzi a csoport szerkezet´et. A rel´atorok olyan, a csoport elemeib˝ol a´ll´o kifejez´esek, melyek a csoport egys´egelem´evel tekintend˝ok egyenl˝onek, ez´altal rel´aci´okat jelk´epeznek. 18

40. Defin´ıci´ o. [csoport prezent´aci´oja] Egy G csoport prezent´aci´oja hS | Ri, ahol S a G csoport gener´atorhalmaza, R pedig a csoportot meghat´aroz´o rel´atorok S-b˝ ol k´epzett halmaza. Egy prezent´aci´o v´eges, ha G v´egesen gener´alt, vagyis S v´eges, valamint ha R is v´eges. 7. T´ etel. [Dyck t´etele] Tekints¨ unk egy S gener´atorhalmaz ´altal gener´alt hSi szabad csopotot. Tekints¨ uk benne szavak egy R halmaz´at. N legyen R norm´alis lez´artja Sben, vagyis az a minim´alis norm´alis r´eszcsoport, ami tartalmazza R-t. Ekkor a hS, Ri prezent´aci´o ´altal meghat´arozott csoport: hS | Ri = hSi/N 11. P´ elda. [csoport prezent´aci´oja] A D2n di´edercsoport prezent´aci´oja: hf, t | t2 , f n , (f t)2 i, ahol t tengelyes t¨ ukr¨oz´est, f pedig egy olyan forgat´ast jelent, melynek rendje relat´ıv pr´ım n-hez. 8. T´ etel. [csoportok prezent´aci´oja] Minden G csoportnak l´etezik prezent´aci´oja, valamint minden v´eges csopornak l´etezik v´eges prezent´aci´oja. Ahhoz, hogy a Cayley-gr´afok defin´ıci´oj´at m´eg m´elyebben meg´erts¨ uk, a Cayleyt´etel ny´ ujt alapot: 41. Defin´ıci´ o. [szimmetrikus csoport] Egy S halmaz Sym(S) szimmetrikus csoportja az a csoport, amely az S halmaz ¨osszes bijekci´oj´at tartalmazza, a kompoz´ıci´ora, mint csoportm˝ uveletre n´ezve. A szimmetrikus csoport elemei az S permut´aci´oi. 12. P´ elda. [szimmetrikus csoport] Egy n elem˝ u halmaz szimmetrikus csoportja n! rend˝ u. P´eld´aul a Z4 = ({0, 1, 2, 3}, + (mod 4)) csoport szimmetrikus csoportj´anak rendje teh´at 24, elemei: id, (12) ,(13), (14), (23), (24), (34), (12)(34), (13)(24), (14)(23), (123), (124), (134), (234), (132), (142), (143), (243), (1234), (1243), (1324), (1342), (1423), (1432). 9. T´ etel. [Cayley-t´etel] Minden G csoport izomorf a G alaphalmazot vett szimmetrikus csoportnak, Sym(G)-nek egy r´eszcsoportj´aval. A Cayley-t´etelben szerepl˝o τ : G → K (K < Sym(G)) izomorfi´at G regul´aris reprezent´aci´oj´anak is szok´as nevezni.

19

13. P´ elda. [regul´aris reprezent´aci´o] A m´ar bemutatott Z4 csoport elemei sorra az {id, (1234), (13)(24), (1432)} elemeknek fognak megfelelni. Trivi´alis, de a fenti p´eld´an is j´ol l´atszik, hogy a kiindul´o csoport kommutativit´as´ab´ol egy´altal´an nem k¨ovetkezik a szimmetrikus csoporj´anak kommutativit´asa, hiszen az Sn szimmetrikus csoportok csak n ≤ 2-re Abel-csoportok. Gondoljuk meg, milyen gr´afokat kapunk speci´alis G csoportokra! Ha G Abel-csoport, akkor ∀a, b ∈ G : ab = ba, vagyis a kommut´atorra a−1 b−1 ab = 1, ´ıgy ez b´armely k´et gener´atorelemre egy 4-hossz´ u k¨ort eredm´enyez a Cayley-gr´afban. Ez a gener´atorelemek sz´am´at´ol f¨ ugg˝oen t¨obbdimenzi´os r´acsot” fog gener´alni, a cso” port kommutativit´asa teh´at mag´aban egy s˝ ur˝ u r´acsozatot jelent a gr´afban. Ha G szabad csoport, akkor a Cayley-gr´af egy Cayley-fa lesz, amit Bethe-h´al´onak is neveznek.

K´et olyan csoport Cayley-gr´afj´at k´esz´ıtett¨ uk el, amelyek k´et gener´atorelemmel adottak. A k¨ ul¨onbs´eg k¨ozt¨ uk prezent´aci´oban megadott R azonoss´agokban van: Az els˝o egy szabad csoport, melyet a ´es b gener´alnak, a csoport prezent´aci´oja ha, b | ∅i. L´athat´o, hogy minden cs´ ucsban n´egy ´el tal´alkozik: kett˝o indul ki ´es kett˝o ´erkezik be. Az ´ıgy kapott Cayley-fa szimmetri´aja j´ol l´athat´o, a kiindul´asi egys´egelemnek m´as elemet v´alasztva (´es term´eszetesen az ´elek hossz´at megfelel˝oen ´atsk´al´azva) a fa o¨nmag´aba vihet˝o ´at. A m´asodik egy di´edercsoport Cayley-gr´afja, ahol a β elem egy t¨ ukr¨oz´est jel¨ol, ez´altal a rendje 2, a hozz´a tartoz´o ´elek ez´altal k´etszeres ´elek lesznek. A m´asik gener´atorelem, α rendje 4, ez´ert ez a n´egyzet izometriacsoportj´anak Cayley-gr´afja. Prezent´aci´oja ´ıgy hα, β | α4 , β 2 , (αβ)2 i. L´athat´o, hogy egyik csoport sem kommutat´ıv, hiszen egyik gr´afban sincsenek 20

meg a megfelel˝oen ir´any´ıtott, 4-hossz´ us´ag´ u k¨or¨ok. (A di´edercsoport gr´afj´aban ugyan vannak 4-k¨or¨ok, de az ir´any´ıt´asuk nem megfelel˝o.) Mivel a kiv´alasztott elemek gener´alj´ak az egyes csoportokat, a Cayley-gr´afok o¨sszef¨ ugg˝oek. Ha az S-t nem megfelel˝oen v´alasztjuk meg, akkor el˝ofordulhat, hogy nem gener´alja G-t ´es ´ıgy a kapott Cayley-gr´af ugyan regul´aris lesz, de nem ¨osszef¨ ugg˝o.

3.3.

Expander gr´ afok

Term´eszetesen ad´odik, hogy egy csoport (ir´any´ıtatlan) Cayley-gr´afj´at szeretn´enk szomsz´eds´agi m´atrixk´ent is fel´ırni. Trivi´alisan ekkor |S| = d gener´ator eset´en a gr´af d-regul´aris, ´ıgy a szomsz´eds´agi m´atrix minden sor´aban ´es oszlop´aban is pontosan d darab 1-es van. K¨onny˝ u l´atni, hogy ilyenkor a m´atrix egyik saj´atvektora az 1-esekb˝ol a´ll´o vektor, a hozz´a tartoz´o saj´at´ert´ek pedig d. A gener´atorelemek rendj´et˝ol f¨ ugg˝oen kapunk s˝ ur˝ ubb vagy ritk´abb gr´afot (´es ezzel m´atrixot is). Expander gr´afok alatt tulajdonk´eppen olyan ritka gr´afokat ´ert¨ unk, amelyek egyszersmind j´ol o¨sszek¨ot¨ottek” is, vagyis a cs´ ucsokb´ol indul´o ´elek strukt´ ur´aja bizonyos ” ´ertelemben s˝ ur˝ u. Azt, hogy egy ilyen ir´any´ıtatlan gr´af mennyire ¨osszef¨ ugg˝o, illetve mennyire j´ol k¨ot¨ott”, t¨obbf´ele m´er˝osz´ammal m´erhetj¨ uk: ” 42. Defin´ıci´ o. [Cheeger-konstans] A G gr´af Cheeger-konstansa (izoperimetrikus sz´ama vagy ´el-expanzi´oja) a h(G) := min n 1≤|S|≤ 2

|∂(S)| |S|

sz´am, ahol S ⊂ V , ´es ∂(S) azon ´elek halmaza, melyeknek pontosan egy v´egpontjuk S-beli. Ha ez a h sz´am nem t´ ul kicsi (a prec´ız megfogalmaz´ast´ol most eltekint¨ unk), akkor az S r´eszhalmazoknak sok szomsz´edjuk lesz. 43. Defin´ıci´ o. [konduktivit´as] Egy G = (V, E) gr´afban egy (S, S) v´ag´as konduktivit´asa P i∈S,j∈S aij ϕ(S) = a(S)a(S) P P ahol a(S) = i∈S j∈V aij , vagyis azon ´elek sz´ama, melyeknek van S-beli cs´ ucsa. A G gr´af konduktivit´asa: φ(G) = min{ϕ(S) | S ⊆ V }. 21

44. Defin´ıci´ o. [cs´ ucs-expanzi´o] A G gr´af α-cs´ ucs-expanzi´oja gα (G) =

|Γ(S)| 1≤|S|≤αn |S| min

ahol Γ(S) azon cs´ ucsok halmaza, melyeknek van S-beli szomsz´edja. 45. Defin´ıci´ o. [spektr´alis h´ezag] Ha egy G d-regul´aris gr´afra a gr´af A szomsz´eds´agi m´atrix´anak val´os saj´at´ert´ekei λ1 ≥ λ2 ≥ · · · ≥ λn , akkor G spektr´alis h´ezaga 4(G) = λ1 − λ2 = d − λ2 . A Cheeger-konstans azt m´eri, hogy az adott gr´afnak van-e sz˝ uk¨ ulete” ´es milyen ” m´ert´ekben: ha a gr´af o¨sszef¨ ugg˝o, akkor szigor´ uan pozit´ıv ´es min´el kisebb, a gr´af ann´al ink´abb sz˝ uk”. A konduktivit´as megmutatja, mennyire gyorsan tart G-n egy ” v´eletlen s´eta az egyenletes eloszl´ashoz. A fenti m´er˝osz´amok k¨oz¨ott t¨obb ¨osszef¨ ugg´es van: • Egy d-regul´aris gr´af Cheeger-konstansa a konduktivit´as´anak d-szerese. • h(G) ≥ g 1 (G) − 1 2

• Egy d-regul´aris gr´afra

4(G) 2

≤ h(G) ≤

p

2d 4 (G) [11, 14, 26].

46. Defin´ıci´ o. [expander csal´ad] d-regul´aris gr´afok G = {G1 , G2 , . . . } csal´adj´ at ´el-expander csal´adnak nevezz¨ uk, ha l´etezik olyan pozit´ıv c konstans, hogy a csal´ ad minden G gr´afj´ara h(G) ≥ c. G cs´ ucs-expander csal´ad, ha l´etezik 1 < c konstans, hogy a csal´ad minden G gr´afj´ara g 1 (G) ≥ c. G spektr´al expander csal´ad, ha l´etezik 2 olyan pozit´ıv c konstans, ami als´o korl´atja a csal´adbeli gr´afok spektr´alis h´ezag´anak. Igazolhat´o, hogy expander csal´adok l´eteznek, valamint Babai L´aszl´onak l´etezik egy sejt´ese is, mely szerint bizonyos j´ol megv´alasztott csoportok Cayley-gr´afjainak csal´adja is expander csal´ad. Ezek bel´at´asa nem egyszer˝ u, nagy eredm´enynek sz´am´ıt ilyen expander csal´adok konstru´al´asa, ez´ert ezen ´all´ıt´asok igazol´as´at´ol most eltekintek. ugEgy gr´af Cheeger-konstansa ´es cs´ ucs-expanzi´oja k¨ozti h(G) ≥ g 1 (G)−1 ¨osszef¨ 2 g´esb˝ol k¨ovetkezik, hogy ha gr´afok egy csal´adja spektr´al expander csal´ad egy c > 1 konstansra, akkor ´el-expander csal´ad is egy c − 1 > 0 konstansra. Az expander gr´afok sz´eles k¨orben elterjedt matematikai modellek: term´eszetes vagy mesters´eges strukt´ ur´ak le´ır´as´an´al, kapcsolatok modellez´es´en´el, kommunik´aci´os h´al´ozatokban ´es h´al´ozati topol´ogi´akban, hibajav´ıt´o k´odokn´al [20, 27] haszn´alj´ak o˝ket. 22

3.4.

Algebrai gr´ afelm´ elet

Egy G gr´af A(G) szomsz´eds´agi m´atrixa val´os ´ert´ek˝ u ´es szimmetrikus, ez´ert a saj´at´ert´ekei mind val´osak: λ1 ≥ λ2 ≥ · · · ≥ λn . A k¨ovetkez˝oket tudhatjuk meg egy gr´af saj´at´ert´ekeib˝ol [7]: (bizony´ıt´as kell vmelyikre?) • ha G regul´aris, akkor λ1 = d • G pontosan akkor ¨osszef¨ ugg˝o, ha λ1 > λ2 • G pontosan akkor p´aros gr´af, ha λ1 = −λn Itt megjegyezz¨ uk, hogy elterjedt m´odszer a szomsz´eds´agi m´atrix norm´al´asa a k¨ovetkez˝ok´eppen: 47. Defin´ıci´ o. [norm´alt szomsz´eds´agi m´atrix] Ha a G gr´af szomsz´eds´agi m´atrixa a A = aij , akkor a norm´alt szomsz´eds´agi m´atrixa A0 = Dij , ahol D a gr´af foka (a legnagyobb foksz´am´ u cs´ ucs foka). L´athat´o, hogy d-regul´aris gr´afokra, amikkel most is foglalkozunk, D = d, valamint a m´atrix soraiban ´es oszlopaiban is az elemek ¨osszege 1 lesz. A norm´alt m´atrix saj´at´ert´ekei 1 ≥ λλ21 ≥ · · · ≥ λλn1 lesznek, p´aros gr´afra pedig λλn1 = −1. A spektr´alis gr´afelm´eletben a gr´af szomsz´eds´agi m´atrix´an k´ıv¨ ul a Laplace-m´atrixa is sok inform´aci´oval szolg´al a strukt´ ur´ar´ol [3]: 48. Defin´ıci´ o. [Laplace-m´atrix] Ha a G egyszer˝ u gr´af szomsz´eds´agi m´atrixa A, saj´at´ert´ekei λ1 ≥ λ2 ≥ · · · ≥ λn , akkor D := diag(d(v1 ), d(v2 ), . . . , d(vn )) a fokm´atrix (d(vi ) az i-edik cs´ ucs foka) ´es a gr´af Laplace-m´atrixa L = D − A. A Laplacem´atrix elemei teh´at:   ha i = j  d(vi ) lij = −1 ha i 6= j ´es i, j szomsz´edosak   0 egy´ebk´ent Az L0 normaliz´alt Laplace-m´atrix:     1 0 −√ 1 lij = d(vi )d(vj )    0

ha i=j ha i 6= j ´es i, j szomsz´edosak egy´ebk´ent 23

Az L Laplace-m´atrix ´es µ1 ≤ µ2 · · · ≤ µn saj´at´ert´ekei a k¨ovetkez˝o tulajdons´agokkal rendelkeznek: • L pozit´ıv szemidefinit (µi ≥ 0) • µ1 = 0 • a 0 saj´at´ert´ek (algebrai) multiplicit´asa a gr´af ¨osszef¨ ugg˝o komponenseinek sz´ama • µ2 a G gr´af algebrai o¨sszef¨ ugg˝os´ege, az el˝oz˝o a´ll´ıt´asb´ol is k¨ovetkezik, hogy µ2 6= 0 pontosan akkor, ha G o¨sszef¨ ugg˝o • a legkisebb nemnulla saj´at´ert´ek a Fiedler-´ert´ek, a hozz´a tartoz´o saj´atvektor a Fiedler-vektor ´ ıt´ 1. All´ as. [a 0 saj´at´ert´ek] A Laplace-m´atrix legkisebb saj´at´ert´eke: µ1 = 0. Bizony´ıt´ as. L-nek saj´atvektora az e = (1, 1, . . . , 1)T vektor, mert d(vi ) = |{j ∈ V | ij ∈ E}|, teh´at Ae = (0, 0, . . . , 0)T . Mivel Ae = 0 · e, a µ = 0 saj´at´ert´eke L-nek. L minden saj´at´ert´eke nemnegat´ıv, ez´ert µ0 = 0 mindenk´eppen.  ´ ıt´ 2. All´ as. [als´o korl´at] A G gr´af h(G) Cheeger-konstansa ´es µ2 algebrai ¨osszef¨ ugg˝os´eg´ere µ22 ≤ h(G). A G gr´af Fiedler-vektora is sok inform´aci´ot ny´ ujt a szerkezetr˝ol, seg´ıts´eg´evel particion´alhat´o egy gr´af a k¨ovetkez˝ok´eppen: a Fiedler-vektor pozit´ıv ´es negat´ıv elemeinek megfelel˝o cs´ ucsok ker¨ ulnek az egyik, illetve m´asik oszt´alyba. Ezen k´ıv¨ ul a nagyon kicsi abszol´ ut´ert´ek˝ u elemekhez tartoz´o cs´ ucsokat egy harmadik oszt´alyba rakhatjuk, ha tov´abb szeretn´enk bontani a gr´afot. Az ´ıgy kapott part´ıci´oban a r´eszek megk¨ozel´ıt˝oleg azonos m´eret˝ uek lesznek, k¨ozt¨ uk pedig kev´es ´el megy.

3.5.

Egy numerikus p´ elda

Vizsg´aljuk meg egy kis” Cayley-gr´af expander-tulajdons´agait! ” 14. P´ elda. [kis kocka ´elgr´afja] A G = {Zn2 } csal´adb´ol v´alasszunk egy kis elemsz´am´ u csoportot: Z2 × Z2 × Z2 . Ez az F2 f¨ol¨otti 3-dimenzi´os vektort´er, ´ıgy rendje 23 = 8 lesz, elemei a 3 hossz´ us´ag´ u 0 − 1 vektorok. 24

Mivel a vektort´er dimenzi´oja 3, ez´ert a csoport gener´atorhalmaz´ahoz is 3 elemet v´alasztunk majd, legyen ez a szok´asos b´azis: a := (1, 0, 0),

b := (0, 1, 0),

c := (0, 0, 1)

A csoport prezent´aci´oja az S = {a, b, c} gener´atorral teh´at: ha, b, c | a2 , b2 , c2 , (ab)2 , (ac)2 , (bc)2 i A csoport Cayley-gr´afja ir´any´ıtatlan lesz, mivel minden gener´atorelem rendje 2. Az egyes gener´atorelemekhez rendelt sz´ınek: a piros, b k´ek, c z¨old sz´ın˝ u ´el [24].

A csoport szomsz´eds´agi m´atrixa ´ıgy a k¨ovetkez˝ok´eppen ´ırhat´o fel: 

0  1  0   1 A= 1   0  0  0

1 0 1 0 0 1 0 0

0 1 0 1 0 0 1 0

1 0 1 0 0 0 0 1

25

1 0 0 0 0 1 0 1

0 1 0 0 1 0 1 0

0 0 1 0 0 1 0 1

 0  0  0   1  1   0  1  0

Mivel minden cs´ ucs foka 3, a Laplace-m´atrix a k¨ovetkez˝o: 

 3 −1 0 −1 −1 0 0 0   −1 3 −1 0  0 −1 0 0    0 −1 3 −1 0  0 −1 0     −1 0 −1 3  0 0 0 −1  L= −1 0 0 0 3 −1 0 −1      0 −1 0  0 −1 3 −1 0   0  0 −1 0 0 −1 3 −1   0 0 0 −1 −1 0 −1 3 Minden cs´ ucs foka 3, ez´ert a normaliz´al´as sor´an minden sort ´es oszlopot v´egigosz” √ tunk” 3-mal. A normaliz´alt Laplace-m´atrix teh´at: 

 1 − 31 0 − 13 − 13 0 0 0  1  1 − 3 1 − 31 0  0 − 0 0 3    0 −1 1 −1 0  1 0 − 0   3 3 3  1  1 1 − 3 0 − 3 1  0 0 0 − 0 3  L = − 1 0 0 0 1 − 31 0 − 13   3    1 1 1  0 −3 0  0 − 1 − 0 3 3    0 0 − 31 1 − 13  0 − 31 0   1 1 1 0 0 0 −3 −3 0 −3 1 Az A szomsz´eds´agi m´atrix karakterisztikus polinomja: x8 − 12x6 + 30x4 − 28x2 + 9. A saj´at´ert´ekek ´es algebrai multiplicit´asuk egyszer˝ uen kisz´am´ıthat´o: x8 − 12x6 + 30x4 − 28x2 + 9 = (x − 1)3 (x + 1)3 (x − 3)(x + 3) λ1 λ2 = λ3 = λ4 λ5 = λ6 = λ7 λ8

= = = =

3 1 −1 −3

A legnagyobb saj´at´ert´ek λ1 = 3, hiszen a gr´af 3-regul´aris. A λ1 = −λ8 megfigyel´es

26

o¨sszhangban van azzal, hogy a gr´af p´aros. A saj´atvektoraira: Av = λv A vizsg´alt 3-regul´aris gr´afra L = D − A = 3I − A = 3v − λv = (3 − λ)v, ez´ert: Lv = (D − A)v = Dv − Av = 3Iv − Av = 3v − Av. Ez´ert pontosan az A m´atrix saj´atvektorai lesznek L saj´atvektorai is, a megfelel˝o λ saj´at´ert´ekekre pedig µ = 3 − λ saj´at´ert´ekeket fogunk kapni, vagyis: µ1 µ2 = µ3 = µ4 µ5 = µ6 = µ7 µ8

= = = =

0 2 4 6

A 0 saj´at´ert´ekhez a (1, 1, 1, 1, 1, 1, 1, 1)T vektor tartozik, ez az o¨sszes cs´ ucsot egy part´ıci´oba sorolja. A gr´af o¨sszef¨ ugg˝o, hiszen µ2 > 0 ´es a Laplace-m´atrix´anak legkisebb nemnulla saj´at´ert´eke a µ2 = 2, ez´ert a Fiedler-´ert´eke is 2. Mivel a 2 saj´at´ert´ek multiplicit´asa 3, ez´ert az ehhez tartoz´o saj´atvektorokhoz tartoz´o b´azis 3-elem˝ u: v1 = (1, 1, 1, 1, −1, −1, −1, −1)T v2 = (1, 1, −1, −1, 1, 1, −1, −1)T v3 = (1, −1, −1, 1, 1, −1, −1, 1)T Ezek a vektorok a kocka h´al´oj´at particion´alva tulajdonk´eppen k´et, szemk¨ozti lapot eredm´enyeznek part´ıc´ok´ent. A 4 saj´at´ert´ekhez a k¨ovetkez˝o saj´atvektorok ´altal gener´alt saj´atalt´er tartozik: u1 = (1, −1, 1, −1, 1, −1, 1, −1)T u2 = (1, 1, −1, −1, −1, −1, 1, 1)T u3 = (1, −1, −1, 1, −1, 1, 1, −1)T Ekkor az oszt´alyokba a kocka k´et, egym´assal szemk¨ozti ´el´enek cs´ ucsa fog ker¨ ulni. A legrosszabb part´ıci´ot a 6 saj´at´ert´ekhez tartoz´o (1, −1, 1, −1, −1, 1, −1, 1)T saj´atvektor adja, ez a kocka cs´ ucsaib´ol alkothat´o k´et diszjunkt szab´alyos tetra´edert eredm´enyezi oszt´alyokk´ent. 27

A csal´ad minden egyes gr´afja egy n-dimenzi´os hiperkocka h´al´ozat´at adja, ezekre is hasonl´o megfigyel´eseket tehet¨ unk a part´ıci´okkal kapcsolatban. A gr´af spektr´alis h´ezaga 4(G) = d − λ2 = 3 − 1 = 2 lesz. A gr´af izoperimetrikus sz´am´at egyszer˝ uen ki tudjuk sz´amolni. h(G) := min

|∂(S)| |S|

Itt S-t egyelem˝ unek v´alasztva |∂(S)| = 3 a regularit´as miatt. A legkisebb ´ert´eket akkor veszi fel, ha |S| = 4, hiszen ekkor a cs´ ucsok fel´et bev´alasztva ∂S = S lesz, ´ıgy h(G) = 1 ad´odik.

28

4. fejezet Elliptikus g¨ orb´ ek Sz´amegyenesen, s´ıkon, t´erben ´es t¨obbdimenzi´os terekben rengeteg csoportot tal´alhatunk. A csoportok strukt´ ur´aja f¨ ugg a testt˝ol, ami f¨ol¨otti vektort´erben dolgozunk, valamint a defini´alt csoportm˝ uvelett˝ol is. T¨obbnyire a komplex sz´amok ´es a kvaterni´ok multiplikat´ıv csoportja a´ltal meghat´arozott szorz´ast haszn´aljuk, lehet a m˝ uvelet a vektorok szok´asos o¨sszead´asa, de defini´alhatunk eg´eszen egyedi m˝ uveletet is, ami teljesen m´as strukt´ ur´at ´es ez´altal eg´eszen elt´er˝o r´eszcsoportokat fog eredm´enyezni. Ezen, sz´amunkra valami´ert ´erdekes r´eszcsoportokb´ol vizsg´alunk meg n´eh´any trivi´alisat, majd egy kev´esb´e k¨ozismert csoportstrukt´ ur´at az elliptikus g¨orb´ek seg´ıts´eg´evel.

4.1.

R´ eszcsoportok s´ıkban ´ es terekben

A kvaterni´ok (H, ·) csoportj´aban sok ´erdekes r´eszcsoportot tal´alunk. Maguk a kvaterni´ok egy n´egydimenzi´os vektorteret alkotnak R f¨ol¨ott. Vektort´erk´ent tekintve szok´asos b´azis a {1, i, j, k}, a sz´amol´asi szab´alyok pedig: i2 = j 2 = k 2 = ijk = −1. Szoros kapcsolat ´all fenn az u ´gynevezett Q kvaterni´ocsoporttal, mellyel a kvaterni´ok b˝ov´ıt´esk´ent az R(Q) form´aban ´ırhat´ok fel. A kvaterni´ocsoport egy regul´aris prezent´aci´oja hi, j|i4 , i2 j 2 , iji−1 j −1 i, ez a D4 di´edercsoport mellett a m´asik nem-kommutat´ıv 8 elem˝ u csoport. A kvaterni´ok legismertebb r´eszcsoportjai (R, ·) < (C, ·) < (H, ·). A kvaterni´ok multiplikat´ıv csoportja asszociat´ıv, C-vel ´es R-rel ellent´etben nem kommutat´ıv ´es a b´aziselemek ismeret´eben a disztributivit´asi szab´aly seg´ıts´eg´evel sz´am´ıthat´o ki az

29

elemek szorzata: (a1 + b1 i + c1 j + d1 k)(a2 + b2 i + c2 j + d2 k) = a1 a2 − b1 b2 − c1 c2 − d1 d2 +(a1 b2 + a2 b1 + c1 d2 − c2 d1 )i +(a1 c2 + a2 c1 − b1 d2 + b2 d1 )j +(a1 d2 + a2 d1 + b1 c2 − b2 c1 )k. A kvaterni´okon bevezetett norm´at a konjug´al´as seg´ıts´eg´evel ´ertelmezhetj¨ uk. A konjug´al´as defin´ıci´o szerint a + bi + cj + dk = a − bi − cj − dk ´es ´ıgy qq = qq. Ebb˝ol is l´atszik, hogy egy q ∈ H elem centraliz´atora: • ha q ∈ R, akkor CH (q) = H • ha q ∈ C, q ∈ / R, akkor CH (q) = C • ´es a´ltal´aban ha q = a1 +bi+cj +dk, akkor CH (q) = {a2 +λ(bi+cj +dk)|λ ∈ R} √ √ Egy q ∈ H elem norm´aja N (q) = qq = a2 + b2 + c2 + d2 , ez multiplikat´ıv: N (q1 q2 ) = N (q1 )N (q2 ). Az inverz elem is a norma seg´ıts´eg´evel ´ırjhat´o fel: q −1 = Nq(q) . Mivel a norma multiplikat´ıv, ez´ert a kvaterni´ok multiplikat´ıv csoportj´anak r´eszcsoportjaiban az elemek norm´ai is multiplikat´ıv csoportok alkotnak. A norma k´epz´ese ´ıgy egy homomorfizmus lesz: N : H → {R+ ∪ 0}. Ezek alapj´an r´eszcsoportot alkotnak az 1 norm´aj´ u elemek, az egys´egg¨omb felsz´ın´et alkot´o 4-dimenzi´os vektorok. Egy nagyobb r´eszcsoportot kapunk, ha egy tetsz˝oleges a ∈ R+ sz´amra tekintj¨ uk az d Sa := {q ∈ H : ∃d ∈ Z : N (q) = a } sz´amokat. Ezek pontosan azok a kvaterni´ok, amelyek norm´aja az a egy eg´esz kitev˝oj˝ u hatv´anya, vagyis a 4-dimenzi´os t´erben azon egys´egg¨omb¨ok, melyek sugara a-nak egy hatv´anya. Egy m´asik ´erdekes r´eszcsoport azon elemek halmaza, melyek egy adott q kvaterni´o eg´esz kitev˝oj˝ u hatv´anyai, vagyis Sq = {. . . , q −3 q −2 , q −1 , 1, q, q 2 , q 3 , . . . }. Egy hasonl´o, de folytonos r´eszcsoport azon kvaterni´okb´ol ´all, melyek egy adott q kvaterni´ora: Pq = {q d |d ∈ R}. Nyilv´an Sq < Pq ´es Sq ∼ = (Z, ·), valamint Pq ∼ = (R, ·). Ezek a csoportok a kvaterni´ok ter´eben spir´alokat rajzolnak ki, q ∈ C v´alaszt´assal pontosan a s´ık logaritmikus spri´aljait adj´ak. (Itt megjegyezz¨ uk, hogy ez csak N (q) 6= 1 eset´en van ´ıgy, N (q) = 1-re egy k¨ort kapunk.)

30

Ha m´ask´eppen defini´aljuk pontok (illetve helyvektoraik) szorzat´at, akkor m´as l´atv´anyos r´eszcsoportokat is kaphatunk. Ha az S = R × R s´ıkban a pontok szorzat´at (x1 , y1 ) · (x2 , y2 ) = (x1 x2 , y1 y2 ) defini´alja, akkor r´eszcsoportk´ent tekinthet¨ unk azon (x, y) pontokra, melyekre xy = 1. Ezek egy hiperbola pontjai, hiszen a defini´alt szorz´asra a hiperbola z´art. Itt az egys´eg az (1, 1) pont, m´asodrend˝ u a (−1, −1) pont ´es a pontok ´ıgy defini´alt szorz´asa Abel-csoportot hat´aroz meg. Ha azon pontokat tekintj¨ uk, melyekre xy = a 6= 0, akkor azon hiperbol´akb´ol fog a´llni a csoport, amelyekre xy = ad , ahol d eg´esz.

4.2.

Elliptikus g¨ orb´ ek

Az elliptikus g¨orb´ek olyan speci´alis g¨orb´ek a s´ıkon, amelyek pontjai (egy megfelel˝o m˝ uvelettel) egy Abel-csoportnak felelnek meg. Nagyon j´ol alkalmazhat´oak pr´ımtesztel´esre (ez elliptikus g¨orb´es pr´ımtesztek a leggyorsabbaknak sz´am´ıtanak), valamint elterjedt haszn´alatuk az elliptikus kriptogr´afiai rendszerekben [21] is. Tekints¨ unk egy K testet ´es f¨ol¨otte egy p(x0 , x1 , x2 ) ∈ K[x0 , x1 , x2 ] d-edfok´ u homog´en polinomot. Azt vizsg´aljuk, hogy a p(x0 , x1 , x2 ) = 0 egyenletnek van-e megold´asa a projekt´ıv s´ıkon. (Az egyszer˝ us´eg kedv´e´ert a K = R test f¨ol¨ott fogunk foglalkozni a g¨orb´ekkel.) Ha egy L test tartalmazza K-t, akkor p nullhelyeit tekinthetj¨ uk P2 (K) helyett a uletnek, amely jelen esetben P2 (L) projekt´ıv s´ıkon. Ezt nevezz¨ uk a H p (L) hiperfel¨ projekt´ıv s´ıkbeli g¨orbe lesz. 49. Defin´ıci´ o. [szingularit´as] Nem-szingul´aris pontoknak nevezz¨ uk azon

31

a ∈ H p (L) pontokat, melyek nem egyidej˝ u megold´asai a k¨ovetkez˝o egyenleteknek: ∂0 p = 0,

∂1 p = 0,

∂2 p = 0

Ekkor a p g¨orbe a pontbeli ´erint˝oegyenes´enek egyenlete: ∂0 p(a)x0 + ∂1 p(a)x1 + ∂2 p(a)x2 = 0 A p(x0 , x1 , x2 ) = 0 egyenlet˝ u g¨orbe nem-szingul´aris, ha minden pontja nem-szingul´aris. Egy nem-szingul´aris harmadfok´ u homog´en p(x0 , x1 , x2 ) ∈ K[x0 , x1 , x2 ] polinom egy elliptikus g¨orb´et defini´al, ha van legal´abb egy racion´alis pontja. uen E(L)-lel jel¨olj¨ uk. Ha L b˝ov´ıt´ese K-nak, akkor a H p (L) g¨orb´et egyszer˝ Ha a K test karakterisztik´aja nem 2 vagy 3, akkor igazolhat´o, hogy minden K f¨ol¨otti elliptikus g¨orbe ´atalak´ıthat´o a k¨ovetkez˝o alak´ uv´a: x0 x22 = x31 + ax20 x1 + bx30 ,

a, b ∈ K

Ennek a g¨orb´enek pontosan egy pontja van a v´egtelenben: (0, 0, 1) ∈ P2 (K). Ezt a pontot fogjuk ∞-nel jel¨olni. ´ erhet¨ Att´ unk x0 6= 0 eset´en affin koordin´at´akra (x = x1 /x0 ´es y = x2 /x0 ), ´ıgy a g¨orbe egyenlet´enek R2 -beli egyenlet´et kapjuk: y 2 = x3 + ax + b Hat´arozzuk meg, hogy mikor lesz a defini´alt g¨orbe nem-szingul´aris! A p(x0 , x1 , x2 ) = x0 x22 − x31 − ax21 x1 − bx30 g¨orbe pontosan akkor szingul´ars, ha a diszkrimin´ansa, 4 = −16(4a3 + 27b2 ) = 0, vagyis p pontosan akkor lesz elliptikus g¨orbe, ha 4 = 6 0. A val´os sz´ams´ıkon 4a3 + 27b2 = 0 param´eterv´alaszt´assal 4 = 0 lesz, ´ıgy egy szingul´aris g¨orb´et kapunk, egy´ebk´ent elliptikus g¨orb´eket. A 4 diszkrimin´ans el˝ojel´et˝ol f¨ ugg a komponensek sz´ama: ha 4 > 0, akkor a g¨orbe k´et komponensb˝ol ´all, 4 < 0 eset´en pedig egy o¨sszef¨ ugg˝o komponenst kapunk.

32

Az ´abr´akon l´athat´o n´eh´any elliptikus g¨orbe (´es k´et, nem elliptikus g¨orbe is) a k¨ovetkez˝o param´eterv´alaszt´assal: q q Az els˝o ´abr´an a = −2 b = −2, −1, 0, 1, 23 · 43 , 2, ´ıgy b = ± 23 · 43 eset´en a g¨orbe szingul´aris lesz, itt a g¨orbe a´tmetszi ¨onmag´at. A m´asodik ´abr´an a = 0 b = −2, −1, 0, 1, 2. az a = 0, b = 0 param´eterv´alaszt´as j´ol l´athat´oan a (0, 0) szingul´aris pontot eredm´enyezi.

4.3.

Az elliptikus g¨ orb´ ek csoporttulajdons´ aga

Egy kiv´alasztott elliptikus g¨orbe pontjain bevezetj¨ uk az o¨sszead´as (+) m˝ uveletet egy v´egtelenbeli pont hozz´av´etel´evel a k¨ovetkez˝ok´eppen: 50. Defin´ıci´ o. [¨osszead´as] A g¨orbe P ´es Q pontjainak ¨osszege annak az R pontnak az R0 inverze, amely a P -n ´es Q-n ´atmen˝o e egyenes ´es a g¨orbe harmadik” ” metsz´espontja a k¨ovetkez˝ok´eppen: • ha az e egyenes h´arom k¨ ul¨onb¨oz˝o pontban metszi a p g¨orb´et, akkor R a P -t˝ ol ´es Q-t´ol k¨ ul¨onb¨oz˝o metsz´espont (P + Q + R = 0) • ha e ´erinti a g¨orb´et ´es P = 6 Q, akkor R az ´erint´esi pont (´es ez´altal vagy P -vel, vagy Q-val egybeesik) (P + Q + Q = 0) • ha P 6= Q ´es e p´arhuzamos az y tengellyel, akkor R = 0 a v´egtelenbeli pont (P + Q + 0 = 0) • ha P = Q ´es e p´arhuzamos az y tengellyel, akkor R = 0 (P + P + 0 = 0).

33

´ ıt´ 3. All´ as. [csoporttulajdons´agok] A p elliptikus g¨orbe pontjai az ´ıgy defini´alt ¨osszead´asra n´ezve csoportot alkotnak. Bizony´ıt´ as. • az ¨osszead´asra n´ezve trivi´alisan z´art • az egys´egelem a v´egtelenbeli 0 pont • P pont inverze a rajta ´atmen˝o, y tengellyel p´arhuzamos egyenes ´es a p g¨orbe metsz´espontja • az asszociativit´ast neh´ez feladat bel´atni, ez´ert most csak bizony´ıt´as n´elk¨ ul mondjuk ki  Az ´ıgy defini´alt o¨sszead´asr´ol k¨onny˝ u l´atni, hogy kommutat´ıv, hiszen sehol nem haszn´altuk ki P ´es Q sorrendj´et. A p elliptikus g¨orbe pontjai teh´at Abel-csoportot alkotnak az ¨osszead´asra n´ezve. Az elliptikus g¨orbe racion´alis pontjai r´eszcsoportot alkotnak a defini´alt csoportban, ezt a tulajdons´agot haszn´alj´ak ki a kriptogr´afiai ´es pr´ımfaktoriz´aci´os alkalmaz´asokban. A r´eszcsoport m´aveleti z´arts´ag´at az a meggondol´as eredm´enyezi, hogy ha egy val´os egy¨ utthat´os harmadfok´ u polinomnak l´etezik k´et racion´alis megold´asa, akkor a harmadik megold´asnak is racion´alisnak kell lennie. 34

K¨ osz¨ onetyilv´ an´ıt´ as Ez´ uton szeretn´ek k¨osz¨onetet mondani t´emavezet˝omnek, K´arolyi Gyul´anak, aki az ¨otletem alapj´an seg´ıtett kiv´alasztani a dolgozatomban t´argyalt t´em´akat. K¨ ul¨on h´al´as vagyok neki dolgozatom lektor´al´as´a´ert ´es a tan´acsok´ert, o¨tletek´ert. K¨osz¨on¨om Szab´o Endre t¨ urelmes ´es alapos munk´aj´at, ami´ert megismertetett a csoportelm´elet alapjaival ´es sz´eps´egeivel. Szeretn´em k¨osz¨onetemet kifejezni csal´adomnak ´es k¨ozeli bar´ataimnak a t¨ urelem´ert ´es t´amogat´as´ert, amit tanulm´anyaim sor´an ny´ ujtottak, valamint ami´ert mellettem a´lltak ´es biztattak.

35

Irodalomjegyz´ ek ´ szlo ´ : Automorphism groups, isomorphism, reconstruction (Hand[1] Babai La book of Combinatorics), 1994 [2] Bjorn Poonen: Elliptic curves, 2008 [3] Bojan Mohar: The Laplacian Spectrum of Graphs (Graph Theory, Combinatorics, and Applications), 1991 ´ sz, V.T. So ´ s and K. Vesztergombi: [4] C. Borgs, J. Chayes, L. Lova Counting Graph Homomorphisms, in: Topics in Discrete Mathematics, (ed. M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas, P. Valtr), Springer, 2006 [5] Dietrich Kuske, Markus Lohrey: Logical Aspects of Cayley-Graphs: The Group Case (Annals of Pure and Applied Logic), 2005 ´: Pell’s Equation, The IMO Compendium, 2007 [6] Dusan Djukic [7] Fan R. K. Chung: Spectral Graph Theory (CBMS Regional Conference Series in Mathematics), Universtiy of Pennsylvania, Philadelphia, 1997 [8] Hendrik W. Lenstra, JR.: Solving the Pell equation, 2008 [9] Harry Polard, Harold G. Diamond: The Theory of Algebraic Numbers, The Mathematical Association of America, 1975 ˇ ic ´: Hamiltonian Paths in Cayley Graphs, Elsevier, [10] Igor Pak, Rados Radoic 2004 [11] J. Cheeger: A lower bound for the smallest eigenvalue of the Laplacian, Princeton Univ. Press, Princeton, 1970

36

[12] Kenneth Ireland, Michael Rosen: A Classical Introduction to Modern Number Theory (Graduate Texts in Mathematics Vol; 84) , Springer-Verlag, New York Heidelberg Berlin, 1982 ´ sz: Combinatorial structures and their applications, Gordon and [13] L. Lova Breach, New York, 1970 [14] P. Buser: A note on the isoperimetric constant (Annales Scientifiques de ´ l’Ecole Normale Sup´erieure), 1982 ´ ´ n Jo ´ zsef, Gro ¨ ller Akos: [15] Pelika Algebra jegyzet, http://www.cs.elte.hu/∼pelikan/algebra.html, 2000 [16] Robert B. Ash: Algebraic Number Theory, http://www.math.uiuc.edu/~r-ash/ANT.html [17] Sheldon B. Akers, Balakrishnan Krishnamurthy: A Group-Theoretic Model for Symmetric Interconnection Networks, 1989 [18] http://en.wikipedia.org/wiki/Group_(mathematics) [19] http://en.wikipedia.org/wiki/Rank_of_an_abelian_group [20] http://dimax.rutgers.edu/~alexo/zemor.pdf [21] http://hg8lhs.ham.hu/titkositas/ecc1.pdf [22] http://homepage.mac.com/ehgoins/ma553/lecture_20.pdf [23] http://math.mit.edu/~spielman/PAPERS/expandersIT.pdf [24] http://mathworld.wolfram.com/CayleyGraph.html [25] http://www.math.uwo.ca/~srankin/courses/403/2004/ fund-theorem-abelian-groups.pdf [26] http://www.math.ias.edu/~boaz/ExpanderCourse/lecture02.ps [27] http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf

37

Nyilatkozat

N´ev: Harkai Alexandra D´ora ELTE TTK, Matematika B.Sc. szak, Matematikai elemz˝o szakir´any ETR azonos´ıt´o: HAANAAT.ELTE Szakdolgozat c´ıme: Csoportok a matematika k¨ ul¨onb¨oz˝o ter¨ uletein

A szakdolgozat szerz˝ojek´ent fegyelmi felel˝oss´egem tudat´aban kijelentem, hogy a dolgozatom o¨n´all´o munk´am eredm´enye, saj´at szellemi term´ekem, abban a hivatkoz´asok ´es id´ez´esek standard szab´alyait k¨ovetkezetesen alkalmaztam, m´asok ´altal ´ırt r´eszeket a megfelel˝o id´ez´es n´elk¨ ul nem haszn´altam fel.

Budapest, 2010. j´ unius 1.

Harkai Alexandra D´ora

38