Todo el que haya visitado este blog con cierta frecuencia durante los últimos años conocerá a Javier Cilleruelo, ya que su nombre ha aparecido por aquí en varias ocasiones. Para quien no lo conozca, Javier Cilleruelo es Profesor Titular del Departamento de Matemáticas de la Universidad Autónoma de Madrid y miembro del Instituto de Ciencias Matemáticas (ICMAT), y ha colaborado en Gaussianos con varios artículos.
La cosa comenzó con el problema de los conjuntos generalizados de Sidon (de cuya demostración hablé aquí), que resolvió junto a Imre Ruzsa y Carlos Vinuesa, y del cual nos habló Javier en este artículo. Más adelante, Javier siguió colaborando con Gaussianos con este artículo sobre el teorema de Szemerédi y con este artículo sobre la conjetura débil de Goldbach.
En esta ocasión, Javier nos habla sobre el último resultado que ha conseguido demostrar, junto a Florian Luca en este caso. El título de esta entrada lo dice todo: Javier y Florian han demostrado que todo entero positivo es suma de tres capicúas. Y además no solamente han dado una demostración, sino que dicha demostración es constructiva. Es decir, dado un numero entero positivo nos proporcionan un algoritmo para encontrar esos tres números capicúas. En lo que sigue os dejo el texto que me ha enviado Javier explicando dicho resultado y dando unas ideas de la demostración. Al final del mismo podéis encontrar un enlace al artículo técnico completo.
Un problema clásico en la teoría de los números consiste en estimar el número de sumandos necesarios para representar cualquier entero positivo como suma enteros de una sucesión notable de números, como los cuadrados, los primos, etc. Algunos ejemplos son los siguientes:
- Teorema (Lagrange 1770): Todo entero positivo es suma de cuatro cuadrados.
- Teorema (Gauss 1796): Todo entero positivo es suma de tres números triangulares.
- Teorema (Wieferich, 1912): Todo entero positivo es suma de nueve cubos.
- Teorema (R. Balasubramanian, F. Dress, y J.-M. Deshouillers 1986): Todo entero positivo es suma de diecinueve cuartas potencias.
- Teorema (Helfgott 2013): Todo impar mayor que 5 es suma de tres primos.
- Conjetura de Goldbach: Todo par mayor que 2 es suma de dos primos.
Todos estos resultados son óptimos en el sentido de que no son ciertos con menos sumandos. Hace unos días, en un trabajo con Florian Luca, hemos añadido un resultado a esta lista de resultados óptimos:
Teorema (J. Cilleruelo, F. Luca 2016): Todo entero positivo es suma de tres capicúas en cualquier base
.
Los números capicúas, también llamados palíndromos, son aquellos que se leen igual de izquierda a derecha y de derecha a izquierda. El carácter capicúa de un número depende, claro está, de la base en la que escribamos dicho número. Así, por ejemplo, el número es un número capicúa en base
, pero no lo es en base
ya que en esta base se escribe de la forma
. El cero se considera un número capicúa (si no deberíamos cambiar el enunciado del teorema diciendo que todo entero positivo es suma de, a lo más, tres números capicúas).
El teorema es óptimo ya que no es difícil construir infinitos enteros que no son suma de dos capicúas.
La conjetura de que tres números capicúas (en base ) eran suficientes para representar todos los enteros positivos era una conjetura que llevaba tiempo rondando en el área, pero sólo se había logrado demostrar que todo entero positivo era suma de 49 números capicúas (W. Banks, 2015).
Nuestra demostración es algorítmica; es decir, dado cualquier entero positivo, proporcionamos un algoritmo para hallar tres capicúas cuya suma sea dicho número. Por ejemplo, para el entero positivo que viene dado por los primeros 21 dígitos del número ,
los tres capicúas que nos da el algoritmo son los siguientes:
Eso no quiere decir que ésta sea la única representación de nuestro número como suma de tres capicúas. Por regla general, cada entero positivo tendrá muchas representaciones, pero para la demostración del teorema es suficiente con proporcionar una representación para cada uno de ellos. A continuación se exponen las ideas centrales del algoritmo.
El algoritmo
El algoritmo que utilizamos es complejo pero elemental, en el sentido que no se utilizan matemáticas profundas. Vamos a ilustrar nuestrol algoritmo viendo paso a paso cómo hemos llegado a los tres capicúas del ejemplo.
La configuración de partida es importante y depende del último y de los tres primeros dígitos del número que queremos representar. En nuestro algoritmo contemplamos hasta 13 configuraciones de partida. Para el entero de nuestro ejemplo la configuración de partida es la siguiente (en el artículo técnico están los detalles que justifican la elección de estos números para comenzar con el algoritmo):
Vamos a ir completando los dígitos de los tres capicúas desde la derecha y desde la izquierda simultáneamente. Con los dígitos de ajustamos los dígitos de la izquierda, y con los dígitos de
ajustamos los dígitos de la derecha. Los dígitos de
, que salvo el inicial son 0 o 1, sirven para controlar las «llevadas» en las columnas de la izquierda (pondremos un 0 si hay llevadas y un 1 si no las hay). La estrategia es suponer que siempre vamos a tener una llevada cuando completamos los dígitos por la izquierda. Siendo así, el siguiente dígito de
tiene que ser un 1 y el siguiente dígito de
un 8:
Seguidamente completamos con un 4 para ajustar el dígito de la segunda columna por la derecha:
Como necesariamente vamos a tener una llevada en la cuarta columna por la izquierda (porque 4 es mayor o igual que 1), el siguiente dígito de va a ser un 0. Si no fuera a haber llevada pondríamos un 1 para suplir a la llevada que no tenemos. Como ya hemos comentado, los dígitos del primer capicúa sirven para controlar las llevadas: si la hay ponemos un 0 y si no la hay ponemos un 1.
El siguiente dígito de es 6 (para ajustar esa columna de la izquierda suponiendo que habrá llevada):
De nuevo completamos con un 1 para ajustar el dígito de la tercera columna por la derecha:
Seguimos con el algoritmo hasta que colisionan la parte izquierda con la parte derecha:
Siguiendo el algoritmo hemos logrado ajustar todos los dígitos excepto el de la columna central (obtenemos un 4 cuando deberíamos obtener un 5). Eso se debe a que no tenemos llevada de la columna anterior. Cuando eso sucede hay que hacer un ajuste, que en este caso es sencillo: simplemente cambiamos el dígito central de por un 1:
Con este último paso finaliza el algoritmo.
Invito a los lectores a que prueben a escribir su número favorito como suma de tres capicúas utilizando este algoritmo. Lo más seguro es que les ocurra como en este caso, que al final tengan que hacer algún ajuste en los dígitos centrales para que todo cuadre. Y en algunos casos estos ajustes no son nada sencillos. De hecho, el ejemplo que hemos elegido era de los más simples. Si el número de cifras es par el ajuste final se complica. Y si además el primer dígito de nuestro número es 1 y el siguiente 0,1 o 2, el ajuste se complica todavía más. Además, el algoritmo descrito funciona cuando nuestro número tiene 7 dígitos o más. Si tiene menos de 7 dígitos hay que aplicar otro algoritmo distinto que también está explicado en el artículo.
Las ideas centrales del algoritmo son las que se han descrito con el ejemplo, pero la casuística es tan compleja que hace que el artículo se alargue hasta las 39 páginas. EL lector interesado puede consultarlo en el siguiente enlace: Every positive integer is a sum of three palindromes.
Tanto las configuraciones de partida como los ajustes finales hacen que el algoritmo no funcione bien para las bases .
Terminamos esta entrada planteando algunos problemas:
- ¿Hay una proporción positiva de enteros que son suma de dos capicúas?
- ¿Cuantos capicúas en base 2 se necesitan para representar todos los enteros positivos?
Este último problema, que nosotros ya no hemos querido intentar, seguro que es accesible y puede ser interesante para algún estudiante aventajado que quiera dar sus primeros pasos en el mundo de la investigación. Se trataría de utilizar un algoritmo parecido (quizás sea incluso más sencillo) pero adaptado a la base 2.
También sería interesante para los expertos en programación implementar el algoritmo descrito en nuestro artículo. Desde Gaussianos animamos a quienes estéis interesados en ello a que lo hagáis y lo compartáis con nosotros.
Este artículo participa en la Edición 7.1 del Carnaval de Matemáticas, que en esta ocasión organiza Tito Eliatron.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
[…] en prensa: Al poco de publicar la entrada me entero por Gaussianos que Javier Cilleruelo, de la Universidad Autónoma de Madrid, ha reducido la cota de Banks de […]
me interesó el asunto y lo intentaré programar como ya hice en el caso de la suma de cuadrados para los enteros positivos! Claro el tema es que una vez que se encuentra el algoritmo hay que optimizarlo para que su respuesta sea rápida (salvo tener una super computadora), en el caso de la suma de cuadrados si el numero es muy muy grande puede ser lento, en eso estoy, o sino ocurre que el resultado no es el óptimo; es decir da más sumandos de los que bastarían!
Perfecto Carlos. Ve informándonos de tus progresos, a ver si entre todos conseguimos programarlo :).
Información Bitacoras.com
Valora en Bitacoras.com: Todo el que haya visitado este blog con cierta frecuencia durante los últimos años conocerá a Javier Cilleruelo, ya que su nombre ha aparecido por aquí en varias ocasiones. Para quien no lo conozca, Javier Cilleruelo es P…
¿Proporción positiva de enteros que son suma de dos capicúas? ¿Proporción positiva? No sé a qué se refiere… ¿A que haya al menos uno que pueda expresarse así?
¡Ah! Y por supuesto, enhorabuena a Javier Cilleruelo. Que siga cosechando resultados y éxitos.
Proporción quiere decir «densidad». La proporción de los pares (y de los impares) es 1/2, la proporción de los múltiplos de 10 es 1/10. La proporción de las potencias de 2 es cero, en el sentido de que el límite de la proporción entre las potencias de 2 menores que n y n es cero cuando n tiende a infinito.
Ante todo, enhorabuena a Javier y Florián. Para programar esto sería necesario primero saber exactamente como elegir los primeros dígitos y cómo hacer el ajuste central en todos los casos posibles. En base 2, todos los números capicúas son impares salvo el 0. Entonces, si el número que pretendemos conseguir es par, es obligatorio un número par de capicúas (a menos que uno de ellos sea 0). De la misma forma, si el número que pretendemos conseguir es impar, hará falta un número impar de capicúas diferentes de cero. Así que ahí ya tenemos una diferencia importante que invita a… Lee más »
¡Enhorabuena!
Bueno, desde que vi publicado este artículo en Facebook me interesó mucho y aún más la tarea pendiente de programar. Lamentablemente sólo tengo hecho un curso de Programación en Python de unos meses en la Facultad de Ingeniería de mi país (Uruguay), así que lo que he obtenido hasta el momento no implementa en absoluto el algoritmo constructivo de la demostración del teorema en cuestión pero sin dudas, creo que funciona aunque se podría optimizar mucho más por algún experto en la materia (pude pobrarlo sin problemas con enteros hasta el 1000 aunque demorando un poco en mi MacBook Air… Lee más »
Acabo de observar que los códigos de las definiciones de las funciones salieron sin la indentación respectiva las cuales serían por definicion y por línea:
def 1: 1 ind en la 1ª línea, 1 ind en el while, 2 inds en la 3ª línea, 2 inds en la 4ª línea y 1 ind en el return
def 2: 1 ind en el return
def 3: 1 ind en el return
def 4: 1 ind en el return
Obviamente, que sin estas correcciones, el programa no correrá.
No tengo muy claro que la densidad de la suma de dos palíndromos sea positiva:
hay 8 sumas menores que 10 (1 no es suma de dos palíndromos)
hay 90 sumas menores que 100 (10 o 21 no son sumas)
hay 981 menores que 1000
hay 7995 menores que 10000
hay 90856 menores que 100000
hay 732836 menores que 10^6
hay 8859893 menores que 10^7
hay 68725987 menores que 10^8
hay 875757971 menores que 10^9
Recuerdos a Cilleruelo, fui alumno suyo.
Sorry for replying in English, but I hope that’s o.k. The following is only for Base-10. If we assume the definition of http://oeis.org/A035137 (0 is considered as a palindrome), then the decade-wise percentages of numbers that cannot be expressed by less than 3 palindromes is growing. From To 3 Palindromes needed 1 10 0 10 100 8 100 1000 1 1000 10000 1979 10000 100000 7042 100000 1000000 257918 1000000 10000000 871675 10000000 100000000 30132082 100000000 1000000000 92939102 So the density of numbers expressible as a sum of two base-10 palindromes is decreasing for larger numbers. Can we estimate what… Lee más »
[…] Había resuelto problemas importantes, como el de los conjuntos de Sidón en colaboración con Carlos Vinuesa e Imre Ruzsa, que fue recogido en una entrada de este blog: Resuelto el problema de los conjuntos generalizados de Sidon. Recientemente había resuelto otro problema en Teoría de Números, en colaboración con Florian Luca, y recogido en una entrada del blog Gaussianos, Todo entero positivo es suma de tres capicúas. […]