Algebra 1 (voorjaar 2017)

 

Mededelingen

 

Rooster

Hoorcollege

 

Behandelde stof

Toekomstige data zijn planning.

Datum Behandelde stof
16 februari slides inleiding, §2 tot en met 2.4 behalve 2.2: groepen, de orde, commuteren, abelse groepen, voorbeelden van groepen: \((\mathbb{R},+)\), \(\mathbb{R}^\ast\), vectorruimtes, \(GL_n(\mathbb{R})\), \(V_4\) (uit §1), \(S(X)\) (permutaties). De verzameling \(Sym(X)\) voor \(X \subseteq \mathbb{R}^2\) uit Definitie 3.7, maar zonder bewijs dat het een groep is.
23 februari §2 t/m 2.8 en §1: 1.7 (was 1.5 in eerdere versies van het dictaat): de orde, \(S_n\), disjunctecykelnotatie, ondergroepen, voortbrengers, cyclische groepen, inclusief opgave 2.49

Foto's van het krijtbord staan hier.
2 maart (college door Peter Bruin) rest van §1 en §2: onder andere \(D_n\), tekenafbeelding, \(A_n\), inclusief opgave 2.46
9 maart §3: symmetrieën van het vlak
16 maart (geen college)
23 maart §4: homomorfismen, kern, beeld, (linker)nevenklasse, stelling van Lagrange, conjugatie
30 maart rest van §4: isomorfiestelling, centrum, normaaldeler, quotiëntgroep
6 april §5 tot en met voorbeelden 5.4: groepswerkingen, baan, stabilisator, baan-stabilisator-stelling 5.3, inclusief opgave 5.2
13 april §5 tot 5.11: banenformule, reguliere werking, conjugatiewerking, opgave 4.58
20 april (geen college)
27 april (geen college)
4 mei (college door Peter Bruin) rest van §5: conjugatiewerking, stelling van Cauchy; mogelijk begin §6.
11 mei §6: ggd, priemfactorisatie, ringen, \(\mathbb Z/n \mathbb Z\)
18 mei rest van §6: Euclidische algoritme, Chinese reststelling, stellingen van Euler en Fermat
25 mei (geen college)
1 juni §8 t/m 8.6: ondergroepen van quotiëntgroepen, commutatorondergroep, abelsgemaakte groep, homomorfiestelling
8 juni Hoorcollege:
Rest van §8: semi-direct product, affiene groep, verwijzing naar 10.4
RSA en Diffie-Hellman: een Sage-werkblad (gebruik het sws-bestand op een Sage notebook-server naar keuze, open het werkblad op de Leidse server, of bekijk een pdf-afdruk van het werkblad)
De stof van dit college is geen tentamenstof. Wel bevat het toepassingen in het dagelijks leven, theorie die bruikbaar is in de rest van je studie, en oefening die nuttig is voor het tentamen.

Werkcollege:
Oude tentamens oefenen.

Werkcollege

 

Tentamen

 

Huiswerk

Het maken van opgaven is essentieel voor het begrijpen en kunnen halen van het vak. Daarnaast mag je opgaven inleveren, en deze tellen mee voor je cijfer (zie huiswerkreglement). De ervaring leert dat wie hier geen gebruik van maakt, een zeer kleine kans heeft om het vak te halen.

De meeste 8-puntsopgaven en alle "overige geschikte opgaven" zonder * zouden zonder veel moeite te doen moeten zijn voor iedereen. Maak (in klad) altijd in ieder geval alle 8-puntsopgaven en probeer zoveel mogelijk andere opgaven te maken. Lever daarna 3 opgaven in het net in.

Als je vastzit bij het maken van een opgave, kan je altijd voor hulp langslopen bij een van de werkcollegebegeleiders of de docent. Je kunt beter niets inleveren dan huiswerk overschrijven of laten overschrijven (zie huiswerkregelment).

Inleverdatum 8-puntsopgaven 9-puntsopgaven overige geschikte opgaven (geen punten)
Huiswerkset 1 met deadline 23 februari 1.15, 2.15, 2.16 2.24, 2.312, 2.43 1.91, 2.17, 2.18, 2.19, 2.22, 2.25, 2.26, 2.35*, 2.36, 2.37*, 2.44*, 2.45*
Huiswerkset 2 met deadline 2 maart 2.93,8, 2.27, 2.30 2.28, 2.406, 2.51 1.16, 1.18, 1.19, 1.20, 1.21, 1.22*, 1.23*, 2.8, 2.23*5,7, 2.324, 2.34*, 2.39*4, 2.46, 2.47, 2.50
Huiswerkset 3 met deadline 9 maart 1.17, 2.5010, 2.54 2.529, 2.55, 2.56 1.20, 1.24, 2.38*, 2.41, 2.42, 2.48*, 2.53
16 maart (geen werkcollege) (geen werkcollege) (geen werkcollege)
Huiswerkset 4 met deadline 23 maart 3.3, 3.21, 3.27 3.2814, 3.2911,12, 3.3012 3.8, 3.11, 3.15, 3.16, 3.17, 3.18, 3.20, 3.2415, 3.25, 3.26*13, 3.3112, 3.32, 3.33, 3.34
Huiswerkset 5 met deadline 30 maart 4.15, 4.16, 4.19 4.20, 4.27, 4.28 4.12, 4.13, 4.14, 4.17, 4.18, 4.21, 4.25
Huiswerkset 6 met deadline 6 april 4.9, 4.46, 4.55 4.29, 4.31, 4.5116 4.7, 4.30, 4.32, 4.33, 4.34, 4.35, 4.36, 4.44, 4.45, 4.47, 4.49, 4.50, 4.52, 4.53, 4.56, 4.58, 4.59
Huiswerkset 7 met deadline 13 april 5.11, 5.1319,17, 5.20 4.6018, 5.14, 5.2117,20 het eerste stuk van §5
20 april (geen werkcollege) (geen werkcollege) (geen werkcollege)
27 april (geen werkcollege) (geen werkcollege) (geen werkcollege)
Huiswerkset 8 met deadline 4 mei 5.18, 5.27, 5.3421 (*)22,23, 5.4724, 5.4925 §5 t/m grofweg opgave 5.37
Huiswerkset 9 met deadline 11 mei 5.2827, 5.3929, 5.5326 5.45, 5.4628, 5.5030 rest van §5, bijvoorbeeld 5.29, 5.51, 5.52; en kijk alvast naar 5.57
Huiswerkset 10 met deadline 18 mei 5.5531, 6.432, 6.2533 6.1135, 6.24, 5.5734 6.15, 6.16, 6.17, 6.18, 6.19, 6.20, 6.2636, 6.28, 6.30, 6.47, 6.48
25 mei (geen werkcollege) (geen werkcollege) (geen werkcollege)
Huiswerkset 11 met deadline 1 juni 6.1337, 6.4138, 7.1739 6.29, 6.3638, 6.4340 6.21, 6.22, 6.31 - 6.42, 6.49, 6.55, 7.11, 7.12, 7.15, 7.16, 7.19
Huiswerkset 12 met deadline 8 juni 8.16, 8.18, 8.2 8.13, 8.14, 8.1541 8.10, 8.11, 8.12, 8.17, 8.19, 8.20, 8.21

Opmerkingen

1De structuur van een viergroep van Klein wordt in de laatste alinea van p.9 van het dictaat gedefinieerd.

2De zin tussen haakjes ("Dit is ook waar als...") hoeft niet bewezen te worden. Deze slaat bovendien alleen op het feit dat de orde van een element \(x \in G\) de orde van \(G\) deelt, niet op de identiteit van producten; de producten in kwestie zijn namelijk niet gedefinieerd voor niet-abelse \(G\).

3Tip: Controleer na afloop voor \(n=5\) dat je precies 120 elementen krijgt.

4Zie Lemma 2.8 voor de definitie van \(\langle S \rangle\).

5Een groep \(G\) heet cyclisch als er een element \(a \in G\) is zodanig dat alle elementen van \(G\) machten van \(a\) zijn.

6Een groep \(G\) heet voortgebracht door een deelverzameling \(S \subseteq G\) als ieder element van \(G\) te schrijven is als een product van elementen van \(S\) en inversen van elementen van \(S\).

7Hier mag je, zoals meestal, de opgave ervoor gebruiken. Voor opgave \(n\) geeft opgave \(n-1\) vaak een bruikbaar resultaat of opgave \(n+1\) een toepassing. Het is zeer aan te raden een paar minuten te besteden aan het lezen van verschillende opgaven en te kijken wat het "nut" of de "bedoeling" van elke opgave is.

8Laat ook zien dat er voor positieve gehele getallen \(2 \leq a \leq n\) precies \(\frac{n!}{a \cdot (n - a)!}\) cykels van lengte \(a\) in \(S_n\) zijn. En laat ook zien dat voor positieve gehele getallen \(a, b \geq 2\) met \(a + b \leq n\) het aantal permutaties met cykeltype \((a, b, 1, 1, \ldots, 1)\) gegeven wordt door \(\frac{n!}{ab \cdot (n - a - b)!}\) als \(a \neq b\) en door \(\frac{n!}{2ab \cdot (n - a - b)!}\) als \(a = b\). Gebruik dit vervolgens voor \(S_4\) en \(S_5\).

9Hints: Laat zien dat er een transpositie \(t\) is met \(f(t)\) ongelijk aan 1; wat is \(f(t)\)? Laat ook zien dat \(f(t)\) gelijk is voor alle transposities \(t\). Combineer deze twee resultaten tot een bewijs van het gevraagde. Gebruik Stelling 1.7 en opgave 2.46 voor de deelresultaten.

10Geef hier zelf een definitie van "baan" die past bij de context (of als dat je echt niet lukt, zoek de definitie op in de index).

11Voor wie het dictaat van 2014 heeft: lees "met een positieve factor" als "met dezelfde positieve factor". Dit is al aangepast in het dictaat van 2015.

12Bij deze opgaven mag je voorgaande opgaven gebruiken, dus bij opgave 30 mag je 29 gebruiken, en bij opgave 31 mag je 29 en 30 gebruiken. Kies je er juist voor om bijvoorbeeld bij opgave 29 gebruik te maken van opgave 30, dan moet je (1) opgave 30 ook maken, (2) bij opgave 30 geen gebruik maken van opgave 29, en (3) dit allemaal duidelijk aangeven.

13Bewijs dat er een \(a \in \mathbb R^2\) is zodat voor alle \(\varphi \in \operatorname{Sym}(F)\) geldt dat \(\varphi(a) = a\), en neem die \(a\) als oorsprong. Enige hints: Laat zien dat de afbeelding \(L \colon \operatorname{Sym}(F) \to O_2(\mathbb R)\) injectief is, dat iedere niet-triviale \(\varphi \in \operatorname{Sym}(F)^+\) een uniek vast punt \(a_{\varphi}\) heeft, en dat \(\operatorname{Sym}(F)^+\) commutatief is.

14Voor de definities, zie opgave 27. Het is voor het huiswerk voldoende om te laten zien dat de puntgroep voor een geschikte keuze van coördinaten gelijk is aan \(C_n\) of \(D_n\) met \(n\) in \(\{1,2,3,4,5,6\}\). Je hoeft dus \(n=5\) niet uit te sluiten, maar het mag wel. Om je te helpen, staan hier een aantal deelopgaven. Het is niet verplicht, maar wel sterk aan te raden, om deze te gebruiken:

  1. Laat \(\Lambda = \{xa + yb : a,b \in \mathbb{Z}\}\) met \(x\) en \(y\) als in de opgave; we noemen dit het rooster opgespannen door \(x\) en \(y\). Laat zien dat voor alle \(\psi \in \overline{G}\) geldt \(\psi(\Lambda)\subseteq\Lambda\). Hint: bekijk \(\phi \tau_x \phi^{-1}\) voor \(\phi \in G\).
  2. Je mag zonder bewijs gebruiken dat \(\Lambda\setminus\{0\}\) een kortste element \(z\) heeft. Definieer \(V := \{x \in \Lambda : |x| = |z|\}\). Laat zien dat \(\overline{G}\) een ondergroep is van \(Sym(V)\).
  3. Laat zien dat elk tweetal elementen van \(V\) een hoek maakt van \(\geq\) 60 graden (gezien vanuit de oorsprong).
  4. Bewijs dat \(\overline{G}\) voor geschikte keuze van coordinaten gelijk is aan \(C_n\) of \(D_n\) met \(n \leq 6\). Hint: gebruik Stelling 3.8.

15Gebruik Stelling 3.11.

16Lees de laatste vraag als: Geef een isomorfisme van \(S_4/H_2\) naar een ''bekende'' groep (van orde 6) uit een eerder hoofdstuk.

17Opgave 5.2 mag gebruikt worden.

18Hints. Laat \(G\) werken op \(G/H_1 × G/H_2\) en gebruik Stelling 5.3. Voor het tweede deel: bekijk \(G = S_3\). Voor de duidelijkheid: je mag Stelling 5.3 uit het college in dit geval gebruiken ondanks het feit dat deze opgave in een eerder hoofdstuk gedrukt staat.

19Geef ook een verzameling representanten (een deelverzameling \(R \subseteq X\) die van iedere baan precies 1 element bevat).

20\(\zeta_3\) is optioneel. Geef eindige groepen expliciet door de (eindige) lijst van elementen te geven of door voortbrengers te geven.

21De laatste zin is optioneel.

22Bepaal het aantal kleuringen met \(n\) (\(n \geq 1\)) kleuren van de hoekpunten van de kubus, op rotatiesymmetrie (de groep \(K^+\)) na.

23Voor de duidelijkheid: zij \(C\) een verzameling bestaande uit \(n\) verschillende kleuren, bepaal het aantal kleuringen van de hoekpunten van de kubus waarbij alleen kleuren uit \(C\) gebruikt worden, op rotatiesymmetrie na. Een kleuring hoeft hierbij niet alle kleuren uit \(C\) te gebruiken. Deze opgave werkt dus precies zoals opgaves 16, 17 en 18, behalve dat het antwoord een functie is van het getal \(n\).

24Hint: Gebruik de reguliere werking op \(G/H\).

25Hint: Gebruik de banenformule.

26En gebruik dit om opgave 5.9 op te lossen voor \(A_4\).

27Je mag opgave 5.27 gebruiken, en de uitkomst van opgave 5.9 voor \(A_5\): \((1, 20, 15, 12, 12)\).

28Dit is te doen door eerdere opgaven te combineren, maar het is leuker om het te doen met alleen stellingen uit het dictaat.

29Je moet Stellingen 5.13 (Cauchy) en 5.9 (reguliere werking) gebruiken. (In een eerdere versie van het dictaat zijn dit stellingen 5.14 en 5.10.)

30Hint: Stel \(H\) is een ondergroep van \(G\) die niet gelijk is aan \(G\). Gebruik opgave 5.49 om te bewijzen dat \(G\) niet de vereniging is van de geconjugeerden van \(H\).

31Hint voor het laatste deel: wat wordt er precies over \(t\) bewezen in een van de bewijzen in hoofdstuk 5?

32Gebruik geen resultaten die later in het dictaat staan.

33Voor een toepassing, zie 6.26.

34In het dictaat van 2017 staat een duidelijke en correcte versie van de opgave. Voor wie een dictaat uit 2016 of eerder heeft: Zij \(G\) een groep van orde \(n = p^k m\) met \(p\) priem en \(p \not \mid m\). Een Sylow-\(p\)-ondergroep van \(G\) is een ondergroep \(H \subseteq G\) van orde \(p^k\). We gaan bewijzen dat zo'n \(H\) bestaat. Neem \(X\) gelijk aan de collectie van \({\it deelverzamelingen}\) van \(G\) van cardinaliteit \(p^k\), en laat \(G\) werken op \(X\) door linksvermenigvuldiging: \(gV = \{gv : v \in V\}\) voor \(g \in G\) en \(V \in X\). (En dan a, b, c als in het dictaat).

35Dit moet zonder opgave 5.39 te gebruiken. Hint: waarop werkt de groep \(\operatorname{GL}_2(\mathbb F_2)\)?

36Hier mag je, zoals meestal, de opgave ervoor gebruiken. Voor opgave \(n\) geeft opgave \(n-1\) vaak een bruikbaar resultaat of opgave \(n+1\) een toepassing. Het is zeer aan te raden een paar minuten te besteden aan het lezen van verschillende opgaven en te kijken wat het "nut" of de "bedoeling" van elke opgave is.

37Maar dan met \(a = 54321\) en \(b = 98765\). Laat je berekening zien.

38Laat je berekening zien. Vergeet het tweede deel niet.

39Je mag de antwoorden vinden met de computer, maar je moet de antwoorden bewijzen met de hand.

40Doe opgave 4.23 en laat zien dat de ondergroepen cyclisch zijn. Je mag opgave 6.42 gebruiken zonder die te bewijzen.

41Vergeet het geval \(n = 1\) niet.

Reglement voor huiswerk

Huiswerk wordt op de volgende manier behandeld:

 

Typesetten

Bij het vak Algebra 1 wordt het huiswerk bij voorkeur netjes elektronisch getypeset voor de leesbaarheid, bij voorkeur met LaTeX. Zowel handgeschreven als getypeset huiswerk moet minstens even leesbaar zijn als wanneer het met LaTeX gedaan wordt. Zo moeten bij dingen als \(a \in G\) de \(a\) en de \(G\) duidelijk visueel onderscheidend gedrukt zijn, zoals de cursieve \(a\) in LaTeX.

Dit heeft meerdere heel verschillende redenen en voordelen. Huiswerk met LaTeX is veel leesbaarder dan vrijwel alle handschriften. Er geen gekras in elektronisch werk. Met elektronisch werk is het eenvoudiger om veranderingen aan te brengen, waardoor je uitwerkingen die niet correct/optimaal zijn opgeschreven eenvoudig corrigeert/verbetert wanneer je ze nog eens doorleest. Je oefent het opschrijven van wiskundige bewijzen niet alleen op papier maar ook elektronisch. Je oefent met LaTeX, wat scheelt bij het schrijven van je scripties en eventuele latere artikelen. Het blijkt dat het echt uitschrijven van je oplossing helpt met het structureren van je uitwerking. Het scheelt ongelofelijk veel nakijktijd. Het zorgt ervoor dat er geen dingen foutgerekend worden doordat ze niet duidelijk leesbaar waren. Aan de andere kant heeft het natuurlijk ook duidelijke nadelen, vooral voor diegenen die nog niet veel met LaTeX gewerkt hebben. Hier volgen een aantal tips om de nadelen zoveel mogelijk te verlichten.

 

Inhoud

In dit eerste college uit de algebracyclus wordt een aantal onderwerpen uit het vak wiskundige structuren, zoals gehele getallen, permutaties, symmetriegroepen en restklassen, geabstraheerd en geünificeerd in het begrip 'groep'. Er wordt aandacht geschonken aan toepassingen in de combinatoriek, de vlakke meetkunde, de getaltheorie en de cryptografie.

Behandeld worden: permutaties, vlakke symmetrieën, groepshomomorfismen, groepswerkingen, rekenen modulo \(n\), het RSA-cryptosysteem, producten en quotiënten van groepen, abelse groepen en Sylowondergroepen.

Tijdens het werkcollege zal tevens aandacht geschonken worden aan het correct opschrijven van bewijzen.

Voorkennis

We gebruiken de taal van de verzamelingenleer, zie de eerste twee hoofdstukken van het dictaat wiskundige structuren. Het helpt aanzienlijk als het vak wiskundige structuren met goed gevolg doorlopen is. Verder worden er soms voorbeelden gegeven die basiskennis uit de lineaire algebra gebruiken.

 

Literatuur

Het dictaat Algebra 1 van prof. Stevenhagen zal als richtlijn dienen voor het college. Dit dictaat is te koop bij het eerste werkcollege en daarna bij het secretariaat (kamer 203a). Het dictaat kost 10 euro en er kan alleen contant (het liefst gepast) worden betaald. Daarnaast is de nieuwste versie altijd hier online beschikbaar. Dictaten uit eerdere jaren zijn prima te gebruiken, maar controleer bij het gebruik van dictaten van voor 2014 even of de opgavenummers overeenkomen.

 

Tentamen

Elk huiswerkcijfer dat hoger is dan het tentamencijfer telt voor 2% mee in het eindcijfer. In totaal telt het huiswerk voor maximaal 20% van het eindcijfer mee. De rest van het eindcijfer wordt bepaald door het tentamen. Niet-ingeleverd huiswerk kost je waardevolle oefening en feedback, maar heeft verder geen directe invloed op het eindcijfer. Dit wijkt dus af van de regel van voor 2017.

Bij het tentamen mag het dictaat gebruikt worden, maar geen uitwerkingen van opgaven en geen rekenmachines of andere elektronische hulpmiddelen. Eventuele onderstrepingen, markering of korte hoorcollege-notities in het dictaat zijn geen probleem, zolang het geen (gedeeltes van) werkcollege-notities of uitwerkingen van opgaven of oude tentamens zijn. Dit wijkt dus af van de regel van voor 2016.

Succesvolle deelname aan dit vak wordt beloond met 6 ECTS studiepunten. Hiervoor moet het (niet-afgeronde) tentamencijfer ten minste een 5,0 bedragen en het afgeronde eindcijfer ten minste een 6 (dus het niet-afgeronde eindcijfer moet ten minste 5,5 zijn).