Repositorio Institucional de Documentos

Bases de G öbne y su aplicación a la esolución de Sudokus Bá ba a Zapa e Za oca T abajo de in de g ado en Ma emá icas Uni e sidad de Za agoza Di ec o es del abajo: José Ignacio Cogolludo Agus ín y Jo ge Ma ín Mo ales Espacio 9 de eb e o de 2021 P ólogo Lógica, apidez, paciencia y ma emá icas. Teniendo en cuen a es os cua o concep os podemos e- sol e el juego del Sudoku, el cual sigue siendo un pasa iempo emocionan e pa a millones de pe sonas. Geomé icamen e hablando, un Sudoku es un able o de amaño 9×9 di idido en cajas 3×3, las cuales poseen núme os en e el 1 y el 9. Es e ompecabezas obedece las siguien es eglas: no puede habe núme os epe idos en la misma ila, columna o caja 3 ×3. Pe o, ¿po , pa a qué y cómo se aplican las ma emá icas a la esolución de es e pasa iempo? Es en es e con ex o donde se basa el p esen e abajo. La his o ia de los Sudokus se emon a a un juego del siglo XVIII, donde los ma emá icos suizos lo llama on “Cuad ados la inos”. Sin emba go, el juego que conocemos ac ualmen e ue in en ado a ina- les de la década de 1970 en Nue a Yo k. Es e juego, ideado po el a qui ec o Howa d Ga ns, se conocía como “Ubica núme os”, pues consis ía en coloca núme os en los espacios acíos de una cuad ícula. Ac ualmen e, es e ompecabezas se conoce como “Sudoku”. El nomb e p o iene de dos palab as japo- nesas: Su, que signi ica núme o y Doku, que signi ica solo. Es e juego ma emá ico ue muy conocido en Japón a pa i de 1986 aunque su popula idad mundial llega ía unos años más a de, en o no al 2005. Hoy en día el Sudoku sigue siendo un enigma habi ual en los pe iódicos, páginas online, e is as, concu sos... Además, como se a a de un puzle numé ico que es imula las capacidades men ales y la memo ia, pe mi e que no sea solo una di e sión, sino que ambién esul e un ap endizaje. Po o a pa e, exis en algunas a ian es de es e amoso juego. En [7] se da un modelo ma emá ico jun o con su sis ema de ecuaciones algeb aicas. Algunas de es as a ian es son: el able o es á colo eado en g is y blanco de mane a que las celdas g ises con ienen núme os pa es y las celdas blancas solamen e impa es (Sudoku pa -impa ), se puede da como pis a inicial la suma de un g upo de celdas en ez del alo de cada celda indi idual (Sudoku kille ), el able o iene o mas dis in as de un ec ángulo (Sudo- kus geomé icos), e c. Aunque de p ime as esul e cuan o menos cu ioso, ealmen e el Sudoku se basa en undamen os ma emá icos, y po ello exis en mé odos numé icos con los que pode esol e los. T a ando el Sudoku como si ue a un g a o, inculando así la geome ía y el álgeb a, podemos esol e es e juego lógico. Un concep o cla e pa a ello son las bases de G öbne que, de una mane a elegan e y di ec a, nos pe mi i án conoce odas las soluciones de un sis ema de ecuaciones. Es as bases de ideales se o man de al mane a que pa a odo polinomio del ideal, el é mino p incipal de es e polinomio es di isible po alguno de los é minos p incipales de los polinomios que componen dicha base. Además, pa a ello, en es e abajo nos amilia iza emos con una de las muchas aplicaciones de las bases de G öbne , la colo ación de g a os. Cabe menciona la a iedad de aplicaciones elacionadas con es a eo ía, en e las que se encuen an calcula el polinomio mínimo en ex ensiones de cue pos, da demos aciones au omá icas en Geome ía Euclidiana, es udia sis emas c ip og á icos y p og amación en e a e incluso es udia algunos esul ados de Teo ía de g a os. III Es e abajo es á o ganizado del siguien e modo. En el Capí ulo 1 se a an los undamen os alge- b aicos y concep os p e ios que in oducen la eo ía de las bases de G öbne . En el Capí ulo 2 p o un- diza emos en dicha eo ía pa a lo cual abaja emos con polinomios en a ias a iables. Pa a es os dos p ime os capí ulos de in o mación más eó ica nos hemos basado en el lib o [5], pe o hay o as e e en- cias sob e es e ema como son [1]y[9]. A con inuación, en el Capí ulo 3 nos cen a emos en es udia el p oblema del colo eado en un g a o, lo cual es á undamen ado en la Sección 3 de [4]. Finalizando, en el Capí ulo 4 aplica emos lo es udiado en los es capí ulos p e ios pa a consegui nues o obje i o, esol- e Sudokus aplicando las ma emá icas y la compu ación. Es e capí ulo inal apoya su desa ollo y base eó ica en [7]. Po úl imo, en el Apéndice A se p esen an a ios códigos, u ilizados pa a la esolución de algunos ejemplos implemen ados median e el so wa e SageMa h [10], el cual usa en “backg ound” el p og ama SINGULAR [6] pa a calcula las bases de G öbne . Toda es a base ma emá ica es la que pe mi e que la gen e pueda pone a p ueba su ce eb o con ace ijos lógicos, in e esan es y desa ian es. Po lo cual, el Sudoku segui á siendo un en e enimien o que ido y popula en la ida co idiana de millones de pe sonas en odo el mundo. Palab as cla e: polinomios, algo i mo de la di isión, o den monomial, ideales monomiales, Lema de Dickson, bases de G öbne , Teo ema de las bases de Hilbe , algo i mo de Buchbe ge , g a o, k-colo ación, Sudoku, Shidoku. IV Summa y In his p ojec i will be explained se e al heo e ical esul s and p ac ical examples ela ed o Sudo- kus. Mo e speci ically, his wo k will be based on he s udy o he G öbne bases and i s applica ion o bo h g aph heo y and Sudokus esolu ion. This p ojec is di ided in o ou chap e s. A b ie desc ip ion o each chap e will be gi en inmedia- ely below. -Chap e 1: P e ious concep s and undamen als To begin wi h, he necessa y concep s o unde s anding he o he chap e s a e gi en. These con- cep s include de ini ions such as monomial, polynomial, a ine space, a ine and linea a ie ies and ideal, among o he s. The exis ence and uniqueness o he di ision algo i hm o polynomials in one a iable will be s udied. -Chap e 2: G öbne Bases Once he p e ious pa is comple ed, he main pa o his p ojec will be s udied. In his second chap e , he heo y o G öbne bases will be in oduced and s udied. Polinomials in K[x1,...,xn] will be deal and how o o de monomials will be discussed, explaining some o he exis ing monomial o de ings ypes. This concep will be impo an o s udy he di ision algo i hm in K[x1,...,xn]which will be be e unde s ood by an example. Besides, Dickson’s Lemma and Hilbe ’s basis Theo em will be s a ed and p o ed. Then, Buchbe ge ’s algo i hm will be unde s- ood. Tha esul will be used o cons uc he G öbne bases. A code o his algo i hm has been implemen ed using SageMa h, which can be ound in he Appendix A. To end his chap e , ou p oblems abou polynomials and ideals will be sol ed hanks o he G öbne bases: 1. The ideal desc ip ion p oblem. 2. The ideal membe ship p oblm. 3. The p oblem o sol ing polinomial equa ions. 4. The implici iza ion p oblem. -Chap e 3: G aph colo ing G aph colo ing wi h kcolo s is he main goal o his chap e . Fi s o all, he kind o g aphs we need will be de ined and hen, he explana ion and esolu ion o his p oblem will be ea ed. To do his, a sys em o polynomial equa ions imposing some condi ions will be gene a ed. To sol e his sys em, he G öbne bases will be used, o which a SageMa h code has been implemen ed. Mo eo e , his code is explained in he Appendix A. -Chap e 4: Sudokus and G öbne bases Sudokus will be sol ed using G öbne bases heo y and he Sudoku will be conside ed as i i was a g aph in o de o apply some esul s o Chap he 3. Tha is, o sol e Sudokus a sys em o polynomial equa ions has o be ob ained, in he same way ha i is ob ained o he g aph colo ing p oblem in he p e ious chap e . An ideal in he polynomial ing o se e al a iables will V be associa ed o he Sudoku. This ideal will be gene a ed by he polynomials which de ine he sys em o equa ions. The educed G öbne basis will be calcula ed o his ideal whose gene a o s o m a sys em equi alen o he o iginal sys em. Tha is why sol ing his new sys em o equa ions, using ma hema ics and compu a ion, he solu ion o he Sudoku is ob ained. In he Appendix A i is explained how o w i e wi h SageMa h a Sudoku wi h he ini ial clues gi en o be able o apply he code gene a ed o he p e ious chap e and hen he sys em will be sol ed. Finally, some ma hema ical conjec u es a e discussed. Mo eo e , a conclusion o his in e es ing applica ion o he G öbne bases is gi en. VI Índice gene al P ólogo III Summa y V 1. Concep os y undamen os p e ios 1 1.1. Polinomios en espacios a ines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Va iedadesa ines ..................................... 2 1.3. Ideales........................................... 2 1.4. Polinomios en una a iable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Bases de G öbne 5 2.1. O den monomial en a ias a iables . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. El algo i mo de la di isión en a ias a iables . . . . . . . . . . . . . . . . . . . . . . 7 2.3. Idealesmonomiales.................................... 9 2.4. El Teo ema de las bases de Hilbe y bases de G öbne . . . . . . . . . . . . . . . . . 11 2.5. C i e io y algo i mo de Buchbe ge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.6. Aplicaciones de las bases de G öbne . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3. Colo eado de g a os 17 3.1. Resolución del p oblema del k-colo eado ........................ 18 4. Sudokus y bases de G öbne 20 4.1. Sudokus.......................................... 20 4.1.1. Caso pa icula : Shidokus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.1.2. ResoluciónSudokus ............................... 24 4.1.3. Gene alización n×n............................... 24 4.2. Conje u asma emá icas.................................. 25 4.3. Conclusión ........................................ 25 A. Códigos SageMa h 27 Bibliog a ía 31 VII Capí ulo 1 Concep os y undamen os p e ios A lo la go de es e capí ulo da emos algunas de iniciones y algunos esul ados p elimina es que se án de ele ancia pa a comp ende las bases de G öbne , obje o p incipal de es udio del ma co eó ico. 1.1. Polinomios en espacios a ines De inición 1. Un monomio xαen las a iables x1,...,xnes un p oduc o de la o ma xα=xα1 1·xα2 2···xαn n donde odos los exponen es α1,...,αnson en e os no nega i os. El o den o al de un monomio es la suma de sus exponen es, el cual deno a emos median e |α|. De inición 2. Un polinomio en las a iables x1,...,xncon coe icien es en un cue po Kes una com- binación lineal ini a de monomios con coe icien es ambién en K. Esc ibi emos el polinomio de la siguien e mane a: =∑ α aαxα,aα∈K,α= (α1,...,αn). Deno a emos median e K[x1,...,xn]al conjun o de odos los polinomios en x1,...,xncon coe icien- es en el cue po K. Es e conjun o o ma un anillo de polinomios. De inición 3. Sea =∑ α aαxαun polinomio en K[x1,...,xn].En onces: i) El coe icien e del monomio xαes aα. ii) Si aα6=0, en onces aαxαse á un é mino del polinomio . iii) El g ado o al de 6=0 es el máximo |α| al que el coe icien e aαes no nulo. Lo deno a emos median e g ado( ). Ejemplo 1. Hola Sean los monomios −15x2y 3xy4. En onces el o den o al del p ime monomio es 2 y el o den o al del segundo monomio es 1+4=5. Sea aho a el polinomio =3xy4−15x2 o mado como combinación lineal de los dos monomios an e io es. En p ime luga , no a que es un polinomio en R[x,y]. • El coe icien e del monomio 3xy4es 3 y el coe icien e de −15x2es −15. • es á compues o po dos é minos: 3xy4y−15x2. •g ado( ) = 5 (ya que 1 +4=5>2). 1 8Capí ulo 2. Bases de G öbne Ejemplo 5. Veamos un ejemplo de cómo unciona es e algo i mo en Q[x,y]. Que emos di idi el po- linomio (x,y) = x3y+x2+2xy2+xy +x+yen e 1(x,y) = x2y+1 y 2(x,y) = xy usando el o den lexicog á ico x>y. Pa a comenza , conside amos q1=0,q2=0, =0,p= . Como LT ( 1) = x2ydi ide a LT (p) = x3yen onces podemos ac ualiza los alo es de q1yp ob eniendo q1=x, y p=x2+2xy2+xy +y. Sin emba go aho a, LT(p) = x2no es di idido po LT( 1) = x2yni po LT( 2) = xy. En onces el algo i mo nos indica que x2pasa a o ma pa e del es o de la di isión. Ac ualizando, ob enemos =x2, y p=2xy2+xy +y. Aho a, LT ( 2) = xy sí di ide a LT(p) = 2xy2y ob enemos los siguien es alo es ac ualizados: q2=2y, y p=xy +y. Como LT ( 2) = xy di ide a LT(p) = xy en onces ac ualizando enemos q2=2y+1, y p=y. Pa a inaliza , emos que ni LT ( 1) = x2yni LT ( 2) = xy di ide a LT(p) = yde modo que yes pa e del es o y así =x2+y. En es e caso enemos p=0, luego hemos e minado la di isión y el algo i mo inaliza. Recopilando odo, enemos: x3y+x2+2xy2+xy +x+y= (x)(x2y+1)+(2y+1)(xy)+(x2+y). Llegados a es e pun o podemos p egun a nos si los cocien es y el es o ob enidos pueden a ia dependiendo del cue po de polinomios en el que abajemos. Veamos con el siguien e ejemplo que e ec i amen e, el cue po es impo an e. Ejemplo 6. Tomamos los polinomios , 1, 2del Ejemplo 5 con la di e encia de que aho a odos ellos es án en el cue po ini o Z3[x,y]. Al aplica el algo i mo de la di isión y di idi en e 1y 2usando el o den lexicog á ico x>yse ob iene: x3y+x2+2xy2+xy +x+y= (x)(x2y+1)+(−y+1)(xy)+(x2+y). También podemos ob ene dis in os cocien es q1,...,qsy dis in o es o dependiendo de cómo es án o denados los di iso es 1,..., s. De modo que el Ejemplo 5 nos ayuda a en ende po qué el algo i - mo de la di isión en K[x1,...,xn]necesi a que = ( 1,..., s)sea una s- upla o denada de polinomios Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 9 usando un o den monomial y ambién nos ilus a que el es o no es á de e minado de mane a única: Si di idimos en e [ 1, 2]ob enemos q1=x,q2=2y+1, =x2+y( e Ejemplo 5), mien as que si di idimos en e [ 2, 1]ob enemos q1=x2+2y+1,q2=0, =x2+x+y. Recalca ambién que el algo i mo de la di isión depende ue emen e de la elección del o den mo- nomial, es deci , los cocien es y el es o pueden a ia dependiendo del o den monomial elegido. Vimos en el p ime capí ulo, al inal de la Sección 1.4, que una de las ca a e ís icas del algo i mo de la di isión en K[x]es esol e el p oblema de pe enencia al ideal, ob eniendo en onces que la condición =0 e a una condición su icien e y necesa ia pa a conclui que ∈ h 1,..., si. Aho a nos encon amos en la siguien e si uación, P oblema: P oblema de pe enencia al ideal en K[x1,...,xn]. Como hemos is o an e io men e, dado un polinomio ∈K[x1,...,xn], consis e en decidi si ∈I=h 1,..., si. ¿Se puede hace algo pa ecido al caso en una a iable? ¿Exis e algún algo i mo pa a esol e lo? Solución: Toda ía no podemos esol e lo, ya que aho a la condición =0 es una condición su icien e pe o no ne- cesa ia pa a a i ma que ∈ h 1,..., si. Pa a soluciona es e p oblema que emos encon a un conjun o gene ado del ideal, en el que el es o se de e mine de o ma única y en el que la condición =0 sea equi alen e a pe enece al ideal. Es e conjun o se á el que, pos e io men e, llama emos base de G öb- ne . Pa a llega has a allí, necesi amos in oduci p e iamen e los concep os y esul ados de la siguien e sección. 2.3. Ideales monomiales De inición 16. Un ideal I⊆K[x1,...,xn]se dice ideal monomial si exis e un subconjun o A⊆Zn ≥0 al que Ies á o mado po odos los polinomios de la o ma ∑ α∈A hαxαdonde hα∈K[x1,...,xn]. Lo deno a emos I=hxα|α∈Ai. Es deci , un ideal monomial se puede gene a po monomios pe o es o no quie e deci que odos los elemen os del ideal sean monomios. Veamos un ejemplo de ideal que es monomial, y o o que no. Ejemplo 7. I=hxy +y2,yx −y2ies un ideal monomial y sin emba go I0=hxy +y2,x−yino lo es. En e ec o: Llamamos 1=xy +y2y 2=yx −y2. En onces 1 2( 1+ 2) = xy ∈Iy1 2( 1− 2) = y2∈I. Luego podemos esc ibi hxy +y2,yx −y2i=hxy,y2i. De modo que Ies un ideal gene ado po monomios, así que Ies un ideal monomial. Llamamos 1=xy +y2y 2=x−y. En onces y 2+ 1=2xy ∈Iyy 2− 1=2y2∈I. Luego podemos esc ibi hxy +y2,x−yi=hxy,y2,x−yiy e así que I0no se puede gene a po monomios. Luego I0no es un ideal monomial. Lema 2.3. Sea I =hxα|α∈Aiun ideal monomial. En onces un monomio xβpe enece a I si y solo si xβes di isible po xαpa a algún α∈A. Lema 2.4. Sea I un ideal monomial y sea ∈K[x1,...,xn]. En onces las siguien es a i maciones son equi alen es: i) ∈I. 10 Capí ulo 2. Bases de G öbne ii) Todo é mino de es á en I. iii) es una combinación lineal en el cue po K de monomios de I. Colo a io 2.5. Dos ideales monomiales son iguales si y solo si con ienen los mismos monomios. A con inuación, se enuncia y demues a el Lema de Dickson ya que end á g an impo ancia en esul ados eó icos pos e io es. Teo ema 2.6 (Lema de Dickson).Todo ideal monomial I =hxα|α∈Aise puede esc ibi como I = hxα(1),...,xα(s)i, donde los en e os α(i)∈A,∀i=1,...,s. En pa icula , I iene una base ini a. Demos ación. P ocedamos po inducción sob e el núme o de a iables, n. ◦Sea n=1. En onces Ies á ini amen e gene ado en K[x1]po los monomios xα 1, donde α∈A⊆ Z≥0. Es o es po que omando β≤αcomo el meno elemen o de Aen onces xβ 1di ide a odo xα 1 y así, po el Lema 2.3, I=hxβ 1i. ◦Supongamos que es cie o pa a n−1 (con n>1) y eamos si se cumple el esul ado pa a n. Asumimos la siguien e no ación: esc ibi emos las a iables como x1,...,xn−1,yde modo que los monomios en K[x1,...,xn−1,y]se esc ibi án como xαymcon α∈Zn−1 ≥0,m∈Z≥0. Supongamos que I⊆K[x1,...,xn−1,y]es un ideal monomial. Pa a encon a los gene ado es de I, de inimos J⊆K[x1,...,xn−1]como un ideal gene ado po los monomios xα ales que xαym∈I pa a algún m≥0. Es deci , J=hxα∈K[x1,...,xn−1]|xαym∈I,m≥0i. Po se Jun ideal monomial en K[x1,...,xn−1], aplicando la hipó esis de inducción exis i á un núme o ini o de gene ado es de modo que enemos J=hxα(1),...,xα(s)i, con α(i)∈A. Pa a cada 1 ≤i≤s, po de inición de J, se cumple xα(i)ymi∈Ipa a algún mi≥0. Sea mel máximo de los mi. En onces pa a cada 0 ≤k≤m−1 conside amos Jk⊆K[x1,...,xn−1]como un ideal gene ado po los monomios xβ ales que xβyk∈I. Es deci , Jk=hxβ∈K[x1,...,xn−1]|xβyk∈I,0≤k≤m−1i. Aplicando de nue o la hipó esis de inducción enemos Jk=hxαk(1),...,xαk(sk)i, o equi alen emen- e, Jkes á gene ado po un núme o ini o de monomios. Veamos que Ies á gene ado po los siguien es monomios: p oceden es de J:xα(1)ym,...,xα(s)ym p oceden es de J0:xα0(1),...,xα0(s0) p oceden es de J1:xα1(1)y,...,xα1(s1)y . . . p oceden es de Jm−1:xαm−1(1)ym−1,...,xαm−1(sm−1)ym−1. Tenemos que cada monomio de Ies di isible po alguno de la lis a an e io . En e ec o, omamos xαyp∈I: - Si p≥men onces xαypes di isible po algún xα(i)ymdebido a la cons ucción de J. - Si p≤m−1 en onces xαypes di isible po algún xαp(j)ypdebido a la cons ucción de Jp. Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 11 Así que po el Lema 2.3 enemos que la lis a an e io de monomios gene a un ideal con los mismos monomios que I, y po el Co ola io 2.5 se iene que ambos ideales son el mismo. Po úl imo, eamos que el conjun o ini o de gene ado es se puede escoge de los gene ado es del ideal. Deno ando aho a las a iables como x1,...,xn, en onces I=hxα|α∈Aies nues o ideal monomial. Que emos e que Ies á gene ado po un núme o ini o de xα’s, con α∈A. Hemos is o que I=hxβ(1),...,xβ(s)ipa a cie os monomios xβ(i)∈I,i=1,...,s. Como xβ(i)∈I, po el Lema 2.3 se iene que cada xβ(i)es di isible po xα(i),α(i)∈A. Po doble con enido se e ácilmen e que I=hxα(1),...,xα(s)icomple ando así la demos ación. Una de las consecuencias del Lema de Dickson es que dadas las dos p ime as condiciones de la De inición 11, la condición iii) iene un equi alen e. Veámoslo: Colo a io 2.7. Sea >una elación de o den en Zn ≥0cumpliendo: i) >es un o den o al en Zn ≥0. ii) Si α>β,γ∈Zn ≥0en onces α+γ>β+γ. En onces >es un buen o den si y solo si α≥0pa a odo α∈Zn ≥0. 2.4. El Teo ema de las bases de Hilbe y bases de G öbne En es a sección se da án esul ados eó icos los cuales se i án pa a da una solución al p oblema de la desc ipción del ideal explicado al p incipio de es e capí ulo. La idea p incipal es que dado un o den monomial, odo polinomio no nulo iene un único é mino p incipal. En onces pa a cualquie ideal I podemos de ini su ideal de é minos p incipales de la siguien e mane a. De inición 17. Sea I⊆K[x1,...,xn]un ideal dis in o del nulo. En onces, una ez ijado un o den mo- nomial en K[x1,...,xn]: i) Deno a emos median e LT (I)al conjun o de odos los é minos p incipales de odos los elemen os de Ique sean no nulos. Es deci , LT (I) = {cxα|exis e ∈I {0} al que LT( ) = cxα}. ii) Deno a emos median e hLT (I)ial ideal gene ado po los elemen os del conjun o LT(I). P oposición 2.8. Sea I ⊆K[x1,...,xn]un ideal dis in o del nulo, en onces i) hLT (I)ies un ideal monomial. ii) Exis en g1,...,g ∈I ales que se cumple la igualdad hLT(I)i=hLT(g1),...,LT(g )i. Pa a p oba el siguien e esul ado, ha emos uso de la P oposición 2.8 y del Teo ema 2.2 (algo i mo de la di isión), dando así una espues a a i ma i a al p oblema de la desc ipción del ideal explicado al p incipio de es e capí ulo. Teo ema 2.9 (Teo ema de las bases de Hilbe ).Todo ideal I ⊆K[x1,...,xn]es á ini amen e gene ado. En o as palab as, I =hg1,...,g icon g1,...,g ∈I. Demos ación. Hola ◦Si I={0}, como {0}es un gene ado de Iy es un conjun o ini o en onces se iene el esul ado. 12 Capí ulo 2. Bases de G öbne ◦Si I6={0}, en onces un conjun o gene ado g1,...,g de Ise puede cons ui de la siguien e mane a: Como I iene un ideal de é minos p incipales, po la P oposición 2.8 exis en g1,...,g ∈I ales que hLT (I)i=hLT(g1),...,LT (g )i. Comp obemos aho a que, e ec i amen e, I=hg1,...,g i. Pa a ello, p ocedamos po doble con enido: - Dado que odo gi∈I, es cla o que hg1,...,g i ⊆ I. - Sea ∈Iun polinomio cualquie a. Fijado un o den monomial, se aplica el algo i mo de la di isión en a ias a iables pa a di idi po [g1,...,g ]y ob enemos =q1g1+···+q g + donde ningún é mino de es di isible po ningún LT(gi),i=1,..., . Veamos que =0. Pa a ello p ocedamos po educción al absu do suponiendo 6=0 . En al caso LT ( )∈ hLT (I)i=hLT(g1),...,LT (g )i(ya que = −q1g1− ··· − q g ∈I) y po el Lema 2.3 se iene que LT ( )debe se di isible po algún LT (gi),i=1,..., . Como es o con adice la a i mación an e io de que ningún é mino de es di isible po ningún LT(gi), se iene =0. Po lo an o =q1g1+···+q g +0∈ hg1,...,g i, comple ando así la demos ación del segundo con enido I⊆ hg1,...,g i. Luego, po doble con enido, I=hg1,...,g i. De inición 18. Dado un o den monomial, un subconjun o ini o G={g1,...,g }de un ideal I⊆ K[x1,...,xn]se di á base de G öbne si hLT (g1),...,LT(g )i=hLT(I)i. De una mane a menos o mal, un conjun o {g1,...,g } ⊆ Ies una base de G öbne de Isi y solo si el é mino p incipal de cada elemen o de Ies di isible po alguno de los LT (gi), pa a i=1,..., . Hola Po con enio se iene h/0i={0}. De inimos en onces el conjun o acío /0 como la base de G öbne del ideal nulo {0}. Colo a io 2.10. Dado un o den monomial, odo ideal I ⊆K[x1,...,xn] iene una base de G öbne . Es más, cualquie base de G öbne de un ideal I es una base de I. Veamos una consecuencia geomé ica del Teo ema 2.9 bas an e impo an e, ya que luego nos pe - mi i á esol e sis emas de ecuaciones en a ias a iables de una o ma sencilla. De inición 19. Sea I⊆K[x1,...,xn]un ideal. Deno a emos median e V(I)al conjun o V(I) = {(a1,...,an)∈Kn| (a1,...,an) = 0,∀ ∈I)}. P oposición 2.11. El conjun o V(I)es una a iedad a ín. En pa icula , si I =h 1,..., si, en onces V(I) = V( 1,..., s). A con inuación, eamos que, al aplica el algo i mo de la di isión en a ias a iables, el es o de la di isión es único cuando los di iso es o man una base de G öbne . P oposición 2.12. Fijado un o den monomial, sea G ={g1,...,g }una base de G öbne del ideal I⊆K[x1,...,xn]y sea ∈K[x1,...,xn]. En onces exis e un es o único ∈K[x1,...,xn]que cumple las dos siguien es p opiedades: i) Ningún é mino de es di isible po LT(gi), pa a i =1,..., . ii) Exis e g ∈I al que =g+ . En pa icula , es el es o de la di isión de en e G sin impo a el o den de los elemen os de G. Colo a io 2.13. Sea G ={g1,...,g }una base de G öbne del ideal I ⊆K[x1,...,xn]y sea ∈ K[x1,...,xn]. En onces ∈I si y solo si el es o de la di isión de en e G es ce o. Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 13 2.5. C i e io y algo i mo de Buchbe ge A pa i de aho a esc ibi emos ¯ Fpa a deno a el es o de la di isión del polinomio en e la s- upla o denada F= ( 1,..., s). Si Fes una base de G öbne pa a el ideal h 1,..., sien onces la s- upla F no es necesa io que es é o denada. Ejemplo 8. Di idiendo =x4y2po F= (xy −1,y2−1)⊆K[x,y], u ilizando el o den lexicog á ico (x>y), ob enemos x4y2F=x2 ya que median e el algo i mo de la di isión se iene x4y2= (x3y+x2)·(xy −1)+(0)·(y2−1)+x2. A con inuación, e emos el c i e io de Buchbe ge , el cual nos ayuda á a sabe si el gene ado de un ideal dado es una base G öbne o no. Pa a ello necesi amos in oduci p e iamen e dos de iniciones. De inición 20. Sean ,g∈K[x1,...,xn]polinomios no nulos. Si mul ig ado( ) = αymul ig ado(g) = β, sea γ= (γ1,...,γn)donde γi=max(αi,βi)pa a cada i=1,...,n. Llama emos xγal mínimo común múl iplo de LM( )yLM(g), es deci , xγ=mcm(LM( ),LM(g)). De inición 21. Sean ,g∈K[x1,...,xn]polinomios no nulos. De inimos el S-polinomio de ygcomo S( ,g) = xγ LT ( )· −xγ LT (g)·g. Aho a ya sí podemos enuncia el siguien e esul ado, el cual como ya hemos explicado, si e pa a sabe cuándo una base de un ideal es una base de G öbne . Teo ema 2.14 (C i e io de Buchbe ge ).Sea I un ideal de polinomios. En onces una base G ={g1,...,g } de I es una base de G öbne de I ⇔S(gi,gj)G=0,∀i,j ales que i 6=j. Demos ación. Ve [5, Capí ulo 2, Sección 6]. Ejemplo 9. Sea I=hx2−y2+z,z−1i. Veamos que G={x2−y2+z,z−1}es una base de G öbne pa a Iu ilizando el o den lexicog á ico habi ual (x>y>z). Deno amos g1=x2−y2+zy ambién g2=z−1. En onces LT(g1) = x2,LT(g2) = zyxγ=x2z(ya que mul ig ado(g1) = (2,0,0)ymul ig ado(g2) = (0,0,1)). De es e modo S(g1,g2) = x2z x2·g1−x2z z·g2=x2−y2z+z2. Aho a, aplicando el algo i mo de la di isión ob enemos x2−y2z+z2= (1)(−x2−y2+z)+(−y2+z)(z−1)+0. Po lo an o S(g1,g2)G=0. Así que po el c i e io de Buchbe ge se iene que Ges una base de G öbne pa a I. Ya hemos is o en el Co ola io 2.10 que odo ideal iene una base de G öbne . Además, g acias al Teo ema 2.14 (c i e io de Buchbe ge ) ya sabemos e si una base dada es una base de G öbne o no. Pe o dado un ideal I⊆K[x1,...,xn], ¿podemos cons ui noso os una base de G öbne pa a I? La espues a a es o es que sí. Pa a ello u iliza emos el siguien e algo i mo. Teo ema 2.15 (Algo i mo de Buchbe ge ).Sea I =h 1,..., si 6={0}un ideal de polinomios. En onces podemos cons ui una base de G öbne G ={g1,...,g }de I en un núme o ini o de pasos u ilizando el siguien e algo i mo: 14 Capí ulo 2. Bases de G öbne Po lo an o, usando el c i e io de Buchbe ge y el algo i mo de Buchbe ge hemos conseguido un mé odo pa a ob ene bases de G öbne . Pe o es as bases, habi ualmen e ienen más elemen os de los necesa ios. Veamos que podemos elimina alguno u ilizando el siguien e lema. Lema 2.16. Sea G una base de G öbne de I ⊆K[x1,...,xn]y sea p ∈G un polinomio al que LT (p)∈ hLT (G {p})i. En onces G {p}es ambién una base de G öbne de I. Ejemplo 10. Conside amos el anillo de polinomios Q[x,y,z]con el o den lexicog á ico habi ual (x>y>z) y sea I=h 1, 2i=hx2+y,x3+zi. Lo p ime o es e que F={ 1, 2}no es una base de G öbne : Como LT (S( 1, 2)) = xy /∈ hLT ( 1),LT ( 2)i=hx2,x3i, en onces el c i e io de Buchbe ge nos ga an- iza que Fno es una base de G öbne de I. Vamos a cons ui una base de G öbne , a pa i de F, u ilizando el algo i mo de Buchbe ge . Iniciamos el algo i mo y así G0=F. Aho a, di idiendo S( 1, 2) = xy −zpo Fob enemos como es o 3=xy−z, el cual es no nulo. Po lo an o debemos ac ualiza nues a base G0={ 1, 2, 3}. En onces, S( 1, 2)G0 =S( 2, 3)G0 =0, S( 1, 3)G0 =xz +y26=0. Po lo an o, añadiendo 4=xz +y2,G0={ 1, 2, 3, 4}. Aho a, S( 1, 2)G0 =S( 1, 3)G0 =S( 1, 4)G0 =S( 2, 3)G0 =0, S( 3, 4)G0 =−y3−z26=0. Así que enemos una nue a G0={ 1, 2, 3, 4, 5}, siendo 5=−y3−z2, pa a la cual se cumple S( i, j)G0 =0,∀1≤i<j≤5. Así, po el c i e io de Buchbe ge enemos que G={ 1, 2, 3, 4, 5}es una base de G öbne de Icon espec o al o den lexicog á ico. No a aho a que LT( 2) = x·LT( 1). Así que po el Lema 2.16 podemos p escindi de 2en nues a nue a base de G öbne . Como no hay más casos en los que el é mino p incipal de un gene ado di ida al é mino p incipal de o o gene ado , en onces la mínima base de G öbne que podemos ob ene es: G={ 1, 3, 4, 5}. De inición 22. Una base de G öbne minimal de un ideal de polinomios I⊆K[x1,...,xn]es una base de G öbne Gde Ila cual cumple: i) ∀p∈G,LC(p) = 1. Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 15 ii) ∀p∈G,LT (p)/∈ hLT(G {p})i. Desa o unadamen e el ideal Iinicial puede ene a ias bases de G öbne minimales, ya que po ejemplo omando ˜ 1=x2+y+az con a∈Q ambién se ía G={˜ 1, 3, 4, 5}una base de G öbne minimal. Pe o a o unadamen e hay una base minimal que es mejo que el es o. Su de inición es la siguien e. De inición 23. Una base de G öbne educida de un ideal de polinomios I⊆K[x1,...,xn]es una base de G öbne Gde Ila cual cumple: i) ∀p∈G,LC(p) = 1. ii) ∀p∈G, ningún monomio de pes á en hLT(G {p})i. Teo ema 2.17. Sea I un ideal de polinomios no nulo. En onces, pa a un o den monomial dado, I iene una única base de G öbne educida. Demos ación. In oduzcamos la siguien e de inición: Di emos que g∈G,Gbase de G öbne minimal de I, es un elemen o educido espec o de Gsi ningún monomio de gpe enece a hLT(G) {p}i con p∈G. No a que si ges un elemen o educido espec o de Gen onces g ambién es educido espec o cualquie o a base de G öbne minimal de Ique con enga a gy que enga los mismos é minos p inci- pales. El obje i o pa a e la exis encia de una base de G öbne educida es pa i de una base de G öbne minimal Gy modi ica la has a que odos sus elemen os sean elemen os educidos. Dado g∈Gun elemen o educido espec o de G, omamos g0=gG {g}yG0= (G {g})∪{g0}. Vea- mos que G0es una base de G öbne minimal de I. Pa a ello no a que LT (g0) = LT(g)ya que al di idi gen e G {g}, necesa iamen e LT (g)pasa a o ma pa e del es o po que no es di isible po ningún elemen o de LT (G {g}). Así enemos que hLT(g0)i=hLT (g)i. Como cla amen e G0⊆I enemos que G0es una base de G öbne minimal de I. Además, g0es un elemen o educido de G0po cons ucción. Aho a omamos los elemen os de Gy aplicamos el p ocedimien o an e io has a que odo elemen o sea educido, ob eniendo así una base de G öbne educida. Queda po p oba la unicidad de es a base de G öbne educida, la cual acabamos de e que exis e. Sean Gy˜ Gdos bases de G öbne educidas de I. En pa icula Gy˜ Gson ambién bases de G öbne mi- nimales de I, luego LT (G) = LT (˜ G). En onces dado g∈G, exis i á un ˜g∈˜ G al que LT (g) = LT(˜g). Así que si p obamos g=˜gen onces G=˜ Gy la unicidad es a á p obada. Pa a e que g=˜g, conside emos el polinomio g−˜g, el cual es á en I. Como Ges una base de G öbne se sigue que g−˜gG=0. También, como LT (g) = LT(˜g)en onces ambos se cancelan al e ec ua la es a g−˜gy el es o de é minos no son di isibles po ninguno de los LT (g) = LT(˜g)ya que Gy˜ Gson bases de G öbne educidas. Se sigue que g−˜gG=g−˜gy po lo an e io g−˜g=0, luego g=˜gcomple ando así la demos ación. El siguien e esul ado, a pesa de es a ca ego izado como co ola io end á g an ele ancia en los dos capí ulos pos e io es. Tene en cuen a que un cue po Kse dice algeb aicamen e ce ado si cada polinomio de g ado al menos 1, con coe icien es en K, iene un ce o en K. Colo a io 2.18. Sea K un cue po algeb aicamen e ce ado. Dado un ideal I ⊆K[x1,...,xn]y dada G una base de G öbne educida de I en onces V(I) = /0 si y solo si G ={1}. 2.6. Aplicaciones de las bases de G öbne En es a sección amos a esol e , u ilizando las bases de G öbne , los p oblemas sob e ideales y a iedades enume ados y b e emen e explicados al p incipio de es e segundo capí ulo. 16 Capí ulo 2. Bases de G öbne 1. P oblema de la desc ipción del ideal. Ya se explicó que es e p oblema consis e en sabe si los ideales I⊆K[x1,...,xn]es án o mados po un conjun o ini o. Lo esol imos u ilizando el Teo ema 2.9, ya que es e esul ado a i ma que odo ideal es á ini amen e gene ado. 2. P oblema de pe enencia al ideal. Dado un ideal I=h 1,..., si ⊆ K[x1,...,xn]podemos sabe si un polinomo pe enece a Ide la siguien e mane a: - Encon a una base de G öbne G={g1,...,g }de Iu ilizando el Teo ema 2.15 (algo i mo de Buchbe ge ). - Po el Co ola io 2.13 podemos a i ma que ∈I⇔ G=0. 3. P oblema de esolución de un sis ema de ecuaciones. Veamos cómo podemos aplica las bases de G öbne pa a esol e sis emas de ecuaciones en a ias a iables: - Si encon amos una base de G öbne de un ideal, con espec o al o den lexicog á ico, la o ma de las ecuaciones se simpli ica bas an e, ya que las a iables se an eliminando suce- si amen e. Un sis ema de ecuaciones de es a o ma es mucho más ácil de esol e . - Po la P oposición 2.11, la cual dice que las a iedades a ines es án de e minadas po ideales, se iene que las soluciones ob enidas con el p ocedimien o an e io , son odas las que exis en. 4. P oblema de implici ación en ideales. El p oblema de encon a un sis ema de ecuaciones cuyas soluciones sean los pun os de una a iedad puede esol e se u ilizando nue amen e las bases de G öbne . Veamos cómo: - Conside amos las ecuaciones pa amé icas x1= 1( 1,..., m), . . . xn= n( 1,..., m), las cuales de inen un subconjun o de una a iedad V⊆Kn. Nos cen amos en el caso de que isean ealmen e polinomios. Conside amos la siguien e a iedad a ín en Km+n x1− 1( 1,..., m) = 0, . . . xn− n( 1,..., m) = 0. La idea es elimina las a iables 1,..., mde esas ecuaciones. Pa a ello enemos que ob ene una base de G öbne . - Supongamos que hemos ob enido una base de G öbne pa a el ideal I=hx1− 1,...,xn− ni con espec o al o den lexicog á ico ( 1>··· > m>x1>··· >xn). En onces los polinomios de la base de G öbne que solo in oluc an las a iables x1,...,xnson las soluciones del sis ema de ecuaciones. Capí ulo 3 Colo eado de g a os En es e capí ulo amos a de ini el concep o de g a o simple, al cual llama emos g a o, y e emos cómo aplica las bases de G öbne a la Teo ía de g a os, en pa icula da emos una solución al p oblema del k-colo eado en un g a o. De inición 24. Un g a o Ges un pa G= (V,E), donde Ves un conjun o ini o de pun os, llamados é ices, y Ees un conjun o de pa es no o denados de é ices, llamadas a is as del g a o. Además di emos que dos é ices son adyacen es si ambos son ex emos de la misma a is a. De inición 25. Un camino en e dos é ices u1yu es una sucesión de a is as de la o ma {u1,u2},{u2,u3},...,{u −1,u }que une los é ices u1yu . De inición 26. Sea G= (V,E)un g a o. Se dice que Ges un g a o conexo si pa a odo pa u, ∈V siemp e exis e un camino que une uy . De inición 27. Sea Gun g a o conexo con é ices V={1,...,n}y a is as E={1,...,m}. Sea Cun conjun o ini o cuyos elemen os llama emos colo es. Una colo ación de Ges una co espondencia al que a cada uno de los é ices de Gse le asigna un colo de Cde mane a que dos é ices adyacen es no pueden ecibi el mismo colo . Fo malmen e, una colo ación de Ges una aplicación γ:V−→ C al que γ(u)6=γ( )si exis e una a is a de Gque une uy . El alo de γ(u)es el colo que ecibe el é ice uen la colo ación γ. De inición 28. Una colo ación de un g a o Gcon kcolo es (k≥1) se llama k-colo ación de G. De inición 29. Di emos que un g a o Ges k-colo eable si exis e una k-colo ación asignada. Obse a que si Ges k-colo eable inmedia amen e se iene que Ges ambién (k+1)-colo eable. No a ambién que si nes el núme o de é ices en onces Ges n-colo eable. De inición 30. El núme o c omá ico de un g a o Gse de ine como el mínimo alo k∈N al que Ges k-colo eable y se deno a po χ(G). Si k=χ(G)se dice que el g a o es k-c omá ico. Ejemplo 11. Sea Gun g a o conexo o mado po 5 é ices, luego V={1,2,3,4,5}, y po 4 a is as, luego E={{1,3},{2,4},{3,4},{3,5}}.Es e g a o es cla amen e 5-colo eable ya que iene 5 é ices. Sin emba go, χ(G) = 2 y así Ges 2-colo eable. 17 24 Capí ulo 4. Sudokus y bases de G öbne Figu a 4.4 4.1.2. Resolución Sudokus Aho a que hemos en endido cómo esol e los Shidokus, podemos aumen a el amaño de ny se- gui los mismos pasos pa a consegui el obje i o de es e capí ulo: esol e los Sudokus u ilizando el p oblema del 9-colo eado y las bases de G öbne . Con inuamos con el puzle Sudoku del Ejemplo 13, el cual que emos esol e . Reco da que ya ha- bíamos hallado los polinomios co espondien es a las condiciones iniciales (los cuales gene an L) de modo que solo al a cons ui el ideal I=J+Ly ob ene su base de G öbne G. De es e modo, siguien- do los mismos pasos que pa a los Shidokus y u ilizando SageMa h, se iene que la solución es: Figu a 4.5 Desa o unadamen e, los sis emas de ecuaciones polinómicas que esuel en los Sudokus no son muy “amigables” ya que el núme o de ecuaciones es bas an e ele ado. A pesa de que exis en unciones, ya incluidas en los paque es de la mayo ía de los lenguajes de p og amación, pa a esol e dichos sis emas, p oduci el sis ema de ecuaciones y aplica las bases de G öbne no es un buen mé odo en gene al. Sin emba go, es e en oque iene algunas en ajas como po ejemplo ob ene odas las posibles soluciones al y como se ha is o en el Ejemplo 15. 4.1.3. Gene alización n×n Al p incipio de es e capí ulo hemos de inido que un Sudoku es á o mado po una cuad ícula 9 ×9 y ambién hemos is o que se puede educi ndando así luga a los Shidokus. En onces, iene su lógica p egun a nos ¿npuede se cualquie núme o na u al, excep uando el 0? Y e ec i amen e la espues a a es o es a i ma i a, podemos elegi n. La esolución de es os Sudokus amaño n×nes simplemen e una gene alización de lo es udiado con an e io idad. Es deci , pa a esol e lo enemos que calcula la base de G öbne educida del ideal I=J+L o mado po : - El ideal J o mado po los polinomios ygde inidos como (xi) = n ∏ k=1 (xi−ck), g(xi,xj) = (xi)− (xj) xi−xj =0,siendo 0 ≤i<j≤n2−1. - El ideal L=hxi−cki,siendo 0 ≤i≤n2−1,1≤k≤n. Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 25 De es e modo, una ez que enemos la base de G öbne educida G, po la P oposición 4.1 end emos la solución pa a cualquie Sudoku de amaño n×n. 4.2. Conje u as ma emá icas A con inuación, amos a da algunas conje u as ma emá icas, es deci , algunas a i maciones apa en- emen e e dade as, ya que se han hecho p uebas con i mando su e acidad, pe o no hay demos ación ma emá ica de ellas. •Uno de los emas que podemos cues iona nos es ¿cuán os posibles Shidokus y Sudokus dis in os hay, igno ándose las elaciones de sime ía en e soluciones simila es? Tal y como se explica en [11], exis en 288 able os de Shidokus. Sin emba go, al in en a con a cuán os Sudokus exis en, el núme o de posibilidades es mayo y el cos e compu acional aumen a. En [11] se explica el camino que se ha seguido pa a ob ene una buena ap oximación al núme o o al de able os de Sudokus álidos, siendo es e núme o 6,6571 ·1021. •Uno de los p oblemas elacionados con el Sudoku que más ha in e esado a los ma emá icos, po habe es ado mucho iempo sin espues a, es el del núme o mínimo de pis as que puede ene un Sudoku pa a esol e lo de mane a única. Se ha conseguido encon a mul i ud de puzles de 17 pis as con solución única pe o ninguno con solo 16 [11]. Es e p oblema, denominado “P oblema del Sudoku mínimo” ue esuel o en 2012 con la ayuda de un o denado e aluando odos, sal o equi alencias, los cuad ados de Sudokus en busca de algún puzle de 16 pis as. Los a í ices de es a demos ación son Ga y McGui e, Bas ian Tugemann y Gilles Ci a io. En el caso de los Shidokus, es e núme o mínimo es 4, como se menciona en [11]. •Sin emba go, ni odos los Sudokus con 17 pis as, ni odos los Shidokus con 4 pis as ( éase el Ejemplo 15), ienen solución única. Es o nos lle a a p egun a nos, ¿cuál es el núme o máximo de pis as que puede habe en una cuad ícula y aún no ene solución única? En la página 26 de [11] se obse a un puzle Sudoku con 77 pis as y sin solución única. De modo que 77 es el máximo núme o de pis as pa a el cual un Sudoku no iene solución única. Además se conje u a que pa a cualquie o a a ian e de los Sudokus, de amaño n×n, es e núme o máximo es n2−4. •La di icul ad en los Sudokus se c ee que depende del núme o de pis as iniciales. Pe o, so p en- den emen e, es a di icul ad se basa en la posición de las pis as. Es a es la azón po la que la dis ibución de las pis as dis ingue un Sudoku ácil de o o di ícil. En la página 122 de [3] se mues a un Sudoku con 20 pis as de mínima di icul ad y o o con 28 pis as de di icul ad máxima. •Una medida más e inada de la di icul ad se hace a pa i del es udio de las écnicas de esolución de Sudokus, como se mues a en [3]. Algunos mé odos son más simples que o os, po lo que se puede conje u a que si un Sudoku equie e un azonamien o más complejo pa a esol e lo, se le asocia una di icul ad mayo . Sin emba go, es ima la di icul ad de un Sudoku no es, ni mucho menos, una ciencia exac a, debido a la eno me ca ga de subje i idad que ello conlle a. 4.3. Conclusión A modo de conclusión, señala la impo ancia que albe ga es a aplicación de las bases de G öbne , ya que hemos conseguido uni concep os geomé icos y algeb aicos. Pa a una modelización geomé ica de los Sudokus hemos es udiado un p oblema undamen al de la Teo ía de g a os el cual a a de colo ea un g a o con kcolo es. De es e modo, hemos sido capaces de con igu a ma emá icamen e un Sudoku como si uese un g a o con an os é ices como celdas. Además, hemos esuel o sis emas de ecuaciones no lineales u ilizando así la pa e eó ica es udiada en el Capí ulo 2, la cual hace e e encia a un es udio en el ma co algeb aico. Po lo an o, a pesa de que apa en emen e el Sudoku es un juego sencillo de pu a lógica, el es udio ealizado en es e capí ulo mues a un as ondo cla amen e ma emá ico, an o en su plan eamien o como en su esolución. Apéndice A Códigos SageMa h Es a pa e inal es á des inada a mos a odos los códigos esc i os en SageMa h que se han u ilizado pa a la esolución de a ios ejemplos a lo la go del p esen e abajo. •Algo i mo de la di isión en a ias a iables. - Las a iables de en ada son ( ,G,A)donde es un polinomio, Ges una lis a de polinomios yAes un anillo de polinomios. - Las a iables de salida son (Q,A( )) donde Qes una lis a de polinomios, que se co espon- den con los cocien es, y A( )es el es o de la di isión. d e d i ( , G, A ) : s = l e n (G) p = A( ) Q = s *[0] = 0 w hi le p != 0 : i = 0 d i i s i o n = a l s e wh il e i < s and d i i s i o n == F a l s e : i G[ i ] . l ( ) . d i i d e s ( p . l ( ) ) : Q[ i ] = Q[ i ] + p . l ( ) / / G[ i ] . l ( ) p = p − ( p . l ( ) / / G[ i ] . l ( ) ) *G[ i ] d i i s i o n = T ue else : i=i+1 i d i i s i o n == F a l s e : = + p . l ( ) p = p − p . l ( ) e u n Q, A( ) •S-polinomio. - Las a iables de en ada son ( ,g,A)donde ygson dos polinomios y Aes un anillo de polinomios. - La a iable de salida es s, co espondien e al S-polinomio buscado. d e S_ po li no mio ( , g , A ) : a = A( ) . lm ( ) b = A( g ) . lm ( ) 27 28 Capí ulo A. Códigos SageMa h c = lcm ( a , b ) s = A( ( c / a )* −( c / b ) *g ) e u n s •Algo i mo de Buchbe ge . - Las a iables de en ada son (F,A)donde Fes una lis a de polinomios y Aes un anillo de polinomios. - La a iable de salida es G, la cual es una lis a de polinomios (es os polinomios son los que o man la base de G öbne ). d e Buch ( F , A ) : n= l e n ( F ) G=F o i i n [ 0 . . n − 2 ] : o j i n [ i + 1 . . n − 1 ] : s= S_polinomio (G[ i ] ,G[ j ] ,A) d= d i ( s , G,A) [ 1 ] i d ! = 0 : e u n Buch ( F+[ d ] ,A) e u n G •Resolución del p oblema del colo eado. - Las a iables de en ada son (G,k)donde Ges un g a o y kes el núme o de colo es. - Las a iables de salida son ( +g,A)donde +qson las ecuaciones de nues o sis ema y Aes el anillo de polinomios. de s i s e m a (G, k ) : n = G. num_ e s ( ) xs = l i s ( a ( ’ x_ % d ’ % i ) o i i n a ng e ( n ) ) F = QQ A = Polyn omi alR ing ( F , xs , o d e = ’ lex ’ ) c o l o e s = a n g e ( k ) = [ ] o j i n xs : = + [A( p od ( [ ( j − i ) o i i n c o l o e s ] ) ) ] g = [ ] a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n G. edges ( ) ] o j i n a i s a s : 1 = [A( p od ( [ ( xs [ j [ 0] ] − i ) o i i n c o l o e s ] ) ) , A( p od ( [ ( xs [ j [ 1] ] − i ) o i i n c o l o e s ] ) ) ] g = g + [A( ( 1 [0] − 1 [ 1 ] ) / ( xs [ j [ 0] ] − xs [ j [ 1 ] ] ) ) ] e u n + g , A Obse ación 2. Pa a de ini el anillo de polinomios en el que que emos abaja , se puede especi- ica cualquie a de los ó denes monomiales explicados en el Capí ulo 2, simplemen e esc ibiendo lo siguien e: ◦O den lexicog á ico: o de = ’lex’ ◦O den lexicog á ico g aduado: o de = ’deglex’ ◦O den lexicog á ico g aduado in e so: o de = ’deg e lex’ Bases de G öbne y su aplicación a los sudokus - Bá ba a Zapa e Za oca 29 •C eación de un able o Sudoku, de amaño n×n, sin pis as. Pa a ello, se han enido que c ea dos unciones. P e iamen e es con enien e explica que a amos el Sudoku como si ue a una ma iz, de modo que la celda xkco esponde al elemen o (i,j)con i,j=0,...,n2−1. Po ejemplo, en un Sudoku 9 ×9 la celda x13 co esponde al elemen o (1,4). 1. A a és de es a unción cada celda del Sudoku se con ie e en un elemen o ma icial de la o ma (i,j). - Las a iables de en ada son (i,j,n)donde ico esponde al p ime elemen o del pa (i,j),jco esponde al segundo elemen o del pa (i,j)ynhace e e encia al amaño. - La a iable de salida es el subíndice de la celda xk. # Pa a un Sudoku 9x9 , s e oma n=3 de c o n e i ( i , j , n ) : e u n ZZ( i *n+ j ) 2. Median e es a unción imponemos las elaciones de adyacencia, de modo que no se epi an los dígi os en ninguna de las egiones. - La a iable de en ada es nque hace e e encia an o al núme o de ilas como al núme o de columnas. - La a iable de salida es la lis a de odas las a is as Ecumpliendo las elaciones impues- as. # Pa a un Sudoku 9x9 , s e oma n=9 de eqs_sudoku ( n ) : R = I n e g e s ( 3 ) E = [ ] # P a es ( i , j ) ( i , k ) a l e s que x_ ( i , j ) y x_ ( i , k ) p e e n e c e n a l a misma i l a # P a es ( j , i ) ( k , i ) a l e s que x_ ( j , i ) y x_ ( k , i ) p e e n e c e n a l a misma i l a o i i n a ng e ( n ^ 2 ) : o j i n a ng e ( n ^ 2 ) : o k i n [ j + 1 . . n ^2 −1]: a= c o n e i ( i , j , n ^2) b= c o n e i ( i , k , n ^2) i ( no [ a , b ] i n E) and ( no [ b , a ] i n E ) : E = [ [ a , b ] ] + E a= c o n e i ( j , i , n ^2) b= c o n e i ( k , i , n ^2) i ( no [ a , b ] i n E) and ( no [ b , a ] i n E ) : E = [ [ a , b ] ] + E # P a e s ( i 1 *i2 , j 1 *j 2 ) ( i 1 *i3 , j 1 *j 3 ) a l e s que x_ ( i 1 *i2 , j 1 *j 2 ) y x_ ( i 1 *i3 , j 1 *j3) pe enecen a l mismo bloq ue n x n o i 1 i n an ge ( n ) : o j 1 i n an ge ( n ) : o i 2 i n an ge ( n ) : o j 2 i n an ge ( n ) : o i 3 i n an ge ( n ) : o j 3 i n an ge ( n ) : a=con e i (i1*n+ i2 , j 1 *n+ j2 , n ^2 ) 30 Capí ulo A. Códigos SageMa h b=con e i (i1*n+ i3 , j 1 *n+j3 , n ^2) i a <b and ( n o [ a , b ] i n E) and ( n o [ b , a ] i n E ) : E=E + [ [ a , b ] ] e u n E Obse ación 3. Si quisié amos esol e un Sudoku de amaño 9 ×9 con pis as iniciales dadas end ía- mos que segui los siguien es pasos: ◦P ime o, aplica el código c eado pa a la esolución del p oblema del colo eado pe o cambiando alguno de los da os. de s i s e m a (G, k ) −−−−−> de s i s e m a ( E , k ) n = G. num_ e s ( ) −−−−−> n = 81 a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n G. edges ( ) ] −−−−−> a i s a s = [ [ _ [ 0 ] , _ [ 1 ] ] o _ i n E] Siendo E la lis a de odas las a is as ob enida an e io men e. ◦Una ez hayado el sis ema, conside amos el ideal gene ado po las soluciones del sis ema. ◦Conside amos ambién el ideal gene ado po los polinomios esul an es de las pis as dadas. ◦Po úl imo sumamos ambos ideales y ob enemos su base de G öbne co espondien e u ilizando la unción I.g oebne _basis(). Bibliog a ía [1] W. W. Adams and P. Lous aunau. An in oduc ion o G öbne bases, olume 3 o G adua e S udies in Ma hema ics. Ame ican Ma hema ical Socie y, P o idence, RI, 1994. [2] D. A. Baye . The di ision algo i hm and he Hilbe scheme. P oQues LLC, Ann A bo , MI, 1982. Thesis (Ph.D.)–Ha a d Uni e si y. [3] A. Bece a Tomé, J. Núñez Valdés, and J. M. Pe ea González. ¿Cuán a Ma emá ica hay en los sudokus? Pensamien o Ma emá ico, 6(1):113–136, 2016. [4] S. Benne . Applica ions o G öbne bases. 2008. [5] D. A. Cox, J. Li le, and D. O’Shea. Ideals, a ie ies, and algo i hms. Unde g adua e Tex s in Ma hema ics. Sp inge , Cham, ou h edi ion, 2015. An in oduc ion o compu a ional algeb aic geome y and commu a i e algeb a. [6] Wol am Decke , Ge -Ma in G euel, Ge ha d P is e , and Hans Schönemann. SINGULAR 4-2-0 — A compu e algeb a sys em o polynomial compu a ions. h p://www.singula .uni-kl. de, 2020. [7] J. Gago-Va gas, I. Ha illo-He moso, J. Ma ín-Mo ales, and J. M. Ucha-En íquez. Sudokus and G öbne bases: no only a di e imen o. In Compu e algeb a in scien i ic compu ing, olume 4194 o Lec u e No es in Compu . Sci., pages 155–165. Sp inge , Be lin, 2006. [8] M.R. Gonzalez-Do ego. Resolu ion o sudokus using G oebne basis. Compu e ools in educa- ion, (3):5–21, 2018. [9] G.-M. G euel and G. P is e . ASingula in oduc ion o commu a i e algeb a. Sp inge , Be - lin, ex ended edi ion, 2008. Wi h con ibu ions by Ola Bachmann, Ch is oph Lossen and Hans Schönemann, Wi h 1 CD-ROM (Windows, Macin osh and UNIX). [10] Sage De elope s. SageMa h, he Sage Ma hema ics So wa e Sys em (Ve sion 9.2.0). h ps://www.sagema h.o g. [11] J. Suá ez Que o. Las ma emá icas en el sudoku. Uni e sidad de Alme ía, Sep iemb e 2017. 31