On the number of sums and products
György Elekes · Acta Arithmetica · 1997
In what follows A will always denote a finite subset of the non-zero reals, and n the number of its elements. As usual, A + A and A · A stand for the sets of all pairwise sums {a + a ′ : a, a ′ ∈ A} and products {a · a ′ : a, a ′ ∈ A}, respectively. Also, |S | denotes the size of a set S. The following problem was posed by Erdős and Szemerédi (see [5]): For a given n, how small can one make |A + A | and |A · A | simultaneously? In other words, defining a lower estimate should be found for m(A): = max{|A + A|, |A · A|}, g(n): = min |A|=n m(A). R e m a r k. The philosophy behind the question is that either of |A + A| or |A · A | is easy to minimize—just take an arithmetic or geometric (i.e., exponential) progression for A. However, in both of these examples, the other set becomes very large. In their above mentioned paper, Erdős and Szemerédi managed to prove the existence of a small but positive constant c1 such that g(n) ≥ n 1+c1 for all n. (See also p. 107 of Erdős ’ paper [3].) Later on, Nathanson and K. Ford found the lower bounds n 32/31 and n 16/15, respectively [7]. The goal of this paper is to improve the exponent to 5/4. Theorem 1. There is a positive absolute constant c such that, for every n-element set A, c · n 5/4 ≤ max{|A + A|, |A · A|}.