コラッツ予想の類似を考えてみよう

トップページ > おもしろ科学実験室（工学のふしぎな世界） > コラッツ予想の類似を考えてみよう

おもしろ科学実験室（工学のふしぎな世界）

コラッツ予想の類似を考えてみよう

2026年4月9日
横浜国立大学数物・電子情報系学科数理科学教育プログラム
教授　原下秀士

1．はじめに

皆さん、コラッツ予想（Collatz conjecture）をご存知でしょうか？自然数nに対して、次の操作を考えます。

自然数nに対してTを2回繰り返し施すとT(T(n))になるが、これをT²(n)と表します。同様にnにTをk回施すとT^k(n)が得られます。コラッツ予想は、どのような自然数nに対しても、Tを何回か施すと1なる（つまり、ある番号kがあり、T^k(n)=1となる）という予想です。この予想は3n+1問題（3n+1problem）と呼ばれることもあります。

数学にはいろんな予想がありますが、まずは例で確かめると、その予想を理解することができます。例えば、n=3の場合はT(3)=10,T(10)=5というように計算していくと

という具合に1に到達しますし、n=127なら

のように、少し長くなるものの最終的には1になります。コラッツ予想は、どのような自然数から始めても、必ず1に到達すると予想しています。現在2⁷¹以下の自然数すべてで正しいことがコンピュータを用いて確かめられています（cf.[1]）が、すべての自然数nに対して正しいと言うためには証明が必要です。このコラッツ予想は、複数の高額な懸賞金がかけられている有名な未解決問題です。皆さんもチャレンジしてみてはいかがだろうか。

2．その類似を考えてみる

ここでは、もちろんコラッツ予想を解決するといったことはできませんが、その類似の問題を考察して、その類似については解決できるというお話を紹介したいと思います。

類似を構成するアイデアは、自然数の代わりに多項式を用いるという方法になります。ただし、多項式の係数は0と1だけで、0,1の和や積はコンピュータの中で行われている演算を採用します。つまり、和と積について

が成り立つとします。そして、これらを係数にもつ多項式、例えば

などを考えます。これらの多項式の和や積は通常のように計算しますが、係数の和や積が出てくるときは、それは上の計算方法に従うとします。例えば

といった具合です。以下、多項式と言えば、係数が0か1のもののみを考えます。つまり次のような形のものです。

(a_i=0,1)．このf(x)に対し、nをf(x)の次数といいdegf(x)と表します。また、a₀はf(x)の定数項と呼ばれます。

コラッツ予想の操作の類似は

とし、コラッツ予想の類似は、0ではない、任意の（係数が0か1の）多項式f(x)に対して、ある番号kがありT^k(f(x))=1となると予想します。これを「コラッツ予想の多項式類似」と呼ぶことにしましょう。例えば、x²+1からスタートしてみると

といった具合に1に到達する。操作Tについて類似と言っているのは、xに2を代入すると、コラッツ予想と同じ操作であるからです。また、自然数」と「多項式」をどのように類似と見做しているかは、2進展開の表示と多項式の表示の類似に依拠しています。たとえば、19を2進展開してみると

となるので、これの多項式類似は

と考えます。同様に

の類似は

であり、これらのそれぞれの足し算を考えてみると

となり、類似が綺麗に成り立っていることが分かります。ただ、これは偶然（しかし時折起こる現象）です。例えば

とその類似

を考えると

であるが

となり、19+6とf(x)+h(x)は類似の関係が綺麗になっていません。この違いは、いわゆる「繰り上がりが有るか、無いか」の違いから来ていることがお分かり頂けるでしょうか？今回のコラッツ予想の類似と言っているものは、「繰り上がりがない数の世界」でのコラッツ予想と考えてよいでしょう。「繰り上がりがない数」を数学的に正確に表現したものが、上で紹介した「係数が0か1の多項式」というわけです。

3．コラッツ予想の多項式類似の証明

ここでは、コラッツ予想の多項式類似が正しいことの証明を紹介します。0ではない（係数が0か1の）多項式f(x)に対して、次の操作を導入します。

定数項が0の場合、SはTと同じで、これはxで割る操作であるから、次数が一つ下がります。定数項が0でない（1である）場合は

と置くと

であることが分かります。

なので、Sで次数は変わりません。deg(S(f(x)))=degf(x)．

定数項が0でない多項式f(x)について、f(x)=1であれば、ある自然数mが唯一つあって、f(x)は次の形(x^mの項がありxⁱ(1≦i≦m−1)の項が無い)で書けます。

このとき、f₀(x) は

の形になるから、m > 1 なら

の形となります。よってm>1ならS(f(x))に対するmは一つ小さくなるし、m=1ならS(f(x))の定数項は0になります。よって、S^m(f(x))は定数項が0になり、次にTを施すと次数が下がります。

以上により、0や1でない任意のf(x)に対して、Tを施していくと次数がどんどん小さくなっていくことが分かるので、Tを有限回施すと1になる（コラッツ予想の多項式類似は正しい）と結論付けられます。

4．まとめと考察

この記事では、コラッツ予想の多項式類似を考えて、その予想が正しいことを確認しました。実は整数論では、自然数と上のような多項式の類似を考察することがよく行われています。例えば、自然数が素数の積で書かれるように、多項式は既約多項式（これ以上因数分解できない多項式）の積で書かれるため、既約多項式は素数の類似の概念と考えられます。X以下の素数の個数π(X)に深く関係するRiemann予想は整数論で最も有名な予想ですが、その多項式類似（次数がd以下の既約多項式の個数に関するもの）を考えることができ、その多項式類似は容易に証明できることが知られています。

図1　y =P₂₀(x)(xは自然数)

また、ABC予想についても、多項式類似が考えられ、それは容易に証明できることが知られています（[3,定理5.2]参照）。これらの予想のように、多項式類似の場合に成立することが、自然数の場合でも成り立つと予想する根拠とされている場合も多いのです。

今回の記事では、そのコラッツ予想版を考えてみました。この記事を書きながら、先行文献を探したところ、やはり同様のことを考えた研究が有りました（[2]など）。流石に学術論文のため、この記事より深い研究がなされています（例えば、与えられたf(x)に対して、1に到達するために必要なTの回数の上からの“良い”評価が与えられています）。

図2　y=N₂₀(x)(xは自然数)

ただ、コラッツ予想の多項式類似においても更に深く考察すると、様々な未解決問題を考えることが出来ます。つまりf(x)に対してTを何回施せば1になるかを、実際Tを施していって実際何回と答えるより効率的な方法はあるかという問い、もしくは、より洗練した言い方をすると、どれくらい効率化できるかという問いが考えられます。その他、その回数の分布はどうなっているかという問いも興味深いと思われます。つまりd次以下の多項式でk回Tを施して（初めて）1となるものの個数P_d(k)の分布を求めよという問題を考えてみます。d=20のときは、図1のようになります。このグラフを適切に近似する関数（kの偶奇に従って、2つの関数がある）がありそうだが、それを求めよという問いになります。皆さんも、考えてみてはいかがでしょうか？

自然数の場合にも同様の分布、つまり2^d以下の自然数でk回Tを施して1になるものの個数N_d(k)を考えてみる。d=20のとき、図2のようなグラフが得られ、多項式のときに比べ、複雑になっていることが分かります。繰り上がりがあるだけで難しさが極端に難しくなっていることが想像できます。皆さんが算数や数学の計算で繰り上がりに悩まされているように、数学者も（より深い意味で）繰り上がりに悩まされていると言えるのかもしれません。