Teseo Decimo Problema de Hilbert

EL DECIMO PROBLEMA DE HILBERT

JOSE ALBERTO VELEZ MARULANDA

UNIVERSIDAD NACIONAL DE COLOMBIAFACULTAD DE CIENCIAS

DEPARTAMENTO DE MATEMATICASSANTAFE DE BOGOTA, D.C.

2001

EL DECIMO PROBLEMA DE HILBERT

JOSE ALBERTO VELEZ MARULANDA

Trabajo de grado presentado como requisito parcial para obtener elttulo de

Matematico

Dirigido por:Dr. RODRIGO DE CASTRO KORGI.

UNIVERSIDAD NACIONAL DE COLOMBIAFACULTAD DE CIENCIAS

DEPARTAMENTO DE MATEMATICASSANTAFE DE BOGOTA, D.C.

2001

A la memoria de mi hermana,Sandra Velez (1971-1993).

4AGRADECIMIENTOS

Agradezco en primer lugar a Dios por darme la fuerza y la salud para obtener todolo que hoy en da he logrado.

Agradezco a mi director de trabajo de grado Rodrigo De Castro, por proponermeel hermossimo tema que se basa este trabajo, ademas fue quien tomo la no muyagradable tarea de corregir mis incontables errores, convirtiendo la lectura de estetexto significativamente mas agradable y entendible a la que se poda haber hechosin sus acertadas correcciones.

Agradezco al profesor Luis Eduardo Giraldo quien realizo la funcion de leer cuida-dosamente el texto y corregir con mucha dedicacion los errores que se me escaparonen la version anterior del trabajo; ademas me hizo saber muchas sugerencias acer-tadas que permiten que este trabajo sea mucho mejor de lo que fue en el momentode la entrega.

Agradezco a mis maestros Liliana Blanco, Margarita Ospina, Vctor Albis, MyriamMunoz, Francisco Caicedo, Oswaldo Lezama, Beatriz Villa, Ignacio Mantilla y enespecial a Andres Villaveces que ademas de ser uno de los matematicos que mas ad-miro, fue el segundo jurado de mi trabajo de grado y aporto mediante sus brillantescomentarios un valioso recurso para mejorar la version final de mi trabajo. Graciasa ellos por compartir conmigo a lo largo de todos estos anos sus conocimientos y susimpata.

Agradezco de manera muy especial a mis amigos y companeros: Javier Solano, Fred-dy Hernandez, Pedro Nel Maluendas, Milena Cortes y Javier Moreno, por ofrecermesu invaluable ayuda durante toda mi carrera, ademas por compartir conmigo inolvid-ables momentos que hicieron de todos estos anos una etapa muy hermosa y rica deexperiencias en mi vida. Gracias tambien a mis demas companeros que vivieron con-migo tantas anecdotas.

Agradezco finalmente a mi padre Jose Levi Velez y a mi hermana Sandra Velez, quiendesafortunadamente la intolerancia de estos tiempos no permitieron que compartieracon ella la felicidad que siento ahora.

JAV

Indice general

1

Introduccion general

The great importance of definite problems for the progress of mathe-matical science in general ... is undeniable. ... (for) as long as a branchof knowledge supplies a surplus of such problems, it maintains its vital-ity. ... every mathematician certainly shares ..the conviction that everymathematical problem is necessarily capable of strict resolution ... wehear within ourselves the constant cry: There is the problem, seek thesolution. You can find it through pure thought...

David Hilbert.

Resena historica

1Las lecturas de las traducciones de los libros sobre aritmetica de Diofanto, querealizo Pierre de Fermat, fue lo que inspiro la teora moderna de numeros y loque hoy conocemos como el estudio de las ecuaciones diofantinas. Las ecuaciones dio-fantinas no son mas que ecuaciones que involucran polinomios en muchas variables;su caracterizacion se debe a la naturaleza de sus soluciones. Diofanto buscabasoluciones racionales, mientras que Fermat y sus sucesores se interesaban en solu-ciones enteras. Fermat esta asociado con dos importantes ecuaciones diofantinas,la denominada ecuacion de Fermat

xn + yn = zn,

que solo tiene soluciones enteras diferentes de la trivial para n 2; y la denominadaecuacion de Pell,

x2 dy2 = k, d no es cuadrado perfecto.1Tomado de [?].

2

INTRODUCCION GENERAL 3

El nombre de esta ecuacion se debe a un error en el estudio de la misma por partede Leonhard Euler. La ecuacion de Pell aclara significativamente la diferen-cia entre el programa original en la busqueda de soluciones racionales por parte deDiofanto y el novedoso programa de Fermat para la busqueda de soluciones en-teras. En respuesta al desafo de Fermat, Lord Brouncker ofrece rapidamenteuna descripcion parametrica de las soluciones racionales, pero trabaja demasiadotiempo en el caso de soluciones enteras. Eventualmente, el deduce un algoritmoque permite generar soluciones enteras (un algoritmo que ya era conocido por losmatematicos hindues unos pocos siglos antes), pero nunca proporciono una pruebade la efectividad de su procedimiento, es decir, nunca probo que su algoritmo enefecto proporcionara siempre una solucion. El primero en probar la existencia desoluciones enteras de la ecuacion de Pell fue Joseph Louis Lagrange, aunquehoy en da se prefiere la solucion dada por Peter Gustav Lejeune Dirichlet.Lagrange con su trabajo adicionalmente fundara la teora de formas cuadraticas,un tema que se encuentra en su mayor plenitud en 1801 con la publicacion de Dis-quisitiones arithmeticae del gran matematico aleman Carl Friedrich Gau.Gau deseaba extender la teora de formas cuadraticas a mas variables, y ampli-arla a formas cubicas. El primer objetivo fue logrado en 1972 por Carl LudwingSiegel, y el segundo permanece inconcluso. En 1900 en el Congreso Interna-cional de Matematicas celebrado en Pars, David Hilbert, con una ampliavision del nuevo siglo, propone veintitres problemas con los cuales se esperara quelos matematicos del siglo XX desarrollaran sus investigaciones y teoras. El decimo enla lista, comunmente denominado El decimo problema de Hilbert o Hilbert10, peda un procedimiento mecanico que determinara la solubilidad o insolubili-dad de una ecuacion diofantina en los enteros. Hilbert estaba interesado en unasolucion positiva del problema. Existen varias versiones que explican el interes deHilbert:

Deseaba extender la teora de formas cuadraticas indefinidamente a mas vari-ables.

El pensaba que era posible eliminar los detalles y la prueba abstracta en lasolucion de problemas (solucionar el Entscheidungsproblem de Hilbert).

Fue una manifestacion de su fe en la habilidad de los matematicos para resolvertodos los problemas matematicos que el encontro y no haba solucionado.

El decimo problema de Hilbert enuncia lo siguiente:


10. Determinacion de la solubilidad de ecuaciones diofantinas. Dada unaecuacion diofantina con un numero de incognitas arbitrario y con coeficientes enteros:Encontrar un procedimiento mecanico, que en un numero finito de pasos, determinesi una ecuacion diofantina tiene solucion en los enteros.

El siglo XX estuvo lleno de trabajos sobre ecuaciones diofantinas, pero no necesari-amente enfocados hacia la solucion del decimo problema de Hilbert. ThoralfSkolem realizo una breve monografa de ecuaciones diofantinas en la tercera deca-da del siglo XX; otros matematicos que abordaron las ecuaciones diofantinas fueron:Thue, Siegel y Roth, quienes trabajaron en clases de ecuaciones con solo finitassoluciones.En los anos treinta se desarrollo una nueva teora, en un principio no relaciona-da con las ecuaciones diofantinas ni con el decimo problema de Hilbert. Ese fueel nacimiento de lo que hoy se denomina teora de algoritmos y la teora de fun-ciones calculables. Se desarrollaron varios modelos de calculabilidad que resultanequivalentes (ver [?]). Estas teoras permitieron demostrar en anos posteriores quealgunos problemas de calculabilidad eran insolubles. Entre ellos estan el problemade la parada, y el problema de la palabra para semigrupos 2; pero el problema de lasecuaciones diofantinas era ignorado. Skolem, quien hace contribuciones a la teorade algoritmos y a la de ecuaciones diofantinas, sugiere que se hagan investigacionessobre el decimo problema de Hilbert, aunque el nunca trabajo en ello.Alrededor de 1950 se comienza a abordar el problema de Hilbert, por medio dealgunos artculos que impulsaban su estudio. Pero la investigacion formal comienzacon un artculo publicado en 1961 y logra su exito en el ano de 1970 con un artculode Yuri Matiyasevic, quien demostro que EL DECIMO PROBLEMA DEHILBERT NO TIENE SOLUCION. Las primeras contribuciones fueron real-izadas por Julia Robinson y Martin Davis. En [?], Robinson defina que unarelacion R sobre enteros no negativos era diofantina si poda ser escrita en la forma:

R(x0, ..., xm) (y0, ...., yn)[P (x0, ..., xm, y0, ...., ym) = 0],donde P es un polinomio con coeficientes enteros e y0, ..., yn tienen como rango elconjunto de los numeros enteros. Se deseaba demostrar que, relaciones recursiva-mente enumerables son diofantinas. Es decir

Teorema 1. Toda relacion recursivamente enumerable R(x0, ..., xm) sobre enterosno negativos se puede escribir de la forma:

R(x0, ..., xm) (y0, ..., yn)[P (x0, ..., xm, y0, ..., yn) = 0].2Estos problemas se pueden ver con todo detalle en [?]


Robinson demostro una forma exponencial del teorema 1, es decir, P no era unpolinomio pero contena una funcion exponencial y = ax. As, Julia Robinsondemostro que, relaciones recursivamente enumerables son exponeciales-diofantinas.En la prueba implemento sucesiones de soluciones de la ecuacion de Pell de laforma:

x2 (a2 1)y2 = 1, a 2. (1)Davis uso mas la logica matematica. La teora de algoritmos clasifica dos tiposde conjuntos de enteros no negativos, estos conjuntos son: conjuntos recursivos ylos recursivamente enumerables, para los cuales existe un algoritmo de enumeracion.Existen conjuntos recursivamente enumerables no recursivos. Si se lograba demostrarel teorema 1, entonces el decimo problema de Hilbert no tendra solucion. Lastecnicas que desarrollo Kurt Godel en la demostracion de su famoso Teoremade incompletitud (ver [?] o [?]), hace suponer que todo conjunto recursivamenteenumerable puede ser escrito en la forma:

(y0Q1y1 Qmym)[P (x, y0, ..., ym) = 0],

donde cada Qi es un cuantificador existencial o un cuantificador universal acotado,esto es, un cuantificador de la forma yi y0. Davis simplifico esta representaciona la forma normal de Davis

(yz yw0 y, ..., wm y)[P (x, y, z, w0, ..., wm) = 0].

Hacia el final de los anos cincuenta,Hilary Putman yMartin Davis [?] demostra-ron, asumiendo la aun no probada existencia de progresiones aritmeticas de numerosprimos de longitud arbitraria, la no solubilidad del problema de Hilbert de la man-era exponencial-diofantina sobre los enteros no negativos. Con la ayuda de JuliaRobinson, la conjetura no probada era innecesara. Davis, Putman y Robinsonaplicaron las relaciones exponenciales-diofantinas de Robinson para eliminar elcuantificador sencillo acotado de la forma normal de Davis. Su prueba fue publica-da en 1961 (ver [?]). El teorema Davis-Putman-Robinson sera una herramientafundamental para demostrar que relaciones exponeciales-diofantinas eran relacionesdiofantinas. Pero el resto de los anos sesenta fue muy poco productivo en cuan-to a la investigacion sobre el decimo problema de Hilbert se refiere. En Marzode 1970, Yuri Matijasevic, un joven matematico ruso (con tan solo 22 anos deedad) demostro que relaciones exponenciales-diofantinas eran diofantinas (ver [?]),es decir, se logro demostrar el teorema 1. Matijasevic uso como instrumento laspropiedades de divisibilidad de la sucesion de Fibonnaci.


Inmediatamente despues de la demostracion deMatijasevic surgieron nuevas prue-bas usando sucesiones de soluciones de la ecuacion de Pell (1), hechas por Davis[?], Chudnosky y Kosovskii. Existe un analisis de la demostracion deMatijase-vic de 1970 en espanol elaborada por el matematico colombiano Xavier Caicedo[?].

Observaciones

La prueba que analizaremos en este trabajo es notablemente mas corta que la de1970. Aqu veremos con detalle la prueba publicada por J.P Jones y Yuri Matija-sevic en Octubre de 1991 [?]. En la prueba se usan tambien sucesiones de solucionesde (1). La diferencia de las demas pruebas que usan dichas sucesiones, es que usamosun metodo desarrollado por Jones y Matijasevic (ver [?]): la aritmetizacion demaquinas ilimitadas de registro (concepto que veremos con detalle en el capitulo 4),modelo de calculabilidad equivalente a las maquinas de Turing (ver [?]). Veremostambien con detalle los conceptos de relacion diofantina, conjunto diofantino y fun-cion diofantina en el captulo 1; tambien haremos un analisis de las sucesiones desoluciones de (1) en el captulo 2.Nos restringiremos unicamente (a menos que se diga lo contrario) al conjunto de losenteros no negativos denotado comunmente por N.

Principio de induccion

Usaremos con frecuencia el principio de induccion matematica.

Teorema 2 (Principio de induccion matematica). Sea S un conjunto deenteros no negativos para el cual son validas las siguientes propiedades:

(a) El numero 1 pertenece a S.

(b) Si un entero k esta en S, entonces k + 1 tambien esta en S.

Entonces S = N.

La demostracion del teorema 2 hace parte de un curso de fundamentos de matematicasy no la haremos aqu. Se puede ver con detalle en [?] .


Soluciones enteras no negativas

La razon del por que nos restringimos al conjunto N se debe a los siguientes teoremas:

Teorema 3. Una ecuacion P (x1, ..., xn) = 0 tiene solucion en los enteros si y solosi la ecuacion

P (x1, ...xn) =

(s1,...,sn)

P (s1x1, ..., snxn) = 0;

donde si = 1 con i = 1, 2, ..., n; tiene solucion en los enteros no negativos.Demostracion: Evidente.

Teorema 4 (Suma de los cuatro cuadrados de Lagrange). Cualquier en-tero no negativo puede expresarse como suma de los cuadrados de cuatro enteros.

La prueba de este teorema es muy tecnica y extensa para mostrarla aqu. Se puedever con detalle en [?].As, una ecuacion P (x1, ..., xn) = 0 tiene soluciones en los enteros no negativos si ysolo si P (z1

2 + y12 + u1

2 + v12, ..., zn

2 + yn2 + un

2 + vn2) = 0 tiene soluciones en los

numeros naturales. Luego el decimo problema de Hilbert se reduce al de solucionesen N.

Concepto de algoritmo y modelos de calculabilidad

En el decimo problema de Hilbert se pide determinar un procedimiento mecanicoque determine en un numero finito de pasos si una ecuacion diofantina tiene solu-ciones enteras o no. En realidad lo que pedaHilbert era un algoritmo que solucioneel decimo problema.Un algoritmo es un metodo cuya ejecucion consiste en la aplicacion, paso a paso, deciertas reglas especificadas a priori. Estas reglas deben determinar el resultado finalcompletamente. Las operaciones basicas de la Aritmetica; sumar, restar, dividir ymultiplicar son procedimientos algortmicos. Un algoritmo conocido es el algoritmode Euclides para deteminar el maximo comun divisor de dos enteros no negativos.Necesitamos definir las funciones calculables, existen los siguientes modelos de cal-culabilidad:

(a) Godel-Herbrand-Kleene (1936): Funciones recursivas generales definidaspor medio de una ecuacion de calculo.

(b) Church (1936): Funciones -definibles.


(c) Godel-Kleene (1936): Funciones -recursivas y funciones recursivas par-ciales.

(d) Turing (1936): Funciones calculables definidas por maquinas finitas conoci-das como maquinas de Turing.

(e) Post (1943): Funciones definidas por sistemas de deduccion canonica.

(f) Markov (1951): Funciones obtenidas por cierto algoritmo sobre un alfabetofinito.

(g) Shepherdson-Sturgis (1963): Maquinas ilimitadas de registro.

Todos los modelos anteriores de calculabilidad son todos equivalentes y determinanla clase de funciones calculables denotada por C.La demostracion de la anterior afirmacion se puede ver con todo detalle en [?]. Eneste trabajo usaremos el modelo de calculabilidad (g). En la prueba del teorema1 usaremos basicamente los resultados obtenidos en los capitulos 3 y 4. En la de-mostracion de la no solubilidad del decimo problema de Hilbert en el capitulo 5mencionaremos la Tesis de Church y usaremos el juego de T.Rado expuesto condetalle en [?]. En el captulo 6 veremos dos importantes consecuencias de la solucionnegativa del decimo problema de Hilbert.

Captulo 1

Conjuntos diofantinos

1.1. Introduccion

En este captulo daremos algunas definiciones y algunos ejemplos que seran valiosospara el desarrollo de los demas captulos. En particular, definiremos uno de los con-ceptos mas valiosos del presente trabajo, las relaciones diofantinas y consecuente-mente, los conjuntos diofantinos. Veremos, por ejemplo, que relaciones comunes so-bre los enteros como la relacion de congruencia, la divisibilidad, la coprimalidad y elorden, son diofantinas. Comenzaremos definiendo un concepto central: ecuacion dio-fantina. Cabe notar que siempre estamos hablando de enteros no negativos, por talrazon, algunos conceptos y propiedades de los numeros enteros han sido ligeramentemodificados, desde luego, sin perjudicar la esencia de los mismos1 .

1.2. Conjuntos diofantinos; ecuaciones, relaciones

y funciones diofantinas

Definicion 1.2.1. Sea P (a1, ..., am, x1, ..., xn), un polinomio con variables a1, ..., am(parametros) y x1, ..., xn (incognitas), la ecuacion:

P (a1, ..., am, x1, ..., xn) = 0, (1.1)

1Un ejemplo de esto es la relacion de coprimalidad que se vera en paginas posteriores. Decimosque dos enteros, a y b son coprimos si su maximo comun divisor es 1, esto es equivalente a queexistan dos enteros, y , tales que a b = 1, debemos asegurarnos que tanto como seanenteros no negativos; as esta propiedad se modifica de la siguiente manera: existen y talesque, a b = 1 o a b = 1.

9

CONJUNTOS DIOFANTINOS 10

donde solo se consideran sus posibles soluciones enteras, se denomina ecuacion dio-fantina.

Ejemplos de ecuaciones diofantinas son:

1. x2 + 1 = 0.

2. ax2 + bx+ c = 0, donde a, b, c Z.3. xn + yn zn = 0.

No siempre las ecuaciones diofantinas tienen solucion. Con respecto a las ecuacionesanteriores, sabemos que la primera no tiene solucion en los reales, luego mucho menosen los enteros; la segunda puede pensarse que tiene solucion si al menos el valorb2 4ac es un cuadrado perfecto, de lo contrario, no tiene soluciones; y finalmente,la tercera ecuacion existen soluciones si n 2, pero por el ultimo teorema de Fermat,no existen soluciones para n 3.Definicion 1.2.2 (Relacion diofantina). Sea A N no vaco, una relacion m-aria, A(a1, ..., am) sobre A, se dice diofantina si existe un polinomio P (a1, ..., am, x1, ...., xn), tal que:

A(a1, ..., am) (x1, ..., xn)[P (a1, ..., am, x1, ...., xn) = 0]. (1.2)

De la anterior definicion es mas facil derivar el concepto de conjunto diofantino.

Definicion 1.2.3 (Conjunto Diofantino). Sea A N no vaco, A es conjuntodiofantino si existe P (a, x1, ...., xn) tal que:

a A (x1, ..., xn)[P (a, x1, ...., xn) = 0]. (1.3)

Tambien es mas natural la definicion de funcion diofantina.

Definicion 1.2.4 (Funcion diofantina). Una funcion de variable entera se dicediofantina si su grafo (i.e {(x, f(x)) : x dom(f)}) es diofantino.

1.3. Algunos ejemplos importantes

Veamos que algunas relaciones comunes entre los enteros no negativos son diofanti-nas.


Ejemplo 1.3.1 (Relacion de orden). Sean a, b N, observemos que la relacion deorden sobre N satisface:

a b (x)[a+ x = b] (1.4)La anterior expresion es de la forma de la ecuacion (1,2), tomando como polinomioen cuestion a a+ x b = 0, as la relacion, , es diofantina.Ejemplo 1.3.2 (Relacion de divisibilidad). Sean a, b N, definimos la relacion dedivisibilidad sobre N como:

a | b (x)[ax = b] (1.5)

Analogamente al anterior ejemplo, tomamos como polinomio en la ecuacion (1,2) aax b = 0, por lo tanto, | tambien es diofantina.Consideremos las siguientes propiedades de los numeros enteros no negativos. SeanA,B Z, entonces son validas las siguientes afirmaciones.

A = 0 o B = 0 AB = 0, A = 0 y B = 0 A2 +B2 = 0 (1.6)

Ejemplo 1.3.3 (Relacion de congruencia). Sean a, b, c N, definimos la relacion decongruencia sobre N como:

a b mod c c | a b o c | b a

Por el ejemplo (??), esto es equivalente a:

a b mod c (x)[a = b+ cx o a = b cx]

Por la propiedad (1,6) tenemos que:

a b mod c (x)[(a b cx)(a b+ cx) = 0]. (1.7)

As por (1,2) , tenemos que es diofantina.Por la propiedad (1,6) tenemos que disyunciones y conjunciones de relaciones dio-fantinas son relaciones diofantinas. Consideremos ahora la siguiente propiedad logi-ca, que nos sera util mas adelante:

(x)[P (x)] (y)[Q(y)] (x, y)[P (x) Q(y)] (1.8)

Las propiedades (1,6) y (1,8) son herramientas que nos permiten ver que muchasrelaciones sobre los enteros no negativos son diofantinas.


Ejemplo 1.3.4 (Relacion de coprimalidad). Sean a, b N, decimos que a y b soncoprimos si su maximo comun divisor es la unidad (i.e. (a,b) = 1 ). Denotemoslocomo a b. Luego,

a b (x, y)[ax by = 1 o ax by = 1]Por la propiedad (1,6), la anterior expresion se transforma en:

a b (x, y)[(ax by 1)(ax by + 1) = 0]. (1.9)As la relacion de coprimalidad, es diofantina.Veamos algunos ejemplos de funciones diofantinas.

Ejemplo 1.3.5 (Funcion de residuo). Sean a, b N, definimos rem(a, b), como lafuncion que devuelve el residuo de la division de a por b. Es decir:

r = rem(a, b) r a mod b y 0 r < b (1.10)lo cual es equivalente, por (1,4) y (1,7) a:

r = rem(a, b) (x)[(a bx r)(a+ bx r) = 0] (y)[b = r + y].Usando la propiedad (1,8) tenemos que:

r = rem(a, b) (x, y)[(a bx r)(a+ bx r) = 0 b r y = 0],as, por la propiedad (1,6) llegamos a:

r = rem(a, b) (x, y)[[(a bx+ r)(a+ bx r)]2 + (b y r)2 = 0].Por lo tanto, en virtud de la definicion 1.2.4, tenemos que rem(a, b) es diofantina.

Ejemplo 1.3.6 (Funcion de cociente). Sean a, b N definimos quo(a, b), como lafuncion que devuelve el cociente de la division de a por b. Es decir:

q = quo(a, b) 0 a qb < b (1.11)lo cual es equivalente, por (1,4) a:

q = quo(a, b) (x)[b a+ qb x = 0],luego, tambien por la definicion 1.2.4 tenemos que quo(a, b) es diofantina.

Captulo 2

La ecuacion de Pell

2.1. Introduccion

La ecuacion diofantina x2dy2 = N , donde d y N son enteros, es comunmente cono-cida como la ecuacion de Pell. Los antiguos matematicos griegos y egipcios, fueronlos primeros en tratar casos particulares de esta ecuacion, pero Pierre de Fer-mat fue el pionero en tratarla sistematicamente. Fermat afirmo que la ecuacionpara el caso N = 1 y d > 0 donde d no era cuadrado perfecto, tena infinitas solu-ciones enteras x e y, pero no dio ninguna prueba. Joseph Lagrange fue el primeroque publico una demostracion de dicha observacion, usando la teora de fraccionescontinuas. Despues, Leonard Euler demostro que la ecuacion tena infinitas solu-ciones, si exista al menos una. La ecuacion de Pell es de suma importancia en lateora de numeros debido a que muchas ecuaciones diofantinas pueden llevarse a unaecuacion de Pell, o a que dependa de alguna forma de ella. Por ejemplo, conocien-do la forma de las soluciones de la ecuacon de Pell, es posible hallar todas lassoluciones enteras de la ecuacion general de segundo grado:

ax2 + bxy + cy2 + dx+ ey + f = 0,

donde a, b, c, d, e y f , son enteros. El procedimiento es el siguiente: Agrupamos losterminos de esta manera

ax2 + (by + d)x+ (cy2 + ey + f) = 0.

Luego, la anterior ecuacion se puede ver como una ecuacion sencilla de segundogrado con discriminante

(by + d)2 4a(cy2 + ey + f),

13

LA ECUACION DE PELL 14

que es equivalente a

(b2 4ac)y2 + (2bd 4ae)y + d2 4af,el cual debe ser un cuadrado perfecto, llamemoslo z2. As, defininamos a

p = b2 4ac, q = 2bd 4ae, r = d2 4af.Luego tenemos

py2 qy + r z2 = 0,que de nuevo es una ecuacion de segundo grado con y como incognita. Procediendocomo antes tenemos

q2 4p(r z2) = w2,por lo tanto,

w2 4pz2 = q2 4prque es una ecuacion de Pell, con N = q24pr. Luego , si conocemos las solucionesenteras de esta ecuacion, obtenemos inmediatamente las soluciones enteras de laecuacion general de segundo grado. En este captulo veremos el caso particular:

x2 dy2 = 1, (2.1)donde d no es cuadrado perfecto, es decir, no existe a Z, tal que d = a2.Observacion 2.1.1. Si d = a2 para algun a, entonces (??) solo tiene la solucionentera trivial (x, y) = (1, 0).

Demostracion: Si d = a2 para algun a, entonces (??) puede factorizarse como:

(x+ ay)(x ay) = 1Luego x+ ay = 1 y x ay = 1, ya que el producto de dos enteros es igual a uno siy solo si ambos son 1, as tenemos el siguiente sistema:

x+ ay = 1,

x ay = 1.Usado regla de Cramer tenemos que:

x =(a a)(a a) = 1,

y =(1 1)(a a) = 0.

Luego, la unica solucion es (x, y) = (1, 0).


2.2. Las soluciones de la ecuacion de Pell

Por la forma de la ecuacion (??), podemos factorizarla de la siguiente manera:

x2 dy2 = (x+dy)(x

dy) = 1.

Luego es natural trabajar sobre el domino Z[d], donde:

Z[d] = { = x+

dy R : x, y Z}.

Sea Z[d], si = x+dy, x e y se denominan las componentes de .Observacion 2.2.1. Si = x +

dy con

d irracional, entonces los enteros x e y

son unicos.

Demostracion: Supongamos que = x+dy y = w +

dz entonces:

x+dy = w +

dz

y as(x w) +

d(y z) = 0

comod es irracional, tenemos que x w = 0 y y w = 0, por lo tanto, x = w e

y = z.

Si = x+dy y = w +

dz, entonces:

+ = (x+ w) +d(y + z)

= (xw + dyz) +d(xz + yw)

Con un poco de trabajo se puede ver que (Z[d],+, ) es un dominio de integridad.

Definicion 2.2.1. Si = x +dy, el numero = x dy, se denomina el

conjugado de .

Definicion 2.2.2. Si = x +dy, el numero N() = x2 dy2, se denomina la

norma de .

Por la definicion ??, es evidente que las soluciones enteras de (??) son las compo-nentes de los tales que cumplen N() = 1. En este trabajo solo consideraremoslos Z[d] tales que N() = 1 y las componentes de enteras no negativas.Lema 2.2.1. Sea , Z[d], = x+dy y = w +dz, entonces:


(1) N() = .

(2) + = 2x y = 2dy.(3) Si N() = 1 entonces, = 1.

(4) = .(5) N() =N()N().

(6) N() = N().

(7) Si 1 entonces, 1 x y 0 y.(8) N(n) =N()n.

(9) Si N() = 1 y N() = 1 entonces, x < w si y solo si y < z.

Demostracion: (1) = (x+dy)(xdy) = x2 dy2 =N().

(2) Evidente.

(3) Por (1) tenemos que = 1, asi = 1.

(4) = (xw + dyz) +d(xz + yw) = (xw + dyz) d(xz + yw), por otrolado, = (xdy)(w dz) = (xw + dyz)d(xz + yw), as se obtienelo deseado.

(5) N() = = = = =N()N().(6) N() =N(xdy) =N(x+d(y)) = x2 d(y)2 = x2 dy2 = N().(7) Tenemos que es un numero real , si 1 entonces su inverso multiplicativo

satisface que 0 < 1, luego, por un lado tenemos que 1 < + = 2xde donde obtenemos que 1

2< x; as x es positivo. Tambien tenemos que 0 =

1 1 = 2yd, luego, 0 y, luego y es no negativo. Como N() = 1entonces x2 dy2 = 1, as x2 = 1 + dy2 1 + 0 = 1, sacando raz cuadradatenemos que x 1 , as tenemos lo deseado.

(8) Usando induccion sobre n y el numeral (5).


(9) Por (7), x, y, w, z son no negativas, como N() = 1 y N() = 1, tenemos quex2 = 1+dy2 y w2 = 1+dz2, luego, si x < w elevando al cuadrado ambos lados,tenemos que 1 + dy2 = x2 < w2 = 1 + dz2, por lo tanto dy2 < dz2 as y < z.De manera analoga se demuestra el otro sentido.

Por los numerales (7) y (9) del lema 2.2.1 se tiene que 1 < si y solo si1 < x < w y 0 < y < z, con N() =N() = 1. Luego este tipo de orden genera unbuen orden total para

{ R : = x+dy > 1, N() = 1, x, y Z}.

Como siempre debemos garantizar que no estamos hablando de un conjunto vaco,por ello enuncamos los siguientes teoremas1:

Teorema 2.2.1. Existen infinitas soluciones de la ecuacion

x2 dy2 = k (2.2)en los enteros no negativos , para algun k tal que |k| < 1 + 2d.Bosquejo de la demostracion: Primero se prueba que la desigualdad

|x y| < 1y, ()

tiene infinitas soluciones con real no racional. Si (x, y) es una solucion de () con =d, entonces

|x+ yd| = |x y

d+ 2y

d| < 1

y+ 2yd (1 + 2

d)y,

y as

|x2 dy2| = |x+dy||x

dy| < [(1 + 2

d)y]

(1

y

)= 1 + 2

d.

Existen muchas tuplas (x, y) disponibles, pero finitos enteros mas pequenos que1 + 2

d e infinitos numeros de la forma x2 dy2 deben tener un valor comun que

es el k del teorema.

1Para la prueba de estos teoremas se necesita teora de fracciones continuas. El lector puedehallar las pruebas detalladas en [?].


Teorema 2.2.2. La ecuacion (??) tiene a lo menos una solucion con y 6= 0.Bosquejo de la demostracion: Usando el teorema ??, existe un entero k > 0 talque una de las dos ecuacionesN() = k tiene infinitas soluciones en Z[d]. Comosolo existen finitas clases de residuos ( mod k) en Z[

d], alguna clase de residuo

debe contener al menos tres de esas soluciones (de hecho infinitas!). Asumamosentonces que N(1) =N(2) = k y 1 2 mod k, pero 1 6= 2. Entonces12 22 0 mod k, luego = 12k es un elemento de Z[

d]. Como

N() =1221

k2=N(1)N(2)

k2= 1,

es solucion de (??), como la segunda componente de es cero , entoncesN() = 1implica que = 1, luego

12 = k = 112 = 1 = 1

contradiciendo nuestra hipotesis.

Por lo tanto existe un primer elemento = a+db, a este real lo denominamos el

generador y a (a, b) la solucion fundamental. Por la forma de tenemos que:

1 < < 2 < 3 < 4 < .... (2.3)

As genera una cadena infinita ascendente de soluciones de (??). Veamos que si es una solucion de (??) diferente de , entonces es una potencia de .

Teorema 2.2.3. Si > 1 es una solucion de (??), entonces existe n N tal que: = n.

Demostracion: Como > 1 y por la minimalidad de tenemos que ; luego,si observamos la cadena (??), vemos que debe estar en medio de ella. Por lo tantoexiste n tal que:

n < n+1.Dividiendo por n la anterior desigualdad, tenemos que:

1 n

<


donde n

= n, sea = n, asi, N(n) =N()N(n) = 1, luego tambien essolucion de (??) y

1 < .Si 6= 1 , entonces tendramos que 1 < < , contradiciendo la minimalidad de .As tenemos que = 1 , luego

n= 1, por lo tanto, = n.

2.3. Sucesiones de Lucas

Consideremos a d de la forma especial, d = a2 1; luego la ecuacion especial dePell es:

x2 (a2 1)y2 = 1. (2.4)Esta ecuacion tiene como solucion fundamental a (a, 1), as el generador es a +a2 1. Para ver esto, supongamos que (x1, y1) solucion de la ecuacion (??) tal

que x1 +a2 1y1 a +

a2 1, luego x1 a si y solo si y1 1, como estamos

hablando siempre de enteros no negativos tenemos que y1 = 1; por lo tanto x1 = a.Sea:

Xa(n) + Ya(n)a2 1 = (a+

a2 1)n. (2.5)

Luego tenemos todas las soluciones de la ecuacion (??) por el teorema 2.2.3. Por suforma las sucesiones x = Xa(n) e y = Ya(n) son estrictamente crecientes.

Lema 2.3.1. Sea d = a2 1, entonces:(1) Xa(n) Ya(n)

a2 1 = (aa2 1)n.

(2) Xa(n) Ya(n)a2 1 = (a+a2 1)n.

(3) Xa(nm) + Ya(nm)d = (Xa(n) + Ya(n)

d)(Xa(m) Ya(m)

d).

(4) Xa(nm) = Xa(n)Xa(m) dYa(n)Ya(m).(5) Ya(nm) = Ya(n)Xa(m)Xa(n)Ya(m).(6) Xa(n+ 1) = aXa(n) + dYa(n).

(7) Xa(n 1) = aXa(n) dYa(n).(8) Ya(n+ 1) = aYa(n) +Xa(n).

(9) Ya(n 1) = aYa(n)Xa(n).


(10) Xa(n+ 1) = 2aXa(n)Xa(n 1).(11) Ya(n+ 1) = 2aYa(n) Ya(n 1).(12) Xa(2n) = 2Xa(n)

2 1.(13) Ya(2n) = 2Xa(n)Ya(n).

Demostracion: (1) Aplicando el conjugado a ambos lados en (2,5) tenemos que:

Xa(n) + Ya(n)a2 1 = (a+

a2 1)n

Xa(n) Ya(n)a2 1 = (a+

a2 1)

n

= (aa2 1)n.

(2) Por propiedades del conjugado tenemos que:

Xa(n) Ya(n)a2 1 = (Xa(n) + Ya(n)

a2 1)1

= ((a+a2 1)n)1

= (a+a2 1)n.

(3)

Xa(nm) + Ya(nm)d = (a+

d)nm

= (a+d)n(a+

d)m

= (Xa(n) + Ya(n)d)(Xa(m) Ya(m)

d).

Haciendo el producto del lado derecho de la ecuacion anterior tenemos que

Xa(nm) + Ya(nm)d = Xa(n)Xa(m)Xa(n)Ya(m)

d

+ Ya(n)Xa(m)d dYa(n)Ya(m)

= (Xa(n)Xa(m) dYa(n)Ya(m))+ (Ya(n)Xa(m)Xa(n)Ya(m))

d.

(4) Igualando partes racionales y partes irracionales en (3), tenemos que Xa(nm) = Xa(n)Xa(m) dYa(n)Ya(m).


(5) Ya(nm) = Ya(n)Xa(m)Xa(n)Ya(m)Observemos que Xa(1) + Ya(1)

a2 1 = a + a2 1, por (2,5), igualando

componentes tenemos que: Xa(1) = a e Ya(1) = 1.

(6) As, por (5) tenemos que:

Xa(n+ 1) = Xa(n)Xa(1) + dYa(n)Ya(1) = aXa(n) + dYa(n).

(7) Analogamente a (6) tenemos que:

Xa(n 1) = Xa(n)Xa(1) dYa(n)Ya(1) = aXa(n) dYa(n).

(8) Ya(n+ 1) = Ya(n)Xa(1) +Xa(n)Ya(1) = aYa(n) +Xa(n).

(9) Ya(n 1) = Ya(n)Xa(1)Xa(n)Ya(1) = aYa(n)Xa(n).(10) Sumando las identidades (6) y (7), tenemos que

Xa(n+ 1) +Xa(n 1) = 2aXa(n)

de donde se tiene la identidad.

(11) Analogo al numeral (10).

(12) Remplazando a m por n en el numeral (4) tenemos que:

Xa(2n) = Xa(n+ n)

= Xa(n)Xa(n) + dYa(n)Ya(n)

= Xa(n)2 + dYa(n)

2

= Xa(n)2 +Xa(n)

2 1= 2Xa(n)

2 1.

(13) Analogamente al numeral (12):

Ya(2n) = Ya(n+ n)

= Ya(n)Xa(n) + Ya(n)Xa(n)

= 2Ya(n)Xa(n).


Observemos que Xa(0)+Ya(0)a2 1 = (a+a2 1)0 = 1, por lo tanto Xa(0) = 1

e Ya(0) = 0.Usando las identidades (10) y (11) del lema 2.3.1, encontramos una representacionrecursiva de las soluciones de la ecuacion (??) de esta manera:

Xa(0) = 1, Xa(1) = a, Xa(n+ 1) = 2aXa(n)Xa(n 1), (2.6)Ya(0) = 0, Ya(1) = 1, Ya(n+ 1) = 2aYa(n) Ya(n 1). (2.7)

La anterior formula de recursion nos genera las sucesiones de Lucas. Las anterioresidentidades y la formula de recursion son ciertas unicamente para 2 a, pero paraa = 1, definimos a X1(n) = 1, e Y1(n) = n, para que sean validas las anterioresexpresiones para cualquier numero natural. Por ejemplo, para a > 1:

Xa(2) = 2aXa(1)Xa(0) = 2a(a) 1 = 2a2 1.Ya(2) = 2aYa(1) Ya(0) = 2a(1) 0 = 2a.

Xa(3) = 2aXa(2)Xa(1) = 2a(2a2 1) a = 4a3 3a.Ya(3) = 2aYa(2) Ya(1) = 2a(2a) 1 = 4a2 1.

En la tabla siguiente veremos los primeros ocho valores correpondientes a Xa(n) eYa(n) para a > 1.

n Xa(n) Ya(n)0 1 01 a 12 2a2 1 2a3 4a3 3a 4a2 14 8a4 8a2 + 1 8a3 4a5 16a5 20a3 + 5a 16a4 12a2 + 16 32a6 48a4 + 18a2 1 32a5 32a3 + 6a7 64a7 112a5 + 56a3 7a 64a6 80a4 + 24a2 18 128a8 256a6 + 160a4 32a2 + 1 128a7 192a5 + 80a3 8a

Para a = 1 tenemos que:

X1(2) = 2X1(1)X1(0) = 2(1) 1 = 1.Ya(2) = 2Y1(1) Ya(0) = 2(1) 0 = 2.Xa(3) = 2X1(2)Xa(1) = 2(1) 1 = 1.Ya(3) = 2Y1(2) Ya(1) = 2(2) 1 = 3.


En la tabla siguiente podemos ver los primeros siete valores de X1(n) e Y1(n), loscuales no son muy interesantes.

n X1(n) Y1(n)0 1 01 1 12 1 23 1 34 1 45 1 56 1 67 1 7

De la primera tabla es posible intuir que para un entero fijo n, Ya(n) es un polinomioen a de grado n 1, formalizaremos esto en el siguiente lema.Lema 2.3.2. Sea n 1 entonces, Ya(n) es un polinomio en a de grado n 1.Demostracion: Por induccion sobre n. Si n = 1, entonces Ya(n) = 1, donde 1es un polinomio de grado 0 = n 1; asi el lema es cierto para 1. Supongamosvalido el lema para n = k 1. Sea Ya(k) = bk1ak1 + bk2ak2 + ... + b1a + b0y Ya(k 1) = ck2ak2 + ck3ak3 + ... + c1a + c0, esto es cierto por hipotesis deinduccion, sea n = k+1, entonces por la identidad (11) del lema 2.3.1, tenemos que:

Ya(k + 1) = 2aYa(k) Ya(k 1)

. As

Ya(k + 1) = 2a(bk1ak1 + bk2ak2 + ...+ b1a+ b0)

(ck2ak2 + ck3ak3 + ...+ c1a+ c0).

Luego

Ya(k + 1) = 2bk1ak + (2bk2 ck2)ak1 + ...+ (2b1 c2)a2 + (2b0 c1)a c0),

que evidentemente es un polinomio de grado k = n 1; asi el lema es valido paratodo n.

El siguiente lema nos permitira deducir una formula de recurrencia importante.


Lema 2.3.3. Sea P (x) un polinomio con coeficientes enteros, y r s mod m,entonces:

P (r) P (s) mod mDemostracion: Evidente.

Por definicion es evidente que:

a b 0 mod (a b).

Asi,a b mod (a b).

Como Yx(n) es un polinomio en x de grado n 1, tenemos por el lema 2.3.3 que

Ya(n) Yb(n) mod (a b) [Regla de Congruencia]. (2.8)

Esto es valido para a, b 1, luego , si tomamos b = 1 , tenemos que

Ya(n) Y1(n) = n mod (a 1).

Asi obtenemos la regla especial de congruencia de Julia Robinson:

Ya(n) n mod (a 1). (2.9)

Las identidades de Lucas (10) y (11) del lema 2.3.1, son tambien utiles para derivarcotas sobre el tamano de Xa(n) e Ya(n).

Lema 2.3.4.(2a 1)n < Ya(n+ 1) < (2a)n (2.10)

para 1 a y 1 < n.Demostracion: Como 1 = 1n < n+1 = Y1(n+1) < 2

n = [2(1)]n, la desigualdad esvalida para a = 1. Supongamos a > 1. Como (2a1)2 < 4a21 = Ya(2+1) < (2a)2,la desigualdad es valida para n = 2. Supongamos valida la desigualdad para n = k,esto es

(2a 1)k < Ya(k + 1) < (2a)k.


Veamos que la desigualdad es valida para n = k + 1. Usando que Ya(n) es unasucesion estrictamente creciente y la hipotesis de induccion, tenemos que:

(2a 1)k+1 = (2a 1)(2a 1)k< (2a 1)Ya(k + 1)= 2aYa(k + 1) Ya(k + 1)< 2aYa(k + 1) Ya(k)< 2a(2a)k Ya(k) < (2a)k+1.

Luego

(2a 1)k+1 < 2aYa(k + 1) Ya(k) < (2a)k+1,

pero Ya(k + 2) = 2aYa(k + 1) Ya(k). As el lema queda demostrado.

La desigualdad del lema 2.3.4 muestra que Ya(n) crece exponencialmente en n. Lasiguiente congruencia fue obtenida por Julia Robinson.

Lema 2.3.5.

Xa(n) (a k)Ya(n) kn mod (2ak k2 1). (2.11)

Demostracion: Debemos ver que se tiene la congruencia para todo n 0 y k 0.Para n = 0, tenemos que

Xa(0) (a k)Ya(0) = 1 1 = k0 mod (2ak k2 1).

Para n = 1, tenemos que

Xa(1) (a k)Ya(1) = a (a k) = k k = k1 mod (2ak k2 1).

Supongamos la congruencia valida para n = m 0 y veamos que la congruencia es


valida tambien para n = m+ 1.

Xa(m+ 1) (a k)Ya(m+ 1) = [2aXa(m)Xa(m 1)] (a k)[2aYa(m) Ya(m 1)]

= 2aXa(m)Xa(m 1) 2a(a k)Ya(m) + (a k)Ya(m 1)

= 2a[Xa(m) (a k)Ya(m)] [Xa(m 1) (a k)Ya(m 1)]

2akm km1 mod (2ak k2 1)= km1(2ak 1)= km1(2ak k2 1 + k2)= km1(2ak k2 1) + km+1 0 + km+1 mod (2ak k2 1)= km+1 mod (2ak k2 1).

Luego el lema es valido para todo n.

Lema 2.3.6. Xa(n) e Ya(n) son primos relativos.

Demostracion: Por la ecuacion (2,4), tenemos que:

[Xa(n)]2 (a2 1)[Ya(n)]2 = 1,

que es equivalente a

Xa(n)[Xa(n)] + [(a2 1)Ya(n)]Ya(n) = 1,luego existen enteros = Xa(n) y = (a2 1)[Ya(n)] tales que

Xa(n) + Ya(n) = 1.

Por lo tanto, Xa(n) e Ya(n) son primos relativos.

Lema 2.3.7.Ya(n) | Ya(k n) Ya(n) | Ya(k). (2.12)

Demostracion: Supongamos que Ya(n) | Ya(k n), entoncesYa(n) | [Ya(k)Xa(n)Xa(k)Ya(n)],


pero tambien tenemos que Ya(n) | Xa(k)Ya(n), asiYa(n) | {[Ya(k)Xa(n)Xa(k)Ya(n)]Xa(k)Ya(n)} = Ya(k)Xa(n).

Pero Xa(n) Ya(n), por el lema 2.3.6, luego, Ya(n) | Ya(k). SiYa(n) | Ya(k),

entonces Ya(n) | Ya(k)Xa(n), y como Ya(n) | Xa(k)Ya(n), tenemos queYa(n) | [Ya(k)Xa(n)Xa(k)Ya(n)] = Ya(k n).

Ahora expondremos una propiedad de divisibilidad que necesitaremos mas adelante.

Lema 2.3.8.n | m Ya(n) | Ya(m). (2.13)

Demostracion: Sea m = ni + r donde 0 r < n. Entonces 0 = Ya(0) Ya(r) 1, existeD,H Z, tal que:

D2 (a2 1)y2 = 1, H n mod 2y.Es decir, por la ecuacion (1,7):

y = Ya(n)(D)[D2 (a2 1)y2 1 = 0] y(H, x)[(H n 2yx)(H n+ 2yx) = 0].

Por las propiedades (1,6) y (1,8), la anterior expresion es equivalente a:

y = Ya(n) (D,H, x)[(D2 (a2 1)y2 1)2+ (H n 2yx)2(H n+ 2yx)2 = 0].

Repetimos el procedimiento para las demas variables necesarias y las juntamos demanera analoga a las ya vistas usando el lema 2.3.14 reiteradamente. As, en virtudde la definicion 1.2.2 , tenemos que la relacion, y = Ya(n), es diofantina.

35

COEFICIENTES EXPONENCIALES Y BINOMIALES 36

De manera analoga, podemos ver que la relacion x = Xa(n) es diofantina, usando ellema 2.3.14 y la ecuacion (2,4). Usando el procedimiento anterior podemos ver queotras relaciones son diofantinas. Saber que y = Ya(n) y x = Xa(n) son diofantinases util para ver que las relaciones m = kn y m =

(nk

)tambien lo son, usando la

ecuacion (1,10) y (1,11).

3.2. Relaciones exponenciales y binomiales

Lema 3.2.1. Si 2 k entonces, kn < (2k 1)n.Demostracion: Evidente.

Lema 3.2.2. Sea 1 n, 2 k. Supongamos que existe a tal que a Yk(n + 1),entonces:

kn = rem(Xa(n) (a k)Ya(n), 2ak k2 1). (3.1)Demostracion: De la ecuacion (2,10) y del lema 3.2.1 tenemos que:

k kn < (2k 1)n < Yk(n) a,luego tenemos que k < a y kn < a, as k + 1 a, por lo tanto,

a < ak < ak + k 1 = ak + k2 k2 + k 1= ak + k(k + 1) k2 1 ak + ak k2 1= 2ak k2 1.

As tenemos que kn < 2ak k2 1, pero por el lema 2.3.5,kn Xa(n) (a k)Ya(n) mod 2ak k2 1

luego, por la ecuacion (1,10) tenemos que:

kn = rem(Xa(n) (a k)Ya(n), 2ak k2 1). (3.2)

Por el lema 3.2.2, m = kn si y solo si, existe a tal que:

kn Xa(n) (a k)Ya(n) mod 2ak k2 1, m


Teorema 3.2.1 (Teorema generalizado del Binomio). Sea A un anillo con-mutativo con unidad, entonces para a, b A y n N tenemos que:

(a+ b)n =n

k=0

(n

k

)ankbk,

(n

k

)=

n!

k!(n k)! . (3.4)

Demostracion: La demostracion es analoga a la del caso real.

Lema 3.2.3. Sea n 0, entonces:

2n =n

k=0

(n

k

)(3.5)

Demostracion: Por la ecuacion (3,4) tenemos que:

2n = (1 + 1)n =n

k=0

(n

k

)1nk1k =

nk=0

(n

k

)

Definicion 3.2.1. Sea x R, el numero [x] se denomina la parte entera de x, elcual es el mayor entero menor o igual que x.

Lema 3.2.4. Sea y = a+ x con a Z y x R, entonces:[y] = a+ [x].

Demostracion: Evidente.

Ahora veremos que el coeficiente binomial, m =(nk

), es una relacion diofantina.

Lema 3.2.5. Para 0 k < n y u > 2n tenemos que:(n

k

)= rem

([(1 + u)n

uk

], u

). (3.6)

Demostracion: Por la ecuacion (3,4) tenemos que:

(1 + u)n

uk=

ni=0

(ni

)1niui

uk=

k1i=0

(ni

)ui

uk+

(nk

)uk

uk+

ni=k+1

(ni

)ui

uk

=k1i=0

(n

i

)uik +

(n

k

)+

ni=k+1

(n

i

)uik.


Ahora, si i k 1, es trivial ver que uik+1 1, as uik 1u, luego por la anterior

afirmacion y (3,5) tenemos que:

k1i=0

(n

i

)uik

k1i=0

(n

i

)1

u 1u

ni=0

(n

i

)=

2n

u< 1. (3.7)

Por lo tanto, usando el lema 3.2.4,[(1 + u)n

uk

]=

[k1i=0

(n

i

)uik

]+

(n

k

)+

ni=k+1

(n

i

)uik

= 0 +

(n

k

)+

ni=k+1

(n

i

)uik

=

(n

k

)+ u

ni=k+1

(n

i

)uik1.

As, [(1 + u)n

uk

](n

k

)mod u, (3.8)

pero es evidente que(nk

) 2n < u, as usando (1,10) tenemos que:(n

k

)= rem

([(1 + u)n

uk

], u

).

Por el lema 3.2.5 existe y tal que q (nk

)= uy, donde q =

[(1+u)n

uk

], as, por

la ecuacon (1,11), existe x < uk, tal que uk = (1 + u)n quk + x, luego, uk =(1 + u)n [uy + (n

k

)]uk + x. Entonces (1 + u)n = yuk+1 + uk

(nk

)+ (uk x). Por lo

tanto, m =(nk

)si y solo si, existen u, x e y tales que:

(1 + u)n = yuk+1 +muk + (uk x), m < u, x < uk y 2n < u. (3.9)

Por los lemas 3.2.5, 3.2.2, 2.3.14 y las ecuaciones (1,10) y (1,11), tenemos que lerelacion binomial, m =

(nk

), es diofantina. Enunciaremos un teorema que nos sera de

gran ayuda mas adelante.


Teorema 3.2.2. Sea g > 1. Entonces cada entero a > 0 se puede expresar demanera unica en la forma:

a = c0 + c1g + c2g2 + ...+ cng

n (3.10)

donde, 0 ci < g con 0 i n.La demostracion del teorema ?? es algo extensa y tecnica. Esta prueba se puedeencontrar con todos los detalles en [?] o en [?].Cuando a 0 tiene la forma (3,10), se dice que a esta escrito en base g, a los valores cise le denominan los dgitos de a en base g. Dada la unicidad que garantiza el teorema??, dos numeros escritos en base g son iguales si y solo si sus correspondientes dgitosson iguales.

Definicion 3.2.2. Sean r y s dos enteros no negativos escritos en base 2 (base bina-ria). Entonces r s si cada dgito binario de r es menor o igual que el correpondientedgito de s, es decir, si

r = r0 + r12 + r222 + ...+ rn2

n

ys = s0 + s12 + s22

2 + ...+ sn2n

entoncesr s ri si, para 0 i n.

La relacion, , se le denomina bit masking1. Es facil ver que esta relacion es unarelacion de orden parcial, es decir reflexiva, antisimetrica y transitiva. Ademas, sir s entonces r s. A partir de esta nueva relacion podemos definir la conjuncionlogica de dos numeros y viceversa de la siguiente manera:

a b a b = a, (3.11)

a b = c c a y a a+ b c. (3.12)Ahora recordaremos algunas definiciones y resultados del Algebra y la Teora deNumeros.

1Este termino es propio de los autores del artculo que se basa este documento. No encontre unatraduccion apropiada para este termino (Nota del autor).


Definicion 3.2.3. Sea p un primo, Zp es el conjunto definido por:

Zp = {0, 1, ..., p 1} (3.13)

donder = {a Z : a r mod p}. (3.14)

Luego, si a r, entonces a = r. Se puede definir una suma y un producto sobre Zpde la manera natural:

r s = rs, r s = r + s (3.15)

Un ejercicio clasico del algebra, es ver que (Zp,,) es un anillo con identidadconmutativo.

Definicion 3.2.4. Sea p un primo, Zp[x] es el conjunto de los polinomios en x concoeficientes en Zp.

Con las operaciones de suma y producto de Zp es facil ver que (Zp[x],,) es unanillo con identidad conmutativo.

Lema 3.2.6. Sea p primo y 0 k < p, entonces:(p

k

) 0 mod p. (3.16)

Con este lema y el teorema generalizado del binomio, es facil probar el siguientelema:

Lema 3.2.7. Sean x, y Z y p primo, entonces:

(a+ b)p ap + bp mod p, (3.17)

as (a+ b)p = ap + bp en Zp, luego esto tambien es cierto en Zp[x]

Los siguientes resultados permitiran ver que es diofantina.Lema 3.2.8 (H. Anton). Sea p un primo. Supongamos que 0 b < p y 0 d < p,entonces (

ap+ b

cp+ d

)(a

c

)(b

d

)mod p. (3.18)


Demostracion: Trabajemos en el anillo Zp[x], por la igualdad (x+ y)p = xp + ypy por el teorema generalizado del Binomio tenemos que:

ap+bn=0

(ap+ b

n

)xn = (1 + x)ap+b

= (1 + x)ap(1 + x)b

= (1 + xp)a(1 + x)b

=

[a

j=0

(a

j

)xjp

][b

i=0

(b

i

)xi

].

El coeficiente de xcp+d debe ser el mismo en ambos polinomios, es decir, cuandojp+i = cp+d, entonces, (jc)p = (di). Por lo tanto p | (di), pero 0 i b < py 0 d < p entonces d i < p, luego d i = 0, asi d = i, asi j = c. En consecuencia,el coeficiente de xcp+d en ambos lados son

(ap+dcp+d

)y(ac

)(bd

), entonces

(ap+dcp+d

)=(ac

)(bd

)en Zp[x], as (

ap+ d

cp+ d

)(a

c

)(b

d

)mod p.

Teorema 3.2.3 (E. Lucas). Sea p primo, s y r enteros no negativos escritos enla forma:

r = r0 + r1p+ r2p2 + ...+ rnp

n,

ys = s0 + s1p+ s2p

2 + ...+ snpn

entonces, (s

r

)(snrn

) (s0r0

)mod p. (3.19)

Demostracion: Por induccion sobre n. La congruencia es valida para n = 1 por ellema 3.2.8 . Supongamos valida la congruencia para n = k, y veamos que es valida


para n = k + 1.(s

r

)=

(s0 + s1p+ s2p

2 + ...+ skpk + sk+1p

k+1

r0 + r1p+ r2p2 + ...+ rkpk + rk+1pk+1

)=

(s0 + (s1 + s2p+ ...+ skp

k1 + sk+1pk)pr0 + (r1 + r2p+ ...+ rkpk1 + rk+1pk)p

)(s1 + s2p+ ...+ skp

k1 + sk+1pk

r1 + r2p+ ...+ rkpk1 + rk+1pk

)(s0r0

)mod p (Por el lema 3.2.7)

(s1r1

) (sk+1rk+1

)(s0r0

)mod p ( Por hipoteis de induccion)

=

(s0r0

)(s1r1

) (sk+1rk+1

)mod p.

La congruencia es entonces valida para n = k + 1, por lo tanto, es valida para todon.

Usando la definicion de(nk

)y que

(n+1k

)=(nk

)+(

nk1)es facil ver que:(

1

1

)= 1,

(1

0

)= 1,

(0

0

)= 1,

(0

1

)= 0 (3.20)

Lema 3.2.9. Sean r, s Z, escritos en base 2, entonces:

r s(s

r

) 1 mod 2. (3.21)

Demostracion: Sear = r0 + r12 + ...+ rn2

n

ys = s0 + s12 + ...+ sn2

n,

los valores de ri y si con 0 i n solo pueden ser 0 o 1. Haciendo p = 2 en elteorema 3.2.3 tenemos que:(

s

r

)(snrn

) (s0r0

)mod 2.

Como r s entonces ri si , luego no se dara el caso(siri

)=(01

)= 0, por lo tanto,

todos los valores de(siri

)son iguales a 1, as(

s

r

) 1 mod 2.


Del lema 3.2.9, junto con el lema 3.2.5 y la ecuaciones (1,10) y (1,11) se concluyeque, es diofantina.

Captulo 4

Aritmetizacion de maquinasilimitadas de registro

What shall we think of an engine of wood and metal which can notonly compute astronomical and navigation tables to any given extent, butrender the exactitude of its operations mathematically certain through itspower of correcting its possible errors?...

Edgar Allan Poe, Maelzels Chess-Player.

4.1. Maquinas ilimitadas de registro, programas

y funciones calculables

La idealizacion matematica de un computador que usaremos todo el tiempo se de-nomina maquina ilimitada de registro (URM)1. La URM tiene un infinito numerode registros, R1, R2, R3, R4, R5, R6..., cada uno de los cuales contiene a la vez, encualquier momento, un entero no negativo o cero. Denotamos como rn el valor con-tenido en Rn. Esto puede ser representado de la siguiente manera:

R1 R2 R3 R4 R5 R6 ...r1 r2 r3 r4 r5 r6 ...

Los contenidos de los registros pueden ser alterados por la URM en respuesta aun numero finito de ciertas instrucciones. Estas instrucciones las designamos como:

1En ingles: Unlimited Register Machine.

44

ARITMETIZACION DE MAQUINAS ILIMITADAS DE REGISTRO 45

L1, L2, L3..., Ls. Describimos el funcionamiento de una URM por medio de estasinstrucciones bajo un programa, P = {L1, L2, L3, ..., Ls}. Un programa realiza lasintrucciones de manera ordenada, segun el correspondiente ndice de la instruccion.Veamos las instrucciones que usaremos de aqu en adelante.

Li SI Rj = 0, IR A Lk. (4.1)

Li+1 SINO Rj Rj 1. (4.2)Estas instrucciones comprueban que el contenido de un registro sea cero; si lo es, setransfiere a la instruccion Lk; de lo contrario, substrae 1 de dicho valor. Es evidenteque en esta intruccion nunca se substrae 1 de cero.

Instr. Comando Interpretacion Enum.Li IR A Lk Se transfiere a la instruccion Lk (4.3)Li SI 0 < Rj, IR A Lk Transferencia condicional a Lk (4.4)Li Rj Rj + 1 Incrementa en 1 el valor contenido en Rj (4.5)Li Rj Rj 1 Decrementa en 1 el valor contenido Rj (4.6)

La URM, bajo un programa P = {L1, L2, L3, ..., Ls}, procede hasta donde sea posi-ble; la computacion se detiene unicamente cuando no existe intruccion siguiente; esdecir, la URM se detiene cuando se solicita la instruccion Lk y Lk 6 P o k > s.Decimos que el calculo se detiene despues de la instruccion Lk. Los valores inicialesde R1, R2, ... al comenzar el calculo de la URM se denominan, configuracion inicialo entrada de la URM. Los valores de R1, R2, R3, ..., al terminar el calculo de la URMse denominan, configuracion final o salida de la URM. . Daremos algunas notacionesque seran utiles mas adelante.

Definicion 4.1.1. Sea una URM bajo un programa P , sea r1, r2, ... una sucesionde numeros naturales, entonces:

1. P (r1, r2, ...) expresa que el calculo bajo P , tiene configuracion inicial r1, r2, ....

2. P (r1, r2, ...) expresa que el calculo P (r1, r2, ...) se detiene.3. P (r1, r2, ...) expresa que el calculo P (r1, r2, ...) nunca se detiene.

Nosotros solo consideraremos la configuracion inicial de la URM finita; estoes, solo consideraremos finitos valores de entrada. As la siguiente notacion nossera muy util. Sea r1, r2, ..., rn N, entonces:

4. P (r1, r2, ..., rn) es equivalente a P (r1, r2, ..., rn, 0, 0, 0, ...).


5. P (r1, r2, ..., rn) expresa que P (r1, r2, ..., rn, 0, 0, 0, ...) .6. P (r1, r2, ..., rn) expresa que P (r1, r2, ..., rn, 0, 0, 0, ...) .

Ejemplo 4.1.1. Una URM que calcula el n-esimo numero de la sucesion de Fi-bonacci. Esta sucesion esta definida por medio de F0 = 0, F1 = 1, y Fx = Fx1 +Fx2, si x 2. Los primeros ocho valores de esta sucesion son: 0,1,1,2,3,5,8,11,.... Se han escrito dos o mas comandos en una misma instruccion para simplificar laprueba.

L1 SI R1 = 0, IR A L20.

L2 R2 R2 + 1, R3 R3 + 1.L3 R1 R1 1.L4 SI R1 = 0, IR A L16.

L5 R1 R1 1.L6 R4 R4 + 1, R5 R5 + 1.L7 R3 R3 1.L8 SI 0 < R3 IR A L6.

L9 R4 R4 + 1, R2 R2 1.L10 SI 0 < R2, IR A L9.

L11 R3 R3 + 1, R4 R4 1.L12 SI 0 < R4, IR A L11.

L13 R2 R2 + 1, R5 R5 1.L14 SI 0 < R5, IR A L13.

L15 SI 0 < R1, IR A L5.

L16 R3 R3 1.L17 SI 0 < R3, IR A L16.


L18 R2 R2 1, R1 R1 + 1.L19 SI 0 < R2, IR A L18.

En el ejemplo 4.1.1 el numero de registros necesarios es 5, el numero de instrucciones19, en realidad se necesitan 20 instrucciones; la instruccion 20 se usa para detenerel programa. La configuracion inicial es: en R1 esta x, el ndice del numero deFibonnaci que se quiere calcular, y en los demas registros cero; la configuracionfinal es: en R1 esta Fx, el numero de Fibonnaci correspondiente al valor inicial ycero en los demas registros. Si la configuracion inicial es P (2, 0, 0, 0, 0), tenemos losresultados resumidos en la tabla 4.1.1, los cuales se obtuvieron al implementar elprograma del ejemplo 4.1.1 en C2.Supongamos ahora que f es una funcion de Nn a N, que hace que f sea calculablepor una URM?. Lo mas natural es ver si es posible calcular f(r1, ..., rn) por medio deuna URM bajo un programa P , con una configuracion inicial r1, ..., rn, 0, 0, .... Estoes, consideraremos un calculo de la forma P (r1, ..., rn) y al final consideraremos(a menos que se diga otra cosa) unicamente el valor final de R1, y los demas losignoraremos. Tambien es posible que P (r1, ..., rn) nunca se detenga. As, definiremosla nocion de calculabilidad de funciones parciales de Nn a N, es decir, funciones fcuyo dominio no necesariamente es todo Nn.

Definicion 4.1.2. Sea f una funcion parcial de Nn a N.

1. Suponga P un programa , y sea r1, ..., rn, b N.a) El calculo P (r1, ..., rn) converge a b si P (r1, ..., rn) y la configuracion

final tiene a b en R1, esto lo denotamos como P (r1, ..., rn) bb) P URM-calcula a f si, para todo r1, ..., rn, b tenemos que: P (r1, ..., rn) b

si y solo si (r1, ..., rn) Dom(f) y f(r1, ..., rn) = b. (En particular, estodice que P (r1, ..., rn) si y solo si (r1, ..., rn) Dom(f)).

2. La funcion f es URM-calculable o URM-computable, si existe un programaque URM-calcule a f .

As, f es calculable o computable si es URM-calculable.

Definimos la clase de todas las funciones calculables por C, y la clase de la funcionesn-arias calculables por Cn.

2Un editor y compilador de programas. Se obtienen los mismos resultados usando Pascal, Basic,Matlab o cualquier otro compilador.


Paso Linea Ejecutada Valor R1 Valor R2 Valor R3 Valor R4 Valor R51 L1 2 0 0 0 02 L2 2 0 0 0 03 L3 2 1 1 0 04 L4 1 1 1 0 05 L5 1 1 1 0 06 L6 0 1 1 0 07 L7 0 1 1 1 18 L8 0 1 0 1 19 L9 0 1 0 1 110 L10 0 0 0 2 111 L11 0 0 0 2 112 L12 0 0 1 1 113 L11 0 0 1 1 114 L12 0 0 2 0 115 L13 0 0 2 0 116 L14 0 1 2 0 017 L15 0 1 2 0 018 L16 0 1 2 0 019 L17 0 1 1 0 020 L16 0 1 1 0 021 L17 0 1 0 0 022 L18 0 1 0 0 023 L19 1 0 0 0 024 L20 1 0 0 0 0

Cuadro 4.1: Datos obtenidos al ejecutar el programa del ejemplo 4.1.1 .


Es posible que se utilice otro registro como entrada-salida diferente a R1, sin embargola definicion ?? es tambien valida para este registro.Por lo tanto, la funcion f(x) = Fx, que calcula el x-esimo numero de la sucesion deFibonacci es calculable por la URM M , del ejemplo 4.1.1.

4.2. Aritmetizacion de una URM

Para aritmetizar el trabajo de una URM, usaremos los dgitos de un numero escritoen base Q, donde Q es potencia de 2, denotemos esto como: Q pow 2.Consideremos la URM del ejemplo 4.1.1, o mas en general M , una URM con rregistros y l lneas en su correspondiente programa. Asumamos que M calcula com-pletamente la funcion y = f(x). Observemos que las instrucciones que establecimosen la seccion 4.1 a lo sumo aumentan en 1 los valores de los registros en cada pasot; luego, si el programa ha realizado s pasos en su calculo, entonces a lo sumo seaumentaran los valores de los registros en s. As el valor del registro Ri, llamemoslori, sera menor o igual a ri + s. Si la configuracion inicial tiene el valor x en R1 yceros en los demas registros, entonces, cada valor en Ri sera siempre menor o iguala x+ s. Por lo tanto, el maximo valor de todos los registros es x+ s.Supongamos que M obtiene el valor de y = f(x) despues de s pasos. Sea ri,t el valoren el registro Ri en el paso t, durante el proceso del calculo. Si Q es lo suficientementegrande tal que, ri,t < Q, entonces podemos considerar los valores ri,t como dgitos deun numero escrito en base Q. Aunque necesitamos ser mas exigentes (mas adelanteveremos la justificacion); necesitamos que 2ri,t < Q, es decir ri,t

Teseo Decimo Problema de Hilbert

Documents

Transcript of Teseo Decimo Problema de Hilbert