ads:
UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE MATEM
´
ATICA
PROGRAMA DE P
´
OS-GRADUAC¸
˜
AO EM MATEM
´
ATICA APLICADA
Decomposi¸c˜ao de Politopos e
Aplica¸c˜oes na Fatora¸c˜ao de
Polinˆomios
por
Luiz Emilio Allem
Disserta¸c˜ao submetida como requisito parcial
para a obten¸c˜ao do grau de
Mestre em Matem´atica Aplicada
Prof. Dr. Vilmar Trevisan
Orientador
Porto Alegre, Setembro de 2005.
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
II
CIP - CATALOGAC¸
˜
AO NA PUBLICAC¸
˜
AO
Allem, Luiz Emilio
Decomposi¸c˜ao de Politopos e Aplica¸c˜oes na Fatora¸c˜ao de
Polinˆomios / Luiz Emilio Allem.—Porto Alegre: PPGMAp
da UFRGS, 2005.
121 p.: il.
Disserta¸c˜ao (mestrado) —Universidade Federal do Rio
Grande do Sul, Programa de P´os- Gradua¸c˜ao em Matem´atica
Aplicada, Porto Alegre, 2005.
Orientador: Trevisan, Vilmar
Disserta¸c˜ao: Matem´atica Aplicada
Politopos, Irredutibilidade de polinˆomios, Fatora¸c˜ao de
polinˆomios
ads:
III
Decomposi¸c˜ao de Politopos e Aplica¸c˜oes na Fatora¸c˜ao de Polinˆomios
por
Luiz Emilio Allem
Disserta¸c˜ao submetida ao Programa de P´os-Gradua¸c˜ao em Matem´atica
Aplicada do Instituto de Matem´atica da Universidade Federal do Rio Grande do Sul,
como requisito parcial para a obten¸c˜ao do grau de
Mestre em Matem´atica Aplicada
Linha de Pesquisa: Algoritmos Num´ericos e Alg´ebricos
Orientador: Prof. Dr. Vilmar Trevisan
Banca examinadora:
Prof. Dr. Jos´e Pl´ınio de Oliveira Santos
UNICAMP
Prof. Dr. Jaime Bruck Ripoll
PPGMAT/IM/UFRGS
Prof. Dr. Jos´e Afonso Barrionuevo
PPGMAp/IM/UFRGS
Disserta¸c˜ao apresentada e aprovada em
26 de Setembro de 2005.
Prof. Dra. Maria Cristina Varriale
Coordenador
IV
SUM
´
ARIO
LISTA DE ABREVIATURAS . . . . . . . . . . . . . . . . . . . . . . . VI
RESUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VII
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . VIII
1 INTRODUC¸
˜
AO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 CONVEXIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Convexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Hiperplanos e Fun¸c˜ao Suporte . . . . . . . . . . . . . . . . . . . . 7
2.3 Soma de Minkowski . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Subtra¸c˜ao de Minkowski . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Politopos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3 FAM
´
ILIAS IRREDUT
´
IVEIS . . . . . . . . . . . . . . . . . . . . . . 28
3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Crit´erio de Irredutibilidade . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Constru¸c˜ao de Politopos Integralmente Indecompon´ıveis . . . 35
3.4 Proje¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 DECOMPOSIC¸
˜
AO DE POLITOPOS . . . . . . . . . . . . . . . . . 48
4.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Envolt´oria Convexa no Plano . . . . . . . . . . . . . . . . . . . . . 49
4.3 Fatores e Decomposi¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Pol´ıgonos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Politopos de Alta Dimens˜ao . . . . . . . . . . . . . . . . . . . . . 66
5 FATORANDO POLIN
ˆ
OMIOS VIA POLITOPOS . . . . . . . . . 71
V
5.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.2 Fatora¸c˜ao Parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3 Equa¸c˜oes do levantamento de Hensel Modificadas . . . . . . . . 81
5.4 Lema Geom´etrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 O Teorema Principal . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6 CONCLUS
˜
AO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
BIBLIOGRAFIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
AP
ˆ
ENDICE A LEVANTAMENTO DE HENSEL . . . . . . . . . 103
AP
ˆ
ENDICE B EXEMPLO DE FATORAC¸
˜
AO VIA POLITOPOS 107
VI
LISTA DE ABREVIATURAS
[x, y] {x + λ(y − x) : λ ∈ [0, 1]}, segmento de reta entre x e y
· norma euclidiana
vert(P ) conjunto dos v´ertices do politopo P
int(P ) interior do politopo P
bd(P ) fronteira do politopo P
P rob(a) probabilidade de ocorrˆencia do evento a
log(n) logaritmo na base 2 de n
O(f(n)) ordem de complexidade
dim(V ) dimens˜ao de V
gerado(u) subespa¸co gerado por u
VII
RESUMO
A presente disserta¸c˜ao aborda pesquisas recentes sobre dois t´opicos dis-
tintos da Matem´atica. N˜ao ´e a primeira vez que as conex˜oes entre geometria e
´algebra s˜ao frut´ıferas, mas ´e somente agora que as id´eias geom´etricas est˜ao sendo
aplicadas efetivamente na fatora¸c˜ao de polinˆomios, um tema puramente alg´ebrico.
Mais es pecificamente, estudamos a decomposi¸c˜ao de politopos e suas
aplica¸c ˜oes na fatora¸c˜ao de polinˆomios. Come¸camos apresentando constru¸c˜oes de
politopos integralmente indecompon´ıveis que levam a crit´erios de irredutibilidade
de polinˆomios. Estudamos detalhadamente algoritmos para a decomposi¸c˜ao de poli-
topos, sempre ilustrados com exemplos e coment´arios sobre suas aplica¸c˜oes.
Terminamos apresentando um algoritmo desenvolvido por Fatima Salem,
Shuhong Gao e Alan Lauder, que fatora polinˆomios bivariados a partir da decom-
posi¸c˜ao do seu politopo de Newton associado. Esse algoritmo ´e um marco nes sa
´area j´a que traduz, pela primeira vez, de forma eficiente, id´eias geom´etricas para a
fatora¸c˜ao polinomial, usando uma t´ecnica similar ao levantamento de Hensel.
VIII
ABSTRACT
The present work deals with recent research about two distinct math-
ematical topics. It is not the first time that connections between geometry and
algebra are fruitful, but it is only now that geometric ideas are being applied effec-
tively in polynomial factorization, a purely algebraic theme.
More specifically we study the decomposition of polytopes and their
applications on polynomial factorization. We begin studying construction of inde-
composable polytopes which give many irreducibility criteria p olynomial. We study
thoroughly algorithms for decomposition of polytopes, always illustrated with ex-
amples and comments about their applications.
We finish presenting an algorithm developed by Fatima Salem, Shuhong
Gao and Alan Lauder for factoring bivariate polynomials from the decomposition of
the Newton polytope associated. This algorithm is a mark land in the field since it
translate, for the first time, effectivelly, geometric ideas for polynomial factorization
using a technic similar to Hensel lifting.
IX
AGRADECIMENTOS
Agrade¸co a meu pai Luiz Costa Allem, a minha m˜ae Marlei Beatriz
Allem e a minha irm˜a Luciane Beatriz Allem por todos esses anos de amor, com-
preens˜ao, motiva¸c˜ao e ajuda em todos os sentidos. Amo muito vocˆes.
Agrade¸co ao Professor e amigo Vilmar Trevisan que, durante todos os
anos, desde a gradua¸c˜ao at´e aqui, sempre me motivou e ajudou muito; com certeza,
sem o seu aux´ılio, eu n˜ao teria chegado at´e este ponto.
Agrade¸co aos queridos amigos e colegas Carlos Hoppen e Clarice Decian
que, durante a gradua¸c˜ao e o mestrado, nunca me deixaram desistir e sempre me
ajudaram muito. Adoro vocˆes.
Agrade¸co `a Professora e amiga Maria Cristina Varriale pela motiva¸c˜ao
e pelas conversas engra¸cadas que tivemos quando eu ia falar com o Professor Vilmar.
Agradecimento especial `a Professora Virg´ınia Maria Rodrigues da PUC-
RS por ter sugerido o problema e por ter participado dos semin´arios que deram
origem a este trabalho.
Agrade¸co ao professor Shuhong Gao, de Clemsom University, a quem
conheci atrav´es da Professora Virg´ınia e que, por meio de conversas, deixou muito
mais acess´ıveis e claras as id´eias de seus artigos em que esta disserta¸c˜ao est´a baseada.
Agrade¸co ao departamento de matem´atica que sempre me deu ´otimas
condi¸c˜oes de estudar e aux´ılio financeiro durante estes anos.
Agrade¸co a Deus por ter me dado sa´ude e vontade para chegar at´e aqui.
1
1 INTRODUC¸
˜
AO
O tema desta disserta¸c˜ao de mestrado ´e a conex˜ao entre polinˆomios
multivariados e politopos de Newton. Um dos primeiros resultados conhecidos li-
gando estes dois assuntos foi feito por Ostrowski em 1921 [16]. Ele associou a cada
polinˆomio multivariado f um politopo, dito politopo de Newton. Observou que
se o polinˆomio multivariado f fosse fator´avel, digamos f = gh, ent˜ao o politopo
de Newton associado a f seria decomposto como a soma do politopo de Newton
associado a g mais o politopo de Newton associado a h, sendo esta decomposi¸c˜ao
em rela¸c˜ao `a soma de Minkowski.
Motivado por tal resultado Shuhong Gao observa em [4] que cada vez
que encontrarmos um politopo integralmente indecompon´ıvel este levar´a a uma
fam´ılia de polinˆomios absolutamente irredut´ıveis, ou sej a, polinˆomios sobre um corpo
F que permanecem absolutamente irredut´ıveis sobre qualquer extens˜ao alg´ebrica de
F. Neste trabalho Gao apresenta constru¸c˜oes de politopos integralmente indecom-
pon´ıveis que levam a crit´erios para irredutibilidade absoluta de polinˆomios multi-
variados.
No trabalho feito por Gao e Lauder em [6, 8] s˜ao apresentrados dois
tipos de algoritmo. Um que decide a indecomponibilidade de politopos em R
n
via
proje¸c˜oes. Outro que constr´oi todos os fatores de um politopo em R
2
, pol´ıgonos.
Ambos algoritmos podem ser usados para encontrarmos fam´ılias de polinˆomios ab-
solutamente irredut´ıveis. E o segundo tipo tamb´em pode ser usado na fatora¸c˜ao de
polinˆomios bivariados.
No final dos trabalhos feitos por Gao e Lauder fica uma pergunta em
aberto: Dado um polinˆomio f, seja P seu politopo de Newton associado integral-
mente decompon´ıvel e seja K um fator integral de P , ´e poss´ıvel associar K a um
fator g de f? Esta pergunta foi respondida por Fatima Abu Salem, Shuhong Gao e
Alan G. B. Lauder em [18].
1 Introdu¸c˜ao 2
Eles responderam esta pergunta para o caso de politopos em R
2
, ou seja,
para polinˆomios bivariados. Pois, como pode ser visto na literatura em [5, 12, 13, 15]
a fatora¸c˜ao de polinˆomios em v´arias vari´aveis pode ser reduzida ao caso bivariado,
que n˜ao pode ser reduzido ao caso univariado por m´etodos polinomialmente efi-
cientes.
Como politopos s˜ao conjuntos convexos apresentaremos no cap´ıtulo 2
um apanhado de resultados a respeito dessa classe de conjuntos, particularmente
politopos. Iremos estudar algumas propriedades de soma e subtra¸c˜ao de Minkowski
pois quando estivermos tratando da decomposi¸c˜ao de politopos, esta sempre ser´a em
rela¸c˜ao `a soma de Minkowski. Gostar´ıamos de dar aten¸c˜ao esp ec ial a dois teoremas
que ser˜ao apresentados no mesmo cap´ıtulo. O teorema de Krein Milmam o qual
nos diz que um politopo ´e a envolt´oria convexa de seus v´ertices, ou seja, qualquer
elemento do politopo pode ser escrito como uma combina¸c˜ao convexa dos v´ertices.
Este resultado ser´a muito importante quando estivermos estudando os crit´erios de
indecomponibilidade de politopos do cap´ıtulo 3. E o teorema 2.4.1 o qual mostra que
um fator de um politopo carrega muitas caracter´ısticas do politopo. Este resultado
ser´a muito importante no cap´ıtulo 4 quando estive rmos tratando da decomposi¸c˜ao
de p olitopos em R
2
, ou seja, pol´ıgonos. Veremos que cada aresta de um pol´ıgono
pode ser decomposta, em rela¸c˜ao `a soma de Minkowski, como a s oma de duas arestas
ou como a soma de uma aresta a um ponto.
No cap´ıtulo seguinte estudaremos os resultados de Shuhong Gao, des-
critos nos artigos [4, 6]. Apresentaremos o crit´erio de irredutibilidade feito por Gao
em [4], o qual observa que se um dado politopo de Newton associado a um polinˆomio
multivariado f ´e integralmente indecompon´ıvel ent˜ao f ´e absolutamente irredut´ıvel.
´
E importante notar que um dado politopo pode representar in´umeros polinˆomios, ou
seja, podemos mudar os coeficientes dos termos do polinˆomio ou acrescentar novos
termos desde que estes n˜ao alterem o formato do politopo. Por isso, a determina¸c˜ao
de crit´erios de indecomponibilidade de politopos levar˜ao a fam´ılias de polinˆomios
absolutamente irredut´ıveis.
1 Introdu¸c˜ao 3
No final do cap´ıtulo 3 apresentaremos constru¸c˜oes de politopos integral-
mente indecompon´ıveis baseadas em proje¸c˜oes que foram feitas em [6]. Por exemplo,
se tivermos um quadrado e fizermos a proje¸c˜ao sobre um de seus lados e esta for
indecompon´ıvel esperamos que o quadrado tamb´em o seja.
No cap´ıtulo 4 estudaremos os algoritmos feitos por Shuhong Gao e Alan
Lauder em [4, 6] que testam a decomponibilidade integral de politopos e constr˜oem
fatores integrais se este for integralmente decompon´ıvel. Veremos que o problema
de verificar se um politopo ´e integralmente indecompon´ıvel ´e NP-completo mesmo
em dimens˜ao 2, logo n˜ao existe, a menos que P=NP, um algoritmo genuinamente
eficiente para decompor politopos. Os algoritmos podem se r usados, primeiro, como
em [4] que ser´a estudado no cap´ıtulo 3, ou seja, cada politopo integralmente indecom-
pon´ıvel ir´a gerar uma fam´ılia de polinˆomios absolutamente irredut´ıveis. Segundo, se
um dado politopo ´e integralmente decompon´ıvel ent˜ao utilizamos o algoritmo para
encontrarmos todos os fatores integrais do politopo, o que ser´a ´util na fatora¸c˜ao de
polinˆomios.
Como foi explorado em [4] cada politopo integralmente indecompon´ıvel
gera uma fam´ılia de polinˆomios absolutamente irredut´ıveis. Em [6] foram apresen-
tados algoritmos para decidir a decomponibilidade integral de politopos e construir
fatores, no caso deste ser integralmente decompon´ıvel. Por´em uma pergunta ainda
estava em aberto: Dado um polinˆomio f e seu politopo de Newton associado P in-
tegralmente decompon´ıvel. Seja K um fator integral de P . Ser´a que K corresponde
ao politopo de Newton associado de um fator g de f? Este problema foi resolvido
por Fatima Abu Salem, Shuhong G ao e Alan G. B. Lauder em [18], o qual ser´a
estudado no cap´ıtulo 5.
Nesta disserta¸c˜ao constam ainda dois apˆendices. O primeiro sobre o
m´etodo de Hensel, que foi primeiramente utilizado por Hans Zassenhauss em 1969
[23] e que ´e a base para o m´etodo de Gao para f atora¸c˜ao via politopos. O se-
gundo com um exemplo explicado detalhadamente no qual fatoramos um polinˆomio
bivariado f via politopos.
4
2 CONVEXIDADE
Neste cap´ıtulo estudaremos um apanhado de resultados acerca de con-
juntos convexos, particularmente politopos. Veremos algumas propriedades de soma
e subtra¸c˜ao de Minkowski, j´a que quando estivermos tratando da decomponibilidade
de politopos, esta sempre ser´a em rela¸c˜ao `a soma de Minkowski. Gostar´ıamos de
enfatizar a importˆancia de dois resultados que estudaremos a seguir. O teorema
de Krein-Milman, o qual nos diz que um politopo ´e a envolt´oria convexa de seus
v´ertices, ou seja, cada ponto de um politopo pode ser escrito como uma combina¸c˜ao
convexa de seus v´ertices. E, tamb´em, o teorema 2.4.1, o qual assegura que um
fator K de um politopo P tem muitas das caracter´ısticas de P . Em particular
quando estivermos tratando com politopos em R
2
, ou seja, pol´ıgonos, veremos que
cada aresta poder´a ser decomposta em rela¸c˜ao `a soma de Minkowski apenas como
a soma de um ponto e uma aresta ou como a soma de duas arestas, sendo estas
paralelas. Os resultados que ser˜ao estudados aqui foram retirados, principalmente,
de [3, 11, 14, 20, 24].
2.1 Convexidade
As formas b´asicas de geometria que estudaremos nesta se¸c˜ao ser˜ao pon-
tos, retas, planos e assim por diante, os quais s˜ao chamados de subespa¸cos afins.
Defini¸c˜ao 2.1.1. Um conjunto S ⊂ R
n
´e dito convexo se dados a, b ∈ S e λ ∈ [0, 1],
ent˜ao a + λ(b − a) = (1 − λ)a + λb ∈ S. Isto ´e, o segmento de reta entre a e b est´a
em S.
A figura 2.1 mostra `a direita um conjunto convexo e `a esquerda um
conjunto n˜ao convexo, pois esta possui um segmento de reta com pontos extremos
no conjunto que n˜ao est´a totalmente contido nele.
2 Convexidade 5
Figura 2.1: exemplo de convexidade
Lema 2.1.1. A intersec¸c˜ao de uma cole¸c˜ao arbitr´aria de conjuntos convexos ´e con-
vexa.
Dem.: Se um segmento de reta est´a contido em todo conjunto da cole¸c˜ao, ent˜ao ele
estar´a contido na intersec¸c˜ao destes conjuntos.
Defini¸c˜ao 2.1.2. Dizemos que x ´e uma combina¸c˜ao convexa de x
1
, . . . , x
r
∈ R
n
se
existem λ
1
, . . . , λ
r
∈ R tais que
1. x = λ
1
x
1
+ ··· + λ
r
x
r
,
2. λ
1
+ ··· + λ
r
= 1,
3. λ
1
≥ 0, . . . , λ
r
≥ 0.
Defini¸c˜ao 2.1.3. A envolt´oria convexa de um conjunto S ⊆ R
n
, denotada por
conv(S), ´e o conjunto de todas as combina¸c˜oes convexas de um n´umero finito de
elementos de S.
conv(S) =
λ
1
x
1
+ ··· + λ
k
x
k
: {x
1
, . . . , x
k
} ⊆ S, λ
i
≥ 0,
k
i=1
λ
i
= 1
.
Uma consequˆencia da defini¸c˜ao acima ´e de que a envolt´oria convexa de qualquer
conjunto S ⊆ R
n
pode ser vista como o menor conjunto convexo contendo S, como
2 Convexidade 6
provaremos a seguir. Assim, ela pode ser constru´ıda como a intersec¸c˜ao de todos os
conjuntos convexos contendo S:
conv (S) =
S
⊆ R
d
: S ⊆ S
, S
convexo
.
Primeiro note que se S ⊂ R
n
´e convexo, ent˜ao conv(S) = S. Claramente S ⊂
conv(S). Vamos mostrar por indu¸c˜ao que S cont´em todas as combina¸c˜oes convexas
de quaisquer k pontos de S. Para k = 2 ´e satisfeito pela defini¸c˜ao de convexidade.
Suponha sem perda de generalidade que ´e satisfeito para k − 1 e que x = λ
1
x
1
+
···+λ
k
x
k
com x
1
, ··· , x
k
∈ S, λ
1
+···+λ
k
= 1 e λ
1
, . . . , λ
k
> 0. Note que podemos
supor que x = (1 − λ
k
)
k−1
i=1
λ
i
1 − λ
k
x
i
+ λ
k
x
k
e j´a que
λ
i
1 − λ
k
> 0 para i = 1, . . . k −1
e
k−1
i=1
λ
i
1 − λ
k
= 1 segue que s =
k−1
i=1
λ
i
1 − λ
k
x
i
∈ S por hip´otese de indu¸c˜ao. Portanto
x = (1 − λ
k
)s + λ
k
x
k
∈ S por convexidade. Isto prova que S = conv(S).
Consideremos agora um conjunto qualquer S ⊂ R
n
seja D(S) a inter-
sec¸c˜ao de todos os conjuntos convexos S
⊂ R
n
contendo S. J´a que S ⊂ conv(S)
e conv(S) ´e convexo, n´os temos que D(S) ⊂ conv(S). Cada conjunto convexo S
com S ⊂ S
satisfaz conv(S) ⊂ conv(S
) = S
, ent˜ao conv(S) ⊂ D(S), o que prova
a igualdade.
Observe que se K = {x
1
, . . . , x
m
} ⊆ R
n
´e finito, ent˜ao ´e f´acil ver que
sua envolt´oria convexa ´e
conv(S) =
m
i=1
λ
i
x
i
:
m
i=1
λ
i
= 1, λ
i
≥ 0
O seguinte resultado sobre gera¸c˜ao de envolt´orias convexas ´e fundamen-
tal. Mas antes vamos definir independˆencia convexa.
Defini¸c˜ao 2.1.4. Pontos x
1
, . . . , x
k
∈ R
n
s˜ao convexamente independentes se ne-
nhum deles ´e uma combina¸c˜ao convexa dos outros, isto ´e, se
k
i=1
λ
i
x
i
= 0 com λ
i
∈ R e
k
i=1
λ
i
= 0 implica que λ
1
= ··· = λ
k
= 0.
2 Convexidade 7
´
E f´acil ver que is to ´e equivalente `a independˆencia linear dos vetores
x
2
− x
1
, . . . , x
k
− x
1
.
Teorema 2.1.1 (Carath´eodory). Se A ⊂ R
n
e x ∈ conv(A), ent˜ao x ´e uma
combina¸c˜ao convexa de pontos convexamente independentes de A. Em particular, x
´e uma combina¸c˜ao convexa de no m´aximo n + 1 pontos de A.
Dem.: O ponto x ∈ conv(A) tem uma representa¸c˜ao
x =
k
i=1
λ
i
x
i
com x
i
∈ A , λ
i
> 0 ,
k
i=1
λ
i
= 1
para algum k ∈ N, e podemos assumir que k ´e minimal. Suponha que x
1
, . . . , x
k
s˜ao convexamente de pendentes. Ent˜ao existem n´umeros reais α
1
, . . . , α
k
, n˜ao todos
nulos, com
k
i=1
α
i
x
i
= 0 e
k
i=1
α
i
= 0.
Podemos escolher m tal que λ
m
/α
m
´e positivo e, com esta restri¸c˜ao, o menor
poss´ıvel(observe que todo λ
i
´e positivo e que no m´ınimo um α
i
´e positivo), ou
seja, 0 < λ
m
/α
m
≤ λ
i
/α
i
se α
i
> 0. Ent˜ao podemos representar x como
x =
k
i=1
(λ
i
−
λ
m
α
m
α
i
)x
i
com todos os coe ficientes n˜ao negativos e com no m´ınimo um deles sendo zero(quando
i = m). Isto contradiz a minimalidade de k. Ent˜ao x
1
, . . . , x
k
s˜ao convexamente
independentes, que implica k ≤ n + 1.
2.2 Hiperplanos e Fun¸c˜ao Suporte
Nesta se¸c˜ao estudaremos algumas propriedades de hiperplanos e sua
liga¸c˜ao com conjuntos convexos. A principal delas e que ser´a vista posteriormente ´e
de que poderemos representar um politopo como a intersec¸c˜ao de um n´umero finito
de semi-espa¸cos definidos por hiperplanos.
2 Convexidade 8
A dimens˜ao de um subespa¸co afim ´e a dimens˜ao do espa¸co vetorial
linear correspondente. Subespa¸cos afim de dimens˜ao 0, 1, 2, e n − 1 em R
n
s˜ao
chamados de pontos, retas, planos, e hiperplanos, respectivamente.
Proposi¸c˜ao 2.2.1. Se · denota o produto interno usual em R
n
, ent˜ao, para u ∈
R
n
\ {0} e α ∈ R fixos, H
α
(u) = {x ∈ R
n
: x, u = α} ´e um hiperplano em R
n
.
Dem.: Vamos dividir a demonstra¸c˜ao em dois casos, α = 0 e α = 0.
1. α = 0: Vamos mostrar que H
0
(u) = {x ∈ R
n
: x, u = 0} ´e um sube-
spa¸co vetorial de dimens˜ao n − 1. Come¸camos mostrando que H
0
(u) ´e
um subespa¸co vetorial de R
n
:
(a) 0, u = 0 ent˜ao 0 ∈ H
0
(u)
(b) Dados x,y ∈ H
0
(u) temos que x+y, u = x, u+y, u = 0 ent˜ao
x + y ∈ H
0
(u)
(c) Seja a ∈ R e x ∈ H
0
(u) ent˜ao ax, u = ax, u = 0, logo ax ∈
H
0
(u).
Portanto H
0
(u) ´e um subespa¸co vetorial de R
n
. Agora vamos mostrar
que dim(H
0
(u)) = n − 1. Note que
H
0
(u) = {x ∈ R
n
: x, u = 0} = (gerado(u))
⊥
e R
n
= (gerado(u)) ⊕ ((gerado(u))
⊥
), e ent˜ao temos que dim(R
n
) =
dim(gerado(u)) + dim((gerado(u))
⊥
) e como dim(gerado(u)) = 1 e
dim(R
n
) = n ent˜ao dim((gerado(u))
⊥
) = n − 1. Portanto H
0
(u) ´e um
subespa¸co vetorial de R
n
de dimens˜ao n − 1, um hiperplano em R
n
.
2. Para α = 0 vamos mostrar que H
α
(u) ´e o deslocamento de um subespa¸co
vetorial de R
n
com dimens˜ao n − 1. Consideremos
H = H
α
(u) − {e
1
} = {x − e
1
: x ∈ H
α
(u)} (2.1)
onde e
1
=
αu
u
. Note que e
1
∈ H
α
(u). Vamos mostrar que H ´e um
subespa¸co vetorial de dimens˜ao n − 1 de R
n
. Seja B = {e
1
, . . . , e
n
}
2 Convexidade 9
uma base ortogonal de R
n
. Definamos v
j
= e
j
+ e
1
para j = 2, . . . , n e
assim temos que v
j
, u = α, logo v
j
∈ H
α
(u) e assim e
j
= v
j
− e
1
∈ H
para j = 2, . . . , n. Agora mostraremos que H ´e um subespa¸co vetorial
de R
n
e que e
1
/∈ H, logo H ter´a dimens˜ao n − 1.
(a) Como e
1
∈ H
α
(u) ent˜ao 0 = e
1
− e
1
∈ H por 2.1.
(b) Dados v,w ∈ H ent˜ao por 2.1 existem x,y ∈ H
α
(u) tais que v = x−
e
1
e w = y −e
1
. Para provarmos que v + w ∈ H basta mostrarmos
que v+w+ e
1
∈ H
α
(u) e ent˜ao por 2.1 v+w+e
1
−e
1
= v+w ∈ H. E
como v +w+e
1
, u = x, u+y, u−e
1
, u = α estamos prontos.
(c) Dados a ∈ R e v ∈ H ent˜ao existe x ∈ H
α
(u) tal que v = x −e
1
e
pelo mesmo argumento anterior basta mostrarmos que av + e
1
∈
H
α
(u) para provarmos que av ∈ H. E como av + e
1
, u = ax −
ae
1
+ e
1
, u = α estamos prontos.
(d) Vamos mostrar que e
1
/∈ H. Vamos supor que e
1
∈ H, ent˜ao
2e
1
∈ H
α
(1). Mas 2e
1
, u = 2α uma contradi¸c˜ao, logo e
1
/∈ H
Portanto H tem dimens˜ao n −1 e H
α
(u) ´e o deslocamento de um subespa¸co vetorial
de R
n
com dimens˜ao n −1, logo H
α
(u) tem dimens˜ao n −1, ou seja, um hiperplano
em R
n
Dizemos que u ´e o vetor normal a H
α
(u). Ent˜ao a proposi¸c˜ao 2.2.1
caracterizou H
α
(u) como um hiperplano em R
n
com vetor normal u e deslocado
αu
u
da origem.
Defini¸c˜ao 2.2.1. Denotaremos por H
+
α
(u) = {x ∈ R
n
: x, u ≥ α} e H
−
α
(u) =
{x ∈ R
n
: x, u ≤ α}. Es ses s˜ao os semi-espa¸cos limitados por H
α
(u).
Algumas propriedades de um conjunto convexo fechado K podem ser
estudadas usando a fun¸c˜ao que associa a cada ponto do R
n
seu ponto mais pr´oximo
em K. Come¸caremos mostrando que esta fun¸c˜ao est´a bem definida.
2 Convexidade 10
Lema 2.2.1. Seja K um conjunto convexo fechado em R
n
. Ent˜ao, para cada x ∈ R
n
existe um ´unico x
∈ K tal que
x − x
= inf
y∈K
x − y (2.2)
Dem.: A existˆencia de x
satisfazendo 2.2 segue de K ser fechado e do fato da
fun¸c˜ao distˆancia · ser cont´ınua. Agora suponha que existe x
∈ K, x
= x
, tal
que
x − x
= x − x
= inf
y∈K
x − y.
Considerando o triˆangulo is´osceles com v´ertices x, x
e x
, como ilustrado na figura
2.2, podemos notar que o ponto m´edio m =
1
2
(x
− x
) do segmento de reta que une
x
e x
tamb´em pertence a K por convexidade, mas m satisfaz
x − m < x − x
= inf
y∈K
x − y
uma contradi¸c˜ao.
Figura 2.2: triˆangulo is´osceles
O lema 2.2.1 nos leva `a defini¸c˜ao da seguinte fun¸c˜ao:
Defini¸c˜ao 2.2.2. A fun¸c˜ao
p
K
: R
n
−→ K
x −→ p
K
(x) = x
,
onde x
´e o mesmo do lema 2.2.1, ´e dita fun¸c˜ao ponto mais pr´oximo relativa a K.
2 Convexidade 11
A defini¸c˜ao a seguir generaliza o conceito de hiperplano tangente que
est´a ilustrado na figura 2.3.
Defini¸c˜ao 2.2.3. Um hiperplano H ´e dito um hiperplano de suporte de um conjunto
convexo fechado K ⊆ R
n
se K ∩ H = ∅ e K ⊂ H
−
ou K ⊂ H
+
.
Figura 2.3: hiperplano de suporte
Proposi¸c˜ao 2.2.2. Seja K ⊆ R
n
fechado, convexo e n˜ao vazio. Ent˜ao, para todo
x ∈ R
n
\K, o hiperplano contendo x
= p
K
(x) e perpendicular `a linha unindo x e x
´e um hiperplano de suporte de K e pode ser descrito por H = {y ∈ R
n
: y, u = 1},
onde u =
x − x
x
, x − x
sempre que 0 /∈ H.
Dem.: Note que o hiperplano H = {y ∈ R
n
: y, u = 1} ´e perpendicular a x − x
e satisafaz x
∈ H, pois H =
y ∈ R
n
: y, x − x
= x
, x − x
. Al´em disso,
x −x
, x −x
> 0 implica x, x −x
> x
, x −x
ent˜ao x ∈ H
+
. Vamos supor que
H n˜ao ´e um hiperplano de suporte de K. Ent˜ao existe algum y ∈ K ∩ (H
+
\ H).
Vamos considerar o c´ırculo de centro x e raio
x − x
, como ilustrado na figura 2.4,
assim H ´e um hiperplano tangente ao c´ırculo no ponto x
. Deste modo o segmento de
reta
x
, y
possui um ponto z interior ao c´ırculo sendo que z ∈ K por convexidade.
Ent˜ao, x − z < x − x
, uma contradi¸c˜ao.
2 Convexidade 12
Figura 2.4: hiperplano tangente ao c´ırculo
Defini¸c˜ao 2.2.4. Seja K ⊂ R
n
um conjunto convexo n˜ao vazio. A fun¸c˜ao
h
K
: R
n
−→ R definida por
u −→ h
K
(u) = sup
x∈K
x, u
´e a fun¸c˜ao suporte de K.
A figura 2.5 ilustra a defini¸c˜ao 2.2.4.
Figura 2.5: fun¸c˜ao suporte
A pr´oxima afirma¸c˜ao ´e uma consequˆencia da defini¸c˜ao.
Lema 2.2.2. Se K + a ´e uma transla¸c˜ao do conjunto convexo K, ent˜ao,
h
K+a
(u) = h
k
(u) + a, u
para todo u ∈ R
n
.
2 Convexidade 13
Proposi¸c˜ao 2.2.3.
1. Para todo u ∈ R
n
\ {0}, o hiperplano
H
K
(u) = {x ∈ R
n
: x, u = h
K
(u)}, (2.3)
´e um hiperplano de suporte de K.
2. Se H ´e um hiperplano de suporte de K, ele tem uma representa¸c˜ao na
forma 2.3.
Dem.:
1. J´a que K ´e fechado e ·, u ´e cont´ınua, ent˜ao existe x
0
∈ K tal que
x
0
, u = h
K
(u) = sup
x∈K
x, u.
Agora dado y ∈ K, segue que y, u ≤ x
0
, u, ent˜ao K ⊂ H
−
K
(u).
2. Seja H = {x ∈ R
n
: x, u = x
0
, u} um hiperplano de suporte de
K em x
0
. Escolhemos u = 0 tal que K ⊂ H
−
. Ent˜ao, x
0
, u =
sup
x∈K
x, u = h
K
(u).
Defini¸c˜ao 2.2.5. Um cone convexo com um v´ertice v ´e definido como um conjunto
convexo S em R
n
tal que v ´e um ponto extremo de S e, para qualquer a ∈ S,
v + λ(a − v) ∈ S para todo n´umero real λ ≥ 0.
Lema 2.2.3. Seja C um cone convexo com v´ertice v e seja H um hiperplano em R
n
com v /∈ H.Suponha que Q = C ∩ H ´e n˜ao vazio e limitado. Ent˜ao, para r ∈ R
n
,
C ∩(r + H) ´e vazio ou existe um n´umero real t ≥ 0 tal que
C ∩(r + H) = v + t (Q − v) = {v + t (a − v) : a ∈ Q}
Dem.: Sejam α ∈ R
n
e β ∈ R tais que
H = {x ∈ R
n
: α, x = β}
2 Convexidade 14
e podemos assumir sem perda de generalidade que v ∈ H
+
e assim, temos que
α, v > β.
Vamos mostrar que para todo ponto a ∈ C com a = v, temos que
α, a < α, v. (2.4)
Suponhamos o contr´ario, ou seja, que existe um ponto a
0
∈ C tal que α, a
0
≥
α, v. Sej a b ∈ Q = C ∩H. Ent˜ao
α, b = β < α, v ≤ α, a
0
.
Seja a
1
= λ
1
a
0
+(1 − λ
1
) b onde λ
1
=
α, v − β
α, a
0
− β
> 0. J´a que λ
1
≤ 1 e C ´e convexo,
ent˜ao a
1
∈ C e
α, a
1
= α, v. (2.5)
Dado t ≥ 0, ent˜ao
b + t (a
1
− v) = v + (t + 1)
b
t + 1
+
ta
1
t + 1
− v
pertence a C, pois a
1
,b ∈ C e C ´e cone convexo com v´ertice v. Por 2.5 temos que
α, b+t (a
1
− v) = α, b+tα, a
1
−tα, v = α, b = β. Ent˜ao b+t (a
1
− v) ∈ H e
assim b+ t (a
1
− v) ∈ H ∩C para todo t ≥ 0, contradizendo o fato de Q ser limitado.
Portanto 2.4 ´e verdade.
Dado r ∈ R
n
e a ∈ C com a = v, considere a intersec¸c˜ao do raio
{v + λ (a − v) : λ ≥ 0} (2.6)
com o hiperplano
r + H = {r + x ∈ R
n
: α, x = β} = {x ∈ R
n
: α, x = α, r + β}. (2.7)
Ent˜ao se um ponto est´a nesta intersec¸c˜ao ele satisfaz (2.6) e (2.7). Assim α, v +
λ (a − v) = α, r + β que implica λ =
α, v − β − α, r
α, v − α, a
. J´a que α, v > α , a,
Ent˜ao λ ≥ 0 se e somente se α, v − β ≥ α, r. Quando esta condi¸c˜ao ´e satisfeita,
r +H intercepta todo raio (2.6) em um ´unico ponto determinado pelo λ acima. Para
2 Convexidade 15
r = 0 temos que α, v − β ≥ 0 = α, r e ent˜ao cada raio 2.6 intercepta H, e ent˜ao
Q, em um ´unico ponto. Logo, podemos indexar todos os raios (2.6) pelos a ∈ Q.
Agora suponha que α, r ≤ α, v−β. Ent˜ao para cada a ∈ Q, o raio 2.6 intercepta
r + H no ponto b = v + λ
0
(a − v) onde
λ
0
=
α, v − β − α, r
α, v − β
.
Seja t = λ
0
, logo, o lema est´a provado.
2.3 Soma de Minkowski
O objetivo desta se¸c˜ao ser´a o estudo de uma opera¸c˜ao fundamental
para conjuntos convexos a qual pode ser definida para conjuntos arbitr´arios em
R
n
chamada soma de Minkowski. Nosso interesse ´e estudar algumas propriedades
dessa soma, pois nos cap´ıtulos seguintes estaremos interessados na decomposi¸c˜ao de
politopos em fun¸c˜ao da soma de Minkowski.
Defini¸c˜ao 2.3.1. Sejam K, L ⊆ R
n
. A soma de Minkowski de K e L ´e o conjunto
K + L = {k + l : k ∈ K, l ∈ L}.
Uma observa¸c˜ao importante a respeito desta soma e que ser´a ´util para
o entendimento de alguns resultados diz respeito `a soma de retas e pontos. Por ex-
emplo, quando somamos um ponto e uma reta, teremos uma reta conforme ilustrado
na figura 2.6a. Por´em, note que, quando somamos duas retas, teremos uma reta se
elas forem paralelas conforme ilustardo na figura 2.6b, caso contr´ario teremos uma
figura retangular conforme ilustrado na figura 2.6c. No cap´ıtulo 4 veremos que est´a
observa¸c˜ao ´e a chave para o algoritmo de decomposi¸c˜ao de politopos em R
2
, ou seja,
pol´ıgonos.
2 Convexidade 16
Figura 2.6: soma de retas
A soma de Minkowski de dois triˆangulos K, L no plano pode ser um triˆangulo(figura
2.7a), um retˆangulo(figura 2.7b), um pe nt´agono(figura 2.7c), ou um hex´agono(figura
2.7d).
Lema 2.3.1.
1. Se τ denota uma transla¸c˜ao, ent˜ao, para quaisquer conjuntos K, L em
R
n
,
τ (K) + L = τ (K + L) = K + τ (L) .
2. Se K, L s˜ao ambos conjuntos convexos, fechados, limitados, ent˜ao, K +
L ´e um conjunto convexo, fechado, limitado, respectivamente.
2 Convexidade 17
Figura 2.7: somando politopos
Dem.:
1. τ ´e dado por um vetor de transla¸c˜ao t. Logo a afirma¸c˜ao segue de
(t + K) + L = t + (K + L) = K + (t + L)
2. Sejam x, x
∈ K e y, y
∈ L. Ent˜ao, para 0 ≤ λ ≤ 1,
λ (x + y)+(1 − λ)
x
+ y
= λx+(1 − λ) x
+λy+(1 − λ) y
∈ K +L,
se K e L s˜ao convexos. As propriedades fechado e limitado seguem de
K e L para K + L j´a que soma ´e uma opera¸c˜ao cont´ınua e leva pares
de conjuntos limitados para um conjunto limitado.
2 Convexidade 18
A maioria das considera¸c˜oes sobre soma de Minkowski s˜ao invariantes
sob transla¸c˜oes, devido ao lema 2.3.1. Podemos visualizar a soma de K + L fixando
L e movˆe-lo por transla¸c˜ao por todos os pontos p tal que p esteja em K. Ent˜ao a
transla¸c˜ao de L cobre K + L, que ´e, K + L =
p∈K
(p + L).
Defini¸c˜ao 2.3.2. Se λ ´e um n´umero real e K ⊂ R
n
´e um conjunto, ent˜ao, dizemos
que λK = {λx : x ∈ K} ´e um m´ultiplo de K. Se λ
1
, . . . , λ
r
∈ R e K
1
, . . . , K
r
s˜ao conjuntos em R
n
, dizemos que λ
1
K
1
+ ··· + λ
r
K
r
´e uma combina¸c˜ao linear de
K
1
, . . . , K
r
.
Observamos que λ pode ser negativo. Entretanto, (−1) K = −K n˜ao ´e
o negativo de K com respeito a soma de Minkowski. Na figura 2.7d, L = −K, mas
K + L = K + (−K) ´e um hex´agono.
Da defini¸c˜ao de combina¸c˜ao linear e do lema anterior, temos o seguinte:
Lema 2.3.2. Se K
1
, . . . , K
r
s˜ao convexos e λ
1
, . . . , λ
r
s˜ao n´umeros reais quaisquer,
ent˜ao, λ
1
K
1
+ ··· + λ
r
K
r
´e convexo.
2.3.1 Subtra¸c˜ao de Minkowski
Como j´a estudamos algumas propriedades de soma de Minkowski, agora
podemos introduzir uma opera¸c˜ao complementar chamada subtra¸c˜ao de Minkowski.
Enquanto a soma de Minkowski de dois conjuntos A, B ⊂ R
n
pode ser definida por
A + B =
b∈B
(A + b),
a diferen¸ca de Minkowski de A e B pode ser definida da se guinte maneira
Defini¸c˜ao 2.3.3. A ∼ B =
b∈B
(A − b)
Se B ´e vazio, A ∼ B ´e, por conven¸c˜ao, igual a R
n
. Tamb´em podemos
escrever
A ∼ B = {x ∈ R
n
: B + x ⊂ A},
2 Convexidade 19
ou seja, s˜ao todos os deslocamentos do conjunto B que o levam a estar contido no
conjunto A.
Exemplo 2.3.1. Considere o retˆangulo A = conv((0, 0), (2, 0), (2, 1), (0, 1)) e o seg-
mento de reta B = conv((0, 0), (1, 0)) como ilustrados na figura 2.8. Note que
A ∼ B = conv((0, 0), (1, 0), (1, 1), (0, 1)), ou seja, se somarmos B a qualquer ele-
mento x do conjunto A ∼ B ent˜ao x + B ⊂ A.
Figura 2.8: subtra¸c˜ao de Minkowski
Existem algumas propriedades simples ligando soma e subtra¸c˜ao de
Minkowski
(A + B) ∼ B ⊃ A (2.8)
(A ∼ B) + B ⊂ A, (B = ∅) (2.9)
(A ∼ B) + C ⊂ (A + C) ∼ B (2.10)
(A ∼ B) ∼ C = A ∼ (B + C) (2.11)
A + B ⊂ C ⇔ A ⊂ C ∼ B (2.12)
As verifica¸c˜oes s˜ao imediatas das defini¸c˜oes. Se trabalharmos com conjuntos con-
vexos, um pouco mais ´e verdade. Como, por exemplo, se A ´e convexo, ent˜ao A ∼ B
´e uma intersec¸c˜ao de conjuntos convexos e ent˜ao convexo.
Defini¸c˜ao 2.3.4. Para conjuntos convexos K,L ∈ R
n
dizemos que L ´e um fator de
K se existe um conjunto convexo M tal que K = M + L.
2 Convexidade 20
Lema 2.3.3. Sejam K,L ∈ R
n
conjuntos convexos. Ent˜ao (K + L) ∼ L = K. A
rela¸c˜ao (K ∼ L) + L = K ´e satisfeita se, e somente se, L ´e um fator de K.
Dem.: Seja x ∈ (K+L) ∼ L, ent˜ao L+x ⊂ K+L e, al´em disso, h
L
+h
{x}
≤ h
K
+h
L
.
Subtraindo h
L
, obtemos x ∈ K. Ent˜ao (K +L) ∼ L ⊂ K, que junto com 2.8 prova a
primeira afirma¸c˜ao. Se (K ∼ L)+L = K, ent˜ao L ´e um fator de K. Reciprocamente,
suponha que K = M + L para algum M ∈ R
n
. Ent˜ao K ∼ L = (M + L) ∼ L = M,
que prova a segunda afirma¸c˜ao
2.4 Politopos
Nesta se¸c˜ao estudaremos algumas propriedades de politopos, pois como
ser´a visto no cap´ıtulo 3, a cada polinˆomio associaremos uma figura geom´etrica que
ser´a um politopo. Assim, informa¸c˜oes a respeito de politopos nos levar˜ao a in-
forma¸c˜oes sobre polinˆomios.
Defini¸c˜ao 2.4.1. Se S ´e um conjunto finito, ent˜ao conv(S) ´e denominado politopo
de S.
Se S = ((0, 0), (1, 2), (2, 2), (3, 2), (2, 4), (4, 2)). Ent˜ao conv(S) ´e um
politopo, conforme ilustrado na figura 2.9.
Figura 2.9: Politopo
Defini¸c˜ao 2.4.2. Um ponto de um politopo ´e dito um v´ertice(ou um ponto extremo)
se ele n˜ao est´a no segmento de reta que liga quaisquer outros dois pontos do politopo.
2 Convexidade 21
Note que o ponto v = (4, 2) ´e um v´ertice do politopo conv(S), como pode ser
observado na figura 2.9.
Se P = conv {x
1
, . . . , x
k
}, ent˜ao claramente os pontos extremos de P
est˜ao entre x
1
, . . . , x
k
. Se H ´e um hiperplano de suporte de P , ent˜ao
H ∩ P = conv(H ∩ {x
1
, . . . , x
k
}),
que nos leva a definir uma face de um politopo.
Defini¸c˜ao 2.4.3. Se H ´e um hiperplano de suporte de um conjunto convexo fechado
P , chamamos F = P ∩ H uma face de P .
Ent˜ao cada face de um politopo ´e tamb´em um politopo. Como j´a foi
definido os pontos extremos de um politopo s˜ao ditos seus v´ertices. O conjunto
de v´ertices de P ´e tamb´em denotado por vert(P ). A defini¸c˜ao a seguir ajuda a
caracterizar o politopo.
Defini¸c˜ao 2.4.4. Dado um politopo P em R
n
. Diremos que F :
1. ´e v´ertice de P , se F ´e face de dimens˜ao 0.
2. ´e aresta de P , se F ´e face de dimens˜ao 1.
3. ´e faceta P , se F ´e face de dimens˜ao k − 1.
Os ´ıtens 1 e 2 do teorema a seguir dizem respeito a qualquer con-
junto convexo. Por´em preferimos apresent´a-los apenas agora e explicarmos sua
importˆancia para politopos.
Teorema 2.4.1. Sejam K e L conjuntos convexos. Ent˜ao,
1. Se h
K
, h
L
s˜ao as fun¸c˜oes suporte de K e L, ent˜ao h
K
+ h
L
´e a fun¸c˜ao
suporte de K + L,
h
K+L
= h
K
+ h
L
.
2 Convexidade 22
2. Se F ´e uma face de K + L, ent˜ao existem ´unicas faces F
K
, F
L
de K e
L, respectivamente, tais que F = F
K
+ F
L
.
Em particular, para cada v´ertice v de K + L existem ´unicos v´ertices v
1
e v
2
de K e L, respectivamente, tais que v = v
1
+ v
2
.
3. Se K, L s˜ao politopos, ent˜ao K + L ´e um politopo.
Dem.:
1. Seja u ∈ R
n
\ {0}, ent˜ao h
K+L
(u) =sup
x∈K+L
x, u =sup
y∈K,z∈L
y +
z, u =sup
y∈K
y, u+sup
z∈L
z, u = h
K
(u) + h
L
(u) .
2. Como F ´e uma face de K + L ent˜ao existe um hiperplano de suporte H
tal que F = (K +L)∩H e por 2.2.3 H tem uma representa¸c˜ao na forma
H
K+L
(u) = {x ∈ R
n
: x, u = h
k+l
(u)} para um c erto u ∈ R
n
\ {0}.
Definamos F
K
= K ∩ H
K
(u) e F
L
= L ∩ H
L
(u), onde H
K
(u) = {x ∈
R
n
: x, u = h
k
(u)} e H
L
(u) = {x ∈ R
n
: x, u = h
l
(u)}. Note
que H
K+L
= H
K
+ H
L
, pois dados x ∈ H
K
e y ∈ H
L
temos que
x + y, u = x, u + y, u = h
K
+ h
L
= h
K+L
. Logo, x + y ∈ H
K+L
e como H
K
, H
L
e H
K+L
s˜ao hiperplanos paralelos, temos a igualdade.
Segue que
F = (K + L) ∩ H
K+L
(u) = (K + L) ∩ (H
K
(u) + H
L
(u))
= (K ∩ H
K
(u)) + (L ∩ H
L
(u)) = F
K
+ F
L
.
Onde a igualdade acima ´e satisfeita pois dado z ∈ (K + L) ∩ H
K+L
temos que z = x + y = x
1
+ y
1
com x ∈ K, y ∈ L, x
1
∈ H
K
e y
1
∈ H
L
.
Queremos mostrar que x ∈ H
k
e y ∈ H
L
. Como x ∈ K ⊂ H
−
K
ent˜ao
x, u ≤ h
K
= x
1
, u e do mesmo modo y, u ≤ h
L
= y
1
, u. Temos
que z, u = h
K+L
, ou se ja, x, u + y, u= x
1
, u + y
1
, u. Ent˜ao
x, u = h
K
e y, u = h
L
e a igualdade ´e s atisfeita.
3. ´e uma consequˆencia do ´ıtem 2 , j´a que a soma de dois v´ertices ´e um
v´ertice e cada v´ertice de K + L ´e obtido deste modo.
2 Convexidade 23
A prova da unicidade dos primeiros dois ´ıtens ser´a feita no cap´ıtulo seguinte.
O ´ıtem 2 do teorema acima ´e muito importante pois nos diz que um
fator de uma face possui o mesmo vetor normal que a face. Isto fica evidente no
corol´ario a seguir quando tratamos especificamente de pol´ıgonos.
O corol´ario a seguir nos leva a enxergar como decompor as arestas de
um pol´ıgono.
Corol´ario 2.4.1. Sejam P, Q e R pol´ıgonos convexos em R
n
com P = Q+R. Ent˜ao
toda aresta de P decomp˜oe-se unicamente como a soma de uma aresta de Q e uma
aresta de R, possivelmente uma delas sendo um ponto.
Como j´a foi observado na se¸c˜ao 2.3 toda aresta de P decomp˜oe-se como
a soma de duas arestas paralelas a ela ou como a soma de uma aresta e um ponto.
A importˆancia deste resultado fic ar´a evidente no cap´ıtulo 4 da presente disserta¸c˜ao,
quando estivermos buscando fatores de um pol´ıgono.
Teorema 2.4.2. Todo politopo possui um n´umero finito de faces, que tamb´em s˜ao
politopos.
Dem.: Seja o politopo P = conv (x
1
, . . . , x
n
), e F = P ∩ H uma face de P onde
H = {x ∈ R
n
: x, a = α} ´e um hiperplano de suporte de P tal que P ⊂ H
−
.
Podemos assumir que x
1
, . . . , x
s
∈ H e x
s+1
, . . . , x
n
∈ H
−
\ H e assim:
x
i
, a = α para i = 1, . . . , s
x
i
, a = α − β
i
, β
i
> 0 para i = s + 1, . . . , n.
Seja x ∈ P , logo, x =
n
i=1
λ
i
x
i
,
n
i=1
λ
i
= 1, λ
i
≥ 0, i = 1, . . . , n . Assim x, a =
n
i=1
λ
i
x
i
, a =
n
i=1
λ
i
x
i
, a =
s
i=1
λ
i
α+
n
i=s+1
λ
i
(α − β
i
) =α
n
i=1
λ
i
−
n
i=s+1
λ
i
β
i
= α−
n
i=s+1
λ
i
β
i
. Portanto
x ∈ H ⇔
n
i=s+1
λ
i
β
i
= 0 ⇔
n
s+1
λ
i
= 0
2 Convexidade 24
assim x ´e uma combina¸c˜ao convexa de x
1
, . . . , x
s
ent˜ao H∩P = conv (x
1
, . . . , x
s
).
O teorema a seguir mostra que para politopos a distin¸c˜ao entre faces ´e
desnecess´aria.
Teorema 2.4.3. Seja P ⊂ R
n
um politopo, F
1
uma face de P e F uma face de F
1
.
Ent˜ao F ´e uma face de P .
Dem.: Podemos assumir que 0 ∈ F . Ent˜ao existe um hip erplano de suporte H
u,0
para P tal que H
u,0
∩P = F
1
e P ⊂ H
−
u,0
. Em H
u,0
existe um hiperplano de suporte
H para F
1
tal que H ∩ F
1
= F , diremos
H = {x ∈ H
u,0
: x, v = 0},
F
1
⊂ {x ∈ H
u,0
: x, v ≤ 0}.
Definimos
η
0
:= max {−x, v/x, u : x ∈ ext(P ) \ ext(F
1
)} e
H(η) := H
ηu+v,0
com η > η
0
. Temos que x, u < 0 para x ∈ ext(P ) \ext(F
1
), ent˜ao
x, ηu + v < η
0
x, u + x, v ≤ 0
pela defini¸c˜ao de η
0
. Para x ∈ ext(F
1
) \ ext(F ) obtemos
x, η + v = x, v < 0,
e para x ∈ ext(F ), x, ηu + v = 0. Ent˜ao ext(F ) ⊂ H(η), enquanto ext(P ) \
ext(F ) ⊂ intH
−
ηu+v,0
. Vemos que H(η) ´e um hiperplano de suporte para P com
H(η) ∩ P = F e al´em disso F ´e uma face de P .
Um politopo foi definido como a envolt´oria convexa de um conjunto
finito de pontos. Alternativamente podemos represent´a-lo como a intersec¸c˜ao de um
n´umero finito de semi espa¸cos. Antes vamos denotar, para um politopo P , int(P )
como seu interior e bd(P ) como sua fronteira.
Teorema 2.4.4. Todo politopo ´e a intersec¸c˜ao de um conjunto finito de semi espa¸cos
limitados por hiperplanos.
2 Convexidade 25
Dem.: Seja P ⊂ R
n
um politopo. Podemos assumir que dim(P ) = n. Sejam
F
1
, . . . , F
k
as facetas de P (dim(F
i
) = n − 1). Ent˜ao F
i
= H
i
∩ P onde H
i
´e um
hiperplano de suporte ´unico de P . Seja H
−
i
o semi espa¸co limitado por H
i
e contendo
P para i = 1, . . . , k. Afirmamos que
P = H
−
1
∩ . . . ∩ H
−
k
. (2.13)
A inclus˜ao P ⊂ H
−
1
∩ . . . ∩ H
−
k
´e trivial. Seja x ∈ R
n
\ P . Seja A a uni˜ao de
envolt´orias convexas de x e quaisquer n − 1 v´ertices de P . Podemos escolher um
ponto y ∈ (int(P )) \A. Existe um ponto z ∈ bd(P ) ∩[x, y], o qual pertence a algum
hiperplano de suporte de P e assim a alguma face F de P . Vamos supor por absurdo
que dim(F ) = j ≤ n − 2 . Pelo teorema 2.1.1, z pertence `a envolt´oria convexa de
j + 1 ≤ n − 1 v´ertices de P e assim a A. Mas ent˜ao y ∈ A, uma contradi¸c˜ao.
Isto mostra que F ´e uma faceta, e assim F = F
i
para algum i ∈ {1, . . . , k}. De
y ∈ int(P ) ⊂ int(H
−
i
) deduzimos que x /∈ H
−
i
. Isto prova 2.13.
Teorema 2.4.5 (Krein-Milman). Todo politopo P ´e a envolt´oria convexa de seus
v´ertices, isto ´e,
P = conv (vert(P )) .
Dem.: Como vert(P ) ⊂ P ent˜ao conv (vert(P )) ⊂ conv(P ) = P . Para a outra
inclus˜ao podemos assumir que P = conv (x
1
, . . . , x
n
) e considerar os elementos x
i
tais que x
i
/∈ P
i
= conv (x
1
, . . . , x
i−1
, x
i+1
, . . . , x
n
) para 1 ≤ i ≤ n (a id´eia ´e mostrar
que cada um desses x
i
’s ´e um v´ertice de P ). Seja q
i
= p
p
i
(x
i
) a imagem de x
i
sob a
fun¸c˜ao ponto mais pr´oximo. Por 2.2.2 o hiperplano passando por q
i
e perpendicular a
x
i
−q
i
´e um hiperplano de suporte H
i
para P
i
. Mostraremos que H
i
= H
i
+{x
i
− q
i
}´e
um hiperplano de suporte para P tal que H
i
∩P = {x
i
}, isto ´e, uma face de dimens˜ao
zero, portanto, um v´ertice de P .(Observe a figura 2.10)
1. Primeiramente vamos mostrar que H
i
´e um hiperplano de suporte para
P em x
i
. Temos que x
i
∈ H
i
, pois x
i
= q
i
+ x
i
− q
i
e q
i
∈ H
i
.
H
i
e H
i
possuem o mesmo vetor normal x
i
− q
i
que denotaremos por
u. Deste modo podemos definir H
i
= {x ∈ R
n
: x, u = q
i
, u} e
2 Convexidade 26
Figura 2.10: hiperplano deslocado
H
i
= {x ∈ R
n
: x, u = x
i
, u}. Vamos mostrar que P ⊂ (H
i
)
−
.
Para isso podemos supor que P
i
⊂ H
i
, ou seja, dado z ∈ P
i
segue
que z, u ≤ q
i
, u. Seja x ∈ P , ent˜ao x = λx
i
+ (1 − λ)z pois P =
conv({x
i
} ∪ P
i
). Precisamos mostrar que x, u ≤ x
i
, u. Temos que
x, u = λx
i
, u + (1 − λ)z, u
≤ λx
i
, u + (1 − λ)q
i
, u
= x
i
, u − (1 − λ)x
i
− q
i
, u
e como x
i
∈ H
+
i
segue que x
i
, u ≥ q
i
, u e assim x
i
−q
i
, u ≥ 0. Isto
nos leva a x, u ≥ x
i
, u,isto ´e, P ⊂ (H
i
)
−
.
2. Agora vamos mostrar que H
i
∩ P = {x
i
}. Suponha, por absurdo, que
exista y ∈ H
i
∩ P tal que y = x
i
, mas H
i
∩ P ´e uma face de P ent˜ao
ter´ıamos x
j
= x
i
tal que x
j
∈ H
i
∩ P pois todas as faces de P s˜ao
geradas por subconjuntos de {x
1
, . . . , x
n
}, onde x
j
∈ P
i
. Temos que
x
j
, u ≤ q
i
, u pois P
i
⊂ H
−
i
e assim x
j
, u < q
i
, u + x
i
− q
i
que
nos leva a x
j
, u < x
i
, u = x
j
, u,absurdo. Portanto H
i
∩ P = {x
i
}
Concluimos que x
i
´e um v´ertice de P . Isto implica que P ⊆ conv(vert(P ))
Note que, como consequˆencia do teorema de Krein-Milman, quando
estivermos interessados na soma de Minkowski de politopos, podemos apenas somar
os v´ertices dos p olitopos, ou seja,
K + L = conv (vert (K) + vert (L)) .
2 Convexidade 27
Como est´a ilustrado na figura 2.7. Com o teorema 2.4.5 em m˜aos tamb´em podemos
observar que se x
1
, . . . , x
k
s˜ao os v´ertices do politopo P e F ´e uma face de P, ent˜ao
existe um hiperplano H tal que
F = H ∩ P = con v(H ∩ {x
1
, . . . , x
k
}).
Portanto, cada face de P ´e a e nvolt´oria convexa de um subconjunto dos v´ertices de
P .
Agora que estudamos algumas propriedades de politopos, vamos asso-
ciar os polinˆomios `as suas resp e ctivas figuras geom´etricas. Nos cap´ıtulos seguintes
da disserta¸c˜ao estudaremos propriedades geom´etricas dos politopos que levar˜ao a
propriedades alg´ebricas como fatora¸c˜ao e irredutibilidade dos seus polinˆomios asso-
ciados.
28
3 FAM
´
ILIAS IRREDUT
´
IVEIS
Neste cap´ıtulo associaremos a cada polinˆomio multivariado um poli-
topo, dito seu politopo de Newton. Apresentaremos o crit´erio de Gao que diz que
um polinˆomio ´e absolutamente irredut´ıvel se seu politopo de Newton associado ´e
integralmente indecompon´ıvel. Veremos alguns crit´erios para indecomponibilidade
de politopos que levam a crit´erios para irredutibilidade de polinˆomios. Observare-
mos que os polinˆomios que satisfazem esses crit´erios poder˜ao ter seus coeficientes
alterados ou serem acrescentados novos termos a eles e ainda assim permanecer˜ao
absolutamente irredut´ıveis.
3.1 Introdu¸c˜ao
Neste cap´ıtulo associaremos a cada polinˆomio f ∈ F[x
1
, . . . , x
n
] um
politopo chamado politopo de Newton da f . Apresentaremos o crit´erio de irre-
dutibilidade de Gao que diz que um polinˆomio ´e absolutamente irredut´ıvel se seu
politopo de Newton associado ´e integralmente indecompon´ıvel em rela¸c˜ao `a soma
de Minkowski.
Na se¸c˜ao 3.3 apresentaremos as constru¸c˜oes feitas por Gao em [4] de
politopos integralmente indecompon´ıveis e, como veremos, um ´unico politopo poder´a
representar in´umeros polinˆomios pois poderemos mudar os coeficientes dos termos
de f ou acrescentar novos termos desde que o politopo de Newton associado n˜ao
seja alterado. Isto levar´a a fam´ılias de polinˆomios absolutamente irredut´ıveis.
Na se¸c˜ao 3.4 apresentaremos constru¸c˜oes de politopos integralmente
indecompon´ıveis baseadas em proje¸c˜oes. Por exemplo, se tivermos um quadrado e
fizermos a proje¸c ˜ao sobre um de seus lados e esta for indecompon´ıvel, ent˜ao espera-se
que o quadrado tamb´em o seja.
3 Fam´ılias Irredut´ıveis 29
3.2 Crit´erio de Irredutibilidade
Polinˆomios multivariados necessitam de algumas defini¸c˜oes espec´ıficas
como por exemplo a respeito de seu grau, enquanto a defini¸c˜ao de irredutibilidade
usada para polinˆomios univariados ´e a mesma para multivariados.
Defini¸c˜ao 3.2.1. Consideremos um polinˆomio f(x
1
, . . . , x
n
) =
f
i
1
i
2
...i
n
X
i
1
1
. . . X
i
n
n
∈
F[X
1
, . . . , X
n
] com (i
1
, . . . , i
n
) ∈ N
n
, onde F ´e um corpo qualquer.
1. Para um termo t = X
i
1
1
. . . X
i
n
n
de f , chamado monˆomio, o n´umero
grau(t) = i
1
+ ··· + i
n
´e dito o grau de t.
2. Para cada termo de f com f
i
1
i
2
...i
n
= 0, o correspondente expoente
vetorial (i
1
, . . . , i
n
), visto em R
n
, ´e dito um vetor suporte de f.
3. Supp(f) ser´a o conjunto de todos os vetores suporte de f, isto ´e,
Supp(f) = {(i
1
, . . . , i
n
) : f
i
1
i
2
...i
n
= 0}.
Note que Supp(f) ´e vazio se f = 0.
4. Se f = 0, diremos que o grau da f ´e o maior grau entre os seus termos,
isto ´e
grau(f) = max{grau(t) : t ´e um termo de f }.
Tamb´em podemos dizer que o grau(f) ´e o grau total da f .
O exemplo a seguir ilustra a defini¸c˜ao dada.
Exemplo 3.2.1. Seja f(x
1
, x
2
, x
3
) := x
11
1
x
7
2
x
3
−
8
13
x
9
1
x
3
2
x
3
3
− x
5
1
x
5
2
x
3
− 7x
3
1
x
5
2
x
3
−
3
7
x
1
x
5
2
x
3
+ x
4
1
x
2
+ 5x
2
2
x
3
3
∈ Q[x
1
, x
2
, x
3
] ent˜ao a sequˆencia de seus graus ´e 19, 15, 11,
9, 7, 5, 5 e assim grau(f) = 19 que ´e o grau m´aximo entre os seus termos. De acordo
com a defini¸c˜ao Supp(f) = {(11, 7, 1), (9, 3, 3), (5, 5, 1), (3, 5, 1), (1, 5, 1), (4, 1, 0), (0, 2, 3)}.
Defini¸c˜ao 3.2.2. Um polinˆomio f ∈ F[x
1
, . . . , x
n
], F corpo, ´e dito redut´ıvel se este
´e um produto de dois polinˆomios f = g · h, g,h ∈ F[x
1
, . . . , x
n
] com f e g n˜ao
constantes. Caso contr´ario ele ´e dito irredut´ıvel.
3 Fam´ılias Irredut´ıveis 30
Exemplo 3.2.2.
1. Todos polinˆomios univariados de grau 0 ou 1 s˜ao irredut´ıveis. J´a que
eles certamente n˜ao podem ser expressos como um produto de polinˆomios
de grau menor.
2. O polinˆomio x
2
− 2 ´e irredut´ıvel sobre Q[x]. Para mostrarmos isto
supomos uma contradi¸c˜ao. Vamos supor que ele ´e redut´ıvel. Ent˜ao
x
2
− 2 = (ax + b)(cx + d)
onde a,b,c,d ∈ Q. Dividindo se necess´ario podemos assumir que a =
c = 1. Ent˜ao b + d = 0 e bd = −2, logo b
2
= 2. Mas nenhum n´umero
racional tem seu quadrado igual a 2. Portanto x
2
−2 ´e irredut´ıvel sobre
o corpo dos n´umeros racionais.
3. Entretanto, x
2
− 2 ´e redut´ıvel sobre os racionais adjun¸c˜ao com
√
2,
Q(
√
2), pois
x
2
− 2 = (x −
√
2)(x +
√
2).
4. O mesmo vale para polinˆomios multivariados.O polinˆomio multivariado
x
2
1
− 2x
2
2
´e irredut´ıvel sobre o corpo dos n´umeros racionais, mas ele
torna-se redut´ıvel sobre Q(
√
2), pois
x
2
1
− 2x
2
2
= (x
1
−
√
2x
2
)(x
1
+
√
2x
2
).
Isto mostra que um polinˆomio f ∈ F irredut´ıvel pode tornar-se redut´ıvel
sobre uma extens˜ao alg´ebrica de F.
Defini¸c˜ao 3.2.3. Um polinˆomio multivariado sobre um corpo F ´e dito absolutamente
irredut´ıvel se ele permanece irredut´ıvel sobre toda extens˜ao alg´ebrica de F.
Agora p odemos definir a figura geom´etrica associada a um polinˆomio
f, a qual veremos ser´a um politopo.
3 Fam´ılias Irredut´ıveis 31
Defini¸c˜ao 3.2.4. O politopo de Newton associado ao polinˆomio f(x
1
, . . . , x
n
) ´e a
envolt´oria convexa do conjunto Supp(f) = {(i
1
, . . . , i
n
) ∈ N
n
: f
i
1
,...,i
n
= 0}, que
denotaremos por P
f
.
Exemplo 3.2.3. Seja f = x
4
y
2
(4,2)
+3 x
2
y
4
(2,4)
+ x
2
y
2
(2,2)
+ 10
(0,0)
∈ R[x, y]. Ent˜ao
Supp(f) = {(4, 2) , (2, 4) , (2, 2) , (0, 0)}
e assim
P
f
= conv(Supp(f)) = conv {(4, 2) , (2, 4) , (2, 2) , (0, 0)}.
Como ilustrado na figura 3.1
Figura 3.1: Politopo de Newton associado ao polinˆomio bivariado f
Note que o polinˆomio
5 x
4
y
2
(4,2)
+7 x
2
y
4
(2,4)
+20 x
2
y
2
(2,2)
+ 17
(0,0)
possui o mesmo politopo de Newton associado que o polinˆomio f do exemplo 3.2.3,
ou seja, podemos mudar arbitrariamente os coeficientes dos termos de f desde que
os coeficientes dos termos cujos expoentes vetoriais, que correspondem aos v´ertices
do politopo, permane¸cam n˜ao nulos e deste modo o politopo permanece o mesmo.
Observe tamb´em que o polinˆomio
f = 5 x
4
y
2
(4,2)
+3 x
2
y
4
(2,4)
+7 x
2
y
3
(2,3)
+20 x
2
y
2
(2,2)
+ xy
2
(1,2)
+ 17
(0,0)
3 Fam´ılias Irredut´ıveis 32
possui o mesmo politopo de Newton associado que o polinˆomio do exemplo 3.2.3,
ou seja, podemos acrescentar monˆomios a f desde que os expoentes vetoriais que
correspondem a estes termos estejam no interior do politopo.
O lema seguinte ´e devido a Ostrowski [16] e data de 1921.
Lema 3.2.1. Sejam f, g, h ∈ F [x
1
, . . . , x
n
] tais que f = gh. Ent˜ao P
f
= P
g
+ P
h
.
Dem.: Come¸camos mostrando que P
f
⊆ P
g
+ P
h
. Para tal observe que Supp(f) ⊆
Supp(g) + Supp(h) e assim P
f
= conv(Supp(f)) ⊆ conv(Supp(g) + Supp(h)) ⊆
conv(Supp(g)) + conv(Supp(h)) = P
g
+ P
h
.
Para mostrar que P
g
+ P
h
⊆ P
f
precisamos observar que de acordo
com o teorema 2.4.1 P
g
+ P
h
´e um politopo e pelo teorema de Krein-Milman cada
politopo ´e a envolt´oria convexa dos seus v´ertices. Ent˜ao para provarmos a inclus˜ao
precisamos mostrar que para cada v´ertice v de P
g
+ P
h
existem ´unicos v´ertices v
1
e
v
2
de P
g
e P
h
, respectivamente, tais que v = v
1
+ v
2
e assim poderemos concluir que
existe um ´unico termo na expans˜ao de g ·h que tem v como seu expoente vetorial(ou
seja, n˜ao tem como este termo se anular na expans˜ao g ·h). Logo v ∈ P
f
. De acordo
com o teorema 2.4.1, cada v´ertice v de P
g
+ P
h
vem da soma de um v´ertice v
1
de P
g
e um v´ertive v
2
de P
h
. Suponha que exista um outro par tal que v
1
∈ P
g
e v
2
∈ P
h
v = v
1
+ v
2
= v
1
+ v
2
. (3.1)
Ent˜ao
v =
1
2
(v
1
+ v
2
) +
1
2
(v
1
+ v
2
).
Observe que v
1
+ v
2
,v
1
+ v
2
∈ P
g
+ P
h
e como v ´e um v´ertice de P
g
+ P
h
, temos que
v n˜ao pode estar no segmento de reta que une quaisquer outros pontos do politopo.
Isso nos leva a
v
1
+ v
2
= v
1
+ v
2
. (3.2)
Subtraindo 3.2 de 3.1 temos que
v
2
− v
2
= v
2
− v
2
, isto ´e, 2(v
2
− v
2
) = 0.
3 Fam´ılias Irredut´ıveis 33
Segue que v
2
= v
2
e v
1
= v
1
.
Mostramos que todos os v´ertices de P
g
+ P
h
est˜ao em P
f
. Como dito
antes, isto mostra que P
g
+ P
h
⊆ P
f
pelo 2.4.5.
Acabamos de mostrar que para cada v´ertice v de P
g
+P
h
existem ´unicos
v´ertices v
1
e v
2
de P
g
e P
h
, respectivamente, tais que v = v
1
+ v
2
. Sabemos que cada
face F do politopo P
f
vem da soma de uma face F
1
de P
g
e uma face F
2
de P
h
e
como toda face de P
f
´e a envolt´oria convexa de um subconjunto dos v´ertices de P
f
podemos garantir a unicidade das faces F
1
e F
2
. Assim a prova do teorema 2.4.1
est´a completa.
Exemplo 3.2.4. Seja f =
g
(1 + x + xy)
h
xy + x
2
y
2
∈ R[x, y]. Ent˜ao
P
g
= conv{(0, 0), (1, 0), (1, 1)} e P
h
= {(1, 1), (2, 2)}, logo
P
f
= P
g
+ P
h
= conv{(1, 3), (2, 2), (1, 2), (0, 2), (3, 1), (2, 1), (1, 1), (2, 0)}.
Conforme ilustrado na figura 3.2.
Figura 3.2: lema de Ostrowski
Defini¸c˜ao 3.2.5. Um ponto em R
n
´e dito integral se suas coordenadas s˜ao inteiras.
Defini¸c˜ao 3.2.6. Um politopo em R
n
´e dito integral se todos seus v´ertices s˜ao
integrais.
Defini¸c˜ao 3.2.7. Um politopo integral C ´e dito integralmente decompon´ıvel se exis-
tirem politopos integrais A e B tais que C = A + B onde ambos A e B possuem no
m´ınimo dois pontos cada. Caso contr´ario, C ´e dito integralmente indecompon´ıvel.
3 Fam´ılias Irredut´ıveis 34
Note que o conceito de indecomponibilidade usado aqui ´e diferente do
que ´e usado nos livros [11, 20].
Motivado pelo lema 3.2.1, Gao em [4] fez a seguinte observa¸c˜ao.
Corol´ario 3.2.1 (Crit´erio de Irredutibilidade). Seja F um corpo e f ∈ F [X
1
, . . . , X
n
]
um polinˆomio n˜ao nulo, n˜ao divis´ıvel por nenhum X
i
. Se o politopo de Newton de
f ´e integralmente indecompon´ıvel ent˜ao f ´e absolutamente irredut´ıvel sobre F.
Dem.: f n˜ao possui fatores com apenas um termo. Suponha f = gh onde g, h
possuem dois termos n˜ao nulos no m´ınimo. Ent˜ao os politopos de Newton de g e h
possuem dois p ontos ou mais cada e pelo lema 3.2.1 P
f
= P
g
+ P
h
, contradizendo
nossa hip´otese de P
f
ser indecompon´ıvel.
´
E importante notar que quando o Newt (f) ´e integralmente decom-
pon´ıvel, ent˜ao f pode ser redut´ıvel ou irredut´ıvel. Por exemplo, se f = 1 + y + xy +
x
2
+ y
2
, ent˜ao o N ewt (f) ´e decomposto como a soma do triˆangulo de v´ertices (0, 0),
(1, 0) e (0, 1) com ele mesmo. Por´em f ´e absolutamente irredut´ıvel sob qualquer
corpo de caracter´ıstica diferente de 2. Sob um corpo de caracter´ıstica 2 temos que
f = (1 + x + wy)
1 + x + w
2
y
,
onde w ´e um elemento de ordem 3.
Se o politopo de Newton da f ´e indecompon´ıvel ent˜ao f ´e absolutamente
irredut´ıvel e permanecer´a absolutamente irredut´ıvel se mudarmos os coeficientes dos
seus termos ou acrescentarmos termos cujos expoentes vetoriais correspondam a
pontos que perten¸cam ao politopo de Ne wton mas sempre mantendo os coeficientes
dos termos que correspondem aos v´ertices do politopo n˜ao nulo. Podemos notar
que esta observa¸c˜ao nos d´a uma grande liberdade na escolha de polinˆomios para
aplica¸c ˜oes.
Como j´a foi comentado, um ´unico politopo pode representar in´umeros
polinˆomios e de acordo com o crit´erio 3.2.1, se este dado politopo f or integralmente
3 Fam´ılias Irredut´ıveis 35
indecompon´ıvel ent˜ao todos os polinˆomios que s˜ao representados por este politopo
ser˜ao absolutamente irredut´ıveis, ou seja, podemos observar que cada vez que tiver-
mos um politopo integralmente indecompon´ıvel teremos uma fam´ılia de polinˆomios
absolutamente irredut´ıveis, polinˆomios estes que s˜ao representados por tal politopo.
3.3 Constru¸c˜ao de Politopos Integralmente
Indecompon´ıveis
Contruiremos agora politopos indecompon´ıveis em R
n
. Como obser-
vado na se¸c˜ao anterior, cada tipo de politopo indecompon´ıvel dar´a uma fam´ılia de
polinˆomios absolutamente irredut´ıveis. Quando um politopo tem somente um ponto
diremos que este ´e trivial. Examinaremos v´arios tipos de politopos n˜ao triviais sim-
ples como segmentos de reta, triˆangulos, tetraedros, pirˆamides e outros. Tamb´em
mostraremos como construir politopos indecompon´ıveis a partir de um politopo
dado.
Um segmento de reta, conv (v
1
, v
2
), ser´a simplesmente denotado por
v
1
v
2
. Para um ponto integral ou vetor v = (a
1
, . . . , a
n
) escreveremos mdc (v) para
significar mdc (a
1
, . . . , a
n
), isto ´e, o m´aximo divisor comum das componentes em
v. Similarmente, para v´arios pontos v
1
, . . . , v
k
, mdc (v
1
, . . . , v
k
) significa o mdc de
todas componentes em v
1
, . . . , v
k
juntas.
Exemplo 3.3.1. Seja v
1
= (n, 0), v
2
= (0, m) e v
3
= (u, u), ent˜ao mdc (v
1
, v
2
, v
3
) =
mdc (n, 0, 0, m, u, u) = mdc (n, m, u).
Lema 3.3.1. Sejam v
0
e v
1
dois pontos integrais distintos em R
n
. Ent˜ao o n´umero
de pontos integrais no segmento de reta v
0
v
1
, incluindo v
0
e v
1
´e igual ao mdc (v
1
− v
0
)+
1. Al´em disso, se v
2
´e outro ponto integral sobre v
0
v
1
, ent˜ao
|v
2
− v
0
|
|v
1
− v
0
|
=
mdc (v
2
− v
0
)
mdc (v
1
− v
0
)
, (3.3)
onde |v| denota o comprimento euclidiano de um vetor v.
3 Fam´ılias Irredut´ıveis 36
Dem.: Os pontos no segmento de reta unindo v
0
e v
1
s˜ao da forma
v = v
0
+ t (v
1
− v
0
) , 0 ≤ t ≤ 1
como v
0
´e integral, ent˜ao v ´e integral se, e somente se, t (v
1
− v
0
) for integral. Mas
v
1
− v
0
´e integral, logo t deve ser um n´umero racional da forma
t =
i
k
, com 0 ≤ i < k e mdc (i, k) = 1.
Ent˜ao t (v
1
− v
0
) ´e integral se, e somente se, k divide mdc (v
1
− v
0
). Logo, k =mdc (v
1
− v
0
) ≥
1. Pois se k < mdc (v
1
− v
0
) n˜ao contar´ıamos todos os pontos integrais sobre v
0
v
1
.
Assim todos os pontos integrais no segmento de reta v
0
v
1
diferentes de v
0
e v
1
tem
t da forma
t =
i
mdc (v
1
− v
0
)
, para 0 < i < mdc (v
1
− v
0
).
Logo, o n´umero de escolhas para i ´e mdc (v
1
− v
0
) − 1 e assim o n ´umero de pontos
integrais sobre v
0
v
1
incluindo v
0
e v
1
´e mdc (v
1
− v
0
) − 1 + 2 =mdc (v
1
− v
0
) + 1.
Agora vamos provar a equa¸c˜ao 3.3. Seja d = mdc (v
1
− v
0
) e suponha que v
2
=
v
0
+i/d (v
1
− v
0
) ´e um ponto integral sobre v
0
v
1
com 0 ≤ i ≤ d. Note que (v
1
−v
0
)/d
´e integral e mdc ((v
1
− v
0
)/d) = 1 ent˜ao
mdc (v
2
− v
0
) = mdc
i
v
1
− v
0
d
= i · mdc
v
1
− v
0
d
= i.
E tamb´em
|v
2
− v
0
| = i
|v
1
− v
0
|
d
, |v
1
− v
0
| = d
|v
1
− v
0
|
d
e assim
|v
2
− v
0
|
|v
1
− v
0
|
=
i
d
=
mdc (v
2
− v
0
)
mdc (v
1
− v
0
)
.
O teorema a seguir ´e muito importante pois mostra como construir
politopos integralmente indecompon´ıveis a partir de um dado politopo.
Teorema 3.3.1. Seja Q um politopo integral em R
n
contido em um hiperplano H e
seja v ∈ R
n
um ponto integral fora de H. Suponha que v
1
, . . . , v
k
s˜ao todos os v´ertices
de Q. Ent˜ao o politopo conv (v, Q) ´e integralmente indecompon´ıvel se, e somente se,
mdc (v − v
1
, v − v
2
, ··· , v − v
k
) = 1.
3 Fam´ılias Irredut´ıveis 37
Figura 3.3: piramide indecompon´ıvel
Dem.: Seja C = conv (v, Q) como descrito na figura 3.3 e suponha que C = A + B
onde A e B s˜ao politopos integrais em R
n
. Deslocando adequadamente A e B
podemos supor v ∈ A e 0 ∈ B. Como v, v
1
, . . . , v
k
s˜ao todos os v´ertices de C, pelo
lema 2.4.1 existem v´ertices a
i
do A e b
i
do B ,´unicos, tais que
v
i
= a
i
+ b
i
para 1 ≤ i ≤ k
e
vv
i
= va
i
+ 0b
i
para 1 ≤ i ≤ k.
J´a que 0 ∈ 0b
i
, ent˜ao por soma de Minkowski va
i
+ 0 ⊆ vv
i
, logo o segmento de reta
va
i
coincide com uma parte de vv
i
come¸cando em v (observe a figura 3.3).Dados
v
1
, v
2
v´ertices de Q, ent˜ao v
1
v
2
´e uma aresta de C, logo pelo teorema 2.4.1
v
1
v
2
= a
1
a
2
+ b
1
b
2
.
Ent˜ao o segmento de reta a
1
a
2
´e paralelo a aresta v
1
v
2
. Isto significa que o triˆangulo
conv (v, a
1
, a
2
) ´e semelhante ao triˆangulo maior conv (v, v
1
, v
2
). Ent˜ao
|a
1
− v|
|v
1
− v|
=
|a
2
− v|
|v
2
− v|
e pelo lema 3.3.1, temos
mdc (a
1
− v)
mdc (v
1
− v)
=
mdc (a
2
− v)
mdc (v
2
− v)
(3.4)
3 Fam´ılias Irredut´ıveis 38
e como 3.4 vale para quaisquer dois v´ertices adjacentes, temos
|a
i
− v|
|v
i
− v|
=
mdc (a
i
− v)
mdc (v
i
− v)
= t para 1 ≤ i ≤ k, (3.5)
onde t ´e uma constante tal que 0 ≤ t ≤ 1. O n´umero t deve ser racional, digamos
t = m/d onde 0 ≤ m ≤ d, d ≥ 1 e mdc (m, d) = 1. Ent˜ao d | mdc (v
i
− v) para
1 ≤ i ≤ k. Suponha que mdc (v − v
1
, v − v
2
, ··· , v − v
k
) = 1 e j´a que
mdc (v − v
1
, v − v
2
, . . . , v − v
k
) =
mdc (mdc (v − v
1
) , mdc (v − v
2
) , . . . , mdc (v − v
k
)) = 1
ent˜ao vemos que d = 1, assim m = 0 ou m = 1, logo t = 0 ou t = 1. Se t = 0 ent˜ao
por 3.5 a
i
= v para 1 ≤ i ≤ k, logo A = {v}. Se t = 1 ent˜ao 3.5 implica que a
i
= v
i
para 1 ≤ i ≤ k, logo A = C e B = {0}. Portanto C ´e integralmente indecompon´ıvel.
Para a reciproca, suponhamos mdc (v − v
1
, v − v
2
, ··· , v − v
k
) = d > 1.
Seja u
i
=
1
d
(v
i
− v) para 1 ≤ i ≤ k. Assim os u
i
’s s˜ao pontos integrais em R
n
.
Definamos
A = conv (v, v
1
− u
1
, ··· , v
k
− u
k
) e B = conv (0, u
1
, . . . , u
k
) .
Vamos mostrar que C = A + B. Come¸caremos mostrando que A + B ⊆ C. Se-
jam a ∈ A e b ∈ B, ent˜ao a + b =
k
i=0
λ
i
(v
i
− u
i
) +
k
i=0
τ
i
u
i
onde v
0
= v, u
0
= 0 e
k
i=0
λ
i
=
k
i=0
τ
i
= 1. Assim a + b =
k
i=0
λ
i
(v
i
− u
i
) +
k
i=0
τ
i
u
i
=
k
i=0
v
i
λ
i
+
1
d
(τ
i
− λ
i
)
∈ conv (v, Q) = C p ois
k
i=0
λ
i
+
1
d
(τ
i
− λ
i
) =
k
i=0
λ
i
= 1. Agora vamos provar a
outra inclus˜ao, que C ⊆ A + B:
k
i=0
λ
i
v
i
=
k
i=0
λ
i
(v
i
+ u
i
− u
i
) =
k
i=0
λ
i
(v
i
− u
i
) +
k
i=0
λ
i
u
i
∈ A + B pois
k
i=0
λ
i
= 1.
J´a que d > 1 e u
i
= 0 e v
i
− u
i
= v para 1 ≤ i ≤ k. Ent˜ao A e B tem no m´ınimo
dois pontos cada, logo C ´e decompon´ıvel.
Exemplo 3.3.2. Seja f o polinˆomio 1 + x
n
+ y
m
+ x
n
y
m
+ x
i
y
j
z
k
∈ F [x, y, z]
onde n,m,k > 0 e i,j ≥ 0. Ent˜ao o politopo de Newton da f ´e a pirˆamide com
3 Fam´ılias Irredut´ıveis 39
v´ertices (0, 0, 0),(n, 0, 0),(n, m, 0),(0, m, 0) e (i, j, k). Se mdc (n, m, i, j, k) = 1 ent˜ao
a pirˆamide ´e indecompon´ıvel e assim, de acordo com o crit´erio de irredutibilidade
3.2.1, f ´e absolutamente irredut´ıvel sobre F.
Note que no exemplo 3.3.2 f permanece absolutamente irredut´ıvel se acrescentar-
mos a ela termos cujos expoentes vetoriais permane¸cam na pirˆamide. Tamb´em os
coeficientes do polinˆomio s˜ao todos 1, mas observe que poder´ıamos mud´a-los para
qualquer elemento n˜ao nulo do corpo em que estiv´essemos trabalhando e isso n˜ao
mudaria o politopo de Newton associado a f e assim f continuaria absolutamente
irredut´ıvel.
Os corol´arios seguintes especializam os casos simples como quando Q ´e
um ponto integral, um segmento de linha ou um triˆangulo.
Corol´ario 3.3.1. Sejam v
0
e v
1
dois pontos integrais distintos em R
n
. Ent˜ao o
segmento de reta v
0
v
1
´e integralmente indecompon´ıvel sse mdc (v
0
− v
1
) = 1.
Dem.: Constru´ımos o hip erplano H passando por v
0
e p erpendicular `a reta unindo
v
0
e v
1
, ent˜ao v
0
∈ H e v
1
/∈ H, assim, pelo teorema 3.3.1 v
0
v
1
´e integralmente
indecompon´ıvel sse mdc (v
1
− v
0
) = 1
O corol´ario 3.3.1 nos leva `a seguinte aplica¸c˜ao:
Corol´ario 3.3.2. Um polinˆomio com dois termos
aX
i
1
1
. . . X
i
k
k
+ bX
i
k+1
k+1
. . . X
i
n
n
∈ F [X
1
, . . . , X
n
] (3.6)
a, b ∈ F \ 0 ´e absolutamente irredut´ıvel sobre F sse mdc (i
1
, . . . , i
n
) = 1
Dem.: A demonstra¸c˜ao da rec´ıproca de ste corol´ario ´e imediata da aplica¸c˜ao do
corol´ario 3.3.1. Por´em a ida ser´a feita agora. Come¸camos dividindo 3.6 pelo seu
primeiro termo, e assim ficamos com
f := 1 + cx
−i
1
1
. . . x
−i
k
k
x
i
k+1
k+1
. . . x
i
n
n
(3.7)
3 Fam´ılias Irredut´ıveis 40
agora, vamos supor que mdc (i
1
, . . . , i
n
) = d > 1. Assim, i
k
= dα
k
para k = 1, . . . , n.
Podemos colocar ω = x
−α
1
1
. . . x
−α
k
k
x
α
k+1
k+1
. . . x
α
n
n
e assim f = 1+cω
d
com d > 1. Logo,
f ´e redutivel quando adjuntarmos o elemento c
1/d
, a d-´esima ra´ız de −1, ao corpo F .
Contradizendo nossa afirma¸c˜ao de o polinˆomio 3.6 ser absolutamente irredut´ıvel.
Exemplo 3.3.3. De acordo com o corol´ario 3.3.2 temos que:
1. x
n
+ y
m
´e absolutamente irredut´ıvel sobre um corpo F se, e somente se,
mdc(n, m) = 1.
2. y
i
+ x
j
z
k
´e absolutamente irredut´ıvel sobre um corpo F se, e somente
se, mdc(i, j, k) = 1.
Corol´ario 3.3.3. Sejam v
0
, v
1
, v
2
trˆes pontos integrais em R
n
, nem todos na mesma
reta. Ent˜ao o triˆangulo conv (v
0
, v
1
, v
2
) ´e integralmentre indecompon´ıvel sse
mdc (v
0
− v
1
, v
0
− v
2
) = 1
Dem.: Aplicando o teorema 3.3.1 com v
1
v
2
= Q ⊂ H = {v
0
+ λ (v
2
− v
1
) : λ ∈ R}
e v
0
/∈ H, temos que conv (v
0
, Q) = conv (v
0
, v
1
, v
2
) ´e integralmente indecompon´ıvel
sse mdc (v
0
− v
1
, v
0
− v
2
)
O pr´oximo resultado mostra uma aplica¸c˜ao do corol´ario 3.3.3.
Corol´ario 3.3.4. Seja f = aX
n
+ bY
m
+ cX
u
Y
v
+
c
ij
X
i
Y
j
∈ F [X, Y ] com a, b, c
n˜ao nulos. Suponha que o politopo de Newton da f ´e o triˆangulo com v´ertices (n, 0),
(0, m) e (u, v). Se mdc (m, n, u , v) = 1 ent˜ao f ´e absolutamente irredut´ıvel sobre F .
Dem.: Sejam v
0
= (u, v), v
1
= (n, 0) e v
2
= (0, m). Pelo corol´ario 3.3.3 se
mdc (v
0
− v
1
, v
0
− v
2
) =mdc (u − n, v, u, v − m) = 1 ent˜ao conv (v
0
, v
1
, v
2
) ´e inte-
gralmente indecompon´ıvel e assim f ser´a absolutamente irredut´ıvel. Ent˜ao devemos
mostrar que mdc (u − n, v, u, v − m) = 1. Por hip´otese mdc(m, n, u, v) = 1. Seja
d = mdc(u−n, v, u, v−m) ent˜ao d | (u−n−u) = −n, logo, d | n. Da mesma maneira
d | (v −m −v) = −m, logo, d | m. Ent˜ao d | (m, n, v, u) logo d | mdc (m, n, u, v) = 1
que nos leva a d = 1.
3 Fam´ılias Irredut´ıveis 41
Figura 3.4: hiperplanos de suporte
Para que o polinˆomio no corol´ario 3.3.4 permane¸ca absolutamente irredut´ıvel de-
vemos tomar cuidado para que os expoentes vetoriais (i, j) referentes aos termos
x
i
y
j
permane¸cam no politopo. Conforme foi estudado no cap´ıtulo 2 cada aresta
do triˆangulo ´e a intersec¸c˜ao do politopo com um hiperplano(observe a figura 3.4).
Ent˜ao
1. se a
1
´e a aresta que une os pontos (0, m) e (n, 0) temos que a
1
:=
P ∩ H
1
= P ∩ {(x, y) ∈ R
2
: (x, y)(m, n) = nm}
2. se a
2
´e a aresta que une os pontos (n, 0) e (u, v) temos que a
2
:=
P ∩ H
2
= P ∩ {(x, y) ∈ R
2
: (x, y)(−v, u − n) = −vn}
3. se a
3
´e a aresta que une os pontos (u, v) e (0, m) temos que a
3
:=
P ∩ H
3
= P ∩ {(x, y) ∈ R
2
: (x, y)(v − m, −u) = −mu}
e de acordo com 2.4.4 temos que P = H
−
1
∩H
−
2
∩H
−
3
. Assim, (i, j) est´a em P se, e
somente se, ele satisfizer:
1. mi + nj − mn ≥ 0
2. −vi + j(u − n) + vn ≥ 0
3 Fam´ılias Irredut´ıveis 42
3. i(v − m) − ju + mu ≥ 0.
Corol´ario 3.3.5. Sejam v
0
, v
1
, v
2
, v
3
quatro pontos integrais em R
n
, nem todos con-
tidos no mesmo plano. Ent˜ao o tetraedro conv (v
0
, v
1
, v
2
, v
3
) ´e integralmente inde-
compon´ıvel sse mdc (v
0
− v
1
, v
0
− v
2
, v
0
− v
3
) = 1.
Dem.: Sejam Q = conv (v
1
, v
2
, v
3
), v
0
/∈ Q, C = conv (v
0
, v
1
, v
2
, v
3
) = conv (v
0
, Q)
´e integralmente indecompon´ıvel sse mdc (v
0
− v
1
, v
0
− v
2
, v
0
− v
3
) = 1.
O pr´oximo resultado ´e uma aplica¸c˜ao do corol´ario 3.3.5.
Corol´ario 3.3.6. Suponha que o politopo de Newton da f = a
1
X
l
+ a
2
Y
m
+ a
3
Z
n
+
a
4
X
u
Y
v
Z
w
+
c
ijk
X
i
Y
j
Z
k
∈ F [X, Y, Z] seja o tetraedro com v´ertices (l, 0, 0),
(0, m, 0), (0, 0, n) e (u, v, w). Se mdc (l, m, n, u, v, w) = 1 ent˜ao f ´e absolutamente
irredut´ıvel sobre F.
Dem.: Sejam v
0
= (u, v, w), v
1
= (l, 0, 0), v
2
= (0, m, 0) e v
3
= (0, 0, n), se
mdc (v
0
− v
1
, v
0
− v
2
, v
0
− v
3
) =mdc (u − l, v, w, u, v − w, w − n) = 1 ent˜ao P
f
ser´a
integralmente indecompon´ıvel, logo, f ser´a absolutamente irredut´ıvel. Por hip´otese
mdc (l, m, n, u, v, w) = 1. Seja d = mdc (u − l, v − m, w − n, u, v, w) ent˜ao d | (u −l−
u) = −l, logo d | l e do mesmo modo d | m, d | n e assim d | mdc (l , m , n , u, v, w) = 1.
O que leva a d = 1.
O corol´ario seguinte nos diz que se, por exemplo em R
3
, tivermos uma
pirˆamide com uma aresta lateral ou uma aresta da base indecompon´ıvel ent˜ao a
pirˆamide ser´a indecompon´ıvel.
Corol´ario 3.3.7. Seja Q um politopo integral em R
n
contido em um hiperplano
H e seja v ∈ R
n
um ponto integral fora de H. Se Q tem uma aresta v
1
v
2
tal
que mdc (v
1
− v
2
) = 1 ou um v´ertice v
1
tal que mdc (v − v
1
) = 1 ent˜ao o politopo
conv (v, Q) ´e integralmente indecompon´ıvel.
Dem.: Sejam v
1
, . . . , v
k
todos os v´ertices de Q. Se mdc (v − v
1
) = 1 ent˜ao
mdc (v − v
1
, v − v
2
, ··· , v − v
k
) = mdc (mdc (v − v
1
) , ··· , (v − v
k
)) = 1 e pelo teo-
3 Fam´ılias Irredut´ıveis 43
rema 3.3.1 conv (v, Q) ´e integralmente indecompon´ıvel. Se mdc (v
1
− v
2
) = 1 e
d = mdc (v − v
1
, v − v
2
, ··· , v − v
k
) ent˜ao d | (v
1
− v) e d | (v − v
2
), logo d |
(v
1
− v + v − v
2
) = (v
1
− v
2
), assim d | mdc (v
1
− v
2
) = 1 e isso implica que d = 1.
Pelo teorema 3.3.1 conv (v, Q) ´e integralmente indecompon´ıvel.
Corol´ario 3.3.8. Seja f = g (X) + h (X
1
, . . . , X
n
) onde g ∈ F [X] de grau r e
h ∈ F [X
1
, . . . , X
n
] de grau total m. Se mdc (r, m) = 1 ent˜ao f ´e absolutamente
irredut´ıvel sobre F.
Dem.: Se necess´ario, podemos fazer uma transla¸c˜ao na vari´avel X para que a con-
stante de f seja n˜ao nula e assim o politopo de Newton de h que fica sendo a
base da nossa pirˆamide. Como h continua tendo grau total m, existe um termo
c
i
1
...i
n
X
i
1
1
. . . X
i
n
n
em h tal que i
1
+ ··· + i
n
= m cujo expoente vetorial (i
1
, . . . , i
n
)
´e o v´ertice v
1
de P
h
. E como g tem grau r, teremos um termo aX
r
em g cujo ex-
poente vetorial (r, 0, . . . , 0) determina num v´ertice v da pirˆamide fora da base. Seja
d = mdc(v − v
1
) = mdc(r, i
1
, . . . , i
n
). Ent˜ao d | i
1
+ ··· + i
n
= m, logo d | (m, r),
ou sej a, d | mdc(m, r). Isso implica que d = 1 e pelo corol´ario 3.3.7 temos que
P
f
´e integralmente indecompon´ıvel e assim, pelo teorema 3.2.1, f ´e absolutamente
irredut´ıvel.
Teorema 3.3.2. Seja Q um politopo integralmente indecompon´ıvel em R
n
que est´a
contido no hiperplano H e tem no m´ınimo dois pontos, e seja v ∈ R
n
um ponto(n˜ao
necessariamente integral) fora de H. Seja S um conjunto qualquer de pontos inte-
grais no politopo conv (v, Q). Ent˜ao o politopo conv (S, Q) ´e integralmente indecom-
pon´ıvel.
Dem.: Seja C = conv (S, Q) e como Q = C ∩ H ent˜ao Q ´e uma face de C. Se
C = A + B, ent˜ao pelo lema 2.4.1 A, B tem faces ´unicas A
1
e B
1
, respectivamente,
tais que Q = A
1
+B
1
. Como Q ´e integralmente indecompon´ıvel ent˜ao A
1
ou B
1
deve
ter apenas um ponto, digamos A
1
. Fazendo um deslocamento adequado de A e B,
podemos assumir que A
1
= {0} e B
1
= Q. Queremos mostrar que A = A
1
= {0}.
Seja r ∈ A. Ent˜ao r + Q ⊆ r + B ⊆ C = conv (S, Q) e como Q ⊂ H temos que
3 Fam´ılias Irredut´ıveis 44
r + Q ⊆ r + H e assim
r + Q ⊆ C ∩ (r + H) . (3.8)
Seja C
1
o cone gerado por v e Q. Ent˜ao
C ⊆ conv (v, Q) ⊆ C
1
e C
1
∩ H = Q (3.9)
e por 3.8 temos que
r + Q ⊆ C
1
∩ (r + H) (3.10)
e pelo lema 2.2.3 existe um n´umero real t ≥ 0 tal que
C
1
∩ (r + H) = v + t (Q − v) (3.11)
Vamos mostrar que t ≤ 1. Seja a ∈ Q, ent˜ao r + a ∈ C
1
∩(r + H) e por 3.11 existe
b ∈ Q tal que r + a = v + t (b − v). E tamb´em, r + a ∈ C ⊆ conv (v, Q) ent˜ao existe
b
1
∈ Q tal que r + a = v + t
1
(b
1
− v) para um certo 0 ≤ t
1
≤ 1. Ent˜ao
t (b − v) = t
1
(b
1
− v) (3.12)
Seja H = {x ∈ R
n
: α, x = β} onde α ∈ R
n
, β ∈ R. Como b, b
1
∈ Q, ent˜ao
α, b = α, b
1
e a equa¸c˜ao 3.12 implica que α, v + t (b − v) = α, v + t
1
(b
1
− v)
e assim t (β −α, v) = t
1
(β − α, v) , logo t = t
1
. E como 0 ≤ t
1
≤ 1 segue que
0 ≤ t ≤ 1. De 3.8 e 3.11 temos r + Q ⊆ v + t (Q − v), isto ´e
Q ⊆ tQ + d (3.13)
onde d = (1 − t) v − r ∈ R
n
. Para k > 0 inteiro aplicamos (3.13) k vezes
Q ⊆ t
k
Q +
t
k−1
+ ··· + t + 1
d (3.14)
Se 0 ≤ t < 1 ent˜ao 3.14 pode ser escrita como
Q ⊆ t
k
Q +
t
k
− 1
t − 1
d.
E como Q ´e limitado quando k → ∞, temos
Q ⊆ {0} +
−1
t − 1
a =
−1
t − 1
a
3 Fam´ılias Irredut´ıveis 45
e assim Q tem apenas um ponto contradizendo a hip´otese de Q ter no m´ınimo dois
pontos. Portanto t = 1 e assim 3.13 fica
r + Q ⊆ Q. (3.15)
Para k > 0 inteiro, aplicando (3.15) k vezes temos que
kr + Q ⊆ Q
e como Q ´e limitado quando k → ∞ ent˜ao r = 0 e A = A
1
= {0}.
Exemplo 3.3.4. Considere o tetraedro com v´ertices (0, 0, 0), (n, 0, 0), (0, m, 0) e
(0, 0, u). Note que o tetraedro ´e indecompon´ıvel se mdc(m, n) = 1. Dado o polinˆomio
f = 1 + x
n
+ y
m
+ x
w
y
v
+ y
i
z
j
+ z
k
, se (w, v, 0), (0, i, j) e (0, 0, k) estiverem no
tetraedro ent˜ao de acordo com o teorema 3.3.2 P
f
ser´a integralmente indecompon´ıvel
pois estar´a contido no tetraedro e os dois com a mesma base no plano xy. Logo, f
ser´a absolutamente irredut´ıvel.
Corol´ario 3.3.9. Seja f = aX
m
+ bY
n
+
c
ij
X
i
Y
j
∈ F [X, Y ] com a, b n˜ao nulos
e (i, j) diferente de (m, 0), (0, n). Suponha que o politopo de Newton de f es-
teja contido no triˆangulo (m, 0), (0, n) e (u, v) para algum ponto (u, v) ∈ R
2
. Se
mdc (m, n) = 1 ent˜ao f ´e absolutamente irredut´ıvel sobre F.
3.4 Proje¸c˜oes
Agora veremos novas constru¸c˜oes de politopos integralmente indecom-
pon´ıveis baseadas em proje¸c˜oes. Intuitivamente esperamos que, por exemplo, se
tivermos um quadrado e fizermos a proje¸c˜ao sobre um de seus lados e esta for inte-
gralmente indecompon´ıvel, ent˜ao o quadrado ser´a tamb´em, por´em veremos que isto
nem sempre ´e verdade.
Defini¸c˜ao 3.4.1. Dizemos que uma transformada linear π : R
n
−→ R
m
´e integral
se ela leva pontos integrais de R
n
para pontos integrais em R
m
.
3 Fam´ılias Irredut´ıveis 46
Lema 3.4.1. Seja P um politopo integral em R
n
e π : R
n
−→ R
m
uma transformada
linear integral. Se π (P ) ´e integralmente indecompon´ıvel e cada v´ertice de π (P ) tem
somente uma pr´e imagem em P ent˜ao P deve ser integralmente indecompon´ıvel.
Antes de provarmos o lema 3.4.1, vamos observar que um politopo inte-
gral P sob qualquer transformada linear integral continua sendo um politopo integral
e que cada v´ertice de π (P ) vem de um v´ertice de P.
Seja P um politopo em R
n
. Ent˜ao pelo teorema de Krein-Milman temos
que P = conv (vert(P )). Logo, P = conv (v
1
, . . . , v
l
). Dado w ∈ π (P ) temos que
w = π
l
i=1
λ
i
v
i
=
l
i=1
λ
i
π (v
i
) c om
l
i=1
λ
i
= 1 ent˜ao π (P ) ⊆ conv (π (v
1
) , . . . , π (v
l
)).
Agora, seja w ∈ conv (π (v
1
) , . . . , π (v
l
)) ent˜ao w =
l
i=1
α
i
π (v
i
) = π
l
i=1
α
i
v
i
com
l
i=1
α
i
= 1, logo w ∈ π (P ) . Portanto π (P ) = conv (π (v
1
) , . . . , π (v
l
)),logo
π (P ) ´e um politopo integral em R
n
.
Ent˜ao π (P ) = conv(π(vert(P ))), ou seja, cada v´ertice w de π (P ) vem
de w = π (v
j
) e assim, cada v´ertice de π (P ) vem de um v´ertice de P . Agora estamos
prontos para provar o lema 3.4.1.
Dem.: Iremos mostrar que se P ´e decompon´ıvel ent˜ao π (P ) tamb´em o ser´a. Suponha
P = A + B onde A, B s˜ao politopos integrais em R
n
com no m´ınimo dois pontos
cada. Ent˜ao π (P ) = π (A) + π (B) e precisamos mostrar que π (A) e π (B) tem no
m´ınimo dois pontos cada, vamos supor que π (A) tem apenas um ponto. Seja w
0
um v´ertice de P tal que π (w
0
) seja um v´ertice de π (P ). J´a que P = A + B, pelo
teorema 2.4.1 existem v´ertices ´unicos a
0
de A e b
0
de B tais que w
0
= a
0
+ b
0
. Como
A tem no m´ınimo dois pontos, seja a
1
outro v´ertice de A tal que a
0
a
1
seja uma
aresta de A. Pelo teorema 2.4.1, a
0
a
1
ser´a fator de uma aresta w
0
w
1
, com w
0
= w
1
.
Note que w
0
w
1
´e paralelo a a
0
a
1
, ou seja, elas tem o mesmo vetor dire¸c˜ao. Ent˜ao
podemos escrever w
1
= w
0
+ t(a
1
− a
0
), logo, w
1
− w
0
= t (a
1
− a
0
) para algum t
3 Fam´ılias Irredut´ıveis 47
real. Ent˜ao
π (w
1
− w
0
) = π (t (a
1
− a
0
)) = t (π (a
1
) − π (a
0
)) = 0
pois π (A) tem apenas um ponto. Logo π (w
1
) = π (w
0
) e assim dois v´ertices de P
v˜ao para um v´ertice de π (P ), contradizendo nossa hip´otese.
Corol´ario 3.4.1. Seja P um politopo integral em R
n
e π : R
n
−→ R
m
uma transfor-
mada linear integral que ´e injetora sobre os v´ertices de P . Se π (P ) ´e integralmente
indecompon´ıvel ent˜ao P tamb´em deve ser.
Teorema 3.4.1. Seja Q um politopo integralmente indecompon´ıvel em R
m
e π :
R
n
−→ R
m
uma transformada linear integral. Seja S um conjunto de pontos inte-
grais em π
−1
(Q) tendo exatamente um ponto em S para cada v´ertice v de Q. Ent˜ao
o politopo conv (S) em R
n
´e integralmente indecompon´ıvel.
Dem.: Basta notar que π (conv (S)) = Q e aplicar o lema 3.4.1.
Exemplo 3.4.1. Dado o polinˆomio f(x, y, z) = y
5
z + x
2
y
4
z
3
+ x
3
z
2
+ x
3
y
7
z
7
+
x
4
y
6
z
5
+x
6
y
10
z
12
+x
7
y
13
ent˜ao temos que o politopo de Newton associado a f ´e P =
conv((0, 5, 1), (2, 4, 3), (3, 0, 2), (3, 7, 7), (4, 6, 5), (6, 10, 12), (7, 13, 0)). Vamos definir
π como a proje¸c˜ao no plano xy.
Ent˜ao π(P ) = conv((0, 5), (2, 4), (3, 0), (3, 7), (4, 6), (6, 10), (7, 13)). Mas
π(P ) ´e o triˆangulo com v´ertices v
0
= (0, 5),v
1
= (3, 0) e v
2
= (7, 13) e cada um deles
possui apenas uma pr´e-imagem em P . Usando o corol´ario 3.3.3 conclu´ımos que π(P )
´e integralmente indecompon´ıvel pois mdc(v
0
−v
1
, v
0
−v
2
) =mdc(3, 5, 7, 8) = 1. Como
as condi¸c˜oes do lema 3.4.1 s˜ao satisfeitas podemos afirmar que P ´e integralmente
indecompon´ıvel. Deste modo, segue que f ´e absolutamente irredut´ıvel.
48
4 DECOMPOSIC¸
˜
AO DE POLITOPOS
Neste cap´ıtulo estudaremos os algoritmos desenvolvidos por Shuhong
Gao e Alan Lauder em [6, 8]. Come¸caremos com um algoritmo que testa a in-
decomponibilidade de politopos e sua aplica¸c˜ao ser´a importante na constru¸c˜ao de
novas fam´ılias de polinˆomios absolutamente irredut´ıveis. Depois veremos um algo-
ritmo que constr´oi todos os fatores integrais de um politopo e que pode ser ´util na
fatora¸c˜ao de polinˆomios como ser´a visto no cap´ıtulo seguinte. Terminamos estu-
dando um algoritmo que testa indecomponibilidade via proje¸c˜oes para politopos de
dimens˜ao maior do que 2.
4.1 Introdu¸c˜ao
Neste cap´ıtulo e como feito no anterior, associaremos a cada polinˆomio
multivariado um politopo, dito seu politopo de Newton. Como foi observado por
Ostrowski em 1921, se um polinˆomio f ´e redut´ıvel, ent˜ao seu politopo de Newton ´e
decompon´ıvel em rela¸c˜ao a soma de minkowski em politopos de Newton associados
aos fatores de f. Este resultado nos leva a dois problemas que ser˜ao estudados neste
cap´ıtulo:
Problema 1:
Dado um politopo integral, decidir se este ´e integralmente indecom-
pon´ıvel.
Aqui o politopo repres entar´a a envolt´oria convexa de um conjunto finito
de pontos integrais. Este ´e um caminho dif´ıcil pois mostraremos que decidir inde-
componibilidade de politopos ´e NP-completo. O interesse neste procedimento ´e que
cada vez que descobrimos um politopo integralmente indecompon´ıvel este nos leva a
uma fam´ılia de polinˆomios absolutamente irredut´ıveis que podem ser representados
por tal politopo.
4 Decomposi¸c˜ao 49
Problema 2:
Dado um politopo integral , encontrar todos os seus fatores integrais.
Dado um polinˆomio f o interesse em sabermos os fatores de seu politopo
de Newton associado poder´a ser ´util na fatora¸c˜ao de f . Como ser´a visto no cap´ıtulo 5
tentaremos fatorar um polinˆomio f em fatores cujos politopos de Newton associados
foram encontrados quando decompomos o politopo de Newton associado a f.
Na se¸c˜ao 4.2 apresentaremos o algoritmo de Grahan que tamb´em pode
ser encontrado com mais detalhes em [10, 17] que fornece os v´ertices da envolt´oria
convexa de n pontos no plano em O(n log n). O algoritmo de Grahan poder´a ser
usado para encontrar os v´ertices de um dado pol´ıgono. Na se¸c˜ao 4.4 iremos apre-
sentar os algoritmos de Gao e Lauder feitos em [6, 8]. O primeiro algoritmo dir´a se
um pol´ıgono integral ´e integralmente indecompon´ıvel ou n˜ao. Enquanto o segundo
algoritmo retornar´a todos os fatores integrais de um pol´ıgono integral, inclusive os
triviais. Na se¸c˜ao 4.5 apresentaremos o algoritmo feito por Gao e Lauder em [6, 8]
que decidir´a indecomponibilidade de politopos em R
n
fazendo sua proje¸c˜ao no plano.
4.2 Envolt´oria Convexa no Plano
Nosso objetivo nesta se¸c˜ao ´e apresentar o algoritmo de Grahan que
fornece os v´ertices no sentido anti-hor´ario da envolt´oria convexa de n pontos no
plano em O(n log n). Este algoritmo poder´a ser usado para calcular os v´ertices do
politopo de Newton associado de um polinˆomio bivariado.
Come¸caremos apresentando um exemplo com algumas hip´oteses, para
facilitar o entendimento, que mais tarde ser˜ao removidas.
Seja P = conv((2, 5), (1, 0), (0, 2), (1, 1), (4, 4), (4, 5), (5, 0)). Vamos as-
sumir que tenhamos um ponto extremo a = (5, 0) sendo que este ´e o ponto extremo
com coordenada x de mais alto valor e com coordenada y de mais baixo valor.
Agora vamos classificar os outros pontos de acordo com a sua inclina¸c˜ao em rela¸c˜ao
4 Decomposi¸c˜ao 50
Figura 4.1: ordena¸c˜ao no sentido anti-hor´ario
ao ponto a no sentido anti-hor´ario: b = (4, 5), c = (4, 4), d = (2, 5), e = (1, 2),
f = (1, 1) e g = (0, 0) (observe a figura 4.1). Estamos assumindo que temos sempre
somente dois pontos sobre cada segmento de reta que liga o ponto a a qualquer outro
ponto de S. Uma condi¸c˜ao que ser´a facilmente removida.
Iremos armazenar os pontos sobre a envolt´oria convexa em uma pilha
S. Inicialmente a pilha cont´em os dois primeiros pontos : S = (b, a). Em nosso
exemplo, com b no topo da pilha. Cada elemento que for adicionado `a pilha ficar´a
na posi¸c˜ao mais a esquerda dela, ou seja, no topo da pilha.
Vamos verificar se c ser´a adicionado a pilha. Para isso vamos calcular o
valor da ´area f ormada pelos pontos a, b e c. Note que (a, b, c) formam um triˆangulo no
sentido anti hor´ario em b e por consequˆencia disso A(a, b, c) > 0, e assim adicionamos
c a pilha. S = (c, b, a). Agora vamos verificar se d ser´a adicionado `a pilha. Note
que (b, c, d) forma um triˆangulo no sentido hor´ario em c, logo A(b, c, d) < 0. Isso
quer dizer que c ∈ int(P ), pois c ∈ H
−
, onde H ´e o hiperplano de suporte da aresta
que liga os pontos b e d que est´a ilustrado na figura 4.2. Logo, retiramos c da pilha
S. S = (b, a) e verificamos se d entra na pilha. Agora adicionamos d `a pilha, pois
a, b, d forma um triˆangulo no sentido anti hor´ario em b. S = (d, b, a).
4 Decomposi¸c˜ao 51
Figura 4.2: ponto interior
Continuando desta maneira notamos que e e f s˜ao adicionados `a pilha, assim S =
(f, e, d, b, a). O ponto g nos leva a tirar e e f da pilha, pois e, f, g formam um
triˆangulo no sentido hor´ario em f. Logo, f ∈ int(P ). Assim como, d, e, g t´ambem
formam um triˆangulo no sentido hor´ario em e, logo, e ∈ int(P ). Deste modo
adicionamos g `a pilha e ficamos com S = (g, d, b, a).
Antes de prosseguirmos vamos apresentar os comandos coloca(p,S) e
retira(S), que coloca p no topo da lista S, e retira o elemento que est´a no topo da
lista S, respectivamente.
Escolhendo p
0
, o v´ertice inicial. Escollheremos o ponto com a orde-
nada y de menor valor e no caso de existirem muitos pontos com a mesma ordenada,
procuramos entre estes o de abscissa de valor mais alto. Ponto que certamente ser´a
um v´ertice. Considerando p
0
como a origem, calculamos as inclina¸c˜oes dos outros
pontos e enumeramos como p
0
, p
1
,. . .,p
n−1
com p
n−1
sendo o ponto de maior an-
gula¸c˜ao anti-hor´ario conforme ilustrado na figura 4.3.
´
E importante notar que quando ordenamos os pontos deste modo ent˜ao
p
1
∈ bd(P ), assim inicializamos S = (p
1
, p
0
).
Colinearidade
4 Decomposi¸c˜ao 52
Figura 4.3: ordena¸c˜ao dos pontos
No caso de termos trˆes pontos ou mais colineares com um deles sendo
o p
0
, ou seja, trˆes pontos ou mais sobre um segmento de reta que liga p
0
a outros
pontos, ent˜ao ficamos com o ponto mais distante de p
0
e descartamos os outros.
No caso de a ´area entre trˆes pontos classificados for zero, A(p
i
, p
i+1
, p
i+2
) =
0 ent˜ao estes pontos s˜ao colineares e por isso o algoritmo que apresentaremos segue
adiante apenas se A(a, b, c) > 0 que ´e o mesmo que dizer: formar um triˆangulo no
sentido anti hor´ario.
Algoritmo 4.2.1 (Grahan).
Entra da: Um conjunto S de pontos no plano.
Sa´ıda: Os v´ertices da conv(S) ordenados no sentido anti-hor´ario.
1. Encontre o ponto com coordenada y de menor valor e entre estes o de
coordenada x de maior valor. Chame-o de p
0
.
2. Ordene todos os outros pontos de acordo com sua angularidade ao redor
de p
0
. No caso de um ou mais pontos com a mesma angularidade, fique
com o mais distante de p
0
e descarte os demais.
3. Pilha S = (p
1
, p
0
) = (p
t
, p
t−1
); t ´e o ´ındice do ponto no topo da pilha.
i ← 2
4 Decomposi¸c˜ao 53
enquanto i < n fa¸ca
se p
i
forma um triˆangulo no sentido anti- hor´ario com p
t−1
,p
t
ent˜ao coloca(p
i
,S) e i ← i + 1
sen˜ao retire(S).
Teorema 4.2.1. A envolt´oria convexa de n pontos no plano pode ser encontrada
utilizando o algoritmo de Graham em O(n log n).
Dem.: Na linha 2 o algoritmo precisa ordenar uma lista com n − 1 elementos.
´
E sabido que os algoritmos de ordena¸c˜ao trabalham em O(n log n) que pode ser
visto com maiores detalhes em [1, 2]. Nos demais passos h´a O(n) opera¸c˜oes, logo o
algoritmo trabalha em O(n log n).
4.3 Fatores e Decomposi¸c˜ao
Como foi definido anteriormente o ente convexo L ´e um fator de K se
existe um ente convexo M ∈ R
n
tal que K = L + M. Veremos que um fator de um
politopo tem a estrutura fortemente relatada pelo politopo. Essa observa¸c˜ao ficar´a
clara quando estivermos tratando de politopos em R
2
, ou seja pol´ıgonos.
Defini¸c˜ao 4.3.1. Para entes convexos K,L ∈ R
n
diremos que L pode ser deslocado
para dentro de K se para cada ponto x da fronteira de K existe um vetor transla¸c˜ao
t ∈ R
n
tal que x ∈ L + t ⊂ K.
Teorema 4.3.1. Sejam K,L ∈ R
n
. Ent˜ao L ´e um fator de K se, e somente se, L
pode ser deslocado para dentro de K.
Dem.: Se K = L + M e x ∈ K, existe y ∈ L e t ∈ M tal que x = y + t, assim
x ∈ L + t ⊂ K. Suponha que L desliza livremente para K. Seja x na f ronteira
de K. Por hip´otese, existe t ∈ R
n
tal que x ∈ L + t ⊂ K. Ent˜ao t ∈ K ∼ L e
x ∈ L + (K ∼ L). Pelo lema 2.3.3, L ´e um fator de K.
4 Decomposi¸c˜ao 54
Os poss´ıveis fatores de um politopo tˆem a estrututa muito parecida com
a do pr´oprio politopo. Sejam P , Q, R ∈ R
n
tais que P = Q+R, ent˜ao como foi feito
no teorema 2.4.1 se F ´e uma face de P , ent˜ao existem faces F
Q
de Q e F
R
de R tais
que F = F
Q
+ F
R
, todas as faces com o vetor normal em comum. Esta observa¸c˜ao ´e
para notarmos que os vetores normais das faces de um fator Q de P est˜ao entre os
vetores normais das faces de P . Particularmente f´acil ´e descrever os fatores de um
pol´ıgono em R
2
, o qual ser´a feito na se¸c˜ao seguinte.
4.4 Pol´ıgonos
Dado um pol´ıgono P podemos represent´a-lo por sua sequˆencia de arestas.
Sejam v
0
, v
1
, . . . , v
m−1
os v´ertices do pol´ıgono ordenados ciclicamente na dire¸c˜ao
hor´aria. As arestas de P s˜ao representadas pelos vetores E
i
= v
i
− v
i−1
= (a
i
, b
i
)
para 1 ≤ i ≤ m, onde a
i
, b
i
∈ N e os ´ındices s˜ao feitos m´odulo m. Chamamos cada
E
i
um vetor aresta.
Defini¸c˜ao 4.4.1. Um vetor v = (a, b) ∈ Z
2
´e dito um vetor primitivo se mdc (a, b) =
1.
Seja n
i
= mdc (a
i
, b
i
) e defina e
i
= (a
i
/n
i
, b
i
/n
i
). Ent˜ao E
i
= n
i
e
i
onde
e
i
´e um vetor primitivo para 1 ≤ i ≤ m.
A sequˆencia de vetores {n
i
e
i
}
1≤i≤m
, que chamamos sequˆencia de arestas
ou sequˆencia poligonal, identifica unicamente o pol´ıgono sob transla¸c˜ao determinada
pelo vetor v
0
, e esta ser´a a entrada para o algoritmo de decomposi¸c˜ao. Como a regi˜ao
do pol´ıgono ´e fechada, temos que
1≤i≤m
n
i
e
i
= (0, 0).
O lema a seguir ´e a motiva¸c˜ao para o algoritmo de decomposi¸c˜ao de
pol´ıgonos, pois ele diz exatamente como ser˜ao os fatores de uma poss´ıvel decom-
posi¸c˜ao do pol´ıgono dado.
4 Decomposi¸c˜ao 55
Lema 4.4.1. Seja P um pol´ıgono com sequˆencia de arestas {n
i
e
i
}
1≤i≤m
onde e
i
∈ Z
2
s˜ao vetores primitivos. Ent˜ao um pol´ıgono integral ´e um fator de P sse sua sequˆencia
de arestas ´e da forma {k
i
e
i
}
1≤i≤m
, 0 ≤ k
i
≤ n
i
, com
1≤i≤m
k
i
e
i
= (0, 0).
Dem.: Seja
e
i
1≤i≤m
a sequˆencia de arestas de um fator Q de P . Sabemos que cada
aresta ne de P pode ser decomposta, em rela¸c˜ao `a soma de Minkowski, pela soma de
duas arestas paralelas a e ou pela soma de uma aresta paralela a e e um ponto. Assim
e
deve ser da f orma ke com 0 ≤ k ≤ n, logo
e
i
1≤i≤m
= {k
i
e
i
}
1≤i≤m
onde 1 ≤ k
i
≤
n
i
. A sequˆencia de arestas {k
i
e
i
}
1≤i≤m
define um pol´ıgono fechado e ser´a um f ator
de P , com o outro fator tendo sequˆencia de arestas da forma {(n
i
− k
i
) e
i
}
1≤i≤m
.
Dada uma sequˆencia de arestas {n
i
e
i
}
1≤i≤m
o algoritmo de decom-
posi¸c˜ao checar´a a existˆencia de uma sequˆencia de inteiros k
i
, com 0 ≤ k
i
≤ n
i
para 1 ≤ i ≤ m, tal que
1≤i≤m
k
i
e
i
= (0, 0), com k
m
= n
m
e algum k
i
= 0.
Exemplo 4.4.1. Seja P o pol´ıgono da figura 4.4. Ent˜ao seus v´ertices ordenados
ciclicamente no sentido anti-hor´ario s˜ao v
0
= (0, 0), v
1
= (2, 0), v
3
= (2, 2) e
v
4
= (0, 2). Deste modo as arestas de P s˜ao representadas pelos vetores E
1
= (2, 0),
E
2
= (0, 2), E
3
= (−2, 0) e E
4
= (0, −2). Os quais nos levam `a seguinte sequˆencia
de arestas : n
1
= 2 e e
1
= (1, 0), n
2
= 2 e e
2
= (0, 1), n
3
= 2 e e
3
= (−1, 0), n
4
= 2
e e
4
= (0, −1). Note que
4
i=1
n
i
e
i
= (0, 0). De acordo com o lema 4.4.1 para
encontrarmos um fator do pol´ıgono P precisaremos resolver a seguinte equa¸c˜ao:
k
1
e
1
+ k
2
e
2
+ k
3
e
3
+ k
4
e
4
= (0, 0) com 0 ≤ k
i
≤ n
i
para 1 ≤ i ≤ 4. (4.1)
Note que k
1
= ··· = k
4
= 1 satisfaz 4.1, ent˜ao acabamos encontrando um fator
L = v
0
+
4
i=1
k
i
e
i
de P representado na figura 4.4. Observe que o outro fator M
de P tal que P = M + L tamb´em ´e M = v
0
+
4
i=1
k
i
e
i
.
4 Decomposi¸c˜ao 56
Figura 4.4: decomposi¸c˜ao de politopos
Observa¸c˜oes
1. Note que de acordo com o teorema 4.3.1 L pode ser deslocado para
dentro de P .
2. Note que cada aresta a
P
de P vem da soma de uma aresta a
L
de L com
uma aresta a
M
de M onde as arestas a
P
,a
L
e a
M
s˜ao paralelas.
3. Note que P ´e o politopo de Newton associado do polinˆomio f = 1 +
x
2
+y
2
+x
2
y
2
. A pergunta que ser´a respondida no cap´ıtulo 5 ´e: O fator
L do politopo P corresponde ao politopo de Newton associado de um
fator g do polinˆomio f ?
O problema que o algoritmo de decomposi¸c˜ao ir´a resolver ´e
Decomponibilidade do pol´ıgono(POLIDECOMP)
Entrada: A sequˆencia de arestas {n
i
e
i
}
1≤i≤m
de um
pol´ıgono convexo integral P .
Quest˜ao: P tem uma decomposi¸c˜ao integral ?
O tamanho da entrada deste problema ´e O (m (logN + logE)) onde N = max {n
1
, . . . , n
m
}
e E o valor absoluto m´aximo das coordenadas de e
i
, 1 ≤ i ≤ m.
A proposi¸c˜ao a seguir mostra a dificuldade deste problema.
4 Decomposi¸c˜ao 57
Proposi¸c˜ao 4.4.1. POLIDECOMP ´e NP-completo
Dem.: Certamente POLIDECOMP est´a em NP,pois dada uma decomposi¸c˜ao pr´opria
{k
i
e
i
}
m
i=1
do pol´ıgono podemos verific´a-la em tempo polinomial.
Para mostrarmos que POLIDECOMP ´e NP-completo, faremos uma
redu¸c˜ao polinomial do problema da Parti¸c˜ao, que ´e sabido ser NP-completo, para
POLIDECOMP. Vale lembrar que a entrada para Parti¸c˜ao ´e uma sequˆencia {s
i
}
m
i=1
de inteiros positivos que podemos peg´a-los em ordem n˜ao-decrescente, ou seja, s
1
≤
s
2
≤ . . . ≤ s
m
. Sej a t =
m
i=1
s
i
, a quest˜ao em Parti¸c˜ao ´e se existe uma subsequˆencia
de {s
i
} cuja soma dˆe t/2. Aqui assumimos que t ´e par, para caso contr´ario a
quest˜ao ´e facilmente respondida. Dada a sequˆencia {s
i
}
m
i=1
para parti¸c˜ao, podemos
transform´a-la na seguinte sequˆencia de arestas:
(s
1
, 1) , (s
2
, 1) , . . . , (s
m
, 1) , m (0, −1) , (−t/2, −1) , (−t/2, 1)
onde verificamos que esta sequˆencia d´a um pol´ıgono, p ois
m+3
i=1
n
i
e
i
= (0, 0) com
n
m+1
= m e n
i
= 1 para o restante. Assim, o pol´ıgono associado a essa sequˆencia
de arestas possui decomposi¸c˜ao pr´opria se, e somente se, a sequˆencia {s
i
}
m
i=1
pos-
sui uma subseqˆencia com soma t/2. Ent˜ao temos uma redu¸c˜ao polinomial, logo
POLIDECOMP ´e NP-completo.
A seguir apresentaremos um algoritmo que procura todos os fatores
de um pol´ıgono P ⊂ R
2
para verificar se P ´e integralmente decompon´ıvel ou n˜ao.
Usaremos a figura 4.4 como exemplo para explicarmos o que o algoritmo far´a. Uma
observa¸c˜ao muito importante que deve ser feita ´e a de que o algoritmo ir´a procurar
fatores de P da forma v
0
+
k
i
e
i
, ou seja, se encontrarmos um fator Q de P ent˜ao
Q ⊆ P .
Exemplo 4.4.2. Dado o pol´ıgono P e sua sequˆencia de arestas como no exem-
plo 4.4.1. Come¸caremos listando todos pontos integrais em P e armazenando no
conjunto P I. Ent˜ao P I = {(0, 0), (0, 1), (0, 2)(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}.
4 Decomposi¸c˜ao 58
Come¸camos calculando todos os pontos integrais que s˜ao obtidos via e
1
saindo de
v
0
= (0, 0):
• v
0
+ 0e
1
= (0, 0) ∈ P I;
• v
0
+ 1e
1
= (1, 0) ∈ P I;
• v
0
+ 2e
1
= (2, 0) ∈ P I.
Ent˜ao, temos A
1
= {(0, 0), (1, 0),(2, 0)} o conjunto de pontos integrais alcan¸cados
via e
1
. Agora veremos que pontos integrais s˜ao alcan¸cados via e
1
e e
2
.
• (0, 0) + 0e
2
= (0, 0) ∈ P I;
• (0, 0) + 1e
2
= (0, 1) ∈ P I;
• (0, 0) + 2e
2
= (0, 2) ∈ P I;
• (1, 0) + 0e
2
= (1, 0) ∈ P I;
• (1, 0) + 1e
2
= (1, 1) ∈ P I;
• (1, 0) + 2e
2
= (1, 2) ∈ P I;
• (2, 0) + 0e
2
= (2, 0) ∈ P I;
• (2, 0) + 1e
2
= (2, 1) ∈ P I;
• (2, 0) + 2e
2
= (2, 2) ∈ P I;
Ent˜ao os pontos integrais alcan¸cados via e
1
e e
2
s˜ao:
A
2
= {(0, 0), (0, 1), (0, 2)(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}.
(Note que A
1
⊂ A
2
). Agora vamos para os pontos integrais que s˜ao alcan¸cados via
e
1
, e
2
e e
3
.
4 Decomposi¸c˜ao 59
• (0, 0) + 0e
3
= (0, 0) ∈ P I
(0, 0) + 1e
3
= (−1, 0) /∈ P I. Este ponto integral ´e ent˜ao descartado pois
estamos procurando decomposi¸c˜oes de P contidas em P .
Prosseguindo como anteriormente temos que os pontos integrais alcan¸cados via e
1
,e
2
e e
3
s˜ao:
A
3
= {(0, 0), (0, 1), (0, 2)(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}.
(Note que A
2
⊂ A
3
). Do mesmo modo, os pontos integrais alcan¸cados via e
1
,e
2
,e
3
e
e
4
s˜ao:
A
4
= {(0, 0), (0, 1), (0, 2)(1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)}.
(Note que A
3
⊂ A
4
).
Podemos ver que v
0
= (0, 0) ∈ A
4
. Mas os pontos v que est˜ao em A
4
s˜ao da forma
v = v
0
+ k
1
e
1
+ k
2
e
2
+ k
3
e
3
+ k
4
e
4
.
Ent˜ao encontramos uma sequˆencia {k
i
e
i
} tal que v
0
= v
0
+ k
1
e
1
+ k
2
e
2
+ k
3
e
3
+ k
4
e
4
,
logo k
1
e
1
+ k
2
e
2
+ k
3
e
3
+ k
4
e
4
= (0, 0) que pelo lema 4.4.1 sabemos que ´e um fator
de P . Logo, P ´e integralmente decompon´ıvel.
Algoritmo 4.4.1 (PoliDecomp).
Entra da: A sequˆencia de arestas {n
i
e
i
}
1≤i≤m
de um pol´ıgono convexo integral P
come¸cando em um v´ertice v
0
onde e
i
∈ Z
2
s˜ao vetores primitivos.
Sa´ıda: P Decompon´ıvel ou Indecompon´ıvel.
1. Calcular o conjunto P I de todos os pontos integrais em P , e inicializar
A
0
= ∅.
2. Para cada i de 1 at´e m −1, calcular o conjunto A
i
de pontos em P I
que s˜ao obtidos via os vetores e
1
, . . . , e
i
:
Para cada 0 < k ≤ n
i
fa¸ca
Se v
0
+ ke
i
∈ P I ent˜ao
4 Decomposi¸c˜ao 60
acrescente-o a A
i
Para cada u ∈ A
i−1
e 0 ≤ k ≤ n
i
fa¸ca
Se u + ke
i
∈ P I ent˜ao
acrescente-o a A
i
3. Calcular o ´ultimo conjunto A
m
:
Para cada u ∈ A
m−1
e 0 ≤ k < n
m
fa¸ca
Se u + ke
m
∈ P I ent˜ao
acrescente-o a A
m
4. Retorne Indecompon´ıvel se v
0
/∈ A
m
e Decompon´ıvel caso contr´ario.
Teorema 4.4.1. O algoritmo acima decide corretamente decomponibilidade em
O (tmN) opera¸c˜oes vetoriais onde t ´e o n´umero de pontos integrais em P , m o
n´umero de arestas e N o n´umero m´aximo de pontos integrais em uma aresta.
Dem.: Para provar que o algoritmo funciona observe que todos os pontos em A
m
s˜ao da forma v
0
+
m
i=1
k
i
e
i
com 0 ≤ k
i
≤ n
i
. O passo 2.1 garante k
i
> 0 para
algum i < m(para eliminarmos a decomposi¸c˜ao trivial nula) e o passo 3 assegura
que k
m
< n
m
, isso pode ser feito pois se algum fator M de P possuir uma aresta
n
m
e
m
o outro fator L de P , tal que P = L + M, n˜ao ter´a nenhum peda¸co da aresta
e
m
e este fator tamb´em ser´a encontrado no algoritmo(note que v
0
+ ke
m
/∈ P I para
k > 0). Se um dos pontos em A
m
´e igual a v
0
ent˜ao
v
0
=
m
i=1
k
i
e
i
+ v
0
e assim
m
i=1
k
i
e
i
= (0, 0),
logo a sequˆencia k
i
e
i
forma uma sequˆencia de arestas de um fator integral pr´oprio
de P . Seja Q um fator integral pr´oprio de P, ent˜ao podemos transladar Q para o
v´ertice v
0
e assim coloc´a-lo em P , logo todos os pontos integrais de Q estar˜ao em P
e assim sua sequˆencia de arestas ser´a detectada pelo algoritmo.
O pior caso ocorre quando cada aresta alcan¸ca todos os pontos do poli-
topo. Como o politopo tem t pontos integrais e cada um deles pode ser alcan¸cado
O(Nm) vezes, ent˜ao o n´umero de passos do algoritmo ´e O(tmN).
4 Decomposi¸c˜ao 61
Observe que t = O(N
m
), logo, o n´umero de passos do algoritmo 4.4.1
´e exponencial. O exemplo a seguir mostra como o n´umero de decomposi¸c ˜oes de um
pol´ıgono pode ser exponencial.
Exemplo 4.4.3. Considere o pol´ıgono com sequˆencia de arestas
(1, 1) , (2, 1) , . . . , (m, 1) , m (0, −1) , t (−1, 0)
onde t = (m + 1) m/2. Para encontrarmos o n´umero de decomposi¸c˜oes, primeiro
devemos observar que: e
1
= (1, 1) ⇒ n
1
= 1, e
2
= (2, 1) ⇒ n
2
= 1,. . . , e
m
=
(m, 1) ⇒ n
1
= 1 e assim para termos um pol´ıgono fechado devemos ter: e
m+1
=
(0, −1) ⇒ n
m+1
= m e
m+2
= (−1, 0) ⇒ n
m+2
= (m + 1) m/2, e assim satisfazendo
m+2
i=1
n
i
e
i
= (0, 0).
Logo, nosso problema ´e: De quantas maneiras podemos resolver a seguinte equa¸c˜ao?
k
1
(1, 1)+k
2
(2, 1)+···+k
m
(m, 1)+k
m+1
(0, −1)+k
m+2
(−1, 0) = (0, 0)
onde 0 ≤ k
i
≤ n
i
para 1 ≤ i ≤ m + 2.
Observe que:
k
1
(1, 1)
2escolhas
+ ··· + k
m
(m, 1)
2escolhas
2
m
escolhas
+ (0, −m) + (−t, 0) = (0, 0)
Temos exatamente 2
m
fatores integrais do pol´ıgono.
Enquanto o algoritmo 4.4.1 retorna como resposta apenas se o pol´ıgono
´e decompon´ıvel ou n˜ao, o algoritmo que apresentaremos a seguir ´e uma generaliza¸c˜ao
deste, no qual dado um pol´ıgono sua sa´ıda n˜ao ser´a apenas um sim ou n˜ao e sim
um array contendo o n´umero de decomposi¸c˜oes pr´oprias do pol´ıgono e informa¸c˜oes
suficientes para contruir tais decomposi¸c˜oes.
4 Decomposi¸c˜ao 62
Algoritmo 4.4.2.
Entra da: A sequˆencia de arestas {n
i
e
i
}
1≤i≤m
de um pol´ıgono convexo integral P
come¸cando em um v´ertice v
0
onde e
i
∈ Z
2
s˜ao vetores primitivos.
Sa´ıda: O n´umero de fatores integrais de P incluindo os triviais, e um array A.
Cada c´elula em A cont´em um par (u, S) onde u ´e um inteiro n˜ao negativo e S ´e um
subconjunto de {(k, i) : 1 ≤ k ≤ n
i
, 1 ≤ i ≤ m}.
1. Calcular o conjunto P I de todos os pontos integrais em P (logo v
0
∈
P I); digamos que P I tem t pontos. Inicialize um t-array A
0
indexado
pelos pontos em P I. Inicialize A
0
[v] := (0, ∅) para todo v ∈ P I exceto
a c´elula A
0
[v
0
] que ´e inicializada com (1, ∅).
2. Para i de 1 at´e m fa¸ca, calcular o t-array A
i
de A
i−1
Primeiro copie o conte´udo de todas as c´elulas de A
i−1
para
A
i
(este passo ´e para k = 0).
Para cada v ∈ P I com o primeiro n´umero da c´elula A
i−1
[v]
n˜ao nulo fa¸ca
Para cada 0 < k ≤ n
i
fa¸ca
Se v
= v + ke
i
∈ P I ent˜ao
reescreva a c´elula A
i
[v
] como segue:
Se (u
1
, S
1
) ´e o valor de A
i−1
[v] e
(u
2
, S
2
) ´e o valor atual de A
i
[v
] ent˜ao
o novo valor de A
i
[v
] ´e (u
1
+
u
2
, S
2
∪ {(k, i)}).
3. Retorne o n´umero u e o array A = A
m
, onde (u, S) ´e o conte´udo da
c´elula A
m
[v
0
].
4 Decomposi¸c˜ao 63
Teorema 4.4.2. O inteiro na sa´ıda do algoritmo acima ´e o n´umero total de fatores
integrais do pol´ıgono P.
Dem.: Note que no final da i-´esima itera¸c˜ao v = v
0
+ k
1
e
1
+ ··· + k
i
e
i
onde 0 ≤
k
i
≤ n
i
, ou seja, descrevemos um caminho de v
0
at´e v usando as arestas e
1
, . . . , e
i
.
Na c´elula A
i
[v] armazenamos o n´umero inteiro positivo u que nos diz de quantas
maneiras diferentes saimos de v
0
e chegamos at´e v. Enquanto o conjunto S armazena
pares (k, j),0 < k ≤ n
j
, com j ≤ i que nos dizem que em um dos caminhos que
unem v e v
0
a ´ultima aresta usada foi ke
j
.
No final do algoritmo o inteiro u na c´elula A
m
[v
0
] nos diz o n´umero de
caminhos fechados da forma v
0
+
m
i=1
k
i
e
i
= v
0
, incluindo os triviais, e pelo lema
4.4.1 este ´e o n´umero de fatores integrais de P .
Como encontrar a decomposi¸c˜ao a partir do array A?
Quando o algoritmo retorna o array A, a c´elula A [v
0
] cont´em o par
(u, S). Para recuperarmos uma decomposi¸c˜ao do pol´ıgono, escolhemos um par (k, i)
do conjunto S e este nos leva ao segmento de linha ke
i
que ser´a a ´ultima aresta
de nossa decomposi¸c˜ao de P . Para encontrarmos a pen´ultima aresta, vamos at´e a
c´elula A [v
0
− ke
i
] =
u
, S
e pegamos um par
k
, i
de S
tal que i
< i e assim o
segmento de linha k
e
i
ser´a nossa pen´ultima aresta na decomposi¸c˜ao. Continuando
este processo criaremos uma sequˆencia i > i
> i
> ··· decrescente que nos levar´a
at´e a c´elula A [v
0
] novamente. Ent˜ao teremos uma decomposi¸c˜ao do pol´ıgono P .
Exemplo 4.4.4. Seja P o pol´ıgono com sequˆencia de arestas
n
1
= 2, e
1
= (0, 2) , n
2
= 1, e
1
= (2, 1) , n
3
= 2, e
3
= (0, −1) , n
4
= 1, e
4
= (−2, −1)
com v
0
= (0, 0). Ap´os aplicarmos o algoritmo a este pol´ıgono, nossa sa´ıda ser´a a
seguinte:
A = [A[(0, 0)] = (6; (1, 3)∪(2, 3)∪(1, 4))]; A [(0, 1)] = (4; (1, 1) ∪ (1, 3) ∪ (1, 4)) ;
A [(1, 1)] = (0, ∅) ; A [(2, 1)] = (3; (1, 2) ∪ (1, 3) ∪ (2, 3)) ; A [(0, 2)] = (2; (2, 1) ∪ (1, 4)) ;
A [(1, 2)] = (0, ∅) ; A [(2, 2)] = (2; (1, 2) ∪ (1, 3)) ; A[(2, 3)] = [(1; (1, 2))].
4 Decomposi¸c˜ao 64
Para recuperarmos uma decomposi¸c˜ao pr´opria do Pol´ıgono P vamos at´e
a c´elula:
A [(0, 0)] = (6; (1, 3) ∪ (2, 3) ∪ (1, 4))
agora escolhemos um par (k, i), que pode ser o par (1, 4). Este par diz que para
chegarmos no ponto (0, 0), o ´ultimo segmento de aresta usado foi o 1e
4
, ou seja que
n´os estavamos no ponto (0, 0) − 1e
4
= (2, 1). Ent˜ao, vamos para a c´elula A (2, 1):
A ((0, 0) − 1e
4
) = A (2, 1) = (3; (1, 2) ∪ (1, 3) ∪ (2, 3))
Agora escolhemos um par (k, i) tal que i < 4, pois j´a usamos a aresta e
4
. Seja o par
(1, 3), ele diz que para chegarmos no ponto (2, 1) usamos o segmento de aresta 1e
3
,
ou seja, que estavamos no ponto (2, 1) − 1e
3
= (2, 2). Ent˜ao, vamos para a c´elula
A (2, 2):
A [(2, 2)] = (2; (1, 2) ∪ (1, 3))
Agora escolhemos um par (k, i) tal que i < 3, pois j´a usamos a aresta e
3
. Seja o par
(1, 2), ele diz que para chegarmos no ponto (2, 2) usamos o segmento de aresta 1e
2
,
ou seja, que estavamos no ponto (2, 2) − 1e
2
= (0, 1). Ent˜ao, vamos para a c´elula
A (0, 1):
A [(0, 1)] = (4; (1, 1) ∪ (1, 3) ∪ (1, 4))
Agora escolhemos um par (k, i) tal que i < 2, pois j´a usamos a aresta e
2
. Seja o par
(1, 1), ele diz que para chegarmos no ponto (0, 1) usamos o segmento de aresta 1e
1
,
ou seja, que estavamos no ponto (0, 1) −1e
1
= (0, 0). Assim, acabamos recuperando
a seguinte decomposi¸c˜a pr´opria do pol´ıgono:
(0, 0) − 1e
4
− 1e
3
− 1e
2
− 1e
1
= (0, 0) .
Deste modo podemos recuperar todas as decomposi¸c˜oes pr´oprias do pol´ıgono P ,
fazendo todas as combina¸c˜oes poss´ıveis dos pares (k, i), respeitando as condi¸c˜oes
necess´arias.
Gostar´ıamos de mencionar que quando encontramos algum fator inte-
gral P
g
de P
f
, ele n˜ao necessariamente corresponde a um fator g de f. Por Exemplo:
4 Decomposi¸c˜ao 65
Exemplo 4.4.5. Seja
f := (a + bx
n
) + y
m
(c + dx
n
) ∈ K [x, y].
Seu politopo de Newton ´e o retˆangulo definido pelos v´ertices (0, 0),(n, 0),(n, m),
e (0, m). P ara decompor este retˆangulo estamos interessados em resolver a seguinte
equa¸c˜ao
k
1
(1, 0) + k
2
(0, 1) + k
3
(−1, 0) + k
4
(0, −1) = (0, 0) com
0 ≤ k
1
≤ n,
0 ≤ k
2
≤ m,
0 ≤ k
3
≤ n e
0 ≤ k
4
≤ m.
ou seja, resolvermos
k
1
− k
3
n+1
, k
2
− k
4
m+1
= (0, 0).
Logo, teremos (n + 1) (m + 1) fatores integrais de P
f
. Por´em f ´e quase
sempre irredut´ıvel, salvo alguns poucos casos.
Faremos agora um exemplo utilizando os resultados at´e agora vistos o
qual nos motivar´a para a se¸c˜ao seguinte.
Exemplo 4.4.6. Seja f = (x
10
y
4
+ x) z
5
+ x
7
y
2
z
3
+ x
2
y
2
z
2
+ y
3
z + x
2
y
3
∈ R, assim
o
Newt (f ) = conv ((10, 4, 5) , (1, 0, 5) , (7, 2, 3) , (2, 2, 2) , (0, 3, 1) , (2, 3, 0)) .
Definamos π sendo a proje¸c˜ao no plano xy e assim
π (Newt (f)) = conv ((10, 4) , (1, 0) , (7, 2) , (2, 2) , (0, 3) , (2, 3)) .
Utilizando o algoritmo 4.2.1 encontramos que os v´ertices do π(Newt(f )) orde nados
no sentido anti-hor´ario s˜ao (10, 4),(0, 3),(1, 0),(7, 2). Os quais tˆem somente uma
pr´e-imagem no Newt (f). Aplicando o algoritmo 4.4.1 no π(Newt(f )) descobrimos
4 Decomposi¸c˜ao 66
que este ´e integralmente indecompon´ıvel. Logo, as condi¸c˜oes do lema 3.4.1 s˜ao
satisfeitas e podemos concluir que o Newt (f) ´e integralmente indecompon´ıvel. Deste
modo, segue que f ´e absolutamente irredut´ıvel.
4.5 Politopos de Alta Dimens˜ao
Nesta se¸c˜ao ser´a apresentado um algoritmo, para politopos em R
n
, mo-
tivado pelo lema 3.4.1. A id´eia ser´a escolher uma transformada linear integral que
leve o politopo P de R
n
para um pol´ıgono π(P ) no plano e ent˜ao verificar se as
condi¸c˜oes do lema s˜ao satisfeitas. Isto ´e, checar se o pol´ıgono π(P ) ´e integralmente
indecompon´ıvel e se cada v´ertice de π(P ) tem somente uma pr´e imagem em P , se
as condi¸c˜oes forem satisfeitas ent˜ao podemos dizer que P ´e integralmente indecom-
pon´ıvel.
Representaremos pontos em R
n
como vetores coluna:
x ∈ R
n
ent˜ao x =
x
1
x
2
.
.
.
x
n
com x
1
, . . . , x
n
∈ R. Assim, um conjunto S
de l pontos em R
n
pode ser representado por uma matriz n × l onde cada coluna
representa um ponto.
Sejam u, v ∈ R
n
dois pontos integrais. Ent˜ao dado um ponto w ∈
R
n
, o produto (u, v)
t
w pode ser visto como um ponto em R
2
. Isto define uma
transforma¸c˜ao integral
π : R
n
−→ R
2
e
(u, v)
t
S (4.2)
4 Decomposi¸c˜ao 67
´e a imagem de S sob π em R
2
. O pol´ıgono definido pela envolt´oria convexa dos
pontos em 4.2 ´e dito pol´ıgono sombra, ou simplesmente sombra, de P transformado
por u e v.
Pelo lema 3.4.1 notamos que a condi¸c˜ao de que cada v´ertice de π (S) ⊂
R
2
tenha somente uma pr´e imagem em S ´e nec ess´aria, por isso o lema a seguir d´a
uma id´eia da probabilidade de escolhermos aleatoriamente pontos u e v em R
n
que
levem a uma transformada injetiva.
Lema 4.5.1. Seja S uma matriz n × l sobre um corpo sem colunas repetidas e
seja K qualquer subconjunto de cardinalidade k do mesmo corpo. Pegue u
i
∈ K
aleatoriamente e independentemente, 1 ≤ i ≤ n, e seja
(a
1
, . . . , a
l
) = (u
1
, . . . , u
n
) S.
Ent˜ao com probabilidade de no m´ınimo 1 −
l (l − 1)
2k
as entradas a
1
, . . . , a
l
s˜ao dis-
tintas.
Dem.: Diremos que um vetor ´e distinto se todas suas entradas s˜ao distintas, e um
vetor ´e constante se todas suas entradas s˜ao iguais. Provaremos o lema por indu¸c˜ao
sobre l. Quando l = 1, o lema ´e trivial. Seja l > 1. Assuma que o lema ´e satisfeito
para todas matrizes com menos que l colunas. J´a que l > 1, nem todas as linhas
de S s˜ao constantes. Tamb´em, linhas constantes podem ser descartadas. Logo a
primeira linha de S pode ser assumida n˜ao constante. Particionamos as colunas de
S por seus valores das entradas na primeira linha. Permutando as colunas de S,
podemos assumir que S ´e da forma
r
1
. . . r
1
··· r
t
. . . r
t
S
1
··· S
t
onde t ≥ 2. S
i
tem l
i
colunas com l
1
+ ··· + l
t
= m, e (r
1
, . . . , r
t
) ´e distinto. J´a
que S n˜ao tem colunas repetidas, S
i
tamb´em n˜ao tem para 1 ≤ i ≤ t. Observe que
(a
1
, . . . , a
l
) ´e distinto s se
1. para cada 1 ≤ i ≤ t, (u
2
, . . . , u
n
) S
i
´e distinto; e
4 Decomposi¸c˜ao 68
2. para cada par 1 ≤ i < j ≤ t, cada entrada de u
1
(r
i
, . . . , r
i
)+(u
2
, . . . , u
n
)S
i
´e distinta
de toda entrada de u
1
(r
j
, . . . , r
j
) + (u
2
, . . . , u
n
)S
j
.
Pela hip´otese de indu¸c˜ao, temos
P rob((u
2
, . . . , u
n
) S
i
´e distinto) ≥ 1 −
l
i
(l
i
− 1)
2k
para 1 ≤ i ≤ t,
logo
P rob((1) ser satisfeito ) ≥ 1 −
t
i=1
l
i
(l
i
− 1)
2k
.
Agora, calculamos a probabilidade do ´ıtem 2 ser satisfeito sobre as condi¸c˜oes do
´ıtem 1 satisfeitas. Precisamos encontrar a probabilidade do ´ıtem 2 ser satisfeito
dada qualquer escolha de u
2
, . . . , u
n
. Para qualquer par 1 ≤ i < j ≤ t, qualquer
coluna w
1
de S
i
e qualquer coluna w
2
de S
j
, se
u
1
r
i
+ (u
2
, . . . , u
n
) w
1
= u
1
r
j
+ (u
2
, . . . , u
n
) w
2
,
ent˜ao
u
1
= (u
2
, . . . , u
n
) (w
2
− w
1
) / (r
i
− r
j
) ,
como r
i
= r
j
. Logo u
1
deve evitar estes valores quando pertencer a S
1
. O n´umero
desses valores poss´ıveis ´e no m´aximo
l =
1≤i<j≤t
l
i
l
j
.
Ent˜ao, para qualquer escolha de u
2
, . . . , u
n
, a probabilidade do ´ıtem 2 ser satisfeito
´e no m´ınimo 1 − l/k,i.´e.,
P rob( (2) ser satisfeito : (1) ´e satisfeito ) ≥ 1 −
l
k
.
Al´em disso
P rob((a
1
, . . . , a
m
) ser distinto )
= P rob((1) e (2) serem satisfeitos)
= P rob((1) ser satisfeito).P rob((2) ser satisfeito : (1) ´e satisfeito)
≥
≥ 1 −
t
i=1
l
i
(l
i
− 1)
2k
1 −
l
k
4 Decomposi¸c˜ao 69
1− ≥ 1 −
t
i=1
l
i
(l
i
− 1)
2k
−
l
c
= 1 −
m (m − 1)
2k
como l
1
+ ··· + l
t
= m. Isto completa a prova.
Por exemplo, K = {−l
2
, . . . , −1, 0, 1, . . . , l
2
} tem k = 2l
2
+1 inteiros. Se
escolhermos as componentes de u e v de K aleatoriamente. Ent˜ao com probabilidade
de no m´ınimo 3/4 os p ontos em 4.2 s˜ao distintos, logo a condi¸c˜ao do lema 3.4.1 ´e
satisfeita, isto ´e, cada v´ertice da sombra tem somente uma pr´e imagem em S. Esta
probabilidade pode ser aumentada arbitrariamente para perto de 1 se aumentarmos
o tamanho do conjunto K.
Algoritmo 4.5.1.
Entra da: Um conjunto finito S de pontos integrais de R
n
.
Sa´ıda: Indecompon´ıvel ou Falhou. O primeiro caso significa que o politopo
P = conv (S) ´e provado ser indecompon´ıvel, enquanto o ´ultimo significa que a de-
componibilidade de P n˜ao est´a decidida.
1. Passo: Organize os pontos em S como uma matriz n ×l, ainda deno-
tado por S, onde l representa o n´umero de linhas de S e cada coluna
representa um ponto. Fixe um conjunto K de inteiros pequenos.
2. Passo: Escolha dois vetores u, v ∈ K
n
aleatoriamente e calcule a
proje¸c˜ao (u, v)
t
S = (a
1
, . . . , a
l
) onde a
i
∈ Z
2
.
3. Passo: Calcular os v´ertices, digamos v
1
, . . . , v
m
na dire¸c˜ao anti-hor´ario,
do pol´ıgono convexo definido pelos pontos a
1
, . . . , a
l
. Se mais que dois
pontos de S s˜ao transformados em um dos v´ertices v
i
s, ent˜ao retorne
Falhou e pare aqui.
4. Passo: Calcular E
i
= v
i
− v
i−1
= n
i
e
i
onde n
i
´e um inteiro positivo e
e
i
´e um vetor primitivo, 1 ≤ i ≤ m.
5. Passo: Entre com a sequˆencia de arestas {n
i
e
i
} no Algoritmo PoliDe-
comp. Se o ´ultimo diz Indecompon´ıvel ent˜ao retorne Indecom-
pon´ıvel, caso contr´ario retorne Falhou.
4 Decomposi¸c˜ao 70
Mesmo que o p olitopo seja integralmente indecompon´ıvel o algoritmo
4.5.1 pode falhar, embora com probabilidade pequena de acordo com o lema 4.5.1.
Se o politopo for decompon´ıvel ent˜ao o algoritmo sempre retornar´a falhou. De fato
a quest˜ao de decidir a decomponibilidade de politopos ´e um problema dif´ıcil, como
pode ser visto no trabalho [21], onde ´e apresentado um politopo indecompon´ıvel
cujas faces s˜ao todas decompon´ıveis. Portanto, ´e poss´ıvel que exista algum poli-
topo indecompon´ıvel cujos pol´ıgonos sombra sempre ser˜ao decompon´ıveis e ent˜ao o
algoritmo nunca obter´a ˆexito.
71
5 FATORANDO POLIN
ˆ
OMIOS VIA
POLITOPOS
Neste cap´ıtulo final, vamos aplicar todos os resultados at´e aqui estuda-
dos em um problema cl´assico da ´algebra: a fatora¸c˜ao de polinˆomios. Mais especi-
ficamente, estudaremos o algoritmo desenvolvido por Fatima Abu Salem, Shuhong
Gao e Alan G. B. Lauder em [18, 19] que fatora um dado polinˆomio bivariado f a
partir da decomposi¸c˜ao do seu politopo de Newton associado.
5.1 Introdu¸c˜ao
Neste cap´ıtulo estudaremos um m´etodo para fatorar um polinˆomio bi-
variado a partir de informa¸c˜oes a respeito do seu politopo de Newton associado,
como feito por Fatima Abu Salem, Shuhong Gao e Alan G. B. Lauder em [18].
Como foi estudado no cap´ıtulo 3, o politopo de Newton associado ao
polinˆomio multivariado f carrega muitas informa¸c˜oes a respeito de f. Por exemplo,
quando o politopo de Newton associado ao polinˆomio f ´e integralmente indecom-
pon´ıvel ent˜ao f ´e absolutamente irredut´ıvel. Por´em n˜ao sab´ıamos responder se
quando o politopo de Newton associado a f fosse integralmente decompon´ıvel se f
seria redut´ıvel ou n˜ao.
No artigo [6] que foi estudado no cap´ıtulo 4 ´e apresentado um algoritmo
que encontra todas as decomposi¸c˜oes integrais de um politopo em R
2
. A pe rgunta
que ficara em aberto e que foi respondida em [18], e que ser´a estudada no presente
cap´ıtulo, ´e se um dado fator integral do politopo de newton associado a f corresponde
a um fator do polinˆomio bivariado f.
Estudaremos o algoritmo feito em [18] que ´e uma modifi¸c˜ao do levan-
tamento de Hensel. Este algoritmo procura um fator g de um polinˆomio bivariado
f a partir de um fator do politopo de Newton associado a f. Como ser´a visto, o
5 Fatorando via politopos 72
algoritmo n˜ao funcionar´a para todos os polinˆomios, e sim para aqueles que s˜ao livre
de quadrados sobre certos subconjuntos das arestas de seus politopos de Newton.
Na se¸c˜ao 5.2 estudaremos o problema central do cap´ıtulo e na se¸c˜ao
5.3 poderemos notar a similaridade do problema que es tamos estudando com o
levantamento de Hensel padr˜ao. Na se¸c˜ao 5.4 estudaremos um lema chave para o
algoritmo de fatora¸c˜ao via politopos, o qual ser´a apresentado na se¸c˜ao 5.5.
5.2 Fatora¸c˜ao Parcial
De agora em diante estaremos trabalhando apenas com polinˆomios bi-
variados, e assim f sempre representar´a um polinˆomio em F[x, y]. Para e = (e
1
, e
2
) ∈
N
2
, o termo x
e
1
y
e
2
ser´a representado por x
e
e o politopo de Newton associado a f
ser´a denotado por P
f
ou Newt(f ).
Dado f um polinˆomio em F[x, y] podemos encontrar uma decomposi¸c˜ao
integral para seu politopo de Newton associado usando o algoritmo 4.4.2, ou seja,
Newt(f ) = Q + R com Q e R pol´ıgonos integrais no primeiro quadrante. Como
estamos interessados em saber se Q e R representam politopos de Newton de fatores
de f podemos associar a cada ponto integral q de Q e r de R as indeterminadas g
q
e h
r
. Isso nos leva a definir
g :=
q∈Q
g
q
X
q
h :=
r∈R
h
r
X
r
.
Diremos que g e h s˜ao os polinˆomios gen´ericos associados `a decomposi¸c˜ao Newt(f) =
Q + R. Nosso objetivo ser´a determinar os valores de g
q
e h
r
para que f = gh.
Exemplo 5.2.1. Seja f := x
2
+ y
2
+ x
3
+ x
3
y
2
∈ R[x, y].
Ent˜ao usando o algoritmo 4.4.2 encontramos uma decomposi¸c˜ao integral do pol´ıgono
Newt(f ) = Q + R onde Q e R est˜ao ilustrados na figura 5.1. Logo, os polinˆomios
gen´ericos dados pela decomposi¸c˜ao integral s˜ao: g := g
20
x
2
+g
11
xy +g
12
xy
2
+g
02
y
2
+
g
12
xy
2
+ g
22
x
2
y
2
e h := h
00
+ h
10
x.
5 Fatorando via politopos 73
Figura 5.1: polinˆomios gen´ericos
Seja #Newt(f) o n´umero de pontos integrais no Newt(f). Para desco-
brirmos se a decomposi¸c˜ao leva a fatores de f poder´ıamos multiplicar os polinˆomios
gen´ericos g e h e igualarmos a f. A igualdade f = gh nos leva a um sistema
de #Newt(f) equa¸c˜oes nas indeterminadas g
q
e h
r
, obtidas quando igualamos os
coeficientes de cada monˆomio x
e
com e ∈ Newt(f ) em ambos os lados da igualdade.
Mas o objetivo de agora em diante n˜ao ser´a apenas o de resolver este
sistema e sim, apresentar um modo eficiente de resolvˆe-lo.
Antes de prosseguirmos gostar´ıamos de dar uma id´eia de como ser´a
feita a fatora¸c˜ao via politopos. Como pode ser visto no apˆendice A o levanta-
mento de Hensel de um p olinˆomio f =
f
i
(x)y
i
∈ F[x, y] constr´oi uma fatora¸c˜ao
f = gh, onde g =
g
i
(x)y
i
e h =
h
i
(x)y
i
, a partir de uma fatora¸c˜ao inicial
f
0
(x) = g
0
(x)h
0
(x) e depois vai encontrando os termos dos fatores g e h do tipo
g
1
(x)y
1
e h
1
(x)y
1
,g
2
(x)y
2
e g
2
(x)y
2
e assim por diante. Ou seja, ´e feito um levanta-
mento horizontal e os termos em y v˜ao aparecendo sucessivamente como ilustrado na
esquerda da figura 5.2. Na fatora¸c˜ao via politopos j´a temos o formato dos poss´ıveis
fatores g e h de f, ou seja, j´a sabemos quais s˜ao seus poss´ıveis termos usando
os polinˆomios gen´ericos dados pela decomposi¸c˜ao do Newt(f). Ent˜ao motivado
pelo levantamento de Hensel estudaremos uma mudan¸ca de vari´avel que levar´a a
come¸carmos a determinar os coeficientes dos termos de g e h que correspondem a
expoentes vetoriais que est˜ao sobre as arestas e vamos subindo ao longo do politopo
como est´a ilustrado na figura 5.2, `a direita.
5 Fatorando via politopos 74
Figura 5.2: levantamento
Como foi descrito acima, os coeficientes dos termos dos poss´ıveis fatores g e h da
f ser˜ao determinados gradativamente a partir de um conjunto de arestas, isso nos
leva `a seguinte defini¸c˜ao.
Defini¸c˜ao 5.2.1. Seja S um subconjunto do Newt (f). Uma S-fatora¸c˜ao parcial da
f ´e uma determina¸c˜ao de um subconjunto das indeterminadas g
q
e h
r
tal que para
cada ponto integral s ∈ S os coeficientes dos monˆomios X
s
nos polinˆomios gh e f
s˜ao iguais.
Exemplo 5.2.2. Referindo-se ao exemplo 5.2.1, seja S = {(2, 0), (1, 1), (1, 2)}.
Ent˜ao quando igualamos os coeficientes dos monˆomios x
s
tal que s ∈ S obtemos
x
2
= h
00
g
20
x
2
logo h
00
g
20
= 1
x
2
y = h
00
g
21
x
2
y + h
10
xg
11
xy logo h
00
g
21
+ h
10
g
11
= 1
x
2
y
2
= h
00
g
22
x
2
y
2
+ h
10
xg
12
xy
2
logo h
00
g
22
+ h
10
g
12
= 1
O caso S = pontos integrais do Newt (f) ´e equivalente a uma fa-
tora¸c˜ao da f no sentido tradicional, e nos referiremos a ela como uma fatora¸c˜ao
completa. Agora suponha que tenhamos uma S-fatora¸c˜ao parcial e uma S
-fatora¸c˜ao
parcial e que al´em disso S ⊂ S
e que as indeterminadas determinadas na S-fatora¸c˜ao
parcial foram determinadas no mesmo corpo de elementos da S
-fatora¸c˜ao parcial.
5 Fatorando via politopos 75
Ent˜ao diremos que a S
-fatora¸c˜ao parcial estende a S-fatora¸c˜ao parcial. Chamare-
mos de extens˜ao pr´opria se S
tiver estritamente mais pontos integrais que S.
Denotaremos o conjunto de todas as arestas do newt (f) por Edge (f).
Cada aresta δ ∈ Edge (f ) ser´a vista como um segmento de reta de um v´ertice (u
1
, v
1
)
para um v´ertice (u
2
, v
2
), onde (u
1
, v
1
) ´e dito o v´ertice inicial da aresta.
Sejam d = mdc (u
2
− u
1
, v
2
− v
1
), u
0
= (u
2
− u
1
) /d, e v
0
= (v
2
− v
1
) /d.
Ent˜ao (u
0
, v
0
) representa a dire¸c˜ao de δ e os pontos integrais sobre δ s˜ao da forma
(u
1
, v
1
) + i (u
0
, v
0
) para 0 ≤ i ≤ d,
de acordo com o lema 3.3.1. Sejam (γ
1
, γ
2
) = (−v
0
, u
0
), uma rota¸c˜ao de 90 graus
do vetor (u
0
, v
0
) no sentido anti-hor´ario, pois assim (γ
1
, γ
2
) apontar´a para dentro do
politopo como ilustrado na figura 5.3.
Figura 5.3: vetores
Seja h
δ
= (u
1
, v
1
), (γ
1
, γ
2
), onde h
δ
´e a fun¸c˜ao suporte de δ. Definimos
(e) = γ
1
e
1
+ γ
2
e
2
− h
δ
para e = (e
1
, e
2
) ∈ R
2
.
Exemplo 5.2.3. Referindo-se ao exemplo 5.2.1, seja δ ∈ Edge(f) tal que δ vai de
(0, 2) a (2, 0) ent˜ao
δ
= e
1
+ e
2
− 2. Note que
δ
≥ 0 para todo e ∈ Newt(f):
δ
(1, 2) = 1 + 2 − 2 = 1,
δ
(3, 2) = 3 + 2 − 2 = 3, e
δ
(2, 0) = 2 + 0 − 2 = 0.
5 Fatorando via politopos 76
E que
δ
= 0 para e ∈ δ.
Deste modo podemos observar que tem a seguinte propriedade.
Proposi¸c˜ao 5.2.1. Seja N ewt (f) o pol´ıgono constru´ıdo no sentido anti-hor´ario,
ent˜ao (e) ≥ 0 para cada ponto e ∈ Newt (f), valendo a igualdade se e ∈ δ
Dem.: Note que (γ
1
, γ
2
) aponta para dentro do Newt (f ), logo Newt (f) ⊂ H
+
,
assim, dado e ∈ Newt (f),
(γ
1
, γ
2
) , (e
1
, e
2
) ≥ h
δ
,
logo, (γ
1
, γ
2
) , (e
1
, e
2
) = h
δ
+ r para algum r ≥ 0, assim (e) = (γ
1
, γ
2
) , (e
1
, e
2
)−
h
δ
= r ≥ 0. Agora se e ∈ δ ent˜ao (γ
1
, γ
2
) , (e
1
, e
2
) = h
δ
,logo (e) = 0.
Defini¸c˜ao 5.2.2. Com a nota¸c˜ao acima dizemos que ´e a fun¸c˜ao primitiva afim
associada com δ , denotada por
δ
.
A fun¸c˜ao
δ
tamb´em tem a seguinte propriedade. Como mdc(γ
1
, γ
2
) = 1
ent˜ao pelo algoritmo de Euclides existem ´unicos σ
1
e σ
2
tais que
σ
1
γ
1
+ σ
2
γ
2
= 1 (5.1)
sob a condi¸c˜ao de que 0 ≤ σ
2
< γ
1
.
Como pode ser visto na figura 5.4 o Newt(f) ´e cortado pelas retas
δ
= i onde i ´e um inteiro n˜ao negativo. Al´em disso, podemos observar que todos
os pontos integrais do politopo estar˜ao sobre estas retas.
Conforme a figura 5.5 cada ponto integral (e
1
, e
2
) do Newt(f) pode ser
escrito em fun¸c˜ao dos vetores (u
0
, v
0
) e (γ
1
, γ
2
) de uma aresta qualquer do Edge(f).
Ent˜ao
(e
1
, e
2
) := w(u
0
, v
0
) +
α(γ
1
, γ
2
)
(γ
1
, γ
2
)
(5.2)
onde α = e
1
γ
1
+ e
2
γ
2
. De acordo com 5.1 temos que γ
1
σ
1
+ γ
2
σ
2
= 1, ou seja,
(−v
0
)σ
1
+ u
0
σ
2
= 1. Multiplicando 5.2 por (σ
2
, −σ
1
) temos que
e
1
σ
2
− e
2
σ
1
= w + α(γ
1
, γ
2
)(σ
2
, −σ
1
)/ (γ
1
, γ
2
)
termo constante sobre cada reta paralela a (u
0
,v
0
)
.
5 Fatorando via politopos 77
Figura 5.4: arestas
Ent˜ao w = e
1
σ
2
− e
2
σ
1
+ constante em cada reta paralela a (u
0
, v
0
).
Deste modo qualquer monˆomio da f orma x
e
1
y
e
2
pode ser escrito como x
e
1
y
e
2
=
z
i
1
w
i
2
, onde
i
1
i
2
=
σ
2
−σ
1
γ
1
γ
2
e
1
e
2
cuja transformada inversa ´e
e
1
e
2
=
γ
2
σ
1
−γ
1
σ
2
i
1
i
2
Esta mudan¸ca de vari´avel tem as seguintes propriedades:
Quando e ∈ δ, ent˜ao e = (u
1
, v
1
) + i(u
0
, v
0
). Note que i
2
= γ
1
e
1
+
γ
2
e
2
=
δ
(e) + h
δ
permanece constante (i
2
= h
δ
). Enquanto i
1
= σ
2
e
1
− σ
1
e
2
=
σ
2
u
1
σ
1
v
1
+ i(σ
2
u
0
− σ
1
v
0
=1
), ou seja, o expoente de z aumenta para cada incremento
de (u
0
, v
0
). Observe que a mudan¸ca de vari´avel funciona do mesmo jeito para as
arestas paralelas a δ.
Exemplo 5.2.4. Referindo-se ao exemplo 5.2.1. Seja δ a aresta do Newt(f) que vai
do v´ertice (0, 2) ao v´ertice (2, 0). Ent˜ao
δ
(e) = e
1
+ e
2
−2, i
1
= −e
2
e i
2
= e
1
+ e
2
.
Fazendo a mudan¸ca de vari´avel em f chegamos a
f = w
2
+ z
−2
w
2
+ w
3
+ z
−2
w
5
5 Fatorando via politopos 78
Figura 5.5: mudan¸ca de vari´avel
Pelo teorema 2.4.1 sabemos que para cada δ ∈ Newt (f) existe um
´unico par de faces(sendo arestas ou v´ertices) δ
∈ Q e δ
∈ R tal que δ = δ
+ δ
.
Pela propriedade 5.2.1 podemos definir δ da seguinte maneira
δ = {e ∈ Newt (f) :
δ
(e) = 0}
pelo teorema 2.4.1 sabemos que h
δ
= h
δ
+ h
δ
e assim
δ
= {e ∈ Q :
δ
(e) = h
δ
− h
δ
}
e
δ
= {e ∈ R :
δ
(e) = −h
δ
}.
Exemplo 5.2.5. Referindo-se ao exemplo 5.2.1, seja δ a aresta do Newt(f) que
vai do v´ertice (0, 2) ao v´ertice (2, 0). Ent ˜ao
δ
= {e ∈ Q :
δ
(e) = 0}
e
δ
= {e ∈ R :
δ
(e) = −2}.
Seja Γ ⊆ Edge (f), e seja K = (k
γ
)
γ∈Γ
um vetor de inteiros p ositivos,
um para cada γ ∈ Γ. Defina
Newt (f ) |
Γ,K
:= {e ∈ Newt (f)|0 ≤
γ
(e) < k
γ
para γ ∈ Γ}.
5 Fatorando via politopos 79
Q
Γ,K
:= {e ∈ Q|0 ≤
γ
(e) < k
γ
− h
γ
para γ ∈ Γ
R
Γ,K
:= {e ∈ R|0 ≤
γ
(e) < k
γ
+ h
γ
para γ ∈ Γ
.
Note que Newt(f) |
Γ,K
, Q |
Γ,K
e R |
Γ,K
representam faixas nos seus respectivos
politopos, conforme pode ser observado na figura 5.6.
Exemplo 5.2.6. Referindo-se ao exemplo 5.2.1. Seja δ
1
a aresta do Newt(f) que
vai do v´ertice (0, 2) ao v´ertice (2, 0) e δ
2
a aresta do Newt(f) que vai do v´ertice
(2, 0) ao v´ertice (3, 0). Sejam Γ = {δ
1
, δ
2
} e K = (1, 1). Ent˜ao os pontos integrais
no Newt(f) |
Γ,K
s˜ao {(0, 2), (1, 1), (2, 0), (3, 0)}, os pontos integrais no Q |
Γ,K
s˜ao
{(0, 2), (1, 1), (2, 0)} e os pontos integrais no R |
Γ,K
s˜ao {(0, 0)}. Conforme repre-
sentado na figura 5.6.
Figura 5.6: faixas
Defini¸c˜ao 5.2.3. Uma Newt(f) | Γ, K- fatora¸c˜ao ´e dita uma (Γ, K; Q, R )- fa-
tora¸c˜ao se as seguintes duas propriedades forem satisfeitas:
• Exatamente os coeficientes indeterminados de g e h indexados pelos pontos inteiros
em Q |
Γ,K
e R |
Γ,K
, respectivamente, foram determinados.
• Seja K
=
k
γ
γ∈Γ
um vetor de inteiros positivos com k
γ
≥ k
γ
para todo γ ∈ Γ,
com a desigualdade estrita para no m´ınimo um γ. Ent˜ao nem todos coeficientes
indeterminados de g indexados por pontos inteiros em Q |
Γ,K
foram determinados.
5 Fatorando via politopos 80
Exemplo 5.2.7. Continuando o exemlo 5.2.6, onde K = (1, 1). Conforme a
defini¸c˜ao 5.2.3, ter´ıamos uma (Γ, K; Q, R)- fatora¸c˜ao se os coeficientes g
02
, g
11
, g
20
, g
30
e h
00
, h
10
indexados por pontos integrais em Q |
Γ,K
e R |
Γ,K
estivessem determina-
dos. E os coeficientes, g
20
e g
02
, indexados por pontos integra is em Q |
Γ,K
n˜ao
foram determinados onde K
= (1, 2).
Se o vetor K ´e unit´ario, denotado por K = (1), diremos uma (Γ; Q, R)-
fatora¸c˜ao parcial.
O problema central deste cap´ıtulo ´e:
Problema 5.2.1. Seja f ∈ F [x, y] com seu pol´ıgono de Newton ,Newt (f), e uma
decomposi¸c˜ao de Minkowski fixa Newt (f) = Q + R onde Q e R s˜ao pol´ıgonos
integrais no primeiro quadrante. Suponha que seja dada uma (Γ; Q, R)- fatora¸c˜ao
parcial de f para algum conjunto Γ ⊆ Edge (f). Construa uma fatora¸c˜ao completa
de f que a estenda, ou mostre que n˜ao pode ser estendida.
O algoritmo que ser´a apresentado no final do cap´ıtulo come¸ca com K = (1), ou seja,
teremos uma K-fatora¸c˜ao(fatora¸c˜ao parcial) na qual os coeficientes que correspon-
dem aos elementos dos conjuntos Q |
Γ,K
e R |
Γ,K
foram determinados. A id´eia do
algoritmo ´e de que a cada passo possamos estender a fatora¸c˜ao parcial, ou mostrar
que ela n˜ao pode ser estendida, usando um novo K
= (k
δ
) tal que
δ∈Γ
k
δ
>
δ∈Γ
k
δ
.
Este processo ´e feito at´e encontrarmos uma fatora¸c˜ao parcial que n˜ao pode ser
estendida ou quando chegarmos at´e um K tal que Q ⊆ Q |
Γ,K
, neste caso checamos
por divis˜ao se encontramos um fator de f.
5 Fatorando via politopos 81
5.3 Equa¸c˜oes do levantamento de Hensel Modificadas
Neste momento estudaremos as equa¸c˜oes b´asicas que ser˜ao usadas no
algoritmo as quais foram derivadas das equa¸c˜oes que s˜ao usadas no levantamento de
Hensel padr˜ao que pode ser visto no apˆendice A.
Para qualquer δ ∈ Edge (f ), temos
δ
. Para i ≥ 0 definimos
f
δ
i
:=
δ
(e)=i
a
e
X
e
.
Note que f
δ
i
´e obtida de f ap´os retirarmos todos os pontos cujos expoentes n˜ao est˜ao
sobre o hiperplano de suporte deslocado i para dentro do Newt (f), conforme figura
5.7. Chamaremos o polinˆomio f
δ
0
de polinˆomio aresta.
Figura 5.7: polinˆomios aresta
Dada a decomposi¸c˜ao Newt (f) = Q + R, sejam δ
e δ
as ´unicas arestas de Q e R
respectivamente, cuja soma d´a δ. Como antes vamos assumir que
δ
δ
= h
δ
−h
δ
e
δ
δ
= −h
δ
. Para i ≥ 0 definimos
g
δ
i
:=
q∈Q,
δ
(q)=h
δ
−h
δ
+i
g
q
X
q
h
δ
i
:=
r∈R,
δ
(r)=−h
δ
+i
h
r
X
r
.
5 Fatorando via politopos 82
Exemplo 5.3.1. Referindo-se ao exemplo 5.2.1. Seja δ a aresta do Newt(f) que vai
de (0, 2) a (2, 0). Ent˜ao
δ
(e) = e
1
+ e
2
− 2. Assim
f
δ
0
=
δ
(e)=i
a
e
x
e
= x
2
+ xy + y
2
f
δ
1
=
δ
(e)=i
a
e
x
e
= x
3
+ x
2
y + xy
2
como ilustrado em 5.7. Assim como para
g
δ
0
= g
20
x
2
+ g
11
xy + g
02
y
2
g
δ
1
= g
21
x
2
y + g
12
xy
2
e para
h
δ
0
= h
00
h
δ
1
= h
10
x
Lema 5.3.1. Sejam f ∈ F [x, y] e Newt (f) = Q + R uma decomposi¸c˜ao integral
com polinˆomios gen´ericos correspondentes g e h. Seja δ ∈ Edge (f). O sistema
de equa¸c˜oes nos coeficientes indeterminados de g e h que s˜ao definidos quando
igualamos os monˆomios em ambos os lados da igualdade f = gh tem as mesmas
solu¸c˜oes que o sistema de equa¸c˜oes definido a seguir:
f
δ
0
= g
δ
0
h
δ
0
e g
δ
0
h
δ
k
+ h
δ
0
g
δ
k
= f
δ
k
−
j=1
k−1
g
δ
j
h
δ
k−j
para k ≥ 1. (5.3)
Ent˜ao qualquer determina¸c˜ao dos coeficientes indeterminados que ´e uma solu¸c˜ao das
equa¸c˜oes 5.3 dar´a uma fatora¸c˜ao completa de f.
Dem.: Na equa¸c˜ao f = gh basta igualar em ambos os lados todos os monˆomios
cujos expoentes vetoriais est˜ao sobre o mesmo deslocamento da reta suporte δ.
Estas s˜ao as equa¸c˜oes que ser˜ao usadas no algoritmo de fatora¸c˜ao via
politopos. Come¸camos com uma determina¸c˜ao dos coeficientes de g
δ
0
e h
δ
0
que d´a
uma fatora¸c˜ao do polinˆomio f
δ
0
, neste momento obtemos uma fatora¸c˜ao parcial. A
equa¸c˜ao 5.3 com k = 1 d´a um sistema linear nos coeficientes indeterminados de g
δ
1
5 Fatorando via politopos 83
e h
δ
1
, a id´eia ´e resolver este sistema para estender a fatora¸c˜ao parcial original. Este
processo ´e iterado para k > 1 at´e que todos os coeficientes indeterminados e m um
dos polinˆomios gen´ericos tenham sido determinados, neste momento checamos se
encontramos um fator por divis˜ao.
5.4 Lema Geom´etrico
Defini¸c˜ao 5.4.1. Seja Λ um conjunto de arestas de um pol´ıgono P em R
2
e r um
vetor em R
2
. Dizemos que Λ domina P na dire¸c˜ao r se as seguintes duas condi¸c˜oes
s˜ao satisfeitas:
• P est´a contido na soma de Minkowski do conjunto Λ e o segmento de reta infinito
rR
≥0
(A envolt´oria positiva de r). Chamaremos esta soma de Mink (Λ, r).
• Cada uma das duas arestas infinitas de Mink (Λ, r) cont´em exatamente um ponto
de P .
Defini¸c˜ao 5.4.2. Diremos que Λ ´e um conjunto dominante irredundante na dire¸c˜ao
r se Λ ´e um conjunto dominante na dire¸c˜ao r que n˜ao contem estritamente qualquer
outro conjunto dominante na dire¸c˜ao r.
Exemplo 5.4.1. Como podemos observar na figura 5.8. Γ = {δ
1
, δ
2
}, onde δ
1
vai
do v´ertice (0, 2) ao (2, 0) e δ
2
vai do v´ertice (2, 0) ao (3, 0), ´e um conjunto dominante
irredundante do politopo na dire¸c˜ao r = (1, 1).
Figura 5.8: conjunto dominante de arestas
5 Fatorando via politopos 84
Proposi¸c˜ao 5.4.1. As aresta em um conjunto dominante irredundante s˜ao adja-
centes.
Vamos definir a transformada π
r
.
Defini¸c˜ao 5.4.3.
π
r
: R
2
−→ r
⊥
:= {s ∈ R
2
| s, r = 0}.
Assim, dado v ∈ R
2
ent˜ao v = w + λr com w ∈ r
⊥
e λ ∈ R. Logo,
v = w + λr. Fazendo produto interno com r obtemos: v, r = w, r + λr, r =
λr, r(pois w⊥r). Logo, λ =
v,r
r,r
e definimos π
r
(v) = v −
v,r
r,r
r.
Segue des ta defini¸c˜ao que π
r
(P ) = π
r
(Λ) se Λ domina P na dire¸c˜ao r.
Proposi¸c˜ao 5.4.2. Se e
1
e e
2
s˜ao arestas adjacentes em um conjunto dominante
irredundante Λ na dire¸c˜ao r, ent˜ao π
r
(e
1
e
2
) = π
r
(e
1
) + π
r
(e
2
).
Dem.: Note que, como Λ domina P na dire¸c˜ao r, ent˜ao r n˜ao pode ser paralelo a
qualquer aresta do P , pois o segundo ´ıtem da defini¸c˜ao 5.4.1 n˜ao seria satisfeito.
Vamos supor que n˜ao seja verdade. Ent˜ao π
r
(e
1
) ⊆ π
r
(e
2
) ou vice-
versa, conforme a figura 5.9.
Figura 5.9: proje¸c˜ao
5 Fatorando via politopos 85
Logo, rR
≥0
+ e
1
⊆ rR
≥0
+ e
2
e assim Λ seria redundante, uma contradi¸c ˜ao.
A propriedade 5.4.2 continua valendo se repassarmos e
1
e e
2
por quais-
quer segmentos de reta paralelos a eles. Ainda obteremos uma aditividade nos
comprimentos.
O lema a seguir ´e a chave do algoritmo, pois garante que a fatora¸c˜ao
parcial pode ser estendida.
Lema 5.4.1. Seja P um pol´ıgono integral e Λ um conjunto dominante irredundante
de arestas de P . Suponha Λ
1
um segmento de reta poligonal em P tal que cada aresta
de Λ
1
´e paralela a alguma aresta de Λ. Se Λ
1
´e diferente de Λ ent˜ao Λ tem no m´ınimo
uma aresta que tem estritamente mais pontos inteiros que a correspondente aresta
em Λ
1
.
A figura 5.10 ilustra o lema 5.4.1.
Figura 5.10: s egmento de reta poligonal
Dem.: Assumimos que Λ domina P na dire¸c˜ao r. Sejam δ
1
, . . . , δ
k
as arestas em Λ
paralelas `as arestas δ
1
, . . . , δ
k
de Λ
1
. Seja n
i
o n´umero de pontos inteiros sobre δ
i
e
m
i
o n´umero de pontos inteiros sobre δ
i
, para 1 ≤ i ≤ k. Dado Λ = Λ
1
, queremos
mostrar que n
i
> m
i
para no m´ınimo um i entre 1 e k. Vamos sup or o contr´ario,
que
n
i
≤ m
i
para 1 ≤ i ≤ k. (5.4)
5 Fatorando via politopos 86
Note que se m
i
= 0 para algum i, ent˜ao estamos prontos, pois cada δ
i
possui no
m´ınimo dois pontos inteiros(n
i
≥ 2 para 1 ≤ i ≤ k). Assim, pode mos assumir que
m
i
≥ 1 para 1 ≤ i ≤ k.
Como Λ ´e dominante, ent˜ao π (P ) = π (Λ) e π (Λ
1
) ⊂ π (P ), logo
π (Λ
1
) ⊂ π (Λ) . Note que como Λ
1
´e diferente de Λ, seus pontos finais n˜ao podem
coincidir, pois o ´unico modo de Λ
1
e Λ terem seus pontos finais e iniciais coincidindo
´e se Λ
1
= Λ. Assim, pelo menos um dos pontos finais de Λ
1
n˜ao estar´a sobre as
arestas infinitas de Mink (Λ, r). Ent˜ao π (Λ
1
) estar´a totalmente contido no π (Λ).
Logo
π (Λ
1
) < π (Λ). (5.5)
Agora, vamos considerar o vetor dire¸c˜ao de δ
i
o v
0
i
e π (v
0
i
) =
i
, o qual ser´a
o mesmo para δ
i
, ent˜ao π (δ
i
) = (n
i
− 1)
i
e pela propriedade 5.4.2 π (Λ) =
k
i=1
(n
i
− 1)
i
. E como δ
i
δ
i
, ent˜ao
π (Λ
1
) =
k
i=1
(m
i
− 1)
i
.
Assim, 5.4 nos leva a
k
i=1
(n
i
)
i
≤
k
i=1
(m
i
)
i
,
ou seja, que π (Λ) ≤ π (Λ
1
). Contradizendo 5.5, a qual nos diz que π(Λ
1
) ´e
estritamente menor que π(Λ). O lema est´a provado.
5.5 O Teorema Principal
Seja Γ um conjunto dominante irredundante do Newt (f) na dire¸c˜ao de
r. Chamaremos uma (Γ; Q, R)-fatora¸c˜ao parcial de f de uma fatora¸c˜ao de arestas
dominante relativa a Γ, Q e R.
Defini¸c˜ao 5.5.1. Uma fatora¸c˜ao de arestas dominante coprima ´e uma (Γ; Q, R)-
fatora¸c˜ao parcial com a propriedade que para cada δ ∈ Γ os polinˆomios aresta g
δ
0
e
h
δ
0
s˜ao coprimos, sob fatores monomiais.
5 Fatorando via politopos 87
Teorema 5.5.1. Seja f ∈ F [x, y] e Newt (f) = Q + R uma decomposi¸c˜ao de
Minkowski fixa, onde Q e R s˜ao pol´ıgonos integrais no primeiro quadrante. Seja Γ
um conjunto dominante irredundante do Newt (f) na dire¸c˜ao r, e assuma que Q
n˜ao ´e apenas um ponto nem um segmento de reta paralelo a rR
≥0
. Para qualquer
fatora¸c˜ao de arestas dominante coprima de f relativa a Γ, Q e R, existe no m´aximo
uma fatora¸c˜ao completa de f que a estende, e al´em disso esta fatora¸c˜ao completa
pode ser encontrada ou mostrar que n˜ao existe em tempo polinomial em = Newt(f).
A prova do teorema seguir´a facilmente ap´os a prova dos pr´oximos dois
lemas.
Algumas propriedades de conjuntos dominantes
Λ := {δ ∈ Γ ⊂ Edge (f) : δ
´e uma aresta e n˜ao apenas um v´ertice }.
Proposi¸c˜ao 5.5.1. Λ = ∅.
Dem.: Vamos supor que Λ = ∅. Ent˜ao com um deslocamento adequado vemos que
Γ ⊂ R e π (R) = π (Γ) que ´e a π (P ) conforme a figura 5.11. Assim, se Q for apenas
um ponto, podemos ter Λ = ∅. Mas assim n˜ao respeitamos nossas hip´oteses. Agora,
se Q tiver pelo menos uma aresta ϑ, essa aresta dever´a ser paralela a r ou Λ n˜ao
dominar´a o Newt (f). Pois, Γ + ϑ n˜ao estar´a contido no Mink (Λ, r). Logo Λ = ∅.
Figura 5.11: conjuntos dominantes
5 Fatorando via politopos 88
Proposi¸c˜ao 5.5.2. Seja Γ um conjunto dominante irredundante para Newt (f) na
dire¸c˜ao r. Ent˜ao o conjunto Γ
=
δ
δ∈Λ
´e um conjunto dominante irredundante
para Q na dire¸c˜ao r.
Dem.: Come¸camos mostrando que Γ
domina Q na dire¸c˜ao r , para ent˜ao mostrar-
mos que Γ
´e irredundante. Vamos supor que exista δ
j
aresta de Q que n˜ao est´a
totalmente contida no Mink
Γ
, r
, ent˜ao δ
j
n˜ao estar´a totalmente contida no
Mink (Γ, r), contradi¸c˜ao.Assim Q ⊂ M ink
Γ
, r
.
Agora vamos supor que pelo menos uma das arestas infinitas de
Mink
Γ
, r
cont´em dois pontos ou mais de Q, ou seja, Q cont´em uma aresta
α
paralela a r, ou seja, existe α ∈ Edge (f) tal que α ´e paralela a r, ent˜ao Γ n˜ao
domina Newt (f ) na dire¸c˜ao r. Contradi¸c˜ao, logo Γ
domina Q na dire¸c˜ao r.
Vamos mostrar que Γ
´e irredundante, para isto vamos supor que Γ
´e
redundante e chegaremos a uma contradi¸c˜ao. Como Γ
´e redundante, ent˜ao podemos
retirar um certo δ
j
tal que δ
j
⊂ δ
i
+rR
≥0
, por´em δ
j
= δ
j
+δ
j
, logo δ
j
⊂ δ
i
+δ
j
+rR
≥0
,
ent˜ao Γ ´e redundante. Contradi¸c˜ao, ent˜ao Γ
´e irredundante.
Agora temos as ferramentas necess´arias para provarmos o lema a seguir.
Lema 5.5.1. Sejam f,Q,R e Γ como no enunciado do teorema 5.5.1. Suponha
que seja dada uma K-fatora¸c˜ao de f, onde K = (k
δ
)
δ∈Γ
(mais especificamente, uma
(Γ, K; Q, R)-fatora¸c˜ao). Para cada δ ∈ Γ, denote por δ
a face de Q suportada por
δ
− (h
δ
− h
δ
). Ent˜ao existe δ ∈ Γ com as seguintes propriedades
• A face δ
´e uma aresta ( n˜ao apenas um v´ertice).
• O n´umero de coeficientes n˜ao determinados de g
δ
k
δ
´e n˜ao nulo mas estritamente
menor que o n´umero de pontos integrais sobre δ
.
• Todos os termos n˜ao determinados tˆem expoentes que s˜ao pontos integrais adjacentes
sobre a linha suportada por
δ
− (h
δ
− h
δ
) + k
δ
.
5 Fatorando via politopos 89
A figura 5.12 ilustra o lema 5.5.1.
Figura 5.12: Coeficientes indeterminados do polinˆomio gen´erico
Dem.: Come¸camos definindo o pol´ıgono
¯
Q como:
¯
Q := {r ∈ Q :
δ
(r) ≥ (h
δ
− h
δ
) + k
δ
∀δ ∈ Γ}
Note que os pontos inteiros em
¯
Q correspondem a coeficientes n˜ao de-
terminados em g. Como j´a mostramos Λ = ∅, assim, seja
¯
δ a face de
¯
Q suportada
por
δ
− ((h
δ
− h
δ
) − k
δ
) que, claramente, ´e paralela a δ
. Note que cada
¯
δ cont´em
pelo menos um ponto inteiro. Como
¯
δ ´e paralelo a δ
para todo δ ∈ Λ, ent˜ao a
sequˆencia de arestas
¯
δ
δ∈Λ
forma uma sequˆencia poligonal em Q. Assim,
δ
δ∈Λ
e
¯
δ
δ∈Λ
satisfazem as hip´oteses do lema 5.4.1. Portanto, existe no m´ınimo uma
aresta δ ∈ Λ tal que δ
tem estritamente mais pontos inteiros que
¯
δ. Esta aresta δ
tem as propriedades requeridas. Isto completa a prova.
Antes de apresentarmos o pr´oximo lema iremos definir o grau de um polinˆomio de
Laurent.
Defini¸c˜ao 5.5.2. Seja o polinˆomio de Laurent f =
a
i
z
i
∈ F[z] com i ∈ Z. Onde
o grau do polinˆomio de Laurent ´e a diferen¸ca entre o maior e o menor expoente, se
o polinˆomio ´e n˜ao-nulo, e −∞ caso contr´ario.
5 Fatorando via politopos 90
Exemplo 5.5.1. Seja o polinˆomio de Laurent f = 2z
−2
+1+3z +5z
7
∈ Z[z]. Ent˜ao
grau(f) = 7 − (−2) = 9.
Lema 5.5.2. Sejam f,Q,R e Γ como no enunciado do teorema 5.5.1. suponha que
tenhamos uma K-fatora¸c˜ao de f, onde K = (k
δ
)
δ∈Γ
. Al´em disso, assuma que esta
fatora¸c˜ao estende uma fatora¸c˜ao de arestas dominante coprima, isto ´e, os polinˆomios
g
δ
0
e h
δ
0
s˜ao coprimos sob fatores monomiais para todo δ ∈ Γ. Ent˜ao existe δ ∈ Γ
tal que os coeficientes de g
δ
k
δ
n˜ao est˜ao todos determinados, mas eles podem ser
determinados em no m´aximo um caminho consistente com as equa¸c˜oes 5.3. Esta
determina¸c˜ao pode ser computada em tempo polinomial em = Newt (f)
Dem.: Selecione δ ∈ Γ tal que as propriedades do lema 5.5.1 sejam satisfeitas.
Sejam n
δ
e m
δ
os n´umeros de pontos integrais sobre δ
e
¯
δ respectivamente, onde
δ
e
¯
δ est˜ao definidas como na prova do lema 5.5.1. Ent˜ao temos que n
δ
> m
δ
e
m
δ
≥ 1. Com a aresta δ podemos definir a fun¸c˜ao primitiva afim associada a δ como
δ
= γ
1
e
1
+ γ
2
e
2
− h
δ
, onde γ
1
e γ
2
s˜ao coprimos. Sejam z e w as novas vari´aveis.
Usando as transformadas
i
1
= e
1
ζ
2
− e
2
ζ
1
, e i
2
= e
1
γ
1
− e
2
γ
2
=
δ
(e
1
, e
2
) + h
δ
,
qualquer monˆomio da forma x
e
1
y
e
2
pode ser escrito como
x
e
1
y
e
2
= z
i
1
w
i
2
(5.6)
Todo monˆomio em g
δ
i
´e da forma x
e
1
y
e
2
onde
δ
(e
1
, e
2
) = h
δ
− h
δ
+ i. Sejam os
monˆomios s e t os termos de g e h respe ctivamente cujos expoentes vetoriais s˜ao os
v´ertices come¸co das faces de Q e R definidas por
δ
−(h
δ
−h
δ
) e
δ
+ (h
δ
−h
δ
) + h
δ
,
respectivamente (ou seja, os v´ertices come¸co de δ
e δ
, respectivamente). Ent˜ao
ap´os termos feito as mudan¸c as de vari´aveis chegamos a:
g
δ
i
(z, w) = sw
i
G
i
(z), h
δ
i
(z, w) = tw
i
H
i
(z) e f
δ
i
(z, w) = stw
i
F
i
(z),
onde G
i
(z), H
i
(z) e F
i
(z) s˜ao polinˆomios de Laurent univariados. Com esta cons-
tru¸c˜ao G
0
(z), H
0
(z) e F
0
(z) s˜ao polinˆomios ordin´arios, ou seja, que cont´em apenas
expoentes n˜ao negativos de z. Para i < k
δ
todos os coeficientes nos polinˆomios
5 Fatorando via politopos 91
G
i
(z) e H
i
(z) foram determinados. Al´em disso G
0
(z) ´e de grau n
δ
, e tamb´em
com excess˜ao de m
δ
coeficientes de G
k
δ
(z) to dos os outros foram deteminados(lema
5.5.1). Com esta mudan¸ca de vari´avel as equa¸c˜oes 5.3 podem ser escritas como
F
0
(z) = G
0
(z) F
0
(z), e para k ≥ 1 temos
G
k
(z) H
0
(z) + G
0
(z) H
k
(z) = F
k
(z) −
k−1
j=1
G
j
(z) H
k−j
(z)
Sabemos que todos os coeficientes de G
i
(z) e H
i
(z) foram determinados para 0 ≤
i < k
δ
em um caminho que come¸camos resolvendo F
0
= G
0
H
0
e as primeiras k
δ
−1
equa¸c˜oes acima. Ent˜ao precisamos resolver a equa¸c˜ao
G
k
δ
H
0
+ G
0
H
k
δ
= F
k
δ
−
k
δ
−1
j=1
G
j
H
k
δ
−j
. (5.7)
para os coeficientes indeterminados de G
k
δ
e H
k
δ
.
Primeiro calculamos, usando o algoritmo de Euclides estendido, polinˆomios
ordin´arios ´unicos U (z) e V (z) tais que
V (z) H
0
(z) + U (z) G
0
(z) = 1
com deg
z
(U (z)) < deg
z
(H
0
(z)) e deg
z
(V (z)) < deg
z
(G
0
(z)). Note que G
0
(z) e
H
0
(z) s˜ao coprimos j´a que temos uma fatora¸c˜ao coprima. Qualquer solu¸c˜ao G
k
δ
(z)
da equa¸c˜ao 5.7 deve ser da forma
G
k
δ
=
V
F
k
δ
−
k
δ
−1
j=1
G
j
H
k
δ
−j
mod G
0
+ G
0
(5.8)
para algum polinˆomio de Laurent (z) c om coeficientes indeterminados. Reescrevendo
5.8 temos
G
k
δ
−
V
F
k
δ
−
k
δ
−1
j=1
G
j
H
k
δ
−j
mod G
0
= G
0
(5.9)
Seja d o grau do polinˆomio de Laurent do lado esquerdo de 5.9. Sabemos que G
0
e
´e um polinˆomio ordin´ario, ou seja, com termos cujos expoentes s˜ao n˜ao negativos,
de grau n
δ
−1 e com termo constante n˜ao nulo pois corresponde a aresta δ
. Como
grau(G
o
) = n
δ
− 1 e G
0
n˜ao possui termos cujos expoentes s˜ao negativos ent˜ao
5 Fatorando via politopos 92
grau()G
0
≥ n
δ
− 1. Se d < n
δ
− 1 ent˜ao = 0. Se d ≥ n
δ
− 1 ent˜ao grau((z)) =
d −(n
δ
−1), logo (z) possui d −(n
δ
−1) + 1 coeficientes indeterminados. Sabemos
que G
k
δ
possui m
δ
coeficientes inde terminados e tem d −n
δ
+ 2 coeficientes todos
indeterminados. No lado esquerdo de 5.9 temos d + 1 termos, ent˜ao para G
k
δ
ser
poss´ıvel de ser determinado ´e necess´ario que d + 1 ≥ m
δ
+ d − n
δ
+ 2. Por hip´otese
m
δ
< n
δ
e assim d + 1 − m
δ
≥ d − n
δ
+ 2.
Como descobrir (z):
Como (z) tem grau d − (n
δ
+ 1) ent˜ao ele tem a seguinte forma:
(z) = a
0
z
a
+ a
1
z
a+1
+ ··· + a
d−(n
δ
−1)
z
a+d−(n
δ
−1)
d−n
δ
+2 coeficientes indeterminados
.
Como descobrir a?
Note que G
0
possui termo constante n˜ao nulo, pois este corresponde a
um v´ertice de Q, fator do Newt(f). E do mesmo modo como foi feito para , G
0
tem a seguinte forma:
G
0
(z) = c
0
+ c
1
z
1
+ ··· + c
n
δ
−1
z
n
δ−1
n
δ
termos
.
Ent˜ao G
0
= c
0
a
0
z
a
+ ··· e assim podemos encontrar a igualando este termo ao
termo de mais baixo grau no lado esquerdo de 5.9.
Calculando os coeficientes indeterminados
Seja q = grau(G
k
δ
).Sabemos que os m
δ
coeficientes indeterminados de
G
k
δ
correspondem a termos adjacentes. Vamos supor que os r termos mais baixos
de G
k
δ
tiveram seus coeficientes determinados e assim os (q + 1) − (m
δ
+ r) mais
altos termos tamb´em. Ent˜ao G
k
δ
tem a seguinte forma:
G
K
δ
= b
0
z
b
+ b
1
z
b+1
+ ··· + b
r−1
z
b+r−1
r termos determinados
+ b
r
z
b+r
+ ··· + b
r+m
δ
−1
z
b+r+m
δ
−1
m
δ
termos indeterminados
+ b
r+m
δ
z
b+r+m
δ
+ ··· + b
q
z
b+q
(q+1)−(r+m
δ
) termos determinados
.
5 Fatorando via politopos 93
a qual nos leva a um sistema triangular. Podemos resolver para os r mais baixos
termos de igualando ambos os termos em 5.8. O mesmo pode ser feito para os
coeficientes dos (q + 1) − (m
δ
+ r) termos mais altos.
Quando o sistema pode n˜ao ter solu¸c˜ao ?
No caso em que d + 1 − m
δ
> d − n
δ
+ 2, isto ´e, quando n
δ
> m
δ
+ 1
os sis temas podem n˜ao ter solu¸c˜ao em comum. Neste caso pode n˜ao haver solu¸c˜ao
para a equa¸c˜ao 5.8 e ent˜ao, como ser´a explicado posteriormente, iremos para outra
aresta coprima do conjunto dominante irreduntante e faremos o mesmo sistema.
Se existir um (z) que satisfa¸ca 5.9 ent˜ao os coeficientes indetermina-
dos de G
k
δ
podem ser determinados. Tendo computado a solu¸c˜ao de 5.9 para G
k
δ
podemos substituir em 5.7 e descobrir H
k
δ
. Ou seja, computar
(F
k
δ
−
k
δ
−1
j=1
G
j
H
k
δ
−j
) − G
k
δ
H
0
G
0
.
Isto completa a prova.
Para provarmos o teorema 5.5.1 precisamos mostrar se `a decomp osi¸c˜ao
dada, Newt(f) = Q + R, corresponde ou n˜ao a uma fatora¸c˜ao f = gh do polinˆomio.
De acordo com o lema 5.5.1 sempre existe uma aresta do conjunto dominante irre-
dundante Γ que pode ser levantada, ou seja, que os coeficientes dos termos cujos
expoentes vetoriais est˜ao sobre ela podem ser determinados. No lema 5.5.2 obser-
vamos como esse levantamento ´e feito.
Quando escolhemos uma aresta de Γ que satisfa¸ca as condi¸c˜oes do lema
5.5.1 para fazermos o levantamento, este nos leva a um sistema nas indeterminadas g
q
que pode ou n˜ao ter solu¸c˜ao. Se o sistema tem solu¸c˜ao continuamos o levantamento.
Por´em, se o sistema n˜ao tem solu¸c˜ao vamos para outra aresta de Γ que satisfa¸ca o
lema 5.5.1 e tentamos fazer o levantamento. Se todas as aresta de Γ levam a sistemas
que n˜ao possuem solu¸c˜ao ent˜ao o levantamento n˜ao p ode continuar e podemos dizer
que a decomposi¸c˜ao do Newt(f) dada n˜ao corresponde a uma fatora¸c˜ao f = gh do
polinˆomio.
5 Fatorando via politopos 94
Se conseguirmos fazer o levantamento at´e o final ent˜ao teremos deter-
minado todas as indeterminadas g
q
e h
r
, ou seja, teremos dois polinˆomios g e h
que correspondem `a decomposi¸c˜ao do Newt(f) dada e que s˜ao candidatos a uma
fatora¸c˜ao f = gh . Um teste de divis˜ao simples pode verificar se, de fato, g e h s˜ao
fatores de f.
Para um maior esclarecimento do que foi discutido recomendamos uma
leitura do apˆendice B e do exemplo 5.5.2 que consta no final do presente cap´ıtulo.
O algoritmo
Algoritmo 5.5.1.
Entra da: Um polinˆomio f ∈ F[x, y].
Sa´ıda: Uma fatora¸c˜ao de f ou falhou.
1. Passo: Calcular um conjunto dominante irredundante Γ do Newt(f).
Para esta escolha de Γ, calcular todas (Γ; Q, R)−fatora¸c˜oes parciais co-
primas de f, isto ´e, calcular todas as fatora¸c˜oes parciais coprimas rel-
ativas aos fatores Q e R e o conjunto dominante Γ. Note que, Q e R
variam sobre todos os pares de fatores tais que Newt(f) = Q + R.
2. Passo: Aplicando repetidamente o m´etodo usado na prova do lema
5.5.2, levante cada fatora¸c˜ao de arestas dominante coprima tanto quanto
poss´ıvel. Se qualquer um destes levantamentos levar a uma fatora¸c˜ao
completa ent˜ao retorne esta fatora¸c˜ao e pare o algoritmo. Se nenhum
deles levar a uma fatora¸c˜ao completa ent˜ao retorne falhou.
O algoritmo sempre funcionar´a quando come¸car com um conjunto do-
minante irredundante Γ do Newt(f) tal que todos os polinˆomios f
δ
0
, para todo δ ∈ Γ,
s˜ao livres de quadrado sob fatores monomiais.
Podemos dizer que quando o algoritmo retornar falhou ent˜ao o polinˆomio
f ´e irredut´ıvel, pois ele testa todos os pares de fatores do Newt(f) para ver se al-
gum deles leva a uma fatora¸c ˜ao de f. Ou seja, se o algoritmo retornar falhou e
5 Fatorando via politopos 95
f = gh ent˜ao ter´ıamos uma decomposi¸c˜ao P
f
= P
g
+ P
h
. Como o algoritmo faz o
levantamento para todos pares de fatores do Newt(f) este deveria ter obtido sucesso.
Caso contr´ario o algoritmo retornar´a um candidato a fator do polinˆomio
f.
Exemplo 5.5.2. Neste exemplo vamos fatorar o polinˆomio f = x
2
+ y
2
+ x
3
+ x
3
y
2
via politopos nos n´umeros inteiros. Observe que, como visto no exemplo 5.4.1, o
conjunto Γ = {δ
1
, δ
2
}, onde δ
1
vai do v´ertice (0, 2) ao (2, 0) e δ
2
vai do v´ertice (2, 0)
ao (3, 0), ´e um conjunto dominante irredundante do Newt(f) na dire¸c˜ao r = (1, 1).
Note que f
δ
1
0
= x
2
+ y
2
, f
δ
1
1
= x
3
, f
δ
1
2
= 0, f
δ
1
3
= x
3
y
2
, g
δ
1
0
= g
02
y
2
+ g
11
xy + g
20
x
2
,
g
δ
1
1
= g
21
x
2
y + g
12
xy
2
, g
δ
1
2
= g
22
x
2
y
2
, h
δ
1
0
= h
00
, h
δ
1
1
= h
10
x. Fazendo a mudan¸ca de
vari´avel temos: F
δ
1
0
= z
2
+ 1, F
δ
1
1
= z
2
, F
δ
1
2
= 0, F
δ
1
3
= 1, G
δ
1
0
= g
02
+ g
11
z + g
20
z
2
,
G
δ
1
1
= g
21
z + g
12
, G
δ
1
2
= g
22
, H
δ
1
0
= h
00
, H
δ
1
1
= h
10
.
De acordo com o lema 5.5.2 temos que
F
δ
1
0
= G
δ
1
0
H
δ
1
0
,
ou seja,
z
2
+ 1 = (g
02
+ g
11
z + g
20
z
2
)(h
00
).
Resolvendo o sistema encontramos g
11
= 0, g
02
= 1, g
20
= 1 e h
00
= 1. Que leva a
G
δ
1
0
= z
2
+ 1 e H
δ
1
0
= 1. Observe, que neste momento, determinamos os coeficientes
sobre a reta
δ
1
= 0.
Figura 5.13: coeficientes determinados sobre a reta
δ
1
= 0
5 Fatorando via politopos 96
Note que a aresta δ
1
tem as propriedades necess´arias de acordo com o lema 5.5.1,
logo, esta pode ser levantada. Ou seja, n
δ
1
= 3 e m
δ
1
= 2 conforme pode ser
observado na figura 5.13. Calculamos V = 1 e U = 0. Precisamos resolver
G
δ
1
1
− {V (F
δ
1
1
) mod G
δ
1
0
} = G
δ
1
0
,
ou seja,
(g
21
z + g
12
) − (−1) = G
δ
1
0
.
Note que d = 1 e n
δ
1
−1 = 2, ent˜ao = 0. E assim, resolvendo o sistema, chegamos
a g
21
= 0 e g
12
= −1. Logo, G
δ
1
1
= −1. Agora, calculamos H
δ
1
1
. Chegamos a h
10
= 1
e assim H
δ
1
1
= 1. Observe, que neste momento, determinamos os coeficientes sobre
a reta
δ
1
= 1.
Figura 5.14: coeficientes determinados sobre a reta
δ
1
= 1
Note que a aresta δ
1
tem as propriedades necess´arias de acordo com o lema 5.5.1,
logo, esta pode ser levantada. Ou seja, n
δ
1
= 3 e m
δ
1
= 1 conforme pode ser
observado na figura 5.14. Agora, vamos calcular G
δ
1
2
. Precisamos resolver o seguinte
sistema
G
δ
1
2
− {V (F
δ
1
2
− G
δ
1
1
H
δ
1
1
) mod G
δ
1
0
} = G
δ
1
0
,
ou seja,
g
22
− 1 = (z
2
+ 1).
Note que d = 0. Ent˜ao = 0.Resolvendo o sistema, obtemos g
22
= 1. Logo, G
δ
1
2
= 1.
Observe, que neste momento, determinamos os coeficientes sobre a reta
δ
1
= 2.
5 Fatorando via politopos 97
Figura 5.15: coeficientes determinados sobre a reta
δ
1
= 2
Fatorando via politopos encontramos
x
2
+ y
2
+ x
3
+ x
3
y
2
= (x
2
+ y
2
− xy
2
+ x
2
y
2
)(1 + x).
98
6 CONCLUS
˜
AO
Possivelmente nossa maior contribuic˜ao presente nesta disserta¸c˜ao seja
o seu texto, em portuguˆes, sobre pesquisas recentes que ligam geometria `a fatora¸c˜ao
de polinˆomios, um tema inicialmente alg´ebrico. M ais especificamente, estudamos
decomposi¸c˜ao de politopos e suas aplica¸c˜oes na fatora¸c˜ao de polinˆomios.
No cap´ıtulo 2 apresentamos um apanhado de resultados acerca de con-
juntos convexos, es pecificamente politopos, que deram base para os cap´ıtulos poste-
riores. Estudamos as consequˆencias que um politopo integralmente indecomp on´ıvel
tem sobre os polinˆomios. Ou seja, estudamos constru¸c˜oes de politopos integralmente
indecompon´ıveis que levam a crit´erios de irredutibilidade de polinˆomios.
Os algoritmos sobre decomponibilidade e indecomponibilidade de poli-
topos, que nos trabalhos originais estavam obscuros, foram descritos detalhadamente
no cap´ıtulo 4, sempre ilustrados com exemplos e coment´arios sobre suas poss´ıveis
aplica¸c ˜oes.
Enquanto a disserta¸c˜ao estava sendo feita, uma pergunta continuava
em aberto: Podemos fatorar o p olinˆomio f via a decomposi¸c˜ao do seu politopo de
Newton associado, ou seja, se Newt(f) = Q + R existe um fator g do polinˆomio f
cujo politopo de Newton associado ´e dado por Q.
Em 2004 a quest˜ao foi respondida. Fatima Abu Salem, Shuhong Gao e
Alan G. B. Lauder desenvolveram um algoritmo derivado do m´etodo de Hensel para
fatorar polinˆomios bivariados a partir da decomposi¸c˜ao do seu politopo de Newton
associado.
Depois de termos estudado todos estes problemas, podemos concluir
que, em um certo sentido, todas as perguntas envolvendo o politopo de newton
associado de um polinˆomio f foram respondidas. Isto ´e, se o politopo de Newton
associado ao polinˆomio f for integralmente indecompon´ıvel ent˜ao f ser´a absoluta-
6 Conclus˜ao 99
mente irredut´ıvel.
´
E bom relembrar, como pode ser visto no exemplo 4.4.5, que
mesmo o politopo de Newton associado a f sendo integralmente decompon´ıvel f
pode ou n˜ao ser redut´ıvel. No entanto, podemos procurar um fator do polinˆomio
via politopos, gra¸cas ao algoritmo apresentado aqui. Naturalmente que ainda h´a
problemas a serem resolvidos nesse ciclo, em particular, na busca de melhorias que
tornem os algoritmos mais eficientes
Como trabalho a ser feito a partir desta disserta¸c˜ao, acreditamos que
possamos contribuir efetivamente para uma melhor compreens˜ao da ´area. Especi-
ficamente, queremos construir fam´ılias de polinˆomios esparsos em F[x
1
, . . . , x
n
] que
quando reduzidos para F[x, y] continuem esparsos e, assim, usarmos o levantamento
via politopos para sua fatora¸c˜ao.
100
BIBLIOGRAFIA
[1] Aho, A. V., Hopcroft, J. E., and Ullman, J. D. The Design and
Analysis of Computer Algorithms. Addison Wesley, 1974.
[2] Baase, S. Computer Algorithms: Introduction to Design and Analysis.
Addison-Wesley, 1988.
[3] Ewald, G. Combinatorial Convexity and Algebraic Geometry, GTM 168.
Springer, 1996.
[4] Gao, S. Absolute irreducibility of polynomials via newton polytopes. J.
of Algebra 237 (2001), 501–520.
[5] Gao, S. Factoring mutivariate polynomials via partial differential equa-
tions. Mathematics of Computation 72 (2003), 801–822.
[6] Gao, S., and Lauder, A. Decomposition of polytopes and polynomials.
Discrete and Computational Geometry 26 (2001), 89–104.
[7] Gao, S., and Lauder, A. G. Hensel lifting and bivariate polynomial
factorisation over finite fields. Mathematics of Computation 71 (2002),
1663–1676.
[8] Gao, S., and Lauder, A. G. Fast absolute irreducibility testing via
newton polytopes. Pre print (2004), 1–13.
[9] Gathen, J. V. Z., and Gerhard, J. Modern Computer Algebra. Cam-
bridge University Press, 1999.
[10] Grahan, R. L. An efficient algorithm for determining the convex hull of
a finite planar set. Information Processing Letters 1 (1972), 132–133.
[11] Gr
¨
unbaum, B. Convex Polytopes. Graduate Texts in Mathemat-
ics,Springer, 2003.
Referˆencias Bibliogr´aficas 101
[12] Hilbert, D.
¨
Uber die irreducibilit¨at rationaler functionen mit ganzzahli-
gen coefficientes. Journal f¨ur die Reine und Angewandte Mathematik 110
(1892), 104–129.
[13] Hoppen, C. Uma Generaliza¸c˜ao do Algoritmo de Gao para Fatora¸c˜ao
de Polinˆomios. Disserta¸c˜ao de Mestrado - PPG Matem´atica Aplicada -
UFRGS, 2004.
[14] Kalai, G., and Ziegler, G. M. Polyto pes-Combinatorics and Compu-
tation. Birkh¨auser, 2000.
[15] Kaltofen, E. Effective noether irreducibility forms and aplications.
Journal of Computer and System Sciences 50 (1995), 274–295.
[16] Ostrowski, A. M.
¨
Uber die bedeutung der theorie der konvexen polyeder
f¨ur die formale algebra. Jahresberichte Deutsche Math. 30 (1921), 98–99.
[17] Rourke, J. O. Computational Geometry in C. Cambridge University
Press, 1998.
[18] Salem, F. A., Gao, S., and Lauder, A. G. Factoring polynomials
via polytopes. Proceeding of ISSAC 2004 (2004), 4–11.
[19] Salem, F. A., Gao, S., and Lauder, A. G. Factoring polynomials via
polytopes: Extended version. Report PRD-RR -04-07 Oxford University
Computing Laboratory (2004).
[20] Schneider, R. Convex bodies: the Brunn-Minkowski theory - Encycople-
dia of Mathematics and its Applications. Cambridge, 1993.
[21] Smilansky, Z. An indecomposable polytope all of whose facets are de-
composable. Mathematika 33, 2 (1986), 192–196.
[22] Trevisan, V. Polynomial factorization ii. Mathematica Contemporˆanea
7 (1994), 185–198.
Referˆencias Bibliogr´aficas 102
[23] Zassenhauss, H. On hensel factorization, i. Journal of Numberr Theory
1 (1969), 291–311.
[24] Ziegler, G. M. Lectures on Polytopes. Graduate Texts in Mathematics,
Springer, 1995.
103
AP
ˆ
ENDICE A LEVANTAMENTO DE
HENSEL
Neste apˆendice estudaremos as id´eias b´asicas do levantamento de Hensel
que podem ser encontradas na literatura em [9, 7, 22], pois precisaremos delas
quando estivermos estudando o algoritmo de fatora¸c˜ao de polinˆomios via polito-
pos.
Denote T (n, q) o conjunto de todos os polinˆomios em F
q
[x, y] de grau
total n que s˜ao mˆonicos em x e tem grau n em x. Seja f ∈ T (n, q) com f = gh
onde g, h ∈ F
q
[x][[y]] s˜ao s´eries de potˆencia n˜ao constante. Diremos que f = gh ´e
uma fatora¸c˜ao anal´ıtica de f no ideal primo gerado por y. Se ambos g e h est˜ao no
subanel F
q
[x, y] ent˜ao nos referimos a f = gh como uma fatora¸c˜ao polinomial de f.
Toda fatora¸c˜ao anal´ıtica de f pode, em princ´ıpio, ser encontrada usando pol´ıgonos
de Newton e uma forma de levantamento Hensel com resp eito ao ideal primo (y).
Suponha que f = gh para certas s´eries de potˆencia g, h ∈ F
q
[x][[y]]. Primeiro de
tudo devemos examinar como os coeficientes de f,g e h s˜ao descritos como expans˜oes
em y. Seja f =
n
k=0
f
k
y
k
, g =
k≥0
g
k
y
k
e h =
k≥0
h
k
y
k
. Aqui f
k
,g
k
,h
k
∈ F
q
[x].
J´a que f mod y = gh mod y ent˜ao temos que f
0
= g
0
h
0
. Igualando os coeficientes
de y
k
para k ≥ 1 em ambos os lados de f = gh vemos que
f
1
= g
0
h
1
+ g
1
h
0
f
2
= g
0
h
2
+ g
1
h
1
+ g
2
h
0
.
.
.
.
.
.
.
.
.
f
k
=
k
i=0
g
i
h
k−i
.
.
.
.
.
.
.
.
.
Ent˜ao para k ≥ 1 temos que
g
0
h
k
+ g
k
h
0
= f
k
−
k−1
i=1
g
i
h
k−i
. (A.1)
B Apˆendice 104
Agora, seja d = mdc(g
0
, h
0
) com u e v escolhidos de tal forma que ug
0
+ vh
0
= d e
grau(u) < grau(h
0
), grau(v) < grau(g
0
). Ent˜ao d divide o lado direito da equa¸c˜ao
e vemos que g
k
e h
k
devem ser da forma
g
k
= v
f
k
−
k−1
i=1
g
i
h
k−i
d
+ ω
k
g
0
d
(A.2)
h
k
= u
f
k
−
k−1
i=1
g
i
h
k−i
d
− ω
k
h
0
d
(A.3)
para algum polinˆomio ω
k
∈ F
q
[x]. Ent˜ao obtemos equa¸c˜oes que descrevem os co-
eficientes f
k
, g
k
e h
k
das expans˜oes de f,g e h respectivamente. Considere agora
a situa¸c˜ao na qual temos um polinˆomio f =
n
k=0
f
k
y
k
e uma fatora¸c˜ao f
0
=
g
0
h
0
∈ F[x].
´
E poss´ıvel usar as equa¸c˜oes A.2 e A.3 para definir uma sequˆencia de
polinˆomios {g
k
}
k≥0
e {h
k
}
k≥0
tal que g =
k≥0
g
k
y
k
e h =
k≥0
h
k
y
k
satisfa¸cam
f = gh mod y
n+1
? A resposta ´e sim, desde que a cada est´agio ω
k
´e escolhido tal
que d, o m´aximo divisor comum de g
0
e h
0
, divide o polinˆomio f
k
−
k−1
i=1
g
i
h
k−i
.
Se d = mdc(g
0
, h
0
) = 1 ent˜ao a escolha de ω
k
pode n˜ao ser ´unica, logo resultando
em muitas escolhas para g
k
’s e h
k
’s. Se d = mdc(g
0
, h
0
) = 1, a equa¸c˜ao A deter-
mina unicamente g
k
e h
k
quando grau(g
k
) < grau(h
0
) e grau(h
k
) < grau(g
0
). Isto
significa que o levantamento pode ser feito de maneira ´unica.
Estamos interessados em fatora¸c˜ao polinomial mais que em fatora¸c˜ao
anal´ıtica arbitr´aria e assim mais algumas observa¸c˜oes podem ser feitas. Suponha
que tenhamos uma fatora¸c˜ao f = gh. Al´em disso, assumimos que f,g e h est˜ao em
F
q
[x, y] e n = grau(f), r = grau(g) e s = grau(h). Ent˜ao r + s = n. Por isso
para 0 ≤ k ≤ n temos grau(g
k
) ≤ r − k e grau(h
k
) ≤ s − k. Isto significa que g
k
e h
k
deveriam ser zero nos casos em que r − k e s − k s˜ao menores do que zero,
respectivamente.
Suponha agora que tenhamos um polinˆomio f ∈ F
q
[x, y] e uma fa-
tora¸c˜ao f
0
= g
0
h
0
onde f =
n
k=0
f
k
y
k
e g
0
e h
0
s˜ao polinˆomios em F
q
[x] com
grau(g
0
) = r, grau(h
0
) = s. Desejamos levantar esta fatora¸c˜ao para F
q
[x, y].
Quando usarmos as equa¸c˜oes A.2 e A.3 para definirmos os polinˆomios g
k
e h
k
deve-
mos escolher ω
k
com condi¸c˜oes apropriadas sobre os graus. No caso que grau(f
0
) = n
B Apˆendice 105
as restri¸c˜oes s˜ao grau(g
k
) < r − k e grau(h
k
) ≤ s − k. Quando mdc(g
0
, h
0
) = 1
existir´a no m´aximo um modo disto ser feito. Defina g
k
e h
k
pelas equa¸c˜oes
g
k
= v(f
k
−
k−1
i=1
g
i
h
k−i
) mod g
0
(A.4)
h
k
= u(f
k
−
k−1
i=1
g
i
h
k−i
) mod h
0
(A.5)
e ent˜ao cheque que grau(g
k
) ≤ r − k e grau(h
k
) ≤ s − k.
Para n ≥ 1, seja M(n, q) ⊆ T (n, q) o subconjunto de todos os polinˆomios
cuja redu¸c˜ao m´odulo y ´e livre de quadrados.
Algoritmo A.0.2 (Levantamento de Hensel). Entrada: Um polinˆomio f =
n
k=0
f
k
y
k
em M(n, q), onde f
k
∈ F
q
[x]. Sa´ıda: Todos os fatores mˆonicos de f com
grau total entre 1 e n/2.
Passo 1: Usar um algoritmo de fatora¸c˜ao polinomial univariada para
fatorar f
0
, um polinˆomio livre de quadrados. Se f
0
´e irredut´ıvel ent˜ao pare o algo-
ritmo. Por isso, assuma que f
0
´e redut´ıvel. Listar todos os pares (g
0
, h
0
) de fatores
mˆonicos com f
0
= g
0
h
0
e 1 ≤ grau(g
0
) ≤ grau(h
0
). Para cada par (g
0
, h
0
), fa¸ca os
passos 2 − 4 onde r = grau(g
0
) logo 1 ≤ r ≤ n/2.
Passo 2: Computar polinˆomios u e v com ug
0
+ vh
0
= 1 e grau(u) <
grau(h
0
), grau(v) < grau(g
0
).
Passo 3: Para k de 1 at´e n/2, computar
g
k
= v
f
k
−
k−1
i=1
g
i
h
k−i
mod g
0
(A.6)
e
h
k
= u
f
k
−
k−1
i=1
g
i
h
k−i
mod h
0
(A.7)
No caso que r ≥ k cheque que grau(g
k
) ≤ r − k, e no caso que k > r
cheque de qualquer forma g
k
= 0. Se uma dessas duas condi¸c˜oes n˜ao for satisfeita
ent˜ao pare a computa¸c˜ao para este par.
B Apˆendice 106
Passo 4: cheque que g :=
r
k=0
g
k
y
k
divide f. Se sim ent˜ao retorne g.
Esta ´e a essˆencia do levantamento de Hensel para fatorar polinˆomios, e
uma prova de sua corretude segue facilmente do que j´a foi discutido.
107
AP
ˆ
ENDICE B EXEMPLO DE FATORAC¸
˜
AO
VIA POLITOPOS
Exemplo B.0.3. Neste exemplo vamos fatorar o polinˆomio f = (x
8
+ x
4
)y
6
+ (x
7
+
x
4
+x
8
)y
5
+(x
8
+2x
6
+2x
4
+2x
10
+x
7
+2x
2
)y
4
+(x
2
+2x
7
+x
4
+x
10
+x
5
+x
9
)y
3
+(x
7
+
2x
8
+x
12
+x
10
+1+3x
4
+x
6
+2x
2
)y
2
+(x
9
+x
5
+x
7
+x
8
+x
4
)y+x
4
+2x
6
+x
10
+x
2
+x
8
,
cujo politopo de Newton associado ´e dado pela figura B.1, via politopos.
Figura B.1: politopo de Newton associado a f
Usando o algoritmo 4.4.2 encontramos as decomposi¸c˜oes integrais de P
f
tais que
P
f
= P
g
+ P
h
. Escolhemos a decomposi¸c˜ao dada pelas figuras B.2 para g e B.3 para
h.
Ent˜ao os polinˆomios gen´ericos associados a B.2 e B.3 s˜ao, respective-
mente: g := g
20
x
2
+ g
30
x
3
+ g
40
x
4
+ g50x
5
+ g
60
x
6
+ g
11
x
1
y
1
+ g
21
x
2
y + g
31
x
3
y +
g
41
x
4
y + g
51
x
5
y + g
61
x
6
y + g
71
x
7
y + g
02
y
2
+ g
12
xy
2
+ g
22
x
2
y
2
+ g
32
x
3
y
2
+ g
42
x
4
y
2
+
g
52
x
5
y
2
+ g
62
x
6
y
2
+ g
72
x
7
y
2
+ g
82
x
8
y
2
+ g
13
xy
3
+ g
23
x
2
y
3
+ g
33
x
3
y
3
+ g
43
x
4
y
3
+
g
53
x
5
y
3
+ g
63
x
6
y
3
+ g
73
x
7
y
3
+ g
24
x
2
y
4
+ g
34
x
3
y
4
+ g
44
x
4
y
4
+ g
54
x
5
y
4
+ g
64
x
6
y
4
e
h := h
00
+ h
10
x + h
20
x
2
+ h
30
x
3
+ h
40
x
4
+ h
11
xy + h
21
x
2
y + h
31
x
3
y + h
22
x
2
y
2
.
Seja δ
1
a aresta do newt(f) que vai do v´ertice (0, 2) ao v´ertice (2, 0),
δ
2
a aresta do newt(f) que vai do v´ertice (2, 0) ao v´ertice (10, 0) e δ
3
a aresta do
B Apˆendice 108
Figura B.2: politopo de Newton P
g
associado ao polinˆomio gen´erico g
Figura B.3: politopo de Newton P
h
associado ao polinˆomio gen´erico h
newt(f) que vai do v´ertice (10, 0) ao v´ertice (12, 2). Note que Γ = {δ
1
, δ
2
, δ
3
} ´e um
conjunto dominante irredundante do Newt(f) na dire¸c˜ao r = (0, 1), conforme pode
ser observado na figura B.4.
Agora, para δ
1
, vamos calcular as f
δ
1
i
(x, y) para i ≥ 0. Note que, os termos de f
δ
1
i
s˜ao os termos do polinˆomio f cujos expoentes vetoriais est˜ao sobre a reta
δ
1
= i.
f
δ
1
0
(x, y) = x
2
+ y
2
,
f
δ
1
1
(x, y) = 0,
f
δ
1
2
(x, y) = 2x
2
y
2
+ x
4
,
f
δ
1
3
(x, y) = x
2
y
3
+ x
4
y,
f
δ
1
4
(x, y) = 2x
6
+ 2x
2
y
4
+ 3x
4
y
2
+ x
5
y,
B Apˆendice 109
Figura B.4: conjunto dominante irredundante do Newt(f)
f
δ
1
5
(x, y) = x
4
y
3
,
f
δ
1
6
(x, y) = x
8
+ x
6
y
2
+ x
7
y + 2x
4
y
4
+ x
5
y
3
,
f
δ
1
7
(x, y) = x
8
y + x
4
y
5
+ x
7
y
2
,
f
δ
1
8
(x, y) = x
10
+ x
4
y
6
+ x
9
y + 2x
8
y
2
+ 2x
6
y
4
+ 2x
7
y
3
,
f
δ
1
9
(x, y) = x
7
y
4
,
f
δ
1
10
(x, y) = x
10
y
2
+ x
9
y
3
+ x
7
y
5
+ x
8
y
4
,
f
δ
1
11
(x, y) = x
10
y
3
+ x
8
y
5
e
f
δ
1
12
(x, y) = x
12
y
2
+ x
8
y
6
+ 2x
10
y
4
.
Observe que os g
δ
1
i
e h
δ
1
i
s˜ao obtidos do mesmo modo. Fazendo as mudan¸cas de
vari´avel descritas no lema 5.5.2 para δ
1
, obtemos:
F
δ
1
0
= 1 + z
2
,
F
δ
1
1
= 0,
F
δ
1
2
= 2 + z
2
,
F
δ
1
3
= z
−1
+ z,
F
δ
1
4
= 2z
2
+ 2z
−2
+ 3 + z,
F
δ
1
5
= z
−1
,
F
δ
1
6
= z
2
+ 1 + z + 2z
−2
+ z
−1
,
B Apˆendice 110
F
δ
1
7
= z + z
−3
+ 1,
F
δ
1
8
= z
2
+ z
−4
+ z + 2 + 2z
−2
+ 2z
−1
,
F
δ
1
9
= z
−2
,
F
δ
1
10
= 1 + z
−1
+ z
−3
+ z
−2
,
F
δ
1
11
= z
−1
+ z
−3
e
F
δ
1
12
= 1 + z
−4
+ 2z
−2
.
Note que esta mudan¸ca de vari´avel funciona do mesmo jeito para os polinˆomiuos
gen´ericos g e h. Assim como, a mudan¸ca de vari´avel das arestas δ
2
e δ
3
seguem de
modo similar.
Agora estamos prontos para come¸car a fatora¸c˜ao do polinˆomio f via
politopos sobre os n´umeros inteiros.
Passo 1 do algoritmo 5.5.1
Come¸camos calculando G
δ
0
e H
δ
0
para as arestas do conjunto dominante
irredundante.
Calculando para δ
1
:
F
δ
1
0
= G
δ
1
0
H
δ
1
0
.
(1 + z
2
) = (g
20
z
2
+ g
11
z + g
02
)(h
00
). (B.1)
Note que g
20
= 0, g
02
= 0 e h
00
= 0, pois correspondem a v´ertices dos pol´ıgonos
P
g
e P
h
. Resolvendo o sistema que obtemos quando igualamos os coeficientes dos
polinˆomios de z em ambos os lados da equa¸c˜ao B.1, obtemos: g
11
= 0, g
20
= 1,
h
00
= 1 e g
02
= 1. Logo,
G
δ
1
0
= z
2
+ 1 e H
δ
1
0
= 1.
Conforme pode ser observado na figura B.5, neste momento acabamos de determinar
os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais est˜ao
sobre a reta
δ
1
= 0.
B Apˆendice 111
Figura B.5:
δ
1
= 0
Calculando para δ
2
:
F
δ
2
0
= G
δ
2
0
H
δ
2
0
(1+z
2
+2z
4
+z
6
+z
8
) = (1+g
30
z+g
40
z
2
+g
50
z
3
+g
60
z
4
)(1+h
10
z+h
20
z
2
+h
30
z
3
+h
40
z
4
)
(B.2)
Note que g
60
= 0 e H
40
= 0. Resolvendo o sistema que obtemos quando igualamos os
coeficientes dos polinˆomios de z em ambos os lados da equa¸c˜ao B.2, temos: g
30
= 0,
g
40
= 0, g
50
= 0, g
60
= 1, h
10
= 0, h
20
= 1, h
30
= 0 e h
40
= 1. Logo:
G
δ
2
0
= 1 + z
4
e H
δ
2
0
= 1 + z
2
+ z
4
.
Conforme pode ser observado na figura B.6, neste momento acabamos de determinar
os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais est˜ao
sobre a reta
δ
2
= 0.
Calculando para δ
3
:
F
δ
3
0
= G
δ
3
0
H
δ
3
0
(1 + z
2
) = (1 + g
71
z + g
82
z
2
)(1) (B.3)
B Apˆendice 112
Figura B.6:
δ
2
= 0
Note que g
82
= 0. Resolvendo o sistema que obtemos quando igualamos os coefi-
cientes de z em B.3, obtemos: g
71
= 0 e g
82
= 1. Logo,
G
δ
3
0
= 1 + z
2
e H
δ
3
0
= 1.
Conforme pode ser observado na figura B.7, neste momento acabamos de determinar
os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais est˜ao
sobre a reta
δ
3
= 0.
Figura B.7:
δ
3
= 0
B Apˆendice 113
Passo 2 do algoritmo 5.5.1
Neste momento observe que de acordo com a figura B.7 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 2 m
δ
2
= 5 m
δ
3
= 2
De acordo com o lema 5.5.1 as arestas δ
1
e δ
2
podem ser levantadas. Escolhemos δ
1
para iniciar o levantamento. Vamos calcular V
δ
1
e U
δ
1
tais que
V
δ
1
H
δ
1
0
+ U
δ
1
G
δ
1
0
.
Encontramos:
V
δ
1
= 1 e U
δ
1
= 0.
Vamos calcular G
δ
1
1
= g
21
z + g
12
m
δ
1
=2
.
G
δ
1
1
− {V
δ
1
(F
δ
1
1
) mod G
δ
1
0
} = G
δ
1
0
.
(g
21
z + g
12
d=1
) = (1 + z
2
) (B.4)
Como d = 1 < n
δ
1
−1 = 2 ent˜ao = 0. Igualando os polinˆomios em B.4 e resolvendo
o sistema obtemos g
21
= 0 e g
12
= 0. Temos que:
G
δ
1
1
= 0 e H
δ
1
1
= 0.
Conforme pode ser observado na figura B.8, neste momento acabamos de determinar
os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais est˜ao
sobre a reta
δ
1
= 1.
Neste momento observe que de acordo com a figura B.8 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 3 m
δ
2
= 4 m
δ
3
= 2
B Apˆendice 114
Figura B.8:
δ
1
= 1
Ent˜ao, de acordo com o lema 5.5.1, as arestas δ
2
e δ
3
podem ser levantadas. Es-
colhemos a aresta δ
2
. Vamos calcular G
δ
2
1
= g
31
z + g
41
z
2
+ g
51
z
3
+ g
61
z
4
m
δ
2
=4
. Temos
que:
V
δ
2
= −z
2
e U
δ
2
= 1 + z
2
.
Vamos resolver:
G
δ
2
1
− {V
δ
2
(F
δ
2
1
) mod G
δ
2
0
} = G
δ
2
0
.
g
31
z + g
41
z
2
+ (g
51
− 1)z
3
+ g
61
z
4
d=3
= (1 + z
4
) (B.5)
Como d = 3 < n
δ
2
− 1 = 4 ent˜ao = 0. Igualando os polinˆomios em B.5 e
resolvendo o sistema obtemos g
31
= 0, g
41
= 0, g
51
= 1 e g
61
= 0. Logo G
δ
2
1
= z
3
.
Vamos calcular H
δ
2
1
= h
11
z + h
21
z
2
+ h
31
z
3
.
H
δ
2
1
=
F
δ
2
1
− G
δ
2
1
H
δ
2
0
G
δ
2
0
= z
2
.
h
11
z + h
21
z
2
+ h
31
z
3
= z
2
. (B.6)
Igualando os polinˆomios em B.6 obtemos: h
11
= 0, h
21
= 1 e h
31
= 0. Temos que
G
δ
2
1
= z
3
e H
δ
2
1
= z
2
.
Conforme pode ser observado na figura B.9, neste momento acabamos de determinar
os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais est˜ao
sobre a reta
δ
2
= 1.
B Apˆendice 115
Figura B.9:
δ
2
= 1
Neste momento observe que de acordo com a figura B.9 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 2 m
δ
2
= 6 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, as arestas δ
1
e δ
3
podem ser levantadas. Esco-
lhemos a aresta δ
1
. Vamos calcular G
δ
1
2
= g
22
+ g
13
z
−1
m
δ
1
=2
.
G
δ
1
2
− {V
δ
1
(F
δ
1
2
− G
δ
1
1
H
δ
1
1
) mod (G
δ
1
0
)} = G
δ
1
0
.
(g
22
− 1) + g
13
z
−1
d=1
= (z
2
+ 1) (B.7)
Como d = 1 < n
δ
1
−1 = 2 ent˜ao = 0. Igualando os polinˆomios em B.7 e resolvendo
o sistema obtemos g
22
= 1 e g
13
= 0. Logo:
G
δ
1
2
= 1 e H
δ
1
2
= 1.
Conforme pode ser observado na figura B.10, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
1
= 2.
B Apˆendice 116
Figura B.10:
δ
1
= 2
Neste momento observe que de acordo com a figura B.10 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 2 m
δ
2
= 5 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, as arestas δ
1
e δ
3
podem ser levantadas. Esco-
lhemos a aresta δ
1
. Vamos calcular G
δ
1
3
= g
32
+ g
23
z
−1
m
δ
1
=2
.
G
δ
1
3
− {V
δ
1
(F
δ
1
3
−
2
j=1
G
δ
1
j
H
δ
1
3−j
) mod G
δ
1
0
} = G
δ
1
0
.
(g
23
− 1)z
−1
+ g
32
− z
d=2
= (1 + z
2
) (B.8)
Como d = 2 = n
δ
1
−1 = 2 ent˜ao grau() = d −(n
δ
1
−1) = 2 −2 = 0. Logo, = bz
a
.
Onde z
a
´e igual ao termo de mais baixo grau no lado esquerdo de B.8. Ent˜ao a = −1
e = bz
−1
. Resolvendo o sitema obtido quando igualamos os polinˆomios em B.8
obtemos: b = −1, g
32
= 0 e g
23
= 0. Logo:
G
δ
1
3
= 0 e H
δ
1
3
= z
−1
.
Conforme pode ser observado na figura B.11, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
1
= 3.
B Apˆendice 117
Figura B.11:
δ
1
= 3
Neste momento observe que de acordo com a figura B.11 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 3 m
δ
2
= 4 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, as arestas δ
2
e δ
3
podem ser levantadas. Escol-
hemos a aresta δ
2
. Vamos calcular
G
δ
2
2
= z
−2
+ 1 + g
42
z
2
+ g
52
z
3
+ g
62
z
4
+ g
72
z
5
m
δ
2
=4
+z
6
.
z
−2
+ (g
42
+ 2)z
2
+ g
52
z
3
+ g
62
z
4
+ g
72
z
5
+ z
6
d=8
= (1 + z
4
). (B.9)
Como d = 8 > n
δ
2
− 1 = 4 ent˜ao o grau() = 8 − 4 = 4. Logo, tem 5 termos.
= bz
a
+ cz
a+1
+ dz
a+2
+ ez
a+3
+ fz
a+4
. Onde z
a
´e igual ao termo de mais baixo
grau no lado esquerdo de B.9. Logo z
a
= z
−2
e assim, = bz
−2
+cz
−1
+d + ez +fz
2
.
Igualando os polinˆomios em B.9 e resolvendo o sistema, obtemos: g
42
= 0, g
52
= 0,
g
62
= 0 e g
72
= 0. Agora, vamos calcular H
δ
2
2
= h
22
z
2
.
H
δ
2
2
=
F
δ
2
2
− G
δ
2
1
H
δ
2
1
− G
δ
2
2
H
δ
2
0
G
δ
2
0
= z
2
.
h
22
z
2
= z
2
. (B.10)
Igualando os polinˆomios em B.10, obtemos: h
22
= 1. Ent˜ao:
G
δ
2
2
= z
−2
+ 1 + z
6
e H
δ
2
2
= z
2
.
B Apˆendice 118
Conforme pode ser observado na figura B.12, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
2
= 2.
Figura B.12:
δ
2
= 2
Neste momento observe que de acordo com a figura B.12 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 2 m
δ
2
= 5 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, as arestas δ
1
e δ
3
podem ser levantadas. Esco-
lhemos a aresta δ
1
. Vamos calcular G
δ
1
4
= z
2
+ z + g
33
z
−1
+ g
24
z
−2
m
δ
1
=2
.
(g
24
− 2)z
−2
+ g
33
z
−1
+ z
2
d=4
= (1 + z
2
) (B.11)
Como d = 4 > n
δ
1
− 1 = 2 ent˜ao grau() = 4 − 2 = 2, logo, possui 3 termos.
Como feito anteriormente, temos que: = az
−2
+ bz
−1
+ c. Igualando os polinˆomios
em B.11 e resolvendo o sistema temos que : g
33
= 0 e g
24
= 1. Ent˜ao:
G
δ
1
4
= z
2
+ z + z
−2
e H
δ
1
4
= 1 + z
−2
.
Conforme pode ser observado na figura B.13, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
1
= 4.
B Apˆendice 119
Figura B.13:
δ
1
= 4
Neste momento observe que de acordo com a figura B.13 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 2 m
δ
2
= 4 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, todas as arestas podem ser levantadas. Escolhe-
mos a aresta δ
2
. Vamos calcular
G
δ
2
3
= g
43
z
2
+ g
53
z
3
+ g
63
z
4
+ g
73
z
5
m
δ
2
=4
.
g
43
z
2
+ (g
53
− 1)z
3
+ g
63
z
4
+ g
73
z
5
d=3
= (1 + z
4
). (B.12)
Como d = 3 < n
δ
2
− 1 = 4 ent˜ao = 0. Igualando os polinˆomios em B.12 e
resolvendo o sistema, obtemos: g
43
= 0, g
53
= 1, g
63
= 0 e g
73
= 0. Ent˜ao:
G
δ
2
3
= z
3
e H
δ
2
3
= z
−1
.
Conforme pode ser observado na figura B.14, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
2
= 3.
B Apˆendice 120
Figura B.14:
δ
2
= 3
Neste momento observe que de acordo com a figura B.14 temos:
n
δ
1
= 3 n
δ
2
= 5 n
δ
3
= 3
m
δ
1
= 1 m
δ
2
= 4 m
δ
3
= 1
Ent˜ao, de acordo com o lema 5.5.1, todas as arestas podem ser levantadas. Escolhe-
mos a aresta δ
2
. Vamos calcular
G
δ
2
4
= 1 + g
34
z + g
44
z
2
+ g
54
z
3
+ g
64
z
4
m
δ
2
=4
.
1 + g
34
z + g
44
z
2
+ g
54
z
3
+ g
64
z
4
d=4
= (1 + z
4
). (B.13)
Como d = 4 = n
δ
2
− 1 = 4 ent˜ao grau() = 0. Logo, como feito anteriormente
= a. Igualando os polinˆomios em B.13 e resolvendo o sistema obtemos: g
34
= 0,
g
44
= 0, g
54
= 0 e g
64
= 1. Ent˜ao:
G
δ
2
4
= 1 + z
4
.
Conforme pode ser observado na figura B.15, neste momento acabamos de deter-
minar os coeficientes dos termos do polinˆomio gen´erico g cujos expoentes vetoriais
est˜ao sobre a reta
δ
2
= 4.
B Apˆendice 121
Figura B.15:
δ
2
= 4
Fazendo a fatora¸c˜ao via politopos obtemos:
g = x
2
+ x
6
+ x
2
y
2
+ y
2
+ x
8
y
2
+ x
5
y
3
+ x
2
y
4
+ x
6
y
4
+ x
5
y
e
h = 1 + x
2
+ x
4
+ x
2
y + x
2
y
2
.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
