\documentstyle{siam}
\newtheorem{problem}{Problem}
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{definition}{Definition}[section]
\begin{document}
\title{Continuous Half-Iterates of Functions}
\author{Kevin Iga}
\date{December 16, 1990}
\maketitle
\begin{abstract}
This paper finds all continuous solutions to the functional equation
$f(f(x))=g(x)$, given a continuous monotonic function $g:\Re
\rightarrow \Re$. The method described here involves choosing a small
piece of the solution, and defining a sequence of functions based on
this initial piece. The sequence of pieces might not, in general,
agree on their overlap or cover the real line. By determining which
initial pieces generate sequences that agree on the overlap and cover
the real line, we determine all the continuous solutions. This method
can be generalized to find differentiable solutions.
\end{abstract}
\section{Introduction}
If $f$ is a function $f:\Re \rightarrow \Re$, we often wish to discuss
the function $f \circ f$, the composition of $f$ with itself, defined so
that $(f \circ f)(x) = f(f(x))$.
It is natural to ask if this definition is reversible, that is, if
$g(x)$ is a function, is there a function $f(x)$ such that $f \circ f
= g$? In other words, can we define a ``half-iterate'' operator on
some functions? Can we make a definition that will preserve
continuity, differentiability, or analyticity? Can we find {\em all}
functions that satisfy requirements like those listed above?
Although these are natural questions, they are, for most functions,
difficult. The question of finding a closed form expression
for the half-iterate has posed many difficulties to mathematicians
working on this problem in the past, and, I claim, has frustrated the
more general problem of finding a function, whether we have a closed
form expression for it or not.
If we discard the ambitious goal of arriving at an expression for a
half-iterate, we can view these functions as actions on a collection
of abstract points. Finding half-iterates in this case is a
combinatorial problem, which has received some attention\footnote{R.
Rice, When is $f(f(x))=az^2+bz+c$?, American Mathematical Monthly,
Vol. 87, \#4 (April 1980) 252-263\\R. Isaacs, Iterates of fractional
order, Canadian Journal of Mathematics, 2 (1950) 409-416}. But such
approaches disregard the topological structure of the real line, and
yield many solutions which are wildly discontinuous and are hard to
characterize.
This paper will address the problem of finding all continuous
half-iterates. It uses a geometric technique that uses the topology
of the line.
We will begin by finding all continuous half-iterates of a
particular function, $e^x$, thereby introducing the basic procedures
that will used again and again. We will then examine the consequences
of insisting on differentiability, or analyticity. We will then apply
this method to the class of continuous, real-valued, monotonic
functions, and find all continuous half-iterates.
I am not aware of any direct applications of the theory of fractional
iterates, but most of the people I have spoken to concerning this
have agreed that it is a natural extension to the theory of functional
equations and of iteration. Indeed, the theory of fractional {\em
differentiation} is well understood and is known to have many
applications.
\section{First Example: $f(f(x))=e^x$}
It is often easier to get an intuition for a general problem by
solving a specific problem. This sometimes gives us a concrete
picture without our having to burden ourselves with unnecessary
details. After we get an intuition for the specific problem, the
generalization is easier. In this case, we will start with the
following problem:
\begin{problem}
Find all continuous functions $f(x)$ such that $f(f(x)) = e^x$.
\end{problem}
\subsection{Necessary conditions}
First we note the following properties of the function $e^x$:
\begin{enumerate}
\item It is one-to-one,
\item it is continuous,
\item it is monotonically increasing, and
\item for no $x$ does $x = e^x$.
\end{enumerate}
As a result, $f(x)$ will have similar properties:
\begin{lemma}
If $f(x)$ is a continuous function so that $f(f(x))=e^x$, then
\begin{enumerate}
\item $f(x)$ is one-to-one,
\item $f(x)$ is monotonically increasing,
\item for no $x$ does $f(x) = x$, and
\item for no $x$ does $f(x) = e^x$.
\end{enumerate}
\end{lemma}
\begin{proof}
Part 1 is an easy set-theoretic result: if $f(x)=f(y)$, for $x\not=y$,
then $f(f(x))=f(f(y))$, but $f(f(x)) = e^x$, which is one-to-one.
We will return to part 2 after examining parts 3 and 4.
Part 3 can be argued in this way: if $f(x)=x$ for some $x$, then
$f(f(x))=f(x)=x$, but $f(f(x))=e^x \not= x$.
Similarly, if $f(x)=e^x$, then $f(f(x))=f(e^x)=f(f(f(x)))=e^{f(x)}$,
and $e^x=f(f(x))=e^{f(x)}$. Because of property 4 of $e^x$, $x=f(x)$,
which, by our previous argument, occurs for no $x$.
Part 2 is a result of the following observations: by hypothesis, $f(x)$
is continuous. $f(x)$ is one-to-one. $f(x)$ must then be either
monotonically increasing or monotonically decreasing. If $f(x)$ were
monotonically decreasing, it would intersect the function $y=x$,
which, by part 3, cannot happen.
\end{proof}
The following method will be used frequently in this paper. It is the
main tool for finding fractional iterates.
Suppose we know that $f(x)=y$. On the graph of $f(x)$, then, we know
one point, i.e. $(x,y)$. But we also know more: $f(f(x))=f(y)$, and
$f(f(x))=e^x$, so we also have the point $(y,e^x)$. We can thus
construct the following sequence of points, all on the graph of
$f(x)$:
\begin{tabular}{l}
$(x,y)$\\
$(y,e^x)$\\
$(e^x,e^y)$\\
$(e^y,e^{e^x})$\\
\vdots
\end{tabular}
We can also construct a reverse sequence:
\begin{tabular}{l}
$(x,y)$\\
$(\ln y,x)$\\
$(\ln x,\ln y)$\\
\vdots
\end{tabular}
We will now justify the existence of the reverse sequence. If $\ln y$
exists (i.e. if $y>0$), then $f(\ln y)$ can have no other value than $x$,
since $x$ will give $f(f(\ln y))=y$, as desired, and since $f(x)$ is
one-to-one. A similar argument works for the entire sequence until
after the y coordinate is negative. The reverse sequence, unlike the forward
sequence, terminates.
Graphically, we can draw the picture in Figure~\ref{sequence1}, where
we know the point $(x,y)$, and compute $(y,e^x)$ by drawing a
horizontal line from $(x,y)$ to the line $y=x$, and a vertical line
from $(x,y)$ to the curve $y=e^x$.
We then close the rectangle to find the next point, and iterate. We
can likewise draw the appropriate rectangle to compute the reverse
sequence.
\begin{figure}
\vspace{5in}
\special{psfile=sequen.plot}
\caption{Computing a sequence for some points in $f(x)$ \label{sequence1}}
\end{figure}
We can, of course, compute the sequence algebraically, or watch the
sequence geometrically; for brevity, we will usually use the algebraic
method; the reader is encouraged to construct the geometric analog to
aid his intuition.
\begin{lemma}
If $f(f(x))=e^x$, then $01$. Then the sequence proceeds as follows:
$(0,a),(a,1),\ldots$. Now if $a>1$, then $01$, so the second point lies below the line $y=x$.
By the intermediate value theorem, $f(x)=x$ for some $x$, which we have
already shown to be impossible.
Likewise, if $f(0)=a<0$, then $0>a$, so the first point lies below the line
$y=x$, and $a<1$, so the second point lies above the line $y=x$. By the
intermediate value theorem, $f(x)=x$ for some $x$, which we have already
shown to be impossible.
\end{proof}
\begin{corollary}
The graph of $f(x)$ lies between the graph of $x$ and the graph of
$e^x$.
\end{corollary}
The following list is a summary of the necessary conditions on a
continuous $f(x)$ so that $f(f(x))=e^x$:
\begin{enumerate}
\item $f(x)$ is continuous.
\item $f(x)$ is monotonically increasing.
\item The graph of $f(x)$ lies between the graph of $x$ and the graph
of $e^x$.
\item The sequence generated by any ordered pair $(x,f(x))$ lies
entirely in the graph of $f(x)$.
\end{enumerate}
\subsection{Proof of sufficiency}
With this in mind, we perform the following construction:
Let a be any number $00$.
Examine the image of $T$ restricted to the graph of $f_1(x)$, and call
it $C$. Note that since $T$ is one-to-one in the $x$ and $y$ coordinates
individually, no two distinct points in $C$ have the same $x$ value or $y$
value. Note that the set of $x$ coordinates in $C$ is $[a,e]$ and the set
of $y$ coordinates in $C$ is $[1,e^a]$. Note also that $(a,1)$ and
$(e,e^a)$ are in $C$. $C$ is therefore a graph of a continuous,
monotonically increasing function from $[a,e]$ onto $[1,e^a]$. Note
also that this lies between the graph of $x$ and the graph of $e^x$.
Let this function be denoted $f_2(x)$.
In the same way, the image of $T$ restricted to the graph of $f_i(x)$, a
monotonically increasing continuous function from $[b,c]$ onto
$[c,e^b]$, is a graph of a monotonically increasing continuous
function from $[c,e^b]$ onto $[e^b,e^c]$, which we can denote
$f_{i+1}(x)$. By recursive definition, we can define $f_i$ for all
integers i.
For exactly the same reasons, this will work for $T^{-1}$, with $f_0$
and $f_{-1}$, with one exception: $T^{-1}$ is only defined for $y>0$.
One way of resolving this is to eliminate the points with $y\leq0$.
So for successive iterations of $T^{-1}$, we have the following
domains:
\[x: [0,a],(\ln a,0],(-\infty,\ln a]\]
\[y: [a,1],(0,a],(\ln a,0]\]
Note that although we cannot extend the sequence any further, we do
not need to; we have domains for all $x<0$. Furthermore, if we
include the $f_i$ for positive $i$, we have a $f_i$ for every point $x$.
Furthermore, the $f_i$ agree at the intersections (the forward and
reverse sequences generated by $(0,a)$).
By the pasting lemma, we can define a function $f(x)$ by letting its
value be the (unique) value obtained by the appropriate $f_i$. In the
way we have defined $f(x)$, it should be clear that $f(x)$ satisfies the
conditions, $f(f(x))=e^x$, and $f(x)$ is continuous. Continuity is
obtained by the pasting lemma, and the half-iteration is obtained by
noting that the $f(x)$ is an invariant of the $T$ function, which is
defined to force the condition $f(f(x))=e^x$.
Note also that we have chosen the most general function that satisfies
the necessity conditions listed above. We have thus classified all
continuous half-iterates of $e^x$.
\begin{definition}
Let G be an injective function from $\Re^2$ to $\Re^2$. Let $G^{-1}$
be a function from a subset of $\Re^2$ to $\Re^2$ such that $G\circ
G^{-1}(x)=x$. Suppose $f_1(x)$ is a function from a subset of $\Re$
to $\Re$. Let $S_1$ be the graph of this function, and for every
$i>1$, let $S_i$ be the image of $G|S_{i-1}$. Furthermore, for every
$i<1$, let $S_i$ be the image of $G^{-1}|(S_{i+1}\cap
domain(G^{-1}))$. Let $S=\bigcup_{i=-\infty}^{\infty}S_i$. If the
closure of S, $Cl S$, is the graph of a function $f(x)$ defined on a
subset of $\Re$, then $f(x)$ is the {\bf iterated G extension} of
$f_1(x)$.
\end{definition}
\begin{theorem}
Let $a$ be a number in the open interval $(0,1)$. Let $f_1(x)$ be a continuous
monotonically increasing function from $[0,a]$ onto $[a,1]$. Let $T$ be
a function $\Re^2 \rightarrow \Re^2$ that maps $(x,y)$ to $(y,e^x)$.
Let $f$ be the iterated $T$ extension of $f_1(x)$. Then
$f(f(x))=e^x$. Furthermore, if $h$ is any continuous function such
that $h(h(x))=e^x$, then $h(x)$ can be constructed in this way.
\end{theorem}
\begin{figure}
\vspace{2in}
\special{psfile=half.plot}
\caption{A continuous half-iterate of $e^x$, generated from $f_1(x)=x+.5$
\label{halfgraph}}
\end{figure}
Figure~\ref{halfgraph} is a graph of one such function, using
$f_1(x) = x+.5$ and performing the above construction.
\subsection{Differentiability}
We have found all continuous half-iterates of $e^x$. The solution
set is quite large. We might ask if we can reduce
the size by demanding that $f(x)$ be differentiable.
Nothing changes in the procedure described in the previous section,
except that the original function $f_1(x)$ must be differentiable, and
that the derivatives at the endpoints of each domain must match.
To satisfy the second condition, we need:
\[ f_1'(1)=f_2'(1)=\left.\frac{d(e^x)}{dy}\right|_{x=0} = 1/f_1'(0)\]
\[ f_1'(0) f_1'(1) = 1\]
We do not need to add additional conditions for differentiability at
other endpoints, since $T$ is differentiable and will map
differentiable curves to differentiable curves.
\begin{theorem}
Let $a$ be a number in the interval $(0,1)$. Let $f_1(x)$ be a differentiable
monotonically increasing function from $[0,a]$ onto $[a,1]$ such that
$f_1'(0) f_1'(1)=1$. Let $T$ be a function $\Re^2 \rightarrow \Re^2$
that maps $(x,y)$ to $(y,e^x)$. Let $f$ be the iterated $T$ extension of
$f_1(x)$. Then $f(f(x))=e^x$. Furthermore, if $h$ is any
differentiable function such that $h(h(x))=e^x$, then $h(x)$ can be
constructed in this way.
\end{theorem}
The reader is encouraged to work out a similar formula for
second-differentiability. For the third derivative, the work is
significantly messier. There seems to be no obvious general formula
for n-th differentiability.
Ultimately, it would be useful to find the restrictions necessary for
$f(x)$ to be infinitely differentiable. We have a great deal of freedom
in choosing the values for the derivatives at $0$, and this determines
the values for the derivatives at $1$, and assuming the existence of
a function with these derivatives at $0$ and a function with the
corrseponding derivatives at $1$, we can find an infinitely differentiable
function connecting the two functions which is one-to-one. There are
infinitely many such solutions, which can be generated by adding an
infinitely differentiable function of support in (0,1) small enough
to preserve the monotonicity of the function.
Requiring $f(x)$ to be analytic is quite a different matter. One way
of approaching this problem is to write $f(x)$ as a Taylor series.
Each of the differentiability conditions corresponds to a converging
sequence linear in each of the power series coefficients. The result
is like a system of linear equations, only with an infinite number of
equations, and an infinite number of unknowns. One might then suppose
whether the half-iterate is unique.
I don't currently have the answer to that, but I am following an
entirely different strategy based on fixed points in the complex
plane. It turns out if we expand $f$ into a power series around a
fixed point, all the summations turn out to be finite. Unfortunately,
$e^x$ has no fixed points in the real line. But it does have fixed
points in the complex plane. If we find the power series around such
a point, the hope is we can construct a function which, when
restricted to the reals, is still real. At first glance, this seems
unlikely, but there are other reasons to believe this is actually the
case.
\begin{conjecture}
There is a unique analytic function $f(x)$ such that $f(f(x))=e^x$.
\end{conjecture}
\section{Applying this method to related functions}
When we attacked the problem of finding continuous solutions to the
functional equation $f(f(x))=e^x$, we first proved theorems about the
nature of $f(x)$, then we showed that we had found all of them. In
this section, we will prove analogous theorems about finding continuous
solutions to the functional equation $f(f(x))=g(x)$, for any continuous
function $g(x)$, then we will prove more theorems for $g(x)$ with special
properties.
Note that in the previous example, the only properties of $e^x$ that
were used were:
\begin{enumerate}
\item $e^x$ is continuous.
\item $e^x$ is monotonically increasing.
\item The graph of $y=e^x$ does not intersect the graph of $y=x$.
\end{enumerate}
In fact, the argument does not change at all, except that the reverse
sequence need not terminate.
\begin{theorem}
Suppose $g(x)$ is a continuous, monotonically increasing function whose graph
does not intersect the graph of $y=x$. The following is a construction for
a function $f(x)$ such that $f(f(x))=g(x)$:
Let $a$ be a number in the open interval $(0,g(0))$. Let $f_1(x)$ be a continuous
monotonically increasing function from $[0,a]$ onto $[a,g(0)]$. Let $T$ be
a function $\Re^2 \rightarrow \Re^2$ that maps $(x,y)$ to $(y,g(x))$.
Let $f$ be the iterated $T$ extension of $f_1(x)$. Then
$f(f(x))=g(x)$. Furthermore, if h is any continuous function such
that $h(h(x))=g(x)$, then $h(x)$ can be constructed in this way.
\end{theorem}
First, to show we cannot apply this method to an arbitrary function,
note the following theorem:
\begin{theorem}
If $g(x)$ is a monotonically decreasing continuous function, then there is no
continuous $f(x)$ such that $f(f(x))=g(x)$.
\end{theorem}
\begin{proof}
Since $g(x)$ is monotonic, it is one-to-one. This implies that $f(x)$ is
one-to-one, and is therefore monotonic. If $f(x)$ is either
monotonically increasing or decreasing, $f(f(x))=g(x)$ will be
monotonically increasing, which contradicts the hypothesis that $g(x)$
be monotonically decreasing.
\end{proof}
Note also that if P is a property that is preserved by
self-iteration, like continuity or differentiability, then if we
wish to find functions $f(x)$ with property P, then $g(x)$ must have
property P, or we will have an empty solution set. It makes no sense,
therefore, to find all continuous functions $f(x)$ such that $f(f(x))$
is the step function.
Instead of going on with other kinds of functions without
half-iterates, I will go on to work with functions that {\em do}
have half-iterates. The approach will be analogous to that of
$e^x$, working with a general function $g(x)$ first, then restricting
$g(x)$ when necessary.
\begin{lemma}
$f(x)$ is one-to-one if and only if $g(x)$ is one-to-one.
\end{lemma}
\begin{proof}
If $g(x)$ is one-to-one, then suppose $x$ and $y$ are such that
$f(x)=f(y)$. Then $g(x)=f(f(x))=f(f(y))=g(y)$. Since $g(x)$ is
one-to-one, $x=y$. Therefore, $f(x)$ is one-to-one.
If $f(x)$ is one-to-one. Suppose $x$ and $y$ are such that $g(x)=g(y)$.
Then $f(f(x))=f(f(y))$. Since $f(x)$ is one-to-one, $f(x)=f(y)$ and
$x=y$. Therefore, $g(x)$ is one-to-one.
\end{proof}
\begin{lemma}
If $f(a)=a$, then $g(a)=a$. \label{fxfix}
\end{lemma}
\begin{proof}
$g(a)=f(f(a))=f(a)=a$.
\end{proof}
\begin{lemma}
If $f(a)=g(a)$, then $g(a)=g(g(a))$. \label{fgfix}
\end{lemma}
\begin{proof}
$g(a)=f(f(a))=f(g(a))=f(f(f(a)))=g(f(a))=g(g(a)).$
\end{proof}
As these lemmas show, points where $g(x)=x$ are important.
\begin{definition}
A {\bf fixed point of $g$} is a real number $x$ where $x=g(x)$. We
will also use the term {\bf fixed point} to refer to the point
$(x,x)=(x,g(x))$ on the graph of $g$, where $x$ is a fixed point of
$g$ The context should make it clear which is meant. A {\bf node
interval} is an open interval $I$ such that for all $x$ in $I$,
$x\not=g(x)$, and for all $x$ in $Bd(I)=Cl(I)-I$, the boundary of $I$,
$x=g(x)$. Given a node interval $I$, the subset of the plane
$\{(x,y)|x\in I, y>x, y>g(x)\}$ is called the {\bf upper region} on $I$,
the set $\{(x,y)|x\in I, yx$ and $f(x)>g(x)$,
then $f(x)$ is said to be an {\bf upper solution} in the interval.
Likewise, if $f(x)x$. Then if $(x,y)$ is in the middle
region on I, $ax$, and $(x,y)$ is in the middle region on
I, $ax$ and $y>g(x)$.
Since $g$ is increasing, it preserves order, so $g(y)>g(x)$ and
$g(y)>g(g(x))$. Since $g$ preserves order, and Bd $I$ consists of
fixed poits, $g(x)\in I$. Similarly, $g^{-1}(y)>g^{-1}(x)$ and
$g^{-1}(y)>x$, and $g^{-1}(x)\in I$.
\end{proof}
\begin{theorem}
If $(x,y)$ is in the lower region in the node interval $I$, then
$(g(x),g(y))$ is in the lower region in $I$. If it is defined,
$(g^{-1}(x),g^{-1}(y))$ is in the lower region in $I$.
\end{theorem}
The proof is not significantly different from the previous theorem.
We will now define an analog to $f_1(x)$ in the case of $e^x$.
\begin{definition}
Given a point $(x,y)$, and a point $(x',y')$ with $x'>x$, in either
the forward or the reverse sequence of the point $(x,y)$, such that in
the interval $(x,x')$ or $(x',x)$ (whichever is non-empty), there are
no points in either sequence, a {\bf partial interpolation} is a
continuous monotonic function from $[x,x']$ onto $[y,y']$. Let $T$ be
the function mapping $(x,y)$ to $(y,g(x))$. A {\bf full
interpolation} is the iterated $T$ extension of a partial
interpolation.
\end{definition}
\begin{theorem}
If $g(x)$ is a continuous monotonically increasing function, there is a
function $f(x)$ so that $f(f(x))=g(x)$, and for every node interval, $f(x)$
is a middle solution. (Such a function will simply be called a {\bf middle
solution}.)
\end{theorem}
\begin{proof}
For every node interval $I$, let $(x,y)$ be any point in the middle
region. Either the forward or the reverse sequence continually
increases. So there is a point $(x',y')$ so that $x'$ is the next
largest point in the sequence after $x$. Let $f_I$ be the full
interpolation. If $I=(a,b)$, $f_I$ is a continuous monotonically
increasing function from $(a,b)$ onto $(a,b)$. If $x$ is a fixed
point of $g$, let $f_x(x)=x$. This means that all $f_I$ and $f_x$
will agree at the endpoints. We apply the pasting lemma to obtain
$f(x)$. The domain covers the node interval, since if either sequence
were to approach a limit point $c$, then by continuity, $f(c)=c$, so
$c$ could not be in the node interval. It must then be on the boundary.
\end{proof}
Note that we were completely general in the above construction. We have
therefore constructed all middle solutions, as we did with $e^x$. We
have not, however, constructed all solutions that include and upper
lower pieces.
\begin{lemma}
A continuous monotonically decreasing function always crosses the line
$y=x$ exactly once.
\end{lemma}
\begin{proof}
Step 1:
If $g(x)$ is monotonically decreasing, let $b=g(a)$.
Case I:
If $bg(a)=b$, so at $b$, $g(b)>b$, so the graph of
$g(x)$ is above the line $y=x$ at $b$. The graph of $g(x)$ is below
the line $y=x$ at $a$. By the intermediate value theorem, $g(x)$
crosses the line $y=x$.
Case II:
If $b>a$, then $g(b)g(b)$ because $g(x)$ is monotonically decreasing, a
contradiction.
\end{proof}
\begin{theorem}
If $f(x)$, a continuous function, is not a middle solution of
$f(f(x))=g(x)$, where $g(x)$ is continuous and monotonically
increasing, then $f(x)$ is monotonically decreasing, and has exactly one
fixed point.
\end{theorem}
\begin{proof}
Suppose $(x,y)$ is in an upper region. The next point in the forward
sequence is $(y,g(x))$. Note that $xg(x)$; that is, it
decreases. Since $f(x)$ is monotonic, it is monotonically decreasing.
It therefore crosses the line $y=x$ in exactly one point.
Suppose $(x,y)$ is in a lower region. The next point in the forward
sequence is $(y,g(x))$. Note that $x>y$ and $yx$ for all $x \in I$, and a {\bf decreasing node interval}
otherwise. A pair of conjugate node intervals are said to have {\bf
odd parity} if one of them is increasing and the other decreasing.
Otherwise we say they have {\bf even parity}.
\end{definition}
\begin{lemma}
\label{oddcross}
If $f(x)$ is a cross solution for $g(x)$, then for all $x$, $g(x)>x$
if and only if $g(f(x))x$ if
and only if $g(f(x))x$ for all $x \in I$. According
to lemma~\ref{oddcross}, $g(f(x))I$. If $a\in I$ and $b\in J$, and
$a**b$, then we reverse the roles of $a$, $b$, $I$, and $J$,
and we have $J***I^\ast$.
\end{lemma}
\begin{proof}
Suppose $x \in I$. Then $af(x)$, and $f(x) \in
I^\ast$. Because $I^\ast$ is a partitioning interval and $a$ is a fixed
point of $g$, $a \not \in I^\ast$, so $af(x)$, so $J^\ast**a\}$. Then $F : S \rightarrow S$ defined by $I \mapsto I^\ast$, is
a bijection from $S$ onto $S$ that maps $L$ onto $R$ that reverses the
order relation $<$ for partitioning intervals, reverses parity, and sends
node intervals to node intervals and fixed point intervals to fixed point
intervals.
\end{theorem}
\begin{corollary}
$L$ and $R$ have the same cardinality.
\end{corollary}
\begin{corollary}
If $g$ has a finite, odd number of fixed points, then any cross solution must
pass through the middle fixed point. If $g$ has an even number of
fixed points, then $g$ has no cross solutions.
\end{corollary}
\begin{theorem}
If $I$ and $J$ are node intervals, and $a\in I$, choose any $b\in J$.
Let $f$ be the full interpolation of $(a,b)$ and $(g(a),g(b))$. Then
$f:I\cup J\rightarrow I\cup J$ and $f\circ f=g$. Furthermore if $h$ is
any continuous monotonically decreasing function from $I\cup J$ onto
$I\cup J$ such that $h\circ h = g$, then $h$ can be constructed in this way.
\end{theorem}
\begin{proof}
First, it's not hard to see that $f$ is well-defined. Every other
element in the sequence of generating the full interpolation is in
$I$; the others are in $J$. The points that must ``paste
together'' are the endpoints to the elements two apart from each other
on the forward and reverse sequences.
To see that the domain and range are as specified is slightly more
difficult. Let $x$ be in the interval $(a,g(a))$ or the interval
$(g(a),a)$, whichever is non-empty. Let $y=f(x)$. The even-numbered
elements in the forward and reverse sequence of $(x,y)$ are in $I$, by
theorem~\ref{thm:gnode}. The odd-numbered elements are therefore in
$J$. The forward and reverse sequences both must approach the
boundary, since if they reached a limit point $c$ in the node
interval, by continuity, $f(c)=c$, so $c$ could not be in the node
interval, and must therefore be on the boundary. So the domain of $f$
is $I\cup J$.
Since $f$ is continuous, as the $x$ component of either ``even''
sequence approaches Bd $I$, the $x$ component to the ``odd'' sequence,
and therefore, the $y$ component to the ``even'' sequence, approaches
Bd $I^\ast$. So the range of $f$ is $I\cup J$.
As before, the definition of the full interpolation ensures that $f\circ f=g$.
Furthermore, if $h$ is a continuous, monotonically decreasing function
from $I\cup J$ onto $I\cup J$ such that $h\circ h = g$,
and $a\in I$, then $g(a)\in I$ and $h$ is the full interpolation.
\end{proof}
\begin{corollary}
If the fixed points of $g$ contains no interval, then given a
bijection $F: S \rightarrow S$ (where $S$ is the set of node
intervals), that reverses the order relation $<$ on $S$, and reverses
parity, and does not fix any node interval, there exists a cross
solution for which $f$ maps node intervals onto their conjugates under
$F$.
\end{corollary}
\begin{proof}
For each pair of node intervals $\{I,F(I)\}$, we use the above theorem to
generate a decreasing half-iterate. The cross solution is obtained by
the pasting lemma.
\end{proof}
\begin{theorem}
If $I$ and $J$ are fixed point intervals with $I*