189-235A: Algebra 1

Blog

Week 1 (Sept 4 and 6). This week I gave a brief motivational overview of Abstract Algebra. One of the historical origins of the subject can be traced to the algebraic solution of the cubic equation discovered by the mathematicians of the 16th Century Italian Renaissance Niccolo Tartaglia, Scipione del Ferro and Girolamo Cardano. For a delightful account of the dramatic story surrounding this discovery, see Chapter 6 of

Journey through genius: the great theorems of mathematics by William Dunham.

Cardano's solution to the cubic was a turning point because it went beyond what the ancients had been able to achieve, suggesting that there might be a lot more to mathematics than was contained in Archimedes and Euclid. It also created a compelling case for the introduction and use of complex numbers. Attempts by mathematicians and philosophers to come to terms with the ``imaginary quantities" in Cardano's formula for the (very real, both in a mathematical and ontological sense) solutions of the cubic were an important impetus for the birth of modern abstract algebra.

Friday's lecture concluded with my beginning to write down the definition of an abstract ring (I didn't get to the end of it, and will conclude at the start of Monday's lecture.) This is to give you a feeling for the kind of general abstract structure we are aiming to study. But starting from week 2, we will be backtracking somewhat, and about very special instances of this concept, starting with the ring of integers which are, in many ways, the prototypical concrete example on which the abstract notion of ring is based.

Week 2 (Sept 9 -13). This week we made the first steps in describing the arithmetic in Z, following loosely sections 8 and 9 of the on-line notes. But our treatment was a bit different from the one given in the on-line notes. For instance on Monday, we introduced the set of positive integers as a set equipped with a zero element and a successor function, satisfying the axiom of induction. We then gave an inductive definition of addition and multiplication, and proved that the resulting operations satisfy the familiar rules (associativity, commutatitvity, distributivity of multiplication over addition...) The resulting (slightly pedantic) proofs are a good illustration of the general strategy of proof by induction: for more on that, see also Section 2.3. of the on-line notes. On Wednesday and Friday we turned to the Euclidean division algorithm and the algorithm for the gcd, following closely sections 8 and 9 of the notes.

This development of the integers served partly as a pretext to cover some of the basic "mathematical vocabulary", concerning proof, sets, functions, complex numbers that will be used throughout the course. This is the material of Part I of the on-line notes, which I am asking you to cover as independent reading. For some of you this might be a leisurely review; on the other side of the spectrum, if you have never been exposed to this material before, you may have to spend a bit more time reading and absorbing the material in Part 1, preferably in advance of the lectures. The sooner you are comfortable with the language, point of view, and concept of proof, the easier it will be to follow the lectures and do the assignments.

Organisational remark. My colleagues in the mathematics department know that some of you have not yet been able to register for the course. With high probability, the problem will sort itself out by the drop-add period if, as is often the case, sufficiently many students decide to drop 235A in favor of other classes that they might be trying out at the same time. If the course is still overbooked by then, you should go see Angela White on the 10th floor of Burnside. I have been assured that everything will be done so that no one who needs the course for her or his program is turned away because of limits on registration.

Week 3 (Sept 16-20).
Organisational remarks: This week I will be out of town on Thursday and Friday, and for this reason I am rescheduling my office hours exceptionally to Wednesday from 2:00-4:30.
On Friday, Antonio Lei will be filling in for me.

The first assignment . Note that your first assignment is due on Monday of next week. You can either hand it in during class or drop it in the assignment slot on the 10th floor of Burnside Hall, before 2:00 PM. I aim to return these assignments to you, like clockwork, on the Monday of the following week. Because of the number of students enrolled in the class, an army of TA's and graders will have to coordinate their work with a military precision to rival the planning that went into the invasion of the beaches of Normandy on D-day. For this reason, among others, absolutely no late assignments will be accepted. If you are unable to complete your work by the 2:00 PM deadline, just hand in what you've written up, and continue to think about the questions you haven't had time to complete. You are also encouraged to discuss them, of course, with your classmates, with me, or with any of the TA's. But such exchanges can only be profitable if you've spent a healthy amount of time before-hand thinking about the questions on your own.
Please remember to clearly indicate your name and the name/number of the course for which you are returning the assignment.

This week we will follow rather closely the material in sections 8-10 in the notes, culminating in the proof of the fundamental theorem of arithmetic (Section 10 of the notes). This theorem, which asserts that every integers can be expressed uniquely as a product of primes (raised eventually to certain powers) is the most fundamental fact about the multiplicative structure of the integers. There is a good reason why it is called the fundamental theorem of arithmetic, and it is also, in some sense, one of the most fundamental of all mathematical truths. It is also at the origins of the most important practical application of number theory, to public key cryptography. This application is based on the facts that

(a) it is not so hard to produce large primes, of 100 digits or so, on a computer (or a cell phone, for that matter), and

(b) given a product pq of two such primes p and q, it is virtually impossible to figure out what the primes p and q are, in any reasonably amount of time, even with a battery of dedicated super computers working on the problem in parallel for months (or years, or centuries).

We will explain (a) and (b) more thoroughly in the coming weeks.

Time permitting, on Friday we will also embark on the first steps in our discussion of congruences (Section 12 and part of Section 13.)

Week 4 (Sept 23-27).

On Friday of last week, Antonio introduced you to the notion of congruences, which turns out to be a very powerful piece of notation, and will furnish us with our first interesting example, beyond the prototypical one of the integers, of a ring. This week will be devoted to various topics related to congruences: notably the fact that Z/nZ is a ring, and that it is even a field if and only if n is prime. We use this to prove Fermat's little theorem, following up with a general discussion of linear congruence equations. Applications of congruences to the RSA cryptosystem will be discussed, as well as some discussion of the problem of primality testing.

Have you completely absorbed the language of set theory? You probably have if you laugh at the following joke.

Week 5 (Sept 30-Oct 4).

This week, we will begin by wrapping up our discussion of congruences by discussing a few further topics, such as Wilson's theorem, and (more importantly) the Chinese remainder theorem and its applications to efficient parallel computing.

We will then move on to the theory of rings of polynomials with coefficients in a field, following more or less the development in Chapter 4 of Eyal Goren's notes.

Office hours: This week, I again have to be absent on Friday afternoon after the lecture, so my office hours will be rescheduled to Wednesday, from 12:30-3:00.

Week 6 (Oct 7-11).

The week's lectures are devoted to rings of polynomials with coefficients in a field F, following more or less the development in Part 4 of Eyal Goren's notes. Highlights include the proof of the unique factorisation theorem which asserts that every polynomial in F[x] factors uniquely into a product of irreducible polynomials. This has strong implications, notably, on the number of distinct roots that a polynomial in F[x] can have.

A theme which emerges from the unique factorisation theorem (and from its proof, which is basically the same as the one we gave for the integers) is the strong analogy that exists between the rings Z and the polyomial rings F[x]. Seeking to develop this analogy even furhter, we introduce the notion of congruence modulo a polynomial and show that it enjoys all the same formal properties of the congruences modulo an integer which were discussed in previous weeks. In the same way that the study of congruences modulo an integer n led us to a new ring, the ring Z/nZ of residue classes modulo n, we are led to construct the rings F[x]/(f(x)) of polynomials modulo a given polynomial f(x). The remainder of the week (Wednesday and Friday) is devoted to the study of these so-called ``quotient rings", which are used, notably, to construct a finite field with 8 elemens, and related algebraic structures.

Time permitting, we will also discuss the factorisation of polynomials over finite fields, a topic that will also be taken up partly in assignment 3.

Remark on the midterm. This is our last full week of lectures before the midterm, which will be on the Wednesday of the following week. The midterm will be based on all the material that we've covered so far, including the material of this week's lectures. (But not the material of Monday, which may be devoted to some review of previous material.)

Week 7 (Oct 14-18).
This week was a short one, with no lecture on Monday because of the Thanksgiving holiday, and the midterm exam on Wednesday. In Friday's lecture I gave corrections for the midterm exam, and we had time in the second half to prove a new, and important, theorem about the field F':=F[x]/f(x) where f(x) is an irreducible polynomial. Namely, we showed that this new field contains the field F as a subfield in a natural way, and that it also contains a root of the polynomial f(x), viewed as a polynomial in F'[x] via the natural inclusion of F into F'. This general procedure for creating new rings (or fields) from existing ones by a process of "adjunction of roots" is an important one in modern abstract algebra--for instance it demystifies the complex numbers and the "imaginary quantities", like the square root of -1, whose "existence" was the object of intense philosophical debate until well into the 17th century.

Week 8 (Oct 21-25).
Having seen the striking list of formal analogies between our study of the integers and the set of polynomials with coefficients in a field, we are now ready and motivated to move to the next level of abstraction and discuss general rings, of which the integers, and the ring F[x] of polynomials, are two prototypical examples.

This week was largely devoted to covering Part 5 of Eyal Goren's notes. After briefly recalling the general ring axioms (which have already been seen before, of course) and some of their basic consequences, we introduce the basic notion of an ideal in a ring, an all-important concept which is meant to make up for the fact that the general notion of the gcd is not as well-behaved in a general ring as it is in Z and F[x].

We proved the theorem that every ideal in the ring Z of integers or in the ring F[x] of polynomials over a field is always principal. We then saw examples of ideals that are not principal, for instance in the ring Z[x] of polynomials with integer coefficients, or in the ring F[x,y] of polynomials in two variables over a field F.

Then, on Friday, I discussed the notion of products of ideals in rings like Z[sqrt(-5)], and explained how the non-unique factorisation of the number 6 into irreducible elements turned into an ostensibly unique factorisation of the principal ideal generated by 6, into four ideals. Very little was proved in this lecture, but this calculation gives a glimpse of one of the historical motivations of the introduction of ideals, by Dedekind. The terminology "ideal" mirrors Dedekind's notion of an "ideal number"---these are extra elements that one has to add to the set of irreducible elements of the ring Z[sqrt(-5)] under multiplication, in order to salvage a statement like unique factorisation (which now becomes unique factorisation into ideals, and not irreducible elemments.)

Week 9 (Oct 28 - Nov 1).
On Monday we introduced the notion of the quotient of a ring by an ideal and worked out a few examples. The notion of quotient (of one algebraic structure by another) represents a pinnacle of abstraction, as far as what you will see in this course. The best way to become familiar and comfortable with the notion is to work out many examples. In fact, you have already worked with quotients before in this class (a bit like Monsieur Jourdain in Molière's "Le Bourgeois Gentilhomme", who discovered he had been speaking in prose without ever being aware of it) when you performed calculations with the congruence rings Z/nZ, and the rings F[x]/(f(x)).

On Wednesday we discussed homomorphisms of rings, and proved that the kernel of any homomorphism is an ideal in the domain ring. This set the stage for the fundamental isomorphism theorem for rings to be covered on Friday, which establishes a dictionary between (surjective) homomorphisms having a given ring R as its domain, and the set of ideals in R.

Week 10 (Nov 4 - Nov 8).
This week we embarked on a new topic, namely, the theory of groups. These new mathematical structures are defined by a much simpler set of axioms than rings: a group is just a set endowed with a single binary operation satisfying the associative law, as well as possessing a (unique) neutral element for this operation, relative to which every element posseses an inverse. Groups turn out to be the ideal structure with which to describe and model the abstract notion of symmetry, which is pervasive in mathematics as well as in physics and computer science.

The most important examples of groups which we discussed were
• the groups GL_n(F) of invertible n times n matrices with entries in a field F, the group operation being the usual matrix multiplication, and the identity element being the usual identity matrix.
• the permutation group S_n consisting of all bijective functions from the set {1,...,n} to itself, the group operation being the composition of functions. We introduced a powerful, versatile notation to describe elements of S_n, the so-called cycle notation, and explained how elements in S_n can be composed with each other rather efficiently in terms of this notation. Other advantages of the cycle notation is that it becomes easy to determine at a glance certain basic invariants of a permutation, such as its order: it is simply the least common multiple of the lengths of the disjoint cycles describing the permutation.
• the dihedral group D₈ is the group of rigid motions preserving a square. It consists of the four rotations 1, r, r², and r³, and the four reflections V, H, D₁ and D about the horizonal, vertical, an digaonal axes of symmetry of the square.

We then described the notion of a homomorphism from one group to another, and discussed the important case of a homomorphism from a finite group G to a permutation group. We proved Cayley's Theorem that every finite group admits an injective homomorphism to a group S_n, where n can be taken to be the cardinality of G. The idea of the proof was to associate to each element of G a bijection from G to itself, arising from left multiplication by that element.

Further examples of homomorphisms were given, for instance, various examples of homomorphisms from D₈ obtained by considering the effect of a rigid motion of the square on various naturally occuring structures inside the square (its vertices, sides, axes of symmetry, etc.)

Week 11 (Nov 11 - Nov 15).
This week we discussed the notion of cosets of a group H in a group G. We proved that a group G can always be written as a disjoint union of its cosets, which all have the same cardinality as that of H. As a result, we deduced Lagrange's theorem that, if G is a finite group and H is a subgroup of G, the cardinality of the latter must divide that of the former.

We then discussed the structure of the set G/H of all cosets for H in G, and asked when the ``natural" rule aH . bH = (ab) H gives rise to a well-defined operation on the set G/H. When it is well-defined, this rule gives rise to a composition law on G/H satisfying all the axioms of a group, and one says that G/H ```inherits" a group structure from the group structure on G. We saw that the answer to the question "When is G/H a group?" is "Sometimes, but not always!". More precisely, it is necessary and sufficient that H be a normal subgroup of G, i.e., that it be stable under conjugation by arbitrary elements of G. This means that if h belongs to H, and g is an arbitrary element of G, then h^g = g^-1 h g must belong to H as well.

This led to a study of the all-important nottion of the conjugacy relation in a group, and to the notion of conjugacy class, which is key to classifying the possible normal subgroups of a group.

Week 12 (Nov 18 - Nov 22).
On Monday we continued briefly with our discussion of conjugacy classes, normal subgroups, and their associated quotients, by describing a few illustrative examples, namely,

• the dihedral group of order 8;
• the symmetric group S₄ and its normal subgroup of order 4.
We stated and proved the first isomorphism theorem for groups, and explained how it could be use to identify the structure of G/H in a few specific examples.

On Wednesday and Friday, I was out of town, and Antonio Lei filled in for me. His lectures followed sections 30-31 of the online notes, and were devoted to the all-important notion of an action of a group on a set, which is just another way of talking about permutation representations (homomorphisms from an abstract group to a permutation group) that were introduced already in week 10. In that week we saw that a finite group G can always be realised as a subgroup of a permutation group (Cayley's theorem) but one can then ask ``In how many fundamentally distinct ways can this be done?" We gave what amounts to a complete classification of the sets which can be equipped with a finite group action, in terms of the notion of cosets.

Week 13 (Nov 25 - Nov 29).
This week will be devoted to covering a few topics in group theory that are left in the notes, including sections 32, 33.4, and 33.5.

Week 14 (Dec 2 - Dec 3).
This week will consist of two consecutive Mondays from the point of view of the McGill calendar, and hence we will have two hours of lecture, but on Monday and Tuesday rather than on Monday and Wednesday!
These two lectures will be devoted to review of the material. I strongly advise you to work out a lot of problems from the posted "practice finals" in the "assignments" web site, and to come to these two lectures armed with precise questions! You will get a lot more out of listening to solutions to problems you have always spent time struggling with yourself (even if with only partial success.)

In addition, there will be extra review sessions by the TA's that week, with the following schedule:

Monday, December 2, 3:30-5:00. Dylan Atwell-Duval, in BH 1018.

Tuesday, December 3, 12:30-2:30. Henri Darmon, BH1111 or 10th floor lounge of Burnside Hall.
Tuesday, December 3, 4:00-6:00. Bahare Mirza, in Burnside Hall lounge (10th floor.)

Wednesday, December 4, 3:30-5:30. Henri Darmon, in Burnside Hall lounge (10th floor).