Murtyの既約判定法
jurupapaさんのブログで面白そうなシリーズが始まりました。可解な代数方程式を冪根で解く計算を数式処理システムMaxima上で行うというものです。
maxima.hatenablog.jp
ガロワ理論が生まれた経緯を考えると，究極と言ってもいいくらいのテーマだと思います（5次方程式に解の公式が存在しないことや，角の三等分の作図不可能性などの「解けない方程式」とは逆方向である，「解ける方程式」に対する完全な解答といえるでしょう)。このテーマは，退職後は素人数学者さん→井汲 景太さん→jurupapaさんという流れで広がってきたようです。何かこういう感じ，いいですよね。
jurupapaさんのブログでは を例として話をすすめるそうです。ということはこの多項式は
で既約な多項式なのでしょう。Maxima 等の気の利いた数式処理システムには多項式の
の範囲での因数分解アルゴリズムが実装されているので，多項式の既約性はコマンド一つで確かめることができます。
本日の問題
今日はこの多項式 を拝借して，整数係数多項式の既約性を手計算で示す方法の話をしましょう。最終目標は次を手計算で示すことです。
この多項式は原始的（係数の最大公約数が ）なので，ガウスの補題より
の元としての既約性と
の元としての既約性は同値です。
整数係数多項式の既約判定法としては，Eisenstein の既約判定法が有名だと思いますが，この問題には適用できません。
数式処理システムの内部では整数係数多項式の因数分解には，Henselの補題を用いたアルゴリズムが使われているようですが，手計算には向かない方法です。
横山和弘，竹島卓，Euclid 環上の因数分解およびGCDについてー格子算法の 応用(pdf file)
今日紹介するのは Murtyの既約判定法というものです。おもしろさの割にはあまり知られていないように思います。
Murtyの既約判定法
Murtyの既約判定法
を
次の多項式，\begin{align}H=\max_{0\le i \le d-1} |a_i/a_d|\end{align} とする。
となる整数
に対し
が素数となるとき，
は
の元として既約である。
証明は元論文を見てください。定理の証明はちょうど1ページしかありませんし，英語も平易なので簡単に読めると思います。
M. Ram Murty, Prime Numbers and Irreducible Polynomials (pdf file)
が素数になるというのは随分と特殊な場合に思えるかもしれませんが，ブニャコフスキー予想が正しいとすれば，それほどまれな事ではありません。
egory-cat.hatenablog.com
Murtyの既約判定法を使って が既約であることを示してみましょう。この場合は
です。
で
が素数になる最小の
は
で，
という5桁の素数になります。
が素数であることを手計算で確かめるのはちょっと大変ですね。素数表で確かめてみましょう。
www.usamimi.info
は素数表に現れているので，確かに素数です。
よってMurtyの既約判定法により，既約であることが確かめられました。
Murtyの既約判定法の一般化
素数表は計算機を使って作っているわけで，この方法では純粋に手計算で既約性を証明できたとは言いにくいところがあります。
素数表を使わずに の既約性が判定できるように，Murtyの既約判定法を一般化します。
Murtyの既約判定法の一般化
を
である整数係数多項式とする。\begin{align}r=\min\{k\in \mathbb{N} ~:~ |a_d|k^d > |a_{d-1}|k^{d-1}+\cdots+|a_1|k+|a_0|\}\end{align}とおく。
を整数，
の最大の素因子を
とし，
とする。
が成り立っているならば，
は
の元として既約である。
を荒く上から
と評価し，さらに
となる場合が普通のMurtyの既約判定法になります。
証明
とおく。
かつ
なので
は少なくとも一つの正の実根を持つ。また，デカルトの符号法則により，
の正の実根は高々一つであることが分かる。よって
はちょうど一つの正の実根を持つ。
は
を満たす正の数なので，
は
の唯一の実根よりも大きい。よって，
となる任意の実数に対し，
となる。この対偶を考えると，
となる実数
は
を満たすことが分かる。
これにより， は
の任意の複素根の絶対値よりも大きいことが分かる。実際，
を満たす
をとると，\begin{align} 0=|f(\alpha)|\ge |a_d|\cdot|\alpha|^d-(|a_{d-1}|\cdot |\alpha|^{d-1}+\cdots+|a_1|\cdot|\alpha|+|a_0|)=g(|\alpha|)\end{align} となるので
である。
さて， が既約であることを背理法で示そう。
と正の次数を持つ多項式
の積に因数分解されたと仮定する。
なので，
の素因子である
は
のいずれかを割り切る。どちらも同様なので
は
を割り切るとする。すると，
が成り立つ。
が
の範囲で
と因数分解されたとする (ただし
は
の次数)。
は
の先頭係数なので
であることに注意すると，
\begin{eqnarray*}
\left|\ell \right| &\ge& |g(n)| = |c| \prod_{i=1}^{d'} |n-\alpha_i| \ge \prod_{i=1}^{d'} (n-|\alpha_i|) \\
&>& \prod_{i=1}^{d'} (n-r) \ge\prod_{i=1}^{d'} (r+|\ell|-r) =|\ell|^{d'}\ge |\ell|.
\end{eqnarray*}
が得られたことになり，これは矛盾である。よって
は既約である。
証明終
