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