# Zeros, chaotic ratios and the computational complexity of approximating the
independence polynomial

David de Boer  ,  Pjotr Buys  ,  Lorenzo Guerini  ,  Han Peters  and  Guus
Regts  Korteweg de Vries Institute for Mathematics, University of Amsterdam.
P.O. Box 94248 1090 GE Amsterdam The Netherlands
<EMAIL_ADDRESS>
###### Abstract.

The independence polynomial originates in statistical physics as the partition
function of the hard-core model. The location of the complex zeros of the
polynomial is related to phase transitions, and plays an important role in the
design of efficient algorithms to approximately compute evaluations of the
polynomial.

In this paper we directly relate the location of the complex zeros of the
independence polynomial to computational hardness of approximating evaluations
of the independence polynomial. We do this by moreover relating the location
of zeros to chaotic behaviour of a naturally associated family of rational
functions; the occupation ratios.

Keywords. Hard-core model, independence polynomial, computational complexity,
occupation ratio, normal family

$\ddagger$ DdB and PB are funded by the Netherlands Organisation of Scientific
Research (NWO): 613.001.851

##  1\. Introduction

The independence polynomial of a graph $G=(V,E)$ is defined by

$Z_{G}(\lambda)=\sum_{I\subseteq V}\lambda^{|I|},$

where the sum is taken over all _independent_ subsets $I$ of the vertex set
$V$. Recall that $I$ is said to be independent if no two vertices in $I$ are
connected by an edge. Note that $Z_{G}(1)$ equals the number of independent
subsets of $V$.

In statistical physics the independence polynomial is known as the partition
function of the hard-core model. Of particular interest from a physics
perspective is the location of the zeros of the partition function for certain
classes of graphs. Away from these zeros the free energy is analytic, i.e.
there are no phase transitions in the Lee-Yang sense cf. [YL52].

It turns out that exact computation of the independence polynomial for large
graphs is not feasible for most values of $\lambda$; it is a #P-Hard
problem111The complexity class #P may be seen as the counting version of the
complexity class NP. For example, the problem of deciding whether a graph on
$n$ vertices contains an independent set of size $k$ is a problem in NP, while
the problem of determining the number of independent sets of size $k$ is in
#P. See [Val79, AB09] for further background., cf. [Rot96, Gre00, Vad01]. A
question that has received significant interest is for which
$\lambda\in\mathbb{C}$ there exist polynomial time algorithms that approximate
$Z_{G}(\lambda)$, up to small multiplicative constants. See e.g. [Wei06, SS14,
Bar16, PR17, BGGv20, ALG20] and the references therein.

Surprisingly, much like absence of zeros implies absence of phase transitions
(in the Lee-Yang sense), absence of zeros implies the existence of efficient
algorithms for this computational problem. More formally, on the maximal
simply connected open set containing the origin on which the independence
polynomial does not vanish for all graphs of a given maximum degree $\Delta$
there exists an efficient algorithm for approximating the independence
polynomial [Bar16, PR17]. Let us denote this maximal ‘zero-free’ set by
$\mathcal{U}_{\Delta}$. For real values of $\lambda$ in the complement of the
closure of $\mathcal{U}_{\Delta}$, approximating the partition function is
computationally hard [SS05, SS14, PR19, BGGv20]. In other words, the
absence/presence of complex zeros near the real axis marks a transition in the
computational complexity of approximating the independence polynomial of
graphs of bounded degree $\Delta$ for real values of $\lambda$. The transition
point for positive $\lambda$ coincides with the phase transition for the hard-
core model on the Cayley tree of degree $\Delta$.

Figure 1. The cardioid $\Lambda_{3}$.

A natural question is whether a similar phenomenon manifests itself for non-
real $\lambda$. Bezaková, Galanis, Goldberg and Štefankovič [BGGv20] made an
important contribution towards solving this question, by showing that for any
integer $\Delta\geq 3$ and non-real $\lambda$ outside a certain
cardioid222Although the domain $\Lambda_{\Delta}$ resembles a cardioid, it is
formally not a cardioid. However, as discussed in section 7, it plays an
analogous role as the Main Cardioid of the Mandelbrot set, justifying our use
of the term cardioid., $\Lambda_{\Delta}$, approximation of the independence
polynomial for graphs of bounded degree at most $\Delta$ is computationally
hard. (In fact #P-hard.) See Figure 1 for a picture of $\Lambda_{3}$ and
Definition 2.5 for the definition of $\Lambda_{\Delta}$. Earlier it was shown
by two of the authors of the present paper [PR19] that zeros of the
independence polynomial of graphs of maximum degree at most $\Delta$
accumulate on the entire boundary of $\Lambda_{\Delta}$. In particular the
‘zero-free’ set $\mathcal{U}_{\Delta}$ is contained in the cardioid; their
intersections with the real axis in fact coincide [SS05, PR19]. Buys [Buy21]
however showed that $\Lambda_{\Delta}$ does contain zeros of the independence
polynomial of graphs of bounded degree $\Delta$. This in particular indicates
that the result of [BGGv20] does not fully answer the question how zeros
relate to computational hardness for non-real $\lambda$.

The goal of the present paper is to solve this question by directly relating,
for any fixed integer $\Delta\geq 3$, the zeros for the family of graphs of
maximum degree at most $\Delta$ to the parameters where approximating
evaluations of the independence polynomial is computationally hard. Our result
is obtained by studying a natural family of rational maps associated to this
family of graphs, using techniques and ideas from complex dynamics. We show
that ‘chaotic behaviour’ of this family is equivalent to the presence of
zeros, and implies computational hardness.

###  1.1. Occupation ratios

Given $\Delta\in\mathbb{Z}_{\geq 2}$, we define $\mathcal{G}_{\Delta}$ as the
collection of finite simple rooted graphs $(G,v)$ such that the maximum degree
of $G$ is at most $\Delta$. For $i\in\\{1,\dots,\Delta\\}$ we define
$\mathcal{G}_{\Delta}^{i}=\\{(G,v)\in\mathcal{G}_{\Delta}:\deg(v)\leq i\\}.$
The _occupation ratio_ , or _ratio_ for short, of a rooted graph $(G,v)$ is
defined by the rational function

$R_{G,v}(\lambda):=\frac{Z_{G}^{\mathrm{in}}(\lambda)}{Z_{G}^{\mathrm{out}}(\lambda)},$

where “in” means that in the definition of $Z_{G}(\lambda)$ the sum is taken
only over independent sets $I$ that contain the marked point $v$, while “out”
means that the independent sets do not contain $v$. The ratio is a very useful
tool in studying the zeros of the independence polynomial, see Lemma 2.1
below, and has been key in several of the aforementioned works. The ratio is
also relevant from a statistical physics perspective as it is closely related
to the _free energy_.

When $(G,v)$ is a rooted Cayley tree of depth $n-1$ and down-degree
$d=\Delta-1$, the ratio satisfies

$R_{G,v}(\lambda)=f_{\lambda,d}^{n}(0),$

where

$f_{\lambda,d}(z):=\frac{\lambda}{(1+z)^{d}}$

and throughout the paper we write $f^{n}$ for the $n$-th iterate of the map
$f$.

In this context it is therefore natural to consider $\lambda$ as the parameter
which determines the orbit of the marked point $0$. This type of setting is
often studied in complex dynamical systems, where one is interested in the
sets where the parameter $\lambda$ is _active_ or _passive_. A parameter
$\lambda_{0}$ is said to be passive if the family of rational functions
$\\{\lambda\mapsto f_{\lambda,d}^{\circ n}(0)\\}$ is normal at $\lambda_{0}$,
i.e. there exists a neighborhood such that every sequence in this family has a
subsequence that converges uniformly. A parameter is active if it is not
passive. The most well-known activity-locus is undoubtedly the boundary of the
Mandelbrot set, where the iterates of the functions $z^{2}+c$ are considered.
Following this terminology we define the _activity-locus_ ,
$\mathcal{A}_{\Delta}$, by

$\mathcal{A}_{\Delta}:=\\{\lambda_{0}\in\mathbb{C}\mid\\{\lambda\mapsto
R_{G,v}(\lambda)\mid(G,v)\in\mathcal{G}_{\Delta}\\}\text{ is not locally
normal at }\lambda_{0}\\}.$

Another notion of chaotic behaviour of the ratios appears in the proof of the
result of Bezaková, Galanis, Goldberg and Šefankovič [BGGv20]. An important
step towards proving #P-hardness is showing that for every non-real $\lambda$
outside of the closed cardioid $\overline{\Lambda_{\Delta}}$ the set of values
$\\{R_{G,v}(\lambda)\mid(G,v)\in\mathcal{G}_{\Delta}^{1}\\}$ is dense in
$\hat{\mathbb{C}}$. Motivated by this we define

$\mathcal{D}_{\Delta}:=\\{\lambda\in\mathbb{C}\mid\\{R_{G,v}(\lambda)\mid(G,v)\in\mathcal{G}_{\Delta}^{1}\\}\text{
is dense in }\hat{\mathbb{C}}\\}$

and refer to the closure of $\mathcal{D}_{\Delta}$ as the _density-locus_. We
will prove it is equal to the activity-locus, thereby showing that these two
notions of chaotic behaviour of the ratios are essentially equivalent.

###  1.2. Main result

To state our main result connecting the presence of zeros to computational
hardness, we define the _zero-locus_ as the closure of

$\mathcal{Z}_{\Delta}=\\{\lambda\in\mathbb{C}:Z_{G}(\lambda)=0\text{ for some
}G\in\mathcal{G}_{\Delta}\\}.$

We informally define the _$\\#\mathcal{P}$ -locus_ as the closure of the
collection of $\lambda$ for which approximating $Z_{G}(\lambda)$ is #P-hard
for $G\in\mathcal{G}_{\Delta}$. See subsection 1.3 below for a formal
definition.

The main results of this paper can now be stated succinctly as follows.

######  Main Theorem.

For any integer $\Delta\geq 3$ the zero-locus, the activity-locus and the
density-locus are equal and contained in the $\\#\mathcal{P}$-locus. In other
words:

$\overline{\mathcal{Z}_{\Delta}}=\mathcal{A}_{\Delta}=\overline{\mathcal{D}_{\Delta}}\subseteq\overline{\\#\mathcal{P}_{\Delta}}.$

We remark that the topological structure of the complement of the zero-locus
is not yet understood. We have the following conjecture.

######  Conjecture 1.1.

For each integer $\Delta\geq 3$, the set
$\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$ is connected.

Should this conjecture be true, then by Proposition 4.3 below, we know that
the maximal ‘zero-free’ set containing $0$, $\mathcal{U}_{\Delta}$, equals the
complement of the zero-locus. Since there exists a polynomial time algorithm
[Bar16, PR17] for approximating the independence polynomial on
$\mathcal{U}_{\Delta}$, this would imply with our main theorem a complete
understanding of the computational complexity of approximating the
independence polynomial in terms of the location of the zeros as well as in
terms of chaotic behaviour of the ratios.

######  Remark 1.2.

We note that [PR20] and [BGPR20] combined implicitly contain similar
equivalent characterizations for the Lee-Yang zeros of the partition function
of the ferromagnetic Ising model on bounded degree graphs. In that setting the
complement of the zero-locus is in fact connected when the edge interaction
parameter is sub-critical.

###  1.3. Computational complexity

We formally state here the computational problems we are interested in. We
denote by $\mathbb{Q}[i]$ the collection of complex numbers with rational real
and imaginary part. Let $\lambda\in\mathbb{Q}[i]$, $\Delta\in\mathbb{N}$ and
consider the following computational problems.

  * _Name_

#Hard-CoreNorm($\lambda,\Delta)$

  * _Input_

A graph $G$ of maximum degree at most $\Delta$.

  * _Output_

If $Z_{G}(\lambda)\neq 0$ the algorithm must output a rational number $N$ such
that $N/1.001\leq|Z_{G}(\lambda)|\leq 1.001N$. If $Z_{G}(\lambda)=0$ the
algorithm may output any rational number.

  * _Name_

#Hard-CoreArg($\lambda,\Delta)$

  * _Input_

A graph $G$ of maximum degree at most $\Delta$.

  * _Output_

If $Z_{G}(\lambda)\neq 0$ the algorithm must output a rational number $A$ such
that $|A-a|\leq\pi/3$ for some $a\in\arg(Z_{G}(\lambda)$. If
$Z_{G}(\lambda)=0$ the algorithm may output any rational number.

We can now formally define the $\\#\mathcal{P}$-locus, as the closure of the
set,

$\\#\mathcal{P}_{\Delta}:=\\{\lambda\in\mathbb{Q}[i]:\text{ the problem
\\#Hard-CoreNorm($\lambda,\Delta)$ is \\#P-hard}\\}.$

We remark that in the definition of $\\#\mathcal{P}_{\Delta}$ we could also
replace #Hard-CoreNorm$(\lambda,\Delta)$ by #Hard-CoreArg$(\lambda,\Delta)$
without altering the validity of Theorem Main Theorem.

We moreover note that the constant $1.001$ is rather arbitrary. It originates
from [BGGv20]. As remarked there the constant can be replaced by any other
constant. Let us quickly explain the idea. If say #Hard-
CoreNorm$(\lambda,\Delta)$ is #P-hard, but there would be a polynomial time
algorithm for the problem with $1.001$ replaced by $1.001^{2}$, then we could
run this algorithm on the disjoint union of two copies of the same graph $G$
obtaining an a $1.001^{2}$ approximation to the norm of $Z_{G\cup
G}(\lambda)=Z_{G}(\lambda)^{2}$. This would immediately gives us a
$1.001$-approximation to the norm of $Z_{G}(\lambda)$. Since the number of
vertices of $G\cup G$ is polynomial in the number of vertices of $G$, we would
thus also get a polynomial time algorithm for the problem with constant
$1.001$.

Organization. After introducing preliminary definitions and results in section
2, we treat the degree $\Delta=2$ case in section 3. While the equalities
between different loci are different when $\Delta=2$, the explicit
descriptions of the zero- and activity-locus will be used in the higher degree
cases.

In section 4 we prove the equality of the zero-locus and the activity-locus.
The inclusion of the latter in the former is actually an immediate consequence
of Montel’s Theorem, and proved earlier in Corollary 2.12. We end that section
by showing that connected components of the complement of the zero-locus are
simply connected.

In section 5 we prove the equality of the activity- and the density-locus, and
in section 6 we prove that the density-locus is contained in the
$\\#\mathcal{P}$-locus.

We end our paper by discussing a special subclass of graphs: the finite Cayley
trees of fixed down-degree $\Delta-1$. In this setting classical results from
complex dynamical systems can be used to obtain a precise description of the
zero- and activity-locus. While there zeros do not lie in the activity-locus,
the activity-locus equals the accumulation set of the zeros.

##  2\. Preliminaries

In this section we collect some preliminary results and conventions that will
be used in the remainder of the paper. The results in this section are not
necessarily new, but often cannot be found in the literature in the exact way
they are stated here. For convenience of the reader we include proofs,
especially when the methods are similar to those used later in the paper.

###  2.1. Ratios of graphs and trees.

Recall that for a rooted graph $(G,v)$ the occupation ratio is defined as the
following rational function in $\lambda$

$R_{G,v}(\lambda)=\frac{Z_{G}^{\mathrm{in}}(\lambda)}{Z_{G}^{\mathrm{out}}(\lambda)}.$

We note that
$Z_{G}(\lambda)=Z_{G}^{\mathrm{in}}(\lambda)+Z_{G}^{\mathrm{out}}(\lambda)$,
which implies that $Z_{G}(\lambda)=0$ if and only if $R_{G,v}(\lambda)=-1$,
unless $Z_{G,v}^{\mathrm{in}}(\lambda)$ and $Z_{G,v}^{\mathrm{out}}(\lambda)$
both vanish, in which case the value of the rational function
$R_{G,v}(\lambda)$ may not equal $-1$. The next lemma will show that we can
often ignore this difficulty.

We will write $G-v$ for the graph $G$ with vertex $v$ removed, and $G-N[v]$
for the graph with $N[v]$ removed, where $N[v]=\\{u\in V(G):\\{u,v\\}\in
E(G)\\}\cup\\{v\\}$ is the closed neighborhood of $v$. We observe that
$Z_{G,v}^{out}(\lambda)=Z_{G-v}(\lambda)$, and similarly
$Z_{G,v}^{in}(\lambda)=\lambda\cdot Z_{G-N[v]}(\lambda)$.

######  Lemma 2.1.

Let $\lambda\in\mathbb{C}^{*}$. The following three statements are equivalent.

  1. (1)

There exists a graph $G$ of maximum degree at most $\Delta$ for which
$Z_{G}(\lambda)=0$.

  2. (2)

There exists a rooted graph $(G,v)\in\mathcal{G}_{\Delta}$ for which
$R_{G,v}(\lambda)=-1$.

  3. (3)

There exists a rooted graph $(G,v)\in\mathcal{G}_{\Delta}$ for which
$R_{G,v}(\lambda)\in\\{-1,0,\infty\\}$.

###### Proof.

Assume that (1) holds, then there is a graph $G$ of maximum degree at most
$\Delta$ for which $Z_{G}(\lambda)=0$. Without loss of generality we can
assume $G\in\mathcal{G}_{\Delta}$ satisfies $Z_{G}(\lambda)=0$ and has a
minimal number of vertices, i.e. for any graph $H\in\mathcal{G}_{\Delta}$ with
$Z_{H}(\lambda)=0$ we have $|V(G)|\leq|V(H)|$. For any vertex $v\in V(G)$ we
have

$0=Z_{G}(\lambda)=Z_{G,v}^{in}(\lambda)+Z_{G,v}^{out}(\lambda).$

As $|V(G-v)|<V(G)$ we have $Z_{G,v}^{out}(\lambda)=Z_{G-v}(\lambda)\neq 0$,
which implies $R_{G,v}(\lambda)=-1$. Thus (2) holds. Trivially, if (2) holds
then also (3) holds. To complete the proof we will assume (3) holds and show
that (1) follows.

Assume there is a rooted graph $(G,v)\in\mathcal{G}_{\Delta}$ for which
$R_{G,v}(\lambda)\in\\{-1,0,\infty\\}$. If $R_{G,v}(\lambda)=-1$, we either
have $Z_{G,v}^{out}(\lambda)=0$, in which case (1) follows, or
$Z_{G,v}^{out}(\lambda)\neq 0$, in which case
$Z_{G,v}^{in}(\lambda)=-Z_{G,v}^{out}(\lambda)$ and (1) follows as well. If
$R_{G,v}(\lambda)=\infty$ we have $Z_{G,v}^{out}(\lambda)=0$. As
$Z_{G,v}^{out}(\lambda)=Z_{G-v}(\lambda)$ we see (1) holds. The final case is
$R_{G,v}(\lambda)=0$, in which case we have
$0=Z_{G,v}^{in}(\lambda)=\lambda\cdot Z_{G-N[v]}(\lambda)$. Now as
$\lambda\neq 0$, we must have $Z_{G-N[v]}(\lambda)=0$, which concludes the
proof. ∎

Note that for $\lambda=0$ we have $R_{G,v}(\lambda)=0$ and $Z_{G}(\lambda)=1$
for any graph $G$ and any vertex $v\in V(G)$. Hence for $\lambda=0$,
statements (1) and (2) in Lemma 2.1 are still equivalent, while statement (3)
is not equivalent to (1) or (2).

The following result due to Bencs [Ben18] will play an important role in this
paper.

######  Theorem 2.2.

Let $(G,v)\in\mathcal{G}_{\Delta}^{i}$ be a rooted connected graph. Then there
is a rooted tree $(T,u)\in\mathcal{G}_{\Delta}^{i}$ and induced graphs
$G_{1},\ldots,G_{k}$ of $G$ such that

  * (i)

$Z_{T}=Z_{G}\prod_{i=1}^{k}Z_{G_{i}}$,

  * (ii)

$R_{G,v}=R_{T,u}$.

The following result is a consequence.

######  Lemma 2.3.

Let $\lambda\in\mathbb{C}$ and $(G,v)\in\mathcal{G}_{\Delta}$ with
$Z_{G}(\lambda)=0$. Then there is a rooted tree
$(T,u)\in\mathcal{G}_{\Delta}^{1}$ such that $Z_{T}(\lambda)=0$ and
$R_{T,u}(\lambda)=-1$.

###### Proof.

Note that for any graph $G$ we have $Z_{G}(0)=1$, so we can assume
$\lambda\neq 0$. By Lemma 2.1 there exists a rooted graph
$(G,v)\in\mathcal{G}_{\Delta}$ such that $R_{G,v}(\lambda)=-1$. By Theorem
2.2(i) we see there is a rooted tree $(T,u)\in\mathcal{G}_{\Delta}$ with
$Z_{T}(\lambda)=0$. It follows there is a tree $\tilde{T}$ of maximum degree
$\Delta$ with a minimal number of vertices such that
$Z_{\tilde{T}}(\lambda)=0$. For $\tilde{T}$ and any vertex $v\in V(\tilde{T})$
we have $R_{\tilde{T},v}(\lambda)=-1$. The lemma follows by choosing $v$ a
leaf of $\tilde{T}$. ∎

At a later stage we will need to worry about the degree of the root vertex in
our definition of the activity- and density-locus. We therefore introduce some
definitions to facilitate their discussion.

Fix an integer $\Delta\geq 2$ throughout. For $i=1,\ldots,\Delta$ we denote
the family of ratios with root degree at most $i$ by

$\mathcal{R}^{i}_{\Delta}:=\\{R_{G,v)}\mid(G,v)\in\mathcal{G}^{i}_{\Delta}\\}.$

We just write $\mathcal{R}_{\Delta}$ instead of
$\mathcal{R}^{\Delta}_{\Delta}$. For a given $\lambda\in\mathbb{C}$, we denote
the set of values of these ratios by

$\mathcal{R}^{i}_{\Delta}(\lambda):=\\{R_{G,v)}(\lambda)\mid(G,v)\in\mathcal{G}^{i}_{\Delta}\\}.$

Then we define $\mathcal{A}^{i}_{\Delta}$ to be the collection of
$\lambda_{0}$ at which the family $\mathcal{R}^{i}_{\Delta}$ is not normal. We
just write $\mathcal{A}_{\Delta}$ instead of $\mathcal{A}^{\Delta}_{\Delta}$.
Finally, we introduce $\mathcal{D}_{\Delta}^{i}$ to be the collection of
$\lambda$ for which the set $\mathcal{R}^{i}_{\Delta}(\lambda)$ is dense in
$\mathbb{C}$. Note that we denote $\mathcal{D}^{1}_{\Delta}$ by
$\mathcal{D}_{\Delta}$ (as opposed to the above convention).

###  2.2. Graph manipulations and definition of the cardioid

The recursion formula given in the following lemma is well known.

######  Lemma 2.4.

Let $T=(V,E)$ be a tree and $v$ a vertex of $T$. Suppose $v$ is connected to
$d\geq 1$ other vertices $u_{1},\dots,u_{d}$. Denote $T_{s}$ for the tree that
is the connected component of $T-v$ containing $u_{s}$. Then we have

$R_{T,v}(\lambda)=\frac{\lambda}{\prod_{s=1}^{d}(1+R_{T_{s},u_{s}}(\lambda))}.$
(1)

###### Proof.

We have

$\frac{Z_{T,v}^{in}(\lambda)}{Z_{T,v}^{out}(\lambda)}=\lambda\frac{Z_{T-N[v]}(\lambda)}{Z_{T-v}(\lambda)}=\lambda\prod_{s=1}^{d}\frac{Z_{T_{s},u_{s}}^{out}(\lambda)}{Z_{T_{s}}(\lambda)}=\lambda\prod_{s=1}^{d}\frac{Z_{T_{s},u_{s}}^{out}(\lambda)}{Z_{T_{s},u_{s}}^{out}(\lambda)+Z_{T_{s},u_{s}}^{in}(\lambda)},$
(2)

where in the second equality we use that the partition function of a graph
factors into the partition functions of its connected components. By dividing
for each $s\in\\{1,\ldots,d\\}$ the denominator and enumerator of the right
hand side of equation (2) by $Z_{T_{s},u_{s}}^{out}(\lambda)$ we obtain the
desired formula. ∎

This lemma implies the claim from the introduction that the ratios of Cayley
trees are given by iterating $f_{\lambda,d}(z)=\frac{\lambda}{(1+z)^{d}}$. We
refer to Section 7 for an in-depth discussion of Cayley trees and their
associated dynamics.

######  Definition 2.5.

Define the cardioid $\Lambda_{\Delta}$ as the closure of the set of parameters
$\lambda$ for which $f_{\lambda,d}$ has an attracting fixed point.

Note that $0\in\Lambda_{\Delta}$. One can show, see Section 2.1 in [PR19],
that

$\Lambda_{\Delta}=\bigg{\\{}\frac{z}{(1-z)^{\Delta}}\ |\
|z|\leq\frac{1}{\Delta-1}\bigg{\\}}.$

Taking $z=\tfrac{-1}{\Delta-1}$, we observe that

$\lambda^{*}(\Delta)=\frac{-(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$

is the intersection point of $\Lambda_{\Delta}$ with the negative real line.

Let $G=(V,E)$ be a graph and let $(G_{i},v_{i})$ be rooted graphs for $i\in
V$. We refer to the graph obtained from $G$ and the $G_{i}$ by identifying
each vertex $i\in V$ with $v_{i}$ as _implementing_ the $G_{i}$ in $G$, see
Figure 2. The next lemmas describe the effect on the ratios for various
choices of $G$ and $G_{i}.$

######  Lemma 2.6.

Let $P_{n}$ denote the path on $n$ vertices. Let $(G_{i},v_{i})$ be rooted
graphs for $i\in\\{1,\ldots,n\\}$ and denote
$\mu_{i}(\lambda)=R_{G_{i},v_{i}}(\lambda)$. Let $\tilde{P}_{n}$ be the graph
obtained by implementing the $G_{i}$ in $P_{n}$. Then

$R_{\tilde{P}_{n},v_{n}}(\lambda)=(f_{\mu_{n}(\lambda)}\circ\cdots\circ
f_{\mu_{1}(\lambda)})(0),$

where $f_{\mu}(z)=\frac{\mu}{1+z}$.

###### Proof.

We use induction on $n$. For $n=1$, by definition we have
$R_{G_{1},v_{1}}(\lambda)=\mu_{1}(\lambda)=f_{\mu_{1}(\lambda)}(0)$. As
$\tilde{P}_{1}=G_{1}$, we have
$R_{\tilde{P}_{1},v_{1}}(\lambda)=R_{G_{1},v_{1}}(\lambda)$. The base case
follows.

Suppose the statement holds for some $n\geq 1$. The vertex $v_{n+1}$ has 1
neighbor that is part of the path $P_{n}$. Let us denote that neighbor as
$v_{n}$. It follows that

$\displaystyle R_{\tilde{P}_{n+1},v_{n+1}}(\lambda)$
$\displaystyle=\frac{Z^{in}_{\tilde{P}_{n+1},v_{n+1}}(\lambda)}{Z^{out}_{\tilde{P}_{n+1},v_{n+1}}(\lambda)}=\frac{Z^{in}_{G_{n+1},v_{n+1}}(\lambda)}{Z^{out}_{G_{n+1},v_{n+1}}(\lambda)}\cdot\frac{Z^{out}_{\tilde{P}_{n},v_{n}}(\lambda)}{Z_{\tilde{P}_{n},v_{n}}(\lambda)}$
$\displaystyle=R_{G_{n+1},v_{n+1}}(\lambda)\cdot\frac{Z^{out}_{\tilde{P}_{n},v_{n}}(\lambda)}{Z^{out}_{\tilde{P}_{n},v_{n}}(\lambda)+Z^{in}_{\tilde{P}_{n},v_{n}}(\lambda)}=\frac{R_{G_{n+1},v_{n+1}}(\lambda)}{1+R_{\tilde{P}_{n},v_{n}}(\lambda)}$
$\displaystyle=f_{\mu_{n+1}(\lambda)}(R_{\tilde{P}_{n},v_{n}}(\lambda)),$

where in the second equality we use that the partition function of a graph
factors into the partition functions of its connected components.

By the induction hypothesis we have

$R_{\tilde{P}_{n},v_{n}}(\lambda)=(f_{\mu_{n}(\lambda)}\circ\cdots\circ
f_{\mu_{1}(\lambda)})(0),$

from which it follows that

$R_{\tilde{P}_{n+1},v_{n+1}}(\lambda)=(f_{\mu_{n+1}(\lambda)}\circ
f_{\mu_{n}(\lambda)}\circ\cdots\circ f_{\mu_{1}(\lambda)})(0),$

completing the proof. ∎

$v_{1}$$G_{1}$$v_{2}$$G_{2}$$v_{3}$$G_{3}$$v_{n}$$G_{n}$ Figure 2. The graph
$\tilde{P}_{n}$ in Lemma 2.6

######  Remark 2.7.

Note that if the graphs $G_{i}$ in Lemma 2.6 are all of maximum degree
$\Delta$ and the roots $v_{i}$ have degree at most $\Delta-2$ for
$i\in\\{2,\ldots,n-1\\}$ and at most degree $\Delta-1$ for $i\in\\{1,n\\}$,
then the graph $\tilde{P}_{n}$ is also of maximum degree $\Delta$.

######  Lemma 2.8.

Let $G=(V,E)$ be a graph and denote $n=|V|$. Let $(H,v)$ be a rooted graph.
Let $\tilde{G}=(\tilde{V},\tilde{E})$ be obtained from $G$ by implementing $n$
copies of $(H,v)$ in $G$. Then for any $w\in V$ we have

$\frac{Z_{\tilde{G},w}(\lambda)}{(Z_{H,v}^{out}(\lambda))^{n}}=Z_{G,w}(R_{H,u}(\lambda))$
(3)

and

$R_{\tilde{G},w}(\lambda)=R_{G,w}(R_{H,v}(\lambda)).$ (4)

###### Proof.

We have

$\frac{Z_{\tilde{G},w}^{in}(\lambda)}{(Z_{H,v}^{out}(\lambda))^{n}}=\frac{\sum_{\begin{subarray}{c}I\in\mathcal{I}(G)\\\
w\in
I\end{subarray}}Z_{H,v}^{in}(\lambda)^{|I|}Z_{H,v}^{out}(\lambda)^{n-|I|}}{(Z_{H,v}^{out}(\lambda))^{n}}=Z_{G,w}^{in}(R_{H,v}(\lambda))$
(5)

and

$\frac{Z_{\tilde{G},w}^{out}(\lambda)}{(Z_{H,v}^{out}(\lambda))^{n}}=\frac{\sum_{\begin{subarray}{c}I\in\mathcal{I}(G)\\\
w\not\in
I\end{subarray}}Z_{H,v}^{in}(\lambda)^{|I|}Z_{H,v}^{out}(\lambda)^{n-|I|}}{(Z_{H,v}^{out}(\lambda))^{n}}=Z_{G,w}^{out}(R_{H,v}(\lambda)).$
(6)

Equality (3) follows from equalities (5) and (6) noting that for any graph $W$
and any vertex $u$ of $W$ we have
$Z_{W}(\lambda)=Z_{W,u}^{in}(\lambda)+Z_{W,u}^{out}(\lambda)$. Equality (4)
follows from equalities (5) and (6) and the definition of the ratio. ∎

We will also need the following slight variation on Lemma 2.4.

######  Lemma 2.9.

Let $(G_{1},v_{1})$ and $(G_{2},v_{2})$ be rooted graphs, and define the
rooted graph $(\tilde{G},\tilde{v})$ by identifying the roots $v_{1}$ and
$v_{2}$. Then

$R_{\tilde{G},\tilde{v}}(\lambda)=\lambda^{-1}\cdot
R_{G_{1},v_{1}}(\lambda)\cdot R_{G_{2},v_{2}}(\lambda).$

###### Proof.

We compute

$R_{\tilde{G},\tilde{v}}(\lambda)=\frac{Z_{\tilde{G},\tilde{v}}^{in}(\lambda)}{Z_{\tilde{G},\tilde{v}}^{out}(\lambda)}=\frac{Z_{G_{1},v_{1}}^{in}(\lambda)\cdot
Z_{G_{2},v_{2}}^{in}(\lambda)\cdot\lambda^{-1}}{Z_{G_{1},v_{1}}^{out}(\lambda)\cdot
Z_{G_{2},v_{2}}^{out}(\lambda)}=\lambda^{-1}\cdot
R_{G_{1},v_{1}}(\lambda)\cdot R_{G_{2},v_{2}}(\lambda).$

∎

###  2.3. The Shearer region

Denote the open disk around $0$ with radius
$\frac{(\Delta-1)^{\Delta-1}}{\Delta^{\Delta}}$ by $B_{\Delta}$. This region,
also known as the Shearer region, is the maximal open disk centered around $0$
that is zero free for the independence polynomial of graphs of maximum degree
$\Delta$ [SS05, She85]. We will show the Shearer region is also disjoint from
the activity-locus and the density-locus, which will later be used to deal
with the $\lambda=0$ case in the proof of our main theorem.

######  Lemma 2.10.

Let $\Delta\geq 2$ be an integer. Then $B_{\Delta}$ is disjoint from the
activity-locus, the zero-locus and the density-locus, i.e., we have
$B_{\Delta}\cap\overline{\mathcal{D}_{\Delta}}=B_{\Delta}\cap\mathcal{A}_{\Delta}=B_{\Delta}\cap\overline{\mathcal{Z}_{\Delta}}=\emptyset$.

###### Proof.

We claim that for any rooted graph $(G,v)\in\mathcal{G}_{\Delta}$ and any
$\lambda\in B_{\Delta}$ we have

$|R_{G,v}(\lambda)|<\begin{cases}\frac{1}{\Delta}\ \ \ \ \ \text{ if
}\deg(v)\leq\Delta-1,\\\ \frac{1}{\Delta-1}\ \ \text{ otherwise.}\end{cases}$

By Theorem 2.2 we can equivalently work with rooted trees
$(T,v)\in\mathcal{G}_{\Delta}$ instead of rooted graphs.

We will proof the claim by induction on the number of vertices of $T$. If
$|V(T)|=1$, we have $\deg(v)=0$ and therefore $R_{T,v}(\lambda)=\lambda$. The
claim then follows as
$\frac{(\Delta-1)^{(\Delta-1)}}{\Delta^{\Delta}}<\frac{1}{\Delta}$ for all
$\Delta\geq 2$. Suppose the claim holds for all rooted trees
$(T,v)\in\mathcal{G}_{\Delta}$ with $|V(T)|\leq n$ for some $n\geq 1$. Let
$(\tilde{T},\tilde{v})\in\mathcal{G}_{\Delta}$ be a rooted tree with $n+1$
vertices. Denote the $d$ children of $\tilde{v}$ as $u_{1},\ldots,u_{d}$ and
denote $(T_{i},u_{i})$ for the rooted subtree of $\tilde{T}$ with root
$u_{i}$. By Lemma 2.4 we have

$R_{\tilde{T},\tilde{v}}(\lambda)=\frac{\lambda}{\prod_{i=1}^{d}(1+R_{T_{i},u_{i}}(\lambda))}.$

We note that each $(T_{i},u_{i})$ has at most $n$ vertices, hence the
induction hypotheses applies. Furthermore in $T_{i}$ we have
$\deg(u_{i})\leq\Delta-1$ as $\tilde{T}$ has maximum degree at most $\Delta$.
Thus we see

$\displaystyle|R_{\tilde{T},\tilde{v}}(\lambda)|$
$\displaystyle=\frac{|\lambda|}{\prod_{i=1}^{d}|1+R_{T_{i},u_{i}}(\lambda)|}\leq\frac{|\lambda|}{\prod_{i=1}^{d}(1-|R_{T_{i},u_{i}}(\lambda)|)}$
$\displaystyle<\frac{|\lambda|}{(1-\frac{1}{\Delta})^{d}}=\frac{\Delta^{d}|\lambda|}{(1-\Delta)^{d}}<\frac{(\Delta-1)^{\Delta-1-d}}{\Delta^{\Delta-d}}.$

Now if $d\leq\Delta-1$, we see
$\frac{(\Delta-1)^{\Delta-1-d}}{\Delta^{\Delta-d}}<\frac{1}{\Delta}$ hence the
claim follows for that case. If $d=\Delta$ we have
$\frac{(\Delta-1)^{\Delta-1-d}}{\Delta^{\Delta-d}}=\frac{1}{\Delta-1}$, which
proves the claim.

It follows from the claim above that the family of ratios
$\mathcal{R}_{\Delta}$ maps $B_{\Delta}$ into the open unit disk, for all
$\Delta\geq 2$. So clearly $B_{\Delta}\cap\mathcal{D}_{\Delta}=\emptyset$. As
$B_{\Delta}$ is open, we have
$B_{\Delta}\cap\overline{\mathcal{D}_{\Delta}}=\emptyset$.

By Montel’s Theorem the family $\mathcal{R}_{\Delta}$ is normal on
$B_{\Delta}$, so $B_{\Delta}\cap\mathcal{A}_{\Delta}=\emptyset$. We showed for
all rooted graphs $(G,v)\in\mathcal{G}_{\Delta}$ that
$|R_{G,v}(\lambda)|<\frac{1}{\Delta-1}\leq 1$, hence the ratio will never
equal $-1$. For $\lambda\neq 0$, we see by Lemma 2.1 that
$\lambda\not\in\mathcal{Z}_{\Delta}$. For $\lambda=0$ we note that
$Z_{G}(0)=1$ for any graph $G\in\mathcal{G}_{\Delta}$. It follows that
$B_{\Delta}\cap\mathcal{Z}_{\Delta}=\emptyset$. Again, as $B_{\Delta}$ is
open, we have $B_{\Delta}\cap\overline{\mathcal{Z}_{\Delta}}=\emptyset$. This
completes the proof. ∎

######  Remark 2.11.

We note that on the negative real line the Shearer region agrees with the
interior of the cardioid, i.e we have $\mathbb{R}_{\leq 0}\cap
B_{\Delta}=\mathbb{R}_{\leq 0}\cap\operatorname{int}{\Lambda_{\Delta}}$ for
all integers $\Delta\geq 3$.

Lemmas 2.10 and 2.1 together imply one of the inclusions in our main result.

######  Corollary 2.12.

For all $\Delta\geq 2$ the activity-locus is contained in the zero-locus, i.e.
$\mathcal{A}_{\Delta}\subseteq\overline{\mathcal{Z}_{\Delta}}$.

###### Proof.

Equivalently, we want to show that for any
$\lambda\in\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$ the family
$\mathcal{R}_{\Delta}$ is normal at $\lambda$. By Lemma 2.10 this is the case
for $\lambda=0$ and thus we assume that $\lambda\neq 0$. Take a sufficiently
small neighborhood $U$ around $\lambda$ such that $0\not\in U$ and
$U\cap\overline{\mathcal{Z}_{\Delta}}=\emptyset$. It follows from Lemma 2.1
that the family $\mathcal{R}_{\Delta}$ avoids $\\{-1,0,\infty\\}$ for all
$\lambda^{\prime}\in U$. Hence by Montel’s Theorem the family is normal on
$U$. ∎

##  3\. Graphs with maximum degree at most two

In this section we will deal with graphs of maximum degree at most two, in
other words graphs for which each component is a path or a cycle. We will show
that

$\overline{\mathcal{Z}_{2}}=\mathcal{A}_{2}=(-\infty,-1/4]\quad\text{ and
}\quad\mathcal{D}_{2}^{1}=\mathcal{D}_{2}^{2}=\emptyset.$

An explicit description of $\mathcal{Z}_{2}$ was already known [HL72, SS05];
we provide a new proof for the sake of completeness.

Note that this is in contrast to the situation for $\Delta\geq 3$ as stated in
Theorem Main Theorem. It follows from Lemma 2.3 that $\mathcal{Z}_{2}$ is
equal to the set of $\lambda$ for which there is a
$(T,v)\in\mathcal{G}_{2}^{1}$, with $T$ a tree, such that
$R_{T,v}(\lambda)=-1$. The collection $\mathcal{G}_{2}^{1}$ consists of rooted
graphs where the component containing the root is a path rooted at an
endpoint. Let $(P_{n},v_{n})$ denote a path on $n$ vertices rooted at an
endpoint $v_{n}$. If we let $f_{\lambda}(z)=\lambda/(1+z)$ then it follows
from Lemma 2.6 that $R_{P_{n},v_{n}}(\lambda)=f_{\lambda}^{n}(0)$. For fixed
$\lambda$ the map $f_{\lambda}$ is a Möbius transformation and therefore we
first review some properties of Möbius transformation.

###  3.1. Möbius transformations

Everything that is done in this section can for example be found in [Bea95,
Section 4.3]. Let $\mathcal{M}$ denote the group of Möbius transformations
with composition as group operation and let $\textrm{GL}_{2}(\mathbb{C})$
denote the group of $2\times 2$ invertible matrices with complex entries. The
following map is a surjective group homomorphism.

$\Phi:\textrm{GL}_{2}(\mathbb{C})\to\mathcal{M},\quad\Big{(}\begin{array}[]{cc}a&b\\\
c&d\\\ \end{array}\Big{)}\mapsto\Big{(}z\mapsto\frac{az+b}{cz+d}\Big{)}.$

For any $g\in\mathcal{M}$ take an element $A\in\Phi^{-1}(\\{g\\})$ and define
$\operatorname{tr}^{2}(g)=\operatorname{tr}(A)^{2}/\det(A)$. This quantity
does not depend on the choice of $A$ and thus $\operatorname{tr}^{2}$ is a
well defined function on $\mathcal{M}$. We say that elements
$f,g\in\mathcal{M}$ are conjugate if there exists an $h\in\mathcal{M}$ such
that $f=h\circ g\circ h^{-1}$.

######  Lemma 3.1 ([Bea95, Theorem 4.3.4]).

Let $f,g\in\mathcal{M}$ not equal to the identity. The maps $f,g$ are
conjugate if and only if $\operatorname{tr}^{2}(f)=\operatorname{tr}^{2}(g)$.
It follows that $g$ is conjugate to

  * •

a rotation $z\mapsto e^{i\theta}\cdot z$ for some $\theta\in(0,\pi]$ if and
only if $\operatorname{tr}^{2}(g)\in[0,4)$;

  * •

the translation $z\mapsto z+1$ if and only if $\operatorname{tr}^{2}(g)=4$;

  * •

a multiplication $z\mapsto\xi\cdot z$ for some $\xi\in\mathbb{C}^{*}$ with
$|\xi|<1$ if and only if
$\operatorname{tr}^{2}(g)\in\mathbb{C}\setminus[0,4]$.

The map $g$ is said to be elliptic, parabolic or loxodromic in these three
cases respectively.

Observe that if $f=h\circ g\circ h^{-1}$ then $f^{n}=h\circ g^{n}\circ
h^{-1}$. It follows that, to understand the dynamical behaviour of a Möbius
transformation $g$, it is enough to understand the dynamical behaviour of any
element in the conjugacy class of $g$. If $g$ is loxodromic then it has two
distinct fixed points in $\widehat{\mathbb{C}}$, one of which is attracting
and the other is repelling. Under iteration of $g$ the orbit of every initial
value except for the repelling fixed point converges to the attracting fixed
point. If $g$ is parabolic then $g$ has a unique fixed point, and under
iteration of $g$ all orbits converge to this fixed point. If $g$ is elliptic
then $g$ is conjugate to a rotation $z\mapsto e^{i\theta}\cdot z$. We say that
$g$ is conjugate to a _rational rotation_ if $\theta$ is a rational multiple
of $\pi$ and otherwise we say that $g$ is conjugate to an _irrational
rotation_. If $g$ is conjugate to a rational rotation there is a positive
integer $n$ such that $g^{n}$ is equal to the identity. If $g$ is conjugate to
an irrational rotation it has two fixed points, say $p,q$, and
$\widehat{\mathbb{C}}\setminus\\{p,q\\}$ is foliated by generalized circles on
which $g$ acts conjugately to an irrational rotation.

We end this subsection by classifying $f_{\lambda}$ in terms of its parameter.

######  Lemma 3.2.

The Möbius transformation $f_{\lambda}$ is

  * •

elliptic if $\lambda\in(-\infty,-1/4)$;

  * •

parabolic if $\lambda=-1/4$;

  * •

loxodromic if $\lambda\in\mathbb{C}^{*}\setminus(-\infty,-1/4]$.

###### Proof.

This follows from Lemma 3.1 and the fact that
$\operatorname{tr}^{2}(f_{\lambda})=-1/\lambda$. ∎

###  3.2. Determining the zero and activity-locus

In this subsection we we will show that both $\overline{\mathcal{Z}_{2}}$ and
$\mathcal{A}_{2}^{1}$ are equal to $(-\infty,-1/4]$. By definition we have
$\mathcal{A}_{2}^{1}\subseteq\mathcal{A}_{2}$ and by Corollary 2.12 we have
$\mathcal{A}_{2}\subseteq\overline{\mathcal{Z}_{2}}$, hence it will follow
that $\mathcal{A}_{2}$ is equal to $(-\infty,-1/4]$ as well.

######  Lemma 3.3.

Zeros of $Z_{G}$ for graphs $G\in\mathcal{G}_{2}$ form a dense subset of the
interval $(-\infty,-1/4)$, hence $\overline{\mathcal{Z}_{2}}=(-\infty,-1/4]$.

###### Proof.

We claim that $\lambda\in\mathcal{Z}_{2}$ if and only if $f_{\lambda}$ is
conjugate to a rational rotation.

First suppose that $\lambda\in\mathcal{Z}_{2}$. Then, by Lemma 2.3, there is
an $n\geq 1$ such that for the path on $n$ vertices $P_{n}$ rooted at the
endpoint $v_{n}$ we have $R_{P_{n},v_{n}}(\lambda)=-1$ and thus
$f_{\lambda}^{n}(0)=-1$. Because $f_{\lambda}^{2}(-1)=0$ regardless of the
value of $\lambda$ we obtain that $f_{\lambda}^{n+2}(0)=0$. This means that
$0$ is a periodic point of $f_{\lambda}$ of period strictly larger than $1$.
This can only occur if $f_{\lambda}$ is conjugate to a rational rotation, as
is explained in Section 3.1.

Suppose that $f_{\lambda}$ is conjugate to a rational rotation. Note that this
implies that $\lambda$ is not equal to zero. Take the smallest positive
integer $n$ such that $f_{\lambda}^{n}$ is equal to the identity and thus
specifically $f_{\lambda}^{n}(0)=0$. Note that $f_{\lambda}(0)=\lambda$ and
$f_{\lambda}^{2}(0)=\lambda/(1+\lambda)$ and thus $n\geq 3$. Since
$f_{\lambda}^{-2}(0)=-1$ we obtain that
$R_{P_{n-2,v_{n-2}}}(\lambda)=f_{\lambda}^{n-2}(0)=-1$. It follows from the
proof of Lemma 2.1 that $\lambda$ is a root of $Z_{P_{n-2}}$.

Parameters $\lambda$ for which $f_{\lambda}$ is conjugate to a rational
rotation lie dense in the set of parameters for which $f_{\lambda}$ is
conjugate to any rotation. It follows from Lemma 3.2 that
$\overline{\mathcal{Z}_{2}}=(-\infty,-1/4]$. ∎

We remark that $\operatorname{tr}^{2}$ of the map that sends $z$ to
$e^{i\theta}\cdot z$ is equal to $2(1+\cos(\theta))$. By comparing this to the
value of $\operatorname{tr}^{2}(f_{\lambda})$ it follows from the previous
proof that

$\mathcal{Z}_{2}=\left\\{\frac{-1}{2(1+\cos(t\pi))}:t\in(0,1)\cap\mathbb{Q}\right\\}.$

We will now prove the final lemma needed to determine $\mathcal{A}_{2}$.

######  Lemma 3.4.

The family $\mathcal{R}_{2}^{1}$ is not normal around any
$\lambda\in(-\infty,-1/4]$, i.e. $(-\infty,-1/4]\subseteq\mathcal{A}_{2}^{1}$.

###### Proof.

Recall that

$\mathcal{R}_{2}^{1}=\\{R_{P_{n},v_{n}}:n\geq 1\\}=\\{\lambda\mapsto
f_{\lambda}^{n}(0):n\geq 1\\}.$

Take a $\lambda_{0}\in(-\infty,-1/4]$ and suppose for the sake of
contradiction that there exists a neighborhood $U$ of $\lambda_{0}$ on which
$\mathcal{R}_{2}^{1}$ is normal. We take $U$ connected and sufficiently small
so that it does not contain $0$, and $0$ is not a fixed point of $f_{\lambda}$
for any $\lambda\in U$. Because $\mathcal{R}_{2}^{1}$ is normal on $U$ there
exists a subsequence of $\\{R_{P_{n},v_{n}}\\}_{n\geq 1}$ that converges
locally uniformly to a holomorphic function $F:U\to\widehat{\mathbb{C}}$. For
$\lambda\in U\setminus(-\infty,-1/4]$ the map $f_{\lambda}$ is loxodromic,
hence $f_{\lambda}^{n}(0)$ converges to the attracting fixed point of
$f_{\lambda}$ as $n$ goes to infinity. This means that for $\lambda\in
U\setminus(-\infty,-1/4]$ we have $f_{\lambda}(F(\lambda))=F(\lambda)$.
Because $U\setminus(-\infty,-1/4]$ is non-empty and open in $U$ it follows
from the identity theorem for holomorphic functions that the equality
$f_{\lambda}(F(\lambda))=F(\lambda)$ must hold for all $\lambda\in U$. The set
$U$ contains a parameter $\lambda_{1}$ for which $f_{\lambda_{1}}$ is
elliptic. The value $0$ is not a fixed point of $f_{\lambda_{1}}$ and thus the
distance of $f_{\lambda_{1}}^{n}(0)$ to both of the fixed points of
$f_{\lambda_{1}}$ is uniformly bounded below for all $n$ by a positive
constant. This means that no subsequence of
$\\{R_{P_{n},v_{n}}(\lambda_{1})\\}_{n\geq 1}$ can converge to the fixed point
$F(\lambda_{1})$. We conclude that $\mathcal{R}_{2}^{1}$ is not normal at
$\lambda_{0}$. ∎

It follows from the previous two lemmas and Corollary 2.12 that

$(-\infty,-1/4]\subseteq\mathcal{A}_{2}^{1}\subseteq\mathcal{A}_{2}^{2}\subseteq\overline{\mathcal{Z}_{2}}=(-\infty,-1/4].$

Therefore we can conclude that both $\mathcal{A}_{2}$ and
$\overline{\mathcal{Z}_{2}}$ are equal to $(-\infty,-1/4]$.

###  3.3. Determining the density-locus.

Recall that for $\lambda\in\mathbb{C}$ we defined
$\mathcal{R}_{\Delta}^{i}(\lambda)=\\{R_{G,v}(\lambda):(G,v)\in\mathcal{G}_{\Delta}^{i}\\}$.
Subsequently we defined $\mathcal{D}_{\Delta}^{i}$ as the set consisting of
those $\lambda$ for which $\mathcal{R}_{\Delta}^{i}(\lambda)$ is dense in
$\widehat{\mathbb{C}}$. It is thus clear that
$\mathcal{D}_{2}^{1}\subseteq\mathcal{D}_{2}^{2}$. To conclude the section we
show the following.

######  Lemma 3.5.

There is no $\lambda_{0}\in\mathbb{C}$ for which
$\mathcal{R}_{2}^{2}(\lambda_{0})$ is dense in $\widehat{\mathbb{C}}$, i.e.
$\mathcal{D}_{2}^{2}=\emptyset$.

###### Proof.

It follows from Theorem 2.2 that

$\mathcal{R}_{2}^{2}(\lambda)=\\{R_{T,v}(\lambda):(T,v)\in\mathcal{G}_{2}^{2}\text{
with $T$ a tree}\\}.$

A rooted tree $(T,v)\in\mathcal{G}_{2}^{2}$ can be viewed as a vertex $v$ onto
which two rooted paths $(P_{n},v_{n})$ and $(P_{m},v_{m})$ are attached for
$n,m\geq 0$. It follows from Lemma 2.4 and Lemma 2.6 that

$R_{T,v}(\lambda)=\lambda\cdot\frac{1}{1+f_{\lambda}^{n}(0)}\cdot\frac{1}{1+f_{\lambda}^{m}(0)}=\frac{1}{\lambda}\cdot
f_{\lambda}^{n+1}(0)\cdot f_{\lambda}^{m+1}(0).$

For a specific $\lambda_{0}$ the right-hand side of this equality is not
defined if $f_{\lambda_{0}}^{n+1}(0)$ and $f_{\lambda_{0}}^{m+1}(0)$ take on
the values $0$ and $\infty$. Recall that if $f_{\lambda_{0}}^{n+1}(0)=\infty$,
then $f_{\lambda_{0}}^{n}(0)=-1$, which implies that
$\lambda_{0}\in\mathcal{Z}_{2}$. If this is the case then Lemma 3.3 implies
that $\lambda_{0}$ is real, and thus $\mathcal{R}_{2}^{2}(\lambda_{0})$ is
contained in $\mathbb{R}\cup\\{\infty\\}$ and is not dense in
$\widehat{\mathbb{C}}$.

Assume that $\lambda_{0}$ is not real. In this case we have the equality

$\mathcal{R}_{2}^{2}(\lambda_{0})=\left\\{\frac{1}{\lambda_{0}}\cdot
f_{\lambda_{0}}^{n+1}(0)\cdot f_{\lambda_{0}}^{m+1}(0):n,m\geq 0\right\\}.$

The map $f_{\lambda_{0}}$ is loxodromic, hence the orbit of $0$ converges to
an attracting fixed point without passing through $\infty$. Note that
$f_{\lambda_{0}}(\infty)=0$, therefore $\infty$ is not the attracting fixed
point, and thus there is a positive bound $B\in\mathbb{R}_{>0}$ such that
$|f_{\lambda_{0}}^{n}(0)|<B$ for all $n$. It follows that

$\left|\frac{1}{\lambda_{0}}\cdot f_{\lambda_{0}}^{n+1}(0)\cdot
f_{\lambda_{0}}^{m+1}(0)\right|<\frac{B^{2}}{|\lambda_{0}|}$

for all $n,m$, and thus $\mathcal{R}_{2}^{2}(\lambda_{0})$ is bounded and in
particular not dense in $\widehat{\mathbb{C}}$. ∎

##  4\. Equality of the zero-locus and the activity-locus for $\Delta\geq 3$

In this section we prove the equalities
$\mathcal{A}_{\Delta}^{1}=\mathcal{A}_{\Delta}^{2}=\cdots=\mathcal{A}_{\Delta}^{\Delta}=\overline{\mathcal{Z}_{\Delta}}$
for $\Delta\geq 3$, thereby proving that the activity-locus is equal to the
zero-locus. Our strategy is similar to the $\Delta=2$ case. By definition we
have
$\mathcal{A}_{\Delta}^{1}\subseteq\mathcal{A}_{\Delta}^{2}\subseteq\cdots\subseteq\mathcal{A}_{\Delta}^{\Delta}$.
We will first show that
$\mathcal{A}_{\Delta}^{1}=\mathcal{A}_{\Delta}^{2}=\cdots=\mathcal{A}_{\Delta}^{\Delta-1}$
and subsequently we will show that
$\overline{\mathcal{Z}_{\Delta}}\subseteq\mathcal{A}_{\Delta}^{\Delta-1}$.
Then Corollary 2.12, which states that
$\mathcal{A}_{\Delta}^{\Delta}\subseteq\overline{\mathcal{Z}_{\Delta}}$, is
enough to arrive at our desired conclusion.

######  Lemma 4.1.

The family $\mathcal{R}_{\Delta}^{1}$ is normal at $\lambda_{0}\in\mathbb{C}$
if and only if $\mathcal{R}_{\Delta}^{\Delta-1}$ is normal at $\lambda_{0}$,
and hence $\mathcal{A}_{\Delta}^{1}=\mathcal{A}_{\Delta}^{\Delta-1}$.

###### Proof.

Recall that

$\mathcal{R}_{\Delta}^{i}:=\\{R_{G,v}:(G,v)\in\mathcal{G}_{\Delta}^{i}\\}$

and thus $\mathcal{R}_{\Delta}^{1}\subseteq\mathcal{R}_{\Delta}^{\Delta-1}$.
It follows that if $\mathcal{R}_{\Delta}^{\Delta-1}$ is normal at
$\lambda_{0}$ then the same holds for $\mathcal{R}_{\Delta}^{1}$.

To show the other direction, assume that $\mathcal{R}_{\Delta}^{1}$ is normal
at $\lambda_{0}$. Note that the family $\mathcal{R}_{\Delta}^{\Delta}$ is
normal at $0$ by Lemma 2.10, hence we can assume $\lambda_{0}\neq 0$. As
$\mathcal{R}_{\Delta}^{1}$ is normal at $\lambda_{0}$, there is a neighborhood
$U$ of $\lambda_{0}$ on which $\mathcal{R}_{\Delta}^{1}$ is a normal family.
We can take $U$ such that $0\not\in U$. We will show that
$\mathcal{R}_{\Delta}^{\Delta-1}$ is also a normal family on $U$. To that
effect take a sequence of rooted graphs $\\{(G_{n},v_{n})\\}_{n\geq
1}\subseteq\mathcal{G}_{\Delta}^{\Delta-1}$. Construct the rooted graphs
$(\hat{G}_{n},\hat{v}_{n})\in\mathcal{G}_{\Delta}^{1}$ by attaching a root
$\hat{v}_{n}$ to the root $v_{n}$ of $G_{n}$ by a single edge. By assumption
the sequence $\\{R_{\hat{G}_{n},\hat{v}_{n}}\\}_{n\geq 1}$ has a subsequence
that converges locally uniformly to a function $H:U\to\widehat{\mathbb{C}}$.
Let $I\subseteq\mathbb{N}$ be the indices belonging to this subsequence. By
Lemma 2.6 we have
$R_{\hat{G}_{n},\hat{v}_{n}}(\lambda)=f_{\lambda}(R_{G_{n},v_{n}}(\lambda))$
for every $\lambda\in U$. Because $U$ does not contain $0$, the Möbius
transformation $f_{\lambda}$ is invertible for every $\lambda\in U$. Therefore
for these $\lambda$ we have

$\lim_{\begin{subarray}{c}n\to\infty\\\ n\in
I\end{subarray}}R_{G_{n},v_{n}}(\lambda)=\lim_{\begin{subarray}{c}n\to\infty\\\
n\in
I\end{subarray}}f_{\lambda}^{-1}(f_{\lambda}(R_{G_{n},v_{n}}(\lambda)))=\lim_{\begin{subarray}{c}n\to\infty\\\
n\in
I\end{subarray}}f_{\lambda}^{-1}(R_{\hat{G}_{n},\hat{v}_{n}}(\lambda))=f_{\lambda}^{-1}(H(\lambda)).$

Because the map $U\times\widehat{\mathbb{C}}\to\widehat{\mathbb{C}}$ that
sends $(\lambda,z)$ to $f_{\lambda}^{-1}(z)$ is continuous, we can conclude
that this limit converges locally uniformly on $U$. Therefore we have shown
that the sequence $\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ has a subsequence that
converges locally uniformly to the holomorphic function $\lambda\mapsto
f_{\lambda}^{-1}(H(\lambda))$, and thus $\mathcal{R}_{\Delta}^{\Delta-1}$ is
normal at $\lambda_{0}$. ∎

######  Proposition 4.2.

Let $\Delta\geq 3$. Then
$\overline{\mathcal{Z}_{\Delta}}\subseteq\mathcal{A}_{\Delta}^{\Delta-1}$, and
hence the zero-locus is contained in the activity-locus.

###### Proof.

Let us assume $\lambda\in\overline{\mathcal{Z}_{\Delta}}$. Then for any open
neighborhood $V$ of $\lambda$ there is a $\lambda_{0}\in V$ for which
$Z_{G}(\lambda_{0})=0$ for some $G\in\mathcal{G}_{\Delta}$. We will prove that
the family $\mathcal{R}_{\Delta}^{\Delta-1}$ cannot be normal on $V$.

By Lemma 2.3 there is a a rooted tree $(T,u)\in\mathcal{G}_{\Delta}^{1}$ for
which $R_{T,u}(\lambda_{0})=-1$. Consider the rooted trees $(T_{n},v)$
obtained by implementing a copy of $(T,u)$ in every vertex of the rooted paths
$(P_{n},v)$. It follows from Lemma 2.8 that

$R_{T_{n},v}=R_{P_{n},v}\circ R_{T,u}.$

We note that in $T_{n}$ the root $v$ has degree $2\leq\Delta-1$. Furthermore
$R_{T,u}$ maps a neighborhood of $\lambda_{0}$ holomorphically to a
neighborhood of $-1$, since $R_{T,u}$ is not constantly equal to $-1$. Lemma
3.4 states that the family $\\{R_{P_{n},v}\\}_{n>0}$ is not normal at $-1$ and
thus it follows that $\\{R_{T_{n},v}\\}_{n>0}$ is not normal at $\lambda_{0}$.
∎

Summarising we have the following relations between sets

$\mathcal{A}_{\Delta}^{1}\stackrel{{\scriptstyle\textnormal{(1)}}}{{\mathstrut{=}}}\mathcal{A}_{\Delta}^{\Delta-1}\subseteq\mathcal{A}_{\Delta}^{\Delta}\stackrel{{\scriptstyle\textnormal{(2)}}}{{\mathstrut{\subseteq}}}\overline{\mathcal{Z}_{\Delta}}\stackrel{{\scriptstyle\textnormal{(3)}}}{{\mathstrut{\subseteq}}}\mathcal{A}_{\Delta}^{\Delta-1},$

where equality (4) is due to Lemma 4.1, inclusion (4) is due to Corollary 2.12
and inclusion (4) is due to Proposition 4.2. It follows that
$\mathcal{A}_{\Delta}^{1}=\ldots=\mathcal{A}_{\Delta}^{\Delta}$, and
$\mathcal{A}_{\Delta}=\overline{\mathcal{Z}_{\Delta}}$ for all $\Delta\geq 2$.

###  4.1. The complement of the zero-locus

As an application of the equality of the zero-locus and the activity-locus, we
show here that each component of the complement of the zero-locus is simply
connected. We recall from the introduction that this implies that if the
complement of the zero-locus is connected (as we conjecture in Conjecture
1.1), then our main result gives a complete understanding of the complexity of
approximately computing the independence polynomial.

######  Proposition 4.3.

Let $\Delta\geq 2$ be an integer. Any connected component of the complement of
the zero-locus, $\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$, is
simply connected.

###### Proof.

For $\Delta=2$ the statement follows directly by the exact characterization of
the closure of the zero-locus. We will therefore assume that $\Delta\geq 3$.

Let $\gamma$ be a simple closed curve contained in the complement of the zero-
locus, $\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$. It is sufficient
to prove that the interior of $\gamma$, which we will denote by $V$, is zero
free. Let us suppose for the sake of a contradiction that this is not the
case.

Let $T$ be a minimal tree for which $Z_{T}(\lambda_{0})=0$ for some
$\lambda_{0}\in V$. Let $v$ be a leaf of $T$. Since $|T|$ is chosen minimal it
follows that $R_{T,v}(\lambda_{0})=-1$. Denote the neighbor of $v$ in $T$ by
$w$. By minimality of $T$ it also follows that $R_{T-v,w}(\lambda)\neq-1$ for
any $\lambda\in\overline{V}$.

Note that $V$ is necessarily bounded, as it is a subset of the cardioid,
$\Lambda_{\Delta}$. Hence by compactness of $\overline{V}$ it follows that
$R_{T-v,w}$ is bounded away from $-1$ on $V$. Since

$R_{T,v}(\lambda)=\frac{\lambda}{1+R_{T-v,w}(\lambda)}$

it follows that $R_{T,v}$ is bounded on $\overline{V}$. By the Open Mapping
Theorem for holomorphic functions it follows that there must be a
$\lambda_{1}\in\partial V=\gamma$ for which

$R_{T,v}(\lambda_{1})\in(-\infty,-1).$

Use Lemma 2.6 to implement the rooted tree $(T,v)$ in the paths $P_{n}$ to
obtain a sequence of rooted graphs $\\{(G_{n},u_{n})\\}_{n\geq 1}$ with

$R_{G_{n},u_{n}}=R_{P_{n},u_{n}}\circ R_{T,v}.$

Since $R_{T,v}(\lambda_{1})\in(-\infty,-1)$, which is contained in the half-
line where the family $\\{\lambda\mapsto
R_{P_{n},u}(\lambda)\\}_{n\in\mathbb{N}}$ is not normal, it follows that the
family of ratios $\\{R_{G_{n},u_{n}}\\}$ is not normal at $\lambda_{1}$. This
contradicts the assumption that $\gamma$ is contained in
$\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$, by the equivalence of
the activity-locus and the zero-locus. ∎

##  5\. Equality of the density-locus and the activity-locus for $\Delta\geq
3$

We first show the inclusion
$\overline{\mathcal{D}_{\Delta}}\subseteq\mathcal{A}_{\Delta}$ holds. Note
that as $\mathcal{A}_{\Delta}$ is closed, it suffices to show
$\mathcal{D}_{\Delta}\subseteq\mathcal{A}_{\Delta}$.

######  Theorem 5.1.

The density-locus is contained in the activity-locus. More precisely, we have
$\mathcal{D}_{\Delta}\subseteq\mathcal{A}_{\Delta}$ for all $\Delta\geq 3$.

######  Remark 5.2.

Recall the remarkable Proposition 6 in [BGGv20], in which it is shown that
non-real $\lambda\in\mathbb{Q}[i]$ outside the cardioid $\Lambda_{\Delta}$ are
contained in the density-locus. As a consequence Theorem 5.1 implies that
$\mathcal{Z}_{\Delta}$ is dense in the complement of the cardioid.

The proof of Theorem 5.1 is by contradiction. So we will assume that there is
a $\lambda_{0}\in\mathcal{D}_{\Delta}$ with
$\lambda_{0}\not\in\mathcal{A}_{\Delta}$ and arrive at a contradiction. In
order to do this, we state and prove three helpful lemmas.

######  Lemma 5.3.

Let $\lambda_{0}\in\mathbb{C}\setminus\mathcal{A}_{\Delta}$. Assume the family
$\mathcal{R}_{\Delta}$ is normal on some open neighborhood $U$ of
$\lambda_{0}$ and that $\\{R_{G_{n},v_{n}}(\lambda_{0})\\}_{n\geq 1}$
converges to $-1$ for a sequence $\\{(G_{n},v_{n})\\}_{n\geq 1}$ of rooted
graphs from $\mathcal{G}_{\Delta}$. Then $\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$
converges to $-1$ locally uniformly on $U$.

###### Proof.

It follows from the conclusion of Section 4, i.e.
$\mathcal{A}_{\Delta}=\overline{\mathcal{Z}_{\Delta}}$, that
$Z_{G}(\lambda)\neq 0$ for all $\lambda\in U$ and $G\in\mathcal{G}_{\Delta}$.
Suppose $\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ does not converge to $-1$ locally
uniformly on $U$. Then, after taking a subsequence if necessary, we may assume
that $\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ converges locally uniformly on $U$ to a
non-constant holomorphic function $f$. Clearly $f(\lambda_{0})=-1$. Since
zeros of holomorphic functions are isolated there exists $\varepsilon>0$ so
that $\overline{B(\lambda_{0},\varepsilon)}\subset U$ and such that

$\delta:=\inf_{\lambda\in\partial
B(\lambda_{0},\varepsilon)}|f(\lambda)+1|>0.$

Let $n$ be sufficiently large so that $|R_{G_{n},v_{n}}-f|<\delta$ uniformly
on $\overline{B(\lambda_{0},\varepsilon)}$. Then

$|(R_{G_{n},v_{n}}(\lambda)+1)-(f(\lambda)+1)|<\delta<|f(\lambda)+1|+|R_{G_{n},v_{n}}(\lambda)+1|$

for all $\lambda\in\partial B(\lambda_{0},\varepsilon)$. By Rouché’s theorem
there exists $\lambda_{1}\in B(\lambda_{0},\varepsilon)$ for which
$R_{G_{n},v_{n}}(\lambda_{1})=-1$. By Lemma 2.1 it follows $\lambda_{1}$ is a
zero of the independence polynomial $Z_{G}$ for some graph $G$ of maximum
degree at most $\Delta$, which is a contradiction as we assumed
$\lambda_{0}\in\mathbb{C}\setminus\mathcal{A}_{\Delta}=\mathbb{C}\setminus\overline{\mathcal{Z}_{\Delta}}$.
∎

######  Lemma 5.4.

Let $\lambda_{0}\in\mathbb{C}\setminus\mathcal{A}_{\Delta}$. Assume the family
$\mathcal{R}_{\Delta}$ is normal on some open neighborhood $U$ of
$\lambda_{0}$ and that $\\{R_{G_{n},v_{n}}(\lambda_{0})\\}_{n\geq 1}$
converges to $\mu\leq-\frac{1}{4}$ for a sequence of rooted graphs
$\\{(G_{n},v_{n})\\}_{n\geq 1}$ in $\mathcal{G}_{\Delta}^{1}$. Then
$\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ converges to $\mu$ locally uniformly on $U$.

###### Proof.

If this is not the case then, as in the previous lemma, we may assume that
$\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ converges locally uniformly to a non-
constant holomorphic function $f$ with $f(\lambda_{0})=\mu$. By Rouché’s
theorem we can find $\lambda_{1}\in U$ and $n$ sufficiently large so that
$R_{G_{n},v_{n}}(\lambda_{1})=\mu$, by the same argument as in the previous
lemma.

Consider the family of rooted graphs $\\{(\widetilde{G}_{k},w_{k})\\}$
obtained by implementing $(G_{n},v_{n})$ in every vertex of the rooted paths
$(P_{k},w_{k})$, where $P_{k}$ is the path with $k$ vertices and $w_{k}$ is
one of its extreme vertices. Since $v_{n}$ has degree $1$, the graph
$\widetilde{G}_{k}$ has maximum degree at most $\Delta$. Hence by Lemma 2.6 we
have

$R_{\widetilde{G}_{k},w_{k}}(\lambda)=f^{k}_{R_{G_{n},v_{n}}(\lambda)}(0).$

By Lemma 3.4 the family $\\{R_{P_{k},w_{k}}\\}=\\{\lambda\mapsto
f^{k}_{\lambda}(0)\\}$ is non-normal at $\lambda=\mu$, and therefore the
family $\\{R_{\widetilde{G}_{k},w_{k}}\\}$ is non-normal at $\lambda_{1}$,
contradicting the fact that the family $\mathcal{R}_{\Delta}$ is normal on
$U$. ∎

######  Lemma 5.5.

Assume there is a $\lambda_{0}\in\mathcal{D}_{\Delta}$ with
$\lambda_{0}\not\in\mathcal{A}_{\Delta}$. Denote $U$ for an open neighborhood
of $\lambda_{0}$ on which the family $\mathcal{R}_{\Delta}$ is normal. Assume
furthermore that $\\{R_{G_{n},v_{n}}(\lambda_{0})\\}_{n\geq 1}$ converges to
$\mu\in\mathbb{R}$ for a sequence of rooted graphs $\\{(G_{n},v_{n})\\}_{n\geq
1}$ in $\mathcal{G}_{\Delta}^{\Delta-1}$. Then $\\{R_{G_{n},v_{n}}\\}_{n\geq
1}$ converges to $\mu$ locally uniformly on $U$.

###### Proof.

If $\mu=-1$ the result follows by Lemma 5.3. We may therefore assume that
$\mu\neq-1$. Recall that we denote $f_{\lambda}(z)=\lambda/(1+z)$. We will
show for each $\mu\in\mathbb{R}$ there exists
$\mu_{1},\mu_{2},\mu_{3}\leq-\frac{1}{4}$ so that

$f_{\mu_{m}}\circ\cdots\circ f_{\mu_{1}}(\mu)=-1,$

for some $m\leq 3$. We distinguish between different cases

  1. (1)

$\mu\geq-3/4$. Take $\mu_{1}=-1-\mu\leq-1/4$, one can check
$f_{\mu_{1}}(\mu)=-1$.

  2. (2)

$\mu<-1$. Take $\mu_{1}=-1/4$ and $\mu_{2}=1-f_{\mu_{1}}(\mu)$, then
$f_{\mu_{1}}(\mu)>0>-3/4$ and so $\mu_{2}\leq-1/4$. One can check
$f_{\mu_{2}}\circ f_{\mu_{1}}(\mu)=-1$.

  3. (3)

$-1<\mu<-3/4$. Take $\mu_{1}=\mu_{2}=-1/4$ and
$\mu_{3}=1-f_{\mu_{2}}(f_{\mu_{1}}(\mu))$, then $f_{\mu_{1}}(\mu)<-1$ so we
see $\mu_{3}\leq-1/4$. One can check $f_{\mu_{3}}\circ f_{\mu_{2}}\circ
f_{\mu_{1}}(\mu)=-1$.

We may assume that $\\{R_{G_{n},v_{n}}\\}_{n\geq 1}$ converges locally
uniformly on $U$ to a holomorphic function $f$ with $f(\lambda_{0})=\mu$. We
want to show $f$ is constant on $U$. Since the set
$\\{R_{G,v}(\lambda_{0}):(G,v)\in\mathcal{G}_{\Delta}^{1}\\}$ is dense in
$\hat{\mathbb{C}}$ by assumption, we can choose sequences of rooted graphs
$\\{(G_{n}^{i},v_{n}^{i})\\}_{n\geq 1}$ in $\mathcal{G}_{\Delta}^{1}$ so that
$\\{R_{G_{n}^{i},v_{n}^{i}}(\lambda_{0})\\}_{n\geq 1}$ converges to $\mu_{i}$
for each $i=1,\ldots,m$. By Lemma 5.4 every sequence
$\\{R_{G_{n}^{i},v_{n}^{i}}\\}_{n\geq 1}$ converges locally uniformly on $U$
to the constant function $\mu_{i}$ for each $i$.

Consider for each $n\geq 1$, the rooted graph $(\widetilde{G}_{n},v_{n}^{m})$
obtained by implementing the rooted graphs $(G_{n},v_{n})$,
$(G_{n}^{1},v_{n}^{1}),\ldots,(G_{n}^{m},v_{n}^{m})$ on the vertices of the
path $P_{m+1}$ of length $m$. Note that $\widetilde{G}_{n}$ has maximum degree
at most $\Delta$.

It follows from Lemma 2.6 that

$R_{\widetilde{G}_{n},v^{m}_{n}}(\lambda)=f_{R_{G_{n}^{m},v^{m}_{n}}(\lambda)}\circ\cdots\circ
f_{R_{G_{n}^{1},v^{1}_{n}}(\lambda)}\circ R_{G_{n},v_{n}}(\lambda).$

By our choice of the $\mu_{i}$ the sequence of ratios
$\\{R_{\widetilde{G}_{n},v^{m}_{n}}(\lambda_{0})\\}_{n\geq 1}$ converges to
$f_{\mu_{m}}\circ\cdots\circ f_{\mu_{1}}(\mu)=-1$. Hence by Lemma 5.3 the
sequence of ratios $\\{R_{\widetilde{G}_{n},v^{m}_{n}}\\}_{n\geq 1}$ converges
locally uniformly to the constant function $-1$. Furthermore the sequence of
ratios $\\{R_{\widetilde{G}_{n},v^{m}_{n}}\\}_{n\geq 1}$ converges to the
function $F:=f_{\mu_{m}}\circ\cdots\circ f_{\mu_{1}}\circ f$. As
$f_{\mu_{m}}\circ\cdots\circ f_{\mu_{1}}(z)$ is a non-constant holomorphic
function and $F=-1$ on $U$, it follows that $f$ is constant on $U$, as
desired. ∎

We are now ready to prove Theorem 5.1.

###### Proof of Theorem 5.1.

Assume for the purpose of a contradiction that there exists
$\lambda_{0}\in\mathcal{D}_{\Delta}^{1}$ with
$\lambda_{0}\not\in\mathcal{A}_{\Delta}$. We note that by Lemma 2.10 we know
$\lambda_{0}\neq 0$. Throughout the proof denote $U$ for an open neighborhood
of $\lambda_{0}$ on which the family $\mathcal{R}_{\Delta}$ is normal; we may
assume $0\not\in U$ by taking $U$ small enough. Assume first that
$\lambda_{0}$ is not purely imaginary. Consider the real number
$c=\frac{-|\lambda_{0}|^{2}}{2\textrm{Re}\,\lambda_{0}}$ and notice that

$\frac{\lambda_{0}^{2}}{\lambda_{0}+c}=2\textrm{Re}\,\lambda_{0}\in\mathbb{R}.$

Choose two sequences of rooted graphs $\\{G_{n},v_{n}\\}_{n\geq 1}$,
$\\{(H_{n},w_{n})\\}_{n\geq 1}$ in $\mathcal{G}_{\Delta}^{1}$ so that
$\\{R_{G_{n},v_{n}}(\lambda_{0})\\}_{n\geq 1}$ and
$\\{R_{H_{n},w_{n}}(\lambda_{0})\\}_{n\geq 1}$ converge to respectively $1$
and $c$. By Lemma 5.5 we must have that these sequence of ratios converge
locally uniformly on $U$ to the respective constants $1$ and $c$.

Consider the sequence of graphs $\widetilde{G}_{n\geq 1}$ constructed by
merging $v_{n}$ and $w_{n}$ and by then connecting this vertex to a vertex
$\widetilde{v}_{n}$.

$v_{n}$$G_{n}$$H_{n}$$\tilde{v_{n}}$ Figure 3. The rooted graph
$\widetilde{G}_{n}$ in the proof of Theorem 5.1

It follows from Lemma 2.6 and Lemma 2.9 for all $\lambda\in U$ that

$R_{\widetilde{G}_{n},\widetilde{v}_{n}}(\lambda)=\frac{\lambda}{1+\lambda^{-1}R_{G_{n},v_{n}}(\lambda)\,R_{H_{n},w_{n}}(\lambda)},$

where we use $0\not\in U$. Therefore the sequence of holomorphic functions
$\\{R_{\widetilde{G}_{n},\widetilde{v}_{n}}\\}_{n\geq 1}$ converges locally
uniformly on $U$ to the function $f(\lambda)=\frac{\lambda^{2}}{\lambda+c}$ as
$n\to\infty$. Note that $f$ is not a constant function, and that
$f(\lambda_{0})\in\mathbb{R}$, contradicting Lemma 5.5. This contradiction
completes the proof for $\lambda_{0}$ not purely imaginary.

Assume instead that $\lambda_{0}$ is purely imaginary and let
$(G,v)\in\mathcal{G}_{\Delta}^{1}$ so that $R_{G,v}(\lambda_{0})$ is not
purely imaginary. For $c\in\mathbb{R}$ to be determined later choose again two
sequences of rooted graphs $\\{G_{n},v_{n}\\}_{n\geq 1}$,
$\\{(H_{n},w_{n})\\}_{n\geq 1}$ in $\mathcal{G}_{\Delta}^{1}$ such that
sequences $\\{R_{G_{n},v_{n}}(\lambda_{0})\\}_{n\geq 1}$ and
$\\{R_{H_{n},w_{n}}(\lambda_{0})\\}_{n\geq 1}$ converge to $1$ and $c$
respectively. Define for each $n\geq 1$, $(\tilde{G_{n}},\widetilde{v_{n}})$
as above and let $(K_{n},v_{n})$ be the rooted graph obtained from the
disjoint union of $(\tilde{G_{n}},\widetilde{v_{n}})$ and $(G,v)$ by
identifying the vertex $\widetilde{v}_{n}$ with $v$. It follows from Lemma 2.6
and Lemma 2.9 for $\lambda\in U$ that

$R_{K_{n},v_{n}}(\lambda)=\frac{R_{G,v}(\lambda)}{1+\lambda^{-1}R_{G_{n},v_{n}}(\lambda)\,R_{H_{n},w_{n}}(\lambda)},$

where we use $0\not\in U$. Thus in order to follow the same argument as before
we require $c\in\mathbb{R}$ for which

$\frac{\lambda_{0}\cdot R_{G,v}(\lambda_{0})}{\lambda_{0}+c}\in\mathbb{R}.$

It is clear that such real number $c$ exists, hence the identical argument
leads to the desired contradiction. ∎

We will now show the other inclusion
$\mathcal{A}_{\Delta}\subseteq\overline{D_{\Delta}}$ also holds for all
$\Delta\geq 3$. We first show the inclusion holds for non-real parameters
$\lambda\in\mathcal{A}_{\Delta}$.

######  Theorem 5.6.

Let $\Delta\geq 3$ and suppose that the family $\mathcal{R}_{\Delta}$ is not
normal in any neighborhood of
$\lambda_{0}\in\mathbb{C}\setminus\mathbb{R}_{\leq 0}$. Then there exists
$\lambda_{1}$ arbitrarily close to $\lambda_{0}$ for which the set
$\\{R_{G,v}(\lambda_{1}):(G,v)\in\mathcal{G}_{\Delta}^{1}\\}$ is dense in
$\hat{\mathbb{C}}$.

###### Proof.

Because $\overline{\mathcal{Z}_{\Delta}}=\mathcal{A}_{\Delta}$ there exists
$\lambda_{2}$ arbitrarily close to $\lambda_{0}$ for which there is a graph
$G$ of maximum degree at most $\Delta$ such that $Z_{G}(\lambda_{2})=0$. We
claim that we can assume $\lambda_{2}\not\in\mathbb{R}$. This is clear if
$\lambda_{0}\not\in\mathbb{R}$. Moreover, if $\lambda_{0}\in\mathbb{R}$ then
$\lambda_{0}$ is a strictly positive real number. Because $Z_{G}(x)>0$ for any
positive real number $x$, it follows that $\lambda_{2}$ is necessarily not
real as long as it is sufficiently close to $\lambda_{0}$.

By Lemma 2.3 there is a rooted tree $(T,v)\in\mathcal{G}_{\Delta}^{1}$ such
that $R_{T,v}(\lambda_{2})=-1$. Since the rational function $\lambda\mapsto
R_{T,v}(\lambda)$ is non-constant, it is an open map. The image of a
neighborhood of $\lambda_{2}$ therefore contains a small open real interval
around $-1$. Recall that Lemma 3.2 states that for $\mu\in(-\infty,-1/4)$ the
map $f_{\mu}:z\mapsto\mu/(1+z)$ is conjugate to a rotation $w\mapsto
e^{i\theta}\cdot w$. Furthermore, by comparing $\operatorname{tr}^{2}$ of both
maps, it is not hard to see that those parameters $\mu$ for which $f_{\mu}$ is
conjugate to an irrational rotation lie dense in $(-\infty,-1/4)$. Therefore
we can choose a $\lambda_{1}\in\mathbb{C}\setminus\mathbb{R}$ arbitrarily
close to $\lambda_{2}$ such that for $\mu:=R_{T,v}(\lambda_{1})$ the map
$f_{\mu}$ is conjugate to an irrational rotation. From now on $\mu$ is fixed
to be this value.

Let ${p,q}$ be the two fixed points of the transformation $f_{\mu}$. In
Section 3.1 we explained that $\hat{\mathbb{C}}\setminus\\{p,q\\}$ is foliated
by generalized circles invariant under $f_{\mu}$, and on which $f_{\mu}$ acts
conjugate to an irrational rotation. We denote the generalized circle through
$z$ by $C_{z}$, and write $C_{q}$ and $C_{p}$ for $\\{q\\}$ and $\\{p\\}$
respectively. The map $z\mapsto C_{z}$ is continuous as a map from
$\hat{\mathbb{C}}$ to the space $\\{K\subseteq\hat{\mathbb{C}}:K\text{
compact}\\}$ equipped with the Hausdorff metric.

Our goal is to show that $\mathcal{R}^{1}_{\Delta}(\lambda_{1})$ is dense in
$\hat{\mathbb{C}}$. We first claim that if
$w\in\mathcal{R}^{1}_{\Delta}(\lambda_{1})$, then
$\mathcal{R}^{2}_{\Delta}(\lambda_{1})\cap C_{w}$ is dense in $C_{w}$.

To prove the claim, let $(H,u)\in\mathcal{G}_{\Delta}^{1}$ be a rooted graph
such that $R_{H,u}(\lambda_{1})=w$. Let $\tilde{G}_{n}$ as follows be obtained
from the path $P_{n+1}$ on $n+1$ vertices, labeled $v_{0}$ up to $v_{n}$, by
implementing $(H,u)$ at $v_{0}$ and the rooted tree $(T,v)$ at the remaining
$n$ vertices of $P_{n+1}$, see Figure 4. Now by Lemma 2.6 we have

$R_{\tilde{G}_{n},v_{n}}(\lambda_{1})=f_{\mu}^{n}(R_{H,u}(\lambda_{1}))=f_{\mu}^{n}(w).$

Observe that for each $n\geq 1$ we have
$(\tilde{G}_{n},v_{n})\in\mathcal{G}_{\Delta}^{2}$. Because $f_{\mu}$ acts
conjugately to an irrational rotation on $C_{w}$ it follows that
$\mathcal{R}^{2}_{\Delta}(\lambda_{1})\cap C_{w}$ is dense in $C_{w}$.

$v_{0}$$H$$v_{1}$$T$$v_{2}$$T$$v_{n}$$T$ Figure 4. The graph
$(\tilde{G}_{n},v_{n})$ in the proof of the claim

Because $\mu\in\mathcal{R}^{1}_{\Delta}(\lambda_{1})$ and
$C_{\mu}=\hat{\mathbb{R}}:=\mathbb{R}\cup\\{\infty\\}$ it follows from the
claim that $\mathcal{R}^{2}_{\Delta}(\lambda_{1})\cap\hat{\mathbb{R}}$ is
dense in $\hat{\mathbb{R}}$. Observe that
$f_{\lambda_{1}}(\hat{\mathbb{R}})=\lambda_{1}\cdot\hat{\mathbb{R}}$. So by
attaching a vertex at the root with an edge, we obtain that
$\mathcal{R}^{1}_{\Delta}(\lambda_{1})\cap\lambda_{1}\cdot\hat{\mathbb{R}}$ is
dense in $\lambda_{1}\cdot\hat{\mathbb{R}}$.

The set

$U=\\{z\in\hat{\mathbb{C}}:\text{$C_{z}$ intersects
$\lambda_{1}\cdot\hat{\mathbb{R}}$ transversely}\\}$

is an open set in $\hat{\mathbb{C}}$, see Figure 5. Because
$\lambda_{1}\not\in\mathbb{R}$ we see that $C_{-1}=\hat{\mathbb{R}}$
intersects $\lambda_{1}\cdot\hat{\mathbb{R}}$ transversely, and thus $-1\in
U$. The set U is contained in
$\cup_{w\in\lambda_{1}\cdot\hat{\mathbb{R}}}C_{w}$. Because
$\mathcal{R}^{1}_{\Delta}(\lambda_{1})\cap\lambda_{1}\cdot\hat{\mathbb{R}}$ is
dense in $\lambda_{1}\cdot\hat{\mathbb{R}}$, it follows that
$\cup_{w\in\mathcal{R}^{1}_{\Delta}(\lambda_{1})}C_{w}$ is dense in $U$. From
the claim we proved earlier, it follows
$\mathcal{R}^{2}_{\Delta}(\lambda_{1})$ is dense in $U$. Attaching a vertex to
the root of a tree in $\mathcal{G}_{\Delta}^{2}$ with ratio $r$ yields a
rooted tree in $\mathcal{G}_{\Delta}^{1}$ with ratio $f_{\lambda_{1}}(r)$, and
thus $\mathcal{R}^{1}_{\Delta}(\lambda_{1})$ is dense in the neighborhood
$U_{\infty}:=f_{\lambda_{1}}(U)$ of $\infty$.

For two rooted trees $(T_{1},v_{1})\in\mathcal{G}_{\Delta}^{1}$ and
$(T_{2},v_{2})\in\mathcal{G}_{\Delta}^{2}$ with ratios $r_{1}$ and $r_{2}$
respectively we can define the rooted tree
$(T_{3},v_{1})\in\mathcal{G}_{\Delta}^{2}$ by adding an edge between the roots
of $T_{1}$ and $T_{2}$ and considering $v_{1}$ the root of the obtained tree.
By Lemma 2.6 the ratio of $(T_{3},v_{1})$ is given by

$F(r_{1},r_{2}):=f_{r_{1}}(r_{2})=\frac{r_{1}}{1+r_{2}}$

under the assumption that this fraction is well defined, i.e.,
$(r_{1},r_{2})\not\in\\{(0,-1),(\infty,\infty)\\}$. It is not hard to see that

$F(U_{\infty}\times\hat{\mathbb{R}}\setminus\\{(0,-1),(\infty,\infty)\\})=\hat{\mathbb{C}}.$

Because $\mathcal{R}^{1}_{\Delta}(\lambda_{1})$ is dense in $U_{\infty}$ and
$\mathcal{R}^{2}_{\Delta}(\lambda_{1})$ is dense in $\hat{\mathbb{R}}$ it
follows that $\mathcal{R}^{2}_{\Delta}(\lambda_{1})$ is dense in
$\hat{\mathbb{C}}$. We finally conclude that
$\mathcal{R}^{1}_{\Delta}(\lambda_{1})$ is dense in
$f_{\lambda_{1}}(\hat{\mathbb{C}})=\hat{\mathbb{C}}$. ∎

$q$$p$$\hat{\mathbb{R}}$$\lambda_{1}\cdot\hat{\mathbb{R}}$ Figure 5. The
generalized circles $\lambda_{1}\cdot\hat{\mathbb{R}}$ and $\hat{\mathbb{R}}$
intersect in the points $0$ and $\infty$. A region around $0$ is drawn. The
open set $U$ is shaded in gray. Examples of generalized circles $C_{w}$ that
intersect $\lambda_{1}\cdot\hat{\mathbb{R}}$ transversely are drawn in red,
while examples of circles that do not intersect
$\lambda_{1}\cdot\hat{\mathbb{R}}$ are drawn in blue.

We can now finally prove the inclusion
$\mathcal{A}_{\Delta}\subseteq\overline{\mathcal{D}_{\Delta}}$ building on
Proposition 6 of [BGGv20] to deal with the real parameters
$\lambda\in\mathcal{A}_{\Delta}$.

######  Theorem 5.7.

Let $\Delta\geq 3$. Then the activity locus is contained in the density locus,
i.e. $\mathcal{A}_{\Delta}\subseteq\overline{\mathcal{D}_{\Delta}}$.

###### Proof.

Let $\lambda_{0}\in\mathcal{A}_{\Delta}$. If
$\lambda_{0}\in\mathbb{C}\setminus\mathbb{R}_{\leq 0}$, then
$\lambda_{0}\in\overline{\mathcal{D}_{\Delta}}$ follows from Theorem 5.6.

We know $\overline{\mathcal{Z}_{\Delta}}=\mathcal{A}_{\Delta}$. By Remark 2.11
we know that

$\overline{\mathcal{Z}_{\Delta}}\cap\mathbb{R}_{\leq 0}=\mathbb{R}_{\leq
0}\setminus\operatorname{int}(\Lambda_{\Delta})$

for all $\Delta\geq 3$. Proposition 6 of [BGGv20] implies that
$\mathbb{C}\setminus(\mathbb{R}\cup\Lambda_{\Delta})\subseteq\overline{\mathcal{D}_{\Delta}}$
for $\Delta\geq 3$. Hence it follows that $\mathbb{R}_{\leq
0}\setminus\operatorname{int}(\Lambda_{\Delta})\subseteq\overline{\mathcal{D}_{\Delta}}$,
which completes the proof. ∎

##  6\. Density implies #P-hardness

In this section we will show that the density-locus is contained in the
$\\#\mathcal{P}$-locus. To prove our result we will need to to show
‘exponential’ density for ratios of a specific family of trees: we need to get
$\varepsilon$-close to a given point $P\in\mathbb{Q}[i]$ with ratios of trees
of size at most $O(\log(1/\varepsilon)+\mathrm{size}(P))$. Here
$\mathrm{size}(P)$ denotes the sum of the bit sizes of the real and imaginary
part of $P$. Moreover, we denote for rational $\varepsilon>0$ by
$\mathrm{size}(\varepsilon,P)$ the sum of the the bit size of $\varepsilon$
and $\mathrm{size}(P)$.

Let $\lambda_{0}\in\mathbb{C}\setminus\mathbb{R}$. Then the Möbius
transformation $f_{\lambda_{0}}$ is loxodromic (cf. Section 3.1) and hence has
a repelling fixed point, which we denote by $z_{0}$.

Let

$A:=\\{z\in\mathbb{C}:2\pi/3-0.01<\arg{z}<2\pi/3,1/17<|z|<1/16\\}.$ (7)

Let
$\mathcal{T}=\\{(G_{1},v_{1}),\ldots,(G_{m},v_{m}),(\overline{G}_{1},\overline{v}_{1}),\ldots,(\overline{G}_{M},\overline{v}_{M}\\}$
be a family of rooted trees and $U$ an open disk containing $z_{0}$. The pair
$(\mathcal{T},U)$ is called a _fast implementer for $\lambda_{0}$_ if the
ratios $\mu_{i}:=R_{G_{i},v_{i}}$ and
$\chi_{i}:=R_{\overline{G}_{i},\overline{v}_{i}}$ are such that the maps
$g_{i}:=f_{\mu_{i}}\circ f_{\chi_{i}}$ are loxodromic and satisfy

  1. (1)

the attracting fixed point $z_{i}$ of $g_{i}$ lies in $U$ for all $i$,

  2. (2)

$\overline{U}\subseteq\cup_{i=1}^{M}g_{i}(U)$,

  3. (3)

$g_{i}^{\prime}(z)\in A$ for all $i$ and all $z\in\overline{U}$,

and the disk $U$ is such that

  1. (1)

$\overline{U}\subset f_{\lambda_{0}}(U)$,

  2. (2)

$\overline{U}$ does not contain the attracting fixed point of
$f_{\lambda_{0}}$,

  3. (3)

$U$ has three rational points on its boundary.

We have the following results concerning fast implementers.

######  Lemma 6.1.

Let $\Delta\geq 3$ be an integer. Let $\lambda_{0}\in\mathcal{D}_{\Delta}$.
Then there exists a fast implementer $(\mathcal{T},U)$ for $\lambda_{0}$.

######  Lemma 6.2.

Let $\lambda_{0}\in\mathbb{C}\setminus\mathbb{R}$ and assume that there exists
a fast implementer
$(\\{(G_{1},v_{1}),\ldots,(G_{m},v_{m}),(\overline{G}_{1},\overline{v_{1}}),\ldots,(\overline{G}_{M},\overline{v}_{M})\\},U)$
for $\lambda_{0}$. Then, given $P\in\mathbb{C}$ and $\epsilon>0$ there exists
an algorithm that yields a sequence of ratios

$w_{1},\dots,w_{K}\in\\{\lambda_{0}\\}\cup\bigcup_{i=1}^{M}\\{\mu_{i}:=R_{G_{i},v_{i}},\chi_{i}:=R_{\overline{G}_{i},\overline{v_{i}}}\\}$

such that $|(f_{w_{K}}\circ\cdots\circ f_{w_{1}})(0)-P|<\epsilon$,
$w_{K}=\lambda_{0}$ and
$K=\mathcal{O}(\max{(\log(1/\epsilon),\log(|P|/\epsilon))})$. If
$\lambda_{0}\in\mathbb{Q}[i]$ and the input parameters $P,\epsilon$ are also
in $\mathbb{Q}[i]$ then the algorithm runs in
$poly(\mathrm{size}(P,\epsilon))$ time.

We provide proofs for these lemmas in the next subsection, but first we
collect some consequences.

######  Corollary 6.3.

Let $\Delta\geq 3$ be an integer. The set $\mathcal{D}_{\Delta}$ is an open
set.

###### Proof.

Let $\lambda_{0}\in\mathcal{D}_{\Delta}.$ Let $(\mathcal{T},U)$ be fast
implementer, as guaranteed to exist by Lemma 6.1. For $\lambda$ nearby
$\lambda_{0}$ we still have that the repelling fixed point of $f_{\lambda}$ is
contained in $U$, its attracting fixed point does not lie in $\overline{U}$
and $\overline{U}\subset f_{\lambda}(U)$. In other words $(\mathcal{T},U)$ is
a fast implementer for $\lambda$. Therefore applying the algorithm of Lemma
6.2 to $\lambda$ we obtain that the collection of values
$\\{R_{G,v}(\lambda)\mid(G,v)\in\mathcal{G}_{\Delta}^{1}\\}$ is dense in
$\hat{\mathbb{C}}$ and hence $\lambda\in\mathcal{D}_{\Delta}$. ∎

For our next corollary we first need a result about the set

$\mathcal{E}_{\Delta}:=\\{\lambda\in\mathbb{Q}[i]\mid Z_{G}(\lambda)=0\text{
for some }G\in\mathcal{G}_{\Delta}\\}.$

######  Lemma 6.4.

Let $\Delta\geq 3$ be an integer. Then the collection $\mathcal{E}_{\Delta}$
is contained in the set

$\Big{\\{}(a+ib)^{-1}\mid a,b\in\mathbb{Z},\text{
}0<\sqrt{a^{2}+b^{2}}\leq\frac{\Delta^{\Delta}}{(\Delta-1)^{\Delta-1}}\Big{\\}}.$

###### Proof.

Let $\lambda\in\mathcal{E}_{\Delta}$. Then there exists a graph $G=(V,E)$ such
that $1/\lambda$ is a root of $P(z):=z^{|V|}Z_{G}(1/z)$. Now $P$ is a monic
polynomial and therefore $1/\lambda\in\mathbb{Z}[i]$ (since $\mathbb{Z}[i]$ is
integrally closed by Gauss’s lemma). We also know that
$|1/\lambda|\leq\frac{\Delta^{\Delta}}{(\Delta-1)^{\Delta-1}}$ by Lemma 2.10.
This proves the lemma. ∎

######  Corollary 6.5.

Let $\Delta\geq 3$ be an integer. Let
$\lambda_{0}\in(\mathcal{D}_{\Delta}\cap\mathbb{Q}[i])\setminus\mathcal{E}_{\Delta}$.
Then given $P\in\mathbb{Q}[i]$ and rational $\varepsilon>0$ there exists an
algorithm that generates a rooted tree $(T,v)$ such that
$|R_{T,v}(\lambda_{0})-P|\leq\varepsilon$ and
$Z^{\text{out}}_{T,v}(\lambda_{0})\neq 0$, and outputs
$Z^{\text{in}}_{T,v}(\lambda_{0})$ and $Z^{\text{out}}_{T,v}(\lambda_{0})$ in
time bounded by $poly(\mathrm{size}(\varepsilon,P))$.

###### Proof.

We first perform a brute force, but constant time, computation to obtain a
fast implementer
$(\\{(G_{1},v_{1}),\ldots,(G_{m},v_{m}),(\overline{G}_{1},\overline{v_{1}}),\ldots,(\overline{G}_{M},\overline{v}_{M}\\},U)$
for $\lambda_{0}$. Denote for $i=1,\ldots,M$, $\mu_{i}:=R_{G_{i},v_{i}}$ and
$\chi_{i}:=R_{\overline{G}_{i},\overline{v_{i}}}$ and $g_{i}:=f_{\mu_{i}}\circ
f_{\chi_{i}}$.

The algorithm of Lemma 6.2 applied to $P$ now returns in time
$poly(\mathrm{size}(\varepsilon,P))$ a sequence of ratios
$\omega_{1}\ldots,\omega_{K}\in\\{\lambda_{0}\\}\cup\bigcup_{i=1}^{M}\\{\mu_{i},\chi_{i}\\}$
that, by Lemma 2.6, correspond to the implementation of the trees $G_{i}$ and
$\overline{G}_{i}$ on a path with
$K=\mathcal{O}(\max{(\log(1/\epsilon),\log(|P|/\epsilon))}$ vertices. The
resulting rooted tree $(T,v)$ has maximum degree at most $\Delta$ and root
degree $1$ and satisfies $|R_{T,v}(\lambda_{0})-P|\leq\varepsilon$. Denote the
rooted tree corresponding to the sequence $\omega_{1},\ldots\omega_{i}$ by
$(T_{i},u_{i})$. Then $(T_{i+1},u_{i+1})$ is obtained from $(T_{i},u_{i})$ by
adding the edge $\\{v_{i+1},u_{i}\\}$ to $T_{i}$ and gluing a rooted tree
$(H,v)\in\\{K_{1},(G_{j},v_{j}),(\overline{G_{j}},v_{j})\mid j=1,\ldots,M\\}$
to $u_{i+1}$ (here $K_{1}$ denotes a single vertex.) We then have

$\left(Z^{\text{in}}_{T_{i+1},u_{i+1}}(\lambda_{0}),Z^{\text{out}}_{T_{i+1},u_{i+1}}(\lambda_{0})\right)=\left(Z^{\text{in}}_{H,v}(\lambda_{0})Z^{\text{out}}_{T_{i},u_{i}}(\lambda_{0}),Z^{\text{out}}_{H,v}(\lambda_{0})Z_{T_{i}}(\lambda_{0})\right).$
(8)

Note that (8) describes a simple recurrence to compute
$Z^{\text{in}}_{T,v}(\lambda_{0})$ and $Z^{\text{out}}_{T,v}(\lambda_{0})$ in
time linear in the number of vertices of $T$.

Finally, we remark that $Z^{\text{out}}_{T,v}(\lambda_{0})\neq 0$ since
$\lambda_{0}\notin\mathcal{E}_{\Delta}$ by assumption. ∎

We can now prove the desired inclusion of the density-locus in the
$\\#\mathcal{P}$-locus.

######  Theorem 6.6.

For any integer $\Delta\geq 3$ the density-locus
$\overline{\mathcal{D}_{\Delta}}$ is contained in the $\\#\mathcal{P}$-locus
$\overline{\\#\mathcal{P}_{\Delta}}.$

###### Proof.

We will show that for any
$\lambda_{0}\in(\mathcal{D}_{\Delta}\cap\mathbb{Q}[i])\setminus\mathcal{E}_{\Delta}$
the computational problem #Hard-CoreNorm($\lambda_{0},\Delta$) is #P-hard.
Since $\mathcal{D}^{1}_{\Delta}$ is an open set and $\mathcal{E}_{\Delta}$ is
finite, this implies the theorem.

This in fact follows directly from the work of [BGGv20]. Let us briefly
indicate why. In [BGGv20, Section 6] the authors show that a polynomial time
algorithm for #Hard-CoreNorm($\lambda_{0},\Delta$) combined with the statement
of Corollary 6.5 for $\lambda_{0}$ yields an algorithm that on input of a
graph $G$ of maximum degree at most $\Delta$ exactly computes $Z_{G}(1)$, the
number of independent sets of $G$, in polynomial time in the number of
vertices of $G$. (The algorithm is obtained by cleverly utilizing Corollary
6.5 for suitable choices of $P$ and gluing combinations of the obtained trees
to $G$ and applying the assumed algorithm for #Hard-
CoreNorm($\lambda_{0},\Delta$) to the resulting graph.) Since determining
$Z_{G}(1)$ is a known #P-complete problem, this implies that #Hard-
CoreNorm($\lambda_{0},\Delta$) is #P-hard. ∎

We note that our result does not allow us to say anything about the complexity
of #Hard-CoreNorm($\lambda_{0},\Delta$) for
$\lambda_{0}\in\partial(\mathcal{D}_{\Delta})\cap\mathbb{Q}[i]$. For example,
for $\lambda_{0}\in\partial(\mathcal{D}_{\Delta})\cap\mathbb{Q}_{\leq 0}$ it
follows from [BGGv20] that the problem #Hard-CoreNorm$(\lambda,\Delta)$ is
#P-hard. For $\lambda\in\mathbb{Q}$ such that
$\lambda\geq\lambda_{c}(\Delta):=\tfrac{(\Delta-1)^{\Delta-1)}}{(\Delta-2)^{\Delta}}$
we know from [BGGv20] that $\lambda\in\partial(\mathcal{D}_{\Delta})$, while
the complexity of #Hard-CoreNorm$(\lambda_{c}(\Delta),\Delta)$ is unknown. For
$\lambda>\lambda_{c}(\Delta)$ the problem Hard-CoreNorm$(\lambda,\Delta)$ is
only known to be NP-hard [SS14], and unlikely to be #P-hard cf.[BGGv20].

###  6.1. Proofs of Lemma 6.1 and Lemma 6.2

The next lemma directly implies Lemma 6.1.

######  Lemma 6.7.

Given $z_{0}\in\mathbb{C}\setminus\\{-1,0\\}$, a dense subset $D$ of
$\mathbb{C}^{*}$ and a non-empty open subset $A$ of the unit disk $\mathbb{D}$
then there exists a finite set of tuples
$\\{(\mu_{i},\chi_{i})\\}_{i=1}^{M}\subset D\times D$ and an arbitrarily small
open disk $U\subseteq\mathbb{C}$ containing $z_{0}$ such that the maps
$g_{i}:=f_{\mu_{i}}\circ f_{\chi_{i}}$ are loxodromic Möbius transformations
and

  1. (1)

the attracting fixed point $z_{i}$ of $g_{i}$ lies in $U$ for all $i$,

  2. (2)

$\overline{U}\subseteq\cup_{i=1}^{M}g_{i}(U)$,

  3. (3)

$g_{i}^{\prime}(z)\in A$ for all $i$ and all $z\in\overline{U}$.

###### Proof.

We denote $g_{\mu,\chi}=f_{\mu}\circ f_{\chi}$ throughout this proof. Note
$g_{\mu,\chi}$ is a Möbius transformation for $\mu,\chi\neq 0$. Without loss
of generality assume that $A$ is bounded away from $0$. Take $\alpha\in A$
such that $\alpha\neq\frac{z_{0}}{z_{0}+1}$. Note that
$\chi_{0}=\frac{(z_{0}+1)^{2}\alpha}{z_{0}-(z_{0}+1)\alpha}$ and
$\mu_{0}=\frac{z_{0}(z_{0}+\chi_{0}+1)}{z_{0}+1}$ are nonzero and well defined
as $z_{0}\neq-1,0$ and $\alpha\neq\frac{z_{0}}{z_{0}+1},0$. Furthermore we
have $g_{\mu_{0},\chi_{0}}(z_{0})=z_{0}$ and
$g_{\mu_{0},\chi_{0}}^{\prime}(z_{0})=\alpha$.

Define $F:(\mathbb{C}^{*})^{2}\times\mathbb{C}\rightarrow\hat{\mathbb{C}}$ as
$F(\mu,\chi,z)=g_{\mu,\chi}(z)-z$. Now as $\frac{\partial F}{\partial
z}(\mu_{0},\chi_{0},z_{0})=\alpha-1\neq 0$, the implicit function theorem
gives an open neighborhood $W$ of $(\mu_{0},\chi_{0})$ and a holomorphic
function $h:W\rightarrow\mathbb{C}$ with $h(\mu_{0},\chi_{0})=z_{0}$ and
$F(\mu,\chi,h(\mu,\chi))=0$ for all $(\mu,\chi)\in W$. As $h$ is a non-
constant holomorphic map, it is an open map and so $h(W)$ is an open
neighborhood of $z_{0}$.

Let $B\subseteq A$ be an open set in $\mathbb{C}$ with $\alpha\in B$ and
$\overline{B}\subseteq A$. Denote $H(\mu,\chi,z)=\frac{\partial
g_{\mu,\chi}}{\partial z}(z)=\frac{\mu\chi}{(1+z+\chi)^{2}}$, note that $H$ is
continuous as a function on
$\mathbb{C}^{3}\setminus\\{(\mu,\chi,z):\chi+z+1=0\\}$. It follows there is an
open neighborhood $C$ of $z_{0}$ such that we have $H(\mu_{0},\xi_{0},z)\in B$
for all $z\in C$. We have $\\{(\mu_{0},\chi_{0})\\}\times\overline{C}\subseteq
H^{-1}(\overline{B})\subseteq H^{-1}(A)$. As $H^{-1}(A)$ is an open subset of
$\mathbb{C}^{3}\setminus\\{(\mu,\chi,z):\chi+z+1=0\\}$ containing the set
$\\{(\mu_{0},\chi_{0})\\}\times\overline{C}$, by a compactness argument it
follows that $H^{-1}(A)$ contains a set of the form $L\times C$, for some open
neighborhood $L$ of the point $(\mu_{0},\chi_{0})$. Hence the set $Y:=L\cap
W\cap h^{-1}(C)$ is an open neighborhood of $(\mu_{0},\chi_{0})$ and so $h(Y)$
is an open neighborhood of $z_{0}$.

Take $U\subset h(Y)$ an open disk containing $z_{0}$, such that
$\overline{U}\subset h(Y)$. Note that we can take $U$ arbitrarily small. By
construction, we have for all $(\mu,\chi)\in Y$ that
$g_{\mu,\chi}^{\prime}(z)\in A$ for all $z\in\overline{U}$. Furthermore, we
have $F(\mu,\chi,h(\mu,\chi))=0$, so $h(\mu,\chi)$ is the attracting fixed
point of $g_{\mu,\chi}$. Note $D\times D$ is dense in $h^{-1}(U)$, hence the
fixed points of $g_{\mu,\chi}$ for $(\mu,\chi)\in h^{-1}(U)\cap(D\times D)$
lie dense in $U$. There is a uniform lower bound on the diameters of the disks
$g_{\mu,\chi}(U)$ for $(\mu,\chi)\in h^{-1}(U)$, because
$g^{\prime}_{\mu,\chi}(z)\in A$ for all $z\in U$ and $A$ is bounded away from
$0$. Therefore

$\left\\{g_{\mu,\chi}(U):(\mu,\chi)\in h^{-1}(U)\cap(D\times D)\right\\}$

is an open cover of $\overline{U}$. As $\overline{U}$ is compact, there is a
finite set of tuples $\\{(\mu_{i},\chi_{i})\\}_{i=1}^{M}\subseteq
h^{-1}(U)\cap(D\times D)$ such that
$\overline{U}\subseteq\cup_{i=1}^{M}g_{\mu_{i},\chi_{i}}(U)$. We thus found
the desired set of tuples in $D\times D$ and the open disk $U$ containing
$z_{0}$. ∎

We next focus on proving Lemma 6.2. To this end let
$\lambda_{0}\in\mathbb{C}\setminus\mathbb{R}$ and let
$(\\{(G_{1},v_{1}),\ldots,(G_{m},v_{m}),(\overline{G}_{1},\overline{v_{1}}),\ldots,(\overline{G}_{M},\overline{v}_{M})\\},U)$
be a fast implementer for $\lambda_{0}$. We fix these throughout this section.
We denote the repelling fixed point of $f_{\lambda_{0}}$ by $z_{0}$ and we
denote for $i=1,\ldots,M$, $\mu_{i}:=R_{G_{i},v_{i}}$,
$\chi_{i}:=R_{\overline{G}_{i},\overline{v_{i}}}$ and $g_{i}:=f_{\mu_{i}}\circ
f_{\chi_{i}}$. We distinguish between the case that $P$ is close to the
attracting fixed point of $f_{\lambda_{0}}$ and the case that it is not. In
the first case the algorithm is much simpler.

Let $a$ be the attracting fixed point of $f_{\lambda_{0}}$. Because
$f_{\lambda_{0}}(\infty)=0$ we observe that $\infty$ is not a fixed point and
thus $a\in\mathbb{C}$. Suppose that $|P-a|\leq\epsilon/2$. Choose $\delta>0$
for which there is a constant $\eta<1$ such that
$|f_{\lambda_{0}}^{\prime}(z)|<\eta$ for all $z\in B(a,\delta)$. The point $0$
is not a fixed point of $f_{\lambda_{0}}$ because
$f_{\lambda_{0}}(0)=\lambda_{0}\neq 0$ and thus $f_{\lambda_{0}}^{n}(0)$
converges to $a$ as $n\to\infty$. It follows that there is a constant $N_{0}$
such that $f_{\lambda_{0}}^{N_{0}}(0)\in B(a,\delta)$. Note that the value of
$N_{0}$ does not depend on the input parameters. Now let
$N_{\epsilon}=\max{\\{\lceil\log_{\eta}(\frac{\epsilon}{2\delta})\rceil,0\\}}+1$.
Then for any $w\in B(a,\delta)$ we have

$|f_{\lambda_{0}}^{N_{\epsilon}}(w)-a|<\eta^{N_{\epsilon}}|w-a|<\epsilon/2$

and thus for $K=N_{0}+N_{\epsilon}$ we have

$|f_{\lambda_{0}}^{K}(0)-P|\leq|f_{\lambda_{0}}^{N_{\epsilon}}(f_{\lambda_{0}}^{N}(0))-a|+|a-P|<\epsilon/2+\epsilon/2<\epsilon.$

Because $K=\mathcal{O}(\log(1/\epsilon))$ this describes the algorithm when
$|P-a|\leq\epsilon/2$.

The case that $|P-a|>\epsilon/2$ is more involved and we will describe the
algorithm as a sequence of simpler subroutines. Just as in Lemma 6.7 let
$z_{i}$ denote the attracting fixed point of $g_{i}$. We will show first show
that, given a parameter $Q$ that is at most distance $\epsilon$ away from some
$z_{i}$, we only have to apply $g_{i}$ to the starting value $0$ an
$\mathcal{O}(\log(1/\epsilon))$ number of times to get $\epsilon$ close to
$Q$. Morally, this should be true because after a fixed number of steps the
orbit of $0$ converges exponentially quickly to $z_{i}$ and because $z_{i}$ is
close to $Q$ the orbit should also get close to $Q$. The only way that this
reasoning could be incorrect is if $z_{i}$ and $Q$ are almost $\epsilon$ apart
and the orbit of $0$ converges to $z_{i}$ from the wrong direction. An example
of this is given by the red orbit in Figure 6. This is the reason that we
required $g_{i}^{\prime}(z_{i})$ to have an argument close to $2\pi/3$ in
which case the above reasoning is correct as the green orbit in Figure 6
demonstrates. In the following proof most time is spent on making this
precise.

$Q$$\epsilon$$z_{i}$ Figure 6. An example of two orbits with the same initial
value converging to $z_{i}$ under iteration of two different maps. For the red
orbit the derivative at $z_{i}$ is real. For the green orbit the derivative at
$z_{i}$ has the same magnitude, while its argument is a little less than
$2\pi/3$.

######  Lemma 6.8.

There exists an algorithm that, given $\epsilon>0$, $Q\in\mathbb{C}$ and
$i\in\\{1,\dots,M\\}$ such that $|Q-z_{i}|<\epsilon$, yields an integer $K$
such that $|g_{i}^{K}(0)-Q|<\epsilon$, where
$K=\mathcal{O}(\log(1/\epsilon))$. If $\lambda_{0}\in\mathbb{Q}[i]$ and the
input parameters $Q,\epsilon$ lie in $\mathbb{Q}[i]$ then the algorithm runs
in $poly(\mathrm{size}(Q,\epsilon))$ time.

###### Proof.

Let $\delta$ be such that $B(z_{i},\delta)\subseteq U$ and let
$\epsilon^{\prime}=\min\\{\epsilon/2,\delta\\}$. Note that
$g_{i}(0)=\frac{\mu_{i}}{1+\chi_{i}}\neq 0$ and thus $0$ is not a fixed point
of $g_{i}$. Because $z_{i}$ is the attracting fixed point of $g_{i}$ we can
find (in a similar way as described above) a positive integer $\tilde{K}$ that
is $\mathcal{O}(\log(1/\epsilon^{\prime}))=\mathcal{O}(\log(1/\epsilon))$ such
that $|g_{i}^{\tilde{K}}(0)-z_{i}|<\epsilon^{\prime}$. If
$|Q-z_{i}|\leq\epsilon/2$ we are done because then

$|g_{i}^{\tilde{K}}(0)-Q|\leq|g_{i}^{\tilde{K}}(0)-z_{i}|+|Q-z_{i}|<\epsilon^{\prime}+\epsilon/2\leq\epsilon.$

So from now on we assume that $|Q-z_{i}|>\epsilon/2$. Define the following
sector $S$ of $B(z_{i},\epsilon^{\prime})$

$S=\\{z_{i}+\xi\cdot\left(\frac{Q-z_{i}}{|Q-z_{i}|}\right):|\xi|<\epsilon^{\prime},-\pi/3\leq\arg(\xi)\leq\pi/3\\}.$

We claim that $S\subseteq B(Q,\epsilon)$. To show this note that

$\left|Q-\left[z_{i}+\xi\cdot\left(\frac{Q-z_{i}}{|Q-z_{i}|}\right)\right]\right|=\left|Q-z_{i}\right|\cdot\left|1-\frac{\xi}{|Q-z_{i}|}\right|<\epsilon\cdot\left|1-\frac{\xi}{|Q-z_{i}|}\right|.$

If $\xi$ is as in the definition of $S$ the complex number $\xi/|Q-z_{i}|$ has
its argument between $-\pi/3$ and $\pi/3$. Furthermore, because
$|\xi|<\epsilon/2$ and $|Q-z_{i}|>\epsilon/2$, its norm is bounded above by
$1$. It follows that the norm of $1-\xi/|Q-z_{i}|$ is at most 1. Indeed,
because $|1-re^{i\phi}|^{2}=1+r^{2}-2r\cos(\phi)$, the statement
$|1-re^{i\phi}|\leq 1$ is equivalent to $r=0$ or $r\leq 2\cos(\phi)$, and the
latter is satisfied for all $0\leq r\leq 1$ and $-\pi/3\leq\phi\leq\pi/3$. The
claim follows.

We now claim that for $w\in B(z_{i},\epsilon^{\prime})$ the intersection of
$\\{w,g_{i}(w),g_{i}^{2}(w),g_{i}^{3}(w)\\}$ with $S$ is not empty. Note that
because $\epsilon^{\prime}\leq\delta$ we have that
$B(z_{i},\epsilon^{\prime})\subseteq U$ and thus $g^{\prime}(w)\in A$ for
every $w\in B(z_{i},\epsilon^{\prime})$. It follows that applying $g_{i}$ to
$w$ has the effect of rotating around $z_{i}$ with an angle strictly between
$2\pi/3-0.01$ and $2\pi/3$ and contracting towards $z_{i}$. Therefore applying
$g_{i}$ to $w$ three times has the effect of rotating $w$ a little less than a
full circle around $z_{i}$, with steps that are strictly less than $2\pi/3$
radians. Because the internal angle of the sector $S$ is $2\pi/3$ the orbit
$w,g_{i}(w),g_{i}^{2}(w),g_{i}^{3}(w)$ cannot miss $S$.

To summarize the algorithm, define $\epsilon^{\prime}$ and determine
$\tilde{K}$ such that $g_{i}^{\tilde{K}}(0)\in B(z_{i},\epsilon^{\prime})$.
Then determine a $j\in\\{0,1,2,3\\}$ such that
$|g_{i}^{\tilde{K}+j}(0)-Q|<\epsilon$. We have shown that there exists at
least one such $j$. The output of the algorithm is $K=\tilde{K}+j$.

∎

We shall now describe an algorithm that does the following. Given a disk $D$
of radius $\epsilon$ inside $U$, it returns an index $i$, a disk $\tilde{D}$
of radius at least $\epsilon$ containing $z_{i}$ and a sequence of indices
$j_{1},\dots,j_{K}$ such that $(g_{j_{1}}\circ\cdots\circ
g_{j_{K-1}})(\tilde{D})\subseteq D$. To describe the computational complexity
of this algorithm, we need a finite way to represent disks in the complex
plane. A pleasant way for our purposes is to represent an open disk $D$ by
three distinct points $P_{1},P_{2},P_{3}$ on its boundary. This is an
unambiguous way to represent a disk because three different points on a circle
uniquely determine that circle. If $P_{1},P_{2},P_{3}\in\mathbb{Q}[i]$ we say
that the disk $D$ is rational and that
$\mathrm{size}(D)=\mathrm{size}(P_{1})+\mathrm{size}(P_{2})+\mathrm{size}(P_{3})$.

Recall that a Möbius transformation maps generalized circles (circles and
straight lines) to generalized circles. In what follows, we will apply Möbius
transformations to disks in the complex plane. We shall make sure that the
image of the disks involved is always again a disk in the complex plane and
not the complement of a disk or a half-plane as it could in general be.
Therefore, if $D$ is a disk represented by $P_{1},P_{2}$ and $P_{3}$ and $g$
is one of the Möbius transformations, then $g(D)$ will be a disk represented
by $g(P_{1}),g(P_{2})$ and $g(P_{3})$. Note that if $D$ is rational and $g$
has rational coefficients then $g(D)$ is a again rational. The Möbius
transformations that we will apply come from a fixed finite set and thus there
is a fixed constant $C$ for which $\mathrm{size}(g(D))\leq
C\cdot\mathrm{size}(D)$.

Let us denote $P_{j}=x_{j}+iy_{j}$ for $j\in\\{1,2,3\\}$. The center
$c_{D}=x+yi$ of the disk $D$ is known as the circumcenter of the triangle with
vertices $P_{1},P_{2}$ and $P_{3}$. The coordinates of $c_{D}$ can be
calculated using the well known and easy to derive formulas

$\displaystyle x$
$\displaystyle=\frac{(x_{1}^{2}+y_{1}^{2})(y_{2}-y_{3})+(x_{2}^{2}+y_{2}^{2})(y_{3}-y_{1})+(x_{3}^{2}+y_{3}^{2})(y_{1}-y_{2})}{2(x_{1}(y_{2}-y_{3})+x_{2}(y_{3}-y_{1})+x_{3}(y_{1}-y_{2}))},$
$\displaystyle y$
$\displaystyle=\frac{(x_{1}^{2}+y_{1}^{2})(x_{3}-x_{2})+(x_{2}^{2}+y_{2}^{2})(x_{1}-x_{3})+(x_{3}^{2}+y_{3}^{2})(x_{2}-x_{1})}{2(x_{1}(y_{2}-y_{3})+x_{2}(y_{3}-y_{1})+x_{3}(y_{1}-y_{2}))}.$

We note that if $D$ is rational, then $c_{D}$ is rational and can be computed
in time linear in $\mathrm{size}(D)$. We can also decide whether a given point
$Q\in\mathbb{Q}[i]$ lies in a given rational disk $D$ in time linear in
$\mathrm{size}(Q)$ and $\mathrm{size}(D)$.

We next need a lemma concerning a geometric construction involving disks.

$A$$B$$c_{A}$$c_{B}$$S_{1}$$S_{2}$ Figure 7. -
$P_{i+1}$$P_{i}$$\frac{P_{i}+P_{i+1}}{2}$$c_{D}$$c_{A}$$c_{A}$$Q_{1}$$Q_{2}$$P_{i}$$c_{D}$
Figure 8. -

######  Lemma 6.9.

There exists an algorithm that, given two disks $A,B$ in the complex plane for
which the center of $A$ is contained in $B$ and $B$ is not contained in $A$,
returns a disk $D$ contained in both $A$ and $B$, such that the area of $D$ is
at least $1/128$ times that of $A$. Furthermore, if $A$ and $B$ are rational
then $D$ is rational and both the running time of the algorithm and
$\mathrm{size}(D)$ are bounded by a fixed constant times $\mathrm{size}(A,B)$.

###### Proof.

For a disk $D$ we denote its center by $c_{D}$ and its radius by $r_{D}$ and
recall that if $D$ is rational then $c_{D}$ is rational and can be computed
efficiently. For two distinct points $P,Q$ on the boundary of $D$ we denote
the closed counterclockwise arc from $P$ to $Q$ by
$\textrm{Arc}_{D}\left(P,Q\right)$ and we denote the sector given by the
convex hull of $\textrm{Arc}_{D}\left(P,Q\right)$ and $c_{D}$ by
$\textrm{Sec}_{D}\left(P,Q\right)$. We note that the internal angle of both
$\textrm{Arc}_{D}\left(P,Q\right)$ and $\textrm{Sec}_{D}\left(P,Q\right)$ is
given by the arclength of $\textrm{Arc}_{D}\left(P,Q\right)$ divided by
$r_{D}$. We claim that either a sector of $A$ whose internal angle is greater
than $2\pi/3$ is contained in the closure of $B$ or a sector of $B$ whose
internal angle is greater than $2\pi/3$ is contained in the closure of $A$.

If the boundaries of $A$ and $B$ either do not intersect or intersect in one
point then $A$ is contained in $B$ and the claim is obvious. Otherwise let
$S_{1},S_{2}$ be the two intersection points such that
$\textrm{Arc}_{A}\left(S_{1},S_{2}\right)$ is contained in $B$ and thus
$\textrm{Arc}_{B}\left(S_{2},S_{1}\right)$ is contained in $A$, see Figure 7.
Consider the quadrilateral $\square c_{B}S_{1}c_{A}S_{2}$ and suppose towards
contradiction that the internal angles at both $c_{A}$ and $c_{B}$ are at most
$2\pi/3$, then the sum of the internal angles at $S_{1}$ and $S_{2}$ is at
least $2\pi/3$ and since they are equal by symmetry the internal angle at
$S_{1}$ is at least $\pi/3$. By then considering the triangle $\triangle
c_{B}S_{1}c_{A}$ it should follow that $|c_{B}-c_{A}|\geq|c_{B}-S_{1}|=r_{B}$,
which contradicts the assumption that $c_{A}$ is contained in $B$. We
therefore find that either the angle $\angle S_{2}c_{B}S_{1}$ or $\angle
S_{2}c_{A}S_{1}$ is at least $2\pi/3$. If the latter is the case then both
$\textrm{Arc}_{A}\left(S_{1},S_{2}\right)$ and $c_{A}$ are contained in the
closure of $B$ and thus the same is true for
$\textrm{Sec}_{A}\left(S_{1},S_{2}\right)$. If the angle $\angle
S_{2}c_{A}S_{1}$ is less than $2\pi/3$, then $\angle S_{2}c_{B}S_{1}$ is at
least $2\pi/3$. It follows that $\angle c_{A}c_{B}S_{1}$ is the largest
internal angle of the triangle $\triangle c_{B}S_{1}c_{A}$ and thus
$|c_{A}-c_{B}|<|c_{A}-S_{1}|=r_{A}$, from which it follows that $c_{B}$ is
contained in $A$. So in this case $\textrm{Sec}_{B}\left(S_{2},S_{1}\right)$
is contained in $A$.

For the algorithm we do not need to know whether a large sector of $B$ is
contained in $A$ or vice versa. Assume for simplicity that a sector $S$ of $A$
with internal angle at least $2\pi/3$ is contained in $B$. Take $S$ to be as
large as possible. In the case that $A$ is contained in $B$ we let $S=A$. Let
$P_{0}$ denote one of the given (rational) points on the boundary of $A$. Now
for $i=0,1,2$ inductively define $P_{i+1}$ as $P_{i}$ rotated around $c_{A}$
with an angle of $\pi/2$. Calculating these points is computationally easy
because $P_{i+1}=c_{A}+i(P_{i}-c_{A})$. Now one of the following is guaranteed
to be the case.

  1. (1)

Two consecutive points $P_{i}$ and $P_{i+1}$ are contained in $S$.

  2. (2)

There is a unique index $i$ such that $P_{i}\in S$.

Determining which of the two cases is true is easy since checking membership
of $S$ is equivalent to checking membership of $B$. In the first case we note
that $\textrm{Sec}_{A}\left(P_{i},P_{i+1}\right)$ is contained in both the
closures of $A$ and $B$. Now let $R=(P_{i}+P_{i+1})/2$ and
$c_{D}=(c_{A}+3R)/4$ and let $D$ be the disk with center $c_{D}$ and the point
$R$ on the boundary, see Figure 8. It can be checked that $D$ is now contained
in $\textrm{Sec}_{A}\left(P_{i},P_{i+1}\right)$ and its area is $1/32$ that of
$A$.

In the second case note that the arc
$\textrm{Arc}_{A}\left(Q_{1},Q_{2}\right)$ containing $P_{i}$ such that the
internal angle of both $\textrm{Arc}_{A}\left(Q_{1},P_{i}\right)$ and
$\textrm{Arc}_{A}\left(P_{i},Q_{2}\right)$ is $\pi/6$ contained in $S$,
otherwise, since the internal angle of $S$ is at least $2\pi/3$, $S$ has to
contain two consecutive points $P_{i}$ and $P_{i+1}$. Now let $D$ be the disk
with center $(c_{A}+3P_{i})/4$ containing $P_{i}$ on its boundary, see Figure
8. It can be checked that $D$ is contained in
$\textrm{Sec}_{A}\left(Q_{1},Q_{2}\right)$ and its area is $1/16$ that of $A$.

The algorithm above is only guaranteed to successfully return a disk contained
in both $A$ and $B$ if a large sector of $A$ is contained in $B$. Therefore we
have to run the algorithm described above (and let it fail if neither of the
two described cases is true) and run the same algorithm with the roles of $A$
and $B$ reversed. If both instances of the algorithm return a disk, say
$D_{1}$ and $D_{2}$, then at least one of them is contained in both $A$ and
$B$ but the other one might not be. So in this case we have to run one final
check to see which one of the two disks is indeed contained in both $A$ and
$B$ (which is computationally easy). If they both are we can return either
$D_{1}$ or $D_{2}$.

In conclusion we obtain a disk $D$ contained in both $A$ and $B$ that is
either at least $1/32$ of the area of $A$ or $1/32$ of the area of $B$.
Because the area of $B$ is at least $1/4$ that of $A$ (otherwise
$r_{B}<r_{A}/2$ and $c_{A}\in B$ would imply $B\subseteq A$), we can conclude
that the area of $D$ is at least $(1/4)\cdot(1/32)=1/128$ that of $A$.

∎

######  Lemma 6.10.

There exists an algorithm that, given a disk $D_{1}\subseteq U$ with radius
$\epsilon$, returns an index $i\in\\{1,\dots,M\\}$, a sequence of indices
$j_{1},\dots,j_{K}\in\\{1,\dots,M\\}$ and a disk $D_{K}$ such that $z_{i}\in
D_{K}$, the radius of $D_{K}$ is at least $\epsilon$ and
$(g_{j_{1}}\circ\cdots\circ g_{j_{K-1}})(D_{K})\subseteq D_{1}$. Furthermore,
$K=\mathcal{O}(\log(1/\epsilon))$. If $\lambda_{0}\in\mathbb{Q}[i]$ and
$D_{1}$ and $\epsilon$ are both rational then $D_{K}$ is rational and the
algorithm runs in $poly(\mathrm{size}(D_{1},\epsilon))$ time.

###### Proof.

For every index $i$ let $U_{i}=g_{i}(U)$. Recall that we took $U$ as a
rational disk. Because the derivative of $g_{i}$ is bounded on $U$, the image
$U_{i}$ is again a disk in the complex plane. If $\lambda_{0}$ is rational,
the coefficients of $g_{i}$ are rational and then $U_{i}$ is also rational.
The point $z_{i}$ is fixed for $g_{i}$ and contained in $U$, therefore, also
contained in $U_{i}$. We describe a procedure to generate a sequence of disks
$\\{D_{n}\\}_{n\geq 1}$, starting with the given disk $D_{1}$. The sequence is
defined in such a way such that $D_{n}\subseteq U$ for all $n$, which is, by
assumption, the case for $D_{1}$.

Suppose we have arrived at disk $D_{n}\subseteq U$. Check if there is any
index $i\in\\{1,\dots,M\\}$ such that $z_{i}\in D_{n}$, if there is stop the
procedure and let $K=n$. Otherwise, let $m_{n}$ be the center of $D_{n}$ and
determine an index $j_{n}\in\\{1,\dots,M\\}$ such that $m_{n}\in U_{j_{n}}$.
Such an index must exist because $m_{n}\in U$ and the disks
$U_{1},\dots,U_{M}$ cover $U$. Because the center of $D_{n}$ lies in
$U_{j_{n}}$ but $U_{j_{n}}$ is not contained in $D_{n}$ ($z_{j_{n}}$ does not
lie in $D_{n}$) we can use Lemma 6.9 to generate a disk $\tilde{D}_{n}$ that
is contained in both $D_{n}$ and $U_{j_{n}}$ whose area is at least $1/128$
times that of $D_{n}$ and which can be assumed to be rational if $D_{n}$ is.
Now we define $D_{n+1}=g_{j_{n}}^{-1}(\tilde{D}_{n})$. Because
$\tilde{D}_{n}\subseteq U_{j_{n}}$ the disk $D_{n+1}$ lies in $U$ and because
$\tilde{D}_{n}\subseteq D_{n}$ the disk $g_{j_{n}}(D_{n+1})$ lies in $D_{n}$.
Furthermore, by the properties of the fast implementer, $g_{j_{n}}^{-1}$ is
expanding the norm on $U_{j_{n}}$ with a factor at least $16$, the area of
$D_{n+1}$ is at least $16^{2}\cdot(1/128)=2$ times that of $D_{n}$. This means
that the area of $D_{n}$ grows exponentially with $n$ and thus, because the
area of $U$ is fixed, the procedure will terminate after
$K=\mathcal{O}(\log(1/\epsilon))$ steps. Note that indeed $z_{i}\in D_{K}$ for
some $i$, the radius of $D_{K}$ is at least that of $D_{1}$ and
$(g_{j_{1}}\circ\cdots\circ j_{K-1})(D_{K})\subseteq D_{1}$. ∎

Recall that we had defined $a$ and $z_{0}$ to be the attracting and repelling
fixed point of $f_{\lambda_{0}}$ respectively. We have already described the
algorithm in Lemma 6.2 when $P$ is near $a$. What follows is the final lemma
needed to describe the algorithm when $P$ is not near $a$.

######  Lemma 6.11.

There exists a fixed positive constant $c$ and an algorithm that, given
$P\in\mathbb{C}$ and $\epsilon>0$ such that $|P-a|\geq\epsilon/2$, yields a
disk $D\subseteq U$ and a positive integer $K$ with
$f_{\lambda_{0}}^{K}(D)\subseteq B(P,\epsilon)$, such that the radius of $D$
is at least $c\cdot\min{(\epsilon,\epsilon/|P|^{2})}$ and
$K=\mathcal{O}(\log(1/\epsilon))$. If both $\lambda_{0}$ and the input
parameters are in $\mathbb{Q}[i]$ then $D$ is also rational and both
$\mathrm{size}(D)$ and the running time of the algorithm is polynomial in
$\mathrm{size}(P,\epsilon)$.

###### Proof.

Let $V$ be a compact neighborhood of $a$ such that
$|f_{\lambda_{0}}^{\prime}(z)|<\xi<1$ for some constant $\xi$ for all $z\in
V$. We first claim that there is an integer $N$ such that the complement of
$f_{\lambda_{0}}^{N}(U)$ is contained in $V$. To show this let
$U_{n}=f_{\lambda_{0}}^{n}(U)$. Recall that we assumed that
$\overline{U}=\overline{U_{0}}\subseteq U_{1}$ and thus inductively
$\overline{U_{n}}\subseteq{U_{n+1}}$. Under iteration of
$f_{\lambda_{0}}^{-1}$ every initial point that is not $a$ converges to
$z_{0}$ and thus eventually lands in $U$. Therefore,

$\bigcup_{n=1}^{\infty}U_{n}=\widehat{\mathbb{C}}\setminus\\{a\\}.$

For $n$ large enough the point $\infty$ is contained in $U_{n}$ and from then
on the sequence $(U_{n})^{c}$ consists of nested disks, containing $a$, whose
radii must necessarily converge to $0$, proving that there is an $N$ such that
$(U_{N})^{c}$ is contained in $V$. Note that $N$ does not depend on the input
parameters. Let $D_{0}$ be the interior of $(U_{N})^{c}$, this is a rational
disk whose size also does not depend on the input, and let
$D_{i}=f_{\lambda_{0}}^{i}(D_{0})$ for $i\in\\{1,2,3\\}$. Let $\delta>0$ be a
constant smaller than the minimum distance between points on the boundary of
$D_{i}$ and $D_{i-1}$. From now on we will assume that $\epsilon<\delta$.
Finally let $h=f_{\lambda_{0}}^{-(N+3)}$.

If $P$ lies outside $D_{2}$, then let $\tilde{D}$ be the disk of radius
$\epsilon$ represented by $P+\epsilon,P+i\epsilon$ and $P-\epsilon$. Note that
$\tilde{D}$ lies outside $D_{3}$ and thus $D=h(\tilde{D})\subset U$. Because
the derivative of a Möbius transformation of the form $z\mapsto(az+b)/(cz+d)$
is $z\mapsto\frac{ad-bc}{(cz+d)^{2}}$ there is a constant $c_{1}$ such that
the radius of $D$ is at least $c_{1}\cdot\min{(\epsilon,\epsilon/|P|^{2})}$.
In this case $D$ and $K=N+3$ are the output of the algorithm.

If $P$ lies inside $D_{2}$ we determine $N_{0}$ such that for
$P_{N_{0}}:=f_{\lambda}^{-N_{0}}(P)$ we have $P_{N_{0}}\in D_{1}$ and
$P_{N_{0}}\not\in D_{2}$. Because $|P-a|\geq\epsilon/2$ and $D_{1}\subset V$
we find that $N_{0}=\mathcal{O}(\log(1/\epsilon))$. Let $\tilde{D}$ be the
disk of radius $\epsilon$ represented by
$P_{N_{0}}+\epsilon,P_{N_{0}}+i\epsilon$ and $P_{N_{0}}-\epsilon$. Note that
again $\tilde{D}$ lies outside $D_{3}$ and thus $D=h(\tilde{D})\subseteq U$.
Furthermore, because $\tilde{D}\subset D_{0}\subset V$ and $f_{\lambda_{0}}$
is attracting on $V$ it follows that
$f_{\lambda_{0}}^{N_{0}}(\tilde{D})\subseteq B(P,\epsilon)$. Finally, if we
let $c_{2}$ be the minimum of $|h^{\prime}(z)|$ for $z\in D_{0}$, we find that
the radius of $D$ is at least $c_{2}\cdot\epsilon$. So in this case the output
is the disk $D$ together with $K=N_{0}+N+3$.

∎

We are now ready to complete the proof of Lemma 6.2.

###### Proof of Lemma 6.2.

Recall we had defined $a$ to be the attracting fixed point of
$f_{\lambda_{0}}$ and that we already described the algorithm in the case that
$|P-a|<\epsilon/2$, therefore we assume that $|P-a|\geq\epsilon/2$.

It follows from Lemma 6.11 that we can generate a disk $D_{1}\subseteq U$ of
radius $r=\mathcal{O}(\min{\\{\epsilon,\epsilon/|P|^{2}\\}})$ and whose size
is polynomial in $\mathrm{size}(P,\epsilon)$ together with a positive integer
$K_{1}$ that is $\mathcal{O}(\log(1/\epsilon))$ such that
$f_{\lambda_{0}}^{K_{1}}(D_{1})$ is contained in $B(P,\epsilon)$. From Lemma
6.10 it follows that we can find an index $i\in\\{1,\dots,M\\}$, a sequence of
indices $j_{1},\dots,j_{K_{2}}$ and a disk $D_{2}$ such that $z_{i}\in D_{2}$,
the radius of $D_{2}$ is at least $r$, its size is polynomial in
$\mathrm{size}(r,D_{1})$, which is again polynomial in
$\mathrm{size}(\epsilon,P)$, and such that

$(g_{j_{1}}\circ\cdots\circ g_{j_{K_{2}}})(D_{2})\subseteq D_{1}.$

Furthermore
$K_{2}=\mathcal{O}(\log(1/r))=\mathcal{O}(\max{(\log(1/\epsilon),\log(|P|/\epsilon))})$.
Finally let $Q$ be the center of $D_{2}$ and note that $\mathrm{size}(Q)$ is
polynomial in $\mathrm{size}(D_{2})$. Then, because $|Q-z_{i}|<r$, it follows
from Lemma 6.8 that we can generate a $K_{3}$ such that $g_{i}^{K_{3}}(0)\in
D_{2}$, where
$K_{3}=\mathcal{O}(\log(1/r))=\mathcal{O}(\max{(\log(1/\epsilon),\log(|P|/\epsilon))})$.
Concluding, we find that

$(f_{\lambda_{0}}^{K_{1}}\circ g_{j_{1}}\circ\cdots\circ
g_{j_{K_{2}}}\circ\circ g_{i}^{K_{3}})(0)\in B(P,\epsilon).$

Furthermore, adding the running times of the individual algorithms, we find
that the final algorithm runs in $poly(\mathrm{size}(P,\epsilon))$ time. ∎

##  7\. Activity and zeros for Cayley trees

For fixed $\Delta\geq 2$ notions such as the activity-locus and the zero sets
can be considered for subcollections of $\mathcal{G}_{\Delta}$. Particularly
interesting subcollections from a physical viewpoint are given by subgraphs of
regular lattices. However, it is notoriously difficult to rigorously deduce
the properties for such collections.

A much simpler collection of rooted graphs in $\mathcal{G}_{\Delta}$ is given
by finite Cayley trees, and we will describe the properties of those in this
section. The trees are uniquely determined by the conditions that every leaf
has fixed distance $n$ to the root vertex $v$, and every non-leaf has down-
degree $d=\Delta-1$. The root vertex therefore has degree $d$, while every
other non-leaf has degree $\Delta$. We denote the Cayley tree of depth $n$ by
$T_{n}$, and its root by $v_{n}$.

As an immediate consequence of Lemma 2.4 we obtain

$R_{T_{n},v_{n}}(\lambda)=f_{\lambda,d}(R_{T_{n-1},v_{n-1}}(\lambda)),$

where $f_{\lambda,d}(z)=\lambda/(1+z)^{d}$. Since the ratio of a single point
is given by $\lambda=f_{\lambda,d}(0)$, it follows inductively that

$R_{T_{n},v_{n}}(\lambda)=f_{\lambda,d}^{n+1}(0).$

In fact, since

$Z^{out}_{T_{n},v_{n}}(\lambda)=\left(Z_{T_{n-1},v_{n-1}}(\lambda)\right)^{d}$

and

$Z^{in}_{T_{n},v_{n}}(\lambda)=\lambda\left(Z^{out}_{T_{n-1},v_{n-1}}(\lambda)\right)^{d}$

it follows by induction on $n$ that for $\lambda\in\mathbb{C}\setminus\\{0\\}$
the polynomials $Z^{in}_{T_{n},v_{n}}(\lambda)$ and
$Z^{out}_{T_{n},v_{n}}(\lambda)$ cannot vanish simultaneously. For
$\lambda\in\mathbb{C}\setminus\\{0\\}$ it follows that $Z_{T_{n}}(\lambda)=0$
if and only if $R_{T_{n},v_{n}}(\lambda)=f_{\lambda,d}^{n}(0)=-1$.

In what follows we deduce properties of the zeros of $Z_{T_{n}}(\lambda)$ and
the activity-locus of $f_{\lambda,d}^{n}(0)$ from well known results in the
field of holomorphic dynamical systems, occasionally adapting the proofs to
our setting. We refer the reader to the standard references [Mil06, CG93].

Observe that $f_{\lambda,d}(-1)=\infty$ and $f_{\lambda,d}(\infty)=0$, and
$f_{\lambda,d}^{\prime}(-1)=f_{\lambda,d}^{\prime}(\infty)=0$. Thus if
$f_{\lambda_{0},d}^{n}(0)=-1$ for some $\lambda_{0}$ and $n$, then $0$ is an
attracting periodic cycle of period $n+2$. This cycle is stable under
perturbations of $\lambda_{0}$, i.e. the attracting cycle persists and in fact
varies holomorphically for nearby parameters $\lambda\sim\lambda_{0}$ by the
implicit function theorem.

Recall that every attracting cycle attracts the orbit of a critical point. But
$f_{\lambda,d}$ has only one critical orbit: the orbit of $-1$, $\infty$ and
$0$. Thus whenever $f_{\lambda,d}$ has an attracting cycle, the orbit
$f_{\lambda,d}^{n}(0)$ converges to the attracting cycle. In fact, the
convergence is uniform in a neighborhood of the parameter $\lambda_{0}$, hence
$\lambda_{0}$ cannot lie in the activity-locus. The situation is therefore
fundamentally different from the setting where the whole family of graphs
$\mathcal{G}_{\Delta}$ is considered, as there $\lambda_{0}$ must lie in the
activity-locus. The following however does hold:

######  Proposition 7.1.

The activity-locus of the family $\\{T_{n},v_{n}\\}$ equals the collection of
accumulation points of the zeros of the collection $\\{Z_{T_{n}}\\}$.

###### Proof.

If there are no zeros in a neighborhood of some $\lambda_{0}$, then the family
$\\{R_{T_{n},v_{n}}\\}$ avoids the values $0,-1$ and $\infty$, and is normal
by Montel’s Theorem.

Suppose on the other hand that $\lambda_{0}$ is an accumulation point of zeros
$\lambda_{1},\lambda_{2},\ldots$. Let $n_{1},n_{2},\ldots$ be the minimal
integers for which $f^{n_{i}}(\lambda_{i})=-1$. Since for fixed $n$ the zeros
of $Z_{T_{n}}$ are isolated, we may assume that $n_{i}\rightarrow\infty$ and
$(n_{i})$ is strictly increasing.

When for a parameter $\lambda$ the rational function $f$ has an attracting
periodic cycle, the unique critical orbit $\\{f^{n}(0)\\}_{n\geq 1}$ must
converge to this periodic orbit. Since attracting periodic cycles are stable,
i.e. they persist under small changes of the parameter $\lambda$, such
parameters lie in a passivity component, i.e., a maximal connected open subset
where the family $\\{\lambda\mapsto f^{n}(0)\\}$ is normal. The passivity
component agrees exactly with the connected component where the attracting
periodic cycle persists, since by [MnSS83] the parameter must become active
when the periodic cycle becomes neutral.

Thus, $\lambda_{i}$ lies in a connected component of the open set where the
family $\\{\lambda\mapsto f^{n}(0)\\}$ is normal, and associated to this
component is the unique period $n_{i}+2$. Since the sequence
$\\{n_{i}\\}_{i\geq 1}$ is strictly increasing, the parameters $\lambda_{i}$
must all lie in distinct connected components. It follows that the limit
parameter $\lambda_{0}$ cannot lie in an open component where the family is
normal, and therefore $\lambda_{0}$ must be an active parameter. ∎

The activity-locus for Cayley trees of down degree $d=2,3$ and $4$ is
illustrated in Figure 9. Each of these diagrams represents the spherical
derivative of the function $\lambda\mapsto f_{\lambda,d}^{120}(0)$.

(a) down-degree 2

(b) down-degree 4

(c) down-degree 3

Figure 9. The activity-locus of Cayley trees for down-degrees $2,3$ and $4$.
For each pixel the spherical derivative of the occupation ratio is computed
for the Cayley tree of depth $120$. Pixels for which this derivative is
sufficiently large are depicted in white, suggesting that the corresponding
parameter $\lambda$ lies approximately on the activity locus.

It follows from Proposition 7.1 above, plus the observation that zeros do not
lie in the activity-locus for the Cayley tree setting, that the Cayley tree
activity-locus never has interior. On the other hand, it follows from the
universality of the Mandelbrot set, a result due to McMullen [McM00], that the
activity-locus must contain a quasiconformal image of the Mandelbrot set of
some degree. Therefore by Shishikura’s result [Shi98] the Hausdorff dimension
of the activity-locus is equal to $2$ for any $d\geq 2$.

It follows from the proof of Proposition 7.1 that the complement of the
activity-locus consists of infinitely many connected components. Each
$\lambda$ for which $f_{\lambda,d}$ has an attracting periodic cycle lies in
such a passive component, a so-called _hyperbolic_ component associated to the
period $k$. Whether all connected components are hyperbolic is an open
question, which is conjectured to hold for quadratic polynomials.

For any down-degree $d$ there are two special connected components that can
easily be identified. The unbounded component is always a hyperbolic component
of period $2$. For degree $2$ this is the complement of the closed disk of
radius $4$. For down-degrees $3$ and $4$ the boundary has respectively $1$ and
$2$ singular points.

For each down-degree $d=\Delta-1$ there is a single hyperbolic component of
period $1$, which contains of course the parameter $\lambda=0$ and equals the
cardioid $\Lambda_{\Delta}$.

Apart from these two special hyperbolic components, any hyperbolic component
contains a unique zero of the partition function, i.e. a unique parameter
$\lambda$ for which $f_{\lambda,d}^{n}(\lambda)=-1$ for some $n\in\mathbb{N}$.
Since $f_{\lambda,d}^{2}(-1)=0$ and $f_{\lambda,d}^{-2}(0)=\\{-1\\}$, these
are exactly the parameters $\lambda\in\mathbb{C}\setminus\\{0\\}$ for which
the unique critical orbit $\\{f_{\lambda,d}^{i}(0)\\}_{i\in\mathbb{N}}$ is
periodic, i.e. for which $f_{\lambda,d}$ is super-attracting.

For the family $p_{c}(z)=z^{2}+c$ the fact that every hyperbolic component of
the Mandelbrot set contains a unique super-attracting parameter is a
consequence of the Multiplier Theorem, due to Douady-Hubbard and Sullivan, see
[Dou83].

Let us recall this fundamental result in the field. Let $H$ be a hyperbolic
component of the Mandelbrot set, say of period $n$. For every parameter $c\in
H$ there exist an attracting periodic cycle $a_{0},a_{1},\ldots,a_{n}=a_{0}$.
The multiplier $h(c)=(f_{c}^{n})^{\prime}(a_{0})$ is independent from the
choice of $a_{n}$, and gives a holomorphic map from $H$ to the unit disk.

######  Theorem 7.2 (Multiplier Theorem).

For every hyperbolic component $H$ the map $c\mapsto h(c)$ gives a conformal
bijection from $H$ to the unit disk.

The proof of the Multiplier Theorem can be found in [CG93], Theorem 2.1 on
page 133, and can be applied almost directly to our setting. We present a
high-level discussion to outline how the proof adapts to our setting.

Let $H$ be a hyperbolic component of period at least $3$. One easily sees that
$h(\lambda)$, the multiplier of the attracting periodic cycle of
$f_{\lambda,d}$ is a holomorphic and surjective map from the hyperbolic
component $H$ to the unit disk $\mathbb{D}$, hence is a branched covering. Let
$Z$ be the set of super-attracting parameters in $H$, i.e. $Z=h^{-1}(0)$. If
it can be shown that $h:H\setminus Z\rightarrow\mathbb{D}\setminus\\{0\\}$ is
a covering map, it follows from the Riemann-Hurwitz Theorem that
$\mathrm{card}(Z)=1$.

Thus, it needs to be shown that $h$ is locally invertible near parameters
$\lambda_{0}\in H\setminus Z$. Write $\eta_{0}=h(\lambda_{0})\in\mathbb{D}$,
and consider values of $\eta$ near $\eta_{0}$. Following the proof of the
Multiplier Theorem one applies quasiconformal surgery by modifying the ellipse
field near the attracting periodic cycle in order to obtain attracting
periodic cycles with multipliers $\eta$. Using the dynamics the ellipse field
can be extended to the full basin of the attracting cycle, obtaining an
invariant ellipse field that is invariant under the map $f_{\lambda_{0},d}$.
The ellipse field corresponds to a Beltrami coefficient, which can be extended
to the entire Riemann sphere by setting it equal to $0$ outside of the basin
of attraction. The Measurable Riemann Mapping Theorem gives a holomorphic
family of quasiconformal maps $\varphi_{\eta}$, with $\varphi_{\eta_{0}}$ the
identity. By composing with suitable Möbius transformations we can guarantee
that the points $-1,\infty$ and $0$ are fixed under all $\varphi_{\eta}$.

Since each ellipse field is invariant under $f_{\lambda_{0},d}$, conjugating
$f_{\lambda,d}$ by $\varphi_{\eta}$ yields a holomorphic family of self-maps
of the Riemann sphere $g_{\eta,d}$ , which are necessarily rational functions
of the same degree $d$. In fact, since each $\varphi_{\eta}$ fixes the points
$-1,\infty$ and $0$, each rational function $f_{\eta,d}$ must send $-1$ to
$\infty$ and $\infty$ to $0$, each with local degree $d$. It follows that the
rational function $g_{\eta,d}$ must be of the form

$g_{\eta,d}(z)=\frac{\lambda(\eta)}{(1+z)^{d}}.$

It follows that $\lambda(\eta)$ gives a local inverse of the multiplier
function $h$, completing this step of the proof. This step guarantees that
there exists a unique zero in each hyperbolic component of period at least
$3$, which equals the super-attracting _center_ of the hyperbolic component.
The proof of the Multiplier Theorem in our setting can be concluded by
analyzing the local degree near the center. We have therefore obtained the
following description of the zeros of the Cayley trees:

######  Corollary 7.3.

Every $\lambda\in\mathbb{C}$ for which $Z_{T_{n}}(\lambda)=0$ for some
$n\in\mathbb{N}$ is the center of a hyperbolic component of the complement of
the activity locus. On the other hand: apart from the two special hyperbolic
components, the unbounded component and the component containing $0$, for each
center $\lambda$ of a hyperbolic component there exists an $n\in\mathbb{N}$
for which $Z_{T_{n}}(\lambda)=0$. As a consequence zero-parameters are
isolated.

## References

  * [AB09] Sanjeev Arora and Boaz Barak.  Computational complexity.  Cambridge University Press, Cambridge, 2009.  A modern approach.
  * [ALG20] N. Anari, K. Liu, and S. O. Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1319–1330, 2020.
  * [Bar16] Alexander Barvinok.  Combinatorics and complexity of partition functions, volume 30 of Algorithms and Combinatorics.  Springer, Cham, 2016.
  * [Bea95] A. F. Beardon.  The geometry of discrete groups, volume 91 of Graduate Texts in Mathematics.  Springer-Verlag, 1995.
  * [Ben18] Ferenc Bencs.  On trees with real-rooted independence polynomial.  Discrete Math., 341(12):3321–3330, 2018.
  * [BGGv20] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič.  Inapproximability of the independent set polynomial in the complex plane.  SIAM J. Comput., 49(5):STOC18–395–STOC18–448, 2020.
  * [BGPR20] Pjotr Buys, Andreas Galanis, Viresh Patel, and Guus Regts.  Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs.  arXiv preprint arXiv:2006.14828v3, 2020.
  * [Buy21] Pjotr Buys.  Cayley Trees do Not Determine the Maximal Zero-Free Locus of the Independence Polynomial.  Michigan Mathematical Journal, -1(-1):1 – 14, 2021.
  * [CG93] Lennart Carleson and Theodore W. Gamelin.  Complex Dynamics.  Universitext: Tracts in Mathematics. Springer-Verlag, New York, 1993.
  * [Dou83] Adrien Douady.  Systèmes dynamiques holomorphes.  In Bourbaki seminar, Vol. 1982/83, volume 105 of Astérisque, pages 39–63. Soc. Math. France, Paris, 1983.
  * [Gre00] Catherine Greenhill.  The complexity of counting colourings and independent sets in sparse graphs and hypergraphs.  Comput. Complexity, 9(1):52–72, 2000.
  * [HL72] Ole J. Heilmann and Elliott H. Lieb.  Theory of monomer-dimer systems.  Comm. Math. Phys., 25:190–232, 1972.
  * [McM00] Curtis T. McMullen.  The Mandelbrot set is universal.  In The Mandelbrot set, theme and variations, volume 274 of London Math. Soc. Lecture Note Ser., pages 1–17. Cambridge Univ. Press, Cambridge, 2000.
  * [Mil06] John Milnor.  Dynamics in one complex variable, volume 160 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, third edition, 2006.
  * [MnSS83] R. Mañé, P. Sad, and D. Sullivan.  On the dynamics of rational maps.  Ann. Sci. École Norm. Sup. (4), 16(2):193–217, 1983.
  * [PR17] Viresh Patel and Guus Regts.  Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials.  SIAM J. Comput., 46(6):1893–1919, 2017.
  * [PR19] Han Peters and Guus Regts.  On a conjecture of Sokal concerning roots of the independence polynomial.  Michigan Math. J., 68(1):33–55, 2019.
  * [PR20] Han Peters and Guus Regts.  Location of zeros for the partition function of the Ising model on bounded degree graphs.  J. Lond. Math. Soc. (2), 101(2):765–785, 2020.
  * [Rot96] Dan Roth.  On the hardness of approximate reasoning.  Artificial Intelligence, 82(1-2):273–302, 1996.
  * [She85] J. B. Shearer.  On a problem of Spencer.  Combinatorica, 5(3):241–245, 1985.
  * [Shi98] Mitsuhiro Shishikura.  The Hausdorff dimension of the boundary of the Mandelbrot set and Julia sets.  Ann. of Math. (2), 147(2):225–267, 1998.
  * [SS05] Alexander D. Scott and Alan D. Sokal.  The repulsive lattice gas, the independent-set polynomial, and the lovász local lemma.  Journal of Statistical Physics, 118(5-6):1151–1261, Mar 2005.
  * [SS14] Allan Sly and Nike Sun.  Counting in two-spin models on $d$-regular graphs.  Ann. Probab., 42(6):2383–2416, 2014.
  * [Vad01] Salil P. Vadhan.  The complexity of counting in sparse, regular, and planar graphs.  SIAM J. Comput., 31(2):398–427, 2001.
  * [Val79] L. G. Valiant.  The complexity of computing the permanent.  Theoret. Comput. Sci., 8(2):189–201, 1979.
  * [Wei06] Dror Weitz.  Counting independent sets up to the tree threshold.  In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 140–149. ACM, New York, 2006.
  * [YL52] C. N. Yang and T. D. Lee.  Statistical theory of equations of state and phase transitions. I. Theory of condensation.  Phys. Rev. (2), 87:404–409, 1952.