## By Pavel Panchekha

### 06 January 2014

Share under CC-BY-SA.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation.

# Fixed Points, Part 3: Attraction and Orders

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.

Part 1: What is a fixed point?
Introduces and rigorously defines fixed points. Fixed points are inputs of a function that map to themselves. Knowing the fixed points of a function tells one a lot about that function and how it behaves.
Part 2: Fixed behaviors
Generalizes a fixed point into a fixed behavior. Every function has a fixed behavior, so behaviors are a better starting point if we want to use fixed points to learn more about functions.
Part 4: Stability
An attractive fixed point is easy to find because many inputs lead to it. This means that if you meant to start with a particular input, but messed up and started with a slightly-incorrect input, you’ll still probably end up with the same output. This captures a “stability” that attractive fixed points. Stability is useful for understanding systems design.

## 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.