Optimal Golomb Rulers

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. 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 $A = \$ where $a_1 < a_2 < ... < a_m$ is a Golomb ruler if and only if

:$\text i,j,k,l \in \left\ \text i \neq j \text k \neq l,\ a_i - a_j = a_k - a_l \iff i=k \text 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 < a_m - a_$. Such a form can be achieved through translation and reflection.

Golomb rulers as functions

An injective function $f:\left\ \to \left\$ with $f(1) = 0$ and $f(m) = n$ is a Golomb ruler if and only if

:$\text i,j,k,l \in \left\ \text i \neq j \text k \neq l, f(i)-f(j) = f(k)-f(l) \iff i=k \text 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 ''x''_i ∈ be binary variables indicating the presence of a mark at position ''i'', for ''i'' = 1, ..., ''L''_u, where ''L''_u 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 \min_ \quad & t \\ \text \quad & i \cdot x_i \leq t, \quad \text i = 1, \ldots, L_u, \\ & \sum_^ x_i = n - 1, \\ & x_j + \sum_^ x_i x_ \leq 1, \quad \text j = 1, \ldots, L_u - 1. \end$

In this model, the variables $x_i$ define the ruler marks, and the constraint involving the bilinear terms $x_i x_$ 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

Information theory and error correction

Golomb rulers are used within information theory related to error correcting codes.

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

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

* Costas array
* Volunteer computing
** BOINC
** distributed.net
* Perfect ruler

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases