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