Demostrada la conjetura de la discrepancia de Erdös.

Millonet1

En 1932 el genial matemático Húngaro Paul Erdös conjeturó que para una secuencia ±1 infinita y cualquier entero C, existen dos enteros, d y k tal que:

La conjetura afirma que para una secuencia aleatoria de 1s y -1s y una constante C arbitraria, siempre existe una subsecuencia finita de forma que la suma de sus elementos es mayor que C cualquiera que sea su valor.

En 2014 se publicó una prueba mediante computadora que demostraba el caso C=2, pero no fueron capaces de demostrarlo para C>2.


Erdös con Tao.

Bien, pues más de 80 años después, Terry Tao ha demostrado hace escasos días que la conjetura de Erdös es verdadera, añadiendo un hito más a su espectacular carrera.

https://en.wikipedia.org/wiki/±1-sequence
Una buena explicación:
https://rjlipton.wordpress.com/2015/09/24/frogs-and-lily-pads-and-discrepancy/
http://www.nature.com/news/maths-whizz-solves-a-master-s-riddle-1.18441
Paper original:
https://terrytao.wordpress.com/2015/09/18/the-logarithmically-averaged-chowla-and-elliott-conjectures-for-two-point-correlations-the-erdos-discrepancy-problem/
http://arxiv.org/abs/1509.05363

3
T-1000

explicación para lelos en el tema.

2 respuestas
Millonet1

#2 dice que si coges una secuencia aleatoria infinita formada solo por 1 y -1: (1,1,-1,1,-1,-1,-1,-1,1...) y un número C, siempre podrás encontrar una parte finita de la secuencia de forma que la suma de todos sus elementos sea mayor que C por muy grande que sea esta C.

1
Aibehn

Entiendo que se basa en que básicamente una secuencia aleatoria de 1 y -1, al ser infinita, por muy aleatoria que sea, probabilisticamente ( aunque sea poco problable, en una secuencia infinita se convierne en un caso seguro ) se da el caso de que se encuentre una secuencia del estilo 1,1,1,1,1,1... como de grande se quiera, y por lo tanto que la suma de la secuencia se pueda hacer como de grande se quiera.

2 1 respuesta
Millonet1

#4 Si, yo creo que la idea intuitiva es esa.

Estoy leyendo la demostración y no me entero de casi nada, a ver si Duronmann nos explica por encima que camino sigue Tao.
Por cierto, veo que la idea se le ocurrió gracias a un comentario en su blog xD

E

Me sumo a la petición de #2 , no he entendido nada de la demostración :psyduck:

RubenLionel

Creo que lo he entendido, pero mejor que venga duronman y lo explique mejor.

Eso si, llevo un cacao mental curioso xD

Millonet1

No os preocupéis, entender a Terry Tao es el sueño de todo estudiante de matemáticas xD

Zero_G

Yo entiendo que haciendo una suma infinita de +1 y -1 de forma aleatoria, quitándole el signo, osea, cogiendo el valor absoluto, el numero siempre sera mayor a C siendo C un numero cualquiera.

Esa creo que es la explicación, el porque me deja :psyduck:

Rivendel

Intuitivamente es evidente el caso es demostrarlo simbolicamente digamos xD

B

Bueno, se resolvio vía polymath, evidentemente Tao hizo gran parte pero fue todo un grupo de matemáticos los que trabajaron en ello juntos. Polymath es un proyecto muy chulo.

Veamos, este tipo de conjeturas (como la quizás más famosa conjetura de Collatz) tienen la gracia de ser muy fáciles de escribir y muy muy difíciles de demostrar. En este caso la conjetura dice que para cualquier f(n) con valores en {-1,1}, para cualquier C existen d, k tales que el sumatorio desde i = 1 hasta i = k de f(id) es, en valor absoluto, mayor que C.

Básicamente si la f toma los valores 1,1,1,1,-1,1,-1,-1,-1,1,-1,-1,-1,-1,-1,1,1,1,1,... es fácil de ver que para cualquier C si cojemos d mayor que 16 ya lo tenemos. La conjetura dice que eso pasa siempre. Al ser tan simple de formular las conexiones que tiene con otras teorías más avanzadas están muy escondidas.

El paper primero discute ejemplos de funciones "parecidas" pero que no llegan a ser iguales donde la conjetura sería falsa. Es importante, por ejemplo, para demostrar la conjetura, el hecho de que |f(n)| = 1 para TODO n.

El proceso parece el siguiente. Primero, se dan cuenta de que parte esencial de la demostración consiste en funciones completamente multiplicativas (f(jd) = f(j)f(d)). Después, "generalizan" y en lugar de mirar funciones que valgan 1 o -1, miran funciones aleatorias cuyos valores están en el círculo unidad de los complejos. Ven que la conjetura inicial es equivalente a decir que el supremo para todo n del valor promedio del sumatorio hasta n de g(j) al cuadrado es igual a infinito. Fijaos que aquí hay más libertad en la función, pero sigue habiendo simetría ya que puede ser g(1) = i, g(2) = 1, g(3) = -1 y así.

Para demostrar esto usan un teorema bastante técnico que no creo que merezca la pena comentar, que básicamente acota la autocorrelación de una función de ese tipo, y lo que llama el truco de van der Corput que es básicamente ver que, en promedio, las "buenas" funciones definidas sobre la circunferencia (de hecho sobre el toro), se repartiran bastante equitativamente. Con estos dos ingredientes ven que los únicos problemas que pueden encontrar para demostrar la conjetura de la discrepancia son funciones multiplicativas que "parecen" como si fueran una función con 0s pero sustituidos. Ya sé que suena raro, pero lo que llama Dirichlet characters son unas funciones que valen 1,0,-1 con unas normas muy concretas y la idea es que las funciones que pueden presentar problemas son aquellas que son "como un caracter de Dirichlet" pero con 1s o -1s en lugar de los ceros.

Una vez han localizado esos casos especiales, los analizan por separado y ven que pueden establecer una cota logaritmica al crecimiento de la discrepancia con un argumento con vectores y representación de los números en base n.

Nótese que la conjetura sería falsa si dijera que el supremo sobre n del sumatorio desde 1 hasta n de |f(id)| es infinito, de hecho muestra un contraejemplo a eso. No obstante eso no es lo mismo que decir que para cualquier C puedas encontrar una k y una d tales que bla bla bla. Orden de los cuantificadores gente.

TL;DR:

Claves de la demostración: Demostrar la relación con un problema más general (y por tanto con más herramientas disponibles, esta es una técnica que va muy bien y Grothendiek fue famoso por usarla con mucha soltura). Solucionar el problema más general en los casos donde todo va bien. Solucionar los casos que no todo va tan bien.

5 1 respuesta
Millonet1

#11 Muchas gracias por tomarte todo ese tiempo para explicarlo tan bien :)

1 respuesta
B

#12 nada faltaría más xD, si a mí me mola hablar de estos temas. El tema clave ha sido encontrar la relación con ese teorema de las autocorrelaciones parece ser (como siempre, encontrar relaciones es lo que más cuesta y más mola).

23 días después
Millonet1

Supongo que este tema estará bastante olvidado, pero he encontrado este explicación en reddit que creo que complementa bien la de Duronman a un nivel algo mas divulgativo:

spoiler
1

Usuarios habituales