i i “Jezernik” — 2019/1/11 — 7:37 — page 121 — #1 i i i i i i VERJETNOST KOMUTIRANJA URBAN JEZERNIK Universidad del Páıs Vasco Math. Subj. Class. (2010): 20P05, 20D60, 20F65 Verjetnost komutiranja je verjetnost, da v dani končni množici, opremljeni z binarno operacijo, dva naključno izbrana elementa komutirata. V članku razǐsčemo vpliv alge- braične strukture na njeno verjetnost komutiranja, pri čemer se osredotočimo predvsem na končne grupe. Razkrijemo nekaj lastnosti množice zavzetih verjetnosti komutiranja končnih grup. Predstavimo tudi sodobneǰse posplošitve pojma verjetnosti komutiranja na neskončne grupe. COMMUTING PROBABILITY Commuting probability is the probability that in a given finite set equipped with a binary operation, two randomly chosen elements commute. In this paper, we explore the influence of the algebraic structure of this set on its commuting probability, focusing especially on finite groups. Some properties of the set of all commuting probability values of finite groups are revealed. We also present modern generalizations of the concept of commuting probability to infinite groups. O verjetnosti komutiranja Opazujmo končno množico X, opremljeno z binarno operacijo. Verjetnost komutiranja vk(X) je verjetnost, da dva naključno in neodvisno izbrana elementa množice X komutirata glede na dano operacijo. Vrednost vk(X) izračunamo tako, da med vsemi urejenimi pari elementov v X izračunamo delež tistih, ki komutirajo. Verjetnost komutiranja sta sistematično prvič raziskovala Erdös in Turán med razvijanjem lastne verjetnostne metode [3]. V pričujočem članku si ta koncept ogledamo iz različnih zornih kotov, pri čemer za vodilo vzamemo interakcijo med algebraično strukturo dane množice X in njeno verjetnostjo komutiranja vk(X). Vstopimo s primeri. Primer 1. Za X vzemimo simetrično grupo S3, najmanǰso nekomutativno grupo. Spomnimo se, da S3 sestoji iz šestih permutacij na treh točkah, kot je prikazano na naslednji sliki. Dve različni permutaciji sta na sliki povezani Obzornik mat. fiz. 65 (2018) 4 121 i i “Jezernik” — 2019/1/11 — 7:37 — page 122 — #2 i i i i i i Urban Jezernik s povezavo, če in samo če komutirata. (2 3) (1 2) (1 2 3) (1 3 2) (1 3) () Verjetnost komutiranja grupe S3 izračunamo tako, da med vsemi urejenimi pari elementov izračunamo delež tistih, ki komutirajo. Število vseh urejenih parov elementov v S3 je 6 2 = 36. Komutirajoče pare preštejmo tako, da za vsak element posebej premislimo, s katerimi elementi komutira. Enota komutira z vsemi elementi. Dvocikli v S3 paroma ne komutirajo. Prav tako noben od dvociklov ne komutira z nobenim triciklom. Tricikla (1 2 3) in (1 3 2) komutirata. Hkrati ne pozabimo, da vsak element komutira sam s sabo. Tako je število vseh komutirajočih urejenih parov v S3 enako 6 + 3 · 2 + 2 · 3 = 18 in zato je verjetnost, da je naključno izbrani urejeni par komutirajoč, enaka vk(S3) = 18 36 = 1 2 . V simetričnih grupah vǐsjih redov Sn število urejenih parov elementov raste zelo hitro, komutirajoči pari pa so, razen disjunktnih ciklov, bolj iz- jemne sorte. Pričakujemo torej, da velja limn→∞vk(Sn) = 0. Res je tako, utemeljitev podamo v posledici 7. Primer 2. Za X vzemimo simetrije kvadrata, predstavljene kot diedrska grupa D4. Spomnimo se, da D4 sestoji iz štirih rotacij (okrog sredǐsča kvadrata za kote 0◦, 90◦, 180◦ in 270◦) in štirih zrcaljenj (dve preko simetral stranic in dve preko diagonal). Preštejmo komutirajoče pare. Enota grupe, tj. rotacija za 0◦, komutira z vsemi elementi. Vsaka od netrivialnih rotacij komutira z vsako od drugih 122 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 123 — #3 i i i i i i Verjetnost komutiranja rotacij. Rotacija za kot 180◦ komutira tudi z vsemi zrcaljenji, nobena od drugih dveh netrivialnih rotacij pa ne komutira z nobenim zrcaljenjem. Zr- caljenji komutirata, če in samo če sta istovrstni. Ugotovili smo torej, da enota komutira z 8 elementi, rotacija za 180◦ prav tako z 8 elementi, rota- ciji za 90◦ in 270◦ s 4 elementi, ter nazadnje vsako od štirih zrcaljenj s 4 elementi. Tako velja vk(D4) = 8+8+2·4+4·4 64 = 5 8 . Kvadrat lahko zamenjamo s poljubnim pravilnim n-kotnikom. Grupa simetrij pravilnega n-kotnika je diedrska grupa Dn. Ta sestoji iz n rotacij in n zrcaljenj. Število urejenih parov elementov je (2n)2, torej raste kvadratno z n. Vsaj takšno rast pa ima tudi število komutirajočih parov, saj vsaka od n rotacij komutira z vsako drugo. Velja torej vk(Dn) > n·n (2n)2 = 14 za vsak n. V posledici 12 premislimo, da velja limn→∞vk(Dn) = 1 4 . Primer 3. Za X vzemimo direktni produkt množic {0, 1} × {1, 2, . . . , n}. Na X definirajmo binarno operacijo ? na naslednji način: (i, j) ? (k, l) = { (i, j) če je j ≤ l; (k, l) sicer. Operacija ? torej vrne element, katerega druga komponenta je manǰsa, če pa sta drugi komponenti enaki, vrne prvi element. Hitro lahko preverimo, da je ta operacija asociativna, torej je (X, ?) polgrupa. Vsaka dva elementa z različnima drugima komponentama komutirata, elementa z enako drugo komponento pa komutirata le, če sta enaka. Komutirajočih parov je ve- liko, zato verjetnost komutiranja v X lažje izrazimo kot nasprotni dogodek nekomutiranja. Tako velja vk(X) = 1 − 2n (2n)2 = 1 − 12n . Z naraščajočim n na ta način najdemo nekomutativne polgrupe z verjetnostjo komutiranja poljubno blizu 1. Z modifikacijo tega primera sta Ponomarenko in Selinski pokazala, da je lahko verjetnost komutiranja končne polgrupe poljubno pozitivno racionalno število med 0 in 1. Izrek 4 ([13] – Ponomarenko in Selinski 2012). Za vsako racionalno število r ∈ (0, 1] obstaja končna polgrupa S, za katero velja vk(S) = r. Nekoliko bolj pestro je z množicami, v katerih je več algebraične struk- ture. Slika 1 prikazuje histogram verjetnosti komutiranja, ki jih dobimo, če opazujemo le grupe moči največ 256. Število takšnih grup je 63 104, le 516 od teh je komutativnih. Najmanǰsa možna verjetnost komutiranja je 121–137 123 i i “Jezernik” — 2019/1/11 — 7:37 — page 124 — #4 i i i i i i Urban Jezernik tukaj 1/28 ≈ 3,6 %. Verjetnosti komutiranja so sicer skoncentrirane okoli 22 %. Ne spreglejmo tudi presenetljivih praznin: na histogramu je videti cele intervale verjetnosti brez zavzetih vrednosti. 0.0 0.2 0.4 0.6 0.8 1.0 0 2000 4000 6000 8000 10000 12000 14000 16000 Slika 1. Histogram verjetnosti komutiranja grup moči kvečjemu 256. Ko na množico X dodamo še več algebraične strukture, recimo z do- datno operacijo, s katero X postane kolobar, so rezultati glede verjetnosti komutiranja sorodni tistim za grupe [10], čeravno se jih v literaturi najde manj. V nadaljevanju se zato osredotočimo na verjetnosti komutiranja grup. V naslednjih razdelkih podamo nekaj osnovnih lastnosti verjetnosti komu- tiranja končnih grup, dokažemo obstoj verjetnostnih lukenj in dosedanja opažanja še izostrimo, nazadnje pa pokažemo, kako lahko pojem verjetnosti komutiranja posplošimo na neskončne grupe. O strukturnem vplivu Osredotočeni smo na končne grupe in na razumevanje vpliva grupne struk- ture na verjetnost komutiranja. Zabeležimo najprej povezavo med verjetno- stjo komutiranja grupe in njenih podgrup ter kvocientov. Trditev 5. Naj bo G končna grupa in H njena podgrupa. Tedaj velja vk(G) ≤ vk(H). Če je H podgrupa edinka v G, velja vk(G) ≤ vk(G/H). Dokaz. Verjetnost komutiranja izrazimo eksplicitno kot delež komutirajočih parov med vsemi urejenimi pari v grupi G: vk(G) = |{(x, y) ∈ G×G : xy = yx}| |G|2 . 124 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 125 — #5 i i i i i i Verjetnost komutiranja Slednje zapǐsimo kot vk(G) = ∑ x∈G |{y ∈ G : xy = yx}| |G|2 in prepoznajmo centralizator CG(x) = {y ∈ G : xy = yx} ≤ G. Da lahko primerjamo vrednost vk(G) z vk(H), bo torej dovolj primerjati velikost CG(x) z velikostjo CH(x) = {y ∈ H : xy = yx} za vsak izbran x ∈ G. Očitno je CH(x) podgrupa grupe CG(x) in tako je CG(x) unija odsekov {aCH(x) : a ∈ CG(x)}. Vsakemu takemu odseku aCH(x) lahko na naraven način priredimo odsek grupe G po podgrupi H, in sicer aH. Hitro preve- rimo, da je to prirejanje dobro definirano in celo injektivno. Za a, b ∈ CG(x) namreč drži aH = bH natanko tedaj, ko je a−1b ∈ H, kar je ekvivalentno po- goju a−1b ∈ CG(x)∩H = CH(x), slednje pa je enako kot aCH(x) = bCH(x). Tako smo izpeljali neenakost |CG(x) : CH(x)| ≤ |G : H| med števili odsekov. Izpeljano neenakost uporabimo v gornjem zapisu verjetnosti komutira- nja: vk(G) = ∑ x∈G |CG(x)| |G|2 ≤ |G : H| ∑ x∈G |CH(x)| |G|2 . V zadnji vsoti gremo po elementih grupe G in preštejemo število elementov v H, ki z vsakim od njih komutirajo. S tem torej preštejemo komutirajoče pare v G×H. Te lahko preštejemo tudi tako, da gremo po elementih podgrupe H in preštejemo elemente v G, ki z njimi komutirajo. Tako dobimo vk(G) ≤ |G : H| ∑ x∈H |CG(x)| |G|2 . Še enkrat uporabimo neenakost med števili odsekov in zaključimo vk(G) ≤ |G : H|2 ∑ x∈H |CH(x)| |G|2 = ∑ x∈H |CH(x)| |H|2 = vk(H). Tako je dokazan prvi del trditve. Za dokaz drugega dela najprej razpǐsemo vk(G/H) = |{(xH, yH) ∈ G/H ×G/H : xyH = yxH}| |G/H|2 . Ob elementih x, y ∈ G je pogoj xyH = yxH ekvivalenten pogoju x−1y−1xy ∈ H. Veljavnost tega pogoja je neodvisna od menjave elementa x ali y s ka- kšnim drugim predstavnikom istega odseka xH ali yH. Tako lahko izrazimo vk(G/H) = |{(x, y) ∈ G×G : x−1y−1xy ∈ H}| |G/H|2 · |H|2 . 121–137 125 i i “Jezernik” — 2019/1/11 — 7:37 — page 126 — #6 i i i i i i Urban Jezernik Parov (x, y) ∈ G × G z lastnostjo x−1y−1xy ∈ H je vsaj toliko, kolikor je parov z lastnostjo x−1y−1xy = 1, se pravi xy = yx. S tem lahko omejimo verjetnost komutiranja v kvocientu, vk(G/H) ≥ |{(x, y) ∈ G×G : xy = yx}| |G|2 = vk(G), s čimer je tudi dokaz drugega dela zaključen. Iz dveh grup G1 in G2 lahko napravimo novo grupo. To storimo najlažje kar tako, da ju zložimo v direktni produkt grup G1×G2. Spomnimo se, da je kot množica to običajen kartezični produkt množic G1 in G2, grupna opera- cija pa je definirana po komponentah, se pravi (g1, h1)(g2, h2) = (g1g2, h1h2) za gi ∈ G1, hi ∈ G2. Preverimo, da je verjetnost komutiranja v tem smislu multiplikativna. Trditev 6. Za končni grupi G1 in G2 velja vk(G1×G2) = vk(G1) ·vk(G2). Dokaz. Res, najprej zapǐsimo vk(G1 ×G2) = ∑ x∈G1×G2 |CG1×G2(x)| |G1 ×G2|2 = ∑ a∈G1 ∑ b∈G2 |CG1×G2((a, b))| |G1 ×G2|2 . Ker v kartezičnem produktu G1 × G2 množimo po komponentah, lahko centralizator izrazimo kot CG1×G2((a, b)) = CG1(a) × CG2(b) ≤ G1 × G2. Sledi vk(G1 ×G2) = ∑ a∈G1 ∑ b∈G2 |CG1(a)||CG2(b)| |G1|2|G2|2 . Zadnjo vsoto prepoznamo kot produkt∑ a∈G1 |CG1(a)| |G1|2 · ∑ b∈G2 |CG2(b)| |G2|2 = vk(G1) · vk(G2) in dokaz je zaključen. Z zabeleženima trditvama nam že uspe utemeljiti, da je v dovolj velikih simetričnih grupah komutirajočih parov zanemarljivo malo. Posledica 7. Velja limn→∞vk(Sn) = 0. Dokaz. Simetrična grupa nižje stopnje se naravno vloži v simetrično grupo vǐsje stopnje, zato je po trditvi 5 zaporedje verjetnosti komutiranja sime- tričnih grup (vk(Sn)) ∞ n=1 padajoče. Pokažimo, da konvergira proti 0. V ta 126 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 127 — #7 i i i i i i Verjetnost komutiranja namen za vsako naravno število k opazujmo grupo Gk = S3× · · ·×S3, ki je produkt k kopij simetrične grupe S3. Po trditvi 6 velja vk(Gk) = ( 1 2 )k . Po Cayleyjevem izreku lahko vsako končno grupo vložimo v dovolj ve- liko simetrično grupo. Torej za vsak k obstaja n, da velja Gk ≤ Sn, in zato za vsak m ≥ n velja vk(Sm) ≤ vk(Sn) ≤ vk(Gk) = ( 1 2 )k . Tako je limn→∞vk(Sn) = 0. Verjetnost komutiranja simetričnih grup vk(Sn) je mogoče izračunati eksplicitno in tako podati tudi asimptotično obnašanje tega zaporedja, ko gre n proti neskončno. Ta in splošneǰsi opis za vse končne grupe sta na- šla že Erdös in Turán, gre pa takole. Elementa x, y abstraktne grupe G sta konjugirana, če obstaja tak g ∈ G, da velja x = g−1yg. Lahko je preveriti, da je relacija konjugiranosti ekvivalenčna relacija na množici G. Ekvivalenčni razred elementa x je enak xG = { g−1xg : g ∈ G } , imenujemo ga razred konjugiranosti. Grupa G tako razpade na disjunktno unijo ra- zredov konjugiranosti. Število teh razredov označimo s k(G). Za elementa g, h ∈ G velja g−1xg = h−1xh, če in samo če je (gh−1)−1x(gh−1) = x. Sle- dnje je enako kot gh−1 ∈ CG(x), kar preberemo kot enakost desnih odsekov CG(x)g = CG(x)h. Na ta način se vzpostavi bijekcija g −1xg 7→ CG(x)g med elementi razreda xG in odseki grupe G po podgrupi CG(x). V posebnem drži enakost |G : CG(x)| = |xG|. Na vsem povedanem temelji naslednji izrek, ki razkrije povezavo med verjetnostjo komutiranja in k(G). Izrek 8 ([3] – Erdös in Turán 1968). Naj bo G končna grupa. Tedaj je vk(G) = k(G) |G| . Dokaz. Kot običajno razpǐsemo vk(G) = ∑ x∈G |CG(x)| |G|2 . Velikost centralizatorja s pomočjo enakosti |G : CG(x)| = |xG| zamenjamo z velikostjo razreda konjugiranosti in dobimo vk(G) = ∑ x∈G 1 |xG| |G| . Vsoto v števcu razdelimo po razredih konjugiranosti in iz vsakega izberimo predstavnika xi za 1 ≤ i ≤ k(G). Razredi konjugiranosti xGi so med sabo 121–137 127 i i “Jezernik” — 2019/1/11 — 7:37 — page 128 — #8 i i i i i i Urban Jezernik disjunktni in pokrijejo ves G, za vsak element x ∈ xGi pa velja xG = xGi . Sledi vk(G) = ∑k(G) i=1 |xGi | 1 |xGi | |G| = k(G) |G| in dokaz je zaključen. Število razredov konjugiranosti dane grupe lahko izračunamo hitreje kot število vseh komutirajočih parov. Premislimo, kakšni so razredi konjugira- nosti v primeru simetrične grupe Sn. Naj bo σ izbrana permutacija. Če zanjo velja σ(i) = j, potem za konjugirano permutacijo α−1σα ob poljubni α ∈ Sn velja (α−1σα)(α−1(i)) = (α−1σ)(i) = α−1(j). Konjugirani element α−1σα torej preslika α−1(i) v α−1(j) in tako permu- tira na enak način kot σ, le da je treba vsako od števil 1 ≤ i ≤ n zamenjati z α−1(i). Ko α preteče vse elemente grupe Sn, v razredu za konjugiranost σSn najdemo ravno vse permutacije z enako ciklično strukturo kot σ. Število razredov konjugiranosti v Sn je zato enako številu vseh možnih razčlenitev naravnega števila n. Elementarna eksplicitna formula za to število ne ob- staja, že dolgo pa je poznana njena dobra asimptotska ocena [7]. Z njo velja vk(Sn) ∼ exp ( π √ 2n 3 ) 4n √ 3 · n! , zato je logaritem log (vk(Sn)) po Stirlingovi aproksimaciji proporcionalen −n log n za velike vrednosti n. Število k(G) je povezano z mnogimi drugimi aspekti teorije grup, tudi bržkone naslavneǰsim – teorijo upodobitev. Brez strahu se lahko s tem dej- stvom okoristimo! Teorija upodobitev je del matematične folklore, potrebno znanje pa lahko osvežimo že z zapiski [11]. Opazovano grupo G s homomorfizmom ρ : G → GL(V ) upodobimo na končnorazsežnem kompleksnem vektorskem prostoru V . Kadar je dimV = n, grupo GL(V ) enačimo z GLn(C). Kadar lahko vektorski prostor V zapi- šemo kot direktno vsoto V = U ⊕W , pri čemer grupa G preko preslikave ρ deluje na vsaki komponenti te vsote posebej, rečemo, da je upodobitev raz- cepna. V nasprotnem imamo opravka z nerazcepno upodobitvijo. Prav tako kot cepimo naravna števila na prafaktorje, lahko upodobitev ρ razcepimo na nerazcepne upodobitve. Število vseh različnih nerazcepnih upodobitev (do izomorfizma natančno) grupe G je ravno k(G) [11, posledica 1.2.5]. Vse 128 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 129 — #9 i i i i i i Verjetnost komutiranja najdemo v univerzalnem primeru upodobitve; to je regularna upodobitev, pri kateri elemente grupe G upodobimo kot leva množenja na grupni alge- bri CG. Fineǰsi pogled na slednjo upodobitev poda naslednji izrek, ki ga najdemo v [11, izrek 1.2.3]. Izrek 9 (Wedderburn). Naj bo G končna grupa. Tedaj je njena regularna upodobitev izomorfna direktni vsoti CG ∼= k(G)⊕ i=1 Vi ⊕ · · · ⊕ Vi︸ ︷︷ ︸ dimVi , kjer so V1, V2, . . . , Vk(G) ravno vse različne nerazcepne upodobitve (do izo- morfizma natančno) grupe G. V posebnem sta kompleksni dimenziji leve in desne strani enaki, zato velja |G| = k(G)∑ i=1 (dimVi) 2 . (1) Primer 10. Opazujmo kvaternionsko grupo Q8 = {±1,±i,±j,±k}. Spo- mnimo se, da v njej množimo z zakoni i2 = j2 = k2 = −1 in ij = k, jk = i, ki = j. Da grupo Q8 upodobimo na enorazsežnem kompleksnem prostoru, je treba podati homomorfizem χ : Q8 → C×. Ta je natanko določen s sliko generatorjev i in j. Za vsakega od njiju smemo izbrati enega od dveh kom- pleksnih korenov števila −1. Enostavno je preveriti, da vsaka taka izbira porodi homomorfizem χ. Skupaj imamo torej štiri enorazsežne upodobitve grupe Q8. Po Wedderburnovem izreku velja 8 = 1 2 + 12 + 12 + 12 + ∑ i d 2 i , kjer so di stopnje vǐsjerazsežnih nerazcepnih upodobitev. Edina možnost je, da obstaja natanko ena taka upodobitev stopnje 2. Tako velja k(Q8) = 5 in zato vk(Q8) = 5 8 . Na splošno je število enorazsežnih upodobitev dane grupeG ravno število odsekov po njeni izpeljani podgrupi G′ = 〈 { x−1y−1xy : x, y ∈ G } 〉. Dokaz tega dejstva najdemo v [11, izrek 2.8.4]. Wedderburnovo formulo (1) zato lahko zapǐsemo kot |G| = ∣∣G : G′∣∣+∑ i d2i , kjer so di stopnje vǐsjerazsežnih nerazcepnih upodobitev grupe G. Od tod je mogoče izpeljati zgornjo mejo za verjetnost komutiranja poljubne grupe. 121–137 129 i i “Jezernik” — 2019/1/11 — 7:37 — page 130 — #10 i i i i i i Urban Jezernik Trditev 11 ([14] – Rusin 1979). Naj bo G končna grupa. Tedaj velja vk(G) ≤ 1 4 ( 1 + 3 |G′| ) . Dokaz. V Wedderburnovi formuli upoštevajmo di ≥ 2, pa velja |G| = |G : G′|+ k(G)∑ i=|G:G′|+1 d2i ≥ |G : G′|+ (k(G)− ∣∣G : G′∣∣) · 4. Neenakost delimo z |G|, izrazimo vk(G) = k(G)/|G| in trditev sledi. O zavzetih vrednostih Množico zavzetih verjetnosti komutiranja vseh končnih grup označimo z V. S strukturnimi rezultati iz preǰsnjega razdelka lahko dokažemo dve zanimivi lastnosti množice V. Najprej se prepričajmo, da V ni diskretna podmnožica intervala [0, 1]. Posledica 12. Velja limn→∞vk(Dn) = 1 4 . Dokaz. Naj bosta ρ in τ rotacija in zrcaljenje v Dn. Velja ρ −1τ−1ρτ = ρ−2. Izpeljana podgrupa D′n torej vsebuje kvadrate vseh rotacij. Teh je vsaj n2 in tako gre |D ′ n| proti neskončno, ko gre n proti neskončno. Že iz uvodnega razdelka vemo, da je vk(Dn) > 1 4 , zato iz trditve 11 sledi limn→∞vk(Dn) = 1 4 . Vrednost 14 je torej limitna točka množice V. Hkrati je po trditvi 6 verjetnost komutiranja grupe S3×S3 ravno 14 , torej je limitna vrednost tudi zavzeta in množica V ni diskretna. Iz strukturnih ocen izpeljimo še drugo lastnost, in sicer obstoj intervalov nezavzetih vrednosti. Posledica 13 ([6] – Gustafson 1973). Interval (58 , 1) ne vsebuje verje- tnosti komutiranja nobene končne grupe. Dokaz. Naj bo G končna grupa z vk(G) > 58 . Iz predpostavke in trditve 11 sledi neenakost 5 8 < vk(G) ≤ 1 4 ( 1 + 3 |G′| ) , ki se poenostavi do |G′| < 2. Sledi G′ = 1, torej je G komutativna in zato vk(G) = 1. 130 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 131 — #11 i i i i i i Verjetnost komutiranja Oglejmo si verjetnosti komutiranja grup moči največ 256 še enkrat, to- krat bolj podrobno. Omejimo se na verjetnosti z intervala [0,1, 0,3]. Slika 2 prikazuje zalogo vrednosti funkcije verjetnosti komutiranja, zožene na mno- žico grup moči kvečjemu 256. Vemo že, da se verjetnosti komutiranja diedr- skih grup z zgornje strani stekajo k vrednosti 14 , na sliki je razločen začetek te konvergence. Tik pod limitno točko 14 je moč zaznati verjetnostno luknjo. Opazimo tudi, da je limitnih točk množice V najbrž več. Zanimivo bi jih bilo opisati. 0.10 0.15 0.20 0.25 0.30 Slika 2. Zavzete verjetnosti komutiranja grup moči kvečjemu 256. O teh in splošneǰsih lastnostih množice zavzetih verjetnosti komutiranja je razmǐsljal že Joseph in postavil naslednje domneve. Domneva 14 ([9] – Joseph 1977). Množica V ima naslednje lastnosti: 1. Limitne točke množice V so racionalne. 2. K limitnim točkam množice V se zavzete verjetnosti komutiranja lahko stekajo le z zgornje strani. 3. Množica V ∪ {0} je zaprta. Po prvi domnevi naj bi okoli vsakega iracionalnega števila na intervalu [0, 1] našli okolico, ki ne seka množice V. Tretja domneva pravi, da za vsako zaporedje vn ∈ V s pozitivno limito limn→∞vn = v obstaja končna grupa z verjetnostjo komutiranja v. Nazadnje druga domneva trdi, da za vsako limitno točko v obstaja δ > 0, da velja (v − δ, v) ∩ V = ∅. Slednje pomeni, da je množica V dobro urejena glede na relacijo >. Delno razrešitev Josephovih domnev najdemo v nedavno objavljenem članku [2]. Avtor prikaže presenetljivo in čudovito povezavo med verjetno- stjo komutiranja in egipčansko kompleksnostjo racionalnih števil. Vsako racionalno število q > 0 lahko zapǐsemo kot vsoto q = 1/n1 + · · ·+ 1/nm za neka naravna števila ni in m. To lahko storimo na več načinov, na primer 5 6 = 1 6 + 1 6 + 1 6 + 1 6 + 1 6 = 1 2 + 1 3 . Najmanǰse število uporabljenih sumandov m, za katerega obstaja tak zapis, je (egipčanska) kompleksnost E(q) šte- vila q. Eberhard dokaže, da so verjetnosti komutiranja končnih grup tesno povezane z ulomki omejene kompleksnosti. 121–137 131 i i “Jezernik” — 2019/1/11 — 7:37 — page 132 — #12 i i i i i i Urban Jezernik Izrek 15 ([2] – Eberhard 2015). Za vsako padajočo funkcijo η : N→ (0, 1) obstaja konstanta M = M(η) ∈ N, tako da je verjetnost komu- tiranja poljubne končne grupe oblike q + , kjer je E(q) ≤ M in 0 ≤  ≤ η(E(q)). Od tod lahko hitro izpeljemo veljavnost prvih dveh zgornjih domnev. Dokaz prvih dveh Josephovih domnev. Naj bo v > 0 limitna točka množice V. Številu v se približajmo kar se da dobro z ulomki omejene kompleksnosti; naj bo Q(m) = sup {q < v : E(q) ≤ m} za vsako naravno število m. Definirajmo funkcijo η : N→ (0, 1) s predpisom η(m) = (v − Q(m))/2. Po izreku obstaja konstanta M , da vsako vrednost p ∈ V lahko zapǐsemo kot p = q + , kjer je E(q) ≤ M in 0 ≤  ≤ η(E(q)). Če slučajno drži še neenakost q < v, sledi q ≤ Q(E(q)) in zato velja najprej neenakost  ≤ η(E(q)) = v −Q(E(q)) 2 ≤ v − q 2 , s tem pa še p = q +  ≤ v + q 2 ≤ v +Q(M) 2 = v − η(M). V tem primeru je torej število p oddaljeno vsaj η(M) od števila v. Vzemimo zaporedje vn = qn+ n ∈ V z limito v. Iz zgornjega premisleka sledi, da lahko le za končno mnogo indeksov velja qn < v. S tem je dokazana druga domneva. Ker je zato vn ≥ qn ≥ v za skoraj vse indekse, tudi zaporedje qn konvergira k v. Množica vseh ulomkov kompleksnosti največ M je zaprta (ko ji dodamo 0), saj jo lahko predstavimo kot sliko zvezne preslikave ({ 1 n : n ∈ N } ∪ {0} )M → [0,M ], ki sešteje M -terico števil na levi. Od tod sledi E(v) ≤ M . Tako je v racionalno število in tudi prva domneva je dokazana. Tretja Josephova domneva je še vedno odprta. 132 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 133 — #13 i i i i i i Verjetnost komutiranja O neskončnih grupah Pojem verjetnosti komutiranja ima smisel za poljubne grupe, opremljene z verjetnostno mero. V posebnem to naravno velja za kompaktne (Hau- sdorffove) topološke grupe. Ponovimo, da je topološka grupa G množica, ki je hkrati opremljena s strukturo grupe in topološkega prostora, oboje pa je uglašeno z zahtevo, da sta množenje in invertiranje v G zvezni presli- kavi. Vsaka kompaktna topološka grupa G je naravno opremljena s Haa- rovo mero; to je verjetnostna Borelova mera µ, za katero med drugim velja µ(x · E) = µ(E) pri vsakem x ∈ G in Borelovi množici E ⊆ G. Bralec lahko več o Haarovi meri prebere v [8, razdelek I.2]. Primer 16. Opazujmo končno grupo G, opremljeno z diskretno topologijo. Njena Haarova mera µ sovpada z normalizirano mero štetja točk. Torej za podmnožico A ⊆ G velja µ(A) = |A|/|G|. Primer 17. Opazujmo multiplikativno grupo S1 kompleksnih števil abso- lutne vrednosti 1. Tukaj je Haarova mera merljive množice A ⊆ S1 enaka vrednosti λ({t ∈ [0, 1] : e2πit ∈ A}), kjer je λ običajna Lebesgueova mera na intervalu [0, 1]. Pare elementov iz grupe G slučajno izbiramo iz produktnega prostora G×G, opremljenega z verjetnostno produktno mero µ×µ. Komutiranje v G izrazimo z zvezno preslikavo k : G×G→ G , k(x, y) = x−1y−1xy . Komuti- rajoči pari so natanko množica k−1({1}). Verjetnost komutiranja v grupi G je tako enaka vk(G) = (µ× µ)(k−1({1})) = ∫ k−1({1}) d(µ× µ). Ni se težko prepričati, da tudi za kompaktne grupe velja izrek o verje- tnostni luknji. Tokrat predstavimo elementarneǰsi dokaz, ki se izogne teoriji upodobitev. Trditev 18 ([6] – Gustafson 1973). Interval (58 , 1) ne vsebuje verjetno- sti komutiranja nobene kompaktne grupe. Dokaz. Verjetnost komutiranja kompaktne grupe G izrazimo kot∫ k−1({1}) d(µ× µ) = ∫ G ∫ CG(x) dµ(y)dµ(x) = ∫ G µ(CG(x)) dµ(x), 121–137 133 i i “Jezernik” — 2019/1/11 — 7:37 — page 134 — #14 i i i i i i Urban Jezernik kjer prva enakost sledi po Fubinijevem izreku. Razdelimo verjetnost komu- tiranja na dva dela, vk(G) = ∫ Z(G) µ(CG(x)) dµ(x) + ∫ G−Z(G) µ(CG(x)) dµ(x). Predpostavimo, da G ni komutativna. Tedaj kvocientna grupa G/Z(G) grupe G po svojem centru ni ciklična, zato je |G : Z(G)| ≥ 4. Ker je G disjunktna unija odsekov po centru, sledi µ(Z(G)) ≤ 14 . Za tiste elemente x ∈ G, ki ne pripadajo centru, velja neenakost |G : CG(x)| ≥ 2 in zato µ(CG(x)) ≤ 12 . Zdaj velja vk(G) ≤ µ(Z(G)) · 1 + µ(G− Z(G)) · 1 2 ≤ µ(Z(G)) 2 + 1 2 ≤ 5 8 , s čimer je dokaz zaključen. Nekoliko bolj izvirna definicija verjetnosti komutiranja je potrebna za ne- skončne grupe, ki same po sebi niso opremljene z verjetnostno mero. Avtorji [1] k temu problemu pristopijo s stalǐsča geometrijske teorije grup. Vsaki končno generirani grupi G, generirani s simetrično množico X = X−1, lahko priredimo njen Cayleyjev graf Cay(G,X). Vozlǐsča tega grafa so elementi grupe G, med elementoma x, y ∈ G pa obstaja povezava, če in samo če je x−1y ∈ X. Primer 19. Naj bo F prosta grupa na dveh generatorjih a, b. Njeni ele- menti so okraǰsane besede s črkami iz množice X = {a, a−1, b, b−1}. Cay- leyjev graf Cay(F,X) dobimo tako, da vsako besedo povežemo z njenim nadaljevanjem z vsako od črk iz množice X. Ta graf je neskončen in je delno prikazan na sliki 3. V sredǐsču je enota 1 grupe F . Ko jo podalj- šamo z vsakim elementom množice X, dobimo njene sosede a, a−1, b, b−1. Vsakega od teh lahko zopet podalǰsamo. Pri tem upoštevamo še kraǰsanje besed, na primer aa−1 = 1. Če se torej v grafu sprehodimo od enote 1 v smeri »desno-gor-levo«, prispemo do elementa aba−1. Cayleyjev graf lahko opremimo z naravno metriko: za razdaljo dX(x, y) med vozlǐsčema x in y razglasimo število povezav na najkraǰsi poti med x in y. Namesto algebraičnega objekta G tako lahko opazujemo metrični prostor Cay(G,X). Verjetnost komutiranja lahko izmerimo v vsakem končnem kosu tega metričnega prostora, cel prostor pa lahko izčrpamo s končnimi množicami, najbolj naravno kar s kroglami okoli enote 134 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 135 — #15 i i i i i i Verjetnost komutiranja a−→ a−→ a−→ ↑b ↑b ↑b ↑b a−→ a−→ ↑b ↑b a−→a−→ ↑b ↑b ↑b a−→ a−→ a−→a−→ ↑b ↑b a−→ a−→ ↑b ↑b ↑b ↑b ↑b a−→a−→ a−→ a−→ ↑b ↑b a−→a−→ ↑b ↑b a−→a−→a−→ ↑b ↑b ↑b ↑b a−→a−→ ↑b ↑b a−→ a−→ Slika 3. Del Cayleyjevega grafa proste grupe z generatorjema a, b. BX(n) = {x ∈ G : dX(x, 1) ≤ n}. V tem jeziku slika 3 prikazuje kroglo BX(3) Cayleyjevega grafa proste grupe. Stopnja komutiranja (v tej splo- šnosti ne moremo govoriti več o verjetnosti) v grupi G je sk(G,X) = lim sup n→∞ |{(x, y) ∈ BX(n)× BX(n) : xy = yx}| |BX(n)|2 . Antoĺın, Martino in Ventura dokažejo, da za grupeG polinomske besedne rasti (to pomeni, da velikosti krogel BX(n) rastejo kvečjemu polinomsko z n) v zgornji definiciji obstaja celo limita ter da je ta neodvisna od izbire končne generirajoče množice X. Poleg tega avtorji premislijo, da je v takih grupah stopnja komutiranja pozitivna le v izjemnih primerih. Trditev 20 ([1] – Antoĺın, Martino in Ventura 2017). Naj bo G gru- pa, generirana s končno množico X. Predpostavimo, da je G polinomske rasti. Tedaj je sk(G,X) > 0 natanko tedaj, ko ima G komutativno podgrupo končnega indeksa. Predpostavka o polinomski rasti je precej omejujoča. Grupe s to lastno- stjo so natanko grupe, ki imajo nilpotentno podgrupo končnega indeksa [4]. Ko nasprotno opazujemo grupe s hitro, eksponentno rastjo, so te daleč stran 121–137 135 i i “Jezernik” — 2019/1/11 — 7:37 — page 136 — #16 i i i i i i Urban Jezernik od komutativnih in avtorji pričakujejo, da je njihova stopnja komutiranja ničelna. To domnevo znajo potrditi za precej širok razred grup s takšno rastjo, in sicer hiperbolične grupe [5]. To so grupe, katerih Cayleyjev graf je videti kot hiperbolični prostor v naslednjem smislu: obstaja δ > 0, pri katerem je vsak trikotnik v Cay(G,X) δ-ozek. Tukaj s pojmom trikotnik mislimo izbiro treh točk v grafu in geodetskih poti med njimi, izraz δ-ozek pa pomeni, da je vsaka točka na kateremkoli robu trikotnika oddaljena za največ δ od vsaj ene točke na uniji drugih dveh robov trikotnika. V takem metričnem prostoru so torej trikotniki negativno ukrivljeni, podobno kot v hiperboličnem prostoru. Primer 21. Proste grupe so hiperbolične. Kot smo videli v primeru 19, so njihovi Cayleyjevi grafi neskončna drevesa in trikotniki v njih so zelo ozki. Primer 22. Lep primer hiperbolične grupe je modularna grupa transfor- macij hiperbolične ravnine {z ∈ C : Im(z) > 0}. Ta sestoji iz preslikav oblike z 7→ az + b cz + d , kjer so a, b, c, d cela števila, za katera velja ad−bc = 1. Opremljena je z ope- racijo komponiranja preslikav. Ni težko preveriti, da preslikavi S : z 7→ −1/z in T : z 7→ z + 1 generirata to grupo. Preslikava S je kompozicija inverzije preko enotske krožnice in zrcaljenja preko imaginarne osi, preslikava T pa enotska translacija. Generatorja zadoščata relacijama S2 = (ST )3 = 1. S tema dvema relacijama je modularna grupa enolično določena in jo v tem smislu lahko podamo kot končno prezentirano grupo 〈S, T | S2, (ST )3〉. Ko postavimo X = {S, S−1, ST, (ST )−1}, si lahko Cayleyjev graf te grupe glede na X predstavljamo sorodno kot graf na sliki 3, le da moramo v slednjem mnogo vozlǐsč identificirati. V Cayleyjevem grafu modularne grupe obsta- jajo dvocikli zaradi enakosti S2 = 1 in tricikli zaradi enakosti (ST )3 = 1. Ko prosti grupi dodajamo naključne dolge relacije, skoraj vedno dobimo hiperbolično grupo. Izrek 23 ([5] – Gromov 1987, [12] – Ol’shanskĭı 1992). Ob danih naravnih številih n ≥ 2 in k ≥ 1 enakomerno in neodvisno iz proste grupe z n generatorji a1, a2, . . . , an izberimo besede r1, r2, . . . , rk doľzine največ `. Naj bo G = 〈a1, . . . , an | r1, . . . , rk〉 kvocient proste grupe po teh relacijah. Tedaj verjetnost, da je G hiperbolična grupa, konvergira proti 1, ko gre ` proti neskončno. 136 Obzornik mat. fiz. 65 (2018) 4 i i “Jezernik” — 2019/1/11 — 7:37 — page 137 — #17 i i i i i i Verjetnost komutiranja Vsako končno generirano grupo lahko predstavimo kot kvocient proste grupe. Kadar za to potrebujemo le končno mnogo relacij, je torej grupa v smislu izreka 23 skoraj zagotovo hiperbolična. Če izključimo tiste, ki vsebujejo ciklično podgrupo končnega indeksa, zanje velja naslednji rezultat. Trditev 24 ([1] – Antoĺın, Martino in Ventura 2017). Naj bo G hi- perbolična grupa, generirana s končno množico X. Predpostavimo, da G ne vsebuje ciklične podgrupe končnega indeksa. Tedaj je sk(G,X) = 0. Nazadnje imajo torej skoraj vse (končno prezentirane) grupe ničelno stopnjo komutiranja. Temu primerno naš izlet po verjetnosti komutiranja končajmo z enim Šalamunom – nič nič nič nič fiuuuuu še ena gobica LITERATURA [1] Y. Antoĺın, A. Martino in E. Ventura, Degree of commutativity of infinite groups, Proc. Am. Math. Soc. 145 (2017), 479–485. [2] S. Eberhard, Commuting probabilities of finite groups, Bull. Lond. Math. Soc. 47 (2015), 796–808. [3] P. Erdös in P. Turán, On some problems of a statistical group-theory. IV, Acta Math. Acad. Sci. Hungar 19 (1968), 413–435. [4] M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53–73. [5] M. Gromov, Hyperbolic groups, Essays in group theory 8 (1987), 75–263. [6] W. H. Gustafson, What is the probability that two group elements commute?, Amer. Math. Monthly 80 (1973), 1031–1034. [7] G. H. Hardy in S. Ramanujan, Asymptotic formulae in combinatory analysis, Proc. Lond. Math. Soc. 2 (1918), 75–115. [8] M. Hladnik, Uvod v harmonično analizo na lokalno kompaktnih grupah, zapiski pre- davanj, Ljubljana, 2006, dostopno na www.fmf.uni-lj.si/~hladnik/3st/HA.pdf, ogled 21. 12. 2018. [9] K. Joseph, Several conjectures on commutativity in algebraic structures, Amer. Math. Monthly 84 (1977), 550–551. [10] D. MacHale, Commutativity in finite rings, Amer. Math. Monthly 83 (1976), 30–32. [11] P. Moravec, Osnove upodobitev končnih grup, Samozal., Ljubljana, 2018, dostopno na www.fmf.uni-lj.si/~moravec/Papers/upodob_moravec.pdf, ogled 21. 12. 2018. [12] A. Yu. Ol’shanskĭı, Almost every group is hyperbolic, Internat. J. Algebra Comput. 2 (1992), 1–17. [13] V. Ponomarenko in N. Selinski, Two semigroup elements can commute with any positive rational probability, College Math. J. 43 (2012), 334–336. [14] D. J. Rusin, What is the probability that two elements of a finite group commute?, Pacific J. Math. 82 (1979), 237–247. 121–137 137