July  2014, 34(7): 2751-2778. doi: 10.3934/dcds.2014.34.2751

Computability of the Julia set. Nonrecurrent critical orbits

1. 

Institute for Mathematical Sciences, Stony Brook University, Stony Brook, NY, 11794-3660, United States

Received  June 2012 Revised  September 2013 Published  December 2013

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.
Citation: Artem Dudko. Computability of the Julia set. Nonrecurrent critical orbits. Discrete & Continuous Dynamical Systems, 2014, 34 (7) : 2751-2778. doi: 10.3934/dcds.2014.34.2751
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Master's thesis, University of Toronto, 2004. Google Scholar

[7]

M. Braverman, Parabolic Julia sets are polynomial time computable, Nonlinearity, 19 (2006), 1383-1401. doi: 10.1088/0951-7715/19/6/009.  Google Scholar

[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.  Google Scholar

[9]

M. Braverman and M. Yampolsky, Computability of Julia Sets, Algorithms and Computation in Mathematics, 23, Springer-Verlag, Berlin, 2009.  Google Scholar

[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.  Google Scholar

[11]

J. Graczyk and G. Światek, Generic hyperbolicity in the logistic family, Ann. of Math. (2), 146 (1997), 1-52. doi: 10.2307/2951831.  Google Scholar

[12]

M. Lyubich, Dynamics of quadratic polynomials. I, II, Acta Math., 178 (1997), 185-247, 247-297. doi: 10.1007/BF02392694.  Google Scholar

[13]

R. Mañé, On a theorem of Fatou, Bol. Soc. Bras. Mat. (N.S.), 24 (1993), 1-11. doi: 10.1007/BF01231694.  Google Scholar

[14]

J. Milnor, Dynamics in One Complex Variable, Third edition, Annals of Mathematics Studies, 160, Princeton University Press, Princeton, NJ, 2006.  Google Scholar

[15]

C. M. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

M. Sipser, Introduction to the Theory of Computation, Second edition, PWS Publishing Company, Boston, 2005. doi: 10.1145/230514.571645.  Google Scholar

[19]

H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Z., 20 (1924), 131-150. doi: 10.1007/BF01188076.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

M. Braverman, Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable, Master's thesis, University of Toronto, 2004. Google Scholar

[7]

M. Braverman, Parabolic Julia sets are polynomial time computable, Nonlinearity, 19 (2006), 1383-1401. doi: 10.1088/0951-7715/19/6/009.  Google Scholar

[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.  Google Scholar

[9]

M. Braverman and M. Yampolsky, Computability of Julia Sets, Algorithms and Computation in Mathematics, 23, Springer-Verlag, Berlin, 2009.  Google Scholar

[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.  Google Scholar

[11]

J. Graczyk and G. Światek, Generic hyperbolicity in the logistic family, Ann. of Math. (2), 146 (1997), 1-52. doi: 10.2307/2951831.  Google Scholar

[12]

M. Lyubich, Dynamics of quadratic polynomials. I, II, Acta Math., 178 (1997), 185-247, 247-297. doi: 10.1007/BF02392694.  Google Scholar

[13]

R. Mañé, On a theorem of Fatou, Bol. Soc. Bras. Mat. (N.S.), 24 (1993), 1-11. doi: 10.1007/BF01231694.  Google Scholar

[14]

J. Milnor, Dynamics in One Complex Variable, Third edition, Annals of Mathematics Studies, 160, Princeton University Press, Princeton, NJ, 2006.  Google Scholar

[15]

C. M. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Reading, MA, 1994.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

M. Sipser, Introduction to the Theory of Computation, Second edition, PWS Publishing Company, Boston, 2005. doi: 10.1145/230514.571645.  Google Scholar

[19]

H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Z., 20 (1924), 131-150. doi: 10.1007/BF01188076.  Google Scholar

[1]

François Berteloot, Tien-Cuong Dinh. The Mandelbrot set is the shadow of a Julia set. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6611-6633. doi: 10.3934/dcds.2020262

[2]

Ronnie Pavlov, Pascal Vanier. The relationship between word complexity and computational complexity in subshifts. Discrete & Continuous Dynamical Systems, 2021, 41 (4) : 1627-1648. doi: 10.3934/dcds.2020334

[3]

Luke G. Rogers, Alexander Teplyaev. Laplacians on the basilica Julia set. Communications on Pure & Applied Analysis, 2010, 9 (1) : 211-231. doi: 10.3934/cpaa.2010.9.211

[4]

Koh Katagata. On a certain kind of polynomials of degree 4 with disconnected Julia set. Discrete & Continuous Dynamical Systems, 2008, 20 (4) : 975-987. doi: 10.3934/dcds.2008.20.975

[5]

Volodymyr Nekrashevych. The Julia set of a post-critically finite endomorphism of $\mathbb{PC}^2$. Journal of Modern Dynamics, 2012, 6 (3) : 327-375. doi: 10.3934/jmd.2012.6.327

[6]

Rich Stankewitz. Density of repelling fixed points in the Julia set of a rational or entire semigroup, II. Discrete & Continuous Dynamical Systems, 2012, 32 (7) : 2583-2589. doi: 10.3934/dcds.2012.32.2583

[7]

Yu-Hao Liang, Wan-Rou Wu, Jonq Juang. Fastest synchronized network and synchrony on the Julia set of complex-valued coupled map lattices. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 173-184. doi: 10.3934/dcdsb.2016.21.173

[8]

Andrea Bonito, Roland Glowinski. On the nodal set of the eigenfunctions of the Laplace-Beltrami operator for bounded surfaces in $R^3$: A computational approach. Communications on Pure & Applied Analysis, 2014, 13 (5) : 2115-2126. doi: 10.3934/cpaa.2014.13.2115

[9]

Silvère Gangloff, Benjamin Hellouin de Menibus. Effect of quantified irreducibility on the computability of subshift entropy. Discrete & Continuous Dynamical Systems, 2019, 39 (4) : 1975-2000. doi: 10.3934/dcds.2019083

[10]

Stefano Galatolo, Mathieu Hoyrup, Cristóbal Rojas. Dynamics and abstract computability: Computing invariant measures. Discrete & Continuous Dynamical Systems, 2011, 29 (1) : 193-212. doi: 10.3934/dcds.2011.29.193

[11]

Marcin Mazur, Jacek Tabor. Computational hyperbolicity. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 1175-1189. doi: 10.3934/dcds.2011.29.1175

[12]

Guizhen Cui, Wenjuan Peng, Lei Tan. On the topology of wandering Julia components. Discrete & Continuous Dynamical Systems, 2011, 29 (3) : 929-952. doi: 10.3934/dcds.2011.29.929

[13]

Silvére Gangloff, Alonso Herrera, Cristobal Rojas, Mathieu Sablik. Computability of topological entropy: From general systems to transformations on Cantor sets and the interval. Discrete & Continuous Dynamical Systems, 2020, 40 (7) : 4259-4286. doi: 10.3934/dcds.2020180

[14]

Stefano Galatolo. Orbit complexity and data compression. Discrete & Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477

[15]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299

[16]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

[17]

Koh Katagata. Quartic Julia sets including any two copies of quadratic Julia sets. Discrete & Continuous Dynamical Systems, 2016, 36 (4) : 2103-2112. doi: 10.3934/dcds.2016.36.2103

[18]

Luiz Henrique de Figueiredo, Diego Nehab, Jorge Stolfi, João Batista S. de Oliveira. Rigorous bounds for polynomial Julia sets. Journal of Computational Dynamics, 2016, 3 (2) : 113-137. doi: 10.3934/jcd.2016006

[19]

Robert L. Devaney, Daniel M. Look. Buried Sierpinski curve Julia sets. Discrete & Continuous Dynamical Systems, 2005, 13 (4) : 1035-1046. doi: 10.3934/dcds.2005.13.1035

[20]

Danilo Antonio Caprio. A class of adding machines and Julia sets. Discrete & Continuous Dynamical Systems, 2016, 36 (11) : 5951-5970. doi: 10.3934/dcds.2016061

2020 Impact Factor: 1.392

Metrics

  • PDF downloads (45)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]