The Quadratic Map
In mathematics, a map is a recurrence relation, a formula for computing a value of a variable based on its own previous value(s). A quadratic map involves raising said previous value(s) to the power of two. Quadratic maps are an archetypal example of chaotic behavior arising from a very simple equation.
Consider the simple quadratic map 𝑓: 𝑥 → 𝑥² + 𝑐, also written as 𝑥ₙ₊₁ = 𝑥ₙ² + 𝑐. This takes some input 𝑥, squares it, and adds a constant value 𝑐. We can iterate the function by taking the output and feeding it back into the function, creating a sequence of numbers: 𝑥₀, 𝑥₁, 𝑥₂, 𝑥₃, 𝑥₄, and so on. The sequence we generate, known as the orbit of 𝑥, depends on our choice of starting value 𝑥₀ and our choice of the constant 𝑐. For most of this post we will use 𝑥₀ = 0 and look at what happens when we change 𝑐.
Let’s consider some different values of 𝑐 and see what happens. We’ll start with zero. When 𝑐 = 0, our function becomes simply 𝑥ₙ₊₁ = 𝑥ₙ². Starting with 𝑥₀ as zero, every iteration is zero because zero squared is zero, so we never move. We can say that with 𝑐 = 0, zero maps to itself in an orbit with a period of one.
What about one? When 𝑐 = 1, the first iteration of our function becomes 𝑥₁ = 0² + 1 = 1 (when 𝑥₀ = 0, the first iteration is always just 𝑐). The next iterations are
𝑥₂ = 1² + 1 = 2,
𝑥₃ = 2² + 1 = 5,
𝑥₄ = 5² + 1 = 26,
and so on. The value grows quickly, unbounded, racing off to infinity.
How about 𝑐 = −1? In this case, the next iterations are
𝑥₂ = (−1)² − 1 = 0,
𝑥₃ = 0² − 1 = −1,
𝑥₄ = (−1)² − 1 = 0,
𝑥₅ = 0² − 1 = −1,
and so on. The iterations bounce back and forth between negative one and zero forever. This is an orbit with a period of two.
What about 𝑐 = −2? In this case, the next iterations are
𝑥₂ = (−2)² − 2 = 2,
𝑥₃ = 2² − 2 = 2,
𝑥₄ = 2² − 2 = 2,
and so on. This is an orbit with a period of one, but our starting point isn’t part of the orbit, so we call negative two itself pre-periodic.
What about 𝑐 = −0.25? In this case, the next iterations are
𝑥₂ = (−0.25)² − 0.25 = −0.1875,
𝑥₃ = (−0.1875)² − 0.25 = −0.21484375,
𝑥₄ = (−0.21484375)² − 0.25 = −0.2038421630859375,
𝑥₅ = (−0.2038421630859375)² − 0.25 = −0.208448372548446…,
and so on. The value of 𝑥 oscillates around the value (1 − √2) / 2, approximately 0.2071, getting closer with each iteration. This is not a true periodic orbit, because the value never repeats. However, as we continue iterating, the orbit becomes arbitrarily close to a true periodic orbit, so we call this orbit asymptotically periodic with a period of one, and we call the value it approaches the attractor of the orbit.
What about 𝑐 = −1.5? In this case, the next iterations are
𝑥₂ = (−1.5)² − 1.5 = 0.75,
𝑥₃ = 0.75² − 1.5 = −0.9375,
𝑥₄ = (−0.9375)² − 1.5 = −0.62109375,
𝑥₅ = (−0.62109375)² − 1.5 = −1.1142425537109375,
and so on. It isn’t obvious what will happen next; the value jumps around unpredictably, sometimes positive and sometimes negative, sometimes closer to zero and sometimes farther. If we keep iterating, we can find iterations where the value comes arbitrarily close to the starting point, but it never converges to a periodic cycle. The orbit is chaotic.
How can we visualize this for more numbers? One way is to plot the function in the (𝑥, 𝑦) plane and draw a cobweb plot. To do this we draw the function 𝑦 = 𝑥² + 𝑐, a parabola shifted vertically by 𝑐 units. Next, we draw a vertical line from our starting point at the origin (because 𝑥₀ = 0) to our function (giving us 𝑥₁ = 𝑐). Then we draw a horizontal line from the function point over to the diagonal line 𝑦 = 𝑥, which represents taking the output as our next input. From there we draw a vertical line back to the function, and repeat. This cobweb plot reveals some interesting behavior as we vary the value of 𝑐.
When 𝑐 is greater than 0.25, the iterations grow bigger and bigger forever, unbounded. The closer 𝑐 gets to 0.25, however, the more the orbit bunches up near the value 0.5 before its eventual zoom off to infinity. At exactly 0.25 the behavior changes, and the orbit becomes bounded: it will get infinitely close to 0.5, but will never get bigger than that. Below 0.25, the orbit spirals towards an attractive fixed point. As 𝑐 continues to decrease, the iterations approach their fixed point slower and slower until −0.75, where the behavior changes again: beyond this point the iterations split apart and begin to converge on two attractive points, bouncing from one to the other. This repeats again as 𝑐 approaches −1.25, where the two attractive points split into four attractive points. The attractive points split into eight at about −1.37 and sixteen at about −1.39, and then the plot dissolves into chaos at about −1.40 — but note that the orbit stays bounded and does not escape to infinity. When the orbit is chaotic, the cobweb plot appears to have “filled in” areas, indicating an infinite amount of non-repeating values. In the chaotic region, small changes in the value of 𝑐 or 𝑥₀ lead to large changes in the orbit of 𝑥. As we continue decreasing 𝑐 the chaos continues, with brief flashes of stability, until 𝑐 reaches −2. When 𝑐 is exactly negative two, the orbit bounces to positive two and stays there; beyond negative two, the orbit blows up to infinity once more.
So that gives the range of real numbers that cause zero to remain bounded under the quadratic map: −2 ≤ 𝑐 ≤ 0.25. Any real number outside that range maps zero to infinity. Numbers within that range map zero to either a periodic cycle or a chaotic sequence.
What causes the attractive points to split? You might notice that the period-one attractive point happens to be an intersection of the parabola 𝑦 = 𝑥² + 𝑐 with the line 𝑦 = 𝑥. Intersection points are fixed points: if we started with 𝑥₀ at an intersection instead of at zero, we wouldn’t go anywhere under iteration. If we are near an intersection, but not exactly on the intersection, the behavior under iteration depends on the slope of the function at the intersection point: if the slope at a fixed point is between positive and negative 1, points near the fixed point will move closer to the fixed point under iteration, making it attractive or stable. If the slope is larger than positive or negative 1, points near the fixed point will move away from the fixed point, making it repulsive or unstable.
When 𝑐 < 0.25 there are two intersection/fixed points, but only one is ever an attractor. The fixed point in the upper right always has a slope greater than 1, so it is repulsive. The lower left fixed point has a slope smaller than 1, making it attractive, until 𝑐 = −0.75, where the slope is exactly −1. For 𝑐 < −0.75 that fixed point becomes repulsive, and we enter the period-two region.
But where do the two new attractive points come from? There are no new intersection points on our parabola. To find the new intersection points we need to iterate the function twice and plot 𝑓(𝑓(𝑥)), or 𝑓²(𝑥). (Note that 𝑓ⁿ(𝑥) means iterating the function 𝑛 times; the 𝑛 is not an exponent.) This gives us the function 𝑦 = (𝑥² + 𝑐)² + 𝑐, which expands into 𝑦 = 𝑥⁴ + 2 𝑐 𝑥² + 𝑐² + 𝑐.
We can see that the twice-iterated function twists in the middle, creating a new attractive intersection point on either side of the original point when 𝑐 < −0.75. The slopes at these new points start at positive 1 and decrease down to −1 as 𝑐 approaches −1.25, after which the slopes are bigger than 1 and the two points become repulsive.
If we plotted 𝑓⁴(𝑥), iterating the function four times, we would see even more twists as 𝑐 decreases, resulting in four stable intersection points for −1.368 ⪅ 𝑐 < −1.25, and so on.
What happens if we plot a graph with our value of 𝑐 on the horizontal axis and the corresponding final value of 𝑥 after many iterations through the quadratic map on the vertical axis? The result is a striking image known as a bifurcation diagram:
Here, we can see how the quadratic map stabilizes to a single value for values of 𝑐 between 0.25 and −0.75, then splits (or bifurcates) into two stable values for 𝑐 between −0.75 and −1.25, then four, then eight, then sixteen, over shorter and shorter intervals, until it dissolves into chaos around −1.4.
The chaotic region contains thin bands of stability, just as we saw with the cobweb plot. Each stable band starts with a base period, which doubles again and again before returning to chaos. The largest stable band within the chaos has a base period of three — the map jumps between three stable values, then six, then twelve, and so on. To the right of the period-three band is a narrower period-five band, and a bit farther over is a period-six band. A few even narrower bands are barely visible at this scale. It is possible to find bands of any period you want interspaced with the chaos.
In each period-doubling band, the ratio of the width of one periodic region to the next approaches a constant value of approximately 4.6692, known as the Feigenbaum constant after physicist Mitchell J. Feigenbaum. For example, the period-one region is 2 times the size of the period-two region, which is approximately 4.2337 times the size of the period-four region, which is approximately 4.5515 times the size of the period-eight region, which is approximately 4.6458 times the size of the period-sixteen region, and so on — each successive ratio is closer to the constant. If we look at the period-three band, the period-three region is approximately 2.1316 times the size of the period-six region, which is approximately 4.2812 times the size of the period-twelve region, which is approximately 4.5686 times the size of the period-twenty-four region, and so on. This constant in the period-doubling behavior appears in every one-dimensional quadratic map, not just the simple quadratic map we are looking at here.
The bifurcation diagram is a quasi-self-similar, or fractal, object; zooming in to any of the period-doubling regions reveals structures that look like distorted versions of the whole diagram. For example, here is an animated zoom into part of the period-three region around −1.77:
You might notice that the bottom edge of the chaotic region in the full diagram looks like a straight line, while the top edge looks like a parabolic curve. There are also lightly-shaded curves running through the inside of the chaotic regions, representing areas where points appear with higher densities. These are called critical curves. The first, the straight line, is simply 𝑦 = 𝑥, and all further curves are generated by repeatedly replacing the first 𝑥 term in the preceding curve with (𝑥² + 𝑥): we have the parabola 𝑦 = 𝑥² + 𝑥, then 𝑦 = (𝑥² + 𝑥)² + 𝑥, then 𝑦 = ((𝑥² + 𝑥)² + 𝑥)² + 𝑥, then 𝑦 = (((𝑥² + 𝑥)² + 𝑥)² + 𝑥)² + 𝑥, and so on. Continued to infinity, this set of curves slowly converges to the exact shapes of the stable curves of the bifurcation diagram.
Let’s look closer at those stable curves. They represent places where 𝑓ⁿ(𝑥) = 𝑥, where 𝑛 is the period of the stable region, the number of values that the orbit cycles between. The simplest case is the period-one curve, where 𝑛 = 1, which gives us 𝑥² + 𝑐 = 𝑥. We can subtract 𝑥 from both sides to get a standard quadratic equation, 𝑥² − 𝑥 + 𝑐 = 0. Next we can use the quadratic formula to find the solution: 𝑥 = (1 ± √(1 − 4𝑐)) / 2. Plotting this for 𝑐 on the horizontal axis and 𝑥 on the vertical axis gives us the fixed values of 𝑥 for any 𝑐. But hold on — the plus-or-minus sign implies that there are two fixed values, even though we’re looking at the period-one region. This goes back to the two intersections of our parabola with a straight line, as seen in the cobweb plot. Only one of the two fixed points has a stable, or attractive, region. The other fixed point is always unstable, or repulsive. The stable fixed point becomes unstable for 𝑐 less than −0.75, but it is still a fixed point: if we start with 𝑥₀ exactly on the fixed point, we will stay there, even if our value of 𝑐 puts us in a region with another stable period or in a region that is chaotic.
How about the curves in the period-two region? This corresponds to 𝑓²(𝑥) = 𝑥, or (𝑥² + 𝑐)² + 𝑐 = 𝑥, which expands into the quartic equation 𝑥⁴ + 2 𝑥² 𝑐 − 𝑥 + 𝑐 + 𝑐² = 0. We can factor that into two quadratic terms, (𝑥² − 𝑥 + 𝑐) (𝑥² + 𝑥 + 𝑐 + 1) = 0. Notice that the first term is the same as the period-one equation — this is because points that are fixed for one iteration will still be fixed after two iterations. We can solve the second term with the quadratic formula, just as before. That gives us 𝑥 = (−1 ± √(−3 − 4𝑐)) / 2. These two curves are both stable in a period-two cycle for values of 𝑐 between −0.75 and −1.25, hopping from one to the other, and unstable for all lower values of 𝑐.
Can we continue for higher periods? Period-three behavior corresponds to 𝑓³(𝑥) = 𝑥, or ((𝑥² + 𝑐)² + 𝑐)² + 𝑐 = 𝑥. This expands into a long and unpleasant equation of degree eight. Factoring out the period-one term again unfortunately does not help much, leaving us with an intractable equation of degree six which cannot be solved with closed-form expressions. The expanded period-four equation is even longer and messier, of degree sixteen, and while it can technically be solved after factoring out the period-one and period-two equations, the resulting expressions are too long to include here. All higher periods are impossible to solve with closed-form expressions. Unfortunately, only the period-one and period-two regions have fixed values with tidy expressions.
So far, we’ve only been talking about real numbers, but what happens if we try setting 𝑐 to a complex number? The answer to that question is our next topic: the Mandelbrot Set.