One of the basic objects of study in combinatorics are finite strings {(a_n)_{n=0}^N} or infinite strings {(a_n)_{n=0}^\infty} of symbols {a_n} from some given alphabet {{\mathcal A}}, which could be either finite or infinite (but which we shall usually take to be compact). For instance, a set {A} of natural numbers can be identified with the infinite string {(1_A(n))_{n=0}^\infty} of {0}s and {1}s formed by the indicator of {A}, e.g. the even numbers can be identified with the string {1010101\ldots} from the alphabet {\{0,1\}}, the multiples of three can be identified with the string {100100100\ldots}, and so forth. One can also consider doubly infinite strings {(a_n)_{n \in {\bf Z}}}, 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 {(X,T)}, that is to say a space {X} together with a shift map {T: X \rightarrow X} (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 {{\bf N}} on the space {X} by using the iterates {T^n: X \rightarrow X} of {T} for {n=0,1,2,\ldots}; if {T} is invertible, we can extend this action to an action of the integers {{\bf Z}} on the same space. One can certainly also consider dynamical systems whose underlying group (or semi-group) is something other than {{\bf N}} or {{\bf Z}} (e.g. one can consider continuous dynamical systems in which the evolution group is {{\bf R}}), but we will restrict attention to the classical situation of {{\bf N}} or {{\bf Z}} 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 {(X,T)}, an observable {c: X \rightarrow {\mathcal A}} taking values in some alphabet {{\mathcal A}}, and some initial datum {x_0 \in X}, we can first form the forward orbit {(T^n x_0)_{n=0}^\infty} of {x_0}, and then observe this orbit using {c} to obtain an infinite string {(c(T^n x_0))_{n=0}^\infty}. If the shift {T} in this system is invertible, one can extend this infinite string into a doubly infinite string {(c(T^n x_0))_{n \in {\bf Z}}}. Thus we see that every quadruplet {(X,T,c,x_0)} consisting of a dynamical system {(X,T)}, an observable {c}, and an initial datum {x_0} creates an infinite string.

Example 1 If {X} is the three-element set {X = {\bf Z}/3{\bf Z}} with the shift map {Tx := x+1}, {c: {\bf Z}/3{\bf Z} \rightarrow \{0,1\}} is the observable that takes the value {1} at the residue class {0 \hbox{ mod } 3} and zero at the other two classes, and one starts with the initial datum {x_0 = 0 \hbox{ mod } 3}, then the observed string {(c(T^n x_0))_{n=0}^\infty} becomes the indicator {100100100\ldots} of the multiples of three.

In the converse direction, every infinite string {(a_n)_{n=0}^\infty} in some alphabet {{\mathcal A}} arises (in a decidedly non-unique fashion) from a quadruple {(X,T,c,x_0)} in the above fashion. This can be easily seen by the following “universal” construction: take {X} to be the set {X:= {\mathcal A}^{\bf N}} of infinite strings {(b_i)_{n=0}^\infty} in the alphabet {{\mathcal A}}, let {T: X \rightarrow X} be the shift map

\displaystyle T(b_i)_{n=0}^\infty := (b_{i+1})_{n=0}^\infty,

let {c: X \rightarrow {\mathcal A}} be the observable

\displaystyle c((b_i)_{n=0}^\infty) := b_0,

and let {x_0 \in X} be the initial point

\displaystyle x_0 := (a_i)_{n=0}^\infty.

Then one easily sees that the observed string {(c(T^n x_0))_{n=0}^\infty} is nothing more than the original string {(a_n)_{n=0}^\infty}. Note also that this construction can easily be adapted to doubly infinite strings by using {{\mathcal A}^{\bf Z}} instead of {{\mathcal A}^{\bf N}}, at which point the shift map {T} now becomes invertible. An important variant of this construction also attaches an invariant probability measure to {X} that is associated to the limiting density of various sets associated to the string {(a_i)_{n=0}^\infty}, 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 {{\mathcal A}} is the binary alphabet {\{0,1\}}, and (for technical reasons related to the infamous non-injectivity {0.999\ldots = 1.00\ldots} of the decimal representation system) the string {(a_n)_{n=0}^\infty} does not end with an infinite string of {1}s, then one can reformulate the above universal construction by taking {X} to be the interval {[0,1)}, {T} to be the doubling map {Tx := 2x \hbox{ mod } 1}, {c: X \rightarrow \{0,1\}} to be the observable that takes the value {1} on {[1/2,1)} and {0} on {[0,1/2)} (that is, {c(x)} is the first binary digit of {x}), and {x_0} is the real number {x_0 := \sum_{n=0}^\infty a_n 2^{-n-1}} (that is, {x_0 = 0.a_0a_1\ldots} in binary).

The above universal construction is very easy to describe, and is well suited for “generic” strings {(a_n)_{n=0}^\infty} 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 {(a_n)_{n=0}^\infty}, and also often obscures some of the key dynamical features associated to that sequence. For instance, to generate the indicator {100100100\ldots} of the multiples of three that were mentioned previously, the above universal construction requires an uncountable space {X} 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 {2/7} 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 {X,T,c,x_0} of the quadruplet {(X,T,c,x_0)} used to generate the sequence {(a_n)_{n=0}^\infty}, three of the components {X,T,c} are completely universal (in that they do not depend at all on the sequence {(a_n)_{n=0}^\infty}), leaving only the initial datum {x_0} 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 {X} to the orbit {\{ T^n x_0: n \in {\bf N} \}} of the initial datum {x_0} (actually for technical reasons it is better to restrict to the topological closure {\overline{\{ T^n x_0: n \in {\bf N} \}}} of this orbit, in order to keep {X} compact). For instance, starting with the sequence {100100100\ldots}, the orbit now consists of just three points {100100100\ldots}, {010010010\ldots}, {001001001\ldots}, bringing the system more in line with the example in Example 1. Technically, this is the “optimal” representation of the sequence by a quadruplet {(X,T,c,x_0)}, because any other such representation {(X',T',c',x'_0)} is a factor of this representation (in the sense that there is a unique map {\pi: X \rightarrow X'} with {T' \circ \pi = \pi \circ T}, {c' \circ \pi = c}, and {x'_0 = \pi(x_0)}). However, from a conceptual point of view this representation is still somewhat unsatisfactory, given that the elements of the system {X} 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 {(a_n)_{n=0}^\infty}, 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 {(a_n)_{n=0}^\infty}, one can use an informal procedure of educated guesswork in order to produce a more natural-looking quadruple {(X,T,c,x_0)} 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 {(a_n)_{n=0}^\infty} with values in some compact alphabet {{\mathcal A}}, and that some adversary selects a natural number {n} without telling you exactly what it is. On the other hand, the adversary must truthfully answer any question about {n} 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 {n}, but one cannot simply ask the adversary what {n} 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 {a_n} of the sequence, but also all subsequent values {a_{n+1}, a_{n+2}, a_{n+3}, \ldots} of the sequence. Furthermore, the answers that the adversary gives for a given choice of {n} should be sufficient information to also determine what answers the adversary would also have given for {n+1}. The space in which your answers reside in will eventually be the space {X} in the quadruplet {(X,T,c,x_0)}, with {T^n x_0} corresponding to the answers in that space that the adversary gives for a given choice of {n}; the observable {c} is the function that takes the answers given and returns the value of {a_n} that one can deduce from those answers, and the shift map {T} encodes the relationship between the answers given for {n} and the answers given for {n+1}. (One can then often place an invariant measure on {X} by considering (or guessing) the equidistribution properties of the orbit {T^n x_0}, 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 {(a_{n+m})_{m=0}^\infty}, which takes values in the compact space {{\mathcal A}^{\bf N}}; the adversary is forced to supply this information, which gives you everything you need for the problem, namely the value of {a_n} and all subsequent elements {a_{n+1}, a_{n+2}, \ldots} of the sequence, as well as what the adversary would have provided for {n+1} instead of {n}. This corresponds to the universal construction outlined earlier. In the case of a binary alphabet {{\mathcal A}}, one can similarly ask for the real number {\sum_{m=0}^\infty 2^{-m-1} a_{n+m}} in {[0,1]}, which achieves the same goal (at least when the sequence {(a_n)_{n=0}^\infty} does not end in an infinite string of {1}s). (One could also ask the adversary for {n} as embedded in a compactification of the natural numbers, such as the Stone-Cech compactification {\beta {\bf N}}, 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 {(a_n)_{n=0}^\infty}. 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 {1001001\ldots} of the indicator function of the multiples of three, so that {a_n} equals {1} when {n} is a multiple of three and {a_n} equals zero otherwise. Thus, it is natural as a first guess to simply ask the adversary if {n} is a multiple of three. But while this question reveals to you the value of {a_n}, it does not reveal the value of {a_{n+1}}, because being told that {n} is not a multiple of three is insufficient information to determine whether {n+1} is a multiple of three. To put it another way, the information the adversary provided for {n} is not sufficient to determine the information the adversary would have provided for {n+1}. To resolve this, we soon see that we need a bit more information than whether {n} is a multiple of three: we need the residue class {n \hbox{ mod } 3} of {n} modulo three, and this is enough information both to work out {a_n}, and to work out what the adversary would say for {n+1} (since the residue class {n+1 \hbox{ mod } 3} is simply the increment of the residue class {n \hbox{ mod } 3}), which upon iteration then provides the value of {a_{n+1}}, {a_{n+2}}, etc. This gives the dynamical system described in Example 1.

Now let us consider another example. Let {\alpha} be a real number that is already known to you (e.g. one can take {\alpha=\sqrt{2}}, for sake of concreteness), and consider the sequence {(\sin(2 \pi n \alpha))_{n=0}^\infty}, taking values in the interval {{\mathcal A}=[-1,1]}. As before, the first naive guess here would be to simply ask the adversary for the value of {a_n := \sin(2 \pi n \alpha)}, which of course will tell you what {a_n} is, but does not quite reveal the value of {a_{n+1}}. Indeed, the sine addition law gives

\displaystyle a_{n+1} = \sin(2\pi(n+1)\alpha) = \sin(2\pi n \alpha) \cos(\alpha) + \cos(2\pi n \alpha) \sin(\alpha) \ \ \ \ \ (1)

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

\displaystyle \cos(2\pi(n+1)\alpha) = \cos(2\pi n\alpha) \cos(\alpha) - \sin(2\pi n \alpha) \sin(\alpha).

Using the usual identification of the unit circle with {{\bf R}/{\bf Z}}, one can reformulate this in a more modern fashion by simply asking the adversary for the value of {\alpha n \hbox{ mod } {\bf Z}} in the unit circle {{\bf R}/{\bf Z}}, as this determines {\sin(2\pi n \alpha)} and can be updated using the shift map {T: x \mapsto x+\alpha} on {{\bf R}/{\bf Z}}. This interprets the sequence {(\sin(2 \pi n \alpha))_{n=0}^\infty} in terms of the circle shift dynamical system, in which {X = {\bf R}/{\bf Z}} and {Tx := x+\alpha}; the observable in this case is {c(x) := \sin(2\pi x)} and the initial datum is {x_0=0}.

Now consider the sequence {(\sin(2\pi n\alpha) + \sin(2\pi n\beta))_{n=0}^\infty} taking values now in {[-2,2]}, where {\alpha,\beta} are two given real numbers (e.g. {\alpha=\sqrt{2}} and {\beta = \sqrt{3}}). 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 {\alpha n \hbox{ mod } {\bf Z}} and {\beta n \hbox{ mod } {\bf Z}}, as these two pieces of information both determine the current member {a_n = \sin(2\pi n\alpha) + \sin(2\pi n\beta)} of the sequence, and can also be updated easily as one moves from {n} to {n+1}. This interprets the given sequence in terms of the {2}-torus shift in which {X = ({\bf R}/{\bf Z})^2}, {T(x,y) := (x+\alpha,y+\beta)}, {c(x,y) := \sin(2\pi x) + \sin(2\pi y)}, and {x_0 := (0,0)}. More generally, any quasiperiodic sequence {(F(( \alpha_k n \hbox{ mod } 1)_{k=1}^d))_{n=0}^\infty} can be interpreted in terms of a shift map on a {d}-torus.

Next, we consider the quadratic phase sequence {(\sin(2\pi n^2 \alpha))_{n=0}^\infty}. Based on previous experience, we can query the adversary for {n^2 \alpha \hbox{ mod } {\bf Z}}, but this is not sufficient by itself, because we cannot update this information into {(n+1)^2 \alpha \hbox{ mod } {\bf Z}} without additional input. However, since

\displaystyle (n+1)^2 \alpha \hbox{ mod } {\bf Z} = n^2 \alpha \hbox{ mod } {\bf Z} + 2 n \alpha \hbox{ mod } {\bf Z} + \alpha \hbox{ mod } {\bf Z},

we can attempt to fix this by also querying the adversary about {n \alpha \hbox{ mod } {\bf Z}} (one could also use {2n\alpha \hbox{ mod } {\bf Z}} here if desired). Note that {n \alpha \hbox{ mod } {\bf Z}} can itself be updated easily through the identity

\displaystyle (n+1) \alpha \hbox{ mod } {\bf Z} = n \alpha \hbox{ mod } {\bf Z} + \alpha \hbox{ mod } {\bf Z}.

By using the combination of these two queries, we represent the above quadratic phase sequence in terms of the skew shift system in which {X = ({\bf R}/{\bf Z}) \times ({\bf R}/{\bf Z})}, {T(x,y) := (x+\alpha, y + 2x + \alpha)}, {c(x,y) := \sin(2\pi y)}, and {x_0 := (0,0)}. Similarly for polynomial phase sequences, in which one replaces {n^2 \alpha} by some other polynomial of {n} with real coefficients.

Now we turn to the example {(\sin( 2\pi \lfloor n \alpha \rfloor \beta))_{n=0}^\infty}, where {\alpha,\beta} are real numbers and {\lfloor x \rfloor} is the greatest integer less than or equal to {x}. As before, we begin by querying the adversary for {\lfloor n \alpha \rfloor \beta \hbox{ mod } {\bf Z}}, but are then faced with the question of how to update this information when moving from {n} to {n+1}, that is to say we need a way to determine

\displaystyle \lfloor (n+1) \alpha \rfloor \beta \hbox{ mod } {\bf Z}

in terms of queried data. The problem here is that {\lfloor (n+1)\alpha \rfloor} could either equal {\lfloor n\alpha \rfloor + \lfloor \alpha \rfloor} or {\lfloor n\alpha \rfloor + \lfloor \alpha \rfloor + 1}. But one can determine which of these is the case by querying for the fractional part {\{n\alpha\}} of {n\alpha}, or equivalently by querying for {n\alpha \mod 1}. Indeed, we see that

\displaystyle \lfloor (n+1)\alpha \rfloor = \lfloor n \alpha \rfloor + \lfloor \alpha \rfloor

if {\{n \alpha\} + \{ \alpha\} < 1}, and

\displaystyle \lfloor (n+1)\alpha \rfloor = \lfloor n \alpha \rfloor + \lfloor \alpha \rfloor+1

otherwise. This leads to the dynamical system {X = {\bf R}/{\bf Z} \times {\bf R}/{\bf Z}} whose shift map is given by setting

\displaystyle T(x,y) := (x+\alpha, y + \lfloor \alpha \rfloor \beta )

when {\{x\} + \{\alpha\} < 1}, and

\displaystyle T(x,y) := (x+\alpha, y + \lfloor \alpha \rfloor \beta + 1)

otherwise, with the observable {c(x,y) := \sin(2\pi y)} and initial datum {x_0 := (0,0)}. This is not the only way to represent this sequence by a dynamical system, of course; if one observes that

\displaystyle 2\pi \lfloor n \alpha \rfloor \beta = 2 \pi n \alpha \beta - 2 \pi \{ n \alpha \} \beta

then one can alternately proceed by querying for {n \alpha \beta \hbox{ mod } {\bf Z}} and {n \alpha \hbox{ mod } {\bf Z}}, leading to a {2}-torus system with {X = {\bf R}/{\bf Z} \times {\bf R}/{\bf Z}}, {T(x,y) := (x+\alpha, y+\alpha\beta)}, {c(x,y) := \sin(2\pi (y - \{x\} \beta)}, and {x_0 := (0,0)}. 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 {(\sin( 2\pi \lfloor n \alpha \rfloor n \beta))_{n=0}^\infty}. Starting with a query to {\lfloor n \alpha \rfloor n \beta \hbox{ mod } {\bf Z}}, one soon realises that to update this piece of information, one also needs access to {n\alpha \hbox{ mod } {\bf Z}} and to {n \beta \hbox{ mod } {\bf Z}}. This gives rise to a mildly complicated system on a {3}-torus {({\bf R}/{\bf Z})^3} (or, alternatively, a cube {[0,1)^3}) that tracks the fractional parts of {n\alpha}, {n\beta}, and {\lfloor n \alpha \rfloor n \beta}, with a piecewise polynomial shift function {T}, 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 {x \mapsto gx} on the Heisenberg nilmanifold

\displaystyle \begin{pmatrix} 1 & {\bf R} & {\bf R} \\ 0 & 1 & {\bf R} \\ 0 & 0 & 1 \end{pmatrix} / \begin{pmatrix} 1 & {\bf Z} & {\bf Z} \\ 0 & 1 & {\bf Z} \\ 0 & 0 & 1 \end{pmatrix},

at the cost of turning the observable {c} 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 {n} (which means that, like {n \mapsto \lfloor n\alpha \rfloor n \beta}, they are formed out of {n} and some real constants using the ring operations {+,\times} and the floor function {\lfloor\rfloor} 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 {o(n)} queries in order to predict the behaviour of the sequence for the next {n} 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 {314159\ldots} arising from the digits of {\pi} in base {10}, so that the alphabet here is {\{0,\ldots,9\}}. The problem here is that knowledge of the {n^{th}} digit of {\pi} tells us virtually nothing useful about the {(n+1)^{st}} digit, and there is no obvious set of queries (other than that of asking for basically the entire string of digits after tne {n^{th}} digit) that would let one perform an update from {n} to {n+1}. Thus, one is basically left with universal constructions, e.g. taking {X} to be the interval {[0,10)}, letting {T} be the shift map {Tx := (10x \% 10)} (i.e. {Tx} is the remainder of {10x} when divided by {10}), with observable {c(x) := \lfloor x \rfloor} and initial datum {x_0:=\pi}. It is widely expected that {\pi} is a “generic” point of this system, which is equivalent to the notoriously difficult conjecture that {\pi} is a normal number in base {10} (of course, {\pi} 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 {\pi} in any way. One can try to use various explicit identities involving {\pi} to hope to get a more useful dynamical system to model {\pi}, 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 {16} digits of {\pi}, but the resulting dynamical system obtained is quite complicated.)

Now we turn to the sequence {0, 1, -1, -1, 0, -1, 1, \ldots} coming from the Möbius function {\mu(n)} (where we adopt for sake of discussion the convention that {\mu(0)=0}). 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

\displaystyle \mu(n) = \mu^2(n) \times \lambda(n)

of the Möbius function into the unsigned part {0,1,1,1,0,1,1,\ldots} of the Möbius function (which is {1} when {n} is square-free, and {0} otherwise), and the Liouville function {\lambda}, which takes values in {\{-1,+1\}} (assigning {\lambda(0)=1}, say, for sake of discussion). Like the digits of {\pi}, 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 {\{-1,+1\}^{\bf N}}). But the unsigned part {\mu^2(n)} is significantly more regular. Indeed, much as the indicator function {1001001\ldots} of the multiples of three can be understood through the querying of {n \hbox{ mod } 3}, {\mu^2(n)} can be obtained after querying {n \hbox{ mod } p^2} for all primes {p}, since {\mu^2(n)} is {1} precisely when all of these residue classes are non-zero. As each of these residue classes are easily updated when we increment {n} to {n+1}, we see that {\mu^2(n)} can be modeled by the dynamical system with {X = \prod_p ({\bf Z}/p^2 {\bf Z})} with {T} being the shift

\displaystyle T x = x + (1)_{p \hbox{ prime}}

and {c: X \rightarrow \{0,1\}} being the observable that sets {c(a_p)_{p \hbox{ prime}}} to equal {1} when the residue classes {a_p} are all non-zero and {0} otherwise, with initial datum {x_0 := (0)_{p \hbox{ prime}}}. 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 {\mu} to place on this system is the Haar measure on {\prod_p ({\bf Z}/p^2 {\bf Z})}, that is to say the product of the uniform probability measures on each of the {{\bf Z}/p^2{\bf Z}}. Using this measure, one can show using Fourier analysis that the shift map {T} is uniquely ergodic, and that {c} is an indicator function of a compact set of measure

\displaystyle \prod_p (1 - \frac{1}{p^2}) = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}.

Among other things, this shows that the square-free numbers have asymptotic density {\frac{6}{\pi^2}}. 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 {\pi}. 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.