2018-11-18

グレブナー基底の力技で既約性判定

数学グレブナ―基底既約多項式

今日はネットで見かけた次の問題をグレブナー基底を使って力技で解いてみます。

$(x^2+y^2-1)^3-x^2y^3\in\mathbb{R}[x,y]$ は $\mathbb{R}[x,y]$ の元として既約である。

www1.ezbbs.net

ちなみに $(x^2+y^2-1)^3-x^2y^3=0$ のグラフを描くと♡になります。

今回採用するのは因数分解の可能性を未定係数法でしらみつぶしに調べるというエレガントな解答からは程遠い方法ですが，グレブナー基底をコンピュータで計算していいなら意外とあっさり解くことができます。

イニシャル部分

多項式 $f(x,y)$ の全次数が最高な単項式を拾って来たものをイニシャル部分と呼び $\mathrm{in}(f)$ と書くことにします。

例えば\begin{align}\mathrm{in}(x^3+2xy^2+xy+x+1)=x^3+2xy^2\end{align}です(全次数が3の部分)。

多項式 $f(x,y)$ が \begin{align}f(x,y)=g(x,y)\times h(x,y)\end{align} と因数分解できたとすると，\begin{align}\mathrm{in}(f)=\mathrm{in}(g)\times \mathrm{in}(h)\end{align} が成り立ちます。

$\mathrm{in}(f)$ が既約だった場合， $\mathrm{in}(g)$ と $\mathrm{in}(h)$ のいずれかが定数になるので， $g$ と $h$ のいずれかが定数になります。よって $\mathrm{in}(f)$ が既約ならば $f(x,y)$ も既約であることが分かります。

例えば $f(x,y)=x^2+2y^2+y+2x+3$ とすると $\mathrm{in}(f)=x^2+2y^2$ は $\mathbb{R}[x,y]$ で既約なので， $f(x,y)$ も $\mathbb{R}[x,y]$ で既約であることが分かります。

$(x^2+y^2-1)^3-x^2y^3$ の既約性

未定係数法

$f(x,y)=(x^2+y^2-1)^3-x^2y^3$ とすると $\mathrm{in}(f)=(x^2+y^2)^3$ となります。これは既約でないので，この時点では $f(x,y)$ が既約かどうかわかりません。

さて，\begin{align}f(x,y)=g(x,y)\times h(x,y)\end{align}と定数でない $g(x,y),~h(x,y)\in \mathbb{R}[x,y]$ の積に因数分解できたと仮定しましょう。

$\mathrm{in}(g),~\mathrm{in}(h)$ は定数でなく，積が $\mathrm{in}(f)=(x^2+y^2)^3$ になるので，あり得る可能性は定数倍と順番を除いて\begin{align}\mathrm{in}(g) =x^2+y^2,~~~\mathrm{in}(h)=(x^2+y^2)^2\end{align}しかありません。

実際にこれらをイニシャルに持つ $g,~h$ が存在するか未定係数法で確かめてみましょう。
\begin{align}
h(x,y)&=x^2+y^2+a_1x+a_2y+a_3\\
g(x,y)&=(x^2+y^2)^2+b_1y^3+b_2xy^2+b_3x^2y+b_4x^3+b_5y^2+b_6xy+b_7x^2+b_8x+b_9y+b_{10}
\end{align}とおいて $h(x,y)\times g(x,y)-f(x,y)$ に現れる係数を全て列挙すると\begin{align}\small (*)
\begin{array}{l}
a_1+b_4, a_2+b_3, 2a_1+b_2+b_4, 2a_2+b_1+b_3+1, a_1+b_2, a_2+b_1, b_4a_1+a_3+b_7+3, \\
b_3a_1+b_4a_2+b_6, b_2a_1+b_3a_2+2a_3+b_5+b_7+6, b_1a_1+b_2a_2+b_6, b_1a_2+a_3+b_5+3, \\
b_7a_1+b_4a_3+b_8, b_6a_1+b_7a_2+b_3a_3+b_9, b_5a_1+b_6a_2+b_2a_3+b_8, b_5a_2+b_1a_3+b_9, \\
b_8a_1+b_7a_3+b_{10}-3, b_9a_1+b_8a_2+b_6a_3, b_9a_2+b_5a_3+b_{10}-3, b_{10}a_1+b_8a_3, b_{10}a_2+b_9a_3
\end{array}
\end{align}となります。つまりこれらが全て同時に $0$ となるような $a_i,~b_j\in\mathbb{R}$ が存在するなら $h(x,y)\times g(x,y)=f(x,y)$ となるような $a_i,~b_j\in\mathbb{R}$ が存在する事になって $f(x,y)$ は可約，存在しないなら既約ということになります。これを手計算で確認するのはちょっと嫌ですよね。そこで登場するのがグレブナー基底です。

グレブナー基底

グレブナー基底は，とあるいい性質を持ったイデアルの生成系です。

グレブナー基底 - Wikipedia

詳しい定義や計算方法を知っていなくても以下の事実さえおさえていれば，とりあえずは大丈夫です。グレブナー基底はコンピュータが計算してくれます。

多項式の集合 $\{p_1(x), \dots, p_n(x)\}\subset k[x_1,\dots,x_d]$ の生成するイデアルのグレブナー基底が $\{q_1(x),\dots, q_m(x)\}\subset k[x_1,\dots,x_d]$ だったとすると，方程式系 \begin{align}p_1(x)=p_2=\dots=p_n(x)=0\end{align}と方程式系 \begin{align}q_1(x)=q_2(x)=\dots=q_m(x)=0\end{align}の解の集合は一致する。

とくに $\{p_1(x), \dots, p_n(x)\}\subset k[x_1,\dots,x_d]$ の生成するイデアルのグレブナー基底が $\{1\}$ となるとき，方程式 $1=0$ には解が存在しないので，方程式系 \begin{align}p_1(x)=p_2=\dots=p_n(x)=0\end{align}の解も存在しません。

既約性の証明

というわけで， $h(x,y)\times g(x,y)-f(x,y)$ に現れる係数を全て集めた $(*)$ が同時に全て $0$ になるかは，グレブナー基底を使ってテストすることができます。 $(*)$ が生成するイデアルのグレブナー基底を計算してみましょう。

sagecell.sagemath.org

S.<a_1,a_2,a_3,b_1,b_2,b_3,b_4,b_5,b_6,b_7,b_8,b_9,b_10> = PolynomialRing(QQ, 13, order='degrevlex')
J=ideal([a_1+b_4,a_2+b_3,2*a_1+b_2+b_4,2*a_2+b_1+b_3+1,a_1+b_2,a_2+b_1,b_4*a_1+a_3+b_7+3,b_3*a_1+b_4*a_2+b_6,b_2*a_1+b_3*a_2+2*a_3+b_5+b_7+6,b_1*a_1+b_2*a_2+b_6,b_1*a_2+a_3+b_5+3,b_7*a_1+b_4*a_3+b_8,b_6*a_1+b_7*a_2+b_3*a_3+b_9,b_5*a_1+b_6*a_2+b_2*a_3+b_8,b_5*a_2+b_1*a_3+b_9,b_8*a_1+b_7*a_3+b_10-3,b_9*a_1+b_8*a_2+b_6*a_3,b_9*a_2+b_5*a_3+b_10-3,b_10*a_1+b_8*a_3,b_10*a_2+b_9*a_3,b_10*a_3+1])
Gb=J.groebner_basis()
Gb

結果は次のようになります。

[1]

出力されたグレブナー基底は $\{1\}$ です。つまり， $h(x,y)\times g(x,y)-f(x,y)$ の係数が同時に全て $0$ になるような $a_i,b_j$ はありません。よって\begin{align}f(x,y)=(x^2+y^2-1)^3-x^2y^3\end{align}は $\mathbb{R}[x,y]$ で因数分解することはできず，既約であることが分かります。

2018-10-25

離散フーリエ変換と中国剰余定理

数学中国剰余定理離散フーリエ変換

今日紹介するのは離散フーリエ変換は中国剰余定理としても理解できるというお話です。この見方をすると，合成積が離散フーリエ変換で積に化ける理由がよく分かります。

離散フーリエ変換

$N$ を正整数とし， $\zeta_N=e^{\frac{2\pi i}{N}}$ を $1$ の原始 $N$ 乗根をします。

長さ $N$ の複素数列 $\vec{a}=(a_0,\dots,a_{N-1})$ に $\vec{A}=(A_0,\dots,A_{N-1})$ \begin{align}A_p= \sum_{k=0}^{N-1} a_k \cdot \zeta_N^{-kp}\end{align}を対応させるものを離散フーリエ変換と呼び， $\mathcal{F}:\mathbb{C}^N \to \mathbb{C}^N$ で表します。

また， $\vec{A}=(A_1,\dots,A_{N-1})$ を $\vec{a}=(a_0,\dots,a_{N-1})$ \begin{align}a_p= \frac{1}{N}\sum_{k=0}^{N-1} A_k \cdot \zeta_N^{kp}\end{align}に対応させるものを逆離散フーリエ変換と呼び， $\mathcal{F}^{-1}:\mathbb{C}^N \to \mathbb{C}^N$ で表します。

$\mathcal{F}$ は線形同型写像で， $\mathcal{F}^{-1}$ が逆写像になっていることが知られています。つまり， $\vec{A}=\mathcal{F}(\vec{a})$ のとき $\vec{a}=\mathcal{F}^{-1}(\vec{A})$ が成り立ちます。

離散フーリエ変換 - Wikipedia

離散フーリエ変換はフーリエ変換の離散版として，解析的な文脈で語られるのが普通ですが，今日は代数的な視点から見てみようと思います。

多項式環での中国剰余定理

複素数体 $\mathbb{C}$ 上の1変数多項式環 $\mathbb{C}[T]$ を $f(T) \in \mathbb{C}[T]$ で生成されるイデアル $\langle f(T)\rangle$ で割った剰余環を $\cfrac{\mathbb{C}[T]}{\langle f(T)\rangle}$ で表すことにします。 $\mathbb{C}[T]$ における中国剰余定理は次の形になります。

中国剰余定理
$f(t)\in \mathbb{C}[T]$ が \begin{align}f(T)=f_0(T)\cdots f_{N-1}(T)\end{align}と因数分解できており， $f_k(T)$ はどの２つを取っても互いに素なとき，自然な全射 $\cfrac{\mathbb{C}[T]}{\langle f(T)\rangle} \to\cfrac{\mathbb{C}[T]}{\langle f_k(T)\rangle}$ をまとめた写像\begin{align}\frac{\mathbb{C}[T]}{\langle f(T)\rangle}\to
\prod_{k=0}^{N-1} \frac{\mathbb{C}[T]}{\langle f_k(T)\rangle}\end{align}は $\mathbb{C}$ -代数としての同型となる。

特に $a_0,\dots,a_{N-1} \in\mathbb{C}$ が相異なる複素数で，\begin{align}f(T)=\prod_{k=0}^{N-1} (T-a_k)\end{align}のときを考えると， $\cfrac{\mathbb{C}[T]}{\langle T-a_k\rangle} \cong \mathbb{C}$ であり， $g(T) \equiv g(a_k) \mod \langle T-a_k\rangle$ なので，この場合の中国剰余定理の同型写像は \begin{eqnarray*}\frac{\mathbb{C}[T]}{\langle \prod_{k=0}^{N-1} (T-a_k)\rangle} &\to&\mathbb{C}^N \cong \prod_{k=0}^{N-1} \frac{\mathbb{C}[T]}{\langle T-a_k\rangle}, \\[2mm]
g(T) &\mapsto& (g(a_0),~g(a_2),~\dots,~g(a_{N-1}))\end{eqnarray*}となります。

この同型により，任意の $(b_0,\dots, b_{N-1})\in \mathbb{C}^N$ に対し，次数が高々 $N-1$ の多項式 $g(T)$ で $g(a_k)=b_k~~(0\le k \le N-1)$ が成り立つものが唯一存在することが分かります。これを利用したのが最近一部ネットで話題の月の日数を与える多項式です。

togetter.com
tsujimotter.hatenablog.com

離散フーリエ変換と中国剰余定理

離散フーリエ変換の代数的解釈

$f(T)=T^N-1$ の場合を考えましょう。 $\zeta_N=e^{\frac{2\pi i}{N}}$ の逆数 $\zeta_N^{-1}$ も $1$ の原始 $N$ 乗根なので\begin{align}T^N-1=\prod_{k=0}^{N-1}(T-\zeta_N^{-k})\end{align}と因数分解できます。よって中国剰余定理より\begin{eqnarray*}\varphi:\frac{\mathbb{C}[T]}{\langle T^N-1\rangle} &\to&\mathbb{C}^N \\[2mm]
g(T) &\mapsto& (g(1),~g(\zeta_N^{-1}),~\dots,~g(\zeta_N^{-p}),\dots,~g(\zeta_N^{-(N-1)}))\end{eqnarray*}は環同型となります。

この定義域である環 $\cfrac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ は，ベクトル空間としては $1,T,T^2,\dots,T^{N-1}$ を基底とする $N$ 次元 $\mathbb{C}$ -ベクトル空間です。この基底を並べたベクトルを $\vec{T}=(1,T,T^2,\dots,T^{N-1})$ とおいて， $\vec{a}=(a_0,\dots,a_{N-1})\in \mathbb{C}^N$ を $\cfrac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ の元 \begin{align}\vec{a}\cdot \vec{T}=a_0+a_1T+a_2T^2+\dots a_{N-1}T^{N-1}\end{align}と同一視することができます ( $\cdot$ は内積)。

離散フーリエ変換の定義を思い出すと，\begin{align}\varphi(\vec{a}\cdot \vec{T})=\mathcal{F}(\vec{a})\end{align}が成り立つことが分かります。つまり， $\vec{a}\leftrightarrow \vec{a}\cdot \vec{T}$ という同一視を通し，環同型 $\varphi$ は離散フーリエ変換 $\mathcal{F}$ そのものと思うことができます。

逆離散フーリエ変換の代数的解釈

$\varphi$ は同型なので逆写像 $\varphi^{-1}$ が存在します。 $\varphi^{-1}$ がどうなるのか見てみましょう。

$\mathbb{C}^N$ の標準的な基底を $e_0,\dots,e_{N-1}$ とします。 $e_p$ は $p$ 番目の成分が $1$ でそれ以外の成分が $0$ のベクトルです。

$0\le p\le N-1$ に対し \begin{align}\varphi\left(\frac{1}{N}\sum_{k=0}^{N-1} \zeta_N^{kp} T^k\right)=e_p\end{align}となります。 $\varphi^{-1}$ は $\mathbb{C}$ -代数の準同型なので $\vec{A}=(A_1,\dots, A_{N-1})$ に対し \begin{eqnarray*}\varphi^{-1}(\vec{A})&=&\varphi^{-1}\left(\sum_{p=0}^{N-1} A_p e_p\right)=\sum_{p=0}^{N-1} A_p \varphi^{-1}(e_p) =\sum_{p=0}^{N-1}A_p\cdot\frac{1}{N}\sum_{k=0}^{N-1} \zeta_N^{kp} T^k\\
&=&\sum_{k=0}^{N-1}\left( \frac{1}{N}\sum_{\ell=0}^{N-1}A_p \zeta_N^{kp}\right)T^k=\mathcal{F}^{-1}(\vec{A})\cdot \vec{T}\end{eqnarray*}となり， $\varphi^{-1}$ は逆離散フーリエ変換と本質的に同じものであることが分かります。

合成積

さて $\varphi:\frac{\mathbb{C}[T]}{\langle T^N-1\rangle} \to\mathbb{C}^N$ は単なるベクトル空間としての同型ではなくて環同型です。 $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ と $\mathbb{C}^N$ の演算を比較すると，足し算はどちらもベクトルの足し算と同じ構造で似たようなものですが，掛け算の方はかなり違って見えます。

$\mathbb{C}^N$ は環の直積なので積の構造は単純です。 $(A_0,\dots,A_{N-1}), (B_0,\dots,B_{N-1}) \in \mathbb{C}^N$ の積は成分ごとの積と定義され\begin{align}(A_0,\dots,A_{N-1})(B_0,\dots,B_{N-1})=(A_0B_0,\dots, A_{N-1}B_{N-1})\end{align}となります。

一方で $\displaystyle f(T)=\vec{a}\cdot \vec{T}=\sum_{p=0}^{N-1} a_pT^p$ と $\displaystyle g(T)=\vec{b}\cdot \vec{T}=\sum_{q=0}^{N-1} b_qT^q$ の $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ での積は\begin{align}f(T)g(T)=\sum_{k=0}^{N-1}\left(\sum_{p+q \equiv k ~\mathrm{mod}~ N} a_pb_q\right)T^k \end{align}となります。

ここで， $\vec{b}=(b_0,b_1,\dots,b_{N-1})$ の添え字を $\mathbb{Z}/N\mathbb{Z}=\{0,1,\dots,N-1\}$ と解釈します。つまり，任意の整数 $m$ に対して $b_{p+mN}=b_p$ です (数列 $b_p$ を周期 $N$ の繰り返しになるように添え字を $\mathbb{Z}$ 全体に拡張したと解釈してもいいです)。すると，先ほどの積は \begin{align}f(T)g(T)=\sum_{k=0}^{N-1}\left(\sum_{p=0}^{N-1} a_pb_{k-p}\right)T^k \end{align}と書けます。

この係数を並べたベクトルは合成積と呼ばれます。

合成積
$\vec{a}=(a_0,\dots,a_{N-1})$ ， $\vec{b}=(b_0,\dots,b_{N-1})$ に対し， $\vec{c}=(c_0,\dots,c_{N-1})$ \begin{align}c_k=\sum_{p=0}^{N-1} a_pb_{k-p}\end{align} を $\vec{a}$ と $\vec{b}$ の合成積と呼び， $\vec{a}*\vec{b}$ と書く。

$\mathbb{C}^N$ はベクトルの和を加法，合成積を乗法とした可換環になります。一見変わった環のような感じがしますが $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ を考えていることと同じです。

中国剰余定理の同型 $\varphi$ を使うと，合成積の離散フーリエ変換がどうなるかすぐ分かります。

合成積の離散フーリエ変換\begin{align}\mathcal{F}(\vec{a}*\vec{b})=\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})\end{align}

ここで $\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})$ は直積環 $\mathbb{C}^N$ での積です (つまり成分ごとに積を取る)。以前と同じように $\vec{T}=(1,T,T^2,\dots,T^{N-1})$ で，黒点 $\cdot$ は内積の記号とします。

証明
合成積の定義より $(\vec{a}*\vec{b})\cdot\vec{T}=(\vec{a}\cdot\vec{T})(\vec{b}\cdot\vec{T})$ が $\frac{\mathbb{C}[T]}{\langle T^N-1\rangle}$ で成り立つ。 $\varphi$ は環準同型だったので， $\varphi((\vec{a}*\vec{b})\cdot\vec{T})=\varphi(\vec{a}\cdot\vec{T})\varphi(\vec{b}\cdot\vec{T})$ となる。

$\varphi(\vec{a}\cdot\vec{T})=\mathcal{F}(\vec{a})$ だったので，これは $\mathcal{F}(\vec{a}*\vec{b})=\mathcal{F}(\vec{a})\mathcal{F}(\vec{b})$ を意味している。

証明終

2018-10-20

数値的半群環のイデアルの生成元の数

数学

$k$ を体とし，正整数 $a_1,a_2\dots,a_n$ で定まる $k[t]$ の部分環 $k[t^{a_1},t^{a_2},\dots, t^{a_n}]$ ，または $k[[t]]$ の部分環 $k[[t^{a_1},t^{a_2},\dots, t^{a_n}]]$ を数値的半群と呼びます。

MathPower にも出ていた可換環論botこと龍孫江さんの今日の記事で次の定理が示されていました。

定理
$k[[t^2,t^3]]$ のあらゆるイデアルは，高々２個の要素で生成される.

blog.livedoor.jp
この「高々２個」の２は $k[[t^2,t^3]]$ の生成元 $t^2$ の指数２と関係がありそうですよね。この定理を一般化した次の定理を示すことができます。

定理
$a_1 < a_2 < \dots < a_n$ を正整数とする。
$k[t^{a_1},t^{a_2}\dots, t^{a_n}]$ と $k[[t^{a_1},t^{a_2}\dots, t^{a_n}]]$ のあらゆるイデアルは，高々 $a_1$ 個の要素で生成される.

証明
まず， $R=k[t^{a_1},t^{a_2}\dots, t^{a_n}]$ に対して示す。

$k[t^{a_1}]$ は $R$ の部分環でPID。 $R$ を含む環 $k[t]$ は階数 $a_1$ の自由 $k[t^{a_1}]$ -加群になっている。 $R$ のイデアルは $k[t]$ の部分 $k[t^{a_1}]$ -加群で，ねじれ部分がないので，階数が高々 $a_1$ の自由 $k[t^{a_1}]$ -加群になり，特に高々 $a_1$ 個の要素で生成されている。 $k[t^{a_1}]$ -加群としての生成系は当然， $R$ -加群としての生成系でもあるので， $R$ の任意のイデアルは高々 $a_1$ 個の要素で生成される。

$R=k[[t^{a_1},t^{a_2}\dots, t^{a_n}]]$ に対しても， $R$ の部分環 $k[[t^{a_1}]]$ を取って，全く同様に証明できる。
証明終

この証明は単に生成元の数がだけ $a_1$ 以下ということだけを示していて，具体的にどのような元で生成されるかは教えてくれません。可換環論botこと龍孫江さんの証明はイデアルの生成元を具体的に生成元がどのようになるのかを与える構成的な証明です。

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

数学ネタのブログです

グレブナー基底の力技で既約性判定

イニシャル部分

$(x^2+y^2-1)^3-x^2y^3$ の既約性

未定係数法

グレブナー基底

既約性の証明

離散フーリエ変換と中国剰余定理

離散フーリエ変換

多項式環での中国剰余定理

離散フーリエ変換と中国剰余定理

離散フーリエ変換の代数的解釈

逆離散フーリエ変換の代数的解釈

合成積

数値的半群環のイデアルの生成元の数