ゴロム定規

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

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

ソロモン・ゴロムが名前の由来だが、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]。distributed.netは次数28の最短ゴロム定規も探索しようと計画している。ただし、新たにアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している[11]。2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた[12]が、2014年2月に確定したと発表した[13]

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

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

他の言語で
Deutsch: Golomb-Lineal
English: Golomb ruler
español: Regla de Golomb
français: Règle de Golomb
Nederlands: Golomb-liniaal
српски / srpski: Голомбов лењир
svenska: Golomblinjal
Tiếng Việt: Thước Golomb