Линейка Голомба

Линейка Голомба в теории чисел — набор неотрицательных целых чисел, расположенных в виде делений на воображаемой линейке таким образом, что расстояние между любыми двумя делениями является уникальным. Другими словами, на всём протяжении линейки нельзя найти два числа, разность между которыми повторялась бы дважды.
 Названы в честь американского математика Соломона Голомба, хотя первые упоминания подобных конструкций встречаются в более ранних публикациях и Бэбкока.

Определения


 Число делений на линейке Голомба называют её порядком, а наибольшее расстояние между двумя её делениями — длиной. Например, линейка с делениями 0 1 4 9 11 является линейкой пятого порядка длины 11. Иногда линейки Голомба описываются расстояниями между соседними делениями, а не абсолютными координатами делений, поэтому приведённая выше линейка будет выглядеть как 1-3-5-2. Максимальное число пар, которые можно составить из делений линейки порядка n, равно числу сочетаний (n2)=n(n1)2.
 Линейки, полученные из данной путём сдвига каждого деления на фиксированное число — например, 1 2 5 10 12, — или перечислением делений линейки в обратном порядке (зеркально-отражённые) — например, 0 2 7 10 11, — считаются эквивалентными. Поэтому в каноническом представлении линейки Голомба наименьшее деление соответствует нулевой координате, а следующее за ним деление располагается на наименьшем из двух возможных расстоянии.
 Линейка Голомба не всегда пригодна для измерения всех целочисленных расстояний в пределах её длины, однако если пригодна, то такую линейку называют совершенной (, PGR). Совершенные линейки существуют только для порядков, меньших пяти.
 Линейку Голомба называют оптимальной (, OGR), если не существует более коротких линеек того же порядка. Другими словами, линейка является оптимальной, если в каноническом представлении значение её последнего деления минимально возможное.
 Создать линейку Голомба относительно просто, но вот доказательство оптимальности линейки является трудоёмким вычислительным процессом. В настоящее время способ получения оптимальной линейки Голомба произвольной длины n неизвестен, однако полагают, что эта задача является NP-трудной.

Известные оптимальные линейки Голомба


 Известны линейки Голомба до 150-го порядка, однако оптимальность доказана только для линеек порядка, не превышающего 27. Следующая таблица содержит все известные на сегодняшний день линейки Голомба в каноническом представлении, для которых доказана оптимальность.
ПорядокДлинаДеленияПромежутки
1000
210 11
330 1 31 2
460 1 4 61 3 2
5110 1 4 9 11
0 2 7 8 111 3 5 2
2 5 1 3
6170 1 4 10 12 17
0 1 4 10 15 17
0 1 8 11 13 17
0 1 8 12 14 171 3 6 2 5
1 3 6 5 2
1 7 3 2 4
1 7 4 2 3
7250 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 251 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
8340 1 4 9 15 22 32 341 3 5 6 7 10 2
9440 1 5 12 25 27 35 41 44
10550 1 6 10 23 26 34 41 53 55
11720 1 4 13 28 33 47 54 64 70 72
0 1 9 19 24 31 52 56 58 69 72
12850 2 6 24 29 40 43 55 68 75 76 85
131060 2 5 25 37 43 59 70 85 89 98 99 106
141270 4 6 20 35 52 59 77 78 86 89 99 122 127
151510 4 20 30 57 59 62 76 100 111 123 136 144 145 151
161770 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177
171990 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199
182160 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216
 - style=``padding: 0 1em'' style=``padding: 0 1em''
19

Нахождение оптимальных линеек Голомба


 Оптимальная линейка Голомба 24-го порядка была найдена в 1967 году Джоном Робинсоном (John P. Robinson) и Артуром Бернштейном (Arthur J. Bernstein). Однако её оптимальность была доказана лишь 1 ноября 2004 года объединёнными усилиями более чем 40 тысяч человек со всего мира в течение 4 лет и 110 дней в рамках проекта распределённых вычислений OGR-24 некоммерческой организации distributed.net.
 Оптимальная линейка Голомба 25-го порядка была найдена в 1984 году Аткинсоном (M. D. Atkinson) и Хассенкловером (A. Hassenklover). Доказательство её оптимальности было завершено за 3006 дней 24 октября 2008 года в рамках проекта OGR-25.
 Доказательство оптимальности линейки Голомба 26-го порядка было завершено за 24 дня 24 февраля 2009 года в рамках проекта OGR-26.
 Доказательство оптимальности линейки Голомба 27-го порядка было завершено за 1822 дня 19 февраля 2014 года в рамках проекта OGR-27.
 Доказательством оптимальности линейки Голомба 28-го порядка занимается проект OGR-28, который на 5 августа 2017 года выполнен на 37.27 Также поиском оптимальных линеек Голомба занимается проект распределённых вычислений yoyo@home.

Применения


 Одним из практических применений линейки Голомба, является использование её в фазированных антенных решётках — например, в радиотелескопах. Антенны с конфигурацией [0 1 4 6] можно встретить в базовых станциях сотовой связи стандарта CDMA.