Entender la conjetura de discrepancia de Erdös $\left| \sum_{i=1}^k x_{i\cdot d} \right| > C$ para series aleatorias de $-1$ y $1$

Question

En el periódico de hoy NRC de los Países Bajos se dedicó un artículo de dos páginas a las pruebas matemáticas asistidas por ordenador (lo siento, enlace de pago y en holandés). Interesante en sí mismo, pero como ejemplo utilizó la prueba parcial para la divergencia de la serie que consiste en una distribución aleatoria de $-1$ y $1$ .

El Lema de Wikipedia sobre la conjetura de Erdös muestra esta fórmula:

$$\left| \sum_{i=1}^k x_{i\cdot d} \right| > C$$

Pero me cuesta entender eso en inglés común y aplicarlo al texto del artículo, que se traduce como:

dada una secuencia infinita de $-1$ y $1$ Toma un conjunto finito de términos a igual distancia, es decir, el primero, el tercero y el quinto, o el quinto, el décimo y el decimoquinto término. Suma todos esos términos. ¿En qué medida pueden diferir de $0$ ? Conjetura de Erdös: infinitamente lejos.

Mi malentendido viene de combinar infinito, aleatorio y finito. Creo que si la secuencia es aleatoria, entonces puede existir potencialmente cualquier conjunto finito de sólo $1$ o sólo $-1$ , lo que significa que la diferencia con respecto a cero es (potencialmente) igual a la cantidad de términos tomados.

El artículo explica además que Boris Konev y Alexei Lisitsa han demostrado que dentro de los primeros 1161 términos, la discrepancia es siempre al menos $3$ . Pero puedo fácilmente llegar a una secuencia que altere exactamente los números tomados, lo que obviamente resultaría en una posible discrepancia de como máximo $1$ para al menos algunas series o rodajas.

Del enlace, cito:

La prueba que el ordenador ha conseguido demuestra, según los dos investigadores, "que ninguna secuencia de longitud $1161$ y discrepancia $2$ existe".

Esto parece contradictorio, pero nadie en los artículos que he encontrado parece preguntarse por esto, y dado que requiere tanta investigación, supongo que simplemente no entiendo el problema.

Supongo que estoy entendiendo mal el problema, pero ¿alguien puede explicarme en qué me estoy equivocando?

Answer 1

En primer lugar, es de suma importancia entender la afirmación :

• Una secuencia aleatoria de $-1$ y $1$ se considera .
• Una constante aleatoria $C$ se elige . (por ejemplo $C=100$ )
• Sumas del tipo $$\sum_{i=1}^{k}x_{id}$$ se consideran .
• Queremos que alguna de esas sumas sea $>C$ en el módulo .

Ahora parece evidente que el principal malentendido que tienes reside en la contradicción entre las sumas de la forma $$\sum_{i=1}^{k}x_{id}$$ (la interpretación correcta ) y la cita del periódico :

es decir, el primero, el tercero y el quinto, o el quinto, el décimo y el decimoquinto término. Suma todos esos términos.

Estas dos interpretaciones no coinciden obviamente porque el índice del primer término debe ser también la diferencia común de los índices $d$ . (por eso $x_1+x_3+x_5$ no se considera )

Ahora que entiendes el enunciado veamos los casos (ya resueltos) $C=1$ y $C=2$ .

Para simplificar, trabajaré para $C=1$ (lo mismo funciona también para $C=2$ ) . Trabajamos por contradicción por lo que suponemos que :

Existe una secuencia infinita tal que todas las sumas consideradas son como máximo $1$ en el módulo

Ahora tenemos en cuenta todos los casos posibles y empezamos a construir uno esperando que eventualmente llegaremos a una contradicción .

Comience, por ejemplo, con $x_1=1$ Si elegimos $x_2=1$ tenemos $x_1+x_2=2$ que supera $1$ por lo que debemos tomar $x_2=-1$ Ahora no importa lo que elijamos para $x_3$ así que toma $x_3=-1$ .

Ahora, cuando elegimos $x_4$ debemos ocuparnos de las sumas : $x_2+x_4$ y $x_1+x_2+x_3+x_4$ así que $-1+x_4$ no puede superar $1$ en el módulo, lo que significa que $x_4=1$ . No importa qué $x_5$ que elegimos para tomar $x_5=1$ .

La secuencia ahora se ve como : $1,-1,-1,1,1$

Cuando elegimos $x_6$ debemos ocuparnos de las sumas : $x_1+x_2+x_3+x_4+x_5+x_6$ , $x_2+x_4+x_6$ y $x_3+x_6$ así que $x_6+1$ , $x_6-1$ no puede superar $1$ en el módulo que no deja ninguna posibilidad de elegir un candidato para $x_6$ :

Si $x_6=1$ entonces $x_6+1=2$ que supera $1$ . Si $x_6=-1$ entonces $x_6-1=-2$ que supera $1$ (en el módulo )

Así llegamos a la contradicción deseada .

Si trabajamos todas las posibilidades para los casos restantes (por el camino asumimos que $x_3=-1$ y $x_5=1$ por lo que hay más casos que manejar ) entonces llegaremos a contradicciones en todos los casos por lo que la afirmación asumida debe ser errónea y así el problema resuelto .

Lo mismo ocurre con $C=2$ : Suponiendo que existe tal secuencia , tratamos de construirla probando todas las posibilidades que satisfacen la condición y cuando llegamos a una contradicción hemos terminado .