ゴロム定規

ゴロム定規（ゴロムじょうぎ）とは、架空の定規上の整数位置に印（マーク）を配置する数学的な構造です。この構造のユニークな点は、任意の二つのマーク間の距離が、他のどの二つのマーク間の距離とも異なるという性質を持つことです。ゴロム尺（ゴロムしゃく）とも称されます。マークの総数は「次数（order）」、最も離れたマーク間の距離は「長さ（length）」と呼ばれ、通常、最小マークを0とする慣例があります。この概念は数学者のソロモン・ゴロムらに由来します。

ゴロム定規にはいくつかの種類があります。「完全ゴロム定規（Perfect Golomb Ruler）」はその長さまでの全ての正の整数距離を測定できますが、マーク数が5個以上では存在しません。一方、「最短ゴロム定規（Optimal Golomb Ruler）」は、特定の次数に対して可能な限り短い長さを持つものを指します。ゴロム定規自体を作成するのは容易ですが、ある次数における最短の配置を見つけることは極めて難しい数学的課題です。

最短ゴロム定規を見つけ出す問題は、計算機科学でNP困難問題とされる可能性が高く、解決には莫大な計算能力が必要です。このため、インターネットを通じて世界中のボランティアのコンピュータを連携させる分散コンピューティングプロジェクト「distributed.net」が設立され、高次の最短ゴロム定規の探査が進められています。

distributed.netは、これまでに次数24、25、26、27の最短ゴロム定規を確定させました。特に次数27の探索は2009年に開始され、約7年で完了すると見込まれていましたが、実際にはそれよりも早く、2014年2月には結果が確定しました。この成果に続き、さらに難易度の高い次数28の最短ゴロム定規の探索に着手しました。新たな探索アルゴリズムの改良にもかかわらず約8年半を要し、2022年11月22日に探査完了が正式に発表されました。現時点では、次数28の探索で要した計算資源や期間を踏まえ、直ちに次数29の最短ゴロム定規の探索を開始する予定はないとされていますが、将来的な技術進歩などを考慮し、継続的な検討は行われる方針です。

最短ゴロム定規の特性は、実世界の技術、特に高性能なレーダーであるフェーズドアレイレーダーの設計や、宇宙の観測に用いられる電波望遠鏡のアンテナ配置などに応用されています。これらの分野では、マーク間の距離が一意であるという特性が、信号の効率的な処理や干渉抑制に役立てられています。

既知の最短ゴロム定規の具体的なマーク配置パターンは多くの場合一意ですが、高次のものほど発見が困難になります。特定のn次最短ゴロム定規を求める計算量の正確な評価は未解明ながら、NP困難という見方が有力であり、今後の研究や技術進歩が新たな発見に繋がることが期待されます。

もう一度検索