Subspace Inversion

· · 个人记录

（这里采取符号 (\omega;q)=(1-\omega) (1-\omega q)\cdots(1-\omega q^{n-1})）

设 f,g 满足

g_n = \sum_k \binom n k_q f_k

那就是

\frac{g_n}{(q;q)_n} = \sum_k \frac{f_k}{(q;q)_k} \frac{1}{(q;q)_{n-k}}

若要进行反演，只需计算乘法逆

\left(\sum_n \frac{x^n}{(q;q)_n}\right)^{-1}

不妨记括号内为 \zeta(x)，注意到

\zeta(x)-\zeta(qx) = \sum_n \frac{(1-q^n)x^n}{(q;q)_n} = x \zeta(x)

因此

\zeta(x)= \frac{\zeta(qx)}{1-x} = \frac{\zeta(q^2x)}{(1-x)(1-qx)} = \cdots = \frac1{(x;q)_{\infty}}

故有

\zeta(x)^{-1} = (x;q)_{\infty} = (1-x)\zeta(qx)^{-1}

解得

\zeta(x) = \sum_n \frac{(-1)^n q^{n(n-1)/2}}{(q;q)_n}x^n

因此，我们得到了子空间反演系数

f_n = \sum_k (-1)^k \binom n k_q q^{k(k-1)/2} g_{n-k}