Solymosi's Sum-Product estimate

 I am writing this hub to describe a recent paper in mathematics by Jozsef Solymosi. I provide a link to the paper below. The paper proves a result concerning sums and products of real numbers. The result is not known to be optimal and generally not believed to be, so it serves as the introduction to a research problem. Nevertheless, Solymosi's paper has the best currently known result, so it is reasonable to believe that understanding it fully is all you need to get going. Expositions of this paper  have been written already, notably on Izabella Laba's blog to which I link below, but I'd like to write one here as, hopefully, the first in a series exploring possible improvements. Participation through comments is welcome.

Incidentally, the idea of doing research through a blog is currently coming into fashion on the web. Tim Gowers would like to write a paper with a large number of coauthors in the way one writes a story with a large number of coauthor's. (Each one writes one sentence!) If you'd like to join in, or read his description of how this is supposed to work, I provide a link to his blog below.

 Before going any further, I want to express what mathematical background the reader might need to understand this hub. First the reader should be familiar with the notion of a set. If the set is finite, the reader should be familiar with the notion of the number of elements in the set (its cardinality, if you will.) If A is a finite set, we will denote by |A|, the number of elements in A. Further, it would be helpful for the reader to be familiar with addition and multiplication of real numbers. Actually, this is a tricky business. I plan for my next hub to explain this topic fully. (It will be my first hub in the "Calculus for Cranks" series.) If you don't know what real numbers are, every time I mention real numbers, pretend that I am talking about rationals. I expect all my readers to know how to add, subtract, mutliply, and divide fractions. That's it.

Given a finite set of real numbers A, I will now define its sumset A+A, and its product set AA.

A+A={a+b: a and b are in A}  ;  AA={ab: a and b are in A}

In other words, the sumset is the set of distinct sums of two elements of A and the product set is the set of distinct products of two elements of A. Let us look at two examples.

Example 1:

A={1, ... , n}

A is the set of the first n natural numbers, an arithmetic progression if you will. Then

A+A={2,3,...,2n}

and has only 2n-1 elements, while AA is a rather large subset of {1, ... , n²}.

Example 2:

A={2,4,8, ..., 2ⁿ}

A is the set of the first n powers of 2, a geometric progression if you will. Then

AA={2²,2³, ... , 2²ⁿ}

and is pretty small, while A+A is rather large.

EXERCISE: Calculate |A+A|

The Sum Product problem:  Given a set A of real numbers with |A|=N, how small can the maximum of the numbers |A+A| and |AA| be?

For any given value of N, the answer to the above question is a number. Thus the full answer is a function of N, call it f(N). We don't really expect to find an exact formula for f(N). (Call us pessimists.) It would be enough to understand roughly how fast f(N) grows as N grows. How can we make this precise? We do it with O and Ω notation.

If f(N) and g(N) are two functions of N, we say that f(N) is O(g(N)) if there is a positive number C independent of N so that we always have f(N) ≤C g(N). Similarly, we say that f(N) is Ω(g(n)) if there is a positive number C so that

 f(N) ≥C g(N).

In what follows, we restrict our attention to f(N) being the smallest possible value of the maximum of the two numbers |A+A| and |AA| for any set A of N real numbers. (This is a kind of minimax. We pick A to be the set of a given size making this maximum smallest. It is somewhat mysterious what this set might look like.)

There is a very old guess by Erdös and Szemeredi about how fast f(N) might grow. They conjectured that for any α < 2 , one has that f(N) is Ω(N ^α). We abbreviate this by saying that f(N) is Ω(N^2-). You can think of this as meaning that f(n) is almost Ω(N²). This is consistent with the examples above. This conjecture is considered pretty important. The reader who solves it will be famous, at least in Hungary.

Now we are ready to state Solymosi's result which is weaker than the conjecture. (And he's alreadyfamous in Hungary.) He showed that f(N) is Ω(N^4/3-). How did he arrive at this? That is what will be explained in the rest of this hub.

We may assume our set A consist only of positive numbers.

Exercise: Why can we assume that?

We need a lemma saying essentially that most children belong to large families.

Lemma Suppose that N^α objects are put in N^β boxes. Then Ω(N^α) objects are in boxes containing Ω(N^α-β)objects

Proof Consider those boxes containing fewer than ½N^α-β objects. In all they contain fewer than ½N^α objects. Q.E.D.

Now we suppose that |A|=N, |A+A|=N^a,|AA|=N^b. We're looking for a lower bound on maximum of a and b. We define a multiplicative quadruplet to be an ordered quadruplet (s,t,u,v) of elements of A so that st=uv. Using the lemma with pairs (s,t) as the objects and products st as the holes, we see that there are Ω(N²) pairs which have products that can be represented in Ω(N^2-b) ways. Therefore there are Ω(N^4-b) multiplicative quadruplets.

Next we notice that whenever we have a multiplicative quadruplet (s,t,u,v) then it follows that s/u=v/t. Now we apply the lemma with multiplicative quadruplets being the objects and pairs (s,u) being the boxes, to see that there are Ω(N^4-b) quadruplets with the property that each one has (s,u) which appears in Ω(N^2-b) others. We denote the set of quotients s/u comingfrom these quadruplets as Q. For each quotient q in Q, we denote r(q) to be the number of representations s/u of q as a quotient of elements in A. Then for every q in Q, we have that r(q) is

 Ω(N^2-b). Finally, we observe

∑r(q)² = Ω(N^4-b),

where the sum on the left is taken over Q and represents the set of quadruplets with the good property.

It would be convenient if all the numbers r(q) were about the same. They may not be but we can sort them into boxes in which they are. Precisely, we let

Q_j={q in Q: 2^j ≤ r(q) < 2^j+1}

Clearly Q_jis empty unless 2^j ≤ N and unless 2^jis Ω(N^2-b). In particular, there are at most O(log N) nonempty sets Q_j and since log N grows slower than any power of N we see that there is a j so that

∑r(q)² = Ω(N^(4-b)-)

where the sum is taken over Q_j. Thus there are Ω(2^-2j N^(4-b)-) quotients in Q_j. We number these from smallest to largest,

q₁<q₂<...<q_M,

where M is Ω(2^-2jN^(4-b)-). We consider the pairs (s,u) of elements of A which have a particular quotient q_l. They lie on the line y=q_l x. (Notice we just switched to two dimensions!) Denote this set of points all on a line L_l. Now consider the consecutive sumsets L_l+L_l+1. They are disjoint because they lie between the consecutive lines y=q_lx and y=q_l+1x. Moreover no two pairs yield the same sum. (It's like summing points on the x-axis with points on the y-axis.) Thus

|L_l+L_l+1| ≈2^2j.

Now we take the union of the disjoint sumsets running over l and we get that the number of sums is Ω(N^(4-b)-). But each sum is a pair of elements in A+A. There are only N^2apairs of elements in A+A. Thus one of a or b is at least (4/3)-. Q.E.D.

That is the whole of Solymosi's argument. It is pretty simple as these things go. It does not solve the problem. I hope to write more hubs and perhaps discuss in the comments how one might hope to do better. Let me begin by giving a hint. What happens to the sums of points on non-consecutive lines?