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

前回のまとめ

$0,\ 1$ からなる数列全体の集合（本記事では巡回列空間と呼んでいるもの）について、和、積を定義し、いろいろな性質があることを見ました。

Def：巡回列空間

$0$ か $1$ からなる数列全体の集合を巡回列空間 $\mathbb{J}$ とする。 つまり、

$$\mathbb{J} = \{ \{ a_i \}_{i \in \mathbb{N}} \ | \ \forall i,\ \ a_i \in \{ 0,\ 1 \} \}$$

Def：巡回列空間における和

巡回列 $\{ a_i \} ,\ \{ b_i \} \in \mathbb{J}$ に対し、その和 $\{ c_i \} \in \mathbb{J}$ を次のように定義する：

繰り上がり計算のため、数列 $\{ d_i \}_{i \geq 0}$ を考えて、

$$\begin{align*} (\mathrm{I}) & \qquad d_0 = 0 \\ (\mathrm{II}) & \qquad 任意の i \in \mathbb{N} に対し、 a_i+b_i+d_{i-1} を 2 で割った商を d_i 、余りを c_i とする \end{align*}$$

Def：巡回列空間における積

巡回列 $a ,\ b \in \mathbb{J}$ に対し、その積 $a \cdot b \in \mathbb{J}$ を次のように定義する：

繰り上がり計算のため、数列 $\{ d_i \}_{i \geq 0}$ を考えて、

$$\begin{align*} (\mathrm{I}) & \qquad d_0 = 0 \\ (\mathrm{II}) & \qquad 任意の i \in \mathbb{N} に対し、\\ & \sum_{1 \leq k \leq i} a_k b_{i+1-k}+d_{i-1} を 2 で割った商を d_i 、余りを (a \cdot b)_i とする \end{align*}$$

によって定義する。

Thm：巡回列空間は環である

巡回列空間 $\mathbb{J}$ は環である：

• $\mathbb{J}$ は加法について可換群である

• 乗法について単位元の存在

$$\exists 1 \in \mathbb{J},\ \forall a \in \mathbb{J}, \qquad a \cdot 1=1 \cdot a=a$$

• 乗法について結合法則

$$\forall a,\ b,\ c \in \mathbb{J}, \qquad (a \cdot b) \cdot c=a \cdot (b \cdot c)$$

• 分配法則

$$\begin{align*} \forall a,\ b,\ c &\in \mathbb{J}, \\ &(a+b) \cdot c= a \cdot c+b \cdot c, \quad a \cdot (b+c)= a \cdot b + a \cdot c \end{align*}$$

さらに、奇数と偶数についての性質も少しだけ見ました。

Def：巡回列空間上の奇数、偶数

$\mathbb{J}$ 上における奇数集合 $O$ と偶数集合 $E$ を次のように定める

$$O:=\{ a \in \mathbb{J} \ |\ a_1 = 1\} \\ E:=\{ a \in \mathbb{J} \ |\ a_1 = 0\}$$

このとき、$O,\ E$ に含まれる要素をそれぞれ奇数、偶数と言う。

Thm：奇数を偶数で割れない

任意に奇数 $a$ と偶数 $b$ を取る。

$$\forall c \in \mathbb{J},\ c \cdot b \neq a$$

Thm：任意の巡回列は奇数で割れる

任意に巡回列 $a$ と奇数 $b$ を取る。

$$\exists c \in \mathbb{J},\ c \cdot b = a$$

またこのような $c$ はただ１つだけである。

巡回列空間上の偶奇の性質

まず、期待される性質として...

• 奇数を偶数で割れない（証明済み）
• 任意の巡回列は奇数で割れる（証明済み）

証明済みのこの２つ意外にどんなものが考えられそうでしょうか？

• 奇数と奇数の和は偶数
• 偶数と奇数の和は奇数
• 偶数と偶数の和は偶数
• 奇数と奇数の積は奇数
• 任意の巡回列と偶数の積は偶数

ぱっとこの５つは、偶奇性があるなら満たしておいてほしそうなところですよね。

証明は全部最初の項を見ればできるので、割愛します。

他には何があるのでしょうか。
和と積はやった。差は和と同じですし、割り算も偶数割る偶数以外は考えています。偶数割る偶数を考えるかどうか、ぐらいでしょうか。

偶数割る偶数の結果は目に見えてますし、、、
一応、割る２の定義だけしておきます。

Def：巡回列空間上の割る２

関数 $x \mapsto 2 \cdot x$ は、$\mathbb{J} \rightarrow E$ への一対一対応になっている。
よって、この逆関数によって、$x \mapsto x / 2$ を $E \rightarrow \mathbb{J}$ 上で定義できる。

あと、割る２について、結合法則を満たすかもみたいところでしょう。

Thm：割る２は結合法則を満たす

巡回列 $a \in \mathbb{J}$ と偶数 $b \in E$ に対し、

$$a \cdot \frac{b}{2} = \frac{a \cdot b}{2}$$

となる。

proof.)

$a \cdot b$ は、

$$\begin{align*} (\mathrm{I}) & \qquad d_0 = 0 \\ (\mathrm{II}) & \qquad 任意の i \in \mathbb{N} に対し、\\ & \sum_{1 \leq k \leq i} a_k b_{i+1-k}+d_{i-1} を 2 で割った商を d_i 、余りを (a \cdot b)_i とする \end{align*}$$

であり、これを２で割ると、$(a \cdot b)/2$ は、任意の $i \in \mathbb{N}$ に対し、

$$((a \cdot b)/2)_i = (a \cdot b)_{i+1}$$

一方、$a \cdot (b/2)$ は、$(b/2)_i=b_{i+1}$ より、

$$\begin{align*} (\mathrm{I}) & \qquad e_0 = 0 \\ (\mathrm{II}) & \qquad 任意の i \in \mathbb{N} に対し、\\ & \sum_{1 \leq k \leq i} a_k b_{i+2-k}+e_{i-1} を 2 で割った商を e_i 、余りを (a \cdot (b/2))_i とする \end{align*}$$

となる。
$(a \cdot b)_{i+1}$ について、

$$\begin{align*} \sum_{1 \leq k \leq i+1} a_k b_{i+2-k}+d_i &= \sum_{1 \leq k \leq i} a_k b_{i+2-k}+a_{i+1} b_1+d_i \end{align*}$$

を２で割った商が $d_{i+1}$ 、余りが $(a \cdot b)_{i+1}$ となる。
よって、$b_1 = 0$ と、$d_1=0$ より、$e_i=d_{i+1}$ となる。

よって、$(a \cdot b)_{i+1} = (a \cdot (b/2))$ となり、

$$a \cdot \frac{b}{2} = \frac{a \cdot b}{2}$$

が示される。（証明終）

さらに分配法則も確認しておきましょう。

Thm：割る２は分配法則を満たす

偶数 $a,\ b \in E$ に対し、

$$\frac{a+b}{2} = \frac{a}{2}+ \frac{b}{2}$$

となる。

これはほとんど自明でしょうか。あと、

$$\frac{x}{2^n} = \frac{x}{2^{n-1}} / 2$$

によって帰納的に、$2^n$ で割るというのも定義しておきましょう。

さて、次はどうするべきでしょうか？
とりあえず、ゴールを考えてみます。

巡回列空間上のコラッツツリー

巡回列空間というものを考えた理由は、コラッツツリーにおいて、すべての巡回列をちょうど１つずつ持つような状態を作りたかったからです。つまり、こうです：

仮説：巡回列空間上でコラッツツリーはすべての巡回列をちょうど１つずつ持つ

巡回列空間 $\mathbb{J}$ 上において、奇数集合を $O$、偶数集合を $E$ とする。関数 $t:\mathbb{J} \rightarrow \mathbb{J}$ を

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

と定義する。ただし、$1 \in \mathbb{J}$ は乗法の単位元であり、$2,\ 3 \in \mathbb{J}$ は自然に定義されるものとする。
このとき、$a \in \mathbb{J}$ を起点とする $t$ による巡回列 $j_t(a) \in \mathbb{J}$ は次のように定義される：

$$\forall i \in \mathbb{N},\ (j_t(a))_i = \chi_O (t^{i-1}(a))$$

ただし、$\chi_O$ は $O$ の定義関数である：

$$\chi_O(x) = \left\{ \begin{array}{ll} 1 & (x \in O) \\ 0 & (x \in E) \end{array} \right.$$

このとき、$t$ による巡回列全体の集合はすべての巡回列をちょうど一つずつ持つか？　つまり、

• すべての巡回列を持つ

$$\forall a \in \mathbb{J},\ \exists b \in \mathbb{J}, \quad j_t(b) = a$$

• 一意性

$$\forall a,\ b \in \mathbb{J}, \quad j_t(a) = j_t(b)\ \Rightarrow \ a=b$$

を満たすか？

巡回列空間上でコラッツツリーによる巡回列を考えています

巡回列空間に対応するツリーは

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

なので、コラッツツリーも対応させて $3x-1$ にしておきます

一意性の証明は既にできるようです。

$$t(a)-t(b)= \frac{a-b}{2} \quad \mathrm{or} \quad 3\ \frac{a-b}{2}$$

と、足し算が消えることを用います。

proof.) 一意性の証明

$a,\ b \in \mathbb{J}$ に対し、$j_t(a)=j_t(b)$ とする。

任意の $n \in \mathbb{N}$ に対し、ある $m \geq 0$ と $c \in \mathbb{J}$ が存在して、

$$t^n(a) = \frac{3^m \cdot a + c}{2^n} \\$$

$$t^n(b) = \frac{3^m \cdot b + c}{2^n}$$

である、よって両辺の差を取れば、

$$t^n(a)-t^n(b)=3^m\ \cdot \frac{a-b}{2^n}$$

が成り立つ。
これより、$a-b$ は $2^n$ で割れなければならない。任意の $n$ に対して成り立つから、$a-b$ は $0,\ 0,\ 0,\ 0,\ ... \in \mathbb{J}$ にならなければならない。これは加法の単位元 $0$ のことであり、

$$a = b$$

となる。（証明終）

ループしない巡回列も含め、全域で四則演算を定義できたことが活かされました。

すべての巡回列を持つか？

次に考えるべきは、すべての巡回列を持つか？　というところです。
ぱっとは分からなかったですが、いろいろ考えてみたら解けたような気がするので、確認を兼ねてそれを書いていきます。

ポイントは、$a \in \mathbb{J}$ を起点とする $t$ による巡回列 $j_t(a) \in \mathbb{J}$ について、この逆関数に当たるものを、ゼロから定義できるか？　というところです。
そのために、「$t$ による巡回列全体の集合はすべてのループする巡回列を持つこと」を用いて逆関数を定義していきます。

すべてのループする巡回列を持つことは、以下のような第08回の議論を使えばよさそうです。

第08回の議論

$a$ が今ループしている要素だとすれば、

$$a=\frac{3^m a+k}{2^n}$$

と書ける。一方、

$$\begin{align*} a \in \mathbb{Q} \setminus E \ \Rightarrow & \quad k は奇数 \\ a \in E \ \Rightarrow & \quad k は偶数 \\ \end{align*}$$

となるから、これは整合性が取れている。
別途、$0,\ 0,\ 0,\ ...$ という巡回列も持つから、すべての今ループしている巡回列を持つ。

次に、逆順を辿ることを考える。

$$\left\{ \begin{align*} t_e^{-1}(x) &= 2x \\ t_o^{-1}(x) &= \frac{2x-1}{3} \end{align*} \right.$$

だから、

$$a=\frac{偶数}{奇数} \Rightarrow \left\{ \begin{array}{ll} t_e^{-1}(a) = 偶 / 奇 \\ t_o^{-1}(a) = 奇 / 奇 \end{array} \right. \\$$

$$a=\frac{奇数}{奇数} \Rightarrow \left\{ \begin{array}{ll} t_e^{-1}(a) = 偶 / 奇 \\ t_o^{-1}(a) = 奇 / 奇 \end{array} \right.$$

となって、すべてのループする巡回列が存在することを示すことができる。

この議論は、巡回列空間にそのまま適用可能である。ただ、ちょっとこの議論粗い部分もあるので、もう少し丁寧に議論しなおします。
以下の証明では、この議論の内前半部（今ループしているもの）だけを使います。

proof.)　すべての巡回列を持つ（前半）

1. 今ループしているすべての巡回列を持つ
   $\alpha \in \mathbb{J}$ について、ある $n \in \mathbb{N}$ が存在して、任意の $i \in \mathbb{N}$ に対し、

$$\alpha_i = \alpha_{n+i}$$

が成り立つとする。
ここで、$k \in \mathbb{J}$ を、整数からなる数列 $m_{j_1}^{j_2}=\sum_{i=j_1}^{j_2} \alpha_i$ を用いて、

$$k = \sum_{i=1}^{n} \alpha_i \cdot 3^{m_i^n} \cdot 2^{i-1}$$

によって定める。
ここで、$a \in \mathbb{J}$ を、$m=m_{1}^{n}=\sum_{i=1}^n \alpha_i$ を用いて、

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

と定義する。
このとき、任意の $j \geq 0$ に対して、

$$t^j(a)=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^n \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j}} \cdot 2^{i-1}$$

が成り立つ。この成立は以下の帰納法に因る：
$(\mathrm{I})$

$$t^0(a)=a=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^n \alpha_{i+0} \cdot 3^{m_{i+j}^{n+j}} \cdot 2^{i-1}$$

$(\mathrm{II})$

$j$ のとき仮定が成り立つとする。
$t^j(a) \in \mathbb{J}$ が偶数のとき、$\alpha_{j+1}=0$ だから、

$$\begin{align*} t^{j+1}(a) &=\frac{1}{3^m-2^n} \cdot \sum_{i=2}^n \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j}} \cdot 2^{i-2} \\ &=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^{n-1} \alpha_{i+j+1} \cdot 3^{m_{i+j+1}^{n+j}} \cdot 2^{i-1} \\ &=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^n \alpha_{i+j+1} \cdot 3^{m_{i+j+1}^{n+j+1}} \cdot 2^{i-1} \\ \end{align*}$$

ただし、最後の行の変形は、$\alpha_{n+j+1}=\alpha_{j+1}=0$ による。

$t^j(a) \in \mathbb{J}$ が奇数のとき、$\alpha_{n+j+1}=\alpha_{j+1}=1$ だから、

$$\begin{align*} t^{j+1}(a) &=(-1+\frac{1}{3^m-2^n} \cdot 3 \cdot \sum_{i=1}^n \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j}} \cdot 2^{i-1}) /2 \\ &=\frac{1}{3^m-2^n} \cdot (2^n-3^m + \sum_{i=1}^n \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j+1}} \cdot 2^{i-1}) /2 \\ &=\frac{1}{3^m-2^n} \cdot \sum_{i=2}^{n+1} \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j+1}} \cdot 2^{i-1} /2 \\ &=\frac{1}{3^m-2^n} \cdot \sum_{i=2}^{n+1} \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j+1}} \cdot 2^{i-2} \\ &=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^{n} \alpha_{i+j+1} \cdot 3^{m_{i+j+1}^{n+j+1}} \cdot 2^{i-1} \\ \end{align*}$$

となって、仮定は成立する。

$(\mathrm{I}),\ (\mathrm{II})$ より、帰納法より、任意の $j \geq 0$ に対して、

$$t^j(a)=\frac{1}{3^m-2^n} \cdot \sum_{i=1}^n \alpha_{i+j} \cdot 3^{m_{i+j}^{n+j}} \cdot 2^{i-1}$$

が成立する。よって、任意の $j \geq 0$ に対し、

$$\chi_O(t^j(a))=\alpha_{j+1}$$

これにより、

$$j_t(a)=\alpha$$

となる。よって、今のような $\alpha \mapsto a$ は今ループしている巡回列に対する $j_t$ の逆関数となる。また、$t$ による巡回列全体の集合は、今ループしているすべての巡回列を持つ。

今ループしている巡回列をすべて持つことは示せました。
ループしている巡回列一般も同様に定義できそうですが、今回の証明では必要なさそうなので、スルーします。

一般の巡回列をすべて持つことは、今ループしている巡回列をすべて持つことを利用して、全域でとある関数を定義し、それが $j_t$ の逆関数となることを示すという流れです。

そのために、１つ補題を示しておきます。

thm：$n$ 項まで一致する２数は $j_t$ を作用させても $n$ 項まで一致する

$n$ は $0$ 以上の整数とする。
$a,\ b \in \mathbb{J}$ に対し、$n$ 項目まで一致し、$n+1$ 項目は不一致とする。つまり、

$$\forall i \leq n, \quad a_i=b_i$$

$$a_{n+1} \neq b_{n+1}$$

とする。このとき、$j_t(a),\ j_t(b) \in \mathbb{J}$ に対し、$n$ 項目まで一致し、$n+1$ 項目は不一致となる。つまり、

$$\forall i \leq n, \quad j_t(a)_i=j_t(b)_i$$

$$j_t(a)_{n+1} \neq j_t(b)_{n+1}$$

が成立する。

proof.)

題意から不一致性を削除したもの

$a,\ b \in \mathbb{J}$ に対し、$n$ 項目まで一致するならば、$j_t(a),\ j_t(b) \in \mathbb{J}$ に対し、$n$ 項目まで一致する。このとき、$a,\ b$ の $n+1$ 項目が一致するするならば、$j_t(a),\ j_t(b)$ の $n+1$ 項目は一致し、$a,\ b$ の $n+1$ 項目が不一致ならば、$j_t(a),\ j_t(b)$ の $n+1$ 項目は一致しない。

について、$n$ についての帰納法により示す。

$(\mathrm{I})$

$$(j_t(a))_1 = \chi_O (t^0(a))=\chi_O(a)=a_1 \\ (j_t(b))_1 = \chi_O (t^0(b))=\chi_O(b)=b_1$$

より、$n=0$ のとき成立。

$(\mathrm{II})$
$n$ について仮定が成り立つとする。
$a,\ b \in \mathbb{J}$ に対し、$n+1$ 項目まで一致するとする。
帰納法の仮定より、$i \leq n$ に対し $t^i(a),\ t^i(b)$ の偶奇が一致するから、 $t$ を作用させるとき、$t^{n+1}$ まで $x/2$ か $\frac{3x-1}{2}$ のどちらを作用させるかという選択がすべて一致しているということである。
よって、ある $m \geq 0$ と $c \in \mathbb{J}$ が存在して、

$$t^{n+1}(a) = \frac{3^m \cdot a + c}{2^{n+1}}$$

$$t^{n+1}(b) = \frac{3^m \cdot b + c}{2^{n+1}}$$

と書ける。

$$t^{n+1}(a)-t^{n+1}(b) = 3^m \cdot \frac{a-b}{2^{n+1}}$$

となるから、$t^{n+1}(a)-t^{n+1}(b)$ と $(a-b)/2^{n+1}$ の偶奇は一致する。

よって、$a,\ b$ の $n+2$ 項目が一致するかどうかは、$t^{n+1}(a),\ t^{n+1}(b)$ の偶奇が一致するかどうかと連動する。

以上より、帰納法より、仮定は成り立つ。（証明終）

ようやく今回のメインディッシュに入ります

proof.)　すべての巡回列を持つ（後半）

2. すべての巡回列を持つ
   $\alpha \in \mathbb{J}$ をとり、関数 $\beta: \mathbb{N} \rightarrow \mathbb{J}$ を次のように定める。
   任意の$n \in \mathbb{N}$ に対し、$\beta(n) \in \mathbb{J}$ を $\alpha$ の $n$ までの項をループさせた巡回列とする。つまり、以下のように定める：

$$i \leq n\ \Rightarrow \ \beta(n)_i= \alpha_i$$

$$i > n\ \Rightarrow \ \beta(n)_i = \beta(n)_{n-i}$$

このとき、$a \in \mathbb{J}$ を、任意の $i \in \mathbb{N}$ に対し、

$$a_i=j_t^{-1}(\beta(i))_i$$

によって定める。
このとき、$j_t(a)=\alpha$ を示す。

2-1.

まず、

$$\forall i \in \mathbb{N},\ \forall k \leq i, \quad a_k=j_t^{-1}(\beta(i))_k$$

を $i$ についての帰納法により示す。

$(\mathrm{I})$

$$\forall k \leq 1, \quad a_k=j_t^{-1}(\beta(1))_k$$

$(\mathrm{II})$
$i$ について仮定が成り立つとする。
$\beta(i)$ と $\beta(i+1)$ は $i$ までの項が一致するから、補題より、$j_t^{-1}(\beta(i)),\ j_t^{-1}(\beta(i+1))$ の $i$ までの項が一致する。

よって、$i+1$ に対し、仮定は成り立つ。

以上より、帰納法によって仮定は示される。

2-2.
任意に $i \in \mathbb{N}$ を取る。
$a$ と $j_t^{-1}(\beta(i))$ について、$i$ 項まで一致する。よって、$j_t(a)$ と

$$j_t(j_t^{-1}(\beta(i)))=\beta(i)$$

の第 $i$ 項まで一致する。
これは、言い換えると、$j_t(a)$ と $\alpha$ が第 $i$ 項まで一致するということである。

$i$ は任意だったから、

$$j_t(a)=\alpha$$

となる。
よって、$\alpha \mapsto a$ はすべての巡回列に対する $j_t$ の逆関数になる。
これは、$j_t$ による像が $\mathbb{J}$ であるということであり、$t$ による巡回列全体の集合が $\mathbb{J}$ と一致するということである。（証明終）

なんとか証明を形にできました！
穴はない...はずです。

目標だった拡張ができたので今回は区切りよく、ここら辺で終わりにします。では～