PRÍMEK, POLIGNAC, POLYMATH

PRÍMEK, POLIGNAC, POLYMATH HARCOS GERGELY

1. Hal´ asz´ as a pr´ımekre A pr´ımsz´ amok rejtélyes viselkedése és a matematikában betöltött központi szerepe az ókori id˝ ok óta foglalkoztatja az embereket. Az elm´ ult 10 évben több rendk´ıv¨ uli átt¨ orést láttunk ezen a ter¨ uleten, amik korábban elérhetetlennek t˝ untek [10, 8, 32, 14, 6, 15, 7]. Ebben a cikkben az ikerpr´ımsejtés kör¨ uli izgalmas fejleményekre koncentr´ alunk, hangs´ ulyozva a tételek mögötti alapgondolatokat. Euklidész m´ ar az Elemek c´ım˝ u m˝ uvében (IX. könyv, 20. áll´ıtás) le´ırta a mindannyiunk által tanult bizony´ıt´ ast, miszerint végtelen sok pr´ımszám van. A szomszédos pr´ımsz´ amok k¨ oz¨ otti t´ avolságok az els˝o k¨ ulönbségt˝ol eltekintve párosak, és tal´ an m´ ar Euklidész megfigyelte, hogy ez a k¨ ulönbség gyakran 2, legalábbis a sorozat elején: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), . . . Az ilyen pr´ımeket ikerpr´ımeknek nevezz¨ uk, és azt sejtj¨ uk, hogy végtelen sok van bel˝ ol¨ uk: Ikerpr´ımsejt´ es. A p − p′ = 2 egyenletnek végtelen sok megoldása van pr´ımekben. ´ Altal´ anosabban, Polignac [19] azt sejtette, hogy minden páros szám végtelen sokszor el˝ ofordul két szomszédos pr´ımszám közötti távolságként, ami motiválja a k¨ ovetkez˝ o fogalmat. 1. defin´ıci´ o. A d pozit´ıv egészt Polignac-sz´ amnak nevezz¨ uk, ha a p − p′ = d egyenletnek végtelen sok megold´ asa van pr´ımekben. A Polignac-számok halmazát jelölje D. A defin´ıci´ oban nem k¨ ovetelj¨ uk meg, hogy p és p′ szomszédos pr´ımszámok legyenek. Polignac sejtéséb˝ ol k¨ ovetkezik, hogy D a pozit´ıv páros számok halmaza, de egészen tavalyig azt sem tudtuk, hogy D nem u ¨res-e. 1. t´ etel (Zhang [32]). Létezik Polignac-szám, azaz D ̸= ∅. A tétel bizony´ıt´ asa a probléma egy u ´jszer˝ u megközel´ıtésén alapul, amit eredetileg Goldston, Pintz, Yıldırim [8] fejlesztett ki Heath-Brown [12] egy korábbi 1

ötletére alapozva. A klasszikus megközel´ıtésben egy konkrét d pozit´ıv páros számról (pl. d = 2) igyeksz¨ unk kimutatni, hogy Polignac-szám, azaz hogy végtelen sok n pozit´ıv egészre az n és az n + d is pr´ımszám. Felfoghatjuk ezt egyfajta pr´ımhalász´ asnak, amiben két kézzel – amik adott távolságra vannak egymástól – próbálunk két pr´ımet fogni u ´gy, hogy az egész számok k¨ ulönböz˝o helyein próbálkozunk. A [8] cikk alap¨ otlete, hogy a pr´ımhalászást ne puszta kézzel, hanem halászhálóval – egy H véges halmaz eltoltjaival – végezz¨ uk. Ezáltal jobb esély¨ unk van arra, hogy két egym´ ashoz k¨ ozeli pr´ımet fogjunk, de cserébe azok távolsága már nem egy konkrét d lesz, hanem a H -ban fellép˝ o k¨ ulönbségek egyike. A [8] cikk központi észrevétele, hogy a pr´ımsz´ amoknak bizonyos maradékosztályokban való nagyon egyenletes eloszl´ asa mellett a v´ azolt pr´ımhalászás hatékonnyá tehet˝o. Motohashi és Pintz [16] a sz¨ ukséges hipotézist jelent˝ osen gyeng´ıtette, és Zhang [32] ezt bizony´ıtotta brav´ urosan. Az 1. tétel szenz´ aci´ os bejelentését követ˝oen Terence Tao vezetésével elindult a Polymath8 elnevezés˝ u internetes kutatási projekt, amibe bárki szabadon bekapcsol´ odhatott, pl. magyar részr˝ol Pintz János mellett a szerz˝o is részt vett benne. A projekt célja Yitang Zhang munkájának megértése, elemzése és a kvantitat´ıv aspektusainak optimaliz´ al´ asa volt – ennek eredményeit a [20] cikk tartalmazza. Id˝ ok¨ ozben – u ´jabb dr´ amai fordulatként – Heath-Brown fiatal tan´ıtványa, James Maynard tov´ abbfejlesztette a [8]-ban szerepl˝o szitát – tehát hogy hol érdemes kivetni a h´ al´ ot –, és ez´ altal a [16]-ban megfogalmazott egyenletes eloszlási hipotézisre sem volt sz¨ uksége. Ily módon Maynard [14] u ´j bizony´ıtást adott a Zhang-tételre, s˝ot azt is bel´ atta, hogy kell˝ oen nagy halászhálóval ak´ armilyen el˝o´ırt véges szám´ u pr´ımet foghatunk, nem csak kett˝ ot. Hasonló észrevételeket tett a blogján Tao is [29], majd a Polymath8 projekt folytat´ odott a Maynard–Tao-tétel továbbfejlesztésével [21].

2. Milyen h´ al´ oval hal´ asszunk? Az 1. tétel bizony´ıt´ as´ anak alap¨ otlete a [8] cikkben szerepel: 1. ¨ otlet. Legyen H = {h1 , . . . , hk } egy egész számokból álló k elem˝ u halmaz. Pr´ ob´ aljunk végtelen sok n pozit´ıv egészt találni u ´gy, hogy az n + H = {n + h1 , . . . , n + hk } eltolt halmaz minél t¨ obb pr´ımet tartalmazzon. A szakirodalomban val´ oban a H jelölés terjedt el a fenti halmazra, ezért a halászh´ al´ o metafora t¨ obbsz¨ or¨ osen helyénvalónak t˝ unik. A továbbiakban az elemeket nagys´ agrendi sorrendben sz´ amozzuk: h1 < . . . < hk . Persze rögtön látjuk, hogy nem minden k elem˝ u halmaz felel meg egyaránt a pr´ımhalászás céljára. Pl. a k = 2 esetben H = {0, 1} eleve rossz, mert n és n + 1 köz¨ ul az egyik mindig páros, tehát n > 2 esetén csak az egyik¨ uk lehet pr´ım. A H = {0, 2} jobb ebb˝ol a szempontból, hiszen az ikerpr´ımsejtés szerint n és n + 2 egyszerre pr´ım végtelen sok n-re. Hasonlóan, a k = 3 esetben a 2 és a 3 szerinti maradékokat nézve látjuk, hogy H = {0, 2, 3} vagy H = {0, 2, 4} nem kifejezetten jó háló gyanánt, hiszen ezek eltoltjaiban legfeljebb csak két pr´ım van, ha n > 3. Ellenben a H = {0, 2, 6} eltoltjaira nem tudunk semmiféle okot, ami megakad´ alyozná, hogy mindhárom eleme pr´ım legyen végtelen sokszor. Ez motiválja az al´ abbi fogalmat. 2

2. defin´ıci´ o. A H = {h1 , . . . , hk } egész számokból álló k elem˝ u halmaz megengedett, ha semmilyen m ≥ 2 egészre nézve nem tartalmaz teljes maradékrendszert. Persze r¨ ogt¨ on l´ atjuk, hogy ha egy k elem˝ u H halmaz tartalmaz teljes maradékrendszert valamilyen m ≥ 2 egészre nézve, akkor m ≤ k, vagyis H tartalmaz teljes maradékrendszert valamilyen p ≤ k pr´ımszámra nézve is – nevezetesen az m b´ armely pr´ımoszt´ oj´ ara nézve. Tehát a fenti defin´ıcióban nem veszt¨ unk semmit, ha feltessz¨ uk, hogy m ≤ k pr´ımsz´ am. Ez mutatja, hogy minden k-ra van megengedett k elem˝ u halmaz, pl. a k ut´ ani els˝o k darab pr´ımszám halmaza. Az 1. ¨ otletnek komoly t´ amogatást ad Dickson [2] egy sejtése, illetve annak Hardyt´ ol és Littlewoodt´ ol sz´ armazó kvantitat´ıv formája [11]: Dickson–Hardy–Littlewood-sejt´ es. Legyen H egy megengedett halmaz. Ekkor végtelen sok n pozit´ıv egészre az n + H eltolt halmaz minden eleme pr´ımszám. A sejtés persze nem mondja meg, az n-et miként válasszuk meg, hogy az n + H ar csak két eleme pr´ım legyen. A metaforánkkal élve: hiába összes eleme, vagy ak´ van h´ al´ onk, ha nem tudjuk, hova vess¨ uk ki, tehát hol gazdag halban a v´ız. Pl. ha az n-et valamilyen nagy x k¨ or¨ ul az egyenletes eloszlás szerint véletlenszer˝ uen választjuk, akkor az n + H halmazba átlagosan csak kb. |H |/ log x pr´ımszám fog esni, mert ebben a tartom´ anyban átlagosan kb. log x távolságra vannak a pr´ımszámok egym´ ast´ ol. Teh´ at ha x nagy, akkor ezen a naiv módon átlagosan közel nulla darab pr´ımet fogunk kihal´ aszni, nemhogy kett˝ot vagy többet. Itt és a továbbiakban log x a természetes logaritmust jelöli, az analitikus számelméletben megszokott m´ odon. Az n u alaszt´ asával, avagy a rossz n-ek kiszitálásával” kell ellen¨gyes megv´ ” s´ ulyozni azt a tényt, hogy a pr´ımszámok sorozata egyre ritkul. Ennek módja már Goldston, Pintz, Yıldırim [8] cikkében szerepel, de Zhang [32] bizony´ıtotta el˝oször, hogy ´ıgy legal´ abb két pr´ımsz´ am garantálható egy alkalmas megengedett halmaz végtelen sok eltoltj´ aban. Maynard [14] még u ¨gyesebben szitálja az n-et, ami által ak´ ar sz´ az pr´ımet is tud garant´ alni végtelen sok n + H alak´ u eltoltban. 2. t´ etel (Zhang [32]). Létezik egy k pozit´ıv egész az alábbi tulajdonsággal. Ha H egy k elem˝ u megengedett halmaz, akkor végtelen sok n pozit´ıv egészre az n + H eltolt halmazba legal´ abb két pr´ımszám esik. A tételb˝ ol azonnal k¨ ovetkezik, hogy ha H = {h1 , . . . , hk } egy megfelel˝o halmaz, akkor a fellép˝ o hj − hi (i < j) k¨ ulönbségek egyike Polignac-szám, hiszen n + hi és n + hj k¨ ul¨ onbsége hj − hi . Tehát ha az a cél, hogy D-ben minél kisebb elem létezését garant´ aljuk, akkor a tételbeli H -t kell minél kisebb átmér˝oj˝ unek választani. Ehhez els˝ o lépésben a tételbeli k-t kell minimalizálni, majd ahhoz kell megtalálni a legjobb H -t. Ilyen t´ıpus´ u optimalizálással telt a Polymath8 projekt jelent˝os része [20, 21]. Az al´ abbi t´ abl´ azatban összefoglaljuk, hogy az 1-2. tételek numerikus vari´ ansai miként fejl˝ odtek. A t´ abl´ azat utols´ o sora szerint van egy 50 elem˝ u H ⊂ {0, 2, . . . , 246} megengedett halmaz, aminek eltoltjaiban végtelen sokszor található két pr´ımszám. Az 50 elem részletesen fel van sorolva a [21] cikk 76. oldalán. Tehát D-ben mindenképpen van legfeljebb 246 nagys´ ag´ u páros szám, de konkrét elemet megnevezni nem 3

min D ≤

forr´ as

k=

Zhang [32]

3.5 × 10

Polymath8a [20]

632

4680

Maynard [14]

105

600

Polymath8b [21]

50

246

6

7 × 107

tudunk. Ilyen konkrét elem megtalálása a jelenlegi módszerekkel reménytelennek t˝ unik: a probléma val´ osz´ın˝ uleg az ikerpr´ımsejtéssel megegyez˝o nehézség˝ u. Mindazon´ altal a D-r˝ ol a fenti eredmények jóval többet elmondanak, amint az a következ˝o fejezetb˝ ol kider¨ ul.

3. A Polignac-sz´ amok s˝ ur˝ us´ ege Pintz J´ anos ismerte fel a 2. tétel azon következményét, hogy a Polignac-számok a természetes számok egy – csak a k-tól f¨ ugg˝o – pozit´ıv hányadát elfoglalják, tov´ abb´ a a szomszédos Polignac-számok közötti távolság korlátos. Az eredményt a k¨ ozelm´ ultban finom´ıtotta Granville, Kane, Koukoulopoulos, Lemke Oliver, és mi ebben a form´ aban mondjuk ki és bizony´ıtjuk. 3. t´ etel (Pintz et al. [18, 9]). Végtelen sok Polignac-szám létezik. Pontosabban: (a) A D ⊂ N halmaz aszimptotikus alsó s˝ ur˝ usége ( ) 1 ∏ 1 d(D) ≥ 1− , k−1 p p≤k

ahol k mint a 2. tételben, és a szorzás a pr´ımeken fut végig. (b) Létezik m ∈ N u ´gy, hogy minden n ∈ N esetén D ∩ {n, n + 1, . . . , n + m} = ̸ ∅. Bizony´ıt´ as. A jelzett becslés a k csökkentésével er˝osödik, ezért feltehet˝o, hogy k a legkisebb egész, ami a 2. tételbeli áll´ıtást kielég´ıti. Ekkor persze k ≥ 2, és a feltétel szerint létezik egy k − 1 elem˝ u H = {h1 , . . . , hk−1 } megengedett halmaz, aminek n + H eltoltj´ aban legfeljebb csak egy pr´ımszám van, ha n kell˝oen nagy. Legyen most h > hk−1 olyan H ∪ {h} egy k elem˝ u megengedett halmaz, ekkor ( egész, amivel ) végtelen sok n + H ∪ {h} eltoltban található két pr´ımszám. A H tulajdonsága miatt sz¨ ukségszer˝ u, hogy valamilyen 1 ≤ j ≤ k − 1 indexre és végtelen sok n-re az n + hj és az n + h egyszerre pr´ım, vagyis h − hj ∈ D. A h > hk−1 egészre tett feltevés csak annyi megk¨ otést jelent, hogy ha egy p ≤ k pr´ımszámra nézve H mod p m´ ar tartalmaz p − 1 k¨ ulönböz˝o maradékot, akkor h mod p is ezen p − 1 marad´ e kok egyike kell, hogy legyen. A k´ınai marad´ ∏ ∏ ektétel alapján tehát megadható (p − 1) darab marad´ e koszt´ a ly modulo ´gy, hogy ha h > hk−1 ezek p≤k p≤k p u uni´ oj´ ab´ ol val´ o, akkor a h − h1 , . . . , h − hk−1 k¨ ulönbségek egyike Polignac-szám. Innen m´ ar k¨ onny˝ u meggondol´ ∏ assal következik az (a) és a (b) áll´ıtás, pl. az utóbbiban vehet˝ o m := hk−1 − h1 + p≤k p. 4

Ahogy a [9] cikk szerz˝ oi is megjegyzik, az (a) áll´ıtásban vehet˝o a már igazolt 1 k = 50 érték [21], és ezzel a d(D) > 354 becslést kapjuk a Polignac-számok aszimptotikus als´ o s˝ ur˝ uségére. Teh´ at átlagosan minden 354 egymás utáni számra jut egy Polignac-sz´ am, m´ıg az els˝ o Polignac-szám legfeljebb 246. Ezzel szemben a szomszédos Polignac-sz´ amok k¨ oz¨ otti legnagyobb távolságra a fentihez hasonló formális érveléssel nem tudunk konkrét értéket szolgáltatni, aminek oka a következ˝o. Adott M pozit´ıv egészre van olyan E ⊂ N halmaz, amiben az M végtelen sokszor fellép két szomszédos elem t´ avols´ agaként, miközben bármely megengedett {h1 , h2 , h3 } h´ armas esetén az E tartalmazza a h2 − h1 , h3 − h2 , h3 − h1 k¨ ulönbségek egyikét. Pl. E -nek vehetj¨ uk azon természetes számok halmazát, amik modulo 3M kongruensek egy legfeljebb M abszol´ ut érték˝ u egész számmal. Tehát ha a 2. tételb˝ol csak annyit haszn´ alunk fel, hogy minden k elem˝ u megengedett H halmazra a D tartalmazza két H -beli elem k¨ ul¨ onbségét, akkor még k = 3 esetén is szóba jön a D = E lehet˝ oség, amikor is a (b) áll´ıt´ as csak m ≥ M mellett igaz.

4. A hal´ asz´ as m˝ uv´ eszete Mint l´ attuk, a 2. tételb˝ ol k¨ ovetkezik az 1. tétel, illetve sok egyéb értékes információ a Polignac-sz´ amok eloszl´ as´ ara vonatkozóan. A 2. tétel bizony´ıtásának alapötlete szintén a [8] cikkben szerepel, és elnagyoltan annyit tesz, hogy megpróbáljuk el˝ore megtippelni, hogy mely n + H alak´ u eltolt halmazokban várható az átlagosnál jóval t¨ obb pr´ımsz´ am. Ezt jól csinálni egyfajta m˝ uvészet, hiszen egyens´ ulyozni kell ak¨ oz¨ ott, ami igaz és amit bizony´ıtani tudunk. Ha t´ ul direkt módon választjuk ki a potenci´ alisan jó eltoltakat, akkor a várakozásunkat nem fogjuk tudni igazolni, ha pedig t´ ul megenged˝ oek vagyunk, akkor az eltoltakba nem esik majd elég pr´ımszám. Form´ alisan az 1. ¨ otlet egy val´ osz´ın˝ uségi finom´ıtásáról van szó: 2. ¨ otlet. Legyen H = {h1 , . . . , hk } egy k elem˝ u megengedett halmaz. Minden elég nagy x > 0 sz´ amra tal´ aljunk olyan valósz´ın˝ uségi mértéket az x ≤ n ≤ 2x egészeken, amire nézve az n + H = {n + h1 , . . . , n + hk } eltolt halmazba es˝o pr´ımek számának várhat´ o értéke egynél nagyobb. A gyakorlatban ez annyit tesz, hogy olyan ν(n) ≥ 0 s´ ulyokat keres¨ unk, amikre bizony´ıthat´ oan fenn´ all (1)

∑ x≤n≤2x

ν(n)

k ∑ i=1

1n + hi

pr´ım

>

∑

ν(n).

x≤n≤2x

Vegy¨ uk észre, hogy az egyenl˝ otlenség csak u ´gy teljes¨ ulhet, ha a jobb oldali összeg pozit´ıv, és akkor ezzel az ¨ osszeggel leosztva a ν(n) s´ ulyok egy valósz´ın˝ uségi mértékké norm´ al´ odnak. Az egyenl˝ otlenségb˝ol következik, hogy valamilyen x ≤ n ≤ 2x egészre a bels˝ o¨ osszeg egynél nagyobb, tehát az n + H eltolt halmazba legalább két pr´ımsz´ am esik. Ha ez minden elég nagy x > 0 számra fennáll, akkor a 2. tételbeli áll´ıt´ as igaz a H -ra. A s´ ulyokat u ´gy érdemes megválasztani, hogy ν(n) várhatóan akkor legyen nagy, amikor az n + h1 , . . . , n + hk számok között sok a pr´ım, vagy legalábbis kevés 5

pr´ımoszt´ ojuk van egy¨ uttesen. A legnaivabb választást a már eml´ıtett Dickson– Hardy–Littlewood-sejtés adja: ν(n) := 1n + h1 , . . . , n + hk

pr´ım .

Ezek a s´ ulyok a gyakorlatban nemigen haszn´ alhatók, mert ha tudnánk, hogy az (1) jobb oldala minden elég nagy x-re pozit´ıv, akkor rögtön a Dickson–Hardy– Littlewood-sejtést is igazoltuk volna. Vezess¨ uk be a P (n) := (n + h1 ) . . . (n + hk ) jel¨ olést, ekkor a [8]-beli s´ ulyokhoz közelebb álló, de még mindig naiv változat a ν(n) := 1P (n) pr´ımosztóinak száma legfeljebb k + ℓ , ahol 0 ≤ ℓ ≤ k egy szabadon v´ alasztható paraméter. Ennek egy analitikus variánsa ( ) ∑ P (n) (2) ν(n) := µ(d) logk+ℓ , d d|P (n)

ahol a µ(d) u ń. M¨ obius-f¨ uggvény a logikai-szitából jól ismert ±1 s´ ulyok megjelenése a pr´ımsz´ amok elméletében (v¨ o. Eratosztenész-szita):   ulönböz˝o pr´ımszám szorzata; +1, ha d páros sok k¨ µ(d) := −1, ha d páratlan sok k¨ ulönböz˝o pr´ımszám szorzata;   0, ha d nem négyzetmentes. Nem trivi´ alis, de a (2)-beli s´ ulyokra teljes¨ ul ( ) 0 ≤ ν(n) ≤ logk+ℓ P (n) , tov´ abb´ a ν(n) akkor és csak akkor pozit´ıv, ha P (n) k¨ ulönböz˝o pr´ımosztóinak száma legfeljebb k + ℓ. Goldston, Pintz, Yıldırım [8] és ezáltal Zhang [32] sikere nagy részben a (2)-beli naiv s´ ulyok egy megfelel˝ o finom´ıtásán m´ ulik, ami lehet˝ové teszi az (1) két oldalának aszimptotikusan pontos kisz´ am´ıtását. A finom´ıtás Selberg [25] u ´ttör˝o munkájának gy¨ um¨ olcse, amit a [8] mer˝ oben u ´jszer˝ u módon használ, bár a szerz˝ok elismerik, hogy az o ¨tlet részben Heath-Browntól [12] származik. A Selberg-szita abból indul ki, hogy ne az o ¨sszes, hanem csak a d ≤ R feltételt kielég´ıt˝o négyzetmentes számokkal szit´ aljunk, ahol R egy szabadon választható levágási paraméter”. A d ≤ R ” megszor´ıt´ assal a s´ ulyok nemnegativitása már nehezen garantálható, ezért azokat még négyzetre is emelj¨ uk. A [8, 32] dolgozatokban konkrétan használt s´ ulyf¨ uggvény ( (3)

ν(n) :=

∑ d|P (n)

6

( µ(d) logk+ℓ +

R d

) )2 ,

ahol R := xθ/2 valamilyen r¨ ogz´ıtett θ > 0 mellett. Itt log+ t := max(log t, 0), tehát az ¨ osszegben csak a d ≤ R osztók vesznek részt. Ezeket a s´ ulyokat érdemes megszor´ıtani azokra az n-ekre, amikre P (n) mentes a nagyon kicsi pr´ımosztóktól. Ennek egyik oka, hogy az ilyen n-ekre az n + h1 , . . . , n + hk tényez˝ok páronként relat´ıv pr´ımek, másrészt ´ıgy az (1) két oldalának aszimptotikus kiszám´ıtásában a kis pr´ımekb˝ ol sz´ armaz´ ou ń. lok´ alis faktorok elhagyhatók. Mi a továbbiakban feltessz¨ uk, hogy P (n) minden pr´ımoszt´ oja legalább log log log x, a többi n-re a ν(n)-t nullának vessz¨ uk. A (3)-beli s´ ulyf¨ uggvény egy arányossági tényez˝ot˝ol eltekintve nem más, mint ( ( )k+ℓ )2 ∑ log d (4) ν(n) := µ(d) 1 − , log R + d|P (n)

ahol értelemszer˝ uen (1 − t)+ := max(1 − t, 0). Egy fontos általános´ıtást javasolt és vizsg´ alt el˝ osz¨ or Soundararajan [27, 28]: ( ( ) )2 ∑ log d (5) ν(n) := µ(d)g , log R d|P (n)

ahol g : R → R egy kell˝ oen sima f¨ uggvény, ami a [0, 1] intervallumon k´ıv¨ ul nulla. Ezek az által´ anosabb s´ ulyok lehet˝ové tették a [8, 32]-beli eredmények jelent˝os éles´ıtését [5, 20], és megnyitott´ ak az utat az u ´jabb felfedezések felé [14, 21].

5. Az ´ atlagos kap´ as Egy H megengedett halmazra az (1) bal és jobb oldalának hányadosa adja meg, hogy az n + H (x ≤ n ≤ 2x) eltoltakba átlagosan hány pr´ımszám esik, ha az átlagolást a ν(n) s´ ulyokkal végezz¨ uk. Ez a hányados hatékonyan kiszám´ıtható az (5) alak´ u s´ ulyokra, feltéve, hogy a pr´ımszámok bizonyos maradékosztályokban kell˝oen egyenletesen oszlanak el. Az egyenletes eloszlás az (1) bal oldalának szám´ıtása közben mer¨ ul fel, mégpedig a k¨ ovetkez˝ oképpen. Az (5)-öt használva az (1) bal oldala k ∑

∑

i=1 d,d′ ≤R

µ(d)µ(d′ )g

(

log d log R

) ( ) log d′ g log R

∑

1n + hi

pr´ım ,

x≤n≤2x [d,d′ ]|P (n)

ahol [d, d′ ] a d és a d′ legkisebb közös többszöröse, tehát a [d, d′ ] | P (n) reláció annyit tesz, hogy d és d′ a P (n) osztója. Pontosabban itt csalunk egy kicsit, de ez a lényeget nem érinti: a bels˝ o összegben csak azok az n-ek szerepelnek, amikre P (n) minden pr´ımoszt´ oja legal´ abb log log log x. A bels˝o összeg olyan – nagyjából x és 2x k¨ oz¨ otti – pr´ımek sz´ am´ at adja meg, amik modulo q := [d, d′ ] egy nem t´ ul nagy sz´ am´ u adott maradékoszt´ alyba esnek. A k¨ uls˝o összegzésben a négyzetmentes d, d′ ≤ R sz´ amok vesznek részt, ezért q ≤ R2 = xθ is négyzetmentes. A továbblépéshez célszer˝ u feltenni, hogy az x és 2x közötti pr´ımszámok maradékai a legtöbb szóba jöv˝ o q modulusra nézve nagyon egyenletesen oszlanak el: 7

EH(θ) hipot´ ezis. Minden A > 0 számhoz található egy C > 0 konstans, hogy x ≥ 2 esetén ∑ q≤xθ q n´ egyzetmentes

max (a,q)=1

∑ x≤p≤2x p≡a (mod q)

1 1− φ(q)

∫

2x

x

dt x
Az egyenl˝ otlenségben szerepl˝o integrál az x és 2x közötti pr´ımek számát adja meg j´ o k¨ ozel´ıtéssel, φ(q) a modulo q redukált maradékosztályok száma. A hipotézist a θ < 1/2 értékekre Bombieri és Vinogradov igazolta egymástól f¨ uggetlen¨ ul [1, 30], m´ıg a θ < 1 értékekre Elliott és Halberstam sejtette [3]. Mindezek után elmondhatjuk a sz´ amol´ as végeredményét, amit eredetileg Goldston, Pintz, Yıldırim [8] talált k+ℓ a g(t) := (1 − t)+ esetben (v¨ o. (4)) és Soundararajan [27, 28] az általános esetben (v¨ o. (5)). 4. t´ etel ([8, 27, 28]). Legyen H egy k elem˝ u megengedett halmaz. Legyen g : R → R egy k-szor folytonosan differenciálható f¨ uggvény, ami a [0, 1] intervallumon k´ıv¨ ul nulla. Az EH(θ) hipotézis mellett van olyan valósz´ın˝ uségi mérték az x ≤ n ≤ 2x egészeken, amire nézve az n + H eltolt halmazba es˝o pr´ımek számának várható értéke ∫ 1 k−2 2 t k g (k−1) (t) dt θ (k − 2)! 0 · ∫ 1 + o(1). k−1 2 2 t g (k) (t) dt (k − 1)! 0 A tételben g (j) a g f¨ uggvény j. deriváltját jelöli, m´ıg o(1) egy nullához tartó mennyiség x → ∞ mellett. Meglep˝o módon a fenti átlagos pr´ımkapás” mértéke nem ” éri el az egyet, de azt a k n¨ ovelésével tetsz˝olegesen meg tudja közel´ıteni. Pontosabban az EH(θ) hipotézist egyel˝ore csak a θ < 1/2 értékekre siker¨ ult bizony´ıtani, m´ıg [5, Theorem 16] szerint a második tört szuprémuma a lehetséges g-k felett kifejezhet˝ o a Jk−2 Bessel-f¨ uggvény els˝o pozit´ıv gyökéb˝ol mint ∫ k sup g

1

tk−2 dt 4k(k − 1) 14.8461 (k − 2)! 0 = ≈4− . ∫ 1 2 k−1 j k 2/3 t 2 k−2,1 (k) g (t) dt (k − 1)! 0 g (k−1) (t)

2

Mindenesetre a fenti tételb˝ ol már következik, hogy ha EH(θ) fennáll bármilyen θ > 1/2 értékre, akkor létezik a 2. tételt kielég´ıt˝o k, tehát létezik Polignac-szám is. Péld´ aul a [8] dolgozat fontos megállap´ıtása, hogy az Elliott–Halberstam-sejtés mellett vehet˝ o k = 6, amikor is min D ≤ 16. 8

6. Hogyan fogjunk t¨ obb pr´ımet? A 4. tétel a hat´ arán van annak, hogy Polignac-szám létezése következzék bel˝ole, ezért a megjelenésekor természetes kérdésként mer¨ ult fel, hogy a benne szerepl˝o várhat´ o érték megn¨ ovelhet˝ o-e valamiképpen. A szóban forgó várható érték a o(1) hibatagot lesz´ am´ıtva két pozit´ıv tényez˝o szorzataként van megadva, ezért – ha kissé ban´ alisak akarunk lenni – valamelyik tényez˝ot kell megnövelni u ´gy, hogy a másik tényez˝ o legfeljebb csak keveset v´ altozzék. A dolog azért bonyolultabb, mint hangzik, olyannyira, hogy a szakért˝ ok k¨ orében elterjedt volt a nézet, miszerint a meglév˝o eszk¨ oz¨ okkel ilyesfajta jav´ıt´ as nem várható. Mégis, a kés˝obbi fejleményekben pontosan ez t¨ ortént, mégpedig mindkét lehetséges irányban. Zhang [32] és Polymath8a [20] az els˝ o tényez˝ o megn¨ ovelésére koncentrált, m´ıg Maynard [14] és Polymath8b [21] a második tényez˝ o megn¨ ovelésére. Zhang [32] bizony´ıt´ asa Motohashi és Pintz [16] egy fontos észrevételére ép¨ ul: a 4. tételhez vezet˝ o sz´ amol´ asban nem veszt¨ unk sokat, ha az EH(θ) hipotézist megszor´ıtjuk azokra a négyzetmentes q ≤ xθ számokra, amiknek minden pr´ımosztója legfeljebb xδ valamilyen δ > 0 konstanssal. Az ilyen számokat xδ -simáknak nevezz¨ uk, és sok el˝ ony˝ os tulajdons´ aguk van, pl. két egymás utáni osztójuknak a hányadosa legfeljebb xδ , tov´ abb´ a bármely osztójuk maga is xδ -sima. Egy másik fontos észrevétel, hogy a sz´ amol´ asban csak azok az a mod q maradékosztályok vesznek részt, amiket b´ armilyen p | q pr´ımosztó szerint redukálva a hj − hi mod p (i ̸= j) maradékoszt´ alyok egyikét kapjuk. Zhang [32] az ily módon gyeng´ıtett EH(θ, δ) hipotézist igazolta valamilyen θ > 1/2 és δ > 0 paraméterekkel, és ebb˝ol adódott k¨ ovetkezésként a 2. tétel. A Polymath8a [20] projekt jelent˝osen b˝ov´ıtette a megfelel˝ o (θ, δ) p´ arok halmaz´ at, minden ilyen párra csökkentette a megfelel˝o k értékét, és egyszer˝ us´ıtette a bizony´ıtást. Pl. a θ fels˝o határa Zhang [32] dolgozatában 1/2 + 1/584, a Polymath8a [20] cikkben 1/2 + 7/300. Maynard [14] és Tao [29] az (5) helyett a ( (6)

ν(n) :=

∑ d1 |n+h1

...

∑ dk |n+hk

( µ(d1 ) . . . µ(dk )f

log d1 log dk ,..., log R log R

) )2

s´ ulyokat haszn´ alja, ahol f : Rk → R egy kell˝oen sima f¨ uggvény, ami a ∆k := {(t1 , . . . , tk ) ∈ Rk : t1 , . . . , tk ≥ 0 és t1 + . . . + tk ≤ 1} szimplexen k´ıv¨ ul nulla. Ez a defin´ıció jobban megfelel az eredeti célkit˝ uzésnek, mert az n + H elemeir˝ ol k¨ ul¨ on-k¨ ul¨ on próbálja elérni, hogy kevés pr´ımosztójuk legyen, nem csak a szorzatukat, a P (n)-t tartja szem el˝ott. Valójában az (5) a (6)-nak azon speci´ alis esete, amikor f (t1 , . . . , tk ) csak a változók o¨sszegét˝ol f¨ ugg, nevezetesen (7)

f (t1 , . . . , tk ) = g(t1 + . . . + tk ).

Ennek oka, hogy a meg´ allapodásunk szerint csak olyan n-ekkel dolgozunk, amikre az n + h1 , . . . , n + hk sz´ amok p´ aronként relat´ıv pr´ımek, vagyis a (6)-beli d1 , . . . , dk változ´ ok k¨ olcs¨ on¨ osen egyértelm˝ uen meghatároznak egy d | P (n) osztót a d = 9

d1 . . . dk utas´ıt´ assal. Ezek ut´ an kimondhatjuk a 4. tétel megfelel˝ojét, ami a (6) s´ ulyokkal val´ o átlagol´ assal k¨ ovetkezik. El˝oször is bevezet¨ unk egy jelölést a ∆k szimplex ti = 0 egyenlettel defini´ alt lapjára: ∆k,i := {(t1 , . . . , tk ) ∈ ∆k : ti = 0},

i = 1, . . . , k.

5. t´ etel ([14, 29]). Legyen H egy k elem˝ u megengedett halmaz. Legyen f : Rk → R egy k-szor folytonosan differenciálható f¨ uggvény, ami a ∆k szimplexen k´ıv¨ ul nulla. Az EH(θ) hipotézis mellett van olyan valósz´ın˝ uségi mérték az x ≤ n ≤ 2x egészeken, amire nézve az n + H eltolt halmazba es˝o pr´ımek számának várható értéke ( )2 k ∫ ∑ ∂ k−1 f θ i=1 ∆k,i ∂t1 . . . ∂ti−1 ∂ti+1 . . . ∂tk · + o(1). )2 ∫ ( 2 ∂kf ∂t1 . . . ∂tk ∆k A (7) alak´ u f¨ uggvényekre a fenti áll´ıtás a 4. tételbe megy át, mert a t1 + tk−1 . . . + tk = t affin hipers´ık a ∆k -t egy (k−1)! térfogat´ u (k − 1)-szimplexben metszi, tk−2 ´ a ∆k,i -t pedig egy térfogat´ u (k − 2)-szimplexben. Altal´ aban véve is megmu(k−2)!

tathat´ o [21, Lemma 41], hogy a tétel nem gyeng¨ ul, ha szimmetrikus f : Rk → R f¨ uggvényekre szor´ıtkozunk: ilyenkor az n + H eltolt halmazba es˝o pr´ımek számának v´ arhat´ o értéke ( )2 ∫ ∂ k−1 f k ∂t1 . . . ∂tk−1 θ ∆k,k · + o(1). ( )2 ∫ 2 ∂kf ∆k

∂t1 . . . ∂tk

Mindezek fényében kézenfekv˝ onek t˝ unik egy f szimmetrikus polinomot keresni, amire a m´ asodik t¨ ort 4-nél nagyobb, mert akkor alkalmas θ < 1/2 értékkel u ´j bizony´ıt´ ast kapunk a 2. tételre. Más szóval, ha Mk jelöli a második tört szuprémumát a lehetséges f -ek felett, akkor Mk > 4 kimutatása a cél. A gyakorlatban célszer˝ ubb az f helyett a nevez˝ oben szerepl˝o F (t1 , . . . , tk ) :=

∂kf ∂t1 . . . ∂tk

parci´ alis deriv´ altat megadni, ami szintén szimmetrikus polinom. Maynard [14] az els˝ o két hatv´ any¨ osszeg, t1 + . . . + tk és t21 + . . . + t2k polinomjaival k´ısérletezve talált egy 11-edfok´ u péld´ at, amib˝ol M105 > 4 következett. Polymath egy 23-adfok´ u F szimmetrikus polinommal demonstrálta az M54 > 4 egyenl˝otlenséget [21, Thek orem 23]. M´ asfel˝ ol bel´ athat´ o [21, Corollary 37], hogy Mk legfeljebb k−1 log k, amiért M50 < 4. Teh´ at a 2. tételben mindenképp vehet˝o k = 54, de a k = 50 értékhez az 5. tétel nem elegend˝ o. Ugyanakkor az 5. tételnek vannak olyan variánsai [21, Theorems 26 & 28], amikben f : Rk → R a ∆k szimplexen k´ıv¨ ul is lehet nullától 10

k¨ ul¨ onb¨ oz˝o: ezek seg´ıtségével a 2. tétel áll´ıtása a k = 50 értékre igazolható, és egy Elliott–Halberstam-t´ıpus´ u sejtés mellett k = 3 is megfelel˝o. Tehát bizony´ıtásunk van arra, hogy min D ≤ 246, és jó okunk van hinni abban, hogy min D ≤ 6. k Mit ad az 5. tétel nagy k-ra? Már eml´ıtett¨ uk az Mk ≤ k−1 log k fels˝o becslést. A m´ asik ir´ anyban Maynard [14] igazolta minden elég nagy k-ra, hogy Mk ≥ log k − log log k − 2. Val´ oj´ aban ez az alsó becslés minden k ≥ 2 értékre teljes¨ ul [21, 48. oldal], és a log log k helyett egy alkalmas abszol´ ut konstanssal is igaz [21, Theorem 23]. Teh´ at a Bombieri–Vinogradov-tétel [1, 30] alapján kb. 14 log k darab pr´ımet tudunk garant´ alni végtelen sok n + H eltoltban, és a Zhang-féle iránnyal kombin´ alva az 14 egy¨ utthat´ o jav´ıtható 157 600 -ra [21, Theorem 6]. Ez a Dickson–Hardy– Littlewood-sejtés egy gyenge formája, és igen figyelemre méltó eredmény.

7. To eneti megjegyz´ esek ¨rt´ A kis pr´ımhézagok terén az egyik els˝o fontos eredmény Erd˝os Páltól [4] származik: létezik egy c < 1 konstans u ´gy, hogy a 0 < p − p′ < c log p egyenl˝ otlenségnek végtelen sok megoldása van pr´ımekben. A c < 1 feltételnek az a jelent˝ osége, hogy a pr´ımszámtétel szerint az x kör¨ uli pr´ımszámok átlagosan log x t´ avols´ agra vannak egym´ astól, vagyis c > 1 esetén a fenti áll´ıtás egyszer˝ u következmény, m´ıg c = 1 esetén nem t´ ul meglep˝o. A c-re többen próbáltak minél jobb értéket megadni, de az igazi áttörést Goldston, Pintz, Yıldırım [8] érte el, amikor siker¨ ult bel´ atniuk, hogy minden c > 0 konstans megfelel˝o. A [8]-ban kifejlesztett m´ odszer fontos szerepet játszott Erd˝os két másik kedvenc problémájának megold´ as´ aban: van-e tetsz˝ olegesen hossz´ u számtani sorozat a pr´ımek között, illetve megjav´ıthat´ o-e a nagy pr´ımhézagokra vonatkoz´ o Rankin-becslés [23] egy végtelenhez tart´ o faktorral. Az els˝ ore ad választ a h´ıres Green–Tao-tétel [10], a másodikat pedig néh´ any h´ onapja oldotta meg egymástól f¨ uggetlen¨ ul Ford–Green–Konyagin– Tao [6] és Maynard [15]. A Rankin-becslés további jav´ıtását tartalmazza a napokban megjelent [7] preprint. A pr´ımhézagokról és a kapcsolódó Landau-problémák történetér˝ ol részletes áttekintést ny´ ujt a [17] dolgozat. A Bombieri–Vinogradov-tétel [1, 30] két alappillére a Siegel–Walfisz-tétel [26, 31] és a Linnyik [13] által felfedezett u ń. nagy szita egy letisztult formája. A nagy szita val´ osz´ın˝ uségsz´ am´ıt´ asi jellegét az els˝ok között ismerte fel Rényi Alfréd [24], és a seg´ıtségével átt¨ orést ért el az ikerpr´ımsejtés és a hozzá szorosan kapcsolódó Goldbach-sejtés megk¨ ozel´ıtésében. Könnyen lehet, hogy már a Linnyik–Rényi-féle els˝ o verzi´ okb´ ol k¨ ovetkezik az EH(θ) hipotézis valamilyen pozit´ıv θ-val, legalábbis erre enged k¨ ovetkeztetni Bombieri egy megjegyzése [1, (1.12) alatt]. Mindez k¨ ulönösen érdekes az 5. tétel fényében, hiszen az itt szerepl˝o várható érték bármilyen θ > 0 mellett tetsz˝ oleges naggy´ a tehet˝o a k és az f : Rk → R alkalmas megválasztásával. A Polymath projekteket Timothy Gowers kezdeményezte 2009 elején a matematikai kutat´ as egy u ´jfajta formájaként. A kutatás nyilvánosan, egy internetes 11

fel¨ uleten kereszt¨ ul t¨ orténik, és bárki kötetlen¨ ul – akár névtelen¨ ul is – csatlakozhat. A pr´ımhézagokra vonatkoz´ o Polymath8 projekt egy intenz´ıv évet ölelt fel 2013 nyar´ at´ ol 2014 nyar´ aig, és k¨ ul¨ on¨ osen sikeresnek mondható. Az Európai Matematikai Társulat (EMS) felkérésére t¨ obb résztvev˝o – közt¨ uk a szerz˝o is – le´ırta az idevágó személyes tapasztalatait, és ezek megjelentek az EMS Newsletter legfrissebb szám´ aban [22].

8. K¨ osz¨ onetnyilv´ an´ıt´ as A cikk a Fazekas Mih´ aly Gimnáziumban, a Közép-európai Egyetemen és a Helvetic Algebraic Geometry Seminar-on tartott el˝oadásaimra ép¨ ul. Köszönöm a megtisztel˝o felkéréseket, ahogyan k¨ ul¨ onb¨ oz˝o grantok – OTKA K101855 és K104183, ERC AdG228005 és AdG-321104 – t´ amogatását is. Hálával tartozom Pintz Jánosnak, aki a kéziratot gondosan átnézte, és értékes megjegyzéseivel ellátta.

Irodalom [1] E. Bombieri, On the large sieve, Mathematika 12 (1965), 201–225. [2] L. E. Dickson, A new extension of Dirichlet’s theorem on prime numbers, Messenger of Math. 33 (1904), 155–161. [3] P. D. T. A. Elliott, H. Halberstam, A conjecture in prime number theory, In: Symposia Mathematica, Vol. IV (INDAM, Rome, 1968/69), 59–72, Academic Press, London, 1970. [4] P. Erd˝ os, The difference of consecutive primes, Duke Math. J. 6, (1940), 438–441. [5] B. Farkas, J. Pintz, Sz. Révész, On the optimal weight function in the GoldstonPintz-Yıldırım method for finding small gaps between consecutive primes, In: Number theory, analysis, and combinatorics, 75–104, De Gruyter Proc. Math., De Gruyter, Berlin, 2014. [6] K. Ford, B. Green, S. Konyagin, T. Tao, Large gaps between consecutive prime numbers, arXiv:1408.4505 [7] K. Ford, B. Green, S. Konyagin, J. Maynard, T. Tao, Long gaps between primes, arXiv:1412.5029 [8] D. A. Goldston, J. Pintz, C. Y. Yıldırım, Primes in tuples I, Ann. of Math. (2) 170 (2009), 819–862. [9] A. Granville, D. M. Kane, D. Koukoulopoulos, R. J. Lemke Oliver, Best possible densities of Dickson m-tuples, as a consequence of Zhang-Maynard-Tao, arXiv:1410.8198 [10] B. Green, T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), 481–547. [11] G. H. Hardy, J. E. Littlewood, Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes, Acta Math. 44 (1923), 1–70. [12] D. R. Heath-Brown, Almost-prime k-tuples, Mathematika 44 (1997), 245–266. [13] Y. V. Linnik, The large sieve (Russian), Dokl. Akad. Nauk SSSR 30 (1941), 292–294. [14] J. Maynard, Small gaps between primes, Ann. of Math. (2), 181 (2015), 383–413.

12

[15] J. Maynard, Large gaps between primes, arXiv:1408.5110 [16] Y. Motohashi, J. Pintz, A smoothed GPY sieve, Bull. Lond. Math. Soc. 40 (2008), 298–310. [17] J. Pintz, Landau’s problems on primes, J. Théor. Nombres Bordeaux 21 (2009), 357–404. [18] J. Pintz, Polignac numbers, conjectures of Erd˝ os on gaps between primes, arithmetic progressions in primes, and the bounded gap conjecture, arXiv:1305.6289 [19] M. A. de Polignac, Recherches nouvelles sur les nombres premiers, Comptes rendus hebdomadaires des séances de l’Académie des sciences 29 (1849), 397–401. [20] D. H. J. Polymath, New equidistribution estimates of Zhang type, Algebra & Number Theory 8 (2014), 2067–2199. [21] D. H. J. Polymath, Variants of the Selberg sieve, and bounded intervals containing many primes, Res. Math. Sci. 1 (2014), no. 12, 83 oldal [22] D. H. J. Polymath, The “Bounded gaps between primes” Polymath project – A retrospective analysis, EMS Newsletter, no. 94, December 2014, 13–23. [23] R. A. Rankin, The difference between consecutive prime numbers, J. London Math. Soc. 13 (1938), 242–244. [24] A. Rényi, On the representation of an even number as the sum of a single prime and single almost-prime number (Russian), Izv. Akad. Nauk SSSR Ser. Mat. 12, (1948), 57–78. [25] A. Selberg, Lectures on sieves, In: Collected papers, Vol. II, Springer-Verlag, Berlin, 1991. ¨ [26] C. L. Siegel, Uber die Classenzahl quadratischer Zahlk¨ orper, Acta Arith. 1 (1935), 83–86. [27] K. Soundararajan, Notes on Goldston-Pintz-Yıldırım, 2005, publik´ alatlan [28] K. Soundararajan, Small gaps between prime numbers: the work of Goldston-PintzYıldırım, Bull. Amer. Math. Soc. (N.S.) 44 (2007), 1–18. [29] T. Tao, Polymath8b: Bounded intervals with many primes, after Maynard, 2013, blogbejegyzés, http://terrytao.wordpress.com/2013/11/19/polymath8b-boundedintervals-with-many-primes-after-maynard/ [30] A. I. Vinogradov, The density hypothesis for Dirichet L-series (Russian), Izv. Akad. Nauk SSSR Ser. Mat. 29 (1965), 903–934; Correction (Russian), ibid. 30 (1966), 719–720. [31] A. Walfisz, Zur additiven Zahlentheorie. II., Math. Z. 40 (1936), 592–607. [32] Y. Zhang, Bounded gaps between primes, Ann. of Math. (2) 179 (2014), 1121–1174.

Harcos Gergely MTA Rényi Alfréd Matematikai Kutat´ ointézet, 1053 Budapest, Re´ altanoda u. 13–15.

K¨ ozép-eur´ opai Egyetem, 1051 Budapest, N´ ador u. 9. [email protected]

[email protected]

13

´ REDUKTJAI A PROJEKTÍV TER BODOR BERTALAN, KALINA KENDE

Jel¨ olje P a megsz´ aml´ alhat´ oan v´ egtelen dimenzi´ os alteret valamilyen Fq test f¨ ol¨ ott. Ebben a dolgozatban bel´ atjuk, hogy ha G egy z´ art r´ eszcsoportja a Sym P szimmetrikus csoportnak, ami tartalmazza Aut P -t, akkor G-t tartalmazza a PΓL(P ) projekt´ıv szemiline´ aris csoport, vagy G = Sym P .

1. Bevezet˝ o A [4] és [2] cikkekben bizony´ıtják, hogy ha P egy véges dimenziós projekt´ıv tér valamilyen véges test f¨ ol¨ ott, és G egy részcsoportja Sym(P )-nek (a P elemein ható teljes szimmetrikus csoportnak), ami tartalmazza P automorfizmuscsoportját, akkor G ≤ PΓL(P ), G = Sym(P ), vagy G = Alt(P ) (a P elemein ható alternáló csoport). Ezekben a cikkekben a PSL(d, q) csoportot tartalmazó csoportokról szóló tételek ker¨ ultek kimond´ asra, amelyek egyszer˝ u következménye az el˝obbi áll´ıtás. Mivel végtelen dimenzi´ o esetén a PSL csoport nem értelmezhet˝o, ´ıgy ezen cikkek eredményeit nem lehet maradéktalanul általános´ıtani a végtelen dimenziós esetre. Az [1] cikkben alternat´ıv bizony´ıtás található ugyanezen tételekre. A [3] cikkben a racion´ alis számtest feletti megszámlálhatóan végtelen dimenziós projekt´ıv tér esetén bizony´ıtják a maximalitást. Ehhez Jordan-csoportokat és m´ as nem elemi eszk¨ oz¨ oket használnak. Ebben a dolgozatban elemi eszközöket használva belátjuk, hogy az áll´ıtás a véges test feletti megsz´ aml´ alhatóan végtelen dimenziós esetben is igaz. Végtelen halmaz esetén az altern´ al´ o csoportnak nincs természetes megfelel˝oje, ´ıgy ez esetben az áll´ıt´ as u ´gy sz´ ol, hogy ha P egy megszámlálhatóan végtelen dimenziós projekt´ıv tér egy véges test f¨ ol¨ ott, és Aut(P ) ≤ G ≤ Sym(P ) egy z´ art csoport, akkor G ≤ PΓL(P ), vagy G = Sym(P ). Itt a zártságot a pontonkénti konvegencia topológiája szerint értj¨ uk. Egy megsz´ aml´ alhat´ oan végtelen dimenziós projekt´ıv tér egy Fq véges test fölött mindig ω-kategorikus, azaz az els˝orend˝ u elméletének pontosan egy megszámlálhat´ o modellje van izomorfia erejéig. Egy megszámlálható ω-kategorikus strukt´ ur´ an´ al megadhat´ o egy természetes bijekció a strukt´ ura automorifizmuscsoportját tartalmaz´ o zárt permut´ aci´ ocsoportok és az els˝orendben definiálható reduktjai köz¨ ott, ahol két reduktot ekvivalensnek tekint¨ unk, ha egymásnak is reduktjai. Eset¨ unkben az adódik, hogy P -nek pontosan 1 + d(k) reduktja van, ahol q = pk , és p pr´ım (d(k) a k sz´ am oszt´ oinak számát jelöli). 14

1.1. Jel¨ ol´ esek. El˝ osz¨ or bevezet¨ unk néhány jelölést, amit a kés˝obbiekben használni fogunk. Legyen G egy csoport, ami hat az Ω halmazon. Ekkor egy S ⊂ Ω esetén jel¨ olje GS az S halmaz elemenkénti stabilizátorát. Egy ω ∈ Ω elem esetén jelölje G(ω) az ω elemnek a G csoport hatása szerinti orbitját. Legyen V egy megsz´ aml´ alhatóan végtelen dimenziós vektortér Fq felett. Ekkor a P projekt´ıv tér pontjaira tekinthet¨ unk u ´gy, mint V egydimenziós altereire. Egy v ∈ V \ 0 vektor esetén jelölje v˜ a v vektor által kifesz´ıtett alteret, mint P ˜ az {˜ elemét. Hasonl´ oan egy X ⊂ V halmaz esetén jelölje X v : v ∈ X} ⊂ P halmazt. A k¨ ovetkez˝ o lemma áll´ıt´ asait gyakran fogjuk használni a kés˝obbiekben, ezért ezeket itt k¨ ul¨ on is kimondjuk. Ezen áll´ıtások közvetlen következményei az el˝obbi defin´ıci´ oknak. 1.1. lemma. Az el˝ obbi jel¨ oléseket használva a következ˝ok teljes¨ ulnek: (1) GS ⊇ G{S} . (2) Ha H ≤ G és ω ∈ Ω, akkor H(ω) ⊆ G(ω). (3) Tetsz˝ oleges S ⊂ P részhalmazra és G ≥ Aut P csoportra a GS stabilizátor tranzit´ıvan hat a P \ ⟨S⟩ halmazon. (4) Tetsz˝ oleges S ⊂ Ω, g ∈ G és ω ∈ Ω esetén GS (ω) = GS g (ω g ) .

2. Az Aut(P ) csoport z´ art szupercsoportjai Ebben a fejezetben meghat´ arozzuk a Sym(P ) csoport azon zárt részcsoportjait, amik tartalmazz´ ak az Aut(P ) projekt´ıv lineáris csoportot. A zártságot itt a pontonkénti konvergencia topol´ ogiája szerint értj¨ uk. Ekkor egy G ≤ Sym(P ) csoport zárts´ aga azzal ekvivalens, hogy ha g ∈ Sym(P ), és a P projekt´ıv tér tetsz˝oleges véges F részhalmaz´ ahoz létezik olyan h ∈ G, hogy g|F = h|F , akkor g ∈ G. Belátjuk, hogy ha egy Aut(P ) ≤ G ≤ Sym(P ) csoport tartalmaz olyan transzformációt, ami nem szemiprojekt´ıv transzformáció (azaz nincs benne PΓL(P )-ben), akkor P tetsz˝ oleges S véges halmaza átvihet˝o P egy projekt´ıv f¨ uggetlen elemekb˝ol álló részhalmaz´ aba egy G-beli elemmel. 2.1. lemma. Tegy¨ uk fel, hogy Aut P ≤ G ≤ Sym P , és a G csoport n-tranzit´ıvan hat P -n. Legyenek az a1 , a2 , . . . , an+1 ∈ P elemek olyanok, hogy ai ∈ / ⟨aj | j ̸= i⟩ valamilyen 1 ≤ i ≤ n + 1 esetén. Ekkor létezik olyan g ∈ G elem, hogy az ag1 , ag2 , . . . , agn+1 elemek f¨ uggetlenek. Bizony´ıt´ as. Legyen S := {a1 , . . . , an+1 }. Feltehet˝o, hogy i = n + 1. Legyen S ′ := S \ {an+1 }. Ekkor a lemma feltétele szerint létezik olyan h ∈ G, hogy az S ′h halmaz f¨ uggetlen. Mivel an+1 ∈ / ⟨S ′ ⟩, ezért Aut (P )S ′ (an+1 ) végtelen, és ´ıgy ′ Aut (P )S ′ (an+1 ) ⊂ GS (an+1 ) is végtelen. A 1.1. lemma szerint azonban ( ) |GS′h ahn+1 | = GS′ (an+1 ) , ( ) ´ıgy GS ′h ahn+1 is végtelen. Ebb˝ol következik, hogy van olyan k ∈ GS ′ elem, amire ahk / ⟨S ′h ⟩. Ez azonban azt jelenti, hogy a g = hk választás jó lesz, hiszen ekkor n+1 ∈ g S = S hk = S ′h ∪ {akn+1 }, ami valóban egy f¨ uggetlen halmaz. 15

2.2. lemma. Tegy¨ uk fel, hogy Aut P ≤ G ≤ Sym P és a G csoport n-tranzit´ıvan hat ˜ = n. Ekkor a G ˜ stabilizátor P -n. Tegy¨ uk fel tov´ abb´ a, hogy S ⊆ V , ahol |S| = |S| S vagy tranzit´ıv a P \ S˜ halmazon, vagy pontosan egy véges orbitja van, aminek n−1 hossza (q − 1) . Bizony´ıt´ as. Mivel a G csoport n-tranzit´ıv, ezért az áll´ıtást elég belátni f¨ uggetlen S ⊂ V részhalmazokra. Legyen tehát S = {v1 , . . . , vn }, ahol a v1 , . . . , vn vektorok (line´ arisan) f¨ uggetlenek. Legyen {∑ } n A := λi vi | λi ∈ Fq \ 0 és B := V \ (A ∪ S). i=1

˜ halmazon is. Ebb˝ol már köAzt áll´ıtjuk, hogy ekkor G tranzit´ıvan hat a A˜ és a B n ˜ = P \ S, ˜ |A| ˜ = |A| = (q−1) = (q − 1)n−1 , vetkezik a lemma áll´ıt´ asa, hiszen A˜ ∪ B q−1 q−1 ˜ halmaz végtelen. és a B ˜ El˝ osz¨ or bel´ atjuk, hogy G tranzit´ıvan hat A-on. Ehhez elég belátni, hogy tetsz˝ oleges u, v ∈ A vektorokhoz létezik olyan Γ ∈∑ Aut(V ), hogy viΓ ∈ ⟨v ∑in⟩ minden n 1 ≤ i ≤ n esetén, és uΓ = v. Legyenek tehát u = i=1 λi vi ∈ A és v = i=1 µi vi ∈ A tetsz˝ olegesek. Ekkor mivel v1 , . . . , vn lineárisan f¨ uggetlenek, ezért létezik olyan Γ ∈ Aut(V ) line´ aris transzform´ ació, amire viΓ = µλii vi . Azt áll´ıtjuk, hogy ez a Γ jó választ´ as, azaz uΓ = v. Val´ oban, mivel Γ lineáris, ezért (∑ )Γ ∑ n n n ∑ Γ Γ u = λ i vi = λi vi = µi vi = v. i=1

i=1

i=1

˜ Most bel´ atjuk, hogy G tranzit´ıvan hat B-on is. Ehhez elég belátni, hogy ha ˜ akkor az S˜ ∪ {a} halmaz egy f¨ a ˜ ∈ B, uggetlen halmazba képezhet˝o valamilyen G-beli elemmel. Ebb˝ ol már k¨ ovetkezik az áll´ıtás, hiszen Aut(P ) (és ´ıgy G is) tranzit´ıvan hat a projekt´ıv f¨ uggetlen n-esek halmazán. ˜ Ha a ∈ / ⟨S⟩, akkor S ∪ {a} f¨ uggetlen halmaz, a} halmaz is f¨ ugget∑n´ıgy az S ∪ {˜ len. Tegy¨ uk fel most, hogy a ∈ ⟨S⟩. Ekkor a = i=1 λi vi valamilyen λi ∈ Fq -k esetén. Mivel a ∈ / A, ezért λj = 0 valamilyen 1 ≤ j ≤ n-re. Ekkor vj ∈ / ⟨vi | i ̸= j⟩, ´ıgy v˜j ∈ / ⟨˜ vi | i ̸= j⟩. Ekkor azonban az 1.1. lemma szerint az S˜ ∪ {˜ a} halmaz átvihet˝o egy f¨ uggetlen halmazba valamilyen G-beli elemmel, és ezt kellett bizony´ıtanunk. 2.3. lemma. Tegy¨ uk fel, hogy Aut P ≤ G ≤ Sym P , és a G csoport n-tranzit´ıvan k −1 hat P -n. Legyen tov´ abb´ a k egy olyan egész szám, amire qq−1 ≥ n. Ekkor minden S ⊂ P , |S| = n halmazra a GS stabilizátor minden P \ S-beli véges orbitja legfeljebb q k −1 u. q−1 − n elem˝ −1 Bizony´ıt´ as. Legyen Q egy k dimenziós altere P -nek. Ekkor mivel |Q| = qq−1 ≥n= |S|, és a G csoport n-tranzit´ıv, ezért feltehet˝o, hogy S ⊂ Q. Ha a ∈ P \ Q ⊂ P \ ⟨S⟩, akkor az a elem GS szerinti orbitja végtelen. Így Q tartalmazza GS minden véges orbitj´ at. Ebb˝ ol k¨ ovetkezik, hogy minden P \ S-beli elem GS szerinti orbitjának k −1 hossza legfeljebb |Q \ S| = |Q| − n = qq−1 − n. k

16

2.4. lemma. Minden q, n ≥ 3 egészekhez létezik olyan k egész szám, amire (q − 1)

n−1

>

q k+1 − 1 −n≥0 q−1

teljes¨ ul. Bizony´ıt´ as. Ha q = 3, 4 és n = 3, 4, akkor az egyenl˝otlenség teljes¨ ul k = 1 esetén. Tegy¨ uk fel most, hogy q ≥ 5, vagy q = 3, 4 és n ≥ 5. Legyen ekkor k a legkisebb k+1 olyan egész, amire q q−1−1 ≥ n. Azt áll´ıtjuk, hogy erre a k-ra teljes¨ ulnek a lemmában fel´ırt egyenl˝ otlenségek. Mivel a k sz´ am értékét minimálisnak választottuk, ezért nq + 1 >

q k −1 q−1

< n, amib˝ol

qk − 1 q k+1 − 1 q+1= ≥n q−1 q−1 n−1

ad´ odik, ´ıgy elég bel´ atni, hogy (nq + 1) − n < (q − 1) . Ezt az áll´ıtást n szerinti teljes indukci´ oval bizony´ıtjuk. Ha n = 5 és q = 3, 4, akkor teljes¨ ul az egyenl˝otlenség. Ha n = 3 és q ≥ 5, akkor 2

(q − 1) > 4(q − 1) − 1 ≥ 3(q − 1) + 1. Az indukci´ os lépéshez tegy¨ uk fel, hogy már tudjuk, hogy ( ) n−2 (n − 1)q + 1 − (n − 1) < (q − 1) , ahol n ≥ 6, vagy n ≥ 4 és q ≥ 5. Ekkor ( ) n−1 (q − 1) > (q − 1) (n − 1)(q − 1) + 1 > 2(n − 1)(q − 1) + 1 ≥ n(q − 1) + 1, és ezt kellett bizony´ıtanunk. 2.5. lemma. Legyen Aut(P ) ≤ G Sym(P ) egy csoport. Ekkor G ≤ PΓL(P ) vagy G 3-tranzit´ıv. Bizony´ıt´ as. Tegy¨ uk fel, hogy G nem 3-tranzit´ıv. Belátjuk, hogy ekkor G ≤ PΓL(P ). Mivel Aut(P ) 2-tranzit´ıv, ezért G is 2-tranzit´ıv. Legyenek tehát a, b ∈ P tetsz˝ olegesek. Mivel G nem 3-tranzit´ıv, ezért a 2.2. lemma szerint a Ga,b stabilizátornak pontosan egy véges orbitja van V \ {a, b}-ben, aminek hossza q − 1. Ha c ∈ / ⟨a, b⟩, akkor Ga,b (c) végtelen, ´ıgy ez a véges orbit benne van az ⟨a, b⟩ projekt´ıv altérben. Mivel azonban ⟨a, b⟩ = q + 1, ezért ez csak u ´gy lehetséges ha Ga,b egyetlen véges orbitja V \ {a, b}-ben ⟨a, b⟩ \ {a, b}. Ebb˝ol következik, hogy c ∈ ⟨a, b⟩ \ {a, b} pontosan akkor teljes¨ ul, ha c ̸= a, b, és a Ga,b (c) orbit véges. Legyen most g ∈ G tetsz˝ oleges. Legyenek továbbá A, B, C ∈ P három egy egye nesre es˝ o pont. Ekkor C ∈ ⟨A, B⟩ \ {A, B}, és ´ıgy az el˝obbiek szerint GA,B (C) < ∞. Ebb˝ ol k¨ ovetkezik (a 1.1. lemma szerint), hogy GAg ,B g (C g ) is véges. Ez azonban azt jelenti, hogy C g ∈ ⟨Ag , B g ⟩ \ {Ag , B g }, azaz az Ag , B g , C g pontok is egy egyenesre esnek. Azt kaptuk tehát, hogy a g ∈ G transzformáció kollineáció (egyenestart´ o bijekci´ o). Ekkor a projekt´ıv geometria alaptétele szerint g ∈ PΓL(P ). 17

Most bel´ atjuk a dolgozat f˝o eredményét. 2.6. t´ etel. Legyen G ≤ Sym(P ) egy zárt csoport. Ekkor G ≤ PΓL(P ) vagy G = Sym(P ). Bizony´ıt´ as. Ennél a bizony´ıt´ asnál feltessz¨ uk, hogy q ≥ 3. A q = 2 eset következik az Fω er reduktjainak a klasszifikációjáb´ ol. Tegy¨ uk fel, hogy G PΓL(P ). 2 vektort´ Ekkor be kell l´ atnunk, hogy G = Sym(P ). Mivel G ≤ Sym(P ) zárt, ezért ehhez elég bel´ atni, hogy G s˝ ur˝ u, azaz minden n-re n-tranzit´ıv. Ezt n szerinti teljes indukcióval bizony´ıtjuk. A 2.5. lemma szerint G 3-tranzit´ıv. Az indukciós lépéshez tegy¨ uk fel, hogy a G csoport n-tranzit´ıv, de nem (n + 1)-tranzit´ıv. Ekkor van olyan S ⊂ P, |S| = n, hogy GS -nek legal´ abb 2 orbitja van P \ S-en. Ekkor a 2.2. lemma szerint GS -nek pontosan n−1 egy véges orbitja van P \ S-en, és ennek hossza (q − 1) . A 2.3. lemma szerint k −1 azonban GS -nek minden V \ P -beli véges orbitjának hossza legfeljebb qq−1 −n minden olyan k-ra, amire

q k −1 q−1

− n ≥ 0. Tehát egy ilyen k-ra n−1

(q − 1)

≤

qk − 1 − n, q−1

ami ellentmond a 2.4. lemm´ anak, hiszen n, q ≥ 3. Legyen q = pk alak´ u, ahol p pr´ım. Ekkor az Aut(Fq ) = Gal(Fq /Fp ) csoport ciklikus, és a σ Frobenius-automorfizmus generálja. A PΓL(P ) csoport fel´ırható Aut(P ) o Gal(Fq /Fp ) alakban. Ebb˝ol következik, hogy a PΓL(P ) projekt´ıv szemiline´ aris csoportnak az Aut(P ) csoportot tartalmazó részcsoportjai mind PΓLm (P ) := Aut(P ) o ⟨σ m ⟩ alak´ uak valamilyen m|k-ra. A PΓLm (P ) csoportok mind véges sok Aut(P ) szerinti mellékoszt´ aly uniói PΓL(P )-ben, ´ıgy ezek a csoportok is zártak. Ezeket az észrevételeket használva a 2.6. tétel a következ˝o formában is megfogalmazhat´ o. 2.7. t´ etel. Legyen G ≤ Sym(P ) egy zárt csoport. Ekkor G = PΓLm (P ) valamilyen m|k-re vagy G = Sym(P ). A 2.7. tétel a k¨ ovetez˝ oket jelenti a P strukt´ ura reduktjaira vonatkozóan. 2.8. k¨ ovetkezm´ eny. P -nek pontosan d(k) + 1 reduktja van, ahol d(k) jelöli a k sz´ am (pozit´ıv) oszt´ oinak szám´ at. Speciálisan ha q = p pr´ım, akkor minden redukt trivi´ alis.

Irodalom [1] P. Bhattachabya, On groups containing the projective special linear group, Arch. Math., 37 (1981), 295–299. [2] W. M. Kantor, T. P. McDonough, On the maximality of PSL(d + 1, q), d ≥ 2, J. London Math. Soc. (2), 8 (1974), 426. [3] I. Kaplan, P. Simon, The affine and projective groups are maximal, arXiv:1310.8157 [4] B. A. Pogorelov, Maximal subgroups of symmetric groups that are defined on projective spaces over finite fields, Mat. Zametki, 16 (1974), 91–100.

18

Bertalan Bodor, Kende Kalina: Closed supergroups of infinite dimensional projective linear groups Let P be a countably infinite dimensional projective space over a finite prime field. In this paper we prove that GL P is maximal in Sym P . Bodor Bertalan

Kalina Kende

E¨ otv¨ os L´ or´ and Tudom´ anyegyetem, Algebra és Sz´ amelmélet Tanszék, 1117 Budapest, P´ azm´ any Péter sét´ any 1/c


[email protected]

[email protected]

19

´ AZ F∞ 2 VEKTORTER REDUKTJAI BODOR BERTALAN, KALINA KENDE

Klasszifik´ aljuk az F∞ er o at k¨ olcs¨ on¨ os defini´ alhat´ os´ ag erej´ eig. ¨sszes reduktj´ 2 vektort´

1. Bevezet´ es Az F∞ er univerz´ alis abban az értelemben, hogy minden véges vagy meg2 vektort´ sz´ aml´ alhat´ oan végtelen F2 feletti vektortér beágyazható F∞ er ω2 -be. Ez a vektort´ kategorikus is: egy A strukt´ urát ω-kategorikusnak nevez¨ unk, ha megszámlálható, és elméletének minden megsz´ amlálható modellje izomorf A-val. Az F∞ erre 2 vektort´ ∞ teljes¨ ul, hogy minden F2 két részalgebrája között men˝o φ izomorfizmus kiterjed F∞ av´ a. Ez a tulajdonság a homogenitás. 2 egy automorfizmus´ A megsz´ aml´ alhat´ o strukt´ urák köz¨ ul a homogén strukt´ urák állnak a legközelebb a véges strukt´ ur´ akhoz. A homogén strukt´ urák elméletéb˝ol mi itt csak azokat az eredményeket ismertetj¨ uk r¨ oviden, amelyek közvetlen¨ ul kapcsolódnak a munkánkhoz. Sok és sokféle o nmag´ a ban is ´ e rdekl˝ o d´ e sre sz´ a mot tartó strukt´ ura tartozik ¨ k¨ ozéj¨ uk: péld´ aul a véletlen gráf, a véges testek feletti megszámlálhatóan végtelen dimenzi´ os vektorterek, a racionális számok halmaza a szokásos rendezési relációval ell´ atva vagy a megsz´ aml´ alható atommentes Boole-algebra. Kevésbé ismert, de egyszer˝ uség¨ uk miatt fontos példa a Henson-gráfok családja, ezek azok a Hn megsz´ aml´ alhat´ o homogén gr´ afok, amelyek nem tartalmaznak teljes Kn részgráfot [8], tov´ abb´ a a homogén részbenrendezett halmaz, ami a véletlen gráfhoz hasonlóan megkaphat´ o véletlen konstrukcióként is [1]. A homogén strukt´ urák általános elméletének kidolgoz´ asa Fra¨ıssé munkájával kezd˝odött [7], a Fra¨ıssé-tétel karakterizálja azokat a véges strukt´ ur´ akb´ ol álló osztályokat, amelyek el˝oállnak, mint valamely homogén strukt´ ura részstrukt´ uráinak osztálya. Egy strukt´ ura egy reduktja alatt a strukt´ ura alaphalmazán értelmezett relációk olyan halmaz´ at értj¨ uk, amelyek mindegyikére igaz, hogy els˝orend˝ u formulákkal defini´ alhat´ o a strukt´ ur´ aban. A reduktok halmazán értelmezhet˝o egy kvázirendezés: R1 . R2 pontosan akkor, ha R2 minden relációja definiálható R1 feletti els˝orend˝ u formul´ akkal. Két redukt kölcsönösen definiálható egymással, ha R1 . R2 és R2 . R1 , azaz R1 minden relációját definiálni lehet R2 feletti els˝orend˝ u formulákkal, és R2 minden rel´ aci´ oj´ at definiálni lehet R1 feletti els˝orend˝ u formulákkal. Az 1. tétel fontos k¨ ovetkezménye, hogy ω-kategorikus strukt´ ura minden reduktja is ω-kategorikus. Ez nem ω-kategorikus strukt´ ur´ akra még akkor sem feltétlen igaz, 20

ha a strukt´ ura nyelve véges, és csak relációkat tartalmaz. A [14]-ben megtalálható Lachlan egy ellenpéld´ aj´ anak le´ırása. Egy redukt automorfizmuscsoportja pontosan azon permutációkból áll, amelyek meg˝ orzik a redukt ¨ osszes relációját, ´ıgy speciálisan tartalmazza az eredeti strukt´ ura automorfizmuscsoportját. Továbbá, egy redukt automorfizmuscsoportjára teljes¨ ul a k¨ ovetkez˝ o zártsági feltétel: ha g1 , g2 . . . ∈ Aut(R) permutációk egy sorozata a redukt automorfizmuscsoportjából, amelyekre teljes¨ ul, hogy a strukt´ ura minden a elemére van olyan j index és ba elem, hogy minden n > j indexre gn (a) = ba , akkor a g1 , g2 . . . sorozat limesze, a h(x) = bx permutáció is benne van az automorfizmuscsoportban. Azonban ω-kategorikus strukt´ urák esetén ennél er˝osebb is igaz: a strukt´ ura automorfizmuscsoportj´ at tartalmazó zárt részcsoportok bijekcióban állnak a reduktok k¨ olcs¨ on¨ os defini´ alhat´ os´ agra vett ekvivalenciaosztályaival, ´ıgy ω-kategorikus strukt´ ur´ ak esetén a reduktok klasszifikálása ekvivalens a strukt´ ura automorfizmuscsoportj´ at tartalmaz´ o z´ art részcsoportok osztályozásával. Mivel a véges testek fölötti legfeljebb megsz´ aml´ alhat´ oan végtelen dimenziós vektorterek ω-kategorikusak, ´ıgy F∞ reduktjait vizsg´ a lhatjuk az automorfizmuscsoportjaikon kereszt¨ ul. 2 Sz´ amos ω-kategorikus homogén strukt´ urának siker¨ ult osztályozni a reduktjait k¨ olcs¨ on¨ os defini´ alhat´ os´ ag erejéig. Kölcsönös definiálhatóság erejéig öt k¨ ulönböz˝o reduktja van például a racion´ alis számoknak a szokásos rendezés¨ ukkel ellátva [6], a véletlen gr´ afnak [14], a véletlen turnamentnek [2] és a véletlen poszetnek [12]. A klasszifik´ aci´ o ismert a konstanssal ellátott Henson-gráfokra is [13]. A homogén rendezett gr´ afnak viszont már t¨ obb mint 40 [3], a racionális számoknak a rendezéssel és egy konstanssal ell´ atva már 116 [10], a véletlen gráfnak egy konstanssal ellátva pedig m´ ar t¨ obb mint 300 reduktja van. Ez utóbbira nem is ismert a teljes klasszifik´ aci´ o. Ennek alapján megfogalmazható, hogy minél több eleme van a nyelvnek, várhat´ oan ann´ al nagyobb lesz a reduktok száma, és ez egyszer˝ unek t˝ un˝o strukt´ urákra is meglep˝ oen nagy tud lenni. Ezekben az eredményekben az a közös, hogy a vizsgált strukt´ urák nyelve minden esetben véges, és nem tartalmaz f¨ uggvényjeleket. A legtöbb klasszifikáció ad hoc sz´ amol´ asokat haszn´ al, u ´jabban Bodirsky és Pinsker munkája nyomán Ramseyelméleti m´ odszereket alkalmaztak sikerrel [4]. Az általunk vizsgált strukt´ urák ezzel ´ szemben nem ´ırhat´ oak le véges relációs nyelven. Igy az eddig ismert módszerek nem m˝ uk¨ odnek. Az ω-kategorikus strukt´ ur´ ak elméletében fontos szerepet tölt be az alábbi tétel: 1. t´ etel (Engeler, Ryll–Nardzewski, Svenonius). Egy A strukt´ ura pontosan akkor ω-kategorikus, ha Aut(A) oligomorf [9]. Az 1. tétel egyszer˝ u k¨ ovetkezménye az alábbi lemma: 2. lemma. Legyen A egy ω-kategorikus strukt´ ura és R egy olyan reláció A alaphalmaz´ an, amelyet minden Aut(A)-beli permut´ ació meg˝oriz. Ekkor R definiálható egy A feletti els˝ orend˝ u formul´ aval. 21

Az F2 f¨ ol¨ otti vektorterek strukt´ urája alapvet˝oen k¨ ulönbözik az Fp fölötti vektorterekét˝ ol páratlan p pr´ımekre. Ez els˝osorban amiatt van, mert két nemnulla elem 2 karakterisztik´ aban mindig f¨ uggetlen. Máshogyan fogalmazva, egy egy elem által gener´ alt részstrukt´ ura az adott elemen k´ıv¨ ul csak a 0-t tartalmazza. Az F∞ vektort´ e r automorfizmuscsoportja a végtelen lineáris csoport amit 2 GL(∞, 2)-vel fogunk jel¨ olni. Hasonlóan, Aff(∞, 2) jelöli az F2 feletti megszámlálhatóan végtelen dimenzi´ os affin tér automorfizmuscsoportját. Az F∞ o 2 elemein hat´ ∞ szimmetrikus csoportot Sym(F∞ )-nel, a 0 elemnek a Sym(F )-beli stabiliz´ a tor´ a t 2 2 pedig Sym (F∞ ) -val fogjuk jel¨ o lni. 2 0 Egy GL(∞, 2) ≤ G ≤ Sym(F∞ artját a pontonkénti konvergencia 2 ) csoport lez´ szerinti topol´ ogi´ aban Cl⟨G⟩-vel jelölj¨ uk. A Cl⟨G⟩ csoportba tartozó permutációkat a k¨ ovetkez˝ o módokon lehet karakterizálni: • A φ permut´ aci´ o akkor és csak akkor eleme Cl⟨G⟩-nek, ha F∞ 2 minden S részhalmaz´ ahoz létezik olyan ψS G-beli permutáció, amelyre φ és ψS megegyeznek az S halmazon. • A φ permutáci´ o akkor és csak akkor eleme Cl⟨G⟩-nek, ha létezik G-beli permut´ aci´ oknak olyan ψ1 , ψ2 . . . sorozata, amelynek határértéke φ. Azaz minden a ∈ F∞ etezik j k¨ uszöbindex u ´gy, hogy minden j < k indexre 2 elemre l´ ψk (a) = φ(a).

2. A 0-t meg˝ orz˝ o reduktok A GL(∞, 2) és a Sym (F∞ alja a 0-t. Ebben az alfejezetben belátjuk, 2 )0 csoport fix´ hogy nincsen más, a 0-t fix´ al´ o GL(∞, 2) ≤ G ≤ Sym(F∞ art csoport. Ekvivalens 2 ) z´ átfogalmaz´ asban: ha egy R redukt relációival definiálható a 0, akkor az a redukt vagy csak a 0-b´ ol áll, vagy az ¨ osszes, a vektortér felett definiálható reláció definiálható R rel´ aci´ oival is. 3. lemma. Legyen ació, amely nem eleme GL(∞, 2)-nek, és fixálja) ⟨ g olyan permut´ ⟩ ( a 0-t. Ekkor a GL(∞, 2), g csoport és ´ıgy az ˝ot tartalmazó Cl GL(∞, 2), g csoport is 3-tranzit´ıvan hat az F∞ 2 \ {0} halmazon. Bizony´ıt´ as. Legyen a és b két tetsz˝oleges nem nulla eleme F∞ es a b 2 -nek. Az a ´ elemek akkor és csak akkor lineárisan f¨ uggetlenek, ha a ̸= b. Most legyen c, d és e h´ arom p´ aronként k¨ ul¨ onb¨ oz˝ o nem nulla eleme F∞ es csak akkor 2 -nek. Ezek akkor ´ line´ arisan f¨ uggetlenek, ha c + d ̸= e. Mivel GL(∞, 2) tranzit´ıvan hat a lineárisan f¨ uggetlen hármasokon, ezért elég ∞ megmutatnunk, hogy tetsz˝ o leges j, k, l ∈ F \ {0} páronként k¨ ulönböz˝o elemekhez 2 ( ) létezik f ∈ Cl GL(∞, 2), g amire f (j), f (k) és f (l) lineárisan f¨ uggetlenek. Ha j, k és l egy line´ arisan f¨ uggetlen rendszer, akkor f -et választhatjuk az identitásnak. Ha j, k és l line´ arisan ¨ osszef¨ uggenek, akkor j + k = l. Mivel vannak olyan a, b ∈ F∞ k¨ u l¨ o nb¨ o z˝ o elemek amikre g(a + b) ̸= g(a) + g(b), és GL(∞, 2) tranzit´ı2 van hat a F∞ \ {0}-beli elemekb˝ o l ´ a ll´ o lineárisan f¨ uggetlen párokon, léteznie kell 2 olyan h GL(∞, 2)-beli permut´ aciónak amire h(j) = a és h(k) = b. Az f f¨ uggvényt választhatjuk g ◦ h-nak. 22

4. lemma. Legyen GL(∞, 2) ≤ G ≤ Sym (F∞ oleges, a 0-t fixáló, GL(∞, 2)-t 2 )0 tetsz˝ tartalmaz´ o z´ art csoport. Legyenek továbbá a1 , a2 . . . an és an+1 olyan F∞ 2 \ {0}-beli p´ aronként k¨ ul¨ onb¨ oz˝ o elemek, amelyekre az an+1 elemet nem tartalmazza a többi által gener´ alt ⟨a1 , a2 . . . an ⟩ altér. Ekkor ha a G csoport n-tranzit´ıvan hat az F∞ 2 \ {0} halmazon, akkor tartalmaz olyan h permutációt, amelyre a h(a1 ), h(a2 ) . . . h(an ), h(an+1 ) elemek line´ arisan f¨ uggetlen rendszert alkotnak. Bizony´ıt´ as. Mivel a G csoport n-tranzit´ıvan hat az F∞ ıgy vá2 \ {0} halmazon ´ laszthatunk olyan G-beli h1 permutációt,⟨ amelyre a h1 (a1 ), h1 (a2⟩) . . . h1 (an ) elemek line´ arisan f¨ uggetlenek. Jelölje W a h1 (a1 ), h1 (a2 ) . . . h1 (an ) generált alteret. A h−1 (W ) halmaz véges, mert egy véges dimenziós altér ˝osképe egy bijekci1 óra nézve, és 2 karakterisztik´ aban a véges dimenziós alterek végesek. A lineáris leképezések f¨ uggetlen rendszereken való el˝o´ırhatósága alapján az an+1 elem pályája az {a1 , a2 . . . an } halmaz G-beli { pontonkénti stabilizátor´ }aban végtelen elemsz´ am´ u, ´ıgy a h1 (a1 ) elem p´ aly´ aja a h1 (a1 ), h1 (a2 ) . . . h1 (an ) halmaz G-beli pontonkénti stabiliz´ ator´ aban is végtelen elemszám´ u. Tehát létezik olyan h2 permutáció az {a1 , a2 . . . an } halmaz G-beli pontonkénti stabilizátorában, amelyre h2 (an+1 ) nem eleme h−1 ació megfelel˝o választás lesz h-nak. 1 (W )-nek. Ekkor a h1 ◦ h2 permut´ 5. lemma. Legyen GL(∞, 2) ≤ G ≤ Sym (F∞ art csoport, amely n-tranzit´ıvan 2 )0 z´ hat az F∞ en a G csoport hatása (n + 1)-tranzit´ıv 2 \ {0} halmazon. Ekkor n ≥ 3 eset´ is az F∞ 2 \ {0} halmazon. Bizony´ıt´ as. Elég megmutatnunk, hogy tetsz˝oleges a1 , a2 . . . an , an+1 páronként k¨ ulönb¨ oz˝ o F∞ \ {0}-beli elemekhez l´ e tezik olyan h ∈ G permut´ a ci´ o , amelyre a h(a 1 ), 2 h(a2 ) . . . h(an ), h(an+1 ) elemek lineárisan f¨ uggetlenek. Ennek bizony´ıtása azért elégséges, mert az (n + 1) elem˝ u lineárisan f¨ uggetlen rendszereken a GL(∞, 2) csoport tranzit´ıvan hat, ´ıgy az ˝ot tartalmazó G csoport is. Feltehetj¨ uk, hogy az a1 , a2 . . . an elemek line´ arisan f¨ uggetlenek, mivel a G csoport n-tranzit´ıv. Ha an+1 nem eleme az a1 , a2 . . . an elemek által generált altérnek, készen vagyunk. Ha an+1 eleme az a1 , a2 . . . an elemek által generá∑ lt altérnek, akkor an+1 egyérn telm˝ uen ´ırhat´ o fel néh´ any aj ¨ osszegeként. Ha an+1 ̸= j=1 aj , akkor választhatunk olyan ak elemet, amely line´ arisan f¨ uggetlen a többi aj elemt˝ol, ´ıgy alkalmazható a 4. lemma. ∑n Ha an+1 = j=1 aj akkor a csoporthatás n-tranzitivitása miatt választhatunk egy h1 permut´ aci´ ot G-b˝ ol u ´gy, hogy a h1 (a1 ), h1 (a2 ) . . . h1 (an−1 ) elemek lineárisan ∑n−1 f¨ uggetlenek legyenek, tov´ abb´ a h1 (an ) = j=1 h1 (aj ) is teljes¨ uljön. Ha h1 (an+1 ) line´ arisan f¨ uggetlen a t¨ obbi elem képét˝ol, akkor tudjuk alkalmazni a 4. lemmát. ∑n Ha pedig nem f¨ uggetlen, akkor fel´ırható h1 (an+1 ) = j=1 εj h1 (aj ) alakban. Itt εj ∈ {0, 1} és legal´ abb egy εj = 0, mert h1 (an+1 ) ̸= h1 (an ), illetve legalább kett˝o εj = 1 kell, hogy legyen. { } A h1 (a1 ), h1 (a2 ) . . . h1 (an−1 ) halmaz GL(∞, 2)-beli stabilizátorába es˝o öszszes permut´ aci´ o fix´ alja az ¨ osszeg¨ uket, azaz a h1 (an ) elemet is. Tehát a h1 (an+1 ) 23

{ } elem pály´ aja a h1 (a1 ), h1 (a2 ) . . . h1 (an−1 ) halmaz stabiliz´ ator´ ara ´ es nem pontonk´ enti stabiliz´ ator´ ara nézve az GL(∞, 2) csoportban véges, mert része egy véges altérnek, de} legal´ abb két elemet tartalmaz, mert az egyelem˝ u orbitok { { } csak a {0} és a h(an ) . Legyen a h2 permutáció a h1 (a1 ), h1 (a2 ) . . . h1 (an−1 ) stabili( ) ( ) zátor´ anak olyan eleme, amelyre h2 h1 (an−1 ) ̸= h1 (an−1 ); ekkor a h−1 1 (h2 h1 (aj ) ) elemeket a bj szimb´ olumokkal jelölve, b1 , b2 . . . bn lineárisan f¨ uggetlenek, és bn+1 ̸= ∑n ar korábban beláttuk. j=1 bj . Ezt az esetet m´ 6. t´ etel. Legyen g ∈ Sym(F∞ 2 ) egy( olyan permut´ ) ació, amelyik meg˝orzi a 0-t, és nem eleme GL(∞, 2)-nek. Ekkor Cl GL(∞, 2), g = Sym (F∞ 2 )0 . Bizony´ıt´ as. Sym (F∞ art csoport, amely n-tranzit´ıvan 2 )0 az egyetlen olyan z´ hat (az F∞ \ {0} halmazon minden n ∈ N-re. A 3. lemmában beláttuk, hogy 2 ) a Cl GL(∞, 2), g csoport 3-tranzit´ıv, a tétel áll´ıtása ´ıgy teljes indukciót használva k¨ ovetkezik az 5. lemm´ ab´ ol. Ezzel befejezt¨ uk a 0-t meg˝orz˝o reduktok osztályozását.

3. Az Aff (∞, 2) redukt Most bel´ atjuk, hogy amennyiben egy redukt nem fixálja a 0-t, akkor az csak az affin tér lehet az Aff(∞, 2) automorfizmuscsoporttal, vagy a strukt´ ura nélk¨ uli halmaz a Sym(F∞ ) automorfizmuscsoporttal. Mivel kett˝ o karakterisztik´ a ban az affin terek 2 egyenesei két pontb´ ol állnak, ´ıgy a tér pontjainak bármely permutációja kollineáció. Ezért automorfizmus alatt olyan permutáci´ okat ért¨ unk, amelyek a magasabb dimenzi´ os altereket is a nekik megfelel˝o dimenziós alterekbe képezik. Sz¨ ukség¨ unk lesz az eltol´ asok csoportjára. Minden F∞ al2 -beli a vektorhoz defini´ juk az a-val val´ o eltol´ ast a k¨ ovetkez˝oképpen: ta (x) = x + a. Az eltolások csoportját T-vel fogjuk jel¨ olni. 7. lemma. Legyen f egy olyan Sym(F∞ ació, amelyre igaz, hogy 2 )-beli permut´ b´ armely h´ arom a, b, c ∈ F∞ elemre az f (a + b + c) = f (a) + f (b) + f (c) egyenl˝oség 2 teljes¨ ul. Ekkor f = t ◦ h alakban el˝oáll´ıtható, ahol t ∈ T egy eltolás, és h ∈ GL(∞, 2) egy vektortér-automorfizmus. ( ) Bizony´ıt´ as. Legyen t a t(x) = x + f (0) eltolás, és h(x) = t f (x) = f (x) + f (0). Ekkor a h permutáci´ o meg˝ orzi az o¨sszeadás m˝ uveletét, és fixálja a 0-t: h(0) = f (0) + f (0) = 0, h(a + b) = f (a + b + 0) + f (0) = f (a) + f (b) + f (0) + f (0) = f (a) + f (b). ( ) Teh´ ul. Továbbá ekkor az f (x) = f (x) + f (0) + f (0) = ( at )h ∈ GL(∞, 2) teljes¨ t h(x) azonoss´ ag is teljes¨ ul, azaz f = t ◦ h. 24

A 7. lemma kimond´ as´ aban szerepl˝o f (a + b + c) = f (a) + f (b) + f (c) képlet motiv´ alja a k¨ ovetkez˝ o négyv´ altozós reláció bevezetését: R(a, b, c, d) ⇔ a + b + c = d. Ez egy szimmetrikus rel´ aci´ o. Geometriai jelentése, hogy négy, páronként k¨ ulönböz˝o elem pontosan akkor áll rel´ aci´ oban egymással, ha egy kétdimenziós affin alteret alkotnak. ( ) 8. t´ etel. A Cl GL(∞, 2), T csoport elemei karakterizálhatóak mint azok a permut´ a(ci´ ok, melyek)meg˝ orzik az R(a, b, c, d) relációt. Tehát f pontosan akkor eleme a Cl GL(∞, 2), T csoportnak, ha f (a + b + c) = f (a) + f (b) + f (c) teljes¨ ul minden a, b, c ∈ F∞ elemre. 2 ⟨ ⟩ Bizony´ıt´ as. Ha f eleme a GL(∞, 2), T csoportnak, akkor f (a + b + c) = f (a) + f (b) + f (c) teljes¨ ul minden a, b, c F∞ 2 -beli elemre, mert mind GL(∞, 2), mind T elemei meg˝ orzik az R rel´ aci´ ot. ( ) Legyen f tetsz˝ oleges Cl GL(∞, 2), T -beli permutáció. Ekkor f el˝oáll mint egy g1 , g2 . . . permut´ osorozat limesze a pontonkénti konvergencia topológiájában, ⟨aci´ ⟩ ahol minden gj egy GL(∞, 2), T -beli permutáció. Tehát minden x ∈ F∞ ete2 -hez l´ zik olyan nx k¨ usz¨ obindex, hogy minden j ≥ nx egészre igaz a gj (x) = f (x) egyenl˝oség. Legyenek az a, b, c ∈ F∞ es legyen n0 = min{na , nb , nc , na+b+c }, 2 elemek fixek, ´ ekkor f (a + b + c) = f (a) + f (b) + f (c) ekvivalens azzal, ⟨hogy gn0 (a + ⟩ b + c) = gn0 (a) (+ gn0 (b) + gn)0 (c). Ez pedig igaz, mert gn0 ∈ GL(∞, 2), T . Tehát f ∈ Cl GL(∞, 2), T -b˝ ol k¨ ovetkezik, hogy minden a, b, c ∈ F∞ 2 elemre f (a + b + c) = f (a) + f (b) + f (c) igaz. A m´ asik ir´ any´ u tartalmaz´ as következik a 7. lemmából. ( ) Teh´ at minden Cl GL(∞, 2), T -beli f permutáció el˝oáll mint f = t ◦ h, ahol Így beláttuk, hogy t ∈ T egy eltol´ a(s, és h ∈ GL(∞, ) 2) egy vektort´ ( er-automorfizmus. ) Aff(∞, 2) = Cl GL(∞, 2), T , mivel a Cl GL(∞, 2), T -beli permutációk affin automorfizmusok, és a 7. lemm´ aból következik, hogy minden affin automorfizmus el˝o´ all f = t ◦ h alakban, ahol t ∈ T és h ∈ GL(∞, 2). 9. lemma. Legyen GL(∞, 2) ≤ G ≤ Sym(F∞ art csoport, amely nem fixálja 2 ) olyan z´ a 0-t. Ekkor a G csoport 3-tranzit´ıvan hat az F∞ eren. 2 vektort´ Bizony´ıt´ as. Elég megmutatnunk, hogy ha a, b, c ∈ F∞ aronként k¨ ulönb˝oz˝o ele2 p´ mek, akkor létezik olyan G-beli h permutáció, amelyre h(a) = 0. Ez azért elégséges, mert GL(∞,( 2) tranzit´ıvan )hat az olyan (0, x, y) rendezett hármasokon, amelyekre x ̸= y, és a h(a), h(b), h(c) elemek ilyen rendezett hármast alkotnak. Teh´ at elég bel´ atni, hogy G tranzit´ıv az F∞ eren. A G csoport tartal2 vektort´ mazza a GL(∞, 2) csoportot, és a GL(∞, 2) csoport tranzit´ıvan hat a F∞ 2 \ {0} halmazon. Ezért G-nek legfeljebb két orbitja lehet a F∞ eren: a {0} és 2 vektort´ ´ a F∞ ıv kell, hogy legyen, mivel nem fixálja a 0-t. 2 \ {0} halmazok. Igy G tranzit´ 25

10. lemma. Legyen GL(∞, 2) ≤ G ≤ Sym(F∞ art csoport, amely nem 2 ) olyan z´ fix´ alja a 0-t. Ekkor a G csoport tranzit´ıvan hat azokon az (a, b, c, d) rendezett négyeseken, amelyekre az a, b, c és d páronként k¨ ulönböz˝o elemei a F∞ ernek, 2 vektort´ tov´ abb´ a R(a, b, c, d) is teljes¨ ul. Bizony´ıt´ as. A GL(∞, 2) csoport tranzit´ıvan hat azokon az (a, b, c, d) négyeseken, amelyekre a, b, c és d a F∞ aronként k¨ ulönböz˝o elemei, és 2 \ {0} halmaznak p´ a + b + c + d = 0 teljes¨ ul. Ez azért igaz, mert ebben az esetben az {a, b, c} elemeknek line´ arisan f¨ uggetlen rendszert kell alkotniuk. Ugyanis ha lineárisan összef¨ ugg˝oek lennének, akkor d = a + b + c = a + b + (a + b) = 0 kellene, hogy legyen, viszont d ̸= 0. Tov´ abb´ a a GL(∞, 2) csoport k¨ ulön-k¨ ulön tranzit´ıvan hat az (a, b, c, d) rendezett négyesek azon négy részhalmazán, ahol a négy elem köz¨ ul pontosan az egyik a 0, a másik három pedig k¨ ulönböz˝o. Meg fogjuk mutatni, hogy a }= 0 esetén { létezik olyan G-beli h permut´ ació, amelyre 0 ∈ / h(a), h(b), h(c), h(d) , továbbá h(a) + h(b) + h(c) + h(d) = 0 teljes¨ ul. Analóg áll´ıtások igazak, ha valamelyik másik elem 0, ezzel a maradék eseteket is visszavezetj¨ uk az els˝o bekezdésben bizony´ıtottra. Legyen az (a, b, c, d) rendezett négyes olyan, amire a = 0, továbbá b + c = d. Mivel a G csoport 3-tranzit´ıv, a 9. lemma alapján ezért létezik olyan G-beli g permut´ aci´ o, amelyre a g(b), g(c) és g(d) elemek lineárisan f¨ uggetlen rendszert alkotnak. Ha g(0) = 0, akkor a 6. tétel szerint a 0 stabilizátorának a G csoportban ∞ ´ G0 = Sym (F∞ alja 2 )0 -nak kell lennie. Igy G = Sym (F2 ), mivel a G csoport nem fix´ a 0-t. Teh´ at ebben az esetben igaz a lemma áll´ıtása. ⟨ ⟩ Ha g(0) ̸= 0, és g(b) nem eleme a g(c), g(d), g(0) generált altérnek, akkor a line´ aris leképezések f¨ uggetlen rendszeren való el˝o´ırhatósága alapján létezik olyan GL(∞, 2)-beli h permut´ aci´ o, amely stabilizálja a g(c), g(d) és g(0) elemeket, viszont ( ) h g(b) ̸= g(b). Ekkor az f = g −1 ◦ h ◦ g olyan permutáció lesz, amelyre f (0) = 0, f (c) = c és f (d) = d, de f (b) ̸= b. Tehát az f (b), f (c) és f (d) elemek lineárisan f¨ uggetlen rendszert alkotnak. A 6. tétel alapján ekkor is a 0 stabilizátora a G cso∞ ´ portban G0 = Sym (F∞ 2 )0 kell, hogy legyen. Igy G = Sym (F2 ), mivel a G csoport nem fix´ alja a 0-t. A h´ atralév˝ o eset az, amikor g(0) ̸= 0, továbbá teljes¨ ul még az alábbi három feltétel is: ⟨ ⟩ • g(b) ∈ g(c), g(d), g(0) , ⟨ ⟩ • g(c) ∈ g(b), g(d), g(0) , ⟨ ⟩ • g(d) ∈ g(b), g(c), g(0) . Indirekt tegy¨ uk fel, hogy g(b) ⟨ ̸= g(c) + g(d)⟩ + g(0). Mivel g(b), g(c), g(d) line´ arisan f¨ uggetlenek, és g(b) ∈ g(c), g(d), g(0) is teljes¨ ul, ezért vagy g(b) = g(c) + g(0), vagy g(b) = g(d) + g(0). Tegy¨ u k fel, hogy g(b) = g(c) + g(0), ekkor ⟨ ⟩ { } a g(b), g(c), g(0) gener´ alt⟨ altér a g(b), g(c), g(0), 0 kell, hogy álljon. Ez ellent⟩ mond annak, hogy g(d) ∈ g(b), g(c), g(0) . A g(b) = g(d) + g(0) lehet˝oség hasonlóan zárhat´ o ki. Így ellentmondásra jutottunk abból a feltevésb˝ol, hogy g(b) ̸= 26

g(c) + g(d) + g(0). Teh´ at a g(b) + g(c) + g(d) + g(0) = 0 egyenl˝oségnek teljes¨ ulnie kell. 11. t´ etel. Legyen GL(∞, 2) ≤ G ≤ Sym (F∞ art csoport, amely nem fixálja 2 ) olyan z´ a 0-t, és nem ˝orzi meg az R(a, b, c, d) relációt sem. Ekkor G = Sym (F∞ 2 ). Bizony´ıt´ as. Mivel a G csoport nem ˝orzi meg az R relációt, ´ıgy a 10. lemmát haszn´ alva kapjuk, hogy a G csoport tranzit´ıvan hat azokon az R-beli rendezett négyeseken, amelyek négy eleme páronként k¨ ulönböz˝o. Így tudunk választani egy olyan g permut´ aci´ ot a G csoportból és hozzá olyan b és c elemeket az F∞ 2 \ {0} halmazb´ ol, melyekre g(0) + g(b) + g(c) + g(b + c) ̸= 0 teljes¨ ul. { } Ha a 0 eleme a g(0), g(b), g(c), g(b + c) halmaznak, akkor a 10. lemma miatt feltehetj¨ uk, hogy g(0) = 0. Ekkor g(b) + g(c) + g(b + c) ̸= 0, vagyis a g(b), g(c) és g(b + c) elemek line´ arisan f¨ uggetlenek. A 6. tételt használva kapjuk, hogy G0 = Sym (F∞ at G = Sym (F∞ orzi meg a 0-t. 2 )0 , teh´ 2 ), mivel a G csoport nem ˝ { Most megvizsg´ a ljuk azt az esetet, mikor 0 nem eleme a g(0), g(b), g(c), } g(b + c) halmaznak. Ekkor g(0) + g(b) + g(c) + g(b + c) ̸= 0 miatt van legalább egy { olyan x elem a {0, b, c, b + c} halmazban, amelyre g(x) nem eleme a ⟨ g(0), g(b), } { } g(c), g(b + c) \ g(x) ⟩ halmaznak. Mivel a b, c és b + c elemek szerepe szimmetrikus, ´ıgy feltehetj¨ uk, hogy x = b + c egy ilyen elem. Ekkor a lineáris leképezések line´ arisan f¨ uggetlen rendszereken ( való el˝ ) o´ırhatósága alapján létezik olyan permut´ a ci´ o , melyre + GL(∞, 2)-beli h h g(b c) ̸= g(b + c), és az y ∈ {0, b, c} ele( ) mekre h g(y) = g(y) teljes¨ ul. Legyen f = g −1 ◦ h ◦ g. Ekkor f (0) = 0, f (b) = b és f (c) = c is teljes¨ ul, de f (b + c) ̸= b + c. Használva a 6. tételt a 0 stabilizátorának a G csoportban G0 = Sym (F∞ ol következik, hogy 2 )0 -nak kell lennie, amib˝ G = Sym (F∞ ). 2

¨ 4. Osszegz´ es Ezzel befejezt¨ uk F∞ alását kölcsönös definiálhatóság erejéig. 2 reduktjainak klasszifik´ 12. t´ etel. A F∞ ernek kölcsönös definiálhatóság erejéig pontosan a követ2 vektort´ kez˝ o négy reduktja van: (1) A vektortér F∞ ol 2 , automorfizmuscsoportja GL(∞, 2), ez pontosan azokb´ a permut´ aci´ okb´ ol áll, melyek meg˝orzik a 0 konstansot és a + bináris m˝ uveletet. (2) Az affin tér, automorfizmuscsoportja Aff(∞, 2), ez pontosan azokból a permut´ aci´ okb´ ol áll, melyek meg˝orzik az R négyváltozós relációt, azaz a kétdimenzi´ os affin altereket. (3) A strukt´ ura egy 0 konstanssal, automorfizmuscsoportja Sym (F∞ 2 )0 , ez pontosan azokb´ ol a permut´ aciókból áll, melyek meg˝orzik a 0 konstansot. (4) A strukt´ ura nélk¨ uli megszámlálhatóan végtelen halmaz, automorfizmuscsoportja Sym (F∞ ), az ¨ osszes permutáció az adott halmazon. 2

27

Irodalom [1] N. Ackerman, C. Freer, R. Patel, Invariant measures concentrated on countable structures. Preprint arXiv:1206.4011 [math.LO] (2012). [2] J. H. Bennett, The reducts of some infinite homogeneous graphs and tournaments. Rutgers university, doktori értekezés (1997). [3] M. Bodirsky, M. Pinsker, A. Pongr´ acz, The 42 reducts of the random ordered graph, bek¨ uldve (2013). [4] M. Bodirsky, M. Pinsker, Reducts of Ramsey Structures, Model Theoretic Methods in Finite Combinatorics, American Mathematical Society, Contemporary Mathematics, 558 (2011), 489–519. [5] P. J. Cameron, Oligomorphic permutation groups. London Mathematical Society Lecture Note Series, 152. Cambridge University Press (Cambridge, 1990). [6] P. J. Cameron, Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, 148 (1976), 127–139. [7] R. Fra¨ıssé, Sur certaines relations qui généralisent l’order des nombres rationnels, Comptes Rendus d’ l’Académie des Sciences de Paris, 237 (1953), 540–542. [8] C. W. Henson, A family of countable homogeneous graphs, Pacific Journal of Mathematics, 38 (1971), 69–83. [9] W. Hodges, Model theory. Encyclopedia of Mathematics and its Applications, 42. Cambridge University Press (Cambridge, 1993). [10] M. Junker, M. Ziegler, The 116 reducts of (Q, <, a), J. Symbolic Logic, 73 no. 3 (2008), 861–884. [11] D. Macpherson, A survey of homogeneous structures, Discrete Mathematics, 311(15) (2011), 1599–1634. [12] P. P. Pach, M. Pinsker, G. Pluh´ ar, A. Pongr´ acz, Cs. Szab´ o, Reducts of the random partial order, Advances in Mathematics, 267 (2014), pp. 94–120. [13] A. Pongr´ acz, Reducts of the Henson graphs with a constant, Annals of Pure and Applied Logic (2013), accepted. [14] S. Thomas, Reducts of the random graph, Journal of Symbolic Logic, 56(1) (1991), 176–181.

Bertalan Bodor, Kende Kalina: First order definable reducts of the vectorspace F∞ 2 We classify the closed subgroups of the countable symmetric group which contain the automorphism group of F∞ 2 , and thus also classify the structures which are first-order definable from F∞ up to interdefinability. 2 Bodor Bertalan

Kalina Kende



[email protected]

[email protected]

28

´ REDUKTJAI PARATLAN ´ AZ Fpω VEKTORTER ´ PRÍMEK ESETEN BODOR BERTALAN, KALINA KENDE

Ebben a dolgozatban le´ırjuk az Fp feletti megsz´ aml´ alhat´ oan v´ egtelen dimenzi´ os vektort´ er els˝ orendben defini´ alhat´ o reduktjait, ahol p ≥ 3 tetsz˝ oleges pr´ım.

1. Bevezet˝ o Legyen K egy tetsz˝ oleges véges test. Jelölje K ω a K test feletti megszámlálhatóan végtelen dimenzi´ os vektorteret. A lineáris leképezésekre vonatkozó kiterjesztési tulajdons´ ag miatt igaz az, hogy K ω bármely két véges altere közti izomorfizmus kiterjeszthet˝ o a teljes vektortér egy automorfizmusává. Ez a tulajdonság a homogenit´ as. Emellett ez a strukt´ ura univerzális is abban az értelemben, hogy b´ armely véges vagy megsz´ amlálhatóan végtelen K feletti vektortér beágyazható K ω -ba. Szintén fontos tulajdonsága ennek a vektortérnek az ω-kategoricitás: egy strukt´ ur´ at ω-kategorikusnak nevez¨ unk, ha az els˝orend˝ u elméletének pontosan egy megsz´ aml´ alhat´ o modellje van izomorfia erejéig. A megsz´ aml´ alhat´ o, homogén, ω-kategorikus strukt´ urákat azért szokták gyakran vizsg´ alni, mert bizonyos értelemben a végtelen strukt´ urák köz¨ ul ezek állnak legk¨ ozelebb a véges strukt´ ur´ akhoz. Ezek közé tartoznak például a véletlen gráf, a racion´ alis sz´ amok halmaza a szokásos rendezési relációval ellátva és a megszámlálhat´ o atommentes Boole-algebra. Egy strukt´ ura megértésénél fontos kérdés lehet, hogy a strukt´ ur´ anak mik az els˝orendben kifejezhet˝o reduktjai, azaz milyen, esetleg gyengébb strukt´ ur´ ak adhat´ ok meg a strukt´ ura alaphalmazán els˝orend˝ u defin´ıcióval. Egy megsz´ aml´ alhat´ o ω-kategorikus strukt´ urával azért kényelmes dolgozni, mert ezen strukt´ ur´ akn´ al a strukt´ ura reduktjai egyértelm˝ u módon jellemezhet˝oek az automorfizmuscsoportjaikkal. M´ ar sz´ amos homogén, megszámlálható, ω-kategorikus strukt´ urára ismert a reduktok teljes klasszifik´ aci´ oja. Ezek közé tartoznak például a véletlen gráf [12], a véletlen hipergr´ af [13] és a véletlen részbenrendezett halmaz [10]. Ezekben az eredményekben az a k¨ oz¨ os, hogy a vizsgált strukt´ urák véges relációs nyelven homogén strukt´ ur´ ak. A legt¨ obb klasszifikáció ad hoc számolásokat használ, u ´jabban Bodirsky és Pinsker munk´ aja nyom´ an Ramsey-elméleti módszereket alkalmaztak sikerrel [4]. Ebben a dolgozatban a K ω vektortér reduktjait vizsgáljuk abban az esetben, amikor K = Fp , ahol p ≥ 3 pr´ım. A K ω vektortér az eddig vizsgált strukt´ urákkal 29

szemben nem ´ırhat´ o le véges relációs nyelven u ´gy, hogy homogén legyen, ´ıgy ebben az esetben az eddig ismert módszerek nem m˝ uködnek.

2. Reduktok Egy A strukt´ ura reduktja egy olyan B strukt´ ura, aminek ugyanaz az alaphalmaza, mint A-nak, és a B strukt´ ura minden rel´ aciója és m˝ uvelete kifejezhet˝o az A strukt´ ura rel´ aci´ oib´ ol és m˝ uveleteib˝ol valamilyen els˝orend˝ u formula seg´ıtségével. Két reduktot ekvivalensnek tekint¨ unk, ha egymásnak is reduktjai. Ha B reduktja Anak, akkor Aut(A) ⊂ Aut(B) ⊂ Sym(A), továbbá könnyen ellen˝orizhet˝o az is, hogy Aut(B) mindig z´ art Sym(A)-ban. A zártságot a pontonkénti konvergencia topológiája szerint értj¨ uk. Ekkor egy G ≤ Sym(A) csoport zártsága azzal ekvivalens, hogy ha g ∈ Sym(A), és az A strukt´ ura alaphalmazának tetsz˝ oleges véges F halmazához létezik olyan h ∈ G, amire g|F = h|F , akkor g ∈ G is teljes¨ ul. Ha az A strukt´ ura ω-kategorikus, akkor ennek a megford´ıtása is igaz: 2.1. t´ etel. Legyen A egy megszámlálható, ω-kategorikus strukt´ ura. Ekkor az A alaphalmaz´ an hat´ o, Aut(A)-t tartalmazó zárt permutációcsoportok éppen az A strukt´ ura reduktjainak automorfizmuscsoportjai, továbbá két redukt automorfizmuscsoportja pontosan akkor egyezik meg, ha ekvivalensek. Ez azt jelenti, hogy egy ω-kategorikus strukt´ ura reduktjai megfeleltethet˝oek az automorfizmuscsoportj´ at tartalmazó zárt permutációcsoportoknak. Egy megsz´ aml´ alhat´ o strukt´ ura ω-kategoricitása könnyen ellen˝orizhet˝o a strukt´ ura automorfizmuscsoportja seg´ıtségével. 2.2. t´ etel. Egy megsz´ aml´ alhat´ o A strukt´ ura pontosan akkor ω-kategorikus, ha az automorfizmuscsoportja Aut(A) oligomorf, azaz minden n ∈ ω esetén véges sok norbitja van A-n. 2.3. k¨ ovetkezm´ eny. Egy megszámlálható ω-kategorikus strukt´ ura redukja is ωkategorikus. Bizony´ıt´ as. Legyen A egy megszámlálható strukt´ ura, és B ennek egy reduktja. Ekkor Aut(B) ⊃ Aut(A), ´ıgy az Aut(B) csoport minden n-orbitja az Aut(A) csoport néh´ any n-orbitj´ anak egyes´ıtése. Ebb˝ol következik, hogy ha az A strukt´ ura automorfizmuscsoportja oligomorf, akkor ez minden reduktjára is igaz. A 2.2. tételt haszn´ alva ebb˝ ol azonnal k¨ ovetkezik az áll´ıtás. 2.4. ´ all´ıt´ as. Legyen V megsz´ amlálhatóan végtelen dimenziós vektortér egy véges test f¨ ol¨ ott. Ekkor V ω-kategorikus. Bizony´ıt´ as. A V strukt´ ura megszámlálható, ezért alkalmazható a 2.2. tétel. Legyen n ∈ ω tetsz˝ oleges, és legyen U egy n dimenziós altere V -nek. Legyenek most v1 , . . . , vn tetsz˝ oleges elemek. Ekkor dim⟨v1 , . . . , vn ⟩ ≤ n, ´ıgy létezik olyan g ∈ Aut V line´ aris leképezés, amire v1g , . . . , vng ∈ U . Ez azt jelenti, hogy az U elemeib˝ol alkotott rendezett n-esek reprezent´ alnak minden n-orbitot. U azonban véges dimenziós tér egy véges test f¨ ol¨ ott, teh´ at véges. Így U n is véges, tehát az n-orbitok száma is véges. 30

2. bizony´ıt´ as. Ez az áll´ıt´ as közvetlen¨ ul a defin´ıcióból is bizony´ıtható. Jelölj¨ uk a V -hez tartoz´ o alaptestet K-val. Tegy¨ uk fel most, hogy W egy megszámlálható modellje V elméletének. Ekkor mivel V vektortér, ezért V elmélete tartalmazza a vektortér axi´ om´ akat is. Ekkor azonban W elmélete is tartalmazza a vektortér axi´ om´ akat, ´ıgy W is vektortér K fölött. Azt kell még belátnunk, hogy dim W = ω. dim W nem lehet véges, mert ha dim W véges lenne, akkor mivel K véges, ezért W is véges lenne, ami nem lehet. Tehát dim W végtelen. Ekkor azonban mivel K véges, ezért ω = |W | = dim W , és ezt kellett bizony´ıtanunk. Ebben a dolgozatban azzal az esettel foglalkozunk, amikor az alaptest K = Fp , ahol p egy p´ aratlan pr´ım. A dolgozat felép´ıtése a következ˝o: A 3. fejezetben azon zárt szupercsoportokat vizsg´ aljuk, amik a 0-t fixálják. Itt definiáljuk a ∼k ekvivalenciarel´ aci´ okat, amik p − 1/k darab k elem˝ u részre osztanak minden 1 dimenziós alteret. Kider¨ ul, hogy a K ω vektortér automorfizmuscsoportjának bármely G 0-t fix´ al´ o z´ art szupercsoportj´ ahoz van olyan k, hogy G hat a ∼k -ekvivalenciaosztályok halmaz´ an, és ez a hat´ as vagy (1) a teljes szimmetrikus csoport, vagy (2) a projekt´ıv line´ aris csoport (és ekkor k = p − 1). A 3.1. alfejezetben megadjuk az (1) esethez tartoz´ o szupercsoportok teljes klasszifikációját. Vég¨ ul a 3. fejezet eredményeit haszn´ alva a 4. fejezetben bebizony´ıtjuk, hogy a vektortérnek pontosan 2 olyan reduktja van, ami a 0-t nem fix´ alja: ezek a végtelen dimenziós affin tér és a megszámlálhatóan végtelen halmaz (strukt´ ura nélk¨ ul).

3. A vektort´ er 0-t fix´ al´ o reduktjai Legyen p ≥ 3 pr´ım, és jel¨ olje V a megszámlálhatóan végtelen dimenziós vektorteret Fp f¨ ol¨ ott. Ebben a fejezetben V automorfizmuscsoportjának azon zárt Aut(V ) ≤ G ≤ Sym(V ) szupercsoportjait vizsgáljuk, amelyek stabilizálják a 0-t. Ehhez el˝oször sz¨ ukség¨ unk lesz néh´ any defin´ıcióra. Tetsz˝oleges k | p − 1 esetén jelölje Γk az Fp -beli k-adik egységgy¨ ok¨ ok által alkotott részcsoportot: Γk = {g ∈ Fp | g k = 1}. Nyilván Γk ≤ F× es |Γk | = k. p ´ 3.1. defin´ıci´ o. Legyen k | p − 1, a, b ∈ V \ 0. Ekkor legyen a ∼k b ha a = λb valamely λ ∈ Γk esetén. Mivel Γk csoport, ∼k ekvivalenciareláció. Valóban: a ∼k a, mert a = 1 · a. Ha a ∼k b, akkor a = λb valamilyen λ ∈ Γk -ra, ´ıgy b = λ−1 a, azaz ∼k szimmetrikus. Ha a ∼k b és b ∼k c, akkor a = λb és b = µc valamely λ, µ ∈ Γk -ra. Mivel Γk csoport, ezért λµ ∈ Γk , ´ıgy a = λµc, tehát a ∼k c és ´ıgy ∼k tranzit´ıv is. A ∼k reláció az egydimenzi´ os altereket p − 1/k darab k elem˝ u osztályra osztja. 3.2. defin´ıci´ o. Legyen G egy tetsz˝oleges csoport, ami hat V \ 0-n: G ≤ Sym(V ) és a, b ∈ V \ 0. Legyen a ∼G b, ha ⟨ag ⟩ = ⟨bg ⟩ minden g ∈ G esetén. Ekkor ∼G ekvivalenciarel´ ació V \ 0-n. Egy a ∈ V \ {0} esetén jelölje ∼G (a) az a vektor ∼G -oszt´ aly´ at. 31

3.3. ´ all´ıt´ as. Legyen Aut(V ) ≤ G ≤ Sym (V )0 tetsz˝oleges csoport. Ekkor ∼G =∼k valamilyen k | p − 1 esetén. Bizony´ıt´ as. Ha Aut(V ) ≤ H ≤ G ≤ Sym (V )0 , akkor ∼G (a) ⊆∼H (a), ´ıgy ∼G (a) ⊆∼Aut(V ) (a) = ⟨a⟩ \ {0} teljes¨ ul. Legyen most Ha = {λ ∈ F× p | a ∼G λa}. Azt áll´ıtjuk, hogy Ha nem f¨ ugg a v´ alasztásától, azaz a, b ∈ V \ {0} esetén Ha = Hb . Tegy¨ uk fel ugyanis, hogy a ∼G λa, de b G λb. Ekkor defin´ıció szerint létezik olyan h ∈ G, hogy ⟨bh ⟩ ̸= ⟨λbh ⟩. Legyen g ∈ Aut(V ) ⊂ G egy olyan lineáris transzformágh ció, amelyre ag = b. Ekkor agh = bh és (λa) = (λbh ), azaz ⟨agh ⟩ ̸= ⟨λagh ⟩, ami ellentmond annak, hogy a ∼G λa. Jelölj¨ uk ezt a közös Ha halmazt Γ-val. Azt áll´ıtjuk, hogy Γ részcsoport F× ıv, 1 ∈ Γ. A szimmetria miatt ha p -ben. Mivel ∼G reflex´ λ ∈ Γ, akkor λa ∼G λ−1 (λa)-ból következik, hogy Γ zárt az inverzképzésre. Vég¨ ul tegy¨ uk fel, hogy µ, λ ∈ Γ, és a ∈ V \ 0 tetsz˝oleges. Ekkor a ∼G λa ∼G µ(λa), ´ıgy a ∼G µλa, ´ıgy µλ ∈ Γ. Teh´ at Γ valóban részcsoportja F× ert ha p -nek, ami ciklikus, ez´ |Γ| = k, akkor k | p − 1 és Γ = Γk . Ebb˝ol pedig következik, hogy u ∼G v pontosan akkor teljes¨ ul, ha van olyan λ ∈ Γ, hogy u = λv, azaz pontosan akkor, ha u ∼k v, és ezt kellett bizony´ıtani. A tov´ abbiakban egy Aut(V ) ≤ G ≤ Sym (V )0 csoport esetén jelölje kG azt a k | p − 1 értéket, amelyre ∼G =∼k . A ∼G reláció defin´ıciójából látható, hogy G meg˝ orzi a ∼G rel´ aci´ ot, ´ıgy G hat a ∼G -ekvivalenciaosztályok halmazán. Ha kG = p − 1, azaz a ∼G -ekvivalenciaosztályok V egydimenziós alterei (a 0 nélk¨ ul), akkor a ∼G -elvivalenciaoszt´ alyok egy megszámlálhatóan végtelen dimenziós Fp feletti projekt´ıv teret alkotnak az ¨ or¨ okölt strukt´ urában. Most azt fogjuk belátni, hogy ha Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, akkor G-re az alábbiak valamelyikre teljes¨ ul: (1) kG = p − 1, és G a P := (V \ 0)/ ∼G projekt´ıv téren a projekt´ıv lineáris transzform´ aci´ ok csoportjaként hat, (2) G a szimmetrikus csoportként hat a ∼G -ekvivalenciaosztályok halmazán. Ezen áll´ıt´ as bizony´ıt´ as´ ahoz el˝oször belátjuk n szerinti indukcióval, hogy ha egy Aut(V ) ≤ G ≤ Sym (V )0 csoportra nem teljes¨ ul a fenti (1) feltétel, akkor n tetsz˝ oleges pont beleképezhet˝ o egy G-beli elemmel V egy elég kicsi” alterébe. ” Az al´ abbi észrevételt sz´ amos alkalommal fogjuk használni. 3.4. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, és legyen S egy véges részhalmaza V -nek. Ekkor egy v ∈ V \ S vektorra az alábbiak ekvivalensek: (1) GS (v) végtelen. (2) GS (v) tartalmaz olyan vektort, ami nincs benne az ⟨S⟩ altérben. (3) GS (v) ⊃ V \ ⟨S⟩. Bizony´ıt´ as. Az (1) → (2) ir´ any nyilvánvaló, hiszen ⟨S⟩ véges. A (3) → (1) irány szintén nyilv´ anval´ o, hiszen V \ ⟨S⟩ végtelen. Tegy¨ uk fel most, hogy v-re teljes¨ ul (2). Ekkor van olyan u ∈ GS (v) vektor, amit nem tartalmaz az ⟨S⟩ altér. Ekkor haszn´ alva, hogy GS tranzit´ıv V \ ⟨S⟩-en, (3) ad´ odik. 32

3.5. defin´ıci´ o. A tov´ abbiakban egy G ≤ Sym (V )0 csoport és egy S ⊂ V részhalmaz esetén jel¨ olje AG (S) azon v ∈ V vektorok halmazát, amelyre S ∪ {v} belekék pezhet˝ o egy G-beli elemmel V egy k dimenziós alterébe. 3.6. lemma. Legyen G ≤ Sym (V )0 egy csoport, és legyen S ⊂ V , |S| = b egy tetsz˝ oleges részhalmaz. Ekkor az alábbiak valamelyike teljes¨ ul: G • Ak (S) = 0, g k • AG es van olyan g ∈ G, amire AG os altere V k (S) = p , ´ k (S) egy k dimenzi´ nek. • AG k (S) = V . Bizony´ıt´ as. Ha az S halmaz nem képezhet˝o bele egy k dimenziós altérbe egy G-beli elemmel, akkor defin´ıci´ o szerint AG uk fel most, hogy nem ez a helyzet, k (S) = ∅. Tegy¨ és legyen ekkor g ∈ G egy olyan transzformáció, amire S g -t tartalmazza V egy U ( g g )g−1 k-dimenzi´ os altere. A defin´ıci´ o ból könnyen látható, hogy AG , k (S) = Ak (S ) g k G g G g ´ıgy elég bel´ atni, hogy AG (S ) = p vagy A (S ) = V . Nyilv´ a n U ⊂ A (S ). Ha k k k g U = AG eszen vagyunk, hiszen |U | = pk , és U egy altér. k (S ), akkor k´ g Ha nem, akkor AG k (S ) tartalmaz olyan v vektort, ami nincs benne U -ban, g teh´ at ⟨S ⟩-ben sincs benne. Ekkor a 3.4. lemma szerint GS g (v) ⊃ V \ ⟨S⟩ ⊃ V \ U, g g g ´ıgy AG attuk, hogy AG ul, ´ıgy AG k (S ) ⊃ V \ U . Azonban l´ k (S ) ⊃ U is teljes¨ k (S ) = V .

3.7. lemma. Legyen G ≤ Sym (V )0 egy csoport, és legyen S ⊂ V , |S| = n egy tetsz˝ oleges részhalmaz. Tegy¨ uk fel továbbá, hogy egy g ∈ G elemre teljes¨ ul, hogy g G G S g ⊂ AG k (S). Ekkor Ak (S) = Ak (S) . G Bizony´ıt´ as. Ha AG all´ıtás nyilvánvaló. Ha nem, k (S) = ∅ vagy A k (S) = V , akkor az ´ h G k G akkor a 3.6. lemma szerint Ak (S) = p , és Ak (S) egy k dimenziós altere V -nek valamilyen h ∈ G-re. Ez azonban azt jelenti, hogy tetsz˝oleges v ∈ AG en k (S) eset´ ( ) g G G g G v ∈ AG k Ak (S) ⊂ Ak (S ) = Ak (S) , G G g g G = pk , ´ıgy hiszen S g ⊂ AG at AG k (S). Teh´ k (S) ⊂ Ak (S) , de Ak (S) = Ak (S) g G G Ak (S) = Ak (S)

A 3.7. lemm´ at által´ aban abban az esetben fogjuk használni, amikor g egy line´ aris transzform´ aci´ o, és S lineárisan f¨ uggetlen elemekb˝ol áll. Ebben az esetben az áll´ıt´ as az alábbi form´ aban is igaz. 3.8. k¨ ovetkezm´ eny. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, és legyen S ⊂ V . Tegy¨ uk fel tovább´ a, hogy x1 , . . . , xm ∈ AG es y1 , . . . , ym ∈ AG arisan k (S) ´ k (S) line´ f¨ uggetlen rendszerek. Ekkor tetsz˝oleges λ1 , . . . , λm ∈ Fp esetén m ∑ i=1

λi xi ∈ AG k (S)

pontosan akkor, ha

m ∑

λi yi ∈ AG k (S).

i=1

33

Bizony´ıt´ as. Legyen S := {a1 , . . . , an }. Az általánosság megszor´ıtása nélk¨ ul feltehet˝ o, hogy y1 = a1 , . . . , ym = am . Mivel x1 , . . . , xm lineárisan f¨ uggetlenek, és dim⟨a1 , . . . , an , x1 , . . . , xm ⟩ ≥ n, ezért létezik olyan {im+1 , . . . , in } ⊂ {1, 2, . . . , n}, hogy x1 , x2 , . . . , xm , aim+1 , . . . , ain lineárisan f¨ uggetlenek. Ekkor létezik olyan g ∈ Aut(V ) ⊂ G line´ aris transzformáció, amire agj = xj , ha 1 ≤ j ≤ m és agj = aij . Ekkor g G S g ⊂ AG etel szerint, ´ıgy a 3.7. lemma szerint AG k (S) a felt´ k (S) = Ak (S) . Mivel g ∑m ∑ g m line´ aris, ezért ekkor i=1 λi ai ∈ AG ul, ha ( i=1 λi ai ) ∈ k (S) pontosan akkor teljes¨ ∑m AG Ismét a linearit´ ast használva ez ekvivalens azzal, hogy i=1 λi agi ∈ AG k (S). k (S), ∑m azaz i=1 λi xi ∈ AG es ezt kellett bizony´ıtanunk. k (S), ´ A tov´ abbiakban t¨ obbsz¨ or fogjuk használni az alábbi affin geometriai tényt, ezért most k¨ ul¨ on is kimondjuk. 3.9. lemma. Legyen A egy véges dimenziós affin tér egy K test felett, ahol char K ̸= 2. Tegy¨ uk fel tov´ abbá, hogy a ∅ ̸= H ⊂ A halmazra teljes¨ ul a következ˝o: ha x, y ∈ H, akkor L(x, y) ⊂ H, ahol L(x, y) jelöli az x és y pontok által kifesz´ıtett egyenest. Ekkor H affin altere A-nak. Vegy¨ uk észre, hogy a 3.9. lemmában tényleg sz¨ ukséges a char K ̸= 2 feltétel. Tegy¨ uk fel ugyanis, hogy K = F2 , és legyen A tetsz˝oleges affin altér F2 felett. Ekkor A tetsz˝ oleges részhalmaz´ ara teljes¨ ul a feltétel, hiszen ekkor tetsz˝oleges x, y ∈ A k¨ ul¨ onb¨ oz˝o pontok esetén L(x, y) = {x, y}. 3.10. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, és legyen S ⊂ V , |S| = n line´ arisan f¨ uggetlen vektorok halmaza. ha AG k (S) tartalmaz egy 0 Ekkor G n−1 n nem átmen˝ o affin egyenest, akkor Ak (S) ≥ p + 1. Speciálisan k < n esetén AG k (S) = V . Bizony´ıt´ as. Legyen S = {a1 , . . . , an }, és legyen L egy affin egyenes, ami nem megy át a 0-n, és L ⊂ AG et tetsz˝oleges (k¨ ulönböz˝o) pont L-en, ekkor k (S). Legyen u, v k´ L = L(u, v). Mivel az L egyenes nem megy át a 0-n, ezért az u és v vekorok line´ arisan f¨ uggetlenek. Legyen most A az a1 , . . . , an pontok által kifesz´ıtett affin altér V -ben, és legyen H := A ∩ AG all´ıtjuk, hogy a H halmazra teljes¨ ulnek k (S). Azt ´ a 3.9. lemma feltételei. Legyenek ugyanis x, y ∈ H tetsz˝olegesek. Azt kell belátnunk, hogy L(x, y) ⊂ A ∩ AG as triviális, mert A affin altér. k (S). Az l(xy) ⊂ A tartalmaz´ Teh´ at már csak azt kell bel´ atnunk, hogy az L(x, y) egyenest tartalmazza AG k (S). Tegy¨ uk fel el˝ osz¨ or, hogy az x és y vektorok lineárisan összef¨ uggenek. Ekkor y = λx valamilyen λ ∈ Fp -re, és ´ıgy 0 ∈ L(x, y). Ekkor azonban 0∑∈ A is teljes¨ ul, n mert ∑ A affin altér. Ez azonban lehetetlen, hiszen A minden eleme i=1 λi ai alak´ u, ahol λi = 1, ami nem lehet 0, mivel az a1 , . . . , an vektorok lineárisan f¨ uggetlenek. Legyenek most x és y line´ arisan f¨ uggetlenek. Azt kell belátnunk, hogy minden λ ∈ Fp -re λx + (1 − λ)y ∈ AG (S). A 3.8. következmény miatt ehhez elég belátni, k ′ hogy vannak olyan x′ és y ′ lineárisan f¨ uggetlen elemek AG k (S)-ben, amire λx + 34

(1 − λ)y ′ ∈ AG ul. Mivel L = L(u, v) ⊂ AG ert az x′ = u és az y ′ = v k (S) teljes¨ k (S), ez´ választ´ as megfelel. Ezzel bel´ attuk, hogy a H halmazra teljes¨ ulnek a 3.9. lemma feltételei, ´ıgy a 3.9. lemma szerint H affin altér. Mivel H tartalmazza az a1 , . . . , an vektorokat, ezért csak H = A lehetséges. Azt kaptuk tehát, hogy az a1 , . . . , an vektorok által kifesz´ıtett affin alteret tartalmazza AG arisan f¨ uggetk (S). Mivel ezek a vektorok line´ lenek, ezért affin f¨ uggetlenek is, ´ıgy ezen altér számossága pn−1 . Amint már láttuk, G ez az altér nem tartalmazza a 0-t. A 0-t azonban mindig tartalmazza ha G A k (S), G n−1 nem u + 1. Vég¨ ul ha n ≥ k + 1, akkor Ak (S) > pk , és ¨res, ´ıgy Ak (S) ≥ p ekkor a 3.6. lemma szerint csak AG eges. k (S) = V lehets´ A k¨ ovetkez˝ o áll´ıt´ as bizony´ıtásához sz¨ ukség¨ unk lesz az alábbi technikai jelleg˝ u lemm´ ara. 3.11. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, és legyen S ⊂ V , |S| = n line´ arisan f¨ uggetlen vektorok halmaza. Tegy¨ uk fel továbbá, hogy az AG k (S) halmaz tartalmaz egy n ∑ v= λi ai ∈ AG k (G) i=1

alak´ u vektort valamilyen λi -kre, ahol a λi egy¨ utthatók köz¨ ul legalább 2 nem 0, és nem mindegyik −1. Ekkor léteznek olyan b1 , . . . , bn , w ∈ AG k (S) vektorok, amelyekre b1 , . . . , bn line´ arisan f¨ uggetlenek, w ∈ / ⟨b1 + b2 + . . . + bn ⟩, és w ∈ / ⟨bi , bj ⟩ semmilyen i, j-re. Bizony´ıt´ as. Ha a bi = ai , v = w választás jó, akkor készen vagyunk. Tegy¨ uk fel ezért, hogy nem ez a helyzet. Ekkor v = λ(a1 + a2 + . . . + an ) valamilyen λ ̸= −1-re vagy v ∈ ⟨ai , aj ⟩ valamilyen 1 ≤ i < j ≤ n indexekre. Tegy¨ uk fel el˝oször, hogy v = λ(a1 + a2 + . . . + an ) valamilyen λ ̸= −1-re. Ebben az esetben a1 = λ1 v − a2 − . . . − an , ´ıgy mivel n ≥ 3 és λ1 ̸= −1, ezért ekkor a b1 = v, b2 = a2 , . . . , bn = an , w = a1 választ´ as megfelel a feltételeinknek. Maradt az az eset, amikor v ∈ ⟨ai , aj ⟩ teljes¨ ul valamilyen 1 ≤ i < j ≤ n-re. Ebben az esetben v = λai + µaj alak´ u, ahol λ, µ ̸= 0. Mivel n ≥ 3, ezért létezik egy l ̸= i, j index. Legyen ekkor w = λai + µaj . A 3.8. következmény szerint w ∈ AG k (S). Legyen most bi = λai + µaj , és legyen bm = am , ha m ̸= i. Ekkor b1 , . . . , bn , w ∈ AG es mivel λ ̸= 0, ezért a b1 , . . . , bn vektorok lineárisan f¨ uggetlenek, továbbá k (S), ´ w = λai + µal = λai + µaj + µ(al − aj ) = bi + µbl − µbj . Ezt azt jelenti, hogy a b1 , . . . , bn , w vektorok ezen választása megfelel a feltételeinknek, hiszen µ ̸= 0, és p ≥ 3 miatt 1 = µ = −µ nem lehetséges. Tegy¨ uk fel, hogy G ≤ Sym (V )0 egy olyan csoport, amire teljes¨ ul, hogy tetsz˝ oleges a1 , . . . , an nem nulla elemek beleképezhet˝oek egy k dimenziós W altérbe k egy G-beli transzform´ aci´ oval valamilyen k-ra. Azt áll´ıtjuk, hogy ekkor n ≤ pk−1 . G Ekkor ugyanis az a1 , . . . , an vektorokkal egy¨ utt a ∼G (ai ) osztály minden eleme is beleképz˝ odik az altérbe. Mivel ezen osztályok diszjunktak, és 0 ∈ W , a ∼G (ai ) 35

oszt´ alyok elemsz´ ama kG , az nkG + 1 ≤ |W | = pk becslés adódik, azaz átrendezve k n ≤ pk−1 . G Azt kaptuk teh´ at, hogy pk−1 egy olyan n lehetséges legnagyobb értéke, amire G minden V -beli n-es beleképezhet˝o V egy k dimenziós alterébe egy G-beli transzform´ aci´ oval. A tov´ abbiakban majd belátjuk, hogy bizonyos feltételek mellett ez az érték majdnem” el is érhet˝o. ” k

3.12. ´ all´ıt´ as. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, amire kG < p − 1; vagy kG = p − 1 és G hat´ asa a P := (V \ 0)/ ∼G projekt´ıv téren nem a projekt´ıv line´ aris transzform´ aci´ ok csoportja. Tegy¨ uk fel továbbá, hogy az n ≥ 3, és legyen k k a legkisebb olyan egész sz´ am, amire teljes¨ ul, hogy k ≥ 2 és n ≤ pk−1 − 1. Ekkor G tetsz˝ oleges S ⊂ V , |S| = n halmaz beleképezet˝o V egy k dimenziós alterébe egy G-beli elemmel. Bizony´ıt´ as. Az áll´ıt´ ast n szerinti teljes indukcióval bizony´ıtjuk. Tegy¨ uk fel el˝oször, hogy n = 3. Ekkor elég bel´ atni, hogy 3 lineárisan f¨ uggetlen elem beleképezhet˝o V egy 2 dimenzi´ os alterébe egy G-beli elemmel. 1/a eset: n = 3 és kG = p − 1. Tekints¨ uk ekkor G hatását a P := (V \ 0)/ ∼G projekt´ıv téren. A feltétel szerint ez nem a projekt´ıv lineáris csoport, legyen tehát g ∈ G egy olyan elem, aminek a hatása a P projekt´ıv téren nem projektivitás. A projekt´ıv geometria alaptétele szerint egy Sym(P )-beli permutáció pontosan akkor projektivit´ as, ha tartja az egyenesket, ´ıgy van olyan L ⊂ P projekt´ıv egyenes, amire Lg nem projekt´ıv egyenes. Legyen U az L egyeneshez tartozó 2 dimenziós altér V -ben. Ekkor teh´ at dim⟨U g ⟩ ≥ 3, ´ıgy vannak olyan a, b, c ∈ U g ⊂ V lineárisan −1 −1 −1 f¨ uggetlen elemek, amikre ag , bg , cg vektorokat tartalmazza az U 2 dimenziós altér. Mivel Aut(V ) (és ´ıgy G is) tranzit´ıvan hat a V -beli lineárisan f¨ uggetlen h´ armasok halmaz´ an, ´ıgy tetsz˝oleges lineáris f¨ uggetlen hármas beleképezhet˝o egy 2 dimenzi´ os altérbe. 1/b eset: n = 3 és kG < p − 1. Ekkor léteznek olyan 0 ̸= a, b ∈ V elemek, amikre ⟨a⟩ = ⟨b⟩, de a G b. Ekkor tehát ag , bg lineárisan f¨ uggetlenek valamilyen g ∈ G esetén. Legyen c egy az ag és bg -t˝ol f¨ uggetlen vektor V -ben. Ekkor tehát az ag , bg , c line´ arisan f¨ uggetlen vektorokat a g −1 ∈ G transzformáció V egy 2 dimenziós alterébe képezi. Az Aut(V ) csoport (és ´ıgy G is) azonban tranzit´ıvan hat a V -beli line´ arisan f¨ uggetlen h´ armasok halmazán, ´ıgy tetsz˝oleges lineáris f¨ uggetlen hármas beleképezhet˝ o egy 2 dimenzi´ os altérbe. 2. eset: n > 3. Tegy¨ uk fel most, hogy teljes¨ ul az áll´ıtás n-re. Belátjuk, hogy ekkor k n + 1-re is teljes¨ ul. Legyen k a legkisebb olyan egész, amire k ≥ 2 és n ≤ pk−1 − 1. G Ha n + 1 >

pk −1 kG

− 1, akkor készen vagyunk, hiszen ekkor a legkisebb olyan k ′ egész,

amire k ′ ≥ 2 és n + 1 ≤ pk −1 kG

′

pk −1 kG

− 1 is teljes¨ ul, az legalább k + 1. Tegy¨ uk fel most,

hogy n + 1 ≤ − 1, azaz n ≤ pk−1 − 2. Ekkor azt kell belátnunk, hogy tetsz˝oleges G T ⊂ V, |T | = n + 1 esetén a T halmaz beleképezhet˝o egy k dimenziós altérbe egy G-beli transzform´ aci´ oval. 36

k

Tegy¨ uk fel, hogy ez nem teljes¨ ul, és legyen ekkor T olyan ellenpélda, amire dim⟨T ⟩ maxim´ alis. ⟨ ⟩ 2/a eset: dim⟨T ⟩ ≤ n. Ekkor van olyan v ∈ T , hogy T \ {v} = ⟨T ⟩. Az indukciós ( )g feltétel szerint van olyan g ∈ G, hogy T \ {v} -t tartalmazza V egy k dimenziós ( )g altere. Ekkor azonban v nem lehet benne ebben az altérben, ´ıgy v g ∈ / ⟨ T \ {v} ⟩, amib˝ ol a 3.4. lemma szerint |G(T \{v})g (v g )| = ∞, és ´ıgy |GT \{v} (v)| = ∞ is teljes¨ ul. Ebb˝ ol k¨ ovetkezik szintén a 3.4. lemma szerint, hogy van olyan h ∈ G, ami ⟨ ⟩ stabiliz´ alja a T \ {v} halmazt, de v h ∈ / T \ {v} . Ez azt jelenti, hogy dim⟨T h ⟩ = dim⟨T, v h ⟩ > dim⟨T ⟩. Mivel dim⟨T ⟩ maximális, ezért létezik olyan h′ ∈ G transzform´ aci´ o, ami a T h halmazt egy k dimenziós altérbe viszi. Ekkor azonban a hh′ ∈ G transzform´ aci´ o egy legfeljebb k dimeziós altérbe viszi T -t, ami ellentmondás.

2/b eset: dim⟨T ⟩ = n + 1. Legyen most S := T \ {v} valamilyen v ∈ T -re. Ekkor |S| = n, és S line´ arisan f¨ uggetlen rendszer. A feltétel szerint v ∈ / AG ıgy k (S), ´ G G k G Ak (S) ̸= V . A 3.6. lemma szerint ekkor Ak (S) ≤ p . Ha u ∈ Ak (S), akkor az AG (S) k halmaz defin´ıci´ oja szerint GS (u) ⊂ AG alisan GS (u) véges. Ekkor k (S), speci´ a 3.4. lemma szerint u ∈ ⟨S⟩. Tehát AG arom alesetet k¨ ulönböztet¨ unk k (S) ⊂ ⟨S⟩. H´ meg. 2/b/1 aleset: λai ∈ AG / ΓkG ∪ {0} és i = 1, 2, . . . , n esetén. Lek (S) valamilyen λ ∈ gyen Sj := S ∪ {λai } \ {aj } minden j ̸= i esetén. Ekkor minden j ̸= i-re aj ∈ / ⟨Sj ⟩, ´ıgy a 3.4. lemma szerint GSj (aj ) = ∞. Mivel λ ∈ / ΓkG ∪ {0}, ezért 0 ̸= λai ai , azaz létezik olyan g ∈ G g transzform´ aci´ o, amire agi és (λai ) lineárisan f¨ uggetlenek. Válasszuk meg ezt a g ( )g transzform´ aci´ ot u ´gy, hogy dim ⟨ S ∪ {λai } ⟩ maximális legyen. Azt áll´ıtjuk, hogy ( )g ( )g ekkor dim ⟨ S ∪ {λai } ⟩ = n + 1, azaz az S ∪ {λai } halmaz elemei lineárisan ( )g f¨ uggetlenek. Tegy¨ uk fel ugyanis, hogy dim ⟨ S ∪ {λai } ⟩ ≤ n. Ekkor mivel agi és ⟨ ⟩ g (λai ) line´ arisan f¨ uggetlenek, ezért létezik olyan j ̸= i, hogy ⟨Sjg ⟩ = Sj ∪ {aj } = ( ) ⟨ S ∪ {λai } g ⟩. Ebb˝ol következik, hogy GSj (aj ) = ∞, és ´ıgy GSjg (agj ) = ∞. Ezért ⟨ ⟩ h a 3.4. lemma szerint van olyan h ∈ G, hogy (Sjg ) = Sjg , de ahj ∈ / Sjg . Ebb˝ol ( )gh ( )g dim ⟨ S ∪ {λai } ⟩ = dim ⟨ S ∪ {λai } ⟩ + 1, ( )g ( )g ami ellentmond dim ⟨ S ∪ {λai } ⟩ maximalitás´ anak. Tehát S ∪ {λai } elemei li( g) ne´ arisan f¨ uggetlenek. Megint a 3.4. lemmát használva adódik, hogy |GS g (λai ) | = ∞, ´ıgy GS (λai ) = ∞. Ez azonban lehetetlen, hiszen λai ∈ AG ıgy GS (λai ) ⊂ k (S), ´ AG (S), ami v´ e ges. k ∑n 2/b/2 aleset: v = i=1 λi ai ∈ AG utthat´ ok k¨ oz¨ ul k valamilyen λi -kre, ahol a λi egy¨ legal´ abb 2 nem 0, és nem mindegyik −1. Ebben az esetben a 3.11. lemma szerint léteznek olyan b1 , . . . , bn , w ∈ Ak (S) elemek, amelyekre b1 , . . . , bn lineárisan f¨ uggetlenek, w ∈ / ⟨b1 + b2 + . . . + bn ⟩, és w ∈ / ⟨bi , bj ⟩ semmilyen i, j-re. A 3.8. következményt 37

az a1 , a2 , . . . , an és b1 , b2 , . . . , bn lineáris f¨ uggetlen rendszerekre alkalmazva adódik, hogy létezik olyan w ∈ Ak (S) is, amire w ∈ / ⟨b1 + b2 + . .∑ . + bn ⟩ és w ∈ / ⟨bi , bj ⟩. Rögn z´ıts¨ unk most egy ilyen tulajdonság´ u w-t. Ekkor w = i=1 λi ai alak´ u, ahol a λi egy¨ utthat´ ok k¨ oz¨ ul legal´ abb 3 nem 0, és nem mindegyik egyforma. Legyen tehát 1 ≤ i < j ≤ n olyan indexek, amire λi ̸= λj . Legyen λ := λi − λj ̸= 0. Legyen tovább´ a a′j = ai , a′i = aj és a′l = al minden i, j ̸= l index esetén. Ekkor a 3.8. következményt az a1 , a2 , . . . , an és a′1 , a′2 , . . . , a′n vektorrendszerekre alkalmazva azt kapjuk, hogy ′ AG k (S) ∋ w :=

n ∑

λi a′i =

i=1

n ∑

λi ai + λ(aj − ai ) = w + λ(aj − ai ).

i=1

A feltevés¨ unk szerint w ∈ / ⟨ai , aj ⟩, ´ıgy w, ai , aj ∈ AG arisan f¨ uggetlenek. k (S) line´ Ekkor persze w′ = w + λ(aj − ai ), ai és aj is lineárisan f¨ uggetlenek. Alkalmazzuk most a 3.8. k¨ ovetkezményt a w, ai , aj és w′ , ai , aj vektorrendszerekre. Mivel w + λai + λaj = w′ ∈ AG ert ekkor k (S), ez´ ′′ ′ AG k (S) ∋ w := w + λai + λaj = w + 2λ(ai + aj ).

Ezt az elj´ ar´ ast folytatva adódik, hogy w + sλ(aj − ai ) ∈ AG k (S) minden s ∈ Fp esetén. Mivel λ ̸= 0, ezért ezt azt jelenti, hogy L := {w + µ(aj − ai ) : µ ∈ Fp } ⊂ AG k (S). Mivel azonban w, a1 , a2 line´ arisan f¨ uggetlenek, ´ıgy L egy 0-n nem átmen˝o affin Ak (S) ≥ pn−1 + 1. Azonban már láttuk, hogy egyenes, ´ ıgy a 3.10. lemma szerint Ak (S) ≤ pk , ´ıgy pn−1 < pn−1 + 1 ≤ pk , azaz n − 1 < k. A k szám a defin´ıciója alapj´ an a legkisebb olyan pozit´ıv egész, amire k ≥ 2 és n ≤ pk−1 − 1 teljes¨ ulnek. G Ez azt jelenti, hogy a k ′ = n − 1 választás t´ ul kicsi”, azaz ekkor a k ′ ≥ 2 és ” k′ az n ≤ p kG−1 − 1 egyenl˝ otlenségek valamelyike nem teljes¨ ul. Mivel n ≥ 3, ´ıgy a k ′ = n − 1 ≥ 2 egyenl˝ otlenség teljes¨ ul. Tehát k

′

pk − 1 pn−1 − 1 n> −1= −1≥ kG kG ≥

( ) pn−1 − 1 − 1 = 1 + p + p2 + . . . + pn−2 − 1 ≥ p−1

≥ p + p2 (1 + p + . . . + pn−4 ) ≥ 3 + (n − 3) = n, hiszen p ≥ 3, ami ellentmond´ as. 2/b/3 aleset: Minden AG u valamilyen λ ∈ ΓkG és k (S)-beli elem vagy v = λai alak´ 1 ≤ i ≤ n-re, vagy v ′ = λ(a1 + a2 + . . . + an ) alak´ u, ahol λ ∈ {0, −1}. Ez a feltétel pontosan azt jelenti, hogy az AG k (S) halmazt tartalmazza a H := {λai : 1 ≤ i ≤ n, λ ∈ ΓkG } ∪ {0, −a1 − a2 − . . . − an } 38

halmaz. Mivel |ΓkG | = kG , ezért a H halmaz számossága nkG + 2. Ekkor az n ≤ pk −1 otlenséget használva kG + 2 egyenl˝ G Ak (S) ≤ |H| = nkG + 2 ≤ pk − 1 − 2kG + 2 ≤ pk − 1 < pk k ad´ odik, ami ellentmond´ as, hiszen feltett¨ uk, hogy AG k (S) = p . Teh´ at minden esetben ellentmondáshoz vezetett a feltevés¨ unk, ´ıgy valóban tetsz˝ oleges T ⊂ V , |T | = n + 1 halmaz beleképezhet˝o egy k dimenziós altérbe egy G-beli transzform´ aci´ oval, és ezt kellett bizony´ıtanunk.

3.13. k¨ ovetkezm´ eny. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, amire kG < p − 1; vagy kG = p − 1 és G hatása a P := (V \ 0)/ ∼G projekt´ıv téren nem a projekt´ıv line´ aris transzform´ aci´ ok csoportja. Legyen továbbá k ≥ 2 tetsz˝oleges egész. k Ekkor tetsz˝ oleges S ⊂ V , |S| = pk−1 − 1 halmaz beleképezet˝o V egy k dimenziós G alterébe egy G-beli elemmel. Bizony´ıt´ as. Alkalmazzuk a 3.12. áll´ıtást n :=

pk −1 kG

− 1 esetén.

3.14. ´ all´ıt´ as. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, amire kG < p − 1; vagy kG = p − 1 és G hat´ asa a P := (V \ 0)/ ∼G projekt´ıv téren nem a projekt´ıv lineáris transzform´ aci´ ok csoportja. Ekkor tetsz˝oleges k ≥ 2 pozit´ıv egészre a G csoport pk −1 ıvan hat a ∼G -ekvivalenciaosztályok halmazán. kG − 1-szeresen tranzit´ Bizony´ıt´ as. Legyen k ≥ 2 és n := pk−1 − 1. Mivel Aut(V ) (és ´ıgy G is) tranzit´ıvan G hat a line´ arisan f¨ uggetlen n-esek halmazán, ezért az áll´ıtáshoz elég belátni, hogy tetsz˝ oleges n (k¨ ul¨ onb¨ oz˝ o) ekvivalenciaosztály átvihet˝o n f¨ uggetlen vektorhoz tartoz´ o ekvivalenciaoszt´ alyba egy G-beli transzformációval. Ehhez elég belátni, hogy tetsz˝ oleges a1 , . . . , an p´ aronként inekvivalens elemek átvihet˝ok n lineárisan f¨ uggetlen elembe egy G-beli transzformációval. Legyenek teh´ at a1 , . . . , an ∈ V \ 0 páronként inekvivalens elemek, és b1 , . . . , bn ∈ V \ 0 line´ arisan f¨ uggetlen elemek. A 3.13. következmény szerint ekkor léteznek olyan g, h ∈ G transzform´ aci´ ok, amire az {ag1 , . . . , agn } és a {bh1 , . . . , bhn } halmazt is tartalmazza V egy k dimenzi´ os altere. Mivel Aut(V ) (és ´ıgy G is) tranzit´ıvan hat V k dimenzi´ os alterein, azért feltehet˝o, hogy az el˝obbi két k dimenziós altér megegyezik. Jel¨ olj¨ uk ezt az alteret U -val. Minden egydimenziós altér pontosan p−1 kG darab ∼G -ekvivalenciaoszt´ aly és a {0} uniója, ´ıgy V minden k dimenziós altere pk −1 p−1 pk −1 darab ∼G -ekvivalenciaosztály és a {0} uniója. A ∼G reláció p−1 · kG = kG defin´ıci´ oj´ ab´ ol adódik, hogy az {ag1 , . . . , agn } és a {bh1 , . . . , bhn } halmaz elemei páronként inekvivalensek. Ez azonban azt jelenti, hogy léteznek olyan u, v ∈ U \ 0 vektorok, hogy {ag1 , . . . , agn , u} és a {bh1 , . . . , bhn , v} halmazok is az U \ 0 halmazbeli ekvivalenciaoszt´ alyok egy teljes reprezentációs rendszerét adják. Legyen most γ ∈ Aut(V ) ⊂ G egy olyan lineáris transzformáció, ami fixálja az U alteret, mint gγ halmazt, és az uγ = v. Ekkor azonban az agγ o ek1 , . . . , an vektorokhoz tartoz´ h h vivalenciaoszt´ alyok halmaza megegyezik a b1 , . . . , bn vektorokhoz tartozó ekvivalenciaoszt´ alyok halmaz´ aval. Ez azt jelenti, hogy létezik az 1, 2, . . . , n indexeknek h egy olyan π ∈ Sn permut´ aci´ oja, amire agγ i ∼G bπ(i) minden 1 ≤ i ≤ n-re. Ekkor k

39

azonban agγh i −1

−1

∼G bπ(i) . Speciálisan, léteznek olyan λ1 , . . . , λn ∈ F× amok, hogy p sz´

agγh = λi bπ(i) minden 1 ≤ i ≤ n-re. A jobb oldalon álló vektorok azonban linei árisan f¨ uggetlenek, hiszen a feltétel szerint b1 , . . . , bn lineárisan f¨ uggetlenek. Tehát a gγh−1 ∈ G transzform´ aci´ o bizony´ıtja az áll´ıtást. A fejezet f˝ otételének bizony´ıtásához sz¨ ukség¨ unk lesz még az alábbi lemmára. 3.15. lemma. Tegy¨ uk fel, hogy G ⊂ Sym(H) egy zárt csoport, ahol |H| = ω, és legyen ∼ egy ekvivalenciarel´ aci´ o H-n, amire minden ∼-ekvivalenciaosztály véges. Tegy¨ uk fel tov´ abb´ a, hogy G kompatibilis a ∼ ekvivalenciarelációval, azaz x ∼ y pontosan akkor teljes¨ ul, ha xg ∼ y g . Ekkor G hatása a ∼-ekvivalenciaosztályok halmaz´ an is zárt. Bizony´ıt´ as. Legyen g ∈ Sym(H/ ∼) tetsz˝oleges, amire teljes¨ ul, hogy tetsz˝oleges ˜ ∈ G, amire h ˜ és g hatása megegyezik F ⊂ H/ ∼ véges halmaz esetén van olyan h F -en. Be kell l´ atnunk, hogy ekkor létezik olyan a g˜ ∈ G transzformáció is, amire g˜ és g hat´ asa megegyezik az o ¨sszes ∼-ekvivalenciaosztályok halmazán. Egy F ⊂ H/ ∼ esetén jel¨ olje F˜ az F -beli ekvivalenciaosztályok unióját. Ekkor ˜ ha F véges, akkor F is. Legyen X1 , X2 , . . . a ∼G ekvivalenciaosztályok egy felsorol´ asa. Legyen Fi := {X , X2 , . . . , Xn }. Ekkor az Fi halmazok ∪végesek, ∅ = F0 ⊂ ∪1∞ ∞ F1 ⊂ F2 ⊂ F3 ⊂ . . ., és i=0 Fi = H/ ∼. Mivel g bijekció, ezért i=0 Fig = H/ ∼ is teljes¨ ul. Ezekb˝ ol k¨ ovetkezik az is, hogy ∞ ∪

∞ ∪

Xi =

i=1

Xig = H.

i=1

Defini´ aljuk a T gy¨ okeres fát a következ˝oképpen. Jelölje Tn a T gyökeres fa n-edik szintjét. Ekkor minden n-re a Tn -en lév˝o cs´ ucsok legyenek az olyan f f¨ ugg˜ ∈ G f¨ ˜ ˜ = h, továbbá vények, amikre D(f ) = Fñ , és létezik olyan h uggvény, amire h| Fi ˜ és g hat´ h asa megegyezik a H/ ∼ halmazon. A T gráfban az f1 ∈ Tn−1 és f2 ∈ Tn cs´ ucsok k¨ oz¨ ott vezessen él, ha f2 |Fñ = f1 . Ekkor az egyetlen T0 -beli cs´ ucs az u ¨res f¨ uggvény, jel¨ olj¨ uk ezt most f0 -lal. Ez lesz a T gyökeres fa gyökere. A defin´ıcióból k¨ onnyen l´ athat´ o, hogy ebben a gráfban ha f ∈ V (Tn ), akkor f0 -ból pontosan egy u ´t vezet f -be, nevezetesen ( ) f0 = f |F˜0 , f |F˜1 , . . . , f |Fñ−1 , f . A T gr´ af teh´ at valóban fa. Azt áll´ıtjuk, hogy létezik az f0 cs´ ucsból induló végtelen u ´t T -ben. Ehhez a K¨ onig-lemma feltételeit fogjuk ellen˝orizni. (1) Létezik ak´ armilyen hossz´ u f0 -b´ ol indul´ ou ´t. Ehhez elég belátni, hogy Tn nem ˜ egy olyan f¨ u at n tetsz˝oleges, és legyen ekkor h uggvény, ¨res minden n-re. Legyen teh´ ˜ és g hat´ ˜ Legyen amire h asa megegyezik Fn -en. A feltételeink szerint létezik ilyen h. ˜ ˜ = f . Ekkor Tn defin´ıciója szerint f ∈ V (Tn ). most h| Fn (2) Minden T -beli cs´ ucs kifoka véges. Ennél többet fogunk bizony´ıtani, belátjuk ugyanis, hogy T v´ e ges minden n-re. Tegy¨ uk fel, hogy f ∈ Tn . Ekkor D(f ) = Fñ = n ∪n es a feltétel szerint i=1 Xi , ´ R(f ) ⊂

n ∪ i=1

40

Xif =

n ∪ i=1

Xig .

∪n ∪n g Az i=1 Xi → i=1 Xig f¨ uggvények száma azonban ∪ véges, hiszen ∪naz X1 , . . . , Xn , X1 , n g . . . , Xn ekvivalenciaoszt´ alyok végesek, és ekkor az i=1 Xi és i=1 Xi halmazok is végesek. Teh´ at a T gy¨ okeres fára (ahol f0 a gyökér) valóban teljes¨ ulnek a König-lemma feltételei. Ekkor a K¨ onig-lemma szerint létezik az f0 cs´ ucsból induló végtelen u ´t ñ , és j > i esetén T -ben. Legyen ez (f0 , f1 , . . .). Ekkor f ∈ T , ´ ıgy D(f ) = F n n n ∪∞ fj |F˜i = fi . Ebb˝ ol k¨ ovetkezik, hogy i=0 fi is f¨ uggvény. Legyen ez f . Ekkor D(f ) =

∞ ∪

D(fi ) =

i=0

R(f ) =

∞ ∪ i=0

∞ ∪

D(fi ) =

i=0

R(fi ) =

∞ ∪ i=0

∞ ∪

Xi = H,

i=0

R(fi ) =

∞ ∪

Xig = H.

i=0

Tegy¨ uk fel most, hogy u ̸= v ∈ H. Ekkor van olyan n, hogy u, v ∈ D(fn ) = Fñ . ˜ ∈ G egy olyan f¨ ˜ ˜ = fn . Ekkor mivel h ˜ bijekció, Legyen most h uggvény, amire h| Fn ˜

˜

ezért uh ̸= v h , amib˝ ol ufn ̸= v fn , és ´ıgy uf ̸= v f . Az f f¨ uggvény tehát egy H → H bijekci´ o. Bel´ atjuk most, hogy f ∈ G. Ehhez G zártsága miatt elég belátni, hogy H ˜ ∈ G f¨ ˜ ˜ = tetsz˝ oleges F véges részhalmazához létezik olyan h uggvény, amire h| Fn fn = f |Fñ . Legyen teh´ at F egy tetsz˝oleges véges részhalmaza H-nak. Ekkor van olyan n, hogy F ⊂ D(fn ) = Fñ , és ekkor az fn f¨ uggvény defin´ıciója miatt létezik ˜ ∈ G f¨ ˜ ˜ = fn = f | ˜ . h uggvény, amire h| Fn Fn Azt áll´ıtjuk most, hogy a g˜ = f választás jó lesz, azaz f és g hatása megegyezik a H/ ∼ halmazon. Legyen ugyanis Xi ∈ H/ ∼ tetsz˝oleges. Ekkor j ≥ i esetén az fj f f¨ uggvények defin´ıci´ oja miatt Xi j = Xig , és ´ıgy Xif = Xig . 3.16. t´ etel. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport. Ekkor az alábbiak valamelyike teljes¨ ul: (1) kG = p − 1, és G a P := (V \ 0)/ ∼G projekt´ıv téren a projekt´ıv lineáris transzform´ aci´ ok csoportjaként hat, (2) G teljes szimmetrikus csoportként hat a ∼G -ekvivalenciaosztályok halmazán. Bizony´ıt´ as. Tegy¨ uk fel, hogy a G csoportra nem teljes¨ ul az (1) feltétel. Be kell látni, hogy ekkor G szimmetrikus csoportként hat a ∼G -ekvivalenciaosztályok halmaz´ an. Ha G-re nem teljes¨ ul az (1) feltétel, akkor a 3.7. áll´ıtás szerint a G csoport pk −1 − 1-szeresen tranzit´ ıv a ∼G -ekvivalenciaosztályok halmazán minden k ≥ 2-re. kG Mivel pk−1 − 1 érték tetsz˝ oleges nagy lehet, ezért ebb˝ol következik az is, hogy G G minden n-re n-tranzit´ıvan hat a ∼G -ekvivalenciaosztályok halmazán, tehát G hatása s˝ ur˝ u a ∼G -ekvivalenciaosztályok halmaz´ an. Be kell még látnunk, hogy ez a hatás zárt is. Ez a 3.15. lemma szerint teljes¨ ul, hiszen G kompatiblis a ∼G rel´ acióval, és minden ∼G ekvivalenciaosztály véges. k

41

A kés˝ obbiekben még sz¨ ukség¨ unk lesz a 3.16. tétel áll´ıtására a kG = 1 esetben, ezért ezt k¨ ul¨ on is kimondjuk. 3.17. k¨ ovetkezm´ eny. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, amire kG = 1. Ekkor G = Sym0 (V ). Bizony´ıt´ as. Mivel p ≥ 3, ezért kG = 1 ̸= p − 1, tehát ekkor a G csoportra 3.16. tételbeli (2) feltétel teljes¨ ul. kG = 1 esetén defin´ıció szerint a ∼G ekvivalenciaosztályok egyelem˝ uek, teh´ at ekkor G a szimmetrikus csoportként hat V \ 0-n, azaz G = Sym0 (V ).

3.1. Azon z´ art csoportok le´ır´ asa, amik a teljes szimmetrikus csoportk´ ent hatnak a ∼G -ekvivalenciaoszt´ alyok halmaz´ an. Ebben a fejezetben megadjuk a klasszifikációját azon Aut(V ) ≤ G ≤ Sym (V )0 zárt csoportoknak, amikre a 3.16. tétel (2) feltétele teljes¨ ul, azaz amikre G hatása a ∼G -ekvivalenciaoszt´ alyok halmazán a teljes szimmetrikus csoport. Ezen csoportok le´ır´ as´ ahoz sz¨ ukség¨ unk lesz a k¨ ovetkez˝o defin´ıciókra. 3.18. defin´ıci´ o. Legyen k | p − 1 tetsz˝oleges. Ekkor egy f : V \ 0 → Γk f¨ uggvényt k-c´ımkézésnek h´ıvunk, ha tetsz˝oleges u ∈ V \ 0 és λ ∈ Γk esetén f (λu) = λf (u). A defin´ıci´ ob´ ol k¨ onnyen l´ atható, hogy a V \ 0 halmaz k-c´ımkézései természetes m´ odon megfeleltethet˝ oek a ∼k -ekvivalenciaosztályok egy reprezentánsrendszerével. Ebb˝ ol speci´ alisan az is k¨ ovetkezik, hogy minden k | p − 1-re van c´ımkézése V \ 0-nak. A megfeleltetés a k¨ ovetkez˝ o: ha adott egy f c´ımkézés, akkor az 1 elem f szerinti ˝osképe egy reprezent´ ansrendszer. Megford´ıtva: ha adott egy X reprezentánsrendszere a ∼k -ekvivalenciaoszt´ alyoknak, akkor minden v ∈ V \ 0 esetén legyen f (v) értéke az{az egyetlen λ, amire}v = λv ′ alak´ u valamilyen v ′ ∈ X esetén. A továbbiakban a v ∈ V \ 0 : f (v) = 1 halmazt jelölj¨ uk V f -fel. 3.19. defin´ıci´ o. Legyen k | p − 1 tetsz˝oleges, és f egy k-c´ımkézés V \ 0-n. Ekkor egy g ∈ Sym (V )0 permut´ aci´ or´ ol azt mondjuk, hogy az f k-c´ımkézéssel kompatibilis, ha g meg˝ orzi a ∼k rel´ aci´ ot, és f (v g ) = f (v) minden v ∈ V \ 0-ra. 3.20. defin´ıci´ o. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy csoport, legyen továbbá f egy tetsz˝ oleges kG -c´ımkézés V \ 0-n. Jelölje ekkor Gf azon g ∈ G elemek részcsoportj´ at, amik kompatibilisek f -fel. 3.21. defin´ıci´ ( o. Legyen k)| p − 1 tetsz˝oleges, és f egy k-c´ımkézés V \ 0-n. Ekkor egy g ∈ Sym (V \ 0)/ ∼k elem esetén jelölje g f azt az egyértelm˝ u g˜ ∈ Sym (V )0 elemet, amire g˜ kompatibilis az f k-c´ımkézéssel, és g és g˜ hatása megegyezik a ∼k ekvivalenciaoszt´ alyok halmaz´ an. ( ) Egy H ≤ Sym (V \ 0)/ ∼k részcsoport esetén legyen H f = {g f : g ∈ H}. 42

A 3.22–3.26. lemm´ akban a c´ımkézések seg´ıtségével le´ırjuk azon Aut(V ) ≤ G ≤ Sym (V )0 z´ art csoportok szerkezetét, amik a szimmetrikus csoportként hatnak a ∼kG -ekvivalenciaoszt´ alyok halmazán. Kider¨ ul, hogy minden ilyen G el˝oáll G∗ · ( )f (Sym (V \ 0)/ ∼kG ) alakban, ahol a G∗ azon G-beli elemek csoportja, amik minden ∼G -ekvivalenciaoszt´ alyt (halmazként) stabilizálnak. Ezut´ an a 3.27–3.34. lemmákban le´ırjuk azon csoportokat, amik el˝oállnak az el˝ obbi G∗ csoportként, és ezzel megkapjuk a teljes klasszifikációt is. Kider¨ ul vég¨ ul, hogy azon Aut(V ) ≤ G ≤ Sym (V )0 zárt csoportok, amik a szimmetrikus csoportként hatnak a ∼k -ekvivalenciaosztályok halmazán bijekcióban állnak a k fok´ u szimmetrikus csoport bizonyos tulajonság´ u (N, H) részcsoportpárjaival. Ez a bijekció nem fog f¨ uggeni att´ ol, hogy melyik c´ımkézést használjuk, azonban a defin´ıciójukban, és a kés˝ obbi bizony´ıt´ asokban végig használni kell valamilyen k-c´ımkézést. Els˝ o lépésként bebizony´ıtjuk, hogy ha Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, ( )f akkor Gf = (Sym (V \ 0)/ ∼kG . 3.22. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, és f egy kG c´ımkézés. Ekkor Gf is z´ art. ( )f Bizony´ıt´ as. A defin´ıci´ ob´ ol l´ atható, hogy Gf = G ∩ (Sym (V \ 0)/ ∼kG , ´ıgy elég ( )f bel´ atni, hogy (Sym (V \ 0)/ ∼kG zárt. Tegy¨ uk fel tehát, hogy g ∈ Sym(V ), és ( )f minden F ⊂ V véges halmazra van olyan h ∈ (Sym (V \ 0)/ ∼kG , hogy g|F = h|F . Be kell látnunk, hogy ekkor g is kompatibilis f -fel. Tegy¨ uk fel tehát, hogy u ∈ V \ 0. Legyen ekkor F = {u}. Erre alkalmazva az el˝obbi észrevételt f (u) = f (uh ) = f (ug ). Mivel ez minden u ∈ V \ 0-ra teljes¨ ul, ezért g kompatibilis f -fel. 3.23. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, és f egy kG -c´ımkézés. Tegy¨ uk fel tov´ abb´ a, hogy Gf tartalmaz egy olyan g elemet, amire a {v ∈ V \ 0 : v ̸= v g } ∩ V f halmaz véges, nem u uggetlenek. Ekkor ¨res, és elemei lineárisan f¨ ( )f Gf = (Sym (V \ 0)/ ∼kG . Bizony´ıt´ as. Egy f kG -c´ımkézéssel kompatibilis permutáció hat a V f = {v ∈ V \ 0 : f (v) = 1} halmazon, tov´ abb´ a egy f -fel kompatibilis g permutációt meghatároz a g permut´ aci´ onak a ∼kG -ekvivalenciaoszályok halmazán való hatása, amit viszont meghat´ aroz g hat´ asa az V f halmazon. Ez ezt jelenti, hogy a lemma áll´ıtásához elég bel´ atni, hogy Gf |V f = Sym(V f ). A 3.22. lemma szerint Gf zárt, ´ıgy Gf |V f is zárt. Ez azt jelenti, hogy a lemma áll´ıtásához elég belátni, hogy a lemma feltételei mellett Gf hat´ asa s˝ ur˝ u a V f halmazon. Ehhez azt fogjuk bizony´ıtani, hogy Gf f hatása a V halmazon tartalmaz minden transzpoz´ıciót. Legyen X egy tetsz˝ oleges végtelen, lineáris f¨ uggetlen elemekb˝ol álló halmaz, ami tartalmazza a {v ∈ V \ 0 : v ̸= v g } ∩ V f halmazt. Legyen SymF (X) azon h ∈ Sym(X) elemek csoportja, amik véges sok kivétellel minden X-beli elemet fixen hagynak, legyen tov´ abb´ a AltF (X) a páros permutációk csoportja SymF (X)-ben. 43

( ) Legyen H := SymF (X) ∩ (Gf )X | , azaz azon h ∈ SymF (X)-ek halmaza, amiket X identit´ asként kiterjesztve V \ X-re egy Gf -beli elemet kapunk. Azt áll´ıtjuk, hogy ekkor a H csoport norm´ aloszt´ o SymF (V f )-ben. Legyen ugyanis h ∈ H, és γ ∈ SymF (X) tetsz˝oleges. Ekkor γ kiterjed V egy automorfizmus´ av´ a, jel¨ olj¨ uk ezt a kiterjesztést is γ-val. Feltehet˝o, hogy ez a kiterjesztés kompatibilis f -fel. Ekkor tehát γ ∈ Aut (V )f ⊂ Gf . Tekints¨ uk ekkor ( ) −1 −1 a γhγ ∈ Sym(X) permut´ aciót. Ekkor γhγ ∈ (Gf )X | , és ekkor γhγ −1 ∈ X ( ) (Gf )X | ∩ SymF (X) = H. Tehát valóban H ▹ SymF (X). Ismert, hogy ekkor X

H = 1 vagy H ⊃ AltF (X). A lemma feltétele szerint a {v ∈ V \ 0 : v ̸= v g } ∩ V f ⊂ X halmaz nem u ¨res, ´ıgy id ̸= g|X ∈ H. Tehát H nem lehet a triviális csoport. ( ) Azt kaptuk teh´ at, hogy H tartalmazza AltF (X)-et. Ekkor persze (Gf )X | X

is tartalmazza AltF (X)-et. Az AltF (X) alternáló csoport azonban s˝ ur˝ u Sym(X)( ) ben. Azt áll´ıtjuk, hogy (Gf )X | zárt is. Ehhez elég belátni, hogy (Gf )X zárt. X Ez teljes¨ ul, hiszen a Gf |V f csoportról láttuk, hogy zárt, és X ⊂ V f . Ebb˝ol kö( ) ( ) vetkezik, hogy (Gf )X | = Sym(X). Speciálisan (Gf )X | tartalmaz minden X X transzpozic´ı´ ot. Ez azt jelenti, hogy minden u, v ∈ X elemre Gf |V f tartalmazza az (uv) transzpoz´ıci´ ot. Ekkor persze Gf |V f bármely u, v ∈ V f lineárisan f¨ uggetlen elemekre tartalmazza az u, v ∈ V f transzpoz´ıciót. Be kell még látnunk, hogy ez akkor is teljes¨ ul, ha u, v ∈ V f nem lineárisan f¨ uggetlenek. Ebben az esetben f legyen w ∈ V \ ⟨u, v⟩ egy tetsz˝oleges vektor. Ekkor (uw), (vw) ∈ Gf |V f , amib˝ol (uv) = (uw)(vw)(uw) ∈ Gf |V f . A Gf |V f csoport tehát valóban tartalmaz minden transzpoz´ıci´ ot, és ezt kellett bizony´ıtanunk. A k¨ ovetkez˝ o áll´ıt´ as bizony´ıtásához sz¨ ukség¨ unk lesz az alábbi jelölésre. 3.24. defin´ıci´ o. Legyen k | p − 1, és legyen g ∈ Sym (V )0 egy tetsz˝oleges elem, ami meg˝ orzi a ∼k -ekvivalenciarel´ aciót. Legyen továbbá f egy tetsz˝oleges k-c´ımkézés V \ 0-n. Ekkor egy v ∈ V \ 0 esetén jelölje σf (g, v) a ( g) λ 7→ f (λ˜ v ) : Γk G → Γ k leképezést, ahol v˜ jel¨ oli az ∼G (v) ekvivalenciaosztály egyetlen olyan elemét, amire v f (v) = 1 (azaz v˜ = f (v) ). Amennyiben ez nem okoz félreértést, a σ leképezésben az f c´ımkézést nem ´ırjuk ki. A defin´ıci´ ob´ ol k¨ onnyen l´ atható, hogy a σ(g, v) leképezés mindig bijekció, és v ∼G v ′ esetén σ(g, v) = σ(g, v ′ ). Ha a g, h ∈ Sym (V )0 elemek meg˝orzik a ∼k relációt, akkor tetsz˝ oleges v ∈ V \ 0 esetén σ(gh, v) = σ(g, v)σ(h, v g ). A k¨ ovetkez˝ o áll´ıt´ asban bel´ atjuk, hogy a 3.23. lemma feltételei valójában automatikusan teljes¨ ulnek minden megfelel˝o G csoportra. 3.25. ´ all´ıt´ as. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, és f egy kG c´ımkézés. ( )f Ekkor Gf = (Sym (V \ 0)/ ∼kG . 44

Bizony´ıt´ as. Ezen áll´ıt´ as bizony´ıtásához a 3.23. lemmát fogjuk használni. Legyenek a1 , a2 , . . . , ap ∈ Vf tetsz˝ oleges lineárisan f¨ uggetlen elemek. A bizony´ıtás további részében az indexeket mod p értj¨ uk. Mivel G a szimmetrikus csoportként hat a ∼kG -ekvivalenciaoszt´ alyok halmazán, ezért van olyan g ∈ G, amire ( )g ∼G (ai ) =∼G (ai+1 ) és bg = b { } minden b ∈ (V \ 0)/ ∼kG \ ∼G (a1 ), ∼G (a2 ), . . . , ∼G (ap ) -re. Legyen σi := σ(g, ai ), és legyen γi egy olyan lineáris transzformáció, amire aγj i = aj+i minden j = 1, 2, . . . , p-re. abb´ a gi := γi−1 ai γi . Ekkor persze az ´ıgy kapott gi{ -kre is tel( Legyen )tov´ gi jes¨ ul, hogy ∼G (aj ) } =∼G (aj+1 ), és bgi = b minden b ∈ (V \ 0)/ ∼kG \ ∼G (a1 ), ∼G (a2 ), . . . , ∼G (ap ) , azaz gi és g hatása megegyezik (V \ 0)/ ∼G -n. Azt áll´ıtjuk, hogy σ(gi , aj ) = σj−i . Val´ oban mivel γi lineáris, ezért tetsz˝oleges j = 1, 2, . . . , p és λ ∈ ΓkG esetén ( ( ) g ) f (λaj ) i = f λagj i = f (λaj+i ) = λ, ´ıgy σ(γi , aj ) = id Γk , amib˝ ol ( ( γ ) γ ) σ(gi , aj ) = σ(γ−i gγi , aj ) = σ(γ−i , aj )σ gγi , aj −i = σ gγi , aj −i = ( ) i = σ(gγi , aj−i ) = σ(g, aj−i )σ γi , aγj−i = σj−i σ(γi , aj ) = σj−i . Legyen most g ′ = g0 g1 , . . . , gkG !−1 ∈ G. Az ´ıgy kapott g ′ hatása a ∼kG ekvivalenciaoszt´ alyok halmaz´ an megegyezik g k! hatásával, és tetsz˝oleges i = 1, 2, . . . , p-re ( ) ( ) ( g0 g1 ,...,gkG !−2 ) σ(g ′ , ai ) = σ(g0 , ai )σ g1 , agi 0 σ g2 , agi 0 g1 . . . σ gkG !−1 , ai = k !

= σ(g0 , ai )σ(g1 , ai+1 ) . . . σ(gkG !−1 , ai+kG !−1 ) = σ(g, ai ) G = id ΓkG , hiszen Sym(ΓkG ) = kG ! Legyen g ′′ = g ′kG !−1 ∈ G. Azt áll´ıtjuk, hogy g ′′ ∈ Gf , azaz minden u ∈ ( Sym (V \ 0)/ ∼kG esetén σ(g, u) = id ΓkG . Tegy¨ uk fel el˝oször, hogy u =∼G (ai ) valamilyen i-re. Ekkor ( ′ ′kg !−1 ) σ(g ′′ , ai ) = σ(g ′ , ai )σ(g ′ , agi ) . . . σ g ′ , agi = = σ(g ′ , ai )σ(g ′ , ai+kG ! ) . . . σ (g ′ , ai+(kG !−1)kG ! ) = id ΓkG . Tegy¨ uk fel most, hogy u k¨ ul¨ onbözik minden ∼G (ai )-t˝ol. Ekkor ( ′ ′kg !−1 ) σ(g ′′ , u) = σ(g ′ , u)σ(g ′ , ug ) . . . σ g ′ , ug = = σ(g ′ , u)

kG !

= id ΓkG , hiszen Sym(ΓkG ) = kG !. A g ′′ ∈ Gf permut´ aci´ o hatása a ∼G -ekvivalenciaosztályok halmazán megegye2 zik g ′kG ! hat´ as´ aval, ami pedig megegyezik g (kG !) hatásával. Ebb˝ol következik, hogy 45

′′

(kG !)2

agi ∼G agi = ai+(kG !)2 G ai , hiszen az a1 , . . . , ap elemek páronként inekviva( 2 ) 2 lensek, és kG < p miatt (kG !) , p = 1, amib˝ol i ̸≡ i + (kG !) mod p. Speciálisan ′′

agi ̸= ai . Ha egy v ∈ V \ 0 elem nincs benne a ∼G (ai ) ekvivalenciaosztályok egyi′′ ′′ kében sem, akkor v g ∼G v. Ekkor azonban mivel g ′′ ∈ Gf , ezért f (v g ) = f (v) is ′′ teljes¨ ul, ami csak v g = v esetén lehetséges. Tehát a g ′′ ∈ Gf permutációra {v ∈ V \ 0 : v ̸= v g } ∩ V f = {a1 , . . . , ap }. Ez a halmaz véges és nem u ¨res, ´ıgy a 3.23. lemma szerint ( )f Gf = (Sym (V \ 0)/ ∼kG . 3.26. k¨ ovetkezm´ eny. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, és f egy ( )f kG -c´ımkézés. Ekkor G = G∗ · (Sym (V \ 0)/ ∼kG alak´ u, ahol { } G∗ = g ∈ G : g identitásként hat (V \ 0)/ ∼kG -n . Bizony´ıt´ as. A ⊃” tartalmaz´ as következik a 3.25. áll´ıtásból. Tegy¨ uk fel most, hogy ” g ∈ G. Ekkor a 3.25. áll´ıt´ as szerint van olyan g ′ ∈ Gf , hogy g és g ′ hatása megegyezik a ∼G -ekvivalenciaoszt´ alyok halmazán. Ekkor g ∗ := gg ′−1 ∈ G∗ , és g = g ∗ g ′ . A 3.26. k¨ ovetkezményb˝ ol következik az is, hogy a G∗ csoport már meghatározza G-t, ´ıgy elég a lehetséges G∗ csoportokat klasszifikálni. A bizony´ıtásból ( )f az is k¨ onnyen l´ athat´ o, hogy a G = G∗ · (Sym (V \ 0)/ ∼kG szorzat valójában ( ) f egy G = G∗ o (Sym (V \ 0)/ ∼kG szemidirekt szorzat. (k)

Egy k | p − 1 sz´ am esetén jelölj¨ uk Sym0 (V )-vel azon permutációk csoportját, (k) amik meg˝ orzik a ∼k rel´ aci´ ot. Ekkor persze Aut(V ) ≤ Sym0 (V ) minden k | p − 1re, és egy Aut(V ) ≤ G ≤ Sym(V ) csoportra pontosan akkor teljes¨ ul kG = k, ha (k) (k′ ) ′ G ≤ Sym0 (V ), de G Sym0 (V ) minden k < k-ra. Legyen (k)

∗

S (k) = (Sym0 (V )) , azaz azon permut´ aci´ ok halmaza, amik minden ∼k ekvivalenciaosztályt önmagukra képeznek. Ekkor egy Aut(V ) ≤ G ≤ Sym (V )0 csoportra G∗ = G ∩ S (kG ) . Ha a g, h elemek az S (k) részcsoportban vannak, akkor tetsz˝oleges v ∈ V \ 0-ra σ(gh, v) = σ(g, v)σ(h, v). Ezt azt jelenti, hogy a S (k) → Sym(Γ), g 7→ σ(g, u) leképezés egy homomorfizmus minden u ∈ V \ 0 esetén. Azt áll´ıtjuk, hogy egy g ∈ S (k) csoportbeli elemet meghatároznak a σ(g, u) homomorfizmusnál vett képei. Val´ oban ha a σ(·, u) homomorfizmusok adottak, akkor egy u ∈ V \ 0 esetén ug = σ(g,u) u f (u) obbi G∗ csoport meghatározásához elég f (u) . Ez azt jelenti, hogy az el˝ ∗ meghat´ arozni, hogy egy G -beli elemnek mik lehetnek a képei a σ(·, u) : u ∈ V \ 0 homomorfizmusokn´ al. 46

(k)

3.27. defin´ıci´ o. Legyen G ≤ Sym0 (V ) egy csoport és f egy k-c´ımkézés. Ekkor egy v ∈ V \ 0 elemre legyen Hv (G) := {σ(g, v) : g ∈ G∗ } és Nv (G) := {σ(g, v) : g ∈ G∗ , σ(g, u) = id Γk minden u k v-re}. A defin´ıci´ ob´ ol l´ athat´ o, hogy Nv (G) és Hv (G) részcsoportjai Sym(Γk )-nak, és Nv (G) ⊂ Hv (G). (k)

3.28. lemma. Legyen G ≤ Sym0 (V ) egy csoport és f egy k-c´ımkézés. Ekkor ha G tartalmazza Aut(V )-t, akkor az Nv (G) és Hv (G) csoportok nem f¨ uggnek a v vektor választ´ as´ atól. Bizony´ıt´ as. Tegy¨ uk fel, hogy Aut(V ) ≤ G. Az áll´ıtást nyilván elég belátni V f -beli vektorokra. Tegy¨ uk fel teh´ at, hogy u, v ∈ V f , és legyen γ ∈ Aut(V ) ≤ G egy lineáris γ transzform´ aci´ o, amire u = v. Tegy¨ uk fel most, hogy egy σ permutáció benne van Hu (G)-ben. Ekkor van olyan g ∈ G∗ , hogy σ(g, u) = σ. Ez esetben a γ −1 ∈ G∗ permutációra σ(γ −1 gγ, v) = σ. Teh´ at Hu (G) ⊂ Hv (g). Hasonlóan Hv (G) ⊂ Hu (G) is teljes¨ ul, ´ıgy Hu (G) = Hv (G). Tegy¨ uk fel, hogy σ ∈ Nu (G). Ekkor van olyan g ∈ G∗ , hogy σ(g, u) = σ és ′ σ(g, u ) = id Γ minden u′ k u esetén. Ez esetben a γ −1 ∈ G∗ permutációra σ(γ −1 gγ, v) = σ és σ(γ −1 gγ, v ′ ) = id Γ minden v ′ k v esetén, ´ıgy Nu (G) ⊂ Nv (G). Hasonl´ oan Nv (G) ⊂ Nu (G). Tehát Nu (G) = Nv (G). (k)

3.29. lemma. Legyen Aut(V ) ≤ G ≤ Sym0 (V ) egy csoport és f egy k-c´ımkézés. Ekkor N (G) ▹ H(G). Bizony´ıt´ as. Legyenek σ ∈ N (G), σ ′ ∈ H(G) tetsz˝olegesek, legyen továbbá u ∈ V \ 0 tetsz˝ oleges. Be kell l´ atnunk, hogy σ ′−1 σσ ′ ∈ N (G). A fel´ırt tartalmazások szerint vannak olyan g, h ∈ G∗ , hogy σ(h, u) =( σ ′ , σ(g, u) és σ(g, u′ ) = id(G) min) = σ′−1 ′ −1 ∗ −1 den u u )esetén. Ekkor h gh ∈ G és σ h gh, u = σ σσ ′ . Ha u′ u, akkor ( −1 σ h gh, u = σ ′−1 id Γk σ ′ = σ ′−1 σ ′ = id Γk . Ez éppen azt jelenti, hogy σ ′−1 σσ ′ ∈ N (G). A tov´ abbiakban az Nu (G) és Hu (G) jelöléseknél néha el fogjuk hagyni az alsó indexeket, amennyiben G ≥ Aut(V ). Ezt a A 3.28. lemma miatt megtehetj¨ uk. 3.30. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán. Ekkor az N (G) és H(G) részcsoportok a c´ımkézést˝ol is f¨ uggetlenek.

47

Bizony´ıt´ as. Ebben a bizony´ıt´ asban az N (G) és H(G) csoportoknál fels˝o indexben jelezz¨ uk, hogy melyik kG -c´ımkézést használjuk a defin´ıciójuknál. A S (k(G)) csoport nem f¨ ugg a c´ımkézést˝ ol, ´ıgy a G∗ = G ∩ S (k(G)) csoport sem. Egy rögz´ıtett f kG ∗ c´ımkézésre, egy g ∈ G -beli elemre és egy v ∈ V \ 0 vektorra pontosan akkor teljes¨ ul σf (g, u) = id ΓkG , ha g identit´ asként hat a ∼G (v) ekvivalenciaosztályon. Így ez a tény is f¨ uggetlen a c´ımkézés megválasztásától. Ezeket használva a következ˝o m´ odon bizony´ıthat´ o a lemma. Legyenek f és f ′ két tetsz˝oleges kG -c´ımkézés V \ 0-n. Legyen most f ′′ egy olyan c´ımkézés, amelyik valamelyik kG ekvivalenciaosztályon megegyezik f -fel és valamelyik ekvivalenciaoszt´ alyon megegyezik f ′ -vel. Legyen u tehát egy olyan elem, amire a ∼G (u) ekvivalenciaosztályon f és f ′′ megegyezik. Ekkor egy g ∈ G∗ ′′ elemre σf (g, u) = σf ′′ (g, u). Ebb˝ol következik, hogy H f (G) = Huf (G) = Huf (G) = H f (G). Tegy¨ uk fel most, hogy σ ∈ N f (G). Ekkor van olyan g ∈ G∗ transzformáció, amire σf (g, u) = σ és σf (g, u′ ) = id ΓkG minden u′ u-ra. Ebb˝ol következik σkG ,f ′′ (g, u) = σf ′′ (g, u) = σ és σf ′′ (g, u′ ) = id ΓkG minden u′ u-ra, hiszen amint láttuk az, hogy σf = id ΓkG teljes¨ ul-e, nem f¨ ugg a c´ımkézés megválasztásától. Tehát ′′ ′′ σ ∈ N f (G). Azt kaptuk teh´ at, hogy N f (G) ⊂ N f (G). Hasonlóan adódik a másik ′′ ir´ any´ u tartalmaz´ as is, ´ıgy val´ ojában N f (G) = N f (G). ′′ ′′ Teh´ at H f (G) = H f (G) és N f (G) = N f (G). Hasonlóan bizony´ıthatóak ′ ′′ ′ ′′ ′ a H f (G) = H f (G) és N f (G) = N f (G) egyenl˝oségek is, ´ıgy H f (G) = H f (G) ′ és N f (G) = N f (G). A Γk csoport hat saját magán a balról (vagy jobbról) szorzással. Ez a hatás h˝ u, ´ıgy adódik egy természetes Γk ,→ Sym(Γk ) beágyazás. 3.31. lemma. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, és f egy kG -c´ımkézés. Ekkor ΓkG ≤ N (G). Bizony´ıt´ as. Legyenek u, v ∈ V f , u ̸= v tetsz˝olegesek. Legyen λ ∈ ΓkG tetsz˝oleges. Bel´ atjuk, hogy λ ∈ N (G). Legyen f ′ az a c´ımkézés, amire f ′ (u′ ) = f (u′ ) minden u(′ G u esetén,) és f ′ (u′ ) = λu′ minden u′ ∼G u esetén. Legyen továbbá g ∈ Sym (V \ 0)/ ∼kG az ′ a permut´ aci´ o, ami kicseréli u és v ekvivalenciaosztályát. Ekkor g f g f ∈ G a 3.25. ál′ ′ l´ıt´ as szerint. Nyilván g f g f ∈ S (k(G)) , ´ıgy g f g f ∈ G∗ = G ∩ S (k(G)) is teljes¨ ul. Azt f f′ f f′ áll´ıtjuk, hogy ekkor σ(g g , v) = λ és σ(g g , v ′ ) = id ΓkG minden v ′ v-re. Ezt elég bizony´ıtani, hiszen az N (G) csoport defin´ıciója szerint λ ∈ N (G). Tegy¨ uk fel, hogy v ′ = µv valamilyen µ ∈ ΓkG -re. Ekkor v ′g

f

gf

′

′ f′ ( f ′ (µu) λµ g f )g gf = (µv) = (µu) = ′ µv = µv = λµv. f (µv) µ

f′ ( f f f′ f g Tegy¨ uk fel most, hogy v ′ v. Ebb˝ol v ′g u, és ´ıgy f (v ′g g ) = f (v ′g ) = f ( f g ′ f f′ f f′ f (v ′g ) = f (v ′ ). Mivel g f g f ∈ G∗ , ezért v ′g g ∼G v ′ is teljes¨ ul, ´ıgy v ′g g = v ′ , ′ azaz σ(g f g f , v) = id ΓkG .

48

3.32. defin´ıci´ o. Legyen f egy tetsz˝oleges k-c´ımkézés valamilyen k | p − 1-ra. Legyenek tov´ abb´ a Γk ≤ N ▹ H ≤ Sym(Γk ) tetsz˝oleges csoportok. Ekkor legyen G∗f (N, H) azon g ∈ Sym0 (V ) elemek csoportja, ami stabilizál minden ∼k -ekvivalenciaoszt´ alyt, a σf (g, v) : v ∈ V \ 0 elemek mind elemei H-nak, és a H/N faktorcsoportban megegyeznek. ( )f Legyen Gf (N, H) := G∗f (N, H)(Sym (V \ 0)/ ∼kG . A 3.27 és 3.32 defin´ıci´ okból könnyen látható, hogy ha Aut(V ) ≤ G ≤ (k) Sym0 (V ) egy csoport, és f egy k-c´ımkézés, akkor ( ) ( ) N Gf (N, H) = N és H Gf (N, H) = H. Ennek a meg´ allap´ıt´ asnak egyszer˝ u következménye, hogy a Gf (N, H) ≤ Gf (N ′ , H ′ ) pontosan akkor teljes¨ ul, ha N ≤ N ′ és H ≤ H ′ , továbbá hogy Gf (N, H) = ′ ′ Gf (N , H ) esetén N = N ′ és H = H ′ (azaz a Gf (N, H) csoportok páronként k¨ ulönb¨ oz˝ oek). 3.33. lemma. Legyen f egy tetsz˝oleges k-c´ımkézés valamilyen k | p − 1-ra. Legyenek tov´ abb´ a Γk ≤ N ▹ H ≤ Sym(Γk ) tetsz˝oleges csoportok. Ekkor Gf (N, H) tartalmazza Aut(V )-t, kG(N,H) = k, és Gf (N, H) a teljes szimmetrikus csoportként hat a ∼k -ekvivalenciaoszt´ alyok halmazán. Bizony´ıt´ as. A lemm´ aban felsorolt áll´ıtásokból csak az nem triviális, hogy Aut(V ) ≤ Gf (N, H). Mivel Γk ≤ N, H, ezért Gf (Γk , Γk ) ≤ Gf (N, H), ´ıgy elég belátni, hogy Aut(V ) ≤ Gf (Γk , Γk ). Legyen γ ∈ Aut(V ) tetsz˝oleges. Ekkor van olyan ( )f g ∈ Sym (V \ 0)/ ∼kG , hogy g ′ := γg stabilizál minden ∼k ekvivalenciaoszályt. Mivel γ ∈ Aut(V ), ezért σ(g, u) ∈ Γk minden u ∈ V \ 0-ra. A g egy f -fel kompatibilis permut´ aci´ o, ´ıgy σ(g, u) = id Γk . Ebb˝ol következik, hogy σ(γg, u) ∈ Γk minden u ∈ V \ 0-ra. Ez defin´ıci´ o szerint éppen azt jelenti, hogy g ′ = γg ∈ G∗f (Γk , Γk ), amib˝ ol ( )f γ = g ′−1 g ∈ G∗f (Γk , Γk ) Sym (V \ 0)/ ∼kG = Gf (Γk , Γk ). Teh´ at val´ oban Aut(V ) ≤ Gf (Γk , Γk ). 3.34. t´ etel. Legyen Aut(V ) ≤ G ≤ Sym (V )0 egy zárt csoport, ami a szimmetrikus csoportként hat a ∼kG -ekvivalenciaosztályok halmazán, és f egy kG -c´ımkézés. Ekkor vannak olyan ΓkG ≤ N ▹ H ≤ Sym(ΓkG ) csoportok, hogy G = Gf (N, H). Bizony´ıt´ as. Azt áll´ıtjuk az N := N (G) és H := H(G) választás jó lesz. Ekkor a 3.29. és a 3.31. lemm´ ak szerint a ΓkG ≤ N ▹ H ≤ Sym(ΓkG ) tartalmazások teljes¨ ul( )f ∗ nek. A 3.26. k¨ ovetkezmény szerint G = G (Sym (V \ 0)/ ∼kG , ´ıgy elég belátni, hogy G∗ = G∗f (N, H). Tegy¨ uk fel, hogy g ∈ G∗ , és legyen v, w tetsz˝oleges inekvivalens elemei V \ 0nak. Ekkor σ(g, v) ∈ H(G) = H. Azt kell még belátni, hogy σ(g, v) és σ(g, w) képe −1 megegyezik a H/N faktorcsoportban. Ehhez ( ) elég belátni, hogy σ(g, v)σ(g, w) ∈ N . Legyen most t ∈ Sym (V \ 0)/ ∼kG az a transzpoz´ıció, ami felcseréli v és 49

f

w ekvivalenciaoszt´ aly´ at. Tekints¨ uk ekkor a h = gtf g −1 (t−1 ) = gtf g −1 tf kommutátort. Ez minden ∼G -ekvivalenciaosztályt stabilizál, és σ(h, v) = σ(g, v)σ(tf , v)σ(g −1 , w)σ(tf , w) = σ(g, v)σ(g, w)

−1

,

tov´ abb´ a minden u G v, w esetén σ(h, u) = σ(g, u)σ(tf , u)σ(g −1 , u)σ(tf , u) = id(ΓkG ). Legyen most v r¨ ogz´ıtett és w1 , w2 , . . . a V \ 0 halmaz elemeinek egy felsorolása. ( ) Legyen ekkor minden i-re ti ∈ Sym (V \ 0)/ ∼kG az a transzpoz´ıció, ami felcseréli w és wi ekvivalenciaosztályát. Tekints¨ uk ekkor a hi := tfi h(tfi ) ∗ permut´ aci´ okat. Ekkor hi ∈ G , σ(hi , v) = σ(tfi , v)σ(g, v)σ(g, w)

−1

σ(tfi , v)

−1

= σ(g, v)σ(g, w)

−1

−1

= tfi htfi

,

és minden olyan u-ra, ami nem ekvivalens a v és wi elemek egyikével sem f

f

σ(hi , u) = σ(tfi , u)σ(tfi , uti )σ(tfi , uti ) = id(ΓkG ). Ekkor a h1 , h2 , . . . sorozat konvergens, és ennek a h határértékére h stabilizál min−1 den ∼G -ekvivalenciaoszt´ alyt, σ(h, v) = σ(g, v)σ(g, w) és σ(h, u) = id(ΓkG ) min−1 den u G v-re. Ebb˝ ol k¨ ovetkezik, hogy σ(g, v)σ(g, w) ∈ N (H) := N . Ezzel beláttuk, hogy G∗ ⊂ G∗f (N, H). Most bel´ atjuk, hogy G∗f (N, H) ⊂ G∗ . Legyen U egy véges részhalmaza V -nek. Mivel G z´ art, ezért az áll´ıt´ ashoz elég belátni, hogy G∗f (N, H) U ⊂ G∗ |U . A G∗f |U hatást gener´ alj´ ak a gn,u : n ∈ N , u ∈ U és a g ′ (h) : h ∈ H elemek megszor´ıtásai U(-ra, ahol) a gn,u és g ′ (h) elemek (stabilizálnak alyt, ) minden ( ∼G -ekvivalenciaoszt´ ) σ g ′ (h), v = h minden v ∈ U -ra, σ g(n, v), v = n és σ g(n, u), v = id(ΓkG ) minden u ∈ U \ ∼G (v)-re. Az N = N (G) csoport defin´ıciójából következik, hogy a g(n, u) U elemeket mind tartalamazza G∗ |U , ´ıgy elég belátni, hogy tetsz˝oleges h ∈ H esetén g ′ (h) U ∈ G∗ |U . A H csoport defin´ıciója miatt van olyan g0 ∈ G∗ elem, amire σ(g0 , v) = h valamilyen v ∈ V \ 0-ra. Láttuk, hogy G∗ ⊂ G∗f (N, H). Ebb˝ ol k¨ ovetkezik, hogy minden u ∈ V \ 0 esetén σ(g∪0 , u) = hnu valamilyen nu ∈ N -re. Legyen U ′ a V∏f egy olyan véges halmaz, amire v∈V f ∼G (v) lefedi U -t, és tekints¨ uk a g1 = g0 u∈U ′ g −1 (nu , u) permutációt. A g(nu , u) transzformációk páronként felcserélhet˝ oek, ´ıgy az el˝ obbi szorzatnál mindegy, hogy milyen sorrendben szorozzuk oleges u ∈ U esetén össze az elemeket. Ekkor tetsz˝ ( ) ′ σ(g1 , u) = σ(g0 , u)σ g −1 (nu , u) = hnu n−1 u = h = σ(g , u), ´ıgy g1 |U = g ′ (h) U , és ezt kellett bizony´ıtanunk. ( ) 3.35. k¨ ovetkezm´ eny. Ha Γk ≤ N ▹ H ≤ Sym Γk (G) , akkor a Gf (N, H) jelölés f¨ uggetlen az f c´ımkézés megv´ alasztásától. ( ) ′ Bizony´ ıt´ as. )Legyen f és f két tetsz˝oleges k-c´ımkézés. Ekkor H Gf (N, H) = H és ( N Gf (N, H) = N . Ekkor azonban a 3.34. tételt alkalmazva a Gf (N, H) csoportra és az f ′ c´ımkézésre ad´ odik, hogy Gf (N, H) = Gf ′ (N, H).

50

4. A vektort´ er 0-t nem fix´ al´ o reduktjai Legyen V tov´ abbra is egy megszámlálhatóan végtelen dimenziós vektortér Fp fölött, ahol p ≥ 3 pr´ım. Ebben a fejezetben belátjuk, hogy ha V automorfizmuscsoportjának egy zárt szupercsoportj´ anak van olyan eleme, ami nem tartja a 0-t, akkor V vagy az affin transzform´ aci´ ok csoportja, vagy a teljes szimmetrikus csoport. Ezen áll´ıt´ as bizony´ıt´ as´ ahoz haszn´ alni fogjuk az el˝oz˝o fejezet eredményeit. Jel¨ olje Aff(V ) az affin transzformációk csoportját V -ben. Egy v ∈ V vektor esetén jel¨ olje trv az u 7→ u + v eltolást V -n. Ekkor minden g ∈ Aff(V ) egyértelm˝ uen fel´ırhat´ o g = g0 tru alakban, ahol g0 ∈ Aut V és u ∈ V . Mivel Aut(Fp ) triviális, és p ≥ 3, ezért az affin geometria alaptétele szerint egy g ∈ Sym(V ) transzformáció pontosan akkor affin transzformáció, ha kollineáció, azaz g minden affin egyenest egyenesbe visz. Erre az észrevételre még sz¨ ukség¨ unk lesz a kés˝obbiekben. 4.1. lemma. Ha Aut(V ) ≤ G ≤ Sym(V ) csoport, ami nem tartja a 0-t, akkor G tranzit´ıvan hat V -n. Bizony´ıt´ as. Aut(V ) tranzit´ıvan hat V \ 0-n, és G-nek van olyan eleme, ami a 0-t egy V \ 0-beli vektorba képezi. Ebb˝ol következik, hogy G tranzit´ıv. A bizony´ıt´ ashoz sz¨ ukség¨ unk lesz az alábbi jelölésre. 4.2. defin´ıci´ o. Legyen G egy csoport, ami hat V -n, és legyenek, a, b ∈ V tetsz˝olegesek. Ekkor jel¨ olje FG (a, b) az {a, b} halmaz elemenkénti stabilizátorának véges orbitjainak uni´ oj´ at. Ez a jel¨ olés a k¨ ovetkez˝ o módon f¨ ugg össze a 3. fejezetbeli ∼G ” jelöléssel. ” 4.3. lemma. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy csoport. Ekkor b ∈ FG (0, a) pontosan akkor teljes¨ ul, ha b ∼G0 a vagy b = 0. Bizony´ıt´ as. b = 0 esetén az áll´ıtás triviális, tegy¨ uk fel most, hogy b ̸= 0. Tegy¨ uk fel el˝ osz¨ or, hogy b ∼G0 a. Ekkor defin´ıció szerint minden g ∈ G0 esetén bg ∈ ⟨ag ⟩, ´ıgy minden b ∈ (G0 )v esetén bg ∈ ⟨a⟩. Ekkor mivel ⟨a⟩ véges, ´ıgy b orbitja is véges. Teh´ at b ∈ FG (0, a). Tegy¨ uk fel most, hogy b a. Ekkor van olyan g ∈ G0 , hogy ag , bg lineárisan f¨ uggetlenek. Legyen h ∈ Aut(V ) ⊂ G0 egy olyan lineáris transzformáció, ami ag -t a-ba viszi. Ekkor gh ∈ (G0 )a és bgh ∈ / ⟨a⟩. Ekkor a 3.4. lemma szerint (G0 )a (b) végtelen, ´ıgy b ∈ / FG (0, a). 4.4. ko eny. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy csoport, ami ¨vetkezm´ nem tartja a 0-t. Ekkor tetsz˝ oleges u, v ∈ V k¨ ulönböz˝o vektorok esetén FG (u, v) = kG0 + 1. Bizony´ıt´ as. A 4.1. lemma szerint G tranzit´ıv, ´ıgy az áll´ıtást elég belátni abban az esetben, amikor u = 0. A 4.3. lemma szerint azonban ekkor F (u, v) = F (0, v) = {w ∈ V : w ̸= 0, w ∼G0 v} ∪ {0}, speciálisan F (0, v) = kG0 + 1. 51

4.5. lemma. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy csoport, ami nem stabilizálja a 0-t. Ekkor tetsz˝ oleges a, b ∈ V, a ̸= b és u, v ∈ FG (a, b), u ̸= v esetén FG (u, v) = FG (a, b). Bizony´ıt´ as. A 4.1. lemma szerint G tranzit´ıv, ´ıgy feltehet˝o, hogy a = 0. A 4.3. lemma szerint ekkor c ∈ F (a, b) pontosan akkor teljes¨ ul, ha c ∼G0 b. Tegy¨ uk fel most, hogy u, v ∈ FG (a, b), u ̸= v és w ∈ / FG (a, b). Ekkor u ∼G0 b ∼G0 v és w G0 b ∼G0 u. Ebb˝ ol k¨ ovetkezik, hogy létezik olyan g ∈ G0 , hogy wg és ug lineárisan f¨ uggetlenek. A ∼G0 rel´ aci´ o defin´ıciója miatt v g ∈ ⟨ug ⟩, ´ıgy wg ∈ / ⟨u⟩ = ⟨ug , v g ⟩. Így g a 3.4. lemma szerint (G0 )ug ,vg (w ) végtelen. Ekkor (G0 )u,v (w) is végtelen, és ´ıgy Gu,v (w) is végtelen. Teh´ at w ∈ / FG (u, v). Beláttuk tehát, hogy w ∈ / FG (a, b) esetén w∈ / FG (u, v). Ez azt jelenti, hogy F (u, v) ⊂ F (a, b). A 4.4. k¨ o vetkezm´ eny szerint G G azonban FG (a, b) = FG (u, v) = kG0 + 1, ´ıgy FG (u, v) = FG (a, b). 4.6. lemma. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy zárt csoport, ami nem fixálja a 0-t. Ekkor kG0 = 1 vagy kG0 = p − 1. Bizony´ıt´ as. Tegy¨ uk fel, hogy 1 < kG0 < p − 1. Ez azt jelenti, hogy létezik olyan λ ∈ Fp \ {0, 1}, hogy λv G0 v. Ekkor a 4.3. lemma szerint λv ∈ / FG (0, v). Azt áll´ıtjuk, hogy ekkor 0 ∈ / FG (v, λv). Tegy¨ uk fel ugyanis, hogy 0 ∈ FG (v, λv). Ebb˝ol a 4.5. lemma szerint F (v, λv) = FG (0, v) kövekezik, amib˝ol λv ∈ FG (0, v), ami nem lehet. Mivel 1 < kG0 , ezért a 4.4. következmény szerint van olyan u ∈ FG (v, λv), amire u ̸= v, λv. Az el˝ obbiek szerint u = 0 nem lehetséges. Mivel u ∈ FG (v, λv), ezért Gv,λv (u) véges, és ´ıgy (G0 )v,λv (u) is véges. Ekkor a 3.4. lemma szerint u ∈ ⟨v, λv⟩ = ⟨v⟩. Azt kaptuk teh´ at, hogy létezik olyan µ ∈ Fp \ {0, 1, λ}, hogy µv = u ∈ FG (v, λv). 1. eset: µv G0 v és µv G0 λv. Ebben az esetben v, λv, µv páronként inekvivalens vektorok. A G0 = G ∩ Sym (V )0 csoport zárt, és tartalmazza Aut(V )-t, ´ıgy a 3.16. tétel szerint G0 3-tranzit´ıvan hat a ∼G0 -ekvivalenciaosztályok halmazán. g g Speci´ alisan létezik olyan g ∈ G0 , amire a v g , (λv) , (µv) vektorok lineárisan f¨ uggetlenek. Ekkor a 3.4. lemma szerint (G0 )vg ,(λv)g (µg) végtelen, és ´ıgy (G0 )v,λv (µv) is végtelen, ami ellentmond annak, hogy µv ∈ FG (v, λv). Tehát µv ∼G0 v vagy µv ∼G0 λv. 2. eset: µv ∼G0 v. Ekkor a 4.4. következményt használva µv ∈ FG (v, λv), amib˝ol λv ∈ FG (v, µv) = FG (0, v), ami ellentmondás. 3. eset: µv ∼G0 λv. Ekkor megint a 4.4. következményt használva µv ∈ FG (v, λv), amib˝ ol v ∈ FG (λv, µv) = FG (0, λv) adódik, és ´ıgy a 4.3. lemma szerint λv ∼G0 v, ami ellentmond´ as. Minden esetben ellentmondást kaptunk, tehát kG0 = 1 vagy kG0 = p − 1. A 4.4 és a 4.6. lemm´ ak szerint, ha egy Aut(V ) ≤ G ≤ Sym(V nem ) csoport F (u, v) = 2 vagy fix´ a lja a 0-t, akkor tetsz˝ o leges u, v ∈ V , u = ̸ v elemek eset´ e n F (u, v) = p + 1. Az el˝ obbi esetben nyilván F (u, v) = {u, v}. Belátjuk, hogy az ut´ obbi esetben F (u, v) = L(u, v), az u, v vektorokat összeköt˝o affin egyenes. Ehhez el˝ osz¨ or sz¨ ukség¨ unk lesz az alábbi lemmára. 52

4.7. lemma. Legyen U egy 2 dimenziós vektortér Fp felett, és legyen H ⊂ U, |H| = p egy olyan halmaz, amelynek elemei páronként lineárisan f¨ uggetlenek, és kielég´ıti az al´ abbi feltételt: (1)

Tetsz˝ oleges λ, µ ∈ Fp és u, v, u′ , v ′ ∈ H esetén, ha u ̸= v, u′ ̸= v ′ és λu + µv ∈ H, akkor λu′ + µv ′ ∈ H.

Ekkor H egy affin egyenes U -ban. Bizony´ıt´ as. A bizony´ıt´ asban jelölj¨ uk I-vel azon (λ, µ) ∈ F2p párok halmazát, amire λu + µv ∈ H valamelyik (az ¨ osszes) k¨ ulönböz˝o elemekb˝ol álló (u, v) ∈ H 2 esetén. Könnyen láthat´ o, hogy ekkor (λ, µ) ∈ I pontosan akkor teljes¨ ul, ha (µ, λ) ∈ I teljes¨ ul. 1. ´ all´ıt´ as. Ha (λ, µ) ∈ I, ahol λ, µ ̸= 0, akkor (µ + 1, −µ) ∈ I. Legyenek ugyanis a, b ∈ H, a ̸= b tetsz˝ olegesek. Tekints¨ uk most a következ˝o összef¨ uggést. 1 µ (λa + µb) − b = a ∈ H. λ λ Mivel µ ̸= 0, ezért λa + µb ̸= b, és ´ıgy ( λ1 , − µλ ) ∈ I. Hasonlóan µ ̸= 0. Ekkor mivel (λ, µ) ∈ H, ezért ( ) 1 µ H∋λ a − b + µa = (µ + 1)a − µb. λ λ

µ 1 λa − λb

̸= a, hiszen

Ebb˝ ol k¨ ovetkezik, hogy (µ + 1, −µ) ∈ I. Most bel´ atjuk a lemma áll´ıtását. Legyenek megint a, b ∈ H, a ̸= b tetsz˝olegesek. Ha p = 3 és −a − b ∈ H, akkor készen vagyunk, hiszen ekkor csak H = {a, b, −a − b} = L(a, b) lehetséges. Tegy¨ uk fel ezért, hogy p > 3, vagy p = 3 és −a − b ∈ / H. Mivel |H| = p, ezért mindkét esetben azt kapjuk, hogy van olyan (λ, µ) ∈ I pár, amire λ ̸= 0, µ ̸= 0 és a λ, µ elemek valamelyike nem −1. Mivel (λ, µ) ∈ I pontosan akkor teljes¨ ul, ha (µ, λ) ∈ I, ezért feltehet˝o, hogy µ ̸= −1. Ekkor az el˝obbiek szerint (µ + 1, −µ) ∈ I. Legyen most M azon ν-k halmaza, amire (ν + 1, −ν) ∈ I teljes¨ ul. Ekkor 0, −1, µ ∈ M , és a feltételeink szerint µ = ̸ 0, −1. Ha (ν + 1, −νb) ∈ I ´ e s ν ̸= 0, −1, ( ) akkor az 1. áll´ıt´ as szerint ν + 2, −(ν + 1) ∈ I. Ebb˝ol következik, hogy µ, µ + 1, . . . , p − 2 ∈ M . Ha (ν + 1, −ν) ∈ I és ν ̸=( 0, −1, akkor ) (−ν, 1 + ν) ∈ I, és ekkor az 1. áll´ıt´ as szerint (−ν + 1, ν) ∈ I és ´ıgy ν, −(ν − 1) ∈ I. Ebb˝ol következik, hogy µ, µ − 1, azt jelenti, hogy csak M = Fp lehetséges, és ekkor { . . . , 2 ∈ M . Ez azonban } I ⊃ (ν + 1, −ν) : ν ∈ Fp , amib˝ol { } H ⊃ (ν + 1)a − νb : ν ∈ Fp = L(a, b) ad´ odik. Az L(a, b) egyenes számossága azonban p, ´ıgy csak H = L(a, b) lehetséges.

53

4.8. ´ all´ıt´ as. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy zárt csoport, ami nem fixálja a 0-t. Ekkor ha kG0 = p − 1, akkor FG (a, b) = L(a, b) tetsz˝oleges a, b ∈ V k¨ ulönböz˝o elemek esetén. Bizony´ıt´ as. Tegy¨ uk fel el˝ osz¨ or, hogy a, b ∈ V line´ arisan összef¨ uggenek. Ekkor ha v∈ / ⟨a, b⟩, akkor a 3.4. lemma szerint (G0 )a,b (v) végtelen, és ´ıgy Ga,b (v) is végtelen, amib˝ ol k¨ ovetkezik, hogy v ∈ / F G (a, b). Tehát FG (a, b) ⊂ ⟨a, b⟩. Ha a, b lineárisan uggenek, akkor ⟨a, b⟩ = L(a, b) = p. A 4.4. következmény szerint az FG (a, b) összef¨ halmaz is p elem˝ u. Ez csak FG (a, b) = L(a, b) esetén lehetséges. Tegy¨ uk fel most, hogy a, b ∈ V lineárisan f¨ uggetlenek. Legyen U = ⟨a, b⟩, ekkor dim U = 2. Az el˝ obbiekhez hasonlóan v ∈ / ⟨a, b⟩ esetén v ∈ / FG (a, b), ´ıgy FG (a, b) ⊂ U . Bel´ atjuk, hogy ekkor az U 2 dimenziós altérre, és a H := FG (a, b) halmazra teljes¨ ulnek a 4.7. lemma feltételei. Ez elég, hiszen ekkor a 4.7. lemma szerint H = FG (a, b) egyenes, és ekkor ez az egyenes csak L(a, b) lehet, hiszen a, b ∈ FG (a, b). A 4.4. k¨ ovetkezmény szerint |H| = FG (a, b) = kG0 + 1 = p. Belátjuk most, hogy H nem tartalmaz két k¨ ulönböz˝o lineárisan összef¨ ugg˝o vektort. Tegy¨ uk fel ugyanis, hogy 0 ̸= u, λu ∈ F (a, b), ahol λ ̸= 1. Ekkor a 4.5. lemma szerint F (a, b) = F (u, λu), ami lehetetlen, hiszen az áll´ıtásnak a már bizony´ıtott el˝oz˝o esete szerint F (u, λu) = ⟨u⟩, és ekkor F (u, λu) nem tartalmazhatna két lineárisan f¨ uggetlen vektort. Be kell még l´ atni a 4.7. lemma (1) feltételét. Ehhez tegy¨ uk fel, hogy u, v, u′ , v ′ ∈ H olyan vektorok, hogy u ̸= v, u′ ̸= v ′ , és legyenek µ, λ ∈ Fp olyan egy¨ utthat´ ok, amelyekre λu + µv ∈ H teljes¨ ul. Be kell látnunk, hogy ekkor λu′ + ′ µv ∈ H. A 4.5. lemma szerint F (a, b) = F (u, v) = F (u′ , v ′ ), ´ıgy ezen áll´ıtáshoz elég bel´ atni, hogy Gu′ ,v′ (λu′ + µv ′ ) véges. Legyen most g ∈ Aut(V ) ⊂ G egy olyan g g line´ aris transzform´ aci´ o, amire (u′ ) = u és (v ′ ) = v. Ilyen létezik, hiszen az u, v és az u′ , v ′ is line´ arisan f¨ uggetlen párok. Ekkor ( ) Gu′ ,v′ (λu + µv) = |G(u′ )g ,(v′ )g (λu′ + µv ′ )g | = Gu,v (λu + µv) , ami véges, hiszen λu + µv ∈ H = FG (a, b) = FG (u, v). 4.9. t´ etel. Legyen Aut(V ) ≤ G ≤ Sym(V ) egy zárt csoport, ami nem fixálja a 0-t. Ekkor G = Aff(V ) vagy G = Sym(V ). Bizony´ıt´ as. A 4.6. lemma szerint kG0 = 1 vagy kG0 = p − 1. 1. eset. kG0 = 1. A G0 = G ∩ Sym0 (V ) csoport zárt, ´ıgy a 3.17. következmény szerint G0 = Sym0 (V ). A 4.1. lemma szerint azonban a G csoport tranzit´ıvan hat V -n. Ez csak G = Sym(V ) esetén lehetséges. 2. eset. kG0 = p − 1. Ekkor el˝ oször belátjuk, hogy G ≤ Aff(V ). Ehhez elég belátni, hogy G minden eleme kolline´ aci´ o. Legyen tehát g ∈ G és L = L(a, b) egy tetsz˝oleges affin egyenes V -ben. Ekkor a 4.8. áll´ıtás szerint L(a, ( )gb) = FG (a, b). Az F(G (a, b))halg maz defin´ıci´ oj´ ab´ ol k¨ onnyen l´ atható, hogy FG (a, b) = FG (ag , bg ), ´ıgy L(a, b) = FG (ag , bg ) = L(ag , bg ). Teh´ at g valóban kollineáció. Tehát G ≤ Aff(V ). Bel´ atjuk most, hogy val´ oj´ aban G = Aff(V ). Tegy¨ uk fel ugyanis, hogy g ∈ G és g nem fix´ alja a 0-t. Ekkor g = g0 trv alak´ u valamilyen g0 ∈ Aut(V )-re és v ∈ V \ 0ra. Ekkor g0 ∈ Aut(V ) ⊂ G miatt trv ∈ G is teljes¨ ul. Belátjuk, hogy ekkor már 54

G tartalmaz minden eltol´ ast. Ez elég, hiszen az eltolások generálják Aff(V )-t. Legyen teh´ at w ∈ V \ 0 tetsz˝ oleges. Legyen ekkor h ∈ Aut(V ) ⊂ G egy olyan lineáris transzform´ aci´ o, ami v-t w-be képezi. Ekkor tetsz˝oleges u ∈ V esetén ( −1 )h ( −1 )h −1 uh trv h = uh + v = uh + v h = u + v h = u + w = utrw , ´ıgy G ∋ h−1 trv h = trw . A 4.9. tétel azonnali k¨ ovetkezménye a következ˝o tétel. 4.10. t´ etel. Legyen A a V strukt´ ura egy reduktja, amiben a 0 nem definiálható. Ekkor A vagy ekvivalens V -vel, mint egy megszámlálhatóan végtelen dimenziós affin térrel, vagy ekvivalens a megszámlálhatóan végtelen, strukt´ ura nélk¨ uli halmazzal. Bizony´ıt´ as. Legyen G := Aut(A). Legyen továbbá A0 az a strukt´ ura, amit A-ból kapunk u ´gy, hogy hozz´ avessz¨ uk a 0-t, mint konstanst. Mivel a 0 nem definiálható A-ban, ezért A és A0 nem ekvivalensek. Ekkor a 2.1. tétel szerint G = Aut(A) ̸= Aut A0 = G ∩ Sym (V )0 . Speci´ alisan G Sym (V )0 . A G csoport egy strukt´ ura automorfizmuscsoportja, ´ıgy zárt. Ekkor a 4.9. tétel szerint G = Aff(V ) vagy G = Sym(V ), amib˝ol szintén a 2.1. tételt haszn´ alva adódik a tétel áll´ıtása.

Irodalom [1] M. Bodirsky, H. Chen, M. Pinsker, The reducts of equality up to primitive positive interdefinability, Journal of Symbolic Logic, 75(4) (2010), 1249–1292. [2] M. Bodirsky, M. Pinsker, Minimal functions on the random graph, Israel Journal of Mathematics (2010), to appear [3] M. Bodirsky, M. Pinsker, T. Tsankov, Decidability of definability, Journal of Symbolic Logic, 78, 1036–1054. [4] M. Bodirsky, M. Pinsker, Reducts of Ramsey structures, Model Theoretic Methods in Finite Combinatorics, 558. Contemporary Mathematics, American Mathematical Society (2011), 489–519. [5] P. J. Cameron, Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, 148 (1976), 127–139. [6] W. Hodges, Model theory, Cambridge University Press (Cambridge, 1993). [7] M. Junker, M. Ziegler, The 116 reducts of (Q; <; a), Journal of Symbolic Logic, 74(3) (2008), 861–884. [8] D. Macpherson, A survey of homogeneous structures, Discrete Mathematics, 311(15) (2011), 1599–1634. [9] P. P. Pach, M. Pinsker, A. Pongr´ acz, Cs. Szab´ o, A new transformation of partially ordered sets, J. Comb. Theory A., 120(7) (2013), 1450–1462. [10] P. P. Pach, M. Pinsker, G. Pluh´ ar, A. Pongr´ acz, Cs. Szab´ o, Reducts of the random partial order, Advances in Mathematics (2014), to appear.

55

[11] A. Pongr´ acz, Reducts of the Henson graphs with a constant, Annals of Pure and Applied Logic (2013), to appear [12] S. Thomas, Reducts of the random graph, Journal of Symbolic Logic, 56(1) (1991), 176–181. [13] S. Thomas, Reducts of random hypergraphs, Annals of Pure and Applied Logic, 80(2) (1996), 165–193.

Bertalan Bodor, Kende Kalina: On first order definable reducts of the vectorspace F∞ p for odd primes Let V denote the countably infinte dimensional projective space over a field of size p, where p is a prime and let PGL(V ) denote its group of automorphisms. We investigate the supergroups of PGL(V ). Bodor Bertalan

Kalina Kende



[email protected]

[email protected]

56

´ FUNKCIONALIS ´ BOOLE-ALGEBRAK REDUKTJAI BODOR BERTALAN, KALINA KENDE

Bevezetj¨ uk a funkcion´ alis redukt fogalm´ at, mint speci´ alis reduktokat, illetve meghat´ arozzuk bizonyos Boole-algebr´ ak ¨ osszes funkcion´ alis reduktj´ at.

1. Bevezet´ es Jel¨ olje Ba = (B, ∧, ∨, 0, 1, ¬) a megszámlálható atommentes Boole-algebrát. Izomorfia erejéig pontosan egy ilyen strukt´ ura létezik. Könny˝ u ellen˝orizni, hogy Ba b´ armely két véges részalgebr´ aja között men˝o izomorfizmus kiterjed Ba egy automorfizmus´ av´ a, tov´ abb´ a minden véges vagy megszámlálhatóan végtelen Boolealgebra beágyazhat´ o Ba-ba. Azaz Ba homogén és univerzális a Boole-algebrák oszt´ aly´ aban. 1. defin´ıci´ o. Egy A = (A, f1 , . . . , fn ) algebra egy funkcionális reduktján egy (A, t1 , . . . , tn ) algebr´ at ért¨ unk, ahol a ti kifejezések el˝oállnak az fi -k iterált kompoz´ıcióiként, azaz a ti m˝ uveletek az A algebra kifejezés-f¨ uggvényei. Péld´ aul (B, ∆), ahol ∆ a szimmetrikus differenciát jelöli, Ba egy Abel-csoport reduktja. Ebben a dolgozatban Ba funkcionális reduktjait klasszifikáljuk. Megmutatjuk, hogy lényegében 13 ilyen funkcionális redukt létezik, és jellemezz¨ uk ezen funkcion´ alis reduktokat. A Ba algera ω-kategorikus. Egy A strukt´ urát ω-kategorikusnak nevez¨ unk, ha megsz´ aml´ alhat´ o, és elméletének minden megszámlálható modellje izomorf A-val. Azaz, ha egy A strukt´ ur´ aban ugyanazok az els˝orend˝ u formulák igazak, mint Baban, akkor A izomorf kell, hogy legyen Ba-val. A Ba strukt´ ura el˝oáll, mint a véges Boole-algebr´ ak oszt´ aly´ anak Fra¨ıssé-limesze [7]. Sok és sokféle önmagában is érdekl˝odésre sz´ amot tart´ o (rel´ aci´ os) homogén strukt´ ura ismert. Közéj¨ uk tartozik például a véletlen gráf, a véges testek feletti megszámlálhatóan végtelen dimenziós vektorterek, a racion´ alis sz´ amok halmaza a szokásos rendezési relációval ellátva vagy a megsz´ aml´ alhat´ o atommentes Boole-algebra. Kevésbé ismert, de egyszer˝ uség¨ uk miatt fontos példa a Henson-gr´ afok családja, ezek azok a Hn megszámlálható homogén gráfok, amelyek nem tartalmaznak teljes Kn részgráfot [8], továbbá a homogén részbenrendezett halmaz, ami a véletlen gráfhoz hasonlóan megkapható véletlen konstrukci´ oként is [1]. A homogén strukt´ urák általános elméletének kidolgozása 57

Fra¨ıssé munk´ aj´ aval kezd˝ od¨ ott [7], a Fra¨ıssé-tétel karakterizálja azokat a végesen gener´ alt strukt´ ur´ akb´ ol áll´ o oszt´ alyokat, amelyek el˝oállnak, mint valamely homogén strukt´ ura végesen gener´ alt részstrukt´ uráinak osztálya. Ebben a dolgozatban egy strukt´ ura egy reduktja alatt a strukt´ ura alaphalmazán értelmezett rel´ aci´ ok olyan halmazát értj¨ uk, amelyek mindegyikére igaz, hogy els˝ orend˝ u formul´ akkal defini´ alható a strukt´ urában. A reduktok halmazán értelmezhet˝ o egy kv´ azirendezés: R1 . R2 pontosan akkor, ha R2 minden relációja definiálható R1 feletti els˝ orend˝ u formul´ akkal. Két redukt kölcsönösen definiálható egymással, ha R1 . R2 és R2 . R1 , azaz R1 minden relációját definiálni lehet R2 feletti els˝ orend˝ u formul´ akkal, és R2 minden relációját definiálni lehet R1 feletti els˝orend˝ u formul´ akkal. A 2. tétel fontos következménye, hogy ω-kategorikus strukt´ ura minden reduktja is ω-kategorikus. Ez nem ω-kategorikus strukt´ urákra még akkor sem feltétlen igaz, ha a strukt´ ura nyelve véges, és csak relációkat tartalmaz. A [14]-ben megtal´ alhat´ o Lachlan egy ellenpéldájának le´ırása. Egy redukt automorfizmuscsoportja pontosan azon permutációkból áll, amelyek meg˝ orzik a redukt ¨ osszes relációját, ´ıgy speciálisan tartalmazza az eredeti strukt´ ura automorfizmuscsoportját. Továbbá, egy redukt automorfizmuscsoportjára teljes¨ ul a k¨ ovetkez˝ o zárts´ agi feltétel: ha g1 , g2 , . . . ∈ Aut(R) permutációk egy sorozata a redukt automorfizmuscsoportjából, amelyekre teljes¨ ul, hogy a strukt´ ura minden a elemére van olyan j index és ba elem, hogy minden n > j indexre gn (a) = ba , akkor a g1 , g2 , . . . sorozat határértéke, a h(x) = bx permutáció is benne van az automorfizmuscsoportban. Azonban ω-kategorikus strukt´ urák esetén ennél er˝osebb is igaz: a strukt´ ura automorfizmuscsoportj´ at tartalmazó zárt részcsoportok bijekcióban állnak a reduktok k¨ olcs¨ on¨ os defini´ alhat´ os´ agra vett ekvivalenciaosztályaival, ´ıgy ω-kategorikus strukt´ ur´ ak esetén a reduktok klasszifikálása ekvivalens a strukt´ ura automorfizmuscsoportj´ at tartalmaz´ o zárt részcsoportok osztályozásával. Sz´ amos ω-kategorikus homogén strukt´ urának siker¨ ult osztályozni a reduktjait k¨ olcs¨ on¨ os defini´ alhat´ os´ ag erejéig. Kölcsönös definiálhatóság erejéig öt k¨ ulönböz˝o reduktja van például a racion´ alis számoknak a szokásos rendezés¨ ukkel ellátva [6], a véletlen gr´ afnak [14], a véletlen turnamentnek [2] és a véletlen poszetnek [12]. A klasszifik´ aci´ o ismert a konstanssal ellátott Henson-gráfokra is [13]. A homogén rendezett gr´ afnak viszont már t¨ obb mint 40 [3], a racionális számoknak a rendezéssel és egy konstanssal ell´ atva már 116 [10], a véletlen gráfnak egy konstanssal ellátva pedig m´ ar t¨ obb mint 300 reduktja van. Ez utóbbira nem is ismert a teljes klasszifik´ aci´ o. Ennek alapján megfogalmazható, hogy minél több eleme van a nyelvnek, várhat´ oan ann´ al nagyobb lesz a reduktok száma, és ez egyszer˝ unek t˝ un˝o strukt´ urákra is meglep˝ oen nagy tud lenni. Mivel a Ba nyelve több jelet tartalmaz az itt felsorolt strukt´ ur´ ak nyelveinél, ´ıgy itt is sok reduktra lehet szám´ıtani. Az eddigi klasszifik´ aci´ okban az a közös, hogy a vizsgált strukt´ urák nyelve minden esetben véges, és nem tartalmaz f¨ uggvényjeleket. A legtöbb klasszifikáció ad hoc sz´ amol´ asokat haszn´ al, u ´jabban Bodirsky és Pinsker munkája nyomán Ramseyelméleti m´ odszereket alkalmaztak sikerrel [4]. Az általunk vizsgált strukt´ urák ezzel szemben nem ´ırhat´ oak le véges relációs nyelven. Így az eddig ismert módszerek nem m˝ uk¨ odnek. 58

Az általunk vizsg´ alt funkcionális reduktokon hasonl´ oan értelmezhet˝o egy kvázirendezés: C1 . C2 pontosan akkor, ha C2 minden m˝ uvelete definiálható C1 feletti els˝ orend˝ u formul´ akkal. Ezekre is igaz, hogy automorfizmuscsoportjuk zárt, és ωkategorikus esetben ha két funkcionális redukt automorfizmuscsoportja megegyezik, akkor azok els˝ orend˝ u formul´ akkal kölcsönösen definiálhatóak egymásból. Azonban a funkcion´ alis reduktok ekvivalenciaosztályai nem állnak bijekcióban a zárt csoportokkal: létezhetnek olyan z´ art, a strukt´ ura automorfizmuscsoportját tartalmazó csoportok, amelyek nem állnak el˝o funkcionális redukt automorfizmuscsoportjaként. Egy algebra felett el˝ ofordulhat, hogy létezik olyan f¨ uggvény, amely definiálhat´ o az algebra m˝ uveleteivel els˝orend˝ u formulákkal, de nem kifejezésf¨ uggvény. Ilyenre példa, ha egy h´ al´ o alaphalmazát tekintj¨ uk, amelyen csak a (∧ m˝ uvelet adott: a ∨ m˝ uvelet defini´ a lhat´ o els˝ o rend˝ u formul´ a val: a ∨ b = c ⇔ (∀d) (d ∧ a=a ) és d ∧ b = b) → d ∧ c = c , viszont nem kifejezésf¨ uggvény. Tehát két k¨ ulönböz˝o C1 és C2 funkcion´ alis reduktnak lehet azonos automorfizmuscsoportja. Az ω-kategorikus strukt´ urák elméletében fontos szerepet tölt be az alábbi tétel [9]: 2. t´ etel (Engeler, Ryll–Nardzewski, Svenonius). Egy A strukt´ ura pontosan akkor ω-kategorikus, ha Aut(A) oligomorf. A 2. tétel egyszer˝ u k¨ ovetkezményei az alábbiak: 3. k¨ ovetkezm´ eny. Legyen A egy ω-kategorikus strukt´ ura és R egy olyan reláció A alaphalmazán, amelyet minden Aut(A)-beli permutáció meg˝oriz. Ekkor R defini´ alhat´ o egy A feletti els˝ orend˝ u formulával. 4. ko vetkezm´ e ny. Legyen C, C , ehány funkcionális reduktja Ba-nak. ¨ 1 C2 , . . . , Ck n´ Ekkor a k¨ ovetkez˝ o két feltétel ekvivalens: • Aut(C1 ) ∩ Aut(C2 ) . . . ∩ Aut(Ck ) = Aut(C). • C1 ∪ C2 . . . ∪ Ck minden m˝ uvelete definiálható C-b˝ol, és C minden m˝ uvelete defini´ alhat´ o C1 ∪ C2 . . . ∪ Ck -ból.

2. A nemline´ aris funkcion´ alis reduktok A dolgozat tov´ abbi részében a Ba megszámlálható atommentes Boole-algebra funkcion´ alis reduktjait fogjuk klasszifikálni kölcsönös definiálhatóság erejéig. Mivel ez a srukt´ ura ω-kategorikus, ´ıgy elegend˝o azon Aut(Ba) ≤ G ≤ Sym(Ba) csoportokat meghat´ arozni, amelyek el˝ o´ allnak valamilyen funkcionális redukt automorfizmuscsoportjaként. A strukt´ ur´ aval mint Boole-gy˝ ur˝ uvel fogunk dolgozni; az els˝orend˝ u k¨ olcs¨ on¨ os defini´ alhat´ os´ ag ¨ onmagában nem lenne elégséges, de a Boole-algebra és a Boole-gy˝ ur˝ u kifejezésf¨ uggvényei megegyeznek, ´ıgy ez megengedett. Ebben a fejezetben a Ba megszámlálható atommentes Boole-algebra nemline´ aris funkcion´ alis reduktjait klasszifikáljuk. Ehhez meghatározzuk a Sym(Ba)nak az Aut(Ba)-t tartalmaz´ o olyan zárt részcsoportjait, melyek meg˝oriznek valamilyen nemline´ aris kifejezésf¨ uggvényt. 59

Legyen f (x, y) egy kétv´ altozós kifejezésf¨ uggvény. Ekkor f (x, y) fel´ırható az 1, x, y, xy monomok k¨ oz¨ ul valah´ any összegeként, mivel minden Boole-gy˝ ur˝ u kommutat´ıv, és minden elem idempotens a szorzásra nézve. 5. lemma. Ha Aut(Ba) ≤ G ≤ Sym(Ba) meg˝oriz valamilyen f (x, y) nemlineáris kétv´ altoz´ os kifejezésf¨ uggvényt, akkor G = Aut(Ba). Bizony´ıt´ as. Ha egy φ permut´ ació meg˝orzi az xy = x ∧ y vagy az xy + x + y = x ∨ y m˝ uveletek valamelyikét, akkor φ automorfizmus. Ez azért igaz, mert minden hálót meghat´ aroz ¨ onmag´ aban egy is a ∧ és a ∨ m˝ uveletek köz¨ ul, és egy Boole-algebra h´ al´ o ezekre a m˝ uveletekre. ( ) • Legyen f (x, y) = xy + x, ekkor f x, f (x, y) = x(xy + x) + x = xy miatt minden f -et meg˝ orz˝ o permutáció automorfizmus, ugyanez igaz az xy + y m˝ uveletre is. • Legyen g(x, y) = xy + x + 1, ekkor g(g(x, y), y) = (xy + x + 1)y + (xy + x + 1) + 1 = xy + x + y miatt minden g-t meg˝orz˝o permutáció automorfizmus, ugyanez igaz az xy + y + 1 m˝ uveletre is. ( ) • Legyen h(x, y) = xy + 1, ekkor h h(x, x), h(y, y) = (xx + 1)(yy + 1) + 1 = xy + x + y miatt minden h-t meg˝orz˝o permutáció automorfizmus. ( ) • Vég¨ ul legyen k(x, y) = xy + x + y + 1, ekkor k k(x, x), k(y, y) = (x + 1)(y + 1) + (x + 1) + (y + 1) + 1 = xy miatt minden k-t meg˝orz˝o permutáció is automorfizmus. Ezzel a felsorol´ assal az ¨ osszes esetet ellen˝orizt¨ uk. Ha f egy tetsz˝ oleges Boole-f¨ uggvény, melynek aritása k, akkor f (x1 , . . . , xk ) =

∑ ⃗ ε∈k 2

α⃗ε

k ∏

xεi i

i=1

alakban is fel´ırhat´ o, ahol∑minden α⃗ε értéke 0 vagy 1. A továbbiakban egy ⃗ε k hossz´ u k 0 − 1 vektorra |⃗ε| jel¨ oli i=1 εi -t. Jel¨ olje tov´ abb´ a fxi xj (x1 , . . . , xk−1 ) = f (x1 , . . . , xj−1 , xi , xj+1 , . . . , xk ) amikor f -ben xj helyébe xi -t helyettes´ıt¨ unk. Amennyiben ez nem okoz félreértést, fxi xj helyett ´ırhatunk fij -t. Sz¨ ukség¨ unk lesz az alábbi defin´ıcióra is: 6. defin´ıci´ o. A Ba strukt´ ura egy c elemével való eltoláson a tc (a) = a + c permutáci´ ot értj¨ uk. Az o as csoportját T -vel fogjuk jelölni: T = {tc : c ∈ Ba}. ¨sszes eltol´ Most karakteriz´ aljuk a h´ aromváltozós nemlineáris kifejezésf¨ uggvények lehetséges automorfizmuscsoportjait: 7. lemma. Legyen f (x, y, z) = α7 xyz + α6 xy + α5 yz + α4 zx + α3 x + α2 y + α1 z + α0 egy nemline´ aris háromv´ altoz´ os kifejezésf¨ uggvény. Ekkor minden olyan φ permutációra, amely eleme Aut(f )-nek, a következ˝o két lehet˝oség egyike teljes¨ ul: • φ eleme Aut(Ba)-nak • φ el˝ o´ all egy Aut(Ba)-beli elemnek és egy nem-identikus eltolásnak a kompoz´ıci´ ojaként. 60

Bizony´ıt´ as. Ha az fxy , fyz , fzx f¨ uggvények legalább egyike nemlineáris, akkor az 5. lemma miatt készen vagyunk. • Ha α7 = 1 és α6 = α5 akkor fyz nemlineáris. Az α5 = α4 és a α4 = α6 alesetek hasonl´ oak, és ezek k¨ oz¨ ul legalább az egyik fennáll. • Ha α7 = 0 és α4 , α5 , α6 mindegyike 0, akkor bármely két változó azonos´ıtása nemline´ aris f¨ uggvényt eredményez. • Ha α7 = 0 és α4 , α5 , α6 köz¨ ul pontosan az egyik 1, feltehetj¨ uk, hogy α4 az, akkor fyz megfelel. • Ha α7 = 0 és α4 , α5 , α6 köz¨ ul pontosan az egyik 0, feltehetj¨ uk, hogy α4 az, akkor fxy megfelel. • Ha α7 = 0 és α4 , α5 , α6 mindegyike 1, u ´gy f (x, y, z) = xy + yz + zx + α3 x + α2 y + α1 z + α0 alak´ u. Ekkor ha α1 , α2 , α3 között az 1-esek száma 0 vagy 2, az f (x + c, y + c, z + c) = xy + yz + zx + c + α3 x + α3 c + α2 y + α2 c + α1 z + α1 c + α0 = f (x, y, z) + (α1 + α2 + α3 + 1)c azonosság miatt minden c ∈ Ba elemre a tc (a) = a + c eltolás meg˝orzi f -et. Legyen φ tetsz˝oleges f -et meg˝orz˝o permut´ aci´ o. Defini´ aljuk a φ˜ = tφ(0) ◦ φ permutációt (φ(x) ˜ = φ(x) + φ(0)), megmutatjuk, hogy φ˜ eleme Aut(Ba)-nak. A φ˜ permutáció meg˝orzi f -et, és φ(0) ˜ = 0, ´ıgy meg˝ orzi a g(x, y) = f (x, y, 0) f¨ uggvényt is, ami viszont egy nemline´ aris kétv´ altoz´ os kifejezésf¨ uggvény, ´ıgy φ˜ ∈ Aut(Ba) az 5. lemma miatt. A t−1 ˜ = φ egy a keresett t´ıpus´ u felbontása φ-nek. φ(0) ◦ φ • Ha pedig α7 = 0, és α4 , α5 , α6 mindegyike 1, és α1 , α2 , α3 között páratlan sok 1 van, akkor f (a, a, a) = (fyz )xy (a) = 0 vagy f (a, a, a) = 1 minden a ∈ Ba( ) ra, ezért a g(x, y) = f x, y, f (x, x, x) f¨ uggvény egy nemlineáris kétváltozós kifejezésf¨ uggvény, ´ıgy minden az f -et, és ´ıgy g-t is meg˝orz˝o φ permutációra φ ∈ Aut(Ba) az 5. lemma miatt. Teh´ at ha f (x, y, z) = xy + yz + zx + α3 x + α2 y + α1 z + α0 alak´ u, ahol α1 , α2 , α3 k¨ oz¨ ott az 1-esek sz´ ama 0 vagy 2, akkor az alábbi két feltétel ekvivalens: • Egy φ permut´ aci´ o meg˝ orzi az f f¨ uggvényt. • Egy φ permut´ aci´ o el˝ o´ all φ = t ◦ ψ alakban, ahol t egy eltolás, és ψ ∈ Aut(Ba). Jel¨ olj¨ uk M -mel a medi´ ans m˝ uveletét: M (x, y, z) = xy + yz + zx, továbbá jelölje Aut(M ) a medi´ ans m˝ uveletét meg˝orz˝o permutációk csoportját. 8. t´ etel. Aut(M ) = T o Aut(Ba) Bizony´ıt´ as. Mivel Aut(M ) minden eleme meg˝orzi M (x, y, z) = xy + yz + xz-et, ´ıgy Aut(M ) minden φ eleme el˝oáll φ = t ◦ ψ alakban (t ∈ T és ψ ∈ Aut(Ba)) a 7. lemma alapj´ abb´ ⟨ an. Tov´ ⟩ a Aut(Ba) és T minden eleme meg˝orzi a mediánst, ´ıgy Aut(M ) = Aut(Ba), T . Az Aut(Ba) és T csoportoknak egyetlen közös eleme van, az identitás, mert Aut(Ba) minden eleme fix´ alja a 0-t, és az identitás az egyetlen 0-t fixáló eltolás. Be kell még látnunk, hogy T normálosztó, ehhez elég megmutatni, hogy tetsz˝oleges tc ∈ T és φ ∈ Aut(Ba) (esetén φ−1 ) ◦ tc ◦ φ ∈ T , amit az alábbi számolás bizony´ıt: (φ−1 ◦ tc ◦ φ)(x) = φ−1 φ(x) + c = (φ−1 ◦ φ)(x) + φ−1 (c) = tφ−1 (c) (x). 61

A háromn´ al t¨ obb v´ altoz´ os nemlineáris kifejezésf¨ uggvények esetét vissza fogjuk vezetni a legfeljebb három v´ altozós esetre. 9. lemma. Legyen f egy nemlineáris Boole-f¨ uggvény, amelynek aritása k, és k legal´ abb 4. Ekkor léteznek olyan 1 ≤ i < j ≤ k indexek melyekre fij is nemlineáris. Bizony´ıt´ as. H´ arom alesetre bontunk: • Ha van olyan ⃗ε amelyre 2 ≤ |⃗ε| ≤ k − 2 és α⃗ε = 1. Ekkor léteznek olyan 1 ≤ i < j ≤ k indexek, melyekre ⃗εi = ⃗εj = 0. Erre az ⃗ε-ra az fij f¨ uggvényben is teljes¨ ul α⃗ε = 1 (´ıgy fij is nemlineáris), mivel az xi -nek xj helyébe való behelyettes´ıtése v´ altozatlanul hagyja azokat a monomokat, melyek sem xi -t sem xj -t nem tartalmazzák, és ilyenek nem képz˝odnek más monomokból a behelyettes´ıtés sor´ an. • Ha az egyetlen legal´ abb másodfok´ u tag az összes változó szorzata, akkor b´ armelyik i, j p´ ar megfelel˝o. • Ha pedig minden legal´ abb másodfok´ u monom foka legalább k − 1, és van (k − 1)-ed fok´ u monom, akkor legyen ⃗ε egy ilyen (k − 1)-ed fok´ u monomhoz tartoz´ o vektor. Legyenek továbbá 1 ≤ i < j ≤ k olyan indexek, melyekre ⃗εi = ⃗εj = 1. Ekkor az f -nek ⃗ε-hez tartozó monomjából az fij -nek egy (k − 2)-ed fok´ u monomja lesz, amelynek egy¨ utthatója nem lehet 0, mivel a helyettes´ıtéssel csak f -nek a (k − 1)-ed fok´ u monomjaiból képz˝odhet (k − 2)-ed fok´ u, és azok k¨ oz¨ ul is csak a kiindulásiból. Ennek alapján, ha f tetsz˝oleges nemlineáris kifejezésf¨ uggvény, akkor a 9. lemma miatt létezik olyan g nemlineáris kifejezésf¨ uggvény, amely legfeljebb három változ´ os, és Aut(Ba) ≤ Aut(f ) ≤ Aut(g), tehát az 5. és a 7. lemmák alapján Aut(Ba) ≤ Aut(f ) ≤ Aut(M ). Most megmutatjuk, hogy valamelyik tartalmazás helyén egyenl˝ oségnek kell állnia. 10. lemma. Legyen f nemlineáris kifejezésf¨ uggvény. Ekkor Aut(f ) = Aut(Ba) vagy Aut(f ) = Aut(M ). Bizony´ıt´ as. Legyen G = Aut(f ). Mivel Aut(M ) = T o Aut(Ba) és Aut(Ba) ≤ G ≤ Aut(M ), ezért G-t egyértelm˝ uen meghatározza a T ∩ G részcsoport. Legyen c, d ∈ Ba olyan elemek, amelyek egy orbitra esnek Aut(Ba) szerint. Tegy¨ uk fel, hogy tc ∈ G, megmutatjuk, hogy ekkor td ∈ G(is fennáll.) Legyen φ ∈ Aut(Ba) olyan, hogy φ(d) = c ekkor: (φ−1 ◦ tc ◦ φ)(x) = φ−1 φ(x) + c = (φ−1 ◦ φ)(x) + φ−1 (c) = td (x). Mivel Ba-nak a nem 0 vagy 1 elemei azonos Aut(Ba) szerinti orbitra esnek, és tc ∈ T ∩ G egyszerre teljes¨ ul az összes azonos orbiton lév˝o c-re, ´ıgy a T ∩ G részcsoport az alábbi négy egyike lehet (felhasználva, hogy t0 = id ∈ G): { } • T ∩ G = tc | c ∈ {0} ; { } • T ∩ G = tc | c ∈ {0, 1} ; { } • T ∩ G = tc | c ∈ Ba \ {1} ; • T ∩ G = {tc | c ∈ Ba}. 62

Ezek k¨ oz¨ ul az els˝ o a G = Aut(Ba), a negyedik a G = Aut(M ) esetnek felel meg, a második és a harmadik lehet˝oségr˝ol pedig megmutatjuk, hogy nem állhatnak fenn. { } A harmadik lehet˝ oséget kizárja, hogy a T ∩ G = tc | c ∈ Ba \ {1} halmaz nem is részcsoport: legyen a ∈ Ba \ {0, 1}, ekkor ta és ta+1 is eleme T ∩ G-nek, ´ıgy a kompoz´ıci´ ojuk (ta+1 ◦ ta )(x) = x + a + a + 1 = t1 (x) is eleme kellene, hogy legyen. A második lehet˝ oség megad egy létez˝o Aut(Ba) ≤ G ≤ Aut(M ) zárt csoportot, err˝ ol kell bel´ atnunk, hogy nem áll el˝o funkcionális redukt automorfizmuscsoportjaként. Jel¨ olje B2 a kételem˝ u Boole-algebrát. Legyen f olyan kifejezésf¨ uggvény, melyet meg˝oriz a t1 permutáció. Ekkor az f (x1 + 1, x2 + 1, . . . , xk + 1) = f (x1 , x2 , . . . , xk ) + 1 és az f (x1 + 0, x2 + 0, . . . , xk + 0) = f (x1 , x2 , . . . , xk ) + 0 azonosságok is teljes¨ ulnek f -re, azaz az f (x1 + c, x2 + c, . . . , xk + c) = f (x1 , x2 , . . . , xk ) + c azonoss´ ag teljes¨ ul minden c ∈ B2 -re. Tehát ez az azonosság teljes¨ ul a B2 által gener´ alt variet´ as minden algebrájában, ´ıgy Ba-ban is. Így ha G = Aut(f ) valamilyen f nemlineáris kifejezésf¨ uggvényre, akkor t1 ∈ Aut(f )-b˝ol következik, hogy tc ∈ Aut(f ) tetsz˝ oleges c-re. A 3. k¨ ovetkezmény alapján ´ıgy egy f nemlineáris kifejezésf¨ uggvényre az alábbi két eset pontosan egyike teljes¨ ul: • Az f m˝ uvelet és a szorz´ as m˝ uvelete kölcsönösen definiálható egymásból. • Az f m˝ uvelet és a medi´ ans m˝ uvelete kölcsönösen definiálható egymásból. Ezzel befejezt¨ uk a nemline´ aris kifejezésf¨ uggvényeket meg˝orz˝o permutációk le´ırását.

3. A line´ aris funkcion´ alis reduktok Ebben a fejezetben a line´ aris funkcionális reduktokat fogjuk meghatározni, kölcsönös defini´ alhat´ os´ ag erejéig. Minden line´ aris kifejezésf¨ uggvény l(x1 , x2 , . . . , xk ) = x1 + x2 + . . . + xk + α alak´ u, ahol α = 0 vagy α = 1. Tekints¨ uk az al´ abbi nyolc kifejezésf¨ uggvényt: (1) 0, (2) 1, (3) x, (4) ¬(x) = x + 1, (5) +0 (x, y) = x + y, (6) +1 (x, y) = x + y + 1, (7) Σ(x, y, z) = x + y + z, (8) Σ1 (x, y, z) = x + y + z + 1. Ezekre a line´ aris f¨ uggvényekre mostantól mint kanonikus line´ aris f¨ uggv´ enyekre fogunk hivatkozni, annak ellenére, hogy a konstans 1 f¨ uggvény nem lineáris: 63

f (a + b) = 1 ̸= 0 = f (a) + f (b). A továbbiakban sz¨ ukség¨ unk lesz ezeknek a f¨ uggvényeknek az automorfizmuscsoportjaira, most ezek le´ırása következik. 1. csoport: Az f = 0 esetben Aut(0) a 0 stabilizátora a Sym(Ba) csoportban. Mivel Aut(0)hoz tetsz˝ oleges φ ∈ / Aut(0) a 0-t nem fixáló permutációt generátorként hozzávéve m´ ar az egész Sym(Ba)-et kapjuk, ´ıgy ez a csoport maximális valódi részcsoportja Sym(Ba)-nek. 2. csoport: Az f = 1 esetben Aut(1) az 1 stabilizátora a Sym(Ba) csoportban. Az Aut(0) csoporthoz hasonl´ oan ez a csoport is maximális valódi részcsoportja Sym(Ba)-nek. 3. csoport: Az f (x) = x esetben Aut(x) maga a Sym(Ba) csoport, amely természetesen tartalmazza az ¨ osszes redukt automorfizmuscsoportját. 4. csoport: Az ¬(x) = x + 1 esetben tekints¨ uk Ba egy tetsz˝oleges I maximális ideálját. Defini´ aljuk a k¨ ovetkez˝ o két csoportot: Sym{I} (Ba) jel¨ olje a Sym(I) csoportot, annak hatását kiterjesztve I-r˝ol a teljes Ba-ra. Egy φ tetsz˝ oleges Sym(I)-beli permutáció hatását a következ˝oképpen terjessz¨ uk ki: φ(x) = φ(x) ha x ∈ I, illetve φ(x) = φ(x + 1) + 1 ha x ∈ / I. Másképpen megfogalmazva, Sym{I} (Ba) az I ideált mint halmazt fixáló permutációk csoportja Sym(Ba)-ban. Z2I pedig jel¨ olje azt a csoportot, amely pontosan azokból a φ permutációkból áll, amelyekre teljes¨ ul, hogy minden x ∈ Ba elemre φ(x) = x vagy φ(x) = x + 1. Ez a Z2I csoport az I maxim´ alis ideál választásától f¨ uggetlen¨ ul mindig ugyanaz, mert a defin´ıci´ oj´ aban sehol sem szerepel I. A jelölést az indokolja, hogy Z2I természetes m´ odon izomorf a Z2 csoport direkt hatványával, ahol az egyes direkttényez˝ok I elemeivel vannak indexelve. Megmutatjuk, hogy Aut(¬) = Z2I o Sym{I} (Ba). A Z2I csoport norm´ alosztó lesz Aut(¬)-ban: legyen φ ∈ Z2I és ψ ∈ Aut(¬) két permut´ aci´ o, megmutatjuk, hogy ψ −1 φψ is eleme Z2I -nek. Ez ekvivalens azzal, hogy minden x ∈ Ba elemre ψ −1 φψ(x) egyenl˝o x-szel vagy (x + 1)-gyel. Két esetre bontunk: ( ) • Ha φ ψ(x) = ψ(x), akkor ψ −1 φψ(x) = x. ( ) ( ) ( ) • Ha φ ψ(x) = ψ(x) + 1, akkor ψ −1 φψ(x) = ψ −1 ¬ψ(x) = ¬ψ −1 ψ(x) = x + 1. Tov´ abb´ a Z2I -nek és Sym{I} (Ba)-nek a metszete csak az identikus permutációb´ ol áll, mivel Z2I -ben nincs olyan permutáció, amely I valamely elemét egy másik, t˝ole k¨ ul¨ onb¨ oz˝ o I-beli elembe vinné. 64

Ahhoz, hogy bel´ assuk, hogy Aut(¬) el˝oáll a Z2I o Sym{I} (Ba) szemidirekt szorzatként, megmutatjuk még, hogy minden φ ∈ Aut(¬) permutáció el˝oáll egy Sym{I} (Ba)-beli és egy Z2I -beli permutáció kompoz´ıciójaként. Legyen φ ∈ Aut(¬) tetsz˝ oleges permut´ aci´ o, defini´ aljuk a φ˜ permutációt a következ˝oképpen: • Ha x ∈ I, akkor φ(x) ˜ legyen φ(x) és φ(x) + 1 köz¨ ul az, amelyik I-be esik. • Ha x ∈ / I, akkor φ(x) ˜ legyen φ(x) és φ(x) + 1 köz¨ ul az, amelyik nem esik I-be. Ekkor φ˜ ∈ Sym{I} (Ba), és φ˜−1 ◦ φ ∈ Z2I , és ezek kompoz´ıciójaként φ el˝oáll. Teh´ at minden, a komplementer m˝ uveletét tartó permutáció u ´gy áll el˝o, hogy az {x, x + 1} p´ arok halmaz´ an tetsz˝olegesen hat, majd minden páron bel¨ ul egymástól f¨ uggetlen¨ ul vagy megcseréli a két elemet, vagy nem. 5. csoport: A +0 (x, y) = x + y esetben a funkcionális redukt egy vektortér: F∞ 2 . Ennek automorfizmus-csoportja defin´ıci´ o szerint az általános lineáris csoport: Aut(+0 ) = GL(∞, 2). 6. csoport: A +1 (x, y) = x + y + 1 esetben a redukt szintén egy vektortér, melynek m˝ uveletei nem azonosak a +0 (x, y) = x + y vektortér m˝ uveleteivel (például +0 nulleleme a 0, +1 nulleleme az (1). Viszont) kettej¨ uk között megadható egy izomorfizmus: a τ1) el( tol´ as, ugyanis τ1 +1 (x, y) = x + y + 1 + 1 = x + 1 + y + 1 = +0 τ1 (x), τ1 (y) és ( ) ( ) τ1−1 +0 (x, y) = x + y + 1 = +1 τ1−1 (x), τ1−1 (y) . Ennek alapján vezess¨ uk be a következ˝ o jel¨ olést: Aut(+1 ) = GL1 (∞, 2). Izomorf strukt´ urák automorfizmuscsoportja is izomorf, azaz Aut(+1 ) = GL1 (∞, 2) ∼ = GL(∞, 2) = Aut(+0 ). 7. csoport: A Σ(x, y, z) = x + y + z esetben a funkcionális redukt egy affin tér. Legyen x, y, z, v ∈ Ba négy p´ aronként k¨ ul¨ onb¨ oz˝ o elem. Ezekre Σ(x, y, z) = v akkor és csak akkor áll fenn, ha az x, y, z, v elemek egy kétdimenziós affin alteret alkotnak: Σ(x, y, z) = v ⇔ x + y + z = v, teh´ at az {x, y, z, v} elemek a {0, y + x, z + x, v + x} kétdimenziós line´ aris altér x-szel val´ o eltoltj´ at alkotják. Σ-t meg˝ orzik (az x0 m˝ uveletet is meg˝orz˝o) GL(∞, 2)-beli permutációk és az eltol´ asok is. Tov´ abb´ a a T eltol´ asok csoportja normálosztó Aut(Σ)-ban, T és GL(∞, 2) egy¨ utt gener´ alj´ ak az egész Aut(Σ)-t, és metszet¨ uk csak az identikus permutáció. Azaz az Aut(Σ) automorfizmuscsoport el˝oáll mint a T o Aut(+0 ) szemidirekt szorzat. Szimmetriaokokb´ ol Aut(Σ) mint a T o Aut(+1 ) szemidirekt szorzat is fel´ırható.

65

8. csoport: Vég¨ ul a Σ1 (x, y, z) = x + y + z( + 1 esetben ) Σ1 seg´ıtségével definiálhatjuk a ¬(x) = g(x, x, x) és a Σ(x, y, z) = Σ1 x, y, ¬(z) m˝ uveleteket. Másrészt ¬(x) és Σ(x, y, z) seg´ ıts´ e g´ e vel is defini´ a lhatjuk Σ (x, y, z)-t a következ˝o módon: Σ1 (x, y, z) = 1 ( ) Σ x, y, ¬(z) . Teh´ at a 4. k¨ ovetkezmény alapján Aut(Σ1 ) = Aut(Σ) ∩ Aut(¬). Mivel az eltol´ asok meg˝ orzik Σ1 -et, ´ıgy T részcsoportja Aut(Σ1 )-nek. Felhaszn´ alva, hogy T ▹ Aut(Σ), a T csoport normálosztó lesz Aut(Σ1 )-ban is. Az Aut(+0 ) = GL(∞, 2) csoportnak az Aut(Σ1 ) csoportba es˝o része a komplementert tart´ o line´ aris permutációkból áll. Belátjuk, hogy ezek pontosan az 1-et fix´ al´ o line´ aris permut´ aci´ ok: legyen φ ∈ Aut(+0 ) komplementertartó. Mivel φ fixálja a 0-t, ´ıgy φ fix´ alja ¬0 = 1-et is. Ford´ıtva, ha φ ∈ Aut(+0 ) meg˝orzi az 1-et, akkor meg˝ orzi a komplementerséget is: φ(x + 1) = φ(x) + φ(1) = φ(x) + 1. Az 1-et fixáló line´ aris permut´ aciók csoportja megegyezik az Aut(+0 ) ∩ Aut(+1 ) csoporttal. Az el˝ oz˝ oekb˝ ovetkezik, hogy) Aut(Σ1() = Aut(Σ) ∩ Aut(¬))= (T o Aut(+0 )) ∩ ( ol k¨ Aut(¬) = T o Aut(+0 ) ∩ Aut(¬) = T o Aut(+0 ) ∩ Aut(+1 ) . 11. lemma. Minden l line´ aris kifejezésf¨ uggvényhez létezik pontosan egy f kanonikus line´ aris f¨ uggvény, amelyre teljes¨ ul, hogy l és f kölcsönösen definiálhatóak egym´ asb´ ol els˝ orend˝ u formul´ ak seg´ıtségével. Bizony´ıt´ as. Legyen l(x1 , x2 , . . . , xk ) = x1 + x2 + . . . + xk + α. El˝ osz¨ or bel´ atjuk olyan f kanonikus lineáris f¨ uggvény létezését, amelyre f és l k¨ olcs¨ on¨ osen defini´ alhat´ o egymásból, az egyértelm˝ uség bizony´ıtását kés˝obb végezz¨ uk el. Minden olyan f¨ uggvény, amelyre k < 2, szerepel a listában, ´ıgy választhatjuk o¨nmagukat a megfelel˝ o f -nek. Ha k > 1 páros sz´ am, akkor az f (x, y) = x + y + α jó választás. Az egyik irány´ u defini´ alhat´ os´ agot f (x, y) = l(x, y, y, . . . , y) bizony´ıtja, a másik irányhoz definiáljuk az( al´ abbi f¨ uggvényeket )rekurz´ıvan: l2 = f (x1 , x2 ) és j > 2-re lj (x1 , x2 , . . . , lj ) = f l(x1 , x2 , . . . , xj−1 ), xj . Ekkor l = lk . Ha pedig k > 1 páratlan sz´ am akkor az f (x, y, z) = x + y + z + α jó választás. Az egyik ir´ any´ u defini´ alhat´ os´ agot f (x, y, z) = l(x, y, z, z, . . . , z) bizony´ıtja, a másik ir´ anyhoz defini´ aljuk az al´ abbi f¨ uggvényeket rekurz´ıvan: l1 = f (x1 , x2 , x3 ) és j > 3-ra (

lj (x1 , x2 , . . . , x2j+1 ) =

) = f l(x1 , x2 , . . . , x2j−1 ), f (x2j , x2j , x2j ), f (x2j+1 , x2j+1 , x2j+1 ) . Ekkor l = l(k−1)/2 . Be kell l´ atnunk még a megfelel˝o f egyértelm˝ uségét. Ha lenne olyan l lineáris kifejezésf¨ uggvény, amihez t¨ obb olyan f kanonikus lineáris f¨ uggvény is létezne, hogy l és f k¨ olcs¨ on¨ osen defini´ alhat´ oak egymásból els˝orend˝ u formulák seg´ıtségével, akkor ezek az f -ek is k¨ olcs¨ on¨ osen definiálhatóak lennének egymásból, ´ıgy megegyezne az automorfizmuscsoportjuk is. Ezért a 3. következmény alapján f egyértelm˝ uségét bizony´ıthatjuk u ´gy, ha a list´ ank minden f¨ uggvényének meghatározzuk az automorfizmuscsoportj´ at, és ezek k¨ ul¨ onböz˝onek bizonyulnak. 66

A nyolc automorfizmuscsoportot jellemezt¨ uk ennek a lemmának a kimondása el˝ott, és k¨ ul¨ onb¨ oz˝ onek bizonyultak. A fejezet további részében pontos tartalmazási viszonyaikat is meg fogjuk határozni, amib˝ol szintén következik, hogy ez a nyolc csoport p´ aronként k¨ ul¨ onb¨ oz˝ o.

1. ´ abra. A funkcion´ alis reduktok h´ al´ oja, az automorfizmuscsoportok tartalmaz´ as szerinti rendezésével

Célunk annak megmutat´ asa, hogy a Ba megszámlálható atommentes Boolealgebra funkcion´ alis reduktjainak automorfizmuscsoportjai az 1. ábrán látható hálót alkotj´ ak a tartalmaz´ asra nézve. Emlékezz¨ unk rá,hogy ennek ismerete azért lehet hasznos, mert seg´ıtségével Ba feletti kifejezésf¨ uggvények tetsz˝oleges H halmazára meg tudjuk hat´ arozni azokat a kifejezésf¨ uggvényeket, amelyeket ki lehet fejezni H-beli f¨ uggvényekkel els˝ orend˝ u formulák seg´ıtségével. Ehhez csak annyit kell tenn¨ unk, hogy megkeress¨ uk a h´ al´ o legb˝ovebb olyan csoportját, amelynek minden eleme meg˝ orzi az ¨ osszes H-beli kifejezésf¨ uggvényt: legyen ez a csoport G. Ekkor H-ból pontosan azok a kifejezésf¨ uggvények fejezhet˝oek ki els˝orend˝ u formulákkal, amelyeket G meg˝ oriz. Az egyes csoportok karakterizációi alapján ezek a kifejezésf¨ uggvények egyszer˝ uen le´ırhat´ oak. Annak megmutat´ as´ ahoz, hogy a háló tényleg ´ıgy néz ki, el˝oször bebizony´ıtjuk a h´ al´ o koatomjair´ ol, hogy antiláncot alkotnak, majd le´ırjuk a bel˝ol¨ uk metszetképzéssel megkaphat´ o elemeket. Legvég¨ ul megkeress¨ uk annak a két zárt csoportonak 67

a helyét a h´ al´ oban, amelyek nemlineáris f¨ uggvények automorfizmuscsoportjaként állnak el˝ o. 12. lemma. A kanonikus line´ aris f¨ uggvények automorfizmuscsoportjaib´ ol metszet-] [ képzéssel megkaphat´ o csoportok az 1. ábrán l´ atható háló Aut(+0 , 0, 1), Aut(∅) intervallum´ at alkotj´ ak a tartalmazásra, mint rendezésre nézve. Bizony´ıt´ as. El˝ osz¨ or jellemezz¨ uk az adott intervallumban szerepl˝o, eddig még nem le´ırt három csoportot: 9. csoport: Az Aut(0, 1) csoport a 0 és 1 elemek pontonkénti stabilizátora. Mivel tetsz˝oleges φ az 1-et nem fix´ al´ o permut´ aci´ ot generátorelemként hozzávéve már a teljes Aut(0)-t kapjuk, ´ıgy Aut(0)-nak maxim´ alis valódi részcsoportja. Hasonlóan maximális valódi részcsoportja Aut(1)-nek is. 10. csoport: Az Aut(¬, 0, 1) csoport értelemszer˝ uen az Aut(0), Aut(1) és Aut(¬) csoportok metszete. Hasonl´ oan ahhoz, ahogy Aut(¬) el˝oáll a Z2I o Sym{I} (Ba) szemidirekt ( ) ( ) szorzatként, Aut(¬, 0, 1) is felbontható: Aut(¬, 0, 1) = Z2I 0 o Sym{I} (Ba) 0 . Itt ( I) ( ) Z2 0 és Sym{I} (Ba) 0 a 0 stabilizátorait jelölik a Z2I és a Sym{I} (Ba) csoportokban. 11. csoport: Az Aut(+0 , 0, 1) csoport már el˝oker¨ ult Aut(Σ1 ) szemidirekt szorzatként való jellemzésénél. Az 1-et fix´ al´ o, vagy ekvivalensen a komplementer m˝ uveletét meg˝orz˝o line´ aris permut´ aciók csoportja. Megmutatjuk, hogy az Aut(0), Aut(1), Aut(Σ) és Aut(¬) csoportok antiláncot alkotnak. • Legyenek a, b ∈ Ba \ {0, 1} tetsz˝oleges elemek, melyek nem egymás komplementerei. Ekkor az (a, a + 1, b, 1) ciklus eleme Aut(0)-nak, jelölj¨ uk φ-vel. Ekkor φ(1) = a ̸= 1 miatt Aut(0) * Aut(1). φ(¬a) = b (̸= a = ¬φ(a) miatt Aut(0) * Aut(¬). ) ( ) Illetve φ Σ(a, a + 1, 1) = 0 ̸= a + b + 1 = Σ φ(a), φ(a + 1), φ(1) miatt Aut(0) * Aut(Σ). • Hasonl´ oan bizony´ıthat´ o, hogy Aut(1) * Aut(0), Aut(1) * Aut(¬) és Aut(1) * Aut(Σ). • Most legyenek a, b ∈ Ba \ {0, 1} tetsz˝oleges elemek, melyek nem egymás komplementerei. Ekkor az (a, b, 0, a + 1, b + 1, 1) ciklus eleme Aut(¬)-nak, jel¨ olj¨ uk φ-vel. Mivel φ sem a 0-t, sem az 1-et nem fixálja, ´ıgy Aut(¬) * Aut(0) és Aut(¬) * Aut(1). Tov´ abbá ( ) ( ) φ Σ(a, b, 0) = a + b ̸= a + b + 1 = Σ φ(a), φ(b), φ(0) miatt Aut(¬) * Aut(Σ). 68

• Legyen τa (x) = x + a tetsz˝oleges eltolás. Ekkor τa meg˝orzi Σ-t, viszont a ̸= 0 esetén τa nem fix´ alja sem a 0-t, sem az 1-et, ´ıgy Aut(Σ) * Aut(0) és Aut(Σ) * Aut(1). Legyen φ olyan GL(∞, 2)-beli permutáció, amely nem fixálja az 1-et, és ´ıgy nem tartja a ¬ m˝ uveletet, mivel GL(∞, 2) minden eleme fixálja a 0-t. Mivel Aut(+0 ) = GL(∞, 2) ⊂ Aut(Σ), ´ıgy Aut(Σ) * Aut(¬). Most az Aut(0), Aut(1), Aut(Σ), Aut(¬) antilánc elemeib˝ol képezhet˝o metszeteket fogjuk meghat´ arozni. A páronkénti metszetek: • Aut 0 ∩ Aut 1 = Aut 0, 1 a stabilizátorok defin´ıciója alapján. • Aut(0) ∩ Aut(Σ) = Aut(+0 ) = GL(∞, 2), a 4. következm´ enyt haszn´ alva ( ) a +0 (x, y) = Σ(x, y, 0), 0 = +0 (x, x) és Σ(x, y, z) = +0 x, +0 (y, x) formul´ ak miatt. • Aut(0) ∩ Aut(¬) = Aut(¬, 0, 1) • Aut(1) ∩ Aut(Σ) = Aut(+1 ) = GL1 (∞, 2) a 4. következm´ enyt )használva ( az +1 (x, y) = Σ(x, y, 1), 1 = +1 (x, x) és Σ(x, y, z) = +1 x, +1 (y, x) formulák miatt. • Aut(0) ∩ Aut(¬) = Aut(¬, 0, 1). • Aut(Σ) ∩ Aut(¬) = ( ) Aut(Σ1 ) a 4. következményt használva a Σ(x, y, z) = Σ1 x, y, Σ1 (z, z, z) , ¬x = Σ1 (x, x, x) és Σ1 (x, y, z) = Σ(x, y, ¬z) formulák miatt. A h´ armas metszetek: • Aut(0) ∩ Aut(1) ∩ Aut(Σ) = Aut(+ ( 0 , 1) a 4.) következményt használva a 0 = +0 (x, x), 1 = 1, Σ(x, y, z) = +0 x, +0 (y, x) , illetve +0 (x, y) = Σ(x, y, 0) és 1 = 1 formul´ ak miatt. • Aut(0) ∩ Aut(1) ∩ Aut(¬) = Aut(¬, 0, 1). • Aut(0) ∩ Aut(Σ) ∩ Aut(¬) = Aut(+ ovetkezményt használva 0 , 1) )a 4. k¨ ( a 0 = +0 (x, x), Σ(x, y, z) = +0 x, +0 (y, x) , ¬x = +0 (x, 1), illetve +0 (x, y) = Σ(x, y, 0) és ¬0 = 1 formulák miatt. • Aut(1) ∩ Aut(Σ) ∩ Aut(¬) (= Aut(+0 , )1) a 4. következményt használva az 1 = 1, Σ(x, y, z) = +0 x, +0 (y, x) , ¬x = +0 (x, 1), illetve +0 (x, y) = Σ(x, y, ¬1) és 1 = 1 formulák miatt. Vég¨ ul az antil´ anc mind a négy elemének metszete: • Aut(0) ∩ Aut(1) ∩ Aut(Σ) ∩ Aut(¬) = Aut(+( 0 , 1) a 4. k¨ )ovetkezményt haszn´ alva a 0 = +0 (x, x), 1 = 1, Σ(x, y, z) = +0 x, +0 (y, x) , ¬x = +0 (x, 1), illetve +0 (x, y) = Σ(x, y, 0) és ¬0 = 1 formulák miatt. Ennek alapján minden kanonikus lineáris f¨ uggvény automorfizmuscsoportja el˝o´ all, mint az Aut(0), Aut(1), Aut(Σ), Aut(¬) antilánc valahány elemének metszete. Az Aut(x) = Sym(Ba) szimmetrikus csoport az u ¨res metszetnek felel meg. A kanonikus line´ aris f¨ uggvények automorfizmuscsoportjain k´ıv¨ ul még három csoport kaphat´ o meg metszetként. Ezek Aut(0, 1) = Sym(0,1) (Ba), ami a {0, 1} hal69

maz pontonkénti stabiliz´ atora a Sym(Ba) csoportban, az Aut(¬, 0, 1) csoport, illetve Aut(+0 , 1), ami az egy konstanssal ellátott vektortér automorfizmuscsoportja: GL(∞, 2) ∩ Sym(Ba)1 (Ba). Ezek felsorolásunkban a 9., 10. és 11. csoportok.

4. A megsz´ aml´ alhat´ o atommentes Boole-algebra funkcion´ alis reduktjai Ebben a fejezetben befejezz¨ uk a funkcionális reduktok kölcsönös definiálhatóság erejéig val´ o klasszifik´ al´ as´ at. Az el˝ oz˝ o fejezetben meghatároztuk, hogy valahány l1 , l2 , . . . lineáris kifejezésf¨ uggvényt meg˝ orz˝ o permut´ aci´ ok milyen zárt r´ alkothatnak, ezek a [eszcsoportokat ] zárt részcsoportok az 1. ábr´ an látható háló {+, 0, 1}, ∅ intervallumát alkotják a tartalmaz´ asra mint rendezésre nézve. Ezt a hálót fogjuk most kiegész´ıteni a nemline´ aris kifejezésf¨ uggvények által meghatározott lehetséges automorfizmusokkal. 13. t´ etel. A Ba funkcion´ alis reduktjai az 1. ábrán látható hálót alkotják, ahol a rendezés az automorfizmuscsoportok tartalmazása. Bizony´ıt´ as. A 10. lemma alapján egy f nemlineáris kifejezésf¨ uggvényre vagy Aut(f ) = Aut(Ba), vagy Aut(f ) = Aut(M ). Mivel tudjuk, hogy Aut(Ba) a háló minim´ alis eleme, ´ıgy csak Aut(M ) helyét kell meghatároznunk a hálóban. T ≤ Aut(M ) miatt Aut(M ) * Aut(0) és Aut(M ) * Aut(1), ´ıgy annyit kell még belátnunk, hogy Aut(M ) Aut(Σ1 ). A 8. tétel miatt Aut(M ) ≤ Aut(Σ1 ) bizony´ıtásához elég belátnunk, hogy az eltol´ asok meg˝ orzik Σ1 -et. Legyen τa (x) = x + a tetsz˝oleges eltolás, ekkor ( ) τa Σ1 (x, y, z) = x + y + z + 1 + a = x + a + y + a + z + a + 1 = ( ) = Σ1 τa (x), τa (y), τa (z) , teh´ at az eltol´ asok meg˝ orzik a Σ1 m˝ uveletet. A szigor´ u tartalmaz´ as belátásához kell mutatnunk olyan permutációt, amely meg˝ orzi a Σ1 m˝ uveletet, de nem tartja a mediánst. Ehhez elég mutatni olyan permut´ aci´ ot, ami fix´ alja a 0-t és az 1-et, továbbá tartja a +0 m˝ uveletét, viszont nem Boole-algebra automorfizmus. Ilyen tulajdonság´ u permutáció létezik: ha a, b ∈ Ba olyan elemek, melyekre a < b, akkor a, b, 1 lineárisan f¨ uggetlen elemek, ´ıgy van olyan permut´ aci´ o a line´ aris csoportban, amely a-t és b-t megcseréli, az 1-et pedig fixálja. Teh´ at tudjuk, hogy a Ba funkcionális reduktjai az 1. ábrán látható hálót alkotj´ ak, ahol a rendezés az automorfizmuscsoportok tartalmazása. Ennél azonban több is igaz: 14. t´ etel. Az 1. ábr´ an l´ athat´ o háló részhálója Sym(Ba) részcsoporthálójának, azaz zárt részcsoportok hál´ obeli egyes´ıtése Sym(Ba) általuk generált részcsoportjának felel meg. 70

A 14. tétel nem teljes¨ ul minden homogén ω-kategorikus algebrai strukt´ urára. Felmer¨ ul a kérdés, hogy tetsz˝oleges Boole-algebrának mik a funkcionális reduktjai k¨ olcs¨ on¨ os defini´ alhat´ oság erejéig. Probl´ ema. Legyen B tetsz˝ oleges Boole-algebra. Ha B-nek legalább 16 eleme van, akkor ugyanazok a funkcion´ alis reduktjai, mint a Ba megszámlálható atommentes Boole-algebr´ anak. Ha a B Boole-algebr´ anak kevés eleme van, akkor olyan funkcionális reduktok is k¨ olcs¨ on¨ osen defini´ alhat´ oak lehetnek egymásból, amelyek a Ba megszámlálható atommentes Boole-algebra esetén nem. Például ha B2 a kételem˝ u Boole-algebra, akkor csak a 0 konstans seg´ıtségével definiálható az 1: (x = 1) ⇔ (x ̸= 0). Amennyiben a fenti problémára a válasz igenl˝o, u ´gy annak bizony´ıtásában jóval kisebb szerepet kell kapniuk az automorfizmuscsoportokat használó technikáknak.

Irodalom [1] N. Ackerman, C. Freer, R. Patel, Invariant measures concentrated on countable structures. Preprint arXiv:1206.4011 [math.LO] (2012). [2] J. H. Bennett, The reducts of some infinite homogeneous graphs and tournaments. Rutgers university, doktori értekezés (1997). [3] M. Bodirsky, M. Pinsker, A. Pongr´ acz, The 42 reducts of the random ordered graph, bek¨ uldve (2013). [4] M. Bodirsky, M. Pinsker, Reducts of Ramsey Structures, Model Theoretic Methods in Finite Combinatorics, American Mathematical Society, Contemporary Mathematics, 558 (2011), 489–519. [5] P. J. Cameron, Oligomorphic permutation groups. London Mathematical Society Lecture Note Series, 152. Cambridge University Press (Cambridge, 1990). [6] P. J. Cameron, Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, 148 (1976), 127–139. [7] R. Fra¨ıssé, Sur certaines relations qui généralisent l’order des nombres rationnels, Comptes Rendus d’ l’Académie des Sciences de Paris, 237 (1953), 540–542. [8] C. W. Henson, A family of countable homogeneous graphs, Pacific Journal of Mathematics, 38 (1971), 69–83. [9] W. Hodges, Model theory. Encyclopedia of Mathematics and its Applications, 42. Cambridge University Press (Cambridge, 1993). [10] M. Junker, M. Ziegler, The 116 reducts of (Q, <, a), J. Symbolic Logic, 73 no. 3 (2008), 861–884. [11] D. Macpherson, A survey of homogeneous structures, Discrete Mathematics, 311(15) (2011), 1599–1634. [12] P. P. Pach, M. Pinsker, G. Pluh´ ar, A. Pongr´ acz, Cs. Szab´ o, Reducts of the random partial order, Advances in Mathematics, 267 (2014), pp. 94–120. [13] A. Pongr´ acz, Reducts of the Henson graphs with a constant, Annals of Pure and Applied Logic (2013), accepted. [14] S. Thomas, Reducts of the random graph, Journal of Symbolic Logic, 56(1) (1991), 176–181.

71

Bertalan Bodor, Kende Kalina: Functional reducts of the countable homogeneous Boolean algebra Let A = (A, f1 , . . . fn ) be an algebra on the set A with operations f1 , . . . , fn . A functional reduct of A is a structure B = (A, t1 , . . . , tk ) on the same set A and with operations t1 , . . . , tk such that every tj is a term function of A. In this paper we classify the functional reducts of the homogeneous countable Boolean algebra. We show that there are 13 such reducts. Bodor Bertalan

Kalina Kende



[email protected]

[email protected]

72

PRÍMEK, POLIGNAC, POLYMATH

Recommend Documents