sábado, 3 de enero de 2009

La Criba de Eratóstenes y La Llave de Oro

La fórmula que nos proporcione el número primo número n aún no se ha encontrado. El primer algoritmo para encontrar los números primos (del que se tenga constancia escrita) nos lo proporcionó el Griego Eratóstenes (200 a.C) el procedimiento es muy sencillo:

Sobre la tabla de todos los números naturales menos el número 1 (al ser trivial que cualquier numero es divisible por él) y el siguiente número no tachado (en este caso el 2) se escoge como un primo, y a continuación se empieza a tachar toda su tabla de multiplicar (4,6,8,10,12,14,16...) como muestra la figura1:
Una vez hecho esto (hasta el número que se desee, en este caso hasta el 200), se escoge el siguiente elemento no tachado como el siguiente primo, en este caso el 3, y se procede a tachar los elementos no tachados ya de su tabla, tal y como muestra la figura:


Repitiendo el proceso para el siguiente que es el 5,… y para el siguiente que sería el 7, 11, 13, y así sucesivamente

Como vemos es un procedimiento muy sencillo tanto para realizar a mano como muy fácilmente implementable en un ordenador. Siempre que se decida hacer hasta cierto número n. Por ejemplo, en la figura 2, está la tabla de números primos hasta n=1000. Los números tachados están en gris claro y los primos en negrita.

A simple vista se ve que es una distribución muy caprichosa (a estas escalas más aún). Entre los diez numeros anteriores a 100 hay sólo un primo (el 97), en cambio entre los 10 siguientes hay cuatro (101, 103, 107 y 109). Y así sucede hasta donde hemos podido comprobar con los más potentes ordenadores.



Otra propiedad que se ve a simple vista es que se van "espaciando" cada vez más: la distancia entre un primo y el siguiente si bien parece caprichosa no deja en promedio de aumentar. Hay un límite: se ha demostrado que entre n y 2n siempre hay al menos un número primo.

Se puede ver positivamente: siempre encontraremos un número primo a partir de un número n dado, por grande que n sea. La primera demostración de que hay infinitos números primos ya la dió Euclides en su Libro IX de los Elementos. La demostración como de costumbre parte del supuesto contrario: si tuviera un número limitado de números primos: p1, p2, p3, ...pk. Siempre podría crear un nuevo número multiplicando todos los primos y sumandole uno, que no sería divisible por ninguno de ellos y por tanto sería primo, lo cual es absurdo porque hemos dicho que ya no había más... luego su número no tiene fin.


O negativamente: Siempre podremos encontrar un intervalo de números de una longitud todo lo grande que queramos sin que haya un sólo número primo dentro en él, por grande que éste sea.

Otra pregunta muy natural y que surge de manera casi inmediata: ¿cuántos números primos hay hasta ese número n? En los casos de arriba con n=100, 200 y 1000, tenemos respectivamente π(100)=25, π(200)=46, π(1000)=168. Esto se conoce como función π(n) y se lee como Pi de n. Gauss fue el primero en ver con su “buen ojo” para las matemáticas que se aproximaba al n/log(n). La historia cuenta que los libros o cuadernos matemáticos de la época solían terminar con tablas de primos y de logaritmos, fue su intuición la que asoció ambas. Después afinó la función aún más con el logaritmo integral Li (una función que no tiene expresión algebraica propia o aún no se ha encontrado, es el área bajo la curva de la función logaritmo, o sea la integral definida bajo la misma desde 2 hasta infinito). De todo esto hablaremos en otra entrada.
Ya volveremos sobre el número de primos menores que un determinado número n, o lo que es casi los mismo la probabilidad de encontrar un número primo menor que n.

Vamos a ver como el siempre absolutamente genial Euler inventó una forma matemáticamente muy elegante de hacer la misma criba. Más tarde Riemann cogió esta fórmula casi olvidada ( o mejor camuflada entre la ingente cantidad de obra publicada por tan prolífico genio) y la extendió a los números complejos, (también la ajustó para que estuviera definida en todo el plano complejo en vez de sólo en el semiplano con Re(S)>1). La haremos pues con la variable S.

Partimos de la función Zeta ζ(S)




(1)


Tal y como vemos es la suma del inverso de todos los números naturales elevados a un mismo número S. Está definida para todos los números estrictamente mayores que 1, ya que en S=1 nos daría la serie armómica que es divergente. Si S=2 tenemos la famosa serie de la inversa de los cuadrados cuya resolución dio fama mundial al jóven Euler, por resolver el famoso “problema de Basilea” (de donde era original al igual que la familia Bernulli quienes acometieron el problema sin éxito al igual que todos los mejores matemáticso del momento) con tan sólo 28 años y demostró que:

ζ(2)= π^2/6

La demostración es una de mis favoritas, y la pondré al final. Lo mejor de todo es que no se molestó en demostrar que todos y cada uno de los pasos seguidos se podían dar con rigor, siguió su instinto e intuición y algún tiempo después dió una demostración rigurosa él mismo.

Multiplicamos la expresión (1) por (y obtenemos la tabla del 2 invertida):



(2)


Ahora viene la idea buena, restamos a la expresión (1) la expresión (2), o sea, a todos los números (invertidos) le restamos (tachamos) la tabla del 2 ,primer primo, (aunque todo invertido, pese a que ya no se diga en adelante). Y obtenemos la siguiente expresión:



(3)


Multiplicamos la expresión (3) por (el siguiente primo, o número no tachado, el tres):



(4)


Ahora le restamos a los que nos quedaban, expresión (3), la expresión (4) (como antes pero ahora restamos la tabla del 3) y obtenemos:



(5)


Repetimos el proceso para todos los primos… de esta manera los vamos pasando a la izquierda y vamos cribando, vamos tachando en la derecha hasta que sólo quedaría el uno (quedaría demostrar que la serie efectivamente converge a 1, pero hagamos como Euler en su día y avancemos...)



(6)

Despejando ζ(S) obtenemos:



(7)



Que puesto de una manera más cómoda y elegante:




Donde tenemos el producto de todos los términos recorriendo todos los números primos.

La idea es muy potente, aunque parezca sólo una manera más adecuada de expresar la idea de la Criba de Eratóstenes. Relaciona la suma de todos los números con el producto de todos los primos. Suma con producto, ¿alguien recuerda que herramienta matemática permite convertir multiplicaciones en sumas? Sí, el logaritmo de un producto es suma de logaritmos (antes de que hubiera calculadoras, las tablas de logaritmos permitían realizar una engorrosa multiplicación de dos números grandes en una siempre y cómoda suma, sin más que consultar las tablas). La idea intuitiva de Gauss parece que estaba en el aire…

En la siguiente entrega os contaré qué descubrió Riemann al pasarla al dominio complejo: Un fantástico paisaje se desplegó ante sus ojos (tal vez los más imaginativos que ha habido en toda la historia de la matemática para ver superficies y curvas en el espacio) con un enorme monte que emergió ante él subiendo hasta los cielos situado en S=1 (único punto en el que la función Zeta de Riemann se hace infinito).



¡Un saludo y FELIZ AÑO NUEVO Elementales!
PD. Poniendo los primeros números primos uno tras otro hasta n=1000 resulta la siguiente lista

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.