Computability of the Julia set. Nonrecurrent critical orbits

Artem Dudko

doi:10.3934/dcds.2014.34.2751

Article Contents

2014, Volume 34, Issue 7: 2751-2778. Doi: 10.3934/dcds.2014.34.2751

This issue Previous Article Rank as a function of measure Next Article On the characterization of $p$-harmonic functions on the Heisenberg group by mean value properties

Computability of the Julia set. Nonrecurrent critical orbits

Artem Dudko^1,

1.
Institute for Mathematical Sciences, Stony Brook University, Stony Brook, NY, 11794-3660

Received: June 2012

Revised: September 2013

Published online: December 2013

Abstract / Introduction Related Papers Cited by

Abstract

We prove, that the Julia set of a rational function $f$ is computable in polynomial time, assuming that the postcritical set of $f$ does not contain any critical points or parabolic periodic orbits.

Keywords:

Mathematics Subject Classification: Primary: 37F50, 37F10; Secondary: 03F60.

Citation:

Related Papers

Cited by

References

[1]	M. Aspenberg, The Collet-Eckmann condition for rational functions on the Riemann sphere, Math. Z., 273 (2013), 935-980.doi: 10.1007/s00209-012-1039-3.
[2]	A. Avila and C. G. Moreira, Statistical properties of unimodal maps: The quadratic family, Ann. of Math. (2), 161 (2005), 831-881.doi: 10.4007/annals.2005.161.831.
[3]	I. Binder, M. Braverman and M. Yampolsky, On computational complexity of Siegel Julia sets, Commun. Math. Phys., 264 (2006), 317-334.doi: 10.1007/s00220-006-1546-3.
[4]	I. Binder, M. Braverman and M. Yampolsky, Filled Julia sets with empty interior are computable, Found. Comput. Math., 7 (2007), 405-416.doi: 10.1007/s10208-005-0210-1.
[5]	M. Braverman and M. Yampolsky, Constructing locally connected non-computable Julia sets, Commun. Math. Phys., 291 (2009), 513-532.doi: 10.1007/s00220-009-0858-5.
[6]	M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Master's thesis, University of Toronto, 2004.
[7]	M. Braverman, Parabolic Julia sets are polynomial time computable, Nonlinearity, 19 (2006), 1383-1401.doi: 10.1088/0951-7715/19/6/009.
[8]	M. Braverman and M. Yampolsky, Non-computable Julia sets, J. Amer. Math. Soc., 19 (2006), 551-578.doi: 10.1090/S0894-0347-05-00516-3.
[9]	M. Braverman and M. Yampolsky, Computability of Julia Sets, Algorithms and Computation in Mathematics, 23, Springer-Verlag, Berlin, 2009.
[10]	J. B. Conway, Functions of One Complex Variable. II, Graduate Texts in Mathematics, 159, Springer-Verlag, New York, 1995.doi: 10.1007/978-1-4612-0817-4.
[11]	J. Graczyk and G. Światek, Generic hyperbolicity in the logistic family, Ann. of Math. (2), 146 (1997), 1-52.doi: 10.2307/2951831.
[12]	M. Lyubich, Dynamics of quadratic polynomials. I, II, Acta Math., 178 (1997), 185-247, 247-297.doi: 10.1007/BF02392694.
[13]	R. Mañé, On a theorem of Fatou, Bol. Soc. Bras. Mat. (N.S.), 24 (1993), 1-11.doi: 10.1007/BF01231694.
[14]	J. Milnor, Dynamics in One Complex Variable, Third edition, Annals of Mathematics Studies, 160, Princeton University Press, Princeton, NJ, 2006.
[15]	C. M. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.
[16]	R. Rettinger, A fast algorithm for Julia sets of hyperbolic rational functions, in Proceedings of the 6th Workshop on Computability and Complexity in Analysis (CCA 2004), Electr. Notes Theor. Comput. Sci., 120, Elsevier, Amsterdam, 2005, 145-157.doi: 10.1016/j.entcs.2004.06.041.
[17]	M. Shishikura and T. Lei, An alternative proof of Mañé's theorem on non-expanding Julia sets, in The Mandelbrot set, Theme and Variations (ed. T. Lei), London Math. Soc. Lect. Note Ser., 274, Cambridge Univ. Press, Cambridge, 2000, 265-279.doi: 10.1017/CBO9780511569159.014.
[18]	M. Sipser, Introduction to the Theory of Computation, Second edition, PWS Publishing Company, Boston, 2005.doi: 10.1145/230514.571645.
[19]	H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Z., 20 (1924), 131-150.doi: 10.1007/BF01188076.