thumb|Golomb ruler of order 4 and length 6. This ruler is both optimal and perfect.
thumb|The perfect circular Golomb rulers (also called [[difference sets) with the specified order. (This preview should show multiple concentric circles. If not, click to view a larger version.)]]
In mathematics, a Golomb ruler is a set of marks at integer positions along a ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its order, and the largest distance between two of its marks is its length. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. Golomb rulers can be viewed as a one-dimensional special case of Costas arrays.
The Golomb ruler was named for Solomon W. Golomb and discovered independently by and . 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.
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.
Golomb rulers have practical applications in information theory and error correction, radio frequency selection and antenna placement, as well as current transformers.
Definitions
Golomb rulers as sets
A set of integers <math>A = \{a_1,a_2,...,a_m\}</math> where <math>a_1 < a_2 < ... < a_m</math> is a Golomb ruler if and only if
:<math>\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.</math>
The order of such a Golomb ruler is <math>m</math> and its length is <math>a_m - a_1</math>. The canonical form has <math>a_1 = 0</math> and, if <math>m>2</math>, <math>a_2 - a_1 < a_m - a_{m-1}</math>. Such a form can be achieved through translation and reflection.
Golomb rulers as functions
An injective function <math>f:\left\{1,2,...,m\right\} \to \left\{0,1,...,n\right\}</math> with <math>f(1) = 0</math> and <math>f(m) = n</math> is a Golomb ruler if and only if
:<math>\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.</math>
The order of such a Golomb ruler is <math>m</math> and its length is <math>n</math>. The canonical form has
:<math>f(2)<f(m)-f(m-1)</math> if <math>m>2</math>.
Optimality
A Golomb ruler of order <var>m</var> with length <var>n</var> may be optimal in either of two respects:
Practical applications
[[File:Golomb ruler conference room.svg|thumb|300px|Example of a conference room with proportions of a [0, 2, 7, 8, 11] Golomb ruler, making it configurable to 10 different sizes.
Radio frequency selection
Golomb rulers are used in the selection of radio frequencies to reduce the effects of intermodulation interference with both terrestrial and extraterrestrial applications.
Radio antenna placement
Golomb rulers are used in the design of phased arrays of radio antennas. 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.
Current transformers
Multi-ratio current transformers use Golomb rulers to place transformer tap points.
Methods of construction
A number of construction methods produce asymptotically optimal Golomb rulers.
Erdős–Turán construction
The following construction, due to Paul Erdős and Pál Turán, produces a Golomb ruler for every odd prime p.
:<math>2pk+(k^2\,\bmod\,p),k\in[0,p-1]</math>
Known optimal Golomb rulers
The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect.
{| class="wikitable"
! Order !! Length !! Marks !! Proved !! Proof discovered by
|-
| 1 || 0 || 0 || 1952|| Wallace Babcock
|-
| 2 || 1 || 0 1 || 1952 || John P. Robinson and Arthur J. Bernstein
|-
| 6 || 17 || 0 1 4 10 12 17 <br /> 0 1 4 10 15 17 <br /> 0 1 8 11 13 17 <br /> 0 1 8 12 14 17 || c. 1967 || Mark Garry, David Vanderschel et al. (web project)
|-
| 22 || 356 || 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 || 1999