はじめに
線形漸化式を満たす数列について考えるとき、その母関数が有理冪級数であることから大抵のことは母関数を式変形するだけで理解できる。以下では母関数だけを見ていても分かり辛いことについて記しておく。それらは具体的には母関数の分母が冪乗の形をしてる線形漸化的な数列や線形漸化的な数列の冪乗和からなる数列の $N$ 項目の効率的な計算の役に立つ。
線形漸化式
有理数の数列 $(u_n\in\mathbb{Q})_{n\ge 0}$ について考える。ある $c_1,\dotsc,c_d\in\mathbb{Q}$ が存在して
\begin{align*}
u_{n} &= \sum_{k=1}^d c_k u_{n-k}\qquad \forall n\ge d
\end{align*}
を満たすとき、数列$(u_n)_{n\ge0}$は上記の線形漸化式を満たすという。$c_d=0$のときは $d$をより小さくとることができるので、$c_d\ne 0$を仮定する。
数列$(u_n)_{n\ge0}$が何かしらの線形漸化式を満たすとき、数列を線形漸化的な数列、もしくは C-recursive な数列という。
ここで
\Gamma(x) = x^d - \sum_{k=1}^d c_k x^{d-k}
を線形漸化式の特性多項式という。$c_d\ne0$の仮定より、$\Gamma(0)\ne 0$である。
特性多項式は数列に対して定義されるのではなく、線形漸化式に対して定義される。
また特性多項式の高次と低次を入れ換えて得られる多項式
Q(x) = 1 - \sum_{k=1}^d c_k x^{k}
は数列 $(u_n)_{n\ge 0}$の母関数の分母である。
\Gamma(x) = \prod_{k=1}^d (x-\alpha_k)
のとき、
Q(x) = \prod_{k=1}^d (1-\alpha_kx)
である。
ある線形漸化式を満たす複素数列が貼る線形空間
$K=\mathbb{Q}$ もしくは $K=\mathbb{C}$ とする。ある線形漸化式を満たす $K$ 上の数列の集合を
\begin{align*}
V_K\left(x^d - \sum_{k=1}^d c_k x^{d-k}\right) &:= \left\{ (u_n\in K)_{n\ge 0}\mid u_n = \sum_{k=1}^d c_ku_{n-k}\right\}
\end{align*}
と定義する。この集合は和とスカラー倍について閉じているので$K$上の線形空間となる。最初の $d$ 項で数列は一意に定まるので、この線形空間の次元は $d$ である。特定の基底を選ぶ場合は最初の $d$ 項を線形独立に決めればよいので、そのような決め方を自由に選べばよい。
事実V: $V$ を $\mathbb{Q}$上の 有限次元線形空間とする。また、$W$ を $V$ が貼る $\mathbb{C}$上の線形空間とする。このとき、$V$ の任意の基底は$W$ の基底である。また、$V$ に含まれる $W$ の任意の基底は $V$ の基底である。
以下では $V_\mathbb{C}(\Gamma)$の特別な基底の選び方について説明する。
$\alpha\in\mathbb{C}$ が $\Gamma(x)$ の根であるとき、
\alpha^d - \sum_{k=1}^d c_k \alpha^{d-k} = 0
であるので、両辺に $\alpha^{n-d}$ を掛けることで
\alpha^n - \sum_{k=1}^d c_k \alpha^{n-k} = 0\qquad\forall n\ge d
であることが分かる。よって、等比数列 $u_n=\alpha^n$は線形漸化式を満たす。
$\Gamma(x)$ の根 $\alpha_1,\dotsc,\alpha_d\in\mathbb{C}\setminus\{0\}$ に重複が無い場合はこの $d$ 個の等比数列が $V_{\mathbb{C}}(\Gamma)$ の基底となる。等比数列達が線形独立であることを示せば十分である。母関数を利用すると
\begin{align*}
&\sum_{k=1}^d t_k\frac1{1-\alpha_k x} = 0\\
\iff&\sum_{k=1}^d t_k\prod_{\ell\ne k} (1-\alpha_\ell x) = 0\\
\implies& t_k \prod_{\ell\ne k}(1-\alpha_\ell\alpha_k^{-1}) = 0\qquad \forall k\in\{1,\dotsc,d\}\\
\implies& t_k = 0\qquad \forall k\in\{1,\dotsc,d\}\\
\end{align*}
であることから線形独立性が示せる。
他にも最初の$d$項だけに注目して転置することで多項式の議論に持ち込んで独立性を証明することもできる。
$\Gamma(x)$ の根 $\alpha\in\mathbb{C}\setminus\{0\}$ が重根である場合を考える。このとき、$\alpha$ は任意の $n\ge d$ について
x^{n-d}\Gamma(x) = x^n - \sum_{k=1}^d c_k x^{n-k}
の重根でもある。よって $\alpha$ はこの導関数
(x^{n-d}\Gamma(x))' = nx^{n-1} - \sum_{k=1}^d c_k(n-k) x^{n-k-1}
の根である。よって
n\alpha^{n-1} - \sum_{k=1}^d c_k (n-k)\alpha^{n-k-1} = 0
を満たす。両辺に $\alpha$ を掛けることで
n\alpha^{n} - \sum_{k=1}^d c_k(n-k) \alpha^{n-k} = 0
を得る。
よって数列 $u_n = n\alpha^n$ は線形漸化式を満たす。
同様の議論から $\alpha$ が $m$重根のとき、数列 $u_n=n(n-1)\dotsm(n-m+1)\alpha^n$ も線形漸化式を満たす。
よって $V_\mathbb{C}(\Gamma)$ に含まれる $d$個の数列が得られた。これらが $V_\mathbb{C}(\Gamma)$ の基底であることを示すためには、その線形独立性を示せば十分である。これも上記と同様、母関数を用いて示すことができる。
特性多項式 $\Gamma$ が $v$ 個の相異なる根 $\alpha_1,\dotsc,\alpha_v$ を持ち、$k=1,\dotsc,v$ について $\alpha_k$ の重複度を $m_k$ とすると、
V_\mathbb{C}(\Gamma) = \mathrm{span}_\mathbb{C}(\{(n^s\alpha_k^n)_{n\ge0}\mid k \in\{1,\dotsc,v\},\,s\in\{0,\dotsc,m_k-1\}\}).
この事実は有理母関数の分母を因数分解して部分分数分解することでも理解できる。
短い線形漸化式と関連する長い線形漸化式
線形漸化的数列 $(u_n\in\mathbb{Q})_{n\ge 0}$ の特性多項式 $\Gamma\in\mathbb{Q}[x]$ が重根を持たないとする。$(u_n)_{n\ge 0}$と関連がある別の線形漸化式について、その有理基底を $V_{\mathbb{Q}}(\Gamma)$ の基底から得る方法を考える。具体的には以下の三つのケースを考える。
- 特性多項式が$\Gamma(x)^m$.
- 線形漸化的数列 $(u_n)_{n\ge0}$ の$m$乗和 $(\sum_{t=0}^n u_t^m)_{n\ge0}$.
- 二つの線形漸化的数列 $(u_n)_{n\ge0},\, (v_n)_{n\ge0}$ のアダマール積 $(u_nv_n)_{n\ge0}$.
以下では $n$ を添字に持つ数列を $(u_n)_{n\ge0}$ と表す代わりに単に $u_n$ と表すこともある。例えば $(\alpha^n)_{n\ge 0}$ と表す代わりに単に $\alpha^n$ と表すこともある。
Γ^m
このとき、 $\Gamma(x)^m$ の根は $\alpha_1,\dotsc,\alpha_d$ であり、それぞれ $m$重根である。
よって $s=0,\dotsc m-1$, $k=1,\dotsc,d$ について数列 $(n^s\alpha_k^n)_{n\ge 0}$は $V_{\mathbb{C}}(Q)$ の基底である。
定理1.
\begin{align*}
V_\mathbb{Q}(\Gamma) &= \mathrm{span}_\mathbb{Q}\left(\{u_n^{(k)}\mid k\in\{1,\dotsc,d\}\}\right)
\end{align*}
のとき、
\begin{align*}
V_\mathbb{Q}(\Gamma^m) &= \mathrm{span}_\mathbb{Q}\left(\left\{n^su_n^{(k)}\mid s=0,\dotsc, m-1,\,k=1,\dotsc,d\right\}\right)
\end{align*}
証明.
事実Vより $\{n^s u_n^{(k)}\}_{s,k}$ が $V_\mathbb{C}(\Gamma^m)$ の基底であることを示せばよい。
各 $k=1,\dotsc,d$について $u_n^{(k)}\in\mathrm{span}_\mathbb{C}(\alpha_1^n,\dotsc,\alpha_d^n)$ より、任意の $s=0,\dotsc,m-1$について
\begin{align*}
n^s u_n^{(k)}\in\mathrm{span}_\mathbb{C}(n^s\alpha_1^n,\dotsc,n^s\alpha_d^n)\subseteq V_{\mathbb{C}}(\Gamma^m)
\end{align*}
である。一方で、各 $k=1,\dotsc,d$について $\alpha_k^n\in V_\mathbb{C}(\Gamma)=\mathrm{span}_\mathbb{C}(u_n^{(1)},\dotsc,u_n^{(d)})$ より、任意の $s=0,\dotsc,m-1$について
\begin{align*}
n^s \alpha_k^n\in\mathrm{span}_\mathbb{C}(n^su_n^{(1)},\dotsc,n^su_n^{(d)})
\end{align*}
である。証明終わり。
具体例
Yukicoder: No.980 Fibonacci Convolution Hard
$$f(x)= \left(\frac{x}{1-px-x^2}\right)^2$$
について $[x^N]\, f(x)$ を計算する問題である。
まず、
$$g(x) = \frac{x}{1-px-x^2}$$
を母関数として持つ数列 $F_n$ について考える。すると $\{F_n,\, F_{n+1}\}$ は $V_\mathbb{Q}(\Gamma)$ の基底となる。よって定理1より、 $f$ を母関数として持つ数列は $(F_n), (F_{n+1}), (nF_n), (nF_{n+1})$の線形結合で表せる。
最初の4項を見ると
\begin{align*}
(F_n)_0^3 &= \bigl(0,\, 1,\, p,\, p^2+1\bigr)\\
(nF_n)_0^3 &= \bigl(0,\, 1,\, 2p,\, 3(p^2+1)\bigr)\\
(F_{n+1})_0^3 &= \bigl(1,\, p,\, p^2+1,\, p(p^2+2)\bigr)\\
(nF_{n+1})_0^3 &= \bigl(0,\, p,\, 2(p^2+1),\, 3p(p^2+2)\bigr)
\end{align*}
である。一方で $f(x)$ の最初の4項は $(0,\, 0,\, 1,\, 2p)$ である。
これらの関係から線形結合の係数を求めることで
\begin{align*}
[x^N]\, f(x) = -\frac{p}{p^2+4} (N+1) F_N + \frac{2}{p^2+4} N F_{N+1}
\end{align*}
であることが分かる。
基本的なアルゴリズムで $(F_N, F_{N+1})$ を $O(\log N)$時間で計算すればよい。
一般に母関数 $f$ の分母が $d$次多項式の $m$乗であった場合、$V_\mathbb{Q}(\Gamma)$ の基底として $\{F_n, F_{n+1},\dotsb, F_{n+d-1}\}$ を選ぶと、
[x^N]\, f(x) = \sum_{k=0}^{d-1} p^{(k)}(N) F_{N+k}
と解を表すことができる。ここで、$p^{(k)}$ は高々 $m-1$ 次の多項式である。
これらの多項式が得られていれば与えられた$N$に対して算術計算量 $O(\mathsf{M}(d)\log N + md)$ で上記の値を計算できる。これは有理冪級数の分母の構造を考慮しない一般的な手法の算術計算量 $O(\mathsf{M}(md)\log N)$ より効率的である。
疑問: 線形結合の係数を算術計算量 $O(\mathsf{M}(md)\log (md))$ で計算できるか？
一般的な行列の理論を使うと、 Vandermonde type の displacement rank が $d$ であることから算術計算量 $O(d^2 \mathsf{M}(md)\log md)$ で解くことはできる。
Victor Pan,
“On Computations with Dense Structured Matrices,”
Mathematics of Computation 55, no. 191, pp. 179–90, 1990.
https://doi.org/10.2307/2008798.
おそらくもっとシンプルに算術計算量 $O(\mathsf{M}(md)\log (md))$ で計算できるはずだが、自分は理解できていない。
数列の冪乗和
線形漸化式を満たす有理数列 $(u_n)_{n\ge 0}$ について $\sum_{n=0}^N u_n^m$ を計算する問題を考える。そのために、まず数列 $(u_n^m)_{n\ge 0}$ が満たす線形漸化式について考える。数列 $(u_n)_{n\ge 0}$ の特性多項式 $\Gamma(x)$ の根を $\alpha_1,\dotsc,\alpha_d\in\mathbb{C}$とし、簡単のために重根はないものとする。このとき、ある $\gamma_1,\dotsc,\gamma_d\in\mathbb{C}$ が存在して、 $u_n = \sum_{k=1}^d \gamma_k \alpha_k^n$ である。よって
u_n^m = \left(\sum_{k=1}^d \gamma_k \alpha_k^n\right)^m
=\sum_{k_1,\dotsc,k_m=1}^d \left(\prod_{v=1}^d \gamma_{k_v}\right) \left(\prod_{v=1}^d \alpha_{k_v}\right)^n
である。よって
\Gamma^{(m)}(x) := \prod_{\substack{m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m}} \left(x- \prod_{k=1}^d \alpha_k^{m_k}\right)
は $(u_n^m)_{n\ge 0}$ の特性多項式である。$m$ の高々$d$個の整数への分割毎に積をまとめると、それぞれが $\alpha_1,\dotsc,\alpha_d$ に対する対称式になるので有理多項式への因数分解になる。
簡単のため $\Gamma^{(m)}$にも重根がないとすると以下が成り立つ。
V_\mathbb{C}(\Gamma^{(m)}) = \mathrm{span}_\mathbb{C}\left(\left\{\left(\prod_{k=1}^d \alpha_k^{m_k}\right)^n\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
$\Gamma^{(m)}$に重根がある場合は根の重複を取り除いても $(u_n^m)_{n\ge0}$ の特性多項式になる。そうすることで以下の議論も同様に成り立つ。以下では簡単のために $\Gamma^{(m)}$に重根がないと仮定している。
定理2.
\begin{align*}
V_\mathbb{Q}(\Gamma) &= \mathrm{span}_\mathbb{Q}\left(\{u_n^{(k)}\mid k\in\{1,\dotsc,d\}\}\right)
\end{align*}
で $\Gamma^{(m)}$に重根がないとき、
V_\mathbb{Q}(\Gamma^{(m)})= \mathrm{span}_\mathbb{Q}\left(\left\{\prod_{k=1}^d u_n^{(k)m_k}\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
である。
証明.
事実Vより $\bigl\{\prod_{k=1}^d u_n^{(k)m_k}\bigr\}_{m_1,\dotsc,m_d}$ が $V_\mathbb{C}(\Gamma^m)$ の基底であることを示せばよい。
$u_n^{(k)}\in\mathrm{span}_\mathbb{C}(\alpha_1^n,\dotsc,\alpha_d^n)$ より、
\prod_{k=1}^d u_n^{(k)m_k}\in \mathrm{span}_\mathbb{C}\left(\left\{\left(\prod_{k=1}^d \alpha_k^{m_k}\right)^n\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
である。
同様に、$\alpha_k^n\in\mathrm{span}_\mathbb{C}(u_n^{(1)},\dotsc,u_n^{(d)})$ より、
\left(\prod_{k=1}^d \alpha_k^{m_k}\right)^n = \prod_{k=1}^d (\alpha_k^n)^{m_k} \in \mathrm{span}_\mathbb{C}\left(\left\{\prod_{k=1}^d u_n^{(k)m_k}\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
である。証明終わり。
この二種類の基底の間に成り立つ線形変換はボソンサンプリングの理論においてモード数 $d$、ボソン数 $m$ の場合に現れるものとほぼ等しい。また、表現論において多変数多項式への行列の作用として同様のものが現れる。
話を $m$ 乗和に戻そう。$(x-1)\Gamma^{(m)}(x)$ は $m$ 乗和からなる数列 $(\sum_{t=0}^n u_t^m)_{n\ge 0}$ の特性多項式になる。$\Gamma^{(m)}(x)$が 1 を根として持つ場合と持たない場合についてそれぞれ考える。
$\Gamma^{(m)}(x)$が 1 を根として持たない場合は、数列 $\sum_{t=0}^n u_t^m$ は線形空間
\mathrm{span}_\mathbb{Q}\left(\{1\}\cup \left\{\prod_{k=1}^d u_n^{(k)m_k}\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
に含まれる。よって、ある $r,\, r_{m_1,\dotsc,m_d} \in\mathbb{Q}$ が存在して、
\sum_{t=0}^n u_t^m = r + \sum_{\substack{m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m}} r_{m_1,\dotsc,m_d} \prod_{k=1}^d u_n^{(k)m_k}
が成り立つ。
$\Gamma^{(m)}(x)$が 1 を根として持つ場合は、数列 $\sum_{t=0}^n u_t^m$ は線形空間
\mathrm{span}_\mathbb{Q}\left(\{n\}\cup \left\{\prod_{k=1}^d u_n^{(k)m_k}\,\middle|\, \begin{gathered}m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m\end{gathered}\right\}\right)
に含まれる。よって
\sum_{t=0}^n u_t^m = rn + \sum_{\substack{m_1,\dotsc,m_d\in\mathbb{Z}_{\ge 0}\\m_1+\dotsb+m_d=m}} r_{m_1,\dotsc,m_d} \prod_{k=1}^d u_n^{(k)m_k}
が成り立つ。
具体例
$d=2$ の場合を考える。
\Gamma(x) = (x-\alpha)(x-\beta)
のとき、
\Gamma^{(m)}(x) = \prod_{k=0}^m\left(x-\alpha^k\beta^{m-k}\right)
である。
特性多項式 $\Gamma(x)$ を持つ数列で基本的なものが二つある。
\begin{align*}
F_n &= \frac{\alpha^n-\beta^n}{\alpha-\beta},&
L_n &= \alpha^n + \beta^n
\end{align*}
これらは $\alpha$と$\beta$ の対称式なので有理数列である。
$F_n$ をフィボナッチ型数列、$L_n$ をリュカ数列と呼ぶことにする。$F_n$ の初項は $(0, 1)$、$L_n$ の初項は $(2, \alpha+\beta)$である。よって、 $F_n,\, F_{n+1}$ は $V_\mathbb{Q}(\Gamma)$ の基底である。
$\Gamma^{(m)}$を有理多項式として表す方法
$\Gamma\in\mathbb{Q}[x]$ より、 $\alpha+\beta,\,\alpha\beta\in\mathbb{Q}$ である。よって$\alpha,\,\beta$ の任意の対称式は有理数である。よって任意の$k=0,\dotsc,m$について、$(x-\alpha^k\beta^{m-k})(x-\alpha^{m-k}\beta^k)$は有理多項式である。
$(x-\alpha^m)(x-\beta^m)$をまとめると再帰的に以下のように高々二次の有理多項式の積に分解できる。
\Gamma^{(m)}(x) = \begin{cases}
1,&\text{if } m = -1\\
x-1,&\text{if } m = 0\\
(x^2-L_mx + (\alpha\beta)^m) (\alpha\beta)^{m-1}\Gamma^{(m-2)}(x/(\alpha\beta)),&\text{otherwise.}
\end{cases}
また、完全に展開した形で表現を得ることもできる。
\begin{align*}
\beta^m\Gamma^{(m)}(x/\beta)(x-\alpha^{m+1}) &= \alpha^m\Gamma^{(m)}(x/\alpha)(x-\beta^{m+1})\\
\end{align*}
より、両辺の $x^k$ の係数に注目すると、 $\Gamma^{(m)}(x) = \sum_{k=0}^{m} c_k x^k$ について
\begin{align*}
&\beta^{m-k+1} c_{k-1}-\alpha^{m+1}\beta^{m-k} c_k = \alpha^{m-k+1} c_{k-1}-\beta^{m+1}\alpha^{m-k} c_k\\
%\iff& c_{k-1} = \frac{\alpha^{m-k}\beta^{m+1}-\alpha^{m+1}\beta^{m-k}}{\alpha^{m-k+1}-\beta^{m-k+1}}c_k\\
\iff& c_{k-1} = (\alpha\beta)^{m-k}\frac{\beta^{k+1}-\alpha^{k+1}}{\alpha^{m-k+1}-\beta^{m-k+1}}c_k\\
\iff& c_{k-1} = -(\alpha\beta)^{m-k}\frac{F_{k+1}}{F_{m-k+1}}c_k\\
\end{align*}
という等式を得る。 $c_{m} = 1$より、係数が決定でき、
c_{m-k} = (-1)^k (\alpha\beta)^{k(k-1)/2}\frac{F_{m+1}\dotsm F_{m-k+2}}{F_{k}\dotsm F_1}
であることが分かる。
$\Gamma^{(m)}$ が 1を根として持つかどうか考える。そのために具体的に $\alpha,\,\beta$ を決める必要がある。フィボナッチ数列の場合($\alpha+\beta=1,\,\alpha\beta=-1$)を考える。$m$ が奇数のとき、$\Gamma^{(m)}$ の根はすべて無理数である。 $m$ が偶数のとき、唯一の有理根 $(\alpha\beta)^{m/2}=(-1)^{m/2}$ を持つ。よって、 $m$ が 4の倍数のとき、またそのときに限り $\Gamma^{(m)}$ は1を根に持つ。
よって、$m$ が4の倍数でないとき、
\begin{align*}
\sum_{t=0}^n F_t^m &= r + \sum_{k=0}^m r_k F_n^k F_{n+1}^{m-k}\\
&= r + F_{n+1}^m\sum_{k=0}^m r_k \left(\frac{F_n}{F_{n+1}}\right)^k
\end{align*}
が成り立つ。 $r$ さえ分かっていれば、後は $r(x) := \sum_{k=0}^m r_kx^k$ に対する多項式補間で $r_0,\dotsc,r_m$ は計算できる。この算術計算量は $O(\mathsf{M}(m)\log m)$ である。
母関数の考察から
\begin{align*}
\frac{P(x)}{(1-x)Q(x)} &= \frac{r}{1-x} + \frac{R(x)}{Q(x)}
\end{align*}
と部分分数分解できるので、$r = P(1)/Q(1)$ と計算できる。この計算量は $O(\mathsf{M}(m))$ である。
よって、算術計算量 $O(\mathsf{M}(m)\log m)$ で係数はすべて計算できる。$m$ が4の倍数のときも同様。
なんかかっこ悪いので、 $r$ も一緒に多項式補間的なもので計算できないか？
また、$V_\mathbb{Q}(\Gamma^{(m)})$ の基底の取り方は他にも考えられる。例えば
\begin{align*}
V_\mathbb{C}(\Gamma^{(m)})&=\mathrm{span}_{\mathbb{C}}(\{(\alpha^k\beta^{m-k})^n\mid k =0,\dotsc,m\})\\
&= \mathrm{span}_{\mathbb{C}}(\{(-1)^{kn}\alpha^{(m-2k)n},\, (-1)^{kn}\beta^{(m-2k)n}\mid k=0,\dotsc,\lfloor m/2\rfloor\})\\
&= \mathrm{span}_{\mathbb{C}}(\{(-1)^{kn}F_{(m-2k)n},\, (-1)^{kn}F_{(m-2k)n+1}\mid k=0,\dotsc,\lfloor m/2\rfloor\})\\
\end{align*}
という基底の取り方もある。
関連問題 Yukicoder: No.2883 K-powered Sum of Fibonacci
線形漸化的数列のアダマール積
線形漸化的数列 $(u_n)_{n\ge 0}$ と $(v_n)_{n\ge 0}$ の特性多項式をそれぞれ
\begin{align*}
\Gamma_0(x) &= \prod_{k=1}^{d_0} (x - \alpha_k)\\
\Gamma_1(x) &= \prod_{\ell=1}^{d_1} (x - \beta_\ell)\\
\end{align*}
とする。このとき、数列 $(u_nv_n)_{n\ge 0}$ は
\begin{align*}
\mathrm{span}_\mathbb{C}\left(\{(\alpha_k\beta_\ell)^n\mid k\in\{1,\dotsc,d_0\},\, \ell\in\{1,\dotsc,d_1\}\}\right)
\end{align*}
に含まれるため、その特性多項式として
\begin{align*}
(\Gamma_0\star\Gamma_1)(x) &:= \prod_{k=1}^{d_0}\prod_{\ell=1}^{d_1} (x - \alpha_k\beta_\ell)
\end{align*}
を選ぶことができる。これを $\Gamma_0$ と $\Gamma_1$ の結合積と定義する。
定理 3.
\begin{align*}
V_\mathbb{Q}(\Gamma_0) &= \mathrm{span}_\mathbb{Q}\left(\left\{u_n^{(k)}\mid k\in\{1,\dotsc,d_0\}\right\}\right)\\
V_\mathbb{Q}(\Gamma_1) &= \mathrm{span}_\mathbb{Q}\left(\left\{v_n^{(\ell)}\mid \ell\in\{1,\dotsc,d_1\}\right\}\right)
\end{align*}
のとき、
\begin{align*}
V_\mathbb{Q}(\Gamma_0\star\Gamma_1) &= \mathrm{span}_\mathbb{Q}\left(\left\{u_n^{(k)} v_n^{(\ell)}\mid k\in\{1,\dotsc,d_0\},\, \ell\in\{1,\dotsc,d_1\}\right\}\right)
\end{align*}
証明は定理1, 2と同様なので省略。
しかし、定理3の具体的な応用は見つけられていない。
例えば累積和 $\sum_{n=0}^N u_nv_n$ の計算が最初に思いつく。$u_n^{(k)} = u_{n+k-1}^{(1)}$, $v_n^{(k)} = v_{n+k-1}^{(1)}$ と基底を取るとして、線形結合の係数が分かっていれば $u_N^{(k)}$ と $v_N^{(k)}$ の計算に $O(\mathsf{M}(d)\log N)$、線形結合に $O(d^2)$ の算術計算量で計算できる。
一方でこの問題に対しては他の計算方法もある。数列 $u_n$ と $w_n := v_{N-n}$ について $\sum_{n=0}^N u_nv_n=\sum_{n=0}^N u_n w_{N-n}$ と理解できる。ここで、数列 $w_n = v_{N-n}$は $n > N$ についても適切に拡張すると線形漸化的である。よって、 $u_n$ の母関数と $w_n$ の母関数の積の $x^N$ の係数を計算する問題と理解することができる。$w_n$ の初項の計算に $O(\mathsf{M}(d)\log N)$かかり、最終的な解の計算において分母の次数は $2d$ であるので、 $O(\mathsf{M}(2d)\log N)=O(\mathsf{M}(d)\log N)$ の算術計算量となる。$O(d^2)$ が現れないのでこちらの手法の方が効率的である。
おまけ: 結合積の計算
以下はこの論文で示された内容である。
Alin Bostan, Philippe Flajolet, Bruno Salvy, Éric Schost,
"Fast computation of special resultants,"
Journal of Symbolic Computation, vol. 41, no. 1, pp. 1-29, 2006.
https://doi.org/10.1016/j.jsc.2005.07.001.
モニック有理多項式の係数は根の基本対称式
e_k = \sum_{1\le i_1<\dotsb<i_k\le d} \prod_{j=1}^k \alpha_{i_j}
に符号を付けたものである。
一方で冪乗和
p_k = \sum_{i=1}^d \alpha_i^k
も対称式であるので有理数であり、また $e_1,\dotsc,e_d$ と $p_1,\dotsc,p_d$ は互いに変換できる(ニュートンの恒等式、アルゴリズムは後述)。
結合積の根 $(\alpha_i\beta_j)_{i,j}$ の冪乗和は
\sum_{i,j} (\alpha_i\beta_j)^k = \left(\sum_i \alpha_i^k\right) \left(\sum_i \beta_j^k\right)
とそれぞれの冪乗和の積として表せる。
これらの考察から結合積 $\Gamma_0,\,\Gamma_1$は以下のアルゴリズムで計算できる。
- $\Gamma_0$ と $\Gamma_1$ の係数は根の基本対称式 $(e_k(\Gamma_0))_{i=1,\dotsc,d},\,(e_k(\Gamma_1))_{i=1,\dotsc,d}$ であるが、それを冪乗和 $(p_k(\Gamma_0))_{i=1,\dotsc,d^2},\,(p_k(\Gamma_1))_{i=1,\dotsc,d^2}$ に変換する。
- $p_k(\Gamma_0\star\Gamma_1) = p_k(\Gamma_0)p_k(\Gamma_1)$ を $k=1,\dotsc, d^2$ について計算する。
- $(p_k(\Gamma_0\star\Gamma_1))_{k=1,\dotsc,d^2}$ を $(e_k(\Gamma_0\star\Gamma_1))_{k=1,\dotsc,d^2}$ に変換する。
あとは $e_k$ と $p_k$ の相互変換が効率的にできることを示せばよい。
$\Gamma$ より $Q(x)=\prod_{i=1}^d (1-\alpha_i x)$ を使う方が考えやすい。
以下の等式が成り立つ。
\begin{align*}
-\log Q(x) &= -\log \prod_{i=1}^d (1-\alpha_i x)\\
&= -\sum_{i=1}^d \log (1-\alpha_i x)\\
&= \sum_{i=1}^d \sum_{n\ge 1} \frac{(\alpha_i x)^n}{n}\\
&= \sum_{n\ge 1} \frac1n\left(\sum_{i=1}^d \alpha_i^n\right) x^n\\
&= \sum_{n\ge 1} \frac1n p_n x^n.
\end{align*}
この等式に基づいてステップ1とステップ3はそれぞれ $O(d\mathsf{M}(d))$ と $O(\mathsf{M}(d^2))$ で計算ができる。