Course Descriptions

16:642:588 - Arithmetic Combinatorics

Spring 2021 - Bharghav Narayanan

Course Description:

Arithmetic combinatorics lies in the intersection of number theory and combinatorics, and studies the behaviour of simple arithmetic operations, such as addition and multiplication, on finite sets of numbers. For example, under what conditions can we guarantee that a set of natural numbers contains a three-term arithmetic progression? How does the size of the sumset A + A differ from the size of A? What if we consider the sumset A+A and the product set A.A simultaneously? Anyone who enjoys either combinatorics and/or number theory should find something of interest in this course. Topics: This course will cover both classical and modern aspects of the subject and we will cover some subset of the following topics: • sumsets and their structure • the sum-product phenomenon and its applications in computer science • Szemeredi's theorem • Fourier analysis on finite abelian groups • geometric tools from incidence geometry • graph theoretic methods, and • algebraic techniques.

Prerequisites: 

Some familiarity with the basics of combinatorics and probability will be assumed.

Text: 

Tao and Vu - Additive combinatorics is the standard reference, but we will supplement this with other sources.

Schedule of Sections:

Previous Semesters:

  • Spring 2021 Prof. Narayanan

FALL 2016

Swastik Kopparty

Text: Tao & Vu, online references

Prerequisites: Graduate combinatorics, probability, algebra

Description: Arithmetic Combinatorics is the study of combinatorial questions involving arithmetic operations. This course will cover some classical and modern aspects of the subject.

Possible topics include:

  • sumsets
  • the sum-product phenomenon
  • Ramsey questions
  • Szemeredi's theorem
  • probabilistic methods
  • geometric methods
  • graph theoretic methods
  • algebraic methods
  • Fourier and group-representation methods
  • analytic methods