2022 Graduate Summer School Course Descriptions

Week 1 - July 18-22, 2022

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: 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.

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.

Week 2 - July 25-29, 2022

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, Facebook. 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: 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.

Suggested reading: Daan van Gent, Polynomial-time algorithms in algebraic number theory. These are the course notes of preparatory lectures that were presented in July, 2021. They can be found at https://pub.math.leidenuniv.nl/~gentdmhvan/pdf/pcmi.pdf

Lecturer: Melanie Matchett Wood, Harvard University. 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 - August 1-5, 2022

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: Jan Vonk, Leiden University. Title: Singular moduli for real quadratic fields 

Singular moduli are the special values of the modular j-invariant at imaginary quadratic arguments. They are algebraic integers with rich prime factorisations, and play a central role in the theory of complex multiplication. Guided by explicit computations, an analogue for real quadratic fields has recently taken shape, based on the notion of rigid meromorphic cocycles. This course will be an introduction to the theory of rigid cocycles. We will discuss the different arithmetic invariants they produce, and their relations to Hilbert's 12th problem, the Birch and Swinnerton-Dyer conjecture, and the work of Gross and Zagier. The focus will be on how explicit computations with rigid cocycles can be carried out, how they influenced the development of the theory, and the computational questions that lie ahead in the further development of this theory.

Lecturer: Olivier Wittenberg, Institut Galilée – Université Sorbonne Paris Nord. 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.