未解決問題による巨大数

以前の記事で東方巨大数5という大会を紹介しました。
昨日(3月26日)、巨大数投稿期間が終了し、総勢64個の巨大数が出そろいました！
予想していた以上にたくさんの数が登場して驚いています。
どの巨大数が優勝するのか今から楽しみですね。

さて、東方巨大数では巨大数を作るにあたっていくつかのルールがあります。
その中の一つが「未解決問題を使ってはいけない」というものです。
正しいのか分からない予想を使って巨大数を作っても、それがどんな大きさになるのかが分からないので審査のしようがありません。

しかし、ここで一つの疑問が生まれます。

未解決問題を使えば大きな数を作れるのか？

今回は未解決問題を使わないといけないという制限の下、巨大数を作れるのかを検証したいと思います。

なお、筆者は数論が全く分かりません。
面白い未解決問題や間違っているところがあれば教えていただけるとありがたいです。

検証方法

• 今回は整数に関する未解決問題に限定して考察します。

• リチャード・K・ガイ著金光滋訳『数論〈未解決問題〉の事典』に載っている整数問題を扱い、この本に載っている"元"未解決問題も考えることにします。この本にはあまりにも多くの問題が載っているので、すべてをこの記事で語ることはできません。

• 「～を満たす数は存在しない」のような形式の未解決整数問題は$${10^{10}}$$程度までコンピュータで検証されている問題が多いため、反例があるならばそれなりに大きな数になることが自明な上、大きさの見積もりが難しいです。
  このような数に関しては、巨大数に関連しそうな数しか扱いません。

• 「～を満たす数は無限に存在する」という形式の予想は、その条件を満たす数を数え上げる関数を構成すればそこそこ大きな関数が簡単に作れてしまいます。
  このような数は、条件を満たす数の列が指数オーダーより急増大しそうなものを扱うことにします。

• その他、個人的に面白いと思った問題も入れることがあります。

それでは見ていきましょう。

素数に関する問題

～の形で表せる素数は無限に存在するか？

ある特定の形で表せる素数が無限に存在するか？という問題はいくつも知られています。
例えば、$${a^2+1}$$や$${2^a-1}$$(メルセンヌ素数)などの形式です。
しかし、これらの素数の分布に関する予想で、指数オーダーを大きく上回るものはありませんでした。

例えば、$${x}$$以下の$${a^2+1}$$型素数の数を$${P(x)}$$とすると$${P(x)～\frac{c \sqrt{x}}{\ln{x}}}$$、
$${x}$$以下の$${2^a-1}$$型素数の数を$${M(x)}$$とすると$${P(x)～ \ln(x)}$$と予想されています。
ここで$${f(x)～g(x)}$$は$${\lim_{x→\infty}\frac{f(x)}{g(x)}=1}$$を表すとします。
ちなみに、素数全体の分布に関しては、$${\pi(x)}$$は$${x}$$以下の素数の数として素数定理$${\pi(x)～\frac{x}{\log{x}}}$$が知られています。

これらの例を見ると分かる通り、2次式や指数程度の条件を満たす素数の分布を用いてもあまり大きな数にはならないようです。
巨大数の土俵に上がるにはもう少し強い条件を課した素数を探さないといけません。

ウィルソン素数

$${m>1}$$が素数であるための必要十分条件としてウィルソンの定理
「$${m>1が素数⇔mが(m-1)!+1を割り切る}$$」
が知られています。

これに関連して、$${p^2}$$が$${(p-1)!+1}$$を割り切るような素数$${p}$$をウィルソン素数といいます。
5, 13, 563がウィルソン素数であることが知られていますが、その後は$${5・10^8}$$まで現れません。
無限に存在するならかなり急増大しそうです。

フィボナッチ型数列の素数

$${u_1}$$と$${u_2}$$が与えられられたとき、$${u_{r+1}=u_{r}+u_{r-1}}$$で定められる数列には無限に素数が含まれるでしょうか？

この問題に関してはあのグラハムが反例を与えています。
$${u_1=1786772701928802632268715130445793}$$
$${u_2=1059683225053915111058165141686995}$$

さらに小さい反例をクヌースが与えています。
$${u_1=49463435743205655}$$
$${u_2=62638280004239857}$$

逆に、このような$${u_1}$$と$${u_2}$$は無限に存在するのでしょうか？
また、$${u_1}$$と$${u_2}$$を数え上げる関数はどのくらいの大きさになるのでしょう？

等差数列

素数のみからなる任意長の等差数列は存在するか？というのは長らく未解決問題でしたが、2004年にテレンス＝タオによって肯定的に解決されました。
これを用いればかなり大きな数が作れそうです。
エルデジュはより一般に$${\Sigma \frac{1}{a_i}}$$が発散するような任意の数列はいくらでも長い等差数列を含むと予想しています。

251,257,263,269のように、連続素数からなるいくらでも長い等差数列は存在するでしょうか？
これは未解決問題です。

ちなみに、素数の差を使うだけではあまり大きな数にはならなさそうです。
$${n}$$番目の素数と$${n+1}$$番目の素数の差を$${d_n}$$として$${d_n>\frac{c\ln{n}\ln\ln{n}\ln\ln\ln{n}}{(\ln\ln\ln{n})^2}}$$
と予想されています。

あるパターンの素数

等差数列や双子素数に関する予想を拡張して、あるパターンの素数は無限に存在するかという問題があります。
たとえば、$${6k-1, 6k+1, 6k+5}$$が素数になる$${k}$$は無限に存在するでしょうか？

この手の問題はしばしば巨大な例が報告されています。
たとえば、2002年にデイヴィッド・ブロードバーストは$${k=61504372896}$$、$${n}$$を$${5119×3163}$$以下の全ての素数の積としたとき、$${N=\frac{(kn(n+1)+210)(n-1)}{35}}$$で$${N+5, N+7, N+11}$$が素数になることを示しました。

ギューガ数

$${n}$$が合成数で、そのすべての素因数$${p}$$が$${\frac{n}{p}-1}$$を割り切るとき、$${n}$$をギューガ数といいます。
最小のギューガ数は少なくとも13800桁であることが知られています。

ギルブレス予想

$${d^1_n}$$を$${n}$$番目の素数と$${n+1}$$番目の素数の差とします。
$${d^{k+1}_n=|d^k_{n+1}-d^k_n|}$$としたとき、すべての$${k}$$について$${d^1_n}$$は1でしょうか？
この予想はギルブレス予想と呼ばれています。
何度も差をとる操作がY数列みたいですよね。

この予想に関してはいろんな意見があるようですので、引用しておきます。

ハラード・クラフトらは、この予想自体は素数と何の関係もないものであり、２と奇数からなる任意の数列は、増加も速すぎず、間隔も大きすぎないから、この数列に対して予想が成り立つと示唆している。オドルィシェコもこの点を議論している。

$${n-2^k}$$が素数になるような$${n}$$

エルデシュは$${1<2^k< n}$$であるすべての$${k}$$に対して$${n-2^k}$$が素数になる$${n}$$は4, 7, 15, 21, 45, 75, 105のみであると予想しました。

この問題はいくつかの派生が知られています。
その一つとして、素数$${p,q}$$と整数$${a>0, b>1}$$を用いて$${\pm{p^a} \pm{q^b}}$$の形で表せない奇数に関するものがあります。
スン・チュー・ウェイは
$${x\equiv 47867742232066880047611079 \mod 664830340250187116398625270490}$$ならば$${\pm{p^a} \pm{q^b}}$$の形で表せないことを示しました。

整除性に関する問題

完全数が無限に存在するか？というのはよく知られた未解決問題です。
ポメランスによって$${k}$$個の異なる素因子を持つ完全数が存在すれば$${(4k)^{(4k)^{2^{k^2}}}}$$より小さいことが示されています。

完全数の類似概念多すぎ問題

さて、完全数のように約数に関する性質を持った数で巨大数に使えそうなものを紹介しようと思ったのですが、完全数の派生と思われる概念が山のように存在します。
なぜ数学者は完全数の派生概念を作りたくなってしまうのでしょう？

ここではこれらの数の名前だけ紹介します。

概完全数　準完全数　擬似完全数　原始過剰数　原始擬似完全数　調和数　調和種数　ウィアード数　多重完全数　実現数　k重超完全数　(m,k)完全数　ユニタリ完全数　ユニタリ多重完全数　親和数　ユニタリ親和数　準親和数　社交数　超完全数　不可触数

約数の和に関する方程式

$${n}$$の約数の和を$${\sigma(n)}$$、約数の個数を$${d(n)}$$で表すことにしましょう。
これらの記法を用いると整数の様々な性質に言及することができます。
例えば完全数は$${\sigma(n)=2n}$$ですね。

$${\sigma(n)}$$を用いて表される様々な方程式が解を無限に持つか？というのは興味深い問題です。
$${m\sigma (m) = n\sigma (n)}$$
$${\sigma(n)=\sigma(n+1)}$$
$${\sigma(p)+\sigma(q)=\sigma(p+q)}$$
$${d(n)=d(n+1)}$$
などの方程式の解について考察する問題は指数オーダーにのる議論が多いようです。

オイラーのトーシャント関数

$${n}$$以下で$${n}$$と互いに素な自然数の数を$${\phi(n)}$$と表記します。
$${\sigma(n)}$$と同じように、$${\phi(n)}$$を用いた方程式が(無限に)解をもつかを問うた問題がいくつか知られています。

ドナルド・ニューマンは$${a, c>0, ad-bc\neq 0}$$を満たす非負整数$${a, b, c, d}$$について$${\phi(an+b)=\phi(cn+d)}$$を満たす自然数$${n}$$が存在することを示しました。
例えば、$${\phi(30n+1)=\phi(30n)}$$の最小の解は1116桁の数であることが知られています。

$${\sigma(\phi(n))=\phi(\sigma(n))}$$のような式に関する考察もされています。

2^a-2^bで割れる多項式

$${2^a-2^b}$$が$${n^a-n^b}$$を割るのはどんな時でしょう？
具体例として$${2^2-2}$$が$${n^2-n}$$を割ること、$${2^{2^2}-2^2}$$が$${n^{2^2}-2^2}$$を割ること、$${2^{2^{2^2}}-2^{2^2}}$$が$${n^{2^{2^2}}-n^{2^2}}$$を割ることが知られています。

スミス数

$${4937775=3\cdot 5 \cdot 5\cdot 65837}$$のように各桁の数の和が、その数の素因数それぞれの各桁の和に等しい数をスミス数と言います。
ちなみに4937775はスミス数を提案したアルバート・ウィランスキーの義理の兄弟の電話番号だそうです。

しばしば巨大なスミス数が報告されており、現在では13614513桁のものが知られています。

加法的数論の問題

ゴールドバッハ予想のように足し算が中心的な役割を果たす問題を加法的数論の問題といいます。

加法的数論の問題は巨大数に使えそうではありませんでした。

今回調べた範囲では、加法的数論の問題で解の分布が予想されているものは凡そ多項式オーダーです。
おそらく、加法が前提にある問題は解くのが難しいので、分布や解が明らかになっていないせいだと思います。
あれこれ考えてみたのですが、私にはわかりませんでした。
加法的巨大数がある方はぜひ教えてください。

まとめ

テトレーションレベルを超えるような関数は出てきませんでした。
これは巨大数で使うような関数は通常の解析学では使いづらく、整数論ではポピュラーではないからだと思います。

素数や整除性を用いた関数は大きな数が散見されました。
素数は研究が進んでいることに加え、そもそも掛け算に関する性質なので、掛け算より強い演算が出てきやすいのだと思います。