現実と数学の区別が付かない

数学ネタのブログです

無限集合版の鳩の巣原理

数学 鳩の巣原理

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

集合 X, Y に対し，Y が無限集合で (X は有限集合でも無限集合でもいい) X の濃度が Y の濃度より小さいとき，任意の写像 f:Y\to X に対し，ある x\in X が存在して f^{-1}(x) の濃度は Y の濃度と等しい．

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


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

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

問題２．A=\mathbb{C}[X,Y]/(Y^2-X^3-1) とする．次の3条件をすべて満たす B を求めよ．

問題１の解答

p=(a,b) とおき，実数 0\neq c\in \mathbb{R} に対し，h_c:= c(x-a)^2+(y-b) とする．曲線 h_c=0 は p を通る放物線のグラフである．

任意の 0\neq c\in \mathbb{R} に対し， h_c=0 がある V の点を通ると仮定する．その点を q_c \in V と書くことにする．\mathbb{R}\backslash\{0\} は連続無限で V は高々可算なので，ある 0 でない実数 c_1 \neq c_2 に対し q_{c_1}=q_{c_2} となる．q_{c_1}=(a',b') とおくと，\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}となる．辺々引くと (c_1-c_2)(a'-a)^2=0 より a'=a であり，よって b=b' も成り立つ．これは p=q_{c_1}\in V を意味するが，p\not\in V に矛盾する．

よって，ある 0\neq c\in \mathbb{R} に対し，放物線のグラフ h_c=0 は V と交わらない．

問題２の解答

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

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

ヒルベルトの零点定理より\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}である．ただし，可換環 R と f,g\in R に対し，\langle f,g\rangle_R で f,g が生成するイデアル fR+gR を表す．

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

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

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

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

\mathfrak{p}=\langle x-a, y-b\rangle_B \in \mathrm{Spec} ~B とする．

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

ここで，任意の c\in K に対し，h_c を含む \mathfrak{p} とは異なる \mathrm{Spec} ~B の元が存在すると仮定する．その素イデアルを \mathfrak{q}_c と書く．\mathrm{Spec} ~B は連続無限濃度で K の濃度はそれよりも大きいので，ある c_1\neq c_2 に対し \mathfrak{q}_{c_1}=\mathfrak{q}_{c_2} となる． \mathfrak{q}_{c_1}=\langle x-a', y-b'\rangle_B とおくと，h_{c_1},h_{c_2}\in \langle x-a', y-b'\rangle_B より，\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}が成り立つ．よって (a,b)=(a',b') であり，\mathfrak{p}=\mathfrak{q}_{c_1} となるが，これは矛盾．

よって，ある c\in K に対し，h_c を含む B の素イデアルは \mathfrak{p} のみとなる．
この c に対し \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}となり，\mathfrak{p} は単項イデアルである．よって B は単項イデアル整域である．

x²+y³ のb関数を手計算する

b関数 D加群 数学

今日は b 関数というものの定義を紹介し，さらに x^2+y^3 の b 関数を手計算で求めてみます．

x^2+y^3 は擬斉次孤立特異点多項式と呼ばれるクラスに属する多項式で，b 関数は簡単に計算できることが知られています．詳しく知りたい人は次の本の第6章などを参照してください．www.iwanami.co.jp

b 関数

微分作用素環

\mathbb{C}[\boldsymbol{x}]=\mathbb{C}[x_1,\dots,x_n] を n 変数多項式環，D_n=S\langle \partial_1,\dots,\partial_n\rangle を多項式係数微分作用素の環とします．ただし，\partial_k=\cfrac{\partial}{\partial x_k} は x_k に関する偏微分作用素です．

D_n の要素としての多項式 f は f 倍写像のことです．

D_n 内での \partial_k と x_k の積である \partial_k x_k は 「x_k 倍してから x_k で偏微分する」という作用素で，関数 \varphi に作用させると，関数の積の微分法則により\begin{align} (\partial_k x_k)(\varphi)=\cfrac{\partial}{\partial x_k}(x_k \varphi)=\varphi+x_k\cfrac{\partial \varphi}{\partial x_k}=\left(1+x_k \partial_k\right)(\varphi) \end{align} となります．つまり，\begin{align}\partial_k x_k=1+x_k \partial_k\end{align}であり，x_k と \partial_k の積は非可換で，D_n は非可換環です．

b 関数の定義

s を D_n 上の不定元として，多項式 f\in \mathbb{C}[\boldsymbol{x}] の形式的なべき f^s を考えます．D_n は f^s に形式的な微分として作用します:\begin{align} \partial_k (f^s) =s f_{x_k} f^{s-1}\end{align}ここで f_{x_k}=\partial_k(f) であり，f^{s-1}=f^s/f です．

ある微分作用素 P(s)\in D_n[s] に対し\begin{align} b(s) f^s=P(s)(f^{s+1})\end{align}となる b(s)\in \mathbb{C}[s] 全体からなる \mathbb{C}[s] のイデアルの生成元を f の b 関数と呼び，b_f(s) で表します．

b_f(s)\neq 0 であり，その根はすべて負の有理数であることが知られています． b 関数の選び方には定数倍の自由度がありますが，モニックという条件を付けると一意に定めることができます．

b_f(s) f^s=P(s)(f^{s+1}) に s=-1 を代入すると \cfrac{b_f(-1)}{f}=P(-1)(1) となり，これが成り立つには b_f(-1)=0 である必要があります．よって b_f(s) は必ず s+1 で割り切れ，\begin{align}\tilde{b}_f(s)=\cfrac{b_f(s)}{s+1}\end{align}とおいて 被約 b 関数と呼びます．

形式的随伴作用素

\displaystyle P=\sum_{\alpha =(\alpha_1,\dots,\alpha_n)\in \mathbb{Z}_{\ge 0}^n} a_{\alpha}(\boldsymbol{x}) \partial_1^{\alpha_1}\cdots\partial_n^{\alpha_n} に対し\begin{align} P^*
=\sum ({-}\partial_1)^{\alpha_1}\cdots({-}\partial_n)^{\alpha_n} a_{\alpha}(\boldsymbol{x}) \end{align}を P の形式的随伴作用素と呼びます．例えば x_1\partial_1 の形式的随伴作用素は \begin{align}(x_1\partial_1)^*=(-\partial_1) x_1=-x_1\partial_1-1\end{align}です．

任意の P,Q\in D_n に対し \begin{align}(P^*)^*=P,~(P+Q)^*=P^*+Q^*,~(PQ)^*=Q^*P^*,~1^*=1\end{align}であり，随伴を取る写像は D_n からその反対環 D_n^{\mathrm{op}} への環同型になっています．

なぜ P^* を P の随伴と呼ぶかというと，次のようなことが成り立つからです．

\mathbb{R}^n で定義された無限階微分可能な関数 \varphi:\mathbb{R}^n\to\mathbb{R} で，任意の多項式係数微分作用素 P\in D_n に対し \lim_{|\boldsymbol{x}|\to\infty} P(\varphi(\boldsymbol{x}))=0 となる関数を急減少関数と呼びます．\varphi(x)=e^{-x_1^2-x_2^2-\dots-x_n^2} や，\{\boldsymbol{x}\in \mathbb{R}^n\mid \varphi(\boldsymbol{x})\neq 0\} が有界となる無限階微分可能関数 \varphi(\boldsymbol{x}) などが急減少関数の例となります．

多項式 f(\boldsymbol{x})\in \mathbb{R}[\boldsymbol{x}] と急減少関数 \varphi(\boldsymbol{x}) に対し，\begin{align}\langle f, \varphi\rangle:=\int_{\mathbb{R}^n} f(x) \varphi(x) d\boldsymbol{x} \end{align}と書くことにします (気分としては「内積っぽいもの」です)．繰り返し部分積分を使うことで任意の P\in D_n に対して，\begin{align} \langle P(f), \varphi\rangle=\langle f, P^*(\varphi)\rangle\end{align}が成り立つことが示せます．

n=1,~P=x^r\partial_x\in D_1 の場合を見てみましょう．部分積分より\begin{align}\langle P(f), \varphi\rangle&=\int_{-\infty}^\infty x^r\partial_x(f(x)) \cdot \varphi(x) dx=\int_{-\infty}^\infty f'(x)\cdot x^r\varphi(x)dx\\
&=[f(x)x^r\varphi(x)]_{-\infty}^\infty-\int_{-\infty}^\infty f(x)\cdot \partial_x(x^r\varphi(x))dx\\
&=\int_{-\infty}^\infty f(x)\cdot (-\partial_x)(x^r\varphi(x))\\
&=\langle f, P^*(\varphi)\rangle\end{align}が確かに成り立っています．

擬斉次孤立特異点多項式 (quasi-homogeneous isolated singularity polynomials) の b 関数

擬斉次孤立特異点多項式

w=(w_1,\dots,w_n) を正整数のベクトルとし，\mathbb{C}[\boldsymbol{x}]=\mathbb{C}[x_1,\dots,x_n] の次数付けを \mathrm{deg}~ x_i =w_i で定めます．この次数付けに対して斉次な多項式を擬斉次多項式または重み付き次数多項式と呼びます．

例えば，\mathbb{C}[x,y],~\mathrm{deg}~ x=3,~\mathrm{deg}~ y=2 の場合，x^2+y^3 は次数 6 の擬斉次多項式，x^4+3x^2y^3-y^6 は次数 12 の擬斉次多項式です．

ここで \displaystyle Y=\sum_{k=1}^nw_k x_k \partial_k という微分作用素を導入します．Y(\boldsymbol{x}^\alpha)=(w\cdot \alpha)(\boldsymbol{x}^\alpha) であり， Y は単項式をその次数倍する微分作用素です．f\in \mathbb{C}[\boldsymbol{x}] を次数 d の擬斉次多項式とすると，Y(f)=df となるので \begin{align}X=\cfrac{1}{d}Y=\sum_{k=1}^n \cfrac{w_k}{d} x_k \partial_k \end{align}とおくと，\begin{align}X(f)=f \end{align}が成り立ちます．

f\in \mathbb{C}[\boldsymbol{x}] に対し，その偏微分 f_{x_k}:=\partial_k(f) で生成されるイデアル \begin{align}J_f:=\langle f_{x_1},\dots,f_{x_n}\rangle\end{align}をヤコビイデアルと呼び，剰余環 \begin{align}M(f):=\mathbb{C}[\boldsymbol{x}]/J_f\end{align}をミルナー代数と呼びます．

f を擬斉次多項式とすると，X(f)=f より f\in J_f であることが分かります．ミルナー代数 M(f) が \mathbb{C} 上有限次元のとき，f を擬斉次孤立特異点多項式と呼びます．これは超曲面 \{f=0\} の特異点が原点のみであることと同値です．

擬斉次孤立特異点多項式の b 関数

擬斉次孤立特異点多項式の b 関数は次の定理で計算できます．

\mathbb{C}[\boldsymbol{x}]=\mathbb{C}[x_1,\dots,x_n] の次数付けを \mathrm{deg}~ x_i =w_i>0 とし， f(\boldsymbol{x})\in \mathbb{C}[\boldsymbol{x}] を次数 d の擬斉次孤立特異点多項式，\displaystyle X=\sum_{k=1}^n \cfrac{w_k}{d} x_k \partial_k とする．

このとき，被約 b 関数 \tilde{b}_f(s) は X^* のミルナー代数 M(f) への作用の最小多項式である．

この定理についていくつかコメントをしておきます．まず，X の形式的随伴は\begin{align}X^*=\sum_{k=1}^n \cfrac{w_k}{d} (-\partial_k)x_k=\sum_{k=1}^n \cfrac{w_k}{d} ({-}x_k\partial_k{-}1)=-X-\cfrac{w_1+\cdots+w_n}{d} \end{align}であり，擬斉次多項式 g に対する作用は\begin{align}X^*(g)=-\cfrac{\mathrm{deg}~g+w_1+\cdots+w_n}{d} g\end{align}となります．つまり X^* は擬斉次多項式に対しては定数倍として作用します．

任意の J_f の元は f_{x_k} の単項式倍の線形和として書け，x^\alpha f_{x_k} は X^* で定数倍されるだけなので， X^*(J_f) \subset J_f が成り立つことが分かります．よって X^* は M(f) 上の線形作用素としてちゃんと定義されています．

M(f) も次数付き環で，その次数 j の成分を A_j で表すと，\mathbb{C} ベクトル空間としての直和分解 \begin{align}M(f)=\bigoplus_j A_j\end{align}が得られます．X^* は A_j 上に -\cfrac{j+w_1+\cdots+w_n}{d} 倍として作用するので， X^* の M(f) への作用の最小多項式である \tilde{b}_f は \begin{align}\tilde{b}_f(s)=\prod_{A_j\neq \{0\}} \left(s+\cfrac{j+w_1+\cdots+w_n}{d}\right)\end{align}となります．b_f(s)=(s+1)\tilde{b}_f(s) なので，この定理は b 関数が 0 でなくその根がすべて負の有理数であるという定理の，擬斉次孤立特異点多項式という特別な場合の証明にもなっています．

また，可換環論の知識があれば b_f(s) が w_1,\dots,w_n, \mathrm{deg}~f だけに依存して決まることが比較的簡単に分かります．

定理の証明の概略

b(s)\in \mathbb{C}[x] に関する条件\begin{align}\mbox{(条件★)}~~\exists P(s)\in D_n[s],~b(s)(s+1)f^s=P(s)(f^{s+1}) \end{align}を同値なものに書き換えていきます．(条件★) を満たす b(s) 全体からなるイデアルの生成元が被約 b 関数 \tilde{b}_f(s) です．

まず X(f)=f であったので， X(f^s)=sX(f)f^{s-1}=sf^s となり，X は f^{s} に s 倍として作用します．また，X(f^{s+1})=(s+1)X(f)f^s=(s+1)f^{s+1} なので，(X-1)f^{s+1}=sf^{s+1} となり，X-1 は f^{s+1} に s 倍として作用します．

よって P(s)=P_ms^m+P_{m-1}s^{m-1}+\dots+P_1s+P_0 \in D_n[s],~P_j\in D_n に対し，P(s) f^{s+1}=P(X-1)f^{s+1} が成り立ちます．ただし，

P_m (X-1)^m+P_{m-1}(X-1)^{m-1}+\dots+P_1(X-1)+P_0 \in D_n

です (D_n は非可換環なので「s に X-1 を代入する」という操作を気軽に行えないことには注意しておいてください)．よって (条件★) は\begin{align}\exists P\in D_n,~(s+1)b(s)f^s=P(f^{s+1}) \end{align}と書き換えることができます．

さて，(s+1)b(s)f^s=P(f^{s+1}) に s=-1 を代入すると 0=P(1) となるので，ある P_1,\dots,P_n\in D_n により P= P_1\partial_1+\dots+P_n\partial_n と書けます．このとき\begin{align}P(f^{s+1})=\sum_{k=1}^n P_k(\partial_k(f^{s+1}))=(s+1)\sum_{k=1}^n P_kf_{x_k}(f^s)\end{align}であり，(s+1)b(s)f^s=(s+1)\sum_{k=1}^n P_kf_{x_k}(f^s) の両辺を s+1 で割ると \begin{align}b(s)f^s=\sum_{k=1}^n P_kf_{x_k}(f^s)\end{align}となります．微分作用素 \sum_{k=1}^n P_kf_{x_k} は J_f が生成する D_n の左イデアル D_nJ_f の元で，f^s に対する s 倍は X に置き換えてよかったので，結局 (条件★) は \begin{align}\exists Q\in D_n J_f,~~b(X) (f^s)=Q (f^s)\end{align} と同値になります．実はこの条件は\begin{align}b(X)\in D_nJ_f\end{align} と同値になることが証明できます（この部分が定理の証明で一番非自明な部分ですが，可換環論の準備が必要になるので詳細は省略します*1）．さらに形式的随伴を取ることで，この条件は\begin{align}b(X^*)\in J_fD_n\end{align}と書き換えられます．形式的随伴により左イデアル D_nJ_f が右イデアル J_fD_n に変換されることに注意してください．

さて，これは \begin{align}\forall g\in \mathbb{C}[\boldsymbol{x}],~b(X^*)(g)\in J_f\end{align}と同値であることも簡単に分かります．\begin{align}b(X^*)\in J_fD_n \Rightarrow \forall g\in \mathbb{C}[\boldsymbol{x}],~ b(X^*)(g)\in J_f \end{align}は自明ですし， \Leftarrow は b(X^*) を次数の低い単項式に作用させていくことで，階数が低い部分から帰納的に J_fD_n に含まれることが分かります．

以上より (条件★) が成り立つことが，b(X^*) のミルナー代数 M(f) への作用が 0 であることと同値にであることが分かりました．

よって被約 b 関数 \tilde{b}_f は X^* の M(f) への作用の最小多項式です．

f(x,y)=x^2+y^3 の場合

\begin{align}
f(x,y)=x^2+y^3
\end{align}の場合の b 関数 b_f と，\begin{align}b_f(s)f^{s+1}=P(f^{s+1})\end{align}を満たす P\in D_2 を求めてみましょう．

偏微分は \partial_x=\cfrac{\partial}{\partial x},\partial_y=\cfrac{\partial}{\partial y} で表します．

b 関数

まずは X とその形式的随伴を求めると，\begin{gather}
X=\cfrac{1}{2}x\partial_x +\frac{1}{3}y\partial_y\\
X^*=-\cfrac{1}{2}x\partial_x -\frac{1}{3}y\partial_y -\cfrac{5}{6}
\end{gather}となります．ミルナー代数は\begin{align}
M(f)=\mathbb{C}[x,y]/\langle f_x, f_y\rangle =\mathbb{C}[x,y]/\langle x, y^2\rangle \cong \mathbb{C}\oplus \mathbb{C}y
\end{align}であり，その基底 1,y に X^* を作用させると
\begin{align}
X^*(1)=-\cfrac{5}{6},~ X^*(y)=-\frac{1}{3}y -\cfrac{5}{6}y=-\cfrac{7}{6}y
\end{align} なので， 1,y は X^* の固有ベクトルであり，その固有値はそれぞれ -\cfrac{5}{6}, -\cfrac{7}{6} となっています．

よって X^* の M(f) への作用の最小多項式は \left(s+\cfrac{5}{6}\right)\left(s+\cfrac{7}{6}\right) となり，これが被約 b 関数です．以上より \begin{align}
b_f(s)=(s+1)\left(s+\cfrac{5}{6}\right)\left(s+\cfrac{7}{6}\right)
\end{align}であることが分かりました．

微分作用素の計算

f=x^2+y^3 のときの b_f(s)f^s=P(f^{s+1}) を満たす微分作用素 P を求めます．
\begin{gather}
\tilde{b}_f(X^*)=\left\{\left(X+\cfrac{5}{6}\right)\left(X+\cfrac{7}{6}\right)\right\}^*=\left(X^*+\cfrac{7}{6}\right)\left(X^*+\cfrac{5}{6}\right)\\
=\left(-\cfrac{1}{2}x\partial_x -\frac{1}{3}y\partial_y +\cfrac{1}{3}\right)\left(-\cfrac{1}{2}x\partial_x -\frac{1}{3}y\partial_y\right)\\
=\cfrac{1}{4}x^2 \partial_x^2+\cfrac{1}{3}xy\partial_x \partial_y+\cfrac{1}{9}y^2 \partial_y^2+\cfrac{1}{12}x \partial_x\\
=\cfrac{1}{8}xf_x \partial_x^2+\cfrac{1}{6}yf_x\partial_x \partial_y+\cfrac{1}{27}f_y \partial_y^2+\cfrac{1}{24}f_x \partial_x
\end{gather}となります．この形式的随伴を取って \begin{gather}
\tilde{b}_f(X)=\left(X+\cfrac{5}{6}\right)\left(X+\cfrac{7}{6}\right)\\
=\cfrac{1}{8}\partial_x^2\cdot xf_x +\cfrac{1}{6}\partial_x \partial_y\cdot yf_x+\cfrac{1}{27} \partial_y^2\cdot f_y-\cfrac{1}{24}\partial_x\cdot f_x \\
=\cfrac{1}{8}(x\partial_x^2+2\partial_x)\cdot f_x +\cfrac{1}{6}(y\partial_x \partial_y+\partial_x)\cdot f_x+\cfrac{1}{27} \partial_y^2\cdot f_y-\cfrac{1}{24}\partial_x\cdot f_x
\end{gather}が得られますが，この式の f_x を \partial_x， f_y を \partial_y に置き換えた微分作用素を P とおく，すなわち \begin{gather}
P=\cfrac{1}{8}(x\partial_x^3+2\partial_x^2) +\cfrac{1}{6}(y\partial_x^2 \partial_y+\partial_x^2)+\cfrac{1}{27} \partial_y^3-\cfrac{1}{24}\partial_x^2\\
=\cfrac{1}{8}x\partial_x^3 + \cfrac{1}{6}y\partial_x^2 \partial_y + \cfrac{1}{27} \partial_y^3 +\cfrac{3}{8}\partial_x^2
\end{gather}とすると，P の作り方より\begin{gather}
P(f^{s+1})=(s+1)\left(X+\cfrac{5}{6}\right)\left(X+\cfrac{7}{6}\right)f^s=(s+1)\left(s+\cfrac{5}{6}\right)\left(s+\cfrac{7}{6}\right)f^s
\end{gather}が成り立ち，P が求めたい微分作用素であることが分かりました．

おまけ：Risa/Asir で計算

国産の数式処理ソフトである Risa/Asir で b 関数の計算をしてみましょう．Windows版は次のサイトからダウウンロードできます．
www.math.kobe-u.ac.jp
b 関数の計算をしてみましょう．

load("bfct")$ で b 関数を計算するためのパッケージを読み込んで，bfct(x^2+y^3) で x^2+y^3 の b 関数を計算しています．
fctr() は因数分解のための関数で，@@は直前の出力を表すものです．つまり fctr(@@) で直前の計算結果を因数分解します．
先ほど計算した結果とちゃんと一致しています．

*1:f_{x_1},\dots,f_{x_n} が正則列であることと，正則列が linear type と呼ばれる性質を持つことを利用します．

ユークリッドの互除法

整数

正整数 m,n の最大公約数（the greatest common divisor）を \mathrm{gcd}(m,n) で表します．\mathrm{gcd}(m,n) の計算方法として，ユークリッドの互除法がよく知られています．
ja.wikipedia.org

\mathrm{gcd}(m,n) に対しては，\begin{align}am+bn=\mathrm{gcd}(m,n)\end{align}となる整数 a,b が存在します（上記Wikipediaの「拡張された互除法」の項を参照）．また，m,n は共に \mathrm{gcd}(m,n) の倍数なので，\begin{align}m=k\cdot \mathrm{gcd}(m,n),~~n=\ell\cdot\mathrm{gcd}(m,n)\end{align}となる自然数 k,\ell が存在します．ユークリッドの互除法を利用して \cfrac{n}{m}=\cfrac{\ell}{k} と約分を計算することが出来ますが，一旦 \mathrm{gcd}(m,n) を計算して，それから m,n を \mathrm{gcd}(m,n) で割り算をするのは結構面倒に感じることがあります．

今回紹介するのは，ユークリッドの互除法の計算を一工夫することで上記の\begin{align}\mathrm{gcd}(m,n),a,b,k,\ell\end{align} を一度に全部に計算する方法です．

ユークリッドの互除法はイデアルの生成系の書き換え

正整数 m,n に対するユークリッドの互除法は，数列 a_i を
\begin{align}
\left\{
\begin{array}{l}
a_1=m,~ a_2=n,\\
a_{i+2}=(\mbox{$a_{i+1},~a_i$ の大きい方を小さい方で割った余り})
\end{array}
\right.
\end{align}と定義し，初めて 0 となる直前の a_i が \mathrm{gcd}(m,n) となるというものですが，この記事では次のように定義します．

正整数のペア m,n から始め，大きい方の数を「大きい方の数を，小さい方の数で割った余り」に取り換えるという操作を，片方が 0 になるまで繰り返す．

例えば 455,663 の場合は\begin{align}
455,663 \longrightarrow 455,208 \longrightarrow 39, 208 \longrightarrow 39, 13 \longrightarrow 0,13
\end{align}といった具合で，\mathrm{gcd}(455,663)=13 が求まります．

同じ数を2回書くので表記としては冗長ですが，ユークリッドの互除法を「イデアルの生成系の書き換え」と解釈するとこのように書くことが妥当に思えます．

可換環 R に対し，a_1,\dots,a_r\in R が生成するイデアルを \begin{align} \langle a_1,\dots,a_r\rangle=\{a_1x_1+\dots+a_rx_r \mid x_1,\dots,x_r \in R\}\end{align}と書くことにします．任意の a,b,q\in R に対し \begin{align}\langle a,b\rangle=\langle a, b-aq\rangle \end{align}であることが簡単に証明できます．このことから，ユークリッドの互除法の計算過程に現れる数のペアが生成する有理整数環 \mathbb{Z} のイデアルは変わらないことが分かります．先ほどの 455,663 を例に取ると\begin{align}
\langle 455,663\rangle = \langle 455,208 \rangle= \langle 39, 208 \rangle = \langle 39, 13 \rangle = \langle 13 \rangle
\end{align}となります．

これをちゃんと理解すると，ユークリッドの互除法の計算過程で正の数こだわる必要はなく，負の数を使ってもいいことが分かります．例えば
\begin{align}\langle 102,531\rangle=\langle 102,21\rangle=\langle -3,21\rangle=\langle 3\rangle\end{align}より \mathrm{gcd}(102,531)=3 というように計算できます．

また，\mathrm{gcd}(m,n)\in\langle m,n\rangle なので am+bn=\mathrm{gcd}(m,n) となる整数 a,b が存在することも自然に分かります．

アルゴリズム

\mathrm{gcd}(m,n) と
\begin{gather}am+bn=\mathrm{gcd}(m,n)\\
m=k\cdot \mathrm{gcd}(m,n),~~n=\ell\cdot\mathrm{gcd}(m,n)
\end{gather}を満たす a,b,k,\ell を一度に全て計算する方法を紹介しましょう．

方法自体は単純で \left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right] という行列を用意して，第１列だけ見るとユークリッドの互除法になるように行基本変形していくだけです．

まず具体例を見てみます．455 と 663 の場合，

\left[ \begin{array}{c:cc} 455 & 1 & 0\\ 663 & 0 & 1 \end{array} \right] \xrightarrow{\mbox{第2行から第1行の1倍を引く}} \left[ \begin{array}{c:cc} 445 & 1 & 0\\ 208 & -1 & 1 \end{array} \right]

\hspace{36mm} \xrightarrow{\mbox{第1行から第2行の2倍を引く}} \left[ \begin{array}{c:cc} 39 & 3 & -2\\ 208 & -1 & 1 \end{array} \right]

\hspace{36mm} \xrightarrow{\mbox{第2行から第1行の5倍を引く}} \left[ \begin{array}{c:cc} 39 & 3 & -2\\ 13 & -16 & 11 \end{array} \right]

\hspace{36mm} \xrightarrow{\mbox{第1行から第2行の3倍を引く}} \left[ \begin{array}{c:cc} 0 & 51 & -35\\ 13 & -16 & 11 \end{array} \right]
この計算結果から，455 と 663 の最大公約数は 13 で，

\left[ \begin{array}{cc} 51 & - 35 \\ {-}16 & 11 \end{array} \right] \left[ \begin{array}{c} 455\\ 663 \end{array} \right] = \left[ \begin{array}{c} 0\\ 13 \end{array} \right]

であることが分かります (ガウスの消去法で逆行列を計算する方法と同じ考え方です)．行列の第2行目 \left[-16,11\right] から
\begin{align}
(-16)\cdot 455+11\cdot 663=13
\end{align}であることが分かり，行列の第1列目 \left[51,-35\right] から，455, 663 がそれぞれ最大公約数 13 の何倍であるかの情報
\begin{align}
455=13\times35,~~ 663=13\times 51
\end{align}が得られます．

定理の形にまとめておきます．

m,n を正整数とする． \left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right] を，第1列だけ見るとユークリッドの互除法になるように行基本変形をすると，

\left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right] または \left[ \begin{array}{c:cc} 0 & c & d\\ g & a & b \end{array} \right]

という形の行列になる(g>0,a,b,c,d は整数)．このとき m と n の最大公約数は g であり \begin{gather}
a m+b n=g\\
m=|d| \cdot g,~~ n=|c|\cdot g
\end{gather}が成り立つ．

一応証明しておきましょう．

\mathrm{gcd}(m,n)=g であることはユークリッドの互除法で最大公約数が求まることから分かります．第1列だけ見るとユークリッドの互除法になるように行基本変形をしていくということは，左から \left[ \begin{array}{cc} 1 & -q\\ 0 & 1 \end{array} \right] または \left[ \begin{array}{cc} 1 & 0\\ {-}q & 1 \end{array} \right] という形の基本行列 (ただし q は正整数) を掛けていくということです．いずれの場合も同様なので，最終的に \left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right] となる場合だけを考えます．第2，3列からなる2次正方行列 \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right] は，初期状態が単位行列で，それに変形過程の行基本変形に対応する基本行列が左からかけられていったものなので，それらの基本行列の積になっています．
つまり， \left[ \begin{array}{c:cc} m & 1 & 0\\ n & 0 & 1 \end{array} \right] に左から \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right] を掛けると \left[ \begin{array}{c:cc} g & a & b\\ 0 & c & d \end{array} \right] となるということです．

特に \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right] \left[ \begin{array}{c} m\\ n \end{array} \right] = \left[ \begin{array}{c} g\\ 0 \end{array} \right] が成り立ちます．よって am+bn=g です．

また，cm+dn=0 が成り立っていますが，これは (c,d) が syzygy加群\begin{align}
\mathrm{Syz}(m,n):=\{(r_1,r_2)\in \mathbb{Z}^2\mid r_1m+r_2n=0\}
\end{align}の元であることを示しています．syzygy加群 \mathrm{Syz}(m,n) は \left(\frac{n}{g},-\frac{m}{g}\right) で生成されます．このことから，\mathrm{Syz}(m,n) の元 (r_1,r_2) で \mathrm{gcd}(|r_1|,|r_2|)=1 を満たすものは \mathrm{Syz}(m,n) の生成元である \pm \left(\frac{n}{g},-\frac{m}{g}\right) しかないことが分かります．

一方で \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right] は行列式が 1 である行列の積なので，この行列自身の行列式も 1 です．よって \begin{align} \mathrm{det} \left[ \begin{array}{cc} a & b\\ c & d \end{array} \right]=ad-bc=1 \end{align} となります．これは \mathrm{gcd}(|c|,|d|)=1 であることを示しています．よって (c,d) は \mathrm{Syz}(m,n) の生成元であり，|c|=\frac{n}{g}, |d|=\frac{m}{g} が成り立ちます．つまり m=|d| \cdot g,~~ n=|c|\cdot g となります．

応用

約分

第184回 数学検定 1級 1次：計算技能検定で出題された問題を解いてみましょう．
http://amateurmath.web.fc2.com/files/184-1-1.pdf

次の分数は約分できますか。できるならば、約分してもっとも簡単な分数で表し、できないならば「約分できない」と答えなさい。
\begin{align}\frac{10033}{12877}\end{align}

行基本変形
\left[ \begin{array}{c:cc} 10033 & 1 & 0\\ 12877 & 0 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 10033 & 1 & 0\\ 2844 & -1 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 1501 & 4 & -3\\ 2844 & -1 & 1 \end{array} \right]

\to \left[ \begin{array}{c:cc} 1501 & 4 & -3\\ 1343 & -5 & 4 \end{array} \right] \to \left[ \begin{array}{c:cc} 158 & 9 & -7\\ 1343 & -5 & 4 \end{array} \right] \to \left[ \begin{array}{c:cc} 158 & 9 & -7\\ 79 & -77 & 60 \end{array} \right]

\to \left[ \begin{array}{c:cc} 0 & 163 & -127\\ 79 & -77 & 60 \end{array} \right] より， \begin{align}\frac{10033}{12877}=\frac{127}{163} \end{align}

合同式での乗法逆元

第372回 数学検定 1級 1次：計算技能検定で出題された問題を解いてみましょう．
http://amateurmath.web.fc2.com/files/372-1-1.pdf

次の合同方程式の解のうち、0 \le x < 79 を満たす整数 x を求めなさい。\begin{align}
65x \equiv 3 ~(\mathrm{mod} ~79)\end{align}

行基本変形
\left[ \begin{array}{c:cc} 65 & 1 & 0\\ 79 & 0 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} 65 & 1 & 0\\ 14 & -1 & 1 \end{array} \right] \to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ 14 & -1 & 1 \end{array} \right]

\to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ {-}1 & 17 & -14 \end{array} \right] \to \left[ \begin{array}{c:cc} {-}5 & 6 & -5\\ 1 & -17 & 14 \end{array} \right]
より (-17)\cdot 65 \equiv 1 ~(\mathrm{mod} ~79) ．\begin{align}
65x &\equiv 3 ~&(\mathrm{mod} ~79)\\
(-17)\cdot65x &\equiv (-17)\cdot3 ~&(\mathrm{mod} ~79)\\
x &\equiv -51 ~&(\mathrm{mod} ~79)\\
x &\equiv 28 ~&(\mathrm{mod} ~79)
\end{align}なので，条件を満たすものは x=28.