 ## By Pavel Panchekha

### 06 January 2014

Share under CC-BY-SA.

# Fixed Points, Part 3: Attraction and Orders

###### Series

This is post 3 of the Fixed Points series.

A fixed point of a function is an input the function maps to itself. When we study the fixed points of a function, we can learn many interesting things about the function itself. This third of four parts talks about attraction basins and the order of a fixed point.

## What types of fixed points are there?

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.

## What starting points yield which fixed behaviors?

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.