ランベック・モーザーの定理

ランベック・モーザーの定理は、自然数を2つの相補的な集合に分割する数学的な記述です。例えば、偶数と奇数、または素数と非素数（1と合成数）への分割に適用されます。ランベック・モーザーの定理には2つの部分があります。1つは、ある意味で逆関数である任意の2つの非減少整数関数を使用して、自然数を2つの相補的な部分集合に分割できることを示し、もう1つは、すべての相補的な分割をこのように構成できることを示しています。${\displaystyle n}$集合内の 番目の自然数に対して、ランベック・モーザーの定理を用いて、次の式を得ることができます。${\displaystyle n}$セットに含まれていない番目の数。

ランベック・モーザーの定理は組合せ数論に属する。1954年に発表したヨアヒム・ランベックとレオ・モーザーにちなんで名付けられており^{[ 1 ]} 、後にロイ・ワイルドによって強化された、原始ピタゴラス三つ組の数に関するランベックとモーザーの無関係な定理とは区別されるべきである^{[ 2 ]}。これは、無理数の丸められた倍数の数列であるビーティ数列の相補的なペアを記述するレイリーの定理を拡張したものである。

任意の2つの実数値逆関数のグラフは、対角線に関して互いに鏡像関係にある。

素数計数関数のヒストグラム（濃い赤色）とその鏡像（薄い赤色）

正の実数上の任意の2つの逆関数のグラフは、対角線に関して互いに鏡像関係にある。${\displaystyle x=y}$[ ^{3 ]}整数関数については、逆関数の類似物と、関数のグラフに類似した曲線（本稿ではヒストグラムと呼ぶ）を定義することが可能であり、^{[ 4 ]同じ}反射特性が成り立つ。より詳細には、${\displaystyle f}$正の整数から非負の整数への任意の関数で、かつ非減少（数列の各値）である。${\displaystyle f(1),f(2),f(3),\dots }$は、少なくとも前の値以上であり、かつ無制限である（最終的には任意の固定値を超えて増加する）。 のヒストグラムを定義する。${\displaystyle f}$点を通る区分的線形曲線である${\displaystyle (0,0)}$、${\displaystyle (i-1,f(i))}$、 そして${\displaystyle (i,f(i))}$各正の整数に対して${\displaystyle i}$水平線と垂直線が交互に現れます。垂直線があるため、関数のグラフではありません。ただし、水平線とその右端点のみを含めると、次のグラフになります。 ${\displaystyle f(\lceil x\rceil )}$丸める関数${\displaystyle x}$整数まで適用します${\displaystyle f}$垂直線分はこれらの水平線分を繋ぎ合わせて、単一の連続した曲線を形成する。^{[ 5 ]}非減少かつ非有界の整数関数を定義する${\displaystyle f^{*}}$それは、すべての正の整数に対して、逆数にできるだけ近いという意味である。${\displaystyle n}$、 $${\displaystyle f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.}$$ 同様に、${\displaystyle f^{*}(n)}$値の数として定義される${\displaystyle x}$そのために${\displaystyle f(x)<n}$これらの定義のいずれからも、${\displaystyle f^{*}{}^{*}=f}$^{[ 6 ]}すると、逆関数のペアのように、2つの関数は${\displaystyle f}$そして${\displaystyle f^{*}}$対角線を挟んで互いに鏡像関係にあるヒストグラムを持つ${\displaystyle x=y}$[ ^{5 ]​}

これら2つの関数から${\displaystyle f}$そして${\displaystyle f^{*}}$さらに2つの関数を定義します${\displaystyle F}$そして${\displaystyle F^{*}}$正の整数から正の整数へ、

$${\displaystyle {\begin{aligned}F(n)&=f(n)+n\\F^{*}(n)&=f^{*}(n)+n\\\end{aligned}}}$$ すると、ランベック・モーザーの定理の最初の部分は、各正の整数が、以下の値のいずれかの中にちょうど一度だけ出現することを述べている。${\displaystyle F}$または${\displaystyle F^{*}}$つまり、以下の値から得られる${\displaystyle F}$そして、以下の値から得られた${\displaystyle F^{*}}$正の整数の2つの相補的な集合を形成する。より強く言えば、これら2つの関数はそれぞれ引数を写像する。${\displaystyle n}$へ${\displaystyle n}$パーティション内のその集合の 番目の要素。^{[ 6 ]}

関数から分割を構築する例として、${\displaystyle f(n)=n^{2}}$、引数を二乗する関数。すると、その逆関数は平方根関数であり、その最も近い整数近似値（ランベック・モーザーの定理で使用される意味で）は${\displaystyle f^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor }$これら2つの関数は${\displaystyle F(n)=n^{2}+n}$そして${\displaystyle F^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor +n.}$ のために${\displaystyle n=1,2,3,\dots }$値${\displaystyle F}$プロニック番号は

2、6、12、20、30、42、56、72、90、110、...

値${\displaystyle F^{*}}$は

1、3、4、5、7、8、9、10、11、13、14、...

これら 2 つの数列は相補的である。各正の整数は、そのうちの 1 つにのみ属する。^{[ 5 ]}ランベック・モーザーの定理によれば、この現象はプロニック数に特有のものではなく、任意の選択で発生する。${\displaystyle f}$適切な特性を備えている。^{[ 6 ]}

ランベック・モーザー定理の第2部では、逆関数からの分割の構成は普遍的であると述べており、正の整数を2つの無限部分に分割するあらゆる場合を説明できるという意味である。${\displaystyle S=s_{1},s_{2},\dots }$そして${\displaystyle S^{*}=s_{1}^{*},s_{2}^{*},\dots }$任意の2つの相補的な増加整数列であれば、関数のペアを構築することができる。${\displaystyle f}$そして${\displaystyle f^{*}}$この分割は、ランベック・モーザーの定理を用いて導出できる。そのためには、次のように定義する。${\displaystyle f(n)=s_{n}-n}$そして${\displaystyle f^{*}(n)=s_{n}^{*}-n}$[ ^{6 ]​}

この方法を適用できる最も単純な例の1つは、正の整数を偶数と奇数に分割することです。${\displaystyle F(n)}$そして${\displaystyle F^{*}(n)}$与えるべき${\displaystyle n}$それぞれ偶数または奇数なので${\displaystyle F(n)=2n}$ そして${\displaystyle F^{*}(n)=2n-1}$これらから2つの関数が導き出される。${\displaystyle f(n)=F(n)-n=n}$そして${\displaystyle f^{*}(n)=F^{*}(n)-n=n-1}$これらは逆のペアを形成し、このペアからランベック・モーザーの定理によって生成される分割は、正の整数を偶数と奇数に分割するのと全く同じです。別の整数分割、つまり（二進表現の偶奇性によって）邪悪な数と忌まわしい数に分割するには、ほぼ同じ関数を使用しますが、チュー・モース数列の値によって調整されます。^{[ 8 ]}

ランベックとモーザーは、ランベック・モーザー定理を証明したのと同じ研究の中で、${\displaystyle F}$関数は${\displaystyle n}$正の整数の集合の 番目の要素、${\displaystyle F^{*}}$関数は${\displaystyle n}$非会員は、${\displaystyle f}$そして${\displaystyle f^{*}}$。させて${\displaystyle F^{\#}(n)}$の値の数を表す${\displaystyle x}$そのために${\displaystyle F(x)\leq n}$これは、の逆関数の近似値です。${\displaystyle F}$しかし（それは${\displaystyle \leq }$の代わりに${\displaystyle <}$定義に使用される逆数のタイプから 1 だけオフセットします${\displaystyle f^{*}}$から${\displaystyle f}$すると、任意の${\displaystyle n}$、${\displaystyle F^{*}(n)}$数列の極限は $${\displaystyle n,n+F^{\#}(n),n+F^{\#}{\bigl (}n+F^{\#}(n){\bigr )},\dots ,}$$ つまり、ある時点以降、この数列の連続する値はすべて等しくなり、結果として得られる値は${\displaystyle F^{*}(n)}$[ ^{9 ]​}

ランベックとモーザーは、ヴィゴ・ブルンとDH・レーマーの以前の研究に倣い、素数を例として用いた。^{[ 10 ]}${\displaystyle \pi (n)}$は素数計数関数です（${\displaystyle n}$)、それから${\displaystyle n}$番目の非素数（1または合成数）は、数列の極限によって与えられます。^{[ 9 ]}$${\displaystyle n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\bigr )},\dots }$$

いくつかの選択肢では${\displaystyle F}$シーケンス${\displaystyle n,n+F^{\#}(n),\dots }$固定ステップ数後に繰り返しを開始します。${\displaystyle n}$それは、から始まります。この場合、繰り返しが始まる時点での数列の要素は、補関数の直接的な公式を与えます。${\displaystyle F^{*}}$例えば、これは次のような場合に起こります。${\displaystyle F(n)=n^{k}}$、${\displaystyle k}$の力​${\displaystyle n}$（整数の場合）${\displaystyle k\geq 2}$):数列は常に第 3 項から繰り返されます。この考え方を利用して、${\displaystyle n}$でない 番目の正の整数${\displaystyle k}$のべき乗は、極限式の3番目（繰り返し）の項によって与えられます^{[ 11 ]}$${\displaystyle n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\rfloor .}$$

この定理はレオ・モーザーとヨアヒム・ランベックによって発見され、1954年に発表された。モーザーとランベックは、サミュエル・ビーティによるビーティ数列に関する先行研究を着想源として挙げ、また、 1930年代初頭のヴィゴ・ブルンとDH・レーマーによる極限公式に関連する手法に関する研究も引用している。${\displaystyle F^{*}}$[ ^{1 ]​}

エドガー・W・ダイクストラは、この結果の視覚的な「証明」（ダイクストラによる引用符）^{[ 12 ]} 、そして後にアルゴリズム的推論に基づくより厳密な証明^{[ 13 ]}を提供した。これら2つの証明のうち最初のものは、整数の分割を平面上の長方形の配置として幾何学的に表現している。これらの長方形の寸法は${\displaystyle 1\times n_{i}}$（単位幅）数値用${\displaystyle n_{i}}$パーティションの最初のセットに属するもの、そして${\displaystyle n_{i}^{*}\times 1}$（単位高さ）数値用${\displaystyle n_{i}^{*}}$2番目のセットでは、各長方形の左下隅が対角線上に位置するように配置されています。${\displaystyle x+y=-2}$そして、それらがこの線より上の半平面の整数正方形を一緒に覆うようにします。最初の長方形、単位正方形は、右上隅を原点に置いて配置されます。次に、長方形は面積の順に1つずつ追加されます。各垂直長方形は、前の長方形の左側に、その左下隅がこの対角線上になるように追加され、各水平長方形は、前の長方形の上に、やはりその左下隅がこの対角線上になるように追加されます。次に、関数${\displaystyle f(i)}$そして${\displaystyle F(i)}$このパッキングから、定理の 高さを読み取ることができます。${\displaystyle i}$th の垂直長方形が上に立ち上がります${\displaystyle x}$それぞれ、軸またはその底辺です。同様に、関数${\displaystyle f^{*}(i)}$そして${\displaystyle F^{*}(i)}$は、${\displaystyle i}$th の水平長方形は右側に伸びています${\displaystyle y}$それぞれ軸またはその左端。逆に、任意の2つの関数${\displaystyle f}$そして${\displaystyle f^{*}}$または${\displaystyle F}$そして${\displaystyle F^{*}}$定理の条件を満たすと、このタイプの長方形充填が生じ、そこから次の値が得られます。${\displaystyle F}$そして${\displaystyle F^{*}}$整数の分割と見なすことができる。^{[ 12 ]}

ユヴァル・ギノサールは、円形のレーストラックを反対方向に、異なる速度で走る2人のアスリートのアナロジーに基づいて、直感的な証明を提供しました。アスリートの一方がトラック上の固定マークを通過するたびに、もう一方のアスリートと出会った回数を報告します（レースの開始を1回の出会いとして数えます）。交差する回数は数えられる回数なので、マークは2人が決して出会わないトラック上の地点に設置できます。すると、アスリートが連続して2回出会う間に、2人はトラック上の各地点を1回ずつ通過するので、この間にちょうどどちらか一方がマークを通過して出会いの回数を報告します。したがって、各アスリートが報告する数値の集合は、正の整数の分割を形成します。ギノサールはこの設定から、ランベック・モーザーの定理の残りの性質を導き出しました。^{[ 14 ]}

• ホフスタッター図形-図形シーケンスは、ランベック-モーザーの定理を適用できるもう1組の相補的なシーケンスである。