Fixed Points, Part 3: Attraction and Orders

Plautus

And sometimes a fixed behavior is really a fixed point. Are there other simple classes?

If a fixed point X of f is equal, for some x, to

x : x : x : …

we say it is a fixed behavior of order 1. More, generally, if X is equal to

x₁ : … : xₙ : x₁ : … : xₙ : …

we say it is a fixed behavior of order n. We also call each of x₁, …, xₙ fixed point of order n. If fⁿ represents the n-fold composition of f, then the fixed points of order n are just the fixed points (of order 1) of fⁿ.

Gaiane

So you see, the generalization to fixed behaviors allows us to talk about fixed points of f, f², and so on, all at once.

Plautus

What about f⁰?

Gaiane

That’d be the identity, right? Everything is a fixed point of the identity.

Plautus

Oh, right. So, wait: are there any fixed behaviors that aren’t just the fixed points of some fⁿ?

Gaiane

Yes, there are.

Not all fixed behaviors have a finite order. Consider the successor function on ℕ; it has one fixed behavior,

0 : 1 : 2 : …

yet no value in this sequence repeats, so it does not have a finite order. There is no k such that incrementing by k has a fixed point.

Plautus

We defined behaviors to be equal if they have an equal suffix. Why not just say, when one is a suffix of the other?

Gaiane

Because multiple inputs might lead to the same behavior.

Plautus

Hmm. So multiple starting points converge to the same result?

Gaiane

Yes, though we usually say the fixed behavior attracts the inputs.

Plautus

Because we want to focus on the behavior?

Gaiane

Something like that.

Given an input x₀, we write 〈x₀〉 for the behavior

x₀ : f x₀ : f² x₀ : f³ x₀ : …

Given a behavior X, we say the attraction basin of X is the set of all inputs x₀ such that 〈x₀〉 = X.

Plautus

So because of how we’ve defined equality, these are all inputs that converge—sorry, attract—to the same behavior?

Gaiane

Are attracted to. Yes. We defined equality in the way we did so that it would be an equivalence relation.

Plautus

Ah, and the attraction basins are the equivalence classes.

Gaiane

Right.

Plautus

So we could have instead defined behaviors as…

This suggests an alternative definition of a behavior. We say that two points x and y attract if fᵃ x = fᵇ y for some a and b; then we identify a behavior with an equivalence class of inputs.

Gaiane

Hold on, why is this equivalent?

Plautus

The condition fᵃ x = fᵇ y is just the condition 〈x〉 = 〈y〉; and each behavior X is just 〈X₀〉, so each behavior expands into some equivalence class of inputs.

Gaiane

Ok, I’ll believe you. But I like the original definition more.

Plautus

Why? For example, this one explicitly mentions points, and we are looking for fixed points, after all.

Gaiane

Well, this definition of a behavior as an equivalence class is sort-of non-constructive. I like that I can think of a behavior as a sequence of values.

Plautus

On the plus side, my definition makes the whole definition of “attraction basin” irrelevant, since a behavior is its attraction basin.

Gaiane

Perhaps. But I like the “basin” terminology. It reminds me to think of attraction basins geometrically.

For f : α → α, the set of attraction basins of fixed behaviors of f partitions α. We can imagine coloring each basin a different color; then the way α is colored tells us something about the behavior of f.

If all fixed behaviors of a function f are equal, we say that f has a super-attractive fixed point.

Plautus

Sure, attraction basins tell us something about the function, maybe.

Gaiane

Maybe?

Plautus

Well, anyway, I think they’re more interesting in describing the fixed point itself. For example, if f has a super-attractive fixed point, I imagine f to “pull” uniformly in one direction.