Báo cáo toán hoc:" The inverse Erd˝s-Heilbronn problem o "

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: The inverse Erd˝s-Heilbronn problem o. | The inverse Erdos-Heilbronn problem Van H. Vu Department of Mathematics Rutgers University Piscataway NJ 08854 USA vanvu@ Philip Matchett Wood Department of Mathematics Rutgers University Piscataway NJ 08854 USA matchett@ Submitted Aug 14 2008 Accepted Jul 24 2009 Published Aug 7 2009 Mathematics Subject Classification 11P70 Abstract The famous Erdos-Heilbronn conjecture first proved by Dias da Silva and Hami-doune in 1994 asserts that if A is a subset of Z pZ the cyclic group of the integers modulo a prime p then A A min 2 A 3 p . The bound is sharp as is shown by choosing A to be an arithmetic progression. A natural inverse result was proven by Karolyi in 2005 if A c Z p Z contains at least 5 elements and A A 2 A 3 p then A must be an arithmetic progression. We consider a large prime p and investigate the following more general question what is the structure of sets A c Z pZ such that A A 2 e A Our main result is an asymptotically complete answer to this question there exists a function Ỗ p o 1 such that if 200 A 1 e p 2 and if A A 2 e A where ez e Ỗ 0 then A is contained in an arithmetic progression of length A A A 3. With the extra assumption that A 1 lOpp p our main result has Dias da Silva and Hamidoune s theorem and Karolyi s theorem as corollaries and thus our main result provides purely combinatorial proofs for the Erdos-Heilbronn conjecture and an inverse Erdos-Heilbronn theorem. 1 Introduction For A a subset of an abelian group we define the sumset of A to be the set of all sums of two elements in A namely A A a b a b E A V. Vu is supported by NSF grant DMS-0901216 and DOD grant AFOSAR-FA-9550-09-1-0167. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R100 1 and we define the restricted sumset of A to be the set of all sums of two distinct elements of A namely A A a b a b G A and a b . Sumsets in a general abelian group have been extensively studied see 31 for a survey and we will focus on sumsets of Z pZ the integers .