 ## By Pavel Panchekha

### 19 February 2014

Share under CC-BY-SA.

# Fixed Points, Part 4: Stability

###### Series

This is post 4 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 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.