Baza Gröbner

O bază Gröbner este o mulțime care generează un ideal al unui inel polinomial dat care are proprietăți speciale.

Definiție

Să fie date următoarele pentru variabilele de câmp și de comutație : un ideal al inelului polinomial al variabilelor de comutație și o ordine completă „ ” pe monomii , unde , i.e. pentru . În acest caz, comanda trebuie să îndeplinească în plus două condiții: $F$ $(x_{1},\ldots,x_{n})$ $eu$ $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$

multiplicativitate :implică pentru; $x^{a}\prec x^{b}$ $x^{{a+c}}\prec x^{{b+c}}$ $c\geq 0$
minimalitatea unității : pentru, i.e. . $1\prec x^{a}$ $a>0$ $\exists j:a_{j}>0$

Un membru este numit membru principal („ conducător ”) (în ceea ce privește ordinea ) al polinomului dacă pentru toate . $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}]$ $x^{a}\prec x^{l)$ $a\in A(p)\setminus \{l\}$

Baza Gröbner a unui ideal al unui inel este o mulțime finită de polinoame din , care generează un ideal și are următoarea proprietate: pentru orice polinom , există un polinom astfel care este divizibil cu . $eu$ $F[x_{1},\ldots ,x_{n}]$ $G=\{g_{1},\ldots ,g_{m}\}$ $F[x_{1},\ldots ,x_{n}]$ $eu$ $p\în I$ $g\în G$ $l_{\prec }(p)$ $l_{\prec }(g)$

Tipuri de baze Gröbner

Baza minimă Gröbner

Baza Gröbner minimă a unui ideal polinom I este baza lui Gröbner G astfel încât:

Coeficientul de la cel mai mare monom al fiecăruia este egal cu unu. $p\în G$
Cel mai înalt monom al fiecăruia nu este divizibil cu niciunul dintre cel mai înalt monom al celorlalte elemente ale bazei. $p\în G$

Baza Gröbner redusă

Baza Gröbner redusă a unui ideal polinom I este baza lui Gröbner G , astfel încât:

Coeficientul de la cel mai mare monom al fiecăruia este egal cu unu. $p\în G$
Niciunul dintre monomii nu este divizibil cu oricare dintre cele mai înalte monomii ale altor elemente ale bazei. $p\în G$

Pentru o bază Gröbner redusă a unui ideal, următoarea afirmație este adevărată:

Fie I un ideal polinom și este dată o ordonare monomială. Apoi , există o bază Gröbner redusă unică a idealului I.

Algoritmi de construcție

Primul algoritm pentru construirea unei baze Gröbner reduse a unui ideal este considerat algoritmul lui Buchberger . În mod interesant, binecunoscuta metodă Gauss pentru rezolvarea sistemelor de ecuații liniare este un caz special al algoritmului Buchberger.

În plus, matematicianul francez Jean-Charles Foger a propus algoritmii F4 și F5 pentru găsirea bazei Gröbner.

Aplicații

Baza Gröbner este un concept esențial în algebra computerizată , geometria algebrică și algebra comutativă computațională .

Istorie

austriac Wolfgang Gröbner standard pentru cazul comutativ liber la începutul anilor 1930 și a publicat-o într-o lucrare din 1950 [1] , unde a scris:

Am început să folosesc această metodă acum 17 ani pentru diverse exemple, unele foarte complexe.

Text original (germană)[ arataascunde] Ich habe diese Methode seit etwa 17 Jahren in den verschiedensten, auch kompliziersten Fällen verwendet.

În 1964, un concept similar pentru inelele locale a fost dezvoltat de Heisuke Hironaka , care a câștigat premiul Fields din 1970 . El a numit sistemele de polinoame introduse baza standard .

Conceptul de bază Gröbner a fost introdus în 1965 de matematicianul austriac Bruno Buchberger , un fost elev al lui Gröbner. Buchberger a propus o procedură constructivă pentru construirea bazei Gröbner sub forma unui algoritm computerizat eficient, care mai târziu a devenit cunoscut sub numele Buchberger

Existența unei baze standard pentru un ideal se bazează pe „lema de compoziție”, care a fost demonstrată pentru cel mai complex dintre cazurile cunoscute ( algebre Lie libere ) de AI Shirshov [2] . Mai mult, corectitudinea unei afirmații similare pentru cazurile asociative și comutative libere a fost considerată evidentă și nu a atras prea multă atenție până la lucrările ulterioare ale lui L. A. Bokut privind teoria înglobărilor inelelor asociative în inele și inele cu proprietăți date. În 1972, L. A. Bokut a publicat „Lema compoziției lui Shirshov” pentru cazul asociativ liber în notele cursului de algebre asociative de la Universitatea Novosibirsk. De aici și din comunicarea orală a devenit cunoscută algebristului american J. Bergman, care l-a publicat în 1979 sub titlul „Diamond Lemma” („Diamond Lema”). Nu a existat o dovadă riguroasă în lucrare și a fost indicată doar schema mnemonică a „fuziunii”, care este necesară pentru înțelegerea ideii de compoziție a lui Shirshov. După publicarea lui Bergman, „lema diamantului” a devenit populară printre algebriști și geometri și a atras atenția și asupra „bazei Gröbner” a lui Buchberger. La mijlocul anilor 1980, o bază standard pentru superalgebre și algebre Lie colorate a fost construită de algebristul moscovit A. A. Mikhalev.

Note

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

Literatură

Arzhantsev IV Gröbner baze și sisteme de ecuații algebrice . - M. : MTSNMO , 2003. - 68 p. — ISBN 5-94057-095-X .
Buchberger B. şi alţii. Algebră computerizată: calcule simbolice și algebrice. — M .: Mir, 1986. — 392 p.
Cox D., Little J., O'Shea D. Idealuri, varietăți și algoritmi. Introducere în aspectele computaționale ale geometriei algebrice și algebrei comutative. — M .: Mir, 2000. — 687 p. - ISBN 5-03-003320-3 .
Pankratiev EV Introducere în algebra computerizată . — Intuiția. — ISBN 978-5-9556-0099-4 .

Link -uri

Churkin V. A. Sisteme de ecuații polinomiale, idealuri și bazele divizoarelor lor .
Bernd Sturmfels . Ce este o bază Gröbner?