Álgebras de semigrupos y aplicaciones
Abstract
Dado un semigrupo abeliano, cancelativo,finitamente generado y con elemento neutro, S, y un cuerpo k,podemos considerar el álgebra S-graduada k[S]. El estudio de esta álgebra tiene un gran interes dentro de la Geometria Algebraica por su relación con la Geometría Tórica. De hecho, estudiar esta álgebra es equivalente a estudiar las relaciones entre los generadores de ideales definidos por variedades monomiales. Si tenemos un conjunto,{n1,....,nr}, de generadores de S, y consideramos el anillo de polinomios R=k[X1,....,Xr],podemos estudiar la resolución libre de K[S]. En esta memoria nos centramos en el estudio de los módulos de sicigias de esta resolución. En primer lugar estudiamos la estructura de los ideales asociados a semigrupos determinando que, para determinados semigrupos, estos se corresponden con ideales de retículo. Damos algoritmos basados en bases de Gröbner que nos permiten calcular sistemas irreducibles de generadores del ideal de un semigrupo con torsión. Además, damos un método efectivo, basado en el cálculo de N-soluciones de sistemas diofánticos en congruencias, para calcular los grados que aparecen en el primer módulo de sicigias de k[S], ampliando estos resultados a toda la resolución del álgebra k[S]. . De estos métodos, deducimos cotas para los grados que aparecen en un sistema minimal de generadores el i-ésimo modulo de sicigias de k[S], en función solamente de los generadores del semigrupo. Explicitamos además una cota para la regularidad de una variedad tórica, así como un algoritmo para hallar dicha regularidad. Gran parte de nuestros resultados se obtienen a través de un estudio de las estructuras de las soluciones enteras positivas de un sistema diofántico en congruencias. Una vez explicitadas sus estructuras, demos algoritmos basados en bases de Gröbner y en el lema de Dickson para resolver sistemas diofánticos en congruencias sin añadir nuevas variables.
Full text
Universidad de Sevilla Álgebras de semigrupos y aplicaciones Alberto Vignerón Tenorio 2004 Tesis de Doctorado Facultad de Matemáticas Directora: Dra. Dña. Pilar Pisón Casares
Algebras de Semigrupos y Aplicaciones Alberto Vigneron Tenorio 5 de octubre de 2004
Quiero expresar mi m as sincero agradecimiento a D~ na. Pilar Pis on Casares por su inestimable ayuda y ense~ nanzas recibidas a lo largo de los ultimos a~ nos. Sin su ayuda esta memoria no ser a hoy una realidad.
A mis padres.
INDICE GENERAL Indice General I Introducci on 1 I C alculo de Ideales de Ret culos y Semigrupos 9 I{A. Introducci on . . . . . . . . . . . . . . . . . . . . . . . . . 9 I{B. Ideales de Ret culo e Ideales de Semigrupo . . . . . . . . 10 I{C. Algoritmos Cl asicos de C alculo de I L . . . . . . . . . . . 13 Teor a de Eliminaci on . . . . . . . . . . . . . . . . . . . . . 16 M etodo de Sturmfels-Hosten-Shapiro . . . . . . . . . . . . 17 M etodo de Di Biase-Urbanke . . . . . . . . . . . . . . . . . 20 I{D. C alculo de Ideales de Semigrupos . . . . . . . . . . . . . 23 Algoritmo Algebraico . . . . . . . . . . . . . . . . . . . . . 24 Algoritmo Geom etrico . . . . . . . . . . . . . . . . . . . . 25 I{E. Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 II Sistemas diof anticos: N soluciones 29 II{A. Introducci on . . . . . . . . . . . . . . . . . . . . . . . . . 29 II{B. C alculo de la N soluci on general . . . . . . . . . . . . . 31 B usqueda Exhaustiva . . . . . . . . . . . . . . . . . . . . . 31 M etodo de Clausen-Fortenbacher . . . . . . . . . . . . . . 33 Reducci on de n umero de ecuaciones . . . . . . . . . . . . 34 M etodo de Contejean-Devie . . . . . . . . . . . . . . . . . 35 N soluci on general mediante el Lema de Dickson . . . . . 36 II{C. C alculo de una N soluci on particular . . . . . . . . . . . 39 Lema de Farkas para sistemas homog eneos . . . . . . . . . 40
II Indice General Lema de Farkas para sistemas no homog eneos . . . . . . . 44 M etodo usando Bases de Gr obner . . . . . . . . . . . . . . 48 II{D. Sistemas Diof anticos en Congruencias . . . . . . . . . . 49 N soluci on particular mediante ideales de semigrupos . . 51 N soluci on general mediante el Lema de Dickson . . . . . 53 II{E. Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 III M odulos de Sicigias 57 III{A. M odulos de Sicigias . . . . . . . . . . . . . . . . . . . . . 57 ~ H i ( m ) = V i ( m )......................... 60 III{B. 0-M odulo de Sicigias . . . . . . . . . . . . . . . . . . . . 63 III{C. C alculo pr actico de la resoluci on dados los C i . . . . . . 67 IV C alculo del Primer M odulo de Sicigias 71 IV{A. Conjunto Finito de Chequeo . . . . . . . . . . . . . . . . 71 IV{B. Notas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 V C alculo de la Resoluci on Libre Minimal 83 V{A. Conjunto Finito de Chequeo . . . . . . . . . . . . . . . . 84 V{B. Cotas de los S grados . . . . . . . . . . . . . . . . . . . 95 V{C. Regularidad de una Variedad T orica Proyectiva . . . . . 99 VI Ejemplos 101 VI{A. Ideal de Semigrupo . . . . . . . . . . . . . . . . . . . . . 101 VI{B. Sistemas Diof anticos . . . . . . . . . . . . . . . . . . . . 104 N soluci on Particular . . . . . . . . . . . . . . . . . . . . . 104 N soluci on General . . . . . . . . . . . . . . . . . . . . . . 105 VI{C. Resoluci on Libre Minimal . . . . . . . . . . . . . . . . . 110 Bibliograf a 119
INDICE DE CUADROS III Indice de cuadros II.1. Algoritmos II{B.7 + II{C.6 versus II{B.7 + II{D.5 . . . . . . 56 VI.1. HG (2 ; 0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 VI.2. HG (2 ; 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 VI.3. HG (2 ; 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 VI.4.Lista de C . . . . . . . . . . . . . . . . . . . . . . . . . . 113 VI.5.Lista de complejos . . . . . . . . . . . . . . . . . . . . . . 115
INDICE DE FIGURAS V Indice de guras IV.1. F hueco . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 IV.2. Homolog a nula . . . . . . . . . . . . . . . . . . . . . . . 78 V.1. i triangulaci on . . . . . . . . . . . . . . . . . . . . . . . . 87 V.2. Triangulaci on del Toro . . . . . . . . . . . . . . . . . . . . 89
INTRODUCCI ON Dado S un semigrupo conmutativo, nitamente generado, cancelativo y con elemento neutro, y dado un cuerpo k; podemos considerar la k algebra asociada al semigrupo, k [ S ] = m 2 S km; entendiendo m como un s mbolo. El producto en esta algebra se dene como m m 0 = m + m 0 ; es decir, el producto de s mbolos es el s mbolo de la suma. El estudio de esta algebra tiene un gran inter es dentro de la Geometr a Algebraica por su relaci on con la Geometr a T orica. De hecho, estudiar este algebra es equivalente a estudiar las relaciones entre los generadores de ideales denidos por variedades monomiales, es decir, variedades anes parametrizadas por ecuaciones monomiales. En [STU95]y [CP] aparece un interesante estudio sobre los distintos enfoques que se dan en la actualidad al estudio de las variedades t oricas. Dados unos generadores del semigrupo S; f n 1 ;:::;n r g ; y el anillo de polinomios R = k [ X 1 ;:::;X r ] ; denimos el ideal del semigrupo como el n ucleo del morsmo de k algebras dado por ' : R ! k [ S ] ' ( X i ) = n i Es conocido (ver [HER70]) que este ideal es binomial y homog eneo respecto de la graduaci on grado ( X i ) = n i : Existen algoritmos para calcular estos ideales si el semigrupo S es libre de torsi on. Casi todos ellos emplean bases de Gr obner. El caso de la torsi on fue abordado por primera vez en [BCMP98b] para semigrupos vericando S \ ( S ) = 0 : Las t ecnicas utilizadas en este art culo se basan en el estudio de ciertos complejos simpliciales que fueron denidos por primera vez en [CM91] y cuyos grafos subyacen-
8 Introducci on En el cap tulo III comenzamos a estudiar la resoluci on libre minimal de la k algebra de un semigrupo Nakayama. Vemos como se pueden caracterizar los grados de los sistemas minimales de generadores del i esimo m odulo de sicigias de k [ S ] ; a trav es de estructuras combinatorias. En particular resolvemos este problema para el 0 m odulo (ideal del semigrupo) mediante un algoritmo (III{B.6). Tambi en vemos como, conocidos los grados que aparecen en los sistemas de generadores minimales, podemos calcular los propios generadores. Los resultados presentados en este cap tulo constituyen una revisi on de los aparecidos en [BCMP98b] y [BCMP98a]. El cap tulo IV lo dedicamos a dar un m etodo efectivo, basado en el c alculo de N soluciones de sistemas diof anticos en congruencias, para calcular los grados que aparecen en el primer m odulo de sicigias de k [ S ] (IV{A.8). B asicamente, este cap tulo recoge los resultados publicados en [PCVTer]. En el cap tulo V generalizamos los m etodos del cap tulo IV a toda la resoluci on del algebra k [ S ] (V{A.9). Adem as, damos cotas para los grados que aparecen en un sistema minimal de generadores del i esimo m odulo de sicigias de k [ S ] ; en funci on solamente de los generadores considerados para el semigrupo. Terminamos el cap tulo explicitando una cota para la regularidad de una variedad t orica (V{ C.1), as como un algoritmo para hallar dicha regularidad (V{C.2). Los resultados de este cap tulo est an recogidos en [BMPCVT99]. En el cap tulo VI, vemos una serie de ejemplos num ericos que ilustran los algoritmos m as importantes dados en esta memoria.
CAP ITULO I C alculo de Ideales de Retculos y Semigrupos I–A. INTRODUCCI´ ON Sea S un semigrupo conmutativo, nitamente generado y con elemento neutro, k un cuerpo, y f n 1 ;:::;n r g un sistema de generadores de S: Denotaremos por R al anillo en r indeterminadas sobre el cuerpo k; k [ X 1 ;:::;X r ] : Recordemos que se puede asociar un ideal I (dependiente del sistema de generadores considerado en S ) al semigrupo S: Dicho ideal es el n ucleo del morsmo de k algebras ' : R ! k [ S ] ; ' ( X i ) = n i ; (I{A.1) donde k [ S ] es el algebra asociada a S: Adem as, es conocido (ver [HER70]) que I est a generado por el conjunto f X X : r X i =1 i n i = r X i =1 i n i ; ; 2 N r g ; luego es un ideal binomial.
10 Ideales de Retculo e Ideales de Semigrupo Diremos que S es Nakayama si verica la condici on S \ ( S ) = f 0 g : Esta propiedad es fundamental para poder hablar de sistemas minimales de generadores de I: Un semigrupo es cancelativo si dados m; n; n 0 2 S con m + n 0 = m + n; se tiene n = n 0 : En cap tulos posteriores nos encargaremos de profundizar m as en el aspecto te orico de los resultados que necesitaremos sobre el algebra de un semigrupo. De manera parecida al caso del semigrupo, dado un ret culo L de Z r ; le podemos asociar un ideal binomial en R; I L := < X u X v : u; v 2 N r ; u v 2 L > : A estos ideales los llamaremos de manera gen erica ideales de ret culo. Para jar notaci on, dado u 2 Z r ; denotamos por u + ;u a los unicos elementos de N r tales que u = u + u y supp ( u + ) \ supp ( u ) = ; : Diremos que un ret culo L es Nakayama si verica la condici on L \ N r = (0) : Y diremos que es saturado si dado cualquier upla u 2 Z r y cualquier 2 Z no nulo vericando u 2 L ; se tiene u 2 L : Entonces, si un ret culo es saturado, existe una matriz, A; con coecientes enteros tal que L = ker( A ) : Es conocido que dado un ret culo saturado, su ideal asociado es primo (ver [ES96]). En este cap tulo veremos en primer lugar que los ideales de ret culo son, en realidad, un caso particular de ideales de semigrupos: los semigrupos conmutativos, nitamente generados, con elemento neutro y cancelativos (lema I{B.1), dando distintos algoritmos para calcular un sistema de generadores del ideal I: Adem as analizaremos diferentes m etodos para calcular unos generadores del ideal I L a partir de un sistema de generadores de L : I–B. IDEALES DE RET´ ICULO E IDEALES DE SEMIGRUPO De nuevo consideremos S un semigrupo abeliano, con elemento neutro, cancelativo y nitamente generado. Por el Teorema de Estructura (ver [BCMP98b]) podemos suponer, sin perdida de generalidad,
Captulo I: C alculo de Ideales de Retculos y Semigrupos 11 que S Z h Z =a 1 Z Z =a s Z ; donde a 1 ;:::;a s son enteros no nulos. Consideremos f n 1 ;:::;n r g un conjunto de generadores del semigrupo S anterior, y sea I k [ X 1 :::;X r ] el ideal asociado a S: El ideal anterior lo podemos identicar con el ideal de ret culo I ker( S ) ; donde ker( S ) es el ret culo formado por las soluciones enteras del sistema ( n 1 j ::: j n r ) 0 B B B @ x 1 . . . x r 1 C C C A = 0 ; como puede verse en el siguiente resultado. Lema I–B.1 I es un ideal de un semigrupo S cancelativo, nitamente generado, abeliano y con elemento neutro, si y s olo si I es un ideal de ret culo. Demostraci´on. Sea S = < n 1 ;:::;n r > un semigrupo y sea I su ideal en R: Por [HER70] sabemos que I est a generado por B = f X X : r X i =1 i n i = r X i =1 i n i ; i ; i 0 g : Adem as, por ser S cancelativo, podemos asegurar que I est a generado por B 0 = f X + X : r X i =1 i n i = 0 ; i 2 Z g : Por tanto, tomando el ret culo L generado por las r uplas + del conjunto B 0 ; tenemos que I = < X + X : + 2 L >; luego I es un ideal de ret culo. Rec procamente, sea L un ret culo en Z r : Consideramos la aplicaci on : N r ! Z r = L e i 7! e i + L ;
12 Ideales de Retculo e Ideales de Semigrupo donde los e i forman la base can onica de N r : Sea S el semigrupo < e 1 + L ;:::;e r + L > ([CG00]). Es f acil ver que su ideal asociado coincide con I L : Este resultado nos indica que existe una dualidad entre los semigrupos cancelativos, conmutativos, nitamente generados y con elemento neutro, y los ret culos. Dado un semigrupo, S; le asociamos un ret culo ker( S ) ; y dado un ret culo L ; podemos asociarle un semigrupo, S = < e 1 + L ;:::;e r + L > : Respecto a las propiedades, es f acil ver que si partimos de un semigrupo S; S es Nakayama si y s olo si ker( S ) lo es, y S es libre de torsi on si y s olo si ker( S ) es saturado. Equivalentemente, si partimos de un ret culo L ; L es Nakayama si y s olo si S lo es, y L es saturado si y s olo si S es libre de torsi on. El ejemplo siguiente pone de maniesto que los sistemas de generadores irreducibles de I pueden tener distinto cardinal. Ejemplo I–B.2 Sea el semigrupo incluido en Z Z = 2 Z Z = 4 Z ; S = < (0 ; 0 ; 1) ; (2 ; 1 ; 1) ; (1 ; 0 ; 3) ; ( 2 ; 1 ; 3) >; que no es Nakayama ( n 2 = n 4 ). Entonces se tiene que el ideal de S est a generado por I = < x 2 4 x 4 3 x 2 1 ;x 2 x 3 4 x 8 3 ; x 4 4 x 8 3 1 > = < x 4 x 2 1 ; 1 x 4 1 ;x 8 3 x 8 1 x 4 2 ; x 12 3 x 10 1 x 6 2 >; donde ambos sistemas son irreducibles. Sin embargo si el semigrupo de partida cumple la condici on: S \ ( S ) = f 0 g ; i.e. es Nakayama, tiene sentido hablar de sistemas minimales de generadores de I; ya que todos los sistemas irreducibles de generadores tienen el mismo cardinal (ver [BCMP98b], aunque en cap tulos posteriores entraremos con m as detalle en este tema). Al ser esta una propiedad
Captulo I: C alculo de Ideales de Retculos y Semigrupos 13 que afecta tanto al resultado que se obtiene, es interesante poder detectar con qu e tipo de semigrupo nos estamos enfrentando. Para ello usaremos la siguiente caracterizaci on. Lema I–B.3 Sea S un semigrupo, y sea I su ideal en k [ X 1 ;:::;X r ] : El semigrupo S no es Nakayama si y s olo si existe en su ideal I un binomio de la forma M 1 ; siendo M un monomio en k [ X 1 ;:::;X r ] : Demostraci´on. Sean n 1 ;:::;n r unos generadores de S; y supongamos que existe un binomio X 1 perteneciente a I; con = ( 1 ;:::; r ) 2 N r : En ese caso tenemos que r X i =1 i n i =0 ; con lo cual S no es Nakayama. An alogamente, si S no es Nakayama, existe una r upla = ( 1 ;:::; r ) 2 N r ; tal que P r i =1 i n i =0 ; y por lo tanto el binomio X 1 pertenece a I: Nota I–B.4 Para ver entonces si S es o no Nakayama s olo habr a que buscar, en cualquier sistema de generadores binomiales con coecientes 1 y 1 de I; si hay o no un elemento de la forma ( M 1) ; con M un monomio. Pasemos ahora a ver distintos algoritmos para calcular un ideal de ret culo y, a partir de ellos, distintos algoritmos para calcular ideales de semigrupos conmutativos, cancelativos, nitamente generados y con elemento neutro. I–C. ALGORITMOS CL´ ASICOS DE C´ ALCULO DE I L Con la notaci on anterior, el problema que nos planteamos es c omo calcular unos generadores del ideal I L a partir de un conjunto de generadores C de L : En adelante vamos a suponer, sin p erdida de generalidad, que
14 Algoritmos Cl asicos de C alculo de I L para toda coordenada i = 1 ; : : : ; r de los elementos de L ; existe al menos un elemento u 2 L tal que u i 6 = 0 : Gracias a ello podemos considerar equivalentes los sistemas de generadores C de L tales que C N r y aquellos en los que existe un elemento con todas las coordenadas estrictamente positivas, ya que podremos pasar de unos a otros con operaciones elementales. Adem as, uno de estos sistemas de generadores existe si y s olo si existe el otro. Una propiedad de los ideales de ret culo que nos ser a muy util en lo sucesivo es la siguiente. Lema I–C.1 X u X v 2 I L si y s olo si u v 2 L con u; v 2 N r : Demostraci´on. Por denici on de I L ; si u v 2 L ; tenemos que X u X v 2 I L : Luego es la otra implicaci on la que tenemos que probar. Al ret culo L podemos asociarle (I{B.1) un semigrupo S generado por unos ciertos n 1 ;:::;n r 2 S tales que L = ker( S ) e I L = I: Entonces, dado un binomio X u X v 2 I L = I; tenemos que (I{A.1) 0 = ' ( X u X v ) = X u i n i X v i n i y por lo tanto P ( u i v i ) n i = 0 : Llegamos entonces a que u v 2 ker( S ) = L ; concluyendo la demostraci on. Si J es un ideal de R; y f 2 R un polinomio, tambi en son ideales los conjuntos ( J : f ) = f g 2 k [ X 1 ;:::;X r ] : fg 2 J g ; ( J : f 1 ) = f g 2 k [ X 1 ;:::;X r ] : f s g 2 J; para alg un s 2 N g : A estos ideales los llamaremos ideales cocientes de J sobre f o f 1 respectivamente. Por ser R noetheriano, sabemos que existe s 2 N tal que ( J : f 1 ) = ( J : f s ) : Estos ideales ser an binomiales si J es binomial y f es un monomio (ver [ES96]).
Captulo I: C alculo de Ideales de Retculos y Semigrupos 15 El porqu e de haber introducido los ideales anteriores queda claramente respondido en el siguiente lema, el cual los liga a los ideales de ret culo. Lema I–C.2 Sea C = f u 1 ; : : : ; u s gL : Entonces C es un conjunto de generadores del ret culo L si y s olo si ( J C : ( X 1 :::X r ) 1 ) = I L ; donde J C := < X u + X u : u = u + u 2 C>: Demostraci´on. Veamos en primer lugar la implicaci on s olo si . Para ello vamos a probar por doble inclusi on la igualdad ( J C : ( X 1 :::X r ) 1 ) = I L : Sea u = u + u 2 L : Si C genera L ; se tiene que existen 1 ; : : : ; s 2 Z tales que u = P s i =1 i u i : Entonces X u + X u 1 = s Y i =1 0 @ X u + i X u i 1 A i 1 : Por comodidad de notaci on, denotaremos por v i a la upla u i si i 0 o u i en otro caso, quedando la expresi on anterior como sigue X u + X u 1 = s Y i =1 0 @ X v + i X v i 1 A 0 i 1 ; con 0 i 0 : Vamos a suponer por comodidad de notaci on que 0 i = i : Reduciendo los denominadores, llegamos a que existe un cierto monomio X a tal que X a ( X u + X u ) = X u ( X P i v + i X P i v i ) : Veamos que X P i v + i X P i v i 2 J C :
16 Algoritmos Cl asicos de C alculo de I L Si suponemos que 1 > 0 ; podemos considerar X P i v + i X P i v i = X w 1 1 X v + 1 X w 2 1 X v 1 ; con w 1 1 = ( 1 1) v + 1 + P s i =2 i v + i y w 2 1 = ( 1 1) v 1 + P s i =2 i v i : Por lo tanto X P i v + i X P i v i = X w 1 1 X v + 1 X w 2 1 X v 1 = X w 1 1 X v + 1 X w 1 1 X v 1 + X w 1 1 X v 1 X w 2 1 X v 1 = X w 1 1 ( X v + 1 X v 1 ) |{z } 2 J C + X v 1 ( X w 1 1 X w 2 1 ) Si operamos de manera inductiva con X w 1 1 X w 2 1 ; obtenemos que X P i v + i X P i v i 2 J C ; y ya hemos demostrado I L ( J C : ( X 1 :::X r ) 1 ) : La otra inclusi on es trivial, basta con recordar que el ideal cociente es binomial y probar la inclusi on para binomios usando I{C.1. Para probar la implicaci on rec proca, tomemos u 2 L y su binomio asociado en I L ; X u + X u : Entonces, existir a un monomio, X a ; de manera que X a ( X u + X u ) 2 J C : Aplicando ahora I{C.1 tenemos u = a + u + a u 2 < C > : Por lo tanto, C es un sistema de generadores de L : Centr emonos en los algoritmos de c alculo del ideal ( J C : ( X 1 :::X r ) 1 ) ; ya que as obtenemos I L : Teor´ıa de Eliminaci´on El primero que referimos se basa en la Teor a de Eliminaci on. Proposici´on I–C.3 Sea I = < f 1 ;:::;f l > un ideal de R; sea f 2 R un polinomio no nulo, y sea J = < f 1 ;:::;f l ; 1 Yf > ideal en k [ X 1 ; : : : ; X r ; Y ] : Entonces, ( I : f 1 ) es el ideal de eliminaci on J X = J \ R: Adem as, si f g 1 ;:::;g m g es una base de J X con g i = h i (1 Yf ) + l X j =1 h ij f j ; (1 i m; h i ; h ij 2 k [ X 1 ;:::;X r ;Y ]) ;
Captulo I: C alculo de Ideales de Retculos y Semigrupos 17 el n umero s = m ax f deg Y ( h ij ) j 1 i m; 1 j l g satisface ( I : f 1 )=( I : f s ) : Demostraci´on. Ver [BW93, p ag. 266]. Para calcular el ideal ( J C : ( X 1 : : : X r ) 1 ) ; habr a pues que calcular el ideal de eliminaci on de < f 1 ; : : : ; f l ; 1 X 1 X r Y >; donde f f 1 ; : : : ; f l g es un sistema generador de J C : Este c alculo se realiza mediante bases de Gr obner (ver [BW93]). N otese que hemos pasado de trabajar en un anillo R con r variables a otro con r +1 variables, k [ X 1 ;:::;X r ; Y ] ; lo cual hace que el coste computacional aumente (eterno problema cuando tratamos de realizar c alculos usando bases de Gr obner). Existen otros m etodos basados en calcular bases de Gr obner con un menor n umero de variables, lo que, en general, acelera el proceso computacional. M´etodo de Sturmfels-Hosten-Shapiro El primero que estudiamos aparece en [STU95] y puede aplicarse al caso en el cual la graduaci on que consideremos en el anillo R sea positiva. Esto, a nivel del ret culo, se traduce en que se verica L \ N r = f 0 g ; es decir, es Nakayama. Dicho algoritmo se basa en el siguiente lema. Lema I–C.4 Sea J un ideal homog eneo para una graduaci on positiva, entonces, - jado el orden reverso lexicogr aco inducido por X 1 > > X r ; y denotando por G a la base de Gr obner reducida de J; se tiene que el conjunto formado por los polinomios que resultan de dividir cada elemento f 2 G por la mayor potencia de X r que divide a f; es una base de Gr obner de ( J : X 1 r ) : Demostraci´on. Ver [STU95, lema 12.1].
24 C alculo de Ideales de Semigrupos Sean n 0 i = n i ; 8 i 2 f 1 ;:::;r g (considerando los generadores de S en Z h + s ), y sean tambi en n 0 i = (0 ; : : : ; 0 |{z } h ; 0 ;:::; 0 ; a i r ; 0 ;:::; 0 |{z } s ) para i 2 f r + 1 ;:::;r + s g ; donde a i r ocupa la coordenada j = i r + h: Denotemos S 0 al semigrupo de Z h + s generado por f n 0 1 ;:::;n 0 r + s g : Algoritmo Algebraico Sea ker( S 0 ) el ret culo formado por las soluciones enteras del sistema ( n 0 1 j ::: j n 0 r + s ) 0 B B B @ x 1 . . . x r + s 1 C C C A = 0 : Es evidente el siguiente resultado, Lema I–D.1 Dado un sistema de generadores C 0 de ker( S 0 ) Z r + s ; el conjunto C que resulta de proyectar C 0 en las r primeras coordenadas, es un sistema de generadores de ker( S ) Z r : As obtenemos un algoritmo puramente algebraico para calcular el ideal de un semigrupo con torsi on. Algoritmo I–D.2 Con las notaciones anteriores: Entrada: Un sistema de generadores de S; f n 1 ; : : : ; n r g : Salida: Un sistema de generadores del ideal de S: 1. Calculamos el semigrupo S 0 : 2. Calculamos un conjunto de generadores C 0 del ret culo ker( S 0 ) : 3. Proyectamos los elementos de C 0 sobre Z r ; y obtenemos C un sistema de generadores del ret culo ker( S ) :
Captulo I: C alculo de Ideales de Retculos y Semigrupos 25 4. De C obtenemos un sistema de generadores de I = I ker( S ) mediante alg un algoritmo de c alculo de ideales de ret culo. Veamos en la siguiente secci on, un algoritmo basado en un resultado geom etrico para calcular el ideal de un semigrupo con torsi on. Su estudio explica por qu e los ideales de semigrupos con torsi on no son necesariamente primos. Algoritmo Geom´etrico Sean S y S 0 como en la secci on anterior, y sea I 0 el ideal de S 0 : Lema I–D.3 Sea B 0 un conjunto de generadores de I 0 formado por binomios con coecientes 1 y 1 : Entonces, el conjunto B que resulta de hacer uno las variables f X i g r + s i = r +1 en los elementos de B 0 ; es un sistema de generadores de I: Demostraci´on. En primer lugar veamos que B est a incluido en I: Sea f 2 B; entonces, existe f 0 2 B 0 tal que f = f 0 ( X 1 ;:::;X r ; 1 ;:::; 1) ; con f 0 = X 0 X 0 ; donde 0 ; 0 2 N r + s y P r + s i =1 0 i n 0 i = P r + s i =1 0 i n 0 i : Es inmediato probar que P r i =1 0 i n i = P r i =1 0 i n i : Por lo tanto f es un binomio de I: Ahora probemos que B genera el ideal I: Para ello basta probar que todo binomio con coecientes 1 en I puede ser expresado en funci on de los elementos de B: Sea f = X X un binomio de I; entonces P r i =1 i n i = P r i =1 i n i : Construiremos f 0 2 I 0 tal que f = f 0 ( X 1 ;:::;X r ; 1 ;:::; 1) ; lo cual basta, ya que al ser B 0 un conjunto generador de I 0 ; tenemos que podemos expresar f 0 en funci on de los elementos de B 0 ; y por lo tanto, al hacer uno las variables f X i g r + s i = r +1 ; tenemos f en funci on de los elementos de B; lo que probar a que B es un conjunto de generadores de I: Sabemos que, denotando por n ij a la j esima componente de n i ; 8 j = 1 ;:::;h + s r X i =1 i n ij = r X i =1 i n ij : Si j 2 f h + 1 ;:::;h + s g la igualdad anterior debe entenderse en Z =a j h Z ;
26 C alculo de Ideales de Semigrupos por lo tanto se tiene que r X i =1 i n ij r X i =1 i n ij = l j a j n para cierto l j 2 Z : Denimos 8 i = 1 ; : : : ; r; 0 i = i y 0 i = i ; mientras que si i = r + 1 ;:::;r + s; denimos 0 i = 8 < : l i r + h si l i r + h 0 0 en otro caso 0 i = 8 < : l i r + h si l i r + h > 0 0 en otro caso Es f acil comprobar ahora que P r + s i =1 0 i n 0 i = P r + s i =1 0 i n 0 i y que con f 0 = X 0 X 0 2 I 0 se tiene que f = f 0 ( X 1 ; : : : ; X r ; 1 ; : : : ; 1) : Usando este lema podemos trabajar pasando de nuestro semigrupo de partida a uno libre de torsi on. La vuelta al semigrupo inicial se realizar a a nivel del ideal y no del ret culo como en el algoritmo I{D.2 haciendo uno las variables introducidas con los nuevos generadores de S 0 : Algoritmo I–D.4 Con las notaciones anteriores: Entrada: Un sistema de generadores de S; f n 1 ; : : : ; n r g : Salida: Un sistema irreducible de generadores del ideal de S; indicando si S es o no Nakayama. 1. Calculamos el semigrupo S 0 : 2. Calculamos un conjunto de generadores B 0 de I 0 (algoritmo I{ C.12). 3. Hacemos uno las variables f X i g r + s i = r +1 en B 0 y obtenemos B un sistema de generadores de I: 4. De B obtenemos un sistema irreducible de generadores de I:
Captulo I: C alculo de Ideales de Retculos y Semigrupos 27 Este algoritmo es computacionalmente menos eciente que I{ D.2 ya que a~ nade nuevas variables al c alculo, pero da una visi on m as geom etrica de la estructura de los ideales de semigrupos con torsi on. De hecho, nos da una explicaci on de por qu e los ideales de semigrupos con torsi on no son primos en general. Esto se debe a que dicho ideal lo obtenemos a partir de uno primo ( I S 0 ) mediante intersecciones con hipersupercies ( f X j = 1 g ), lo cual no da necesariamente un ideal primo. I–E. NOTAS En este cap tulo hemos presentado dos tipos de algoritmos: unos calculan el ideal de un ret culo y otros el de un semigrupo. De entre los primeros, existen estudios que realizan una comparativa sobre ideales de ret culos Nakayama y saturados (ver por ejemplo [HS95]). Estas comparaciones son anteriores a la mejora realizada en [HS] (algoritmo I{C.6), y de ellas se deduc a que para ese tipo de ret culos ambos algoritmos eran de un eciencia similar. Por lo tanto, cabe pensar ahora que el algoritmo I{C.6 es m as eciente, en cuanto a tiempo de c omputo, que I{C.12. Adem as, en [BLSR99] (implementado en CoCoA [CoC]) se da un algoritmo paralelizado de I{C.6 el cual optimiza a un m as ese algoritmo. En el caso de un ret culo no Nakayama, el m as eciente es I{C.12 debido a que no hay que usar la elevaci on de Lawrence y por lo tanto siempre estamos trabajando en un anillo de polinomios en r variables, frente a las 2 r variables necesarias para aplicar I{C.7. El algoritmo I{ C.12 es el m as recomendable para usar si no conocemos la naturaleza del ret culo, es decir, si es o no Nakayama o saturado. En cuanto a los ideales de semigrupos con torsi on, s olo exist a hasta la aparici on de [PCVT96] una referencia a ese c alculo en [BCMP98b], pero dicho algoritmo usaba m etodos combinatorios que en la pr actica resultan del todo inecientes, adem as de que s olo es aplicable a semigrupos Nakayama. Un algoritmo posterior a [PCVT96] aparece en
28 Notas [RUB96]. En [RGS98] encontramos otro algoritmo donde se aborda el problema desde el c alculo de N soluciones de un sistema diof antico. Entre el algoritmo I{D.2 (publicado en [VT99]) y el aparecido en [RGS98] no se han realizado estudios comparativos respecto de la ecacia de ambos. El algoritmo I{C.12 lo hemos implementado en MapleV3 y puede ser obtenido v a ftp en ftp.uca.es/pub/matematicas/semigrou1.zip
CAP ITULO II Sistemas diof anticos: N soluciones II–A. INTRODUCCI´ ON En este cap tulo vamos a realizar un peque~ no recorrido a trav es de distintos m etodos que calculan N soluciones de un sistema diof antico. Adem as damos nuevos algoritmos para calcular N soluciones de sistemas diof anticos en congruencias. Comencemos considerando el sistema diof antico homog eneo Gx = 0 ; con G 2 M m r ( Z ) : Es conocido desde nales del siglo XIX ([GOR73], [HIL90]) que las soluciones enteras positivas ( N soluciones) de un sistema de ecuaciones homog eneas diof anticas forman un semigrupo S con elemento neutro y nitamente generado, existiendo un unico sistema minimal de generadores tal que cualquier N soluci on puede ser expresada como una combinaci on lineal con coecientes enteros positivos de los elementos de dicho conjunto. A este conjunto se le denomina base de Hilbert y se le denota por H ( S ) o H S:
30 Introducci on Denotaremos por al orden parcial natural sobre N r ; es decir, dadas dos uplas de n umeros enteros y 0 ; diremos que es mayor que 0 ( 0 ) si todos los elementos de 0 son enteros no negativos y al menos uno es no nulo. Sea L N r ; diremos que 2 L es minimal en L si 8 0 2 L n f g ; 6 0 : Denotaremos por H ( L ) o H L al conjunto si L 6 = f 0 g , H L es el conjunto de elementos minimales en L n f 0 g ; si L = f 0 g ; H L := f 0 g : El lema de Dickson ([BW93, p ag. 163]) nos garantiza la nitud de H L: Nosotros damos en II{B.5 una versi on constructiva de dicho lema para determinados subconjuntos de N r a los que ya nos referiremos. Considerando esta notaci on, tenemos el siguiente resultado. Lema II–A.1 Sea G = f x 2 N r j Gx = 0 g ; entonces HG es el sistema minimal de generadores de G (i.e. HG es la base de Hilbert de G ). En el caso de que el sistema sea no homog eneo, Gx = b; con b 2 Z m ; las N soluciones pueden ser escritas como la uni on nita de subconjuntos de N r : Estos subconjuntos est an formados por la suma de una N soluci on minimal y el conjunto de N soluciones del sistema homog eneo asociado, como vemos en el lema siguiente. Lema II–A.2 Sea G 0 el conjunto f x 2 N r j Gx = b g ; y sea G = f x 2 N r j Gx = 0 g : Entonces G 0 = [ x 2HG 0 ( x + G ) : Resolver un sistema no homog eneo se reduce habitualmente a resolver un sistema homog eneo con una inc ognita m as. Este paso nos lo permite la siguiente nota.
Captulo II: Sistemas diof anticos: N soluciones 31 Nota II–A.3 Sistemas no homog eneos. HG 0 = Hf x 2 N r j ( G j b )( x; 1) = 0 g : Si G 00 = f x 2 N r +1 j ( G j b ) x = 0 g , entonces HG 0 = f x 2 N r j ( x; 1) 2 HG 00 g : En cap tulos sucesivos, vamos a necesitar calcular tan solo N soluciones minimales m as grandes que un elemento jo dado e 0 : Esto lo haremos mediante la siguiente nota, pasando a resolver el problema calculando N soluciones de un sistema no homog eneo. Nota II–A.4 Sea e 2 N r y sea G e := f x 2 N r j Gx = 0 ; x e g : Para calcular HG e ; usaremos que G e = G 0 e + e; y HG e = HG 0 e + e con G 0 e := f x 2 N r j G ( x + e ) = 0 g : Por lo tanto, una vez obtenido HG 0 e (soluciones de un sistema no homog eneo), le sumaremos a cada uno de sus elementos la upla e: El resultado de esa suma ser a HG e : II–B. C´ ALCULO DE LA N SOLUCI´ ON GENERAL Para encontrar un sistema de generadores de las N soluciones de un sistema diof antico, aparecen en la bibliograf a matem atica varios m etodos. Entre ellos vamos a destacar aquellos que m as han influido en la elaboraci on de esta memoria. Los dividiremos en distintas secciones en funci on de la losof a de cada m etodo. B´usqueda Exhaustiva Este m etodo se basa en la realizaci on de una b usqueda exhaustiva (o barrido) de las N soluciones en una regi on del espacio. Dicha regi on viene determinada por una cota para las coordenadas de los
32 C alculo de la N soluci on general elementos de un sistema de generadores de las N soluciones. El m etodo consiste en, una vez obtenida una cota, comprobar qu e uplas de elementos enteros positivos (determinados por las cotas) verican las ecuaciones. Despu es, nos quedamos s olo con los elementos minimales de ese conjunto. El principal problema de este m etodo es el enorme tama~ no de las cotas conocidas hasta el momento. En esta memoria s olo vamos a dar algunos ejemplos de estas cotas (ver [TOM97] si se desea ampliar esta informaci on). Para ello, vamos a considerar los sistemas Gx = b; Gx = 0 ; con G = ( g ij ) 2 M m r ( Z ) ;rg ( G ) = m y r m: (II{B.1) Denotamos por HG 0 y por HG a los respectivos conjuntos de N soluciones minimales. La norma uno ( jj jj 1 ) de un conjunto se dene como el m aximo de las normas uno de cada elemento del conjunto, siendo la norma uno de una upla la suma de los valores absolutos de sus coordenadas. Para una matriz, A = ( a ij ) ; denimos su norma uno como jj A jj 1 = m ax i P j j a ij j : En [STU91] el autor prueba que jjHGjj 1 ( m + 1)( r m ) m ax fj menores de orden m m de G jg : (II{B.2) Para ello se usan t ecnicas relacionadas con ideales de ret culos y la relaci on de estos ideales con los sistemas diof anticos. En [POT91] aparecen varias cotas. Entre ellas consideramos la siguiente jjHGjj 1 (1 + m ax 1 i m r X j =1 j g ij j ) m ; (II{B.3) y una un poco m as peque~ na en general, jjHGjj 1 m Y i =1 (1 + r X j =1 j g ij j ) : (II{B.4) Las cotas anteriores (II{B.4) y (II{B.2) no son comparables en general, existiendo ejemplos particulares donde una es mayor que la
Captulo II: Sistemas diof anticos: N soluciones 33 otra, y viceversa. Por ejemplo, si consideramos la matriz 0 @ 8 4 5 5 3 5 8 5 1 A obtenemos que la cota (II{B.2) vale 474, que (II{B.4) vale 506. Sin embargo, si consideramos la matriz 0 @ 1 0 3 4 5 2 1 9 1 A tenemos que (II{B.2) vale 186 mientras que (II{B.4) vale 162. M´etodo de Clausen-Fortenbacher En [CF89] aparece un algoritmo para calcular N soluciones a una unica ecuaci on diof antica homog enea, abriendo la puerta a una serie de trabajos posteriores que utilizan este algoritmo como punto de partida. Consideremos una unica ecuaci on diof antica homog enea dx g 1 x 1 + g 2 x 2 + + g r x r = 0 : La idea que aparece en [CF89] es construir las N soluciones minimales de esta ecuaci on a partir de la base can onica de N r ; f e 1 ; : : : ; e r g : Partiendo de (0 ;:::; 0) podemos ir incrementando las coordenadas hasta llegar a una N soluci on o a un vector mayor que una N soluci on. Como es de suponer, esta idea tiene que ir acompa~ nada de alguna condici on inteligente que limite las coordenadas que van a ser incrementadas para obtener un m etodo que, adem as de efectivo, sea eciente. Esas condiciones para incrementar una coordenada son: 1. Si g 1 x 1 + g 2 x 2 + + g r x r < 0 ; entonces incrementamos en 1 alguna coordenada x i tal que g i > 0 ; 2. Si g 1 x 1 + g 2 x 2 + + g r x r > 0 ; entonces incrementamos en 1 alguna coordenada x i tal que g i < 0 : El m etodo consiste en dirigir de forma inteligente la b usqueda de las N soluciones minimales en las direcciones correctas .
40 C alculo de una N soluci on particular Lema de Farkas para sistemas homog´eneos El m etodo que vamos a presentar a continuaci on nos permite saber de manera r apida si un sistema diof antico homog eneo tiene o no alguna N soluci on. Si el sistema de partida es homog eneo (como es el caso), es equivalente estudiar la existencia de N soluciones que estudiar la existencia de soluciones en Q + : Supongamos entonces que L es el Q espacio vectorial de las soluciones del sistema homog eneo (II{B.1). Supongamos tambi en que f c 1 ; ; c q g Q r es una base de L; y denotemos por C a la ( q r )-matriz cuyas las son f c 1 ;:::;c q g : Llamemos v 1 ;:::;v r 2 Q q a las columnas de C: N otese que existe u 2 L \ ( Q + ) r no nulo si y s olo si existe w = ( w 1 ;:::;w q ) 2 Q q con w v i 0 ; y al menos uno de estos productos es estrictamente positivo. La relaci on entre u 2 L Q r y w 2 Q q es la siguiente u = w 1 c 1 + + w q c q = ( w v 1 ; : : : ; w v r ) : Una vez colocados en este punto, nos basta con aplicar la siguiente versi on constructiva del lema de Farkas. Proposici´on II–C.1 Sean v 1 ; : : : ; v r 2 Q q : Existe un algoritmo para decidir si existe o no un vector w 2 Q q tal que w v 1 > 0 y w v i 0 ; 8 i = 2 ; : : : ; r: En el caso de existencia, dicho algoritmo nos da un tal vector w: Demostraci´on. La prueba la haremos de manera recurrente sobre r: Supongamos que r = 1 : Si v 1 = 0 ; no existe soluci on. En otro caso, v 1 i 6 = 0 ; para alg un i: Tomando w 2 Q q con todas las coordenadas nulas salvo la i esima igual a v 1 i j v 1 i j ; ya hemos encontrado el w que buscamos. Supongamos que r 2 : Si no existe p 2 Q q tal que p v 1 > 0 y p v i 0 ; 8 i = 2 ; : : : ; r 1 ; no existe w y por lo tanto no existe soluci on. Caso de que s exista p; y p v r 0 ; tomamos w = p; y habr amos terminado.
Captulo II: Sistemas diof anticos: N soluciones 41 Consideremos entonces que existe p pero p v r < 0 : Denimos unos nuevos vectores v 0 i de la manera siguiente: v 0 i = v i p v i p v r v r ; 8 i = 1 ;:::;r 1 : (II{C.1) Si existe p 0 2 Q q tal que p 0 v 0 1 > 0 ; y p 0 v 0 i 0 ; 8 i = 2 ;:::;r 1 ; es suciente considerar w = p 0 p 0 v r p v r p; ya que w v i = p 0 v 0 i ; 8 i = 1 ;:::;r 1 y w v r = 0 : En cualquier caso, hemos probado que existe un vector w vericando la proposici on. Veamos que en otro caso ( 6 9 p 0 ) no existe w: Supongamos que r = 2 ; como no existe p 0 ; tenemos que v 0 1 = 0 : Entonces v 1 = v 2 ; con = p v 1 p v 2 < 0 y por lo tanto no existe w (de existir, 0 < w v 1 = w v 2 0 ; lo cual es imposible). Vamos a suponer el resultado cierto para cualquier entero menor que r: Si no existe p 0 ; existir a l; un entero entre 1 y r 1 ; tal que para cualquier j = 1 ;:::;l 1 ; existe l j > l j 1 y una colecci on de vectores p j ; v ( j ) 1 ; : : : ; v ( j ) l j 2 Q q vericando: 1. v (1) i = v 0 i ; 8 i = 1 ;:::;r 1 : 2. p j v ( j ) 1 > 0 ; p j v ( j ) i 0 ; p j v ( j ) l j < 0 ; 8 i = 2 ;:::;l j 1 : 3. v ( j +1) i = v ( j ) i p j v ( j ) i p j v ( j ) lj v ( j ) l j ; 1 i l j 1 : 4. v ( l ) 1 = 0 : Denotemos (1) i = p v i p v r ; i = 1 ;:::;r 1 ; y ( j +1) i = p j v ( j ) i p j v ( j ) l j ; j = 1 ;:::;l 1 ; i = 1 ;:::;l j 1 : ( ( j ) i 0 ; ( j ) 1 > 0 ; 8 i 6 = 1 ; 8 j: )
42 C alculo de una N soluci on particular Vamos a probar que v ( j ) i = v i + r X h = i +1 ( j ) ih v h ; con ( j ) ih 0 8 h = i + 1 ;:::;r; 8 j = 1 ;:::;l; 8 i = 1 ;:::;l j : Ve amoslo por inducci on en j: Para j = 1 ; es suciente ver que de (II{C.1) se tiene: v (1) i = v 0 i = v i + (1) i v r : Supong amoslo cierto para j; y prob emoslo para j + 1 : Sabemos, por la denici on de v ( j +1) i ; que v ( j +1) i = v ( j ) i + ( j +1) i v ( j ) l j ; 1 i l j 1 : Usando la hip otesis de inducci on, podemos escribir v ( j ) i = v i + r X h = i +1 ( j ) ih v h ; y v ( j ) l j = v l j + r X h = l j +1 ( j ) l j h v h ; y obtenemos el resultado. Ahora como v ( l ) 1 = 0 ; tenemos v 1 = r X h =2 ( l ) 1 h v h ; con ( l ) 1 h 0 : De aqu se deduce trivialmente que no existe w: De la propia demostraci on, obtenemos un algoritmo. Algoritmo II–C.2 Algoritmo de Farkas ([ROS95]). Entrada: Unos vectores v 1 ;:::;v r 2 Q q : Salida: Un vector, si existe, w 2 Q q ; tal que w v 1 > 0 ; y w v i 0 ; i = 2 ;:::;r: Caso de no existir w; devuelve ; : 1. Si r = 1 : a )Si v 1 = 0 ; devolver ; :
Captulo II: Sistemas diof anticos: N soluciones 43 b ) En otro caso, devolver w 2 Q q un vector con todas las coordenadas nulas salvo la i esima con v 1 i ; y v 1 i 6 = 0 : 2. Si r 2 : determina si existe p 2 Q q tal que p v 1 > 0 y p v i 0 para i desde 2 hasta r 1 ; para ello usar de manera recurrente el algoritmo II{C.2. 3. Si no existe p; devolver ; y parar. 4. Si p v r 0 ; devolver w = p y parar. 5. Sea v 0 i = v i p v i p v r v r ; 8 i = 1 ; : : : ; r 1 : Determinar si existe p 0 2 Q q tal que p 0 v 0 1 > 0 y p 0 v 0 i 0 ; i = 2 ;:::;r 1 usando de manera recurrente el algoritmo II{C.2. 6. Si existe p 0 ; devolver w = p 0 p 0 v r p v r p y parar. 7. Devolver ; : Ahora podemos usar este algoritmo para encontrar, caso de que exista, una N soluci on particular de un sistema diof antico homog eneo. Algoritmo II–C.3 N soluci on particular de un sistema homog eneo. Entrada: La matriz del sistema diof antico Gx = 0 : Salida: Una N soluci on no trivial, u; del sistema caso de que exista, o la soluci on trivial si es la unica. 1. Si r = 1 ; tenemos una unica inc ognita, luego la soluci on es trivial. 2. Si r 2 ; sea C la matriz cuyas las son una base del Q espacio vectorial dado por Gx = 0 : Tomamos v 1 ;:::;v r las columnas de C:
44 C alculo de una N soluci on particular 3. Para i = 1 ; : : : ; r : a ) Determinar usando el algoritmo II{C.2 si existe un vector w tal que w v i > 0 y w v j 0 ; para j 6 = i; j = 1 ; : : : ; r: b )Si existe w; sea u 0 = ( w v 1 ;:::;w v r ) 2 Q r : Devuelve m nu 0 2 N r ; con m el m nimo com un m ultiplo de los denominadores de u 0 ; y n el m aximo com un divisor de las coordenadas de mu 0 : Parar. 4. Devuelve u = 0 : Lema de Farkas para sistemas no homog´eneos En [PCVT98], generalizamos el uso del lema de Farkas para encontrar N soluciones particulares a sistemas diof anticos no homog eneos. Supongamos jado el sistema diof antico no homog eneo (II{B.1). Para encontrar una N soluci on particular a dicho sistema, consideramos el sistema homogeneizado ( b j G ) x = 0 : Si sobre este sistema homog eneo, consideramos las notaciones dadas en II{C, tenemos que el sistema no homog eneo tiene una N soluci on, u; si y s olo si 9 (1 ;u ) 2 L con u 2 N r ; y si y s olo si 9 w 2 Q q con w v 1 = 1 y w v i 2 N 8 i = 2 ;:::;r + 1 : De manera an aloga al caso homog eneo, la relaci on entre la N soluci on y w es (1 ; u ) = w 1 c 1 + + w q c q = ( w v 1 ; : : : ; w v r +1 ) : Por lo tanto, para poder generalizar el m etodo basado en el lema de Farkas a sistemas no homog eneos, tenemos que resolver el siguiente problema: dados v 1 ; : : : ; v r +1 2 Q q ; determinar si existe w 2 Q q tal que w v 1 = 1 y w v i 2 N 8 i = 2 ;:::;r +1 : Veamos como podemos resolverlo. Denotaremos por W al Q espacio vectorial generado por v 2 ; : : : ; v r +1 :
Captulo II: Sistemas diof anticos: N soluciones 45 Si v 1 = 2 W; denotamos por ^ v 1 a la proyecci on ortogonal de v 1 en W ? : Es claro que ^ v 1 6 = 0 y v 1 ^ v 1 > 0 : En este caso, es suciente tomar w =^ v 1 v 1 ^ v 1 ; porque w v 1 = 1 y w v i = 0 ; 8 i = 2 ;:::;r + 1 : Si v 1 2 W; podemos distinguir dos subcasos: Si v 1 = P r +1 i =2 i v i con i 0 ; entonces no existe w (como vimos en la demostraci on de II{C.1). En otro caso, tomamos v 1 = P r +1 i =2 i v i : Sea A la matriz cuyas las corresponden a los vectores v 2 ;:::;v r +1 ; y denotemos por L 1 Q r el Q espacio vectorial generado por las columnas de A: Suponemos que Cx = 0 son unas ecuaciones impl citas de L 1 ; y denimos S 1 = f s 2 N r j Cs = 0 g : N otese que el sistema que nos dene al semigrupo S 1 es homog eneo. Sea f s 1 ;:::;s h g un sistema de generadores de S 1 : Denotamos por D; a la matriz ( s 1 jj s h ) ; y por m = ( m 1 ; : : : ; m h ) := ( 2 ; : : : ; r +1 ) D: Con estas notaciones tenemos el siguiente resultado. Proposici´on II–C.4 Son equivalentes: 1. 9 w 2 Q q con w v 1 = 1 y w v i 2 N ; 8 i = 2 ;:::;r + 1 : 2. 9 y 2 N h tal que m 1 y 1 + + m h y h = 1 : En este caso, es suciente tomar w como una soluci on particular de Ax = z; con z = Dy: Demostraci´on. 1 ) 2 : Sea z = Aw: Es claro que z 2 S 1 ; y entonces existe y 2 N h tal que z = Dy: De la combinaci on lineal v 1 = P r +1 i =2 i v i y la igualdad w v 1 = 1 ; tenemos que ( 2 ;:::; r +1 ) z = 1 : Entonces m 1 y 1 + + m h y h = 1 :
46 C alculo de una N soluci on particular 2 ) 1 : Sea z = Dy: Como z 2 S 1 L 1 ; deducimos que los rangos de A y de ( A j z ) son iguales, luego el sistema es compatible. Sea w una soluci on. Para nalizar la demostraci on, basta se~ nalar que la combinaci on lineal v 1 = P r +1 i =2 i v i implica que w v 1 = ( 2 ; : : : ; r +1 ) Aw = ( 2 ;:::; r +1 ) Dy = 1 : Como corolario de la proposici on anterior, tenemos que un sistema diof antico admite una N soluci on si y s olo si la admite una ecuaci on construida a partir de el: m 1 y 1 + + m h y h = 1 : Al ser la proposici on anterior constructiva y teniendo distintos m etodos efectivos para resolver en N una ecuaci on diof antica, vamos a tener, a partir del siguiente algoritmo, un nuevo algoritmo para calcular una N soluci on a un sistema diof antico. Algoritmo II–C.5 Algoritmo de Farkas generalizado ([PCVT98]). Entrada: Un conjunto de vectores v 1 ;:::;v r +1 2 Q q ; con r 1 : Salida: Un vector, caso de existir, w 2 Q q tal que w v 1 = 1 y w v i 2 N ; 8 i = 2 ;:::;r + 1 : 1. Consideramos W el Q espacio vectorial generado por v 2 ;:::;v r +1 : 2. Si v 1 = 2 W; tomamos ^ v 1 la proyecci on ortogonal de v 1 en W ? : Devolvemos w = ^ v 1 v 1 ^ v 1 y paramos. 3. En otro caso, aplicamos el algoritmo II{C.2: Si v 1 = P r +1 i =2 i v i con i 0 ; entonces no hay soluci on y paramos. En otro caso continuamos. 4. Tomamos una combinaci on v 1 = P r +1 i =2 i v i : 5. Sea A la matriz cuyas las corresponden a los vectores v 2 ;:::;v r +1 : Consideramos Cx = 0 unas ecuaciones impl citas del Q espa-
Captulo II: Sistemas diof anticos: N soluciones 47 cio vectorial generado por las columnas de A; L 1 Q r : Computamos f s 1 ;:::;s h g un sistema de generadores de S 1 = f s 2 N r j Cs = 0 g usando el algoritmo II{B.7. En este algoritmo usaremos II{C.6 para calcular una N soluci on particular. 6. Sea ( m 1 ; : : : ; m h ) = ( 2 ; : : : ; r +1 ) D; con D = ( s 1 jj s h ) : Si existe y 2 N h tal que m 1 y 1 + + m h y h = 1 ; devolvemos w una soluci on particular de Ax = z con z = Dy; y paramos. En otro caso no hay soluci on, luego paramos. De este algoritmo podemos obtener otro que nos da una N soluci on particular de un sistema diof antico no homog eneo. Algoritmo II–C.6 N soluci on particular usando el lema de Farkas para sistemas no homog eneos. Entrada: Un sistema Gx = b como (II{B.1). Salida: Una N soluci on particular si existe. 1. Si b = 0 ; usamos al algoritmo II{C.3. 2. Si r = 1 ; tenemos una unica inc ognita, luego detectar una N soluci on es trivial. 3. Si r 2 ; sea M = ( b j G ) : Sea c 1 ;:::;c q una base del Q espacio vectorial dado por las soluciones de Mx = 0 : 4. Sean v 1 ;:::;v r +1 2 Q q los vectores correspondientes a las columnas de la matriz cuyas las son los c 1 ;:::;c q : A estos vectores les aplicamos el algoritmo II{C.5. Si existe w 2 Q q tal que w v 1 = 1 y w v i 2 N ; entonces la salida es u donde (1 ; u ) = w 1 c 1 + + w q c q = ( w v 1 ;:::;w v r +1 )
48 C alculo de una N soluci on particular y paramos. En otro caso, no hay soluci on, luego paramos. Es de destacar que los algoritmos enlazados anteriores no son c clicos ya que tanto en II{C.5 como en II{B.7 se va reduciendo el n umero de variables hasta llegar a una sola. En ese caso es trivial dar una N soluci on. M´etodo usando Bases de Gr¨obner Tanto en [POT91] como en [CT91], los autores usan las bases de Gr obner y la Teor a de Eliminaci on para resolver el problema del c alculo de N soluciones de un sistema diof antico. Dado un sistema diof antico como (II{B.1), consideramos el anillo de polinomios k [ Z 1 ; : : : ; Z r ;Y 1 ;:::;Y m ;T ] y el ideal denido por I = < Y 1 Y m T 1 ; Y G ( e 1 ) + Y G ( e 1 ) Z 1 ; Y G ( e 2 ) + Y G ( e 2 ) Z 2 ;:::;Y G ( e r ) + Y G ( e r ) Z r > : Teorema II–C.7 Con las notaciones anteriores: 1. Gx = 0 tiene una N soluci on si y s olo si existe en I un binomio de la forma Z 1 : En tal caso, es una N soluci on. 2. Gx = b tiene una N soluci on si y s olo si Y c T d = Z m od I; con d 2 N tal que c = b d ( 1 ; 1 ;:::; 1) 2 N r : En tal caso, es una N soluci on. Demostraci´on. Ver [POT91] y [CT91]. Del anterior teorema se obtiene un algoritmo para saber si un sistema diof antico, tanto homog eneo como no homog eneo, posee una N soluci on. Este algoritmo pasa, en el caso no homog eneo, por calcular una base de Gr obner de I respecto a un orden de eliminaci on de T e Y y reducir Y c T d respecto de ella ([CT91]). Si el resultado de esta reducci on
Captulo II: Sistemas diof anticos: N soluciones 49 es Z ; tenemos una N soluci on. En otro caso, el sistema no tiene N soluciones. En el caso homog eneo, hay que comprobar si tenemos alg un binomio de la forma Z 1 en una base de Gr obner reducida de I respecto del orden por el cual comparamos primero lexicogr acamente las Z i ; y en caso de igualdad miramos el grado, y nalmente el orden lexicogr aco ([POT91]). Si en esa base de Gr obner hay un binomio de la forma Z 1 ; tenemos una N soluci on. En otro caso, el sistema no tiene N soluciones. Si la matriz del sistema estuviese formada por elementos enteros no negativos ( G ( e i ) 0), podr a eliminarse la variable T y el ideal I que tomar amos ser a I = < Y G ( e 1 ) Z 1 ; Y G ( e 2 ) Z 2 ;:::;Y G ( e r ) Z r > : Con este supuesto trabajar amos con r + m variables. Aunque como hemos visto, en general trabajamos con r + m + 1 variables. En II{D.5 veremos una optimizaci on y generalizaci on de este c alculo usando ideales de semigrupos. II–D. SISTEMAS DIOF´ ANTICOS EN CONGRUENCIAS Un tema apenas tratado en la literatura y que es la base de algunas partes de esta memoria, es el estudio y c alculo de las N soluciones de sistemas diof anticos en congruencias. Es decir, sistemas del tipo ( Sist ) 8 > > > > > > > > > > > > > > < > > > > > > > > > > > > > > : n 11 x 1 + n 12 x 2 + + n 1 r x r = b 1 n 21 x 1 + n 22 x 2 + + n 2 r x r = b 2 . . .. . .. . . n h 1 x 1 + n h 2 x 2 + + n hr x r = b h n ( h +1)1 x 1 + n ( h +1)2 x 2 + + n ( h +1) r x r = b h +1 m od a 1 . . .. . .. . .. . . n ( h + s )1 x 1 + n ( h + s )2 x 2 + + n ( h + s ) r x r = b h + s m od a s
56 Notas Cuadro II.1. Algoritmos II{B.7 + II{C.6 versus II{B.7 + II{D.5 Sistemas Homog eneos Usando bases de Gr obner Usando lema de Farkas 1 3 2 5 2 sec., s = [1 ; 1 ; 1 ; 0] 5 sec., s = [5 ; 0 ; 0 ; 1] 1 2 1 2 2 1 1 2 ! 4 sec., s = [0 ; 4 ; 2 ; 3] 16 sec., s = [2 ; 6 ; 0 ; 5] 1 2 3 5 2 1 4 5 ! 5 sec., s = [7 ; 0 ; 1 ; 2] 7 sec., s = [5 ; 5 ; 0 ; 3] 3 1 2 3 3 7 2 1 ! 7 sec., s = [2 ; 1 ; 1 ; 1] 111 sec., s = [8 ; 6 ; 9 ; 0] 4 1 0 1 0 2 0 1 0 2 3 1 ! 5 sec., s = [0 ; 0 ; 1 ; 0 ; 0 ; 0] 1961 sec., s = [1 ; 8 ; 0 ; 4 ; 0 ; 0] 0 B @ 1 2 3 0 1 0 1 0 3 0 1 2 0 0 1 1 C A 4 sec., s = [0 ; 3 ; 0 ; 1 ; 6] 9 sec., s = [0 ; 3 ; 0 ; 1 ; 6] 0 B B B @ 2 0 1 0 1 0 0 0 2 0 3 1 1 3 0 1 1 0 2 0 0 2 1 0 1 C C C A 17 sec., s = [1 ; 0 ; 2 ; 3 ; 4 ; 8] 500 sec., s = [1 ; 0 ; 2 ; 3 ; 4 ; 8] 0 B @ 0 1 2 3 0 0 1010 3 0 1 4 2 0 0 1 1 C A 102 sec., s = [2 ; 2 ; 1 ; 0 ; 1 ; 4] Parado a los 40.000 sec., s = [18 ; 6 ; 3 ; 0 ; 7 ; 0] 1 2 3 2 4 2 1 3 2 5 ! 49 sec., s = [1 ; 3 ; 1 ; 2 ; 0] Parado a los 40.000 sec., s = [9 ; 3 ; 5 ; 0 ; 0]
CAP ITULO III M odulos de Sicigias En este cap tulo vamos a estudiar la resoluci on libre minimal del algebra de un semigrupo Nakayama con torsi on. En particular, comenzaremos deniendo tal resoluci on y dando el m etodo aparecido en [BCMP98a] para calcular dicha resoluci on. Este m etodo utiliza la homolog a reducida de ciertos complejos simpliciales asociados a los elementos del semigrupo. Empezaremos por explicar los pasos principales del algoritmo aparecido en [BCMP98b] para calcular el 0-m odulo de sicigias (ideal del semigrupo). La naturaleza de este algoritmo es completamente distinta a los explicados en el cap tulo I, y est a basado en combinatoria y en los m etodos de programaci on lineal entera del cap tulo II. Es precisamente esta losof a la que seguiremos en cap tulos sucesivos para dar un algoritmo que calcula sistemas minimales de generadores de los m odulos de sicigias de orden superior, y por tanto la resoluci on libre minimal de k [ S ] : III–A. M´ ODULOS DE SICIGIAS De nuevo vamos a considerar un semigrupo, S; cancelativo, abeliano, nitamente generado y con elemento neutro. En estas condicio-
58 M odulos de Sicigias nes, es conocido, y ya lo hemos empleado con anterioridad, que nuestro semigrupo es isomorfo a un subsemigrupo de un grupo abeliano nitamente generado, G ( S ) (ver [BCMP98b]). Por ello, podemos suponer sin p erdida de generalidad que, S Z h Z =a 1 Z Z =a s Z con a = ( a 1 ; : : : ; a s ) 2 Z s : Sea f n 1 ;:::;n r g un conjunto de generadores de S: Vamos a suponer en lo sucesivo que nuestro semigrupo es Nakayama, es decir, verica la condici on S \ ( S ) = f 0 g : Considerando k un cuerpo, denotamos por R al anillo de polinomios k [ X 1 ;:::;X r ] ; y por k [ S ] a la k algebra asociada a S: Sea m = ( X 1 ; : : : ; X r ) el ideal maximal irrelevante de R: La k algebra, k [ S ] ; es un anillo S graduado k [ S ] = m 2 S k [ S ] m ; donde las componentes homog eneas son k [ S ] m = km: R es tambi en un anillo S graduado, dando a cada variables X i el grado n i : Por lo tanto podemos escribir R = m 2 S R m ; donde R m es el k espacio vectorial generado por los monomios de grado m: Es conocido que estos espacios vectoriales son de generaci on nita (ver [BCMP98b, nota 1.3]). La S graduaci on anterior nos permite enunciar el lema de Nakayama para m odulos S graduados. Proposici´on III–A.1 Sea S un semigrupo cancelativo, abeliano, nitamente generado, con elemento neutro y Nakayama. Si Q es un R m odulo S graduado tal que m Q = Q; entonces se tiene que Q = 0 : Demostraci´on. Ver [BCMP98b, proposici on 1.4].
Captulo III: M odulos de Sicigias 59 El homomorsmo de k algebras (I{A.1) dado por ' 0 : R ! k [ S ] ' ( X i ) = n i ; es un homomorsmo graduado de grado cero, y su n ucleo es, como ya vimos, un ideal homog eneo, I: Este ideal depende directamente del sistema de generadores de S tomado, pero, consideremos el sistema que consideremos, se tiene que k [ S ] = R=I: Luego conocer el ideal es conocer el algebra del semigrupo. Denotemos por V 0 al cociente I= m I; y por V 0 ( m ) a los cocientes I m = ( m I ) m ; con m 2 S: Por III{A.1, tenemos que un conjunto nito de elementos de I lo genera si y s olo si las clases de sus elementos en V 0 generan este espacio vectorial. Adem as, un sistema minimal de generadores de I tiene tantos elementos de grado m como dim k V 0 ( m ) : Los espacios vectoriales V 0 ( m ) son nulos salvo una cantidad nita por ser R un anillo noetheriano. Llegados a este punto, si uno escoge un sistema minimal y homog eneo de generadores de I; f f 1 ;:::;f b 1 g ; puede construir un nuevo homomorsmo de k algebras ' 1 : R b 1 ! R ' 1 ( e j ) = f j con j = 1 ;:::;b 1 ; b 1 := P m 2 S dim k V 0 ( m ) y e j el j esimo generador est andar de R b 1 : De la misma manera podemos construir recurrentemente los morsmos ' i +1 : R b i +1 ! R b i ; (III{A.1) que corresponden a tomar un conjunto minimal y homog eneo de generadores en N i = ker( ' i ) R b i ; con N 0 = I y b 0 = 1 ; y hacer que la imagen de cada uno de los generadores est andar de R b i +1 sea un generador de
60 M odulos de Sicigias N i : Si para cada j entre uno y b i ; el grado del j esimo generador de N i es m j 2 S; R b i +1 tiene como elementos homog eneos las b i +1 uplas cuya j esima componente es un elemento homog eneo en R de grado m m j : Con este proceso construimos una resoluci on libre minimal y S graduada para el R m odulo k [ S ] dada por ! R b i +1 ' i +1 ! R b i ' i ! ! R b 2 ' 2 ! R b 1 ' 1 ! R ' 0 ! K [ S ] ! 0 ; con b i +1 = P m 2 S dim k V i ( m ) ; y V i ( m ) = ( N i ) m ( m N i ) m : El entero b i +1 es nito por ser R noetheriano. El n umero de elementos de grado m en un sistema minimal de generadores del i esimo m odulo de sicigias N i es dim k V i ( m ) : El teorema de Auslander-Buchbaum (ver [VAS98]) nos garantiza que b i es nulo a partir de un ndice i sucientemente grande. Concretamente se tiene el siguiente resultado. Proposici´on III–A.2 Con las notaciones anteriores, la resoluci on libre minimal S graduada para el algebra k [ S ] tiene la forma 0 ! R b p ! ! R b 1 ! R ! K [ S ] ! 0 con r rg ( G ( S )) p r: Visto esto, para obtener el i esimo paso de la resoluci on libre minimal de k [ S ] ; podemos calcular, en primer lugar, los distintos m 2 S tales que los espacios V i ( m ) son no nulos, y despu es una base de cada espacio vectorial. Los espacios V i ( m ) los vamos a determinar mediante espacios isomorfos a ellos. Veamos ahora cu ales ser an esos espacios. ~ H i ( m ) = V i ( m ) Para comenzar, sea el conjunto formado por los sub ndices de los generadores de S; i.e. := f 1 ; 2 ; : : : ; r g : Dado F ; vamos a denotar
Captulo III: M odulos de Sicigias 61 por n F al elemento P i 2 F n i ; y por n ; al cero. Con esta notaci on, para cada m 2 S; podemos denir el siguiente complejo simplicial. Definici´on III–A.3 Sea m 2 S; llamaremos complejo asociado a m al complejo simplicial abstracto m := f F j m n F 2 S g : Fijado un elemento m en S; y escogida una orientaci on en cada cara de m ; podemos considerar la homolog a reducida, ~ H ( m ) ; del complejo m con valores sobre el cuerpo k: Construy amosla. Sea ~ C i ( m ) el k espacio vectorial generado por las caras de dimensi on i de m ; donde dim F := ]F 1 (dim ; := 1). Sea tambi en @ i la aplicaci on k lineal @ i :~ C i ( m ) ! ~ C i 1 ( m ) @ i ( F ) = P F 0 2 m ; dim F 0 = i 1 FF 0 F 0 donde FF 0 = 0 si F 0 6 F , y FF 0 = 1 si F 0 F ( FF 0 ser a uno si la orientaci on inducida de F en F 0 es igual a la escogida en F 0 ; en otro caso FF 0 = 1). Fijemos nuestra atenci on sobre las aplicaciones ~ C i +1 ( m ) @ i +1 ! ~ C i ( m ) @ i ! ~ C i 1 ( m ) con i 0 : Denotaremos por ~ Z i ( m ) a ker( @ i ) ; y por ~ B i ( m ) a Im ( @ i +1 ) : A los elementos de ~ Z i ( m ) se les denomina ciclos y a los de ~ B i ( m ) bordes. Entonces tenemos que ~ H i ( m ) := ~ Z i ( m ) = ~ B i ( m ) : Ahora estamos en condiciones de enunciar el resultado que nos va a permitir calcular V i ( m ) : Teorema III–A.4 Sea S un semigrupo abeliano, nitamente generado, cancelativo, con elemento neutro y Nakayama. Fijado un conjunto de generadores no
62 M odulos de Sicigias nulos de S; f n 1 ;:::;n r g ; un cuerpo conmutativo k; y considerando la resoluci on libre minimal S graduada de k [ S ] y los complejos m ; se tiene ~ H i ( m ) = V i ( m ) (como k espacios vectoriales) ; para todo m 2 S; y i 0 : Demostraci´on. Ver [BCMP98a, teorema 2.1]. Adem as, en [BCMP98a, teorema 3.3], los autores dan de manera expl cita el isomorsmo del teorema anterior. El resto de esta memoria consiste fundamentalmente en probar que se tiene un algoritmo, basado en m etodos combinatorios, para computar sistemas minimales de los m odulos de sicigias de k [ S ] : Concretamente, Algoritmo III–A.5 Con las notaciones anteriores Entrada: Un conjunto de generadores f n 1 ;:::;n r g de S: Salida: Un sistema minimal de generadores del i esimo m odulo de sicigias de k [ S ] : 1. Calcular el conjunto C i := f m 2 S j ~ H i ( m ) 6 = 0 g : 2. Calcular, D ( m ) ; una base del espacio vectorial ~ H i ( m ) ; con m 2 C i : 3. Calcular M el conjunto imagen de S m 2 C i D ( m ) ; para distintos i; mediante el isomorsmo III{A.4. M es un conjunto minimal de generadores del i esimo m odulo de sicigias de k [ S ] : El algoritmo anterior ser a realmente un algoritmo si todos los pasos se pueden realizar de manera efectiva. En particular, tienen que ser efectivos los m etodos que utilicemos para resolver dos problemas: calcular C i y calcular una base de ~ H i ( m ) : El segundo problema se puede resolver de manera algor tmica mediante algebra lineal realizando los
Captulo III: M odulos de Sicigias 63 siguientes pasos: Se determina m usando los m etodos de programaci on lineal entera explicados en el cap tulo II. Se determina ahora ~ H i ( m ) := ~ Z i ( m ) = ~ B i ( m ) usando algebra lineal ordinaria en espacios vectoriales sobre un cuerpo k: De hecho, una vez conocidas las caras de m y jada una orientaci on, las aplicaciones @ i se pueden explicitar f acilmente mediante matrices. Un ejemplo de esto lo veremos en el cap tulo VI. En la siguiente secci on, vamos a dar un m etodo efectivo para calcular C 0 ; resolviendo el c alculo de C i ; para cualquier i; en cap tulos posteriores. III–B. 0-M´ ODULO DE SICIGIAS Veamos ahora un algoritmo combinatorio que nos permite, no s olo calcular, sino caracterizar, el conjunto de los grados que aparecen en un conjunto minimal de generadores del ideal de un semigrupo, C 0 : Por tratarse de homolog a reducida, son equivalentes: que ~ H 0 ( m ) 6 = 0 y que el complejo m es no conexo (ver [BCMP98b]). N otese que si M = X 1 1 X r r es un monomio en R de grado m 2 S; tenemos que supp ( M ) 2 m : Adem as, si A 2 m es una cara maximal de m ; se tiene que existe un monomio de grado m cuyo soporte es A: Denotemos por B al conjunto B = f X X j r X i =1 i n i = r X i =1 i n i ; i ; i 0 g : Sea m no conexo, y G m B un subconjunto de binomios de grado m: Consideremos el siguiente grafo con v ertices las componentes conexas de m (supondremos que hay s ): si b = M M 0 2 G m ; tomamos una
64 0-M odulo de Sicigias arista cuyos extremos sean las componentes conexas que contengan a supp ( M ) y supp ( M 0 ) : Diremos que G m es un arbol generador para m si es un grafo conexo con s v ertices y s 1 aristas, es decir, un arbol en el sentido usual. La relaci on entre estos arboles y el ideal de S la explicitamos en el siguiente resultado. Teorema III–B.1 Sea G B : Son equivalentes: 1. G = S m 2 S G m ; donde G m es un arbol generador para m si este es no conexo, y G m = ; en otro caso. 2. G es un conjunto minimal de generadores de I: Demostraci´on. Ver [BCMP98b, teorema 2.5]. A partir del anterior teorema se obtiene un m etodo para calcular un sistema minimal de generadores de I : 1. Determinar m 2 S tales que m es no conexo ( C 0 ). 2. Si m es no conexo (i.e. m 2 C 0 ), determinamos los monomios M i de grado m con supp ( M i ) 2 C i donde C 1 ;:::;C s son las componentes conexas de m : Tomamos G m = f M 1 M 2 ;:::;M 1 M s g : Este proceso ser a un algoritmo si podemos calcular de manera algor tmica los m 2 S tales que su m es no conexo, i.e. ~ H 0 ( m ) 6 = 0 : Adem as, necesitamos calcular las componentes conexas. Pues bien, ese algoritmo existe y pasaremos ahora a describirlo. A partir de aqu consideraremos que el conjunto est a ordenado. Comencemos dando alguna nueva notaci on. Notaci´on III–B.2 Sea A = f i 1 ;:::;i p g B con A 6 = ; y B 6 = : Denotaremos: E ( A; B ) al conjunto de los = ( 1 ;:::; p ) 2 N p tal que 1. i j 6 = 0 ; para 1 j p:
Captulo III: M odulos de Sicigias 65 2. Es posible escribir p X j =1 i j n i j = X t= 2 A t n t con t 2 N y t 6 = 0 para al menos un t = 2 B: ~ E ( A; B ) = E ( A; B ) + N p : H E ( A; B ) = f 2 E ( A; B ) j es minimal g : Diremos que los elementos de H E ( A; B ) son los v ertices de ~ E ( A;B ) : A partir de estas notaciones podemos considerar la siguiente denici on. Definici´on III–B.3 Sea m 2 S; y sea A = f i 1 ;:::;i p g B con A 6 = ; y B 6 = : Diremos que A est a m aislado de n B si se cumple: 1. Es posible escribir m = p X j =1 i j n i j = X t= 2 B t n t con i j ; t 2 N ; y i j 6 = 0 para todo j: 2. ( i 1 ; : : : ; i p ) 2 H E ( A;B ) : 3. ( l 1 ; : : : ; l s ) = 2 ~ E ( A 0 ;B ) ; para cada A 0 = f i 1 ; : : : ; i s g A; y A 0 6 = A: Para detectar si un conjunto, A; est a m aislado de n B podemos ver las siguientes condiciones: 1. Si existe un monomio de grado m con soporte contenido en n B: 2. Si existe ( i 1 ;:::; i p ) 2 H E ( A; B ) tal que m = P p j =1 i j n i j : 3. 8 A 0 = f l 1 ;:::;l s g A; y 8 ( 0 l 1 ;:::; 0 l s ) 2 H E ( A 0 ;B ) ; ( 0 l 1 ;:::; 0 l s ) ( l 1 ;:::; l s ) : El problema es determinar H E ( A 0 ; B ) ; 8 A 0 A: Esto se resuelve
Captulo IV: C alculo del Primer M odulo de Sicigias 73 Lema IV–A.3 Sea m 2 S tal que ~ H 1 ( m ) 6 = 0 : Existen F y un F hueco de m cuyas caras son F j ; vericando c = t X j =1 j F j 2 Z 1 ( m ) n B 1 ( m ) ; con j = 1 ; 8 j = 1 ; : : : ; t: Demostraci´on. Por ser ~ H 1 ( m ) 6 = 0 ; podemos considerar el menor entero t tal que exista d = t X j =1 j F j 2 Z 1 ( m ) n B 1 ( m ) ; con j 6 = 0 8 j = 1 ;:::;t: En tal caso, F i 6 = F j 8 i 6 = j: Supongamos como punto de partida que F 1 = f i 1 ; i 2 g : Entonces, para alg un 1 = 1 ; @ 1 d = 1 1 ( f i 2 g f i 1 g ) + = 0 : En este caso, debe existir un conjunto F j con j 6 = 1, y tal que i 2 pertenezca a el. Por comodidad de notaci on, vamos a suponer que j = 2 ; y que F 2 = f i 2 ; i 3 g : Es claro que i 1 6 = i 3 porque F 1 6 = F 2 : An alogamente, existe un conjunto F 3 = f i 3 ; i 4 g ( t 3 ; primera condici on de F hueco ) donde, trivialmente, i 3 6 = i 4 y i 4 6 = i 2 : Veamos las posibilidades de surgen: Si i 4 = i 1 ; tenemos F 1 = f i 1 ; i 2 g ; F 2 = f i 2 ;i 3 g ; F 3 = f i 3 ; i 1 g : Entonces podemos denir los elementos d 1 = 1 F 1 + 2 1 F 2 + 3 1 F 3 ; d 2 = ( 2 2 1 ) F 2 + ( 3 3 1 ) F 3 + t X j =4 j F j ; con i = 1 ; y tales que @ 1 d 1 = 0, y por lo tanto d 2 = d d 1 2 Z 1 ( m ) : Si suponemos que d 2 6 = 0 ; se tiene que, por ser t
74 Conjunto Finito de Chequeo minimal, d 2 2 B 1 ( m ) : En este caso, d 1 = 2 B 1 ( m ) ; y entonces t = 3 ; luego d 2 = 0 : Tomando c = (1 = 1 ) d 1 ya habr amos terminado la demostraci on. Si i 4 6 = i 1 ; y sabiendo que i 4 6 = i 2 ; e i 4 6 = i 3 ; tenemos que t 4. Al igual que antes, obtenemos que existe F j = f i 4 ;i 5 g ; i 5 6 = i 3 ; i 4 . De nuevo vamos a considerar j = 4 por comodidad de notaci on. Si tuvi esemos el caso i 5 = i 1 ; podemos seguir el razonamiento del punto anterior construyendo un elemento c = P 4 j =1 j F j 2 Z 1 ( m ) n B 1 ( m ) ; por lo que habr amos terminado. Si tuvi esemos el caso i 5 = i 2 ; podemos seguir el razonamiento del punto anterior construyendo un elemento c = P 4 j =2 j F j 2 Z 1 ( m ) n B 1 ( m ) : Pero esto entra en contradicci on con t 4 : Por lo tanto, tomamos F 5 = f i 5 ; i 6 g y continuamos con este proceso. Esta construcci on es nita al existir un n umero nito de posibilidades para i j : Entonces, podemos concluir que existe c = t X j =1 j F j 2 Z 1 ( m ) n B 1 ( m ) ; con F 1 = f i 1 ; i 2 g ; F 2 = f i 2 ;i 3 g ; F 3 = f i 3 ; i 4 g ; : : : ; F t = f i t ; i 1 g ; para unos determinados j = 1 8 j = 1 ;:::;t . Lo que debemos probar ahora es que el pol gono denido por F 1 ; : : : ; F t es ciertamente un F hueco de m , donde F es el conjunto t [ j =1 F j : Para esto, s olo nos queda probar sobre ; la segunda condici on de la denici on de F hueco. Supongamos que existe F 0 F; F 0 6 = F j ; ]F 0 2 y F 0 2 m : En ese caso, deben existir a su vez dos enteros i p ; i q 2 F 0 con p < q; tales que f i p ; i q g 6 = F j 6 = f i q ; i p g 8 j = 1 ;:::;t: Supongamos por comodidad que p = 1 y consideremos F 00 = f i 1 ; i q g : Entonces podemos rescribir c de la manera
Captulo IV: C alculo del Primer M odulo de Sicigias 75 siguiente c = P t j =1 j F j + t +1 F 00 t +1 F 00 = 1 F 1 + 2 F 2 + + q 1 F q 1 t +1 F 00 |{z } c 1 + t +1 F 00 + q F q + + t F t |{z } c 2 : Para un determinado t +1 = 1 ; se tiene que c 1 ;c 2 2 Z 1 ( m ) : Por lo tanto, o bien c 1 = 2 B 1 ( m ) o c 2 = 2 B 1 ( m ) ya que c = 2 B 1 ( m ) : Esto entra en contradicci on con que t es minimal. Como aclaraci on a la demostraci on anterior, cabe decir que los enteros i = 1 dependen directamente de la orientaci on considerada en m : Usando este lema, construir el conjunto nito de chequeo, C ; pasa por encontrar una condici on sobre los m 2 S para que exista un pol gono F hueco de m : Nosotros vamos a dar esta condici on a trav es de las bases de Hilbert de ciertos sistemas de ecuaciones diof anticos. Comencemos deniendo un orden sobre el semigrupo S: Definici´on IV–A.4 Sea > S el orden parcial sobre S denido por: m S m 0 si m m 0 2 S: Dado un subconjunto H de S; diremos que m 2 H es S minimal en H si m 6 > S m 0 ; 8 m 0 2 H: La existencia de elementos S minimales en un subconjunto H S viene garantizada por ser S Nakayama, ya que esto nos asegura que hay una cantidad nita de escrituras de m en funci on de los generadores de S ( [BCMP98b, proposici on 1.2]). Supongamos que es un F hueco de m ; entonces, existe ( i ) = ( ( i ) 1 ;:::; ( i ) r t +2 ) 2 N ( r t +2) t
76 Conjunto Finito de Chequeo vericando 8 > > > > > > < > > > > > > : m n F 1 = P j 2 ( n F ) [ F 1 (1) j n j mod a m n F 2 = P j 2 ( n F ) [ F 2 (2) j n j mod a . . . m n F t 1 = P j 2 ( n F ) [ F t 1 ( t 1) j n j mod a m n F t = P j 2 ( n F ) [ F t ( t ) j n j mod a ) 8 > > > > > < > > > > > : m = n F 1 + A F 1 (1) mod a m = n F 2 + A F 2 (2) mod a . . . m = n F t 1 + A F t 1 ( t 1) mod a m = n F t + A F t ( t ) mod a donde A F i 2 M ( h + s ) ( r t +2) ( Z ) es la matriz cuyas columnas son las de A indicadas por el conjunto ( n F ) [ F i . Dada f e 1 ; : : : ; e r g la base can onica de N r , denimos e F i := i ( X j 2 F i e j ) ; con i : N r ! N r t +2 la proyecci on que elimina las coordenadas correspondientes al conjunto F n F i , 1 i t . Con las notaciones anteriores, tenemos que existe una upla de uplas = ( (1) ; (2) ;:::; ( t ) ) 2 N ( r t +2) t tal que m = A F 1 (1) = A F 2 (2) = = A F t ( t ) mod a; y e con e := ( e F 1 ; e F 2 ; : : : ; e F t 1 ;e F t ) 2 N ( r t +2) t : Entonces, la forma de conseguir elementos m 2 S tales que sea un F hueco de m ; ser a computar algunas N soluciones, 2 N ( r t +2) t ; de los sistemas de ecuaciones diof anticos 0 B B B B B B B B B B @ A F 1 A F 2 0 0 0 0 0 0 A F 2 A F 3 0 0 0 0 0 0 A F 3 A F 4 0 0 0 ......... 0 0 0 0 0 A F t 1 A F t 1 C C C C C C C C C C A 0 B B B B B B B B B B @ (1) (2) . . . ( t 1) ( t ) 1 C C C C C C C C C C A = 0 ; donde cada tramo de ( h + s ) las del sistema est a en congruencia m odulo a ( mod a ). Un sistema de la forma anterior lo denotaremos por A = 0 mod ~ a;
Captulo IV: C alculo del Primer M odulo de Sicigias 77 donde A := 0 B B B B B B B B @ A F 1 A F 2 0 0 0 0 0 0 A F 2 A F 3 0 0 0 0 0 0 A F 3 A F 4 0 0 0 ......... 0 0 0 0 0 A F t 1 A F t 1 C C C C C C C C A 2 M ( t 1)( h + s ) ( r t +2) t ( Z ) ; y el s mbolo mod ~ a hace referencia a los tramos en congruencias. Denimos ahora R al conjunto de N soluciones R := f = ( (1) ;:::; ( t ) ) 2 N ( r t +2) t jA = 0 mod ~ a; e g : Sea H R el conjunto de los elementos minimales de R ; y R al subconjunto de S; R := f p 2 S j p = A F 1 (1) = = A F t ( t ) ; ( (1) ; (2) ; : : : ; ( t ) ) 2 R g : Sea C := f p 2 S j p es S minimal en R g : Relacionemos ahora todas estas deniciones y notaciones con el lema IV{A.3, dando un nuevo resultado mediante el cual vamos a poder atrapar los elementos de S con primera homolog a no nula. Proposici´on IV–A.5 Si ~ H 1 ( m ) 6 = 0 ; entonces existe un F hueco de m tal que m 2 C : Demostraci´on. Por el lema IV{A.3, tenemos que existe un F hueco de m cuyas caras F i verican que c = t X j =1 j F j 2 Z 1 ( m ) n B 1 ( m ) ; para ciertos j = 1 ; 8 j = 1 ;:::;t: Visto esto, es claro que m 2 R : Supongamos que m 2 R n C : En este caso, debe existir m 0 2 C y m 00 2 S; tales que m = m 0 + m 00 :
78 Conjunto Finito de Chequeo Si m 00 = 0 ; tendr amos probado que m 2 C ; y por lo tanto habr amos concluido. Supongamos entonces que m 00 6 = 0 ; m 00 = r X i =1 d i n i : Las posibilidades que se plantean son: Si i 2 F . Tomamos un ndice l tal que i = 2 F l . d i 6 = 0 ) m 00 n i 2 S m 0 2 C ) m 0 n F l 2 S 9 = ; ) m n F l n i 2 S ) F l [ f i g 2 m : Esto entra en contradicci on con el hecho de que es un F hueco de m : Si i = 2 F . d i 6 = 0 ) m 00 n i 2 S m 0 2 C ) m 0 n F j 2 S 9 = ; ) m n F j n i 2 S; 8 j = 1 ;:::;t: Entonces, consideramos F 0 j = F j [ f i g 2 m ; 8 j = 1 ;:::;t: Es f acil ver que c = @ 2 ( t X j =1 j F 0 j ) : Esto es una contradicci on ya que c = 2 B 1 ( m ). Gr acamente lo que ocurre es que la gura asociada con el F hueco es contr actil a un punto, tal y como se aprecia en la gura IV.2. Figura IV.2. Homolog a nula Hemos probado pues que m 2 C :
Captulo IV: C alculo del Primer M odulo de Sicigias 79 Relacionados los elementos S minimales con el lema IV{A.3, nos falta ver que los conjuntos C son nitos y se pueden calcular de manera efectiva. Para hacer esto vamos a considerar el conjunto H R := f p 2 S j p = A F 1 (1) = = A F t ( t ) ; = ( (1) ;:::; ( t ) ) 2 H R g : Por lo visto en el cap tulo II, y en particular por el lema de Dickson, tenemos que H R es un conjunto nito, y por lo tanto tambi en es nito H R : En el siguiente resultado usamos este hecho para demostrar que C es nito. Lema IV–A.6 Con las notaciones anteriores, se tiene que C H R : En particular, C es nito. Demostraci´on. Asumamos en un primer momento que m 2 C n H R : En particular tenemos que m 2 C ) 9 = ( (1) ;:::; ( t ) ) 2 R j m = A F 1 (1) = = A F t ( t ) : Al considerar que m = 2 H R ; no puede ser minimal en R . Entonces, existen 0 2 H R y 00 N soluci on de A 00 = 0 tal que = 0 + 00 : Si consideramos el elemento m 0 = A F 1 0 (1) 2 H R ; tenemos que m m 0 2 S; y por lo tanto m no es S minimal en R , porque m 6 = m 0 . Con ello hemos llegado a una contradicci on ya que m 2 C . C es un conjunto nito al serlo H R : Nota IV–A.7 N otese que el lema IV{A.6 nos relaciona los elementos S minimales de R con los minimales de R ; H R : Esto ser a una pieza clave a la hora de acotar el grado de las primeras sicigias del algebra k [ S ] que veremos en V{B.3. De hecho, en dicha secci on acotaremos los grados mediante su pertenencia a H R y no por estar en C : Aplicando ahora el lema IV{A.6, obtenemos un algoritmo para el c alculo de un conjunto nito C S para chequear los elementos
80 Conjunto Finito de Chequeo m 2 S tales que ~ H 1 ( m ) 6 = 0 : Algoritmo IV–A.8 Algoritmo de Chequeo Entrada: un conjunto de generadores f n 1 ;:::;n r g de S: Salida: C un conjunto nito para chequear los m 2 S tales que ~ H 1 ( m ) 6 = 0 : 1. G := ; y F := f F P () j ]F 3 g 2. Mientras F 6 = ; : a ) Para F 2 F y 8 pol gono cuyo conjunto de v ertices es F : 1) Calcular el subconjunto de N soluciones, H R 1 : 2) Calcular el conjunto C a partir de H R 2 : 3) G = G [ f ( m; ; F ) j m 2 C g b ) F = F n F: 3. C := f m 2 S j F hueco de m y ( m; ; F ) 2 G g Este algoritmo (IV{A.8) nos permite enunciar el siguiente teorema. Teorema IV–A.9 El conjunto C 1 de S -grados que aparecen en un sistema minimal de generadores del primer m odulo de sicigias de k [ S ] ; puede ser calculado de forma efectiva a trav es de los complejos simpliciales m , m 2 S . Demostraci´on. Inmediata del algoritmo IV{A.8. 1 Mediante II{A.4 y los algoritmos de c alculo de N soluciones del cap tulo II , se puede obtener este conjunto calculando las N soluciones minimales del sistema A = A e : 2 Usando el lema IV{A.6, podemos calcular C comprobando si las diferencias de elementos de H R est an o no en S; i.e. son S minimales
Captulo IV: C alculo del Primer M odulo de Sicigias 81 Usando III{A.4 hemos obtenido un nuevo algoritmo para computar un sistema minimal de generadores de N 1 : para todo m 2 C 1 , tomamos una base del espacio ~ H 1 ( m ) ; y a partir de ellos calculamos una base de V 1 ( m ) a trav es del isomorsmo ~ H 1 ( m ) = V 1 ( m ) : Corolario IV–A.10 Un conjunto minimal de generadores del primer m odulo de sicigias de k [ S ] puede ser determinado usando el algoritmo IV{A.8. Con m as detalle, para construir a partir del algoritmo IV{A.8 la resoluci on libre minimal de una variedad t orica, hay que aplicar el algoritmo III{A.5. El primer paso, el c alculo del conjunto C 1 ; se realiza a partir de un conjunto nito que lo contiene, C ; y que es la salida del algoritmo IV{A.8. Una vez obtenido C ; eliminamos de este conjunto los elementos m 2 C S tales que la homolog a reducida asociada a m es nula. El resultado de esta selecci on es el conjunto C 1 : IV–B. NOTAS Aunque el comportamiento computacional de los algoritmos que hemos descrito en este cap tulo no es bueno, su importancia radica en que nos permite comprender combinatoriamente el algebra asociada a un semigrupo. Esta es la diferencia principal con los algoritmos basados en bases de Gr obner (ver [EIS95, teorema de Schreyer]), ya que estos s olo son una herramienta de c alculo, y no una v a de comprensi on.
CAP ITULO V C alculo de la Resoluci on Libre Minimal INTRODUCCI´ ON Como en cap tulos anteriores, vamos a considerar S = < n 1 ;:::;n r > Z h Z =a 1 Z =a s con a = ( a 1 ; : : : ; a s ) 2 Z s ; y tal que S \ ( S ) = f 0 g : Sea = f 1 ;:::;r g ; y sea C i el conjunto C i := f m 2 S j ~ H i ( m ) 6 = 0 g : En este cap tulo vamos a dar un conjunto nito de chequeo, C 0 i ; tal que si existe un elemento en un sistema minimal de generadores del i esimo m odulo de sicigia de k [ S ] ; su grado pertenece a C 0 i ; es decir, C i C 0 i : Para ello generalizaremos los resultados obtenidos para i = 1 en el cap tulo anterior, sorteando los distintos problemas que surgen al generalizar. Adem as, a partir de los conjuntos C 0 i anteriores, acotaremos el grado de los elementos que aparecen en un sistema minimal de gene-
90 Conjunto Finito de Chequeo Consideremos la matriz con coecientes enteros A ( t ) := 0 B B B B B B B B B B @ A A 0 0 0 0 0 0 A A 0 0 0 0 0 0 A A 0 0 0 ......... 0 0 0 0 0 A A 1 C C C C C C C C C C A 2 M ( h + s )( t 1) rt ( Z ) y e := ( e F 1 ;:::;e F t ) 2 N rt : Entonces de cada i triangulaci on de F en m , se obtiene un vector = ( (1) ; : : : ; ( t ) ) 2 N rt vericando: 1. A ( t ) = 0 m od ~ a: 2. e 3. m = A (1) = ::: = A ( t ) : Como ya vimos en el cap tulo dedicado al c alculo de C 1 ; estamos buscando los elementos m 2 S tal que ~ H i ( m ) 6 = 0 ; luego tenemos que proceder de manera inversa. Fijemos F y = f F 1 ; : : : ; F t g una i triangulaci on de F; y consideremos ahora que m no est a jada. Vamos a buscar entonces los elementos m 2 S tales que es una i-triangulaci on de F en m : De manera an aloga al cap tulo IV, denimos los conjuntos: R := f = ( (1) ; : : : ; ( t ) ) 2 N rt j A ( t ) = 0 m od ~ a; e g ; R := f m 2 S j m = A (1) ; = ( (1) ; (2) ;:::; ( t ) ) 2 R g : Gracias al lema V{A.1, sabemos que si m 2 S verica que ~ H i ( m ) 6 = 0, podemos encontrar un conjunto de v ertices F y una i triangulaci on de F; tal que m 2 R . Tenemos pues que C i [ F [ R ;
Captulo V: C alculo de la Resoluci on Libre Minimal 91 donde la uni on es sobre todas las i triangulaciones de F; y F con ]F i + 2 ( F proviene del lema V{A.1). Como ya vimos, los conjuntos R no son, en general, nitos, pero si lo son los conjuntos formados por sus elementos minimales H R := f 2 R j es minimal para g : A partir de estos, denimos en S una serie de subconjuntos nitos con los que vamos a calcular C i ; H R := f m 2 S j m = A (1) ; = ( (1) ; (2) ;:::; ( t ) ) 2 H R g y C := f m 2 S j m es S minimal en R g : El conjunto H R es nito por serlo H R ; y C es tambi en nito por estar contenido en H R como nos prueba el siguiente lema. Lema V–A.6 En las condiciones anteriores, C H R : En particular, C es nito. Demostraci´on. Esta demostraci on es an aloga a la del lema IV{A.6. Estamos ya en condiciones de dar, al igual que para el caso de la primera sicigia IV{A.5, un resultado que nos atrape los elementos de S cuya i esima homolog a es no nula. Proposici´on V–A.7 Si m 2 S y~ H i ( m ) 6 = 0, entonces existe un conjunto de v ertices, F con ]F i + 2 ; y una i-triangulaci on de F en m ; tal que m 2 C : Demostraci´on. Al suponer que ~ H i ( m ) 6 = 0, existe un elemento no nulo en este conjunto, c 2 ~ Z i ( m ) n ~ B i ( m ) ; vericando que c = P t j =1 j F j ; con j 2 k n f 0 g para cualquier j = 1 ;:::;t , y con F j 6 = F l si j 6 = l . Por V{A.1, tomando F = S t j =1 F j y = f F 1 ;:::;F t g , tenemos que es una i triangulaci on de F en m y que m 2 R : Falta probar que, efectivamente, m 2 C :
92 Conjunto Finito de Chequeo Al estar m 2 R ; tenemos que es suma de un elemento S minimal en R ; m 0 2 C ; y de un elemento m 00 2 S : m = m 0 + m 00 : Si m 00 = 0 ; tendr amos que m = m 0 2 C y habr amos terminado la demostraci on. Supongamos que m 00 6 = 0 : m 00 2 S implica directamente que admite una escritura del tipo m 00 = P r j =1 j n j con j 2 N para cualquier j; 1 j r . Por comodidad en la demostraci on, supongamos que 1 6 = 0 : Si 1 2 F , aplicamos el lema V{A.1 para p = 1 : Entonces, existir a q; 1 q t; tal que 1 = 2 F q y F q [ f 1 g = 2 m : En cualquier caso, m 0 n F q 2 S porque m 0 2 C ; y m 00 n 1 2 S porque 1 6 = 0 : Tenemos entonces que m n F q n 1 = m 0 + m 00 n F q n 1 2 S: Este hecho contradice que F q [ f 1 g = 2 m y por lo tanto se deduce que 1 = 2 F . Al no estar 1 en F y ser m = m 0 + m 00 ; tenemos que m n F j n 1 2 S; para cualquier j . Sea F 0 j = F j [ f 1 g 2 m y sea c 0 = t X j =1 j F 0 j 2 ~ C i +1 ( m ) : Vamos a probar que @ i +1 c 0 = c: Para simplicar los c alculos vamos a considerar la orientaci on natural sobre las caras de m : Como @ i c = 0 ; tenemos que t X j =1 j F j F 0 = 0 ; para todo F 0 con dim( F 0 ) = i 1 : (V{A.1) Por otro lado @ i +1 ( c 0 ) = X dim ( F 00 )= i 0 @ t X j =1 j F 0 j F 00 1 A F 00 : Vamos a probar que c = X 1 = 2 F 00 0 @ t X j =1 j F 0 j F 00 1 A F 00 (V{A.2) y 0 = X 1 2 F 00 0 @ t X j =1 j F 0 j F 00 1 A F 00 : (V{A.3)
Captulo V: C alculo de la Resoluci on Libre Minimal 93 Si 1 = 2 F 00 y F 0 l F 00 6 = 0 ; para alg un 1 l t; tenemos que 1 = 2 F 00 F 0 l = F l [ f 1 g ; y entonces F 00 = F l : En cualquier caso, l es unica y tenemos t X j =1 j F 0 j F 00 = l F 0 l F 00 = l : Esto prueba (V{A.2). Para probar (V{A.3), supongamos que 1 2 F 00 y que F 0 l F 00 6 = 0 ; para alg un 1 l t: Como 1 2 F 00 F 0 l ; tenemos que F 00 = f 1 g [ F 0 con F 0 F 0 l y dim( F 0 ) = i 1 : Adem as como F 0 j F 00 = F j F 0 y usando (V{A.1), tenemos (V{A.3). Esto prueba que @ i +1 c 0 = c; y por lo tanto c 2 ~ B i ( m ) ; llegando a una contradicci on. La contradicci on surge de suponer que m 00 6 = 0 ; luego m 00 es realmente el elemento neutro de S; prob andose as nuestro resultado. Por la proposici on anterior (V{A.7) tenemos la inclusi on C i [ F [ C ; donde F , ]F i + 2 ; y es una i triangulaci on de F: Al ser cada C nito (lema V{A.6), hemos encontrado un conjunto nito conteniendo a C i : Podr amos considerar ya este conjunto como C 0 i ; pero a un podemos anar un poco m as el resultado mediante el siguiente hecho: si m 2 C con = f F 1 ; : : : ; F t g i triangulaci on de F , tenemos la garant a de que F j 2 m ; 8 j; 1 j t , pero puede ocurrir que F 2 m ; es decir, sea una i triangulaci on de F; pero no una i triangulaci on de F en m : Para descartar ese caso, denimos los conjuntos C 0 := f m 2 C j F = 2 m g ; que lo excluyen, y sus uniones C i ( F ) := [ C 0 : El siguiente teorema nos da, para cada i; un conjunto nito que contiene a los grados que aparecen en un sistema minimal de generadores del i esimo m odulo de sicigias de k [ S ] :
94 Conjunto Finito de Chequeo Teorema V–A.8 El conjunto, C i , de los S grados de las i esimas sicigias minimales de k [ S ], est a contenido en el conjunto nito C 0 i := [ F ;]F i +2 C i ( F ) : Al igual que ocurr a en el cap tulo IV, la construcci on de C 0 i puede realizarse de manera efectiva, ya que estamos calculando N soluciones a sistemas diof anticos. Por lo tanto, tenemos un algoritmo para construir un conjunto de grados que contienen al conjunto formado por los grados de un sistema minimal de generadores del i esimo m odulo de sicigias del algebra k [ S ] : Algoritmo V–A.9 Algoritmo de Chequeo Entrada: un conjunto de generadores f n 1 ;:::;n r g de S: Salida: C 0 i un conjunto nito para chequear los m 2 S tales que ~ H i ( m ) 6 = 0 : 1. G := ; y F := f F P () j ]F i + 2 g 2. Mientras F 6 = ; : a ) Para F 2 F y 8 i triangulaci on de F : 1) Calcular el subconjunto de N soluciones, H R 1 : 2) Calcular el conjunto C a partir de H R 2 : 3) G = G [ f ( m; ; F ) j m 2 C g b ) F = F n F: 3. C 0 i := f m 2 S j ( m; ; F ) 2 G; F = 2 m g Este algoritmo (V{A.9) nos permite enunciar el siguiente teorema an alogo a IV{A.9. 1 C alculo an alogo a IV{A.8. 2 C alculo an alogo a IV{A.8.
Captulo V: C alculo de la Resoluci on Libre Minimal 95 Teorema V–A.10 El conjunto C i de S -grados que aparecen en un sistema minimal de generadores del i esimo m odulo de sicigias de k [ S ] ; puede ser calculado de forma efectiva a trav es de los complejos simpliciales m , m 2 S . Demostraci´on. Inmediata del algoritmo V{A.9. Este teorema, junto con el algoritmo III{A.5, nos permiten enunciar el siguiente corolario. Corolario V–A.11 Un conjunto minimal de generadores del i esimo m odulo de sicigias de la resoluci on libre minimal de una variedad t orica puede ser determinado usando el algoritmo V{A.9. La forma de obtener el conjunto minimal de generadores que nos reere el corolario anterior pasa por aplicar III{A.5. Una vez obtenido un superconjunto nito C 0 i que contiene a C i ; hay que eliminar de C 0 i los elementos cuya homolog a asociada a su complejo simplicial sea nula. As obtenemos el conjunto C i : Con esto queda justicado que III{A.5 es un algoritmo. V–B. COTAS DE LOS S GRADOS Como ya hemos visto, nuestros conjuntos de chequeo, ya sean para la primera como para la i esima sicigia, se obtienen a trav es de una serie de subconjuntos de ciertas N soluciones minimales de ecuaciones diof anticas. Vamos a usar este hecho para dar una cota de los grados que aparecen en un sistema minimal de generadores del i esimo m odulo de sicigias de k [ S ] : Nuestras cotas s olo depender an de los generadores del semigrupo. Para obtener estas cotas, vamos a recurrir a las cotas sobre las N soluciones que hemos dado en la secci on II{B, y en particular usaremos la dada por Pottier, (II{B.3).
96 Cotas de los S grados Sea T := 0 B B B B B B B B B B B B B B B B B B B B @ 0 0 0 0 0 0 0 0 0 ......... 0 0 0 0 0 0 0 0 0 a 1 a 1 0 0 0 0 0 0 0 0 0 a 2 a 2 0 0 0 0 0 0 0 0 0 a 3 a 3 0 0 0 ......... 0 0 0 0 0 0 0 a s a s 1 C C C C C C C C C C C C C C C C C C C C A 2 M ( Z ) ( h + s ) 2 s : Denotaremos por ~ T a la matriz 0 B B B B B B B B B B @ T 0 0 0 0 T 0 0 0 0 T 0 ...... 0 0 0 T 1 C C C C C C C C C C A 2 M ( Z ) ( t 1)( h + s ) 2 s ( t 1) : Fijemos m 2 C i : Aplicando la proposici on V{A.7, sabemos que existe un conjunto F , con ]F i + 2 ; y existe una i triangulaci on de F en m ; tal que m 2 C : Hemos visto tambi en que por el lema V{ A.6, m 2 H R : Y entonces existe 2 H R tal que m = A (1) , donde = ( (1) ;:::; ( t ) ) : Tenemos que 2 H R si y s olo si e 2 Hf 2 N rt j A ( t )( + e ) = 0 m od ~ a g y si y s olo si existe 2 N 2 s tal que ( e ; ; 1) 2 Hf 2 N rt +2 s jA = 0 g ; con A := ( A ( t ) j ~ T jA ( t ) e ) 2 M ( h + s )( t 1) ( rt +2 s ( t 1)+1) ( Z ) : N otese que e sigue la denici on dada en V{A para i triangulaciones.
Captulo V: C alculo de la Resoluci on Libre Minimal 97 Lema V–B.1 Con las notaciones anteriores, se tiene jj ( e ; ; 1) jj 1 (1 + 2 m ax j fj a j jg + 4 jjAjj 1 ) ( h + s )( d i 1) ; con d i := 0 @ r i + 1 1 A . Demostraci´on. Usando los razonamientos anteriores, hemos llegado a que ( e ; ; 1) 2 H ( A ). Por (II{B.3) jj ( e ; ; 1) jj 1 (1 + jjA jj 1 ) ( h + s )( t 1) : Como la matriz A tiene ( h + s )( t 1) las, donde ] = t; = f F 1 ; : : : ; F t g ; F j F; y ]F j = i + 1 ; para cualquier j: Entonces t = ] 0 @ ]F i + 1 1 A 0 @ r i + 1 1 A = d i ; y por lo tanto, ( h + s )( t 1) ( h + s )( d i 1). Veamos ahora que jjA jj 1 4 jjAjj 1 + 2 m ax fj a j jg : jjA jj 1 jjA ( t ) jj 1 + jj ~ T jj 1 + jjA ( t ) e jj 1 = 2 jjAjj 1 + 2 m ax fj a j jg + jjA ( t ) e jj 1 2 jjAjj 1 + 2 m ax fj a j jg + 2 jjAjj 1 = 4 jjAjj 1 + 2 m ax fj a j jg : Aplicando este resultado a los grados de la resoluci on, obtenemos el siguiente teorema. Teorema V–B.2 Si m 2 S es un S grado de una i sicigia minimal de k [ S ], entonces m = A x con x 2 N r tal que jj x jj 1 (1 + 2 m ax fj a j jg + 4 jjAjj 1 ) ( h + s )( d i 1) + ( i + 1) d i 1 ; donde d i = 0 @ r i + 1 1 A .
98 Cotas de los S grados Demostraci´on. Con la notaci on del lema V{B.1 tenemos m = A (1) con = ( (1) ;:::; ( t ) ) vericando el lema. Para la demostraci on es suciente notar que jj (1) jj 1 jj jj 1 = jj e + e jj 1 jj e jj 1 + jj e jj 1 jj ( e ;; 1) jj 1 1+( i +1) t: Ahora por V{B.1, jj (1) jj 1 (1+2 m ax fj a j jg +4 jjAjj 1 ; 1 ) ( h + s )( d i 1) +( i + 1) d i 1. En el caso i = 1 ; puede conseguirse una sustancial mejora en la cota anterior. Dicha mejora proviene de que un F hueco es un tipo especial de 1 triangulaci on. En M ( t 1)( h + s ) (( r t +2) t +2 s ( t 1)) ( Z ) ; consideramos la matriz ~ A := 0 B B B B @ A F 1 A F 20 0 0 0 0 T 0 0 0 0 A F 2 A F 30 0 0 0 0 T 0 0 0 0 A F 3 A F 40 0 0 0 0 T 0 ............... 0 0 0 0 0 A Ft 1 A Ft 0 0 0 T 1 C C C C A Vamos a denir unos enteros positivos que dependen directa y exclusivamente del conjunto de generadores tomados en S : sea D := max pol gono sobre F , F f D g con D := sup i f X j j ( A j A e )( i; j ) jg 2 N : Obtenemos as el siguiente resultado que nos da una cota sobre la escritura de los S grados de los sistemas minimales de generadores de las primeras sicigias de k [ S ] : Teorema V–B.3 Sea m 2 S un grado de un elemento minimal de un sistema homog eneo de generadores del primer m odulo de sicigias de k [ S ] : Entonces 9 2 N r tal que m = A y jj jj 1 es a lo m as (1 + 2 max i =1 ;:::;s fj a i jg + D ) ( h + s )( r 1) + 2 r 1 :
Captulo V: C alculo de la Resoluci on Libre Minimal 99 En cualquier caso, este grado es simplemente exponencial en el n umero de variables. Apliquemos estos resultados a acotar la regularidad de una variedad t orica. V–C. REGULARIDAD DE UNA VARIEDAD T´ ORICA PROYECTIVA Vamos a suponer que I es un ideal homog eneo para la graduaci on natural. Esto es equivalente a que exista un vector w 2 Q h tal que n i w = 1 ; 8 i = 1 ;:::;r ([STU91, lema 4.14]). Geom etricamente, I dene una variedad proyectiva en P r 1 ( k ) : N otese que si f 2 I es S -homog eneo de grado m 2 S; se tiene que grado ( f ) = jj jj 1 , para 2 N r con A = m: En este caso el semigrupo S es libre de torsi on. Supongamos que f f 1 ;:::;f b g es un sistema minimal de generadores de I; con S grado ( f i ) = p i 2 S y grado ( f i ) = jj i jj 1 ; donde p i = A i ; 1 i b . Si g = ( g 1 ; : : : ; g b ) 2 N 1 es una primera sicigia de S grado m 2 S; entonces S grado ( g i ) = m p i y grado ( g i ) = jj i jj 1 donde A i = m p i . Adem as, m = A ( i + i ) y grado ( g ) = jj i + i jj 1 . En general, si h = ( h 1 ;:::;h b i ) 2 N i es una i sicigia de S grado m 2 S; se tiene que grado ( h ) = jj jj 1 ; para 2 N r tal que m = A : As obtenemos una cota para la regularidad de CastelnuovoMumford de I: Teorema V–C.1 Con las notaciones anteriores, reg ( I ) (1 + 4 jjAjj 1 ) h ( d 1) + ( r + 1)( d 1) donde d = 0 @ r b r= 2 c 1 A : Demostraci´on. La regularidad de I es reg ( I ) = max 1 i r f t i i g ; donde t i es el m aximo grado de las i sicigias de I (ver [BS87]). Por el teorema V{B.2, t i (1 + 4 jjAjj 1 ) h ( d i 1) + ( i + 1) d i 1 ;
106 Sistemas Diof anticos Denotaremos por G al conjunto de N soluciones del sistema anterior, y por G ( i; ) al conjunto f x 2G N 4 j x i = g : Con esta idea denimos recurrentemente G ( i 1 ; 1 ) ( i j ; j ) : Por el lema II{B.5, para calcular un sistema minimal de generadores de nuestro sistema, es suciente, dada una N soluci on particular, construir el conjunto F = f s g [ r [ i =1 s i 1 [ =0 HG ( i; ) ; y a partir de el tendr amos que HG = H F: El primer paso es calcular una N soluci on particular, s; del sistema. Este paso lo realizamos mediante el algoritmo II{D.5 y obtenemos la upla s = (0 ; 3 ; 0 ; 0) : Por lo tanto, tenemos que calcular el conjunto F = f (0 ; 3 ; 0 ; 0) g [ S 4 i =1 S s i 1 =0 HG ( i; ) = f (0 ; 3 ; 0 ; 0) g [ HG (2 ; 0) [ HG (2 ; 1) [ HG (2 ; 2) ; usando el propio algoritmo II{D.6 recurrentemente para obtener los conjuntos HG (2 ; ) : Calculemos HG (2 ; 0) : Para ello tenemos que considerar el sistema inicial haciendo x 2 = 0 ; 8 > > < > > : x 1 +3 x 3 3 x 4 = 0 2 x 1 x 3 = 0 m od3 +2 x 3 + x 4 = 0 m od3 De nuevo tenemos que calcular, a partir de una N soluci on particular s 0 del anterior sistema, un conjunto F 0 = f s 0 g [ 4 [ i =1 s 0 i 1 [ =0 HG (2 ; 0)( i; ) :
Captulo VI: Ejemplos 107 Una tal s 0 es (0 ; 0 ; 3 ; 3) ; luego F 0 = f s 0 g [ S 4 i =1 S s 0 i 1 =0 HG (2 ; 0)( i; ) = f (0 ; 0 ; 3 ; 3) g [ HG (2 ; 0)(3 ; 0) [ HG (2 ; 0)(3 ; 1) [ HG (2 ; 0)(3 ; 2) [ [HG (2 ; 0)(4 ; 0) [ HG (2 ; 0)(4 ; 1) [ HG (2 ; 0)(4 ; 2) : HG (2 ; 0)(3 ; 0) es f 0 ; 0 ; 0 ; 0) g ya que el sistema 8 > > < > > : x 1 3 x 4 = 0 2 x 1 = 0 m od3 + x 4 = 0 m od3 no posee m as N soluci on que la trivial. An alogamente, HG (2 ; 0)(3 ; 1) = ; ; ya que el sistema 8 > > < > > : x 1 3 x 4 = 3 2 x 1 = 1 m od3 + x 4 = 2 m od3 no posee ninguna N soluci on particular. Mediante el mismo razonamiento tenemos que HG (2 ; 0)(3 ; 2) = ; : En cambio, el conjunto HG (2 ; 0)(4 ; 0) es no vac o ya que el sistema asociado a el (homog eneo en este caso) 8 > > < > > : x 1 3 x 3 = 0 2 x 1 x 3 = 0 m od3 +2 x 2 = 0 m od3 tiene, por ejemplo, como N soluci on particular s 00 = (9 ; 0 ; 3 ; 0) : De nuevo tenemos que calcular HG (2 ; 0)(4 ; 0) mediante un conjunto auxiliar F 00 = f s 00 g [ 4 [ i =1 s 00 i 1 [ =0 HG (2 ; 0)(4 ; 0)( i; ) : Para el conjunto HG (2 ; 0)(4 ; 0)(1 ; 0) ; tenemos que encontrar una N soluci on particular del sistema 8 > > < > > : 3 x 3 = 0 x 3 = 0 m od3 +2 x 3 = 0 m od3
108 Sistemas Diof anticos Cuadro VI.1. HG (2 ; 0) HG (2 ; 0) (0 ; 0 ; 3 ; 3) HG (2 ; 0)(3 ; 0) = f (0 ; 0 ; 0 ; 0) g HG (2 ; 0)(3 ; 1) = ; HG (2 ; 0)(3 ; 2) = ; HG (2 ; 0)(4 ; 0) = f (9 ; 0 ; 3 ; 0) g HG (2 ; 0)(4 ; 1) = ; HG (2 ; 0)(4 ; 2) = ; HG (2 ; 0)(4 ; 0)(1 ; 0) = f 0 ; 0 ; 0 ; 0 g HG (2 ; 0)(4 ; 0)(1 ; 1) = ; HG (2 ; 0)(4 ; 0)(1 ; 2) = ; HG (2 ; 0)(4 ; 0)(1 ; 3) = ; HG (2 ; 0)(4 ; 0)(1 ; 4) = ; HG (2 ; 0)(4 ; 0)(1 ; 5) = ; HG (2 ; 0)(4 ; 0)(1 ; 6) = ; HG (2 ; 0)(4 ; 0)(1 ; 7) = ; HG (2 ; 0)(4 ; 0)(1 ; 8) = ; HG (2 ; 0)(4 ; 0)(1 ; 0) = ; HG (2 ; 0)(4 ; 0)(1 ; 1) = ; HG (2 ; 0)(4 ; 0)(1 ; 2) = ; Al encontrarnos con un sistema de ecuaciones con una sola inc ognita, es trivial ver si tiene o no alguna N soluci on. En este caso la unica es la trivial HG (2 ; 0)(4 ; 0)(1 ; 0) = f 0 ; 0 ; 0 ; 0 g : N otese que hemos ido, mediante nuestra recurrencia, reduciendo el n umero de inc ognitas del sistema hasta llegar a uno de resoluci on inmediata (con una sola inc ognita). Adem as, al llegar a una sola inc ognita tambi en es trivial el calcular el conjunto de las N soluciones minimales. Continuando con este proceso para HG (2 ; 0) ; y para el resto de los conjuntos, HG (2 ; 1) y HG (2 ; 2) ; obtenemos las tablas VI.1, VI.2 y VI.3. Por lo tanto, tenemos que HG (2 ; 0) = f (0 ; 0 ; 3 ; 3) ; (9 ; 0 ; 3 ; 0) g HG (2 ; 1) = f (6 ; 1 ; 3 ; 1) g HG (2 ; 0) = f (0 ; 0 ; 3 ; 3) ; (9 ; 0 ; 0 ; 3) g HG (2 ; 2) = f (3 ; 2 ; 3 ; 2) g El conjunto dado por las uniones de los anteriores y s es F = f (0 ; 3 ; 0 ; 0) ; (9 ; 0 ; 3 ; 0) ; (6 ; 1 ; 3 ; 1) ; (0 ; 0 ; 3 ; 3) ; (9 ; 0 ; 0 ; 3) ; (3 ; 2 ; 3 ; 2) g : Sus elementos minimales coinciden, en este caso, con el propio F; H F =
Captulo VI: Ejemplos 109 Cuadro VI.2. HG (2 ; 1) HG (2 ; 1) (6 ; 1 ; 3 ; 1) HG (2 ; 1)(1 ; 0) = ; HG (2 ; 1)(1 ; 1) = ; HG (2 ; 1)(1 ; 2) = ; HG (2 ; 1)(1 ; 3) = ; HG (2 ; 1)(1 ; 4) = ; HG (2 ; 1)(1 ; 5) = ; HG (2 ; 1)(3 ; 0) = ; HG (2 ; 1)(3 ; 1) = ; HG (2 ; 1)(3 ; 2) = ; HG (2 ; 1)(4 ; 0) = ; Cuadro VI.3. HG (2 ; 2) HG (2 ; 2) (3 ; 2 ; 3 ; 2) HG (2 ; 2)(1 ; 0) = ; HG (2 ; 2)(1 ; 1) = ; HG (2 ; 2)(1 ; 2) = ; HG (2 ; 2)(3 ; 0) = ; HG (2 ; 2)(3 ; 1) = ; HG (2 ; 2)(3 ; 2) = ; HG (2 ; 2)(4 ; 0) = ; HG (2 ; 2)(4 ; 1) = ;
110 Resoluci on Libre Minimal F: Por lo tanto deducimos que el conjunto minimal de generadores de las N soluciones (base de Hilbert) de nuestro sistema diof antico homog eneo de partida es HG = H F = f (0 ; 3 ; 0 ; 0) ; (9 ; 0 ; 3 ; 0) ; (6 ; 1 ; 3 ; 1) ; (0 ; 0 ; 3 ; 3) ; (9 ; 0 ; 0 ; 3) ; (3 ; 2 ; 3 ; 2) g : VI–C. RESOLUCI´ ON LIBRE MINIMAL Vamos a aplicar el algoritmo IV{A.8 al siguiente semigrupo S = < (1 ; 0 ; 0) ; (0 ; 1 ; 0) ; (0 ; 0 ; 1) ; (4 ; 2 ; 5) ; (3 ; 3 ; 1) > Z 3 : Este semigrupo corresponde a una supercie proyectiva simplicial (ver [BCMP98a]). Denotaremos = f 1 ; 2 ; 3 ; 4 ; 5 g : El primer paso de nuestro algoritmo consiste en determinar el conjunto F = f F P () j ]F 3 g : En nuestro caso, este conjunto es F = ff 1 ; 2 ; 3 g ; f 1 ; 2 ; 4 g ; f 1 ; 2 ; 5 g ; f 1 ; 3 ; 4 g ; f 1 ; 3 ; 5 g ; f 1 ; 4 ; 5 g ; f 2 ; 3 ; 4 g ; f 2 ; 3 ; 5 g ; f 2 ; 4 ; 5 g ; f 3 ; 4 ; 5 g ; f 1 ; 2 ; 3 ; 4 g ; f 1 ; 2 ; 3 ; 5 g ; f 1 ; 2 ; 4 ; 5 g ; f 2 ; 3 ; 4 ; 5 g ; f 1 ; 3 ; 4 ; 5 g ; f 1 ; 2 ; 3 ; 4 ; 5 gg En general estos conjuntos se pueden tomar considerando los conjuntos formados por las combinaciones sin repetici on de elementos de tomados en grupos de 3 en 3, 4 en 4, etc, hasta ] : Comencemos con el primero de los elementos de F : Sea F = f 1 ; 2 ; 3 g 2 F ; En este caso, s olo es posible un unico pol gono sobre F; = (1 2 3) ; con F 1 = f 1 ; 2 g ; F 2 = f 2 ; 3 g y F 3 = f 3 ; 1 g : Fijado este pol gono, el siguiente paso consiste en computar el conjunto de N soluciones, H R (1 2 3) ; el cual es el conjunto de N soluciones minimales del sistema diof antico 0 @ A F 1 A F 2 0 0 A F 2 A F 3 1 A |{z } A (1 2 3) = 0 ;
Captulo VI: Ejemplos 111 igual a 0 B B B B B B B B B B B B @ 1 0 4 3 0 0 4 3 0 0 0 0 0 1 2 3 1 0 2 3 0 0 0 0 0 0 5 1 0 1 5 1 0 0 0 0 0 0 0 0 0 0 4 3 1 0 4 3 0 0 0 0 1 0 2 3 0 0 2 3 0 0 0 0 0 1 4 1 0 1 5 1 1 C C C C C C C C C C C C A = 0 ; tales que e (1 2 3) ; con e (1 2 3) = [1 ; 1 ; 0 ; 0 ; 1 ; 1 ; 0 ; 0 ; 1 ; 1 ; 0 ; 0] como se deni o en el cap tulo IV. Por la nota II{A.4, para obtener dicho conjunto, debemos computar las N soluciones minimales, H R e ; de: 0 B B B B B B B B B B B B @ 1 0 4 3 0 0 4 3 0 0 0 0 0 1 2 3 1 0 2 3 0 0 0 0 0 0 510 1 5 1 0 0 0 0 0 0 0 0 0 0 4 3 1 0 4 3 0 0 0 0 1 0 2 3 0 0 2 3 0 0 0 0 0 1 4 1 0 1 5 1 1 C C C C C C C C C C C C A |{z } A (1 2 3) = 0 B B B B B B B B B B B B @ 1 0 1 1 1 0 1 C C C C C C C C C C C C A |{z } A (1 2 3) e (1 2 3) Este conjunto es f [ 0 ; 5 ; 0 ; 2 ; 0 ; 5 ; 1 ; 1 ; 6 ; 1 ; 0 ; 0 ] ; [ 0 ; 7 ; 0 ; 2 ; 2 ; 5 ; 1 ; 1 ; 2 ; 6 ; 1 ; 0 ] ; [ 0 ; 17 ; 0 ; 4 ; 12 ; 5 ; 1 ; 3 ; 0 ; 18 ; 3 ; 0 ] ; [0 ; 12 ; 0 ; 3 ; 7 ; 5 ; 1 ; 2 ; 1 ; 12 ; 2 ; 0 ] ; [ 0 ; 15 ; 1 ; 6 ; 10 ; 5 ; 2 ; 5 ; 22 ; 0 ; 0 ; 0 ] ; [ 0 ; 28 ; 2 ; 11 ; 5 ; 24 ; 6 ; 6 ; 41 ; 0 ; 0 ; 0 ] ; [0 ; 41 ; 3 ; 16 ; 0 ; 43 ; 10 ; 7 ; 60 ; 0 ; 0 ; 0 ] ; [ 1 ; 28 ; 2 ; 11 ; 0 ; 30 ; 7 ; 5 ; 42 ; 0 ; 0 ; 0 ] ; [ 1 ; 15 ; 1 ; 6 ; 5 ; 11 ; 3 ; 4 ; 23 ; 0 ; 0 ; 0] ; [2 ; 15 ; 1 ; 6 ; 0 ; 17 ; 4 ; 3 ; 24 ; 0 ; 0 ; 0 ] ; [ 3 ; 2 ; 0 ; 1 ; 0 ; 4 ; 1 ; 1 ; 6 ; 0 ; 0 ; 0 ] ; [ 3 ; 4 ; 0 ; 1 ; 2 ; 4 ; 1 ; 1 ; 2 ; 5 ; 1 ; 0 ] ; [3 ; 14 ; 0 ; 3 ; 12 ; 4 ; 1 ; 3 ; 0 ; 17 ; 3 ; 0 ] ; [ 3 ; 9 ; 0 ; 2 ; 7 ; 4 ; 1 ; 2 ; 1 ; 11 ; 2 ; 0 ] ; [ 281 ; 0 ; 0 ; 0 ; 192 ; 0 ; 15 ; 74 ; 0 ; 203 ; 47 ; 31] ; [15 ; 0 ; 0 ; 0 ; 10 ; 0 ; 1 ; 4 ; 4 ; 8 ; 2 ; 1 ] ; [ 12 ; 0 ; 0 ; 0 ; 7 ; 1 ; 1 ; 3 ; 1 ; 8 ; 2 ; 1 ] ; [ 47 ; 0 ; 0 ; 0 ; 30 ; 2 ; 3 ; 12 ; 0 ; 34 ; 8 ; 5 ] ; [29 ; 0 ; 0 ; 0 ; 12 ; 8 ; 3 ; 6 ; 0 ; 21 ; 5 ; 3 ] ; [ 17 ; 0 ; 0 ; 0 ; 0 ; 12 ; 3 ; 2 ; 6 ; 8 ; 2 ; 1 ] ; [ 13 ; 0 ; 0 ; 0 ; 2 ; 7 ; 2 ; 2 ; 2 ; 8 ; 2 ; 1 ] ; [16 ; 0 ; 0 ; 0 ; 5 ; 6 ; 2 ; 3 ; 5 ; 8 ; 2 ; 1 ] ; [148 ; 1 ; 0 ; 0 ; 102 ; 0 ; 8 ; 39 ; 0 ; 108 ; 25 ; 16 ] ; [ 15 ; 1 ; 0 ; 0 ; 11 ; 0 ; 1 ; 4 ; 11 ; 4 ; 1 ; 0] ; [12 ; 1 ; 0 ; 0 ; 8 ; 1 ; 1 ; 3 ; 8 ; 4 ; 1 ; 0 ] ; [9 ; 1 ; 0 ; 0 ; 5 ; 2 ; 1 ; 2 ; 5 ; 4 ; 1 ; 0 ] ; [6 ; 1 ; 0 ; 0 ; 2 ; 3 ; 1 ; 1 ; 2 ; 4 ; 1 ; 0 ] ; [22 ; 1 ; 0 ; 0 ; 12 ; 4 ; 2 ; 5 ; 0 ; 17 ; 4 ; 2 ] ; [ 10 ; 1 ; 0 ; 0 ; 0 ; 8 ; 2 ; 1 ; 6 ; 4 ; 1 ; 0 ] ; [ 15 ; 2 ; 0 ; 0 ; 12 ; 0 ; 1 ; 4 ; 0 ; 13 ; 3 ; 1 ] ; [72 ; 35 ; 0 ; 0 ; 84 ; 0 ; 4 ; 19 ; 0 ; 89 ; 18 ; 0 ] ; [ 53 ; 25 ; 0 ; 0 ; 61 ; 0 ; 3 ; 14 ; 1 ; 64 ; 13 ; 0] ; [34 ; 15 ; 0 ; 0 ; 38 ; 0 ; 2 ; 9 ; 2 ; 39 ; 8 ; 0 ] ; [ 15 ; 5 ; 0 ; 0 ; 15 ; 0 ; 1 ; 4 ; 3 ; 14 ; 3 ; 0 ] ; [ 15 ; 3 ; 0 ; 0 ; 13 ; 0 ; 1 ; 4 ; 7 ; 9 ; 2 ; 0 ] ; [15 ; 2 ; 0 ; 1 ; 12 ; 0 ; 1 ; 5 ; 18 ; 0 ; 0 ; 0 ] ; [ 53 ; 30 ; 0 ; 1 ; 66 ; 0 ; 3 ; 15 ; 0 ; 70 ; 14 ; 0 ] ; [ 15 ; 20 ; 0 ; 3 ; 30 ; 0 ; 1 ; 7 ; 0 ; 32 ; 6 ; 0] ; [34 ; 25 ; 0 ; 2 ; 48 ; 0 ; 2 ; 11 ; 0 ; 51 ; 10 ; 0 ] ; [ 34 ; 20 ; 0 ; 1 ; 43 ; 0 ; 2 ; 10 ; 1 ; 45 ; 9 ; 0] ; [ 15 ; 15 ; 0 ; 2 ; 25 ; 0 ; 1 ; 6 ; 1 ; 26 ; 5 ; 0] ; [15 ; 10 ; 0 ; 1 ; 20 ; 0 ; 1 ; 5 ; 2 ; 20 ; 4 ; 0 ] ; [ 12 ; 5 ; 0 ; 0 ; 12 ; 1 ; 1 ; 3 ; 0 ; 14 ; 3 ; 0 ] ; [ 12 ; 3 ; 0 ; 0 ; 10 ; 1 ; 1 ; 3 ; 4 ; 9 ; 2 ; 0 ] ; [12 ; 2 ; 0 ; 1 ; 9 ; 1 ; 1 ; 4 ; 15 ; 0 ; 0 ; 0 ] ; [ 9 ; 8 ; 0 ; 1 ; 12 ; 2 ; 1 ; 3 ; 0 ; 15 ; 3 ; 0 ] ; [ 9 ; 3 ; 0 ; 0 ; 7 ; 2 ; 1 ; 2 ; 1 ; 9 ; 2 ; 0 ] ; [9 ; 2 ; 0 ; 1 ; 6 ; 2 ; 1 ; 3 ; 12 ; 0 ; 0 ; 0 ] ; [6 ; 11 ; 0 ; 2 ; 12 ; 3 ; 1 ; 3 ; 0 ; 16 ; 3 ; 0 ] ; [ 6 ; 2 ; 0 ; 1 ; 3 ; 3 ; 1 ; 2 ; 9 ; 0 ; 0 ; 0 ] ; [6 ; 6 ; 0 ; 1 ; 7 ; 3 ; 1 ; 2 ; 1 ; 10 ; 2 ; 0 ] g
112 Resoluci on Libre Minimal Ahora, aplicando una vez m as el resultado II{A.4, debemos a~ nadir e (1 2 3) a cada elemento del anterior conjunto para obtener H R (1 2 3) ; y de ah H R (1 2 3) : R (1 2 3) = < [ 7 ; 0 ; 2 ] ; [ 7 ; 2 ; 2] ; [13 ; 6 ; 4 ] ; [10 ; 4 ; 3 ] ; [ 19 ; 2 ; 7] ; [34 ; 4 ; 13 ] ; [49 ; 6 ; 19 ] ; [ 35 ; 4 ; 13] ; [ 20 ; 2 ; 7] ; [21 ; 2 ; 7 ] ; [ 7 ; 0 ; 1 ] ; [ 7 ; 2 ; 1 ] ; [13 ; 6 ; 3 ] ; [ 10 ; 4 ; 2 ] ; [ 282 ; 1 ; 0 ] ; [16 ; 1 ; 0 ] ; [ 13 ; 1 ; 0 ] ; [ 48 ; 1 ; 0 ] ; [ 30 ; 1 ; 0] ; [ 18 ; 1 ; 0 ] ; [ 14 ; 1 ; 0] ; [ 17 ; 1 ; 0] ; [149 ; 2 ; 0 ] ; [ 16 ; 2 ; 0 ] ; [ 13 ; 2 ; 0] ; [ 10 ; 2 ; 0 ] ; [ 7 ; 2 ; 0 ] ; [ 23 ; 2 ; 0 ] ; [ 11 ; 2 ; 0 ] ; [ 16 ; 3 ; 0] ; [ 73 ; 36 ; 0 ] ; [ 54 ; 26 ; 0] ; [35 ; 16 ; 0 ] ; [ 16 ; 6 ; 0] ; [ 16 ; 4 ; 0] ; [19 ; 0 ; 1 ] ; [57 ; 28 ; 1 ] ; [ 25 ; 12 ; 3] ; [41 ; 20 ; 2 ] ; [ 38 ; 18 ; 1 ] ; [ 22 ; 10 ; 2] ; [ 19 ; 8 ; 1] ; [13 ; 6 ; 0 ] ; [ 13 ; 4 ; 0 ] ; [ 16 ; 0 ; 1] ; [ 13 ; 6 ; 1] ; [10 ; 4 ; 0 ] ; [13 ; 0 ; 1 ] ; [ 13 ; 6 ; 2 ] ; [ 10 ; 0 ; 1 ] ; [ 10 ; 4 ; 1] > Los elementos S minimales de R (1 2 3) son C (1 2 3) = f [13 ; 1 ; 0] ; [7 ; 2 ; 0] ; [7 ; 0 ; 1] g : Este conjunto lo hemos obtenido restando dos a dos los elementos de H R (1 2 3) y comprobando si su diferencia est a o no en S: Repitiendo este proceso con todos los pol gonos asociados a los elementos de F ; obtenemos los resultados de la tabla VI.4 Sea ahora G = S C = f [13 ; 1 ; 0] ; [7 ; 2 ; 0] ; [7 ; 0 ; 1] ; [12 ; 1 ; 4] ; [23 ; 0 ; 1] ; [7 ; 2 ; 1] ; [22 ; 1 ; 1] ; [15 ; 3 ; 1] ; [25 ; 2 ; 2] ; [72 ; 0 ; 5] ; [38 ; 10 ; 0] ; [30 ; 6 ; 10] ; [28 ; 14 ; 3] g : El paso siguiente es computar el conjunto C = f m 2 G j F hueco de m g : Para ello vamos a considerar los diferentes complejos simpliciales asociados a los elementos de G dados en la tabla VI.5. El c alculo de dichos
Captulo VI: Ejemplos 113 Cuadro VI.4. Lista de C ]F = 3 C (1 2 3) = f [13 ; 1 ; 0] ; [7 ; 2 ; 0] ; [7 ; 0 ; 1] g C (1 2 4) = f [13 ; 1 ; 0] ; [7 ; 2 ; 0] g C (1 2 5) = f [13 ; 1 ; 0] ; [12 ; 1 ; 4] g C (1 3 4) = f [23 ; 0 ; 1] g C (1 3 5) = f [7 ; 0 ; 1] g C (1 4 5) = f [7 ; 2 ; 1] g C (2 3 4) = f [22 ; 1 ; 1] g C (2 3 5) = f [12 ; 1 ; 4] g C (2 4 5) = f [15 ; 3 ; 1] g C (3 4 5) = f [25 ; 2 ; 2] g ]F = 4 C (1 2 3 4) = ; C (1 2 4 3) = f [72 ; 0 ; 5] g C (1 3 2 4) = ; C (1 2 3 5) = ; C (1 2 5 3) = f [38 ; 10 ; 0] g C (1 3 2 5) = ; C (1 2 4 5) = ; C (1 2 5 4) = f [30 ; 6 ; 10] g C (1 4 2 5) = ; C (2 3 4 5) = ; C (2 3 5 4) = ; C (2 4 3 5) = ; C (1 3 4 5) = f [28 ; 14 ; 3] g C (1 3 5 4) = ; C (1 4 3 5) = ; ]F = 5 C (12345) = ; C (12354) = ; C (12435) = ; C (12453) = ; C (12534) = ; C (12543) = ; C (13245) = ; C (13254) = ; C (13425) = ; C (13524) = ; C (14235) = ; C (14325) = ;
114 Resoluci on Libre Minimal complejos lo hemos realizado a trav es de los resultados dados en el cap tulo II. Por ejemplo, para calcular [7 ; 0 ; 1] ; consideramos el sistema diof antico (7 ; 0 ; 1) = 1 (1 ; 0 ; 0) + 2 (0 ; 1 ; 0) + 3 (0 ; 0 ; 1) + 4 (4 ; 2 ; 5) + 5 (3 ; 3 ; 1) cuyos coecientes son los generadores de S; y calculamos el conjunto minimal de las N soluciones: f [7 ; 0 ; 1 ; 0 ; 0] ; [0 ; 1 ; 5 ; 1 ; 1] ; [4 ; 3 ; 0 ; 0 ; 1] g : Los soportes de estas N soluciones minimales son las caras maximales de [7 ; 0 ; 1] : De hecho, estas N soluciones son las unicas escrituras de [7 ; 0 ; 1] en funci on de los generadores de S: Los elementos que cuyos pol gonos corresponden realmente con F huecos de sus complejos son: C = f [7 ; 2 ; 0] ; [7 ; 0 ; 1] ; [7 ; 2 ; 1] g : Este es precisamente el conjunto que se obtiene al aplicar el algoritmo IV{A.8. Para calcular ahora el conjunto C 1 ; tenemos que ver cuales de los elementos de C tienen homolog as no nulas. Por lo tanto tenemos que calcular las homolog as asociadas a sus complejos simpliciales. Realicemos este c alculo para, por ejemplo, [7 ; 0 ; 1] : Entonces tenemos que considerar las aplicaciones ~ C 2 ( [7 ; 0 ; 1] ) @ 2 ! ~ C 1 ( [7 ; 0 ; 1] ) @ 1 ! ~ C 0 ( [7 ; 0 ; 1] ) ; donde ~ C 2 ( [7 ; 0 ; 1] ) = < f 1 ; 5 ; 2 g ; f 2 ; 3 ; 4 g ; f 2 ; 3 ; 5 g ; f 2 ; 4 ; 5 g ; f 3 ; 4 ; 5 g >; ~ C 1 ( [7 ; 0 ; 1] ) = < f 1 ; 2 g ; f 1 ; 3 g ; f 1 ; 5 g ; f 2 ; 3 g ; f 2 ; 4 g ; f 2 ; 5 g ; f 3 ; 4 g ; f 3 ; 5 g ; f 4 ; 5 g > y ~ C 0 ( [7 ; 0 ; 1] ) = < f 1 g ; f 2 g ; f 3 g ; f 4 g ; f 5 g > :
Captulo VI: Ejemplos 115 Cuadro VI.5. Lista de complejos [13 ; 1 ; 0] ! 1 2 3 4 5 [7 ; 2 ; 0] ! 1 4 35 2 [7 ; 0 ; 1] ! 1 5 2 3 4 [12 ; 1 ; 4] ! 1 2 3 4 5 [23 ; 0 ; 1] ! 1 2 3 4 5 [7 ; 2 ; 1] ! 1 2 5 4 3 [22 ; 1 ; 1] ! 1 2 3 4 5 [15 ; 3 ; 1] ! 1 2 3 4 5 [25 ; 2 ; 2] ! 1 2 3 4 5 [72 ; 0 ; 15] ! 1 2 3 4 5 [38 ; 10 ; 0] ! 1 2 3 4 5 [30 ; 6 ; 10] ! 1 2 3 4 5 [28 ; 14 ; 3] ! 1 2 3 4 5
122 Bibliografa torial Optimization, LNCS 920, Springer-Verlag , 920:267{ 276, 1995. [HUE78] G. HUET. An algorithm to generate the basis of solutions to homogeneous linear diophantine equations. Inform. Process. Lett. , 7(3), 1978. [LAM87] J.L. LAMBERT. Une borne pour les g en erateurs des solutions enti eres positives d'une equation diophantienne lin eaire. C. R. Acad. Sci. Paris. , 305:39{40, 1987. [PCVT96] P. PIS ON CASARES and A. VIGNERON TENORIO. Ideales de semigrupos con torsi on: C alculos mediante maplev. Actas del EACA'96, Sevilla (Spain) , 1996. [PCVT98] P. PIS ON-CASARES and A. VIGNERON-TENORIO. N solutions to linear systems over Z . Preprint of University of Sevilla , 43, 1998. [PCVTer] P. PIS ON-CASARES and A. VIGNERON-TENORIO. First syzygies of toric varieties and diophantine equations in congruence. Communications in Algebra , Por aparecer. [POT91] L. POTTIER. Minimal solutions of linear diophantine systems: bounds and algorithms. Proceedings of the Fourth International Conference on Rewriting Techniques and Applications, Italy , pages 162{173, 1991. [PS98] I. PEEVA and B. STURMFELS. Syzygies of codimension 2 lattice ideals. Math. Z. , 229:163{194, 1998. [RGS98] J. ROSALES and P. GARC IA-S ANCHEZ. Presentaciones de monoides cancelativos. Proceedings of EACA'98, Guadalajara (Spain) , pages 130{141, 1998. [ROS91] J.C. ROSALES. Semigrupos num ericos . PhD thesis, Universidad de Granada, 1991.
Bibliografa 123 [ROS95] J.C. ROSALES. On nitely generated submonoids of N k . Semigroup Forum , 50:251{262, 1995. [RUB96] J.C. ROSALES and J.M. URBANO-BLANCO. A deterministic algorithm to decide if a nitely presented abelian monoid is cancellative. Communications in Algebra , 24(13):4217{ 4224, 1996. [SCH96] A. SCHRIJVER. Theory of Linear and Integer Programming . Wiley-Interscience, 1996. [STA96] R. STANLEY. Combinatorics and commutative algebra 2nd ed , volume 41 of Progress in Mathematics . Boston Basel Berlin, Birkh auser, 1996. [STU91] B. STURMFELS. Gr obner bases of toric varieties. T^ ohoku Math. J. , 43:249{261, 1991. [STU95] B. STURMFELS. Gr obner Basis and Convex Polytopes , volume 8 of University Lecture Series . American Mathematical Society, Providence, RI, 1995. [TOM97] A.P. TOMAS. On Solving Linear Diophantine Constraints . PhD thesis, Facultad de Ciencias, Universidad de Oporto, 1997. [VAS98] W.V. VASCONCELOS. Computational Methods in Commutative Algebra and Algebraic Geometry , volume 2 of Algorithms and Computations in Mathematics . Springer, 1998. [VT99] A. VIGNERON-TENORIO. Semigroup ideals and linear diophantine equations. Linear Algebra and its Applications , 295:133{144, 1999.
Indice alfab etico ( J : f ), 14 ( J : f 1 ), 14 C , 91 I L , 10 I ker( S ) , 11 J C , 15 L ( i; ), 37 R , 77 R , 90 S minimal, 75 V i ( m ), 60 N soluci on, 29 A ; 77 A , 71 A ( t ), 90 C , 77 G 0 , 30 G e , 31 G , 30 H ( L ) ; H L , 30 H R , 91 m , 61 , 60 R , 77 R , 90 H R , 91 H R , 79 minimal, 30 ker( S ), 11 @ i , 61 un F hueco, 72 i triangulaci on, 86 ~ C i ( m ), 61 ~ H i ( m ), 61 ~ Z i ( m ), 61 ' i +1 , 59 jj jj 1 , 32 e , 76 e , 90 k [ S ], 58 reg ( I ), 6 Complejo simplicial, 61 Conjunto ortogonal, 21 Ideales de ret culo, 10 Ret culo Nakayama, 10 Semigrupo cancelativo, 10 Semigrupo Nakayama, 10 124
Resumen: Dado un semigrupo abeliano, cancelativo, finitamente generado y con elemento neutro, S, y un cuerpo k, podemos considerar el álgebra S-graduada k[S]. El estudio de esta álgebra tiene un gran interés dentro de la Geometría Algebraica por su relación con la Geometría Tórica. En esta memoria nos centramos en el estudio de los módulos de sicigias de la resolución del álgebra asociada al semigrupo. Damos algoritmos basados en bases de Gröbner que nos permiten calcular sistemas irreducibles de generadores del ideal de un semigrupo con torsión. Además, damos un método efectivo, basado en el cálculo de N-soluciones de sistemas diofánticos en congruencias, para calcular los grados que aparecen en el primer módulo de sicigias de k[S], ampliando estos resultados a toda la resolución del álgebra k[S]. De estos métodos, deducimos cotas para los grados que aparecen en un sistema minimal de generadores el i-ésimo módulo de sicigias, en función solamente de los generadores del semigrupo. Explicitamos una cota para la regularidad de una variedad tórica, así como un algoritmo para hallar dicha regularidad.
Abstract Given a finitely commutative cancelative semigroup with zero element, S, and a field k, we can consider the S-graduated algebra k[S]. The study of this algebra has a great interest inside the Algebraic Geometry because of its relation with the Toric Geometry. In this memory we study the modules of sizigies of the resolution of the algebra associated with the semigroup. We give algorithms based on Gröbner bases that allow us to compute irreducible systems of generators of the ideal of a semigroup with torsion. Besides, we give an effective method to compute the degrees that appear in the first module of sicigias of k[S] using diophantine equations in congruences, extending these results to the whole resolution of the algebra k[S]. Of these methods, we deduce bounds for the degrees of a minimal systems of generators of the i-sizigies by means of the semigroup generators. We give explicit bounds for the regularity of a toric variety, as well as an algorithm to find it.