Comments on Formalizing proof of existence of roots of functional equation
Parent
Formalizing proof of existence of roots of functional equation
Hey, codidact!
I've been solving for solutions to $f^n(x)=x$ where $f(x) = 4x(1-x)$ (the r=4 case of the logistic map, yes) and $f^n(x) = f(f^{n-1}(x))$ is defined recursively. Domain and range are both $[0,1]$.
I think I'm almost there - just need some logic to clear the (apparently) last hurdle.
Since $f^n(x)$ can arise from two different values of $f^{n-1}(x)$ (symmetrical about 0.5) I began to build a sort of reverse tree where I go backwards from $f^n(x)$ to $2^n$ possible values of $x$. This implies that for any $f^n(x) = k, 0 \lt k \lt 1$ there are $2^n$ distinct $x$ available to iterate on. (The $f^n(x) = 1, 0$ cases have some number of repeated roots, but that does not matter, as I am solving for equality to $x$, and 0 is a solution and I leave it at that)
I have this inkling of an idea: since there are infinite such $k$ I should be easily able to find $2^n$ values of $k$ such that $k$ is a part of ${\{x:f^n(x)=x}\}$. But this sort of reasoning seems highly inaccurate to me.
Is this even an acceptable conjecture? Is there any way I can formalize the proof along these lines?
I'd appreciate help with tags.
Post
All real roots are in $[0, 1)$.
If $x \le 0$ then $f(x) \le x$ with equality only at $x = 0$. By induction, for all $n \in \mathbb{N}$ and $x \le 0$ we have $f^n(x) \le x$ with equality only at $x = 0$.
If $x \ge 1$ then $f(x) \le 0$, so for all $n \in \mathbb{N}$ we have $f^n(x) \le 0 < x$.
Therefore by elimination all real roots of $f^n(x) - x$ are in the interval $[0, 1)$.
There are $2^n$ real roots for $n \ge 1$
Let $g_-(x) = \frac{1 - \sqrt{1 - x}}{2}$ and $g_+(x) = \frac{1 + \sqrt{1 - x}}{2}$. $g_-$ is a continuous bijection from $[0,1]$ to $[0, \tfrac12]$ and $g_+$ is a continuous bijection from $[0,1]$ to $[\tfrac12, 1]$. Both of them satisfy $f(g(x)) = x$.
Consider a function $h$ constructed by composing some sequence of length $n \ge 1$ where each element of the sequence is $g_-$ or $g_+$. Then $f^n(h(x)) = x$. Moreover, $h$ is a continuous bijection from $[0,1]$ to some closed interval $I_h \subset [0,1]$ which depends on the sequence used to construct it. $h(0) \ge 0$ and $h(1) \le 1$, so by Bolzano's theorem† there is a fixpoint $x_h$ for which $h(x_h) = x_h$. Therefore $f^n(h(x_h)) = f^n(x_h)$, whence $f^n(x_h) = x_h$.
Finally, we note that each choice of sequence gives a different interval for the domain of $h$, and therefore for the corresponding fixpoint $x_h$. The intervals aren't quite disjoint: to complete the proof it's necessary to deal with the special case $g_-(1) = g_+(1)$, but since we've already noted that $1$ isn't a root I will hand-wave that away.
There are $2^n$ choices of sequences, so at least $2^n$ real roots in $[0, 1)$; but since $f^n(x) - x$ is a polynomial of degree $2^n$ it cannot have more than $2^n$ roots.
The key point which I think you were missing is the relevance of continuity.
† To be precise, we need to case split on equality vs inequality and apply Bolzano's theorem in the case with no equality.
1 comment thread