On Sidon sets in a random set of vectors

Abstract

For positive integers $d$ and $n$, let $[n{]}^d$ be the set of all vectors $(a_1,a_2,\dots ,a_d)$, where $a_i$ is an integer with $0\le a_i\le n-1$. A subset $S$ of $[n{]}^d$ is called a \emph{Sidon set} if all sums of two (not necessarily distinct) vectors in $S$ are distinct. In this paper, we estimate two numbers related to the maximum size of Sidon sets in $[n{]}^d$. First, let ${\mathcal{Z}}_{n,d}$ be the number of all Sidon sets in $[n{]}^d$. We show that $\log ({\mathcal{Z}}_{n,d})=\Theta (n^{d/2})$, where the constants of $\Theta$ depend only on $d$. Next, we estimate the maximum size of Sidon sets contained in a random set $[n{]}_p^d$, where $[n{]}_p^d$ denotes a random set obtained from $[n{]}^d$ by choosing each element independently with probability $p$.

arXiv comment14 pages, 1 figure, title was modified