Math 75

Applied topics in number theory and algebra: finite fields and coding theory

Instructor: Carl Pomerance (carl.pomerance at dartmouth.edu)

Abstract | Classes | Tutorials | Staff | Textbook | Grading | News and current assignment | Past assignments | Exams | Honor Code


News and current assignment

If you'd like to drop by my office early this week I can return your recent assignments.

There will be no final examination.
Any past-due work needs to be handed in to me by 11 AM on Friday, May 30, at the latest.

Here is an article of mine on primality testing written a few years ago.

Here are some notes I prepared on finite fields. I hope they're useful.

And here is a continuation of the notes.

Our text is "Error-correcting codes and finite fields" by Oliver Pretzel, published by Oxford. This book should be at Wheelock Books, and it is available on amazon and other sites.

I taught this class (jointly with Paul Pollack) in Spring term 2008, covering the same topics. You might find the class notes from that term helpful; they're here.

Abstract

Finite fields and coding theory

Coding theory is not involved with secrecy. Rather, it involves efficient ways of sending data over channels that sometimes make errors. From dvd's with scratches in them to low-signal areas of cell coverage, we have all been the beneficiaries of this technology. The ability to send a bit stream that is just a tad longer than the one you'd like to send, but has the ability to detect, and even correct a few errors made in the transmission, is vital for modern life.

The principal mathematical tool behind error-correcting codes is the theory of finite fields. We have all run into fields, even if we haven't taken a course in algebra. For example, the field of rational numbers, the field of real numbers, and the field of complex numbers: these should all be familiar. But they are all infinite fields. A finite field enjoys the same axioms of addition and multiplication as these infinite fields, but it has only finitely many elements. A "prime" example: the integers mod p, where p is a prime number. There are also somewhat more complicated examples that are built off of these "prime" cases. We shall see in this course how to exploit the algebra of finite fields to consruct efficient error-correcting codes.

Prerequisites: An undergrad number theory course and/or an undergrad course in abstract algebra. A lot of what we'll be doing involves some linear algebra. I'll be happy to try and fill in gaps for motivated students.

Grading: There will be weekly written assignments, a midterm, and a final exam. Enrolled graduate students who have been admitted to candidacy: please see me about requirements.

Classes

Room: 004 Kemeny
Lectures: Monday-Wednesday-Friday 11:15 am--12:20 pm (11 hour)
X-hour: Tuesday 12:00 pm - 12:50pm

We may meet several of the x-hours, but this will always be announced in advance.

Staff

Instructor:
Carl Pomerance -- 339 Kemeny / Tel. 6-2635
Office hours: Tuesday and Thursday 9:00 AM--9:55 AM and by arrangement at other times.

Textbook

See above.

Homework

Homework is due at the start of the class period on the due date.
Homework will be generally due once per week on Mondays.
Assignments will be posted on this website, with extra problems and/or comments sometimes added as the week progresses.

Past assignments

Homework assignment 1 is here.
It's due, Monday, March 31.

The attached assignment is due on Wednesday, April 9.

The attached assignment is due on Monday, April 14.

Here is the take-home midterm due at the start of class on Monday, April 21.
However, if you need some extra time, please ask me. (I'm a bit slow on the uptake, not making the connection about this being a holiday weekend.)

Assignment due Monday, April 28: Chapter 3 in the text, numbers 7, 8, 10, 16, 17, 19. (Note that "error pattern" is defined in the next chapter.)
Also, construct a check matrix for the binary triple repetition (9,3) code, which encodes (a,b,c) as (a,a,a,b,b,b,c,c,c).

Homework assignment due Monday, May 5, 2014:
Ch. 4, #1, #3, #6, #7; Ch. 5, # 4.
Note: I believe "rows" in 4.3 is meant to be "columns".
Also note: Unless you can find some compact way of describing the coset leader/syndrome table for the ternary code of 4.7, you can skip this part. Here's something to do instead:
When constructing a coset leader/syndrom table one thing that needs to be checked is that the coset leaders are actually in different cosets. Show that if the syndromes are different, this is guaranteed.

Homeword due Wednesday, May 14: Ch.14, #2, #4, #5-#10.

Homework due Wednesday, May 21.

This assignment is due Wednesday, May 28.
(Note: For Problem 2, you are allowed to assume the fact that the multiplicative group modulo n is cyclic when n is the square of a prime.)

Exams

There will be a midterm and a final exam.

Grading

Grades will be based on homework and exams.

Honor Code

Collaboration on homework is definitely allowed and even encouraged. However, it is tempting to think that you understand something that was figured out by your friend. When you hand in a solution, you should know it well enough that you could explain it to others. Please name others you worked with when handing in homework papers. Merely copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code, even if attribution is made. You should understand what you turn in.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Coordinator, Nancy Pompian, can be reached at 6-2014 if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.