Editing Golomb ruler (section)

{{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>