tailieunhanh - Đề tài " Finite and infinite arithmetic progressions in sumsets "

We prove that if A is a subset of at least cn1/2 elements of {1, . . . , n}, where c is a sufficiently large constant, then the collection of subset sums of A contains an arithmetic progression of length n. As an application, we confirm a long standing conjecture of Erd˝s and Folkman on complete sequences. o | Annals of Mathematics Finite and infinite arithmetic progressions in sumsets By E. Szemer redi and V. H. Vu Annals of Mathematics 163 2006 1 35 Finite and infinite arithmetic progressions in sumsets By E. Szemeredi and V. H. Vu Abstract We prove that if A is a subset of at least cn1 2 elements of 1 . n where c is a sufficiently large constant then the collection of subset sums of A contains an arithmetic progression of length n. As an application we confirm a long standing conjecture of Erdos and Folkman on complete sequences. 1. Introduction For a finite or infinite set A of positive integers Sa denotes the collection of finite subset sums of A Sa s s x B c A BI . IxeB Two closely related notions are that of lA and l A lA denotes the set of numbers which can be represented as a sum of l elements of A and l A denotes the set of numbers which can be represented as a sum of l different elements of A respectively. If l A then l A is the empty set. It is clear that Sa A J A One of the fundamental problems in additive number theory is to estimate the length of the longest arithmetic progression in Sa Ia and l A respectively. The purpose of this paper is multi-fold. We shall prove a sharp result concerning the length of the longest arithmetic progression in Sa. Via the proof we would like to introduce a new method which can be used to handle many other problems. Finally the result has an interesting application as we can use it to settle a forty-year old conjecture of Erdos and Folkman concerning complete sequences. Research supported in part by NSF grant DMS-0200357 by an NSF CAREER Grant and by an A. Sloan Fellowship. 2 E. SZEMEREDI AND V. H. VU Theorem . There is a positive constant c such that the following holds. For any positive integer n if A is a subset of n with at least cn1 2 elements then Sa contains an arithmetic progression of length n. Here and later n denotes the set of positive integers between 1 and n. The proof Theorem introduces a new and useful