MATH 254A, Winter 2003

Terence Tao

Some highlights of arithmetic combinatorics

MW 3-4:30, MS 6221

• This course is concered with combinatorial estimates associated with arithmetic operations such as addition, subtraction, and multiplication.  A typical question is the following: if A is a set of N integers, how large or small can the sum-set A+A := { x + y: x,y in A }, the difference set A-A := { x - y: x,y in A }, and the product set A*A := { xy: x,y in A } be, and how are the sizes of these sets related?  A typical result is the following: if |A+A| <= CN, then |A+A+A| <= C^3 N (this is part of Plunnecke's theorem).  We will explore these types of questions and applications to problems such as the Kakeya

• set problem.

• The course is almost entirely self-contained, relying mostly on elementary combinatorics and on elementary Fourier analysis, although a little bit of number theory, graph theory, and even ergodic theory(!) will also enter.  Note though that despite the elementary nature of the material, some of the arguments here are quite deep and non-trivial.  There are no prerequisites, though some exposure to analysis (particularly in proving various types of estimates) will probably help. For instance, material from 245A will be helpful but not absolutely necessary.

•
• Topics to be covered include:
• Plunnecke's theorem, and other sumset results
• The (Gowers-)Balog-Szemeredi theorem, and applications to the Kakeya problem
• Freiman's theorem on sumsets and arithmetic progressions
• Szemeredi's theorem on arithmetic progressions (Roth's argument for progressions of length 3, Gowers' argument for progressions of length 4,
Furstenburg's ergodic theory argument)
• Elekes's theorem on A+A and A*A
If time permits:
• Bourgain's refinement of Roth's (and Heath-Brown's) theorem
• Chang's improved version of Freiman's theorem
• Bourgain's solution to the discretized ring conjecture
• There is no text; printed notes will be distributed during the course and will also be available on the web.  There are no examinations for this course, though there will be non-mandatory homework.