Instructor:
Sorin Popescu
(office: Math 3-109, tel. 632-8255, e-mail
sorin at math.sunysb.edu)
Office hours: Tu 11:30am-12:30pm, Th 2:20pm-3:30pm
Graduate Assistants:
Tanvir Prince (office: Math 2-121, email prince at math.sunysb.edu)
Office hours: Tu 6pm-8pm MLC, Wed 1pm-2pm Math 2-121
Travis Waddington (office: Math 3-122, e-mail ratatosk at math.sunysb.edu)
Office hours: Tu 1:45-3:45pm MLC, Mo 12-2:00pm 3-122
Schedule:
Lecture: TuTh 12:50pm-2:10pm, Library W0512
Recitation 1: Tu 3:50pm-4:45pm, Physics P117
Recitation 2: Mo 11:45am-12:40pm, Physics P112
Midterm Review session: Monday, Feb 21, 5:00-6:30pm in Math P-131
Midterm Review session: Tue, Mar 29, 6:30-8:00pm in Math P-131
Final exam review session: Wed, May 11, 3:00-5:00pm in Math P-131
Final exam: Tuesday, May 17, 11:00-1:30pm in Old Eng 145
Grades are now posted on the Solar system. Have a nice summer!
Prerequisites:
Either MAT 203 or MAT 205 or AMS 261 (Calculus III),
and MAT 211 or AMS 210 (Linear algebra) are prerequisites for this class.
In general basic linear algebra exposure is required and assumed, but I will try to
keep prerequisites to a minimum.
Textbook(s):
Numbers, Groups and Codes,
J. F. Humphreys, M. Y. Prest, (second edition), Cambridge University Press.
Available from the university bookstore or check prices at
AddAll.
The class is an introduction to algebraic structures and applications. The above textbook
moves from algebraic properties of integers, through other examples, to the
beginnings of group theory. Applications to finite state machines,
public key cryptography and to error correcting codes are also emphasised.
Attention is also paid to the historical development of the mathematical
ideas presented. The text should be easily accessible for both students of mathematics and computer science.
Here are a number of other good undergraduate books that you may perhaps find
useful to consult during the semester (all of them available in our library):
-
A Friendly Introduction to Number Theory, J.H. Silverman, (second edition).
- An Introduction to the Theory of Numbers,
I. Niven and H.S. Zuckerman
- Elementary Number Theory and Its Applications , by Kenneth Rosen, (fourth edition)
- Number theory with computer applications, R. Kumanduri and C. Romero
- Concrete Abstract Algebra : From Numbers to Groebner Bases, Niels Lauritzen
- Introduction to Cryptography with Coding Theory, Wade Trappe and Lawrence C. Washington
- Naive set theory, P. Halmos
-
Groups and Symmetry: A Guide to Discovering Mathematics, David W. Farmer
Course description:
We will basically cover the following chapters in the textbook but the schedule below
may/will be adjusted based on students' preparation and progress.
Topic | Sections in textbook | Week | Notes |
Euclidean division algorithm, GCD/LCM, Induction | Sections 1.1 and 1.2 | 1/24-1/30 | |
Prime numbers, Unique factorization, Congruences, Linear Congruences | Sections 1.3 and 1.4 | 1/31-2/6 | |
Fermat's theorem, Euler's theorem, applications | Sections 1.5 and 1.6 | 2/7-2/13 | |
Public key criptography, Cryptographic protocols | Section 1.6 | 2/14-2/20 | |
Sets, functions | Sections 2.1 and 2.2 | 2/21-2/27 | Midterm 2/22 |
Relations | Section 2.3 | 2/28-3/6 | |
Permutations | Section 4.1 | 3/7-3/13 | |
Order and signature of a permutation, transpositions and cycles | Section 4.2 | 3/14-3/20 | |
Groups: definition and examples | Section 4.3 | 3/28-4/3 | Midterm 3/31 |
Algebraic structures | Section 4.4 | 4/4-4/10 | |
Order of an element, generators, subgroups | Sections 5.1 and 5.2 | 4/11-4/17 | |
Lagrange's theorem; finite groups of small order | Sections 5.2 and 5.3 | 4/18-4/24 | |
Error detecting/correcting codes | Section 5.4 | 4/25-5/1 | |
Error detecting/correcting codes (continued) | Section 5.4 | 5/2-5/8 | |
Review session | Wed 05/11 | 3:00-5:00pm | P-131 |
Final Exam | Tu 05/17 | 11:00am-1:30pm | Old Eng 145 |
Note: Although students may take both MAT 312 and MAT 313, there is some
nontrivial overlap in the material of these two courses.
Projects, Homework & Grading:
Students are encouraged to do an individual special project or
participate in a group special project. These could involve a
historical report on material of the course, including perhaps a brief
oral presentation or learning some topic in algebra not discussed in
the course or writing a computer program for some algorithm. The
choice of topic and the exact scope of the special project are to be
determined after consultation with the instructor and the final form
of a proposal must be presented in writing to the instructor.
Homework is an integral part of the course. Problems will be assigned
periodically. You should try to solve them by yourself. You should
also discuss them with your fellow students and you may work together
on each problem set, but what you hand in must be your own writing and
you should be able to answer questions about its content. The
solutions of homework problems can be discussed (after the due date)
in lectures and/or more appropriately in recitation sections. Some of the
homework problems will be graded and solutions will be
posted on the web. Problems marked with an asterisk (*) are for extra credit.
Late homeworks will not be accepted.
There will be two midterm examinations (on 2/22 and 3/31) and
a final exam (on 05/17). All examinations are inclusive in the sense
that they will cover all the material studied up to a specified
date. The exact area of coverage of each examination will be posted on
the web. No calculators, notes, or books, etc., will be allowed during the
midterms or final exam. Exam dates and times are not flexible and there
will be NO makeup exams.
Your grade will be based on the weekly homeworks (20%), midterms (25% each),
and the final exam (30%). The two lowest homework grades will be dropped
before calculating the average. A special project and class participation
may also contribute (up to 15%) toward the final grade (either as bonus,
or as substitute for some of the homework).
Links:
The following is a (growing) list of web sites devoted to
topics relevant for our class:
-
An On-Line Encyclopedia of Integer Sequences.
- Fibonacci Numbers and Nature. Or
Tony Phillips'
"The most
irrational number". Also
"Who was Fibonacci?": a brief biography of Fibonacci.
- Primes: Lots of interesting facts about prime numbers.
-
Mersenne Primes: interesting facts about Mersenne primes, perfect
numbers, and related topics.
- Primes is P:
about a recent polynomial time deterministic algorithm to test if an input
number is prime or not.
- RSA:
The RSA company's web page containing lots of interesting information
about the RSA public key cryptosystem and cryptography in general,
from both a technological and a socio-political viewpoint.
- The RSA factoring challenge.
- The Enigma machine (in German).
- Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone.
It is a handbook for both novices and experts, introducing practical aspects of both conventional and public-key cryptography.
- GCHQ Challenge (as of December 2004). Their next cryptographic challenge is
scheduled to appear on their website in June 2005.
- Ron Rivest's Cryptography and Security links page.
- MIT Lecture Notes on Cryptography, by S. Goldwasser and M. Bellare.
- Java applet drawing Hasse diagrams of posets. Another interactive poset drawing applet is available here.
- An alternative discussion (to the textbook) of the signature of permutations. Also the short argument we have used in class to define signature. (Both links work from campus IP addresses only.)
- An elementary discussion of the famous Sam Loyd 15 puzzle: A Modern Treatment of the 15 Puzzle by Aaron F. Archer, in The American Mathematical Monthly, Vol. 106, No. 9. (Nov., 1999), pp. 793-799 (link works from campus IP addresses only).
- General graph puzzles (the above 15 puzzle corresponds to the graph = cartesian product of the path on 4 vertices with itself) are discussed in: Graph puzzles, homotopy, and the alternating group, Richard M. Wilson, in Journal of Combinatorial Theory, Series B, Volume 16, Issue 1, pages 86-96.
- Rubik's cube involves a subgroup G of S48, permuting the moving 48 colored squares,
and generated by six specific permutations (clockwise quarter-turns of the front, back, right, left, top and bottom faces
of the cube). Solving Rubik's cube amounts to the mathematical problem of finding an algorithm such that, given any element g of the group G, one can determine a sequence g1,...,gk of powers gi of the generators such that g=g1...gk. This requires the discovery of short words in the generators whose effects on the cube are to move relatively few of the 48 squares.
- An analysis of the 4 slices analogue of Rubik's cube using (groups of) permutations: Rubik's Revenge: The Group Theoretical Solution, by Mogens Esrom Larsen, in The American Mathematical Monthly,
Vol. 92, No. 6, pp. 381-390 (link works from campus IP addresses only).
- A very brief explanation of the "mysterious art" of English bell ringing.
Read more about elements of group theory in campanology in Arthur White's paper "Fabian Stedman: The First Group Theorist?", in The American Mathematical Monthly, Vol. 103, No. 9. (Nov., 1996), pp. 771-778 (link works from campus IP addresses only).
- A brief history/introduction to error-correcting codes Digital Revolution - Error Correction Codes, Joseph Malkevitch, in What's New in Mathematics Feature Column of the AMS.
- A summary describing how information is encoded on Compact Discs. CDs use a modified form of the Reed-Solomon code called the Cross Interleave Reed-Solomon Coding (CIRC). Here is a short description of how Reed-Solomon codes are used for error-correction on a audio CD (Red Book Standard).
- Maple code (and brief explanations) relevant to class material.
A number of interesting local links that you are warmly encouraged
to explore:
Math Learning Center
The
Math Learning Center (MLC), located in Room S-240A of the Math Tower,
is an important resource. It is staffed most days and some evenings by mathematics tutors
(professors and advanced students).
For more information and a schedule, consult the
MLC web site.
Special needs
If you have a physical, psychiatric, medical or
learning disability that may impact on your ability to carry out
assigned course work, you may contact the Disabled Student Services
(DSS) office (Humanities 133, 632-6748/TDD). DSS will review your
concerns and determine, with you, what accommodations may be necessary
and appropriate. I will take their findings into account in deciding
what alterations in course work you require. All information on and
documentation of a disability condition should be supplied to me in
writing at the earliest possible time AND is strictly
confidential. Please act early, since I will not be able to make any
retroactive course changes.