Голомб правитель

«ОГР» перенаправляется сюда. Чтобы узнать о других значениях, см. OGR (значения) .

Линейка Голомба порядка 4 и длины 6. Эта линейка одновременно оптимальна и совершенна .

Совершенные круговые линейки Голомба (также называемые разностными наборами ) с указанным порядком. (В этом предварительном просмотре должно быть показано несколько концентрических кругов. Если нет, нажмите, чтобы просмотреть увеличенную версию.)

В математике линейка Голомба — это набор меток в целых позициях на линейке, при котором никакие две пары меток не находятся на одинаковом расстоянии друг от друга. Количество отметок на линейке — это ее порядок , а наибольшее расстояние между двумя ее отметками — ее длина . Перевод и отражение линейки Голомба считаются тривиальными, поэтому наименьшая отметка обычно ставится в 0, а следующая отметка — в меньшее из двух возможных значений. Линейки Голомба можно рассматривать как одномерный частный случай массивов Костаса .

Правитель Голомба был назван в честь Соломона В. Голомба и открыт независимо Сидоном (1932 г.). и Бэбкок (1953) . Софи Пиккар также опубликовала раннее исследование этих множеств в 1939 году, сформулировав в качестве теоремы утверждение о том, что две линейки Голомба с одинаковым набором расстояний должны быть конгруэнтны . Это оказалось неверным для шеститочечных линеек, но в остальном верно.

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

Distributed.net завершил массовые параллельные поиски оптимальных правителей Голомба от 24-го до 28-го порядков, каждый раз подтверждая предполагаемого кандидата в правители.

В настоящее время сложность поиска оптимальных линеек Голомба (ОГР) произвольного порядка n (где n задано в унарном виде) неизвестна. В прошлом существовали предположения, что это NP-сложная проблема. Доказано, что проблемы, связанные с построением линеек Голомба, являются NP-сложными, при этом также отмечается, что ни одна известная NP-полная задача не имеет такого же вкуса, как поиск линеек Голомба.

Определения

Линейки голомбов

Набор целых чисел $A=\{a_{1},a_{2},...,a_{m}\}$ где $a_{1}<a_{2}<...<a_{m}$ является линейкой Голомба тогда и только тогда, когда

${\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ and }}j=l.$

Порядок правителя такого голомбского $m$ его длина и $a_{m}-a_{1}$. Каноническая форма имеет $a_{1}=0$ и, если $m>2$, $a_{2}-a_{1}<a_{m}-a_{m-1}$. Такой формы можно достичь посредством перевода и рефлексии.

как

Инъективная функция $f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}$ с $f(1)=0$ и $f(m)=n$ является линейкой Голомба тогда и только тогда, когда

${\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ and }}j=l.$

Порядок правителя такого голомбского $m$ его длина и $n$. Каноническая форма имеет

$f(2)<f(m)-f(m-1)$ если $m>2$.

Оптимальность

Линейка Голомба порядка m и длины n может быть оптимальной в двух отношениях:

• Он может быть оптимально плотным , демонстрируя максимальное m для конкретного значения n ,
• Он может быть оптимально коротким и иметь минимальное n для конкретного значения m .

Общий термин «оптимальная линейка Голомба» используется для обозначения второго типа оптимальности.

Практическое применение

Пример конференц-зала с пропорциями линейки Голомба [0, 2, 7, 8, 11], что позволяет настроить его на 10 различных размеров.

Теория информации

Линейки Голомба используются в теории информации , связанной с кодами, исправляющими ошибки .

Выбор радиочастоты

Линейки Голомба используются при выборе радиочастот для уменьшения влияния интермодуляционных помех как с эфирными, так и с радиочастотами. и инопланетяне приложения.

Размещение радиоантенны

Линейки Голомба используются при проектировании фазированных решеток радиоантенн. В радиоастрономии одномерные решетки синтеза могут иметь антенны в конфигурации линейки Голомба, чтобы получить минимальную избыточность выборки компонентов Фурье.

Трансформаторы тока

с несколькими коэффициентами В трансформаторах тока для размещения точек отводов трансформатора используются линейки Голомба.

Методы строительства

Ряд методов построения дает асимптотически оптимальные линейки Голомба.

Строительство

Следующая конструкция, предложенная Паулем Эрдешем и Палом Тураном , дает линейку Голомба для каждого нечетного простого числа p.

$2pk+(k^{2}\,{\bmod {\,}}p),k\in [0,p-1]$

оптимальные

В следующей таблице приведены все известные оптимальные линейки Голомба, за исключением тех, у которых отметки расположены в обратном порядке. Первые четыре идеальны .

Заказ	Длина	Знаки	Доказано [*]	Доказательство обнаружил
1	0	0	1952	Уоллес Бэбкок
2	1	0 1	1952	Уоллес Бэбкок
3	3	0 1 3	1952	Уоллес Бэбкок
4	6	0 1 4 6	1952	Уоллес Бэбкок
5	11	0 1 4 9 11 0 2 7 8 11	в. 1967 год	Джон П. Робинсон и Артур Дж. Бернштейн
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	в. 1967 год	Джон П. Робинсон и Артур Дж. Бернштейн
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	в. 1967 год	Джон П. Робинсон и Артур Дж. Бернштейн
8	34	0 1 4 9 15 22 32 34	1972	Уильям Миксон
9	44	0 1 5 12 25 27 35 41 44	1972	Уильям Миксон
10	55	0 1 6 10 23 26 34 41 53 55	1972	Уильям Миксон
11	72	0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72	1972	Уильям Миксон
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979	Джон П. Робинсон
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981	Джон П. Робинсон
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985	Джеймс Б. Ширер
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985	Джеймс Б. Ширер
16	177	0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177	1986	Джеймс Б. Ширер
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993	В. Олин Сиберт
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993	В. Олин Сиберт
19	246	0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246	1994	Апостолос Доллас, Уильям Т. Рэнкин и Дэвид Маккракен
20	283	0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283	1997?	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
21	333	0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333	8 мая 1998 г.	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
22	356	0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356	1999	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
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	1999	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
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	13 октября 2004 г.	distributed.net
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	25 октября 2008 г.	distributed.net
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	24 февраля 2009 г.	distributed.net
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	19 февраля 2014 г.	distributed.net
28	585	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 585	23 ноября 2022 г.	distributed.net

^{^ *} Оптимальный правитель был бы известен еще до этой даты; эта дата представляет собой ту дату, когда было обнаружено, что она оптимальна (поскольку все остальные линейки оказались не меньшими). Например, линейка, оказавшаяся оптимальной для порядка 26, была записана 10 октября 2007 г., но ее оптимальность не была известна до тех пор, пока 24 февраля 2009 г. не были исчерпаны все остальные возможности.

См. также

• Массив Костаса
• Волонтерские вычисления
  • БОИНК
  • distributed.net
• Идеальный правитель
• Последовательность Сидона
• Редкий правитель

Ссылки

• Гарднер, Мартин (март 1972 г.). «Математические игры». Научный американец . 226 (3): 108–112. Бибкод : 1972SciAm.226c.108G . doi : 10.1038/scientificamerican0372-108 .

Внешние ссылки

• Страницы линейки Голомба Джеймса Б. Ширера
• Distributed.net: Проект OGR
• В поисках оптимальных 20, 21 и 22 линеек Марка Голомба
• Голомбовые линейки длиной до 200