The Erd\H{o}s-Szemer\'edi problem on sum set and product set

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\H os-Szemer'edi [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 $\mathrm{\mid }AA\mathrm{\mid }<c\mathrm{\mid }A\mathrm{\mid }$, then $\mathrm{\mid }A+A\mathrm{\mid }>c^{\mathrm{\prime }}\mathrm{\mid }A{\mathrm{\mid }}^2$ (see Theorem 1). A quantitative version of this phenomenon combined with Pl"unnecke type of inequality (due to Ruzsa) permit us to settle completely a related conjecture in [E-S] on the growth in $k$. If $$g(k)\equiv \text{min}\{\mathrm{\mid }A[1]\mathrm{\mid }+\mathrm{\mid }A\{1\}\mathrm{\mid }\}$$ over all sets $A\subset \Bbb Z$ofcardinality$|A| = k$andwhere$A[1]$(respectively,$A{1}$) refers to the simple sum (resp., product) of elements of $A$. (See (0.6), (0.7).) It was conjectured in [E-S] that $g(k)$ grows faster than any power of $k$ for $k\to \mathrm{\infty }$. We will prove here that $\ell n g(k)\sim\frac{(\ell n k)^2}{\ell n \ell n k}$ (see Theorem 2) which is the main result of this paper.