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

前回のまとめ

前回はループ長さ集合の定義と、次の定理を証明しました：

Def：ループ長さ

集合 $AA$ 上のツリー

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

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

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

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

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

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

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

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

$$T1=Tree(t1),T2=Tree(t2) T_1=\mathrm{Tree}(t_1), \quad T_2=\mathrm{Tree}(t_2) \ \ \$$

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

$$(i)∀l1∈L1, ∃l2∈L2,l2はl1の約数(ii)∃f:A→A,f∘t1=t2∘f \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*}$$

まずは前回の続き

抽象的な話に入る前に、もう少し土台作りをやりましょう。
　なんと上記のThmは可算集合でも成立するようですね。

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

可算集合 $AA$ 上の２つのツリー

$$T1=Tree(t1),T2=Tree(t2) T_1=\mathrm{Tree}(t_1), \quad T_2=\mathrm{Tree}(t_2) \ \ \$$

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

$$(i)∀l1∈L1, ∃l2∈L2,l2はl1の約数(ii)∃f:A→A,f∘t1=t2∘f \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.）

$(i) ⇐ (ii)(\mathrm{i})\ \Leftarrow \ (\mathrm{ii})$ は有限のときと同様にすればよい。問題は $(i) ⇒ (ii)(\mathrm{i})\ \Rightarrow \ (\mathrm{ii})$ である。
まず有限の時と同様に $ff$ を定義する：

$$1.∀i,f(ai, 1)=bi, 12.t1(x)=y⇒f(x)=t2−1(f(y)) \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*}$$

重要なのは、この定義の場合、定義域が $AA$ 全体を覆っているとは限らないところである。
ある未定義の $a∈Aa \in A$ が１つあったら、

$$1.∀i,f(a)=b1, 12.t1(x)=y⇒f(x)=t2−1(f(y))3.t1(x)=y⇒f(y)=t2(f(x)) \begin{align*} \mathrm{1.} & \qquad \forall i, \quad f(a)=b_{1, \ 1} \\ \mathrm{2.} & \qquad t_1(x)=y \quad \Rightarrow \quad f(x)=t_2^{-1}(f(y)) \\ \mathrm{3.} & \qquad t_1(x)=y \quad \Rightarrow \quad f(y)=t_2(f(x)) \end{align*}$$

によって、定義域を拡張する。
まだ、未定義の $a∈Aa \in A$ が残っていれば、同様の方法で定義域を拡張し、以下無限回繰り返す。
$AA$ は可算なので、これで $ff$ は定義された。
またこの時、

$$f∘t1=t2∘f f \circ t_1=t_2 \circ f$$

は成立する。（証明終）

可算なら問題なく成立するようですね。
土台作りは一旦ここまで。また、超抽象的で感覚的なお話になってきます。

こっからどうするか

さて、これから何をするか。まずは状況整理しましょう。

今までの流れ

コラッツ予想の肝は「ツリー」だと筆者は見ました。
なぜなら、それ以外に難しい発想をしていないと思うからです。３倍して１足すのも、２で割るのも、奇偶判定も、さほど難しいことではありません。コラッツ予想を未解決問題にまで難しくしている本質は、「ツリー」という発想にあるのではないかと考えているわけです。
まず初めにやったことは、ツリー上に「構造が等しい」という概念を導入したことです。
そこで、全単射写像 $σ\sigma$ と

$$σ∘t1=t2∘σ \sigma \circ t_1=t_2 \circ \sigma$$

という式が出てきたわけです。
次にやったことは、この上式について一般の関数 $ff$ に対して成り立つ場合を考察しました。

$$f∘t1=t2∘f f \circ t_1=t_2 \circ f$$

流れで言うと、$ff$ と一般に広げられたのですから、$Tree(f)\mathrm{Tree}(f)$ を考察するのは自然でしょう。
また全体的なイメージとして、やりたくなることは、
・$∀∃∀\forall \exist \forall$のような並びの概念の導入する
・$max⁡min⁡,min⁡max⁡\max \min, \min \max$のような並びの概念を導入する
・この新しいツリー$Tree(f)\mathrm{Tree}(f)$全体を１点のノードと見なし、ツリー上のツリーを考えたくなるのも普通だと思います
　ただ、これらの概念を自然に定義するための「道」がないというのが実情です。

$Tree(f)\mathrm{Tree}(f)$を考察したい

ではとりあえず、$Tree(f)\mathrm{Tree}(f)$を考察しましょう。
しかし、これは意外と具体的に何をやるのか難しいです。というのも、今まで見てきた$t1,t2t_1, t_2$と何が違うんだ、という気もします。やはり、起点としては、

$$f∘t1=t2∘f f \circ t_1=t_2 \circ f$$

をこねくり回すしかないところでしょうか。
例えば、もしある関数$ϕ:A→A\phi:A \rightarrow A$が存在して、

$$t2=t1∘ϕ t_2 = t_1 \circ \phi$$

が成立するなら、

$$t1∘(ϕ∘f)=f∘t1 t_1 \circ (\phi \circ f) = f \circ t_1$$

とはなりますが。僕たち（私たち）入れ替わってる！？　状態ですが、発展性があるかどうかは微妙です。

他にもやれることはいくつか考えられますが、どれもどうやって発展させていくのかが難しい気がしています：

max-minの概念導入

T

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

というツリーに対して、ループするまでが一番長いのは、

$$4→3→2→1→2 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2$$

です。このツリーに対し、ループするまでに最大４回かかるという意味で、「４」を対応させることを考えます。
これは定式化すると、関数 $t:A→At: A \rightarrow A$ に対して、

$$max⁡x∈Amin⁡{n∈N ∣ ∃i<n, tn(x)=ti(x)} \max_{x \in A} \min \{n \in \mathbb{N} \ | \ \exists i<n, \ t^n(x)=t^i(x) \}$$

となります。しかし、これをどう使っていくのかは難しいところです。

素因数分解的な概念（ちょっと違う？）

今までの定理で出現した概念として次のようなものがありました：

$$(i)∀l1∈L1, ∃l2∈L2,l2はl1の約数 (\mathrm{i}) \qquad \forall l_1 \in L_1, \ \exists l_2 \in L_2, \qquad l_2はl_1の約数$$

この概念を直接使うことを考えた場合、次のようなツリーを考えたくなるでしょう：

T2

1───2  3───4───5  6───7───8───9───10 　...
└───┘  └───────┘  └───────────────┘

ループ長さが素数列 $2, 3, 5, 7, 11, ...2,\ 3,\ 5,\ 7,\ 11,\ ...$ となるようなツリーを $Tree(t2)\mathrm{Tree}(t_2)$として考えれば、任意のツリー $Tree(t1)\mathrm{Tree}(t_1)$ に対して、

$$f∘t1=t2∘f f \circ t_1=t_2 \circ f$$

となる $ff$ が存在します。だから何だ感はありますが...

偶奇という概念を導入しよう

ではどうするか？
タイトルで言ってしまってますが、偶奇性もとりあえずいれとけ、みたいな話はある気がしています。コラッツ予想とは、

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

なる $tt$ によって構成されるツリーに関する話題です。偶奇はコラッツ予想と切っても切れない関係と言いますか、概念として非常に重要な位置を占めるように見えます。なので、そもそも偶奇を含めてツリーを考えていくべきだったのかもしれません。
なお、偶数と奇数に限らず２つに分ければいい、と抽象化しておきます。

「Eから見た構造」という概念を導入しよう

集合 $AA$ を部分集合 $E⊂AE \subset A$ で分割することを考えます。
$O=A∖EO = A \setminus E$ とすれば、$A=E+OA = E + O$ となります。この状況で、構造が等しいという概念はどうなるでしょうか。

$$A={e1, e2, e3, o1, o2, o3}E={e1, e2, e3}O={o1, o2, o3} \begin{align*} A &= \{e_1,\ e_2,\ e_3,\ o_1,\ o_2,\ o_3 \} \\ E &= \{e_1,\ e_2,\ e_3 \} \\ O &= \{o_1,\ o_2,\ o_3 \} \end{align*}$$

$T1T_1$ ：

$T2T_2$ ：

こんな感じで、それぞれのノードが $E, OE,\ O$ のどっちに所属しているのかということを含めて、構造の一致を考えるのが一番自然でしょう。

こんなイメージから、

$$σ(t1(o2))=σ(e1)=e3=t2(o1)=t2(σ(o2)) \sigma(t_1(o_2))=\sigma(e_1)=e_3=t_2(o_1)=t_2(\sigma(o_2))$$

とやるのは、前の議論と同じ。変わるところは $σ\sigma$ がただの全単射写像ではないというところです。

$$σ(oi)=ojσ(ei)=ej \sigma(o_i) = o_j \\ \sigma(e_i) =e_j$$

のように、$σ\sigma$ によって $O,EO, E$ 集合のどちらかに所属するのかと言うのは変わらないはずなので、$EE$ 上の全単射 $σe\sigma_e$ と $OO$ 上の全単射 $σo\sigma_o$ を用いて以下のように表せる必要があります。

$$σ(x)={σe(x)(x∈E)σo(x)(x∈O) \sigma(x) = \left\{ \begin{array}{ll} \sigma_e(x) & (x \in E) \\ \sigma_o(x) & (x \in O) \end{array} \right.$$

よって、新しい構造はこうなります：

Def：ツリーの構造

集合 $AA$ 上に２つのツリー $Tree(t1), Tree(t2)\mathrm{Tree}(t_1),\ \mathrm{Tree}(t_2)$ がある。また $E⊂AE \subset A$ とする。
このとき、ある２つの全単射写像 $σe:E→E, σo:A∖E→A∖E\sigma_e:E \rightarrow E,\ \sigma_o:A \setminus E \rightarrow A \setminus E$が存在して、

$$σ(x):={σe(x)(x∈E)σo(x)(x∈A∖E)σ∘t1=t2∘σ \begin{align*} & \sigma(x) := \left\{ \begin{array}{ll} \sigma_e(x) & (x \in E) \\ \sigma_o(x) & (x \in A \setminus E) \end{array} \right. \\ \\ & \sigma \circ t_1=t_2 \circ \sigma \end{align*}$$

が成り立つとき、$T1T_1$ と $T2T_2$ の $EE$ から見た構造は等しいという。

fの一般化

さらに、今までの議論展開と同様のことをしていきましょう。
つまり、

$$f(x):={fe(x)(x∈E)fo(x)(x∈A∖E)f∘t1=t2∘f \begin{align*} & f(x) := \left\{ \begin{array}{ll} f_e(x) & (x \in E) \\ f_o(x) & (x \in A \setminus E) \end{array} \right. \\ \\ & f \circ t_1=t_2 \circ f \end{align*}$$

となるような一般の関数 $fe:E→E, fo:A∖E→A∖Ef_e:E \rightarrow E,\ f_o:A \setminus E \rightarrow A \setminus E$ が存在する条件を考えたいということです。
例えば次のような２つのツリーに対して考えてみましょう。

$T1T_1$ ：

$T2T_2$ ：

パソコンの力を借りると、答えはただ１つあることが分かります。

$$f=(e1e2o1o2e1e1o1o1) f= \begin{pmatrix} e_1 & e_2 & o_1 & o_2 \\ e_1 & e_1 & o_1 & o_1 \end{pmatrix} \$$

ソースコード

python

e1 = 0
e2 = 1
o1 = 2
o2 = 3
A_name = ['e1', 'e2', 'o1', 'o2']
A = [e1, e2, o1, o2]
t1 = [o1, o2, e1, e1]
t2 = [o1, e1, e1, e2]

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

for ie1 in range(2):
    for ie2 in range(2):
        for io1 in range(2, 4):
            for io2 in range(2, 4):
                if(check([ie1, ie2, io1, io2])):
                    print(A_name[ie1], A_name[ie2], A_name[io1], A_name[io2])

では次のようなものだったらどうでしょうか。

$T1T_1$ ：

$T2T_2$ ：

これは解なしのようです。
では次は...

$T1T_1$ ：

$T2T_2$ ：

これは解が１つあります。

$$f=(e1e2o1o2e1e2o1o1) f= \begin{pmatrix} e_1 & e_2 & o_1 & o_2 \\ e_1 & e_2 & o_1 & o_1 \end{pmatrix} \$$

では次は...

$T1T_1$ ：

$T2T_2$ ：

これは最初の例の $T1,T2T_1, T_2$ を逆にしたものですが、どうやら解なしのようですね。

なんとなく条件は分かってきているでしょう。
しかし、スッキリとして表現を見つけられるでしょうか？
今までの約数的な発想を使おうとすると、結構ごちゃごちゃする気がします。

なので次のような新しい概念を中心に考えてみてはどうでしょうか：

Def：巡回列

集合 $AA$ 上にツリー $Tree(t)\mathrm{Tree}(t)$ がある。また $E⊂AE \subset A$とその定義関数を

$$χE(x)={1(x∈E)0(x∈A∖E) \chi_E(x) = \left\{ \begin{array}{ll} 1 & (x \in E) \\ 0 & (x \in A \setminus E) \end{array} \right.$$

とする。このとき、$a∈Aa \in A$ に対し、次の数列

$$χE(a), χE(t(a)), χE(t2(a)), χE(t3(a)), ... \chi_E(a),\ \chi_E(t(a)),\ \chi_E(t^2(a)),\ \chi_E(t^3(a)),\ ...$$

を $aa$ を起点とする $EE$ についての巡回列という。

巡回列という言葉があるのかは知りませんが、こんな定義をしてみました。

例えば、
$TT$ ：

について、$o2o_2$は、

$$o2→e2→e1→o1→e1→o1→... o_2 \rightarrow e_2 \rightarrow e_1 \rightarrow o_1 \rightarrow e_1 \rightarrow o_1 \rightarrow ...$$

のように推移していくので、$o2o_2$ を起点をする巡回列は、

$$0, 1, 1, 0, 1, 0, ... 0,\ 1,\ 1,\ 0,\ 1,\ 0,\ ...$$

となるということです。
今回はこれで終了。次回はこの新しい概念を使ってどこまで行けるかというゲームになりそうですね。では。