29 votos

Mejorar una secuencia de 1s y -1s

Suponga que toma un $\pm 1$ secuencia y se quiere "mejorarla" tomando límites puntuales de traslados. ¿Qué propiedades puede garantizar obtener en el límite?

Dos ejemplos ilustran lo que creo que deberían ser los extremos. Si tu secuencia es aleatoria, entonces cada subsecuencia finita ocurre infinitamente a menudo, lo que significa que es fácil encontrar traducciones que convergen puntualmente a cualquier secuencia que quieras. En particular, puedes hacer que la secuencia final sea constante, aunque lo que me interesa es que esté muy estructurada.

Por el contrario, supongamos que la secuencia es cuasiperiódica, o más concretamente que se toma un número real $\alpha$ y definir $x_n$ sea 1 o -1 en función de si la parte entera de $\alpha n$ es par o impar. En ese caso, no es difícil demostrar que todo límite puntual es también cuasiperiódico. (A menos que me haya equivocado, el resultado es que debe haber algún $\beta$ tal que $z_n$ es 1 o -1 según si la parte entera de $\alpha n+\beta$ es par o impar).

¿Qué se puede decir en general? ¿Podemos siempre "deshacernos del azar" y encontrar un límite altamente estructurado? ¿Y qué significa "altamente estructurado"? Quizás que un sistema dinámico asociado es compacto, aunque lo ideal sería una caracterización en términos de la propia secuencia.

Esta cuestión debería ser el pan de cada día para los teóricos de la ergodicidad. De hecho, me siento ligeramente culpable por no conocer ya la respuesta. Surge de forma natural en un proyecto de Polymath (que se puede encontrar buscando "Erdos discrepancy problem").

Añadido más tarde: Acabo de darme cuenta de un simple lema. Supongamos que quieres deshacerte de alguna subsecuencia finita. Entonces puedes hacerlo si puedes encontrar subsecuencias arbitrariamente largas que eviten esa subsecuencia finita. Así que, o bien puedes deshacerte de la subsecuencia, o ésta aparece en la secuencia original con huecos acotados. Creo que eso significa que se puede llegar a una secuencia tal que cada subsecuencia finita que aparezca lo haga con espacios acotados.

16voto

steevc Puntos 211

Esto forma parte de la dinámica topológica (un primo cercano de la teoría ergódica, también conocida como dinámica medible, en la que el espacio subyacente en el que tiene lugar la dinámica es un espacio topológico en lugar de un espacio de medidas). La relación con la combinatoria es, a grandes rasgos, la siguiente: la dinámica topológica es a los teoremas de Ramsey de coloración (como el de van der Waerden) lo que la dinámica medible es a los teoremas de Ramsey de densidad (como el de Szemeredi).

Para simplificar, vamos a trabajar con los números enteros (hay un truco para tratar luego los números naturales, del que hablaré más adelante).

Considere el cubo $\Omega := \{-1,+1\}^{{\bf Z}}$ con el desplazamiento estándar a la derecha T. Damos a este cubo la topología de producto, convirtiéndolo en un espacio compacto metrizable. Cada secuencia +-1 es entonces un punto x en $\Omega$ y define una órbita $T^{\bf Z} x = \{ T^n x: n \in {\bf Z} \}$ y luego un cierre de órbita $\overline{T^{\bf Z} x}$ . Se trata de un subconjunto cerrado e invariable en T de $\Omega$ (que un dinamicista topológico llamaría subsistema de $\Omega$ ).

Obsérvese que si y aparece en este cierre de órbita, entonces toda subcadena finita de y aparece en algún lugar de x. Así que es natural tratar de buscar lo que está en este cierre de órbita.

Una simple aplicación del lema de Zorn nos dice que todo cierre de órbita contiene al menos una mínimo subconjunto cerrado no vacío de T-invariante; estos se conocen como sistemas mínimos . (La noción de minimalidad en la dinámica topológica es, en líneas generales, equivalente a la noción de ergodicidad en la teoría ergódica). Cada elemento de un sistema mínimo es casi periódico , lo que significa que cada bloque finito del elemento aparece de forma sindeada (con huecos acotados). Así que siempre se puede obtener un elemento casi periódico (este es un caso especial de la Teorema de recurrencia de Birkhoff ).

Todo esto se discute en estos notas de conferencias mías .

Ahora bien, se puede ir más allá de la minimalidad y obtener una mayor clasificación de tales sistemas, y el tema se vuelve bastante interesante en este punto. Por ejemplo, tenemos sistemas isométricos (análogo al sistemas compactos en teoría ergódica), con la propiedad de que si dos puntos $x,y$ en el sistema están cerca, entonces todos sus turnos $T^n x, T^n y$ son uniformemente cercanos también. Los cierres de órbita de las secuencias cuasiperiódicas entran en esta categoría. En el otro extremo, tenemos sistemas de mezcla topológica (análogo al sistemas de mezcla en teoría ergódica), en la que dados dos conjuntos abiertos no vacíos U, V en el sistema, el desplazamiento $T^n U$ de una de ellas intersectará a la otra V para todo n suficientemente grande. Los cierres de órbita de las secuencias aleatorias (es decir, todos los $\Omega$ ) entran en esta categoría. Luego hay varios sistemas intermedios entre estos, por ejemplo uno puede tomar extensiones isométricas de sistemas isométricos (análogo a cosas como los sistemas nil en la teoría ergódica), y así sucesivamente. Todo esto se discute en cierta medida en estos apuntes míos de conferencias posteriores .

Si se trabaja con los números naturales y no con los enteros, entonces puede parecer a primera vista que el desplazamiento T ahora no es invertible, pero no es difícil convertir la situación de los números naturales a la situación de los enteros, comenzando con una secuencia x en los enteros y observando el conjunto de cadenas en los enteros con la propiedad de que cada subcadena finita de esos enteros aparece infinitamente a menudo en la secuencia original. Se trata de un subconjunto cerrado T-invariante de $\Omega$ un simple argumento de compacidad muestra que no es vacío. Así que básicamente se puede reducir a subsistemas de $\Omega$ como antes.

Por último, debo mencionar que existe una aproximación a este tema a través de los ultrafiltros. Dado cualquier ultrafiltro no principal $p \in {\Bbb Z}$ se puede tomar el ultrashift $T^p x$ de una secuencia $x$ definido como el ultralímite de los desplazamientos $T^n x$ a lo largo del ultrafiltro p (esto está bien definido porque $\Omega$ es compacta y metrizable). Se puede entonces reducir una parte importante de la dinámica topológica a las propiedades algebraicas de los ultrafiltros. Por ejemplo, el teorema de Hindman es una consecuencia rápida de la existencia de un ultrafiltro idempotente. Esto se discute en la primera serie de notas anteriores, y también en su secuela .

8voto

John Topley Puntos 58789

Aquí hay otros comentarios en el espíritu de las respuestas de Terry y Anton.

Los símbolos no tienen nada de especial $\pm 1$ en la pregunta; los espacios de las cadenas binarias $(\mathbb{Z}/2)^\mathbb{N}$ y $(\mathbb{Z}/2)^\mathbb{Z}$ son una notación más estándar. Como dice Terry, se puede alternar entre las secuencias infinitas simples y las dobles.

El proceso de tomar límites puntuales de las traslaciones una y otra vez hasta que no se puedan eliminar más datos es exactamente equivalente a encontrar un conjunto mínimo con respecto a la acción dinámica del mapa de desplazamiento. Si $x$ no se encuentra en un conjunto mínimo, entonces el cierre de su órbita contiene un $y$ cuya órbita tiene un cierre menor; así $y$ es un límite de traslación de $x$ en la que se ha perdido algo. Por otro lado, todos los puntos de un conjunto mínimo son límites de traslación entre sí, por lo que una vez que se está en un conjunto mínimo, no hay forma de borrar más datos.

Birkhoff estableció que una secuencia simbólica $x$ es mínimo, o se encuentra en un conjunto mínimo, si y sólo si es "casi periódico". Anton utilizó el término "cuasiperiódico", pero éste es un término confuso que a veces significa casi periódico y a veces significa otras cosas. Es cierto que un patrón cuasiperiódico, como un mosaico de Penrose o un cuasicristal, es casi periódico (se trata de ejemplos de dimensiones superiores, pero las cuestiones son las mismas para todos los grupos abelianos localmente compactos). A veces los ejemplos cuasiperiódicos tienen la propiedad adicional de que la longitud de recurrencia $L(\ell)$ es lineal en $\ell$ o $O(\ell)$ . Los tilings de Penrose ya están relacionados con una clase interesante de ejemplos en una dimensión: Si $\alpha$ es un número irracional entre 0 y 1, entonces la secuencia $a_n = \lfloor (n+1)\alpha \rfloor - \lfloor n \alpha \rfloor$ es una secuencia binaria casi periódica.

Lo que Antón podría querer decir con la afirmación "no conseguirás más" es dos cosas. Primero, que toda secuencia casi periódica es mínima, y por tanto no se puede simplificar más tomando un límite de sus traslados. Segundo, que no hay ninguna caracterización más sencilla de los desplazamientos mínimos que el hecho de que sean casi periódicos.

Sección 13.7 del libro "An introduction to symbolic dynamics and coding" de Douglas Lind ofrece un estudio de las propiedades de los desplazamientos mínimos en la dinámica simbólica. Lind dice que un ejemplo ampliamente estudiado es el Secuencia Morse-Thue que es un ejemplo de secuencia casi periódica obtenida mediante reglas de sustitución. Lind dice que cualquier secuencia casi periódica de tipo sustitución, o cambio de sustitución tiene entropía cero, pero que Furstenburg encontró un ejemplo de un desplazamiento mínimo con entropía positiva. Esto sugiere que no siempre es posible "deshacerse de la aleatoriedad", como pide Tim (?), aunque todos los límites estén muy estructurados en el sentido de ser casi periódicos.

5voto

crashmstr Puntos 15302

"Cuasiperiódico" significa que hay una función $L:\mathbb N\to\mathbb N$ tal que cualquier secuencia de longitud $\ell$ aparece en cualquier secuencia de longitud $L(\ell)$ . Puedes obtener una secuencia cuasiperiódica como límite, pero no obtendrás más. Esto último se desprende de su observación (que se añade después).

P.D. Si empiezas con una secuencia cuasiperiódica, entonces puedes obtener una nueva secuencia como límite. Pero, del mismo modo, también puedes obtener tu secuencia original a partir de la nueva.

P.P.S. Parece interesante considerar las secuencias cuasiperiódicas con $L(\ell)=const\cdot\ell$ . ¿Se ha considerado en algún lugar? ¿Es cierto que si $L=\tfrac{3}{2}\cdot\ell$ entonces la secuencia es periódica?

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X