Orbit Census

affine·mess f(x) =

periods ≤8

Options

Grid points for the root search

Periodic points of period n are the roots of fⁿ(x) − x. They are bracketed on this grid and then polished by bisection. A finer grid finds the tightly packed ones of high period.

Sample paths per destination

Typical forward orbits, from starting points spread over the interval, drawn until they visibly reach their fate: a cycle, ∞, or no fate at all.

Bi-infinite paths

Paths that emerge from a repelling cycle: started a hair away from it, so going backwards they converge to it.

Preimage depth

Pre-periodic points hanging off each cycle: x with f(x) on the cycle, then their preimages, and so on (at most 400 in all).

Search effort

Newton's method on fⁿ(z) − z from a grid of starting points in the visible window, plus random restarts for polynomials until the count is complete or time runs out.

Background

Escape bound: |x| > 10^k

An orbit that grows past this bound is reported as escaping. All its values are exact integers.

Escaping orbits

Auto collapses them into the single node ∞ when they would crowd out the cycles.

Max steps per orbit

Starting window |x| ≤

Escape bound: height > 10^k

The height of p/q is max(|p|, q). Orbits whose height passes the bound are reported as escaping.

Every point of ℤ/n is eventually periodic, so the census here is complete: every cycle is found, of every length. Trees are drawn when n ≤ 4000.

Pick a space X and type a map f : X → X. Draw an arrow from every point x to f(x). Each connected piece of the resulting directed graph is a cycle with trees hanging off it, or a forward-infinite path that never closes up. This applet takes a census of the cycles: fixed points first, then cycles of length 2, 3, … up to the bound you set with periods ≤. On ℝ, intervals, ℤ, ℤ/n and ℚ the picture is that directed graph itself, never the graph of f: cycles are drawn as rings, the points that flow into them hang off them as trees, and a path that never closes up is drawn as a chain.

Cycles are colored by length. A filled dot is an attracting periodic point (the multiplier λ = f′(x₀)⋯f′(x_n−1) has |λ| < 1), a hollow dot is repelling. Click a row of the table, an orbit in the list, or a point in the picture to highlight it. Drag to pan, scroll or pinch to zoom; labels appear as you zoom in.

On ℝ and on an interval

Cycles. Points of period n are roots of fⁿ(x) − x. The applet evaluates this on a fine grid over [a, b], brackets each sign change, polishes it by bisection, and also hunts tangential roots where fⁿ only touches the diagonal. It sorts roots by their least period and merges points of the same cycle. On ℝ, [a, b] is only the search window and orbits may leave it; on an interval it is the space X, and cycles that leave it are discarded. For a polynomial of degree d ≥ 2 the table also shows the most cycles a period can have (see ℂ below), so you can see when the line has all of them, as for the logistic map at r = 4.

Pre-periodic points. Hanging off each cycle point c are its other preimages, the solutions of f(y) = c in the window, then their preimages, to the depth set in Options. These points land exactly on the cycle after finitely many steps.

Typical forward paths. The applet follows a few hundred orbits from starting points spread over the window and reports their fate: converging to an attracting (or neutral) cycle, tending to ±∞, leaving the interval, or never settling. A few of each are drawn step by step, x₀ (ringed) → x₁ → …, until they are visually indistinguishable from their limit. A dashed arrow into a ring means “converges to this cycle”, aimed at the point that the orbit's next step approaches. An attracting cycle of period higher than the bound can turn up this way too; it is listed under “found by following orbits”.

Bi-infinite paths. Start a hair away from a repelling cycle and iterate: the orbit moves away from the cycle and eventually meets its fate. Going backwards, the local inverse branch near the cycle contracts, so the backward orbit converges to the cycle. The result is a path infinite in both directions, from a repelling cycle (drawn as a dashed copy of the cycle point) to an attractor, to ∞, or to nowhere in particular. For the logistic map in the period-3 window, such paths run from the repelling fixed points into the attracting 3-cycle.

Rounding. For maps like 2x mod 1, the tent map or the period-5 example, every floating-point orbit eventually lands exactly on a repelling cycle, because each step shifts out one bit of the binary expansion. That is an artifact, not dynamics, so such orbits are counted as never settling, and their drawn paths stop well before it happens.

Sharkovsky's theorem

Order the positive integers like this:

3 ▷ 5 ▷ 7 ▷ 9 ▷ … ▷ 2·3 ▷ 2·5 ▷ … ▷ 4·3 ▷ 4·5 ▷ … ▷ 2^k·3 ▷ … ▷ 2³ ▷ 2² ▷ 2 ▷ 1

Odd numbers first, then twice the odds, then four times the odds, and so on, with the powers of 2 last, in decreasing order. Sharkovsky's theorem (1964): if a continuous map of an interval into ℝ has a point of least period m, it has points of least period n for every n with m ▷ n. In particular, period 3 forces every period (Li and Yorke rediscovered this in 1975 under the title Period three implies chaos). The theorem is sharp: for every m there is a continuous map whose set of periods is exactly {n : m ⊵ n}. The example pl(x, 1,3, 2,5, 3,4, 4,2, 5,1) is the classic one with period 5 and no period 3.

The proof only looks at the intervals between consecutive points of the given orbit and how f stretches them over each other. So it is enough that f is continuous on the smallest interval containing that orbit, and the forced orbits live inside that interval too. The applet uses exactly this: it takes the Sharkovsky-strongest period it found, checks numerically that f has no jumps or poles on the span of a witnessing orbit, and lights up every period that orbit forces, including periods beyond your search bound. Forced periods that the numerical search did not find are not errors in the theorem; they exist, usually in very thin windows.

A corollary worth knowing: if a continuous map has only finitely many periods, they are 1, 2, 4, …, 2^k. The logistic map at r = 3.5 is an example.

On ℤ, ℤ/n and ℚ

Here arithmetic is exact (big integers and fractions), and the picture is the functional graph itself: cycles as rings, trees of preimages hanging off them.

ℤ/n. The formula is evaluated as an exact rational at x = 0, 1, …, n − 1 and reduced mod n (a denominator must be invertible mod n). Since X is finite, every orbit ends in a cycle and the census is complete. The panel also reports the size of the image f(X) and the number of points with no preimage.

ℤ. Every orbit starting in the window |x| ≤ M is followed exactly until it closes a cycle, joins an orbit already seen, or passes the escape bound. Every cycle that meets the window is therefore found. Points outside the window are not drawn; a dashed arrow labeled +k means the orbit spent k − 1 steps outside before coming back. Orbits that pass the escape bound all flow into one node, ∞. For a polynomial that is honest: ∞ is a fixed point of the map extended to the projective line. When escaping orbits would crowd out the picture, only a few typical ones are drawn step by step and the rest are counted. The basin column counts the starting points that end up in each cycle. The Collatz map has exactly five known cycles on ℤ, of lengths 1, 2, 3, 5 and 18, and the conjecture is that there are no others.

ℚ. The starting points are the fractions p/q with q up to the bound and |p/q| ≤ the window. For a polynomial with rational coefficients, Northcott's theorem says the rational periodic points have bounded height, so an orbit whose height blows up is genuinely wandering. For x² + c one can have rational cycles of length 1, 2 and 3 (try c = −29/16). Poonen conjectured that no other lengths occur; lengths 4 and 5 are proven impossible, and length 6 is impossible under standard conjectures.

On ℂ

Periodic points are found with Newton's method applied to fⁿ(z) − z, started from a grid filling the visible window. For a polynomial of degree d ≥ 2, fⁿ(z) = z has dⁿ solutions with multiplicity, and Möbius inversion gives the number with least period exactly n:

ν(n) = Σ_{k | n} μ(n/k) d^k, so for d = 2: 2, 2, 6, 12, 30, 54, 126, 240, …

The table shows found / expected cycles (ν(n)/n), so you can see whether the hunt was complete. The background shades the escape time; the dark set is where orbits stay bounded (the filled Julia set, for a polynomial). Sharkovsky's theorem is a fact about the line and has no analogue here: z ↦ ωz with ω a primitive cube root of unity has the fixed point 0 and every other point has period 3, with no period 2 anywhere.

Writing f

Use x (or z), numbers, + − * / ^, implicit multiplication (3x, r x(1-x)), constants pi, e, i. Functions: sin cos tan exp log sqrt abs floor ceil round sign frac min max mod gcd, and the hyperbolic and inverse trig functions. a % b is the remainder in [0, b). Comparisons < <= == != >= > give 1 or 0, and if(cond, a, b) picks a branch. pl(x, x1,y1, x2,y2, …) is the piecewise-linear map through the given points. Single letters such as r, c, a, k become parameters with sliders; their boxes accept fractions like -29/16, which stay exact over ℤ and ℚ.

Fine print

On ℝ and ℂ everything is floating point. Roots are verified by their residual, discontinuities are detected numerically, and two cycles closer than about 10⁻⁸ are merged. Convergence of a sample orbit is declared when it comes within 10⁻¹⁰ of an attracting cycle, or when it repeats itself to 10⁻⁹ with some period up to max(N, 64); neutral cycles get a looser test, since orbits creep toward them. On ℤ and ℚ only the explicitly listed operations are exact; a formula with sqrt or sin over ℤ falls back to floating point and must land on integers.