From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: 'roots' of functions
Date: 30 Oct 1997 17:04:39 GMT
In article <634v48$fpc5@mx2.hrz.uni-essen.de>,
Urs Schreiber wrote:
> Im am looking for ways to determine 'roots' of functions, i.e. to
>find functions that are equal to a given function when iterated.
>
> The only approach I found so far involves Taylor-series development
>of such roots at a development point i that suffices f(i) = i.
...
> I am exspecially interested in roots of ln and exp.
So it's "roots" in the sense of "square roots" or "cube roots", not as in
"roots of a polynomial".
You need to specify just what your intended domain X is, and what kind of
function your interest is in (continuous, differentiable, piecewise-linear...).
Then you'll have a semigroup End(X) of functions f: X -> X of the
desired type, and your question is whether a given element g in this
semigroup is a power g = f^n for some n.
Actually it's a little easier in some cases than others; if your g is
already one-to-one and onto, you're asking about a _group_ Sym(X) of
permutations/homeomorphisms/diffeomorphisms/... These groups have been
the object of some serious study.
Let me illustrate what you can do if you're interested in square roots of
the exponential function.
Let's see, you want f(f(x))=exp(x) for all x, or f o f = exp.
Since exp is defined on all of R, I assume you want f to be, too.
Since exp is one-to-one, so must f be. Since exp maps onto (0, oo),
the image of f must be at least that large.
Now, shall we insist that f be at least continuous? Your suggestion of
power series and so on certainly implies you want that. Well, the
continuous image of an interval is an interval, so the image of f
is an interval of the form (a, oo) or [a, oo) for some a <= 0.
(The case im(f)=R is ruled out, since then the image of fof would be
all of R, too.)
We can rule out having im(f)=[a, oo) as well. A continuous one-to-one
function on an interval must be either everywhere increasing or
everywhere decreasing. Either way, we would find that f(a) would be
a maximum or minimum point in the image of exp, and we know no such
point exists.
So f carries the real line to (a, oo), and carries (a,oo) to (0,oo).
Thus f must carry (-oo, a] to (a,0]. We express this by defining numbers
a0 = a
a1 = 0
and the corresponding intervals
I0 = (-oo, a0] = (-oo, a]
I1 = (a0, a1] = (a, 0]
and then noting f(a_i) = a_(i+1) and f(I_i)=f(I_(i+1)) for i=0.
Likewise we can define an increasing sequence of numbers with
a_(i+1) = f(a_i)
and obtain a partition of the real line into half-open intervals
I_i = (a_(i-1), a_i]
with the property tha f(I_i)=f(I_(i+1)) for all i. Observe that
we already know half these numbers: since a_(i+2) = f(a_(i+1)) = f(f(a_i)) =
exp(a_i), we conclude a_3 = 1, a_5=e, a_7=e^e, and so on. The others
are likewise determined by a: a_2 = e^a, a_4 = e^(a_2), and so on.
Moreover, the action of f on all the larger intervals is also determined
by the action on the first two. For example, if x is in I2 = (0, a2],
then x = exp(y) for some y in I0 = (-oo, a], and so
f(x) = f(exp(y)) = f( f(f(y)) ) =f(f( f(y) )) = exp( f(y) )
so if you know what f does on I0, you can compute f(y) and then
f(x) = exp(f(y)) as well.
Even the action of f on the second interval is determined, as soon as
we know the action on the first one. For if x is in I1 = (a, 0], then
x = f(y) for some unique y in I0 = (-oo, a], and so
f(x) = f(f(y)) = exp(y) = exp(f^(-1)(x)).
Can we determine anything else for sure? The answer is no, since _any_
f meeting these conditions will serve as a square-root of exp. That is:
1. Pick any a < 0
2. Pick any increasing function f with f( (-oo, a] ) = (a,0]
3. Define f on (a,0] by f(x) = exp( f^(-1)(x) ).
4. Define f on the rest of the line recursively using
f(x) = exp(f(log(x)))
Then f will be a continuous function with f o f = exp.
For example, suppose we take a=-1. I need first an increasing function
carrying (-oo, -1] onto (-1,0]. Use f(x) = exp(x+1)-1, for example.
Then f is defined on (-1,0] by f(x) = exp( log(x+1) - 1 ) = (x+1)/e.
On subsequent intervals I use f(x) = exp(f(log(x)), so for example on
(0, 1/e] we have f(x) = exp( exp(logx + 1) -1) ) = exp( e*x - 1) and on
(1/e, 1] we have f(x) = exp( (logx + 1)/e ) = (e*x)^(1/e).
The formulas are messy and not nearly as informative, I think, as the
presentation in the previous paragraph.
Can one go further and ask that f be differentiable? Since differentiability
is a local phenomenon, we need ask only two things: that the f chosen
in step 2 be differentiable on (-oo, a), and that the behaviours on the
endpoints "match up": unscrambling the definition of the derivative, we need
lim ( f(a+h) - f(a) )/h = lim exp(w)/( f(w) - a )
h->0- w-> -oo
Assuming f is defined and differentiable on an open set larger than
(-oo, a], the left side is just f'(a). So in my example, for instance,
f'(a) = exp(a+1) = 1, while the limit on the right is 1/e, and I have
failed to provide differentiability. It's easy to convince oneself
graphically that this can be fixed: leave the graph of f unchanged
except on, say, [-2,-1], where f is to be raised higher a little sooner
and then allowed to increase more slowly at the right end (and so to have
a derivative of 1/e there); this can be justified formally by the use
of differentiable (even C^\infty) functions with compact support, but
I won't go into details since it's not clear that you're really interested
in this.
Now, if you want a function f with f o f = exp and f _real analytic_
everywhere, then none of this material is likely to help. Real-analytic
functions are much more "rigid"; typically their values on a small
interval completely determine their value everywhere, so we can't
expect to piece together local functions to get a global one.
(In other words, in the category of real-analytic functions, End(R) is a
much smaller semigroup, and exp = f^2 is much less likely to be true for
some f.)
For more information on functional equations of this type see
http://www.math.niu.edu/~rusin/known-math/index/39-XX.html
dave
==============================================================================
From: wvenable@spam.maths.adelaide.edu.au (Bill Venables)
Message-ID:
Date: 23 Jan 92 02:08:22 GMT
In article a_rubin@dsg4.dse.beckman.com (Arthur
Rubin) writes:
> These problems were stated (in some form) by the late Richard Feynmann.
> I've looked at them on and off since I was at CalTech, but I don't have any
> answers.
>
> (1) Is there a "natural" function f satisfying the equation:
>
> x
> f(f(x)) = e
Some references to work already done:
Kneser, H., Reele analytische L\"osungen der Gleichung $\phi(\phi(x))=e^x$.
J. f. reine angew. Math. v. 187, (1950) 56--67.
Szekeres, G., Fractional iteration of exponentially growing functions. J.
Australian Math. Soc. v. 2, (1962) 301-320.
> (2) Is there a "natural" function g satisfying the equation:
>
> x
> g(e ) = g(x) + 1
>
Problems (1) and (2) are connected. This is an Abel equation, the solution
of which is used in constructing solutions to (1). See above references.
I have no idea what "natural" means in this context, BTW.
--
Bill Venables, Dept. of Statistics, | Email: venables@stats.adelaide.edu.au
Univ. of Adelaide, South Australia. | Tel: +61 8 228 5412 Fax: ...232 5670
==============================================================================
From: somos@ces.cwru.edu (Michael Somos)
Message-ID: <1992Jan24.070252.8056@usenet.ins.cwru.edu>
Date: Fri, 24 Jan 92 07:02:52 GMT
The following article may be highly relevant:
Mathematics of Computation, October 1991, Volume 57, number 196, pp 723-733
INFINITELY DIFFERENTIABLE GENERALIZED LOGARITHMIC AND EXPONENTIAL FUNCTIONS
by Peter Walker, College of Science, Sultan Qabos University, P.O.Box 32486,
AL-KHOD, Muscat, Sultanate of Oman.
ABSTRACT. We construct infinitely differentiable solutions of the functional
equation f(x+1)=e^f(x). Numerical values are found and their accuracy is
discussed.
1. INTRODUCTION
Functions F,G satisfying
(1) F(x+1) = e^F(x)
and
(2) G(e^x) = G(x)+1
are called generalized exponential and logarithmic functions, respectively.
They are important in numerical analysis, where they are used in a new system
of computer arithmetic which has significant advantages over floating-point
arithmetic, including freedom from overflow and underflow, and a more satisfyin
g
error measure. Details of this can be found in [1] and [2].
More generally, solutions of the Abelian functional equation
(3) f(x+1) = phi(f(x)),
where phi is a given function mapping a set X to itself, are important in
studying the flow on X determined by phi. This is because the inverse function
g (suitably defined) satisfies
(4) g(phi(x)) = g(x)+1,
and the composition phi_t(x) = f(g(x)+t), t in R, satisfies the formal ident-
ities phi_0(x) = x, phi_1(x) = phi(x), and phi_{t+u}(x) = phi_t(phi_u(x)).
In the case X=C, phi(x) = e^x - 1, the author showed [7] that (3) has a
non-constant entire solution. Mapping properties of this function and its
inverse in C can be found in [9]. Numerical values are calculated in [6], and
by a different method in [8].
-------------------------------------------------------------------------------
[page 724]
The case X=C, phi(x) = e^x is of particular interest and difficulty owing
to the absence of a real fixed point and the complicated nature of the traject-
ories of the exponential function, as is shown for instance in [3]. The exist-
ance of a real-analytic solution of (2) in this case was proved by Kneser [5],
but that method did not allow numerical values to be calculated.
In this paper we show how to construct a C^oo solution of (2) by the use
of a C^oo auxiliary function h which satisfies
h(e^x) = e^h(x) - 1, x in R
The numerical values of h are easy to calculate since the iterative pro-
cedure by which it is defined is rapidly convergent. Section 2 gives the
construction of h and shows that it has the required properties. It is not
clear whether h can be continued analytically off the real axis: if this were
possible, then we could relate our solution to the one found by Kneser.
This function h is composed with the solution g (which is known from [7]
or [8]) of g(e^x - 1) = g(x) + 1, to give the required G = g o h. The major
difficulty arises in the calculation of g and this is discussed in $3.
Numerical values of G are calculated in the range [0,1]; values outside
this range can be found from the functional equation.
Other approaches to the problem which have been considered are discussed
and compared in $4.
...
-------------------------------------------------------------------------------
--
[page 733]
These differences cannot be explained without at least a proof of
convergence of the matrix method. And we cannot identify our function
defined by the iteration method of $3, with Kneser's function defined
by conformal mappings, without an extension of the domain of the
function h to include nonreal values. Until both these difficulties
have been overcome, the possibility remains that either two or three
distinct generalized logarithms have been constructed.
BIBLIOGRAPHY
1. C.W.Clenshaw, D.W.Lozier, F.W.J.Olver, and P.R.Turner, Generalized exponenti
al
and logarithmic functions, Comput. Math. Appl. 128 (5/6) (1986), 1091-1101.
2. C.W.Clenshaw, F.W.J.Olver, and P.R.Turner, Level-index arithmetics an intro-
ductory survery, Numerical Analysis and Parallel Processing (P.R.Turner, ed.
),
Lecture Notes in Math., vol. 1397, Springer-Verlag, New York, 1989.
3. R.L.Devaney and M.Krych, Dynamics of exp z, Ergodic Theory of Dynamical Syst
ems
4 (1984), 35-52.
4. P.Fatou, Sur les e'quations fonctionelles, Bull. Soc. Math. France 47 (1919)
,
161-261; 48 (1920), 33-94 and 208-314.
5. H.Kneser, Reele analytische Lo"sungen der Gleichung phi(phi(x))=e^x und verw
and-
ter Funktionalgleichungen, J. Reine Angew. Math. 187 (1948) 56-67.
6. K.W.Morris and G. Szekeres, Tables of the logarithm of iteration of e^x-1, J
.
Austral. Math. Soc. 2 (1961-1962), 321-333.
7. P.L.Walker, A class of functional equations which have entire solutions, Bul
l.
Austral. Math. Soc. 39 (1988), 351-356.
8. --, On the solutions of an Abelian functional equation, J. Math. Anal. Appl.
155 (1991) 93-110.
9. --, The exponential iteration of e^x-1, Proc. Amer. Math. Soc. 110 (1990), 6
11-
620.
-------------------------------------------------------------------------------
--
Shalom, Michael Somos (No, I don't work for CWRU)
==============================================================================
From: bromille@daimi.aau.dk (Peter Bro Miltersen)
Newsgroups: sci.math.research
Subject: Re: Functional Square Root of Exponentiation (Query)
Date: 25 Sep 1998 08:25:10 GMT
Yesterday, I asked whether there exists smooth, increasing functions f,
so that f(f(x))=e^x.
I received several replies, including archives of previous discussion
about this. The short answer to the question is YES - with lots more
to say about it. Below, I list the references I received in rough
chronological order. I did not check all of them myself yet.
My motivation for asking the question is some work we are doing in
computational complexity, where these and similar functions popped
up in a natural way.
Thanks to everybody for some very fast and helpful replies.
Peter.
------------------
H. Kneser, Reele analytische L\"osungen der Gleichung $\phi(\phi(x))=e^x$.
J. f. reine angew. Math. 187, (1950) 56--67.
G. Szekeres, Fractional iteration of exponentially growing functions. J.
Australian Math. Soc. 2, (1962) 301-320.
M. Kuczma, Functional Equations in a Single Variable,
PWN-Polish Scientific Publishers, Warsaw, 1968.
C. Horowitz, Iterated logarithms of entire functions. Israel J. Math. 29
(1978) 31--42.
M. Kuczma and B. Choczewski and R. Ger, Iterative Functional Equations,
Cambridge University Press, Cambridge, 1990.
P. Walker, Infinitely differentiable generalized logarithmic and exponential
functions, Mathematics of Computation 57 (1991) 723-733.
K. Iga, Continuous half-iterates of functions, Manuscript.
URL
==============================================================================
To: iga@math.stanford.edu
From: rusin@math.niu.edu
Subject: f(f(z))=exp(z)
Date: Dec. 23, 1997
In a paper I found at your site you conjecture there is an analytic
f with f o f = exp. If you mean "entire" (complex analytic on C)
then this is false. I asked a complex analyst about this once and
she found a paper by Polya (one of the London Math Soc journals about
1926) stating that if f and g are entire and
f o g is of finite order (e.g. the exponential function is)
then either f is of order 0 or g is a polynomial.
But in order to have f o f = exp, neither of these is permissible.
I assume there is a _real_ analytic f with f o f = exp, but
I don't really know for sure. (I'm in the process of looking into this.)
If you have an F with F(z+1) = exp(F(z)), then f(z) = F^(-1)(F(z)+1/2) will have the property f o f = exp. The existence of
such an F is discussed in some papers by P. Walker (recent) but I
haven't seen them; I think they also punt on the issue of analyticity.
dave
==============================================================================
[The thread arises again... -- djr]
==============================================================================
From: edgar@math.ohio-state.edu (G. A. Edgar)
Newsgroups: sci.math.research
Subject: Re: Iterated exponential
Date: Fri, 16 Oct 1998 14:11:32 -0400
In article <19981016104752.15123.00001386@ng40.aol.com>, rico162960@aol.com
(Rico162960) wrote:
> I have been working on the function f(x) with the following properties:
> exp(f(x))=f(x+1),f(0)=0, f inv(x)=g(x) where g(exp(x))=g(x)+1,if
> h(p,x)=f(g(x)+p) then h(p,h(q,x))=h(p+q,x). b(x)=f(x) - ln(x+1), f(x) is
> defined for x>-1 and b(x) is defined for x>-2. b(-1)=ln(f'(0)),
> b'(-1)=f"(0)/(2f'(0)). f(.5)=.498563, f'(.5)=.956753 approx. Does
anyone
> know if any work in this field?
>
Work up to 1968 may be found in this book.
(I think the iterated exponential is the last chapter)
AUTHOR Kuczma, Marek.
TITLE Functional equations in a single variable.
PUBLISH INFO Warszawa [PWN-Polish Scientific Publishers] 1968.
DESCRIPTION 383 p. illus. 25 cm.
SERIES Monografie matematyczne, t. 46.
NOTES On spine: Functional equations.
Bibliography: p. [308]-371.
--
Gerald A. Edgar edgar@math.ohio-state.edu
==============================================================================
From: Tony Dixon
Newsgroups: sci.math.research
Subject: Re: Iterated exponential
Date: Mon, 19 Oct 1998 15:47:44 +1300
Rico162960 wrote:
> I have been working on the function f(x) with the following properties:
> exp(f(x))=f(x+1),f(0)=0, f inv(x)=g(x) where g(exp(x))=g(x)+1,if
> h(p,x)=f(g(x)+p) then h(p,h(q,x))=h(p+q,x). b(x)=f(x) - ln(x+1), f(x) is
> defined for x>-1 and b(x) is defined for x>-2. b(-1)=ln(f'(0)),
> b'(-1)=f"(0)/(2f'(0)). f(.5)=.498563, f'(.5)=.956753 approx. Does anyone
> know if any work in this field?
g(x) is Abel's functional equation for exp(x), which grows slower than
any finite iterate of log(x). So f(x) grows faster than any iterate of
exp(x).
As well as Kuczma's book (Functional equations in a single variable),
you may be interested in the paper
G. Szekeres, "Scales of Infinity and Abel's functional equation," Math.
Chronicle 13, 1-17 (1984)
cheers, Tony
tdixon_AT_maths.otago.ac.nz
==============================================================================
[...and again...]
==============================================================================
From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik)
Newsgroups: sci.math
Subject: Re: Semi-logarithms
Date: 8 Dec 1998 15:10:03 -0500
In article ,
Carl R. White wrote:
:
:A while ago, in another thread, I introduced the following function to
:explain (or help explain) basic commutative functions:
:
:For positive-integer r and any x;
:
:ln^ 0(x) = x
:ln^ 1(x) = ln(x)
:ln^-1(x) = e^(x)
:ln^ r(x) = ln(ln^[r-1](x))
:ln^-r(x) = e^(ln^[1-r](x))
:
:However, I have begun to speculate about using real values for r, and not
:just integers. I seem, at this point, to have reached the limit of my
:expertise...
Consult books written by Marek Kuczma: Functional Equations in One
Variable (chapter about iteration groups, and references), and another
book co-authored by Kuczma, which is entirely about iterations.
The best situation would be to obtain an Abel function (iteration counter)
for the exponential, that is an invertible function A(x) with inverse
B(x) such that
A(exp(x)) = A(x) + 1
Then exp(x) = B(A(x) + 1),
exp(exp(x)) = B(A(x) + 2)
ln(x) = B(A(x) - 1)
and in your notation, ln^k(x) = B(A(x)-k)
applicable whenever A(x)-k is in the domain of B.
The trouble is that the domains (in the real case) of the iterated
logarithms recede, making the domain speculations difficult.
That's why Kuczma (or someone before him) introduced the iteration counter
a(x) for the function exp(x)-1 , because the iterations of the inverse,
the function ln(x+1), are all defined for all positive x.
His function (the letter "a" he uses is from the Gothic font) satisfies
a(exp(x)-1) = a(x) + 1
(together with an initial condition and monotonicity requirement)
and it is an example of a function which grows slower than any iterate of
the shifted logarithm, the ln(1+x) function.
Good luck, ZVK(Slavek).
==============================================================================
[...and again!...]
==============================================================================
From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Finding a power series
Date: 19 Dec 1998 16:39:07 GMT
Rico Federighi wrote:
> I f one sets f(x)=1/2 + 7/8 x + 1/4 x^2, I notice that f(f(x)) = 1 +
>63/64 x + 121/256 x^2 + 7/64 x^3 + 1/64x^4 is quite close to exp(x).
>Could one perturb the coefficients and solve for f(x) so that f(f(x))
>is indeed exp(x)? I have a gut feeling that the constant term of f(x)
>is closer to 347/696 than 1/2. I would be interested in any ideas one
>could shed on this problem. (Rico t. Federighi)
Assuming you expect the power series to converge for some nonzero x,
you're looking for an analytic function f which satisfies f o f = exp.
It's easy enough to find continuous -- even smooth -- functions f
with this property. I don't think there are such local analytic functions
f, and I know there are no such functions f whose Taylor series
converges for all x since this would make f an entire function
(analytic on the complex plane), at which point it would violate some
theorems about the rate of growth of such functions.
You can find some further information about functions f with f o f = exp
as one of the topics in Functional Equations,
http://www.math.niu.edu/~rusin/known-math/index/39-XX.html
although most of the material there (not all) deletes the assumption of
analyticity.
Let me point out why this question is of some importance. (Well, "of some
independent interest" might be more accurate).
1. You know that if m and n are integers, "m+n" means, "apply the
successor operation to m, n times". This operation "+" extends to
real numbers and has some nice properties (e.g. commutative law).
2. You know that if m and n are integers, "m*n" means, "apply the
addition operation to m, n times". This operation "*" extends to
real numbers and has some nice properties (e.g. commutative law).
3. You know that if m and n are integers, "m^n" means, "apply the
"*" operation to m, n times". This operation "^" extends to
real numbers and has some nice properties (e.g. associative law).
4. Now, if m and n are integers, let "m#n" mean, "apply the
"^" operation to m, n times". So e.g. 3#4 = 3^(3^(3^3))). Does
this operation "#" extend to real numbers in a way which has some
nice properties? One problem here is that it's not clear what those
nice properties should be (e.g. associative law cannot hold).
We can't tell what "x#(1/2)" should mean since we haven't specified
how "#" should behave for noninteger second arguments. When you
start to unravel what x#(1/2) should mean, you might eventually
come to the question posed at the outset here, namely, what
functions(s) have f o f = exp.
You might find more information by looking up "tower functions" or
"iterated exponentials".
dave