Iterative Roots and Fractional Iteration

References collected by Lars Kindermann

A solution φ of the functional equation φ(φ(x))=f(x) or φ2=f is called an iterative root of the given function f. More general, solutions of φn=fm are the fractional iterates of f: φ=fm/n. Extending this notation towards even real exponents ft defines the continous iteration (semi)group of the function f. The "standard interpretation" of this procedure is the embedding of a discrete time dynamical system into a continuous flow. While this problem is investigated since 1815, Charles Babbage was the first to look for the "roots of identity" φ(φ(x))=x, it remains an often extremely difficult task to find the iterative roots of even very simple functions. Many questions about their existence, uniqueness and properties are still unsolved.

The most cited reference to this topic is the book Iterative functional equations by Marek Kuczma, Bogdan Choczewski & Roman Ger (1990) together with the update article Recent results on functional equations in a single variable, perspectives and open problems by Karol Baron & Witold Jarczyk (2001). Another good book with some more emphasis on applications is Topics in Iteration Theory (1981) with the update Progress of Iteration Theory since 1981 (1995) by György Targonski.

Some basic introduction and mathematical classification can be found online on the webpage by D. Rusin: Difference and functional equations. In: The mathematical Atlas at www.math-atlas.org


References

* J. Aczél, G. Rote & J. Schwaiger, Webs, Iteration Groups and Equivalent Changes in Probabilities. Quarterly of Applied Mathematics 54 (1996), 475-499 | Article

* R. Aldrovandi, L.P. Freitas, Continous Iteration of Dynamical Maps. J. Math. Phys. 39 (1998), 5324-5336

* Ll. Alsedá, S. Kolyada, J. Llibre & L. Snoha, Axiomatic definition of the topological entropy on the interval. Preprint CRM #458, Centre de Recerca Matematica, Barcelona. To appear in Aequationes Math.(2000) | Article

* C. Babbage, Essay towards the Calculus of functions. Phil. trans. Royal Soc. London 105 (1815), 389-424 | Article

C. Babbage, Examples of the solution of functional equations. Cambridge 1820

M. Bajraktarevic, Solution générale de l'équation fonctionelle fN(x) = g(x). Publ. Inst. Math. Beograd (N.S.) 5(19) (1965), 115-124

* I.N. Baker, The iteration of entire transcendental functions and the solution of the functional equation f(f(z) = F(z). Math. Ann. 129 (1955), 174-180

* I.N. Baker, Zusammensetzung ganzer Funktionen. Math. Zeitschr. 69 (1958), 121-163

* K. Baron & W. Jarczyk, Recent results on functional equations in a single variable, perspectives and open problems. Aequationes Math. 61. (2001), 1-48 | Abstract

L. Bartlomiejczyk, Iterative roots with big graph. Abstract of Summer symposium in Real Analysis, XXIV, Real Anal. Exchange

A.F. Beardon, Iteration of rational functions. Complex analytic dynamical systems. Graduate Texts in Mathematics 132, Springer-Verlag, New York, 1991

J. Beránek, On Tabors problem concerning a certain quasi - ordering of iterative roots of functions. Aequationes Math. 39. (1990), 1-5 | Homepage

* A. Blokh, E. Coven, M. Misiurewicz & Z. Nitecki, Roots of continuous piecewise monotone maps of an interval. Acta Math. Univ. Comenianae, (1991), 3-10

* A.M. Blokh, The set of all iterates is nowhere dense in C ([0,1],[0,1]). Trans. Amer. Math. Soc. 322, (1992), 787-798

* U.T. Bödewadt, Zur Iteration reeller Funktionen. Math. Zeitschr. 49 (1943), 497-516

* S. Bogatyi, On the nonexistence of iterative roots. Topology and its applications. 76 (1997), 97-123

* S. Bogatyi, A topological view on a problem of formal series. Aequationes Math. 56 (1998), 18-22 | Abstract

* K. Briggs, Formal power series solution of functional equations. MapleTech 2, no. 2 (1995), 48-51 | Homepage postscript.gz

* K. Brown, f(f(x)) = exp(x) generates the Multinomials. Draft on website http://mathpages.com/home/kmath507.htm

R. Brown, On solving nonlinear functional, finite difference, composition and iterated equations. Fractals 7 (1999), 277-282

+ E. Castillo, A. Iglesias,A Package for symbolic solution of real functional equations of real variables. Aequationes Math. 54 (199), 181-198 | Abstract

* R. Cheng, A. Dasgupta, B.R. Ebanks, L.F. Kinch, L.M. Larson & R.B. McFadden, When Does f-1=1/f? (1988)

* B. Choczewski, Problem 27. Report of meeting. The Twenty-eight International Symposium on Functional Equations (Graz-Mariatrost, 1990), Aequationes Math. 41 (1991), 296

* B. Choczewski & M. Kuczma, On iterative roots of polynomials. European conference of iteration theory - Lisboa ’91 (1992), 59-67

+ J.P.R. Christensen, Topology and Borel Structure. North-Holland Math. Studies 10, Amsterdam, 1974

* L. Comtet, Advanced Combinatorics. Reidel Publishing, Dordrecht, 1974

Wun-Seng Chou, Iterative roots of constant ploynomials over finite fields. Meeting of the Amer. Math. Soc., Las Vegas, 1999

P.J. Davis, Interpolation and Approximation. Blaisdell Publishing Company, New York 1963

G. Derfel & R. Schilling, Spatially chaotic configurations and functional equations with rescaling. J. Phys. A: Math. Gen. 29 (1996), 4537-4547

K.D. Dikof & R. Graw, A strictly increasing real function with no iterative roots of any order. Remark at the 1980 International Symposium on Functional Equations, Abstract to be Published.

* K.B. Dunn & R. Lidl, Iterative roots of functions over finite fields. Math. Nachr. 115 (1984), 319-329

* P. Erdös & E. Jabotinsky, On Analytic Iteration. J. Analyse Math. 8 (1960/61), 361-376

* G.M. Ewing & W.R. Utz, Continuous solutions of fn(x) = f(x). Can. J. Math. 5 (1953), 101-103

* M.J. Feigenbaum, Quantitative Universality for a Class of Nonlinear Transformations. J. of Statistic Physics 19 (1978), 25-52

H. Fripertinger & L. Reich, Functional equations and iteration theory. Webpage of the project, There are more references on this page available!

* B. Gawel, On the uniqueness of continuous solutions of functional equations. Ann. Polon. Math. LX.3 (1995), 231-239

* V. Goryainov, Koenigs function and fractional iteration of probability generating functions. XVIII Nevanlinna Colloquium, University of Helsinki, 2000 | Abstract

P.I. Haidukov, On searching a function from a given iterate. Uc. Zap. Buriatsk. Ped. Inst. 15 (1958), 361-376

* H.J. Hamilton, Roots of equations by functional iteration. Duke. Math. J. 13 (1946), 113-121

+ G.H. Hardy, Orders of infinity. Cambridge Tracts in Mathematics 12 (1924), 31

* C. Horowitz, Iterated logarithms of entire functions. Israel J. Math. 29 (1978), 31-42

* P.D. Humke & M. Laczkovich, The Borel structure of iterates of continuous functions. Proc. Edinburgh Math. Soc. (2) 32 (1989), 483-494

* K. Iga, Continuous half-iterates of functions. Manuscript from http://math.pepperdine.edu/~kiga | postscript

* R. Isaacs, Iterates of fractional order. Canad. J. Math. 2 (1950), 409-416.

R. Isaacs, On Fractional Iteration. Technical Report No. 320, Department of Mathematical Sciences, The John Hopkins University, November 1979

* E. Jabotinsky, Analytic iteration. Trans. Amer. Math. Soc. 108 (1963), 457-477

W. Jarczyk, A recurrent method of solving iterative functional equations. Prace Nauk. Uniw. Slask. Katowic. 1206 (1991)

* L. Kindermann, An Addition to Backpropagation for Computing Functional Roots. Proc. Int'l ICSC/IFAC Symp. on Neural Computation - NC'98, Vienna (1998), 424-427 | homepage Article

* L. Kindermann, Computing Iterative Roots with Neural Networks. Proc. Fifth Int'l Conf. on Neural Information Processing - ICONIP'98, Vol. 2, Kitakyushu (1998), 713-715 | Article

* L. Kindermann, A. Lewandowski & P. Protzel, A Comparison of Different Neural Methods for Solving Iterative Roots. Proc. Seventh Int'l Conf. on Neural Information Processing - ICONIP'2000, Taejon (2000), 565-569 | Article

* L. Kindermann & P. Protzel, Computing iterative roots with second order training methods. Proceedings of the International Joint Conference on Neural Networks (IJCNN'2001), Washington DC 2001 | Article

* L. Kindermann, Neuronale Netze zur Berechnung Iterativer Wurzeln und Fraktionaler Iterationen. Ph.D Thesis, University of Chemnitz 2001

* L. Kindermann, A. Lewandowski & P. Protzel, A framework for solving functional equations with neural networks. Proc. Eighth Int'l Conf. on Neural Information Processing - ICONIP'2001, Fudan University Press, Shanghai (2001), 1075-1078 | Article

* L. Kindermann & P. Protzel, Physics without laws - Making exact predictions with data based methods. Proc. Int'l Joint Conference on Neural Networks - IJCNN'2002, Honolulu (2002), 1673-1677 | Article

* L. Kindermann, A. Lewandowski & P. Protzel, Finding the Optimal Continuous Model for Discrete Data by Neural Network Interpolation of Fractional Iteration. To Appear in: Proc. Int'l Conf. on Artificial Neural Networks - ICANN 2002, Madrid (2002) | Article

* H. Kneser, Reelle analytische Lösungen der Gleichung φ(φ(x)) = ex und verwandter Funktionalgleichungen. J. reine angew. Math. 187 (1950), 56-67

* J. Kobza, Iterative functional equation x(x(t))=f(t) with f(t) piecewise linear. Journal of Computational and Applied Mathematics 115 (2000), 331-347

+ A.R. Kräuter, Wurzeln und analytische Iteration formal-biholomorpher Abbildungen. Berichte Math. Stat. Forschungszentrum Graz 123 (1980)

* U. Krengel & H. Michel, Über Wurzeln ergodischer Transformationen. Math. Z. 96 (1967), 50-57

D. Kroll, Grundlagen Nichtlinearer Analyse: Differential und Differenzengleichungen. In: Nichtlineare Dynamik in kondensierter Materie, Kernforschungsanlage Jülich, 1983

* M. Kuczma, On the functional equation φn(x) = g(x). Ann. Polon. Math. 11 (1961) 161-175

M. Kuczma, On the Schröder equation. Rozprawy Matematyczne, Instytut Matematyczny Polskiej Akademii Nauk, Warszawa, 1963

* M. Kuczma & A. Smajdor, Fractional Iteration in the class of convex functions. Bull. Acad. Polon. Sci., Ser. sci. math. astronom. phys. 16 (1968), 717-720

M. Kuczma, Functional Equations in a Single Variable, PWN-Polish Scientific Publishers, Warsaw, 1968.

* M. Kuczma, Fractional iteration of differentiable functions. Ann. Polon. Math. 22 (1969), 217-227

M. Kuczma, Fractional iteration of differentiable functions with multiplier zero. Commentationes Math. 14 (1970) 35-39

* M. Kuczma & A. Smajdor, Regular fractional iteration. Bull. Acad. Polon. Sci., Ser. sci. math. astronom. phys. 19 (1971), 203-207

* M. Kuczma, Regular fractional iteration of convex functions. Ann. Polon. Math. 38 (1980), 95-100

* M. Kuczma, B. Choczewski, R. Ger, Iterative functional equations. Encyclopedia of Mathematics and its Applications, Vol. 32, Cambridge University Press, Cambridge 1990

* M. Kuczma, On a functional equation ocurrimg in astrophysics. Mathematica Pannonica 3/2 (1992), 17-27

G. Labelle, Sur l'Inversion et l'Iteration Continue des Séries Formelles. Europ. J. Combinatorics, 1 (1980), 113-138

* R. Leipnik & R. Oberg, Subvex functions and Bohr’s uniqueness theorem. Amer. Math. Monthly 74 (1967), 1093-1094

* Z. Lesniak, Constructions of fractional iterates of sperner homeomorphisms of the plane. In: W. Foerg-Rob, Iteration Theory, Singapore u.a. 1996, S. 182-192

He Lianfa & New Dongxiao, The iterative roots for a class of selfmapping on S1. Jour. Math. Res. & Exp. 11 (1991), 305-310

* J.C.Lillo, The functional equation fn(x) = g(x). Arkiv för Mat. 5 (1965), 357-361

* J.C.Lillo, The functional equation f2(x) = g(x). Ann. Polon. Math. 19 (1967), 123-135

L.S.O. Liverpool, Fractional iteration near a fix point of multiplier 1. J. London Math. Soc. 41 (1979) | Homepage

* S. Lojasiewicz, Solotion générale de l'équation fonctionelle f(f(...f(x)...))) = g(x). Annales de la Societé Plonaise de Mathematique 24 (1951), 88-91

* J.L. Massera & A. Petracca, On the functional equation f(f(x)) = 1/x. Revista Union Mat. Argentinia 11 (1946), 206-211

* P.J. McCarthy, Ultrafunctions, projective function geometry, and polynomial functional equations. Proc. London Math. Soc. (3) 53 (1986), 321-339

* A. McNaughton, Generalized iterative roots. Abstracts of the New Zealand Mathematics Colloquium, University of Waikato, Hamilton, New Zealand 2000 | Abstract

* P.B. Miltersen, N.V Vinodchandran, O. Watanabe, Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Research Report c-130, 1999. Dept. of Math and Comput. Sc., Tokyo Inst. of Tech. and BRICS Report Series RS-99-4, Dept. of Computer Science, Univ. Aarhus, 1999 | Article

* C. Mira & S. Müllenbach, Sur l’iteration fractionaire d’un endomorphisme quadratique. Comptes rendus Acad. Sci. Paris (1) Math. 297, (1983), 369-372

T. Narayaninsamy, On the fractional iteration of endomorphisms. In: European Conference on Iteration Theory, eds. J. P. Lampreia, J. Llibre, C. Mira, J. Sousa Ramos, G. Targonski, Singapore 1991

T. Narayaninsamy, On a class of fractional iterates. Int. J. of Bifurcation and Chaos 6 (1996), 55 - 67

T. Narayaninsamy, Fractional iterates for n-dimensional maps. J. Applied Mathematics and Computation 98 (1999), 261-278

T. Narayaninsamy, A connection between fractional iteration and graph theory. J. App. Math. Comp. 107 (2000), 181-202 | Article

* D.S. Ornstein, Ergodic theory, randomness and dynamical systems. Yale University Press, 1974

* T. Powierza, Set-valued Iterative Square Roots of Bijections. Bull. Pol. Ac. Math. 47 (1999)

* T. Powierza, On the smallest set-valued iterative roots of bijections. Abstracts of The 2nd Debrecen-Katowice Winter Seminar on Functional Equations, Hajdúszoboszló, Hungary 2002 | Abstract

L. Reich, Analytische und fraktionelle Iteration formal-biholomorpher Abbildungen. Jahrbuch Überblicke Mathematik 1979, Bibliographisches Institut (1979)

L. Reich, On power series transformations in one indeterminate having iterative roots of given order and with given multiplier. European Conf. Iteration Theory - ECIT, Lisbon (1991), 210-216

* L. Reich, On the distribution of formal power series transformation with respect to embeddability in the order topology. Österreichische Akademie der Wissenschaften, Sitzungsbericht Abt. II 208 (1999), 97-114

* R. Resch, F. Stenger, & J. Waldvogel, Functional equations related to the iteration of functions. Aequationes Math. 60 (2000), 25-37 | Abstract

* J.P. Ressayre, Iterations of o-minimal functions. Abstracts of the New York City Logic Conference, 1999 | Homepage

R.E. Rice, Fractional iterates. PhD Thesis, University of Massachusetts, Amherest (1977)

R.E. Rice, Iterative square roots of Cebysev polynomials. Stochastica 3 (1979), 1-14

* R.E. Rice, B. Schweizer & A. Sklar, When is f(f(z)) = az2+bz+c for all complex z? Amer. Math. Monthly 87 (1980), 252-263

* G. Riggert, n-te iterative Wurzeln von beliebigen Abbildungen. Aequ. Math. 14 (1976), 208

* G. Riggert, Note on n-th iterative roots of mappings of a finite set into itself. Aequ. Math. 15 (1977), 288

* R. Schilling, Spatially chaotic structures. In: H. Thomas, Nonlinear Dynamics in Solids, Springer-Verlag, Berlin, 1992, 213-241

* E. Schröder, Über iterierte Funktionen. Math. Ann. 3 (1871), 296-322

J. Schwaiger, Roots of formal power series in one variable. Aequationes Math. 29 (1985), 40-43

* B. Schweizer & A. Sklar, Invariants and equivalence classes of polynomials under linear conjugacy. Contributions to General Algebra 6 (1988), 253-257

* K. Simon, Some dual statements concerning Wiener measure and Baire category. Proc. Amer. Math. Soc. 106 (1989), 455-463

* K. Simon, Typical continuous functions are not iterates. Acta Math. Hung. 55 (1990), 133-134

* A. Sklar, Canonical decompositions, stable functions and fractional iterates. Aequat. Math. 3 (1969), 118-129

* A. Smith, Is there any way to approximate the solution of f(x) given f(f(x)) = g(x)? Argonne National Laboratory, Division of Educational Programs. Newton BBS: Ask A Scientist Mathematics Archive (1993) www.newton.dep.anl.gov/newton/askasci/1993/math/MATH023.HTM

* L. Smolarek, The formula of fractional iteration of function differentiable at its fixed point. Zeszyty Nauk. Mat. Uniw. Gdans. 7 (1987), 99-107 | Homepage

* G. Szekeres, Regular iterations of real and complex functions. Acta Math. 100 (1958), 203-258

* G. Szekeres, Fractional iteration of exponentially growing functions. J. Austral. Math. Soc. 2 (1961/62), 301-320

G. Targonski, Topics in Iteration Theory. Vandenhoeck und Ruprecht, Göttingen 1981

* G. Targonski, An Iteration theoretical approach to the concept of time. Colloques Internationaux du C.N.R.S. 229, Transformations ponctuelles et leurs applications, Toulouse (1973), 259-271

G. Targonski, Open questions about KW-orbits and iterative roots. Aequationes Math. 41 (1991), 277-278

* G. Targonski, Progress of iteration theory since 1981. Aequationes Math. 50 (1995), 50-72

* B.B. Tenneson, More on iteration - Fractional iterates of f(x) = x2-2. Manuscript from online.sfsu.edu/~brian271 | Article

* H. Töpfer, Komplexe Iterationsindizes ganzer und rationaler Funktionen. Math. Ann. 121 (1949), 191-222

* P. Walker, The exponential of iteration of ex-1. Proc. Am. Math. Soc. 110 (1990), 611-620

* P. Walker, Infinitely differentiable generalized logarithmic and exponential functions. Mathematics of Computation 57 (1991), 723-733

G.J. Whitrow, The Natural Philosophy of Time. Thomas Nelson and Sons Ltd. London and Edinburgh 1961

* M.C. Zdun, Continous iteration semigroups. Boll. Un. Mat. Ital. 14 A (1977), 65-70

* M.C. Zdun, Differentiable fractional iteration. Bull. Acad. Sci. Polon. Sér. Sci. Math. Astronom. Phys. 25 (1977), 643-646

* M.C. Zdun, On differentiable iteration groups. Publ. Math. Debrecen 26 (1979), 105-114

* M.C. Zdun, Regular fractional iterations. Aequationes Math. 28 (1985), 73-79

* M.C. Zdun, On iterative roots of homeomorphisms of the circle. Bull. Pol. Ac: Math. 48 (2000)

Weinian Zhang, Discussion on iterated equation Σi=1n fi(x)=F(x) Chin. Sci. Bul. (Kexue Tongbao), 32 (1987), 21: 1444-1451

* Weinian Zhang, A generic property of globally smooth iterative roots. Scientia Sinica A, 38 (1995), 267-272

Weinian Zhang, PM functions, their characteristic intervals and iterative roots. Annales Polonici Mathematici, LXV.2 (1997), 119-128

Weinian Zhang, Discussion on the differentiable solutions of the iterated equation Σi=1n fi(x)=F(x). Nonlinear Analysis, 15 (1990), 4: 387-398

Weinian Zhang, Solutions of equivariance for a polynomial-like iterative equation. Proc. Royal Soc. Edinburgh, 130A (2000), 5: 1153-1163

* G. Zimmermann, Über die Existenz iterativer Wurzeln von Abbildungen. Dissertation, Marburg/Lahn 1978


Contact

©2004 For comments, questions, additions please contactXkindermann@reglos.de at www.reglos.de/kindermann