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 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.
b) Le formal multiplication matrices di G sono a due a due commutative. In questo caso le formal multiplication matrices rappresentano l'en- domor smo di moltiplicazione di P/I rispetto alle basi {t1, . . . , tµ}.
Dimostrazione. Siano X1, . . . , Xn le formal multiplication matrix corri-
spondenti a G = {g1, . . . , gν} che è O-border prebases data. Dimostreremo
come prima cosa che a) implica b). Poichè G è una O-border bases, l'insieme {t1, . . . , tµ} è base dello spazio vettoriale P/I su K, e ogni matrice χr de ni-
sce una mappa K-lineare ϕr : K[x1, . . . , xn]/I → K[x1, . . . , xn]/I. Vogliamo
dimostrare che ϕr è l'endomor smo corrispondente alla moltiplicazione per
xr. Consideriamo l'espansione : ϕr(t1) = ξ (r) 11t1+ . . . + ξ (r) µ1tµ ... ... ϕr(tµ) = ξ (r) 1µt1+ . . . + ξ (r) µµtµ
In queste espansioni possono veri carsi solo due casi. Il prodotto xrtl
eguaglia qualche termine ti nell'order ideal O oppure qualche termine bj
appartenete a ∂O. Nel primo caso abbiamo ϕr(tl) = ti = xrtl, e nel secondo
caso abbiamo ϕr(tl) = α1jt1 + . . . + αµjtµ = bj = xrtl. Da ciò segue che
la mappa ϕr : K[x1, . . . , xn]/I → K[x1, . . . , xn]/I è la moltiplicazione per xr
per r = 1, . . . , n. Quindi abbiamo XrXs = XsXr per r, s ∈ {1, . . . , n}, cioè le
matrici χ1, . . . , χn sono a due a due commutative. Resta da dimostrare che
b) implica a). Senza perdere di generalità, sia t1 = 1. Le matrici χ1, . . . , χn
de niscono una struttura di K[x1, . . . , xn]-modulo su hOiK tramite
f · (c1t1+ . . . + cµtµ) = (t1, . . . , tµ)f (X1, . . . , Xn)(c1, . . . , cµ)tr
dove poniamo f(X1, . . . , Xn) = f Iµ per f ∈ K. Per prima cosa dimostriamo
che questo P -modulo è ciclico con generatore t1. Per fare ciò,usiamo l'indu-
zione sul grado per dimostrare che ti · t1 = ti per i = 1, . . . , µ. Indichiamo
con ei la matrice di dimensioni µ × 1 che ha 1 nell' entrata i-esima e zero
altrove. L'induzione inizia con t1 = (t1, . . . , tµ)Iµ· ei. Il passo induttivo sarà
ti = xjtk. Di conseguenza abbiamo
ti· t1 = (t1, . . . , tµ)ti(χ1, . . . , χn)e1
= (t1, . . . , tµ)χjtk(χ1, . . . , χn)e1
= (t1, . . . , tµ)χjek= (t1, . . . , tµ)ei
Otteniamo cosi una mappa suriettiva K[x1, . . . , xn]-lineare
˜
Θ : K[x1, . . . , xn] → hOiK
che soddisfa f 7→ f · t1 e induce un isomor smo di K[x1, . . . , xn]-moduli
Θ : K[x1, . . . , xn]/J → hOiK con J = Ker ˜Θ. In particolare, le classi di resto
t1+ J, . . . , tµ+ J sono linearmente indipendenti su K. Adesso dimostriamo
che I ⊆ J. Sia bj = xktl. Allora abbiamo
gj(X1, . . . , Xn)e1 = bj(X1, . . . , Xn)e1− µ X i=1 αijti(X1, . . . , Xn)e1 = Xktl(X1, . . . , Xn)e1− µ X i=1 αijei = Xkel− µ X i=1 αijei = n X i=1 αijei− n X i=1 αijei = 0.
Di conseguenza otteniamo gj ∈ Ker ˜Θper j = 1, . . . , ν e così I ⊆ J, come
desiderato. Per cui c'è un naturale omomor smo di anelli suriettivo Ψ : K[x1, . . . , xn]/I → K[x1, . . . , xn]/J.
Poichè l'insieme {t1 + I, . . . , tµ+ I} genera il K-spazio vettoriale
K[x1, . . . , xn]/I,
e poichè l'insieme {t1+ J, . . . , tµ+ J } è linearmente indipendente su K,
entrambi gli insiemi devono essere basi e I = J. Questo dimostra che G è una O-border bases di I.
L'esempio seguente mostra che le formal multiplication matrix corrispon- denti ad una O-border prebases non sempre commutano.
Esempio 2.3.2. Sia P = Q[x, y] e O = {1, x, y, x2, y2}. Allora il bor-
der di O è ∂O = {xy, x3, y3, x2y, xy2}. Consideriamo l'insieme di polino-
mi {g1, g2, g3, g4, g5} con g1 = xy − x2 − y2, g2 = x3 − x2, g3 = y3 − y2,
g4 = x2y − x2, e g5 = xy2 − y2. È una O-border prebases dell'ideale
X = 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 e Y = 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1
non commutano, in quanto
X · Y = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 6= Y · X = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 1
In virtù del teorema, l'insieme G non è una O-border bases di I.
Basandoci sul teorema precedente, possiamo ora dimostrare un analogo del criterio di Buchberger. Il primo passo consiste nell'analizzare la condi- zione di commutatività nel teorema 2.3.4 e trasformarlo in equazioni per i coe cienti g1, . . . , gν.
Proposizione 2.3.4. Per j = 1, . . . , ν, scriviamo gj = bj −Pµi=1αijti con
αij ∈ K. Dato r ∈ {1, . . . , n}, de niamo una mappa
% : {1, . . . ,µ} −→ N
i 7−→ j if xrti = tj ∈ O k if xrti = bk ∈ ∂O
Allora la O-border prebases G di I è una O-border bases di I se e solo se le seguenti equazioni sono soddisfatte per p = 1, . . . , µ e 1 ≤ r < s ≤ n:
(1) X {m|xrtm∈O} δp%(m)αmk+ X {m|xrtm∈O} αp%(m)αmk = αpl se xrti = tj, xsti = bk, xrbk = bl. (2) X {m|xrtm∈O} δp%(m)αmk+ X {m|xrtm∈O} αp%(m)αmk = X {m|xrtm∈O} δp%(m)αmk+ X {m|xrtm∈O} αp%(m)αmk.
se xrti = bj, xsti = bk
Dimostrazione. Dal teorema 2.3.4 l'insieme G è una O-border bases se e solo se XrXsei = XsXrei per i = 1, . . . , µ. Portando tutto ciò nel linguaggio di
hOiK la condizione risultante dipende dalla posizione di ti relativa al border
di O. Si distinguono quattro casi. tk tl
ti tj Primo caso: xr
xsti ∈ O
Poichè O è un order ideal, abbiamo tj = xrti ∈ O e tk = xsti ∈ O.
Così abbiamo XrXsei = Xrek = el = Xsej = XsXrei, ossia la condizione di
commutatività si mantiene per la de nizione di formal multiplication matrix. tk bl
ti tj Secondo caso: xr
xsti ∈ ∂O e xrti, xsti ∈ O
Poniamo xrti = tj, xsti = tk e xrxsti = bl. Allora abbiamo
XsXrei = Xrek = (α1l, . . . , αµl)tr = Xsej = XrXsei
Ancora una volta, la commutatività segue immediatamente dalla de nizione di formal multiplication matrix.
bk bl
ti tj Terzo caso: xr
ti ∈ O e xsti ∈ ∂O
Poichè ∂O e O sono order ideal, questo caso implica xrxsti ∈ ∂O. Po-
niamo xrti = tj , xsti = bk e xrxsti = bl. La condizione di commutatività
diventa Xr(α1k, . . . , αµk)tr = (α1l, . . . , αµl)tr, cioè P µ m=1ξ
(r)
pmαmk = αpl per
p = 1, . . . , µ. In accordo con la de nizione di formal multiplication matrix, queste condizioni sono equivalenti all'equazione (1) per p = 1, . . . , µ.
bk ∗
ti bj Quarto caso: xt
ti ∈ ∂O e xsti ∈ O
Sia xrti = bj e xsti = bk. La condizione di commutatività diventa
Xr(α1k, . . . , αµk)tr = Xs(α1j, . . . , αµl)tr, ossia Pµm=1ξ (r)
pmαmk =Pµm=1ξ (r) pmαmj
per p = 1, . . . , µ. Queste condizioni sono equivalenti all'equazione (2) per p = 1, . . . , µ. Questo ricopre tutti i casi. Abbiamo dimostrato che XrXs =
XsXr per 1 6 r < s 6 n è equivalente all'insieme di equazioni (1) e (2).
Ora vogliamo interpretare le equazioni (1) e (2) in termini della rewrite relation associata a G. La seguente de nizione è motivata dal terzo e quarto caso della dimostrazione precedente.
De nizione 2.3.5. Siano bi, bj ∈ O due border term distinti.
a) I border term bi, bj vengono chiamati next-door neighbour se abbiamo
bi = xkbj per qualche k ∈ {1, . . . , n}.
b) I border term bi, bj vengono chiamati across-the-street neighbour se
xkbi = xlbj per qualche k, l ∈ {1, . . . , n}.
c) I border term bi, bj vengono chiamati neighbour se sono next-door
neighbour o across-the street-neighbour.
A questo punto siamo in grado di dimostrare l'analogo del criterio di Buchberger. L' S-polinomio di due elementi distinti gi, gj ∈ Gè de nito da
S(gi, gj) = lcm(bi, bj) bi gi− lcm(bi, bj) bj gj.
Proposizione 2.3.5. (Criterio di Buchberger per le Border Bases) Sotto le precedenti ipotesi, la O-border prebases G è una O-border basis di I se e solo se una delle seguenti condizioni equivalenti è soddisfatta.
1. Per ogni 1 6 i 6 j 6 ν, l' S-polinomio S(gi, gj) riduce a zero tramite G
−→.
2. Per tutti i neighbour bie bj, l' S polinomio S(gi, gj)riduce a zero tramite G
−→.
Dimostrazione. La condizione 1 vale se G è una border bases, poichè S(gi, gj) ∈ I e G soddisfa la condizione C1. Poichè 1 implica banalmente 2,
resta da dimostrare che G è una border bases se la condizione 2 vale. Dati next-door neighbour bl = xrbk, calcoliamo
gl− xrgk = (bl− µ X m=1 αmltm) − xr(bk− µ X m=1 αmktm) = − µ X m=1 αmltm+ µ X m=1 αmk(xrtm) = − µ X m=1 αmltm+ X {m|xrtm∈O} αmkt%(m)+ X {m|xrtm∈∂O} αmkb%(m) = − µ X m=1 αmltm+ X {m|xrtm∈O} αmkt%(m)+ X {m|xrtm∈∂O} αmkg%(m) + X {m|xrtm∈∂O} (αmk µ X p=1 αp,%(m)tp)
Poichè (g1, . . . , gν) ⊆ I, il coe ciente di ogni tp deve annullarsi nella somma − µ X m=1 αmltm+ X {m|xrtm∈O} αmkt%(m)+ X {m|xrtm∈∂O} (αmk µ X p=1 αp,%(m)tp)
Questo fatto porta alla equazione (1) nella proposizione 2.3.4. Dati across- the-street neighbour xrbk = xsbj, calcoliamo
xrgk− xsgj = xr(bk− µ X m=1 αmktm) − xs(bj − µ X m=1 αmjtm) = − µ X m=1 αmk(xrtm) + µ X m=1 αmj(xstm) = − X {m|xrtm∈O} αmkt%(m)− X {m|xrtm∈∂O} αmkb%(m) + X {m|xrtm∈O} αmjt%(m)+ X {m|xrtm∈∂O} αmjb%(m) = − X {m|xrtm∈O} αmkt%(m)− X {m|xrtm∈∂O} αmkg%(m) − X {m|xrtm∈∂O} αmk µ X p=1 αp%(m)tp + X {m|xrtm∈O} αmjt%(m)+ X {m|xrtm∈∂O} αmjg%(m) + X {m|xrtm∈∂O} αmj µ X p=1 αp%(m)tp
Il coe ciente di ogni tp deve ancora una volta annullarsi, e questo forni-
sce esattamente l'equazione (2) nella proposizione 2.3.4. Complessivamente vediamo che gl− xrgk
G
−→ 0o xrgk− xsgj G
−→ 0, rispettivamente, implica la commutatività delle formal multiplication matrix, e di conseguenza che G è una O- border bases.
Abbiamo caratterizzato quindi le border bases come border prebases dotate di una delle seguenti proprietà equivalenti: special generation, generazione del Border Form Ideal, con uenza delle corrispondenti rewrite relation e ridu- zione a zero dell' S-polinomio. Accanto a queste abbiamo la caratterizzazione
tramite sollevamento delle sigizie; essa è fondata su uno studio dettagliato delle posizioni relative dei border term e del loro modulo delle sigizie. In particolare, una border prebases è una border bases se e solo se tutte le si- gizie fondamentali dei border term con nanti si sollevano. Tutto ciò verrà descritto nel seguito. Studieremo quindi il modulo delle sigizie
SyzK[x1,...,xn](b1, . . . , bν) = {(f1, . . . , fν) ∈ K[x1, . . . , xn]
ν | f
1b1+ . . . + fνbν = 0}
I suoi elementi vengono chiamati border sygyzy.
Preliminarmente consideriamo la struttura del border ∂O data dalla re- lazione di equivalenza generata dalla relazione di essere neighbour che verrà indicata con ∼. La proposizione seguente stabilisce che ∂O è connesso nel senso che c'è una sola classe di equivalenza rispetto a ∼.
Proposizione 2.3.6. Per ogni border term bi, bj ∈ ∂O, c'è una sequenza
nita bk0, bk1, . . . , bks di border term da bi = bk0 a bj = bks tali che bkl−1, bkl
sono neighbour per l = 1, . . . , s.
Dimostrazione. Siano bi, bj ∈ ∂O e g =gcd(bi, bj). Abbiamo di conse-
guenza bi = xαi11. . . x αp ipg e bj = x β1 j1 . . . x βq jqg con αk, βl ∈ N+ e {i1, . . . , ip} ∩ {j1, . . . , jq} = ∅. Usiamo l'induzione su α1 + . . . αp+ β1+ . . . + βq. Se β1 + . . . + βq = 0, ossia se g = bj, allora bi = bk0 = x α1 i1 . . . x αp ipg = bi, x α1 i1 . . . x αp−1 ip g, . . . , x α1 i1 . . . x αp−1 ip−1 g, xα1 i1 . . . x αp−1−1 ip−1 g, . . . , xi1g, g = bks = bj
è una sequenza di border term, poichè ∂O e O sono order ideal. Per costruzione, ogni due termini consecutivi in questa sequenza sono next-door neighbour. Il caso α1 + . . . + αp si dimostra in maniera simmetrica. Adesso
assumiamo α1+ . . . + αp, β1 + . . . βq > 0. Allora xj1|bj, ossia bj = xj1t con
t ∈ Tn. Poichè ∂O è un order ideal, abbiamo t ∈ ∂O. Terminiamo la dimostrazione considerando tre casi.
Caso 1: Se t ∈ ∂O, allora t è un next-door neighbour di bj e t ∼ bj per
Caso 2: Se t ∈ O e xi1t ∈ ∂O, allora xi1t è un across-the street-neighbour
di bj. Poichè gcd(xi1t, bi) = xig, abbiamo xi1t ∼ bi per ipotesi induttiva.
Così otteniamo bi ∼ xi1t ∼ xj1t = bj.
Caso 3: Se t ∈ O e xi1t ∈ O, allora xj1xi1t = xi1bj ∈ ∂O è un next-door
neighbour di bj. Poichè gcd(xi1bj, bi) = xi1g, abbiamo xi1bj ∼ bi per ipotesi
induttiva. Otteniamo pertanto bi ∼ xi1bj ∼ bj.
Sia {e1, . . . , eν} la base canonica del modulo libero K[x1, . . . , xn]ν Le
sigizie fondamentali σij = lcm(bi, bj) bi ei− lcm(bi, bj) bj ej generano il
modulo delle border sygyzy
SyzK[x1,...,xn](b1, . . . , bν).
Dimostreremo che esiste un insieme di generatori più e ciente per questo modulo delle sigizie.
De nizione 2.3.6. Sia O un order ideal con border ∂O = {b1, . . . , bν}.
a) Dati due next-door neighbour bi, bj ossia per bi = xkbj, la sigizia fon-
damentale σij ha la forma τij = ei − xkej e viene chiamata una
next-door neighbour sygyzy.
b) Dati due across-the-street neighbour bi, bj, ossia per xkbi = xlbj,la sigi-
zia fondamentale σij ha la forma vij = xkei − xlej e viene chiamata
una across-the-street neighbour sygyzy.
c) L'insieme di tutte le neighbour sygyzy è l'insieme di tutte le next-door o across-the-street neighbour sigizie.
Proposizione 2.3.7. SyzK[x1,...,xn](b1, . . . , bν)è generato dall'insieme di tutte
le neighbour sygyzy.
Dimostrazione. Poichè il modulo SyzK[x1,...,xn](b1, . . . , bν) è generato dal-
l'insieme delle sigizie fondamentali {σij | 1 ≤ i < j ≤ ν} sarà su ciente
dimostrare che ogni sigizia fondamentale è una combinazione K[x1, . . . , xn]-
lineare di neighbour sygyzy. Per comodità di notazione scriveremo σji= −σij
per 1 ≤ i < j ≤ n. Sia bk0, . . . , bks una sequenza di border term costruiti
nella dimostrazione della proposizione 2.3.6, cioè tali che bk0 = bi, bks = bj
e bkl−1, bkl sono neighbour per l = 1, . . . , s. Aermiamo che ci sono ter-
mini f1, . . . , fs ∈ Tn tali che σij = Psl=1flϕl, dove ϕl è la sygyzy neigh-
bour tra bkl−1 e bkl. Per dimostrare questa aermazione, procederemo per
induzione su s. Per s = 1, i termini bi e bj sono neighbour e σij è la cor-
rispondente neighbour sygyzy. Per s > 1, sia bi = xαi11. . . x
αp
ip · gcd(bi, bj)
e bj = xβj11. . . x
βq
jq · gcd(bi, bj) come nella dimostrazione della proposizione
2.2.6. Se q = 0, ossia se xα1
i1 . . . x
αp
ip · bj, allora bi = bk0 = xipbk1 e quindi
σij − tijτk0k1 = tijxipek1 − tijeks = xipσk1ks è una sigizia di bk1 e bks. L'af-
fermazione segue per induzione. Se q ≥ 1, scriviamo bj = xj1t con t ∈ T
n e
controlliamo gli stessi tre casi come nella proposizione 2.3.6.
Caso 1: Se t ∈ ∂O, allora bks−1 = t e τksks−1 = eks − xj1eks−1 è una
next-door neighbor sygyzy. Così
σij + tijτksks−1 = tijek0 − tjixj1eks−1 = xj1σk0ks−1
è una sigizia di bk0 e bks−1. L'aermazione segue per induzione.
Caso 2: Se t ∈ O e bks−1 = xi1t ∈ ∂O, allora xi1bks = xi1xj1t = xj1bks−1
e vksks−1 = xi1eks− xj1eks−1 è un across-the-street-neighbor sygyzy. Poichè
tksk0 =lcm(bks, bk0 = x
α1
i1 . . . x
αp
ip, e poichè xi1|bks−1 implica αi1 ≥ 1, abbiamo
una fattorizzazione tksk0 = xi1t 0 con t0 ∈ Tn. Allora σij + t0vksks−1 = tijek0 − t 0x j1σk0ks−1
è una sigizia di bk0 e bks−1. L'aermazione segue per induzione.
Caso 3: Se xi1t ∈ O e bks−1 = xi1bj ∈ ∂O, allora τks−1ks = eks−1− xi1eks
è una next-door neighbour sygyzy. Nuovamente scriviamo tksk0 = xi1t
0 con
t0 ∈ Tn e calcoliamo σ
ij− t0τks−1ks = tijek0− t
0e
ks−1 = σk0ks−1. Ancora una
volta l'asserto segue per induzione.
Va osservato che le neighbour sygyzies sono particolarmente semplici: sono binomi e i loro coe cienti sono o le costanti ±1 o indeterminate. Ora applicheremo ciò che conosciamo sulle border sygyzy per caratterizzare le border bases tramite il sollevamento delle sigizie. Ci interessa in particolare il caso del modulo delle sigizie
SyzK[x1,...,xn](g1, . . . , gν) = {(f1, . . . , fν) ∈ K[x1, . . . , xn]
ν |f
e iniziamo de nendo un sollevamento di una border sygyzy.
De nizione 2.3.7. Siano (f1, . . . , fν) ∈ SyzK[x1,...,xn](b1, . . . , bν) una border
sygyzy. Una sigizia (F1, . . . , Fν) ∈ SyzK[x1,...,xn](g1, . . . , gν) è un solleva-
mento di (f1, . . . , fν) se si veri ca uno dei seguenti casi:
1) Pν
j=1fjgj = 0 per tutti gli i ∈ {1, . . . , ν} o
2) Pν
j=1fjgj 6= 0 e per tutti gli i ∈ {1, . . . , ν} tali che Fi− fi 6= 0 abbiamo
deg(Fi− fi) 6 indO(Pνj=1fjgj) − 1.
Nel secondo caso la combinazione Pj(Fj − fj)gj cancella Pjfjgj, e il
bound del grado assicura che non ci sono cancellazioni interne nella combi- nazione Pj(Fj− fj)gj al di là dell'indice di Pjfjgj. Il prossimo esempio mo-
stra che esistono sollevamenti e inoltre che sollevamenti di neighbour sygyzies sono molto semplici da calcolare se G è una border bases.
Esempio 2.3.3. Assumiamo che G sia una border bases.
a) Data una next-door sygyzy τij = ei−xkej, tutti i termini che compaiono
in gi− xkgj hanno indice 6 1. Per cui esistono c1, . . . , cm ∈ K tali che
il supporto di gi − xkgj −Pνm=1cmgm è contenuto in O. Poichè G è
una border bases, ne segue che ϕij = ei − xkej −
Pν
m=1cmem è una
sigizia di (g1, . . . , gν). Questa sigizia solleva τij, perchè gi− xkgj = 0
oppure deg(cm)= 0 < 1 = indO(gi− xkgj).
b) Dato una across-the-street neighbor sygyzy vij = xkei− xlej, gli unici
termini di indice 2 presenti in xkgi − xlgj sono xkbi e xlbj. Poichè
questi 2 termini si cancellano e tutti gli altri termini hanno indice ≤ 1, esistono d1, . . . , dν ∈ K tali che il supporto di xkgi− xlgj−
Pν
m=1dmgm
è contenuto in O. Ancora la proprietà della border bases di G implica che ψij = xkei− xlej −
Pν
m=1dmem è una sigizia di (g1, . . . , gν) che
solleva vij perchè xkgi−xlgj = 0o deg(dm)= 0 < 1 = indO(xkgi−xlgj).
Poichè l'indice non è monotono rispetto alla moltiplicazione per un ter- mine, l'indice di Pν
j=1fjgj può essere in realtà più grande dell'indice r dei
termini in f1b1+ . . . + fνbν. Il seguente esempio ne è un caso.
Esempio 2.3.4. Sia O = {1, x, x2} ⊂ T2. Allora ∂O = {y, xy, x2y, x3}.
L'insieme G = {g1, g2, g3, g4} dove g1 = y − x2, g2 = xy, g3 = x2y, g4 = x3 è
una O-border bases di I = (g1, g2, g3, g4). Abbiamo indO(f b1) = 1 per f = x2
Dimostriamo adesso la proposizione che caratterizza le border bases tra- mite sollevamento di border sigizy pure.
Proposizione 2.3.8. Nelle ipotesi precedenti, l'insieme G è una O-border bases di I se e solo se una delle seguenti condizioni equivalenti è soddisfatta.
i) Ogni border sygyzy si solleva ad una sigizia di (g1, . . . , gν).
ii) Ogni neighbor sygyzy si solleva ad una sigizia di (g1, . . . , gν).
Dimostrazione. Per prima cosa dimostriamo che una border bases sod- disfa i). Sia (f1, . . . , fν) una border sygyzy, e sia f = f1g1 + . . . + fνgν.
Utilizzando il Border Division Algorithm, calcoliamo una rappresentazione f = h1g1+ . . . + hνgν con deg(hi) ≤ indO(f ) − 1. Il normal remainder è zero,
poichè f ∈ I e G è una border bases di I. Adesso (f1 − h1, . . . , fν − hν) è
una sigizia di (g1, . . . , gν) che solleva (f1, . . . , fν).
Poichè i) implica ii), resta da dimostrare che G è una border bases se ii)vale. Data una next-door neigbor sygyzy τij = ei − xkej, abbiamo gi − xkgj = 0
oppure l'indice di gi−xkgj è uno. Quindi ogni sollevamento di τij ha la forma
τij −Pνm=1cmem con cm ∈ K. Data un across-the street neighbor sygyzy
vij = xkei− xlej, il polinomio xkgi− xlgj è zero oppure il suo indice è uno.
Quindi ogni sollevamento di vijha la forma vij−
Pν
m=1cmem con cm ∈ K. In
entrambi i casi l'S-polinomio ha la forma S(gi, gj) =Pνm=1cmgm, e l'asserto
segue dall'ultima parte della proposizione 2.3.5.
C'è una dierenza importante tra i sollevamenti delle Border Bases e quelli nella teoria delle basi di Gröbner: la condizione i) garantisce il sollevamento di tutte le border sygyzy, mentre nelle teoria delle basi di Gröbner possiamo sollevare solo sigizie omogenee dei leading term. Per esaminare quale tipo di border sygyzy è il corretto analogo delle sigizie omogenee dei leading term, introduciamo due tipi particolari di border sygyzy.
De nizione 2.3.8. Sia O un order ideal con border ∂O = {b1, . . . , bν}, e sia
k ∈ N.
a) Una border sygyzy (f1, . . . , fν)si dice pura di indice k se ∪νi=1Supp(fibi)
è contenuta in ∂kO. Viene chiamata pura se è pura per qualche indice.
b) Una border sygyzy (f1, . . . , fν) si dice perfetta di indice k se è pura