Thedyadic transformation (also known as thedyadic map,bit shift map,2x mod 1 map,Bernoulli map,doubling map orsawtooth map^[1][2]) is themapping (i.e.,recurrence relation)

${\displaystyle T:[0,1)\to [0,1{)}^{\mathrm{\infty }}}$

${\displaystyle x\mapsto (x_0,x_1,x_2,\dots )}$

(where${\displaystyle [0,1{)}^{\mathrm{\infty }}}$ is the set ofsequences from${\displaystyle [0,1)}$) produced by the rule

${\displaystyle x_0=x}$

${\displaystyle \text{for all }n\ge 0,x_{n+1}=(2x_n)mod1}$.^[3]

Equivalently, the dyadic transformation can also be defined as theiterated function map of thepiecewise linear function

The namebit shift map arises because, if the value of an iterate is written inbinary notation, the next iterate is obtained by shifting the binary point one bit to the right, and if the bit to the left of the new binary point is a "one", replacing it with a zero.

The dyadic transformation provides an example of how a simple 1-dimensional map can give rise tochaos. This map readily generalizes to several others. An important one is thebeta transformation, defined as${\displaystyle T_{\beta }(x)=\beta xmod1}$. This map has been extensively studied by many authors. It was introduced byAlfréd Rényi in 1957, and an invariant measure for it was given byAlexander Gelfond in 1959 and again independently byBill Parry in 1960.^[4][5][6]

The map can be obtained as ahomomorphism on theBernoulli process. Let${\displaystyle \mathrm{\Omega }=\{H,T{\}}^{\mathbb{N}}}$ be the set of all semi-infinite strings of the letters${\displaystyle H}$ and${\displaystyle T}$. These can be understood to be the flips of a coin, coming up heads or tails. Equivalently, one can write${\displaystyle \mathrm{\Omega }=\{0,1{\}}^{\mathbb{N}}}$ the space of all (semi-)infinite strings of binary bits. The word "infinite" is qualified with "semi-", as one can also define a different space${\displaystyle \{0,1{\}}^{\mathbb{Z}}}$ consisting of all doubly-infinite (double-ended) strings; this will lead to theBaker's map. The qualification "semi-" is dropped below.

This space has a naturalshift operation, given by

${\displaystyle T(b_0,b_1,b_2,\dots )=(b_1,b_2,\dots )}$

where${\displaystyle (b_0,b_1,\dots )}$ is an infinite string of binary digits. Given such a string, write

${\displaystyle x=\sum _{n=0}^{\mathrm{\infty }}\frac{b_n}{2^{n+1}}.}$

The resulting${\displaystyle x}$ is areal number in theunit interval${\displaystyle 0\le x\le 1.}$ The shift${\displaystyle T}$ induces ahomomorphism, also called${\displaystyle T}$, on the unit interval. Since${\displaystyle T(b_0,b_1,b_2,\dots )=(b_1,b_2,\dots ),}$ one can easily see that${\displaystyle T(x)=2xmod1.}$ For the doubly-infinite sequence of bits${\displaystyle \mathrm{\Omega }=2^{\mathbb{Z}},}$ the induced homomorphism is theBaker's map.

The dyadic sequence is then just the sequence

${\displaystyle (x,T(x),T^2(x),T^3(x),\dots )}$

That is,${\displaystyle x_n=T^n(x).}$

Note that the sum

${\displaystyle y=\sum _{n=0}^{\mathrm{\infty }}\frac{b_n}{3^{n+1}}}$

gives theCantor function, as conventionally defined. This is one reason why the set${\displaystyle \{H,T{\}}^{\mathbb{N}}}$ is sometimes called theCantor set.

One hallmark of chaotic dynamics is the loss of information as simulation occurs. If we start with information on the firsts bits of the initial iterate, then afterm simulated iterations (m < s) we only haves − m bits of information remaining. Thus we lose information at the exponential rate of one bit per iteration. Afters iterations, our simulation has reached the fixed point zero, regardless of the true iterate values; thus we have suffered a complete loss of information. This illustrates sensitive dependence on initial conditions—the mapping from the truncated initial condition has deviated exponentially from the mapping from the true initial condition. And since our simulation has reached a fixed point, for almost all initial conditions it will not describe the dynamics in the qualitatively correct way as chaotic.

Equivalent to the concept of information loss is the concept of information gain. In practice some real-world process may generate a sequence of values (x_n) over time, but we may only be able to observe these values in truncated form. Suppose for example thatx₀ = 0.1001101, but we only observe the truncated value 0.1001. Our prediction forx₁ is 0.001. If we wait until the real-world process has generated the truex₁ value 0.001101, we will be able to observe the truncated value 0.0011, which is more accurate than our predicted value 0.001. So we have received an information gain of one bit.

The dyadic transformation istopologically semi-conjugate to the unit-heighttent map. Recall that the unit-height tent map is given by

The conjugacy is explicitly given by

${\displaystyle S(x)=\sin \pi x}$

so that

${\displaystyle f_1=S^{-1}\circ T\circ S}$

That is,${\displaystyle f_1(x)=S^{-1}(T(S(x))).}$ This is stable under iteration, as

${\displaystyle f_1^n=f_1\circ \cdots \circ f_1=S^{-1}\circ T\circ S\circ S^{-1}\circ \cdots \circ T\circ S=S^{-1}\circ T^n\circ S}$

It is also conjugate to the chaoticr = 4 case of thelogistic map. Ther = 4 case of the logistic map is${\displaystyle z_{n+1}=4z_n(1-z_n)}$; this is related to thebit shift map in variablex by

${\displaystyle z_n={\sin }^2(2\pi x_n).}$

There is also a semi-conjugacy between the dyadic transformation (here named angle doubling map) and thequadratic polynomial. Here, the map doubles angles measured inturns. That is, the map is given by

${\displaystyle \theta \mapsto 2\theta mod2\pi .}$

Because of the simple nature of the dynamics when the iterates are viewed in binary notation, it is easy to categorize the dynamics based on the initial condition:

If the initial condition isirrational (asalmost all points in the unit interval are), then the dynamics are non-periodic—this follows directly from the definition of an irrational number as one with a non-repeating binary expansion. This is the chaotic case.

Ifx₀ isrational the image ofx₀ contains a finite number of distinct values within [0, 1) and theforward orbit ofx₀ is eventually periodic, with period equal to the period of thebinary expansion ofx₀. Specifically, if the initial condition is a rational number with a finite binary expansion ofk bits, then afterk iterations the iterates reach the fixed point 0;if the initial condition is a rational number with ak-bit transient (k ≥ 0) followed by aq-bit sequence (q > 1) that repeats itself infinitely, then afterk iterations the iterates reach a cycle of length q. Thus cycles of all lengths are possible.

For example, the forward orbit of 11/24 is:

${\displaystyle \frac{11}{24}\mapsto \frac{11}{12}\mapsto \frac{5}{6}\mapsto \frac{2}{3}\mapsto \frac{1}{3}\mapsto \frac{2}{3}\mapsto \frac{1}{3}\mapsto \cdots ,}$

which has reached a cycle of period 2. Within any subinterval of [0, 1), no matter how small, there are therefore an infinite number of points whose orbits are eventually periodic, and an infinite number of points whose orbits are never periodic. This sensitive dependence on initial conditions is a characteristic ofchaotic maps.

The periodic and non-periodic orbits can be more easily understood not by working with the map${\displaystyle T(x)=2xmod1}$ directly, but rather with thebit shift map${\displaystyle T(b_0,b_1,b_2,\dots )=(b_1,b_2,\dots )}$ defined on theCantor space${\displaystyle \mathrm{\Omega }=\{0,1{\}}^{\mathbb{N}}}$.

That is, thehomomorphism

${\displaystyle x=\sum _{n=0}^{\mathrm{\infty }}\frac{b_n}{2^{n+1}}}$

is basically a statement that the Cantor set can be mapped into the reals. It is asurjection: everydyadic rational has not one, but two distinct representations in the Cantor set. For example,

${\displaystyle 0.1000000\cdots =0.011111\dots }$

This is just the binary-string version of the famous0.999... = 1 problem. The doubled representations hold in general: for any given finite-length initial sequence${\displaystyle b_0,b_1,b_2,\dots ,b_{k-1}}$ of length${\displaystyle k}$, one has

${\displaystyle b_0,b_1,b_2,\dots ,b_{k-1},1,0,0,0,\cdots =b_0,b_1,b_2,\dots ,b_{k-1},0,1,1,1,\dots }$

The initial sequence${\displaystyle b_0,b_1,b_2,\dots ,b_{k-1}}$ corresponds to the non-periodic part of the orbit, after which iteration settles down to all zeros (equivalently, all-ones).

Expressed as bit strings, the periodic orbits of the map can be seen to the rationals. That is, after an initial "chaotic" sequence of${\displaystyle b_0,b_1,b_2,\dots ,b_{k-1}}$, a periodic orbit settles down into a repeating string${\displaystyle b_k,b_{k+1},b_{k+2},\dots ,b_{k+m-1}}$ of length${\displaystyle m}$. It is not hard to see that such repeating sequences correspond to rational numbers. Writing

${\displaystyle y=\sum _{j=0}^{m-1}{b}_{k+j}{2}^{-j-1}}$

one then clearly has

${\displaystyle \sum _{j=0}^{\mathrm{\infty }}{b}_{k+j}{2}^{-j-1}=y\sum _{j=0}^{\mathrm{\infty }}{2}^{-jm}=\frac{y}{1-2^{-m}}}$

Tacking on the initial non-repeating sequence, one clearly has a rational number. In fact,every rational number can be expressed in this way: an initial "random" sequence, followed by a cycling repeat. That is, the periodic orbits of the map are in one-to-one correspondence with the rationals.

This phenomenon is note-worthy, because something similar happens in many chaotic systems. For example,geodesics oncompactmanifolds can have periodic orbits that behave in this way.

Keep in mind, however, that the rationals are a set ofmeasure zero in the reals.Almost all orbits arenot periodic! The aperiodic orbits correspond to the irrational numbers. This property also holds true in a more general setting. An open question is to what degree the behavior of the periodic orbits constrain the behavior of the system as a whole. Phenomena such asArnold diffusion suggest that the general answer is "not very much".

Instead of looking at the orbits of individual points under the action of the map, it is equally worthwhile to explore how the map affects densities on the unit interval. That is, imagine sprinkling some dust on the unit interval; it is denser in some places than in others. What happens to this density as one iterates?

Write${\displaystyle \rho :[0,1]\to \mathbb{R}}$ as this density, so that${\displaystyle x\mapsto \rho (x)}$. To obtain the action of${\displaystyle T}$ on this density, one needs to find all points${\displaystyle y=T^{-1}(x)}$ and write^[7]

${\displaystyle \rho (x)\mapsto \sum _{y=T^{-1}(x)}\frac{\rho (y)}{|T^{\mathrm{\prime }}(y)|}}$

The denominator in the above is theJacobian determinant of the transformation, here it is just thederivative of${\displaystyle T}$ and so${\displaystyle T^{\mathrm{\prime }}(y)=2}$. Also, there are obviously only two points in the preimage of${\displaystyle T^{-1}(x)}$, these are${\displaystyle y=x/2}$ and${\displaystyle y=(x+1)/2.}$ Putting it all together, one gets

${\displaystyle \rho (x)\mapsto \frac{1}{2}\rho \left(\frac{x}{2}\right)+\frac{1}{2}\rho \left(\frac{x+1}{2}\right)}$

By convention, such maps are denoted by${\displaystyle \mathcal{L}}$ so that in this case, write

${\displaystyle \left[{\mathcal{L}}_T\rho \right](x)=\frac{1}{2}\rho \left(\frac{x}{2}\right)+\frac{1}{2}\rho \left(\frac{x+1}{2}\right)}$

The map${\displaystyle {\mathcal{L}}_T}$ is alinear operator, as one easily sees that${\displaystyle {\mathcal{L}}_T(f+g)={\mathcal{L}}_T(f)+{\mathcal{L}}_T(g)}$ and${\displaystyle {\mathcal{L}}_T(af)=a{\mathcal{L}}_T(f)}$ for all functions${\displaystyle f,g}$ on the unit interval, and all constants${\displaystyle a}$.

Viewed as a linear operator, the most obvious and pressing question is: what is itsspectrum? Oneeigenvalue is obvious: if${\displaystyle \rho (x)=1}$ for all${\displaystyle x}$ then one obviously has${\displaystyle {\mathcal{L}}_T\rho =\rho }$ so the uniform density is invariant under the transformation. This is in fact the largest eigenvalue of the operator${\displaystyle {\mathcal{L}}_T}$, it is theFrobenius–Perron eigenvalue. The uniform density is, in fact, nothing other than theinvariant measure of the dyadic transformation.

To explore the spectrum of${\displaystyle {\mathcal{L}}_T}$ in greater detail, one must first limit oneself to a suitablespace of functions (on the unit interval) to work with. This might be the space ofLebesgue measurable functions, or perhaps the space ofsquare integrable functions, or perhaps even justpolynomials. Working with any of these spaces is surprisingly difficult, although a spectrum can be obtained.^[7]

A vast amount of simplification results if one instead works with theCantor space${\displaystyle \mathrm{\Omega }=\{0,1{\}}^{\mathbb{N}}}$, and functions${\displaystyle \rho :\mathrm{\Omega }\to \mathbb{R}.}$ Some caution is advised, as the map${\displaystyle T(x)=2xmod1}$ is defined on theunit interval of thereal number line, assuming thenatural topology on the reals. By contrast, the map${\displaystyle T(b_0,b_1,b_2,\dots )=(b_1,b_2,\dots )}$ is defined on theCantor space${\displaystyle \mathrm{\Omega }=\{0,1{\}}^{\mathbb{N}}}$, which by convention is given a very differenttopology, theproduct topology. There is a potential clash of topologies; some care must be taken. However, as presented above, there is a homomorphism from the Cantor set into the reals; fortunately, it mapsopen sets into open sets, and thus preserves notions ofcontinuity.

To work with the Cantor set${\displaystyle \mathrm{\Omega }=\{0,1{\}}^{\mathbb{N}}}$, one must provide a topology for it; by convention, this is theproduct topology. By adjoining set-complements, it can be extended to aBorel space, that is, asigma algebra. The topology is that ofcylinder sets. A cylinder set has the generic form

${\displaystyle (\ast ,\ast ,\ast ,\dots ,\ast ,b_k,b_{k+1},\ast ,\dots ,\ast ,b_m,\ast ,\dots )}$

where the${\displaystyle \ast }$ are arbitrary bit values (not necessarily all the same), and the${\displaystyle b_k,b_m,\dots }$ are a finite number of specific bit-values scattered in the infinite bit-string. These are the open sets of the topology. The canonical measure on this space is theBernoulli measure for the fair coin-toss. If there is just one bit specified in the string of arbitrary positions, the measure is 1/2. If there are two bits specified, the measure is 1/4, and so on. One can get fancier: given a real number one can define a measure

${\displaystyle {\mu }_p(\ast ,\dots ,\ast ,b_k,\ast ,\dots )=p^n(1-p{)}^m}$

if there are${\displaystyle n}$ heads and${\displaystyle m}$ tails in the sequence. The measure with${\displaystyle p=1/2}$ is preferred, since it is preserved by the map

${\displaystyle (b_0,b_1,b_2,\dots )\mapsto x=\sum _{n=0}^{\mathrm{\infty }}\frac{b_n}{2^{n+1}}.}$

So, for example,${\displaystyle (0,\ast ,\cdots )}$ maps to theinterval${\displaystyle [0,1/2]}$ and${\displaystyle (1,\ast ,\dots )}$ maps to the interval${\displaystyle [1/2,1]}$ and both of these intervals have a measure of 1/2. Similarly,${\displaystyle (\ast ,0,\ast ,\dots )}$ maps to the interval${\displaystyle [0,1/4]\cup [1/2,3/4]}$ which still has the measure 1/2. That is, the embedding above preserves the measure.

An alternative is to write

${\displaystyle (b_0,b_1,b_2,\dots )\mapsto x=\sum _{n=0}^{\mathrm{\infty }}\left[b_n{p}^{n+1}+(1-b_n)(1-p{)}^{n+1}\right]}$

which preserves the measure${\displaystyle {\mu }_p.}$ That is, it maps such that the measure on the unit interval is again the Lebesgue measure.

Denote the collection of all open sets on the Cantor set by${\displaystyle \mathcal{B}}$ and consider the set${\displaystyle \mathcal{F}}$ of all arbitrary functions${\displaystyle f:\mathcal{B}\to \mathbb{R}.}$ The shift${\displaystyle T}$ induces apushforward

${\displaystyle f\circ T^{-1}}$

defined by${\displaystyle \left(f\circ T^{-1}\right)(x)=f(T^{-1}(x)).}$ This is again some function${\displaystyle \mathcal{B}\to \mathbb{R}.}$ In this way, the map${\displaystyle T}$ induces another map${\displaystyle {\mathcal{L}}_T}$ on the space of all functions${\displaystyle \mathcal{B}\to \mathbb{R}.}$ That is, given some${\displaystyle f:\mathcal{B}\to \mathbb{R}}$, one defines

${\displaystyle {\mathcal{L}}_{T}f=f\circ T^{-1}}$

This linear operator is called thetransfer operator or theRuelle–Frobenius–Perron operator. The largest eigenvalue is theFrobenius–Perron eigenvalue, and in this case, it is 1. The associatedeigenvector is the invariant measure: in this case, it is theBernoulli measure. Again,${\displaystyle {\mathcal{L}}_T(\rho )=\rho }$ when${\displaystyle \rho (x)=1.}$

To obtain the spectrum of${\displaystyle {\mathcal{L}}_T}$, one must provide a suitable set ofbasis functions for the space${\displaystyle \mathcal{F}.}$ One such choice is to restrict${\displaystyle \mathcal{F}}$ to the set of all polynomials. In this case, the operator has adiscrete spectrum, and theeigenfunctions are (curiously) theBernoulli polynomials!^[8] (This coincidence of naming was presumably not known to Bernoulli.)

Indeed, one can easily verify that

${\displaystyle {\mathcal{L}}_T{B}_n=2^{-n}{B}_n}$

where the${\displaystyle B_n}$ are theBernoulli polynomials. This follows because the Bernoulli polynomials obey the identity

${\displaystyle \frac{1}{2}{B}_n\left(\frac{y}{2}\right)+\frac{1}{2}{B}_n\left(\frac{y+1}{2}\right)=2^{-n}{B}_n(y)}$

Note that${\displaystyle B_0(x)=1.}$

Another basis is provided by theHaar basis, and the functions spanning the space are theHaar wavelets. In this case, one finds acontinuous spectrum, consisting of the unit disk on thecomplex plane. Given${\displaystyle z\in \mathbb{C}}$ in the unit disk, so that, the functions

${\displaystyle {\psi }_{z,k}(x)=\sum _{n=1}^{\mathrm{\infty }}{z}^n\exp i\pi (2k+1)2^{n}x}$

obey

${\displaystyle {\mathcal{L}}_T{\psi }_{z,k}=z{\psi }_{z,k}}$

for${\displaystyle k\in \mathbb{Z}.}$ This is a complete basis, in that everyinteger can be written in the form${\displaystyle (2k+1)2^n.}$ The Bernoulli polynomials are recovered by setting${\displaystyle k=0}$ and${\displaystyle z=\frac{1}{2},\frac{1}{4},\dots }$

A complete basis can be given in other ways, as well; they may be written in terms of theHurwitz zeta function. Another complete basis is provided by theTakagi function. This is a fractal,differentiable-nowhere function. The eigenfunctions are explicitly of the form

${\displaystyle {\text{blanc}}_{w,k}(x)=\sum _{n=0}^{\mathrm{\infty }}{w}^{n}s((2k+1)2^{n}x)}$

where${\displaystyle s(x)}$ is thetriangle wave. One has, again,

${\displaystyle {\mathcal{L}}_T{\text{blanc}}_{w,k}=w{\text{blanc}}_{w,k}.}$

All of these different bases can be expressed as linear combinations of one-another. In this sense, they are equivalent.

The fractal eigenfunctions show an explicit symmetry under the fractalgroupoid of themodular group; this is developed in greater detail in the article on theTakagi function (the blancmange curve). Perhaps not a surprise; the Cantor set has exactly the same set of symmetries (as do thecontinued fractions.) This then leads elegantly into the theory ofelliptic equations andmodular forms.

The Hamiltonian of the zero-field one-dimensionalIsing model of${\displaystyle 2N}$ spins with periodic boundary conditions can be written as

${\displaystyle H(\sigma )=g\sum _{i\in {\mathbb{Z}}_{2N}}{\sigma }_i{\sigma }_{i+1}.}$

Letting${\displaystyle C}$ be a suitably chosen normalization constant and${\displaystyle \beta }$ be the inverse temperature for the system, the partition function for this model is given by

${\displaystyle Z=\sum _{\{{\sigma }_i=\pm 1,i\in {\mathbb{Z}}_{2N}\}}\prod _{i\in {\mathbb{Z}}_{2N}}C{e}^{-\beta g{\sigma }_i{\sigma }_{i+1}}.}$

We can implement therenormalization group by integrating out every other spin. In so doing, one finds that${\displaystyle Z}$ can also be equated with the partition function for a smaller system with but${\displaystyle N}$ spins,

${\displaystyle Z=\sum _{\{{\sigma }_i=\pm 1,i\in {\mathbb{Z}}_N\}}\prod _{i\in {\mathbb{Z}}_N}\mathcal{R}[C]e^{-\mathcal{R}[\beta g]{\sigma }_i{\sigma }_{i+1}},}$

provided we replace${\displaystyle C}$ and${\displaystyle \beta g}$ with renormalized values${\displaystyle \mathcal{R}[C]}$ and${\displaystyle \mathcal{R}[\beta g]}$ satisfying the equations

${\displaystyle \mathcal{R}[C{]}^2=4\cosh (2\beta g)C^4,}$

${\displaystyle e^{-2\mathcal{R}[\beta g]}=\cosh (2\beta g).}$

Suppose now that we allow${\displaystyle \beta g}$ to be complex and that${\displaystyle \mathrm{Im}[2\beta g]=\frac{\pi }{2}+\pi n}$ for some${\displaystyle n\in \mathbb{Z}}$. In that case we can introduce a parameter${\displaystyle t\in [0,1)}$ related to${\displaystyle \beta g}$ via the equation

${\displaystyle e^{-2\beta g}=i\tan (\pi (t-\frac{1}{2})),}$

and the resulting renormalization group transformation for${\displaystyle t}$ will be precisely the dyadic map:^[9]

${\displaystyle \mathcal{R}[t]=2tmod1.}$

• Bernoulli process
• Bernoulli scheme
• Gilbert–Shannon–Reeds model, a random distribution on permutations given by applying the doubling map to a set ofn uniformly random points on the unit interval

• Chaotic maps

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata