ゴロム定規

ゴロム定規（ゴロムじょうぎ、英: Golomb ruler）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。

次数4、長さ6のゴロム定規。最短で完全である。

ソロモン・ゴロムが名前の由来だが、Sidon[1]とBabcock[2]も独自に発見している。

ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全 (perfect)」ゴロム定規 (PGR) という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている[3]。また、同一次数（マーク数）で最短のゴロム定規を「最短 (optimal)」ゴロム定規 (OGR) という。ゴロム定規を作るのは簡単だが、特定次数のゴロム定規を見つけるのは困難である。

特定次数における最短ゴロム定規の発見を分散コンピューティングを利用したプロジェクトとしてdistributed.netで進められている。distributed.netでは、次数24[4]、次数25[5]、次数26[6][7]、次数27[8]の最短ゴロム定規を求め、最短の候補を検証中である[9][10]。

2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた[11]が、2014年2月に確定したと発表した[12]。

distributed.netは次数28の最短ゴロム定規を探索している。また、新たなアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している[13]。 2022年11月22日に、約8年半かかって探査が終了したと発表した[14]。次数28の最短ゴロム定規の探査終了時点では、想定している規模や期間から、現時点では次数29の最短ゴロム定規を探索する予定はないが、今後も継続して検討するとしている。

最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。

今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている[3]。