Recall the Mandelbrot set $M$ is the set of points $c$ in the complex plane such that the sequence $z_0 = 0, z_{n+1} = z_n^2 + c$ is bounded. It is well-known that $M$ is a compact set of positive area.
Is the area $A$ of the Mandelbrot set provably a computable real number?
That is, is there an algorithm (however slow, complex, or memory intensive) that would estimate $A$ to within any desired precision? Can we prove this algorithm will work?
We do known a formula for $A$:
$$A = \pi (1 – \sum_{n=0}^\infty n b_n^2)$$
Here $b_n$ are "the coefficients of the Laurent series about infinity of the conformal map $\psi$ of the exterior of the unit disk onto the exterior of the Mandelbrot set" (see here). The sequence $b_n$ is computable as it is given by a (messy) recursive formula (formula 7 in here).
Is there a way to compute the rate of convergence of $\sum_{n=0}^\infty n b_n^2$?
Remarks:
-
By computable I mean in the sense of computability/recursion theory (also computable analysis). However, all I am asking for is an algorithm which, when given a natural number $k$ as input, outputs a rational approximation $A_k$ which is within $2^{-k}$ of $A$.
-
The formula above is not enough. While we can compute partial sums $A_N = \sum_{n=0}^N n b_n^2$ to get an upper bound on $A$, we need a way to compute the rate of convergence of the series to actually compute $A$. One possible way to do this is to bound $n b_n^2 \leq c_n$ where the sequence $c_n$ is computable and $\sum_{n=0}^\infty c_n$ is finite and computable.
-
It is easy to show that $A$ is computable from above (a.k.a. upper semi-computable, right-c.e., computable in the upper reals). One can use the formula above or one can just use the standard way of drawing the Mandelbrot set: keep removing pixels where every point in that pixel escapes the circle $|z| \leq 2$. (For logicians: $M$ is $\Pi^0_1$.)
-
One could try fancier methods of drawing the Mandelbrot set, such as distance estimation where one draws a pixel iff it contains a point in $M$. One problem with this, is that we don't actually know that this method is computable? (It depends on the hyperbolicity conjecture. See here, here, and here.) A bigger problem is that this method still only gives us an upper estimation of $A$, since if we draw a pixel we don't know how much of the area of the pixel contains $M$.
-
As for estimating $A$ from below, one could enumerate all the hyperbolic components of $M$—those are the iconic cardioids and disks found in the Mandelbrot set (including the mini Mandelbrot islands). Then one can add up all their areas. In this way one can get a lower bound. Hertling did show the hyperbolic components are enumerable in a computable way. (For logicians: the union of the hyperbolic components is $\Sigma^0_1$.) However, there are two problems. It is unknown if the hyperbolic components make up the total of the interior (although it is widely conjectured to be true), and it is not known if the boundary of $M$ has zero area.
-
There are many estimates of the area of the Mandelbrot set in the literature. (See here for a(n outdated) summary.) They seem to group into four methods:
- Using the series formula above to give an upper estimate. (For newest estimate see here.)
- Adding up known parts of the interior to give a lower estimate.
- (Statistical) Pixel counting. It seems like this method could both over count and under count a pixel depending on how it is drawn. (While they give precise answers I don't know how mathematically rigorous the error values given by this method are.) (I think this newer boundary counting method is a type of pixel counting as well.)
- (Statistical) Monte Carlo. While this is a rigorous method for measuring area, one still has to know if the point is in the set. For example, if the boundary of $M$ has positive area, then this method would have problems since with positive probability one would get a point on the boundary and it would be impossible to determine if it was in the set or not. Therefore, I don't know how mathematically rigorous the error values and confidence interval of this Monte Carlo analysis are.
-
As for statistical methods, surprisingly this does provide a possible rigorous route to showing that the area of the Mandelbrot set is computable. If one can give a (provably correct) algorithm which takes in a rational $\epsilon > 0$ a probability $p < 1$ and a source of randomness, and outputs an approximation $A_{\epsilon, p}$ for which $|A_{\epsilon, p} – A| < \epsilon$ with probability $p$, then $A$ is computable. (The main idea is that any number computable with positive probability is computable outright.)
However, it seems to me that the only ways to make these statistical methods rigorous is to know that the boundary of $M$ has area zero and that one can determine (in a computably enumerable way) if a point is in the interior of $M$, both of which are open problems. (However, there maybe some important theorem I don't know about which is why I am asking.)
Best Answer
Your statement that the area of the union of bounded hyperbolic components is lower-computable is very plausible.
So if, as conjectured, hyperbolic parameters have full measure, then the area is indeed computable.
Without the assumption of this conjecture, I believe that the question is open. While it seems unlikely to be able to make any rigorous statement here, it seems intuitively clear that we cannot give any rigorous estimates without knowing the answer. Indeed, if there was a non-hyperbolic interior component, this would belong to a sequence of little Mandelbrot copies that do not shrink. Our algorithm somehow has to account for this area? For example, I believe it is not even known whether the Mandelbrot set itself is computable (i.e., whether the distance to the set is a computable function).
Now, admittedly sometimes there can be miraculous results using some series formulae. However, the corresponding formulae for the area of filled-in Julia sets can be shown to not converge nicely/quickly in any way, see Dezotti, Convergence properties of the Gronwall area formula for quadratic Julia sets, arXiv:1405.1933. So I would be surprised if a lower bound can be deduced from the series expansion.