Marta Carvelli
25 giugno 2017
Indice
1 Introduzione e de nizioni 7
1.1 De nizioni preliminari . . . 7
2 Caratterizzazione delle Border Bases 11 2.1 De nizione e prime proprietà . . . 11
2.2 Algoritmo di Mourrain . . . 24
2.3 Caratterizzazione . . . 33
3 Algoritmi 55 3.1 Descrizioni preliminari . . . 55
3.2 Algoritmi Esatti . . . 55
3.2.1 Basis Tansformation Algorithm . . . 61
3.2.2 Border Bases Algorithm 2 . . . 63
3.3 Algoritmi Approssimati . . . 79
3.3.1 Stable Order Ideal Algorithm . . . 80
3.3.2 Approximate Vanishing Ideal . . . 97
3.4 Calcolo della Border Bases Approssimata . . . 111
3.5 Conclusioni . . . 126
Bibliogra a 129
Introduzione
In questa tesi verrà trattata la teoria delle border basis per ideali polinomiali zero dimensionali; per esporre la trattazione verranno utilizzate le notazioni presenti in Kreuzer, Robbiano [2]. Le border basis sono una generalizza-zione delle Gröbner basis: rispetto ad esse sono piú stabili rispetto ad una trasformazione dei coe cienti dei polinomi; ciò vuol dire che la variazione dei coe cienti tramite delle quantità molto piccole non provoca un grosso cambiamento nella border basis. Un'altra caratteristica delle border basis è quella di mantenere inalterata la simmetria dell'ideale di partenza.
Vediamo ora un esempio esempli cativo di quanto detto sopra. Consideriamo il sistema polinomiale seguente:
(
f1 = 14x2 + y2− 1 = 0
f2 = x2+14y2− 1 = 0
La varietà associata consiste dei 4 punti X = ( ±r 4 5, ± r 4 5 !)
Usando la teoria delle basi di Gröbner descriveremo la situazione come segue. L'insieme {x2− 4
5, y 2− 4
5} è la base di Gröbner ridotta dell'ideale
I = (f1, f2) ⊆ C[x, y]
rispetto all'ordinamento σ = DegRevLex. Abbiamo pertanto LTσ{I} = (x2, y2)
e la classe di resto dei termini in T2 \ LT
σ{I} = {1, x, y, xy} forma una
base dello spazio vettoriale su C di C[x, y]/I. Adesso consideriamo il sistema polinomiale perturbato ( ˜f1 = 1 4x 2+ y2+ εxy − 1 = 0 ˜ f2 = x2+ 14y2+ εxy − 1 = 0 5
dove ε è un numero positivo molto piccolo. L'intersezione dei luoghi di zeri dei due polinomi consiste di quattro punti perturbati vicini a quelli in X. Questa volta l'ideale ˜I = ( ˜f1, ˜f2)ha la base di Gröbner ridotta
x2− y2, xy + 5 4εy 2− 1 ε, y 3− 16ε 16ε2− 25x + 20 16ε2− 25y 2 .
Inoltre abbiamo LTσ( ˜I) = (x2, xy, x3) e T2 \ LTσ{ ˜I} = {1, x, y, y2}. Si
evince quindi che una piccola variazione nei coe cienti di f1 e f2 ha
cau-sato un grosso cambiamento strutturale nella base di Gröbner di (f1, f2)
e nella base dello spazio vettoriale C[x, y]/(f1, f2) nonostante gli zeri del
sistema non siano variati di molto. Diamo adesso un altro esempio. Sia I = (x2+ xy + y2, x3, x2y, xy2, y3)in Q[x, y] un ideale simmetrico rispetto al-lo scambio di x con y. Poiché il leading term di x2+xy +y2è x2o +y2, l'ideale
(I)ha due possibili leading term ideal, cioé gli ideali J1 = (x2, xy2, y3)e J2 =
(x3, x2y, y2). Nessuno dei due è simmetrico; l'insieme O = {1, x, y, x2, y2} è simmetrico e rappresenta una base dello spazio vettoriale Q[x, y]/I. Le basi di Gröbner non preservano la simmetria; sarebbe auspicabile trovare un siste-ma di generatori di I con proprietà simili a quelle delle basi di Gröbner che preservi la simmetria. Per far fronte a questa necessità verrà introdotta la teoria delle Border Basis. Verranno descritti inizialmente, seguendo sempre le notazioni di Kreuzer, Robbiano in [2], gli strumenti per sviluppare la teo-ria: de niremo pertanto i concetti di order ideal, dei suoi border, dell'indice di un elemento e le sue proprietà; dopo aver introdotto l'indice passeremo alla border form di un polinomio e costruiremo in ne la teoria delle Border Bases de nendone le proprietà e caratterizzandole; vedremo nei capitoli successivi una serie di algoritmi, alcuni esatti e altri approssimati. In ne daremo cenni di un algoritmo che non fa riferimento a nessun ordinamento monomiale.
Capitolo 1
Introduzione e de nizioni
1.1 De nizioni preliminari
Sia K un campo algebricamente chiuso, P = K[x1, ...xn], e sia I ⊆ K[x1, ...xn]
un ideale zero-dimensionale. L'idea alla base della teoria delle Border bases è di descrivere un anello zero-dimensionale K[x1, ...xn]/I tramite un order ideal
di monomi O la cui classe di resto forma una base di K[x1, ...xn]/I sul campo
K e tramite la tavola di moltiplicazione di questa base. Ci sono diversi van-taggi ad usare un order ideal piuttosto che un insieme arbitrario di termini; ad esempio dopo aver de nito il border ∂O di O come ∂O = ∪n
i=1xiO \ O
possiamo descrivere la struttura moltiplicativa di K[x1, ...xn]/I in
manie-ra semplice : è su ciente conoscere come i prodotti xit ∈ ∂O con t ∈ O
possano venir decomposti nella forma xit ∈ hOiK + I. Inoltre de nendo
∂O = O ∪ ∂O e ∂2O = ∂(∂O) e ripetendo la procedura, possiamo introdur-re border di dimensione più alta. Ciò porta alla de nizione di indice di un termine t rispetto ad O : esso è quel numero i tale che t ∈ ∂iO; l'indice è
de nito unicamente. Nonostante non abbia le stesse proprietà del grado ci permette comunque di introdurre la border form di un polinomio. Possiamo quindi ora costruire la teoria delle border bases. Sia O = {t1, . . . , tn} un
order ideal e ∂O = {b1, ..., bν} il suo border. Una border prebases consiste
di un polinomio della forma gj = bj −Pµi=1αijti con αij ∈ K e può essere
usata per la border division. È una border basis se e solo se le classi di resto di {t1, ..., tµ} formano una base su K di K[x1, ...xn]/I. Se O
rappre-senta una base dello spazio vettoriale P/I, allora una O-border bases di I esiste, è univocamente determinata, e genera l'ideale I. Inoltre è possibile de nire e calcolare la forma normale rispetto ad O. In seguito vedremo che le border bases possono essere caratterizzate dall'essere generate in maniera speciale ossia tramite dei border form ideal, e dalla convergenza delle
ni associate riscritte rispetto alle basi di Gröbner. Le border bases possono essere anche caratterizzate dal fatto che le loro matrici di moltiplicazione associate commutano e hanno il loro criterio di Buchberger. In ne per ideali zero-dimensionali ci consentono di superare i limiti delle basi di Gröbner visti negli esempi precedenti e possono essere calcolate usando gli algoritmi per le border bases che vedremo. Diamo adesso delle de nizioni che saranno utili in seguito.
Sia K[x1. . . xn] l'anello dei polinomi nelle indeterminate {x1, . . . , xn} sul
campo K. De niamo xm =Q
j∈[n]xjmj per m ∈ Nn e indichiamo con
Tn= {xm| m ∈ Nn}
il monoide dei termini. Per ogni d ∈ N indicheremo con T6dn = {xm ∈ Tn| kmk
1 6 d}
Tn
6d = {xm ∈ Tn| kmk1 6 d}, ossia l'insieme dei monomi di grado totale
al più d. Per un polinomio p ∈ K[X] con p = Pl
i=1aixmi de niremo supporto
di p l'insieme supp(p) = {xmi | i ∈ [l]}dove l = {1, . . . , l} e in maniera simile,
per un insieme di polinomi Q si de nisce supp(Q) = Sp∈Qsupp(p). Diamo
ora alcune de nizioni, iniziando da quella di ordinamento monomiale : De nizione 1.1.1. Un ordinamento monomiale su K[x1, . . . , xn] su Zn>0
o equivalentemente, ogni relazione sull'insieme dei monomi xα, α ∈ Zn>0
soddisfacente :
i) > è un ordinamento totale ( lineare) su Zn >0.
ii) se α > β e γ ∈ Zn
>0, allora α + γ > β + γ.
iii) > è un buon ordinamento in Zn
>0. Ciò signi ca che ogni sottoinsieme
non vuoto di Zn
>0 ammette un elemento minimo rispetto a >.
.
Dato un term ordering σ, il leading term LTσ(p) di un polinomio p è :
De nizione 1.1.2. LTσ(p) = t con t ∈ supp(p) tali che per tutti i t0 ∈
il leading coe cient LCσ(p) di p è il coe ciente di LTσ(p).
Omettere-mo di speci care σ quando l'ordinamento è chiaro dal contesto. Ricordia-mo che il grado di un polinomio p ∈ K[X] è deg(p) = max
xm∈supp(p)kmk1. La
leading form LF (p) di un polinomio p = Pn i aix m i ∈ K[X] è de nita co-me LF (p) = Pl i=1,kmki=daix m
i , è ottenuta cioè isolando la parte di grado
massimo. Entrambi possono essere generalizzate agli insiemi in modo ovvio de nendo LF (P ) = {LF (p) | p ∈ P } e LT (P ) = {LT (p) | p ∈ P }. Nel se-guito useremo spesso l'insieme di polinomi M = {p1, ..., ps}, l'ideale da loro
generato e lo spazio vettoriale generato le cui coordinate sono indicizzate dai monomi nel supporto di M. Denoteremo l'ideale generato da M come (M )K[X] e lo spazio vettoriale generato come hM iK. Per n ∈ N de niamo
[n] = {1, ..., n}. Accanto a queste de nizioni dobbiamo ricordare quella di base di Gröbner e quella di ideale zero dimensionale:
De nizione 1.1.3. Base di Gröbner
Si ssi un ordinamento monomiale su K[x1, . . . , xn]. Un sottoinsieme
nito G = {g1, . . . , gs} di un ideale I è detto una base di Gröbner (o base
standard) se :
(LT (g1), ..., LT (gt)) = (LT (I))
dove (LT (I)) è l'ideale generato dall'insieme
LT (I) = {cxα| ∃ f ∈ I con LT (f ) = cxα}.
Accanto alla de nizione di base di Gröbner vanno ricordate anche quelle di Base di Gröbner minimale e Base di Gröbner ridotta.
De nizione 1.1.4. Base di Gröbner minimale Una base di Gröbner minimale per un I ⊆ K[x1, . . . , xn] è una base di Gröbner per I tale che:
i) LC(p) = 1 per tutti i p ∈ G.
ii) Per tutti i p ∈ G, lt(p) non appartiene a (LT (G − {p})).
De nizione 1.1.5. Base di Gröbner ridotta Una base di Gröbner ridotta per un ideale polinomiale I è una base di Gröbner per I tale che:
i) LC(p) = 1 per tutti i p ∈ G.
ii) Per tutti i p ∈ G, nessun monomio di p giace nell'ideale (LT (G−{p})). Va precisato inoltre che la base di Gröbner ridotta è unica mentre quella minimale non lo è.
De nizione 1.1.6. Sia V = V(I) l'insieme delle soluzioni in Kn associate
all'ideale polinomiale I. I si dice zero-dimensionale se vale una delle seguenti proprietà tra di loro equivalenti :
i) V è un insieme nito.
ii) Il K-spazio vettoriale S = Span(xα| xα ∈ hLT (I)i)/ ha dimensione
nita.
iii) Il K-spazio vettoriale K[x, y]/I ha dimensione nita.
A questo punto possiamo andare a caratterizzare le Border Bases dimo-strandone innanzitutto esistenza e unicità; vanno date alcune de nizioni che saranno utili in questa sezione.
Capitolo 2
Caratterizzazione delle Border
Bases
2.1 De nizione e prime proprietà
Sia K un campo, sia K[x1. . . xn]con graduazione standard e sia Tnil monoide
dei termini in K[x1. . . xn].
De nizione 2.1.1. Sia O un sottoinsieme non vuoto di Tn :
a) La chiusura di O é l'insieme O di tutti i termini in Tn che dividono
uno dei termini di O.
b) L'insieme O viene chiamato un order ideal se O = O cioè se O è chiuso rispetto alla divisione.
Il complementare di un order ideal è un monoideale e viceversa. Da un order ideal se ne possono costruire altri nella maniera seguente :
De nizione 2.1.2. Border di O
a) Il border di O è l'insieme ∂O = (T1)n· O\O = (x1O ∪ . . . ∪ xnO) \ O
La prima border closure di O è l'insieme ∂O = O ∪ ∂O.
b) Per ogni k ≥ 1 de niamo induttivamente il (k + 1)-esimo border di O con ∂k+1O = ∂(∂kO) e la (k + 1)-esima border closure di O
con la regola ∂k+1O = ∂kO ∪ ∂k+1O. Per convenienza, indichiamo
∂0O = ∂0O = O.
La k-esima border closure di un order ideal è un order ideal per ogni k ≥ 0. 11
Esempio 2.1.1. Sia O = {1, x, y, x2, xy, y2, x3, x2y, y3, x4, x3y} ⊂ T2.
L'in-sieme O è un order ideal. Visualizziamo O e i primi suoi due border come segue. • • • • • • • • • ◦ ◦ • • • ◦ ◦ ◦ ◦ ◦ × × × × × × ×
Proposizione 2.1.1. ( Proprietà basilari dei Border) Sia O ⊆ Tn un order ideal :
a) Per ogni k ≥ 0 abbiamo un'unione disgiunta ∂kO = ∪k
i=0∂iO. Di
conseguenza abbiamo un'unione disgiunta Tn= ∪∞ i=0∂iO.
b) Per ogni k ≥ 1 abbiamo ∂kO = Tn
k· O \ Tn<k · O.
c) Un termine t ∈ Tn è divisibile per un termine in ∂O se e solo se
t ∈ Tn\ O.
Dimostrazione. Per prima cosa dimostreremo a). La de nizione ∂O fornisce ∂O = O ∪ Tn
1 · O . Induttivamente ne segue che:
∂k+1O = ∂kO ∪ Tn
1 · ∂kO = ∂kO ∪ Tnk+1O.
La seconda parte di a) segue dall'osservazione che ogni termine è in ∂kO
per qualche k ≥ 0 e l'aermazione b) è conseguenza di ∂k+1O = ∂k+1O \∂kO.
In ne, l'aermazione c) si ottiene da b) che implica che t ∈ ∂kO per
qualche k ≥ 1 è equivalente all'esistenza di una fattorizzazione t = t0t00 con
deg(t0) = k − 1 e t00 ∈ ∂O.
L'unione disgiunta nella parte a) della proposizione ci permette di misu-rare la 'distanza' di un termine da un order ideal nella maniera seguente: De nizione 2.1.3. Sia O ⊆ Tn un order ideal.
a) Per ogni t ∈ Tn l'indice di t rispetto ad O è l'unico numero k ∈ N tale
che t ∈ ∂kO e si denota con ind O(t).
b) Per un polinomio f ∈ P \ {0} de niamo l' indice di f rispetto ad O (oppure O − indice di f) come indO(f ) = max{indO(t)|t ∈ Supp(f )}.
Elenchiamo adesso alcune utili proprietà dell'indice. Proposizione 2.1.2. Sia O ⊆ Tn un order ideal
a) Dato un termine t ∈ Tn, il numero k = ind
O(t) è il più piccolo numero
naturale tale che t = t0t00 con t ∈ Tn k e t
00∈ O.
b) Dati 2 termini t, t0
∈ Tn, abbiamo ind
O(tt0) ≤ deg(t) + indO(t0).
c) Dati 2 polinomi f, g ∈ P entrambi diversi da zero e tali che f + g 6= 0, abbiamo la disuguaglianza
indO(f + g) ≤ max{indO(f ), indO(g)}.
d) Dati 2 polinomi f, g ∈ P entrambi diversi da zero, abbiamo la disugua-glianza
indO(f g) ≤ min{deg(f ) + indO(g), deg(g) + indO(f )}.
Dimostrazione. L'aermazione a) segue dalla proposizione precedente utilizzando il fatto che ∂k
O = Tn
k · O \ T n
<k · O, mentre il punto b) segue
direttamente da a). L'inclusione Supp(f + g) ⊆ Supp(f) ∪ Supp(g) ci dà come conseguenza il punto c). In ne, l'aermazione d) segue dal punto b) e dal fatto che Supp(fg) ⊆ {t0t00 | t0 ∈ Supp(f ), t00 ∈ Supp(g)}.
Purtroppo utilizzare l'indice rispetto ad O per ordinare i termini presen-ta degli inconvenienti: è infatti incompatibile con la moltiplicazione, ossia indO(t) ≤ indO(t0) non implica, in generale che indO(tt00) ≤ indO(t0t00). Il
prossimo esempio lo dimostra:
Esempio 2.1.2. Sia O = {1, x, x2} ⊂ T2. Allora O è un order ideal con
border ∂O = {y, xy, x2y, x3}. Il diagramma seguente illustra la situazione.
• • • ◦ ◦ ◦ × × ×
◦ × ×
Moltiplicando per x2 i termini di ind
O(x2) < indO(y), otteniamo
indO(x2· x2) > indO(x2· y).
In maniera simile, moltiplicando per x i termini di indO(y) = indO(x2 · y)
otteniamo indO(x · y) < indO(x · x2y).
Nel prosieguo indicheremo con O = {t1. . . tµ}un order ideal nito in Tne
con ∂O = {b1. . . bµ}il suo border. Useremo la classe di resto dei termini in O
come una K−base dell'anello delle classi di resto di P modulo qualche ideale zero dimensionale. Per l'ideale zero dimensionale cercheremo un insieme di generatori con la forma seguente:
De nizione 2.1.4. Un insieme di polinomi G = {g1. . . gν} viene chiamato
una O - border prebases se i polinomi hanno la forma : gj = bj− µ X i=1 αijti con αij ∈ K per 1 ≤ i ≤ µ e 1 ≤ j ≤ ν.
Le border prebases consentono di eseguire la divisione polinomiale con resto. L'algoritmo seguente fornisce uno strumento fondamentale per lavorare con le border prebases.
Algoritmo 2.1.5. Border Division Algorithm
Siano O = {t1. . . tµ} un order ideal in Tn, ∂O = {b1. . . bν} il suo border
e sia {g1. . . gν} una O-border prebases. Dato un polinomio f ∈ K[x1. . . xn],
consideriamo la seguente sequenza di istruzioni:
1) Siano f1 = . . . = fν = 0, c1 = . . . = cµ= 0 e h = f.
2) Se h = 0, restituisci (f1, . . . , fν, c1, . . . , cµ) e stop.
3) Se indO(h) = 0 allora scrivi h = c1t1 + ... + cµtµ con c1. . . cµ ∈ K.
Restituisci (f1, . . . , fν, c1, . . . , cµ) e stop.
4) Se indO(h) > 0allora sia h = a1h1+ . . . + ashs con a1, . . . , as ∈ K \ {0}
e h1, . . . , hs ∈ Tntali che indO(h1) = indO(h). Determina il più piccolo
indice i ∈ {1, . . . , ν} per il quale h1 si fattorizza come h1 = t0b1 con un
termine t0
∈ Tn di grado ind
O(h) − 1 . Sottrai a1t0gi da h, aggiungi a1t0
a fi, e continua col passo 2).
f = f1g1+ . . . + fνgν + c1t1+ . . . + cµtµ
e deg(fi) ≤ indO(f ) − 1 per tutti gli i ∈ {1, . . . , ν} con figi 6= 0. Questa
rappresentazione non dipende dalla scelta del termine h1 nel passo 4).
Dimostrazione. Per prima cosa dimostreremo che le istruzioni posso-no essere eseguite. Nel passo 3) il fatto che indO(h) = 0 implica che il
Supp(f ) ⊆ O. Nel passo 4) scriviamo h come una combinazione lineare di termini e notiamo che almeno uno di loro, ad esempio h1 deve avere indice
k = indO(h) > 0. Il punto a) della proposizione 2.1.2, fornisce una
fattoriz-zazione h1 = ˜tti con ˜t ∈ Tnk e ti ∈ O e non c'è una fattorizzazione con un
termine ˜t di grado più piccolo. Dato che k > 0, possiamo scrivere ˜t = t0x j
per qualche t0
∈ Tn e j ∈ {1, . . . , n}. Allora abbiamo deg(t0) = k − 1 e il
fatto che ˜tabbia il più piccolo grado possibile implica che xjti ∈ ∂O. Dunque
vediamo che h1 = t0(xjti) = t0bk per qualche bk∈ ∂O.
Ora dimostreremo che l'algoritmo termina. Proveremo che il passo 4) viene eseguito un numero nito di volte. Analizziamo la sottrazione h1−a1t0gi
nel passo 4). Per de nizione, c'è una rappresentazione gi = bi −Pµk=1αkitk
tale che αki ∈ K per k = 1, . . . , µ. Quindi la sottrazione diventa :
h1 − a1t0gi = a1h1+ · · · + ashs− a1t0bi+ a1t0
Pµ
k=1αkitk.
Adesso, poichè abbiamo a1h1 = a1t0bi, un termine di indice indO(h)viene
rimosso da h e sostituito con dei termini della forma t0t
l ∈ ∂k−1O i quali
hanno indice strettamente minore. L'algoritmo termina dopo un numero nto di passi perchè c'è solo un numero nito di termini di indice minore o uguale di quello di un termine dato. In ne proviamo la correttezza; a tale scopo dimostriamo che l'equazione
f = h + f1g1+ . . . + fνgν + c1t1+ cµtµ
è un invariante dell'algoritmo. Viene soddisfatta alla ne del passo 1); un polinomio fi viene modi cato nel passo 4), dove la sottrazione h1− a1t0gi
viene compensata dall'addizione (fi+ a1t0)gi. Le costanti c1, . . . , cµ vengono
modi cate solo nel passo 3) nel quale h viene sostituito con c1t1+ . . . + cµtµ.
Quando l'algoritmo termina, abbiamo h = 0. Questo prova la rappresen-tazione stabilita di f. L'ulteriore aermazione che questa rappresenrappresen-tazione non dipenda dalla scelta di h1 nel passo 4) segue dall'osservazione che h1
vie-ne sostituito con termini di indice strettamente più basso, per cui le diverse esecuzioni del passo 4) corrispondenti alla riduzione di diversi termini di un dato indice h non interferiscono l'uno con l'altro; pertanto, il risultato nale, dopo che tutti quei termini sono stati riscritti, è indipendente dall'ordine in
cui i termini vengono 'trattati'.
Bisogna notare che la rappresentazione calcolata dal Border Division Algorithm è ottima nel senso che per ogni t ∈ Supp(fi) abbiamo
indO(tbi) = deg(t) + 1 e
indO(t(gi− bi)) 6 deg(t) .
Esempli chiamo ora il Border Division Algorithm con un esempio concreto: Esempio 2.1.3. Sia O = {t1, t2, t3} ⊆ T2l'order ideal dato da t1 = 1, t2 = x,
t3 = y. Il border di O è ∂O = {b1, b2, b3} con b1 = x2, b2 = xy e b3 = y2.
I polinomi g1 = x2 + x + 1, g2 = xy + y, g3 = y2+ x + 1 costituiscono una
O-border prebases. Vogliamo dividere il polinomio f = x3y2−xy2+ x2+ 2per
questa O-border prebases. I successivi border sono : ∂2O = {x3, x2y, xy2, y3},
∂3O = {x4, x3y, x2y2, xy3, y4} e ∂4O = {x5, x4y, x3y2, x2y3, xy4, y5}.
Applichiamo il Border Division Algorithm.
1) Siano f1 = f2 = f3 = 0, c1 = c2 = c3 = 0 e h = x3y2− xy2 + x2+ 2.
Gli O-indici dei termini nel Supp(h) sono 4,2,1 e 0 rispettivamente, e quindi h ha indice 4.
4) Abbiamo x3y2 = xy2·b
1 con deg xy2 =ind(h)-1. Così abbiamo f1 = xy2
e h = x3y2− xy2+ x2+ 2 − xy2(x2+ x + 1). I termini nel supporto di
h = −x2y2− 2xy2+ x2+ 2hanno O-indice 3, 2 ,1 e 0, rispettivamente.
4) Abbiamo x2y2 = y2· b
1 con deg y2 = ind(h)-1. Aggiungi −y2 a f1 per
ottenere f1 = xy2− y2, e sia h = −x2y2− 2xy2+ x2+ 2 + y2(x2+ x + 1).
I termini nel supporto di h = −xy2+ x2+ y2+ 2hanno O-indice 2,1,1
e 0, rispettivamente. 4) Abbiamo xy2 = y · b
2 con deg y = ind(h)-1. Siano f1 = −y e h =
−xy2+ x2+ y2+ 2 + y(xy + y). I termini nel supporto del polinomio
h = x2+ 2y2+ 2 hanno O-indice 1,1 e 0 rispettivamente.
4) Abbiamo x2 = 1 · b
1 con deg 1 = ind(h)-1. Aggiungiamo 1 ad f1 per
ottenere f1 = xy2 − y2 + 1 e sia h = x2 + 2y2 + 2 − 1(x2 + x + 1).
I termini nel supporto di h = 2y2 − x + 1 hanno O-indice 1, 0 e 0
rispettivamente. 4) Abbiamo y2 = 1 · b
3 con deg 1 = ind (h)-1. Aggiungi 2 a f3 per ottenere
f3 = 2, e sia h = 2y2− x + 1 − 2(y2 + x + 1). I termini nel supporto
3) Abbiamo h = −1 · t1− 3 · t2+ 0 · t3. L'algoritmo restituisce la t-upla
(xy2− y2 + 1, −y, 2, 1, −3, 0)
e si arresta.
Complessivamente, abbiamo calcolato la rappresentazione f = (xy2− y2+ 1)g
1− yg2+ 2g3− 1t1− 3t2+ 0t3
Se eseguiamo l'algoritmo rispetto alla t-upla (g0 1, g 0 2, g 0 3) = (g3, g2, g1), calcola la rappresentazione f = (x3+ x)g10 − 1g20 + (x2+ 2)g30 + 1t1− 3t2− 1t3 = (x2+ 2)g1− 1g2+ (x3+ x)g3+ 0t1+ 1t2 − 1t3
Questo dimostra che l'ordine dei polinomi nella O-border prebases in- uenza il risultato del Border Division Algorithm.
Possiamo usare il risultato del Border Division Algorithm per de nire il normal O − remainder NRO,G(f ) = c1t1 + . . . + cµtµ di un polinomio
f rispetto alla -upla G = (g1, . . . , gν). Nell'esempio precedente abbiamo
N FO,G(f ) = −3x − 1 e NFO,G0(f ) = x − y. Gli elementi f e NRO,G(f )
rap-presentano la stessa classe di resto nell'anello P/(g1, . . . , gν). In particolare, la
classe di resto degli elementi di O genera il K-spazio vettoriale P/(g1, . . . , gν).
Segue dall'esempio precedente che questo sistema di generatori non è neces-sariamente una base. Infatti, abbiamo 4x − y + 1 = NRO,G0(f ) − N RO,G(f ).
Pertanto, è naturale introdurre la nozione seguente..
De nizione 2.1.6. Sia G = {g1, . . . , gν} una O-border prebases, sia G la
upla (g1, . . . , gν) e sia I ⊆ K[x1, . . . , xn] un ideale contenente G. L'insieme
G o la upla G viene chiamata una O-border basis di I se è soddisfatta una delle seguenti condizioni.
a) La classe di resto O = {t1, . . . , tµ} forma una base dello spazio
vetto-riale K[x1, . . . , xn]/I su K.
b) Abbiamo I ∩ hOiK = {0}.
c) Abbiamo K[x1, . . . , xn] = I ⊕ hOiK.
Le Border Basis consentono di preservare la simmetria; riprendiamo l'e-sempio visto nell'introduzione.
Esempio 2.1.4. Siano Q[x, y] e I = (x2 + xy + y2, x3, x2y, y3). L'insieme
O = {1, x, y, x2, y2} è un order ideal che consiste di 5 termini, tanti quanti
dimK(Q[x, y]/I) = 5. Poichè abbiamo ∂O = {x3, x2y, xy, xy2, y3}, i polinomi g1 = x3, g2 = x2y, g3 = xy + x2 + y2, g4 = xy2 e g5 = y3 formano una
O-border prebasis of I. Inoltre, le condizioni della de nizione sono soddisfatte perché I è omogeneo e la condizione c) può esser controllata grado per grado. Pertanto l'insieme G = {g1, . . . , g5} è una O-border basis per I.
Adesso dimostreremo che la de nizione contiene il fatto che una O -border prebasisdi I realmente genera I.
Proposizione 2.1.3. Sia G una O-border prebasis di un ideale I ⊆ P . Allora l'ideale I è generato da G.
Dimostrazione. Per de nizione, abbiamo (g1, . . . , gµ) ⊆ I. Per provare
l'inclusione inversa, sia f ∈ I. Usando il Border Division Algorithm 2.1.5, il polinomio f può essere espresso come f = f1g1+. . .+fνgν+c1t1+. . .+cµtµ,
do-ve f1, . . . , fν ∈ K[x1, . . . , xn] e c1, . . . , cµ ∈ K. Questo implica l'uguaglianza
delle classi di resto 0 = f = c1t1+ . . . + cµtµ in K[x1, . . . , xn]/I. Per
assunzio-ne, le classi di resto t1, . . . , tµ sono linearmente indipendenti su K; ne segue
che c1 = . . . = cµ = 0 e l'espressione di f diventa f = f1g1+ . . . + fνgν.
Abbiamo quindi de nito un nuovo oggetto matematico di cui vogliamo di-mostrare esistenza e unicità. Una condizione necessaria per l'esistenza di una O-border bases di I è data chiaramente da # O = dimK(K[x1, . . . , xn]/I).
L'esempio successivo mostra che questa condizione non è però su ciente. Esempio 2.1.5. Siano Q[x, y] e I l'ideale dei polinomi che si annullano sull'insieme costituito dai 5 punti X = {(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)} in A2
Q. Abbiamo allora dimK(Q[x, y]/I) = 5. In T
2 i seguenti order ideal
contengono cinque elementi :
O1 = {1, x, x2, x3, x4} O2 = {1, x, x2, x3, y} O3 = {1, x, x2, y, y2} O4 = {1, x, x2, y, xy} O5 = {1, x, y, y2, y3} O6 = {1, y, y2, y3, y4} O7 = {1, x, y, xy, y2}
Non tutti sono adatti per costituire una border bases di I. Per esempio, la classe di resto degli elementi di O1 non può formare una base sul campo
K dello spazio vettoriale Q[x, y]/I poichè x3− x ∈ I in quanto si annulla su tutti i punti di X. Allo stesso modo, la classe di resto degli elementi di O6
non può formare una base su K di Q[x, y]/I in quanto y3− y ∈ I.
Proposizione 2.1.4. (Esistenza e unicita' delle Border Bases) Sia O = {t1, . . . , tµ}un order ideal, sia I ⊆ K[x1, . . . , xn]un ideale zero-dimensionale
e assumiamo che la classe di resto degli elementi di O formi una base dello spazio vettoriale K[x1, . . . , xn]/I sul campo K.
a) Esiste una unica O-border bases di I.
b) Sia G una O-border prebases i cui elementi stanno in I. Allora G è una O-border bases di I.
c) Sia k ⊆ K il campo di de nizione di I. Allora la O-border bases di I è contenuta in k[x1, . . . , xn].
Dimostrazione. Proveremo dapprima la a). Sia ∂O = {b1, . . . , bν}. Per
ogni i ∈ {1, . . . , ν}, l'ipotesi implica che la classe di resto di bi in P/I è
linearmente dipendente sulla classe di resto degli elementi di O. Quindi I contiene un polinomio della forma gi = bi −Pµj=1αijtj con αij ∈ K.
Allo-ra G = {g1, . . . , gν} è una O-border prebases e quindi una O-border bases
per I per la de nizione 2.1.6. Sia adesso G0
= {g01, . . . , g0ν} un'altra O-border bases di I. Supponiamo che esista un indice i ∈ {1, . . . , ν} tale che gi0 = bi−Pµj=1α0ijtj con αij 6= α0ij per qualche indice j ∈ {i, . . . , µ}, allora
gi − g0i è un polinomio in I diverso da zero e ha supporto in O. Questo
contraddice l'ipotesi e dimostra a). Dimostriamo b). Dalla de nizione di O-border bases è su ciente osservare che l'insieme G è una O -O-border bases di I e applicare a). In ne dimostreremo c). Sia P0 = k[x1, . . . , xn]e I
0
= I ∩ P0. Dato σ un term ordering, gli ideali I e I0
hanno la stessa base di Gröbner ridotta per il lemma 2.4.16 Kreuzer Robbiano, Computational Commutati-ve Algebra 1). Quindi abbiamo Tn \ LT
σ{I} = Tn \ LTσ{I
0
}, e pertanto dimk(K[x1, . . . , xn]/I) = dimk(P
0
/I0). Gli elementi di O sono contenuti in P0, e sono linearmente indipendenti modulo I0. Quindi la loro classe di resto forma uno spazio vettoriale su k di P0
/I0. Sia ora G0 la O-border bases di I0. Allora G0 è una O -border prebases i cui elementi sono contenuti in I. L'asserto si ottiene allora da b).
Un ideale zero dimensionale possiede in ogni caso una border bases? Usan-do la parte a) della proposizione possiamo riformulare la Usan-domanda nel moUsan-do seguente: dato I un ideale zero dimensionale, ci sono order ideal tali che
le classi di resto dei loro elementi formano una base su K dello spazio vet-toriale K[x1, . . . , xn]/I ? La risposta è aermativa, e verrà dimostrato con
l'aiuto delle Basi di Gröbner. Dato un order ideal O ⊂ Tn, il suo
comple-mentare Tn\ O è l'insieme dei termini di un ideale monomiale. Ricordiamo
che ogni ideale monomiale ha un unico insieme minimale di generatori (ve-di prop 1.3.11 Kreuzer, Robbiano Computational Commutative Algebra 1). Gli elementi dell' insieme minimale di generatori dell'ideale monomiale cor-rispondente a Tn\ O vengono chiamati corner di O. Un'immagine spiega
l'adeguatezza del nome.
• • • • • • • • × × ×
La prossima proposizione ci aiuta a chiarire la relazione tra le Gröbner Bases e la border bases di un ideale di polinomi zero dimensionale.
Proposizione 2.1.5. Sia σ un term ordering su Tn, e sia O
σ(I)l'order ideal
Tn\ LTσ{I}. Allora esiste una unica Oσ(I)-border bases di I, e la σ base
di Gröbner ridotta di I è il sottoinsieme di G corrispondente ai corner di Oσ(I).
Dimostrazione. Dal teorema della base di Macaulay (Teorema 1.5.7 Kreu-zer Robbiano, Computational Commutative Algebra 1), la classe di resto degli elementi in Oσ(I) forma una base su K di K[x1, . . . , xn]/I. Quindi il
punto a) della proposizione 2.1.4 implica l'esistenza e l'unicità della Oσ(I)
border bases di I. Per dimostrare la seconda aermazione sia b ∈ Tn\ O σ(I)
un corner di Oσ(I). Gli elementi della σ-base di Gröbner ridotta di I con
leading term b hanno la forma b − NFσ,I(b), dove NFσ,I(b)è contenuta nello
span di Oσ(I). Poichè la Oσ(I) di I è unica, questi elementi coincidono con
i border bases elementi corrispondenti a b.
Riassumendo, l'ideale I non ha necessariamente una O-border bases per ogni order ideal O consistente di un numero di termini che eguaglia la dimK(K[x1, . . . , xn]/I), ma c'è sempre una O-border bases per
O = Tn\ LT σ{I}
dove σ è un term ordering. Comunque, l'esempio 2.1.4 dimostra che non tutte le border basis di I provengono da un term ordering. In questo senso, la teoria delle border basis generalizza quella delle Basi di Gröbner. La pro-posizione successiva mostra che, quando dividiamo per una border basis, il normal remainder non dipende dall'ordine degli elementi.
Analizziamo ulteriormente l'analogia tra Gröbner basis e Border basis ini-ziando col dare una de nizione.
De nizione 2.1.7. Una coppia (g, b) è detta un marked polynomial se g è un polinomio diverso da zero e b ∈ Supp(g) con coe ciente diverso da zero. Una upla di polinomi (g1, . . . , gν) è marked da una upla di termini
(b1, . . . , bν)se (g1, b1), . . . , (gν, bν)sono marked polynomial. Una lista di
mar-ked polynomial (g1, b1), . . . , (gν, bν)viene detta marked coherently se esiste
un term ordering σ tale che LTσ(gi) = bi per i = 1, . . . , ν. La de nizione
vale anche nel caso in cui la lista sia formata da un solo polinomio.
Ricordiamo inoltre che una O-border (pre)bases può esser vista come una upla di polinomi marcata dai termini nel border di O.
Vediamo un esempio di quanto detto. Sia I = (14x2+ y2− 1, x2+1 4y
2− 1) ∈ Q[x, y].
I ha una border basis rispetto ad O = {1, x, y, xy}; il border di O è ∂O = {x2, x2y, xy2, y2}. La O-border basis di I è {x2− 4 5, x 2y − 4 5y, xy 2 −4 5x, y 2 −4 5}
Dalla de nizione segue che (x2− 4 5, x 2), (x2y −4 5y, x 2y), (xy2−4 5x, xy 2), (y2 −4 5, y 2)
sono marked polynomial.
Proposizione 2.1.6. Sia O un order ideal tale che la classe di resto degli elementi di O forma una base sul campo K dello spazio vettoriale
K[x1, . . . , xn]/I.
Sia G la O-border bases di I, e sia G0 il sottoinsieme di G consistente
degli elementi marked dai corner di O. Allora le seguenti condizioni sono equivalenti.
2. Gli elementi in G0 sono marked coherently.
3. Gli elementi in G sono marked coherently.
Inoltre, se queste condizioni sono soddisfatte, allora G0 è la base di
Gröb-ner ridotta di I rispetto a σ.
Dimostrazione. Proviamo che 1) implica sia 2) che l'aermazione aggiun-tiva. Il fatto che G0 sia la base di Gröbner ridotta di I rispetto a σ segue
dalla proposizione 2.1.5. Quindi G0 è marked coherently. Ora dimostriamo
che 2) implica 3). Per ogni polinomio g ∈ G \ G0, esiste un polinomio g0 ∈ G0
tale che il marked term di g è della forma b = tLTσ(g0). Allora il supporto
del polinomio g − tg0 è contenuto in O, e quindi g = tg0 . Così proviamo
anche che g è marked coherently rispetto a σ.
Poiché 3)⇒2) è ovvio, resta da dimostrare solo 2)⇒ 1). Sia σ un term orde-ring che rende G0 marked coherently. Denotiamo l'ideale monomiale generato
dai leading term degli elementi in G0 da LT
σ(G0). Poiché LTσ(I) ⊇ LTσ(G0),
otteniamo Oσ(I) = Tn \ LTσ(I) ⊆ Tn\ LTσ(G0) = O. Inoltre la classe di
resto degli elementi di Oσ(I) forma una base su K dello spazio vettoriale
K[x1, . . . , xn]/I, e quindi in realtà l'inclusione è un'uguaglianza.
Nella teoria delle basi di Gröbner possiamo de nire un unico rappresen-tante di una classe di resto in K[x1, . . . , xn]/I usando la forma normale di
un polinomio f. La forma normale è ottenuta calcolando il resto (normal remainder) di f ottenuto dalla divisione per una base di Gröbner. Il resto non dipende dalla base di Gröbner ma solo dal term ordering dato e dall'i-deale I. Può essere pertanto usato per per rendere eettivamente calcolabili le operazioni nell'anello K[x1, . . . , xn]/I. Imiteremo ora questo approccio e
generalizzeremo la forma normale alla teoria delle border bases.
Sia O un order ideal, sia G = {g1, . . . , gν}la O-border bases di un ideale
zero dimensionale, e sia G la upla G = (g1, . . . , gν). In questa situazione il
normal O -remainder di un polinomio non dipende dall'ordine degli elementi in G.
Proposizione 2.1.7. Sia G = {g1, . . . , gν} la O-border bases di un ideale
I ⊆ P, sia
π : {1, . . . , ν} −→ {1, . . . , ν} una permutazione e G0 = (g
(π(1)), . . . , g(π(ν))) la corrispondente
permuta-zione della upla G. Allora abbiamo NFO,G(f ) = N FO,G0(f ) per ogni
Dimostrazione. Il Border Division Algorithm applicato a G = G0,
rispet-tivamente, fornisce le seguenti rappresentazioni: f = f1g1+ . . . + fνgν + N FO,G(f ) = f
0
1gπ(1)+ . . . + f
0
νgπ(ν)+ N FO,G0(f )
dove fi, fj ∈ K[x1, . . . , xn]. Quindi abbiamo
N FO,G(f ) − N FO,G0(f ) ∈ hOiK∩ I.
Dall'ipotesi che I abbia una O- border bases segue che hOiK ∩ I = {0}, da
cui la tesi.
Questo risultato ci permette di generalizzare il concetto di forma normale alla teoria delle Border Bases.
Proposizione 2.1.8. Proprietà basilari delle Forme Normali
Sia O un order ideal, sia I ⊆ P un ideale che ha una O -border bases, siano a1, a2 ∈ K e siano f, f1, f2 ∈ P.
a) Se esiste un term ordering σ tale che O = Oσ(I), allora abbiamo
N FO,I(f ) = N Fσ,I(f ).
b) NFO,I(a1f1+ a2f2) = a1N FO,I(f1) + a2N FO,I(f2).
c) NFO,I(N FO,I(f )) = N FO,I(f ).
d) NFO,I(f1f2) = N FO,I(N FO,I(f1)N FO,I(f2)).
Dimostrazione. L'aermazione a) segue dal fatto che sia NFO,I(f ) e
N Fσ,I(f )sono uguali ad un polinomio unicamente determinato in f +I il cui
supporto è contenuto in O. Le aermazioni b), c) e d) seguono dalla stessa unicità.
Un'ulteriore caratterizzazione viene da Kehrein, Kreuzer,Robbiano [3] che fornisce un'espressione della Normal Form tramite le matrici. Diamo quindi ora delle de nizioni che ci serviranno per descriverla.
Dato uno spazio vettoriale V sul campo K che porta una struttura di K[x1, . . . , xn]-modulo, esistono degli endomor smi di V che sono associati
alla moltiplicazione per le indeterminate.
De nizione 2.1.8. Sia V un K-spazio vettoriale. Per i = 1, . . . , n la mappa P-lineare
ϕi : V −→ V de nita da
è chiamato l'i-esimo endomor smo di moltiplicazione di V . Gli endomor smi di moltiplicazione sono a 2 a 2 commutativi, cioè ab-biamo ϕi◦ ϕj = ϕj ◦ ϕi per i, j ∈ {1, . . . , n}.
Esempio 2.1.6. Sia I ⊆ K[x1, . . . , xn]un ideale. L'algebra quoziente K[x1, . . . , xn]/I
possiede una struttura naturale di K[x1, . . . , xn]-modulo
K[x1, . . . , xn] × K[x1, . . . , xn]/I → K[x1, . . . , xn]/I
data da (f, g + I) 7→ fg + I. Per cui ci sono endomor smi di moltiplica-zione canonici
Xi : K[x1, . . . , xn]/I → K[x1, . . . , xn]/I
tali che Xi(f + I) = xif + I per f ∈ K[x1, . . . , xn] e i = 1, . . . , n. Da
notare che K[x1, . . . , xn]/I è un K[x1, . . . , xn]-modulo ciclico con generatore
1 + I.
Possiamo quindi ora caratterizzare la Normal Form anche tramite le matrici.
Proposizione 2.1.9. Siano M1, . . . , Mn ∈ M atn(K) le matrici degli
en-domor smi di moltiplicazione di K[x1, . . . , xn]/I rispetto alla base data dalle
classe di resto dei termini in O. Supponiamo t1 = 1 e sia e1 il primo vettore
della base canonica di Kν. Allora abbiamo
N FO,I(f ) = (t1, . . . , tν) · f (M1, . . . , Mn) · e1
per ogni f ∈ K[x1, . . . , xn].
Dimostrazione. Per dimostrarlo osserviamo che e1 è il vettore delle
coor-dinate di 1 + I nella base di K[x1, . . . , xn]/I data dalla classe di resto dei
termini in O. Poichè Mi è la matrice di moltiplicazione per xi, la upla
f (M1, . . . , Mn) · e1 è la upla delle coordinate di f + I in questa base. Da ciò
segue l'asserto.
2.2 Algoritmo di Mourrain
Presentiamo adesso per completezza un altro approccio nel calcolo della Nor-mal Form che non riguarda direttamente le Border Bases ma sarà utile per lo sviluppo di alcuni algoritmi per il calcolo delle suddette che verranno de-scritti nel prossimo capitolo. Mourrain presenta in [4] un modo dierente di
calcolare la Normal form all'interno dell'algebra quoziente A di un anello di polinomi P modulo un ideale I. L' algoritmo è basato su un criterio che dà un condizione necessaria e su ciente a nchè una proiezione in un insieme di polinomi sia una Normal form modulo l'ideale I. Questo criterio non ri-chiede alcun ordinamento monomiale e generalizza il criterio di Buchberger per gli S-polinomi; porta ad un nuovo algoritmo per costruire la struttura moltiplicativa di un'algebra zero dimensionale.
Daremo quindi ora delle de nizioni e dimostreremo dei lemmi in modo poi da descrivere la struttura moltiplicativa dell'algebra zero dimensionale e in- ne l'algoritmo. Sia quindi K un campo; indicheremo con P = K[x1, . . . , xn]
l'anello dei polinomi nelle variabili x1, . . . , xn a coe cienti in K. Per ogni
α = (α1, . . . , αn) ∈ Nn indichiamo con xα il monomio xα11 · · · xαnn, con |α|
il suo grado deg(xα) = |α| = α
1 + . . . + αn e con (x∗) l'insieme di tutti i
monomi nelle variabili x1, . . . , xn. Scriveremo x0 = 1 in modo da avere
nota-zioni 'omogenee'. Per ogni sottoinsieme G ⊂ P indichiamo con hGi lo spazio vettoriale generato dagli elementi di G e con (G) l'ideale generato dai suoi elementi in P .
De nizione 2.2.1. Per ogni sottospazio lineare V di K[x1, . . . , xn], sia
V+= V + x
1· V + . . . + xn· V
lo spazio vettoriale generato dagli elementi v, xiv per v ∈ V, i ∈ 1, . . . , n. Se
m ⊂ (x)∗ è un sottoinsieme monomiale di K[x1, . . . , xn], denotiamo anche
con m+ l'unione di m, x
1· m, . . . , xn· m, in modo che hmi+ = hm+i .
De-notiamo con V[d]= (V[d−1])+, la d-esima potenza dell'operatore+ su V . Per
convenzione, V[0] = V. L'insieme V[∗] = ∪
d>0V[d] è anche l'ideale generato
da V ed è denotato con (V ).
De nizione 2.2.2. Per ogni polinomio p ∈ K[x1, . . . , xn] ed ogni spazio
vettoriale B ⊂ P , il B-indice di p è il minimo d tale che p ∈ B[d] se p ∈ (B)
e −∞ altrimenti.
Il B-indice di p corrisponde alla 'distanza' tra p e B.
Il prossimo passo sarà quello di de nire la riduzione di un polinomio su B, ossia il B-indice di un polinomio.
Lemma 2.2.1. Siano B e K spazi vettoriali su K[x1, . . . , xn] tali che
Allora ogni elemento p di B[∗] di B- indice d può esser ridotto tramite un
elemento k ∈ K[d−1] ad un elemento r ∈ B : p = r + k. Il polinomio r viene
chiamato un B-resto di p lungo K.
Dimostrazione. Dimostreremo la tesi per induzione sul B-indice di un polinomio. La proprietà è vera per gli elementi in B[1] = B+, che sono di
B-indice 6 1 e che possono essere ridotti tramite K = K[0] ad elementi di
B. Assumiamo vera la proprietà per polinomi di B indice 6 d − 1 e sia p un polinomio di B indice d. Allora p ∈ B[d] ha la forma
p =Pn i=0xipi
con pi ∈ B[d−1]. Per ipotesi induttiva, visto che pi è di indice ≤ d − 1,
esiste ri ∈ B, ki ∈ K[d−2] tale che pi = ri+ ki, cosicchè
p = Pn i=0xiri+ Pn i=0xiki = r0+ k0 con r0 =Pn i=0xiri ∈ B+e k0 = Pn
i=0xiki ∈ K[d−1]. Per ipotesi r0 = r+k”
con r ∈ B ∈, k” ∈ K. Quindi, p = r + k con r ∈ B, k = k0+ k” ∈ K[d−1].
Osservazione 2.2.1. Se 1 ∈ B allora B[∗] = P e ogni polinomio p ∈ P può
essere B-ridotto lungo K.
Se B = hmi, dove m è un insieme di monomi che contiene 1, allora B[d]
è generato da monomi della forma xα = xα0
xα” con xα0 ∈ m e |α”| 6 d. Il B-indice di xα è il minimo dei gradi di |α”| in una tale decomposizione.
Descriveremo un algoritmo di riduzione relativo a questo caso. Algoritmo 2.2.1. RIDUZIONE A B = hmi CON 1 ∈ m ⊂ (x)∗.
Per ogni monomio xα di B-indice d,
1. Decomponi xα come xα = x ixα
0
con xα0 ∈ B[d−1], per un appropriato i.
2. Calcola la B riduzione r0 ∈ B di xα0.
3. Calcola la B riduzione r ∈ B di xir0 ∈ B+ tramite la proiezione di B+
su B lungo K.
Il polinomio r è un B- resto di xα lungo K.
Osserviamo che il resto r non è necessariamente unico. Questo algoritmo fornisce uno dei possibili resti.
De nizione 2.2.3. La B-riduzione lungo K è canonica modulo (K) se e solo se (?) per ogni n ∈ N ed ogni p ∈ B[n] esiste una unica coppia di r ∈ B
Introduciamo ora una nozione che verrà usata estensivamente nel segui-to. È una proprietà di connettività, che ci consente di raggiungere ogni elemento dello spazio vettoriale a partire da un singolo elemento, attraverso la moltiplicazione per le variabili x1, i = 1, . . . , n.
De nizione 2.2.4. Sia B uno sottospazio vettoriale di K[x1, . . . , xn].
Di-ciamo che B è connesso a e0 ∈ B, se per ogni b ∈ B, o b = λe0, λ ∈ K
oppure esistono b0, . . . , bn ∈ B tali che
b =Pn
i=0xibi
con x0 = 1, bi un multiplo di e0 e deg(bi) < deg(b).
Una situazione tipica si ha quando B è generato da un insieme di mo-nomi m tali che per ogni m ∈ m, esistono i1, . . . , ik con m = xi1. . . xik e
xi1. . . xil ∈ B per l = 1, . . . , k. In altre parole, possiamo andare da 1 ∈ m ad
ogni elemento m ∈ m tramite moltiplicazione per una variabile stando in m. Questa situazione si veri ca ad esempio con le basi di Gröbner quando m è l'insieme dei monomi che non inizialmente dell'ideale I per un ssato ordi-namento monomiale; è una base dell'anello quoziente K[x1, . . . , xn]/I (vedi
teorema di Maculay).
Consideriamo ora uno spazio vettoriale B connesso ad 1 ed una proiezione N da B+ su B. Come abbiamo visto in precedenza, ogni polinomio p ∈ K[x1, . . . , xn]può essere B-ridotto lungo il nucleo di N. Adesso ci poniamo il
problema di decidere se tale riduzione è canonica usando solo le informazioni locali che abbiamo, ossia la proiezione N da B+ su B. Abbiamo quindi il
teorema seguente:
Teorema 2.2.5. Sia B uno spazio vettoriale di K[x1, . . . , xn] connesso ad
1. Sia N : B+ → B una mappa K-lineare tale che N
|B = I, ossia l'identità
sullo spazio vettoriale B. Sia I = (ker(N)) l'ideale generato dal nucleo di N. De niamo
Mi : B → B
b 7→ N (xib)
Le due proprietà sono equivalenti:
1) Per tutti gli i tali che 1 ≤ i, j ≤ n, Mi◦ Mj = Mj◦ Mi.
2) P = B ⊕ I.
Se queste proprietà sono veri cate, la mappa di B-riduzione lungo ker(N ) è canonica.
Il teorema verrà dimostrato in 2 passi: per prima cosa, descriveremo la normalizzazione N in termini degli operatori Mi. Per ogni α = (α1, . . . , αn) ∈
Nn, denotiamo con Mα l'operatore M1α1 ◦ . . . ◦ Mnαn. Osserviamo che se gli
operatori Mi commutano, Mα è indipendente dall'ordine nel quale
compo-niamo gli operatori. Per linearità, per ogni p ∈ P , de compo-niamo anche p(M), che è ottenuto sostituendo in p alle variabili xi l'operatore Mi. Per convenzione,
poniamo M0 = I.
Proposizione 2.2.1. Si assuma che lo spazio vettoriale B sia connesso ad 1 e che gli operatori Mi commutino. Allora per ogni b ∈ B+, N (b) = b(M)(1).
Dimostrazione. Proveremo prima per induzione sul grado che per b ∈ B, abbiamo b(M)(1) = b. Se b = 1, allora abbiamo b(M)(1) = M0(1) = 1,
che prova la proprietà per polinomi in B di grado 0. Assumiamo vera la proposizione per tutti i b0 ∈ B di grado 6= 0 e < d. Per ipotesi, per ogni
polinomio b ∈ B di grado ≤ d, esistono b0, . . . , bn ∈ B tali che b = Pni=0xibi
con deg(bi) < d. Allora per ipotesi induttiva abbiamo:
b(M)(1) = ( n X i=0 xibi)(M)(1) = n X i=0 Mi◦ bi(M)(1) = n X i=0 Mi ◦ bi(M)(1) = n X i=0 Mi(bi) = n X i=0 N (xibi) = N ( n X i=0 xibi) = N (b) = b per N = I su B.
Deduciamo adesso la proprietà per gli elementi della forma b = xib0 con
b0 ∈ B . Dalla de nizione,
N (xib0) = Mi(b0) = Mi(b0(M))(1) = b(M)(1).
Per linearità, si estende a B+.
Il secondo passo consiste nel descrivere l'ideale I generato dal ker(N) in termini degli operatori Mi
Proposizione 2.2.2. Sia B un K-spazio vettoriale connesso ad 1. Sia N : B+ −→ B una mappa K−lineare tale che N|B = I dove I è l'identità su B; siano Mi operatori de niti da
Mi : B → B
b 7→ N (xib)
- hp(x) − p(M)(1)ip∈B.
- {p ∈ P tali che p(M)(1) = 0}.
Dimostrazione. Per ogni p ∈ K[x1, . . . , xn], sia σ(p) = p(M)(1) ∈ B e sia
J = hp(x) − σ(p)ip∈K[x1,...,xn].
Proveremo come prima cosa che J coincide con l'ideale J0 = {p ∈ K[x1, . . . , xn] tali che p(M)(1) = 0}.
Secondo la proposizione (2.2.1) abbiamo
(p(x) − σ(p))(M))(1) = σ(p) − σ(p)(M)(1) = σ(p) − σ(p) = 0
che prova J ⊂ J0. Viceversa,per ogni p ∈ J0, tale che σ(p) = p(M)(1) = 0,
abbiamo
p(x) = p(x) − σ(p) ∈ J, che dimostra che J = J0 è un ideale di K[x
1, . . . , xn].
Dimostriamo adesso che J = I. Dato che N ◦ N = N, il nucleo ker(N) è generato dai polinomi b − N(b), b ∈ B+. Quindi, in base alla proposizione
2.2.1, I = (ker(N)) è generato dai polinomi b − b(M)(1) per b ∈ B0, il che
implica I ⊂ J. Viceversa ora dimostriamo per induzione sul grado che J ⊂ I. Per ogni α 6= 0 ∈ Nn, esiste i ∈ N e α0
∈ Nn tale che xα = x ixα 0 . Abbiamo xα− Mα(1) = x i(xα 0 − Mα0(1)) + x iMα 0 (1) − Mi◦ Mα 0 (1)
Per induzione, l'elemento (xα0
− Mα0
(1)) ∈ J è anche in I. Inoltre denotando bα0 = Mα
0
(1), abbiamo xibα0 − Mi(bα0) = xibα0 − N (xibα0) ∈ Ker(N ) ⊂ I,
che prova che xα− Mα(1) ∈ I. Per linearità, ciò implica che J ⊂ I e I = J
Dimostriamo ora il teorema principale di questa sezione Dimostrazione del teorema 2.2.5.
2 ⇒ 1. Se P = B ⊕ I allora B ∩ I = {0}. Dato che per ogni b ∈ B, abbiamo Mi(b) ≡ xib modulo I, ne deduciamo che per ogni 1 ≤ i, j ≤ n,
abbiamo
modulo I. Ma abbiamo anche (Mi ◦ Mj − Mj ◦ Mi)(b) ∈ hBi. Quindi,
(Mi◦ Mj− Mj ◦ Mi)(b) ∈ hBi = 0.
1 ⇒ 2. Consideriamo la mappa σ : P → B
p 7→ p(M )(1)
che è suriettiva in virtù della proposizione 2.2.1: per ogni b ∈ B, σ(b) = b. Per la proposizione 2.2.2 il suo nucleo è l'ideale I = (ker(N)), che prova che B è isomorfo a K[x1, . . . , xn]/I e K[x1, . . . , xn] = B ⊕ I.
Osservazione 2.2.2. L'ipotesi che B sia connesso ad 1 è necessaria per la dimostrazione del teorema. Consideriamo come esempio il caso in cui B = h1, x, x3i e N de nito su B+ = h1, x, . . . , x4i da
N (1) = 1, N (x) = x, N (x2) = 0, N (x3) = x3, N (x4) = x3.
Allora, l'ideale generato da ker(N) è I = (x2). C' è solo un operatore M 1,
cosicchè l'ipotesi di commutazione è ovviamente soddisfatta, ma {1, x, x3}
non è una base di K[x1, . . . , xn]/I. B ∩ I = hx3i.
Nel prosieguo descriveremo un nuovo algoritmo per il calcolo della tavola di moltiplicazione di un'algebra quoziente di dimensione zero, basata sul cri-terio del teorema 2.2.5. Più precisamente, calcoliamo la normalizzazione da B+ a B, che produce direttamente la tavola di moltiplicazione delle variabili xi, e di conseguenza le radici del sistema tramite il calcolo degli autovettori.
Facendo il confronto col calcolo delle basi di Gröbner, anzichè considerare riduzioni a due a due, manipoliamo le matrici dei coe cienti dei polinomi, osservando globalmente la loro struttura. Questo ci consente di sfruttare que-sta struttura coinvolta nella computazione e porta ad algoritmi per polinomi con coe cienti approssimati la cui stabilità numerica può essere analizzata più chiaramente. Siano f1, . . . , fm ∈ K[x1, . . . , xn] m polinomi e sia L uno
spazio vettoriale connesso ad 1 e contenente f1, . . . , fm ∈ K[x1, . . . , xn]. Sia I
l'ideale di K[x1, . . . , xn] generato da f1, . . . , fm ∈ K[x1, . . . , xn]. Assumiamo
che A = K[x1, . . . , xn]/I sia zero-dimensionale. De niamo poi per induzione
i seguenti spazi vettoriali: - K0 = hf1, . . . , fmi.
- Kn+1= Kn+∩ L, n ≥ 0.
Poichè L è uno spazio vettoriale nito, la successione crescente Kn è
stazio-naria; indichiamo con K∗ l'unione di tutti gli spazi vettoriali Kn. Per
costru-zione, abbiamo K∗ ⊂ I. Assumiamo 1 non appartenente a K∗, altrimenti
Proposizione 2.2.3. Siano B, L, K∗ sottospazi vettoriali di K[x1, . . . , xn]
tali che B uno spazio supplementare di K∗ in L, connesso ad 1 assumiamo
inoltre che B+ ⊂ L. Sia N la proiezione di L su B lungo K ∗ e
Mi : B → B
b 7→ Mi(b) = N (xib)
Allora abbiamo Mi◦ Mj = Mj◦ Mi per 1 ≤ i, j ≤ n
Dimostrazione. Sia ρI − N la proiezione su K∗ lungo B. Poichè per ogni
b ∈ B e per 1 ≤ i, j ≤ n abbiamo
Mj◦ Mi(b) = Mj(xib − ρ(xib)) = xj(xib − ρ(xib)) − ρ(xixjb − xjρ(xib))
= xixjb + xjk1+ k2
con k1, k2 ∈ K∗. In maniera analoga abbiamo
Mi◦ Mj(b) = xixjb + xik10 + k 0 2 con k0 1, k 0 2 ∈ K∗, cosicchè (Mj◦ Mi− Mi◦ Mj)(b) = xjk1+ k2− xik10 − k20 ∈ K∗+.
Per come sono de niti gli operatori Mi, abbiamo anche
(Mj ◦ Mi− Mi◦ Mj)(b) ∈ B
ma B ∩ K+
∗ = B ∩ K∗+∩ L = B ∩ K∗ = {0}. Di conseguenza, gli operatori
Mi commutano.
Teorema 2.2.6. Siano B, L, K∗ sottospazi vettoriali di K[x1, . . . , xn]tali che
B sia uno spazio supplementare di K∗ in L, connesso ad 1. Assumiamo che
B+ ⊂ L. Allora K[x
1, . . . , xn] = B ⊕ I e la B- riduzione lungo K = K∗∩ B+
è canonica modulo I = (f1, . . . , fm).
Dimostrazione. Assumiamo che B ⊕ K∗ = L e B+ ⊂ L. Sia N la
proiezione di L su B lungo K∗ e sia Mi : B → B tale che per ogni b ∈ B,
Mi(b) = N (xib). Denotando con K = K∗ ∩ B+, abbiamo B+ = B ⊕ K.
La proposizione 2.2.3 ci dice che gli operatori Mi commutano. Cosi per il
teorema 2.1.5 abbiamo K[x1, . . . , xn] = B ⊕ J dove J è l'ideale generato da
Per costruzione, dato che K ⊂ K∗ ⊂ I, abbiamo J ⊂ I. Proviamo adesso
per induzione sul grado che, per ogni p ∈ L, abbiamo N(p) = p(M)(1). La proprietà è ovviamente vera per polinomi di grado 0. Assumiamo che sia vera per polinomi di grado < d e sia p ∈ L un polinomio di grado d. Poichè L è connesso ad 1, esistono p1, . . . , pn∈ L tali che
p =Pn i=0xipi
con deg(pi) < d. Deduciamo che
p − p(M)(1) =Pn
i=0xi(pi− pi(M)(1) + xipi(M)(1) − Mi(pi(M)(1)).
Per induzione, pi − pi(M)(1) ∈ K∗. Inoltre poichè pi(M)(1) ∈ B, ki =
xipi(M)(1) − Mi(pi(M)(1) è in K cosicchè
p − p(M)(1) ∈ (K+
∗ ) ∩ L = K∗.
Questo implica che, per ogni p ∈ L la proiezione N(p) di p su B lungo K∗ è
p(M)(1) : N(p) = p(M)(1). Dato che fj ∈ K∗ ⊂ L e N(fj) = 0 = fj(M)(1)
deduciamo dalla proposizione 2.1.10 che fj ∈ J, cosicchè I = J. Questo
prova K[x1, . . . , xn] = B ⊕ I dove I = (K).
Il teorema 2.2.6 conduce al seguente algoritmo per costruire la funzione Normal Form in A = K[x1, . . . , xn]/I
Algoritmo 2.2.2. NORMAL FORM PER A.
INPUT: Siano f1, . . . , fm ∈ K[x1, . . . , xn]e I = (f1, . . . , fm)e assumiamo
che A = K[x1, . . . , xn]/I sia zero dimensionale. Sia L uno spazio vettoriale
nito di K[x1, . . . , xn] contenente f1, . . . , fm e connesso ad 1.
(1) K0 = hf1, . . . , fmi.
(2) Finché Kn6= Kn−1, calcola Kn+1 = Kn+∩ L, sostituisci n con n + 1.
(3) Calcola uno spazio vettoriale supplementare B di K∗(= Kn0) che è
connesso ad 1.
(4) Se B+ non è ⊂ L, sostituisci L con L+ e vai al passo (2).Altrimenti
stop.
OUTPUT : la B-riduzione lungo K∗ è canonica modulo l'ideale
Questo algoritmo necessariamente termina. Altrimenti L conterrebbe i multipli di (f1, . . . , fm) di grado k, con k grande quanto si vuole. Di
con-seguenza, L conterrebbe gli S-polinomi e i resti coinvolti nel calcolo della base di Gröbner di (f1, . . . , fm) per un ssato ordinamento monomiale. In
altre parole, L conterrebbe una base di Gröbner di I = (f1, . . . , fm). Cosí
uno spazio supplementare B di K∗ in L connesso ad 1 avrebbe dimensione
D = dimK(K[x1, . . . , xn]/I) cosicchè B+ ⊂ Lse k > D. Secondo il teorema
2.2.6 quando l'algoritmo termina la B riduzione lungo K = K∗∩Bè canonica
modulo I. Poichè L è connesso ad 1, lo spazio vettoriale B connesso ad 1 e supplementare a K∗ può essere calcolato in modo incrementale, iniziando da
1 (nel caso in cui 1 non appartenga a K∗).
Prima di continuare ad esaminare la teoria delle Border Bases in maniera più dettagliata, torniamo ad una delle domande iniziali, ossia ci chiediamo se le Border Bases siano numericamente stabili. Vediamo l'esempio seguente. Esempio 2.2.1. Sia P = Q[x, y], sia I = 1
4x 2 + y2 − 1, x2+ 1 4y 2− 1 e sia ˜ I = 14x2+ y2+ εxy − 1, x2+ 1 4y 2+ εxy − 1
dove ε è un numero piccolo. Allora sia I che ˜I ammettono border bases rispetto ad O = {1, x, y, xy}. Il border di O è ∂O = {x2, x2y, xy2, y2}. La O-border bases di I è
x2−4 5, x 2y − 4 5y, xy 2− 4 5x, y 2− 4 5 . La O-border bases di ˜I è
x2+4 5εxy − 4 5, x 2y − 16ε 16ε2− 25x + 20 16ε2 − 25y, xy2+ 20 16ε2− 25x − 16ε 16ε2− 25y, y 2 +4 5εxy − 4 5
Quando eettuiamo una variazione da 0 a ε nei coe cienti relativi ad xy dei due generatori, si osserva che una border bases cambia in modo continuo nell'altra. Così le border bases hanno un comportamento numericamente stabile rispetto a piccole perturbazioni dei coe cienti di xy. Inoltre, questo esempio mostra anche come le Basi di Gröbner non preservano la simmetria del sistema di equazioni dato mentre le border bases lo fanno.
2.3 Caratterizzazione
In questa sezione svilupperemo ulteriormente l'analogia tra Border Basis e Gröbner Basis. Più precisamente, caratterizzeremo le Border bases in diversi
modi che ricalcano la caratterizzazione delle Gröbner Basis ma vedremo an-che una maniera di caratterizzare le Border Basis an-che non ha analogo nelle Gröbner Basis. Continueremo ad utilizzare le notazioni e ipotesi introdotte in precedenza. In particolare, sia O = {t1. . . tµ} un order ideal in Tn, sia
∂O = {b1. . . bν}il suo border, sia G = {g1. . . gν}una O-border bases, sia al
G la upla (g1, . . . , gν), e sia I ⊆ P l'ideale zero-dimensionale generato da G.
Abbiamo la seguente proposizione.
Proposizione 2.3.1. (Border bases e Special Generation)
Stanti le notazioni precedenti, l'insieme G è una O-border bases di I se e solo se le seguenti condizioni equivalenti sono soddisfatte.
a) Per ogni f ∈ I \ {0}, esistono polinomi f1, . . . , fν ∈ P tali che
f = f1g1+ . . . + fνgν e deg(fi) 6 indO(f ) − 1 ogni volta che fi 6= 0.
b) Per ogni f ∈ I \ {0}, esistono polinomi f1, . . . , fν ∈ P tali che
f = f1g1+ . . . + fνgν e
max{deg(fi) | i ∈ {1, . . . , ν}, fi 6= 0} = indO(f ) − 1.
Dimostrazione. Come prima cosa dimostreremo che a) si mantiene se G è una O-border bases. Il Border Division Algorithm fornisce una rappresenta-zione f = f1g1+. . .+fνgν+c1t1+. . .+cµtµcon f1, . . . , fν ∈ P e c1, . . . , cµ∈ K
tali che abbiamo deg(fi) 6 indO(f ) − 1 per i = 1, . . . , ν. Allora abbiamo
c1t1+ . . . + cµtµ∈ I, e l'ipotesi implica c1 = . . . = cµ = 0.
Ora invece proviamo che a) implica b). Se deg(fi) 6 indO(f ) − 1 allora
la proposizione 2.1.2.b, fornisce
indO(figi) ≤ deg(fi) + indO(gi) = deg(fi) + 1 < indO(f ).
Per la proposizione 2.1.2.c deve esserci almeno un numero i ∈ {1, . . . , ν} tale che deg(fi) = indO(f ) − 1.
In ne, assumiamo che b) valga e che ci siano dei coe cienti c1, . . . , cµ∈ K
con c1t1+ . . . + cµtµ ∈ I. Applicando b) al polinomio f = c1t1+ . . . + cµtµ in
I otteniamo una rappresentazione f = f1g1+ . . . + fνgν con f1, . . . , fν ∈ P
tale che max{deg(fi) | i ∈ {1, . . . , ν}, fi 6= 0} = indO(f ) − 1 = −1. Da
cui f1 = . . . = fν = 0 e quindi c1 = . . . = cµ = 0. Di conseguenza l'insieme
G è una O-border bases.
Le basi di Gröbner vengono caratterizzate come un insieme di polinomi i cui leading term generano l'ideale dei leading term. Nella teoria delle border
bases i leading term vengono sostituiti dalle border form che sono de nite come segue.
De nizione 2.3.1. Dato f ∈ P , scriviamo f = a1u1 + . . . + asus con
coe cienti a1, . . . , as ∈ K \ {0} e termini u1, . . . , us ∈ Tn soddisfacenti
indO(u1) ≥ . . . indO(us).
a) Il polinomio BFO = P{i|indO(ui)=indO(f )}aiui ∈ P viene chiamato la
border form di f rispetto ad O. Per f = 0 poniamo BFO(f ) = 0.
b) Dato un ideale I ⊆ P , l'ideale BFO(I) = BFO(f )|f ∈ I) viene
chia-mato border form ideal di I rispetto ad O.
Per esempio, gli elementi della O-border prebases G hanno la border form BFO(gi) = bi. Ora caratterizziamo le Border Bases tramite il loro border
form ideal.
Proposizione 2.3.2. (Border Bases e Border Form Ideal)
Stante le notazioni precedenti, l'insieme G è una O-border bases di I se e solo se una delle seguenti condizioni equivalenti è soddisfatta.
B1 Per ogni f ∈ I, il supporto di BFO(f ) è contenuto in Tn\ O.
B2 Abbiamo BFO(I) = (BFO(g1), . . . , BFO(gν)) = (b1, . . . , bν).
Dimostrazione. Per prima cosa dimostreremo che una border basis sod-disfa la condizione B.1. Supponiamo che la border form di un polinomio f ∈ I \ {0}contenga un termine di O nel suo supporto. Allora tutti i termini nel supporto di f sono contenuti in O, ossia f = c1t1+ . . . + cµtµ per
oppor-tuni c1, . . . , cµ ∈ K. L'ipotesi implica c1 = . . . = cµ = 0, in contraddizione
a f 6= 0. Nel seguito dimostreremo che B1 implica B2. Poichè gi ∈ I,
ab-biamo bi ∈ BFO(I) per i = 1, . . . , ν. Per dimostrare l'inclusione inversa, sia
f ∈ I \ {0}. Da B1 e dalla proposizione 2.1.1.c, ogni termine nel supporto di
BFO(f ) è divisibile per un termine in O. Quindi la border form di f è
con-tenuta in (b1, . . . , bν). In ne, mostriamo che B2 implica che G è una border
bases. Siano c1, . . . , cµ elementi in K con f = c1t1 + . . . + cµtµ ∈ I. Allora
tutti i termini nel supporto di f hanno indice zero, e pertanto f = BFO(f ).
Da B2 e dalla proposizione 2.1.1.c, segue che c1 = . . . = cµ= 0.
Per caratterizzare le Border Bases in analogia alle Gröbner Bases de- niamo la rewrite relation associata a G. Sia f ∈ P un polinomio e sia
t ∈ Supp(f )un multiplo di un border term t = t0bi e sia c ∈ K il coe ciente
di t in f. Allora h = f − ct0g
i non contiene più il termine t. Aermiamo
che f riduce ad h in un passo usando gi e scriviamo f →gi h . La
chiu-sura ri essiva e transitiva della relazione g1
→, i ∈ {1, . . . , ν}, viene chiamata la rewrite relation associata a G ed è denotata con G
→. La relazione di equivalenza generata da G
→è denotata da ↔G. In forte contrasto con la teoria delle basi di Gröbner le rewrite relation associate alle border prebases non sono in generale Noetheriane. Lo dimostriamo col seguente esempio.
Esempio 2.3.1. Sia P = Q[x, y] e O = {1, x, y, x2, y2}. Allora O è un
order ideal con border ∂O = {xy, x3, x2y, xy2, y3}. Consideriamo la O-border
prebases G = g1, . . . , g5,dove g1 = xy − x2 − y2, g2 = x3, g3 = x2y, g4 = xy2, g 5 = y3. La catena di riduzioni x2y g1 → x3 + xy2 g2 → xy2 g1 → x2y + y3 g5 → x2y
può esser ripetuta inde nitamente e di conseguenza G
→non è Noetheriano. Il venir meno della Noetherianità ha conseguenze negative sulla rewrite relation
G
→. Fortunatamente la relazione di equivalenza ←→G preserva l'equivalenza modulo I.
Osservazione 2.3.2. Sia G
←→ la relazione di equivalenza rewrite relation associata ad una O-border prebases G = {g1, . . . , gν} e siano f1, f2, f3, f4 ∈
P. a) Se f1 G ←→ f2 e f3 G ←→ f4 allora f1+ f3 G ←→ f2+ f4. b) Se f1 G ←→ f2 allora f1f3 G ←→ f2f3. c) Abbiamo f1 G ←→ f2 se e solo se f1− f2 ∈ (g1, . . . , gν).
Osserviamo anche che ogni polinomio f con supporto in O è irriducibile rispetto a G
←→; in base alla proposizione 2.1.1.c, non contiene termini che possono essere ridotti. In particolare il normal remainder NFO,G(f )calcolato
tramite il Border Division Algorithm è irriducibile rispetto ad G
Proposizione 2.3.3. (Border Bases e Rewrite Relation) Nelle nota-zioni precedenti, l'insieme G è una O-border bases di I se e solo se le seguenti condizioni equivalenti sono soddisfatte.
C1 Per f ∈ P , abbiamo f G −→ 0 se e solo se f ∈ I. C2 Se f ∈ I è irriducibile rispetto a G −→, abbiamo f = 0.
C3 Per ogni f ∈ P , esiste un elemento h ∈ P tale che f →G h e h è
irriducibile rispetto a G
−→. L'elemento h è univocamente determinato. C4 La rewrite relation
G
−→ è con uente.
Dimostrazione Per prima cosa dimostreremo che una border bases ha la proprietà C1. Se un polinomio f ∈ P soddisfa f
G
−→ 0, è su ciente raccogliere le sottrazioni compiute dai singoli reduction step sul lato destro per ottenere f ∈ (g1, . . . , gν). Viceversa, sia f ∈ I. Applichiamo il Border
Division Algorithm ad f. L'algoritmo esegue reduction step usando elementi di G per calcolare il normal remainder NFO,G(f ) ∈ hOiK. Poichè f ∈ I,
abbiamo inoltre NFO,G(f ) ∈ I. L'ipotesi che G sia una border bases fornisce
N FO,G(f ) ∈ I ∩ hOiK, ossia abbiamo f G
−→ 0. Per dimostrare che C1 implica
C2, notiamo che C1 mostra f G
−→ 0per f ∈ I. Così un polinomio f ∈ I che è irriducibile rispetto a G
−→ deve essere zero. Di seguito proveremo che C2
implica C3. Sia f ∈ P ; il Border Division Algorithm esegue una riduzione
f →G N FO,G(f ), cioè esiste una riduzione ad un polinomio che è irriducibile
rispetto a G
−→. Supponiamo che f −→ hG e h sia irriducibile rispetto a −→G . Allora h − NFO,G(f ) ∈ I e il supporto di questa dierenza è contenuto in
O; così è irriducibile rispetto a −→G e C2 fornisce h = NFO,G(f ). Mettendo
tutto insieme, il normal remainder di f ha le proprietà richieste da C3. Ora
dimostriamo che C3 implica C4. Siano f1 G
−→ f2 e f1 G
−→ f3 due riduzioni.
Il Border Division Algorithm fornisce f1 G
−→ N FO,G(f2)e f1 G
−→ N FO,G(f3).
Poichè i normal remainder sono irriducibili rispetto a →G, la condizione C 3
implica NFO,G(f2) = N FO,G(f3). Quindi ci sono riduzioni
f2 G
−→ f4 e f3 G
−→ f4
con f4 = N FO,G(f2) = N FO,G(f3). In ne, per dimostrare che G è una
border bases se soddisfa C4, possiamo usare l'osservazione 2.3.2 e procedere
come nella dimostrazione di C4) ⇒ C1) nella proposizione 2.2.2 in Kreuzer,
Ora passiamo ad una caratterizzazione delle Border Bases che non ha analogo nelle Gröbner Bases. Poichè la classe di resto degli elementi di O ge-nera K[x1, . . . , xn]/I come spazio vettoriale sul campo K, possiamo descrivere
la struttura di anello di questo spazio vettoriale moltiplicando i generatori per una indeterminata e descrivendo gli eetti che questa moltiplicazione produce.
De nizione 2.3.3. Sia G = {g1, . . . , gν} una O-border bases, cioè sia
gj = bj− µ
X
i=1
αijti
con αij ∈ K per i = 1, . . . µ e e j = 1, . . . , ν. Dato r ∈ {1, . . . , n}, de niamo
la r-esima formal multiplication matrix χr = (ξ (r)
kl ) di G con
ξkr(r) = δki, if xrtl = ti αkj, if xrtl = bj
dove δki = 1 se k = i e δki = 0 altrimenti.
Le formal multiplication matrix codi cano la seguente procedura. Mol-tiplichiamo un elemento di hOik per l'indeterminata xr. Ogni volta che
xrti = bj è contenuto nel border, riduciamo tramite il corrispondente border
polynomial gj cosicchè il risultato sta in hOik. Elementi
v = c1t1+ . . . + cµtµ∈ hOiK
vengono codi cati come vettori colonna (c1, . . . , cµ)tr ∈ Kµ. Quindi xrv
cor-risponde a χr(c1, . . . , cµ)tr. Osserviamo che tutti le componenti della matrice
ξkl(r) sono determinate dai polinomi g1, . . . , gν. Il teorema seguente
caratte-rizza le border bases tramite la proprietà che le loro formal multiplication matrix commutino.
Teorema 2.3.4. Border Bases e Matrici Commutative
Sia O = {t1, . . . , tµ} un order ideal, sia G = {g1, . . . , gν} una O-border
prebases, e sia I = (g1, . . . , gν). Allora le seguenti condizioni sono equivalenti.
