[FOM] Mandelbrot set, Catalan numbers, Context-free grammars

Sat May 14 23:43:24 EDT 2016

Andrius, hello. You might be interested in the recent book 

Yuri F. Bilu, Yann Bugeaud, Maurice Mignotte
The Problem of Catalan
Springer, 2014

http://link.springer.com/book/10.1007%2F978-3-319-10094-4

Good luck,

Verónica

On May 14, 2016, at 10:44 AM, Andrius Kulikauskas <ms at ms.lt> wrote:

I wish to share a curious link that I noticed between the Mandelbrot set and the Catalan numbers which may be useful for studying the kinds of logical expressions that automata can generate.  I appreciate any related references or ideas that you might offer.

I am interested to understand the big picture in math.  That is, I am looking for a perspective from which I could understand which ideas are cognitively most basic and how more sophisticated mathematics unfolds.  This wish supposes that math is not merely "explicit", not merely what gets written down, but that there are also "implicit" notions at play which may yet be distinguished as "basic" or "sophisticated".  I am interested to discuss with mathematicians how we might investigate math as a whole.

I was reading mathematical physicist Roger Penrose's "Road to Reality", which is an impressive 1100+ page survey of all he knows about math, available for free online.  I was curious why he mentions the Mandelbrot set, which I think of as an example of what is most accidental in math, and thus least interesting from my point of view.  The Mandelbrot set is generated by considering any complex number c and what happens in the limit to infinity upon iterating the substitution  z -> z^2 + c and then discarding the z (setting z=0) at the end.  If the iterations Pn stay bounded (<=2), then we include c in the Mandelbrot set, and otherwise they diverge to infinity and we don't include them.  Roger Penrose writes this out much more elegantly as the sequence:
... c^2 + c)^2  + c)^2  + c)^2 + c

Well, as a combinatorialist, I realized that the leading terms settle down and might actually be a nice sequence.  It turns out that they are in fact the Catalan numbers, as can be shown by induction to yield their recurrence relation.
https://en.wikipedia.org/wiki/Catalan_number
These are some of the most basic numbers in combinatorics.  They count the number of correct expressions for n pairs of parentheses. In other words, they count the semantical possibilities that our mind has in associating operators in a string of operators. Furthermore, this is related to the types of strings that can be generated by context-free grammars and context-sensitive grammars, which are important in the Chomsky hierarchy. For example, we could code the words that such a grammar generates and if we plug in 1 for all of the symbols then we should typically get the Catalan numbers or something related.

The generating function G(c) is given by G(c) = c*G(c)^2 + 1.  Thus 0 = c*G(c)^2 - G(c) + 1.   Solving the quadratic equation yields G(c) = 2/(1 + (1-4c)^(1/2)).

One question then is whether the behavior of Pn as n goes to infinity is given by G(c).  The coefficients are all positive and the coefficients of G(c) are always greater than Pn.  The first half or so of the coefficients of Pn match those of G(c).  So if Pn diverges then it seems that G(c) should diverge, too.  And if Pn does not diverge, then neither should G(c).  But I'm not an expert and I'm not sure.

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).  Which apparently is not trivial as I gather from this post:
http://math.stackexchange.com/questions/1097097/generating-series-of-catalan-numbers

Also, surprisingly, the relation between the Mandelbrot set and the Catalan numbers may not be well known.  There is a note at the Online Encyclopedia of Integer Sequences https://oeis.org/A000108 thanks to an observation in 2009 by Donald D. Cross http://cosinekitty.com/mandel_poly.html

But now imagine this as a tool for Foundations of Math.  We can interpret the Catalan generating function at each complex number (or pair of real numbers, or map from one real number to another real number).  This generating function can be thought of as enumerating all of the possibilities for a grammar.  In particular, consider a hierarchy of grammars where a matrix A describes the rules (and the symbols accepted) and a matrix X is the nonterminal generator of the possibilities:
X -> AX finite automata, regular languages
X -> AXA push-down automata, context free languages
XA -> AX linear bounded automata, context sensitive languages
XA -> X Turing machines, recursively enumerable languages

A rule like X -> AXA is involved in making sure that each open parenthesis is ultimately paired with a closed parenthesis.  This is what I suppose the Catalan numbers are coding when they converge.  A rule like XA->AX allows the cursor to glide across many symbols. This perhaps could be the case when the Catalan generating function doesn't settle down.  And a rule like XA->X means that the automata is able to destroy information and introduce irreversibility like a full fledged Turing machine, and then perhaps in that case the Catalan generating function diverges.

So that is some poetic thinking which might perhaps yet spark ideas even for the P/NP complete problem.

Also, I note that the Catalan numbers count the number of semiorders on n unlabeled items.
https://en.wikipedia.org/wiki/Semiorder
This makes me think of cardinality and the Continuum hypothesis. For the semiorders seem to be "almost" orders.  And in fact it may be possible to play with that "almost" in the limit, making it more or less favorable.  Thus they seem relevant if one is to try to construct a set that is bigger than the integers but less than the continuum.

The Mandelbrot set could be an amazing object for tackling nasty problems.  Apparently, the Mandelbrot set may be locally connected. I think that would mean that you could always find a small enough neighborhood where the set is "nonchaotic" but if you move farther away then you will get chaotic results.

I appreciate any critique or feedback.  I also want to point out that what I thought was a most idiosyncratic object in math is in fact related to what is cognitively most fundamental (the possibilities for associativity) and this link may be quite practical and powerful.  So this suggests that math is not evolving haphazardly but rather if we survey all of math so far then we might get a sense of some overarching organizational principles.

I just want to add that I am very grateful for this forum.  I am glad to witness Harvey Friedman's thinking out loud even though I can only understand just a bit.  Also, my first talk in graduate school was about Hilbert's Tenth Problem which Martin Davis helped solve and which is inspiring in terms of what math can encode.

Andrius

Andrius Kulikauskas
ms at ms.lt
+370 607 27 665
Vilnius, Lithuania
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom