Download ahora

Del Caballero de Mére al Teorema de Green-Tao:
un paseo (aleatorio)
por el mundo de la probabilidad
y por la teoría de Ramsey
Juanjo Rué
École Polytechnique, Palaiseau (L’X)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 1
Dónde encontramos la probabilidad?
En la economía
Valor de la acción de Criteria, y análisis técnico.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 2
Dónde encontramos la probabilidad?
En la naturaleza
Filtración en un medio poroso
(Percolación)
Movimiento de una
particula en
suspensión.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 3
Dónde encontramos la probabilidad?
En la sociedad
Modelo de una red de abastecimiento
Modelo de una red
social (Comunidades)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 4
Juegos de azar:
aquí empieza todo
Introduccion a la probabilidad y la teoria de Ramsey.– p. 5
Un poco de historia
• Los primeros en preguntarse sobre cuestiones de juegos de azar
fueron los renacentistas: Piacoli, Cardano, Galilei, . . . .
• Primer problema real: encuentro de Pascal con el Chevalier de
Mére en 1651, que originó una abundante correspondencia entre
Pascal y Pierre de Fermat.
“...el caballero de Mére tiene mucho talento, pero no es
geómetra; ésto es, como sabéis un gran defecto...”
Introduccion a la probabilidad y la teoria de Ramsey.– p. 6
Ahora tocaría explicar los problemas típicos: la ruina del jugador,
la aguja de Buffon, . . . , pero NO lo haremos.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 7
Un inciso: demasiado poco espacio!
“...Es imposible encontrar la forma de convertir un cubo en la
suma de dos cubos, una potencia cuarta en la suma de dos
potencias cuartas, o en general cualquier potencia más alta que
el cuadrado en la suma de dos potencias de la misma clase; para
este hecho he encontrado una demostración excelente. El
margen es demasiado pequeño para que la demostración quepa
en él...”
⇓
Este problema es el conocido último teorema de Fermat, que afirma
que si n > 2 la ecuación xn + y n = z n únicamente tiene soluciones
triviales.
La cuestión es que este problema se consiguió resolver el año 1996
con técnicas que en el siglo XV II no se habìan desarrollado todavía.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 8
Un truco matemágico
“...En un instituto dividimos los alumnos en dos grupos. En uno
de ellos, a cada alumno se le da una moneda que tira 200 veces,
escribiendo la secuencia que obtiene. En el otro grupo, los
alumnos no reciben una moneda, y se pide que traten de escribir
una secuencia aleatoria de caras y cruces de longitud 200.
Después el matemago recolecta los papeles y trata de
clasificarlos según el método de generación. La mayoría de veces
la clasificación es bastante buena · · ·
En este caso, y que no sirva de precedente, el mago desvelará el
secreto.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 9
Un truco matemágico (y 2)
El matemago debe de mirar la carrera más larga
L
3
4
5
6
7
8
9
10
11
12
p
6,54 · 10−8
7 · 10−4
0,0339
0.1660
0,2574
0,2235
0,1459
0,0829
0,0440
0,0226
La mayoría de gente normalmente
escribe carreras de longitud menor
que 4, porque sienten que de otra
manera obtenemos algo no
aleatorio. El matemago
simplemente usa este criterio!
(Combinatoria analítica y análisis de algoritmos)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 10
Lost en Barcelona
Supongamos que estamos paseando por el Eixample de Barcelona y
que nos perdemos.
Existe algún método para llegar a nuestro destino?
Introduccion a la probabilidad y la teoria de Ramsey.– p. 11
Lost en Barcelona (y 2)
En esta situación basta que realicemos un paseo aleatorio por el
Eixample, y con probabilidad 1 acabaremos llegando a nuestro
destino!
Problema: igual dedicaremos demasiado tiempo a volver a casa . . . .
Estos paseos siempre retornan al origen cuando estamos en el caso
unidimensional y en el caso bidimensional...pero el caso
tridimensional ya no!
(Dimensión crítica y paseos aleatorios en grafos infinitos)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 12
Una paradoja de aniversarios...
En una habitación van entrando personas, y se va apuntando su fecha
de aniversario.
Cuál es el número esperado de personas que entren antes que
hayan dos con el mismo aniversario?
⇓
La cuestión es que con n ∼ 24 personas hay muchos aparejamientos
de personas. Si estamos en un planeta marciano con r días por año,
Z
0
∞
r
r
πr 2
t
+ + error pequeño
dr ∼
e−t 1 +
r
2
3
Introduccion a la probabilidad y la teoria de Ramsey.– p. 13
...y otra de cromos
En una colección de 365 cromos, cuantos sobres de 1 cromo hay
que comprar en media?
⇓
Aquí el problema es el inverso, uno tiene que esperar un valor mucho
mayor que el número total de cromos (para agotar todas las
posibilidades.) Hacen falta en media 2364.
Z
∞
0
−t/r r
1 − (1 − e
)
1
dr ∼ r log(r) + γr + + error pequeño
2
Conclusión: es un buen negocio dedicarse a vender cromos.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 14
Barajando cartas
Supongamos que tenemos una baraja de cartas ordenada: cuántos
shufflings necesitamos realizar para esperar que el orden en la baraja
sea completamente aleatorio? (i.e., podemos obtener con igual
probabilidad cualquier orden de las cartas)
⇓
Persi Diaconis (Standford) y Dave Bayer (Columbia) demostraron el
año 1992 que con 7 shufflings hay suficiente.
Después de este resultado, en los casinos de Las Vegas tomaron el
teorema como regla de funcionamiento.
(Paseos aleatorios en grafos finitos y cadenas de Markov)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 15
Orden en el desorden:
La teoría de Ramsey
Introduccion a la probabilidad y la teoria de Ramsey.– p. 16
Por donde empezamos? Contando palomas...
Principio del palomar de Dirichlet: N + 1 palomas que llegan a un
palomar con N agujeros: dos de ellas deben de compartir
necesariamente un agujero!
Por ejemplo, en un grupo de 366 personas siempre existen dos que
cumplen años el mismo día!
Filosofía: encontramos una pauta en una configuración cualquiera de
palomas.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 17
Matemáticas y eventos sociales para abrir boca
Problema: demostrar que en una
fiesta de más de 6 personas siempre
existen 3 de ellas que se conocen
mutuamente o bien 3 de ellas que no
se conocen las unas con las otras.
Se supone que la relación de amistad es simétrica.
Observar lo que nos dice el problema: en un conjunto cualquiera
(aleatorio) de 6 personas, SIEMPRE existe una subestructura
subjacente.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 18
Modelando el problema: grafos
• A cada persona le asociamos un punto, al que llamaremos
vértice.
• Si dos personas se conocen, pintamos una linea (arista) entre los
vértices.
• Si dos personas no se conocen, pintamos una linea (arista)
punteada entre los vértices.
Traducción: si coloreamos
con 2 colores el grafo K6 ,
siempre existe un triángulo
monocromático.
Cogemos un vértice y aplicamos el principio del palomar . . .
Introduccion a la probabilidad y la teoria de Ramsey.– p. 19
Algo más difı́cil, por favor
Fijamos un entero k. Existe un número N tal que toda fiesta con más
de N personas contiene un grupo de k personas que se conocen
mútuamente o bien un grupo de k personas que no se conocen las
unas con las otras?
Traducción: existe un N
tal que si coloreamos el
grafo KN con dos colores,
siempre obtenemos un Kk
monocromático?.
La respuesta es que SI. Es el resultado que bautiza la teoría de
Ramsey.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 20
...y como se demuestra? El método probabilı́stico.
Se trata de una idea seminal de Paul
Erdös, consistente en definir un espacio
de probabilidad adecuado, y demostrar
que cierto objeto con la propiedad
deseada tiene probabilidad positiva. Esta
idea se conoce como el método
probabilístico.
De hecho, se demuestra las siguientes cotas para los números de
Ramsey R(k, k)
2k/2 < R(k, k) < 2k
2
/2
Por ejemplo, 8 < 23 < R(6, 6) < 218 = 262144
Así pues, coloreando aleatoriamente el grafo KN , siempre existe una
subestructura subjacente.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 21
Rizando el rizo: número cromático y cuello
• El número cromático de un grafo χ(G) es el número mínimo de
colores necesarios para pintar los vértices, sin que hayan dos
vertices incidentes del mismo color.
• El cuello de un grafo g(G) es la longitud del ciclo más corto.
Muchas aristas: número cromático alto, cuello bajo.
Pocas aristas: número cromático bajo, cuello alto.
Hay grafos con χ(G) y g(G) arbitrariamente grande?
Erdös (1959) demuestra que existen, pero construirlos es un
problema muy difícil!
Introduccion a la probabilidad y la teoria de Ramsey.– p. 22
Teoremas tipo Ramsey sobre los naturales
Teorema de Van der Waerden infinito: consideremos una coloración
(aleatoria) de los números enteros con r colores. Entonces existe un
color que contiene progresiones aritméticas arbitrariamente largas.
Inciso: una progresión aritmética de longitud k es un conjunto de
números de la forma
a, a + b, a + 2b, . . . , a + (k − 1)b
Por exemplo 3, 5, 7, 9 es una progresión aritmética de longitud 4.
Es decir, si particionamos el conjunto de los naturales en clases
C1 , C2 , . . . , Cr , uno de los conjuntos Ci (no sabemos cual) tiene una
subestructura subyacente.
Se puede decir algo más general?
Introduccion a la probabilidad y la teoria de Ramsey.– p. 23
El teorema de Szemerédi
Dado un conjunto infinito ∆ de enteros positivos, definimos
T
|∆ {1, 2, . . . , n}|
d(n) =
n
De todos los d(n), tomamos el más pequeño, y decimos que éste es la
densidad de ∆.
Teorema de Szemerédi: si la densidad de ∆ es estrictamente mayor
que 0, entonces contiene progresiones aritméticas arbitrariamente
largas (sea como sea ∆).
Introduccion a la probabilidad y la teoria de Ramsey.– p. 24
La prueba
Se conocen esencialmente tres pruebas de este resultado, con
demostraciones cualitativamente distintas
André Szemerédi
(Combinatoria)
Hillel Furstenberg
(Teoría ergódica)
Tim Gowers
(Análisis
funcional)
...Y se puede ir más allá?
Introduccion a la probabilidad y la teoria de Ramsey.– p. 25
Números primos:
el teorema de Green-Tao
Introduccion a la probabilidad y la teoria de Ramsey.– p. 26
Qué es un número primo y alguna que otra definición
Un entero positivo es primo si sus divisores son el 1 y él mismo.
12 = 3 × 4, luego no es primo; 1 no es primo! (ni compuesto)
Los primeros primos son los siguientes
2, 3, 5, 7, 11, 13, 17, 19, . . .
Teorema: Existen infinitos números primos (Euclides).
Si hubiera un conjunto finito, {p1 , p2 , . . . , pN }, entonces el número
p1 p2 . . . pN + 1 tendrá que ser primo y no estaría en la lista!
a, b son primos entre si si no tienen ningun divisor común primo.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 27
Intermezzo: sumas de inversos de enteros
Sea ∆ un conjunto de números enteros positivos, sin incluir el 0.
Si el conjunto ∆ es finito ⇒ la suma
P
Si el conjunto ∆ es infinito ⇒ la suma
infinita.
a∈∆
a−1 es finita!
P
−1
a
puede ser finita o
a∈∆
1. Tomamos el conjunto ∆ = {1, 2, 4, 8, . . . }. Entonces:
1
1 1
S = 1 + + + ··· = 1+ S ⇒ S = 2
2 4
2
2. ∆ = {1, 2, 3, 4 . . . }. Entonces:
1 1
1 1 1 1
1
1
1
1
1+ +( + )+( + + + )+. . . > 1+ +2 +4 +· · · = ∞
2
3 4
5 6 7 8
2
4
8
Introduccion a la probabilidad y la teoria de Ramsey.– p. 28
Resultados más refinados de números primos
1. La suma de los inversos de los primos diverge:
P
−1
p
=∞
p primo
2. Postulado de Bertrand: entre un número y su doble siempre
existe un primo.
3. Teorema de Dirichlet: sean a, b primos entre si. En la progresion
aritmética a, a + b, a + 2b, a + 3b, . . . existen infinitos primos.
La idea "básica" de la prueba es intentar demostrar que
X
p−1 = ∞
p=a+br primo
Se introduce el concepto de función L.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 29
El teorema del número primo; densidad 0!
Uno de los problemas con más historia de la aritmética.
Sea π(n) el número de primos menores que n (π(10) = 4: {2, 3, 5, 7}).
lı́m
n→∞
π(n)
n
log(n)
=1
De otro modo, para
n muy grande, π(n) y
n
log(n) valen ”casi” lo
mismo.
La densidad de primos es igual a:
π(n)
n
∼
n
log(n)
n
∼
1
log(n)
−→ 0
El teorema de Szemerédi no funciona en los primos!
Introduccion a la probabilidad y la teoria de Ramsey.– p. 30
...hasta la llegada de los maestros...
Ben Green (Cambridge)
Terence Tao (UCLA)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 31
El teorema de Green-Tao
En el conjunto de los números primos existen progresiones
aritméticas arbitrariamente largas.
Idea de la prueba: estudiar propiedades generales de conjuntos
pseudoaleatorios, y demostrar después que dichas propiedades se
cumplen para el conjunto de los números primos.
m
En cierto modo, el conjunto de los números primos es un conjunto
escogido al azar!
Técnicamente, se trata de una combinación del trabajo de Szemerédi,
Furstenberg y Gowers.
Se trata de uno de los resultados más impresionantes de los últimos
30 años.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 32
De otra liga
Por ello (junto con otras cosas) Terence Tao recibió la medalla Fields
el 2006 en Madrid, y Ben Green está en todas la quinielas para la
medalla Fields de este año.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 33
De otra liga
Por ello (junto con otras cosas) Terence Tao recibió la medalla Fields
el 2006 en Madrid, y Ben Green está en todas la quinielas para la
medalla Fields de este año.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 34
De otra liga
Introduccion a la probabilidad y la teoria de Ramsey.– p. 35
Problemas abiertos
Introduccion a la probabilidad y la teoria de Ramsey.– p. 36
Algunos problemas sobre los que pensar...a ratos
• Hallar números de Ramsey.
Suppose aliens invade the Earth and threaten to
obliterate it in a year’s time unless human beings can
find the Ramsey number R(5, 5). We could marshal the
world’s best minds and fastest computers, and within
a year we could probably calculate the value. If the
aliens demanded the Ramsey number R(6, 6),
however, we would have no choice but to launch a
preemptive attack.
Paul Erdös.
• Hipótesis de Riemann: Los zeros complejos no triviales de la
P∞
función ζ(s) = n=1 n−s se hallan en la banda crítica.
Hay maneras más sencillas de ganar 106 dolares.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 37
Algunos problemas sobre los que pensar...a ratos (y 2)
• La conjetura de Erdös-Turán: sea ∆ = {a1 , a2 , . . . } un conjunto
P∞ 1
infinito de enteros positivos. Si i=1 ai = ∞, entonces el
conjunto ∆ contiene progresiones aritméticas arbitrariamente
largas!
• La conjetura de Goldbach: Todo entero positivo es suma de dos
primos?
• Primos gemelos: existen infinitos primos gemelos? (p y p + 2 son
primos)
• La conjetura de Erdös-Turán para funciones de
representación: sea ∆ un conjunto infinito de enteros, si todo
entero n se escribe como x + y, x, y ∈ ∆, entonces las maneras
de escribir n como suma de dos elementos de ∆ es no acotado.
Introduccion a la probabilidad y la teoria de Ramsey.– p. 38
Estas cuestiones son de gran importancia...
Introduccion a la probabilidad y la teoria de Ramsey.– p. 39
...pero existen otras mucho más dificiles
Gracias por venir!
Introduccion a la probabilidad y la teoria de Ramsey.– p. 40
Del Caballero de Mére al Teorema de Green-Tao:
un paseo (aleatorio)
por el mundo de la probabilidad
y por la teoría de Ramsey
Juanjo Rué
École Polytechnique, Palaiseau (L’X)
Introduccion a la probabilidad y la teoria de Ramsey.– p. 41