Universit a degli studi di Trento - Home | Me UniTrento · Universit a degli studi di Trento...

Universita degli studi di Trento

Dipartimento di Matematica

Laurea triennale in Matematica

Teorema della base di Hilbert

e basi di Grobner

Relatrice:Alessandra Bernardi

Laureanda:Maria Ricci

26 settembre 2016

Introduzione

In questa tesi presentiamo un problema classico in algebra computazionale: datoun anello di polinomi in n variabili R a valori in un campo K, e un ideale I ∈ R,determinare se un polinomio f appartiene o meno a I. Se R = K[x1, . . . , xn], lasoluzione e immediata, una volta risolto un secondo problema, ovvero la divisionetra polinomi. Nel caso n = 1, infatti, grazie all’unicita del resto dell’algoritmo didivisione, quest’ultimo e sufficiente come soluzione al problema: ne presentiamo laversione classica nella prima sezione, dopo alcuni risultati preliminari. Per n ≥ 2 lecose si complicano, dal momento che non e piu assicurata l’unicita del resto nelladivisione. Tuttavia il problema e stato completamente risolto, grazie alla teoriadelle basi di Grobner, sviluppata da Bruno Buchberger a partire dalla sua tesi didottorato [1]. Nella seconda parte dunque generalizziamo l’algoritmo di divisione trapolinomi da una a n variabili e introduciamo le basi di Grobner, le quali fornisconoun metodo di divisione che garantisce l’unicita del resto e rispondono esaustivamenteal problema. Infine presentiamo una versione elementare e una piu avanzata di unalgoritmo per calcolare una base di Grobner. Dove non altrimenti specificato, lateoria e gli esempi sono tratti da [2].

INDICE 2

Indice

1 Problema dell’appartenenza in K[x] 31.1 Teorema della base di Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Teorema di scomposizione in fattori irriducibili in K[x] . . . . . . . . . . . 4

2 Problema dell’appartenenza in K[x1, . . . , xn] 62.1 Ordini monomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Algoritmo della divisione in K[x1, . . . , xn] . . . . . . . . . . . . . . . . . . . 92.3 Basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4 Proprieta delle basi di Grobner . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Algoritmo di Buchberger 143.1 Ottimizzazioni dell’algoritmo di Buchberger . . . . . . . . . . . . . . . . . 18

Riferimenti Bibliografici 19

1 PROBLEMA DELL’APPARTENENZA IN K[X] 3

1 Problema dell’appartenenza in K[x]

1.1 Teorema della base di Hilbert

Definizione 1.1. Un anello A si dice notheriano se soddisfa una delle seguenti condizioniequivalenti:

(i) l’insieme degli ideali di A soddisfa la condizione della catena ascendente (A.C.C.):ogni catena ascendente di ideali

I1 ⊂ I2 ⊂ · · · ⊂ Ik ⊂ . . .

si arresta, ovvero Ik = Ik+1 = . . . per qualche k;

(ii) ogni insieme non vuoto di ideali ammette un elemento massimale;

(iii) ogni ideale di A e finitamente generato.

Una dimostrazione dell’equivalenza si puo trovare in [4].

La noetherianita degli anelli di polinomi e fondamentale per la terminazione deglialgoritmi.

Teorema 1.1 (Teorema della base di Hilbert). L’anello di polinomi in una variabile A[x]di un anello noetheriano A e noetheriano.

Dimostrazione (Sarges [3]). Assumiamo per assurdo che A[x] non sia noetheriano, quindiesiste I ideale di A[x] non finitamente generato. Sia f1 6= 0 un polinomio di grado minimotra quelli in I, dunque (f1) ⊆ I. Prendiamo poi un secondo polinomio f2 6= 0 in I \ (f1)di grado minimo e procediamo cosı per induzione: se abbiamo trovato f1, . . . , fk ∈ I nonnulli, prendiamo fk+1 ∈ I \ (f1, . . . , fk) ∀k ∈ N∗. Poiche I non e finitamente generatootteniamo una sequenza infinita di polinomi. Se ai e il coefficiente direttore di fi (si vedala Definizione 2.5 piu avanti) e deg(fi) = ni, abbiamo per costruzione n1 ≤ n2 ≤ . . . eotteniamo una catena ascendente di ideali in A:

(a1) ( (a1, a2) ( · · ·

Mostriamo che questa catena non e stazionaria, giungendo all’assurdo. Se fosse staziona-ria ∃ ah tale che (a1, . . . , ah) = (a1, . . . , ah+1) e dunque ah+1 =

∑hi=1 aibi per certi bi ∈ A,

ma allora fh+1−∑h

i=0 fixnh+1−nibi sarebbe un polinomio in I \ (f1, . . . , fh) di grado stret-

tamente minore di fh+1, il che contraddice le ipotesi su fh+1. Ne segue che la catena none stazionaria, ma questo e assurdo perche A e noetheriano.

Corollario 1.2. Se A e un anello noetheriano, allora anche A[x1, . . . , xn] e un anellonoetheriano.

Dimostrazione. Sara sufficiente procedere per induzione, ricordando cheA[x1, . . . , xn−1][xn] = A[x1, . . . , xn]: per il Teorema della base di Hilbert 1.1, A noetheria-no implica A[x1] notheriano e quindi A[x1][x2] = A[x1, x2] noetheriano eccetera.


1.2 Teorema di scomposizione in fattori irriducibili in K[x]

Sia K un campo e I ⊆ K[x] un suo ideale. L’anello K[x] e noetheriano, poicheogni campo e banalmente noetheriano. Con il prossimo teorema vedremo di piu: ogniideale di K[x] e generato da un unico elemento. Un anello con questa proprieta vienedetto dominio a fattorizzazione unica, o PID. Questo fatto, unito al Teorema della basedi Hilbert 1.1, dimostra che K[x] e un dominio a fattorizzazione unica (UFD), perciose nella fattorizzazione di un polinomio f compare un certo elemento g ∈ K[x] alloraf ∈ (g). Questa e la soluzione al Problema 1 per polinomi in una variabile.

Teorema 1.3. Sia f ∈ K[x] un polinomio di grado positivo e sia c ∈ K il coefficiente di-rettore di f . Quindi esistono polinomi monici irriducibili distinti p1, . . . , pr ∈ K[x] e interipositivi m1, . . . ,mr tali che f = cpm1

1 · · · pmrr . Inoltre se esistono altri polinomi irriducibili

distinti q1, . . . , qs ∈ K[x] ed interi positivi n1, . . . , ns tali che f = cqn11 · · · qns

s , allora r = se si possono permutare i termini qn1

1 · · · qnss in maniera tale che p1 = q1, . . . , pr = qr e

m1 = n1, . . . ,mr = nr.

Dimostrazione. • K campo dunque K[x] e un PID.Sia I un ideale di K[x] e sia f un polinomio di grado minimo in I: chiaramente(f) ⊆ I. Viceversa, sia g ∈ I \ (f), per cui deg(g) ≥ deg(f). Tramite l’algoritmo didivisione euclideo (K[x] e euclideo, grazie alla funzione grado deg : K[x] → N, chemanda un polinomio f(x) ∈ K[x] nel suo grado deg(f) ∈ N) possiamo scrivere:

g = fq + r con q, r ∈ K[x] e deg(r) < deg(f)

osserviamo pero che r = g − fq e f , g ∈ I che e un ideale, percio r ∈ I e r = 0 perminimalita di f , dunque g = fq e I = (f).

• K[x] e un UFD.Ogni PID e un UFD: mostriamo che K[x] e principalmente noetheriano (ogni idealeprincipale soddisfa l’A.C.C.) e ogni elemento irriducibile e primo. La prima af-fermazione e banalmente vera: ogni PID e noetheriano e dunque principalmentenoetheriano. Sia ora p ∈ K[x] irriducibile. Supponiamo che p|ab ma p - a per certia, b ∈ K[x] non nulli e non invertibili. L’ideale (p) e massimale: se ∃ J ⊆ K[x] taleche (p) ⊆ J allora J = (d) per un qualche d ∈ K[x] e (p) ⊆ (d) ossia d|p. Quindi o de associato a p da cui (p) = J oppure d e invertibile e (d) = K[x]. Poiche p - a alloraa /∈ (p) da cui segue che (p, a) = K[x], dunque ∃u, v ∈ K[x] tali che pu + av = 1per cui si puo scrivere pub+ avb = b. Abbiamo trovato che p|b.

• Osserviamo infine che se c e il coefficiente direttore di f , allora

f = cxn +n−1∑i=0

cixi ∈ K[x], c ∈ K (1)

e c e invertibile. Possiamo allora scrivere

f = c

(xn +

n−1∑i=0

cic−1

xi

)=: cg (2)


dove g e un polinomio monico in K[x], che possiede una fattorizzazione unicain polinomi monici irriducibili: g = pm1

1 · · · pmrr , dunque f = cpm1

1 · · · pmrr e la

fattorizzazione (unica) di f .

Teorema 1.4. Il polinomio (x−a) ∈ K[x], a ∈ K, divide f ∈ K[x] se e solo se f(a) = 0.

Dimostrazione. Naturalmente (x−a) divide f , da cui esiste g ∈ K[x] tale che f = (x−a)g.Ne segue che f(a) = g(a)(a− a) = 0.Viceversa, se f(a) = 0 e f = (x− a)q + r per opportuni q, r ∈ K[x] allora0 = f(a) = 0 + r(a), ma deg(r) < deg((x − a)) = 0 percio deg(r) = 0 e r ∈ K, ovveror = 0.

Corollario 1.5. Per controllare se un polinomio f ∈ K[x] appartiene ad un dato idealeI = (p) e sufficiente controllare se p|f . Per fare questo si puo usare il seguente algoritmodi divisione in una variabile.

Algoritmo 1

Input: g, fOutput: q, r

1: while r 6= 0 and LT (g) divide LT (r) do

2: q := q + LT (r)LT (g)

3: r := r − LT (r)LT (g)

g4: end while

Esempio 1.2. Proviamo a vedere se f = 2x3+3x2−5x−4 ∈ I ⊂ K[x] con I = (x2−x−1).Tramite l’Algoritmo 1 otteniamo:

2x + 5

x2 − x− 1)

2x3 + 3x2 − 5x− 4− 2x3 + 2x2 + 2x

5x2 − 3x− 4− 5x2 + 5x + 5

2x + 1

Il resto della divisione e non nullo, percio f = 2x3 + 3x2 − 5x− 4 /∈ I.

2 PROBLEMA DELL’APPARTENENZA IN K[X1, . . . , XN ] 6

2 Problema dell’appartenenza in K[x1, . . . , xn]

Problema 1 (Ideal membership problem). Sia I un ideale in un anello di polinomiK[x1, . . . , xn], dove K e un campo, e sia f un polinomio. Come stabilire se f appartienead I?

L’anello K[x1, . . . , xn] e ancora noetheriano e a fattorizzazione unica, ma non e un PID,quindi non vale un analogo del Corollario 1.5. In questa sezione vediamo che esiste tuttaviaun algoritmo di divisione in piu variabili che ci permette di scrivere una fattorizzazione dif , con un eventuale resto, imponendo alcune condizioni sui termini direttori dei polinomi.Proseguiamo mostrando che e sempre possibile estrarre da I un opportuno sistema digeneratori (una base di Grobner) per cui il resto e unico, e questo sara il criterio perstabilire se f ∈ I o meno.

2.1 Ordini monomiali

Definizione 2.1. Un ordine monomiale su K[x1, . . . , xn] e una relazione “ > ” su Zn≥0

o, equivalentemente, ogni relazione sull’insieme dei monomi xα, α ∈ Zn≥0, che soddisfa:

1. “ > ” e un ordine totale su Zn≥0: per ogni coppia di monomi xα, xβ vale alternati-vamente xα > xβ, xα < xβ, xα = xβ;

2. se α > β e γ ∈ Zn≥0, allora α + γ > β + γ;

3. “ > ” e un buon ordinamento: ogni sottoinsieme non vuoto di Zn≥0 ammette minimorispetto a “ > ”.

Esempio 2.2 (Ordine lessicografico LEX). Siano α = (α1, . . . , αn) e β = (β1, . . . , βn) ∈Zn≥0. Si dice che α >lex β se nel vettore differenza α−β ∈ Zn≥0 la prima entrata non nullada sinistra e positiva. Scriveremo xα >lex x

β se α >lex β.Mostriamo che l’ordine lessicografico e un ordine monomiale.

Osserviamo che l’ordine lessicografico su Zn≥0 si riduce all’ordine naturale in Z≥0 sulk + 1-esimo termine di α e β se αi − βi = 0 ∀i ∈ 1, . . . , k.

1. Supponiamo che αi − βi sia la prima entrata da sinistra non nulla del vettore(α1, . . . , αn)−(β1, . . . , βn): ora l’ordinamento e su Z≥0 dunque vale alternativamenteαi > βi, αi < βi, αi = βi; ne segue che >lex e un ordine totale.

2. Supponiamo α >lex β e γ ∈ Zn≥0. Si ha ((α + γ) − (β + γ)) = ((α1 + γ1) − (β1 +γ1), . . . , (αn + γn)− (βn + γn)) = (α1 − β1, . . . , αn − βn) = α− β percio α >lex β dacui α + γ >lex β + γ.

3. Sia S := {αj}j∈Λ, Λ 6= ∅ un sottoinsieme non vuoto di Zn≥0. Per il principio delminimo esiste un elemento minimale in S, e questo si trova ordinando in Z≥0 i k-esimi termini di {αj = (αj1, . . . , αjn)} tra gli αj che hanno un minimo nell’entrata(k − 1)-esima ∀k = 2, . . . , n.


Esempio 2.3 (Ordine lessicografico graduato GRLEX). Siano α, β ∈ Zn≥0. Con |α| indi-chiamo

∑ni=1 αi. Diciamo che α >grlex β se |α| > |β|, oppure se |α| = |β| e α >lex β.

Mostriamo che l’ordine lessicografico graduato e un ordine monomiale.

La funzione Zn≥0 3 α −→ |α| =∑n

i=1 αi ∈ Z≥0 e un omomorfismo di gruppi, dunque:

1. |α| > |β| in Z≥0 implica α >grlex β in Zn≥0 e da |α| < |β| segue β >grlex α; nel caso|α| = |β| GRLEX si riduce a LEX.

2. Poiche |α|+ |γ| =∑n

i=1 αi +∑n

i=1 γi =∑n

i=1(αi + γi) = |α+ γ| e abbiamo gia vistoda α >lex β segue α + γ >lex β + γ, se α >grlex β allora α + γ >grlex β + γ.

3. Se S := {αj}j∈Λ e un sottoinsieme non vuoto di Zn≥0, allora, a meno di riordino degliindici, abbiamo:

α1 ≥grlex α2 ≥grlex · · · ≥grlex αk ≥grlex · · · (3)

e dunque in Z≥0:|α1| ≥ |α2| ≥ · · · ≥ |αk| ≥ · · · (4)

e questa catena ammette un minimo, cioe esiste un n0 ∈ N per cui |αn| = |αn0|∀n >n0; da n0 in poi ricadiamo nell’ordine lessicografico, che e un buon ordinamento,dunque S ammette minimo.

Esempio 2.4 (Ordine lessicografico graduato inverso DEGREVLEX). Siano α, β ∈ Zn≥0.Diciamo che α >degrevlex β se |α| > |β| o |α| = |β| e la prima entrata non nulla da destrain α− β e non negativa.Mostriamo che l’ordine lessicografico graduato inverso e un ordine monomiale.

1. Se |α| e maggiore o minore di |β| vale lo stesso discorso di GRLEX. Quando |α| = |β|,l’ordine si riduce a quello in Z≥0: infatti, sia αi − βi la prima entrata non nullada destra di α − β; se αi − βi > 0 allora α >degrevlex β, mentre se, al contrario,αi − βi < 0 abbiamo β >degrevlex α; da ultimo, se il vettore differenza α− β e nullo,allora α =degrevlex β.

2. E sufficiente verificare il caso α >degrevlex β e |α| = |β|: se αi−βi e la prima entratanon nulla da destra di α − β allora lo sara anche di (α + γ) − (β + γ): infatti((αi + γi) − (βi + γi)) = αi − βi mentre ((αk + γk) − (βk + γk)) = ((αk − βk) +(γk − γk)) = 0 ∀k = i + 1 . . . n, dunque anche in questo caso α >degrevlex β implicaα + γ >degrevlex β + γ.

3. Come nell’esempio precedente, se S := {αj}j∈Λ e un sottoinsieme non vuoto di Zn≥0,nella catena in Z≥0

|α1| ≥ |α2| ≥ · · · ≥ |αk| ≥ · · · (5)

abbiamo l’uguaglianza da un certo n0 in poi; ora il minimo in {αn}n≥n0 e datodall’elemento αj che ha la prima entrata da destra non nulla minima, cioe tale che∀n αji < αni dove i e la prima entrata non nulla da destra di αn.

Definizione 2.5. Sia f =∑

α aαxα, f ∈ K[x1, . . . , xn] e sia “ > ” un ordine monomiale.

Si danno le seguenti definizioni:


• il multigrado di f e multideg(f) = max>{α ∈ Zn≥0|aα 6= 0};

• il coefficiente direttore di f e:

LC(f) = amultideg(f) ∈ K (6)

• il monomio direttore di f e:

LM(f) = xmultideg(f) (7)

• il termine direttore di f e:

LT (f) = LC(f) · LM(f) (8)

Esempio 2.6. Scriviamo multideg(f), LC(f), LM(f) e LT (f) di f = 4xy2z + 4z2 −5x3 + 7x2z2 ∈ K[x, y, z] per LEX, GRLEX e DEGREVLEX rispettivamente. Definiamo i gradicorrispondenti a ciascun monomio: α1 := (1, 2, 1), α2 := (0, 0, 2), α3 := (3, 0, 0), α4 :=(2, 0, 2).

LEX: Si ha chiaramente α3 >lex α4 >lex α1 >lex α2 e quindi multideg(f) = (3, 0, 0),LC(f) = −5, LM(f) = x3 e LT (f) = −5x3

GRLEX: in questo caso abbiamo |α1| = 4, |α2| = 2, |α3| = 3, |α4| = 4, e α4 >lex α1

per cui l’ordine e α4 >grlex α1 >grlex α3 >grlex α2 e multideg(f) = α4, LC(f) = 7,LM(f) = x2z2 e LT (f) = 7x2z2

DEGREVLEX: poiche α4 >degrevlex α1 l’ordine e uguale a quello di GRLEX.


2.2 Algoritmo della divisione in K[x1, . . . , xn]

Fissato un ordine monomiale “ > ” inK[x1, . . . , xn] e una s-upla di polinomi (f1, . . . , fs)in K[x1, . . . , xn], ogni polinomio f puo essere scritto come f = a1f1 + · · · + asfs + r conai, r ∈ K[x1, . . . , xn]; inoltre o r = 0 oppure r e una combinazione lineare a coefficienti inKdi monomi nessuno dei quali e divisibile per alcun LT (f1), . . . , LT (fs). Se aifi 6= 0 si ha chemultideg(f) ≥ multideg(aifi). Il seguente algoritmo procede dividendo successivamenteil resto ausiliario, che all’inizio e posto uguale a f , per LT (f1), . . . , LT (fs) e ha terminequando il resto ausiliario diventa nullo: questo accade sempre perche il multigrado delresto ausiliario decresce strettamente e l’ordine monomiale scelto e un buon ordinamento.Osserviamo che l’algoritmo non garantisce l’unicita della decomposizione o del resto.

Algoritmo 2

Input: f1, . . . , fs, fOutput: a1, . . . , as, r

1: a1 := 0, . . . , as := 0, r := 02: p := f3: while p 6= 0 do4: i:=1 divisibile := false5: while i ≤ s and divisibile = false do6: if LT (fi) divide LT (p) then

7: ai := ai + LT (p)LT (fi)

8: p := p− LT (p)LT (fi)

fi9: divisibile := true

10: else11: i := i+ 112: end if13: end while14: if divisibilie = false then15: r := r + LT (p)16: p := p− LT (p)17: end if18: end while

Esempio 2.7. Testiamo l’algoritmo di divisione nei seguenti casi con l’ordine LEX x > y

1. f = xy2 +1 e f1 = xy+1 e f2 = y+1. I termini a1, a2 rappresentano rispettivamentei quozienti di f1, f2, riportati sulla sinistra, mentre sulla colonna di destra vengono


segnati i resti. Il dividendo e scritto sotto radice.

a1 : x+ ya2 : 1 resto

xy + 1 √xy2 + 1

y + 1x2y + y

1− yy − 1

2 → 2

La decomposizione e xy2 + 1 = y(xy + 1)− (y + 1) + 2.

2. Dividiamo ora, in due modi diversi, f = x2y+xy2 +y2 per f1 = xy−1 e f2 = y2−1.

a1 : xa2 : x+ 1 resto

xy − 1 √x2y + xy2 + y2

y2 − 1x2y − x

xy2 + x+ y2

xy2 − x

2x+ y2 → 2x

y2

y2 − 1

1 → 1

Abbiamo diviso una volta per f1 e due per f2 e la decomposizione risulta x2y +xy2 + y2 = x(xy + 1) + (x+ 1)(y2 − 1) + 2x+ 1.Dividiamo ora due volte per f1 e una volta per f2: in questo modo otteniamo unadecomposizione diversa.

a1 : x+ ya2 : 1 resto

xy − 1 √x2y + xy2 + y2

y2 − 1x2y − x

xy2 + x+ y2

xy2 − y

x+ y2 + y → x

y2 + y

y2 − 1

y + 1 → y + 1


xy2 + xy2 + y2 = (x+ y)(xy − 1) + (y2 − 1) + x+ y + 1.

Sia ora f = xy2 − x e siano f1 = y2 − 1 e f2 = xy − 1. Chiaramente xy2 − x =x(y2 − 1) = xf1, dunque f ∈ (f1, f2) ma se procediamo con l’Algoritmo 2 dividendo fdapprima per f2 si trova che il resto della divisione e diverso da zero e non piu divisibileper f1 e f2. Procediamo dividendo prima per f2:

a1 : 0a2 : y resto

xy − 1 √xy2 − x

y2 − 1x2y − y

− x+ y → −x+ y

La fattorizzazione in questo modo e xy2 − x = y(xy − 1) + 0(y2 − 1)− x+ y.Da questo esempio possiamo capire che se il resto della divisione e nullo allora f ∈(f1, . . . , fs) ma e falso il viceversa.

Osservazione 2.8. In tutti gli esempi precedenti i divisori erano della forma xα+1 e il LTsecondo l’ordine LEX era xα. Si puo vedere che questo vale in generale, piu precisamente:per ogni ordine monomiale xα > 1 ∀α. Se cosı non fosse avremmo 1 > xα per qualche α;ma allora, per la proprieta 2 in Definizione 2.1 degli ordini monomiali, moltiplicando perxα si ottiene xα > x2α e successivamente xα > x2α > x3α > . . . > xnα > . . . ma questo ein contraddizione con il fatto che un ordine monomiale e un buon ordinamento.

2.3 Basi di Grobner

Definizione 2.9. Sia fissato un ordine monomiale “ > ” su K[x1, . . . , xn]. Sia I ⊆K[x1, . . . , xn] un ideale. Sia G ⊆ I, G = {g1, . . . , gs} una famiglia di elementi di I. Lafamiglia G e detta una base di Grobner di I rispetto a “ > ” se (LT (g1), . . . , LT (gs)) =(LT (I)) := ideale generato dai termini direttori degli elementi di I.

Questa definizione e sensata perche, dato un ideale I ∈ K[x1, . . . , xn] e un suo qual-siasi sottoinsieme di polinomi f1, . . . , ft, vale sempre LT (f1), . . . , LT (ft) ⊂ (LT (I)), mal’inclusione puo essere stretta, come mostra il seguente

Esempio 2.10. Sia I = (f1, f2, f3) ⊆ R[x, y, z] con f1 = xy2 − xz + y, f2 = xy + z2

e f3 = x − yz4. Fissiamo l’ordinamento lessicografico con x > y > z. Il polinomio(xy2− xz+ y)− (xy+ z2)y+ (x− yz4) = y+ yz− yz5 appartiene ad I, ma il suo terminedirettore e LT (y+yz−yz5) = y, che di certo non appartiene a (LT (f1), LT (f2), LT (f3)) =(xy2, xy, x).

In casi semplici e facile individuare una base di Grobner.

Esempio 2.11. Sia I = (g1, g2) ∈ R[x, y, z] con g1 = x− z, g2 = y+ z. Si ha LT (g1) = x,LT (g2) = y con LEX; gli elementi g1, g2 formano una base di Grobner: verifichiamo l’in-clusione (LT (I)) ⊂ (x, y). Se f appartiene ad I esistono A(x, y, z), B(x, y, z) ∈ R[x, y, z]tali che f = A(x, y, z)(x− z) +B(x, y, z)(y + z), ovvero

f = A(x, y, z)x− A(x, y, z)z +B(x, y, z)y +B(x, y, z)z.


Se vale LT (f) /∈ (x, y), ovvero LT (f) non e divisibile ne per x ne y, non puo che essereLM(f) = zm per qualche m ≥ 0. Ma allora non dovremmo avere monomi in x, y, maquesto e impossibile.

Definizione 2.12. Un ideale si dice monomiale se possiede un sistema di generatoricostituito solo da monomi.

Il seguente risultato permette di dimostrare l’unicita del resto se l’insieme dei divisorie una base di Grobner.

Teorema 2.1 (Lemma di Dickson). Sia I ⊂ K[x1, . . . , xn] un ideale monomiale. AlloraI puo essere scritto nella forma I = (xα(1), . . . , xα(s)) con (α(1), . . . , α(s)) ∈ Zn≥0. Inparticolare I ha una base finita.

Dimostrazione. La dimostrazione procedera per induzione sul numero n di variabili.Se n = 1, K[x1] e un PID: l’ideale I = (xα : α ∈ A ⊂ Z≥0) e generato dall’unico monomioxβ tale che β ≤ α ∀α ∈ A.Supponiamo ora n ≥ 1 e che la tesi sia vera per n − 1. Indicheremo per chiarezzaxn =: y e di conseguenza i monomi come xεym con ε ∈ Zn−1

≥0 e m ∈ Z≥0. Consideriamoquindi un ideale monomiale I ⊂ K[x1, . . . , xn−1, y] e la sua proiezione in K[x1, . . . , xn−1],J := {xε : xεym ∈ I}, ovvero generato dai monomi xε che moltiplicati per ym stanno in I.L’ideale J e monomiale, dunque per ipotesi induttiva ha un numero finito di generatori:J = (xε(1), . . . , xε(s)). Per definizione di J , per ogni i = 1 . . . s, esiste un mi ≥ 0 tale chexε(i)ymi ∈ I; selezioniamo m := max{mi : i = 1 . . . s} e definiamo gli ideali

Jk ⊂ K[x1, . . . , xn−1], Jk := {xβ : xβyk ∈ I} per ogni k tra 0 e m− 1.

Questi ideali sono ancora monomiali e ricadono nell’ipotesi induttiva, percio, per ogni k,Jk = (xεk(1), . . . , xεk(sk)). Vediamo che I e generato dai seguenti monomi:

xε(1)ym, . . . , xε(s)ym da J =: Jm

xε0(1), . . . , xε0(s) da J0

xε1(1)y, . . . , xε1(s)y da J1

. . .

. . .

xεm−1(1)ym−1, . . . , xεm−1(s)ym−1 da Jm−1

infatti ogni monomio di I e divisibile per almeno un elemento della lista, per costruzionedegli ideali Jk. Sia xαyp ∈ I: se p ≥ m allora xαyp e divisibile per qualche xε(i)ym, mentrese p ≤ m− 1 allora e divisibile per un xεp(j)yp. Ne segue che i suddetti monomi generanoun ideale contenente gli stessi monomi di I, dunque sono uguali. Resta da provare chel’insieme finito di generatori puo essere estratto da un dato insieme di generatori dell’i-deale, ovvero che, se I = {xα : α ∈ A} e A ⊂ Zn≥0, allora I e generato da un numero

finito di tali xα. Abbiamo visto che I = (xβ(1), . . . , xβ(s)) per certi xβ(i) ∈ I. Ma alloraogni xβ(i) e divisibile per un qualche xα(i), α(i) ∈ A.


Esempio 2.13. Per vedere meglio come funziona la dimostrazione del Lemma di Dicksoncalcoliamo una base per l’ideale I ∈ K[x, y], I = (x3y6, x5y4, x6) ordinato lessicografica-mente. La proiezione di I in K[x] e J = (x3); la massima potenza in cui compare y in Ie m = 6, dunque le sezioni di I sono

J0 = (x6)

J1 = J2 = J3 = {0}

J4 = J5 = (x5)

ne segue che una base per I e data da (x3y6, x6, x5y4, x5y5).

2.4 Proprieta delle basi di Grobner

Proposizione 2.2. Sia I ⊆ K[x1, . . . , xn] un ideale. Allora

1. (LT (I)) e un ideale monomiale;

2. esistono g1, . . . , gs ∈ I tali che (LT (I)) = (LT (g1), . . . , LT (gs)).

Dimostrazione. 1. Se K[x1, . . . , xn] e noetheriano allora I e finitamente generato, dun-que possiamo prendere come sistema di generatori LT (f) per ogni f ∈ I;

2. Per il Lemma di Dickson 2.1 esistonom1, . . . ,ms ∈ I tali che (LT (I)) = (m1, . . . ,ms).Quindi {m1, . . . ,ms} ⊂ (LT (I)), percio per ogni i = 1, . . . , s, mi e il terminedirettore di qualche gi ∈ I (e sufficiente prendere gi = mi + fi con fi ∈ I emultideg(fi) ≤ multideg(mi)). Abbiamo trovato g1, . . . , gs ∈ I tali che (LT (I)) =(LT (g1), . . . , LT (gs)).

Proposizione 2.3. Sia G = {g1, . . . , gt} una G-base dell’ideale I ⊆ K[x1, . . . , xn] e siaf ∈ K[x1, . . . , xn], quindi esiste ed e unico r ∈ K[x1, . . . , xn] tale che

(i) nessun termine di r e divisibile per uno dei LT (gi);

(ii) esiste g ∈ I tale che f = g + r.

Dimostrazione. L’esistenza di un tale r e data dall’algoritmo di divisione visto nella se-zione precedente: esistono h1, . . . , ht, r ∈ K[x1, . . . , xn] tali che f = h1g1 + · · · + htgt + re g := h1g1 + · · · + htgt appartiene a I perche g1, . . . , gt e una G-base. Per quanto ri-guarda l’unicita, supponiamo che f = g + r = g′ + r′ con g, g′ ∈ I; allora r − r′ =g′ − g ∈ I e LT (r − r′) ∈ (LT (I)). Ne segue che o LT (r − r′) e divisibile per qualcheLT (g1), . . . , LT (gt), ma questo contraddice le ipotesi fatte su r e r′, oppure r = r′.

Corollario 2.4. Sia G = {g1, . . . , gt} una G-base dell’ideale I ⊆ K[x1, . . . , xn] e siaf ∈ K[x1, . . . , xn]. Si ha che f ∈ I se e solo se il resto della divisione di f per G e 0.

3 ALGORITMO DI BUCHBERGER 14

Dimostrazione. Abbiamo gia visto che se il resto della divisione di f per G = {g1, . . . , gt}e nullo allora f ∈ (g1, . . . , gt) ⊆ I. Viceversa, sia f ∈ I; per l’algoritmo della divisionepossiamo sempre scrivere

f =t∑i=1

aigi + r con ai, r ∈ K[x1, . . . , xn]

dove r e il resto della divisione. Quindi r = f −∑t

i=1 aigi ∈ I, da cui LT (r) e divisibileper almeno uno tra LT (g1), . . . , LT (gt), ma questo e assurdo per la definizione di r. Nesegue che r = 0.

Dunque per risolvere il Problema 1 per un ideale I e un polinomio f in K[x1, . . . , xn] siusa l’Algoritmo 2, prendendo come insieme di divisori una G-base per I.

3 Algoritmo di Buchberger

Presentiamo qui una prima versione di un algoritmo per estrarre una base di Grobner daun insieme di polinomi, basato sull’uso degli S-polinomi, di cui diamo subito la definizione.

Definizione 3.1. Siano f, g due polinomi non nulli in K[x1, . . . , xn]; indichiamo con αe β i loro rispettivi multigradi. Sia γ = (γ1, . . . , γn) con γi = max(αi, βi) per ogni i. Ilminimo comune multiplo di LM(f) e LM(g) e definito come

xγ = LCM(LM(f), LM(g)).

L’S-polinomio di f e g e la combinazione

S(f, g) =xγ

LT (f)· f − xγ

LT (g)· g.

Esempio 3.2. Facciamo un esempio di un S-polinomio: siano f = 4x2z − 7y2 e g =xyz2 + 3xz4 in R[x, y, z] . Secondo l’ordine lessicografico LT (f) = 4x2z, LT (g) = xyz2 ementre il minimo comune multiplo e x2yz2, dunque:

S(f, g) =x2yz2

4x2z4xz − 7y2 − x2yz2

xyz2xyz2 + 3xz4 = −3x2z4 − 7

4y3z

e LT (S(f, g)) = −3x2z4 <lex x2yz2.

Lemma 3.1. Sia∑s

i=1 cifi una somma di polinomi tali che multideg(fi) = δ ∈ Zn≥0 perogni i e ci ∈ K. Se multideg(

∑si=1 cifi) < δ allora la somma puo essere scritta come

combinazione lineare a coefficienti in K degli S-polinomi S(fj, fk) per 1 ≤ j, k ≤ s.Inoltre per ogni j, k vale multideg(S(fj, fk) < δ).

Dimostrazione. Sia di = LC(fi). Poiche multideg(∑s

i=1 cifi) < δ mamultideg(fi) = δ non puo che essere

∑si=1 cidi = 0, ovvero il termine direttore si can-

cella. Calcoliamo ora gli S-polinomi, definendo i polinomi monici pi = fidi

. Per ipotesi

LCM(LM(fj), LM(fk)) = xδ, quindi

S(fj, fk) =xδ

LT (fj)fj −

xδ

LT (fk)fk =

xδ

djxδfj −

xδ

dkxδfk = pj − pk (9)


ogni pi ha multigrado pari a δ e coefficiente direttore 1, dunque le differenze pj−pk hannomultigrado strettamente minore di δ e dall’equazione precedente questo vale anche per gliS-polinomi. Riscriviamo ora la somma in termini dei pi

s∑i=1

cifi = c1d1(p1 − p2) + (c1d1 + c2d2)(p2 − p3) + · · ·

+ (c1d1 + · · ·+ cs−1ds−1)(ps−1 − ps) + (c1d1 + · · ·+ csds)ps. (10)

Usando (9) e∑s

i=1 cidi = 0 otteniamo la combinazione lineare voluta

s∑i=1

cifi = c1d1S(f1, f2) + (c1d1 + c2d2)S(f2, f3) + · · ·

+ (c1d1 + · · ·+ cs−1ds−1)S(fs−1, fs). (11)

Il prossimo teorema e la base su cui si fonda l’algoritmo per calcolare delle basi diGrobner, ideato da Bruno Buchberger [5].

Teorema 3.2 (criterio di Buchberger). Sia I ∈ K[x1, . . . , xn] un ideale non vuoto. Unabase G = g1, . . . , gs per I e una G-base per I se e solo se per ogni coppia i, j con i 6= j, ladivisione di S(gi, gj) per G (in un qualche ordine) da resto nullo.

Dimostrazione. Se G e una base di Grobner, allora il resto della divisione di S(gi, gj) ∈ Iper G e nullo per il Corollario 2.4.Viceversa, supponiamo che f ∈ I sia un polinomio non nullo. Dobbiamo mostrare cheLT (f) ∈ (LT (g1), . . . , LT (gs)). Dal momento che G e una base per I, esistono h1, . . . , hs ∈K[x1, . . . , xn] tali che

f =s∑i=1

higi. (12)

Definiamom(i) = multideg(higi) em = max{m(i) : i = 1 . . . s}. Allora si ha multideg(f) ≤m. Se vale l’uguaglianza allora LT (f) ∈ (LT (g1), . . . , LT (gs)), mentre se vale il minorestretto allora e avvenuta qualche cancellazione tra i LT di g1, . . . , gs. Osserviamo ora chela scrittura di (12) non e unica, ovvero possiamo prendere altri polinomi h′1, . . . , h

′s ed

ottenere comunque f , variando solo il multigrado m. Tuttavia un ordine monomiale eun buon ordinamento, quindi esistera un m minimale. Vediamo che con questo m valel’uguaglianza multideg(f) = m tramite una dimostrazione per assurdo. Riscriviamo f nelmodo seguente

f =∑

m(i)=m

higi +∑

m(i)≤m

higi =

=∑

m(i)=m

LT (hi)gi +∑

m(i)=m

(hi − LT (hi))gi∑

m(i)≤m

higi. (13)


Assumendo per assurdo che multideg(f) < m, la prima somma deve avere anch’essa mul-tigrado < m, dal momento che i monomi nella seconda e terza ce l’hanno per costruzione.Possiamo ulteriormente riscrivere f ponendo LT (hi) = cix

αi , per cui

f =∑

m(i)=m

cixαigi +

∑m(i)=m

(hi − cixαi)gi∑

m(i)≤m

higi. (14)

Ora, la prima somma e una combinazione lineare degli S-polinomi S(xαjgj, xαkgk) per il

Lemma 3.1. Vediamo come sono fatti: per costruzione, ogni termine xαigi ha lo stessomultigrado m, dunque

S(xαjgj, xαkgk) =

xm

xαjLT (gj)xαjgj −

xm

xαkLT (gk)xαkgk = xm−γjkS(gj, gk) (15)

dove γjk = LCM(LM(gj), LM(gk)). Ne segue che esistono cjk ∈ K tali che∑m(i)=m

LT (hi)gi =∑j,k

cjkxm−γjkS(gj, gk). (16)

Dall’Algoritmo 2 e dall’ipotesi che gli S-polinomi abbiano resti nulli modulo G sappiamoche esistono aijk ∈ K[x1, . . . , xn] tali che

S(gj, gk) =∑s

i=1 aijkgi e

multideg(aijkgi) ≤ multideg(S(gj, gk)) per ogni i, j, k

ovvero, quando il resto e nullo possiamo scrivere S(gj, gk) come una combinazione linearedi G dove non tutti i termini direttori si cancellano. Moltiplicando da entrambe le partiper xm−γjk abbiamo la disuguaglianza

multideg(xm−γjkaijkgi) ≤ multideg(xm−γjkS(gj, gk)) < m. (17)

Ora sostituendo xm−γjkS(gj, gk) in (16) e ponendo bijk = xm−γjkaijk otteniamo∑m(i)=m

LT (hi)gi =∑j,k

cjkxm−γjkS(gj, gk) =

=∑j,k

cjk

(∑i

bijkgi

)=∑i

digi (18)

con multideg(digi) < m per ogni i. Sostituendo ancora in (14) otteniamo una espressioneper f come combinazione lineare di G dove ogni monomio ha multigrado minore di m, ilche contraddice la minimalita di m.

Una volta scelto un ordine monomiale si puo procedere con la seguente versione ele-mentare dell’algoritmo di Buchberger.


Algoritmo 3

Input: I = (f1, . . . , fs)Output: una base di Grobner GB = (g1, . . . , gt) per I

1: GB := F2: repeat3: G := GB4: for (p, q) coppia in G con p 6= q do5: R:= resto della divisione di S(p, q) per G6: if S 6= 0 then7: G := G ∪ {S}8: end if9: end for

10: until GB = G

Esempio 3.3. Calcoliamo una base di Grobner per l’ideale I = (f1, f2), con f1 = x2y−1,f2 = xy2 − x, usando l’Algoritmo 3 e l’ordine lessicografico.Impostiamo G := GB := {f1, f2} e calcoliamo il primo S-polinomio:

S(f1, f2) = x2y2

x2y(x2y − 1)− x2y2

xy2(xy2 − x) = x2 − y

che non e divisibile per G ed e non nullo, dunque aggiungiamo R := f3 := x2 − y a G.Risulta quindi G 6= GB, percio proseguiamo.

S(f1, f3) = y2 − 1, non divisibile per G→ R := y2 − 1→ aggiungiamo f4 := y2 − 1a G

S(f2, f3) = y3 − 1, che, diviso per G da R := y − 1 → aggiungiamo a G il nuovopolinomio f5 := y − 1

S(f1, f4) = x2 − y = f3 → R := 0 e non aggiungiamo termini a G

S(f2, f4) = 0→ R := 0, andiamo avanti

S(f3, f4) = x2 − y3 → R := 0.

Tutti i restanti S-polinomi danno resto nullo, per cui otteniamo G = GB e abbiamoterminato. Una base di Grobner per I e

{g1, g2, g3, g4, g5} = {x2y − 1, xy2 − x, x2 − y, y2 − 1, y − 1}.

Da questo solo esempio possiamo notare che l’Algoritmo 3 non e molto veloce: anchepartendo da due polinomi in due variabili il ciclo principale puo durare a lungo, percheogni volta che viene aggiunto un nuovo termine e necessario considerare tutte le nuovecoppie di polinomi. Notare che nell’Esempio abbiamo evitato di ricalcolare gli S-polinomigia esaminati, sebbene, cosı come e scritto, l’algoritmo prenda in considerazione ognivolta tutte le coppie in G. Nella prossima sezione vedremo una versione piu avanzatadell’Algoritmo.


3.1 Ottimizzazioni dell’algoritmo di Buchberger

Le seguenti osservazioni sono tratte da [6].

1. La scelta dell’ordine monomiale influenza i tempi di calcolo: si e visto che DEGREVLEXproduce i risultati migliori.

2. Scegliendo ad ogni ciclo coppie di polinomi (f, g) in I tali che il minimo comunemultiplo dei rispettivi termini direttori sia il piu piccolo possibile, S(f, g) tendera afornire prima un resto non nullo durante il processo.

3. L’operazione piu costosa e la divisione degli S-polinomi, ma fortunatamente e pos-sibile ridurre il numero di tali divisioni:

- se ad un certo punto troviamo un resto nullo, ovvero S = 0 al punto 5 nell’Al-goritmo 3, questo rimarra nullo anche aggiungendo altri elementi all’insiemegeneratore G, dunque non e necessario ricalcolarlo. Piu precisamente, dal mo-mento che i nuovi generatori vengono aggiunti uno per volta, sara sufficientecalcolare i resti della divisione di S(fi, fj) per G con i ≤ j − 1;

- quando GCD(LT (f), LT (g)) = 1, ovvero quando f e g hanno termini direttorisenza variabili comuni, S(f, g) da resto nullo se diviso per {f, g} ∈ G, dunquenon e necessario calcolarlo;

- infine, se in G esistono p, f, g tali che lt(p) divide LCM(LT (f), LT (g)) e i restidi S(f, p), S(g, p) sono gia stati calcolati, possiamo trascurare la coppia (f, g).

Il seguente algoritmo tiene conto di quanto detto.

Algoritmo 4

Input: I = (f1, . . . , fs)Output: una base di Grobner G = (g1, . . . , gt) per I

1: GB := I2: B := {(i, j) : 1 ≤ i < j ≤ s e GCD(LT (fi), LT (fj)) 6= 1}3: t := s4: while B 6= ∅ do5: (i, j) := (i, j) ∈ B con minimo LCM(LT (fi), LT (fj))6: B := B \ {(i, j)}7: if non esiste alcun p ∈ GB tale che (fi, p) /∈ B, (fj, p) /∈ B e

LT (p) divida LCM(LT (fi), LT (fj)) then8: S := resto della divisione di S(f, g) per GB9: if S 6= 0 then

10: t := t+ 1; ft := S11: GB := GB ∪ {S}12: B := B ∪ {(i, t) : 1 ≤ i ≤ t− 1}13: end if14: end if15: end while16: return GB

RIFERIMENTI BIBLIOGRAFICI 19

Riferimenti bibliografici

[1] B. Buchberger. An algorithm for finding the basis elements of the residue classes ringof a zero dimensional polynomial ideal. University of Innsbruck, 1965.

[2] D. Cox, J. Little, D. O’Shea. Ideals, Varieties, and Algorithms, cap. 1 e 2. Springer-Verlag 2007.

[3] P.M. Cohn, Basic Algebra: Groups, Rings and Fields. Springer 2015.

[4] M. Reid. Undergraduate Commutative Algebra. Cambridge University Press 1995.

[5] B. Buchberger. Grobner-Bases: An Algorithmic Method in Polynomial Ideal Theory,in Multidimensional Systems Theory - Progress, Directions and Open Problems inMultidimensional Systems. Reidel Publishing Company 1985.

[6] A. Heck. Introduction to Maple, pp. 697-746. Springer-Verlag 1993.

Universit a degli studi di Trento - Home | Me UniTrento · Universit a degli studi di Trento...

Documents

Transcript of Universit a degli studi di Trento - Home | Me UniTrento · Universit a degli studi di Trento...