L-階差数列システム

注意　この記事は未完成です。

東巨3に出したL-階差数列システムの解説(主に解析の話)をします。証明の類は全無視の方向で行きます。

\(M=m\)

東巨3エントリーには使用されていませんが、\(M\)が定数関数のときから始めます。

定義はここに載ってるので、概要だけ抽出して説明します。

• 末項の階差と\(-m\)のうち、大きい方を\(D\)とする。
• 末項より小さく階差が\(D\)より小さい項の内最右の項をBad rootとする。

以下略。

\(m=0\)

特に難しいところもないのでサッと流します。

(0,1)=(|0|0|0|...)=\({\omega}\)

(0,1,1)=(|0,1|0,1|0,1|...)=\({\omega^2}\)

(0,1,1,2)=(0,1|1|1|1|...)=\({\omega^{\omega}}\)

(0,1,1,2,1,2)=\({\omega^{\omega×2}}\)

(0,1,1,2,1,2,2)=(0,1,1,2|1,2|1,2|1,2|...)=\({\omega^{\omega^2}}\)

(0,1,1,2,1,2,2,3)=(0,1,1,2,1,2|2|2|2|...)=\({\omega^{\omega^{\omega}}}\)

(0,1,1,2,2)=(|0,1,1,2|1,2,2,3|2,3,3,4|...)=\({\varepsilon_0}\)

(0,1,1,2,2,1,2,2,3,3)=(0,1,1,2,2|1,2,2,3|2,3,3,4|3,4,4,5|...)=\({\varepsilon_0^2}\)

(0,1,1,2,2,1,2,2,3,3,2,3,3,4,4)=\({\varepsilon_0^{\varepsilon_0}}\)

(0,1,1,2,2,2)=(|0,1,1,2,2|1,2,2,3,3|2,3,3,4,4|...)=\({\varepsilon_1}\)

(0,1,1,2,2,3)=(0,1,1,2|2|2|2|...)=\({\varepsilon_{\omega}}\)

(0,1,1,2,2,3,2)=(|0,1,1,2,2,3|1,2,2,3,3,4|2,3,3,4,4,5|...)=\({\varepsilon_{\omega+1}}\)

(0,1,1,2,2,3,2,3,3,4,4)=(0,1,1,2,2,3|2,3,3,4|3,4,4,5|4,5,5,6|...)=\({\varepsilon_{\varepsilon_0}}\)

(0,1,1,2,2,3,3)=(|0,1,1,2,2,3|2,3,3,4,4,5|4,5,5,6,6,7|...)=\({\zeta_0}\)

(0,1,1,2,2,3,3,2)=\({\varepsilon_{\zeta_0+1}}\)

(0,1,1,2,2,3,3,2,3,3,4,4,5,5)=\({\varepsilon_{\zeta_0×2}}\)

(0,1,1,2,2,3,3,3)=\({\zeta_1}\)

(0,1,1,2,2,3,3,4)=\({\zeta_{\omega}}\)

(0,1,1,2,2,3,3,4,3,4,4,5,5,6,6)=\({\zeta_{\zeta_0}}\)

(0,1,1,2,2,3,3,4,4)=(|0,1,1,2,2,3,3,4|3,4,4,5,5,6,6,7|6,7,7,8,8,9,9,10|...)=\({\varphi(3,0)}\)

(0,1,2)=(|0,1|1,2|2,3|...)=\({\varphi({\omega},0)}\)

(0,1,2,2)=\({\varepsilon_{\varphi({\omega},0)+1}}\)

(0,1,2,2,3,3)=\({\zeta_{\varphi({\omega},0)+1}}\)

(0,1,2,2,3,4)=\({\varphi({\omega},1)}\)

(0,1,2,3)=\({\varphi({\omega},{\omega})}\)

(0,1,2,3,3,4,5)=\({\varphi({\omega},{\omega+1})}\)

(0,1,2,3,3,4,5,6)=\({\varphi({\omega},{\omega×2})}\)

(0,1,2,3,4)=\({\varphi({\omega},{\omega^2})}\)

(0,2)=(|0|1|2|...)=\({\varphi({\omega},{\omega^{\omega}})}\)

\(m=1\)

まず、列\(S_n\)を定義しておきます。

• \(S_0=0\)
• \(S_{n+1}=S_n,S_n+1\)

例

\(S_1=0,1\)

\(S_2=0,1,1,2\)

\(S_3=0,1,1,2,1,2,2,3\)

\(S_4=0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4\)

\(S_n\)は以下の性質を持ちます。

• 初項は\(0\),末項は\(n\)
• 長さは\(2^n\)
• 階差の最小値は\(2-n\)(中央の一か所のみ)
• 階差が全て\(-m\)以上である連続部分列の最大長は\(2^{m+2}\)

以降、これを使って略記します。

\((0,1,1,2,1,2,2,3,2)=(S_3,2)=(|S_3|S_3+1|S_3+2|...)={\varepsilon_0}\)

一応解説します。

\((S_3,S_3+1,S_3+2...)\)の階差は\(S_3+n\)と\(S_3+n+1\)の境界で\(-2\)になり、\(D\)より小さいのでBad root探索はここで終わります。また、\({\Delta}\)の値は常に0で、\({\Delta}=0\)のときの挙動は原始数列とほぼ同じなので\((S_3,2)={\varepsilon_0}\)になります。

\((S_3,2,1)=(|S_3,2|S_3,2|S_3,2|...)={\varepsilon_0×{\omega}}\)

\((S_3,2,1,S_3,2)=(|S_3,2,1,S_3|S_3+1,3,2S_3+1|S_3+2,3,2S_3+2|...)={\varepsilon_1}\)

m=0のときは2の後に2を追加すると\({\alpha}→{\alpha}↑↑{\omega}\)の効果になりますが、今回は3の後でないと\(S_2\)と\(S_2+1\)の間で引っ掛かります。

\((S_3,2,1,S_3,2,1,S_3,2)={\varepsilon_2}\)

\((S_3,2,1,1)={\varepsilon_{\omega}}\)

\((S_3,2,1,1,S_3,2,1,1)={\varepsilon_{\omega×2}}\)

\((S_3,2,1,2)={\varepsilon_{\omega^{\omega}}}\)

\((S_3,2,S_2+1,S_3+1,3)={\varepsilon_{\varepsilon_0}}\)

\((S_3,2,S_2+1,2)={\zeta_0}\)

\((S_3,2,S_2+1,2,1,S_3,2)={\varepsilon_{\zeta_0+1}}\)

\((S_3,2,S_2+1,2,1,S_3,2,S_2+1,S_3+1,3,S_2+2,3)={\varepsilon_{\zeta_0×2}}\)

\((S_3,2,S_2+1,2,1,S_3,2,S_2+1,2)={\zeta_1}\)

\((S_3,2,S_2+1,2,1,1)={\zeta_{\omega}}\)

\((S_3,2,S_2+1,2,1,2)={\zeta_{\omega^{\omega}}}\)

\((S_3,2,S_2+1,2,S_2+1,S_3+1,3,S_2+2,3)={\zeta_{\zeta_0}}\)

\((S_3,2,S_2+1,2,S_2+1,2={\varphi(3,0)}\)

\((S_3,2,2)=(S_2|S_2+1,2|S_2+1,2|S_2+1,2|...)={\varphi({\omega},0)}\)

m=0のときと異なり、\({\varphi({\omega},0)}\)が小極限になりました。

\((S_3,2,2,1,S_3,2)={\varepsilon_{\varphi({\omega},0)+1}}\)

\((S_3,2,2,1,S_3,2,S_2+1,2)={\zeta_{\varphi({\omega},0)+1}}\)

\((S_3,2,2,1,S_3,2,2)={\varphi({\omega},1)}\)

\((S_3,2,2,1,1)={\varphi({\omega},{\omega})}\)

\((S_3,2,2,1,2)={\varphi({\omega},{\omega^{\omega}})}\)

\((S_3,2,2,S_2+1,S_3+1,3,3)={\varphi({\omega},{\varphi({\omega},0)})}\)

\((S_3,2,2,S_2+1,2)={\varphi({\omega+1},0)}\)

\((S_3,2,2,S_2+1,2,2)={\varphi({\omega×2})}\)

\((S_3,2,2,2)={\varphi({\omega^2})}\)

\((S_3,2,3)={\varphi({\omega^{\omega}},0)}\)

\((S_3,S_2+2,S_3+2,4)={\varphi({\varepsilon_0},0)}\)

\((S_2,S_2+1,S_2+2,3)={\varphi(1,0,0)}\)

\((S_2,S_2+1,S_2+2,3,2)={\varepsilon_{\varphi(1,0,0)+1}}\)

\((S_2,S_2+1,S_2+2,3,2,1,S_2,S_2+1,2)={\varepsilon_{\varphi(1,0,0)+2}}\)

\((S_2,S_2+1,S_2+2,3,2,1,S_2,S_2+1,2,S_2+1,2)={\zeta_{\varphi(1,0,0)+1}}\)

\((S_2,S_2+1,S_2+2,3,2,1,S_2,S_2+1,S_2+2,3)={\varphi(1,0,1)}\)

\((S_2,S_2+1,S_2+2,3,2,1,1)={\varphi(1,0,{\omega})}\)

\((S_2,S_2+1,S_2+2,3,2,1,2)={\varphi(1,0,{\omega^{\omega}})}\)

\((S_2,S_2+1,S_2+2,3,2,S_2+1,2)={\varphi(1,1,0)}\)

\((S_2,S_2+1,S_2+2,3,2,S_2+1,S_2+2,3)={\varphi(2,0,0)}\)

\((S_2,S_2+1,S_2+2,3,2,2)={\varphi({\omega},0,0)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3)={\varphi(1,0,0,0)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3,2,1,S_2,S_2+1,S_2+2,3,S_2+2,3)={\varphi(1,0,0,1)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3,2,S_2+1,2)={\varphi(1,0,1,0)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3,2,S_2+1,S_2+2,3)={\varphi(1,1,0,0)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3,2,S_2+1,S_2+2,3,S_2+2,3)={\varphi(2,0,0,0)}\)

\((S_2,S_2+1,S_2+2,3,S_2+2,3,S_2+2,3)={\varphi(1,0,0,0,0)}\)

\((S_2,S_2+1,S_2+2,3,3)=SVO={\psi_0({\Omega^{\Omega^{\omega}}})}\)

\({\varphi}\)関数が力尽きたので\({\psi}\)関数に切り替えます。ここで使用する\({\psi}\)関数は以下のタイプのものです。(名前や定義は忘れました。)

• \({\psi_n(0)}={\varepsilon_{\Omega_n+1}}\)
• \({\psi_n({\alpha+1})}={\psi_n({\alpha})}↑↑{\omega}\)
• \({\psi_0({\Omega_{\omega}})}={\psi_0({\psi_1({\psi_2(...)})})}\)

\((S_2,S_2+1,S_2+2,3,4)={\psi_0({\Omega^{\Omega^{\omega^{\omega}}}})}\)

\((S_2,S_2+1,S_2+2,S_2+3,4)={\psi_0({\Omega^{\Omega^{\Omega}}})}=LVO\)

\((S_2,2)={\psi_0({\psi_1(0)})}=BHO\)

\((S_2,2,1,S_2,S_2+1,2)={\psi_0({\psi_1(0)+1})}\)

\((S_2,2,1,S_2,S_2+1,2,S_2+1,2)={\psi_0({\psi_1(0)+{\Omega}})}\)

\((S_2,2,1,S_2,S_2+1,S_2+2,3)={\psi_0({\psi_1(0)+{\Omega^{\Omega}}})}\)

\((S_2,2,1,S_2,2)={\psi_0({\psi_1(0)×2})}\)

\((S_2,2,1,1)={\psi_0({\psi_1(0)×{\omega}})}\)

\((S_2,2,S_2+1,2)={\psi_0({\psi_1(0)×{\Omega}})}\)

\((S_2,2,S_2+1,3)={\psi_0({\psi_1(0)^2})}\)

\((S_2,2,S_2+1,3,2,2)={\psi_0({\psi_1(0)^{\omega}})}\)

\((S_2,2,S_2+1,3,S_2+2,3)={\psi_0({\psi_1(0)^{\Omega}})}\)

\((S_2,2,S_2+1,3,S_2+2,4)={\psi_0({\psi_1(0)^{\psi_1(0)}})}\)

\((S_2,2,2)=(0,1,1,2,2,2)={\psi_0({\psi_1(1)})}\)

\((0,1,1,2,2,3)={\psi_0({\psi_1({\omega})})}\)

\((0,1,1,2,2,3,S_2+2,S_2+3,4)={\psi_0({\psi_1({\Omega})})}\)

\((0,1,1,2,2,3,S_2+2,4)={\psi_0({\psi_1({\psi_1(0)})})}\)

\((0,1,1,2,2,3,3)={\psi_0({\psi_1({\Omega_2})})}\)

\((0,1,1,2,2,3,3,2)={\psi_0({\psi_1({\Omega_2})+1})}\)

\((0,1,1,2,2,3,3,2,2)={\psi_0({\psi_1({\Omega_2+1})})}\)

\((0,1,1,2,2,3,3,2,3,3,4,4,5,5)={\psi_0({\psi_1({\Omega_2}+{\psi_1({\Omega_2})})})}\)

\((0,1,1,2,2,3,3,3)={\psi_0({\psi_1({\Omega_2×2})})}\)

\((0,1,1,2,2,3,3,4)={\psi_0({\psi_1({\Omega_2×{\omega}})})}\)

\((0,1,1,2,2,3,3,4,4)={\psi_0({\psi_1({\Omega_2^2})})}\)

\((0,1,2)={\psi_0({\psi_1({\Omega_2^{\omega}})})}\)

既に気付いた人も多いと思いますが、\(m=0\)のときと\(m=1\)のときの(0,1,1,2,2)から(0,1,2)までの挙動は非常によく似ている部分があります。

• \((0,1,1,2,2)_0={\psi_0(0)}\)
• \((0,1,1,2,2)_1={\psi_0({\psi_1(0)})}\)

• \((0,1,1,2,2,3)_0={\psi_0({\omega})}\)
• \((0,1,1,2,2,3)_1={\psi_0({\psi_1({\omega})})}\)

• \((0,1,1,2,2,3,3)_0={\psi_0({\Omega})}\)
• \((0,1,1,2,2,3,3)_1={\psi_0({\psi_1({\Omega_2})})}\)

• \((0,1,2)_0={\psi_0({\Omega^{\omega}})}\)
• \((0,1,2)_1={\psi_0({\psi_1({\Omega_2^{\omega}})})}\)

\({\psi_n}\)と\({\Omega_n}\)の\(n\)の値が増えています。結論だけ言うとこの現象は\(m\)の値が増えていっても続くようで、例えば\((0,1,1,2,2,3,3)_2={\psi_0({\psi_1({\psi_2({\Omega_3})})})}\)になります。ちなみに\({\omega}\)はこの現象には関わらないようで、 \((0,1,2)_2={\psi_0({\psi_1({\psi_2({\Omega_3^{\omega}})})})}\)になります。

\(m\)の値が増えると\({\varepsilon_0}\)～\({\psi_0({\psi_1(0)})}\)までの対応関係は際限なく複雑化していきますが、\({\psi_0({\psi_1(0)})}\)からは上記のように\(M=m-1\)のときの\({\varepsilon_0}\)からの対応関係と同じ感じになります。

\(M=L_0(0)\)

いよいよ本題であるLDSの話に入ります。

まず、そもそもL関数とは何かというところから説明します。\(M\)が定数関数のとき、\(M\)が\(1\)増えるごとに\({\psi_n}\)の\(n\)の値も\(1\)ずつ増えていくというのは先ほど説明しました。これが正しければ、システムの強さは\(M\)が増えるごとに\({\psi_0({\Omega_{\omega}})}\)に近づいていくものの、\({\psi_0({\Omega_{\omega}})}\)を超えることはできません。ならば\(M=\infty\)とすればいいのではないか、と思うかもしれませんが(実は最初に思い付いたのは\(M=\infty\)で、その後に\(M=m\)に修正されました。)そうすると\((0,1,2)\)の計算が終了しません。そこで、\(M\)の値を有限としつつ段階的に引き上げていくために考え出したのが\(L_0(0)\)関数です。\(L_0(0)\)は数列に依存した値をとる関数で、「階差が全て0より大きい連続部分列の最大長」を表します(本来のL関数の定義はもう少し複雑ですが、\((0,2)_{L_0(0)}\)未満の話に限定すればこの説明でも十分です。)。

例

• \((0,1,2,3,0,1,2)_{L_0(0)}=(\underline{0,1,2,3},0,1,2)_4\)
• \((0,1,1,2,1,2,2,3)_{L_0(0)}=(\underline{0,1},1,2,1,2,2,3)_2\)

\(S=S_n\)のときは\(L_0(0)=2\)なので、\((0,1,2)\)までは\(M=2\)の場合と同じ振る舞いをします。そして\((0,1,2)\)から\((0,1,2,3)\)までは\(M=3\)とほぼ同じ(先頭が\(S_5\)でないので若干ややこしくなります。)挙動を示し、以降同様に挙動が切り換えられていきます。

よってここまでの話を総合すると\((0,2)_{L_0(0)}={\psi_0({\Omega_{\omega}})}\)と評価でき、

E3:A-01-Hs\(\approx f_{\psi_0({\Omega_{\omega}})+1}(108)\)

となります。

\(M=L_0(1)\)

さて、いよいよこの記事を書いた主目的である\(L_0(1)\)数列の話に入ります。

以下、執筆中。