Catching a spider: Automating the Spider Algorithm in Complex Dynamics

Wayne Peng

National Central University

Chen-P.

Let $\phi_c(x) = x^d + c$ and $\psi(x) = x^d$ be rational functions with $c\in\mathbb{Z}\setminus\{0\}$. Then we have

$d$ even, $c>0$: $\sup_{x\in\mathbb{P}^1(\bar{\mathbb{Q}}\cap\mathbb{R})}|h_{\phi_c}(x)-h_{\psi}(x)|=|h_{\phi_c}(\pm 1)-h_{\psi}(\pm 1)|$
otherwise: $\sup_{x\in\mathbb{P}^1(\bar{\mathbb{Q}}\cap\mathbb{R})}|h_{\phi_c}(x)-h_{\psi}(x)|=|h_{\phi_c}(x_0)-h_{\psi}(x_0)|$ with $x_0$ some real fixed point of $\phi_c$

P.-Tucker

Assuming Vojta's conjecture and the $abc$ conjecture. Let $K$ be a number field, and let $f,g\in K[x]$ be indecomposable non-PCF polynomials with $\deg f,\deg g>1$.

Then, for every $a,b\in K$, \[ \boxed{ T_f(a)\cong_K T_g(b) \quad\Longleftrightarrow\quad (a,b)\text{ lies on a balanced periodic curve for }(f,g). } \]

Start with a simple dynamical system

Iteration means feeding the output of a function back into the same function.

For $f(x)=x^2-1$:

$$0\longmapsto -1\longmapsto 0\longmapsto -1\longmapsto\cdots\text{ and }\infty\to\infty$$

The critical points eventually repeat. Such a map is called post-critically finite, or PCF.

What can the infinitely many backward paths of this very simple system tell us?

Now run the process backward

Choose a point $t$. First solve $f(x)=t$, then solve $f^2(x)=t$, and continue.

$t \leftarrow f^{-1}(t) \leftarrow f^{-2}(t) \leftarrow \cdots$

The answers branch into a tree. The preimage of a loop from $t$ around a critical point is a path connect branches.

The iterated monodromy group records all of these shuffles. $$ \rho_f \colon \pi_1\!\left(\mathbb{P}^1(\mathbb{C})\setminus P_f,\,t\right) \longrightarrow \operatorname{Aut}(T_f), $$

Why introduce a spider?

We need a consistent way to draw one loop around each critical point.

Draw non-crossing paths from one common base point. Travel out along one leg, circle its endpoint, and return along the same leg.

This collection of legs is a spider.

What is hard for a computer?

A person can often see when one path can be smoothly deformed into another.

Can a computer recognize the same path without continuously testing every possible deformation?

paths may bend, stretch, and look completely different;
they may not cross a critical point or one another;
the method must also work near the point at infinity.

Key idea: replace the picture by a graph

Pull the spider backward through the function. The result is an embedded graph, which I call the web.

The web records only finite information:

which important points are connected;
which paths share a vertex;
the clockwise order of edges around each vertex.

The continuous deformation problem is now a finite graph-search problem.

The algorithm

1
Approximate each spider leg by finitely many points

2
Pull back the legs and build the web

3
Search for paths that do not conflict

4
Check every local neighborhood and its clockwise order

Output: a finite certificate that the selected paths form a good spider.

When does the computer say “good”?

A criterion for finding a good spider

Let $G$ be the web and let $z_0\in f^{-1}(t)$ be the head. A collection of paths $\{\rho_x\}$ forms a good spider at $z_0$ if:

for every $x\in f^{-1}(t)\setminus\{z_0\}$, the path $\rho_x$ lies in $G$ and connects $z_0$ to $x$;
the head $z_0$ is adjacent to at most two vertices labelled $p$, and if there are two, no leg of the original spider $\mathcal S$ lies between them;
for every endpoint $x$, exactly one neighbor of $x$ that does not lie on $\rho_x$ is labelled $p$.

Passing these checks guarantees that the lifted loops can be recognized automatically.

Example: $f(x)=2x^3-3x^2+1$

Pulled-back web

Compatible paths found by the search

Why this matters

Continuous deformation problem
$\Downarrow$
finite graph + path search + clockwise order
$\Downarrow$
a compact automaton describing infinitely many tree symmetries

Thank you!

Examples database