Hatena Blog Tags
はてなブログ トップ
グレブナー基底
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

グレブナー基底

(サイエンス)
【ぐれぶなーきてい】

誕生

1964年に広中平祐、1965年にB. Buchbergerによって独立に発見された。広中標準基底とも呼ばれる。B. Buchbergerは指導教授のW. Groebnerの名前を取って、グレブナー基底と名付けた。

概観

グレブナー基底を使うと、「多項式fは多項式g_{1},...,g_{n}によってf=A_{1} g_{1}+...+A_{n}g_{n}(A_{1},...,A_{n}は多項式)と多項式和に書けるか？」という問いを、一つのアルゴリズムで回答できる。

解説

上の「一つのアルゴリズム」とは、最高次数の項同士の割り算の繰り返しである。

まず、単純な場合からみてみよう。例えば、f=6x^2-x-1、g=x-1、g'=3x+1)と置きf=A gおよびf=A'g'と書けるか考えよう。この場合は、グレブナー基底の概念を持ち出す必要はなく、単に上述のアルゴリズムが答えを与える。まず、fの最高次数の元は6 x^2であり、gの最高次数の元はxである。よって、それらの割り算\frac{6x^2}{x}=6xを使い、f-6 x gとすれば、6 x^2を消せる。実際にf- 6 xg=(6x^2-x-1)- 6x g=-7x-1である。ここで余りの多項式-7x-1の最高次数の元は-7xなので、更に(f- 6x g)-\frac{-7x}{x}gとすれば、-7xも消える。実際に、(f-6xg)+7g=-7x-1+7(x+1)=6である。ここで、6の最高次数の元は6であり、6からgのどんな多項式倍を引いたとしても、余分なxの多項式倍が出てきてしまうだけで、6自体をgの多項式倍で書けない。よって、f-6xg+7g=6すなわちf=(6x-7)g+6より進まず、fはgの多項式倍で書けない。一方で、上述のアルゴリズムをfとg_{1}=(3x+1)に対して行うと、今度はぴたりとf=(2x-1)g_{1}と書ける。

次に、少し複雑な例をみてみよう。例えば、f=xy^{2}、g_{1}=x^4-xy, g_{2}=x^3 y- y-1と置き、fがf=A_{1} g_{1}+A_{2}g_{2}と書けるか考える。この場合は、上述のアルゴリズムをそのまま使ってしまうと正しい回答を得ない。実際に、y^{2}(x^{4}-x^{2}y)-xy^{2}(x^3 y-xy-1)=xy^2と書けるにも関わらず、g_{1}及びg_{2}はfの最高次数の項xy^{2}より高い次数の項x^4及びx^{3}yを含むので、上述のアルゴリズムは最初からストップする。

しかし、与えられた多項式を対応するグレブナー基底に置き換えると、再び上述のアルゴリズムを生かせる。 まず、数式プログラムのSingularを用いてg_{1}, g_{2}に対応するグレブナー基底を得よう。

> ring r=0,(x,y),lp;
// **ベースとなる環の定義。ここでは、標数が0で２変数の環で、多項式の次数の計算には、辞書式順序を採用している **
> poly g_1=x^4-x*y;
> poly g_2=(x^3)*y-y-1;
// **多項式の定義 **
> ideal I=g_1,g_2;
// **[tex:g_{1},g_{2}]による多項式和全体をIと置く **
> groebner(I);
// **[tex:g_{1},g_{2}]に対応するグレブナー基底の計算 **
_[1]=y2
_[2]=x2y
_[3]=xy
_[4]=y
_[5]=x2
_[6]=x
_[7]=1

g_{1},g_{2}をグレブナー基底G=\{y^{2},x^{2}y,xy,y,x^2,x,1\}に置き換えてみると、Gにはfの最高次数の元より小さな次数の元xyを含むので、f-\frac{x y^{2}}{xy}(xy)という操作によりf-y(xy)=0、すなわちf=y(xy)を得る。

発展

多項式が出てくる問題であれば常に役に立ので、代数幾何を初めとした純粋数学に限らず、工業、生物、統計、等々様々な場面での応用がある。上にあげたSingular以外にも国産のRisa/Asirを初め、多くのプログラムで利用できる。


*リスト：リスト::数学関連

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
toddler’s diary•8日前

JST CREST 日比チーム（編）「グレブナー道場」共立出版 2011

グレブナー基底にまつわる書籍や解説はほとんどがこの CREST メンバーによって書かれている印象です．というよりも私の持っている本がほぼその系統ということかもしれません．ただ，その路線だとほぼほぼ数学科の学生が学ぶ道筋になっていて，先が見えにくい長い道のりを一歩一歩進んでいく感じで先が見えません．まあそれがこの本のように「道場」ということなのかもしれません．全体を俯瞰した書き方をして読者を導くというようなことは数学科では邪道なのかもしれません．一方で，大数学者でも読者に寄り添った書き方をしてくださる先生もいて，そのあたりは何が違うのだろうと思うことはあります． さて，話は全く変わりますが，高校…

ネットで話題

もっと見る
1830ブックマークペットボトルを机に置いてください。出来たらあなたは合格です。 - ペットボトルを机に置いてください。出来たらあなたは合格です。（グレブナー基底大好きbot） - カクヨムkakuyomu.jp
78ブックマーク最近、妹がグレブナー基底に興味を持ち始めたのだが。（グレブナー基底大好きbot） - カクヨムkakuyomu.jp
43ブックマークペットボトルを机に置いてください。出来たらあなたは合格です。（グレブナー基底大好きbot） - カクヨムkakuyomu.jp
39ブックマーク三角関数禁止法 - 三角関数禁止法（グレブナー基底大好きbot） - カクヨムkakuyomu.jp
32ブックマーク三角関数禁止法（グレブナー基底大好きbot） - カクヨムkakuyomu.jp
26ブックマークグレブナー基底で嘘を見抜くtogetter.com
18ブックマークグレブナー基底 - Wikipediaja.wikipedia.org
13ブックマークグレブナー基底※　（２）の順序は、我々が多項式の展開で降べきの順に整理する指針と同じである。 読者のために、練習問題を置いておこう。 練習問題　　ｘｍｙｎｚｐ　（ ｍ ， ｎ ， ｐ ≧ ０　、ｍ＋ｎ＋ｐ＝５ ）　を、辞書式順序で並べよ。 （解）　項は全部で、　3Ｈ5＝7Ｃ5＝２１　個ある。 ｚ5＜ｙｚ4＜ｙ2ｚ3＜ｙ3ｚ2＜ｙ4ｚ＜...www004.upp.so-net.ne.jp
8ブックマークグレブナー基底大好きbot on Twitter: "【問題】 次のうち一番権限を持っていそうな人物を見つけなさい A.部長の田中さん B.課長の鈴木さん C.新人の須藤さん"twitter.com

関連ブログ

すゅん/Суюнのメモ帳/裏紙•4ヶ月前

【UECアドカレ2023その2】今まで読んでみて良かった本を紹介する

はじめに この記事はUEC 2 Advent Calendar 2023の23日目の記事です。 adventar.org 前日の記事はツナマヨさんの「積んでたコンテンツを消化していくよ」でした。 tunamayo1412.hatenablog.com 買ったけど未だ読めていない本は自分の本棚にもそこそこありますね…。(本当はこの記事でもちょっと紹介する予定でしたが締め切りを過ぎたのでカットしました) はじめに 自己紹介 突然ですが、読書していますか？ 学生向け LaTeX超入門 スペースキーで見た目を整えるのはやめなさい エクセル方眼紙で文書を作るのはやめなさい 分析者のためのデータ解釈学入門…

crypto-writeup-public•4ヶ月前

groebner basis

グレブナー基底

INTEGERS•5ヶ月前

あなたの推し1458次方程式は何ですか？ [PNG版]

私の推し1458次方程式はです。 解説 沢口一之が著書『古今算法記』に出題した15題の遺題の第14問は次のような問題でした。 第14問図図において、BD、AD、CD、AC、BC、ABの長さをそれぞれ とおく。以下の関係が成り立つとき、 の値を求めよ。 関孝和は著書『発微算法』において沢口一之の問題の解答を掲載していますが、実際には特定の未知数（第14問の場合は ）が満たす1変数代数方程式を求め、それをもって（本質的に）答え（たこと）にしています。 ただ、この第14問については「計算が多く, 文が繁雑になるので*1」方程式を得るための手順の概要と次数（= 1458次！）のみを記して、具体的な方程…

crypto-writeup-public•5ヶ月前

resultant

消去式のこと。なんかmagicallyに変数を減らすことができて便利。resultantの偉いところは合成数modでも使えるというところ（groebner basisがで動くのに対して）。別にグレブナー基底もで式を建ててから移せばいいんですけど n = randint(0, 2^100) Zn = Zmod(n) s, t = Zn.random_element(), Zn.random_element() u, v = s + t, s * t PR.<x, y> = PolynomialRing(Zn) f1 = x + y - u f2 = x * y - v # 理由はよくわからないけ…

crypto-writeup-public•5ヶ月前

diceCTF 2021 | benaloh

#diceCTF_2021 #good_challenges_2021 from Crypto.Random.random import randrange from Crypto.Util.number import getPrime, GCD r = 17 def keygen(): while True: p = getPrime(1024) a, b = divmod(p-1, r) if b == 0 and GCD(r, a) == 1: break while True: q = getPrime(1024) if GCD(r, q-1) == 1: break n = p*q …

INTEGERS•5ヶ月前

宮城清行すげえ

関孝和すげえという話をします。 【算聖】関 孝和【新助、自由亭】 先月、上野健爾、小川束、小林龍彦、佐藤賢一 による『関孝和全集』が岩波書店から出版されました：岩波書店のページ。 最近はこの本を勉強しているのですが、すこぶる面白いです。 私は元々「関・ベルヌーイ数」という数学的対象がものすごく好きです。これは「ベルヌーイ数」と呼ばれることの方が多いですが、ヤコブ・ベルヌーイとは独立に関孝和も発見しているという話だけをとっても、私が関孝和のことを好きになることに不思議はありません*1。なお、関・ベルヌーイ数が書かれているのは、遺著『括要算法』*2です*3。 実際は関・ベルヌーイ数の発見だけではな…

toddler’s diary•6ヶ月前

R.T.Rockafeller "Convex Analysis" Princeton University Press 1996

最適化については何冊か本を持っていますが、この本は pdf で見られるので紙の本を持っている必要はないかもしれません。SVMが流行っていたころは、凸な問題であることの優位性が異常に強調されていたイメージです。一方、今ではディープラーニングは非凸の代表格ですが、逆にほとんどの局所解が大域解と同程度の性能ということで、両極端ですがそれはそれで認められている気がします。 自分自身で非凸の問題に取り組んだのは、（制約付き）多項式の最適化で、多項式最適化という手法があることがあることを知って、しばらく自分で調べたり、年頃が近い村松さんに連絡して勉強しようと思っていましたが、どこかで少し発表しただけで立ち…

toddler’s diary•9ヶ月前

野呂正行、横山和弘「グレブナー基底の計算 基礎編 計算代数入門」東京大学出版会 2003

確か藤木さんとの研究だったと思いますが、コンピュータビジョンのある種の問題が多変数の4次方程式を解く問題に帰着されるというような研究をしたことがあります。だいぶ前に塩漬けにしてしまったので詳細は忘れましたが、その時に、それを解くヒントとして、グレブナー基底を少しだけ勉強しました。 どうして塩漬けにしてしまったのかすら忘れてしまいましたが、『単に連立方程式を与えるとグレブナー基底を求めてそこから解を出してくれる』というタイプのツールがなくてそのまま自然消滅してしまったように思います。(その後調べたところ、グレブナー基底ベースのコンピュータビジョンの研究は結構あるようです) 世の中には技術があって…

やまびこアンテナ•9ヶ月前

爆笑した！新宿紀伊国屋書店のとあるブースの話

どうも！やまびこです♪ 先日、新宿の紀伊国屋書店で見つけた面白い本のブースを見つけました！ １．紀伊国屋書店で見つけた特徴的なブース 新宿の紀伊国屋書店は、１階から８階まですべてが書店となっている大型書店です！ それぞれ、本の種類ごとにブースが分かれており、置いてある本のラインナップも非常に多くなっています。 その紀伊国屋書店で、非常に特徴的なブースを見つけました！ ２．専門書ブースで見つけた「とある本」 僕が見つけたのは、数学などの専門書が置いてあるブースです。 その一角に、数学に関する専門書が多数おいてありました。 フェルマーの最終定理、宇宙に秘められた謎、素数の音楽、四色問題、グレブナー…