2004/02/17 by Mei-Chu Chang
Mathematics · #math.CO
published as Ann. of Math. (2), Vol. 157 (2003), no. 3, 939--957 · 19 pages published version
arxiv created 2004/02/17 · arxiv updated 2009/12/01
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édi [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|, then |A+A| > c^′ |A|2 (see Theorem 1). A quantitative version of this phenomenon combined with Plünnecke 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) ≡ min\|A[1]| + |A\1\|\ over all sets A⊂ \Bbb Z of cardinality |A| = k and where 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→∞. We will prove here that ℓ n g(k)∼((ℓ n k)2)/(ℓ n ℓ n k) (see Theorem 2) which is the main result of this paper.