Bases de Gröbner y Sudokus

Vista previa del material en texto

Bases de Gröbner y su aplicación
a la resolución de Sudokus
Bárbara Zapater Zarroca
Trabajo de fin de grado en Matemáticas
Universidad de Zaragoza
Directores del trabajo:
José Ignacio Cogolludo Agustín y
Jorge Martín Morales
Espacio
9 de febrero de 2021
Prólogo
Lógica, rapidez, paciencia y matemáticas. Teniendo en cuenta estos cuatro conceptos podemos re-
solver el juego del Sudoku, el cual sigue siendo un pasatiempo emocionante para millones de personas.
Geométricamente hablando, un Sudoku es un tablero de tamaño 9×9 dividido en cajas 3×3, las cuales
poseen números entre el 1 y el 9. Este rompecabezas obedece las siguientes reglas: no puede haber
números repetidos en la misma fila, columna o caja 3× 3. Pero, ¿por, para qué y cómo se aplican las
matemáticas a la resolución de este pasatiempo? Es en este contexto donde se basa el presente trabajo.
La historia de los Sudokus se remonta a un juego del siglo XVIII, donde los matemáticos suizos lo
llamaron “Cuadrados latinos”. Sin embargo, el juego que conocemos actualmente fue inventado a fina-
les de la década de 1970 en Nueva York. Este juego, ideado por el arquitecto Howard Garns, se conocía
como “Ubicar números”, pues consistía en colocar números en los espacios vacíos de una cuadrícula.
Actualmente, este rompecabezas se conoce como “Sudoku”. El nombre proviene de dos palabras japo-
nesas: Su, que significa número y Doku, que significa solo. Este juego matemático fue muy conocido en
Japón a partir de 1986 aunque su popularidad mundial llegaría unos años más tarde, en torno al 2005.
Hoy en día el Sudoku sigue siendo un enigma habitual en los periódicos, páginas online, revistas,
concursos... Además, como se trata de un puzle numérico que estimula las capacidades mentales y la
memoria, permite que no sea solo una diversión, sino que también resulte un aprendizaje.
Por otra parte, existen algunas variantes de este famoso juego. En [7] se da un modelo matemático
junto con su sistema de ecuaciones algebraicas. Algunas de estas variantes son: el tablero está coloreado
en gris y blanco de manera que las celdas grises contienen números pares y las celdas blancas solamente
impares (Sudoku par-impar), se puede dar como pista inicial la suma de un grupo de celdas en vez del
valor de cada celda individual (Sudoku killer), el tablero tiene formas distintas de un rectángulo (Sudo-
kus geométricos), etc.
Aunque de primeras resulte cuanto menos curioso, realmente el Sudoku se basa en fundamentos
matemáticos, y por ello existen métodos numéricos con los que poder resolverlos. Tratando el Sudoku
como si fuera un grafo, vinculando así la geometría y el álgebra, podemos resolver este juego lógico. Un
concepto clave para ello son las bases de Gröbner que, de una manera elegante y directa, nos permitirán
conocer todas las soluciones de un sistema de ecuaciones. Estas bases de ideales se forman de tal manera
que para todo polinomio del ideal, el término principal de este polinomio es divisible por alguno de los
términos principales de los polinomios que componen dicha base. Además, para ello, en este trabajo nos
familiarizaremos con una de las muchas aplicaciones de las bases de Gröbner, la coloración de grafos.
Cabe mencionar la variedad de aplicaciones relacionadas con esta teoría, entre las que se encuentran
calcular el polinomio mínimo en extensiones de cuerpos, dar demostraciones automáticas en Geometría
Euclidiana, estudiar sistemas criptográficos y programación entera e incluso estudiar algunos resultados
de Teoría de grafos.
III
Este trabajo está organizado del siguiente modo. En el Capítulo 1 se tratan los fundamentos alge-
braicos y conceptos previos que introducen la teoría de las bases de Gröbner. En el Capítulo 2 profun-
dizaremos en dicha teoría para lo cual trabajaremos con polinomios en varias variables. Para estos dos
primeros capítulos de información más teórica nos hemos basado en el libro [5], pero hay otras referen-
cias sobre este tema como son [1] y [9]. A continuación, en el Capítulo 3 nos centraremos en estudiar el
problema del coloreado en un grafo, lo cual está fundamentado en la Sección 3 de [4]. Finalizando, en el
Capítulo 4 aplicaremos lo estudiado en los tres capítulos previos para conseguir nuestro objetivo, resol-
ver Sudokus aplicando las matemáticas y la computación. Este capítulo final apoya su desarrollo y base
teórica en [7]. Por último, en el Apéndice A se presentan varios códigos, utilizados para la resolución
de algunos ejemplos implementados mediante el software SageMath [10], el cual usa en “background”
el programa SINGULAR [6] para calcular las bases de Gröbner.
Toda esta base matemática es la que permite que la gente pueda poner a prueba su cerebro con
acertijos lógicos, interesantes y desafiantes. Por lo cual, el Sudoku seguirá siendo un entretenimiento
querido y popular en la vida cotidiana de millones de personas en todo el mundo.
Palabras clave: polinomios, algoritmo de la división, orden monomial, ideales monomiales, Lema
de Dickson, bases de Gröbner, Teorema de las bases de Hilbert, algoritmo de Buchberger, grafo,
k-coloración, Sudoku, Shidoku.
IV
Summary
In this project it will be explained several theoretical results and practical examples related to Sudo-
kus. More specifically, this work will be based on the study of the Gröbner bases and its application to
both graph theory and Sudokus resolution.
This project is divided into four chapters. A brief description of each chapter will be given inmedia-
tely below.
- Chapter 1: Previous concepts and fundamentals
To begin with, the necessary concepts for understanding the other chapters are given. These con-
cepts include definitions such as monomial, polynomial, affine space, affine and linear varieties
and ideal, among others. The existence and uniqueness of the division algorithm for polynomials
in one variable will be studied.
- Chapter 2: Gröbner Bases
Once the previous part is completed, the main part of this project will be studied. In this second
chapter, the theory of Gröbner bases will be introduced and studied. Polinomials in K[x1, . . . ,xn]
will be dealt and how to order monomials will be discussed, explaining some of the existing
monomial orderings types. This concept will be important to study the division algorithm in
K[x1, . . . ,xn] which will be better understood by an example. Besides, Dickson’s Lemma and
Hilbert’s basis Theorem will be stated and proved. Then, Buchberger’s algorithm will be unders-
tood. That result will be used to construct the Gröbner bases. A code of this algorithm has been
implemented using SageMath, which can be found in the Appendix A. To end this chapter, four
problems about polynomials and ideals will be solved thanks to the Gröbner bases:
1. The ideal description problem.
2. The ideal membership problm.
3. The problem of solving polinomial equations.
4. The implicitization problem.
- Chapter 3: Graph coloring
Graph coloring with k colors is the main goal of this chapter. First of all, the kind of graphs we
need will be defined and then, the explanation and resolution of this problem will be treated. To
do this, a system of polynomial equations imposing some conditions will be generated. To solve
this system, the Gröbner bases will be used, for which a SageMath code has been implemented.
Moreover, this code is explained in the Appendix A.
- Chapter 4: Sudokus and Gröbner bases
Sudokus will be solved using Gröbner bases theory and the Sudoku will be considered as if it
was a graph in order to apply some results of Chapther 3. That is, to solve Sudokus a system
of polynomial equations has to be obtained, in the same way that it is obtained for the graph
coloring problem in the previous chapter. An ideal in the polynomial ring of several variables will
V
be associated to the Sudoku. This ideal will be generated by the polynomials which define the
system of equations. The reduced Gröbner basis will be calculated for this ideal whose generators
form a system equivalent to the originalsystem. That is why solving this new system of equations,
using mathematics and computation, the solution to the Sudoku is obtained. In the Appendix A it
is explained how to write with SageMath a Sudoku with the initial clues given to be able to apply
the code generated for the previous chapter and then the system will be solved. Finally, some
mathematical conjectures are discussed. Moreover, a conclusion to this interesting application of
the Gröbner bases is given.
VI
Índice general
Prólogo III
Summary V
1. Conceptos y fundamentos previos 1
1.1. Polinomios en espacios afines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Variedades afines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Ideales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4. Polinomios en una variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Bases de Gröbner 5
2.1. Orden monomial en varias variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2. El algoritmo de la división en varias variables . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Ideales monomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4. El Teorema de las bases de Hilbert y bases de Gröbner . . . . . . . . . . . . . . . . . 11
2.5. Criterio y algoritmo de Buchberger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6. Aplicaciones de las bases de Gröbner . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Coloreado de grafos 17
3.1. Resolución del problema del k-coloreado . . . . . . . . . . . . . . . . . . . . . . . . 18
4. Sudokus y bases de Gröbner 20
4.1. Sudokus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.1.1. Caso particular: Shidokus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.1.2. Resolución Sudokus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1.3. Generalización n×n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2. Conjeturas matemáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3. Conclusión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
A. Códigos SageMath 27
Bibliografía 31
VII
Capítulo 1
Conceptos y fundamentos previos
A lo largo de este capítulo daremos algunas definiciones y algunos resultados preliminares que serán
de relevancia para comprender las bases de Gröbner, objeto principal de estudio del marco teórico.
1.1. Polinomios en espacios afines
Definición 1. Un monomio xα en las variables x1, . . . ,xn es un producto de la forma
xα = xα1
1 · x
α2
2 · · ·x
αn
n
donde todos los exponentes α1, . . . ,αn son enteros no negativos. El orden total de un monomio es la
suma de sus exponentes, el cual denotaremos mediante |α|.
Definición 2. Un polinomio f en las variables x1, . . . ,xn con coeficientes en un cuerpo K es una com-
binación lineal finita de monomios con coeficientes también en K. Escribiremos el polinomio f de la
siguiente manera:
f = ∑
α
aαxα , aα ∈ K, α = (α1, . . . ,αn).
Denotaremos mediante K[x1, . . . ,xn] al conjunto de todos los polinomios en x1, . . . ,xn con coeficien-
tes en el cuerpo K. Este conjunto forma un anillo de polinomios.
Definición 3. Sea f = ∑
α
aαxα un polinomio en K[x1, . . . ,xn]. Entonces:
i) El coeficiente del monomio xα es aα .
ii) Si aα 6= 0, entonces aαxα será un término del polinomio f .
iii) El grado total de f 6= 0 es el máximo |α| tal que el coeficiente aα es no nulo. Lo denotaremos
mediante grado( f ).
Ejemplo 1. Hola
Sean los monomios −15x2 y 3xy4. Entonces el orden total del primer monomio es 2 y el orden
total del segundo monomio es 1+4 = 5.
Sea ahora el polinomio f = 3xy4−15x2 formado como combinación lineal de los dos monomios
anteriores. En primer lugar, notar que f es un polinomio en R[x,y].
• El coeficiente del monomio 3xy4 es 3 y el coeficiente de −15x2 es −15.
• f está compuesto por dos términos: 3xy4 y −15x2.
• grado( f ) = 5 (ya que 1+4 = 5 > 2).
1
2 Capítulo 1. Conceptos y fundamentos previos
1.2. Variedades afines
Definición 4. Sea un cuerpo K y un entero n positivo. Entonces denotaremos mediante Kn al espacio
afín de dimensión n sobre K formado por n-tuplas cuyos elementos están en K.
Los polinomios y los espacios afines están relacionados. La ventaja de trabajar con el anillo de
polinomios K[x1, . . . ,xn] es que se puede identificar, cuando K es infinito, con las funciones polinómicas
del espacio afín Kn. Es decir, identificamos los polinomios con las funciones evaluadas en Kn. De este
modo, los polinomios definen variedades afines y así se puede enlazar el álgebra con la geometría.
Definición 5. Sea K un cuerpo y sean f1, . . . , fs polinomios en K[x1, . . . ,xn]. Entonces la variedad afín
definida por f1, . . . , fs viene dada por el siguiente conjunto
V( f1, . . . , fs) = {(a1, . . . ,an) ∈ Kn | fi(a1, . . . ,an) = 0, ∀ 1≤ i≤ s} ⊆ Kn.
Es decir, V( f1, . . . , fs) es el conjunto de puntos a1, . . . ,an que anulan a todos los polinomios f1, . . . , fs.
Definición 6. Fijemos ahora un cuerpo K y consideremos un sistema lineal de m ecuaciones con coefi-
cientes en K
a11x1 + · · ·+a1nxn = b1,
... (1.1)
am1x1 + · · ·+amnxn = bm.
La solución de estas ecuaciones forman una variedad afín en Kn llamada variedad lineal.
En el Capítulo 2 estudiaremos cómo obtener todas las soluciones del sistema de ecuaciones (1.1) y
en el Capítulo 3 lo aplicaremos.
1.3. Ideales
El objetivo de esta sección es introducir el concepto de ideal. Así mismo, veremos cómo están
relacionados los ideales con las variedades afines.
Definición 7. Un subconjunto I ⊆ K[x1, . . . ,xn] se dice que es un ideal si cumple:
i) 0 ∈ I.
ii) Si f ,g ∈ I, entonces f +g ∈ I.
iii) Si f ∈ I y h ∈ K[x1, . . . ,xn], entonces h f ∈ I.
El primer ejemplo natural de un ideal es el ideal generado por un número finito de polinomios. Es
decir, si f1, . . . , fs ∈ K[x1, . . . ,xn] entonces
〈 f1, . . . , fs〉=
{
s
∑
i=1
hi fi
∣∣h1, . . . ,hs ∈ K[x1, . . . ,xn]
}
es un ideal de K[x1, . . . ,xn]. Diremos que 〈 f1, . . . , fs〉 es el ideal generado por f1, . . . , fs.
Definición 8. Sea I un ideal. Se dice que I está finitamente generado si existe un número finito de
polinomios f1, . . . , fs ∈ K[x1, . . . ,xn] tal que I = 〈 f1, . . . , fs〉.
Veamos ahora que una variedad depende solamente del ideal generado por sus ecuaciones.
Proposición 1.1. Si 〈 f1, . . . , fs〉= 〈g1, . . . ,gt〉, entonces se tiene V( f1, . . . , fs) = V(g1, . . . ,gt).
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 3
Ejemplo 2. Consideramos la variedad V(2x2 +3y3−11,x2− y2−3). Sea I1 = 〈2x2 +3y3−11,
x2− y2−3〉= 〈F1,F2〉 y sea I2 = 〈x2−4,y2−1〉= 〈 f1, f2〉. Veamos, por doble contenido, que I1 = I2 :
• F1 = 2 f1 +3 f2 ∈ I2, F2 = f1− f2 ∈ I2⇒ I1 ⊆ I2.
• f1 =
1
4
(F1 +3F2) ∈ I1, f2 =
1
5
(F1−2F2) ∈ I1⇒ I2 ⊆ I1.
Por lo tanto, aplicando la Proposición 1.1 obtenemos V(2x2+3y3−11,x2−y2−3)=V(x2−4,y2−1)=
{(±2,±1)}.
Este ejemplo nos muestra que si cambiamos los polinomios que generan el ideal, podemos determi-
nar más fácil la variedad.
1.4. Polinomios en una variable
En esta sección vamos a estudiar el algoritmo de la división para polinomios en una variable. Este
algoritmo lo usaremos para determinar la estructura de los ideales en K[x]. Asimismo nos ayudará a
entender la idea del máximo común divisor ya que se muestra un método para calcularlo, el cual es
análogo al algoritmo de Euclides sobre los enteros.
Definición 9. Sea f un polinomio no nulo de modo que f = c0xm+c1xm−1+ · · ·+cm ∈ K[x] con ci ∈ K
y c0 6= 0 (es decir, grado( f ) = m). Se dice que c0xm es el término principal de f y lo denotaremos
mediante LT ( f ).
Proposición 1.2 (El algoritmo de la división en K[x]). Sea K un cuerpo y sea g un polinomio no nulo
en K[x]. Entonces todo polinomio f ∈ K[x] se puede escribir como
f = q ·g+ r,
donde q,r ∈ K[x] y el resto verificar = 0 o grado(r) < grado(g). Es más, q y r son únicos y existe un
algoritmo para calcularlos.
Tomamos como variables de entrada g y f y como variables de salida q y r. A continuación, se
muestra un algoritmo presentado en forma de pseudocódigo para hallar tales q y r.
Dado un ideal nos gustaría ser capaces de encontrar su generador de una forma efectiva. Para ello
necesitamos la siguiente definición.
Definición 10. Un máximo común divisor de los polinomios f1, . . . , fs ∈ K[x] es un polinomio h tal que:
i) h divide a f1, . . . , fs.
ii) Si p es otro polinomio que divide a f1, . . . , fs, entonces p es múltiplo de h.
Cuando h cumpla estas propiedades, lo denotaremos h = mcd( f1, . . . , fs).
A continuación, se muestran las principales propiedades de este máximo común divisor.
4 Capítulo 1. Conceptos y fundamentos previos
Proposición 1.3. Sean f1, . . . , fs ∈ K[x], con s ≥ 2. Entonces:
i) mcd( f1, . . . , fs) existe y es único salvo una constante multiplicativa no nula en K.
ii) mcd( f1, . . . , fs) es un generador del ideal 〈 f1, . . . , fs〉.
iii) Si s ≥ 3, entonces mcd( f1, . . . , fs) = mcd( f1,mcd( f2, . . . , fs)).
iv) Existe un algoritmo para calcular mcd( f1, . . . , fs).
Veamos cómo funciona tal algoritmo presentado en forma de pseudocódigo.
• Para s= 2. Tomamos como variables de entrada los polinomios f1 y f2 y obtenemos como variable
de salida h = mcd( f1, f2).
• Para s ≥ 3. Tomamos como variables de entrada los polinomios f1, . . . , fs y llamamos polin a
la lista formada por dichos polinomios. Para calcular el máximo común divisor, denotado en el
pseudocódigo mediante m, hay que crear una función que llame al algoritmo de Euclides para dos
polinomios, explicado justo antes.
Problema: Problema de pertenencia al ideal en K[x].
Dados los polinomios f1, . . . , fs ∈ K[x], ¿existe un algoritmo para saber si un polinomio cualquiera
f ∈ K[x] pertenece al ideal 〈 f1, . . . , fs〉?
Solución:
Efectivamente existe un algoritmo para resolver este problema. Consiste en:
- Usar el algoritmo de Euclides para hallar el máximo común divisor de f1, . . . , fs, denotado por h.
Por la propiedad (ii) de la Proposición 1.3, h genera el ideal 〈 f1, . . . , fs〉.
- Por tanto, f ∈ 〈 f1, . . . , fs〉 equivale a decir que f ∈ 〈h〉. Así que tenemos que usar el algoritmo de
la división para poder escribir f = qh+ r con grado(r)< grado(h).
- Entonces f pertenecerá al ideal si y solo si r = 0.
Entre otras cosas, en el siguiente capítulo resolveremos este mismo problema pero para polinomios
definidos en varias variables, es decir f1, . . . , fs ∈ K[x1, . . . ,xn], utilizando una extrategia similar: en-
contraremos una buena base del ideal, que será concretamente una base de Gröbner, y utilizaremos el
algoritmo de la división para determinar si un polinomio está en el ideal.
Capítulo 2
Bases de Gröbner
En este capítulo estudiaremos una generalización del algoritmo de la división en varias variables.
También estudiaremos las bases de Gröbner e importantes resultados que nos ayudarán a encontrar
dichas bases, las cuales nos permitirán resolver problemas sobre ideales de polinomios y variedades.
Más concretamente, nos centraremos en estudiar y resolver estas cuatro cuestiones:
1. Problema de la descripción del ideal:
¿Los ideales I ⊆ K[x1, . . . ,xn] están formados por un conjunto finito de polinomios? O en otras
palabras, ¿podemos escribir I = 〈 f1, . . . , fs〉 para fi ∈ K[x1, . . . ,xn]?
2. Problema de pertenencia al ideal:
Dado un polinomio f ∈ K[x1, . . . ,xn] consiste en decidir si f ∈ I = 〈 f1, . . . , fs〉.
3. Problema de resolución de un sistema de ecuaciones:
Consiste en encontrar todas las soluciones en Kn del sistema de ecuaciones polinómicas
f1(x1, . . . ,xn) = · · ·= fs(x1, . . . ,xn) = 0.
4. Problema de implicitación en ideales:
Queremos encontrar un sistema de ecuaciones (en x1, . . . ,xn) cuyas soluciones son los puntos de
la variedad V ⊆Kn dada por las ecuaciones paramétricas x1 = f1(t1, . . . , tm), . . . ,xn = fn(t1, . . . , tm)
donde fi son polinomios o funciones racionales en las variables t j.
2.1. Orden monomial en varias variables
En esta sección vamos a estudiar las propiedades necesarias para ser capaces de ordenar (ascen-
dente, o descendentemente) los términos de un polinomio en varias variables inequívocamente. Los
conceptos explicados a continuación nos serán útiles cuando expliquemos el algoritmo de la división en
K[x1, . . . ,xn].
Para la siguiente definición nos será de utilidad recordar que un conjunto posee orden total si dados
tres elementos a,b,c se cumple la propiedad reflexiva, transitiva, antisimétrica y la de totalidad (b≤ a,
o a≤ b).
Definición 11. Un orden monomial sobre K[x1, . . . ,xn] es cualquier relación > en Zn
≥0, o equivalente-
mente cualquier relación en el conjunto de monomios xα ,α ∈ Zn
≥0 satisfaciendo:
i) > es un orden total (o lineal) en Zn
≥0.
ii) Si α > β , γ ∈ Zn
≥0 entonces α + γ > β + γ . Esto es equivalente a decir que si xα > xβ y xγ es
cualquier monomio entonces se cumple xαxγ > xβ xγ .
5
6 Capítulo 2. Bases de Gröbner
iii) > es un buen orden en Zn
≥0. Esto significa que si A⊆ Zn
≥0 es no vacío, entonces existe α ∈ A tal
que β > α para todo β 6= α en A.
El siguiente lema nos ayudará a entender mejor qué significa la condición iii). Además, lo usaremos
para justificar que algunos algoritmos deben terminar en un número finito de pasos.
Lema 2.1. Una relación de orden > en Zn
≥0 se dice que es un buen orden si y solo si toda secuencia
estrictamente decreciente en Zn
≥0 termina.
Existe una gran variedad de órdenes monomiales. Veamos cómo se definen tres de ellos aunque
el que nosotros utilizaremos para todo lo explicado posteriormente será el orden lexicográfico, el cual
explicamos a continuación.
Definición 12. Sean α = (α1, . . . ,αn), β = (β1, . . . ,βn) ∈ Zn
≥0 . Diremos que α posee un orden lexi-
cográfico respecto a β (lo denotaremos mediante α >lex β ) si en la diferencia α −β ∈ Zn la primera
componente de más a la izquierda, no nula, es positiva. Si esto se cumple, escribiremos xα >lex xβ .
Con esta definición de orden lexicográfico estamos ordenando los términos de un polinomio tenien-
do en cuenta los monomios de mayor grado. Sin embargo, puede darse el caso de querer ordenar dichos
términos utilizando el grado total de los monomios. Es por ello por lo que definimos el siguiente orden
monomial.
Definición 13. Sean α = (α1, . . . ,αn), β = (β1, . . . ,βn) ∈ Zn
≥0 . Diremos que α posee un orden lexico-
gráfico graduado respecto a β (lo denotaremos mediante α >grlex β ) si
|α|=
n
∑
i=1
αi > |β |=
n
∑
i=1
βi, o |α|= |β | y α >lex β .
Otra forma de ordenar los monomios es utilizar el orden lexicográfico graduado inverso, el cual es
menos intuitivo pero es el más eficiente computacionalmente hablando.
Definición 14. Sean α = (α1, . . . ,αn), β = (β1, . . . ,βn) ∈ Zn
≥0 . Diremos que α posee un orden lexico-
gráfico graduado inverso respecto a β (lo denotaremos mediante α >grvlex β ) si
|α|=
n
∑
i=1
αi > |β |=
n
∑
i=1
βi, o |α|= |β |
y en la diferencia α−β ∈ Zn la primera componente de más a la derecha, no nula, es negativa.
Ejemplo 3. Sea f (x,y,z) = 3x3 − 3y2 + 4x2z4 + z6. Vamos a reescribir el polinomio ordenando sus
términos, dependiendo del orden monomial usado con x > y > z.
Orden lexicográfico. El término mayor es aquel cuya primera componente de más a la izquierda
(al restar los vectores), no nula, sea positiva. Para ello, escribimos cada término de f como un
vector de tres componentes donde cada una de ellas corresponde al exponente de la variable x,y,z
respectivamente:
x3→ (3,0,0) y2→ (0,2,0) x2z4→ (2,0,4) z6→ (0,0,6)
Así que f (x,y,z) = 3x3 +4x2z4−3y2 + z6.
Orden lexicográfico graduado. El término mayor es aquel cuyo grado total es mayor, y si dos
términos poseen el mismo grado entonces se utilizará el orden lexicográfico para ordenarlos.
Entonces:
grado(x3) = 3 grado(y2) = 2 grado(x2z4) = 6 grado(z6) = 6
Además (2,0,4) >lex (0,0,6) (hay que mirar el orden lexicográfico deesos dos términos ya que
tienen el mismo grado). Así que f (x,y,z) = 4x2z4 + z6 +3x3−3y2.
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 7
Orden lexicográfico graduado inverso. El término mayor es aquel cuyo grado es mayor, y si dos
términos poseen el mismo grado entonces será mayor aquel que tenga la componente de más a la
derecha (al restar los vectores), no nula y negativa. Entonces:
grado(x3) = 3 grado(y2) = 2 grado(x2z4) = 6 grado(z6) = 6
Además (2,0,4)− (0,0,6) = (2,0,−2) y vemos que la componente de más a la derecha no nula
es negativa (hay que hacer la diferencia de esos dos ya que tienen el mismo grado) de modo que
(2,0,4)>grvlex (0,0,6). Así que f (x,y,z) = 4x2z4 + z6 +3x3−3y2.
Usaremos la siguiente terminología.
Definición 15. Sea f = ∑
α
aαxα un polinomio no nulo en K[x1, . . . ,xn] y sea > un orden monomial.
i) El multigrado de f obedece a la siguiente fórmula: multigrado( f ) = max(α ∈ Zn
≥0 |aα 6= 0).
ii) El coeficiente principal de f es el coeficiente correspondiente al monomio xmultigrado( f ). Lo deno-
taremos mediante LC( f ).
iii) El monomio principal de f es el monomio que es igual a xmultigrado( f ). Lo denotaremos mediante
LM( f ).
iv) El término principal de f se denota mediante LT ( f ) = LC( f ) ·LM( f ).
Ejemplo 4. Retomando el Ejemplo 3:
Aplicando el orden lexicográfico habíamos obtenido f (x,y,z) = 3x3+4x2z4−3y2+z6. Entonces:
multigrado( f ) = (3,0,0) y LT ( f ) = 3 · x3 = 3x3.
Aplicando tanto el orden lexicográfico graduado como el orden lexicográfico graduado inver-
so habíamos obtenido f (x,y,z) = 4x2z4 + z6 + 3x3− 3y2. Entonces: multigrado( f ) = (2,0,4) y
LT ( f ) = 4 · x2z4 = 4x2z4.
2.2. El algoritmo de la división en varias variables
En esta sección formularemos un algoritmo de la división en K[x1, . . . ,xn] extendiendo el algoritmo
de la división en una variable, estudiado en la Proposición 1.2, pero con una pequeña diferencia ya que
ahora el resto no quedará determinado de forma única.
Teorema 2.2 (El algoritmo de la división en K[x1, . . . ,xn]). Sea > un orden monomial en Zn
≥0 y sea
f = ( f1, . . . , fs) una s-tupla ordenada de polinomios en K[x1, . . . ,xn]. Entonces todo polinomio f ∈
K[x1, . . . ,xn] se puede escribir como
f = q1 f1 + · · ·+qs fs + r
donde qi,r ∈ K[x1, . . . ,xn] y el resto verifica r = 0 o r es una combinación lineal de monomios con
coeficientes en K tal que ninguno de ellos es divisible por ningún término principal LT ( f1), . . . ,LT ( fs).
Tomamos como variables de entrada f1, . . . , fs, f y como variables de salida q1, . . . ,qs,r. A conti-
nuación, se muestra un algoritmo presentado en forma de pseudocódigo para hallar tales q1, . . . ,qs,r.
8 Capítulo 2. Bases de Gröbner
Ejemplo 5. Veamos un ejemplo de cómo funciona este algoritmo en Q[x,y]. Queremos dividir el po-
linomio f (x,y) = x3y+ x2 + 2xy2 + xy+ x+ y entre f1(x,y) = x2y+ 1 y f2(x,y) = xy usando el orden
lexicográfico x > y.
Para comenzar, consideramos q1 = 0,q2 = 0,r = 0, p = f .
Como LT ( f1) = x2y divide a LT (p) = x3y entonces podemos actualizar los valores de q1 y p
obteniendo q1 = x, y p = x2 +2xy2 + xy+ y.
Sin embargo ahora, LT (p) = x2 no es dividido por LT ( f1) = x2y ni por LT ( f2) = xy. Entonces el
algoritmo nos indica que x2 pasa a formar parte del resto de la división. Actualizando, obtenemos
r = x2, y p = 2xy2 + xy+ y.
Ahora, LT ( f2) = xy sí divide a LT (p) = 2xy2 y obtenemos los siguientes valores actualizados:
q2 = 2y, y p = xy+ y.
Como LT ( f2) = xy divide a LT (p) = xy entonces actualizando tenemos q2 = 2y+1, y p = y.
Para finalizar, vemos que ni LT ( f1) = x2y ni LT ( f2) = xy divide a LT (p) = y de modo que y es
parte del resto y así r = x2 + y. En este caso tenemos p = 0, luego hemos terminado la división y
el algoritmo finaliza.
Recopilando todo, tenemos:
x3y+ x2 +2xy2 + xy+ x+ y = (x)(x2y+1)+(2y+1)(xy)+(x2 + y).
Llegados a este punto podemos preguntarnos si los cocientes y el resto obtenidos pueden variar
dependiendo del cuerpo de polinomios en el que trabajemos. Veamos con el siguiente ejemplo que
efectivamente, el cuerpo es importante.
Ejemplo 6. Tomamos los polinomios f , f1, f2 del Ejemplo 5 con la diferencia de que ahora todos ellos
están en el cuerpo finito Z3[x,y]. Al aplicar el algoritmo de la división y dividir f entre f1 y f2 usando
el orden lexicográfico x > y se obtiene:
x3y+ x2 +2xy2 + xy+ x+ y = (x)(x2y+1)+(−y+1)(xy)+(x2 + y).
También podemos obtener distintos cocientes q1, . . . ,qs y distinto resto r dependiendo de cómo están
ordenados los divisores f1, . . . , fs. De modo que el Ejemplo 5 nos ayuda a entender porqué el algorit-
mo de la división en K[x1, . . . ,xn] necesita que f = ( f1, . . . , fs) sea una s-tupla ordenada de polinomios
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 9
usando un orden monomial y también nos ilustra que el resto no está determinado de manera única: Si
dividimos f entre [ f1, f2] obtenemos q1 = x,q2 = 2y+ 1,r = x2 + y (ver Ejemplo 5), mientras que si
dividimos f entre [ f2, f1] obtenemos q1 = x2 +2y+1,q2 = 0,r = x2 + x+ y.
Recalcar también que el algoritmo de la división depende fuertemente de la elección del orden mo-
nomial, es decir, los cocientes y el resto pueden variar dependiendo del orden monomial elegido.
Vimos en el primer capítulo, al final de la Sección 1.4, que una de las caraterísticas del algoritmo de
la división en K[x] es resolver el problema de pertenencia al ideal, obteniendo entonces que la condición
r = 0 era una condición suficiente y necesaria para concluir que f ∈ 〈 f1, . . . , fs〉.
Ahora nos encontramos en la siguiente situación,
Problema: Problema de pertenencia al ideal en K[x1, . . . ,xn].
Como hemos visto anteriormente, dado un polinomio f ∈ K[x1, . . . ,xn], consiste en decidir si
f ∈ I = 〈 f1, . . . , fs〉.
¿Se puede hacer algo parecido al caso en una variable? ¿Existe algún algoritmo para resolverlo?
Solución:
Todavía no podemos resolverlo, ya que ahora la condición r = 0 es una condición suficiente pero no ne-
cesaria para afirmar que f ∈ 〈 f1, . . . , fs〉. Para solucionar este problema queremos encontrar un conjunto
generador del ideal, en el que el resto se determine de forma única y en el que la condición r = 0 sea
equivalente a pertenecer al ideal. Este conjunto será el que, posteriormente, llamaremos base de Gröb-
ner. Para llegar hasta allí, necesitamos introducir previamente los conceptos y resultados de la siguiente
sección.
2.3. Ideales monomiales
Definición 16. Un ideal I ⊆ K[x1, . . . ,xn] se dice ideal monomial si existe un subconjunto A ⊆ Zn
≥0
tal que I está formado por todos los polinomios de la forma ∑
α∈A
hαxα donde hα ∈ K[x1, . . . ,xn]. Lo
denotaremos I = 〈xα |α ∈ A〉.
Es decir, un ideal monomial se puede generar por monomios pero esto no quiere decir que todos los
elementos del ideal sean monomios. Veamos un ejemplo de ideal que es monomial, y otro que no.
Ejemplo 7. I = 〈xy+ y2,yx− y2〉 es un ideal monomial y sin embargo I′ = 〈xy+ y2,x− y〉 no lo es. En
efecto:
Llamamos f1 = xy+ y2 y f2 = yx− y2. Entonces
1
2
( f1 + f2) = xy ∈ I y
1
2
( f1− f2) = y2 ∈ I.
Luego podemos escribir 〈xy+ y2,yx− y2〉 = 〈xy,y2〉. De modo que I es un ideal generado por
monomios, así que I es un ideal monomial.
Llamamos f1 = xy+ y2 y f2 = x− y. Entonces y f2 + f1 = 2xy ∈ I y y f2− f1 = 2y2 ∈ I.
Luego podemos escribir 〈xy+ y2,x− y〉 = 〈xy,y2,x− y〉 y ver así que I′ no se puede generar por
monomios. Luego I′ no es un ideal monomial.
Lema 2.3. Sea I = 〈xα |α ∈ A〉 un ideal monomial. Entonces un monomio xβ pertenece a I si y solo si
xβ es divisible por xα para algún α ∈ A.
Lema 2.4. Sea I un ideal monomial y sea f ∈ K[x1, . . . ,xn]. Entonces las siguientes afirmaciones son
equivalentes:
i) f ∈ I.
10 Capítulo 2. Bases de Gröbner
ii) Todo término de f está en I.
iii) f es una combinación lineal en el cuerpo K de monomios de I.
Colorario 2.5. Dos ideales monomiales son iguales si y solo si contienen los mismos monomios.
A continuación, se enuncia y demuestra el Lemade Dickson ya que tendrá gran importancia en
resultados teóricos posteriores.
Teorema 2.6 (Lema de Dickson). Todo ideal monomial I = 〈xα |α ∈ A〉 se puede escribir como I =
〈xα(1), . . . ,xα(s)〉, donde los enteros α(i) ∈ A, ∀i = 1, . . . ,s. En particular, I tiene una base finita.
Demostración. Procedamos por inducción sobre el número de variables, n.
◦ Sea n = 1. Entonces I está finitamente generado en K[x1] por los monomios xα
1 , donde α ∈ A ⊆
Z≥0. Esto es porque tomando β ≤ α como el menor elemento de A entonces xβ
1 divide a todo xα
1
y así, por el Lema 2.3, I = 〈xβ
1 〉.
◦ Supongamos que es cierto para n− 1 (con n > 1) y veamos si se cumple el resultado para n.
Asumimos la siguiente notación: escribiremos las variables como x1, . . . ,xn−1,y de modo que los
monomios en K[x1, . . . ,xn−1,y] se escribirán como xαym con α ∈ Zn−1
≥0 , m ∈ Z≥0.
Supongamos que I ⊆ K[x1, . . . ,xn−1,y] es un ideal monomial. Para encontrar los generadores de
I, definimos J ⊆ K[x1, . . . ,xn−1] como un ideal generado por los monomios xα tales que xαym ∈ I
para algún m≥ 0. Es decir,
J = 〈xα ∈ K[x1, . . . ,xn−1] |xαym ∈ I,m≥ 0〉.
Por ser J un ideal monomial en K[x1, . . . ,xn−1], aplicando la hipótesis de inducción existirá un
número finito de generadores de modo que tenemos J = 〈xα(1), . . . ,xα(s)〉, con α(i) ∈ A.
Para cada 1 ≤ i ≤ s, por definición de J, se cumple xα(i)ymi ∈ I para algún mi ≥ 0. Sea m el
máximo de los mi. Entonces para cada 0≤ k≤m−1 consideramos Jk ⊆ K[x1, . . . ,xn−1] como un
ideal generado por los monomios xβ tales que xβ yk ∈ I. Es decir,
Jk = 〈xβ ∈ K[x1, . . . ,xn−1] |xβ yk ∈ I,0≤ k ≤ m−1〉.
Aplicando de nuevo la hipótesis de inducción tenemos Jk = 〈xαk(1), . . . ,xαk(sk)〉, o equivalentemen-
te, Jk está generado por un número finito de monomios.
Veamos que I está generado por los siguientes monomios:
procedentes de J : xα(1)ym, . . . ,xα(s)ym
procedentes de J0 : xα0(1), . . . ,xα0(s0)
procedentes de J1 : xα1(1)y, . . . ,xα1(s1)y
...
procedentes de Jm−1 : xαm−1(1)ym−1, . . . ,xαm−1(sm−1)ym−1.
Tenemos que cada monomio de I es divisible por alguno de la lista anterior. En efecto, tomamos
xαyp ∈ I :
- Si p≥ m entonces xαyp es divisible por algún xα(i)ym debido a la construcción de J.
- Si p≤ m−1 entonces xαyp es divisible por algún xαp( j)yp debido a la construcción de Jp.
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 11
Así que por el Lema 2.3 tenemos que la lista anterior de monomios genera un ideal con los mismos
monomios que I, y por el Corolario 2.5 se tiene que ambos ideales son el mismo.
Por último, veamos que el conjunto finito de generadores se puede escoger de los generadores del
ideal. Denotando ahora las variables como x1, . . . ,xn, entonces I = 〈xα |α ∈ A〉 es nuestro ideal
monomial. Queremos ver que I está generado por un número finito de xα ’s, con α ∈ A. Hemos
visto que I = 〈xβ (1), . . . ,xβ (s)〉 para ciertos monomios xβ (i) ∈ I, i = 1, . . . ,s. Como xβ (i) ∈ I, por
el Lema 2.3 se tiene que cada xβ (i) es divisible por xα(i),α(i) ∈ A. Por doble contenido se ve
fácilmente que I = 〈xα(1), . . . ,xα(s)〉 completando así la demostración.
Una de las consecuencias del Lema de Dickson es que dadas las dos primeras condiciones de la
Definición 11, la condición iii) tiene un equivalente. Veámoslo:
Colorario 2.7. Sea > una relación de orden en Zn
≥0 cumpliendo:
i) > es un orden total en Zn
≥0.
ii) Si α > β , γ ∈ Zn
≥0 entonces α + γ > β + γ .
Entonces > es un buen orden si y solo si α ≥ 0 para todo α ∈ Zn
≥0.
2.4. El Teorema de las bases de Hilbert y bases de Gröbner
En esta sección se darán resultados teóricos los cuales servirán para dar una solución al problema de
la descripción del ideal explicado al principio de este capítulo. La idea principal es que dado un orden
monomial, todo polinomio no nulo tiene un único término principal. Entonces para cualquier ideal I
podemos definir su ideal de términos principales de la siguiente manera.
Definición 17. Sea I ⊆ K[x1, . . . ,xn] un ideal distinto del nulo. Entonces, una vez fijado un orden mo-
nomial en K[x1, . . . ,xn]:
i) Denotaremos mediante LT (I) al conjunto de todos los términos principales de todos los elementos
de I que sean no nulos. Es decir,
LT (I) = {cxα |existe f ∈ I \{0} tal que LT ( f ) = cxα}.
ii) Denotaremos mediante 〈LT (I)〉 al ideal generado por los elementos del conjunto LT (I).
Proposición 2.8. Sea I ⊆ K[x1, . . . ,xn] un ideal distinto del nulo, entonces
i) 〈LT (I)〉 es un ideal monomial.
ii) Existen g1, . . . ,gt ∈ I tales que se cumple la igualdad 〈LT (I)〉= 〈LT (g1), . . . ,LT (gt)〉.
Para probar el siguiente resultado, haremos uso de la Proposición 2.8 y del Teorema 2.2 (algoritmo
de la división), dando así una respuesta afirmativa al problema de la descripción del ideal explicado al
principio de este capítulo.
Teorema 2.9 (Teorema de las bases de Hilbert). Todo ideal I ⊆ K[x1, . . . ,xn] está finitamente generado.
En otras palabras, I = 〈g1, . . . ,gt〉 con g1, . . . ,gt ∈ I.
Demostración. Hola
◦ Si I = {0}, como {0} es un generador de I y es un conjunto finito entonces se tiene el resultado.
12 Capítulo 2. Bases de Gröbner
◦ Si I 6= {0}, entonces un conjunto generador g1, . . . ,gt de I se puede construir de la siguiente
manera:
Como I tiene un ideal de términos principales, por la Proposición 2.8 existen g1, . . . ,gt ∈ I tales
que 〈LT (I)〉 = 〈LT (g1), . . . ,LT (gt)〉. Comprobemos ahora que, efectivamente, I = 〈g1, . . . ,gt〉.
Para ello, procedamos por doble contenido:
- Dado que todo gi ∈ I, es claro que 〈g1, . . . ,gt〉 ⊆ I.
- Sea f ∈ I un polinomio cualquiera. Fijado un orden monomial, se aplica el algoritmo de la
división en varias variables para dividir f por [g1, . . . ,gt ] y obtenemos
f = q1g1 + · · ·+qtgt + r
donde ningún término de r es divisible por ningún LT (gi), i = 1, . . . , t. Veamos que r = 0.
Para ello procedamos por reducción al absurdo suponiendo r 6= 0 . En tal caso LT (r) ∈
〈LT (I)〉 = 〈LT (g1), . . . ,LT (gt)〉 (ya que r = f − q1g1− ·· · − qtgt ∈ I) y por el Lema 2.3
se tiene que LT (r) debe ser divisible por algún LT (gi), i = 1, . . . , t. Como esto contradice
la afirmación anterior de que ningún término de r es divisible por ningún LT (gi), se tiene
r = 0. Por lo tanto f = q1g1 + · · ·+qtgt +0 ∈ 〈g1, . . . ,gt〉, completando así la demostración
del segundo contenido I ⊆ 〈g1, . . . ,gt〉.
Luego, por doble contenido, I = 〈g1, . . . ,gt〉.
Definición 18. Dado un orden monomial, un subconjunto finito G = {g1, . . . ,gt} de un ideal I ⊆
K[x1, . . . ,xn] se dirá base de Gröbner si
〈LT (g1), . . . ,LT (gt)〉= 〈LT (I)〉.
De una manera menos formal, un conjunto {g1, . . . ,gt} ⊆ I es una base de Gröbner de I si y solo si el
término principal de cada elemento de I es divisible por alguno de los LT (gi), para i = 1, . . . , t.
Hola
Por convenio se tiene 〈 /0〉 = {0}. Definimos entonces el conjunto vacío /0 como la base de Gröbner del
ideal nulo {0}.
Colorario 2.10. Dado un orden monomial, todo ideal I ⊆ K[x1, . . . ,xn] tiene una base de Gröbner. Es
más, cualquier base de Gröbner de un ideal I es una base de I.
Veamos una consecuencia geométrica del Teorema 2.9 bastante importante, ya que luego nos per-
mitirá resolver sistemas de ecuaciones en varias variables de una forma sencilla.
Definición 19. Sea I ⊆ K[x1, . . . ,xn] un ideal. Denotaremos mediante V(I) al conjunto
V(I) = {(a1, . . . ,an) ∈ Kn | f (a1, . . . ,an) = 0, ∀ f ∈ I)}.
Proposición 2.11. El conjunto V(I) es una variedad afín. En particular, si I = 〈 f1, . . . , fs〉, entonces
V(I) = V( f1, . . . , fs).
A continuación, veamos que, al aplicar el algoritmo de la división en varias variables, el resto de la
división es único cuando los divisores forman una base de Gröbner.
Proposición 2.12. Fijado un orden monomial, sea G = {g1, . . . ,gt} una base de Gröbner del ideal
I ⊆ K[x1, . . . ,xn] y sea f ∈ K[x1, . . . ,xn]. Entonces existe un resto único r ∈ K[x1, . . . ,xn] que cumple las
dos siguientes propiedades:
i) Ningún término de r es divisible por LT (gi), para i = 1,. . . , t.
ii) Existe g ∈ I tal que f = g+ r.
En particular, r es el resto de la división de f entre G sin importar el orden de los elementos de G.
Colorario 2.13. Sea G = {g1, . . . ,gt} una base de Gröbner del ideal I ⊆ K[x1, . . . ,xn] y sea f ∈
K[x1, . . . ,xn]. Entonces f ∈ I si y solo si el resto de la división de f entre G es cero.
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 13
2.5. Criterio y algoritmo de Buchberger
A partir de ahora escribiremos f̄ F para denotar el resto de la división del polinomio f entre la s-tupla
ordenada F = ( f1, . . . , fs). Si F es una base de Gröbner para el ideal 〈 f1, . . . , fs〉 entonces la s-tupla F
no es necesario que esté ordenada.
Ejemplo 8. Dividiendo f = x4y2 por F = (xy− 1,y2− 1) ⊆ K[x,y], utilizando el orden lexicográfico
(x > y), obtenemos
x4y2F
= x2
ya que mediante el algoritmo de la división se tiene
x4y2 = (x3y+ x2) · (xy−1)+(0) · (y2−1)+ x2.
A continuación, veremos el criterio de Buchberger, el cual nos ayudará a saber si el generador de un
ideal dado es una base Gröbner o no. Para ello necesitamos introducir previamente dos definiciones.
Definición 20. Sean f ,g∈K[x1, . . . ,xn] polinomios no nulos. Si multigrado( f ) = α y multigrado(g) =
β , sea γ = (γ1, . . . ,γn) donde γi = max(αi,βi) para cada i = 1, . . . ,n. Llamaremos xγ al mínimo común
múltiplo de LM( f ) y LM(g), es decir, xγ = mcm(LM( f ),LM(g)).
Definición 21. Sean f ,g ∈ K[x1, . . . ,xn] polinomios no nulos. Definimos el S-polinomio de f y g como
S( f ,g) =
xγ
LT ( f )
· f − xγ
LT (g)
·g.
Ahora ya sí podemos enunciar el siguiente resultado, el cual como ya hemos explicado, sirve para
saber cuándo una base de un ideal es una base de Gröbner.
Teorema 2.14 (Criterio de Buchberger). Sea I un ideal de polinomios. Entonces una base G= {g1, . . . ,gt}
de I es una base de Gröbner de I ⇔ S(gi,g j)
G
= 0, ∀i, j tales que i 6= j.
Demostración. Ver [5, Capítulo 2, Sección 6].
Ejemplo 9. Sea I = 〈x2− y2 + z,z− 1〉. Veamos que G = {x2− y2 + z,z− 1} es una base de Gröbner
para I utilizando el orden lexicográfico habitual (x > y > z).
Denotamos g1 = x2−y2+ z y también g2 = z−1. Entonces LT (g1) = x2, LT (g2) = z y xγ = x2z (ya que
multigrado(g1) = (2,0,0) y multigrado(g2) = (0,0,1)). De este modo
S(g1,g2) =
x2z
x2 ·g1−
x2z
z
·g2 = x2− y2z+ z2.
Ahora, aplicando el algoritmo de la división obtenemos
x2− y2z+ z2 = (1)(−x2− y2 + z)+(−y2 + z)(z−1)+0.
Por lo tanto
S(g1,g2)
G
= 0.
Así que por el criterio de Buchberger se tiene que G es una base de Gröbner para I.
Ya hemos visto en el Corolario 2.10 que todo ideal tiene una base de Gröbner. Además, gracias
al Teorema 2.14 (criterio de Buchberger) ya sabemos ver si una base dada es una base de Gröbner o
no. Pero dado un ideal I ⊆ K[x1, . . . ,xn], ¿podemos construir nosotros una base de Gröbner para I? La
respuesta a esto es que sí. Para ello utilizaremos el siguiente algoritmo.
Teorema 2.15 (Algoritmo de Buchberger). Sea I = 〈 f1, . . . , fs〉 6= {0} un ideal de polinomios. Entonces
podemos construir una base de Gröbner G = {g1, . . . ,gt} de I en un número finito de pasos utilizando
el siguiente algoritmo:
14 Capítulo 2. Bases de Gröbner
Por lo tanto, usando el criterio de Buchberger y el algoritmo de Buchberger hemos conseguido un
método para obtener bases de Gröbner. Pero estas bases, habitualmente tienen más elementos de los
necesarios. Veamos que podemos eliminar alguno utilizando el siguiente lema.
Lema 2.16. Sea G una base de Gröbner de I ⊆ K[x1, . . . ,xn] y sea p ∈G un polinomio tal que LT (p) ∈
〈LT (G\{p})〉. Entonces G\{p} es también una base de Gröbner de I.
Ejemplo 10. Consideramos el anillo de polinomios Q[x,y,z] con el orden lexicográfico habitual
(x > y > z) y sea I = 〈 f1, f2〉= 〈x2 + y,x3 + z〉.
Lo primero es ver que F = { f1, f2} no es una base de Gröbner:
Como LT (S( f1, f2)) = xy /∈ 〈LT ( f1),LT ( f2)〉 = 〈x2,x3〉, entonces el criterio de Buchberger nos garan-
tiza que F no es una base de Gröbner de I.
Vamos a construir una base de Gröbner, a partir de F , utilizando el algoritmo de Buchberger.
Iniciamos el algoritmo y así G′ = F . Ahora, dividiendo S( f1, f2) = xy− z por F obtenemos como resto
f3 = xy− z, el cual es no nulo. Por lo tanto debemos actualizar nuestra base G′ = { f1, f2, f3}. Entonces,
S( f1, f2)
G′
= S( f2, f3)
G′
= 0,
S( f1, f3)
G′
= xz+ y2 6= 0.
Por lo tanto, añadiendo f4 = xz+ y2, G′ = { f1, f2, f3, f4} . Ahora,
S( f1, f2)
G′
= S( f1, f3)
G′
= S( f1, f4)
G′
= S( f2, f3)
G′
= 0,
S( f3, f4)
G′
=−y3− z2 6= 0.
Así que tenemos una nueva G′ = { f1, f2, f3, f4, f5}, siendo f5 =−y3− z2, para la cual se cumple
S( fi, f j)
G′
= 0, ∀ 1≤ i < j ≤ 5.
Así, por el criterio de Buchberger tenemos que G = { f1, f2, f3, f4, f5} es una base de Gröbner de I con
respecto al orden lexicográfico.
Notar ahora que LT ( f2) = x ·LT ( f1). Así que por el Lema 2.16 podemos prescindir de f2 en nuestra
nueva base de Gröbner. Como no hay más casos en los que el término principal de un generador divida
al término principal de otro generador, entonces la mínima base de Gröbner que podemos obtener es:
G = { f1, f3, f4, f5}.
Definición 22. Una base de Gröbner minimal de un ideal de polinomios I ⊆ K[x1, . . . ,xn] es una base
de Gröbner G de I la cual cumple:
i) ∀p ∈ G, LC(p) = 1.
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 15
ii) ∀p ∈ G, LT (p) /∈ 〈LT (G\{p})〉.
Desafortunadamente el ideal I inicial puede tener varias bases de Gröbner minimales, ya que por
ejemplo tomando f̃1 = x2 + y+ az con a ∈ Q también sería G = { f̃1, f3, f4, f5} una base de Gröbner
minimal. Pero afortunadamente hay una base minimal que es mejor que el resto. Su definición es la
siguiente.
Definición 23. Una base de Gröbner reducida de un ideal de polinomios I ⊆ K[x1, . . . ,xn] es una base
de Gröbner G de I la cual cumple:
i) ∀p ∈ G, LC(p) = 1.
ii) ∀p ∈ G, ningún monomio de p está en 〈LT (G\{p})〉.
Teorema 2.17. Sea I un ideal de polinomios no nulo. Entonces, para un orden monomial dado, I tiene
una única base de Gröbner reducida.
Demostración. Introduzcamos la siguiente definición: Diremos que g ∈G, G base de Gröbner minimal
de I, es un elemento reducido respecto de G si ningún monomio de g pertenece a 〈LT (G)\{p}〉 con
p ∈ G. Notar que si g es un elemento reducido respecto de G entonces g también es reducido respecto
cualquier otra base de Gröbner minimal de I que contenga a g y que tenga los mismos términos princi-
pales.
El objetivo para ver la existencia de una base de Gröbner reducida es partir de una base de Gröbner
minimal G y modificarla hasta que todos sus elementos sean elementos reducidos.
Dado g ∈G un elemento reducido respecto de G, tomamos g′ = gG\{g} y G′ = (G\{g})∪{g′}. Vea-
mos que G′ es una base de Gröbner minimal de I. Para ello notar que LT (g′) = LT (g) ya que al dividir
g entre G\{g}, necesariamente LT (g) pasa a formar parte del resto porque no es divisible por ningún
elemento de LT (G\{g}). Así tenemos que 〈LT (g′)〉= 〈LT (g)〉. Como claramente G′ ⊆ I tenemos que
G′ es una base de Gröbner minimal de I. Además, g′ es un elemento reducido de G′ por construcción.
Ahora tomamos los elementos de G y aplicamos el procedimiento anterior hasta que todo elemento sea
reducido, obteniendo así una base de Gröbner reducida.
Queda por probar la unicidad de esta base de Gröbner reducida, la cual acabamos de ver que existe.
Sean G y G̃ dos bases de Gröbner reducidas de I. En particular G y G̃ son también bases de Gröbner mi-
nimales de I, luego LT (G) = LT (G̃). Entonces dado g∈G, existirá un g̃∈ G̃ tal que LT (g) = LT (g̃). Así
que si probamos g = g̃ entonces G = G̃ y la unicidad estará probada. Para ver que g = g̃, consideremos
el polinomio g− g̃, el cual está en I. Como G es una base de Gröbner se sigue que g− g̃G
= 0. También,
como LT (g) = LT (g̃) entonces ambos se cancelan al efectuar la resta g− g̃ y el resto de términos no son
divisibles por ninguno de los LT (g) = LT (g̃) ya que G y G̃ son bases de Gröbner reducidas. Se sigue
que g− g̃G
= g− g̃ y porlo anterior g− g̃ = 0, luego g = g̃ completando así la demostración.
El siguiente resultado, a pesar de estar categorizado como corolario tendrá gran relevancia en los
dos capítulos posteriores. Tener en cuenta que un cuerpo K se dice algebraicamente cerrado si cada
polinomio de grado al menos 1, con coeficientes en K, tiene un cero en K.
Colorario 2.18. Sea K un cuerpo algebraicamente cerrado. Dado un ideal I ⊆ K[x1, . . . ,xn] y dada G
una base de Gröbner reducida de I entonces V(I) = /0 si y solo si G = {1}.
2.6. Aplicaciones de las bases de Gröbner
En esta sección vamos a resolver, utilizando las bases de Gröbner, los problemas sobre ideales y
variedades enumerados y brevemente explicados al principio de este segundo capítulo.
16 Capítulo 2. Bases de Gröbner
1. Problema de la descripción del ideal.
Ya se explicó que este problema consiste en saber si los ideales I ⊆ K[x1, . . . ,xn] están formados
por un conjunto finito. Lo resolvimos utilizando el Teorema 2.9, ya que este resultado afirma que
todo ideal está finitamente generado.
2. Problema de pertenencia al ideal.
Dado un ideal I = 〈 f1, . . . , fs〉 ⊆ K[x1, . . . ,xn] podemos saber si un polinomo f pertenece a I de la
siguiente manera:
- Encontrar una base de Gröbner G = {g1, . . . ,gt} de I utilizando el Teorema 2.15 (algoritmo
de Buchberger).
- Por el Corolario 2.13 podemos afirmar que f ∈ I⇔ f G
= 0.
3. Problema de resolución de un sistema de ecuaciones.
Veamos cómo podemos aplicar las bases de Gröbner para resolver sistemas de ecuaciones en
varias variables:
- Si encontramos una base de Gröbner de un ideal, con respecto al orden lexicográfico, la
forma de las ecuaciones se simplifica bastante, ya que las variables se van eliminando suce-
sivamente. Un sistema de ecuaciones de esta forma es mucho más fácil de resolver.
- Por la Proposición 2.11, la cual dice que las variedades afines están determinadas por ideales,
se tiene que las soluciones obtenidas con el procedimiento anterior, son todas las que existen.
4. Problema de implicitación en ideales.
El problema de encontrar un sistema de ecuaciones cuyas soluciones sean los puntos de una
variedad puede resolverse utilizando nuevamente las bases de Gröbner. Veamos cómo:
- Consideramos las ecuaciones paraméticas
x1 = f1(t1, . . . , tm),
...
xn = fn(t1, . . . , tm),
las cuales definen un subconjunto de una variedad V⊆ Kn. Nos centramos en el caso de que
fi sean realmente polinomios. Consideramos la siguiente variedad afín en Km+n
x1− f1(t1, . . . , tm) = 0,
...
xn− fn(t1, . . . , tm) = 0.
La idea es eliminar las variables t1, . . . , tm de esas ecuaciones. Para ello tenemos que obtener
una base de Gröbner.
- Supongamos que hemos obtenido una base de Gröbner para el ideal I = 〈x1− f1, . . . ,xn− fn〉
con respecto al orden lexicográfico (t1 > · · ·> tm > x1 > · · ·> xn ). Entonces los polinomios
de la base de Gröbner que solo involucran las variables x1, . . . ,xn son las soluciones del
sistema de ecuaciones.
Capítulo 3
Coloreado de grafos
En este capítulo vamos a definir el concepto de grafo simple, al cual llamaremos grafo, y veremos
cómo aplicar las bases de Gröbner a la Teoría de grafos, en particular daremos una solución al problema
del k-coloreado en un grafo.
Definición 24. Un grafo G es un par G = (V,E), donde V es un conjunto finito de puntos, llamados
vértices, y E es un conjunto de pares no ordenados de vértices, llamadas aristas del grafo. Además
diremos que dos vértices son adyacentes si ambos son extremos de la misma arista.
Definición 25. Un camino entre dos vértices u1 y ut es una sucesión de aristas de la forma
{u1,u2},{u2,u3}, . . . ,{ut−1,ut} que une los vértices u1 y ut .
Definición 26. Sea G = (V,E) un grafo. Se dice que G es un grafo conexo si para todo par u,v ∈ V
siempre existe un camino que une u y v.
Definición 27. Sea G un grafo conexo con vértices V = {1, . . . ,n} y aristas E = {1, . . . ,m}. Sea C un
conjunto finito cuyos elementos llamaremos colores. Una coloración de G es una correspondencia tal
que a cada uno de los vértices de G se le asigna un color de C de manera que dos vértices adyacentes no
pueden recibir el mismo color. Formalmente, una coloración de G es una aplicación γ : V −→C tal que
γ(u) 6= γ(v) si existe una arista de G que une u y v. El valor de γ(u) es el color que recibe el vértice u en
la coloración γ .
Definición 28. Una coloración de un grafo G con k colores (k ≥ 1) se llama k-coloración de G.
Definición 29. Diremos que un grafo G es k-coloreable si existe una k-coloración asignada.
Observar que si G es k-coloreable inmediatamente se tiene que G es también (k + 1)-coloreable.
Notar también que si n es el número de vértices entonces G es n-coloreable.
Definición 30. El número cromático de un grafo G se define como el mínimo valor k ∈ N tal que G es
k-coloreable y se denota por χ(G). Si k = χ(G) se dice que el grafo es k-cromático.
Ejemplo 11. Sea G un grafo conexo formado por 5 vértices, luego V = {1,2,3,4,5}, y por 4 aristas,
luego E = {{1,3},{2,4},{3,4},{3,5}}. Este grafo es claramente 5-coloreable ya que tiene 5 vértices.
Sin embargo, χ(G) = 2 y así G es 2-coloreable.
17
18 Capítulo 3. Coloreado de grafos
Ahora que tenemos claras las definiciones anteriores, vamos a explicar en qué consiste el problema
que queremos resolver usando bases de Gröbner.
1. Problema del k-coloreado en un grafo:
Sea G = (V,E) un grafo. Entonces el problema del k-coloreado en un grafo busca que el grafo
sea k-coloreable, es decir, ver que existe una aplicación γ : V −→ Ck = {c1, . . . ,ck} tal que si
{u,v} ∈ E entonces γ(u) 6= γ(v).
3.1. Resolución del problema del k-coloreado
Para resolver el problema del k-coloreado en un grafo utilizaremos un sistema de ecuaciones po-
linómicas. A continuación se explica cómo obtener las ecuaciones del sistema y veremos un ejemplo
práctico. Si el lector tiene interés en conocer los detalles, ver [2].
Consideramos un grafo con n vértices. Sea xi la variable asignada al vértice i∈V y sea ct el elemento
asignado a cada color. Consideremos el conjunto {ct : 1≤ t ≤ k} ⊆ K, con K cuerpo y con k≤ i. Como
este ha de ser algebraicamente cerrado, para poder aplicar luego la Proposición 2.18, tendría que ser
K = C. Sin embargo, como los polinomios con los que vamos a trabajar tienen coeficientes en Q,
podemos en realidad considerar el cuerpo de los racionales K =Q.
Definimos las dos siguientes funciones:
f (x) =
k
∏
t=1
(x− ct), g(x,y) =
f (x)− f (y)
x− y
.
Vamos a ver qué condiciones necesitamos y cómo escribirlas matemáticamente para obtener así
nuestro sistema de ecuaciones polinómicas.
• Queremos que todos nuestros vértices estén coloreados. Por la definición de f , si f (xi) = 0 se
tiene entonces xi = ct , o lo que es lo mismo, a cada vértice se le asigna un color. De modo que:
f (xi) = 0, ∀i ∈ {1, . . . ,n}.
La función f (xi) es un producto de polinomios ya que es de la forma f (xi) = (xi−c1) · · ·(xi−ck),
y el producto de polinomios es un polinomio. Luego, f (xi) es un polinomio en la variable xi.
Como K[xi]⊆ K[x1, . . . ,xn] entonces f (xi) es un polinomio en las variables x1, . . . ,xn.
• Además queremos que no haya dos vértices conectados por la misma arista y que tengan el mismo
color, es decir, que todo par de vértices conectados por una arista tengan colores diferentes. Por
las definiciones de f y g, si g(xi,x j) = 0 se tiene entonces f (xi)− f (x j) = 0 (luego cada vértice
tiene un color asignado) y xi− x j 6= 0 (luego son colores distintos). De modo que:
g(xi,x j) = 0, si{i, j} ∈ E.
Sabemos que g(xi,x j) es un polinomio en el anillo de polinomios K[x1, . . . ,xn] porque como
f (x) = xk +ak−1xk−1 + · · ·+a1x+a0, podemos escribir
g(xi,x j) =
xk
i − xk
j
xi− x j
+
ak−1xk−1
i −ak−1xk−1
j
xi− x j
+ · · ·+
a1xi−a1x j
xi− x j
+
a0−a0
xi− x j
.
Entonces para cualquier fracción
am(xm
i − xm
j )
xi− x j
sabemos que (xm
i −xm
j )= (xi−x j)(xm−1
i +xm−2
i x j+
· · ·+ xm−1
j ). Por lo tanto
am(xm
i − xm
j )
xi− x j
= am(xm−1
i + xm−2
i x j + · · ·+ xm−1
j ).Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 19
De modo que nuestro sistema de ecuaciones polinómicas, para resolver el problema del k-coloreado,
es el siguiente {
f (xi) = 0, ∀i ∈ {1, . . . ,n}
g(xi,x j) = 0, si{i, j} ∈ E.
(3.1)
Por el Corolario 2.18, tenemos que el sistema tiene solución si y solo si G 6= {1}, o equivalentemen-
te, el sistema no tiene solución si y solo si G= {1}, siendo G base de Gröbner reducida. Si efectivamente
posee solución, podemos afirmar que el grafo es k-coloreable.
Para hallar los valores de las ecuaciones del sistema, utilizaremos el software SageMath [10]. Se ha
creado un código llamado “Resolución del problema del coloreado”, el cual podemos encontrar en el
Apéndice A. Bastará introducir nuestro grafo e indicar el número de colores que queremos usar.
Para resolver este sistema podemos utilizar las bases de Gröbner tal y como se explicó en el tercer
problema de la Sección 2.6. Para entender esto mejor, estudiemos el siguiente ejemplo.
Ejemplo 12. Consideramos el grafo no dirigido G= (V,E) con V = {1,2,3} y E = {{1,2},{2,3}}.
Nuestro sistema de ecuaciones polinómicas es:
2x2
1− x1 = 0
2x2
2− x2 = 0
2x2
3− x3 = 0
2x1 +2x2−1 = 0
2x2 +2x3−1 = 0
Vamos a aplicar lo estudiado en el capítulo anterior sobre cómo resolver un sistema de ecuaciones
utilizando bases de Gröbner, ya que hemos obtenido un sistema de ecuaciones en varias variables.
- Hallamos una base de Gröbner, con respecto al orden lexicográfico, del ideal I, el cual está gene-
rado por las ecuaciones del sistema anterior. Esta base es:
G = { f1, f2, f3}= {x1− x3,x2 + x3−1,x2
3− x3}.
Por el Corolario 2.18 se tiene que el grafo es 2-coloreable si y solo si 1 /∈ G. Por lo tanto, como
existe solución (ya que la base no es trivial), se tiene que este grafo es 2-coloreable. Veamos en el
siguiente paso cuál es su solución.
- Resolviendo el sistema formado por f1 = 0, f2 = 0 y f3 = 0, obtenemos que sus soluciones son:
x1 = x3 = 0 y x2 = 1 o x1 = x3 = 1 y x2 = 0.
Por la Proposición 2.11, se tiene que estas soluciones halladas son todas las que existen.
De este modo, identificando el valor 0 al color azul y el valor 1 al color marrón, tenemos que el
grafo se puede pintar de estas dos maneras:
Observar que este procedimiento es válido para cualquier grafo, incluso si consideramos grafos más
complejos, como puede ocurrir en el caso de los Sudokus, tal y como se estudia en el siguiente capítulo.
Capítulo 4
Sudokus y bases de Gröbner
Los Sudokus están formados por un tablero en el que hay una cuadrícula 9×9 dividida en 9 cajas de
tamaño 3×3 en las cuales aparecen números del 1 al 9 cumpliendo ciertas condiciones. Estas condicio-
nes son: en cada caja de 3×3 no puede haber números repetidos, al igual que cada fila y cada columna
han de estar completas sin repeticiones. Cada juego empieza con el tablero parcialmente relleno por
ciertos dígitos, a los cuales llamaremos pistas, y el objetivo para resolverlo es encontrar qué número
corresponde a cada celda en blanco.
A lo largo de este capítulo será importante tener claro que un puzle Sudoku es un subconjunto de un
Sudoku que determina de forma única el resto del tablero.
La finalidad de este capítulo es resolver dicho juego matemático usando las bases de Gröbner. Para
ello, interpretaremos el Sudoku como un grafo y la resolución del Sudoku como un problema del
k-coloreado, de modo que:
- El grafo tiene 81 vértices, uno para cada celda.
- Asignando a cada número un color, tenemos k = 9 colores.
- Las aristas están definidas por las relaciones de adyacencia: donde queremos diferentes números
(misma fila, columna y caja 3×3) necesitamos diferentes colores.
Definición 31. Dado un Sudoku, cada fila, cada columna o cada caja 3×3 formará una región.
Definición 32. Diremos que dos vértices están ligados si pertenecen a la misma región.
Nuestro objetivo es dar colores (dígitos del 1 al 9) a cada vértice de modo que si dos vértices están
ligados tienen que tener colores distintos. Es decir, queremos resolver el problema del 9-coloreado en un
grafo, el cual viene representado mediante un Sudoku, para lo cual utilizaremos el procedimiento des-
crito en el Capítulo 3. Por lo tanto, buscamos una manera de colorear el grafo con exactamente 9 colores.
Notar que no podríamos completar el Sudoku con menos de 9 números diferentes ya que entonces
dejaríamos alguna celda vacía. Por ello, el número cromático 1 de nuestro grafo es 9.
4.1. Sudokus
En un Sudoku cada vértice tiene otros 20 vértices con los que estar ligado. Como tenemos 81 celdas,
entonces el número de aristas de nuestro grafo es igual a
81 ·20
2
= 810.
1Si H es un grafo, para calcular su número cromático con SageMath, utilizamos la función chromatic_number(H).
20
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 21
Para resolver el problema del 9-coloreado utilizaremos un sistema de ecuaciones polinómicas tal y
como se presenta en el Capítulo 3. Veamos qué datos tenemos y cómo, a partir de ellos, construimos las
ecuaciones.
Consideramos un Sudoku, el cual tiene 81 celdas y las numeramos de izquierda a derecha y de
arriba abajo. Identificando celdas con vértices, tenemos que la celda i corresponde a la variable xi asig-
nada a cada vértice, con i = {0, . . . ,80}. Escribimos el conjunto de colores como {ck : 1 ≤ k ≤ 9} ⊆
Q[x0, . . . ,x80].
Sea I ⊆ Q[x0, . . . ,x80]. Entonces, para que el grafo sea 9-coloreable necesitamos un sistema de
ecuaciones polinómicas obtenido de forma análoga a como construimos el sistema (3.1).
- Queremos que todos nuestros vértices estén coloreados (es decir, que todas las celdas estén relle-
nas por un número). Entonces consideramos el polinomio
f (xi) =
9
∏
k=1
(xi− ck) = 0, ∀ 0≤ i≤ 80.
- Queremos que no haya dos vértices conectados por la misma arista y que tengan el mismo color,
es decir, que se cumplan las relaciones de adyacencia definidas anteriormente. De modo que
tenemos
g(xi,x j) =
f (xi)− f (x j)
xi− x j
= 0, ∀ 0 ≤ i < j ≤ 80.
Además de considerar f y g, para poder resolver el Sudoku, toda la información inicial debe ser
incluida en forma de polinomios. ¿Qué forma tendrán estos nuevos? Si en la celda xi tenemos la infor-
mación de que está el valor ck, con i = 0, . . . ,80, k = 1, . . . ,9, entonces el polinomio será xi− ck.
Entonces el ideal I para el cual tendremos que hallar una base de Gröbner (como en el problema del
k-coloreado) es I = J +L = 〈 f (xi),g(xi,x j)〉+ 〈xi− ck〉, siendo L el ideal generado por los polinomios
de las incógnitas que ya tienen valor.
Ejemplo 13. Consideramos el puzle Sudoku de la Figura 4.1.
Figura 4.1
Como acabamos de explicar, una de las cosas que tenemos que hacer para resolverlo, es añadir los
siguientes polinomios al ideal I:
x0−3, x2−4, x11−8, x12−4, x13−9, x16−6, x20−7, x23−1, x27−7, x32−8,
x34−5, x38−2, x39−6, x41−4, x42−3, x46−8, x48−9, x53−1, x57−3,
x60−2, x64−2, x67−8, x68−6, x69−4, x78−8, x80−6.
Observación 1. Una vez que hemos añadido toda la información inicial del Sudoku, se obtiene que al-
guno de los polinomios f (xi) no es realmente necesario, ya que al considerar f (xi) estamos consiguiendo
que todos los vértices estén coloreados, pero hay algunos que ya están coloreados desde el principio.
Sin embargo, podemos dejar estos valores duplicados ya que, matemáticamente, no es contradictorio.
22 Capítulo 4. Sudokus y bases de Gröbner
Toda la información sobre las soluciones de un Sudoku está contenida en la variedad afín
V(I) = {(c0, . . . ,c80) ∈Q81 |H(c0, . . . ,c80) = 0, H ∈ I}.
De modo que, como I = J +L entonces tenemos que considerar la siguiente variedad afín para hallar
las soluciones de nuestro problema:
V(J+L) = V(〈 f (xi),g(xi,x j),xi− ck〉).
Una vez que tenemos claro qué forma tiene el ideal I, tenemos que hallar una base de Gröbner
reducida de I, con respecto al orden lexicográfico.
Proposición 4.1. Las siguientes afirmaciones son equivalentes:
i) La única solución del Sudoku es c = (c0, . . . ,c80).
ii) I = J+L= 〈{x0− c0, . . . ,x80− c80}〉.
iii) G = {xi− ck | i = 0, . . . ,80}, donde ck son números del 1 al 9, es una base de Gröbner reducida
de I.
Demostración. Ver [8, Proposición 25].
Es decir, la base de Gröbner reducida de I, G, contendrá polinomios de la forma xi−ck. Resolviendo
el sistema formado por los polinomios de G igualados a 0 se obtiene xi = ck de modo que la celda xi
tendrá el valor ck. Por la Proposición 2.11 estas soluciones son todas las que existen.
Para entender todo esto es interesante ver cómo se aplica la teoría explicada anteriomente a un
ejemplo práctico de resolución de un Sudoku. Sin embargo, antes de empezar, es conveniente trabajar
primero con una versión más simple de los Sudokus, llamada Shidokus.
4.1.1. Caso particular: Shidokus
Los Shidokus son un caso particular de los Sudokus ya que las reglas de estos rompezabezas son
las mismas: todas sus regiones contienen exactamente solo una vez cada número. La única diferencia es
que los Shidokus están formados por una cuadrícula 4×4 dividida en 4 cajas de tamaño 2×2, de modo
que los dígitos ahora se moverán del 1 al 4.
En un Shidoku cada vértice tiene otros 7 vértices con los que estar ligado. Como tenemos 16 celdas,
entonces el número de aristas de nuestro grafo es igual a
16 ·7
2
= 56.
Observar que ahora, nuestro objetivo es resolver el problema del 4-coloreado en un grafo aplicando
el método explicado en este capítulo. Para entender mejor cómo, veamos el siguiente ejemplo.
Ejemplo 14. Sea el puzle Shidoku, correspondiente a la imagen de la izquierda, de la Figura 4.2.
Figura 4.2
Para resolverlo, tenemos que calcular la base de Gröbner reducida del ideal I. Este ideal estará
formado por:
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 23
- Polinomios de la forma f (xi) =
4
∏
k=1
(xi− ck), ∀ 0≤ i≤ 15.
- Polinomios de la forma g(xi,x j) =
f (xi)− f (x j)
xi− x j
= 0, ∀ 0 ≤ i < j ≤ 15.
- Los siguientes polinomios, que equivalen a las condiciones iniciales:
x0−1, x2−2, x3−3, x5−2, x8−4, x11−2, x14−1.
Considerando I el ideal formado por todos esos polinomios, podemos calcular la base de Gröbner,
con respecto al orden lexicográfico, de I. La base obtenida es:
G = {x0−1,x1−4,x2−2,x3−3,x4−3,x5−2,x6−4,x7−1,x8−4,
x9−1,x10−3,x11−2,x12−2,x13−3,x14−1,x15−4}.
Esta base es la que nos proporciona la solución del Shidoku. Esto se traduce en que la imagen de la
derecha de la Figura 4.2 es la solución de nuestro puzle Shidoku inicial.
A continuación, se explican los pasos que se han realizado con SageMath para la resolución del
ejemplo anterior.
Se ha introducido el tablero vacío de un Shidoku mediante el código explicado en el Apéndice A.
Se han calculado los polinomios f (xi), g(xi,x j) aplicando el código creado para la resolución del
problema del coloreado (ver Apéndice A). Se ha definido J como el ideal generado por estos
polinomios.
Se han introducido los polinomios referentes a las condiciones iniciales y se ha definido L como
el ideal generado por estos polinomios.
Se ha calculado la base de Gröbner del ideal I = J+L. Para este ejemplo se ha utilizado la función,
ya integrada en SageMath, I.groebner_basis(). Es conveniente usar esta función en vez de aplicar
el algoritmo de Buchberger (el cual está implementado en el Apéndice A) ya que el algoritmo no
proporciona una base de Gröbner reducida.
Sin embargo, a pesar de obtener la base de Gröbner reducida, es posible que nuestro Shidoku inicial
no posea solución única. Esto se puede observar con el siguiente ejemplo.
Ejemplo 15. Veamos qué ocurre con el Shidoku de la Figura 4.3.
Figura 4.3
Repitiendo los mismos pasos que en el ejemplo anterior, obtenemos una base de Gröbner G aunque
ahora no todos los polinomios de la base son de la forma xi− ck.
Entonces, para encontrar la solución del Shidoku (la cual existe ya que G 6= {1}), tenemos que
resolver el sistema de ecuaciones formado por los polinomios de G igualados a 0. Una vez resuelto, lo
esperado es obtener soluciones de la forma xi = ck las cuales nos proporcionen la solución del sistema.
Sin embargo, la solución del sistema no es única, lo que implica que existe una variedad de soluciones
para nuestro Shidoku. Estas soluciones son las que podemos observar en la Figura 4.4.
24 Capítulo 4. Sudokus y bases de Gröbner
Figura 4.4
4.1.2. Resolución Sudokus
Ahora que hemos entendido cómo resolver los Shidokus, podemos aumentar el tamaño de n y se-
guir los mismos pasos para conseguir el objetivo de este capítulo: resolver los Sudokus utilizando el
problema del 9-coloreado y las bases de Gröbner.
Continuamos con el puzle Sudoku del Ejemplo 13, el cual queremos resolver. Recordar que ya ha-
bíamos hallado los polinomios correspondientes a las condiciones iniciales (los cuales generan L) de
modo que solo falta construir el ideal I = J+L y obtener su base de Gröbner G. De este modo, siguien-
do los mismos pasos que para los Shidokus y utilizando SageMath, se tiene que la solución es:
Figura 4.5
Desafortunadamente, los sistemas de ecuaciones polinómicas que resuelven los Sudokus no son muy
“amigables” ya que el número de ecuaciones es bastante elevado. A pesar de que existen funciones, ya
incluidas en los paquetes de la mayoría de los lenguajes de programación, para resolver dichos sistemas,
producir el sistema de ecuaciones y aplicar las bases de Gröbner no es un buen método en general. Sin
embargo, este enfoque tiene algunas ventajas como por ejemplo obtener todas las posibles soluciones
tal y como se ha visto en el Ejemplo 15.
4.1.3. Generalización n×n
Al principio de este capítulo hemos definido que un Sudoku está formado por una cuadrícula 9×9
y también hemos visto que se puede reducir n dando así lugar a los Shidokus. Entonces, tiene su lógica
preguntarnos ¿n puede ser cualquier número natural, exceptuando el 0? Y efectivamente la respuesta a
esto es afirmativa, podemos elegir n.
La resolución de estos Sudokus tamaño n× n es simplemente una generalización de lo estudiado
con anterioridad. Es decir, para resolverlo tenemos que calcular la base de Gröbner reducida del ideal
I = J+L formado por:
- El ideal J formado por los polinomios f y g definidos como f (xi) =
n
∏
k=1
(xi− ck),
g(xi,x j) =
f (xi)− f (x j)
xi− x j
= 0, siendo 0 ≤ i < j ≤ n2−1.
- El ideal L = 〈xi− ck〉, siendo 0≤ i≤ n2−1, 1≤ k ≤ n.
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 25
De este modo, una vez que tenemos la base de Gröbner reducida G, por la Proposición 4.1 tendremos la
solución para cualquier Sudoku de tamaño n×n.
4.2. Conjeturas matemáticas
A continuación, vamos a dar algunas conjeturas matemáticas, es decir, algunas afirmaciones aparen-
temente verdaderas, ya que se han hecho pruebas confirmando su veracidad, pero no hay demostración
matemática de ellas.
• Uno de los temas que podemos cuestionarnos es ¿cuántos posibles Shidokus y Sudokus distintos
hay, ignorándose las relaciones de simetría entre soluciones similares? Tal y como se explica en
[11], existen 288 tableros de Shidokus. Sin embargo, al intentar contar cuántos Sudokus existen,
el número de posibilidades es mayor y el coste computacional aumenta. En [11] se explica el
camino que se ha seguido para obtener una buena aproximación al número total de tableros de
Sudokus válidos, siendo este número 6,6571 ·1021.
• Uno de los problemas relacionados con el Sudoku que más ha interesado a los matemáticos, por
haber estado mucho tiempo sin respuesta, es el del número mínimo de pistas que puede tener un
Sudoku para resolverlo de manera única. Se ha conseguido encontrar multitud de puzles de 17
pistas con solución única pero ninguno con solo 16 [11]. Este problema, denominado “Problema
del Sudoku mínimo” fue resuelto en 2012 con la ayuda de un ordenador evaluando todos, salvo
equivalencias, los cuadrados de Sudokus en busca de algún puzle de 16 pistas. Los artífices de esta
demostración son Gary McGuire, Bastian Tugemann y Gilles Civario. En el caso de los Shidokus,
este número mínimo es 4, como se mencionaen [11].
• Sin embargo, ni todos los Sudokus con 17 pistas, ni todos los Shidokus con 4 pistas (véase el
Ejemplo 15), tienen solución única. Esto nos lleva a preguntarnos, ¿cuál es el número máximo de
pistas que puede haber en una cuadrícula y aún no tener solución única? En la página 26 de [11]
se observa un puzle Sudoku con 77 pistas y sin solución única. De modo que 77 es el máximo
número de pistas para el cual un Sudoku no tiene solución única. Además se conjetura que para
cualquier otra variante de los Sudokus, de tamaño n×n, este número máximo es n2−4.
• La dificultad en los Sudokus se cree que depende del número de pistas iniciales. Pero, sorpren-
dentemente, esta dificultad se basa en la posición de las pistas. Esta es la razón por la que la
distribución de las pistas distingue un Sudoku fácil de otro difícil. En la página 122 de [3] se
muestra un Sudoku con 20 pistas de mínima dificultad y otro con 28 pistas de dificultad máxima.
• Una medida más refinada de la dificultad se hace a partir del estudio de las técnicas de resolución
de Sudokus, como se muestra en [3]. Algunos métodos son más simples que otros, por lo que se
puede conjeturar que si un Sudoku requiere un razonamiento más complejo para resolverlo, se
le asocia una dificultad mayor. Sin embargo, estimar la dificultad de un Sudoku no es, ni mucho
menos, una ciencia exacta, debido a la enorme carga de subjetividad que ello conlleva.
4.3. Conclusión
A modo de conclusión, señalar la importancia que alberga esta aplicación de las bases de Gröbner,
ya que hemos conseguido unir conceptos geométricos y algebraicos. Para una modelización geométrica
de los Sudokus hemos estudiado un problema fundamental de la Teoría de grafos el cual trata de colorear
un grafo con k colores. De este modo, hemos sido capaces de configurar matemáticamente un Sudoku
como si fuese un grafo con tantos vértices como celdas. Además, hemos resuelto sistemas de ecuaciones
no lineales utilizando así la parte teórica estudiada en el Capítulo 2, la cual hace referencia a un estudio
en el marco algebraico. Por lo tanto, a pesar de que aparentemente el Sudoku es un juego sencillo de
pura lógica, el estudio realizado en este capítulo muestra un trasfondo claramente matemático, tanto en
su planteamiento como en su resolución.
Apéndice A
Códigos SageMath
Esta parte final está destinada a mostrar todos los códigos escritos en SageMath que se han utilizado
para la resolución de varios ejemplos a lo largo del presente trabajo.
• Algoritmo de la división en varias variables.
- Las variables de entrada son ( f ,G,A) donde f es un polinomio, G es una lista de polinomios
y A es un anillo de polinomios.
- Las variables de salida son (Q,A(r)) donde Q es una lista de polinomios, que se correspon-
den con los cocientes, y A(r) es el resto de la división.
d e f d i v ( f , G,A ) :
s = l e n (G)
p = A( f )
Q = s * [ 0 ]
r = 0
w h i l e p != 0 :
i = 0
d i v i s i o n = f a l s e
w h i l e i < s and d i v i s i o n == F a l s e :
i f G[ i ] . l t ( ) . d i v i d e s ( p . l t ( ) ) :
Q[ i ] = Q[ i ] + p . l t ( ) / / G[ i ] . l t ( )
p = p − ( p . l t ( ) / / G[ i ] . l t ( ) ) *G[ i ]
d i v i s i o n = True
e l s e :
i = i + 1
i f d i v i s i o n == F a l s e :
r = r + p . l t ( )
p = p − p . l t ( )
r e t u r n Q, A( r )
• S-polinomio.
- Las variables de entrada son ( f ,g,A) donde f y g son dos polinomios y A es un anillo de
polinomios.
- La variable de salida es s, correspondiente al S-polinomio buscado.
d e f S_po l inomio ( f , g ,A ) :
a = A( f ) . lm ( )
b = A( g ) . lm ( )
27
28 Capítulo A. Códigos SageMath
c = lcm ( a , b )
s = A( ( c / a )* f −( c / b )* g )
r e t u r n s
• Algoritmo de Buchberger.
- Las variables de entrada son (F,A) donde F es una lista de polinomios y A es un anillo de
polinomios.
- La variable de salida es G, la cual es una lista de polinomios (estos polinomios son los que
forman la base de Gröbner).
d e f Buch ( F ,A ) :
n= l e n ( F )
G=F
f o r i i n [ 0 . . n − 2 ] :
f o r j i n [ i + 1 . . n − 1 ] :
s= S_po l inomio (G[ i ] ,G[ j ] ,A)
d= d i v ( s , G,A) [ 1 ]
i f d ! = 0 :
r e t u r n Buch ( F+[ d ] ,A)
r e t u r n G
• Resolución del problema del coloreado.
- Las variables de entrada son (G,k) donde G es un grafo y k es el número de colores.
- Las variables de salida son ( f + g,A) donde f + q son las ecuaciones de nuestro sistema y
A es el anillo de polinomios.
d e f s i s t e m a (G, k ) :
n = G. num_ver t s ( )
xs = l i s t ( v a r ( ’ x_ % d ’ % i ) f o r i i n r a n g e ( n ) )
F = QQ
A = Polynomia lR ing ( F , xs , o r d e r = ’ lex ’ )
c o l o r e s = r a n g e ( k )
f = [ ]
f o r j i n xs :
f = f + [A( prod ( [ ( j − i ) f o r i i n c o l o r e s ] ) ) ]
g = [ ]
a r i s t a s = [ [ _ [ 0 ] , _ [ 1 ] ] f o r _ i n G. edges ( ) ]
f o r j i n a r i s t a s :
f1 = [A( prod ( [ ( xs [ j [ 0 ] ] − i ) f o r i i n c o l o r e s ] ) ) ,
A( prod ( [ ( xs [ j [ 1 ] ] − i ) f o r i i n c o l o r e s ] ) ) ]
g = g + [A( ( f1 [0] − f1 [ 1 ] ) / ( xs [ j [ 0 ] ] − xs [ j [ 1 ] ] ) ) ]
r e t u r n f + g , A
Observación 2. Para definir el anillo de polinomios en el que queremos trabajar, se puede especi-
ficar cualquiera de los órdenes monomiales explicados en el Capítulo 2, simplemente escribiendo
lo siguiente:
◦ Orden lexicográfico: order = ’lex’
◦ Orden lexicográfico graduado: order = ’deglex’
◦ Orden lexicográfico graduado inverso: order = ’degrevlex’
Bases de Gröbner y su aplicación a los sudokus - Bárbara Zapater Zarroca 29
• Creación de un tablero Sudoku, de tamaño n×n, sin pistas.
Para ello, se han tenido que crear dos funciones. Previamente es conveniente explicar que tratamos
el Sudoku como si fuera una matriz, de modo que la celda xk corresponde al elemento (i, j) con
i, j = 0, . . . ,n2−1. Por ejemplo, en un Sudoku 9×9 la celda x13 corresponde al elemento (1,4).
1. A través de esta función cada celda del Sudoku se convierte en un elemento matricial de la
forma (i, j).
- Las variables de entrada son (i, j,n) donde i corresponde al primer elemento del par
(i, j), j corresponde al segundo elemento del par (i, j) y n hace referencia al tamaño.
- La variable de salida es el subíndice de la celda xk.
# Pa ra un Sudoku 9x9 , se toma n=3
d e f c o n v e r t i r ( i , j , n ) :
r e t u r n ZZ ( i *n+ j )
2. Mediante esta función imponemos las relaciones de adyacencia, de modo que no se repitan
los dígitos en ninguna de las regiones.
- La variable de entrada es n que hace referencia tanto al número de filas como al número
de columnas.
- La variable de salida es la lista de todas las aristas E cumpliendo las relaciones impues-
tas.
# Pa ra un Sudoku 9x9 , se toma n=9
d e f eqs_sudoku ( n ) :
R = I n t e g e r s ( 3 )
E = [ ]
# P a r e s ( i , j ) ( i , k ) t a l e s que x_ ( i , j ) y x_ ( i , k ) p e r t e n e c e n
a l a misma f i l a
# P a r e s ( j , i ) ( k , i ) t a l e s que x_ ( j , i ) y x_ ( k , i ) p e r t e n e c e n
a l a misma f i l a
f o r i i n r a n g e ( n ^ 2 ) :
f o r j i n r a n g e ( n ^ 2 ) :
f o r k i n [ j + 1 . . n ^2 −1] :
a= c o n v e r t i r ( i , j , n ^2 )
b= c o n v e r t i r ( i , k , n ^2 )
i f ( n o t [ a , b ] i n E ) and ( n o t [ b , a ] i n E ) :
E = [ [ a , b ] ] + E
a= c o n v e r t i r ( j , i , n ^2 )
b= c o n v e r t i r ( k , i , n ^2 )
i f ( n o t [ a , b ] i n E ) and ( n o t [ b , a ] i n E ) :
E = [ [ a , b ] ] + E
# P a r e s ( i 1 * i2 , j 1 * j 2 ) ( i 1 * i3 , j 1 * j 3 ) t a l e s que
x_ ( i 1 * i2 , j 1 * j 2 ) y x_ ( i 1 * i3 , j 1 * j 3 ) p e r t e n e c e n
a l mismo b loq ue n x n
f o r i 1 i n r a n g e ( n ) :
f o r j 1 i n r a n g e ( n ) :
f o r i 2 i n r a n g e ( n ) :
f o r j 2 i n r a n g e ( n ) :
f o r i 3 i n r a n g e ( n ) :
f o r j 3 i n r a n g e ( n ) :
a= c o n v e r t i r ( i 1 *n+ i2 , j 1 *n+ j2 , n ^2 )
30 Capítulo A. Códigos SageMath
b= c o n v e r t i r ( i 1 *n+ i3 , j 1 *n+ j3 , n ^2 )
i f a<b and ( n o t [ a , b ] i n E ) and
( n o t [ b , a ] i n E ) :
E=E + [ [ a , b ] ]
r e t u r n E
Observación