ゴロム定規
ゴロム定規（ゴロムじょうぎ、英: 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]。
2009年から開始した次数27の最短ゴロム定規を探すプロジェクトは、予想では7年で発見できるとしていた[11]が、2014年2月に確定したと発表した[12]。
distributed.netは次数28の最短ゴロム定規を探索している。また、新たなアルゴリズムの改善策が見つかったため、以前ほど時間はかからないと予測している[13]。 2022年11月22日に、約8年半かかって探査が終了したと発表した[14]。次数28の最短ゴロム定規の探査終了時点では、想定している規模や期間から、現時点では次数29の最短ゴロム定規を探索する予定はないが、今後も継続して検討するとしている。
最短ゴロム定規は、フェーズドアレイレーダーの設計、電波望遠鏡の配置などに応用されている。
今のところ、n-次の最短ゴロム定規を求める問題の計算量は不明だが、NP困難問題だと考えられている[3]。
既知の最短ゴロム定規
[編集]下表は、全ての既知の最短ゴロム定規である。マークの配置が表にあるものと逆のもの（対称型）は省く。
| 次数 | 長さ | マークの位置 |
|---|---|---|
| 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 |
脚注
[編集]- ^ S. Sidon, "Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen", Mathematische Annalen 106 (1932), pp. 536–539
- ^ Wallace C. Babcock. "Intermodulation Interference in Radio Systems/Frequency of Occurrence and Control by Channel Selection", Bell System Technical Journal 31 (1953), pp. 63–73.
- ^ a b “Modular and Regular Golomb Rulers”. 2009年6月23日閲覧。
- ^ “stats.distributed.net - OGR-24 Overall Project Stats”. 2008年3月27日閲覧。
- ^ “stats.distributed.net - OGR-25 Overall Project Stats”. 2008年9月22日閲覧。
- ^ bovin's .plan archive
- ^ Distributed.net Projects
- ^ “stats.distributed.net - OGR-27 Overall Project Stats”. 2014年2月28日閲覧。
- ^ “distributed.net - .plan archives”. 2008年3月27日閲覧。
- ^ “distributed.net - .plan archives 2”. 2008年10月26日閲覧。
- ^ bovine's plan, 24-Feb-2009 17:26
- ^ “distributed.net staff blogs - The OGR-27 project has been completed.”. 2014年2月28日閲覧。
- ^ “distributed.net - .plan archives 3”. 2009年6月23日閲覧。
- ^ “distributed.net staff blogs - Completion of OGR-28 project”. 2022年11月23日閲覧。
参考文献
[編集]- Gardner, Martin (March 1972). “Mathematical games”. Scientific American: 108–112.
外部リンク
[編集]- 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)
- Weisstein, Eric W. "Golomb Ruler". mathworld.wolfram.com (英語).