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.