Introdução a Teoria de Bases de Gröbnerdiane/Grobner.pdf · Motivação Subespaços Uma variável Comutativo Não Comutativo Para resolver estes problemas, precisamos das bases

Introdução a Teoria de Bases de Gröbner

Profa Dra: Diane Castonguay

INF-UFG

Setembro de 2007

Profa Dra: Diane Castonguay INF-UFG


Motivação Subespaços Uma variável Comutativo Não Comutativo

Sumário

Motivação

O problema da pertinência em Subespaços

O problema de pertinência em K[x].

O problema de pertinência em K[x1, . . . , xn]

O problema de pertinência em K<x1, . . . , xn>




Referência Principal

Este mini curso foi elaborado a partir da dissertação de mestradode Alexey Antônio Villas Bôas.[Villas Bôas, 2005]




Motivação

Problema da pertinência para ideal de polinômios.Dado um polinômio, decida se ele pertence ou não a um ideal doanel de polinômios.Parece facil?




Motivação





Motivação





Exemplo

I Consideremos o anel dos polinômios em três variaveiscomutativas K[x1, x2, x3] e o ideal gerado por

{f1 := x2 − y3z, f2 := x2 − z2, f3 := y2z − y}

Será que f := xy − xz3 pertence a este ideal?I Consideremos o anel dos polinômios em uma variavel K[x] e o

ideal gerado por

{f1 := x3 − 3x+ 2, f2 := x4 − 1, f3 := x6 − 1}

Será que f := x3 + 4x2 + 3x− 7 pertence a este ideal?




Exemplo

I Consideremos o anel dos polinômios em três variaveiscomutativas K[x1, x2, x3] e o ideal gerado por

{f1 := x2 − y3z, f2 := x2 − z2, f3 := y2z − y}

Será que f := xy − xz3 pertence a este ideal?I Consideremos o anel dos polinômios em uma variavel K[x] e o

ideal gerado por

{f1 := x3 − 3x+ 2, f2 := x4 − 1, f3 := x6 − 1}

Será que f := x3 + 4x2 + 3x− 7 pertence a este ideal?




Problemas

I Problema da pertinência para ideal de polinômiosDado f ∈ K[x1, . . . , xn] e um conjunto gerador para um idealI de K[x1, . . . , xn], decida se f pertence a I.

I Problema da igualdade em quocientes do anel depolinômiosDado f, g ∈ K[x1, . . . , xn] e um conjunto gerador para umideal I de K[x1, . . . , xn], decida se f + I = g + I.




Problemas

I Problema da pertinência para ideal de polinômiosDado f ∈ K[x1, . . . , xn] e um conjunto gerador para um idealI de K[x1, . . . , xn], decida se f pertence a I.

I Problema da igualdade em quocientes do anel depolinômiosDado f, g ∈ K[x1, . . . , xn] e um conjunto gerador para umideal I de K[x1, . . . , xn], decida se f + I = g + I.




Para resolver estes problemas, precisamos das bases de Gröbner.

Estas ideias foram introducidas por Buchberger na sua tese dedoutorado em 1965 [Buchberger, 1965] e desde entãodesempenham um papel muito importante na área de ÁlgebraComputacional.

Além do mas, muitos sistemas de computação algébrica incluempacotes para lidar com Bases de Gröbner (comutativa). Entre eles,podemos citar: Axiom, Maple, Mathematica, CoCoA e Reduce.
















Introduciremos dois algoritmos que são as chaves da teoria (no casocomutativo).

I Algoritmo da DivisaoEste algoritmo decide da pertinência de um elemento numideal, dados o elemento e uma Base de Gröbner para o idealem questão.

I Algoritmo de BuchbergerConstrói uma Base de Gröbner para um ideal, a partir de umconjunto �nito de geradores.
















Sumário

Motivação

O problema da pertinência em SubespaçosAlgoritmo - Redução Incompleta de Gauss








Consideremos um corpo K, V = Kn e �xamos uma base ordenadacanônica de V .

Problema da pertinência.Dado v um vetor de V e B = {b1, . . . , bm} uma base ordenada deum subespaço W de V , Decida se v pertence a W .Consideremos estes elementos como vetores (coordenadas na basecanônica de V .)






















I Primeira abordagem:Resolver o sistema linear de equações α1b1 + . . .+ αmbm = v

I Segunda abordagem:Constrói uma matriz M com m+ 1 linha, onde as m primeiraslinhas correspondem aos elementos de B e a ultima linha aoelemento v.Aplique o algoritmo de Gauss-Jordan a M .Temos que v pertence a W se e somente se a matriz resultanteda aplicação de Gauss-Jordan a matriz M tiver uma linha nula.



















Terceira Abordagem

Consideramos uma base especial para W .

I Chamamos de coordenada líder de um vetor não nulo v(denotada por v) a menor coordenada não nula de v.

I Uma base G de um subespaço vetorial W é dita uma Base deGauss se ela satis�zer as segunites propriedades:

I Não existem dois vetores em G com a mesma coordenada líder.I Se um vetor não nulo u pertence a W , então existe um

elemento g em G tal que u = g.

I Denotaremos por cl(u) o valor da coordenada líder de u.




Terceira Abordagem










Terceira Abordagem










Terceira Abordagem










RedIncGAUSS

Algoritmo - Redução Incompleta de Gauss (RedIncGAUSS)

Este algoritmo recebe como entrada uma Base de Gauss G de umsubespaço W de V e um vetor v de V . O algoritmo devolve comosaida um vetor h.

I RedIncGauss(G,v)1. h← v2. enquanto existe g ∈ G tal que h = g faça

3. h← h− cl(h)cl(g) g

4. �m-enquanto

5. devolva h




RedIncGAUSS

Algoritmo - Redução Incompleta de Gauss (RedIncGAUSS)

Este algoritmo recebe como entrada uma Base de Gauss G de umsubespaço W de V e um vetor v de V . O algoritmo devolve comosaida um vetor h.

I RedIncGauss(G,v)1. h← v2. enquanto existe g ∈ G tal que h = g faça

3. h← h− cl(h)cl(g) g

4. �m-enquanto

5. devolva h




RedIncGAUSS

Teorema

Seja G uma Base de Gauss do subespaço W de V e v ∈ V . Ovetor v pertence a W se e somente se h := RedIncGAUSS(G, v)for igual a zero.

Exemplo sobre a importância da base ser de Gauss

Consideremos a base B := {(1, 2, 1), (1, 0, 2), (0, 0, 1)} ev = (1, 0, 3)




RedIncGAUSS

Teorema







RedIncGAUSS

Teorema







Sumário

Motivação


O problema de pertinência em K[x].Algoritmo da Divisão para polinômios em K[x]Algoritmo de Euclides






O problema de pertinência em K[x].Para n = 1, o algoritmo de Buchberger se reduz ao Algoritmo deEuclides.

I Fato: Todo ideal de K[x] é principal.

Sejam I um ideal de K[x] e p um polinômio. Sabemos que existeum polinômio h tal que I =< h >.Para saber se p pertence a I, veri�caremos se o resto da divisão porh é nulo.

I Dado um conjunto gerador {f1, . . . , fn} de I, precisamosencontrar um polinômio h tal que I =< h >. Para isto,podemos usar repetidamente o Algoritmo de Euclides paraencontrar um máximo divisor comum dos dois polinômios queserá o nosso gerador.
































DivisãoPoli

Algoritmo da Divisão para polinômios em K[x] (DivisãoPoli)O algoritmo recebe como entrada dois polinômios g e f e devolve oresto da divisão de f por g, ou seja, outro polinômio r que satisfazgrau(r) < grau(g) e f = ag + r, para algum polinômio a.

I DivisãoPoli(f,g)1. r ← f2. enquanto r 6= 0 e g divide r faça

3. r ← r − cl(r)rcl(g)g g

4. �m-enquanto

5. devolva r

Para um polinômio g, o termo líder é o monômio de maior grau deg.Exemplos com maior e menor grau

I f := x5 − x2 e g := x2 − x eI f := x5 − x2 e g := x2 − 1




DivisãoPoli




4. �m-enquanto

5. devolva r






DivisãoPoli




4. �m-enquanto

5. devolva r






DivisãoPoli

Algoritmo da Divisão para polinômios em K[x] (DivisãoPoli)



4. �m-enquanto

5. devolva r






DivisãoPoli

Algoritmo da Divisão para polinômios em K[x] (DivisãoPoli)



4. �m-enquanto

5. devolva r






Euclides

Algoritmo de Euclides (Euclides)O algoritmo recebe como entrada dois polinômios f e g de K[x] edevolve um polinômio h = mdc(f, g).

I Euclides(f,g)1. h← f2. s← g3. enquanto s 6= 0 faça

4. r ←DivisãoPoli(h, s)5. h← s6. s← r7. �m-enquanto

8. devolva h

ExemploI =< f1 := x3 − 3x+ 2, f2 := x4 − 1, f3 := x6 − 1 > ep := x3 + 4x2 + 3x− 7.




Euclides




8. devolva h





Euclides




8. devolva h





Sumário

Motivação



O problema de pertinência em K[x1, . . . , xn]De�niçõesAlgoritmo da DivisãoBase de GröbnerAlgoritmo de Buchberger

O problema de pertinência em K<x1, . . . , xn>Profa Dra: Diane Castonguay INF-UFG



De�nições

Ordem monomial

Uma ordem monomial em K[x1, . . . , xn] é uma relação ≤ nosmonômios de K[x1, . . . , xn] satisfazendo:

I ≤ é uma boa ordemI Para todos os monômios xα, xβ , xγ ∈ K[x1, . . . , xn], sexα < xβ então xαxγ < xβxγ

Notação: Assumiremos que x1 > x2 > . . . > xn.Seja α = (α1, . . . , αn) ∈ Nn, denotaremos por xα = xα1

1 xα22 . . . xαn

n




De�nições

Ordem monomial




1 xα22 . . . xαn

n




De�nições

Ordem monomial




1 xα22 . . . xαn

n




De�nições

Ordem monomial




1 xα22 . . . xαn

n




De�nições

Ordem monomial




1 xα22 . . . xαn

n




De�nições

Exemplos

I Ordem lexicográ�ca (abreviada por lex)Dizemos que xα < xβ se existe 1 ≤ j ≤ n tal que αj < βj eαi = βi, para todo 1 ≤ i < j.

I Ordem de grau e lexicográ�ca (abreviada por deglex)Dizemos que xα < xβ se∑n

i=1 αi <∑n

i=1 βiou∑n

i=1 αi =∑n

i=1 βi e xα é menor que xβ na ordem

lexicográ�ca.




De�nições

Exemplos

I Ordem lexicográ�ca (abreviada por lex)Dizemos que xα < xβ se existe 1 ≤ j ≤ n tal que αj < βj eαi = βi, para todo 1 ≤ i < j.

I Ordem de grau e lexicográ�ca (abreviada por deglex)Dizemos que xα < xβ se∑n

i=1 αi <∑n

i=1 βiou∑n

i=1 αi =∑n

i=1 βi e xα é menor que xβ na ordem

lexicográ�ca.




De�nições

Monômio Líder

Seja f = a1xα1 + a2x

α2 + . . .+ atx

αt um polinômio não nulo de

K[x1, . . . , xn], com 0 6= ai ∈ K e αi ∈ Nn, para 1 ≤ i ≤ t e ≤uma ordem monomial em K[x1, . . . , xn]. Tome xαj o máximodentre todos os xαi , na ordem ≤.

I Chamamos xαj o monômio líder de f (na ordem dada), edenotaremos por f .

I Ainda, chamamos aj de coe�ciente líder de f e denotaremospor cl(f).

I Por �m, se S é um subconjunto de K[x1, . . . , xn],denotaremos por S o conjunto {f | f ∈ S}.




De�nições

Monômio Líder


α2 + . . .+ atx









De�nições

Monômio Líder


α2 + . . .+ atx









De�nições

Monômio Líder


α2 + . . .+ atx









DivisãoComut

Algoritmo da Divisão em K[x1, . . . , xn] (DivisãoComut)O algoritmo recebe como entrada um polinômio f ∈ K[x1, . . . , xn],e um conjunto �nito S = {f1, f2, . . . , fs} ⊂ K[x1, . . . , xn] edevolve como saída outro polinômio f .

I DivisãoComut(S, f)1. f ′ ← 02. enquanto f 6= 0 faça

3. enquanto fi ∈ S tal que fi divide f faça

4. f ← f − cl(f)f

cl(fi)fifi

5. �m-enquanto

6. se f 6= 07. então f ′ ← f ′ + cl(f)f8. f ← f − cl(f)f9. �m-se

10. �m-enquanto

11. devolva f ′Profa Dra: Diane Castonguay INF-UFG



DivisãoComut

Algoritmo da Divisão em K[x1, . . . , xn] (DivisãoComut)

I DivisãoComut(S, f)1. f ′ ← 02. enquanto f 6= 0 faça

3. enquanto fi ∈ S tal que fi divide f faça

4. f ← f − cl(f)f

cl(fi)fifi

5. �m-enquanto

6. se f 6= 07. então f ′ ← f ′ + cl(f)f8. f ← f − cl(f)f9. �m-se

10. �m-enquanto

11. devolva f ′




DivisãoComut

Exemplo

Considere K[x, y, z] com a ordem lexicográ�ca (x > y > z).S = {f1 := x2 − y3z, f2 := x2 − z2, f3 := y2z − y} e f := x2 − y2.S = {f1 := x2 − y3z, f2 := x2 − z2, f3 := y2z − y} ef := xy − xz3.




DivisãoComut

Exemplo





DivisãoComut

Exemplo





DivisãoComut

Teorema da Base de Hilbert

Todo ideal I de K[x1, . . . , xn] é �nitamente gerado,ou seja I =< g1, . . . , gt >, para alguns g1, . . . , gt ∈ I.




DivisãoComut

Teorema da Base de Hilbert

Todo ideal I de K[x1, . . . , xn] é �nitamente gerado,ou seja I =< g1, . . . , gt >, para alguns g1, . . . , gt ∈ I.




Base de Gröbner

Base de Gröbner

Um subconjunto G de um ideal I de K[x1, . . . , xn] é uma base deGröbner para I (na ordem monomial �xada) se < G >=< I >, ouequivalentemente se, para todo polinômio não nulo f ∈ I, existeum polinômio g ∈ G tal que g divide f .




Base de Gröbner

Exemplo

Consideremos K[x, y] com a ordem de grau e lexicográ�ca (x > y).Tomemos F = {f1 := x3 − 2xy, f2 := x2y − 2y2 + x} e I o idealgerado por F .

I O conjunto F não é uma base de Gröbner para I. De fato,f1y − f2x = −x2 ∈ I, mas x2 /∈< f1, f2 >.

I O conjunto {x2, 2xy, 2y2 − x} é uma base de Gröbner para I.I O conjunto {f1, f2, x

2, 2xy, 2y2 − x} é uma base de Gröbnerque contém F .




Base de Gröbner

Exemplo








Base de Gröbner

Exemplo








Base de Gröbner

Exemplo








Base de Gröbner

Exemplo








Base de Gröbner

Teorema

Seja G uma base de Gröbner do ideal I em K[x1, . . . , xn] e seja fum polinômio de K[x1, . . . , xn].Então f ′ = DivisãoComut(G, f) é igual a zero se, e somente se, fpertence a I.

Exemplo:Consideremos K[x, y] com a ordem de grau-lexicográ�ca (x > y) eG = {x2, 2xy, 2y2 − x} uma base de Gröbner.Seja f := x2y − 2y2 + x. O polinômio f pertence a <G>?




Base de Gröbner

Teorema






Base de Gröbner

Teorema






Base de Gröbner

Teorema






Base de Gröbner

S-polinômio

Sejam f, g polinômios de K[x1, . . . , xn].O S-polinômio de f e g é.

S(f, g) :=xγ

cl(f)ff − xγ

cl(g)gg

onde xγ é o mínimo comum multíplo de f e g,ou seja, se f = xα e g = xβ , com α = (α1, . . . , αn} eβ = (β1, . . . , βn}, então γ = (γ1, . . . , γn}, com γi = max(αi, βi).




Base de Gröbner

S-polinômio


S(f, g) :=xγ

cl(f)ff − xγ

cl(g)gg





Base de Gröbner

S-polinômio


S(f, g) :=xγ

cl(f)ff − xγ

cl(g)gg





Base de Gröbner

S-polinômio


S(f, g) :=xγ

cl(f)ff − xγ

cl(g)gg





Base de Gröbner

S-polinômio


S(f, g) :=xγ

cl(f)ff − xγ

cl(g)gg





Base de Gröbner

Teorema

Seja I um ideal de K[x1, . . . , xn].Um conjunto gerador G = {g1, . . . , gt} é uma base de Gröbner se esomente se para todos pares (i, j), com i 6= j, S(gi, gj) se reduzpara zero sobre G (para alguma ordem em que os elementos de Gsão considerados pelo Algoritmo da Divisão).




Base de Gröbner

Teorema

Seja I um ideal de K[x1, . . . , xn].Um conjunto gerador G = {g1, . . . , gt} é uma base de Gröbner se esomente se para todos pares (i, j), com i 6= j, S(gi, gj) se reduzpara zero sobre G (para alguma ordem em que os elementos de Gsão considerados pelo Algoritmo da Divisão).




Buchberger

Algoritmo de Buchberger (BUCHBERGER)O algoritmo recebe como entrada um conjunto �nitoF = {f1, f2, . . . , ft} de geradores de um ideal I de K[x1, . . . , xn] edevolve um conjunto G ⊇ F que é uma Base de Gröbner de I.BUCHBERGER(F)1. G← F2. repita3. G′ ← G4. para cada par fi, fj ∈ G faça5. r ← DivisãoComut(G,S(fi, fj))6. se r 6= 07. então G← G ∪ {r}8. �m-se9. �m-para10. até G = G′

11. devolva GProfa Dra: Diane Castonguay INF-UFG



Buchberger

Algoritmo de Buchberger (BUCHBERGER)BUCHBERGER(F)

1. G← F

2. repita

3. G′ ← G

4. para cada par fi, fj ∈ G faça

5. r ← DivisãoComut(G,S(fi, fj))6. se r 6= 07. então G← G ∪ {r}8. �m-se

9. �m-para

10. até G = G′

11. devolva GProfa Dra: Diane Castonguay INF-UFG



Buchberger

Exemplo

Seja K[x, y] com a ordem de grau-lexicográ�ca (x > y).Consideremos F = {f1 := x3 − 2xy, f2 := x2y − 2y2 + x} e I oideal gerado por F .




Buchberger

Exemplo

Seja K[x, y] com a ordem de grau-lexicográ�ca (x > y).Consideremos F = {f1 := x3 − 2xy, f2 := x2y − 2y2 + x} e I oideal gerado por F .




Buchberger

Teorema

Seja F = {f1, f2, . . . , ft} um conjunto gerador de um ideal I nãonulo de de K[x1, . . . , xn].Se F for fornecido como entrada para o Algoritmo de Buchberger,esse terminará em um número �nito de passos e devolverá umaBase de Gröbner �nita para I.




Buchberger

Teorema

Seja F = {f1, f2, . . . , ft} um conjunto gerador de um ideal I nãonulo de de K[x1, . . . , xn].Se F for fornecido como entrada para o Algoritmo de Buchberger,esse terminará em um número �nito de passos e devolverá umaBase de Gröbner �nita para I.




Sumário

Motivação




O problema de pertinência em K<x1, . . . , xn>De�niçõesAlgoritmo da DivisãoBase de GröbnerProcedimento de MoraProfa Dra: Diane Castonguay INF-UFG



As idéias envolvidas na Teoria de Bases de Gröbner nãocomutativas foram inicialmente estudadas de forma independentepor Bokut [Bokut, 1976] e por Bergman [Bergman, 1978].

Entretanto, quem primeiro considerou essa teoria de um ponto devista mais computacional foi Mora [Mora, 1986, Mora, 1994],introduzindo uma generalização do Algoritmo de Buchberger para ocaso não comutativo (em particular para a álgebra livre), conhecidocomo Procidemento de Mora.

Existem uma série de pacotes computacionais que implementam osalgoritmos e procedimentos da Teoria de Bases de Gröbner nãocomutativas. Entre eles, destacamos Opal, NCGB (Mathematica),Bergman (Standard Lisp) e GNBP (GAP4).
















Os problemas do caso não comutativo

No caso comutativo há sempre a garantia de existência de umaBase de Gröbner �nita.Par o caso não comutativo, existem exemplos de ideais �nitamentegerados que não possuem nenhuma Base de Gröbner �nita,independente da ordem dada nos termos. Com isso o Procedimentode Mora pode nunca �nalizar sua computação.

Por outro lado, existe a garantia de que se o ideal admitir algumaBase de Gröbner �nita (para a ordem dada) então o procedimentode Mora terminará e devolverá uma Base de Gröbner �nita.

O problema de calcular uma Base de Gröbner não écomputável.
































De�nições

Ordem Admissível

Dado uma alfabeto X = {x1, . . . , xn}. Consideramos, neste minicurso, o caso particular de K<X> a álgebra livre sobre X.Denotamos por X∗ o conjunto das palavras sobre X.

Dizemos que uma ordem ≤ em X∗ é admissível se, as seguintescondições forem satisfeitas.

I A ordem ≤ é uma boa ordem em X∗.I Sejam p, q ∈ X∗, se p < q então upr < uqr, para todosu, r ∈ X∗.




De�nições

Ordem Admissível







De�nições

Ordem Admissível







De�nições

Ordem Admissível







De�nições

Ordem de grau e lexicográ�ca

I Ordem lexicográ�ca (abreviada por lex)Dizemos que u ≤ v se v = uw para algum w ∈ X∗ ouse u = wxuu

′ e v = wxvv′ para algumas letras xu, xv ∈ X e

algumas palavras w, u′, v′ ∈ X∗.

A ordem lexicográ�ca NÃO é uma ordem admíssivel.

I Ordem de grau e lexicográ�ca (abreviada por deglex)Dizemos que u < v se‖ u ‖<‖ v ‖ou‖ u ‖=‖ v ‖ e u é menor que v na ordem lexicográ�ca.




De�nições










De�nições










De�nições


I Ordem de peso e lexicográ�ca (abreviada por weight-lex)Dada uma aplicação peso φ : X → N− {0}, de�nimosφ : X∗ → N sua extensão natural. Dizemos que u < v seφ(u) < φ(v)ouφ(u) = φ(v) e u é menor que v na ordem lexicográ�ca.

As ordens de grau e lexicográ�ca e de peso e lexicográ�ca sãoadmíssiveis.




De�nições


I Ordem de peso e lexicográ�ca (abreviada por weight-lex)Dada uma aplicação peso φ : X → N− {0}, de�nimosφ : X∗ → N sua extensão natural. Dizemos que u < v seφ(u) < φ(v)ouφ(u) = φ(v) e u é menor que v na ordem lexicográ�ca.

As ordens de grau e lexicográ�ca e de peso e lexicográ�ca sãoadmíssiveis.




De�nições

Termo Líder

Sejam ≤ uma ordem admissível em X∗ e f ∈ K<X>.

I De�nimos como termo líder de f o maior elemento dosuporte de f (na ordem dada), e o denotamos por f .

I Ainda, chamamos o coe�ciente de f de coe�ciente líder def , denotado por cl(f).

I Por �m, se S é um subconjunto de K<X>, denotaremos porS o conjunto {f | f ∈ S}.




De�nições

Termo Líder








De�nições

Termo Líder








De�nições

Termo Líder








Divisão

Algoritmo da Divisão em K<X> (Divisão)O algoritmo recebe como entrada um elemento f ∈ K<X>, e umconjunto �nito S = {f1, f2, . . . , fs} ⊂ K<X> e devolve comosaída outro elemento h de K<X> tal que f = a+ h ondea ∈<S> e nenhum elemento do suporte de h seja divisível pelotermo líder de um dos fi. Além do mais, h ≤ f .

I Divisão(S, f)1. g ← f2. h← 03. enquanto g 6= 0 faça

4. enquanto existem fi ∈ S e w,w′ ∈ X∗ tais que wfiw′ = g

faça

5. g ← g − cl(g)cl(fi)

wfiw′

6. �m-enquanto

7. se g 6= 08. então h′ ← h′ + cl(g)g9. g ← g − cl(g)g

10. �m-se

11. �m-enquanto

12. devolva h




Divisão

Algoritmo da Divisão em K<X> (Divisão)

I Divisão(S, f)1. g ← f2. h← 03. enquanto g 6= 0 faça

4. enquanto existem fi ∈ S e w,w′ ∈ X∗ tais que wfiw′ = g

faça

5. g ← g − cl(g)cl(fi)

wfiw′

6. �m-enquanto

7. se g 6= 08. então h′ ← h′ + cl(g)g9. g ← g − cl(g)g

10. �m-se

11. �m-enquanto

12. devolva h




Divisão

Exemplo

Considere K<a, b, c> com a ordem de grau e lexicográ�ca(a > b > c).S = {f1 := ab− ac, f2 := a2 − ac, f3 := ba} e f := caaba.Escolhendo f1 primeiro, temos como saída cacca.Escolhendo f2 primeiro, temos como saída 0.Escolhendo f3 primeiro, temos como saída 0.




Divisão

Exemplo





Divisão

Exemplo





Divisão

Exemplo





Divisão

Exemplo





Base de Gröbner

Base de Gröbner

Um subconjunto G de um ideal I de K<X> é uma base deGröbner para I (na ordem admissível �xada) se < G >=< I >,ou equivalentemente se, para todo elemento não nulo f ∈ I, existeum polinômio g ∈ G tal que g divide f .




Base de Gröbner

Exemplo - Nem sempre é �nito

Seja I o ideal gerado por f := aba− b2a.I Consideremos K<a, b> com a ordem de grau e lexicográ�ca

(a > b).Uma base de Gröbner para I é

G := {ab2i−1a− b2ia | i ≥ 1}

De fato, não existe base de Gröbner �nita para I.

I Consideremos K<a, b> com a ordem de grau e lexicográ�ca(b > a).Uma base de Gröbner para I é {f}.




Base de Gröbner




G := {ab2i−1a− b2ia | i ≥ 1}






Base de Gröbner




G := {ab2i−1a− b2ia | i ≥ 1}






Base de Gröbner




G := {ab2i−1a− b2ia | i ≥ 1}






Base de Gröbner




G := {ab2i−1a− b2ia | i ≥ 1}






Base de Gröbner




G := {ab2i−1a− b2ia | i ≥ 1}






Base de Gröbner

Exemplo - Sempre in�nito

Consideremos K<a, x, y> e I o ideal gerado por{axya− xya, xy − yx}.

I O conjunto

G := {ayixia− yixia, xy − yx | i ≥ 1}

é uma base de Gröbner para I para qualquer ordem admissívelsatisfazendo xy > yx.

De fato, não existe base de Gröbner �nita para I, independente daordem admissível escolhida.




Base de Gröbner



I O conjunto







Base de Gröbner



I O conjunto







Base de Gröbner

Teorema

Seja G uma base de Gröbner do ideal I em K<X> e sejaf ∈ K<X>.Então f ′ = Divisão(G, f) é independente da escolha feita na linha4.Logo, f ′ é igual a zero se, e somente se, f pertence a I.




Base de Gröbner

Teorema





Base de Gröbner

Teorema





Base de Gröbner

Relação de SobreposiçãoSejam f, g dois elementos de K<X>.Uma sobreposição envolvendo f e g é uma quadrupla (f, g, u, v)satisfazendo:

I u e v são palavras não nula de X∗.I uf = gv.I O termo líder de f não divide v e o termo líder de g não divideu.

Dado uma sobreposição (f, g, u, v), diremos que uma relação desobreposição envolvendo f e g é dada por

O(f, g, u, v) = uf − αgv

com α = cl(uf)/cl(gv).Profa Dra: Diane Castonguay INF-UFG



Base de Gröbner








Base de Gröbner








Base de Gröbner








Base de Gröbner








Base de Gröbner








Base de Gröbner

Relação de Divisão

Sejam f, g dois elementos de K<X>.Dizemos que existe uma relação de divisãoenvolvendo f e G sef = ugv, para algumas palavras de X∗.Neste caso, essa relação de divisão é dada por

D(f, g, u, v) = f − αugv

com α = cl(f)/cl(ugv).




Base de Gröbner








Base de Gröbner








Base de Gröbner

Proposição

Sejam f, g dois elementos de K<X>.Existe apenas um número �nito de relações de sobreposição e dedivisão envolvendo f e g.




Base de Gröbner

Proposição

Sejam f, g dois elementos de K<X>.Existe apenas um número �nito de relações de sobreposição e dedivisão envolvendo f e g.




PMORA

Procedimento de Mora (PMORA)O algoritmo recebe como entrada um conjunto �nitoF = {f1, f2, . . . , ft} de geradores de um ideal I de K<X>. Casotermine sua computação, ele devolve uma Base de Gröbner �nitapara I. Aindam se I possuir alguma Base de Gröbner �nita (para aordem admissível �xada), o procedimento termina.

1. R← ∅; G← F2. para cada par f, g ∈ G faça3. R← R ∪ CalculaRelações(f, g)4. �m-para5. enquanto R 6= ∅ faça6. r ← EscolheRelação(R)7. h← Divisão(G, r)8. se h 6= 09. então G← G ∪ {h}10. para cada par g ∈ G faça11. R← R∪ CalculaRelações(g, h)12. �m-para; �m-se;�m-enquanto13. devolva G




PMORA

Procedimento de Mora (PMORA)

1. R← ∅; G← F

2. para cada par f, g ∈ G faça3. R← R ∪ CalculaRelações(f, g)4. �m-para5. enquanto R 6= ∅ faça6. r ← EscolheRelação(R)7. h← Divisão(G, r)8. se h 6= 09. então G← G ∪ {h}10. para cada par g ∈ G faça11. R← R∪ CalculaRelações(g, h)12. �m-para; �m-se;�m-enquanto13. devolva G




PMORA

CalculaRelações(f, g)

Esta função recebe como entrada dois elementos de K<X> edevolve um conjunto contendo todas as relações de sobreposição ede divisão não nulas envolvendo os elementos f e g.

Esta função pode ser emplementada sem muita di�culdade fazendobuscas por subpalavras envolvendo f e g. Ademais, sua saída serásempre um conjunto �nito.




PMORA

CalculaRelações(f, g)

Esta função recebe como entrada dois elementos de K<X> edevolve um conjunto contendo todas as relações de sobreposição ede divisão não nulas envolvendo os elementos f e g.

Esta função pode ser emplementada sem muita di�culdade fazendobuscas por subpalavras envolvendo f e g. Ademais, sua saída serásempre um conjunto �nito.




PMORA

EscolheRelação(R)

Esta função recebe como entrada um conjunto composto porrelações de sobreposição e de divisão e devolve um desseselementos (removendo-o do conjunto original R).

Ela deve possuir a seguinte propriedade: se um elemento s éinserido no conjunto R e sucessivas chamadas são feitas para afunção EscolheRelação, s deve ser devolvido em um número �nitode chamadas de EscolheRelação.

Em outras palavras, exigimos que toda relação de sobreposição e dedivisão encontrada pelo procedimento seja considerada em tempo�nito.




PMORA

EscolheRelação(R)







PMORA

EscolheRelação(R)







PMORA

Exemplo

Seja K<a, b, c, d, e, f> com a ordem de peso e lexicográ�ca(a < b < c < d < e < f) com a seguinte aplicação peso:

φ(a) = 3 e φ(b) = φ(c) = φ(d) = φ(e) = φ(f) = 1

Consideremos I o ideal gerado por F = {g1, g2, . . . , g7} com:g1 := ca− ac g2 := da− ad g3 := ba− b2cg4 := be2 − b2c g5 := b2cf − bc g6 := e2f − bc2g7 := bcd




PMORA

Exemplo

Seja K<a, b, c, d, e, f> com a ordem de peso e lexicográ�ca(a < b < c < d < e < f) com a seguinte aplicação peso:

φ(a) = 3 e φ(b) = φ(c) = φ(d) = φ(e) = φ(f) = 1

Consideremos I o ideal gerado por F = {g1, g2, . . . , g7} com:g1 := ca− ac g2 := da− ad g3 := ba− b2cg4 := be2 − b2c g5 := b2cf − bc g6 := e2f − bc2g7 := bcd




PMORA

Teorema

Seja F = {f1, f2, . . . , ft} um conjunto gerador de um ideal I nãonulo de de K<X>.Se F for fornecido como entrada para o Procedimento de Mora,esse terminará em um número �nito de passos e devolverá umaBase de Gröbner �nita para I se e somente se I possui uma Basede Gröbner �nita.




PMORA

Teorema

Seja F = {f1, f2, . . . , ft} um conjunto gerador de um ideal I nãonulo de de K<X>.Se F for fornecido como entrada para o Procedimento de Mora,esse terminará em um número �nito de passos e devolverá umaBase de Gröbner �nita para I se e somente se I possui uma Basede Gröbner �nita.




PMORA

Bergman, G. M., The diamond lemma for ring theory, Adv. inMath. 29 (1978), no. 2, 178-218.

Bokut, L. A., Imbeddings into simple associative algebras,Algebra i Logika 15 (1976), no. 2, 117-142, 245.

Buchberger, B., On �nding a vector space basis of the residue

class ring modulo a zero dimensional polynomial ideal, Ph.D.thesis, Univ. of Innsbruck, Austria, 1965.

Mora, F., Gröbner bases for non-commutative polynomial rings,Algebraic algoritms and error-correcting codes: proceedings(Jacques Calmet, ed.), Lecture Notes in Computer Science,vol. 229, Springer-Verlag, 1986, 353-362.




PMORA

Mora, T., An introduction to commutative and

noncommutative Gröbner bases, Theoretical Computer Science134 (1994), 131-173.

Villas Bôas, A. A., Aspectos algébricos e computacionais da

teoria de bases de Gröbner não comutativas, Dissertação deMestrado, Univ. de São Paulo, Brasil, 2005.



Documents

Introdução a Teoria de Bases de Gröbnerdiane/Grobner.pdf · Motivação Subespaços Uma variável Comutativo Não Comutativo Para resolver estes problemas, precisamos das bases