Gröbner alapon

A Gröbner-bázis egy olyan halmaz , amely egy adott polinomgyűrű ideálját generálja , amely speciális tulajdonságokkal rendelkezik.

Definíció

Adjuk meg a mező- és ingázóváltozókra a következőket: az ingázó változók polinomgyűrűjének valamilyen ideálja és a monomokon egy teljes „ ” sorrend , ahol , azaz. számára . Ebben az esetben a megrendelésnek még két feltételnek kell megfelelnie: $F$ $(x_{1},\ldots ,x_{n})$ $én$ $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$

multiplicativitás :azt jelenti , hogy; $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
mértékegység minimálissága : for, i.e. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

Egy tagot a polinom vezető (" vezető ") tagjának nevezünk (a sorrend szempontjából ), ha mindenre vonatkozik . ${\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))$ $a\in A(p)\setminus \{l\}$

Egy gyűrűideál Gröbner - bázisa a -ból származó véges polinomok halmaza , amely ideált generál, és a következő tulajdonsággal rendelkezik: bármely polinomhoz létezik olyan polinom , amely osztható -vel . $én$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $én$ $p\in I$ $g\in G$ $l_{\prec }(p)$ $l_{\prec }(g)$

A Gröbner-bázisok típusai

A Gröbner-minimálbázis

Egy I polinomideál minimális Gröbner -bázisa a G Gröbner-bázis , amelyre:

Az együttható mindegyik legmagasabb monomijánál eggyel egyenlő. $p\in G$
Mindegyik legmagasabb monomiája nem osztható az alap többi elemének egyik legmagasabb monomijával. $p\in G$

Csökkentett Gröbner bázis

Egy I polinomiális ideál redukált Gröbner -bázisa a G Gröbner -bázisa , úgy, hogy:

Az együttható mindegyik legmagasabb monomijánál eggyel egyenlő. $p\in G$
A monomok egyike sem osztható a bázis többi elemének legmagasabb monomijával. $p\in G$

Az ideál redukált Gröbner-alapjára a következő állítás igaz:

Legyen I polinomideál, és adott a monomiális rendezés. Ekkor létezik az I ideális redukált Gröbner-alapja .

Építési algoritmusok

A legelső algoritmus egy ideál redukált Gröbner-alapjának megalkotására a Buchberger-algoritmus . Érdekes módon a jól ismert Gauss-módszer lineáris egyenletrendszerek megoldására a Buchberger-algoritmus speciális esete.

Ezenkívül Jean-Charles Foger francia matematikus F4 és F5 algoritmusokat javasolt a Gröbner-bázis megtalálásához.

Alkalmazások

A Gröbner-bázis alapvető fogalom a számítógépes algebrában , az algebrai geometriában és a számítási kommutatív algebrában .

Történelem

Wolfgang Gröbner osztrák matematikus 1930 -as évek elején kidolgozta szabad kommutatív eset szabványalapjainak elméletét 1950 -es cikkében [1] , ahol ezt írta:

17 évvel ezelőtt kezdtem el ezt a módszert alkalmazni különféle, nagyon összetett példákra.

Eredeti szöveg (német)[ showelrejt] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

1964 -ben egy hasonló koncepciót dolgozott ki a helyi gyűrűkre Heisuke Hironaka , aki 1970 -ben elnyerte a Fields-díjat . A bevezetett polinomrendszereket standard bázisnak nevezte .

A Gröbner-bázis fogalmát 1965 -ben Bruno Buchberger osztrák matematikus , Gröbner egykori tanítványa vezette be . Buchberger egy konstruktív eljárást javasolt a Gröbner-bázis megalkotására egy hatékony számítógépes algoritmus formájában, amely később Buchberger ismertté

Az ideál standard alapja a „kompozíciós lemmán” alapul, amelyet az ismert esetek legbonyolultabb esetére (szabad Lie algebrák ) először AI Shirshov [2] bizonyított . Sőt, egy hasonló állítás helyességét a szabad asszociatív és kommutatív esetekre nyilvánvalónak tartották, és egészen L. A. Bokut későbbi munkáiig az asszociatív gyűrűk gyűrűkbe és adott tulajdonságokkal rendelkező gyűrűkbe való beágyazódásának elméletéig nem keltett különösebb figyelmet. 1972 -ben L. A. Bokut a Novoszibirszki Egyetem asszociatív algebrák kurzusának jegyzeteiben publikálta a "Shirshov kompozíciós lemmáját" a szabad asszociatív esetre . Innen és a szóbeli kommunikációból vált ismertté J. Bergman amerikai algebraista számára, aki 1979 -ben adta ki „Gyémánt Lemma” („Diamond Lemma”) címmel. A munkában nem volt szigorú bizonyíték, és csak a "fúzió" mnemonikus sémáját jelölték meg, amely szükséges Shirshov kompozíciós ötletének megértéséhez. Bergman publikációja után a „gyémánt lemma” népszerűvé vált az algebrászok és a geométerek körében, és felhívta a figyelmet Buchberger „Gröbner-alapjára”. Az 1980-as évek közepén A. A. Mikhalev moszkvai algebraista megalkotta a szuperalgebrák és a színes Lie-algebrák szabványos alapját.

Jegyzetek

↑ W. Gröbner. Über die Eliminationstheorie // Monatshefte für Mathematik : folyóirat. - 1950. - 1. évf. 54 . - 71-78 . o .
↑ SMJ, 1962, 3. kötet, 2. sz. 292-296.

Irodalom

Arzhantsev IV Gröbner algebrai egyenletrendszerek és alapok . - M. : MTSNMO , 2003. - 68 p. — ISBN 5-94057-095-X .
Buchberger B. és mások. Számítógépes algebra: Szimbolikus és algebrai számítások. — M .: Mir, 1986. — 392 p.
Cox D., Little J., O'Shea D. Ideálok, fajták és algoritmusok. Bevezetés az algebrai geometria és a kommutatív algebra számítási vonatkozásaiba. — M .: Mir, 2000. — 687 p. - ISBN 5-03-003320-3 .
Pankratiev EV Bevezetés a számítógépes algebrába . — Intuíció. — ISBN 978-5-9556-0099-4 .

Linkek

Churkin V. A. Polinomiális egyenletrendszerek, ideálok és osztóalapjaik .
Bernd Sturmfels . Mi az a Gröbner-alap?