Bases de Groebner: una introducción a la Geometría Algebraica

Traballo Fin de Grao Bases de Groebner: Una Introducción a la Geometría Algebraica Marcos Fernández Criado 2018/2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Bases de Groebner: Una Introducción a la Geometría Algebraica Marcos Fernández Criado 2018 / 2019 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Trabajo propuesto Área de Coñecemento: Álgebra Título: Bases de Groebner: Introducción a la geometría algebraica Breve descrición do contido: Un subconjunto algebraico de un espacio afín de dimensión n sobre un cuerpo k es el conjunto soluciones de un sistema de ecuaciones polinómicas en n variables con coeficientes en el cuerpo. Estudiaremos las propiedades de este tipo de subconjuntos utilizando Bases de Gröbner. El trabajo es una propuesta para iniciar al alumno en el estudio de la Geometría Algebraica. Recomendacións Se recomienda haber cursado las asignaturas Ecuaciones Algebraicas, Estructuras Algebraicas. Puede ser conveniente para el alumno cursar paralelamente la asignatura Álgebra, Números y Geometría. Outras observacións iii Índice general Resumen vii Introducción ix 1. Bases de Groebner 1 1.1. Motivaciones: Variedades algebraicas afines. . . . . . . . . . . . . . . . . . . 1 1.2. Ideales monomiales: Lema de Dickson. . . . . . . . . . . . . . . . . . . . . . 4 1.3. Órdenesmonomiales................................ 7 1.4. Algoritmo de división . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5. Definición y existencia de la base de Groebner . . . . . . . . . . . . . . . . . 15 1.6. Propiedades de las bases de Groebner. . . . . . . . . . . . . . . . . . . . . . 17 1.6.1. Criterio para determinar bases de Groebner. . . . . . . . . . . . . . . 18 1.6.2. Construcción de una base de Groebner: Algoritmo de Buchberger. . 22 2. Teoría de la Eliminación 27 2.1. Teoremas de Eliminación y Extensión. . . . . . . . . . . . . . . . . . . . . . 27 2.2. TeoremadeClausura. .............................. 35 2.3. Problema de implicitación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.1. Parametrización polinómica. . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.2. Parametrización racional. . . . . . . . . . . . . . . . . . . . . . . . . 40 3. Aplicaciones de las bases de Groebner 45 3.1. Programación Lineal Entera. . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2. Teoríadegrafos. ................................. 55 3.3. Criptosistemas Polly Cracker. . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Bibliografía 65 v Resumen En este trabajo se presentarán el lema de Dickson, los órdenes monomiales y el algoritmo de la división. Se definirán, usando el Teorema de la Base de Hilbert, y caracterizarán las bases de Groebner, y se dará un algoritmo para calcularlas: el algoritmo de Buchberger. Se resolverán dos problemas diferentes usando bases de Groebner: el problema de determinar si un polinomio pertenece a un ideal y el problema de hallar las ecuaciones implícitas de una variedad dada en forma paramétrica. Se darán también interpretaciones geométricas de resultados como el Teorema de Eliminación y el Teorema de Extensión, y aplicaciones de las bases de Groebner externas al álgebra conmutativa, tales como la resolución del problema de optimización con restricciones de una función con dominio entero, una aproximación a un algoritmo para colorear grafos con qcolores y los criptosistemas Polly-Cracker para el encriptado de mensajes. Abstract In this paper we present Dickson‘s lemma, monomial orders and division algorithm. We define, using de Hilbert’s basis theorem, and characterize Groebner bases, and provide a method to calculate them: the Buchberger‘s algorithm. We will present and solve two differente problems using Groebner bases: the ideal membership problem and the implicitization problem. Also, we will provide different geometrical interpretations of results like Elimination and Extension Theorems, and applications of Groebner bases outside commutative algebra, such as the resolution of the problem of optimize a funcion in an entire domain with constraints, an approximation of an algorithm to fill graphs with qcolours and Polly-Cracker cryptosystems to code a message. vii 4CAPÍTULO 1. BASES DE GROEBNER 1.2. Ideales monomiales: Lema de Dickson. En esta sección vamos a resolver el Problema de la descripción de ideales para un tipo concreto de ideales: Los ideales monomiales. Este caso particular es uno de los ingredientes que nos permitirá resolver el problema en general. Los polinomios de la forma cxα1 1xα2 2···xαn n∈K[x1, . . . , xn], con α= (α1, α2, . . . , αn)∈ Nnyc∈Kun escalar no nulo, se denominan monomios; el (múlti-)grado α= (α1, . . . , αn) determina el monomio xα1 1xα2 2···xαn n. Para él utilizaremos la notación abreviada xα=xα1 1xα2 2···xαn n. El anillo de polinomios K[x] = K[x1, . . . , xn]es un K-espacio vectorial y el conjunto de los monomios mónicos M(x1, . . . , xn) = {xα/α∈Nn}es la base canónica de K[x]. El conjunto M(x) = M(x1, . . . , xn)es un monoide con el producto de K[x], y la correspondencia x?:Nn→ M(x)es un isomorfismo entre los monoides (Nn,+) y(M(x),·). Denotaremos 0= (0,...,0) el neutro de Nn, que corresponde al neutro 1∈ M(x). Definición 1.10. Diremos que un ideal I⊂K[x1, . . . , xn]es monomial si posee un sistema de generadores formado por monomios, o equivalentemente (por ser Kun cuerpo), si existe un subconjunto A⊂Nntal que I=hxα/ α ∈Ai, esto es: f∈I⇐⇒ f= s X i=1 hixα(i),con α(i)∈Ayhi∈K[x1, . . . , xn] Proposición 1.11. sea Iun ideal monomial y f∈K[x1, . . . , xn]un polinomio. Los siguientes enunciados son equivalentes: (i)El polinomio fpertenece a I. (ii)Cada monomio de fpertenece a I. (iii)El polinomio fes una combinación K-lineal de monomios de I. Demostración. Las implicaciones (iii)⇒(ii)⇒(i)son consecuencia inmediata de la definición de ideal monomial. Para completar la demostración veamos que (i)⇒(iii). Supongamos que I=hxα/ α ∈Aipara un subconjunto A⊂Nn. Entonces cada polinomio f∈Ise puede escribir de la forma f=Ps i=1 hixα(i), para ciertos exponentes α(i)∈Ay polinomios hi∈K[x1, . . . , xn]. Escribiendo cada polinomio hicomo combinación K-lineal de monomios, hi=Psi j=1 bijxν(ij), se obtiene una expresión de la forma f= s X i=1 hixα(i)= s X i=1 si X j=1 bijxν(ij)xα(i),(1.1) es decir, fse escribe como combinación K-lineal de monomios xν(ij)xα(i)∈I. 1.2. IDEALES MONOMIALES: LEMA DE DICKSON. 5 Corolario 1.12. Dos ideales monomiales son iguales si, y sólo si, contienen los mismos monomios. Lema 1.13. Sea I=hxα/α∈Ai ⊂ K[x1, . . . , xn]un ideal monomial, con A⊂Nn. Dado σ∈Nnequivalen: (i)El monomio xσpertenece a I. (ii)El monomio xσes divisible por xαpara algún α∈A. (iii)Existe α∈Atal que σ=α+ν, para algún ν∈Nn. Demostración. Las implicaciones (iii)⇒(ii)⇒(i)son inmediatas. Para demostrar que (i)⇒(iii)supongamos que f=xσen la expresión (1.1), entonces agrupando los términos de la derecha se tendría que xσes una suma finita de términos de la forma bijxνij +αi. Por ser los monomios una K-base la suma de la derecha se reduce a un término de la forma xν+αcon α∈Ayν∈Nn. El Lema de Dickson resuelve el Problema de la descripción de ideales para el caso de ideales monomiales: Todo ideal monomial del anillo de polinomios K[x1, . . . , xn] es finitamente generado. En lugar de demostrar directamente el Lema de Dickson, enunciaremos y demostraremos un resultado equivalente sobre los exponentes de los monomios de un ideal monomial (Proposición 1.14), obteniendo como corolario inmediato el Lema de Dickson. Consideremos en Nnla relación determinada “componente a componente” a partir de la relación de orden habitual de N, es decir, la relación de orden definida de la siguiente forma: ασ:⇐⇒ σ−α∈Nn(α,σ∈Nn)(1.2) Si denotamos α+Nn:= {α+ν/ν∈Nn}, ασ⇐⇒ σ∈α+Nn. El orden es compatible con la estructura de monoide (Nn,+): ∀α,σ,ν∈Nn:ασ=⇒α+νσ+ν(1.3) Si n > 1entonces (Nn,)no es un conjunto bien ordenado, pero tiene la siguiente buena propiedad: Proposición 1.14 (Lema de Dickson para Nn).En el conjunto ordenado (Nn,), todo subconjunto A⊂Nnno vacío posee un número finito de elementos minimales. 6CAPÍTULO 1. BASES DE GROEBNER Demostración. Haremos la demostración por inducción en n. El caso n= 1 es la propiedad del buen orden de los naturales. Supongamos que n > 1. Elegimos un elemento α(0) = (α01, α02, . . . , α0n)∈A, si existe σ∈Atal que σ/∈α(0) + Nn, entonces existirá un índice i∈ {1, . . . , n}para el cual σi< α0i. Es decir, σ∈ ∪n i=1Ai, donde Ai:= {α∈A / 0⩽αi< α0i}, i ∈ {1, . . . , n}. Obsérvese que Ai=S0⩽j<α0iAij, siendo Aij := {α∈Ai/ αi=j}.Sea πi:Nn→Nn−1la proyección que consiste en eliminar la componente i∈ {1, . . . , n}. La proyección πiinduce una biyección que conserva el orden entre Aij y su imagen πi(Aij)⊂Nn−1. Por hipótesis de inducción, si Aij es no vacío entonces posee un conjunto finito de elementos minimales Aij; sea A0la unión de la colección finita de subconjuntos Aij. Entonces A={α(0)}∪A0⊂A es un subconjunto finito que contiene todos los minimales de A. Según el Lema 1.13, la relación ασequivale a que el monomio xσsea divisible por el monomio xα, y se tiene la siguiente consecuencia de la proposición: Corolario 1.15 (Lema de Dickson).Sea A⊂NneI=hxα/α∈Ai ⊂ K[x]el ideal monomial que determina A. Existen α(1),...,α(s)∈Atales que I=hxα(1),...,xα(s)i. Demostración. Según la proposición anterior, respecto a la relación de orden , el conjunto Aposee un conjunto finito de minimales. Si α(1),...,α(s)son los minimales de Aentonces A⊂ ∪s i=1(α(i) + Nn)y, por el Lema 1.13, I=hxα(1),...,xα(s)i. 1.3. ÓRDENES MONOMIALES. 7 1.3. Órdenes monomiales. En el anillo de polinomios en una variable K[x], sobre un cuerpo K, la ordenación de monomios ··· > xm+1 > xm>··· > x2>x>1 es un elemento clave en el algoritmo de la división. También se ordenan las variables en el algoritmo de reducción de Gauss para resolver sistemas de ecuaciones lineales en varias variables x1, . . . , xncon coeficientes en K. En estos algoritmos, cada iteración se reduce a trabajar con “el coeficiente principal” de los polinomios. Si queremos generalizar estos algoritmos para tratar de resolver sistemas de ecuaciones con coeficientes en el cuerpo Kque involucran varias variables, x1, . . . , xn, elevadas a exponentes naturales arbitrarios, nos encontramos con un problema evidente: ¿Cuál es el coeficiente principal de un polinomio no nulo f∈K[x1, . . . , xn]? En K[x]el orden de los monomios M(x)es claro, se ordenan según los exponentes siguiendo el orden de N. Esta forma de ordenar los monomios de M(x)posee dos propiedades muy útiles: es un buen orden y es compatible con el producto de monomios. El objetivo en esta sección es ordenar el conjunto de los monomios M(x)⊂K[x] = K[x1, . . . , xn]de forma que se verifiquen esas buenas propiedades. A través de la correspondencia biyectiva x?:Nn→ M(x), dar un orden en el conjunto M(x)equivale a dar un orden en el conjunto de los exponentes Nn. Si ⩽es una relación de orden en Nn, denotaremos con el mismo símbolo ⩽el orden determinado en M(x): xα⩽xσ:⇐⇒ α⩽σ(α,σ∈Nn). Como la correspondencia x?:Nn→ M(x)es un isomorfismo de monoides entre (Nn,+) y (M(x),·), que un orden en Nnsea compatible con la suma equivale a que el determinado en M(x)sea compatible con el producto. Ejemplo 1.16. El orden (Nn,), definido en (1.2), determina la ordenación de monomios xαxσ:⇐⇒ ασ. Como hemos indicado, este no en un buen orden si n > 1; sin embargo, el orden (Nn,) es compatible con la suma, es decir, el orden que determina entre los monomios M(x)es compatible con el producto: ∀α,σ,ν∈Nn:xαxσ⇐⇒ xαxνxσxν La siguiente definición resume las propiedades que dede tener un orden en el conjunto de exponentes Nnpara que el orden que establece entre monomios M(x)tenga “buenas propiedades”: 8CAPÍTULO 1. BASES DE GROEBNER Definición 1.17. Un orden ⩽en Nnes monomial si es un buen orden que, además, es compatible con la suma, es decir, ∀α,σyν∈Nnse verifica [α⩽σ=⇒α+ν⩽σ+ν]. Lema 1.18. Una relación de orden ⩽en Nnes un buen orden si, y sólo si, toda sucesión decreciente de elementos de Nn, α(1) ⩾α(2) ⩾α(3) ⩾··· , es estacionaria, es decir, existe n∈Ntal que α(n) = α(m)para todo m≥n. Demostración. Demostraremos que ⩽no es un buen orden si, y sólo si, existe una sucesión infinita estrictamente decreciente de elementos de Nn. Si ⩽no es un buen orden en Nn, existirá un subconjunto no vacío S⊂Nnque no tiene elemento mínimo. Como Ses no vacío, podemos elegir un elemento α(1) ∈S; como α(1) no es mínimo de S, existirá un elemento α(2) ∈Stal que α(1) >α(2); como α(2) ∈S no es el mínimo de S, existirá un elemento α(3) ∈Stal que α(2) >α(3). Repitiendo este proceso construímos una sucesión infinita estrictamente decreciente de elementos de Nn. Recíprocamente, si existe una sucesión estrictamente decreciente de elementos de Nn α(1) >α(2) >α(3) >··· entonces el subconjunto S={α(1),α(2),α(3), . . .} ⊂ Nnes no vacío y no posee mínimo, así que ⩽no puede ser un buen orden. Antes de entrar en más detalles, vamos a presentar un corolario útil de la Proposición 1.14 (Lema de Dickson para Nn) que permite caracterizar de forma más sencilla los ordenes monomiales. Corolario 1.19. Sea ⩽una relación de orden en Nnverificando: (i) ⩽es una realación de orden total. (ii) ⩽es compatible con la suma de Nn. Entonces, ⩽es un buen orden en Nnsi, y sólo si, α⩾0= (0,...,0) para cualquier α∈Nn. Demostración. Asumiendo que (Nn,⩽)es un conjunto bien ordenado es suficiente comprobar que β⩾0, siendo βel elemento más pequeño de Nn. Supongamos que β0, como la relación de orden es total necesariamente 0>β; entonces por (ii) se tiene que β=0+β>β+β, lo cual es un absurdo dado que β+β∈Nnyβera el elemento más pequeño de Nn. 1.3. ÓRDENES MONOMIALES. 9 Recíprocamente, supongamos que α⩾0,∀α∈Nn. Obsérvese que en este caso: ασ=⇒α⩽σ(α,σ∈Nn) En efecto, por hipótesis 0es el mínimo de (Nn,⩽)y⩽es compatible con la suma entonces ασ⇐⇒ σ−α∈Nn=⇒0⩽σ−α=⇒α⩽σ Veamos que cualquier subconjunto no vacío A⊂Nnposee mínimo para la relación ⩽. Por la Proposición 1.15, para la relación si A⊂Nnes no vacío posee un conjunto finito de minimales G={α(1),α(2),...,α(s)} ⊂ A. Dado que nuestra relación de orden ⩽es de orden total, permutando índices si fuera necesario, podemos escribir α(1) ⩽α(2) ⩽··· ⩽ α(s). Así, el elemento α(1) es el mínimo de (A, ⩽). Observación 1.20.El Corolario 1.19 permite demostrar que un orden ⩽en Nnes monomial si, y sólo si, verifica las siguientes tres propiedades: (m1)⩽es de orden total, (m2)⩽es compatible con la suma y, (m3)para todo α∈Nn,α⩾0= (0,...,0). Ejemplos de órdenes monomiales: Es sencillo demostrar que los siguientes órdenes son monomiales comprobando las condiciones m1,m2, y m3. Orden Lexicográfico: Dados α,β∈Nn, diremos que α>lexσsi, en el vector α−β∈Znla primera entrada no nula empezando por la izquierda es positiva. Escribiremos xα>lexxβsi α>lexβ. Notación: Dado α∈Nn, denotaremos |α|=Pn i=1 αi. Orden graduado lexicográfico: Dados α,β∈Nn, α>grlexβ:⇐⇒ |α|>|β|o|α|=|β|yα>lex β Orden graduado lexicográfico inverso: Sean αyβ∈Nn. Decimos que α>grevlex β si |α|>|β|, o si |α|=|β|y la primera entrada no nula de α−β∈Znempezando por la derecha es negativa. Ejemplo 1.21. Aquí vemos diferentes comparaciones entre ternas de N3: (1,0,0) >lex(0,7,6) (3,2,6) >lex(3,2,1) (2,1,0) >lex(1,7,3) (5,4,3) >grevlex(6,2,4) (6,2,4) >grlex(5,4,3) (1,7,1) >grlex(4,2,2) (2,5,4) >grlex(0,6,5) (0,6,5) >grevlex(2,5,4) (4,1,1) >lex(1,4,4) 10 CAPÍTULO 1. BASES DE GROEBNER Observación 1.22.Las variables x1, . . . , xnquedan ordenadas de igual forma para cualquiera de estos tres órdenes; si >denota uno de los órdenes >lex,>grlex o>grevlex: x1> x2>··· > xn. Si fijamos un orden monomial en el conjunto de los exponentes Nn, dado un polinomio f=Pαaαxα∈K[x1, . . . , xn]podemos ordenar sin ambigüedad los monomios de f respecto a dicha ordenación. Ejemplo 1.23. Para fijar ideas, vamos a comparar como quedan ordenados los monomios de un polinomio según los diferentes órdenes monomiales que hemos visto hasta ahora. Sea f= 7x2y2z+ 3z4−5x3+ 2x2yz2∈K[x, y, z]. Sus monomios se ordenarían como sigue: •Respecto a >lex:f=−5x3+ 7x2y2z+ 2x2yz2+ 3z4; •Respecto a >grlex:f= 7x2y2z+ 2x2yz2+ 3z4−5x3; •Respecto a >grevlex:f= 2x2yz2+ 7x2y2z+ 3z4−5x3. Definición 1.24. Fijemos un orden monomial. Dado polinomio no nulo f=Pαaαxα∈K[x1, . . . , xn]se definen los siguientes elementos destacados del polinomio: El multigrado ogrado de f:MGRAD(f) := m´ax{α∈Nn/aα6= 0}; El coeficiente principal de f:LC(f) := aMGRAD(f); El monomio principal de f:LM(f) := xMGRAD(f); El término principal de f:LT(f) := LC(f)·LM(f) = aMGRAD(f)·xMGRAD(f). Ejemplo 1.25. De nuevo, para fijar ideas, vamos a ver quienes son los diferentes elementos destacados del polinomio fdel ejemplo 1.23 según los órdenes monomiales que hemos introducido: •Respecto a >lex:LC(f) = −5,LM(f) = x3,LT(f) = −5x3; •Respecto a >grlex:LC(f)=7,LM(f) = x2y2z, LT(f)=7x2y2z; •Respecto a >grevlex:LC(f)=2,LM(f) = x2yz2,LT(f)=2x2yz2. La demostración del siguiente lema es inmediata: Lema 1.26. Dados f, g ∈K[x1, . . . , xn]polinomios no nulos: MGRAD(f·g) = MGRAD(f) + MGRAD(g); f+g6= 0 ⇒MGRAD(f+g)⩽m´ax{MGRAD(f),MGRAD(g)}. 1.4. ALGORITMO DE DIVISIÓN 11 1.4. Algoritmo de división en K[x1,...,xn] Fijado un orden monomial >en los exponentes Nn. Una vez determinado el orden de los monomios de un polinomio no nulo, el siguiente paso es establecer un algoritmo de división que involucre varios divisores. Dado un polinomio f∈K[x], la idea de “dividir” fpor una familia de polinomios f1, . . . , fs∈K[x]consiste en expresar fen la forma f=h1f1+. . . +hsfs+r, para ciertos polinomios h1, . . . , hs, r ∈K[x], de tal manera que rsea un “resto” que no se pueda simplificar utilizando los términos principales de los polinomios f1, . . . , fs. En el caso del anillo de polinomios en una variable K[x]y un divisor f1bastaba exigir como condición para finalizar el algoritmo que r= 0, o que siendo r6= 0 su grado fuese menor que el grado del divisor. En el caso general la idea básica es cancelar el término principal de fmultiplicando algún fipor un monomio apropiado y restándolos, para a continuación repetir el proceso con el polinomio resultante de dicha operación, hasta que este proceso no se pueda repetir más. Para ver cómo proceder, empezaremos con un ejemplo: Ejemplo 1.27. Consideremos el orden monomial lexicográfico, con x>y. Vamos a ”dividir” f=xy2+xpor f1=xy + 1 yf2=x+ 1: Multiplicamos f1·yy se lo restamos a f: (xy2+x)−[(xy + 1) ·y] = x−y. Como xy no divide a x, pasamos a f2: Multiplicamos f2·1y se lo restamos al resultado anterior: x−y−[(x+ 1) ·1] = −y−1. Como xno divide a y, hemos acabado y r=−y−1. Concluímos: f=xy2+ 1 = (xy + 1) ·y+ (x+ 1) ·1+(−y−1) = f1·a1+f2·a2+r. Observamos que el resto obtenido, r=−y−1, no es divisible por el término principal de ninguno de los divisores. ¿Es esta condición la adecuada para poder definir correctamente el algoritmo? Teorema 1.28 (Algoritmo de la división en K[x1, . . . , xn]).Sea F= (f1, . . . , fs)una s-tupla ordenada de polinomios de K[x] = K[x1, . . . , xn]y fijemos un orden monomial (Nn,⩾). Cada polinomio f∈K[x]se puede escribir de la siguiente forma: f=h1f1+···+hsfs+r, con hi, r ∈K[x1, . . . , xn], tales que r= 0 ores una combinación K-lineal de monomios, ninguno de los cuales es divisible por ninguno de los LT(fi). Además, si hifi6= 0, entonces MGRAD(f)⩾MGRAD(hifi). 12 CAPÍTULO 1. BASES DE GROEBNER Nos referiremos a rcomo resto de la división de fpor la s-tupla ordenada F= (f1, . . . , fs), y escribiremos r=fF. Demostración. Demostraremos la existencia tanto de los coeficientes hicomo del resto r explicitando un algoritmo para hallarlos, y viendo que dicho algoritmo concluye en un número finito de pasos. Input: f1, . . . , fs, f Output: h1, . . . , hs, r h1:= 0; . . . ;hs:= 0; r:= 0 p:= f WHILE p6= 0 DO i:= 1 divisionoccurred:=false WHILE i⩽sAND divisionoccurred=false DO IF LT(fi)divides LT(p)THEN hi:= hi+LT(p)/LT(fi) p:= p−(LT(p)/LT(fi))fi divisionoccurred:= true ELSE i:= i+ 1 IF divisionoccurred=false THEN r:= r+LT(p) p:= p−LT(p) Donde la variable prepresenta el dividendo, que puede ser distinto en cada iteración del algoritmo. La variable lógica divisionoccurred nos indica cuando el término LT(fi)divide al término principal del dividendo p. Para probar que dicho algoritmo funciona, observemos que la igualdad f=h1f1+. . . +hsfs+p+r(1.4) se mantiene en cada iteración. En cada iteración del bucle principal WHILE...DO se da una y sólo una de las siguientes situaciones: O bien LT(fi)divide a LT(p), en cuyo caso se procede de forma análoga al algoritmo en una variable, o bien LT(fi)no divide a LT(p), en cuyo caso LT(p)se añade al resto. En el caso de que LT(fi)divida a LT(p), se produce el siguiente cambio: hifi+p= (hi+LT(p)/LT(fi))fi+ (p−LT(p)/LT(fi))fi, 1.4. ALGORITMO DE DIVISIÓN 13 mientras que en el otro caso, tenemos que p+r= (p−LT(p)) + (r+LT(p)), con lo cual la igualdad (1.4) se mantiene. Nos falta probar que el algoritmo termina, es decir, que llega un momento en el cual p= 0. Para ver esto observemos lo que le ocurre apen cada iteración: Si LT(fi)divide a LT(p), redefinimos pcomo p−(LT(p)/LT(fi))fi, mientras que en el otro caso, redefinimos pcomo p−LT(p). En ambas situaciones se produce una resta de dos polinomios que tienen el mismo término principal, y por tanto, se cancelan y el multigrado de pdisminuye. Si el algoritmo no terminase en un número finito de pasos, obtendríamos una sucesión infinita estrictamente decreciente de multigrados, y esto contradice el hecho de que el orden elegido sea un orden monomial. Observación 1.29.El problema es que este algoritmo no conserva las buenas propiedades de su versión en 1 variable, como la unicidad del resto: Ni los coeficientes h1, . . . , hsni el “resto” rquedan determinados de forma única por el dividendo fy el “divisor” F= (f1, . . . , fs). Podemos observar este hecho en el siguiente ejemplo: Ejemplo 1.30. Sea f=x2y+xy +yun polinomio. Vamos a dividir fpor f1=xy −1y por f2=x−1considerando en K[x, y]el orden lexicográfico, con x>y. (I) Consideremos F12 = (f1, f2) : Dado que LT(f)es divisible por LT(f1), restamos a fel producto f1·x: (x2y+xy +y)−[(xy −1) ·x] = xy −x+y Como xy es divisible por LT(f1), restamos a xy −x+yel producto f1·1 : (xy −x+y)−[(xy −1) ·1] = −x+y−1 Como xno es divisible por LT(f1), pasamos al polinomio f2. Le restamos a −x+y−1el producto f2·(−1) (−x+y−1) −[(x−1) ·(−1)] = y−2 De esta forma, f= (x+ 1) ·f1−f2+y−2, y el resto es: r=y−2. (II) Consideremos ahora F21 = (f2, f1): Dado que LT(f)es divisible por LT(f2), restamos a fel producto f2·xy (x2y+xy +y)−[(x−1) ·xy]=2xy +y Como xy es divisible por LT(f2), restamos a 2xy +yel producto f2·2y (2xy +y)−[(x−1) ·2y] = y+ 2y= 3y Y como yno es divisible por LT(f1)ni por LT(f2), obtenemos que f= (xy + 2y)·f2+ 3y, y en este caso el resto es: r= 3y. Observación 1.31.Que el resto quede determinado o no de forma única es relevante para determinar si un polinomio dado pertenece a un ideal. Si al dividir fpor F= (f1, . . . , fs) 20 CAPÍTULO 1. BASES DE GROEBNER nulo f∈Ise verifica que LT(f)∈ hLT(g1),...,LT(gt)i. Si f∈I=hg1, . . . , gties no nulo, existirán polinomios hi∈K[x1, . . . , xn]tales que f= t X i=1 higi.(1.5) Obsérvese que MGRAD(f)⩽m´ax{MGRAD(higi); 1 ≤i≤t, higi6= 0}.(1.6) Dada una expresión del tipo (1.5) para f, denotemos µ(i) = MGRAD(higi), siendo higi6= 0. Sea A={µ(i); 1 ≤i≤t, higi6= 0}yδ= m´ax A, entonces la desigualdad (1.6) se puede reescribir como: MGRAD(f)⩽δ. Consideramos para ftodas las posibles expresiones del tipo (1.5). Para cada una de estas expresiones, podemos obtener un δdistinto, pero dado que el orden monomial es un buen orden, podemos elegir una expresión de la forma (1.5) para fde forma que δsea de grado mínimo. Si MGRAD(f) = δ, es decir, MGRAD(f) = MGRAD(hi0gi0)para algún i0∈ {1, . . . , t} entonces LT(gi0)divide a LT(f), por tanto LT(f)∈ hLT(g1),...,LT(gt)i. Habríamos concluido la demostración. Veamos que el otro caso MGRAD(f)<δno es posible por reducción al absurdo: Supongamos que MGRAD(f)<δy escribamos fde la forma siguiente: f=X µ(i)=δ higi+X µ(i)<δ higi. Si separamos los términos principales de los polinomios hi, podemos reescribir f de la siguiente forma: f= X µ(i)=δ LT(hi)gi + X µ(i)=δ (hi−LT(hi))gi+X µ(i)<δ higi (1.7) El sumando de la derecha es a su vez suma de términos de multigrado menor que <δ. Por tanto, la hipótesis MGRAD(f)<δequivale a que el sumando de la izquierda tenga multigrado <δ. Para cada ital que µ(i) = δ, sea LT(hi) = cixα(i). Entonces, el primer sumando en (1.7) se escribe de la forma X µ(i)=δ LT(hi)gi=X µ(i)=δ cixα(i)gi. Una vez obtenida esta expresión, estamos en las condiciones del enunciado del Lema 1.48, pues MGRAD(cixα(i)gi) = δy la suma tiene grado <δ. Por el Lema 1.48, tenemos que: X µ(i)=δ LT(hi)gi=X µ(i)=δ cixα(i)gi=X j,k cjk ·xδ−γ(jk)·S(gj, gk),(1.8) 1.6. PROPIEDADES DE LAS BASES DE GROEBNER. 21 donde cjk ∈Kyxγ(jk)= lcm(LM(gj),LM(gk)). Por hipótesis, aplicando el algoritmo de la división el resto de dividir S(gj, gk)por g1, . . . , gtes cero, por tanto existen polinomios aijk ∈K[x]tales que S(gj, gk) = t X i=1 aijk ·gi, y, por el algoritmo de la división, para los sumandos no nulos se verifica la acotación MGRAD(aijkgi)⩽MGRAD(S(gj, gk)).(1.9) Multiplicando S(gj, gk)por xδ−γ(jk)obtenemos la expresión xδ−γ(jk)·S(gj, gk) = t X i=1 bijkgi,(1.10) con bijk := xδ−γ(jk)aijk. El Lema 1.48 y la desigualdad (1.9) nos dicen que MGRAD(bijkgi)⩽MGRAD(xδ−γ(jk)·S(gj, gk)) <δ,(1.11) siempre que los polinomios involucrados en la expresión sean no nulos. Si sustituimos la expresión (1.10) en la ecuación (1.8), se obtiene X µ(i)=δ LT(hi)gi=X j,k cjk t X i=1 bijkgi!= t X i=1  X j,k cjkbijk gi= t X i=1 e higi,(1.12) siendo e hi:= Pj,k cjkbijk. Si e higi6= 0, de la ecuación (1.11) se sigue que MGRAD(e higi)<δ (ya que los cjk son escalares). Finalmente, sustituyendo Pµ(i)=δLT(hi)gi=Pt i=1 e higien la ecuación (1.7), obtenemos la expresión para f: f= t X i=1 e higi+X µ(i)=δ (hi−LT(hi))gi+X µ(i)<δ higi, del tipo (1.5) en la que todos los sumandos tienen multigrado <δ. Esto contradice la minimalidad de δ, concluyendo que necesariamente MGRAD(f) = δ. El Teorema 1.49 proporciona un algoritmo para comprobar si un conjunto dado de generadores de un ideal es una base de Groebner. Veamos un ejemplo muy básico de como realizar dicho algoritmo: Ejemplo 1.50. Consideremos el ideal I=hx−z2, y −z3i. Vamos a comprobar que el conjunto G={x−z2, y −z3}es una base de Groebner de I con el orden lexicográfico, con x>y>z. 22 CAPÍTULO 1. BASES DE GROEBNER Como en Gsolo hay 2 polinomios, la única sizigia que se puede construír con sus elementos es: S(x−z2, y −z3) = xy x(x−z2)−xy y(y−z3) = xz3−yz2. Ahora, si ejecutamos el algoritmo de la división para dividir este polinomio por Gobtenemos: S(x−z2, y −z3) = xz3−yz2=z3·(x−z2)+(−z2)·(y−z3)+0. Se tiene que el resto es cero, es decir: S(x−z2, y −z3)G= 0, y entonces en virtud del Teorema 1.49 podemos afirmar que Ges una base de Groebner para el ideal Icon el orden monomial elegido. Sin embargo, Gno es una base de Groebner de Isi el orden considerado es el graduado lexicográfico, con x>y>z, ya que en este caso los monomios z2yz3son mayores que los monomios xeyrespectivamente, y se producirían los siguientes resultados: S(−z2+x, −z3+y) = z3 z2(−z2+x)−z3 z3(−z3+y) = xz −y. Dado que z2yz3no dividen ni a xz ni a y, el resultado al ejecutar el algoritmo de la división es: S(x−z2, y −z3) = 0 ·(−z2+x)+0·(−z3+y) + xz −y Es decir: S(x−z2, y −z3)G=xz −y6= 0. 1.6.2. Construcción de una base de Groebner: Algoritmo de Buchberger. Por el Corolario 1.37, tenemos garantizado que todo ideal I6={0}, I ∈K[x1, . . . , xn] tiene al menos una base de Groebner. Ahora veremos un procedimiento para encontrar dicha base. Teorema 1.51 (Algoritmo de Buchberger).Sea I=hf1, . . . , fsi 6= 0 un ideal de polinomios. Entonces una base de Groebner para Ipuede construírse en un número finito de pasos usando el siguiente algortimo: Input:= F= (f1, . . . , fs) Output:= G= (g1, . . . , gt), F ⊂G G:= F REPEAT G0:= G FOR cada par {p, q}, p 6=q∈G0DO 1.6. PROPIEDADES DE LAS BASES DE GROEBNER. 23 T:= S(p, q)G0 IF S6= 0 THEN G:= G∪{T} UNTIL G:= G0 Demostración. Primero comprobaremos que el conjunto Gque hemos definido siempre está contenido en I: Inicialmente, Ges un conjunto de generadores de I, y por tanto G⊂I. Los elementos que se le añaden a Gson los restos T= S(p, q)G0 , con p, q elementos de G. Si Gestá contenido en I, también lo estarán p, q yS(p, q), y como estamos dividiendo por G0⊂I, obtenemos que G∪{T} ⊂ I. El algoritmo termina cuando Ges igual a G0. Esto significa que S(p, q)G= 0 para todo p, q ∈G. Por el Teorema 1.49, que Gverifique esta condición es equivalente a que sea una base de Groebner G. Falta por probar que el algoritmo efectivamente concluye. En cada iteración, el conjunto Gestá constituído por G0(el anterior G) y por los restos no nulos de las sizigias de elementos de G0. Entonces, como G0⊂G, se tiene que: hLT(G0)i⊂hLT(G)i.(1.13) Además, si G06=G, tampoco se tiene la igualdad entre LT(G0)yLT(G). Para probar esto, supongamos que un resto no nulo rde una sizigia se añade al conjunto G0. Por ser el resto de una división por G0,LT(r)no es divisible por ningún término principal de ningún elemento de G0, y entonces, LT(r)/∈LT(G0). Pero LT(r)∈LT(G)porque r∈G. La ecuación (1.13)nos dice que los ideales hLT(G0)ide las sucesivas iteraciones forman una cadena ascendente de ideales en K[x]. Usando la condición de cadena ascendente, se tiene que dicha cadena de ideales debe estabilizarse en un número finito de iteraciones, de forma que hLT(G0)i=hLT(G)i. Por el razonamiento que acabamos de hacer, esto implica que G=G0y así, el algoritmo termina en un número finito de iteraciones. Vamos a ilustrar el algoritmo de Buchberger con un ejemplo: Ejemplo 1.52. Sea I=hf1, f2i=hx3−2xy2, x2y−2y2iun ideal en K[x, y]y consideremos el orden lexicográfico, con x>y. {f1, f2}no es una base de Groebner ya que: S(f1, f2) = x3y x3(x3−2xy2)−x3y x2y(x2y−2y2) = x3y−2xy3−(x3y−2xy2) = −2xy3+2xy2. LT(S(f1, f2)) = −2xy3+ 2xy2/∈ hLT(f1),LT(f2)i. Nuestro algoritmo consiste en extender el conjunto inicial de generadores con nuevos polinomios de Ipara obtener una base de Groebner. Si intentamos dividir S(f1, f2)por F={f1, f2}, obtenemos: 24 CAPÍTULO 1. BASES DE GROEBNER S(f1, f2)=0·f1+ 0 ·f2+ (−2xy3+ 2xy2). Esto nos indica que deberíamos incluír −2xy3+2xy2en nuestro conjunto de generadores del ideal: f3=−2xy3+ 2xy2, F ={f1, f2, f3}. S(f1, f2) = f3⇒S(f1, f2)F= 0. S(f1, f3) = x3y3 x3·(x3−2xy)−x3y3 −2xy3·(−2xy3+ 2xy2)=2x3y2−2xy4. Tras realizar el algoritmo de la división, obtenemos que S(f1, f3)F= 2xy26= 0. Igual que antes, añadimos 2xy2al conjunto de generadores: f4= 2xy2, F ={f1, f2, f3, f4}. S(f1, f2)F= S(f1, f3)F= 0. S(f1, f4) = x3y2 x3(x3−2xy)−x3y2 2xy2(2xy2) = −2xy3= 1 ·f3−1·f4. S(f1, f4)F= 0. S(f2, f3) = x2y3 x2y(x2y−2y2)−x2y3 −2xy3(−2xy3+ 2xy2) = x2y2−2y4=y·f2−2y4+ 2y3. S(f2, f3)F=−2y4+ 2y3. Denotamos el polinomio por: f5=−2y4+ 2y3, y ampliamos el conjunto de generadores nuevamente: F={f1, f2, f3, f4, f5}. S(f1, f2)F= S(f1, f3)F= S(f1, f4)F= 0. S(f2, f4) = x3y2 x2y(x2y−2y2)−x3y2 2x3y2(2x3y2−2xy4) = xy4−2xy3=−y 2·f3−xy3. S(f2, f4)F=−xy3. Añadimos este polinomio al conjunto de generadores: f6=−xy3, F ={f1, f2, f3, f4, f5, f6}. Ahora, los únicos restos que no dan cero son los siguientes: S(f3, f6) = xy3 −2xy3(−2xy3+ 2xy2)−xy3 xy3(xy3) = −2xy2. S(f3, f6)F=−2xy26= 0. S(f4, f6) = x3y3 2x3y2(2x3y2−2xy4)−x3y3 xy3(xy3) = −2y4=f5−2y3. S(f4, f6)F=−2y36= 0. Como estos dos polinomios son monomios que no se dividen el único al otro, debemos añadir ambos a nuestro conjunto de generadores. Denotamos f7=−2xy2, f8=−2y3, y nuestro nuevo conjunto de generadores: F={f1, f2, f3, f4, f5, f6, f7, f8}. Ahora es sencillo comprobar que S(fi, fj)F= 0 para todo i, j ∈ {1,...,8}. En virtud del Teorema 1.49, F es base de Groebner de I. Una vez que hemos visto como construír una base de Groebner para un ideal I, vamos ahora a buscar, a partir de ella, una base de Groebner mejor, en el sentido de que no contenga elementos redundantes y sea lo más simple posible: Lema 1.53. Sea Guna base de Groebner para el ideal de polinomios I. Sea p∈Gun polinomio tal que LT(p)∈ hLT(G−{p})i. Entonces G−{p}es también una base de Groebner de I. 1.6. PROPIEDADES DE LAS BASES DE GROEBNER. 25 Demostración. Sea G={g1, . . . , gt, p}. Sabemos que hLT(g1),...,LT(gt),LT(p)i=hLT(I)i, y que LT(p)∈ hLT(G−{p})i=hLT(g1),...,LT(gt)i.Esto implica de forma inmediata que: hLT(g1),...,LT(gt)i=hLT(g1),...,LT(gt),LT(p)i=hLT(I)i. Y por tanto {g1, . . . , gt}=G−{p}es una base de Groebner de I. Definición 1.54. Una base de Groebner minimal para el ideal Ies una base de Groebner de Ital que: •LC(p)=1para todo p∈G. •Para todo p∈G, LT(p)/∈ hLT(G−{p})i. Proposición 1.55. Sean GyG0dos bases de Groebner minimales de un ideal I. Entonces: LT(G) = LT(G0). Demostración. Sean G={f1, . . . , fs}yG0={g1, . . . , gt}. Por definición de base de Groebner, se tiene la siguiente igualdad: hLT(f1),...,LT(fs)i=hLT(I)i=hLT(g1),...,LT(gt)i. Consideremos el primero de los polinomios de G, f1. La igualdad anterior nos garantiza que LT(f1)∈ hLT(g1),...,LT(gt)i. Por el Lema 1.13 sabemos que entonces existe j1∈ {1, . . . , t} tal que LT(gj1)|LT(f1). Por otro lado, LT(gj1)∈ hLT(f1),...,LT(fs)i, entonces existirá un índice i1∈ {1, . . . , s}tal que LT(fi1)|LT(gj1). Por ser Guna base de Groebner minimal necesariamente se tiene la igualdad LT(f1) = LT(gj1)y entonces ya tenemos probado que LT(f1)∈LT(G0). De forma análoga comprobamos que los términos principales LT(f2),...,LT(fs)también pertenecen a LT(G0). Si ahora intercambiamos los papeles de GyG0y usamos este mismo razonamiento, es inmediato comprobar que los términos principales LT(g1),...,LT(gt) pertenecen a LT(G). Definición 1.56. Una base de Groebner reducida para un ideal de polinomios Ies una base de Groebner G tal que: •LC(p)=1para todo p∈G. •Para todo p∈G, ningún monomio de p pertenece a hLT(G−{p})i. Proposición 1.57. Fijado un orden monomial en K[x1, . . . , xn], para cada ideal no nulo I⊂K[x1, . . . , xn]existe una única base de Groebner reducida. 26 CAPÍTULO 1. BASES DE GROEBNER Demostración. Primero probaremos que existe al menos una base de Groebner reducida. Sea Guna base minimal de I. Decimos que un elemento g∈Ges reducido para Gsi ningún monomio de Gpertenece a hLT(G−{g})i. Nuestro objetivo es modificar Ghasta que todos sus elementos sean reducidos. Una primera observación es que si ges reducido para G, entonces gtambién es reducido para cualquier otra base minimal de Ique contenga a g y tenga el mismo conjunto de términos principales. Esto es debido a que la definición de reducido solo involucra a los términos principales. Ahora, dado g∈G, sean g0=gG−{g}yG0= (G−{g})∪{g0}. Queremos ver que G0 es otra base de Groebner minimal de I. Para esto, observemos que LT(g0) = LT(g), ya que cuando dividimos gpor G−{g},LT(g)se añade al resto de la división debido a que no es divisible por ningún elemento de LT(G−{g}). Esto prueba que hLT(G0)i=hLT(G)i. Dado que G0está contenido en I, queda claro que G0es una base de Groebner, y también que es minimal. Finalmente, notemos también que g0es reducido para G0por construcción. Ahora, podemos tomar todos los elementos de Gy aplicar el proceso anterior para que todos los elementos sean reducidos. La base de Groebner podría cambiar cada vez que repetimos el proceso, pero si un elemento es reducido, lo sigue siendo siempre y cuando no cambiemos los términos principales de los elementos de la base. Así, repitiendo el proceso las veces que sea necesario, obtenemos una base de Groebner reducida. Nos falta demostrar la unicidad: Supongamos que Gy˜ Gson bases de Groebner reducidas para I. Entonces, en particular, Gy˜ Gson bases de Groebner minimales. y eso implica que tienen los mismos términos principales: LT(G) = LT(G0). Dado g∈G, hay un ˜g∈˜ Gtal que LT(g) = LT(˜g). Si podemos probar que g= ˜g, entonces G=˜ Gy tendremos probada la unicidad. Para probar g= ˜g, consideremos g−˜g∈I. Como Ges una base de Groebner, tenemos que g−˜gG= 0. Además, por 1.55 sabemos que LT(g) = LT(˜g). Esto significa que al restarlos, los términos principales se cancelan, y los términos restantes no son divisibles por ninguno de los elementos de LT(G) = LT(G0)puesto que son bases de Groebner reducidas. Esto prueba que g−˜gG=g−˜g= 0, y entonces g= ˜g. Con este resultado, queda resuelto el problema de decidir si dos ideales del anillo de polinomios K[x]son iguales: Corolario 1.58. Dos ideales no nulos de K[x1, . . . , xn]son iguales si, y sólo si, fijado un orden monomial poseen la misma base de Groebner reducida. Capítulo 2 Teoría de la Eliminación En este capítulo estudiaremos un método sistemático para la resolución de sistemas de ecuaciones polinómicas: el método de eliminación de variables. Resolver sistemas de ecuaciones polinómicas es extremadamente importante ya que nos permitirá hallar explícitamente los puntos que conforman las variedades afines algebraicas. Recordemos que: V(I) = {(a1, . . . , an)∈Kn/ f(a1, . . . , an) = 0 ∀f∈I}. Las bases de Groebner resultarán de utilidad para la demostración de los resultados más importantes que permiten llevar a cabo la resolución de los sistemas: El teorema de Eliminación y el teorema de Extensión. La aplicación más inmediata que mostraremos será resolver el Problema de Implicitación. 2.1. Teoremas de Eliminación y Extensión. Antes de introducir notación y resultados, veamos un ejemplo de resolución de un sistema de ecuaciones: Ejemplo 2.1. Consideremos el siguiente sistema de ecuaciones polinómicas: x2+y2= 0 y2−z2= 1 x2+y−z2= 0        Consideramos el ideal I=hx2+y2, y2−z2−1, x2+y−z2i. Ahora, consideramos una base de Groebner del ideal Irespecto al orden lexicográfico: G={x2+z2+ 1, y −2z2−1,4z4+ 3z2}. 27 28 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN Las ecuaciones obtenidas igualando los elementos de esta base a cero tienen exactamente las mismas soluciones que las iniciales, pues los dos conjuntos de polinomios generan el mismo ideal. Sin embargo, considerando las ecuaciones dadas por la base de Groebner, observamos que la última ecuación solo involucra a z, y es fácil de resolver: 4z4+ 3z2= 0 ⇒z∈ {0,±√3 2i} Sustituyendo estos resultados en y−2z2−1=0podemos obtener los valores de y. Finalmente, con los valores de yy de z, sustituímos en x2+z2+ 1 = 0 y obtenemos los valores de x. Así, las soluciones del sistema serían: (i, 1,0),(−i, 1,0),(i 2,−1 2,√3 2i),(−i 2,−1 2,√3 2i),(−i 2,−1 2,−√3 2i),(−i 2,−1 2,−√3 2i)!. Dos factores clave que nos han permitido resolver el sistema de esta forma han sido: Encontrar una ecuación en una sola variable: 4z4+ 3z2= 0 Extender las soluciones de esa ecuación al resto de ecuaciones, sustituyendo los valores obtenidos. La idea básica de la teoría de eliminación es que estos dos procesos puedan llevarse a cabo de forma general. Para justificar dichos resultados es necesario definir los ideales de eliminación: Definición 2.2. Fijemos un entero k∈ {0, . . . , n −1}. Dado un ideal I⊂K[x1, . . . , xn], el ideal de K[xk+1, . . . , xn]definido por Ik:= I∩K[xk+1, . . . , xn] se denomina ideal de eliminación k-ésimo de I. Si I=hf1, . . . , fsi, el ideal Ikproporciona las ecuaciones que verifican los puntos de V(I), que no contienen a las variables x1, . . . , xky que se pueden construir a partir de las ecuaciones f1=··· =fs= 0 dadas por el ideal original I. Para aclarar este concepto, consideremos los siguientes ejemplos Ejemplo 2.3. Sea I⊂K[x1, x2, x3, x4, x5]el ideal I=hx3 1−2x2+x4,7x2 2+x4−x5, x2 3+ 5x4 4, x5i. 2.1. TEOREMAS DE ELIMINACIÓN Y EXTENSIÓN. 29 En este caso, podemos decir que los generadores de Ison adecuados para eliminar variables, ya que se puede comprobar que: I0=I I1=h7x2 2+x4−x5, x2 3+ 5x4 4, x5i I2=hx2 3+ 5x4 4, x5i I3=I4=hx5i Ejemplo 2.4. Pero no siempre es inmediato hallar los ideales de eliminación de un ideal a partir de un sistema de generadores. Por ejemplo, sea I=hx1, x1+x2+x3, x3i ⊂ K[x1, x2, x3, x4]. En este caso, en dos de los generadores del ideal aparece la variable x1. Pero esto no significa que el primer ideal de eliminación I1sea igual a hx3i. Eligiendo otro sistema de generadores I=hx1, x2, x3i es muy sencillo ver que: I0=I, I1=hx2, x3i, I2=hx3i, I3={0}. Observación 2.5.El problema de eliminación consiste en, dado un ideal I⊂K[x1, . . . , xn], encontrar un sistema de generadores del ideal Ik=I∩K[xk+1, . . . , xn], para 0≤k < n. Es decir, se trata de encontrar un sistema de generadores del ideal I⊂K[x1, . . . , xn]que contenga a un sistema de generadores de Ik, para cada k∈ {0, . . . , n −1}. El siguiente teorema nos muestra cómo resolver este problema utilizando bases de Groebner respecto a un orden monomial adecuado, que nos permita eliminar variables. Definición 2.6. Sea y={x1, . . . , xk} ⊂ x={x1, . . . , xk, xk+1, . . . , xn}una colección de variables y z=x\y. Diremos que un orden monomial en K[x]elimina las variables ysi siempre que yα>yβse verifica que yαzσ>yβzν, para cualesquiera monomios zσyzν. Ejemplo 2.7. El orden monomial lexicográfico con x1> x2>··· > xnelimina las variables y={x1, . . . , xk}. El orden graduado lexicográfico no elimina ninguna variable. Teorema 2.8 (Teorema de Eliminación).Consideremos en K[x1, . . . , xn]el orden monomial lexicográfico determinado por x1> x2>··· > xn. Para cada k∈ {0, . . . , n −1} consideremos en K[xk+1, . . . , xn]el orden monomial inducido por el de K[x1, . . . , xn]. Sea I⊂K[x1, . . . , xn]un ideal y Guna base de Groebner de I. Entonces, en K[xk+1, . . . , xn], el conjunto Gk=G∩K[xk+1, . . . , xn]es una base de Groebner del ideal de eliminación k-ésimo Ik⊂K[xk+1, . . . , xn]. Demostración. Fijemos k∈ {0, . . . , n −1}. Para un subconjunto B⊂K[xk+1, . . . , xn] denotaremos por hBikel ideal de K[xk+1, . . . , xn]generado por B. Demostraremos que hLT(Gk)ik=hLT(Ik)ik. 36 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN Demostración. Por simplicidad escribiremos πk(V)en lugar de πk(VK(I)). Para ver que V(Ik)es la menor variedad que contiene a πk(V), en virtud de la Proposición 1.5, es equivalente demostrar que V(Ik) = V(I(πk(V))). Como sabemos que πk(V)⊂V(Ik)y V(I(πk(V))) es la variedad más pequeña que contiene a πk(V), la inclusión V(I(πk(V))) ⊂ V(Ik)es inmediata. Para ver la otra inclusión, sea f∈I(πk(V)) ⊂K[xk+1, . . . , xn], es decir, f(ak+1, . . . , an) = 0para todo (ak+1, . . . , an)∈πk(V). Si consideramos fcomo un polinomio en K[x1, . . . , xn], es claro que f(a1, . . . , an) = 0 para todo (a1, . . . , an)∈Vya que fno involucra a las variables x1, x2, . . . , xk. Por el Teorema 1.9 (Teorema de los ceros de Hilbert), existe un entero m tal que fm∈ hf1, . . . , fsi, y de nuevo, fmno involucra a las variables x1, x2, . . . , xk, por tanto, fm∈I∩K[xk+1, . . . , xn] = Iky entonces f∈√Ik, lo cual implica que I(πk(V)) ⊂√Ik. Entonces, como la aplicación Vinvierte las inclusiones, se tiene que V(Ik) = V(pIk)⊂V(I(πk(V))). El siguiente resultado se verifica para cualquier k∈ {1,2, . . . , n}, pero su demostración requieren técnicas más sofisticadas que no hemos tratado en este trabajo. Teorema 2.18 (Teorema de Clausura para k= 1).Bajo las hipótesis del teorema anterior: 1. El conjunto V(I1)⊂Kn−1es la variedad afín más pequeña que contiene a π1(V). 2. Si V6=∅entonces existe una variedad X$V(I1)⊂Kn−1tal que X∪π1(V) = V(I1). Demostración. El primer enunciado es un caso particular del teorema anterior. Veamos la demostración del segundo. Consideremos cada uno de los generadores f∈ {f1, . . . , fs}no nulos del ideal Iescrito como un polinomio en la variable x1con coeficientes en K[x2, . . . , xn]: f=cfxdf 1+términos de menor grado en x1, cf∈K[x2, . . . , xn], siendo degx1f=df. Para f= 0, denotaremos cf= 0. Se verifica que (V(cf1, . . . , cfs)∩V(I1)) ∪π1(V) = V(I1). En efecto, el contenido (V(cf1, . . . , cfs)∩V(I1)) ∪π1(V)⊂V(I1)es trivial, veamos que se verifica el otro contenido. Dado (a2, . . . , an)∈V(I1), si (a2, . . . , an)/∈V(cf1, . . . , cfs) entonces, por el Teorema de Extensión, existirá un punto de la forma (a1, a2, . . . , an)∈V, es decir se tendría que (a2, . . . , an) = π1(a1, a2, . . . , an)∈π1(V). 2.2. TEOREMA DE CLAUSURA. 37 Sea X⊂Kn−1, el subconjunto algebraico X:= V(cf1, . . . , cfs)∩V(I1). Si X(V(I1) habríamos demostrado el resultado enunciado. Supongamos que X=V(I1), es decir que V(I1)⊂V(cf1, . . . , cfs)o equivalentemente, por el teorema de los ceros, que cf1, . . . , cfs∈ √I1⊂K[x2, . . . , xn]. En particular cf1, . . . , cfs∈√I⊂K[x1, x2, . . . , xn]y por tanto V=V(f1, . . . , fs, cf1, . . . , cfs). Sustituyendo Ipor el ideal I0=hf1, . . . , fs, cf1, . . . , cfsi es sencillo comprobar que V=V(e I)siendo e I:= hf1−cdf1 f1, . . . , fs−cdf1 fs, cf1, . . . , cfsi. Cada nuevo generador del ideal e Ide la forma e fi:= fi−cdfi fique no es cero tiene grado en x1estrictamente menor que el grado de fi. Sustituyendo el ideal Ipor el ideal e Ipara determinar V,V=V(e I), y repitiendo el algoritmo inicial para el ideal e Idefinimos un conjunto algebraico e X⊂V(I1)⊂Kn−1tal que V(I1) = V(e I1) = e X∪π1(V). Si en esta iteración el conjunto e Xsigue siendo igual a V(e I1), repetimos el proceso hasta que el conjunto obtenido e Xsea un subconjunto propio de V(e I1) = V(I1), y entonces habríamos demostrado el enunciado. En cada iteración los grados en x1de los generadores del ideal e I1es cero o estrictamente menor que el de los generadores del ideal anterior I0. Si al iterar el proceso los generadores son de grado 0en x1, entonces cualquier (a2, . . . , an)∈ V(I1)⊂Kn−1es una solución parcial del sistema original, ya que que (a, a2, . . . , an)∈V, para cualquier a∈K; es decir, X=∅yπ1(V) = V(I1). 38 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN 2.3. Problema de implicitación. Una variedad afín algebraica V⊂Knno siempre viene determinada mediante ecuaciones polinómicas igualadas a cero. En ocasiones, se describen las coordenadas de los puntos de una variedad afín recurriendo al uso de expresiones algebraicas en función de ciertos parámetros. El problema de implicitación consiste en transformar las expresiones paramétricas en ecuaciones implícitas que determinen todos los puntos dados por la parametrización. Observación 2.19.Uno de los problemas inmediatos que se presentan es que el conjunto de puntos dados por una parametrización puede no ser igual a una variedad afín. Ejemplo 2.20. Una de las parametrizaciones de la circunferencia de radio unidad es la siguiente: x=1−t2 1 + t2, y =2t 1 + t2, t ∈K. Notemos que, sin embargo, xno toma el valor −1, sea cual sea el valor de t: x=−1 = 1−t2 1 + t2⇒1−t2=−1−t2⇒1 = −1. Es decir, el punto (−1,0) pertenece a la circunferencia pero es un punto que no viene dado por la parametrización. Surgen de forma natural dos preguntas: ¿Cuándo una parametrización nos proporciona todos los puntos de una variedad? Y en el caso de que no sea así, ¿Cómo encontramos los puntos de una variedad que no vienen dados por la parametrización? 2.3.1. Parametrización polinómica. Resolveremos primero el caso de que la parametrización sea polinómica. Consideremos una parametrización de un subconjunto de Kndado por una expresión de la forma              x1=f1(t1, . . . , tm) x2=f2(t1, . . . , tm) . . .. . . xn=fn(t1, . . . , tm) donde f1, . . . , fn∈K[t1, . . . , tm]son polinomios en las variables t1, . . . , tm. Podemos visualizar esta parametrización como la aplicación F:Km−→ Kn 2.3. PROBLEMA DE IMPLICITACIÓN. 39 definida por: F(t1, . . . , tm)=(f1(t1, . . . , tm), . . . , fn(t1, . . . , fm)). De esta forma, el conjunto parametrizado viene dado por F(Km)⊂Kn. Por tanto, nuestro problema consiste en hallar la menor variedad afín de Knque contiene a F(Km), y para ello vamos a recurrir al proceso de eliminación visto en las secciones anteriores. Consideramos el conjunto algebraico V=V(x1−f1, . . . , xn−fn)⊂Km+n, cuyos puntos son de la forma (t1, . . . , tm, f1(t1, . . . , tm), . . . , fn(t1, . . . , tm)).El conjunto Ves el grafo de la función F, es decir, la imagen de la aplicación i:Km−→ Km+n definida por: i(t1, . . . , tm)=(t1, . . . , tm, f1(t1, . . . , tm), . . . , fn(t1, . . . , tm)). Consideremos el siguiente diagrama conmutativo: Km+n πm ## Km i:: F//Kn A la vista del diagrama, la aplicación Fpuede descomponerse en F=πm◦i. Además, i(Km) = V, y se sigue la igualdad F(Km) = πm(i(Km)) = πm(V),(2.1) que nos dice que la imagen de la parametrización es la proyección de su grafo en sus n últimas componentes. Ahora, podemos usar resultados vistos en la teoría de la eliminación para hallar la variedad afín más pequeña que contiene a F(Km). En particular, el Teorema 2.17 nos dice que, si Kes algebraicamente cerrado, la variedad más pequeña que contiene a πm(V), y por tanto también a F(Km), es V(Im). ¿Qué ocurre en el caso de que el cuerpo Kno sea algebraicamente cerrado? Teorema 2.21 (Implicitación polinómica).Sea Kun cuerpo infinito y F:Km−→ Kn la aplicación definida por la parametrización polinómica. Sea I=hx1−f1, . . . , xn−fni ⊂ K[t1, . . . , tm, x1, . . . , xn]y sea Imel m-ésimo ideal de eliminación. Entonces V(Im)es la variedad afín más pequeña de Knque contiene a F(Km). Demostración. Como acabamos de ver, si Kes algebraicamente cerrado este resultado es un corolario inmediato del Teorema 2.17 (Teorema de Clausura). Veamos pues que ocurre cuando Kno es algebraicamente cerrado. Denotamos por Kla clausura algebraica de K, y de esta forma VKn(Im)denota la variedad en KyVKn(Im)denota la variedad en K. Por la ecuación (2.1) sabemos que F(Km) = πm(V)⊂VKn(Im). Sea ZK=VKn(g1, . . . , gs)una variedad de Kntal que 40 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN F(Km)⊂ZK. Nuestro objetivo es demostrar que VKn(Im)es la menor variedad afín que contiene a F(Km), es decir, que VKn(Im)⊂ZK. Como F(Km)⊂ZK, para todo i∈ {1, . . . , n},se tiene que gi◦F=gi(f1(t1, . . . , tm), . . . , fn(t1, . . . , tm)) ∈K[t1, . . . , tm] es cero en todo punto de Km, y como Kes un cuerpo infinito, gi◦Fes el polinomio cero. Esto implica en particular, que gi◦Ftambién es el polinomio cero en Km, y que entonces los gise anulan en todo punto de F(Km). De hecho ZK=VKn(g1, . . . , gs)es una variedad de Knque contiene a F(Km). Como el teorema es cierto para Kpor ser algebraicamente cerrado, tenemos que VKn(Im)⊂ZKen Kn. Si de esos conjuntos, solo tomamos las soluciones que están en Kn, es inmediato ver que VKn(Im)⊂ZK, y así queda probado el teorema. Con este resultado ya estamos en condiciones de construír un algoritmo para resolver el problema de implicitación en el caso de que la parametrización sea polinómica: Si tenemos nuestras variables definidas como: xi=fi(t1, . . . , tm), i ∈ {1, . . . , n}, consideramos el ideal I=hx1−f1, . . . , xn−fniy hallamos una base de Groebner de dicho ideal respecto al orden lexicográfico, con t1> . . . > tm> x1> . . . > xn. El teorema de eliminación nos garantiza entonces que los elementos de la base de Groebner que no contienen a las variables t1, . . . , tmforman una base de Im. En conclusión, esos elementos definen la variedad que buscamos de forma implícita. 2.3.2. Parametrización racional. Para resolver el problema en el caso general nos falta analizar el caso de que la parametrización sea racional: Consideremos una parametrización de un subconjunto de Kndado por una expresión de la forma              x1=p1(t1, . . . , tm) q1(t1, . . . , tm) . . .. . . xn=pn(t1, . . . , tm) qn(t1, . . . , tm) Donde p1, q1, . . . , pn, qn∈K[t1, . . . , tm], y q1, . . . , qnson no nulos. Una primera idea para abordar este nuevo problema es eliminar los denominadores y utilizar el mismo método que en el caso de parametrizaciones polinómicas, considerando ahora las ecuaciones: q1·x1−p1= 0, . . . , qn·xn−pn= 0. Sin embargo este argumento no siempre funciona. 2.3. PROBLEMA DE IMPLICITACIÓN. 41 Ejemplo 2.22. Para ver un caso en el que intentar eliminar los denominadores con este método no nos sirve, consideremos la parametrización racional dada por: x=u3 v2, y =v2 u3, z =u. Es sencillo comprobar que cualquier punto de este tipo (x, y, z)∈C3pertenece a la superficie xy = 1, esto es, que todos los puntos de la parametrización pertenecen a la variedad V(xy −1). Veamos que ocurre si quitamos los denominadores y aplicamos el algoritmo dado por el Teorema 2.21: Consideramos el ideal que resulta quitando los denominadores, I=hu3−v2x, u3y−v2, u −zi ∈ K[u, v, x, y, z]. El segundo ideal de eliminación de I, considerando el orden lexicográfico, con u > v > x>y>zes I2=I∩K[x, y, z] = h−z3+xyz3i=hz3·(xy −1)i. Entonces V(I2) = V(xy −1) ∪V(z3), y dado que la parametrización está contenida en V(xy −1), esto nos indica que V(I2)no es la menor variedad que contiene a la parametrización. Uno de los fallos que tiene este modo de proceder es que en este caso las funciones pi qi pueden no estar definidas en todos los puntos de Km. Para arreglar esto, podemos definir W=V(q1q2···qn)⊂Km. Como Wes el conjunto de todos los puntos en los que alguno de los denominadores se anula, es evidente que el morfismo F:Km−W−→ Kn, definido por F(t1, . . . , tm) = p1(t1, . . . , tm) q1(t1, . . . , tm),...,pn(t1, . . . , tm) qn(t1, . . . , tm) sí que es una aplicación bien definida. Igual que antes, para resolver el problema de implicitación necesitamos encontrar la menor variedad afín que contenga a F(Km−W). Si, como antes, relacionamos esta aplicación con la aplicación grafo iy la proyección en las últimas ncoordenadas πm, definidas previamente, obtenemos el diagrama: Km+n πm ## Km−W i88 F//Kn Si consideramos el ideal I=hg1·x1−f1, . . . , gn·xn−fni, la variedad que define dicho ideal contiene a la imagen de la aplicación i:i(Km−W)⊂V(I). Pero como vimos en el Ejemplo 2.22 esta variedad no siempre es la más pequeña que contiene a i(Km−W). Para arreglar este problema, vamos a añadir una variable más a nuestro anillo de polinomios. Sea q=q1q2···qnel producto de todos los denominadores de la parametrización racional, es decir, W=V(q). Consideramos ahora el ideal: J=I∪h1−qyi=hq1·x1−p1, . . . , qn·xn−pn,1−qyi ⊂ K[y, t1, . . . , tm, x1, . . . , xn]. 42 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN La ecuación que hemos añadido, 1−qy = 0, hace que los denominadores no se anulen. Ahora, para crear un diagrama similar al que teníamos en el caso inicial, necesitamos definir una nueva aplicación, j:Km−W−→ K1+m+n, dada por: j(t1, . . . , tm) = 1 q(t1, . . . , tm), t1, . . . , tm,p1(t1, . . . , tm) q1(t1, . . . , tm),...,pn(t1, . . . , tm) qn(t1, . . . , tm). Lema 2.23. Sean Jel ideal y j:Km−W−→ K1+m+nla aplicación que acabamos de definir. Entonces j(Km−W) = V(J)⊂K1+m+n. Demostración. Por las definiciones que acabamos de dar del ideal Jy de la aplicación j, la inclusión j(Km−W)⊂V(J)es inmediata. Sea (b, λ1, . . . , λm, a1, . . . , an)∈V(J)un punto. Tenemos que demostrar que dicho punto está en la imagen de Km−Wa través de la aplicación j. Igualando término a término el punto con la imagen de la aplicación, tenemos las siguientes igualdades: b=1 q(λ1, . . . , λm), λ1=λ1, . . . , λm=λm, a1=p1(λ1, . . . , λm) q1(λ1, . . . , λm), . . . , an=pn(λ1, . . . , λm) qn(λ1, . . . , λm). La primera de estas igualdades es equivalente a que 1−qy = 0. Esto nos indica, además, que ninguno de los denominadores se anula en (λ1, . . . , λm). Usando esto, las ecuaciones del ideal dadas por qi·xi−pi= 0 pueden resolverse con xi=pi qi, que es precisamente la expresión de la imagen de la coordenada (1 + m+i)-ésima a través de j, para todo i∈ {1, . . . , n}. Con esto queda claro que el punto pertenece a V(J)y queda probado el lema. Probado este resultado, la relación que hay ahora entre las aplicaciones es la siguiente: K1+m+n π1+m $$ Km−W j88 F//Kn Por lo que podemos descomponer la aplicación Fcomo: F=π1+m◦j, y entonces: F(Km−W) = π1+m(j(Km−W)) = π1+m(V(J)).(2.2) Con esta igualdad, podemos resolver el problema de implicitación usando la teoría de la eliminación de forma análoga al caso en el que la parametrización era polinómica. Teorema 2.24 (Implicitación racional).Sean Kun cuerpo infinito y F:Km−W−→ Kn la función determinada por la parametrización racional. Sea además J=hx1q1−p1, . . . , xnqn−pn,1−qyi ⊂ K[y, t1, . . . , tm, x1, . . . , xn] 2.3. PROBLEMA DE IMPLICITACIÓN. 43 donde q=q1q2···qn, y sea J1+m=J∩K[x1, . . . , xn]el (1+m)-ésimo ideal de eliminación para el orden lexicográfico determinado por y > t1> . . . > tm> x1> . . . > xn. Entonces V(Jm+1)es la variedad afín más pequeña de Knque contiene a F(Km−W). Demostración. Si Kes un cuerpo algebraicamente cerrado este resultado es un corolario del Teorema 2.17 (Teorema de clausura). Supongamos ahora que Kes un cuerpo infinito no necesariamente algebraicamente cerrado. Sea V=V(J)⊂K1+m+n. Por (2.2), sabemos que F(Km−W) = π1+m(V), y además se tiene la siguiente inclusión: π1+m(V)⊂VKn(J1+m). Consideremos ahora una variedad ZK=V(q1, . . . , qs)⊂Knque verifica que F(Km−W)⊂ZK.Tenemos que demostrar que V(J1+m)⊂ZK. Como F(Km−W)⊂ZK, para todo ise tiene que gi◦F∈K(t1, . . . , tm)es cero en todo punto de Km−W. Si demostramos que gi◦Fes cero en K(t1, . . . , tm), la demostración se concluye con el mismo argumento que en el Teorema 2.21. Consideremos el polinomio (gi◦F)·qry veamos que es cero en todo punto a∈K1+m+n: Si a∈W, tenemos que q(a) = 0, y si a∈Km−W, como Fsolo actúa sobre las variables t1, . . . , tm,(gi◦F)(a)=0. Entonces (gi◦F)·qres el polinomio cero, y como el anillo de polinomios es un dominio y q6= 0, entonces gi◦Fes necesariamente el polinomio cero, y la demostración se concluye entonces del mismo modo que en el Teorema 2.21. 44 CAPÍTULO 2. TEORÍA DE LA ELIMINACIÓN Capítulo 3 Aplicaciones de las bases de Groebner 3.1. Programación Lineal Entera. Consideremos un problema de programación lineal entera puro, es decir, donde todos los coeficientes que aparezcan representen números enteros. Dicho problema podría plantearse de la forma siguiente: mín / máx `(A),A=(A1, . . . , An)∈Znsujeto a: a11A1+a12A2+. . . +a1nAn⩽b1 a21A1+a22A2+. . . +a2nAn⩽b2 . . .. . ..... . .. . . am1A1+am2A2+. . . +amnAn⩽bm (3.1) Donde `:Zn−→ Res una función lineal con coeficientes reales, A=(A1, . . . , An)son las variables, y los coeficientes aij, bjson números enteros. Resolveremos únicamente el caso en el que las variables representen números enteros no negativos, es decir, A∈Nn, pero la forma de hallar la solución puede extenderse para resolver el problema con variables enteras. Como máx `(A) = -mín (-`(A)), nos restringiremos sin pérdida de generalidad al caso de minimizar funciones. Además, consideraremos únicamente restricciones de tipo ⩽ya que ai1A1+ai2A2+. . . +ainAn⩾bi es equivalente a −ai1A1−ai2A2−. . . −ainAn⩽−bi, 45 52 CAPÍTULO 3. APLICACIONES DE LAS BASES DE GROEBNER sean no negativos. El problema que nos encontramos es que ahora las variables zipueden tener exponente negativo, y por tanto las expresiones Qm i=1 zbi iyQm i=1 Qn j=1 zaij Aj i pueden no ser elementos del anillo de polinomios K[z1, . . . , zm]. Para resolver este problema vamos a hacer algo muy similar a lo que hicimos cuando queríamos extender el algoritmo del problema de implicitación polinómica al problema de implicitación racional: Consideramos una nueva variable t, el anillo de polinomios K[z1, . . . , zm, t]y el ideal J=htz1···zm−1i ⊂ K[z, t]. Lo que haremos será adaptar los resultados que hemos visto para el caso de coeficientes no negativos, en el que trabajábamos con el anillo de polinomios K[z]. Sin embargo, en este caso tendremos que trabajar con el anillo cociente K[z1, . . . , zm, t] htz1···zm−1i,(3.6) donde la igualdad tz1···zm−1=0nos indica que podemos pensar en la variable tcomo el producto de las variables z−1 1···z−1 m. Si reescribimos los coeficientes de la forma siguiente (a1j, . . . , amj)=(a0 1j, . . . , a0 mj) + αj(−1,...,−1) para j= 1, . . . , n, (b1, . . . , bm)=(b0 1, . . . , b0 m) + β(−1,...,−1), con a0 ij, b0 i, αj, β ∈Npara todo iy todo j, obtenemos las siguientes expresiones en el anillo cociente (3.6) para j= 1, . . . , n: m Y i=1 zaij i= m Y i=1 za0 ij −αj i= m Y i=1 za0 ij iz−αj i= m Y i=1 z−αj i! m Y i=1 za0 ij i!=tαj m Y i=1 za0 ij i, m Y i=1 zbi i= m Y i=1 zb0 i−β i= m Y i=1 zb0 i iz−β i= m Y i=1 z−β i! m Y i=1 zbi i i!=tβ m Y i=1 zb0 i i. Entonces, podemos reescribir la ecuación (3.5), adaptándola a las nuevas expresiones que tenemos para las restricciones en el anillo cociente (3.6), como: n Y j=1 tαj m Y i=1 za0 ij i!Aj =tβ m Y i=1 zb0 i i A la vista de esta igualdad, podemos adaptar la Proposición 3.1 al caso en el que nos encontramos. Esta proposición nos da una condición inequívoca para determinar nuestro conjunto de puntos factibles. 3.1. PROGRAMACIÓN LINEAL ENTERA. 53 Proposición 3.7. Sea Kun cuerpo y supongamos que nos encontramos en las condiciones que acabamos de ver, siendo J=htz1···zm−1i ⊂ K[z, t]. Definimos el homomorfismo de anillos ˜ϕ:K[w]−→ K[z1, . . . , zm, t] Jcomo: ˜ϕ(wj) = tαj m Y i=1 za0 ij i!+J, ˜ϕ(g(w1, . . . , wn)) = g(ϕ(w1), . . . , ϕ(wn)) + J, donde ϕ:K[w]−→ K[z, t]es el homomorfismo equivalente a ˜ϕpero sin cocientar módulo J. Entonces (A1, . . . , An)pertenece a la región factible de (3.3) si, y sólo si, ϕ(wA1 1···wAn n)+J=tβzb0 1 1···zb0 m m+J. Demostración. Por la Proposición 3.1, (A1, . . . , An)está en la región factible de (3.3) si, y sólo si n Y j=1 m Y i=1 zaij i!Aj = m Y i=1 zbi i, que ya hemos visto que se corresponde en el anillo cociente con n Y j=1 tαj m Y i=1 za0 ij i!Aj =tβ m Y i=1 zb0 i i. Como ˜ϕ(wj) = tαjQm i=1 za0 ij i+J, tomando clases de equivalencia, llegamos a la igualdad que nos garantiza que se verifican las restricciones:   n Y j=1 (ϕ(wj))Aj +J=ϕ(w1)A1···ϕ(wn)An+J= =ϕ(wA1 1···wAn n)+J=tβzb0 1 1···zb0 m m+J= tβ m Y i=1 zb0 i i!+J. Igual que en el caso de coeficientes no negativos, volvemos a definir los polinomios fj=tαj m Y i=1 za0 ij i∈K[z1, . . . , zm, t] de modo que la imagen por ϕde K[w1, . . . , wn]será el conjunto de polinomios de (3.6) que podamos expresar como polinomios en f1, . . . , fn. Con esto, podemos simplificar la expresión del homomorfismo ˜ϕ: ˜ϕ(wj) = fj+J. 54 CAPÍTULO 3. APLICACIONES DE LAS BASES DE GROEBNER El siguiente resultado, similar al de la Proposición 3.3, está enunciado para polinomios arbitrarios. Al igual que en el problema de coeficientes enteros no negativos, tendrá especial interés para la resolución del problema de programación lineal considerar los fjque acabamos de definir. Proposición 3.8. Consideremos polinomios arbitrarios f1, . . . , fn∈K[z, t], y un orden monomial en el que todo monomio que contenga a alguna de las variables zi, t es mayor que aquel en el que solo aparezcan las variables wj. Sea Guna base de Groebner para el ideal I=htz1···zm−1, f1−w1, . . . , fn−wni ⊂ K[z, t, w]y sea f∈K[z, t]. Si denotamos g=fG, entonces: •Existe f0∈K[w]tal que ˜ϕ(f0)=[f]∈K[z1,...,zm,t] Jsi, y sólo si, g∈K[w]. •Si f, f1, . . . , fnson monomios, y [f]está en la imagen por ˜ϕ, entonces gtambién es un monomio de K[w]. La demostración de este resultado se puede consultar en [9]. Probado esto, tenemos un resultado análogo al Teorema 3.6 que resuelve el problema de programación lineal entera con coeficientes enteros. Lo que nos dice dicho resultado es que si consideramos un orden monomial adaptado al problema (3.3) tenemos que: Si [f] = [zb0 1 1···zb0 m m]∈˜ϕ(K[w1, . . . , wn]),entonces el monomio fG∈K[w1, . . . , wn] proporciona una solución al problema 3.3 con coeficientes enteros. En caso contrario, el problema no tiene solución. 3.2. TEORÍA DE GRAFOS. 55 3.2. Teoría de grafos. Un grafo Gno dirigido se define de forma general mediante un conjunto finito de vértices VG, un conjunto finito de aristas EG, y una relación que asigna cada arista, e, a exactamente dos vértices, i, j, no necesariamente distintos. En el caso de que iyjsean iguales diremos que la arista ees un lazo. En general consideraremos únicamente grafos simples, esto es, sin lazos y sin aristas múltiples, y diremos que dos vértices i, j son adyacentes si existe una arista que los relacione. Podemos ilustrar un grafo G= (VG, EG)con un diagrama, asignando a cada vértice un punto en el plano y a cada arista una curva continua que no se corte a sí misma y cuyos extremos sean los puntos de los vértices a los que está asociada. Si existe un diagrama en el cual las aristas de Gno se corten en más puntos que en los vértices, diremos que el grafo Ges un grafo plano. Además, si cada par de vértices de un grafo Gestán conectados mediante una unión de aristas se dice que el grafo Ges conexo. En caso contrario diremos que Ges disconexo. Definición 3.9. Sea G= (VG, EG)un grafo general, con conjunto de vértices VGy conjunto de aristas EG. Una q-coloración propia de Ges una función c:VG−→ C de VGen un conjunto Cde cardinalidad q, tal que c(i)6=c(j)para todo par (i, j)∈EG. Diremos que el grafo Ges q-coloreable si admite una q-coloración propia, y llamaremos color a cada elemento del conjunto C. Es decir, en una q-coloración propia de un grafo no se admite que dos vértices adyacentes estén coloreados con el mismo color. Notemos que, para cualquier grafo G, cualquier coloración c:VG−→ Cinduce una relación de equivalencia en el conjunto de vértices VGen función del color, de manera que dos vértices i, j están relacionados si c(i) = c(j). De esta forma, cada color determina una clase de equivalencia, y basándonos en la partición inducida en el conjunto de vértices por esta relación, diremos que dos q-coloraciones propias son distintas cuando inducen particiones distintas en el conjunto de vértices VG. Más formalmente: Definición 3.10. Un grafo G= (VG, EG)es q-coloreable de manera única si existe una única q-coloración propia salvo permutaciones de colores. Definición 3.11. Si Ges un grafo q-coloreable pero no es k-coloreable para ningún númer natural k < q, diremos que qes el número cromático de G. 56 CAPÍTULO 3. APLICACIONES DE LAS BASES DE GROEBNER Ejemplo 3.12. El número cromático de un grafo completo de nvértices es n. A continuación se muestran coloraciones de los grafos completos de 2, 3, 4 y 5 nodos: 1 2 1 2 3 1 2 3 4 1 2 3 4 5 El procedimiento para decidir si un grafo es q-coloreable con el uso de bases de Groebner es sistemático: Definición 3.13. Sea Gun grafo simple y no dirigido, con vértices VG={1, . . . , n}y aristas EG. Llamaremos ideal de q-coloración del grafo Gal ideal IG,q ⊂C[x1, . . . , xn] generado por xq i−1,para todo i∈VG, xq−1 i+xq−2 ixj+. . . +xixq−2 j+xq−1 jpara todo (i, j)∈E. Lema 3.14. V(IG,q)⊂Cnestá formado por todas las q-coloraciones de G. En este caso, consideramos que el conjunto de colores son las raíces q-ésimas de la unidad. Demostración. La variedad V(IG,q)está formada por los puntos de Cnque anulan todas las ecuaciones de polinomios de IG,q igualados a cero. El polinomio xq i−1se anula si, y sólo si, el vértice ies una raíz q-ésima de la unidad, es decir, un color. Además, los polinomios xq−1 i+xq−2 ixj+. . . +xixq−2 j+xq−1 jserán cero únicamente si los vértices iyjtienen colores distintos, ya que xq−1 i+xq−2 ixj+. . . +xixq−2 j+xq−1 j=(xq i−1) −(xq j−1) xi−xj . De esta forma, tenemos un criterio para decir cuando un grafo es q-coloreable. Este lema nos dice además que, si V(IG,q) = ∅, entonces el grafo Gno admite ninguna q-coloración propia. Por otra parte, V(IG,q)6=∅nos indica que existe al menos una q-coloración propia de nuestro grafo G, pero no nos dice si esta coloración es única, ni cuántas existen. Ejemplo 3.15. Veamos a continuación un grafo que admite una única 4-coloración y otro que admite más de una: 3.2. TEORÍA DE GRAFOS. 57 1 2 3 5 4 G1 1 2 3 4 5 6 7 1 2 3 4 5 6 7 G2 Los ideales de 4-coloración en cada uno de los grafos son los siguientes. En el caso del grafo G1el conjunto de aristas es E1={(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}, mientras que en el caso del grafo G2el conjunto de aristas es E2={(1,2),(1,3),(1,5),(2,3),(2,5),(3,4),(3,5),(3,6),(4,6),(4,7),(5,6),(5,7),(6,7)}. Siguiendo esta notación, los generadores de los ideales de 4-coloración de los grafos Gk, para k∈ {1,2}, son: x4 i−1,para todo i∈Vk, x3 i+x2 ixj+xix2 j+x3 jpara todo (i, j)∈Ek. Donde Vkes el conjunto de nodos de cada grafo: V1={1,2,3,4,5}, V2={1,2,3,4,5,6,7}. A la vista del ejemplo anterior surge la siguiente cuestión: ¿Podemos saber si un grafo dado posee una única q-coloración? La respuesta es afirmativa si consideramos un conjunto apropiado de polinomios. A continuación detallamos quienes son esos polinomios. Sea γuna q-coloración del grafo Gde nvértices que usa los qcolores, y supongamos que los qúltimos vértices tienen cada uno un color distinto. Usaremos las variables x1, . . . , xn−q para los n−qprimeros vértices y las variables y1, . . . , yqpara los qúltimos. Consideremos los polinomios g1, . . . , gndefinidos por: •yq q−1. •hj(yj, . . . , yq) = X αj+...,+αq=j yαj j···yαq q, con j= 1, . . . , q −1. •xi+y2+. . . +yq, si color(xi) = color(y1). •xi−yj, si color(xi) = color(yj), si j⩾2. Usando los polinomios que acabamos de definir sí que es posible determinar cuando un grafo es q-coloreable de forma única. 58 CAPÍTULO 3. APLICACIONES DE LAS BASES DE GROEBNER Teorema 3.16. Dado un grafo G, sea IG,q su ideal de q-coloración. Consideremos las variables x1, . . . , xn−q, y1, . . . , yqy los polinomios g1, . . . , gnque hemos definido anteriormente. Entonces los siguientes resultados son equivalentes: iGes q-coloreable de manera única. ii g1, . . . , gn∈IG,q. iii {g1, . . . , gn}es la base de Groebner reducida de IG,q respecto al orden lexicográfico con x1> . . . > xn−q> y1> . . . > yq. La demostración de este resultado puede consultarse en [7]. Ejemplo 3.17. Dado el grafo Gsiguiente, 01 02 0304 05 06 07 08 0910 11 12 Las variables y1, y2ey3son las asociadas a los nodos 10,11 y12 respectivamente. Los polinomios g1, . . . , gnque acabamos de definir, asociados al grafo G, son {y3 3−1, y2 2+y2y3+y2 3, y1+y2+y3, x7−y3, x4−y3, x3−y3, x9−y2, x6−y2, x2−y2, x8+y2+y3, x5+y2+y3, x1+y2+y3}. En particular, los polinomios h1yh2son: h1(y1, y2, y3) = y1+y2+y3, h2(y2, y3) = y2 2+y2y3+y2 3. Ahora, si calculamos G, la base de Groebner reducida del ideal de 3-coloración del grafo G,IG,3, nos encontramos con que es precisamente la misma, teniendo en cuenta que las variables y1, y2ey3se corresponden con x10, x11 yx12 respectivamente. G={x3 12 −1, x7−x12, x4−x12, x3−x12, x2 11 +x11x12 +x2 12, x9−x11, x6−x11 x2−x11, x10 +x11 +x12, x8+x11 +x12, x5+x11 +x12, x1+x11 +x12}. Esto nos indica que el grafo Gadmite una única 3-coloración, que salvo permutaciones de colores, es la dada al comienzo del ejemplo. 3.2. TEORÍA DE GRAFOS. 59 Ejemplo 3.18. Este procedimiento para determinar si un grafo es q-coloreable, o si posee una q-coloración única, también puede aplicarse a la resolución de Sudokus. Para esto, basta darse cuenta de que un Sudoku puede verse como un grafo. El conjunto de vértices sería VS={1,...,81}, dado que cada cuadrado del Sudoku representa un vértice. Si dos cuadrados i, j pertenecen a la misma fila, a la misma columna o al mismo bloque de 3x3cuadrados, entonces la arista (i, j)pertenecerá al conjunto de aristas, ES. De esta forma, todos los vértices asociados a cuadrados que pertenecen a la misma fila, columna o bloque son adyacentes, y podemos considerar un Sudoku como un grafo GS= (VS, ES). Nuestro objetivo a la hora de resolver el Sudoku es dar una 9-coloración propia, con la única salvedad de que en este caso nuestros ’colores’ serán los números del 1al 9. La forma de resolverlo es la siguiente: •Consideramos el grafo GSdefinido como acabamos de explicar. •Asociamos a cada vértice ila variable xi, con i∈ {1,...,81}, y por cada dígito j= 1,...,9, buscamos un vértice ique tenga a jcomo dato inicial, y le cambiamos el nombre a xipor yj. •Consideramos el ideal de 9-coloración del grafo, IG,9. •Le añadimos al ideal IG,9los 8 polinomios de la forma: hj(yj, . . . , y9) = X αj+...+α9=j yαj j···yα9 9,con j∈ {1,...,8}. •Por cada dato adicional j6= 1, que esté en un vértice ique no hemos renombrado por yj, le añadimos al ideal IG,9el polinomio xi−yj. •Por cada 1adicional que tengamos como dato, que esté en un vértice ique no hemos renombrado por yj, le añadimos al ideal IG,9el polinomio xi+y2+. . . +y9. Notemos que ahora el ideal IG,9consta de todos los polinomios g1, . . . , gna los que se refiere el Teorema 3.16. Si el Sudoku está bien planteado, dicho teorema nos garantiza unicidad de 9-coloración y por tanto podremos resolverlo. 60 CAPÍTULO 3. APLICACIONES DE LAS BASES DE GROEBNER 3.3. Criptosistemas Polly Cracker. La criptografía se define como el conjunto de procedimientos y técnicas para escribir un mensaje de un modo enigmático, de forma que solo sea legible para quien sepa descifrarlo. A estos procedimientos se les denomina criptosistemas, y constan de dos etapas: la primera encripta el mensaje con una cierta clave, haciéndolo ilegible, y la segunda utiliza dicha clave para obtener el mensaje original. Podemos clasificar los diferentes criptosistemas según sus claves: •Simétrico o de clave privada: Utiliza la misma clave para encriptar el mensaje y para desencriptarlo. •Asimétrico o de clave pública: Usa dos claves diferentes. La clave de encriptado es pública, mientras que la de desencriptado no lo es. Nos centraremos en el estudio de criptosistemas de clave pública, en particular en los criptosistemas Polly Cracker. Desde el punto de vista matemático, el encriptado del mensaje consiste en una aplicación εentre dos conjuntos a los que llamaremos alfabeto inicial yalfabeto final. Llamaremos mensaje a un elemento del alfabeto inicial, y su imagen a través de la aplicación εserá el mensaje encriptado. Por tanto, desencriptar un mensaje consiste en hallar la aplicación inversa de ε:ε−1. La seguridad de un criptosistema depende de la dificultad de determinar la aplicación ε−1. Los criptosistemas Polly Cracker se caracterizan porque la clave pública que proporcionan es, o bien una base de Groebner de un polinomio en varias variables, o bien un punto de la variedad afín definida por un ideal. Tenemos la siguiente situación: Bob quiere transmitirle un mensaje ma Alice sin que Eve pueda saber en qué consiste dicho mensaje. Para ello, Bob encripta mcon la clave pública proporcionada por Alice, y transmite m0. Alice, conociendo la clave privada, debe ser capaz de recuperar m, pero Eve, que no posee más datos que los proporcionados por Bob, no. Bob encripta  Alice desencripta  m∈alfabeto inicial //m0∈alfabeto final //m Eve OO 3.3. CRIPTOSISTEMAS POLLY CRACKER. 61 El procedimiento que se ha de seguir para transmitir el mensaje, según el criptosistema Polly Cracker abstracto, es el siguiente: Alice toma un conjunto de polinomios Fque generan un ideal I, del cuál conoce un cero, ψ∈Kn. Es decir, ψ∈V(I)o, equivalentemente, f(ψ) = 0 para todo f∈I. La clave que se hace pública en este caso es el conjunto de polinomios Fque generan el ideal I, y la clave secreta es el punto ψ. La forma de encriptar el mensaje m∈Kes la siguiente: Bob toma un polinomio arbitrario h∈Iy computa el mensaje encriptado, que es el polinomio c:= h+m. Para obtener el mensaje original, Alice solo tiene que evaluar el polinomio en el punto ψ: c(ψ) = h+m(ψ) = h(ψ) + m(ψ) = h(ψ) + m=m. La seguridad de este criptosistema se basa en la dificultad de hallar un cero del ideal I, es decir, en la dificultad de resolver un sistema de ecuaciones algebraicas. En la práctica, para asegurar que dicho sistema de ecuaciones no tenga una solución fácil de calcular en tiempo polinomial, se selecciona el conjunto de polinomios Fde forma que sean una transcripción de un problema NP-completo, de forma que resolver el sistema de ecuaciones es equivalente a resolver este problema. Los primeros en proponer estos criptosistemas fueron Koblitz y Fellows en 1994 [10]. Se basaron en problemas relacionados con la teoría de grafos, de hecho su idea inicial fue codificar el problema de 3-coloración de un grafo. Ejemplo 3.19. Sea G= (VG, EG)un grafo. Alice conoce una 3-coloración de este grafo, que, recordemos, es una aplicación c:VG−→ {1,2,3}que verifica que si (i, j)∈EG entonces c(i)6=c(j). Para transmitir esta aplicación en lenguaje polinomial, se definen los conjuntos de polinomios F0, F1, F2, F3en las variables xi,k, dadas por xi,k = 1 si c(i) = k, y xi,k = 0 en caso contrario. •F0={xi,1·xi,2, xi,1·xi,3, xi,2·xi,3,1⩽i⩽n}. Cada vértice no puede estar pintado de dos colores distintos. •F1={xi,1+xi,2+xi,3−1,1⩽i⩽n}. Cada vértice está pintado de al menos un color. •F2={xi,1·xj,1, xi,2·xj,2, xi,3·xj,3,(i, j)∈EG}. Dos vértices conectados por una arista están pintados con colores distintos. •F3={x2 i,k −xi,k,1⩽i⩽n, 1⩽k, ⩽3}. Las variables xi,k sólo pueden tomar los valores 0y1, es decir, xi,k ∈Z2. La clave pública es F=F0∪F1∪F2∪F3. Como ya vimos en la sección anterior, conocer una 3-coloración equivale a conocer un punto de la variedad afín definida por el ideal generado por F.