コラッツ予想の基本的なこと

この記事はテレンス・タオのブログ記事に書いてあるコラッツ予想に関する考察のうちの一部を勉強し, その理解をもとに日本語で自分なりに紹介するものです. コラッツ予想の難しさの1つの側面を知ることができます.

写像$${C\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}}$$を

$$
C(N)\coloneqq\begin{cases} N/2 & (N\in 2\mathbb{Z}_{>0}), \\ 3N+1 & (N\in 2\mathbb{Z}_{\geq 0}+1)\end{cases}
$$

で定めるとき, コラッツ予想は次のように述べることができます.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

コラッツ予想 任意の$${N\in\mathbb{Z}_{>0}}$$に対して, ある$${k\in\mathbb{Z}_{>0}}$$が存在して$${C^k(N)=1}$$が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

ただし, $${C^k}$$は$${C}$$の$${k}$$回合成を意味します.

写像$${C}$$の代わりに次のような写像$${T\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}}$$, $${S\colon 2\mathbb{Z}_{\geq 0}+1\to2\mathbb{Z}_{\geq 0}+1}$$を考えることも多いです.

$$
T(N)\coloneqq\begin{cases} N/2 & (N\in 2\mathbb{Z}_{>0}), \\ \frac{3N+1}{2} & (N\in 2\mathbb{Z}_{\geq 0}+1),\end{cases} \qquad S(N)\coloneqq C^{\mathrm{ord}_2(3N+1)}(3N+1).
$$

ただし, $${\mathrm{ord}_2}$$は$${2}$$進付値を表します.
このとき, コラッツ予想が次のように言い換えられることはすぐにわかります.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

コラッツ予想 (言い換え1) 任意の$${N\in\mathbb{Z}_{>0}}$$に対して, ある$${k\in\mathbb{Z}_{>0}}$$が存在して$${T^k(N)=1}$$が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

コラッツ予想 (言い換え2) 任意の$${N\in\mathbb{Z}_{>0}}$$に対して, ある$${k\in\mathbb{Z}_{>0}}$$が存在して$${S^k(N)=1}$$が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

集合$${\{C^k(N) \mid k\in\mathbb{Z}_{\geq 0}\}}$$のことを$${N}$$のコラッツ軌道といい, その集合の最小元を$${C_{\min}(N)}$$と表します.
すると, コラッツ予想は「全ての$${N\in\mathbb{Z}_{>0}}$$に対して$${C_{\min}(N)=1}$$が成り立つ」と言い換えられますが, それを示すには次の2つを示せばよいこともすぐにわかります.

1. $${1\to 4\to 2\to 1}$$以外にループがない.

2. $${C_{\min}(N)=O(1).}$$

非自明なループがないということは次を意味します: 正整数$${N, k}$$に対して$${C^k(N)=N}$$が成り立つならば, $${N\in\{1,2,4\}}$$である.

さて, $${3}$$倍して$${1}$$を足すという操作は大体$${3}$$倍するということなので, 写像$${C}$$を繰り返すということは「たくさん$${3}$$倍してたくさん$${2}$$で割る」ということであり, 数論的には「$${2}$$の冪 vs $${3}$$の冪」と見ることができます. この観点で「非自明なループがない」という「弱コラッツ予想」は実は次の予想と同値であることが知られています.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

予想A $${N\in\mathbb{Z}_{>1}}$$と$${k\in\mathbb{Z}_{>0}}$$と整数列

$$
0=a_0<a_1<\cdots<a_k
$$

であって, 

$$
(2^{a_k}-3^k)N=3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+3\cdot 2^{a_{k-2}}+2^{a_{k-1}}
$$

が成り立つようなものは存在しない.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

同値性の証明を行う前にもう1つの写像を導入しておきます.
$${\mathbb{Z}_{>0}}$$に同値関係$${a\sim b}$$を$${a/b=2^m}$$が成り立つような$${m\in\mathbb{Z}}$$が存在することとして定義します. 同値類には記号$${[a]}$$を使います. 商集合$${\mathbb{Z}_{>0}/\sim}$$と奇数の集合$${2\mathbb{Z}_{\geq 0}+1}$$の間に自然な全単射があることがわかります.

このとき, 写像$${\overline{S}\colon\mathbb{Z}_{>0}/\sim \ \to \ \mathbb{Z}_{>0}/\sim}$$を

$$
\overline{S}([N])\coloneqq [3N+2^{\mathrm{ord}_2(N)}]
$$

で定めます. この写像がwell-definedであることは定義から簡単に確かめられます. これは$${N}$$が奇数のときに$${\overline{S}([N])=[S(N)]}$$が成り立つという意味で$${S}$$と$${\overline{S}}$$は等価な写像です. そして, 「非自明なループがない」という「弱コラッツ予想」が次の予想と同値であることは即座にわかります.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

予想B ある$${k\in\mathbb{Z}_{>0}}$$と$${[N]\in\mathbb{Z}_{>0}/\sim}$$に対して$${\overline{S}^k([N])=[N]}$$が成り立つならば, $${[N]=[1]}$$である.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

それでは予想Aと予想Bが同値であることを証明しましょう.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

「予想Bの否定 $${\Longrightarrow}$$ 予想Aの否定」の証明.
ある$${[N]\neq [1]}$$と$${k\in\mathbb{Z}_{\geq 1}}$$が存在して, $${\overline{S}^k([N])=[N]}$$が成り立つと仮定する. このとき, $${[N]}$$は奇数と仮定してよい($${\mathbb{Z}/\sim}$$の代表元としていつでも奇数を取れるので). また, $${k>1}$$と仮定してよい. (理由: $${k=1}$$であれば, $${\overline{S}([N])=[3N+1]=[N]}$$なので, ある整数$${m}$$が存在して$${2^mN=3N+1}$$が成り立つ必要がある. これを満たすものは$${m=2, N=1}$$しかない.)
写像$${\overline{S}}$$の定義から

$$
\overline{S}^k([N])=[3^kN+3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots +2^{a_{k-1}}]
$$

と計算できる. ただし, $${0\leq i\leq k-1}$$に対して

$$
n_i\coloneqq 3^iN+3^{i-1}\cdot 2^{a_0}+\cdots + 2^{a_{i-1}}
$$

として, 帰納的に$${a_i\coloneqq \mathrm{ord}_2(n_i)}$$で定義している.

(理由: $${a_0=\mathrm{ord}_2(n_0)=\mathrm{ord}_2(N)=0}$$なので,

$$
\overline{S}([N])=[3N+1]=[3N+2^{a_0}]=[n_1]
$$

である. 漸化式$${n_{i+1}=3n_i+2^{a_i}}$$に注意しておく. 帰納法を使うことにして

$$
\overline{S}^i([N])=[n_i]
$$

の成立を仮定すると,

$$
\overline{S}^{i+1}([N])=[3n_i+2^{a_i}]=[n_{i+1}]
$$

なので, $${\overline{S}^k([N])=[n_k]}$$が示された.)

また, $${0=a_0< a_1<\cdots < a_{k-1}}$$が成り立っている. (理由: $${n_i=2^{a_i}m_i}$$と書くことにすると, $${3n_i+2^{a_i}=n_{i+1}}$$より$${2^{a_i}(3m_i+1)=2^{a_{i+1}}m_{i+1}}$$となって, $${3m_i+1}$$は偶数, $${m_{i+1}}$$は奇数なので, $${a_i< a_{i+1}}$$.)

さて, 仮定により$${\overline{S}^k([N])=[N]}$$であったため, ある整数$${a_k}$$が存在して

$$
2^{a_k}N=3^kN+3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots +2^{a_{k-1}}
$$

が成り立つ. $${2^{a_k}N=3n_{k-1}+2^{a_{k-1}}}$$より先ほど同様に考えて$${a_{k-1}< a_k}$$が成り立っている. そうして移項すると

$$
(2^{a_k}-3^k)N=3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots +2^{a_{k-1}}
$$

に到達して, $${N>1}$$であったから予想Aの反例が得られた.

「予想Aの否定 $${\Longrightarrow}$$ 予想Bの否定」の証明.
$${N\in\mathbb{Z}_{>1}}$$と$${k\in\mathbb{Z}_{>0}}$$と整数列

$$
0=a_0<a_1<\cdots<a_k
$$

であって, 

$$
(2^{a_k}-3^k)N=3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+3\cdot 2^{a_{k-2}}+2^{a_{k-1}}
$$

が成り立つようなものが存在したとする. $${a_0=0}$$なので, $${N}$$は奇数である. $${n_0=N}$$および$${n_{i+1}=3n_i+2^{a_i}}$$によって帰納的に$${n_i}$$を定める($${0\leq i\leq k}$$). このとき, 

$$
(2^{a_k}-3^k)n_i=3^{k-1}\cdot 2^{a_i}+3^{k-2}\cdot 2^{a_{i+1}}+\cdots+ 2^{a_{i+k-1}}
$$

が成り立つ. ただし, $${j>0}$$に対して$${a_{k+j}\coloneqq a_k+a_j}$$と定めている. (理由: $${i=0}$$のときは$${N}$$達が満たしている式そのもの. $${i}$$のときに成立したとすると

$$
\begin{align*}
(2^{a_k}-3^k)n_{i+1}&=3^k\cdot 2^{a_i}+3^{k-1}\cdot 2^{a_{i+1}}+\cdots+3\cdot 2^{a_{i+k-1}}+(2^{a_k}-3^k)\cdot 2^{a_i}\\
&=3^{k-1}\cdot 2^{a_{i+1}}+\cdots+3\cdot 2^{a_{i+k-1}}+2^{a_{i+k}}
\end{align*}
$$

と$${i+1}$$のときも成立することがわかる.) $${i\geq k+1}$$の場合も含めて$${(a_i)}$$は狭義単調増大なので, $${a_i=\mathrm{ord}_2(3^{k-1}\cdot 2^{a_i}+\cdots+ 2^{a_{i+k-1}})}$$であり, $${2^{a_k}-3^k}$$が奇数であることから$${a_i=\mathrm{ord}_2(n_i)}$$が従う. よって,

$$
\overline{S}([n_i])=[3n_i+2^{a_i}]=[n_{i+1}]
$$

が得られ, 特に

$$
\overline{S}^k([N])=\overline{S}^{k-1}([n_1])=\cdots =[n_k]=[2^{a_k}N]=[N]
$$

がわかる. これは予想Bの否定を示している.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

以上で, 弱コラッツ予想と予想Aが同値であることがわかりました. この事実を用いることによって, 次を証明することができます.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

命題  弱コラッツ予想が正しいと仮定する. このとき, $${2^a>3^k}$$を満たすような$${a,k\in\mathbb{Z}_{>0}}$$について,

$$
2^a-3^k \to\infty \quad (k\to \infty)
$$

が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

これを証明するために, 補題を2つ用意しておきます.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

補題１ $${q\in\mathbb{Z}_{\geq 2}}$$, $${d\in\mathbb{Z}_{\geq 1}}$$に対して, $${d+1}$$個の整数$${v, v_1,\dots, v_d}$$であって, $${v_1,\dots, v_d}$$が全て$${q}$$と互いに素であるようなものを考える. $${\pi\colon\mathbb{Z}\to\mathbb{Z}/q\mathbb{Z}}$$を自然な全射とし, 

$$
P(v;v_1,\dots, v_d)\coloneqq \{v+\varepsilon_1v_1+\cdots+\varepsilon_dv_d \mid (\varepsilon_1,\dots,\varepsilon_d)\in\{0,1\}^d\}
$$

とおく. このとき,

$$
\#\pi(P(v;v_1,\dots, v_d))\geq \min\{q,d+1\}
$$

が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

証明. $${d\leq q-1}$$のときに$${\#\pi(P(v;v_1,\dots, v_d))\geq d+1}$$を示せば十分である. (理由: $${d>q-1}$$のときは$${P(v;v_1,\dots, v_d)\supset P(v;v_1,\dots, v_{q-1})}$$なので, $${d+1=q}$$のときに$${\mathbb{Z}/q\mathbb{Z}}$$において$${q}$$個の元が生じれば, それ以降ずっと$${q}$$個である.) このことを$${d}$$に関する数学的帰納法で証明する.

$${d=1}$$のとき. $${P(v;v_1)=\{v, v+v_1\}}$$であり, $${v_1}$$が$${q}$$と互いに素であることから

$$
v\not\equiv v+v_1\pmod{q}
$$

なので, $${\#\pi(P(v;v_1))=2}$$がわかる.

次に, $${d+1\leq q-1}$$とし, $${\pi(P(v;v_1,\dots, v_{d}))\geq d+1}$$が成り立つと仮定する. 仮定より$${w_1,\dots, w_{d+1}\in P(v;v_1,\dots, v_{d})}$$であって, $${\#\{\pi(w_1),\dots, \pi(w_{d+1})\}=d+1}$$であるようなものをとることができる. このとき, $${w_1+v_{d+1}, \dots, w_{d+1}+v_{d+1}}$$の中に$${\bmod{q}}$$で$${w_1,\dots, w_{d+1}}$$のいずれとも異なるものが存在することを示せばよい. それを背理法で証明するために

$$
\{\pi(w_1+v_{d+1}),\dots,\pi(w_{d+1}+v_{d+1})\}=\{\pi(w_1),\dots, \pi(w_{d+1})\}
$$

を仮定しよう. このとき,

$$
\left(\sum_{i=1}^{d+1}w_i\right) + (d+1)v_{d+1} \equiv  \sum_{i=1}^{d+1}w_i \pmod{q}
$$

が成り立つので, $${q\mid (d+1)v_{d+1}}$$となる. $${v_{d+1}}$$は$${q}$$と互いに素であるので, $${q\mid d+1}$$が従い, $${d+1\leq q-1 \leq d}$$となって矛盾.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

補題２ $${2^a>3^k}$$を満たすような$${a,k\in\mathbb{Z}_{>0}}$$について, $${k}$$が十分大きければ, ある整数$${d\geq\frac{k}{4}}$$が存在して,

$$
\Delta_{a,k}\coloneqq\{(a_1,\dots, a_{k-1})\in \mathbb{Z}_{>0}^{k-1} \mid a_1<\cdots<a_{k-1}<a\}
$$

は互いに素な2つの$${d}$$次元立方体を含む.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

証明. ある整数$${d\geq\frac{k}{4}}$$が存在して

$$
(1,3,\dots, 2d-1,2d+1,2d+2,\cdots ,k-2+d, k-1+d)\in\Delta_{a,k}
$$

および

$$
(3,5,\dots, 2d+1,2d+3,2d+4,\cdots ,k+d, k+1+d)\in\Delta_{a,k}
$$

が成り立つ. (理由: $${d\coloneqq\left\lfloor\frac{1}{2}\left(\frac{\log 3}{\log 2}-1\right)k\right\rfloor}$$とおけば, $${k+1+d < k+2d\leq k+\left(\frac{\log 3}{\log 2}-1\right)k=\frac{\log 3}{\log 2}k < a}$$であり, $${\frac{1}{2}\left(\frac{\log 3}{\log 2}-1\right)=0.29248…}$$である.)

このとき, $${d}$$次元立方体

$$
\begin{align*}
&\{(1+\varepsilon_1,3+\varepsilon_2,\dots, 2d-1+\varepsilon_d,2d+1,2d+2,\cdots ,k-2+d, k-1+d) \mid \\
& \ (\varepsilon_1,\dots,\varepsilon_d)\in\{0,1\}^d\}
\end{align*}
$$

および

$$
\begin{align*}
&\{(3+\varepsilon_1,5+\varepsilon_2,\dots, 2d+1+\varepsilon_d,2d+3,2d+4,\cdots ,k+d, k+1+d) \mid \\
& \ (\varepsilon_1,\dots,\varepsilon_d)\in\{0,1\}^d\}
\end{align*}
$$

はともに$${\Delta_{a,k}}$$に含まれており, 共通部分はない.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

命題の証明. $${2^a>3^k}$$を満たすような$${a,k\in\mathbb{Z}_{>0}}$$をとり, $${k}$$は十分大きいものとする. 実際には$${2^a-3^k\geq \frac{k}{4}}$$を証明しよう. $${a_0=0, a_k=a}$$と記号を固定する.

$$
\begin{align*}
V_{a_k,k}\coloneqq &\{3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+ 3\cdot 2^{a_{k-2}}+2^{a_{k-1}} \mid \\
& \ (a_1,\dots, a_{k-1})\in\Delta_{a_k,k}\}
\end{align*}
$$

と$${V_{a_k,k}}$$を定義する. まず, 写像

$$
\iota\colon \Delta_{a_k,k}\to V_{a_k,k};\quad (a_1,\dots, a_{k-1})\mapsto 3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+2^{a_{k-1}}
$$

が全単射であることに注意しておく. (理由:

$$
\begin{align*}
&3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+ 3\cdot 2^{a_{k-2}}+2^{a_{k-1}}\\
&=3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{b_1}+\cdots+ 3\cdot 2^{b_{k-2}}+2^{b_{k-1}}
\end{align*}
$$

が成り立つとき, 両辺から$${3^{k-1}\cdot 2^{a_0}}$$を引いた残りについて, 左辺の$${\mathrm{ord}_2}$$は$${a_1}$$であり, 右辺の$${\mathrm{ord}_2}$$は$${b_1}$$であることが$${(a_i)}$$および$${(b_i)}$$の単調性からわかる. よって, $${a_1=b_1}$$である. 今度は両辺から$${3^{k-2}\cdot 2^{a_1}}$$を引いた残りについて, 左辺の$${\mathrm{ord}_2}$$は$${a_2}$$であり, 右辺の$${\mathrm{ord}_2}$$は$${b_2}$$である. よって, $${a_2=b_2}$$であり, 以下同様.)

$${q\coloneqq 2^{a_k}-3^k}$$とおくと, 弱コラッツ予想が正しいという仮定から, すなわち予想Aが正しいという仮定から, $${V_{a_k,k}}$$が$${q}$$の倍数を含むならばそれは$${q}$$しかあり得ない.予想Aから$${q>1}$$もわかる.

さて, 補題２によって, 整数$${d\geq \frac{k}{4}}$$および$${(a_1,\dots,a_{k-1})\in \Delta_{a_k,k}}$$が存在して

$$
\begin{align*}
\Box\coloneqq&\{(a_1+\varepsilon_1,a_2+\varepsilon_2,\dots, a_d+\varepsilon_d,a_{d+1},a_{d+2},\cdots ,a_{k-2}, a_{k-1}) \mid \\
& \ (\varepsilon_1,\dots,\varepsilon_d)\in\{0,1\}^d\}\subset\Delta_{a_k,k}
\end{align*}
$$

かつ

$$
\forall v\in \iota(\Box),\quad v\not\equiv 0\pmod{q}
$$

が成り立つ. (理由: 補題２によって互いに素な2つの$${d}$$次元立方体の存在を示していたので, どちらか一方の$${\iota}$$による像は$${q}$$を含むことができず, よって$${q}$$の倍数を一切含まない.) 定義から

$$
\iota(\Box)=P(3^{k-1}\cdot 2^{a_0}+3^{k-2}\cdot 2^{a_1}+\cdots+2^{a_{k-1}}; 3^{k-2}\cdot 2^{a_1},\dots, 3^{k-d-1}\cdot 2^{a_d})
$$

であるが, $${3^{k-2}\cdot 2^{a_1},\dots, 3^{k-d-1}\cdot 2^{a_d}}$$はいずれも(素因数は$${2}$$ or $${3}$$より)$${q}$$と互いに素なので, 補題１より

$$
\#\pi(\iota(\Box))\geq \min\{q,d+1\}
$$

が成り立つ. ところが, 今$${0\not\in\pi(\iota(\Box))}$$だったので, 

$$
q > \min\{q,d+1\}
$$

ということになっており, これが成り立つということは

$$
q > d\geq \frac{k}{4}
$$

が結論される.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

というわけでコラッツ予想は次の定理を系として含んでいることが判明しました.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

定理 $${2^a>3^k}$$を満たすような$${a,k\in\mathbb{Z}_{>0}}$$について,

$$
2^a-3^k \to\infty \quad (k\to \infty)
$$

が成り立つ.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

「定理」と書きました. 先ほどは未解決問題を仮定して導出しましたが, 実はこれ自体は未解決ということではありません. 例えばベイカーの定理から証明することができます. まずは利用するベイカーの定理の主張を復習しておきましょう.

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

ベイカーの定理 $${\alpha_1,\dots, \alpha_n}$$を$${0}$$でない代数的数であって, $${\log \alpha_1, \dots, \log \alpha_n}$$が$${\mathbb{Q}}$$上一次独立であるようなものとする. このとき, $${(\beta_0,\dots, \beta_n)\in\overline{\mathbb{Q}}^{n+1}\setminus\{(0,\dots, 0)\}}$$
に対して,

$$
|\beta_0+\beta_1\log \alpha_1+\cdots+\beta_n\log \alpha_n|>H^{-C}
$$

が成り立つ. ここで, $${H}$$は$${\beta_0,\dots,\beta_n}$$の各高さを考えたときの最大値であり, $${C}$$は$${n, \log\alpha_1,\dots, \log \alpha_n}$$および「$${\beta_0,\dots,\beta_n}$$の各次数を考えたときの最大値」のみに依存して定まる正の実数(effective).

♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩♫♪♩

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

ベイカーの定理を用いた「定理」の証明. 

$$
2^a-3^k=3^k(e^{a\log 2-k\log 3}-1)
$$

であるが, $${\log 2}$$と$${\log 3}$$が$${\mathbb{Q}}$$上一次独立であることは容易にわかるので, ベイカーの定理より

$$
|a\log 2-k\log 3|>H^{-C}
$$

が成り立つ. この場合の$${H}$$は$${\max\{|a|,|-k|\}=a}$$であり, $${C}$$は$${a,k}$$には依存しない. 今は$${2^a-3^k>0}$$なので$${a\log 2-k\log 3>0}$$が必要であり, $${x>0}$$に対して$${e^x-1>x}$$が成り立つので, 

$$
2^a-3^k > \frac{3^k}{a^C}
$$

が得られる. $${2^a-3^k}$$そのものは$${k}$$を固定したときに$${a}$$がでかくなればなるほど大きくなるため, $${2^{a-1}<3^k}$$を仮定しても一般性を失わない. このとき, $${k}$$が十分大きければ$${a<2k}$$なので, 

$$
2^a-3^k > \frac{3^k}{(2k)^C}
$$

に到達する. これは$${k\to\infty}$$で発散する.

♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬♬

こうして, ベイカーの定理を用いれば定量的にはより強い形で「定理」が証明されました. ベイカーの定理は(ベイカーがフィールズ賞をとった業績でもあり)とても強力ですが, ここで重要なのはたった今導出した「定理」自体はそんなに自明ではないということです. というのも

$$
2^a-3^k=3^k\left(3^{a\left(\frac{\log 2}{\log 3}-\frac{k}{a}\right)}-1\right)
$$

なので, $${2^a-3^k}$$が小さくなり得るかという話は$${\frac{\log 2}{\log 3}}$$の有理近似と結びついており, 「定理」を得るにはベイカーの定理よりは弱い形でよいかもしれないけれど, 何かしら近似についての結果は使う必要がありそうだからです.

数学において定理の証明はその系の証明より難しいとは限らないことはよくあることではありますが, ですがそれはある意味で数学の不思議な側面であり, 定理の証明がその系の証明より難しいことは普通であるとは言っていいと思います. その観点からするとコラッツ予想(の非自明なループがないという弱い部分)を証明することは少なくとも$${2}$$の冪と$${3}$$の冪の差が無限に大きくなるという「定理」よりは難しいと考えられます. そして, その「定理」もそれなりに難しいものです. 以上はコラッツ予想がそんなに簡単な相手ではないことを知ることができる1つの話題でした. (コラッツ予想を完全に証明するには今回の側面だけが関わってくるわけでは当然ありません.)

参考文献

T. Tao, The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3, テレンス・タオのブログ, 2011/8/25.