Discrete Maps and Iterated Functions — Mathematics Knowledge System

Overview

Discrete dynamical systems, or maps, iterate a function f: X -> X repeatedly: x_0, f(x_0), f^2(x_0), ... The logistic map x_{n+1} = r*x_n*(1-x_n) is the canonical example, exhibiting everything from stable fixed points to period doubling to fully developed chaos as the parameter r increases from 0 to 4. Sharkovskii's theorem gives a remarkable ordering on the positive integers that dictates which periods can coexist: the existence of a period-3 orbit forces all other periods, making period-3 the 'strongest.' The bifurcation diagram of the logistic map — a fractal structure of periodic windows and chaotic bands — is perhaps the most famous illustration of the route to chaos.

Intuition

The logistic map models a population that grows geometrically but is limited by overcrowding. When r is small, the population settles to a fixed level. As r increases, the population starts oscillating between two values (period 2), then four (period 4), and so on through a doubling cascade. Past r approx 3.57, the oscillation never repeats — chaos. But inside the chaos, bright periodic windows appear: tiny parameter intervals where the system is periodic again, the most prominent being the period-3 window near r = 3.83. Sharkovskii's theorem explains the order: once period-3 appears, every other period must also be present.

Formal Definition

Definition

A discrete dynamical system is a map f: X -> X, with orbit x_0, x_1 = f(x_0), x_2 = f^2(x_0), ... A period-n point satisfies f^n(p) = p but f^k(p) ≠ p for 0 < k < n.

x_{n+1} = r\, x_n(1 - x_n), \quad x_n \in [0,1], \quad r \in [0,4]

Logistic map

f^n(p) = p, \quad f^k(p) \neq p \text{ for } 1 \leq k < n \implies p \text{ has period } n

Period-n point definition

\lambda = \lim_{n\to\infty} \frac{1}{n} \sum_{k=0}^{n-1} \ln |f'(x_k)|

Lyapunov exponent of the map

\frac{r_n - r_{n-1}}{r_{n+1} - r_n} \to \delta \approx 4.6692 \quad \text{(Feigenbaum constant)}

Period-doubling convergence rate

Notation

Notation	Meaning
$f^n$	n-th iterate of f (apply f n times)
$\text{Per}(f)$	Set of all periodic points of f
$r_\infty$	Accumulation point of period-doubling bifurcations (approx 3.5699 for logistic map)
$\delta$	Feigenbaum's constant approx 4.6692

Theorems

Theorem 1: Sharkovskii's Theorem

Define the Sharkovskii ordering on positive integers: 3 > 5 > 7 > ... > 2*3 > 2*5 > ... > 4*3 > ... > 2^3 > 2^2 > 2 > 1. If f: R -> R is continuous and has a periodic point of period m, then f has a periodic point of period n for every n that comes after m in the Sharkovskii ordering. In particular, period 3 implies all other periods.

Theorem 2: Feigenbaum Universality

For any smooth unimodal map f_r with a quadratic maximum, the period-doubling bifurcation parameters r_1 < r_2 < ... satisfy (r_n - r_{n-1})/(r_{n+1}-r_n) -> delta approx 4.6692 (Feigenbaum's constant). Moreover, the geometry of the bifurcation diagram rescales in the x-direction by alpha approx -2.5029 at each level. Both constants are universal, independent of the specific map.

Theorem 3: Stability of Fixed Points for Maps

A fixed point p of f (f(p)=p) is stable if |f'(p)| < 1, unstable if |f'(p)| > 1, and neutrally stable if |f'(p)| = 1. A period-n orbit {p, f(p), ..., f^{n-1}(p)} is stable if the multiplier |(f^n)'(p)| = |f'(p) * f'(f(p)) * ... * f'(f^{n-1}(p))| < 1.

Worked Examples

1
Fixed points: r*x*(1-x) = x. For x ≠ 0: r*(1-x) = 1, so 1-x = 1/r, x* = 1 - 1/r = 1 - 1/2.5 = 0.6.
$x^* = 1 - \frac{1}{r} = 0.6$
2
Stability: |f'(x*)| = |r*(1-2x*)| = |2.5*(1-1.2)| = |2.5*(-0.2)| = 0.5 < 1.
$|f'(x^*)| = |r(1 - 2x^*)| = 0.5 < 1$
3
Since |f'(x*)| = 0.5 < 1, the fixed point x* = 0.6 is stable (attracting).

✓ Answer

Stable fixed point at x* = 0.6 with multiplier 0.5; nearby orbits converge to 0.6.

Practice Problems

Mediumfree response

For the logistic map with r = 3.2, show that the fixed point x* = 1-1/r is unstable and that a stable 2-cycle exists.

Mediumfree response

State Sharkovskii's theorem and explain why a continuous map of the interval with a period-5 orbit must also have a period-3 orbit.

Common Mistakes

Common Mistake

Thinking period-5 implies period-3 via Sharkovskii's theorem.

The Sharkovskii ordering is 3 > 5 > 7 > ...; period-3 forces period-5, but period-5 does NOT force period-3. The implication runs from earlier to later in the ordering.

Common Mistake

Thinking the Lyapunov exponent is just |f'| evaluated at a single fixed point.

The Lyapunov exponent is an ergodic average: lim (1/n) sum ln|f'(x_k)| over the orbit. For periodic and chaotic orbits this average differs from the derivative at any single point.

Common Mistake

Assuming chaos begins immediately after the first period-doubling bifurcation.

Chaos onset occurs after an infinite cascade of period doublings; the first doubling (period 1 to period 2) is far from chaos, which begins at r_inf approx 3.5699 for the logistic map.

Common Mistake

Equating topological conjugacy with smooth conjugacy.

Topological conjugacy preserves qualitative structure (periodic orbits, chaos) but not metric invariants like Lyapunov exponents. Smooth conjugacy preserves metric properties as well.

Quiz

Historical Background

Oleksandr Sharkovskii published his period-ordering theorem in 1964 in a Ukrainian journal, where it was largely overlooked until Li and Yorke rediscovered the period-3 case in 1975 and coined the word 'chaos.' Robert May's 1976 Nature article 'Simple Mathematical Models with Very Complicated Dynamics' introduced the logistic map to biologists and physicists, sparking enormous interest. Feigenbaum's 1978 discovery of the universal constant in period-doubling cascades showed that the route to chaos has a quantitative universality across all unimodal maps, a result later proved rigorously using renormalization group methods by Lanford and Collet-Eckmann-Koch.

1964
Sharkovskii publishes his period-ordering theorem
Oleksandr Sharkovskii
1975
Li and Yorke prove 'Period Three Implies Chaos' and coin the term 'chaos'
Tien-Yien Li, James Yorke
1976
Robert May publicizes the logistic map as a model of population dynamics
Robert May
1978
Feigenbaum discovers the universal constant delta approx 4.669 in period-doubling
Mitchell Feigenbaum

Summary

Discrete maps iterate f repeatedly; the logistic map x -> r*x*(1-x) is the canonical example exhibiting period-doubling routes to chaos.
Sharkovskii's theorem orders positive integers so that period-m implies all periods after m; period-3 is the strongest, forcing all other periods.
Feigenbaum's universal constant delta approx 4.669 governs the rate at which period-doubling bifurcations accumulate, universal across all smooth unimodal maps.
A period-n orbit is stable if its multiplier (product of |f'| around the orbit) is less than 1; positive Lyapunov exponent implies chaos.

References

BookStrogatz, S. H. Nonlinear Dynamics and Chaos. Westview Press, 2015. Chapter 10.
BookDevaney, R. An Introduction to Chaotic Dynamical Systems. Addison-Wesley, 1989. Chapters 1-2.
WebsiteWikipedia — Logistic map