Editing Golomb ruler

{{Short description|Set of marks along a ruler such that no two pairs of marks are the same distance apart}}
{{Redirect|OGR}}

[[File:Golomb Ruler-4.svg|thumb|Golomb ruler of order 4 and length 6. This ruler is both ''optimal'' and ''perfect''.]]
[[File:Perfect circular Golomb rulers.svg|thumb|The perfect circular Golomb rulers (also called [[difference set]]s) 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 (mathematics)|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 array]]s.

The Golomb ruler was named for [[Solomon W. Golomb]] and discovered independently by {{harvtxt|Sidon|1932}}<ref>{{cite journal |last1=Sidon |first1=S. |year=1932 |title=Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen |journal=Mathematische Annalen |volume=106 |pages=536–539 |doi=10.1007/BF01455900 |s2cid=120087718}}</ref> and {{harvtxt|Babcock|1953}}. [[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 [[congruence (geometry)|congruent]]. This turned out to be false for six-point rulers, but true otherwise.<ref>{{cite journal
 | last1 = Bekir | first1 = Ahmad
 | last2 = Golomb | first2 = Solomon W. | author2-link = Solomon W. Golomb
 | doi = 10.1109/TIT.2007.899468
 | issue = 8
 | journal = [[IEEE Transactions on Information Theory]]
 | mr = 2400501
 | pages = 2864–2867
 | title = There are no further counterexamples to S. Piccard's theorem
 | volume = 53
 | year = 2007| s2cid = 16689687
 }}.</ref>

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 ruler|perfect]]'' Golomb ruler. It has been proved that no perfect Golomb ruler exists for five or more marks.<ref name="mcgill.ca"/> 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 computing|parallel searches]] for optimal order-24 through order-28 Golomb rulers, each time confirming the suspected candidate ruler.<ref name="distributed.net OGR-24 completion announcement">{{cite web |url=https://blogs.distributed.net/2004/11/01/10/24/nugget/ |title=distributed.net - OGR-24 completion announcement |date=2004-11-01}}</ref><ref name="distributed.net OGR-25 completion announcement">{{cite web |url=https://blogs.distributed.net/2008/10/25/23/14/bovine/ |title=distributed.net - OGR-25 completion announcement |date=2008-10-25}}</ref><ref name="distributed.net OGR-26 completion announcement">{{cite web |url=https://blogs.distributed.net/2009/02/24/17/26/bovine/ |title=distributed.net - OGR-26 completion announcement |date=2009-02-24}}</ref><ref name="distributed.net OGR-27 completion announcement">{{cite web |url=https://blogs.distributed.net/2014/02/ |title=distributed.net - OGR-27 completion announcement |date=2014-02-25}}</ref><ref name="Completion of OGR-28 project">{{cite web |title=Completion of OGR-28 project |url=https://blogs.distributed.net/2022/11/23/03/28/bovine/ |access-date=23 November 2022}}</ref>

Currently, the [[Complexity class|complexity]] of finding optimal Golomb rulers (OGRs) of arbitrary order ''n'' (where ''n'' is given in unary) is unknown.{{clarify|Why is it relevant that n be represented in unary?|date=January 2023}} In the past there was some speculation that it is an [[NP-hard]] problem.<ref name="mcgill.ca">{{cite web|url=http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino|title=Modular and Regular Golomb Rulers}}</ref> 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.<ref>{{cite journal |author=Meyer C, Papakonstantinou PA |title=On the complexity of constructing Golomb rulers |journal=Discrete Applied Mathematics |volume=157 |issue=4 |date=February 2009 |pages=738–748 |doi=10.1016/j.dam.2008.07.006|doi-access=free }}</ref>

==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><ref>{{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
  }}</ref>

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><ref name="Drakakis">{{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 = 
  }}</ref>{{rp|236}}

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 [[optimization (mathematics)|optimal]] in either of two respects:<ref name="Drakakis"/>{{rp|237}}

* It may be ''optimally dense'', exhibiting maximal <var>m</var> for the specific value of <var>n</var>,
* It may be ''optimally short'', exhibiting minimal <var>n</var> for the specific value of <var>m</var>.

The general term ''optimal Golomb ruler'' is used to refer to the second type of optimality.

==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.<ref name="ErdősTurán1941"/>]]

===Information theory and error correction===
Golomb rulers are used within [[information theory]] related to [[error correcting code]]s.<ref name="titlestats.A class of binary recurrent codes with limited error propagation">{{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}}</ref>

===Radio frequency selection===
Golomb rulers are used in the selection of radio frequencies to reduce the effects of [[intermodulation interference]] with both [[Earth|terrestrial]]<ref name="titlestats.Intermodulation Interference in Radio Systems">{{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 }}</ref> and [[outer space|extraterrestrial]]<ref name="titlestats.Carrier frequency assignment for nonlinear repeaters">{{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}}</ref> 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.<ref>{{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}}</ref><ref>{{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 }}</ref>

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

==Methods of construction==
A number of construction methods produce [[asymptotically optimal]] Golomb rulers.

===Erdős–Turán construction===
{{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.<ref name="ErdősTurán1941">{{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}}</ref>

:<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 ruler|perfect]].

{| class="wikitable"
! Order !! Length !! Marks !! Proved{{ref label|unknown_index|*|^ *}} !! Proof discovered by
|-
| 1 || 0 || '''0''' || 1952<ref name="mathpuzzles">[http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html Rulers, Arrays, and Gracefulness] Ed Pegg Jr. November 15, 2004. Math Games.</ref>|| Wallace Babcock
|-
| 2 || 1 || '''0 1''' || 1952<ref name="mathpuzzles" />|| Wallace Babcock
|-
| 3 || 3 || '''0 1 3''' || 1952<ref name="mathpuzzles" />|| Wallace Babcock
|-
| 4 || 6 || '''0 1 4 6''' || 1952<ref name="mathpuzzles" />|| Wallace Babcock
|-
| 5 || 11 || 0 1 4 9 11 <br /> 0 2 7 8 11 || c. 1967<ref name="shearer">{{cite web|url= http://www.research.ibm.com/people/s/shearer/grtab.html|archive-url=https://web.archive.org/web/20170625090514/http://www.research.ibm.com/people/s/shearer/grtab.html|archive-date=25 June 2017 |title= Table of lengths of shortest known Golomb rulers |last=Shearer|first=James B|date=19 February 1998| publisher= [[IBM]] }}</ref> || 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<ref name="shearer" /> || John P. Robinson and Arthur J. Bernstein
|-
| 7 || 25 || 0 1 4 10 18 23 25 <br /> 0 1 7 11 20 23 25 <br /> 0 1 11 16 19 23 25 <br /> 0 2 3 10 16 21 25 <br /> 0 2 7 13 21 22 25 || c. 1967<ref name="shearer" /> || John P. Robinson and Arthur J. Bernstein
|-
| 8 || 34 || 0 1 4 9 15 22 32 34 || 1972<ref name="shearer" /> || William Mixon
|-
| 9 || 44 || 0 1 5 12 25 27 35 41 44 || 1972<ref name="shearer" /> || William Mixon
|-
| 10 || 55 || 0 1 6 10 23 26 34 41 53 55 || 1972<ref name="shearer" /> || William Mixon
|-
| 11 || 72 || 0 1 4 13 28 33 47 54 64 70 72 <br /> 0 1 9 19 24 31 52 56 58 69 72 || 1972<ref name="shearer" /> || William Mixon
|-
| 12 || 85 || 0 2 6 24 29 40 43 55 68 75 76 85 || 1979<ref name="shearer" /> || John P. Robinson
|-
| 13 || 106 || 0 2 5 25 37 43 59 70 85 89 98 99 106 || 1981<ref name="shearer" /> || John P. Robinson
|-
| 14 || 127 || 0 4 6 20 35 52 59 77 78 86 89 99 122 127 || 1985<ref name="shearer" /> || James B. Shearer
|-
| 15 || 151 || 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 || 1985<ref name="shearer" /> || James B. Shearer
|-
| 16 || 177 || 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 || 1986<ref name="shearer" /> || James B. Shearer
|-
| 17 || 199 || 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199 || 1993<ref name="shearer" /> || W. Olin Sibert
|-
| 18 || 216 || 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 || 1993<ref name="shearer" /> || W. Olin Sibert
|-
| 19 || 246 || 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 || 1994<ref name="shearer" /> || Apostolos Dollas, William T. Rankin and David McCracken
|-
| 20 || 283 || 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 || 1997?<ref name="shearer" /> || Mark Garry, David Vanderschel et al. (web project)
|-
| 21 || 333 || 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 || 8 May 1998<ref name="org2021">{{cite web |title= In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived)|date=26 November 1998 | publisher= Mark Garry, David Vanderschel, et al |url= http://members.aol.com/golomb20/index.html |archive-url=https://web.archive.org/web/19981206073704/http://members.aol.com/golomb20/index.html |archive-date=1998-12-06}}</ref> || 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<ref name="shearer" /> || Mark Garry, David Vanderschel et al. (web project)
|-
| 23 || 372 || 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372 || 1999<ref name="shearer" /> || Mark Garry, David Vanderschel et al. (web project)
|-
| 24 || 425 || 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425 || {{date|13 October 2004}}<ref name="distributed.net OGR-24 completion announcement" /> || [[distributed.net]]
|-
| 25 || 480 || 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 || {{date|25 October 2008}}<ref name="distributed.net OGR-25 completion announcement" /> || [[distributed.net]]
|-
| 26 || 492 || 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492 || {{date|24 February 2009}}<ref name="distributed.net OGR-26 completion announcement" /> || [[distributed.net]]
|-
| 27 || 553 || 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 || {{date|19 February 2014}}<ref name="distributed.net OGR-27 completion announcement" /> || [[distributed.net]]
|-
| 28 || 585 || 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585 || {{date|23 November 2022}}<ref name="Completion of OGR-28 project" /> || [[distributed.net]]
|-
|}

{{note label|unknown_index|*|^ *}} <small>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}}.</small>

==See also==
* [[Costas array]]
* [[Volunteer computing]]
** [[Berkeley Open Infrastructure for Network Computing|BOINC]]
** [[distributed.net]]
* [[Perfect ruler]]
* [[Sidon sequence]]
* [[Sparse ruler]]

==References==
{{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 }}

==External links==
* [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]]