近況
自宅のデスクトップPCが壊れた。
春に洗濯機を買い替えたこともあり、PC部品の買い替えがお財布にいたい。
先日、バシク行列コインなるものが発表された。
web3には詳しくないのでよく分からないが、このコインにどういう意義があるのかよく分からない。
このコインは与えられたバシク行列Sについて、何手か展開することでSになる行列を探す問題を解くと報酬がもらえる。
素人考えだが、一応proof of workっぽい体裁をとっているものの、この問題は計算量が小さすぎるように思える。
実際、任意の標準形のバシク行列SとS'について、S'[n]の計算が停止するのにn手かかるのだとすれば、Sの末尾にS'を連結したものはn手の計算でSになるので、この問題は定数時間で解けてしまう(標準形に限るならこの問題はもう少し複雑になるが、このコインでは標準形を気にしていない)。
一応、workの計算量が小さい場合でも、社会的に意義のある問題を扱っている仮想通貨なら報酬が出ることがあるが、この問題は社会的にも巨大数論的にもあまり意味がないので、このような問題に報酬を安易に出すのはコインの価値を下げかねない。
web3に詳しい方がいれば、このコインに価値があるのかを教えてほしい。
今回の一件の一つの教訓は、巨大数コミュニティに属していない人からすると「標準形」のような重要な概念が分かりづらいのかもしれない。
今回のコインを作った人はおそらく「標準形」という概念を知らずに作っており、それゆえコインが巨大数論的には無価値なものになっているように見える(何か勘違いをしていたらごめんなさい)。
巨大数論の重要な概念・用語はしばしば巨大数の定義には直接書かれておらず、そのアルゴリズムに関する詳細な議論に触れることで初めてわかる。
私たちは別にこれを隠しているわけでもないのだが、やはり多くの人は巨大数研究wikiの記事に書かれた解説か、そこから再生産された解説しか目を通さないので、その周辺で使われている重要な概念は全く伝わってないとみるべきなのだろう。
なぜこのような重要な概念が記事に書かれていないのかと言えば、記事に載せるコストが高いからである。
本記事に書いてあるものはある程度コンセンサスや数学的な正しさが必要とされる。
巨大数の議論はインターネット上に散乱していて、これらをある程度把握したうえで誰もが納得する書き方をしないといけないのだが、そこそこ手間がかかる。
今回の件を受けてバシク行列の記事に「標準形」の解説を加えたが、その後rpakr法(バシク行列の標準形判定法)に関する指摘を受けた。
恥ずかしいことにこの議論の存在は全く覚えていなかったし、今もrpakr法をどう説明したらいいのか悩んでいるところである。
こういう具合で、数学強者でも巨大数強者でもない私が記事を編集するのは腰が引けてしまう。
すこし話が変わるが、最近Xで、wikipediaの「巨大数」の項目で列挙されている巨大数の一覧は「内輪ノリ」ではないのかというポストを見かけた。
私も、「巨大数」と「巨大数(ネットカルチャー)」の記事を分けた方がいいと思う。
巨大のカルチャーは生まれてから四半世紀もたっているのであって、そろそろ誰かが(数学ではなく)社会現象としてきちんと精査してテキストに残すべきだろうが、wikiに「巨大数(ネットカルチャー)」の記事を新設するのは相当手間がかかると予見される。
誰かここら辺を上手くやってくれませんか。
メモ帳
いまのところ分かっていることをまとめておく場所です。
適宜更新します。
経験的事実
- m行バシク行列の長さnの標準形の数をf_m(n)とすると、実際にf_m(n)を計算できる程度の範囲ではlog(f_m(n))∝nが成り立っているように見える。
- よく見ると、y=log(f_m(n))はy=kxより僅かに急増大しているようにみえる。
- (n!)^m>f_m(n)>(m+n)!/m!×n!であるため、f_m(n)は指数～階乗程度の増大速度を持ち、log(f_m(n))の増大速度はO(n)～O(n×log(n))である。
- グラフを書いて直線y=kxに見えていたのは、もしかするとy=kx×log(x)では？
- 長さnの巨大数列の標準形の数は厳密に2^n個。→最小の数列システムが2^nであるなら、それに合わせて他の数列システムを分析するときにも対数の底を2にした方が比べやすい？
- f(n)を計算する際の計算量は非常に大きい。バシク行列を何十万回も展開することになるが、ハム太郎の親バシクはバシク行列と同等でありながら計算量を著しく抑えることができる。
- 対数の底を2として、原始数列はlog(f(x))=1.37x-2.41、横ベクレミシェフはlog(f(x))=2.25x-3.3、ペア数列はlog(f(x))=2.51x-4.51。Γ0の横ベクが原始数列よりペア数列に近くなっているのはグーゴロジストの直感から反している。これは横ベクの極限形が(0,0,1,1,2,2...)だからではないかという仮説が立った。そこで、極限形を(0,0,1,1,2,2...)にした原始数列を作るとlog(f(x))=2.02x-2.73、横ベクより少し小さい極限形を無理やり(0,1,2,3,...)にした横ベクはlog(f(x))=1.45x-2.68になったので、仮説は正しいと思われる。
- ペア亜数列問題：現在もっとも頭を悩ませている問題である。二行目を巨大数列に変えたペア数列をペア亜数列と呼ぶこととする。ペア亜数列はΦ(ω,0)程度の強さを持つ。ペア亜数列問題は、長さnのペア亜数列がペア数列よりとても多いという問題である。なぜこのような現象が起こるのかよく分からない。
考察の試み・足掻き
以下、簡単のため数列を展開する際のブラケットは固定されているものとする。
いかなる数列システムでもf(x)個の長さxの数列の内、末尾が0の数列(後続順序数に対応する数列)はf(x-1)個ある。
また、長さxの数列のうち、一手展開すると長さyになる数列の個数をg(y,x)とする。
数列システムの長さの遷移にのみ注目し、数列システムを単純化したモデルとして以下のようなマルコフ過程を考えることとする。S_{i}は長さがiであるという状態に対応する。
- 自然数iで添え字づけされた可算個の状態S_iを持つ。
- S_0は必ずS_1に、S_1は必ずS_0に遷移する。
- i>1の場合、S_iは確率f(x-1)/f(x)でS_{i-1}に、確率g(j,x)/f(x)でS_{j}に遷移する。
このマルコフ過程から求まる特徴量はいくつかあるので、それを数列システムの特徴量として解釈できないだろうか？
例えば、遷移確率のスペクトル特性、S_{0}に至るまでの期待時間、拡散係数、再帰確率の減衰率等がある。
(この確率過程に定常確率はないので、一般的な指標である定常確率のエントロピーは使えない。)
今はまだ分からないが、h(t)=lim_{x→∞}g([ty],x)/f(x)が収束するなら、モデルをより簡単にできるだろう。(h(t)は一手の展開で長さがt倍になる確率を表す。[x]は床関数。)。
もっとも重要な問題はこの確率過程はS_{0}にほとんど確実に至るか？という問題である。
f(x)が指数オーダーの場合、f(x-1)/f(x)は一定である。(つまり、どの長さの数列を集めても後続順序数が同じ確率で入っている!)
そのため、g(y,x)が分かればS_{0}に有限時間で至ることが比較的簡単にわかる。
f(x)が階乗オーダーの場合、f(x-1)/f(x)≒1/xであり、この正再帰性は非自明であり、S_{0}に有限時間で至るかは比較的難しそうである。
こういう思考過程で、とにもかくにもf(x)の増大速度とg(y,x)、可能であればh(t)を実験で求めるのが良いと思っている。
h(t)はブラケットに依存してしまうので、代わりにb/v(bはbad partの長さ、vは数列の長さ)の分布を知ればよい。
検定
上に述べたマルコフ過程の仮定がどの程度妥当かというのは統計的な検定で調べることができる。
長さiの数列が一手の展開で長さjになる割合をp(i,j)、長さiの数列が二手の展開で長さjになる割合をq(i,j)として、q(i,k)=Σ_{j}p(i,j)p(j,k)が成り立っていることを検定すればよい。
しかし、現状バシク行列でこの検定を行うのには困難が伴っている。
例えば、ブラケットを3に固定した場合二手、展開すると長さは9倍程度になりうる。
長さ10の数列から始めた場合、長さ90程度になる恐れがあるが、長さ90のペア数列をすべて列挙するのは不可能である。
検定を行う一つの方法は長さnのm行バシク行列を偏りなくランダムに取得する方法を確立することである。
それができれば、ランダムに200個ほどの行列を選んでp(i,j)、q(i,j)を求めることで、ある程度信頼できる検定が可能であろう。
宇宙人
(この記事では、数列を展開する際にS[n]のnが自然数pに固定されているとします。
また、空の列を展開すると空の列になるとします。)
ある日、ある星の宇宙人が謎の数列書き換え操作を手に入れた。
グーゴロジストと呼ばれる地球人の一部が利用しているらしいが、宇宙人には数列が何を意味しているのかは全く分からない。
宇宙人は数列の書き換え操作を繰り返し観察することで、以下の知見を得た。
・長さnの標準形数列はe^n個程度である。
・書き換え操作によってほとんど確実に文字列は長くなる。具体的には、長さnの文字列の数e^nに対して、長さが減る文字列はe^(n-1)個程度である。
・長さが増える場合にt倍になったとすると、あるpが存在してtは1<t<pの範囲で分布していた。
宇宙人は熱力学のことは知っていたので、以下のように推論した。
・長さvの標準形数列の数をf(v)して、S=k・log(f(v))(kは(ボルツマン)定数)とすると、Sとvは比例している。これはエントロピーSと体積vの関係に似ている。きっとこの文字列は気体の状態を表していて、書き換え操作はその時間発展なのだろう。
・ほとんど確実にvが増えるので、拡散している気体のようなものだろう。
・長さが減る確率が一定の割合で存在しているので、小さなエネルギー障壁があるのだろう。
・内部エネルギーはU=αv(αは定数)のように表されるだろう。
・温度はT=α/kだろう。
宇宙人はtの分布を詳しく調べることで、この書き換え操作の統計的性質を求めることにした。
後日、宇宙人は他にも何種類かの謎の数列書き換え操作を手に入れたので、書き換え操作ごとにボルツマン係数と内部エネルギーの係数α、tの分布を求めて分類した。
いくつかの数列はf(v)=∞となったので、適切な制限を課した。
※地球人は数列の展開規則を知っているため、tの分布を調べる場合は「長さvの数列のbad rootがn番目の項としたときのn/vの分布」を調べたほうが効率が良い。
(宇宙人がより大きな数列についても観察を続けると、実はvが十分大きい場合にはlog(f(v))とvは比例関係から離れているという実験結果を得るかもしれない。しかし、vが小さい範囲での線形近似には一定の有用性がある。
特に巨大数イベント等では、膨大な量の表記を表解析をする前にある程度の傾向が掴めるなら大きなメリットだろう。)
正月
正月はジョージ・オーウェルの1984を読んだ。
陰鬱な気分になったため、正月に読むんじゃなかったと後悔している。
jgaの記事投稿祭をやろうというのはハムさんの案だった。
ハムさんがどういう意図でこれを提案したのかは分からないが、かねてから既存の巨大数コンテストの開催は難しくなっているという話題は上がっていた。
審査員ができる人の数は変わらないのに、巨大数を作る技術の発展に伴って解析が難しくなって審査の負担が増えているために、大会が持続可能ではないのではないかという意見である。
また、既存の巨大数コンテストは巨大数を作った人以外が評価されないという側面があった。
そこで、持続可能で、様々な巨大数の営みが評価されうる巨大数のコンテストとして記事投稿祭というアイデアは非常に良いものに思えた。
記事投稿祭は東方巨大数とのすみわけが明確なように設計された。
金とグレーの高級感のある配色を全面に押し出し、大会運営の言葉は堅い敬語で統一して、「投稿祭」ではなく「記事大賞」にした。
もともとjgaのアイコンがモノトーンなこともあってうまくかみ合っていると思う。
(大会メッセージを書くたびに、ハムさんと敬語の言い回しに頭を抱えている)
ロゴのデザインやgoogle siteのページの製作はハムさんがやってくださった。
ありがたい。
投票ではなく、審査員がそれぞれページを選んで賞を与えるというアイデアもあったが、賞が結局個人の好みであると思われるのが怖いので変更した。
明らかに失敗したと感じているのは、google siteのドメインをjga-article-awardsで取得してしまったことである。
japan-googlogy-associationで取得しておけば、他にもいろんなことに使えただろう。
google siteの自由度があんなに高いとは思っていなかったため、今回のイベントに使ったらもう使わないと思っていた。
バシク行列計算ドリル
バシク行列に慣れるためにバシク行列を計算してみましょう。
以下のバシク行列について
]を求めてください。
余裕があれば頑張って対応する順序数を求めてください。
1.\begin{pmatrix}0\end{pmatrix}
2.\begin{pmatrix}
0 & 1 & 0
\end{pmatrix}
3.\begin{pmatrix}
0 & 1 & 2 & 3 & 2
\end{pmatrix}
4.\begin{pmatrix}
0 & 1 \\
0 & 1 \\
\end{pmatrix}
5.\begin{pmatrix}
0 & 1 & 1\\
0 & 1 & 0\\
\end{pmatrix}
6.\begin{pmatrix}
0 & 1 & 2\\
0 & 1 & 0\\
\end{pmatrix}
7.\begin{pmatrix}
0 & 1 & 2\\
0 & 1 & 1\\
\end{pmatrix}
8.\begin{pmatrix}
0 & 1 & 2 & 3\\
0 & 1 & 1 & 1\\
\end{pmatrix}
9.\begin{pmatrix}
0 & 1 & 2\\
0 & 1 & 2\\
\end{pmatrix}
10.\begin{pmatrix}
0 & 1 & 2 & 3\\
0 & 1 & 2 & 3\\
\end{pmatrix}
型システムとは
工学において、型とはプログラムの変数のデータの分類である。
「180」は自然数の型を持ち、「"Hello"」は文字列の型を持つ。
型システムはデータの分類を検証してくれるシステムである。
例えば、自然数の型を持つ変数にうっかり「"Hello"」を代入してしまっても、型システムはあらかじめそのミスを検出してくれる。
実社会で使われるプログラムにおいて、事前にミスを発見できるのは非常に便利なので、多くのプログラミング言語で型システムが導入されている。
このブログでは上のような工学的立場に立って、最小の前提知識で強力な型システムCalculus of Constructionsを紹介する。
その後、型理論と数理論理学の関連を紹介する。
