Math 8803/4803 (additive Combinatorics)
Click here for a copy of
the syllabus.
Office Hours will be Tuesday and Friday from 2:00 to 3:00.
Homework 1 (to be turned in at a date to be specified later).

First, click here for a note
on the Erdos Multiplication Table Theorem and the second moment method
(basically, the step I missed in class in the variance computation is
that all one needs is an UPPER BOUND on the second moment, which then
allows one to drop the floor functions from various steps.)

Page 5, problem 1.1.3. Establish the first part of that problem.
And then use that fact to solve the following problem .

Click here for a note
on what I discussed at the end of class today.

Work problem #1.3.3.

Work problem #1.3.5.

Work Problem #1.5.1.

Turn these problems in during class on Fri. Feb. 18.

Click here for a shocking new easy proof of
PlunneckeRuzsa.

Incidentally, the visitor in our class today (Feb. 11), sitting
in the back, was Nets Katz. In case you don't know who he is, he recently
was the coauthor on two major results in discrete mathematics. One of
these was his resolution of the Erdos Distance Conjecture (a problem that
Tom Trotter and several more of our senior discrete math faculty had worked
on for years without success), which
you can read about by going here ... and
another was his recent breakthrough improvement on the CAP set problem,
which you can read about by going here .

On Monday we will discuss the BalogSzemerediGowers theorem,
and I plan to only give Gowers's proof of it (it is much simpler than
the BalogSzemeredi proof, and gives much better dependence among the
parameters). Nonetheless, I wrote a note on the BalogSzemeredi proof
once, which you can read by going here .
The proof makes use of the Szemeredi Regularity Lemma, which you can read
about by going here . Finally, I proved
a certain multisum extenion of BalogSzemerediGowers with my previous
ph.d. student Evan Borenstein, which you can read about by going
here (to appear in SIAM J. of Discrete Math.).

Go here for an expository note
on the BalogSzemerediGowers theorem written by Seva (Vsevold) Lev. It
is the note that I have been using for my lecture.

For a note on the size of {a^2 + b : a,b in A} from class today,
go here .

Go here for the first set
of problems in the second HW. (This is a walkthrough of one of my
unpublished results.)

Click here for a note
by Ben Green on Solymosi's sumproduct theorem over the complex numbers.

Click here for a note I wrote
on the BourgainKatzTao Theorem.

Click here for
that article I mentioned at the end of class by Philip MatchettWood,
Melanie MatchettWood, and Van Vu that shows how one can transfer
many sumproduct problems from the complex numbers to finite fields
Fp. J. P. Serre wrote about similar ideas in this note. (Although, the bounds for many sumproduct
problems are stronger in C than in Fp; so, this method is often not
very helpful.)
Work problem #4.2.9. And work this problem.
I've started writing up some more problems related to counting
lattice points inside a rectangle (motivated by a question Daniel asked
me about once), but have not yet finished it. It makes use of Fourier
analysis over R^2, which has a somewhat different character from the
discrete Fourier analysis we have been discussing in class (which is why
I have decided to write a note and some problems about it  I don't
plan to cover it in class). To see what I have written so far, click
here .

To see a proof of the quantitative Varnavides theorem I discussed
in class, go here (this is a paper of mine where the proof appears  see
Lemma 3.1). Another paper of mine where the proof appears is
here .
(See lemma 1). In the proof I presented in class today, you don't
actually need the condition d  e  it turns out all that was needed
is that e = dk, where k is less than M... this takes care of all the ``wrap
around'' issues we were having to deal with.

For a note by Ben Green on the Szemeredi(HeathBrown) Theorem on
threeterm progressions, click here .
Note that there is a typo on page 2  the N^7/3 should be N^3.

I have revised and expanded that last HW on counting
lattice points. Basically, by continuing the analysis it turns out
that the Poisson Summation Formula for R^2 falls out naturally
(although I had planned to also discuss PSF, I didn't expect that it
would fall out so naturally; and, for all I know this is a new proof
of PSF!). What's interesting is that the PSF is a ``global,
basisfree formula'', whereas the way we applied Fourier Inversion
required choosing a basis. This is common in Fourieranalytic arguments:
in the final analysis the choice for basis (or vector space, or
subgroup, or ...) disappears and one is only left with global properties
of the object under study. Click
here for the revised HW.

There are some REALLY good talks on Discrete Analysis (which includes
additive combinatorics) that you can view online at the Isaac Newton
Institute. Click here to see some of these talks.

I wanted to point out a nice essay written by Terry Tao
titled ``There's more to mathematics than rigor and proofs''. Click
here to see this article.

Click here for a combinatorial proof
that if A is a subset of F_p* and A > p^(4/5) then 3A.A= F_p.
This is slightly weaker than the exponent 3/4 that FOurier methods
give. Perhaps someone will see how to improve it so that the result
matches what one can get from Fourier methods (or find an altogether
different combinatorial proof).

Click here for a short
note on Holder's inequality and basic Fourier analysis.

We started discussing Freiman's theorem today (April 4), and
I will put up a note on Ruzsa's ``Good Modeling Lemma''  an
essential ingredient in Ruzsa's proof of Freiman, as we
discussed  that I wrote a few years ago soon
(I want to polish it some more first). In the meantime,
here
are some notes written by Andrew Granville that contain a full treatment of
Freiman's theorem, among dozens of other topics.

For the note on the ``good modeling lemma'' I promised,
click here (I think it is a better
presentation than in the Granville note). Click here for a recent paper due to myself, Izabella Laba and Olof Sisask
where we generalize Ruzsa's lemma to two sets A and B (see Prop. 5.1).
(This should also show you how Ruzsa's lemma can be used in applications.)

Click here for the next
homework.

Click here for another combinatorial
proof that 3(A.A) = F_p  this time with A > (1+o(1))p^{3/4}.
The proof is basically just a trivial deduction from some theorems of
Javier Cilleruelo on Sidon Sets. Furthermore, Javier's theorem can
be used to show that if A > (1+o(1))p^{3/4} then 2(A.A) contains F_p^*.

Click here for a
writeup of the Fourier proof of discrete LittlewoodOfford (that I
covered in class today). Click
here for a note on the combinatorial proofs of Erdos.

Tomorrow (Wednesday, Apr. 20) I will be speaking about
the Large Sieve. Click here
for a note I wrote a few years ago about it.

Today I will be speaking on Chang's Structure Theorem, which is
a significant part of her proof of Freiman's Theorem; furthermore, it is
one of the mostused lemmas/theorems (structure theorem)
in Additive Combinatorics  it is very
powerful! Ben Green wrote a very nice note on this, which you can see by
going here: here .
(Skip to Sec. 2.)

Today (Apr. 25) we will be discussing Rudin's Inequality,
which has a proof similar to Chang's Structure Theorem. See
this note by Ben Green (which also has
another exposition of Chang's Theorem). Rudin's inequality is an essential
ingredient in many major results in additive combinatorics. One place where
it appears is in theorems about the existence of long APs in sumsets.
See, for example, this expository article
written by Olof Sisak. Another place where it has been useful (rather
surprisingly!) is in the theory of sumproduct inequalities, in particular
this article by MeiChu Chang
(she uses estimates in the spirit of Rudin, but they are not exactly the
same as udin's inequalities).