• Welcome
• CSP notes
• Teaching
• Research

Algebra II for Computer Scientists

Meetings Wednesdays from 17.30 in my office K313, Department of Algebra, 3rd floor, Sokolovská 83).

Assigned reading with weekly meetings and exercises. Final examination is oral (answering several questions about the material covered).

Exercises are mostly translated from David Stanovský's collection (in Czech).

Literature

• Louis Rowen: Algebra: Groups, Rings and Fields
• J.S.Milne's course notes
• RBJT Allenby: An Introduction to Abstract Algebra

Tentative schedule

• Week 1: Introductory meeting. Divisibility in integers and commutative rings. Recommended reading: Louis Rowen: Algebra: Groups, Rings and Fields for an introduction, parts of Chapter II of Serge Lang's Algebra, or p.104–106 of Rings, Fields and Groups, An Introduction to Abstract Algebra by RBJT Allenby. If all else fails, read Wikipedia...
• Week 2: Domains, ideals: Chapter 3 in Allenby's book
• Week 3: Euclidean domains, principal ideal domains, unique factorization domains: Section 3.7 in Allenby's book
• Week 4: Field of fractions, the domains Z[x] and Q[x,y], divisibility of polynomials, irreducible polynomials: Theorem 3.10.3 and Section 3.11 in Allenby
• Week 5: Applications in number theory: Section 3.8 in Allenby (with references to previous sections)
• Week 6: Roots of polynomials, multiplicity of roots: Section 1.11 in Allenby
• Week 7: Multiplicative groups in fields: Parts of weeks 7 and 18 of Louis Rowen's Algebra: Groups, Rings and Fields. Don't worry too much about Sylow groups in week 7.
• Week 8: Field extensions: Parts of Sections 4.2, 4.4, and def 4.5.6 in Allenby, Week 21 of Rowen's notes
• Week 9: Fundamental theorem of algebra, algebraic closure, Galois groups: Fundamental theorem of algebra is everwhere (you need to know what it says; we skip the proof), for algebraic closure see p. 180 of Allenby, for Galois groups see Wikipedia. There is not that much reading this time, so instead spend more time thinking about the concepts -- for example, how would you show that every field has an algebraic closure?
• Week 10: Finite fields: 4.5 in Allenby
• Week 11: Chinese remainder theorem: Section 2.3 in Frédérique Oggier's Algebraic Methods for the proof of the general CRT, see problems for some applications in number theory. Wikipedia article on Secret sharing using the Chinese remainder theorem
• Week 12: Gröbner bases: See Mike Stillman's tutorial on Gröbner bases and slides "Gröbner Bases and Applications" by Christopher Hillar We won't cover all the details, so it is OK to skip the more technical parts (in fact, you will need to skip things). The most important things are a) what is a Gröbner basis b) what can we do with it algebraically c) what interesting geometrical/combinatorial problems we can solve with it (see questions below to guide you).
• Week 13-14: Basics of universal algebra: Chapter 2, §1, 2, 5, 6, and definition of direct product of algebras from § 7 of of Burris, Sankappanavar: A Course in Universal Algebra.

Knowledge and skills (updated as we go)

• Week 1: Divisibility in integers and commutative rings
  • What are some examples of commutative rings?
  • What does it mean that a divides b in a commutative ring R?
  • Why "cancellative monoid" makes sense as an abstract description of divisibility in commutative rings?
  • What are integral domains and why are they great for divisibility questions?
  • How does divisibility play together with addition/subtraction?
  • Which pairs of integers are associated?
  • What is the greatest common divisor/least common multiple in a commutative ring. Why they need not exist?
  • What is the relationship between gcd(a,b) and lcd(a,b) (if they both exist)?
  • What are prime and irreducible elements in a commutative ring. Which inclusion between these element sets always holds?
  • What does the fundamental theorem of arithmetic say (without proof)?
  • Exercise set 1 (problem 4 edited to be more reasonable)
• Week 2: Domains, ideals
  • Why is the ring Z[sqrt(d)] a domain for d square free (nonzero) integer?
  • Why is the norm function useful when trying to understand domains Z[sqrt(d)]?
  • What is a (two-sided) ideal in a (commutative) ring?
  • Why is any ideal I that contains the element 1 boring?
  • What is a principal ideal? What is a principal ideal domain?
  • How to express the ideal generated by two elements r, s in a commutative ring R in a nice way?
  • Find an ideal in a commutative ring that is not principal.
  • What is Bezout's identity and why it follows from the fact that integers are a principal ideal domain?
  • How would you define multiplication of ideals (in commutative rings) so that it gives nice results for principal ideals?
  • Ideal turns out to be exactly the right object for creating congruences, ie. computing "modulo I". For example the ideal (6) of Z allows us to add and multiply modulo 6. Can you explain why properties of ideals (of commutative rings) are exactly the right properties that ensure computation "modulo I" makes sense?
  • Exercise set 2
• Week 3: Euclidean domains, principal ideal domains, unique factorization domains
  • What is the Euclidean norm?
  • Why is the ``unique'' factorization in unique factorization domains (UFD) defined in such a complicated way? That is, what is wrong with the following definition: A domain is UFD if for every a in this domain there exists exactly one sequence of irreducibles s1,...,sn such that a=s1*s2*...*sn
  • Why should we care about unique factorization?
  • What is the relationship between Euclidean domains, principad ideal domains and UFDs? What does this mean for Z, Q, Q[x], and Z[x]?
  • Exercise set 3
• Week 4:Field of fractions, the domains Z[x] and Q[x,y], divisibility of polynomials, irreducible polynomials
  • The domain Q[x] is not a field because it does not have enough inverse elements. How can we extend Q[x] into a field?
  • Let f be a polynomial from Z[x]. If we are thinking about divisibility, why is it safe to assume that f is primitive?
  • Make sure you understand the proof that if f,g are primitive polynomials from Z[x] (or any U[x] where U is a UFD) then fg is also a primitive polynomial.
  • When proving that Z[x] is a UFD, we look at Q which is the field of fractions of Z. When proving that U[x] is a UFD, we look at the field of fractions of U. Why?
  • When showing that Q[x,y] is a UFD, why can't we just use the same reasoning as for Q[x]?
  • Exercise set 4
• Week 5: Applications in number theory
  • Why should we care about Z[sqrt(d)] when solving Diophantine equations over Z?
  • If we are given a Diophantine equation p(x,y)=z^3, which Z[sqrt(d)] is it a good idea to examine?
  • What automorphisms useful for solving Diophantine equations does Z[sqrt(d)] have?
  • Exercise set 5
• Week 6: Roots of polynomials, multiplicity of roots
  • In Allenby's book, quite a lot of effort is spent separating two meanings of a polynomial: A polynomial is a formal expression in, say, Q[x], but it is also a function, say, Q->Q. Why should we care about the difference between these concepts?
  • Continuing from the previous point, can you find two different polynomials over Z_2 that define the same function Z_2->Z_2?
  • Let's say we send each polynomial p in Q[x] to p(1), its value for x=1. What nice properties does this mapping have?
  • Try to prove on your own the theorem that if a is a root of a polynomial p, ie. p(a)=0, then x-a divides p(x).
  • What is strange about roots of the zero polynomial?
  • What can you say about roots of irreducible polynomials? Why does it matter which field take our polynomials over?
  • How can we tell if a polynomial q over a field of characteristic 0 has roots of multiplicity 2 or more?
  • Exercise set 6
• Week 7: Multiplicative groups in fields
  • What is the definition of the order of an element in a group? What about exponent of a group?
  • If an Abelian group has exponent 54, how do we know that it contains an element of order 54?
  • What is the exponent of the symmetric group on 3 elements?
  • Is it true that the multiplicative group of any field is cyclic?
  • Can you prove Wilson's theorem using the fact that the multiplicative group of Z_p is cyclic?
  • Exercise set 7
• Week 8: Field extensions
  • What do we mean when we say that complex numbers are a vector space over the real numbers?
  • In what sense is Q[sqrt(2)] a "simpler" extension of Q than R?
  • How do field extensions of complex numbers look like?
  • (From Allenby's book): Say we want to extend Q so that both x^2+1 and x^2+x+1 split into linear factors. Can we just take I the ideal generated by x^2+1 and x^2+x+1 in Q[x] and take Q[x]/I?
  • Let c be a complex number. What is the difference between Q[c] and Q(c)?
  • What is a rupture field of a polynomial?
  • What is a splitting field of a polynomial?
  • Why is it not obvious that a splitting field of a fixed polynomial p(x) over, say, Q is unique up to isomorphism?
  • Exercise set 8
• Week 9: Fundamental theorem of algebra, algebraic closure, Galois groups
  • What does the fundamental theorem of algebra say?
  • Use the fund. theorem of algebra to figure out how do irreducible polynomials over C and R look like.
  • Constructing an algebraic closure takes a lot of patience, but it is not hard -- you basically just have to keep adding roots of polynomials until you run out of polynomials (a bit of set theory is needed to make sure this works). Why is it not obvious that all algebraic closures of a given field should be isomorphic? (We will skip the proof of this; it is not hard, but it is tedious and techical.)
  • What is the Galois group of (the splitting field of) x^2+1 over R?
  • Exercise set 9
• Week 10: Finite fields
  • Why is there no field of order (=size) 6?
  • How would you prove on your own that all fieds of order 9 are isomorphic?
  • Is GF(4) isomorphic to a subfield of GF(8)?
  • Exercise set 10
• Week 11: Chinese remainder theorem (CRT)
  • How does the CRT for integers follow from the general CRT?
  • What does CRT say for polynomials over, say, Q when the ideals are generated by linear polynomials x-a?
  • Why is CRT useful for solving systems of equations?
  • How could one use the CRT to do arithmetic in the ring R using smaller rings R/I?
  • Exercise set 11
• Week 12: Gröbner bases
  • What is the ideal membership problem?
  • What do we mean when we say that an ideal has a finite basis?
  • Is the basis of an ideal unique? Does it have a well defined size like in linear algebra?
  • If U is a subset of C^n, what nice propertied does the set of all complex polynomials that are zero in U have?
  • What do the two important Gröbner basis algorithms input and output?
  • How can one use Gröbner bases to (maybe) solve Euclidean geometry problems?
  • How can one use Gröbner bases to (maybe) solve 3-coloring of graphs?
  • Exercise set 12
• Weeks 13–14: Basics of universal algebra (algebras, congruences, factoralgebras, homomorphisms)
  • Is a group an example of an algebra? How about a ring? How about a graph?
  • What problem do we run into when we trying to view a field as an algebra with binary operations of addition a multiplication, two nullary operations (constants) 0 and 1, and unary opeartions of multiplicative and additive inverse?
  • What are subalgebras of a group?
  • Let A be an algebra on at least 2 elements. What are the two (trivial) congruences that every such algebra has?
  • Let G be a group. There is a bijective correspondence between congruences of G and normal subgroups of G. How does it work?
  • Let R be a (not necessarily commutative) ring (with a unit). What do congruences of R correspond to?
  • How do the three isomorphism theorems from the book by Burris and Sankappanavar correspond to the three isomorphism theorems for rings (or groups, depending on which ones you had in Algebra I)?
  • Exercise set 13