Массив Костаса

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

В математике массив Костаса можно рассматривать геометрически как набор из n точек, каждая из которых находится в центре квадрата квадратной мозаики размера n × n , так что каждая строка или столбец содержит только одну точку, а все n ( n  - 1)/2 вектора смещения между каждой парой точек различны. В результате получается идеальная функция автоматической неоднозначности «чертежная кнопка» , что делает массивы полезными в таких приложениях, как гидролокаторы и радары . Массивы Костаса можно рассматривать как двумерные родственники конструкции одномерной линейки Голомба , и, помимо того, что они представляют математический интерес, они имеют аналогичные приложения в экспериментальном проектировании и радиолокационной технике с фазированной решеткой .

Массивы Костаса названы в честь Джона П. Костаса , который впервые написал о них в техническом отчете 1965 года. Независимо о них в том же году написал Эдгар Гилберт , опубликовав то, что сейчас известно как логарифмический метод Уэлча построения массивов Костаса. ^[1] Общее перечисление массивов Костаса является открытой проблемой в информатике, и поиск алгоритма, который может решить ее за полиномиальное время, является открытым исследовательским вопросом.

Числовое представление

Массив Костаса может быть представлен численно как массив чисел n × n , где каждая запись равна либо 1 для точки, либо 0 для отсутствия точки. При интерпретации как двоичные матрицы эти массивы чисел обладают тем свойством, что, поскольку каждая строка и столбец имеют ограничение на наличие только одной точки, они, следовательно, также являются матрицами перестановок . Таким образом, массивы Костаса для любого заданного n являются подмножеством матриц перестановок порядка n .

Массивы обычно описываются как серия индексов, определяющих столбец для любой строки. Поскольку дано, что любой столбец имеет только одну точку, можно представить массив одномерно. Например, ниже приведен действительный массив Костаса порядка N  = 4:

${\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}$    или просто     ${\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}$

В координатах стоят точки: (1,2), (2,1), (3,3), (4,4).

Поскольку координата x увеличивается линейно, мы можем сокращенно записать это как набор всех координат y . Тогда позиция в наборе будет координатой x . Обратите внимание: {2,1,3,4} будет описывать вышеупомянутый массив. Это определяет перестановку. Это упрощает передачу массивов для заданного порядка N.

Известные массивы

Количество массивов Костаса известно для порядков с 1 по 29 ^[2] (последовательность A008404 в OEIS ):

Вот некоторые известные массивы: N = 1 {1}

Н = 2 {1,2} {2,1}

N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2 ,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1, 3} {4,3,1,2}

N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1, 5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5, 4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5 ,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2 } {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5, 2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5 ,1,2} {4,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} { 5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6 ,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6 ,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5 ,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1 ,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5, 3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3, 6,1} {2,5,1,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3, 4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6, 4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3, 1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} { 3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} {3,4,1,6,2,5 } {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2 ,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1 ,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5 ,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2 ,1,5,6,3} {4,2,1,6,3,5} {4,2,3,5,1,6} {4,2,3,6,5,1} {4 ,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3, 2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5, 2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2, 4,3,6} {5,1,3,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2, 3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5, 2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} { 5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1 } {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} {6,1,4,3,5 ,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5 ,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4 ,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4 ,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6 ,5,2,3,1,4}

Доступен перечисление известных массивов Костаса порядка 200, ^[3], порядка 500 ^[4] и порядка 1030 ^[5] . Хотя эти списки и базы данных этих массивов Костаса, вероятно, почти полны, могут существовать другие массивы Костаса с порядками выше 29, которых нет в этих списках.

Конструкции

Уэлч

Массив Уэлча-Костаса , или просто массив Уэлча, представляет собой массив Костаса, созданный с использованием следующего метода, впервые обнаруженного Эдгаром Гилбертом в 1965 году и переоткрытого в 1982 году Ллойдом Р. Уэлчем . Массив Уэлча – Костаса создается путем взятия примитивного корня g простого числа p и определения массива A с помощью if , в противном случае 0. Результатом является массив Костаса размера p  - 1. ${\displaystyle A_{i,j}=1}$ ${\displaystyle j\equiv g^{i}{\bmod {p}}}$

Пример:

3 — примитивный элемент по модулю 5.

3 ¹ = 3 ≡ 3 (по модулю 5)

3 ² = 9 ≡ 4 (по модулю 5)

3 ³ = 27 ≡ 2 (по модулю 5)

3 ⁴ = 81 ≡ 1 (по модулю 5)

Следовательно, [3 4 2 1] является перестановкой Костаса. Точнее, это экспоненциальный массив Уэлча. Транспонирование массива представляет собой логарифмический массив Уэлча.

Количество массивов Уэлча – Костаса, существующих для данного размера, зависит от функции totient .

Лемпель-Голомб

Конструкция Лемпеля – Голомба принимает α и β как примитивные элементы конечного поля GF( q ) и аналогичным образом определяет if , в противном случае 0. Результатом является массив Костаса размера q  − 2. Если α  +  β  = 1, то первый строка и столбец могут быть удалены, чтобы сформировать другой массив Костаса размера q  - 3: такая пара примитивных элементов существует для каждой степени простого числа q>2 . ${\displaystyle A_{i,j}=1}$ ${\displaystyle \alpha ^{i}+\beta ^{j}=1}$

Расширения Тейлора, Лемпеля и Голомба

Генерация новых массивов Костаса путем добавления или вычитания одной или двух строк/столбцов с единицей или парой единиц в углу была опубликована в статье, посвященной методам генерации ^[6] , а также в знаковой статье Голомба и Тейлора 1984 года. ^[7]

Более сложные методы создания новых массивов Костаса путем удаления строк и столбцов существующих массивов Костаса, сгенерированных генераторами Уэлча, Лемпеля или Голомба, были опубликованы в 1992 году. ^[8] Не существует верхнего предела порядка, для которого эти генераторы будут создавать Массивы Костаса.

Другие методы

Два метода, позволяющие найти массивы Костаса до 52-го порядка с использованием более сложных методов добавления или удаления строк и столбцов, были опубликованы в 2004 ^[9] и 2007 годах ^{[10] .}

Варианты

Массивы Костаса на шестиугольной решетке известны как сотовые массивы . Показано, что существует лишь конечное число таких массивов, которые должны иметь нечетное число элементов, расположенных в форме шестиугольника. В настоящее время известно 12 таких массивов (с точностью до симметрии), что предположительно соответствует их общему числу. ^[11]

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

• перестановка
• Группа диэдра
• Комбинаторный дизайн

Примечания

1. Костас (1965); Гилберт (1965); Независимое открытие массивов Костаса, Аарон Стерлинг, 9 октября 2011 г.
2. Борода (2006); Дракакис и др. (2008); Дракакис, Иорио и Рикард (2011); Дракакис и др. (2011)
3. Борода (2006).
4. Борода (2008).
5. Борода (2017); Бирд, Джеймс К., Файлы для загрузки: Costas Arrays , получено 20 апреля 2020 г.
6. Голомб (1984).
7. Голомб и Тейлор (1984).
8. Голомб (1992).
9. Рикард (2004).
10. Бирд и др. (2007).
11. Блэкберн, Саймон Р.; Пануи, Анастасия; Патерсон, Маура Б.; Стинсон, Дуглас Р. (10 декабря 2010 г.). «Сотовые массивы». Электронный журнал комбинаторики . 17 : 172 р. дои : 10.37236/444 . ISSN  1077-8926.

Рекомендации

• Баркер, Л.; Дракакис, К.; Рикард, С. (2009), «О сложности проверки свойства Костаса» (PDF) , Proceedings of the IEEE , 97 (3): 586–593, doi : 10.1109/JPROC.2008.2011947, S2CID  29776660, в архиве. из оригинала (PDF) от 25 апреля 2012 г. , получено 10 октября 2011 г..
• Берд, Джеймс (март 2006 г.), «Генерация массивов Костаса порядка 200», 2006 г., 40-я ежегодная конференция по информационным наукам и системам , IEEE, doi : 10.1109/ciss.2006.286635, S2CID  2241386.
• Берд, Джеймс К. (март 2008 г.), «Полиномы генератора массива Костаса в конечных полях», 2008 г., 42-я ежегодная конференция по информационным наукам и системам , IEEE, doi : 10.1109/ciss.2008.4558709, S2CID  614347.
• Берд, Джеймс К. (2017), Массивы Костаса и перечисление до порядка 1030, Порт данных IEEE, doi : 10.21227/H21P42.
• Борода, Дж.; Руссо, Дж.; Эриксон, К.; Монтелеоне, М.; Райт, М. (2004), «Комбинаторное сотрудничество в области решеток Костаса и радиолокационных приложений», IEEE Radar Conference, Филадельфия, Пенсильвания (PDF) , стр. 260–265, doi : 10.1109/NRC.2004.1316432, S2CID  7733481, заархивировано из оригинал (PDF) от 25 апреля 2012 г. , получено 10 октября 2011 г..
• Борода, Джеймс; Руссо, Джон; Эриксон, Кейт; Монтелеоне, Майкл; Райт, Майкл (апрель 2007 г.), «Методология создания массивов Костаса и поиска», IEEE Transactions on Aerospace and Electronic Systems , 43 (2): 522–538, doi : 10.1109/taes.2007.4285351, S2CID  32271456.
• Костас, Дж.П. (1965), Средние ограничения на конструкцию и характеристики гидролокатора , Отчет класса 1 R65EMH33, GE Corporation
• Костас, Дж. П. (1984), «Исследование класса сигналов обнаружения, имеющих почти идеальные свойства доплеровской неоднозначности по дальности» (PDF) , Proceedings of the IEEE , 72 (8): 996–1009, doi : 10.1109/PROC.1984.12967 , S2CID  2742217, заархивировано из оригинала (PDF) 30 сентября 2011 г. , получено 10 октября 2011 г..
• Дракакис, Константинос; Рикард, Скотт; Борода, Джеймс К.; Кабальеро, Родриго; Иорио, Франческо; О'Брайен, Гарет; Уолш, Джон (октябрь 2008 г.), «Результаты перечисления массивов Костаса порядка 27», IEEE Transactions on Information Theory , 54 (10): 4684–4687, doi : 10.1109/tit.2008.928979, hdl : 2262/59260.
• Дракакис, Константинос; Иорио, Франческо; Рикард, Скотт (2011), «Перечисление массивов Костаса порядка 28 и его последствия», Достижения в математике коммуникаций
• Дракакис, Константинос; Иорио, Франческо; Рикард, Скотт; Уолш, Джон (август 2011 г.), «Результаты перечисления массивов Костаса порядка 29», Advances in Mathematics of Communications , 5 (3): 547–553, doi : 10.3934/amc.2011.5.547 , hdl : 2262/ 59260.
• Гилберт, EN (1965), «Латинские квадраты, не содержащие повторяющихся биграмм», SIAM Review , 7 (2): 189–198, doi : 10.1137/1007035, MR  0179095.
• Голомб, Соломон В. (1984), «Алгебраические конструкции для массивов Костаса», Журнал комбинаторной теории , серия A, 37 (1): 13–21, doi : 10.1016/0097-3165(84)90015-3, MR  0749508.
• Голомб, Соломон В. (1992), « Конструкции и для массивов Костаса», IEEE Transactions on Information Theory , 38 (4): 1404–1406, doi : 10.1109/18.144726, MR  1168761 ${\displaystyle T_{4}}$ ${\displaystyle G_{4}}$
• Голомб, SW ; Тейлор, Х. (1984), «Построение и свойства массивов Костаса» (PDF) , Proceedings of the IEEE , 72 (9): 1143–1163, doi : 10.1109/PROC.1984.12994, S2CID  39718506, заархивировано из оригинала ( PDF) от 30 сентября 2011 г. , получено 10 октября 2011 г..
• Гай, Ричард К. (2004), «Разделы C18 и F9», Нерешенные проблемы теории чисел (3-е изд.), Springer Verlag , ISBN 0-387-20860-7.
• Морено, Оскар (1999), «Обзор результатов по шаблонам сигналов для обнаружения одной или нескольких целей», Потт, Александр; Кумар, П. Виджай; Хеллесет, Тор; и другие. (ред.), Наборы различий, последовательности и их корреляционные свойства , Серия Институтов передовых научных исследований НАТО, том. 542, Клювер, с. 353, ISBN 0-7923-5958-5.
• Рикард, Скотт (2004), «Поиск массивов Костаса с использованием свойств периодичности», Международная конференция IMA по математике в обработке сигналов..

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

• MacTech 1999 Задача программиста: массивы Костаса
• Интернет-энциклопедия целочисленных последовательностей :
  • A008404: Количество массивов Костаса порядка n, считая вращения и перевороты как отдельные.
  • A001441: Количество неэквивалентных массивов Костаса порядка n в группе диэдра.
• «Массив Костаса», Математическая энциклопедия , EMS Press , 2001 [1994]