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

前回のまとめ

前回は、巡回列生成関数 $j_t$ が全射になる条件を見ていきました。

Thm：任意ツリーの巡回列は全射

全単射の２つの関数

$$t_o:O \rightarrow \mathbb{J} \\ t_e:E \rightarrow \mathbb{J}$$

を用いて、

$$t(x) := \left\{ \begin{align*} t_e(x) \quad & (x \in E) \\ t_o(x) \quad & (x \in O) \end{align*} \right.$$

と表せる連続関数 $t$ について、$j_t: \mathbb{J} \rightarrow \mathbb{J}$ は全射となる。

次にやりたいこと

次にやりたいことはなんでしょうか。
全射性をやったら、単射性もやりたくなりますよね。まずこれをやりましょう。

単射性

Thm：任意ツリーの巡回列は全単射

全単射の２つの関数

$$t_o:O \rightarrow \mathbb{J} \\ t_e:E \rightarrow \mathbb{J}$$

を用いて、

$$t(x) := \left\{ \begin{align*} t_e(x) \quad & (x \in E) \\ t_o(x) \quad & (x \in O) \end{align*} \right.$$

と表せる連続関数 $t$ がある。
任意の $o, e$ の並び $*$ に対し、減少集合列 $t_*^{-n}(\mathbb{J})$ は、

$$\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\forall n > N,\ \forall x, y \in t_*^{-n}(\mathbb{J}),\ \quad d(x,\ y) < \varepsilon$$

を満たすとする。
このとき、巡回列生成関数 $j_t: \mathbb{J} \rightarrow \mathbb{J}$ は全単射となる。

$\mathbf{t_*^{-n}(\mathbb{J})}$ はいつか十分に小さくなるという仮定を追加しています。
これは非常に自然な仮定だと思います。

proof.)

$j_t(a) = j_t(b)$ と仮定する。
このとき、$j_t(a)$ と一致する $o,\ e$ の並び $*$ を取れば、任意の $n \in \mathbb{N}$ に対し、

$$a,\ b \in t_*^{-n}(\mathbb{J})$$

となる。
ここで、任意に $m \in \mathbb{N}$ を取る。
$\varepsilon = 2^{-m}$ に対し、

$$\exists N \in \mathbb{N},\ a, b \in t_*^{-N-1}(\mathbb{J}),\ \quad d(a,\ b) < \varepsilon$$

よって、$a,\ b$ は少なくとも第 $m$ 項までは一致する。
$m$ は任意だったから $a=b$ となる。（証明終）

本質的には

$$t(x) = \left\{ \begin{align*} x/2 \quad & (x \in E) \\ \frac{3x-1}{2} \quad & (x \in O) \end{align*} \right.$$

でやった方法と同じになります。

次に見たいことは、逆が成り立つか？　というところです。

全単射からツリーを構成する

Thm：任意の全単射 $\phi$ に対し、対応する $t$ が存在する

巡回列空間 $\mathbb{J}$ 上において、奇数集合を $O$、偶数集合を $E$ とする。
任意の全単射写像 $\phi:\mathbb{J} \rightarrow \mathbb{J}$ に対し、$\phi(E)=E$ ならば、
２つの全単射関数

$$t_o:O \rightarrow \mathbb{J} \\ t_e:E \rightarrow \mathbb{J}$$

を用いて、

$$t(x) := \left\{ \begin{align*} t_e(x) \quad & (x \in E) \\ t_o(x) \quad & (x \in O) \end{align*} \right.$$

と表せる $t$ が存在して、巡回列生成関数 $j_t$ と $\phi$ は一致する。

証明する前に、利便性のため $\mathrm{next}$ という関数を定義しておきます。

def：基礎ツリー関数 next

関数 $\mathrm{next}: \mathbb{J} \rightarrow \mathbb{J}$ を、

$$\forall n \in \mathbb{N},\ \quad \mathrm{next}(x)_n = x_{n+1}$$

によって定義する。

proof.)

任意に全単射写像 $\phi:\mathbb{J} \rightarrow \mathbb{J}$ で、$\phi(E)=E$ となるものをとる。

$$t := \phi^{-1} \circ \mathrm{next} \circ \phi$$

によって $t$ を定義する。これが求めるものであることを示す。

$$\phi(E)=E \\ \phi(O)=O$$

並びに全単射性より、$\mathrm{next}(E)=\mathbb{J},\ \mathrm{next}(O)=\mathbb{J}$ と合わせて、

$$t(E)=\mathbb{J} \\ t(O)=\mathbb{J}$$

が言える。これが $E,\ O$ それぞれで全単射となることも同様に分かる。

ここで、$t$ による巡回列生成関数 $j_t$ を考える。
任意に $a \in \mathbb{J}$ と $i \in \mathbb{N}$ を取る。

$$\phi(t^{i-1}(a)) = \mathrm{next}^{i-1} (\phi(a))$$

である。
この等式より、$\phi(t^{i-1}(a))$ の第１項と $\phi(a)$ の第 $i$ 項は一致する。

さらに、$t^{i-1}(a)$ と $\phi(t^{i-1}(a))$ の偶奇が一致する、つまり、第１項は一致する。
よって、$t^{i-1}(a)$の第１項と $\phi(a)$ の第 $i$ 項は一致する。
これは $j_t = \phi$ のことである。（証明終）

$$t = \phi^{-1} \circ \mathrm{next} \circ \phi$$

という関係式は、実は、このシリーズで一番最初にやった式と同じです。
構造が等しいという言葉をこの式によって定義したりしました。

ここまでできたら、次の目標はこれですよね。

ループする要素を起点とする巡回列はループするか

仮説：ループする要素を起点とする巡回列はループするか

巡回列空間上で

$$t(x) = \left\{ \begin{align*} x/2 \quad & (x \in E) \\ \frac{3x-1}{2} \quad & (x \in O) \end{align*} \right.$$

と定義する。
このとき、$j_t(L) = L$ か？

なお、$L$ は次のように定義することにします。

def：ループする要素からなる集合 L

$L \subset \mathbb{J}$ をループする要素からなる集合、つまり、

$$L := \{ \ x \in \mathbb{J} \ | \ \exists n \neq m \in \mathbb{N},\ \mathrm{next}^n(x)=\mathrm{next}^m(x) \ \}$$

と定義する。

この仮説が１つのゴールだと思っています。
なぜなら、これが分かれば、コラッツ予想において、発散するものは存在しないということが言えるからです。

ただやはりというか、まだまだ手の出しどころが難しい問題のようです。

今までやってきこととしては、$j_t$ が全単射だと言えれば、なんか全体の兼ね合いからうまく言えるんじゃないかと期待していましたが、全然そんなことはないようですね。

また、$t_*^{n}(x)=x$ ならば $x \in L$ より、$L \subset j_t(L)$ は言えるので、じゃあ反対を言えばいいと思い... $\phi$ から $t$ の構成ができたらいいんじゃないか？　とも思いましたが、これもそんな簡単な話ではなかったようです。

う～ん、どうするか。。。

まず、$L$ という概念について、捉え方は２通りあります。
定義は、

$$\mathrm{next}^n(x)=\mathrm{next}^m(x)$$

という見方で定義しました。

一方で、
加法の単位元 $0,\ 0,\ 0,\ 0,\ ...$ と、乗法の単位元 $1,\ 0,\ 0,\ 0,\ ...$ から四則演算をやっていって作られる空間という見方もできます。

一応、証明しておきます。

Thm：ループ集合は奇数による除法を除く四則によって構築できる（前半）

任意の $x \in L$ に対し、
加法の単位元と乗法の単位元を用いた有限回の四則演算によって、$x$ を表現することができる。

proof.)

まず、加法の単位元と乗法の単位元から和と差によって構成できる整数に当たるものについては、有限回で構成できる。
基礎ツリーは、

$$\mathrm{next}(x) = \left\{ \begin{align*} x/2 \quad & (x \in E) \\ \frac{x-1}{2} \quad & (x \in O) \end{align*} \right.$$

と書ける。
$x \in L$ に対し、$m > n$ を用いて、

$$\mathrm{next}^n(x)=\mathrm{next}^m(x)$$

とすると、$y = \mathrm{next}^n(x)$ は、

$$y=\mathrm{next}^{m-n}(y)$$

を満たす。よって、分配法則より、巡回列空間上のある整数 $a \in \mathbb{J}$ を用いて、

$$y=\frac{y-a}{2^{m-n}}$$

と書ける。よって、

$$y = \frac{-a}{2^{m-n}-1}$$

となり、$y$ は有限回の四則演算によって構築できる。
ここで、

$$\begin{align*} \mathrm{next}_e^{-1}(x) &= 2 \cdot x\\ \mathrm{next}_o^{-1}(x) &= 2 \cdot x + 1 \end{align*}$$

であり、適切な $o,\ e$ の並び $*$ を取れば、

$$x = \mathrm{next}_*^{-n}(y)$$

となり、これも有限回の四則演算によって構築できる。（証明終）

この逆も証明しなければなりません。

Thm：ループ集合は四則によって構築できる（後半）

加法の単位元と乗法の単位元を用いた有限回の四則演算によって、$x$ を表現することができるとする。
このとき、$x \in L$ である。

これを見るには、ループするもの同士に和や積を作用させたときにループすることを示せばよさそうです。
ただ、積の方が...意外と難問ですか。

ちょっと考え方を変えなければ解けないようです。

proof.)

加法の単位元と乗法の単位元を用いた有限回の四則演算によって表現することができるもの全体の集合を $Q$ とする。
整数÷奇数の形で表せられる有理数集合を $\mathbb{Q}_o$ とする。

このとき、$\mathbb{Q}_o$ への自然な全単射が構成できる。
$\mathrm{next}$ については、$\mathbb{Q}_o$ 上でも、

$$\mathrm{next}(x) = \left\{ \begin{align*} x/2 \quad & (x \in E) \\ \frac{x-1}{2} \quad & (x \in O) \end{align*} \right.$$

と書ける。
よって、任意の $x \in \mathbb{Q}_o$ についてループする。（第07回参照）
一対一に対応するから、任意の $x \in Q$ についても成り立つ。（証明終（？））

$|x| > 1$ ならば、$|\mathrm{next}(x)|$ は $|x|$ よりも小さくなることを用いています

少し面白いのは、$L$ 上の要素同士の積が $L$ の中に入ることを示すのが、直接的なやり方ではないということです。
実際、示すためには今のようなツリー的な発想が必要みたいです。

それと、細かい話をすると、今の議論がちゃんと論理的な議論だったかは微妙なところがあります。
少し精査してみます。

Lの二面性を精査する

今やった議論を既存の実数や有理数という概念を使わずにやってみます。

まずは $Q$ を定義します。

def：有理巡回列集合 $Q$

$\mathbb{J}$ 上において、加法の単位元 $0$ と乗法の単位元 $1$ を用いた有限回の四則演算によって表現することができるもの全体の集合を $Q \subset \mathbb{J}$ とする。

そして、$Q を整数÷奇数で表せることを示します。
そのために、整数×整数は整数であることを示す必要があります。

def：巡回列空間上の整数

$\mathbb{J}$ 上において、加法の単位元 $0$ と乗法の単位元 $1$ を用いた有限回の和・差によって表現することができるもの全体の集合を $Z \subset \mathbb{J}$ とする。

整数同士の和が整数なのは明らかです。

thm：整数同士の積は整数である

$$2 = 1 + 1 = 0,\ 1,\ 0,\ 0,\ 0,\ ...$$

について、任意の $x \in \mathbb{J}$ に対し、

$$x + x = 2 \cdot x$$

は明らか。
ここで乗法の単位元 $1$ と和のみで作れる全体の集合を自然数 $N \subset \mathbb{J}$ と定義する。
任意の自然数 $a \in N$について、

$$a = \sum_{i=0}^n 2^{a_i}$$

と表現できる。
任意の整数 $b \in Z$ について、

$$a \cdot b = \sum_{i=0}^n (2^{a_i} \cdot b)$$

となる。これは整数である。また、負の整数については、

$$(-a) \cdot b = -(a \cdot b)$$

とすれば整数になることが分かる。（証明終）

thm：$Q$ は整数÷奇数である

$$Q = \{ \ m / n \ | \ m \in Z,\ n \in N \cap O \ \}$$

proof.)

$Q$ の任意の要素が有限回の四則演算で表せることは明らか。
よって、$Q$ の要素を任意に取り出して、四則演算を行っても $Q$ に含まれることを示せばよい。

• 和

$$\frac{m_1}{n_1}+\frac{m_2}{n_2}=\frac{m_1 n_2 + m_2 n_1}{n_1 n_2}$$

奇数×奇数は奇数なので、これは $Q$ の要素になる。
差も同様。

• 積

$$\frac{m_1}{n_1} \cdot \frac{m_2}{n_2}=\frac{m_1 \cdot m_2}{n_1 \cdot n_2}$$

この等式の成立は可換と結合法則による。
整数×整数は整数なので、これは $Q$ の要素である。

-除法（奇数）

$$\frac{m_1}{n_1} / \frac{m_2}{n_2}=\frac{m_1 \cdot n_2}{n_1 \cdot m_2}$$

奇数による除法を考えているので、$m_2$ も奇数である。$n_1 \cdot m_2$ が負になるときは、分子分母に $-1$ 倍すればよい。
よってこれは $Q$ の要素になる。

-除法（２）

$2$ による除法については、$m$ が偶数である必要がある。このとき、

$$\frac{m}{n} / 2 = \frac{m/2}{n}$$

となって、これも $Q$ の要素である。（証明終）

thm：Q上の大小関係

任意の $q_1,\ q_2 \in Q$ について、

$$q_1 - q_2 = \frac{m}{n}$$

と表現できる。（$m \in Z,\ n \in N \cap O$）
このとき、$m,\ n$ は一意ではないが、どのような表現を選んでも、$m$ が $N$ に含まれるか否かは $q_1,\ q_2$ によってのみ決定される。
よって、

$$q_1 > q_2 \ :\Leftrightarrow \ m \in N$$

と定義できる。
これは $Q$ 上の全順序となるか？

proof.)

$a > b,\ b > c \ \Rightarrow \ a>c$ さえ見ればよい。

$$a - b = \frac{m_1}{n_1},\ b - c = \frac{m_2}{n_2}$$

とする。

$$a - c = (a - b) + (b - c) = \frac{m_1 n_2 + m_2 n_1}{n_1 n_2}$$

$m_1 n_2 + m_2 n_1$ は $N$ の要素である。（証明終）

準備ができたので、解いていきます。

Thm：ループ集合は四則によって構築できる（後半）

$$x \in Q \Rightarrow x \in L$$

proof.)

$\mathrm{next}$ について、

$$\mathrm{next}(x) = \left\{ \begin{align*} x/2 \quad & (x \in E) \\ \frac{x-1}{2} \quad & (x \in O) \end{align*} \right.$$

である。
$a \in Q$ について、

$$a = \frac{m}{n}$$

と表せるとする。（$m \in Z,\ n \in N \cap O$）
$整数 / n$ と表せる要素について、$\mathrm{next}$ を作用させても、$整数 / n$ となる。

ここで、
$|x| > 1$ ならば、$|\mathrm{next}(x)| < |x|$

であり、
$整数 / n$ と表せられるものについて、 $|\mathrm{next}(x)| \leq 1$ となる $x$ は有限である。よって、鳩ノ巣の原理より、$n,\ m$ が存在して、

$$\mathrm{next}^n(a) = \mathrm{next}^m(a)$$

となる。
よって、$a \in L$ となる。（証明終）

とりあえず、穴はなかったですね。
今回は、ループ集合 $L$ が $Q$ という見方もできるということを見ました。

次回はどう進めていくのか、ちょっと全く分かっていませんが、今回はこの辺りで終わりにしようと思います。では～