Arnaud Ch Éritat
email: arnaud.cheritat@math.univ-toulouse.fr

BRAVERMAN AND YAMPOLSKY: COMPUTABILITY OF JULIA SETS ALGORITHMS AND COMPUTATIONS IN MATHEMATICS VOLUME 23, SPRINGER

This notion of degree coincides with the

Introduction

Most of us have seen computer generated pictures of Julia sets. They are fractal compact subsets of the plane of complex numbers, generated by the iteration of polynomials with complex coefficients, or of rational maps, or other holomorphic maps. There is a great variety of Julia sets and there is a great variety of ways of illustrating a single one. Color pictures certainly have an aesthetic aspect, notwithstanding the fact that the color scheme is often chosen so as to have a meaning in terms of the underlying dynamical system. Black and white pictures usually show the Julia set itself, which is closed: it is the place where the dynamical system is chaotic. For some rational maps, it is quickly drawn. For others, the known algorithms are very slow. There are even some for which no convincing pictures has ever been produced, like those with a Cremer point 1 . Braverman and Yampolsky have studied the theoretical aspects of the computability of Julia sets of rational maps, as functions of the parameter, and the complexity of this computation: for instance they proved that there are polynomials whose coefficients are computable but whose Julia sets are non-computable, and some others that are arbitrarily hard to compute. Their results are interesting in that they may contradict the naive intuition of those familiar with complex dynamics: they proved the computability 1 see the definition in further sections of some Julia sets with Cremer points, which are not well understood, and noncomputability of some other Julia sets that nevertheless possess a nice and well understood locally connected topological model.

Julia sets

We will restrict the discussion to rational maps and later focus on polynomials. Classical introductions to the topic include [START_REF] Beardon | Quadratic Julia sets with positive area[END_REF], [START_REF] Carleson | Complex Dynamics. Universitext: Tracts in Mathematics[END_REF], [START_REF] Milnor | Dynamics in One Complex Variable[END_REF], [START_REF] Morosawa | Holomorphic dynamics[END_REF], Steinmetz [1993], alphabetically sorted.

A rational map is a quotient of two polynomials: R(z) = P (z)/Q(z). It gives a well defined map from the Riemann sphere C = C∪{∞} to itself. There is a integer number d, called the degree 2 of R, such that all but finitely many points in C have exactly d preimages by R. If the fraction P/Q is in its lowest terms, i.e. there is no common root between P and Q, then deg(R) = max(deg(P ), deg(Q)). Moreover, all points z ∈ C have exactly d preimages if we count them with multiplicity. The multiplicity m of a point w is the local degree of R near the w: there are local changes of variable φ, ψ mapping respectively w to 0 and R(w) to 0 and such that ψ • R • φ -1 (z) = z m holds near 0. The critical points are the points where the derivative of R vanishes (if z or R(z) is ∞ then a change of variable must be used to check this). There are 2d -2 critical points, counted with multiplicity, where the multiplicity of a critical point is the multiplicity of z as a solution of R (z) = 0, and it is also equal to one subtracted from the local degree of R at z.

To a rational map R is associated a discrete dynamical system, i.e. from an initial point z 0 in the Riemann sphere C = C ∪ {∞}, one defines a sequence inductively by

z n+1 = R(z n ). Then z n = R n (z 0 ) where R n = R • • • • • R denotes the n-th iterate of R.
A periodic point is a z ∈ C such that R n (z) = z for some n > 0. Its period p is the minimal value of n. Its multiplier is the quantity λ = (R p ) (z). It is invariant under an analytic change of variable of the form φ

• R • φ -1 . The periodic point is called repelling if |λ| > 1, attracting if |λ| < 1, neutral (or indifferent) if |λ| = 1
and superattracting if |λ| = 0 (which we choose to consider as a particular case of attracting points).

The Julia set J(R) of a rational map has two equivalent definitions. First it is the complement of the Fatou set, which is the set of points which have a neighborhood where the sequence of iterates R n form an equicontinuous family. The Julia set is also and more simply the closure of the set of repelling periodic points of R. These definitions and their equivalence are part of the founding works of Fatou and Julia in the early 20 th century: Julia [1918], Fatou [1917a,b]. From the second definition follows at once that J(R n ) = J(R) for n ≥ 1.

From now on, we will restrict to rational maps of degree at least 2. Then the Julia set is a nonempty compact subset of the plane, and it is perfect (there is no isolated point). Theorem. Every periodic Fatou component is of one of the following types:

• The immediate basin of an attracting periodic point.

• The immediate basin of a petal of a parabolic periodic point.

• A rotation domain: a Siegel disk or a Herman ring.

The terminology used in this theorem has to be explained. The set of iterates R n (z) of a given point z is called its orbit. The orbit of a periodic point is called a cycle. Every point in a cycle has the same multiplier. The set of points tending to a given attracting cycle is open and nonempty and called its basin. The connected component of a basin containing a given point in the cycle is called the immediate basin of this point. A parabolic periodic point is one whose multiplier is a root of unity. Since the degree of R is at least 2, one can prove that parabolic points must belong to the Julia set. Yet, locally, a parabolic point still attracts a finite number of large connected open regions attached to it, called petals. Petals are stable3 under some iterate R m of R (with m ≥ 1). These regions are separated by fjords where points are repelled from the parabolic point. Each petal is contained in the Fatou set and the connected component of the Fatou set containing a given petal is called its immediate basin. A Siegel disk is a simply connected component of the Fatou set where the dynamics of an iterate of R is conjugated to a rotation. A Herman ring is the same but for an open region homeomorphic to an annulus. Immediate basins and rotation domains are subsets of the Fatou set.

The following theorem was proved much later, by Sullivan: [START_REF] Sullivan | Itération des fonctions analytiques complexes[END_REF][START_REF] Sullivan | Quasiconformal homeomorphisms and dynamics. I. Solution of the Fatou-Julia problem on wandering domains[END_REF] Theorem [START_REF] Sullivan | Itération des fonctions analytiques complexes[END_REF]. Every Fatou component is eventually periodic.

Which means that one of its iterates is periodic. This theorem is often referred to as the no wandering domain theorem. In other words, the union of all attracting and parabolic basins and all iterated preimages of rotation domains is the whole Fatou set. The main tool of the proof is quasiconformal deformations. It is an adaptation to rational maps of the Ahlfors finiteness theorem in the domain of Kleinian groups. These two domains have many similarities.

When the rational map is a polynomial, then there is a third well known equivalent definition of the Julia set, as the boundary of the filled-in Julia set, that we will now define. First note that since R is a polynomial and has degree at least 2, infinity is fixed and super attracting. Using the maximum principle one can prove that the basin of infinity, i.e. the set of points attracted to infinity, is connected. Its complement is thus called the filled-in Julia set because it is the union of the Julia set and of all the bounded connected components of its complement. The filled-in Julia set of the polynomial P is denoted K(P ).

There are many other definitions of the Julia set. For instance, it is the support of the unique measure of maximal entropy (a.k.a. the Brolin-Lyubich measure).

A rational map is hyperbolic when it is repelling on its Julia set in the following sense: identify 4 C with a euclidean 2-sphere, and let R be hyperbolic whenever there exists an iterate R n such that the infimum over z ∈ J(R) of the norm of the differential of R n is > 1. Hyperbolicity does not depend on the identification; changing it just changes the valid values of n. There is one very striking classical result of Fatou:

Theorem. A rational map of degree ≥ 2 is hyperbolic if and only if all critical orbits tend to attracting cycles.

Let us focus again on periodic points of rational maps: we have seen that if the multiplier λ satisfies |λ| < 1 then the periodic point z belongs to the Fatou set and attracts nearby points, that if |λ| > 1 then it belongs to the Julia set, and that if λ is a root of unity and deg(R) > 1 then it also belongs to the Julia set, attracts big nearby domains called petals and repels between them. What if |λ| = 1 but λ is not a root of unity? Let us write λ = e 2πiθ with θ ∈ R -Q which is called the rotation number. If there exists a local change of variable for which the map becomes a rotation, we will say that the periodic point is linearizable. If not, it will be called a Cremer point. The question of linearizability turns out to be a subtle one.

• Pfeiffer, around 1917, proved the existence of maps with non-linearizable fixed points with irrational rotation number. • Cremer, around 1927, found for all d ≥ 2 an explicit condition on θ, sufficient for polynomial of degree d to be non-linearizable. • The first results in the opposite direction occurred only in 1942, when Siegel proved in an major article that there exist rotation numbers for which all maps are linearizable: diophantine numbers. • Brjuno and independently Rüssman, in the 1960's, found a more general class of rotation numbers for which this is the case. • The last step is when Yoccoz proved in the late 1980's that this condition is optimal, and that for the other irrational rotation numbers, the polynomial P θ (z) = e 2πiθ z + z 2 is not linearizable at the origin. This is of course not the end of the story. For instance Douady conjectured that a linearizable periodic point of a rational map (of degree at least 2) necessarily has a rotation number satisfying Brjuno's condition. This question is still open today.

The number of non-repelling cycles is always bounded: Fatou) there are at most 4d -4 non-repelling cycles,

Theorem. If the rational map R has degree d ≥ 2, then • (
• (Shishikura) the sharp bound is 2d -2.
The most extensively studied family of rational maps is the family of quadratic polynomials: P c (z) = z 2 +c. Every polynomial of degree 2 is conjugated to a unique P c by a complex affine map z → az + b. It can have at most one repelling cycle. Note that if this cycle is of Cremer type (i.e. neutral but neither parabolic nor linearizable) then by the classification of components, the only Fatou component is the basin of infinity (which we recall is connected) and thus K(P ) = J(P ).

The notion of computability

Most readers of this journal are likely to be familiar with the notion of computability and they can skip the present section. For the others, let us warn that we will be a bit vague here.

A sequence of integers is said to be computable if there is a finite computer program able to compute these numbers. There is no bound on the amount of memory or time available to the program. 5 A completely rigorous treatment of these notions is given by Turing machines, but this is out of the scope of the present review.

Since the set of all integer sequences is uncountable and the set of all finite programs is countable, it means that most integer sequences are not computable. On the other hand, many sequences we are familiar with are computable, and usually their definition provides the algorithm for computing them.

A computable subset of the integers is just a set whose characteristic function is computable, i.e. there is a program which for all input n stops and outputs 1 if n is in the set and 0 if not. One fascinating feature is that is possible to explicitly and unambiguously define sets that are not computable (this is related to the halting problem).

The data of a real number is equivalent to the data of its (proper) decimal expansion, so it is tempting to define a computable real number as one whose decimal expansion is a computable sequence. This is correct but contains subtle aspects. 6 The two following definitions of a computable real number x are equivalent:

(1) the proper decimal expansion of x is computable, (2) there exists a program with input an integer n and output a rational number

x n with |x n -x| < 1/10 n .

In particular, computability does not depend on the base chosen, decimal, binary, etc. . . The first definition is more straightforward but the second one is more reasonable.

Many usual mathematical constants like e (the basis of Napier's natural logarithm), the constant π, Feigenbaum's constant δ, all algebraic numbers, etc. . . are computable.

Remark. It is important to note that if x is a real number and if there exists some program with input n ≥ 0 and output a rational x n , and if moreover x n -→ x as n -→ +∞, this does not imply that x is computable: the definition of computability includes a control on the distance from x to its approximation x n , and there 5 More precisely the program has an input and an output. When an integer n is given as an input, then the output should be the term un of the sequence. The machine is also supposed to halt once it has given the output. For this definition to be sensible, one must allow for arbitrarily large integers n as an input, because all finite sequences are computable: just encode the values of the sequence within the program and let the latter retrieve them. Note that integers are encoded for instance by their decimal or their binary expansion: this means that larger integers take more memory to encode and more time to handle.

6 Consider for instance the Euler-Mascheroni constant γ. It is not known if it is rational or not. But an algorithm for computing approximations exists, with an error bound. More precisely, there exists a program with input an integer n and output a decimal (or binary or rational, etc. . . ) real number xn with |xn -γ| < 1/10 n . If γ is irrational, or is rational but not decimal, then this algorithm can be used to write another algorithm providing the decimals of the number. If γ is a decimal rational, then there also exists an algorithm giving the decimals, but it does not use the original one: since every rational has an eventually periodic decimal expansion, the initial segment and the periodic part of the sequence of its decimals can be encoded within a program. Therefore we know that the decimals of γ are computable, event if we do not know which program will do it! indeed exist non-computable numbers that are limits of programmable sequences of rationals. 7

4. Computability of a compact subset of the plane

We switch to base 2 to stay closer to the book. The plane is identified both with R 2 and with the set of complex numbers C and its elements will be often denoted as z.

The definition of a computable compact subset of the plane is similar to the second definition of a computable real number. On the set C of all nonempty compact subsets of the plane is defined the Hausdorff distance as follows:

d(K, L) = max(δ(K, L), δ(L, K)) where δ(K, L) = sup z∈K d(z, L) d(z, L) = inf w∈L d(z, w).
Another definition of δ is the following:

δ(K, L) = inf ε > 0 K ⊂ L + B(0, ε) .
where L + B(0, ε) = z + w z ∈ L and |w| < ε is also the ε neighborhood of L, i.e. the set of all points at distance < ε of L.

Let F be the collection of finite sets of points with rational coefficients. Then F is a dense subset of C. An element C of C is called computable if there exists a program which on input n outputs some C n ∈ F, such that d(C n , C) < 1/2 n . An encoding of these finite sets must be fixed in advance but the notion of computability will not depend on it.

Dyadic numbers are rational numbers of the form k/2 n with k ∈ Z. They are thus represented on computers by a pair of integers. 8 An equivalent definition of computability for compact subsets of the plane, slightly closer to the behavior of actual programs used to produce pictures of Julia sets, is the following: choose a real b > 1. Call C computable if and only if there exists a program such that:

(1) the input is dyadic numbers x, y and r (2) on each input r > 0 and x, y the program stops and outputs (where z =

x + iy):

1 if d(z, C) < r, 0 if d(z, C) > br, either 0 or 1 otherwise.
This is reminiscent of distance estimator algorithms. The actual value b is not important as long as b > 1, since a computable compact for some b with some algorithm is computable for any other b > 1 with another algorithm which uses the first one. One possible proof uses the equivalence with "z → d(z, C) is computable" (see the next section).

As a simple yet instructive example, let z = x + iy be a point in the plane. The set {z} is computable if and only if both coordinates x and y are computable. 7 The set of real numbers satisfying this weaker definition is still countable. 8 It is not necessary to have a unique representation of objects as long as one can program a comparison function: for instance k/2 n = l/2 m iff 2 m k = 2 n l.

Computability of functions

This notion is a bit subtle and may not match first intuition. We first need to introduce oracles. Consider a real variable x ( 9 ) and a sequence u n of dyadic numbers such that |x -u n | ≤ 1/2 n . An algorithm/program/Turing-machine with oracle access to x is the same as a standard program but it is allowed to query u n , i.e. it can call a special function φ(n), which is not computed by a Turing machine, that returns u n to the program. It can call it many times and with any value of n it has been able to compute so far. It is useful to imagine, though of course not necessary, and debatable, that φ is a function that asks a human user to type u n on a keyboard. For complexity considerations, one should require moreover that the size of the encoding of u n is O(n). Typically one could require u n to be of the form p/2 n where p is an integer. 10 Let S be any subset of R. A function f from S to R is computable if there exists an algorithm with oracle access to x that for all value of x ∈ S, given n outputs a 2 -n dyadic approximation of f (x), i.e. some y = p/2 q such that |f (x) -y| < 2 -n . ( 11) If f is defined on a bigger set than S we say it is computable on S if its restriction to S is computable.

One consequence of this definition is that computable functions are continuous! And if f is computable on S then the restriction of f to S is continuous.

For instance, the step function

H : R → R, H(x) = 0 if x < 0, H(x) = 1 if x > 0, H(0) = 1/2, is not computable on R but it is on R -{0}.
It may seem annoying at first, that such a simple and familiar function be non-computable. But it makes sense if we think in experimental terms. Assume we are given a real quantity x, for instance the result of a physical measure, which we can know only up to some approximation. Computing H(x) amounts to determining whether x is positive, negative, or 0. How are we ever going to know that x = 0 if we can only get finite approximations of x? This information, that x = 0 or not, must be given in addition. On the opposite, if we are sure for some reason that x = 0, then we know that if we measure it finely enough, we will know its sign.

Let x 0 and y 0 be real numbers. Saying that the function defined on S = {x 0 } with value y 0 is computable is the same as saying that there is exists an algorithm with an oracle φ, that computes y 0 when φ gives approximations to x 0 .

There are still only countably many Programs/Turing-machines with the ability to call oracles.

The notion of computable functions extends to many other spaces, in particular to functions from R m to R n . For instance a nonempty compact subset

C of R m is computable if and only if the distance function R m → R, x → d(x, C) is computable.
One should be aware that programs for computing sets must give an output that is certified to be an approximation of the set up to a bound fixed by the user. Most actual programs found today for plotting Julia sets, if not all, do not bound the 9 it may also be a subset of the integers, or any infinite structure encodable by a sequence of finite structures un, together with a notion of approximation and an controlled bound on this approximation 10 I suppose this may be relaxed in some situations to un having an encoding length with an upper bound that is polynomial in n.

11 The program may ask for φ(k) for values of k bigger than n, in fact for any k it has been able to compute so far.

roundoff errors when manipulating approximations of real and complex numbers, nor is their output certified to be an approximation of the Julia set within some given error. Also, many of them draw a colour encoding of some potential functions in the Fatou set instead of the Julia set itself.

Computability of Julia sets

We will list here some of the most striking results proved in the book. They are cited almost faithfully: we just adapted here or there the vocabulary or the formulation for more uniformity in the review.

Theorem (3.1 page 39). For all d ≥ 2 there exists an algorithm with oracle access to the coefficients of a rational mapping of degree d which computes the Julia set of every hyperbolic rational map of degree d.

This means that the map R → J(R) is computable over S = the set of all hyperbolic rational maps of degree d. (12 ) In particular, if R has computable coefficients and is hyperbolic, then J(R) is computable: there is no need for an oracle since the coefficients can be computed inside the program. 13 We did not speak of complexity in the introduction but the algorithm computes J(R) in a reasonable time (see the next theorem).

To handle parabolic points, some supplementary information must be given to the algorithm: Theorem (3.16 page 59). Given

• a rational function R(z) such that every critical orbit of R converges to an attracting or a parabolic cycle; and • some finite combinatorial information about the parabolic cycles of R; there is an algorithm M that produces an image of the Julia set J(R). It takes M at most time C R • n c to decide one pixel in J(R) with precision 2 -n . Here c is some (small) constant and C R depends on R but not on n.

And M does not depend on R. Deciding a pixel refers to the second definition of computable subsets of R 2 we presented in §4: it is calling the program with supplementary inputs x, y, r, with r = 2 -n and x, y two dyadic numbers whose encoding is not much bigger than n, and the program is supposed to terminate and output 0 or 1 according to rules explained in §4. The combinatorial data include the number of parabolic cycles, their periods, rotation numbers and their number of petals. This information has to be known a priori because a program cannot determine whether an equality holds between quantities that depends on real or complex numbers given by oracles.

Another way to realize that a program cannot work without this information is based on the continuity of computable functions: there is a phenomenon, called parabolic implosion [START_REF] Douady | Does a Julia set depend continuously on the polynomial? In Complex dynamical systems[END_REF], that implies that R → J(R) is not continuous property), and one of the biggest conjectures in one-dimensional holomorphic dynamics is that it is dense: this is referred to as the Fatou conjecture.

13 It would not be reasonable to expect J(R) to be computable for all R, since there are uncountably many different Julia sets but only countably many programs. This is a bit analogous to the fact that the set {x} is computable if and only if x is computable, though it is trivially computable with oracle access to x for all x.

at rational maps R 0 with a parabolic cycle (and this holds even when R → J(R) is restricted to hyperbolic maps union {R 0 }). This has a consequence : since the function R → J(R) is not continuous on the set of all rational maps, there is no algorithm for computing all Julia sets, with oracle access to R. However, we will see that Braverman and Yampolsky have stronger negative results (the labelling does not reflect that of the book):

Theorem A (extracts of Chapter 5). There exist rational maps R whose Julia set is not computable by any algorithm even with oracle access to the coefficients of R. The map R can be chosen to be a quadratic polynomial, moreover with computable coefficients. 14In fact they give much more precise statements. But first let us state the following theorem, which in comparison of the previous one, may come as a surprise:

Theorem (4.1 page 65). For all polynomials P there exists an algorithm with oracle access to the coefficients of P that computes the filled-in Julia set K(P ). In other words, the function P → K(P ) is computable over {P 0 } for all P 0 .

Here also the statement hides subtleties: different polynomials require different algorithms. There is a countable yet infinite number of algorithms required. However one algorithm is sufficient if one allows for entering as an input a finite amount of supplementary information about P , like the number of parabolic cycles, the number of linearizable neutral cycles and of Cremer cycles, a way to locate them, and some other bits of information (finitely encodable).

So in the case of a quadratic polynomial like in Theorem A above, the filledin Julia set K(P ) is computable but not its boundary J(P ), which is a striking result. Also, consider a quadratic polynomial P with a Cremer point whose rotation number is computable (it exists), then K(P ) (which equals J(P )) is not locally connected and worse, no topological model is known; yet, it is computable.

A rational map R as in Theorem A necessarily has a Siegel disk or a Herman ring. Indeed, in Chapter 4, the following statement is proven: Theorem (4.5 page 69). Let R be a rational map without rotation domains. Then its Julia set is computable by an algorithm with oracle access to the coefficients of R. The algorithm requires information about the parabolic points as an input.

There is thus a close relationship between computability and rotation domains, and an important part of the book is devoted to unveiling it.

Conformal radius of Siegel disks and computability of Julia sets

To simplify things, the authors focus on the particular, yet archetypal, family of quadratic polynomials, and even more precisely on those that have a period one cycle with indifferent multiplier. Such a map is conjugated by a complex-affine map z → az + b to a unique P θ (z) = e 2πiθ z + z 2 with θ ∈ R. Let ∆ θ denote its Siegel disk if the fixed point z = 0 is linearizable and be the empty set otherwise. If ∆ θ = ∅ let the inner radius be the distance from 0 to its boundary ∂∆ θ and let the conformal radius be φ (0) where φ : B(0, 1) → ∆ θ is the unique conformal isomorphism mapping 0 to 0 and with real positive derivative at the origin.15

Theorem (Sections 4.3 and 5.2.1). Assume that the map P θ (z) = e 2πiθ z + z 2 has a Siegel disk. Then the following assertions are equivalent (where "w.o.a. θ" abbreviates "with oracle access to θ"):

• J(P θ ) is computable w.o.a. θ,
• the inner radius of the Siegel disk is computable w.o.a. θ,

• the conformal radius of the Siegel disk is computable w.o.a. θ.

A right-computable number is a real x such that there exists a program with input an integer n and output a rational number u n ∈ Q such that u n -→ x and such that u n is weakly decreasing: u n+1 ≤ u n . A left-computable real is defined analogously but with an increasing sequence. A real is computable iff it is both right and left computable. The connoisseur will have foreseen that non-computable yet right-computable real numbers can be constructed from the Halting Problem.

Theorem. Denote by r(θ) the conformal radius of the Siegel disk of P θ .

(1) There exist values of θ such that r(θ) is not computable w.o.a. θ.

(2) In fact, there exist computable values of θ such that r(θ) is not computable.

This implies (1) because an oracle access to a computable number is useless.

(3) Let r sup be the supremum of r(θ) over all θ. Then ∀r ∈ (0, r sup ),

(∃θ computable such that r(θ) = r) ⇐⇒ (r is right-computable). This implies (2) because there exist right-computable numbers which are not computable, and it is easy to see that they form a dense set in R.

Moreover, the authors also prove the existence of computable values of θ such that r(θ), hence J(P θ ), are computable, but with arbitrarily high complexity (complexity refers to the operating time of the Turing machine or program doing the computation).

Recall that a bounded type number is an irrational whose continued fraction expansion has a bounded sequence of entries. A lot of things have been proved by famous mathematicians on the Julia set of P θ when θ has bounded type. For instance the boundary of the Siegel disk ∆ θ is a Jordan curve, fractal but with controlled geometry: its Hausdorff dimension is strictly between 1 and 2, it is equal to the closure of the critical orbit, the Julia set is locally connected, has Hausdorff dimension < 2, the filled-in Julia set is deep near ∂∆ θ , there exists a simple homeomorphic model of J(P θ ), etc. . . Proposition (4.9 page 71). Let θ be of bounded type. Then J(P θ ) is computable by an algorithm using oracle access to θ, and an upper bound M on the entries of the continued fraction expansion of θ.

However, Braverman and Yampolsky also prove: Theorem (6.16 page 129). There exist values of θ such that J(P θ ) is locally connected (and we have an explicit homeomorphic model) but not computable even with oracle access to θ. 16 We have omitted in this short presentation many interesting other results presented in the book.

The book

The book is roughly self contained, a basic knowledge of complex analysis being the required background.

The first two chapters are introductions to the notion of computability and to the dynamics of rational mappings, mostly without proofs. They are written in an accessible way with many explications, examples and illustrations. The second one also includes related tools of complex analysis, like the uniformization theorem, the hyperbolic metric, and distortion bounds on univalent maps.

After this introduction begins the heart of the matter. Some of the results already appeared in previous works of the authors, while some are new. Most proofs are given in detail; some are only sketched, or easier parts are left to the reader.

The third chapter is about hyperbolic rational maps and the (larger) class of maps whose critical points all belong to attracting or parabolic basins. The proof of computability uses the fact that J(R) is the closure of the set of repelling orbits, which can be computed (as a function of R). It also uses a construction of computable open sets around the attracting cycles that trap orbits passing in them, and a construction of similar traps for parabolic cycles. By the classification of Fatou components, all points not in J eventually fall into these traps U under iteration of R. The proposed algorithm then computes simultaneously on one hand approximations of the union of more and more repelling orbits, and on the other hand approximations of the complement C -R -n (U ) of preimages of higher and higher order n. The first set is contained in the second and they are both compact. They will differ less and less as the program runs, and when it detects that their Hausdorff distance is small enough its stops and outputs either one. As the authors say, it is (roughly) an approximation of J from above and from below. All this can be made rigorous.

They also prove that there is an algorithm with whose complexity is polynomial in some sense. The proof is more subtle and much harder to read. It is based on Koebe's distortion theorem for hyperbolic maps, and moreover on an accelerator near parabolic points (i.e. a way to compute many iterates with few computations).

Chapter 3 ends with a discussion of some known results about the discontinuity of Julia set as a function of R (in particular parabolic implosion) and its implications on the computability of R → J(R).

Chapter 4 presents more positive results about computability: filled-in Julia sets of polynomials and Julia sets of rational maps without rotation domains. There is also the equivalence between computability of the Julia sets of some quadratic polynomials and computability of the conformal radius of the Siegel disk (they restrict the study to period one Siegel disks). They also prove computability when the rotation number has bounded type, using a quasiconformal model of the Julia set to bound the geometry of the Siegel disk, and the fact that its boundary is in this case the closure of the critical orbit. The chapter ends with a proof of the computability of the closure J of (z, c) ∈ C 2 z ∈ J(P c ) where P c (z) = z 2 + c. They relate this to robust computability and random iteration. 17

Chapter 5 is devoted to negative results. It begins with a discussion of some known results about Siegel disks and Cremer points in the quadratic family, that will be used in the rest of the chapter (and also some open conjectures which 17 These two subjects are similar to, but different from, the study of J . are likely to be true and that conditionally allows them to enhance some of their theorems).

It is followed by the equivalence between computability of J(z → e 2πiθ z +z 2 ) and of the conformal radius r(θ) of the Siegel disk (with the convention that r(θ) = 0 when there is no Siegel disk).

Then a careful study of the dependence on θ of r(θ), which is known to be very wild, is done with computability objectives in mind. Some of their results use the close relation between r(θ) and the Brjuno function

Φ(θ) = n≥0 θ 0 • • • θ n-1 log 1 θ n ,
which was introduced by Yoccoz, where the sequence θ n is given by Gauss's algorithm for continued fractions: θ 0 is the fractional part of θ and θ n+1 is the fractional part of θ n . See [START_REF] Yoccoz | Théorème de Siegel, nombres de Bruno et polynômes quadratiques[END_REF], who proved that the fixed point z = 0 of P θ (z) = e 2πiθ z + z 2 is linearizable if and only if B(θ) < ∞ (see Section 2 in the present review), [START_REF] Buff | The Brjuno function continuously estimates the size of quadratic Siegel disks[END_REF] where it is proved that ν : θ → log(r(θ)) + Φ(θ) has a continuous extension to the reals, and the conjecture in [START_REF] Marmi | The Brjuno functions and their regularity properties[END_REF] asserting that the previous function should be 1/2-Hölder continuous.

An interesting question would be to determine whether the corresponding results by Braverman and Yamposlky could be proved without the correspondence with Φ. Section 5.3.2 of the book is an interesting discussion of Cremer points. For a quadratic polynomial, recall that when there is a Cremer cycle, then J(P ) = K(P ) and thus J(P ) is computable with oracle access to θ. This is the case for instance for P (z) = e 2πiθ z + z 2 when θ is an irrational real number which does not satisfy Brjuno's arithmetic condition. But what about the complexity of this computation? It is known neither that there are cases where the computation can be done with low complexity, nor that there are cases with high complexity. It is remarkable that there does not exist today any convincing computer picture of a Cremer point. Another problem is that even if an image could be actually produced, it could be well possible that the Julia set would be composed of strands being so dense that near the Cremer point the image would look like a black area, indistinguishable from an open subset of the plane, and making the strands visible would require zooming to an impratical factor (10 10 10 for instance) or creating an image with a similar unachievable number of pixels.

Chapter 5 also includes two conditional sections: assuming that θ → ν(θ) has a computable modulus of continuity, then one section proves that J(z → e 2πiθ z + z 2 ) is computable when either θ or e 2πiθ is an algebraic number, and the second section proves that parameters c ∈ C such that J(z → z 2 +c) is not computable with oracle access to c and parameters θ such that J(z → e 2πiθ z + z 2 ) is not computable with oracle access to θ are rare: they form sets of zero Hausdorff dimension.

Chapter 6 is titled "Computability versus Topological Properties of Julia Sets". Section 6.1 proposes a toy example of a computable closed set whose boundary is not computable, based on the halting problem (more generally on some type of noncomputable predicates). The remaining sections focus on quadratic polynomials and deal with the notion of local connectedness: basically they prove that it is independent of computability with oracle access to the parameters, in the sense that all four combinations occur. The proof that there exists θ such that P θ : z → e 2πiθ z + z 2 is locally connected but not computable even with oracle access to θ is the most difficult; it uses in particular cylinder renormalization and a key result of Inou and Shishikura about this tool and the control on the post-critical set that this allows one to do. 18 Let me allow a personal remark as we near the end of this review, which after all is written by a human being. I have never seen a book without typos or errors, and this one is not an exception. All the ones I could spot were easily fixable, though, and some of them could be false positives due to my misunderstanding of some statement or forgetting of context or notation.

As a conclusion, this book sees the meeting of two worlds: computability theory and iteration of rational maps. It is a fruitful one, with both positive and negative result, and a share of surprises. It is also a compendium of several years of research by the authors and joints work with Ilia Binder, together with a lot of new results. It gives a nice and quick introduction to both topics, and much of it is pleasant to read, though the most technical parts are hard, especially the proofs that the algorithms work. The notations or formulations are not perfectly uniform between theorems, likely a side effect of part of them being a collection of results from previous articles. The book includes interesting discussions and presents stimulating conjectures. This is a theoretical work, and it is clear that some methods, even though they run in polynomial time, are much slower than existing algorithms. But at least they are proven to work. Moreover a certain number of new computational techniques are introduced, like their power series expansion-based acceleration procedure at parabolic points, and it is not impossible that, and would be interesting to determine if, some of them could improve actual programs used to draw Julia sets, in accuracy or running time.

Figure 1 :

 1 Figure 1: Example of Julia set of a rational map, represented as a black set on the Riemann sphere.

  The Fatou set is open, so its connected components are open. It may be empty. The image of a connected component is a whole connected component. Fatou classified periodic Fatou components:

A set X is called stable if R(X) ⊂ X and invariant if R(X) = X.

conformally, i.e. via a stereographic projection

This set S is an open subset of the set of rational maps of degree d (hyperbolicity is a stable

Again, when the coefficients are computable, there is no need for an oracle.

Note that such an isomorphism necessarily conjugates P to the rotation (this follows from the case of equality in Schwarz's lemma).