Las ternas pitagóricas son uno de los elementos más longevos en la historia de las matemáticas. Una terna pitagórica es un trío de números naturales \(a,b\) y \(c\) que corresponden con las longitudes de los lados de un triángulo rectángulo, y por lo tanto quedan caracterizadas por verificar \(a^2+b^2=c^2\); es el caso de los números \(3, 4\), y \(5\): \(3^2+4^2=5^2\). Aunque se llaman ternas pitagóricas son muy anteriores a Pitágoras: unas cuantas de ellas aparecen en la tablilla Plimpton 322, desenterrada en Larsa (cerca de Babilonia) y a la que se calculan unos 3.800 años de antigüedad; entre las ternas que contiene está, por ejemplo, \(4601, 4800\) y \(6649\), que es bastante espectacular. Euclides recogió en los Elementos buena parte de lo que los pitagóricos habían descubierto sobre ellas, y Diofanto también las estudió en su Aritmética. Precisamente trabajando en uno de los problemas de Diofanto sobre ternas pitagóricas, a Fermat se le ocurrió proponer su célebre teorema/conjetura: si \(n\) es mayor que \(2\), la ecuación \(a^n+b^n=c^n\) no tiene soluciones enteras distintas de las triviales. Algo antes de que Andrew Wiles pusiera en 1994 la guinda de la demostración del teorema de Fermat, las ternas pitagóricas ya estaban enredando en otro reto matemático: ¿Podemos colorear los números naturales \(\{ 1,2,3,\ldots \}\) con dos colores de forma que no haya tres números del mismo color y que formen una terna Pitagórica?
Este rompecabezas, al que podemos bautizar como problema de la coloración de ternas pitagóricas, bien podría haber sido propuesto por Paul Erdös. No lo fue, aunque Ronald Graham (en la foto con su mujer y Erdös en 1986), a semejanza de Erdös, ofreció en los años 80 un premio de 100 dólares para quien resolviera el problema de la coloración de las ternas pitagóricas. Decir que Graham fue colaborador de Paul Erdös no es decir mucho, habiendo tenido Erdös del orden de quinientos, y decir que fue su amigo es quizá demasiado, habiendo sido Erdös un matemático vagabundo que no conoció más hogar que las matemáticas. Tal y como se cuenta en El hombre que amaba los números de Paul Hoffman, Graham posiblemente fue lo más parecido a un amigo que tuvo Erdös, además de su albacea y, por así decir, administrador de bienes. Matemático y malabarista, Graham fue además el inventor del «número de Erdös»: Erdös tiene número de Erdös 0, y si el número de Erdös más bajo de los colaboradores de un autor es n, entonces el número de Erdös de ese autor es n+1.
En mayo de 2016, apareció en los Arxiv un artículo de Marijn J. H. Heule, Oliver Kullmann y Victor W. Marek demostrando que el problema de la coloración de ternas pitagóricas tiene solución para \(\{ 1,2,3,\ldots ,7824\}\) (ver imagen a la derecha), esto es, podemos colorear los números 
naturales \(\{ 1,2,3,\ldots ,7824\}\) con dos colores de forma que no haya tres números del mismo color y que formen una terna Pitagórica (Joshua Cooper y Ralph Overstreet habían demostrado en 2015 que el problema tenía solución para \(\{ 1,2,\ldots ,7664\}\)). Pero lo importante del artículo de Heule, Kullmann y Marek es que reportaban que el problema no tiene solución para \(\{ 1,2,3,\ldots ,7825\}\) (un dato: hay \(9465\) ternas pitagóricas formadas por números naturales menores o iguales que \(7824\), por \(9472\) formadas por números naturales menores o iguales que \(7825\)).
La demostración de Heule, Kullmann y Marek es asistida por ordenador y, en esencia, consiste en generar coloraciones en \(\{ 1,2,3,\ldots ,7825\}\) y comprobar que siempre hay una terna pitagórica del mismo color. Usando simetría y otros recursos, los investigadores lograron reducir los aproximadamente \(3\times 10^{2355}\) maneras de colorear \(\{ 1,2,3,\ldots ,7825\}\) a poco más de \(10{18}\). La comprobación se llevó a cabo en el centro Stampede de supercomputación de la Universidad de Texas (at Austin) usando 800 procesadores en paralelo durante dos días de computación. El fichero generado (la demostración, por así decir) ocupa la alucinante cifra de 200 terabytes de información y supone un record absoluto. Se da la circunstancia de que el anterior record, 13 gigabytes, lo generó la demostración por ordenador de un caso especial de la conjetura de la discrepancia de Erdös (ver el post anterior en este blog).
Heule, Kullmann y Marek son expertos en «propositional satisfiability problems» (SAT, en corto). Este tipo de problemas, del que la coloración de las ternas pitagóricas es un ejemplo, es de tipo NP completo; o sea, (a) no puede ser resuelto por un ordenador ideal (una máquina de Turing) en tiempo polinomial del número de datos que lo definen (problema NP), pero una vez conocida la solución esta tiene una comprobación polinomial y (b) todo problema NP se puede reducir en tiempo polinomial a uno de tipo SAT. A pesar de lo cual se ha desarrollado toda una artillería computacional para resolver problemas de tipo SAT. Ha sido este tipo de herramientas las que han usado Heule, Kullmann y Marek para dar respuesta negativa a la coloración de las ternas pitagóricas. Los autores creen además que este problema seguirá sin tener solución aun aumentando el número de colores, de hecho han propuesto la siguiente conjetura: para cada número \(k\) mayor que dos hay un número \(f(k)\) tal que el conjunto \(\{ 1,2,\ldots ,f(k)-1 \}\) puede ser coloreado con $k$ colores de manera que no haya tres números del mismo color y que formen una terna Pitagórica, mientras que esto es imposible para \(\{ 1,2,\ldots ,f(k)\}\). Por ahora sólo sabemos que \(f(2)=7825\).
Mucho se ha debatido desde que en 1977 Appel y Haken se ayudaran de un ordenador para completar su demostración del teorema de los cuatro colores; a pesar de que la de Heule, Kullmann y Marek debe todavía más al ordenador y de que no enseña cuál es la característica que hace que el problema de la coloración de las ternas pitagóricas falle para \(\{ 1,2,3,\ldots ,7825\}\), Ronald Graham ya ha pagado religiosamente los 100 dólares que ofreció a quien lo resolviera.
Referencias:
Marijn J. H. Heule, Oliver Kullmann, Victor W. Marek Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquers,
https://arxiv.org/abs/1605.00723
Lamb, Evelyn (26 May 2016). «Two-hundred-terabyte maths proof is largest ever». Nature. doi:10.1038/nature.2016.19990.
https://www.nature.com/news/two-hundred-terabyte-maths-proof-is-largest-ever-1.19990
https://en.wikipedia.org/wiki/Boolean_Pythagorean_triples_problem
Dejar una contestacion