𝔉𝔲𝔯𝔪𝔞𝔫 𝔘𝔫𝔦𝔳𝔢𝔯𝔰𝔦𝔱𝔶 Electronic Journal of Undergraduate Mathematics Volume 4, 1998 9 - 14

THE STRONG SHADOWING PROPERTY ON THE UNIT INTERVAL

JOSEPH H. BROWN AND JAMES O. WARREN

Abstract. We study continuous maps of the unit interval into itself. We determine necessary and sufficient conditions so that all pseudo-orbits can be approximated by orbits with the same initial point.

1. Introduction

For a metric space X, a function f :X →X, and x ∈ X, the sequence {f^{n}(x)}_{n=0}^{∞} is called the orbit of x, where f^{n} is the n-fold composition of f. Computers simplify the task of calculating orbits, but round-off error will create a “sloppy orbit” called a pseudo-orbit. These pseudo-orbits may or may not stay close to their actual orbits. If every pseudo-orbit stays close to some actual orbit, f is said to have the shadowing property.

To be precise, for δ > 0, a δ-pseudo-orbit of f is defined as a sequence {x_{n}}_{n=0}^{∞} such that d(x_{n+1}, f(x_{n})) ≤ δ for all n ∈ IN. Furthermore, a function f has the shadowing property if for ε > 0, there exists δ > 0 such that given a δ-pseudo-orbit {x_{n}}_{n=0}^{∞}, there exists x ∈ X where d(x_{n}, f^{n}(x)) < ε for all n ∈ IN.

Notice it may be the case that an actual orbit must start at a different point than a given pseudo-orbit in order to shadow it. For example, a continuous increasing function f : [0, 1] → [0, 1] with f(0) = 0, f(1) = 1, and f(x) > x on (0, 1) has the shadowing property by [3]. However, any δ-pseudo-orbit which starts at x_{0} = 0 and climbs toward 1 cannot be shadowed by the orbit fixed at 0.

Even though the pseudo-orbit may be close to some orbit, this is not always the desired result. Instead, since pseudo-orbits are typically generated when trying to generate an orbit, one may be interested in whether or not an orbit and pseudoorbit beginning at the same point will stay close to each other. This leads us to make the definition: f has the strong shadowing property if for ε > 0, there exists δ > 0 such that for any δ-pseudo-orbit {x_{n}}_{n=0}^{∞}, d(x_{n}, f^{n}(x_{0})) < ε for all n ∈ IN. The purpose of this paper is to characterize all continuous functions on [0, 1] which have the strong shadowing property.

Given a continuous function f : [0, 1] → [0, 1], let gr(f) denote the graph of f and gr^{−1}(f) denote the reflection of gr(f) about the diagonal i(x) = x. Also, f has a k-cycle (k ≥ 2) if there exists a set of k distinct points, {x_{0}, x_{1}, …, x_{k−1}}, such that f(x_{j}) = x_{j+1} (mod k). We show that the following three conditions are equivalent:

Received by the editors September 22, 1998.

1991 Mathematics Subject Classification. 58F03.

Key words and phrases. Shadowing property, Dynamical systems.

This work was originally done in 1993, when both authors participated in an NSF REU at Hope College. At that time James O. Warren was an undergraduate at Texas A&M University and Joseph H. Brown was an undergraduate at North Dakota State University.

1. f has the strong shadowing property

2. f has no cycles and only one fixed point

3. gr(f) and gr^{−1}(f) have exactly one point in common.

The equivalence of (2) and (3) is easily seen. If gr(f) and gr^{−1}(f) have more than one point in common, then either f has a 2-cycle or f has more than one fixed point. Conversely, if gr(f) and gr^{−1}(f) have exactly one point in common, f cannot have any 2-cycles. The Sarkovskii ordering of cycles [1, p.62] then guarantees that f has no cycles. Furthermore, any fixed point of f will be in the intersection of gr(f) and gr^{−1}(f), so f has only one fixed point.

2. Preliminaries

Throughout this paper, we take IN = {0, 1, 2, … }, “⊂” denotes strict containment, f^{0}(x) = x, and all intervals are intersected with [0, 1].

We begin with three lemmas first proved by Sarkovskii [4]. The original proofs were not accessible, so we provide the following arguments.

Lemma 1. Let f : [0, 1] → [0, 1] be a continuous function with no cycles. For x ∈ [0, 1], if f(x) > x, then f(y) > x for all y ∈ [x, f(x)] (if f(x) < x, then f(y) < x for all y ∈ [f(x), x]).

Proof: We prove this lemma by contradiction. Assume x ∈ [0, 1] with f(x) > x, and suppose there exists z ∈ [x, f(x)] such that f(z) ≤ x. Let y = max{t ∈ [x, f(x)] : f(t) = x}. Since f(x) > x and f(y) = x < y, f must intersect the diagonal i(t) = t in [x, y]. Thus, there exists at least one fixed point in [x, y]. Let p_{L} = max{t ∈ [x, y] : f(t) = t}. There are two cases to be considered.

Case 1: f has at least one fixed point p ∈ [y, 1]. Let p_{R} = min{t ∈ [y, 1] : f(t) = t}. Since f(y) = x < p_{L} and f(p_{R}) = p_{R} > p_{L}, there exists s_{1} ∈ (y, p_{R}) such that f(s_{1}) = p_{L} by the Intermediate Value Theorem. Similarly, there exists s_{2} ∈ (y, p_{R}) such that f(s_{2}) = s_{1}. Since f^{2}(y) = f(x) > y and f^{2}(s_{2}) = p_{L} < s_{2} with y, s_{2} ∈ (p_{L}, p_{R}), f^{2} must intersect the diagonal i(t) = t in the interval (p_{L}, p_{R}). Hence there exists p ∈ (p_{L}, p_{R}) such that f^{2}(p) = p and f(p) ≠ p, so f has at least one 2-cycle.

Case 2: f has no fixed points in [y, 1]. The point y was chosen so f(y) = x, f^{2}(y) = f(x) > y. Since the range of f^{2} is contained in [0, 1], f^{2}(1) < 1. So f^{2} must intersect the diagonal i(t) = t in the interval [y, 1]. Hence there exists p ∈ [y, 1] such that f^{2}(p) = p and f(p) ≠ p, so f has at least one 2-cycle.

Each of these cases contradicted that f has no cycles, so if f(x) > x, then f(y) > x for all y ∈ [x, f(x)]. Similar arguments prove that if f(x) < x, then f(y) < x for all y ∈ [f(x), x]. □

Lemma 2. Let f : [0, 1] → [0, 1] be a continuous function with no cycles. For all n_{1}, n_{2}, n_{3} ∈ IN (n_{1} < n_{2} < n_{3}) and x ∈ [0, 1], if f^{n_{2}}(x) ≠ f^{n_{3}}(x), then f^{n_{1}}(x) is not in the interval with endpoints f^{n_{2}}(x) and f^{n_{3}}(x).

Proof: Choose x ∈ [0, 1] and n_{1}, n_{2}, n_{3} ∈ IN (n_{1} < n_{2} < n_{3}) such that f^{n_{2}}(x) ≠ f^{n_{3}}(x). Since f^{n_{2}}(x) ≠ f^{n_{3}}(x), f^{n_{1}}(x) cannot be a fixed point. Without loss of generality, assume f^{n_{1}}(x) < f^{n_{1}+1}(x). We prove this lemma by using strong induction to show that f^{n}(x) > f^{n_{1}}(x) for n = n_{1} + 1, …, n_{3}.

Assume f^{k}(x) > f^{n_{1}}(x) for k = n_{1} +1, …, n where n < n_{3}. If f^{n}(x) = f^{n−1}(x), then f^{n+1}(x) = f^{n−1}(x) > f^{n_{1}}(x) by the induction hypothesis. If f^{n}(x) > f^{n−1}(x), then f(f^{n}(x)) > f^{n−1}(x) by Lemma 1. Thus, f^{n+1}(x) > f^{n−1}(x) ≥ f^{n_{1}}(x) by the induction hypothesis. If f^{n}(x) < f^{n−1}(x), let s = max{k ∈ IN, k < n : f^{k}(x) < f^{k+1}(x)}. We know s exists since f^{n_{1}}(x) < f^{n_{1}+1}(x).

We claim that f^{s}(x) < f^{n}(x) < f^{s+1}(x), for suppose f^{n}(x) < f^{s}(x). By the definition of s, we have the inequalities f^{s+1}(x) > f^{s+2}(x) > ⋯ > f^{n}(x). Hence, there exists p, s + 1 ≤ p ≤ n − 1, such that f^{p}(x) ∈ [f^{s}(x), f^{s+1}(x)] and f^{p+1}(x) ∉ [f^{s}(x), f^{s+1}(x)]. This contradicts Lemma 1, so f^{s}(x) < f^{n}(x). Furthermore, since f^{k}(x) < f^{k−1}(x) for k = s + 2, …, n, f^{n}(x) < f^{s+1}(x).

By Lemma 1, f(f^{n}(x)) = f^{n+1}(x) > f^{s}(x) ≥ f^{n_{1}}(x). Thus by induction, f^{n}(x) > f^{n_{1}}(x) for n = n_{1} +1, …, n_{3}. Therefore, f^{n_{1}}(x) is not in the interval with endpoints f^{n_{2}}(x) and f^{n_{3}}(x). □

Lemma 3. Let f : [0, 1] → [0, 1] be a continuous function. If f has no cycles, then for any x ∈ [0, 1], the orbit {f^{n}(x)}_{n=0}^{∞} will converge to a fixed point.

Proof: First notice that f^{n}(x) → z implies z is a fixed point of f. Let x ∈ [0, 1]. Since f has no cycles, m ≠ n implies f^{m}(x) ≠ f^{n}(x) or f^{m}(x) is a fixed point. We can assume that f^{m}(x) ≠ f^{n}(x) for m ≠ n. By the Bolzano-Weierstrass Theorem, {f^{n}(x)}_{n=0}^{∞} has a cluster point, z. We will show that z is unique.

Suppose that z′ is another cluster point of {f^{n}(x)}_{n=0}^{∞}. Without loss of generality, let z < z′. By Lemma 2, (z, z′) cannot contain any points from the orbit of x. Moreover, {f^{n}(x)}_{n=0}^{∞} is the union of two disjoint subsequences: {f^{n_{k}}(x)} ↑ z and {f^{m_{k}}(x)} ↓ z′. Hence, there exists a subsequence {a_{j}} of {f^{n_{k}}(x)}_{n=0}^{∞} such that f(a_{j}) → z′. Thus, f(z) = z′ by continuity. Similarly, f(z′) = z, which contradicts that f has no cycles. Therefore, the sequence {f^{n}(x)}_{n=0}^{∞} must converge to z, and z must be a fixed point of f by continuity. □

Our initial approach to proving that a function with one fixed point and no cycles has the strong shadowing property was to determine two arbitrarily small intervals containing the fixed point with one interval contained in the other. These intervals would have the property that the image of the larger interval would be contained within the smaller interval. Then we could determine δ such that all δ-pseudo-orbits would eventually be contained in the larger interval, so f would have the strong shadowing property.

However, we cannot guarantee such intervals for f. For example, a function with a fixed point which attracts on one side of the fixed point and repels on the other side cannot have these desired intervals. Nonetheless, we can prove the existence of these intervals for f^{2}.

Lemma 4. Let f : [0, 1] → [0, 1] be a continuous function with no cycles and one fixed point p. For ε > 0, there exists η > 0, I = (a, b), and I_{η} = (a − η, b + η) such that I ⊂ I_{η} ⊆ B_{ε}(p) with p ∈ I and f^{2}(I_{η}) ⊆ I.

Proof: Let ε > 0 be given. By Lemma 3, the fixed point p attracts the entire interval [0, 1]. Since p is the only fixed point of f, then f(x) > x on [0, p) and f(x) < x on (p, 1]. We begin by finding an interval I_{1} ⊆ B_{ε}(p) such that f(I_{1}) ⊆ I_{1}. There are two possible cases.

Case 1: f(B_{ε}(p)) ⊆ B_{ε}(p). Then define I_{1} = B_{ε}(p) and ε′ = ε/2.

Case 2: ∃z ∈ B_{ε}(p) such that f(z) ∉ B_{ε}(p). Without loss of generality, assume z ∈ (p, p + ε). Since f(x) < x on (p, 1], f(z) < p − ε. Let m_{1} = min{x ∈ [p, z] : f(x) = p − ε}, and define I_{1} = (p − ε, m_{1}), ε′ = m_{1} − p. We claim that f(I_{1}) ⊆ I_{1}. If x ∈ (p, m_{1}), then f(x) > p − ε. Furthermore, f(x) < x < m_{1}, so f(x) ∈ (p − ε, m_{1}). If x ∈ (p − ε, p), then there exists x_{1} ∈ (p, m_{1}) such that f(x_{1}) = x by the Intermediate Value Theorem. Since f(x) > x, Lemma 2 implies f(x) < x_{1} < m_{1}. Thus, f(x) ∈ (x, x_{1}) ⊆ (p − ε, m_{1}), so f(I_{1}) ⊆ I_{1}.

Construct I_{2} for B_{ε′}(p) as I_{1} was constructed for B_{ε}(p). Without loss of generality we have I_{2} = (a, b) such that f(I_{2}) ⊆ I_{2}. Let J = (c, d) denote an open interval of f^{−1}(I_{2}) such that I_{2} ⊂ J ⊂ I_{1}. There are two cases to be considered.

Case 1: c < a, b < d. Taking η = min{a − c, d − b}, we have f(I_{η}) ⊆ I_{2}, so f^{2}(I_{η}) ⊆ I_{2}.

Case 2: c = a, b < d (c < a, b = d done similarly). Then there exists e < c such that f((e, d)) ⊆ (c, d). We also know that f((c, d)) ⊆ (a, b) = I_{2}. By defining η =min{a − e, d − b}, f^{2}(I_{η}) ⊆ I_{2}.

In each of these cases I = I_{2} and I_{η} are the required intervals. □

Using this lemma, we will prove that f^{2} has the strong shadowing property, where f has no cycles and one fixed point p. To show that f itself has the strong shadowing property, we first establish the uniform convergence of {f^{k}}_{k=0}^{∞} to c(x) ≡ p on [0, 1]. Given ε > 0, by the proof of Lemma 4, there exists an open interval I ⊆ B_{ε}(p) such that p ∈ I and f(I) ⊆ I. We have pointwise convergence of {f^{k}} by Lemma 3, so for each x ∈ [0, 1] there exists N_{x} ∈ IN such that f^{n}(x) ∈ I if n ≥ N_{x}. Therefore, ⋃_{n∈IN} f^{−n}(I) is an open cover of [0, 1]. By the compactness of [0, 1], we can find N ∈ IN such that f^{N}(x) ∈ I for all x ∈ [0, 1]. Thus, |f^{n}(x) − p| < ε for all x ∈ [0, 1] and n ≥ N, so {f^{k}}_{k=0}^{∞} must converge uniformly to c(x) ≡ p.

Finally we show that if f^{2} has the strong shadowing property, then f has the strong shadowing property.

Lemma 5. Let f : [0, 1] → [0, 1] be a continuous function with no cycles and one fixed point p. If f^{k} has the strong shadowing property for some k ∈ IN, then f^{n} has the strong shadowing property for all n ∈ IN.

Proof: First we show that if f^{k} has the strong shadowing property, then f has the strong shadowing property. For arbitrary ε > 0, f^{k} having the strong shadowing property implies there exists δ′, 0 < δ′ < \frac{ε}{2}, such that all δ′-pseudo-orbits of f^{k} are \frac{ε}{2} strong shadowed. Moreover, we know from the uniform convergence of \{f^{n}\} that there exists N ∈ IN such that if n ≥ N, |f^{n}(x) − p| < \frac{ε}{4} for x ∈ [0, 1]. Let K = max{N, k}. From uniform continuity, we have the existence of 0 < δ_{1} < δ_{2} < ⋯ < δ_{K} < \frac{δ′}{K} such that d(x, t) < δ_{i} ⇒ d(f(x), f(t)) < δ_{i+1} for i = 1, …, K − 1.

We constructed this δ-chain so that for any δ_{1}-pseudo-orbit {x_{m}}_{m=0}^{∞} of f, the sequence {x_{j+nk}}_{n=0}^{∞} is a δ′-pseudo-orbit of f^{k}, where j ∈ IN. To see this, take an arbitrary j ∈ IN. Then d(x_{j+1}, f(x_{j})) < δ_{1} ⇒ d(f(x_{j+1}), f^{2}(x_{j})) < δ_{2} ⇒ ⋯ ⇒ d(f^{k−1}(x_{j+1}), f^{k}(x_{j})) < δ_{k}. Similarly, d(f^{k−2}(x_{j+2}), f^{k−1}(x_{j+1})) < δ_{k−1} < δ_{k}, d(f^{k−3}(x_{j+3}), f^{k−2}(x_{j+2})) < δ_{k−2} < δ_{k}, …, d(x_{j+k}, f(x_{j+k−1})) < δ_{1} < δ_{k}. Applying the triangle inequality, d(x_{j+k}, f^{k}(x_{j})) < k · δ_{k} < K · \frac{δ′}{K} = δ′. Therefore {x_{j+nk}}_{n=0}^{∞} is a δ′-pseudo-orbit of f^{k}.

By the construction of the δ-chain, d(x_{n}, f^{n}(x_{0})) < δ_{n} < \frac{ε}{2} < ε for n = 1, …, K. If n > K, let r ≡ n mod K, 0 ≤ r < K. If r = 0, then d(x_{n}, f^{n}(x_{0})) = d(x_{mk}, f^{mk}(x_{0})) < δ′ < ε since f^{k} has the strong shadowing property. Otherwise, n = mk + r where r ≠ 0, so d(x_{mk+r}, f^{mk}(x_{r})) < \frac{ε}{2}. Since n > K, then mk ≥ K, which implies mk ≥ N. Therefore, d(f^{mk+r}(x_{0}), p) < \frac{ε}{4} and d(f^{mk}(x_{r}), p) < \frac{ε}{4}, so d(f^{mk+r}(x_{0}), f^{mk}(x_{r})) < \frac{ε}{2}. Applying the triangle inequality again, we have d(f^{mk+r}(x_{0}), x_{mk+r}) = d(f^{n}(x_{0}), x_{n}) < ε. Thus, d(x_{0}, f^{n}(x_{0})) < ε for all n ∈ IN, so f has the strong shadowing property.

Finally, if f has the strong shadowing property, then so does f^{n} for all n ∈ IN. This follows because the δ-pseudo-orbits for f with d(x_{k}, f(x_{k−1})) = 0 for all k ≢ 0 mod n are simply the δ-pseudo-orbits for f^{n}. □

Notice that the last statement is independent of the condition that f has no cycles and one fixed point. We use this fact in the proof of the main theorem.

3. Main Result - The Strong Shadowing Property

Theorem 1. Given a continuous function f : [0, 1] → [0, 1] the following are equivalent:

1. f has the strong shadowing property

2. f has no cycles and one fixed point

3. gr(f) and gr^{−1}(f) have exactly one point in common.

Proof:

(1 ⇒ 2) Suppose f has more than one fixed point. Notice that f cannot have an interval of fixed points, otherwise the pseudo-orbit could move about the whole interval while the actual orbit remains fixed. Moreover, since f is continuous, the fixed points of f cannot even be dense in an interval by the same argument. Thus, there must exist fixed points p_{1} < p_{2} with no fixed points in the interval (p_{1}, p_{2}).

Without loss of generality we can assume f(x) > x on (p_{1}, p_{2}). Given δ > 0, consider the δ-pseudo-orbit x_{0} = p_{1}, x_{1} = x_{0} + \frac{δ}{2}, x_{n} = f(x_{n−1}) for n ≥ 2. Since f(x) > x on [p_{1} + \frac{δ}{2}, p_{2} − \frac{δ}{2}], the pseudo-orbit \{x_{n}\}_{n=0}^{∞} must move at least the distance \frac{p_{2}−p_{1}}{2} from p_{1}. Thus, f does not have the strong shadowing property.

We know by Lemma 5 that f having the strong shadowing property implies f^{n} has the strong shadowing property for all n ∈ IN. By the above, f^{n} must have one fixed point for all n ∈ IN. Therefore, f can have no cycles.

(2 ⇒ 1) Let g = f^{2}, then g has one fixed point p and no cycles. For arbitrary ε > 0, Lemma 4 implies there exist I = (a, b) and I_{η} ⊆ (p − \frac{ε}{2}, p + \frac{ε}{2}) with p ∈ I and g(I_{η}) ⊆ I. Furthermore, the uniform convergence of {g^{n}}_{n=0}^{∞} to c(x) ≡ p guarantees the existence of N ∈ IN such that g^{N}(x) ∈ I for all x ∈ [0, 1].

Since I_{η} ⊆ (p − \frac{ε}{2}, p + \frac{ε}{2}), η < \frac{ε}{2}. From the uniform continuity of g, we have the existence of 0 < δ_{1} < δ_{2} < … < δ_{N} < \frac{η}{N} such that d(x, t) < δ_{i} ⇒ d(g(x), g(t)) < δ_{i+1} for i = 1, …, N. Consider a δ_{1}-pseudo-orbit of g, {x_{n}}_{n=0}^{∞}. Thus, d(x_{1}, g(x_{0})) < δ_{1} ⇒ d(g(x_{1}), g^{2}(x_{0})) < δ_{2} ⇒ ⋯ ⇒ d(g^{N−1}(x_{1}), g^{N}(x_{0})) < δ_{N}. Similarly, d(g^{N−2}(x_{2}), g^{N−1}(x_{1})) < δ_{N−1} < δ_{N}, d(g^{N−3}(x_{3}), g^{N−2}(x_{2})) < δ_{N−2} < δ_{N}, …, d(x_{N}, g(x_{N−1})) < δ_{1} < δ_{N}. By applying the triangle inequality, d(x_{N}, g^{N}(x_{0})) < N · δ_{N} < N · \frac{η}{N} ≤ η < ε. Repeating this procedure, we get d(x_{n}, g^{n}(x_{0})) < ε for n = 1, …, N.

Since N iterations have occurred, g^{k}(x) ∈ I ⊆ I_{η} for all k > N. Furthermore, the δ_{1}-pseudo-orbit {x_{N+k}}_{k=1}^{∞} cannot leave I_{η} since δ < η. Since diam I_{η} < ε, d(x_{k}, g^{k}(x_{0})) < ε for all k > N. Therefore, g = f^{2} has the strong shadowing property, so f has the strong shadowing property by Lemma 5. □

A corollary to this theorem is that surjective functions on the unit interval do not have the strong shadowing property. By the theorem, we need only consider surjective functions with one fixed point. Let g be such a function with fixed point p. Therefore, g(x) > x on [0, p) and g(x) < x on (p, 1]. In particular, there exists a ∈ (p, 1] so that g(a) = 0, and there exists b ∈ [0, p) such that f(b) = a. Therefore, g^{2}(x) < x on some interval of [0, p), so g has at least one 2-cycle. Then g does not have the strong shadowing property.

4. References

1. R.L. Devaney, An Introduction to Chaotic Dynamical Systems, Addison Wesley, 1987.

2. T. Gedeon and M. Kuchta, Shadowing Property of Continuous Maps, Preprint.

3. T. Pennings and J. Van Eeuwen, Pseudo-Orbit Shadowing on the Unit Interval, Real Anal. Exch. 16:(1990-91).

4. A.N. Sarkovskii, On Cycles and the Structure of a Continuous Mapping, Ukrain. Mat. Ž. 17:(1965).

James O. Warren: SCCM Program, Stanford University

   E-mail address: warren@sccm.stanford.edu

Sponsor: Timothy Pennings, Hope College

   E-mail address: pennings@math.hope.edu