インテジャーズ

INTEGERS

数、特に整数に関する記事。

3x+1問題

3x+1問題とは

3x+1問題
与えられた自然数が偶数ならば半分にし、奇数なら3倍して1加えるという操作を考える。この操作を繰り返すと、どんな自然数であっても必ず1になるであろう。

という問題で、未解決問題です。3n+1予想、Collatz予想、角谷予想などなど様々な呼称を持ちます。

例えば、7から始めると、

7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16
 \to 8 \to 4 \to 2 \to 1

と確かに1になります。

27から始めると111回、97から始めると118回の操作の後、1に到達します。

問題を解くためには

  • 1 \to 4 \to 2 \to 1以外にループが存在しない。
  • 発散するような数列を含まない。

ことを示す必要があります。

例えば、3x+1問題の代わりに3x-1問題を同様に考えると、

\displaystyle 1 \to 2 \to 1

という自明なループの他に

\displaystyle 17 \to 50 \to 25 \to 74 \to 37 \to 110 \to 55 \to 164 \to 82 \to 41 \to 122 \to 61
 \to 182 \to 91 \to 272 \to 136 \to 68 \to 34 \to 17

というループが存在します。

さて、奇数の次は絶対に偶数になるので、操作を一回分節約して3x+1作用素T\colon \mathbb{N} \to \mathbb{N}を次のように定義しましょう:

3x+1作用素 \displaystyle T(n) := \begin{cases}\frac{n}{2} & n \equiv 0\pmod{2} \\ \frac{3n+1}{2} & n \equiv 1 \pmod{2} \end{cases}.

このとき、3x+1問題は次のように言い換えられます。

3x+1予想
任意の自然数nに対して、或るk \in \mathbb{N}が存在して、T^k(n)=1が成り立つ。

実は、3x+1予想と呼ばれる予想があります。

定義 3x+1半群S
\displaystyle S:= \left. \left\langle \left\{ \frac{n}{T(n)} \right| n \in \mathbb{N} \right\} \right\rangle = \left\langle 2, \left. \left\{ \frac{2k+1}{3k+2} \right| k \geq 0 \right\} \right\rangle= \left\langle 2, \frac{1}{2}, \frac{3}{5}, \frac{5}{8}, \frac{7}{11}, \dots \right\rangle
と定義する。ただし、乗法は\mathbb{Q}における通常の乗法を考える。

弱3x+1予想 \ \ \ S \supset \mathbb{N}.

3x+1 \Longrightarrow 弱3x+1の証明. 任意に自然数nを取る。n \in Sを示せばよい。3x+1予想によって、或るk \in \mathbb{N}が存在して、T^k(n)=1が成り立つ。まず、\displaystyle 2, \frac{1}{2} \in Sなので、1 \in Sであることに注意する。このとき、1=T(T^{k-1})(n) \in Sおよび\displaystyle \frac{T^{k-1}(n)}{T(T^{k-1}(n))} \in Sより、T^{k-1}(n) \in Sが分かる。これを繰り返せば、T(n) \in S\displaystyle \frac{n}{T(n)} \in Sよりn \in Sに到達する。 Q.E.D.

しかしながら、弱3x+1予想が解けたからと言って、上の議論を逆順に辿れるとは限らないため、3x+1予想よりは確かに弱いことが分かります。

実は3x+1予想は未解決ですが、弱3x+1予想は既に解決されています。その証明の解説はお楽しみに。