Правитель голомба

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

Совершенные циклические линейки Голомба (также называемые разностными множествами) с заданным порядком.

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

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

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

Distributed.net выполнил распределенные массовые параллельные поиски оптимальных правителей Голомба порядка 24–27, каждый раз подтверждая предполагаемого кандидата в правители. ^[5]^[6]^[7]^[8] В феврале 2014 года distribution.net начал поиск оптимальных линейок Голомба ( OGR ) порядка 28.

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

Определения [ править ]

Наборы правителей Голомба [ править ]

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

{\ displaystyle {\ text {для всех}} i, j, k, l \ in \ left \ {1,2, ..., m \ right \} {\ text {такой, что}} i \ neq j { \ text {and}} k \ neq l, \ a_ {i} -a_ {j} = a_ {k} -a_ {l} \ iff i = k {\ text {and}} j = l.}

^[10]

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

Правители Голомба как функции [ править ]

Инъективна функция с и является Голомбами правителем , если и только если ${\ Displaystyle е: \ влево \ {1,2, ..., м \ вправо \} \ в \ влево \ {0,1, ..., п \ вправо \}}$ ${\ displaystyle 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.

^[11]^{: 236}

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

f(2)<f(m)-f(m-1)

если .

m>2

Оптимальность [ править ]

Линейка Голомба порядка m и длины n может быть оптимальной в любом из двух аспектов: ^[11]^{: 237}

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

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

Практическое применение [ править ]

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

Теория информации и исправление ошибок [ править ]

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

Выбор радиочастоты [ править ]

Линейки Голомба используются при выборе радиочастот, чтобы уменьшить влияние интермодуляционных помех как для наземных ^{[14], так} и для внеземных ^[15] приложений.

Размещение радиоантенны [ править ]

Линейки Голомба используются в конструкции фазированных решеток радиоантенн. Антенны в конфигурации [0,1,4,6] линейки Голомба часто можно увидеть на вышках AM или на сотовых станциях. В радиоастрономии решетки одномерного синтеза могут иметь антенны в конфигурации линейки Голомба, чтобы получить минимальную избыточность выборки компонента Фурье. ^[16]^[17]

Трансформаторы тока [ править ]

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

Способы строительства [ править ]

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

Строительство Эрдёша-Турана [ править ]

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

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

Известные оптимальные правители Голомба [ править ]

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

Приказ	Длина	Метки	Проверено ^[*]	Доказательство обнаружено
1	0	0	1952 ^[18]	Уоллес Бэбкок
2	1	0 1	1952 ^[18]	Уоллес Бэбкок
3	3	0 1 3	1952 ^[18]	Уоллес Бэбкок
4	6	0 1 4 6	1952 ^[18]	Уоллес Бэбкок
5	11	0 1 4 9 11 0 2 7 8 11	c. 1967 ^[19]	Джон П. Робинсон и Артур Дж. Бернштейн
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	c. 1967 ^[19]	Джон П. Робинсон и Артур Дж. Бернштейн
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	c. 1967 ^[19]	Джон П. Робинсон и Артур Дж. Бернштейн
8	34	0 1 4 9 15 22 32 34	1972 ^[19]	Уильям Миксон
9	44 год	0 1 5 12 25 27 35 41 44	1972 ^[19]	Уильям Миксон
10	55	0 1 6 10 23 26 34 41 53 55	1972 ^[19]	Уильям Миксон
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 ^[19]	Уильям Миксон
12	85	0 2 6 24 29 40 43 55 68 75 76 85	1979 ^[19]	Джон П. Робинсон
13	106	0 2 5 25 37 43 59 70 85 89 98 99 106	1981 ^[19]	Джон П. Робинсон
14	127	0 4 6 20 35 52 59 77 78 86 89 99 122 127	1985 ^[19]	Джеймс Б. Ширер
15	151	0 4 20 30 57 59 62 76 100 111 123 136 144 145 151	1985 ^[19]	Джеймс Б. Ширер
16	177	0 1 4 11 26 32 56 68 76 115 117 117 134 150 163 168 177	1986 ^[19]	Джеймс Б. Ширер
17	199	0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199	1993 ^[19]	В. Олин Сиберт
18	216	0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216	1993 ^[19]	В. Олин Сиберт
19	246	0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246	1994 ^[19]	Апостолос Доллас, Уильям Т. Ранкин и Дэвид Маккракен
20	283	0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283	1997? ^[19]	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
21 год	333	0 2 24 56 77 82 83 95129144 179 186 195 255 265 285 293 296310 329 333	8 мая 1998 ^[20]	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
22	356	0 1 9 14 43 70106122124128 159 179 204 223 253 263270 291 330 341 353 356	1999 ^[19]	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
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 ^[19]	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
24	425	0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403425	13 октября 2004 г. ^[5]	распределенный.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 г. ^[6]	распределенный.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 г. ^[7]	распределенный.net
27	553	0 3 15 41 66 95 97 106 142 152 220 221 225 242295 330 338 354 382 388 402415 486 504 523 546 553	19 февраля 2014 ^[8]	распределенный.net

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

См. Также [ править ]

Массив Костаса
Редкий правитель
Идеальный правитель
Сидоновская последовательность
распределенный.net
BOINC
Распределенных вычислений

Ссылки [ править ]

Перейти ↑ Sidon, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen . 106 : 536–539. DOI : 10.1007 / BF01455900 . S2CID 120087718 .
^ Бэбкок, Уоллес С. (1953). «Интермодуляционные помехи в радиосистемах / Частота появления и управление выбором канала». Технический журнал Bell System . 31 : 63–73. DOI : 10.1002 / j.1538-7305.1953.tb01422.x .
^ Бекир, Ахмад; Голомб, Соломон В. (2007). «Других контрпримеров к теореме С. Пикара нет». IEEE Transactions по теории информации . 53 (8): 2864–2867. DOI : 10.1109 / TIT.2007.899468 . Руководство по ремонту 2400501 . S2CID 16689687 . .
^ a b «Модульные и регулярные линейки Голомба» .
^ a b "distribution.net - Объявление о завершении ОГР-24" . Проверено 25 февраля 2014 .
^ a b "Распределенный.net - Объявление о завершении ОГР-25" . Проверено 25 февраля 2014 .
^ a b "distribution.net - Объявление о завершении проекта OGR-26" . Проверено 25 февраля 2014 .
^ a b "distribution.net - Объявление о завершении проекта OGR-27" . Проверено 25 февраля 2014 .
^ Meyer C, Papakonstantinou PA (февраль 2009). «О сложности построения Правителей Голомба». Дискретная прикладная математика . 157 (4): 738–748. DOI : 10.1016 / j.dam.2008.07.006 .
^ Димитроманолакис, Апостолос. "Анализ линейки Голомба и задачи о множестве Сидона и определение больших, почти оптимальных линейок Голомба" (PDF) . Проверено 20 декабря 2009 . Cite journal requires |journal= (help)
^ a b Дракакис, Константинос (2009). «Обзор доступных методов построения линейки Голомба» . Успехи в математике коммуникаций . 3 (3): 235–250. DOI : 10,3934 / amc.2009.3.235 .
^ а б Эрдёш, Пол ; Туран, Пал (1941). «О проблеме Сидона в аддитивной теории чисел и некоторых смежных проблемах». Журнал Лондонского математического общества . 16 (4): 212–215. DOI : 10,1112 / jlms / s1-16.4.212 .
Перейти ↑ Robinson J, Bernstein A (январь 1967). «Класс двоичных рекуррентных кодов с ограниченным распространением ошибок». IEEE Transactions по теории информации . 13 (1): 106–113. DOI : 10.1109 / TIT.1967.1053951 .
^ «Интермодуляционные помехи в радиосистемах» (отрывок) . Проверено 14 марта 2011 .
^ Фанг, RJF; Сандрин, WA (1977). «Распределение несущей частоты для нелинейных повторителей». Технический обзор Comsat (аннотация). 7 : 227. Bibcode : 1977COMTR ... 7..227F .
^ Томпсон, А. Ричард; Моран, Джеймс М .; Свенсон, Джордж У. (2004). Интерферометрия и синтез в радиоастрономии (второе изд.). Wiley-VCH. п. 142 . ISBN 978-0471254928.
^ Arsac, J. (1955). "Передачи пространственных частот в системах приемников, любезно предоставленных" [Передачи пространственных частот в коротковолновых приемных системах]. Optica Acta (на французском языке). 2 (112). DOI : 10.1080 / 713821025 .
^ а б в г http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html
^ a b c d e f g h i j k l m n o p q r "Таблица длин самых коротких известных линеек" . IBM . Проверено 28 ноября 2013 .
^ «В поисках оптимальных 20 и 21 Марков Правителей Голомба (из архива)» . Марк Гарри, Дэвид Вандершель и др. Архивировано из оригинала на 1998-12-06.

Гарднер, Мартин (март 1972 г.). «Математические игры». Scientific American . 226 (3): 108–112. DOI : 10.1038 / Scientificamerican0372-108 .

Внешние ссылки [ править ]

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

[1] Перейти ↑ Sidon, S. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen . 106 : 536–539. DOI : 10.1007 / BF01455900 . S2CID 120087718 .

[2] Бэбкок, Уоллес С. (1953). «Интермодуляционные помехи в радиосистемах / Частота появления и управление выбором канала». Технический журнал Bell System . 31 : 63–73. DOI : 10.1002 / j.1538-7305.1953.tb01422.x .

[3] Бекир, Ахмад; Голомб, Соломон В. (2007). «Других контрпримеров к теореме С. Пикара нет». IEEE Transactions по теории информации . 53 (8): 2864–2867. DOI : 10.1109 / TIT.2007.899468 . Руководство по ремонту 2400501 . S2CID 16689687 . .

[mcgill.ca-4] «Модульные и регулярные линейки Голомба» .

[distributed.net_OGR-24_completion_announcement-5] "distribution.net - Объявление о завершении ОГР-24" . Проверено 25 февраля 2014 .

[distributed.net_OGR-25_completion_announcement-6] "Распределенный.net - Объявление о завершении ОГР-25" . Проверено 25 февраля 2014 .

[distributed.net_OGR-26_completion_announcement-7] "distribution.net - Объявление о завершении проекта OGR-26" . Проверено 25 февраля 2014 .

[distributed.net_OGR-27_completion_announcement-8] "distribution.net - Объявление о завершении проекта OGR-27" . Проверено 25 февраля 2014 .

[9] Meyer C, Papakonstantinou PA (февраль 2009). «О сложности построения Правителей Голомба». Дискретная прикладная математика . 157 (4): 738–748. DOI : 10.1016 / j.dam.2008.07.006 .

[10] Димитроманолакис, Апостолос. "Анализ линейки Голомба и задачи о множестве Сидона и определение больших, почти оптимальных линейок Голомба" (PDF) . Проверено 20 декабря 2009 . Cite journal requires |journal= (help)

[Drakakis-11] Дракакис, Константинос (2009). «Обзор доступных методов построения линейки Голомба» . Успехи в математике коммуникаций . 3 (3): 235–250. DOI : 10,3934 / amc.2009.3.235 .

[ErdősTurán1941-12] а б Эрдёш, Пол ; Туран, Пал (1941). «О проблеме Сидона в аддитивной теории чисел и некоторых смежных проблемах». Журнал Лондонского математического общества . 16 (4): 212–215. DOI : 10,1112 / jlms / s1-16.4.212 .

[titlestats.A_class_of_binary_recurrent_codes_with_limited_error_propagation-13] Перейти ↑ Robinson J, Bernstein A (январь 1967). «Класс двоичных рекуррентных кодов с ограниченным распространением ошибок». IEEE Transactions по теории информации . 13 (1): 106–113. DOI : 10.1109 / TIT.1967.1053951 .

[titlestats.Intermodulation_Interference_in_Radio_Systems-14] «Интермодуляционные помехи в радиосистемах» (отрывок) . Проверено 14 марта 2011 .

[titlestats.Carrier_frequency_assignment_for_nonlinear_repeaters-15] Фанг, RJF; Сандрин, WA (1977). «Распределение несущей частоты для нелинейных повторителей». Технический обзор Comsat (аннотация). 7 : 227. Bibcode : 1977COMTR ... 7..227F .

[16] Томпсон, А. Ричард; Моран, Джеймс М .; Свенсон, Джордж У. (2004). Интерферометрия и синтез в радиоастрономии (второе изд.). Wiley-VCH. п. 142 . ISBN 978-0471254928.

[17] Arsac, J. (1955). "Передачи пространственных частот в системах приемников, любезно предоставленных" [Передачи пространственных частот в коротковолновых приемных системах]. Optica Acta (на французском языке). 2 (112). DOI : 10.1080 / 713821025 .

[mathpuzzles-18] а б в г http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html

[shearer-19] ^ a b c d e f g h i j k l m n o p q r "Таблица длин самых коротких известных линеек" . IBM . Проверено 28 ноября 2013 .

[org2021-20] «В поисках оптимальных 20 и 21 Марков Правителей Голомба (из архива)» . Марк Гарри, Дэвид Вандершель и др. Архивировано из оригинала на 1998-12-06.

[1]