そろそろネタ元をばらしましょう。次の論文です。これを[Fiore/Leinster]として引用します。
- Marcelo Fiore, Tom Leinster "Objects of Categories as Complex Numbers"
http://arxiv.org/abs/math/0212377
[Fiore/Leinster]から参照されている以下の論文がSeven Treesを詳しく扱ったもののようです（僕はまだ読んでません）。
- A. Blass "Seven trees in one" Journal of Pure and Applied Algebra, 103:1.21, 1995.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.8517
Seven trees と A tree が同じになる（木とタプルの変形で移りあえる）ことは、ウィリアム・ローヴェルが言い出した事らしいです（ローヴェル論文も僕は未見）。
- F. W. Lawvere "Some thoughts on the future of category theory" In Proc. Como 1990, volume 1488 of Lecture Notes in Mathematics, pages 1.13. Springer-Verlag, 1991.
(Web上には見あたらない)
[Fiore/Leinster]には、Seven Treesパズルの答までは書いてないのですが、十分なヒントは得られます。[Blass]には完全な解があるようです（bonotakeさん情報）。これらのヒント（あるいは答）を見るのもいいでしょうし、がんばって自分で解くのもご自由に。僕は僕で、Seven Treesパズルとその周辺をもう少し説明するつもりです（今日はあまりしないけど）。
これには驚いちゃうよね、等式変形からアルゴリズムへ
ローヴェルも「これには驚いたぜ」（I was surprised to note that ...）と言ってるようですが、何の背景もなしにこの同型（T = T7）はまず思いつかないでしょう。T = I + T2 の両辺を互いに写す同型から出発すれば、T = T7 にたどり付く、ってわけです。
[Fiore/Leinster]に、その等式変形が途中まで出ています。
T
= 1 + T2
// T2 → T + T3 と展開する
= 1 + T + T3
// T3 → T2 + T4 と展開する
= 1 + T + T2 + T4
// I + T2 → T と縮約する
= 2T + T4
...
...
展開（unfold）と縮約（fold）を繰り返すのですが、その基本は Tn ←→ Tn-1 + Tn+1 です； これは T = I + T2 の両辺にTn-1を掛け算すれば出ます。
上の[Fiore/Leinster]の引用では（もとの論文でも）、計算が4ステップしか書いてありませんが、18ステップの計算で T7 が出るそうです。
僕はヒントを知っているけど、できない。
と書いた時点で、18ステップの計算ができなかったのです(苦笑; なんとかなったが)。T → I + T2 と I + T2 → T の写像は、「ちゃんと問題を述べると」の最後に書いたように具体的な手順で書けます。Tn → Tn-1 + Tn+1 と Tn-1 + Tn+1 → Tn もタプルの成分を操作すればいいので具体的に書けます。というわけで、等式変形の各ステップは、必ず具体的な操作に落とせます。18ステップ全体を追いかければ、T → T7 と T7 → T の両方向の具体的なアルゴリズムが得られます。
アルゴリズムとはいっても、与えられた木のルートに近い部分（最大でも4レベル）だけを見ればいいので、有限個のパターンマッチを使い分ければいいのです。パターンマッチの数（場合分けの数）は、KeisukeNakanoさんによると5まで落とせるようですが、5が最小なのでしょうか？ 限界の評価や、評価がsharpestであることをどう示すか見当が付かないので、僕はわかりません。
Seven Treesの魅力と拡がり
「7」がミステリアスなマジックナンバーとして登場するところがこのパズルの醍醐味ですよね。任意のnで出来ちゃうのでは、ロマンもポエムも面白みもありません。T = Tn が成立する次の候補はもちろん n = 13です（根拠は「どこがヒントなんじゃい？」に書いたとおり）。
Seven Treesは、プログラミングパズルとして、あるいは、データ構造とアルゴリズムの観点から十分に興味深いのですが、それで話が閉じてしまうわけではありません。
「どこがヒントなんじゃい？」で述べたようなクレイジーな計算（crazy calculation）、意味不明な証明（nonsense proof）が、実は妥当（valid）なことが[Fiore/Leinster]で証明されています。「方程式に関する命題が複素数の範囲で確認できれば、実は二分木のようなデータ構造の領域でも同様な命題が成立する」というメタ定理です。
このメタ定理は、論理（モデル論、証明論）の立場からも面白いと思います。技術的には、半環（semiring, rig）から環を絞り出す新しい方法や、多項式の古典代数学が使われます。この手法を適用するなら、不動点方程式で定義される再帰的領域（の同型）に関する問題は、多項式イデアルの問題に翻訳されます。例えば、グレブナー基底を使った計算代数システムでイデアルの問題を解いてしまえば、領域の同型が保証されます。
二分木のデータ領域Tは、T = I + T2 を満たすことから、データ領域の圏のなかで、「1の6乗根」の役割を演じていることになります。よって、I（単元集合）とT（二分木集合）から、足し算（直和）と掛け算（直積）で生成された領域の全体は、1（ほんとのイチ）とτ（1の6乗根）から掛け算と足し算で生成された環に相当します。1とτから作られた環は、複素数体の部分環で「代数的な整数の環」の一例です。データ領域と代数的整数論が意外なところで結びついている印象があります。面白いですね。
