Cyclic Golomb ruler

Question

Golomb rulers are widely researched, but apart from an old problem by Dudeney I could not find anything about cyclic Golomb rulers.

A cyclic Golomb ruler would be a circle of integer length on which markers are placed at integer distances, such that all distances between two different markers are different. Clearly with $n$ marks there are $n(n-1)$ distances to consider. A perfect cyclic Golomb ruler (PCGR) with $n$ marks would have all distances $1,\ldots,n(n-1)$ and a total length of $n(n-1)+1$. The $n$ marks break the circle in $n$ pieces of integer length, giving a sequence of $n$ consecutive piece-lengths. This can be done in $2n$ different ways (we can start at $n$ different points and then move either clockwise or counterclockwise). We will use the lexicographically smallest sequence to describe the configuration.

Following things are easy to show:

. $[1,2]$ is the unique PCGR with two marks (length 3).

. $[1,2,4]$ is the unique PCGR with three marks (length 7).

. $[1,3,2,7]$ and $[1,2,6,4]$ are the only PCGRs with four marks (length 13).

. There is no PCGR with five marks (Oops, this turns out to be untrue, but I found the flaw in the argument).

And although it is very easy to show that there are no "normal" perfect Golomb rulers with more than $4$ marks, I have not yet been able to come up with a proof that there is no PCGR with more than $4$ marks (because it is not true).

Does anyone know how to prove this, or maybe provide references to research on this subject?

Answer 1

These are commonly known as cyclic difference sets (CDSs) and perfect CDSs. A search for those terms should lead to many references.

In particular the pages starting at http://www.inference.org.uk/cds/index.htm are an exploration of CDSs by Kris Coolsaet which includes several examples and construction methods.

Via the Wayback Machine we can find a PDF list of known perfect CDSs at https://web.archive.org/web/20101226230341/http://www.ccrwest.org/diffsets/ds_list.pdf

The representation there is:

• $v$ = length
• $k$ = number of marks
• $t$ = multiplicity of each difference
• $n=k-t$
• listed numbers are the position around the circle

so those with $t=1$ are perfect CDSs equivalent to those defined in the OP.

A perfect CDS with $5$ marks does exist, given as $3,6,7,12,14$ in the last link and equivalent to $[1,3,10,2,5]$ in the OP's representation.