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 - A, 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. 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. 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. 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. 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. 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, (2004).

[7]

M. Braverman, Parabolic Julia sets are polynomial time computable,, Nonlinearity, 19 (2006), 1383. 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. doi: 10.1090/S0894-0347-05-00516-3.

[9]

M. Braverman and M. Yampolsky, Computability of Julia Sets,, Algorithms and Computation in Mathematics, (2009).

[10]

J. B. Conway, Functions of One Complex Variable. II,, Graduate Texts in Mathematics, (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. doi: 10.2307/2951831.

[12]

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

[13]

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

[14]

J. Milnor, Dynamics in One Complex Variable,, Third edition, (2006).

[15]

C. M. Papadimitriou, Computational Complexity,, Addison-Wesley Publishing Company, (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), (2004), 145. 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, (2000), 265. doi: 10.1017/CBO9780511569159.014.

[18]

M. Sipser, Introduction to the Theory of Computation,, Second edition, (2005). doi: 10.1145/230514.571645.

[19]

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

show all references

References:
[1]

M. Aspenberg, The Collet-Eckmann condition for rational functions on the Riemann sphere,, Math. Z., 273 (2013), 935. 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. 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. 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. 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. 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, (2004).

[7]

M. Braverman, Parabolic Julia sets are polynomial time computable,, Nonlinearity, 19 (2006), 1383. 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. doi: 10.1090/S0894-0347-05-00516-3.

[9]

M. Braverman and M. Yampolsky, Computability of Julia Sets,, Algorithms and Computation in Mathematics, (2009).

[10]

J. B. Conway, Functions of One Complex Variable. II,, Graduate Texts in Mathematics, (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. doi: 10.2307/2951831.

[12]

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

[13]

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

[14]

J. Milnor, Dynamics in One Complex Variable,, Third edition, (2006).

[15]

C. M. Papadimitriou, Computational Complexity,, Addison-Wesley Publishing Company, (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), (2004), 145. 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, (2000), 265. doi: 10.1017/CBO9780511569159.014.

[18]

M. Sipser, Introduction to the Theory of Computation,, Second edition, (2005). doi: 10.1145/230514.571645.

[19]

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

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Peter Giesl, Sigurdur Hafstein. Computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : i-ii. doi: 10.3934/dcdsb.2015.20.8i

[13]

Shu Liao, Jin Wang, Jianjun Paul Tian. A computational study of avian influenza. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1499-1509. doi: 10.3934/dcdss.2011.4.1499

[14]

Nur Aidya Hanum Aizam, Louis Caccetta. Computational models for timetabling problem. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 269-285. doi: 10.3934/naco.2014.4.269

[15]

Ian H. Dinwoodie. Computational methods for asynchronous basins. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3391-3405. doi: 10.3934/dcdsb.2016103

[16]

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

[17]

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

[18]

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

[19]

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

[20]

Nathaniel D. Emerson. Dynamics of polynomials with disconnected Julia sets. Discrete & Continuous Dynamical Systems - A, 2003, 9 (4) : 801-834. doi: 10.3934/dcds.2003.9.801

2017 Impact Factor: 1.179

Metrics

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

Other articles
by authors

[Back to Top]