[FOM] Mandelbrot set, Catalan numbers, Context-free grammars
Timothy Y. Chow
tchow at alum.mit.edu
Sun May 15 15:52:04 EDT 2016
Andrius Kulikauskas
> So it appears that the exceedingly bizarre Mandelbrot set is simply
> defined by the behavior (convergence, divergence or otherwise) of the
> generating function of the Catalan numbers G(c).
I was not aware of this connection between the Catalan numbers and the
Mandelbrot set; thanks for pointing it out.
Note, however, that what the Mandelbrot set tracks is not simply the
behavior of G(c). G(c) is the formal power series limit of a sequence of
polynomials G_1(c), G_2(c), G_3(c), ..., and what the Mandelbrot set
tracks is whether {G_i(c)} is bounded.
I would also point out that the Mandelbrot set is not as arbitrary as you
make it sound. If one is interested in the process of iterating
functions, which is arguably a "basic" process, then it is natural to
start with "simple" functions. Iterating linear functions is easy to
understand, so it is natural to consider quadratic functions. The family
of quadratic functions {z^2 + c} has a reasonable claim to being the
"simplest" nontrivial family of quadratic functions, and the question
"Does iterating on 0 diverge to infinity?" has a reasonable claim to being
one of the simplest questions that one might hope to answer.
> This generating function can be thought of as enumerating all of the
> possibilities for a grammar.
In case you are not aware of it, the Kleene-Schutzenberger theorem
relating regular languages and rational generating functions is perhaps
the first major result connecting grammars and generating functions.
Perhaps some of the literature on generalizations of that theorem will be
of interest to you.
Tim
More information about the FOM
mailing list