Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.83.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Non-computable Julia sets
HTML articles powered by AMS MathViewer

by M. Braverman and M. Yampolsky
J. Amer. Math. Soc. 19 (2006), 551-578
DOI: https://doi.org/10.1090/S0894-0347-05-00516-3
Published electronically: December 22, 2005
PDF | Request permission

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
  • 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, DOI 10.1007/978-1-4612-0701-6
  • Artur Avila, Xavier Buff, and Arnaud Chéritat, Siegel disks with smooth boundaries, Acta Math. 193 (2004), no. 1, 1–30. MR 2155030, DOI 10.1007/BF02392549
    • [BBY1]BBY1 I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at Arxiv.org. [BBY2]BBY2 I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear.
  • Errett Bishop and Douglas Bridges, Constructive analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. MR 804042, DOI 10.1007/978-3-642-61667-9
    • [Brv1]thesis 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]Brv2 M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at Arxiv.org.
  • 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]BC2 X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242. [BC2]BC X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
  • 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, DOI 10.1090/psapm/049/1315535
  • 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
  • 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, DOI 10.24033/asens.1491
  • A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168–202. MR 86756, DOI 10.4064/fm-42-1-168-202
  • Ker-I Ko, Complexity theory of real functions, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1137517, DOI 10.1007/978-1-4684-6802-1
  • 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, DOI 10.1016/S0049-237X(98)80052-9
  • 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 72079
  • S. Mazur, Computable analysis, Rozprawy Mat. 33 (1963), 110. MR 153553
  • 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, DOI 10.1007/s002200050110
  • Yu. V. Matiyasevich, Desyataya problema Gil′berta, 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
  • Curtis T. McMullen, Complex dynamics and renormalization, Annals of Mathematics Studies, vol. 135, Princeton University Press, Princeton, NJ, 1994. MR 1312365
  • John Milnor, Dynamics in one complex variable, Friedr. Vieweg & Sohn, Braunschweig, 1999. Introductory lectures. MR 1721240
  • 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, DOI 10.4007/annals.2004.159.1
  • Ch. Pommerenke, Boundary behaviour of conformal maps, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 299, Springer-Verlag, Berlin, 1992. MR 1217706, DOI 10.1007/978-3-662-02770-7
    • [Ret]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).
  • 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, DOI 10.1145/780542.780570
  • Steffen Rohde and Michel Zinsmeister, Variation of the conformal radius, J. Anal. Math. 92 (2004), 105–115. MR 2072743, DOI 10.1007/BF02787758
  • Carl Ludwig Siegel, Iteration of analytic functions, Ann. of Math. (2) 43 (1942), 607–612. MR 7044, DOI 10.2307/1968952
    • [Sip]Sip M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. [Tur]Tur A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265.
  • Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. MR 1795407, DOI 10.1007/978-3-642-56999-9
  • 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
Bibliographic 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
  • 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
  • © Copyright 2005 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • 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
  • MathSciNet review: 2220099