Algebraic Geometry Codes
Fall 2024/5
About the course
This course focuses on the study of algebraic geometry codes, also known as Goppa codes. Like Reed-Solomon or Reed-Muller codes, AG codes involve polynomial (or rather rational function) evaluations. However, AG codes differ in that the evaluation points are selected from a specifically chosen algebraic curve. This seemingly minor distinction leads to a substantial increase in the complexity of the mathematics required to construct, understand, and analyze these codes. Indeed, the analysis includes deep results such as the Riemann-Roch Theorem and the Riemann Hypothesis over algebraic function fields, which is, in fact, a famous theorem known as the Hasse-Weil Theorem.
Throughout this course, we will develop the intricate and beautiful mathematics that underpin AG codes and provide constructions of codes that surpass the Gilbert-Varshamov bound (for sufficiently large constant size alphabets). The course content is fundamentally algebraic. We will work with rings and groups, focusing primarily on field extensions and Galois theory.
My goal is to make this course accessible to students of theoretical computer science, even though it involves a significant amount of mathematics. Specifically, I will not assume any prior knowledge in topology, complex analysis, or commutative algebra. However, I will occasionally point out connections between the course material and these areas to offer some insight and help those familiar with these topics connect the dots.
The course lectures and recitations will be conducted in English and will be regularly uploaded to a dedicated YouTube channel.
Syllabus
Introduction
Welcome to AG Codes! (notes)
Introduction to coding theory (notes)
Abstracting the Notion of a Point
Informal discussion (notes)
Ordered groups (notes)
Valuations (notes)
Valuation rings (notes)
Places (notes)
Function Fields
Artin's approximation theorem (notes)
The ramification and residual indices (notes)
Function fields (notes)
Riemann's Theorem
Divisors and Riemann-Roch Spaces (notes)
Riemann's Theorem & the genus (notes)
Goppa Codes
Goppa codes (notes)
The Riemann-Roch Theorem
Adeles (notes)
Weil differentials (notes)
The Riemann-Roch Theorem (notes)
Function Field Extensions
Function field extensions and the fundamental equality (notes)
Analyzing our running example (notes)
Our example in more depth (notes)
Normal extensions (notes)
The conrom (notes)
The Different, Hurwitz Genus Formula, and Kummer's Theorem
Integrality & the complementary module (notes)
The Different and Dedekind's Different Theorem. Proof is given in this course (notes)
Hurwitz Genus Formula. Proof is not given in this course (notes)
Kummer's theorem (notes)
Explicit Formulas for the Different (notes)
Construction of Algebraic-Geometric Codes
Recap (notes)
Kummer extensions (notes)
Towers of function fields (notes)
Wild towers from Artin-Schreier extensions. Not covered in this course (notes)
Projects for the seminar (notes)
The Hasse-Weil Theorem
Constant field extensions. Proofs are not given in this course (notes)
The Hasse-Weil theorem or proof of the Riemann Hypothesis for function fields!
Recitations
Below are the notes for the recitations. Like the lectures, the recitations are recorded and available on the course’s YouTube channel.
Recitation 1 & 2 - Abstract algebra refresher (notes)
Recitation 3 - Field theory recap (notes)
Recitation 4 - The rational function field's places (notes)
Recitation 5 - A lemma on the ramification and residual indices (notes)
Recitation 6 - Extension of places, divisors, trace and norm (notes)
Recitation 7 & 8 - The Hermitian function field (notes)
Recitation 8 & 9 - Adeles, Weil differentials & AG Codes (notes)
Technicalities
When and where
Lectures are on Wednesdays 10:00-13:00 and recitations by Tomer Manket are an hour afterwards, Wednesdays 14:00-15:00. Location TBD.
Grade
Fifty percent of your grade will be based on a one-hour presentation at the end of the semester, covering material not addressed in the lectures or recitations. The remaining 50% will be determined by your performance on the problem sets (submissions in pairs). We will publish 5 or 6 problem sets throughout the semester.
Literature
We will not follow a particular text but most of what we will cover appears in Stichtenoth' Algebraic Function Fields and Codes. Combined with the seminar portion of the course, we will cover a significant part of this book. I will also partially follow Dan Haran's lecture notes, though these are in Hebrew (which, honestly, is easier to learn than algebraic geometry codes).
Some recommended literature that we will not directly follow is Lorenzini's marvellous An Invitation to Arithmetic Geometry, and Morandi's lecture notes. Also highly recommended books are Algebraic Goemetric Codes: Basic Notions and its followup Algebraic Geometry Codes: Advanced Chapters by Tsfasman, Vladut and Nogin. Another book which may interest you is Schmidt's classical Equations Over Finite Fields - An Elementary Approach.
Two Highly Recommended Books on the History of Mathematics
There are two additional, highly recommended books that focus on the historical development of the field, although they involve and assume a substantial level of mathematical understanding. The first is Theory of Algebraic Functions of One Variable, the first English translation of the classic 1882 paper by Dedekind and Weber. This seminal work of Dedekind and Weber aimed to establish Riemann's ideas from the 1850s on rigorous and sound algebraic foundations. The key breakthrough in this paper was the development of the theory of algebraic functions in analogy with Dedekind's theory of algebraic numbers, where the concept of the ideal plays a central role. By introducing such concepts into the theory of algebraic curves, Dedekind and Weber laid the groundwork for modern algebraic geometry. This book, enriched by Stillwell's contributions that go far beyond a mere translation, offers an insightful and rewarding read.
The second book, The Riemann Hypothesis in Characteristic p in Historical Perspective by Roquette, marvelously covers the historical development and resolution of the Riemann Hypothesis in function fields. It begins with Artin and Schmidt's foundational works, progresses through contributions by Hasse and Davenport, continues with Deuring, and culminates in Weil's celebrated proof, followed by Bombieri's surprisingly fairly short and simple proof. Like the previous recommendation, this book seamlessly weaves mathematical content into its historical context, making it both an informative and engaging read.
Video lectures
There are some excellent online courses available that cover some of the mathematics we’ll need. While none focus specifically on the coding aspect, the underlying math is generally the more challenging part of the course compared to its application to coding theory.
Plane algebraic curves by Andreas Gathmann
This is a superb course that covers the theory of plane curves with minimal background in commutative algebra. Its strong emphasis on geometry, alongside the commutative algebra, provides a great complement to our course, which is more algebraically focused. Highly recommended.
Computational Arithmetic - Geometry for Algebraic Curves by Nitin Saxena
This excellent (still ongoing) course places more emphasis on the case where the ground field is finite, which is of particular interest to us, compared to Gathmann's course mentioned earlier. Here too, the prerequisites in commutative algebra are fairly minimal.
Algebraic Geometric Codes by Peter Beelen
This crash course provides an overview of some of the topics we will cover. However, the prerequisites are more advanced. It will likely be more beneficial to you either during or after completing our course.
Algebraic Number Theory by U. K. Anandavardhanan
Since we will be working with finite fields, much of the mathematics we need overlaps with the underlying concepts in algebraic number theory (arguably as much as those in algebraic geometry). While we will develop our theory independently of algebraic number theory, for those interested in the connection between the two fields—and in gaining some "arithmetic" intuition—this is a recommended course.
Basic Algebraic Geometry by Miles Reid
This introductory course in algebraic geometry emphasizes intuitive geometric concepts while gradually developing the necessary commutative algebraic ideas. Although we will focus solely on algebraic curves, which are "one-dimensional," it is highly valuable to understand the broader development of algebraic geometry in greater generality. Like many other courses (such as Gathmann's course mentioned earlier), it concludes with a proof of the Riemann-Roch Theorem, which we will cover about halfway through our course. The author also has an excellent book.
Algebraic Geometry by Richard Borcherds
There’s nothing quite like Richard Brocherd's courses. This one offers a more in-depth exploration of algebraic geometry. There is also a follow-up course on schemes.
Commutative Algebra by Richard Borcherds
Richard Borcherds also offers a fantastic and in-depth course on commutative algebra.
Galois Theory by Richard Borcherds
In addition to commutative algebra, we will also need Galois theory, especially for the second part of the course. While I will assume you are all familiar with Galois theory (as it is part of the formal prerequisites), you're likely to learn something new, as is always the case with Richard Brocherd's courses.
Algebraic Coding Theory by Mary Wootters
Since this is a course on coding theory after all, I feel obligated to recommend a relevant course on the subject. Mary Wootters offers such an excellent course, with a focus on algebraic techniques. While the mathematics is more elementary compared to that used in algebraic geometry codes, their sophisticated application will give you valuable insight into how algebraic methods can be applied in coding theory. Additionally, Mary is an outstanding lecturer.