2WF50 Algebra en Discrete Wiskunde - Semester B Kwartiel 1

Inhoudsbeschrijving Laatste nieuws Studiemateriaal Tentamen Collegeplanning

Docent: Tanja Lange
e-mail:tanja@hyperelliptic.org

Instructeur: Ruud Pellikaan

Dit is the pagina voor het college 2WF50 - Algebra en Discrete Wiskunde. De oficiele pagina OWInfo.

Inhoudsbeschrijving
Monoiden en semigroepen, de classificatie van cyclische monoiden. Productconstructies en deelstructuren. Groepen, de kleine stelling van Fermat, de stelling van Lagrange over ondergroepen. Ringen en lichamen, een uitgebreide kennismaking met polynoomringen over een lichaam. Idealen en normale ondergroepen als kernen van morfismen. De classificatie van eindige lichamen. Een meer gedetailleerde studie van permutatie groepen, en automorfisme groepen van combinatorische en meetkundige objecten.

Laatste nieuws

Instructie: dinsdags 08:45 - 10:30, potentiaal 9.05
College: dinsdags 10:45 - 12:30, auditorium 13, en vrijdags 13:45 - 15:30, auditorium 10.
Op februari 25 instructie in MF 11 en 12.
Op maart 14 geen college ivm Open Dagen.
Op maart 25 geen instructie of college maar PRV62.
Op maart 28 college (blok 5&6) en instructie (blok 7&8, in Aud 14)
Op april 1 geen college of instructie, op april 4 wel college.

Studiemateriaal

Algebra Interactive, Springer-verslag, Heidelberg 1999 (aanbevolen), in engels. Dit boek is niet meer beschikbaar voor verkoop maar de auteurs stellen een exemplaar voor download ter beschikking.
Meer informatie op het web

Collegeplanning

04 Feb 2014
Instructie:
Repetitie van rekenen modulo n, het m-RSA-cryptosysteem, het Euclidische algoritme.
Public-key crypto
M-RSA m-RSA is "Kid-RSA" van Fellows en Koblitz gekraakt. Attentie, did systeem is niet veilig.
College:
Monoiden en halfgroepen: definities, structuur, n-tallige bewerkingen, halfgroepen, neutraal element/eenheidselement.
Hier zijn de foto's van het board.

07 Feb 2014
College:
Monoiden en halfgroepen: commutatieve bewerkingen, deel-structuren (monoid, halfgroep), vermenigvuldigtafel, vrije monoid over A, direct product van monoiden en halfgroepen, iedere doorsnede van deelmonoiden/onderhalfgroepen is een monoid/halfgroep, homomorphismen, isomorphismen, enkele voorbeelden.
Hier zijn de foto's van het board.

11 Feb 2014
Instructie:
Exercises 6.7.3, 6.7.4, 6.7.5,6.7.7, 6.7.10 on pages 160, 161 of the Algebra Interactive pdf file.

Huiswerk: Blad 1

College:
Cyclische monoiden, voortbrenger van een cyclische monoid, <D>M: deelmonoid van M voortgebracht door D, Ck,n, inverse, Euler φ function, φ(m)=|(Z/m)*|.
Hier zijn de foto's van het board.

14 Feb 2014
College:
inverse, inverse van a is uniek, schrapwet: uit xy=xz volgt y=z voor inv(x) in M; groepen, ondergroepen, direct product van groepen, doorsnede van ondergroepen is een ondergroep, cyclische groepen, voorbrenger, centrum Z(G), centralisator C(X,G), normalisator N(X,G), voorbeelden.
Hier zijn de foto's van het board.

18 Feb 2014
Instructie:
Exercises 6.7.11 (note, I used Cn,k instead of Ck,n; 6.7.13; 6.7.16 with r= the real numbers; 6.7.24; 6.7.25; 6.7.27 with R= the real numbers, GL(n,R) was denoted GLn(R) in class and is the general linear group, i.e. the group of matrices with nonzero determinant. (pages 161 and 162 of the Algebra Interactive pdf file).

Huiswerk: Blad 2

College:
Centrum Z(G), centralisator C(X,G), normalisator N(X,G), beeld.
Voorbeelden:

Hier zijn de foto's van het board.

21 Feb 2014
College:
Orde van een groep, orde van een element, cyclische groepen, voorbrenger, voorbeelden, linkernevenklassen, stelling van Lagrange.
Hier zijn de foto's van het board.

25 Feb 2014
Exercises:
In MF 11+12, on http://www.sagemath.org. Install sage or get an account before the exercise round; bring your laptop.
Here is a quick reference sheet for sage.
This is the list of the commands I typed. Note that some of them will give errors, these are deliberate to show that only x is a predefined variable and that Zmod.order() is not defined (could be addition or multiplication).

Homework: Sheet 3. Note, I updated part 3 to include another number.

Lecture:
Lagrange's Theorem, left cosets all have the same size, order of an element divides the group oder, Fermat's little theorem, normal subgroups, examples, kernel of a homomorphism is a normal subgroup. Rings, examples such as Z, Z/nZ, polynomial rings R[x], unit group, ring homomorphisms, properties of homomorphisms.
(Stelling van Lagrange, alle linkernevenklassen zijn even groot, kleine stelling van Fermat/stelling van Euler, normaaldeler, kern is een normaaldeler, voorbeelden. Ring, voorbeelden, Z, Z/nZ, R[x], eenheidengroep, homomorphismen, eigenschappen.)
Hier zijn de foto's van het board.

28 Feb 2014
Lecture:
Examples of rings and homomorphisms, R[x]/(x^2+1) is isomorphic to C, ideals, kernel of a homomoprhism is an ideal, direct products, proof of Chinese Remainder Theorem using direct products, CRT also works for polynomials, polynomial rings R[x] over a ring R, (R× S)×=R×× S×.
Here are the pictures of the black board.

11 Mar 2014
Exercises:
Please prepare 6.7.31, 6.7.35, 7.8.1, 7.8.3, 7.8.4, 7.8.7, 7.8.8. You should use the exercise time to ask questions about the parts that you find most complicated; no need to go through these exercises in order.

Homework: Sheet 4 and read (and understand) the proof that the quotient ring of a domain is a field.

Lecture:
Intersection of subrings is a subring, <D>R, R[x][y]=R[x,y], zero divisors, domains, zero divisors are not invertible, if R is a domain then so is R[x], cancellation law holds in domains, fields, finite domains are fields, L(a), field of fractions.
Here are the pictures of the black board.

18 Mar 2014
Exercises:
Please prepare 7.8.9, 7.8.11, 7.8.12, 7.8.13 (you can use the homework), 7.8.14, 7.8.15. You should use the exercise time to ask questions about the parts that you find most complicated; no need to go through these exercises in order.

Homework: Sheet 5 and read (and understand) the proofs of the last theorem and lemma covered in class.

Lecture:
Prime field, characterisitic, K is L-vectorspace, finite fields have order equal to a prime power, field with 4 elements, a(x) invertible in K[x]/(f(x)) if gcd(a,f)=1, if f is irreducible this gives a field, α is a root of f(x) is equivalent to (x-α) divides f(x), homomorphisms and fixed points, Frobenius automorphism (mapping of x to x^q or x^p) for finite field and properties.
Here are the pictures of the black board.

18 Mar 2014
Lecture:
Algebraic integers; a algebraic over L; algebraic integers form a field; ideals; (V)R, examples; Z is a principal ideal domain = every ideal is principal, i.e. generated by a single element; equivalent statements to I=R; I+J: prime ideals; maximal ideals; examples; maximal ideals are prime ideals; over Z the converse almost holds, only exception is (0)Z; residue classes; residue classes are equivalence classes; R/I is a ring; first isomorphism theorem: φ homomorphism from ring R to ring S, then R/ker(φ) is isomorphic to Im(φ).
I left out that the intersection of ideals is an ideal, e.g. (2)Z, (3)Z, (4)Z are ideals in Z. Let I be their intersection. An element in I is divisible by 2, 3, and 4, so it is divisible by 12. In general, for (v1)Z, (v2)Z, ... , (vn)Z the intersection is generated by lcm(v1,v2,....vn).
Homework: Read and understand the proof of the first isomorphism theorem. Here are the pictures of the black board.

25 Mar 2014
Exercises and lecture replaced by training in information skills in MF 11+12.
Homework: Sheet 6

28 Mar 2014
Lecture given by Ruud Pellikaan:
Field has only trivial ideals; repeatition of domain, field, prime field, prime ideal, and maximal ideal; R/I is domain if I is a prime ideal; R/I is field if I is a maximal ideal; example: I=(X^2+1)R; Finite fields: repetition: characterisitic is prime, order is prime power; for |L|=q have (x^q-x) is the product of (x-a), where a runs through all of L; L* has q-1 elements; * notation is used for fields to denote the multiplicative group; construction of field with p^n elements using a monic, irreducible polynomial of degree n over Z/p; subfields of field with p^n elements are such that they have p^m elements, for m a divisor of n; the multiplicative group is cyclic (note that the reference should go to 6.5.10 and that the statement needs to hold for every divisor of the group order, not just the group order itself); minimal polynomial of an algebraic element; the minimal polynomial is unique and it is irreducible; the minimal polynomial of a divides every polynomial f which has f(a)=0.
Here are the pictures of the black board.

Exercise (in Aud 14):
Please prepare: 7.8.19, 7.8.20, 7.8.21, 7.8.22, 7.8.23 (hint, use the norm), 7.8.24, 7.8.27 (what happens when you replace 3 by any prime? by any number?), 7.8.28, 7.8.30.

04 Apr 2014
Notations for finite field as Fq; Frobenius automorphism; minimal polynomial of a has exactly all of a's conjugates as roots; an irreducible polynomial over Fp of degree n divides xpn-x; the latter equals the product of all monic, irreducible polynomials of degree dividing n; this gives a way to find irreducible polynomials; examples, there are (p^2-p)/2 irreducible polynomials of degree 2 over Fp; classification of finite fields.
Quick repetition of how to solve CRT.
Here are the pictures of the black board.

Tentamen

Het tentamen voor 2WF50 is gepland voor woensdag 16-04-2014 09:00-12:00; sluitingsdatum is de 30-03-2014. De herkansing is gepland voor woensdag 02-07-2014, 14:00-17:00; sluitingsdatum is de 15-06-2014.

Proeftentamen (van Algebra 2, 2WF10, was 3ECTS)

Tentamen van 2014: 2014-04-16.pdf.
Tentamen van 2011: 2011-11-10.pdf en 2012-01-27.pdf.
Tentamen van 2010: 2010-11-02-exam.pdf en 2011-01-21-exam.pdf.

Voor de laatste jaren was Andries Brouwer de docent voor Algebra 2. Hij was zo vriendschappelijk om me zijn oude examens te geven.