One of the basic objects of study in combinatorics are finite strings or infinite strings of symbols from some given alphabet , which could be either finite or infinite (but which we shall usually take to be compact). For instance, a set of natural numbers can be identified with the infinite string of s and s formed by the indicator of , e.g. the even numbers can be identified with the string from the alphabet , the multiples of three can be identified with the string , and so forth. One can also consider doubly infinite strings , which among other things can be used to describe arbitrary subsets of integers.

On the other hand, the basic object of study in dynamics (and in related fields, such as ergodic theory) is that of a dynamical system , that is to say a space together with a shift map (which is often assumed to be invertible, although one can certainly study non-invertible dynamical systems as well). One often adds additional structure to this dynamical system, such as topological structure (giving rise topological dynamics), measure-theoretic structure (giving rise to ergodic theory), complex structure (giving rise to complex dynamics), and so forth. A dynamical system gives rise to an action of the natural numbers on the space by using the iterates of for ; if is invertible, we can extend this action to an action of the integers on the same space. One can certainly also consider dynamical systems whose underlying group (or semi-group) is something other than or (e.g. one can consider continuous dynamical systems in which the evolution group is ), but we will restrict attention to the classical situation of or actions here.

There is a fundamental *correspondence principle* connecting the study of strings (or subsets of natural numbers or integers) with the study of dynamical systems. In one direction, given a dynamical system , an *observable* taking values in some alphabet , and some initial datum , we can first form the forward orbit of , and then observe this orbit using to obtain an infinite string . If the shift in this system is invertible, one can extend this infinite string into a doubly infinite string . Thus we see that every quadruplet consisting of a dynamical system , an observable , and an initial datum creates an infinite string.

Example 1If is the three-element set with the shift map , is the observable that takes the value at the residue class and zero at the other two classes, and one starts with the initial datum , then the observed string becomes the indicator of the multiples of three.

In the converse direction, every infinite string in some alphabet arises (in a decidedly *non*-unique fashion) from a quadruple in the above fashion. This can be easily seen by the following “universal” construction: take to be the set of infinite strings in the alphabet , let be the shift map

let be the observable

and let be the initial point

Then one easily sees that the observed string is nothing more than the original string . Note also that this construction can easily be adapted to doubly infinite strings by using instead of , at which point the shift map now becomes invertible. An important variant of this construction also attaches an invariant probability measure to that is associated to the limiting density of various sets associated to the string , and leads to the *Furstenberg correspondence principle*, discussed for instance in these previous blog posts. Such principles allow one to rigorously pass back and forth between the combinatorics of strings and the dynamics of systems; for instance, Furstenberg famously used his correspondence principle to demonstrate the equivalence of Szemerédi’s theorem on arithmetic progressions with what is now known as the Furstenberg multiple recurrence theorem in ergodic theory.

In the case when the alphabet is the binary alphabet , and (for technical reasons related to the infamous non-injectivity of the decimal representation system) the string does not end with an infinite string of s, then one can reformulate the above universal construction by taking to be the interval , to be the doubling map , to be the observable that takes the value on and on (that is, is the first binary digit of ), and is the real number (that is, in binary).

The above universal construction is very easy to describe, and is well suited for “generic” strings that have no further obvious structure to them, but it often leads to dynamical systems that are much larger and more complicated than is actually needed to produce the desired string , and also often obscures some of the key dynamical features associated to that sequence. For instance, to generate the indicator of the multiples of three that were mentioned previously, the above universal construction requires an uncountable space and a dynamics which does not obviously reflect the key features of the sequence such as its periodicity. (Using the unit interval model, the dynamics arise from the orbit of under the doubling map, which is a rather artificial way to describe the indicator function of the multiples of three.)

A related aesthetic objection to the universal construction is that of the four components of the quadruplet used to generate the sequence , three of the components are completely universal (in that they do not depend at all on the sequence ), leaving only the initial datum to carry all the distinctive features of the original sequence. While there is nothing wrong with this mathematically, from a conceptual point of view it would make sense to make all four components of the quadruplet to be adapted to the sequence, in order to take advantage of the accumulated intuition about various special dynamical systems (and special observables), not just special initial data.

One step in this direction can be made by restricting to the orbit of the initial datum (actually for technical reasons it is better to restrict to the topological closure of this orbit, in order to keep compact). For instance, starting with the sequence , the orbit now consists of just three points , , , bringing the system more in line with the example in Example 1. Technically, this is the “optimal” representation of the sequence by a quadruplet , because any other such representation is a factor of this representation (in the sense that there is a unique map with , , and ). However, from a conceptual point of view this representation is still somewhat unsatisfactory, given that the elements of the system are interpreted as infinite strings rather than elements of a more geometrically or algebraically rich object (e.g. points in a circle, torus, or other homogeneous space).

For general sequences , locating relevant geometric or algebraic structure in a dynamical system generating that sequence is an important but very difficult task (see e.g. this paper of Host and Kra, which is more or less devoted to precisely this task in the context of working out what component of a dynamical system controls the multiple recurrence behaviour of that system). However, for specific examples of sequences , one can use an informal procedure of educated guesswork in order to produce a more natural-looking quadruple that generates that sequence. This is not a particularly difficult or deep operation, but I found it very helpful in internalising the intuition behind the correspondence principle. Being non-rigorous, this procedure does not seem to be emphasised in most presentations of the correspondence principle, so I thought I would describe it here.

The basic way to proceed here is to ask oneself the following information-theoretic question. Suppose you are given the sequence with values in some compact alphabet , and that some adversary selects a natural number without telling you exactly what it is. On the other hand, the adversary must truthfully answer any question about that you pose to it, provided that the answer takes values in some compact space (so one can for instance ask yes-no questions about , but one cannot simply ask the adversary what is, since the natural numbers are not compact). Your job is to acquire enough information from the adversary in order for you to determine not only the current value of the sequence, but also all subsequent values of the sequence. Furthermore, the answers that the adversary gives for a given choice of should be sufficient information to also determine what answers the adversary would also have given for . The space in which your answers reside in will eventually be the space in the quadruplet , with corresponding to the answers in that space that the adversary gives for a given choice of ; the observable is the function that takes the answers given and returns the value of that one can deduce from those answers, and the shift map encodes the relationship between the answers given for and the answers given for . (One can then often place an invariant measure on by considering (or guessing) the equidistribution properties of the orbit , but we will not pursue this point here.)

As it stands, this problem has a trivial answer: you simply asks the adversary for the entire tuple , which takes values in the compact space ; the adversary is forced to supply this information, which gives you everything you need for the problem, namely the value of and all subsequent elements of the sequence, as well as what the adversary would have provided for instead of . This corresponds to the universal construction outlined earlier. In the case of a binary alphabet , one can similarly ask for the real number in , which achieves the same goal (at least when the sequence does not end in an infinite string of s). (One could also ask the adversary for as embedded in a compactification of the natural numbers, such as the Stone-Cech compactification , to get another trivial solution to the problem; this gives rise to some other important ways to extract a dynamical interpretation to a set of integers. See this blog post for some variants on this theme.)

But the point of phrasing things this way is that one can look for more “elegant” ways in which to extract information from the adversary, in which one asks the adversary for a certain minimal amount of “relevant” information rather than asking what is basically an infinite number of questions rolled into one (which one then considers to be “cheating”). Ideally, the information asked should also reflect the underlying geometric or algebraic structure of the original sequence . From a purely rigorous mathematical viewpoint, there are no compelling objective criteria by which to judge what set of questions to ask the adversary is the “best” one, but one can nevertheless still proceed by relying on more informal and subjective evaluations of the information asked. It turns out that proceeding in an intelligently guided trial-and-error fashion, in which one starts with an initial first guess to the problem and refines it in reaction to the defects of that guess, is usually quite instructive in revealing the “true” dynamics behind any given sequence.

Let’s illustrate this with a few examples. We begin with the previously considered example of the indicator function of the multiples of three, so that equals when is a multiple of three and equals zero otherwise. Thus, it is natural as a first guess to simply ask the adversary if is a multiple of three. But while this question reveals to you the value of , it does not reveal the value of , because being told that is not a multiple of three is insufficient information to determine whether is a multiple of three. To put it another way, the information the adversary provided for is not sufficient to determine the information the adversary would have provided for . To resolve this, we soon see that we need a bit more information than whether is a multiple of three: we need the residue class of modulo three, and this is enough information both to work out , and to work out what the adversary would say for (since the residue class is simply the increment of the residue class ), which upon iteration then provides the value of , , etc. This gives the dynamical system described in Example 1.

Now let us consider another example. Let be a real number that is already known to you (e.g. one can take , for sake of concreteness), and consider the sequence , taking values in the interval . As before, the first naive guess here would be to simply ask the adversary for the value of , which of course will tell you what is, but does not quite reveal the value of . Indeed, the sine addition law gives

which does not quite allow us to determine from , because while and are known quantities, the cosine is not quite determined: the classic identity only determines up to a sign. This can be rectified in a number of ways. One is to ask the adversary for both and , as one can then update both of these pieces of data for through the addition law (1) as well as its counterpart

Using the usual identification of the unit circle with , one can reformulate this in a more modern fashion by simply asking the adversary for the value of in the unit circle , as this determines and can be updated using the shift map on . This interprets the sequence in terms of the *circle shift* dynamical system, in which and ; the observable in this case is and the initial datum is .

Now consider the sequence taking values now in , where are two given real numbers (e.g. and ). Pursuing a similar line of reasoning to the above, we soon see that a good set of questions to ask the adversary are the values of and , as these two pieces of information both determine the current member of the sequence, and can also be updated easily as one moves from to . This interprets the given sequence in terms of the *-torus shift* in which , , , and . More generally, any quasiperiodic sequence can be interpreted in terms of a shift map on a -torus.

Next, we consider the quadratic phase sequence . Based on previous experience, we can query the adversary for , but this is not sufficient by itself, because we cannot update this information into without additional input. However, since

we can attempt to fix this by also querying the adversary about (one could also use here if desired). Note that can itself be updated easily through the identity

By using the combination of these two queries, we represent the above quadratic phase sequence in terms of the *skew shift* system in which , , , and . Similarly for polynomial phase sequences, in which one replaces by some other polynomial of with real coefficients.

Now we turn to the example , where are real numbers and is the greatest integer less than or equal to . As before, we begin by querying the adversary for , but are then faced with the question of how to update this information when moving from to , that is to say we need a way to determine

in terms of queried data. The problem here is that could either equal or . But one can determine which of these is the case by querying for the fractional part of , or equivalently by querying for . Indeed, we see that

if , and

otherwise. This leads to the dynamical system whose shift map is given by setting

when , and

otherwise, with the observable and initial datum . This is not the only way to represent this sequence by a dynamical system, of course; if one observes that

then one can alternately proceed by querying for and , leading to a -torus system with , , , and . One can verify that this system is in fact conjugate to the previous system; it simplifies the shift at the expense of making the observable more complicated (in particular, at least one of the dynamics or the observable will be discontinuous).

Similar considerations apply to the example . Starting with a query to , one soon realises that to update this piece of information, one also needs access to and to . This gives rise to a mildly complicated system on a -torus (or, alternatively, a cube ) that tracks the fractional parts of , , and , with a piecewise polynomial shift function , the precise description of which we leave as an exercise to the reader. In analogy with the previous example, this system can be conjugated to a rotation on the *Heisenberg nilmanifold*

at the cost of turning the observable into a slightly messy piecewise smooth function; see e.g. this blog post for details. More generally, any function arising from phases that are *bracket polynomials* (or *generalised polynomials*) in (which means that, like , they are formed out of and some real constants using the ring operations and the floor function finitely many times), the associated sequences can be described in terms of a piecewise smooth function on a nilmanifold; see this paper of Bergelson and Leibman for details.

Thus far, we have restricted attention to sequences that are strongly “deterministic” in various senses (for instance, they have zero topological entropy, which roughly speaking means that one needs only queries in order to predict the behaviour of the sequence for the next steps in time). This is reflected in the nilpotent (and finite-dimensional) nature of the systems being produced. When the sequence is more chaotic, then it becomes difficult to find a dynamical system to describe the dynamics that is any simpler than the universal system. Consider for instance the sequence arising from the digits of in base , so that the alphabet here is . The problem here is that knowledge of the digit of tells us virtually nothing useful about the digit, and there is no obvious set of queries (other than that of asking for basically the entire string of digits after tne digit) that would let one perform an update from to . Thus, one is basically left with universal constructions, e.g. taking to be the interval , letting be the shift map (i.e. is the remainder of when divided by ), with observable and initial datum . It is widely expected that is a “generic” point of this system, which is equivalent to the notoriously difficult conjecture that is a normal number in base (of course, is conjectured to be normal in every base, but currently it is not known if it is normal in even one base). This dynamical system model does not shed too much light on this issue, since it is not tailored to in any way. One can try to use various explicit identities involving to hope to get a more useful dynamical system to model , but so far these efforts have not yielded dramatic results. (One could hope for instance that the Bailey-Borwein-Plouffe formula could help describe the base digits of , but the resulting dynamical system obtained is quite complicated.)

Now we turn to the sequence coming from the Möbius function (where we adopt for sake of discussion the convention that ). The Möbius function is conjectured to behave quite random in many ways (see this blog post for a discussion of some of these), and so one might think that there is no interesting dynamical system to model this function other than the universal ones. But one can perform a separation

of the Möbius function into the unsigned part of the Möbius function (which is when is square-free, and otherwise), and the *Liouville function* , which takes values in (assigning , say, for sake of discussion). Like the digits of , the Liouville function is widely expected to fluctuate in a chaotic fashion and is unlikely to be easily modeled by anything other than a universal model (e.g. the shift map on ). But the unsigned part is significantly more regular. Indeed, much as the indicator function of the multiples of three can be understood through the querying of , can be obtained after querying for all primes , since is precisely when all of these residue classes are non-zero. As each of these residue classes are easily updated when we increment to , we see that can be modeled by the dynamical system with with being the shift

and being the observable that sets to equal when the residue classes are all non-zero and otherwise, with initial datum . While this system does have positive topological entropy, it is otherwise fairly regular and can be analysed relatively easily (especially when compared with the Möbius or Liouville functions). For instance, an obvious invariant measure to place on this system is the Haar measure on , that is to say the product of the uniform probability measures on each of the . Using this measure, one can show using Fourier analysis that the shift map is *uniquely ergodic*, and that is an indicator function of a compact set of measure

Among other things, this shows that the square-free numbers have asymptotic density . Several further properties of this system were analysed recently by Cellarosi and Sinai. The Möbius function itself does not arise directly from this system, but instead comes from a *joining* of this system with a system modeling the Liouville function. Unfortunately, the latter system is poorly understood (one can use a universal model here, and conjecture that the Liouville function corresponds to a generic point in that model, but only a small number of aspects of this conjecture can be rigorous established with current technology), and our understanding of either the Möbius or Liouville functions are still very far from satisfactory.

There are a vast number of systems that lie intermediate between the deterministic systems associated to nilmanifolds, and the (conjecturally) chaotic systems associated to sequences such as the Möbius function or the digits of . For instance, the systems associated to automatic sequences, such as the Thue-Morse sequence or the Rudin-Shapiro sequence exhibit a number of interesting intermediate behaviours (e.g. the system associated to Thue-Morse has purely singular spectrum despite having zero topological entropy), and have attracted a substantial amount of attention in dynamics.

## 5 comments

Comments feed for this article

28 March, 2013 at 7:12 am

Jon AwbreyOne approach to discrete dynamics is through differential logic, the first elements of which are essayed here:

Differential Logic and Dynamic Systems

29 March, 2013 at 12:26 pm

Jon AwbreyThere is a motivational prelude to the main fugue here:

Differential Propositional Calculus

3 April, 2013 at 8:09 am

enricoI think that there is a typo in the skew shift representing the quadratic phase sequence. Isn’t it T(x,y) = (x+alpha, y+2x + alpha)?

[Corrected, thanks – T.]4 April, 2013 at 2:42 am

Nik WanI want to be like you. How do you work daily? monthly? seasonally?

Whats your daily routine?

20 November, 2013 at 11:44 am

Vít TučekShortly after Example 1 you write “Then one easily sees that the observed string {(c(T^n x_0))_{n=0}^\infty} is nothing more than the original string {(b_i)_{n=0}^\infty}.” I think the original string should be {(a_i)_{n=0}^\infty}

[Corrected, thanks – T.]