# Golomb-liniaal

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 naar de Amerikaanse hoogleraar Solomon genoemd in de wiskunde en elektrotechniek aan de University of Southern California.
De getallen op een golomb-liniaal vormen een sidonverzameling. Een sidonverzameling is een verzameling van natuurlijke getallen, waarvan iedere verschil tussen twee verschillende elementen uniek is of waarvan iedere som van twee elementen uniek is. De getallen mogen bij het optellen twee keer worden genomen, dus de som van een getal met zichzelf. De Hongaarse wiskundige Simon Sidon rekende al eerder met sidonverzamelingen dan dat er golomb-linialen waren. Hij gebruikte ze in 1932 bij het bestuderen van fourierreeksen.
Verschuiven en spiegelen van een golomb-liniaal geven eigenlijk dezelfde liniaal, zodat als kleinste getal meestal 0 wordt gekozen en als eerstvolgende het kleinste van de twee verschillen aan de uiteinden van de rij, aan het begin en aan het einde.
Een golomb-liniaal met alle verschillen tot aan de lengte van de rij heet perfect. Zo een liniaal met $n$ markeringen is ${\tfrac {1}{2}}n(n-1)$ eenheden lang en er komen de verschillen van 1 tot en met ${\tfrac {1}{2}}n(n-1)$ op voor. Er bestaan geen perfecte golomb-linialen voor $n$ groter dan 4.

## Optimale golomb-linialen

Een golomb-liniaal heet optimaal als er geen kortere golomb-liniaal is van dezelfde orde. De lengte van een optimale golomb-liniaal met $n$ getallen, voor $n=2,3,4,\ldots$ is: $1,3,6,11,17,25,34,\ldots$
Golomb-linialen zijn eenvoudig te maken, maar het vinden van de optimale linialen van een bepaalde orde is lastig en rekentechnisch tijdrovend. Het vinden van de optimale golomb-liniaal wordt exponentieel moeilijker naarmate het aantal getallen er op toeneemt. Er is geen manier of algoritme bekend voor het maximale aantal getallen op een golomb-liniaal van gegeven lengte of wat de kortst mogelijke golomb-liniaal is met een gegeven aantal getallen. Het berekenen van optimale golomb-linialen met veel getallen kan met behulp van parallel rekenen worden gedaan. Dat is in 2022 gedaan om de lijst met 28 getallen compleet te maken, dat ging met distributed computing.
Methoden om golomb-linialen te construeren zijn besproken in een artikel van Konstantinos Drakakis.
Optimale golomb-linialen kunnen bij het plaatsen van sensoren bij röntgenkristallografie en voor het plaatsen van antennes in de radioastronomie gebruikt.
De onderstaande tabel bevat alle tot nu toe bekende optimale golomb-linialen.
| Orde | Lengte | Getallen |
| 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 |
| 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 |

### voetnoten

* ↑ S Sidon. Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen, 1932. voor Mathematische Annalen 106, blz 536–539
* ↑ rij A003022 in OEIS voor optimale golomb-linialen
* ↑ distributed.net. OGR.
* ↑ K Drakakis. A review of the available construction methods for Golomb rulers, 2009. in Advances in Mathematics of Communications 3, 3, blz 235-250. DOI:10.3934/amc.2009.3.235

### websites

* IBM. Model a Golomb Ruler, gewijzigd op 25 april 2024.
* www.luschny.de. Perfect and Optimal Rulers.