This is part of topological dynamics (a close cousin of ergodic theory, aka measurable dynamics, in which the underlying space on which the dynamics takes place is a topological space rather than a measure space). The relationship with combinatorics is roughly as follows: topological dynamics is to colouring Ramsey theorems (such as van der Waerden) as measurable dynamics is to density Ramsey theorems (such as Szemeredi).
For simplicity, let's work on the integers (there is a trick to then deal with the natural numbers, that I will talk about later).
Consider the cube $Omega := {-1,+1}^{{bf Z}}$, with the standard right shift T. We give this cube the product topology, making it a compact metrisable space. Every +-1 sequence is then a point x in $Omega$, and defines an orbit $T^{bf Z} x = { T^n x: n in {bf Z} }$, and then an orbit closure $overline{T^{bf Z} x}$. This is a closed, T-invariant subset of $Omega$ (which a topological dynamicist would call a subsystem of $Omega$).
Note that if y appears in this orbit closure, then every finite substring of y appears somewhere in x. So it is natural to try to look for what is in this orbit closure.
A simple application of Zorn's lemma tells us that every orbit closure contains at least one minimal non-empty closed T-invariant subset; these are known as minimal systems. (The notion of minimality in topological dynamics is broadly equivalent to the notion of ergodicity in ergodic theory.) Every element of a minimal system is almost periodic, which means that every finite block in the element appears syndetically (with bounded gaps). So one can always get an almost periodic element (this is a special case of the Birkhoff recurrence theorem).
All this is discussed in these lecture notes of mine.
Now, one can go beyond minimality and obtain further classification of such systems, and the subject gets rather interesting at this point. For instance, we have isometric systems (analogous to the compact systems in ergodic theory), with the property that if two points $x,y$ in the system are close, then all their shifts $T^n x, T^n y$ are uniformly close as well. Orbit closures of quasiperiodic sequences fall in this category. At the other extreme, we have topologically mixing systems (analogous to the mixing systems in ergodic theory), in which given any two non-empty open sets U, V in the system, the shift $T^n U$ of one of them will intersect the other V for all sufficiently large n. Orbit closures of random sequences (i.e. all of $Omega$) fall into this category. Then there are various intermediate systems between these, for instance one can take isometric extensions of isometric systems (analogous to things like nilsystems in ergodic theory), and so forth. This is all discussed to some extent in these later lecture notes of mine.
If one is working on the natural numbers rather than the integers, then it may seem prima facie that the shift T is now not invertible, but it is not difficult to convert the natural number situation to the integer situation, by starting with a sequence x on the integers and looking at the set of strings on the integers with the property that every finite substring of those integers appears infinitely often in the original sequence. This is a closed T-invariant subset of $Omega$; a simple compactness argument shows that it is nonempty. So one can basically reduce to subsystems of $Omega$ as before.
Finally, I should mention that there is an approach to this subject via ultrafilters. Given any non-principal ultrafilter $p in {Bbb Z}$, one can take the ultrashift $T^p x$ of a sequence $x$, defined as the ultralimit of the shifts $T^n x$ along the ultrafilter p (this is well-defined because $Omega$ is compact metrisable). One can then reduce a significant fraction of topological dynamics to the algebraic properties of ultrafilters. For instance, Hindman's theorem is a quick consequence of the existence of an idempotent ultrafilter. This is discussed at the first set of notes above, and also in its sequel.
No comments:
Post a Comment