Golomb ruler: Information from Answers.com

"OGR" redirects here. For the OGR programming library, see GDAL.

Golomb ruler of order 4 and length 6. This ruler is both optimal and perfect.

In mathematics, 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 and discovered independently by Sidon^[1] and Babcock.^[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 proven 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 finding the optimal Golomb rulers for a specified order is computationally very challenging. Distributed.net has completed distributed massively parallel searches for optimal order-24,^[4] order-25^[5] and order-26^[6]^[7] Golomb rulers, confirming the suspected candidates.^[8]^[9] Distributed.net also has plans to find optimal Golomb rulers 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.^[10] Distributed.net is actively searching for the optimal order-27 ruler; the expected time to discover it is about seven years.^[11]

One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennas in a [0,1,4,6] Golomb ruler configuration can often be seen at cell sites.^{[dubious – discuss]}

Currently, the complexity of finding optimal Golomb rulers of arbitrary order n (where n is given in unary) is unknown. Although some speculate that this is an NP-hard problem^[3], problems related to the construction of Golomb Rulers have been shown to be NP-hard where it is also noted that no known NP-complete problem has similar flavor to finding Golomb Rulers^[12].

1 Definitions
2 Methods of construction
- 2.1 Erdős–Turan construction
3 Known optimal Golomb rulers
4 See also
5 References
6 External links

Definitions

Golomb rulers as sets

A set of integers

$A = \left\{a_1,a_2,...,a_m\right\} \quad a_1 < a_2 < ... < a_m$

is a Golomb ruler if and only if

$\forall i,j,k,l \in \left\{1,2,...,m\right\}, a_i-a_j=a_k-a_l \iff i=k \and j=l$ ^[13]

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

$\forall i,j,k,l \in \left\{1,2,...,m\right\}, f(i)-f(j)=f(k)-f(l) \iff i=k \and j=l$ ^[14]^: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:^[14]^: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.

Methods of construction

A number of construction methods produce asymptotically optimal Golomb rulers.

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

$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.

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 0 3 4 9 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

References

^ S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539
^ Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.
^ ^a ^b "Modular and Regular Golomb Rulers". http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/JustinColannino.
^ "stats.distributed.net - OGR-24 Overall Project Stats". http://stats.distributed.net/projects.php?project_id=24. Retrieved 2008-03-27.
^ "stats.distributed.net - OGR-25 Overall Project Stats". http://stats.distributed.net/projects.php?project_id=25. Retrieved 2008-09-22.
^ http://n0cgi.distributed.net/cgi/planarc.cgi?user=bovine
^ http://www.distributed.net/projects.php
^ "distributed.net - .plan archives". http://n0cgi.distributed.net/cgi/planarc.cgi?user=nugget&plan=2004-11-01.10:24. Retrieved 2008-03-27.
^ "distributed.net - .plan archives 2". http://n0cgi.distributed.net/cgi/planarc.cgi?user=bovine&plan=2008-10-25.23:14. Retrieved 2008-10-26.
^ http://n0cgi.distributed.net/cgi/planarc.cgi?user=bovine&plan=2008-10-26.09:52
^ bovine's plan, 24-Feb-2009 17:26
^ C. Meyer, P.A. Papakonstantinou, "On the Complexity of Constructing Golomb Rulers". http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYW-4T9TBYY-2&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=202862ee62742f681c1cb98244414dc4. , Discrete Applied Mathematics
^ Dimitromanolakis, Apostolos (PDF). [http://www.cs.toronto.edu/%7Eapostol/golomb/main.pdf Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers]. http://www.cs.toronto.edu/%7Eapostol/golomb/main.pdf. Retrieved 2009-12-20.
^ ^a ^b 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ő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: 212–215.

Gardner, Martin (March 1972). "Mathematical games". Scientific American: 108–112.

External links

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What kind of ruler was Socrates or was he not a ruler? Read answer...
	Is the england ruler a good ruler or bad ruler? Read answer...
	Who China's ruler? Read answer...

	How are rulers made rulers?
	Why is a ruler called a ruler?
	Who were the rulers?

Golomb ruler

Contents