Algebraic Geometric Codes

Fall 2024/5

About the course

This course focuses on the study of algebraic geometric 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 (tentative)

Introduction

Introduction to coding theory

The geometric picture: affine & projective curves

The basics of function fields; Goppa codes

Introduction

Abstracting the notion of a point: valuation, valuation rings, and places.

Function fields

Artin's approximation theorem

Divisors

Riemann's Theorem

The Genus

Goppa codes

The Riemann-Roch Theorem

Adeles and Weil differentials

The Riemann-Roch Theorem

Elliptic and hyperelliptic function fields

Function field extensions

Places in extensions

The ramification index and relative degree

The fundamental equality

Normal extensions

The co-norm in extension

Constant field extensionss

Integral elements

Kummer's theorem

The Hasse-Weil Theorem

The Zeta Function of a function field

The Zeta function under constant field extensions

The Hasse-Weil theorem

The Different

The complementary module

The different

Dedekind's Different Theorem

Hurwitz Genus Formula

Cyclic extensions

Kummer extensions

Artin-Schreier extensions

Construction of Algebraic-Geometric Codes

Towers of function fields

Several constructions

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.

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.