Bounds for generalized Sidon sets.

Let Γ be an abelian group and g ≥ h ≥ 2 be integers. A set A ⊂ Γ is a C h [ g ] -set if given any set X ⊂ Γ with | X | = h , and any set { k 1 , … , k g } ⊂ Γ , at least one of the translates X + k i is not contained in A . For any g ≥ h ≥ 2 , we prove that if A ⊂ { 1 , 2 , … , n } is a C h [ g ] -set in Z , then | A | ≤ ( g − 1 ) 1 / h n 1 − 1 / h + O ( n 1 / 2 − 1 / 2 h ) . We show that for any integer n ≥ 1 , there is a C 3 [ 3 ] -set A ⊂ { 1 , 2 , … , n } with | A | ≥ ( 4 − 2 / 3 + o ( 1 ) ) n 2 / 3 . We also show that for any odd prime p , there is a C 3 [ 3 ] -set A ⊂ F p 3 with | A | ≥ p 2 − p , which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer h ≥ 3 , there is a C h [ h ! + 1 ] -set A ⊂ { 1 , 2 , … , n } with | A | ≥ ( c h + o ( 1 ) ) n 1 − 1 / h . A set A is a weak C h [ g ] -set if we add the condition that the translates X + k 1 , … , X + k g are all pairwise disjoint. We use the probabilistic method to construct weak C h [ g ] -sets in { 1 , 2 , … , n } for any g ≥ h ≥ 2 . Lastly we obtain upper bounds on infinite C h [ g ] -sequences. We prove that for any infinite C h [ g ] -sequence A ⊂ N , we have A ( n ) = O ( n 1 − 1 / h ( log n ) − 1 / h ) for infinitely many n , where A ( n ) = | A ∩ { 1 , 2 , … , n } | . [ABSTRACT FROM AUTHOR]