Golomb-Lineal

Golomb-Lineal der Ordnung 4 und Länge 6, das sowohl optimal als auch perfekt ist.

Ein Golomb-Lineal oder Golomb-Maßstab (häufig auch englisch Golomb Ruler nach dem englischen Fachbegriff) ist in der Zahlentheorie ein Lineal mit Markierungen an ganzzahligen Positionen, bei dem es keine zwei Paare von Markierungen mit dem gleichen Abstand zueinander gibt. Golomb-Lineale haben ihren Namen von Solomon W. Golomb, einem US-amerikanischen Professor für Mathematik und Elektrotechnik an der Universität von Südkalifornien.

Ein Golomb-Lineal kann definiert werden als endliche Menge ${\displaystyle M\subset \mathbb {Z} }$ mit der Eigenschaft: wenn ${\displaystyle a,b,c,d\in M}$ mit ${\displaystyle a\neq b}$ und ${\displaystyle |a-b|=|c-d|}$, dann ist ${\displaystyle \{a,b\}=\{c,d\}}$.

Allgemeines

Golomb-Lineale werden anhand ihrer Ordnung und ihrer Länge kategorisiert. Die Ordnung eines Golomb-Lineals ist dabei definiert durch die Anzahl der Markierungen, die Länge durch den größten Abstand zweier Markierungen. Da Parallelverschiebung und Spiegelung bei Golomb-Linealen als triviale Operationen angesehen werden, wird die erste Markierung üblicherweise bei 0 gesetzt und diejenige, die den kleinsten Abstand von einer Endmarkierung hat, an der kleineren der beiden möglichen positiven Positionen (sodass die erste und die zweite näher beieinander sind als die vorletzte und die letzte Markierung). Außerdem sollen die Abstände keinen gemeinsamen Teiler haben, sonst könnte man das Lineal um diesen Faktor verkürzen ([0,2,8,12] → [0,1,4,6]).

Ein Golomb-Lineal muss nicht alle Abstände bis zu seiner Länge messen können, es müssen also nicht alle Abstände zwischen den Markierungen – aufsteigend geordnet – eine lückenlose Zahlenreihe (1,2,3,4,5,…) ergeben. Wenn das jedoch der Fall ist, wird es ein perfektes Golomb-Lineal genannt. Es existieren keine perfekten Golomb-Lineale mit einer Ordnung größer als vier.[1] Ein Golomb-Lineal ist optimal, wenn es keine kürzeren Lineale derselben Ordnung gibt. Optimale Golomb-Lineale für eine gegebene Ordnung zu finden ist, im Gegensatz zum Erstellen von Linealen mit Golomb-Eigenschaft, eine rechenintensive Aufgabe. Mittels verteilten Rechnens wurden bislang optimale Golomb-Lineale bis zur Ordnung 28 durch das distributed.net-Projekt bestätigt. Das Projekt bestätigte zuletzt nach einer Gesamtdauer von über 8 Jahren das bis dahin kürzeste bekannte Lineal für die Ordnung 28.[2]

Die Suche nach einem optimalen Lineal der Ordnung 29 ist mit Stand 2022 von distributed.net nicht geplant, da der Aufwand zu hoch erscheint.[2]

Anwendung

Golomb-Lineale finden Anwendung beim Entwurf von Gruppenantennen wie beispielsweise Radioteleskopen. Antennen in [0,1,4,6] Golomb-Anordnung findet man häufig bei Mobilfunkmasten. Auch die Anordnung von Feldsensoren in Kernspintomographie nutzt Eigenschaften von Golomb-Maßstäben.

Bei beiden Anwendungen ist das Ziel, mit einer Minimalzahl an Elementen (Antennen, Sensoren) eine Maximalzahl an unterschiedlichen Abständen und im Dreidimensionalen eine Maximalzahl an verschiedenen Abstrahl- und Empfangswinkeln zu erreichen. Sind die verwendeten Golomb-Lineale optimal, wird auch noch die Ausdehnung des Messsystems bzw. der Gruppenantenne minimiert, was die Handhabbarkeit verbessert oder einen Einsatz überhaupt erst ermöglicht.

Bekannte optimale Golomb-Lineale

Demonstration, wie ein Konferenzraum mit den Proportionen des Golomb-Lineals [0, 2, 7, 8, 11] in 10 verschiedenen Größen konfiguriert werden kann.[3]

Die Tabelle zeigt die Werte für alle derzeit bekannten optimalen Golomb-Lineale bis zur Ordnung 28, wobei äquivalente Lineale (das heißt in umgekehrter Reihenfolge zu einem der angegebenen) nicht enthalten sind. Die ersten Vier stellen dabei perfekte Golomb-Lineale dar.

Ordnung	Länge	Markierungen	Bewiesen am	Bewiesen durch
1	0	0	1952[4]	Wallace Babcock
2	1	0 1	1952[4]	Wallace Babcock
3	3	0 1 3	1952[4]	Wallace Babcock
4	6	0 1 4 6	1952[4]	Wallace Babcock
5	11	0 1 4 9 11 0 2 7 8 11	c. 1967[5]	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[5]	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[5]	John P. Robinson and Arthur J. Bernstein
8	34	0 1 4 9 15 22 32 34	1972[5]	William Mixon
9	44	0 1 5 12 25 27 35 41 44	1972[5]	William Mixon
10	55	0 1 6 10 23 26 34 41 53 55	1972[5]	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[5]	William Mixon
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979[5]	John P. Robinson
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981[5]	John P. Robinson
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985[5]	James B. Shearer
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985[5]	James B. Shearer
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986[5]	James B. Shearer
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993[5]	W. Olin Sibert
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993[5]	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[5]	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?[5]	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. Mai 1998[6]	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[5]	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[5]	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. Oktober 2004[7]	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. Oktober 2008[8]	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. Februar 2009[9]	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. Februar 2014[10]	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[2]	distributed.net

Weblinks

• Freistetters Formelwelt: Ein etwas anderes Lineal (deutsch)
• Was ist eigentlich ein Optimaler Golomb-Maßstab? (englisch)
• Golomb rulers (englisch)
• Folge A003022 in OEIS

Einzelnachweise

1. Modular and Regular Golomb Rulers. Abgerufen im 1. Januar 1 
2. Completion of OGR-28 project. Abgerufen am 23. November 2022 (englisch). 
3. Paul Erdős, Paul Turan: On a problem of Sidon in additive number theory, and on some related problems. In: J. London Math. Soc. 16:212--215, 1941.
4. Rulers, Arrays, and Gracefulness Ed Pegg Jr. November 15, 2004. Math Games.
5. James B Shearer: Table of lengths of shortest known Golomb rulers. IBM, 19. Februar 1998, archiviert vom Original am 25. Juni 2016; abgerufen im 1. Januar 1 (englisch). 
6. In Search Of The Optimal 20 & 21 Mark Golomb Rulers (archived). Mark Garry, David Vanderschel et al, 26. November 1998, archiviert vom Original am 6. Dezember 1998; abgerufen im 1. Januar 1 (englisch). 
7. distributed.net - OGR-24 completion announcement. 1. November 2004; abgerufen im 1. Januar 1 (englisch). 
8. distributed.net - OGR-25 completion announcement. 25. Oktober 2008; abgerufen im 1. Januar 1 (englisch). 
9. distributed.net - OGR-26 completion announcement. 24. Februar 2009; abgerufen im 1. Januar 1 (englisch). 
10. distributed.net - OGR-27 completion announcement. 25. Februar 2014; abgerufen im 1. Januar 1 (englisch).