Cenni alle basi di Grobner

In queste pagine si presentano molto sommariamente alcuni aspetti della nozione e dell’uso delle basi di Grobner.

Un’introduzione completa ed esauriente si puo trovare ormai in molti testi, tra cui segnaliamo l’articolo di Buchberger nel

libro di Buchberger e Winkler, Grobner basis and applications (Cambridge University Press 1998) ed i due volumi di Kreuzer

e Robbiano, Computational Commutative Algebra 1 & 2 (Springer). Questi ultimi forniscono un ampio repertorio di appli-

cazioni di queste tecniche a problemi di varia natura e introducono all’uso del software open-source CoCoA, reperibile al sito

CoCoA.dima.unige.it dell’Universita di Genova. Un altro testo introduttivo, rivolto ad alcune applicazioni di queste tecniche

alla Geometria Algebrica, e Cox, Little, O’Shea, Ideals, Varieties and Algorithms: an introduction to Computational Algebraic

Geometry and Commutative Algebra (Springer); cosı come segnalo il volume collettivo Computations in algebraic geometry

with Macaulay 2, a cura di Eisenbud, Grayson, Stillman and Sturmfels, reperibile assieme al software (open-source) Macaulay 2

nel sito dell’Universita dell’Illinois ad Urbana-Champaign (www.math.uiuc.edu/Macaulay2/Book). Nello stesso sito sono presenti

numerose indicazioni e tutorial sull’uso del software stesso.

1. Moduli noetheriani

Cominciamo richiamando alcune definizioni generali sui moduli su un anello.

Definizione. Sia A un anello commutativo con unita. Un A-modulo e un gruppo abeliano M dotato diuna moltiplicazione A×M →M soddisfacente alle condizioni

(a+ b)m = am+ bm, a(m+ n) = am+ an, a(bm) = (ab)m, 1m = m,

qualunque siano a, b in A ed m,n in M .

Ad esempio, se A e il campo R dei numeri reali, un A-modulo e uno spazio vettoriale su R. Se A = Z,l’anello degli interi razionali, ogni gruppo abeliano e un modulo su A. Come per gli spazi vettoriali, gliomomorfismi di A-moduli sono le applicazioni lineari, ovvero le applicazioni f : M → N tali che f(a1m1 +a2m2) = a1f(m1) + a2f(m2) per ogni m1,m2 in M ed ogni a1, a2 in A.

Vediamo ora una serie di condizioni equivalenti.

Proposizione. Siano A un anello commutativo con unita ed M un A-modulo. Sono equivalenti le seguentiaffermazioni:(a) ogni sottomodulo N di M e finitamente generato;(b) ogni catena ascendente di sottomoduli, M0 ⊆ M1 ⊆ M2 ⊆ · · ·, di M e stazionaria; ovvero, esiste un

indice n0 tale che Mn0 =⋃n≥0Mn;

(c) ogni sottoinsieme non vuoto di sottomoduli di M contiene un elemento massimale.

dim. (a) ⇒ (b). Data una catena ascendente di moduli, come nell’enunciato, sia N =⋃n≥0Mn e siano

f1, . . . , fr dei generatori di N . Se n0 e un indice sufficientemente grande affinche f1, . . . , fr appartenganotutti a Mn0 , si ha necessariamente Mn0 = N .

(b)⇒ (c). Sia A una famiglia non vuota di sottomoduli di M e supponiamo per assurdo che non vi sia unelemento massimale. Allora, a partire da un sottomodulo M0 ∈ A posso trovare un sottomodulo M1 in Aper cui M0 ( M1. Ragionando analogamente con M1, esiste un sottomodulo M2 in A per cui M1 ( M2.Continuando allo stesso modo potrei costruire una catena ascendente di sottomoduli che non e stazionaria,contro le ipotesi.

(c) ⇒ (a). Sia N un sottomodulo e sia F l’insieme dei sottomoduli di N che sono finitamente generati. Sitratta di un insieme non vuoto, perche certamente (0) ∈ F . Detto N0 un elemento massimale di F , se nonfosse N0 = N , potrei trovare un elemento f ∈ N tale che f ∈ N r N0. Allora avrei N0 ( N0 + Af ∈ F ,contro l’ipotesi che N0 fosse un elemento massimale. �

1

Definizione. Un A-modulo M si dice noetheriano se soddisfa alle condizioni della Proposizione precedente.Un anello A si dice noetheriano se lo e come modulo su se stesso (ovvero se tutti i suoi ideali sono finitamentegenerati).

L’anello dei numeri interi, Z, cosı come l’anello C[X] dei polinomi in una indeterminata a coefficienti inun campo C, sono anelli euclidei e quindi tutti i loro ideali sono principali e quindi si tratta di anelli noethe-riani. In particolare, osserviamo che la funzione grado da un buon ordinamento dei monomi 1, X,X2, X3, . . .di C[X] e che un polinomio f appartiene all’ideale generato da un elemento f0, se, e solo se, f0 | f .

Nell’anello C[X1, . . . , Xn] dei polinomi in n indeterminate, la funzione grado non da piu un buon or-dinamento tra i monomi e non definisce un algoritmo di divisione euclideo; gli ideali di C[X1, . . . , Xn] nonsono piu principali, cosı come non e piu vero che un elemento appartenga ad un ideale solo se e divisibile peruno dei generatori dell’ideale stesso. Il celebre Teorema della base di Hilbert afferma che, se un anello R enoetheriano, allora anche l’anello dei polinomi R[X] lo e. Quindi potremmo dedurre da questo che l’anelloC[X1, . . . , Xn] e noetheriano, visto che l’anello dei polinomi in una indeterminata (oppure il campo C) e unanello noetheriano. Nel seguito vedremo una dimostrazione di questo fatto che non fa appello al Teorema diHilbert.

2. Ideali monomiali

Introduciamo in C[X1, . . . , Xn] la notazione dei multiindici, ovvero, dato α = (α1, . . . , αn) ∈ Nn, scrive-remo Xα (o Xα se vi fosse il rischio di ambiguita) per indicare il monomio Xα1

1 · · ·Xαnn . Il grado del monomio

e l’intero |α| = α1 + · · · + αn. Scriveremo f =∑α cαX

α per indicare un elemento di C[X1, . . . , Xn], ove ilcoefficiente cα e diverso da zero solo per un numero finito di multiindici. I monomi Xα, al variare di α inNn, formano una base del C-spazio vettoriale C[X1, . . . , Xn], e cio conferisce alcune particolarita agli idealigenerati da monomi, detti anche ideali monomiali.

Proposizione. Sia J un ideale monomiale di C[X1, . . . , Xn].(a) Un monomio Xγ appartiene a J se, e solo se, e divisibile per uno dei monomi che generano J .(b) Un polinomio f =

∑β cβX

β appartiene a J se, e solo se, tutti i monomi Xβ con cβ 6= 0 appartengonoa J .

(c) [Lemma di Dickson] J e generato da un numero finito di monomi.

dim. (a) SiaXγ = f1Xα1+· · ·+frXαr conXα1 , . . . , Xαr monomi in J ed f1, . . . , fr polinomi in C[X1, . . . , Xn].

Scrivendo i polinomi f1, . . . , fr come somma di monomi a coefficienti in C e raccogliendo gli addendi conte-nenti lo stesso monomio, si ottiene una scrittura del tipo

Xγ =

r∑i=1

∑βi

cβiXαiXβi .

Poiche si tratta degli elementi di una base, deve essere cβi = 1 per un opportuno multiindice βi ∈ Nn, mentretutti gli altri coefficienti sono uguali a zero. Per cui Xγ = XαiXβi .(b) Se f =

∑β cβX

β appartiene a J , allora f = f1Xα1 + · · ·+frXαr per opportuni monomi Xα1 , . . . , Xαr in

J ed opportuni polinomi f1, . . . , fr in C[X1, . . . , Xn]. Quindi ogni monomio Xβ che compare effettivamentenella scrittura di f deve ottenersi come XαiXµ per un qualche αi ovvero comparire come addendo in qualcunodei prodotti a destra, perche i monomi formano una base dello spazio vettoriale.(c) Si dimostra per induzione sul numero n di indeterminate. Essendo vero quando n = 1; supponiamo chela tesi sia vera in C[X1, . . . , Xn−1] e consideriamo gli ideali monomiali

Jm = (Xα ∈ C[X1, . . . , Xn−1] | XαXmn ∈ J )

che formano una catena ascendente. Per l’ipotesi induttiva, la catena e stazionaria e quindi esiste un interom0 tale che Jm0 =

⋃m≥0 Jm. Per ottenere un insieme di generatori di J e quindi sufficiente prendere un

insieme finito di generatori per ciascuno degli ideali J0, J1, . . . , Jm0e moltiplicare ogni elemento di questi

insiemi per la relativa potenza di Xn (i generatori di J0 per 1 = X0n, i generatori di J1 per Xn, i generatori

di J2 per X2n, e cosı via). �

2

3. Ordinamenti monomiali

Uno strumento che si rivelera utile nel seguito consiste nell’introdurre un buon ordinamento(†) tra imonomi dell’anello C[X1, . . . , Xn], che sia compatibile con la relazione di divisibilita.

Definizione. Un (buon) ordinamento monomiale (term-ordering) sui monomi di C[X1, . . . , Xn] e un buonordinamento compatibile col prodotto, ovvero tale che

Xα ≤ Xβ ⇒ XαXµ ≤ XβXµ

per ogni monomio Xµ.

Esempi. (a) Poiche gli esponenti dei monomi variano in Nn e l’insieme dei numeri naturali, N, e bene-ordinato nell’ordinamento usuale, si verifica immediatamente che si ha un buon ordinamento monomiale(∗)

ponendo• l’ordinamento lessicografico su Nn (lex), ove α > β se esiste un indice 1 ≤ i0 ≤ n tale che i < i0 ⇒αi = βi e αi0 > βi0 .

(b) Dato un elemento α = (α1, . . . , αn) ∈ Nn, si indica talvolta con |α| = α1 + · · · + αn il suo grado (o lasua lunghezza). Ricordiamo due ordinamenti particolarmente usati:• L’ordinamento grado-lessicografico su Nn (grlex) per cui α > β se |α| > |β| in N, oppure |α| = |β| eα > β nell’ordine lessicografico.• L’ordinamento grado-lessicografico rovesciato su Nn (grrevlex) per cui α > β se |α| > |β| in N, oppure|α| = |β| e esiste un indice 1 ≤ j0 ≤ n tale che j > j0 ⇒ αj = βj e αj0 < βj0 (ovvero si inverte l’ordinelessicografico a partire dall’ultima componente).

(c) Piu in generale, l’ordinamento lessicografico definisce un ordinamento totale nel gruppo Zn ed ognisottomonoide finitamente generato da elementi maggiori di 0 = (0, . . . , 0) viene ad essere bene-ordinato.Possiamo quindi definire un buon ordinamento monomiale su Nn fissando una matrice A ∈ Mn(Z), condetA 6= 0, e tale che le colonne αj = (a1j , . . . , anj) > 0 in Zn. Infatti, data una tale matrice A, si poneβ ≤A γ se, e solo se, Aβ ≤ Aγ nell’ordine lessicografico. Ad esempio, prendendo le matrici

A =

1 1 ... 1

1 0 ... 0

0. . . 0

0 ... 1 0

B =

( 1 1 ... 1

0 0 ... −10 . .

.0

0 −1 ... 0

)

si ritrovano, rispettivamente, l’ordine grado-lessicografico sui monomi e l’ordine grado-lessicografico rove-sciato. Nelle applicazioni, quest’ultimo si rivela spesso molto utile nel ridurre i tempi di calcolo ed e usatocome default nel software Macaulay .(d) Dato un ordine totale in un insieme, x ≤ y, si puo definire l’ordinamento inverso, ponendo per definizionex ≤inv y se, e solo se, y ≤ x. In questo modo si ottiene un nuovo ordinamento totale sull’insieme, ma nonc’e alcun motivo per cui si abbia un buon ordinamento quando lo era quello di partenza. Ad esempio, seinvertiamo l’ordinamento lessicografico su N2, l’insieme { (n, 0) |n ∈ N } non ha un elemento minimo. Pero suun insieme finito ogni ordinamento totale e un buon ordinamento. Quindi si puo considerare (ad esempio) lacombinazione del grado e dell’inverso dell’ordine lessicografico su ciascun sottoinsieme di monomi dello stessogrado. Anche in questo modo si ottiene un buon ordinamento monomiale nell’anello dei polinomi chiamatotalvolta ordine grado-lessicografico inverso. Se l’autore non si e imbrogliato da solo, questo ordinamentocorrisponde alla scelta della matrice

C =

1 1 ... 1

−1 0 ... 0

0. . . 0

0 ... −1 0

.

(†) Ricordiamo che una relazione d’ordine, x ≤ y, in un insieme e una relazione riflessiva (x ≤ x), antisimmetrica (x ≤ y, y ≤x ⇒ x = y) e transitiva (x ≤ y, y ≤ z ⇒ x ≤ z). L’ordine e totale se ogni coppia di elementi dell’insieme e confrontabile. Si

parla di buon ordinamento se ogni sottoinsieme non vuoto ha un elemento minimo.(∗) In queste righe e nel seguito, abbiamo identificato un buon ordinamento dei multi-indici in Nn con un buon ordinamento

dei monomi di C[X1, . . . , Xn], identificando α ∈ Nn con il monomio Xα. In alcuni testi questa corrispondenza viene indicata

come il logaritmo dei monomi, e si scrive α = logXα.

3

Si mette in guardia il lettore che, a volte, quest’ordine viene scambiato con l’ordine grado lessicograficorovesciato, di cui condivide molte proprieta.

Osservazione. Sia fissato un buon ordinamento monomiale sui monomi di C[X1, . . . , Xn]. Allora

(a) 1 e il minimo di tutti i monomi.

(b) Se Xα divide Xβ , allora Xα ≤ Xβ .

dim. (a) Se fosse Xα < 1 = X0 per qualche multi-indice α, moltiplicando entrambo i termini per Xα

avrei X2α ≤ Xα e continuando analogamente, otterrei una catena discendente infinita e quindi l’insieme{Xnα |n ∈ N } non avrebbe un minimo.

(b) Se Xβ = XαXµ per qualche monomio Xµ. Dalla relazione Xµ ≥ 1, dimostrata sopra, si ricava Xβ ≥ Xα,moltiplicando entrambo i termini per Xα. �

Possiamo rafforzare l’osservazione precedente in un criterio utile per riconoscere i buoni ordinamentimonomiali.

Osservazione. Sia dato un ordine totale sui monomi di C[X1, . . . , Xn] che soddisfa alla condizione Xα <Xβ ⇒ XαXγ < XβXγ , per ogni scelta di Xα, Xβ , Xγ . Allora, l’ordine e un buon ordinamento monomiale(term-ordering) se, e solo se, 1 e il minimo di tutti i monomi.

dim. L’osservazione precedente dice che la condizione e necessaria affinche si abbia un buon ordinamento.Viceversa, dato un insieme non vuoto di monomi, A, sia IA l’ideale monomiale di C[X1, . . . , Xn] generatodagli elementi di A. Per il Lemma di Dickson, IA e generato da un numero finito di monomi, che possiamoporre in ordine crescente: Xα1 < · · · < Xαs . Ogni, monomio Xβ ∈ A e divisibile per qualcuno dei generatoridi IA e quindi si ha

Xβ = XαiXγ > Xαi1 = Xαi ≥ Xα1 ;

e quindi Xα1 e il minimo di A. �

Definizione. Sia fissato un buon ordinamento monomiale sui monomi di C[X1, . . . , Xn]. Dato un polinomiof =

∑α cαX

α, si definiscono

• il monomio direttivo (leading monomial) LM(f) = max {Xα | cα 6= 0 };• il termine direttivo (leading term) LT (f) = cαX

α, quando Xα = LM(f);

• il coefficiente direttivo (leading coefficent) LC(f) = cα, quando Xα = LM(f).

Dato un qualsiasi ideale I di C[X1, . . . , Xn] gli si puo associare l’ideale monomiale LM(I) = (LM(f) | f ∈ I ),generato dai monomi direttivi di tutti gli elementi di I.

Invitiamo il lettore a far attenzione al fatto che, in generale, se I = (f1, . . . , fr) e l’ideale generatodai polinomi f1, . . . , fr non e vero che LM(I) sia l’ideale generato da LM(f1), . . . , LM(fr). Un facilecontroesempio e dato dall’ideale I = (X,X + 1) in C[X], che e l’deale banale (1) e coincide quindi l’idealemonomiale associato, ma LM(X + 1) = X = LM(X), per cui l’ideale generato dai monomi direttivi deigeneratori e uguale a (X) 6= (1).

4

4. Algoritmo di divisione e Basi di Grobner

Possiamo quindi introdurre il cosiddetto algoritmo di divisione che ci portera al concetto di Base diGrobner di un ideale di C[X1, . . . , Xn].

Definizione. [Algoritmo di divisione] Sia fissato un buon ordinamento monomiale su C[X1, . . . , Xn] e sianodati l’ideale J di C[X1, . . . , Xn] generato dai polinomi f1, . . . , fr ed un polinomio g ∈ C[X1, . . . , Xn]. Sipone g0 = g. Quindi, dato il polinomio gn, per n ≥ 0, se qualcuno tra i monomi direttivi di f1, . . . , fr, siaLM(fi), divide il monomio direttivo di gn, si pone

gn+1 = gn −LT (gn)

LT (fi)fi

e l’algoritmo si arresta al passo N , se gN = 0 oppure se LM(gN ) /∈ (LM(f1), . . . , LM(fr)).Il termine gN e anche detto il resto dell’algoritmo di divisione.

L’algoritmo si arresta certamente dopo un numero finito di passi perche si ha LM(g0) > LM(g1) >LM(g2) > · · · e l’insieme di questi monomi deve avere un elemento minimo. Se l’algoritmo si arresta quandogN = 0, allora ognuno dei termini gn si scrive come combinazione dei generatori f1, . . . , fr dell’ideale J equindi g ∈ J . Pero, se il procedimento termina con un resto gN 6= 0 non posso concludere che g /∈ J , masolo che LM(g) /∈ (LM(f1), . . . , LM(fr)). L’esempio di f1 = X, f2 = X + 1 e g = 1 in C[X], ci fa vedereche l’algoritmo si arresta al passo 0, con resto g0 = 1, pur avendosi (1) = (f1, f2).

Introduciamo quindi dei particolari insiemi di generatori degli ideali di C[X1, . . . , Xn] che rendanoeffettivo l’algoritmo di divisione per poter decidere se un polinomio g appartiene o no ad un ideale.

Definizione. Sia fissato un buon ordinamento monomiale su C[X1, . . . , Xn] e sia J un ideale di C[X1, . . . , Xn].I polinomi f1, . . . , fr di J sono una base di Grobner per J se LM(J) = (LM(f1), . . . , LM(fr)).

Proposizione. Sia fissato un buon ordinamento monomiale su C[X1, . . . , Xn] e sia f1, . . . , fr una base diGrobner per J . Allora, J = (f1, . . . , fr).

dim. Possiamo utilizzare l’algoritmo di divisione ed osservare che, dato un polinomio g, se l’algoritmo siarresta con gN = 0, allora g appartiene all’ideale generato da (f1, . . . , fr) ed e quindi contenuto in J . Se,invece, l’algoritmo si arresta con gN 6= 0, allora LM(g) /∈ (LM(f1), . . . , LM(fr)) = LM(J) e quindi g /∈ J .

�

Oltre ad osservare come una base di Grobner, f1, . . . , fr, renda effettivo l’algoritmo di divisione perdecidere se un elemento appartiene o meno all’ideale generato da f1, . . . , fr; possiamo affermare che ogniideale I di C[X1, . . . , Xn] ammette una base di Grobner. Infatti, per il Lemma di Dickson, l’ideale LM(I)ha un insieme finito di generatori e quindi per ottenere una base di Grobner per I, e sufficiente scegliere(arbitrariamente) dei polinomi di I che abbiano come monomio direttivo gli elementi di un insieme digeneratori di LM(I). Possiamo quindi enunciare il seguente

Corollario. Ogni ideale di C[X1, . . . , Xn] e finitamente generato, ovvero C[X1, . . . , Xn] e un anello noethe-riano.

Osservazione. Sia fissato un buon ordinamento monomiale su C[X1, . . . , Xn] e sia I un ideale. Una base di Grobner ridottaper I e una base di Grobner f1, . . . , fr dell’ideale che soddisfa alle ulteriori proprieta(R1) LT (fi) = LM(fi) per ogni i = 1, . . . , r (ovvero, il coefficiente direttivo e uguale ad 1);(R2) se i 6= j nessun monomio di fj e divisibile per LM(fi).

Una base di Grobner ridotta esiste per ogni ideale di C[X1, . . . , Xn] ed e unica. Infatti, data una base di Grobner, f1, . . . , fr perl’ideale I, dividiamo ciascuno dei polinomi per il coefficiente direttivo, in modo che sia soddisfatta la condizione (R1). Inoltre,possiamo supporre di avere ordinato i polinomi, in modo che LM(f1) ≤ LM(f2) ≤ · · · ≤ LM(fr). Se due elementi hanno lostesso monomio direttivo, possiamo eliminare uno dei due, sapendo che i rimanenti sono ancora una base di Grobner per I (cioei loro monomi direttivi generano ancora LM(I)). Possiamo quindi supporre che i monomi direttivi di f1, . . . , fr siano tutti

distinti. Se uno dei termini di f2 =∑

cαXα, sia cδXδ, e divisibile per LM(f1) posso sostituire f2 con f2 = f2 − cδX

δ

LM(f1)f1,

ed avere ancora una base di Grobner di I. Posso ripetere l’operazione con tutti i termini di f2 divisibili per LM(f1) e quindi,proseguendo ricorsivamente, posso supporre che la condizione (R2) sia soddisfatta per i generatori, f1, . . . , fi e considerare i

5

termini di fi+1 divisibili per qualcuno dei monomi direttivi dei generatori precedenti. Posso eliminare questi monomi dallascrittura di fi+1, continuando ad avere una base di Grobner per I e quindi, dopo un numero finito di passi arrivo ad ottenereuna base di Grobner ridotta per I.

Per vedere che una tale base e unica, supponiamo di avere due basi di Grobner ridotte, f1, . . . , fr e g1, . . . , gs, e supponiamodi avere LM(f1) < LM(f2) < · · · < LM(fr) e LM(g1) < LM(g2) < · · · < LM(gs). Se fosse LM(f1) < LM(g1), LM(f1)non potrebbe appartenere ad (LM(g1), . . . , LM(gs)) = LM(I) e quindi, deve essere necessariamente LM(f1) = LM(g1). Perlo stesso motivo, se f1 − g1 6= 0, il monomio direttivo LM(f1 − g1) non potrebbe appartenere ad LM(I) e quindi deve esseref1 = g1. Supponiamo allora fi = gi per i = 1 . . . , k e osserviamo che, se fosse LM(fk+1) < LM(gk+1), LM(fk+1) nonpotrebbe appartenere ad (LM(g1), . . . , LM(gs)) = LM(I), perche non potrebbe essere divisibile per nessuno dei generatori.Quindi, deve essere necessariamente LM(fk+1) = LM(gk+1). Per lo stesso motivo, se fk+1 − gk+1 6= 0, il monomio direttivoLM(fk+1 − gk+11) non potrebbe appartenere ad LM(I) perche minore di LM(fk+1 e non divisibile per nessuno dei monomidirettivi dei precedenti, essendo fk+1 e gk+1 parte di una base di Grobner ridotta. Quindi deve essere fk+1 = gk+1 e si completail ragionamento per induzione.

5. Forma normale

Dato un ideale I di R = C[X1, . . . , Xn], nella sezione precedente abbiamo visto l’importanza dell’idealemonomiale LM(I) = (LM(f) : f ∈ I) per determinare dei sistemi di generatori per I. Vogliamo mostrarel’importanza di quell’ideale monomiale per descrivere gli elementi dell’anello quoziente R/I. Mostreremo chei monomi non appartenenti a LM(I) formano una base di R/I come spazio vettoriale su C (talvolta dettala base di Macaulay di R/I).

Proposizione. Sia fissato un buon ordinamento monomiale in R = C[X1, . . . , Xn] e sia I un ideale di R.Ogni polinomio g ∈ R ha un’unica scrittura della forma

g ≡∑

Xα /∈LM(I)

cαXα (mod I),

ove cα ∈ C e solo un numero finito di coefficienti e diverso da 0. Chiameremo questa scrittura la formanormale per g modulo I.

dim. Per stabilire che una tale scrittura esiste per ogni polinomio, consideriamo l’insieme dei monomi direttividi polinomi g che non ammettono una scrittura del tipo descritto. Se questo insieme non e vuoto deveammettere un elemento minimo Xβ e deve quindi esistere un polinomio g che non ha una tale scrittura conLT (g) = LM(g) = Xβ . Facciamo vedere che cio porta comunque ad una contraddizione. Infatti, se per casoXβ ∈ LM(I), sia h ∈ I con LT (h) = LM(h) = Xβ e consideriamo g = g−h. Ora g ≡ g (mod I) e LM(g) <LM(g). Per la minimalita di Xβ , g dovrebbe avere una forma normale, ma questa dovrebbe essere una formanormale anche per g e cio e assurdo. Supponiamo allora che Xβ /∈ LM(I), allora LM(g −Xβ) < LM(g) equindi, per la minimalita di LM(g), deve esserci una forma normale per g −Xβ ≡

∑Xα /∈LM(I) cαX

α, ma

sommando il monomio Xβ ai due membri dell’uguaglianza, si otterrebbe una forma normale per g, controle ipotesi. Quindi l’insieme dei polinomi che non ammettono una forma normale deve essere vuoto.

Per stabilire che una tale scrittura e unica, si puo ragionare cosı: supponiamo di avere

g ≡∑

Xα /∈LM(I)

cαXα ≡

∑Xα /∈LM(I)

c′αXα (mod I),

e sia h =∑Xα /∈LM(I)(cα− c′α)Xα ∈ I. Se h avesse un solo coefficiente diverso da zero, avremmo che LM(h)

apparterrebbe ad LM(I), in quanto h ∈ I, ma tale monomio dovrebbe essere preso tra gli Xα /∈ LM(I), ilche e assurdo. �

Data una base di Grobner, f1, . . . , fr, dell’ideale I ed un polinomio g ∈ C[X1, . . . , Xn], possiamo definireun algoritmo per determinare la forma normale del polinomio g modulo I. Sia g0 = g. Se nessuno dei monomiche compare con coefficiente non nullo nella scrittura di gn appartiene a LM(I), abbiamo gia il polinomio

6

in forma normale. Altrimenti, sia cβXβ il piu grande monomio di LM(I) che compare nella scrittura di gn

e sia fi tale che LM(fi)|Xβ poniamo

gn+1 = gn − cβXβ

LT (fi)fi.

In tal modo si ha una sequenza strettamente decrescente di monomi di LM(I) che compaiono nella scritturadei vari gn. Poiche i monomi sono bene ordinati, la successione deve arrestarsi dopo un numero finito dipassi e l’algoritmo ha termine con la forma normale di g.

Esempio. Si consideri il polinomio f(X,Y ) = X4 + X2Y 2 + Y 3 − X3 in C[X,Y ] e l’ideale I = (f, ∂f∂X

, ∂f∂Y

) (se si pensa

ad f come all’equazione di una curva piana, gli zeri dell’ideale I corrispondono ai punti singolari della curva). Una basedi Grobner per I e data dai monomi X2, Y 2 (solo l’origine e punto singolare). La dimensione (come spazio vettoriale) suC dell’anello B = C[X,Y ]/I e uguale a 4, perche ogni polinomio si scrive in forma normale modulo I come combinazionedei monomi che non stanno in LM(I) = (X2, Y 2), ovvero 1, X, Y,XY . Indichiamo con x = X + I ed y = Y + I le classiresto modulo I. Si vede facilmente che nell’anello B tutti gli elementi che non stanno nell’ideale (x, y) sono invertibili [infatti(1 + ax+ by+ cxy)−1 = 1− ax− by+ (2ab− c)xy, come si verifica con un calcolo diretto]. Quindi B e un anello locale, che hacome unico massimale l’ideale m = (x, y) i cui elementi sono tutti nilpotenti. In particolare, m2 = (xy) 6= (0) = m3.

6. Criterio di Buchberger

Dato un insieme di generatori, f1, . . . , fr di un ideale J di C[X1, . . . , Xn], il criterio di Buchbergerfornisce un procedimento effettivo per poter decidere se i generatori dati sono una base di Grobner per J e,in caso negativo, una tecnica per poter completare i generatori dati ad una base di Grobner.

Osserviamo dapprima che dei polinomi f1, . . . , fr non sono una base di Grobner se esiste un polinomioh = h1f1 + · · · + hrfr tale che LM(h) /∈ (LM(f1), . . . , LM(fr)). In particolare, perche cio possa accadere,deve essere LT (h) 6= LT (hifi) per ogni i = 1, . . . , r e quindi devono esistere almeno due indici diversi, i0 ej0 tali che

LM(hi0fi0) = LM(hj0fj0) = Xδ = max {LM(hifi) | i = 1, . . . , r }

e inoltre deve aversi LM(h) < Xδ.

Definizione. [S-polinomio] Dati due polinomi non nulli, f1 ed f2 in C[X1, . . . , Xn], l’S-polinomio dellacoppia (f1, f2) e

S = S(f1, f2) =Xγ

LT (f1)f1 −

Xγ

LT (f2)f2,

ove Xγ = lcm(LM(f1), LM(f2)).

Sia S l’S-polinomio di (f1, f2); in particolare, si ha LM(S) < Xγ = lcm(LM(f1), LM(f2)). Inoltre, sepossiamo scrivere S come combinazione di f1, . . . , fr tramite l’algoritmo di divisione (cioe se produce resto0), allora si ha S =

∑rj=1 h(1, 2)jfj , con LM(h(1, 2)jfj) ≤ LM(S) < Xγ .

La relazione tra gli S-polinomi e la questione posta all’inizio di questa sezione e il contenuto del seguente

Teorema. [Criterio di Buchberger] Sia fissato un ordinamento monomiale su C[X1, . . . , Xn] e siano dati ipolinomi f1, . . . , fr. Sono equivalenti(a) f1, . . . , fr e base di Grobner per l’ideale I = (f1, . . . , fr).(b) ogni S-polinomio di coppie (fi, fj) dei generatori dati da resto 0 nell’algoritmo di divisione.

dim. (a)⇒(b). Dato che il polinomio S(fi, fj) appartiene all’ideale generato da fi ed fj ed e quindi contenutoin I, otterremo resto 0 nell’algoritmo di divisione avendo preso una base di Grobner dell’ideale I.

(b)⇒(a). Se, per assurdo, i polinomi f1, . . . , fr non fossero una base di Grobner per I, esisterebbe unpolinomio h tale che

h = h1f1 + · · ·+ hrfr e LM(h) /∈ (LM(f1), . . . , LM(fr)).

7

Posto Xδ = max {LM(fjhj) | j = 1, . . . , r }, possiamo supporre di aver scelto h e la sua scrittura in modoche

1) il monomio Xδ sia minimale;2) il numero di indici j tali che LM(fjhj) = Xδ sia minimo.

Vogliamo mostrare che tutto cio ci porta ad una contraddizione.A meno di riordinare gli indici, possiamo supporre che

LM(f1h1) = LM(f2h2) = · · · = LM(fmhm) = Xδ > LM(fjhj), per j ≥ m ≥ 2.

Scritto S = S(f1, f2) S =∑rj=1 h(1, 2)jfj , con LM(h(1, 2)jfj) ≤ LM(S) < Xγ = lcm(LM(f1), LM(f2)),

tramite l’algoritmo di divisione (che da resto 0, per ipotesi), possiamo scrivere

0 =Xγ

LT (f1)f1 −

Xγ

LT (f2)f2 −

r∑j=1

h(1, 2)jfj ove Xγ > LM(S) ≥ LM(h(1, 2)jfj), per ogni j = 1, . . . , r.

Osserviamo che Xδ = LM(f1h1) = LM(f2h2) e un multiplo comune dei monomi direttivi LM(f1) edLM(f2) e quindi e divisibile per il loro comune multiplo; ovvero esiste un monomio Xµ tale che XµXγ = Xδ.Moltiplicando tutti i termini della somma qui sopra per LC(h1)Xµ e sottraendoli termine a termine allascrittura di h, si ottiene h = h1f1 + · · · + hrfr, ove Xδ ≥ LM(hjfj) per ogni j e la disuguaglianza vale in

senso stretto per j > m e per j = 1. Quindi il numero di indici per cui vale l’uguaglianza Xδ = LM(hjfj) ediminuito strettamente, contro l’ipotesi che si trattasse di una scelta minimale. La contraddizione discendedall’aver supposto che i polinomi f1, . . . , fr non fossero una base di Grobner. �

Quanto dimostrato nel teorema precedente, ci permette di concludere che, se i polinomi dati, f1, . . . , frnon sono una base di Grobner per l’ideale I = (f1, . . . , fr), possiamo aggiungere ai generatori dati gliS-polinomi che non danno resto 0 nell’algoritmo di divisione, ottenendo un nuovo insieme di generatorig1, . . . , gs dell’ideale I. Se ancora vi sono S-polinomi di questo nuovo insieme di generatori che danno unresto diverso da 0, li aggiungiamo ai generatori dell’ideale ed otteniamo un nuovo insieme di generatorih1, . . . , ht dell’ideale I. Gli ideali monomiali

(LM(f1), . . . , LM(fr)) ⊂ (LM(g1), . . . , LM(gs)) ⊂ (LM(h1), . . . , LM(ht)) ⊂ · · ·formano una catena ascendente (tutta contenuta in LM(I)) che deve arrestarsi dopo un numero finito dipassi (Lemma di Dickson), fornendo cosı una base di Grobner per I.

7. Un esempio

Consideriamo l’ideale I = (f1, f2) con f1 = X21 −X2 ed f2 = X3

1 −X3), nell’anello C[X1, X2, X3] con i monomi ordinatisecondo l’ordine lessicografico. Si ha

S(f1, f2) = X1f1 − f2 = X3 −X1X2, con LM(S) = X1X2 /∈ (LM(f1), LM(f2)) = (X21 ).

Quindi poniamo f3 = S(f1, f2) = X3 −X1X2 e consideriamo gli S-polinomi

S(f1, f3) = X2f1 −X1f3 = −X22 +X1X3, S(f2, f3) = X2f2 −X2

1f3 = X21X3 −X2X3 = X3f1.

Si ha LM(S(f1, f3)) = X1X3 /∈ (LM(f1), LM(f2), LM(f3)) = (X21 , X1X2). Quindi dobbiamo aggiungere anche il polinomio

f4 = S(f1, f3) = −X22 +X1X3, ma non S(f2, f3). Dobbiamo considerare anche gli S-polinomi

S(f1, f4) = X3f1 −X1f4 = X1X22 −X2X3 = X2f3,

S(f2, f4) = X3f2 −X21f4 = X2

1X22 −X

23 = (X1X2 +X3)f3,

S(f3, f4) = X3f3 −X2f4 = X32 −X

23 .

Si ha LM(S(f3, f4)) = X32 /∈ (LM(f1), . . . , LM(f4)) = (X2

1 , X1X2, X1X3). Quindi dobbiamo aggiungere anche il polinomio

f5 = S(f3, f4) = X32 −X

23 e considerare gli S-polinomi

S(f1, f5) = X32f1 −X

21f5 = −X4

2 +X21X

23 = (X1X3 +X2

2 )f4,

S(f2, f5) = X32f2 −X

31f5 = −X3

2X3 +X31X

23 = X2

1X3f3 +X2X3f1,

S(f3, f5) = X22f3 −X1f5 = −X2

2X3 +X1X23 = X3f4,

S(f4, f5) = X32f4 −X1X3f5 = X1X

33 −X

52 = X2

3f4 −X22f5.

Si conclude che f1, . . . , f5 e base di Grobner di I e che f2 si puo eliminare dalla base perche il suo monomio direttivo e contenutonell’ideale generato dai monomi direttivi degli altri elementi della base.

8

8. Un’applicazione

Diamo un esempio dell’uso delle basi di Grobner per decidere come colorare (se possibile) i vertici di un grafo con 3 colori,

in modo che ogni coppia di vertici congiunta da un lato abbia colori distinti. E subito chiaro che tale colorazione puo nonesistere: come si puo vedere facilmente prendendo i quattro vertici di un quadrato, congiunti dai lati e dalle diagonali (i primitre vertici devono avere colori a due a due distinti e per colorare il quarto vertice dovrebbe esserci un quarto colore).

Il grafo qui sotto, ammette invece una colorazione del tipo voluto, come si vede nel disegno a fianco e diamo una rapidadescrizione di come e stato possibile calcolarla usando CoCoA.

P1

P2

P3

P4

P5

P6

P7

P8

P9

P1

P2

P3

P4

P5

P6

P7

P8

P9

Identifichiamo i tre colori con gli elementi del campo F3 = Z/3Z; ad esempio,

0 = rosso, 1 = verde, −1 = blu,

come abbiamo fatto nell’esempio qui sopra. Consideriamo l’anello dei polinomi R = F3[X1, . . . , X9], ove vi e un’indeterminataper ogni vertice del grafo. Una colorazione dei vertici del grafo costituisce un punto (x1, . . . , x9) nell’insieme degli zeri di unideale I di R, generato da polinomi che codifichino le due condizioni

(a) che x1, . . . , x9 siano nel campo F3;(b) che xi 6= xj quando i vertici corrispondenti sono congiunti da un lato.

Affinche gli zeri siano nel campo primo dobbiamo mettere in I i polinomi X3i −Xi per i = 1, . . . , 9. Se due vertici congiunti

da un lato dobbiamo imporre la condizione xi− xj 6= 0, ovvero che la coppia (xi, xj) sia uno zero del polinomio (Xi−Xj)2− 1

(gli elementi diversi da zero di F3 soddisfano all’equazione X2 = 1). Dunque, dobbiamo aggiungere all’ideale I il polinomioX2i + X2

j + XiXj − 1 per ogni coppia di vertici (Pi, Pj) congiunta da un lato. Nel caso in questione, abbiamo 19 lati di cuitener conto.

Inoltre, possiamo attribuire ad arbitrio il colore ad una coppia di punti (congiunti): x1 = 0 ed x2 = 1, come nell’esempiosopra. Cio consente di aggiungere i polinomi X1 ed X2 − 1 all’ideale I.

Una base di Grobner per l’ideale (nell’ordine grado-lessicografico rovesciato, che e il default di CoCoA), e quindi uguale a

X1, X2 − 1, X3 + 1, X4, X5, X6 − 1, X7 + 1, X8 − 1, X9 + 1.

Vi e quindi un’unica colorazione soddisfacente alle condizioni poste (e quindi un’unica colorazione, a meno di permutazioni deicolori). Riportiamo qui sotto le istruzioni utilizzate per calcolare la base di Grobner con CoCoA (v. 4.7)

V:=9;Use S::=ZZ/(3)[x[1..V]]; -- polinomi in V indeterminate a coeff in Z/3ZSet Indentation; -- per scrivere su righe distinte i polinomi calcolatiLati:=[[1,2],[1,3],[1,6],[1,9],[2,3],[2,4],[2,7],[3,4],[3,5],

[4,6],[4,7],[4,8],[5,6],[5,7],[5,9],[6,7],[6,9],[7,8],[8,9]];

L:=[x[H]^3-x[H] | H In 1..V ];J:=Ideal(L);N:=Len(Lati);M:=[x[Lati[H,1]]^2+x[Lati[H,2]]^2+x[Lati[H,1]]x[Lati[H,2]]-1 | H In 1..N ];I:=Ideal(M);CC:=I+J+Ideal(x[1],x[2]-1);G:=GBasis(CC);G;

Chi avesse provato a calcolare in modo analogo la colorazione corrispondente al grafo costituito dai quattro vertici diun quadrato, i lati e le due diagonali (lati, [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]) avrebbe ottenuto come base di Grobner il solopolinomio 1, essendo banale l’ideale generato dalle relazioni.

Osserviamo infine che, nel caso in cui siano possibili diverse colorazioni (e non solo permutazioni nella scelta dei colori), al-cuni dei polinomi della base di Grobner potrebbero avere grado maggiore di uno e quindi zeri distinti. Inoltre, la scelta arbitrariadi fissare i colori agli estremi del primo lato potrebbe ridurre il numero delle possibili soluzioni. A questo proposito si suggerisce dianalizzare quanto si ottiene “colorando” il grafo di lati [1, 2], [1, 4], [2, 3], [2, 5], [2, 6], [2, 7], [3, 4], [3, 7], [4, 5], [4, 6], [4, 7], [5, 7], [6, 7](provare a farsi una figura!) e quelli che si possono ottenere dopo qualche permutazione dei vertici.

9

Ottimizzazione del resto. Un altra applicazione delle basi di Grobner si puo trovare nel problema di calcolare il numerominimo di monete necessario per comporre una prefissata quantita. Ad esempio (utilizziamo le frazioni di dollaro, visto cheil problema e stato posto cosı originariamente), avendo a disposizione pennies (p), nickels (n = 5p), dimes (d = 2n = 10p), equarters (q = 5n = 25p) come comporre la cifra di $1.17 (117 pennies) con il numero minimo di monete? Si possono usare lebasi di Grobner, nel modo seguente: si considera una variabile per ogni tipo di moneta e quindi l’anello R = Q[p, n, d, q] doveogni somma va a comporre un monomio i cui esponenti corrispondono al numero di monete di ciascun tipo e si pone l’ordinegrado-lessicografico, per cui un minimo tra i monomi che esprimono la stessa somma e composto col numero minimo di monete. Irapporti di cambio generano l’ideale I = (n−p5, d−p10, q−p25), una cui base di Grobner e −d+n2,−d3 +nq, d2n−q,−n+p5.La somma di $1.17 corrisponde, ad esempio, al monomio p17n10d5q0 che ha forma normale p2dnq4 in R/I e questa e unadecomposizione con il numero minimo di monete.

Ovviamente, si puo formalizzare l’analogo problema per le monete in euro, ovvero con le variabili a1, a2, a5, a10, a20,a50, a100, a200, corrispondenti alle monete da 1, 2, 5, 10, 20, 50 eurocent e da 1 e 2 euro e con il corrispondente ideale.

9. Sizigie

Dato un ideale I = (f1, . . . , fr) in A = C[X1, . . . , Xn], resta definito un omomorfismo (di A-moduli)f : Ar → A, ove f(h1, . . . , hr) = h1f1 + · · · + hrfr, la cui immagine e l’ideale I. Il nucleo, kerf , e unsottomodulo di Ar detto il modulo delle sizigie di f1, . . . , fr, che talvolta si indica col simbolo Syz(f1, . . . , fr).Poiche A e un anello noetheriano, il modulo Ar e anch’esso noetheriano e quindi il modulo delle sizigie e unA-modulo finitamente generato.

Per vedere che An e un modulo noetheriano si puo utilizzare il seguente fatto

Lemma. Sia R un anello commutativo e siano M un R-modulo ed N un suo sottomodulo. Allora M enoetheriano se, e solo se, N ed M/N sono noetheriani.

dim. Sia M un modulo noetheriano (cf. §.1). Ogni sottomodulo di N e, in particolare un sottomodulo diM e quindi e finitamente generato, per cui N e anch’esso noetheriano. D’altra parte, ogni sottomodulo diM/N e immagine omomorfa di un sottomodulo di M contenente N . Le proiezioni canoniche dei generatoridi questo sottomodulo generano l’immagine in M/N e quindi anche M/N e noetheriano.

Viceversa, se N ed M/N sono noetheriani, preso un qualsiasi sottomodulo K di M , la sua immagine inM/N e finitamente generata e quindi esistono degli elementi, x1, . . . , xt tali che, preso comunque, m ∈ K,esistono a1, . . . , at ∈ R tali che m−a1x1−. . .−atxt appartenga ad N e sia quindi combinazione dei generatoridi N , che sono in numero finito. Quindi K e finitamente generato ed M e noetheriano. �

Grazie al Lemma precedente ed al fatto che l’anello A = C[X1, . . . , Xn] e noetheriano, e sufficienteosservare che l’identificazione di A con l’ultima componente di An+1 determina un isomorfismo tra An+1/Ae An e permette cosı di dimostrare, per induzione su n, che An e noetheriano.

Se un ideale di A e generato da monomi, Xα1 , . . . , Xαr , il modulo delle sizigie Syz(Xα1 , . . . , Xαr ) egenerato dalle relazioni del tipo Xγ−αiXαi −Xγ−αjXαj , per 1 ≤ i < j ≤ r, ove Xγ = Xγ(i,j) e il minimocomune multiplo dei due monomi Xαi e Xαj , perche i monomi formano una base su C dello spazio vettorialeC[X1, . . . , Xn]. La dimostrazione del Criterio di Buchberger, porta come conseguenza che il modulo dellesizigie di una base di Grobner, f1, . . . , fr, di un ideale I e generato dalle relazioni

Xγ

LT (fi)ei −

Xγ

LT (fj)ej −

r∑k=1

h(i, j)kek, ove Xγ = lcm(LM(fi), LM(fj)),

e1, . . . , er e la base canonica di Ar ed S(fi, fj)−∑rk=1 h(i, j)kfk = 0 e la relazione che si ottiene applicando

l’algoritmo di divisione all’S-polinomio S(fi, fj) = Xγ

LT (fi)fi − Xγ

LT (fj)fj , per 1 ≤ i < j ≤ r. Infatti, si puo

ripetere l’argomento usato nella dimostrazione del criterio, supponendo di avere una relazione∑rk=1 hkfk = 0,

con Xδ minimale tale che Xδ = LM(fihi) = LM(hjfj) ≥ LM(hkfk), per k = 1, . . . , r; e con un numerominimale di addendi per cui Xδ = LM(hkfk). Come si e visto nella dimostrazione detta, supporre che nonsia ottenuta nel modo descritto, porta ad una contraddizione con la minimalita.

10

10. Il Teorema degli zeri di Hilbert

Dato un sottoinsieme, S ⊆ An(C), possiamo considerare l’insieme I(S) = { f ∈ R | f(P ) = 0, ∀P ∈ S },che e un ideale di R = C[X1, . . . , Xn]. Viceversa, dato un insieme di polinomi F ⊆ R, possiamo considerareil sottoinsieme V (F ) = {P ∈ An(C) | f(P ) = 0, ∀f ∈ F }. E chiaro che, se I = (F ) e l’ideale generato da F ,allora V (F ) = V (I). Ad esempio, si ha V (1) = V (R) = ∅, V ((0)) = An(C) e, se P = (a1, . . . , an) ∈ An(C),allora I({P}) = (X1 − a1, . . . , Xn − an).

I sottoinsiemi del tipo V (I), al variare di I tra gli ideali di R, sono i chiusi di una topologia nello spazioaffine detta la topologia di Zariski. Infatti, ∅ e An(C) sono tra questi chiusi e, presa una famiglia qualunquedi chiusi, V (Iα), con α ∈ A , si ha

⋂α∈A V (Iα) = V (I), ove I =

∑Iα e l’ideale generato dagli Iα (il piu

piccolo ideale che li contiene tutti). D’altra parte, dati due chiusi, V (I) e V (J), si ha V (I) ∪ V (J) = V (IJ)ove IJ e l’ideale generato dai prodotti fg con f ∈ I e g ∈ J .

Dato un sottoinsieme S di An(C), la sua chiusura sara l’insieme V (I(S)) ⊇ S e I(V (I(S))) = I(S).D’altra parte, V (I(V (I))) = V (I) per ogni ideale I di R, perche I(V (I)) ⊇ I e, se P /∈ V (I) esiste unpolinomio f ∈ I tale che f(P ) 6= 0. Ma, in generale, le relazioni tra un ideale I e l’ideale I(V (I)) possonoessere molto deboli. Ad esempio, nel piano affine reale, per entrambi gli ideali I1 = (X2 + Y 2 + 1) eI2 = (1), si ha V (I) = ∅ ⊂ A2(R) e quindi I(V (I)) = (1) = R[X,Y ], pur trattandosi di ideali diversi.Quando il campo C e algebricamente chiuso, ci sono delle relazioni piu strette tra I e I(V (I)) e questo eil contenuto del Nullstellensatz, o Teorema degli Zeri, di Hilbert. Il teorema ha diverse formulazioni traloro equivalenti che riportiamo qui sotto. Ricordiamo che, dato un ideale I di R, il radicale di I e l’ideale√I = rad(I) = { g ∈ R | gn ∈ I ∃n ≥ 1 } ed osserviamo che, se p e un ideale primo, allora rad(p) = p, perche

se p contiene un prodotto, allora deve contenere almeno uno dei fattori.

Teorema. [Nullstellensatz] Sia C un campo algebricamente chiuso e R = C[X1, . . . , Xn]; allora valgono leseguenti affermazioni, tra loro equivalenti.

(N1) Per ogni ideale I si ha I(V (I)) = rad(I).(N2) Ogni ideale massimale m in R e del tipo (X1 − a1, . . . , Xn − an) per qualche a = (a1, . . . , an) ∈ An(C).(N3) Se I e un ideale proprio di R (ovvero I 6= R), allora V (I) 6= ∅.

Mostriamo che i tre enunciati del Nullstellensatz sono equivalenti.(N1)⇒(N2) Sia m un ideale massimale. si ha I(V (m)) = rad(m) = m 6= R e quindi V (m) contiene almeno

un punto a = (a1, . . . , an) ∈ An(C) e quindi m e contenuto in I({a}) = (X1 − a1, . . . , Xn − an) e quindii due ideali devono coincidere per la massimalita.

(N2)⇒(N3) Se 1 /∈ I, allora I e contenuto in un ideale massimale, ovvero I ⊆ (X1 − a1, . . . , Xn − an) perqualche a = (a1, . . . , an) ∈ An(C) e quindi a ∈ V (I).

(N3)⇒(N1) Sia I = f1, . . . , fr). Chiaramente, si ha rad(I) ⊆ I(V (I)), perche, dato g ∈ radI e P ∈ V (I), siha gn(P ) = 0 per qualche n ≥ 1, e quindi g(P ) = 0. Supponiamo ora 0 6= g ∈ I(V (I)) e consideriamoil sottoinsieme V =

{(x1, . . . , xn, z) ∈ An+1(C) | zg(x1, . . . , xn) = 1

}e l’immagine U di V in An(C)

tramite la proiezione (x1, . . . , xn, z) 7→ (x1, . . . , xn). Allora, U = { (x1, . . . , xn) ∈ An(C) | g(x1, . . . , xn) 6= 0 }e quindi U ∩ V (I) = ∅, essendo g ∈ I(V (I)). Allora, per l’ideale J = (f1, . . . , fr, Zg) di S =C[X1, . . . , Xn, Z] si ha V (J) = ∅ e quindi 1 ∈ J , ovvero 1 = h1f1 + · · · + hrfr + k(Zg − 1), peropportuni polinomi h1, . . . , hr, k ∈ S. Posto Z = 1

g in ciascuno di questi polinomi si ha l’identita

1 = h1f1+···+hrfrgN

in C(X1, . . . , Xn), per opportuni polinomi h1, . . . , hr e per un opportuno esponente

N . dunque gN = h1f1 + · · ·+ hrfr ∈ I, e quindi g ∈ rad(I).Abbiamo dimostrato che i tre enunciati sono equivalenti, ma ci resta da provare che almeno uno di

questi e verificato su un campo algebricamente chiuso (ipotesi che, in realta, non abbiamo mai usato nelleverifiche precedenti). La dimostrazione di (N2) discende dal seguente Lemma, dovuto ad Oscar Zariski, chenon dimostreremo.

Lemma. [Zariski] Sia C un campo algebricamente chiuso ed F un campo contenente C e finitamentegenerato come C-algebra. Allora F = C.

Osserviamo che, dato un ideale massimale m in R = C[X1, . . . , Xn], il quoziente F = R/m e un campoed e generato su C dalle immagini delle indeterminate X1, . . . , Xn e quindi e finitamente generato come C-algebra. Per il Lemma di Zariski, F = C e quindi esistono degli scalari a1, . . . , an in C tali che Xi − ai ∈ m,per la massimalita m = (X1 − a1, . . . , Xn − an).

11

Nel caso particolare in cui C = C, il Lemma di Zariski si puo ottenere dall’osservazione che la tesi ecertamente vera se i generatori di F (come algebra) sono algebrici su C; perche C e algebricamente chiusoe quindi contiene tutti gli elementi di F algebrici su C. D’altro canto, F , come spazio vettoriale su C, egenerato dai monomi nei generatori di F come algebra e quindi da un insieme numerabile. Se F contenesseun elemento, z, non algebrico su C, allora si avrebbe z−a 6= 0 per ogni a in C e i quozienti 1

z−a formerebberouna famiglia non-numerabile, di elementi di F linearmente indipendenti su C. Il che e assurdo.

Fino a questo momento, le basi di Grobner non hanno fatto la loro comparsa in questa sezione. Illoro ruolo e giustificato da alcune conseguenze della discussione precedente che trovano modo di esprimersiattraverso le basi di Grobner.

Osservazione. Siano f1, . . . , fr in C[X1, . . . , Xn). Il sistema di equazioni

f1(X) = 0. . .fr(X) = 0

e privo di soluzioni

se, e solo se, 1 e base di Grobner ridotta di I = (f1, . . . , fr).

dim. Indicata con C la chiusura algebrica del campo C, diciamo che il sistema nell’enunciato non ha soluzionese V (I) = ∅ in An(C). Cio significa che I(V (I)) = rad(I) = (1) in C[X1, . . . , Xn) e quindi che 1 = 1n ∈ I.

�

Abbiamo quindi un criterio effettivo per decidere se un sistema di equazioni polinomiali ha o menosoluzioni. Il risultato seguente ci permette invece di capire se un polinomio si annulla in V (I), senza bisognodi calcolare esplicitamente gli elementi di questo insieme.

Osservazione. Sia I = (f1, . . . , fr) un ideale di C[X1, . . . , Xn). Il polinomio g appartiene a rad(I) se, esolo se, 1 e base di Grobner ridotta dell’ideale (f1, . . . , fr, Zg − 1) di C[X1, . . . , Xn, Z).

dim. Abbiamo visto nella dimostrazione dell’equivalenza tra le varie forme del Nullstellensatz, che l’ideale(f1, . . . , fr, Zg − 1) e privo di zeri quando g si annulla su tutti i punti di V (I). �

Riportiamo senza dimostrazione un ultimo fatto sui sistemi di equazioni polinomiali che ammettono unnumero finito di soluzioni.

Osservazione. Sia I = (f1, . . . , fr) un ideale di R = C[X1, . . . , Xn). V (I) e un insieme finito di punti (inAn(C)) se, e solo se, esiste un esponente, m, tale che Xm

j ∈ LM(I) per ogni i = 1, . . . ,m.

L’osservazione discende dal fatto che V (I) e un insieme finito se, e solo se, C[X1, . . . , Xn)/I e uno spaziovettoriale di dimensione finita su C e, per quanto visto sulla forma normale dei polinomi, la dimensione diquesto spazio coincide con il numero di monomi che non appartengono a LM(I).

12

11. Eliminazione

Cominciamo con l’esempio di un sistema di equazioni polinomiali. Sia I = (X21 +X2 +X3 − 1, X1 +X2

2 +X3 − 1, X1 +

X2 +X23 − 1) in R = Q[X1, X2, X3] e cerchiamo di determinare V (I). Se consideriamo l’ordine lessicografico (X1 > X2 > X3

e conseguenze di queste), possiamo sostituire i generatori dati con un base di Grobner dell’ideale, ovvero

X1 +X2 +X23 − 1, X2

2 −X2 −X23 +X3, 2X2X

23 +X4

3 −X23 , X

63 − 4X4

3 + 4X33 −X

23 .

Questi polinomi sono dei nuovi generatori dell’ideale I e quindi possiamo usare questi per determinare V (I). Pur avendo gradopiu elevato dei precedenti, presentano il grosso vantaggio di ridurre man mano il numero delle indeterminate effettivamentepresenti, per cui

X63 − 4X4

3 + 4X33 −X

23 = X2

3 (X3 − 1)2(X23 + 2X3 − 1)

e quindi le soluzioni (x1, x2, x3) ∈ V (I) devono avere x3 ∈ {0, 1,−1±√

2}. Sostituendo questi valori nei due polinomi precedenti,si ottengono i possibili valori di x2 e infine si determina x1. Quindi, salvo errori ed omissioni, si ha

V (I) = {(1, 0, 0), (0, 1, 0), (0, 0, 1), (−1−√

2,−1−√

2,−1−√

2), (−1 +√

2,−1 +√

2,−1 +√

2)}.

Questo procedimento non conduce in ogni caso ad una risoluzione del sistema di partenza, ma indica la possibilita di un

comportamento analogo alla tecnica di eliminazione nell’ambito dei sistemi di equazioni lineari (cosa si sarebbe potuto dire se

i generatori di I fossero stati polinomi di primo grado?). Cerchiamo di dare un’introduzione un po’ piu precisa dell’argomento.

Cerchiamo di descrivere geometricamente il procedimento di eliminazione di alcune tra le variabili.Supponiamo quindi di avere uno spazio affine An+m(C) e l’insieme V (I) degli zeri di un ideale I inC[X1, . . . , Xn, Y1, . . . , Ym] e consideriamo la proiezione π : An+m(C)→ Am(C) e il sottoinsieme W = πV (I)di Am(C). Il problema e di descrivere dei generatori di I(W ) in C[Y1, . . . , Ym] in termini dei generatori diI(V (I)). (Tutto cio nella speranza di ricavare dalla descrizione di W –o meglio della sua chiusura V (I(W ))–maggiori informazioni su V (I))

Proposizione. Sia V ⊆ An+m(C) una varieta affine e J = I(V ) in S = C[X1, . . . , Xn, Y1, . . . , Ym]. Seindichiamo con π : An+m(C) → Am(C) la proiezione π : (x1, . . . , xn, y1, . . . , ym) 7→ (y1, . . . , ym) e con Wl’immagine di V tramite π, allora si ha I(W ) = J ∩ C[Y1, . . . , Ym].

dim. Sia f in J ∩ C[Y1, . . . , Ym]. Se P ∈ W = π(V ), allora esiste un punto Q ∈ V tale che π(Q) = P ef(P ) = f(Q) = 0, perche f ∈ J = I(V ). Quindi J∩C[Y1, . . . , Ym] ⊆ I(W ). L’altra inclusione e evidente. �

Definizione. Un buon ordinamento monomiale in S = C[X1, . . . , Xn, Y1, . . . , Ym] e un ordine di eliminazioneper X1, . . . , Xn, se LM(f) ∈ C[Y1, . . . , Ym] implica f ∈ C[Y1, . . . , Ym].

Ad esempio, l’ordine lessicografico con X1 > X2 > · · · > Y1 > · · · > Yn e un ordine di eliminazione perX1, . . . , Xn. Piu in generale, dati due ordinamenti monomiali Xα >x X

γ per imonomi nelle X e Y β >y Yδ

per i monomi nelle Y , si puo definire l’ordine prodotto, ponendo

XαY β > XγY δ se Xα >x Xγ , oppure Xα = Xγ e Y β >y Y

δ.

Ad esempio, e un ordine di eliminazione per X1, . . . , Xn, il prodotto degli ordinamenti grado lessicograficorovesciato per le due variabili.

Le basi di Grobner si comportano bene rispetto all’eliminazione.

Proposizione. Sia J un ideale in S = C[X1, . . . , Xn, Y1, . . . , Ym] e sia fissato su S un ordine di eliminazioneper X1, . . . , Xn. Se f1, . . . , fr e base di Grobner per J nell’ordinamento dato, allora J ∩ C[Y1, . . . , Yn] egenerato dagli fj appartenenti a C[Y1, . . . , Ym].

dim. Supponiamo esista un polinomio in J ∩C[Y1, . . . , Yn], ma che non appartenga all’ideale generato daglifj nella base di Grobner che appartengono a C[Y1, . . . , Ym]. Avendosi un buon ordinamento tra i monomipossiamo anche supporre che LM(g) sia minimale tra i monomi direttive dei polinomi in questo insieme.Poiche f1, . . . , fr sono una base di Grobner, esiste uno degli fj con il monomio direttivo che divide il monomio

13

direttivo di g e quindi con LM(fj) ∈ C[Y1, . . . , Yn]. Per cui fj ∈ C[Y1, . . . , Yn]. Posto g = g− LT (g)LT (fj)

fj si ha

una contraddizione. �

Esempi. (a) Si consideri il sistema di equazioni algebriche{X + Y = aX2 + Y 2 = a3

X3 + Y 3 = a5

e ci chiediamo per quali valori di a il sistema abbia soluzione. Indicato con Z = V (I) l’insieme dellesoluzioni del sistema nelle tre incognite X,Y, a, possiamo considerare la proiezione π : A3 → A1 che manda(x, y, a) 7→ a, e la chiusura dell’insieme π(Z). Posto l’ordine in cui X > Y > a, di eliminazione per X,Y ; unabase di Grobner per I = (X+Y −a,X2+Y 2−a3, X3+Y 3−a5) e X+Y −a, 2Y 2−a3−2Y a+a2, 2a5−3a4+a3,e quindi I ∩C[a] = (2a5− 3a4 +a3), ove 2a5− 3a4 +a3 = a3(a− 1)(2a− 1). Quindi possono esserci soluzionial sistema solo quando a ∈ {0, 1, 12}. In tutti i casi si hanno soluzioni e sono: {(0, 0, 0)} per a = 0,{(0, 1, 1), (1, 0, 1)} per a = 1, e {( 1

4 ,14 ,

12 )} per a = 1

2 .(b) Date le due rette, φ1 : A1 → A3, e φ2 : A1 → A3, definite da φ1(s) = (s, 0, 0) e φ2(s) = (1, 1, s),consideriamo lo scroll(∗) formato dalle rette che si appoggiano sui punti delle rette date che sono immaginedello stesso punto di A1, ovvero

S ={t1φ1(s) + t2φ2(s)

∣∣ s ∈ A1, t1 + t2 = 1}.

Vogliamo trovare un’equazione cartesiana per lo scroll. I punti di S hanno coordinate del tipo

{x1 = t1s+ t2x2 = t2x3 = t2s

,

quindi considerando l’ideale J = (X1− t1s− t2, X2− t2, X3− t2s), possiamo considerare una base di Grobnerper un ordinamento in cui t1 > t2 > s > X1 > X2 > X3 che e un ordine di eliminazione per t1, t2, s e ci da ipolinomi

1− t1 −X1, t2 −X2, s−X1 +X2 −X3, X1X2 −X22 −X3 +X2X3

e quindi la chiusura della proiezione in A3 e V (J ∩ C[X1, X2, X3]), ovvero il paraboloide iperbolico diequazione X1X2 −X2

2 −X3 +X2X3.

(∗) Ricordiamo che, piu in generale, se V e una varieta e φi : V → An, i = 1, . . . , k, sono morfismi di varieta, lo scrolldeterminato da questi dati e l’insieme

S = { t1φi(v) + · · ·+ tkφk(v) | v ∈ V, t1 + · · ·+ tk = 1 } .

14