Introduction to Algberaic-Geometric Codes
Spring 2019
Course Pitch (a.k.a. Syllabus)
Theoretical computer scientists make a regular use of algebraic objects, most prominently polynomials over finite fields, to construct and analyze desired objects such as error correcting codes, expander graphs, pseudorandom generators, cryptographic protocols, and randomness extractors. Reed-Solomon codes is one such classic example. In 1975, Goppa suggested to construct and analyze codes using machinery from algebraic geometry or, more precisely, based on algebraic curves. In a long line of research, such codes were eventually constructed. Surprisingly, these codes beat the Gilbert-Varshamov bound for sufficiently large (constant size) fields.
The mathematics underlying Goppa codes is far deeper than the standard tools generally used by theoretical computer scientists, and the hope is that it can be further exploited in resolving other open problems, especially problems for which using polynomials one currently obtains the state-of-the-art results. Indeed, many important problems fall into this category. For that to happen, the underlying mathematics must be grasped by computer scientists. This is the goal of this course (and its follow-up).
In this introductory course we will thoroughly develop the fascinating mathematics underlying algebraic curves to the point where Goppa's framework can be defined and well-understood - a modest yet challenging goal. The approach we take is mostly algebraic, however, we will not abandon the geometric aspect - we will "think geometrically" and prove theorems algebraically. Students who complete the course should be able to use the mathematical tools developed beyond the code-specific application.
Who this course is for?
The target audience for the course is computer science graduate and advanced undergraduate students that would like to study fascinating, deep mathematics and employ it in their own research. I will assume basic knowledge in ring theory and field theory. This was covered in a course I gave last semester as in any standard course on abstract algebra. I will not assume knowledge in topology, commutative algebra or Galois theory - we'll develop all we need.
Slides
So, initially, I was hoping to deliver this course on board like any good old math course. However, this turned out to be difficult in terms of time. So, we are switching to slides now:
Lecture 6 (April 29, 2019)
In this lecture, we studied the following three units + the construction of the field of fractions with respect to a multiplicative set that appears in the next unit.
Lecture 7 (May 6, 2019)
We study the important commutative algebraic tool of localization and use it to prove an important result regarding algebraic curves.
-
Just started Localization of modules
Lecture 8 (May 13, 2019)
Lecture 9 (May 20, 2019)
Lecture 10 (May 27 2019)
Lecture 11 (June 3 2019)
-
Projective curves
Lecture 12 (June 10 2019)
You can access the old notes here.
Assignments and Final
When and where
Lectures: Monday 12:10-15:00, Orenstein 111
Recitations: Wednesday 10:10-11:00, Orenstein 103
Grade
About 8-10 light assignments will be given during the semester. These will account for 50% of the grade. The remaining 50% will be determined by a take-home exam.
Reading material
We will mainly follow the truly marvellous book An Invitation to Arithmetic Geometry by Dino Lorenzini. We may also make use of the standard book in the field of algebraic geometric codes: Algebraic Function Fields and Codes by Henning Stichtenoth. Other resources include great lecture notes by Morandi, and the books Algebraic Geometry in Coding Theory and Cryptography by Niederreiter and Xing, and Algebraic-Geometric Codes by Tsfasman and Valdut.
Viewing material
To get some taste of what this course is about, see the introductory talk I gave on the subject at IAS. To go deeper, I recommend Beelen's mini-course on the subject. It assumes prior knowledge but is clear enough so that much can be gained nonetheless.
A follow-up course
In the following semester, a follow-up course was planned to be given in which we will continue to develop central tools in the study of algebraic curves such as the Riemann-Roch theorem, factorization of ideals in ring extensions, ramification and discriminants, the zeta function attached to an algebraic curve, and explicit constructions of algebraic curves with desired properties as well as algebraic-geometric codes. Some of the material may shift from this more advanced course to the introductory course and vice versa.