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

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

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

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

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

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

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

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

Определения

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

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

{ 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}$ . Такой формы можно достичь путем перевода и размышления.

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

An инъективный функция ${ Displaystyle е: влево {1,2, ..., м вправо } в влево {0,1, ..., п вправо }}$ с участием ${ displaystyle f (1) = 0}$ и ${ Displaystyle f (м) = п}$ является правителем Голомба тогда и только тогда, когда

{ displaystyle { text {для всех}} i, j, k, l in left {1,2, ..., m right } { text {такой, что}} 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

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

{ Displaystyle е (2) <е (м) -f (м-1)}

если

{ displaystyle m> 2}

.

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

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

Это может быть оптимально плотный, демонстрируя максимальную м для конкретной стоимости п,
Это может быть оптимально короткий, выставляя минимальные п для конкретной стоимости м.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{ displaystyle 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 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 95 129 144 179 186 195 255 265 285 293 296 310 329 333	8 мая 1998^[20]	Марк Гарри, Дэвид Вандершель и др. (веб-проект)
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^[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 403 425	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 242 295 330 338 354 382 388 402 415 486 504 523 546 553	19 февраля 2014 г.^[8]	распределенный.net

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

Смотрите также

использованная литература

^ Сидон, С. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen. 106: 536–539. Дои:10.1007 / BF01455900.CS1 maint: ref = harv (ссылка на сайт)
^ Бэбкок, Уоллес С. (1953). «Интермодуляционные помехи в радиосистемах / частота возникновения и управление выбором канала». Технический журнал Bell System. 31: 63–73.CS1 maint: ref = harv (ссылка на сайт)
^ Бекир, Ахмад; Голомб, Соломон В. (2007). «Других контрпримеров к теореме С. Пикара нет». IEEE Transactions по теории информации. 53 (8): 2864–2867. Дои:10.1109 / TIT.2007.899468. Г-Н 2400501..
^ ^а ^б «Модульные и регулярные линейки Голомба».
^ ^а ^б "Distribution.net - Объявление о завершении строительства ОГР-24". Получено 2014-02-25.
^ ^а ^б "Distributed.net - Объявление о завершении строительства ОГР-25". Получено 2014-02-25.
^ ^а ^б "Distributed.net - Объявление о завершении строительства ОГР-26". Получено 2014-02-25.
^ ^а ^б "Distributed.net - Объявление о завершении строительства ОГР-27". Получено 2014-02-25.
^ Мейер С., Папаконстантину П.А. (февраль 2009 г.). «О сложности построения Правителей Голомба». Дискретная прикладная математика. 157 (4): 738–748. Дои:10.1016 / j.dam.2008.07.006.
^ Димитроманолакис, Апостолос. "Анализ линейки Голомба и задачи о множестве Сидона и определение больших, почти оптимальных линейок Голомба" (PDF). Получено 2009-12-20. Цитировать журнал требует | журнал = (Помогите)
^ ^а ^б Дракакис, Константинос (2009). «Обзор доступных методов построения линейки Голомба». Успехи в математике коммуникации. 3 (3): 235–250. Дои:10.3934 / amc.2009.3.235.
^ ^а ^б Эрдеш, Пол; Туран, Пал (1941). «О проблеме Сидона в аддитивной теории чисел и некоторых смежных проблемах». Журнал Лондонского математического общества. 16 (4): 212–215. Дои:10.1112 / jlms / s1-16.4.212.
^ Робинсон Дж, Бернштейн А (январь 1967). «Класс двоичных рекуррентных кодов с ограниченным распространением ошибок». IEEE Transactions по теории информации. 13 (1): 106–113. Дои:10.1109 / TIT.1967.1053951.
^ «Интермодуляционные помехи в радиосистемах» (отрывок). Получено 2011-03-14.
^ Fang, R. J. F .; Сандрин, В. А. (1977). «Распределение несущей частоты для нелинейных повторителей». Технический обзор Comsat (Абстрактные). 7: 227. Bibcode:1977COMTR ... 7..227F.
^ Томпсон, А. Ричард; Моран, Джеймс М .; Свенсон, Джордж У. (2004). Интерферометрия и синтез в радиоастрономии (Второе изд.). Wiley-VCH. п.142. ISBN 978-0471254928.
^ Арсак, Дж. (1955). "Передачи пространственных частот в системах приемников, любезно предоставленных" [Передачи пространственных частот в коротковолновых приемных системах]. Optica Acta (На французском). 2 (112).
^ ^а ^б ^c ^d http://mathpuzzle.com/MAA/30-Rulers%20and%20Arrays/mathgames_11_15_04.html
^ ^а ^б ^c ^d ^е ^ж ^г ^час ^я ^j ^k ^л ^м ^п ^о ^п ^q ^р "таблица длин самых коротких из известных линейок". IBM. Получено 2013-11-28.
^ "В поисках оптимальных правителей Голомба 20 и 21 Марка (из архива)". Марк Гарри, Дэвид Вандершель и др. Архивировано из оригинал на 1998-12-06.

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

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

[1] Сидон, С. (1932). "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen". Mathematische Annalen. 106: 536–539. Дои:10.1007 / BF01455900.CS1 maint: ref = harv (ссылка на сайт)

[2] Бэбкок, Уоллес С. (1953). «Интермодуляционные помехи в радиосистемах / частота возникновения и управление выбором канала». Технический журнал Bell System. 31: 63–73.CS1 maint: ref = harv (ссылка на сайт)

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

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

[distributed.net_OGR-24_completion_announcement-5] а ^б "Distribution.net - Объявление о завершении строительства ОГР-24". Получено 2014-02-25.

[distributed.net_OGR-25_completion_announcement-6] а ^б "Distributed.net - Объявление о завершении строительства ОГР-25". Получено 2014-02-25.

[distributed.net_OGR-26_completion_announcement-7] а ^б "Distributed.net - Объявление о завершении строительства ОГР-26". Получено 2014-02-25.

[distributed.net_OGR-27_completion_announcement-8] а ^б "Distributed.net - Объявление о завершении строительства ОГР-27". Получено 2014-02-25.

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

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

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

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

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

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

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

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

[17] Арсак, Дж. (1955). "Передачи пространственных частот в системах приемников, любезно предоставленных" [Передачи пространственных частот в коротковолновых приемных системах]. Optica Acta (На французском). 2 (112).

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

[shearer-19] а ^б ^c ^d ^е ^ж ^г ^час ^я ^j ^k ^л ^м ^п ^о ^п ^q ^р "таблица длин самых коротких из известных линейок". IBM. Получено 2013-11-28.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[*]

[18]

[19]

[20]