FAMAT em Revista - Número 09 - Outubro de 2007
25
Ordenação de monômios, divisão em anéis de polinômios
de várias variáveis e as Bases de Groebner
Danilo Adrian Marques∗
Prof. Cı́cero Carvalho†
Faculdade de Matemática - FAMAT
Universidade Federal de Uberlândia - UFU
38408-100, Uberlândia - MG
Junho 2007
1
Ordens Sobre Monômios
Examinando em detalhes o algoritmo da divisão em K [x] e o escalonamento para sistemas de
equações lineares (ou matrizes), veremos que uma noção de ordem de termos é um ingrediente
chave de ambos (embora isto não seja freqüentemente enfatizado). Por exemplo, dividindo
f (x) = x5 − 3x2 + 1 por g (x) = x2 − 4x + 7 pelo método padrão, nós farı́amos:
i) escreverı́amos os termos do polinômio em ordem decrescente de grau de x
ii) no primeiro passo, o termo lı́der (o termo de maior grau) em f é: x5 = x3 · x2 =
x3 · (termo lı́der em g). Então, nós subtraı́mos x3 · g (x) de f para cancelar o termo lı́der,
ficando 4x4 − 7x3 − 3x2 + 1
iii) então, nós repetı́riamos o mesmo processo sobre f (x) − x3 · g (x), etc. até obtermos um
polinômio de grau menor que 2
Para o algoritmo da divisão sobre polinômios de uma variável, então, nós lidamos com a
ordem de grau sobre monômios de uma variável:
. . . > xm+1 > xm > . . . > x2 > x > 1
(1)
Similarmente, no algortimo de escalonamento sobre matrizes, em alguma linha dada, nós
trabalhamos sistematicamente com a primeira entrada da esquerda - as entradas lı́deres são
aquelas entradas não nulas a extrema esquerda da linha. No nı́vel de equações lineares, este é
expressado pela ordem das variáveis x1 , . . . , xn como a seguir:
x1 > x 2 > . . . > x n
(2)
Nós escrevemos os termos nas nossas equações em ordem decrescente. Além disso, num
sistema na forma escalonada (onde a primeira entrada não nula de cada linha é 1, e todas as
outras entradas na coluna contendo um lı́der 1 são zero) as equações são listadas com seus
∗
†
Orientando de Iniciação Cientı́fica: FAPEMIG. E-mail: [email protected]
Professor Orientador - E-mail: [email protected]
26
FAMAT em Revista - Número 09 - Outubro de 2007
termos lı́deres em ordem decrescente (de fato, a definição precisa de um sistema na forma
escalonada poderia ser dada em termos desta ordem).
Da evidência acima, podemos imaginar que uma componente muito importante de alguma
extensão da divisão e escalonamento para polinômios arbitrários em várias variáveis é uma ordem de termos em polinômios em K [x1 , . . . , xn ]. Aqui, discutiremos as propriedades desejáveis
que as ordens poderiam ter, e construiremos vários exemplos diferentes que satisfarão nossas
necessidades. Cada uma destas ordens será usada em diferentes contextos.
Primeiro observamos que podemos reconstruir o monômio xα = xα1 1 . · · · .xαnn a partir da
n-upla de expontes α = (α1 , . . . , αn ) ∈ Zn≥0 . Esta observação estabelece uma correspondência
bijetiva entre monômios em K [x1 , . . . , xn ] e o conjunto Zn≥0 . Além disso, qualquer ordem >
sobre o espaço Zn≥0 nos dará uma ordem sobre monômios: se α > β, de acordo com esta ordem,
nós também diremos que xα > xβ .
Existem várias maneiras diferentes de se definir uma ordem sobre Zn≥0 , mas exigimos sempre
que tais ordens sejam compatı́veis com a estrutura algébrica de anéis polinomiais.
Para começar, como um polinômio é uma soma de monômios, nós gostarı́amos ser capazes
de organizar os termos em um polinômio sem ambigüidade na ordem decrescente (ou crescente).
Para fazer isto, nós temos que ser capazes de comparar todo par de monômios para estabelecer
sua posição relativa. Então exigimos que a ordem seja total, i.e. para todo par de monômios
xα e xβ , exatamente uma das três condições seja verdadeira:
xα > xβ ou xα = xβ ou xα < xβ
A seguir, nós temos que levar em conta o efeito da soma e do produto sobre polinômios.
Quando adicionamos polinômios podemos simplesmente reorganizar os termos na ordem apropriada para a presente soma sem dificuldades. Produtos são mais sutis, entretanto. Como a
multiplicação no anel polinomial distribui sobre adição, é suficiente considerar o que acontece
quando nós multiplicamos um monômio por um polinômio. Então, nós exigimos que todas as
ordens de monômios tenham a seguinte propriedade adicional: se xα > xβ e xγ é um monômio
qualquer, então xα ·xγ > xβ ·xγ . Em termos dos vetores de expoentes, esta propriedade significa
que se α > β na nossa ordem sobre Zn≥0 , então, para todo γ ∈ Zn≥0 , α + γ > β + γ.
Com essas considerações em mente, nós fazemos a seguinte definição.
Definição 1 Uma ordem de monômios sobre K [x1 , . . . , xn ] é uma relação > sobre Zn≥0 , ou
equivalentemente, uma relação no conjunto dos monômios xα , α ∈ Zn≥0 , satisfazendo:
i) > é uma ordem total sobre Zn≥0 ;
ii) Se α > β e γ ∈ Zn≥0 , então α + γ > β + γ;
iii) > é uma boa ordenação sobre Zn≥0 . Isto significa que todo conjunto não vazio de Zn≥0 tem
um elemento mı́nimo em relação a >.
O Lema a seguir nos ajudará a entender o que a condição da boa ordenação da parte (iii)
da definição significa.
Lema 1.1 Uma relação de ordem > sobre Zn≥0 é uma boa ordenação se e somente se toda
seqüência estritamente decrescente em Zn≥0
α (1) > α (2) > α (3) > . . .
eventualmente termina.
FAMAT em Revista - Número 09 - Outubro de 2007
27
Demonstração:
Provaremos a contrapositiva: > não é uma boa ordenação se e somente se existe uma
seqüência estritamente decrescente infinita em Zn≥0 .
Se > não é uma boa ordenação, então algum subconjunto não vazio S ⊂ Zn≥0 não tem um
menor elemento. Agora pegue α (1) ∈ S. Já que α (1) não é o menor elemento, nós podemos
encontrar α (2) ∈ S tal que α (1) > α (2) em S. Então α (2) também não é o menor elemento,
então existe α (3) tal que α (2) > α (3) em S. Continuando este processo, nós temos uma
seqüência estritamente decrescente infinita: α (1) > α (2) > α (3) > . . ..
Por outro lado, dada uma seqüência infinita, então {α (1) , α (2) , α (3) , . . .} é um subconjunto não vazio de Zn≥0 sem o menor elemento, e então > não é uma boa ordenação.
2
Esse lema será usado para mostrar que vários algoritmos podem ser terminados, por que
alguns termos são estritamente decrescentes (com respeito a uma determinada ordem fixada)
em cada passo do algoritmo.
Como um exemplo simples de uma ordem de monômios, vemos que a ordem numérica usual
... > m + 1 > m > ... > 3 > 2 > 1 > 0
nos elementos de Z≥0 satisfaz as três condições da Definição 1. Então, a ordenação grau (1)
sobre monômios em K [x] é uma ordem de monômios.
Nosso primeiro exemplo de uma ordem sobre n-uplas será a ordem lexicográfica (ou ordem
lex, abreviadamente).
Definição 2 (Ordem Lexicográfica) Sejam α = (α1 , . . . , αn ), β = (β1 , . . . , βn ) ∈ Zn≥0 . Nós
dizemos que α >lex β se no vetor diferença α − β ∈ Zn a primeira entrada não nula a partir
da esquerda é positiva. Escrevemos xα >lex xβ se α >lex β.
Exemplo 1.1
i) (1, 2, 0) >lex (0, 3, 4) já que α − β = (1, −1, −4);
ii) (3, 2, 4) >lex (3, 2, 1) já que α − β = (0, 0, 3);
iii) As variáveis x1 , . . . , xn foram ordenadas do jeito usual [veja 2] pela ordem lex:
(1, 0, . . . , 0) >lex (0, 1, 0, . . . , 0) >lex . . . >lex (0, 0, . . . , 1),
então x1 >lex x2 >lex . . . >lex xn
Na prática, quando trabalhamos com polinômios em duas ou três variáveis, chamamos as
variáveis de x, y, z em vez de x1 , x2 , x3 . Também assumiremos que a ordem alfabética x >
y > z sobre variáveis é usada para definir a ordem lexicográfica a menos que dissermos outra
explicitamente.
A ordem Lex é análoga a ordem de palavras usadas em dicionários (por isso o nome).
Proposição 1.1 A ordem lex sobre Zn≥0 é uma ordem de monômios.
Demonstração: Ver [1]
2
Existem várias ordens lex, dependendo de como as variáveis são ordenadas. Até agora, nós
temos usado a ordem lex com x1 > x2 > . . . > xn , mas dada qualquer ordem das variáveis
x1 , x2 , . . . , xn , existe uma ordem lex correspondente. Por exemplo, se as variáveis são x e y,
então temos uma primeira ordem lex com x > y e uma segunda com y > x. No caso geral de n
variáveis, existem n! ordens lex. No que segue, a frase “ordem lex”se referirá à primeira, com
x1 > x2 > . . . > xn , a menos que explicitada de outra forma.
28
FAMAT em Revista - Número 09 - Outubro de 2007
Observe que na ordem lex, independentemente do grau total, uma variável é maior que
qualquer monômio envolvendo variáveis menores, por exemplo, utilizando a ordem lex x > y >
z, temos x >lex y 5 z 3 .
Para alguns propósitos, queremos considerar o grau total dos monômios e ordenar monômios
de maior grau primeiro. Nossa primeira forma de se fazer isto é a ordem lexicográfica graduada
(ou ordem grlex).
Definição 3 (Ordem Grau-lex): Seja α, β ∈ Zn≥0 . Dizemos que α >grlex β se:
|α| =
n
X
αi > |β| =
i=1
n
X
βi ou |α| = |β| e α >lex β
i=1
Assim, podemos concluir que as ordens grlex são dadas pelo grau total em primeiro lugar e
então “desempatamos”usando a ordem lex.
Exemplo 1.2
i) (1, 2, 3) >grlex (3, 2, 0) já que |(1, 2, 3)| = 6 > 5 = |(3, 2, 0)|;
ii) (1, 2, 4) >grlex (1, 1, 5) já que |(1, 2, 4)| = |(1, 1, 5)| e (1, 2, 4) >lex (1, 1, 5);
iii) As variáveis são ordenadas de acordo com a ordem lex, isto é, x1 >grlex . . . >grlex xn .
Como no caso da ordem lex, existem n! ordens grlex sobre n variáveis, dependendo de como
as variáveis são ordenadas.
Outra ordem, um tanto menos intuitiva, sobre monômios é a ordem lexicográfica graduada
reversa (ou ordem grevlex). Ainda que esta ordem dê algum trabalho para que nos acostumemos
com ela, a ordem grevlex em algumas operações, é a mais eficiente para computações (ou
cálculos).
Definição 4 (Ordem Grau-lex reversa): Seja α, β ∈ Zn≥0 . Dizemos que α >grevlex β se:
|α| =
n
X
i=1
αi > |β| =
n
X
βi ou
i=1
|α| = |β| e a primeira entrada não nula a partir da direita de α − β ∈ Zn≥0 é negativa.
Como na ordem grlex, a ordem grevlex é dada pelo grau total primeiro, porém, nesta ordem,
o “desempate” se dá de um jeito diferente.
Exemplo 1.3
i) (4, 7, 1) >grevlex (4, 2, 3) já que |(4, 7, 1)| = 12 > 9 = |4, 2, 3|;
ii) (1, 5, 2) >grevlex (4, 1, 3) já que |(1, 5, 2)| = |(4, 1, 3)| e (1, 5, 2) − (4, 1, 3) = (−3, 4, −1);
iii) A ordem grevlex dá a mesma ordem sobre as variáveis que a ordem lex:
(1, 0, . . . , 0) >grevlex (0, 1, 0, . . . , 0) >grevlex . . . >grevlex (0, 0, . . . , 1),
então x1 >grevlex x2 >grevlex . . . >grevlex xn
Igualmente as ordens lex e grlex, existem n! ordens grevlex, dependendo de como as variáveis
são ordenadas.
FAMAT em Revista - Número 09 - Outubro de 2007
2
29
Ordenando Polinômios
P
Se f = α aα xα é um polinômio em K [x1 , . . . , xn ] e escolhida uma ordem de monômios >,
podemos então ordenar os monômios de f sem ambigüidades com respeito a >.
Exemplo 2.1 Seja f = 4xy 2 z + 4z 2 − 5x3 + 7x2 z 2 ∈ K [x, y, z]
a) Com respeito a ordem lex, reordenando os termos de f na ordem decrescente temos:
f = −5x3 + 7x2 z 2 + 4xy 2 z + 4z 2
b) Com respeito a ordem grlex, temos:
f = 7x2 z 2 + 4xy 2 z − 5x3 + 4z 2
c) Com respeito a ordem grevlex, temos:
f = 4xy 2 z + 7x2 z 2 − 5x3 + 4z 2
Usaremos a seguinte terminologia:
Definição 5 Sejam f =
de monômios.
P
α
aα xα um polinômio não nulo em K [x1 , . . . , xn ] e > uma ordem
i) O multi-grau de f é:
¡
¢
multideg (f ) = max α ∈ Zn≥0 : aα 6= 0 (o máximo é dado com respeito a >)
ii) O coeficiente lı́der de f é:
LC (f ) = amutideg(f ) ∈ K
iii) O monômio lı́der de f é:
LM (f ) = xmultideg(f ) (com coeficiente 1)
iv) O termo lı́der de f é:
LT (f ) = LC (f ) · LM (f )
Exemplo 2.2 Seja f = −5x3 +7x2 z 2 +4xy 2 z +4z 2 (como acima) e seja > a ordem lex. Então:
multideg (f ) = (3, 0, 0)
LC (f ) = −5
LM (f ) = x3
LT (f ) = −5x3
30
3
FAMAT em Revista - Número 09 - Outubro de 2007
Algoritmo da Divisão em K [x1, . . . , xn]
Para estudar o problema da pertinência de polinômios de várias variáveis no ideal, formularemos
um algoritmo de divisão para polinômios em K [x1 , . . . , xn ] que estende o algoritmo para K [x].
No caso geral, a meta é dividir f ∈ K [x1 , . . . , xn ] por f1 , . . . , fs ∈ K [x1 , . . . , xn ]. Como
veremos, isto significa expressar f na forma:
f = a1 f1 + . . . + as fs + r
onde os “quocientes” a1 , . . . , as e o resto r estão em K [x1 , . . . , xn ]. Alguns cuidados serão
necessários para caracterizar o resto e neste momento usaremos as ordens de monômios introduzidas.
Após o algoritmo pronto veremos como aplicá-lo ao problema da pertinência.
A idéia básica do algoritmo é a mesma que no caso de uma variável: queremos cancelar o
termo lı́der de f (com respeito a ordem de monômios fixada) multiplicando algum fi por um
monômio apropriado e subtraı́-lo de f . Então esse monômio torna-se um termo correspondente
ai . Em vez de escrever o algoritmo no caso geral, primeiro trabalharemos com alguns exemplos
para ver o que é envolvido.
Exemplo 3.1 Primeiro dividiremos f = xy 2 + 1 por f1 = xy + 1 e f2 = y + 1 usando a ordem
lex com x > y. Queremos empregar o mesmo esquema para divisão de polinômios de uma
variável, sendo que a diferença é que existem vários divisores e quocientes.
xy 2 + 1
| xy + 1; y + 1
Os termos lı́deres LT (f1 ) = xy e LT (f2 ) = y ambos dividem o termo lı́der LT (f ) = xy 2 .
Já que f1 é listado primeiro, usaremos ele. Dividindo xy 2 por xy, temos y e então subtraimos
yf1 de f .
xy 2 + 1
xy 2 + y
−y + 1
|xy + 1; y + 1
y;
Agora repetimos o mesmo processo sobre −y +1. Dessa vez usaremos f2 já que LT (f1 ) = xy
não divide LT (−y + 1) = −y. Assim obtemos:
xy 2 + 1
xy 2 + y
−y + 1
−y − 1
2
|xy + 1; y + 1
y ; (−1)
Já que LT (f1 ) e LT (f2 ) não dividem 2, o resto é r = 2 e concluimos a divisão. Então,
temos escrito f = xy 2 + 1 na forma:
xy 2 + 1 = y (xy + 1) + (−1) (y + 1) + 2
Exemplo 3.2 Neste exemplo, encontraremos uma sutileza inesperada que pode ocorrer quando
estamos trabalhando com polinômios de mais de uma variável. Vamos dividir f = x2 y +xy 2 +y 2
por f1 = xy − 1 e f2 = y 2 − 1. Como no exemplo anterior, usaremos a ordem lex com x > y.
FAMAT em Revista - Número 09 - Outubro de 2007
31
Os dois primeiros passos do algoritmo são usuais, dando assim a seguinte divisão parcialmente
completada.
x2 y + xy 2 + y 2
x2 y − x
xy 2 + x + y 2
xy 2 − y
x + y2 + y
|xy − 1; y 2 − 1
x+y ;
Note que nem LT (f1 ) = xy nem LT (f2 ) = y 2 dividem LT (x + y 2 + y) = x. Entretanto,
x + y 2 + y não é o resto já que LT (f2 ) divide y 2 . Então, se movemos x para o resto, podemos
continuar dividindo.
Observação 3.1 Este é um problema que nunca acontece no caso de uma variável: uma vez
que o termo lı́der do divisor não divide mais o termo lı́der que está abaixo do radical, o algoritmo
termina.
Para executar essa idéia, criamos uma coluna de resto r, do lado esquerdo do radical, onde
colocamos os termos que pertencem ao resto. E então continuamos dividindo até o dividendo
intermediário seja zero (chamamos o polinômio debaixo do radical de dividendo intermediário).
Aqui está o próximo passo, onde movemos x para a coluna do resto (como indicado pela seta):
r
x
x2 y + xy 2 + y 2
x2 y − x
xy 2 + x + y 2
xy 2 − y
x + y2 + y
←−
y2 + y
|xy − 1; y 2 − 1
x+y ;
Agora continuamos dividindo. Se podemos dividir pelo LT (f1 ) ou LT (f2 ), procedemos
como usualmente, e se nenhum divide, movemos o termo lı́der do dividendo intermediário para
a coluna do resto. Aqui está o resto da divisão:
r
x
x+y
x+y+1
x2 y + xy 2 + y 2
x2 y − x
xy 2 + x + y 2
xy 2 − y
x + y2 + y
←− y 2 + y
y2 − 1
y+1
←−
1
←−
0
|xy − 1; y 2 − 1
x+y ; 1
Então, o resto é x + y + 1, e obtemos:
¡
¢
x2 y + xy 2 + y 2 = (x + y) (xy − 1) + 1 y 2 − 1 + x + y + 1
(3)
Observe que o resto é a soma de monômios, nenhum dos quais é divisı́vel pelos termos lı́deres
LT (f1 ) ou LT (f2 ).
32
FAMAT em Revista - Número 09 - Outubro de 2007
O exemplo acima é uma ilustração bastante completa de como o algoritmo da divisão trabalha. Este exemplo nos mostra também qual propriedade nós queremos que o resto tenha:
nenhum dos termos pode ser divisı́vel pelos termos lı́deres dos polinômios que estão dividindo.
Podemos agora enunciar a forma geral do algortimo da divisão.
Teorema 3.1 (Algortimo da Divisão em K [x1 , . . . , xn ]): Fixe uma ordem de monômios > sobre Zn≥0 e seja F = (f1 , . . . , fs ) uma s-upla de polinômios ordenadas em K [x1 , . . . , xn ]. Então
todo f ∈ K [x1 , . . . , xn ] pode ser escrito como:
f = a1 f1 + . . . + as fs + r
onde ai ,r ∈ K [x1 , . . . , xn ], e qualquer r = 0 ou r é uma combinação linear, com coeficientes
em K, de monômios, nenhum dos quais é divisı́vel por nenhum dos LT (f1 ) , . . . , LT (fs ). Nós
chamaremos r um resto de f na divisão por F . Além disso, se ai fi 6= 0, então temos:
multideg (f ) ≥ multideg (ai fi )
Demonstração: Provemos a existência de a1 , . . . , as e r dando um algoritmo para a
construção deles e mostrando que ele opera corretamente sobre qualquer entrada dada. Vejamos
a seguinte generalização:
Input : f1 , . . . , fs , f
Output : a1 , . . . , as , r
a1 := 0, . . . , as := 0, r := 0
p := f
W hile p 6= 0 Do
i := 1
divisionocurred := f alse
W hile i ≤ s e divisionocurred = f alse Do
If LT (fi ) divides LT (p) T hen
ai := ai + LT (p) / LT (fi )
p := p − (LT (p) /LT (fi )) fi
divisionocurred = true
Else
i := i + 1
If divisionocurred = f alse T hen
r := r + LT (p)
p := p − LT (p)
Relacionando este algoritmo com o exemplo anterior observamos que a variável p representa
o dividendo intermediário para cada estágio, a variável r representa a coluna do lado esquerdo, e
as variáveis a1 , . . . , as são os quocientes. Finalmente, a variável booleana “divisionocurred”nos
fala quando algum LT (fi ) divide o termo lı́der do dividendo intermediário. Observe que cada
vez que vamos através do laço principal W hile . . . Do, precisamente uma das duas coisas acontece:
i) (Passo da Divisão): Se algum LT (fi ) divide LT (p), então o algoritmo procede como o
caso de uma variável;
ii) (Passo do Resto): Se nenhum LT (fi ) divide LT (p), então o algoritmo adiciona LT (p)
para o resto.
FAMAT em Revista - Número 09 - Outubro de 2007
33
Estes passos correspondem exatamente ao que fizemos no Exemplo 3.2. Para provar que o
algoritmo funciona, primeiro mostraremos que:
f = a1 f1 + . . . + as fs + r
(4)
é válido para todos os estágios. Isto é claramente verdadeiro para os valores iniciais de a1 , . . . ,
as , p e r. Agora suponha que (4) é válido para um passo do algoritmo. Se o próximo passo for
um Passo da Divisão, então algum LT (fi ) divide LT (p) e a igualdade
ai fi + p = (ai + LT (p) / LT (fi )) fi + (p − (LT (p) / LT (fi )) fi )
mostra que ai fi + p é inalterado. E como todas as outras variáveis não são afetadas, temos que
(4) é verdadeira. Por outro lado, se o próximo passo for o Passo do Resto, então p e r serão
mudados, mas a soma p + r é inalterada já que
p + r = (p − LT (p)) + (r + LT (p))
e como antes, a igualdade (4) é ainda preservada.
A seguir, observe que o algoritmo pára quando p = 0. Nesta situação, (4) torna-se:
f = a 1 f1 + . . . + a s fs
Já que os termos são adicionados a r somente quando eles não são divisı́veis por nenhum dos
LT (fi ), isso segue que a1 , . . . , as e r tem a propriedade desejada quando o algoritmo termina.
Finalmente, precisamos mostrar que o algoritmo eventualmente termina. A observação
chave é que cada vez que redefinimos a variável p, qualquer um dos seus multi-graus diminui
(relativo a nossa ordem de termos) ou se torna 0. Para ver isso, primeiro suponha que durante
um Passo da Divisão, p é redefinida por:
p0 = p −
Assim temos que:
µ
LT
LT (p)
fi
LT (fi )
¶
=
LT (p)
fi
LT (fi )
LT (p)
LT (fi ) = LT (p)
LT (fi )
para que p e LT (p) / LT (fi ) fi tenham o mesmo termo lı́der. Então, a diferença deles, p0 ,
tem o multi-grau estritamente menor quando p0 6= 0. A seguir, suponha que durante um Passo
do Resto, p é redefinido por:
p0 = p − LT (p)
Aqui, é óbvio que multideg (p0 ) < multideg (p) quando p0 6= 0. Então, em qualquer um
dos casos, o multi-grau cai. Se o algoritmo nunca terminasse, então terı́amos uma seqüência
decrescente infinita de multi-graus. A propriedade da boa ordenação de >, como mostrado no
Lema 1.1, mostra que isto não pode ocorrer. Então p = 0 tem que ocorrer eventualmente, para
que o algoritmo termine depois de vários passos finalmente.
Resta estudar a relação entre multideg (f ) e multideg (ai fi ). Todo termo em ai é da forma
LT (p) / LT (fi ) para algum valor da variável p. O algoritmo começa com p = f e acabamos
de provar que o multi-grau de p decresce. Isto mostra que LT (p) ≤ LT (f ), e então temos que:
LT (p) ≤ LT (f ) =⇒
LT (p)
LT (f )
LT (p)
LT (f )
≤
=⇒
LT (fi ) ≤
LT (fi ) =⇒
LT (fi )
LT (fi )
LT (fi )
LT (fi )
=⇒ ai LT (fi ) ≤ LT (f ) =⇒ multideg (ai fi ) ≤ multideg (f )
34
FAMAT em Revista - Número 09 - Outubro de 2007
quando ai fi 6= 0. Isto prova o Teorema.
2
A álgebra por detrás do algoritmo da divisão é muito simples (não existe nada além da
álgebra que foi feita no colegial), o que surpreende é que esta forma de algoritmo foi isolada e
explorada somente nos últimos 30 anos.
Infelizmente, esse algoritmo não possui as mesmas propriedades agradáveis da versão de
uma variável.
A primeira propriedade importante do algoritmo da divisão em K [x] é que o resto não é
unicamente determinado. Para ver isto considere o seguinte exemplo:
Exemplo 3.3 Vamos dividir f = x2 y + xy 2 + y 2 por f1 = y 2 − 1 e f2 = xy − 1. Usaremos a
ordem lex com x > y. Este é o mesmo exemplo 3.2, exceto que mudamos a ordem dos divisores.
r
2x
2x + 1
x2 y + xy 2 + y 2
xy 2 − x
x2 y + x + y 2
y2 − 1
x2 y + x + 1
x2 y − x
2x + 1
←−
1
←−
0
|y 2 − 1; xy − 1
x+1 ; x
Isto mostra que:
¡
¢
x2 y + xy 2 + y 2 = (x + 1) y 2 − 1 + x (xy − 1) + 2x + 1
(5)
Se compararmos esta equação com a equação (3), veremos que o resto é diferente do que
vimos no Exemplo 3.2.
Isto mostra que o resto não é unico, ou seja, para cada ordem F = (f1 , . . . , fs ), existe um
resto na divisão de f por F .
Uma caracterı́stica agradável do Algortimo da Divisão em K [x] é o jeito dele resolver o
problema da pertinência de polinômio de uma variável no ideal. Nós temos alguma coisa
similar para várias variáveis? Uma conseqüência é um simples corolário do Teorema 3.1: se
após a divisão de f por F = (f1 , . . . , fs ) obtermos um resto r = 0, então f = a1 f1 + . . . + as fs ,
de forma que f ∈ hf1 , . . . , fs i. Então r = 0 é uma condição suficiente para o problema da
pertinência. Contudo, como o seguinte exemplo mostra, r = 0 não é uma condição necessária
para estar no ideal.
Exemplo 3.4 Seja f1 = xy + 1, f2 = y 2 − 1 ∈ K [x, y] com a ordem lex. Dividindo f = xy 2 − x
por F = (f1 , f2 ), o resultado é:
¡
¢
xy 2 − x = y (xy + 1) + 0 y 2 − 1 + (−x − y)
Com F = (f2 , f1 ), entretanto, temos:
¡
¢
xy 2 − x = x y 2 − 1 + 0 (xy + 1) + 0
O segundo cálculo mostra que f ∈ hf1 , f2 i. Então o primeiro cálculo mostra que ainda que
f ∈ hf1 , f2 i, é ainda possı́vel obter um resto não nulo na divisão por F = (f1 , f2 ) .
Então concluı́mos que o Algoritmo da Divisão dado é uma generalização imperfeita do
equivalente de uma variável. E para resolver essa imperfeição para o problema da pertinência,
serão necessárias as Bases de Hilbert.
FAMAT em Revista - Número 09 - Outubro de 2007
4
O Teorema das
de Groebner
Bases
de
35
Hilbert
e
as
Bases
Definição 6 Um ideal I ⊂ K [x1 , . . . , xn ] é um ideal de monômios se existe um conjunto
S ⊂ Zn≥0 (possivelmente infinito) tal que I consiste de todos os polinômios que são somas finitas
da forma Σα∈A hα xα , onde hα ∈ K [x1 , . . . , xn ]. Neste caso, escrevemos I = hxα : α ∈ Ai
Lema 4.1 Seja I = hxα : α ∈ Ai um ideal de monômios. Então um monômio xβ pertence a I
se e somente se xβ é divisı́vel por xα para algum α ∈ A.
Observe que xβ é divisı́vel por xα exatamente quando xβ = xα · xγ para algum γ ∈ Zn≥0 .
Lema 4.2 Seja I um ideal de monômios, e seja f ∈
condições são equivalentes:
K [x1 , . . . , xn ]. Então as seguintes
i) f ∈ I
ii) Todo termo de f está em I
iii) f é uma K-combinação linear de monômios em I
Corolário 4.1 Dois ideais de monômios são os mesmos se, e somente se, eles contém os
mesmos monômios.
Teorema 4.1 (Lema de Dickson): Um ideal de monômios I = hxα : α ∈ Ai ⊂ K [x1 , . . . , xn ]
pode ser escrito sobre a forma I = hxα(1) , . . . , xα(s) i, onde α(1), . . . , α(s) ∈ A. Em particular,
I tem uma base finita.
O Teorema 4.1 soluciona a descrição do ideal para ideais de monômios, por ele dizer que
qualquer ideal tem uma base finita. Isto, por sua vez, nos permite resolver o problema da
pertinência para ideais de monômios. A saber, se I = hxα(1) , . . . , xα(s) i, então podemos facilmente mostrar que um polinômio f está em I se, e somente se, o resto de f na divisão por
xα(1) , . . . , xα(s) é zero.
Definição 7 Seja I ⊂ K [x1 , . . . , xn ] um ideal diferente de 0.
i) Denotamos por LT (I) o conjunto dos termos lı́deres dos elementos de I. Então,
LT (I) = cxα : existe f ∈ I com LT (f ) = cxα
ii) Denotamos por hLT (I)i o ideal gerado pelos elementos de LT (I)
Já vimos que os termos lı́deres têm um importante papel no algoritmo da divisão. Com
isso, surgi uma sutileza que deve ser mencionada: se damos um conjunto gerador finito para I,
digamos I = hf1 , . . . , fs i, então hLT (f1 ), . . . , LT (fs )i e hLT (I)i podem ser ideais diferentes. É
verdade que hLT (fi )i ∈ LT (I) ⊂ hLT (I)i pela definição, que implica hLT (f1 ), . . . , LT (fs )i ⊂
hLT (I)i. Entretanto, hLT (I)i pode ser estritamente maior. Para ver isto, considere o exemplo
a seguir.
36
FAMAT em Revista - Número 09 - Outubro de 2007
Exemplo 4.1 Seja I = hf1 , f2 i, onde f1 = x3 − 2xy e f2 = x2 y − 2y 2 + x e a ordem grlex sobre
monômios em K [x, y]. Então,
x · (x2 y − 2y 2 + x) − y(x3 − 2xy) = x2
e x2 ∈ I. Logo, x2 = LT (x2 ) ∈ hLT (I)i. Entretanto, x2 ∈ I não é divisı́vel por LT (f1 ) = x3
ou LT (f2 ) = x2 y, logo, x2 não pertence hLT (f1 ), LT (f2 )i pelo Lemma 4.1.
Agora mostraremos que hLT (I)i é um ideal monomial e isto nos permitirá aplicar os resultados anteriores. Em particular, seguirá que hLT (I)i é gerado por um número finito de termos
lı́deres.
Proposição 4.1 Seja I ⊂ K [x1 , . . . , xn ] um ideal.
i) hLT (I)i é um ideal monomial
ii) Existem g1 , . . . , gt ∈ I tal que hLT (I)i = hLT (g1 ), . . . , LT (gt )i
Demonstração:
i) O monômio lı́der LM (g) dos elementos g ∈ I − {0} gera o ideal monomial
hLM (g) : g ∈ I − {0}i. Já que LM (g) e LT (g) diferem apenas por uma constante
não nula, pelo Corolário 4.1 temos que hLM (g) : g ∈ I − {0}i = hLT (I)i. Então, hLT (I)i
é um ideal monomial.
ii) Já que hLT (I)i é gerado pelos monômios LM (g) para g ∈ I − {0}, o Lema de Dickson nos
diz que hLT (I)i = hLM (g1 ), . . . , LM (gt )i para infinitos g1 , . . . , gt ∈ I. Já que LM (gi )
difere de LT (gi )apenas por uma constante não nula, novamente pelo Corolário 4.1, temos
que hLT (I)i = hLT (g1 ), . . . , LT (gt )i e isto completa a prova.
2
Agora, podemos usar a Proposição 4.1 e o Algoritmo da Divisão para provar a existência de
um conjunto gerador finito de todo ideal de polinômios e, então dando uma resposta afirmativa
para o problema da descrição. Seja I ⊂ K [x1 , . . . , xn ] um ideal qualquer e considere o ideal
associado hLT (I)i como na Definição 7. Como sempre, selecionamos uma ordem de monômio
particular para usar no algoritmo da divisão e na computação dos termos lı́deres.
Teorema 4.2 (Teorema da Base de Hilbert): Todo ideal I ⊂ K [x1 , . . . , xn ] tem um conjunto
gerador finito. Isto, é, I = hg1 , . . . , gt i para algum g1 , . . . , gt ∈ I
Demonstração:
Se I = {0}, tomamos nosso conjunto gerador como {0}, que certamente é finito.
Se I contém algum polinômio não nulo, então um conjunto gerador g1 , . . . , gt para I pode
ser construido como a seguir. Pela Proposição 4.1, existem g1 , . . . , gt ∈ I tal que hLT (I)i =
hLT (g1 ), . . . , LT (gt )i. Afirmamos que I = hg1 , . . . , gt i.
É claro que I = hg1 , . . . , gt i ⊂ I, já que cada gi ∈ I. Por outro lado, seja f ∈ I um polinômio
qualquer. Se aplicarmos o algoritmo da divisão para dividir f por hg1 , . . . , gt i então chegamos
numa expressão da forma:
f = a1 g1 + . . . + at gt + r
FAMAT em Revista - Número 09 - Outubro de 2007
37
onde nenhum termo de r é divisı́vel por nenhum dos LT (g1 ), . . . , LT (gt ).
Afirmamos que r = 0. Para ver isto, observe que:
r = f − a1 g1 + . . . + at gt ∈ I
Se r 6= 0, então LT (r) ∈ hLT (I)i = hLT (g1 ), . . . , LT (gt )i, e pelo Lema 4.1, segue que LT (r)
deve ser divisı́vel por algum LT (gi ). Isto contradiz o fato dele ser o resto e, conseqüentemente,
r tem que ser zero. Então,
f = a1 g1 + . . . + at gt + 0 ∈ hLT (g1 ), . . . , LT (gt )i
que mostra que I ⊂ hg1 , . . . , gt i e, portanto, I = hg1 , . . . , gt i
2
Além de responder a questão da descrição do ideal, a base {g1 , . . . , gt } usada na prova do
Teorema 4.2 tem a propriedade especial hLT (I)i = hLT (g1 ), . . . , LT (gt )i. Como nem todas as
bases possuem essa propridade, como vimos no exemplo 3.2, às essas bases daremos o seguinte
nome.
Definição 8 Fixe uma ordem de monômios. Um subconjunto finito G = {g1 , . . . , gt } de um
ideal I é dito ser uma base de Groebner (ou base padrão) se
hLT (g1 ), . . . , LT (gt )i = hLT (I)i
Equivalentemente, mas mais informalmente, um conjunto {g1 , . . . , gt } ⊂ I é uma base de
Groebner de I se, e somente se, o termo lı́der de algum elemento de I é divisı́vel por um dos
LT (gi ). A prova do Teorema 4.2 também estabelece o seguinte resultado.
Corolário 4.2 Fixe uma ordem de monômios. Então todo ideal I ⊂ K [x1 , . . . , xn ] diferente
de {0} tem uma base de Groebner. Além disso, qualquer base de Groebner para um ideal I é
uma base de I.
Definição 9 Seja K um corpo e sejam f1 , . . . , fs polinômios em K [x1 , . . . , xn ]. Denotamos
por variedade afim definida por f1 , . . . , fs o seguinte conjunto:
V (f1 , . . . , fs ) = {(a1 , . . . , an ) ∈ K n : fi (a1 , . . . , an ) = 0, para todo 1 ≤ i ≤ s}
Exemplo 4.2 Seja J = hg1 , g2 i = hx + z, y − zi. Temos que g1 e g2 formam uma base de
Groebner usando a ordem lex em R[x, y, z].
Vamos mostrar que a forma inicial de todo elemento não nulo de J implica no ideal
hLT (g1 ), LT (g1 )i = hx, yi. Pelo Lema 4.1, isto é equivalente mostrando que o termo lı́der de
qualquer elemento não nulo de J é divisı́vel por x ou y.
Para provar isto, considere algum f = Ag1 + Bg2 ∈ J. Suponha, por absurdo, que f é não
nulo e LT (f ) não é divisı́vel por x e nem por y. Então pela definição de ordem lex, f será um
polinômio em z somente. Entretanto, f se anula no subespaço linear L = V (x + z, y − z) ⊂ R3
já que f ∈ J.
Observe que (x, y, z) = (−t, t, t), para algum número real t, já que pela definição de V ,
x + z = 0 ⇒ x = −z e y − z = 0 ⇒ y = z e assim fazendo z = t, temos (−t, t, t).
O único polinômio em z que anula nesses infinitos pontos é o polinômio nulo, o que é uma
contradição. (De fato, pois caso contrário, terı́amos que o polinômio possuindo grau igual a d
possuiria infinitas raizes, o que é um absurdo.)
Assim segue que hg1 , g2 i é uma base de Groebner.
38
FAMAT em Revista - Número 09 - Outubro de 2007
Referências
[1] Cox, D. and Little, J. and O’Shea, D., Ideals, varieties, and algorithms, Springer, segunda
edição, 1991.
[2] Kreuzer, M. and Robbiano, L , Computational Commutative Algebra 1, Springer, 2000.
[3] CoCoA: a system for doing Computations in Commutative Algebra, disponı́vel em
http://cocoa.dima.unige.it