Sums, Products, and Growth of Sets

Addition and multiplication are two of the first mathematical concepts that we learn about as young children, and one might expect that we know everything that there is to know about these two simple operations. However, for many of the most famous open problems in mathematics, there is an interaction between the two operations which is difficult to get a grip on. Take for instance the Goldbach Conjecture, which states that any even integer greater than 2 can be written as a sum of two primes. The basic object we are working with here is the set P of all prime numbers, which is defined via the concept of multiplication. We then ask an additive question about this set: does the set P+P of all sums of pairs of primes contain the set of all (sufficiently large) even integers? We call P+P the sum set of P. Moreover, given any set A of integers, we can consider its sum set A+A. The set of all products of pairs of elements from A is called the product set, and denoted AA. This project is primarily concerned with the sum-product problem. Roughly speaking, we would like to show that at least one of A+A or AA is large, no matter what set A we start with. To get an idea about this we can consider some simple examples. What kind of set might we construct in order to try and make A+A small? We need to enforce that A+A contains a fairly small number of elements that repeat many times. We could take A={1,2,,100}, which gives A+A={2,3,,200}. In this example, the sum set is about twice as large as the original set, and it turns out that the sum set is always at least twice the size of the original set (minus one). More generally, we could take A to be an arithmetic progression of any size, and we will reach the same conclusion that the sum set is slightly less than twice the size of the original set; the smallest it can possibly be. But in such situations as above where A is an arithmetic progression, it turns out that the product set AA will be rather large, with very few repetitions occurring. So, according to these examples at least, it appears that, if the sum set is small then the product set will be large. A similar situation occurs if we reverse the roles of addition and multiplication. The sets which have minimal sized product sets are geometric progressions. However, if A is a geometric progression then A+A is very large indeed. These extreme cases motivate a more general conjecture of Erdos and Szemerédi, which claims that at least one of A+A or AA is close to the maximum possible size for any finite set of integers A. After 38 years, this question remains wide open. The Erdos-Szemerédi Conjecture lies at the heart of this project, and the basic goal is to improve our understanding of this conjecture, including making new quantitative progress. We will also consider several interesting and important problems of a similar spirit, such getting strong bounds in the case when the product set is very small.

Conflict between notions of additive and multiplicative structure is a repeating theme in major open problems in mathematics. This conflict arises itself in the Twin Prime Conjecture, the Goldbach Conjecture and the abc Conjecture, amongst other problems, and it lies at the very heart of the field of sum-product theory: to summarise this area as succinctly as possible, one may say that sum-product type results are characterised as statements proving that additive and multiplicative structure cannot coexist. Let's be a little more specific. Given a finite set of n numbers, we can form their sum set by taking all pairs from the set and taking their sum. The product set is defined similarly. How large can these new sets be? Are they necessarily much larger than the original set? By taking the original set to be an arithmetic progression, we arrive at an example whereby the sum set is not much bigger than the original set (the set essentially doubles in size, which is the smallest possible growth). However, in this case, the product set turns out to be very large. Conversely, we can restrict the growth of the product set by taking our initial set to be a geometric prpgression, but in this case the sum set is very large. This motivates a beautiful open problem of Erds and Szemerédi; show that, for any given initial set, at least one of the sum set or product set is very large. There has been considerable progress on this problem in the last 50 years since it was first stated, but the precise quantitative solution to the full conjecture remains out of reach. We have considered many variations and generalisations of this problem during this project. A key theme has been to better understand the relationship between convexity and additive structure. Some new elementary arguments have given some progress here. In particular, the method of "squeezing" has been developed and applied during the time of this project with strong results. The relationship with problems in discrete geometry was also explored, and one of the highlights was a quantitative breakthrough concerning the number of distinct dot products determined by a point set in the plane.