Golomb ruler

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\neq j{\text{ and }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ and }}j=l.}$[10]

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.

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\neq j{\text{ and }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ and }}j=l.}$[11]^:236

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}$.

A Golomb ruler of order m with length n may be optimal in either of two respects:[11]^:237

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

Golomb rulers are used within Information Theory related to error correcting codes.[13]

Golomb rulers are used in the selection of radio frequencies to reduce the effects of intermodulation interference with both terrestrial[14] and extraterrestrial[15] applications.

Golomb rulers are used in the design of phased arrays of radio antennas. Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at AM tower or cell sites. In radio astronomy one-dimensional synthesis arrays can have the antennas in a Golomb ruler configuration in order to obtain minimum redundancy of the Fourier component sampling.[16][17]

Multi-ratio current transformers use Golomb rulers to place transformer tap points.

The following construction, due to Paul Erdős and Pál Turán, produces a Golomb ruler for every odd prime p.[12]

${\displaystyle 2pk+(k^{2}\,{\bmod {\,}}p),k\in [0,p-1]}$