Golomblinjal

Innen matematikken er en Golomblinjal ett sett merker på heltallsposisjoner langs en imaginær linjal, som er plassert slik at alle par av merker står med forskjellig avstand. Antallet markører på linjalen er dens orden, og den lengste distansen mellom to av markørene er dens lengde. Translasjon og refleksjon av en Golomblinjal anses som likegyldig, slik at den minste markøren starter som regel på 0, og den neste markøren settes som regel på den laveste av sine mulige verdier.

Golomblinjalen har fått sitt navn etter Solomon W. Golomb, men har blitt uavhengig oppdaget av Sidon og Babcock

Det er ikke påkrevet at en Golomblinjal skal kunne gi alle distansene opp til dens lengde, men om den gjør det, så kalles den perfekt. Det har blitt bevist at det ikke eksisterer perfekte Golomblinjaler for fem eller flere markører. En Golomblinjal er optimal om det ikke finnes kortere Golomblinjaler med samme orden (antall markører). Å lage Golomblinjaler er enkelt, men å finne den optimale Golomblinjalen for en gitt orden er beregningsmessig meget utfordrende. Distributed.net har gjennomført massivt distriuerte parallelle søk for optimale orden-24, orden-25, orden-26 og orden-27 Golomblinjaler, og har bekreftet de anslåtte optimale kandidatene
. Distributed.net har også planlagt å finne/bekrefte en optimal Golomblinjal for orden-28. Det var forventet at Golomblinjalene for orden-27 og orden-28 tok kortere tid å finne/bekrefte enn de foregående prosjektene, grunnet oppdagelsen av forbedrede algoritmer.

En praktisk tilnærming til bruk av Golomblinjaler er innen design og utforming av faseordnede radioantenner slik som radioteleskop.

For tiden så er kompleksiteten i å finne en optimal Golomblinjal for en vilkårlig orden-n ukjent, men er oppfattet å være et NP-vanskelig problem

Kjente optimale Golomblinjaler
Den følgende tabellen inneholder alle kjente, verifiserte, optimale Golomblinjaler, hvor de som har markører i reversert orden er utelatt.

 Den optimale linjalen ble oppdaget før denne datoen. Denne datoen representerer tidspunktet da linjalen ble funnet å være optimal (fordi alle andre varianter beviselig ikke var mindre).

Referanser 
 og Babcock

Se også

Eksterne lenker
 James B. Shearer's Golomb ruler pages
 distributed.net: Project OGR
 In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers
 "Rulers, Arrays, and Gracefulness" by Ed Pegg Jr.
 Golomb rulers up to length of over 200 (via Internet Archive)
 

Tallteori