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

[Laurent Bartholdi]

Dear Andrius:
There is much to think about in your email, and I can only comment on the
link Mandelbrot set / Catalan numbers. As far as I see, the link is merely
that the Catalan numbers describe the main cardioid of the Mandelbrot set.
You consider the generating function G(c) = c G(c)^2+1; consider now the
function c*G(c), which satisfies cG = (cG)^2+c. Thus c*G(c) is a fixed
point of z^2+c. The main cardioid, in the Mandelbrot set, is the set of c
such that the fixed point c*G(c) is attracting, namely |c*G(c)|<1/2.
However, the structure of the Mandelbrot set is much more complicated than
the set of c such that Pn has an attracting fixed point; though these
attracting periodic points of z^2+c are presumably dense in the Mandelbrot
set.

On Sun, 15 May 2016 at 01:51 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
>
-- 
Laurent Bartholdi
DMA, École Normale Supérieure, 45 rue d'Ulm, 75005 Paris. +33 14432 2060
Mathematisches Institut, Universität Göttingen, Bunsenstrasse 3-5, D-37073
Göttingen. +49 551 39 7826
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160515/8353cb74/attachment-0001.html>