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


More information about the FOM mailing list