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.


1 Answer 1


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".


You must log in to answer this question.

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