массив Костаса

В математике массив Костаса можно рассматривать геометрически как набор из 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}

N = 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} ,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} ,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} ,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} ,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} ,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} ,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, которые не входят в эти списки. В общем, в настоящее время наиболее известная верхняя граница числа массивов Костаса порядка имеет асимптотическую форму . ^[6]${\displaystyle C(n)}$${\displaystyle n}$${\displaystyle C(n)/n!\leq e^{-\Theta (n)}}$

Массив Уэлча–Костаса , или просто массив Уэлча, — это массив Костаса, сгенерированный с использованием следующего метода, впервые открытого Эдгаром Гилбертом в 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] — это перестановка Костаса. Точнее, это экспоненциальный массив Уэлча. Транспонирование массива — логарифмический массив Уэлча.

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

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

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

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

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

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

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

• Баркер, Л.; Дракакис, К.; Рикард, С. (2009), «О сложности проверки свойства Костаса» (PDF) , Труды IEEE , 97 (3): 586–593, doi :10.1109/JPROC.2008.2011947, S2CID  29776660, архивировано из оригинала (PDF) 25.04.2012 , извлечено 10.10.2011.
• Бирд, Джеймс (март 2006 г.), «Создание массивов Костаса порядка 200», 40-я ежегодная конференция по информационным наукам и системам 2006 г. , IEEE, doi :10.1109/ciss.2006.286635, S2CID  2241386.
• Бирд, Джеймс К. (март 2008 г.), "Полиномы-генераторы массивов Костаса в конечных полях", 42-я ежегодная конференция по информационным наукам и системам 2008 г. , IEEE, doi :10.1109/ciss.2008.4558709, S2CID  614347.
• Бирд, Джеймс К. (2017), Массивы Костаса и перечисление до порядка 1030, IEEE Dataport, doi : 10.21227/H21P42.
• Бирд, Дж.; Руссо, Дж.; Эриксон, К.; Монтелеоне, М.; Райт, М. (2004), «Комбинаторное сотрудничество в области решеток Костаса и радиолокационных приложений», Конференция IEEE по радарам, Филадельфия, Пенсильвания (PDF) , стр. 260–265, doi :10.1109/NRC.2004.1316432, S2CID  7733481, заархивировано из оригинала (PDF) 25.04.2012 , извлечено 10.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
• Костас, Дж. П. (1984), «Исследование класса сигналов обнаружения, имеющих почти идеальные свойства неоднозначности доплеровского диапазона» (PDF) , Труды IEEE , 72 (8): 996–1009, doi :10.1109/PROC.1984.12967, S2CID  2742217, заархивировано из оригинала (PDF) 2011-09-30 , извлечено 2011-10-10.
• Дракакис, Константинос; Рикард, Скотт; Бирд, Джеймс К.; Кабальеро, Родриго; Иорио, Франческо; О'Брайен, Гарет; Уолш, Джон (октябрь 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 по теории информации , 38 (4): 1404–1406, doi :10.1109/18.144726, MR  1168761${\displaystyle T_{4}}$${\displaystyle G_{4}}$
• Голомб, SW ; Тейлор, H. (1984), "Построение и свойства массивов Костаса" (PDF) , Труды IEEE , 72 (9): 1143–1163, doi :10.1109/PROC.1984.12994, S2CID  39718506, заархивировано из оригинала (PDF) 2011-09-30 , извлечено 2011-10-10.
• Гай, Ричард К. (2004), «Разделы C18 и F9», Нерешенные проблемы теории чисел (3-е изд.), Springer Verlag , ISBN 0-387-20860-7.
• Moreno, Oscar (1999), "Обзор результатов по образцам сигналов для определения местоположения одной или нескольких целей", в Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (ред.), Difference Sets, Sequences and Their Correlation Properties , NATO Advanced Science Institutes Series, т. 542, Kluwer, стр. 353, ISBN 0-7923-5958-5.
• Рикард, Скотт (2004), «Поиск массивов Костаса с использованием свойств периодичности», Международная конференция IMA по математике в обработке сигналов.
• Варнке, Лутц; Коррелл, Билл; Свонсон, Кристофер (2023), «Плотность массивов Костаса убывает экспоненциально», IEEE Transactions on Information Theory , 69 (1): 575–581, doi :10.1109/TIT.2022.3202507, MR  4544975.

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