We zetten op een liniaal een aantal markeringen, op zo’n manier dat geen afstand tussen twee markeringen tweemaal voorkomt. Een dergelijke liniaal heet Golomb-liniaal. De reeks 0, 1, 4, 6 vormt een Golomb-liniaal: elke twee getallen uit de reeks hebben een ander verschil, zoals in onderstaande figuur is te zien. Golomb-linialen zijn voor uiteenlopende toepassingen als radioastronomie, de constructie van röntgendiffractiemicroscopen en cryptografie bruikbaar.
Een Golomb-liniaal is een reeks niet-negatieve gehele getallen waarbij geen twee getallen uit deze reeks hetzelfde verschil hebben. Hier zie je een optimale Golomb-liniaal (Engels: Optimal Golomb Ruler (OGR)) van orde 4 en lengte 6 (d.w.z.: 4 merktekens tussen de 0 en de 6)
Perfecte en optimale linialen
Bij de Golomb-liniaal 0, 1, 4, 6 komen de afstanden 1 tot en met 6 allemaal eenmaal voor. Deze mooie eigenschap geldt voor lang niet elke Golomb-liniaal. Bij langere linialen zullen er in het algemeen gaten vallen in de afstanden die voorkomen. Een liniaal die alle verschillen tussen 1 en zijn eigen lengte bevat, heet een perfecte Golomb-liniaal.
Een optimale liniaal is de kortste liniaal met n getallen (waarbij kortste betekent dat het laatste getal uit de reeks zo klein mogelijk is). De genoemde liniaal 0, 1, 4, 6 is behalve perfect ook optimaal.
Golomb-linialen zijn vernoemd naar Solomon W. Golomb (geboren 1932), een wiskundige die gespecialiseerd is in de combinatoriek, getaltheorie en coderingstheorie. Naast zijn wiskundig onderzoek heeft hij veel aan popularisering gedaan: hij verzorgde jarenlang de rubriek ‘Mathematical Games’ in de Scientific American.
Zoektocht via gedistribueerde berekeningen
Bij een gedistribueerde berekening wordt een groot probleem opgedeeld in kleine stukken die afzonderlijk door diverse computers kunnen worden opgelost. Het project OGR-25, de zoektocht naar een optimale Golomb-liniaal van orde 25, is een cryptografieproject van Distributed.net.
Onlangs is er een nieuwe optimale Golomb-liniaal gevonden. De optimale Golomb-liniaal van orde 25 heeft een lengte van 480 en bevat de volgende getallen: 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. Het duurde jaren rekenen met duizenden computers om te bewijzen dat deze Golomb-liniaal inderdaad de kortste is voor 25 getallen. De reeks zelf was overigens al in 1984 gevonden.
Voor het project OGR-25 van Distributed.net zijn 3006 dagen en 124.387 deelnemers nodig geweest
NP-volledig
Het vinden van optimale Golomb-linialen wordt ‘exponentieel moeilijker’ naarmate het aantal markeringen toeneemt. Wiskundigen spreken van een NP-volledig probleem. NP-volledigheid is een begrip uit de compexiteitstheorie. NP-volledige problemen behoren tot de moeilijkst oplosbare problemen. Daarom zoekt men naar lange optimale Golomb-linialen door middel van via internet gedistribueerde berekeningen; iedereen kan dan zijn steentje bijdragen en dan is het probleem toch nog behapbaar.
Zie ook:
- Golomb ruler (MathWorld; Eng.)
- Golomb ruler (Wikipedia; Eng.)
- De website van Distributed.net
- Distributed.net rondt zoektocht naar OGR-25 af