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

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

Определения


 Число делений на линейке Голомба называют её порядком, анаибольшее расстояние между двумя её делениями — длиной.Например, линейка с делениями 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 310 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 42
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.