Resuelta una conjetura de Erdös sobre congruencias

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:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. Dice que la demostración es fetén porque peude dar un valor máximo, pero que no la da. Pues vaya.

    Publica una respuesta
  2. 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”.

    Publica una respuesta
  3. “No existen recubrimientos incongruentes que cumplan que todos sus módulos son números impares”
    Era impares? He encontrado uno con los pares, creo

    Publica una respuesta
  4. Vale y… ¿cuál es la cota? ¿40? Y si no es 40… ¿se ha encontrado el recubrimiento?

    Publica una respuesta
  5. 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?

    Publica una respuesta
  6. Sí, es suficiente, pero el autor es algo perezoso y no la ofrece.

    Publica una respuesta
  7. 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):

    \left \{ 0(2), 0(3), 1(4), 5(6), 7(12) \right \}

    Se obtendría:

    \left \{ 1(2), 0(4), 0(6), 2(8), 10(12), 14(24) \right \}

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - 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…
  2. Resuelta una conjetura de Erdös sobre cong... - [...]   [...]
  3. Lo Mejor de la Semana (14-20 de julio) | Hablando de Ciencia | Artículos - [...] 2013, está siendo un buen año para las matemáticas y la teoría de números. [...]
  4. Resuelta una conjetura de Erdös sobre cong... - […]   […]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *