Spring 2018. Math 113, section 1 (ccn 26640):
Introduction to Abstract Algebra
Instructor: Alexander Givental
Lectures: MWF 8-9, room: 289 Cory
Office hours: W 2-4 pm, in 701 Evans
Textbook: none required, but these lecture notes by Alexander Paulin will be used as a main reference.
Prerequisites: Math 54 or any other course with equivalent linear algebra content.
Homework: will be posted to this website, and due on Fridays of the net week.
Course description:
I once taught an overflow section of math 113, where students came from different sections with already purchased different textbooks. Thus, I couldn't follow any particular one, and so I began to manage the corurse material, including recommended reading, and hw, thorugh website. It turned out I liked this format, and I intend to do the same this semester. Alexander Paulin generously allowed us to use his course notes, which will be extremely useful at least as a concise and well-written reference resource. We probably won't follow the notes too closely, as the plan is to dedicate the class time and hw to project-like exploration of mportant and non-trivilal examples. The content of the course will be mostly standard: groups, rings, and fields, perhaps with a brief deviation toward algebraic geometry at the end.
GSI: Tao Su, taosu@math.berkeley.edu , for office hours, check his website
Grading policy: hw 40%, quizzes 20%, final 40%
HW1, due by Fr, Jan. 26: Reading: pages 1-11 from Paulin. Solve:
1. Exercise from Paulin's text on bottom of page 5.
2. Find the remainder of the division of a=111.....111 (100 ones) by
b=1111111 (7 ones).
3. Practice the Euclidean algorithm to find integers x,y such that 95x+432y=1
4. Prove that 300^{3000}-1 (300 to the power 3000, minus 1) is divisible by 1001.
5. Compute 2^{2018} modulo 111.
HW2 (due by Fr, Feb. 2):
The purpose of this homework is
to explore with bare hands several examples of groups (which seem to have different nature but at a closer look seem somewhat similar), and the notion of
isomorphism.
Read: Pages 12-13 from Paulin.
Solve:
1. Compare the following groups, identify all elementns in each
of them (the total number called the order of the group is 4 in all
these cases), study the operation (you may write the whole table of
multiplication, if you think it helps) to find out
which of the groups are isomorphic to each other and which are not.
A. The group \Z_10^* of multiplicatively invertible remainders modulo 10
(it consists of 1,-1,3, -3);
the operation is multiplication mod 10, of course
B. \Z_8^* (the same, but modulo 8)
C. \Z_2^2, the group of 2-dimensional vectors (a,b), where a,b are remainders
modulo 2 (i.e 0 or 1, as in computer science) with the operation of
componentwise addition modulo 2.
D. Complex numbers 1, -1, i, -i with respect to multiplication of complex
numbers
E. The group of all symmetries of a rectangle (i.e. of all rigid
motions of the plane which preserve the rectangle), with the operation of
composition.
F. In the group S_4 of all permutations of {1,2,3,4}, consider the subgroup
(denoted K_4 and called the Klein subgroup) of all those permutations which
preserve each of the three partitions of {1,2,3,4} into pairs: {1,2 | 3,4}
{1,3 | 2,4} , and {1,4 | 2,3} (I admit, this description is convoluted, but
the very existence of this subgroup is a remarkable fact of Nature
with serious consequences, and is worth studying).
G. In the group of all rotations of the unit cube |x|,|y|,|z|<1
(operation - composition of rotations), consider the subgroup of all those
rotations which
preserve each of the three coordinate axes. (In other words, every rotation of
the cube somehow permutes the axes, but for some non-trivial rotations this
pernutation is trivial; they, together with the identity, form our group.)
2. Find out which of the following groups are isomorphic to each other,
and which are not:
H. The group D_3 of all rotations of the 3-space preserving the regular
triangular prysm (by definition, its bases are
parallel equilateral triangles, and the side faces are rectangles perpendicular
to the bases);
I. GL_2(\Z_2) - the group of 2x2 matrices whose entries are 0 or 1 (added and
multiplied modulo 2), equipped with the operation of matrix multiplication,
and invertible with respect to this operation (GL stands for "general linear")
J. S_3 - the group of permutations of {1,2,3}.
K. The group with two generators a,b and the relations a^2=e, b^2=e, (ab)^3=e.
Well, this a novel way to describe a group, so let's discuss it. Consider the
alphabet consisting of two letters a and b. Elements of the group are
represented by words written in this alphabet. One actually needs to add the
letters a^{-1} and b^{-1}, but in my example, a^2=b^2=e, i.e. a and b are their
own inverses. The operation is concatenation of words. The empty word
represent the identity element e. The important thing is
that two words represent the same element if they are obtained from each other
by cancellations that use the given relations or any other relations that can
be derived from them and the axioms of a group. For example,
(aba)(aba)=abaaba=abba=aa=e; (babab)(aba)=b(ababab)a=ba because in my group
not only aa=bb=e, but also ababab=e; multiplying ababab=e by bab on the right,
we find that aba=bab.
HW3, due Fr, Feb. 9:
The goal of this homework is to get a good grip
on the notions of a subgroup, cyclic group, the order of a group (or of an element), isomorphism, as well
as permutation groups, by examining in detail one example: The group S_4 of all permutations on the set {1,2,3,4}
of 4 symbols.
(a) List all elements of the group (there should be 24). For each of them, find the number of
elements in the cyclic subgroup generated by it (Control test: the numbers can only be divisors of 24).
(b) Which elements generate the same cyclic subgroup? How many distinct cyclic subgroups are there
of each order?
(c) Identify non-cyclic subgroups; I am aware of four
such subgroup of order 4, four of order 6, three of order 8, and
one of order 12, not counting the whole group. Show that such subgroups of the same order are isomorphic to each other.
(d) Compare the numbers of subgroups of each order with those we found in class in the group G of rotations of the cube.
(The numbers should agree.) Invent an isomorphism between S_4 and G, and find out how exactly those non-cyclic subgroups of
S_4 are realized under your isomorphism as subgroups in the group of rotation of the cube.
HW4, due Fr., Feb. 16: For reference, use the material of Sections 3.2, and 3.8 of Paulin's notes. Warning: what is called in the notes right coset is usually called left coset, and vice versa. We will stick to the usual terminology. Solve:
1. Prove that all groups of order < 6 are abelian (=commutative).
2. In the group of all symmetries of the regular triangle, show that every subgroup other than the whole group is cyclic. Pick a cyclic subgroup of order 2, write out explicitly all left cosets, all right cosets, and check whether they coincide. Do the same for the cyclic subgroup of order 3.
3. In the group G of rotations of the cube |x|,|y|,|z|< or = 1,
let H be the subgroup of all rotations which fix vertex (1,1,1).
Identify the set of left cosets of H with the set of vertices. Namely, show
that each left coset of H consists of exactly those rotations which transform (1,1,1) to a particular vertex of the cube.
4. Examine 4 non-cyclic subgroups of order 4 in the group G of rotations of the cube, and find out which of them are normal (i.e. have left cosets identical to the right cosets) and which are not.
5. Prove that if the number of left cosets of a subgroup H in a (possibly infinite) group G is finite, then the number of right cosets is also finite and equal to the number of left cosets. (This number is called the index of H in G.) Show that any subgroup of index 2 is normal.
HW5, due Fr., Feb. 23: Read Section 3.8 of Paulin's notes. Solve:
1. Show that the special linear group SL_n(R) of real nxn-matrices with determinant 1 is a normal subgroup in the general linear group GL_n(R) of all invertible real nxn-matices, and identify the quotient group with GL_1(R).
2. Show that in the orthogonal group O_n of orthogonal nxn-matrices, the special orthogonal group SO_n of orthogonal nxn-matrices matrics with determinant 1 is a normal subgroup, and identify the quotient group with O_1.
3. Consider the set of n! square matrices of size n whose columns are obtained as permutations of the colums of the identity matrix I_n. Show that these matrixes form a group with respect to matrix multiplication, and identify this group with the group S_n of permutations of n symbols. Show that the subgroup A_n in S_n formed by the matrices with determinant 1 is a normal subgroup (it is called the alternating group ). Find the order of A_n and describe the quotient group S_n/A_n.
4. Show that in the dihedral group D_n of symmetries of a regular n-gon (D_n consists of 2n elements: n rotations and n reflections) the rotations form a normal subgroup, and describe the quotient group.
5. Is O_n (resp. SO_n) normal in GL_n(R) (resp. in SL_n(R))?
Here is a growing list of tautological problems about groups
HW6, due Fri., Mar. 2: Read Paulin's sections 3.4 - 3.5. Solve:
1. Consider the natural action of GL_3(R) on R^3 by linear transformations, and describe the orbit of each vector and the stabilizer of the vector (1,0,0).
2. The same for the natural action of the orthogonal group O_3 on the Euclidean space R^3 equipped with the standard dot-product.
3. For an arbitrary action of a group G on a set X, prove that stabilizers of different elements of the same orbit are conjugated subgroups in G.
4. In a group G, let Z_g denotes the subgroup consisting of all those elements which commute with g
(it is called the centralizer of g). Prove that the number of classes of conjugate elements in a finite group G is equal to
the average size of the centralizer: \sum_g |Z_g| /|G|. Hint: Apply Cauchy's counting principle to the action of G on itself by conjugations.
5. Compute the number of different necklaces formed by 17 black or white beads of the same spherical chape and size
threaded on a circular thread. (The necklaces which can be obtained from each other by rotating and/or flipping them in space
are considered the same.)
Quiz 3: Group actions, Wed., March 7 (5 min)
HW7, due Fri, Mar. 9: Read Paulin's notes, section 3.6 (about symmetric groups). In addition, read elsewhere about the following key fact on permutation groups (not found in Paulin's notes, I think): For n>4, the alternating group A_n is simple, i.e. does not contain any non-trivial normal subgroup; consequently, the only non-trivial normal subgroup in S_n is A_n, with the only exception of n=4, when the Klein subgroup K_4\subset A_4 \subset S_4 is also normal in S_4.
Solve:
1. Let g be a permutation on (1,2,...,n) choosen randomly with the probability 1/n! from n! permutations. What is the expected nummber of fixed points of g? (Recall that the expected number equals 0 p_0+1p_1+2p_2+...+np_n, where p_k is the probability of the permutation g to have k fixed points.)
2. Show that if the same permutation is written (in two different ways) as the composition of k transpositions and of l transpositions, then the parity of k and l must be the same. Give an example where k and l differ.
3. Find the parity of the permutation transforming logarithm into algorithm
4. In S_n, show that the conjugacy class of a permutation g with l_1 cycles of length 1, l_2 cycles of lengths 2, l_3 cycles of length 3, etc. consists of
n!/(l_1! l_2! l_3!...)(1^{l_1} 2^{l_2} 3^{l_3} ...) permutations. Find the order of the centralizer of g, and using the result, describe explicitly all those permutations which commute with g.
5. In S_n, consider the permutation s=(1,2,3) (cyclicly permutting these three elements of the set {1,2,...,n}). Find all even permutations which commute with s, and derive that all 3-cycles form a single conjugacy class in the alternating group A_n (denoted Alt_n in Paulin's notes).
HW8, due Fr., Mar. 16: Start reading sections 3.9-3.11 of Paulin's notes. Unrelated to that:
In a group G, consider the subset K of all commutators aba^{-1}b^{-1}, where a,b are elements of G.
Let C be the intersection of all subgroups containing K. (In other words, it is the smallest subgroup containing K.)
1. Prove that C is normal, and that the quotient group G/C is abelian.
2. Prove that any homomorphism of G to an abelian group contains C in its kernel. Derive from this that everey homomorphism
to an abelian group A can be represented as composition G -> G/C -> A, where the first arrow is the standard projection
to the quotient group.
3. Find the commutator subgroup in S_4.
4. Compute the commutator subgroup in the dihedral group D_n (consisting of 2n symmetries of the regular n-gon: n rotations and n reflections).
5 (related to section 3.9 of Paulin's notes). Show that the direct sum of the three cyclic groups: \Z_7, \Z_11, and \Z_{13} is cyclic, and find a generator of it.
On Wednesday, March 21, we will have Quiz 4 on the theory of permutation groups S_n.
HW9, due Fr., Mar. 23: Read 3.10-3.11.
1. Show that any abelian group of order 1001 is cyclic.
2. Classify up to isomorphism all abelian groups of order 16.
3. Find the place of \Z^*_32 (the multiplicative group of odd
remainders modulo 32) in your classification.
4. Find the place of \Z^*_{17} (the multiplicative group of non-zero remainders modulo 17) in your classification.
5. Prove that any subgroup H in \Z^2 (the integer lattice in the plane \R^2) is isomorphic to \Z^0, \Z^1, or \Z^2. ( Warning: A priori it is not obvious at all that H is finitely generated.)
We begin "Rings and Fields" part of the course. Our main topics include:
(a) Rings, ring homomorphisms, ideals, and the Epimorphism theorem for rings.
(b) Embeddings of rings into fields; the field of fractions of an integral domain; minimal fields and chracteristic.
(c) Divisibility and factorization: Euclidean rings, PIDs, UFDs; Gaussian integers, irreducibles in \Q[x].
(d) Elements of the field extension theory; applications to impossibility results for some geometric constructions.
HW10, due Fr., Apr. 6: Read Sections 4.1-4.4 of Paulin's notes.
1. Describe all units in the following rings: (a) \Z/n\Z, (b) \C[x] (polynomials in one indeterminate x with complex coefficients), (c) \Z[x]/(x^2+1) (Gaussian integers), (d) the ring M_2(\Z_2) of 2x2-matrices with entries from \Z_2={0,1}, the ring of integers mod 2, (e) the ring \H of complex 2x2-matrices whose top row is (z, w) and the bottom row is (-w*, z*), where z and w are arbitrary complex numbers, and * denotes the complex conjugation (verify that such matrices do form a ring!)
2. Find out which of the following rings (obtained by taking the quotient of the ring of polynomials in two indetermiantes x,y with the sepcified coefficients, by the ideal generated by one specified polynomial) have zero divisors: (a) \R[x,y]/(xy), (b) \R[x,y]/(x^2+y^2), (c) \C[x,y]/(x^2+y^2), (d) \Z_5 [x,y]/(x^2+y^2), (e) \C[x,y]/(x^2+y^2-1) where \R stands for "reals", \C for "complex", and \Z_5 = \Z/5\Z for "integers modulo 5".
HW11, due Fr., Apr. 13: We will discuss the construction of the ield of fractions of an integral domain on Monday, and the dividibility theory in Euclidean rings on Wednesday. Read the respective material from sections 4.5 - 4.9 in Chapter 4 of Paulin's notes. Solve:
1. In the construction of the field of fractions of an integral domain,verify the distributive law.
2. Let R be an integral domain, and a,b are two of its elements. Suppose a^m=b^m and a^n=b^n for some relatively prime positive integers m and n. Prove that a=b.
3. Let \Z[\zeta] be the set of complex numbers of the form a+b\zeta, where \zeta = (-1+i\sqrt{3})/2, and a,b are arbitrary integers. Sketch the set on the complex plane, and prove that it is a Euclidean ring.
4. Try the same argument for the ring \Z[\sqrt{-3}] of complex numbers of the form a+b\sqrt{-3} and show where it fails. [It must fail, because in the latter ring, there is no unique factorization into irreducibles: 2^2=(1+\sqrt{-3})(1-\sqrt{-3}).]
5. In F[x], find the greatest common divisor of polynomials
x^m-1 and x^n-1.
On Friday, April 13, we will have Quiz 5
on the material of the previous week: ideals, quotient rings, and the epimorphism theorem for rings.
HW12, due Fr., Apr. 20: Read Sections 4.8-4.11 of Paulin's notes. Solve:
1. Prove that in a PID, elements f_1,...,f_n are relatively prime (i.e. don't have a non-invertible common factor) if and only if there exist elements
h_1,...,h_n such that h_1f_1+...+h_nf_n =1.
2. Give an example of an ideal I in \C [x,y] which is prime but not maximal. (\C stands for the field of complex numbers.)
3. Let P be a polynomial with integer coefficients irreducible in \Z[x] (in particular this means that coefficients of P have no nontrivial common factor). Let Q be another such an irreducible polynomial which is proportional to P in \Q[x]. Prove that Q and P coincide up to a sign. Here \Z stands for the ring of integers, and \Q for the field of rationals.
4. Prove that \Q[x]/(8x^3-6x-1) is a field.
5. Prove that \Z_7[x]/(x^2+1) is a field, and find the number of elements in it. (Here \Z_7=\Z/7\Z stands for the filed of integers mod 7.)
HW13, due Fr., Apr. 27: On Monday, we will discuss prime factorization of Gaussian integers and its application to representations of integers as the sums of two squares. After that we will have a brief introduction into the theory of field extensions (reading Section 5.1 of Paulin's notes may be useful here) with the ultimate goal to show impossibility of some straighedge-and-compass constructions in elementary geometry. Solve:
1. Since the ring \Q [x]/(8x^3-6x-1) is a field (see previous hw), x-1 must be invertible in it. So, compute its inverse.
2. Factor x^4+1 into irrediucibles in \Q [x], and \R [x], and in \C [x].
3. Find all ways to represent 1105 as the sum of two squares of positive integers.
4. Prove that in \Z_/p\Z, where p is an odd prime, half of all non-zero elements are squares, and half are not.
5. Prove that the multiplicative group F^* of any finite field F is cyclic. ( Hint: Use the classification of finite abelian groups to show that such a group is cyclic if and only if the least common multiple of the orders of its elements equals the order of the group.)
Sample Final Exam
The actual final exam (on Monday, May 7, 8-11 am, in 289 Cory) will consist
of 10-12 problems covering the entire material of the course, of which you willbe asked to solve 6 problems of your choice (i.e. you may solve as many as you wish, but only 6 best will count).
Some students asked me to complile a detailed syllabus for the course. Here it is:
0. Divsibility of integers, the Euclidean agorithm, GCD, the Fundamental Theorem of Arithmetic, modular arithmetic, Fermat's little theorem, and its generalization by Euler, the Chinese remainder theorem, formula for the Euler number \phi(n) of invertible congruence classes mod n.
1. Groups, isomorphisms. Groups of symmetries of sets with additional
structure. Cayley's theorem (realizing every
groups as a subgroup in the group of permuatations on itself).
2. Equivalence relations, cosets, Lagrange's theorem.
3. Group homomorphisms, isomorphisms, normal subgroups, quotient groups, the epimorphism theorem (identifying the image of a homomorphism
with the quotient of the domain group by its kernel).
4. Actions of groups on sets, the orbit-stabilizer theorem (identifying the orbit
of a given point with the set of cosets of the stabilizer of the point).
Cuchy's counting principle (computing the number of orbits as the average
number of fixed points of the group's elements).
5. The action of the group on itself by conjugations. Conjugated subgroups. Conjugacy classes.
6. Pemutation groups S_n. Conjugacy classes in S_n and cycle structure decomposition.
Parity of permutations. The alternating group A_n. The simplicity of A_n with n>4. The Klein normal subgroup in A_4.
7. Groups described by generators and relations. Cyclic groups. Direct sums. Classification of finitely generated abelian groups up to isomorphism.
8. Rings. Some classes of rings (commutative, entire, integral domains, skew-fields,
fields), and their examples (e.g. the skew-filed of quaternions).
9. Homomorphism, ideals, quotient rings, the epimorphims theorem for rings.
10. The field of fractions of an integral domain.
11. Divisibility in integral domains. Euclidean rings: \Z, F[x], \Z[i].
Examples of non-unique factorization. Principal, prime, and maximal ideals. Examples in polynomial rings F[x,y,...,z].
12. Unique factorization theory: A Euclidean ring is PID; A PIDs is a UFD; If R is a UFD, then R[x} is a UFD (as a consequence of Gauss' lemma).
Examples: \Z[x], F{x,y].
13. Primes in Euclidean rings \C[x], \R[x], and in \Q[x]. Eisenstein's criterion of irreducibility in \Q[x].
14. Primes in the Gaussian ring \Z[i], and the representations of integers as the sums of two squares.
15. Elements of field theory: the charactristic of a field, field extensions, algebraic and transcendental extensions. Vector spaces over a field,
dimension, and its application to filed extensions: [K:F]=[K:E][E:F].
16. Applications to (non)constructibility by straightedge and compass.