Лінійка Голомба
Лінійка Голомба в теорії чисел — набір невід'ємних цілих чисел, розташованих у вигляді поділок на уявній лінійці таким чином, що відстань між будь-якими двома поділками є унікальною. Іншими словами, на всій довжині лінійки неможливо знайти два числа, різниця між якими повторювалася б двічі[1].
Названі на честь американського математика Соломона Голомба[2], хоча перші згадки подібних конструкцій зустрічаються в раніших публікаціях Сідона[3] і Бебкока[4].
Визначення
Число поділок на лінійці Голомба називають її порядком, а найбільшу відстань між двома її поділками — довжиною. Наприклад, лінійка з поділками 0 1 4 9 11 є лінійкою п'ятого порядку довжини 11. Іноді лінійки Голомба описують відстанями між сусідніми поділками, а не абсолютними координатами поділок, тому наведена вище лінійка може виглядати як 1-3-5-2. Найбільше число пар, які можна скласти з поділок лінійки порядку n, дорівнює числу сполучень .
Лінійки, отримані з даної зсувом кожної поділки на фіксоване число — наприклад, 1 2 5 10 12, — або переліченням поділок лінійки в зворотному порядку (дзеркально-відбиті) — наприклад, 0 2 7 10, 11, — вважаються еквівалентними. Тому в канонічному поданні лінійки Голомба найменша поділка відповідає нульовій координаті, а наступна поділка розташовується на найменшій з двох можливих відстаней.
Лінійка Голомба не завжди придатна для вимірювання всіх цілочисельних відстаней у межах її довжини, проте якщо придатна, то таку лінійку називають досконалою (англ. Perfect Golomb Ruler, PGR). Досконалі лінійки існують тільки для порядків, менших від п'яти.
Лінійку Голомба називають оптимальною (англ. Optimal Golomb Ruler, OGR), якщо не існує коротших лінійок того ж порядку. Іншими словами, лінійка є оптимальною, якщо в канонічному поданні значення її останньої поділки мінімально можливе.
Створити лінійку Голомба відносно просто, але доведення оптимальності лінійки є трудомістким обчислювальним процесом. Нині спосіб отримання оптимальної лінійки Голомба довільної довжини n невідомий, проте вважають, що ця задача є NP-складною.
Відомі оптимальні лінійки Голомба
Відомі лінійки Голомба до 150-го порядку[5], однак оптимальність доведено тільки для лінійок порядку, що не перевищує 27. В таблиці наведено всі відомі нині лінійки Голомба в канонічному поданні, для яких доведено оптимальність.
Порядок | Довжина | Поділки | Проміжки |
---|---|---|---|
1 | 0 | 0 | 0 |
2 | 1 | 0 1 | 1 |
3 | 3 | 0 1 3 | 1 2 |
4 | 6 | 0 1 4 6 | 1 3 2 |
5 | 11 | 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 170 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 42 5 6 8 1 3 |
8 | 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 | |
10 | 55 | 0 1 6 10 23 26 34 41 53 55 | |
11 | 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 | |
14 | 127 | 0 4 6 20 35 52 59 77 78 86 89 99 122 127 | |
15 | 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 | |
18 | 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 | |
20 | 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 492 | |
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 553 |
Відшукання оптимальних лінійок Голомба
Оптимальну лінійку Голомба 24-го порядку знайшли 1967 року Джон Робінсон (John P. Robinson) та Артур Бернштейн (Arthur J. Bernstein). Однак її оптимальність доведено лише 1 листопада 2004 року спільними зусиллями більш ніж 40 тисяч осіб з усього світу протягом 4 років і 110 днів у рамках проєкту розподілених обчислень OGR-24[6] некомерційної організації distributed.net.
Оптимальну лінійку Голомба 25-го порядку знайшли 1984 року Аткінсон (MD Atkinson) і Хассенкловер (A. Hassenklover). Доведення її оптимальності завершено за 3006 днів 24 жовтня 2008 року в рамках проєкту OGR-25[7].
Доведення оптимальності лінійки Голомба 26-го порядку завершено за 24 дні 24 лютого 2009 року в рамках проєкту OGR-26[8].
Доведення оптимальності лінійки Голомба 27-го порядку завершено за тисячу вісімсот двадцять два дні 19 лютого 2014 року в рамках проєкту OGR-27[9].
Над доведенням оптимальності лінійки Голомба 28-го порядку працює проєкт OGR-28, який на 10 грудня 2020 року виконано на 78,41 %[10].
Також пошуком оптимальних лінійок Голомба займається проєкт розподілених обчислень yoyo@home.
Застосування
Одним з практичних застосувань лінійки Голомба, є використання її у фазованих антенних решітках — наприклад, у радіотелескопах. Антени з конфігурацією [0 1 4 6] можна зустріти в базових станціях стільникового зв'язку стандарту CDMA.
Примітки
- Introduction To Golomb Rulers by Mark Garry
- Solomon W. Golomb. Архів оригіналу за 28 липня 2007. Процитовано 28 липня 2007.
- S. Sidon. Ein Satzuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen // Mathematische Annalen : magazin. — 1932. — Bd. 106 (23 Januar). — S. 536—539.
- Wallace C. Babcock. Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection // Bell System Technical Journal : journal. — 1953. — Vol. 31 (23 January). — P. 63—73.
- Golomb ruler table(англ.)
- Статистика проекта OGR-24
- Статистика проекта OGR-25
- Статистика проекта OGR-26
- Статистика проекта OGR-27
- Статистика проекта OGR-28
Див. також
- Масив Костаса
- Досконала лінійка
- Паралельні обчислювальні системи
- Розподілені обчислення
Посилання
- Досконалі й оптимальні лінійки (рос.)
- Perfect and Optimal Rulers (англ.)
- Mark Garry. «In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers»
- Ed Pegg Jr. «Rulers, Arrays, and Gracefulness»
- Weisstein, Eric W. Лінійка Голомба(англ.) на сайті Wolfram MathWorld.
- James B. Shearer. Golomb ruler pages