Golomb ruler

Golomb rulers as sets A set of integers A = \{a_1,a_2,...,a_m\} where a_1 is a Golomb ruler if and only if :\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. The order of such a Golomb ruler is m and its length is a_m - a_1. The canonical form has a_1 = 0 and, if m>2, a_2 - a_1 . Such a form can be achieved through translation and reflection. Golomb rulers as functions An injective function f:\left\{1,2,...,m\right\} \to \left\{0,1,...,n\right\} with f(1) = 0 and f(m) = n is a Golomb ruler if and only if :\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. The order of such a Golomb ruler is m and its length is n. The canonical form has :f(2) if 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. == Mathematical formulation ==

An optimization-based approach to find an optimal Golomb ruler of order n can be formulated as the following mixed-integer nonlinear programming (MINLP) problem. Let xi ∈ {0,1} be binary variables indicating the presence of a mark at position i, for i = 1, ..., Lu, where Lu is an upper bound on the length of the ruler. Let t be a continuous variable representing the total length of the ruler. The problem is formulated as: : \begin{aligned} \min_{t \geq 0,\ x_i \in \{0,1\}} \quad & t \\ \text{s.t.} \quad & i \cdot x_i \leq t, \quad \text{for } i = 1, \ldots, L_u, \\ & \sum_{i=1}^{L_u} x_i = n - 1, \\ & x_j + \sum_{i=1}^{L_u - j} x_i x_{i+j} \leq 1, \quad \text{for } j = 1, \ldots, L_u - 1. \end{aligned} In this model, the variables x_i define the ruler marks, and the constraint involving the bilinear terms x_i x_{i+j} ensures that all pairwise distances are distinct. The objective is to minimize the largest marked position, which corresponds to the ruler's length. ==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. :2pk+(k^2\,\bmod\,p),k\in[0,p-1] ==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. The optimal ruler would have been known before this date; this date represents that date when it was discovered to be optimal (because all other rulers were proved to not be smaller). For example, the ruler that turned out to be optimal for order 26 was recorded on , but it was not known to be optimal until all other possibilities were exhausted on . ==See also==