Golomb-liniaal

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen
Golomb-limiaal van orde 4 en lengte 6. Deze liniaal is zowel optimaal als perfect.

Een Golomb-liniaal is in de wiskunde een rij natuurlijke getallen die zo is samengesteld dat geen twee paren getallen uit de rij hetzelfde verschil hebben. Het aantal getallen heet de orde van de liniaal en het grootste voorkomende verschil de lengte. Qua concept lijkt dit op een liniaal die zo is gemaakt dat geen tweetal strepen dezelfde afstand heeft als een ander paar. De Golomb-liniaal is genoemd naar Solomon W. Golomb, een Amerikaanse hoogleraar wiskunde en elektrotechniek aan de universiteit van Zuid-Californië.

De getallen op een Golomb-liniaal vormen een Sidon-verzameling. Een Sidon-verzameling is een verzameling van natuurlijke getallen, waarvan elk verschil tussen twee verschillende elementen uniek is; of waarvan elke som van twee (niet noodzakelijk verschillende) elementen uniek is. Sidon-verzamelingen dateren van voor de Golomb-linialen; de Hongaarse wiskundige Simon Sidon gebruikte ze bij zijn studie van Fourierreeksen in 1932.[1]

Verschuiven en spiegelen van een Golomb-liniaal geven in essentie dezelfde liniaal, zodat als kleinste getal gewoonlijk 0 wordt gekozen.

Een Golomb-liniaal die alle afstanden tot aan z'n lengte kan meten wordt perfect genoemd. Zo een liniaal met markeringen is exact eenheden lang en kan de afstanden van 1 tot en met meten. Er bestaan geen perfecte Golomb-linialen voor groter dan 4.

Een Golomb-liniaal heet optimaal als er geen kortere Golomb-liniaal is van dezelfde orde. De lengte van een optimale Golomb-liniaal met markeringen, voor is: [2]

Golomb-linialen zijn eenvoudig te maken, maar het vinden van de optimale linialen van een bepaalde orde is lastig en rekentechnisch tijdrovend. Let wel: het vinden (en bewijzen) van OGR's wordt exponentieel moeilijker naarmate het aantal markeringen toeneemt. Er is geen formule of algoritme bekend dat zegt wat het maximaal aantal markeringen is voor een Golomb-liniaal van gegeven lengte, of wat de kortst mogelijke Golomb-liniaal is met een gegeven aantal markeringen. Het berekenen van OGR's met veel markeringen kan worden gedaan door in parallel van een groot aantal beginreeksen te bepalen of er een OGR mee kan worden gemaakt. Op dit moment wordt dit voor een OGR met 28 markeringen gedaan in een zogenaamd distributed computing-project.[3]

Methoden om Golomb-linialen te construeren zijn besproken in een artikel van Konstantinos Drakakis.[4]

Optimale Golomb-linialen (OGR's) hebben veel toepassingsmogelijkheden waaronder sensorplaatsing bij röntgendiffractie, in de kristallografie en voor de plaatsing van antennes in de radio-astronomie.

Bekende optimale Golomb-linialen[bewerken]

De onderstaande tabel bevat alle tot nu toe bekende optimale Golomb-linialen.


orde lengte 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
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

Externe links[bewerken]