\documentstyle{siam}
%\newenvironment{proof}{Proof: }{\\Q.E.D.\\}
\newtheorem{problem}{Problem}
%\newtheorem{theorem}{Theorem}[chapter]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}{Conjecture}[section]
\newtheorem{definition}{Definition}[section]
\begin{document}
\title{Fractional Composition of Functions}
\author{Kevin Iga}
\date{December 16, 1990}
\maketitle

\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-composite'' operator on
some functions?  Can we make a definition that will preserve
continuity, differentiability, or analyticity?  Can we find {\em all}
functions that satisfy the above requirements?  Can we define a
``one-third composite'' operator, and so forth; or, more genererally,
define a continuous family of fractional composite operators?

Although these are natural questions, they are, for most functions,
difficult questions, and there seems to be nothing, or perhaps very
little, written on the subject.  I am not aware of any direct
applications of the theory of fractional composites, 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.  There is some work
on similar functional equations, which are listed in the appendix.

We will begin by finding all continuous half-composites 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.

We may then ask if we can find a one-third composite, or, more
generally, a one-parameter group of functions $g^u(x)$ so that
$g^u\circ g^v(x)=g^{u+v}(x)$ and $g^1(x)=g(x)$, taking simple examples
and applying the same methods to related functions.  We will then
discuss how this might be generalized for an arbitrary function from
any topological space $X$ to itself.

\section{First Example: $f(f(x))=e^x$}

To give an introduction to the main methods used in this paper, we
will solve 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 composites.

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{2in}
\special{psfile=/mit/mosquito/Phasetwo/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 $0<f(0)<1$.
\end{lemma}

\begin{proof}
First, $f(0)$ cannot be 0 or 1 since $f(x)\not=x$ and $f(x)\not=e^x$
for all x.

Suppose $f(0)=a>1$.  Then the sequence proceeds as follows:
$(0,a),(a,1),\ldots$.  Now if $a>1$, then $0<a$, so the first point lies above
the line $y=x$, but $a>1$, 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 $0<a<1$.  Let $f_1(x)$ be any continuous monotonically
increasing function from $[0,a]$ onto $[a,1]$.  This means, of course,
that $f_1(0)=a$ and $f_1(a)=1$.

Let $T$ be a function that carries $(x,y)$ to $(y,e^x)$ and let $T^{-1}$
be the reverse map carrying $(x,y)$ to $(\ln y, x)$ if $y>0$.

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-composition 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-composites 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=/mit/mosquito/Phasetwo/half.plot}
\caption{A continuous half-composite 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-composites 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.  If we assume $f(x)$ is analytic,
we can then 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-composite 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.

\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-composition, 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-composites, I will go on to work with functions that {\em do}
have half-composites.  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, y<x, y<g(x)\}$ is called the {\bf lower region}
on $I$, and the interior of the remaining region in $I\times\Re$ is
called the {\bf middle region} on $I$.
\end{definition}

Essentially, the fixed points separate the domain into node intervals, as in
figure~\ref{nodeint}

\begin{figure} \label{nodeint}
\vspace{5in}
\special{psfile=nodeint.ps}
\caption{Node intervals and fixed points}
\end{figure}

\subsection{Monotonically increasing functions}

We will now restrict our field of interest to monotonically increasing
functions, because they are similar enough to $y=e^x$ to be dealt
with in a similar fashion, and are slightly more complicated in that they
may cross the line $y=x$ any number of times.

\begin{theorem}
If $g$ is monotonic, then on a node interval, the graph of $y=f(x)$
intersects neither the graph of $y=x$ nor the graph of $y=g(x)$.
\end{theorem}

\begin{proof}
Let $I$ be a node interval, and $a \in I$.  Since $I$ is a node
interval, $g(a)\not=a$.  If $f(a)=a$, then $g(a)=a$ by
lemma~\ref{fxfix}.  If $f(a)=g(a)$, then $g(g(a))=g(a)$ by
lemma~\ref{fgfix}.  Since $g$ is one-to-one, $g(a)=a$.
\end{proof}

Between any two fixed points of $g$, then, $f(x)$ can be ``above'' both of
the graphs $y=x$ and $y=g(x)$, ``between'' the graphs, or ``below'' both
graphs.  These three cases, it turns out, are very different.

\begin{definition}
If $f(f(x))=g(x)$, and in a node interval, $f(x)>x$ and $f(x)>g(x)$,
then $f(x)$ is said to be an {\bf upper solution} in the interval.
Likewise, if $f(x)<x$ and $f(x)<g(x)$, then $f(x)$ is said to be a
{\bf lower solution} in the interval.  Otherwise, $f(x)$ is a {\bf
middle solution} in the interval.
\end{definition}

We still want the concept of the forward and reverse sequences, so we
redefine them here.

\begin{definition}
The successor of $(x,y)$ in the forward sequence is $(y,g(x))$, and if
$y$ is in the image of $g$, the successor of $(x,y)$ in the reverse sequence
is $(g^{-1}(y),x)$; otherwise, it is undefined, and the sequence terminates.
\end{definition}

\begin{theorem}
If $(x,y)$ is in the middle region on the node interval $I$, then its
forward and reverse sequences lie entirely in the middle region on the
node interval $I$.
\end{theorem}
\begin{proof}
Suppose that in $I=(a,b)$, $g(x)>x$.  Then if $(x,y)$ is in the middle
region on I, $a<x<y<g(x)<g(b)=b$.  Since $g(x)$ is monotonically
increasing, $g(x)<g(y)$.  The next point in the sequence is $(y,g(x))$.
Since $a<y<b$ and $y<g(x)<g(y)$, the new point is in the middle region
on the node interval $I$.  By induction, the forward sequence lies
entirely in the middle region on the node interval $I$.

If $(x,y)$ is in the middle region on $I=(a,b)$, then $y$ is in the
image of $g$, since both $a$ and $b$ are in the image of $g$, and
$a<y<b$, and $g$ is continuous.  Since $g$ is monotonically
increasing, if we take the long string of inequalities in the last
paragraph, and act on it by the inverse of $g$, we get
$a<g^{-1}(x)<g^{-1}(y)<x<b$.  Concatenating them gives us
$a<g^{-1}(x)<g^{-1}(y)<x<y<g(x)<b$.  The next point in the reverse
sequence, is $(g^{-1}(y),x)$.  We note that $a<g^{-1}(y)<b$, and
$g^{-1}(y)<x<y$, so the new point is in the middle region on the node
interval $I$.  By induction, the reverse sequence lies entirely in the
middle region on the node interval $I$.

If $I=(a,\infty)$, and $g(x)>x$, and $(x,y)$ is in the middle region on
I, $a<x<y<g(x)$.  The next point in the sequence is $(y,g(x))$.  Since
$a<y$ and $y<g(x)<g(y)$, the new point is in the middle region.

The argument for the reverse sequence is the same as before.

The other cases for $I$ include: $I=(-\infty,b)$, where the reverse
sequence may terminate, and $I=(-\infty,\infty)$, where $g(x)$ is a continuous
monotonically increasing function that does not intersect the line $y=x$,
which is a previously solved problem.

If $g(x)<x$ in $I=(a,b)$, and $(x,y)$ is in the middle region, then
$a=g(a)<g(y)<g(x)<y<x<g^{-1}(y)<b$, so the next point in the forward sequence,
$(y,g(x))$, and in the reverse sequence, $(g^{-1}(y),x)$, are in the
middle region again.  The other cases for I are similar.
\end{proof}

The reader is encouraged to supply the proofs for the cases not explicitly
delineated here.  What we have essentially shown is that if we have a middle
solution on a node interval, it does not interfere with the solutions on
the other node intervals.

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)$.
\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 $b<a$, then $g(b)>g(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(a)=b$, so at $b$, $g(b)<b$, so the graph of
$g(x)$ is below the line $y=x$ at $b$.  The graph of $g(x)$ is above
the line $y=x$ at $a$.  By the intermediate value theorem, $g(x)$
crosses the line $y=x$.

Case III:

If $b=a$, then $g(x)\not=x$ for some other $x$, since otherwise,
$g(x)$ would be identical to $x$, which is a monotonically increasing
function.  Choose this $x$ and apply case I or case II as appropriate.

Step 2:
Suppose $g(a)=a$ and $g(b)=b$, and $a<b$.  Then $g(a)=a<b=g(b)$ but
$g(a)>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 $x<y$ and $y>g(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 $y<g(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.
\end{proof}

\begin{definition}
If $g(x)$ is continuous and monotonically increasing, a continuous
function $f(x)$ such that $f(f(x))=g(x)$ is called a {\bf cross
solution} if it is not a middle solution.
\end{definition}

The results of this section are as follows: if $g(x)$ is continuous
and monotonically increasing, then there are two kinds of
half-composites: middle solutions and cross solutions.  Middle
solutions are monotonically increasing; cross solutions are
monotonically decreasing.  Middle solutions contain all fixed points of $g$;
cross solutions contain only one.  Middle solutions are always between
the graphs of $x$ and $g(x)$; cross solutions are never between those
graphs.

\subsubsection{Specific examples}

If $g(x)=x$, then it has exactly one middle solution continuous
half-composite $f(x)=x$.  All other continuous half-composites must be
cross solutions.  There are an infinite number of them: $f(x)=a-x$,
for any constant $a$, are some of them.  Any continuous function which
is its own inverse is a solution.  The reader may be tempted to recall
that the function $f(x)=-1/x$ is its own inverse; however, remember
we are only examining continuous solutions.

If $g(x)=x^9$, then note that $f(x)=x^3$ qualifies as a middle
solution, and $f(x)=-x^3$ is a cross solution.  More generally, if
$g(x)$ is a monotonically increasing odd function, and $f(x)$ is an
odd middle solution, then $-f(x)$ is an odd cross solution since
$-f(-f(x))=f(f(x))=g(x)$, and multiplying by $-1$ turns a
monotonically increasing function to a monotonically decreasing
function, and vice-versa.

\subsubsection{Properties of cross solutions}

Suppose $g(x)$ has fixed points.  We wish to find all cross solutions.
The reader should draw a graph with $g(x)$ and $y=x$, and pick a fixed
point of $g$ where a cross solution is expected to intersect $y=x$.
Pick an $x$ value a little to the left of the touching point.  Since a
cross solution is monotonically decreasing, pick a y value a little
above the touching point.  Start with this point and construct the
first few points in the forward sequence.

If your $g(x)$ ``crossed through'' the line $y=x$ at your chosen
touching point, you should see no immediate problem for the first few
points.  If your $g(x)$ ``bounced off'' the line $y=x$, you should end
up with $g(x)$ increasing (it actually approaches $(x,\infty)$).  To make
this concise, we make the following definitions:

\begin{definition}
An {\bf isolated touching point} is a touching point $(x,g(x))=(x,x)$
for which there exists a neighborhood around $x$ that contains no other
touching point values.  An {\bf accretion touching point} is a
touching point that is not isolated.
\end{definition}

\begin{definition}
A {\bf crossing point} $(x,g(x))$ is an isolated touching point where
every neigborhood of $x$ contains a point $a$ such that $g(a)>a$ and a
point $b$ such that $g(b)<b$.  A {\bf bouncing point} is an isolated
touching point that is not a crossing point.
\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))<f(x)$.
\end{lemma}

\begin{proof}
Consider the point $(x,f(x))$ on the graph of $f$.  Two points down the
forward sequence from this point is $(g(x),g(f(x)))$.  Since $f(x)$ is
a cross solution, $f(x)$ is monotonically decreasing.  This means the
gradient between these two points is negative.  Therefore, $g(x)>x$ if
and only if $g(f(x))<f(x)$.
\end{proof}

\begin{lemma}
\label{smearing}
If $(a,a)$ is a touching point, and $U$ is a neighborhood around $a$,
then for some $x \in U-{a}$, $f(x) \in U-{a}$.
\end{lemma}

\begin{proof}
The function $f$ maps $a$ to $a$, and is continuous at $a$.  This
means that for every neighborhood $U$ around $f(a)=a$, there is a
neighborhood $V$ around $a$ such that $f(V) \subset U$.  Choose any $x
\in (U-{a}) \cap V \subset U-{a}$.  Then $f(x)\in f(V) \subset U$.
Since $f$ is one-to-one, $f(x)\not= a$.
\end{proof}

\begin{theorem}
No cross solution passes through a bouncing point.
\end{theorem}

\begin{proof}
Suppose $f(x)$ is a cross solution for $g(x)$ that passes through a
bouncing point $(a,a)$.  Around $a$, there is a neighborhood $U$ which
contains no other touching point values.  Since $(a,a)$ is a bouncing
point, either $g(x)<x$ for all $x \in U-{a}$, or $g(x)>x$ for all $x
\in U-{a}$.  Without loss of generality, suppose $g(x)>x$ for all $x
\in U-{a}$.

By lemma~\ref{smearing}, there is an $x \in U-{a}$ such that $f(x)
\in U-{a}$.  By lemma~\ref{oddcross}, $g(x)>x$ if and only if
$g(f(x))<f(x)$.  Since we supposed $g(x)>x$, we must conclude
$g(f(x))<f(x)$.  But $f(x) \in U-{a}$, so $g(f(x))>f(x)$.  From this
contradiction we see that a cross solution cannot pass through a
bouncing point.
\end{proof}

In this theorem we see that the problem with a cross solution passing
through a bouncing point is really due to this fact: There is a node
interval on each side of the bouncing point in question, each of which
maps to the other by $f$.  For $f$ to be a cross solution, the graph
of $g$ passes above the line $y=x$ on one node interval and below the
line on the other.  It is this that prevents a cross solution from passing
through a bouncing point.

We can generalize this further: g must be on opposite sides of the
side of the line $y=x$ on node intervals that map to each other by $f$.
We will now try to make this precise.

\begin{theorem}
Given a node interval $(a,b)$, its image under $f$, that is, $f((a,b))$,
is a node interval.
\end{theorem}

\begin{proof}
If $g(a)=a$, then $g(f(a))=f(f(f(a)))=f(g(a))=f(a)$, so $f$ maps
touching points to touching points.  Suppose $g(f(a))=f(a)$.  Then
$f(a)=g(f(a))=f(f(f(a)))=f(g(a))$, and since $f$ is one-to-one,
$a=g(a)$.  This shows that $f^{-1}$ maps touching points to touching
points.  This means that if $(a,b)$ is a node interval, $f((a,b))$
contains no touching points.  Furthermore, sup and inf of $f((a,b))$ are
$f(a)$ and $f(b)$ (not necessarily in that order), both of which are
touching points.  Hence we have $f((a,b))$ is a node interval.
\end{proof}

\begin{definition}
If $I$ is a node interval, then the {\bf conjugate node interval} of
$I$ under $f$ is $f(I)$ and is written $I^{\ast}$.
\end{definition}

\begin{lemma}
$I^{\ast\ast}=I$
\end{lemma}
\begin{proof}
If $(a,b)$ is a node interval,
$(a,b)^{\ast\ast}=(f(f(a)),f(f(b)))=(g(a),g(b))=(a,b)$.
\end{proof}

\begin{corollary}
The half-composite $f$ defines a bijection between node intervals that is
its own inverse.
\end{corollary}

\begin{definition}
A node interval $I$ is said to be an {\bf increasing node interval} if
$g(x)>x$ 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{theorem}
Conjugate node intervals under a cross solution have odd parity.
\end{theorem}

\begin{proof}
Suppose $I$ is a node interval, and $x\in I$.  Suppose $I$ is an
increasing node interval.  Then $g(x)>x$ for all $x \in I$.  According
to lemma~\ref{oddcross}, $g(f(x))<f(x)$ for all $f(x) \in I^\ast$.
So $I^\ast$ is a decreasing node interval.  By symmetry, if $I$ is a
decreasing node interval, $I^\ast$ is an increasing node interval.
\end{proof}

The operation $I \rightarrow I^\ast$ is a bijection on the set of
node intervals, which is the identity for middle solutions, and
for cross solutions, it maps the node intervals on either side
of the fixed point of $f$ to each other.  From this fact, we see
that the cardinality of touching points on either side of the fixed
point of a cross solution is the same.  To formalize this, we make
the following definitions:

\begin{definition}
If $I$ and $J$ are node intervals, we say $a<I$ if $a<x$ for all $x \in I$,
and $J<b$ if $y<b$ for all $y \in J$, and $I<J$ if $x<y$ for all $x \in I$
and $y\in J$.
\end{definition}

\begin{lemma}
If $I$ is a node interval for a cross solution $f$, and $f(a)=a$, and
if $a<I$, then $a>I^\ast$.
\end{lemma}

\begin{proof}
Suppose $x \in I$.  Then $a<x$, so $a=f(a)>f(x)$, and $f(x) \in
I^\ast$.  Because $I^\ast$ is a node interval and a is a touching
point, $a \not \in I^\ast$, so $a<y$ for all $y \in I^\ast$.
\end{proof}

\begin{lemma}
If $I$ and $J$ are node interval for a cross solution, $I<J$ then
$J^\ast<I^\ast$.
\end{lemma}

\begin{proof}
If $x\in I$ and $y\in J$ and $x<y$, then $f(y)>f(x)$, so $J^\ast<I^\ast$.
\end{proof}

What these lemmas prove is:

\begin{theorem}
Let $S$ be the set of all node intervals for a cross solution $f$ with
a fixed point $a$.  Let $L = \{I : I<a\}$, and $R = \{I: I>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 node intervals, and reverses parity.
\end{theorem}

\begin{corollary}
$L$ and $R$ have the same cardinality.
\end{corollary}

\begin{corollary}
If $g$ has a finite number of touching points, then any cross solution must
pass through the middle touching point.  If $g$ has an even number of
touching points, then $g$ has no cross solutions.
\end{corollary}

\subsubsection{The solution}

We will now find all continuous half-composites for an arbitrary monotonically
increasing function, in a manner analogous to the way we found all continuous
half-composites for $y=e^x$.  We will start with any function of a particular
type, then form the iterated extension.  It will be evident that this always
yields a half-composite, and that all half-composites can be formed in this
way.  The difference is this: we will work by node intervals for middle
solutions and conjugate pairs of node intervals for cross solutions.

\begin{theorem}
If $I$ is a node interval, and $a\in I$, choose any $b$ between $a$
and $g(a)$.  Let $f_1$ be a continuous monotonically increasing
function either from $(a,b)$ to $(b,g(a))$ or from $(b,a)$ to
$(g(a),b)$ (whichever is non-empty).  Let $T$ be the function
$\Re^2\rightarrow\Re^2$ that maps $(x,y)$ to $(y,g(x))$.  Let $f(x)$
be the iterated $T$ extension of $f_1(x)$.  Then $f : I \rightarrow I$
and $f(f(x))=e^x$.  Furthermore, if $h$ is any continuous function $h:
I \rightarrow I$, then $h$ can be constructed in this way.
\end{theorem}

\end{document}
%intro: f(f(x)) = g(x)
%g(x) = e^x
%all f(x) continuous
%all f(x) differentiable, 2nd, etc.
%conjecture: only one if analytic?
%g(x) = monotonic fn. never crossing y=x
%g(x) = finite # crossings
%g(x) = finte # intersections (crossings, tangencies)
%g(x) = discrete intersections
%g(x) = not monotonic
%
%power series
%Return to conjecture: if f(x) intersects y=x, we can find c-infinity f.
%1/3 composites? rational composites?  real composites?
%
%special cases:
%g(x) = x+a
%x*a
%g(x) = mx+b (and other similar things gotten from trying the answer)
%x^a
%isomorphisms between arithmetics
%h-1(g(h(x))) methods
%g(x) = constant-- all solutions?  Continuous/differentiable?
%g(x) = x-- all solutions? Continuous/differentiable solutions?
%
%g(x) not over R but a subset?
%C-->C
%X-->X
