ニュートン法の2次収束性とヘンゼルの補題

可換環論でのニュートン法が「2次収束」することの証明をちゃんと書いておく．

可換環 の可逆元全体を で表す．可換環とそのイデアル に対し の剰余環 での像を と書く．

に対し ならば ．

証明． とすると， である．

とおくと，\begin{align}(x+I^n)(z+I^n)&=xy(1-a+a^2+\cdots a^{n-1})\\
&=(1+a)(1-a+a^2+\cdots +(-a)^{n-1})\\
&=1+ (-1)^{n-1}a^n\in 1+I^n\end{align}より が の逆元となる．証明終

表記を簡単にするために の可逆元 の逆元 を と書くことにする．これは を で考えてその像を取っているのではないことに注意（ は で可逆とは限らない）．次の定理に現れる もこの意味での逆元である．

定理
を可換環とそのイデアル， を正整数，] とする． が \begin{align}f(a)\in I^n,~f'(a)+I\in (R/I)^\times\end{align}を満たすとき，\begin{align}b\in a -\cfrac{f(a)}{f'(a)}+I^{2n}\end{align}となる を取ると であり，\begin{align}f(b)\in I^{2n},~f'(b)+I\in (R/I)^\times\end{align}が成り立つ．

証明． は の取り方より自明．

となる が存在する． より \begin{gather}
f(a)+f'(a)(b-a)\in f'(a) I^{2n}\subset I^{2n},\\
b-a\in -\cfrac{f(a)}{f'(a)} +I^{2n} \subset I^n
\end{gather}であるので， が成り立つ．

また， より であるので\begin{align}f'(b)+I=f'(a)+I\in (R/I)^\times\end{align}である．証明終

この定理はニュートン法の１ステップで， の における単根 が における根 に持ち上がるということを言っている． が に改善されており，ニュートン法は「2次収束」である．

系（ニュートン法）
を可換環とそのイデアル，] とする． が \begin{align}f(a)\in I,~f'(a)+I\in (R/I)^\times\end{align}を満たすとき， を次で定める
\begin{align}
x_0&= a, \\
x_{n+1}&\in x_n -\cfrac{f(x_n)}{f'(x_n)} + I^{2^{n+1}}.
\end{align}このとき， は一意に定まっており，\begin{align}
f(x_n) \in I^{2^n},~x_{n+1}-x_n \in I^{2^n}
\end{align}が成り立つ．

特に が収束するとき， を満たす．

系（ヘンゼルの補題）
は上の系と同様とする． が 進位相で完備のとき，\begin{align}f(b)=0,~b-a\in I\end{align}を満たす が存在する．

周期関数の1周期積分の区分求積法

高橋-森理論など，複素解析を用いて数値積分誤差を行う話があります．今回は比較的わかりやすい例として，周期関数の1周期積分の区分求積法は区間の分割数を増やすにしたがって非常に早く（指数オーダーで）収束することを紹介します．

周期関数の1周期積分

とし，領域 で正則な が実数 を周期に持つ，つまり\begin{align}
\forall z\in D, f(z+\alpha)=f(z) \end{align}が成り立っているとする．例えば，何らかの式 に対する は周期 を持つ ( が「よい」ものなら正則にもなる)．実軸上での周期1つ分の積分 \begin{align} I:=\int_0^\alpha f(x) dx \end{align}を の1周期積分と呼ぶことにする．積分区間は でなくても，長さ の区間ならばどこを取っても同じである． と変数変換すると，\begin{align}
\displaystyle I=\int_0^\alpha f(x) dx=\alpha^{-1} \int_0^1 f(\alpha t) dt
\end{align}となり，周期1の周期関数 の1周期積分の計算に帰着できる．表記を簡単にするために を改めて とおいて，周期が であるとする．

このとき，1周期積分 は区分求積法\begin{gather}
I=\lim_{N\to \infty} I_N\\
I_N:=\frac{1}{N}\sum_{k=0}^{N-1} f\left(\frac{k}{N}\right)
\end{gather}で求まりるが，この極限は指数オーダーで収束することを証明する．

証明

とおく． も周期 を持つことに注意しておく．

の特異点は高々一位の極 であり，留数は\begin{align}
\mathrm{Res}\left(g,\cfrac{k}{N}\right)=\lim_{z\to \frac{k}{N}} g(z)\left(z-\frac{k}{N}\right)=\left.\cfrac{f(z) }{(e^{2\pi i Nz}-1)'}\right|_{z=\frac{k}{N}}=\frac{1}{2\pi i N} f\left(\cfrac{k}{N}\right)
\end{align}である ( が の零点で， の除去可能特異点となる場合は留数が )．

とし，下図のように経路 を取り，反時計回りの閉じた経路 を考えると， で囲まれる領域に含まれる の特異点は なので，留数定理より \begin{align}
\int_C g(z) dz=2\pi i \sum_{k=0}^{N-1} \mathrm{Res}\left(g,\cfrac{k}{N}\right)=2\pi i \sum_{k=0}^{N-1}\frac{1}{2\pi i N} f\left(\cfrac{k}{N}\right)=I_N\end{align}が成り立つ．

周期性 より が成り立つので，\begin{align}
I_N=\int_C g(z) dz&=-\int_{C_1} g(z) dz - \int_{C_3} g(z) dz + \int_{C_2} g(z) dz + \int_{C_4} g(z) dz\\
&=- \int_{C_1} g(z) dz + \int_{C_2} g(z) dz
\end{align}となる．また，下図のように反時計回りの閉路 をとる．

は で正則なのでコーシーの積分定理より である．また，周期性 より，やはり虚軸に平行な部分の経路の積分がキャンセルして となり，\begin{align}
0=\int_{C'}f(z)dz =\int_{-h/2}^{1-h/2} f(x) dx -\int_{C_1} f(z)dz
\end{align} が成り立つ．よって\begin{align}
I=\int_0^1 f(x) dx =\int_{-h/2}^{1-h/2} f(x) dx =\int_{C_1} f(z) dz
\end{align}となる．以上より， と の差を \begin{align}
I-I_N&=\int_{C_1} f(z)+g(z) dz - \int_{C_2} g(z) dz\\
&= \int_{C_1} \left( 1+\cfrac{1}{e^{2\pi i Nz}-1}\right) f(z) dz - \int_{C_2}\cfrac{1}{e^{2\pi i Nz}-1} f(z) dz\\
&=\int_{C_1} \cfrac{e^{2\pi i Nz}}{e^{2\pi i Nz}-1} f(z) dz - \int_{C_2}\cfrac{1}{e^{2\pi i Nz}-1} f(z) dz
\end{align}と複素積分で表すことができる．

以下 を を満たすように大きく取る．このとき が成り立つ．
より， 上では \begin{align}
\left|\cfrac{e^{2\pi i N( id+t)}}{e^{2\pi i N (id+t)}-1} \right| \le \cfrac{|e^{2\pi i N( id+t)}|}{1-|e^{2\pi i N( id+t)}|} = \cfrac{e^{-2\pi dN}}{1-e^{-2\pi dN}}<2e^{-2\pi dN}
\end{align} より， 上では \begin{align}
\left|\cfrac{1}{e^{2\pi i N (-id+t)}-1} \right| \le\cfrac{1}{|e^{2\pi i N(-id+t)}|-1}=\cfrac{1}{e^{2\pi d N}-1} = \cfrac{e^{-2\pi dN}}{1-e^{-2\pi dN}}<2e^{-2\pi dN}
\end{align}よって とおくと，\begin{align}
\left|I-I_N\right| &\le \int_{C_1} \left |\cfrac{e^{2\pi i Nz}}{e^{2\pi i Nz}-1}\right| |f(z)| |dz| + \int_{C_2} \left |\cfrac{1}{e^{2\pi i Nz}-1} \right| |f(z)| |dz| \\
&<2e^{-2\pi dN}\cdot M \cdot \mathrm{length}(C_1) + 2e^{-2\pi dN}\cdot M\cdot\mathrm{length}(C_2)\\&=4Me^{-2\pi dN}
\end{align}となり，極限 は指数オーダーで収束する．

無限集合版の鳩の巣原理

羽以上の鳩を 個の巣箱に入れると，少なくとも１つの巣箱に2羽以上の鳩が入るというのが鳩の巣原理と呼ばれるものです．ほとんど当たり前と思えるものですが，これを使った面白い証明がいろいろと知られています．鳩の巣原理を使える形に問題を言い換える技法の巧妙さと，そこから鳩の巣原理一発で証明が終了してしまう気持ちよさを味わうことができます．
manabitimes.jp
この鳩の巣原理を無限集合の場合にも「集合 に対し， の濃度が の濃度より小さいとき， から への単射は存在しない」という形に一般化できますが，もう少し強く次のことが言えます．

集合 に対し， が無限集合で ( は有限集合でも無限集合でもいい) の濃度が の濃度より小さいとき，任意の写像 に対し，ある が存在して の濃度は の濃度と等しい．

が有限集合で が無限集合の場合には「無限集合を有限個に分割すると，いずれかは無限集合である」という形でお馴染みなもので，例えば「有界な実数列は収束部分列を持つ」というボルツァーノ＝ワイエルシュトラスの定理や，ディリクレのディオファントス近似定理の証明に使われます．
ja.wikipedia.org
ja.wikipedia.org

今回は が共に無限集合の場合に無限集合版の鳩の巣原理が使える問題を２つ紹介します．使うのは「濃度の大きい集合から小さい集合への単射は存在しない」という形のものです．

問題１． を高々可算な部分集合とする．このとき，任意の に対し， を通る放物線のグラフ \begin{align} y=c_2x^2+c_1x+c_0,~~c_2\neq 0, \end{align}で， とは交わらないものが存在することを示せ．

問題２． とする．次の3条件をすべて満たす を求めよ．

• は可換環の拡大，
• は単項イデアル整域，
• 自然な写像 が全単射．

問題１の解答

とおき，実数 に対し， とする．曲線 は を通る放物線のグラフである．

任意の に対し， がある の点を通ると仮定する．その点を と書くことにする． は連続無限で は高々可算なので，ある でない実数 に対し となる． とおくと，\begin{align}
\left\{\begin{array}{c} c_1(a'-a)^2+(b'-b)=0 \\ c_2(a'-a)^2+(b'-b)=0\end{array}\right.
\end{align}となる．辺々引くと より であり，よって も成り立つ．これは を意味するが， に矛盾する．

よって，ある に対し，放物線のグラフ は と交わらない．

問題２の解答

を の拡大体で， より濃度の大きい代数閉体とする( 例えば の代数閉包とすればよい)．\begin{align}C=A\otimes_{\mathbb{C}}K=K[X,Y]/(Y^2-X^3-1)\end{align}とおき， の積閉集合 を \begin{align}S=\{f(x,y)\in C\mid \forall (a,b) \in V_{\mathbb{C}}(Y^2-X^3-1), f(a,b)\neq 0\}\end{align}と定義し， とおく．ただし はそれぞれ の剰余環における像であり，体 に対し である．

は非特異アフィン代数曲線の座標環なのでデデキント整域であり， も の局所化なのでデデキント整域である．

ヒルベルトの零点定理より\begin{gather}
\mathrm{Spec}~A=\{(0)\}\cup \{\langle x-a,x-b\rangle_A \mid (a,b) \in V_{\mathbb{C}}(Y^2-X^3-1)\}\\
\mathrm{Spec}~C=\{(0)\}\cup \{\langle x-a,x-b\rangle_C \mid (a,b) \in V_{K}(Y^2-X^3-1)\}
\end{gather}である．ただし，可換環 と に対し， で が生成するイデアル を表す．

の素イデアルは または， と交わらない の素イデアルを に拡大したものだが， が と交わらない必要十分条件は であるので，\begin{gather}
\mathrm{Spec}~B=\{(0)\}\cup \{\langle x-a,x-b\rangle_B \mid (a,b) \in V_{\mathbb{C}}(Y^2-X^3-1)\}
\end{gather}である． が連続無限濃度を持つことも注意しておく．

に対し \begin{align} \langle x-a,x-b\rangle_B \cap A= \langle x-a,x-b\rangle_A \in \mathrm{Spec}~A\end{align}なので，自然な写像 が全単射であることが分かる．

あとは が単項イデアル整域であることを示せば が求める具体例であることが分かる．

に対し，離散付値環 の標準的な離散付値 ( の極大イデアルの生成元での値が となるもの) を と書く． はデデキント整域なので，任意の に対し， となる は有限個しか存在せず，さらに \begin{align}gB=\prod_{(0)\neq \mathfrak{p}\in \mathrm{Spec} ~B} \mathfrak{p}^{v_{\mathfrak{p}}(g)}\end{align}が成り立つことが知られている．

とする．

なので だが，いずれか一方は の生成元なので (中山の補題により，局所ネター環のイデアルの生成系からは極小生成系が選べる)，少なくとも と のいずれか一方は成り立つ．どちらの場合も同様なので とする． に対し，\begin{align}h_c:=c(x-a)^2+(y-b)\in B\end{align}とおく． より であり， となる．

ここで，任意の に対し， を含む とは異なる の元が存在すると仮定する．その素イデアルを と書く． は連続無限濃度で の濃度はそれよりも大きいので，ある に対し となる． とおくと， より，\begin{align}
\left\{\begin{array}{c} c_1(a'-a)^2+(b'-b)=0 \\ c_2(a'-a)^2+(b'-b)=0\end{array}\right.
\end{align}が成り立つ．よって であり， となるが，これは矛盾．

よって，ある に対し， を含む の素イデアルは のみとなる．
この に対し \begin{align} h_c B=\prod_{(0)\neq \mathfrak{q}\in \mathrm{Spec} ~B} \mathfrak{q}^{v_{\mathfrak{q}}(h_c)}=\mathfrak{p}\end{align}となり， は単項イデアルである．よって は単項イデアル整域である．