自己紹介・記録解説

初投稿

MZV,初投稿,計算量

1096

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

この記事はぜんぜん数学的に厳密ではありません　ゆるして　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

初投稿

MZVの具体値とか求めるアプリいる？

ってきいたら作って欲しいといわれたので作りました。

…

それだけなのですが、そこまでにいろいろとあるのでそれを話します。

プログラムの数学

mathlogのコミュニティガイドライン

を読んできたのですが、実は結構震えています。

数学として、プログラムの話をしてもよいのでしょうか。

どう考えてもさすがにそれはまずいので、計算量の話をしますが、

それでもここで話す内容ではないのではと考えてしまいます。

Mathlog で投稿可能な内容として次のようなものがあります。

物理学やコンピュータサイエンス、経済学などの数学の応用先となる分野の内容*
*

運営としては、物理やコンピューターサイエンスなどの数学を応用した内容によって、数学に対する見方が変わる人や数学を学ぶきっかけになる人も多くいると考えております。そのため、数学を応用した分野の内容も投稿可能としています。

とあるので、少しだけ安心しました。

いろいろと調べるうちに、コードのサポートもあるようなので、

それも使ってみたいと思います。

本題

まず

M Z V

は初見なので定義を聞きました。←MZVの文字かっこいい！

定義1　Multiple Zeta Value

\begin{array}{r} ζ (s_{1}, s_{2}, \dots, s_{r}) := \sum_{0 < n_{1} < n_{2} < \dots < n_{r}} n_{1}^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} \end{array}

頑張って打ちました。

これ初めて見たときぎょっとしましたね。なんでΣの上に数字が無いんやと。

よく下をみたらありますね。謎の範囲が。

これを満たすような

n_{1}, n_{2}, \dots, n_{r}

のすべてのパターンで足し算するらしいです。

これをプログラムにぶち込んで計算しましょう。

というわけなのですが、ここはmathlogなので、プログラムではなく計算量の話をします。

MZVの計算量がおおい。

MZVは見ての通りすごい形で総和を計算するのですが、プログラムにするのは簡単で、

ループを何回かかませば簡単に実装できます。

では本題の計算量がどれくらいになるのかなのですが、

このままだと上限を決めていないので無限大になってしまいます。

\infty!!

これではいけないので、次のような関数を定義してみましょう

定義2　Multiple Zeta Value

\begin{array}{r} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) := \sum_{a < n_{1} < n_{2} < \dots < n_{r} < p + r} n_{1}^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} (a < p) \end{array}

このようにして範囲を制限してあげることで、計算量が無限大にならないようにします。

具体的な計算法

具体的には、このように変形してあげます。

\begin{array}{rcl} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) & = & \sum_{n_{1} = a + 1}^{p} \sum_{n_{2} = n_{1} + 1}^{p + 1} \dots \sum_{n_{r} = n_{r - 1} + 1}^{p + r - 1} n_{1}^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} \end{array}

こうすることでプログラムの形が見えてきます。

r = 3

と限定してコードを書いてみましょう。

サイトに実装して動かすのでjavascriptで書きます。

[VScode:Dark (Visual Studio -C/C++)]
 0function MZV3(inputs) {
   var results = [];    //結果を入れる箱
 2    let n = Number(inputs[3].value);
 3
   let i1=0;
   let i2=0;
   let i3=0;
   let y1;
   let y2;
   let y3;
   let d1 = new BigNumber(0);
   let d2 = new BigNumber(0);
   
   let s1 = inputs[0].value;        //ユーザーからの入力
   let s2 = inputs[1].value;
   let s3 = inputs[2].value;
   let sum = new BigNumber(0);
   for(i1 =      1; i1 <= n-2; i1++){
       for(i2 = i1 + 1; i2 <= n-1; i2++){
           for(i3 = i2 + 1; i3 <= n  ; i3++){
               y1 = BigNumber(i1).pow(s1);    //i3 ^ s1
               y2 = BigNumber(i2).pow(s2);    //i3 ^ s2
               y3 = BigNumber(i3).pow(s3);    //i3 ^ s3
               d1 = y1.times(y2);
               d2 = d1.times(y3);
               d1 = BigNumber(1).dividedBy(d2);
               sum = sum.plus(d1);            //sumに計算した値を足していく。
           }
       }
   }
   results.push(sum.toString());         //結果を詰め込む
   let results;
32}

という感じです。（ぐへぇ）

プログラムが分からない人もいると思うので、説明すると、プログラム中にあるforというものが、

ここでいう

\sum

の範囲にあたります。

これを重ねているのは、

\sum

が連なっているということと同じです。

で、計算量はどのくらいになるのかというのを見積もると、超大雑把にみて

O (p^{r})

くらいかなぁと考えました。

(javascriptの四則演算の計算量のオーダーがはっきりとしないので、

ここでいう計算量はループの数ということにして、計算量を比較していきます。)

ここで、

p

と

r

は

ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r})

から来ています。

実用的にはpのほうがrよりもずっと大きく設定するので、これでいいでしょう。

これ、指数レベルのオーダーなので、多変数&精度を求められると、計算時間が爆発してしまいます。

さて、

O (p^{r})

というのは、ループの数のオーダーなのですが、

これをいかにして減らすのでしょうか？？？？？？？

名言より

ルロイ修道士の名言に、次のようなものがあります。

困難は分割せよ

これはルネ・デカルトの言葉なのですが、ルロイ修道士の方がなじみ深いですね。

この言葉をもとに、まずは簡単な問題へとレベルを落としてみます。

手始めに、こういうものをしてみましょう

\begin{array}{rcl} ζ_{0}^{5} (1, 1) & = & \sum_{0 < n_{1} < n_{2} < 7} n_{1}^{- 1} n_{2}^{- 1} \end{array}

\begin{array}{rcl} = \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{1 \cdot 4} + \frac{1}{1 \cdot 5} & + & \frac{1}{1 \cdot 6} \\ + \frac{1}{2 \cdot 3} + \frac{1}{2 \cdot 4} + \frac{1}{2 \cdot 5} & + & \frac{1}{2 \cdot 6} \\ + \frac{1}{3 \cdot 4} + \frac{1}{3 \cdot 5} & + & \frac{1}{3 \cdot 6} \\ + \frac{1}{4 \cdot 5} & + & \frac{1}{4 \cdot 6} \\ + & \frac{1}{5 \cdot 6} \end{array}

実際に書いてみると、きれいですね。

きれいに並んでいるので、どうにかうまい計算方法を見つけたいものですが...

例えばこういう風にするとどう見えるでしょうか。

\begin{array}{r} \frac{1}{1} (\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{2} (\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{3} (\frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{4} (\frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{5} (\frac{1}{6}) \end{array}

おお、綺麗にまとまりましたね。こうすると、下から計算していくと、計算量が減らせそうです。

例えば

\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

を計算するときに

\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

の計算結果を使いまわせます！

こうすることで、計算量を減らすことができます。（すごい発見）

でも、一般の場合は？

ここで問題になってくるのが、一般の場合です。

一般の場合、、、急に想像しずらくなりました。

でも、私たちには上に書いた具体例という強力な武器があります。

これをもとに考えてみましょう。

もし、

p

が大きくなったとしても、

r = 2

ならば上記の方法をのばすことで対応できます。

では、

r

を変えたとき、どう対処すればよいでしょうか。

私はどうしたかというと、ルロイ修道士の名言に従いました。

\begin{array}{rcl} ζ_{0}^{4} (1, 1, 1) & = & \sum_{0 < n_{1} < n_{2} < n_{3} < 7} n_{1}^{- 1} n_{2}^{- 1} n_{3}^{- 1} \end{array}

これを展開してみましょう。（頑張って）

...
と言いたいところですが、賢い皆さんならこれが3次元的に広がりそうなのは分かると思います。
なので、さらに問題を分割してみたいと思います
具体的には、

n_{1} = 1

の時を考えます。

\begin{array}{rcl} \frac{1}{1 \cdot 2 \cdot 3} + \frac{1}{1 \cdot 2 \cdot 4} + \frac{1}{1 \cdot 2 \cdot 5} & + & \frac{1}{1 \cdot 2 \cdot 6} \\ + \frac{1}{1 \cdot 3 \cdot 4} + \frac{1}{1 \cdot 3 \cdot 5} & + & \frac{1}{1 \cdot 3 \cdot 6} \\ + \frac{1}{1 \cdot 4 \cdot 5} & + & \frac{1}{1 \cdot 4 \cdot 6} \\ + & \frac{1}{1 \cdot 5 \cdot 6} \end{array}

これを見ると分かる通り、綺麗にくくれそうです。

\begin{array}{rcl} \frac{1}{1} (\frac{1}{2 \cdot 3} + \frac{1}{2 \cdot 4} + \frac{1}{2 \cdot 5} & + & \frac{1}{2 \cdot 6} \\ + \frac{1}{3 \cdot 4} + \frac{1}{3 \cdot 5} & + & \frac{1}{3 \cdot 6} \\ + \frac{1}{4 \cdot 5} & + & \frac{1}{4 \cdot 6} \\ + & \frac{1}{5 \cdot 6}) \end{array}

むむむ、、、よく見てみるとさっきの2変数の形に似ています。
というよりこれこう書けるじゃないですか！

\begin{array}{r} \frac{1}{1} (ζ_{1}^{5} (1, 1)) \end{array}

ということは

n_{1} = 2

のときもなりそう、、、

\begin{array}{r} \frac{1}{2} ζ_{2}^{5} (1, 1) \end{array}

実際になりましたね！(実際になるか展開して確かめるのは読者に任せる。)
ということで、結局こうなります。

\begin{array}{r} ζ_{0}^{4} (1, 1, 1) = \sum_{0 < n_{1} < 5} \frac{1}{n_{1}} ζ_{n_{1}}^{5} (1, 1) \end{array}

よし、やっと一般の場合を予想できます。多分こんな感じでしょう。

\begin{array}{r} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) = \sum_{a < n_{1} < p + 1} \frac{1}{n_{1}^{s_{1}}} ζ_{n_{1}}^{p + 1} (s_{2}, s_{3}, \dots, s_{r}) \end{array}

これ、証明できるかな？

証明

証明の強力な手助けとして、上に頑張って書いた具体例があります。
それをもとに証明方法を考えてみましょう。
と言っても、多分

n_{1}

が

a + 1, a + 2, \dots, p

の時を考えて全部足せばいけるやろ！
という気持ちでやってみます。

\begin{array}{rcl} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) & = & \sum_{a < n_{1} < n_{2} < \dots < n_{r} < p + r} n_{1}^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} \end{array}

ここで、右辺の

\begin{array}{r} \sum_{a < n_{1} < n_{2} < \dots < n_{r} < p + r} n_{1}^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} \end{array}

において

n_{1} = t (a < t < p + 1)

の時、この式は、

\begin{array}{rcl} \sum_{(a <) t < n_{2} < \dots < n_{r} < p + r} t^{- s_{1}} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} & = & t^{- s_{1}} \sum_{t < n_{2} < \dots < n_{r} < p + r} n_{2}^{- s_{2}} \dots n_{r}^{- s_{r}} \\ = & \frac{1}{t^{s_{1}}} ζ_{t}^{p + 1} (s_{2}, s_{3}, \dots, s_{r}) \end{array}

となりますね！
あとはこれを

t = a + 1, a + 2, \dots, p

の時をすべて足すだけです！

\begin{array}{r} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) = \sum_{a < t < p + 1} \frac{1}{t^{s_{1}}} ζ_{t}^{p + 1} (s_{1}, s_{2}, \dots, s_{r}) \end{array}

証明できました！

◼

\begin{array}{r} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) = \sum_{a < n_{1} < p + 1} \frac{1}{n_{1}^{s_{1}}} ζ_{n_{1}}^{p + 1} (s_{1}, s_{2}, \dots, s_{r}) \end{array}

...
証明できましたが、これがどう計算量の削減につながるのでしょうか。
じつは、ここにはさっき見出した素晴らしい発見が見えない形になってしまっています。
そう、それが計算結果の使いまわしです。

おお、綺麗にまとまりましたね。こうすると、例えば

\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

を計算するときに

\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

の計算結果を使いまわせます！
こうすることで、計算量を減らすことができます。（すごい発見）

はいはい、さっきやりましたね。でもいったいどこに消えたのでしょうか。
上の方の、計算結果を使いまわせます！のところで書いていた分数たちに注目しましょう。

\begin{array}{r} \frac{1}{1} (\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{2} (\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{3} (\frac{1}{4} + \frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{4} (\frac{1}{5} + \frac{1}{6}) \\ + \frac{1}{5} (\frac{1}{6}) \end{array}

これですね。これをよくよく考えると次のように表せられます。

\begin{array}{r} \frac{1}{1} (ζ_{1}^{6} (1)) + \frac{1}{2} (ζ_{2}^{6} (1)) + \frac{1}{3} (ζ_{3}^{6} (1)) + \frac{1}{4} (ζ_{4}^{6} (1)) + \frac{1}{5} (ζ_{5}^{6} (1)) \end{array}

これ、さっきの公式１に似てませんか？
ね、似てるよね。
ここで、使いまわしはどれをどう使いまわしていたのか思い出すと、

\frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

を計算するときに

\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}

の計算結果を使いまわせます！

なので、

ζ_{1}^{6} (1)

を計算するとき、

ζ_{2}^{6} (1)

を使いまわせる！と言っているのです。
うん...

は？

ということでこれ、どうやって一般の場合に前回の結果を使うのでしょうか。
上の具体例をよく見ると、こういうことになっています。

\begin{array}{r} ζ_{1}^{6} (1) = ζ_{2}^{6} (1) + \frac{1}{6} \end{array}

つまり？

\begin{array}{r} ζ_{1}^{6} (1) - ζ_{2}^{6} (1) = \frac{1}{6} \end{array}

とみれば、下の数をずらした物の差は、簡単に表せるような気がします。
では、これに従い公式1を使って計算してみましょう。いい結果が出ろ！たのむ！

\begin{array}{rcl} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) - ζ_{a + 1}^{p} (s_{1}, s_{2}, \dots, s_{r}) & = & \sum_{a < n_{1} < p + 1} \frac{1}{n_{1}^{s_{1}}} ζ_{n_{1}}^{p + 1} (s_{1}, s_{2}, \dots, s_{r}) - \sum_{a + 1 < n_{1} < p + 1} \frac{1}{n_{1}^{s_{1}}} ζ_{n_{1}}^{p + 1} (s_{1}, s_{2}, \dots, s_{r}) \\ = & \frac{1}{(a + 1)^{s_{1}}} ζ_{a + 1}^{p + 1} (s_{2}, s_{3}, \dots, s_{r}) \end{array}

うわぁぁぁぁでたぁぁぁぁ！！！！

n_{1} = a + 1

のときだけ引き算されなくてこんな式ができました

\begin{array}{r} ζ_{a}^{p} (s_{1}, s_{2}, \dots, s_{r}) - ζ_{a + 1}^{p} (s_{1}, s_{2}, \dots, s_{r}) = (a + 1)^{- s_{1}} ζ_{a + 1}^{p + 1} (s_{2}, s_{3}, \dots, s_{r}) \end{array}

ここまで来て気づいたこと

はい、急に何かと思われるでしょうがここまで来て一つかなり重い問題が浮かび上がってきました
それは、、、

記事を書くのがめんどくさすぎる！！！！

ここまで書いてきましたが皆さん分かってますよね、おかしいと。
背景がまずおかしいし、一番上では文字がうごくし、
なんか急にめっちゃカラフルなプログラムが出てきたりと
これね、ほとんどHTMLで書いているのでいろいろできるんですね
できるんです、できるんですけど問題が山ほどあります
CSSが使えない、プレビューが異次元に飛ぶ、