考えていること(ちょっとずつ更新)

投稿1•2の要点

\begin{eqnarray} K_a^p(k_1,k_2,\dots,k_r\:;f_1,f_2,\dots,f_r) :=\sum_{a< n_1< n_2<\dots< n_r< p+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ \end{eqnarray}
とするとき、
\begin{eqnarray} K_a^p(\boldsymbol{k};\boldsymbol{f}) &=& \sum_{a< n_1< n_2<\dots< n_r< p+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& f_1(a+1,k_1)\sum_{a+1< n_2<\dots< n_r< p+r}f_2(n_2,k_2)\dots f_r(n_r,k_r) \:\:+ \sum_{a+1< n_1< n_2<\dots< n_r< p+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& f_1(a+1)K_{a+1}^{p+1}(_{\rightarrow}\boldsymbol{k};_{\rightarrow}\boldsymbol{f}) + K_{a+1}^p(\boldsymbol{k},\boldsymbol{f}) \\ \end{eqnarray}
ただし、
\begin{eqnarray} \boldsymbol{k} &=& (k_1,k_2,\cdots,k_r) \\ \boldsymbol{f} &=& (f_1,f_2,\cdots,f_r) \\ _{\rightarrow}\boldsymbol{k} &=& (k_2,k_3,\cdots,k_r) \\ _{\rightarrow}\boldsymbol{f} &=& (f_2,f_3,\cdots,f_r) \\ \boldsymbol{k}_{\leftarrow} &=& (k_1,k_2,\cdots,k_{r-1}) \\ \boldsymbol{f}_{\leftarrow} &=& (f_1,f_2,\cdots,f_{r-1}) \end{eqnarray}
が成り立つので、$K_a^p(\boldsymbol{k};\boldsymbol{f})$を求める時のループ数が$\mathcal{O}(p^r)$から、$\mathcal{O}(pr)$になる
という話

どうして

どうして
\begin{eqnarray} \sum_{a< n_1< n_2<\dots< n_r< p} \end{eqnarray}
ではなくて
\begin{eqnarray} \sum_{a< n_1< n_2<\dots< n_r< p+r} \end{eqnarray}
なのでしょうか。
これは$n_1$から数字をギチギチに詰めて行った時、
\begin{eqnarray} \sum_{a< a+1< a+2<\dots< a+r<\Box} \end{eqnarray}
となるので、もし$\Box=p$なら、
\begin{eqnarray} \sum_{a< a+1< a+2<\dots< a+r< p} \\ a+r< p\\ \end{eqnarray}
となり、$r$に頼る$p$の制限が出てきてしまいます。
そこで$\Box=p+r$とすることで、
\begin{eqnarray} \sum _{a< a+1< a+2<\dots< a+r< p+r} \\ a+r< p+r\\ a< p \end{eqnarray}
となって綺麗になるからです。

他の式

\begin{eqnarray} K_a^{a+1}(\boldsymbol{k};\boldsymbol{f}) &=& \sum_{a< n_1< n_2<\dots< n_r< a+1+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& f_1(a+1,k_1)f_2(a+2,k_2)\dots f_r(a+r,k_r) \\ K_a^{p}(k;f) &=& \sum_{a< n< p}f(n,k) \\ &=& f(1,k)+f(2,k)+\dots +f(p,k) \\ \end{eqnarray}
この$K$は色々と使い勝手があって、階乗とか自然数の$n$乗の和とか多重なんとか値みたいなやつが大体作れます。

他で区切ってみる

さっきは$n_1=a+1$か、$n_1>a+1$かで区切りましたが、他で区切ってみるとどうなるのかな。

$n_r$

$n_r$で区切ってみましょう。

\begin{eqnarray} K_a^p(\boldsymbol{k};\boldsymbol{f}) &=& \sum_{a< n_1< n_2<\dots< n_r< p+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& f_r(p+r-1,k_r)\sum_{a< n_1<\dots< n_{r-1}< p+r-1}f_1(n_1,k_1)\dots f_{r-1}(n_{r-1},k_{r-1}) \:\:+ \sum_{a< n_1< n_2<\dots< n_r< p+r-1}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& f_r(p+r-1,k_r)K_{a}^{p}(\boldsymbol{k}_{\leftarrow};\boldsymbol{f}_{\leftarrow}) + K_{a}^{p-1}(\boldsymbol{k},\boldsymbol{f}) \\ \\ \end{eqnarray}
あってる？

$n_i+1$と$n_{i+1}$

$n_i+1=n_{i+1}$か$n_i+1< n_{i+1}$かで場合分けしましょう。
\begin{eqnarray} K_a^p(\boldsymbol{k};\boldsymbol{f}) &=& \sum_{a< n_1< n_2<\dots< n_r< p+r}f_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r) \\ &=& \sum_{\substack{a< n_1<\cdots< n_i \\n_i+1< n_{i+2}<\cdots< n_r< p+r}} f_1(n_1,k_1)\cdots f_i(n_ik_i)f_{i+1}(n_i+1,k_{i+1})\cdots f_r(n_r,k_r) \\ &+& \sum_{\substack{a< n_1<\cdots< n_i \\n_i+1< n_{i+1}<\cdots< n_r< p+r}} f_1(n_1,k_1)\cdots f_i(n_ik_i)f_{i+1}(n_{i+1},k_{i+1})\cdots f_r(n_r,k_r) \\ \end{eqnarray}
うーん。うまくいかないですね

エイトケンの$\Delta^2$加速法をつかう

MZVとかって収束が遅いんですよね。なので加速法を使うとかしてみましょう
\begin{eqnarray} \lim_{p \rightarrow \infty} K_0^p(\boldsymbol{k};\boldsymbol{f}):= K(\boldsymbol{k};\boldsymbol{f}) \end{eqnarray}
として、これが収束するとします。
数列${\{a_n\}}$を考えて、エイトケンの$\Delta^2$加速法を適用させます。
\begin{eqnarray} a_n &=& K_0^n(\boldsymbol{k};\boldsymbol{f}) \\ t_n &=& a_n-\frac{(a_{n+1}-a{n})^2}{a_{n+2}-2a_{n+1}+a_n} \\ &=& K_0^n(\boldsymbol{k};\boldsymbol{f}) - \frac{(K_0^{n+1}(\boldsymbol{k};\boldsymbol{f}) - K_0^n(\boldsymbol{k};\boldsymbol{f}))^2}{K_0^{n+2}(\boldsymbol{k};\boldsymbol{f}) -2K_0^{n+1}(\boldsymbol{k};\boldsymbol{f}) + K_0^n(\boldsymbol{k};\boldsymbol{f})} \end{eqnarray}

あれ?

これさっき見ましたよね
\begin{eqnarray} K_a^p(\boldsymbol{k};\boldsymbol{f}) = f_r(a+p-1)K_{a}^{p}(\boldsymbol{k}_{\leftarrow};\boldsymbol{f}_{\leftarrow}) + K_{a}^{p-1}(\boldsymbol{k},\boldsymbol{f}) \end{eqnarray}
ほら、これ$p = n+1$と$a=0$にしたら、
\begin{eqnarray} K_0^{n+1}(\boldsymbol{k};\boldsymbol{f}) = f_r(n)K_{0}^{n+1}(\boldsymbol{k}_{\leftarrow};\boldsymbol{f}_{\leftarrow}) + K_{0}^{n}(\boldsymbol{k},\boldsymbol{f}) \\ \\ \therefore K_0^{n+1}(\boldsymbol{k};\boldsymbol{f}) - K_{0}^{n}(\boldsymbol{k},\boldsymbol{f}) = f_r(n)K_{0}^{n+1}(\boldsymbol{k}_{\leftarrow};\boldsymbol{f}_{\leftarrow}) \\ \end{eqnarray}
嫌な予感がしますね。