Лінійка Голомба
Лінійка Голомба в теорії чисел — набір невід'ємних цілих чисел, розташованих у вигляді поділок на уявній лінійці таким чином, що відстань між будь-якими двома поділками є унікальною. Іншими словами, на всій довжині лінійки неможливо знайти два числа, різниця між якими повторювалася б двічі[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, — вважаються еквівалентними. Тому в канонічному поданні лінійки Голомба найменша поділка відповідає нульовій координаті, а наступна поділка розташовується на найменшій з двох можливих відстаней.
Лінійка Голомба не завжди придатна для вимірювання всіх цілочисельних відстаней у межах її довжини, проте якщо придатна, то таку лінійку називають досконалою (Шаблон:Lang-en, PGR). Досконалі лінійки існують тільки для порядків, менших від п'яти.
Лінійку Голомба називають оптимальною (Шаблон:Lang-en, 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.
Примітки
Див. також
Посилання
- Досконалі й оптимальні лінійки Шаблон:Webarchive Шаблон:Ref-ru
- Perfect and Optimal Rulers Шаблон:Webarchive Шаблон:Ref-en
- Mark Garry. «In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers»
- Ed Pegg Jr. «Rulers, Arrays, and Gracefulness»
- Шаблон:MathWorld
- James B. Shearer. Golomb ruler pages Шаблон:Webarchive