¿Podemos colorear los números naturales con un número finito de colores de tal modo que, para todo \((a,b)\ne(2,2)\), el color de la suma \(a+b\) sea distinto del color del producto \(ab\)? (La excepción se debe a que dados dos números naturales \(a\), \(b\in\mathbf {N}\) hay solo un caso en que \(a+b=ab\), cuando \(a=b=2\).) Por ejemplo, $$\pi=3.14159\,26535\,89793\,23846\,26433\,83279\,\dots ,$$ podemos pensar que coloreamos los números con 10 colores \(0\), \(1\), \(2\),…, \(9\). coloreando el \begin{align*} &\text{1 del color 3},\\ &\text{2 del color 1},\\ &\text{3 del color 4},\\ &\text{4 del color 1},\\ &\text{5 del color 5},\\ &\text{6 del color 9},\\&\dots\end{align*} de acuerdo con las cifras de \(\pi\). En este caso el color de \(2+8=10\) y el de \(2\times8=16\) son iguales a \(3\). Pero esto es solo un caso, ¡hay infinitas formas de colorear y podemos usar millones de colores! Al menos necesitamos 3 colores, ya que tomando \((a,b)=(1,6)\), \((1,7)\) o \((2,4)\) tenemos que las parejas \((6,7)\), \((7,8)\) y \((6,8)\) tienen que tener distinto color. Luego el color de \(6\), \(7\) y \(8\) tienen que ser distintos.
Anticipo ya que la respuesta es negativa, pero no adelantemos acontecimientos.
El problema es antiguo aunque es difícil dar una cita sobre su origen exacto. En el año 1979 hay publicaciones estudiando el problema de si podemos colorear los números naturales de manera que ninguna cuaterna \(\{a, b, a+b, ab\}\) sea monocromática. Estas cuestiones entran dentro de la teoría de Ramsey. Hilbert en 1892 fue el primero en usar un teorema de tipo Ramsey, pero es mas espectacular la aplicación que hizo Schur en 1916 que está conectada al último teorema de Fermat. Un método de probar que una ecuación diofántica no tiene soluciones es tratar de encontrar un primo \(p\) de manera que la ecuación no tenga solución \(\bmod\ p\). Schur probó el siguiente teorema como un lema en un trabajo sobre la ecuación de Fermat \(x^n+y^n=z^n\).
Teorema de Schur. Si coloreamos los números naturales con un número finito de colores, existen tres números del mismo color \(x\), \(y\), \(z\) tales que \(x+y=z\).
Usando este resultado Schur fue capáz de probar que dado \(n\), si \(p\) es un primo suficientemente grande, entonces la ecuación \(x^n+y^n=z^n\) tiene solución no nula \(\bmod\ p\). Por tanto cierra el camino de probar que no hay solución de la ecuación de Fermat mediante este método.
Ronald Graham y Neil Hindman en 1979 pensaron una variante de nuestro problema; ellos piden que \(\{a,b,a+b, ab\}\) sea monocromática. Llegaron a probar que podían colorear los números del 1 al 251 con dos colores cumpliendo la condición de no tener cuaternas \(\{a,b,a+b, ab\}\) monocromáticas. En cambio los números de 1 al 252 necesitan al menos 3 colores. Esta afirmación la prueban con la ayuda de un ordenador. Nosotros podíamos preguntar: ¿Cuál sería el menor número \(N\) tal que no podamos colorear \(\{1,2,\dots, N\}\) con tres colores satisfaciendo la condición \(a+b\) y \(ab\) sean de distinto color? (cuando \(ab\ne a+b\) se entiende).
El algoritmo del avaro.
Una manera de atacar el problema es usar el algoritmo del avaro, ir coloreando los números sucesivamente. Supuestos coloreados \(1\), \(2\), …, \(n-1\) coloreamos \(n\) de manera que cumpla la condición (\(a+b\) y \(ab\) distintos colores) pero usando el mínimo número de colores. Si los colores los designamos por números y el color de \(n\) por \(f(n)\), definiremos así una función. Los primeros pasos del avaro serían los siguientes
- \(f(1)=1\), debemos usar un color y no tenemos ninguna restricción, usamos el primer color disponible \(1\).
- \(f(2)=2\), no podemos poner \(f(2)=1\) pues \(\{2,1\}=\{1+1,1\times1\}\) luego \(1\) y \(2\) tienen que tener distinto color. Uso el primer color disponible el \(2\).
- \(f(3)=1\). La única restricción que tenemos es que el color de \(3=1+2\) tiene que ser distinto del de \(2=1\times2\). Usamos \(1\) que es el primer color disponible para \(3\).
- \(f(4)= 2\) ya que el color de \(4=1+3\) debe ser distinto del de \(3=1\times3\). Así que \(f(4)\) no puede ser \(1\) pero no hay nada que prohiba \(f(4)=2\).
- \(f(5)= 1\) Tenemos que \(5=1+4=2+3=1\times5\). Así que \(f(5)\) no puede ser \(f(1\times4)\), \(f(2\times3)\) ni \(f(1+5)\). Luego solo tiene prohibido el \(2\) y podemos pintarlo del color \(1\).
- \(f(6)= 2\). Ya que al ser \(6=1+5=2+4=1\times6=2\times3\) debemos evitar los valores de \(f(5)\), \(f(8)\), \(f(7)\), \(f(5)\). Lo que prohibe solo el \(1\).
- …
Este proceso puede proseguir indefinidamente. En cada caso hay solo un número finito de colores a evitar y en caso necesario podemos usar un color nunca usado antes. ¿Pero necesitaremos un número infinito de colores? Esta cuestión es interesante pero no resuelve la cuestión original. El del avaro puede no ser el mejor método posible.
La función \(f(n)\) así definida tiene propiedades muy interesantes. La sucesión \(f(n)\) es la número A235726 en OEIS. Muchos años propuse a mis alumnos estudiar las propiedades de \(f(n)\), indicándoles el origen del problema. Todavía hoy queda abierto saber cómo crece \(g(n):=\max_{1\le j\le n}f(j)\). Lo que prueba el resultado que comentamos hoy es que \(\lim g(n)=\infty\).
Una solución inesperada.
A pesar de que el problema me interesó desde que tuve conocimiento de él hace como una década, no me he enterado de su solución hasta tres años después de la publicación en la revista Annals of Mathematics. Su autor es Joel Moreira, un matemático portugués ahora en la Universidad de Warwick, que ha demostrado que dada cualquier coloración finita de los números naturales siempre existirán infinitas parejas \(\{ a+b,a\times b \}\) monocromáticas (en realidad demuestra más: que hay infinitas ternas \(\{ a,a+b,a\times b \}\) monocromáticas). Moreira mantiene un blog, I Can’t Believe It’s Not Random!, sobre las matemáticas que le interesan.
La solución de este problema tiene una larga historia. La filosofía en los problemas de tipo Ramsey es que un conjunto suficientemente grande va a contener estructuras finitas predeterminadas. Por ejemplo una reunión de suficientes personas va a contener un grupo de 5 que se conocen todos entre sí, o bien un grupo de 7 en que ninguna pareja se conocen entre sí. Pero hay muchas variantes, por ejemplo nuestro problema se encuadra dentro del siguiente esquema:
Diremos que una familia finita de polinomios \(\{f_1,\dots, f_k\}\) en varias variables \(x=(x_1,\dots, x_s)\) es de Ramsey si para todo partición de \(\mathbf{N}\) en un número finito de colores \(\mathbf{N}=C_1\cup\cdots\cup C_r\), hay un color \(i\) y un \(x\in \mathbf{N}^s\) tal que \(\{f_1(x),\dots, f_k(x)\}\subset C_i\). Nuestro problema pregunta si la familia \(\{x+y, xy\}\) es de Ramsey.
Dinámica Topológica.
La primera sorpresa que uno encuentra en el artículo de Joel Moreira es que convierte el problema en un problema de dinámica topológica. En principio la dinámica topológica estudia un espacio topológico en el que actúa un grupo de transformaciones, y se desarrolló para estudiar las soluciones de ecuaciones diferenciales. Hay muchas dificultades técnicas para conseguir un espacio (compacto) y un grupo de transformaciones de manera que sus propiedades de recurrencia tengan que ver con los pares de números naturales \(\{a+b,ab\}\). El resultado final es aritmético pero los puntos del espacio \(X\) usado en la prueba son ultrafiltros en \(\textbf{N}\), lo que constituye una compactificación del conjunto de números naturales \(\textbf{N}\).
De hecho, en unos trabajos anteriores de Joel con su director de tesis Vitaly Bergelson, aplican esta técnica con éxito para probar que si coloreamos \(\mathbf{Q}\) con un número finito de colores, siempre existe \(x\in \mathbf{Q}\) e \(y\in \mathbf{N}\) con \(\{x+y,xy\}\) monocrómatico y \(x+y\ne xy\). Al trabajar con \(\mathbf{Q}\) se tiene mucho más juego en el problema. Bergelson y Moreira usaron teoría ergódica para resolver el problema analogo en \(\mathbf{Q}\). Ellos tenían buenos motivos por los que esta prueba no funcionaría en \(\mathbf{N}\), que el semigrupo de las transformaciones afines en \(\mathbf{N}\) no es amenable. Joel Moreira mas tarde advirtió que usando la dinámica topológica en lugar de la teoría ergódica podía trasladar la prueba.
El teorema que consigue probar se refiere a familias finitas de funciones \(\mathcal F\) del tipo \begin{gather*} x_0x_1\cdots x_N,\\ x_0x_1\cdots x_m+f(x_{m+1},\dots, x_n),\quad 0\le m<n\le N,\end{gather*} siendo las \(f\) funciones que cumplen que fijando sus variables menos la última queda un polinomio en \(x_n\) sin término constante.
Moreira prueba que si coloreamos \(\mathbf{N}\) con un número finito de colores, encontramos \(x_0\), \(x_1\), …, \(x_N\) tales que todas los valores de las funciones de \(\mathcal F\) tienen el mismo color en esos puntos.
Elementos para la prueba.
La prueba obtenida tiene la propiedad de que podemos eliminar el lenguaje de la dinámica topológica y entenderla hasta cierto punto.
Se basa en un concepto de conjunto de naturales grande. Hay muchas posibilidades de definir el concepto de grande para subconjuntos de \(\textbf{N}\). Pero necesitamos que el concepto tenga ciertas propiedades:
- Cualquier conjunto grande es no vacío.
- \(\textbf{N}\) es grande.
- Si \(A\supset B\) y \(B\) es grande, entonces \(A\) es grande.
- Si dividimos un conjunto grande \(A\) en un número finito de partes \(A=B_1\cup B_2\cup\cdots\cup B_N\), al menos uno de los \(B_r\) es grande.
- Si \(A\) es grande, entonces \(nA=\{na\colon a\in A\}\) es grande.
- Si \(A\) es grande, \(n+A=\{n+a\colon a\in A\}\) es grande.
- Si \(A\) es grande \(A-n=\{a-n\colon a\in A, a-n\ge1\}\) es grande.
Podemos usar la siguiente definición: Llamaremos grande a un subconjunto \(M\subset\textbf{N}\) que se pueda escribir como una intersección \(M=A\cap B\), donde \(A\) tiene lagunas acotadas. Esto es, existe un número \(a\) tal que cualquier conjunto de \(a\) números consecutivos corta a \(A\). En cambio \(B\) contiene intervalos de longitud arbitraria.
(Los conjuntos que he llamado grandes se denominan en el artículo piecewise syndetic sets.)
Los conjuntos grandes que hemos definido tienen una propiedad importante y difícil de probar, que va a ser clave en la prueba.
Teorema de tipo van der Waerden. Sea \(M\) grande y \(F\subset \textbf{N}\) un conjunto finito, existen entonces infinitos \(y\in\textbf{N}\) tales que los conjuntos $$ M\cap\bigcap_{m\in F}(M-my)$$ son grandes.
Admitido este teorema la prueba es realmente ingeniosa y no me resisto a detallarla. Es de esas construcciones, frecuentes en matemáticas, donde vemos el ingenio humano en su máxima expresión. Hay que tener mucha paciencia, ganas de ver resuelto el problema, y horas de intentos para llegar a una solución de este tipo. Quizás es aquí donde la dinámica topológica ha traído su magia. No dejéis de leerla, pero en un momento que tengáis un rato, es la matemática en estado puro.
La construcción inductiva.
Ya tenemos toda la maquinaria. Supongamos que nos dan una coloración del conjunto de los números naturales $$\textbf{N}=C_1\cup C_2\cup \cdots\cup C_r.$$ Nuestro problema es encontrar infinitos pares \(\{a+b,ab\}\) todos contenidos en el mismo color \(C_t\). Para ello vamos a construir inductivamente una sucesión de conjuntos grandes $$B_0, B_1, B_2, \dots$$ y una sucesión de números naturales $$y_1, y_2, y_3, \dots$$ tales que $$B_n\subset y_n B_{n-1}.$$ A la vez construiremos una sucesión de colores $$t_0,t_1,t_2,t_3,\dots$$ y unos conjuntos grandes auxiliares $$D_1,D_2, D_3,\dots$$ Empezamos notando que por la cuarta propiedad de los conjuntos grandes uno de los colores \(C_{t_0}\) tiene que ser grande. De ese modo tenemos elegidos los dos elementos con índice \(0\), el primer color \(t_0\) y \(B_0=C_{t_0}\).
Ahora aplicamos el teorema de tipo van der Waerden para conseguir un número \(y_1\) tal que $$D_1=B_0\cap(B_0-y_1) \text{ sea grande.}$$ Entonces, usando la propiedad 5 de los conjuntos grandes, \(y_1 D_1\) es grande, y entonces (por la propiedad 4) hay un color \(t_1\) de forma que $$B_1=y_1 D_1\cap C_{t_1}\text{ es grande}.$$ Así hemos construido \(D_1\), \(y_1\), \(t_1\), y \(B_1\), podemos suponer que hemos construido ya todos los \(B_j\), \(D_j\), \(y_j\) y \(t_j\) con \(1\le j\le n-1\) y vamos a construir los elementos con índice \(n\). Sea \(F_n\) el conjunto formado por \(1\) y los productos de la forma $$y_j^2y_{j+1}^2\cdots y_{n-1}^2,\quad 1\le j\le n-1.$$ Con este conjunto \(F_n\), por el teorema de tipo van der Waerden, encontramos \(y_n>y_{n-1}\) y tal que $$D_n=B_{n-1}\cap\bigcap_{u\in F_n}(B_{n-1}-u y_n)$$ sea grande.
Por las propiedades de los conjuntos grandes \(y_n D_n\) es grande y podemos escoger un color \(t_n\) tal que $$B_n=y_n D_n \cap C_{t_n}\text{ sea grande.}$$ Notar que por definición los elementos de \(B_n\) tienen el color \(t_n\). De este modo hemos construido \(D_n\), \(y_n\), \(t_n\) y \(B_n\) y estamos en condiciones de mostrar las infinitas parejas \(\{a+b,ab\}\) monocromáticas.
Notemos que, como dijimos, la construcción prueba que $$B_n \subset y_n D_n\subset y_n B_{n-1}.$$ En particular para \(m<n\) tendremos $$B_n\subset y_{m+1}y_{m+2}\cdots y_n B_m.$$ Solo hay un número finito de colores, luego para infinitas parejas de números naturales \(m<n\) se tiene \(t_m=t_n\), tomemos \(c\in B_n\) y pongamos \(b=y_{m+1}\cdots y_n\), de manera que \(B_n\subset b B_m\). Entonces \(c\) es múltiplo de \(b\) y podemos definir \(a=c/b\). Como \(c=ab\in B_n\) su color es \(t_n\).
\(a\) es también de color \(t_n\) ya que $$ab\in B_n\subset b B_m,$$ luego \(a\in B_m\) cuyo color es \(t_m=t_n\). Veremos ahora que también \(a+b\in B_m\). Con esto acabamos, pues el color de \(a+b\) será \(t_m=t_n\). Notemos $$b(a+b)=c+b^2\in B_n+b^2\subset y_n D_n+b^2.$$ Por su definición \(D_n\subset B_{n-1}-u y_n\) con \(u=y_{m+1}^2\cdots y_{n-1}^2\) (cuando \(m=n-1\) hay que entender \(y_{m+1}^2\cdots y_{n-1}^2=1\), recordar que \(F_n\) contiene el \(1\), también puede uno tomar \(m<n-1\), que es posible) tenemos $$y_nD_n +b^2\subset y_n(B_{n-1}-y_{m+1}^2\cdots y_{n-1}^2 y_n)+b^2.$$ Usamos ahora que \(B_n\subset y_{m+1}y_{m+2}\cdots y_n B_m\), $$b(a+b)\in y_n(y_{m+1}\cdots y_{n-1}B_{m}-y_{m+1}^2\cdots y_{n-1}^2 y_n)+b^2$$ $$= b B_{m}-b^2+b^2=b B_{m},$$ esto es \(a+b\in B_m\) como dijimos. Luego hemos probado que existen infinitos triples \(\{a,a+b,ab\}\) monocromáticos.
En palabras del propio Moreira, no creo que hubiera podido llegar a esta demostración combinatoria sin haber usado previamente la dinámica topológica para probarlo en primer lugar y sin el trabajo anterior con Bergelson.
Para saber más.
El trabajo publicado en Annals se puede descargar libremente de arXiv, contiene la prueba simple que hemos incluido:
Joel Moreira, Monochromatic sums and products in \(\mathbf{N}\), Annals of Math. 185 (2017), 1069-1090.
Un poco antes Ben Green y Tom Sanders han probado el teorema en \(F_p\), el cuerpo primo de \(p\) elementos. Como aquí el conjunto es finito prueban que una fracción de las ternas \(c_rp^2\) son monocromáticas, siendo la constante \(c_r>0\) dependiente solo del número de colores.
Su prueba es también libre en la red:
Ben Green y Tom Sanders, Monochromatic sums and products, Discrete Analysis 2016:5 (48 páginas).
La revista Discrete Analysis es un experimento en revistas electrónicas. No hay publicación sino una página con una descripción del trabajo y su mérito. El artículo descansa en arXiv (con un estilo propio que le da un aire de publicado). Por otro lado la revista tiene su proceso de revisión y es de gran calidad. Además no hay gastos (o son mínimos) para los editores. Es un modelo de lo que debe ser una publicación matemática. Como vemos publican en ella los mejores matemáticos: Green es el que junto con Tao probó que los primos contienen progresiones aritméticas arbitrariamente largas.
A propósito de las matemáticas y la combinatoria de los colores (y a pesar de mi daltonismo), no puedo dejar de recomendar aquí el libro:
Alexander Soifer, The mathematical Coloring Book. Mathematics of Coloring and the Colourful Life of Its Creators, Springer, 2009.
Es un tipo nuevo de libro de matemáticas. Expone las matemáticas sin olvidar a l@s matematic@s que la han creado. Se lee como una novela.
Dejar una contestacion