巨大数研究 Wiki
Advertisement
巨大数研究 Wiki

Y(1,3)とDBMSの変換及び証明が難航しているため、ここで思考を整理しようと思う。

山火事の基本性質

追記(2020/12/15): 山火事の基本性質の証明が書かれたため一旦解決済みとする。

2020/11/02現在において証明がなされていない命題山火事の基本性質がある。名称の通り山火事という展開規則に関する命題なのだが、実際に内容を見て貰えれば分かる通り超極悪である。「基本」性質とは名ばかりで、実際にはこの規則によって展開された数列のMt.Fujiを書いた時、展開前の数列のMt.Fujiによって推測される形と一致するというものである。つまり、もしこの命題が成り立たなければ、定義に使われたプログラムどころかY数列数のwell-defined性すら危ぶまれる。最悪、停止しなくなるだろう。

さて、この命題は、Mt.Fujiがこの性質を満たせば数列は一致するということは比較的簡単に示せるだろう、なぜならばそれには展開のアルゴリズムの最後の方に現れるObjectの性質を調べればいいだけだからだ。しかし、実際に個別の数の親がこのようになるかというと難しい。BMSと違い、数列はこのMt.Fujiを圧縮したものであり、そこで情報を失ってしまうからだ。さらに、数がどのような式で表されるかを求めようとするとこれはまた複雑である。したがって、このことについての考察や思考をTwitterでツイートした文言を交えて書いていく。

ツイートのまとめ

筆者のツイッターのアカウントは非公開であることに注意されたい。

2020/10/28 13:27 基本性質(書き換え&ただしさの証明)

2020/10/28 14:22

good partに片足突っ込んでる時は高さも親も固定なので当然親は存在して、

噴火してかつisAscendingでない場合はB_r部分に繋がっているかgood partに片足突っ込んでるから当然親は存在して、

噴火してかつisAscendingな場合は、B_bならコピー先にあるのはわかっていて、

B_rは祖先を辿って怒る親にたどり着けるから当然親もコピーされていて、B_eはgood partに行ってたとしたら後の方が吸われているので大丈夫で、

山火事であったら横にそのままなので親の存在は大丈夫そう、そもそも必要なのは山火事の時であって噴火する時は今は考えていない。

そしてこれはgetBadRootで怒る親がコピー先の親が足らなくならないくらいに噴火する場合ガチャガチャ山肌まで動くから言える。


でもやっぱりMt.Fujiを再計算した時親がその感じになる証明ができない...


あと山火事(名詞)と噴火(名詞/動詞)日本語

2020/10/29 12:02

まず一番下、a,b,c,d,e,f,g,h,i,jがあってiの想定された親がgであったとして、計算仮定からg<iであるから、証明するべきはh≧i。ここでghijがcdefのコピーだとする。計算で親はコピー元から取っているからeの親はcである。ここで、計算過程の足し算を見る。


good partに片足突っ込むか山肌のところまでコピー元と等しい。そして、その下からは悪い部分に収まっている。


「良い部分」...


ツリーっぽい。親と左上の足し算が。そして、good partに入ったり山肌に行ったりしたら定数。bad rootにくっつく部分は下の方だけれど、これが難しい、

でも全てくっつくいて計算されるから足し算にはあまり関係しなくて、比べるぶんには定数としても変数としても消えるから大丈夫。そしてこのツリー構造はコピーされる。足し算にflattenしてmovie end. 何言ってるのか自分でもわからないけど実際にやってみればわかる。今1,2,4,8,10,8あたりで試してる。

2020/10/29 13:50 画像

2020/10/29 13:54 画像

2020/10/29 14:00

それぞれコピーに対応するコピーされたbadRootSeamの数を下からr_0,r_1,...,r_(h-1)としたら、それぞれの数を求める式はあるc,a_0,a_1,...,a_(h-1)が存在してc+Σ(0≦i<h)a_i×r_iと表され、コピーされるとc,a_iは固定でr_iが変化する。

2020/10/29 14:34

例えば1,2,4,8,13,12,8では13のコピーはr_0+2r_1+2r_2+3、12のコピーはr_0+2r_1+2r_2+2である。この場合は差が定数であるため比較が簡単である。しかし、それは全ての場合で成り立つだろうか。1,2,4,8,16,15,14,13,12,11,10,9,8,8と入れて全て見ると次のようになる。

16 - r_0+2r_1+3r_2+5

15 - r_0+2r_1+3r_2+4

14 - r_0+2r_1+3r_2+3

13 - r_0+2r_1+3r_2+2

12 - r_0+2r_1+2r_2+2

11 - r_0+2r_1+r_2+2

10 - r_0+r_1+r_2+3

9 - r_0+r_1+r_2+2

8 - r_0+r_1+r_2+1

よく見ると11と10では形が違うことがわかる。これでは単なる比較は不可能である。

2020/10/29 14:46

幸いなことにこの場合r_1≧r_2+1≧2であるから問題はないが、1,2,4,8,16,[16,32],16はどうだろう。r_1≧4である上r_2も定数でないから式の関係は無茶苦茶になるだろう。

2020/10/29 16:17

32 - r_0+2r_1+3r_2+4r_3+6

31 - r_0+2r_1+3r_2+4r_3+5

30 - r_0+2r_1+3r_2+4r_3+4

29 - r_0+2r_1+3r_2+3r_3+4

28 - r_0+2r_1+3r_2+3r_3+3

27 - r_0+2r_1+3r_2+2r_3+3

26 - r_0+2r_1+2r_2+2r_3+4

25 - r_0+2r_1+2r_2+2r_3+3

24 - r_0+2r_1+2r_2+2r_3+2

23 - r_0+2r_1+2r_2+r_3+2

22 - r_0+2r_1+r_2+r_3+3

21 - r_0+2r_1+r_2+r_3+2

20 - r_0+r_1+r_2+r_3+5

19 - r_0+r_1+r_2+r_3+4

18 - r_0+r_1+r_2+r_3+3

17 - r_0+r_1+r_2+r_3+2

16 - r_0+r_1+r_2+r_3+1

これ怒る親が親より遠い祖先の場合複雑になりそう

2020/10/29 23:14

怒る親の直接的な子に対してこのような式を取ったとき、コピー元の値の順序は対応する式の係数を(r_0,r_1,...,r_(h-1),c)と並べて辞書式順序を適応して保存されるか。


これは結局経路の問題で、多分証明できる。

2020/10/30 07:35

画像のは子じゃなくて孫か、とりあえず子の場合は、式を求める怒る親の子があって値がa=a'+1>a'>怒る親としたとき、aのコピーの式が(c_0,c_1,...,c_(h-1),c)という数列で表され、aをa_0、a_iの左上をa_(i+1)、a'をa'_0、a'_iの左上をa'_(i+1)とし、

p=max{i|i<h and a_(i+1) exists and parent(a_i) is not in good part}としたとき、a_p>1ならば0≤i<pならばparent(a)=parent(a')かつparent(a'_p)が存在しないかh≤pであるからa'の式は(c_0,c_1,...,c_(h-1),c-1)、a_p=1ならば

parent(a'_(p-1))=parent(parent(a_(p-1))となりそれとそれより左上は親がgood partに入りa'の式は(c_0,c_1,...,c_(p-2),0,...)となりa_(p-1)の親はr_(p-1)であるから0<c_(p-1)であるから、辞書式順序でa'の式の係数≺aの式の係数となり、この二つの順序は推移的であるからaとa'が怒る親の子であり、

cとc'がそれぞれaとa'のコピーの式を表す数式であるとき、a'<a⇔c'≺cである。

考察

ここでは展開の計算過程の欲しているMt.Fujiの形状を参照していることに注意。ある数の式はツリーによって示される。それぞれのノードは子の和であり、子は親と左上である。ツリーの深層化は対応する怒る親のコピー、良い部分、もしくは山肌にたどり着いたところで止める。すると、目的の数は対応するツリーの葉の総和と等しい。また、直系先祖に怒る親が含まれていなければ悪い部分から良い部分の間に祖先がいない[要証明]である。良い部分や山肌は定数であり[要証明]、またこのツリーはコピー同士で共有するため[要証明]、これは\(r_i\)を対応する怒る親の下から\(i\)番目の数、\(h\)を怒る親のseamのheightとした時、\(\sum_{0\leq i<h}c_ir_i+c\)という式で表すことができ、またこの式は係数と定数項を取り出すことで\((c_0,c_1,\cdots,c_{h-1},c)\)と表し、これを式の数列表記と呼ぶ。ツリーはコピーされるから数列表記は等しくなる。

ところで、推定している親があったとして、親が実際にそれになる条件とは何であろう。それは自分と親の間にある兄弟が自分以上であることである。甥などはその祖先、特に自分の兄弟より大きいため考えなくとも良い。

数列に対する辞書式順序を\(\prec\)とする。もし兄弟の関係にある数二つ\(a,b\)があり、対応する式の数列表記を\(f_a,f_b\)とした時、\(a< b\implies f_a\prec f_b\)を期待する。これは数列の一部、つまりMt.Fujiで一番下の列の数のみでなく、任意の数について考える。ただし、\(f_a=({c_a}_0,{c_a}_1,\cdots,{c_a}_{h-1},c_a)\)、\(f_b=({c_b}_0,{c_b}_1,\cdots,{c_b}_{h-1},c_b)\)とする。

ツイートには怒る親の子で上が成り立つ事が示されている。それを下に書き直す。

\(a-1=b\)とする。\(a\)のseamでheightが\(i\)の数を\(a_i\)、\(b\)のseamでheightが\(i\)の数を\(b_i\)とした時、\(0\leq c<h+1\)かつ\(a_c=1\)であるような\(c\)が存在しなければ、\(0\leq i<h\)ならば\(a_i\)と\(b_i\)の親は共通であるから、任意の非負整数\(i\)に対して\(0\leq i<h\)ならば\({c_a}_i={c_b}_i\)であり、また\(a-1=b\)であるから\(c_a-1=c_b\)である。\(0\leq c<h+1\)かつ\(a_c=1\)であるような\(c\)が存在し\(a_c\)の親が悪い部分に含まれるならば、\(0\leq i<c-1\)ならば\(a_i\)と\(b_i\)の親は共通であるから、\({c_a}_i={c_b}_i\)であり、\(b_{c-1}\)の親は\(a_{c-1}\)の親(\(=r_{c-1}\))の親以降でありこれは良い部分であるから、\({c_a}_{c-1}>{c_b}_{c-1}\)である。いずれの場合も\(f_b\prec f_a\)であり、また\(a-b>1\)の場合は再起的に成り立つ事が示せる。

一般化する。\(a-1=b\)かつ\(a\)と\(b\)は兄弟で親を\(p\)とし、\(a\)のseamでheightが\(i\)の数を\(a_i\)、\(b\)のseamでheightが\(i\)の数を\(b_i\)、\(p\)のseamでheightが\(i\)の数を\(p_i\)とした時、\(0\leq c<h+1\)かつ\(a_c=1\)であるような\(c\)が存在しなければ、\(a_i\)と\(b_i\)の親は共通であるから、任意の非負整数\(i\)に対して\(0\leq i<h\)ならば\({c_a}_i={c_b}_i\)であり、また\(a-1=b\)であるから\(c_a-1=c_b\)である。\(0\leq c<h+1\)かつ\(a_c=1\)であるような\(c\)が存在し\(a_c\)の親が悪い部分に含まれ\(a_c\)の左下の親が良い部分に含まれるならば、\(0\leq i<c-1\)ならば\(a_i\)と\(b_i\)の親は共通であるから、\({c_a}_i={c_b}_i\)であり、\(b_{c-1}\)の親は\(a_{c-1}\)の親の親以降でありこれは良い部分であるから、\({c_a}_{c-1}>{c_b}_{c-1}\)である。\(0\leq c<h+1\)かつ\(a_c=1\)であるような\(c\)が存在し\(a_c\)の親が悪い部分に含まれ\(a_c\)の左下の親が悪い部分に含まれるならば、\(0\leq i<c-1\)ならば\(a_i\)と\(b_i\)の親は共通であるから、\({c_a}_i={c_b}_i\)であり、\(b_{c-1}\)の親は\(a_{c-1}\)の親の親以降であるから\(\cdots\rightarrow a_{c-1}\rightarrow a_{c-1}\textrm{の親}\rightarrow a_{c-1}\textrm{の親の左上}\rightarrow\cdots\)の経路を失いこれによって\(r_c\)への既存の経路を少なくとも\(1\)本以上失い、\(b_c\)の親をたどる経路によって多くても\(r_c\)への経路を\(1\)本追加するから\(a_c\geq b_c\)であり、\(b_{c-1}=a_{c-1}-1=a_{c-1}\textrm{の親}+1-1=a_{c-1}\textrm{の親}\)であり、さらに\(c-1\leq i\)に対して\(b_i\)の値と親は同じheightの\(a_{c-1}\)nの親の左上の左上の...と等しくなるから、\(b\)のツリーは\(a\)のツリーの\(a_{c-1}\)のサブツリーを\(a_{c-1}\)の親のツリーで置換したものとなり、\(a_{c-1}=a_{c-1}\textrm{の親}+1\)から\(a_{c-1}\)の式は\(a_{c-1}\)の親の式より\(\prec\)大きくなるから\(f_b\prec f_a\)である。いずれの場合も\(f_b\prec f_a\)であり、また\(a-b>1\)の場合は再起的に成り立つ事が示せる。

この議論はMt.Fujiで一番下の数のみならず、階差数列を含む全ての数について適応可能である。親と自分の間にあるが兄弟でない数に山は繋がらないためである。

オリジナルまたはコピーの怒る親のseam\(r\)と\(r'\)があり、\(r\)は\(r'\)の左にあるとする。すると、任意の非負整数\(i<h-1\)に対し、\(r'_{i+1}-r_{i+1}\leq r'_i-r_i\)である。なぜならば、\(r'_{i+1}\)の\(r_{i+1}\)までの自分を含み\(r_{i+1}\)を含まない祖先は全て\(r'_i\)の\(r_i\)までの自分を含み\(r_i\)を含まない祖先の左上であり、任意の数の左上はその数より小さいからである。

よって、兄弟\(a\)と\(b\)と怒る親\(r\)があり、コピー\(a'\)と\(b'\)と\(r'\)があり\(a-1=b\)とする。 \(c\)が存在しなければ自明に\(b'<a'\)である。\(a_c\)が存在し\(a_c\)の親が悪い部分に含まれるならば、\(b\)のツリーは\(a\)のツリーの\(a_{c-1}\)のサブツリーを\(a_{c-1}\)の親のツリーで置換したものとなるから\(b'_{c-1}=a'_{c-1}\textrm{の親}\)となり、\(a_{c-1}=a_{c-1}\textrm{の親}+a_c\)の枝であるから\(a'_{c-1}=a'_{c-1}\textrm{の親}+a'_c>b'_{c-1}\)。\(0\leq i<c-1\)に対して\(a'_i=b'_i\)であるから\(b'<a'\)である。\(a-b>1\)の場合は再起的に成り立つ事が示せる。

!!!@1t***ae0要校正。「ーっw

制限した展開規則の数式的書き換えの必要性

必要である

毎回アルゴリズムを沿う必要がなくなり、証明が書きやすい。

今後の研究への可能性。

不必要である

これがなくとも証明は山火事の基本性質を使用することで可能である。

労力を要する。

用語と数式の変換

用語 数式
\(m\)で\(s\)番目のseamでheightが\(h\)である数 \(m_{h\textrm{Search}(m_h,s-h)}\)
\(o\)が横列\(r\)の要素であるときの\(o\)の親 \(r_{\textrm{parentIndex}(o)}\)
\(o\)が\(m\)の横列\(m_i\)の要素であるときの\(o\)の左上 \(m_{(i+1)\textrm{Search}(m_{i+1},\textrm{position}(o)-1)}\)
\(o\)が\(m\)の横列\(m_i\)の要素であるときの\(o\)の右下 \(m_{(i-1)\textrm{Search}(m_{i-1},\textrm{position}(o)+1)}\)
\(m\)の斜め階差数列 \(\textrm{diagonal}(m)\)

文献・脚注

Advertisement