Gröbner grundlag

En Gröbner-basis er et sæt , der genererer et ideal for en given polynomialring, der har særlige egenskaber.

Definition

Lad følgende være givet for felt- og pendlingsvariablerne : nogle idealer for polynomialringen af pendlingsvariabler og en fuldstændig rækkefølge “ ” på monomialer , hvor , dvs. for . I dette tilfælde skal ordren desuden opfylde to betingelser: $F$ $(x_{1},\ldots,x_{n})$ $jeg$ $F[x_{1},\ldots ,x_{n}]$ $(x_{1},\ldots,x_{n})$ $\præc$ $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$ $\præc$

multiplikativitet :betyder for; $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
minimalitet af enhed : for, dvs. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

Et medlem kaldes det førende (" ledende ") medlem (med hensyn til rækkefølge ) af polynomiet , hvis for alle . ${\displaystyle l_{\prec }(p)=\varphi _{l}\cdot x^{l))$ $\præc$ $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\}$

Gröbner-grundlaget for et ideal af en ring er et endeligt sæt af polynomier fra , som genererer et ideal og har følgende egenskab: for ethvert polynomium er der et polynomium , som er deleligt med . $jeg$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $jeg$ $p\in I$ $g\in G$ $l_{\prec }(p)$ $l_{\prec }(g)$

Typer af Gröbner-baser

Gröbner minimal basis

Det minimale Gröbner-grundlag for et polynomielt ideal I er dets Gröbner-basis G , således at:

Koefficienten ved det højeste monomial af hver er lig med én. $p\in G$
Den højeste monomial af hver er ikke delelig med nogen af de højeste monomer af andre elementer i basis. $p\in G$

Reduceret Gröbner-grundlag

Den reducerede Gröbner-basis for et polynomieideal I er dets Gröbner-basis G , sådan at:

Koefficienten ved det højeste monomial af hver er lig med én. $p\in G$
Ingen af monomierne er delelige med nogen af de højeste monomialer af andre elementer i basisen. $p\in G$

For et reduceret Gröbner-grundlag for et ideal er følgende udsagn sandt:

Lad jeg være et polynomielt ideal, og der er givet en vis monomial rækkefølge. Så eksisterer der et enestående reduceret Gröbner-grundlag for idealet jeg .

Konstruktionsalgoritmer

Den allerførste algoritme til at konstruere et reduceret Gröbner -grundlag for et ideal anses for at være Buchbergers algoritme . Interessant nok er den velkendte Gauss-metode til løsning af systemer af lineære ligninger et specialtilfælde af Buchberger-algoritmen.

Derudover foreslog den franske matematiker Jean -Charles Foger F4- og F5 - algoritmerne til at finde Gröbner-grundlaget.

Ansøgninger

Gröbner-grundlaget er et væsentligt begreb inden for computeralgebra , algebraisk geometri og beregningskommutativ algebra .

Historie

østrigske matematiker Wolfgang Gröbner standardbaser for den frie kommutative kasus i begyndelsen af 1930'erne og publicerede den i et papir fra 1950 [1] , hvor han skrev:

Jeg begyndte at bruge denne metode for 17 år siden til forskellige eksempler, nogle meget komplekse.

Originaltekst (tysk)[ Visskjule] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

I 1964 blev et lignende koncept for lokale ringe udviklet af Heisuke Hironaka , som vandt 1970 Fields Prize . Han kaldte de indførte systemer af polynomier standardgrundlaget .

Begrebet et Gröbner-grundlag blev introduceret i 1965 af den østrigske matematiker Bruno Buchberger , en tidligere elev af Gröbner. Buchberger foreslog en konstruktiv procedure til at konstruere Gröbner-grundlaget i form af en effektiv computeralgoritme, som senere blev kendt som -

Eksistensen af et standardgrundlag for et ideal er baseret på "sammensætningslemmaet", som først blev bevist for de mest komplekse af de kendte tilfælde (fri Lie-algebraer ) af AI Shirshov [2] . Desuden blev rigtigheden af et lignende udsagn for de frie associative og kommutative tilfælde betragtet som indlysende og tiltrak ikke megen opmærksomhed, før L. A. Bokuts senere værker om teorien om indlejringer af associative ringe i ringe og ringe med givne egenskaber. I 1972 udgav L. A. Bokut "Shirshovs kompositionslemma" for den frie associative case i noterne fra kurset om associative algebraer ved Novosibirsk Universitet. Herfra og fra mundtlig kommunikation blev den kendt for den amerikanske algebraist J. Bergman, som udgav den i 1979 under titlen "Diamond Lemma" ("Diamond Lemma"). Der var ingen strenge beviser i værket, og kun det mnemoniske skema for "fusion" blev angivet, hvilket er nødvendigt for at forstå Shirshovs idé om sammensætning. Efter Bergmans udgivelse blev "diamantlemmaet" populært blandt algebraister og geometre, og det gjorde også opmærksom på Buchbergers "Gröbner-grundlag". I midten af 1980'erne blev et standardgrundlag for superalgebraer og farvede Lie-algebraer konstrueret af Moskva-algebraisten A. A. Mikhalev.

Noter

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

Litteratur

Arzhantsev IV Gröbner baser og systemer af algebraiske ligninger . - M .: MTSNMO , 2003. - 68 s. — ISBN 5-94057-095-X .
Buchberger B. m.fl. Computeralgebra: Symbolske og algebraiske beregninger. — M .: Mir, 1986. — 392 s.
Cox D., Little J., O'Shea D. Idealer, varianter og algoritmer. Introduktion til beregningsmæssige aspekter af algebraisk geometri og kommutativ algebra. — M .: Mir, 2000. — 687 s. - ISBN 5-03-003320-3 .
Pankratiev EV Introduktion til computeralgebra . — Intuition. — ISBN 978-5-9556-0099-4 .