ゴロム定規

数学において、ゴロム定規とは、定規に沿った整数位置にある目盛りの集合で、目盛りの 2 組の距離が等しくならないものをいいます。定規の目盛りの数は定規の位数で、目盛り同士の最大距離は定規の長さです。ゴロム定規の平行移動と反転は自明であると考えられるため、最小の目盛りは通常 0 に置かれ、次の目盛りは 2 つの可能な値のうち小さい方に置かれます。ゴロム定規は、コスタス配列の 1 次元の特殊なケースと見なすことができます。

ゴロム定規はソロモン・W・ゴロムにちなんで名付けられ、シドン（1932）^[1]とバブコック（1953）によって独立に発見されました。ソフィー・ピカールも1939年にこれらの集合に関する初期の研究を発表し、同じ距離の集合を持つ2つのゴロム定規は必ず合同であるという主張を定理として述べました。これは6点定規の場合は誤りであることが判明しましたが、それ以外の場合は正しいものでした。^[2]

ゴロム定規は必ずしもその長さまでのすべての距離を測定できる必要はありませんが、測定できる場合は完全なゴロム定規と呼ばれます。5 つ以上の目盛りに対して完全なゴロム定規は存在しないことが証明されています。^[3]同じ次数のより短いゴロム定規が存在しない場合に、ゴロム定規は最適です。ゴロム定規を作成するのは簡単ですが、指定された次数に対して最適なゴロム定規 (または複数の定規) を証明することは計算上非常に困難です。

Distributed.netは、最適な24次から28次のゴロム定規の分散型大規模並列探索を完了し、そのたびに候補定規の候補を確認しました。 ^{[4] [5] [6] [7] [8]}

現在、任意の位数n ( nは単項で与えられる)の最適ゴロム定規 (OGR) を見つける複雑さは不明です。^{[説明が必要]}過去には、NP 困難問題であるという推測がありました。^[3]ゴロム定規の構築に関連する問題は NP 困難であることが証明されていますが、既知の NP 完全問題でゴロム定規を見つけるのと似た性質を持つものはないことも指摘されています。^[9]

ゴロム定規となる 整数の集合は、${\displaystyle A=\{a_{1},a_{2},...,a_{m}\}}$${\displaystyle a_{1}$

${\displaystyle {\text{すべての }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{i\neq j{\text{ かつ }}k\neq l であるような }}i\neq j{\text{ かつ }}k\neq l である、\ a_{i}-a_{j}=a_{k}-a_{l}\iff i=k{\text{ かつ }}j=l.}$^[10]

このようなゴロム定規の位数はで、長さは です。標準形は であり、 の場合、 です。このような形は、平行移動と反射によって実現できます。 ${\displaystyle m}$${\displaystyle a_{m}-a_{1}}$${\displaystyle a_{1}=0}$${\displaystyle m>2}$${\displaystyle a_{2}-a_{1}-a_{m}-a_{m-1}}$

およびを持つ単射関数 がゴロム定規であるのは、 ${\displaystyle f:\left\{1,2,...,m\right\}\to \left\{0,1,...,n\right\}}$${\displaystyle f(1)=0}$${\displaystyle f(m)=n}$

${\displaystyle {\text{for all }}i,j,k,l\in \left\{1,2,...,m\right\}{\text{such that }}i\neq j{\text{ and }}k\neq l,f(i)-f(j)=f(k)-f(l)\iff i=k{\text{ and }}j=l.}$^{[11] : 236}

このようなゴロム定規の位数はで、長さはである。標準形は ${\displaystyle m}$${\displaystyle n}$

${\displaystyle f(2)<f(m)-f(m-1)}$もし。${\displaystyle m>2}$

長さnのm次のゴロム定規は、次の2つの点のいずれかにおいて最適である可能性がある: ^{[11] : 237}

• 特定のn値に対してmが最大となる最適密度となる可能性がある。
• 特定のmの値に対してn が最小となるように、最適に短くなる場合があります。

最適ゴロム定規という一般的な用語は、2 番目のタイプの最適性を指すために使用されます。

ゴロム定規は誤り訂正符号に関連する情報理論の中で使用されている。^[13]

ゴロム定規は、地上^[14]と地球外^[15]の両方のアプリケーションでの相互変調干渉の影響を低減するために無線周波数の選択に使用されます。

ゴロム定規は、電波アンテナのフェーズドアレイの設計に使用されます。電波天文学では、1次元合成アレイでは、フーリエ成分サンプリングの冗長性を最小限に抑えるために、アンテナをゴロム定規構成にすることができます。^{[16] [17]}

多比率変流器では、ゴロム定規を使用して変圧器のタップポイントを配置します。^{[引用が必要]}

いくつかの構築方法により、漸近的に最適なゴロム定規が生成されます。

Paul ErdősとPál Turánによる次の構築では、奇数の素数 p ごとにゴロム定規が生成されます。^[12]

${\displaystyle 2pk+(k^{2}\,{\bmod {\,}}p),k\in [0,p-1]}$

次の表には、逆の順序でマークされているものを除いて、既知の最適なゴロム定規がすべて含まれています。最初の 4 つは完璧です。

^ * 最適な定規はこの日付より前に知られていたはずです。この日付は、それが最適であると発見された日付を表しています (他のすべての定規がそれより小さくないことが証明されたため)。たとえば、順序 26 に最適であることが判明した定規は 2007 年 10 月 10 日に記録されましたが、他のすべての可能性が尽きた 2009 年 2 月 24 日まで、それが最適であるとはわかりませんでした。

• コスタス配列
• ボランティアコンピューティング
  • ボインク
  • 分散ネット
• 完璧な支配者
• シドン配列
• まばらな定規

• ガードナー、マーティン（1972年3月）。 「数学ゲーム」。サイエンティフィック・アメリカン。226 （3）：108-112。Bibcode ：1972SciAm.226c.108G。doi ： 10.1038/scientificamerican0372-108。

• ジェームズ・B・シアラーのゴロム定規のページ
• 分散型ネット: プロジェクト OGR
• 最適な 20、21、22 マーク ゴロム定規を探して
• 長さ200以上までのゴロム定規