Fixed Points, Part 4: Stability

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.

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.

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.