Teorema de la semana: el de Szemerédi

Una progresión aritmética es una sucesión de números de la forma

$a, a + r, a + 2r, a + 3r, \ldots.$

Es decir, la diferencia entre cada dos números consecutivos es la misma. Por ejemplo, las sucesiones

$1, 2, 3, 4, \ldots;$

$2, 6, 10, 14;$ y

$2.5, 2.8, 3.1, 3.4, 3.7, 4;$

son progresiones aritméticas. Las progresiones aritméticas pueden ser finitas o infinitas. De los tres ejemplos anteriores, la primera (la sucesión de los enteros) es infinita, mientras que las dos últimas son finitas. Al número de términos de una progresión aritmética se la llama su longitud; así, en los ejemplos finitos anteriores, las longitudes son 4 y 6, respectivamente. Son las progresiones aritméticas finitas las protagonistas del teorema de esta semana.

En 1927, Bartel Leendert van der Waerden demostró que si partimos el conjunto de los enteros positivos en dos clases, $\mathbb \{1, 2, 3, \ldots\} = A\cup B,$ entonces $A$ o $B$ contiene progresiones aritméticas de cualquier longitud. En otras palabras: si pintamos los enteros positivos en dos colores, digamos, rojo y azul, entonces podemos encontrar progresiones aritméticas, de cualquier longitud, formadas por solo números rojos, o por solo azules. Más aún, Van der Waerden mostró que, para cualquier $k,$ existe un número $N = N(k)$ (o sea, $N$ depende de $k$ ) tal que, si coloreamos en dos colores el conjunto

$\{ 1, 2, 3, \ldots, N\}$ ,

entonces tenemos una progresión aritmética de longitud $k$ de números del mismo color. De hecho, Van der Waerden demostró más: para cualquiera $r$ y $k,$ existe un número $N = N(r, k)$ tal que, si coloreamos en $r$ colores el conjunto $\{ 1, 2, 3, \ldots, N\},$ entonces tenemos una progresión aritmética de longitud $k$ con números de un mismo color. La demostración no es difícil y, de hecho, Ronald Graham y Bruce Rothschild publicaron en los 70 una demostración del teorema de Van der Waerden de una sola página.

Más adelante, en los 30, Paul Erdös y Pál Turán consideraron el siguiente problema: ¿cuál es el mínimo número $l$ tal que, si tomamos cualquiera $l$ enteros entre $1$ y $N,$

$1 \le a_1 < a_2 < a_3 < \ldots < a_l \le N,$

entonces el conjunto $\{a_1, a_2, a_3, \ldots, a_l \}$ tiene una progresión aritmética de longitud $k$ ? Erdös y Turán demostraron que, si denotamos a ese número como $r(k,N)$ , el límite

$\displaystyle \lim_{N\to\infty} \frac{r(k,N)}{N} = c$

existe, y conjeturaron que, de hecho, es igual a cero. En otras palabras, para cualquier número positivo $\delta$ (por pequeño que sea), existe un $N = N(\delta,k)$ tal que cualquiera $\delta N$ números entre $1$ y $N$ contienen una progresión aritmética de longitud $k$ .

El problema resultó ser extremadamente difícil. No fue sino hasta 1954 cuando Klaus Roth demostró el caso $k=3$ (Roth recibió la medalla Fields en 1958), y tuvieron que pasar 15 años para que Endre Szemerédi demostrara el caso $k=4$ .

El mismo Szemerédi, seis años después, en 1975, publicó la solución a la conjetura de Erdös y Turán para $k$ general; su resultado es ahora conocido como el teorema de Szemerédi.

Teorema (Szemerédi). Sea $k$ un entero positivo y $\delta >0$ . Entonces existe $N$ tal que cualquier subconjunto de $\{1, 2, \ldots, N\}$ con $\delta N$ elementos tiene una progresión aritmética de longitud $k$ .

La demostración de Szemerédi está basada en la teoría de grafos y es sumamente complicada, no en el sentido de ser avanzada (de hecho, es «elemental»), sino que el razonamiento lógico de los enunciados está demasiado enredado. Terry Tao publicó ayer en su blog los «ingredientes» de la demostración, y hace notar que el mismo Szemerédi incluyó un diagrama con las implicaciones lógicas de las proposiciones, lemas y teoremas en que está dividida su demostración (el diagrama lo pueden ver en el post de Francis).

Unos años después, Hillel Furstenberg dio una demostración distinta del teorema de Szemerédi, basada en teoría ergódica. Aunque más simple que la demostración de Szemerédi, no es elemental, en el sentido que requiere de teorías más avanzadas en análisis. En el 2001, Tim Gowers (medalla Fields 1998) publicó una tercera demostración del teorema de Szemerédi. Esta vez, Gowers logró desarrollar una demostración basada solo en teoría de números aditiva, con técnicas clásicas de análisis de Fourier. El costo, sin embargo, fueron las más de 100 páginas que ocupa la demostración. Son pocos los teoremas en matemáticas cuyas demostraciones han motivado el desarrollo de tantas áreas distintas en matemáticas.

Esta semana, Endre Szemerédi ha sido condecorado con el premio Abel.

El teorema de esta semana participa en Carnaval de Matemáticas, edición 3.14, cuyo anfitrión es el blog Hablando de Ciencia.

Teoremas de la semana anteriores: teorema de la semana.

Teorema de la semana: el de Szemerédi

4 comentarios sobre “Teorema de la semana: el de Szemerédi”

Deja un comentario Cancelar la respuesta

Sharéalo:

Relacionado

4 comentarios sobre “Teorema de la semana: el de Szemerédi”

Deja un comentario Cancelar la respuesta