Catching a spider: Automating the Spider Algorithm in Complex Dynamics

Wayne Peng

National University of Kaohsiung

<p>
        List of all degree $3$ PCF polynomials (see [2]).
      </p>
      <div class="grid-container">
        <div class="grid-item">$ z^{3} $</div>
        <div class="grid-item">$ -z^{3} + 1 $</div>
        <div class="grid-item">$ -2z^{3} + 3z^{2} + \tfrac{1}{2} $</div>
        <div class="grid-item">$ -2z^{3} + 3z^{2} $</div>
        <div class="grid-item">$ -z^{3} + \tfrac{3}{2}z^{2} - 1 $</div>
        <div class="grid-item">$ 2z^{3} - 3z^{2} + 1 $</div>
        <div class="grid-item">$ 2z^{3} - 3z^{2} + \tfrac{1}{2} $</div>
        <div class="grid-item">$ z^{3} - \tfrac{3}{2}z^{2} $</div>
        <div class="grid-item">$ -3z^{3} + \tfrac{9}{2}z^{2} $</div>
        <div class="grid-item">$ -4z^{3} + 6z^{2} - \tfrac{1}{2} $</div>
        <div class="grid-item">$ 4z^{3} - 6z^{2} + \tfrac{3}{2} $</div>
        <div class="grid-item">$ 3z^{3} - \tfrac{9}{2}z^{2} + 1 $</div>
        <div class="grid-item">$ -z^{3} + \tfrac{3}{2}z^{2} - 1 $</div>
        <div class="grid-item">$ -\tfrac{1}{4}z^{3} + \tfrac{3}{2}z + 2 $</div>
        <div class="grid-item">$ -\tfrac{1}{28}z^{3} - \tfrac{3}{4}z + \tfrac{7}{2} $</div>
      </div>

<h3>Dynamical Galois Group</h3>
      <ul>
        <li class="fragment" data-fragment-index="1">Let $K$ be a number field.</li>
        <li class="fragment" data-fragment-index="2">Let $f$ be a polynomial of degree $d$ over $K$.</li>
        <li class="fragment" data-fragment-index="3">$K_n(\alpha) = K(f^n(X)-\alpha)$ is the splitting field of $f^n(X)-\alpha$.</li>
        <li class="fragment" data-fragment-index="4">$\alpha$ is called <em>base point</em>. $\alpha$ can be algebraic or transcendental over $K$.</li>
        <li class="fragment" data-fragment-index="5">$G_n(\alpha)= \mathrm{Gal}(K_n(\alpha)/K)$; $G_\infty = \varprojlim_n G_n(\alpha)$.</li>
      </ul>
      <p class="fragment" data-fragment-index="6">We may define a tree structure on $\alpha$ and its preimages under $f$ by creating an edge between two points $a$ and $b$ if $f(a)=b$.</p>
      <div class="proposition fragment" data-fragment-index="7">
        <p>
          We have a natural embedding $\phi_n: G_n\to \operatorname{Aut}(X^n)$.
        </p>
      </div>

In general, we note that $K_\infty(\alpha)$ is unramified outside a finite set of places $S$. Then the dynamical Galois group is a quotient group of $G_S=\operatorname{Gal}(K_{S}/K)$ where $K_S$ is the maximal extension of $K$ unramified outside of $S$. Since $K$ has characteristic $0$, the ramification is tame. It then follows by Neukirch, Schmidt, and Wingberg that $G_S$ is finitely generated.

Three steps to define IMG action

STEP 1

Give a collection of paths $\mathcal{L}=\{l_x\}_{x\in f^{-1}(t)}$ where $l_x$ starts at $t$ and ends at $x$.

STEP 2

Consider a spider and attach the foot of every leg with a small circle around each pole. These are loops starting from $t$ and then walk along legs and circle around a pole and travel back along the legs. Clearly, these loops are generators $g$ of $\pi_1(\mathcal{M},t)$

STEP 3

Let $x,y\in f^{-1}(t)$, and let $f^{-1}(g)[x]$ be the lift from $x$ to $y$. Define $g' = l_xf^{-1}(g)[x] l_y^{-1}$. Then, the following relationship gives IMG acting on trees $X^*$ $$(xw)^g = yw^{g'}$$

Is the loop $l_xf^{-1}(g)[x] l_y^{-1}\in\pi_1(\mathcal{M},t)$ a simple loop? Is it homotopic to the loop associated with a leg of the spider?

An automaton over the alphabet $X$ is given by

set of the states $A$;
a map $\tau:A\times X\to X\times A$ ($g\cdot x = y\cdot g'$).

If $g'$ is homotopic to the loop associated with a leg of the spider for all $g$, then IMG acting on alphabet $X$ induces an automaton.

(Nekrashevych)

Let $f:\mathbb{R}^2\to\mathbb{R}$ be a post-critically finite topological polynomial. Suppose that there exists an invariant spider $\mathcal S$. Then, a standard action on $\operatorname{IMG}(f)$ on $X^*$ is generated by some automaton.

Nekrashevych claims that an invariant spider always exists by Hubbard and Schleicher [3]. Nevertheless, the paper only focus on quadratic polynomial, and doesn't make any claim on the existence of invariant spider.

Difficulties...

Using infinity as the spider head is not always manageable.
How to choose a good collection of paths $\mathcal{L}$?

Let $\phi_f$ be a virtual endomorphism of $\pi(\mathcal{M},t)$. Then, for every right coset transversal $\mathcal{T}=\{r_x\}_{x\in f^{-1}(t)}$ and sequence $\mathcal{C}=\{h_x\}_{x\in f^{-1}(t)}$ there exists a collection of paths $\mathcal L$ such that the respective IMG action is the action defined by the triple $(\phi, \mathcal T, \mathcal C)$.

Blackbox...

To define the virtual endomorphism $\phi_f$, we need to fixed a preimage $z_0$ of $t$ and a path $l$ from $t$ to $z_0$.
$\mathcal{C} = \{1\}_x$.
$r_x=f(\rho_x)$ are the image of path $\rho_x$ from $z_0$ to $x$.
The relationship to define an automata is given by $$g\cdot x = y\cdot \phi_f(r_xgr_y^{-1})$$ where $\phi_f(r_xgr_y^{-1}) = \rho_x f^{-1}(g)[x] \rho_y^{-1}$.

Goal:

Find a collection of paths $\{\rho_x\}_{x\in f^{-1}(t)\setminus\{z_0\}}$ such that $$\rho_x f^{-1}(g)[x]\rho_y^{-1}$$ is homotopic to the generators constructed from the spider $\mathcal S$.

$f = 2x^3-3x^2+1$

Let $\mathcal{S}$ be a spider on $\mathcal{M}$. We call a collection of paths $\{\rho_x\}$ Lucas, a good spider, at $z_0\in f^{-1}(t)$ if for each leg $\rho_x$ starting at $z_0$ and ending at $x\in f^{-1}(t)\setminus\{z_0\}$, the path $\rho_x f^{-1}(g)[x]$ either ends at some point, not a pole, or is homotopic to a leg of $\mathcal{S}$.

Where to find Lucas?

Consider the graph $G=(E,V)$, called web, where $$ E = f^{-1}(t)\cup f^{-1}(P)\quad\text{and}\quad V=f^{-1}(\mathcal{S}).$$

We label vertices in $f^{-1}(t)$ by $x$ and the vertices in $f^{-1}(P)$ by $p$ if the vertices is in $P$ or $d$ otherwise.

(P.)

Given a web $G$, a collection of paths $\{\rho_x\}$ is Lucas at $z_0$ if these paths are paths on $G$ starting from $z_0$ and ending at $t$ and satisfy the following:

the head only connects to at most two vertices labels by $p$ with no leg from $\mathcal S$ between these two vertices;
for each $x$, only one neighbor of $x$ not on the path $\rho_x$ is labeled by $p$.

Since the iterated monodromy group acts on $f^-1(t)$ transversely, $G$ is connected. Since the legs of $\mathcal S$ intersect only at $t$, the unique lifting lemma implies that $G$ is a topological graph. Let $l$ be a path from $t$ to $z_0$. Let $p_1$ and $p_2$ (if they exist) be the direct poles of $z_0$ on ${r_x}$. By assumption, there is a path $l$ from $t$ to $z_0$ such that $\{l\cdot (z_0,p_1),\; l\cdot(z_0,p_2)\}$ is homotopic to $\{l_{p_1}, l_{p_2}\}$.

Now, if $f^{-1}(l_p)[x]$ is not a pole, we may ignore it. If it is a pole, denoted by $p'$, then the poles enclosed by $r_x\cdot f^{-1}(l_p)[x]\cdot l_{p'}^{-1}$ fall into one of the following two cases:

case 1:

case 2:

In either case, we can redefine the path $r_i$ so that the pole lies outside the loop, and thus we can catch a Lucas.

Discussion

What if a head $z_0$ connects directly to three poles?
What if the neighbors of a foot $x$ contain three poles?
Construct higher degree rational function or polynomial to test the code

Reference

[1] https://arxiv.org/pdf/1212.1518

[2] https://math.mit.edu/~drew/ANTSXIV/CubicPostcriticallyFiniteSlides.pdf

[3] John H. Hubbard and Dierk Schleicher, The spider algorithm, Complex Dynamical Systems. The Mathematics Behind the Mandelbrot and Julia Sets (Robert L. Devaney, ed.), Proceedings of Symposia in Applied Mathematics, vol. 49, 1994, pp. 155–180.