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 Plunnecke-Ruzsa.

• 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 Balog-Szemeredi-Gowers theorem, and I plan to only give Gowers's proof of it (it is much simpler than the Balog-Szemeredi proof, and gives much better dependence among the parameters). Nonetheless, I wrote a note on the Balog-Szemeredi 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 multi-sum extenion of Balog-Szemeredi-Gowers 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 Balog-Szemeredi-Gowers 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 walk-through of one of my unpublished results.)

• Click here for a note by Ben Green on Solymosi's sum-product theorem over the complex numbers.

• Click here for a note I wrote on the Bourgain-Katz-Tao Theorem.

• Click here for that article I mentioned at the end of class by Philip Matchett-Wood, Melanie Matchett-Wood, and Van Vu that shows how one can transfer many sum-product problems from the complex numbers to finite fields Fp. J. P. Serre wrote about similar ideas in this note. (Although, the bounds for many sum-product 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-(Heath-Brown) Theorem on three-term 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, basis-free formula'', whereas the way we applied Fourier Inversion required choosing a basis. This is common in Fourier-analytic 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 Littlewood-Offord (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 most-used 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 sum-product inequalities, in particular this article by Mei-Chu Chang (she uses estimates in the spirit of Rudin, but they are not exactly the same as udin's inequalities).