Golombin viivain

Optimaalinen neljän pisteen Golombin viivain.

Golombin viivain on sellainen joukko kokonaislukuja, ymmärrettynä pisteiksi lukusuoralla, että samaa kahden pisteen välistä etäisyyttä ei esiinny eri pistepareissa. Esimerkiksi {0, 1, 3} on Golombin viivain, koska sen pisteiden välillä on etäisyydet 1, 2 ja 3, jotka ovat kaikki erisuuria. Sen sijaan {0,1,2} ei ole Golombin viivain, koska etäisyys 1 esiintyy kaksi kertaa, sekä pisteiden 0 ja 1 välillä että pisteiden 1 ja 2 välillä. Ne on nimetty Solomon Golombin mukaan, joskaan Golomb ei ollut ensimmäinen, joka tutki niitä. Golombin viivaimilla on sovellutuksia muun muassa radioteleskooppien antennien sijoittelussa, radiokanavien valinnassa, röntgenkristallografiassa ja koodausteoriassa.

Golombin viivainta voidaan siirtää ja peilata lukusuoralla etäisyyksien muuttumatta, joten esimerkiksi viivain {10,11,13} on olennaisesti sama kuin {0,1,3}. Niinpä tavallisesti tarkastellaan vain viivaimia, jotka ovat kanonisessa muodossa: pienin luku on nolla, ja viivaimista, jotka ovat toistensa peilikuvia, valitaan leksikaalisesti pienempi. Kanoninen Golombin viivain, jossa on n pistettä, on optimaalinen, jos sen pituus eli päätepisteiden välinen etäisyys on mahdollisimman pieni n-pisteisten viivaimien joukossa. Esimerkiksi {0,1,3} on optimaalinen kolmen pisteen viivain, mutta {0,1,10} ei.

Historia

Simon Sidon, Paul Erdős ja Pál Turán tutkivat 1930-luvulla Sidonin joukkoja eli lukujoukkoja, joissa kaikkien parien summat ovat erisuuret. Sophie Piccard puolestaan tutki 1930-luvulla lukujoukon alkioiden erotusten muodostamia joukkoja, ja esitti 1939 muun muassa väittämän, että jos kahdella Golombin viivaimella (joita ei silloin vielä kutsuttu sillä nimellä) on samat erotusjoukot, niin joukot ovat siirtoa ja peilausta vaille samat. Väite osoittautui vääräksi, kun Gary Bloom vuonna 1977 löysi kaksi erilaista 6 pisteen viivainta, joiden erotusjoukot ovat samat, nimittäin {0,1,4,10,12,17} ja {0,1,8,11,13,17}. Kaikille suuremmille viivaimille Piccardin väittämä kuitenkin pätee, minkä Ahmad Bekir ja Solomon Golomb osoittivat 2007.

Sidonin joukot ja Golombin viivaimet ovat sama asia eri muodossa, ja niiden välinen yhteys on varsin yksinkertainen. Jos nimittäin joukko ei ole Golombin viivain, niin siinä on sellaiset neljä alkiota $a,b,c,d$, että $a-b=c-d$. Silloin myös $a+d=b+c$, eli joukko ei ole myöskään Sidonin joukko. Myös käänteinen on helppo osoittaa. Yhteyttä Sidonin joukkojen ja Golombin viivaimien välillä ei kuitenkaan alkuun huomattu, koska näitä ongelmia tutkivat eri tutkijat.

Edellisistä riippumatta Wallace C. Babcock tutki 1950-luvulla radiokanavien valintaongelmaa, joka johti Golombin viivaimiin. Hän löysi optimaaliset viivaimet enintään 8 pisteelle. Optimaalinen 8 pisteen viivain on {0, 1, 4, 9, 15, 22, 32, 34}. 1960-luvulla Solomon Golomb tutki viivaimia systemaattisesti. Hän käytti niistä nimeä minimum spanning rulers, mutta vuonna 1972 Martin Gardner nimesi ne Golombin viivaimiksi (engl. Golomb’s rulers) Scientific Americanin kolumnissaan.

Optimaalisten viivainten etsintä

Viime aikoina optimaalisia viivaimia on etsitty massiivisesti hajautetulla laskennalla distributed.net-projektissa. Optimaalinen 27 pisteen viivain selvitettiin projektissa, joka kesti viitisen vuotta ja valmistui vuonna 2014. Sen jälkeen vuosina 2014–2022 selvitettiin optimaalinen 28 pisteen viivain. Sen pituus on 585, ja itse viivain on

{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}.

Tunnetut optimaalisten viivainten pituudet on lueteltu OEIS-tietokannassa.

Suuret viivaimet

Erdősin ja Turánin vuonna 1941 esittämällä konstruktiolla voidaan helposti muodostaa suuriakin Golombin viivaimia, vaikkakaan ei optimaalisia. Jos $n$ on alkuluku, niin joukko

$\{2nk+(k^{2}{\bmod {n}})\;:\;k=0,1,\ldots ,n-1\}$

on Golombin viivain, jossa on $n$ pistettä. Sen pituus on hiukan vähemmän kuin $2n^{2}$. Lyhyempiäkin konstruktioita tunnetaan: Imre Ruzsan konstruktiossa n pisteen viivaimen pituus on vain hiukan enemmän kuin n². Erdősin vuonna 1934 esittämän konjektuurin mukaan kaikilla n on olemassa n pisteen Golombin viivaimia, joiden pituus on vähemmän kuin n². Konjektuuria ei ole todistettu, mutta Apostolos Dimitromanolakis on vuonna 2002 laskennallisesti varmistanut sen 65 000 pisteen viivaimiin asti.