La conjetura de Gilbreath

Consideramos la sucesión de los primos puestos en fila. Debajo escribimos las diferencias entre ellos\(.\)  $$\begin{array}{ccccc cccccccccc} 2&&3&&5&&7&&11&&13&&17&&19\\ &1&&2&&2&&4&&2&&4&&2\\&&1&&0&&2&&2&&2&&2\\&&&1&&2&&0&&0&&0\\&&&&1&&2&&0&&0\\&&&&&1&&2&&0\\&&&&&&1&&2\\&&&&&&&1\end{array}$$ Continuamos el proceso formando una tercera fila, pero restando el menor del mayor, para que todos sean no negativos. Repetimos este proceso indefinidamente. Proth en 1878 observó que todas las filas obtenidas de este modo comienzan con un 1. Muchas fuentes informan que Proth creyó tener una prueba, que no era correcta. Más adelante volveré sobre esto para no interrumpir ahora el desarrollo.

La tercera fila hasta donde la hemos escrito está formada por el \(1\) al principio y después todos \(0\) y \(2\). Esto implica que las restantes filas de todo el triángulo de números estará formado por ceros y doses salvo los unos situados al principio. Esta observación es clave, pero debemos notar que en cualquier fila, si la continuamos suficientemente vamos a encontrar números distintos del \(0\) y el \(2\). 

¿Cómo de convencidos estamos de la conjetura?

La primera reacción que podemos tener es de incredulidad. Tomamos la sucesión de los primos. Formamos las diferencias sucesivas, cambiando su signo cuando salgan negativas y después de todo ¿obtenemos una fila de unos! ¿Por qué? 

De manera que nos ponemos a la tarea de comprobar la conjetura. Las ideas matemáticas simples reaparecen espontáneamente. En 1958 Norman L. Gilbreath, un estudiante de matemáticas en la Universidad de California, tratando de encontrar un método de generar primos construyó el cuadro de las diferencias en valor absoluto y volvió a notar la propiedad de la primera fila de unos. Otros dos compañeros, R. B. Kilgrove y K. E. Ralston, aprovecharon que uno de los primeros computadores, el SWAC, estaba situado en UCLA y comprobaron la conjetura para la fila de los primeros 63419 primos. Ellos ya notaron que si en una fila todos los números hasta el \(n\)-ésimo, salvo el primero que es un 1, son iguales a \(0\) o \(2\) entonces las siguientes \(n-1\) filas comienzan con un \(1\). Esto disminuye bastante el número de operaciones necesarias para confirmar la conjetura. Su proeza es más notable si miramos lo que eran los ordenadores en los años 50 del siglo pasado.

El ordenador SWAC donde Kilgrove and Ralston comprobaron la conjetura.

Los resultados de Odlyzko.

Los ordenadores eran bastante más potentes en 1993. Odlyzko consiguió probar que la conjetura es cierta para todos los primos \(<10^{13}\), aproximadamente \(3.4\times10^{11}\) primos.

Consideremos la fila de los primeros \(n\) primos y vayamos formando filas hasta que lleguemos a una fila \(k\) que excepto por el primer elemento \(=1\) esté formado por \(0\) y \(2\). Diremos que \(G(n)=k\). Por ejemplo la tabla que formamos antes prueba que \(G(8)=2\). Esta función crece muy lentamente, Odlyzko nota que \(G(\pi(10^{13}))=635\). Esto es, solo se necesitan calcular 635 filas de diferencias para demostrar que todos los primos \(p\le 10^{13}\) satisfacen la conjetura de Gilbreath.

Así que, aunque con los primos debemos ser muy precavidos, sí, los cálculos llevan a pensar que la conjetura de Gilbreath es cierta.

¿Qué tienen que ver los primos con esto?

Gilbreath es también conocido como mago. Hay un método de barajar cartas que lleva su nombre. Otro mago, Martin Gardner, llevaba una sección de juegos matemáticos en la revista Scientific American. En 1980 uno de los artículos de Gardner se dedicó a la conjetura de Gilbreath. Sorprendió allí presentando las ideas de Hallard Croft. Mantenía este matemático que la propiedad no tiene mucho que ver con los primos. Dada una sucesión arbitraria \((a_n)\) de números enteros podemos construir una nueva sucesión transformada \((b_n)\) mediante el proceso de las diferencias sucesivas en valor absoluto. Por ejemplo $$\begin{array}{ccccc ccccc ccccc} 5&&8&&9&&11&&27&&33&&71&&75\\ &3&&1&&2&&16&&6&&38&&4\\ &&2&&1&&14&&10&&32&&34\\ &&&1&&13&&4&&22&&2\\ &&&&12&&9&&18&&20\\ &&&&&3&&9&&2\\ &&&&&&6&&7\\ &&&&&&&1 \end{array}$$ la sucesión transformada \((b_n)\) en este caso es \(5\), \(3\), \(2\), \(1\), \(12\), \(3\), \(6\), \(1\), …  que obviamente no satisface la conjetura, pues la original es bastante arbitraria.

Croft mantenía que cualquier sucesión que empiece por \(2\) y continúe con números impares en orden creciente y tal que las primeras diferencias no sean muy grandes cumplirá la misma propiedad que los primos: la sucesión transformada verificará que \(b_n=1\) para \(n>1\). Esto es, que lo observado por Proth y Gilbreath prácticamente no es una propiedad de los primos. 

Estrictamente la afirmación de Croft es falsa. De hecho Odlyzko es más cauto y tan solo afirma que una sucesión que empiece por \(2\) seguida por una sucesión creciente de números impares generados con incrementos pequeños y aleatorios tendrá una sucesión transformada \((b_n)\) tal que \(b_n=1\) para \(n\ge n_0\), siendo \(n_0\) dependiente de la sucesión elegida. Es decir, que la conjetura se cumplirá a partir de un término en adelante.

Modos de atacar la conjetura.

Erdös dijo en algún momento que la conjetura de Gilbreath era cierta pero que se tardaría al menos 200 años en probar. Una afirmación sorprendente ya que hay muchos caminos por explorar. Por ejemplo dada una sucesión finita $$p_1, p_2,\dots, p_n, q$$ donde los \(p_j\) son los primeros primos, ¿qué valores de \(q\) satisfacen la conjetura? Mis experimentos me hacen ver que cualquier \(q\) impar en un cierto intervalo satisface la conjetura. Por ejemplo, tomando todos los primos hasta \(p_{4000}=37813\) cualquier número impar \(q\) tal que \(33667\le q\le 41959\) cumpliría la conjetura. Uno sabe que el siguiente primo es \(\le p_n+p_n^{0.525}<38067\). Esto indica un posible camino de ataque de la conjetura. 

Otra posibilidad es atacar una variante más asequible. Una propuesta muy atractiva es la de David Eppstein: la conjetura de Gilbreath para los números prácticos.

He propuesto a veces a mis alumnos en la asignatura de Teoría de Números el trabajo de estimar la probabilidad de que una sucesión como los primos verifique la conjetura. 

¿Qué sabemos de los primos? Mucho, pero en principio sabemos que un número grande \(x\) tiene probabilidad \(1/\log x\) de ser primo. Esta afirmación necesita una explicación. Si el número es par y grande su probabilidad de ser primo es nula. Lo que quiere decir la afirmación anterior es que si tomamos todos los números hasta \(x\) hay \(\pi(x)\) primos menores o iguales a \(x\). Luego si entendemos la probabilidad como cociente entre casos favorables partido por el total de casos, la probabilidad es $$\frac{\pi(x)}{x}\approx\frac{1}{\log x}.$$ Podemos también decir que si el número es par su probabilidad de ser primo es \(0\) y si es impar es \(\approx 2/\log x\).

Así podemos imaginar un modelo probabilístico para los primos.

Construimos una sucesión \((a_n)\) de pseudoprimos. Pondremos \(a_1=2\), \(a_2=3\) y para cada \(n\ge3\), pondremos \(a_n=a_{n-1}+2u_n\) donde \(u_n\) se escoge del conjunto \(\{1,2,3,\dots \lfloor \log n\rfloor\}\) aleatoriamente con igual probabilidad. Parándonos en \(\lfloor\log n\rfloor\) conseguimos que el valor medio de \(a_n\) sea \(n\log n\), así como el valor aproximado del primo \(n\)-ésimo es \(n\log n\)

Lo que yo le pedía a mis alumnos era estimar la probabilidad de que esos pseudoprimos verifiquen la conjetura de Gilbreath. Por el simple método de generar muchas sucesiones de pseudoprimos suficientemente larga y ver cuántas cumplen la conjetura. Con \(10000\) pruebas encontramos la probabilidad \(0.499\) de que se cumpla Gilbreath con este modelo. Odlyzko esperaba mas bien que existiera un \(M\) de manera que la sucesión transformada cumpliera que \(b_n=1\) para \(n\ge M\). Probando con nuestro modelo encontramos que la probabilidad de que \(b_n=1\) para \(n>10\) sube hasta \(0.9916\). Finalmente, entre las \(10000\) pruebas no encontramos ninguna que no cumpla la conjetura para \(n>40\). 

El trabajo de Zachary Chase.

Hasta este mes de mayo todo lo que se sabía sobre la conjetura de Gilbreath eran comprobaciones numéricas y conjeturas sobre probabilidades basadas en intuiciones. En mayo se ha publicado el trabajo de Chase A Random analogue of Gilbreath’s conjecture. Zachary Chase es un postgraduado de la Universidad de Oxford, dirigido por el Prof. Ben Green, el mismo que con Terry Tao demostró la existencia de progresiones aritméticas de primos de longitud arbitraria.

Chase usa unos pseudoprimos como antes, \(a_{n+1}=a_n+2u_n\), escogiendo \(u_n\) al azar de un conjunto \(\{1,2,\dots, f(n)\}\), y prueba que con probabilidad \(1\) existe un \(M\) tal que la sucesión transformada verifica \(b_n=1\) para \(n>M\).

Es decir, Chase ha probado casi lo que decía Odlyzko. La diferencia está solo en que Chase necesita suponer que \(f(n)\le \frac{1}{100}\frac{\log\log n}{\log\log\log n}\). El modelo de los primos tomaba \(f(n)=\lfloor\log n\rfloor\). Deberíamos ser capaces de mejorar el teorema de Chase para admitir funciones \(f(n)\) más grandes. 

¿Cómo es la prueba de Chase? Los experimentos numéricos muestran que la conjetura es cierta porque los términos más a la derecha, aparte de los \(1\) del principio son siempre \(0\) o \(2\). Lo que Chase prueba es que esto ocurre con probabilidad \(1\) a partir de un término en adelante. 

Primero observa que si \(a_{n+1}=a_n+2u_n\) entonces las primeras diferencias son \(1\), \(2u_2\), \(2u_3\), …  Podemos olvidarnos del primer \(1\) y dividir todo por \(2\). Debemos probar que después de un cierto número de iteraciones a partir de la sucesión \((u_n)\) escogidos aleatoria e independientemente, llegaremos a una sucesión de \(0\) y \(1\). 

El resultado básico es probar que si tomo \(M\) y \(C\) tal que \(3\le C\le \frac{1}{100}\frac{\log\log M}{\log\log\log M}\) y ahora tomamos al azar los \(u_1\), \(u_2\), …, \(u_M\) aleatoria e independientemente entre \(\{0, \dots, C-1\}\), entonces, con probabilidad muy grande (al menos \(1-e^{-e^{\sqrt[20]{\log M}}}\)), en una fila no muy alejada (la fila \(e^{\sqrt[5]{\log M}}\)) del proceso todo se reduce a \(0\) y \(1\). 

La prueba es un magnifico ejemplo de cómo funcionan las matemáticas puras. Estamos afilando las armas para enfrentarnos a lo desconocido. Este es un problema complicado de probabilidades que echaría para atrás al más experimentado. El interés va mas allá de probar la conjetura de Gilbreath. Se trata de un problema difícil y es por esto digno de ser atacado. Vamos mejorando nuestra capacidad de calcular probabilidades. No puede sorprender después que cuando un físico o ingeniero se enfrente con un problema, el matemático lo tenga resuelto a veces con cientos de años de ventaja. La matemática está siempre atenta para atacar los problemas que resultan complicados.

Destacaré un lema de la prueba de Chase que me parece una joya. Cómo convierte el problema en algo finito y combinatorio.

Lema. Supongamos que \(a_1\), \(a_2\),… \(a_n\) se escogen aleatoria e independientemente de entre \(\{0,1,\dots, C-1\}\) siendo \(n\ge (200C^2)^{2C}\) y realizamos el proceso de sucesivas diferencias en valor absoluto hasta que quede un solo número. La probabilidad de que este número sea un \(0\) es al menos \(\frac{1}{200C^2}\). 

Nouvelle Correspondance Mathématique.

Volvemos ahora sobre Proth, el primero que notó la propiedad. Nouvelle correspondence Mathématique fue una revista belga que se publicó desde 1874 hasta 1880. Fue fundada por Eugene Catalan y Paul Mansion. Su objetivo era la difusión de las matemáticas, publicaba problemas y soluciones del nivel de la agregación francesa (esto es, el examen para profesores de institutos de segunda enseñanza). También se trataba de difundir conocimientos, pero no la publicación de resultados originales. 

El tipo de revista me recuerda una tradición que viene de lejos. La Aritmética de Diofanto es una recopilación de problemas, todos con un cierto estilo, y sus soluciones. Leyendo a Diofanto uno imagina a un grupo de amantes de la Matemática planteando problemas y retándose a resolverlos. Es en un ambiente análogo, el que crea la revista Nouvelle Correspondance, en el que surge la idea de Proth. Como un problema que se sale de las capacidades del grupo. Proth no era más que un granjero aficionado a las matemáticas. Autodidacta y ciertamente no muy sofisticado. Se le recuerda por un criterio de primalidad para números de la forma \(N=2^n h+1\), primos que se denominan primos de Proth. También le debemos la conjetura de Gilbreath y el hermoso teorema de que si ponemos \begin{align*} x&=a^2+b^2+ab\\ y&=c^2+d^2+cd\\ z&= (a+c)^2+(b+d)^2+(a+c)(b+d)\\ t&=a^2+c^2+ac\\ u&=b^2+d^2+bd\\ v&=(a+b)^2+(c+d)^2+(a+b)(c+d) \end{align*} entonces \begin{align*} x+y+z&=t+u+v\\ x^2+y^2+z^2&=t^2+u^2+v^2\\ xy+xz+yz&=tu+uv+vt \end{align*} Por cierto, el problema de encontrar números \(x\), \(y\), \(z\), \(t\), \(u\), \(v\) verificando las tres ecuaciones anteriores tiene todo el estilo de los problemas de Diofanto. Todo esto son no pocos recuerdos para un granjero.

No obstante, la conjetura se recuerda como la conjetura de Gilbreath y no hay nadie que la presente y no diga que Proth creyó tener una prueba que no era correcta. Al escribir la entrada, debido al resultado de Chase, tuve interés en ver cuál era la prueba fallida de Proth. Me llevé una sorpresa. Los que hablan de la prueba fallida citan uno de los dos siguientes trabajos:

F. Proth, Théorèmes sur les nombres premiers, Comp. Rend. Acad. Sci. Paris, 85 (1877), 329-331.

F. Proth, Sur la série des nombres premiers, Nouvelle Correspondance Mathématique, 4 (1878) 236-240.

Pero si uno busca el tomo y la página de la primera referencia encuentra otro artículo

F. Pepin, Sur la formule \(2^{2^n}+1\), Comp. Rend. Acad. Sci. Paris, 85 (1877), 329-331.

que no tiene nada que ver con lo que nos ocupa. La segunda referencia sí que está dedicada a la conjetura. Es cierto que Proth lo presenta como un teorema, pero no presenta ninguna prueba. En su lugar Proth se dedica a sacar algunas consecuencias de su «teorema». Al final del artículo encontramos una nota firmada por E. C. (sin duda el editor de la revista Eugene Catalan) diciendo «¿no es cierto que los teoremas del Señor Proth que acabamos de leer son, más bien, postulados?».

Rebuscando en los tomos de Comptes Rendues encontramos una nota:

F. Proth, Théorèmes sur les nombres premiers, Comp. Rend. Acad. Sci. Paris, 87 (1878), 926.

pero se refiere a criterios de primalidad. Finalmente en el tomo  84 (1877) 259 dice: E. Proth somete a juicio de la Academia algunos teoremas nuevos sobre los números. En la página 92 leemos: E. Lucas dirige algunas observaciones críticas, sobre la materia de los teoremas sobre los números que han sido comunicados por F. Proth en la sesión del 27 de diciembre de 1876. 

Probablemente Lucas vio, que aunque no un teorema, Proth sí tenía una observación interesante. Por esto admitió la publicación en la revista menor aunque no dejó que la academia publicara el trabajo de Proth. 

Es un poco injusto no hablar de la intuición de Proth, que sin ordenadores tiene más mérito del que suponemos, y remachar que su prueba era errónea. Que yo sepa, nadie ha visto ninguna prueba errónea. Y además, nadie tiene una prueba que ofrecer.

Para saber más.

La conjetura de Gilbreath es un tema popular dentro de las matemáticas. Por ejemplo la encontramos reflejada en las páginas sobre los primos de Chris K. Caldwell, o en Wikipedia.

Los  trabajos experimentales tienen bastante información y son accesibles en internet.

R. B. Killgrove and K. E. Ralston, On a conjecture concerning the primes, Math. Comp. 13 (1959), 121-122.

A. M. Odlyzko, Iterated absolute values of differences of consecutive primes, Math. Comp. 61 (1993), 373–380.

 Y el trabajo de Zachary Chase puede obtenerse en arXiv:

Zachary Chase, A Random Analogue of Gilbreath’s Conjecture, arXiv:2005.00530, mayo  (2020).

Los tomos de la revista Nouvelles Correspondances Mathematiques pueden encontrarse en internet. El trabajo de Proth relevante a nuestra cuestión apareció en el tomo 4

La mejor fuente que he encontrado de la revista está en la Universidad de Gotinga y permite descargarse pdf de los tomos Nouvelle Correspondance Mathématique. También encontramos algunos tomos sueltos en otras fuentes:  Tomo 1, 1874-1875, Tomo 4 1878, Tome 5, 1879.