Kneading theory

From Scholarpedia

This article is undergoing 1 initial review (1 completed); It may contain inaccuracies and unapproved changes made by anonymous reviewers.

Revision as of 08:19, 11 May 2009; view current revision
←Older revision | Newer revision→

Peer review status

You are not logged in.

Reviewer A: Modified and approved on 11 May 2009.

Reviewer B: Awaits author's response (last modifications by reviewer - 66 days ago)

This article is not accepted to Scholarpedia yet. It may contain inaccuracies and unapproved changes made by anonymous reviewers.

Dr. Toby Hall prefers wiki-style peer-review process: reviewers are encouraged to modify the article directly.

Author: Dr. Toby Hall, Department of Mathematical Sciences, University of Liverpool

Kneading theory is a tool, developed by Milnor and Thurston, for studying the topological dynamics of piecewise monotone self-maps of an interval.

Associated to such an interval map $f$ is its kneading matrix $N(t)$ , whose entries are elements of ${\mathbb Z}[[t]]$ , the ring of formal power series with integer coefficients. This matrix contains information about important combinatorial and topological invariants of $f$ .

Milnor and Thurston's work was eventually published in Milnor and Thurston 1988, although the majority of their article had been widely circulated in preprint form since 1977. The use of symbolic dynamics in the study of interval maps, which is the starting point of their work, was developed earlier (see for example Parry 1966, Metropolis Stein and Stein 1973).

Quite often notation different from Milnor and Thurston's is used, see Alternative notation.

1 The unimodal case
2 The multimodal case
3 Other directions
4 Alternative notation
5 References
6 Recommended reading

[edit]

The unimodal case

Figure 1: A unimodal map

The theory is most easily understood in the special case of unimodal maps, which is also the most common area of application. In this section $f:[0,1]\to[0,1]$ is a fixed continuous map (so the dependence of objects on $f$ will not be explicitly noted), with the properties that

there is some $c\in(0,1)$ such that $f$ is strictly increasing on $[0,c]$ and strictly decreasing on $[c,1]$ , and
$f(0)=f(1)=0$ .

A rich source of examples is provided by the logistic family $f_\mu(x)=\mu x(1-x)$ , where $0<\mu\le 4$ .

[edit]

The cutting invariant and the lap invariant: topological entropy

Let $\Gamma$ be the set of preimages of $c$ , i.e.

$\Gamma = \{x\in[0,1]\,:\,f^i(x)=c \mbox{ for some }i\ge 0\}.$

$\Gamma$ can be written as the disjoint union of the sets $\Gamma_i$ ( $i\ge 0$ ), where elements $x$ of $\Gamma_i$ satisfy $f^i(x)=c$ but $f^j(x)\not=c$ for $j<i$ . Let $\gamma_i$ denote the cardinality of $\Gamma_i$ (so $\gamma_i\le 2^i$ for all $i$ ). The cutting invariant of $f$ is the formal power series

$\gamma(t) = \sum_{i=0}^\infty \gamma_i t^i \, \in{\mathbb Z}[[t]].$

Constructing formal power series from sequences of integers in this way will be a common process: where appropriate, these formal power series will be regarded as complex power series without further comment. A closely related construction is of the lap invariant $\ell(t)$ : let $\ell_i$ denote the number of monotone pieces (or laps) of $f^i$ for $i\ge 1$ , and write

$\ell(t) = \sum_{i=0}^\infty \ell_{i+1} t^i\, \in{\mathbb Z}[[t]].$

Since $\ell_i=1+\sum_{j=0}^{i-1}\gamma_j$ it follows that

(1)

$\ell(t)=\frac{1}{1-t}\left(1+\gamma(t)\right).$

Let $s=\limsup_{i\to\infty}\ell_i^{1/i}\in[1,2]$ , the reciprocal of the radius of convergence of $\ell(t)$ , and hence also of $\gamma(t)$ . Misiurewicz and Szlenk 1977 show that the topological entropy $h(f)$ of $f$ is given by $h(f)=\log s$ . This quantity $s$ is called the growth number of $f$ . It can readily be shown that the sequence $(\ell_i^{1/i})$ converges, so that in fact $s=\lim_{i\to\infty}\ell_i^{1/i}$ .

[edit]

The kneading determinant

Let $x\in[0,1]\setminus\Gamma$ (that is, $x$ is not a preimage of $c$ ). Define the kneading coordinate of $x$ to be the sequence $\theta(x)\in\{+1,-1\}^{\mathbb N}$ by

$\theta_0(x)= \begin{cases} +1, & \mbox{if }x<c\\ -1, & \mbox{if }x>c \end{cases} \qquad \mbox{and} \qquad \theta_i(x)=\theta_{i-1}(x)\theta_0(f^i(x)) \mbox{ for }i\ge1.$

(More succinctly, $\theta_i(x)=+1$ or $-1$ according as $f^{i+1}$ is locally increasing or locally decreasing at $x$ .)

Construct a corresponding power series $\theta(x,t)=\sum_{i=0}^\infty \theta_i(x) t^i\in{\mathbb Z}[[t]]$ .

Example

Any unimodal map $f$ as defined above has

(2)

$\theta(0,t)=\frac{1}{1-t}\quad\mbox{ and }\quad\theta(1,t)=\frac{-1}{1-t}$ .

For $x=0$ , $\theta_0(f^i(x))=\theta_0(0)=+1$ for all $i\ge 0$ , so that $\theta_i(0)=+1$ for all $i\ge 0$ ;
for $x=1$ , $\theta_0(x)=-1$ and $\theta_0(f^i(x))=\theta_0(0)=+1$ for all $i>0$ , so that $\theta_i(x)=-1$ for all $i\ge 0$ .

Now for any $x\in[0,1]$ , define elements $\theta(x^+)$ and $\theta(x^-)$ of $\{+1,-1\}^{\mathbb N}$ by

$\theta(x^+)=\lim_{y\searrow x}\theta(y)\qquad\mbox{and}\qquad\theta(x^-)=\lim_{y\nearrow x}\theta(y),$

where the limits are taken through elements $y$ of $[0,1]\setminus\Gamma$ . (These limits can be taken with respect to the product topology on $\{+1,-1\}^{\mathbb N}$ , but the situation is very simple. For each $i$ , let $z>x$ be the smallest element of $(x,1] \cap \bigcup_{j\le i}\Gamma_j$ (or $z=1$ if this set is empty): then $\theta_i(y)$ is constant for $y\in(x,z)$ , and $\theta_i(x^+)$ is this constant value.)

Construct corresponding power series $\theta(x^+,t)$ and $\theta(x^-,t)$ by $\theta(x^\pm,t)=\sum_{i=0}^\infty \theta_i(x^\pm)t^i\in{\mathbb Z}[[t]]$ .

The kneading determinant $D(t)$ of $f$ (also called the kneading invariant in the unimodal context) is then defined by

$D(t)=\theta(c^-,t)\in{\mathbb Z}[[t]].$

It expresses the discontinuity of the kneading coordinate across $x=c$ .

Example Let $f(x)=3.84\,x(1-x)$ (which has a stable period 3 orbit). The orbit of $c=1/2$ satisfies $f^{3i+1}(c)>c$ , $f^{3i+2}(c)<c$ and $f^{3i+3}(c)<c$ for all $i\ge 0$ . Hence (abbreviating $+1$ and $-1$ to $+$ and $-$ )

$\begin{array}{rcl} \left(\theta_0(f^i(c^-))\right)_{i\ge 0} &=& (+, -, +, +, -, +, +, -, +, +, -, +, +, \ldots),\quad\mbox{and so}\\ \theta(c^-) &=& (+, -, -, -, +, +, +, -, -, -, +, +, +, \ldots), \quad\mbox{and}\\ D(t) &=& 1-t-t^2-t^3+t^4+t^5+t^6-t^7-t^8-t^9 + \cdots \,\, = (1-t-t^2)/(1+t^3). \end{array}$

[edit]

Homtervals

Order $\{+1,-1\}^{\mathbb N}$ lexicographically with $+1 \prec -1$ : that is, if $\theta\not=\phi\in\{+1,-1\}^{\mathbb N}$ , then $\theta \prec \phi$ if and only if $\theta_n = +1$ , where $n$ is least such that $\theta_n\not= \phi_n$ . Then it can easily be shown that

$x<y \,\,\implies\,\, \theta(x^-) \preceq \theta(y^-).$

That is, the function $x\mapsto \theta(x^-)$ (and similarly the function $x\mapsto\theta(x^+)$ ) is increasing.

A non-trivial interval $[a,b]$ on whose interior these functions are constant (that is, whose interior is disjoint from $\Gamma$ ) is called a homterval. $f$ can only have a homterval $[a,b]$ if either every point of $[a,b]$ is in the basin of a periodic orbit, or if $[a,b]$ is a wandering interval: the latter possibility cannot occur if $f$ is $C^2$ and has non-flat turning point (de Melo and van Strien 1993, see also Guckenheimer 1979, Misiurewicz 1981).

[edit]

The relationship between the kneading determinant and the cutting invariant

The fundamental relationship between the kneading determinant $D(t)$ and the cutting invariant $\gamma(t)$ is

(3)

$D(t)\gamma(t)=\frac{1}{1-t}.$

To see why this holds, observe first that $D(t)=\theta(c^-,t)=-\theta(c^+,t)$ (since " $f(c^+)=f(c^-)$ "). That is, the discontinuity in $\theta(x,t)$ across $x=c$ is $-2D(t)$ . It follows that the discontinuity across an element $x$ of $\Gamma_i$ is $\theta(x^+,t)-\theta(x^-,t)=-2t^i D(t)$ .

Fix $n\ge 0$ . Then $\theta_n(x^-)$ is constant on the open intervals whose endpoints are the points of $\bigcup_{i=0}^n\Gamma_i$ . Hence

$\theta_n(1)-\theta_n(0)=\sum_{i=0}^n\sum_{x\in\Gamma_i}\left(\theta_n(x^+)-\theta_n(x^-)\right).$

Now the left hand side of this equation is $-2$ (cf. (2)), while $\theta_n(x^+)-\theta_n(x^-)=-2\theta_{n-i}(c^-)$ for $x\in\Gamma_i$ . Therefore

$1=\sum_{i=0}^n\sum_{x\in\Gamma_i}\theta_{n-i}(c^-) = \sum_{i=0}^n\gamma_i\theta_{n-i}(c^-).$

However $\sum_{i=0}^n\gamma_i\theta_{n-i}(c^-)$ is the coefficient of $t^n$ in $D(t)\gamma(t)$ , which establishes the result.

Example Let $f(x)=3.84\,x(1-x)$ , so that $D(t)=(1-t-t^2)/(1+t^3)$ as above. It follows by (3) that $\gamma(t)=(1+t^3)/(1-2t+t^3)$ , and (1) then gives

$\ell(t) = \frac{2}{1-t}\left(\frac{1-t+t^3}{1-2t+t^3}\right) = 2+4t+8t^2+16t^3+30t^4+54t^5+94t^6+\cdots.$

Hence, for example, $f^6$ has 54 laps.

[edit]

Topological entropy

Theorem $\quad$ Let $f$ be a unimodal map. Then its topological entropy $h(f)$ is positive if and only if $D(t)$ has a zero in $|t|<1$ . In this case, $h(f)=\log\frac{1}{r}$ , where $r$ is the smallest zero of $D(t)$ in $[0,1)$ , and $D(t)$ has no zeros in $|t|<r$ .

This result follows immediately from (3). By Misiurewicz and Szlenk 1977, $h(f)=\log \frac{1}{r}$ , where $\gamma(t)$ has radius of convergence $r$ . Clearly $D(t)$ has radius of convergence 1. Hence $D(t)$ and $\gamma(t)$ are analytic in $|t|<r$ , so $D(t)$ can have no zeros in $|t|<r$ . If $\frac{1}{r}>1$ , then $\gamma(t)$ has a pole at $t=r$ , since all of its coefficients are positive. Letting $t\to r$ from below in $D(t)\gamma(t)=1/(1-t)$ (which is valid as an identity for complex power series in $|t|<r$ ) gives $D(r)=0$ .

Example

Figure 2: Growth number of logistic maps

Let $f(x)=3.84\,x(1-x)$ , so that $D(t)=(1-t-t^2)/(1+t^3)$ as above. Hence $D(t)$ has a unique zero in $[0,1)$ , which is $r=(\sqrt{5}-1)/2$ , and it follows that $h(f)=\log(1/r)=\log((\sqrt{5}+1)/2)$ .

In cases such as the above where the coefficients of $D(t)$ form an eventually periodic sequence, the topological entropy can be calculated by standard Markov partition techniques, but the theorem has wider applicability. It can also be used as a practical means of estimating the topological entropy of unimodal maps: for example, Fig.2 shows a graph of growth number against parameter $\mu$ in the logistic family, calculated using this method.

[edit]

The Artin-Mazur zeta function

Suppose that $f$ has only finitely many periodic orbits of each period. The Artin-Mazur zeta function of $f$ (Artin and Mazur 1965) is the formal power series

$\zeta(t)=\exp\,\sum_{k\ge 1}n(f^k)\frac{t^k}{k},$

where $n(f^k)$ denotes the number of fixed points of $f^k$ . One of the most substantial results of Milnor and Thurston 1988 is a relationship between this zeta function and the kneading determinant.

For the sake of simplicity, assume that $f$ is differentiable, and that all but finitely many of its periodic orbits are unstable: these conditions hold, for example, if $f$ is a rational function, or if it has negative Schwarzian derivative (see sections 8-11 of Milnor and Thurston 1988 for ways in which this assumption can be relaxed).

Then

$\zeta(t)^{-1} = D(t) \prod_{P}\kappa_P(t),$

where the product is over the periodic orbits $P$ of $f$ which are not unstable together with the fixed point $0$ , and the polynomials $\kappa_P(t)$ are as follows:

For the fixed point $0$ , $\kappa_P(t)=(1-t)^2$ if the fixed point is stable (on the right), and $\kappa_P(t)=1-t$ otherwise.
For each other non-unstable periodic orbit of period , is
- $1-t^k$ if $P$ is stable on one side only;
- $1-t^{2k}$ if $P$ is stable and the derivative of $f^k$ is negative at the points of $P$ ;
- $(1-t^k)^2$ if $P$ is stable and the derivative of $f^k$ is non-negative at the points of $P$ .

In particular, $\zeta(t)$ has radius of convergence $r=1/s$ , where $s$ is the growth number of $f$ .

Example Let $f(x)=3.84\,x(1-x)$ , so that $D(t)=(1-t-t^2)/(1+t^3)$ as above. $f$ has a stable period 3 orbit, at the points of which $f^3$ has negative derivative (and there are no other stable periodic orbits since $f$ has negative Schwarzian derivative). The fixed point at $x=0$ is unstable. Hence

$\zeta(t)^{-1}=\frac{1-t-t^2}{1+t^3}(1-t)(1-t^6)=1-2t+2t^4-t^6.$

The expression

$t\zeta'(t)/\zeta(t)=\sum_{k\ge 1}n(f^k)t^k = \frac{2t(1+t+t^2-3t^3-3t^4)}{1-t-t^2-t^3+t^4+t^5}=2t+4{t}^{2}+8{t}^{3}+8{t}^{4}+12{t}^{5}+22{t}^{6}+30{t}^{7}+\cdots$

then makes it possible to calculate $n(f^k)$ for each $k$ .

[edit]

Semi-conjugacy to piecewise-linear models

Assume throughout this section that $f$ has positive topological entropy, i.e. that it has growth number $s>1$ .

Figure 3: A tent map

By means of kneading theory, it is possible to construct explicitly a continuous increasing surjection $\lambda:[0,1]\to[0,1]$ which semi-conjugates $f$ to the tent map $F_s:[0,1]\to[0,1]$ defined (see Fig.3) by

$F_s(x)= \begin{cases} sx, & \mbox{if }x\le 1/2\\ s(1-x), & \mbox{if }x\ge 1/2. \end{cases}$

The semi-conjugacy $\lambda$ is given by

(4)

$\lambda(x)=\frac{1}{2}\left(1-(1-r)\,\theta(x^-, r)\right),$

where $r=1/s$ (note that the function $x\mapsto \theta(x^-,r)$ is continuous, since $D(r)=0$ ).

Given a subinterval $J=[a,b]$ of $[0,1]$ , define $\ell_i^J$ to be the number of laps of $f^i|_J$ for each $i\ge 1$ , and let $\ell^J(t)$ be the corresponding formal power series

$\ell^J(t)=\sum_{i=0}^\infty \ell_{i+1}^J t^i\in{\mathbb Z}[[t]].$

Recall that $\ell(t)=\ell^{[0,1]}(t)$ has radius of convergence $r$ . Notice that $0< \ell^J(t)\le \ell(t)$ for all $t\in[0,r)$ so that the singularity of $\ell^J(t)/\ell(t)$ at $t=r$ is removable. The limit $L(J)=\lim_{t\nearrow r}\frac{\ell^J(t)}{\ell(t)}$ therefore exists and lies in $[0,1]$ .

Observe the following:

If $x\in(a,b)$ , then $L(J)=L([a,x])+L([x,b])$ .

(For $\ell^J(t)-\left(\ell^{[a,x]}(t)+\ell^{[x,b]}(t)\right)$ is bounded in $[0,r)$ , while $\ell(t)$ has a pole at $t=r$ .)

Let $i\ge 1$ . If $(a,b)$ is disjoint from $\Gamma_j$ for $0\le j<i$ , then $L(J)=r^iL(f^i(J))$ .

(For then $f^i|_J$ is a homeomorphism, so $\ell_j^J=1$ for $1\le j\le i$ , while $\ell_j^J=\ell_{j-i}^{f^i(J)}$ for $j>i$ . Hence $\ell^J(t)=1+t+\cdots+t^{i-1}+t^i\ell^{f^i(J)}(t)$ , and the result follows on dividing by $\ell(t)$ and taking the limit as $t\nearrow r$ .)

$L(J)$ depends continuously on the endpoints of $J$ .

(By the first property above, it suffices to show that, given $\epsilon>0$ , $L(J)<\epsilon$ for all sufficiently small $J$ . Let $i$ be large enough that $r^i<\epsilon$ : then any $J$ whose interior is disjoint from the finite set $\bigcup_{j=0}^{i-1}\Gamma_j$ satisfies $L(J)=r^iL(f^i(J))\le r^i<\epsilon$ .)

Now define $\lambda:[0,1]\to[0,1]$ by $\lambda(x)=L([0,x])$ . Clearly $\lambda(0)=0$ and $\lambda(1)=1$ ; and, by the properties above, $\lambda$ is continuous and increasing.

Theorem $\quad$ $F_s\circ\lambda = \lambda\circ f$ , and $\lambda(c)=1/2$ .

For the proof, observe that:

If $x\in[0,c]$ then $(0,x)$ is disjoint from $\Gamma_0=\{c\}$ , and hence $\lambda(x)=L([0,x])=rL(f([0,x]))=r\lambda(f(x))$ , so

$\lambda\circ f(x)=s\lambda(x).$

If $x\in[c,1]$ then similarly $\lambda(x)=L([0,c])+L([c,x]) = \lambda(c)+rL([f(x),f(c)])=\lambda(c)+r(\lambda(f(c))-\lambda(f(x)))$ . Hence

$\lambda\circ f(x)=s(\lambda(c)-\lambda(x))+\lambda(f(c)).$

Thus $\lambda\circ f$ is continuous, and is of the form $F\circ\lambda$ , where $F:[0,1]\to [0,1]$ has slope $s$ for $x\in[0,\lambda(c)]$ , and slope $-s$ for $x\in[\lambda(c),1]$ . Since $F(0)=F(1)=0$ , it follows that $F=F_s$ and $\lambda(c)=1/2$ .

To obtain the expression (4) for $\lambda(x)$ (which is more accessible for calculations), define $\gamma_i^J$ to be the cardinality of $\Gamma_i\cap(a,b)$ , and let $\gamma^J(t)=\sum_{i=0}^\infty \gamma_i^Jt^i\in{\mathbb Z}[[t]]$ be the corresponding formal power series. As in (1), it is straightforward that

Figure 4: The function which semiconjugates $x\mapsto3.84x(1-x)$ to a tent map

$\ell^J(t) = \frac{1}{1-t}\left(1+\gamma^J(t)\right),$

so that $\lambda(x)$ can equivalently be defined as $\lambda(x)=\lim_{t\nearrow r}\frac{\gamma^{[0,x]}(t)}{\gamma(t)}$ .

Analogously to (3), it can be shown that $\theta(b^-,t)-\theta(a^+,t)=-2D(t)\gamma^J(t)$ . Hence

$\frac{\gamma^{[0,x]}(t)}{\gamma(t)} = \frac{\theta(x^-,t)-\theta(0,t)}{\theta(1,t)-\theta(0,t)},$

from which (4) follows, since $\theta(0,t)=1/(1-t)$ and $\theta(1,t)=-1/(1-t)$ by (2).

Example Let $f(x)=3.84x(1-x)$ . The graph of the function $\lambda$ which semi-conjugates $f$ to the tent map $F_{(\sqrt{5}+1)/2}$ is shown in Fig.4. Notice that $\lambda$ is locally constant on the basin of attraction of the stable period 3 orbit of $f$ .

See also Parry 1966 for an alternative approach to the proof of this result in the case of transitive maps and Alseda, Llibre and Misiurewicz 2000 in the general case.

[edit]

Renormalization

Figure 5: Renormalizing a unimodal map

A unimodal map $f$ is renormalizable if there is a proper subinterval $J$ of $[0,1]$ and an integer $n>1$ such that $f^n|_J$ is itself (topologically conjugate to) a unimodal map (see Fig.5). Consideration of the longest possible sequence of renormalizations of $f$ gives rise to a canonical decomposition $\Omega(f)=\bigcup_{i=0}^p\Omega_i$ of the non-wandering set of $f$ into $f$ -invariant basic sets (see Jonker and Rand 1981). The topological entropies $h(f|_{\Omega_i})$ are reflected by zeros of $D(t)$ : the following brief description summarizes results from Jonker and Rand 1981.

A map $f$ is renormalizable if and only if there is an element $w$ of $\{-1,+1\}^n$ for some $n>1$ and non-negative integers $b_0, a_1, b_1, a_2, \ldots$ (this may also be a finite sequence whose last entry is $\infty$ ) such that

$\theta(c^-)=w(-w)^{b_0}w^{a_1}(-w)^{b_1}w^{a_2}\ldots,$

where $-w\in\{-1,+1\}^n$ is the word obtained from $w$ by interchanging $+1$ and $-1$ . In this case, writing $R_w\theta(c^-)$ for the sequence $(+1)(-1)^{b_0}(+1)^{a_1}(-1)^{b_1}(+1)^{a_2}\ldots$ , $R_wD(t)$ for the corresponding formal power series (which is the kneading determinant of the renormalized map $f^n|_J$ ), and $w(t)$ for the polynomial $\sum_{i=0}^{n-1}w_it^i$ , it can easily be seen that

$D(t)=w(t)R_wD(t^n),$

from which the following result can be derived:

Theorem $\quad$ Let $\Omega_i$ be a basic set in the canonical decomposition of the non-wandering set of a unimodal map $f$ , with $h(f|_{\Omega_i})=s_i>0$ . Then $D(t)$ has a zero at $t=e^{-s_i}$ .

Note, however, that $D(t)$ may have zeros in $(0,1)$ which do not correspond to the topological entropy on any basic set.

Example Let $f(x)=3.85209\,x(1-x)$ (so that $f$ has a stable period 15 orbit). Then

$\theta(c^-)=(+---++-+++---++)^\infty = (w(-w)^2w(-w))^\infty,$

where $w=+--$ . Hence $w(t)=1-t-t^2$ , $R_wD(t)=(1-t-t^2+t^3-t^4)/(1-t^5)$ , and

$D(t)=\frac{1-t-t^2-t^3+t^4+t^5-t^6+t^7+t^8+t^9-t^{10}-t^{11}-t^{12}+t^{13}+t^{14}}{1-t^{15}}$

$\qquad\,\,=(1-t-t^2)\left(\frac{1-t^3-t^6+t^9-t^{12}}{1-t^{15}}\right) = w(t)R_wD(t^3).$

$D(t)$ has two zeros in $(0,1)$ : at $(\sqrt{5}-1)/2$ , a zero of $w(t)$ , corresponding to $h(f)=h(f|_{\Omega_0})$ ; and at about $0.871$ , the cube root of a zero of $R_wD(t)$ , corresponding to $h(f|_{\Omega_1})$ .

[edit]

The multimodal case

[edit]

Introduction

A continuous self-map $f:I\to I$ of an interval $I=[a,b]$ is piecewise monotone if there are elements $c_1<c_2<\cdots<c_{\ell-1}$ of $(a,b)$ such that $f$ is strictly monotone on each interval $I_1=[a,c_1]$ , $I_{n+1}=[c_n, c_{n+1}]$ ( $1\le n\le \ell-2$ ), and $I_\ell=[c_{\ell-1},b]$ .

It will always be assumed that $\ell$ has been chosen to be as small as possible, so that each $c_n$ is a local extremum, or turning point, of $f$ .

The kneading theory for piecewise monotone maps is developed analogously to the unimodal case. The kneading coordinate of a point $x\in I$ must identify which of the $\ell$ laps of $f$ each iterate of $x$ belongs to, and there are $\ell-1$ turning points across which the discontinuity of the kneading coordinate needs to be specified: this information gives rise to an $(\ell-1)\times\ell$ matrix with entries in ${\mathbb Z}[[t]]$ , which is called the kneading matrix $N(t)$ of $f$ . The kneading determinant $D(t)$ of $f$ is the (suitably normalised) determinant of an $(\ell-1)\times(\ell-1)$ submatrix of $N(t)$ .

Additional minor complications compared to the unimodal case (with the definition of unimodal used above), are caused by the facts that the first lap of $f$ may be either increasing or decreasing, and that it is not assumed that the endpoints $\{a,b\}$ of $I$ form an $f$ -invariant set.

[edit]

The cutting invariant, lap invariant, and growth number

The lap invariant $\ell(t)$ of $f$ is defined exactly as in the unimodal case:

$\ell(t)=\sum_{i=0}^\infty \ell_{i+1}t^i\in{\mathbb Z}[[t]],$

where $\ell_i$ is the number of laps of $f^i$ .

Similarly, the cutting invariant $\gamma(t)$ of $f$ is defined by

$\gamma(t)=\sum_{i=0}^\infty \gamma_it^i\in{\mathbb Z}[[t]],$

where $\gamma_i$ is the cardinality of the set $\Gamma$ of points $x\in(a,b)$ with the property that $f^i(x)$ is a turning point, but $f^j(x)$ is not a turning point for $j<i$ . The lap invariant and the cutting invariant are related by

$\ell(t)=\frac{1}{1-t}\left(1+\gamma(t)\right),$

and hence they have the same radius of convergence $1/s$ , where $s=\limsup_{i\to\infty}\ell_i^{1/i}=\lim_{i\to\infty}\ell_i^{1/i}\in[1,\ell]$ , the growth number of $f$ . Misiurewicz and Szlenk 1977 show that the topological entropy $h(f)$ of $f$ is given by $h(f)=\log s$ .

Slightly more information is provided by the formal power series

$\gamma^n(t) = \sum_{i=0}^\infty \gamma_i^n t^i\in{\mathbb Z}[[t]] \quad (1\le n\le\ell-1),$

where $\gamma_i^n$ is the cardinality of the set $\Gamma_i^n$ of points $x\in(a,b)$ with the property that $f^i(x)=c_n$ , but $f^j(x)$ is not a turning point for $j<i$ . Notice that $\gamma(t)=\sum_{n=1}^{\ell-1}\gamma^n(t)$ .

[edit]

The kneading matrix and kneading determinant

For each $n$ with $1\le n\le \ell$ , let $\epsilon_n=+1$ if $f|_{I_n}$ is increasing, and $\epsilon_n=-1$ if $f|_{I_n}$ is decreasing. In particular, $\epsilon_{n+1}=-\epsilon_n$ for $1\le n < \ell$ .

Let $M$ be the free module with basis $\{I_1,\ldots,I_\ell\}$ over ${\mathbb Z}$ . Given $x\in[a,b]\setminus\Gamma$ , let $k(x)=\left(k_i(x)\right)_{i\ge0}\in\{1,\ldots,\ell\}^{\mathbb N}$ be defined by the condition $f^i(x)\in I_{k_i(x)}$ for each $i\ge 0$ .

The kneading coordinate $\theta(x)=\left(\theta_i(x)\right)_{i\ge 0}\in M^{\mathbb N}$ of $x$ is then defined by

$\theta_i(x)=I_{k_i(x)}\prod_{j=0}^{i-1}\epsilon_{k_j(x)}\qquad (x\in[a,b]\setminus\Gamma) .$

More succinctly, $\theta_i(x)=\pm I_n$ , where $f^i(x)\in I_n$ , the sign being $+$ or $-$ according as $f^i$ is locally increasing or locally decreasing at $x$ . (Note the distinction with the unimodal case, where the sign of $\theta_i(x)$ reflected the local behaviour of $f^{i+1}$ .)

Construct a corresponding formal power series $\theta(x,t)=\sum_{i=0}^\infty \theta_i(x)t^i \in M[[t]]$ , where $M[[t]]$ is regarded as the free module with basis $\{I_1,\ldots,I_\ell\}$ over ${\mathbb Z}[[t]]$ .

For arbitrary $x\in[a,b]$ , define elements $\theta(x^+)$ and $\theta(x^-)$ of $M^{\mathbb N}$ by

$\theta(x^+)=\lim_{y\searrow x}\theta(y)\qquad\mbox{and}\qquad\theta(x^-)=\lim_{y\nearrow x}\theta(y),$

where the limits are taken through elements $y$ of $[a,b]\setminus\Gamma$ . Construct corresponding formal power series

$\theta(x^\pm,t) = \sum_{i=0}^\infty \theta_i(x^\pm)t^i \in M[[t]].$

The kneading increments $\nu_m(t)$ of $f$ (for $1\le m\le \ell-1$ ) express the discontinuity of the kneading coordinate across the turning point $c_m$ , and are defined by

$\nu_m(t)=\theta(c_m^+,t)-\theta(c_m^-,t)\in M[[t]].$

The kneading matrix $N(t)$ of $f$ is the $(\ell-1)\times\ell$ matrix over ${\mathbb Z}[[t]]$ whose $(m,n)$ entry is the coefficient of $I_n$ in $\nu_m(t)$ : that is, $\nu_m(t)=\sum_{n=1}^\ell N_{mn}(t)I_n$ .

Notice that

$\nu_m(t) = I_{m+1}-I_m + 2\sum_{i=1}^\infty t^i\theta_i(c_m^+) = I_{m+1}-I_m +2\sum_{i=1}^\infty t^i I_{k_i(c_m^+)}\prod_{j=0}^{i-1}\epsilon_{k_j(c_m^+)}$

(since " $f(c_m^+)=f(c_m^-)$ "). It follows that

$\sum_{n=1}^\ell N_{mn}(t)(1-\epsilon_n t) = (1-\epsilon_{m+1}t)-(1-\epsilon_m t)+2\sum_{n=1}^\ell \sum_{i\ge 1:\,k_i(c_m^+)=n} t^i(1-\epsilon_n t)\prod_{j=0}^{i-1}\epsilon_{k_j(c_m^+)}$

$\qquad\qquad\qquad\qquad\quad = 2\left(-\epsilon_{m+1}t+\sum_{i=1}^\infty t^i\left[\prod_{j=0}^{i-1}\epsilon_{k_j(c_m^+)} - t\prod_{j=0}^{i}\epsilon_{k_j(c_m^+)}\right]\right)$

$\qquad\qquad\qquad\qquad\quad = 0$

for $1\le m \le \ell-1$ . This linear relationship between the columns of $N(t)$ implies that $(-1)^{n+1}D_n(t)/(1-\epsilon_n t)$ is independent of $n$ , where $D_n(t)$ is the determinant of the submatrix of $N(t)$ obtained by deleting the $n$ th column ( $1\le n\le \ell$ ).

The kneading determinant $D(t)$ of $f$ is defined to be this common value, that is

$D(t) = D_1(t)/(1-\epsilon_1 t),$

where $D_1(t)$ is the determinant of the submatrix of $N(t)$ obtained by deleting its first column.

This definition agrees with that given in Section 1 in the case where $f$ is a unimodal map.

[edit]

Theorems

All of the results of the unimodal case described in Section 1, with the exception of the statement about renormalization, have direct analogues in the general case. The proofs are similar in spirit, but generally rather more complicated. Full details can be found in Milnor and Thurston 1988.

The analogue of (3) is that the coefficients of $I_n$ in $\theta(b^-,t)-\theta(a^+,t)$ are given by the entries of the vector $(\gamma^1(t)\,\,\gamma^2(t)\,\,\cdots\,\, \gamma^{\ell-1}(t)) N(t)$ , that is

(5)

$\theta(b^-,t)-\theta(a^+,t) = \sum_{n=1}^\ell\sum_{m=1}^{\ell-1}\gamma^m(t)N_{mn}(t)I_n.$

From this can be derived

Theorem $\quad$ The topological entropy $h(f)$ of $f$ is positive if and only if $D(t)$ has a zero in $|t|<1$ . In this case, $h(f)=\log\frac{1}{r}$ , where $r$ is the smallest zero of $D(t)$ in $[0,1)$ , and $D(t)$ has no zeros in $|t|<r$ .

The relationship between the kneading determinant and the Artin-Mazur zeta function of $f$ is also almost identical to that in the unimodal case, the only complication being a greater variety of different possible behaviours of $f$ on the endpoints of $I=[a,b]$ . Recall that the condition that all but finitely many of the periodic orbits of $f$ are unstable is guaranteed if $f$ is a rational function, or has negative Schwarzian derivative.

Theorem $\quad$ Suppose that $f$ is differentiable, has only finitely many periodic orbits of each period, and that all but finitely many of its periodic orbits are unstable. Let $\zeta(t)$ denote the Artin-Mazur zeta function of $f$ . Then

$\zeta(t)^{-1} = D(t)\prod_P\kappa_P(t),$

where the product is over the periodic orbits $P$ of $f$ which are either not unstable, or are contained in the endpoints of $I$ , and the polynomials $\kappa_P(t)$ are as follows: if $P$ has period $k$ then

If $P$ is contained in the endpoints of $I$ , then $\kappa_P(t)=(1-t^k)^2$ if $P$ is stable (on one side), and $\kappa_P(t)=1-t^k$ otherwise.
For each other non-unstable periodic orbit , is
- $1-t^k$ if $P$ is stable on one side only;
- $1-t^{2k}$ if $P$ is stable and the derivative of $f^k$ is negative at the points of $P$ ;
- $(1-t^k)^2$ if $P$ is stable and the derivative of $f^k$ is non-negative at the points of $P$ (other than any endpoints of $I$ contained in $P$ ).

In particular, $\zeta(t)$ has radius of convergence $r=1/s$ , where $s$ is the growth number of $f$ .

Just as unimodal maps with positive topological entropy can be semi-conjugated to tent maps, so piecewise monotone maps with positive topological entropy can be semi-conjugated to piecewise-linear maps.

Theorem $\quad$ Suppose that the growth number $s$ of $f$ satisfies $s>1$ . Define a function $\lambda:[a,b]\to[0,1]$ by

$\lambda(x) = \lim_{t\nearrow 1/s}\frac{\ell^{[a,x]}(t)}{\ell(t)}.$

(Here $\ell^J(t)=\sum_{i=0}^\infty \ell_{i+1}^J t^i$ , where $\ell_i^J$ is the number of laps of $f^i|_J$ for a subinterval $J$ of $I$ .) Then $\lambda$ is a continuous increasing surjection, and there is a piecewise linear map $F:[0,1]\to[0,1]$ , for which each linear piece has slope $\pm s$ , such that

$F\circ\lambda = \lambda\circ f.$

Note that $F$ may have fewer laps than $f$ .

[edit]

Example

Figure 6: The graph of $f$

Let $f:[0,1]\to[0,1]$ be the bimodal map given by $f(x)=1-7.03x+18.68x^2-12.65x^3$ (see Fig.6). The two turning points of $f$ are $c_1\simeq 0.2534$ and $c_2\simeq 0.7311$ . $f$ has a stable fixed point $P_1\simeq 0.2217$ and a stable period 3 orbit given approximately by $P_3 = \{0.5753, 0.7295, 0.9016\}$ . Since $f$ has negative Schwarzian derivative, there are no other stable periodic orbits. The signs associated to the laps of $f$ are given by $\epsilon_1 = -1$ , $\epsilon_2 = +1$ , and $\epsilon_3 = -1$ . The endpoints $0$ and $1$ are exchanged by $f$ .

The turning point $c_1$ is in the immediate basin of attraction of the fixed point $P_1$ , and the turning point $c_3$ is in the immediate basin of attraction of the period 3 orbit $P_3$ . Hence

$\begin{array}{rcll} k(c_1^-) &=& 1^\infty & \mbox{ so }\quad\theta(c_1^-,t) = \left(1-\frac{t}{1+t}\right)I_1, \\ k(c_1^+) &=& 2\,1^\infty & \mbox{ so }\quad\theta(c_1^+,t) = \left(\frac{t}{1+t}\right)I_1 + I_2,\\ k(c_2^-) &=& 2\,(3\,2\,2)^\infty \quad & \mbox{ so }\quad \theta(c_2^-,t) = \left(1-\frac{t^2+t^3}{1+t^3}\right) I_2 + \left(\frac{t}{1+t^3}\right)I_3, \mbox{ and}\\ k(c_2^+) &=& 3\,(3\,2\,2)^\infty & \mbox{ so }\quad\theta(c_2^+,t) = \left(\frac{t^2+t^3}{1+t^3}\right)I_2 + \left(1-\frac{t}{1+t^3}\right)I_3. \end{array}$

The kneading increments are therefore given by

$\begin{array}{rcl} \nu_1(t) &=& \theta(c_1^+,t)-\theta(c_1^-,t) = \left(-1+\frac{2t}{1+t}\right)I_1 + I_2,\\ \nu_2(t) &=& \theta(c_2^+,t)-\theta(c_2^-,t) = \left(-1+\frac{2(t^2+t^3)}{1+t^3}\right)I_2 + \left(1-\frac{2t}{1+t^3}\right)I_3, \end{array}$

giving the kneading matrix

$N(t) = \begin{pmatrix} -1 + \frac{2t}{1+t} & 1 & 0 \\ 0 & -1+\frac{2(t^2+t^3)}{1+t^3} & 1-\frac{2t}{1+t^3} \end{pmatrix} .$

The kneading determinant $D(t)$ is the determinant of the matrix obtained by deleting the first column of $N(t)$ , divided by $1+t$ , that is

$D(t)=\frac{1}{1+t}\left(1-\frac{2t}{1+t^3}\right) = \frac{(1-t)(1-t-t^2)}{(1+t^3)(1+t)}.$

The only zero of $D(t)$ in $[0,1)$ is $r=(\sqrt{5}-1)/2$ , so $f$ has growth number $s=1/r=(\sqrt{5}+1)/2$ , and topological entropy $h(f)=\log\left(\frac{\sqrt{5}+1}{2}\right)$ .

The cutting invariant of $f$ can be obtained after calculating $\theta(1,t)-\theta(0,t)=\left(\frac{-1}{1-t}\right)I_1 + \left(\frac{1}{1-t}\right)I_3$ . (5) then gives

$\begin{pmatrix} \gamma^1(t) & \gamma^2(t) \end{pmatrix} \, \begin{pmatrix} -1 + \frac{2t}{1+t} & 1 & 0 \\ 0 & -1+\frac{2(t^2+t^3)}{1+t^3} & 1-\frac{2t}{1+t^3} \end{pmatrix} = \begin{pmatrix} \frac{-1}{1-t} & 0 & \frac{1}{1-t} \end{pmatrix} .$

Therefore $\gamma^1(t)=\frac{1+t}{(1-t)^2}$ , $\quad\gamma^2(t)=\frac{1+t^3}{(1-t)^2(1-t-t^2)},\quad$ and

$\gamma(t) = \gamma^1(t)+\gamma^2(t) = \frac{2(1+t)}{(1-t)(1-t-t^2)}.$

The lap invariant $\ell(t)$ is then given by (1) as

$\ell(t) = \frac{1}{1-t}\left(1+\gamma(t)\right) = \frac{3+t^3}{(1-t)^2(1-t-t^2)} = 3+9t+21t^2+43t^3+81t^4+145t^5+\cdots.$

Thus, for example, $f^4$ has 43 laps.

The Artin-Mazur zeta function $\zeta(t)$ of $f$ is given by

$\zeta(t)^{-1} = D(t)(1-t^2)^2(1-t^6) = (1-t)^2(1-t^2)(1-t^3)(1-t-t^2),$

since $f'(P_1)<0$ (giving a factor $1-t^2$ ), $(f^3)'$ is negative at the points of $P_3$ (giving a factor $1-t^6$ ), and the endpoints $\{0,1\}$ constitute an unstable period 2 orbit (giving a factor $1-t^2$ ). Hence

$\frac{t\zeta'(t)}{\zeta(t)} = 3t+7t^2+9t^3+11t^4+13t^5+25t^6+31t^7+\cdots.$

Thus, for example, $f^5$ has 13 fixed points, comprised of 3 fixed points and 2 period 5 orbits of $f$ .

Figure 7: The function which semiconjugates $f$ to a piecewise linear map

Figure 8: The piecewise linear model of $f$

The graph of the function $\lambda:[0,1]\to[0,1]$ which semiconjugates $f$ to a piecewise linear map is shown in Fig.7. For each $x$ , $\lambda(x)$ can be approximated as follows:

Calculate $\theta(x,t)-\theta(0,t) = a_1(t)I_1+a_2(t)I_2+a_3(t)I_3$ up to the term in $t^{50}$ .
By (an analogue of) (5),

$\begin{pmatrix} \gamma^{[0,x],1}(t) & \gamma^{[0,x],2}(t) \end{pmatrix} \, \begin{pmatrix} -1 + \frac{2t}{1+t} & 1 & 0 \\ 0 & -1+\frac{2(t^2+t^3)}{1+t^3} & 1-\frac{2t}{1+t^3} \end{pmatrix} = \begin{pmatrix} a_1(t) & a_2(t) & a_3(t) \end{pmatrix}$

(here $\gamma^{[0,x],n}(t)=\sum_{i=0}^\infty \gamma_i^{[0,x],n}t^i$ , where $\gamma_i^{[0,x],n}$ is the number of points $y\in(0,x)$ such that $f^i(y)=c_n$ , but $f^j(y)$ is not a turning point for $j<i$ ).

Then $\lambda(x)$ is obtained by evaluating the limit of $\frac{\gamma^{[0,x],1}(t)+\gamma^{[0,x],2}(t)}{\gamma(t)}$ as $t\to r=(\sqrt{5}-1)/2$ .

This function $\lambda$ semi-conjugates $f$ to the piecewise linear map $F:[0,1]\to[0,1]$ which has $F(0)=1$ , $F(1)=0$ , slope $\pm s$ in each linear piece, and turning points at $C_1=(3-\sqrt{5})/2$ and $C_2 = 3(\sqrt{5}-1)^2/8$ (see Fig.8). Notice that $C_1$ is a fixed point of $F$ , and $C_2$ is a period 3 point of $F$ .

[edit]

Other directions

This article has summarised kneading theory as developed in Milnor and Thurston 1988. Since Milnor and Thurston's work, the theory has been extended to a variety of other contexts, and applied in other ways. The following is a partial list.

It is possible to characterize admissible matrices over ${\mathbb{Z}}[[t]]$ , that is, those which can be realized as kneading matrices of some piecewise monotone interval map. Conditions for a family $f_\mu$ of piecewise monotone maps to be full (roughly, for the family to exhibit all admissible kneading matrices of the appropriate dimensions) are given by de Melo and van Strien 1993, Galeeva and van Strien 1996.
The set of kneading coordinates (itineraries) which are compatible with a given kneading matrix can also be characterized. In a family of polynomial interval maps, orbits which are destroyed on the interval migrate into the complex plane: the theory of complex dynamics plays a vital role in understanding the behaviour of such families. In another direction, pruning theory is an attempt to understand the set of "kneading coordinates" exhibited by Hénon-type maps of the plane (see for example Cvitanović, Gunaratne and Procaccia 1988).
Kneading theory can be extended in a natural way to piecewise monotone interval maps which are permitted to have a finite number of discontinuities. See for example Preston 1989 for a summary of results, and Rand 1978 and Williams 1979 for the special case of Lorenz maps.
Baladi and Ruelle 1994, Baladi 1995 introduce weighted kneading matrices for the computation of weighted zeta functions of the form

$\zeta_g(t)=\exp\sum_{k\ge 1}\frac{t^k}{k}\sum_{x\in\mbox{Fix}(f^k)}\prod_{i=0}^{k-1}g(f^i(x)),$

where $g:[a,b]\to{\mathbb C}$ is of bounded variation.

Kneading theory can be developed in the context of tree maps. See for example Baillif 1999, Baillif and de Carvalho 2001 and Alves and Sousa Ramos 2004.
Preston 1989 uses kneading theory to construct invariant measures of maximal entropy for piecewise monotone interval maps.

[edit]

Alternative notation

Quite often a different notation is used (which results in a less algebraic approach). Namely, instead of formal power series one considers kneading sequences. Letters are assigned to turning points and laps. The $n$ -th term of the $k$ -th sequence is the letter assigned to the set to which $f^{n+1}(c_k)$ belongs (where $c_k$ is the $k$ -th turning point). The sequence terminates if $f^{n+1}(c_k)$ is a turning point itself. For a unimodal map the letters are usually $L$ for the left lap, $R$ for the right one, and $C$ for the turning point; in this case there is only one kneading sequence. More information can be found for instance in Collet and Eckmann 1980.

[edit]

References

Ll. Alsedà, J. Llibre and M. Misiurewicz Combinatorial dynamics and entropy in dimension one Second Edition, World Scientific (Advanced Series in Nonlinear Dynamics, vol. 5), Singapore 2000.

J. Alves and J. Sousa Ramos Kneading theory for tree maps Ergodic Theory Dynam. Systems 24 (2004), no. 4, 957-985.

M. Artin and B. Mazur On periodic points Ann. of Math. (2) 81 1965 82-99.

M. Baillif Dynamical zeta functions for tree maps Nonlinearity 12 (1999), no. 6, 1511-1529.

M. Baillif and A. de Carvalho Piecewise linear model for tree maps Internat. J. Bifur. Chaos Appl. Sci. Engrg. 11 (2001), no. 12, 3163-3169.

V. Baladi and D. Ruelle An extension of the theorem of Milnor and Thurston on the zeta functions of interval maps Ergodic Theory Dynam. Systems 14 (1994), no. 4, 621-632.

V. Baladi Infinite kneading matrices and weighted zeta functions of interval maps J. Funct. Anal. 128 (1995), no. 1, 226-244.

P. Collet and J.-P. Eckmann Iterated Maps on the Interval As Dynamical Systems Birkhauser, Boston 1980.

P. Cvitanović, G. Gunaratne and I. Procaccia Topological and metric properties of Hénon-type strange attractors Phys. Rev. A (3) 38 (1988), no. 3, 1503-1520.

R. Galeeva and S. van Strien Which families of $l$ -modal maps are full? Trans. Amer. Math. Soc. 348 (1996), no. 8, 3215-3221.

J. Guckenheimer Sensitive Dependence to Initial Conditions for One Dimensional Maps Comm. Math. Phys. 70 (1979), no. 2, 113-160.

L. Jonker and D. Rand Bifurcations in one dimension. I. The nonwandering set Invent. Math. 62 (1981), no. 3, 347-365.

N. Metropolis, M. Stein and P. Stein On finite limit sets for transformations on the unit interval J. Combinatorial Theory Ser. A 15 (1973), 25-44.

M. Misiurewicz Absolutely continuous measures for certain maps of an interval Inst. Hautes Études Sci. Publ. Math. No. 53 (1981), 17-51.

M. Misiurewicz and W. Szlenk Entropy of piecewise monotone mappings Dynamical systems, Vol. II - Warsaw, pp. 299-310. Asterisque, No. 50, Soc. Math. France, Paris, 1977.

W. Parry Symbolic dynamics and transformations of the unit interval Trans. Amer. Math. Soc. 122 1966 368-378.

C. Preston What you need to know to knead Adv. Math. 78 (1989), no. 2, 192-252.

D. Rand The topological classification of Lorenz attractors Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 451-460.

R. Williams The structure of Lorenz attractors Inst. Hautes Études Sci. Publ. Math. No. 50 (1979), 73-99.

[edit]

Invited by:	Prof. James Meiss, Applied Mathematics University of Colorado
Action editor:	Prof. James Meiss, Applied Mathematics University of Colorado
Reviewer B:	Dr. Charles Tresser, IBM Thomas J. Watson Research Center, New York

Kneading theory

From Scholarpedia

Contents

The unimodal case

The cutting invariant and the lap invariant: topological entropy

The kneading determinant

Homtervals

The relationship between the kneading determinant and the cutting invariant

Topological entropy

The Artin-Mazur zeta function

Semi-conjugacy to piecewise-linear models

Renormalization

The multimodal case

Introduction

The cutting invariant, lap invariant, and growth number

The kneading matrix and kneading determinant

Theorems

Example

Other directions

Alternative notation

References

Recommended reading

Views

Personal tools

Scholarpedia

Encyclopedia of

For readers

For authors

Toolbox