Golomb ruler

Last updated August 18, 2023

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.

Definitions
Golomb rulers as sets
Golomb rulers as functions
Optimality
Practical applications
Information theory and error correction
Radio frequency selection
Radio antenna placement
Current transformers
Methods of construction
Erdős–Turán construction
Known optimal Golomb rulers
See also
References
External links

The Golomb ruler was named for Solomon W. Golomb and discovered independently by Sidon (1932) ^[1] and 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 congruent. This turned out to be false for six-point rulers, but true otherwise.^[2]

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.^[3] 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.^[4]^[5]^[6]^[7]^[8]

Currently, the complexity of finding optimal Golomb rulers (OGRs) of arbitrary order n (where n is given in unary) is unknown.^{[ clarification needed ]} In the past there was some speculation that it is an NP-hard problem.^[3] 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.^[9]

Definitions

Golomb rulers as sets

A set of integers $A=\{a_{1},a_{2},...,a_{m}\}$ where $a_{1}<a_{2}<...<a_{m}$ 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.

^[10]

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_{m-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.

^[11]^: 236

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

f(2)<f(m)-f(m-1)

if

m>2

.

Optimality

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

Practical applications

Information theory and error correction

Golomb rulers are used within information theory related to error correcting codes.^[13]

Radio frequency selection

Golomb rulers are used in the selection of radio frequencies to reduce the effects of intermodulation interference with both terrestrial ^[14] and extraterrestrial ^[15] 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.^[16]^[17]

Current transformers

Multi-ratio current transformers use Golomb rulers to place transformer tap points.^{[ citation needed ]}

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.^[12]

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.

Order	Length	Marks	Proved^[*]	Proof discovered by
1	0	0	1952^[18]	Wallace Babcock
2	1	0 1	1952^[18]	Wallace Babcock
3	3	0 1 3	1952^[18]	Wallace Babcock
4	6	0 1 4 6	1952^[18]	Wallace Babcock
5	11	0 1 4 9 11 0 2 7 8 11	c. 1967^[19]	John P. Robinson and Arthur J. Bernstein
6	17	0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17	c. 1967^[19]	John P. Robinson and Arthur J. Bernstein
7	25	0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25	c. 1967^[19]	John P. Robinson and Arthur J. Bernstein
8	34	0 1 4 9 15 22 32 34	1972^[19]	William Mixon
9	44	0 1 5 12 25 27 35 41 44	1972^[19]	William Mixon
10	55	0 1 6 10 23 26 34 41 53 55	1972^[19]	William Mixon
11	72	0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72	1972^[19]	William Mixon
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979^[19]	John P. Robinson
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981^[19]	John P. Robinson
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985^[19]	James B. Shearer
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985^[19]	James B. Shearer
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986^[19]	James B. Shearer
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993^[19]	W. Olin Sibert
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993^[19]	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^[19]	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?^[19]	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^[20]	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^[19]	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^[19]	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	13 October 2004^[4]	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	25 October 2008^[5]	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	24 February 2009^[6]	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	19 February 2014^[7]	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	23 November 2022^[8]	distributed.net

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

Related Research Articles

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the local maxima and minima of a function subject to equation constraints. It is named after the mathematician Joseph-Louis Lagrange. The basic idea is to convert a constrained problem into a form such that the derivative test of an unconstrained problem can still be applied. The relationship between the gradient of the function and gradients of the constraints rather naturally leads to a reformulation of the original problem, known as the Lagrangian function.

distributed.net Distributed computing organization

Distributed.net is a volunteer computing effort that is attempting to solve large scale problems using otherwise idle CPU or GPU time. It is governed by Distributed Computing Technologies, Incorporated (DCTI), a non-profit organization under U.S. tax code 501(c)(3).

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

In computer science, a suffix array is a sorted array of all suffixes of a string. It is a data structure used in, among others, full-text indices, data-compression algorithms, and the field of bibliometrics.

A perfect ruler of length $is a ruler with integer markings, for which there exists an integer such that any positive integer is uniquely expressed as the difference for some . This is referred to as an -perfect ruler.$

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., p(i) ≥ p(i + 1) for all positive i), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that probability distribution would have assigned. A universal code is asymptotically optimal if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity.

In multi-objective optimization, the Pareto front is the set of all Pareto efficient solutions. The concept is widely used in engineering. It allows the designer to restrict attention to the set of efficient choices, and to make tradeoffs within this set, rather than considering the full range of every parameter.

In information theory and computer science, the Damerau–Levenshtein distance is a string metric for measuring the edit distance between two sequences. Informally, the Damerau–Levenshtein distance between two words is the minimum number of operations required to change one word into the other.

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique. The longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time $where denotes the length of the input sequence.$

Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs and a list of machines. The required output is a schedule – an assignment of jobs to machines. The schedule should optimize a certain objective function. In the literature, problems of optimal job scheduling are often called machine scheduling, processor scheduling, multiprocessor scheduling, or just scheduling.

<span class="mw-page-title-main">Generalized Pareto distribution</span> Family of probability distributions often used to model tails or extreme values

In statistics, the generalized Pareto distribution (GPD) is a family of continuous probability distributions. It is often used to model the tails of another distribution. It is specified by three parameters: location $, scale, and shape . Sometimes it is specified by only scale and shape and sometimes only by its shape parameter. Some references give the shape parameter as .$

In mathematics, the Golomb–Dickman constant arises in the theory of random permutations and in number theory. Its value is

In number theory, a Sidon sequence is a sequence $of natural numbers in which all pairwise sums are different. Sidon sequences are also called Sidon sets; they are named after the Hungarian mathematician Simon Sidon, who introduced the concept in his investigations of Fourier series.$

A sparse ruler is a ruler in which some of the distance marks may be missing. More abstractly, a sparse ruler of length $with marks is a sequence of integers where . The marks and correspond to the ends of the ruler. In order to measure the distance, with there must be marks and such that .$

In computer science, the reduction operator is a type of operator that is commonly used in parallel programming to reduce the elements of an array into a single result. Reduction operators are associative and often commutative. The reduction of sets of elements is an integral part of programming models such as Map Reduce, where a reduction operator is applied (mapped) to all elements before they are reduced. Other parallel algorithms use reduction operators as primary operations to solve more complex problems. Many reduction operators can be used for broadcasting to distribute data to all processors.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

In functional analysis and related areas of mathematics, a complete topological vector space is a topological vector space (TVS) with the property that whenever points get progressively closer to each other, then there exists some point $towards which they all get closer. The notion of "points that get progressively closer" is made rigorous by Cauchy nets or Cauchy filters, which are generalizations of Cauchy sequences, while "point towards which they all get closer" means that this Cauchy net or filter converges to The notion of completeness for TVSs uses the theory of uniform spaces as a framework to generalize the notion of completeness for metric spaces. But unlike metric-completeness, TVS-completeness does not depend on any metric and is defined for all TVSs, including those that are not metrizable or Hausdorff.$

References

↑ Sidon, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen. 106: 536–539. doi:10.1007/BF01455900. S2CID 120087718.
↑ Bekir, Ahmad; Golomb, Solomon W. (2007). "There are no further counterexamples to S. Piccard's theorem". IEEE Transactions on Information Theory . 53 (8): 2864–2867. doi:10.1109/TIT.2007.899468. MR 2400501. S2CID 16689687..
1 2 "Modular and Regular Golomb Rulers".
1 2 "distributed.net - OGR-24 completion announcement". 2004-11-01.
1 2 "distributed.net - OGR-25 completion announcement". 2008-10-25.
1 2 "distributed.net - OGR-26 completion announcement". 2009-02-24.
1 2 "distributed.net - OGR-27 completion announcement". 2014-02-25.
1 2 "Completion of OGR-28 project" . Retrieved 23 November 2022.
↑ Meyer C, Papakonstantinou PA (February 2009). "On the complexity of constructing Golomb rulers". Discrete Applied Mathematics. 157 (4): 738–748. doi: 10.1016/j.dam.2008.07.006 .
↑ Dimitromanolakis, Apostolos. "Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers" (PDF). Retrieved 2009-12-20.
1 2 Drakakis, Konstantinos (2009). "A Review Of The Available Construction Methods For Golomb Rulers". Advances in Mathematics of Communications. 3 (3): 235–250. doi: 10.3934/amc.2009.3.235 .
1 2 Erdős, Paul; Turán, Pál (1941). "On a problem of Sidon in additive number theory and some related problems". Journal of the London Mathematical Society. 16 (4): 212–215. doi:10.1112/jlms/s1-16.4.212.
↑ Robinson J, Bernstein A (January 1967). "A class of binary recurrent codes with limited error propagation". IEEE Transactions on Information Theory. 13 (1): 106–113. doi:10.1109/TIT.1967.1053951.
↑ Babcock, Wallace C. (1953). "Intermodulation Interference in Radio Systems" (excerpt). Bell System Technical Journal. 32: 63–73. doi:10.1002/j.1538-7305.1953.tb01422.x. Archived (PDF) from the original on 2011-07-07. Retrieved 2011-03-14.
↑ Fang, R. J. F.; Sandrin, W. A. (1977). "Carrier frequency assignment for nonlinear repeaters". Comsat Technical Review (abstract). 7: 227. Bibcode:1977COMTR...7..227F.
↑ Thompson, A. Richard; Moran, James M.; Swenson, George W. (2004). Interferometry and Synthesis in Radio Astronomy (Second ed.). Wiley-VCH. p. 142. ISBN 978-0471254928.
↑ Arsac, J. (1955). "Transmissions des frequences spatiales dans les systemes recepteurs d'ondes courtes" [Transmissions of spatial frequencies in shortwave receiver systems]. Optica Acta (in French). 2 (112): 112–118. Bibcode:1955AcOpt...2..112A. doi:10.1080/713821025.
1 2 3 4 Rulers, Arrays, and Gracefulness Ed Pegg Jr. November 15, 2004. Math Games.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Shearer, James B (19 February 1998). "Table of lengths of shortest known Golomb rulers". IBM. Archived from the original on 25 June 2017.
↑ "In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived)". Mark Garry, David Vanderschel, et al. 26 November 1998. Archived from the original on 1998-12-06.

Gardner, Martin (March 1972). "Mathematical games". Scientific American . 226 (3): 108–112. Bibcode:1972SciAm.226c.108G. doi:10.1038/scientificamerican0372-108.

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sidon, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen. 106: 536–539. doi:10.1007/BF01455900. S2CID 120087718.

[2] Bekir, Ahmad; Golomb, Solomon W. (2007). "There are no further counterexamples to S. Piccard's theorem". IEEE Transactions on Information Theory . 53 (8): 2864–2867. doi:10.1109/TIT.2007.899468. MR 2400501. S2CID 16689687..

[mcgill.ca-3] 1 2 "Modular and Regular Golomb Rulers".

[distributed.net_OGR-24_completion_announcement-4] 1 2 "distributed.net - OGR-24 completion announcement". 2004-11-01.

[distributed.net_OGR-25_completion_announcement-5] 1 2 "distributed.net - OGR-25 completion announcement". 2008-10-25.

[distributed.net_OGR-26_completion_announcement-6] 1 2 "distributed.net - OGR-26 completion announcement". 2009-02-24.

[distributed.net_OGR-27_completion_announcement-7] 1 2 "distributed.net - OGR-27 completion announcement". 2014-02-25.

[Completion_of_OGR-28_project-8] 1 2 "Completion of OGR-28 project" . Retrieved 23 November 2022.

[9] Meyer C, Papakonstantinou PA (February 2009). "On the complexity of constructing Golomb rulers". Discrete Applied Mathematics. 157 (4): 738–748. doi: 10.1016/j.dam.2008.07.006 .

[10] Dimitromanolakis, Apostolos. "Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers" (PDF). Retrieved 2009-12-20.

[Drakakis-11] 1 2 Drakakis, Konstantinos (2009). "A Review Of The Available Construction Methods For Golomb Rulers". Advances in Mathematics of Communications. 3 (3): 235–250. doi: 10.3934/amc.2009.3.235 .

[ErdősTurán1941-12] 1 2 Erdős, Paul; Turán, Pál (1941). "On a problem of Sidon in additive number theory and some related problems". Journal of the London Mathematical Society. 16 (4): 212–215. doi:10.1112/jlms/s1-16.4.212.

[titlestats.A_class_of_binary_recurrent_codes_with_limited_error_propagation-13] Robinson J, Bernstein A (January 1967). "A class of binary recurrent codes with limited error propagation". IEEE Transactions on Information Theory. 13 (1): 106–113. doi:10.1109/TIT.1967.1053951.

[titlestats.Intermodulation_Interference_in_Radio_Systems-14] Babcock, Wallace C. (1953). "Intermodulation Interference in Radio Systems" (excerpt). Bell System Technical Journal. 32: 63–73. doi:10.1002/j.1538-7305.1953.tb01422.x. Archived (PDF) from the original on 2011-07-07. Retrieved 2011-03-14.

[titlestats.Carrier_frequency_assignment_for_nonlinear_repeaters-15] Fang, R. J. F.; Sandrin, W. A. (1977). "Carrier frequency assignment for nonlinear repeaters". Comsat Technical Review (abstract). 7: 227. Bibcode:1977COMTR...7..227F.

[16] Thompson, A. Richard; Moran, James M.; Swenson, George W. (2004). Interferometry and Synthesis in Radio Astronomy (Second ed.). Wiley-VCH. p. 142. ISBN 978-0471254928.

[17] Arsac, J. (1955). "Transmissions des frequences spatiales dans les systemes recepteurs d'ondes courtes" [Transmissions of spatial frequencies in shortwave receiver systems]. Optica Acta (in French). 2 (112): 112–118. Bibcode:1955AcOpt...2..112A. doi:10.1080/713821025.

[mathpuzzles-18] 1 2 3 4 Rulers, Arrays, and Gracefulness Ed Pegg Jr. November 15, 2004. Math Games.

[shearer-19] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Shearer, James B (19 February 1998). "Table of lengths of shortest known Golomb rulers". IBM. Archived from the original on 25 June 2017.

[org2021-20] "In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived)". Mark Garry, David Vanderschel, et al. 26 November 1998. Archived from the original on 1998-12-06.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[13]

[14]

[15]

[16]

[17]

[12]

[*]

[18]

[19]

[20]