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