モーザー・デ・ブルイン配列

数論において、モーザー・デ・ブルイン数列は、レオ・モーザーとニコラース・ゴヴェルト・デ・ブルインにちなんで名付けられた整数列であり、4の異なるべき乗の和から構成される。言い換えれば、2進数表現において偶数位のみが非ゼロである数、あるいは4進数表現において数字が0と1のみで構成される数である。

この数列のモーザー・デ・ブルイン数は平方数に比例して増加します。これらは繰り上がりのない修正された算術の平方数です。2 つのモーザー・デ・ブルイン数の差に 2 を掛けても平方数にはなりません。すべての自然数は、モーザー・デ・ブルイン数とモーザー・デ・ブルイン数の 2 倍の和として一意に構成できます。この和としての表現は、整数と、 Z オーダー曲線上の位置の順に並べられた整数のペアとの間の1 対 1 の対応関係を定義します。

モーザー・ド・ブルイン数列は、互いに乗法逆元であり、かつ両方とも単純な十進数表現を持つ超越数のペアを構成するために使用できます。単純な漸化式により、モーザー・ド・ブルイン数列の値を以前の値から計算することができ、モーザー・ド・ブルイン数列が2正則数列であることを証明するために使用できます。

モーザー・デ・ブルイン数列の数字は、4の異なるべき乗を足し合わせることによって形成されます。数列はこれらの数字をソートされた順序でリストします。数列は^{[ 1 ]から始まります。}

例えば、69はこの数列に属します。なぜなら、69は64 + 4 + 1に等しく、これは4の3つの異なるべき乗の和だからです。

Moser–de Bruijn 数列の別の定義は、2 進数表現で偶数位にのみゼロ以外の数字を持つ数の順序付き数列であるということです。たとえば、69 はこの数列に属します。なぜなら、その 2 進数表現 1000101 _2には、2 ⁶、2 ²、および 2 ⁰の位置にゼロ以外の数字があり、これらはすべて偶数の指数を持つからです。数列の数は、4 進数表現で数字 0 または 1 のみを使用する数として記述することもできます。 ^{[ 1 ]}この数列の数の場合、4 進数表現は、奇数位の 2 進数桁をスキップすることによって 2 進数表現から見つけることができます。奇数位の 2 進数桁はすべてゼロである必要があります。これらの数の16 進数表現には、数字 0、1、4、5 のみが含まれます。たとえば、69 = 1011 ₄ = 45 _{16 です}。言い換えれば、それらはバイナリ表現とネガバイナリ表現が等しい数である。 ^{[ 1 ] [ 2 ]}バイナリ表現に連続する2つの非ゼロがないため、モーザー・デ・ブルイン数列はフィボナッチ数列の部分列を形成する。

これらの数の二進数または4進数の定義から、それらは平方数にほぼ比例して増加することがわかります。モーザー・デ・ブルイン数列の任意の閾値以下の要素の数${\displaystyle n}$に比例する${\displaystyle {\sqrt {n}}}$[ ^{3 ]} この事実は平方数にも当てはまります。より正確には、その数^は${\displaystyle {\sqrt {n}}}$（次の形式の数値の場合）${\displaystyle n=4^{k}}$） そして${\displaystyle {\sqrt {3n}}}$（のために${\displaystyle n\sim 4^{k}/3}$実際、モーザー・デ・ブルイン数列の数値は、二進数の繰り上がりを伴わない算術の二乗であり、単一ビットの加算と乗算はそれぞれ排他的論理和と論理積演算である。^{[ 4 ]}

平方差のない数列に関するFurstenberg–Sárközy の定理に関連して、 Imre Z. Ruzsa は、Moser–de Bruijn 数列の二進定義と同様に、基数における交互の位置の数字を制限する、大きな平方差のない集合の構成法を発見しました。${\displaystyle b}$数字。^{[ 5 ]}基数に適用した場合${\displaystyle b=2}$ルザの構成法は、モーザー・ド・ブルイン数列を2倍したものを生成するが、これもまた二乗差のない集合である。しかし、この集合は疎すぎるため、ファーステンベルク・サルコジの定理に対する非自明な下限を与えることはできない。

Moser–de Bruijn 列は、 Sidon 列と同様の性質に従います。つまり、和は${\displaystyle x+2y}$、 どこ${\displaystyle x}$そして${\displaystyle y}$両方ともモーザー・デ・ブルイン数列に属し、すべて一意です。これらの和のうち、同じ値を持つものは2つとありません。さらに、すべての整数は${\displaystyle n}$合計として表すことができる${\displaystyle x+2y}$、 どこ${\displaystyle x}$そして${\displaystyle y}$両方ともモーザー・デ・ブルイン数列に属します。${\displaystyle n}$計算する${\displaystyle x=n\ \&\ \mathrm {0x55555555} }$ビットごとのブール値と${\displaystyle n}$すべての偶数位置に 1 を持つバイナリ値 (ここでは16 進数で表現) で、${\displaystyle y=(n-x)/2}$[ ^{1 ] [ 6 ]​}

モーザー・デ・ブルイン数列は、すべての整数が一意の式を持つという性質を持つ唯一の数列です。${\displaystyle x+2y}$こうした理由から、この数列はもともとモーザー（1962）によって研究された。^{[ 7 ]}この性質を拡張して、デ・ブルイン（1964）は次のような無限に多くの線形式を発見した。${\displaystyle x+2y}$その時${\displaystyle x}$そして${\displaystyle y}$両方ともモーザー・デ・ブルイン数列に属し、すべての整数を一意に表します。^{[ 8 ] [ 9 ]}

数値を分解する${\displaystyle n}$の中へ${\displaystyle n=x+2y}$そして、${\displaystyle x}$そして${\displaystyle y}$Moser–de Bruijn 数列から整数への順序保存写像 (各数の 4 乗を対応する 2 乗に置き換えることによって) は、非負整数から非負整数の順序対への全単射を与えます。この全単射の逆は、非負整数座標を持つ平面上の点の線形順序を与え、これはZ オーダー曲線を定義するために使用できます。^{[ 1 ] [ 10 ]}

このアプリケーションに関連して、モーザー・デ・ブルイン数列の各要素をその前の要素から生成する式があると便利です。これは次のように行うことができます。${\displaystyle x}$はシーケンスの要素であり、その次の要素は${\displaystyle x}$は、バイナリ表現の奇数位置のビットを埋めることによって得られる。${\displaystyle x}$1ずつ増やし、結果に1を加え、埋められたビットをマスクします。ビットを埋めて1を加えることは、1つの加算演算にまとめることができます。つまり、次のメンバーは式^{[ 1 ] [ 6 ] [ 10 ]で与えられる数です。}$${\displaystyle \displaystyle (x+{\textrm {0xaaaaaaab}})\ \&\ {\textrm {0x55555555}}.}$$ この式に現れる2つの16進定数は、2進数として解釈できます。${\displaystyle 1/3}$そして${\displaystyle -1/3}$それぞれ。^{[ 1 ]}

ゴロンブ（1966）は、この数列に基づいて、平方数を引くことに類似した減算ゲームを調査した。ゴロンブのゲームでは、2人のプレイヤーが交互に山からコインを取り除く。${\displaystyle n}$コイン。各ターンで、プレイヤーはモーザー・デ・ブルイン数列に属する任意の数のコインを取り除くことができる。それ以外の数のコインを取り除くことは許されない。最後のコインを取り除いたプレイヤーが勝者となる。ゴロンブが指摘するように、このゲームの「コールド」局面（これから手番をするプレイヤーが負けている局面）は、まさに次の形式の局面である。${\displaystyle 2y}$どこ${\displaystyle y}$これはモーザー・デ・ブルイン数列に属します。このゲームで勝つための戦略は、現在のコインの数を分解することです。${\displaystyle n}$、 の中へ${\displaystyle x+2y}$どこ${\displaystyle x}$そして${\displaystyle y}$両方ともモーザー・デ・ブルイン系列に属し、そして（もし${\displaystyle x}$（ゼロ以外）削除${\displaystyle x}$コインを捨て、他のプレイヤーに不利な状況を残す。${\displaystyle x}$がゼロの場合、この戦略は不可能であり、勝ち手はありません。^{[ 3 ]}

モーザー・デ・ブルイン数列は無理数の例の基礎を形成する。${\displaystyle x}$10進数表現の${\displaystyle x}$そして${\displaystyle 1/x}$どちらも簡潔かつ明示的に記述できます。${\displaystyle E}$は Moser-de Bruijn シーケンス自体を示します。それから $${\displaystyle x=3\sum _{n\in E}10^{-n}=3.300330000000000330033\dots ,}$$ 非ゼロの桁がモーザー・デ・ブルイン数列で与えられる位置にある十進数の場合、その逆数の非ゼロの桁は、1、3、9、11、…の位置にあり、これは、${\displaystyle E}$そしてそれらすべてに1を加える：^{[ 11 ] [ 12 ]}$${\displaystyle {\frac {1}{x}}=3\sum _{n\in E}10^{-2n-1}=0.30300000303\dots \ .}$$

あるいは、次のように書くこともできます。 $${\displaystyle \displaystyle \left(\sum _{n\in E}10^{-n}\right)\left(\sum _{n\in E}10^{-2n}\right)={\frac {10}{9}}.}$$

同様の例は他の基数でも成り立ちます。たとえば、上記の 2 つの十進数の非ゼロの桁と同じ位置に非ゼロのビットがある2 つの二進数も無理数の逆数です。 ^{[ 13 ]}これらの二進数と十進数、および Moser–de Bruijn 数列で与えられた位置に 1 つの非ゼロの桁を繰り返すことによって他の基数でも同じように定義される数は、超越数です。それらの桁の長いゼロ列により、無理数度が 3 以上である代数的数である場合にRoth の定理で許容されるよりも正確に有理数で近似できるという事実から、それらの超越性が証明できます。 ^{[ 12 ]}

生成関数$${\displaystyle F(x)=\prod _{i=0}^{\infty }(1+x^{4^{i}})=1+x+x^{4}+x^{5}+x^{16}+x^{17}+\cdots ,}$$ 展開された形式の指数がモーザー・ド・ブルイン数列で与えられ、関数方程式^{[ 1 ] [ 2 ]に従う。}$${\displaystyle F(x)F(x^{2})={\frac {1}{1-x}}}$$ および^{[ 14 ]}$${\displaystyle F(x)=(1+x)F(x^{4}).}$$ 例えば、この関数は上記の 2 つの小数逆数を記述するために使用できます。1 つは${\displaystyle 3F(1/10)}$そしてもう一つは${\displaystyle {\tfrac {3}{10}}F(1/100)}$それらが逆数であるという事実は、2 つの関数方程式のうちの最初の例です。生成関数の積形式の部分積は、これらの数自体、およびそれらの倍数の連分数展開の収束を生成するために使用できます。 ^{[ 11 ]}

Moser–de Bruijn 数列は、数列の n 番目の値、${\displaystyle S(n)}$（開始時刻は${\displaystyle S(0)=0}$）位置の値から決定されます${\displaystyle \lfloor n/2\rfloor }$:$${\displaystyle {\begin{aligned}S(2n)&=4S(n)\\S(2n+1)&=4S(n)+1\end{aligned}}}$$ この漸化式を繰り返すと、次の形式の任意の部分列が得られます。${\displaystyle S(2^{i}n+j)}$元の数列の線形関数として表現されるということは、モーザー・デ・ブルイン数列が2正則数列であることを意味する。^{[ 15 ]}

• スタンレー数列とカントール集合は、要素の3進数表現を用いて同様に定義される集合である。

• Weisstein、Eric W.、「Moser–De Bruijn Sequence」、MathWorld