Formal Power Series (FPS)

この記事を書いた4時間後に以下の記事が公開されました。これを読もうね－完－
maspypy.com

以上で本質情報は終了です。ありがとうございました。以下はおまけです。

まえがき

この記事を読んでも競プロに強くはなれませんよ。
FFTで多項式乗算が高速にできる原理をしらなくても、FFTを実装すれば多項式乗算ができるのと同じです。

環

カジュアルな定義："足し算"と"掛け算"が定義されている集合を環という。
もうすこし正確な定義：集合と"足し算"と"掛け算"の3つ組を環という。（同じ集合に対して、違う"足し算"と"掛け算"を定義して、違う環を作ることもできるので）
本当に正確な定義：wikipediaでも読んでろ→環 (数学) - Wikipedia
ここでいう"足し算"と"掛け算"はそういう名前の二項演算のことであって、別に足し算と掛け算のことではない。でも足し算と掛け算みたいな性質（例：分配法則）が成り立っていることを要求する。
さらに、"足し算"は暗黙のうちに"引き算"ができることを要求する。"掛け算"は別に"割り算"ができることを要求しない。

例1

整数全体の集合に、+を"足し算"、×を"掛け算"と定めたものは環になる

例2

0以上M未満の整数全体の集合に、mod Mでの足し算を"足し算"、mod Mでの掛け算を"掛け算"と定めたものは環になる

例3

uint32で表すことができる数全体の集合に、bitwise xorを"足し算"、bitwise andを"掛け算"と定めたものは環になる

例4

0以上2^2^N未満の整数全体に、bitwise xorを"足し算"、Nim productを"掛け算"と定めたものは環になる
これは例3と同じ集合に別の演算が入る例でもある

例5

0以上の整数全体の集合に、minを"足し算"、+を"掛け算"と定めたものは環ではない。minは"引き算"ができないので。ちなみに、環の定義から「"引き算"ができる」を抜いたものを半環という
（余談：半群は単位的とは限らないのに半環の加法群は単位的なんですね～）

例6

整数を成分とする2×2の正方行列全体の集合に、成分ごとの和を”足し算"、行列積を"掛け算"と定めたものは環になる。ただし、この環は掛け算が可換でない。つまり、"掛け算"を×であらわしたとき、A×B=B×Aが一般には成り立たない。
"掛け算"が可換な環を可換環といい、可換でない環を非可換環という。
非可換環、直感に反するので困るんだよね。そういうのは面倒なので、以下この記事では単に環と言ったときは可換環を指すものとする。

形式的べき級数

定義：数列 $(a_0,a_1,a_2,\ldots)$ のことを形式的べき級数(FPS)という。
多項式？　不定元X？　なんの話ですか？　べき級数というのは数列のことですよ。

形式的べき級数環

次で定義される環を形式的べき級数環という。
集合：全ての数列からなる集合 $\{(a_0,a_1,a_2,\ldots)\}$
"足し算"： $(a_0,a_1,a_2,\ldots)+(b_0,b_1,b_2,\ldots)=(a_0+b_0,a_1+b_1,a_2+b_2,\ldots)$
"掛け算"： $(a_0,a_1,a_2,\ldots)*(b_0,b_1,b_2,\ldots)=(c_0,c_1,c_2,\ldots)$ としたとき、 $c_i=\sum_{k=0}^{i}a_kb_{i-k}$
数列の話をしてたのに急に本性表してきたなこいつ。
"足し算"と"掛け算"の定義をみるとわかるとおり、数列 $A:=(a_0,a_1,a_2,\ldots)$ に対して、不定元Xを用いた無限級数 $f_A(X)=a_0+a_1X+a_2X^2+\ldots$ を対応させると、この"足し算"と"掛け算"は無限級数の足し算と掛け算だと思うことができるんですね～。あーあ、せっかく数列の話ってごまかしてたのに。そういうわけで以下ではFPSは不定元Xを用いた無限級数を用いて表します。無駄な努力だったな……。
ところでもちろん、数列の各要素に対しても"足し算"と"掛け算"が定まっている必要がある。つまり、FPS環を考えたいなら数列の要素はなんでもいいというわけではなく、それもまた環の元である必要がある。要素が環 $R$ の元であるような数列の集合から作ったFPS環のことを $R[[X]]$ と書く。このとき、 $R$ を $R[[X]]$ の係数環という。

例1

上の方でやった、整数全体に普通の足し算と普通の掛け算を定めるやつ、あれのことを $\mathbb{Z}$ と表す。（単に集合としての整数全体をさすことももちろんあるけど、環として考えますよというのを強調しています）
$\mathbb{Z}[[X]]$ は整数係数のFPS環である。

例2

上の方でやったmodMのやつのことを数学では $\mathbb{Z}/M\mathbb{Z}$ と書きます。（この記法はふつう剰余環を意識したものなので、上でやったことを定義とするわけではないけど、できるものは同じなのでここでは気にしないことにしましょう）
$(\mathbb{Z}/M\mathbb{Z})[[X]]$ は係数をmod Mで考えるFPS環。

環の乗法逆元

乗法逆元の話をするまえに加法逆元の話を思い出しておこう。
"引き算"というのは、二項演算ではなく、単項演算だったんですよね（！？）
どういうことかというと、xに対して、x+y=0となるようなyのことをxの加法逆元といい、-xと表して、一般にa-bというのはa+(-b)のことだった、という話です。
これを踏まえて乗法逆元の話を考えてみる。環の"掛け算"は"割り算"ができる必要はないといったが、6/-1=-6のように、できることももちろんある。
定義：xに対して、x*y=1となるようなyのことをxの乗法逆元といい、 $x^{-1}$ と表す。
一般にa/bというのは $a*b^{-1}$ のことだった、ということになるわけですね。
（この説明にはちょっとごまかしがあって、例えば $\mathbb{Z}$ において6/2を「2x=6となるx」として定義する感じで、部分的には二項演算としての割り算ができることもあるんですが、そういうのは考えません）
主張：乗法逆元は存在すれば一意。
証明は各自
定義：乗法逆元が存在するような元のことを可逆元という。

例1

$\mathbb{Z}$ の可逆元は $\pm 1$

例2

$\mathbb{Z}/9\mathbb{Z}$ の可逆元は $1,2,4,5,7,8$
（わかってる人向けのエクスキューズ：同値類だから整数そのものじゃないとかいう難しい話を初心者にするのはやめよう！だってここで同値類の定義してないし）

例3

$\mathbb{Z}[[X]]$ の可逆元はなんでしょう？
答え：定数項が $\pm 1$ であるような全ての元
なんで？
1-Xの乗法逆元を求めて見よう。そのようなものが存在するなら、定義から
$(1-X)(b_0+b_1X+b_2X^2+b_3X^3+\ldots)=1$ となる。
次数ごとに左辺と右辺を比べてみよう。
定数項： $1*b_0=1$ → $b_0=1$
1次の項： $1*b_1+(-1)*b_0=0$ → $b_1=1$
2次の項： $1*b_2+(-1)*b_1=0$ → $b_2=1$
…
ということで、以下帰納的に $b_i=1$ と求まる。つまり $(1-X)^{-1}=1+X+X^2+\ldots$ となるということ。この求め方をぐっと睨むとわかってもらえる通り、定数項が1であるようなFPSの逆元を求めようとすると $1*b_n+a_1*b_{n-1}+\ldots=0$ という形の方程式を解いて $b_n$ を求めることになるが、これはnの小さい順にやると自明。

？？

この話って要するに、実数の逆元を考えている時に、「1÷7は0.142857……と必要なだけ計算することができますね。だから逆元は存在するんです！」と同じ論法をしている。間違ってはないんだけど、その「……」ってどういう意味やねんという話になります。いやなるかどうかはしりませんが、俺はなったので、きっちりやっておきましょう。
「可逆なfとその逆元gに対して、帰納法で任意のnについてgのn次の係数を一意に決定することができ、このとき任意のn>0に対してfgのn次の係数が0になることを具体的に計算できる。証明終わり」めでたしめでたし。いやー、収束がどうこうとかいう話をする必要があるのかと思って一瞬焦った。ちなみに例に挙げた実数の逆元の話のときは、繰り上がりとかいう概念のせいで同じ論法ではうまくいかないので収束がどうこうとかいう話をする必要があります（多分）

主張：FPS環の元は、定数項が係数環の可逆元であるとき、かつその時に限り可逆である。
証明は各自

有限項で打ち切る話

コンピューターは有限しか扱えないので、 $(1-X)^{-1}$ すらナイーブには表すことができません。
でも実数を「1÷7は……うーんまあ0.142857で近似すればいいかｗ」と計算するように、FPSもn次の項までで打ち切って近似計算できます。
実数だと誤差評価は面倒な話ですが、FPSのときはn次の項で打ち切ってFPS環の計算をするとn次の項までの精度があり続けます。繰り上がりがないのでね。
本質的には、「整数 $\mathbb{Z}$ をmod Mの世界 $\mathbb{Z}/(M)$ に持っていってもコンパチ」というのと同様に、「FPS環 $R[[X]]$ を有限項で打ち切って $R[[X]]/(X^n)$ に持っていってもコンパチ」という話なんですけども。

exp

定義：有理数を含む環を係数とするFPS環において、定数項が0であるようなの元 $f$ に対して、 $\exp(f)=\sum_{i\geq 0}\frac{1}{i!}f^i$ と定める。
有理数を含むという条件は、要するに1,2,3,4,…での割り算ができますという意味です。
この定義式は $\exp(X)=1+X+\frac{1}{2}X^2+\frac{1}{6}X^3+\ldots$ というおなじみの式を導きますが、あくまで定義であって、実関数 $e^X$ のマクローリン展開とはなんの関係もありません。
行列Aに対してexp(A)を考えるのと同じで定義です。
（同じ名前がついている以上、本当になんの関係も無いわけではないですが、実関数の常識は忘れましょう）
余談：定義域は「定数項が0」ほど厳しい必要はなく、「定数項が冪零」でいいと思うんですが、まあ面倒なのでここでは0にしておきましょう。
$\mathbb{Q}$ を含んで、かつ0でない冪零元が存在するような環の例としては $\mathbb{Q}[t]/(t^2)$ があり、 $(\mathbb{Q}[t]/(t^2))[[X]]$ において $\exp(t)=1+t$ となります。

exp(1)

「『定数項が0であるようなFPSの元 $f$ に対して』←？？？　 $\mathbb{R}[[X]]$ 上では $\exp(1)=e$ だし、定数項があっても大丈夫じゃん」
大丈夫ではありません。……という話がしたいんですが、この話をするためには収束がどうこうとかいう話をする必要がある。さっき頑張って回避したのに、結局やらなきゃだめなのか……

お断り

以下、うっかり付値環の話をしてしまったので、係数が体でないと話が通らなくなってしまいました。ということで以下では係数は体です。
"付値"という言葉を使っているものの、付値の性質は完備性しか使っていないので、それを別に証明すれば環を係数とするFPS環でも同様にいえます。というかここでは完備性の証明はしていないので全部一緒です。
他にも $\{f+(X^n)\}$ を開基とする位相を入れて(距離空間ではなく)位相空間での収束を考えてもいえるみたいです。

証明の準備

expの話がしたいだけなので、expの話ができるギリギリまでいろいろ省略
定義：体 $\mathbb{F}$ を係数とするFPS環 $\mathbb{F}[[X]]$ に対して、付値 $\nu:\mathbb{F}[[X]]\to\mathbb{Z}_{\geq 0}\cup\{\infty\}$ を、 $\nu(f)=\min\{n \mid f \text{のn次の係数が0でない}\}$ と定める。このとき、FPS環の元f,gに対して、その距離を $d(f,g)=2^{-\nu(f-g)}$ で定める。
なんのこっちゃねんという感じですが、要するに「低次の項がいっぱい一致してたらだいたい一緒」という気持ちです。「0.12345……と0.12489……は2桁目まで一致してるから、距離は10^-2くらいかなーｗ」というのと同じで「 $1+2X+3X^2+4X^3+5X^4+\ldots$ と $1+2X+4X^2+8X^3+9X^4+\ldots$ は2つ目の項まで一致してるから、距離は2^-2くらいかなーｗ」という気持ちです。
定義：距離空間の元の列 $a=(a_1,a_2,\ldots)$ に対して、 $\lim_n d(x,a_n)=0$ が成り立つとき、aはxに収束するという。また、あるxが存在して数列aがxに収束するとき、aは収束するという。
無限に近づくなら収束、という普通の定義。これはFPS環とか関係なく、距離空間のお話です。
定義：体係数FPS環における収束は、付値によって定まる距離による収束とする。
それはそう。普通は「位相」という言葉を使うけど、面倒なので……。
定義：無限和 $\sum_{i=1}^{\infty}a_i$ は、数列 $A_n=\sum_{i=1}^{n}a_i$ が収束するとき、その収束先を値として定義する。
要するに、 $\sum_{i=1}^{\infty}\frac{1}{2^i}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots$ というやつは、部分和のなす列 $(\frac{1}{2},\frac{3}{4},\frac{7}{8},\ldots)$ が1に収束するので $\sum_{i=1}^{\infty}\frac{1}{2^i}=1$ というようにここを等号で結んじゃいますねという話です。これもFPSとか関係なく、無限和の定義に関するお話。
主張：体係数FPS環は完備離散付値環である。
証明：忘れた。代数学の本を読みましょう。
この"完備"というのは、付値によって定まる距離による距離空間としてみたとき完備であるという意味。距離空間が完備であるというのは、任意のコーシー列が収束するという意味。数列 $(a_n)$ がコーシー列であるとは、 $\forall \epsilon>0 \exists N \forall n,m\geq N. d(a_n,a_m)<\epsilon$ を満たすということ。収束列⇒コーシー列は一般に成り立つので、逆が成り立てば完備ということ。
例えば、有理数は完備ではない。なぜなら、列 $(3,3.1,3.14,3.141,3.1415,\ldots)$ はコーシー列だが、収束先が有理数の中に存在しないので。

exp再び

主張：有理数を含む体を係数とするFPS環において定義された $\exp(f)$ は、fの定数項が0のとき、かつそのときに限り定義される。
証明：
・定数項が0⇒定義される
$\exp_n(f)=\sum_{i=0}^{n-1}\frac{1}{i!}f^i$ とする。ここで、列 $F_n=\exp_n(f)$ を考える。少し考えると、 $n,m\geq N$ のとき、 $F_n$ と $F_m$ のN次未満の項は一致していることがわかる。つまり、数列 $(F_n)$ はコーシー列である。したがって完備性からこの数列は収束し、無限和の定義から収束先が $\exp(f)$ である。
・定数項が0でない⇒定義されない
$f$ の定数項を $a_0\neq 0$ とする。 $A_n=\exp_n(a_0)$ を考えると、 $a_0$ は冪零でないので任意のnで $A_n\neq A_{n+1}$ となる。したがって、列 $F_n=\exp_n(f)$ は任意のnで $d(F_n,F_{n+1})=1$ となり、コーシー列でないので、特に収束列でない。

係数環が一般の環のときは、Mを $a_0^M=0$ を満たす正整数として、証明中の「 $F_n$ と $F_m$ のN次未満の項は一致していることがわかる」を、「 $F_n$ と $F_m$ のN+1-M次未満の項は一致していることがわかる」に書き換えると定数項が冪零のケースがいえる。

つまり？

$\mathbb{R}[[X]]$ の世界では $\exp(1)=e$ とはしないよというのは、 $\exp_n(1)$ の列 $(1,2,5/2,8/3,\ldots)$ の定数項がいつまで経っても収束しないからですね。実数でいうところの、上の方の桁がいつまでもガチャガチャ変わってたら収束とはいわねえよという気持ちです（←これはかなり嘘が入っています。プロ各位怒らないで）

ここまでで7500文字くらいらしいです。一通りのトピックは書いたと思うし飽きたのでそろそろやめます

追記

Q.「expは $\mathbb{Q}$ を含む環を係数とするFPS環上で定義される」って書いてるけど、mod998244353でやっとるやんけ、なんやねんぽまえ
A.完全に正しい指摘。でもn次未満の項しか必要ない場合、つまり $R[[X]]/(X^n)$ で考えているときは、 $\exp$ の代わりに $\exp_n$ を使っても出てくるものは同じになるから、1,2,…,n-1さえ可逆なら十分なんですね～。
正確には、 $R[[X]]$ でexpが定義可能なとき以下の図が可換図式であり、右行ってから下行くルートは1,2,…,n-1さえ可逆なら定義できるので、「expが定義不可能だが、1,2,…,n-1が可逆」というときはこっちルートを採用して使いましょう、という意味。
$\require{AMScd} \begin{CD} R[[X]] @>自然な射影>> R[[X]] / (X^n)\\ @V{\exp}VV @V{\exp_n}VV \\ R[[X]] @>自然な射影>> R[[X]] / (X^n) \end{CD}$
正当性をいうには、以下が可換であることを言う必要があると思う。（右上から右下への写像がもし $\exp_m$ なら自明だけど、実際には $\exp_n$ なので、可換になることはby definitionとはいかないはず……）
$\require{AMScd} \begin{CD} R[[X]] /(X^m)@>自然な射影>> R[[X]] / (X^n)\\ @V{\exp_m}VV @V{\exp_n}VV \\ R[[X]] /(X^m)@>自然な射影>> R[[X]] / (X^n) \end{CD}$

Q.logは？
A.expの逆演算として定めるよりは、天下りに定義したあと、expの逆演算になっていることを確かめる方が簡単でしょう。
定義：FPS環の元であって、定数項が1であるようなfに対して、 $\log(f)=\sum_{i\geq 1}\frac{(-1)^{i+1}}{i}(f-1)^i$ とする。
$\exp(\log(f))=\log(\exp(f))=f$ となることを各自確かめること

Q.指数法則とかchain ruleとか……
A.実は成り立ちます。でも、あなたのよく知るそれは、たぶん実関数の話ですよね。FPS環上の演算としてみても成立するかどうかは各自確かめること

メモ

yukicoderでゆるふわgolf