frame|次数4、長さ6のゴロム定規。最短で完全である。 ゴロム定規（ゴロムじょうぎ、）とは、想像上の定規の上で一連の整数位置にマークを配置し、任意のマークの対の距離がどれをとっても等しくならないものをいう。ゴロム尺とも。マーク数を「次数 (order)」、2つのマーク間の距離のうち最大の距離を「長さ (length)」という。ゴロム定規の平行移動と鏡映は自明と考えられる。そのため慣例として、最小のマークを0とし、その次のマークは2つの可能な値のうち小さいほうを取る。
ソロモン・ゴロムが名前の由来だが、S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539とBabcockWallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.も独自に発見している。
ゴロム定規は、その長さまでの全ての距離を測定できる必要はないが、全ての距離を測定できるゴロム定規を「完全ゴロム定規 (PerfectGolomb Ruler)」 という。5個以上のマークのあるゴロム定規では、完全ゴロム定規が存在しないことが証明されている。また、同一次数（マーク数）で最短のゴロム定規を「最短ゴロム定規 (OoptimalGolomb Ruler) 」という。ゴロム定規を作るのは簡単だが、特定次数の最短ゴロム定規を見つけるのは困難である。
特定次数における最短ゴロム定規の発見を分散コンピューティングを利用したプロジェクトとしてdistributed.netで進められている。distributed.netでは、次数24、次数25、次数26bovin's .plan archiveDistributed.net Projects、次数27の最短ゴロム定規を求め、最短の候補を検証中である。
2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていたbovine's plan, 24-Feb-2009 17:26が、2014年2月に確定したと発表した。
distributed.netは次数28の最短ゴロム定規を探索している。また、新たなアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している。 2022年11月22日に、約8年半かかって探査が終了したと発表した。次数28の最短ゴロム定規の探査終了時点では、想定している規模や期間から、現時点では次数29の最短ゴロム定規を探索する予定はないが、今後も継続して検討するとしている。
最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。
今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている。
既知の最短ゴロム定規 下表は、全ての既知の最短ゴロム定規である。マークの配置が表にあるものと逆のもの（対称型）は省く。
次数 長さ マークの位置 1 0 0 2 1 0 1 3 3 0 1 3 4 6 0 1 4 6 5 11 0 1 4 9 11 0 2 7 8 11 6 17 0 1 4 10 12 17 0 1 4 10 15 17 0 1 8 11 13 17 0 1 8 12 14 17 7 25 0 1 4 10 18 23 25 0 1 7 11 20 23 25 0 1 11 16 19 23 25 0 2 3 10 16 21 25 0 2 7 13 21 22 25 8 34 0 1 4 9 15 22 32 34 9 44 0 1 5 12 25 27 35 41 44 10 55 0 1 6 10 23 26 34 41 53 55 11 72 0 1 4 13 28 33 47 54 64 70 72 0 1 9 19 24 31 52 56 58 69 72 12 85 0 2 6 24 29 40 43 55 68 75 76 85 13 106 0 2 5 25 37 43 59 70 85 89 98 99 106 14 127 0 4 6 20 35 52 59 77 78 86 89 99 122 127 15 151 0 4 20 30 57 59 62 76 100 111 123 136 144 145 151 16 177 0 1 4 11 26 32 56 68 76 115 117 134 150 163 168 177 17 199 0 5 7 17 52 56 67 80 81 100 122 138 159 165 168 191 199 18 216 0 2 10 22 53 56 82 83 89 98 130 148 153 167 188 192 205 216 19 246 0 1 6 25 32 72 100 108 120 130 153 169 187 190 204 231 233 242 246 20 283 0 1 8 11 68 77 94 116 121 156 158 179 194 208 212 228 240 253 259 283 21 333 0 2 24 56 77 82 83 95 129 144 179 186 195 255 265 285 293 296 310 329 333 22 356 0 1 9 14 43 70 106 122 124 128 159 179 204 223 253 263 270 291 330 341 353 356 23 372 0 3 7 17 61 66 91 99 114 159 171 199 200 226 235 246 277 316 329 348 350 366 372 24 425 0 9 33 37 38 97 122 129 140 142 152 191 205 208 252 278 286 326 332 353 368 384 403 425 25 480 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480 26 492 0 1 33 83 104 110 124 163 185 200 203 249 251 258 314 318 343 356 386 430 440 456 464 475 487 492 27 553 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 28 585 0 3 15 41 66 95 97 106 142 152 220 221 225 242 295 330 338 354 382 388 402 415 486 504 523 546 553 585
脚注
参考文献
外部リンク James B. Shearer's Golomb ruler pages distributed.net: Project OGR In Search Of The Optimal 20, 21 & 22 Mark Golomb Rulers "Rulers, Arrays, and Gracefulness" by Ed Pegg Jr. Golomb rulers up to length of over 200 (via Internet Archive)