This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
Introduction
The kneading sequences of a multimodal map f of a closed interval I are symbolic sequences that locate the iterates of its critical values up to the precision set by the partition defined by its critical points [15, 16]. See Sect. 2 for the exact meaning of these concepts in the present work and the general mathematical setting. Since the nth iterate of a critical point of f is a critical value of the nth iterate of f, fn, one may attach to the symbols of each kneading sequence of f a label informing about their minimum/maximum (or “critical”) character. The result is called a min-max sequence, one per critical point, consisting of min-max symbols. These symbols and sequences were introduced in [10, 11] for unimodal maps, and in [3] for multimodal maps. Thus, min-max sequences generalize kneading sequences in that they give additional geometric information about the extrema structure of fn at the critical points for all n ≥ 1. It turns out that the computational cost of a min-max symbol is virtually the same as of a kneading symbol. Indeed, the extra piece of information contained in each symbol of the min-max sequence generated by a critical point, as compared to the corresponding symbol of the kneading sequence generated by the same critical point, can be automatically retrieved from a look-up table once the min-max symbol of the previous iterate of f and the kneading symbol of the current iterate of f have been calculated.
The min-max symbols have been studied in recent years in the papers in [12] for twice-differentiable uni-modal maps, in [3] for twice-differentiable multimodal maps, and in [4,5] for just continuous multimodal maps. Along with theoretical aspects, such as a number of relations between the min-max symbols of a unimodal or multimodal map and certain geometrical properties of the map and its iterates, the practical aspects were also on the fore in those references. In particular, several numerical algorithms for the topological entropy [1, 19] can be found as well in those references, the algorithm in [5] being a variant of the algorithm in [4] and this one a simplification of the algorithm in [3]. The interested reader is also referred to [6–9, 13, 14, 18] for several numerical techniques to compute the topological entropy with various degrees of generality.
In this paper we review two interesting applications of the min-max symbols of a multimodal map f , namely, new expressions for its topological entropy, h(f), and a general algorithm to compute it. In so doing we resort to the well-known expression
where lap(fn) is shorthand for the lap number of fn (i.e., the number of maximal monotonicity segments of fn) [2, 17]. We will see in Sect. 3 that the min-max symbols allow to relate lap( fn) with the number of ‘transversal’ intersections of fn with the so-called critical lines. Let us also recall at this point other remarkable formulas such as
where Var(fn) stands for the variation of fn [17].
The rest of this paper is organized as follows. In order to make the paper self-contained, we summarize in Sect. 2 all the basic concepts, especially the concept of min-max sequences, needed in the subsequent sections, and the concept of ‘bad’ symbols, which are the hallmark of this approach. In Sect. 3 we derive the two new expressions (11) and (19) for h(f ), which add to (1)-(3). A third expression, Eq. (22), is derived in Sect. 4 and, in turn, transformed into a numerical scheme to compute h(f). The resulting algorithm is put to test with bimodal and trimodal maps in Sects. 4.1 and 4.2.
In sum, the following pages give a general panorama of the min-max symbols in action. For other applications of the min-max symbols the reader is referred to [3]. Further applications are the subject of current research.
Preliminaries
Let I be a compact interval [a,b] ⊂ ℝ and f : I → I a piecewise monotone continuous map. Such a map is called l-modal if f has precisely l turning points (i.e., points in (a,b) where f has a local extremum). More precisely, we assume that f has local extrema at c1 < ... < cl and that f is strictly monotone on each of the l + 1 intervals
The set of l-modal maps will be denoted hereafter as ℳl(I), ℳl([a,b]), or just ℳl if the interval I = [a,b] is clear from the context or unimportant for the argument. As in the Introduction, sometimes one also speaks of multimodal maps in general, the name unimodal map being reserved for the case l = 1. Furthermore, if f(c1) is a maximum (resp. minimum), f is said to have a positive (resp. negative) shape.
The itinerary of x ∈ I under f is a symbolic sequence
It is easily shown [3] that the iterates of the critical points, fn(ci), are local extrema. This information is included in the min-max sequences of an l-modal map f,
and $\begin{array}{}
\displaystyle
\gamma _n^i
\end{array}$ are kneading symbols [3, 10–12]. Hence, the min-max symbols$\begin{array}{}
\displaystyle
\omega _n^i
\end{array}$ are a generalization of the kneading symbols $\begin{array}{}
\displaystyle
\gamma _n^i
\end{array}$ in that they also specify whether fn(ci) is a maximum or a minimum. In the exponential-like notation of (5), the ‘base’ belongs to the alphabet {m,M}, and the ‘exponent’ (also called signature in [3]) belongs to the alphabet {I1,c1,I2,...,cl,Il+1}. Therefore, the extra information of a min-max symbol $\begin{array}{}
\displaystyle
\omega _n^i
\end{array}$ as compared to a kneading symbol $\begin{array}{}
\displaystyle
\gamma _n^i
\end{array}$ is contained in its base.
In [4, Theorem 1] it is proved that if f ∈ ℳl has a positive shape, then the ‘transition rules’ given in Table 1 hold:
Transition rules for l-modal maps with a positive shape.
Here “even” and “odd” refer to the parity of the subindices of Ij(1 ≤ j ≤ l + 1) or ck(1 ≤ i ≤ l) in the exponent of $\begin{array}{}
\displaystyle
\omega _n^i
\end{array}$. If, otherwise, f has a negative shape, then one has to swap m and M on the right column of Table 1 [4, Theorem 1]:
Transition rules for l-modal maps with a negative shape.
These transition rules prove our claim in the Introduction that, from the point of view of the computational cost, min-max sequences and kneading sequences are virtually equivalent.
Let the ith critical line, 1 ≤ i ≤ l, be the line y = ci on the Cartesian plane {(x,y) : x,y ∈ ℝ}. Min-max symbols split into bad and good symbols with respect to the ith critical line. Geometrically, the latter correspond to local maxima strictly above the line y = ci, and to local minima strictly below the line y = ci. All other min-max symbols are bad by definition with respect to the ith critical line. We use the notation
for the set of bad symbols of f ∈ ℳl with respect to the ith critical line. There are 2(l + 1) bad symbols and 2l good symbols with respect to a given critical line. Fig. 1 shows four bad min-max symbols with respect to the critical line y = ci. Since the concept of bad symbol needs the minimum/maximum character of fn(ci), it is a distinctive ingredient of properties derived via min-max symbols.
For further reference, define the sets of pairs of indices
(n ≥ 1, 1 ≤ i ≤ l). That is, $\begin{array}{}
\displaystyle
{\mathscr K}_n^i
\end{array}$ collects the upper and lower indices (k,m), respectively, of the bad symbols with respect to the ith critical line in all the initial segments of length n of the min-max sequences of f:
Let f ∈ ℳl(I). Since f is continuous and piecewise strictly monotone, so is fn for all n ≥ 2 as well. We say that x0 ∈ I is an interior simple zero of fn(x) − ci = 0, n ≥ 0, if a < x0 < b, fn(x0) = ci, and fn(x0) is not a local extremum, thus fn(x) −ci takes both signs in every neighborhood of x0. In the case of (everywhere) differentiable maps, an interior simple zero x0 of fn(x) − ci = 0 amounts geometrically to a transversal intersection on the two-dimensional interval I × I = {(x,y) : x,y ∈ I} of the curve y = fn(x) and the critical line y = ci.
Let $\begin{array}{}
\displaystyle
s_n^i
\end{array}$, 1 ≤ i ≤ l, stand for the number of interior simple zeros of fn(x) − ci = 0, n ≥ 0. In order to simplify the notation, set
which expresses the topological entropy of a multimodal map f by means of the number of interior simple zeros of fn(x) − ci = 0, 1 ≤ i ≤ l, or, in more geometrical terms, via the number of ‘transversal’ intersections of fn with the critical lines, for n ≥ 1.
For (11) to provide also a practical tool for computing h(f), a procedure is needed to go from s0,s1,...,sn−1 to sn. Here is where the min-max sequences of f enter the scene.
We say that an l-modal map f of the interval I = [a,b] is boundary-anchored if f{a,b} ⊂ {a,b}, i.e., if
It is well-known that when it comes to calculate the topological entropy of an l-modal map f, h(f), then one may assume without restriction that f is boundary-anchored. Explicitly, given f ∈ ℳl(I) there exist a closed interval J ⊃ I and F ∈ ℳl(J) such that h(F) = h(f) and F is boundary-anchored; see, e.g., [4, Theorem 3] and the references therein.
Therefore, assume for the time being that f ∈ ℳl is boundary-anchored. Then it is proved in [4, Theorem 2] that for any n ≥ 1, 1 ≤ i ≤ l,
Note that the right hand of (12) only contains the numbers sν with 0 ≤ ν ≤ n − 1, what allows to calculate sn in a fully recursive way from the seeds $\begin{array}{}
\displaystyle
s_0^1 = ... = s_0^l = 1
\end{array}$. This fact and Remark 1 render Eq. (11) a formula for actually computing the topological entropy of any (i.e., not necessarily boundary-anchored) l-modal map f. Since the calculation of $\begin{array}{}
\displaystyle
S_n^i
\end{array}$ involves the bad symbol set $\begin{array}{}
\displaystyle
{\mathscr K}_n^i
\end{array}$, the corresponding algorithm presupposes the knowledge of the min-max symbols $\begin{array}{}
\displaystyle
\omega _m^k
\end{array}$ with 1 ≤ k ≤ l, and 1 ≤ m ≤ n.
Remark 2
The generalization of (12) to general f ∈ ℳl, regardless of the boundary conditions, can be found in [3, Theorem 5.3].
The relation (14) not only promotes (11) to the basis of an algorithm for the computation of h(f) via minmax symbols, but also leads to a further expression for h(f). For this insert (10) in (14) to write the lap number lap(fn) of a boundary-anchored l-modal map as
Next we derive from (16) a formula for h(f) which involves the min-max symbols of f in an explicit manner. To this end we are going to express sn in terms of S1,...,Sn.
for boundary-anchored l-modal maps. Apply now (1) to (18) and derive the following formula for the topological entropy of any l-modal map in virtue of Remark 1.
According to (19) h(f) ≤ log(l+1) =: h(f)max, a well-known result for l-modal maps. Therefore, (19) expresses the difference h(f)max − h(f) by means of the sequence (Sn)n≥1. Note that the convergence is monotonic, i.e.,
0 ≤ x ≤ 1, 0 < ν ≤ 1, was extensively studied in [5, Sect. 6].
Computation of the topological entropy
In this section we are going to review a general algorithm to compute h(f) [4]. This algorithm is based on the formula for h(f) which follows readily from (1) and (16),
again for any l-modal map f (Remark 1). All we need is a recursive scheme to compute the right hand side of (22) for ever larger n’s.
The core of the algorithm consists of a loop over n. Each time the algorithm enters the loop, the values of sn−1 and Sn−1 are updated to sn and Sn, and the current estimation of h(f) is compared to the previous one. Note that the computation of $\begin{array}{}
\displaystyle
S_n^i
\end{array}$, 1 ≤ i ≤ l, requires $\begin{array}{}
\displaystyle
s_0^i = 1
\end{array}$, $\begin{array}{}
\displaystyle
s_1^i,...,s_{n - 1}^i
\end{array}$, see (13), while the computation of $\begin{array}{}
\displaystyle
s_n^i
\end{array}$, 1 ≤ i ≤ l, requires $\begin{array}{}
\displaystyle
s_0^i,s_1^i,...,s_{n - 1}^i
\end{array}$, and $\begin{array}{}
\displaystyle
S_n^i
\end{array}$, see (12). Note also that $\begin{array}{}
\displaystyle
{\mathscr K}_n^i = {\mathscr K}_{n - 1}^i \cup ({\mathscr K}_n^i\backslash {\mathscr K}_{n - 1}^i)
\end{array}$, where
(A4) Computation loop. For 1 ≤ i ≤ l and n ≥ 2 keep calculating $\begin{array}{}
\displaystyle
{\mathscr K}_n^i,S_n^i
\end{array}$, and $\begin{array}{}
\displaystyle
s_n^i
\end{array}$ according to the recursions
As a matter of course, the parameter ε does not bound the error $\begin{array}{}
\displaystyle
\left| {h(f) - \frac{1}{n}\log \frac{{{s_n} + {S_n}}}{l}} \right|
\end{array}$ but the difference between two consecutive estimations, see (25). The number of exact decimal positions of h(f) can be found out by taking different ε’s, as we will see in the numerical simulations below. Equivalently, one can control how successive decimal positions of $\begin{array}{}
\displaystyle
\frac{1}{n}\log \frac{{{s_n} + {S_n}}}{l}
\end{array}$ stabilize with growing n. Moreover, the smaller h(f), the smaller ε has to be chosen to achieve a given numerical precision.
Remark 3
There are, of course, very efficient algorithms for the computation of h(f) tailored to particular cases; for unimodal maps, see, e.g., [7]. Also in the unimodal case, the relation (16) leads easily to the recursive formula [12]
n ≥ 1, which allows to compute h(f) in a simple and fast manner.
The algorithm (A1)-(A5) was benchmarked in [4] against (27) for unimodal maps and against the algorithm of [3] (also based on (22)) for l-modal maps with 2 ≤ l ≤ 5. The result was that (27) is faster for unimodal maps, otherwise the algorithm (A1)-(A5) is faster. Let us mention in passing that (19) was used in [5] to derive a similar though slower computational scheme.
For the sake of completeness, we show next numerical results obtained with the above algorithm (A1)-(A5) applied to bimodal and trimodal maps. The algorithm was coded for arbitrary l with PYTHON and run on an Intel(R) Core(TM)2 Duo CPU. The base of the logarithm function is 2.
Bimodal maps
Consider the bimodal maps fν1,ν2: [0,1] → [0,1] defined as
Therefore, if we choose ν1 > ν2, then fν1,ν2 has a positive shape, while ν1 < ν2 entails a negative shape. Fig. 2 shows the graphs of the full range maps f1,0 and f0,1, together with f0.75,0.25 and f0.25,0.75.
Fig. 3 shows the plot of h(f0,ν2) vs. ν2, 0 < ν2 ≤ 1, computed with ε = 10−4 and Δν2 = 0.001. Fig. 4 depicts the values of h(fν1,ν2) vs. ν1 and ν2, with ε = 10−4 and Δν1 = Δν2 = 0.01. Finally, Table 3 illustrates the convergence of the algorithm (as measured by the number of computation loops) when calculating h(f0.1,0.9). We see that ε = 10−7 is necessary to fix the first two decimal positions.
Performances when computing h(f0.1,0.9) in bits with the bimodal map.
precision
h
n
ε = 10−4
0.655591287672
179
ε = 10−5
0.643433302022
565
ε = 10−6
0.639578859603
1786
ε = 10−7
0.638359574751
5645
Trimodal maps
Consider the trimodal maps gν1,ν2 : [0,1] → [0,1] defined as
As before, if we choose ν1 > ν2, then gν1,ν2 has a positive shape, while ν1 < ν2 entails a negative shape. Fig. 5 shows the graphs of the full range maps g1,0 and g0,1, together with g0.75,0.25 and g0.25,0.75.
Fig. 6 shows the plot of h(g0,ν2) vs. ν2, 0 < ν2 ≤ 1, computed with ε = 10−4 and Δν2 = 0.001. Fig. 7 depicts the values of h(gν1,ν2) vs. ν1 and ν2, with ε = 10−4 and Δν1 = Δν2 = 0.01. Finally, Table 4 illustrates the convergence of the algorithm when calculating h(g0.1,0.9). Here ε = 10−6 fixes the first two decimal positions.
Performances when computing h(g0.1,0.9) in bits with the trimodal map.
precision
h
n
ε = 10−4
1.02013528493
203
ε = 10−5
1.00638666069
640
ε = 10−6
1.00202049572
2023
ε = 10−7
1.00063926538
6394
Conclusion
In this paper we have reviewed a few applications of the min-max symbols to both theoretical and computational aspects of the topological entropy of multimodal maps. Among the first, see Eqs. (19) and (22); among the latter, see the fast and numerically stable algorithm for h(f) presented in Sect. 4, which is based on Eq. (22). The application of this algorithm to bimodal and trimodal maps was illustrated in Sect. 4 as well. The expressions (19), (22), and also (11) add to other well-known ones for h(f) such as (1)-(3).