Härskare Golomb

En Golomb linjal i talteori  är en uppsättning icke-negativa heltal arrangerade som divisioner på en imaginär linjal på ett sådant sätt att avståndet mellan två divisioner är unikt. Det är med andra ord omöjligt att hitta två tal längs linjalens hela längd, vars skillnad skulle upprepas två gånger [1] .

De är uppkallade efter den amerikanske matematikern Solomon Golomb [2] , även om det första omnämnandet av sådana konstruktioner kan hittas i tidigare publikationer av Sidon [3] och Babcock [4] .

Definitioner

Antalet divisioner på Golomblinjalen kallas dess ordning , och det största avståndet mellan dess två divisioner kallas längd . Till exempel är en linjal med divisioner 0 1 4 9 11 en linjal av femte ordningen av längd 11. Ibland beskrivs Golomb-linjaler av avstånden mellan intilliggande divisioner, och inte av de absoluta koordinaterna för divisionerna, så linjalen ovan skulle ser ut som 1-3-5-2. Det maximala antalet par som kan göras från divisioner av en linjal av ordning n är lika med antalet kombinationer .

Linjaler som erhållits från en given genom att skifta varje division med ett fast nummer – till exempel 1 2 5 10 12 – eller genom att lista linjalens divisioner i omvänd ordning (spegelvänd) – till exempel 0 2 7 10 11 – anses likvärdig. Därför, i den kanoniska representationen av Golomb-linjalen, motsvarar den minsta divisionen nollkoordinaten, och divisionen som följer den är placerad på det minsta av de två möjliga avstånden.

Golomblinjalen är inte alltid lämplig för att mäta alla heltalsavstånd inom sin längd, men om den är lämplig kallas en sådan linjal perfekt ( engelska  Perfect Golomb Ruler  (english) , PGR). Perfekta linjaler finns bara för order mindre än fem.

En Golomb linjal kallas optimal ( Eng.  Optimal Golomb Ruler  (engelska) , OGR) om det inte finns några kortare linjaler av samma ordning. Med andra ord, en linjal är optimal om, i den kanoniska representationen, värdet av dess sista division är det minsta möjliga.

Att skapa en Golomb-linjal är relativt enkelt, men att bevisa en linjals optimalitet är en tidskrävande beräkningsprocess. För närvarande är en metod för att erhålla en optimal Golomb linjal av godtycklig längd n okänd, men detta problem tros vara NP-hårt .

Kända optimala Golomb linjaler

Golomblinjaler upp till ordning 150 är kända [5] , men optimalitet har bevisats endast för linjaler av ordning som inte överstiger 27. Följande tabell innehåller alla Golomblinjaler som är kända hittills i den kanoniska representationen för vilken optimalitet har bevisats.

Ordning Längd Divisioner luckor
ett 0 0 0
2 ett 0 1 ett
3 3 0 1 3 12
fyra 6 0 1 4 6 1 3 2
5 elva 0 1 4 9 11
0 2 7 8 11 		1 3 5 2
2 5 1 3
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 		1 3 6 2 5
1 3 6 5 2
1 7 3 2 4
1 7 4 2 3
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 		1 3 6 8 5 2
1 6 4 9 3 2
1 10 5 3 4 2
2 1 7 6 5 4
2 5 6 8 1 3
åtta 34 0 1 4 9 15 22 32 34 1 3 5 6 7 10 2
9 44 0 1 5 12 25 27 35 41 44
tio 55 0 1 6 10 23 26 34 41 53 55
elva 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
fjorton 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127
femton 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
arton 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
tjugo 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 49
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 5

Hitta optimala Golomb-linjaler

Den optimala 24:e ordningens Golomb linjal hittades 1967 av John P. Robinson och Arthur J. Bernstein . Dess optimalitet bevisades dock först den 1 november 2004 genom de kombinerade ansträngningarna från mer än 40 tusen människor från hela världen under 4 år och 110 dagar som en del av OGR-24- projektet för distribuerad dator [6] av icke- vinstorganisation distributed.net .

Den optimala Golomb-härskaren av 25:e ordningen hittades 1984 av Atkinson ( MD Atkinson ) och Hassenklover ( A. Hassenklover ). Beviset på dess optimalitet avslutades på 3006 dagar den 24 oktober 2008 som en del av OGR-25- projektet [7] .

Optimitetsbeviset för den 26:e ordningens Golomb-härskare avslutades på 24 dagar den 24 februari 2009 som en del av OGR-26- projektet [8] .

Optimalitetsbeviset för den 27:e ordningens Golomb-härskare färdigställdes 1822 dagar den 19 februari 2014 som en del av OGR-27- projektet [9] .

Beviset på optimaliteten hos Golomb-härskaren av den 28:e ordningen är OGR-28- projektet , som är 87,87 % färdigt den 4 september 2021 [10] .

Det distribuerade datorprojektet yoyo@home letar också efter optimala Golomb-linjaler .

Applikationer

En av de praktiska tillämpningarna av Golomb-linjalen är dess användning i fasade antennuppsättningar  - till exempel i radioteleskop . Antenner med [0 1 4 6]-konfigurationen kan hittas i CDMA cellulära basstationer .

Anteckningar

  1. ↑ Introduktion till Golomb-härskare av Mark Garry
  2. ↑ Solomon W. Golomb (länk ej tillgänglig) . Tillträdesdatum: 28 juli 2007. Arkiverad från originalet 28 juli 2007. 
  3. ↑ S. Sidon. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen  (tyska)  // Mathematische Annalen  : magazin. - 1932. - Bd. 106 . - S. 536-539 .
  4. ↑ Wallace C. Babcock. Intermodulationsstörningar i radiosystem/Frekvens av förekomst och styrning genom kanalval  // Bell System Technical  Journal : journal. - 1953. - Vol. 31 . - S. 63-73 .
  5. ↑ Golomb linjalbord Arkiverad 16 april 2018 på Wayback Machine 
  6. ↑ OGR-24 projektstatistik . Hämtad 22 december 2007. Arkiverad från originalet 17 februari 2016.
  7. ↑ OGR-25 projektstatistik . Hämtad 22 december 2007. Arkiverad från originalet 17 oktober 2013.
  8. ↑ OGR-26 projektstatistik . Hämtad 1 november 2008. Arkiverad från originalet 29 december 2014.
  9. ↑ OGR-27 projektstatistik . Tillträdesdatum: 8 januari 2010. Arkiverad från originalet 9 januari 2014.
  10. ↑ OGR-28 projektstatistik . Hämtad 26 februari 2014. Arkiverad från originalet 21 juli 2015.

Se även

Länkar