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

投稿1•2の要点

$$\begin{array}{r}{K}_a^p(k_1,k_2,\dots ,k_r;f_1,f_2,\dots ,f_r):=\sum _{a<n_1<n_2<\cdots <n_r<p+r}{f}_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r)\end{array}$$
とするとき、
$$\begin{array}{rcl}{K}_a^p(\mathit{k};\mathit{f})& =& \sum _{a<n_1<n_2<\cdots <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<\cdots <n_r<p+r}{f}_2(n_2,k_2)\dots f_r(n_r,k_r)+\sum _{a+1<n_1<n_2<\cdots <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}{(}_{\to }\mathit{k}{;}_{\to }\mathit{f})+K_{a+1}^p(\mathit{k},\mathit{f})\end{array}$$
ただし、
$$\begin{array}{rcl}\mathit{k}& =& (k_1,k_2,\cdots ,k_r)\\ \mathit{f}& =& (f_1,f_2,\cdots ,f_r)\\ {}_{\to }\mathit{k}& =& (k_2,k_3,\cdots ,k_r)\\ {}_{\to }\mathit{f}& =& (f_2,f_3,\cdots ,f_r)\\ {\mathit{k}}_{\leftarrow }& =& (k_1,k_2,\cdots ,k_{r-1})\\ {\mathit{f}}_{\leftarrow }& =& (f_1,f_2,\cdots ,f_{r-1})\end{array}$$
が成り立つので、$K_a^p(\mathit{k};\mathit{f})$を求める時のループ数が$\mathcal{O}(p^r)$から、$\mathcal{O}(pr)$になる
という話

どうして

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

他の式

$$\begin{array}{rcl}{K}_a^{a+1}(\mathit{k};\mathit{f})& =& \sum _{a<n_1<n_2<\cdots <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)+\cdots +f(p,k)\end{array}$$
この$K$は色々と使い勝手があって、階乗とか自然数の$n$乗の和とか多重なんとか値みたいなやつが大体作れます。

他で区切ってみる

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

$n_r$

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

$$\begin{array}{rcl}{K}_a^p(\mathit{k};\mathit{f})& =& \sum _{a<n_1<n_2<\cdots <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<\cdots <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<\cdots <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({\mathit{k}}_{\leftarrow };{\mathit{f}}_{\leftarrow })+K_a^{p-1}(\mathit{k},\mathit{f})\\ \end{array}$$
あってる？

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

$n_i+1=n_{i+1}$か$n_i+1<n_{i+1}$かで場合分けしましょう。
$$\begin{array}{rcl}{K}_a^p(\mathit{k};\mathit{f})& =& \sum _{a<n_1<n_2<\cdots <n_r<p+r}{f}_1(n_1,k_1)f_2(n_2,k_2)\dots f_r(n_r,k_r)\\ & =& \sum _{\begin{array}{c}a<n_1<\cdots <n_i\\ n_i+1<n_{i+2}<\cdots <n_r<p+r\end{array}}{f}_1(n_1,k_1)\cdots f_i(n_i{k}_i)f_{i+1}(n_i+1,k_{i+1})\cdots f_r(n_r,k_r)\\ & +& \sum _{\begin{array}{c}a<n_1<\cdots <n_i\\ n_i+1<n_{i+1}<\cdots <n_r<p+r\end{array}}{f}_1(n_1,k_1)\cdots f_i(n_i{k}_i)f_{i+1}(n_{i+1},k_{i+1})\cdots f_r(n_r,k_r)\end{array}$$
うーん。うまくいかないですね

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

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

あれ?

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