【数学】コラッツ予想を解きたい！01

概要

やりたいことは、タイトルの通りです。
01という数字から察せられるように連載型で、まずは10回を目指して書いていきます。最終的に解けるかどうかは知りません。

方針

コラッツ予想を解くうえでどうしたら良いか？
筆者は、ツリーについて理解度を上げるのが急所と見ました。

$$f(x) = \left\{ \begin{array}{ll} 3x+1 & (x:\mathrm{odd}) \\ x/2 & (x:\mathrm{even}) \end{array} \right. \$$

コラッツ予想で出てくるこの $f$ と、以下の $Tree$が一対一対応しているという発想を基本にしてみます。（なお、すべての枝は向き付きの枝とします）

Tree

1───2───4───8───16─┬─32───64───...
└───────┘          └─5───10─┬─20───40─┬─80───...
                            │         └─13───26───...
                            └─3───6───12───...

この発想より、$f$ によって生成される木 $T$に対し、

$$T=\mathrm{Tree}(f) \$$

のような書き方をすることにします。

また、集合 $A$ 上の木として、
・枝は向き付きで考える
・すべての $A$ の要素からちょうど１つの枝が伸びる
を満たす木全体の集合を考えると、これが$f:A\rightarrow A$のような形をした関数全体の集合と一対一対応するのは明らかですね。

このような前提から、理解を進めていったら、なんか解けたりしないかな～って思ったりしてます。
（※些細なことですが、正確に言うとツリーではなく、有向グラフと言うべきかもしれません。ただとりあえず既存の概念は多用するつもりはなく、そもそも筆者は自力で考えてみたいから未解決問題にチャレンジしているというところがあります）

「Treeの構造」という概念

Treeが等しいとは、当然、その元となる関数が一致するかどうかです。
しかしこれだけでは発展性がないため、別の概念を持ち込むことを考えましょう。

例えば、集合

$$A=\{1, \ 2, \ 3,\ 4,\ 5,\ 6,\ 7,\ 8\ \} \$$

の上で、次のような２つのツリー $T_1, T_2$ を考えます。（枝の向きは心の目で見てください）

T1

1───2───3─┬─4───5
└───┘     └─6─┬─7
              └─8

T2

2───5───1─┬─8───7
└───┘     └─6─┬─3
              └─4

この２つのツリーは、それぞれのノードの数値自体は異なりますが、全体の形が一緒ですよね。これって数式で書くとどうなるでしょうか。
具体的なノードの対応としては、

$$\sigma= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 5 & 1 & 8 & 7 & 6 & 3 & 4 \end{pmatrix} \$$

となり、また２つのツリーについて、

$$T_1=\mathrm{Tree}(t_1) \\ T_2=\mathrm{Tree}(t_2)$$

としてみます。$\sigma,\ t_1,\ t_2$間でどのような関係式が成り立つかが気になるところですね。

   ─2───3─
    ↓σ  ↓σ
   ─5───1─

こんな発想から...

$$\sigma(t_1(3))=\sigma(2)=5=t_2(1)=t_2(\sigma(3)) \$$

よって、

$$(\sigma \circ t_1)(3)=(t_2 \circ \sigma)(3) \$$

（関数の合成の記法は、この分かりやすい順序で定義します）

これは一般に成り立つので、次のような等式が得られます：

$$\sigma \circ t_1=t_2 \circ \sigma \$$

非常にきれいな関係式が成り立ちました！
この発想を基に、ツリーの構造という概念を定義します。

Def：ツリーの構造

集合 $A$ 上２つのツリー

$$T_1=\mathrm{Tree}(t_1), \ \ T_2=\mathrm{Tree}(t_2)$$

について、ある全単射写像 $\sigma:A \rightarrow A$ が存在して、

$$\sigma \circ t_1=t_2 \circ \sigma$$

が成り立つとき、$T_1$ と $T_2$ の構造は等しいという。またこの時、

$$T_1 \simeq T_2$$

と書く。

（引用の書き方をしていますが、引用というわけではないです。いい書き方が分からなかったので）

このように定義しましたが、じゃあこれが実際に僕たちがイメージするような構造となっているか、と言われると、自明ではないところだと思います。なので、次の定理を考えます。

Thm：構造定義の妥当性

集合 $A$ 上２つのツリー

$$T_1=\mathrm{Tree}(t_1), \ \ T_2=\mathrm{Tree}(t_2)$$

について、

$$T_1 \simeq T_2$$

が成り立っている。つまり、ある全単射写像 $\sigma:A \rightarrow A$ が存在して、

$$\sigma \circ t_1=t_2 \circ \sigma$$

が成り立っている。このとき、任意の $a \in A$に対し、

$$|\{ x \ | \ t_1(x)=a \}|= |\{ y \ | \ t_2(y)=\sigma(a) \}|$$

が成り立つ。

ツリーの各ノードは、
・出ていく枝は１本
・やってくる枝は？本
　となっていますが、この定理の主張は、やってくる枝の本数が「 $T_1$ のノード $a$ 」と「 $T_2$ のノード$\sigma(a)$」で一致しているということです。

以下、証明しますが、証明は超簡単です。

$$\sigma \circ t_1=t_2 \circ \sigma$$

より、

$$\forall x \in \{ x \ | \ t_1(x)=a \}, \qquad \sigma(x) \in \{ y \ | \ t_2(y)=\sigma(a) \} \\ \forall y \in \{ y \ | \ t_2(y)= \sigma(a) \}, \qquad \sigma^{-1}(y) \in \{ x \ | \ t_1(x)=a \}$$

が言えるからです。（証明終）

今回はここで終了。まだこれだけだと何もできないので、次回はさらに別の概念を考えていきます。