189-235A: Algebra 1

Blog

Week 1 (August 27 and 29). 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.

On Friday's lecture we discussed the integers, which are the prototypical example 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. In the coming week, we will be focusing on the ring of integers which is in many ways, the prototypical concrete example on which the abstract notion of ring is based.

Week 2 (Sept 3 and 5). This week we made the first steps in describing the arithmetic in Z. Last Friday, 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 (or rather, indicated how one might go about proving, if one were persistent enough) 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. This week we turned to the Euclidean division algorithm and the algorithm for the gcd, which are among the most important arithmetic facts about the integers.

This development of the integers also 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 Eyal Goren's 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.

Week 3 (Sept 8-12). This week we will follow rather closely the material in section 12 in the notes. We will study the notion of congruences, which are essential to some of the most important practical application of number theory, notably 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).

(c) Certain operations in the rings $\mathbb Z/n\mathbb Z$ -- notably, exponentiation -- can be calculated efficiently in practice, while their inverses are extremely hard to compute in a reasonable amount of time.

We will explain (a) and (b) more thoroughly in the coming weeks, and focus a bit more on (c) this week.

Week 4 (Sept 15-19).
This week we described a few applications of the finite rings introduced in the previous week, notably to the RSA public-key cryptosystem. We then turned our attention to Polynomial rings, which provide a basic template for generating new rings from old ones. After introducing the notion of the degree of a polynomial, and fussing a bit about what the correct degree should be for the $0$ polynomial (the answer was $-\infty$...) we specialised to the setting where our ring of coefficients was a field $F$, namely, we studied the properties of the polynomial ring $F[x]$. The overarching theme in this discussion is that the ring $F[x]$ then behaves, in this case, much like the ring ${\mathbb Z}$. This striking resonance stems from the fact that both classes of rings enjoy a Euclidean division algorithm with remainder, from which many other properties -- Euclidean algorithm for the gcd, Gauss's Lemma, and unique factorisation into irreducibles -- flow naturally.

Week 5 (Sept 22-26).
This week we continued with our development of the arithmetic of polynomial rings with coefficients in a field. After proving the analoge of the ``fundamental theorem of arithmetic" in this setting, we discussed features that were not apparent in our study of the integers and are specific to this new setting: most importantly, the notion of a root and the fact that the linear (hence irreducible) factors of a polynomial are in bijection with its roots. We used this to conclude that a non-zero polynomial has at most as many roots as its degree. We then discussed the problem of determining when elements of $F[x]$ are irreducible, and, more generally, of factoring them, a rich question whose exact solution depends very much on the nature of the underlying field of coefficients.

Week 6 (Sept 29-October 3).
This week we continued to discuss polynomials and their irreducibility, finishing our discussion of the Eisenstein criterion for irreduciblity over the rationals, and then moving on to polynomials with coefficients in a finite field, where we described a nice formula for calculating the number of distinct roots of a polynomial $f(x)$ with coefficients in the field of $p$ elements, by calculating the degree of $ \gcd(x^p-x,f(x)).$

Since the polynomial rings $F[x]$ display such a striking analogy with the ring $\mathbb Z$ of integers, it was natural to ask: ``what is the analogue of the passage from $\mathbb Z$ to $\mathbb Z/n\mathbb Z$, when $\mathbb Z$ is replaced by a polynomial ring $F[x]$? This leads to an algebraic construction that is of immense importance and corresonds to the process of ``adjoining to $F$ the root of a polynomial."

On Friday, October 3, our class will be cancelled. (We will make up for it later in the term, with a review session on the week of the midterm.) To satiate your Friday algebra craving, you are invited to watch the following two videos. The first, about the chinese remainder theorem, should be viewed as compulsory since it covers the Chinese Remainder Theorem, which is relevant to your Assignment 3. The second one, about the efficient factorisation of large integers, is there to satisfy your curiosity over the extent to which one can improve, in practice, over the naive ''trial division" method.