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$.

Paul ErdösAntes de comentar de qué trata este problema creo que es interesante recordar qué es esto de las congruencias. Dos números enteros a,b son congruentes módulo m (entero mayor que 1) si m es un divisor de a-b, o, equivalentemente, si tanto a como b dejan el mismo resto al dividir entre m. Se suele escribir a \equiv b \pmod{m}. 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 a \pmod{m} como el conjunto de números enteros que son congruentes con a módulo m. Analizando un poco lo que significa que dos enteros sean congruentes módulo otro entero es fácil ver que esta congruencia a \pmod{m} es el conjunto de números enteros que aparecen al sumar al entero a el valor m una cantidad entera de veces. Es decir:

a \pmod{m}=\{ a+mk \; / \; k \in \mathbb{Z} \}

Por ejemplo, 3 \pmod{4} 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:

3 \pmod{4}=\{ 3+4k \; / \; k \in \mathbb{Z} \}

Vamos a meternos en el problema en cuestión. Erdös llamó recubrimiento (o sistema completo de residuos)) de \mathbb{Z} a un conjunto finito de congruencias

\{ a_1 \pmod{m_1}, a_2 \pmod{m_2}, \ldots , a_k \pmod{m_k} \}

tales que todo número entero cumple al menos una de ellas. Es decir, un recubrimiento (covering system en inglés) de \mathbb{Z} es un conjunto finito de congruencias tales que la unión de todas ellas es el propio \mathbb{Z}.

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:

\{ 0 \pmod{2}, 1 \pmod{2} \}

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:

0 \pmod{2},0 \pmod{3},1 \pmod{4},5 \pmod{6},7 \pmod{12} \}

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 12k+1. Pero entonces se cumple que el número es 4 \cdot (3k)+1, 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 12k+11. Entonces también se puede expresar como 6 \cdot (2k)+11. Como 11=6+5, tenemos que el número puede escribirse como 6 \cdot (2k)+6+5=6 \cdot (2k+1)+5, 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:

\{ 0(3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), 26(120) \}

¿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í:

Bob Hough

Dado N un número entero mayor que 1 cualquiera, siempre existe un recubrimiento por congruencias de \mathbb{Z} 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 N.

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:

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉