Golombin viivain

Wikipediasta
Siirry navigaatioon Siirry hakuun
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.[1] 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ä. Scientific Americanin kolumnisti Martin Gardner nimesi viivaimet Solomon Golombin mukaan[2], joskaan Golomb ei ollut ensimmäinen, joka tutki niitä.[3] Golombin viivaimilla on sovellutuksia muun muassa radioteleskooppien antennien sijoittelussa, radiokanavien valinnassa, röntgenkristallografiassa ja koodausteoriassa.[4]

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.[1] Esimerkiksi {0,1,3} on optimaalinen kolmen pisteen viivain, mutta {0,1,10} ei.

Historia[muokkaa | muokkaa wikitekstiä]

Simon Sidon, Paul Erdős ja Pál Turán tutkivat 1930-luvulla Sidonin joukkoja eli lukujoukkoja, joissa kaikkien parien summat ovat erisuuret.[5] 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.[6]

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}.[3][7]

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 , että . Silloin myös , 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.[5]

Optimaalisten viivainten etsintä[muokkaa | muokkaa wikitekstiä]

Viime aikoina optimaalisia viivaimia on etsitty massiivisesti hajautetulla laskennalla distributed.net-projektissa. Osaprojekti OGR-27 valmistui vuonna 2014 kestettyään noin viisi vuotta. Sen tuloksena oli, että optimaalisia 27 pisteen viivaimia on olemassa tasan yksi, ja sen pituus on 553. Kyseinen 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}.[8]

28 pisteen viivainten etsintä on käynnissä.[9] Tunnetut optimaalisten viivainten pituudet on lueteltu OEIS-tietokannassa.[10]

Suuret viivaimet[muokkaa | muokkaa wikitekstiä]

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

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

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. a b Golomb Ruler MathWorld. Viitattu 23.10.2020. (englanniksi)
  2. Golomb, Solomon W.: Golomb’s Reminiscences (Sivut 235-245) Mathematical Properties of Sequences and Other Combinatorial Structures. 2003. Boston: Springer. Viitattu 23.10.2020. (englanniksi)
  3. a b Pegg, Ed Jr.: Rulers, Arrays, and Gracefulness Math Games. 15.11.2004. Viitattu 23.10.2020. (englanniksi)
  4. Alperin, Roger C. & Drobot, Vladimir: Golomb Rulers. Mathematics Magazine, 2011, 84. vsk, s. 48–55. (englanniksi)
  5. a b c Dimitromanolakis, Apostolos: Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers (Diplomityö) 2002. Technical University of Crete. Viitattu 24.10.2020. (englanniksi)
  6. Bekir, Ahmad & Golomb, Solomon W.: There are no further counterexamples to S. Piccard’s theorem. IEEE Transactions on Information Theory, 2007, 53. vsk, nro 8, s. 2864–2867. (englanniksi)
  7. Babcock, Wallace C.: Intermodulation interference in radio systems frequency of occurrence and control by channel selection. The Bell System Technical Journal, 1953, 32. vsk, nro 1, s. 63–73. Artikkelin verkkoversio. (englanniksi)
  8. Reed, Mike: The OGR-27 project has been completed 25.2.2014. distributed.net. Viitattu 23.10.2020. (englanniksi)
  9. OGR-28 / Overall Project Stats distributed.net. Viitattu 23.10.2020. (englanniksi)
  10. A003022 Length of shortest (or optimal) Golomb ruler with n marks. The On-line Encyclopedia of Integer Sequences. The OEIS Foundation. Viitattu 23.10.2020. (englanniksi)