Bounds for generalized Sidon sets

Abstract

Let $\Gamma$ be an abelian group and $g\ge h\ge 2$ be integers. A set $A\subset \Gamma$ is a $C_h[g]$-set if given any set $X\subset \Gamma$ with $|X|=k$, and any set $\{k_1,\dots ,k_g\}\subset \Gamma$, at least one of the translates $X+k_i$ is not contained in $A$. For any $g\ge h\ge 2$, we prove that if $A\subset \{1,2,\dots ,n\}$ is a $C_h[g]$-set in $\mathbb{Z}$, then $|A|\le (g-1{)}^{1/h}{n}^{1-1/h}+O(n^{1/2-1/2h})$. We show that for any integer $n\ge 1$, there is a $C_3[3]$-set $A\subset \{1,2,\dots ,n\}$ with $|A|\ge (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\subset {\mathbb{F}}_p^3$ with $|A|\ge p^2-p$, which is asymptotically best possible. Using the projective norm graphs from extremal graph theory, we show that for each integer $h\ge 3$, there is a $C_h[h!+1]$-set $A\subset \{1,2,\dots ,n\}$ with $|A|\ge (c_h+o(1))n^{1-1/h}$. A set $A$ is a \emph{weak $C_h[g]$-set} if we add the condition that the translates $X+k_1,\dots ,X+k_g$ are all pairwise disjoint. We use the probabilistic method to construct weak $C_h[g]$-sets in $\{1,2,\dots ,n\}$ for any $g\ge h\ge 2$. Lastly we obtain upper bounds on infinite $C_h[g]$-sequences. We prove that for any infinite $C_h[g$]-sequence $A\subset \mathbb{N}$, we have $A(n)=O(n^{1-1/h}(\log n{)}^{-1/h})$ for infinitely many $n$, where $A(n)=|A\cap \{1,2,\dots ,n\}|$.

10 pages. arXiv admin note: text overlap with arXiv:1306.6044