\begin{eqnarray}
\zeta_{a}^{p}(s_1,s_2,\dots,s_r)-\zeta_{a+1}^{p}(s_1,s_2,\dots,s_r)={(a+1)^{-s_1}}\zeta_{a+1}^{p+1}(s_2,s_3,\dots,s_r)
\end{eqnarray}
\begin{eqnarray}
\zeta_{a}^{p}(s_1,s_2,\dots,s_r)-\zeta_{a+1}^{p}(s_1,s_2,\dots,s_r)={(a+1)^{-s_1}}\zeta_{a+1}^{p+1}(s_2,s_3,\dots,s_r)
\end{eqnarray}イコールの左と右で何が違うのでしょうか?(私は左利きです)重要なことに気づきました。右辺のゼータの変数が減っている!!!!
ということは?これを上手に使えば変数を一つにまで減らせる????具体的に行動してみましょう!$a=0,p=5,r=3$です\begin{eqnarray}\\
\color{#f50}\zeta_{0}^{5}(s_1,s_2,s_3)-\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)&=&{1^{-s_1}}\color{#99f}\zeta_{1}^{6}(s_2,s_3)
\\\\\color{#99f}
\zeta_{1}^{6}(s_2,s_3)-\color{#9ff}\zeta_{2}^{6}(s_2,s_3)&=&{2^{-s_2}}\zeta_{2}^{7}(s_3)
\end{eqnarray}ちょっと待って$\zeta_{2}^{7}(s_3)$はいいとして、$\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)$とか$\color{#9ff}\zeta_{2}^{6}(s_2,s_3)$ってどうやって求めるんですか?\begin{eqnarray}
\zeta_2^7(s_3)= 3^{-s_3}+4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3}
\end{eqnarray}は求められますね$\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)$ですが、これも上記のようにすればいいんじゃないですか???つまり、\begin{eqnarray}\\
\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)&-&\color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)&=&{2^{-s_1}}\color{#9ff}\zeta_{2}^{6}(s_2,s_3)
\\\\\color{#9ff}
\zeta_{2}^{6}(s_2,s_3) &-&\color{#09f}\zeta_{3}^{6}(s_2,s_3) &=&{3^{-s_2}}\zeta_{3}^{7}(s_3)
\end{eqnarray}この$\color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)$と$\color{#09f}\zeta_{3}^{6}(s_2,s_3)$も同じことすればいいんじゃないですか???\begin{eqnarray}\\
\color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)&-&\color{#f90}\zeta_{3}^{5}(s_1,s_2,s_3)&=&{2^{-s_1}}\color{#09f}\zeta_{3}^{6}(s_2,s_3)
\\\\\color{#09f}
\zeta_{3}^{6}(s_2,s_3) &-&\color{#0f9}\zeta_{4}^{6}(s_2,s_3) &=&{3^{-s_2}}\zeta_{3}^{7}(s_3)
\end{eqnarray}うわ、ぐちゃぐちゃになってきました。もうちょっと綺麗に図にしたいですね。どうしようかな、綺麗に図を描けるやつとかあったかな、、、\begin{xy}
\xymatrix {
\zeta_{0}^{5}(s_1,s_2,s_3)
&\zeta_{1}^{5}(s_1,s_2,s_3)
\ar@//[l]
& 1^{-s_1} \zeta_{1}^{6}(s_2,s_3)
\ar@//[l]
&\zeta_{1}^{6}(s_2,s_3)
\ar@{.>}[l]
&\zeta_{2}^{6}(s_2,s_3)
\ar@//[l]
& 2^{-s_2}\zeta_{2}^{7}(s_3)
\ar@//[l]
&\zeta_{2}^{7}(s_3)
\ar@{.>}[l]
\\
\zeta_{1}^{5}(s_1,s_2,s_3)
\ar@//[ur]
&\zeta_{2}^{5}(s_1,s_2,s_3)
\ar@//[l]
&2^{-s_1} \zeta_{2}^{6}(s_2,s_3)
\ar@//[l]
&\zeta_{2}^{6}(s_2,s_3)
\ar@{.>}[l]
\ar@//[ur]
&\zeta_{3}^{6}(s_2,s_3)
\ar@//[l]
&3^{-s_2}\zeta_{3}^{7}(s_3)
\ar@//[l]
&\zeta_{3}^{7}(s_3)
\ar@{.>}[l]
\ar@/_/[u]
\\
\zeta_{2}^{5}(s_1,s_2,s_3)
\ar@//[ur]
&\zeta_{3}^{5}(s_1,s_2,s_3)
\ar@//[l]
&3^{-s_1} \zeta_{3}^{6}(s_2,s_3)
\ar@//[l]
&\zeta_{3}^{6}(s_2,s_3)
\ar@{.>}[l]
\ar@//[ur]
&\zeta_{4}^{6}(s_2,s_3)
\ar@//[l]
&4^{-s_2}\zeta_{4}^{7}(s_3)
\ar@//[l]
&\zeta_{4}^{7}(s_3)
\ar@{.>}[l]
\ar@/_/[u]
\\
\zeta_{3}^{5}(s_1,s_2,s_3)
\ar@//[ur]
&\zeta_{4}^{5}(s_1,s_2,s_3)
\ar@//[l]
&4^{-s_1} \zeta_{4}^{6}(s_2,s_3)
\ar@//[l]
&\zeta_{4}^{6}(s_2,s_3)
\ar@{.>}[l]
\ar@//[ur]
&\zeta_{5}^{6}(s_2,s_3)
\ar@//[l]
&5^{-s_2}\zeta_{5}^{7}(s_3)
\ar@//[l]
&\zeta_{5}^{7}(s_3)
\ar@{.>}[l]
\ar@/_/[u]
}
\end{xy}
ありましたねxymatrix
が。上のような感じで綺麗に書けました。(矢印を白くできなかったので文字は黒、背景は#9aaにしています)さて、一番右のやつらは計算できますし、計算するときに一つ下で計算した値を使いまわせますね。例\begin{eqnarray}
\zeta_2^7(s_3) &=& 3^{-s_3}+4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3} \\
\zeta_3^7(s_3) &=& 4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3} \\
\therefore \zeta_2^7(s_3) &=& 3^{-s_3}+\zeta_3^7(s_3)
\end{eqnarray}じゃぁ、$\zeta_{4}^{5}(s_1,s_2,s_3)$や、$\zeta_{5}^{6}(s_2,s_3)$はどうやって求めるの?これはもう、定義に沿った方が早いです。定義より、\begin{eqnarray}
\zeta_{4}^{5}(s_1,s_2,s_3) &=& \sum_{4 < n_1< n_2< n_3< 5+3} n_1^{-s_1}n_2^{-s_2} n_3^{-s_3} \\
&=& 5^{-s_1} + 6^{-s_2} + 7^{-s_3} \\
\zeta_{5}^{6}(s_2,s_3) &=& \sum_{5 < n_1< n_2< 6+2} n_1^{-s_2} n_2^{-s_3} \\
&=& 6^{-s_2} + 7^{-s_3} \\
\end{eqnarray}あれ、これも計算結果を使いまわせますね。\begin{eqnarray}
\zeta_{4}^{5}(s_1,s_2,s_3) &=& 5^{-s_1} + \zeta_{5}^{6}(s_2,s_3)
\end{eqnarray}これで、矢印を上手に辿って戻ることで、$\zeta_{0}^{5}(s_1,s_2,s_3)$を求めることができます!!!! では、もとめられると分かったとして、結局これの計算量はどのぐらいになっているのでしょうか???$p$と$r$が上の図でどこに当たるのかですが、縦の大きさは$p-1$行、横は$r$列あるように見えますね(点線の矢印で区切ると3つのセクションに分かれる)と、いうことは、、、、、、、、、、、、、、、、、、、、、いうことは、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、あれ、計算量$\mathcal{O}( p \cdot r)$では????????
前の記事を思い出してみてください。で、計算量はどのくらいになるのかというのを見積もると、超大雑把にみて$\mathcal{O}(p^r)$くらいかなぁと考えました。
(javascript
の四則演算の計算量のオーダーがはっきりとしないので、
ここでいう計算量はループの数ということにして、計算量を比較していきます。)
ここで、$p$と$r$は$\zeta_a^p(s_1,s_2,…,s_r)$から来ています。
実用的には$p$のほうが$r$よりもずっと大きく設定するので、これでいいでしょう。
これ、指数レベルのオーダーなので、多変数&精度を求められると、計算時間が爆発してしまいます。
さて、$\mathcal{O}(p^r)$というのは、ループの数のオーダーなのですが、
これをいかにして減らすのでしょうか???????
あれ、指数時間でしたね。ということは?指数時間→多項式時間
\\\\指数時間→多項式時間////