週刊 代数的実数を作る
このページについて
これは、筆者 (@mod_poppo) が代数的実数をプログラミング言語上で実装する過程を、一連の記事として連載するものである。#16 までは「週刊」ということで定期的な連載を目指していたが、それ以降は不定期連載となる。
書籍化
2018年10月8日の「技術書典5」にこの連載を書籍化したものを出しました（加筆訂正あり）。詳しくは 技術書典5に代数的数を作る本を出します を参照してください。
BOOTHでPDF版を購入・ダウンロードできます（1000円）。詳しくは以下のリンク先を参照：
「代数的数を作る 多項式の根と因数分解のアルゴリズム」
目次
- #0 イントロダクション (2017年10月14日) 計算可能実数
- #1 一変数多項式環 (2017年10月14日) 一変数多項式環, ホーナー法, ユークリッドの互除法, 係数膨張
- #2 実根の数え上げ (2017年10月21日) スツルムの定理, 根の限界
- #3 代数的数の演算と終結式 (2017年10月28日) 終結式, シルベスター行列
- #4 擬除算と多項式剰余列 (2017年11月5日) 擬除算, 多項式剰余列, 部分終結式
- #5 区間演算と計算可能実数 (2017年11月18日) 区間演算, 浮動小数点数, IEEE754, 計算可能実数
- #6 代数的数の演算 まとめ (2017年11月25日) 判別式, 根の分離
- #7 整数係数 (2017年12月10日) 可換環, 整域
- #8 多項式の因数分解 その1 Kronecker の方法と無平方分解 (2017年12月16日) Kronecker の方法, 多項式補間, 無平方分解
- #9 有限体 (2017年12月23日) 体, 有限体, フェルマーの小定理
- #10 多項式の因数分解 その2 Cantor-Zassenhaus の方法 (2018年1月8日)
- #11 多項式の因数分解 その3 Berlekamp の方法 (2018年1月13日)
- #12 多項式の因数分解 その4 整数係数の因数分解 (2018年1月22日) 係数の上限, 最小多項式
- #13 多項式の因数分解 その5 Hensel の補題 (2018年1月28日) Hensel lifting, p 進数
- #14 代数的実数を係数とする代数方程式 (2018年2月4日) 多変数多項式, 実閉体
- #15 虚根の数え上げ、そして代数閉体へ（前編） (2018年2月18日) 一般 Sturm 列, Routh-Hurwitz の定理, Cauchy 指数, 偏角の原理
- #16 虚根の数え上げ、そして代数閉体へ（後編） (2018年2月28日) また会う日まで
筆者のブログ内の関連記事：
- 「週刊 代数的実数を作る」創刊 (2017年10月17日)
- 「週刊 代数的実数を作る」中間報告 (2017年12月14日)
- 「週刊 代数的実数を作る」を終えて (2018年3月16日)
- 技術書典5に代数的数を作る本を出します (2018年9月12日)
この連載を気に入ってくれた方へ
以前は CoinHive を設置していたが、 CoinHive のサービス終了ということで、撤去した。この連載を気に入ってくれた方は、BOOTHでPDF版を購入していただけるとありがたい。
参考文献
参考文献は#0の最後の方にも一応書いた。こちらのリストは、#0の後に知ったものも含め、徐々に拡充していくつもりである。
- Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Third Edition, Cambridge University Press, 2013
- 計算機代数に関する事項の多くをカバーしている。一応、邦訳もある。
- Donald E. Knuth 著「The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition 日本語版」アスキードワンゴ、2015年
- 多項式に関する基本的なアルゴリズムや、多項式の因数分解について載っている。
- 穴井宏和、横山和宏 著「QEの計算アルゴリズムとその応用 数式処理による最適化」東京大学出版会、2011年
- この連載の#2に関わる内容を扱っている。
- 吉永正彦 著「周期と実数の0-認識問題 Kontsevich-Zagier の予想」数学書房、2016年
- この連載の#0に関わる内容を扱っている。
- 雪江明彦 著「代数学1 群論入門」日本評論社、2010年
- 代数学の教科書としてオススメである。
- 雪江明彦 著「代数学2 環と体とガロア理論」日本評論社、2010年
- 同上。
- 高木貞治 著「代数学講義 改訂新版」共立出版、1965年
- 現代的な代数学の教科書とは違った
趣 があり、実数や複素数を係数とする多項式を主に扱っている。この連載で取り上げた内容と被るトピックとしては、スツルムの定理や根の限界について詳しい。
- 現代的な代数学の教科書とは違った
その他オンラインの資料・読み物
プログラミングと計算機代数（特に代数的実数）、という方向性で筆者のアンテナに引っかかったものをいくつか挙げる。この連載を読んだ方ならきっと興味を持たれる（もしくは既に知っている）だろう。
- 酒井政裕, (Haskellによる)代数的実数とCADの実装紹介, 2013年5月4日
- 2013年にあった「Haskellで計算機代数勉強会」という勉強会でのスライド。
- Haskellで代数的実数を実装するという話。趣旨がこの連載とモロ被りである。
- というわけで、この連載では、この2013年のスライドに書かれているようなものよりも洗練されたものを目指さなければならない。
- Sano Taketo, Swiftで代数学入門, 2016年3月
- Swiftで有理数体の代数拡大 \mathbf{Q}(\sqrt{2}) を実装してみた、的な話。
- 具体的なプログラミング言語で実装しつつ解説するという趣旨は、この連載と近いものがある。
- ちなみに、Swiftには標準の多倍長整数型はないみたいなので、この連載で使う実装言語の候補には入らなかった。
- グレブナー基底大好きbot, 最近、妹がグレブナー基底に興味を持ち始めたのだが。 - カクヨム, 2016年3月〜
- 計算機代数と言えばグレブナー基底、である。
- 「第1章 グレブナー基底と妹」で、代数的数の和の最小多項式をグレブナー基底を使って計算するような話がある（一方、「週刊 代数的実数を作る」ではグレブナー基底ではなく終結式を使う）。
- 書籍版の「第\sqrt{2}章 妹、分離スル。」ではスツルム列による実根の分離を扱っている。
- グレブナー基底大好きbot, Pythonで学ぶ「プログラミング可換環論」, 2017年10月〜
- Pythonを使って可換環論をやるらしい。要注目。
- peng225, 5次方程式の解を巡る旅 〜多項式の既約性判定編〜 - ペンギンは空を飛ぶ, 2018年1月9日
- 多項式の既約性判定についてまとめられている。流れとしてはこの連載でも扱う「多項式の因数分解」と近い。
- 野呂 正行, 計算機代数入門, 2005年2月26日, PDFファイル