Base di Gröbner

In algebra commutativa, algebra computazionale e geometria algebrica, una base di Gröbner è un tipo particolare di sottoinsieme generativo di un ideale ${\displaystyle I}$ in un anello dei polinomi ${\displaystyle k[x_{1},\ldots ,x_{n}]}$, dove ${\displaystyle k}$ è un campo.

La teoria delle basi di Gröbner per gli anelli polinomiali è stata sviluppata da Bruno Buchberger nel 1965, che gli diede tale nome in onore del suo mentore Wolfgang Gröbner. Un concetto analogo per gli anelli locali fu sviluppato indipendentemente da Heisuke Hironaka nel 1964, che diede loro il nome di Basi Standard (Standard Basis).

Una base di Gröbner può essere vista come una generalizzazione multivariata non-lineare dell'algoritmo di Euclide per il calcolo del massimo comun divisore univariato, o dell'eliminazione di Gauss-Jordan per i sistemi lineari, o dei problemi di programmazione intera. Le basi di Gröbner hanno il grande vantaggio di ridurre lo studio degli ideali polinomiali a quello degli ideali monomiali (vale a dire generati da monomi).

Dato un ordine monomiale ${\displaystyle <}$ sull'anello polinomiale ${\displaystyle R}$, un sottoinsieme ${\displaystyle G}$ dell'ideale ${\displaystyle I\subset R}$ è detto una base di Gröbner per ${\displaystyle I}$ rispetto a ${\displaystyle <}$ se soddisfa una delle seguenti proprietà:

• l'ideale dato dai termini principali dei polinomi nell'ideale ${\displaystyle I}$ è esso stesso generato dai termini principali della base ${\displaystyle G}$;
• il termine principale di ciascun polinomio in ${\displaystyle I}$ è divisibile per il termine principale di un qualche polinomio della base ${\displaystyle G}$;
• la divisione multivariata di ciascun polinomio nell'anello polinomiale ${\displaystyle R}$ per ${\displaystyle G}$ restituisce un resto univoco;
• la divisione multivariata di ciascun polinomio nell'ideale ${\displaystyle I}$ per ${\displaystyle G}$ restituisce ${\displaystyle 0}$.

Tutte queste proprietà sono equivalenti; le ultime due proprietà consentono di effettuare calcoli nell'anello ${\displaystyle R/I}$ con la stessa facilità dell'aritmetica modulare. È significativo che ogni ideale polinomiale abbia una base di Gröbner, e che essa possa essere ottenuta per ogni ideale partendo con un sottoinsieme generatore.

La divisione multivariata richiede un ordine monomiale: la base dipende dall'ordinamento scelto, e ordinamenti differenti possono portare a basi di Gröbner radicalmente differenti. Due dei più comuni ordinamenti usati sono l'ordine lessicografico e l'ordinamento sul grado totale. Quest'ultimo ordinamento tipicamente fornisce la maggiore velocità di calcolo delle basi di Gröbner; in questo ordine, i monomi sono inizialmente confrontati per grado totale, e in caso di valori uguali viene considerato il monomio più piccolo rispetto all'ordinamento lessicografico.

Nella maggior parte dei casi le basi di Gröbner esistono per qualsiasi ordinamento monomiale. Un metodo per calcolarle è l'algoritmo di Buchberger. Un altro metodo, basato sulle stesse teorie matematiche dell'algoritmo di Buchberger, è l'algoritmo di Faugère F4. Ci sono anche due algoritmi per convertire una base di Gröbner calcolata rispetto ad un ordinamento monomiale ad una calcolata rispetto ad un altro: l'algoritmo FGLM e l'algoritmo Gröbner walk. Questi algoritmi sono spesso impiegati per calcolare Basi di Gröbner lessicografiche (il cui calcolo è solitamente difficile) a partire dal più facile calcolo rispetto all'ordinamento del grado totale.

Una base di Gröbner è detta ridotta se il coefficiente del monomio principale di ciascun elemento della base è 1 e in nessun elemento della base esiste un monomio che sia contenuto nell'ideale generato dai termini principali degli altri elementi della base.

Nel caso peggiore, il calcolo di una base di Gröbner può richiedere un tempo esponenziale rispetto al numero di soluzioni del sistema polinomiale. Malgrado i limiti derivanti da questa complessità, le basi di Gröbner, sia quelle standard che quelle ridotte, sono spesso effettivamente calcolabili, e la maggior parte dei sistemi di computer algebra contiene specifiche routine.

• (EN) M. Kreuzer, L. Robbiano Computational Commutative Algebra 1 and 2, Springer
• Giovanni Calcerano, Basi di Groebner, catene regolari: metodi ed algoritmi per gli ideali polinomiali, tesi di laurea presso la facoltà di Matematica dell'Università La Sapienza di Roma, 1995, relatrice Dina Ghinelli
• (EN) Heisuke Hironaka: Resolution of singularities of an algebraic variety over a field of characteristic zero. In: Annals of Mathematics 79 (1964), Nr. 1, S. 109–326
• (DE) Bruno Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Österreich, Universität Innsbruck, Diss., 1965
• (EN) T. Becker, B. V. Weispfenning, Gröbner bases: a computational approach to commutative algebra. Graduate Texts in Mathematics: readings in mathematics. Bd. 141, New York: Springer Verlag, 1993
• (EN) David Cox, John Little, Donald O'Shea, Ideals, varieties, and algorithms. New York: Springer-Verlag, 1997
• (EN) Joachim von z. Gathen, Jürgen Gerhard, Modern Computer Algebra. Cambridge University Press, 1999

• (EN) Opere riguardanti Gröbner basis, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Gröbner Basis, su MathWorld, Wolfram Research.
• (EN) Gröbner basis, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• CoCoA [1], Computations in Commutative Algebra
• B. Buchberger, Groebner Bases: A Short Introduction for Systems Theorists (PDF). in Proceedings of EUROCAST 2001.
• Comparative Timings Page for Gröbner Bases Software, su magma.maths.usyd.edu.au. URL consultato il 24 novembre 2006 (archiviato dall'url originale il 6 dicembre 2006).
• ogb (archiviato dall'url originale il 5 dicembre 2006). Online Gröbner Basis, Galway, Eire
• Gröbner Basis Theory. Leicester University

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica