4
$\begingroup$

Given a number $m\in\mathbb N$, let $\mathbb Z_m=\{0,1,\dots,m-1\}$ denote the ring of integers modulo $m$ (although we won't need multiplication, so any cyclic group of order $m$ will do). Given a second number $k\in\mathbb N$ I'm looking for subsets of $k$ elements from $\mathbb Z_m$ such that no pair-wise difference occurs more than once. More formally, I'm looking for some $A\subset\mathbb Z_m$ with $\lvert A\rvert=k$ and

$$\forall a,b,c\in A: \lvert\{a,b,c\}\rvert=3\rightarrow a+b-c\not\in A\pmod m$$

  • Is there a name for such a kind of set? I guess it might be somehow related to Golomb rulers, but the cyclic nature is not common to rulers as far as I know.
  • Is there a known method to efficiently enumerate such sets for given $m$ and $k$?
  • Is there a known theorem concerning the existence of such subsets for specific $m$ and $k$?

I know I'm asking three distinct questions here, but I very much hope that someone may be able to address more than one, perhaps by providing a good reference. Knowing a name will probably help me locate suitable literature. But answers addressing only one of these questions are welcome as well.

Update: It seems that for the special case of $m=k^2-k+1$ where every possible difference has to actually occur exactly once, the kind of set I defined would be called an $(m,k,1)$ cyclic difference set. I'm still interested in a more general term for cases where some differences are missing.

$\endgroup$

1 Answer 1

2
$\begingroup$

No doubt this answer comes too late, but for a good record: such sets are called Sidon sets (in $\mathbb Z_m$), and there is a vast amount of literature about them, starting from this Wikipedia entry. There is no way to efficiently enumerate such sets. For your third question, since a subset of a Sidon set is (trivially) Sidon, you are in fact asking how large can a Sidon subset of the group $\mathbb Z_m$ be; this problem has received much attention also, one can find lots of references just googling for "Sidon sets".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .