×

zbMATH — the first resource for mathematics

Non-computable Julia sets. (English) Zbl 1099.37042
The authors study computability properties of Julia sets of quadratic polynomials. Here, a set is computable, if, roughly speaking, its image can be generated by a computer with an arbitrary precision. The main theorem is the following: There exists a parameter value \(c\in\mathbb{C}\) such that the Julia set of the quadratic polynomial \(f_c(z)=z^2+c\) is not computable.
Reviewer: Pei-Chu Hu (Jinan)

MSC:
37F50 Small divisors, rotation domains and linearization in holomorphic dynamics
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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. · Zbl 0872.68036
[2] Artur Avila, Xavier Buff, and Arnaud Chéritat, Siegel disks with smooth boundaries, Acta Math. 193 (2004), no. 1, 1 – 30. · Zbl 1076.37030 · doi:10.1007/BF02392549 · doi.org
[3] I. Binder, M. Braverman, M. Yampolsky. Filled Julia sets with empty interior are computable, e-print math.DS/0410580 at Arxiv.org. · Zbl 1160.37013
[4] I. Binder, M. Braverman, M. Yampolsky. On computational complexity of Siegel Julia sets, Commun. Math. Physics, to appear. · Zbl 1233.68138
[5] Errett Bishop and Douglas Bridges, Constructive analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 279, Springer-Verlag, Berlin, 1985. · Zbl 0656.03042
[6] 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).
[7] M. Braverman, Parabolic Julia sets are polynomial time computable. e-print math.DS/0505036 at Arxiv.org. · Zbl 1190.37049
[8] A. D. Brjuno, Analytic form of differential equations. I, II, Trudy Moskov. Mat. Obšč. 25 (1971), 119 – 262; ibid. 26 (1972), 199 – 239 (Russian).
[9] X. Buff, A. Chéritat, Quadratic Siegel disks with smooth boundaries. Preprint Univ. Paul Sabatier, Toulouse, III, Num. 242. · Zbl 1076.37030
[10] X. Buff, A. Chéritat, The Yoccoz function continuously estimates the size of Siegel disks, Annals of Math., to appear.
[11] 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. · Zbl 0934.30023 · doi:10.1090/psapm/049/1315535 · doi.org
[12] 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). 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. 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). 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.
[13] 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. · Zbl 0587.30028
[14] A. Grzegorczyk, Computable functionals, Fund. Math. 42 (1955), 168 – 202. · Zbl 0066.26001
[15] Ker-I Ko, Complexity theory of real functions, Progress in Theoretical Computer Science, Birkhäuser Boston, Inc., Boston, MA, 1991. · Zbl 0791.03019
[16] 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. · Zbl 0938.03090 · doi:10.1016/S0049-237X(98)80052-9 · doi.org
[17] 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). 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). · Zbl 0065.00201
[18] S. Mazur, Computable analysis, Rozprawy Mat. 33 (1963), 110. · Zbl 0113.24306
[19] S. Marmi, P. Moussa, and J.-C. Yoccoz, The Brjuno functions and their regularity properties, Comm. Math. Phys. 186 (1997), no. 2, 265 – 293. · Zbl 0947.30018 · doi:10.1007/s002200050110 · doi.org
[20] Десятая проблема Гил\(^{\приме}\)берта, Математическая Логика и Основания Математики [Монограпхс ин Матхематицал Логиц анд Фоундатионс оф Матхематицс], вол. 26, ВО ”Наука”, Мосцощ, 1993 (Руссиан, щитх Руссиан суммары). Юри В. Матиясевич, Хилберт’с тентх проблем, Фоундатионс оф Цомпутинг Сериес, МИТ Пресс, Цамбридге, МА, 1993. Транслатед фром тхе 1993 Руссиан оригинал бы тхе аутхор; Щитх а форещорд бы Мартин Давис.
[21] Curtis T. McMullen, Complex dynamics and renormalization, Annals of Mathematics Studies, vol. 135, Princeton University Press, Princeton, NJ, 1994. · Zbl 0807.30013
[22] John Milnor, Dynamics in one complex variable, Friedr. Vieweg & Sohn, Braunschweig, 1999. Introductory lectures. · Zbl 0946.30013
[23] 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. · Zbl 1069.37038 · doi:10.4007/annals.2004.159.1 · doi.org
[24] Ch. Pommerenke, Boundary behaviour of conformal maps, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 299, Springer-Verlag, Berlin, 1992. · Zbl 0762.30001
[25] 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).
[26] 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. · Zbl 1192.68375 · doi:10.1145/780542.780570 · doi.org
[27] Steffen Rohde and Michel Zinsmeister, Variation of the conformal radius, J. Anal. Math. 92 (2004), 105 – 115. · Zbl 1070.30001 · doi:10.1007/BF02787758 · doi.org
[28] Carl Ludwig Siegel, Iteration of analytic functions, Ann. of Math. (2) 43 (1942), 607 – 612. · Zbl 0061.14904 · doi:10.2307/1968952 · doi.org
[29] M. Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. · Zbl 1169.68300
[30] A. M. Turing, On Computable Numbers, With an Application to the Entscheidungsproblem. In Proceedings, London Mathematical Society, 1936, pp. 230-265. · Zbl 0016.09701
[31] Klaus Weihrauch, Computable analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000. An introduction. · Zbl 0956.68056
[32] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.