Mandelbrot set, Catalan numbers, and NP-Completeness

[Andrius Kulikauskas]

Hi Kirby and all,

As most of you probably know, the Mandelbrot set is consider one of the
most outrageously beautiful objects in math:
https://en.wikipedia.org/wiki/Mandelbrot_set

I wrote the letter below for the Foundation of Mathematics group but I
think it might be interesting here. Partly it's the thought that
without knowing much math one can discover a curious or even amazing
connection. I wrote up my adventure and realized that just a few years
ago "cosine kitty" had made some straightforward calculations to
discover the same sequence of numbers I did.
http://cosinekitty.com/mandel_poly.html
And probably like me, he googled those first few numbers and found the
Catalan numbers, too. So I'm curious where this leads. But mostly I'm
encouraged that there is a "big picture" in math. Also, it suggests
that an emphasis on computational approaches can overlook elegant math
ideas, like multiplying out polynomials and spotting the Catalan
numbers. Unless I'm completely wrong about something. Of course, I
used google. :)

Andrius


----------------------------
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
m...@ms.lt
+370 607 27 665
Vilnius, Lithuania

[kirby urner]

On Sat, May 14, 2016 at 6:55 AM, Andrius Kulikauskas <m...@ms.lt> wrote:

Hi Kirby and all,

As most of you probably know, the Mandelbrot set is consider one of the most outrageously beautiful objects in math:
https://en.wikipedia.org/wiki/Mandelbrot_set

Wow with the connection to Catalan numbers.  I'm familiar with Catalan
polyhedrons, the duals to the Archimedeans:

http://www.georgehart.com/virtual-polyhedra/archimedean-duals-info.html

You'll recall I'm really into duals, especially when introducing the Platonics:

tetrahedron <- dual -> tetrahedron

octahedron <- dual -> cube

icosahedron <- dual -> dodecahedron

Fig. 1:  the Platonic Set, usually considered a

set of five, as tetrahedron is self-dual.

Disambiguation:  other dodecahedra besides the pentagonal exist, nor need
the pentagons stay regular should we loosen constraints.  We're likely to want
the rhombic dodecahedron to have prominence in many applications so will
be introducing PD and RD for pentagonal and rhombic dodecahedra respectively.

Check out this "game with blocks" using Archimedean honeycomb duals:

http://www.steelpillow.com/polyhedra/AHD/AHD.htm  (click on Chart for cool PDF)

https://en.wikipedia.org/wiki/Honeycomb_%28geometry%29

Note there's a difference between dualizing an individual polyhedron
e.g. Archimedean <--> Catalan and dualizing what's called a "space

filling honeycomb" such as made by the cuboctahedron and octahedron,

or tetrahedron and octahedron.

http://www.rwgrayprojects.com/synergetics/s10/figs/f3230.html
http://mathworld.wolfram.com/Cuboctahedron.html  (dual of RD)
https://youtu.be/_VT9eS35Cts (octahedron)

Structure number 7 (DS-8, A-15, C, W-14, J-12)

• Picture:
  
  
• Delaney symbol
• octahedron, cuboctahedron, ratio 1:1, vertex figure 2:4
• Space group Pm-3m

from: http://mathieudutour.altervista.org/UniformTiling/index.html

Eyeballing your letter, I find it more cross-disciplinary than usual

meaning it'd be a stretch for most specialists to tackle, so they set

it aside or postpone any day of reckoning (bookkeeping) with the

calculation that if it's relevant it will come around knocking again
down the road.  This is logical human behavior, a focus of
queuing theory among other disciplines.

Keep connecting those dots!

Kirby

[Andrius Kulikauskas]

Kirby and all,
I wrote this follow up letter.
Andrius
-------------------------------------------

Tim, Thank you for introducing me to the Kleene-Schutzenberger theorem.
That sounds relevant.

Don Cross wrote me to explain that he contributed the Mandelbrot
generator sequence to the Online integer sequence database in 2005 and
then somebody later noticed that they are the same as the Catalan numbers.

Tim, yes, I agree with you that the Mandelbrot set is not at all as
arbitrary as I thought. The simplest way I can think of it is as
follows. Suppose I have for my "input" a vector in the 2-dimensional
plane and that I define addition of the input as vector addition. And
suppose that for my "output" I define addition as multiplication in the
complex plane. Well, then the algorithm is simply:
add the input, add the output, add the input, add the output, add the
input, add the output...
In other words:
add c, multiply what you get by itself, add c, multiply what you get by
itself...
Where multiplication is a rotation and moving further out or further in
the unit circle. It reminds me of kneading bread and seeing what
happens to a carroway seed.
This is all to say that the Mandelbrot set fails as an example of an
"accidental" instance of astonishing math.

Tim, Laurent, my (limited) understanding is that in the limit to
infinity the generating function of the Catalan numbers G(c) behaves the
same as the sequence of polynomials G_1(c), G_2(c) etc. typically used
to define the Mandelbrot set. In other words, we could equally well use
the Catalan generating function G(c) and see if it converges, diverges,
or neither. In fact, that would be more natural, more basic and link in
to much, much more mathematical machinery as the Catalan numbers are
very central.

Indeed, I found this connection mentioned with enthusiasm by Philippe
Flajolet and Robert Sedgewick in their definitive textbook Analytic
Combinatorics, 2009. Their book is available online for free:
http://algo.inria.fr/flajolet/Publications/book.pdf
See pages 535-537 and also the link to the theta function is discussed
on page 328-330. However, that is all their book has to say about the
Mandelbrot set, and their earlier version did not mention it at all. I
haven't seen any further research. Whereas they mention the Catalan
numbers dozens and dozens of times. They note the connection to
counting trees but not, as far as I could see, to counting parenthesis
expressions. Indeed, the repeatedly look for and point out
"universality phenomenon" of qualitative distinctions that analytic
combinatorics helps to draw amongst combinatorial objects to show their
basic types and their behavior. They also do make a distinction which
recalls the Chomsky hierarchy in that they distinguish between the
combinatorial behavior of regular expressions as opposed to nested
sequences, lattice paths, and continued fractions, as can be generated
by context-free grammars. They also have wonderful tables like Figure
V.11 which link the Catalan numbers with the Chebyshev polynomials (they
satisfy the same recurrence relations) and similarly with other counting
numbers and orthogonal polynomials.

I found a paper that links the Mandelbrot set and the Chebyshev polynomials:
http://www.worldscientific.com/doi/abs/10.1142/S0218127401003577?journalCode=ijbc

Algebraic combinatorist Richard Stanley in 2015 wrote a brand new book
"Catalan Numbers" which makes no mention of the Mandelbrot set. So I
take that to be an example of what giant chasms there are separating the
different branches of mathematics.

There are also q-t-Catalan numbers to think about.