FPS周りの用語の整理

2026/03/14

趣旨

競技プログラミング界隈ではFPS（形式冪級数）が良く言及されます。

しかしながらあまり意味を知らずに使っている人も多いようで、FPS以外の用語で言及した方が適切な文脈でもFPSとして言及してしまうという状況が散見されるようです。

例えば多項式と言えば良いものをFPSと言ってしまったり、ですね。

卑近な用語で例えるならば、

整数の問題を見て「実数の問題は苦手だなぁ」と表明してしまう。（整数は実数なのであってはいる）
行列を２つ掛け算する問題を見て「行列累乗か～気付かなかった」と表明してしまう。（どんな行列もその行列自身の$1$乗なのであってはいる）

といった状況を思い浮かべてください。別に好意的に解釈できない表現ではないですが、読んだ人からは「この人、実数／行列累乗って何だか知らずに話してない？」と訝しげに見られてしまい大抵の場合は損になりそうです。違和感がありすぎるので、さすがにこういう状況は起こらないでしょう。

しかしながらFPSではこれに類する状況が起こりがちなようです。ここではFPS周りの用語を正確に解説することで、違和感のある表現を減らしていくお手伝いをさせていただきます。

注意

用語の使い方に関する注意を解説する際は、用語の定義に厳密に則って解説するつもりです。

仮に例えば「競技プログラミング界隈では多項式の意味でFPSという言葉が使われるんですよ」という人がいたとして、その流儀を否定するものではありません。

単にFPSという用語の一般的定義に則ってその用法を説明するだけです。

多項式

多項式の具体例は、$x$とか$x^2-x$とかそういうやつでしたね。$x$は不定元です。不定元ってそもそも何でしょうね？

多項式を語る時、その定義は疎かにされがちです。定義を固定しないと「不定元とは何か？」すらふわっとした回答しかしにくいので、ここでは定義をきちんと固定します。

なお定義の仕方は色々あり、ここで紹介するのはあくまで一例です。

定義

(1) $X$を集合とする$X$値点列とは、写像$\mathbb{N} \to X$のことである。$X$値点列$a$と$d \in \mathbb{N}$に対し、$a(d)$を$a_d$と書き表す。

(2) $R$を環とする。$R$係数の多項式とは、$R$値点列$f$であって$\# \{d \in \mathbb{N} \mid f_d \neq 0 \} < \infty$を満たすもののことである。

なおここでは環といったら単位的可換環を表します。$R$係数多項式全体の集合には$R$の環構造から自然に$R$代数構造が定まります。

$R$係数多項式$f$と$d \in \mathbb{N}$に対し$f_d$を$f$の$d$次係数と呼びます。なお(1)で$a(d)$をわざわざ$a_d$と書くように直したのは、$()$を使った代入記法を多項式に特殊化（別の意味に再定義）させたいからです。

というわけで$R$代数$A$と$a \in A$に対し、$f(a)$を$\sum_{d=0}^{\infty} f_d a^d \in A$と定義し直します。ここで無限和は本質的有限和（有限個の項を除いて$0 \in R$である無限和）なので自然に意味を持ちますし、$A$に離散位相を入れた時の級数の極限だと思っても良いです。

この代入演算が忘却関手に対する左随伴性を持つことから、より一般に自由構成の像を多項式対象と呼ぶこともあります。カッコつけたければ「$R$係数多項式環は$R$代数の圏から集合の圏への忘却関手の左随伴に$\{0\}$を代入したもののことだよ」とか「多項式は環の圏から可換モノイドの圏への乗法に関する忘却関手の左随伴に$\mathbb{N}$を代入したもののことだよ」とか言ってもいいですが、左随伴は同型を除かなければ一意ではないので厳密には定義になっていないため最初から分かっている相手でないと騙してしまうことになりかねないので気をつけましょう。

さて多項式の定義も終わったことですし不定元を定義しましょう。

$R$係数多項式であって$1$次係数が$1 \in R$でありかつ任意の$d \in \mathbb{N} \setminus \{1\}$に対し$d$次係数が$0 \in R$であるものが一意に存在するので、それを$R$係数多項式の不定元と呼びます。

他の数学概念同様、$R$係数多項式の不定元も記号で置いて構いません。例えば$x$などが良く使われます。

$R$係数多項式の不定元を$x$と置いている文脈では、$R$係数多項式全体の環を$R[x]$と書き表します。すると$x \in R[x]$となり、$R[x]$は環なので$x^2$なり$x^2-x$なりも自然に意味を持ちます。

複数種類の環$R$を考える際は$R$ごとに不定元の記号を変えた方が安全ですが、曖昧さがない場合は記号が濫用されます。

例えば$R$として$\mathbb{R}$を考えて不定元を$x$と置いている時、$R$として$\mathbb{R}[x]$も考える場合は記号の濫用を避けた方が良く、しばしば不定元を$y$と置きます。この場合、$\mathbb{R}[x]$係数多項式の環は$\mathbb{R}[x][y]$となるわけですね。

また多項式環を表すためカッコ記号が$[x][y]$のように連続する場合、それらをまとめて$[x,y]$と略記します。つまり$\mathbb{R}[x,y] = \mathbb{R}[x][y]$です。$2$変数多項式環はこのように作られるわけですね。$3$変数以上も同様です。

なお$\mathbb{R}[x,y] \cong \mathbb{R}[y,x]$みたいなお話をしたい時は、上の定式化だとやや不便なので各自好きに修正してください。数学で１つの概念に流儀がいっぱいあるのは、今したい話に適合した定義の中で簡便なものを採用したいからですね。

多項式関数

$R$を環とします。$R$上の多項式関数とは、写像$f \colon R \to R$であって以下の条件を満たすもののことです。

ある$R$係数多項式$g$が存在して、任意の$r \in R$に対し$f(r) = g(r)$が成り立つ。

何だ、多項式関数は多項式そのもののことか、と思いきや概念としては別物です。$R$値多項式全体の環を$P_R$と置くと、単に自然な全射環準同型$R[x] \twoheadrightarrow P_R$があるだけです。

常に同型というわけですらない２つの概念を同一視するのは危険なのでやめておきましょう。同型でない$R$の例としては競技プログラミングでもお馴染みのものがあるので、ぜひ考えてみてください。

なお今回は$1$変数の場合だけ扱いましたが、多変数も同様（多項式関数と多項式は別概念）です。

FPS

FPS（形式冪級数）とは、大雑把に言うと「多項式を無限次に拡張したもの」です。

多項式の定義を固定しないと「とはいえ無限次に拡張するとは？」となってしまうかもしれませんが、多項式の定義を固定した今、FPSも厳密に定義することが可能です。

もちろん定義の仕方は色々あり、ここで紹介するのはあくまで一例であることはお忘れないようにお願いいたします。

定義

$R$を環とする。$R$係数の形式冪級数とは、$R$値点列のことである。

もう既に定義した概念に名前をつけ直しただけでしたね。定義から、$R$係数多項式は$R$係数形式冪級数です。逆は$R$が零環でない限り成り立ちません。

$R$係数多項式の不定元を$x$と置いている文脈では、$R$係数形式冪級数全体を$R[[x]]$と書き表します。$R[[x]]$も自然と$R$代数をなし、$R[x]$はその部分$R$代数となります。

流儀次第では$R[[x-1]]$などの書き方も許容されます。どんな流儀だとうまくいくか考えてみましょう。

形式冪級数$f$のことをしばしば

\[ \sum_{d=0}^{\infty} f_d x^d \]

とも書き表します。形式的にこう書き表していると思ってもいいですし、$x$進位相に関する級数の極限を考えてると思ってもよいです。$f_0 = 0$の場合には$d = 1$からの和で表したりなど記法の亜種も多いので、極限と思った方が臨機応変に対応しやすいかもしれません。

母関数

$R$値点列$a$の（通常型）母関数とは、$R$係数形式冪級数$a$のことです。

なお$R$値点列でなく$R$値有限列に対しても同様に母関数が定まり、これは結果的に$R$係数多項式になります。

$R$値形式冪級数という概念を$R$値点列そのものとして定義する流儀では、母関数を取るという操作が数学的には何もしていないわけですね。

では何故あえて「母関数を取る」なんて表現するのでしょうか？　数学的に何もしないのであれば表現する必要はないでしょうし、逆に「母関数の母関数の母関数を取る」なんて言っても良いのではないでしょうか？

これは主観ですが、数学で名前を呼び分ける時、皆さん頭の中でプログラミングにおける型みたいなものを念頭に置いている感じがするんですよね。だから数列の母関数を取ると宣言する時は、これから形式冪級数と見て形式冪級数環に関わる手法を駆使することを読者に宣言しているのだと考えましょう。

例えば整数列は$\mathbb{Z}$係数形式冪級数になります。だからといってただの数列の問題をFPSの問題と表現してしまうと、形式冪級数環に関わる手法を駆使する必要のある問題であると表明しているように聞こえてしまうわけです。

集合論を学ぶと$1 = \{0\}$とか$(0,0) = \{1\}$とか謎の等式が形式的に成り立ってしまうことを知るわけですが、だからといってこれらを無意味に混在させて表現すると「何をしたいのか」が全然伝わらなくなることに近いかもしれません。

厳密に定義するために固定した１つの実装でたまたま同じなだけなので、必要のない限り実装依存の等式を断りなく使うのを避けるのが数学で好まれがちというわけです。等式を書いても間違いではありません。単に意図が分かりにくくて訝しげな目で見られて何か勘違いしているのかもしれないと疑われて損をするだろうというお話です。

この辺は数学特有の感覚かもしれません。プログラミングで強いて言えばC++でchar a = 'a';をchar a = 97;と書いても別に良いけれど前者が好まれそう、みたいな？

ちなみにこの他にも指数型母関数というものもありますし、数列以外にも組み合わせ論的種という概念にも母関数が定義されます。

組み合わせ論的種もたまに怪しい説明を見ますが、高度典型の中でも話題に上がる頻度が少ない気がするので今回は割愛します。組み合わせ論的種が未履修な人はこの問題でも解いて学んでみてください。

Taylor展開

$U$を$\mathbb{R}$の開集合とし、$f$を$C^{\omega}$級関数$U \to \mathbb{R}$とし、$u \in U$とします。$C^{\omega}$級の仮定から特に$f$は$C^{\infty}$級でもあるので、数列$(f^{(d)}(u)/d!)_{d \in \mathbb{N}}$が意味を持ちます。この母関数をここでは$F$と置きましょう。

定義から$F$は形式冪級数です。$C^{\infty}$級より強く$C^{\omega}$級であることの恩恵として収束半径というものが正になります。そのような形式冪級数は収束冪級数と呼ばれます。この収束冪級数$F$を$f$の$u$におけるTalor展開と呼んだり、$F$を求める行為そのものをTaylor展開と呼んだりもします。この辺もやはり色々な流儀があります。

$F$を扱う際は$\mathbb{R}[[x]]$でなく$\mathbb{R}[[x-u]]$という書き方が好まれます。ただし$u = 0$であることが分かっている時は$\mathbb{R}[[x-u]]$より$\mathbb{R}[[x]]$が好まれます。短いと気持ちが良いですからね。

なお$\mathbb{R}$でなくても良いです。$\mathbb{C}$でも$\mathbb{Q}_p$でもTaylor展開で収束冪級数が得られます。

等比級数の和の公式

$\sum_{d=0}^{\infty} x^d = \frac{1}{1-x}$という公式がありますね。$x$に実数を代入する時は$\lvert x \rvert < 1$という条件がつきました。

よく見るとこれ、両辺とも任意の環$R$に対する$R[[x]]$の要素になってますね。そして$R[[x]]$の要素の等式として成立します。何かを代入するわけでもないので$\lvert x \rvert < 1$という条件も不要（というか$\lvert x \rvert$が定義されていないか、$x$進付値という概念を用いて$\lvert x \rvert < 1$となるように定義するものなので気にしなくて良いか）です。

というわけで形式冪級数が得られました。なお右辺を掛ける操作は$1-x$を掛ける操作の逆操作で、母関数に$1-x$を掛ける操作は数列に階差数列を取る操作ですね。ということは左辺を母関数に掛ける操作は数列に階差数列を取る操作の逆操作……つまり累積和を取る操作になります。実際に各自で計算して確かめてみてください。

二項展開

まず実数の二項定理は既知のものとしましょう。

定理（実数の二項定理）

任意の$x \in \mathbb{R}$と$n \in \mathbb{N}$に対し$(1+x)^n = \sum_{d=0}^{\infty} \binom{n}{d} x^d$である。

右辺は$d$の動く範囲が本来$n$までで良いですが、$\infty$までにしても二項係数が$d = n+1$から$0$になっていくので問題ありません。

さて、両辺は実数$x$と非負整数$n$の関数なわけですが、$n$を止めると両辺とも多項式関数になっていますね。つまりこれは多項式関数の等式なわけですが、多項式関数と多項式が別物であると強調した以上、多項式関数の等式が多項式の等式でもあるのかに触れる必要があります。

定理（多項式の二項定理）

$R$を環とし、$n$を非負整数とする。$R[x]$において等式$(1+x)^n = \sum_{d=0}^{\infty} \binom{n}{d} x^d$が成り立つ。

こちらは抽象的に環論で示せますが、せっかくなら$(x,n)$に旅をしてもらいましょう。

証明

実数の二項定理と$\mathbb{R}$係数多項式の一致の定理により、主張は$R = \mathbb{R}$の場合に成り立つ。

自然な埋め込み$\mathbb{Z}[x] \hookrightarrow \mathbb{R}[x]$は単射なので、主張が$R = \mathbb{R}$の場合に成り立つことから主張は$R = \mathbb{Z}$の場合にも成り立つ。

自然な写像$\mathbb{Z}[x] \to R[x]$は環準同型であるので、主張が$R = \mathbb{Z}$の場合に成り立つことから主張は一般にも成り立つ。$\Box$

一致の定理や単射性と準同型性の連鎖により証明の中で$(x,n)$の居場所が

\[ (\mathbb{R},\mathbb{N}) \rightsquigarrow (\mathbb{R}[x],\mathbb{N}) \rightsquigarrow (\mathbb{Z}[x],\mathbb{N}) \rightsquigarrow (R[x],\mathbb{N}) \]

と変遷していくのが面白いですね。さて、多項式環の普遍性を知っていれば即座に次が思いつきます。

系（環の二項定理）

$R$を環とし、$n$を非負整数とする。任意の$x \in R$に対し$(1+x)^n = \sum_{d=0}^{\infty} \binom{n}{d} x^d$である。

証明

不定元$y$に$x$を代入する写像$R[y] \to R$は環準同型であり、環準同型は環論の等式を保つので、多項式の二項定理から主張が成り立つ。$\Box$

今度は$(x,n)$が

\[ (R[x],\mathbb{N}) \rightsquigarrow (R,\mathbb{N}) \]

と旅をしています。次はどこに行きましょう？

定理（$p$進数の二項展開）

$p$を素数とする。任意の$x \in p \mathbb{Z}_p$と$n \in \mathbb{Z}_p$に対し、$(1+x)^n = \sum_{d=0}^{\infty} \binom{n}{d} x^d$が成り立つ。（ただし非整数乗は実数の場合と同様に整数乗の極限で定める）

証明

環の二項定理が$R = \mathbb{Z}_p$に対して成り立つので、$n \in \mathbb{N}$の時は主張が成り立つ。

両辺は$n$に関して$p$進連続であり、$\mathbb{N}$は$\mathbb{Z}_p$で稠密なので、主張は一般にも成り立つ。

今度は$(x,n)$が

\[ (R,\mathbb{N}) \rightsquigarrow (\mathbb{Z}_p,\mathbb{N}) \rightsquigarrow (\mathbb{Z}_p,\mathbb{Z}_p) \]

と旅をしましたね。さて、$p$進数の二項定理では$n$が非負整数ですらなくなったわけですが、多項式の二項定理の右辺もまた$n$が非負整数でなくても$R$と$n$の組み合わせ次第で$R$係数形式冪級数として意味を持ちますね。例えば

$n \in \mathbb{Z}$である場合
$R$が$\mathbb{Q}$代数であり、$n \in R$である場合
$p$を素数として、$R$が$\mathbb{Z}_p$代数であり、$n \in \mathbb{Z}_p$である場合

のいずれも右辺が$R$係数形式冪級数として意味を持ちます。これにて新たな形式冪級数の例が大量に得られました。

なお左辺も$n \in \mathbb{Z}$である場合に$R$係数形式冪級数として意味を持ちます。となると、両辺が意味を持つ時に等式が成り立つかどうかが気になりますね。

定理（負の二項定理）

$R$を環とする。任意の$n \in \mathbb{Z}$に対し$R[[x]]$において等式$(1+x)^n = \sum_{d=0}^{\infty} \binom{n}{d} x^d$が成り立つ。

$n=-1$の場合は等比級数の和の公式ですね。これも抽象的に環論で示せますが、やはり旅を楽しんでいきましょう。

証明

$p$を好きな素数（例えば$2$）とする。$p$進数の二項定理と$\mathbb{Z}_p$係数形式冪級数の一致の定理（Weierstrassの予備定理）より、主張は$R = \mathbb{Z}_p$の場合に成り立つ。

自然な埋め込み$\mathbb{Z}[[x]] \hookrightarrow \mathbb{Z}_p[[x]]$は単射であるので、主張が$R = \mathbb{Z}_p$の場合に成り立つことから主張は$R = \mathbb{Z}$の場合にも成り立つ。

自然な写像$\mathbb{Z}[[x]] \to R[[x]]$は環準同型であるので、主張が$R = \mathbb{Z}$の場合に成り立つことから主張は一般の場合にも成り立つ。$\Box$

実数の二項定理、多項式の二項定理、環の二項定理、$p$進数の二項定理、負の二項定理と渡っていくのに$(x,n)$は

\[ \begin{array}{cl} & (\mathbb{R},\mathbb{N}) \rightsquigarrow (\mathbb{R}[x],\mathbb{N}) \rightsquigarrow (\mathbb{Z}[x],\mathbb{N}) \rightsquigarrow (R[x],\mathbb{N}) \rightsquigarrow (R,\mathbb{N}) \\
\rightsquigarrow & (\mathbb{Z}_p,\mathbb{N}) \rightsquigarrow (1 + p \mathbb{Z}_p,\mathbb{Z}_p) \rightsquigarrow (\mathbb{Z}_p[[x]],\mathbb{Z}) \rightsquigarrow (\mathbb{Z}[[x]],\mathbb{Z}) \rightsquigarrow (R[[x]],\mathbb{Z}) \end{array} \]

と変遷しましたね。長い長い旅でした。そろそろ形式冪級数の扱いに慣れてきましたね。

exp

$R$を$\mathbb{Q}$代数とします。この時

\[ \exp(x) := \sum_{d=0}^{\infty} \frac{1}{d!} x^d \]

は$R$係数形式冪級数となります。

え？　素数$p$に対する$\mathbb{F}_p$は$\mathbb{Q}$代数ではないですよ？

$\exp$を$\mathbb{F}_p$係数形式冪級数と思い込むミスはよくあるので気をつけていきましょう。

ここで$\mathbb{F}_p$係数形式冪級数とみなせない$\mathbb{Q}$係数形式冪級数を$\mathbb{F}_p$係数多項式に落とすテクニックがあるので紹介します。ここだけの用語で、それを法$p$類似と呼ぶことにします。

定義（$\mathbb{Q}$係数形式冪級数の法$p$類似）

$p$を素数とし、$f \in \mathbb{Q}[[x]]$とする。$f$の法$p$類似を以下のように定義する。

(1) 任意の$d \in \mathbb{N}$に対し$f_d \in \mathbb{Z}_{(p)}$ならば、$f$の法$p$類似を \[ \sum_{d=0}^{\infty} (f_d + p \mathbb{Z}_{(p)}) x^d \in \mathbb{F}_p[[x]] \setminus \mathbb{F}_p[x] \] と定める。

(2) $f_d \notin \mathbb{Z}_{(p)}$を満たす$d \in \mathbb{N}$が存在するならば、その最小値$d_0$を用いて$f$の法$p$類似を \[ \sum_{d=0}^{d_0-1} (f_d + p \mathbb{Z}_{(p)}) x^d \in \mathbb{F}_p[x] \] と定める。

ただし$p \mathbb{Z}_p$による剰余類は自然な同型$\mathbb{Z}_{(p)}/(p) \cong \mathbb{F}_p$により$\mathbb{F}_p$の要素とみなします。

$\exp$の法$p$類似は(2)のパターンですね。$p-1$次の多項式です。多項式をわざわざFPSと言ってしまうと訝しげに見られるかもしれません。法$p$類似を取る前の$\mathbb{Q}$係数形式冪級数の話かな？　って。

$\mathbb{F}_p[[x]]/(x^p)$の要素とみなすこともできますが、$\mathbb{F}_p[[x]]/(x^p)$は$\mathbb{F}_p[[x]]$と別物なのでその要素を断りなくFPSというのも違和感がありそうです。

$\mathbb{C}$の定義を$\mathbb{R}[x]/(x^2+1)$で与えている文脈で複素数のことを$\mathbb{R}$係数多項式と呼ぶようなものなので、それを受け入れられる人が多いかどうかという問題ですね。

log

$R$を$\mathbb{Q}$代数とします。この時

\[ \log(1+x) := \sum_{d=1}^{\infty} \frac{(-1)^{d+1}}{d} x^d \]

は$R$係数形式冪級数となります。

え？　素数$p$に対する$\mathbb{F}_p$は$\mathbb{Q}$代数ではないですよ？

$\log$を$\mathbb{F}_p$係数形式冪級数と思い込むミスはよくあるので気をつけていきましょう。

$\log$の法$p$類似もまた(2)のパターンでやはり$p-1$次の多項式です。

$\exp$との関係については合成の章で詳しく扱いましょう。

畳み込み

多項式や形式冪級数の乗算（及びそれから母関数を取る操作を通じて定まる数列の乗算や群環の乗算や局所コンパクト位相群上の適当な可積分性を持った関数の乗算など）のことです。

非負整数$N$を固定して$x^N - 1$の生成するイデアルで割った環における乗算（及びそれから母関数を取る操作を通じて定まる数列の乗算や巡回群の群環の乗算）は巡回畳み込みと呼びます。

その他、グラフ畳み込みなど色々な用法があります。

DFT

離散フーリエ変換、すなわち可換離散群上の関数（もしくは群環の要素）に対するFourier変換のことです。

FFT

高速フーリエ変換、すなわちDFTを高速に計算するアルゴリズムのことです。

係数体として要素数がプロス素数である有限体を考えている時はNTTとも言います。

え？　形式冪級数（の乗算）じゃないですよ？

多項式（の乗算）のことでもないです。

じゃあ何なのさ、と言われてもDFTを高速に計算するアルゴリズムです。

FFTを使うことで、例えば巡回次数が$2$冪の場合の巡回畳み込みを計算することができます。

巡回次数を大きく取ることで、多項式の畳み込みも巡回畳み込みに帰着させて計算することができます。

形式冪級数を有限次で打ち切ることで、形式冪級数の畳み込みも多項式の畳み込みに帰着させて計算することができます。

FPSのことをFFTと呼ぶのは、最短経路問題のことを優先度付きキューと呼んだり最小費用流のことをポテンシャルと呼んだりするようなものです。用語を知っている人が聞いたら訝しげな顔をするでしょう。

今回はこれを覚えていってください。「FPSそのものはFFTできない」。間違っても「FPSにFFTをすると～」とか言わない。約束です。

代入

多項式への代入はもう説明しましたね。

え？　形式的冪級数への代入……？

一般の環では$0$しか代入できませんよ？　$\mathbb{Z}_p$係数なら$p \mathbb{Z}_p$の要素が代入できますが。

「FPSに（$0$でない要素）を代入すると～」とか言ってしまうと訝しげな目で見られるわけです。代入できているということはきっと多項式なんでしょうね。そりゃ多項式は形式冪級数でもあるので間違ってはいませんが、冒頭に述べた「整数をあえて実数と呼ぶ」問題がここにあるわけです。

「FPSにFFTをすると～」がおかしいのも同じ理由ですね。FFTの定義に代入（正確には指標が誘導する環準同型）が使われてますものね。

合成

多項式同士は自由に合成ができますし、関数同士も定義域と終域が条件を満たせば合成できます。

しかも多項式の合成と多項式関数の合成は整合的です。

形式冪級数同士の合成は必ずしも定義できません。それはそうでしょう、定数（$1$次以上の項が$0$の形式冪級数）も合成できるのでしたら代入ができるということですから。

一般の環では、一般の形式冪級数に定数項が$0$の形式冪級数が合成できます。

つまりどちらも定数項が$0$でもない多項式を合成する時に「FPSの合成で～」とか言っていると訝しげな目で見られるかもしれないわけです。そりゃ多項式は形式冪級数ですが。

さて、合成といえば逆関数ですね。

定理（$\exp$と$\log$の関係）

(1) 任意の$\mathbb{Q}$代数$R$に対し、$R[[x]]$における等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & := & \log(1+(\exp(x)-1)) = x \end{array} \] が成り立つ。

(2) 任意の素数$p$に対し、$\exp$と$\log$の法$p$類似をそれぞれ$e_p$と$\ell_p$と置くと、$\mathbb{F}_p[x]/(x^p)$における等式 \[ \begin{array}{rcl} e_p(\ell_p(1+x)) & = & 1 + x \\
\ell_p(e_p(x)) & := & \ell_p(1+(e_p(x)-1)) = x \end{array} \] が成り立つ。

証明

(1) 複素対数の分枝を取る。複素正則関数としての等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & = & x \end{array} \] と複素正則関数の一致の定理から、主張は$R = \mathbb{C}$の場合に成り立つ。

自然な埋め込み$\mathbb{Q}[[x]] \hookrightarrow \mathbb{C}[[x]]$は単射なので、主張が$R = \mathbb{C}$の場合に成り立つことから主張は$R = \mathbb{Q}$の場合にも成り立つ。

自然な埋め込み$\mathbb{Q}[[x]] \hookrightarrow R[[x]]$は環準同型なので、主張が$R = \mathbb{Q}$の場合に成り立つことから主張は一般の場合にも成り立つ。

(2) 自然な商$\mathbb{Q}[[x]] \twoheadrightarrow \mathbb{Q}[[x]]/(x^p) \cong \mathbb{Q}[x]/(x^p)$は環準同型なので、(1)が$R = \mathbb{Q}$の場合に成り立つことから$\mathbb{Q}[x]/(x^p)$における等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & = & x \end{array} \] が成り立つ。

自然な埋め込み$\mathbb{Z}_{(p)}[x]/(x^p) \hookrightarrow \mathbb{Q}[x]/(x^p)$は単射なので、$\mathbb{Q}[x]/(x^p)$における等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & = & x \end{array} \] が成り立つことから$\mathbb{Z}_{(p)}[x]/(x^p)$における等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & = & x \end{array} \] も成り立つ。

自然な商$\mathbb{Z}_{(p)}[x]/(x^p) \twoheadrightarrow \mathbb{Z}_{(p)}[x]/(x^p)/(p) \cong \mathbb{Z}_{(p)}[x]/(p)/(x^p) \cong \mathbb{Z}_{(p)}/(p)[x]/(x^p) \cong \mathbb{F}_p[x]/(x^p)$は単射なので、$\mathbb{Z}_{(p)}[x]/(x^p)$における等式 \[ \begin{array}{rcl} \exp(\log(1+x)) & = & 1 + x \\
\log(\exp(x)) & = & x \end{array} \] が成り立つことから$\mathbb{F}_p[x]/(x^p)$における等式 \[ \begin{array}{rcl} e_p(\ell_p(1+x)) & = & 1 + x \\
\ell_p(e_p(x)) & = & x \end{array} \] も成り立つ。

今回は$x$の旅が

\[ \mathbb{C} \rightsquigarrow \mathbb{C}[[x]] \rightsquigarrow \mathbb{Q}[[x]] \rightsquigarrow R[[x]] \]

と

\[ \begin{array}{cl} & \mathbb{Q}[[x]] \rightsquigarrow \mathbb{Q}[[x]]/(x^p) \rightsquigarrow \mathbb{Q}[x]/(x^p) \rightsquigarrow \mathbb{Z}_{(p)}[x]/(x^p) \\
\rightsquigarrow & \mathbb{Z}_{(p)}[x]/(x^p)/(p) \cong \mathbb{Z}_{(p)}[x]/(p)/(x^p) \cong \mathbb{Z}_{(p)}/(p)[x]/(x^p) \cong \mathbb{F}_p[x]/(p)/(x^p) \rightsquigarrow \mathbb{F}_p[x] \end{array} \]

となりました。楽しかったですね。

割った商

多項式の商は、割る多項式の最高次係数が可逆である場合に可能です。

可逆でない場合は必ずしも定義されない（定義される十分条件もある）のですが、たまに怪しい記述を見かけますね。

形式冪級数の商は逆に定数項が可逆である場合に可能です。

可逆でない場合でも、一般には定義されないですが例えば体係数で$x$進付値の適切な大小関係があれば可能です。

紛らわしいのは、多項式の商の計算方法の１つに形式冪級数の商を使う方法があることです。単にアルゴリズム中で使うだけで両者は別物であることに注意しましょう。

多項式の商の話なのに「FPSの商が～」とか言ってしまうと訝しげな目で見られるかもしれないということです。

割った余り

商が定義できれば、それを用いて余りも定義できます。

多項式の除算は、割る多項式の最高次係数が可逆である場合に可能です。

やはり可逆でない場合は必ずしも定義されない（定義される十分条件もある）ことに注意しましょう。

形式冪級数の除算は逆に定数項が可逆である場合に可能ですがその場合の余りは$0$なのであまり役に立ちません。

可逆でない場合でも、一般には定義されないですが例えば体係数で$x$進付値の適切な大小関係があれば可能ですがやはりその場合の余りは$0$なのであまり役に立ちません。

商とは無関係にイデアルのよる商での剰余類のことを指すなら一般の形式冪級数でも定義されますが、一般的な用語かは怪しいのできちんと断りを入れてから使ったほうが良さそうです。

Taylorシフト

Taylorシフトは多項式の平行移動（Taylor展開）またはそれを計算するアルゴリズムです。

一般の形式冪級数には基本的に定義されません（$0$平行移動させる、とかは何もしないのでもちろん定義されますが）。

アルゴリズムの中で形式冪級数（の法$p$類似）やFFTが使われるだけです。

「FPSのTaylorシフトが～」とか言ったら訝しげな目で見られるかもしれません。

多点評価

多点評価は多項式の代入を複数点で計算するアルゴリズムです。

一般の形式冪級数には代入が基本的に定義されないと述べた通り、一般の形式冪級数には多点評価が定義されません。

アルゴリズムの中でFFTが使われるだけです。もはやFPSはあまり関係ありません。

「FPSの多点評価が～」とか言ったら訝しげな目で見られるかもしれません。

評価点シフト

評価点シフトは区間での多項式の代入値のデータから別の区間での多項式の代入値を計算するアルゴリズムです。

一般の形式冪級数には代入が基本的に定義されないと述べた通り、一般の形式冪級数には多点評価が定義されません。

アルゴリズムの中で形式冪級数（の法$p$類似）やFFTが使われるだけです。

「FPSの評価点シフトが～」とか言ったら訝しげな目で見られるかもしれません。

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。（波カッコでもたまにバグる）

数式環境をくくる大括弧と数式環境内の中括弧や半角空白や濃度のシャープは半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

inline数式内の縦棒はlvertなどを使わないとmarkdownの表と認識される。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。