コラッツの問題

コラッツの問題（コラッツのもんだい、Collatz problem）は、数論の未解決問題のひとつである。問題の結論の予想を指してコラッツ予想と言う。伝統的にローター・コラッツの名を冠されて呼ばれるが、固有名詞に依拠しない表現としては3n+1問題とも言われ、また初期にこの問題に取り組んだ研究者や場所の名を冠して、角谷の問題、米田の予想、ウラムの予想、シラキュース問題、コラッツ・角谷問題などとも呼ばれる。

数学者ポール・エルデシュは「数学はまだこの種の問題に対する用意ができていない」と述べた。また、ジェフリー・ラガリアスは2010年に、コラッツの予想は「非常に難しい問題であり、現代の数学では完全に手が届かない」と述べた。

2019年9月、テレンス・タオによって大きな進展があり、ほとんどの自然数において（より正確には対数密度の意味で）、コラッツ写像の反復の途中で、どんなにゆっくり大きくなる上限を与えてもそれを下回る値が現れること（予想に関連する性質の一つ）を示すプレプリントを発表し、論文は2022年5月に出版された。

概要

任意の正の整数に対して、以下で定められる操作について考える。が偶数の場合、を 2 で割るが奇数の場合、に 3 を掛けて 1 を足す操作の結果（計算結果）を新たなとしてこの操作を繰り返し続けた時、「どんな初期値から始めても、有限回の操作のうちに必ず 1 に到達する（そして 1→4→2→1 というループに入る）」という主張が、コラッツの予想である。

モジュラ計算の表記を用いて、上記の操作を関数として定義する。

任意の正の整数に対して、この関数 (コラッツ写像とも呼ばれる) を繰り返し適用することで整数の無限列を得る。数式としての定義は次のようになる。

このとき、コラッツ予想を形式的に書くと、以下のようになる。

すなわち、任意の正整数に対してを繰り返し適用していると、がいつかは成り立つという主張がコラッツ予想である。1に到達して以降は、この数列は 1, 4, 2 を繰り返すのみとなるため、以降では最初に1に到達して以降の数は表記しないことにする。

コラッツ予想が誤りであるなら、1 を含まない数列を生成する初期値が存在するということになる。そのような数列は、1 を含まない繰り返し数列に突入するか、もしくは際限なく増大していくかのいずれかである。そのような数列はいまだ見つかっていない。

コンピュータを用いた計算により、268 までの初期値には反例がないことが確かめられている。

例

初期値を 6 にしたとき、6, 3, 10, 5, 16, 8, 4, 2, 1 という1に到達する数列を得る。

初期値を 11 とすると、11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 となり、1 に到達するまでにより長くかかる。初期値として 27 を選ぶと、以下のように数列の項数は112にまで及び、その値は最終的に 1 に到達する前に最大 9232 まで増大する。

各整数において1になるまでの回数はを，各整数に対する最大値はを参照。「3を掛けて1を加えた後、奇数になるまで2で割る」という1回の作業で1となる数値は、と無限に存在する。

歴史 1930年代ごろ、学生であったコラッツは数論的関数を有向グラフとして表現して、そのグラフの性質が関数のふるまいとどのように関連付けられるかに興味を持った。この時の彼のノートには、現在知られるものとは異なる関数について調べられている。コラッツはこれらの関数についての問題を出版することはなかったが、1950年の国際数学者会議をきっかけに広くこの問題が知られるようになり、1963年に初めて (1930年代にコラッツが研究していた形のものが) 紙面に取りあげられた。その後、この問題に興味を持った数学者によって研究される間に、様々な別名を得ることとなった。「ハッセのアルゴリズム」はヘルムート・ハッセに、「シラキュース問題」はシラキュース大学に、「角谷の問題」は角谷静夫に、「ウラムの問題」はスタニスワフ・ウラムに由来する。

コラッツ予想の解決にはいくつかの懸賞金がかけられており、コクセターが50ドル、エルデシュが500ドル、は1000ポンドを申し出ている。

2011年度（平成23年度）大学入試センター試験『数学II・数学B』第6問に題材として取り上げられた。

2019年、テレンス・タオは「を満たす任意の関数について、から始まるコラッツ数列の最小値は (Logarithmic densityの意味で) ほとんど全ての自然数においてより小さい」ことを証明した。注意すべき点として、これはほとんどすべての自然数においてコラッツ予想（すべての自然数が最終的に1に到達すること）が成立すると主張するものではない。事実タオは、結論を「ある絶対定数が存在して、（対数密度の意味で）ほとんどすべての自然数について軌道の最小値が以下になる」と強める問いは、完全なコラッツ予想とほぼ同程度に難しい可能性が高く、本論文の手法の射程外であると述べている。この成果は予想に関連する大きな進展として報じられた。帰結として例えば、から始まるコラッツ数列の最小値はほとんど全ての自然数においてより小さくなることが従う。

2021年7月7日、株式会社音圧爆上げくんが、「コラッツ予想の真偽を明らかにした方に懸賞金1億2000万円を支払います」と発表した。

この予想を支持する論拠コラッツの予想は未解決だが、この問題を研究した多くの数学者は正しいだろうと考えている。そう予想される理由を以下に挙げる。

経験的証拠この予想は、初期値が268 ≈ 2.95×1020までは成り立つことがコンピュータで確認されている。この数値は、コンピュータのスピードアップとテスト技術の向上に伴って更新され続けている。

しかしこういったコンピューターでの検証は、予想が真であるという証拠にはならない。ポリア予想、、スキューズ数の場合に示されているように、非常に大きな数において予想の反例が見つかることがある。

ヒューリスティクス厳密な議論ではないヒューリスティクスであるが、ステップを経るごとに数の大きさがどのようになるかを考察する。今、n が偶数ならば、次のステップで大きさは半分になる。また、n が奇数ならば、次のステップで 3n + 1 になるが、これは必ず偶数であるから、その次に (3n + 1)/2 になることまでは確定している。ここまでを一つのステップと解釈すれば、このステップで大きさは約 3/2 倍になる。1回のステップを経た後に偶数になるか、奇数になるかが半々であると考えると、1/2 の確率で数の大きさは 1/2 倍になり、残る 1/2 の確率で数の大きさは 3/2 倍になる。よって、1回のステップで、数の大きさは (1/2)1/2 × (3/2)1/2 倍になると期待される。これは 1 より小さな値であるから、ステップを経るごとに「確率的に」小さくなると考えられる。この意味で、いつかは 1 に到達するとの予想は確からしい。

確率論の言葉を用いるとこれは無限のステップ数を取る極限で1に平均収束するということであり、厳密には予想の確からしさとは無関係である。

コラッツの数列を計算するプログラミング例以下は擬似コードによるプログラミング例である。与えられた初期値に対するコラッツ数列を計算できる。 def collatz(n) show n if n.odd? and n > 1 collatz(3n + 1) else if n.even? collatz(n / 2)

このプログラムは 1, 4, 2, 1 の無限サイクルを省くために 1 に到達すると停止するようになっている。もしコラッツ予想が正しければ、いかなる正の整数の初期値を与えても停止する。

この問題を、初期のコンピュータで計算することで研究したのがスタニスワフ・ウラムであった。

サイクルが奇数であるときには必ず偶数になることから、コラッツ写像の「ショートカット」形式が次の定義で与えられる：

コラッツ数列のサイクルとは相異なる正整数からなる数列であって、, , ..., を満たすものである。唯一知られているサイクルは長さ2ので、これは自明なサイクルと呼ばれる。

サイクルの長さ自明ではないサイクルの長さは少なくともである。Eliahouは1993年の論文で、サイクルの最小値がを超えるならば、周期の長さが

となることを示した。ここでは非負整数で、かつである。この結果は、の連分数展開と関連している。最新の検証では、までコラッツ予想が正しいと判明しているので、同様の論法によりサイクルの長さの下限は (「ショートカット」無しなら ) であると言える。

k-サイクル -サイクルとは、奇数が連続する増加列個と偶数が連続する減少列個の個の部分で全体が構成されたサイクルである。例えばサイクルが、奇数による増加列1個と、偶数による減少列1個で構成されたなら、1-サイクルと呼ぶ。Steiner (1977)は、1-サイクルが、自明なサイクル(1;2)のみであることを証明した。ジョン・サイモンズは、Steinerの方法を使って、2-サイクルが存在しないことを証明した。サイモンズとde Wegerはこの証明を拡張して、までの場合において、非自明な-サイクルが存在しないことを示した。また、が69以上の場合においては、存在した場合のサイクルの最小値の範囲を与えた。例えばの場合は、サイクルの最小値はより大きくより小さいことが示されている。

コラッツ予想の他の形式ボトムアップ方式

別のアプローチをとってみる：ボトムアップ方式でいわゆるコラッツグラフを作成してみる。コラッツグラフは、以下のように操作を逆にして定義する。

したがって、すべての正の整数が最終的に1になることを証明する代わりに、1がすべての正の整数に逆方向につながることを証明すればよい。任意の整数, ⇔ である。ゆえに、 ⇔ である。推測的に、この逆関係は、1–2–4ループ（この記事の問題の説明のセクションで定義されている変更されていない関数の4–2–1ループの逆）を除いてツリーを形成する。

操作を、ショートカット操作に置き換えた場合は、コラッツグラフの定義は以下のようになる。

任意の整数, ⇔ 。ゆえに、 ⇔ である。推測的に、この逆関係は、1–2ループ（上記のように修正された関数f（n）の1–2ループの逆）を除いてツリーを形成する。

剰余列

本節では、コラッツ関数を少し変形したものを考える：

nが奇数の場合には3n + 1が必ず偶数になるので上記のようにできる。

をxの2で割った余りとする。P(2n) = 0 で、P(2n + 1) = 1 である。整数nの剰余列を、pi = P(ai), ただしa0 = n, and ai+1 = f(ai) と定義する。 (3n + 1)/2 または n/2、どちらの操作が適用されるかは、剰余に依存する。剰余列はfによる操作の場合分けに等しい。 f(n)に対してこの形式を適用すると、２つの整数m とnの剰余列は、m とnが2kを法として合同の場合のみ、最初のk項で一致することが示される。これは、すべての整数が剰余列により一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応する剰余列が異なる必要があることを意味する。

n=a·2k + b に関数 f を k 回適用すると、a·3c + dとなる。ここでdはbに関数fをk回適用した結果で、cはその過程で3倍の演算を行った（増加した）回数である。（例えば、a·25 + 1 では、1が2,1,2,1と変化し最後に2になるので、3回の増加がある。よって結果はa·33+2 である。a·22 + 1 では、1が2に増加しその後1になるので、結果は3a + 1 となる。） bが2k - 1の場合には、 k回の増加があり、結果は2a·3k - 1となる。aに掛かる係数は、aには無関係で、bにのみ依存する。これにより、特定の形式の数値が特定の反復回数の後、常により小さい数値になることを予測できます。例えば、4a + 1 は、2回のf操作により3a + 1となり、16a + 3は4回のf操作により9a + 2となる。これらの小さくなった数が1へとつながるかどうかは、 aの値に依存する。

法の一般化本節ではショートカット版を、単にコラッツ写像と称する。

を2以上の整数として

という、各整数にを法とした非負の最小の余りを返す関数を導入すると、コラッツ写像はと書ける。このことから、

と定めると、法について一般化されたコラッツ写像が得られる。この写像は以下の特徴を持つ。 . . . したがって、とくに1の周期軌道と、整数上の不動点の分布が、どのに於いてもオリジナルのコラッツ写像と酷似する。これらの周期軌道を自明な軌道と呼ぶことにすると、既に10未満のに於いては、に於いて、正の範囲に非自明な周期軌道が確認されている。コラッツ予想の変形についてこのことから次の命題が興味の対象となる。

"そのような法すべて"からなる集合に2が含まれるか? がオリジナルのコラッツの問題に相当する。

定義域の拡張整数全体への拡張正整数だけではなく、負数も含む任意の整数から開始するコラッツ数列について考えることができる。このとき、自明なサイクル0→0を除いて、合計4つの既知のサイクルがあり、知られている限りでは任意の0でない整数は以下に示された4つのサイクルのいずれかに到達する。

以下の表において、奇数の値は太字で示されている。また各サイクルは、最小絶対値の要素を先頭にしている。

サイクル奇数値のサイクル長全サイクル長 1, 4, 2, 1 ... 1 3 −1, −2, −1 ... 1 2 −5, −14, −7, −20, −10, −5 ... 2 5 −17, −50, −25, −74, −37, −110, −55, −164, −82, −41, −122, −61, −182, −91, −272, −136, −68, −34, −17 ... 7 18

一般化されたコラッツの予想は、による反復の下で、すべての整数が最終的に上記の4つのサイクルの1つ (または0→0の自明なサイクル) に入るという主張である。

分母が奇数である有理数への拡張コラッツ写像は、分母が奇数である既約分数に拡張できる。ここで偶奇性の判定は分子の偶奇性によって判定し、それ以外は定義域が整数の場合と同様に行う。すなわち、分子が偶数であれば2で割り、奇数であればその有理数に3を掛けて1を足すこととする。「ショートカット」した定義を使用する場合、任意の周期的かつ既約なパリティ列(2を法とした余りの列)は一意な有理数によって生成されることが知られている。逆に、分母が奇数であるすべての有理数は、周期的なパリティ列を持っていると予想されている (周期性予想、periodicity conjecture)。

長さのパリティ列が奇数を正確に個含むとして、そのインデックスをで表すとすると、パリティサイクルを生成する有理数が次のように決定される：

例えば、長さ7のパリティサイクルは、0, 2, 3, 6 の位置にパリティ1 (すなわち奇数) が存在している。従って , と置くと、周期列を生成する有理数が次のように求まる。

これは、下記の有理数のサイクルとなり、パリティは確かにの周期となっていることがわかる。

の巡回置換は、上記の分数の1つに関連付けられる。例えば、サイクルから同様の手順で有理数を得ると

となり、先の例で得たサイクルの2番目に対応している。

コラッツ予想が正しいことを仮定すると、とが正の整数（それぞれ1と2）によって生成される唯一のパリティサイクルであることが示される。

有理数の分母が3の倍数でない場合、この拡張されたコラッツ数列はすべて同じ分母を持ち、このとき分子の列はコラッツ関数の「」への一般化を適用することによって得ることができる。

2-進整数環への拡張有理数と類似の拡張として、コラッツ写像の2-進整数環への拡張が挙げられる。この環は部分環として奇数分母の有理数全体からなる環を含んでいる。このとき写像は

で与えられ、これは上でwell-definedな連続写像であり、かつハール測度を保存する。加えて、その力学系はエルゴードであることが知られている。

実数・複素数への拡張

コラッツ写像は、整数時に元々の定義と一致するように実数に拡張することができる。これは補間関数と呼ばれる。これを行うには、下記を満たす２つの関数を適当に決めればよい。

そしてこれらを使って下記のようにコラッツ写像を定義できる： .

との選択肢として、例えば、とを選ぶことができる。

実直線上でのこの写像の反復については、マーク・チェンバーランドの研究によると、この関数は実直線上に無限に多くの不動点を持ち、また反復合成について単調に無限大に発散する軌道も持つ。

の正の不動点を小さい方からとおく。このとき、の範囲には周期アトラクターがちょうど2つ存在して、1つは、もう1つはである。サムネイル|複素コラッツ写像のジュリア集合。色がついている点はすべて無限遠へ発散する。 Letherman, Schleicher および Wood はこの関数の研究を複素平面へと拡張した。ほとんどの複素平面上の点は無限遠へと発散するが、境界となるジュリア集合はフラクタル図形を描く。

複素関数で定義する方法は他にもたくさんある。たとえば、正弦関数と余弦関数の代わりに複素指数関数を使用する方法がある：

この場合異なるダイナミクスを示す。例えばでは、となり発散する。この定義に対応するジュリア集合は、右図のようになる。"haris"や"rays"と呼ばれる無数の構造がある。

検証計算の最適化時間と空間のトレードオフ上記の剰余列により、コラッツ数列の計算の高速化が可能である。

（剰余列節の関数を使ったとして）ステップ先にジャンプするために、まず現在の数値を2つに分割する：（2進数表記で下位ビット）と、（残りの上位ビット）。ステップをジャンプした結果は以下になる：

(もしくは )と配列は、ビットの数すべてについて事前計算しておく。はに関数を回行った数で、はその間に登場した奇数の数である。例えばなら5ステップのジャンプが可能で、そのために下位5ビットを分割して、下記配列を使う：

これは、個の事前計算とストレージが要求される。これにより計算速度が倍高速化出来るが、時間と空間のトレードオフである。

剰余類による制限コラッツ予想の反例を探すにあたって、上記の事前計算を使うと加速させることができる。もし、与えられたとで、不等式

が成り立ったとすると、すべてのについても成立する。そうすると、最初の反例（存在するとして）は、を法としてと合同ではないと言える。

例えば、最初の反例は必ず奇数である。なぜならばで、よりも小さいからである。同様に、最初の反例はで3と合同である。なぜならば、で、より小さいからである。コラッツ予想の反例でないすべてのには、上記不等式が成立するが存在する。なので、ある数のコラッツ予想の検証するとき、合同なクラスを検証するとよい。が増加したときの検証は、より小さいで除外されなかったについてのみ検証すればよい。指数関数的に小さい割合だけが残ることになる。例えばでは、だけが残る。

類似の問題関数 f の定義を少し変えることにより、コラッツの問題の類似を考えることができる。変数nが奇数の時の乗数の奇数一般への拡張による類似問題例えば「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 2m – 1 (m ≥ 1)をかけて 1 を足すという操作を繰り返すと、有限回で 1 に到達する」という命題を考える。m = 1 のとき（nが奇数なら単に1を足す）は、この命題が正しいことを簡単に証明できる。m = 2 の場合が上述のコラッツの問題である。m ≥ 3 の場合は、mの値とnの初期値によっては、1を含まない繰り返し数列、もしくは際限なく増大していく数列が得られるため、この命題は一般に成り立たない。たとえば m = 3 の場合、nの初期値を13に設定すると、13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13 という1を含まない数列のサイクルが得られる。これは上記のヒューリスティクスの観点からして、mが大きくなるほど1に到達する可能性は低くなると予想されることとも符合する。

変数nが奇数の時の加算数の奇数一般への拡張による類似問題また、もう一つの類似として、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3をかけて 2l - 1 (l ≥ 1) を足すという操作を繰り返すと、有限回で 1 に到達する」という命題を考える。ここで、l = 1 のときが上述のコラッツの問題である。しかし、l ≥ 2の場合、1を含まない繰り返し数列が得られる場合があるので、この命題は一般に成り立たない。

たとえば、l = 2として、初期値n = 43を与えた場合、43, 132, 66, 33, 102, 51, 156, 78, 39, 120, 60, 30, 15, 48, 24, 12, 6, 3, 12, 6, 3という数列が得られ、この命題は成り立たない。初期値nが1, 2などなら有限回で1に到達するが、他の初期値に対しては3, 12, 6, 3と、3を繰り返すサイクルになると思われる。そこでl = 2に対してコラッツの予想を応用し、「任意の正の整数 n に対して、上記の操作を行えば、有限回で1または3に到達する」という命題を代わりに立てれば、これが成り立つと予想される。

この二つの予想を一般化して、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 3をかけて 2l – 1 (l ≥ 1) を足すという操作を繰り返すと、有限回で1または2l – 1 (l ≥ 1) に到達する」という命題を立てたとしても、l ≥ 3以上の場合には、この命題は一般に成り立たない。たとえばl = 3の場合、任意の自然数nが1または5に到達するという命題になるが、n＝13の時、13, 44, 22, 11, 38, 19, 62, 31, 98, 49, 152, 76, 38, 19と、19を繰り返す無限ループになり、1にも5にも到達しない。

ただし、上の、2l – 1 (l ≥ 1) が、0以上の整数aを用いて3a–1 (a ≥ 1) で表されるときには、上記のプロセスを繰り返せば、有限回数で1または3a–1 (a ≥ 1) に到達することは予想される。a = 1の場合がコラッツの問題である。a = 2の場合は、上記でl = 2のケースである。

変数nが奇数の時の乗数と加算数双方の、奇数一般への拡張による類似問題以上のことから、一般化は困難ではあるが、個別に考えるなら、さらに進んで、「任意の正の整数 n に対して n が偶数の場合、n を 2 で割る n が奇数の場合、n に 2m – 1 (m ≥ 1) をかけて、2l – 1 (l ≥ 1) を足すという操作を繰り返すとき、n、m、lの値に応じてどのような数列が展開されるか」

という問題にも拡張できるなど、コラッツの問題の類似問題の幅は広い。

ギャラリー

参考文献

関連文献『数学100の問題』日本評論社　「角谷の問題」として取り上げられている。『数学の魔法の宝箱』イアン・スチュアート (数学者) SBクリエイティブ：「コラッツ＝シラキュース＝ウラム問題」として紹介されている。

コラッツの問題

Źródło i licencja