コスタス配列

数学において、コスタス配列は幾何学的にはn 個の点の集合とみなすことができ、各点はn × nの正方形のタイルの正方形の中心に位置し、各行または列には 1 点のみが含まれ、各点のペア間のn ( n  − 1)/2 個の変位ベクトルはすべて異なります。これにより、理想的な「画鋲」の自動曖昧性関数が得られ、配列はソナーやレーダーなどの用途に役立ちます。コスタス配列は、1 次元のゴロム定規構造の 2 次元版とみなすことができ、数学的に興味深いだけでなく、実験設計やフェーズドアレイレーダー工学にも同様の用途があります。

コスタス配列は、1965 年の技術レポートで初めてコスタス配列について書いたJohn P. Costasにちなんで名付けられました。それとは別に、 Edgar Gilbertも同年にコスタス配列について執筆し、現在では対数ウェルチ法として知られるコスタス配列の構築法を発表しました。^[1] コスタス配列の一般的な列挙はコンピューター サイエンスの未解決問題であり、多項式時間でこれを解くアルゴリズムを見つけることは未解決の研究課題です。

コスタス配列は、数値的にはn × nの配列として表すことができます。各要素は、点の場合は 1、点がない場合は 0 になります。バイナリ行列として解釈される場合、これらの数値配列は、各行と各列に 1 つの点のみが存在するという制約があるため、順列行列でもあるという特性を持ちます。したがって、任意のnに対するコスタス配列は、順序nの順列行列のサブセットです。

配列は通常、任意の行の列を指定する一連のインデックスとして記述されます。任意の列には 1 つのポイントしかないため、配列を 1 次元で表すことができます。たとえば、次数N  = 4 の有効な Costas 配列は次のとおりです。

${\displaystyle {\begin{配列}{|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{配列}}}$    あるいは単に     ${\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] （} OEISの配列A008404）。

以下に既知の配列をいくつか示します: 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} ,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 年にEdgar Gilbertによって最初に発見され、1982 年にLloyd R. Welchによって再発見されました。ウェルチ・コスタス配列は、素数pの原始根 gを取り、配列Aを の場合は、それ以外の場合は 0で定義することによって構築されます。結果は、サイズp  − 1 のコスタス配列です。 ${\displaystyle A_{i,j}=1}$${\displaystyle j\equiv g^{i}{\bmod {p}}}$

例：

3 は 5 を法とする原始要素です。

3 ¹ = 3 ≡ 3 (mod 5)

3 ² = 9 ≡ 4 (5 を法として)

3 ³ = 27 ≡ 2 (mod 5)

3 ⁴ = 81 ≡ 1 (mod 5)

したがって、[3 4 2 1]はコスタス順列です。より具体的には、これは指数ウェルチ配列です。配列の転置は対数ウェルチ配列です。

与えられたサイズに対して存在するウェルチ・コスタス配列の数は、トーティエント関数に依存します。

Lempel-Golomb 構成では、 αと β を有限体GF( q )の原始元として、同様に の場合は を、それ以外の場合は 0 を定義します。結果はサイズq  − 2のコスタス配列です。α  +  β = 1 の場合は、最初の行と列を削除して、サイズq − 3 の別のコスタス配列を形成できます 。このような原始元のペアは、q>2のすべての素数累乗に対して存在します。 ${\displaystyle A_{i,j}=1}$${\displaystyle \alpha^{i}+\beta^{j}=1}$

角に1または1のペアがある行/列または2行を加算または減算することによる新しいコスタス配列の生成は、生成方法に焦点を当てた論文^[7]と、ゴロムとテイラーの1984年の画期的な論文^{[8]で発表されました。}

ウェルチ、レンペル、ゴロムのジェネレータによって生成された既存のコスタス配列の行と列を削除することで新しいコスタス配列を生成するより洗練された方法が1992年に公開されました。^[9] これらのジェネレータがコスタス配列を生成する順序に上限はありません。

より複雑な行や列の追加や削除の方法を用いて52次までのコスタス配列を求める2つの方法が2004年^[10]と2007年に発表された。 ^[11]

六角格子上のコスタス配列はハニカム配列として知られている。このような配列は有限個しか存在せず、奇数個の要素が六角形の形状に配置されている必要があることが示されている。現在、このような配列は12個（対称性まで）知られており、これが総数であると推測されている。^[12]

• 順列
• 二面体群
• 組み合わせ設計

• Barker, L.; Drakakis, K.; Rickard, S. (2009)、「Costas 特性の検証の複雑さについて」(PDF)、Proceedings of the IEEE、97 (3): 586–593、doi :10.1109/JPROC.2008.2011947、S2CID 29776660、2012-04-25に オリジナル(PDF)からアーカイブ、 2011-10-10に取得。
• ビアード、ジェームズ (2006 年 3 月)、「200 次までのコスタス配列の生成」、2006 年第 40 回情報科学およびシステム年次会議、IEEE、doi :10.1109/ciss.2006.286635、S2CID  2241386。
• Beard, James K. (2008 年 3 月)、「有限体におけるコスタス配列生成多項式」、2008 年第 42 回情報科学およびシステム年次会議、IEEE、doi :10.1109/ciss.2008.4558709、S2CID  614347。
• Beard, James K. (2017)、Costas 配列と 1030 次までの列挙、IEEE Dataport、doi :10.21227/H21P42。
• Beard, J.; Russo, J.; Erickson, K.; Monteleone, M.; Wright, M. (2004)、「Combinatoric collaboration on Costas arrays and ratings」、IEEE Radar Conference、フィラデルフィア、ペンシルバニア(PDF)、pp. 260–265、doi :10.1109/NRC.2004.1316432、S2CID 7733481、2012-04-25に オリジナル(PDF)からアーカイブ、2011-10-10に取得。
• ビアード、ジェームズ、ルッソ、ジョン、エリクソン、キース、モンテレオーネ、マイケル、ライト、マイケル（2007 年 4 月）、「コスタス配列生成および検索方法論」、IEEE Transactions on Aerospace and Electronic Systems、43 (2): 522–538、doi :10.1109/taes.2007.4285351、S2CID  32271456。
• コスタス、JP (1965)、ソナーの設計と性能に関する中程度の制約、クラス 1 レポート R65EMH33、GE コーポレーション
• Costas, JP (1984)、「ほぼ理想的な距離ドップラー曖昧性特性を持つ検出波形のクラスの研究」(PDF)、Proceedings of the IEEE、72 (8): 996–1009、doi :10.1109/PROC.1984.12967、S2CID 2742217、2011-09-30に オリジナル(PDF)からアーカイブ、 2011-10-10に取得。
• Drakakis, Konstantinos; Rickard, Scott; Beard, James K.; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (2008 年 10 月)、「順序 27 のコスタス配列の列挙の結果」、IEEE Transactions on Information Theory、54 (10): 4684–4687、doi :10.1109/tit.2008.928979、hdl : 2262/59260。
• Drakakis, Konstantinos、Iorio, Francesco、Rickard, Scott (2011)、「順序 28 のコスタス配列の列挙とその結果」、Advances in Mathematics of Communications
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (2011 年 8 月)、「順序 29 の Costas 配列の列挙の結果」、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。
• ゴロム、ソロモン W. (1984)、「コスタス配列の代数的構成」、組み合わせ理論ジャーナル、シリーズ A、37 (1): 13–21、doi :10.1016/0097-3165(84)90015-3、MR  0749508。
• ゴロム、ソロモン W. (1992)、「コスタス配列のと構築」、 IEEE Transactions on Information Theory、38 (4): 1404–1406、doi :10.1109/18.144726、MR  1168761${\displaystyle T_{4}}$${\displaystyle G_{4}}$
• Golomb, SW ; Taylor, H. (1984)、「Costas 配列の構築と特性」(PDF)、Proceedings of the IEEE、72 (9): 1143–1163、doi :10.1109/PROC.1984.12994、S2CID 39718506、2011-09-30に オリジナル(PDF)からアーカイブ、 2011-10-10に取得。
• ガイ、リチャード K. (2004)、「セクション C18 および F9」、数論における未解決問題(第 3 版)、Springer Verlag、ISBN 0-387-20860-7。
• モレノ、オスカー (1999)、「1 つまたは複数のターゲットの位置を特定するための信号パターンに関する結果の調査」、ポット、アレクサンダー、クマール、P. ビジェイ、ヘレステス、トル、その他 (編)、差異セット、シーケンス、および相関特性、NATO 先進科学研究所シリーズ、第 542 巻、クルーワー、353 ページ、ISBN 0-7923-5958-5。
• Rickard, Scott (2004)、「周期性特性を用いたコスタス配列の探索」、IMA 信号処理数学国際会議。
• Warnke, Lutz; Correll, Bill; Swanson, Christopher (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]