Introdução a Teoria de Bases de Gröbnerdiane/Grobner.pdf · Motivação Subespaços Uma...

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

Profa Dra: Diane Castonguay

INF-UFG

Setembro de 2007

Profa Dra: Diane Castonguay INF-UFG

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

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>

Profa Dra: Diane Castonguay INF-UFG

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

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

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]

Profa Dra: Diane Castonguay INF-UFG

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

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

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?

Profa Dra: Diane Castonguay INF-UFG

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

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

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?

Profa Dra: Diane Castonguay INF-UFG

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

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

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?

Profa Dra: Diane Castonguay INF-UFG

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

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

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?

Profa Dra: Diane Castonguay INF-UFG

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

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

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?

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

Sumário

Motivação

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

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>

Profa Dra: Diane Castonguay INF-UFG

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

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

O problema da pertinência em Subespaços

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 .)

Profa Dra: Diane Castonguay INF-UFG

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

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

O problema da pertinência em Subespaços

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 .)

Profa Dra: Diane Castonguay INF-UFG

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

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

O problema da pertinência em Subespaços

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 .)

Profa Dra: Diane Castonguay INF-UFG

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

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

O problema da pertinência em Subespaços

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 .)

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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)

Profa Dra: Diane Castonguay INF-UFG

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

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

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)

Profa Dra: Diane Castonguay INF-UFG

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

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

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)

Profa Dra: Diane Castonguay INF-UFG

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

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].Algoritmo da Divisão para polinômios em K[x]Algoritmo de Euclides

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

DivisãoPoli

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

DivisãoPoli

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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]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

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

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

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

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 ′

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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>?

Profa Dra: Diane Castonguay INF-UFG

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

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

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>?

Profa Dra: Diane Castonguay INF-UFG

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

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

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>?

Profa Dra: Diane Castonguay INF-UFG

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

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

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>?

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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

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

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

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

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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>De�niçõesAlgoritmo da DivisãoBase de GröbnerProcedimento de MoraProfa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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∗.

Profa Dra: Diane Castonguay INF-UFG

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

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

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∗.

Profa Dra: Diane Castonguay INF-UFG

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

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

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∗.

Profa Dra: Diane Castonguay INF-UFG

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

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

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∗.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

De�nições

Ordem de grau e lexicográ�ca

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

De�nições

Ordem de grau e lexicográ�ca

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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 .

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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}.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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).

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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

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

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.

Profa Dra: Diane Castonguay INF-UFG

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