Border Bases Algorithm 2

Denizione 3.2.6. Siano V e W sottospazi vettoriali di K[x1, . . . , xn] e sia

v0 ∈ V.

1) Sia W+ _{:= W + x}

1W + . . . + xnW.

2) Induttivamente deniamo i sottospazi vettoriali

Allora V è connesso a v0 se la catena ascendente V0 ⊆ V1 ⊆ V2 ⊆ . . .

converge a V nel senso che ∪k≥0Vk = V.

Quando V è generato da un insieme di termini diciamo anche che l'insieme dei termini è connesso a v0. L'insieme dei termini {1, x, xy} è connesso ad 1,

ma non è un order ideal. Nell'algoritmo di Mourrain, l'insieme dei termini connessi ad 1 svolgono il ruolo che gli order ideal svolgono per le border bases. Per semplicità di esposizione, introduciamo i seguenti concetti.

Denizione 3.2.7. Sia I ⊆ P un ideale e B ⊆ P un sottospazio vettoriale. Chiamiamo B uno Spazio base di Mourrain per I se è connesso ad 1 e se P = B L I come spazi vettoriali.

Algoritmo 3.2.8. (Mourrain's Generic Algorithm)

Sia F := {f1, . . . , fs} ⊂ P un insieme di polinomi che generano un ideale

zero-dimensionale I = hFiP. Il seguente algoritmo calcola uno spazio base

di Mourrain B per I.

M1) Determina L ⊆ P un sottospazio vettoriale di dimensione nita che sia

connesso ad 1 che contenga f1, . . . , fs.

M2) Sia K0 il sottospazio vettoriale hf1, . . . , fsiK. Sia l = 0.

M3) Calcola Kl+1 := K_l+T L.

M4) Se Kl+1 6= Kl allora aumenta l di uno e vai al passo M3

M5) Calcola un sottospazio vettoriale B connesso ad 1 tale che L = B L Kl

M6) Se B+ 6⊆ L allora sostituisci L con L+ e vai al passo 3. Altrimenti

restituisci B e stop.

Mourrain si soerma sul passo M5, poichè L è connesso ad 1, lo spazio

vettoriale B connesso ad 1 e supplementare a K∗ [ = Kl nel passo M5] può

essere calcolato incrementalmente, partendo da 1 (nel caso in cui 1 6∈ K∗).

In ogni caso, non specica come questo calcolo debba esser eettuato. Non siamo a conoscenza di un esempio il cui risultato sia un insieme di termini connessi ad 1 ma non un order ideal. Il problema di rendere il passo M5

esplicito è il punto di partenza per lo sviluppo del border bases algorithm che andremo a descrivere.

In questa sezione presenteremo un adattamento dell'algoritmo di Mour- rain alle border basis; lo faremo in vari passi iniziando con l'approfondire un concetto fondamentale dell'algoritmo di Mourrain.

Denizione 3.2.9. Siano F ⊆ L sottospazi vettoriali di K[x1, . . . , xn]. Pen-

siamo ad L come l' universo in cui i nostri calcoli vengono eseguiti. De- niamo induttivamente i sottospazi vettoriali

F0 := F e Fk+1 := Fk+∩ L per k = 0, 1, 2, . . .

L'unione FL := ∪k≥0Fk della catena ascendente F0 ⊆ F1 ⊆ F2 ⊆ . . . viene

chiamato L-stable span di F. In particolare, se F := {f1, . . . , fs} è un

insieme di polinomi che generano F = hFiK, allora scriveremo anche FL al

posto di FL.

Questa denizione è motivata dal caso speciale L = K[x1, . . . , xn] in

cui il K[x1, . . . , xn]-stable span eguaglia l'ideale generato da F, cioè FP =

hf1, . . . , friP. Ma per forza di cose, per ragioni di calcolo, preferiamo che L

sia un universo di dimensione nita. Ora elencheremo alcune proprietà di base dello stable span che serviranno nel seguito.

Lemma 3.2.10. Siano F ⊆ G ⊆ U ⊆ L sottospazi vettoriali di = K[x1, . . . , xn].

Allora valgono le seguenti relazioni.

F ⊆ FL, FL = (FL)L, FL⊆ GL, FU ⊆ FL, e FL = (FU)L.

Dimostrazione. Le prime due relazioni sono conseguenza immediata della denizione di stable span. Siano poi F0 := F e Fk+1 := Fk+∩ L per k ∈ N.

Analogamente deniamo Gk per k ∈ N. Da F ⊆ G e

Fk+1 = F_k+∩ L ⊆ G+_k ∩ L = Gk+1

deduciamo induttivamente Fk ⊆ Gk per tutti i k. Quindi

FL= ∪kFk ⊆ ∪kGK = GL

che prova la terza relazione. La dimostrazione della quarta proprietà è simile e verrà omessa. L'ultima relazione si dimostra applicando la terza relazione a F ⊆ FU per ottenere FL ⊆ (FU)L. L'inclusione inversa segue formando lo

L-stable span di ambo i lati di FU ⊆ FL.

Il prossimo obbiettivo sarà quello di descrivere esplicitamente come cal- colare lo stable span per l'universo L = hTn

≤diK. Questo include il sot-

to problema di calcolare un'estensione della base per gli spazi vettoriali hViK ⊆ hV ∪ GiK dove V è una base dello spazio più piccolo e G include

i generatori addizionali. Per questo calcolo utilizzeremo l'eliminazione di Gauss nella forma seguente.

Lemma 3.2.11. Sia σ un term ordering e V = {v1, . . . , vr} ⊂ P \ {0} un

insieme nito di polinomi con leading term dierenti a due a due e leading coecient uguali ad 1. Sia G = {g1, . . . , gs} ⊂ P un insieme nito di po-

linomi. L'algoritmo seguente calcola un insieme nito W ⊂ P con leading coecient uguali ad 1 e tali che V ∪ W ha leading term dierenti a due a due e hV ∪ WiK = hV ∪ GiK. L'insieme V o W può esser vuoto.

(1) Sia H := G e ρ := 0.

(2) Se H = ∅ allora restituisci W := {vr+1, . . . , vr+%} e stop.

(3) Scegli f ∈ H e rimuovilo da H. Sia i := 1. (4) Se f = 0 o i > r + % allora vai al passo 7.

(5) Se LTσ(f ) = LTσ(vi)allora sostituisci f con f −LCσ(f ).vi, reset i := 1

e vai al passo 4.

(6) Aumenta i di uno, e vai al passo 4.

(6) Se f 6= 0 allora aumenta % di 1, e poni vr+% :=

f LCσ(f )

. Continua col passo 2.

Dimostrazione. L'algoritmo mantiene l'invariante seguente: i leading term dei polinomi v1, . . . , vr+% sono a due a due dierenti e

h{v1, . . . , vr+%} ∪ {f } ∪ HiK = hV ∪ GiK. (3.1)

All'inizio, quando f non è ancora denito, {f} va interpretato come l'insieme vuoto.

Il loop nei passi 4 − 6 è nito, poichè in ogni iterazione o i cresce o viene resettato con una riduzione del leading term di f. La seconda possibilità può avvenire solo un numero nito di volte poichè σ è un buon ordinamento. Quindi dopo un numero nito di iterazioni i non viene resettato ulteriormente e, alla ne, sorpassa l'invariato upper bound r + %. La riduzione al passo 5 non modica lo span nell'equazione (3.1) e, quando il loop termina, o f = 0 oppure LTσ(f ) 6∈ {LTσ(v1), . . . , LTσ(vr+%)}. Anche il loop dei passi 2 − 7

termina: l'insieme H viene inizializzato come l'insieme nito G e dopo ogni iterazione rimuove un elemento da H mentre nessun altro elemento viene aggiunto. Così l'intero algoritmo termina.

Al termine, H = ∅ e {f} ⊆ {0, vr+%}, cosicchè l'invariante verica la

correttezza dell'algoritmo.

La ragione per cui usiamo vettori di base con leading term a due a due distinti è la seguente: se V = {v1, . . . , vr}è una base del sottospazio vettoriale

V ⊆ P con leading term a due a due distinti allora l'insieme LTσ{V } := {LTσ(v)|v ∈ V \ {0}}

dei leading term degli elementi di V eguaglia l'insieme dei leading term della sua base LTσ{V} := {LTσ(v1), . . . , LTσ(vr)}.

Nel seguito, renderemo più esplicita l'operazione + su un sottospazio vet- toriale hFiK ⊆ P. Con un abuso di notazione deniremo anche l'operazione

+ su un insieme di polinomi F := {f1, . . . , fr} ponendo

F+_{:= F ∪ x}

1F ∪ . . . ∪ xnF.

In questo modo abbiamo hFi+ K = hF

+_i K.

Proposizione 3.2.2. (Calcolo di uno Stable Span)

Sia F := {f1, . . . , fr} ⊂ P e L := hTn≤diK con f1, . . . , fr ∈ L, ossia tali che

d ≥ max{degfi|1 ≤ i ≤ r}.

Sia σ un degree compatible term ordering. L'algoritmo seguente calcola una base V dello stable span FL. Inoltre, i vettori della base hanno leading

term a due a due dierenti.

(1) Calcola una base V di hFiK con leading term a due a due dierenti.

(Applica il lemma a V = ∅ e G = F.) (2) Calcola un'estensione della base W0 _{:= {v}0

r+1, . . . , vr+%0 0} per

hViK ⊆ hV+iK

cosicchè gli elementi di V ∪ W0 _{hanno leading term a due a due die-}

renti. (Applica il lemma a V e G := V0_{\ V.)}

(3) Sia W := {vr+1, . . . , vr+%} := {v ∈ W0|deg(v) ≤ d} .

(4) Se % > 0 allora sostituisci V con V ∪ W, incrementa r di %, e vai al passo 2.

(5) Restituisci V

Dimostrazione. I passi 2−4 mantengono il seguente loop invariante. Ogni iterazione del loop nel passo 2 − 4 inizia con un insieme nito V con leading term dierenti a due a due e calcola un insieme nito W tale che V ∪ W ha leading term a due a due dierenti e

hViK ⊆ hV ∪ WiK = hV+iK ∩ L ⊆ L.

In particolare, V ∪ W è una base di hV+_i

K∩ L. Tramite il lemma 3.2.11, il

passo 1 calcola un insieme nito V con leading term dierenti a due a due. Cosi il loop invariante è inizializzato correttamente. Sempre tramite il lemma 3.2.11, il passo 2 determina una estensione dei vettori di base W0 _{tale che}

V ∪ W0 _{è una base di hV}+_i

K con leading term dierenti a due a due. Il passo

4 interseca questo sottospazio con L scartando i polinomi di grado maggiore di d; qui usiamo la degree compatibility di L = hTn

≤diK e di σ.

Un'altra iterazione viene chiamata nel passo 4 se e solo se una estensione W0 _{non vuota della base è stata calcolata. Poichè r aumenta di una quantità}

positiva % ad ogni nuova iterazione mentre il limite superiore r < dimKL

resta costante, questo loop termina. Dopo il termine il loop invariante diventa hViK = hVi+_K ∩ Lche dimostra la correttezza.

Lo stable span FL è contenuto in L cosi come nell'ideale generato da F,

ossia FL⊆ L ∩ hF iP. Il seguente esempio mostra che l'inclusione può essere

stretta e che, in universi non sucientemente larghi, questa approssimazione dipende dall'insieme di generatori F e non solo dall'ideale generato da hFiP.

Esempio 3.2.3. Sia F := {f1, f2, f3} con f1 := x2y2+ 1, f2 := x4,f3 := y4.

Inoltre, sia H := {1}. Gli insiemi F e H generano entrambi l'ideale banale h1iP perchè 1 = f2.f3− f12+ 2f1.

(1) Sia L := hTn

≤4iK. Allora FL = hF iK con dimKFL = 3, mentre HL= L

con dimKHL= 10

(2) Sia L := hTn

≤5iK. Allora FL = L = HL

Il calcolo sopra eseguito dello stable span include anche informazioni riguardo un order ideal che si candida per supportare una border bases.

Proposizione 3.2.3. Sia F := {f1, . . . , fs} ⊂ P e sia L = hT≤dniK tale che

F ⊆ L. Allora esiste un order ideal O tale che L = FL⊕ hOiK

Cioè, se σ è un term ordering grado compatibile e V := {v1, . . . , vr} una

base di FL con leading term dierenti a due a due allora LTσ{FL} è chiuso

rispetto ai multipli in L, ossia se t ∈ Tn

≤d e LTσ(v)|t per qualche v ∈ FL

allora t = LTσ(w) per qualche w ∈ FL. In maniera duplice questo stabilisce

che O = Tn

≤d \ {LTσ(v1), . . . , LTσ(vr)} è un order ideal. Soddisfa inoltre la

decomposizione in somma diretta scritta sopra.

Dimostrazione. La denizione di O e l'exchange lemma di Steinitz pro- ducono

L = hLTσ(v1), . . . , LTσ(vr)iK⊕ hOiK = hv1, . . . , vriK⊕ hOiK = FL⊕ hOiK.

Per provare la proprietà dell'order ideal O, dobbiamo dimostrare che per ogni termine t ∈ Tn _{\ O} e ogni indeterminata x

i il prodotto xit ∈ Tn\ O.

Poichè O ⊆ Tn

≤d, dobbiamo solo considerare il caso xit ∈ Tn≤d. Poichè t 6∈ O,

c'è un elemento della base v ∈ V tale che t = LTσ(v). Abbiamo

xiv ∈ V+ ⊆ F_L+ e LTσ(xiv) = xit ∈ Tn≤d.

Poichè σ è degree compatible, xiv ∈ hTn≤diK = L. Così xiv ∈ F_L+∩ L = FL,

e quindi LTσ(xiv) ∈ LTσ{FL} = LTσ{V} che mostra che xit ∈ Tn≤d\ O .

La prossima proposizione descrive le basi che serviranno come criteri di stop per il Border Bases Algorithm. Controlla se un candidato order ideal supporta realmente una border bases. Va notato come il caso speciale L = P e ˜I = I assomigli alla denizione di border bases.

Proposizione 3.2.4. Sia L un sottospazio vettoriale di P . Sia ˜I un sotto- spazio vettoriale di un ideale zero-dimensionale I ⊆ P tale che ˜I+_{∩ L = ˜I}

e h˜IiP = I (In un certo senso, ˜I è un L-stable approssimazione di I). Sia

O = {t1, . . . , tµ} un order ideal tale che

L = ˜I ⊕ hOiK.

Dimostrazione.Per ogni border term bj ∈ ∂O ⊆ L la decomposizione in

somma diretta denisce un polinomio gj ∈ ˜I in accordo a

bj = gj+Pm_i=1αijti ∈ ˜I ⊕ hOiK

Per costruzione, G := {g1, . . . , gν} è una O-border prebases.

Consideriamo due neighbouring prebases polinomi gk, gl. Il supporto del

loro S-polinomio S(gk, gl) ∈ ˜I+ è contenuto in O+. Quindi ci sono coecienti

cj ∈ K tali che h := S(gk, gl) −

Pν

j=1cjgj ha il suo supporto in O. Allora

h ∈ ˜I+_∩hOi

K = ˜I+∩L∩hOiK = ˜I ∩hOiK = {0}. Dal criterio di Buchberger

per le border bases , G è una border bases di h˜IiP = I

Il seguente processo di riduzione trasforma un insieme di polinomi idoneo nella border bases cercata.

Algoritmo 3.2.12. (Final Reduction Algorithm)

Sia F = {f1, . . . , fs} ⊂ P un sistema di generatori di un ideale zero-dimensionale

I. Sia σ un term ordering compatibile con la graduazione. Sia L un order ideal (ad esempio L = Tn

≤d), V una base dello span FL con leading term a

due a due dierenti, e sia O := L \ LTσ(V) tale che

L = FL⊕ hOiK e ∂O ⊆ L

Allora il seguente algoritmo calcola la Oσ{I}-border bases {g1, . . . , gν}.

(F1) Sia VR:= ∅.

(F2) Sia V = ∅ allora vai al passo (F8).

(F3) Determina in V l'elemento v avente leading term minimo. Rimuovilo

da V. (F4) Sia H := Supp(v) \ ({LTσ(v)} ∪ O). (F5) Se H = ∅ allora aggiungi v LCσ(v) a VR e vai al passo (F2).

(F6) Per ogni h ∈ H determina wh ∈ VR e ch ∈ K tali che LTσ(w) = h e

h 6∈ Supp(v − ch· wh).

(F7) Sostituisci v con v − P_hch· wh, aggiungi

v

LCσ(v) a V

R e vai al passo

(F8) Sia ∂O = {b1, . . . , bν}. Determina per ogni bj ∈ ∂O il polinomio gj ∈

VR con bj = LTσ(gj). Restituisci {g1, . . . , gν}.

Dimostrazione. L'ipotesi dà una base V di FL in modo che per ogni

bj ∈ ∂O ci sia un hj ∈ V con bj = LTσ(hj). Abbiamo quasi raggiunto

l'obbiettivo, ma è ancora possibile che Supp(hj) contenga termini fuori da

{bj} ∪ O. L'algoritmo riduce questi termini non desiderati.

Il loop dei passi (F2) − (F7)mantiene l'invariante hV ∪ {v} ∪ VRiK = FL

dove l'insieme V ∪ {v} ∪ VR ha leading term a due a due distinti. (Inizial-

mente, quando v non è denito, interpretiamo {v} come l'insieme vuoto). Inoltre, gli elementi di VR sono polinomi g con Supp(g) ⊆ {LTσ(g)} ∪ O

e LCσ(g) = 1. Questa proprietà invariante si mantiene prima della prima

iterazione perchè la prima parte dell'algoritmo ha calcolato V come base di FL con leading term a due a due dierenti e il passo (F1)denisce VR come

l'insieme vuoto. Ogni iterazione rimuove da V gli elementi v con leading term minimo. Così, se Supp(v) contiene un termine fuori da {LTσ(v) ∪ O}

allora questo è necessariamente il leading term si qualche elemento in VR :

deve essere in T≤d\ O = LTσ{FL}, che eguaglia LTσ{V ∪ {v} ∪ VR}, mentre

non può essere in LTσ{{v} ∪ V}in virtù della minimalità di LTσ(v). Perciò

w e c nel passo (F6) esistono come stabilito. Il loop dei passi (F2) − (F7) è

nito poichè ogni iterazione rimuove un elemento dall'insieme nito V. Al termine l'invariante prova che abbiamo ottenuto una base di VR di FL con

leading term dierenti a due a due e che Supp(g) ⊆ {LTσ(g)} ∪ O per tutti

i g ∈ VR.

Abbiamo trovato polinomi gj ∈ VR⊆ FL⊆ I con

Supp(gj) ⊆ LTσ(gj) ∪ O,

con LCσ(gj) = 1, e {LTσ(g1), . . . , LTσ(gν)} = ∂O. Dalle ipotesi e dalla

proposizione 3.2.3, l'order ideal O supporta una border bases. Data l'unicità delle border bases, i polinomi calcolati g1, . . . , gν costituiscono questa O-

border bases.

Il Final Reduction Algorithm è più sottile di quanto possa sembrare a prima vista. L'informazione contenuta in V non è limitata all'avere per ogni per ogni border term un polinomio avente questo termine nel suo suppor- to. Nel provare a disfarsi del term ordering, prendiamo in considerazione il problema seguente.

Sia I un ideale zero-dimensionale e O un order ideal che supporta una border bases di I. Sia ∂O = {b1, . . . , bν} e siano v1, . . . , vν ∈ I polinomi con

bj ∈ Supp(vj) per tutti gli 1 ≤ i ≤ ν. Può esserci un algoritmo che calcola

la O-border bases {g1, . . . , gν} di I ?

La risposta è negativa. Per esempio, consideriamo l'ideale monomiale I := hx2_{, yi}

P in P := K[x, y]. L'order ideal O = {1, x} supporta la border

bases {y, xy, y2_{} e I contiene i polinomi y, xy, x}2_{+ x}3_{. Chiaramente, non ci}

sono modi di ottenere il polinomio di base x2 _{tramite riduzione usando solo}

i polinomi dati.

Siamo inne in grado di mettere insieme l'algoritmo principale. Algoritmo 3.2.13. (Border Bases Algorithm 2).

Sia F = {f1, . . . , fs} ⊂ P un insieme di polinomi che genera un ideale

zero-dimensionale I = hFiP. Sia σ un term ordering compatibile con la

graduazione. Il seguente algoritmo calcola la Oσ{I}-border bases {g1, . . . , g}.

(B1) Sia d := max{deg(fi) | 1 ≤ i ≤ s} e L := hTn≤diK

(B2) Calcola V = {v1, . . . , vr} una base di hFiK con leading term dierenti

a due a due.

(B3) Calcola W0 := {vr+10 , . . . , vr+%0 0}per hVi_K ⊆ hV+i_K cosicchè gli elementi

di V∪ hanno leading term a due a due dierenti. (B4) Sia W = {vr+1, . . . , vr+%} = {v ∈ W0 | deg(v) ≤ d}.

(B5) Se % > 0 allora sostituisci V con V ∪ W, incrementa r di % e vai al

passo (B3).

(B6) Sia O := Tn≤d\ {LTσ(v1), . . . , LTσ(vr)}.

(B7) Se ∂O 6⊆ L allora incrementa d di uno, aggiorna L := hTn≤diK, e

continua con lo step (B3).

(B8) Applica il Final Reduction Algorithm e restituisci i polinomi g1, . . . , gν

da esso calcolati.

Dimostrazione. Il passo (B1) inizializza L cosicchè F ⊆ L. Dalla propo-

sizione 3.2.2, passi (B2) − (B5)calcola una base V dello stable span FL con

leading term a due a due dierenti. Tramite la proposizione 3.2.3, passo (B6)

denisci un order ideal. Adesso consideriamo il loop dei passi (B3) − (B7).

Ogni nuova iterazione inizia con l'universo aggiornato L := hTn

≤diK e una

rispetto all'universo precedente U := hTn

≤d−1iK. Applicando la proposizione

3.2.1 all'insieme di polinomi ˜V, vediamo che i passi (B3) − (B5) calcolano

una base V dello stable span ˜VL, e il lemma 3.2.2 dà ˜VL = (FU)L = FL .

Quindi ogni iterazione nisce con una base aggiornata V di FL e un order

ideal O aggiornato tale che L = FL⊕ hOiK. Nel seguito controlliamo che si

verichino solo un numero nito di iterazioni. Sebbene l'order ideal Oσ{I} e

i polinomi della border bases gj non siano stati ancora calcolati, esistono. In

particolare ∂Oσ{I} = {LTσ(g1), . . . , LTσ(gν)}, e ci sono polinomi hj1, . . . , hjs

tali che

gj = hj1f1+ . . . + hjsfs per 1 ≤ j ≤ ν (3.2)

Sia ˜d := max({d} ∪ {deg(hji)fi | 1 ≤ i ≤ s, 1 ≤ j ≤ ν}). È suciente

considerare il caso in cui il loop non è terminato prima di raggiungere l'i- terazione con valore del parametro d = ˜d. Questa iterazione usa l'universo L = hTn_{≤ ˜d}iKe calcola una base V di FLcon leading term a due a due dierenti.

Dalla scelta di ˜d, tutti gli addendi hjifi nell'espansione (3.2) sono in L e quin-

di g1, . . . , gν ∈ FL. Abbiamo ∂Oσ{I} = {LTσ(g1), . . . , LTσ(gν)} ⊆ LTσ{FL}.

Poichè LTσ{FL} è chiuso per i multipli in L (proposizione 3.2.3), dedu-

ciamo Tn

≤ ˜d \ ∂Oσ{I} ⊆ LTσ{FL}. Quindi Oσ{I} contiene l'order ideal

O := Tn

≤ ˜d \ LTσ{FL} che è determinato dall'iterazione corrente. Questo

porta a ∂O ⊆ Oσ{I} ∪ ∂Oσ{I} ⊆ L e il loop termina.

Avendo raggiunto il passo (B8) abbiamo una base V di FL che soddisfa

tutte le ipotesi della proposizione 3.2.12. Quindi il Final Reduction Algori- thm calcola la O- border bases. Sopra abbiamo dimostrato che O ⊆ Oσ{I}.

Entrambe gli order ideal supportano border bases di I; in particolare, devono avere lo stesso numero di elementi e di conseguenza coincidono.

La Oσ{I}-border basis calcolata dall'algoritmo è una estensione della

Gröbner basis σ-ridotta. Ora descriveremo un esempio in cui questo al- goritmo si comporta meglio di quello di Buchberger.

Esempio 3.2.4. Consideriamo I l'ideale zero dimensionale generato da F := {f1, . . . , f5}

dove f1 = x3− x f2 = y3− y, f3 = x2y −1₂y −1₂y2,f4 = xy − x −1₂y + x2−1₂y2

e f5 = xy2 − x − 1₂y + x2 − 1₂y2. Questa è la O7-border bases calcolata

prima cosa calcoliamo la Oσ{I}-border bases seguendo gli step del Border

Bases Algorithm.

(B1) I generatori producono l'universo L := hT≤3iQ.

(B2) L'insieme dei generatori è una base di hFiQ con leading term a due a

due dierenti, quindi riscritta in base al DegLex V = {x3 _{− x, y}3 ₋

y, x2_{y −} 1 2y 2₋ 1 2y, x 2_{+ xy −} 1 2y 2_{− x −} 1 2y, xy 2_{+ x}2₋ 1 2y 2_{− x −} 1 2y}

(B3) Otteniamo V+ = {x4 − x2, x3y − xy, xy3 − xy, y4 − y2, x3y − 1₂xy2 − 1 2xy, x 2_y2₋ 1 2y 3 ₋ 1 2y 2_{, x}3_{+ x}2_{y −} 1 2xy 2_{− x}2₋ 1 2xy, x 2_{y + xy}2₋ 1 2y 3 ₋ x − 1₂y2_{, x}2_y2 _{+ x}2 ₋ 1 2xy 2 _{− x}2 ₋ 1 2xy, xy 3 _{+ x}2_{y −} 1 2y 3 _{− xy −} 1 2y 2_}.

Una estensione della base con leading term a due a due dierenti è W0 _{= {x}4_{− x}2_{, x}3_{y − xy, xy}3_{− xy, y}4_{− y}2_{, x}2_y2₋1 2y 3₋ 1 2y 2_}. (B4) W = W0∩ L = ∅

(B6) L'algoritmo calcola l'order ideal O = {1, x, y, y2, xy} avente border

∂O = {x2, xy2, x22, y3} che è contenuto nell'universo.

(B8) Sia VR:= ∅. Il Final Reduction Algorithm tratta (esamina?)gli elemen-

ti di V nel seguente ordine : v = x2_{+ xy −}1 2y 2_{− x −}1 2y (H = ∅), v = y3− y (H = ∅), v = xy2+ x2−1 2y 2_{− x −}1 2y (H = {x 2_{}; sostituisci} v con v1.(x2 + xy − 1₂y2 − x − 1₂y), così v = xy2 − xy ), v = x2y − 1 2y 2₋1 2y (H = ∅) e v = x

3_{− x (H = ∅). Alla ne viene restituita la}

border bases {x2_{+ xy −}1 2y 2_{− x −}1 2y, y 3_{− y, xy}2_{− xy, x}2_{y −}1 2y 2₋1 2y}

Dall'altro lato, l'algoritmo di Buchberger calcola i seguenti S-polinomi S12= −x6+x3y3+x4−xy3, S13 = −x4+x3y+x2−xy, S14= −x4+x3+x2−x,

S15= −x5+ x3y2+ x3− xy2,

S23= x2y3−y5−x2y+y3, S24= −y6+x2y3+y4−x2y, S25 = xy3−y4−xy+y2,

S34= −x2y2+ x2y +1₂y3−1₂y, S35= −x3y + x2y2+1₂xy2−1₂y3+1₂xy −1₂y2,

S45= +x2y2+ xy3 −1₂y4− x3− x2y − 1₂xy2.

La coppia di generatori (f1, f2) e (f2, f4) hanno leading term relativamen-

te primi; lasciamo che l'algoritmo di Buchberger li trascuri. Allora gli S- polinomi riducono a zero, quindi il sistema di generatori è una border bases.. Come dierisce questo calcolo? Il calcolo della border bases richiede solo i termini no al terzo grado. Nel calcolo dell'algoritmo di Buchberger com- paiono i nove termini addizionali: x5_{, x}3_y2_{, x}2_y3_{, y}5_{, x}4_{, x}2_{y, x}2_y2_{, xy}3_{, y}4 (la

lista esclude i termini x6_{, x}3_y3_{, y}6 _{che compaiono nell'S-polinomio i cui gene-}

ratori hanno leading term relativamente primi). Così questo calcolo produce termini no al quinto grado che di conseguenza devono esser ridotti. Perciò anche in questo piccolo esempio osserviamo una ridondanza nell'algoritmo di Buchberger che viene evitata dal border bases algorithm.

Illustriamo adesso un algoritmo più complicato

Esempio 3.2.5. Consideriamo l'ideale su cui si annullano i punti (−1, 0, 0), (0, 0, 0), (1, 0, 0), (3, 0, 0), (5, 0, 0), (0, 0, 7) in A3_{(Q). È generato dall'insieme dei polinomi:}

z2_{+ 3y − 7z, yz − 4y, xz − 4y, y}2_{− 4y, xy − 4y,}

x5− 8x4_{+ 14x}3_{+ 8x}2_{− 15x + 15y}

Sia σ := DegRevLex. Il Border Bases Algorithm parte con l'universo hT3

≤5iK che consiste di 56 termini. Per calcolare lo stable span, l'algoritmo

esegue 4 estensioni lineari della base. Dopodichè ottiene l'order ideal {1, x, x2_{, x}3_{, x}4_{, y, z}}

il cui border è già contenuto nell'universo. L'universo non deve essere in- grandito. La border basis è l'insieme dei 12 polinomi

z2

+ 3y − 7z, yz − 4y, xz − 4y, y2 − 4y, xy − 4y, x2z − 16y, x2y − 16y, x3y − 64y, x4z − 256y, x4y − 256y, x5− 8x4_{+ 14x}3_{+ 8x}2_{− 15x + 15y}

L'algoritmo di Buchberger applicato a questi esempi funziona con S- polinomi no al grado 6,(ci sono S- polinomi di grado 7 ma appartengono a coppie con leading term relativamente primi). La dierenza in questo caso non è impressionante, ma sussiste.

Abbiamo anche alcune ottimizzazioni del Border Bases Algorithm. La seguente sostituisce l'uso di Tn

≤d come universo computazionale con order

ideal che vengono mantenuti più piccoli possibile.

Algoritmo 3.2.14. (Improved Border Bases Algorithm)

Sia F = {f1, . . . , fs} ⊂ P polinomi che generano I := hFiP un ideale zero

dimensionale. Sia σ un term ordering compatibile con la graduazione . Il seguente algoritmo calcola la Oσ{I}-border bases {g1, . . . , gν}.

(I1) Sia L l'order ideal generato da ∪r

i=1Supp(fi)

(I2) Calcola una base V di hFiK con leading term a due a due dierenti.

(I3) Calcola W0 _{una estensione della base per hVi}

K ⊆ hV0iK in modo che

gli elementi di V ∪ W0 _{abbiano leading term a due a due dierenti.}

(I4) Sia W := {w ∈ W0_|LT

σ(w) ∈ L}.

(I5) Se ∪w∈WSupp(w) 6⊆ L allora sostituisci L con l'order ideal generato da

L e ∪w∈WSupp(w) e continua col passo (I4).

(I6) Se W 6= ∅ allora sostituisci V con V ∪ W e continua col passo (I3). (I7) Sia O := L \ {LTσ(v)|v ∈ V.

(I8) Se ∂O 6⊆ L allora sostituisci L con l'order ideal L+ e continua col passo

(I3)

(I9) Applica il Final Reduction Algorithm e restituisci i polinomi g1, . . . , gν

da esso calcolati.

Dimostrazione. Per dimostrare che la procedura termina e che l'algoritmo è corretto, consideriamo i suoi loop seguendo l'ordine in cui appaiono. Il subloop dei passi (I4)-(I5) è nito perchè W ⊆ W0 _{implica che ogni istanza}

di L è contenuta nell'order ideal invariante generato da ∪v∈V∪W0Supp(v).

Poichè ogni nuova iterazione corrisponde ad un ampliamento di L all'interno di questo insieme invariante nito, possono esserci solo un numero nito di iterazioni.

Quando questo sottoloop termina, abbiamo hV∪WiK = hV ∪W0iK∩hLiK.

Il primo membro è contenuto nel secondo perchè l'ampliamento dell'universo nel passo (I5) assicura che la premessa w ∈ W, cioè LTσ(w) ∈ L, implica

Supp(w) ⊆ L. Per l'inclusione inversa sia

v = α1v1+ . . . + αrvr+ β1w1+ . . . + βsws in hLiK,

dove α1, . . . , αr, β1, . . . , βs ∈ K \ {0}, v1, . . . , vr ∈ V, e w1, . . . , ws ∈ W0.

Si assume che i vettori siano a due a due dierenti. Dobbiamo dimostrare che w1, . . . , ws ∈ W. Poichè i leading term di V ∪ W0 sono a due a due

dierenti, LTσ(v) eguaglia qualche LTσ(vi) o qualche LTσ(wj). Sappiamo

che Supp(vi) ⊆ L; quindi, nel primo caso, otteniamo

Nel secondo caso deduciamo da LTσ(wj) = LTσ(v) ∈ L che wj ∈ W.

Otteniamo

v − βjwj ∈ hV ∪ W0iK∩ hLiK.

L'inclusione desiderata segue per induzione.

Ora mostreremo che il loop nei passi (I3)-(I6) è nito. All'inizio di un'ite- razione arbitraria sia L contenuta in qualche Tn

≤d. Allora il criterio di scelta

del sottoinsieme LTσ(w) ∈ L e il fatto che σ è compatibile con la gradua-

zione producono Supp(w) ⊆ Tn

≤d. Così, per L ⊆ Tn≤d all'inizio della prima

iterazione, tutte le estensioni della base avvengono nello spazio di dimensione nita hTn

≤diK

Alla ne di questo loop, abbiamo hViK = hVi+K∩hLiK dovuto alle seguenti

identità . L'estensione della base nel passo (I3) dà hV ∪W0_i

K =hVi+K. Poichè

abbiamo passato il subloop (I4)-(I5), abbiamo hV ∪WiK = hV ∪ WiK∩ hLiK.

Inne, quando usciamo dal subloop nel passo (I6), abbiamo W = ∅ e quindi hViK = hV ∪ WiK.

Adesso, mostriamo che la denizione di O nel passo (I9) produce un or- der ideal. In maniera analoga alla dimostrazione della proposizione 3.2.3 sia t ∈ L \ O e consideriamo il caso xit ∈ L. Poichè t 6∈ O c'è un

v ∈ V con t = LTσ(v). Abbiamo xiv ∈ V+ e dalle considerazioni del ca-

so LTσ(xiv) = xit ∈ L, cioè xiv ∈ V ∪ W. Avendo passato il subloop

(I4)-(I5), deduciamo Supp(xiv) ⊆ L. Così xiv ∈ hVi+K ∩ hLiK. Dai ragio-

namenti fatti in precedenza questa intersezione è uguale a hViK. Poichè i

leading term di V sono dierenti a due a due, LTσ(xiv) ∈ LTσ{V}. Questo

dimostra xit ∈ L \ O.

Il loop nei passi (I3)-(I8) termina perchè, con ogni chiamata di una nuova

Nel documento Basi Border (pagine 63-79)