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

Набор отметок на линейке таким образом, что никакие две пары отметок не находятся на одинаковом расстоянии друг от друга.

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

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

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

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

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

Distributed.net завершил распределенный массовый параллельный поиск оптимальных линеек Голомба порядка 24–28, каждый раз подтверждая предполагаемого кандидата на линейку. ^{[4] [5] [6] [7] [8]}

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

Определения

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

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

${\displaystyle {\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.}$^[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 f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$ ${\displaystyle f(1)=0}$ ${\displaystyle f(m)=n}$

${\displaystyle {\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}

Порядок такой линейки Голомба равен , а ее длина равна . Каноническая форма имеет ${\displaystyle m}$ ${\displaystyle n}$

${\displaystyle f(2)<f(m)-f(m-1)}$если . ${\displaystyle m>2}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Многодиапазонные трансформаторы тока используют линейки Голомба для размещения точек ответвления трансформатора. ^{[ необходима ссылка ]}

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Сидон, С. (1932). «Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen». Математические Аннален . 106 : 536–539. дои : 10.1007/BF01455900. S2CID  120087718.
2. Бекир, Ахмад; Голомб, Соломон В. (2007). «Нет никаких дополнительных контрпримеров к теореме С. Пикара». IEEE Transactions on Information Theory . 53 (8): 2864–2867. doi :10.1109/TIT.2007.899468. MR  2400501. S2CID  16689687..
3. «Модульные и регулярные линейки Голомба».
4. "distributed.net - объявление о завершении OGR-24". 2004-11-01.
5. "distributed.net - объявление о завершении OGR-25". 2008-10-25.
6. "distributed.net - объявление о завершении OGR-26". 2009-02-24.
7. "distributed.net - объявление о завершении OGR-27". 2014-02-25.
8. "Завершение проекта OGR-28" . Получено 23 ноября 2022 г. .
9. Meyer C, Papakonstantinou PA (февраль 2009). «О сложности построения линеек Голомба». Discrete Applied Mathematics . 157 (4): 738–748. doi : 10.1016/j.dam.2008.07.006 .
10. Димитроманолакис, Апостолос. "Анализ линейки Голомба и задач набора Сидона, а также определение больших, почти оптимальных линеек Голомба" (PDF) . Получено 20 декабря 2009 г.
11. Drakakis, Konstantinos (2009). «Обзор доступных методов построения линеек Голомба». Успехи в области математики коммуникаций . 3 (3): 235–250. doi :10.3934/amc.2009.3.235.
12. Erdős, Paul ; Turán, Pál (1941). «О проблеме Сидона в аддитивной теории чисел и некоторых связанных с ней проблемах». Журнал Лондонского математического общества . 16 (4): 212–215. doi :10.1112/jlms/s1-16.4.212.
13. Робинсон Дж., Бернстайн А. (январь 1967 г.). «Класс двоичных рекуррентных кодов с ограниченным распространением ошибок». Труды IEEE по теории информации . 13 (1): 106–113. doi :10.1109/TIT.1967.1053951.
14. Babcock, Wallace C. (1953). "Интермодуляционные помехи в радиосистемах" (отрывок) . Bell System Technical Journal . 32 : 63–73. doi :10.1002/j.1538-7305.1953.tb01422.x. Архивировано (PDF) из оригинала 2011-07-07 . Получено 2011-03-14 .
15. Фанг, Р. Дж. Ф.; Сандрин, ВА (1977). «Назначение несущей частоты для нелинейных ретрансляторов». Технический обзор Comsat (аннотация). 7 : 227. Бибкод :1977COMTR...7..227F.
16. Томпсон, А. Ричард; Моран, Джеймс М.; Свенсон, Джордж У. (2004). Интерферометрия и синтез в радиоастрономии (второе издание). Wiley-VCH. стр. 142. ISBN 978-0471254928.
17. Арсак, Дж. (1955). «Передача пространственных частот в коротковолновых приемных системах». Optica Acta (на французском языке). 2 (112): 112–118. Бибкод : 1955AcOpt...2..112A. дои : 10.1080/713821025.
18. Линейки, массивы и изящество Эд Пегг-младший. 15 ноября 2004 г. Математические игры.
19. Ширер, Джеймс Б. (19 февраля 1998 г.). "Таблица длин самых коротких известных линеек Голомба". IBM . Архивировано из оригинала 25 июня 2017 г.
20. "В поисках оптимальных 20 и 21 линеек Марка Голомба (архив)". Марк Гарри, Дэвид Вандершель и др. 26 ноября 1998 г. Архивировано из оригинала 1998-12-06.

• Гарднер, Мартин (март 1972 г.). «Математические игры». Scientific American . 226 (3): 108–112. Bibcode : 1972SciAm.226c.108G. doi : 10.1038/scientificamerican0372-108.

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

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