Improving a sequence of 1s and -1s

Question

Suppose you take a $\pm 1$ sequence and you want to "improve it" by taking pointwise limits of translates. What properties can you guarantee to get in the limit?

Two examples illustrate what I think should be the extremes. If your sequence is random, then every finite subsequence occurs infinitely often, which means that it is easy to find translates that converge pointwise to any sequence you like. In particular, you can make the final sequence constant, though what interests me is that it is highly structured.

By contrast, let's suppose that the sequence is quasiperiodic, or more concretely that you take a real number $\alpha$ and define $x_n$ to be 1 or -1 according to whether the integer part of $\alpha n$ is even or odd. In that case, it is not hard to prove that every pointwise limit is quasiperiodic as well. (Unless I've made a mistake, the result is that there must be some $\beta$ such that $z_n$ is 1 or -1 according to whether the integer part of $\alpha n+\beta$ is even or odd.)

What can be said in general? Can we always "get rid of the randomness" and find a highly structured limit? And what does "highly structured" mean? Perhaps that an associated dynamical system is compact, though I'd ideally like a characterization in terms of the sequence itself.

This question ought to be meat and drink to ergodic theorists. Indeed, I feel slightly guilty for not knowing the answer already. It arises naturally in a Polymath project (which can be found by searching for "Erdos discrepancy problem").

Added later: I've just realized one simple lemma. Suppose you want to get rid of some finite subsequence. Then you can do it if you can find arbitrarily long subsequences that avoid that finite subsequence. So either you can get rid of the subsequence, or it occurs in the original sequence with bounded gaps. I think that means you can reach a sequence such that every finite subsequence that appears appears with bounded gaps.

Answer 1

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.

Answer 2

Here are some other comments in the spirit of Terry's and Anton's answers.

There is nothing special about the symbols $\pm 1$ in the question; the spaces of binary strings $(\mathbb{Z}/2)^\mathbb{N}$ and $(\mathbb{Z}/2)^\mathbb{Z}$ are a more standard notation. As Terry says, you can switch between singly infinite and doubly infinite sequences.

The process of taking pointwise limits of translates over and over again until no more data can be removed is exactly equivalent to finding a minimal set with respect to the dynamical action of the shift map. If $x$ does not lie in a minimal set, then the closure of its orbit contains a $y$ whose orbit has a smaller closure; thus $y$ is a limit of translates of $x$ in which something has been lost. On the other hand, all points in a minimal set are limits of translates of each other, so once you are in a minimal set, there is no way to erase any more data.

Birkhoff established that a symbolic sequence $x$ is minimal, or lies in a minimal set, if and only if it is "almost periodic". Anton used the term "quasiperiodic", but this is a confusing term that sometimes means almost periodic and sometimes means other things. It is true that a quasiperiodic pattern such as a Penrose tiling or a quasicrystal is almost periodic. (These are higher-dimensional examples, but the issues are the same for all locally compact abelian groups.) Sometimes quasiperiodic examples have the additional property that the recurrence length $L(\ell)$ is linear in $\ell$ or $O(\ell)$. Penrose tilings are already related to one interesting class of examples in one dimension: If $\alpha$ is an irrational number between 0 and 1, then the sequence $a_n = \lfloor (n+1)\alpha \rfloor - \lfloor n \alpha \rfloor$ is an almost periodic binary sequence.

What Anton could mean by the statement "you will not get more" is two things. First, that every almost periodic sequence is minimal, and therefore that you can't simplify it further by taking a limit of its translates. Second, that there isn't any simpler characterization of minimal shifts than that they are almost periodic.

Section 13.7 of the book "An introduction to symbolic dynamics and coding" by Douglas Lind gives a survey of properties of minimal shifts in symbolic dynamics. Lind says that that a widely studied example is the Morse-Thue sequence, which is an example of an almost periodic sequence obtained by substitution rules. Lind says that any substitution-type almost periodic sequence, or substitution shift, has zero entropy, but that Furstenburg found an example of a minimal shift with positive entropy. This suggests that it is not always possible to "get rid of the randomness", as Tim (?) asks, even though all limits are highly structured in the sense of being almost periodic.

Answer 3

"Quasiperiodic" means that there is a function $L:\mathbb N\to\mathbb N$ such that any sequence of length $\ell$ appears in any sequence of length $L(\ell)$. You can get a quasiperiodic sequence as a limit, but you you will not get more. The later follows from your remark (which is added later).

P.S. If you start with a quasiperiodic sequence, then you can get a new sequence as a limit. But, the same way, you also can get your original sequence from the new one.

P.P.S. It seems to be interesting to consider quasiperiodic sequences with $L(\ell)=const\cdot\ell$. Was it considered anywhere? Is it true that if $L=\tfrac{3}{2}\cdot\ell$ then sequence is periodic?