iPX社員によるブログ

iPX社員が"社の動向"から"自身の知見や趣味"、"セミナーなどのおすすめ情報"に至るまで幅広い話題を投下していくブログ。社の雰囲気を感じ取っていただけたら幸いです。

怪物曲線

最近思うこととか

今回はかなり固い内容をしてみようと思う、今週担当の鹿又と申します。
大学と大学院の専門は「数学」と「情報」でしたが、双方とも現在でも (笑) 程度の実力です。
iPXの中には、この双方ともで相当な実力を持つ人たちにあふれています。
また、今まで出会ってきた人々は皆、遠慮せずに努力でき、それに見合った実力を持つ人たちばかりで、それはそれは自分の存在の価値を恥ず位でした。

今回のお題について

私のやってきた数学は、直接「数」を扱うものではありませんでした。
思えば、私は置換積分とか部分積分とかよくわかっていませんし...。
聞く話によると、数学というのは、解析学幾何学代数学の3つに分かれているそうで、今回のお題は幾何学代数学の中間の位置(?)に当たる「離散幾何学」という分野に位置づけられるそうです。
確率論や統計学らへんは、数学者に言わせれば「数学ではない」らしいです。

中学、高校辺りから数学について嫌な印象をお持ちの方々もいらっしゃる中、「曲線」という言葉は正直耳障りのよい言葉ではありませんね。
曲線の中にも変な性質を持ったものがいて、これを「怪物」とか「フラクタル」とか言います。
変な性質というのは、これらの曲線はInitiatorとGeneratorという2種の線でできていて、自己相似性 (fractale)という性質を持っていて、操作によって線が重なり合わないというものです。
なんのこっちゃって感じですよね。
一応、例にドラゴン曲線やヒルベルト曲線があります。(これはWikipediaとかご覧下さい)
ヒルベルトって響きがいいと思っていたら、そう言えば、ゼノサーガで使われていましたね。

ゴスパーの怪物曲線

もう10年以上も前になる大学2年生の時代。
学力が足らず、浪人する程でもない大学に入学するのに1浪して、センター試験の「化学」の成績のみでギリギリ合格したのでしたが...。
入学時、大学では経営とか組織論とかやりたいと思っていたものの、これが大して面白くなく、逆に面白かった講義が現在齢80を超える中村義作先生の「統計学」でした。
これがきっかけでオペレーションズリサーチ (OR) なんかも面白く感じ、文転ならぬ理転する感じになった大学2年生。(けれど2つとも純粋数学とは言えない)
数学めいたマクロ経済学は授業に5回しか出ていないのに試験の成績は2位になるなど、このくそ凡人の大したことのない人生の中で最も頭がよかった時期のようでした。
選んだゼミは数理系で、先生からやってみろと言われた題が「拡張ゴスパーの怪物曲線の探索」でした。
忘れもしない最初の課題がとても重く、まずは先生の書いたCソース1000行の内容理解と説明、探索アルゴリズムと性質の数学的証明でした。
特に数学的証明の1つは全然わからず、授業中も自宅に帰っても移動時でも四六時中考え、やっと4日目にして帰納法で解いたのを思い出します。
家に帰ってからそれこそ没頭して朝を迎えるということは、人生においてこれ以外にありませんでした。

探索アルゴリズムはここに記しませんが、ゴスパーの怪物曲線というのは、オリジナルではこんなものです。
線の本数が7本なのでN=7と書きます。
f:id:ipx-writer:20150921012442j:plain
7本の黒の矢印がGenerator、赤い長い矢印がInitiatorです。
この各GeneratorをInitiatorとして見て、矢印の向きも考慮して曲線を書き直すと下のようになります。
f:id:ipx-writer:20150921012451j:plain
この操作は何度でも可能で、仮に操作回数を「深度」というならば、深度=2は上の形、深度=3になると、
f:id:ipx-writer:20150921012456j:plain
深度=4ではこのようになります。
f:id:ipx-writer:20150921012500j:plain
この再帰操作では、Generatorが互いに交わることなく、しかも永遠にできます。

この曲線にはいくつかの性質があります。
① Generatorに正三角形を"反時計回りに矢印が来るように"付けると綺麗に格子状になる (polyhex)
  こんな感じに
f:id:ipx-writer:20150921012446j:plain

② ①の図形は3回割り図形 (120°回転対称)

③ ①の図形のInitiatorにも正三角形を付けると、Initiatorの正三角形の面積 = Σ(Generatorの正三角形の面積)
f:id:ipx-writer:20150921014326j:plain
この証明が先ほど書いた、とても大変だった証明です。

④ Nを決めると、Initiatorの(x, y)座標およびGenerator1つの長さが自動的に決まる
⑤ N=3n+1しかあり得ない

拡張ゴスパー曲線

ふつう思うのは、「N=7と言っているのだから、これだけではないでしょう」という予想です。
性質を見つけて証明し、それを基にして探索をかけると、オリジナル以外で最初に見つかるのは、最小でN=13でこんなやつです。
左:曲線    右:正三角形を付けたもの
f:id:ipx-writer:20150921021123j:plain
再帰操作すると、
深度=2,     深度=3
f:id:ipx-writer:20150921021406j:plain

さらに大きいのを探索すると、こんなのも出てきます。
N=19
ラーメンみたいなやつ
f:id:ipx-writer:20150921023355j:plain

N=37
f:id:ipx-writer:20150921023408j:plain

N=61
f:id:ipx-writer:20150921023420j:plain

N=91
見つけた最大のものです。
f:id:ipx-writer:20150921023425j:plain

その後...

この研究は最後どうなったか?
コンピュータによる探索を行っても、この拡張ゴスパー曲線、N=3n+1にしか現れないことは数学的に証明可能なものの、実際はなぜかN=6n+1のときにしか現れなく、N=6n+1であっても拡張が存在しないNもあることがわかりました。
観測的な法則はあるが証明できていないものを「予想」って言います。
中村先生もそれに興味をもって、一緒に考えてくれましたが一部条件下でのみ証明でき、結局完全な証明はできませんでした。
更に、探索には「ハミルトン閉路問題」というNP完全問題 (O(c^n)なのかな??) が立ちはだかり、Nが十分大きい場合には全探索自体が不可能になりました。
この「O」というのは確か、ビッグオーノーテーションなんて名前で呼ばれて、サイズが1増えると手数がどんだけ増えるかということで、「...のオーダで増える」みたいに使うと思います。
大学生だった私の名前は入っていないものの、先生がまとめ直した論文が学会誌に載ったそうです。

大学時代はよかったなぁという、ほとんどおじさんになってしまった人間のツマラナイ武勇伝といった感じになってしまいました。サーセンでした...。

<参考 興味のある方は以下もどうぞ>
1. 高くて買えません...
http://www.amazon.co.jp/%E9%9B%A2%E6%95%A3%E5%B9%BE%E4%BD%95%E5%AD%A6%E3%81%AB%E3%81%8A%E3%81%91%E3%82%8B%E6%9C%AA%E8%A7%A3%E6%B1%BA%E5%95%8F%E9%A1%8C%E9%9B%86-P-%E3%83%96%E3%83%A9%E3%82%B9/dp/4621063391

2. Wikipedia
ドラゴン曲線 - Wikipedia
ヒルベルト曲線 - Wikipedia

3. 実際読んでません...(1)
https://www.chikumashobo.co.jp/product/9784480093561/

4. 実際読んでません...(2)
http://www.amazon.co.jp/%E3%83%9E%E3%83%BC%E3%83%81%E3%83%B3%E3%83%BB%E3%82%AC%E3%83%BC%E3%83%89%E3%83%8A%E3%83%BC%E3%81%AE-%E6%95%B0%E5%AD%A6%E3%82%B2%E3%83%BC%E3%83%A0-1-%E5%88%A5%E5%86%8A%E6%97%A5%E7%B5%8C%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9-176/dp/4532511763