Transcript
Trabajo Fin de M´ aster:
El Teorema de Roth Universidad Aut´ onoma de Madrid Departamento de Matem´ aticas
Alumno: Seraf´ın Ruiz Cabello
Dirigido por: Javier Cilleruelo Mateo 17 de septiembre de 2010
´Indice general ´ Indice general
1
Resumen
3
1. Introducci´ on 1.1. Notaci´ on . . . . . . . . . . . . . . . . 1.2. Rese˜ na hist´ orica . . . . . . . . . . . 1.2.1. Teorema de Van de Waerden 1.2.2. Conjetura de Erd¨os-Tur´an . . 1.2.3. Teorema de Roth . . . . . . . 1.2.4. Teorema de Sz´emeredi . . . . 1.3. S´ıntesis de los datos . . . . . . . . .
. . . . . . .
5 5 6 6 7 8 10 11
2. Demostraci´ on anal´ıtica de Roth 2.1. An´ alisis de Fourier en Z/nZ . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Demostraci´ on anal´ıtica de Roth . . . . . . . . . . . . . . . . . . . . . .
13 13 17
3. Demostraci´ on combinatoria de Sz´ emeredi 3.1. Resultados previos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Demostraci´ on combinatoria de Sz´emeredi . . . . . . . . . . . . . . . .
27 28 34
4. Ejemplo de Behrend 4.1. Ejemplo de Behrend . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39 39
Bibliograf´ıa
43
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
´INDICE GENERAL
Resumen El teorema de Roth es un resultado cl´asico de la teor´ıa combinatoria de n´ umeros. Demostrado por primera vez por el matem´atico brit´anico Klaus F. Roth en 1953, existen gran cantidad de diferentes demostraciones de este resultado en la literatura, utilizando diversas t´ecnicas matem´aticas. El teorema afirma que, para cualquier δ > 0, todo subconjunto de {1, 2, . . . , N } que tenga m´as de δN elementos contiene una progresi´ on aritm´etica de tres elementos, si N es suficientemente grande. Cuantificar el tama˜ no de N (en funci´ on de δ) es uno de los grandes retos en la teor´ıa combinatoria de n´ umeros. A lo largo del primer cap´ıtulo de esta exposici´on, presentaremos una breve rese˜ na hist´ orica en la que hablaremos de los or´ıgenes de este teorema (el teorema de Van der Waeden o la conjetura de Erd¨os-Tur´an, para la que el teorema de Roth prueba un caso particular); de las distintas mejoras del resultado que han ido produci´endose (hace tan s´ olo dos meses, Tom Sanders presentaba la u ´ltima mejora de la cota inferior para N ) y de algunos de los distintos tipos de demostraciones que se han producido. Concretamente, nos centraremos en dos demostraciones: la que hace uso del an´alisis de Fourier discreto y prueba la combinatoria, precursora de la primera demostraci´ on del teorema de Sz´emeredi. En los siguientes dos cap´ıtulos, presentaremos de forma expl´ıcita la demostraci´ on original de Roth (mediante an´alisis de Fourier) y la demostraci´on combinatoria que dio Sz´emeredi (mediante cubos de Hilbert); en ambos casos, desarrollando la teor´ıa previa necesaria y luego exponiendo el llamado argumento iterativo, clave para demostrar que un conjunto contiene una progresi´on aritm´etica de tres elementos. Finalmente y en sentido contrario expondremos el famoso ejemplo de Behrend. En contraposici´ on al teorema de Roth, en este ejemplo se construye un conjunto de gran tama˜ no que no contiene tres elementos en progresi´on aritm´etica.
3
Tema 1
Introducci´ on 1.1.
Notaci´ on
A lo largo de esta exposici´on se emplear´a la siguiente notaci´on: Dado un n´ umero natural N , el s´ımbolo [N ] representar´a al conjunto {1, 2, . . . , N }. Dado un entero N , se considera el menor n tal que todo subconjunto A de [N ] con al menos n elementos contega progresiones aritm´eticas (no triviales) de tres elementos. A n se le denotar´a por r3 (N ). Formalmente, la funci´on r3 (N ) est´ a definida como r3 (N ) := m´ın{n ∈ N : ∀A ⊂ [N ] y |A| ≥ n, A contiene al menos una progresi´on aritm´etica no trivial de 3 t´erminos } De manera an´ aloga puede definirse la funci´on rk (N ) para todo k natural mayor que 3. Dado un n´ umero real x, los s´ımbolos bxc y {x} representar´an, respectivamente, su parte entera y su parte fraccionaria. Para escribir exponenciales de forma abreviada se emplear´an las siguientes notaciones: e(t) = e2πit , eq (t) = e2πit/q Cuando estemos trabajando en Z/Zn , escribiremos de forma abreviada a ≡ b (n) para decir a ≡ b (m´ od n). 5
´ TEMA 1. INTRODUCCION
Dadas dos funciones f y g, la notaci´on f = O(g) indicar´a que f (x) < ∞. l´ım sup g(x) x→∞ An´alogamente se podr´ a escribir f g. Asimismo, la notaci´ on f = o(g) indicar´a que l´ım
x→∞
f (x) = 0. g(x)
Por u ´ltimo, la notaci´ on f g indicar´a que f = O(g) y g = O(f ). N´otese que f = O(g) implica que existe una constante postiva C tal que |f (x)| ≤ C|g(x)| a partir de un |x| suficientemente grande. Al mismo tiempo, si se cumple f g existir´ an dos constantes positivas c1 y c2 tales que c1 |g(x)| ≤ |f (x)| ≤ c2 |g(x)|. Si se escribe f d g, significa que la constante c tal que |f (x)| ≤ c|g(x)| depende de d.
1.2.
Rese˜ na hist´ orica
El teorema de Roth es un conocido resultado sobre la existencia de progresiones aritm´eticas dentro de un conjunto de n´ umeros enteros. Dados dos enteros positivos d y k, una progresi´ on aritm´etica de k elementos con diferencia com´ un d es cualquier conjunto de la forma {n, n + d, n + 2d, . . . , n + (k − 1)d}, donde n es cualquier n´ umero natural. Estrictamente hablando, si d es igual a 0 tambi´en nos hallamos antes una progresi´ on aritm´etica, de las llamadas triviales. Obviamente estas progresiones no tienen inter´es, pero aparecen en el recuento de todas las progresiones sobre un conjunto.
1.2.1.
Teorema de Van de Waerden
Los or´ıgenes del teorema de Roth se remontan a 1927, a˜ no en el que se demuestra el teorema de Van der Waerden sobre progresiones aritm´eticas, que puede enunciarse de dos maneras distintas (en [14] se prueba que cada uno de ellas implica la otra): Teorema 1.1 (Van der Waerden (1)) Sean l y k dos enteros positivos. Entonces, para toda partici´ on de Z en l conjuntos C1 , C2 , . . . , Cl , existe un ´ındice j ∈ [l] tal que Cj contiene k elementos en progresi´ on aritm´etica. 6
˜ HISTORICA ´ 1.2. RESENA
Teorema 1.2 (Van der Waerden (2)) Sean l y k dos enteros positivos. Existe un n´ umero natural N (l, k) tal que, para todo N ≥ N (l, k) y para toda partici´ on del conjunto [N ] en l conjuntos C1 , C2 , . . . , Cl , existe un ´ındice j ∈ [l] tal que Cj contiene k elementos en progresi´ on aritm´etica. Observamos que, mientras en la versi´on (1) se utilizan conjuntos infinitos, todos los conjuntos que aparecen en la versi´on (2) son finitos. Por ello, la versi´on (2) del teorema (que ser´ a la m´ as importante para nosotros) se suele llamar versi´on finita del teorema de Van der Waerden. El teorema tambi´en se suele formular de una manera equivalente que proporciona una intuitiva interpretaci´on visual: Existe un n´ umero natural N (l, k) tal que si N ≥ N (l, k)) y cada n´ umero del conjunto [N ] se pinta de un color arbitrario entre l posibles colores, entonces existir´a una progresi´on aritm´etica de k n´ umeros pintados del mismo color; o, como tambi´en se le llama, una progresi´on monocrom´atica. Aunque este teorema supuso un enorme avance en el campo de la combinatoria, pose´ıa una gran desventaja: los valores obtenidos para N (l, k) eran enormes. Incluso tomando el menor l posible no trivial, la cota dada por Van der Waerden era N (2, k) ≤ A(k), para todo k ≥ 2, donde A(k) es la funci´ on de Ackermann, definida como A(k) = fk (k), para la familia recursiva de funciones: f1 (k) = k + 1 fj+1 (k) = (fj ◦ . . . ◦ fj )(1), j ≥ 1. | {z } k
Puede probarse que esta funci´on crece tan r´apido que no es expresable como composici´ on de operaciones ordinarias. Esta cota fue mejorada sustancialmente por Shelah sesenta a˜ nos m´as tarde (ver [13]). Pero las cotas que hoy conocemos, y que mejoraron las de Shelah, son un corolario de un resultado m´ as general que comentaremos a continuaci´on.
1.2.2.
Conjetura de Erd¨ os-Tur´ an
Definici´ on 1.3 Sea A ⊂ {1, 2, 3 . . .} un subconjunto arbitrario de los naturales. Se define la densidad superior de A como la siguiente cantidad: d(A) = l´ım sup N →∞
7
|A ∩ [N ]| . N
´ TEMA 1. INTRODUCCION
En el a˜ no 1936, Erd¨ os y Tur´ an, motivados por el teorema de Van der Waerden, conjeturaron un resultado mucho m´ as general que dicho teorema: Conjetura 1.4 (Erd¨ os-Tur´ an (1)) Sea A ⊂ N un conjunto con d(A) > 0. Entonces, para todo k ≥ 3, A contiene una progresi´ on aritm´etica de k elementos. Conjetura 1.5 (Erd¨ os-Tur´ an (2)) Sea k ≥ 3 un n´ umero entero y δ ∈ (0, 1]. Existe un n´ umero natural N (k, δ) tal que para todo N ≥ N (k, δ) y todo conjunto A ⊂ [N ] con |A| ≥ δN , A contiene una progresi´ on aritm´etica de k elementos. Al igual que ocurr´ıa con el teorema de Van der Waerden, existen dos versiones (finita e infinita) de la conjetura, y puede probarse (ver [14]) que ambas son equivalentes. En particular, es inmediato ver que la versi´on (2) implica la (1), y que en cualquier caso, si la conjetura es cierta, en particular demuestra tambi´en el teorema de Van der Waerden.
1.2.3.
Teorema de Roth
La conjetura pudo ser demostrada, aunque muchos a˜ nos m´as tarde. El primero en arrojar algo de luz sobre la conjetura fue precisamente Roth, quien en 1953 consigui´o demostrarla para el caso particular k = 3, mediante el teorema que hoy lleva su nombre y que es el objeto principal de este trabajo. En el cap´ıtulo 2 analizaremos este teorema con detalle. Teorema 1.6 (Roth, 1953) Sea N un n´ umero entero mayor o igual que 3. Entonces (1.1)
r3 (N )
N . log log N
En particular, este resultado proporciona una muy buena cota para la conjetura de Erd¨os-Tur´ an en el caso k = 3. En efecto, del enunciado anterior deducimos que N (3, δ) ee
c/δ
,
para alguna constante positiva c que no depende de δ. Hacemos aqu´ı un alto en el desarrollo de la conjetura de Erd¨os-Tur´an y nos detenemos en el desarrollo hist´ orico del teorema de Roth, que ocupar´a el grueso de los siguientes cap´ıtulos. En particular nos detendremos en dos aspectos. El primero de ellos es exponer brevemente las mejoras obtenidas sobre la cota original de Roth, (1.1). Dicha cota ha sido mejorada repetidas veces durante las u ´ltimas d´ecadas. A continuaci´ on hacemos un breve repaso a las mejoras m´as significativas: 8
˜ HISTORICA ´ 1.2. RESENA
En 1987 y 1990, respectivamente, Heath-Brown (ver [7]) y Sz´emeredi (ver [15]) consegu´ıan reducir el doble logaritmo a uno solo elevado a una constante α ≥ 1/20: c N , N (3, δ) exp . r3 (N ) (log N )α δ 1/α La mejor cota hasta hace unos meses era la que estableci´o Bourgain, por primera vez en 1999, consiguiendo llevar el exponente del logaritmo hasta 2/3. r3 (N )
N , (log N )(2/3)
N (3, δ) exp
c . δ 3/2
Finalmente, el mejor resultado a d´ıa de hoy es el dado por Sanders. Teorema 1.7 (Sanders) Sea N un n´ umero entero mayor o igual que 3. Entonces (1.2)
r3 (N )
N , (log N )3/4−ε
para todo ε > 0. O, de otra manera, N (3, δ) ε exp
c δ 4/3+ε)
,
donde c es una constante absoluta. Tambi´en cabe rese˜ nar, en sentido contrario, el ejemplo de Behrend, que construye un conjunto de gran tama˜ no sin progresiones aritm´eticas de tres elementos. Este ejemplo ser´ a estudiado en el cap´ıtulo 4. Teorema 1.8 (Behrend) Sea N un n´ umero natural suficientemente grande. Entonces, existe un conjunto A ⊂ [N ], conteniendo al menos p N exp(−c log N ) elementos (donde c es una constante real positiva) que no contiene ninguna progresi´ on aritm´etica no trivial de tres elementos. El segundo aspecto son las diferentes demostraciones surgidas del teorema de Roth, empleando t´ecnicas de diversa naturaleza. Entre ellas destacamos la reciente demostraci´ on de Croot (ver [4]) y la demostraci´on combinatoria que hizo Sz´emeredi, empleando cubos de Hilbert. Esta demostraci´on ser´a analizada minuciosamente en el cap´ıtulo 3. 9
´ TEMA 1. INTRODUCCION
1.2.4.
Teorema de Sz´ emeredi
Aunque en los pr´ oximos temas nos centraremos b´asicamente en el teorema de Roth y en algunas de sus demostraciones, no quisi´eramos concluir esta introducci´on sin incluir tambi´en la resoluci´ on de la conjetura de Erd¨os-Tur´an. Las t´ecnicas anal´ıticas empleadas por Roth proporcionaban una muy buena cota de la conjetura, pero u ´nicamente para el caso k = 3, siendo en principio in´ util para el resto de valores de k. Fue Sz´emeredi quien, mediante t´ecnicas combinatorias, logr´o salvar este escollo. Si bien la cota obtenida en su demostraci´on del teorema de Roth era peor que la que se obten´ıa en la demostraci´ on anal´ıtica, dicha demostraci´on ten´ıa el inter´es de contener en su interior el germen de lo que terminar´ıa siendo la demostraci´on completa de la conjetura de Erd¨ os-Tur´ an, para cualquier k ≥ 3. Por ello, a la conjetura se la conoce hoy en d´ıa como teorema de Sz´emeredi. De hecho, en 1969 (ver [16]), Sz´emeredi demostraba la conjetura de Erd¨os-Tur´an para el caso k = 4, y 6 a˜ nos despu´es (ver [17]) obten´ıa la soluci´on completa para cualquier k. Ambas demostraciones eran de car´acter combinatorio y utilizaban como argumento principal el llamado lema de regularidad. Al igual que lo conjetura de Erd¨os-Tur´an, el teorema de Sz´emeredi presenta una versi´on infinita y otra finita. Teorema 1.9 (Sz´ emeredi, versi´ on infinita, 1975) Sea A ⊂ {1, 2, 3, . . .} un conjunto arbitrario de n´ umeros naturales con densidad superior positiva. Entonces, A contiene una progresi´ on aritm´etica de longitud arbitrariamente grande. Teorema 1.10 (Sz´ emeredi, versi´ on finita, 1975) Sea δ > 0 y k un entero mayor o igual que 3. Entonces, existe un n´ umero N (k, δ) tal que para todo N ≥ N (k, δ) y todo conjunto A ⊂ [N ] con al menos δN elementos, A contiene una progresi´ on aritm´etica no trivial de longitud k. Las cotas inferiores para N (k, δ) obtenidas por Sz´emeredi para valores gen´ericos de k eran enormes. Pero en 1996, Tim Gowers sorprendi´o a la comunidad matem´atica con una demostraci´ on anal´ıtica del teorema de Sz´emeredi, consiguiendo adem´as mejorar sustancialmente las cotas inferiores para N (k, δ), y por tanto tambi´en para el teorema de Van der Waerden. Teorema 1.11 (Gowers, 1996) Sean N un entero mayor o igual que 3 y k cualquier n´ umero natural no inferior a 4. Entonces, rk (N )
N , (log log N )ck 10
1.3. S´INTESIS DE LOS DATOS k+9
con ck = 2−2
.
De este teorema se deduce de forma evidente el siguiente corolario, que es una expresi´ on m´ as fuerte del teorema de Van der Waerden: Corolario 1.12 Sean k ≥ 4, N ≥ 3 enteros positivos tales que el cada elemento del conjunto [N ] se pinta de un color arbitrario entre no m´ as de (log log N )ck colores. Entonces, [N ] contiene una progresi´ on monocrom´ atica de longitud k.
1.3.
S´ıntesis de los datos
Uniendo el ejemplo de Behrend (Teorema 1.8) y la mejor cota conocida para el teorema de Roth (Teorema 1.7), podemos acotar r3 (N ) (es decir, el mayor cardinal de un conjunto A ⊂ [N ] que no contenga progresiones aritm´eticas de tres elementos) superior e inferiormente: N e(−c
√
log N )
r3 (N ) ε
con ε cualquier real mayor que cero.
11
N , (log N )3/4−ε
´ TEMA 1. INTRODUCCION
12
Tema 2
Demostraci´ on anal´ıtica de Roth 2.1.
An´ alisis de Fourier en Z/nZ
En esta secci´ on trabajaremos en Z/N Z, con N un n´ umero primo, para hacer an´ alisis de Fourier discreto. Dado un conjunto A ⊂ Z/N Z, denotamos como A(n) a la funci´ on indicador de A. La transformada de Fourier discreta de la funci´on A es b A(n) =
X
eN (an).
a∈A
Dado a ∈ Z/N Z, el s´ımbolo (a)N denota al representante de la clase a m´odulo N comprendido entre 1 y N inclusive. Es decir,
(2.1)
(ma)N := m´ın{n ≥ 1 : n ≡ ma (N )}
Se verifica entonces que (a)N /N = {a/N }. Para poder aplicar el an´ alisis de Fourier a la existencia de progresiones aritm´eticas en un conjunto, partimos del concepto de distribuci´on uniforme. As´ı, dada una sucesi´ on num´erica {an }n∈N , se dir´ a que ´esta est´a uniformemente distribuida (m´ odulo uno) si para cualesquiera 0 ≤ α < β ≤ 1 se cumple |n ≤ N : {an } ∈ (α, β]| ∼ (β − α)N
cuando N → ∞.
Existe un criterio necesario y suficiente para determinar con facilidad cu´ando una sucesi´ on est´ a uniformemente distribuida: 13
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
Proposici´ on 2.1 (Criterio de Weil) Una sucesi´ on {an }n∈N est´ a uniformemente distribuida m´ odulo uno si y s´ olo si se verifica que para todo b ∈ Z \ {0}: X 1 e(ban ) = 0 l´ım sup N →∞ N n≤N Ser´ıa deseable que, para definir de manera an´aloga el concepto de distribuci´on uniforme m´ odulo N , la definici´ on fuese algo parecido a la siguiente: Dada una sucesi´ on {an }n∈Z/N Z , se dice que est´ a uniformemente distribuida m´ odulo N si para cualesquiera 0 ≤ α < β ≤ 1 se cumple |a ∈ A : (ma)N ∈ (αN, βN ]| ∼ (β − α)|A|. El problema es que esta definici´on s´olo tiene sentido de manera asint´otica. Es decir, cuando A ⊂ N y |A| tiende a infinito. Nuestro objetivo es llegar a una definici´on aplicable a subconjuntos A finitos, contenidos en Z/N Z. Por ello, necesitamos una definici´on m´ as consistente. En primer lugar introducimos el concepto de error para el conjunto A: Definici´ on 2.2 Dado un conjunto A de residuos m´ odulo N , se define el error para A como: #{a ∈ A : (ma)N ∈ (x, x + y]} y (2.2) Err(A) := m´ ax − . 0≤x 0 fijos, se verifica que, si Err(A) ≤ δ 2 , entonces b |A(m)| δ|A| para todo m 6≡ 0 (N ). 14
´ 2.1. ANALISIS DE FOURIER EN Z/N Z
Demostraci´ on: Dado un entero k ≥ 1, se tiene que si (ma)N ∈ (x, x + N/k], entonces (ma)N /N ∈ (x/N, x/N + 1/k). Y como (ma)N = N {ma/N }, se cumple
e
ma N
x 1 (ma)N =e +O = e =e N N N k x x 1 1 =e 1+O e O = e N k N k x 1 = e . +O N k
n ma o
Y entonces, utilizando esta observaci´on para x = jN/k, tenemos que: b |A(m)| =
X ma e N
a∈A
=
k−1 X j=0
=
k−1 X j=0
X a∈A (ma)N ∈(jN/k,(j+1)N/k]
X a∈A (ma)N ∈(jN/k,(j+1)N/k]
e
ma N
1 j +O . e k k
El n´ umero de elementos de A tales que (ma)N ∈ (jN/k, (j + 1)N/k] se puede estimar mediante la f´ ormula del error (2.2), tomando x = jN/k e y = N/k. As´ı, #{a ∈ A : (ma)N ∈ (x, x + y] N/k ≤ Err(A). − |A| N Luego 1 |#{a ∈ A : (ma)N ∈ (x, x + y]| = |A|( + O(Err(A))). k Por otro lado, es evidente que
(2.3)
k−1 X j=0
15
ek (j) = 0
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
Utilizando esto y los c´ alculos anteriores, concluimos que X X X k−1 1 j b + O |A(m)| = e k k j=0 a∈A a∈A (ma)N ∈(jN/k,(j+1)N/k] k−1 X 1 |A| j = |A| +O + O(Err(A)) e k k k j=o k−1 k−1 X X |A| j |A| + |A| ≤ e O(Err(A)) + O k k k j=0
(utilizando (2.3))
=
|A|
k−1 X
j=0
O(Err(A)) + O
j=0
1 |A| k · Err(A) + k
|A| k
La prueba se completa tomando k 1/δ, junto con la hip´otesis de que Err(A) δ 2 . Queda entonces: b |A(m)| = δ|A|(Err(A) + 1) δ|A|, lo que concluye la demostraci´ on.
De forma similar al criterio de Weil, este teorema proporciona una condici´on suficiente para que el error del conjunto A sea grande: si alguno de los valores de la b transformada de Fourier (es decir, {|A(m)|, m 6≡ 0 (N )} es suficientemente grande, entonces el error tambi´en lo ser´ a y existir´a un dilatado de A que no estar´a uniformemente distribuido. Este hecho tendr´a una importancia vital en la demostraci´on del teorema de Roth de este cap´ıtulo. Sin embargo, este resultado no nos permite asegurar la existencia o no de progresiones aritm´eticas en A en funci´on de su error. En la siguiente secci´ on presetaremos resultados que cuantifican esta idea intuitiva. A continuaci´ on, por razones que se expondr´an m´as adelante, nos planteamos buscar soluciones de una ecuaci´ on algo diferente, a˜ nadiendo un segundo conjunto de residuos B. Nos planteamos buscar soluciones a la ecuaci´on siguiente: (2.4)
a + b ≡ 2d
(m´ od N ),
a ∈ A; b, d ∈ B; A, B ⊂ Z/N Z.
Teorema 2.4 Sean dos conjuntos A, B ⊂ Z/N Z. Si se verifica la siguiente cota: (2.5)
b |A(m)| ≤
|B| |A|, para todo m 6≡ 0 (N ), 2N 16
´ ANAL´ITICA DE ROTH 2.2. DEMOSTRACION
entonces la ecuaci´ on (2.4) posee al menos
|A||B|2 2N
2N 1− soluciones (no tri|A||B|
viales). Demostraci´ on: El n´ umero de progresiones aritm´eticas (triviales o no) de tres elementos de A viene dado, seg´ un (2.4), por la siguiente f´ormula: XXX 1 X r(a + b − 2d) 1 X b b b e = A(r)B(r)B(−2r) N N N a∈A b∈B d∈B
r (mod.N )
r (mod.N )
b B(0) b B(0) b Obviamente, el sumando en r = 0 vale N1 A(0) = |A||B|2 /N . Para el resto de residuos, puede establecerse la siguiente cota: 1 X b b b |A(r)||B(r)|| B(−2r)| ≤ N r6≡0
(Cauchy-Schwarz) ≤
X 1 b b b m´ax |A(m)| |B(r)|| B(−2r)| N m6≡0 r6≡0 1/2 1/2 X X 1 2 b b b 2 m´ax |A(m)| |B(s)| |B(t)| N m6≡0 s6≡0
t6≡0
p 1 b (Plancherel) = m´ax |A(m)| N |B|N |C| N m6≡0 p b = m´ax |A(m)| |B||B|. m6≡0
Por tanto, el n´ umero de soluciones de (2.4) est´a acotado inferiormente por |A||B|2 /N − b m´ axm6≡0 |A(m)| · |B|. Y entonces, si se cumple (2.5), existen al menos |A||B|2 /2N soluciones (triviales o no) para (2.4). Si quitamos las triviales, que por construcci´on han de ser exactamente |B|, nos quedan |A||B|2 |A||B|2 2N − |B| = 1− 2N 2N |A||B| soluciones no triviales.
2.2.
Demostraci´ on anal´ıtica de Roth
Teorema 2.5 (Roth) Sea δ > 0. Existe una constante absoluta C > 0 tal que si N (C/δ) es un entero positivo mayor que Nδ = ee , entonces todo subconjunto A de [N ] con al menos δN elementos contiene una progresi´ on aritm´etica no trivial de 3 elementos. Observaci´ on: El teorema tambi´en puede enunciarse al rev´es; es decir, tomando un entero N y sin m´ as que invertir la f´ormula, deducir el m´ınimo valor de δ que puede 17
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
tomarse. Es f´ acil ver que ese valor es δ(N )
1 . log log N
De aqu´ı se deduce la siguiente cota inferior para el tama˜ no de un subconjunto de [N ] que contiene forzosamene progrsiones aritm´eticas de 3 elementos: r3 (N )
N . log log N
Demostraci´ on: En primer lugar, aclaramos que en lo sucesivo y salvo que se especifique otra cosa, cuando hablemos de progresiones aritm´eticas estaremos refiri´endonos s´olo a progresiones aritm´eticas no triviales. Para comenzar la demostraci´ on, n´otese que tomando cualquier δ mayor que 2/3, por ejemplo δ = 3/4, es f´ acil comprobar que el teorema es v´alido para cualquier N ≥ 6, ya que entonces A poseer´ a al menos dos tercios de los elementos de [N ] m´as un elemento adicional, y por tanto A siempre contendr´a tres elementos consecutivos. Observemos tambi´en que si el enunciado del teorema se verifica para un cierto entonces trivialmente se verifica tambi´en para cualquier δ > δ ∗ , ya que cualquier A con al menos δN elementos contiene m´ ultiples subconjuntos A∗ con m´as de δ ∗ N elementos. Por tanto, para demostrar el teorema fijaremos un δ ∈ (0, 3/4), un entero N y un conjunto A cumpliendo las hip´otesis del enunciado y determinando que una de las dos siguiente condiciones debe satisfacerse: δ∗,
O bien A contiene una 3-progresi´on aritm´etica no trivial (con lo que habr´ıamos probado el teorema), O bien existe una progresi´ on aritm´etica de longitud N1 < N que contiene m´as de δ1 N1 elementos de A, con δ1 > δ(1 + cδ) para una cierta constante positiva c a determinar m´ as adelante. La clave para demostrar el teorema est´a en que siempre podemos aplicar este hecho (que ser´ a demostrado a lo largo de este cap´ıtulo) repetidas veces, cada vez sobre conjuntos m´ as peque˜ nos pero con mayor densidad. Si llamamos A1 a A ∩ N1 , podemos operar sobre ´el de la misma forma que hicimos con A, y obtener otro subconjunto A2 con densidad sobre N2 < N1 mayor de lo que era la densidad de A1 en N1 . En un escenario en que se d´e el segundo caso de forma indefinida para todos los Aj , llegar´a un momento en que una cierta densidad δk haya crecido lo suficiente con respecto a δ como para superar al valor cr´ıtico δ = 3/4, con lo cu´al Ak contendr´ıa tres elementos en progresi´ on aritm´etica y habr´ıamos acabado, ya que Ak ⊆ A. El precio que hay 18
´ ANAL´ITICA DE ROTH 2.2. DEMOSTRACION
que pagar por conseguir un subconjunto m´as denso en cada paso es que el valor N se ir´ a reduciendo tambi´en a cada paso, pudiendo incluso llegar a valores sin sentido (menores que uno). Es necesario, por lo tanto, cuantificar el crecimiento de las deltas para asegurarnos de que el argumento iterativo se puede seguir empleando en cada paso; de ah´ı surge la cota inferior de N que nuestra el enunciado y que vamos a demostrar. A la hora de realizar an´ alisis de Fourier discreto sobre A, es m´as sencillo operar si N es un n´ umero primo. Por el postulado de Bertrand sabemos que existe al menos un n´ umero primo entre N y 2N . Este resultado se ha mejorado varias veces, y actualmente se sabe que existe un primo entre N y N + N 2/3 (de hecho, este resultado puede mejorarse hasta valores cercanos a N + N 1/2 ; por ejemplo, en [1] se toma N + N 1,525 ). Dado entonces N y un conjunto A ⊂ [N ] con densidad al menos δ, si reemplazamos N por p, el menor primo no inferior N , entonces N N ≥ δp p N + N 2/3 ! δN 2/3 1 ≥ p δ − 1/3 ≥ p(δ − δ 4 ), = p δ− N + N 2/3 N
|A| = δN = δp
donde en la u ´ltima desigualdad suponemos que N > δ −12 . Observaci´ on: N´ otese que suponer N > δ −12 no provoca p´erdida de generalidad C/δ para el teorema. En efecto, es una cuenta sencilla comprobar que ee ≥ δ −12 para todo δ > 0 y para cualquier C > 11/10. Por tanto, si suponemos (2.6)
N > ee
C/δ
, C > 11/10,
los c´ alculos anteriores son l´ıcitos. Y, como se ver´a al final de este cap´ıtulo, el teoC/δ rema se demuestra para N > ee , donde C es una constante mayor que 50, por lo que podemos utilizar esta suposici´on. Por tanto, si al realizar la primera iteraci´on en lugar de N consideramos N 0 = p, entonces un conjunto A que tuviera al menos δN elementos tendr´a al menos (δ −δ 4 )N 0 elementos, luego la densidad de A en N 0 ser´a δ 0 ≥ δ − δ 4 ; y tras realizar una primera iteraci´ on la densidad de A1 en N10 pasar´a a ser δ 0 + cδ 02 = δ − δ 4 + c(δ − δ 4 )2 = δ + c0 δ 2 + O(δ 4 ) δ + c0 δ 2 . En adelante, abusando de la notaci´on, nos referiremos a N 0 como N y a c0 como c, asumiendo que reemplazar N por un primo no afecta al argumento de densidad por lo que acabamos de probar (aunque, obviamente, este hecho debe ser tenido en cuenta a la hora de calcular c).
19
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
Procedamos a demostrar el argumento iterativo, tomando un δ ∈ (0, 3/4), un entero [N ] y un subconjunto A que satisfagan las hip´otesis del enunciado. Supongamos por reducci´ on al absurdo que [A] no contiene progresiones aritm´eticas. Distinguiremos dos casos: Sean B1 := A ∩ [N/3] y B2 = A ∩ ([N ] \ [2N/3]). Si (2.7)
|B1 | ≥ (1 + cδ)|A|/3
´o |B2 | ≥ (1 + cδ)|A|/3,
entonces el argumento iterativo est´a completado, tomando N1 = bN/3c y A1 = B1 o bien A1 = {N − a : a ∈ B2 }, seg´ un sea B1 o B2 quien verifique (2.7). Si no se verifica (2.7), se considera el conjunto formado por el tercio central de los elementos de A. Es decir, B = A ∩ ([2N/3] \ [N/3]). Y por hip´ otesis de que no se cumplen los dos primeros casos, es claro que (2.8)
|B| > (1 − 2cδ)|A|/3.
A la vista de lo hecho hasta ahora, la constante c ha de estar en el intervalo (0, 1/2δ) para que los datos tengan sentido. Poniendo, por ejemplo, c = 1/8δ, se tiene que o bien |A1 | ≥ 9δ 8 N1 (en el primer caso), o bien el conjunto |B| verifica δ |B| > |A|, 4 sin m´as que sustituir en c. Observaci´ on: En este punto podemos f´acilmente intercambiar c por la c0 que quedaba al sustituir N por un primo. Como c0 δ 2 = cδ 2 + O(δ 4 ), queda c0 = c + O(δ 2 ), con lo cu´al podemos, en lugar de tomar c = 1/8δ, tomar uno ligeramente mayor (ya que, si se desarrolla el t´ermino de error se deduce que c > c0 ). Concretamente, existe un c ∈ [1/8δ, 1/4δ] tal que, operando como ahora, c0 vale 1/8δ. Por simplicidad en la notaci´on, omitiremos expl´ıcitamente este paso y en adelante supondremos que la c de la que estamos hablando es c0 . Vamos a aplicar el an´ alisis de Fourier que vimos en la secci´on 2.1. Recordemos que, dadas las variables a ∈ A y b, d ∈ B, consider´abamos la ecuaci´on (2.9)
a + b ≡ 2d (N ) 20
´ ANAL´ITICA DE ROTH 2.2. DEMOSTRACION
Se verifica que si A no contiene progresiones de tres elementos, esta ecuaci´on no tiene soluci´ on que no tenga todos los coeficientes iguales. Esto se deduce del hecho de que N/3 < b, d < 2N/3, por lo que 2N/3 < 2d < 4N/3 y 0 < 2d − b < 3N/3 = N ; con lo que de existir una soluci´ on no trivial para esta ecuaci´on, se verificar´ıa a+b = 2d y esto no es posible por hip´ otesis, ya que en A no hay progresiones aritm´eticas de 3 elementos. Como consecuencia de lo anterior, afirmamos que debe existir un m 6≡ 0 (N ) tal b que |A(m)| > (1 − 2cδ)|A|/6. Para probar esto, recurrimos al teorema 2.4. Como no existen soluciones a la ecuaci´on (2.4), debe existir alguna clase m m´odulo N , no nula, tal que: p |B||B| |B| |A| |B| (1 − 2cδ)|A| |A| b (2.10) |A(m)| > |A| = ≥ δ> δ = δ(1 − 2cδ) 2N 2 N 2 2·3 6 Equivalentemente, sustituyendo c por 1/8δ,
(2.11)
δ b |A(m)| > |A| 8
Podemos interpretar este hecho de la siguiente forma: existe un dilatado de A (concretamente, el conjunto {ma : a ∈ A}) que no est´a uniformemente distribuido. Por tanto, dicho conjunto est´a lejos de presentar una cierta estructura aleatoria. Esto propiciar´ a que exista una gran progresi´on dentro de ´el conteniendo m´as elementos del dilatado de lo que cabr´ıa esperar. Pero necesitamos algo m´as; para evitar el problema de que las progresiones en Z/N Z no son progresiones genuinas (es decir, progresiones en Z), es preciso que la progresi´on que obtengamos cumpla ciertas propiedades que hagan que sea f´ acil de descomponer en progresiones genuinas. En este sentido, tenemos la siguiente definici´ on: Definici´ on 2.6 Dada una progresi´ on aritm´etica P de diferencia entre t´erminos d en Z/N Z, diremos que P es una progresi´ on no solapada si |P |d < N . Es inmediato comprobar que toda progresi´on no solapada P puede descomponerse en dos progresiones genuinas P1 , P2 , ya que por construcci´on P s´olo puede dar una vuelta a Z/N Z. Nuestro pr´oximo objetivo va a ser, partiendo del hecho de que el conjunto mA no est´ a uniformemente distribuido, tratar de obtener una progresi´ on P ⊂ Z/N Z sobre la que A tenga una densidad relativa mayor de la que ten´ıa en N y cumpliendo al mismo tiempo que P sea no solapada. b Lema 2.7 Si existen m 6≡ 0 (N ) y ε > 0 tales que |A(m)| ≥ εN √ , entonces existe una progresi´ on aritm´etica no solapada P ⊂ Z/N Z tal que |P | ≥ N /4 y |A ∩ P | ≥ (δ + ε/4)|P |. 21
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
Demostraci´ on: En primer √ lugar, afirmamos que existe una progresi´on no solapada b ≥ |Q|/2. Para verlo, consideramos las N Q ⊂ Z/N Z tal que |Q| ≥ N /4 y |Q(m)| coordenadas (0, 0), (1, m), (2, 2m), . . . , ((N − 1), (N − 1)m), m´odulo N . Todas ellas est´an en la malla {(x, y) ∈ Z2 : x, y = 0, 1, . . . , N − 1}. √ la malla en cuadrados iguales de lado l = N/b N c. Tendemos entonces √ Dividimos b N c2 < N cuadrados (la desigualdad siempre es estricta, pues N es primo), y por lo tanto dos de los pares arriba nombrados deben estar en un mismo cuadrado. Es decir, existen enteros diferentes s, t ∈ {0, 1, . . . , N − 1} tales que t − s ≤ l (N ) y m(t − s) ≤ l (N ). Fijemos d := t − s y consideremos la progresi´on √ N Q := {zd : |z| ≤ b c}, 2π √ que por construcci´ on tiene b N /πc elementos. Se verifica lo siguiente (recu´erdese que Q denota por abuso tanto al conjunto como a su funci´on indicador, mientras no se indique otra cosa): X qm X qdm b e |Q(m)| = Q(q)e = N N q∈Q |q|≤ 12 |Q| X X qdm 2πqdm ≥ Re . e cos = N N 1 1 |q|≤ 2 |Q|
|q|≤ 2 |Q|
Por otro lado, $√ % 2πqdm 1 1 N 1 1 N N ≤ 2π 2 |Q|l N ≤ π 2π b√N c N ≤ 2 . Y entonces (2.12)
b |Q(m)| ≥
X |q|≤ 12 |Q|
1 1 |Q| cos ≥ |Q| cos ≥ . 2 2 2
Ya tenemos Q, y a partir de ´el vamos a construir P , que ser´a un trasladado suyo. En primer lugar, dado un conjunto A, definimos su funci´ on indicador balanceada como fA (a) := A(a) − δ, que es la trasladada de la funci´on indicador P A(a) con media nula. Esto es inmediato de probar, simplemente viendo que n(mod.N ) fA (n) = P P A(n) − n(mod.N ) n(mod.N ) δ = A − δN = 0.
22
´ ANAL´ITICA DE ROTH 2.2. DEMOSTRACION
Pasamos a construir P . Pongamos P = Q + q, para alg´ un q a determinar (ser´ an entonces equivalentes las funciones Q(k − q) y P (k), para cualquier k ∈ N ; adem´ as los conjuntos P y Q tendr´ an el mismo cardinal). Se tiene que X ε ε |A ∩ P | ≥ (δ + )|P | ⇔ A(k)P (k) ≥ δ|P | + |P | 4 4 k(mod.N ) X X ε δ P (k) ≥ |Q| ⇔ A(k) − 4 k(mod.N ) k(mod.N ) X ε (A(k) − δ) Q(k − q) ≥ |Q| ⇔ 4 k(mod.N ) X ε ⇔ fA (k)Q(k − q) ≥ |Q|. 4 k(mod.N )
Pongamos G(q) =
P
k fA (k)Q(k
− q). Por hip´otesis y utilizando (2.12), se tiene
que X |G(q)| = f (k)Q(k − q) A q(mod.N ) q(mod.N ) k(mod.N ) X
X
b ≥ |fc A (m)||Q(m)| 1 1 b |Q| ≥ ε|Q|, ≥ |A(m)| 2 2 donde hemos utilizado que las funciones A y fA tienen por construcci´on la misma transformada sobre cualquier m 6≡ 0 (M ), adem´as de la desigualdad siguiente: X
f ∗ g(x) =
x
XX x
=
f (y)g(x − y)
y
1 X b 2 g (r)|2 |f (r)| |b N r
≥ |fb(m)||b g (m)|, donde x, y y r son variables mudas que recorren los enteros m´odulo N . Como, on, P por construcci´ PG(q) tambi´ P en es de media nula por serlo fA , (es f´acil de ver que q(mod.N ) G(q) = q(mod.N ) k(mod.N ) (A(k) − δ)Q(k − q) = 0), se tiene que P 1 a un q tal que G(q) + |G(q)| ≥ q(mod.N ) G(q) + |G(q)| ≥ 2 εN |Q|, por lo que existir´ 1 1 a que G(q) ≥ 4 ε|Q|, y por tanto, fijando este q y tomando 2 ε|Q|. Esto implicar´ P = Q + q, queda probado el lema.
23
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
El siguiente paso es dividir la progresi´on P en dos progresiones genuinas, conservando una densidad relativa suficientemente grande. En este sentido, tenemos el siguiente lema: Lema 2.8 Si P ⊂ Z/N Z es una progresi´ on aritm´etica no solapada tal que |A ∩ P | ≥ (δ + ε0 )|P |, encontes existe una progresi´ on genuina P1 con P1 ≥ 21 ε0 |P | y |A ∩ P1 | ≥ (δ + 21 ε0 )|P1 |. Demostraci´ on: Basta escribir P = P1 t P2 , con P1 y P2 progresiones genuinas. Supongamos por ejemplo que |P1 | ≤ |P2 |. Si |P1 | ≤ 21 ε0 |P |, entonces 1 1 |A ∩ P2 | ≥ (δ + ε0 )|P | − |P1 | ≥ (δ + ε0 )|P | ≥ (δ + ε0 )|P2 |, 2 2 con lo que P2 satisfar´ıa el lema. En caso de que no se cumpla |P1 | ≤ 12 ε0 |P |, tanto P1 como P2 verifican 1 |P1 |, |P2 | ≥ ε0 |P |. 2 Y A debe tener densidad al menos δ + ε0 en uno de ellos. En cualquiera de los dos casos, llamando P1 a aqu´el de los dos que nos de el resultado buscado, se tiene el lema. Combinando ahora todo lo que sabemos, podemos llegar al resultado final. En primer lugar, de (2.11) se deduce que (2.13)
δ δ δ2 b |A(m)| ≥ |A| ≥ δN = N. 8 8 8
Luego nuestro ε ser´ a δ 2 /8. Del lema 2.7 deducimos que existe una progresi´on P , √ 2 δ2 no solapada, tal que |P | ≥ N /4 y |A ∩ P | ≥ (δ + δ 4/8 )|P | = (δ + 32 )|P |. P se puede descomponer en dos progresiones genuinas P1 y P2 y, utilizando el lema 2.8, existir´a una de ellas, digamos P1 , tal que √ √ 1 δ2 N 1 P1 ≥ ε|P | ≥ = 2−8 δ 2 N 2 8 8 4 y 1 |A ∩ P1 | ≥ (δ + ε)|P1 | = (δ + 2−6 δ 2 )|P1 |. 2 Podemos reflejar esto en una proposici´on final: Proposici´ on 2.9 Fijados un δ ∈ (0, 1], un entero N suficientemente grande en funci´ on de δ, y un conjunto A ⊂ [N ] con |A| ≥ δN , entonces se cumple uno de los dos siguientes hechos: 24
´ ANAL´ITICA DE ROTH 2.2. DEMOSTRACION
A contiene tres elementos en progresi´ on aritm´etica. Existe una progresi´ on aritm´etica genuina P1 ⊂ [N ], con √ (2.14) |P1 | ≥ 2−8 δ 2 N y |A ∩ P1 | ≥ (δ + 2−6 δ 2 )|P1 |. N´ otese que, el caso en que se cumpla (2.7) est´a incluido en la segunda opci´ on aqu´ı expuesta, ya que se obtiene una progresi´on mayor y con mejor densidad, por lo que la opci´ on aqu´ı expuesta es m´as restrictiva y siempre podemos, sin p´erdida de generalidad, suponer que se da uno de los dos casos que nombramos en la proposici´on 2.9. El paso iterativo final se basa en aplicar repetidamente la proposici´on 2.9. Dados δ, N y A como en el enunciado, supongamos que A no contiene progresiones aritm´eticas de 3 elementos (si no, ya habr´ıamos acabado). Por lo que √ hemos visto, en el peor −8 2 escenario podemos considerar una progresi´on N1 > 2 δ N tal que A1 = A ∩ [N1 ] 1 2 contiene al menos (1 + 216 δ)δN1 = (δ + 64 δ )N1 elementos (sin m´as que llamar N1 al P1 de la proposici´ on). Repitiendo el paso una vez m´as, tenemos una progresi´on de q p √ −8 2 −8 2 N2 ≥ 2 δ1 N1 ≥ 2 δ1 2−8 δ 2 N elementos tal que A2 = A1 ∩ [N2 ] tiene al menos δ2 N2 elementos, con δ2 ≥ δ1 + 2c δ12 ≥ (δ + 216 δ 2 ) + 216 (δ + 216 δ 2 ) ≥ δ + 2 216 δ 2 . Repitiendo este argumento un n´ umero k de pasos, tendremos que la densidad δk ser´a al menos de δ + k 216 δ 2 . Por lo tanto, para 6 doblar la densidad, son necesarios 2δ pasos. Para doblarla de nuevo y llegar a 4δ, 6 6 6 son necesarios en total 2δ + 22δ pasos (es decir, 22δ pasos adicionales. En general, tras 26 −1 + . . . + 2−(l−1) ) ≤ 26 2 = 27 pasos, la densidad ser´ a forzosamente mayor δ (1 + 2 δ δ que 3/4, con lo que el correspondiente conjunto Ak contendr´a forzosamente una progresi´ on aritm´etica, as´ı como sus predecesores; en particular, A tambi´en contendr´a una progresi´ on aritm´etica, lo que bastar´ıa para probar el teorema de Roth. Para que el argumento sea v´alido, necesitamos que el valor de Nk tenga sentido; por ejemplo, que sea mayor que uno. Sabemos, por ejemplo, que el conjunto Nk contiene 3 2 3−k k k m´ as de δ 2 δ 2/2 δ 2/3 · . . . δ 2/k 2−2 2−2 · . . . · 2−2 N 1/2 ≤ δ 4 216 N 1/2 elementos. Por k tanto, basta probar que δ 4 N 1/2 ≥ 216 . Tomando logaritmos: 1 log N + 4 log δ ≥ 16 log 2 ⇒ 2k 7 δ −1
⇒ log N ≥ [16 log 2 + 4 log(δ −1 )]2k = [16 log 2 + 4 log(δ −1 )]22 25
.
´ ANAL´ITICA DE ROTH TEMA 2. DEMOSTRACION
Por otro lado, la funci´ on 24λ − 16 log 2 − 4 log λ es positiva en el rango λ ∈ [1, ∞). −1 Por tanto, 24δ ≥ 16 log 2 + 4 log δ −1 en el rango δ ∈ (0, 1), y es suficiente que se cumpla log N ≥ 2(2
7 +4)δ −1
7 δ −1
≥ 22
24δ
−1
≥ 22
7 δ −1
[16 log 2 + 4 log(δ −1 )]
Equivalentemente, log log N ≥ (27 + 4) log 2 · δ −1 . Luego es suficiente que N ≥ exp[exp(132 log 2 · δ −1 )] = exp[exp(Cδ −1 )].
26
Tema 3
Demostraci´ on combinatoria de Sz´ emeredi Unos quince a˜ nos despu´es de publicarse la demostraci´on original del teorema de Roth, Endre Sz´emeredi present´o otra alternativa que, si bien no mejoraba la cota de Roth (de hecho era una cota terriblemente pobre a nivel pr´actico), conten´ıa algunos elementos de lo que ser´ıa la demostraci´on general para la existencia de progresiones con k elementos, donde k es cualquier n´ umero natural. La clave de la demostraci´on se basa, al igual que en la original, en un argumento de densidad que se puede aplicar repetidas veces sobre A y sus sucesivos subconjuntos. Concretamente probaremos que, fijos δ, N y A, siendo A cualquier conjunto que contenga al menos δN elementos, siempre ocurre uno de los siguientes hechos: 4
O bien N ≤ (64/δ 2 )e , lo cu´al no es ninguna restricci´on, ya que en nuestras hip´ otesis exigiremos que N sea mayor que una cantidad notablemente mayor que ´esta. O bien A contiene una progresi´on aritm´etica, que es lo que buscamos probar. O bien, en el caso m´ as general, existir´a una progresi´on larga P ⊂ [N ] donde la densidad relativa de A aumente hasta, al menos δ+cδ 2 , con c = 1/16. Mientras el tama˜ no de las sucesivas progresiones no sea demasiado peque˜ no, siempre podremos reiterar indefinidamente este paso a voluntad hasta que la densidad relativa crezca hasta llegar a 3/4, por lo que como ya vimos en el cap´ıtulo anterior, A contendr´ıa una progresi´on aritm´etica. Nuestro estudio se basar´a en probar que esta tercera opci´on se dar´a siempre que no se d´e alguna de las otras dos. A lo largo de este cap´ıtulo hablaremos varias veces de la densidad relativa o densidad de un conjunto en otro. En un sentido preciso, esto 27
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
quiere decir lo siguiente: si tenemos dos conjuntos A, P ⊂ N, ambos finitos, la densidad de A en P se define como (3.1)
1 |A ∩ P |. |P |
d(A|P ) :=
N´otese que no es preciso que A est´e contenido en P para que la definici´on tenga sentido.
3.1.
Resultados previos
La demostraci´ on est´ a estructurada en tres grandes resultados previos junto con un lema final que se apoya en los tres anteriores y que constituye el argumento clave para la demostraci´ on de Sz´emeredi. En primer lugar, veremos dos proposiciones sobre densidades relativas de un conjunto en una serie de subconjuntos de P que forman una uni´on disjunta de ´este. A continuaci´on analizaremos resultados para poder dividir P en distintos subconjuntos que sean progresiones aritm´eticas de raz´on com´ un. Por u ´ltimo, introduciremos el concepto de k-cubo o cubo de Hilbert, y veremos condiciones suficientes para que un conjunto A gen´erico contenga al menos un k-cubo. Todos estos ingredientes formar´ an en la siguiente secci´on el lema final con el que poder demostrar el teorema de forma satisfactoria. En lo que sigue, habitualmente A representar´a el conjunto que queremos probar que contiene progresiones aritm´eticas y P la progresi´on que queremos subdividir en varias progresiones m´ as peque˜ nas, de modo que la densidad de A en alguna de ellas sea significativamente mayor de lo que lo era en P . En este sentido tenemos el siguiente lema: Lema 3.1 Sean A, P ⊂ N dos conjuntos finitos de modo que P puede escribirse como uni´ on disjunta finita de los conjuntos P1 , . . . , Pk . Es decir, P =
k G
Pj .
j=1
Entonces se verifica d(A|P ) =
k X |Pj | j=1
|P |
· d(A|Pj )
28
3.1. RESULTADOS PREVIOS
Demostraci´ on: Por (3.1), es equivalente demostrar k
k
j=1
j=1
|A ∩ P | X |Pj | 1 X = · d(A|Pj ) = |Pj | · d(A|Pj ). P P |P | Y esto es cierto, ya que k [ |Pj | · d(A|Pj ) = |A ∩ Pj | = A ∩ Pj = |A ∩ P | j=1 j=1 j=1
k X
k X
Observaci´ on: De este lema se deduce en particular que alguna de las densidad del nivel inferior es al menos del mismo tama˜ no que la original. Es decir, existe alg´ un Pi tal que d(A|Pi ) ≥ d(A|P ). A˜ nadiendo unas hip´ otesis poco restrictivas a P , podemos decir algo m´as que esto; de hecho podemos determinar que alguna de esas densidades es algo mayor que la original: Proposici´ on 3.2 Sea δ ∈ (0, 8/9] cualquiera y sean M < N dos n´ umeros naturales. Sea A ⊂ [N ] un subconjunto con |A| = δN elementos y supongamos que existe un conjunto P con A ⊂ P ⊂ [N ] y tal que |P | ≤ (1 − δ/8)N . Sea P1 ∪ P2 ∪ . . . ∪ Pk una partici´ on de P (es decir, P es uni´ on disjunta de los Pj ) tal que kM ≤ N . Entonces existe un i ∈ [k] tal que: (3.2)
d(A|Pi ) ≥ (δ +
1 2 δ ) 16
y
|Pi | ≥
δ3 M 16
Demostraci´ on: En primer lugar vamos a ver que necesariamente alguno de los Pj debe verificar |Pj | ≥ (δ 3 /16)M . En caso de que ninguno lo verificase, se tendr´ıa |P | ≤ k m´ax |Pi | ≤ i∈[k]
δ3 N δ3 M =N < N δ = |A|, M 16 16
que es obviamente una contradicci´on. Vamos a dividir entonces los Pj en dos grupos, seg´ un excedan o no esta cantidad. Definimos los conjuntos: J1 := {j ∈ [k] : Pj ≥ (δ 3 /16)M } J2 := [k] \ J1 . 29
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
con J1 no vac´ıo por construcci´ on. Se tiene, como |A| = δN y |P | ≤ (1 − δ/8)N , que d(A|P ) =
δ δ + δ 2 /8 |A| ≥ = ≥ δ + δ 2 /8. |P | 1 − δ/8 1 − δ 2 /64
Utilizando el lema 3.1, X
d(A|P ) =
d(A|Pj )
j∈J1
X Pj Pj + d(A|Pj ) . P P j∈J2
Podemos establecer la siguiente cota sobre los conjuntos de menor tama˜ no; es decir, aquellos cuyo ´ındice est´ a en J2 : X
d(A|Pj )
X Pj Pj N δ 3 M/16 δ2 ≤ ≤ = . P |A| M δN 16 j∈J2
j∈J2
Recopilando todo lo obtenido hasta ahora, tenemos que δ+
X Pj δ2 δ2 ≤ d(A|P ) ≤ + d(A|Pj ) . 8 16 P j∈J1
Y por tanto, δ+
X Pj δ2 ≤ d(A|Pj ) ≤ d(A|P ) ≤ m´ax d(A|Pj ). j∈J1 16 P j∈J1
Luego efectivamente existe un ´ındice i ∈ [k] que verifica (3.2).
Pongamos M = log log N en la proposici´on anterior. Nuestro objetivo ahora ser´a recubrir A con una uni´ on disjunta de progresiones P1 , . . . , Pk tales que k ≤ log N log N y tal 2 que la uni´ on de todas ellas tenga, al menos, (δ + δ /16) elementos. Entonces, por lo que acabamos de probar, alguna de esas progresiones, pongamos Pi , tendr´a al menos (δ 3 /16) · log log N elementos, con d(A|Pj ) ≥ δ + δ 2 /16. Con lo cu´al, existe una progresi´on bastante larga en la cu´ al la densidad relativa de A se incrementa sensiblemente, que es nuestro objetivo principal. Para poder demostrar el teorema satisfactoriamente, necesitamos que las k progresiones sean de la misma raz´ on, es decir, que todas ellas sean de diferencia com´ un d. Para lograr esto, estudiaremos algunos resultados t´ecnicos sobre progresiones a continuaci´ on: Definici´ on 3.3 Sea A ⊂ N un conjunto finito y d un n´ umero natural. Dados dos elementos a, b ∈ A, decimos que son equivalentes, y escribimos a ∼d b o bien a ∼ b si existe una progresi´ on P = {a, a + d, a + 2d, . . . , a + sd = b} ⊂ A 30
3.1. RESULTADOS PREVIOS
o bien P = {b, b + d, b + 2d, . . . , b + sd = a} ⊂ A. Observaci´ on: Obviamente, la noci´on de equivalencia que hemos dado depende del par´ ametro d, que debe ser fijo. A´ un as´ı, a lo largo de la exposici´on utilizaremos la notaci´ on ∼ omitiendo el valor d siempre que no haya lugar a confusi´on.
Proposici´ on 3.4 Se verifican las siguiente propiedades: 1. La relaci´ on dada en la definici´ on anterior es una relaci´ on de equivalencia. De hecho, descompone a A en k clases de equivalencia: A=
k G
Jj .
j=1
2. El valor k viene determinado por la siguiente propiedad: k = |(A + d) \ A|. 3. El complementario de A, que designamos con A, queda descompuesto en como m´ aximo k + d clases de equivalencia mediante ∼. Demostraci´ on: (1) Las propiedades reflexiva y sim´etrica son evidentes por definici´on. La transitiva es muy sencilla de probar. Supongamos que tenemos a, b, c ∈ A, todos distintos (si no ya estar´ıa probado), y verificando a ∼ b, b ∼ c. Sean P y Q, respectivamente, las progresiones que generan la equivalencia de a con b y la de b con c. Supongamos que a < b < c. Entonces a y c son equivalentes tomando P ∪ Q = {a, a + d, . . . , a + sd = b, a + (s + 1)d, . . . , a + (s + t)d = c}. En cualquier otro caso, a y c est´an ambos en P o ambos en Q y se obtiene la equivalencia tomando un subconjunto adecuado. (2) Sea B := (A + d) \ A. Afirmamos que existe una aplicaci´on sobreyectiva ϕ : A −→ B, con la caracter´ıstica de que cada ϕ−1 (B) es una de las clases Jj . En efecto, si definimos para a ∈ A (3.3) se tiene que: 31
ϕ(a) = m´ın{b ∈ B : {a, a + d, . . . , a + sd = b} ⊂ A},
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
La aplicaci´ on est´ a bien definida; es decir, para cada a ∈ A, existe al menos un b ∈ B cumpliendo la condici´ on (3.3). Si no fuera as´ı, deber´ıa existir un n ≥ 1 Sn−1 tal que j=0 {a + kd} ⊂ A ∩ B y a + nd 6∈ A ∪ B. Pero si a + (n − 1)d est´a en A, entonces a + nd tiene que estar en B por definici´on, y entonces se producir´ıa una contradicci´ on. La aplicaci´ on es sobreyectiva. Si existiese un b ∈ B tal que ϕ−1 (b) = ∅, entonces b − d ∈ B. Pero al mismo tiempo, por definici´on b est´a en A + d, por lo que b − d est´a en A. Por tanto, b − d est´ a a la vez en A y B, lo que es una contradicci´on. (3) La prueba es muy similar a la del apartado anterior. En este caso la funci´on ϕ no es adecuada, ya que A es infinito y los m´ınimos no tienen por qu´e estar definidos. As´ı pues, para n ∈ Z definimos ψ(n) como toda la clase de equivalencia de n; es decir: ψ(n) := {z ∈ N : n ∼ z} ⊂ Z. Consideramos el conjunto C = A \ (A + d). Por simetr´ıa con B, C posee exactamente k elementos. Tomemos ahora, por ejemplo, el conjunto S := {1, 2, . . . , d}. Puede reemplazarse por cualquier conjunto de d − 1 elementos, todos incongruentes entre s´ı e incongruentes con 0 m´ odulo d. Por simetr´ıa con el caso anterior, es f´acil ver que para cada i ∈ S, el conjunto Si = i + dZ = {. . . , i − 2d, i − d, i, i + d, . . .} se descompone en, a lo m´ as i(k) + 1 clases, donde i(k) P = |C ∩ Si |. Por tanto, Pd como Sd d A ⊂ i=1 Si , se tiene que A se descompone en, a lo m´as, i=1 [i(k) + 1] = i=1 i(k) + d = k + d clases. Definici´ on 3.5 Dados n´ umeros naturales a, d1 , . . . , dk , se define el k-cubo como el conjunto M (a, d1 , . . . , dk ) = {a + c1 d1 + c2 d2 + . . . + ck dk : cj ∈ {0, 1}, j = 1, 2, . . . , k} A M (a, d1 , . . . , dk ) tambi´en se le suele denotar por Mk . N´otese que Mj+1 := M (a, d1 , . . . , dj+1 ) = Mj ∪ (Mj + di ). A continuaci´ on estudiaremos condiciones suficientes para que A contenga un kcubo. Lema 3.6 Sean δ ∈ (0, 1) y k, N ∈ N tales que (3.4)
k
N > (4/δ)e .
Entonces, cualquier conjunto A ⊂ [N ] con al menos δN elementos contiene un k-cubo. 32
3.1. RESULTADOS PREVIOS
Demostraci´ on: Consideremos δ, k, N y A fijos, verificando las hip´otesis del enunciado. Sea el conjunto T := {(a, b) ⊂ A × A : a < b} ⊂ A × A. Por construcci´ on, T contiene al menos 1+2+. . .+(|A|−1) = |A|(|A|−1)/2 elementos. Por otro lado, la desigualdad 12 (|A| − 1) ≥ 14 (|A| − δ) equivale a 2|A| ≥ 2δ + 4, que es cierta para |A| > 2, lo cu´al no hace perder generalidad. Por tanto, T contiene al menos |A|(|A| − 1)/2 ≥ |A|(|A| − δ)/4 = δN (δN − δ)/4 = δ 2 N (N − 1)/4 elementos. Ahora particionamos T como NG −1 T = Uj , j=1
con Uj = {(a, b) ∈ T : b − a = j}, j ∈ [N − 1]. Por el principio del palomar, existe un d1 ∈ [N − 1] tal que |Ud1 | ≥ δ 2 N/4. Es decir, que d1 es diferencia com´ un de al 2 menos δ N/4 parejas de elementos, que componen Ud1 . Supongamos que tales parejas se escriben como (a1 , b1 ), (a2 , b2 ), . . . , (am , bm ), con m = |Ud1 |. Si ponemos A1 = {a1 , a2 , . . . , am } y δ1 = δ 2 /4, entonces A1 tiene al menos δ1 N elementos y A1 ∪ (A1 + d1 ) = {a1 , a2 , . . . , am } ∪ {b1 , b2 , . . . , bm } ⊂ A Sea ahora T1 := {(a, b) ⊂ A1 × A1 : a < b} ⊂ A1 × A1 . Por analog´ıa con T , T1 contiene al menos |A1 |(|A1 | − 1)/2 = δ12 N (N − 1)/4 elementos, siempre que |A1 | > 2. Si dividimos de nuevo los elementos de T1 en funci´on de la diferencia entre los dos elementos de cada par, debe existir una diferencia d2 com´ un a δ12 N/4 parejas. Si, igual que antes, creamos A2 con el primer elemento de cada una de esas parejas, entonces A2 tiene al menos δ2 N elementos (con δ2 := δ12 /4) y A2 ∪ (A2 + d2 ) ⊂ A1 ⊂ A. De forma an´ aloga a estos dos primeros casos, para cada j = 3, . . . , k, existir´ an una diferencia dj , un conjunto Aj y un δj = δj−1 /4 tales que Aj tiene al menos δj N elementos y Aj ∪ (Aj + dj ) ⊂ A. j
j−1
2 /4 = δ 4 /43 = . . . = δ 2 /42 Es f´ acil ver por inducci´ on que δj = δj−1 j−2 utilizando la cota (3.4), k
k
δ 2 4e |Ak | ≥ δk N ≥ 4 2k · ek = 4 4 δ 33
4
/δ
ek −2k
≥ 4.
. Entonces,
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
Por tanto, Ak tiene m´ as de dos elementos, as´ı como todos los anteriores. En particular, Ak es no vac´ıo. Basta tomar un s ∈ Ak y definir el k-cubo Mk = M (s; d1 , . . . , dk ), que por construcci´ on est´ a contenido en A. Observaci´ on: La condici´ on (3.4) puede escribirse de otra manera que nos ser´a u ´til k m´as adelante. Tomando logaritmos, la condici´on N > (4/δ)e equivale a log N ≥ k log(4/δ)e = ek log(4/δ) = ek+log log(4/δ) , que a su vez equivale a (3.5)
log log N ≥ k + log log(4/δ)
A continuaci´ on veremos el u ´ltimo resultado previo, que utilizaremos en el lema final de la siguiente secci´ on. Corolario 3.7 Sean δ ∈ (0, 1) y N un entero tal que 4
N > (16/δ 2 )e .
(3.6)
Entonces, cualquier A ⊂ [N ] con m´ as de δN elementos contiene un k-cubo, para alg´ un 1 k ≥ 1 + 2 log log N . Demostraci´ on: Utilizando el lema 3.6 y la condici´on equivalente (3.5), A contiene un k-cubo siempre que log log N ≥ k + log log(4/δ). El mayor k posible que verifica esto es k ≥ log log N − log log(4/δ) − 1. Por otro lado, la hip´otesis (3.6) equivale a 4 N ≥ ((4/δ)2 )e = exp(e4 (log(4/δ))2 ), que a su vez equivale a log N ≥ e4 (log(4/δ))2 . Tomando logaritmos una vez m´ as, (3.6) equivale a (3.7)
log log N ≥ 4 + 2 log log(4/δ).
Multiplicando esta ecuaci´ on por (−2), − log log(4/δ) − 1 ≥ 1/2 log log N . Por tanto, A contiene un k-cubo para k ≥ log log N − log log(4/δ) − 1 ≥ 1 + 1/2 log log N, con lo que queda probado el lema.
3.2.
Demostraci´ on combinatoria de Sz´ emeredi
Juntando todos las piezas de la secci´on anterior llegamos al siguiente lema, que es el coraz´on de la prueba de Sz´emeredi. A partir de ´el podremos construir el argumento iterativo clave para demostrar que todo conjunto A con δN elementos contiene una progresi´on aritm´etica de tres elementos. 34
´ COMBINATORIA DE SZEMEREDI ´ 3.2. DEMOSTRACION
Lema 3.8 Sean δ ∈ (0, 1) y N un entero tal que 4
N > (64/δ 2 )e .
(3.8)
Entonces, cualquier A ⊂ [4N 2 ] con m´ as de 4δN 2 elementos verifica que: O bien contiene 3 elementos en progresi´ on aritm´etica. O bien existe una progresi´ on P tal que |P | ≥ (δ 3 /40) log log N y adem´ as d(A|P ) ≥ 2 δ + δ /16 Demostraci´ on: En primer lugar dividimos [4N 2 ] en cuatro subconjuntos de igual longitud, B0 , B1 , B2 y B3 , con Bi = {iN 2 +1, iN 2 +2, . . . , (iN 2 +N }, con i = 0, 1, 2, 3. Asimismo, definimos Ai = A∩Bi para cada i. Podemos suponer que los cuatro conjuntos verifican Ai ≥ δN 2 /2. En caso contrario, al no verificar la desigualdad uno de ellos, los otros tres han de contener juntos m´as de 4δN 2 −δN 2 /2 = (7δ/2)N 2 elementos. Por tanto, alguno de ellos, pongamos As , tendr´a m´as de (7δ/6)N 2 = (δ + δ/6)N 2 elementos. Y entonces el lema estar´ıa trivialmente probado al satisfacerse la segunda opci´ on 3 2 con P = Bs , ya que |Bs | = N/4 ≥ δ /40 log log N y d(A|Bs ) ≥ δ + δ/6 > δ + δ /16. Por tanto, asumimos en lo sucesivo que Bi ≥ δN 2 /2 para i = 0, 1, 2, 3. Dividimos B1 en N intervalos iguales, de N elementos cada uno. Como d(A|Bi ) ≥ δ/2, uno de los N intervalos, al que llamaremos C, verifica d(A|C) ≥ δ/2, por la observaci´on posterior al lema 3.1. 4
4
Como N > (64/δ 2 )e > (16/δ 2 )e , podemos aplicar el corolario 3.7, y el conjunto A ∩ C contendr´ a un k-cubo, para un cierto k ≥ 1 + 1/2 log log N . A este k-cubo lo denotaremos por Mk = M (a; d1 , d2 , . . . , dk ), donde a, d1 , d2 , . . . , dk son unos de los posibles datos que convierten a Mk en k-cubo. A su vez, para j = 1, 2, . . . , k − 1, denotamos por Mj al conjunto M (a; d1 , d2 , . . . , dj ). A continuaci´ on creamos una sucesi´on finita no decreciente de conjuntos, de la siguiente forma: Para cada j ∈ [k], Qj = {2b − c : b ∈ Mj , c ∈ A0 } = 2Mj − A0 ⊂ [4N 2 ]. La contenci´ on se tiene ya que 2Mj ⊂ 2C ⊂ [2N 2 , 4N 2 − 2] y A0 ⊂ [1, N 2 ], y por tanto Qj ⊂ [N 2 , 4N 2 − 3] ⊂ [4N 2 ]. Por construcci´on, Qj ⊂ Qj+1 para cada j ∈ [k − 1], ya que Mj ⊂ Mj+1 . Es evidente entonces que los conjuntos Qj+1 \ Qj , con j ∈ [k − 1], son disjuntos. Como todos est´an contenidos en el intervalo [4N 2 ], 35
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
el n´ umero de elementos que contenga alguno de ellos ser´a no superior a la media de todos. Es decir, existe un j ∈ [k − 1] tal que |Qj+1 \ Qj| ≤
(3.9)
4N 2 4N 2 8N 2 ≤ = . k−1 1/2 log log N log log N
Sean D = [4N 2 ] \ Qj y d = 2dj+1 . Podemos proceder como en la proposici´on 3.4 y crear una uni´ on disjunta de D = D1 ∪ . . . ∪ Dm , con m ≤ |(Qj + d) \ Qj | = |Qj+1 \ Qj |, donde cada Dl es una progresi´ on aritm´etica de la misma raz´on d. Ya estamos en condiciones de aplicar la proposici´on 3.2. Por construcci´on de Qj , A ∩ Qj = ∅ (si esto no fuera as´ı, existir´ıa un a ∈ Qj que podr´ıa escribirse como a = 2b − c, con a ∈ A, b ∈ Mj ⊂ A y c ∈ A0 ⊂ A, y A contendr´ıa una progresi´on aritm´etica formada por a, b y c, no todos iguales por construcci´on de Qj ), de donde A ⊂ D. Tambi´en por construcci´ on de Qj , se puede comrpobar f´acilmente que |Qj | ≥ |A0 | ≥ δ 2 N/2, de donde |D| ≤ 4N 2 − |A0 | = (1 − δ/8)4N 2 . Utilizando la proposici´on 3.2, existe un ´ındice l ∈ [m] tal que d(A|Dl ) ≥ δ + δ 2 /16 y adem´as |Dl | ≥
δ 3 4N 2 δ3 4N 2 · ≥ · 16 m 16 |Qj+1 \ Qj| + d
Usando (3.9) y que d = 2dj+1 ≤ 2N : ≥
δ3 4N 2 δ3 4N 2 · ≥ · = 16 8N 2 / log log N + 2N 16 8N 2 / log log N + 2N 2 / log log N δ3 4 δ 3 log log N · = . 16 10/ log log N 40
El lema est´ a completo simplemente llamando P a Dl .
Utilizando este lema podemos demostrar finalmente el teorema de Roth. Llamemos E1 a la progresi´ on Dl sobre la que A tiene densidad relativa δ1 ≥ δ + δ 2 /16. Sea A1 = A ∩ E1 . Como A1 no contiene progresiones aritm´eticas, volvemos a aplicar toda la maquinaria sobre ´el, obteniendo en el peor de los casos una progresi´on E2 sobre la que A1 tiene densidad relativa δ2 ≥ δ1 + δ12 /16 ≥ δ + 2δ 2 /16. Realizando este paso repetidas veces, pongamos j veces, la densidad relativa δj ser´a mayor que δ + jδ 2 /16. Y por tanto, tras j = 16/δ iteraciones, la densidad relativa ser´a al menos el doble de la original. Por analog´ıa con la demostraci´on del cap´ıtulo anterior obtenemos que, tras realizar k = 32/δ iteraciones, la densidad relativa de Ak−1 en Ek es mayor que 3/4, y por lo tanto el conjunto correspondiente Ak contiene una progresi´on aritm´etica de tres elementos, luego A tambi´en la contiene.
36
´ COMBINATORIA DE SZEMEREDI ´ 3.2. DEMOSTRACION
Al igual que en la demostraci´on de Roth, es necesario asegurarnos de que, tras k iteraciones, |Ek | ≥ 1 para que el resultado sea aplicable. Se tiene, cambiando N por p 0 N = N/2 que δ 3 log log N 0 |E1 | ≥ 40 |E2 | ≥
δ13 log log |E1 | δ 3 log log[(δ 3 /40) log log N 0 ] ≥ 40 40 ...
|Ek | ≥ (δ 3 /40) log log[(δ 3 /40) log log[. . . [(δ 3 /40) log log N 0 ]]] Luego la condici´ on que debe cumplirse es 1 ≤ (δ 3 /40) log log[(δ 3 /40) log log[. . . [(δ 3 /40) log log N 0 ]]]
(3.10)
Tomando exponenciales, vemos que la condici´on 1 ≤ (δ 3 /40) log log N 0 equivale a N ≥ e(e
40/δ 3 )
. An´ alogamente, es f´acil ver que 1 ≤ (δ 3 /40) log log[(δ 3 /40) log log N 0 ]
equivale a
3
N 0 ≥ exp[exp[(40δ 3 exp(e40/δ ))]]. Y por tanto, la expresi´ on gen´erica (3.10) es an´aloga a p 3 (3.11) N 0 = N/2 ≥ exp[exp[40/δ 3 exp[exp[40/δ 3 exp[. . . (exp(e40/δ ))]]]]]. Como adelant´ abamos al principio, se trata de una cota muy pobre que no mejora la dada por Roth. Sin embargo, esta demostraci´on de Sz´emeredi fue el primer paso para la demostraci´ on gen´erica (para todo k ≥ 3) del teorema que hoy lleva su nombre.
37
´ COMBINATORIA DE SZEMEREDI ´ TEMA 3. DEMOSTRACION
38
Tema 4
Ejemplo de Behrend En contraposici´ on al teorema de Roth, Behrend consigui´o construir un subconjunto de N de gran tama˜ no que no contiene progresiones aritm´eticas de tres elementos. Adem´ as su construcci´ on es sencilla, al existir una aplicaci´on biyectiva entre los puntos del conjunto y los de una esfera, en la que es inmediato ver que no puede haber tres elementos alineados.
4.1.
Ejemplo de Behrend
Teorema 4.1 (Behrend) Sea N un n´ umero natural suficientemente grande. Enton√ ces, existe un conjunto A ⊂ [N ], con al menos N exp(−c log N ) elementos (donde c es una constante real positiva) que no contiene ninguna progresi´ on aritm´etica no trivial de tres elementos. Demostraci´ on: La demostraci´on se basa en un sencillo hecho geom´etrico: Una esfera (en n dimensiones) y una recta siempre se cortan en como m´aximo dos puntos. Formalmente, podemos enunciarlo as´ı: Lema 4.2 Sean n, r ∈ N cualesquiera. Entonces, el conjunto T = {x ∈ Zn : |x| = r} no contiene tres elementos en progresi´ on aritm´etica (no trivial). La demostraci´ on del lema es pr´acticamente evidente a la vista de lo expuesto en el p´ arrafo anterior. Sea E(r) = {x ∈ Rn : |x| = r} ⊂ Rn . 39
TEMA 4. EJEMPLO DE BEHREND
Por construcci´ on, E(r) es la superficie de la bola de centro 0 y radio r contenida en Rn . Entonces, como T ∈ E(r) ⊂ Rn , si tomamos cualquier recta t contenida en Rn , se verifica por geometr´ıa que |E(r) ∩ t| ≤ 2. Y entonces T no puede contener tres elementos en progresi´ on aritm´etica (es decir, x, y, z ∈ T distintos tales que x + y = 2z), ya que si as´ı ocurriera, como z − x = y − z, se deducir´ıa que existe una recta que pasa por los tres puntos, contenidos estos a su vez en una esfera, lo cu´al es una contradicci´on. Por tanto T no contiene progresiones aritm´eticas de tres elementos. Procedamos ahora a demostrar el teorema. En primer lugar, cuando se dice que N debe ser suficientemente grande no significa que haya ninguna restricci´on concreta sobre el valor m´ınimo que puede tomar N , salvo que ´este tenga un √ valor lo suficientemente grande como para que cantidades del orden de N exp(−c log N ) no sean insignificantes y el supuesto conjunto A tengan un n´ umero aceptable de elementos. Sean n y M n´ umeros naturales menores que N y dependientes de ´este. M´as adelante fijaremos sus valores. Para todo r natural, consideramos el conjunto siguiente: S(r) = {x ∈ [M ]n :
n X
x2j = r}.
j=1
Se verifica de manera trivial que S(r) es vac´ıo si r 6∈ [n, nM 2 ]; de hecho, S(n) y S(nM 2 ) tendr´an cada uno un s´ olo punto ((1, 1, . . . , 1) y (M, M, . . . , M ), respectivamente). Por tanto: n
[M ] ⊂
2 nM [
S(r),
r=n
P ya que n ≤ nj=1 x2j ≤ nM 2 . As´ı pues, tenemos n(M 2 − 1) conjuntos que recubren a uno de cardinal M n . Usando el principio del palomar, alguno de esos conjuntos tendr´a√entonces tantos elementos como la media de todos ellos. Es decir, existe un radio r∗ tal que S(r∗ ) contiene al menos Mn M n−2 > n(M 2 − 1) n elementos. Obviamente, S(r∗ ) no contiene progresiones aritm´eticas, por ser un subconjunto del T que dimos en el lema 4.2. Por tanto, si logramos inyectarlo de manera adecuada en [N ], habremos conseguido un subconjunto de [N ] sin progresiones aritm´eticas. Consideramos la aplicaci´ on P : S(r∗ ) −→ [N ], definida como: x 7→ P (x) := x1 + (2M )x2 + (2M )2 x3 + . . . (2M )n−1 xn , 40
4.1. EJEMPLO DE BEHREND
para x = (x1 , x2 , . . . xn ) ∈ S(r∗ ). La aplicaci´on estar´a bien definida siempre y cuando P (x) ≤ N, ∀x ∈ S(r∗ ). Esto puede conseguirse ajustando M en funci´on de N , algo que haremos m´ as adelante. En primer lugar, vamos a demostrar que P es inyectiva. En efecto, si consideramos x ∈ S(r∗ ) y j ∈ [n], entonces 0 < xj ≤ M < 2M , pues S(r∗ ) ⊂ [M ]n . Por tanto, si P (x) = P (y), se tiene que x1 + (2M )x2 + . . . + (2M )n−1 xn = y1 + (2M )y2 + . . . + (2N )n−1 yn , de donde xj = yj para cada j ∈ [n] de manera trivial por los posibles valores de los coeficientes x1 , x2 , . . . , xn , y1 , y2 , . . . , yn y la unicidad en la expresi´on de un n´ umero en base 2M . Del mismo modo se puede ver que, dados x, y, z ∈ S(r∗ ), se tiene que x+y = 2z si y s´ olo si P (x)+P (y) = 2P (z). Una implicaci´on es evidente. para ver la otra supongamos que P (x) + P (y) = 2P (z). Entonces. (x1 + y1 ) + (2M )(x2 + y2 ) + . . . + (2M )n−1 (xn + yn ) = = 2z1 + (2M )2z2 + . . . + (2M )n−1 . La demostraci´ on se hace de forma id´entica a la de la prueba de la inyectividad salvo en el supuesto de que existan xj = yj = M , o bien zj = M . En tales casos, mediante un peque˜ no truco, puede probarse que tambi´en se tiene la propiedad. Si j es la coordenada m´ as peque˜ na en la que xj = yj = M , entonces (xj +yj )(2M )j−1 +(xj+1 +yj+1 )(2M )j = (1 + xj+1 + yj+1 )(2M )j = 2zj (2M )j−1 + 2zj+1 (2M )j , de donde se deduce que zj tiene que ser M , y deducimos que xj+1 + yj+1 = 2zj+1 . Por tanto, esto no modifica el argumento y se tiene la propiedad. Por u ´ltimo, probaremos que, para cualquier x ∈ S(r∗ ) se tiene P (x) ≤ (2M )n . Como el valor m´ aximo se alcanza para x = (M, M, . . . , M ), deducimos que P (x) ≤ M (1 + 2M + (2M )2 + . . . + (2M )n−1 ) (2M )n − 1 = M < (2M )n . 2M − 1 √ Utilizando esta u ´ltima propiedad, basta fijar M como b n N /2c para que la aplicaci´ on P est´e bien definida. En concreto, debido a ello se tendr´a que A := P (S(r∗ )) ⊂ [N ], y adem´ as A no contendr´a progresiones aritm´eticas de 3 elementos, por no conte√ nerlas S(r∗ ) y por la inyectividad de P . Si fijamos ahora n como log N , vemos que el cardinal de A es: 41
TEMA 4. EJEMPLO DE BEHREND
|A| = ≥ = = = = =
% $ n−2 1/n 1 M N 1 N 1/n 1 |S(r∗ )| > = ≥ n 2 n 4 2 n " !# N 1−2/n N 1−2/n = exp log n2n n2n 2 exp log N − log N − log n − n log 2 n 2 N exp − log N − log n − n log 2 n p p 2 N exp − √ log N − log( log N ) − log N log 2 log N p p N exp −2 log 2 log N − log log N p p N exp − log 4 log N + O(log log N ) .
Y con esto queda probado el teorema. Vemos que, como adelant´abamos al principio, sobre N no hay ninguna restricci´on concreta sobre los valores que puede tomar. Simplemente debe √ ser lo suficientemente grande como para que las cantidades del orden de N exp(−c log N ) no tengan un valor despreciable.
42
Bibliograf´ıa [1] Baker, Roger C.; Harman, Glyn and Pintz, J´anos; The difference between consecutive primes, II, Proceedings of the London Mathematical Society 83, (2001), 532562. [2] Bourgain, Jean; On triples in arithmetic progression, eom. Funct. Anal., 9(5), (1999), 968984 [3] Bourgain, Jean; Roth’s theorem on progressions revisited, J. Anal. Math., 104, (2008), 155206. [4] Croot, Ernest and Sisack, Olof; A probabilistic technique for finding almost-periods of convolutions http://people.math.gatech.edu/~ecroot/prob-almost-periods.pdf [5] Gowers, Timothy; Additive and combinatorial number theory (2007) http://www.dpmms.cam.ac.uk/~wtg10/addnoth.notes.ps
[6] Granville, Andrew; An introduction to aditive combinatorics http://www.dms.umontreal.ca/~andrew/PDF/ProcAddPap.pdf
[7] Heath-Brown, David R.; Integer sets containing no arithmetic progressions, London Math. Soc.(2), (1987) 35(3):385394. [8] Lyall, Neil; Behrend’s example http://www.math.uga.edu/~lyall/REU/Behrend.pdf
[9] Magyar, Akos; Roth’s theorem. The combinatorial approach http://www.math.uga.edu/~magyar/courses/M8440/roth_comb3.pdf
[10] Rahman, Mustazee; Roth’s theorem on 3-term arithmetic progressions http://wiki.math.toronto.edu/TorontoMathWiki/images/2/2d/Expo_paper.pdf
[11] Roth, Klaus F.; On certain sets of integers, J. London Math. Soc., (1953), 28:104109. 43
BIBLIOGRAF´IA
[12] Sanders, Tom; On certain other sets of integers (2010) http://arxiv4.library.cornell.edu/abs/1007.5444
[13] Shelah, Saharon; Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1:3, (1988), 683697. [14] Shkerdov, Il’ya Dmitrievich; Szemer´edi’s theorem and problems on arithmetic progressions, Russ. Math. Surv. 61, (2006), 1101. [15] Sz´emeredi, Endre; Integer sets containing no arithmetic progressions, Acta Math. Hungar., 56(1-2), (1990), :155158. [16] Sz´emeredi, Endre; On sets of integers containing no four elements in arithmetic progression, Acta Math. Hungar., 20:12 (1969), 89104. [17] Sz´emeredi, Endre; On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199245. [18] Waerden, Bartel Leendert van der; Beweis einer baudetschen vermutung, Nieuw Arch. Wisk. 15, (1927), 212216.
44