The Erdős–Szeméredi problem on sum set and product set

Summary The basic theme of this paper is the fact that if A is a finite set of integers, then the sum and product sets cannot both be small. A precise formulation of this fact is Conjecture 1 below due to Erd˝ os-Szemeredi (E-S). (see also (El), (T), and (K-T) for related aspects.) Only much weaker results or very special cases of this conjecture are presently known. One approach consists of assuming the sum set A + A small and then deriving that the product set AA is large (using Freiman's structure theorem) (cf. (N-T), (Na3)). We follow the reverse route and prove that if |AA| c � |A| 2 (see Theorem 1). A quantitative version of this phenomenon combined with the Plunnecke type of inequality (due to Ruzsa) permit us to settle completely a related conjecture in (E-S) on the growth in k .I f