tailieunhanh - Đề tài "The Erd˝os-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˝s-Szemer´di [E-S]. (see also [El], [T], o e 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. | Annals of Mathematics The Erd os-Szemer edi problem on sum set and product set By Mei-Chu Chang Annals of Mathematics 157 2003 939 957 The Erdos-Szemeredi problem on sum set and product set By Mei-Chu Chang 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 Erdos-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 IAA c A then A A c A 2 see Theorem 1 . A quantitative version of this phenomenon combined with the Pliinnecke 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 c z of cardinality A k and where A 1 respectively A 1 refers to the simple sum resp. product of elements of A. See . It was conjectured in E-S that g k grows faster than any power of k for k TO. Wp will Ỉ1ĨY1VÍ hnm thnt In ritỉA r -j Ợnt . mí1 whlr h is I Im mnin V V e w Hl pro v e neie biia b in g my Inln k see J- neoreiii J w inc 11 is b lie maul result of this paper. Introduction Let A B be finite sets of an abelian group. The sum set of A B is A B a b a G A b G B . We denote by hA A A h fold the h-fold sum of A. Partially supported by NSA. 940 MEI-CHU CHANG Similarly we can define the product set of A B and ft-fold product of A. AB ab I a G A b G B Ah A A h fold . If B b a singleton we denote AB by b A. In 1983 Erdos and Szemeredi E-S conjectured that for subsets of integers the sum set and the product set cannot both be small. Precisely they made the following conjecture. Conjecture 1 Erdos-Szemeredi . For any e 0 and any h G N there is