The Erdos-Szemereldi problem on sum set and product set

• 成果类型: Article
• 署名作者: Chang, MC
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2003.157.939
• 发表日期: 2003
• 页码: 939-957
• 关键词: NUMBER

摘要

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 Erdos-Szemeredi [E-S]. (see also [Ell, IT], 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 the Plunnecke 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) equivalent to min{\A[1]\ + \A{1}\} over all sets A subset of Z of cardinality \A\ = k and where A[1] (respectively, Af 11) 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 --> infinity. We will prove here that ln g(k) similar to (ln k)(2)/ln ln k (see Theorem 2) which is the main result of this paper.