Gröbnerův základ

Gröbnerova báze je množina , která generuje ideál daného polynomického kruhu , který má speciální vlastnosti.

Definice

Pro pole a proměnné dojížďky budiž uvedeno : nějaký ideál polynomického okruhu dojížděcích proměnných a nějaký úplný řád " " na monočlenech , kde , tzn. pro . V tomto případě musí objednávka navíc splňovat dvě podmínky: $F$ $(x_{1},\ldots ,x_{n})$ $já$ $F[x_{1},\ldots ,x_{n}]$ $(x_{1},\ldots ,x_{n})$ $\prec$ $x^{a}=x_{1}^{a_{1}}\cdot \ldots \cdot x_{n}^{a_{n}}$ $a=(a_{1},\ldots ,a_{n})\geq 0$ $a_{j}\geq 0$ $j=1,\ldots ,n$ $\prec$

multiplikativnost :implikuje pro; $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
minimalita jednotky : pro, tzn. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

Člen se nazývá vedoucí (" vedoucí ") člen (s ohledem na uspořádání ) polynomu if for all . ${\displaystyle l_{\prec }(p)=\varphi _{l}\cdot x^{l))$ $\prec$ $p=\sum _{a\in A(p)}\varphi _{a}\cdot x^{a}\in F[x_{1},\ldots ,x_{n}]$ ${\displaystyle x^{a}\prec x^{l))$ ${\displaystyle a\in A(p)\setminus \{l\))$

Gröbnerův základ ideálu kruhu je konečná množina polynomů z , která generuje ideál a má následující vlastnost: pro jakýkoli polynom existuje polynom takový, který je dělitelný . $já$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $já$ $p\in I$ $g\in G$ $l_{\prec }(p)$ $l_{\prec }(g)$

Typy Gröbnerových bází

Gröbnerův minimální základ

Minimální Gröbnerova báze polynomického ideálu I je jeho Gröbnerova báze G taková, že:

Koeficient na nejvyšším monomiálu každého je roven jedné. $p\in G$
Nejvyšší jednočlen každého z nich není dělitelný žádným nejvyšším jednočlenem ostatních prvků základu. $p\in G$

Redukovaný Gröbnerův základ

Redukovaná Gröbnerova báze polynomického ideálu I je jeho Gröbnerova báze G , taková, že:

Koeficient na nejvyšším monomiálu každého je roven jedné. $p\in G$
Žádný z monočlenů není dělitelný žádným z nejvyšších monočlenů ostatních prvků základu. $p\in G$

Pro redukovaný Gröbnerův základ ideálu platí následující tvrzení:

Nechť jsem polynomický ideál a je dáno nějaké monomiální uspořádání. Pak existuje unikátní redukovaný Gröbnerův základ ideálního I .

Konstrukční algoritmy

Za úplně první algoritmus pro konstrukci redukované Gröbnerovy báze ideálu je považován Buchbergerův algoritmus . Zajímavé je, že známá Gaussova metoda pro řešení soustav lineárních rovnic je speciálním případem Buchbergerova algoritmu.

Francouzský matematik Jean-Charles Foger navíc navrhl algoritmy F4 a F5 pro nalezení Gröbnerovy báze.

Aplikace

Gröbnerův základ je základní koncept v počítačové algebře , algebraické geometrii a výpočetní komutativní algebře .

Historie

matematik Wolfgang Gröbner bází pro volný komutativní případ na počátku 30. let a publikoval ji v roce 1950 [1] , kde napsal:

Tuto metodu jsem začal používat před 17 lety pro různé příklady, některé velmi složité.

Původní text (německy)[ zobrazitskrýt] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

V roce 1964 vyvinul podobný koncept pro místní kroužky Heisuke Hironaka , který v roce 1970 vyhrál Fieldsovu cenu . Zavedené soustavy polynomů nazval standardním základem .

Koncept Gröbnerovy báze zavedl v roce 1965 rakouský matematik Bruno Buchberger , bývalý Gröbnerův žák. Buchberger navrhl konstruktivní postup pro konstrukci Gröbnerovy báze v podobě efektivního počítačového algoritmu, který později vešel ve jako Buchbergerův

Existence standardní báze pro ideál je založena na „kompozičním lemmatu“, které pro nejsložitější ze známých případů (volné Lieovy algebry ) poprvé dokázal AI Shirshov [2] . Navíc správnost podobného tvrzení pro volné asociativní a komutativní případy byla považována za zřejmou a nevzbudila velkou pozornost až do pozdějších prací L. A. Bokuta o teorii vnoření asociativních kroužků do kroužků a kroužků s danými vlastnostmi. V roce 1972 publikoval L. A. Bokut „Shirshovovo kompoziční lemma“ pro volný asociativní případ v poznámkách kurzu o asociativních algebrách na Novosibirské univerzitě. Odtud a z ústní komunikace se dostala do povědomí amerického algebraisty J. Bergmana, který ji publikoval v roce 1979 pod názvem „Diamantové lemma“ („Diamantové lemma“). V práci nebyl žádný přísný důkaz a bylo naznačeno pouze mnemotechnické schéma „fúze“, které je nezbytné pro pochopení Shirshovovy myšlenky kompozice. Po Bergmanově publikaci se „diamantové lemma“ stalo oblíbeným mezi algebraisty a geometry a upozornilo také na Buchbergerův „Gröbnerův základ“. V polovině 80. let 20. století zkonstruoval moskevský algebraista A. A. Michalev standardní základ pro superalgebry a barevné Lieovy algebry.

Poznámky

↑ W. Gröbner. Über die Eliminationstheorie // Monatshefte für Mathematik : deník. - 1950. - Sv. 54 . - str. 71-78 .
↑ SMJ, 1962, roč. 3, č. 2, s. 292-296.

Literatura

Arzhantsev IV Gröbner základy a systémy algebraických rovnic . - M. : MTSNMO , 2003. - 68 s. — ISBN 5-94057-095-X .
Buchberger B. a další. Počítačová algebra: Symbolické a algebraické výpočty. — M .: Mir, 1986. — 392 s.
Cox D., Little J., O'Shea D. Ideály, variety a algoritmy. Úvod do výpočetních aspektů algebraické geometrie a komutativní algebry. — M .: Mir, 2000. — 687 s. - ISBN 5-03-003320-3 .
Pankratiev EV Úvod do počítačové algebry . — Intuice. — ISBN 978-5-9556-0099-4 .

Odkazy

Čurkin V. A. Systémy polynomických rovnic, ideály a jejich báze dělitele .
Bernd Sturmfels . Co je Gröbnerův základ?