Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 

 

Non-computable Julia sets


Authors: M. Braverman and M. Yampolsky
Journal: J. Amer. Math. Soc. 19 (2006), 551-578
MSC (2000): Primary 37F50; Secondary 68Q17
DOI: https://doi.org/10.1090/S0894-0347-05-00516-3
Published electronically: December 22, 2005
MathSciNet review: 2220099
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that under the definition of computability which is natural from the point of view of applications, there exist non-computable quadratic Julia sets.


References [Enhancements On Off] (What's this?)

  • [BCSS] Lenore Blum, Felipe Cucker, Michael Shub, and Steve Smale, Complexity and real computation, Springer-Verlag, New York, 1998. With a foreword by Richard M. Karp. MR 1479636
  • [ABC] Artur Avila, Xavier Buff, and Arnaud Chéritat, Siegel disks with smooth boundaries, Acta Math. 193 (2004), no. 1, 1–30. MR 2155030, https://doi.org/10.1007/BF02392549
  • [BBY1] I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at Arxiv.org.
  • [BBY2] I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear.
  • [BB] Errett Bishop and Douglas Bridges, Constructive analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. MR 804042
  • [Brv1] M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Proc. CCA 2004., Electr. Notes Theor. Comput. Sci. 120: 17-30 (2005).
  • [Brv2] M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at Arxiv.org.
  • [Bru] A. D. Brjuno, Analytic form of differential equations. I, II, Trudy Moskov. Mat. Obšč. 25 (1971), 119–262; ibid. 26 (1972), 199–239 (Russian). MR 0377192
  • [BC1] X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242.
  • [BC2] X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
  • [Do] Adrien Douady, Does a Julia set depend continuously on the polynomial?, Complex dynamical systems (Cincinnati, OH, 1994) Proc. Sympos. Appl. Math., vol. 49, Amer. Math. Soc., Providence, RI, 1994, pp. 91–138. MR 1315535, https://doi.org/10.1090/psapm/049/1315535
  • [DH1] A. Douady and J. H. Hubbard, Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 84, Université de Paris-Sud, Département de Mathématiques, Orsay, 1984 (French). MR 762431
    A. Douady and J. H. Hubbard, Étude dynamique des polynômes complexes. Partie II, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 85, Université de Paris-Sud, Département de Mathématiques, Orsay, 1985 (French). With the collaboration of P. Lavaurs, Tan Lei and P. Sentenac. MR 812271
    A. Douady and J. H. Hubbard, Étude dynamique des polynômes complexes. Partie I, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 84, Université de Paris-Sud, Département de Mathématiques, Orsay, 1984 (French). MR 762431
    A. Douady and J. H. Hubbard, Étude dynamique des polynômes complexes. Partie II, Publications Mathématiques d’Orsay [Mathematical Publications of Orsay], vol. 85, Université de Paris-Sud, Département de Mathématiques, Orsay, 1985 (French). With the collaboration of P. Lavaurs, Tan Lei and P. Sentenac. MR 812271
  • [DH2] Adrien Douady and John Hamal Hubbard, On the dynamics of polynomial-like mappings, Ann. Sci. École Norm. Sup. (4) 18 (1985), no. 2, 287–343. MR 816367
  • [Grz] A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 0086756
  • [Ko1] Ker-I Ko, Complexity theory of real functions, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1137517
  • [Ko2] K. Ko, Polynomial-time computability in analysis, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1271–1317. MR 1673610, https://doi.org/10.1016/S0049-237X(98)80052-9
  • [Lac] Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. I, C. R. Acad. Sci. Paris 240 (1955), 2478–2480 (French). MR 0072079
    Daniel Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. II, III, C. R. Acad. Sci. Paris 241 (1955), 13–14, 151–153 (French). MR 0072080
  • [Maz] S. Mazur, Computable analysis, Rozprawy Mat. 33 (1963), 110. MR 0153553
  • [MMY] S. Marmi, P. Moussa, and J.-C. Yoccoz, The Brjuno functions and their regularity properties, Comm. Math. Phys. 186 (1997), no. 2, 265–293. MR 1462766, https://doi.org/10.1007/s002200050110
  • [Mat] Yu. V. Matiyasevich, \cyr Desyataya problema Gil′berta, \cyr Matematicheskaya Logika i Osnovaniya Matematiki [Monographs in Mathematical Logic and Foundations of Mathematics], vol. 26, VO “Nauka”, Moscow, 1993 (Russian, with Russian summary). MR 1247235
    Yuri V. Matiyasevich, Hilbert’s tenth problem, Foundations of Computing Series, MIT Press, Cambridge, MA, 1993. Translated from the 1993 Russian original by the author; With a foreword by Martin Davis. MR 1244324
  • [McM1] Curtis T. McMullen, Complex dynamics and renormalization, Annals of Mathematics Studies, vol. 135, Princeton University Press, Princeton, NJ, 1994. MR 1312365
  • [Mil] John Milnor, Dynamics in one complex variable, Friedr. Vieweg & Sohn, Braunschweig, 1999. Introductory lectures. MR 1721240
  • [PZ] C. L. Petersen and S. Zakeri, On the Julia set of a typical quadratic polynomial with a Siegel disk, Ann. of Math. (2) 159 (2004), no. 1, 1–52. MR 2051390, https://doi.org/10.4007/annals.2004.159.1
  • [Pom] Ch. Pommerenke, Boundary behaviour of conformal maps, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 299, Springer-Verlag, Berlin, 1992. MR 1217706
  • [Ret] R. Retinger. A fast algorithm for Julia sets of hyperbolic rational functions, Proc. of CCA 2004, Electr. Notes Theor. Comput. Sci. 120: 145-157 (2005).
  • [RW] Robert Rettinger and Klaus Weihrauch, The computational complexity of some Julia sets, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 177–185. MR 2121048, https://doi.org/10.1145/780542.780570
  • [RZ] Steffen Rohde and Michel Zinsmeister, Variation of the conformal radius, J. Anal. Math. 92 (2004), 105–115. MR 2072743, https://doi.org/10.1007/BF02787758
  • [Sie] Carl Ludwig Siegel, Iteration of analytic functions, Ann. of Math. (2) 43 (1942), 607–612. MR 0007044, https://doi.org/10.2307/1968952
  • [Sip] M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
  • [Tur] A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265.
  • [Wei] Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407
  • [Yoc] Jean-Christophe Yoccoz, Théorème de Siegel, nombres de Bruno et polynômes quadratiques, Astérisque 231 (1995), 3–88 (French). Petits diviseurs en dimension 1. MR 1367353

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 37F50, 68Q17

Retrieve articles in all journals with MSC (2000): 37F50, 68Q17


Additional Information

M. Braverman
Affiliation: Department of Computer Science, University of Toronto, Toronto, ON M5S 3G4, Canada

M. Yampolsky
Affiliation: Department of Mathematics, University of Toronto, Toronto, ON M5S 2E4, Canada

DOI: https://doi.org/10.1090/S0894-0347-05-00516-3
Received by editor(s): June 28, 2004
Published electronically: December 22, 2005
Additional Notes: The first author’s research is supported by an NSERC CGS scholarship
The second author’s research is supported by an NSERC operating grant
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.