Golomb ruler
Encyclopedia
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Golomb ruler is a set of marks at integer positions along an imaginary 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.
The Golomb ruler was named for Solomon W. Golomb
Solomon W. Golomb
Solomon Wolf Golomb is an American mathematician and engineer and a professor of electrical engineering at the University of Southern California, best known to the general public and fans of mathematical games as the inventor of polyominoes, the inspiration for the computer game Tetris...
and discovered independently by Sidon and Babcock.
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 proven 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 finding the optimal Golomb rulers for a specified order is computationally very challenging. Distributed.net
Distributed.net
distributed.net is a worldwide distributed computing effort that is attempting to solve large scale problems using otherwise idle CPU or GPU time. It is officially recognized as a non-profit organization under U.S...
has completed distributed massively parallel searches
Parallel computing
Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
for optimal order-24, order-25 and order-26 Golomb rulers, confirming the suspected candidates. Distributed.net also has plans to find optimal Golomb rulers (OGRs) of order-27 and order-28. However, they are not expected to take as long as the previous projects due to the discovery of an improved algorithm. Distributed.net is actively searching for the optimal order-27 ruler; in May 2009, the expected time to discover it was estimated at about seven years. , the computation was about 43% complete, after 940 days (2.5 years) of work.
Currently, the complexity of finding 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
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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.
Golomb rulers as sets
A set of integers
is a Golomb ruler if and only if
The order of such a Golomb ruler is
and its length is 
. The canonicalCanonical
Canonical is an adjective derived from canon. Canon comes from the greek word κανών kanon, "rule" or "measuring stick" , and is used in various meanings....
form has
and, if 
, 
. Such a form can be achieved through translation and reflection.Golomb rulers as functions
An injective functionInjective function
In mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
with
and 
is a Golomb ruler if and only if
The order of such a Golomb ruler is
and its length is 
. The canonical form has
if 
.Optimality
A Golomb ruler of order
with length n may be optimalOptimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
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.
Practical Applications
Information Theory/Error Correction
Golomb rulers are used within Information TheoryInformation theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
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 terrestrialTerrestrial
Terrestrial refers to things related to land or the planet Earth.Terrestrial may also refer to:* Terrestrial animal, an animal that lives on land opposed to living in water, or sometimes an animal that lives on or near the ground, as opposed to in trees etc.** A fishing fly that simulates the...
and extraterrestrial applications.
Radio Antennae Placement
Golomb rulers are used in the design of phased arrayPhased array
In wave theory, a phased array is an array of antennas in which the relative phases of the respective signals feeding the antennas are varied in such a way that the effective radiation pattern of the array is reinforced in a desired direction and suppressed in undesired directions.An antenna array...
radio antennas such as radio telescope
Radio telescope
A radio telescope is a form of directional radio antenna used in radio astronomy. The same types of antennas are also used in tracking and collecting data from satellites and space probes...
s. Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at cell site
Cell site
A cell site is a term used to describe a site where antennas and electronic communications equipment are placed, usually on a radio mast, tower or other high place, to create a cell in a cellular network...
s.
Methods of construction
A number of construction methods produce asymptotically optimalAsymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm...
Golomb rulers.
Erdős–Turan construction
The following construction, due to Paul ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Pál Turán
Pál Turán
Paul Turán was a Hungarian mathematician who worked primarily in number theory. He had a long collaboration with fellow Hungarian mathematician Paul Erdős, lasting 46 years and resulting in 28 joint papers.- Life and education :...
, produces a Golomb ruler for every odd prime p.
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 |
|---|---|---|
| 1 | 0 | 0 |
| 2 | 1 | 0 1 |
| 3 | 3 | 0 1 3 |
| 4 | 6 | 0 1 4 6 |
| 5 | 11 | 0 1 4 9 11 0 2 7 8 11 |
| 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 |
| 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 |
| 8 | 34 | 0 1 4 9 15 22 32 34 |
| 9 | 44 | 0 1 5 12 25 27 35 41 44 |
| 10 | 55 | 0 1 6 10 23 26 34 41 53 55 |
| 11 | 72 | 0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72 |
| 12 | 85 | 0 2 6 24 29 40 43 55 68 75 76 85 |
| 13 | 106 | 0 2 5 25 37 43 59 70 85 89 98 99 106 |
| 14 | 127 | 0 4 6 20 35 52 59 77 78 86 89 99 122 127 |
| 15 | 151 | 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 |
| 16 | 177 | 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 |
| 17 | 199 | 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199 |
| 18 | 216 | 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 |
| 19 | 246 | 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 |
| 20 | 283 | 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 |
| 21 | 333 | 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 |
| 22 | 356 | 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 |
| 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 |
| 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 |
| 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 |
| 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 |
External links
- James B. Shearer's Golomb ruler pages
- distributed.net: Project OGR
- In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers
- "Rulers, Arrays, and Gracefulness" by Ed Pegg Jr.
- Golomb rulers up to length of over 200 (via Internet ArchiveInternet ArchiveThe Internet Archive is a non-profit digital library with the stated mission of "universal access to all knowledge". It offers permanent storage and access to collections of digitized materials, including websites, music, moving images, and nearly 3 million public domain books. The Internet Archive...
)