Gröbner grund

En Gröbner-bas är en mängd som genererar ett ideal för en given polynomring som har speciella egenskaper.

Definition

Låt följande ges för fält- och pendlingsvariablerna : några ideal för polynomringen av pendlingsvariabler och någon fullständig ordning “ ” på monomialer , där , d.v.s. för . I detta fall måste beställningen dessutom uppfylla två villkor: $F$ $(x_{1},\ldots,x_{n})$ $jag$ $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$

multiplikativitet :innebär för; $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
enhets minimalitet : för, dvs. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

En medlem kallas den ledande (" ledande ") medlemmen (med avseende på ordning ) av polynomet om för alla . ${\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 grunden för ett ideal av en ring är en ändlig uppsättning polynom från , som genererar ett ideal och har följande egenskap: för alla polynom , det finns ett polynom som är delbart med . $jag$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $jag$ $p\in I$ $g\in G$ $l_{\prec }(p)$ $l_{\prec }(g)$

Typer av Gröbner-baser

Den Gröbner minimala basen

Den minimala Gröbnerbasen för ett polynomideal I är dess Gröbnerbas G så att:

Koefficienten vid den högsta monomialen av varje är lika med en. $p\in G$
Den högsta monomen av var och en är inte delbar med någon av de högsta monomierna av andra element i basen. $p\in G$

Minskad Gröbnerbasis

Den reducerade Gröbnerbasen för ett polynomideal I är dess Gröbnerbas G , så att:

Koefficienten vid den högsta monomialen av varje är lika med en. $p\in G$
Ingen av monomierna är delbara med någon av de högsta monomierna av andra element i basen. $p\in G$

För en reducerad Gröbner-bas för ett ideal är följande påstående sant:

Låt mig vara ett polynomideal och viss monomordning ges. Sedan finns det en unik reducerad Gröbnerbas av idealet jag .

Konstruktionsalgoritmer

Den allra första algoritmen för att konstruera en reducerad Gröbner-bas av ett ideal anses vara Buchbergers algoritm . Intressant nog är den välkända Gauss-metoden för att lösa system av linjära ekvationer ett specialfall av Buchberger-algoritmen.

Dessutom föreslog den franske matematikern Jean -Charles Foger F4- och F5 - algoritmerna för att hitta Gröbner-basen.

Applikationer

Gröbnerbasen är ett väsentligt begrepp inom datoralgebra , algebraisk geometri och beräkningskommutativ algebra .

Historik

österrikiske matematikern Wolfgang Gröbner standardbaser för det fria kommutativa fallet i början av 1930 -talet och publicerade den i en tidning från 1950 [1] , där han skrev:

Jag började använda den här metoden för 17 år sedan för olika exempel, några mycket komplexa.

Originaltext (tyska)[ visaDölj] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

1964 utvecklades ett liknande koncept för lokala ringar av Heisuke Hironaka , som vann 1970 års Fields Prize . Han kallade de införda systemen av polynom standardbasen .

Konceptet med en Gröbner-bas introducerades 1965 av den österrikiske matematikern Bruno Buchberger , en tidigare elev till Gröbner. Buchberger föreslog en konstruktiv procedur för att konstruera Gröbner-basen i form av en effektiv datoralgoritm, som senare blev känd som -

Förekomsten av en standardbas för ett ideal är baserad på "kompositionslemma", som först bevisades för det mest komplexa av de kända fallen (fria Lie-algebras ) av AI Shirshov [2] . Dessutom ansågs riktigheten av ett liknande uttalande för de fria associativa och kommutativa fallen uppenbart och väckte inte mycket uppmärksamhet förrän L. A. Bokuts senare arbeten om teorin om inbäddningar av associativa ringar i ringar och ringar med givna egenskaper. 1972 publicerade L. A. Bokut "Shirshovs kompositionslemma" för det fria associativa fallet i anteckningarna till kursen om associativa algebror vid Novosibirsks universitet. Härifrån och genom muntlig kommunikation blev den känd för den amerikanske algebraisten J. Bergman, som gav ut den 1979 under titeln ”Diamond Lemma” (”Diamond Lemma”). Det fanns inga rigorösa bevis i arbetet, och endast det mnemoniska schemat för "fusion" indikerades, vilket är nödvändigt för att förstå Shirshovs idé om komposition. Efter Bergmans utgivning blev "diamantlemma" populärt bland algebraister och geometrar, och det uppmärksammade också Buchbergers "Gröbnerbas". I mitten av 1980- talet konstruerades en standardbas för superalgebror och färgade Lie-algebror av Moskvaalgebraisten A. A. Mikhalev.

Anteckningar

↑ W. Gröbner. Über die Eliminationstheorie // Monatshefte für Mathematik : journal. - 1950. - Vol. 54 . - S. 71-78 .
↑ SMJ, 1962, vol. 3, nr 2, sid. 292-296.

Litteratur

Arzhantsev IV Gröbner baser och system av algebraiska ekvationer . - M. : MTSNMO , 2003. - 68 sid. — ISBN 5-94057-095-X .
Buchberger B. m.fl. Datoralgebra: Symboliska och algebraiska beräkningar. — M .: Mir, 1986. — 392 sid.
Cox D., Little J., O'Shea D. Idealer, varianter och algoritmer. Introduktion till beräkningsaspekter av algebraisk geometri och kommutativ algebra. — M .: Mir, 2000. — 687 sid. - ISBN 5-03-003320-3 .
Pankratiev EV Introduktion till datoralgebra . — Intuition. — ISBN 978-5-9556-0099-4 .

Länkar

Churkin V. A. System av polynomekvationer, ideal och deras divisorbaser .
Bernd Sturmfels . Vad är en Gröbner-bas?