最近、またしても数学熱が出てきている。
以前は参考書などを見て進めていたのだが、それも若干飽きてきていたので、新しいことをやろうと思った。
そこでふと思い出したのが、未解決問題と呼ばれる問題たちだ。
色々と技術は進んできてはいるものの、現在まだ解かれていない問題もたくさんある。
その難易度はどれも凄まじいものだ。
何が難しいかというと、まず問題文を理解することも非常に困難だったりする。
…しかし、その中には、問題の意味だけなら中学生でも理解できるものだってある。
かの有名なフェルマーの最終定理だってそうだ。
問題文は中学生でも理解できる、しかし証明は300年以上もの間数学者を苦しめてきていた。
このような問題は幾つか存在する。
今回は、そんな問題文の理解だけは簡単な、コラッツ予想というものを紹介しよう。
先に言っておくと、チャレンジはしているものの当然ながら自力で解ける気は一切していない。
ただ、その挑戦の楽しさくらいはお伝えできればと思っている。
よかったら、お付き合い願いたい。
2022/5/1追記
本文にも追記するが、奇数の操作回数に着目して色々と考えを進めてみた。
その様子を以下の別記事で書いているので、気になる方は見てみて欲しい。
コラッツ予想とは
まずは問題文を紹介しよう。
ある自然数を\(k\)とし、これに以下の操作を行う。
- \(k\)が奇数なら、3倍して1を足す。
- \(k\)が偶数なら、2で割る。
このとき、\(k\)がどんな自然数でも操作を有限回繰り返すことで1にたどり着けるのか、というのがコラッツ予想だ。
幾つか、具体例で見てみよう。
まず、\(k = 3\)の時。
3→10→5→16→8→4→2→1
ここで1にたどり着いた。
次に、\(k = 5\)…は上の中に出ているので、\(k = 7\)くらいで。
7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
ちょっと回数がかかったが、1にたどり着いてくれた。
こんな感じで、今は2数しか見ていないが、なんとなく1になりそうな気はすると思う。
しかし、すべての自然数で1にたどり着けるのかが分かっていない。
今どこまで分かってるの？
厳密な論文とかではないので、Wikipediaの参照で許してほしい。
まず、初期値\(k\)が\(2^{68}\)以下の自然数については全て1にたどり着くことが分かっている。
\(2^{68}\)だとあまりイメージがつかないが…大体\(2.95 \times 10^{20}\)くらい、つまり20桁になる。
しかし、実際にはこれより大きい数はいくらでもあり、具体例でこれだけ合っているから正しい、とは言えないのが数学だ。
また、Wikiにはテレンス・タオという方がほとんど全ての自然数において、ほとんど正しいと証明したと書いてあるが…正直、中身の論文を見ていないので、なんとも言えない。
そして、Wikiのページをご覧頂いた方なら目についたのではないだろうか。
数学者たちから、現代の数学では手が届かないとまで言われている。
問題文の簡単さからは想像できない難しさであることが分かるだろう。
チャレンジしてみた
まあ、冒頭にも書いた通り、解けるとは思っていない。
しかし、なんらかの足がかりくらいは掴みたいなぁと思い、少しチャレンジしてみた。
背理法で挑戦
まず、証明手法の鉄板の一つである背理法を使ってみよう。
つまり、1にたどり着かないような初期値\(k\)が存在すると仮定し、矛盾を導き出すというものだ。
…が、これにも2パターンある。
- 操作を繰り返すことで、どんどん大きくなる
- 操作を繰り返すことで、1を含まないループが生じる
一個ずつ見ていこう。
発散パターン
どんどん大きくなる、というのが数学的に曖昧だろう。
というわけで、以下のような定義を考えた。
初期値\(k\)から開始して、操作の度に出てくる数字を順に\(a_0 = k, a_1, a_2, …, a_n, …\)と置く。
このとき、どんな\(a_s\)を取っても、\(a_s < a_t\)となるような\(a_s\)より後に出てくる数\(a_t\)が存在する。
数式で書くと以下の通り。
$$\forall a_s \in \{a_i | i \in \mathbb{N}\}, \exists t \in \{j \in \mathbb{N} | s < j\} \mbox{ s.t. } a_s < a_t$$
また、このパターンの場合は操作で同じ数が出てきた途端に二つ目のループになるので、ループはしない前提だ。
まず、初期値\(k\)について、奇数で考える。
もし偶数なら操作によって2で割り続け、改めてそれを\(k\)と置けば同じ議論ができるからだ。
また、\(k\)は発散する数のうち最小のものであると仮定しよう。
つまり、数列の中で\(k\)より小さいものが出てきた瞬間に発散しなくなる、ということだ。
では、ここで自然数\(m_1\)を使って\(k = 2m_1 – 1\)と置いておこう。
奇数なので、3倍して1を足す。
$$3k + 1 = 3(2m_1 – 1) + 1 = 6m_1 – 2$$
偶数なので2で割る。
$$\frac{6m_1 – 2}{2} = 3m_1 – 1$$
さて、もしこれが偶数だとすると2で割ることになる。
すると、元の\(k\)に3倍して1足したものを4で割るということになり、元が1であっても元に戻り、3以上だと元の数よりも小さくなる。
よって、この\(3m_1 – 1\)は奇数でしかあり得なく、ここから\(3m_1\)が偶数、つまり\(m_1\)も偶数だと分かった。
では、新たに自然数\(m_2\)を導入して、\(m_1 = 2m_2\)と置いておこう。
これで代入して式を直しておく。
$$3m_1 – 1 = 3 \cdot 2m_2 – 1 = 6m_2 – 1$$
奇数なので、3倍して1足す。
$$3(6m_2 – 1) + 1 = 18m_2 – 2$$
偶数なので2で割る。
$$\frac{18m_2 – 2}{2} = 9m_2 – 1$$
さて、ここで条件分岐が発生する。
もしこれ全体が奇数なら、偶数ならという2つの分かれ道だ。
全体が奇数だとしたら\(9m_2\)は偶数、つまり\(m_2\)も偶数。
この時はまた自然数\(m_3\)を導入して、\(m_2 = 2m_3\)と表すことになる。
計算までしてしまおう。
$$9m_2 – 1 = 9 \cdot 2m_3 – 1 = 18m_3 – 1$$
$$3(18m_3 – 1) + 1 = 54m_3 – 2$$
$$\frac{54m_3 – 2}{2} = 27m_3 – 1$$
全体が偶数だとしたら\(9m_2\)は奇数、つまり\(m_2\)も奇数。
こちらも自然数\(m_3\)を導入して、\(m_2 = 2m_3 – 1\)と表すだろう。
計算もしてみる。
$$9(2m_3 – 1) – 1 = 18m_3 – 10$$
$$\frac{18m_3 – 10}{2} = 9m_3 – 5$$
そして、数はどんどん大きくなる、言い換えるといつまでもこの操作を繰り返すことができる。
…さて、ここまで導入した数字を見直してみよう。
\(m_1\)は\(k\)が奇数だということを表すために導入した文字で、明らかに\(k > m_1\)。
もし\(k = m_1\)だったら\(1 = 2 \times 1 – 1\)しかあり得ず、その場合は初期値1でスタートしたことになるからだ。
\(m_2\)は\(m_1\)が偶数だということを表すために導入した文字、これも明らかに\(m_1 > m_2\)だ。
こちらは純粋に2で割っているので、どう考えても明らかだろう。
\(m_3\)は条件によって分岐してしまっているが、いずれにしろ必ず\(m_2 \leq m_3\)となる。
イコールとなるのは奇数を表すために置いた場合で、両者とも1になる。
そして、この導入した文字たちは全て自然数で、その下限は1だ。
以上から、いくらでも繰り返せる、繰り返すと自然数の下限にぶつかるという2つが矛盾する…と言いたいところだった。
実は、これだけではまだ証明できていない。
というのも、上で出した\(27m_3 – 1\)という部分、これは奇数か偶数か分からないのでまた場合分けが必要になる。
このとき、全体が偶数、つまり\(m_3\)が奇数として、かつ1だったとしてみよう。
すると、これは26となり、確かに今は計算を続けると1に届くので矛盾する。
しかし、この条件分岐を延々と繰り返すと導入した文字が1でもまだ証明されていない数にもなり得て、今度はその数が1に収束するのか、という別問題にすり替わるだけ。
つまり、これでは証明できなさそうだ。
一回やった時は半分解けた！と興奮したのだが…実は今ここに書いている段階で気づいて、だいぶショックを受けている。
やはり数学のプロが挑戦し続けている問題、そんな簡単に分かるはずはなかった。
ループパターン
今度は、1を含まないループになるパターンだ。
実際、1も操作すると4になり、2回2で割ると1に戻るというループを構成している。
これについて、1を含まないループが存在すればコラッツ予想が偽だったと証明できることになる。
…が、正直こちらは方針すら思いつかない。
他のパターンは？
さて、今背理法で攻めようとしていて、成り立たないとしたら2パターンの場合いずれかだ、ということを書いた。
では、これ以外にないの？という部分が気になると思う。
結論から言うと、これ以外にはない。
この部分限定であれば私でも証明できるので、してみよう。
背理法で攻めたいので、上二つのパターンどちらにもならず、かつ1にもたどり着かないような初期値\(k\)が存在すると仮定する。
まず、大きくなり続けることも、1にもたどり着かないということは、何回操作しても一定の範囲に収まることになる。
具体的には分からないが、その下限を\(l\)、上限を\(u\)としておこう。
そして、ループもしないので、初期値\(k\)から作った数列\(a_n\)の中には重複もない。
では、ここで\(u – l + 1\)回操作をしてみる。
初期値\(k\)を含めると、操作により出てくる数は\(u – l + 2\)個だ。
そして、上限と下限から、この数列が取りうる範囲には\(u – l + 1\)個の自然数が存在する。
ということは、鳩ノ巣原理から、最低でも必ずいずれかの2つが同じになる。
言い換えると、必ずループすることになる。
今、ループをしないと仮定していたので、矛盾だ。
よって、提示した2パターンいずれかになるか、1にたどり着くことが分かった。
…私の力では、このあたりが限界だった。
逆転の発想
さて、背理法では初期値に着目して、そのまま操作することを考えていた。
では、逆向きに考えてみよう。
1から逆の操作をして、全ての自然数を作り出すことができれば証明完了、という発想だ。
偶数に対する操作は簡単で、単に2倍すれば一つ前の数が分かる。
奇数については、どういう数なら奇数の操作結果として合流するかを考えなければいけない。
ある奇数\(2n – 1\)に対して、1回普通に操作してみよう。
$$3(2n – 1) + 1 = 6n – 2$$
これが表しているのは、操作後は必ず6の倍数から2で引いた数になっている、あるいは6の倍数に4を足した数になっている、ということだ。
つまり、これを使えば1から順番に数を作り出していくことが可能だ。
で、実際にプログラムを書いて、ゴリゴリ計算して45回くらいの操作で1にたどり着ける数を一覧にしてみたのだが…正直使えそうなものは見つからなかった。
しいて言えば、3の倍数からは分岐しないくらいだろうか。
これも条件を見れば自明だ。
1回の奇数操作で1になる素数
さて、証明に使えるかは分からないが、この過程で一個だけ性質を見つけたので紹介しておこう。
コラッツ予想の二つの操作のうち、奇数の操作に着目する。
この奇数の操作1回で1にたどり着けるような素数は5のみだ、というものを見つけた。
これは証明もできたので軽く証明してみる。
まず、奇数操作0回、つまり偶数操作のみでたどり着ける数は2、4、8、16、…という2のべき乗になっている。
このうち、奇数操作によって合流できるのは4、16、64、…という、4のべき乗だ。
これは6の倍数-2を2倍すると6の倍数-4、6の倍数-4を2倍すると6の倍数-2になる、という性質を使えば簡単に証明できる。
では、4のべき乗に奇数の逆操作をすると、以下のようになる。
$$\frac{4^n – 1}{3} = \frac{(2^n + 1)(2^n – 1)}{3}$$
ここで、\(n = 1\)の時は分子の括弧が3と1になり、約分して1になる。
これは奇数操作で\(4^1 = 4\)になるのは1であることを表している。
次に\(n = 2\)、分子は5と3でまた約分して5、これは素数だ。
ここからがポイントで、\(n = 3\)以降は必ず分子の括弧どちらかが3の倍数となり、両方とも3より大きい。
つまり、約分した後も自然数の積の形になっている。
ということは素数ではなく合成数になっているので、これ以降素数は出現しない。
以上から、奇数操作が1回だけで1にたどり着ける素数は5のみ、ということが分かった。
…だから何？感がすごいが、まあできたのでメモ程度に残しておこう。
今後どんな方針でやっていくか
ここまでどんなことをやってきたかを書いてきたが…さすがは未解決問題、一筋縄ではいかなさそうだ。
で、これからも色々な方面で攻めてみようと思っているが、幾つか方針を挙げてみよう。
まず、2進数で考えてみるパターン。
これまでは全て10進数で考えていたが、2進数に直すと何か面白いことは起こらないか、という発想だ。
実際、3n+1もn/2も2進数でわりと表現しやすく、特に割る方は最下位ビットが0なら右方向に桁をずらすだけ。
これで、1の個数について何かしらの法則が見つかれば進展するかもしれない。
次に、グラフ理論の木構造。
グラフ理論と呼ばれる数学の分野があり、その中にある木構造をうまく使うとこのコラッツ予想の操作によって辿れる数をまとめることができる。
この木構造を条件に従って作った時に全ての自然数が出てきて、かつ木構造が崩れていなければ証明できたことになるだろう。
…と、ここまではネットでも議論をしている方がいらっしゃるので、調べてみるのも面白いと思う。
その他、あまり調べていないのでやっているところがあるか分からないが…操作の回数との関係とかに注目してみるのも面白いかもしれない。
2022/5/1追記
冒頭にも書いたが、上の方針のうち、最後の奇数操作との関係に着目して少し調べてみた。
また、それに関連して幾つか性質や、予想の言い換えなどもしている。
その様子を以下の記事にまとめたので、もし気になる方がいたら、覗いてみて欲しい。
おわりに
今回は、コラッツ予想というまだ解かれていない問題の概要を見てきた。
解くのは非常に困難ではあるが、こんな数で成り立つのかな？と試すくらいなら小学生でもできるだろう。
暇つぶしにでも、ぱっと見つけた数で試してみてはいかがだろうか。
また、挑戦する権利は誰にでもある。
可能性はもちろん低いと思うが…素人が解ける可能性もゼロではないので、やる気がある方は是非挑戦してみて欲しい。
コメント