Golomb ruler

A set of integers $A\; =\; \backslash \{a\_1,a\_2,...,a\_m\backslash \}$ where is a Golomb ruler if and only if

:$\backslash text\{for\; all\; \}\; i,j,k,l\; \backslash in\; \backslash left\backslash \{1,2,...,m\backslash right\backslash \}\; \backslash text\{such\; that\; \}\; i\; \backslash neq\; j\; \backslash text\{\; and\; \}\; k\; \backslash neq\; l,\backslash \; a\_i\; -\; a\_j\; =\; a\_k\; -\; a\_l\; \backslash iff\; i=k\; \backslash text\{\; and\; \}\; j=l.${{cite web

| last = Dimitromanolakis

| first = Apostolos

| title = Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers

| url = http://www.cs.toronto.edu/%7Eapostol/golomb/main.pdf

| access-date = 2009-12-20

}}

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$, . Such a form can be achieved through translation and reflection.

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

:$\backslash text\{for\; all\; \}\; i,j,k,l\; \backslash in\; \backslash left\backslash \{1,2,...,m\backslash right\backslash \}\; \backslash text\{such\; that\; \}\; i\; \backslash neq\; j\; \backslash text\{\; and\; \}\; k\; \backslash neq\; l,\; f(i)-f(j)\; =\; f(k)-f(l)\; \backslash iff\; i=k\; \backslash text\{\; and\; \}\; j=l.${{Cite journal

| last = Drakakis

| first = Konstantinos

| title = A Review Of The Available Construction Methods For Golomb Rulers

| journal = Advances in Mathematics of Communications

| volume = 3

| issue = 3

| pages = 235–250

| year = 2009

| doi = 10.3934/amc.2009.3.235| doi-access =

}}{{rp|236}}

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

:

A Golomb ruler of order m with length n may be optimal in either of two respects:{{rp|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.

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 ∈ {0,1} 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{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. {{Cite journal

| last1 = Duxbury

| first1 = Phil

| last2 = Lavor

| first2 = Carlile

| last3 = de Salles-Neto

| first3 = Luiz Leduino

| title = A conjecture on a continuous optimization model for the Golomb Ruler Problem

| journal = RAIRO - Operations Research

| volume = 55

| issue = 4

| pages = 2241–2246

| year = 2021

| publisher = EDP Sciences

| doi = 10.1051/ro/2021027

}}

File:Golomb ruler conference room.svg

Golomb rulers are used within information theory related to error correcting codes.{{cite journal |title=A class of binary recurrent codes with limited error propagation |date=January 1967 |journal=IEEE Transactions on Information Theory |author=Robinson J, Bernstein A |volume=13 |issue=1 |pages=106–113 |doi=10.1109/TIT.1967.1053951}}

Golomb rulers are used in the selection of radio frequencies to reduce the effects of intermodulation interference with both terrestrial{{cite journal |url=http://www.alcatel-lucent.com/bstj/vol32-1953/articles/bstj32-1-63.pdf |archive-url=https://web.archive.org/web/20110707104054/http://www.alcatel-lucent.com/bstj/vol32-1953/articles/bstj32-1-63.pdf |archive-date=2011-07-07 |url-status=live |title=Intermodulation Interference in Radio Systems |year=1953 |access-date=2011-03-14 |format=excerpt |doi=10.1002/j.1538-7305.1953.tb01422.x |last1=Babcock |first1=Wallace C. |journal=Bell System Technical Journal |volume=32 |pages=63–73 }} and extraterrestrial{{cite journal |title=Carrier frequency assignment for nonlinear repeaters |journal=Comsat Technical Review |volume=7|pages=227 |type=abstract |bibcode=1977COMTR...7..227F |last1=Fang |first1=R. J. F. |last2=Sandrin |first2=W. A. |year=1977}} applications.

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.{{cite book |last1=Thompson |first1=A. Richard |last2=Moran |first2=James M. |last3=Swenson |first3=George W. |title=Interferometry and Synthesis in Radio Astronomy |url=https://archive.org/details/interferometrysy00thom_120 |url-access=limited |publisher=Wiley-VCH |edition=Second |year=2004 |page=[https://archive.org/details/interferometrysy00thom_120/page/n162 142] |isbn=978-0471254928}}{{cite journal |last=Arsac |first=J. |title=Transmissions des frequences spatiales dans les systemes recepteurs d'ondes courtes |language=fr |trans-title=Transmissions of spatial frequencies in shortwave receiver systems |journal=Optica Acta |volume=2 |issue=112 |year=1955|pages=112–118 |doi=10.1080/713821025 |bibcode=1955AcOpt...2..112A }}

Multi-ratio current transformers use Golomb rulers to place transformer tap points.{{citation needed|date=April 2022}}

A number of construction methods produce asymptotically optimal Golomb rulers.

{{anchor|Erdős–Turan construction}}

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

| doi = 10.1112/jlms/s1-16.4.212

| last1 = Erdős

| first1 = Paul

| author-link = Paul Erdős

| last2 = Turán

| first2 = Pál

| author-link2 = Pál Turán

| title = On a problem of Sidon in additive number theory and some related problems

| journal = Journal of the London Mathematical Society

| volume = 16

| issue = 4

| pages = 212–215

| year = 1941}}

:$2pk+(k^2\backslash ,\backslash bmod\backslash ,p),k\backslash in[0,p-1]$

The following table contains all known optimal Golomb rulers, excluding those with marks in the reverse order. The first four are perfect.

{{note label|unknown_index|*|^ *}} 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 {{date|10 October 2007}}, but it was not known to be optimal until all other possibilities were exhausted on {{date|24 February 2009}}.

• Costas array
• Volunteer computing
• BOINC
• distributed.net
• Perfect ruler
• Sidon sequence
• Sparse ruler

{{Reflist}}

• {{cite journal|first=Martin|last=Gardner|author-link=Martin Gardner|title=Mathematical games|journal=Scientific American|date=March 1972|volume=226|issue=3|pages=108–112|doi=10.1038/scientificamerican0372-108|bibcode=1972SciAm.226c.108G }}

• [https://web.archive.org/web/20171225101048/http://www.research.ibm.com/people/s/shearer/grule.html James B. Shearer's Golomb ruler pages]
• [https://www.distributed.net/OGR distributed.net: Project OGR]
• [https://web.archive.org/web/20071112013839/http://members.aol.com/golomb20/ In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers]
• [https://web.archive.org/web/20210401043316/http://www3.telus.net/millerlf/g3-records.html Golomb rulers up to length of over 200]

Category:Antennas (radio)

Category:Distributed computing projects

Category:Length, distance, or range measuring devices

Category:Number theory