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

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

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

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

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

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

${\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}}$ или просто ${\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. (последовательность A008404 в OEIS ):

Заказ	Число
1	1
2	2
3	4
4	12
5	40
6	116
7	200
8	444
9	760
10	2160
11	4368
12	7852
13	12828
14	17252
15	19612
16	21104
17	18276
18	15096
19	10240
20	6464
21	3536
22	2052
23	872
24	200
25	88
26	56
27	204
28	712
29	164

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

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

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

Н = 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}

Н = 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}

Н = 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, заказать 500 и заказать 1030 доступны. Хотя эти списки и базы данных этих массивов Костаса, вероятно, почти полны, могут существовать другие массивы Костаса с порядками выше 29, которых нет в этих списках.

Конструкции

Уэлч

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

Пример:

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

Тейлора, Лемпеля

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

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

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

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

Варианты

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

См. также

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

Ссылки

• Баркер, Л.; Дракакис, К.; Рикард, С. (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), "The $T_{4}$ и $G_{4}$ конструкции для массивов Костаса», IEEE Transactions on Information Theory , 38 (4): 1404–1406, doi : 10.1109/18.144726 , MR   1168761
• Голомб, 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]