Cykliske grupper

[06.04.2020] [Nørderier/Teori]

Lad G være en gruppe, og lad x ∈ G. En måde at danne en undergruppe H af G er ved at lade H være alle positive og negative potenser af x. Dette sikrer at H er aflsuttet overfor inversdannelse og multiplikation hvad x angår.

Definition
- En delmængde S af en gruppe G siges at frembringe G hvis ethvert element i G kan skrives som et produkt af elementer og deres inverse i S. Dette noteres som G = .langle S .rangle.
- Enhver ligning i G som tilfredsstiller S kaldes en relation i S. Disse noteres som R_1, R_2, ..., R_m.
- Generelt: hvis G frembringes af S, og hvis der er en samling relationer så enhver ligning i S kan laves af disse, kalder vi disse frembringere og relationer for en repræsentation af G og skriver:

G = .langle S .divides R_1, R_2, ..., R_m .rangle

Eksempler:

Gruppen G = (setZ, +) frembringes af elementet {1}. Dette indser vi ved at starte med 0 og plusse/minusse med 1. Vi skriver setZ = .langle 1 .rangle.
Gruppen G = D_2n frembringes af elementerne {r,s}. Derudover er der de specielle relationer i G: r^n = s^2 = 1, rs = sr^{-1}, og vi kan nu skrive en repræsentation af G:
D_2n = .langle r,s .divides r^n = s^2 = 1, rs = sr^{-1} .rangle
Hele G kan altså skrives som produkter af {r,s} med de to relationer in mente.

Definition En gruppe, H, er cyklisk hvis G kan frembringes af et enkelt element, altså:

.exist x .isin H : H = {x^n | n .isin setZ}

En cyklisk gruppe kan have mere end en frembringer, feks. den inverse til frembringeren. Derudover er en cyklisk gruppe abelsk da produktet af to forskellige potenser af samme element kommuterer.

Eksempler:

Lad G = D_2n = .langle r,s .divides r^n = s^2 = 1, rs = sr^{-1} .rangle og lad H være alle rotationer i G. Nu er H = .langle r .rangle = {1, r, r^2, ..., r^{n - 1}}. Derudover er |H| = |r| = n.
Bemærk at da:
**matfelt**r^i = 1r^i = r^{n}r^i = r^{n + i} = r^{-n + i}, .forall i .isin [1,n-1]**//**
er en given potens, hverken negativ eller positiv, af r ikke entydig udover i det angivet interval.
Da D_2n ikke er abelsk, er gruppen heller ikke cyklisk.
Lad H = (setZ, +). Da er H = .langle 1 .rangle = .langle -1 .rangle da etvhert element i H kan skrives unikt som n ⋅ 1. Her er hver potens entydig, og vi skal dermed bruge både negative-, positive- og nul gange af generatoren for at frembringe H.

Prop. 2 Hvis H = .langle x .rangle da er |H| = |x| hvor tilfældet ∞ = ∞. Udspecificeret:

Hvis |H| = |x| .lt %infin, er x^n = 1, og 1,x,x^2, ... ,x^{n - 1} er alle entydige elementer i H.
Hvis |H| = %infin, er x^n .ne 0, .forall n .ne 0 og x^a .ne x^b, .forall b .ne a

Bevis:
(1) : Første del har vi haft før, men vi tager det en ekstra gang for de nyankomne:
- Lad G være en endelig cyklisk gruppe af orden n.
- Lad 0 .le i .lt j .lt n, og lad x ∈ G være frembringer for G hvilket betyder at n er den mindste potens i hvilken x = 1.
- Lad x^i = x^j, i .ne j.
Vi får nu x^{j}x^{-i} = 1 .drarrow x^{j - i} = 1 hvilket er en modstrid da 0 < j - i < n, og da n er den mindste potens i hvilken x er 1. Beviset i tilfældet j < i forløber på samme måde.
Vi mangler så at vise at der er n elementer i H. Dette viser vi ved at benytte divisionsalgoritmen. Lad x^t være en hvilken som helst potens af x, skriv t = nq + k, og vi får:

x^t = x^{nq + k} = (x^n)^{q}x^k = 1^{q}x^k = x^k .isin {1, x, x^2,...,x^{n - 1}}

(2) : Lad |x| = ∞. Da er den eneste potens af x der giver 1, 0. Lad så x^a = x^b, 0 .le a .lt b, og vi får at x^{b}x^{-a} = 1 .drarrow x^{b - a} = 1. Men da b - a > 0, fører dette til en modstrid. Derudover, da forskellige potenser af x er forskellige elementer i H, er |H| = ∞.

Prop. 3 Lad G være en gruppe, lad x være et element i G, og lad m, n .isin setZ. Vi får nu:

x^m = 1 .and x^n = 1 .drarrow x^d = 1, d = (m,n)

Specielt gælder x^m = 1 .drarrow |x| .divides m, m .isin setZ

Bevis: ifølge Euklids algoritme eksisterer heltallene r og s så d = mr + ns hvor d er den største fælles divisor af m og n. Vi får nu:

x^d = x^{mr + ns} = (x^{m})^{r}(x^{n})^{s} = 1^{r}1^{s} = 1

hvilket viser første del af prop.3. For anden del lad x^m = 1, |x| = n. Hvis m = 0, gælder n | m i det hele taget. Så lad 0 < m. Ifølge ovenstående kan vi nu finde x^d = 1, d = (n,m). Men da n er den mindste potens i hvilken x er 1, må d = n.

Sætning 4 : To cykliske grupper af samme orden er isomorfe. Altså:

Hvis n .isin setZ og og ⟨ y ⟩ begge er cykliske grupper af orden n, er
%phi : .langle x .rangle .functo .langle y .rangle %phi(x^k) = y^k
en veldefineret isomorfi.
Hvis ⟨ x ⟩ er en uendelig cyklisk gruppe, er
%phi : setZ .functo .langle x .rangle %phi(k) = x^k
en veldefineret isomorfi.

Beviser:
(1) : Lad ⟨ x ⟩ og ⟨ y ⟩ være cykliske grupper af orden n. Lad %phi : .langle x .rangle .functo .langle y .rangle være givet ved %phi(x^k) = y^k. Vi skal først og fremmest vise at φ er veldefineret, altså at:

x^r = x^s .drarrow %phi(x^r) = %phi(x^s)

Da x^{r}x^{-s} = 1, får vi ifølge prop.3 at n|(r - s) hvilket betyder at nk = r - s .drarrow nk + s = r hvilket giver:

%phi(x^r) = y^r = %phi(x^{nk + s}) = %phi((x^n)^{k}x^s) = %phi(1^{k}x^s) = %phi(x^s) = y^s

og φ er veldefineret. Herfra følger at %phi(x^{a}x^b) = %phi(x^a)%phi(x^b), så φ er en homomorfi. Siden %phi(x^k) = y^k, x^k .isin .langle x .rangle, y^k .isin .langle y .rangle hvor begge potenser er entydige, er φ surjektiv. Siden begge grupper har samme orden, er φ surjektiv hvis og kun hvis den er bijektiv. Dermed er φ en isomorfi.

(2) : Hvis .langle x .rangle er en uendelig cyklisk gruppe, kan vi lade %phi : setZ .functo .langle x .rangle være givet ved %phi(k) = x^k. Da alle elementer i både def. mængden og billedmængen er distinkte, er φ veldefineret. Dette medfører også at φ er injektiv og dermed surjektiv (def. af cykliske grupper). Som ovenfor er φ en homomorfi og dermed en isomorfi.

Prop. 5 Lad G være en gruppe, og lad x .isin G, a .isin setZ .setminus {0}

|x| = %infin .drarrow |x^a| = %infin
|x| = n .lt %infin .drarrow |x^a| = {n}over{(n,a)}
|x| = n .lt %infin .and a .isin setZ^{+} : a .divides n .drarrow |x^a| = {n}over{a}

Beviser:

(1) : Lad |x| = %infin, |x^a| = m .lt %infin, og vi får:

1 = (x^a)^m = x^am og x^{-am} = (x^am)^{-1} = 1^{-1} = 1

Siden hverken a eller m er 0, er en af enten -am og am positive, og dermed er en eller anden potens af x 1. Men dette modsiger antagelsen |x| = ∞, og vi har opnået en modstrid.

(2) : Lad y = x^a, (n,a) = d som giver n = db, a = dc. Da d er den største fælles divisor i n og a, gælder (b,c) = 1 - de er indbyrdes primiske hvilket indses på følgende måde:

Lemma 1
Lemma til lemma2. Lad a, b .isin setZ .setminus {0}, d = (a,b). Da gælder at:

a = (-d)q_1 .drarrow a = d(-q_1) b = (-d)q_2 .drarrow b = d(-q_2)

Da q blot er et heltal, er d > 0.

Lemma 2
Lad n = db og a = dc. Lad d = (a,n) være den største fælles divisor i a og n, og lad e = (b,c) > 1. Da kan b skrives som ex, og c kan skrive som ey for to heltal x og y større end 0. Men ifølge Prop.1.4 for talteori gælder, at hvis d er den største fælles divisor i a og n, gælder for alle andre fælles divisorer i a og n at de er divisorer i d. Dermed får vi e|d. Skriv nu d = ef, for et eller andet heltal f større end 0, og vi får at n = dex = efex og a = dey = efey. Da e > 1, får vi at efe > ef = d hvilket er i modstrid med at d er den største fælles divisor i a og n.

Vi skal nu vise at |x^a|(n,a) = n, altså at y = b, før (2) gælder. Bemærk først at:

y^b = (x^a)^b = x^{ab} = x^{dcb} = x^{nc} = 1^c = 1

Derfor må der gælde at |y| er divisor i b. Lad k = |y|, og vi får:

x^{ak} = y^k = 1

Prop. 6 Lad H = .langle x .rangle

(|x| = %infin .drarrow H = .langle x^a .rangle) .dlrarrow a = .plusmn 1.
(|x| = n .lt %infin .drarrow H = .langle x^a .rangle) .dlrarrow (a,n) = 1. Specielt er antallet af frembringere i H φ(n) (Eulers φ-funktion).

Beviser:
(1) : Rimeligt konkret: Lad |H| = |x| = ∞. Der gælder ifølge prop.2.2 at x .ne x^p1 .ne x^p2 hvor p1 og p2 er to forskellige primtal større end 1. Den eneste potens af x der kan frembringe begge de to primtalspotenser, er 1 eller -1.
(2) : Ifølge prop.2.1 frembringer x^a en undergruppe af H med orden |x^a|. Denne undergruppe er lig med H hvis og kun hvis |x| = |x^a|. Ifølge prop.5.2 får vi:

|x^a| = |x| .dlrarrow {n}over{(n,a)} = n .dlrarrow (a,n) = 1

Siden nu φ(n) er alle de a ≤ n for hvilke gælder (a,n) = 1, er φ(n) altså antallet af frembringere for H.

Eksempel

Prop.6 fortæller præcist hvilke frembringere en restklasse mod n har. Der gælder nemlig at .langle overline a .rangle = setZ .setminus nsetZ .dlrarrow (n,a) = 1. Feks for n = 8 får vi at
setZ .setminus 8setZ = .langle overline 1 .rangle = .langle overline 3 .rangle = .langle overline 5 .rangle = .langle overline 7 .rangle
(husk at gruppen er additiv) og at φ(8) = 4. Dette giver faktisk god intuitiv mening da feks. alle potenser af lige tal mindre end eller lig med 8, altid vil resultere i et lige tal.

Sætning 7 Lad H = .langle x .rangle være en cyklisk gruppe.

Enhver undergruppe af H er cyklisk. Mere præcist, hvis K ≤ H, er enten K = {1} eller K = .langle x^d .rangle hvor d er det mindste heltal i hvilken potens x er i K.
Hvis |H| = ∞, gælder for hver unik positive heltal a og b at .langle x^a .rangle .ne .langle x^b .rangle. Derudover er .langle x^m .rangle = .langle x^{|m|} .rangle, hvor |m| er den absolutte værdi af m. Dermed korresponderer den den ikke trivielle undergruppe af H bijektivt med heltallene 1, 2, 3, 4, ...
Hvis |H| = n < ∞, er der for hvert positive heltal a der er divisor i n, en unik undergruppe til H af orden a. Denne undergruppe er cyklisk givet ved .langle x^d .rangle hvor d = n/a. Derudover findes der for hvert heltal m en frembragt u.gruppe .langle x^m .rangle = .langle x^{(n,m)} .rangle. Så undergrupper til H korresponderer bijektivt med de positive divisorer i n.

Beviser

(1) : Lad K ≤ H. Hvis K = {1}, er (1) sand for denne undergruppe. Så lad K ≠ {1}. Dermed eksisterer et a ≠ 0 så x^a .isin K. Hvis a er negativ, gælder x^{-a} .isin K da K er en undergruppe. Der er altså altid et x med en positiv potens a i K. Lad nu

P = {b | b .isin setZ^{+} .and x^b .isin K}

Altså de b for hvilke konjunktionen gælder. Ifølge ovenstående er P en ikke-tom mængde af positive heltal. Ifølge talteori prop.1.1 har P et minimumelement, d. Siden K er en undergruppe af H, er ethvert element i K på formen x^a for et heltal a. Vi får nu med divisionsalgoritmen:

a = qd + r, 0 .le r .lt d

Nu er x^r = x^{a - qd} = x^a(x^d)^{-q} et element i K da både x^a, x^d er elementer i K. Da d er minimum, er r = 0, altså er a = qd, og derfor x^a = (x^d)^q .isin .langle x^d .rangle. Dette giver K .le .langle x^d .rangle hvilket beviser (1).

(2) : Lad |H| = ∞, og lad a, b > 0. Da gælder at a .ne b .drarrow x^a .ne x^b ifølge prop.2.2, og dermed at en af følgende to er falske: x^a|x^b eller x^b|x^a (≠ betyder enten > eller < når det nu er tal vi arbejder med). I den divisorrelation der er falsk, kan højre side ikke frembringes af venstre. Derfor gælder at .langle x^a .rangle .ne .langle x^b .rangle.
Lad nu .langle x^m .rangle være en cyklisk gruppe og m et heltal. Da gælder .langle x^m .rangle = .langle x^{-m} .rangle. Vælg nu den positive af m, og vi får at .langle x^m .rangle = .langle x^{|m|} .rangle

(3) : Lad |H| = n < ∞ og a|n. Lad d = n/a hvor prop.5.3 giver at .langle x^d .rangle er en undergruppe af orden |x^d| = (n .slash d) = n .slash (n .slash a) = a hvilket viser eksistensen af denne undergruppe.
Lad nu K være en undergruppe af orden a. Af første del har vi at K = .langle x^b .rangle hvor b er det mindste heltal så x^b .isin K. Af prop.5 får vi:

{n}over{d} = a = |K| = |x^b| = {n}over{(n,b)}

så d = (n,b). Specielt er d divisor i b. Siden b kan skrives som et produkt af d, gælder x^b .isin .langle x^d .rangle, og derfor gælder:

K = .langle x^b .rangle .le .langle x^d .rangle

Siden |.langle x^d .rangle| = a = |K|, får vi at K = .langle x^d .rangle.

Index

Del