2020 Graduate Summer School Course Descriptions
Week 1 - July 6-10, 2020
Lecturer: Henry Cohn, Microsoft Research New England. Title: Numerical exploration in sphere packing, Fourier analysis, and physics
The sphere packing problem asks what fraction of R^n can be covered with congruent balls whose interiors are disjoint. This problem arises naturally in geometry, information theory, and physics, but it remains mysterious in most cases. In this course, we'll look at a variety of computational problems surrounding the packing problem. How can we optimize over lattices or other structures in R^n? How does the space of lattices behave? How can we bound the packing density or related quantities? Along the way, we'll examine optimization problems in Fourier analysis, uncertainty principles, and modular forms.
Lecturer: Hendrik Lenstra, Universiteit Leiden. Title: Algorithms in algebraic number theory
This minicourse is about algorithms for computational problems that one encounters in algebraic number theory. The emphasis is not on actual computations, but on issues of mathematical interest that arise in the design of efficient algorithms; here "efficient" is generally taken to mean "polynomial-time". We shall discuss problems for which such algorithms are known, and techniques for circumventing problems for which no efficient algorithms are known. Special attention will be given to the computation of rings of integers, and to the computation of power residue symbols and Artin symbols.
Lecturer: Joseph Silverman, Brown University. Title: An Introduction to Lattices, Lattice Reduction, and Lattice-Based Cryptography
A lattice is a discrete subgroup of R^n. We will discuss the theory of lattices and describe how they have been used to construct practical public key cryptosystems and digital signature schemes that are, at least presently, secure against attacks by quantum computers.
- Lecture #1: Lattices and Hard Lattice Problems.
- Lecture #2: Lattice Reduction: Solving(?) Hard Lattice Problems.
- Lecture #3: Public Key Cryptography 101: A Brief Introduction.
- Lecture #4: Lattice-Based Public Key Cryptosystems.
- Lecture #5: Lattice-Based Digital Signatures and Rejection Sampling.
Week 2 - July 13-17, 2020
Lecturer: Nadia Heninger, University of California, San Diego. Title: Lattices, lattice reduction, and computational problems in cryptanalysis and coding theory
In this course, we will explore a number of algorithmic techniques for solving problems that arise in classical cryptanalysis and coding theory, mostly centered around using lattices and lattice reduction type algorithms. Topics will include efficient lattice reduction, Coppersmith's method for finding small solutions to polynomial equations modulo integers and its numerous variants, and the hidden number problem.
Lecturer: Kristin Lauter, Microsoft Research. Title: Supersingular Isogeny Graphs in Cryptography
With the advent of quantum computers, the mathematical community is under urgent pressure to work on proposing and attacking new hard problems for use in cryptography, which are not already broken in polynomial time by a quantum computer. Supersingular Isogeny Graphs were proposed for use in cryptography in 2006 by Charles, Goren, and Lauter. Supersingular Isogeny Graphs are examples of Ramanujan graphs, which are optimal expander graphs. These graphs have the property that relatively short walks on the graph approximate the uniform distribution, and for this reason, walks on expander graphs are often used as a good source of randomness in computer science. But the reason these graphs are important for cryptography is that finding paths in these graphs, i.e. routing, is hard: there are no known subexponential algorithms to solve this problem, either classically or on a quantum computer. For this reason, cryptosystems based on the hardness of problems on Supersingular Isogeny Graphs are currently under consideration for standardization in the NIST Post-Quantum Cryptography (PQC) Competition. This course will introduce these graphs, the cryptographic applications, and the various algorithmic approaches which have been tried to attack these systems.
Lecturer: Andrew V. Sutherland, MIT. Title: Computational tools for number theorists
Abstract: In this lecture series I will survey a wide array of computational tools and platforms available to number theorists, including (1) computer algebra systems (Magma, Nemo/Hecke, PARI/GP, SageMath), (2) online databases (the LMFDB, databases included in GAP and Magma, and various tables and websites maintained by individual researchers), (3) software libraries (such as NTL and Pari, as well as specialized packages like ARb, Flint, GMP, MPFR, primesieve, Singular, smalljac), (4) algorithmic techniques (birthday-paradox methods, CRT-lifting, evaluation/interpolation, Groebner bases, LLL, Newton/p-adic iteration), and (5) implementation and deployment tools (Jupyter Notebooks, GitHub, Valgrind, parallelization/optimization methods, cloud computing). We will only scratch the surface of most of these topics; the primary goal is to give participants a broad perspective so they can make informed decisions when choosing computational tools to use in their own research, as well as some rules of thumb to help guide these decisions. There are no mathematical prerequisites, but I will assume students have some (possibly minimal) programming experience and that they are comfortable thinking algorithmically; familiarity with Python and/or C/C++ will be useful but is not required.
Lecturer: Melanie Matchett Wood, University of California, Berkeley. Title: Arithmetic Statistics
This course will be an introduction to arithmetic statistics, and start by explaining the motivating questions of the field. Given a finite group G, how many number fields with Galois group G are there with discriminant bounded by X, asymptotically in X? As we vary a number field in a family, what distribution on class groups do we obtain? What is the distribution of local properties of the number field, such as whether a rational prime is split in that number field? As we vary an elliptic curve in a family, what is the distribution of Selmer groups and of ranks? These questions all lead to further generalizations as well. We will discuss the known results, and give an introduction to some of the methods that have been successful so far, including geometry of numbers and analytic methods. We will explain the important conjectures, and some open questions where it is not even known what to conjecture. We will introduce the random linear algebraic models that help support and inform many of the conjectures. We will also highlight places where conjectures have been informed or supported by computation and places where new computations would have the potential to advance the field.
Week 3 - July 20-24, 2020
Lecturer: Tim Dokchitser, University of Brisol. Title: Curves over local fields
This short course is an introduction to arithmetic surfaces and models of curves. I will begin by defining regular models, explain some of their properties and give examples. There has been a lot of recent progress on the question how to compute models for interesting classes of curves, and I will try to summarise some of it in the second lecture. The third lecture is about why we want to study them: I will explain how some of the invariants related to the Birch-Swinnerton-Dyer conjecture rely on being able to compute such models.
Prerequisites: Curves over fields, basic algebraic geometry, p-adic numbers.
Suggested reading list: J. Silverman, Arithmetic of Elliptic curves, Ch. I+II (basic algebraic geometry), VII (elliptic curves over local fields) J. Silverman, Advanced Topics in the Arithmetic of Elliptic curves, Ch III+IV Q. Liu, Algebraic geometry and arithmetic curves (for a comprehensive arithmetic geometry background)
Lecturer: David Harvey, University of New South Wales. Title: Counting points on curves over finite fields
The zeta function of an algebraic variety over a finite field is a rational function that encodes a wealth of interesting arithmetic information about the variety. Concretely, computing the zeta function amounts to counting the number of solutions to a system of polynomial equations in several variables. In this course, I will discuss a few algorithms for computing zeta functions, focusing in particular on the case of hyperelliptic curves, i.e., equations of the form $y^2 = f(x)$. The first main goal of the course is to explain an algorithm that computes the zeta function of a curve over a field of characteristic $p$ in time roughly $p^{1/2}$. The second main goal is to explain an algorithm that takes as input a curve defined over $\mathbb{Z}$, and computes the zeta function of its reduction modulo $p$ simultaneously for all (good) primes $p < N$ in time roughly $N (\log N)^3$, i.e., in ``average polynomial time'' per prime. Some familiarity with thinking about algorithms and asymptotic complexity will probably be helpful for this course, but I will not assume any prior experience with zeta functions or algorithms for computing them.
Lecturer: Bianca Viray, University of Washington. Title: Rational points on varieties and the Brauer-Manin obstruction
In 1970, Manin introduced a powerful obstruction to the existence of rational points on varieties coming from the abelian reciprocity laws encoded in the Brauer group. This obstruction, now known as the Brauer-Manin obstruction, explains a large fraction of the failures of the local-to-global principle known to date. This mini-course will cover both the theoretical and computational aspects of the Brauer-Manin obstruction, with an emphasis on how the two inform each other. At the end of the mini-course, we will also review failures of the local-to-global principle that are not explained by the Brauer-Manin obstruction.
Prerequisites: Algebraic number theory, Brauer groups of number fields, including statements from class field theory. Familiarity with algebraic geometry, including Picard groups and étale cohomology.
Suggested reading: Gille, Philippe; Szamuely, Tamás Central simple algebras and Galois cohomology. Second edition of [MR2266528]. Cambridge Studies in Advanced Mathematics, 165. Cambridge University Press, Cambridge, 2017. xi+417 pp. ISBN: 978-1-316-60988-0; 978-1-107-15637-1 Skorobogatov, Alexei Torsors and rational points. Cambridge Tracts in Mathematics, 144. Cambridge University Press, Cambridge, 2001. viii+187 pp. ISBN: 0-521-80237-7
Lecturer: Olivier Wittenberg, Institut de Mathématique d’Orsay. Title: Around the inverse Galois problem
The inverse Galois problem asks whether any finite group can be realised as the Galois group of a Galois extension of the rationals. This problem and its refinements have stimulated a large amount of research in number theory and algebraic geometry in the past century, ranging from Noether's problem (letting X denote the quotient of the affine space by a finite group acting linearly, when is X rational?) to the rigidity method (if X is not rational, does it at least contain interesting rational curves?) and to the arithmetic of unirational varieties (if all else fails, does X at least contain interesting rational points?). The goal of the lecture series will be to provide an introduction to these topics.