Golomb ruler

The Golomb ruler was named for Solomon W. Golomb and discovered independently by Sidon (1932) and Babcock (1953). Sophie Piccard also published early research on these sets, in 1939, stating as a theorem the claim that two Golomb rulers with the same distance set must be congruent. This turned out to be false for six-point rulers, but true otherwise.

There is no requirement that a Golomb ruler be able to measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proved that no perfect Golomb ruler exists for five or more marks. A Golomb ruler is optimal if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, but proving the optimal Golomb ruler (or rulers) for a specified order is computationally very challenging.

Distributed.net has completed distributed massively parallel searches for optimal order-24 through order-28 Golomb rulers, each time confirming the suspected candidate ruler.

Currently, the complexity of finding optimal Golomb rulers (OGRs) of arbitrary order n (where n is given in unary) is unknown. In the past there was some speculation that it is an NP-hard problem. Problems related to the construction of Golomb rulers are provably shown to be NP-hard, where it is also noted that no known NP-complete problem has similar flavor to finding Golomb rulers.

Definitions

Golomb rulers as sets

A set of integers ${\displaystyle A=\{a_1,a_2,...,a_m\}}$ where ${\displaystyle a_1<a_2<...<a_m}$ is a Golomb ruler if and only if

${\displaystyle \text{for all }i,j,k,l\in \left\{1,2,...,m\right\}\text{such that }i\ne j\text{ and }k\ne l,a_i-a_j=a_k-a_l⟺i=k\text{ and }j=l.}$

The order of such a Golomb ruler is ${\displaystyle m}$ and its length is ${\displaystyle a_m-a_1}$. The canonical form has ${\displaystyle a_1=0}$ and, if ${\displaystyle m>2}$, ${\displaystyle a_2-a_1<a_m-a_{m-1}}$. Such a form can be achieved through translation and reflection.

Golomb rulers as functions

An injective function ${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$ with ${\displaystyle f(1)=0}$ and ${\displaystyle f(m)=n}$ is a Golomb ruler if and only if

${\displaystyle \text{for all }i,j,k,l\in \left\{1,2,...,m\right\}\text{such that }i\ne j\text{ and }k\ne l,f(i)-f(j)=f(k)-f(l)⟺i=k\text{ and }j=l.}$

The order of such a Golomb ruler is ${\displaystyle m}$ and its length is ${\displaystyle n}$. The canonical form has

${\displaystyle f(2)<f(m)-f(m-1)}$ if ${\displaystyle m>2}$.

Optimality

A Golomb ruler of order m with length n may be optimal in either of two respects:

• It may be optimally dense, exhibiting maximal m for the specific value of n,
• It may be optimally short, exhibiting minimal n for the specific value of m.

The general term optimal Golomb ruler is used to refer to the second type of optimality.