Editing Dyadic transformation (section)

==Density formulation==
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 <math>\rho:[0,1]\to\mathbb{R}</math> as this density, so that <math>x\mapsto\rho(x)</math>. To obtain the action of <math>T</math> on this density, one needs to find all points <math>y=T^{-1}(x)</math> and write<ref name="driebe">
Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands {{ISBN|0-7923-5564-4}}
</ref>  
:<math>\rho(x) \mapsto \sum_{y=T^{-1}(x)} \frac{\rho(y)}{|T^\prime(y)|}</math>
The denominator in the above is the [[Jacobian matrix and determinant|Jacobian determinant]] of the transformation, here it is just the [[derivative]] of <math>T</math> and so <math>T^\prime(y)=2</math>. Also, there are obviously only two points in the preimage of <math>T^{-1}(x)</math>, these are <math>y=x/2</math> and <math>y=(x+1)/2.</math> Putting it all together, one gets
 
:<math>\rho(x) \mapsto \frac{1}{2}\rho\!\left(\frac{x}{2}\right) + \frac{1}{2}\rho\!\left(\frac{x+1}{2}\right)</math>

By convention, such maps are denoted by <math>\mathcal{L}</math> so that in this case, write
:<math>\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)</math>
The map <math>\mathcal{L}_T</math> is a [[linear operator]], as one easily sees that <math>\mathcal{L}_T(f+g)= \mathcal{L}_T(f) + \mathcal{L}_T(g)</math> and <math>\mathcal{L}_T(af)= a\mathcal{L}_T(f)</math> for all functions <math>f,g</math> on the unit interval, and all constants <math>a</math>.

Viewed as a linear operator, the most obvious and pressing question is: what is its [[spectrum of a  matrix|spectrum]]? One [[eigenvalue]] is obvious: if <math>\rho(x)=1</math> for all <math>x</math> then one obviously has <math>\mathcal{L}_T\rho=\rho</math> so the uniform density is invariant under the transformation. This is in fact the largest eigenvalue of the operator <math>\mathcal{L}_T</math>, it is the [[Frobenius–Perron theorem|Frobenius–Perron eigenvalue]]. The uniform density is, in fact, nothing other than the [[invariant measure]] of the dyadic transformation.

To explore the spectrum of <math>\mathcal{L}_T</math> in greater detail, one must first limit oneself to a suitable [[function space|space of functions]] (on the unit interval) to work with. This might be the space of [[Lebesgue measure|Lebesgue measurable functions]], or perhaps the space of [[square integrable]] functions, or perhaps even just [[polynomial]]s. Working with any of these spaces is surprisingly difficult, although a spectrum can be obtained.<ref name="driebe"/>

===Borel space===
A vast amount of simplification results if one instead works with the [[Cantor space]] <math>\Omega=\{0,1\}^\mathbb{N}</math>, and functions <math>\rho:\Omega\to\mathbb{R}.</math> Some caution is advised, as the map <math>T(x)=2x\bmod 1</math> is defined on the [[unit interval]] of the [[real number line]], assuming the [[natural topology]] on the reals.  By contrast, the map <math>T(b_0, b_1, b_2, \dots)=(b_1, b_2, \dots)</math> is defined on the [[Cantor space]] <math>\Omega = \{0,1\}^{\mathbb{N}}</math>, which by convention is given a very different [[topological space|topology]], the [[product 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 maps [[open set]]s into open sets, and thus preserves notions of [[continuous function (topology)|continuity]].

To work with the Cantor set <math>\Omega=\{0,1\}^{\mathbb{N}}</math>, one must provide a topology for it; by convention, this is the [[product topology]]. By adjoining set-complements, it can be extended to a [[Measurable space|Borel space]], that is, a [[sigma algebra]]. The topology is that of [[cylinder set]]s. A cylinder set has the generic form
:<math>(*,*,*,\dots,*,b_k,b_{k+1},*,\dots, *,b_m,*,\dots)</math>
where the <math>*</math> are arbitrary bit values (not necessarily all the same), and the <math>b_k, b_m, \dots</math> 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 the [[Bernoulli 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 <math>0 < p < 1</math> one can define a measure
:<math>\mu_p( *,\dots,*,b_k,*,\dots) = p^n(1-p)^m</math>
if there are <math>n</math> heads and <math>m</math> tails in the sequence. The measure with <math>p=1/2</math> is preferred, since it is preserved by the map

:<math>(b_0, b_1, b_2, \dots) \mapsto x = \sum_{n=0}^\infty \frac{b_n}{2^{n+1}}.</math>
So, for example, <math>(0,*,\cdots)</math> maps to the [[interval (mathematics)|interval]] <math>[0,1/2]</math> and <math>(1,*,\dots)</math> maps to the interval <math>[1/2,1]</math> and both of these intervals have a measure of 1/2. Similarly, <math>(*,0,*,\dots)</math> maps to the interval <math>[0,1/4]\cup[1/2,3/4]</math> which still has the measure 1/2. That is, the embedding above preserves the measure.

An alternative is to write
:<math>(b_0, b_1, b_2, \dots) \mapsto x = \sum_{n=0}^\infty \left[b_n p^{n+1} + (1-b_n)(1-p)^{n+1}\right]</math>
which preserves the measure <math>\mu_p.</math> That is, it maps such that the measure on the unit interval is again the Lebesgue measure.

===Frobenius–Perron operator===
Denote the collection of all open sets on the Cantor set by <math>\mathcal{B}</math> and consider the set <math>\mathcal{F}</math> of all arbitrary functions <math>f:\mathcal{B}\to\mathbb{R}.</math> The shift <math>T</math> induces a [[pushforward measure|pushforward]] 
:<math>f\circ T^{-1}</math>
defined by <math>\left(f \circ T^{-1}\right)\!(x) = f(T^{-1}(x)).</math> This is again some function <math>\mathcal{B}\to\mathbb{R}.</math> In this way, the map <math>T</math> induces another map <math>\mathcal{L}_T</math> on the space of all functions <math>\mathcal{B}\to\mathbb{R}.</math> That is, given some <math>f:\mathcal{B}\to\mathbb{R}</math>, one defines
:<math>\mathcal{L}_T f = f \circ T^{-1}</math>
This linear operator is called the [[transfer operator]] or the ''Ruelle–Frobenius–Perron operator''.  The largest eigenvalue is the [[Frobenius–Perron theorem|Frobenius–Perron eigenvalue]], and in this case, it is 1.  The associated [[eigenvector]] is the invariant measure: in this case, it is the [[Bernoulli measure]]. Again, <math>\mathcal{L}_T(\rho)= \rho</math> when <math>\rho(x)=1.</math>

===Spectrum===
To obtain the spectrum of <math>\mathcal{L}_T</math>, one must provide a suitable set of [[basis function]]s for the space <math>\mathcal{F}.</math> One such choice is to restrict <math>\mathcal{F}</math> to the set of all polynomials. In this case, the operator has a [[discrete spectrum]], and the [[eigenfunction]]s are (curiously) the [[Bernoulli polynomial]]s!<ref>Pierre Gaspard, "''r''-adic one-dimensional maps and the Euler summation formula", ''Journal of Physics A'', '''25''' (letter) L483-L485 (1992).</ref> (This coincidence of naming was presumably not known to Bernoulli.)

Indeed, one can easily verify that
:<math>\mathcal{L}_T B_n= 2^{-n}B_n</math>
where the <math>B_n</math> are the [[Bernoulli polynomials]]. This follows because the Bernoulli polynomials obey the identity
:<math>\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)</math>
Note that <math>B_0(x)=1.</math>

Another basis is provided by the [[Haar basis]], and the functions spanning the space are the [[Haar wavelet]]s. In this case, one finds a [[continuous spectrum]], consisting of the unit disk on the [[complex plane]]. Given <math>z\in\mathbb{C}</math> in the unit disk, so that <math>|z|<1</math>, the functions

:<math>\psi_{z,k}(x)=\sum_{n=1}^\infty z^n \exp i\pi(2k+1)2^nx</math>
obey
:<math>\mathcal{L}_T \psi_{z,k}= z\psi_{z,k}</math>
for <math>k\in\mathbb{Z}.</math> This is a complete basis, in that every [[integer]] can be written in the form <math>(2k+1)2^n.</math> The Bernoulli polynomials are recovered by setting <math>k=0</math> and <math>z=\frac{1}{2}, \frac{1}{4}, \dots</math>

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

:<math>\mbox{blanc}_{w,k}(x) = \sum_{n=0}^\infty w^n s((2k+1)2^{n}x)</math>
where <math>s(x)</math> is the [[triangle wave]]. One has, again,
:<math>\mathcal{L}_T \mbox{blanc}_{w,k} = w\;\mbox{blanc}_{w,k}.</math>

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 fractal [[groupoid]] of the [[modular group]]; this is developed in greater detail in the article on the [[Takagi function]] (the blancmange curve). Perhaps not a surprise; the Cantor set has exactly the same set of symmetries (as do the [[continued fraction]]s.) This then leads elegantly into the theory of [[Elliptic partial differential equation|elliptic equation]]s and [[modular form]]s.