問題とは
3x+1問題
与えられた自然数が偶数ならば半分にし、奇数なら倍して加えるという操作を考える。この操作を繰り返すと、どんな自然数であっても必ずになるであろう。
与えられた自然数が偶数ならば半分にし、奇数なら倍して加えるという操作を考える。この操作を繰り返すと、どんな自然数であっても必ずになるであろう。
という問題で、未解決問題です。予想、Collatz予想、角谷予想などなど様々な呼称を持ちます。
例えば、から始めると、
と確かにになります。
から始めると回、から始めると回の操作の後、に到達します。
問題を解くためには
- 以外にループが存在しない。
- 発散するような数列を含まない。
ことを示す必要があります。
例えば、問題の代わりに問題を同様に考えると、
という自明なループの他に
というループが存在します。
さて、奇数の次は絶対に偶数になるので、操作を一回分節約して作用素を次のように定義しましょう:
3x+1作用素 .
このとき、問題は次のように言い換えられます。
3x+1予想
任意の自然数に対して、或るが存在して、が成り立つ。
任意の自然数に対して、或るが存在して、が成り立つ。
実は、弱予想と呼ばれる予想があります。
定義 半群をと定義する。ただし、乗法はにおける通常の乗法を考える。
弱3x+1予想 .
3x+1 弱3x+1の証明. 任意に自然数を取る。を示せばよい。予想によって、或るが存在して、が成り立つ。まず、なので、であることに注意する。このとき、およびより、が分かる。これを繰り返せば、 & よりに到達する。 Q.E.D.
しかしながら、弱予想が解けたからと言って、上の議論を逆順に辿れるとは限らないため、予想よりは確かに弱いことが分かります。
実は予想は未解決ですが、弱予想は既に解決されています。その証明の解説はお楽しみに。