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

前回のまとめ

前回見たのは２点です。

１．ツリー $T_1$と写像 $t_1:A \rightarrow A$ を対応させるということ
２．ツリー構造が等しいということの定義。全単射写像 $\sigma:A \rightarrow A$を用いて、

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

を満たすとき構造が等しいと定義しました。

次に何をするか？

正直、今書いている段階でもどうしたらいいか分からないところではあるのですが、現状、これだけでは何もできないので新しい概念を持ち込みたいところですよね。
　さてどうするか。
　こういうのはどうでしょう？
　上の定義を見ると、$A \rightarrow A$ の写像全体をツリーと対応させている一方で、$\sigma$を全単射としているのは少し条件が強すぎるような気もします。
　なのでもっと広く、一般の $f:A \rightarrow A$ について、

$$f \circ t_1=t_2 \circ f$$

となるような状況について、考察してみるのも面白いかもしれません。

例えば、こんな感じの $T_1, \ T_2$ について、$f$ は存在するのでしょうか。

T1

1───2─┬─3
└───┘ └─4

T2

1───2───3───4
└───┘ 

この場合、（総当たり的にやると）答えは５つあるようですが、その内の１つを挙げておきます：

$$f= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 3 \end{pmatrix} \$$

これが条件を満たすことは簡単でしょう。
（※こういう書き方は置換の場合にしかないかもしれませんが、まあいいでしょう）

では、$T_1,\ T_2$ がこうだったら、どうなるでしょう？

T1

1───2───3───4
└───────┘ 

$$t_1= \begin{pmatrix} 1 & 2 & 3 & 4\\ 3 & 1 & 2 & 3 \end{pmatrix} \$$

T2

1───2───3───4
└───┘

$$t_2= \begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 1 & 2 & 3 \end{pmatrix} \$$

これは意外と難問のようですね。
　やってみると、むむっ？　意外と見つからないぞ！？　ってなりました（笑）
　とりあえず、コンピューターの力を借りて、総当たりしてみましょう。

ソースコード

python

t_1 = [3, 1, 2, 3]
t_2 = [2, 1, 2, 3]

def check(f):
    for i in range(4):
        if(f[t_1[i]-1] - t_2[f[i]-1]):
            return 0
    return 1

for i0 in range(1, 5):
    for i1 in range(1, 5):
        for i2 in range(1, 5):
            for i3 in range(1, 5):
                if(check([i0, i1, i2, i3])):
                    print([i0, i1, i2, i3])

ななんと！　答えは「なし！」という結果に...

これの結果は、予想外でした。
　だって、関数$f$に制約はないのだから、１つくらいはあるんじゃないか。そう思ってました。しかし実際は、１つもないらしい。

もう少し状況を調べてみましょう。

T1

1───2───3───4
└───────┘ 

T2

1─┐ 2───3───4
└─┘ └───┘

こんな状況だったら、答えは

$$f= \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 1 & 1 & 1 \end{pmatrix} \$$

の１つ。

T1

1─┐ 2───3───4
└─┘ └───┘

T2

1───2───3───4
└───────┘

上の状況だったら、答えはなし、となるようです。

その他、いろいろな条件で調査してみると、次のような概念と仮説が生まれます：

Def：ループ長さ

集合 $A$ 上のツリー

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

について、ループする要素からなる集合

$$K = \{ \ x \in A \ | \ \exists n \in \mathbb{N} , \quad x = t^{n}(x) \ \}$$

をとる。このとき、次の集合

$$L = \{ \ \min \{ n \in \mathbb{N} \ | \ x = t^{n}(x) \} \ | \ \ x \in K \} \ \$$

をループ長さ集合といい、その元をループ長さと言う。

少し定義はごちゃついてますが、概念はシンプルです。

T

1─┐ 2───3───4
└─┘ └───┘

なら、

$$L = \{ \ 1, \ 2 \ \}$$

となりますし、

T

1───2───3───4
└───────────┘

なら、

$$L = \{ \ 4 \ \}$$

となるということです。

仮説：f の存在（必要条件）

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

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

について、ループ長さ集合をそれぞれ $L_1, \ L_2$ とする。

$$\forall l_1 \in L_1, \ \exists l_2 \in L_2, \qquad l_2はl_1の約数$$

が成り立つならば、

$$\exists f:A \rightarrow A, \qquad f \circ t_1=t_2 \circ f$$

が成り立つ。

$T_1$ の任意のループ長さに対し、その約数となるような $T_2$ のループ長さが存在するならば、 $f$ が存在することを主張しています。

例えば、以下のような時は、

T1

1───2───3───4───5───6
└───────────────────┘ 

T2

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

ループ長さは、

$$L_1 = \{ 6 \}, \quad L_2 = \{ 3 \}$$

となるので、条件を満たします。
　そして実際、総当たりすると３つの $f$ が得られます：

$$f= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 2 & 3 & 1 & 2 & 3 \end{pmatrix} , \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 1 & 2 & 3 & 1 \end{pmatrix} , \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 2 & 3 & 1 & 2 \end{pmatrix} \ \$$

ソースコード

python

t_1 = [6, 1, 2, 3, 4, 5]
t_2 = [3, 1, 2, 3, 4, 3]

def check(f):
    for i in range(6):
        if(f[t_1[i]-1] - t_2[f[i]-1]):
            return 0
    return 1

for i0 in range(1, 7):
    for i1 in range(1, 7):
        for i2 in range(1, 7):
            for i3 in range(1, 7):
                for i4 in range(1, 7):
                    for i5 in range(1, 7):
                        if(check([i0, i1, i2, i3, i4, i5])):
                            print([i0, i1, i2, i3, i4, i5])

そして同時に、これは仮説を証明する上でコアとなるような発想を与えてくれています。

例えば、２つのツリーのループする部分が以下のようだったとしましょう。

T1の一部

1───2───3───4───5───6
└───────────────────┘ 

T2の一部

7───8───9
└───────┘

まず $f(1)$ が、$7, \ 8, \ 9$ のどこへ行くかを固定します。その後、

$$f \circ t_1=t_2 \circ f \$$

を用いて、他の行先を決定します。つまり、例えば $f(1)=7$ とした場合、

$$f(6) = f(t_1(1)) = t_2(f(1))=t_2(7)=9 \\ f(5) = f(t_1(6)) = t_2(f(6))=t_2(9)=8 \\ f(4) = f(t_1(5)) = t_2(f(5))=t_2(8)=7 \\ f(3) = f(t_1(4)) = t_2(f(4))=t_2(7)=9 \\ f(2) = f(t_1(3)) = t_2(f(3))=t_2(9)=8 \\ f(1) = f(t_1(2)) = t_2(f(2))=t_2(8)=7$$

となって、すべて決定されます。また $1$ に戻ってきた時、ちゃんと $7$ になっていますね。

では、次のような場合はどうでしょうか。

T1の一部

1───2───3───4───5───6───11───12───13───...
└───────────────────┘ 

T2の一部

7───8───9
└───────┘

$t_1(11)=6$ なので、逆順を辿る必要があります。
　そして、最もシンプルな発想は、同じく $t_1(1)=6$ となるノード $1$ と合わせてしまうということです。つまり、

$$f(11)=f(1)=7$$

とするということです。
　一般化のため、これを $1$ という言葉抜きで表現してみましょう。イメージとしては、

$$f \circ t_1=t_2 \circ f \$$

の両辺に右から $t_1^{-1}$、左から $t_2^{-1}$ をかけると、

$$f \circ t_1^{-1}=t_2^{-1} \circ f$$

となるので、これを使うイメージです。
（※数式はイメージです）

$$f(11) = f(t_1^{-1}(6))= t_2^{-1}(f(6))=t_2^{-1}(9)=7$$

こんなイメージ。
　正確に書くとこうなります：

$T_2$ のループしている要素の集合$\{ 7, \ 8, \ 9 \}$上で $t_2$は全単射。よってこの上で、逆関数$t_2^{-1}$を定義できる。
ここで $t_1(x)= 6$となる任意の $x$に対し、

$$f(x)=t_2^{-1}(f(6))$$

と定める。

では実際に、仮説を証明してみましょう。
　このような発想でやる場合、$A$は有限集合ではないとダメっぽいので、有限集合という仮定のもと証明してみます。無限集合に対し仮説が成り立つかは、後で考えましょう。

proof.)

$T_1$のループ長さ集合 $L_1$とそのそれぞれの元に対応するループ要素集合 $K_i^{1}$は次のように書ける：

$$L_1 = \{l_1^{1}, \ ... \ , l_n^{1} \} \\ K_i^{1} = \{a_{i, \ 1}, \ ... \ , a_{i, \ l_i^{1}} \}$$

このとき、各 $l_i^{1}$ に対し、$l_i^{2} \in L_2$ が存在して、$l_i^{2}$ は $l_i^{1}$ の約数となるとできる。

ここで、各 $l_i^{2}$ に対応するループ要素集合 $K_i^{2}$ は次のように書ける：

$$K_i^{2} = \{b_{i, \ 1}, \ ... \ , b_{i, \ l_i^{2}} \}$$

$t_2$は集合 $\cup_i K_i^{2}$上で全単射だから、この上で、逆関数$t_2^{-1}$を定義できる。
ここで $f$を次の２つにより定義する：

$$\begin{align*} \mathrm{1.} & \qquad \forall i, \quad f(a_{i, \ 1})=b_{i, \ 1} \\ \mathrm{2.} & \qquad t_1(x)=y \quad \Rightarrow \quad f(x)=t_2^{-1}(f(y)) \end{align*}$$

これがwell-definedであることは、ループしない要素に対しては明らか。ループする要素についても、$l_i^{2}$は $l_i^{1}$の約数だから整合性は取れている。
また、$f$の像は集合 $\cup_i K_i^{2}$ 上にある。
最後、

$$f \circ t_1=t_2 \circ f$$

を見る。

$$t_1(x)=y, \ f(x)=t_2^{-1}(f(y))$$

が成り立っているとき、

$$f(t_1(x))=f(y)=t_2(t_2^{-1}(f(y)))=t_2(f(x))$$

が成立する。
$f$の定義より、上式は任意の $x \in A$に対して成立する。（証明終）

となんとか証明できました。

これ、我ながら、なかなか筋の良い展開な気がしています。というのも、コラッツ予想は（発散する列がなければ）ループする要素があるかどうかの議論なので、なんとなくおぼろげですが近づけた感じはありますよね。

そして、さらにこの定理を発展させる上で、気になるのは以下の２点です：
・無限に対しても成り立つか？
・逆も成り立つか？
　実は、逆については意外と簡単のようなのでやってみましょう。

Thm：f の存在（必要十分条件）

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

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

について、ループ長さ集合をそれぞれ $L_1, \ L_2$ とする。
次の $(\mathrm{i}), \ (\mathrm{ii})$は同値である。

$$\begin{align*} & (\mathrm{i}) \qquad \forall l_1 \in L_1, \ \exists l_2 \in L_2, \qquad l_2はl_1の約数 \\ & (\mathrm{ii}) \qquad \exists f:A \rightarrow A, \qquad f \circ t_1=t_2 \circ f \quad \end{align*}$$

proof.)

$(\mathrm{i})\ \Rightarrow \ (\mathrm{ii})$ は既に示したので、$(\mathrm{i})\ \Leftarrow \ (\mathrm{ii})$ を示す。
任意に $l_1 \in L_1$を取り、対応するループ集合の元の１つを $a$とする。

$$a_i = t_1^{i}(a)$$

によって $a_i$を定義すると、$i=1, \ ... \ , \ l_1$を考えればよい。さらに、

$$b_i = f(a_i)$$

とする。このとき、任意の $i$に対して、

$$t_2(b_i)=t_2(f(a_i))=f(t_1(a_i))=f(a_{i+1})=b_{i+1}$$

が成り立つ。この等式を$i=1, \ ... \ , \ l_1$に対して考えれば、

$$b_1 = t_1^{l_1}(b_1)$$

が言える、これで十分性は示された。（証明終）

みんな大好き同値が言えました。
　ってことは今回は終了です。
　次回は...どうするんでしょうかね？　う～ん、どうするんでしょう？
　分かりませんが、今回はおしまい！　ではでは。