形式的べき級数

Operations on Formal Power Series - Codeforcesを読め　終わり

以下では形式的べき級数環および形式的べき級数体にという概念を既知とし、その演算を具体的に計算機で計算するという部分に焦点を当てる。係数環は体とする。

数学わかる人向けの説明：
形式的べき級数の操作は係数体の標数が0であることを課していることが多いが、競プロの文脈ではFpを係数体として考えることになる。
その辺の問題を回避するには、「p-1次未満の多項式に関する操作を、一旦Q[[x]]$\mathbb{Q}[[x]]$に持ち上げて計算した後、Fp[x]${\mathbb{F}}_p[x]$に戻している」と考えるのがよさそう（ほんとう？）

●加減算、スカラー倍
F±G,kFの結果をn次の精度で得るには、F,Gがn次の精度でわかっている必要がある。
やるだけO(n)

●形式的微積分
F',∫Fの結果をn次の精度で得るには、Fがn+1,n-1次の精度でわかっている必要がある。
やるだけO(n)
ここで積分は、定数項が0になるようにとるものとする

●乗算
FGの結果をn次の精度で得るにはF,Gがn次の精度でわかっている必要がある。
FFTでO(nlogn)

●除算
1/Fの結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
1/Fが求められれば良い。Fの定数項は1であるとしてよい。
ニュートン法により求められる(※)。
具体的には、Fが与えられた時、FG=1となるGを次の手続きで求める。
f(x)=1/x−F$f(x)=1/x-F$とおくと、求めるべきはf(x)=0$f(x)=0$の解。ニュートン法の漸化式はGk+1=2Gk−G2kF$G_{k+1}=2G_k-G_k^{2}F$となる。
この式を用いて計算するとGk+1F−1=−(GkF−1)2$G_{k+1}F-1=-(G_{k}F-1{)}^2$を得、たしかに2次収束していることがわかる(※※)。
ニュートン法の計算過程において、Gk$G_k$の精度がO(2k)$O(2^k)$次程度であることから、F$F$もその程度の次数で打ち切ったもので計算を行って良い。
(実装上は2k$2^k$なのか2k+1$2^{k+1}$なのか2k+1$2^k+1$なのかなど、細かいところに注意が必要)
漸化式1回の計算には乗算が定数回あるので計算量は∑k=1,2,4,8,...O(klogk)=O(nlogn)$\sum _{k=1,2,4,8,...}O(k\log k)=O(n\log n)$
(※ニュートン法が一般に形式的べき級数環でうまくいくかは考えてないが、体上の形式的べき級数環はHensel環なのでHensel's lemmaから言えるはず)
(※※一般の場合がどうであるにせよ、今回うまくいくことここで正当化されている)

●平方根
√Fの結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
Fの定数項は1であるとしてよい。(mod pでの平方根を求める方法は既知とする)
ニュートン法により求められる。
具体的には、Fが与えられた時、G^2=FとなるGを次の手続きで求める。
f(x)=x2−F$f(x)=x^2-F$とおくと、求めるべきはf(x)=0$f(x)=0$の解。ニュートン法の漸化式はGk+1=Gk2+F2Gk$G_{k+1}=\frac{G_k}{2}+\frac{F}{2G_k}$となる。
この式を用いて計算するとG2k+1−F=(G2k−F)24G2k$G_{k+1}^2-F=\frac{(G_k^2-F{)}^2}{4G_k^2}$を得、たしかに2次収束していることがわかる。
漸化式1回の計算には除算が定数回あるので計算量は∑k=1,2,4,8,...O(klogk)=O(nlogn)$\sum _{k=1,2,4,8,...}O(k\log k)=O(n\log n)$

●exp
Fを定数項が0であるような形式的べき級数とする。
このときexp(F)をexp(F)=∑∞k=0Fkk!$\exp (F)=\sum _{k=0}^{\mathrm{\infty }}\frac{F^k}{k!}$により定める。
（定数項が0でない場合、定数項の計算に無限和が残って困る）
exp(F)の結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
実際に求めるときにはlogを使うので、説明はlogの話のあとで。

(※分母にn!があることから分かる通り、本当は係数体の標数が0のときにしか定義されないが、標数未満の次数についてのみ考える場合はいい感じになる。正確にはこういう可換図式を睨むことになるはず？　もっと簡単だったら教えて)
Q[[x]]exp⏐↓⏐Q[[x]]−→−−−−−→−−−−Q[[x]]/(xn)  ⊃exp⏐↓⏐Q[[x]]/(xn)  ⊃  subset of Z(p)[[x]]/(xn)exp⏐↓⏐  Z(p)[[x]]/(xn)−→−−−−−→−−−−Fp[[x]]/(xn)exp⏐↓⏐Fp[[x]]/(xn)$\begin{array}{ccccccc}\mathbb{Q}[[x]]& \stackrel{}{\to }& \mathbb{Q}[[x]]/(x^n)\supset & & \text{subset of }{\mathbb{Z}}_{(p)}[[x]]/(x^n)& \stackrel{}{\to }& {\mathbb{F}}_p[[x]]/(x^n)\\ \exp \downarrow & & \exp \downarrow & & \exp \downarrow & & \exp \downarrow & \\ \mathbb{Q}[[x]]& \stackrel{}{\to }& \mathbb{Q}[[x]]/(x^n)\supset & & {\mathbb{Z}}_{(p)}[[x]]/(x^n)& \stackrel{}{\to }& {\mathbb{F}}_p[[x]]/(x^n)\end{array}$

●log
Fを定数項が1であるような形式的べき級数とする。
logはexpの逆演算で定義される。すなわち、定数項が1であるようなFに対して、exp(G)=F$\exp (G)=F$を満たすGがただ1つ存在し、それをG=log(F)$G=\log (F)$と定める。(※次数が低い方から順に考えると存在し一意であることがわかる)
log(F)の結果をn次の精度で得るにはFがn次の精度でわかっている必要がある。
合成関数の微分(※)から
exp(G)=FG′exp(G)=F′G′F=F′G=∫F′/F$$\begin{gathered} \exp (G)=F \\ {G}^{\prime }\exp (G)=F^{\prime } \\ {G}^{\prime }F=F^{\prime } \\ G=\int F^{\prime }/F \end{gathered}$$
したがってO(nlogn)$O(n\log n)$
(※expの実体はべき級数なので、(解析学の意味ではなく、代数学の形式的操作の意味で)成立することが示せる)

●expふたたび
ニュートン法により求める。
f(x)=log(x)−F$f(x)=\log (x)-F$とおくと、求めるべきはf(x)=0$f(x)=0$の解。ニュートン法の漸化式はGk+1=Gk(1−f(Gk))$G_{k+1}=G_k(1-f(G_k))$となる。
計算するとf(Gk+1)=−f(Gk)22+O(f(Gk)3)$f(G_{k+1})=-\frac{f(G_k{)}^2}{2}+O(f(G_k{)}^3)$となり、確かに2次収束していることがわかる。
漸化式1回の計算にはlogと乗算が1回あるので計算量は∑k=1,2,4,8,...O(klogk)=O(nlogn)$\sum _{k=1,2,4,8,...}O(k\log k)=O(n\log n)$

●expその2
冒頭で挙げた記事に書かれているやつ。
これもニュートン法だが、logを明示的に計算しない。
代わりにHk=1/Gk$H_k=1/G_k$となるものを持つ(等号はmod x^(2^k))。具体的に漸化式は次のようになる。
Hk=2Hk−1−GkH2k−1$H_k=2H_{k-1}-G_k{H}_{k-1}^2$
Gk+1=Gk(1−∫Hk(G′k−GkF′))$G_{k+1}=G_k(1-\int H_k(G_k^{\prime }-G_k{F}^{\prime }))$
Hの方の漸化式は少し前に述べた、逆元を求めるニュートン法そのものなので説明は不要だろう。Gの漸化式について述べる。
Hk=1/Gk$H_k=1/G_k$を漸化式に代入すると
∫Hk(G′k−GkF′)=∫(G′kGk−F′)=log(Gk)−F=f(Gk)$$\begin{gathered} \int H_k(G_k^{\prime }-G_k{F}^{\prime }) \\ =\int (\frac{G_k^{\prime }}{G_k}-F^{\prime }) \\ =\log (G_k)-F \\ =f(G_k) \end{gathered}$$
となり、同じ式が得られた。(※等号は mod x^(2^k))
(※最初に挙げたlogを使うものの計算量は各kで乗算2回除算1回積分1回。この方法は乗算3回微分1回積分1回である。どっちの方が早いかは知らん)

●平方根その２
Fの定数項は1であるとしてよい。
指数法則の成立が確認できる。すなわちexp(F+G)=exp(F)exp(G)$\exp (F+G)=\exp (F)\exp (G)$が成り立つ。(※解析学の意味ではなくｒｙ)
このことから、n/mに対してexp((n/m)log(F))=Fn/m$\exp ((n/m)\log (F))=F^{n/m}$になることがわかる。
したがってexp((1/2)log(F))$\exp ((1/2)\log (F))$を計算すれば良くO(nlogn)$O(n\log n)$