# Fixed Points, Part 4: Stability

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 last of four parts talks about the stability of fixed points.

## Classifying fixed points

- Gaiane
- You said that attraction basins are more interesting in their ability to describe their fixed point.
- Plautus
- Yes.
- Gaiane
- What do you mean?
- Plautus
- I don’t know about you, but when I hear about a mathematical object, my first instinct is to classify it.
- Gaiane
- You want to classify fixed points?
- Plautus
- Sure. We already know a bit…

Given a function `f : X → X`

, its set of fixed points is `X`

modulo attraction in `f`

. We’ll write `Fixed(f)`

for the set of fixed points of `f`

.

- Gaiane
- What do you mean by attraction in
`f`

? - Plautus
- I had this definition for
`x`

and`y`

*attracting*if`fᵃ x = fᵇ y`

. I’m saying attraction in`f`

to make the dependence on`f`

clear. - Gaiane
- Oh, ok. Go on.

One important class of fixed points is the set of fixed points of a certain degree. We’ll write `Fixedⁿ(f)`

for these.

- Gaiane
- Right, but these aren’t all of them.
- Plautus
- Yep.
- Gaiane
- Like the fixed point of the successor function on natural numbers.
- Plautus
- Well, that’s actually just because we’re not considering enough numbers.
- Gaiane
- What?!

Define `ω+1`

to be the set of natural numbers, together with a new element we call `ω`

. We then extend the definition of behavior to allow transfinite induction on the length of the chain. Then we find that the successor function, extended to have the value `ω`

on input `ω`

, has as a degree-1 fixed point at `ω`

.

- Gaiane
- What just happened?
- Plautus
- Uhh… I’m not sure.
- Gaiane
- So you didn’t follow that?
- Plautus
- No. I don’t know where those words came from, either. It wasn’t me.
- Gaiane
- What I got out of it is that the successor function
*secretly*has a degree-1 fixed point. - Plautus
- I think it had something to do with the successor function always increasing its input by a fixed amount.
- Gaiane
- Oh, maybe all fixed points are fixed-degree fixed points? (Some secretly?)
- Plautus
- “All types” is a bit intimidating. Let’s start with very simple domains.

## Fixed points on finite domains

Let `X`

have exactly `n`

elements, and let `f`

be an arbitrary function `X → X`

. We claim that any fixed point of `f`

has finite degree.

- Gaiane
- Why’s this true?
- Plautus
- I’m not sure, but my intuition tells me that on a finite domain, all
`f`

can do is swap some elements around. - Gaiane
- Well, it can also map some elements to other elements.
- Plautus
- Actually, we can eliminate that.

First, we turn `f`

into a permutation, by inventing `X’`

, which is `X`

but equating elements `x`

and `y`

if `f x = f y`

. Then we have an `f’ : X’ → X’`

, because `f`

is well-defined on equivalence classes in `X’`

. Furthermore, `f’`

is a permutation since it maps distinct inputs to distinct outputs by definition.

- Gaiane
- Ah, but a fixed behavior of
`f`

has degree`n`

when all the points it cycles through are fixed points of`fⁿ`

. - Plautus
- And if
`f`

is a permutation on`X’`

…

Now, we can see the set of permutations on `X’`

as a group, and since `X’`

is finite, this group is also finite. Thus it has finite order. So there is some `k`

such that `(f’)ᵏ`

is the identity of which all points have degree 1.

- Gaiane
- Not really how I thought of putting it, but sure.
- Plautus
- What would you do?
- Gaiane
- I’d just construct the order explicitly.

Since `X`

had exactly `n`

elements, `X’`

has at most `n`

elements. So there are at most `n!`

permutations on it. So `(f’)^(n!)`

must be the identity. Thus `f`

has a degree dividing `n!`

.

- Plautus
- Ok. In any case, it has fixed degree.
- Gaiane
- Well, we should move on to the natural numbers next. They’re the simplest infinite set.

## Fixed behaviors in the integers

- Plautus
- I’m still a bit confused about the whole “fixed behavior of the successor function” business.
- Gaiane
- How about we ignore that for now, and characterize fixed points as “fixed degree or increase arbitrarily”.
- Plautus
- Are those the only two options?
- Gaiane
- I think so.

A function `f : ℕ → ℕ`

*diverges* on an input `x`

if `fⁿ(x)`

can be arbitrarily large (for arbitrarily large `x`

).

- Plautus
- What do you mean, can be arbitrarily large?
- Gaiane
- The formal definition is a
`lim sup`

; basically, for any threshold value`T`

, there’s some`n`

so that`fⁿ(x) > T`

. - Plautus
- Ok. Is there a difference between that and
`lim inf`

, where there’s some`n`

such that`fⁿ⁺ᵏ(x) > T`

for all`k`

? - Gaiane
- No, consider

If `lim sup fⁿ(x) → ∞`

, then `lim inf fⁿ(x) → ∞`

. For suppose not, and instead `lim inf fⁿ(x) = T`

. Then for any `n`

, there is a larger `m`

such that `fᵐ(x) ≤ T`

.

Let’s write out a sequence of such `m`

. First we have the `m`

for `n = 0`

, which we’ll call `m₀`

. Then we have the `m`

for `n = m₀ + 1`

, which we’ll call `m₁`

(note that `m₁ > m₀`

). Next, we have the `m`

for `n = m₁ + 1`

, which we call `m₂`

and for which `m₂ > m₁ > m₀`

. Continuing in this manner, we find a

m₀ < m₁ < m₂ < m₃ < ...

We can write `(f^mᵢ)(x)`

as `aᵢ`

, so we have a sequence

a₀ , a₁ , a₂ , a₃ , ...

which are all less than `T`

.

But since there are a finite number of elements less than `T`

, some of the `aᵢ`

terms must have the same value. And if `aᵢ = aⱼ`

, then `(f^mᵢ)(x) = (f^mⱼ)(x)`

, so `(f^(mᵢ + k))(x) = (f^(mⱼ + k))(x)`

, so that `f`

has degree `mⱼ - mᵢ`

.

But then `fⁿ(x)`

takes on only finitely many values (at most `mᵢ + (mⱼ - mᵢ) = mⱼ`

), and thus we cannot have `lim sup fⁿ(x) → ∞`

. This is a contradiction.

- Plautus
- You thought of all that?
- Gaiane
- The proof really obscures the intuition here.

Basically, the point is that if `fⁿ(x)`

has arbitrarily large terms, it can’t have finite degree because then it would only take on finitely many values (which would thus not be arbitrarily large).

But then `fⁿ(x)`

can never repeat terms (once it repeats a term, it is stuck in a cycle, since every term is decided only by the previous term). And if `fⁿ(x)`

can not repeat terms, it eventually “uses up” all of the small ones.

- Plautus
- That makes a bit more sense now.
- Gaiane
- Also, the proof shows that if function does not diverge, must have a fixed degree and vice versa.
- Plautus
- How?
- Gaiane
- By the same intuition…

In general, if a function does not diverge, then `lim sup fⁿ(x) = T`

. Then after at most `T`

terms, `fⁿ(x)`

must repeat an output, and so begins a cycle. So `fⁿ`

has degree at most `T`

.

On the other hand, if `f`

has a fixed degree, it cannot diverge since it only cycles through a finite set of values.

- Plautus
- Wait, so you’ve proven the theorem we wanted: either a function diverges, or it has a fixed degree.
- Gaiane
- Looks like I did!
- Plautus
- I notice that your proof made use of a reasoning by contradiction. What about the same theorem in constructive logic?
- Gaiane
- I don’t know. I’m not too familiar with constructive logic, but it’d be interesting to formulate this theorem in Coq.
- Plautus
- Not to me. Anyway, so it sounds like we’ve got functions on the naturals all figured out.
- Gaiane
- I wouldn’t say that. Here’s an open problem a friend told me about.

Consider the function

f(n) = if (even? n) then (n / 2) else (3 * n + 1)

Clearly it has a fixed point at `0`

of degree 1, and it also has a fixed-point of degree 3, which is `1 : 4 : 2 : 1 : ...`

. Are there any other fixed points?

- Gaiane
- Apparently this is a very hard problem, to the point that Paul Erdős said, “Mathematics is not yet ripe for such problems.”
- Plautus
- Huh. Weird. So it might have another fixed point of some large degree somewhere, or it might diverge.
- Gaiane
- Yeah. Mathematicians have even proven bounds on the degree; it can’t be smaller than 136, for example.
- Plautus
- Weird!
- Gaiane
- The point is, though we know all functions on the naturals diverge or have finite-degree fixed points, we don’t necessarily know which fixed points are which.
- Plautus
- Still, that’s cool. We should move on to continuous spaces next, right?
- Gaiane
- Maybe some other time. It’s late, and I ought to go to sleep. See you again soon.