Richard E. Phillips Lecture Series

Error-correcting codes and algebraic geometry

Tuesday, January 18, 2005 at 4:10 p.m. in B104 Wells Hall

Abstract

Fix an integer q>1 and let A be a set of size q. An "code of length N over the alphabet A" is a subset C of A^N. Given d<N, one wants C to be as large as possible under the condition that every distinct c,c' in C differ in at least d coordinates. For many q,N,d, the best constructions known use surprisingly sophisticated tools from algebraic geometry and number theory. In particular, this happens when q is large but fixed, d/N is limited to a suitable interval in (0,1), and N tends to infinity. We review some of the applications, both within and outside mathematics, for solutions to the combinatorial problems of constructing good codes and estimating their parameters, and indicate some of the fundamental upper and lower bounds on these parameters. We then outline how algebraic geometry yields very good codes that generalize the following classical construction: A is a finite field k (such as the integers mod q if q is prime), N=q, and C consists of the polynomial functions of degree at most q-d from k to k. Finally, we hint at recent further improvements (to be explored at greater length in the final lecture) that correspond to replacing polynomials by rational functions, or to other variations on the classical construction.

Linear codes and algebraic geometry in projective space

Wednesday, January 19, 2005 at 4:10 p.m. in A304 Wells Hall

Abstract

When A is a finite field k, the code of polynomial functions of bounded degree from k to k is a special case of a "linear code": a subset of k^N that is a vector subspace. Much of the theory of error-correcting codes concerns the important special case of linear codes. There is a particularly close connection between linear codes and algebraic geometry; for instance there is a natural bijection between linear codes with d>2 and subsets of projective space over k. (The polynomial code comes from a ``rational normal curve'' in that projective space.) This connection is profitable for both coding theory and algebraic geometry. We outline some examples in both directions.

Linear and nonlinear codes from algebraic curves

Thursday, January 20, 2005 at 4:10 p.m. in A304 Wells Hall

Abstract

In this final and more specialized lecture, we illustrate the application to coding theory of algebraic curves over finite fields, especially modular curves: how the arithmetic of such curves yields excellent error-correcting codes, and how certain families of modular curves have simple formulas that can be used to efficiently construct and potentially use some of those codes.

For additional information:

Department of Mathematics
Michigan State University
East Lansing, MI 48824-1027
(517)355-9680
ginther@math.msu.edu
www.math.msu.edu/Lecture_Series