2

Let $n$ be a positive integer. If $k$ is an integer such that $2^{k+1} \leq n$, then $A=\{1,2,2^2,...,2^{k-1},2^k\}$ is a subset in $\mathbb{Z}_n$ such that $|(A+x) \cap A| \leq 1$, for all $x \in \mathbb{Z}_n$, $x \neq 0$.

Indeed, if $y,z \in (A+x)\cap A$, $y=2^a+x=2^b$ and $z=2^c+x=2^d$. So, $x=2^b-2^a=2^d-2^c$ and $2^c+2^b=2^d+2^a$ $\implies$ ($a=b$ and $d=c$) or ($a=c$ and $b=d$) $\implies x=0$ or $y=z$.

$|A|=k+1$. Is it possible to find a subset $B$ with $|B|>k+1$ and such that $|(B+x) \cap B| \leq 1$, for all $x \in \mathbb{Z}_n$, $x \neq 0$.

Thanks in advance.

francis-jamet
  • 2,254

1 Answers1

2

This is very closely related to Golomb rulers, which are the analogous sets in $\mathbb Z$ rather than $\Bbb Z_n$. Golomb rulers are themselves essentially Sidon sets. Fortunately, many good constructions of Sidon sets are actually Sidon sets modulo $n$ for certain types of integers $n$, such as those of the form $p^2-p$ or $p^2-1$ or $p^2+p+1$ for primes $p$. See section 2.2 of my paper with Kevin O'Bryant for some of these constructions gathered in one place.

The powers of $2$ give a Sidon set in $\Bbb Z_n$ of size about $\log n$. Generally speaking, the largest Sidon sets should be much larger, around $\sqrt n$. Admittedly the above reference doesn't prove this for all $n$ (just those special $n$), but they should get you calibrated at least.

Greg Martin
  • 78,820