Tillägg till föreläsning 3 (11/9/01)

Sats 3.1 Låt n, k ≥ 0 vara heltal. Antalet lösningar till

x_{1} + x_{2} + ⋯ + x_{k} = n,  (1)

där de x_{i} är icke-negativa heltal, är ( \begin{matrix}n + k − 1 \\ k − 1 \end{matrix} ).

Bevis : Vi inför symbolerna ·, |, som ska kallas för ‘dot’ och ‘dash’ resp.

Notera att den binomiala koefficienten ( \begin{matrix}n + k − 1 \\ k − 1 \end{matrix} ) är lika med antalet

ord som kan bildas ut av n stycken ‘dots’ och k − 1 stycken ‘dashes’. För varje sådant ord innehåller n + k − 1 symboler totalt, och ordet bestäms unikt av vilka k − 1 av de n + k − 1 positionerna som har en ‘dash’.

Vi skall nu beskriva en 1-1 korrespondens mellan dessa ord och lösningarna till (1). Tag ett godtyckligt ord W alltså, och ansluta därtill k-tuplet (x_{1}, x_{2}, ..., x_{k}), där

x_{1} = antalet ‘dots’ innan den första ‘dash’,
x_{2} = antalet ‘dots’ mellan den första och andra ‘dashes’,
x_{3} = antalet ‘dots’ mellan den andra och tredje ‘dashes’,
⋯
⋯
⋯
x_{k} = antalet ‘dots’ efter den sista ‘dash’.

Eftersom det finns n stycken ‘dots’ totalt i W, då är (x_{1}, ..., x_{k}) en lösning till (1). Det är klart att olika ord ger olika k-tupel, och att varje lösning till (1) anslutas till något ord. Då har vi den efterlängtade 1-1 korrespondensen och beviset är slut.

Sats 3.2 Låt n ≥ 0 vara ett heltal. Då gäller att

( \begin{matrix}2n \\ n \end{matrix} ) = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} )^{2} .  (2)

Bevis : Den VL av (2) är antalet n-element delmängder till {1, ..., 2n}. Låt A beteckna samlingen av alla dessa n-element mängder. Vi skall nu visa hur man får dela upp A i n stycken mindre samlingar, A_{1}, ..., A_{n}, så att

#(A_{k}) = ( \begin{matrix}n \\ k \end{matrix} )^{2} .  (3)

Detta skall räcka till att bevisa (2). Så vad är A_{k} då ?

Ju, först splittra mängden {1, ..., 2n} i två halvar, H_{1} := {1, ..., n} och H_{2} := {n + 1, ..., 2n}. Låt då A_{k} bestå av alla n-element mängder som innehåller k element från H_{1} och n − k från H_{2}. Då är varje mängd X i samlingen A_{k} av formen

X = X_{1} ⊔ X_{2},

där X_{1} är en k-element delmängd till H_{1} och X_{2} är en (n − k)-element

delmängd till H_{2}. Vi har alltså ( \begin{matrix}n \\ k \end{matrix} ) möjligheter för X_{1} och ( \begin{matrix}n \\ n − k \end{matrix} )

möjligheter för X_{2}. Enligt multiplikationprincipen har vi då totalt

( \begin{matrix}n \\ k \end{matrix} ) × ( \begin{matrix}n \\ n − k \end{matrix} ) = ( \begin{matrix}n \\ k \end{matrix} ) × ( \begin{matrix}n \\ k \end{matrix} ) = ( \begin{matrix}n \\ k \end{matrix} )^{2}

möjligheter för X, som bevisar (3) och därmed hela satsen.

Sats 3.3 Låt n ≥ 0 vara ett heltal. Då gäller att

2^{n} = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) .  (4)

Bevis : Koefficienten ( \begin{matrix}n \\ k \end{matrix} ) är antalet k-element delmängder till \{1, ..., n\}.

Om vi summerar över k, från 0 till n, då räknas VARJE delmängd till {1, ..., n} precis en gång. Det kvarstår därför att bevisa att {1, ..., n} har totalt 2^{n} delmängder. Vi gör detta genom att beskriva en 1-1 korrespondens mellan delmängderna och binära ord av längd n. Enligt multiplikationsprincipen, är antalet sådana ord exakt 2^{n}, eftersom vi har två möjligheter (0 eller 1) för varje position, och n positioner totalt.

Tag nu ett ord W. Antag att W har en etta i k stycken positioner, säg positioner x_{1}, ..., x_{k} där 1 ≤ x_{1} < ... < x_{k} ≤ n, och en nolla i de kvarstående positionerna. Anslut då till W, k-element mängden {x_{1}, ..., x_{k}}, som är en delmängd till {1, ..., n}. Det är klart att till olika ord anslutas olika mängder, och att varje delmängd till {1, ...n} anslutas till något ord. Då har vi den efterlängtade 1-1 korrespondensen, och beviset är därmed slut.

Obs! Ekv. (4) kan också deriveras genom att sätta x = y = 1 i Binomialsatsen. Se dina föreläsningsanteckningar.

Sats 3.4 Låt X vara en ändlig, icke-tom mängd. Då är det totala antalet delmängder till X bestående av ett jämnt antal element lika med det totala antalet delmängder bestående av ett udda antal element.

Bevis : Det räcker att betrakta mängderna {1, ..., n}, för n ≥ 1. Låt J_{n} (resp. U_{n}) beteckna det totala antalet delmängder till {1, ..., n} bestående av ett jämnt (resp. udda) antal element. Vi skall visa att, för alla n ≥ 1,

J_{n} = U_{n} = J_{n−1} + U_{n−1} = 2^{n−1}.

Betrakta J_{n}. Låt A vara en delmängd till {1, ..., n} som har ett jämnt antal element. Det finns J_{n} möjligheter för A enligt definitionen. Antingen n ∈ A eller n ∉ A. Om n ∈ A då är A = {n} ⊔ A^{∗}, där A^{∗} är en delmängd till {1, ..., n − 1} som har ett element mindre än A, därför ett udda antal element. Enligt definitionen, finns det U_{n−1} möjligheter för A^{∗}. Om n ∉ A, där är A själv en delmängd till {1, ..., n − 1}, med ett jämnt antal element, så enligt definitionen finns det J_{n−1} möjligheter för A.

Då finns det totalt J_{n−1} + U_{n−1} möjligheter för A, som bevisar att J_{n} = J_{n−1} + U_{n−1}.

En liknande argument (som lämnas till läsaren), visar att U_{n} = J_{n−1}+U_{n−1}. Slutligen, att J_{n} = U_{n} = 2^{n−1} följer då från att {1, ..., n} har totalt 2^{n} delmängder (se beviset av Sats 3.3).

Obs! I termer av binomiska koefficienter, Sats 3.4 är ekvivalent med ekvationen

∑_{k=0}^{n}(−1)^{k} ( \begin{matrix}n \\ k \end{matrix} ) = 0.  (5)

Denna ekvation kan också verifieras genom att sätta x = 1, y = −1 i Binomialsatsen. Se övning 5.27 och dina föreläsningsanteckningar.

Sats 3.5 Låt n ≥ 0 vara ett heltal. Då gäller att

3^{n} = ∑_{k=0}^{n} ( \begin{matrix}n \\ k \end{matrix} ) 2^{k}.  (6)

Bevis : Vi påstår at båda ledar av (6) ger antalet ternära ord (dvs, ord i de tre symbolerna 0, 1 och 2) av längd n.

VL : Vi har tre möjligheter för varje position (0, 1 och 2) och n positioner totalt, så enligt multiplikationprincipen finns det 3^{n} möjliga ord av längd n.

HL : Låt W beteckna samlingen av alla ternära ord av längd n. Vi skall dela upp W i n stycken mindre samlingar, W_{1}, ..., W_{n}, så att

#(W_{k}) = ( \begin{matrix}n \\ k \end{matrix} ) 2^{k}.

Detta skall räcka till att bevisa (6). Så vad är W_{k} då ?

Ju, W_{k} skall bestå av alla ord med (n − k)-stycken nollor. För ett sådant

ord, finns det ( \begin{matrix}n \\ n − k \end{matrix} ) val för positionerna av nollorna. Efter att ha plac-

erat nollorna får man sätta antingen en etta eller an tvåa i var en av de kvarstående k positionerna. Enligt multiplikationprincipen, har vi då att

#(W_{k}) = ( \begin{matrix}n \\ n − k \end{matrix} ) 2^{k} = ( \begin{matrix}n \\ k \end{matrix} ) 2^{k},

vilket skulle visas.

Obs! Ekv. (6) kan också deriveras genom att sätta x = 2, y = 1 i Binomialsatsen. Se övning 5.28 och dina föreläsningsanteckningar.

Sats 4.1 Låt a, b vara naturliga tal. Då gäller att SGD(a, b) är det minsta naturliga talet som kan skrivas i formen

ax + by,  (7)

för något par x, y av heltal (inklusive negativa tal).

Bevis : Låt d vara det minsta naturliga talet som kan skrivas i formen (7). Låt x_{0}, y_{0} vara heltal så att

d = ax_{0} + by_{0}.  (8)

För att bevisa att d = SGD(a, b) måste vi visa att

(i) d|a.

(ii) d|b.

(iii) Om c|a och c|b, då c|d.

(i) Enligt division algoritmen, finns det ett unikt par q, r av heltal så att 0 ≤ q, 0 ≤ r < d och

a = qd + r.  (9)

Att d|a är ekvivalent med att r = 0. För att visa detta, substituera (8) i (9) som då säger, efter lite manipulation,

r = a(1 − qx_{0}) + b(−qy_{0}).  (10)

Ekv. (10) uttrycker r i formen av (7). Men r ≥ 0 och d, enligt dess definition, är det minsta positiva talet som kan skrivas i denna form. Därför måste ju r = 0.

(ii) Samma typ av argument som för (i).

(iii) Låt c vara någon gemensam delare till a och b. Då är c också en delare till ax_{0} + by_{0} = d, v.s.v.

Hädanefter, använder vi multiplikativ notation · för den binära operationen i en allmän grupp.

Definition 9.1 : En icke-tom delmängd H till en grupp G kallas för en delgrupp till G om

(i) för alla a, b ∈ H, så är ab ∈ H ; dvs, H är sluten under multiplikationen i G, (ii) för alla a ∈ H, så är a^{−1} ∈ H.

Proposition 9.1 Låt (G, ·) vara en grupp, och H en delgrupp. Då är (H, ·) en grupp.

Bevis : Vi måste kolla att (H, ·) satisfierar gruppaxiomen. H är sluten under · enligt (i). Gruppoperationen är associativ i hela G, då också i H. Varje element i H har en invers i H, enligt (ii). Det kvarstår att visa existensen av en identitet. Vi påstår att identiteten 1_{G} av G ligger i H. För H är icke-tom, så det finns minst ett element a ∈ H. Då är a^{−1} ∈ H, enligt (ii). Och då är 1_{G} = aa^{−1} ∈ H, enligt (i).

Proposition 9.2 I en ändlig grupp, (i) är ett tillräckligt villkor för att en delmängd ska vara en delgrupp.

Bevis : Så låt G vara en ändlig grupp och H en sluten delmängd. Låt a ∈ H. Vi måste visa att a^{−1} ∈ H. Eftersom G är ändlig, kan inte alla positiva potenserna a^{n}(n > 0) av a vara olika element i G. Därför måste det finnas n > m > 0 så att a^{n} = a^{m}, som antyder att a^{n−m−1} = a^{−1}. Men a^{n−m−1} = a · a · ... · a (n − m − 1 gånger) är ett element av H, eftersom H är sluten under multiplikation, v.s.v.

Obs! Prop. 9.2 kan inte utvidgas till oändliga grupper. Till exempel, tag G = (Z, +) och H = N. Då är H sluten under multiplikation, men inte en delgrupp till Z.

Exempel 9.1 : Låt G vara en grupp, a ∈ G. Låt H vara delmängden av G som består av alla potenser av a, både positiva och negativa, tillsammans med a^{0} = 1. Då är det klart att H är en delgrupp till G. Den kallas för den cyckliska delgruppen genererad av a, och betecknas < a >.

Definition 9.2 : En grupp G kallas för cyklisk om det kan genereras av ett enda element, dvs om det finns a ∈ G så att G = < a >. Ett sådant element kallas för en generator av G.

Obs! Notera att en cyklisk grupp är abelsk.

Exempel 9.2 : Man ser lätt att de additiva grupperna Z och Z/nZ, för alla n > 0, är cykliska och genererade av 1. För varje primtal p är det också sant att den multiplikativa gruppen (Z/pZ)^{×} är cyklisk. För p udda är till och med grupperna (Z/p^{n}Z)^{×} cykliska, för alla n > 0. Tyvärr kan vi inte bevisa dessa fakta i denna kurs, men se Exempel 9.4(i) nedan. Notera också att att

(i) det är inte så lätt att ange en explicit generator av gruppen (Z/pZ)^{×}, för ett givet p. Man kan bevisa att minst 1/ log_{2} p av talen 2, ..., p − 1 är generatorer, men hur de är distribuerade i intervallen [0, p − 1] är inte helt klart. En konsekvens av den så kallade Riemann hypotesen skulle vara att det finns en konstant C > 0 så att, för varje p > 0, det finns en generator av (Z/pZ)^{×} som är mindre än C(log_{2} p)^{6} !! Vidare, om man har en generator av (Z/pZ)^{×}, så finns det en lätt formel för generatorer av (Z/p^{n}Z)^{×}, för alla n > 1. Se också Exempel 9.4(ii) nedan.

(ii) gruppen (Z/2^{n}Z)^{×} är inte cyklisk för n ≥ 3, men “nästan” - se anmärkning 9.1 nedan. För allmäna n, utom prim potenser, brukar (Z/nZ)^{×} inte vara cyklisk heller - se Prop. 9.3(iii) och Exempel 3.35 i boken.

Definition 9.3 : Om G är en ändlig grupp, då kallas antalet element i G för ordningen av G, och betecknas |G| eller o(G). Om G är oändlig, då säger man att G har oändlig ordning och skriver o(G) = ∞. Om H är en delgrupp till en ändlig grupp G, då kallas kvotet o(G)/o(H) för indexen av H i G, och betecknas (G : H). Vi skall se senare (Sats 9.6) att indexen av en delgrupp är alltid ett heltal.

Definition 9.4 : Låt G vara en grupp och a ∈ G. Ordningen av a är det minsta positiva talet n så att a^{n} = 1, och betecknas |a| eller o(a). Om det finns inget sådant n, då säger man att a har oändlig ordning och skriver o(a) = ∞.

Exempel 9.3 : (i) I varje grupp har identiteten ordning 1.

(ii) o(Z) = ∞ och varje icke-noll element i Z har oändlig ordning. (iii) o(Z/nZ) = n. Elementet [1] har ordning n, men elementet [2] har ordning n/2 när n är jämnt.

Proposition 9.3 Låt G vara en grupp, a ∈ G.

(i) För ett heltal N, då gäller att a^{N} = 1 omm o(a)|N. (ii) Ordningen av a är lika med ordningen av den cykliska delgruppen som genereras av a. (iii) Låt nu G vara en ändlig grupp. Då har varje element i G en ändlig ordning av högst o(G), och G är cyklisk omm det finns ett element a ∈ G så att o(a) = o(G).

Bevis : (i) Notera att om o(a) = ∞ då finns det inget N så att a^{N} = 1, som är konsistent med vad (i) säger. Antag nu att a har ändlig ordning, lika med t säg. Låt N > 0. Enligt division algoritm, finns det heltal q, r, med o ≤ r < t så att N = qt + r. Då har vi att

a^{N} = a^{qt+r} = (a^{t})^{q} · a^{r} = a^{r}.  (11)

Eftersom t är det minsta positiva talet så att a^{t} = 1, så följer det från (11) att a^{N} = 1 omm r = 0, dvs omm t|N, v.s.v.

(ii) Låt n > m > 0 vara ett par av positiva heltal. Då, m.h.a. (i), har vi att

a^{n} = a^{m} ⇔ a^{n−m} = 1 ⇔ o(a) < ∞ och o(a) | n − m.  (12)

Om o(a) = ∞ då medför (12) att inga två positiva potenser av a är lika, så att < a > = ∞ också. Om o(a) = t < ∞, då medför (11) och (12) att

< a > = {1, a, ..., a^{t−1}},

dvs att dessa t element är olika, och att varje potens av a är lika med ett av dem. Då har vi att o(< a >) = t också i det här fallet.

Obs! Argumentet i detta bevis borde påminna er om första delen av vårt bevis av Eulers sats.

Exempel 9.4 (i) Låt G = (Z/7Z)^{×}. Då är G cyklisk av ordning ϕ(7) = 6 och genererad av [3]. Vi har [3]^{1} = [3], [3]^{2} = [2], [3]^{3} = [6], [3]^{4} = [4], [3]^{5} = [5] och [3]^{6} = [1].

(ii) Låt n ≥ 3. Gruppen (Z/2^{n}Z)^{×} har ordning ϕ(2^{n}) = 2^{n−1}. Gruppen har inget element av ordning 2^{n−1}, alltså är inte cyklisk. Men man kan visa att [5] har ordning 2^{n−2} (se inlämningsuppgift 2), så gruppen är, på något sätt, nästan cyklisk. Se också Korollarium 9.7 nedan.

Anmärkning 9.1 : (a) Given en ändlig grupp G vars ordning är känd, och ett slumpmässigt valt a ∈ G, kan det vara väldigt svårt att beräkna o(a). Om faktoriseringen av o(G) är också känd då blir problemet mycket lättare pga Korollarium 9.7 nedan, men, som vi vet, verkar ju faktorieringen av ett heltal att vara ett väldigt knepigt problem också.

Å andra sidan, brukar det vara betydligt lättare att avgöra om det givna elementet a är en generator av G. Enligt del (ii) av propositionen, gäller det bara att avgöra om o(a) = o(G) eller inte, snarare än att beräkna o(a) exakt. I gruppen (Z/pZ)^{×} till exempel (p ett udda primtal), som vi vet är cyklisk (se Exempel 9.3 ovan), finns det en snabb algoritm för att avgöra om ett givet a ∈ {2, ..., p − 1} är en generator - se supplementär kursmaterialen.

(b) För alla de ändliga grupper som har bemöts i denna kurs har gruppordningen varit ganska lätt att beräkna. Men det uppstår situationer där ordningen av gruppen själv (never mind its’ elements) är långt från klart. Ett viktigt exempel kommer från en modern form av kryptering som heter ECC (elliptic curve cryptography) - se supplementär kursmaterialen.

Följande resultat sammanfattar de viktigaste egenskaperna hos ändliga cyckliska grupper :

Proposition 9.4 Låt G vara en cyklisk grupp av ordning n > 0, och a en generator av G.

(i) a^{i} är en generator av G omm SGD(i, n) = 1. Då har G precis ϕ(n) olika generatorer. (ii) För varje positiv delare d av n har G en unik cyklisk delgrupp av index d, som genereras av a^{d}. G har inga delgrupper utom dessa.

Bevis : (i) Jag påstår att

o(a^{i}) = \frac{n}{SGD(n, i)}.  (13)

För HL är det minsta talet t så att n|it. Använd nu Prop. 9.3(i).

(ii) Låt H vara en delgrupp till G. Låt d vara det minsta positiva talet så att a^{d} ∈ H. Jag påstår att

(a) d|n,

(b) H = < a^{d} >,

(c) (G : H) = d.

(a) : Vi har att a^{qd} ∈ H för alla heltal q, eftersom H är sluten under multiplikation och inversion. Låt r = SGD(d, n). Enligt Euklides algoritm, finns det heltal x, y så att r = nx + dy. Då har vi att

a^{r} = a^{nx+dy} = (a^{n})^{x} · a^{dy} = a^{dy} ∈ H,

så r ≥ d, som medför att r = d, dvs att d|n.

(b) : Antag att a^{i} ∈ H för något i > 0. Enligt division algoritmen finns det heltal q, r, med 0 ≤ r < d så att i = qd + r ⇒ r = i − qd. Då har vi att a^{r} = a^{i} · a^{−qd} ∈ H, som tvingar r = 0.

(c) : o(H) = o(a^{d}), enligt Prop. 9.3(ii). Men, enligt del (i) och (a) är ju o(a^{d}) = n/SGD(n,d) = n/d. Därför är (G : H) = o(G)/o(H) = n/\frac{n}{d} = d, v.s.v.

Exempel 9.5 : I gruppen Z/nZ är

o([a]) = \frac{n}{SGD(n, a)}.

Vi fortsätter med några exempel till av delgrupper :

Exempel 9.6 : G = D_{n}, r = rotation genom 2π/n, s = spegling genom x-axeln. < r > är en cyklisk delgrupp av index 2 och < s > är en cyklisk delgrupp av index n. För varje delare d av n, så genererar r^{d} och s en delgrupp H_{d} av index d. H_{d} är abelsk omm n är jämnt och d = n/2, i vilket fall H_{n/2} är en icke-cyklisk grupp av ordning 4. Varje element i H_{n/2} (utom 1) har ordning 2 (dvs, är en så-kallad involution).

Exempel 9.7^{1} : G = S_{n}. En cyklisk permutation (a_{1}, ..., a_{k}) har ordning k. Om π ∈ S_{n} är en produkt av r st. disjunkta cykel av ordningar k_{1}, ..., k_{r} resp., då är

1Historical remark : Galois proved his theorem about non-existence of a ‘formula’ for

o(π) = MGM(k_{1}, ..., k_{r}).

För 1 ≤ i ≤ n, sätt

H_{i} := {π ∈ S_{n} : π(i) = i}.

Då är varje H_{i} en delgrupp av ordning (n − 1)! och index n, som kan identifieras med S_{n−1}.

Exempel 9.8 : G någon grupp som helst. Sätt

Z(G) := {z ∈ G : zg = gz för alla g ∈ G}.

Då är Z(G) en delgrupp av G (se inlämningsuppgift 2) som kallas för centrum av G.

I exempel 6 och 7 notera att indexen av varje delgrupp är ett heltal. Dessutom säger Prop. 9.4(ii) att detsamma gäller för en godtycklig delgrupp i en godtycklig ändlig cyklisk grupp. Detta är ingen slump, som vi skall nu bevisa :

Obs! Följande argument borde påminna er om andra delen av vårt bevis av Eulers sats (tag H = < [a] >).

Lemma 9.5 Låt G vara en grupp, H en delgrupp. Inför en relation ∼ på G som följer :

Säg a ∼ b om det finns h ∈ H så att b = ah.

Då är ∼ en ekvivalens relation på G.

Bevis :

the roots of a 5th degree polynomial equation by reducing the existence of such a formula to the group S_{5} having a certain purely group-theoretic property called solubility. It is not hard to show that S_{n} is insoluble iff n ≥ 5, and hence that there exists no ‘formula’ for the roots of a polynomial of any degree ≥ 5. For more discussion, see the supplementary course material.

Reflexivitet : a = a · 1 och 1 ∈ H. Symmetri : b = ah ⇒ a = bh^{−1}, och h ∈ H ⇒ h^{−1} ∈ H. Transitivitet : Antag b = ah_{1} och c = bh_{2}. Då är c = (ah_{1})h_{2} = a(h_{1}h_{2}) och h_{1}, h_{2} ∈ H ⇒ h_{1}h_{2} ∈ H. Ekvivalensklassen av a ∈ G betecknas aH och kallas för den vänstra komängden av H som innehåller a. Det är klart från definitionen av ∼ att

aH = {ah : h ∈ H}.  (14)

Då säger Lemma 5 att, för två element a, b ∈ G, antingen aH ∩ bH = ϕ eller aH = bH, i vilket fall b = ah för något h ∈ H. Sats 9.6 (Lagrange) Låt G vara en ändlig grupp och H en delgrupp till G. Då är o(H) en delare till o(G). Bevis : Enligt Lemma 5 är G unionen av parvis disjunkta vänstra komängder av H. Det är klart från (14) att varje komängd har precis o(H) element. Om det finns k st. komängder, då har vi att o(G) = k · o(H), som medför att o(H) delar o(G), v.s.v. Korollarium 9.7 Låt G vara en ändlig grupp och a ∈ G. Då gäller att

(i) o(a) delar o(G). (ii) a^{o(G)} = 1. Bevis : (i) Tillämpa Sats 9.6 till delgruppen H = < a > och använd Prop. 9.3(ii). (ii) Följer från del (i) och Prop. 9.3(i). Korollarium 9.8 Eulers sats. Bevis : Tillämpa Kor. 9.7(ii) till gruppen G = (Z/nZ)^{×}.