3e:null 3f:["$","title",null,{"children":"Exploring Mandelbrot Polynomials | Silvas Workspapce | Observable"}] 45:Tc56,# Exploring Mandelbrot Polynomials ## Introduction In this notebook we are going to explore how to compute Mandelbrot polynomial using matrices and some properties of their roots. ### Preface I have first encountered Mandelbrot polynomials in graduate school when I stumbled upon [Dr. Piers Lawrence page](https://research.lawrences.info//research.html), at the time I thought it looked pretty nifty but sort of forget about it the day after. Recently, I saw the wonderful open source book [_Computational Discorvery on Jupyter_](https://computational-discovery-on-jupyter.github.io/Computational-Discovery-on-Jupyter/index.html]) by Neil J. Calkin, Eunice Y.S. Chan, and Robert M. Corless. I must say I was attracted by the picture they chose as a logo, since I was looking for ways to speed up my code for the Barnsley set and Thurston set. The section in this book entitled "Mandelbrot Polynomials and Matrices" looked interesting and I skimmed throught it. Only when I read in the second Remark about how people computed millions of roots, I went to look up those people webpages. To my surprise I saw the following gif in Dr. Lawrence homepage

Animation of the 21-periodic points under iteration of the Mandelbrot map

... mmmh that is odd, halfway in the gif it kind of looks like the image of the [Entropy spectra](https://www.math.toronto.edu/tiozzo/gallerynew.html) under the involution ${tex`z\mapsto 1/z`} ...at least for values of z outside the unit disk... I do not see a reason for why that would be true... so I went and downloaded the ${tex`2^{23-1}-1\approx4.2`} million roots that [Dr. Dario A. Dini](https://people.cs.dm.unipi.it/bini/) computed with his software MPSolve and plot the involution of their 12th iterate (which took them 47 days!) and

${await FileAttachment("mand22_12_hexbin_2500_twilight.png").image({width: 300, alt: "12th iterate of periodic points of period 22"})}

plotted all the points of the 12th iterate.

${await FileAttachment("mand22_12_hexbin_2500_twilight_g1.png").image({width: 300, alt:"12th iterate of periodic points of period 22 without those that lie inside the unit circle"})}

${tex`\mapsto`} removed the unit disk

${await FileAttachment("inv_mand22_12_hexbin_2500_twilight_g1.png").image({width: 300, alt:"involution of the 12th iterate of periodic points of period 22 without those that lie in the unit circle"})}

${tex`\mapsto`} applied the involution

almost! But, as expected, not true at all. Also, I should be using the preperiodic points so that I can take as many iterates as I want without coming back to the Mandelbrot set... still this is pretty nifty!46:T1fb1, ## Mandelbrot Polynomials ### The mathematics #### The Mandelbrot set Let us recall the definition of the main object of interest: the Mandelbrot set ${tex`\mathcal{M}`} is the set of all points ${tex`c`} in the complex plane ${tex`\mathbb{C}`} such that iterating 0 under the map ${tex`z\mapsto z^2+c`} does not go to infinity. Alternatively, is the set of all points ${tex`c`} for which the corresponding Julia set is connected. Let ${tex`c=0`} then ${tex.block`\tiny{\boxed{0}\mapsto 0^2+c = \boxed{0} \mapsto c^2+c = \boxed{0} \mapsto (c^2+c)^2+c = \boxed{0} \mapsto ((c^2+c)^2+c)^2+c = \boxed{0} \mapsto (((c^2+c)^2+c)^2+c)+c = \boxed{0}\mapsto\ldots.}`} Therefore, the point ${tex`c=0`} is in ${tex`\mathcal{M}`} since 0 is periodic with period 1. Let ${tex`c=\mathrm{i}`} then ${tex.block`\tiny{\boxed{0}\mapsto 0^2+c = \boxed{\mathrm{i}} \mapsto c^2+c = \boxed{-1+\mathrm{i}} \mapsto (c^2+c)^2+c = \boxed{-\mathrm{i}} \mapsto ((c^2+c)^2+c)^2+c = \boxed{-1+\mathrm{i}} \mapsto (((c^2+c)^2+c)^2+c)+c = \boxed{-\mathrm{i}}\mapsto\ldots.}`} Therefore, the point ${tex`c=\mathrm{i}`} is in ${tex`\mathcal{M}`} since 0 is eventually periodic with period 2. Let ${tex`c=1`} then ${tex.block`\tiny{\boxed{0}\mapsto 0^2+c = \boxed{1} \mapsto c^2+c = \boxed{2} \mapsto (c^2+c)^2+c = \boxed{5} \mapsto ((c^2+c)^2+c)^2+c = \boxed{26} \mapsto (((c^2+c)^2+c)^2+c)+c = \boxed{677}\mapsto\ldots.}`} Thus, the point ${tex`c=1`} is not in ${tex`\mathcal{M}`} since the iterates of 0 tend to ${tex`\infty`}. Doing the above for all the (uncountable) points in ${tex`\mathbb{C}`} we get the Mandelbrot set. In fact, it is easy to show that ${tex`\mathcal{M}`} is contained in a disk of radius 2, so we can restrict our domain. #### Periodic points Let us define the quadratic map ${tex`Q_c(z):=z^2+c`} for ${tex`c\in\mathbb{C}`}. Use the notation ${tex`Q_c^{(k)}(z)`} to express the ${tex`k`}th iterate of ${tex`Q_c`}: that is ${tex.block`Q_c^{\circ0}(z)=z\\Q_c^{(1)}(z)=Q_c(z)=z^2+c\\Q_c^{(2)}(z)=Q_c(Q_c(z))=(z^2+c)^2+c\\ Q_c^{(3)}(z)=Q_c(Q_c(Q_c(z)))=((z^2+c)^2+c)^2+c`} and so on... Periodic points of period ${tex`n`} are those for which ${tex`Q_c^{(n)}(z)=z`} with ${tex`n`} being the smallest integer value for which the equation holds. Preperiodic points with perperiod ${tex`k`} and period ${tex`m`} are points such that ${tex`Q_c^{(k)}(z)=Q_c^{(k+m)}(z)`}. There is also a further distinction of periodic points on whether they are _super-attracting_,_attracting_, _repelling_, or _neutral_: a periodic point $z$ of period $n$ is called - *super-attracting* if ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c^{(n)}(z)\right\vert=0`} - *attracting* if ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c^{(n)}(z)\right\vert<1`} - *repelling* if ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c^{(n)}(z)\right\vert>1`} - *neutral* if ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c^{(n)}(z)\right\vert=1`} >##### Attracting fixed points > >Suppose we want to find all the attracting fixed points ${tex`c\in \mathbb{C}`}, then we need to solve ${tex`Q_c(z)=z`} with the constraint that ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c(z)\right\vert<1`}. Solving the equation for $c$ we have ${tex.block`c=z-z^2.`} Now these values have to be attracting, which in this case means ${tex.block`\vert 2z\vert<1\iff z=r\mathrm{e}^{\mathrm{i} \theta},~~r\in[0,0.5),~\theta\in[0,2\pi)`} thus ${tex.block`c=r\mathrm{e}^{\mathrm{i} \theta}-r^2\mathrm{e}^{2\mathrm{i} \theta}=r^2+r\left(1-2r\cos(\theta)\right)\mathrm{e}^{\mathrm{i}\theta},~~r\in[0,0.5),~\theta\in[0,2\pi)`} which describes the inside of the cardioid ${tex.block`c=\frac{1}{4}+\frac{1-\cos(\theta)}{2}\mathrm{e}^{\mathrm{i}\theta}.`} > >In particular, the center of the cardioid ${tex`c=0`} is the only super-attracting fixed point. >##### Attracting periodic points of period 2 > >Suppose we want to find all the attracting periodic points ${tex`c\in \mathbb{C}`} of period 2, then we need to solve ${tex`Q_c^{(2)}(z)=z`} with the constraint that ${tex`\left\vert\frac{\rm d}{{\rm d}z}Q_c^{(2)}(z)\right\vert<1`}. Solving the quation for ${tex`c`} we have ${tex.block`(z+c)^2+c=z\implies c^2+(1+2z^2)c+(z^4-z)=0\\ c=\frac{-(1+2z^2)\pm\sqrt{(1+2z^2)^2-4(z^4-z)}}{2(1+2z^2)}=\begin{cases}z-z^2\\ -(z^2+z+1)\end{cases}.`} We can exclude the first solution as we know it describes the attracting fixed points. > >Now these values have to be attracting, which in this case means ${tex.block`\vert 4z(z^2+c)\vert<1 \iff 4z(z^2+c)=r\mathrm{e}^{\mathrm{i} \theta},~~r\in[0,1),~\theta\in[0,2\pi).`} Using that ${tex`c=-(z^2+z+1)`} we have ${tex.block`4z(z+1)=-r\mathrm{e}^{\mathrm{i}\theta}\implies z^2+z=-\frac{r}{4}\mathrm{e}^{\mathrm{i}\theta}.`} Substituting back to ${tex`c=-(z^2+z+1)`} we finally get ${tex.block`c=-1+\frac{r}{4}\mathrm{e}^{\mathrm{i}\theta},~~r\in[0,1),~\theta\in[0,2\pi)`} which describes the inside of the disk of radius 0.25 centered at ${tex`-1`}. > >In particular, the center of the disk ${tex`c=-1`} is the only super-attracting fixed point of period 2. #### Super-attracting periodic points The regions of the Mandelbrot set in which ${tex`Q_c`} has an attracting periodic point are called _hyperbolic components_. The cardioid and the circle we computed above are two examples of such hyperbolic components. Moreover, each hyperbolic components has a center, that is a point in which ${tex`Q_c`} is super-attracting. This means that the periodic cycle must contain the critical point 0. Therefore, if we are interested only in finding the super-attracting periodic points of period ${tex`n`} we need to solve ${tex`Q_c^{(n)}(0)=0`}. >##### Super-attracting fixed point > >To find the super-attracting fixed point we have to solve the equation ${tex`Q_c(0)=0`} which directly gives us ${tex`c=0`}. >##### Super-attracting periodic point of period 2 > >To find the super-attracting periodic point of period 2 we have to solve the equation ${tex`Q_c^{(2)}(0)=c(c+1)=0`}. We know already that ${tex`c=0`} cannot be a solution, so ${tex`c=-1`} is the only solution. >##### Super-attracting periodic point of period 3 > >To find the super-attracting periodic points of period 3 we have to solve the equation ${tex`Q_c^{(3)}(0)=c(c^3+2c^2+c+1)=0`}. We know already that ${tex`c=0`} cannot be a solution, so there are only three solutions. >##### Super-attracting periodic point of period 4 > >To find the super-attracting periodic points of period 4 we have to solve the equation ${tex.block`\tiny{Q_c^{(4)}(0)=c(c^7+4c^6+6c^5+6c^4+5c^3+2c^2+c+1)=c(c+1)(c^6+3c^5+3c^4+3c^3+2c^2+1)=0.}`} We know already that ${tex`c=0`} and ${tex`c=-1`} cannot be solutions, so there are only six solutions. Note that in the last two examples we excluded some solutions. In fact, whenever we are solving for (super-)attracting periodic points of period ${tex`n`}, we have to exclude the (super-)attracting periodic points of period ${tex`m`}, where ${tex`m|n`}. #### The Mandelbrot polynomials and matrices The Mandelbrot polynomials are defined using recursion: ${tex.block`p_0(z)=0\\ p_{n+1}(z)=z \big(p_n(z)\big)^2+1 \qquad\forall n\geq1 . `} Here are the first five Mandelbrot polynomials ${tex.block` p_0(z)=0;~~p_1(z)=1;~~p_2(z)=z+1;\\ p_3(z)=z^3+2z^2+z+1;\\ p_4(z)=z^7+4z^6+6z^5+6z^4+5z^3+2z^2+z+1 `} Notice that ${tex`p_n(c)`} for ${tex`n\geq2`} equals ${tex`Q_c^{(n)}(0)`} dvided by ${tex`c`}. The Mandelbrot matrices are recursively-constructed upper Hessenberg matrices that only contains ${tex`\{-1,0\}`}. They were first constructed by Dr. Pierce Lawrence. The eigenvalues of these matrices are the roots of the corresponding Mandelbrot polynomials. ${tex.block`M_2=\begin{bmatrix}-1\end{bmatrix}\\ \\ M_{n+1}=\begin{bmatrix}M_n & & -\vec{c}_n\vec{r}_n\\ -\vec{r}_n & 0 & \\ & -\vec{c}_n & M_n\end{bmatrix}~~\forall n\geq1`} where ${tex`\vec{c}_n=\begin{bmatrix}1 & 0 &\cdots &0\end{bmatrix}^T`} and ${tex`\vec{r}_n=\begin{bmatrix}0&\cdots&0&1\end{bmatrix}`} are unit vectors of length ${tex`2^{n-1}-1`}, the degree of ${tex`p_n`}. Showing that ${tex`p_n(z)=\det(zI_n-M_n)`} for all ${tex`n\geq2`} requires induction and the Schur complement. 47:[{"id":"8ff4997937abef39f264882e498076f7b0455c8278ecd9c7e60891031c5d6b89e07d144a6fd73bea910192cc44cf679bb81aa4c8bd6cdf341a972300a9655842","href":"https://static.observableusercontent.com/files/8ff4997937abef39f264882e498076f7b0455c8278ecd9c7e60891031c5d6b89e07d144a6fd73bea910192cc44cf679bb81aa4c8bd6cdf341a972300a9655842","name":"mand22_12_hexbin_2500_twilight.png","type":"image/png","lastModified":1686476890133.945,"size":696249},{"id":"d1b3ea0564ccfe18d7b5ff406a3bd94a78bf65ad699395cca92de35212a26ac6f1f10ea0a20527c5eb1d27d0e29561057313d91f73c91e17063a055b857a650e","href":"https://static.observableusercontent.com/files/d1b3ea0564ccfe18d7b5ff406a3bd94a78bf65ad699395cca92de35212a26ac6f1f10ea0a20527c5eb1d27d0e29561057313d91f73c91e17063a055b857a650e","name":"mand22_12_hexbin_2500_twilight_g1.png","type":"image/png","lastModified":1686476910636.017,"size":383859},{"id":"7f556c162614d7da7721783e3a4cddcd872d0d576da0d768dcc433132731ea916d30af4b6fd0650fa3386608cb19b01aef76b523827f68694ba0efa56da7f63e","href":"https://static.observableusercontent.com/files/7f556c162614d7da7721783e3a4cddcd872d0d576da0d768dcc433132731ea916d30af4b6fd0650fa3386608cb19b01aef76b523827f68694ba0efa56da7f63e","name":"inv_mand22_12_hexbin_2500_twilight_g1.png","type":"image/png","lastModified":1686476917420.086,"size":658092}] 43:{"id":"35adfb1b033fd9ef","slug":null,"title":"Exploring Mandelbrot Polynomials","thumbnail":"fe60ad64fda82fb8c10e6c9e2c5ac0321d4d1f5aced9badbb213db9a2e4ee9dd","access_level":"public","create_time":"$D2023-06-11T09:35:30.900Z","update_time":"$D2023-06-11T12:21:48.335Z","view_time":null,"first_public_time":"$D2023-06-11T09:35:30.900Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"768fc3a9171c17e2","login":"silvasworkspace","name":"Silvas Workspapce","avatar_url":"https://avatars-next.observableusercontent.com/ae8c2ad703961bf12e8816260fa3fb8249cd96e422b39ee5615250633bb459c0","tier":"starter_2024","bio":"","following":false},"version":66,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"26e328310b657089","login":"silvestristefano","name":"Stefano Silvestri","avatar_url":"https://avatars-next.observableusercontent.com/ae8c2ad703961bf12e8816260fa3fb8249cd96e422b39ee5615250633bb459c0","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"768fc3a9171c17e2","login":"silvasworkspace","name":"Silvas Workspapce","avatar_url":"https://avatars-next.observableusercontent.com/ae8c2ad703961bf12e8816260fa3fb8249cd96e422b39ee5615250633bb459c0","tier":"starter_2024","role":"editor"},{"type":"individual","id":"26e328310b657089","login":"silvestristefano","name":"Stefano Silvestri","avatar_url":"https://avatars-next.observableusercontent.com/ae8c2ad703961bf12e8816260fa3fb8249cd96e422b39ee5615250633bb459c0","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Exploring Mandelbrot Polynomials","cells":[{"id":0,"value":"$45","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":16,"value":"$46","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"}],"files":"$W47","stdlib":"1"}} 44:"$43:body"