AM106/206 Syllabus

AM 106 & 206:
Applied Algebra

Fall 2010

SYLLABUS

Lecturer: Prof. Salil Vadhan
Teaching Fellow:  Thiago Costa (possibly with others, depending on enrollment)
Course website: http://www.courses.fas.harvard.edu/3871
Staff e-mail: am106@seas.harvard.edu
Time & place: MW 2:30-4, Pierce 209

# Summary

Algebra is the study of operations (such as addition, multiplication, composition) on sets of objects (such as numbers, polynomials, matrices, permutations). In addition to studying specific operations on specific sets, we also abstract properties that such operations commonly satisfy and the implications of these properties, thereby unifying the study of a wide variety of mathematical objects. In addition to being a beautiful subfield of mathematics, algebra has numerous applications in science and engineering. It is extremely useful for studying symmetries of physical objects, and for encoding data and computations to provide properties such as error-correction and privacy.

In this course, we will cover:

• The basics of abstract algebra (groups, rings, fields)
• Algorithmic aspects of algebra: which algebraic problems have (efficient) algorithms, and which do not.
• Applications of algebra to science and engineering

# Topics

1. Introduction (1 lecture)
2. The Integers (2 lectures)
• General Theory (Gallian Ch. 0): induction, gcds, prime factorization, modular arithmetic
• Algorithmic Aspects: O notation, complexity of arithmetic, factorization, Euclidean algorithm
3. Group Theory (10 lectures)
• General Theory (Gallian Chs. 1-10): groups, subgroups, cyclic groups, permutation groups, isomorphisms, cosets, products, quotients, homomorphisms
• Algorithmic Aspects: exponentiation vs. discrete logarithms, computational group theory
• Applications: symmetry groups in crystallography, public-key cryptography
4. Rings and Fields (10 lectures)
• General Theory (Gallian Chs. 12-17, 19-22): rings, integral domains, ideals and quotients, ring homomorphisms, polynomial rings, vector spaces, extension fields, finite fields.
• Algorithmic aspects: polynomial arithmetic, finite field arithmetic.
• Applications: error-correcting codes

There is much more material, both theory and applications, on these topics that we do not have time to cover. AM 206 students will have the opportunity to explore some of these in their essays and homework problems.

# Prerequisites

The formal prerequisite for the course is (Applied) Math 21b or equivalent, but general "mathematical maturity" is more important than the specific material in these courses.  At times, we will assume familiarity with basic linear algebra as covered in Math 21b, but students who have instead taken a prior proof-based course on a different topic (such as AM 107, Math 101, CS 121, or CS 124) should be adequately prepared.

This course is more abstract and proof-based than most applied math classes. If you are doing proofs for the first time, it is particularly important that you invest sufficient effort at the start of the course to gain comfort, for example by attending the section on doing proofs, coming to office hours, and completing and turning in ps0.

AM 106 students:

• Weekly problem sets: 50%  (lowest score dropped)
• Two in-class quizzes: 10% each
• Final exam: 25%
• Class participation: 5%

AM 206 students:

• Weekly problem sets: 40%  (lowest score dropped)
• Two (7-8 page) essays on advanced topics of your choice: 10% each
• Presentation during reading period: 5% each
• Two in-class quizzes: 5% each
• Final exam: 20%
• Class participation: 5%

Your class participation grade is based on participation in lecture, but can also be boosted by participation in section and/or coming to office hours or section with questions or comments that show genuine interest in the material (i.e. is not just aimed to help you answer questions on the problem set or exam).  Do not be afraid of asking "stupid" questions!

AM206 problem sets will omit some of the more basic problems, and have some more advanced problems added.

# Problem Sets & Collaboration Policy

The course will have weekly problem sets, due Fridays at 2:10pm sharp (to be turned in electronically or in the box labelled AM 106 in the basement of Maxwell Dworkin.) Up to two times during the semester, you may turn your problem set in 3 days late, by Monday at 2:10pm. Any exceptions to this policy requires a note from your resident dean (or academic advisor, in the case of graduate students).

Students are encouraged to discuss the course material and the homework problems with each other in small groups (2-3 people).   Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem.  In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around.

While working on your problem sets, you may not refer to existing solutions, whether from other students, past offerings of this course, materials available on the internet, or elsewhere.  All sources of ideas, including the names of any collaborators, must be listed on your homework paper.

# Sections

There will be weekly sections, which will be used to clarify difficult points from lecture, review background material, go over previous homework solutions, and sometimes provide interesting supplementary material.

The required text is:

·        Joseph A. Gallian.  Contemporary Abstract Algebra, 7th edition.  It has been ordered at the Coop, and for reserve in the libraries.

However, we will also be covering some material (particularly applications and algorithmic discussions) that is not in Gallian, so it is important that you also attend lecture. Some other books that may be helpful:

# Related Courses at Harvard

• Math 122 &123: Algebra I & II. A full-year course in abstract algebra. Because it is longer and assumes more background, Math 122-123 covers a number of topics that we cannot fit in AM 106, such as group representations, modules, and Galois theory. (Students taking AM 206 can study some of these topics for their additional assignments.) On the other hand, it usually does not include the algorithmic aspects and applications of algebra that we will cover in AM 106.
• Math 152: Discrete Mathematics. A seminar-style course covering a variety of related topics in abstract algebra and discrete mathematics. My guess is that it has significant but not complete overlap with the "general theory" we cover, but that it has not much overlap with the applications and algorithmic issues we cover.
• Computer Science 226r: Efficient Algorithms. Covers algorithmic aspects of integer and polynomial arithmetic, finite fields, and error-correcting codes. Even though there is some overlap, this course complements AM106 quite well. In AM106, we will have time to do a more systematic treatment of algebra, but will spend less time on algorithms. CS226r does not cover group theory.

# Changes in Response to Student Comments

• Comment: Too slow in the first half and too fast in the second half.
Response: This is a common problem I have in courses I teach. But the good news is that I finally managed to avoid this comment last Spring by making an effort to go faster at the beginning. I will try to do the same this semester.

• Comment: Not enough applications!
Reponse: Regrettably, it is hard to fit in very many applications while covering all of groups, rings, and fields. This term we are committed to doing a serious treatment of 3 applications (symmetry groups in crystallography, cyclic groups in cryptography, and polynomials over finite fields in error-correcting codes), and dropping some of the more theoretical material as needed to make room. Students interested in more applications or more theory can get pointers from the AM206 essay topics.

• Comment: Course requires comfort with proofs.
Response: We will hold a special section next week on doing proofs, and will add an optional ps0 for practice and feedback on them.

• Comment: Lecture notes not useful.
Response: The lecture notes are simply intended to provide an outline of what was covered in lecture and provide details on material that is different than the text. They are not meant to be a substitute for attending lecture or reading the (excellent) textbook. Nevertheless, they will be slightly expanded in this offering.

• Comment: Too much computer science.
Response: We feel that discussion of computational and algorithmic issues is central to applied mathematics. Moreoever, abstract algebra has turned out to provide more applications in computer science than in, say, economics. However, we are going to spend more time on an application to the physical sciences (crystallography).

• Comment: AM206 is too much work.
Response: AM206 is indeed an intensive course, only for students who are willing to devote a significant amount of effort. However, we have increased the weight on the essays to reflect the amount of work and interest they provided for last year's students, and are going to try to shorten some of the problem sets for AM206 students.