# On the Beta Transformation

Linas Vepstas

(December 2017 (Updated Feb 2018 and Dec 2018))

###### Abstract

The beta transformation is the iterated map $\beta x\,\mod 1$. The special
case of $\beta=2$ is known as the Bernoulli map, and is exactly solvable. The
Bernoulli map provides a model for pure, unrestrained chaotic (ergodic)
behavior: it is the full invariant shift on the Cantor space
$\left\\{0,1\right\\}^{\omega}$. The Cantor space consists of infinite strings
of binary digits; it is notable for many properties, including that it can
represent the real number line.

The beta transformation defines a subshift: iterated on the unit interval, it
singles out a subspace of the Cantor space that is invariant under the action
of the left-shift operator. That is, lopping off one bit at a time gives back
the same subspace.

The beta transform seems to capture something basic about the multiplication
of two real numbers: $\beta$ and $x$. It offers insight into the nature of
multiplication. Iterating on multiplication, one would get $\beta^{n}x$ – that
is, exponentiation; the mod 1 of the beta transform contorts this in strange
ways.

Analyzing the beta transform is difficult. The work presented here is more-or-
less a research diary: a pastiche of observations and some shallow insights.
One is that chaos seems to be rooted in how the carry bit behaves during
multiplication. Another is that one can surgically insert “islands of
stability” into chaotic (ergodic) systems, and have some fair amount of
control over how those islands of stability behave. One can have islands with,
or without a period-doubling “route to chaos”.

The eigenvalues of the transfer operator seem to lie on a circle of radius
$1/\beta$ in the complex plane. Given that the transfer operator is purely
real, the appearance of such a quasi-unitary spectrum unexpected. The spectrum
appears to be the limit of a dense set of quasi-cyclotomic polynomials, the
positive real roots of which include the Golden and silver ratios, the Pisot
numbers, the n-bonacci (tribonacci, tetranacci, etc.) numbers.

<EMAIL_ADDRESS>doi:10.13140/RG.2.2.17132.26248

##  1 Introduction

The last three or four decades of mathematical research has seen dramatic
advances in the theory of subshifts. This text is mostly not about that,
except to point out that this theory has very broad and important impact on
many branches of physics and mathematics. From the perspective of the amateur
enthusiast, the theory of subshifts finally exposes and makes clear some of
the mysterious and intriguing behavior of fractals and of chaotic dynamical
systems.

This text focuses almost entirely on just one particular map of the unit
interval, the $\beta$-transform, defined as the iterated map $\beta x\mod 1$.
As such, it is an example of an iterated map on the unit interval of the real
number line. Such maps have the form

$f:[0,1]\to[0,1]$

and the topic is the exploration of the consequence of iterating the map by
composing:

$f^{n}(x)=(f\circ f\circ\cdots\circ f)(x)=f(f(\cdots f(x)\cdots))$

Such one-dimensional iterated maps have been heavily studied, and there is a
large body of results, interconnecting many different concepts and results
from mathematics, and so having a particularly broad range.

This text attempts to report some brand-new results on the $\beta$-transform.
This is perhaps surprising, as one might think that the $\beta$-transform is
sufficiently simple so as to be well-studied and well-understood, it being
among the very simplest of iterated one-dimensional maps. This text also
attempts to report these results in a naive and unsophisticated fashion, in
the hope that this makes the text readable for the interested student and
casual enthusiast.

Thus, although the author is personally excited by the advances in the field,
this text is neither a survey of known results on the $\beta$-transform, nor
does it much glance at most of the typical avenues that are available for
studying one-dimensional maps. This text does focus extensively on the
spectrum of the transfer operator (the “Ruelle Perron Frobenius operator”),
and thus it contributes to the general “Koopmania”. Little prior knowledge is
assumed, and the needed concepts are introduced in a very casual and informal
way. This will, no doubt, completely discourage and dismay the formally
trained mathematician. The best I can offer is to reiterate: “new results”,
off the beaten track.

This text begins with some pretty pictures, showing the iterated tent and
logistic maps, so as to remind the reader as to why this is an interesting
problem to study. The fact is that the $\beta$-transformation is far more dry
and abstract than the rather sexy logistic map, or its complex cousin, the
Mandelbrot set. The hope is that the $\beta$-transformation is also simpler,
and therefore, perhaps, easier to understand. The reader will soon discover
that there is nothing particularly easy about it, and that, at every turn, one
bumps into other interesting areas of mathematics that could, perhaps should
shed some light, but don’t actually seem to do so, in practice.

The most fun for the casual reader might be chapter 5, on the periodic orbits,
where the quasi-cyclotomic polynomials appear; these are polynomials of the
form $p_{n}\left(z\right)=z^{k+1}-b_{0}z^{k}-b_{1}z^{k-1}-\cdots-b_{k-1}z-1$
for the $b_{j}$ being binary bits (zero or one). Also quite fun is the section
on the islands of stability, which sheds light on how one can take a purely
ergodic (chaotic) system, and surgically insert, as desired, islands of
stability. The point here is that the classic logistic map attracted interest
precisely because of its interleaving of chaos and stability; it turns out,
one can manufacture such systems, at will.

Perhaps the most surprising aspect of iteration (surprising to me) is that the
invariant measure consists of flat plateaus. Or perhaps this is not
surprising; after all, for the full shift, $\beta=2$, the invariant measure is
a straight line, and this is equivalent to saying that the real numbers are
aboslutely evenly distributed, or that the toss of a perfectly fair coin is a
perfectly even, random sequences of heads and tails. Flatness implies an even
distribution. So flatness is not surprising. But look at it a different way:
the digit sequences are wildly and ergodically different, yet none-the-less
manage to _sum to exactly the same value_ , when summed in an analytic series!
Why should crazy-different, crazy-chaotic sequences yeild identical
summations? That they do should be considered to be the “fundamental theorem
of analytic ergodics”. (I use the word “analytic” here in the same sense as
“analytic number theory” or “analytic combinatorics”. Given a sequence of
values, one explores the analytic properties of its generating functions.) If
this theorem has ever been clearly stated before, or if it has been proven
(for any case other than the Bernoulli shift), I do not know. It seems
terribly important for analyzing subshifts.

A word about the format of this paper: this is a _de facto_ “research diary”,
not a formal report. This, it contains various unfinished corners and notes-
to-self.

###  1.1 Bernoulli shift

The Bernoulli shift (aka the bit-shift map) is an iterated map on the unit
interval, given by iteration of the function

$b(x)=\begin{cases}2x&\mbox{ for }0\leq x<\frac{1}{2}\\\ 2x-1&\mbox{ for
}\frac{1}{2}\leq x\leq 1\end{cases}$ (1)

The symbolic dynamics of this map gives the binary digit expansion of $x$.
That is, write

$b^{n}(x)=(b\circ b\circ\cdots\circ b)(x)=b(b(\cdots b(x)\cdots))$

to denote the $n$-fold iteration of $b$ and let $b^{0}(x)=x$. The symbolic
dynamics is given by the bit-sequence

$b_{n}\left(x\right)=\begin{cases}0&\mbox{ if }0\leq b^{n}(x)<\frac{1}{2}\\\
1&\mbox{ if }\frac{1}{2}\leq b^{n}(x)\leq 1\end{cases}$ (2)

Of course, the symbolic dynamics recreates the initial real number:

$x=\sum_{n=0}^{\infty}b_{n}\left(x\right)2^{-n-1}$

All of this is just a fancy way of saying that a real number can be written in
terms of it’s base-2 binary expansion. That is, the binary digits for $x$ are
the $b_{n}=b_{n}\left(x\right)$, so that

$x=0.b_{0}b_{1}b_{2}\cdots$

The Bernoulli shift has many interesting properties, connecting it to the
Cantor set and to many self-similar fractals. I have explored these in many
other texts, as have other authors, and will not repeat these here. The author
is too lazy to provide a bibliography; the reader is directed at search
engines.

The current task is to attempt to see how many of these properties still hold
in slightly more complex systems, and whether any of the tools used to analyze
and solve the Bernoulli shift can be applied to these systems.

###  1.2 Shift space

The use of the word “shift” here deserves a small bit of formality. A “shift
space” can be formally defined to be a set of infinite sequences of a set of
$N$ letters (or symbols), together with a shift operator $T$ that takes each
sequence, and lops off the left-most symbol. For the Bernoulli shift, there
are $N=2$ letters, taken from the set $\left\\{0,1\right\\}$. For the
Bernoulli shift, one is typically interested in the set of all possible
infinite sequences: this is the “full shift”. One writes
$\left\\{0,1\right\\}^{\omega}$ for this shift space, $\omega$ denoting
countable infinity. For the Bernoulli shift, the map $b\left(x\right)$ is the
shift operator: it just lops of the left-most symbol.

In general, a shift space does not have to include every possible sequence of
symbols; it does, however, by definition, have to be shift-invariant. That is,
given some set $S$ of infinite sequences of $N$ symbols, the set $S$ is a
shift space if and only if, by loping off the leading symbol of each string,
one regains $S$ again. In formulas, a shift space $S$ must obey

$TS=S$

For example, $S=\left\\{000\cdots,111\cdots\right\\}$ contains only two
elements: the string of all zeros, and the string of all ones; loping off the
leading digit just returns $S$ again. In general, shift spaces may contain a
finite, or a countable, or an uncountable number of elements. In general, one
defines the “full shift” as the space $N^{\omega}$ of all possible strings of
$N$ symbols. Subsets that are shift spaces are called “subshifts”.

The words “symbolic dynamics” also deserve some mention: given one specific
sequence $x$ out of the shift space, one can ponder “where it goes to”, as one
lops off a symbol at a time. This gives the “symbolic dynamics” or the “point
dynamics” of the sequence. The “orbit” is defined as the set
$\left\\{T^{m}x\,|\,\mbox{integer }m\geq 0\right\\}$– that is, the set of all
places that $x$ goes to. There are several possibilities: one is that $x$ is a
fixed point, so that $Tx=x$. Another is that $x$ is a repeating sequence of
symbols, in which case iteration repeats as well: $T^{m}x=x$ holds whenever
the repeat length is $m$; this is a periodic orbit. Most importantly, there
usually uncountably many non-periodic sequences or orbits. That is, the number
of periodic orbits is always countable: one merely arranges them in
lexicographic order, and one is done. As Cantor famously demonstrated (and
Hilbert so carefully expanded on) this cannot be done for the non-periodic
orbits: they are uncountable.

In what follows, the text will in general confine itself to uncountable case.
Periodic orbits exist, but will be ignored; in a certain strict sense, they
constitute a set of measure zero. A number of glosses like this will be made:
for example, the real numbers, and the Cantor space
$\left\\{0,1\right\\}^{\omega}$ are both uncountable; however, they are not in
one-to-one correspondence, as some real numbers can have two different
representations as bit sequences. Specifically, these are the fractions
$\left(2n+1\right)/2^{m}$ for positive integers $m,n$ – they can be validly
represented by bit-sequences ending in all-zeros, or all-ones. There are
countably many such fractions, termed the dyadic fractions. For the most part,
this difference between the real number line, and the Cantor space will be
ignored.

###  1.3 Beta shift

The beta shift is similar to the Bernoulli shift, replacing the number 2 by a
constant real-number value $1<\beta\leq 2$. It can be defined as

$T_{\beta}(x)=\begin{cases}\beta x&\mbox{ for }0\leq x<\frac{1}{2}\\\
\beta\left(x-\frac{1}{2}\right)&\mbox{ for }\frac{1}{2}\leq x\leq
1\end{cases}$ (3)

This map, together with similar maps, is illustrated in figure 5 below.

Just as the Bernoulli shift generates a sequence of digits, so does the beta
shift: write

$k_{n}=\begin{cases}0&\mbox{ if }0\leq T_{\beta}^{n}(x)<\frac{1}{2}\\\
1&\mbox{ if }\frac{1}{2}\leq T_{\beta}^{n}(x)\leq 1\end{cases}$ (4)

Given the symbolic dynamics, one can reconstruct the original value whenever
$1<\beta$ as

$x=\frac{k_{0}}{2}+\frac{1}{\beta}\left(\frac{k_{1}}{2}+\frac{1}{\beta}\left(\frac{k_{2}}{2}+\frac{1}{\beta}\left(\frac{k_{3}}{2}+\frac{1}{\beta}\left(\cdots\right)\right)\right)\right)$

That is, one clearly sees that $T_{\beta}(x)$ acts as a shift on this
sequence:

$T_{\beta}(x)=\frac{k_{1}}{2}+\frac{1}{\beta}\left(\frac{k_{2}}{2}+\frac{1}{\beta}\left(\frac{k_{3}}{2}+\frac{1}{\beta}\left(\frac{k_{4}}{2}+\frac{1}{\beta}\left(\cdots\right)\right)\right)\right)$

In this sense, this shift is “exactly solvable”: the above provides a closed-
form solution for iterating and un-iterating the sequence.

Multiplying out the above sequence, one obtains the so-called
“$\beta$-expansion” of a real number $x$, namely the series

$x=\frac{1}{2}\,\sum_{n=0}^{\infty}\frac{k_{n}}{\beta^{n}}$ (5)

That is, the bit-sequence that was extracted by iteration can be used to
reconstruct the original real number. Setting $\beta=2$ in eqn 2 gives the
Bernoulli shift. Explicitly, one has $T_{2}\left(x\right)=b\left(x\right)$.

Unlike the Bernoulli shift, not every possible bit-sequence occurs in this
system. It is a subshift of the full shift: it is a subset of
$\left\\{0,1\right\\}^{\omega}$ that is invariant under the action of
$T_{\beta}$. This is explored in greater detail in a later section.

###  1.4 Associated polynomial

The iterated shift can also be written as a finite sum. This is noted here; it
will be useful in later sections. Observe that

$T_{\beta}(x)=\beta\left(x-\frac{k_{0}}{2}\right)$

and that

$T_{\beta}^{2}(x)=\beta^{2}x-\frac{\beta}{2}\left(\beta k_{0}+k_{1}\right)$

and that

$T_{\beta}^{3}(x)=\beta^{3}x-\frac{\beta}{2}\left(\beta^{2}k_{0}+\beta
k_{1}+k_{2}\right)$

The general form is then:

$T_{\beta}^{p}(x)=\beta^{p}x-\frac{\beta}{2}\sum_{m=0}^{p-1}k_{m}\beta^{p-m-1}$
(6)

Since the $k_{m}$ depend on both $\beta$ and on $x$, this is not a “true”
polynomial; however, it will be useful in analysis, later.

###  1.5 Density Visualizations

Why is the beta transform interesting to explore? This can be partly
illustrated with some graphs. Shown in figure 2 is the “bifurcation diagram”
for the beta transform. It visualizes the long-term dynamics of the beta
shift. Comparing to the usual bifurcation diagram, e.g. for the Feigenbaum
logistic map (shown in figure 4) one thing becomes immediately apparent: there
are no actual “bifurcations”, no “islands of stability”, no period-doubling
regions. Although there are periodic orbits, these form a set of measure zero:
the iteration produces purely chaotic motion for all values of $\beta$. Thus,
the beta transform provides a clean form of “pure chaos”,111Formal mathematics
distinguishes between many different kinds of chaotic number sequences: those
that are ergodic, those that are weakly or strongly Bernoulli, weakly or
strongly mixing. The beta transform is known to be ergodic,[1] weakly
mixing[2] and weakly Bernoulli.[6] without the pesky “islands of stability”
popping up intermittently.

The visualization of the long-term dynamics is done by generating a histogram,
and then taking the limit, as follows. One divides the unit interval into a
fixed sequence of equal-sized bins; say a total of $N$ bins, so that each is
$1/N$ in width. Pick a starting $x$, and then iterate: if, at the $n$’th
iteration, one has that $j/N\leq b_{\beta}^{n}(x)<(j+1)/N$, then increment the
count for the $j$’th bin. After a total of $M$ iterations, let $c(j;M)$ be the
count in the $j$’th bin. This count is the histogram. In the limit of a large
number of iterations, as well as small bin sizes, one obtains a distribution:

$\rho(y;x)=\lim_{N\to\infty}\lim_{M\to\infty}\frac{c(j;M)}{M}\mbox{ for
}\frac{j}{N}\leq y<\frac{j+1}{N}$

This distribution depends on the initial value $x$ chosen for the point to be
iterated; a “nice” distribution results when one averages over all starting
points:

$\rho(y)=\int_{0}^{1}\rho(y;x)\,dx$

Numerically, this integration can be achieved by randomly sampling a large
number of starting points. Observe that $\rho(y)$ is a probability
distribution:

$1=\int_{0}^{1}\rho(x)\,dx$

This probability distribution is an eigenstate of the transfer operator for
the beta transform; the definition of the transfer operator of the beta
transform is given later. Probability distributions are the same thing as
measures; this particular distribution is invariant under iteration, and thus
is often called the invariant measure, or sometimes the Haar measure.

For each fixed $\beta$, one obtains a distinct distribution $\rho_{\beta}(y)$.
The figure 1 illustrates some of these distributions. Note that, for
$\beta<1$, the distribution is given by $\rho_{\beta}(y)=\delta(y)$, a Dirac
delta function, located at $y=0$.

Figure 1: Beta-shift Density Distribution

The above figure shows three different density distributions, for
$\rho_{1.2}(y)$, $\rho_{1.6}(y)$ and $\rho_{1.8}(y)$, calculated numerically.
This is obtained by histogramming a large number of point trajectories, as
described in the text. The small quantities of jitter are due to a finite
number of samples. To generate this figure, a total of $M=4000$ iterations
were performed, using randomly generated arbitrary-precision floats (the Gnu
GMP package), partitioned into $N=800$ bins, and sampled 24000 times (or 30
times per bin) to perform the averaging integral. It will later be seen that
the discontinuities in this graph occur at the “iterated midpoints”
$m_{p}=T_{\beta}^{p}\left(\beta/2\right)$. The flat plateaus really are flat,
and this is perhaps the one of the most amazing aspects of this figure; ths
will be a recurring theme throughout the text.

The general trend of the distributions, as a function of $\beta$, can be
visualized with a Feigenbaum-style “bifurcation diagram”, shown in figure 2.
This color-codes each distribution $\rho_{\beta}(y)$ and arranges them in a
stack; a horizontal slice through the diagram corresponds to $\rho_{\beta}(y)$
for a fixed value of $\beta$. The term “bifurcation diagram” comes from its
use to visualize the logistic map iterator.

Figure 2: Beta-shift Bifurcation Diagram

This figure shows the density $\rho_{\beta}(y)$, rendered in color. The
constant $\beta$ is varied from 0 at the bottom to 2 at the top; whereas $y$
runs from 0 on the left to 1 on the right. Thus, a fixed value of $\beta$
corresponds to a horizontal slice through the diagram. The color green
represents values of $\rho_{\beta}(y)\approx 0.5$, while red represents
$\rho_{\beta}(y)\gtrsim 1$ and blue-to-black represents
$\rho_{\beta}(y)\apprle 0.25$. The diagram is “interesting” only for
$1<\beta$; for smaller $\beta$’s, one has that $\rho_{\beta}(y)=\delta(y)$,
indicated by the column of red pixels on the left side of the image. The lines
forming the fan shape are not actually straight, they only seem to be; in
fact, they have a slight curve. This means that one cannot apply simple-minded
guess-work to discover the overall diagram shown here.

###  1.6 Tent Map

The tent map is a closely related iterated map, given by iteration of the
function

$v_{\beta}(x)=\begin{cases}\beta x&\mbox{ for }0\leq x<\frac{1}{2}\\\
\beta\left(1-x\right)&\mbox{ for }\frac{1}{2}\leq x\leq 1\end{cases}$

Its similar to the beta shift, except that the second arm is reflected
backwards, forming a tent. The bifurcation diagram is shown in figure 3. Its
is worth contemplating the similarities between this, and the corresponding
beta shift diagram. Clearly, there are a number of shared features.

Figure 3: Tent Map Bifurcation Diagram

The bifurcation diagram for the tent map. The value of $\beta$ runs from 1 at
the bottom of the image, to 2 at the top. The color scheme is adjusted so that
green represents the average value of the distribution, red represents areas
of more than double the average value, while blue shows those values that are
about half the average value. Note that this is a different color scheme than
that used in figure 2; that scheme would obliterate the lower half of this
figure in red.
The black areas represent parts of the iterated range that are visited at most
a finite number of times. To the left, a straight line indicates that after
one iteration, points in the domain $\beta/2\leq x\leq 1$ are never visited.
To the right, points in the domain $0\leq x\leq\beta\left(1-\beta/2\right)$
are never visited more than a finite number of times.

###  1.7 Logistic Map

The logistic map is related to the tent map, and is given by iteration of the
function

$f_{\beta}\left(x\right)=2\beta x(1-x)$

It essentially replaces the triangle forming the tent map with a parabola of
the same height. That is, the function is defined here so that the the same
value of $\beta$ corresponds to the same height for all three maps. Although
the heights of the iterators have been aligned so that they match, each
exhibits rather dramatically different dynamics. The $\beta$-transform has a
single fixed point for $\beta<1$, and then explodes into a fully chaotic
regime above that. By contrast, the logistic map maintains a single fixed
point up to $\beta=3/2$, where it famously starts a series of period-doubling
bifurcations. The onset of chaos is where the bifurcations come to a limit, at
$\beta=3.56995/2=1.784975$. Within this chaotic region are “islands of
stability”, which do not appear in either the $\beta$-transform, or in the
tent map. The tent map does show a period-doubling regime, but in this region,
there are no fixed points: rather, the motion is chaotic, but confined to
multiple arms. At any rate, the period doubling occurs at different values of
$\beta$ than for the logistic map.

The bifurcation diagram is shown in figure 4. Again, it is worth closely
examining the similarities between this, and the corresponding tent-map
diagram, as well as the $\beta$-transform diagram. Naively, it would seem that
the general structure of the chaotic regions are shared by all three maps.
Thus, in order to understand chaos in the logistic map, it is perhaps easier
to study it in the$\beta$-transform.

Figure 4: Logistic Map Bifurcation Diagram

The logistic map bifurcation diagram. The value of $\beta$ runs from 1.75 at
the bottom of the image, to 2 at the top. The color scheme is adjusted so that
green represents the average value of the distribution, red represents areas
of more than double the average value, while blue shows those values that are
about half the average value. Clearly, the orbits of the iterated points spend
much of their time near the edges of the diagram.

The general visual similarity between the figures 2, 3 and 4 should be
apparent, and one can pick out and find visually similar regions among these
three illustrations. Formalizing this similarity is a bit harder, but it can
be done: there is a way to make all three of these maps be “topologically
conjugate” to one-another. This is perhaps surprising to some readers, but is
based on the observation that the “islands of stability” in the logistic map
are countable, and are in one-to-one correspondence with certain “trouble
points” in the iterated beta transformation. These are in turn in one-to-one
correspondence with rational numbers. With a slight distortion of the beta
transformation, the “trouble points” can be mapped to the islands of
stability, in essentially the same way that “phase locking regions” or “Arnold
tongues” appear in the circle map. But this is all for a later section, again,
mentioned here only to whet the appetite.

###  1.8 Beta Transformation

After exactly one iteration of the beta shift , all initial points
$\beta/2\leq x\leq 1$ are swept up into the domain $0\leq x<\beta/2$, and
never leave. Likewise, the range of the iterated beta shift is $0\leq
x<\beta/2$. Thus, an alternative representation of the beta shift, filling the
entire unit square, can be obtained by dividing both $x$ and $y$ by $\beta/2$
to obtain the function

$t_{\beta}(u)=\begin{cases}\beta u&\mbox{ for }0\leq u<\frac{1}{\beta}\\\
\beta u-1&\mbox{ for }\frac{1}{\beta}\leq u\leq 1\end{cases}$ (7)

which can be written more compactly as $t_{\beta}\left(x\right)=\beta x\,\mod
1$. In this form, the function is known as the beta transform, and is often
called the $\beta$-transformation, presenting a typesetting challenge to
search engines when used in titles of papers. The orbit of a point $x$ in the
beta shift is identical to the orbit of a point $u=2x/\beta$ in the beta
transformation. Explicitly comparing to the beta shift of eqn 3:

$T_{\beta}^{n}\left(x\right)=\frac{\beta}{2}t_{\beta}^{n}\left(\frac{2x}{\beta}\right)$

The beta shift and the $\beta$-transformation are essentially “the same
function”; this text works almost exclusively with the beta shift, and is thus
idiosyncratic, as it flouts the much more common convention of working with
the $\beta$-transformation. There is no particular technical reason for this;
it is rather due to happenstance.

After a single iteration of the tent map, a similar situation applies. After
one iteration, all initial points $\beta/2\leq x\leq 1$ are swept up into the
domain $0\leq x<\beta/2$. After a finite number of iterations, all points
$0<x\leq\beta\left(1-\beta/2\right)$ are swept up, so that the remaining
iteration takes place on the domain $\beta\left(1-\beta/2\right)<x<\beta/2$.
It is worth defining a “sidetent” function, which corresponds to the that part
of the tent map in which iteration is confined. It is nothing more than a
rescaling of the tent map, ignoring those parts outside of the above domain
that “wander away”. The sidetent is given by

$s_{\beta}(u)=\begin{cases}\beta\left(u-1\right)+2&\mbox{ for }0\leq
u<\frac{\beta-1}{\beta}\\\ \beta\left(1-u\right)&\mbox{ for
}\frac{\beta-1}{\beta}\leq u\leq 1\end{cases}$

Performing a left-right flip on the side-tent brings it closer in form to the
beta-transformation. The flipped version, replacing $u\to 1-u$ is

$f_{\beta}(u)=\begin{cases}\beta u&\mbox{ for }0\leq u<\frac{1}{\beta}\\\
2-\beta u&\mbox{ for }\frac{1}{\beta}\leq u\leq 1\end{cases}$

The tent map (and the flipped tent) exhibits fixed points (periodic orbits;
mode-locking) for the smaller values of $\beta$. These can be eliminated by
shifting part of the tent downwards, so that the diagonal is never
intersected. This suggests the “sidetarp”:

$a_{\beta}(u)=\begin{cases}\beta u&\mbox{ for }0\leq u<\frac{1}{\beta}\\\
\beta\left(1-u\right)&\mbox{ for }\frac{1}{\beta}\leq u\leq 1\end{cases}$

The six different maps under consideration here are depicted in figure 5. It
is interesting to compare three of the bifurcation diagrams, side-by-side.
These are shown in figure 6.

Figure 5: Iterated piece-wise linear maps

The beta shift map, shown in the upper left, generates orbits that spend all
of their time in the shaded area: a box of size
$\frac{\beta}{2}\times\frac{\beta}{2}$. Enlarging this box to the unit square
gives the $\beta$-transformation. The tent map resembles the beta shift,
except that one arm is flipped to make a tent-shape. After a finite number of
iterations, orbits move entirely in the shaded region; enlarging this region
to be the unit square gives the sidetent map. Flipping it left-right gives the
fliptent map. Although it is not trivially obvious, the fliptent map and the
sidetent map have the same orbits, and thus the same bifurcation diagram.

The bottom three maps all have fixed points and periodic orbits, essentially
because the diagonal intersects the map. The top three maps have no periodic
orbits, and are purely chaotic, essentially because the diagonal does not
intersect them. Note tht the slopes and the geometric proportions of all six
maps are identical; they are merely rearrangents of the same basic elements.

Figure 6: Beta transform and Side-tent

The left figure shows the bifurcation diagram for the $\beta$-transform, as it
is normally defined as the $\beta x\mod 1$ map. It is the same map as the beta
shift, just rescaled to occupy the entire unit square. In all other respects,
it is identical to 2.

The middle figure is a similarly-rescaled tent map, given the name “side tent”
in the main text. It is essentially identical to 3, with the middle parts
expanded and the sides removed. In both figures, $\beta$ runs from 1 at the
bottom to 2 at the top. The right-hand-side figure is the “sidetarp”, clearly
its an oddly-folded variant of the beta transform.

###  1.9 Beta Transformation Literature Review and References

The $\beta$-transformation, in the form of $t_{\beta}\left(x\right)=\beta
x\,\mod 1$ has been well-studied over the decades. The beta-expansion 4 was
introduced by A. Renyi[1], who demonstrates the existence of the invariant
measure. The ergodic properties of the transform were proven by W. Parry[2],
who also shows that the system is weakly mixing.

An explicit expression for the invariant measure was independently obtained by
A.O. Gel’fond[3] and by W. Parry[2], as

$\nu_{\beta}\left(y\right)=\frac{1}{F}\sum_{n=0}^{\infty}\frac{\varepsilon_{n}\left(y\right)}{\beta^{n}}$
(8)

where $\varepsilon_{n}$ is the digit sequence

$\varepsilon_{n}\left(y\right)=\begin{cases}0&\mbox{ if
}t_{\beta}^{n}\left(1\right)\leq y\\\ 1&\mbox{ otherwise}\end{cases}$

and $F$ is a normalization constant.

In the same way that a dyadic rational $p/2^{n}$ has two different binary
expansions, one ending in all-zeros, and a second ending in all-ones, so one
may also ask if and when a real number $x$ might have more than one
$\beta$-expansion (for fixed $\beta$). In general, it can; N. Sidorov shows
that almost every number has a continuum of such expansions![4]

Conversely, the “univoke numbers” are those values of $\beta$ for which there
is only one, unique expansion for $x=1$. These are studied by De Vries.[5]

The $\beta$-transformation has been shown to have the same ergodicity
properties as the Bernoulli shift.[6] The fact that the beta shift, and its
subshifts are all ergodic is established by Climenhaga and Thompson.[7]

An alternative to the notion of ergodicity is the notion of universality: a
$\beta$-expansion is universal if, for any given finite string of bits, that
finite string occurs somewhere in the expansion. This variant of universality
was introduced by Erdös and Komornik[8]. Its is shown by N. Sidorov that
almost every $\beta$-expansion is universal.[9] Conversely, there are some
values of $\beta$ for which rational numbers have purely periodic
$\beta$-expansions;[10] all such numbers are Pisot numbers.[11]

The symbolic dynamics of the beta-transformation was analyzed by F.
Blanchard[12]. A characterization of the periodic points are given by Bruno
Maia[13]. A discussion of various open problems with respect to the beta
expansion is given by Akiyama.[14]

When the beta expansion is expanded to the entire real-number line, one
effectively has a representation of reals in a non-integer base. One may ask
about arithmetic properties, such as the behavior of addition and
multiplication, in this base - for example, the sum or product of two
$\beta$-integers may have a fractional part! Bounds on the lengths of these
fractional parts, and related topics, are explored by multiple authors.[15,
16, 17]

Certain values of $\beta$ \- generally, the Pisot numbers, generate fractal
tilings,[18, 19, 20, 10, 14] which are generalizations of the Rauzy fractal.
An overview, with common terminology and definitions is provided by
Akiyama.[21] The tilings, sometimes called (generalized) Rauzy fractals, an be
thought of as living in a direct product of Euclidean and $p$-adic spaces.[22]

The set of finite beta-expansions constitutes a language, in the formal sense
of model theory and computer science. This language is recursive (that is,
decidable by a Turing machine), if and only if $\beta$ is a computable real
number.[23]

The zeta function, and a lap-counting function, are given by Lagarias[24]. The
Hausdorff dimension, the topological entropy and general notions of
topological pressure arising from conditional variational principles is given
by Daniel Thompson[25]. A proper background on this topic is given by Barreira
and Saussol[26].

None of the topics or results cited above are made use of, or further expanded
on, or even touched on below. That’s mostly because what follows below is just
a … different perspective on the topic. Not intentionally so; it just happened
to come out that way.

##  2 Symbolic Dynamics

The Bernoulli shift corresponds to the sequence of binary digits of a real
number. Such sequences can be imagined to belong to the space of all possible
sequences of binary digits, the Cartesian product of infinitely many copies of
the set containing two elements:

$\left\\{0,1\right\\}\times\left\\{0,1\right\\}\times\left\\{0,1\right\\}\times\cdots=\left\\{0,1\right\\}^{\omega}=2^{\omega}$

This space has a natural topology, the product topology, which differs sharply
from the natural topology on the real-number line. Essentially all of the
strange phenomena of fractals and of iterated functions follows from the
product topology on this sequence.

One notable effect that can be explained in terms of the product topology is
the fractal self-similarity of many kinds of fractals: this arises from the
self-similarity of the product space under the action of a shift:
specifically, the left-shift, which discards the left-most digit, and shifts
the rest over by one. The shift operator itself is that operator that performs
this shift; self-similar fractals can be seen to be eigenstates of the shift
operator.

Another notable effect is the close proximity of the Cantor set to the
proceedings. In a certain sense, the Cantor set can be understood to be the
most basic manifestation of the product space. When attuned to its presence,
it can be seen everywhere throughout the proceedings.

A third byproduct is the manifestation of the infinitely-deep binary tree.
This arises when the set $\left\\{0,1\right\\}$ of the product space is re-
interpreted as the set $\left\\{L,R\right\\}$ of left-right moves. At each
point in a binary sequence, one can make a choice of one of two things: to
move left or right. This naturally suggests a binary decision tree.

A fourth byproduct is the presence of some implicit, ambient hyperbolic space.
The infinite binary tree, when drawn on flat two-dimensional space, simply
“runs out of room”, as each subsequent branching pushes closer together. The
infinite binary tree can be embedded in the simplest hyperbolic space, the
Poincaré disk or upper-half-plane, in such a way that the distance, the
spacing between two neighboring nodes is always the same. Visually, this takes
the form of some prototypical M.C. Escher drawing, of a repeated fractal form
moving out to the edge of a disk. This makes the self-similar shape of the
infinite binary tree manifest: as one moves from one location to another, one
always sees “the same thing” in all directions: the space is homogeneous.

The rational numbers play a very special role in the infinite binary tree.
Dyadic rationals, of the form $\left(2p+1\right)/2^{n}$ for integers $p$ and
$n$ correspond to bit sequences (eqn 2) that terminate in all-zeros after a
finite number of moves. That is, after an initial “chaotic” sequence, they
settle down to a fixed point of period one. General rational numbers $p/q$
behave similarly, in that after an initial “chaotic” sequence, they settle
down to periodic orbits of some fixed period. The bit-sequence becomes cyclic.
This cyclic behavior implies that most of classical number theory can be
dragged into the proceedings. Any particular statement that classical number
theory makes with regard to rational numbers, or even modular forms, can be
promptly ported over to a statement about the bit-sequences and the orbits of
the Bernoulli shift, usually taking on a strange and unrecognizable form.

All of these things go together, like hand in glove: whenever one is manifest
and visible, the others are lurking right nearby, in the unseen directions.
All of these things can be given a formal and precise definition, and their
explicit inter-relationships articulated. This has been done by a wide variety
of authors over the last four decades; a proper bibliography would be
overwhelming. I have written on all of thee topics, trying to present them in
the simplest, most jargon-free way that I can, in a dozen different texts
available wherever you found this one. The ideas will not be repeated here;
they are not immediately useful to the current proceedings. None-the-less, the
general interplay between all of these concepts is extremely important to
understand, and burbles constantly under the surface of the current
proceedings. In essence, shifts and subshifts are interesting precisely
because they touch on so any different topics; and, conversely, so many
different areas of mathematics can inform the subshift.

###  2.1 Symbolic Dynamics

Given that iteration can generate strings of binary digits, and that these can
be reassembled back into real numbers, it is interesting to ask what those
mappings look like. To firm up the notation,
let$\left(b_{n}\right)=\left(b_{0},b_{1,},\cdots\right)$ denote a sequence of
bits (or symbols) and write

$x_{\beta}\left(\left(b_{n}\right)\right)=\frac{1}{2}\,\sum_{n=0}^{\infty}\frac{b_{n}}{\beta^{n}}$

as the real number generated from that sequence. Conversely, given a real
number $x$, let $\left(k_{n;\beta}\left(x\right)\right)$ denote the sequence
of bits obtained by iterating the beta shift on $x$ with constant $\beta$;
that is, the sequence generated by eqn. 4. The bit sequence for
$\left(k_{n;2}\left(x\right)\right)$ is just the bit sequence
$\left(b_{n}\left(x\right)\right)$ generated by eqn 2. The transformations
between symbol sequences and real numbers make sense only when $1<\beta\leq
2$.

Two interesting functions can be considered. One is the compressor

$\mbox{cpr}_{\beta}(y)=x_{2}\left(\left(k_{n;\beta}\left(y\right)\right)\right)$

and the other is the expander

$\mbox{pdr}_{\beta}(y)=x_{\beta}\left(\left(k_{n;2}\left(y\right)\right)\right)$
(9)

The terms “compressor” and “expander” are being invented here to indicate
negative and positive Lyapunov exponents associated with the two functions.
For almost all $y$, the compressor function is pushing nearby points closer
together; the total measure of the range of the compressor function is less
than one. Likewise, for almost all $y$, the expander function is pushing
nearby points apart. These two functions are illustrated in figures 7 and 8.

Figure 7: Compressor Function

This illustrates the compressor function for various values of $\beta$. As
should be clear, almost all input values are mapped to a set of discrete
output values.

Figure 8: Expander Function

This illustrates the expander function for various values of $\beta$. As
should be clear, almost all neighboring input values are mapped to wildly
different output values.

The two functions are adjoint; specifically, one has that
$\mbox{pdr}_{\beta}\left(\mbox{cpr}_{\beta}\left(y\right)\right)=y$ but that
$\mbox{cpr}_{\beta}\left(\mbox{pdr}_{\beta}\left(y\right)\right)\neq y$. The
former relation is equivalent to eqn. 5. Not all possible sequences of bit
strings appear in the beta shift sequence
$\left(k_{n;\beta}\left(x\right)\right)$; that is, this function is not a
surjection onto $\left\\{0,1\right\\}^{\omega}$. This manifests itself as the
gaps in the range of the compressor function, clearly visible in figure 7. If
a sequence of bits is viewed as a sequence of left-right moves walking down a
binary tree, this implies that some branches of the tree are never taken, and
can be pruned. Only branches on the right are ever pruned: That is, there can
be arbitrarily long sequences of zeros in the expansion, but the longest
possible sequence of 1’s is always bounded. The longest run of 1’s possible is
the largest value of $n$ that satisfies

$2\geq\frac{1+\beta+\beta^{2}+\cdots\beta^{n-1}}{\beta^{n-1}}$

Solving, the bound is

$n=1+\left\lfloor\frac{-\log\left(2-\beta\right)}{\log\beta}\right\rfloor$
(10)

That is, every $n$’th right branch is pruned from the binary tree. For
example, a run of three 1’s in a row is possible only for
$\beta\geq\left(1+\sqrt{5}\right)/2=1.618034\cdots$ the Golden Ratio. The
range of $\mbox{cpr}_{\beta}\left(y\right)$ is most of, but not all of the
Cantor set. The figure 9 visualizes the range of the compressor as a function
of $\beta$.

Figure 9: Range of the compressor

This figure illustrates a color coded visualization of the range of the
compressor function. As before $\beta$ varies from 0 at the bottom to 2 at the
top, and $y$ varies from 0 on the left to 1 on the right. In general, the
compressor function maps intervals of the real number line to single points;
the color corresponds to the size (the measure) of the intervals that were
mapped to that particular point. Blue corresponds to a compression of the
measure by about 1, green to a compression of about 2-3, and yellow-red to a
compression greater than that.

###  2.2 Shifts with holes

Viewed as a shift space, as opposed to a cut-down binary tree, the trimming
can be thought of as a punching of holes into the full shift. This requires a
bit of mental gymnastics. Let $\left(a,c\right)$ be an (open) interval on the
real number line: $\left(a,c\right)=\left\\{x\,|\,a<x<c\right\\}$. Given the
Bernoulli shift $b\left(x\right)=T_{2}\left(x\right)$ from eqns 1 or 3,
consider the set

$\mathcal{I}\left(a,c\right)=\left\\{x\,|\,b^{n}\left(x\right)\notin\left(a,c\right)\mbox{
for any }n\geq 0\right\\}$

That is, as one iterates on some fixed $x$, one requests that no iterate
$b^{n}\left(x\right)$ ever lands in the interval $\left(a,c\right)$. In
essence, one has punched a hole in the unit interval; this corresponds to a
“hole” in the full Bernoulli shift. The set $\mathcal{I}\left(a,c\right)$ is
what remains after punching such a hole.

How can this be visualized? Considering the case $n=0$, its clear that
$\mathcal{I}\left(a,c\right)$ cannot contain $\left(a,c\right)$. That is,
$\mathcal{I}\left(a,c\right)\cap\left(a,c\right)=\emptyset$. For $n=1$, the
interval $\left(a,c\right)$ can come from one of two places: either from
$\left(\frac{a}{2},\frac{c}{2}\right)$ or from
$\left(\frac{a+1}{2},\frac{c+1}{2}\right)$, and so neither of these can be in
$\mathcal{I}\left(a,c\right)$. Continuing, for $n=2$, the intervals
$\left(\frac{a}{4},\frac{c}{4}\right)$,
$\left(\frac{a+1}{4},\frac{c+1}{4}\right)$,
$\left(\frac{a+2}{4},\frac{c+2}{4}\right)$ and
$\left(\frac{a+3}{4},\frac{c+3}{4}\right)$ must also be gone. Continuing in
this fashion, one proceeds with an infinite hole-punch: to obtain
$\mathcal{I}\left(a,c\right)$, one just cuts out $\left(a,c\right)$ and
everything that iterates to $\left(a,c\right)$. For the holes, write

$\mathcal{H}\left(a,c\right)=\bigcup_{n=0}^{\infty}\bigcup_{k=0}^{2^{n}-1}\left(\frac{a+k}{2^{n}},\frac{c+k}{2^{n}}\right)$

and for the interval with the holes punched out:

$\mathcal{I}\left(a,c\right)=\left[0,1\right]\backslash\mathcal{H}\left(a,c\right)$

where $\bigcup$ denotes set-union and $\backslash$ denotes set subtraction. It
is not hard to see that, in the end, this forms a contorted Cantor set, using
the standard midpoint-subtraction algorithm, but with different endpoints. The
canonical Cantor set is built by taking
$\left(a,c\right)=\left(\frac{1}{3},\frac{2}{3}\right)$.

Note that both $\mathcal{H}\left(a,c\right)$ and $\mathcal{I}\left(a,c\right)$
are subshifts: applying the left-shift to them just returns the same set
again. Bot are invariant under the action of the shift operator. In formulas,

$b\mathcal{H}\left(a,c\right)=\mathcal{H}\left(a,c\right)$

and

$b\mathcal{I}\left(a,c\right)=\mathcal{I}\left(a,c\right)$

where, for notational simplicity, the parenthesis are not written, so that for
the set $S$, write $bS=b\left(S\right)$. As shifts, its more appropriate to
view both as sets of bit-sequences, so that the proper relationship between
one and the other should have been written as

$\mathcal{I}\left(a,c\right)=\left\\{0,1\right\\}^{\omega}\backslash\mathcal{H}\left(a,c\right)$

How should these subshifts be visualized as strings? Let
$\left(b_{n}\left(x\right)\right)$ be the bit sequence generated by $x$, for
some $a<x<c$. The cut operation states that such strings can never occur
anywhere in $\mathcal{I}\left(a,c\right)$. Explicitly,
$\mathcal{I}\left(a,c\right)$ never contains sequences of the form
$d_{0}d_{1}d_{2}\cdots
d_{k}b_{0}\left(x\right)b_{1}\left(x\right)b_{2}\left(x\right)\cdots$ for any
arbitrary leading bits $d_{0}d_{1}d_{2}\cdots d_{k}$.

How should these subshifts be visualized as binary trees? The simplest case to
visualize is to take $a=m/2^{n}$ and $c=\left(m+1\right)/2^{n}$ being dyadic
rationals, for some integers $m,n$. In this case, one takes the bit-expansion
for both have the same $n$ leading bits: one starts at the root of the tree,
and walks down the binary tree, making left-right moves in accordance with
this sequence, and after $n$ moves, arrives at a node above a subtree. Just
cut out this subtree, in it’s entirety. That’s the first cut. Now repeat the
process, for the left and right subtrees, from off the root, _ad infinitum_.
For $a$ and $c$ not dyadic rationals, the process is more complicated. If $a$
and $c$ are ordinary rationals, thus having a repeating bit-sequence, one
performs in the same way, but cyclically walking down the side branches of
subtrees. For $a$ and $c$ irrational, the algorithm is considerably more
complicated, and is left as an exercise for the reader :-).

A general classification of shifts with holes, for the beta transform, was
performed by Lyndsey Clark[27].

###  2.3 Generalized compressors and expanders

The range of the compressor function is a shift with a hole. Specifically, for
a given $\beta$, the range of $\mbox{cpr}_{\beta}$ is
$\mathcal{I}\left(\frac{\beta}{2},\frac{1}{2}\right)$. The construction for
shifts with holes can then be applied to construct generalized compressor and
expander functions. One way, which is really rather cheesy, but it works, is
to define the function

$\mbox{dcpr}_{\beta,\gamma}\left(a;x\right)=\sum_{n=0}^{\infty}\left[\frac{1}{\gamma^{n+1}}\sum_{k=0}^{2^{n}-1}\delta\left(x-\frac{a+k}{\beta^{n}}\right)\right]$

and then define the generalized compressor as

$\mbox{cpr}\left(a;x\right)=\int_{0}^{x}\mbox{dcpr}\left(a;y\right)dy$

That is, as one walks along the unit interval, from left to right, one picks
up points with weights on them, obtaining a generalized Devil’s staircase
(Cantor-Vitali) function. This generalization does not seem to be terribly
useful here, and is left to rot.

###  2.4 Self-similarity

Subshifts are, by definition, self-similar. If $S$ is a subshift, and $T$ is
the shift operator, then $TS=S$ is a part of the definition of the subshift.
It is fun to see how this actually manifests itself on the unit interval.

So, the two functions cpr and pdr are self-similar. The pdr function
demonstrates classic period doubling self-similarity: namely, under
$g(x)=x/2$, it behaves as

$\left(\mbox{pdr}_{\beta}\circ
g\right)\left(x\right)=\mbox{pdr}_{\beta}\left(\frac{x}{2}\right)=\frac{1}{\beta}\mbox{pdr}_{\beta}\left(x\right)$

while under reflection $r(x)=1-x$, it behaves as

$\left(\mbox{pdr}_{\beta}\circ
r\right)\left(x\right)=\mbox{pdr}_{\beta}\left(1-x\right)=\frac{\beta}{2\left(\beta-1\right)}-\mbox{pdr}_{\beta}\left(x\right)$

Note that

$\lim_{x\to
1}\,\mbox{pdr}_{\beta}\left(x\right)=\frac{\beta}{2\left(\beta-1\right)}$

The full dyadic monoid is generated by the generators $g$ and $r$; see other
posts from me for lengthly expositions on the structure of the dyadic monoid
and its relationship to the Cantor set and a large variety of fractals.

Here, $g$ is the generator that corresponds to the shift operator $T$. The
notation $g$ is used only to stay consistent with other things that I’ve
written. The generator $r$ indicates that the subshift is also invariant under
reflection; in this case, under the exchange of the symbols $0\leftrightarrow
1$ in the corresponding shift.

The function cpr also exhibits self-similarity, although it alters (expands)
what happens on the $x$ axis. Several self-similarities are apparent. First,
for $0\leq x\leq 1$, one has

$\mbox{cpr}_{\beta}\left(\frac{x}{2}\right)=\frac{1}{2}\mbox{cpr}_{\beta}\left(\frac{\beta
x}{2}\right)$

Equivalently, for $0\leq y\leq\beta/2$ one can trivially restate the above as

$\mbox{cpr}_{\beta}\left(\frac{y}{\beta}\right)=\frac{1}{2}\mbox{cpr}_{\beta}\left(y\right)$
(11)

Although it follows trivially, this restatement helps avoid later confusion.

The left and right halves are identical to one-another, but offset:

$\mbox{cpr}_{\beta}\left(\frac{1}{2}+\frac{x}{2}\right)=\frac{1}{2}+\mbox{cpr}_{\beta}\left(\frac{x}{2}\right)$

It follows that

$\mbox{cpr}_{\beta}\left(\frac{1}{2}+\frac{y}{\beta}\right)=\frac{1}{2}+\frac{1}{2}\mbox{cpr}_{\beta}\left(y\right)$

Combining the above results into one, one has that

$\mbox{cpr}_{\beta}\left(\frac{y}{\beta}\right)+\mbox{cpr}_{\beta}\left(\frac{1}{2}+\frac{y}{\beta}\right)=\frac{1}{2}+\mbox{cpr}_{\beta}\left(y\right)$

This last form is interesting, as it makes an appearance in relation to the
transfer operator, defined below.

###  2.5 Other things with similar symmetry

The cpr curve is just one that belongs to a class of such curves. As an
example, one may construct a Takagi (blancmange) curve by iterating triangles
whose peak is located at $1/\beta$. The Takagi curve is an example of a curve
transforming under a 3-dimensional representation of the dyadic monoid; the
cpr curves transforms under a two-dimensional representation. See my paper on
the Takagi curve for details. Figure 10 shows such a curve. Denote by
$\mbox{tak}_{\beta;w}\left(x\right)$a curve constructed in this fashion. The
transformation properties of this curve include self-similarity on the left,
as

$\mbox{tak}_{\beta;w}\left(\frac{x}{\beta}\right)=x+w\;\mbox{tak}_{\beta;w}\left(x\right)$

for $0\leq x\leq 1$ and self-similarity on the right, as

$\mbox{tak}_{\beta;w}\left(\frac{1}{\beta}+x\left(1-\frac{1}{\beta}\right)\right)=1-x+w\;\mbox{tak}_{\beta;w}\left(x\right)$

Both of these properties follow directly from the construction of the curve;
they can be taken as the defining equations for the curve. That is, the curve
can be taken as that function which satisfies these two recursion relations.

The derivative of the skew Takagi curve is shown in figure 11, and, for lack
of a better name, could be called the skew Haar fractal wavelet. It can be
defined as the formal derivative

$\mbox{har}_{\beta;w}\left(x\right)=\frac{d}{dx}\,\mbox{tak}_{\beta;w}\left(x\right)$

This formal derivative is well-defined, as the skew Takagi is smooth and
piecewise-linear almost everywhere; the places where it has corners is a dense
set of measure zero. That is, the derivative is defined everywhere, except on
a set of measure zero, which happens to be dense in the unit interval.

Figure 10: Skew Takagi Curve

This figure shows a skew Takagi curve, and the first four steps of its
construction. The initial triangle is of height 1; the apex is located at
$1/\beta$, for $\beta=1.6$ in this figure. Subsequent triangles obtain a
height of w=0.7 above the apex point, and are similarly skew.

Note that the Haar fractal wavelet is piece-wise constant everywhere. It is
constructed from a “mother wavelet” given by

$h_{\beta}(x)=\begin{cases}\beta&\mbox{for }0\leq x<\frac{1}{\beta}\\\
\frac{-\beta}{\beta-1}&\mbox{for }\frac{1}{\beta}\leq x\leq 1\end{cases}$ (12)

which is then iterated on to form the fractal curve
$\mbox{har}_{\beta;w}\left(x\right)$. The self symmetries are

$\mbox{har}_{\beta;w}\left(\frac{x}{\beta}\right)=\beta+w\;\mbox{har}_{\beta;w}\left(x\right)$

and

$\mbox{har}_{\beta;w}\left(\frac{1}{\beta}+x\left(1-\frac{1}{\beta}\right)\right)=-\frac{\beta}{\beta-1}+w\;\mbox{har}_{\beta;w}\left(x\right)$

Figure 11: Skew Haar Wavelet

This figure shows the derivative of the skew Takagi curve. Note that it is
piece-wise constant everywhere. The mother wavelet is shown, as well as the
fourth iteration. The specific values graphed are $\beta=1.6$ and $w=0.7$.

###  2.6 Fixed Points; Periodic Orbits

The Bernoulli shift, given by eqn 2, generates every possible bit-sequence. As
was observed in a previous section, not every possible bit-sequence occurs in
the beta shift. The longest sequence of all-ones possible was given by eqn 10.
Arbitrary finite lengths of zeros do appear; but are there fixed points, i.e.
sequences that terminate in all-zeros? Clearly, $x=1/2\beta^{n}$ is such a
fixed point: after $n+1$ iterations of eqn 3, $x$ goes to zero, and stays
there. Is this the only such fixed point? The answer depends on $\beta$. If
$\beta$ can be written in the form of $\beta^{n}=2m+1$ for some integers $n$
and $m$, then the values of $x$ which can iterate down to zero in $n+1$ steps
are dense in the interval $\left[0,\beta/2\right]$. Curiously, such values
$\beta$ are dense in the interval $\left[1,2\right)$. A later chapter performs
explores periodic orbits in great detail.

##  3 Transfer operators

The discovery and study of invariant measures, as well as of decaying states
can be approached via the transfer operator, or, properly named, the Ruelle-
Frobenius-Perron operator. This is an operator that captures the behavior of a
distribution under the action of a map. The invariant measure is an eigenstate
of this operator; indeed, it provides a formal definition for what it means to
be invariant under the action of the map.

Given an iterated map $g:[0,1]\to[0,1]$ on the unit interval, the transfer
operator defines how distributions are acted on by this map. It is defined as

$\left[\mathcal{L}_{g}f\right]\left(y\right)=\sum_{x=g^{-1}(y)}\frac{f(x)}{\left|g^{\prime}(x)\right|}$

The left adjoint of the transfer operator is the composition operator (Koopman
operator). This is defined as

$\left[\mathcal{C}_{g}f\right]\left(y\right)=f\left(g\left(y\right)\right)$

The Koopman operator is adjoint, in the sense that
$\mathcal{L}_{g}\mathcal{C}_{g}=1$ but that, in general,
$\mathcal{C}_{g}\mathcal{L}_{g}\neq 1$.

###  3.1 The $\beta$-transform Transfer Operator

The transfer operator for the beta shift map $T_{\beta}(x)$ is

$\left[\mathcal{L}_{\beta}f\right]\left(y\right)=\begin{cases}\frac{1}{\beta}\left[f\left(\frac{y}{\beta}\right)+f\left(\frac{y}{\beta}+\frac{1}{2}\right)\right]&\mbox{
for }0\leq y\leq\beta/2\\\ 0&\mbox{ for }\beta/2<y\leq 1\end{cases}$

or, written more compactly

$\left[\mathcal{L}_{\beta}f\right]\left(y\right)=\frac{1}{\beta}\left[f\left(\frac{y}{\beta}\right)+f\left(\frac{y}{\beta}+\frac{1}{2}\right)\right]\Theta\left(\frac{\beta}{2}-y\right)$
(13)

where $\Theta$ is the Heaviside step function. The density distributions
graphed in figure 1 are those functions satisfying

$\left[\mathcal{L}_{\beta}\rho\right]\left(y\right)=\rho\left(y\right)$ (14)

That is, the $\rho(y)$ satisfies

$\rho\left(y\right)=\frac{1}{\beta}\left[\rho\left(\frac{y}{\beta}\right)+\rho\left(\frac{y}{\beta}+\frac{1}{2}\right)\right]\Theta\left(\frac{\beta}{2}-y\right)$
(15)

This is generally referred to as the Ruelle-Frobenius-Perron (RFP)
eigenfunction, as it corresponds to the largest eigenvalue of the transfer
operator, and specifically, the eigenvalue 1.

More generally, one is interested in characterizing the eigenspectrum

$\left[\mathcal{L}_{\beta}\rho\right]\left(y\right)=\lambda\rho\left(y\right)$

for eigenvalues $\left|\lambda\right|\leq 1$ and eigenfunctions $\rho(y)$.
Solving this equation requires choosing a space of functions in which to work.
Natural choices include any of the Banach spaces, and in particular, the space
of square-integrable functions. Particularly interesting is the space of
almost-smooth functions, those having discontinuities at only a countable
number of locations, but otherwise being infinitely differentiable. Although
the discussion so far implicitly conditions one to restrict oneself to real-
valued functions, and to consider only real-valued eigenvalues, this is
perhaps too sharp a restriction. It will become clear in the following
chapters that even the most basic form of $\mathcal{L}_{\beta}$ has a complex-
valued spectrum. At any rate, it should be obvious that, whatever the choice
of function space, one must have that $\rho\left(y\right)=0$ whenever
$\beta<2y$. This turns out to be a rather harsh condition.

At least one basic fact is known: for at least some kinds of function spaces,
the RFP eigenfunction is given by Gel’fond and Parry, as shown in eqn 8. More
precisely, it is just the rescaled form
$\rho\left(x\right)=\nu\left(2x/\beta\right)$ for $x<\beta/2$ and zero
otherwise. Changing vocabulary, this is sometimes called the “invariant
measure”; as it describes a measure on the unit interval. That is, for the
space of all possible measures on the unit interval, the Gel’fond-Parry
measure is one of the eigenfunctions of the transfer operator. Some caution is
advised here: for the special case of $\beta=2$, that is, the Bernoulli shift,
one has as an eigenfunction the Minkowski measure[37]; it has eigenvalue 1,
but is otherwise quite pathological: it is continuous nowhere, zero on the
rationals, and divergent on the rest (i.e. on a “fat” Cantor set). There’s no
particular reason to think that this holds only for $\beta=2$; measures can
be, in general, very unusual functions.

A very minor simplification can be achieved with a change of variable. Let
$y=\frac{\beta}{2}-\epsilon$. Then the eigenequation becomes

$\lambda\beta\rho\left(\frac{\beta}{2}-\epsilon\right)=\rho\left(\frac{1}{2}-\frac{\epsilon}{\beta}\right)+\rho\left(1-\frac{\epsilon}{\beta}\right)$

The second term vanishes whenever $\beta/2<1-\epsilon/\beta$ or
$\epsilon<\beta(1-\beta/2)$ and so one has the simpler recurrence relation

$\lambda\rho\left(y\right)=\frac{1}{\beta}\rho\left(\frac{y}{\beta}\right)$
(16)

whenever $\beta(\beta-1)<2y\leq\beta$.

The equations 15 and 16 can be treated as recurrence relations, defining the
$\lambda=1$ eigenstate. Recursing on these gives exactly the densities shown
in figure 1. Computationally, these are much, much cheaper to compute, at
least for $\beta$ much larger than 1, although convergence issues present
themselves as $\beta$ approaches 1. The resulting density may be called the
Ruelle-Frobenius-Perron eigenstate; because it can be quickly computed, it
provides an alternative view of figure 1, free of stochastic sampling noise.

###  3.2 A note on complex eigenvalues

Since the operator $\mathcal{L}_{\beta}$ is purely real, then if it has a
complex spectrum, the eigenvalues and eigenfunctions must come in complex-
conjugate pairs. This can make numerical searches and numerical convergence
behave in unexpected ways, so some brief commentary is in order.

Assume that there exists some complex-valued eigenfunction
$\rho_{\lambda}\left(x\right)$ for fixed, complex eigenvalue $\lambda$. Write
it’s real and complex components as

$\rho_{\lambda}\left(x\right)=\sigma\left(x\right)+i\tau\left(x\right)$

while also writing $\lambda=a+ib$. Then

$\displaystyle\left[\mathcal{L}_{\beta}\sigma\right]\left(x\right)=$
$\displaystyle\frac{1}{2}\left[\mathcal{L}_{\beta}\left(\rho_{\lambda}+\bar{\rho}_{\lambda}\right)\right]\left(x\right)$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(\lambda\rho_{\lambda}\left(x\right)+\bar{\lambda}\bar{\rho}_{\lambda}\left(x\right)\right)$
$\displaystyle=$ $\displaystyle a\sigma\left(x\right)-b\tau\left(x\right)$

Both left and right sides of the above are real. If one had somehow stumbled
upon $\sigma\left(x\right)$ numerically, as an eigenvector-candidate, then the
above admixing of the imaginary component would quickly throw one off the
hunt. Thus, a numeric search for complex-valued eigenfunctions must
necessarily take into account eigenfunction pairs, with real and imaginary
components that mix together as above.

###  3.3 Almost-solutions

If one ignores the Heaviside step function in the definition 13, one easily
finds a number of “almost solutions” to the transfer operator. These are most
easily discussed by defining the operator

$\left[\mathcal{P}_{\beta}f\right]\left(y\right)=\frac{1}{\beta}\left[f\left(\frac{y}{\beta}\right)+f\left(\frac{y}{\beta}+\frac{1}{2}\right)\right]$

Solving this operator is relatively straight-forward. Consider, for example,
the monomial $f\left(y\right)=y^{n}$. Clearly,
$\left[\mathcal{P}_{\beta}y^{n}\right]$ is a polynomial of degree $n$ and that
therefore, the space of polynomials is closed under the action of
$\mathcal{P}_{\beta}$. But this result is even stronger: the monomials provide
a basis in which $\mathcal{P}_{\beta}$ is upper-triangular,_i.e._ solvable.
It’s eigensolutions in this basis are polynomials. The eigenspectrum is
clearly discrete, and is given by $\left(\beta\right)^{-n-1}$ for integers $n$
corresponding to the degree of the polynomial eigensolution.

This all goes horribly wrong if one instead considers $\mathcal{L}_{\beta}$
and the almost-monomials
$f\left(y\right)=y^{n}\Theta\left(\frac{\beta}{2}-y\right)$. This does not
provide a basis that is closed under the action of $\mathcal{L}_{\beta}$.
Attempting to find the closure by iterating on $\mathcal{L}_{\beta}$ generates
a splatter of step functions. This case is examined more closely in the next
chapter.

Attempting some guess-work, the self-similarity of the cpr function suggests
an opening. Specifically, let
$\mbox{ei}_{\beta}\left(x\right)=\mbox{cpr}_{\beta}\left(x\right)-1/2$. The
one finds that

$\displaystyle\left[\mathcal{P}_{\beta}\mbox{ei}_{\beta}\right]\left(y\right)=$
$\displaystyle\frac{1}{\beta}\left[\mbox{ei}_{\beta}\left(\frac{y}{\beta}\right)+\mbox{ei}_{\beta}\left(\frac{y}{\beta}+\frac{1}{2}\right)\right]$
$\displaystyle=$ $\displaystyle\frac{\mbox{ei}_{\beta}\left(y\right)}{\beta}$

This is a non-polynomial, fractal eigenfunction of $\mathcal{P}_{\beta}$, and,
with a bit of elbow-grease, one can find many more. This includes the Takagi
functions, and their higher-order analogs, which are, roughly speaking, Takagi
functions constructed from polynomials. These all have interesting self-
similarity properties under the dyadic monoid.

Unfortunately, one has that $\mbox{ei}_{\beta}\left(x\right)\neq 0$ when
$\beta<2x$; it won’t do as an eigenfunction of $\mathcal{L}_{\beta}$. There is
no obvious, simple modification of $\mbox{ei}_{\beta}\left(x\right)$ that
would cause it to be a valid eigensolution of $\mathcal{L}_{\beta}$. Manually
installing a factor of $\Theta\left(\frac{\beta}{2}-y\right)$ and then
iterating to find the closure leads to the same splatter of step functions as
in the case of the polynomials.

Another interesting case arises if one attempts a Fourier-inspired basis.
Define

$\mbox{e}_{\beta;n;l}\left(x\right)=\exp\,i2\pi\left(2l+1\right)\beta^{n}x$

for integer $l$. One then obtains a shift sequence

$\left[\mathcal{P}_{\beta}\mbox{e}_{\beta;n;l}\right]\left(x\right)=\frac{1}{\beta}\mbox{e}_{\beta;n-1;l}\left(x\right)\left(1+\mbox{e}_{\beta;n;l}\left(\frac{1}{2}\right)\right)$

This is not a viable candidate for $\mathcal{L}_{\beta}$, as it is again beset
by the step function. As a shift sequence, it can be used to construct
coherent states that are eigenfunctions of $\mathcal{P}_{\beta}$, having any
eigenvalue within the unit disk. Specifically, observe that
$\mbox{e}_{\beta;0;l}\left(1/2\right)=\exp i\pi\left(2l+1\right)=-1$ so that
$\left[\mathcal{P}_{\beta}\mbox{e}_{\beta;0;l}\right]\left(x\right)=0$ and so
the shift sequence terminates after finite iteration. Given a complex value
$z$, construct the coherent state as

$\phi_{l;z}\left(x\right)=\sum_{n=0}^{\infty}z^{n}\mbox{e}_{\beta;n;l}\left(x\right)$

The shift is then

$\left[\mathcal{P}_{\beta}\phi_{l;z}\right]\left(x\right)=\frac{z}{\beta}\sum_{n=0}^{\infty}z^{n}\left(1+\mbox{e}_{\beta;n+1;l}\left(\frac{1}{2}\right)\right)\mbox{e}_{\beta;n;l}\left(x\right)$

This is not particularly useful, until one notices that for for certain values
of $\beta$, this contains nilpotent sub-series.

Specifically, fix a value of $n=N$ and consider those values of $\beta$ for
which $\mbox{e}_{\beta;N;l}\left(1/2\right)=-1$. This holds whenever
$\beta^{N}$ is an odd integer, that is, whenever
$\beta=\left(2m+1\right)^{1/N}$ (and, as always, $\beta\leq 2$). For these
special values of $\beta$, one has that
$\left[\mathcal{P}_{\beta}\mbox{e}_{\beta;N;l}\right]\left(x\right)=0$ and so
the functions

$\phi_{l;z;N}\left(x\right)=\sum_{n=0}^{N}z^{n}\mbox{e}_{\beta;n;l}\left(x\right)$

vanish after $N$ iterations of $\mathcal{P}_{\beta}$. That is, these can be
used to form a a basis in which $\mathcal{P}_{\beta}$ is nilpotent.
Conversely, letting $m$ and $N$ be free, the values for which
$\beta=\left(2m+1\right)^{1/N}$ are dense in the interval $\left[1,2\right)$
and so any $\beta$ is arbitrarily close to one with a nilpotent function
space. These values of $\beta$ are exactly the same values for which the bit
sequences given by eqn 4 eventually terminate in all zeros; i.e. become
periodic fixed points with period 1.

The existence of a dense set of fixed points is dual to the the existence of
nilpotent densities. That is, one “causes” or “forces” the other to happen.
This idea should be further elaborated, as it establishes a duality between
countable and uncountable sets, which has an element of curiosity to it.

Presumably, there are special values of $\beta$ which allow a periodic orbits
to originate from a dense set. Such values of $\beta$, and such periodic
orbits, should then correspond to specific self-similarities of the
$\phi_{l;z}\left(x\right)$ function, specifically manifesting as cyclic
behavior in
$\left(1+\mbox{e}_{\beta;n+1;l}\left(\frac{1}{2}\right)\right)^{p}$ for some
period $p$. Whether there is some similar manifestation for
$\mathcal{L}_{\beta}$ is wholly unclear; however, the examination of the
periodic orbits of the beta shift, undertaken in a later chapter, will provide
a strong clue.

###  3.4 Rotated Renyi-Parry function

A different class of almost-solutions starts with the Renyi-Parry invariant
measure defined in eqn 8. Using this, one may define a “rotated” function

$v_{\beta;z}\left(x\right)=\sum_{n=0}^{\infty}\frac{d_{n}\left(x\right)}{\beta^{n}}z^{n}$
(17)

where $d_{n}\left(x\right)=\varepsilon_{n}\left(2x/\beta\right)$ are the same
digits as defined by Renyi and Parry, just rescaled for the beta shift
convention being used here. That is,

$d_{n}\left(x\right)=\begin{cases}1&\mbox{if
}x<T^{n}\left(\frac{\beta}{2}\right)\\\ 0&\mbox{otherwise}\end{cases}$

and $T$ the beta shift map of eqn 3. The summation is clearly convergent (and
holomorphic) for complex numbers $z$ within the disk $\left|z\right|<\beta$.

Exploring this numerically, one finds that

$\left[\mathcal{L}_{\beta}v_{\beta;z}\right]\left(x\right)=\frac{1}{z}v_{\beta;z}\left(x\right)+C\left(\beta;z\right)$

where $C\left(\beta;z\right)$ is a constant independent of $x$ (or rather, a
constant for $x<\beta/2$ and zero otherwise). The fact that
$C\left(\beta;z\right)$ is a constant independent of $x$ can be taken either
as a humdrum fact, typical of the territory, or as a big unexplained surprise!
I prefer the later. The sequence of digits $d_{n}\left(x\right)$ depend
strongly on $x$. The function $v_{\beta;z}\left(x\right)$ depends strongly on
$x$. The digits $d_{n}\left(x\right)$ are entangled in an analytic series, in
very highly non-trivial form. This is worth pursuing to great extent.

First, some baby-steps. Combining the above expressions, one can write

$\displaystyle C\left(\beta;z\right)=$
$\displaystyle\left[\mathcal{L}_{\beta}v_{\beta;z}\right]\left(y\right)-\frac{v_{\beta;z}\left(y\right)}{z}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\frac{z^{n}}{\beta^{n}}\left[\frac{1}{\beta}d_{n}\left(\frac{y}{\beta}\right)+\frac{1}{\beta}d_{n}\left(\frac{y}{\beta}+\frac{1}{2}\right)-\frac{1}{z}d_{n}\left(y\right)\right]$

Again: this is a constant, independent of $y$ for $0\leq y<\beta/2$, and zero
for $y\geq\beta/2$. This only holds for the sum; individual terms are not
independent of $y$. The interesting limit is where $\left|z\right|\to\beta$
and so its convenient to define

$\displaystyle D\left(\beta;\zeta\right)=$ $\displaystyle\zeta\beta
C\left(\beta;\zeta\beta\right)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\zeta^{n}\left[\zeta
d_{n}\left(\frac{y}{\beta}\right)+\zeta
d_{n}\left(\frac{y}{\beta}+\frac{1}{2}\right)-d_{n}\left(y\right)\right]$

This is holomorphic on the unit disk $\left|\zeta\right|<1$, as each
individual $d_{n}$ is either zero or one; there won’t be any poles inside the
unit disk. Again, this is independent of $y$.

The equation is readily simplified. Set $y=0$, to obtain
$d_{n}\left(0\right)=1$. Cancelling terms, one obtains

$D\left(\beta;\zeta\right)=-1+\zeta\sum_{n=0}^{\infty}\zeta^{n}d_{n}\left(\frac{1}{2}\right)$
(18)

This is straight-forward to examine numerically; the disk is readily plotted,
and reveals what looks like a countable number of zeros in the disk
$\left|\zeta\right|<1$, and then many more in the limit $\left|\zeta\right|\to
1$. Each zero corresponds to an eigenfunction/eigenvalue pair, the
eigenfunction given by eqn 17. The table below lists some examples; the
numbers are accurate to about the last decimal place.

$\beta$ | $z$ | $\left|z\right|$ | $1/z$
---|---|---|---
1.8 | -1.591567859 | 1.591567859 | -0.6283112558
1.8 | -1.1962384 +i 1.216022231 | 1.705783215 | -0.4111213835 - i 0.4179206604
1.8 | 0.9919147363 +i 1.446092984 | 1.753590535 | 0.3225655308 -i 0.4702619429
1.6 | -1.063651387 +i 1.008959895 | 1.466067646 | -0.4948701876 -i 0.4694246429
1.4 | 0.550836432 +i 1.178171082 | 1.300579822 | 0.3256481633 -i 0.6965211931
1.2 | 0.9578845659 +i 0.6073301155 | 1.134192537 | 0.7446284155 -i -0.4721187476

These are not particularly meaningful numbers; they just give a flavor for
some locations of eigenvalues. The overall distribution is scattered; the
zeros appear in not very predictable locations, mostly not far from the edge
of the disk. Insight into this behavior is developed in depth in later
chapters. A typical eigenfunction is shown in figure 12; this is for the zero
listed in the last row of the table above. Although its unlike figure 1, it
does have the same general characteristics, belonging to the same family.

Figure 12: Typical Eigenfunction

Formula 18 will reappear in a later chapter, where it is found to describe
periodic orbits of the beta shift. It will serve to tie together the transfer
operator with the behavior of orbits.

This section ends with a deep mystery: why is $C\left(\beta;z\right)$
independent of the $y$ coordinate? How should it be explained? How can it be
put to good use? Might there be more of such identities? Or is there only this
one?

###  3.5 Analytic Ergodics

Why is $C\left(\beta;z\right)$ independent of the $y$ coordinate? And is this
surprising, or not surprising?

Perhaps it should not be surprising. The full shift (the Bernoulli shift) has
an absolutely flat, uniform distribution. This is not a surprise: real numbers
are uniformly distributed on the real number line. Pick almost any real
number: the binary digits are uniformly distributed. The FP eigenfunction of
the transfer operator for the Bernoulli shift is a constant. This is not a
surprise; the uniformity of the reals demands this.

Compare to the invariant measure of eqn 8, shown in the very first figure 1.
The figure clearly consists of flat plateaus; the flatness harking back to,
and “explained by” the flatness of the real numbers. But those flat regions
arise from eqn 17 (with $z=1$), and if one looks at the individual binary
digit sequences $d_{n}\left(x\right)$ for two different values of $x$, these
sequences become wildly, crazily, chaotically different; why should they sum
to the same value? This now seems to be profound, in some way that the
flatness of the reals is not.

Presumably, this should be known as “the fundamental theorem of analytic
ergodics”. Or at least, “the funamental theorem of analytic subshifts”. Oddly,
I’ve never heard of such a theorem, nor recollect any proof of it having
scrolled past my eyes. Perhaps it is known. It certainly deserves greater
fame; it seems like it would be quite the tool to unlock many of the mysteries
being fumbled-over in this text.

###  3.6 Iterated transfer operator

To understand the nature of the steady-state solution (the Frobenius-Perron
eigenstate), its is worth iterating on the recurrence relation for it, by
hand, the first few times. To do this, it is convenient to write it in the
form

$\left[\mathcal{L}_{\beta}f\right]\left(y\right)=\frac{\Theta\left(y\right)}{\beta}\left[f\left(\alpha\left(y\right)\right)+f\left(\omega\left(y\right)\right)\right]$

where $\Theta\left(y\right)=1$ if $y\leq\beta/2$ else zero; this is a step
function to denote the vanishing for the operator for $2y>\beta$. (This
differs from the use of $\Theta$ as the Heaviside step function in earlier
sections; the intent is the same, but the goal is to have a briefer notation
here. Which is which should be clear from context.) The functions
$\alpha\left(y\right)=y/\beta$ and
$\omega\left(y\right)=\frac{1}{2}+\alpha\left(y\right)$ are convenient
shorthands for symbolic iteration.

Iterating once gives

$\displaystyle\left[\mathcal{L}^{2}f\right]\left(y\right)=$
$\displaystyle\frac{\Theta\left(y\right)}{\beta^{2}}$
$\displaystyle\left[\Theta\left(\alpha\left(y\right)\right)\left[f\left(\alpha^{2}\left(y\right)\right)+f\left(\left(\omega\circ\alpha\right)\left(y\right)\right)\right]+\right.$
$\displaystyle\left.\Theta\left(\omega\left(y\right)\right)\left[f\left(\left(\alpha\circ\omega\right)\left(y\right)\right)+f\left(\omega^{2}\left(y\right)\right)\right]\right]$

Using a simplified notation
$g\left(y\right)=f\left(\alpha\left(y\right)\right)+f\left(\omega\left(y\right)\right)$
allows this to be iterated a third time:

$\displaystyle\left[\mathcal{L}^{3}f\right]\left(y\right)=$
$\displaystyle\frac{\Theta\left(y\right)}{\beta^{3}}$
$\displaystyle\left[\Theta\left(\alpha\left(y\right)\right)\left[\Theta\left(\alpha^{2}\left(y\right)\right)g\left(\alpha^{2}\left(y\right)\right)+\Theta\left(\omega\alpha\left(y\right)\right)g\left(\omega\alpha\left(y\right)\right)\right]+\right.$
$\displaystyle\left.\Theta\left(\omega\left(y\right)\right)\left[\Theta\left(\alpha\omega\left(y\right)\right)g\left(\alpha\omega\left(y\right)\right)+\Theta\left(\omega^{2}\left(y\right)\right)g\left(\omega^{2}\left(y\right)\right)\right]\right]$

and a fourth time, this time omitting the argument, and the various nesting
parenthesis.

$\displaystyle\left[\mathcal{L}^{4}f\right]\left(y\right)=$
$\displaystyle\frac{\Theta\left(y\right)}{\beta^{4}}$
$\displaystyle\left[\Theta\alpha\Theta\alpha^{2}\left[\Theta\alpha^{3}g\alpha^{3}+\Theta\omega\alpha^{2}g\omega\alpha^{2}\right]+\right.$
$\displaystyle\Theta\alpha\Theta\omega\alpha\left[\Theta\alpha\omega\alpha
g\alpha\omega\alpha+\Theta\omega^{2}\alpha g\omega^{2}\alpha\right]$
$\displaystyle\Theta\omega\Theta\alpha\omega\left[\Theta\alpha^{2}\omega
g\alpha^{2}\omega+\Theta\omega\alpha\omega g\omega\alpha\omega\right]$
$\displaystyle\left.\Theta\omega\Theta\omega^{2}\left[\Theta\alpha\omega^{2}g\alpha\omega^{2}+\Theta\omega^{3}g\omega^{3}\right]\right]$

Notice that the primary structure is given by a product of step functions.
This is more conveniently visualized as a tree:

For any given iteration, the result is the sum of the vertexes at a given
level, while the product of step functions is the product of the step
functions in the tree, following the path to each node. Because any particular
step function might be zero, it effectively acts to cut off the tree at that
location. It is therefore interesting to understand general products of the
$\alpha$ and $\beta$ functions.

It is convenient to define

$\gamma_{x}\left(y\right)=\frac{x}{2}+\frac{y}{\beta}$

so that $\alpha\left(y\right)=\gamma_{0}\left(y\right)$ and
$\omega\left(y\right)=\gamma_{1}\left(y\right)$, so that a general iterated
sequence of intermixed $\alpha$’s and $\omega$’s can be written uniformly in
terms of $\gamma$. Given a sequence of bits $b_{0}b_{1}b_{2}\cdots b_{n}$ with
each $b_{k}$ being either zero or one, the iterated sequence of functions can
be written as

$\left(\gamma_{b_{0}}\gamma_{b_{1}}\gamma_{b_{2}}\cdots\gamma_{b_{n}}\right)\left(y\right)=\frac{1}{2}\left[b_{0}+\frac{b_{1}}{\beta}+\frac{b_{2}}{\beta^{2}}+\cdots+\frac{b_{n}}{\beta^{n}}\right]+\frac{y}{\beta^{n+1}}$
(19)

So, for example:

$\alpha^{n}\left(y\right)=\frac{y}{\beta^{n}}$

while

$\omega^{2}\left(y\right)=\frac{1}{2}+\frac{1}{\beta}\left(\frac{1}{2}+\frac{y}{\beta}\right)$

and, in general, that

$\omega^{n}\left(y\right)=\frac{1}{2}\left[1+\frac{1}{\beta}+\frac{1}{\beta^{2}}+\cdots\frac{1}{\beta^{n-1}}\right]+\frac{y}{\beta^{n}}$

Iterated sequences of pairs of functions, of the form
$\gamma_{b_{0}}\gamma_{b_{1}}\gamma_{b_{2}}\cdots\gamma_{b_{n}}$ are
reminiscent of de Rham curves, which generalize Cesaro curves and the Koch
snowflake. The proper definition of a de Rham curve assumes the sequence is of
infinite length, and applies a certain continuity condition, and is generally
carried out on the complex plane, so that a continuous, nowhere-differentiable
curve results. Here, the curve is distinctly not continuous: eqn 19 is a
finite-length form of the shift series 5 which can be visualized as the
expander function pdr 9, as shown in figure 8.

###  3.7 The Tree Function

Given a bit sequence $\left(b_{k}\right)$ and value for $y$, define the tree
function as

$T_{\beta}\left(\left(b_{k}\right);y\right)=\Theta\left(y\right)\prod_{n=0}^{\infty}\Theta\left(\gamma_{b_{0}}\gamma_{b_{1}}\gamma_{b_{2}}\cdots\gamma_{b_{n}}\left(y\right)\right)$

For any given fixed sequence of bits and value of $y$, this function is either
zero or one. One way to understand this function is to ask how it varies for
fixed $\beta$ and $y$, but with the bit sequence coming from the Bernoulli
shift of eqn 2, so that $b_{n}=b_{n}\left(x\right)$. This simplifies notation,
so that one can write

$T_{\beta}\left(x;y\right)=T_{\beta}\left(\left(b_{k}\left(x\right)\right);y\right)=\Theta\left(y\right)\prod_{n=0}^{\infty}\Theta\left(\gamma_{x;n}\left(y\right)\right)$

with
$\gamma_{x;n}\left(y\right)=\gamma_{b_{0}}\gamma_{b_{1}}\gamma_{b_{2}}\cdots\gamma_{b_{n}}\left(y\right)$.
Its clear that the tree function has maximum support when $y=0$. Figure 13
shows several gamma functions, and the corresponding tree function that
results. Figure 14 shows the $x$ vs. $y$ behavior of the tree functions.
Figure 15 shows the $\beta$ vs. $x$ behavior of the functions. Figure 16 shows
a unified visualization of the three preceding charts.

Figure 13: Gamma functions

Examples of “typical” gamma functions. Both figures show gamma functions for
$\beta=1.6$; the one on the left shows them for $y=0$, while the one on the
right shows them for $y=0.7$. Every gamma function is a sequence of plateaus;
the zig-zag line is a high-order gamma, essentially showing the limiting case.
The tree function is unity whenever all of these curves are below $\beta/2$,
and is zero when above. So, for example, for the left figure, the tree
function is unity, for all values of $x$ less than about 0.4952; it drops to
zero, then returns to unity above $x=0.5$, until about 0.6221, when it briefly
plunges and rises again. Then, another dip, before finally settling to zero
near 0.6541. For the right figure, a high-order zig-zag rises above 0.8
somewhere near 0.4914; then $\gamma_{x;1}\left(0.7\right)$ rises above 0.8 and
stays there, driving the tree function to zero, rendering all other orders
irrelevant.

Figure 14: Tree functions

The above illustrate the $y$ vs. $x$ dependence of the tree functions; the
left image is for $\beta=1.4$, the right is for $\beta=1.6$. Green indicates
the regions where the tree function is unity, and black where it is zero. To
be clear, this shows $T_{\beta}\left(x;y\right)$ with $x$ and $y$ plotted
along the $x$ and $y$ axes. The tree functions shown in figure 13 are just two
horizontal slices taken from the right image: a slice along the bottom, and a
slice a bit above the middle.

Figure 15: Tree function variations

These figures illustrate the $\beta$ vs. $x$ dependence of the tree function.
The upper left shows $T_{\beta}\left(x;0\right)$, the upper right shows
$T_{\beta}\left(x;0.3\right)$, the lower left shows
$T_{\beta}\left(x;0.5\right)$, the lower right shows
$T_{\beta}\left(x;0.7\right)$. In each case, $x$ runs from 0 to 1 along the
$x$ axis, while $\beta$ runs from 1 to 2 along the vertical axis. As before,
green indicates where the tree function is unity, and black where it is zero.
The tree functions shown in figure 13 correspond to horizontal slices in the
first and last images. Note that many (possibly all??) of the green spikes in
the upper-left image reach all the way down to the bottom, although they are
mostly much thinner than a pixel and thus not rendered. The vague blue hazing
near the spikes is an attempt at anti-aliasing, to highlight the sharpness.

Figure 16: Tree function Unified Visualization

This figure presents a unified visualization of figures 13, 14 and 15. That
is, it depicts the $T_{\beta}\left(x;y\right)$ varying all three parameters.
The parameter$\beta$ runs from 1 at the bottom, to 2 at the top. The parameter
$x$ runs from 0 to 1, left to right. Because $T_{\beta}\left(x;y\right)$ is
either zero or one, the color is used to represent the largest value of $y$
for which $1=T_{\beta}\left(x;y\right)$. The color coding corresponds to red
for $y=1,$ green for $y=0.5$, blue for $y=0.25$ and black for $y=0$. Thus, for
example, figure 15 can be obtained directly from this, by setting a given
color, “or darker”, to black. The figure 14 represents a single fixed
horizontal slice through this figure, with the height of the rectangles in
figure 14 corresponding to the color in this figure.

###  3.8 Haar Basis Matrix Elements

The symmetric Haar wavelets are built from the mother wavelet

$h\left(x\right)=\begin{cases}1&\mbox{for }0\leq x<1/2\\\ -1&\mbox{for
}1/2\leq x<1\end{cases}$

and has individual wavelets given by

$h_{nj}\left(x\right)=2^{n/2}h\left(2^{n}x-j\right)\;\mbox{ for }0\leq j\leq
2^{n}-1$

The matrix elements of the transfer operator are

$\left\langle mi\left|{\cal
L}_{\beta}\right|nj\right\rangle=\int_{0}^{1}h_{mi}\left(x\right)\left[\mathcal{L}_{\beta}h_{nj}\right]\left(x\right)dx$

where the operator $\mathcal{L}_{\beta}$ is given by eqn 13. Computing these
by hand promptly pushes into a big mess. One can obtain explicit expressions,
just that they are tedious to obtain. Some preliminary observations include
that

$\left\langle mi\left|{\cal L}_{\beta}\right|nj\right\rangle=0\;\mbox{ if
}\beta\leq i/2^{m-1}$

because the transfer operator vanishes above $\beta/2$. In the same vein,
matrix elements vanish unless

$\left[\frac{i}{2^{m}},\frac{i+1}{2^{m}}\right]\cap\left[\frac{\beta
j}{2^{n}},\frac{\beta\left(j+1\right)}{2^{n}}\right]\neq\emptyset$

or if

$\left[\frac{i}{2^{m}},\frac{i+1}{2^{m}}\right]\cap\left[\beta\left(\frac{j}{2^{n}}-\frac{1}{2}\right),\beta\left(\frac{j+1}{2^{n}}-\frac{1}{2}\right)\right]\neq\emptyset$

In all other cases, the Haar wavelets completely fail to overlap, and thus the
matrix elements are zero. In addition, only three pairs of wavelets overlap in
a non-zero fashion. That is, for a fixed $m,n$ and $j$, there are at most six
different values of $i$ for which the matrix elements are non-vanishing: the
first three of these are the values for which

$\frac{\beta
j}{2^{n}}\in\left[\frac{i}{2^{m}},\frac{i+1}{2^{m}}\right]\;\mbox{ or
}\;\frac{\beta\left(j+\frac{1}{2}\right)}{2^{n}}\in\left[\frac{i}{2^{m}},\frac{i+1}{2^{m}}\right]\;\mbox{
or
}\;\frac{\beta\left(j+1\right)}{2^{n}}\in\left[\frac{i}{2^{m}},\frac{i+1}{2^{m}}\right]$

and likewise for three more. The observation is that the integral vanishes
unless the first wavelet intersects an edge transition of the second wavelet.

The primary failure of this basis is that there is no obvious way to
diagonalize the transfer operator in this basis. There is no obvious way of
solving it, of finding it’s eigenfunctions and eigenvalues, other than by
brute-force numerical attack.

###  3.9 Julia Set

Consider the two iterators
$a_{0}\left(y\right)=\min\left(\frac{\beta}{2},\beta y\right)$ and
$a_{1}\left(y\right)=\max\left(0,\beta y-\frac{\beta}{2}\right)$.
Individually, they are the two arms of the beta shift. Here, they have been
separated from each other, so that the full domain $0\leq y\leq 1$ is allowed.
Exploring all possible inter-iterations for these gives the Julia set for the
transfer operator: it indicates where a point “came from”, for the iterated
transfer operator. There are several related ways to visualize this. One way
is to fix $y$ and then, given a bit-sequence $\left(b_{n}\right)$ to compute

$j\left(\left(b_{n}\right)\right)=a_{b_{o}}\circ a_{b_{1}}\circ
a_{b_{2}}\circ\cdots\left(y\right)$

Figure 17 shows a visualization for finite bit-sequences: in essence, the very
first few iterations. Although it is similar to figure 9, it is not the same.

Figure 17: Julia Set visualization

Consider the binary tree of dyadic fractions: that is, the tree whose rows are
1/2, (1/4 3/4), (1/8 3/8 5/8 7/8), … Consider a function $J$ on this tree. For
the head of the tree, set $J\left(1/2\right)=\beta$. For the next row, set
$J\left(1/4\right)=a_{0}\left(J\left(1/2\right)\right)$ and
$J\left(3/4\right)=a_{1}\left(J\left(1/2\right)\right)$. Iterate in this
fashion so that
$J\left(\left(2k-1\right)/2^{n+1}\right)=a_{0}\left(J\left(k/2^{n}\right)\right)$
and
$J\left(\left(2k+1\right)/2^{n+1}\right)=a_{1}\left(J\left(k/2^{n}\right)\right)$
recursively. This produces a function $J$ taking values on every dyadic
fraction $k/2^{n}$.

In the above figure, $\beta$ runs from 1 at the bottom to 2 at the top. A
single horizontal slice through the image shows a color-coded version of $J$,
with red coding values near 1, green coding values near 1/2 and blue, fading
to black coding values of 1/4 and less. Note that there are many faint blue
lines that extend quite far down, but not all the way down: these form a
stair-step. The image is 1024 pixels wide: it shows the first ten rows of the
binary tree. Although this image is similar to figure 9, it differs in many
details.

For a related notion, consider the definition of “laps”, from Jeffrey Lagerias
_etal_.[24].

##  4 Hessenberg basis

There is a set of Haar-like wavelets in which the transfer operator is of the
form of a Hessenberg operator - that is, the operator becomes almost upper-
diagonal, with only one diagonal, just below the main diagonal, that is non-
zero. Explicitly, the transfer operator $\mathcal{L}_{\beta}$ has matrix
entries $\left[\mathcal{L}_{\beta}\right]_{ij}$ such that
$\left[\mathcal{L}_{\beta}\right]_{ij}=0$ whenever $i>j+1$. A matrix having
this form is called a Hessenberg matrix; such matrices have various
interesting properties; among others, they generalize the Jacobi matrix. This
chapter explicitly constructs an infinite-dimensional Hessenberg matrix, which
may now be called a Hessenberg operator.

Hessenberg operators occur naturally in spectral measure theory; some of this
will be reviewed in several later chapters. To get a flavor for what is to
come: Given a Hessenberg operator, one may construct a system of orthogonal
polynomials that provide a basis for square-integrable holomorphic functions
on some domain of the complex plane. Such a space is called a Berman space; in
this sense it generalizes the Jacobi operator for real Borel measures. This
basis of polynomials in turn allows the Hessenberg operator to be explicitly
seen as a shift operator on that domain, with
$\left[Hf\right]\left(z\right)=zf\left(z\right)$ for $H$ the Hessenberg
operator and $f\left(z\right)$ a holomorphic function (specifically a Bergman
function) on the Bergman domain. But all of this is for later chapters; its
mentioned here only to whet the appetite.

###  4.1 Hessenberg wavelet basis

The transfer operator $\mathcal{L}_{\beta}$ can be fairly easily brought into
Hessenberg matrix form. A sequence of of orthonormal functions is constructed
in this section; when used as a basis, the transfer operator becomes almost
upper-diagonal.

The trick to the construction is to define wavelets such that the transfer
operator applied each wavelet causes the end-points of the wavelet to exactly
line up with the end- or mid-points of previous wavelets, thus avoiding the
nasty interval-overlap algebra required with the Haar basis. This is
accomplished by carefully picking the midpoint of the next wavelet in the
sequence to be located exactly at the discontinuity of the transfer operator
applied to the previous wavelet.

The construction proceeds as follows. Let

$\psi_{0}\left(x\right)=\begin{cases}\frac{1}{\sqrt{\beta/2}}&\mbox{for }0\leq
x\leq\beta/2\\\ 0&\mbox{for }\beta/2<x\leq 1\end{cases}$

Consider ${\cal L}_{\beta}\psi_{0}$. It is the sum of two parts: two step-
functions; one which is constant for $x\leq\beta/2$ and another that is
constant for $\frac{x}{\beta}+\frac{1}{2}\leq\frac{\beta}{2}$. Solving
explicitly for the location of the step, it is
$x=\beta\left(\beta-1\right)/2$. For convenience, define
$m_{1}=\beta\left(\beta-1\right)/2$ and $m_{0}=\beta/2$. These will anchor a
series of midpoints, beginning with $m_{-1}=0$. Using the midpoint $m_{1}$,
construct the wavelet

$\psi_{1}\left(x\right)=\begin{cases}\frac{1}{m_{1}}\sqrt{\frac{m_{1}\left(m_{0}-m_{1}\right)}{m_{0}}}&\mbox{for
}0\leq x\leq m_{1}\\\
\frac{-1}{m_{0}-m_{1}}\sqrt{\frac{m_{1}\left(m_{0}-m_{1}\right)}{m_{0}}}&\mbox{for
}m_{1}<x\leq m_{0}\\\ 0&\mbox{for }m_{0}<x\leq 1\end{cases}$

Note that this is normalized to unit length:
$\int_{0}^{1}\left|\psi_{1}\left(x\right)\right|^{2}dx=1$ and that it is
explicitly orthogonal to the first:
$\int_{0}^{1}\psi_{1}\left(x\right)\psi_{0}\left(x\right)dx=0$.

Consider ${\cal L}_{\beta}\psi_{1}$. As always, it is the sum of two parts.
The midpoint of $\psi_{1}$ is at $m_{1}=\beta\left(\beta-1\right)/2$ and this
mid-point is mapped to one of two different places. If $m_{1}<1/2$ then it is
mapped to $m_{2}=\beta m_{1}$ else it maps to
$m_{2}=\beta\left(m_{1}-1/2\right)$. Thus, if $m_{1}<1/2$, define

$\psi_{2}\left(x\right)=\begin{cases}0&\mbox{for }0\leq x\leq m_{1}\\\
\frac{1}{\left(m_{2}-m_{1}\right)}\sqrt{\frac{\left(m_{2}-m_{1}\right)\left(m_{0}-m_{2}\right)}{m_{0}-m_{1}}}&\mbox{for
}m_{1}\leq x\leq m_{2}\\\
\frac{-1}{\left(m_{0}-m_{2}\right)}\sqrt{\frac{\left(m_{2}-m_{1}\right)\left(m_{0}-m_{2}\right)}{m_{0}-m_{1}}}&\mbox{for
}m_{2}<x\leq m_{0}\\\ 0&\mbox{for }m_{0}<x\leq 1\end{cases}$

else define

$\psi_{2}\left(x\right)=\begin{cases}\frac{1}{m_{2}}\sqrt{\frac{m_{2}\left(m_{2}-m_{1}\right)}{m_{1}}}&\mbox{for
}0\leq x\leq m_{2}\\\
\frac{-1}{\left(m_{1}-m_{2}\right)}\sqrt{\frac{m_{2}\left(m_{2}-m_{1}\right)}{m_{1}}}&\mbox{for
}m_{2}\leq x\leq m_{1}\\\ 0&\mbox{for }m_{1}<x\leq 1\end{cases}$

Because each end of the interval on which $\psi_{2}$ is non-zero lies entirely
within one of the constant arms of $\psi_{1}$, one has, by construction, that
$\int_{0}^{1}\psi_{2}\left(x\right)\psi_{1}\left(x\right)dx=0$ (and, of
course, $\int_{0}^{1}\psi_{2}\left(x\right)\psi_{0}\left(x\right)dx=0$.)

The rest of the basis can be constructed iteratively, based on these examples.
The midpoints are given by iterating 3 on $m_{0}=\beta/2$, so that
$m_{p}=T_{\beta}\left(m_{p-1}\right)=T_{\beta}^{p}\left(m_{0}\right)$ is the
$p$’th iterate of $\beta/2$. Let $m_{l}$ be largest midpoint smaller than
$m_{p}$ (and $l<p$); let $m_{u}$ be the smallest midpoint larger than $m_{p}$
(and $l<p$). Let $m_{-1}=0$ initiate the sequence by providing the smallest-
possible “midpoint”; $m_{0}=\beta/2$ already provides the largest possible.

Then define

$\psi_{p}\left(x\right)=\begin{cases}0&\mbox{for }0\leq x\leq m_{l}\\\
\frac{C_{p}}{\left(m_{p}-m_{l}\right)}&\mbox{for }m_{l}\leq x\leq m_{p}\\\
\frac{-C_{p}}{\left(m_{u}-m_{p}\right)}&\mbox{for }m_{p}<x\leq m_{u}\\\
0&\mbox{for }m_{u}<x\leq 1\end{cases}$ (20)

By construction, this has the property that
$\int_{0}^{1}\psi_{p+1}\left(x\right)\psi_{n}\left(x\right)dx=0$ for any
$n<p+1$. The normalization constant is

$C_{p}=\sqrt{\frac{\left(m_{p}-m_{l}\right)\left(m_{u}-m_{p}\right)}{m_{u}-m_{l}}}$

which is determined by requiring that
$\int_{0}^{1}\left|\psi_{p}\left(x\right)\right|^{2}dx=1$.

###  4.2 Matrix Elements

The above-defined basis provides the Hessenberg representation for the
transfer operator. Defining

$\left\langle n\left|{\cal
L}_{\beta}\right|m\right\rangle=\int_{0}^{1}\psi_{n}\left(x\right)\left[\mathcal{L}_{\beta}\psi_{m}\right]\left(x\right)dx$
(21)

this has the expected Hessenberg form, in that

$\left\langle n\left|{\cal L}_{\beta}\right|m\right\rangle=0\quad\mbox{ for
}n>m+1$

This is just one diagonal short of being actually solvable. A visualization of
the matrix elements is shown in figure 18.

Figure 18: Hessenberg Operator Matrix Elements

Six illustrations of the absolute value of the matrix elements $\left\langle
n\left|{\cal L}_{\beta}\right|m\right\rangle$ for the transfer operator
$\mathcal{L}_{\beta}$ for (left to right, top to bottom) $\beta=$1.1, 1.2,
1.3, 1.6, 1.90, 1.998 and $0\leq n,m<48$ in the Hessenberg basis. The red
color represents values of 0.66 or larger, green represents values of 0.33 and
blue and darker correspond to 0.16 or less. Almost all matrix elements are in
fact precisely zero; black pixels in these images correspond to matrix
elements that are zero. Note that the almost all of the diagonal matrix
elements are exactly zero: that is $\left\langle n\left|{\cal
L}_{\beta}\right|n\right\rangle=0$ for most $n$. The bright-red pixels are
just below the diagonal: for most $n$, one has that $\left\langle
n+1\left|{\cal L}_{\beta}\right|n\right\rangle\apprge 0.5$ with the occasional
blueish pixel suggesting a smaller value. These two, taken together, suggests
that the eigenvalue spectrum is rapidly decreasing. The first few images
suggests a regular pattern that gets increasingly compressed and chaotic as
$\beta$ increases. More-or-less the sane structure prevails if one instead
zooms out to look at the 600x600 submatrix; animating with fine-grained steps
in $\beta$ does not result in an interesting animated movie.

###  4.3 Completeness

The Hessenberg basis construction gives a countable set of $\psi_{n}$ that is
an orthonormal basis on the unit interval:
$\int_{0}^{1}\psi_{m}\left(x\right)\psi_{n}\left(x\right)dx=\delta_{mn}$. Are
they complete? Obviously the $\left\\{\psi_{n}\right\\}$ cannot be complete on
the unit interval, as they all vanish for $\beta/2<x$. Perhaps they are
complete on the interval $[0,\beta/2]$, where they are already orthonormal:
$\int_{0}^{\beta/2}\psi_{m}\left(x\right)\psi_{n}\left(x\right)dx=\delta_{mn}$.

A numerical exploration shows that the midpoints $m_{p}$ are dense in the
interval $(0,\beta/2)$, and so this suggests that the basis should be
considered to be “sufficiently complete” on the interval $[0,\beta/2]$. The
distribution of the $m_{p}$ follow exactly the distribution of the invariant
measure. Convergence is uniform to the same degree that the midpoints
“eventually” fill in and become dense in some interval. Renyi[1] and Parry[2]
do more: they show that the midpoint process is ergodic (Parry points out that
it’s weakly mixing), and provide a formal proof that the distribution is one
and the same as the invariant measure.

The above has some exceptions: there are some values of $\beta$ for which the
midpoint $m_{0}$ iterates $x=1/2$, wherupon iteration stops (i.e. iterates to
zero), or becomes cyclic (forming a periodic orbit). Which is which depends on
how the point $1/2$ is treated by the map. These values of $\beta$ are
potential “trouble spots”, and are explored in greater detail in the next
chapter. They are dense in the interval $1<\beta<2$, but they form a countable
set that can be taken to be of measure zero. Thus, most “most” values of
$\beta$ are not problematic. Excluding the trouble spots, the Hessenberg basis
can be taken to be complete.

Clearly, the $\psi_{n}$ span some subspace; do they span the Hilbert space
$L_{2}\left[0,\beta/2\right]$ of square-integrable functions on the interval
$[0,\beta/2]$? To what degree can one legitimately write

$\delta\left(y-x\right)=\sum_{n=0}^{\infty}\psi_{n}\left(y\right)\psi_{n}\left(x\right)$

as a resolution of the identity?

The question of completeness dogs some “obvious” assumptions one wants to
make. For example, if the set of states is complete, and the resolution of the
identity holds, then one expects that the transfer operator resolves to the
iterated function:

$\delta\left(y-\left(\beta x\,\mod
1\right)\right)=\sum_{n=0}^{\infty}\sum_{m=0}^{\infty}\psi_{n}\left(y\right)\left\langle
n\left|{\cal L}_{\beta}\right|m\right\rangle\psi_{m}\left(x\right)$

It is fun to verify that the world works as one expects it to work: the above
can be verified to hold numerically, for sums limited to a finite cutoff.

###  4.4 Numerical Eigenvalues

Given the apparent sparsity visible in figure 18, one might think that the
eigenvalue problem is fairly stable, numerically. It is not all that much.
Numerical exploration suggests that the spectrum is on or near a circle lying
in the complex plane222This was confirmed with both GSL gsl_eigen_nonsymmv()
and Lapack DHSEQR solvers, exploring the principle submatrix of various sizes,
up to about $2000\times 2000$ entries. Both systems agree to at least six
decimal places, if not more. Both show sporadic eigenvalues off the circle,
but these are not numerically stable; ergo, the only valid eigenvalues are
those on the circle. The matrix entries were constructed using the midpoint
algorithm, described in the last section. To verify that they are accurate,
several techniques were used: numerical integration to confirm orthogonality,
and the use of the GnuMP multi-precision library to push up accuracy., of
radius $\left|\lambda\right|=1/\beta$ (ignoring, that is, the leading
eigenvalue of 1, which is easily found).

To be clear, this is a numerical exploration of the $N\times N$ principle
submatrix of $\left\langle n\left|{\cal L}_{\beta}\right|m\right\rangle$. The
eigenvalue problem being posed is to find a vector
$\vec{v}=\left(v_{k}\right)_{k=0}^{N}$ that solves

$\sum_{m=0}^{N}\left\langle n\left|{\cal L}_{\beta}\right|m\right\rangle
v_{m}=\lambda v_{n}$

for some constant $\lambda$ (with the set of possible $\lambda$ depending on
$N$, of course).

There are various pitfalls in extrapolating from this to the $N\to\infty$
limit. For the next few paragraphs, consider only some notion of a “minimal”
extension from finite $N$ to the limit. That is, for each finite $N$, one has
a finite set of eigenvalues and eigenvectors. In the limit, there may be
accumulation points: points where the eigenvalues accumulate to a limit point,
in a standard topological sense. What should that that topological space be?
For finite $N$, all eigenvectors are explicitly summable, and thus can be
taken to belong to any Banach space $\ell_{p}$. One may as well take $p=2$ the
Hilbert space, and normalize the eigenvectors $\vec{v}$ so that
$1=\sum_{m=0}^{N}v_{m}^{2}$.

For finite $N$, it appears that “most” eigenvalues $\lambda$ are “near” the
circle $\left|\lambda\right|=1/\beta$, and that they seem to be very uniformly
distributed around this circle. The numerical results indicate that in the
limit $N\to\infty$, that the scare-quotes “most” becomes “almost all” in the
usual sense. Similarly, “near” appears to mean that for any given $\lambda$ at
finite $N$, one has that
$\left|\lambda\right|-1/\beta\sim\mathcal{O}\left(1/N\right)$. As to
uniformity, it seems that the spacing between nearest neighbors is also
$\mathcal{O}\left(1/N\right)$, and that there are no “premature” accumulation
points: eigenvalues never get any closer than $\mathcal{O}\left(1/N\right)$,
either.

Thus, the minimal closure, the minimal extrapolation to limit points strongly
suggests that the limit points really do lie, uniformly distributed, on the
circle $\left|\lambda\right|=1/\beta$. Then, writing a given accumulation
point as $\lambda=\beta^{-1}\exp 2\pi i\phi$, what the numerics do not reveal,
or, at least, do not easily reveal, is whether the allowed values of $\phi$
are always rational, irrational or might have some other regular structure.
The numerical exploration does suggest that the eigenvalues are dense on the
circle. Certainly it is the case Hessenberg basis is countable, an so one
would expect the eigenvalue spectrum obtained in this way to be at least
countable, as well. Whether it is also uncountable seems unknowable in this
naive sense.

This question is interesting because if only rational $\phi$ are allowed, then
the decaying eigenfunctions belong to a cyclic group, and exhibit an exact
form of Poincaré recurrence as they decay. If irrational $\phi$ are allowed,
then the decaying eigenfunctions are at least ergodic.

For $\beta=2$, the $\beta$-transform is the Bernoulli shift, the transfer
operator is solvable, and the spectrum is exactly known. This has been
explored by various authors[28]. I’ve written extensively about this spectrum
and the eigenvalues in other texts[29, 30, 31]. To recap, it takes several
forms, depending on the function space that one chooses to work in. If one
restricts oneself to polynomial eigenfunctions, then the spectrum is real,
non-negative (it has an extensive kernel) and has eigenvalues of $2^{-n}$ for
all $n$. The eigenfunctions are the Bernoulli polynomials. Restricting to
square-integrable eigenfunctions, the spectrum continuous, having eigenvalues
on the unit disk in the complex plane. The continuous-spectrum eigenfunctions
(for eigenvalues other than $2^{-n}$) can be understood in several ways: if
forced to be differentiable, then they are not bounded (they diverge) at the
endpoints of the interval. If forced to be bounded, then they are fractal
(non-smooth) over the entire interval. The unitary spectrum corresponds to
differentiable-nowhere eigenfunctions (wait, or continuous-nowhere? I forget.)

A pair of plausible, numerically-extracted eigenfunctions are shown in image
19.

Figure 19: Decaying Eigenfunction, Period Two

This shows a numerically-computed decaying eigenfunction of period two, for
$\beta=1.6$. It is period two, in that it corresponds to an eigenvalue of
$\lambda=-1/\beta=-0.625$, so that after one iteration of
$\mathcal{L}_{\beta}$, the sign flips. This can be confirmed, numerically:
after one iteration, the sign really does flip, to within numerical errors.
This was computed by numerically diagonalizing the $861\times 861$ matrix
given by the lowest terms of eqn 21, and then graphing the eigenvector closes
to $\lambda=-0.625$ (The GnuMP library was used to provide the required level
of precision in the calculations.)

Although this figure is drawn with curves labeled “real” and “imaginary”, this
is a bit fantastic, and is a numeric artifact. For any period-two
eigenfunction, the real and imaginary parts would have no coupling, and would
be independent of each other; either one could be set to zero and one would
still have a valid eigenfunction. This differs from the case of period-three
and higher, where the real and imaginary parts are expected to mix. (Nor are
the two components orthogonal, as one might expect.) The eigenfunction is also
fantastic in that only slightly different numerics result in a completely
different eigenfunction being computed. Even the functions resulting from
diagonalizing the $863\times 863$ matrix differ fair amount from those arising
from the $861\times 861$ matrix; there’s only a general resemblance. This is
not entirely surprising: the magnitude of the basis coefficients decays very
slowly; even at $861$, that are still on the order of $10^{-3}$, and thus
contribute strongly.

Computed eigenfunctions for period-three are not dissimilar, nor are the ones
for other values of $\beta$. They do seem to start having the general
oscillatory character of $\sin\left(1/x\right)$ as $\beta\to 1$, but its not
clear if this is a numeric artifact, or something real. The wildness of these
functions contrast sharply with the seemingly tame $\lambda=1$ eigenfunctions
shown in figure 1. Compare to figure 12, which paves the way.

Presumably, the spectrum can be related to the lap-counting function, given by
Lagarias[24].

###  4.5 (Non-)Unitarity

The numerical results suggest a hypothesis that perhaps some fragment of
$\mathcal{L}_{\beta}$ is unitary, as it is ordinarily the case that when
eigenvalues appear on the unit circle, it is because an operator is unitary.
That does not seem to be the case here. Specifically, define the Frobenius-
Perron eigenvector $\rho$ as the one satisfying $\mathcal{L}_{\beta}\rho=\rho$
and normalizing it to unit length, so that $\left\|\rho\right\|=1$ in the
Hilbert (mean-square) norm. Define the reduced operator $\mathcal{R}_{\beta}$
in terms of the matrix elements

$\frac{1}{\beta}\left\langle n\left|{\cal
R}_{\beta}\right|m\right\rangle=\left\langle n\left|{\cal
L}_{\beta}\right|m\right\rangle-\left\langle\rho|n\right\rangle\left\langle\rho|m\right\rangle$

That is, it is just the beta shift operator, with the Frobenius-Perron
eigenvector removed, so that $\mathcal{R}_{\beta}\rho=0$ . Its rescaled, so
that the remaining eigenvectors of $\mathcal{R}_{\beta}$ lie on the unit
circle. Is this operator unitary in any way? That is, might either
$\mathcal{R}_{\beta}\mathcal{R}_{\beta}^{\dagger}$ or
$\mathcal{R}_{\beta}^{\dagger}\mathcal{R}_{\beta}$ be the identity? Here, the
dagger $\dagger$ is just the transpose, as $\mathcal{R}_{\beta}$ is purely
real. Numerical exploration clearly shows that $\mathcal{R}_{\beta}$ is
neither unitary on the left nor on the right. Not a surprise, but does leave
the understanding of $\mathcal{L}_{\beta}$ in a curious situation.

Perhaps it is not enough to subtract the invariant measure: The zeros of the
formula 18 lying inside the disk must be subtracted as well. There seems to be
a cutable number of these; the subtraction won’t be straight-forward.

###  4.6 Invariant Measure

Let $v_{n}$ be the Ruelle-Frobenius-Perron eigenvector in the Hessenberg
basis. That is, let $v_{n}$ be the vector that solves

$\sum_{m=0}^{\infty}\left\langle n\left|{\cal L}_{\beta}\right|m\right\rangle
v_{m}=v_{n}$ (22)

This is readily computed numerically, and it is straightforward to verify the
numerics by confirming that

$\rho\left(x\right)=\sum_{m=0}^{\infty}v_{m}\psi_{m}\left(x\right)$

is the invariant measure of equations 14,15, with the $\psi_{k}\left(x\right)$
being the wavelets of eqn 20. This expansion seems to “make sense”, as the
discontinuities seen in the graph of $\rho\left(x\right)$ in figure 1 occur at
exactly the midpoints $m_{p}$ and the size of each discontinuity appears to
get smaller as $p$ gets larger. Given that the wavelet
$\psi_{p}\left(x\right)$ has its central discontinuity at $m_{p}$ and is
bounded on left and right by midpoints of lower order, this expansion seems to
be very natural. This is supported by the diagram 20, which depicts the values
of $v_{n}$ as a function of $n$ for selected values of $\beta$. These values
of $v_{n}$ are real, positive, and quickly get small; there are no
difficulties or issues of convergence.

Figure 20: Frobenius-Perron Eigenvector Coefficients

The coefficients $v_{n}$ solving eqn 22 as a function of $n$, for various
values of $\beta$. Note that the coefficients are all real and positive. These
can be obtained in two different ways: either by numerically diagonalizing the
matrix equation of 22 or by numerically integrating
$\int_{0}^{1}\rho\left(x\right)\psi_{n}\left(x\right)dx$. Either method gives
the same results; diagonalization is far, far quicker. The slope appears to go
as approximately $v_{m}\sim C\beta^{-m}$ with $C=0.02$ roughly.

Is there some simple expression for the values of $v_{n}$ as a function of
$\beta$? If so, it must be formed using some sort of fractal shift. Figure 21
illustrates $v_{1}$ through $v_{5}$.

Figure 21: Perron-Frobenius Eigenvector Coefficients

This figure shows $v_{1}$ through $v_{5}$ as $\beta$ is varied. The most
prominent spike is located at $\beta=\varphi=1.618\cdots$ the Golden Ratio.
All spikes correspond to orbits that terminate in a fixed point after a finite
number of iterations. The root cause and location of the spikes is shown in
figure 23.

The orbit of the midpoint is correlated with value of the coefficients,
illustrated in figure 22. The midpoint polynomial for
$m_{p}=T_{\beta}^{p}\left(\beta/2\right)$, given in eqn 24, is compared to
$v_{m}\beta^{m}$. It can be seen to “line up”. The two are somehow related;
its not clear just how.

Figure 22: Orbits and Coefficients

This figure compares the midpoint orbit to the coefficients, providing
evidence for the hypothesis stated in the text. The midpoint orbit is just
$m_{p}=T_{\beta}^{p}\left(\beta/2\right)$. Because $\beta=1.1$ in this figure,
the discontinuities are infrequent and appear to be quasi-regular (they are
ultimately fully chaotic), as the midpoint mostly just walks up to where it is
knocked down again. The “coefficient” curve is a graph of $10v_{p}\beta^{p}$
for $p$ running along the horizontal axis. This is the same $v_{p}$ as
discussed in the text, and previously shown in figure 20. Here, its rescaled
by its asymptotic behavior, and a constant of 10 to place it on the same
vertical scale. The discontinuitites clearly line up. The relationship is
clearly non-trivial.

###  4.7 Generating Function

The truncated ordinary generating function associated with the eigenvector of
eqn 22 is

$G_{N}\left(z\right)=\sum_{m=0}^{N}v_{m}z^{m}$

with the ordinary generating function being the limit $N\to\infty$. A
numerical study of this function indicates that most of the $N$ zeros of
$G_{N}$ are arranged approximately on a circle of radius $\beta$. The
arrangement appear to be quite uniform, with more-or-less equi-distant spacing
of the zeros. As $N$ increases, it seems that more of the zeros get closer to
the circle, although the numerical instabilities associated with double-
precision math make this difficult to control; an arbitrary-precision
eigenvalue solver would be needed to confirm this behavior.

If this behavior persists, and it seems that it will, then the limit
$N\to\infty$ cannot be taken, and the ordinary generating function, as an
analytic function, can’t exist, _per se_ , as it would be uniformly zero
inside the disk. Thus, the zeros already found by means of eqn 18 seem to come
to the rescue: these are located inside the disk; perhaps these are
masquerading as “numerical instabilities”, and should be taken as actually
existing, and not spurious.

In the next chapter, it will be seen that circles of zeros in the complex
plane is a recurring theme. This suggests a hypothesis that somehow it might
hold that

$\sum_{m}^{N}v_{m}\left(\beta z\right)^{m}\sim z^{N+1}-\sum_{k}b_{k}z^{k}$

as both sides have zeros arranged in circles of unit radius. The right hand
side is defined and explored in detail in the next chapter. Superficially,
this hypothesis is clearly false: coefficients on the left are all real and
positive; coefficients on the right - the $b_{k}$, are bits, either zero or
one. Yet both exhibit a circle of zeros.

XXX This section is awkward. Revise it or cut it.

###  4.8 Givens rotations

An open question: A Hessenberg matrix can be brought to solvable form by
applying a sequence of Givens rotations. Is the sequence of angles that appear
in these rotations meaningful in any way, or are they just some form of
uninteresting junk?

##  5 Periodic Orbits

The iteration of the midpoint, used to construct the Hessenberg basis, works
well, unless the midpoint iterates to hit the point $x=1/2$ where the map has
a discontinuity. Here, iteration stops: at the next step, this point is
defined to iterate to zero, in eqn 3. Zero is a fixed point, and so there is
nowhere further to go. This occurs for certain values of $\beta$: after a
finite number for steps, the midpoint $m_{0}=\beta/2$ iterates to 1/2. This
section explores these special values of $\beta$.

Aside from the definition in eqn 3, one can consider the modified map, where
the less-than sign has been altered to a less-than-or-equals:

$T_{\beta}^{\leq}(x)=\begin{cases}\beta x&\mbox{ for }0\leq
x\leq\frac{1}{2}\\\ \beta\left(x-\frac{1}{2}\right)&\mbox{ for
}\frac{1}{2}<x\leq 1\end{cases}$

In this map, the point $x=1/2$ iterates to $\beta/2$, which is just the
initial midpoint itself. In this case, the halted orbits become periodic
orbits. There is a third possibility, to simply remove the points 0, 1 and 1/2
from the domain:

$T_{\beta}^{<}(x)=\begin{cases}\beta x&\mbox{ for }0<x<\frac{1}{2}\\\
\beta\left(x-\frac{1}{2}\right)&\mbox{ for }\frac{1}{2}<x<1\end{cases}$

In this case, if the midpoint iterates to 1/2, it can be taken to simply have
exited the domain of validity.

All three variants can be considered together, so that the “true” beta shift
is taken as the quotient space or identification space[32] of the three
variants, in the strict topological sense of a quotient space. Thus,
interestingly, for the beta shift, the periodic orbits and the fixed point
both belong to the same equivalence class. This has some interesting
implications when one compares the beta shift to other iterated maps, such as
the logistic map, which have non-trivial stable regions. Topologically, it
would seem that one can perform a kind of surgery, attaching stable regions
exactly into those spots where, in the beta shift, one has an equivalence
class. This solves (at least for me) the long-standing problem of exactly how
to properly describe the topological conjugacy between different kinds of
iterated maps.

###  5.1 The $\beta$-generalized Golden Ratio

The above wavelet basis seems to be well-behaved, except when
$\beta=\varphi=\left(1+\sqrt{5}\right)/2$ the Golden Ratio. In this situation,
one has that $m_{0}=\varphi/2$ and $m_{1}=1/2$. At this location, further
iteration breaks down. That is, $m_{2}=T_{\varphi}\left(m_{1}\right)$ can
either be taken to be $m_{2}=0$ or $m_{2}=m_{0}$. In the former case,
iteration simply stops; in the later case, it repeats, again, without
generating new midpoints that can provide a workable basis.

Working backwards, this issue re-appears whenever the $p$’th iterate
$m_{p}=T_{\beta}^{p}\left(m_{0}\right)$ lands at the discontinuity, so that
one may take either $m_{p}=0$ or $m_{p}=m_{0}$. For $p=3$, there are two
trouble spots, which occur when either $\beta^{3}-\beta^{2}-1=0$ or when
$\beta^{3}-\beta^{2}-\beta-1=0$. These correspond to the values of
$\beta=1.465571231876768\cdots$ and $\beta=1.839286755214161\cdots$.

Where are the trouble spots located? Consider, for example,
$m_{4}=T_{\beta}^{4}\left(m_{0}\right)$, and consider the movement of $m_{4}$
as $\beta$ is swept through the range $1<\beta<2$. This is shown in figure 23.
As made clear in the image, three new trouble spots appear. These are located
at $\beta=1.380327757\cdots$ and $\beta=1.754877666\cdots$ and
$\beta=1.927561975\cdots$, which are the real roots of
$\beta^{4}-\beta^{3}-1=0$ and $\beta^{4}-\beta^{3}-\beta^{2}-1=0$ and
$\beta^{4}-\beta^{3}-\beta^{2}-\beta-1=0$ respectively.

Figure 23: Location of Midpoints

This rather busy image illustrates the location of the first five midpoints,
$m_{0},m_{1},\cdots,m_{4}$ as a function of $\beta$. The locations of the
discontinuities are termed “trouble spots”; the first trouble spot occurring
for $m_{2}$ at $\beta=\varphi$. The midpoint $m_{3}$ has two new trouble spots
at $\beta=1.465\cdots$ and $\beta=1.839\cdots$; the trouble spot at
$\beta=\varphi$ being disallowed, as it already lead to a termination of
midpoint iteration. The midpoint $m_{4}$ has three new trouble-spots.

Following a similar suggestion by Dajani[6], numbers of this kind may be
called “generalized golden means”. Unfortunately, the term “generalized golden
mean” is in common use, and is applied to a variety of different systems. Not
all are relevant; one that is, is given by Hare _et al._[33] who provide
series expansions for the real roots of
$\beta^{p}-\sum_{k=0}^{n-1}\beta^{k}=0$; these are known as the n-bonacci
constants (Fibonacci, tribonacci, tetranacci, _etc._). Stakhov[34] considers
$\beta^{p+1}-\beta^{p}-1=0$ in general settings. Some, but not all of these
numbers are known to be Pisot numbers or Salem numbers[13]. In what follows,
these will be referred to as the “beta golden means”, since all of the ones
that appear here have explicit origins with the beta shift.

###  5.2 Counting Orbits

How many trouble spots are there? The table below shows the count $M_{p}$ of
the number of “new” trouble spots, as a function of the midpoint index $p$.

$p$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---
$M_{p}$ | 1 | 2 | 3 | 6 | 9 | 18 | 30 | 56 | 99 | 186 | 335

This appears to be Sloane’s OEIS A001037 which has a number of known
relationships to roots of unity, Lyndon words, and the number of orbits in the
tent map. The trouble spots are the positive real roots of polynomials of the
form $\beta^{p}-\beta^{p-1}-b_{1}\beta^{p-2}-b_{2}\beta^{p-3}-\cdots-1=0$ with
the $b_{k}$ being certain binary bit sequences. There is just one such
(positive , real) root for each such polynomial. These polynomials are
irreducible, in the sense that a bit-sequence $b_{k}$ is disallowed if it has
the same root as some lower-order polynomial. For example,
$\beta^{4}-\beta^{3}-\beta-1$ is disallowed; it has the same root as
$\beta^{2}-\beta-1$. Although the digits $b_{k}$ must be zero or one, this
definition of irreducibility, plus the counting, suggests some relationship to
the irreducible polynomials over the field $\text{$\mathbb{F}$}_{2}$, as that
is what the definition of OEIS A001037 counts. Yet the relationship, if any,
is quite unclear.333A hypothesis presented in a later section suggests that
each orbit should be thought of as a Galois group, with the length of the
orbit corresponding to the number of elements in the Galois group. It seems
that this might explain much of the structure.

The values of $M_{n}$ are given explicitly by Moreau’s necklace-counting
function

$M_{n}=\frac{1}{n}\sum_{d|n}2^{d}\mu\left(\frac{n}{d}\right)$

where the sum runs over all integers $d$ that divide $n$ and $\mu$ is the
Möbius function. The generating function is

$\frac{t}{\frac{1}{2}-t}=\sum_{n=1}^{\infty}nM_{n}\frac{t^{n}}{1-t^{n}}$

which has a radius of convergence of $\left|t\right|<1/2$. For large $n$, the
asymptotic behavior can be trivially deduced from the defining sum:

$M_{n}=\frac{2^{n}}{n}-\mathcal{O}\left(\frac{2^{n/2}}{n}\right)$

The above counting function is for necklaces with only two colors. In general,
one can have necklaces with 3 or more colors; can that happen here? Yes, of
course: if one considers the general $\beta$-transform for $2<\beta$, then, in
general, it can be taken as a “kneading transform” with
$\left\lceil\beta\right\rceil$ branches or folds in it. The analogous trouble-
spots again appear, and they can appear after an arbitrary finite-length
orbit. Insofar as they correspond to periodic orbits, they are necessarily
counted by the necklace-counting function. That is, one must consider all
possible strings of $\left\lceil\beta\right\rceil$ letters, modulo a cyclic
permutation: this is the very definition of a necklace (or “circular word”).
The number of such necklaces is given by the necklace-counting function. Each
such orbit is necessarily represented by a Lyndon word, which is a
representative of the conjugacy class of the orbit.

###  5.3 $\beta$-Golden Polynomials

The “trouble spots” whenever the $k$’th iterate
$m_{k}=T_{\beta}^{k}\left(m_{0}\right)$ lands on the starting midpoint
$m_{k}=m_{0}$. Because of the piece-wise linear form of $T_{\beta}$, the
$k$’th iterate will be a piece-wise collection of polynomials, each of order
$k$, and of the form
$\beta^{k}-\beta^{k-1}-b_{1}\beta^{k-2}-b_{2}\beta^{k-3}-\cdots-1$ for some
binary digits $b_{i}$ being zero or one. These must be arranged in the manner
such that $\beta^{k}-\beta^{k-1}-b_{1}\beta^{k-2}-b_{2}\beta^{k-3}-\cdots-1=0$
at each discontinuity, as illustrated in figure 23. This limits the
polynomials that can appear; it limits the possible coefficients $b_{i}$; not
all bit-sequences appear.

Although the count of these polynomials is the same as that for the
irreducible polynomials over $\mathbb{F}_{2}$, the relationship is completely
opaque (to me). Apparently, this is a generic issue: the number of irreducible
polynomials over $\mathbb{F}_{p}$, for $p$ prime, is the same as the number of
necklaces, and yet, there is no known bijection between these irreducible
polynomials and the Lyndon words![35] Thus, a compilation seems to be called
for.

The table below explicitly shows the polynomials for the first few orders. A
polynomial is included in the table if it is an iterate of a previous
polynomial, and if it’s real root is bracketed by the roots of the earlier
iterates. That is, $p_{n}\left(\beta\right)$must have the form
$\beta\left(p_{n/2}\left(\beta\right)+1\right)-1$ when $n$ is even or $\beta
p_{\left(n-1\right)/2}\left(\beta\right)-1$ for $n$ odd. The roots must be
bracketed by the roots of polynomials occurring earlier in the sequence; if
the root is not bracketed, then the corresponding polynomial does not appear
in the list.

The bracketing relationship is rather awkwardly expressed in the following
pseudo-code. Here, $r_{n}$ is the root $p_{n}\left(r_{n}\right)=0$. The
polynomial $p_{n}$ is included in the list if it is the case that this pseudo-
code does not fail:

$m_{prev}$ := $n$

$m$ := $\left\lfloor n/2\right\rfloor$

while (0 < $m$)

$m_{prev}$ is even and $r_{m}$ < $r_{n}$ then fail

$m_{prev}$ := $m$

$m$ := $\left\lfloor m/2\right\rfloor$

The above is a rather awkward way of stating that roots must be bracketed by
pairs of previous roots. It can perhaps be more easily understood by studying
the location of the discontinuities in figure 23: new discontinuities at
higher orders must occur before earlier ones.

Thus, for example, the polynomial $\beta^{3}-\beta-1$ is excluded from the
list simply because it is not an iterate of an earlier polynomial, even though
it has the interesting real root $1.324717957244746\cdots$, the “silver
constant”. The numbering scheme does not even have a way of numbering this
particular polynomial. Despite this, the silver constant does appear, but a
bit later, as the root of $p_{8}=\beta^{5}-\beta^{4}-1$, which is an allowed
polynomial.

The polynomial $p_{5}=\beta^{4}-\beta^{3}-\beta-1$ is excluded because it has
$\varphi=1.618\cdots$ as a root, which was previously observed by $p_{1}$. The
polynomial $p_{9}=\beta^{5}-\beta^{4}-\beta-1$ is excluded because it’s root,
$r_{9}=1.497094048762796\cdots$ is greater than its predecessor $r_{2}$; the
recursive algorithm does not compare to $r_{4}$.

There are other ways to start the table, and to index the polynomials. The
given indexing has the property that $2n+1$, taken as binary, encodes the
coefficients of the polynomial. The order of the polynomial is
$\left\lceil\log_{2}\left(2n+1\right)\right\rceil$. The index $n$ itself
encodes the orbit of the midpoint. That is, writing $n=b_{0}b_{1}b_{2}\cdots
b_{p}$ for binary digits $b_{k}$, then $T_{\beta}^{k}\left(\beta/2\right)<1/2$
if and only if $b_{k}=0$. Note that $b_{0}=1$ always corresponds to
$1/2<\beta/2$ always. By convention, the last digit is always 1, also.

order | $p_{n}\left(\beta\right)$ | $n$ | binary | root
---|---|---|---|---
0 | $1$ |  |  |
1 | $\beta$ |  | 0 | 0
$\beta-1$ | 0 | 1 | 1
2 | $\beta^{2}-\beta-1$ | 1 | 11 | $\varphi=\frac{1+\sqrt{5}}{2}=1.618\cdots$
3 | $\beta^{3}-\beta^{2}-1$ | 2 | 101 | $1.465571231876768\cdots$
$\beta^{3}-\beta^{2}-\beta-1$ | 3 | 111 | $1.839286755214161\cdots$
4 | $\beta^{4}-\beta^{3}-1$ | 4 | 1001 | $1.380277569097613\cdots$
$\beta^{4}-\beta^{3}-\beta^{2}-1$ | 6 | 1101 | $1.7548776662466924\cdots$
$\beta^{4}-\beta^{3}-\beta^{2}-\beta-1$ | 7 | 1111 | $1.9275619754829252\cdots$
5 | $\beta^{5}-\beta^{4}-1$ | 8 | 10001 | $1.324717957244746\cdots$
$\beta^{5}-\beta^{4}-\beta^{2}-1$ | 10 | 10101 | $1.5701473121960547\cdots$
$\beta^{5}-\beta^{4}-\beta^{3}-1$ | 12 | 11001 | $1.704902776041646\cdots$
$\beta^{5}-\beta^{4}-\beta^{3}-\beta-1$ | 13 | 11011 | $1.812403619268042\cdots$
$\beta^{5}-\beta^{4}-\beta^{3}-\beta^{2}-1$ | 14 | 11101 | $1.888518845484414\cdots$
$\beta^{5}-\beta^{4}-\beta^{3}-\beta^{2}-\beta-1$ | 15 | 11111 | $1.965948236645485\cdots$

The next table lists the acceptable polynomials for order 5, 6 and 7\. Again,
the coefficients appearing in the polynomial are encoded by the binary value
of $2n+1$ in the sequence.

order | sequence
---|---
5 | 8,10,12,13,14,15
6 | 16,20,24,25,26,28,29,30,31
7 | 32,36,40,42,48,49,50,52,53,54,56,57,58,59,60,61,62,63

Although there are as many of these polynomials as there are Lyndon words,
there is no obvious way to write a bijection between the two. It is almost
possible to do so by writing $2n$ in binary, and then reversing the order of
the bits, left-to-right. One almost gets the Lyndon words in the correct
order, except “in the middle”: so, for example, in the table above, one can
get the Lyndon order by exchanging 10 with 12, and 13 with 14. But the table
above cannot be re-ordered: the given ordering encodes the orbit of the
midpoint. Apparently, although a given orbit can be cyclically rotated to
obtain a Lyndon word, the initial segment of the orbit is not a Lyndon word
itself.

Questions that present themselves include:

  * •

Is there a generating function for the squence of allowed values of $n$? What
is it?

  * •

How long is the initial segment of each periodic orbit, before the orbit
attains it’s Lyndon word form? What are the values of $\beta$ where the
initial orbits are not in Lyndon form?

###  5.4 Distribution of $\beta$-Golden Roots

It seems natural to assume that the real roots have some distribution. This
seems not to be the case. Figure 24 shows the numerically computed (bin-
counted) distribution of the zeros of $p_{n}\left(\beta\right)$ for $n<2^{k}$
for three different values of $k$. This suggests that, in the limit of
$k\to\infty$, almost all $p_{n}\left(\beta\right)$ have roots that approach 2.
Although the roots appear to be dense in $1<\beta<2$, essentially all of the
weight of that density is at $2$. Since the roots are countable, the density