\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{Continuous Fractional Composites 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-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 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-composite 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-composite, we can view these functions as actions on a collection
of abstract points.  Finding half-composites 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-composites.  It uses a geometric technique that uses the topology
of the line.

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.

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.

\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{5in}
\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{2in}
\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.

\begin{theorem}
If $(x,y)$ is in the upper region in the node interval $I$, then
$(g(x),g(y))$ is in the upper region in $I$.  If it is defined,
$(g^{-1}(x),g^{-1}(y))$ is in the upper region in $I$.
\label{thm:gnode}
\end{theorem}
\begin{proof}
Since $(x,y)$ is in the upper region in $I$, $y>x$ 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 $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 fixed point.  Since a
cross solution is monotonically decreasing, pick a y value a little
above the fixed 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
fixed 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)$).

It turns out the crucial property is whether, on the node intervals
immediately surrounding the fixed point, the graph of $y=g(x)$ is on
the same side of the graph of $y=x$, or not.

More generally, the graph of $y=g(x)$ 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, and prove it.

\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 fixed
points of $g$ to fixed points of $g$.  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 fixed points of $g$ to fixed
points of $g$.  This means that if $(a,b)$ is a node interval,
$f((a,b))$ contains no fixed points of $g$.  Furthermore, sup and inf
of $f((a,b))$ are $f(a)$ and $f(b)$ (not necessarily in that order),
both of which are fixed 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{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{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.  Applying the same argument to
$I^{\ast}$, and taking the contrapositive, we get: 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.  It is the identity map for middle solutions, and
for cross solutions, it maps the node intervals on either side
of the fixed point of $f$ to each other.  In order to develop this bijection,
we need an order relation on the set of node intervals.

\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{theorem}
The relation $<$ on the set of node intervals is an order relation.
\end{theorem}
\begin{proof}
The antisymmetry and transitive rules are clear from our definition.  The only
rule we need to check is trichotomy.

If $I$ and $J$ are two distinct node intervals, they are disjoint.  Since
they are intervals, if $a\not\in J$ is less than $b$ for some $b\in J$, then
$a<I$.  Likewise, if $a\not\in J$ is greater than $b$ for some $b\in J$, then
$a>I$.  If $a\in I$ and $b\in J$, and $a<b$, then $a<J$, so $a<\inf J$.
Since $a\in I$, $I<\inf J$, so $I<J$.  If $a>b$, then we reverse the
roles of $a$, $b$, $I$, and $J$, and we have $J<I$.

By our definition, we cannot have both $I<J$ and $J<I$.  Neither can we have
$I<I$.
\end{proof}

\begin{lemma}
If $I$ is a node interval for a cross solution $f$, and $a$ is the
fixed point of $f$, 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 fixed
point of $g$, $a \not \in I^\ast$, so $a<y$ for all $y \in I^\ast$.
\end{proof}

\begin{lemma}
If $I$ and $J$ are node intervals 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\in S : I<a\}$, and $R = \{I\in S :
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, 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$ is a node interval, and $a\in I$, choose any $b$ outside the
open interval from $a$ to $g(a)$.  Let $f$ be the full interpolation
of $(a,b)$ and $(g(a),g(b))$.  Then $f:I\cup I^\ast\rightarrow I\cup
I^\ast$ and $f\circ f=g$.  Furthermore, if $h$ is any continuous
monotonically decreasing function from $I\cup I^\ast$ onto $I\cup
I^\ast$ such that $h\circ h=g$, $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 $I^\ast$.  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
$I^\ast$.  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 I^\ast$.

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 I^\ast$.

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 I^\ast$ onto $I\cup I^\ast$ 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}
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,
there exists a cross solution for which $F$ maps node intervals onto
their conjugates.
\end{corollary}

\begin{proof}
For each pair of node intervals $\{I,F(I)\}$, we use the above theorem to
generate a decreasing half-composite.  The cross solution is obtained by
the pasting lemma.
\end{proof}

\section{Conclusion}

What do we have?  We know the set of continuous half-composites of any
monotonic function.  Or at least we can construct a general element of the
set.  Although we only demonstrated requiring differentiability for
the case of $e^x$, the method is general.  In fact, we can require
arbitrarily high finite numbers of derivatives in our solutions.
We might, in principle, be able to require infinite differentiability
if we can write all the criteria in a finite format.

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 can also
discuss how this might be generalized for an arbitrary function from
any topological space $X$ to itself.

\end{document}
