Muy buen año para la teoría de números este 2013. Después de la demostración de la conjetura débil de Goldbach y la cota del hueco entre primos gemelos ha caído la que podríamos llamar conjetura del recubrimiento por congruencias, planteada por Paul Erdös en 1950. Pero en este caso no se ha comprobado que es cierta, sino que es falsa. Y el artífice de esta refutación es Bob Hough. Vamos a explicar un poco de qué va este problema, que, por cierto, era una de las conjeturas no resueltas de Erdös que más le gustaban, y por cuya resolución ofreció 1000$.
Antes de comentar de qué trata este problema creo que es interesante recordar qué es esto de las congruencias. Dos números enteros
son congruentes módulo
(entero mayor que 1) si
es un divisor de
, o, equivalentemente, si tanto
como
dejan el mismo resto al dividir entre
. Se suele escribir
. Por ejemplo, 23 y 35 son congruentes módulo 4, ya que 4 es un divisor de 35-23=12.
Con esto podemos definir ahora la congruencia como el conjunto de números enteros que son congruentes con
módulo
. Analizando un poco lo que significa que dos enteros sean congruentes módulo otro entero es fácil ver que esta congruencia
es el conjunto de números enteros que aparecen al sumar al entero
el valor
una cantidad entera de veces. Es decir:
Por ejemplo, son todos los números enteros congruentes con 3 módulo 4, que son el propio 3, el 7 (3+4), el 11 (3+4·2), el 15 (3+4·3), el -1 (3+4·(-1), el -5 (3+4·(-2)), etc. Es decir:
Vamos a meternos en el problema en cuestión. Erdös llamó recubrimiento (o sistema completo de residuos)) de a un conjunto finito de congruencias
tales que todo número entero cumple al menos una de ellas. Es decir, un recubrimiento (covering system en inglés) de es un conjunto finito de congruencias tales que la unión de todas ellas es el propio
.
Veamos un ejemplo. Partiendo de que los módulos deben ser mayores que 1 para que las congruencias no sean triviales, el ejemplo más sencillo de recubrimiento es el siguiente:
La primera congruencia con todos los números enteros que dejan resto 0 al dividirlos entre 2, y la segunda todos los enteros que dejan resto 1 al dividirlos entre 2. Como ésas son las dos únicas posibilidades, la unión de las dos congruencias es el conjunto de los números enteros.
Pero para este problema a Erdös no le interesaban todos los recubrimientos posibles, sino solamente los que cumplen que todos los módulos son distintos, denominados recubrimientos incongruentes.
Primera cuestión interesante: ¿existen recubrimientos incongruentes? Pues sí, sí existen. El ejemplo más simple es el siguiente:
No es difícil comprobar que todo número entero cumple alguna de esas congruencias. Veámoslo:
Todo número entero deja resto 0, 1, 2, … , 10 u 11 al dividirlo entre 12. Analicemos todos los casos:
- Si el resto es un número par, entonces el propio número es par, por lo que cumple la primera congruencia.
- Si el resto es un múltiplo de 3, entonces el número es múltiplo de 3, por lo que cumple la segunda congruencia.
- Si el resto es 1, el número es de la forma
. Pero entonces se cumple que el número es
, por lo que deja resto 1 al dividirlo entre 4, cumpliendo así la tercera congruencia. Algo parecido ocurre cuando el resto es 5.
- Si el resto es 7 se cumple la última congruencia.
- Y si el resto es 11, el número es de la forma
. Entonces también se puede expresar como
. Como 11=6+5, tenemos que el número puede escribirse como
, por lo que deja resto 5 al dividirlo entre 6, cumpliendo así la cuarta congruencia.
Fijémonos ahora en el módulo más pequeño de todos los que aparecen en estas cinco congruencias. Ese módulo más pequeño es 2. ¿Se podrá encontrar un recubrimiento incongruente en el que el módulo más pequeño sea 3? Pues sí, se puede. Aquí tenéis uno (entre paréntesis aparece el módulo de cada congruencia) que encontró el propio Erdös:
¿Y uno en el que el módulo más pequeño sea 4? Pues también. Y con números más grandes. El récord está en un recubrimiento incongruente con módulo más pequeño igual a 40, y fue establecido por Pace P. Nielsen en 2009. El paper en cuestión es A covering system whose smallest modulus is 40.
La pregunta es obligada: ¿se podrá seguir subiendo o habrá algún tipo de cota para el módulo mínimo?. Erdös conjeturó que se podía seguir subiendo de forma indefinida, que no habría cota. Por tanto, la conjetura del recubrimiento por congruencias podría enunciarse tal que así:
Dado
un número entero mayor que 1 cualquiera, siempre existe un recubrimiento por congruencias de
en el que todos los módulos son distintos (es decir, es lo que antes hemos llamado incongruente) y tal que el menor módulo que aparece en dicho recubrimiento es mayor o igual que
.
Y esto es lo que al parecer ha refutado Bob Hough en su trabajo The least modulus of a covering system. En este documento puede verse la demostración de este hecho, cuya clave parece ser una inteligente aplicación iterada de una versión de un resultado conocido como lema local de Lovász.
Todos los genios se equivocan alguna vez, y en esta ocasión, sorprendentemente (por lo inusual), la intuición de Erdös no acertó.
Y para terminar os dejo otra conjetura de Erdös relacionada con los recubrimientos incongruentes. Ahí va:
No existen recubrimientos incongruentes que cumplan que todos sus módulos son números impares.
Ya tenéis trabajo para este verano.
Fuentes y enlaces relacionados:
- Post de Terence Tao en Google+ comentando el tema (aquí fue donde lo vi por primera vez).
- Problems and results in discrete mathematics, interesante documento escrito por Erdös en el que se habla de éste y otros problemas.
- On some of my problems in number theory I would most like to see solved, otro interesante documento escrito por Erdös en el que trata éste y otros problemas.
- Covering system en la Wikipedia en inglés.
- Covering systems: number theory in the spirit of Paul Erdös.
- La foto de Erdös la he tomado de aquí.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Muy buen año para la teoría de números este 2013. Después de la demostración de la conjetura débil de Goldbach y la cota del hueco entre primos gemelos ha caído la que podríamos llamar conjetura del recubrimiento por ……
Muy interesante.
Dice que la demostración es fetén porque peude dar un valor máximo, pero que no la da. Pues vaya.
Creo que el título de este post no es incorrecto pero eso no me impide creer que habría estado mejor “Resuelta por la negativa una conjetura de Erdös sobre congruencias”.
«No existen recubrimientos incongruentes que cumplan que todos sus módulos son números impares»
Era impares? He encontrado uno con los pares, creo
Vale y… ¿cuál es la cota? ¿40? Y si no es 40… ¿se ha encontrado el recubrimiento?
Luis GSA, la conjetura se ha resuelto, y ha resultado ser falsa. Se podía haber puesto un «negativamente» en el título, pero no lo vi necesario ya que se explica en la entrada. Gracias por tu sugerencia :).
Francesc, sí, la conjetura habla de que todos los módulos sean impares.
Sobre el tema de la cota, parece que se demuestra que la cota existe, aunque no se da. Eso es suficiente para decir que la conjetura es falsa, ¿verdad?
Sí, es suficiente, pero el autor es algo perezoso y no la ofrece.
Maestrillo, sí, en eso tienes razón :(.
[…] […]
Francesc para conseguir un recubrimiento sólo con módulos pares, a mí se me ocurre una forma de conseguirlo a partir de un recubrimiento ya existente.
Si no me equivoco mucho, basta con multiplicar por 2 todos los módulos y todos los restos, este nuevo conjunto de congruencias recubriría los pares, así que bastaría añadir 1 mod (2).
Por ejemplo, del recubrimiento más simple (tomado de este mismo artículo):
Se obtendría:
[…] 2013, está siendo un buen año para las matemáticas y la teoría de números. […]
[…] […]