Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-10T12:31:25.101Z Has data issue: false hasContentIssue false
  • English
  • Français

Poly-time computability of the Feigenbaum Julia set

Published online by Cambridge University Press:  21 July 2015

ARTEM DUDKO  and
MICHAEL YAMPOLSKY
ARTEM DUDKO
Affiliation:
Mathematics Department, Stony Brook University, USA
MICHAEL YAMPOLSKY
Affiliation:
Mathematics Department, University of Toronto, Canada email yampol@math.toronto.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present the first example of a poly-time computable Julia set with a recurrent critical point: we prove that the Julia set of the Feigenbaum map is computable in polynomial time.

Information

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 36 , Issue 8 , December 2016 , pp. 2441 - 2462
Copyright
© Cambridge University Press, 2015 

References

Binder, I., Braverman, M. and Yampolsky, M.. On computational complexity of Siegel Julia sets. Commun. Math. Phys. 264(2) (2006), 317–334.CrossRefGoogle Scholar
Binder, I., Braverman, M. and Yampolsky, M.. Filled Julia sets with empty interior are computable. Found. Comput. Math. 7 (2007), 405–416.CrossRefGoogle Scholar
Braverman, M.. Computational complexity of Euclidean sets: hyperbolic Julia sets are poly-time computable. Master’s Thesis, University of Toronto, 2004.CrossRefGoogle Scholar
Braverman, M.. Parabolic Julia sets are polynomial time computable. Nonlinearity 19(6) (2006), 1383–1401.CrossRefGoogle Scholar
Braverman, M. and Yampolsky, M.. Non-computable Julia sets. J. Amer. Math. Soc. 19(3) (2006), 551–578.CrossRefGoogle Scholar
Braverman, M. and Yampolsky, M.. Computability of Julia Sets (Algorithms and Computation in Mathematics, 23) . Springer, Berlin, 2008.Google Scholar
Buff, X.. Geometry of the Feigenbaum map. Conform. Geom. Dyn. 3 (1999), 79–101.CrossRefGoogle Scholar
de Melo, W. and van Strien, S.. One-dimensional Dynamics. Springer, Berlin, 1993.CrossRefGoogle Scholar
Douady, A. and Hubbard, J.. On the dynamics of polynomial-like maps. Ann. Sci. Éc. Norm. Supér. (4) 18 (1985), 287–344.CrossRefGoogle Scholar
Dudko, A.. Computability of the Julia set. Non-recurrent critical orbits. Discrete Contin. Dyn. Syst. Ser. A 34 (2014), 2751–2778.CrossRefGoogle Scholar
Epstein, H.. Fixed points of composition operators II. Nonlinearity 2 (1989), 305–310.CrossRefGoogle Scholar
Epstein, H.. Fixed points of the period-doubling operator. Lecture Notes, Lausanne.Google Scholar
Lanford, O. III. A computer-assisted proof of the Feigenbaum conjectures. Bull. Amer. Math. Soc. (N.S.) 6(3) (1982), 427–434.CrossRefGoogle Scholar
Lyubich, M.. Dynamics of quadratic polynomials, I–II. Acta Math. 178 (1997), 185–297.CrossRefGoogle Scholar
Lyubich, M.. Feigenbaum–Coullet–Tresser universality and Milnor’s hairiness conjecture. Ann. of Math. (2) 149 (1999), 319–420.CrossRefGoogle Scholar
McMullen, C.. Renormalization and 3-manifolds which Fiber Over the Circle (Annals of Math Studies, 142) . Princeton University Press, Princeton, NJ, 1996.CrossRefGoogle Scholar
Papadimitriou, C. M.. Computational Complexity. Addison-Wesley, Reading, MA, 1994.Google Scholar
Rettinger, R.. A fast algorithm for Julia sets of hyperbolic rational functions. Electron. Notes Theor. Comput. Sci. 120 (2005), 145–157.CrossRefGoogle Scholar
Sipser, M.. Introduction to the Theory of Computation, 2nd edn. BWS Publishing, Boston, 2005.Google Scholar
Turing, A. M.. On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. (3) 42 (1937), 230–265.CrossRefGoogle Scholar