アルゴリズムを数式に接続する

きっかけ

最近、「素数の音楽」という本を読んで、その中で「すべての素数を生み出す数式」というのが紹介されていたのに強いインスピレーションを受けた。普通の数式ではないが、明らかに多項式で、不思議な数式だ。この数式がどのようにして得られたのかにも興味をそそられるが、たぶん、僕の知力では追いつかないだろう。それよりも、素数を生み出すというようなアルゴリズム的な機能を数式に落とし込んでいるという点に感銘を受けた。そして、僕はどのような課題をクリアすれば、アルゴリズムを数式に落とし込めるだろうかと考え始めた。すぐにアイデアが浮かび、詳細を詰めた。全てではないが、単純なアルゴリズムであれば、比較的容易に落とし込みが可能だと今は思っている。

素数公式

今や電子暗号技術の根幹を成す素数は、数学のみならず全ての人類にとって重要な問題となっている。特に数学では、ギリシア時代から延々と議論が続いている。例えば、「ある数N以下の素数はいくつあるか」という素数の数え上げ問題などだ。
素数の数え上げ問題に最初に肉薄したのは、カール・フリードリヒ・ガウスだ。$N$以下の素数の数を$\pi$とおくと
\begin{equation}\pi\left(N\right)\propto \log{N}\end{equation}
という大まかな分布にたどり着いた。実際には、もう少し詳しいところまで到達しているが、驚くべきはその成果が若干15歳で達成されたことだ。ガウスの天才が規格外であることを示すエピソードとして有名だ。
以来、多くの数学者が素数の数え上げ問題にかかわったが、転機となったのはゲオルク・フリードリヒ・ベルンハルト・リーマンだ。リーマンは素数の数え上げに言及し、おそらく完全に素数の数え上げに対応する関数を示した。
リーマンの示した方法で素数の数え上げを行うには、ゼータ関数の非自明な０点がある特徴的な直線に並んでいる必要があることがわかっており、「リーマン予想」と呼ばれている。人類が調査可能な範囲において、リーマン予想は正しいことがわかっているが、リーマン予想が「完全に」正しいという証明は存在していない。このリーマン予想を証明することは数学における大問題となっている。ま、僕にはよくわからない世界だ。

リーマン予想は証明されない方が人類にとって良いかもしれないという意見もある。リーマン予想が正しいとなると、我々は素数を見つけるためのもう一つのアルゴリズムを手にすることになる。現在の暗号技術は素数を見つけるのが困難だという数学的経験則に基づいて成立しているのだが、リーマン予想によって別の素数探索法が現れる可能性がでてくる。すると、これまでの経験則が崩れて暗号技術全体が崩壊する可能性が出てくる、というのだ。

素数の探索

素数の探索は、プログラミングの格好の教材で、プログラマなら何度かつくったことがあるだろう。もっとも単純なものは次のようなものだ

ある数Nが素数かどうかを調べるために、Nを２～N‐１までの整数で割り算し、割り切れるかどうかを調べる。もし、一度も割り切れなければNは素数である。

JavaScriptで書けば次のようになるだろう。
function IsPrime(N) {
    var i
    for(i=2; i<N; i++) {
    if( (N % i)==0) return 0;
    }
    return 1;
}

話の都合上、$IsPrime$関数は$N$が素数の時に１を返し、素数でない時は０を返す関数として設計してある。
これは最も単純なので、計算に無駄が多い。計算の無駄を少なくすることでプログラムを高速化する手段はいくつも存在するので、素数の探索プログラムは、アルゴリズムの性能アップを学ぶ格好の題材なのだ。僕の目的はアルゴリズムを数式に変換することなので、もとになるアルゴリズムは効率よりも単純さが重要だ。だから、これでよい。

素数判定アルゴリズムを使うと素数の数え上げが簡単に作成できる。すなわち、
\begin{equation} \pi\left(x\right)=\sum_{N=2}^{x} IsPrime(N) \label{algopi} \end{equation}
一方リーマンの素数公式はもっと複雑で、
\begin{equation}
{\displaystyle \pi (x)=\sum _{m\leqq \log _{2}x}{\frac {\mu (m)}{m}}\left({\rm {li}}(x^{\frac {1}{m}})-\sum _{\rho }{\rm {li}}(x^{\frac {\rho }{m}})-\log 2+\int _{x^{\frac {1}{m}}}^{\infty }{\frac {dt}{t(t^{2}-1)\log t}}\right)}
\label{Riemann}
\end{equation}
になるらしい（Wikipediaより）。

アルゴリズムを数式にする

アルゴリズムによる素数の数え上げ式($\ref{algopi}$)とリーマンの素数公式($\ref{Riemann}$)は、複雑さが段違いということにすぐ気づく。リーマン予想が正しいとすると両者は同じ値を与える関数であるはずだ。ということは、両者の複雑さの違いは$IsPrime$関数に由来する。もし、$IsPrime$関数を普通の式で書き下せば、リーマンの素数公式に一致（あるいは類似）するのだろうか？という疑問を僕は持った。
ということで、$IsPrime$関数を数式に変換することを考えよう。Javascriptで例示したプログラムでは、for構文とif構文が１回ずつ使われている。これらを数式に置き換えることができるだろうか？
for構文の部分は$\sum_{i=2}^{N-1}$に極めて近い。$\sum$は和をとるが、プログラムでは、実は論理積がとられている。なので、積をとる$\prod$の方が近い。つまり、
\begin{equation}
\prod_{i=2}^{N-1} if\left(mod(N,i)\ne 0\right)
\end{equation}
ただし、$mod(N,i)$は$N$を$i$で割った時の余りを値とする関数とする。また、$if$関数は
\begin{equation}
if(x)=\left\{\begin{matrix}0&{if\ x\ is\ false}\\1&{if\ x\ is\ true}\end{matrix}\right.
\end{equation}
となっていると都合がよい。
ここで定義した$if$関数はプログラミングテクニックとして比較的なじみ深いもので、いくつかの言語では条件分岐に関してこのような実装を行っている。
さて問題は、このような$if$関数が通常の演算で実現できるだろうか？ということだ。リーマンの素数公式で使われている数学要素は、足し算、引き算、掛け算、割り算、積分、複素数、無限といったところだ。だから、僕たちは$IsPrime$関数をこれらの要素で構成しなければならないだろう。$if$関数に極めて近い関数に、$sgn$関数がある。
\begin{equation} sgn\ x =\left\{ \begin{matrix}-1&{if\ x\lt 0}\\0&{if\ x=0}\\1&{if\ x\gt 0}\end{matrix}\right. \end{equation}
$sgn$関数は別名を符号関数という。極めて便利だけど、残念ながら人工的すぎて、上述の数学要素で直接構成できるわけではない。この$sgn$関数に似た関数の一つにHilbert変換のインパルス応答関数$H(q)$がある。
\begin{equation} H(q) =\left\{\begin{matrix}-i&{if\ q\lt 0}\\0&{if\ x=0}\\i&{if\ q\gt 0}\end{matrix}\right. \end{equation}
これはインパルス応答関数なので、実空間のタイプがあって、
\begin{equation} H(q) =\int_{-\infty}^{\infty} \frac{1}{x}e^{-iqx}dx
\end{equation}

であれば、if関数に類似のものを次のように定義できる。

\begin{equation} if^\prime (x)=\frac{1}{2}+\frac{1}{2i}H(x)
\end{equation}

ただし、０のところだけ、違っている。引数が整数に限定される場合には、

\begin{equation} if (x) \sim if^\prime (x+\delta)\ where\ -1\lt \delta\lt 1
\label{iffunc}
\end{equation}
数学における４つの不等号$\lt,\le,\gt,\ge$に応じて$\delta$が選択される。

数学的な美しさというものが存在するなら、$\delta = \frac{1}{2}$とするのが良いかもしれない。

もし$\delta$関数が使えるなら、$if^\prime$関数は次のようにしてもよい。
\begin{equation}
if^\prime\left(x\right)=\int_{-\infty}^{x}{\delta\left(x\right)dx}
\end{equation}
これは、ヘビサイド関数として知られている。要は、$if^\prime$関数というのは、極めて人工的だけれど、通常の数学の概念と親和性があるということだ。

余りを計算する

プログラムに見られる構文は２つだけだが、実は余りの計算がもう一つの関門になっている。あまりの計算は通常の演算では作り出せない。そこで、$N$を$M$で割ったときの余りを返す$mod(N,M)$という関数を$if$関数を使って構成することを考える。
当たり前のことだけど、$N=pM+r$を満たす$0\le r\lt M$なる$r$を見つけることがミッションになる。いろんな方法が考えられるが先に$p$を見つけることを考えた方が実は近道かもしれない。すなわち、$r=N-pM$というわけだ。$p$を見つける最もシンプルな方法の一つが次の数式だ。
\begin{equation}
p=\sum_{m=0}^{\infty}if(N-mM)
\end{equation}
これを使うと$mod$関数は簡単で、
\begin{equation}
mod(N,M)=N-M\sum_{m=0}^{\infty}if(N-mM)
\end{equation}

以上をまとめると、

\begin{equation}
IsPrime(N)=1-if\left(\prod_{M=2}^{N-1}mod(N,M)\right)
\end{equation}

となる。

めだたく、新しい素数公式が次のように得られる。

\begin{equation}
\pi(N)=\sum_{n=2}^{N}\left\{1-if\left(\prod_{M=2}^{N-1}\left[n-M\sum_{m=0}^{\infty}if(n-mM)\right]\right)\right\}
\label{final}
\end{equation}

これは素数公式か？

アルゴリズムから出発したので、上式は素数公式であることが確実だ。ただし、$if$関数にフーリエ変換があり、精密な数値計算には向かない。また、途中に∞個の総和があり、計算量の見通しが難しい。また、アルゴリズムが有する計算量を完全に反映する。もっとも愚直なアルゴリズムから出発しているため、効率の面では最低だ。

この式の計算を進め、欠点を補えれば、使い物になるかもしれないが、僕は悲観的だ。重要なのは実用面ではなく、アルゴリズムを普通の解析関数に落とし込んだ点だと僕は思っている。ここまで落とし込めば、アルゴリズムという散文的な概念を数式という伝統的な数学で議論することが可能になるからだ。

リーマンの素数公式の驚くべき点は、素数という典型的な数論の概念を解析関数という別の数学概念に接続している点だ。ここで議論した$mod$関数は数論の世界を解析接続するための基本ツールの一つだ。もう一つのツールは$if$関数だ。ここでは$if$関数を使って$mod$関数を構成したが、その逆も可能だ。そこから、$if$関数と$mod$関数はある種の「同値」関係にあることがうかがえる。

ここに至り、僕は一つの仮説を持っている。リーマンの素数公式というのは、ある種のアルゴリズムを解析接続したものだというものだ。リーマン予想を証明する代わりに、素数探索アルゴリズムの解析接続をいろいろ試すというアプローチがあるんじゃないだろうか。僕は$if$関数を梃子にしたが、それはプログラマとしてはとても自然な発想だ。でも、$mod$関数が$if$関数で構成できるように、梃子として用いることができる数学的ツールはほかにもあるだろうことがうかがえる。

僕がここであらたに導入したのは本質的に$if$関数だけなのだけど、$if$関数だけですべてのアルゴリズムを伝統的な解析関数に変換できるかは不明だ。というのも、プログラミングの世界ではプログラミング言語として万能性を持つために必須な要素というのはもう少し多いからだ。ただ、最小チューリングマシンが極めてシンプルに構成できるという事実は僕たちにとって朗報だ。論理的には最小チューリングマシンの要素をすべてカバーする変換ツールを用意できれば、すべてのアルゴリズムが解析接続できることになるのだから！それは新しいパラダイムを提供するはずだ。

リーマン予想についてのコメント

式($\ref{final}$)とリーマンの素数公式が同じものだと考えると、$if$関数とゼータ関数が何らかの対応を持つことになる。そう思うとリーマン予想についていくつかの推測が得られる。式($\ref{iffunc}$)にあるように、$if^\prime$関数の引数が０になることを避けるために、不自然なオフセットが付け加える必要がある。そのオフセットはある範囲で自由であり、それを$1/2$とするのは自然に思える。逆に言うと、$1/2$でなくてもい。リーマン予想はゼータ関数の０点の実部が$1/2$であるというものであるが、それが$if^\prime$関数に付け加えるオフセットと対応するかもしれない。
例えば、式($\ref{final}$)に半整数を入力してみると、計算が破たんする。そうした破たんは半整数の場合にだけ顕著に生じる。つまり、特異点だ。ただし、入力が素数-1/2の時は、$if^\prime$関数が０になることがない。リーマン予想の$1/2$が式($\ref{iffunc}$)で付け足した$1/2$と対応しそうな感じがするでしょ？
そうすると、ゼータ関数の０点が$1/2$である必然性はないことになる。つまり、$if^\prime$のオフセットと同様に１以下の一定値であればよい、という話かもしれない。であれば、なぜ$1/2$なのかを説明するのは極めて難しいということが推測される。まずは、一定値だということを示すべきなんだろう。
$if^\prime$関数が０になるとは、約数を持つ＝素数でないということだから、ゼータ関数の０点も素数でないことを示しているのかもしれない。０点という特別な性質なんだから、特別な性質をもつ素数と何らかの対応を持つだろう、と勝手に思い込んでしまっていないだろうか。式($\ref{iffunc}$)は、そういう先入観とは真逆の可能性を強く示唆していると思う。であれば、ゼータ関数の０点がほぼ等間隔である理由も思い当たる。ゼータ関数の０点はエラトステネスのふるいであるかもしれないということだ。ふるいの目（穴）は等間隔に開いているものだ。
すでに指摘したがリーマンの素数公式は数論の問題を解析接続してしまうという驚きの成果であり、どうしてもそれに目を奪われてしまう。つまり、意味がきちんとしているのは整数の入力だけなのに、複素数の入力が許されてしまうためのにそこに惑わされるのだ。$if$関数を定義するためにどうしても複素数の計算が出てきてしまうわけだが、それがゆえに式($\ref{final}$)も複素数の入力を許してしまう。意味がないとは知りつつ、複素数を入力を試してしまい、その不思議な光景に目を奪われるのだ。

マイルストーン

現時点では、$if$関数以外のツールを僕たちは手にしていないが、どのようなツールが可能かについてちょっとしたアイデアがある。NHKの白熱教室のエドワードフレンケル教授の回でラングランズプログラムの例として、ある方程式の解の数を多項式の係数として得るという奇妙な数式が紹介された。その時は全く理解不能だったが、それはアルゴリズムを数式に変換する全く別の形態であるという気がしている。
プログラマの視点からすると、$if$関数と不自由なループしか使えないというのでは、万能性からは程遠いと言わざるをえない。プログラミング言語が万能性を持つには、複数の変数を取り扱う手段がほしいところだ。なので、アルゴリズムを数式に変換するツールとして、複数の数値を交差計算するツールがほしいということになる。その一つの方法として、代数式の係数が使える。つまり、因数分解された多項式の括弧を外す際に各多項式の複数の係数の積和が実施される。どの係数とどの係数をかけ合わせるかは、変数の次数が制御する。それはある種のアルゴリズムを構成する。
このアイデアを一般化するために、テンソルが応用できる。例えば、２階のテンソルは、2次の多項式と対応させることができるが、それは一つの行列で特徴づけることができる。同様にｎ階のテンソルは、ｎ階の行列で特徴づけることができる。すなわち、変数に対応するベクトルに対し、ｎ階のテンソルの和を考えることで、あらゆる代数式を構成できるだろう。
これまで僕たちはアルゴリズムを一つの値を出力する一つの関数に表現するとしてきたが、そのようなスタイルに適合するアルゴリズムは極めて限定的だ。例えば、ワードプロセッサはそのようなフォーマットにはそぐわないのは明らかだ。別の表現形式として、多項式の係数を利用するということも悪くない。すなわちそれが、NHKの白熱教室で紹介された奇妙な多項式の背後にある数学だと直感している。もしかすると、その方が簡単かもしれない。そのようなテンソル形式で$if$関数を構成するには無限階のテンソルが必要になる。予想としてはそのようなテンソルを使えば、ワードプロセッサのような複雑なソフトウェアを含むあらゆるアルゴリズムを一つの数式として得ることができるだろう、ということだ。